[LLVMdev] df_ext_iterator in LiveIntervalAnalysis

[Fernando Magno Quintao Pereira]

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