Subzero: Improve regalloc performance by optimizing UnhandledPrecolored.

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 50 matching lines @@
 // 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) {
   static TimerIdT IDscan = GlobalContext::getTimerID("linearScan");
   TimerMarker T(IDscan, Func->getContext());
   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().
   const VarList &Vars = Func->getVariables();
   {
     static TimerIdT IDinitUnhandled =
         GlobalContext::getTimerID("initUnhandled");
     TimerMarker T(IDinitUnhandled, Func->getContext());
     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;

[jvoung (off chromium), 2014/10/02 16:08:18]

Tiny nit: I don't know if it saves anything to make a single Foo =
LiveRangeWrapper(Var);

and then Unhandled.insert(Foo); if (...) { UnhandlePrecolored.insert(Foo); }

[jvoung (off chromium), 2014/10/02 17:00:06]

Ah maybe not -- there's probably something with move semantics that would make
it fine/better the way you had it.

[Jim Stichnoth, 2014/10/02 19:41:47]

Done.  Probably doesn't affect performance, but it improves clarity.

[Jim Stichnoth, 2014/10/02 19:41:47]

Well, I still like it better your way. :)

       Unhandled.insert(LiveRangeWrapper(Var));
       if (Var->hasReg()) {
         Var->setRegNumTmp(Var->getRegNum());
         Var->setLiveRangeInfiniteWeight();
+        UnhandledPrecolored.insert(LiveRangeWrapper(Var));
       }
     }
   }
 
   // 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.
@@ skipping 24 matching lines @@
       // 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());
       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;
       bool Moved = false;
       if (Item.endsBefore(Cur)) {
@@ skipping 145 matching lines @@
           overlapsDefs(Func, Cur, Item.Var)) {
         AllowOverlap = false;
         dumpDisableOverlap(Func, Item.Var, "Active");
       }
     }
 
     // Remove registers from the Free[] list where an Unhandled range
     // overlaps with the current range and is precolored.
     // Cur.endsBefore(Item) is an early exit check that turns a
     // guaranteed O(N^2) algorithm into expected linear complexity.
-    llvm::SmallBitVector PrecoloredUnhandled(RegMask.size());
-    // Note: PrecoloredUnhandled is only used for dumping.
-    for (const LiveRangeWrapper &Item : Unhandled) {
+    llvm::SmallBitVector PrecoloredUnhandledMask(RegMask.size());
+    // Note: PrecoloredUnhandledMask is only used for dumping.
+    for (const LiveRangeWrapper &Item : UnhandledPrecolored) {
+      assert(Item.Var->hasReg());
       if (Cur.endsBefore(Item))
         break;
-      if (Item.Var->hasReg() && Item.overlaps(Cur)) {
+      if (Item.overlaps(Cur)) {

[jvoung (off chromium), 2014/10/02 16:08:18]

Any idea if overlaps() is more expensive, or checking if !(Free[R] &&
PrecoloredUnhandledMask[R] && AllowOverlap) is more expensive?

[Jim Stichnoth, 2014/10/02 19:41:47]

I don't think that would be worth it:

1. After combining the similar loop below with this one, the overlaps() check
will almost always have to be done anyway.

2. I'm not sure if there's a good way to cleanly express the rearrangement of
the logic.

3. The potential benefit seems limited to the handful of percent reported below
(though that might grow once more low-hanging fruit is dealt with).

         int32_t ItemReg = Item.Var->getRegNum(); // Note: not getRegNumTmp()
         Free[ItemReg] = false;
-        PrecoloredUnhandled[ItemReg] = true;
+        PrecoloredUnhandledMask[ItemReg] = true;
         // Disable AllowOverlap if the preferred register is one of
         // these precolored unhandled overlapping ranges.
         if (AllowOverlap && ItemReg == PreferReg) {
           AllowOverlap = false;
           dumpDisableOverlap(Func, Item.Var, "PrecoloredUnhandled");
         }
       }
     }
 
     // Print info about physical register availability.
     if (Verbose) {
       for (SizeT i = 0; i < RegMask.size(); ++i) {
         if (RegMask[i]) {
           Str << Func->getTarget()->getRegName(i, IceType_i32)
               << "(U=" << RegUses[i] << ",F=" << Free[i]
-              << ",P=" << PrecoloredUnhandled[i] << ") ";
+              << ",P=" << PrecoloredUnhandledMask[i] << ") ";
         }
       }
       Str << "\n";
     }
 
     if (Prefer && (AllowOverlap || Free[PreferReg])) {
       // First choice: a preferred register that is either free or is
       // allowed to overlap with its linked variable.
       Cur.Var->setRegNumTmp(PreferReg);
       if (Verbose) {
@@ skipping 30 matching lines @@
         Weights[RegNum].addWeight(Item.range().getWeight());
       }
       // Same as above, but check Inactive ranges instead of Active.
       for (const LiveRangeWrapper &Item : Inactive) {
         int32_t RegNum = Item.Var->getRegNumTmp();
         assert(Item.Var->hasRegTmp());
         if (Item.overlaps(Cur))
           Weights[RegNum].addWeight(Item.range().getWeight());
       }
       // Check Unhandled ranges that overlap Cur and are precolored.
-      // Cur.endsBefore(*I) is an early exit check that turns a
+      // Cur.endsBefore(Item) is an early exit check that turns a
       // guaranteed O(N^2) algorithm into expected linear complexity.
-      for (const LiveRangeWrapper &Item : Unhandled) {
+      for (const LiveRangeWrapper &Item : UnhandledPrecolored) {
+        assert(Item.Var->hasReg());
         if (Cur.endsBefore(Item))
           break;
-        int32_t RegNum = Item.Var->getRegNumTmp();
-        if (RegNum < 0)
-          continue;
-        if (Item.overlaps(Cur))
+        if (Item.overlaps(Cur)) {

[jvoung (off chromium), 2014/10/02 16:08:18]

Does this loop find the same set of Items which overlap Cur as the earlier loop?
Wondering if we could do something with that.

[Jim Stichnoth, 2014/10/02 19:41:47]

Nice!  We can pull Weights[] earlier in the loop and preset the pre-colored
weights to Inf, and avoid this loop entirely.

With the change from iterating over Unhandled to iterating over
UnhandledPrecolored, the gain isn't so much, but it still looks like a handful
of percent improvement on 176.gcc.

+          int32_t RegNum = Item.Var->getRegNumTmp();
           Weights[RegNum].setWeight(RegWeight::Inf);
+        }
       }
 
       // All the weights are now calculated.  Find the register with
       // smallest weight.
       int32_t MinWeightIndex = RegMask.find_first();
       // MinWeightIndex must be valid because of the initial
       // RegMask.any() test.
       assert(MinWeightIndex >= 0);
       for (SizeT i = MinWeightIndex + 1; i < Weights.size(); ++i) {
         if (RegMask[i] && Weights[i] < Weights[MinWeightIndex])
@@ skipping 143 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const LiveRangeWrapper &Item : Inactive) {
     Item.dump(Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice