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

41 files changed, 380 insertions, 408 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
diff --git a/lib/CodeGen/InstrSched/InstrScheduling.cpp b/lib/CodeGen/InstrSched/InstrScheduling.cpp
index 7d2ececab1..f01196aefa 100644
--- a/lib/CodeGen/InstrSched/InstrScheduling.cpp
+++ b/lib/CodeGen/InstrSched/InstrScheduling.cpp
@@ -630,8 +630,8 @@ RecordSchedule(MachineBasicBlock &MBB, const SchedulingManager& S)
   // some NOPs from delay slots.  Also, PHIs are not included in the schedule.
   unsigned numInstr = 0;
   for (MachineBasicBlock::iterator I=MBB.begin(); I != MBB.end(); ++I)
-    if (! mii.isNop((*I)->getOpcode()) &&
-	! mii.isDummyPhiInstr((*I)->getOpcode()))
+    if (! mii.isNop(I->getOpcode()) &&
+	! mii.isDummyPhiInstr(I->getOpcode()))
       ++numInstr;
   assert(S.isched.getNumInstructions() >= numInstr &&
 	 "Lost some non-NOP instructions during scheduling!");
@@ -643,12 +643,12 @@ RecordSchedule(MachineBasicBlock &MBB, const SchedulingManager& S)
   // First find the dummy instructions at the start of the basic block
   MachineBasicBlock::iterator I = MBB.begin();
   for ( ; I != MBB.end(); ++I)
-    if (! mii.isDummyPhiInstr((*I)->getOpcode()))
+    if (! mii.isDummyPhiInstr(I->getOpcode()))
       break;
   
-  // Erase all except the dummy PHI instructions from MBB, and
+  // Remove all except the dummy PHI instructions from MBB, and
   // pre-allocate create space for the ones we will put back in.
-  MBB.erase(I, MBB.end());
+  while (I != MBB.end()) MBB.remove(I);
   
   InstrSchedule::const_iterator NIend = S.isched.end();
   for (InstrSchedule::const_iterator NI = S.isched.begin(); NI != NIend; ++NI)
