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.

llvm-svn: 11340

10 files changed, 55 insertions, 75 deletions

diff --git a/llvm/lib/Target/Sparc/EmitAssembly.cpp b/llvm/lib/Target/Sparc/EmitAssembly.cpp
index af86e05a905..20fbfa3619c 100644
--- a/llvm/lib/Target/Sparc/EmitAssembly.cpp
+++ b/llvm/lib/Target/Sparc/EmitAssembly.cpp
@@ -721,7 +721,7 @@ void SparcAsmPrinter::emitBasicBlock(const MachineBasicBlock &MBB) {
   // Loop over all of the instructions in the basic block...
   for (MachineBasicBlock::const_iterator MII = MBB.begin(), MIE = MBB.end();
        MII != MIE; ++MII)
-    emitMachineInst(*MII);
+    emitMachineInst(MII);
   toAsm << "\n";  // Separate BB's with newlines
 }
 
diff --git a/llvm/lib/Target/Sparc/InstrSelection/InstrSelection.cpp b/llvm/lib/Target/Sparc/InstrSelection/InstrSelection.cpp
index 5d9d0a355b1..4ddc4edfbb6 100644
--- a/llvm/lib/Target/Sparc/InstrSelection/InstrSelection.cpp
+++ b/llvm/lib/Target/Sparc/InstrSelection/InstrSelection.cpp
@@ -283,10 +283,7 @@ InstructionSelection::InsertPhiElimInstructions(BasicBlock *BB,
       break;
     }
 
-  // find the position of first machine instruction generated by the
-  // terminator of this BB
-  MachineBasicBlock::iterator MCIt =
-    std::find(MBB->begin(), MBB->end(), FirstMIOfTerm);
+  MachineBasicBlock::iterator MCIt = FirstMIOfTerm;
 
   assert(MCIt != MBB->end() && "Start inst of terminator not found");
   
