[LLVMdev] df_ext_iterator in LiveIntervalAnalysis

[Chris Lattner]

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

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