[LLVMdev] df_ext_iterator in LiveIntervalAnalysis

Chris Lattner sabre at nondot.org
Fri Jun 22 13:30:10 PDT 2007


On Fri, 22 Jun 2007, Evan Cheng wrote:
> Nice idea. Please also try using SmallPtrSet (with a sufficiently
> large size) instead of std::set for traversal after everything is
> working. Using std::set can really hurt compile time in case of large
> basic block numbers.

> Is there a way to dynamically adjust "SmallSize" based on number of
> basic blocks in the function?

Nope.  The small size for SmallSet really should be "small" anyway (say < 
32).  For sets below that threshold, queries do a linear scan of all the 
elements to determine if something is inside the set.

-Chris

> On Jun 21, 2007, at 10:20 PM, Fernando Magno Quintao Pereira wrote:
>
>>
>> I would like to make a suggestion. In the LiveIntervalAnalysis class,
>> instead of numbering the instructions in the order in which basic
>> blocks
>> are stored in the machine function, use the df_ext_iterator. It
>> will order
>> the instruction according to the dominance tree (or it seems to be
>> doing
>> so). There are many advantages in doing this. One of them is that,
>> once
>> you traverse the dominance tree to find the live intervals, they
>> will be
>> contiguous, you don't have to handle holes. Could someone tell me
>> if there
>> is any problem in doing this? In my version of LLVM, I just
>> had to make two changes in LiveIntervalAnalysis:
>>
>> //===---------------------------------------
>> First: when numbering the instructions:
>> // <-- new code
>> //===---------------------------------------
>>    unsigned miIndex = 0;
>>    MachineBasicBlock *entry = mf_->begin();
>>    std::set<MachineBasicBlock*> visited;
>>    for (df_ext_iterator<MachineBasicBlock*> dfi = df_ext_begin(entry,
>> visited),
>>                        endi = df_ext_end(entry, visited); dfi != endi;
>> ++dfi) {
>>        MachineBasicBlock *mbb = *dfi;
>>        for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd =
>> mbb->end();
>>                                                            mi !=
>> miEnd;
>> ++mi) {
>>          bool inserted = mi2iMap_.insert(std::make_pair(mi,
>> miIndex)).second;
>>          assert(inserted && "multiple MachineInstr -> index
>> mappings");
>>          i2miMap_.push_back(mi);
>>          miIndex += InstrSlots::NUM;
>>        }
>>    }
>>    this->maxInstrIndex_ = miIndex;
>> //===---------------------------------------
>> // --> old code
>> //===---------------------------------------
>>    unsigned miIndex = 0;
>>    for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_-
>>> end();
>>         mbb != mbbEnd; ++mbb) {
>>      for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd =
>> mbb->end();
>>           mi != miEnd; ++mi) {
>>        bool inserted = mi2iMap_.insert(std::make_pair(mi,
>> miIndex)).second;
>>        assert(inserted && "multiple MachineInstr -> index mappings");
>>        i2miMap_.push_back(mi);
>>        miIndex += InstrSlots::NUM;
>>      }
>>    }
>>    this->maxInstrIndex_ = miIndex;
>>
>> //===---------------------------------------
>> Second: when computing the intervals:
>> // <-- new code
>> //===---------------------------------------
>>    MachineBasicBlock *entry = mf_->begin();
>>    std::set<MachineBasicBlock*> visited;
>>    for (df_ext_iterator<MachineBasicBlock*> dfi = df_ext_begin(entry,
>> visited),
>>                           end = df_ext_end(entry, visited); dfi !=
>> end;
>> ++dfi) {
>>        MachineBasicBlock *mbb = *dfi;
>> //===---------------------------------------
>> // --> old code
>> //===---------------------------------------
>> //  for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
>> //       I != E; ++I) {
>> //    MachineBasicBlock* mbb = I;
>>
>> Fernando
>> _______________________________________________
>> 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
>

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/



More information about the llvm-dev mailing list