Fix order of eval problem from when I refactored this into a function.

[oota-llvm.git] / lib / CodeGen / LiveVariables.cpp

diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp
index c11e00f0c8dc2699ece3035fb4014cf3f160ee63..cb034c017a89ab486b674612896f3980d18dd193 100644 (file)
--- a/lib/CodeGen/LiveVariables.cpp
+++ b/lib/CodeGen/LiveVariables.cpp
@@ -34,6 +34,7 @@
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Config/alloca.h"
+#include <algorithm>
 using namespace llvm;
 
 static RegisterAnalysis<LiveVariables> X("livevars", "Live Variable Analysis");
@@ -51,6 +52,25 @@ LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) {
   return VirtRegInfo[RegIdx];
 }
 
+bool LiveVariables::KillsRegister(MachineInstr *MI, unsigned Reg) const {
+  std::map<MachineInstr*, std::vector<unsigned> >::const_iterator I = 
+  RegistersKilled.find(MI);
+  if (I == RegistersKilled.end()) return false;
+  
+  // Do a binary search, as these lists can grow pretty big, particularly for
+  // call instructions on targets with lots of call-clobbered registers.
+  return std::binary_search(I->second.begin(), I->second.end(), Reg);
+}
+
+bool LiveVariables::RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const {
+  std::map<MachineInstr*, std::vector<unsigned> >::const_iterator I = 
+  RegistersDead.find(MI);
+  if (I == RegistersDead.end()) return false;
+  
+  // Do a binary search, as these lists can grow pretty big, particularly for
+  // call instructions on targets with lots of call-clobbered registers.
+  return std::binary_search(I->second.begin(), I->second.end(), Reg);
+}
 
 
 void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo,
@@ -125,9 +145,9 @@ void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) {
   // Does this kill a previous version of this register?
   if (MachineInstr *LastUse = PhysRegInfo[Reg]) {
     if (PhysRegUsed[Reg])
-      RegistersKilled.insert(std::make_pair(LastUse, Reg));
+      RegistersKilled[LastUse].push_back(Reg);
     else
-      RegistersDead.insert(std::make_pair(LastUse, Reg));
+      RegistersDead[LastUse].push_back(Reg);
   }
   PhysRegInfo[Reg] = MI;
   PhysRegUsed[Reg] = false;
@@ -136,9 +156,9 @@ void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) {
        unsigned Alias = *AliasSet; ++AliasSet) {
     if (MachineInstr *LastUse = PhysRegInfo[Alias]) {
       if (PhysRegUsed[Alias])
-        RegistersKilled.insert(std::make_pair(LastUse, Alias));
+        RegistersKilled[LastUse].push_back(Alias);
       else
-        RegistersDead.insert(std::make_pair(LastUse, Alias));
+        RegistersDead[LastUse].push_back(Alias);
     }
     PhysRegInfo[Alias] = MI;
     PhysRegUsed[Alias] = false;
@@ -293,14 +313,24 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &MF) {
   for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i)
     for (unsigned j = 0, e = VirtRegInfo[i].Kills.size(); j != e; ++j) {
       if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst)
-        RegistersDead.insert(std::make_pair(VirtRegInfo[i].Kills[j],
-                             i + MRegisterInfo::FirstVirtualRegister));
+        RegistersDead[VirtRegInfo[i].Kills[j]].push_back(
+                                    i + MRegisterInfo::FirstVirtualRegister);
 
       else
-        RegistersKilled.insert(std::make_pair(VirtRegInfo[i].Kills[j],
-                               i + MRegisterInfo::FirstVirtualRegister));
+        RegistersKilled[VirtRegInfo[i].Kills[j]].push_back(
+                                    i + MRegisterInfo::FirstVirtualRegister);
     }
 
+  // Walk through the RegistersKilled/Dead sets, and sort the registers killed
+  // or dead.  This allows us to use efficient binary search for membership
+  // testing.
+  for (std::map<MachineInstr*, std::vector<unsigned> >::iterator
+       I = RegistersKilled.begin(), E = RegistersKilled.end(); I != E; ++I)
+    std::sort(I->second.begin(), I->second.end());
+  for (std::map<MachineInstr*, std::vector<unsigned> >::iterator
+       I = RegistersDead.begin(), E = RegistersDead.end(); I != E; ++I)
+    std::sort(I->second.begin(), I->second.end());
+  
   // Check to make sure there are no unreachable blocks in the MC CFG for the
   // function.  If so, it is due to a bug in the instruction selector or some
   // other part of the code generator if this happens.
@@ -342,21 +372,23 @@ void LiveVariables::instructionChanged(MachineInstr *OldMI,
   // Move the killed information over...
   killed_iterator I, E;
   tie(I, E) = killed_range(OldMI);
-  std::vector<unsigned> Regs;
-  for (killed_iterator A = I; A != E; ++A)
-    Regs.push_back(A->second);
-  RegistersKilled.erase(I, E);
-
-  for (unsigned i = 0, e = Regs.size(); i != e; ++i)
-    RegistersKilled.insert(std::make_pair(NewMI, Regs[i]));
-  Regs.clear();
+  if (I != E) {
+    std::vector<unsigned> &V = RegistersKilled[NewMI];
+    bool WasEmpty = V.empty();
+    V.insert(V.end(), I, E);
+    if (!WasEmpty)
+      std::sort(V.begin(), V.end());   // Keep the reg list sorted.
+    RegistersKilled.erase(OldMI);
+  }
 
   // Move the dead information over...
   tie(I, E) = dead_range(OldMI);
-  for (killed_iterator A = I; A != E; ++A)
-    Regs.push_back(A->second);
-  RegistersDead.erase(I, E);
-
-  for (unsigned i = 0, e = Regs.size(); i != e; ++i)
-    RegistersDead.insert(std::make_pair(NewMI, Regs[i]));
+  if (I != E) {
+    std::vector<unsigned> &V = RegistersDead[NewMI];
+    bool WasEmpty = V.empty();
+    V.insert(V.end(), I, E);
+    if (!WasEmpty)
+      std::sort(V.begin(), V.end());   // Keep the reg list sorted.
+    RegistersDead.erase(OldMI);
+  }
 }