[LLVMdev] df_ext_iterator in LiveIntervalAnalysis

Roman Levenstein romixlev at gmail.com
Fri Jun 22 10:57:59 PDT 2007


Hi,

Just my two cents:

If I recall correctly, in some papers on the linear scan register 
allocation people described that they tried different orderings for 
instruction numbering, e.g. including DFS or based on the loop nesting 
levels, etc. There was no clear winner though.

But let's see the numbers anyway. May be it really brings some improvements.

-Roman

Chris Lattner wrote:
> On Thu, 21 Jun 2007, 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:
> 
> That should work fine.  Please do it, then do some 
> compile-time/code-quality comparisons to see if it's better :)
> 
> good numbers + code = patch committed to cvs :)
> 
> Thanks, nice idea btw!
> 
> -Chris
> 
>> //===---------------------------------------
>> 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
>>
> 
> -Chris
> 




More information about the llvm-dev mailing list