ilistification of MachineBasicBlock

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.