Subzero: Translation-time improvements in the register allocator.

src/IceRegAlloc.cpp

Index: src/IceRegAlloc.cpp
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index 14e08d28eb1fdda40261f1be87239c3bcf549f92..8357c803bde726a0ef2022da8c8d824e9d93dda5 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -58,6 +58,14 @@ void dumpDisableOverlap(const Cfg *Func, const Variable *Var,
   }
 }
 
+bool compareRanges(const LiveRangeWrapper &L, const LiveRangeWrapper &R) {
+  InstNumberT Lstart = L.Var->getLiveRange().getStart();
+  InstNumberT Rstart = R.Var->getLiveRange().getStart();
+  if (Lstart == Rstart)
+    return L.Var->getIndex() < R.Var->getIndex();
+  return Lstart < Rstart;
+}
+
 } // end of anonymous namespace
 
 // Implements the linear-scan algorithm.  Based on "Linear Scan
@@ -94,6 +102,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
   const VarList &Vars = Func->getVariables();
   {
     TimerMarker T(TimerStack::TT_initUnhandled, Func);
+    Unhandled.reserve(Vars.size());
     for (Variable *Var : Vars) {
       // Explicitly don't consider zero-weight variables, which are
       // meant to be spill slots.
@@ -105,13 +114,18 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
         continue;
       Var->untrimLiveRange();
       LiveRangeWrapper R(Var);
-      Unhandled.insert(R);
+      Unhandled.push_back(R);
       if (Var->hasReg()) {
         Var->setRegNumTmp(Var->getRegNum());
         Var->setLiveRangeInfiniteWeight();
-        UnhandledPrecolored.insert(R);
+        UnhandledPrecolored.push_back(R);
       }
     }
+    // Do a reverse sort so that erasing elements (from the end) is

[jvoung (off chromium), 2014/10/13 21:41:50]

Can the comment fit on one line?

[Jim Stichnoth, 2014/10/13 23:40:31]

Done.  (overriding emacs's default preferences :) )

+    // fast.
+    std::sort(Unhandled.rbegin(), Unhandled.rend(), compareRanges);
+    std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(),
+              compareRanges);
   }
 
   // RegUses[I] is the number of live ranges (variables) that register
@@ -126,8 +140,8 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
   UnorderedRanges::iterator Next;
 
   while (!Unhandled.empty()) {
-    LiveRangeWrapper Cur = *Unhandled.begin();
-    Unhandled.erase(Unhandled.begin());
+    LiveRangeWrapper Cur = Unhandled.back();
+    Unhandled.pop_back();
     if (Verbose) {
       Str << "\nConsidering  ";
       Cur.dump(Func);
@@ -155,8 +169,8 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
       assert(RegUses[RegNum] >= 0);
       ++RegUses[RegNum];
       assert(!UnhandledPrecolored.empty());
-      assert(UnhandledPrecolored.begin()->Var == Cur.Var);
-      UnhandledPrecolored.erase(UnhandledPrecolored.begin());
+      assert(UnhandledPrecolored.back().Var == Cur.Var);
+      UnhandledPrecolored.pop_back();
       continue;
     }
 
@@ -174,8 +188,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
           Item.dump(Func);
           Str << "\n";
         }
-        Active.erase(I);
-        Handled.push_back(Item);
+        Handled.splice(Handled.end(), Active, I);
         Moved = true;
       } else if (!Item.overlapsStart(Cur)) {
         // Move Item from Active to Inactive list.
@@ -184,8 +197,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
           Item.dump(Func);
           Str << "\n";
         }
-        Active.erase(I);
-        Inactive.push_back(Item);
+        Inactive.splice(Inactive.end(), Active, I);
         Moved = true;
       }
       if (Moved) {
@@ -219,8 +231,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
           Item.dump(Func);
           Str << "\n";
         }
-        Inactive.erase(I);
-        Handled.push_back(Item);
+        Handled.splice(Handled.end(), Inactive, I);
       } else if (Item.overlapsStart(Cur)) {
         // Move Item from Inactive to Active list.
         if (Verbose) {
@@ -228,8 +239,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
           Item.dump(Func);
           Str << "\n";
         }
-        Inactive.erase(I);
-        Active.push_back(Item);
+        Active.splice(Active.end(), Inactive, I);
         // Increment Item in RegUses[].
         assert(Item.Var->hasRegTmp());
         int32_t RegNum = Item.Var->getRegNumTmp();
@@ -339,7 +349,9 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
     // complexity.
     llvm::SmallBitVector PrecoloredUnhandledMask(RegMask.size());
     // Note: PrecoloredUnhandledMask is only used for dumping.
-    for (const LiveRangeWrapper &Item : UnhandledPrecolored) {
+    for (auto I = UnhandledPrecolored.rbegin(), E = UnhandledPrecolored.rend();
+         I != E; ++I) {
+      LiveRangeWrapper &Item = *I;
       assert(Item.Var->hasReg());
       if (Cur.endsBefore(Item))
         break;
@@ -449,8 +461,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
             --RegUses[MinWeightIndex];
             assert(RegUses[MinWeightIndex] >= 0);
             Item.Var->setRegNumTmp(Variable::NoRegister);
-            Active.erase(I);
-            Handled.push_back(Item);
+            Handled.splice(Handled.end(), Active, I);
           }
         }
         // Do the same for Inactive.
@@ -475,8 +486,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
               Str << "\n";
             }
             Item.Var->setRegNumTmp(Variable::NoRegister);
-            Inactive.erase(I);
-            Handled.push_back(Item);
+            Handled.splice(Handled.end(), Inactive, I);
           }
         }
         // Assign the register to Cur.