diff --git a/llvm/lib/Target/Sparc/LiveVar/BBLiveVar.cpp b/llvm/lib/Target/Sparc/LiveVar/BBLiveVar.cpp
index d8878ad4209..e3515e8bdbe 100644
--- a/llvm/lib/Target/Sparc/LiveVar/BBLiveVar.cpp
+++ b/llvm/lib/Target/Sparc/LiveVar/BBLiveVar.cpp
@@ -41,7 +41,7 @@ void BBLiveVar::calcDefUseSets() {
   // iterate over all the machine instructions in BB
   for (MachineBasicBlock::const_reverse_iterator MII = MBB.rbegin(),
          MIE = MBB.rend(); MII != MIE; ++MII) {
-    const MachineInstr *MI = *MII;
+    const MachineInstr *MI = &*MII;
     
     if (DEBUG_LV >= LV_DEBUG_Verbose) {
       std::cerr << " *Iterating over machine instr ";
diff --git a/llvm/lib/Target/Sparc/LiveVar/FunctionLiveVarInfo.cpp b/llvm/lib/Target/Sparc/LiveVar/FunctionLiveVarInfo.cpp
index fd23a2353e3..e2822c300e8 100644
--- a/llvm/lib/Target/Sparc/LiveVar/FunctionLiveVarInfo.cpp
+++ b/llvm/lib/Target/Sparc/LiveVar/FunctionLiveVarInfo.cpp
@@ -283,7 +283,7 @@ void FunctionLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *BB) {
   for (MachineBasicBlock::const_reverse_iterator MII = MIVec.rbegin(),
          MIE = MIVec.rend(); MII != MIE; ++MII) {  
     // MI is cur machine inst
-    const MachineInstr *MI = *MII;  
+    const MachineInstr *MI = &*MII;  
 
     MInst2LVSetAI[MI] = SetAI;                 // record in After Inst map
 
@@ -299,7 +299,7 @@ void FunctionLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *BB) {
       MachineBasicBlock::const_iterator fwdMII = MII.base(); // ptr to *next* MI
       for (unsigned i = 0; i < DS; ++i, ++fwdMII) {
         assert(fwdMII != MIVec.end() && "Missing instruction in delay slot?");
-        MachineInstr* DelaySlotMI = *fwdMII;
+        const MachineInstr* DelaySlotMI = fwdMII;
         if (! TM.getInstrInfo().isNop(DelaySlotMI->getOpcode())) {
           set_union(*MInst2LVSetBI[DelaySlotMI], *NewSet);
           if (i+1 == DS)
diff --git a/llvm/lib/Target/Sparc/MappingInfo.cpp b/llvm/lib/Target/Sparc/MappingInfo.cpp
index 2afde6bdf59..4648c54e48e 100644
--- a/llvm/lib/Target/Sparc/MappingInfo.cpp
+++ b/llvm/lib/Target/Sparc/MappingInfo.cpp
@@ -153,7 +153,7 @@ void MappingInfoAsmPrinter::create_BB_to_MInumber_Key(Function &FI,
   for (MachineFunction::iterator BI = MF.begin(), BE = MF.end();
        BI != BE; ++BI) {
     MachineBasicBlock &miBB = *BI;
-    key[miBB[0]] = i;
+    key[&miBB.front()] = i;
     i = i+(miBB.size());
   }
 }
@@ -174,7 +174,7 @@ void MappingInfoAsmPrinter::create_MI_to_number_Key(Function &FI,
     unsigned j = 0;
     for(MachineBasicBlock::iterator miI = miBB.begin(), miE = miBB.end();
         miI != miE; ++miI, ++j) {
-      key[*miI] = j;
+      key[miI] = j;
     }
   }
 }
@@ -195,7 +195,7 @@ void MappingInfoAsmPrinter::buildBBMIMap(Function &FI, MappingInfo &Map) {
        BI != BE; ++BI, ++bb) {
     MachineBasicBlock &miBB = *BI;
     writeNumber(bb);
-    writeNumber(BBkey[miBB[0]]);
+    writeNumber(BBkey[&miBB.front()]);
     writeNumber(miBB.size());
   }
 }
diff --git a/llvm/lib/Target/Sparc/PeepholeOpts.cpp b/llvm/lib/Target/Sparc/PeepholeOpts.cpp
index 60c7bcbd0c4..a69171c604e 100644
--- a/llvm/lib/Target/Sparc/PeepholeOpts.cpp
+++ b/llvm/lib/Target/Sparc/PeepholeOpts.cpp
@@ -31,14 +31,14 @@ DeleteInstruction(MachineBasicBlock& mvec,
   // Check if this instruction is in a delay slot of its predecessor.
   if (BBI != mvec.begin()) {
       const TargetInstrInfo& mii = target.getInstrInfo();
-      MachineInstr* predMI = *(BBI-1);
+      MachineBasicBlock::iterator predMI = BBI; --predMI;
       if (unsigned ndelay = mii.getNumDelaySlots(predMI->getOpcode())) {
         // This instruction is in a delay slot of its predecessor, so
         // replace it with a nop. By replacing in place, we save having
         // to update the I-I maps.
         // 
         assert(ndelay == 1 && "Not yet handling multiple-delay-slot targets");
-        (*BBI)->replace(mii.getNOPOpCode(), 0);
+        BBI->replace(mii.getNOPOpCode(), 0);
         return;
       }
   }
@@ -99,7 +99,7 @@ inline bool
 RemoveUselessCopies(MachineBasicBlock& mvec,
                     MachineBasicBlock::iterator& BBI,
                     const TargetMachine& target) {
-  if (IsUselessCopy(target, *BBI)) {
+  if (IsUselessCopy(target, BBI)) {
     DeleteInstruction(mvec, BBI, target);
     return true;
   }
@@ -148,16 +148,8 @@ bool PeepholeOpts::runOnBasicBlock(BasicBlock &BB) {
   assert(MBB && "MachineBasicBlock object not found for specified block!");
   MachineBasicBlock &mvec = *MBB;
 
-  // Iterate over all machine instructions in the BB
-  // Use a reverse iterator to allow deletion of MI or any instruction after it.
-  // Insertions or deletions *before* MI are not safe.
-  // 
-  for (MachineBasicBlock::reverse_iterator RI=mvec.rbegin(),
-         RE=mvec.rend(); RI != RE; ) {
-    MachineBasicBlock::iterator BBI = RI.base()-1; // save before incr
-    ++RI;             // pre-increment to delete MI or after it
-    visit(mvec, BBI);
-  }
+  for (MachineBasicBlock::iterator I = mvec.begin(), E = mvec.end(); I != E; )
+    visit(mvec, I++);
 
   return true;
 }
diff --git a/llvm/lib/Target/Sparc/PrologEpilogCodeInserter.cpp b/llvm/lib/Target/Sparc/PrologEpilogCodeInserter.cpp
index 4398f6bc844..55db2334195 100644
--- a/llvm/lib/Target/Sparc/PrologEpilogCodeInserter.cpp
+++ b/llvm/lib/Target/Sparc/PrologEpilogCodeInserter.cpp
@@ -157,12 +157,12 @@ void InsertPrologEpilogCode::InsertEpilogCode(MachineFunction &MF)
       unsigned numNOPs = 0;
       while (termMvec.back()->getOpcode() == V9::NOP)
       {
-        assert( termMvec.back() == MBB.back());
-        delete MBB.pop_back();
+        assert( termMvec.back() == &MBB.back());
         termMvec.pop_back();
+        MBB.erase(&MBB.back());
         ++numNOPs;
       }
-      assert(termMvec.back() == MBB.back());
+      assert(termMvec.back() == &MBB.back());
         
       // Check that we found the right number of NOPs and have the right
       // number of instructions to replace them.
diff --git a/llvm/lib/Target/Sparc/RegAlloc/LiveRangeInfo.cpp b/llvm/lib/Target/Sparc/RegAlloc/LiveRangeInfo.cpp
index 2c0196d8fa6..f28ca86c708 100644
--- a/llvm/lib/Target/Sparc/RegAlloc/LiveRangeInfo.cpp
+++ b/llvm/lib/Target/Sparc/RegAlloc/LiveRangeInfo.cpp
@@ -171,7 +171,7 @@ void LiveRangeInfo::constructLiveRanges() {
     // iterate over all the machine instructions in BB
     for(MachineBasicBlock::iterator MInstIterator = MBB.begin();
         MInstIterator != MBB.end(); ++MInstIterator) {  
-      MachineInstr *MInst = *MInstIterator; 
+      MachineInstr *MInst = MInstIterator; 
 
       // If the machine instruction is a  call/return instruction, add it to
       // CallRetInstrList for processing its args, ret value, and ret addr.
@@ -330,7 +330,7 @@ void LiveRangeInfo::coalesceLRs()
 
     // iterate over all the machine instructions in BB
     for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){
-      const MachineInstr *MI = *MII;
+      const MachineInstr *MI = MII;
 
       if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
 	std::cerr << " *Iterating over machine instr ";
diff --git a/llvm/lib/Target/Sparc/RegAlloc/PhyRegAlloc.cpp b/llvm/lib/Target/Sparc/RegAlloc/PhyRegAlloc.cpp
index e45f13b258a..0cb1776f8aa 100644
--- a/llvm/lib/Target/Sparc/RegAlloc/PhyRegAlloc.cpp
+++ b/llvm/lib/Target/Sparc/RegAlloc/PhyRegAlloc.cpp
@@ -233,7 +233,7 @@ void PhyRegAlloc::buildInterferenceGraphs() {
 
     // iterate over all the machine instructions in BB
     for ( ; MII != MBB.end(); ++MII) {
-      const MachineInstr *MInst = *MII;
+      const MachineInstr *MInst = MII;
 
       // get the LV set after the instruction
       const ValueSet &LVSetAI = LVI->getLiveVarSetAfterMInst(MInst, BB);
@@ -355,25 +355,13 @@ inline void InsertAfter(MachineInstr* newMI, MachineBasicBlock& MBB,
   MII = MBB.insert(MII, newMI);
 }
 
-// used by: updateMachineCode (1 time)
-inline void DeleteInstruction(MachineBasicBlock& MBB,
-                              MachineBasicBlock::iterator& MII) {
-  MII = MBB.erase(MII);
-}
-
-// used by: updateMachineCode (1 time)
-inline void SubstituteInPlace(MachineInstr* newMI, MachineBasicBlock& MBB,
-                              MachineBasicBlock::iterator MII) {
-  *MII = newMI;
-}
-
 // used by: updateMachineCode (2 times)
 inline void PrependInstructions(std::vector<MachineInstr *> &IBef,
                                 MachineBasicBlock& MBB,
                                 MachineBasicBlock::iterator& MII,
                                 const std::string& msg) {
   if (!IBef.empty()) {
-      MachineInstr* OrigMI = *MII;
+      MachineInstr* OrigMI = MII;
       std::vector<MachineInstr *>::iterator AdIt; 
       for (AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt) {
           if (DEBUG_RA) {
@@ -391,7 +379,7 @@ inline void AppendInstructions(std::vector<MachineInstr *> &IAft,
                                MachineBasicBlock::iterator& MII,
                                const std::string& msg) {
   if (!IAft.empty()) {
-      MachineInstr* OrigMI = *MII;
+      MachineInstr* OrigMI = MII;
       std::vector<MachineInstr *>::iterator AdIt; 
       for ( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) {
           if (DEBUG_RA) {
@@ -442,14 +430,14 @@ bool PhyRegAlloc::markAllocatedRegs(MachineInstr* MInst)
 ///
 void PhyRegAlloc::updateInstruction(MachineBasicBlock::iterator& MII,
                                     MachineBasicBlock &MBB) {
-  MachineInstr* MInst = *MII;
+  MachineInstr* MInst = MII;
   unsigned Opcode = MInst->getOpcode();
 
   // Reset tmp stack positions so they can be reused for each machine instr.
   MF->getInfo()->popAllTempValues();  
 
   // Mark the operands for which regs have been allocated.
-  bool instrNeedsSpills = markAllocatedRegs(*MII);
+  bool instrNeedsSpills = markAllocatedRegs(MII);
 
 #ifndef NDEBUG
   // Mark that the operands have been updated.  Later,
@@ -506,7 +494,7 @@ void PhyRegAlloc::updateMachineCode()
     // their assigned registers or insert spill code, as appropriate. 
     // Also, fix operands of call/return instructions.
     for (MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII)
-      if (! TM.getInstrInfo().isDummyPhiInstr((*MII)->getOpcode()))
+      if (! TM.getInstrInfo().isDummyPhiInstr(MII->getOpcode()))
         updateInstruction(MII, MBB);
 
     // Now, move code out of delay slots of branches and returns if needed.
@@ -523,56 +511,58 @@ void PhyRegAlloc::updateMachineCode()
     // 
     // If the annul bit of the branch is set, neither of these is legal!
     // If so, we need to handle spill differently but annulling is not yet used.
-    for (MachineBasicBlock::iterator MII = MBB.begin();
-         MII != MBB.end(); ++MII)
+    for (MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII)
       if (unsigned delaySlots =
-          TM.getInstrInfo().getNumDelaySlots((*MII)->getOpcode())) { 
-          MachineInstr *MInst = *MII, *DelaySlotMI = *(MII+1);
+          TM.getInstrInfo().getNumDelaySlots(MII->getOpcode())) { 
+          MachineBasicBlock::iterator DelaySlotMI = MII; ++DelaySlotMI;
+          assert(DelaySlotMI != MBB.end() && "no instruction for delay slot");
           
           // Check the 2 conditions above:
           // (1) Does a branch need instructions added after it?
           // (2) O/w does delay slot instr. need instrns before or after?
-          bool isBranch = (TM.getInstrInfo().isBranch(MInst->getOpcode()) ||
-                           TM.getInstrInfo().isReturn(MInst->getOpcode()));
+          bool isBranch = (TM.getInstrInfo().isBranch(MII->getOpcode()) ||
+                           TM.getInstrInfo().isReturn(MII->getOpcode()));
           bool cond1 = (isBranch &&
-                        AddedInstrMap.count(MInst) &&
-                        AddedInstrMap[MInst].InstrnsAfter.size() > 0);
+                        AddedInstrMap.count(MII) &&
+                        AddedInstrMap[MII].InstrnsAfter.size() > 0);
           bool cond2 = (AddedInstrMap.count(DelaySlotMI) &&
                         (AddedInstrMap[DelaySlotMI].InstrnsBefore.size() > 0 ||
                          AddedInstrMap[DelaySlotMI].InstrnsAfter.size()  > 0));
 
           if (cond1 || cond2) {
-              assert((MInst->getOpCodeFlags() & AnnulFlag) == 0 &&
+              assert((MII->getOpCodeFlags() & AnnulFlag) == 0 &&
                      "FIXME: Moving an annulled delay slot instruction!"); 
               assert(delaySlots==1 &&
                      "InsertBefore does not yet handle >1 delay slots!");
-              InsertBefore(DelaySlotMI, MBB, MII); // MII pts back to branch
-
-              // In case (1), delete it and don't replace with anything!
-              // Otherwise (i.e., case (2) only) replace it with a NOP.
-              if (cond1) {
-                DeleteInstruction(MBB, ++MII); // MII now points to next inst.
-                --MII;                         // reset MII for ++MII of loop
-              }
-              else
-                SubstituteInPlace(BuildMI(TM.getInstrInfo().getNOPOpCode(),1),
-                                  MBB, MII+1);        // replace with NOP
 
               if (DEBUG_RA) {
                 std::cerr << "\nRegAlloc: Moved instr. with added code: "
                      << *DelaySlotMI
-                     << "           out of delay slots of instr: " << *MInst;
+                     << "           out of delay slots of instr: " << *MII;
+              }
+
+              // move instruction before branch
+              MBB.insert(MII, MBB.remove(DelaySlotMI));
+
+              // On cond1 we are done (we already moved the
+              // instruction out of the delay slot). On cond2 we need
+              // to insert a nop in place of the moved instruction
+              if (cond2) {
+                MBB.insert(MII, BuildMI(TM.getInstrInfo().getNOPOpCode(),1));
               }
             }
-          else
+          else {
             // For non-branch instr with delay slots (probably a call), move
             // InstrAfter to the instr. in the last delay slot.
-            move2DelayedInstr(*MII, *(MII+delaySlots));
-        }
+            MachineBasicBlock::iterator tmp = MII;
+            std::advance(tmp, delaySlots);
+            move2DelayedInstr(MII, tmp);
+          }
+      }
 
     // Finally iterate over all instructions in BB and insert before/after
     for (MachineBasicBlock::iterator MII=MBB.begin(); MII != MBB.end(); ++MII) {
-      MachineInstr *MInst = *MII; 
+      MachineInstr *MInst = MII; 
 
       // do not process Phis
       if (TM.getInstrInfo().isDummyPhiInstr(MInst->getOpcode()))
@@ -635,7 +625,7 @@ void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
                                        MachineBasicBlock::iterator& MII,
                                        MachineBasicBlock &MBB,
 				       const unsigned OpNum) {
-  MachineInstr *MInst = *MII;
+  MachineInstr *MInst = MII;
   const BasicBlock *BB = MBB.getBasicBlock();
 
   assert((! TM.getInstrInfo().isCall(MInst->getOpcode()) || OpNum == 0) &&
@@ -658,7 +648,8 @@ void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
   // include all live variables before that branch or return -- we don't want to
   // trample those!  Verify that the set is included in the LV set before MInst.
   if (MII != MBB.begin()) {
-    MachineInstr *PredMI = *(MII-1);
+    MachineBasicBlock::iterator PredMI = MII;
+    --PredMI;
     if (unsigned DS = TM.getInstrInfo().getNumDelaySlots(PredMI->getOpcode()))
       assert(set_difference(LVI->getLiveVarSetBeforeMInst(PredMI), LVSetBef)
              .empty() && "Live-var set before branch should be included in "
diff --git a/llvm/lib/Target/Sparc/SparcV9CodeEmitter.cpp b/llvm/lib/Target/Sparc/SparcV9CodeEmitter.cpp
index 495f79171eb..753f5d30f3d 100644
--- a/llvm/lib/Target/Sparc/SparcV9CodeEmitter.cpp
+++ b/llvm/lib/Target/Sparc/SparcV9CodeEmitter.cpp
@@ -778,7 +778,7 @@ void SparcV9CodeEmitter::emitBasicBlock(MachineBasicBlock &MBB) {
   currBB = MBB.getBasicBlock();
   BBLocations[currBB] = MCE.getCurrentPCValue();
   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ++I){
-    unsigned binCode = getBinaryCodeForInstr(**I);
+    unsigned binCode = getBinaryCodeForInstr(*I);
     if (binCode == (1 << 30)) {
       // this is an invalid call: the addr is out of bounds. that means a code
       // sequence has already been emitted, and this is a no-op