[LLVMdev] Some questions about live intervals

[Evan Cheng]

On Feb 10, 2008, at 11:44 PM, Roman Levenstein wrote:

> Hi Evan,
>
> --- Evan Cheng <evan.cheng at apple.com> wrote:
>
>> Thanks. One question though. Should getMBBFromIndex() assert if given
>> an index out of the range or simply returns a NULL pointer? I would
>> think the later makes it a bit more friendly.
>
> Yes. It would be more friendly, probably. I can submit such a patch,  
> if
> you think it suits better.
>
> On the other hand I want to mention the following pros:
> - assert-based approach follows the style of all other getNNN
> functions in LiveIntervalAnalysis.h. They all assert in out-of-range
> cases.
> - What does it mean, if you have a situation where you ask for the MBB
> of an instruction index, which is out of range for any MBB? How can
> this happen? If you know the index, then instruction should have been
> already registered before, it's number is known and it is supposed to
> belong to an MBB. If not, some internal mapping tables (e.g. start and
> end of MBBs, index to MBB mappings, etc) in LiveIntervalAnalysis are
> likely to be broken. In this case, it is better to assert() in those
> cases, IMHO.
>
> Please, let me know, if I should sumbit a patch without any assert()
> and returning just a NULL pointer.

Now I think either approach is fine. Please commit. Thanks!

Evan

>
>
> -Roman
>
>
>> On Feb 8, 2008, at 8:59 AM, Roman Levenstein wrote:
>>
>>> Hi Evan,
>>>
>>> Here is a patch for the LiveIntervalAnalysis that we discussed.
>>>
>>> --- Evan Cheng <evan.cheng at apple.com> schrieb:
>>>>> 1) What is the easiest way to understand which MBB a given
>>>> instruction index belongs to? All the required information is
>>>> available in the
>>>>> MBB2IdxMap of the LiveIntervalAnalysis class. Would it be useful
>>>> to add  a small function getMBBFromIndex() to this class?
>>>>
>>>> Sure there is a reverse map (actually just a vector) Idx2MBBMap.
>>>> Justadd a query.
>>>
>>> Done. Please find a patch attached to this mail.
>>>
>>>>> As for (1) and (2), I could implement and provide patches for it,
>>>>> if you think this is desirable.
>>>>
>>>> Yes, thanks.
>>>
>>> Here you are!
>>>
>>> -Roman
>>>
>>>
>>>     Lesen Sie Ihre E-Mails auf dem Handy.
>>> www.yahoo.de/goIndex: lib/CodeGen/LiveIntervalAnalysis.cpp
>>> ===================================================================
>>> --- lib/CodeGen/LiveIntervalAnalysis.cpp	(revision 46884)
>>> +++ lib/CodeGen/LiveIntervalAnalysis.cpp	(working copy)
>>> @@ -79,22 +79,7 @@
>>>    delete ClonedMIs[i];
>>> }
>>>
>>> -namespace llvm {
>>> -  inline bool operator<(unsigned V, const IdxMBBPair &IM) {
>>> -    return V < IM.first;
>>> -  }
>>>
>>> -  inline bool operator<(const IdxMBBPair &IM, unsigned V) {
>>> -    return IM.first < V;
>>> -  }
>>> -
>>> -  struct Idx2MBBCompare {
>>> -    bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS)
>>
>>> const {
>>> -      return LHS.first < RHS.first;
>>> -    }
>>> -  };
>>> -}
>>> -
>>> Index: include/llvm/CodeGen/LiveIntervalAnalysis.h
>>> ===================================================================
>>> --- include/llvm/CodeGen/LiveIntervalAnalysis.h	(revision 46884)
>>> +++ include/llvm/CodeGen/LiveIntervalAnalysis.h	(working copy)
>>> @@ -40,6 +40,20 @@
>>>  class VirtRegMap;
>>>  typedef std::pair<unsigned, MachineBasicBlock*> IdxMBBPair;
>>>
>>> +  inline bool operator<(unsigned V, const IdxMBBPair &IM) {
>>> +    return V < IM.first;
>>> +  }
>>> +
>>> +  inline bool operator<(const IdxMBBPair &IM, unsigned V) {
>>> +    return IM.first < V;
>>> +  }
>>> +
>>> +  struct Idx2MBBCompare {
>>> +    bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS)
>>
>>> const {
>>> +      return LHS.first < RHS.first;
>>> +    }
>>> +  };
>>> +
>>>  class LiveIntervals : public MachineFunctionPass {
>>>    MachineFunction* mf_;
>>>    const TargetMachine* tm_;
>>> @@ -153,6 +167,23 @@
>>>      return MBB2IdxMap[MBBNo].second;
>>>    }
>>>
>>> +    /// getMBBFromIndex - given an index in any instruction of an
>>> +    /// MBB return a pointer the MBB
>>> +    MachineBasicBlock* getMBBFromIndex(unsigned index) const {
>>> +      std::vector<IdxMBBPair>::const_iterator I =
>>> +	    std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(),
>> index);
>>> +
>>> +      // Take previous pair
>>> +      std::vector<IdxMBBPair>::const_iterator J =
>>> +	  ((I != Idx2MBBMap.end() && I->first > index) ||
>>> +	   (I == Idx2MBBMap.end() && Idx2MBBMap.size()>0)) ? (I-1): I;
>>> +
>>> +      assert(J != Idx2MBBMap.end() && J->first < index+1 &&
>>> +	     index < getMBBEndIdx(J->second) &&
>>> +	     "index does not correspond to an MBB");
>>> +      return J->second;
>>> +    }
>>> +
>>>    /// getInstructionIndex - returns the base index of instr
>>>    unsigned getInstructionIndex(MachineInstr* instr) const {
>>>      Mi2IndexMap::const_iterator it = mi2iMap_.find(instr);
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>
>
>
>       __________________________________  Ihre erste Baustelle?  
> Wissenswertes für Bastler und Hobby Handwerker. www.yahoo.de/clever
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev