Change MachineBasicBlock's vector of MachineInstr pointers into an

ilist of MachineInstr objects. This allows constant time removal and
insertion of MachineInstr instances from anywhere in each
MachineBasicBlock. It also allows for constant time splicing of
MachineInstrs into or out of MachineBasicBlocks.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11340 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 44 insertions, 26 deletions

diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h
index b8a0361f7f..7285057210 100644
--- a/include/llvm/CodeGen/MachineBasicBlock.h
+++ b/include/llvm/CodeGen/MachineBasicBlock.h
@@ -14,16 +14,17 @@
 #ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H
 #define LLVM_CODEGEN_MACHINEBASICBLOCK_H
 
-#include <vector>
+#include "llvm/CodeGen/MachineInstr.h"
+#include "Support/ilist"
 
 namespace llvm {
 
 class BasicBlock;
-class MachineInstr;
-template <typename T> struct ilist_traits;
 
 class MachineBasicBlock {
-  std::vector<MachineInstr*> Insts;
+public:
+  typedef ilist<MachineInstr> Instructions;
+  Instructions Insts;
   MachineBasicBlock *Prev, *Next;
   const BasicBlock *BB;
 public:
@@ -35,19 +36,27 @@ public:
   ///
   const BasicBlock *getBasicBlock() const { return BB; }
   
-  typedef std::vector<MachineInstr*>::iterator                iterator;
-  typedef std::vector<MachineInstr*>::const_iterator    const_iterator;
+  typedef ilist<MachineInstr>::iterator                       iterator;
+  typedef ilist<MachineInstr>::const_iterator           const_iterator;
   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
   typedef std::reverse_iterator<iterator>             reverse_iterator;
 
   unsigned size() const { return Insts.size(); }
   bool empty() const { return Insts.empty(); }
 
-  MachineInstr * operator[](unsigned i) const { return Insts[i]; }
-  MachineInstr *&operator[](unsigned i)       { return Insts[i]; }
+  const MachineInstr& operator[](unsigned i) const {
+      const_iterator it = Insts.begin();
+      std::advance(it, i);
+      return *it;
+  }
+  MachineInstr& operator[](unsigned i) {
+      iterator it = Insts.begin();
+      std::advance(it, i);
+      return *it;
+  }
 
-  MachineInstr *front() const { return Insts.front(); }
-  MachineInstr *back()  const { return Insts.back(); }
+  MachineInstr& front() { return Insts.front(); }
+  MachineInstr& back()  { return Insts.back(); }
 
   iterator                begin()       { return Insts.begin();  }
   const_iterator          begin() const { return Insts.begin();  }
@@ -64,16 +73,11 @@ public:
   iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); }
 
   // erase - Remove the specified element or range from the instruction list.
-  // These functions do not delete any instructions removed.
+  // These functions delete any instructions removed.
   //
   iterator erase(iterator I)             { return Insts.erase(I); }
   iterator erase(iterator I, iterator E) { return Insts.erase(I, E); }
-
-  MachineInstr *pop_back() {
-    MachineInstr *R = back();
-    Insts.pop_back();
-    return R;
-  }
+  MachineInstr* remove(iterator &I)      { return Insts.remove(I); }
 
 private:   // Methods used to maintain doubly linked list of blocks...
   friend class ilist_traits<MachineBasicBlock>;
diff --git a/include/llvm/CodeGen/MachineFunction.h b/include/llvm/CodeGen/MachineFunction.h
index 4f255598d3..2c443967ee 100644
--- a/include/llvm/CodeGen/MachineFunction.h
+++ b/include/llvm/CodeGen/MachineFunction.h
@@ -20,7 +20,6 @@
 
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "Support/Annotation.h"
-#include "Support/ilist"
 
 namespace llvm {
 
diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index ff05631d40..0cc46b0c54 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -28,6 +28,8 @@ class MachineBasicBlock;
 class TargetMachine;
 class GlobalValue;
 
+template <typename T> class ilist_traits;
+
 typedef int MachineOpCode;
 
 //===----------------------------------------------------------------------===//
@@ -353,12 +355,24 @@ class MachineInstr {
   unsigned         opCodeFlags;         // flags modifying instrn behavior
   std::vector<MachineOperand> operands; // the operands
   unsigned numImplicitRefs;             // number of implicit operands
-
+  MachineInstr* prev, *next;            // links for our intrusive list
   // OperandComplete - Return true if it's illegal to add a new operand
   bool OperandsComplete() const;
 
   MachineInstr(const MachineInstr &);  // DO NOT IMPLEMENT
   void operator=(const MachineInstr&); // DO NOT IMPLEMENT
+
+private:
+  // Intrusive list support
+  //
+  friend class ilist_traits<MachineInstr>;
+  MachineInstr() { /* this is for ilist use only to create the sentinel */ }
+  MachineInstr* getPrev() const { return prev; }
+  MachineInstr* getNext() const { return next; }
+
+  void setPrev(MachineInstr* mi) { prev = mi; }
+  void setNext(MachineInstr* mi) { next = mi; }
+
 public:
   MachineInstr(int Opcode, unsigned numOperands);
 
diff --git a/include/llvm/Target/MRegisterInfo.h b/include/llvm/Target/MRegisterInfo.h
index b808ca3001..61c594ceb3 100644
--- a/include/llvm/Target/MRegisterInfo.h
+++ b/include/llvm/Target/MRegisterInfo.h
@@ -16,13 +16,14 @@
 #ifndef LLVM_TARGET_MREGISTERINFO_H
 #define LLVM_TARGET_MREGISTERINFO_H
 
-#include "llvm/CodeGen/MachineBasicBlock.h"
 #include <cassert>
 
 namespace llvm {
 
 class Type;
+class MachineBasicBlock;
 class MachineFunction;
+class MachineInstr;
 
 /// MRegisterDesc - This record contains all of the information known about a
 /// particular register.  The AliasSet field (if not null) contains a pointer to
@@ -226,17 +227,17 @@ public:
   //
 
   virtual int storeRegToStackSlot(MachineBasicBlock &MBB,
-                                  MachineBasicBlock::iterator &MBBI,
+                                  MachineInstr* MI,
                                   unsigned SrcReg, int FrameIndex,
                                   const TargetRegisterClass *RC) const = 0;
 
   virtual int loadRegFromStackSlot(MachineBasicBlock &MBB,
-                                   MachineBasicBlock::iterator &MBBI,
+                                   MachineInstr* MI,
                                    unsigned DestReg, int FrameIndex,
                                    const TargetRegisterClass *RC) const = 0;
 
   virtual int copyRegToReg(MachineBasicBlock &MBB,
-                           MachineBasicBlock::iterator &MBBI,
+                           MachineInstr* MI,
                            unsigned DestReg, unsigned SrcReg,
                            const TargetRegisterClass *RC) const = 0;
 
@@ -260,8 +261,8 @@ public:
   /// instructions added to (negative if removed from) the basic block.
   ///
   virtual int eliminateCallFramePseudoInstr(MachineFunction &MF,
-					     MachineBasicBlock &MBB,
-                                         MachineBasicBlock::iterator &I) const {
+                                            MachineBasicBlock &MBB,
+                                            MachineInstr* MI) const {
     assert(getCallFrameSetupOpcode()== -1 && getCallFrameDestroyOpcode()== -1 &&
 	   "eliminateCallFramePseudoInstr must be implemented if using"
 	   " call frame setup/destroy pseudo instructions!");
@@ -289,7 +290,7 @@ public:
   /// added to (negative if removed from) the basic block.
   ///
   virtual int eliminateFrameIndex(MachineFunction &MF,
-                                  MachineBasicBlock::iterator &II) const = 0;
+                                  MachineInstr* MI) const = 0;
 
   /// emitProlog/emitEpilog - These methods insert prolog and epilog code into
   /// the function. The return value is the number of instructions