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..407171c3411ce059d260e801449ec5e1d4e91b70 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -225,6 +225,13 @@ void LinearScan::init(RegAllocKind Kind) {
   Inactive.clear();
   Active.clear();
 
+  TargetLowering *Target = Func->getTarget();

[Jim Stichnoth, 2015/09/03 17:48:49]

I think maybe it's about time to make TargetLowering *Target a field of
LinearScan.

[John, 2015/09/03 22:38:24]

Done.

+  SizeT NumRegs = Target->getNumRegisters();
+  RegAliases.resize(NumRegs);
+  for (SizeT Reg = 0; Reg < NumRegs; ++Reg) {
+    RegAliases[Reg] = &Target->getAliasesForRegister(Reg);

[Jim Stichnoth, 2015/09/03 17:48:49]

Would it be easier/cleaner to just call something like
Target->getRegisterAliases() and get read-only access to the array of
SmallBitVectors?  Since you're anyway copying into your own array.

[John, 2015/09/03 22:38:24]

As we spoke offline, the underlying types holding the register aliases are not
the same.

+  }
+
   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 RegNum = Aliases.find_first(); RegNum >= 0;

[Jim Stichnoth, 2015/09/03 17:48:49]

This repeated loop pattern uses 4 different variable name variants: Reg,
RegAlias, RegNum, and ItemReg.  Would it be inappropriate to make them the same
everywhere?

[John, 2015/09/03 22:38:24]

Done.

+           RegNum = Aliases.find_next(RegNum)) {
+        --RegUses[RegNum];
+        assert(RegUses[RegNum] >= 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 RegNum = Aliases.find_first(); RegNum >= 0;
+           RegNum = Aliases.find_next(RegNum)) {
+        assert(RegUses[RegNum] >= 0);
+        ++RegUses[RegNum];
+      }
     }
   }
 }
@@ -459,15 +472,21 @@ 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 ItemReg = Aliases.find_first(); ItemReg >= 0;
+           ItemReg = Aliases.find_next(ItemReg)) {
+        // TODO(jpp): This loop should not update the weight of "parent" (i.e.,

[Jim Stichnoth, 2015/09/03 17:48:49]

I don't understand this TODO.  The purpose of this part is to mark the
pre-colored register off-limits by marking that register's weight as infinite. 
A register's weight can never be more than infinite.

I wonder if this comment was meant for handleNoFreeRegisters()?

[John, 2015/09/03 22:38:24]

Misplaced TODO.

+        // larger) registers if its current weight is more than the new weight.
+        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");
+        }
       }
     }
   }
@@ -479,8 +498,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 +512,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 +525,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 +538,35 @@ 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));
+    RegWeight W;
+    const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+    for (int32_t RegNum = Aliases.find_first(); RegNum >= 0;
+         RegNum = Aliases.find_next(RegNum)) {
+      assert(Item->hasRegTmp());
+      RegWeight Tmp = Item->getWeight(Func);
+      if (W < Tmp)
+        W = Tmp;
+    }
+    Iter.Weights[Item->getRegNumTmp()].addWeight(W);

[Jim Stichnoth, 2015/09/03 17:48:49]

Should probably drop a TODO here about the fact that we need to consider whether
each alias gets the same weight increment.  (At least I don't think we've come
to a decision on that.)

[John, 2015/09/03 22:38:25]

Done.

   }
   // Same as above, but check Inactive ranges instead of Active.
   for (const Variable *Item : Inactive) {
-    int32_t RegNum = Item->getRegNumTmp();
-    assert(Item->hasRegTmp());
-    if (Item->rangeOverlaps(Iter.Cur))
-      Iter.Weights[RegNum].addWeight(Item->getWeight(Func));
+    bool HasWeight = false;
+    RegWeight W;
+    const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()];
+    for (int32_t RegNum = Aliases.find_first(); RegNum >= 0;
+         RegNum = Aliases.find_next(RegNum)) {
+      assert(Item->hasRegTmp());
+      if (Item->rangeOverlaps(Iter.Cur)) {
+        HasWeight = true;
+        RegWeight Tmp = Item->getWeight(Func);
+        if (W < Tmp)
+          W = Tmp;
+      }
+    }
+    if (HasWeight) {
+      Iter.Weights[Item->getRegNumTmp()].addWeight(W);
+    }
   }
 
   // All the weights are now calculated. Find the register with smallest
@@ -548,8 +598,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 Reg = Aliases.find_first(); Reg >= 0;
+             Reg = Aliases.find_next(Reg)) {
+          --RegUses[Reg];
+          assert(RegUses[Reg] >= 0);
+        }
         Item->setRegNumTmp(Variable::NoRegister);
         moveItem(Active, Index, Handled);
       }
@@ -574,8 +628,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 Reg = Aliases.find_first(); Reg >= 0;
+         Reg = Aliases.find_next(Reg)) {
+      assert(RegUses[Reg] >= 0);
+      ++RegUses[Reg];
+    }
     Active.push_back(Iter.Cur);
     dumpLiveRangeTrace("Allocating   ", Iter.Cur);
   }