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

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.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 207 matching lines @@
 }
 
 void LinearScan::init(RegAllocKind Kind) {
   this->Kind = Kind;
   Unhandled.clear();
   UnhandledPrecolored.clear();
   Handled.clear();
   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");
     break;
   case RAK_Global:
   case RAK_Phi:
     initForGlobal();
     break;
   case RAK_InfOnly:
     initForInfOnly();
@@ skipping 95 matching lines @@
       Moved = true;
     } else if (!Item->rangeOverlapsStart(Cur)) {
       // Move Item from Active to Inactive list.
       dumpLiveRangeTrace("Inactivating ", Cur);
       moveItem(Active, Index, Inactive);
       Moved = true;
     }
     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);
+      }
     }
   }
 }
 
 void LinearScan::handleInactiveRangeExpiredOrReactivated(const Variable *Cur) {
   for (SizeT I = Inactive.size(); I > 0; --I) {
     const SizeT Index = I - 1;
     Variable *Item = Inactive[Index];
     Item->trimLiveRange(Cur->getLiveRange().getStart());
     if (Item->rangeEndsBefore(Cur)) {
       // Move Item from Inactive to Handled list.
       dumpLiveRangeTrace("Expiring     ", Cur);
       moveItem(Inactive, Index, Handled);
     } else if (Item->rangeOverlapsStart(Cur)) {
       // Move Item from Inactive to Active list.
       dumpLiveRangeTrace("Reactivating ", 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];
+      }
     }
   }
 }
 
 // Infer register preference and allowable overlap. Only form a preference when
 // the current Variable has an unambiguous "first" definition. The preference
 // is some source Variable of the defining instruction that either is assigned
 // a register that is currently free, or that is assigned a register that is
 // not free but overlap is allowed. Overlap is allowed when the Variable under
 // consideration is single-definition, and its definition is a simple
@@ skipping 74 matching lines @@
 // overlaps with the current range, and set those registers to infinite weight
 // so that they aren't candidates for eviction.  Cur->rangeEndsBefore(Item) is
 // an early exit check that turns a guaranteed O(N^2) algorithm into expected
 // linear complexity.
 void LinearScan::filterFreeWithPrecoloredRanges(IterationState &Iter) {
   for (Variable *Item : reverse_range(UnhandledPrecolored)) {
     assert(Item->hasReg());
     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");
+        }
       }
     }
   }
 }
 
 void LinearScan::allocatePrecoloredRegister(Variable *Cur) {
   int32_t RegNum = Cur->getRegNum();
   // RegNumTmp should have already been set above.
   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();
 }
 
 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);
 }
 
 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);
 }
 
 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
   // weight.
   int32_t MinWeightIndex = Iter.RegMask.find_first();
   // MinWeightIndex must be valid because of the initial RegMask.any() test.
   assert(MinWeightIndex >= 0);
   for (SizeT i = MinWeightIndex + 1; i < Iter.Weights.size(); ++i) {
     if (Iter.RegMask[i] && Iter.Weights[i] < Iter.Weights[MinWeightIndex])
       MinWeightIndex = i;
@@ skipping 11 matching lines @@
                        "infinite-weight live range");
     }
   } else {
     // Evict all live ranges in Active that register number MinWeightIndex is
     // assigned to.
     for (SizeT I = Active.size(); I > 0; --I) {
       const SizeT Index = I - 1;
       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);
       }
     }
     // Do the same for Inactive.
     for (SizeT I = Inactive.size(); I > 0; --I) {
       const SizeT Index = I - 1;
       Variable *Item = Inactive[Index];
       // Note: The Item->rangeOverlaps(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->getRegNumTmp() == MinWeightIndex &&
           Item->rangeOverlaps(Iter.Cur)) {
         dumpLiveRangeTrace("Evicting     ", Item);
         Item->setRegNumTmp(Variable::NoRegister);
         moveItem(Inactive, Index, Handled);
       }
     }
     // 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);
   }
 }
 
 void LinearScan::assignFinalRegisters(
     const llvm::SmallBitVector &RegMaskFull,
     const llvm::SmallBitVector &PreDefinedRegisters, bool Randomized) {
   const size_t NumRegisters = RegMaskFull.size();
   llvm::SmallVector<int32_t, REGS_SIZE> Permutation(NumRegisters);
@@ skipping 239 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const Variable *Item : Inactive) {
     dumpLiveRange(Item, Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice