[LLVMdev] df_ext_iterator in LiveIntervalAnalysis

[Evan Cheng]

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?

Evan

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