X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLocal.cpp;h=bea603ce49667b7a8c6f4053816b24d9ebbb4c0d;hb=21ab22e47592d8a4046cfdac844d76b2cb76d711;hp=188b3b341708753a8480abd0c6a36c8e7c6b6785;hpb=d368c6163a54190c852838b370a62a86caafde3a;p=oota-llvm.git

diff --git a/lib/CodeGen/RegAllocLocal.cpp b/lib/CodeGen/RegAllocLocal.cpp
index 188b3b34170..bea603ce496 100644
--- a/lib/CodeGen/RegAllocLocal.cpp
+++ b/lib/CodeGen/RegAllocLocal.cpp
@@ -23,14 +23,15 @@
 #include "llvm/Target/TargetMachine.h"
 #include "Support/CommandLine.h"
 #include "Support/Debug.h"
+#include "Support/DenseMap.h"
 #include "Support/Statistic.h"
-#include <iostream>
 using namespace llvm;
 
 namespace {
   Statistic<> NumStores("ra-local", "Number of stores added");
   Statistic<> NumLoads ("ra-local", "Number of loads added");
-  Statistic<> NumFused ("ra-local", "Number of reloads fused into instructions");
+  Statistic<> NumFolded("ra-local", "Number of loads/stores folded into "
+                        "instructions");
   class RA : public MachineFunctionPass {
     const TargetMachine *TM;
     MachineFunction *MF;
@@ -42,19 +43,11 @@ namespace {
     std::map<unsigned, int> StackSlotForVirtReg;
 
     // Virt2PhysRegMap - This map contains entries for each virtual register
-    // that is currently available in a physical register.  This is "logically"
-    // a map from virtual register numbers to physical register numbers.
-    // Instead of using a map, however, which is slow, we use a vector.  The
-    // index is the VREG number - FirstVirtualRegister.  If the entry is zero,
-    // then it is logically "not in the map".
-    //
-    std::vector<unsigned> Virt2PhysRegMap;
+    // that is currently available in a physical register.
+    DenseMap<unsigned, VirtReg2IndexFunctor> Virt2PhysRegMap;
 
     unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) {
-      assert(MRegisterInfo::isVirtualRegister(VirtReg) &&"Illegal VREG #");
-      assert(VirtReg-MRegisterInfo::FirstVirtualRegister <Virt2PhysRegMap.size()
-             && "VirtReg not in map!");
-      return Virt2PhysRegMap[VirtReg-MRegisterInfo::FirstVirtualRegister];
+      return Virt2PhysRegMap[VirtReg];
     }
 
     // PhysRegsUsed - This array is effectively a map, containing entries for
@@ -99,8 +92,8 @@ namespace {
     }
 
     void MarkPhysRegRecentlyUsed(unsigned Reg) {
-      assert(!PhysRegsUseOrder.empty() && "No registers used!");
-      if (PhysRegsUseOrder.back() == Reg) return;  // Already most recently used
+      if(PhysRegsUseOrder.empty() ||
+         PhysRegsUseOrder.back() == Reg) return;  // Already most recently used
 
       for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i)
         if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) {
@@ -159,7 +152,7 @@ namespace {
     /// the virtual register slot specified by VirtReg.  It then updates the RA
     /// data structures to indicate the fact that PhysReg is now available.
     ///
-    void spillVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
+    void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
                       unsigned VirtReg, unsigned PhysReg);
 
     /// spillPhysReg - This method spills the specified physical register into
@@ -257,7 +250,7 @@ void RA::removePhysReg(unsigned PhysReg) {
 /// virtual register slot specified by VirtReg.  It then updates the RA data
 /// structures to indicate the fact that PhysReg is now available.
 ///
-void RA::spillVirtReg(MachineBasicBlock &MBB, MachineInstr *I,
+void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
                       unsigned VirtReg, unsigned PhysReg) {
   assert(VirtReg && "Spilling a physical register is illegal!"
          " Must not have appropriate kill for the register or use exists beyond"
@@ -493,13 +486,12 @@ MachineInstr *RA::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
     assignVirtToPhysReg(VirtReg, PhysReg);
   } else {         // No registers available.
     // If we can fold this spill into this instruction, do so now.
-    MachineBasicBlock::iterator MII = MI;
-    if (RegInfo->foldMemoryOperand(MII, OpNum, FrameIndex)) {
-      ++NumFused;
+    if (MachineInstr* FMI = RegInfo->foldMemoryOperand(MI, OpNum, FrameIndex)){
+      ++NumFolded;
       // Since we changed the address of MI, make sure to update live variables
       // to know that the new instruction has the properties of the old one.
-      LV->instructionChanged(MI, MII);
-      return MII;
+      LV->instructionChanged(MI, FMI);
+      return MBB.insert(MBB.erase(MI), FMI);
     }
 
     // It looks like we can't fold this virtual register load into this
@@ -527,7 +519,7 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
   // loop over each instruction
   MachineBasicBlock::iterator MI = MBB.begin();
   for (; MI != MBB.end(); ++MI) {
-    const TargetInstrDescriptor &TID = TM->getInstrInfo().get(MI->getOpcode());
+    const TargetInstrDescriptor &TID = TM->getInstrInfo()->get(MI->getOpcode());
     DEBUG(std::cerr << "\nStarting RegAlloc of: " << *MI;
           std::cerr << "  Regs have values: ";
           for (unsigned i = 0; i != RegInfo->getNumRegs(); ++i)
@@ -548,11 +540,13 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
     // physical register is referenced by the instruction, that it is guaranteed
     // to be live-in, or the input is badly hosed.
     //
-    for (unsigned i = 0; i != MI->getNumOperands(); ++i)
-      if (MI->getOperand(i).isUse() &&
-          !MI->getOperand(i).isDef() && MI->getOperand(i).isRegister() &&
-          MRegisterInfo::isVirtualRegister(MI->getOperand(i).getReg()))
+    for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
+      MachineOperand& MO = MI->getOperand(i);
+      // here we are looking for only used operands (never def&use)
+      if (!MO.isDef() && MO.isRegister() && MO.getReg() &&
+          MRegisterInfo::isVirtualRegister(MO.getReg()))
         MI = reloadVirtReg(MBB, MI, i);
+    }
 
     // If this instruction is the last user of anything in registers, kill the
     // value, freeing the register being used, so it doesn't need to be
@@ -579,10 +573,11 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
 
     // Loop over all of the operands of the instruction, spilling registers that
     // are defined, and marking explicit destinations in the PhysRegsUsed map.
-    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
-      if (MI->getOperand(i).isDef() && MI->getOperand(i).isRegister() &&
-          MRegisterInfo::isPhysicalRegister(MI->getOperand(i).getReg())) {
-        unsigned Reg = MI->getOperand(i).getReg();
+    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+      MachineOperand& MO = MI->getOperand(i);
+      if (MO.isDef() && MO.isRegister() && MO.getReg() &&
+          MRegisterInfo::isPhysicalRegister(MO.getReg())) {
+        unsigned Reg = MO.getReg();
         spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in the reg
         PhysRegsUsed[Reg] = 0;            // It is free and reserved now
         PhysRegsUseOrder.push_back(Reg);
@@ -592,6 +587,7 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
           PhysRegsUsed[*AliasSet] = 0;  // It is free and reserved now
         }
       }
+    }
 
     // Loop over the implicit defs, spilling them as well.
     for (const unsigned *ImplicitDefs = TID.ImplicitDefs;
@@ -612,10 +608,11 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
     // implicit defs and assign them to a register, spilling incoming values if
     // we need to scavenge a register.
     //
-    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
-      if (MI->getOperand(i).isDef() && MI->getOperand(i).isRegister() &&
-          MRegisterInfo::isVirtualRegister(MI->getOperand(i).getReg())) {
-        unsigned DestVirtReg = MI->getOperand(i).getReg();
+    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+      MachineOperand& MO = MI->getOperand(i);
+      if (MO.isDef() && MO.isRegister() && MO.getReg() &&
+          MRegisterInfo::isVirtualRegister(MO.getReg())) {
+        unsigned DestVirtReg = MO.getReg();
         unsigned DestPhysReg;
 
         // If DestVirtReg already has a value, use it.
@@ -624,6 +621,7 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
         markVirtRegModified(DestVirtReg);
         MI->SetMachineOperandReg(i, DestPhysReg);  // Assign the output register
       }
+    }
 
     // If this instruction defines any registers that are immediately dead,
     // kill them now.
@@ -648,11 +646,7 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
     }
   }
 
-  // Rewind the iterator to point to the first flow control instruction...
-  const TargetInstrInfo &TII = TM->getInstrInfo();
-  MI = MBB.end();
-  while (MI != MBB.begin() && TII.isTerminatorInstr((--MI)->getOpcode()));
-  ++MI;
+  MI = MBB.getFirstTerminator();
 
   // Spill all physical registers holding virtual registers now.
   for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i)
@@ -664,7 +658,8 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
 
 #ifndef NDEBUG
   bool AllOk = true;
-  for (unsigned i = 0, e = Virt2PhysRegMap.size(); i != e; ++i)
+  for (unsigned i = MRegisterInfo::FirstVirtualRegister,
+           e = MF->getSSARegMap()->getLastVirtReg(); i <= e; ++i)
     if (unsigned PR = Virt2PhysRegMap[i]) {
       std::cerr << "Register still mapped: " << i << " -> " << PR << "\n";
       AllOk = false;
@@ -692,7 +687,7 @@ bool RA::runOnMachineFunction(MachineFunction &Fn) {
 
   // initialize the virtual->physical register map to have a 'null'
   // mapping for all virtual registers
-  Virt2PhysRegMap.assign(MF->getSSARegMap()->getNumVirtualRegs(), 0);
+  Virt2PhysRegMap.grow(MF->getSSARegMap()->getLastVirtReg());
 
   // Loop over all of the basic blocks, eliminating virtual register references
   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();