Subzero: Use the linear-scan register allocator for Om1 as well.

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.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the LinearScan class, which performs the
@@ skipping 55 matching lines @@
   const static size_t BufLen = 30;
   char buf[BufLen];
   snprintf(buf, BufLen, "%2d", Var->getRegNumTmp());
   Str << "R=" << buf << "  V=";
   Var->dump(Func);
   Str << "  Range=" << Var->getLiveRange();
 }
 
 } // end of anonymous namespace
 
-void LinearScan::initForGlobalAlloc() {
+// 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);
-  Unhandled.clear();
-  UnhandledPrecolored.clear();
-  Handled.clear();
-  Inactive.clear();
-  Active.clear();
+  FindPreference = true;
+  FindOverlap = true;
+  const VarList &Vars = Func->getVariables();
+  Unhandled.reserve(Vars.size());
   // Gather the live ranges of all variables and add them to the
   // Unhandled set.
-  const VarList &Vars = Func->getVariables();
-  Unhandled.reserve(Vars.size());
   for (Variable *Var : Vars) {
     // Explicitly don't consider zero-weight variables, which are
     // meant to be spill slots.
     if (Var->getWeight() == RegWeight::Zero)
       continue;
     // Don't bother if the variable has a null live range, which means
     // it was never referenced.
     if (Var->getLiveRange().isEmpty())
       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();
+  for (CfgNode *Node : Func->getNodes()) {
+    for (auto I = Node->getInsts().begin(), E = Node->getInsts().end(); I != E;
+         ++I) {
+      if (auto Kill = llvm::dyn_cast<InstFakeKill>(I)) {
+        if (!Kill->isDeleted() && !Kill->getLinked()->isDeleted())
+          Kills.push_back(I->getNumber());
+      }
+    }
+  }
+}
+
+// Prepare for very simple register allocation of only infinite-weight
+// Variables while respecting pre-colored Variables.  Some properties
+// we take advantage of:
+//
+// * Live ranges of interest consist of a single segment.
+//
+// * Live ranges of interest never span a call instruction.
+//
+// * Phi instructions are not considered because either phis have
+//   already been lowered, or they don't contain any pre-colored or
+//   infinite-weight Variables.
+//
+// * We don't need to renumber instructions before computing live
+//   ranges because all the high-level ICE instructions are deleted
+//   prior to lowering, and the low-level instructions are added in
+//   monotonically increasing order.
+//
+// * There are no opportunities for register preference or allowing
+//   overlap.
+//
+// Some properties we aren't (yet) taking advantage of:
+//
+// * Because live ranges are a single segment, the Unhandled set will
+//   always be empty, and the live range trimming operation is
+//   unnecessary.
+//
+// * Calculating overlap of single-segment live ranges could be
+//   optimized a bit.
+void LinearScan::initForInfOnly() {
+  TimerMarker T(TimerStack::TT_initUnhandled, Func);
+  FindPreference = false;
+  FindOverlap = false;
+  SizeT NumVars = 0;
+  const VarList &Vars = Func->getVariables();
+
+  // Iterate across all instructions and record the begin and end of
+  // the live range for each variable that is pre-colored or infinite
+  // weight.
+  std::vector<InstNumberT> LRBegin(Vars.size(), Inst::NumberSentinel);
+  std::vector<InstNumberT> LREnd(Vars.size(), Inst::NumberSentinel);
+  for (CfgNode *Node : Func->getNodes()) {
+    for (auto Inst = Node->getInsts().begin(), E = Node->getInsts().end();
+         Inst != E; ++Inst) {
+      if (Inst->isDeleted())
+        continue;
+      if (const Variable *Var = Inst->getDest()) {
+        if (Var->hasReg() || Var->getWeight() == RegWeight::Inf) {
+          if (LRBegin[Var->getIndex()] == Inst::NumberSentinel) {
+            LRBegin[Var->getIndex()] = Inst->getNumber();
+            ++NumVars;
+          }
+        }
+      }
+      for (SizeT I = 0; I < Inst->getSrcSize(); ++I) {
+        Operand *Src = Inst->getSrc(I);
+        SizeT NumVars = Src->getNumVars();
+        for (SizeT J = 0; J < NumVars; ++J) {
+          const Variable *Var = Src->getVar(J);
+          if (Var->hasReg() || Var->getWeight() == RegWeight::Inf)
+            LREnd[Var->getIndex()] = Inst->getNumber();
+        }
+      }
+    }
+  }
+
+  Unhandled.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;
+      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 considition, but it would be nice to

[jvoung (off chromium), 2014/11/14 23:26:22]

"considition -> condition"

[Jim Stichnoth, 2014/11/14 23:51:34]

Done.

+  // 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.

[jvoung (off chromium), 2014/11/14 23:26:22]

It might be nice to have a assert-level verifier pass at some point if this
becomes a problem, but yeah I don't see when that would happen w/ this.

[Jim Stichnoth, 2014/11/14 23:51:34]

Agreed.  Also to verify things like monotonically increasing instruction
numbers.

+  Kills.clear();
+}
+
+void LinearScan::init(RegAllocKind Kind) {
+  Unhandled.clear();
+  UnhandledPrecolored.clear();
+  Handled.clear();
+  Inactive.clear();
+  Active.clear();
+
+  switch (Kind) {
+  case RAK_Global:
+    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());
-
-  // Build the (ordered) list of FakeKill instruction numbers.
-  Kills.clear();
-  for (CfgNode *Node : Func->getNodes()) {
-    for (auto I = Node->getInsts().begin(), E = Node->getInsts().end(); I != E;
-         ++I) {
-      if (I->isDeleted())
-        continue;
-      if (auto Kill = llvm::dyn_cast<InstFakeKill>(I)) {
-        if (!Kill->getLinked()->isDeleted())
-          Kills.push_back(I->getNumber());
-      }
-    }
-  }
 }
 
 // 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.
 //
@@ skipping 144 matching lines @@
     // 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 assignment - i.e., the register gets copied/aliased
     // but is never modified.  Furthermore, overlap is only allowed
     // when preferred Variable definition instructions do not appear
     // within the current Variable's live range.
     Variable *Prefer = NULL;
     int32_t PreferReg = Variable::NoRegister;
     bool AllowOverlap = false;
-    if (const Inst *DefInst = VMetadata->getFirstDefinition(Cur)) {
-      assert(DefInst->getDest() == Cur);
-      bool IsAssign = DefInst->isSimpleAssign();
-      bool IsSingleDef = !VMetadata->isMultiDef(Cur);
-      for (SizeT i = 0; i < DefInst->getSrcSize(); ++i) {
-        // TODO(stichnot): Iterate through the actual Variables of the
-        // instruction, not just the source operands.  This could
-        // capture Load instructions, including address mode
-        // optimization, for Prefer (but not for AllowOverlap).
-        if (Variable *SrcVar = llvm::dyn_cast<Variable>(DefInst->getSrc(i))) {
-          int32_t SrcReg = SrcVar->getRegNumTmp();
-          // Only consider source variables that have (so far) been
-          // assigned a register.  That register must be one in the
-          // RegMask set, e.g. don't try to prefer the stack pointer
-          // as a result of the stacksave intrinsic.
-          if (SrcVar->hasRegTmp() && RegMask[SrcReg]) {
-            if (!Free[SrcReg]) {
-              // Don't bother trying to enable AllowOverlap if the
-              // register is already free.
-              AllowOverlap =
-                  IsSingleDef && IsAssign && !overlapsDefs(Func, Cur, SrcVar);
-            }
-            if (AllowOverlap || Free[SrcReg]) {
-              Prefer = SrcVar;
-              PreferReg = SrcReg;
+    if (FindPreference) {
+      if (const Inst *DefInst = VMetadata->getFirstDefinition(Cur)) {
+        assert(DefInst->getDest() == Cur);
+        bool IsAssign = DefInst->isSimpleAssign();
+        bool IsSingleDef = !VMetadata->isMultiDef(Cur);
+        for (SizeT i = 0; i < DefInst->getSrcSize(); ++i) {
+          // TODO(stichnot): Iterate through the actual Variables of the
+          // instruction, not just the source operands.  This could
+          // capture Load instructions, including address mode
+          // optimization, for Prefer (but not for AllowOverlap).
+          if (Variable *SrcVar = llvm::dyn_cast<Variable>(DefInst->getSrc(i))) {
+            int32_t SrcReg = SrcVar->getRegNumTmp();
+            // Only consider source variables that have (so far) been
+            // assigned a register.  That register must be one in the
+            // RegMask set, e.g. don't try to prefer the stack pointer
+            // as a result of the stacksave intrinsic.
+            if (SrcVar->hasRegTmp() && RegMask[SrcReg]) {
+              if (FindOverlap && !Free[SrcReg]) {
+                // Don't bother trying to enable AllowOverlap if the
+                // register is already free.
+                AllowOverlap =
+                    IsSingleDef && IsAssign && !overlapsDefs(Func, Cur, SrcVar);
+              }
+              if (AllowOverlap || Free[SrcReg]) {
+                Prefer = SrcVar;
+                PreferReg = SrcReg;
+              }
             }
           }
         }
-      }
-    }
-    if (Verbose) {
-      if (Prefer) {
-        Str << "Initial Prefer=" << *Prefer << " R=" << PreferReg
-            << " LIVE=" << Prefer->getLiveRange() << " Overlap=" << AllowOverlap
-            << "\n";
+        if (Verbose && Prefer) {
+          Str << "Initial Prefer=" << *Prefer << " R=" << PreferReg
+              << " LIVE=" << Prefer->getLiveRange()
+              << " Overlap=" << AllowOverlap << "\n";
+        }
       }
     }
 
     // Remove registers from the Free[] list where an Inactive range
     // overlaps with the current range.
     for (const Variable *Item : Inactive) {
       if (Item->rangeOverlaps(Cur)) {
         int32_t RegNum = Item->getRegNumTmp();
         // Don't assert(Free[RegNum]) because in theory (though
         // probably never in practice) there could be two inactive
         // variables that were marked with AllowOverlap.
         Free[RegNum] = false;
         // Disable AllowOverlap if an Inactive variable, which is not
         // Prefer, shares Prefer's register, and has a definition
         // within Cur's live range.
         if (AllowOverlap && Item != Prefer && RegNum == PreferReg &&
             overlapsDefs(Func, Cur, Item)) {
           AllowOverlap = false;
           dumpDisableOverlap(Func, Item, "Inactive");
         }
       }
     }
 
     // Disable AllowOverlap if an Active variable, which is not
     // Prefer, shares Prefer's register, and has a definition within
     // Cur's live range.
-    for (const Variable *Item : Active) {
-      int32_t RegNum = Item->getRegNumTmp();
-      if (Item != Prefer && RegNum == PreferReg &&
-          overlapsDefs(Func, Cur, Item)) {
-        AllowOverlap = false;
-        dumpDisableOverlap(Func, Item, "Active");
+    if (AllowOverlap) {
+      for (const Variable *Item : Active) {
+        int32_t RegNum = Item->getRegNumTmp();
+        if (Item != Prefer && RegNum == PreferReg &&
+            overlapsDefs(Func, Cur, Item)) {
+          AllowOverlap = false;
+          dumpDisableOverlap(Func, Item, "Active");
+        }
       }
     }
 
     std::vector<RegWeight> Weights(RegMask.size());
 
     // Remove registers from the Free[] list where an Unhandled
     // precolored 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
@@ skipping 231 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const Variable *Item : Inactive) {
     dumpLiveRange(Item, Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice