[LLVMdev] ilistification of MachineBasicBlock

[Alkis Evlogimenos]

Hi all,

Two days ago MachineBasicBlock got ilistified. What does this mean and 
how does it affect you? Read on.

MachineBasicBlock used to have a std::vector<MachineInstr*> to represent 
the instructions it constisted of. This representation has the following 
problems:
     1) O(n) insertions/removals to/from anywhere but the end of a basic 
block (removals are very comomn in peephole optimizers and insertions in 
register allocators)
     2) After an insertion all std::vector<MachineInstr*>::iterators are 
invalidated.
     3) After an erase all std::vector<MachineInstr*>::iterators after 
it are invalidated.

After ilistification, MachineBasicBlock uses an ilist<MachineInstr> data 
structure (include/Support/ilist). The ilist (short for intrusive list) 
is a lot like std::list but with the additional benefit of allowing the 
conversion of a MachineInstr* to an ilist<MachineInstr>::iterator with 
no cost whatsoever. With this data structure we get:
     1) O(1) insertion/removals to/from anywhere in the basic block
     2) insertion/removals do not invalidate any iterators (other than 
the one being erased of course).

Now since the new container holds instances of MachineInstr objects and 
not pointers to them for loops that used to be written as:

     for (MachineBasicBlock::iterator i = insts.begin(), e = 
insts.end(); i != e; ++) {
         MachineInstr* instr_pointer = *i;
         MachineInstr& instr_ref = **i;
will need to be changed to:

     for (MachineBasicBlock::iterator i = insts.begin(), e = 
insts.end(); i != e; ++) {
         MachineInstr* instr_pointer = i;
         MachineInstr& instr_ref = *i;

Note the implicit conversion from ilist<MachineInstr>::iterator to 
MachineInstr* and the one less dereference operator needed to get a 
reference to the object.

You must also take care when using MachineBasicBlock's operator[]. It is 
there strictly for compatibility purposes and will be removed when we 
get around eliminating its use.  It internally uses std::advance to 
increment the ilist's begin() iterator the specified number of times and 
as such it is not an efficient way of accessing the list.

I hope this helps to get your code working with this new interface.

If you have any questions feel free to reply to this email.

-- 

Alkis