@@ -1175,25 +1175,25 @@ static void ReplaceNopsWithUsefulInstr(SchedulingManager& S,
   //  
   unsigned int firstDelaySlotIdx = node->getOrigIndexInBB() + 1;
   MachineBasicBlock& MBB = node->getMachineBasicBlock();
-  assert(MBB[firstDelaySlotIdx - 1] == brInstr &&
+  assert(&MBB[firstDelaySlotIdx - 1] == brInstr &&
          "Incorrect instr. index in basic block for brInstr");
   
   // First find all useful instructions already in the delay slots
   // and USE THEM.  We'll throw away the unused alternatives below
   // 
   for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
-    if (! mii.isNop(MBB[i]->getOpcode()))
+    if (! mii.isNop(MBB[i].getOpcode()))
       sdelayNodeVec.insert(sdelayNodeVec.begin(),
-                           graph->getGraphNodeForInstr(MBB[i]));
+                           graph->getGraphNodeForInstr(&MBB[i]));
   
   // Then find the NOPs and keep only as many as are needed.
   // Put the rest in nopNodeVec to be deleted.
   for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
-    if (mii.isNop(MBB[i]->getOpcode()))
+    if (mii.isNop(MBB[i].getOpcode()))
       if (sdelayNodeVec.size() < ndelays)
-        sdelayNodeVec.push_back(graph->getGraphNodeForInstr(MBB[i]));
+        sdelayNodeVec.push_back(graph->getGraphNodeForInstr(&MBB[i]));
       else {
-        nopNodeVec.push_back(graph->getGraphNodeForInstr(MBB[i]));
+        nopNodeVec.push_back(graph->getGraphNodeForInstr(&MBB[i]));
 	  
         //remove the MI from the Machine Code For Instruction
         const TerminatorInst *TI = MBB.getBasicBlock()->getTerminator();
@@ -1202,7 +1202,7 @@ static void ReplaceNopsWithUsefulInstr(SchedulingManager& S,
           
         for(MachineCodeForInstruction::iterator mciI=llvmMvec.begin(), 
               mciE=llvmMvec.end(); mciI!=mciE; ++mciI){
-          if (*mciI==MBB[i])
+          if (*mciI == &MBB[i])
             llvmMvec.erase(mciI);
         }
       }
@@ -1282,10 +1282,10 @@ ChooseInstructionsForDelaySlots(SchedulingManager& S, MachineBasicBlock &MBB,
   // 
   delayNodeVec.clear();
   for (unsigned i=0; i < MBB.size(); ++i)
-    if (MBB[i] != brInstr &&
-        mii.getNumDelaySlots(MBB[i]->getOpcode()) > 0)
+    if (&MBB[i] != brInstr &&
+        mii.getNumDelaySlots(MBB[i].getOpcode()) > 0)
     {
-      SchedGraphNode* node = graph->getGraphNodeForInstr(MBB[i]);
+      SchedGraphNode* node = graph->getGraphNodeForInstr(&MBB[i]);
       ReplaceNopsWithUsefulInstr(S, node, delayNodeVec, graph);
     }
 }
diff --git a/lib/CodeGen/InstrSched/SchedGraph.cpp b/lib/CodeGen/InstrSched/SchedGraph.cpp
index fe150c243a..01ca36ff6a 100644
--- a/lib/CodeGen/InstrSched/SchedGraph.cpp
+++ b/lib/CodeGen/InstrSched/SchedGraph.cpp
@@ -53,7 +53,8 @@ struct ValueToDefVecMap: public hash_map<const Value*, RefVec> {
 
 SchedGraphNode::SchedGraphNode(unsigned NID, MachineBasicBlock *mbb,
                                int   indexInBB, const TargetMachine& Target)
-  : SchedGraphNodeCommon(NID,indexInBB), MBB(mbb), MI(mbb ? (*mbb)[indexInBB] : 0) {
+  : SchedGraphNodeCommon(NID,indexInBB), MBB(mbb),
+    MI(mbb ? &(*mbb)[indexInBB] : (MachineInstr*)0) {
   if (MI) {
     MachineOpCode mopCode = MI->getOpcode();
     latency = Target.getInstrInfo().hasResultInterlock(mopCode)
@@ -183,10 +184,10 @@ void SchedGraph::addCDEdges(const TerminatorInst* term,
   // all preceding instructions in the basic block.  Use 0 latency again.
   // 
   for (unsigned i=0, N=MBB.size(); i < N; i++)  {
-    if (MBB[i] == termMvec[first])   // reached the first branch
+    if (&MBB[i] == termMvec[first])   // reached the first branch
       break;
     
-    SchedGraphNode* fromNode = this->getGraphNodeForInstr(MBB[i]);
+    SchedGraphNode* fromNode = this->getGraphNodeForInstr(&MBB[i]);
     if (fromNode == NULL)
       continue;			// dummy instruction, e.g., PHI
     
@@ -198,11 +199,11 @@ void SchedGraph::addCDEdges(const TerminatorInst* term,
     // the terminator) that also have delay slots, add an outgoing edge
     // from the instruction to the instructions in the delay slots.
     // 
-    unsigned d = mii.getNumDelaySlots(MBB[i]->getOpcode());
+    unsigned d = mii.getNumDelaySlots(MBB[i].getOpcode());
     assert(i+d < N && "Insufficient delay slots for instruction?");
       
     for (unsigned j=1; j <= d; j++) {
-      SchedGraphNode* toNode = this->getGraphNodeForInstr(MBB[i+j]);
+      SchedGraphNode* toNode = this->getGraphNodeForInstr(&MBB[i+j]);
       assert(toNode && "No node for machine instr in delay slot?");
       (void) new SchedGraphEdge(fromNode, toNode,
                                 SchedGraphEdge::CtrlDep,
@@ -554,9 +555,9 @@ void SchedGraph::buildNodesForBB(const TargetMachine& target,
   // Build graph nodes for each VM instruction and gather def/use info.
   // Do both those together in a single pass over all machine instructions.
   for (unsigned i=0; i < MBB.size(); i++)
-    if (!mii.isDummyPhiInstr(MBB[i]->getOpcode())) {
+    if (!mii.isDummyPhiInstr(MBB[i].getOpcode())) {
       SchedGraphNode* node = new SchedGraphNode(getNumNodes(), &MBB, i, target);
-      noteGraphNodeForInstr(MBB[i], node);
+      noteGraphNodeForInstr(&MBB[i], node);
       
       // Remember all register references and value defs
       findDefUseInfoAtInstr(target, node, memNodeVec, callDepNodeVec,
@@ -632,7 +633,7 @@ void SchedGraph::buildGraph(const TargetMachine& target) {
   
   // Then add incoming def-use (SSA) edges for each machine instruction.
   for (unsigned i=0, N=MBB.size(); i < N; i++)
-    addEdgesForInstruction(*MBB[i], valueToDefVecMap, target);
+    addEdgesForInstruction(MBB[i], valueToDefVecMap, target);
 
   // Then add edges for dependences on machine registers
   this->addMachineRegEdges(regToRefVecMap, target);
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index caa9e2e391..9bee8955fa 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -92,7 +92,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
 
         for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
              mi != miEnd; ++mi) {
-            inserted = mi2iMap_.insert(std::make_pair(*mi, miIndex)).second;
+            inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second;
             assert(inserted && "multiple MachineInstr -> index mappings");
             miIndex += 2;
         }
@@ -109,12 +109,10 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
         const MachineBasicBlock* mbb = mbbi;
         unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock());
 
-        for (MachineBasicBlock::const_iterator mii = mbb->begin(),
-                 mie = mbb->end(); mii != mie; ++mii) {
-            MachineInstr* mi = *mii;
-
+        for (MachineBasicBlock::const_iterator mi = mbb->begin(),
+                 mie = mbb->end(); mi != mie; ++mi) {
             for (int i = mi->getNumOperands() - 1; i >= 0; --i) {
-                MachineOperand& mop = mi->getOperand(i);
+                const MachineOperand& mop = mi->getOperand(i);
                 if (mop.isRegister() &&
                     MRegisterInfo::isVirtualRegister(mop.getReg())) {
                     unsigned reg = mop.getAllocatedRegNum();
@@ -169,8 +167,8 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb,
             if (vi.AliveBlocks[i]) {
                 MachineBasicBlock* mbb = lv_->getIndexMachineBasicBlock(i);
                 if (!mbb->empty()) {
-                    interval->addRange(getInstructionIndex(mbb->front()),
-                                       getInstructionIndex(mbb->back()) + 1);
+                    interval->addRange(getInstructionIndex(&mbb->front()),
+                                       getInstructionIndex(&mbb->back()) + 1);
                 }
             }
         }
@@ -181,7 +179,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb,
 
     // we consider defs to happen at the second time slot of the
     // instruction
-    unsigned instrIndex = getInstructionIndex(*mi) + 1;
+    unsigned instrIndex = getInstructionIndex(mi) + 1;
 
     bool killedInDefiningBasicBlock = false;
     for (int i = 0, e = vi.Kills.size(); i != e; ++i) {
@@ -189,8 +187,8 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb,
         MachineInstr* killerInstr = vi.Kills[i].second;
         unsigned start = (mbb == killerBlock ?
                           instrIndex :
-                          getInstructionIndex(killerBlock->front()));
-        unsigned end = (killerInstr == *mi ?
+                          getInstructionIndex(&killerBlock->front()));
+        unsigned end = (killerInstr == mi ?
                         instrIndex + 1 : // dead
                         getInstructionIndex(killerInstr) + 1); // killed
         // we do not want to add invalid ranges. these can happen when
@@ -204,7 +202,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb,
     }
 
     if (!killedInDefiningBasicBlock) {
-        unsigned end = getInstructionIndex(mbb->back()) + 1;
+        unsigned end = getInstructionIndex(&mbb->back()) + 1;
         interval->addRange(instrIndex, end);
     }
 }
@@ -221,10 +219,10 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb,
     // we consider defs to happen at the second time slot of the
     // instruction
     unsigned start, end;
-    start = end = getInstructionIndex(*mi) + 1;
+    start = end = getInstructionIndex(mi) + 1;
 
     // a variable can be dead by the instruction defining it
-    for (KillIter ki = lv_->dead_begin(*mi), ke = lv_->dead_end(*mi);
+    for (KillIter ki = lv_->dead_begin(mi), ke = lv_->dead_end(mi);
          ki != ke; ++ki) {
         if (reg == ki->second) {
             DEBUG(std::cerr << " dead\n");
@@ -237,7 +235,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb,
     do {
         ++mi;
         end += 2;
-        for (KillIter ki = lv_->killed_begin(*mi), ke = lv_->killed_end(*mi);
+        for (KillIter ki = lv_->killed_begin(mi), ke = lv_->killed_end(mi);
              ki != ke; ++ki) {
             if (reg == ki->second) {
                 DEBUG(std::cerr << " killed\n");
@@ -301,19 +299,18 @@ void LiveIntervals::computeIntervals()
 
         for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
              mi != miEnd; ++mi) {
-            MachineInstr* instr = *mi;
             const TargetInstrDescriptor& tid =
-                tm_->getInstrInfo().get(instr->getOpcode());
-            DEBUG(std::cerr << "\t[" << getInstructionIndex(instr) << "] ";
-                  instr->print(std::cerr, *tm_););
+                tm_->getInstrInfo().get(mi->getOpcode());
+            DEBUG(std::cerr << "\t[" << getInstructionIndex(mi) << "] ";
+                  mi->print(std::cerr, *tm_););
 
             // handle implicit defs
             for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
                 handleRegisterDef(mbb, mi, *id);
 
             // handle explicit defs
-            for (int i = instr->getNumOperands() - 1; i >= 0; --i) {
-                MachineOperand& mop = instr->getOperand(i);
+            for (int i = mi->getNumOperands() - 1; i >= 0; --i) {
+                MachineOperand& mop = mi->getOperand(i);
                 // handle register defs - build intervals
                 if (mop.isRegister() && mop.isDef())
                     handleRegisterDef(mbb, mi, mop.getAllocatedRegNum());
@@ -336,15 +333,14 @@ void LiveIntervals::joinIntervals()
 
     const TargetInstrInfo& tii = tm_->getInstrInfo();
 
-    for (MachineFunction::const_iterator mbbi = mf_->begin(),
-             mbbe = mf_->end(); mbbi != mbbe; ++mbbi) {
-        const MachineBasicBlock* mbb = mbbi;
+    for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
+         mbbi != mbbe; ++mbbi) {
+        MachineBasicBlock* mbb = mbbi;
         DEBUG(std::cerr << "machine basic block: "
               << mbb->getBasicBlock()->getName() << "\n");
 
-        for (MachineBasicBlock::const_iterator mii = mbb->begin(),
-                 mie = mbb->end(); mii != mie; ++mii) {
-            MachineInstr* mi = *mii;
+        for (MachineBasicBlock::iterator mi = mbb->begin(), mie = mbb->end();
+             mi != mie; ++mi) {
             const TargetInstrDescriptor& tid =
                 tm_->getInstrInfo().get(mi->getOpcode());
             DEBUG(std::cerr << "\t\tinstruction["
diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp
index fcc78c0550..420cb4443e 100644
--- a/lib/CodeGen/LiveVariables.cpp
+++ b/lib/CodeGen/LiveVariables.cpp
@@ -213,7 +213,7 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &MF) {
     // Loop over all of the instructions, processing them.
     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
 	 I != E; ++I) {
-      MachineInstr *MI = *I;
+      MachineInstr *MI = I;
       const TargetInstrDescriptor &MID = TII.get(MI->getOpcode());
 
       // Process all of the operands of the instruction...
@@ -275,9 +275,8 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &MF) {
       MachineBasicBlock *Succ = BBMap.find(*SI)->second.first;
       
       // PHI nodes are guaranteed to be at the top of the block...
-      for (MachineBasicBlock::iterator I = Succ->begin(), E = Succ->end();
-	   I != E && (*I)->getOpcode() == TargetInstrInfo::PHI; ++I) {
-        MachineInstr *MI = *I;
+      for (MachineBasicBlock::iterator MI = Succ->begin(), ME = Succ->end();
+	   MI != ME && MI->getOpcode() == TargetInstrInfo::PHI; ++MI) {
 	for (unsigned i = 1; ; i += 2)
 	  if (MI->getOperand(i+1).getMachineBasicBlock() == MBB) {
 	    MachineOperand &MO = MI->getOperand(i);
diff --git a/lib/CodeGen/MachineCodeForInstruction.cpp b/lib/CodeGen/MachineCodeForInstruction.cpp
index 50a54099c5..9d63df5bf8 100644
--- a/lib/CodeGen/MachineCodeForInstruction.cpp
+++ b/lib/CodeGen/MachineCodeForInstruction.cpp
@@ -60,9 +60,8 @@ MachineCodeForInstruction::~MachineCodeForInstruction() {
   for (unsigned i=0, N=tempVec.size(); i < N; i++)
     delete tempVec[i];
   
-  // Free the MachineInstr objects allocated, if any.
-  for (unsigned i=0, N = size(); i < N; i++)
-    delete (*this)[i];
+  // do not free the MachineInstr objects allocated. they are managed
+  // by the ilist in MachineBasicBlock
 
   // Free the CallArgsDescriptor if it exists.
   delete callArgsDesc;
diff --git a/lib/CodeGen/MachineFunction.cpp b/lib/CodeGen/MachineFunction.cpp
index 6c15ad5c4d..4de55f4596 100644
--- a/lib/CodeGen/MachineFunction.cpp
+++ b/lib/CodeGen/MachineFunction.cpp
@@ -62,34 +62,6 @@ FunctionPass *llvm::createMachineFunctionPrinterPass(std::ostream *OS,
   return new Printer(OS, Banner);
 }
 
-namespace {
-  struct Deleter : public MachineFunctionPass {
-    const char *getPassName() const { return "Machine Code Deleter"; }
-
-    bool runOnMachineFunction(MachineFunction &MF) {
-      // Delete all of the MachineInstrs out of the function.  When the sparc
-      // backend gets fixed, this can be dramatically simpler, but actually
-      // putting this stuff into the MachineBasicBlock destructor!
-      for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); BB != E;
-           ++BB)
-        while (!BB->empty())
-          delete BB->pop_back();
-
-      // Delete the annotation from the function now.
-      MachineFunction::destruct(MF.getFunction());
-      return true;
-    }
-  };
-}
-
-/// MachineCodeDeletion Pass - This pass deletes all of the machine code for
-/// the current function, which should happen after the function has been
-/// emitted to a .s file or to memory.
-FunctionPass *llvm::createMachineCodeDeleter() {
-  return new Deleter();
-}
-
-
 //===---------------------------------------------------------------------===//
 // MachineFunction implementation
 //===---------------------------------------------------------------------===//
@@ -127,7 +99,7 @@ void MachineFunction::print(std::ostream &OS) const {
     OS << "\n" << LBB->getName() << " (" << (const void*)LBB << "):\n";
     for (MachineBasicBlock::const_iterator I = BB->begin(); I != BB->end();++I){
       OS << "\t";
-      (*I)->print(OS, Target);
+      I->print(OS, Target);
     }
   }
   OS << "\nEnd function \"" << Fn->getName() << "\"\n\n";
diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp
index afb87e501f..03a1da9f13 100644
--- a/lib/CodeGen/PHIElimination.cpp
+++ b/