Keep the killed/dead sets sorted, so that "KillsRegister" can do a quick

binary search to test for membership.  This speeds up LLC a bit more on KC++,
e.g. on itanium from 16.6974s to 14.8272s, PPC from 11.4926s to 10.7089s and
X86 from 10.8128s to 9.7943s, with no difference in generated code (like all
of the RA patches).

With these changes, isel is the slowest pass for PPC/X86, but linscan+live
intervals is still > 50% of the compile time for itanium.  More work could
be done, but this is the last for now.


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

1 files changed, 26 insertions, 22 deletions

diff --git a/include/llvm/CodeGen/LiveVariables.h b/include/llvm/CodeGen/LiveVariables.h
index 3debf347fc..2c1e06596f 100644
--- a/include/llvm/CodeGen/LiveVariables.h
+++ b/include/llvm/CodeGen/LiveVariables.h
@@ -145,16 +145,8 @@ public:
 
   /// KillsRegister - Return true if the specified instruction kills the
   /// specified register.
-  bool KillsRegister(MachineInstr *MI, unsigned Reg) const {
-    std::map<MachineInstr*, std::vector<unsigned> >::const_iterator I = 
-      RegistersKilled.find(MI);
-    if (I != RegistersKilled.end())
-      for (std::vector<unsigned>::const_iterator CI = I->second.begin(),
-           E = I->second.end(); CI != E; ++CI)
-        if (*CI == Reg) return true;
-    return false;
-  }
-
+  bool KillsRegister(MachineInstr *MI, unsigned Reg) const;
+  
   killed_iterator dead_begin(MachineInstr *MI) {
     return getDeadDefsVector(MI).begin();
   }
@@ -169,16 +161,8 @@ public:
   
   /// RegisterDefIsDead - Return true if the specified instruction defines the
   /// specified register, but that definition is dead.
-  bool RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const {
-    std::map<MachineInstr*, std::vector<unsigned> >::const_iterator I = 
-      RegistersDead.find(MI);
-    if (I != RegistersDead.end())
-      for (std::vector<unsigned>::const_iterator CI = I->second.begin(),
-           E = I->second.end(); CI != E; ++CI)
-        if (*CI == Reg) return true;
-    return false;
-  }
-
+  bool RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const;
+  
   //===--------------------------------------------------------------------===//
   //  API to update live variable information
 
@@ -193,7 +177,17 @@ public:
   /// instruction.
   ///
   void addVirtualRegisterKilled(unsigned IncomingReg, MachineInstr *MI) {
-    RegistersKilled.insert(std::make_pair(MI, IncomingReg));
+    std::vector<unsigned> &V = RegistersKilled[MI];
+    // Insert in a sorted order.
+    if (V.empty() || IncomingReg > V.back()) {
+      V.push_back(IncomingReg);
+    } else {
+      std::vector<unsigned>::iterator I = V.begin();
+      for (; *I < IncomingReg; ++I)
+        /*empty*/;
+      if (*I != IncomingReg)   // Don't insert duplicates.
+        V.insert(I, IncomingReg);
+    }
     getVarInfo(IncomingReg).Kills.push_back(MI);
   }
 
@@ -226,7 +220,17 @@ public:
   /// register is dead after being used by the specified instruction.
   ///
   void addVirtualRegisterDead(unsigned IncomingReg, MachineInstr *MI) {
-    RegistersDead.insert(std::make_pair(MI, IncomingReg));
+    std::vector<unsigned> &V = RegistersDead[MI];
+    // Insert in a sorted order.
+    if (V.empty() || IncomingReg > V.back()) {
+      V.push_back(IncomingReg);
+    } else {
+      std::vector<unsigned>::iterator I = V.begin();
+      for (; *I < IncomingReg; ++I)
+        /*empty*/;
+      if (*I != IncomingReg)   // Don't insert duplicates.
+        V.insert(I, IncomingReg);
+    }
     getVarInfo(IncomingReg).Kills.push_back(MI);
   }