Subzero: Cleanly implement register allocation after phi lowering.

src/IceRegAlloc.cpp

Index: src/IceRegAlloc.cpp
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index 400cb7de34095d1ea2ef72b7b32873ca2fcbe50c..7695cc5d03b48f751c68109834f4224964e26b4e 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -37,7 +37,7 @@ constexpr size_t REGS_SIZE = 32;
 // is with respect Cur.start.  Initial tests show no measurable
 // performance difference, so we'll keep the code simple for now.
 bool overlapsDefs(const Cfg *Func, const Variable *Item, const Variable *Var) {
-  const bool UseTrimmed = true;
+  constexpr bool UseTrimmed = true;
   VariablesMetadata *VMetadata = Func->getVMetadata();
   if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var))
     if (Item->getLiveRange().overlapsInst(FirstDef->getNumber(), UseTrimmed))
@@ -73,9 +73,8 @@ void dumpLiveRange(const Variable *Var, const Cfg *Func) {
   if (!BuildDefs::dump())
     return;
   Ostream &Str = Func->getContext()->getStrDump();
-  const static size_t BufLen = 30;
-  char buf[BufLen];
-  snprintf(buf, BufLen, "%2d", Var->getRegNumTmp());
+  char buf[30];
+  snprintf(buf, llvm::array_lengthof(buf), "%2d", Var->getRegNumTmp());
   Str << "R=" << buf << "  V=";

[jvoung (off chromium), 2015/07/24 19:43:08]

Could you just use std::to_string(Var->getRegNumTmp()) ?

[Jim Stichnoth, 2015/07/26 04:47:49]

That has the "%d" printf equivalent, as opposed to "%2d" above.  I found this
makes the register allocator's debugging output maximally aligned and easier to
read.

   Var->dump(Func);
   Str << "  Range=" << Var->getLiveRange();
@@ -88,7 +87,7 @@ void dumpLiveRange(const Variable *Var, const Cfg *Func) {
 void LinearScan::initForGlobal() {
   TimerMarker T(TimerStack::TT_initUnhandled, Func);
   FindPreference = true;
-  FindOverlap = true;
+  FindOverlap = (Kind != RAK_Phi);

[jvoung (off chromium), 2015/07/24 19:43:08]

Could you leave a comment about what FindOverlap is for (why leave out for
RAK_Phi)?

The IceOperand.h comment says "TODO(stichnot): We're not really using
FindOverlap yet, but we..." though it seems to matter?

[Jim Stichnoth, 2015/07/26 04:47:49]

Done.
I think what I meant by this comment is that it was always the case that
FindPreference==FindOverlap and so FindOverlap wasn't actually adding any
independent state over the FindPreference setting.

But since that's no longer true, I removed the comment.

   const VarList &Vars = Func->getVariables();
   Unhandled.reserve(Vars.size());
   UnhandledPrecolored.reserve(Vars.size());
@@ -103,6 +102,10 @@ void LinearScan::initForGlobal() {
     // it was never referenced.
     if (Var->getLiveRange().isEmpty())
       continue;
+    // Post phi lowering register allocation is only concerned with
+    // infinite-weight and pre-colored variables.

[jvoung (off chromium), 2015/07/24 19:43:08]

I'm not sure I understand the pre-colored part (there can be infinite-weight
temporaries that aren't pre-colored?)

[Jim Stichnoth, 2015/07/26 04:47:50]

This is terminology that I think is used consistently in the code base, but
could probably use some cleanup and clarification.

Pre-coloring is when a variable is assigned a specific register due to
instruction or ABI requirements.  Infinite-weight forces some physical register
without specifying which one.

Pre-coloring implies infinite-weight, but unfortunately Variable::RegNum and
Variable::Weight are unrelated in the code base, so they both have to be checked
together in several places in the code base.  (And to further complicate things,
there's also Variable::Live::Weight which could also be infinite.)

It would be good to make a pass over the register allocator and lowering and
anything else relevant and try to combine these checks into a single, well-named
predicate.

[jvoung (off chromium), 2015/07/27 22:28:15]

I think my confusion is with the term "and" in the comments, + demorgan's,
something like

if (... !(Var->hasReg() || Var->getWeight().isInf()))
  continue;

Seems more like "only concerned with infinite-weight or pre-colored variables" ?

On 2015/07/26 04:47:50, stichnot wrote:
Yes that might be good.

[Jim Stichnoth, 2015/07/30 07:22:18]

Ah, I see.  Done.

+    if (Kind == RAK_Phi && !Var->getWeight().isInf() && !Var->hasReg())
+      continue;
     Var->untrimLiveRange();
     Unhandled.push_back(Var);
     if (Var->hasReg()) {
@@ -114,6 +117,11 @@ void LinearScan::initForGlobal() {
 
   // Build the (ordered) list of FakeKill instruction numbers.
   Kills.clear();
+  // Phi lowering should not be creating new call instructions, so there should
+  // be no infinite-weight not-yet-colored live ranges that span a call
+  // instruction, hence no need to construct the Kills list.
+  if (Kind == RAK_Phi)
+    return;
   for (CfgNode *Node : Func->getNodes()) {
     for (Inst &I : Node->getInsts()) {
       if (auto Kill = llvm::dyn_cast<InstFakeKill>(&I)) {
@@ -196,7 +204,7 @@ void LinearScan::initForInfOnly() {
       assert(LREnd[i] != Inst::NumberSentinel);
       Unhandled.push_back(Var);
       Var->resetLiveRange();
-      const uint32_t WeightDelta = 1;
+      constexpr uint32_t WeightDelta = 1;
       Var->addLiveRange(LRBegin[i], LREnd[i], WeightDelta);
       Var->untrimLiveRange();
       if (Var->hasReg()) {
@@ -217,6 +225,7 @@ void LinearScan::initForInfOnly() {
 }
 
 void LinearScan::init(RegAllocKind Kind) {
+  this->Kind = Kind;
   Unhandled.clear();
   UnhandledPrecolored.clear();
   Handled.clear();
@@ -224,7 +233,11 @@ void LinearScan::init(RegAllocKind Kind) {
   Active.clear();
 
   switch (Kind) {
+  case RAK_Unknown:
+    llvm::report_fatal_error("Invalid RAK_Unknown");
+    break;
   case RAK_Global:
+  case RAK_Phi:
     initForGlobal();
     break;
   case RAK_InfOnly:
@@ -251,6 +264,76 @@ void LinearScan::init(RegAllocKind Kind) {
   Active.reserve(Unhandled.size());
 }
 
+// This is called when Cur must be allocated a register but no registers are
+// available across Cur's live range.  To handle this, we find a register that
+// is not explicitly used during Cur's live range, spill that register to a
+// stack location right before Cur's live range begins, and fill (reload) the
+// register from the stack location right after Cur's live range ends.
+void LinearScan::addSpillFill(Variable *Cur, llvm::SmallBitVector RegMask) {
+  // Identify the actual instructions that begin and end Cur's live range.
+  // Iterate through Cur's node's instruction list until we find the actual
+  // instructions with instruction numbers corresponding to Cur's recorded live
+  // range endpoints.  This sounds inefficient but shouldn't be a problem in
+  // practice because:
+  // (1) This function is almost never called in practice.
+  // (2) Since this register over-subscription problem happens only for
+  //     phi-lowered instructions, the number of instructions in the node is
+  //     proportional to the number of phi instructions in the original node,
+  //     which is never very large in practice.
+  // (3) We still have to iterate through all instructions of Cur's live range
+  //     to find all explicitly used registers (though the live range is usually
+  //     only 2-3 instructions), so the main cost that could be avoided would be
+  //     finding the instruction that begin's Cur's live range.
+  assert(!Cur->getLiveRange().isEmpty());
+  InstNumberT Start = Cur->getLiveRange().getStart();
+  InstNumberT End = Cur->getLiveRange().getEnd();
+  CfgNode *Node = Func->getVMetadata()->getLocalUseNode(Cur);
+  assert(Node);
+  InstList &Insts = Node->getInsts();
+  InstList::iterator SpillPoint = Insts.end();
+  InstList::iterator FillPoint = Insts.end();
+  // Stop searching after we have found both the SpillPoint and the FillPoint.
+  for (auto I = Insts.begin(), E = Insts.end();
+       I != E && (SpillPoint == E || FillPoint == E); ++I) {
+    if (I->getNumber() == Start)
+      SpillPoint = I;
+    if (I->getNumber() == End)
+      FillPoint = I;
+    if (SpillPoint != E) {
+      // Remove from RegMask any physical registers referenced during Cur's live
+      // range.  Start looking after SpillPoint gets set, i.e. once Cur's live
+      // range begins.
+      for (SizeT i = 0; i < I->getSrcSize(); ++i) {
+        Operand *Src = I->getSrc(i);
+        SizeT NumVars = Src->getNumVars();
+        for (SizeT j = 0; j < NumVars; ++j) {
+          const Variable *Var = Src->getVar(j);
+          if (Var->hasRegTmp())

[jvoung (off chromium), 2015/07/24 19:43:08]

This doesn't have to be concerned about Var->hasReg(), only RegTmp?

[Jim Stichnoth, 2015/07/26 04:47:49]

That's right.  In the register allocator design, allocation decisions are
provisionally stored in the RegNumTmp field but can be later revoked. 
initForGlobal() and initForInfOnly() initialize RegNumTmp based on RegNum for
pre-colored variables, and then the end of scan() commits the decisions from
RegNumTmp->RegNum.  So in keeping with the rest of the scan() implementation,
this code deals with RegNumTmp rather than RegNum.

+            RegMask[Var->getRegNumTmp()] = false;
+        }
+      }
+    }
+  }
+  assert(SpillPoint != Insts.end());
+  assert(FillPoint != Insts.end());
+  ++FillPoint;
+  // TODO(stichnot): Randomize instead of find_first().
+  int32_t RegNum = RegMask.find_first();
+  assert(RegNum != -1);
+  Cur->setRegNumTmp(RegNum);
+  TargetLowering *Target = Func->getTarget();
+  Variable *Preg = Target->getPhysicalRegister(RegNum, Cur->getType());

[jvoung (off chromium), 2015/07/24 19:43:08]

Should this SpillLoc type depend on Cur->getType() or the Target's stack slot
type?

[Jim Stichnoth, 2015/07/26 04:47:50]

I think Cur->getType() is right.  For example, on x86-32, if it's IceType_f64,
it should use a 64-bit stack slot, and if it's a vector type, it should use an
aligned 128-bit stack slot.  If the type width is narrower than a target stack
slot, some extra stack space is probably wasted.

FWIW, across spec2k, there are a handful of instances of i1/i8/i16/double, so I
assume it's working correctly. :)

+  // TODO(stichnot): Add SpillLoc to VariablesMetadata tracking so that SpillLoc
+  // is correctly identified as !isMultiBlock(), reducing stack frame size.
+  Variable *SpillLoc = Func->template makeVariable(Cur->getType());

[jvoung (off chromium), 2015/07/24 19:43:08]

does this need the Func->template ... ?

[Jim Stichnoth, 2015/07/26 04:47:50]

Done.  (guess I copied this from an older version of the lowering code)

+  // Add "reg=FakeDef;spill=reg" before SpillPoint
+  Target->lowerInst(Node, SpillPoint, InstFakeDef::create(Func, Preg));

[jvoung (off chromium), 2015/07/24 19:43:08]

Probably not too much, but Target->lowerInst() does end up doing
Context.init(Node); each time, though it's the same Node for all of these.

[Jim Stichnoth, 2015/07/26 04:47:50]

Yeah, my feeling was that addSpillFill() is invoked so very infrequently that it
was better to keep the design/implementation simple.

Added a TODO to the TargetLowering::lowerInst() definition.

+  Target->lowerInst(Node, SpillPoint, InstAssign::create(Func, SpillLoc, Preg));
+  // add "reg=spill;FakeUse(reg)" before FillPoint
+  Target->lowerInst(Node, FillPoint, InstAssign::create(Func, Preg, SpillLoc));
+  Target->lowerInst(Node, FillPoint, InstFakeUse::create(Func, Preg));
+}
+
 // Implements the linear-scan algorithm.  Based on "Linear Scan
 // Register Allocation in the Context of SSA Form and Register
 // Constraints" by Hanspeter Mössenböck and Michael Pfeiffer,
@@ -312,10 +395,10 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull,
         RegMaskFull & Func->getTarget()->getRegisterSetForType(Cur->getType());
     KillsRange.trim(Cur->getLiveRange().getStart());
 
-    // Check for precolored ranges.  If Cur is precolored, it
+    // Check for pre-colored ranges.  If Cur is pre-colored, it
     // definitely gets that register.  Previously processed live
     // ranges would have avoided that register due to it being
-    // precolored.  Future processed live ranges won't evict that
+    // pre-colored.  Future processed live ranges won't evict that
     // register because the live range has infinite weight.
     if (Cur->hasReg()) {
       int32_t RegNum = Cur->getRegNum();
@@ -501,7 +584,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull,
     llvm::SmallVector<RegWeight, REGS_SIZE> Weights(RegMask.size());
 
     // Remove registers from the Free[] list where an Unhandled
-    // precolored range overlaps with the current range, and set those
+    // pre-colored range 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
@@ -518,7 +601,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull,
         Free[ItemReg] = false;
         PrecoloredUnhandledMask[ItemReg] = true;
         // Disable AllowOverlap if the preferred register is one of
-        // these precolored unhandled overlapping ranges.
+        // these pre-colored unhandled overlapping ranges.
         if (AllowOverlap && ItemReg == PreferReg) {
           AllowOverlap = false;
           dumpDisableOverlap(Func, Item, "PrecoloredUnhandled");
@@ -528,7 +611,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull,
 
     // Remove scratch registers from the Free[] list, and mark their
     // Weights[] as infinite, if KillsRange overlaps Cur's live range.
-    const bool UseTrimmed = true;
+    constexpr bool UseTrimmed = true;
     if (Cur->getLiveRange().overlaps(KillsRange, UseTrimmed)) {
       Free.reset(KillsMask);
       for (int i = KillsMask.find_first(); i != -1;
@@ -615,8 +698,11 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull,
         // Handled state.
         Handled.push_back(Cur);
         if (Cur->getLiveRange().getWeight().isInf()) {
-          Func->setError("Unable to find a physical register for an "
-                         "infinite-weight live range");
+          if (Kind == RAK_Phi)
+            addSpillFill(Cur, RegMask);
+          else
+            Func->setError("Unable to find a physical register for an "
+                           "infinite-weight live range");
         }
       } else {
         // Evict all live ranges in Active that register number