Subzero. Changes the Register Allocator so that it is aware of register

src/IceRegAlloc.cpp

Index: src/IceRegAlloc.cpp
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index cad7fb582e8e329676d16e1916358e568047ed76..bccd29bb0603854f477beea3b0f0a3071578fcc8 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -225,6 +225,13 @@ void LinearScan::init(RegAllocKind Kind) {
   Inactive.clear();
   Active.clear();
 
+  Target = Func->getTarget();

[Jim Stichnoth, 2015/09/04 16:53:10]

Actually, Target is probably better initialized in the ctor, similar to Ctx.

[John, 2015/09/04 17:32:25]

Done.

+  SizeT NumRegs = Target->getNumRegisters();
+  RegAliases.resize(NumRegs);
+  for (SizeT Reg = 0; Reg < NumRegs; ++Reg) {
+    RegAliases[Reg] = &Target->getAliasesForRegister(Reg);
+  }
+
   switch (Kind) {
   case RAK_Unknown:
     llvm::report_fatal_error("Invalid RAK_Unknown");
@@ -340,9 +347,12 @@ void LinearScan::handleActiveRangeExpiredOrInactive(const Variable *Cur) {
     if (Moved) {
       // Decrement Item from RegUses[].
       assert(Item->hasRegTmp());
-      int32_t RegNum = Item->getRegNumTmp();
-      --RegUses[RegNum];
-      assert(RegUses[RegNum] >= 0);
+      const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+      for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;

[Jim Stichnoth, 2015/09/04 00:10:20]

So I greatly prefer using int32_t rather than int.  Unfortunately,
SmallBitVector.h chooses to use int for the return value of find_first() and
find_next().  I wonder if it's reasonable to typedef something to int and use it
for these SmallBitVector accesses, so that the type actually matches yet we
minimize our explicit use of int.

[John, 2015/09/04 17:32:25]

This is an excellent case where using auto is superior to **anything** (ok,
maybe using decltype() magic would also work, but... yikes.)

+           RegAlias = Aliases.find_next(RegAlias)) {
+        --RegUses[RegAlias];
+        assert(RegUses[RegAlias] >= 0);
+      }
     }
   }
 }
@@ -362,9 +372,12 @@ void LinearScan::handleInactiveRangeExpiredOrReactivated(const Variable *Cur) {
       moveItem(Inactive, Index, Active);
       // Increment Item in RegUses[].
       assert(Item->hasRegTmp());
-      int32_t RegNum = Item->getRegNumTmp();
-      assert(RegUses[RegNum] >= 0);
-      ++RegUses[RegNum];
+      const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+      for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+           RegAlias = Aliases.find_next(RegAlias)) {
+        assert(RegUses[RegAlias] >= 0);
+        ++RegUses[RegAlias];
+      }
     }
   }
 }
@@ -459,15 +472,19 @@ void LinearScan::filterFreeWithPrecoloredRanges(IterationState &Iter) {
     if (Iter.Cur->rangeEndsBefore(Item))
       break;
     if (Item->rangeOverlaps(Iter.Cur)) {
-      int32_t ItemReg = Item->getRegNum(); // Note: not getRegNumTmp()
-      Iter.Weights[ItemReg].setWeight(RegWeight::Inf);
-      Iter.Free[ItemReg] = false;
-      Iter.PrecoloredUnhandledMask[ItemReg] = true;
-      // Disable Iter.AllowOverlap if the preferred register is one of these
-      // pre-colored unhandled overlapping ranges.
-      if (Iter.AllowOverlap && ItemReg == Iter.PreferReg) {
-        Iter.AllowOverlap = false;
-        dumpDisableOverlap(Func, Item, "PrecoloredUnhandled");
+      const llvm::SmallBitVector &Aliases =
+          *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp()
+      for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+           RegAlias = Aliases.find_next(RegAlias)) {
+        Iter.Weights[RegAlias].setWeight(RegWeight::Inf);
+        Iter.Free[RegAlias] = false;
+        Iter.PrecoloredUnhandledMask[RegAlias] = true;
+        // Disable Iter.AllowOverlap if the preferred register is one of these
+        // pre-colored unhandled overlapping ranges.
+        if (Iter.AllowOverlap && RegAlias == Iter.PreferReg) {
+          Iter.AllowOverlap = false;
+          dumpDisableOverlap(Func, Item, "PrecoloredUnhandled");
+        }
       }
     }
   }
@@ -479,8 +496,12 @@ void LinearScan::allocatePrecoloredRegister(Variable *Cur) {
   assert(Cur->getRegNumTmp() == RegNum);
   dumpLiveRangeTrace("Precoloring  ", Cur);
   Active.push_back(Cur);
-  assert(RegUses[RegNum] >= 0);
-  ++RegUses[RegNum];
+  const llvm::SmallBitVector &Aliases = *RegAliases[RegNum];
+  for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+       RegAlias = Aliases.find_next(RegAlias)) {
+    assert(RegUses[RegAlias] >= 0);
+    ++RegUses[RegAlias];
+  }
   assert(!UnhandledPrecolored.empty());
   assert(UnhandledPrecolored.back() == Cur);
   UnhandledPrecolored.pop_back();
@@ -489,8 +510,12 @@ void LinearScan::allocatePrecoloredRegister(Variable *Cur) {
 void LinearScan::allocatePreferredRegister(IterationState &Iter) {
   Iter.Cur->setRegNumTmp(Iter.PreferReg);
   dumpLiveRangeTrace("Preferring   ", Iter.Cur);
-  assert(RegUses[Iter.PreferReg] >= 0);
-  ++RegUses[Iter.PreferReg];
+  const llvm::SmallBitVector &Aliases = *RegAliases[Iter.PreferReg];
+  for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+       RegAlias = Aliases.find_next(RegAlias)) {
+    assert(RegUses[RegAlias] >= 0);
+    ++RegUses[RegAlias];
+  }
   Active.push_back(Iter.Cur);
 }
 
@@ -498,8 +523,12 @@ void LinearScan::allocateFreeRegister(IterationState &Iter) {
   int32_t RegNum = Iter.Free.find_first();
   Iter.Cur->setRegNumTmp(RegNum);
   dumpLiveRangeTrace("Allocating   ", Iter.Cur);
-  assert(RegUses[RegNum] >= 0);
-  ++RegUses[RegNum];
+  const llvm::SmallBitVector &Aliases = *RegAliases[RegNum];
+  for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+       RegAlias = Aliases.find_next(RegAlias)) {
+    assert(RegUses[RegAlias] >= 0);
+    ++RegUses[RegAlias];
+  }
   Active.push_back(Iter.Cur);
 }
 
@@ -507,16 +536,28 @@ void LinearScan::handleNoFreeRegisters(IterationState &Iter) {
   // Check Active ranges.
   for (const Variable *Item : Active) {
     assert(Item->rangeOverlaps(Iter.Cur));
-    int32_t RegNum = Item->getRegNumTmp();
     assert(Item->hasRegTmp());
-    Iter.Weights[RegNum].addWeight(Item->getWeight(Func));
+    const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+    // We add the Item's weight to each alias/subregister to represent that,
+    // should we decide to pick any of them, then we would incur that many
+    // memory accesses.
+    RegWeight W = Item->getWeight(Func);
+    for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+         RegAlias = Aliases.find_next(RegAlias)) {
+      Iter.Weights[RegAlias].addWeight(W);
+    }
   }
   // Same as above, but check Inactive ranges instead of Active.
   for (const Variable *Item : Inactive) {
-    int32_t RegNum = Item->getRegNumTmp();
+    if (!Item->rangeOverlaps(Iter.Cur))
+      continue;
     assert(Item->hasRegTmp());
-    if (Item->rangeOverlaps(Iter.Cur))
-      Iter.Weights[RegNum].addWeight(Item->getWeight(Func));
+    const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+    RegWeight W = Item->getWeight(Func);
+    for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+         RegAlias = Aliases.find_next(RegAlias)) {
+      Iter.Weights[RegAlias].addWeight(W);
+    }
   }
 
   // All the weights are now calculated. Find the register with smallest
@@ -548,8 +589,12 @@ void LinearScan::handleNoFreeRegisters(IterationState &Iter) {
       Variable *Item = Active[Index];
       if (Item->getRegNumTmp() == MinWeightIndex) {
         dumpLiveRangeTrace("Evicting     ", Item);
-        --RegUses[MinWeightIndex];
-        assert(RegUses[MinWeightIndex] >= 0);
+        const llvm::SmallBitVector &Aliases = *RegAliases[MinWeightIndex];
+        for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+             RegAlias = Aliases.find_next(RegAlias)) {
+          --RegUses[RegAlias];
+          assert(RegUses[RegAlias] >= 0);
+        }
         Item->setRegNumTmp(Variable::NoRegister);
         moveItem(Active, Index, Handled);
       }
@@ -574,8 +619,12 @@ void LinearScan::handleNoFreeRegisters(IterationState &Iter) {
     }
     // Assign the register to Cur.
     Iter.Cur->setRegNumTmp(MinWeightIndex);
-    assert(RegUses[MinWeightIndex] >= 0);
-    ++RegUses[MinWeightIndex];
+    const llvm::SmallBitVector &Aliases = *RegAliases[MinWeightIndex];
+    for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+         RegAlias = Aliases.find_next(RegAlias)) {
+      assert(RegUses[RegAlias] >= 0);
+      ++RegUses[RegAlias];
+    }
     Active.push_back(Iter.Cur);
     dumpLiveRangeTrace("Allocating   ", Iter.Cur);
   }