Subzero: Improve regalloc performance by optimizing UnhandledPrecolored.

src/IceRegAlloc.cpp

Index: src/IceRegAlloc.cpp
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index 3a4c178311747a5eda63ba2ed0aefb3b77f45b65..6d8e4e27fcc9bb4245586b3816832c3439777bb3 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -68,6 +68,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
   TimerMarker T(IDscan, Func->getContext());
   assert(RegMaskFull.any()); // Sanity check
   Unhandled.clear();
+  UnhandledPrecolored.clear();
   Handled.clear();
   Inactive.clear();
   Active.clear();
@@ -101,6 +102,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
       if (Var->hasReg()) {
         Var->setRegNumTmp(Var->getRegNum());
         Var->setLiveRangeInfiniteWeight();
+        UnhandledPrecolored.insert(LiveRangeWrapper(Var));
       }
     }
   }
@@ -145,6 +147,9 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
       Active.push_back(Cur);
       assert(RegUses[RegNum] >= 0);
       ++RegUses[RegNum];
+      assert(!UnhandledPrecolored.empty());
+      assert(UnhandledPrecolored.begin()->Var == Cur.Var);
+      UnhandledPrecolored.erase(UnhandledPrecolored.begin());
       continue;
     }
 
@@ -310,15 +315,16 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
     // 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) {
@@ -334,7 +340,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
         if (RegMask[i]) {
           Str << Func->getTarget()->getRegName(i, IceType_i32)
               << "(U=" << RegUses[i] << ",F=" << Free[i]
-              << ",P=" << PrecoloredUnhandled[i] << ") ";
+              << ",P=" << PrecoloredUnhandledMask[i] << ") ";
         }
       }
       Str << "\n";
@@ -385,16 +391,16 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
           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