Subzero: Translation-time improvements in the register allocator.

src/IceRegAlloc.cpp

 //===- subzero/src/IceRegAlloc.cpp - Linear-scan implementation -----------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the LinearScan class, which performs the
@@ skipping 40 matching lines @@
     const InstDefList &Defs = VMetadata->getDefinitions(Var);
     for (size_t i = 0; i < Defs.size(); ++i) {
       if (i > 0)
         Str << ",";
       Str << Defs[i]->getNumber();
     }
     Str << "\n";
   }
 }
 
+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
 // Register Allocation in the Context of SSA Form and Register
 // Constraints" by Hanspeter Mössenböck and Michael Pfeiffer,
 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF .  This
 // implementation is modified to take affinity into account and allow
 // two interfering variables to share the same register in certain
 // cases.
 //
 // Requires running Cfg::liveness(Liveness_Intervals) in
 // preparation.  Results are assigned to Variable::RegNum for each
 // Variable.
 void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
   TimerMarker T(TimerStack::TT_linearScan, Func);
   assert(RegMaskFull.any()); // Sanity check
   Unhandled.clear();
   UnhandledPrecolored.clear();
   Handled.clear();
   Inactive.clear();
   Active.clear();
   Ostream &Str = Func->getContext()->getStrDump();
   bool Verbose = Func->getContext()->isVerbose(IceV_LinearScan);
   Func->resetCurrentNode();
   VariablesMetadata *VMetadata = Func->getVMetadata();
 
   // Gather the live ranges of all variables and add them to the
-  // Unhandled set.  TODO: Unhandled is a set<> which is based on a
-  // balanced binary tree, so inserting live ranges for N variables is
-  // O(N log N) complexity.  N may be proportional to the number of
-  // instructions, thanks to temporary generation during lowering.  As
-  // a result, it may be useful to design a better data structure for
-  // storing Func->getVariables().
+  // Unhandled set.
   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.
       if (Var->getWeight() == RegWeight::Zero)
         continue;
       // Don't bother if the variable has a null live range, which means
       // it was never referenced.
       if (Var->getLiveRange().isEmpty())
         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 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
   // I is currently assigned to.  It can be greater than 1 as a result
   // of AllowOverlap inference below.
   std::vector<int> RegUses(RegMaskFull.size());
   // Unhandled is already set to all ranges in increasing order of
   // start points.
   assert(Active.empty());
   assert(Inactive.empty());
   assert(Handled.empty());
   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);
       Str << "\n";
     }
     const llvm::SmallBitVector RegMask =
         RegMaskFull &
         Func->getTarget()->getRegisterSetForType(Cur.Var->getType());
 
     // Check for precolored ranges.  If Cur is precolored, it
     // definitely gets that register.  Previously processed live
     // ranges would have avoided that register due to it being
     // precolored.  Future processed live ranges won't evict that
     // register because the live range has infinite weight.
     if (Cur.Var->hasReg()) {
       int32_t RegNum = Cur.Var->getRegNum();
       // RegNumTmp should have already been set above.
       assert(Cur.Var->getRegNumTmp() == RegNum);
       if (Verbose) {
         Str << "Precoloring  ";
         Cur.dump(Func);
         Str << "\n";
       }
       Active.push_back(Cur);
       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;
     }
 
     // Check for active ranges that have expired or become inactive.
     for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) {
       Next = I;
       ++Next;
       LiveRangeWrapper Item = *I;
       Item.Var->trimLiveRange(Cur.range().getStart());
       bool Moved = false;
       if (Item.endsBefore(Cur)) {
         // Move Item from Active to Handled list.
         if (Verbose) {
           Str << "Expiring     ";
           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.
         if (Verbose) {
           Str << "Inactivating ";
           Item.dump(Func);
           Str << "\n";
         }
-        Active.erase(I);
-        Inactive.push_back(Item);
+        Inactive.splice(Inactive.end(), Active, I);
         Moved = true;
       }
       if (Moved) {
         // Decrement Item from RegUses[].
         assert(Item.Var->hasRegTmp());
         int32_t RegNum = Item.Var->getRegNumTmp();
         --RegUses[RegNum];
         assert(RegUses[RegNum] >= 0);
       }
     }
@@ skipping 13 matching lines @@
       // beginning of the function.
       if (!Item.range().isNonpoints())
         continue;
       if (Item.endsBefore(Cur)) {
         // Move Item from Inactive to Handled list.
         if (Verbose) {
           Str << "Expiring     ";
           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) {
           Str << "Reactivating ";
           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();
         assert(RegUses[RegNum] >= 0);
         ++RegUses[RegNum];
       }
     }
 
     // Calculate available registers into Free[].
     llvm::SmallBitVector Free = RegMask;
@@ skipping 89 matching lines @@
     std::vector<RegWeight> Weights(RegMask.size());
 
     // Remove registers from the Free[] list where an Unhandled
     // precolored range overlaps with the current range, and set those
     // registers to infinite weight so that they aren't candidates for
     // eviction.  Cur.endsBefore(Item) is an early exit check that
     // turns a guaranteed O(N^2) algorithm into expected linear
     // 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;
       if (Item.overlaps(Cur)) {
         int32_t ItemReg = Item.Var->getRegNum(); // Note: not getRegNumTmp()
         Weights[ItemReg].setWeight(RegWeight::Inf);
         Free[ItemReg] = false;
         PrecoloredUnhandledMask[ItemReg] = true;
         // Disable AllowOverlap if the preferred register is one of
         // these precolored unhandled overlapping ranges.
@@ skipping 89 matching lines @@
           LiveRangeWrapper Item = *I;
           if (Item.Var->getRegNumTmp() == MinWeightIndex) {
             if (Verbose) {
               Str << "Evicting     ";
               Item.dump(Func);
               Str << "\n";
             }
             --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.
         for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) {
           Next = I;
           ++Next;
           LiveRangeWrapper Item = *I;
           // Note: The Item.overlaps(Cur) clause is not part of the
           // description of AssignMemLoc() in the original paper.  But
           // there doesn't seem to be any need to evict an inactive
           // live range that doesn't overlap with the live range
           // currently being considered.  It's especially bad if we
           // would end up evicting an infinite-weight but
           // currently-inactive live range.  The most common situation
           // for this would be a scratch register kill set for call
           // instructions.
           if (Item.Var->getRegNumTmp() == MinWeightIndex &&
               Item.overlaps(Cur)) {
             if (Verbose) {
               Str << "Evicting     ";
               Item.dump(Func);
               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.
         Cur.Var->setRegNumTmp(MinWeightIndex);
         assert(RegUses[MinWeightIndex] >= 0);
         ++RegUses[MinWeightIndex];
         Active.push_back(Cur);
         if (Verbose) {
           Str << "Allocating   ";
           Cur.dump(Func);
@@ skipping 60 matching lines @@
   if (!Func->getContext()->isVerbose(IceV_LinearScan))
     return;
   Func->resetCurrentNode();
   Str << "**** Current regalloc state:\n";
   Str << "++++++ Handled:\n";
   for (const LiveRangeWrapper &Item : Handled) {
     Item.dump(Func);
     Str << "\n";
   }
   Str << "++++++ Unhandled:\n";
-  for (const LiveRangeWrapper &Item : Unhandled) {
-    Item.dump(Func);
+  for (auto I = Unhandled.rbegin(), E = Unhandled.rend(); I != E; ++I) {
+    I->dump(Func);
     Str << "\n";
   }
   Str << "++++++ Active:\n";
   for (const LiveRangeWrapper &Item : Active) {
     Item.dump(Func);
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const LiveRangeWrapper &Item : Inactive) {
     Item.dump(Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice