Replace RegScavenger::DistanceMap with a simpler local algorithm.

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

2 files changed, 53 insertions, 68 deletions

diff --git a/include/llvm/CodeGen/RegisterScavenging.h b/include/llvm/CodeGen/RegisterScavenging.h
index f81c495..6a15fcf 100644
--- a/include/llvm/CodeGen/RegisterScavenging.h
+++ b/include/llvm/CodeGen/RegisterScavenging.h
@@ -150,6 +150,12 @@ private:
 
   /// Add Reg and its aliases to BV.
   void addRegWithAliases(BitVector &BV, unsigned Reg);
+
+  unsigned findSurvivorReg(MachineBasicBlock::iterator MI,
+                           BitVector &Candidates,
+                           unsigned InstrLimit,
+                           MachineBasicBlock::iterator &UseMI);
+
 };
 
 } // End llvm namespace
diff --git a/lib/CodeGen/RegisterScavenging.cpp b/lib/CodeGen/RegisterScavenging.cpp
index e595a36..9faf597 100644
--- a/lib/CodeGen/RegisterScavenging.cpp
+++ b/lib/CodeGen/RegisterScavenging.cpp
@@ -280,41 +280,47 @@ unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
   return (Reg == -1) ? 0 : Reg;
 }
 
-/// DistanceMap - Keep track the distance of an MI from the current position.
-typedef DenseMap<MachineInstr*, unsigned> DistanceMap;
-
-/// Build a distance map for instructions from I to E.
-static void buildDistanceMap(DistanceMap &DM,
-                             MachineBasicBlock::iterator I,
-                             MachineBasicBlock::iterator E) {
-  DM.clear();
-  for (unsigned d = 0; I != E; ++I, ++d)
-    DM.insert(DistanceMap::value_type(I, d));
-}
+/// findSurvivorReg - Return the candidate register that is unused for the
+/// longest after MBBI. UseMI is set to the instruction where the search
+/// stopped.
+///
+/// No more than InstrLimit instructions are inspected.
+///
+unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator MI,
+                                       BitVector &Candidates,
+                                       unsigned InstrLimit,
+                                       MachineBasicBlock::iterator &UseMI) {
+  int Survivor = Candidates.find_first();
+  assert(Survivor > 0 && "No candidates for scavenging");
+
+  MachineBasicBlock::iterator ME = MBB->getFirstTerminator();
+  assert(MI != ME && "MI already at terminator");
+
+  for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) {
+    // Remove any candidates touched by instruction.
+    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+      const MachineOperand &MO = MI->getOperand(i);
+      if (!MO.isReg() || MO.isUndef() || !MO.getReg())
+        continue;
+      Candidates.reset(MO.getReg());
+      for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++)
+        Candidates.reset(*R);
+    }
 
-/// findFirstUse - Calculate the distance to the first use of the
-/// specified register in the range covered by DM.
-static MachineInstr *findFirstUse(const MachineBasicBlock *MBB,
-                                  const DistanceMap &DM,
-                                  unsigned Reg,
-                                  unsigned &Dist) {
-  const MachineRegisterInfo *MRI = &MBB->getParent()->getRegInfo();
-  MachineInstr *UseMI = 0;
-  Dist = ~0U;
-  for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg),
-         RE = MRI->reg_end(); RI != RE; ++RI) {
-    MachineInstr *UDMI = &*RI;
-    if (UDMI->getParent() != MBB)
-      continue;
-    DistanceMap::const_iterator DI = DM.find(UDMI);
-    if (DI == DM.end())
+    // Was our survivor untouched by this instruction?
+    if (Candidates.test(Survivor))
       continue;
-    if (DI->second < Dist) {
-      Dist = DI->second;
-      UseMI = UDMI;
-    }
+
+    // All candidates gone?
+    if (Candidates.none())
+      break;
+
+    Survivor = Candidates.find_first();
   }
-  return UseMI;
+
+  // We ran out of candidates, so stop the search.
+  UseMI = MI;
+  return Survivor;
 }
 
 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
@@ -336,40 +342,15 @@ unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
       Candidates.reset(MO.getReg());
   }
 
-  // Prepare to call findFirstUse() a number of times.
-  DistanceMap DM;
-  buildDistanceMap(DM, I, MBB->end());
-
   // Find the register whose use is furthest away.
-  unsigned SReg = 0;
-  unsigned MaxDist = 0;
-  MachineInstr *MaxUseMI = 0;
-  int Reg = Candidates.find_first();
-  while (Reg != -1) {
-    unsigned Dist;
-    MachineInstr *UseMI = findFirstUse(MBB, DM, Reg, Dist);
-    for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
-      unsigned AsDist;
-      MachineInstr *AsUseMI = findFirstUse(MBB, DM, *AS, AsDist);
-      if (AsDist < Dist) {
-        Dist = AsDist;
-        UseMI = AsUseMI;
-      }
-    }
+  MachineBasicBlock::iterator UseMI;
+  unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
 
-    // If we found an unused register there is no reason to spill it. We have
-    // probably found a callee-saved register that has been saved in the
-    // prologue, but happens to be unused at this point.
-    if (!isAliasUsed(Reg))
-      return Reg;
-
-    if (Dist >= MaxDist) {
-      MaxDist = Dist;
-      MaxUseMI = UseMI;
-      SReg = Reg;
-    }
-    Reg = Candidates.find_next(Reg);
-  }
+  // If we found an unused register there is no reason to spill it. We have
+  // probably found a callee-saved register that has been saved in the
+  // prologue, but happens to be unused at this point.
+  if (!isAliasUsed(SReg))
+    return SReg;
 
   assert(ScavengedReg == 0 &&
          "Scavenger slot is live, unable to scavenge another register!");
@@ -383,10 +364,8 @@ unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
   TRI->eliminateFrameIndex(II, SPAdj, this);
 
   // Restore the scavenged register before its use (or first terminator).
-  II = MaxUseMI
-    ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator();
-  TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC);
-  ScavengeRestore = prior(II);
+  TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC);
+  ScavengeRestore = prior(UseMI);
   // Doing this here leads to infinite regress.
   // ScavengedReg = SReg;
   ScavengedRC = RC;