X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocFast.cpp;h=803e248065f6409c6c39c3fe61e308cace069f27;hb=343735288798bbd1cd2ed2750fa6cd323f12c26c;hp=70c1c1e3e68db1f6eacb328322ee828b32673f4c;hpb=548643c573d53950e28e9e810cd0454ba9a21af0;p=oota-llvm.git

diff --git a/lib/CodeGen/RegAllocFast.cpp b/lib/CodeGen/RegAllocFast.cpp
index 70c1c1e3e68..803e248065f 100644
--- a/lib/CodeGen/RegAllocFast.cpp
+++ b/lib/CodeGen/RegAllocFast.cpp
@@ -35,9 +35,6 @@
 #include <algorithm>
 using namespace llvm;
 
-static cl::opt<bool> VerifyFastRegalloc("verify-fast-regalloc", cl::Hidden,
-    cl::desc("Verify machine code before fast regalloc"));
-
 STATISTIC(NumStores, "Number of stores added");
 STATISTIC(NumLoads , "Number of loads added");
 STATISTIC(NumCopies, "Number of copies coalesced");
@@ -157,7 +154,7 @@ namespace {
     LiveRegMap::iterator reloadVirtReg(MachineInstr *MI, unsigned OpNum,
                                        unsigned VirtReg, unsigned Hint);
     void spillAll(MachineInstr *MI);
-    bool setPhysReg(MachineOperand &MO, unsigned PhysReg);
+    bool setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg);
   };
   char RAFast::ID = 0;
 }
@@ -203,10 +200,17 @@ bool RAFast::isLastUseOfLocalReg(MachineOperand &MO) {
 void RAFast::addKillFlag(const LiveReg &LR) {
   if (!LR.LastUse) return;
   MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum);
-  if (MO.isDef())
-    MO.setIsDead();
-  else if (!LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum))
-    MO.setIsKill();
+  if (MO.getReg() == LR.PhysReg) {
+    if (MO.isDef())
+      MO.setIsDead();
+    else if (!LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum))
+      MO.setIsKill();
+  } else {
+    if (MO.isDef())
+      LR.LastUse->addRegisterDead(LR.PhysReg, TRI, true);
+    else
+      LR.LastUse->addRegisterKilled(LR.PhysReg, TRI, true);
+  }
 }
 
 /// killVirtReg - Mark virtreg as no longer available.
@@ -267,9 +271,12 @@ void RAFast::spillVirtReg(MachineBasicBlock::iterator MI,
 
 /// spillAll - Spill all dirty virtregs without killing them.
 void RAFast::spillAll(MachineInstr *MI) {
+  if (LiveVirtRegs.empty()) return;
   isBulkSpilling = true;
-  for (LiveRegMap::iterator i = LiveVirtRegs.begin(),
-       e = LiveVirtRegs.end(); i != e; ++i)
+  // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
+  // of spilling here is deterministic, if arbitrary.
+  for (LiveRegMap::iterator i = LiveVirtRegs.begin(), e = LiveVirtRegs.end();
+       i != e; ++i)
     spillVirtReg(MI, i);
   LiveVirtRegs.clear();
   isBulkSpilling = false;
@@ -381,6 +388,8 @@ void RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg,
 // can be allocated directly.
 // Returns spillImpossible when PhysReg or an alias can't be spilled.
 unsigned RAFast::calcSpillCost(unsigned PhysReg) const {
+  if (UsedInInstr.test(PhysReg))
+    return spillImpossible;
   switch (unsigned VirtReg = PhysRegState[PhysReg]) {
   case regDisabled:
     break;
@@ -396,6 +405,8 @@ unsigned RAFast::calcSpillCost(unsigned PhysReg) const {
   unsigned Cost = 0;
   for (const unsigned *AS = TRI->getAliasSet(PhysReg);
        unsigned Alias = *AS; ++AS) {
+    if (UsedInInstr.test(Alias))
+      return spillImpossible;
     switch (unsigned VirtReg = PhysRegState[Alias]) {
     case regDisabled:
       break;
@@ -436,14 +447,11 @@ void RAFast::allocVirtReg(MachineInstr *MI, LiveRegEntry &LRE, unsigned Hint) {
 
   // Ignore invalid hints.
   if (Hint && (!TargetRegisterInfo::isPhysicalRegister(Hint) ||
-               !RC->contains(Hint) || UsedInInstr.test(Hint) ||
-               !Allocatable.test(Hint)))
+               !RC->contains(Hint) || !Allocatable.test(Hint)))
     Hint = 0;
 
   // Take hint when possible.
   if (Hint) {
-    assert(RC->contains(Hint) && !UsedInInstr.test(Hint) &&
-           Allocatable.test(Hint) && "Invalid hint should have been cleared");
     switch(calcSpillCost(Hint)) {
     default:
       definePhysReg(MI, Hint, regFree);
@@ -471,17 +479,15 @@ void RAFast::allocVirtReg(MachineInstr *MI, LiveRegEntry &LRE, unsigned Hint) {
   unsigned BestReg = 0, BestCost = spillImpossible;
   for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) {
     unsigned Cost = calcSpillCost(*I);
-    if (Cost < BestCost) {
-      BestReg = *I;
-      BestCost = Cost;
-      if (Cost == 0) break;
-    }
+    // Cost is 0 when all aliases are already disabled.
+    if (Cost == 0)
+      return assignVirtToPhysReg(LRE, *I);
+    if (Cost < BestCost)
+      BestReg = *I, BestCost = Cost;
   }
 
   if (BestReg) {
-    // BestCost is 0 when all aliases are already disabled.
-    if (BestCost)
-      definePhysReg(MI, BestReg, regFree);
+    definePhysReg(MI, BestReg, regFree);
     return assignVirtToPhysReg(LRE, BestReg);
   }
 
@@ -518,8 +524,12 @@ RAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum,
         Hint = DstReg;
     }
     allocVirtReg(MI, *LRI, Hint);
-  } else
-    addKillFlag(LR); // Kill before redefine.
+  } else if (LR.LastUse) {
+    // Redefining a live register - kill at the last use, unless it is this
+    // instruction defining VirtReg multiple times.
+    if (LR.LastUse != MI || LR.LastUse->getOperand(LR.LastOpNum).isUse())
+      addKillFlag(LR);
+  }
   assert(LR.PhysReg && "Register not assigned");
   LR.LastUse = MI;
   LR.LastOpNum = OpNum;
@@ -570,11 +580,11 @@ RAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum,
   return LRI;
 }
 
-// setPhysReg - Change MO the refer the PhysReg, considering subregs.
-// This may invalidate MO if it is necessary to add implicit kills for a
-// superregister.
-// Return tru if MO kills its register.
-bool RAFast::setPhysReg(MachineOperand &MO, unsigned PhysReg) {
+// setPhysReg - Change operand OpNum in MI the refer the PhysReg, considering
+// subregs. This may invalidate any operand pointers.
+// Return true if the operand kills its register.
+bool RAFast::setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg) {
+  MachineOperand &MO = MI->getOperand(OpNum);
   if (!MO.getSubReg()) {
     MO.setReg(PhysReg);
     return MO.isKill() || MO.isDead();
@@ -585,17 +595,17 @@ bool RAFast::setPhysReg(MachineOperand &MO, unsigned PhysReg) {
   MO.setSubReg(0);
   if (MO.isUse()) {
     if (MO.isKill()) {
-      MO.getParent()->addRegisterKilled(PhysReg, TRI, true);
+      MI->addRegisterKilled(PhysReg, TRI, true);
       return true;
     }
     return false;
   }
   // A subregister def implicitly defines the whole physreg.
   if (MO.isDead()) {
-    MO.getParent()->addRegisterDead(PhysReg, TRI, true);
+    MI->addRegisterDead(PhysReg, TRI, true);
     return true;
   }
-  MO.getParent()->addRegisterDefined(PhysReg, TRI);
+  MI->addRegisterDefined(PhysReg, TRI);
   return false;
 }
 
@@ -612,7 +622,7 @@ void RAFast::AllocateBasicBlock() {
          E = MBB->livein_end(); I != E; ++I)
     definePhysReg(MII, *I, regReserved);
 
-  SmallVector<unsigned, 8> PhysECs;
+  SmallVector<unsigned, 8> PhysECs, VirtDead;
   SmallVector<MachineInstr*, 32> Coalesced;
 
   // Otherwise, sequentially allocate each instruction in the MBB.
@@ -661,7 +671,7 @@ void RAFast::AllocateBasicBlock() {
         if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
         LiveRegMap::iterator LRI = LiveVirtRegs.find(Reg);
         if (LRI != LiveVirtRegs.end())
-          setPhysReg(MO, LRI->second.PhysReg);
+          setPhysReg(MI, i, LRI->second.PhysReg);
         else
           MO.setReg(0); // We can't allocate a physreg for a DebugValue, sorry!
       }
@@ -712,12 +722,13 @@ void RAFast::AllocateBasicBlock() {
         LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, CopyDst);
         unsigned PhysReg = LRI->second.PhysReg;
         CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0;
-        if (setPhysReg(MO, PhysReg))
+        if (setPhysReg(MI, i, PhysReg))
           killVirtReg(LRI);
       } else if (MO.isEarlyClobber()) {
+        // Note: defineVirtReg may invalidate MO.
         LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, 0);
         unsigned PhysReg = LRI->second.PhysReg;
-        setPhysReg(MO, PhysReg);
+        setPhysReg(MI, i, PhysReg);
         PhysECs.push_back(PhysReg);
       }
     }
@@ -760,13 +771,21 @@ void RAFast::AllocateBasicBlock() {
       }
       LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, CopySrc);
       unsigned PhysReg = LRI->second.PhysReg;
-      if (setPhysReg(MO, PhysReg)) {
-        killVirtReg(LRI);
+      if (setPhysReg(MI, i, PhysReg)) {
+        VirtDead.push_back(Reg);
         CopyDst = 0; // cancel coalescing;
       } else
         CopyDst = (CopyDst == Reg || CopyDst == PhysReg) ? PhysReg : 0;
     }
 
+    // Kill dead defs after the scan to ensure that multiple defs of the same
+    // register are allocated identically. We didn't need to do this for uses
+    // because we are crerating our own kill flags, and they are always at the
+    // last use.
+    for (unsigned i = 0, e = VirtDead.size(); i != e; ++i)
+      killVirtReg(VirtDead[i]);
+    VirtDead.clear();
+
     MRI->addPhysRegsUsed(UsedInInstr);
 
     if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) {
@@ -796,8 +815,6 @@ bool RAFast::runOnMachineFunction(MachineFunction &Fn) {
   DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
                << "********** Function: "
                << ((Value*)Fn.getFunction())->getName() << '\n');
-  if (VerifyFastRegalloc)
-    Fn.verify(this, true);
   MF = &Fn;
   MRI = &MF->getRegInfo();
   TM = &Fn.getTarget();