Subzero: Cleanly implement register allocation after phi lowering.

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 19 matching lines @@
 // being compiled.
 constexpr size_t REGS_SIZE = 32;
 
 // Returns true if Var has any definitions within Item's live range.
 // TODO(stichnot): Consider trimming the Definitions list similar to
 // how the live ranges are trimmed, since all the overlapsDefs() tests
 // are whether some variable's definitions overlap Cur, and trimming
 // 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))
       return true;
   const InstDefList &Defs = VMetadata->getLatterDefinitions(Var);
   for (size_t i = 0; i < Defs.size(); ++i) {
     if (Item->getLiveRange().overlapsInst(Defs[i]->getNumber(), UseTrimmed))
       return true;
   }
   return false;
@@ skipping 15 matching lines @@
       Str << "," << Defs[i]->getNumber();
     }
     Str << "\n";
   }
 }
 
 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();
 }
 
 } // end of anonymous namespace
 
 // Prepare for full register allocation of all variables.  We depend
 // on liveness analysis to have calculated live ranges.
 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());
   // Gather the live ranges of all variables and add them to the
   // Unhandled set.
   for (Variable *Var : Vars) {
     // Explicitly don't consider zero-weight variables, which are
     // meant to be spill slots.
     if (Var->getWeight().isZero())
       continue;
     // Don't bother if the variable has a null live range, which means
     // 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()) {
       Var->setRegNumTmp(Var->getRegNum());
       Var->setLiveRangeInfiniteWeight();
       UnhandledPrecolored.push_back(Var);
     }
   }
 
   // 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)) {
         if (!Kill->isDeleted() && !Kill->getLinked()->isDeleted())
           Kills.push_back(I.getNumber());
       }
     }
   }
 }
 
@@ skipping 62 matching lines @@
   }
 
   Unhandled.reserve(NumVars);
   UnhandledPrecolored.reserve(NumVars);
   for (SizeT i = 0; i < Vars.size(); ++i) {
     Variable *Var = Vars[i];
     if (LRBegin[i] != Inst::NumberSentinel) {
       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()) {
         Var->setRegNumTmp(Var->getRegNum());
         Var->setLiveRangeInfiniteWeight();
         UnhandledPrecolored.push_back(Var);
       }
       --NumVars;
     }
   }
   // This isn't actually a fatal condition, but it would be nice to
   // know if we somehow pre-calculated Unhandled's size wrong.
   assert(NumVars == 0);
 
   // Don't build up the list of Kills because we know that no
   // infinite-weight Variable has a live range spanning a call.
   Kills.clear();
 }
 
 void LinearScan::init(RegAllocKind Kind) {
+  this->Kind = Kind;
   Unhandled.clear();
   UnhandledPrecolored.clear();
   Handled.clear();
   Inactive.clear();
   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:
     initForInfOnly();
     break;
   }
 
   struct CompareRanges {
     bool operator()(const Variable *L, const Variable *R) {
       InstNumberT Lstart = L->getLiveRange().getStart();
       InstNumberT Rstart = R->getLiveRange().getStart();
       if (Lstart == Rstart)
         return L->getIndex() < R->getIndex();
       return Lstart < Rstart;
     }
   };
   // Do a reverse sort so that erasing elements (from the end) is fast.
   std::sort(Unhandled.rbegin(), Unhandled.rend(), CompareRanges());
   std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(),
             CompareRanges());
 
   Handled.reserve(Unhandled.size());
   Inactive.reserve(Unhandled.size());
   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,
 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF .  This
 // implementation is modified to take affinity into account and allow
 // two interfering variables to share the same register in certain
 // cases.
 //
 // Requires running Cfg::liveness(Liveness_Intervals) in
 // preparation.  Results are assigned to Variable::RegNum for each
@@ skipping 41 matching lines @@
     if (Verbose) {
       Ostream &Str = Ctx->getStrDump();
       Str << "\nConsidering  ";
       dumpLiveRange(Cur, Func);
       Str << "\n";
     }
     const llvm::SmallBitVector RegMask =
         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();
       // RegNumTmp should have already been set above.
       assert(Cur->getRegNumTmp() == RegNum);
       if (Verbose) {
         Ostream &Str = Ctx->getStrDump();
         Str << "Precoloring  ";
         dumpLiveRange(Cur, Func);
         Str << "\n";
@@ skipping 165 matching lines @@
             overlapsDefs(Func, Cur, Item)) {
           AllowOverlap = false;
           dumpDisableOverlap(Func, Item, "Active");
         }
       }
     }
 
     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
     // complexity.
     llvm::SmallBitVector PrecoloredUnhandledMask(RegMask.size());
     // Note: PrecoloredUnhandledMask is only used for dumping.
     for (Variable *Item : reverse_range(UnhandledPrecolored)) {
       assert(Item->hasReg());
       if (Cur->rangeEndsBefore(Item))
         break;
       if (Item->rangeOverlaps(Cur)) {
         int32_t ItemReg = Item->getRegNum(); // Note: not getRegNumTmp()
         Weights[ItemReg].setWeight(RegWeight::Inf);
         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");
         }
       }
     }
 
     // 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;
            i = KillsMask.find_next(i)) {
         Weights[i].setWeight(RegWeight::Inf);
         if (PreferReg == i)
           AllowOverlap = false;
       }
     }
 
@@ skipping 66 matching lines @@
         if (RegMask[i] && Weights[i] < Weights[MinWeightIndex])
           MinWeightIndex = i;
       }
 
       if (Cur->getLiveRange().getWeight() <= Weights[MinWeightIndex]) {
         // Cur doesn't have priority over any other live ranges, so
         // don't allocate any register to it, and move it to the
         // 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
         // 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) {
             if (Verbose) {
               Ostream &Str = Ctx->getStrDump();
@@ skipping 130 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const Variable *Item : Inactive) {
     dumpLiveRange(Item, Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice