Subzero: Automatically infer regalloc preferences and overlap.

src/IceRegAlloc.cpp

Index: src/IceRegAlloc.cpp
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index f79e8dcc7be4565327188990f51cd72a1a22f09a..bc1bf4f01436566a15b9a4923c8f2583f5283eea 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -21,6 +21,22 @@
 
 namespace Ice {
 
+namespace {
+
+// Returns true if Var has any definitions within Item's live range.
+bool overlapsDefs(const Cfg *Func, const LiveRangeWrapper &Item,
+                  const Variable *Var) {
+  VariablesMetadata *VMetadata = Func->getVMetadata();
+  const InstDefList &Defs = VMetadata->getDefinitions(Var);
+  for (size_t i = 0; i < Defs.size(); ++i) {
+    if (Item.range().overlaps(Defs[i]->getNumber()))
+      return true;
+  }
+  return false;
+}
+
+} // end of anonymous namespace
+
 // 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,
@@ -40,6 +56,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
   Active.clear();
   Ostream &Str = Func->getContext()->getStrDump();
   Func->resetCurrentNode();
+  VariablesMetadata *VMetadata = Func->getVMetadata();
 
   // Gather the live ranges of all variables and add them to the
   // Unhandled set.  TODO: Unhandled is a set<> which is based on a
@@ -185,6 +202,47 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
         Free[i] = false;
     }
 
+    // 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 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;
+    bool AllowedToOverlap = false;
+    if (const Inst *DefInst = VMetadata->getSingleDefinition(Cur.Var)) {

[jvoung (off chromium), 2014/09/25 16:42:11]

Was this meant to be getFirstDefinition() (based on the above comment "has an
unambiguous "first" defining instruction).

On the other hand, the check below requires Cur.Var to be singledef.

[Jim Stichnoth, 2014/09/25 18:13:55]

Yeah, fixed.
 
The Overlap check requires single-def, but not for the Prefer hint.

+      assert(DefInst->getDest() == Cur.Var);
+      bool IsAssign = DefInst->isSimpleAssign();
+      bool IsSingleDef = !VMetadata->isMultiDef(Cur.Var);
+      for (SizeT i = 0; i < DefInst->getSrcSize(); ++i) {
+        if (Variable *SrcVar = llvm::dyn_cast<Variable>(DefInst->getSrc(i))) {
+          // The NoConflictingDefs condition is supposed to accurately
+          // represent this requirement: "overlap is only allowed when
+          // preferred Variable definition instructions do not appear
+          // within the current Variable's live range."
+          bool NoConflictingDefs = !overlapsDefs(Func, Cur, SrcVar);
+          int32_t SrcReg = SrcVar->getRegNumTmp();
+          if (SrcReg != Variable::NoRegister && RegMask[SrcReg]) {

[jvoung (off chromium), 2014/09/25 16:42:11]

Would it be better to check SrcReg != Variable::NoRegister && RegMask[SrcReg]
first, before calling overlapsDefs()? Seems like it could be cheaper.

[Jim Stichnoth, 2014/09/25 18:13:55]

Yes.  That should be fixed in the latest patchset.

+            AllowedToOverlap = IsSingleDef && NoConflictingDefs && IsAssign;
+            if (AllowedToOverlap || Free[SrcReg])

[jvoung (off chromium), 2014/09/25 16:42:11]

Similar, would it be cheaper to check for Free[SrcReg] earlier, before calling
overlapsDefs to determine AllowedToOverlap?

[Jim Stichnoth, 2014/09/25 18:13:55]

Hmm, I think you're right.  The logs do show a lot of cases where Overlap is set
to true yet the variable is listed as free.  Changed.

+              Prefer = SrcVar;
+          }
+        }
+      }
+    }
+    if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+      if (Prefer) {
+        Str << "Initial Prefer=" << *Prefer << " R=" << Prefer->getRegNumTmp()
+            << " LIVE=" << Prefer->getLiveRange()
+            << " Overlap=" << AllowedToOverlap << "\n";
+      }
+    }
+
     // Remove registers from the Free[] list where an Inactive range
     // overlaps with the current range.
     for (UnorderedRanges::const_iterator I = Inactive.begin(),
@@ -198,6 +256,40 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
         // variables that were allowed marked with
         // AllowRegisterOverlap.
         Free[RegNum] = false;
+        // If there is a variable on the inactive list, which is not
+        // Prefer, and overlaps with Cur, and shares Prefer's
+        // register, then disallow overlap.
+        if (AllowedToOverlap && Item.Var != Prefer &&
+            RegNum == Prefer->getRegNumTmp() && Item.overlaps(Cur)) {
+          AllowedToOverlap = false;
+          if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+            Str << "Disabling Overlap due to Inactive " << *Item.Var
+                << " LIVE=" << Item.Var->getLiveRange() << "\n";
+          }
+        }
+      }
+    }
+
+    // Disable AllowOverlap if the preferred register is already used
+    // in an Active range (which by definition overlaps) that is not
+    // Prefer.  TODO(stichnot): Actually only disable AllowOverlap if
+    // an Active variable with the preferred register has a definition
+    // within the current variable's live range.
+
+    // If there is a variable on the active list, which is not Prefer,
+    // and shares Prefer's register, and has a definition within Cur's
+    // live range, then disallow overlap.
+    for (UnorderedRanges::iterator I = Active.begin(), E = Active.end();
+         AllowedToOverlap && I != E; ++I) {
+      LiveRangeWrapper Item = *I;
+      int32_t RegNum = Item.Var->getRegNumTmp();
+      if (Item.Var != Prefer && RegNum == Prefer->getRegNumTmp() &&
+          overlapsDefs(Func, Cur, Item.Var)) {
+        AllowedToOverlap = false;
+        if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+          Str << "Disabling Overlap due to Active " << *Item.Var
+              << " LIVE=" << Item.Var->getLiveRange() << "\n";
+        }
       }
     }
 
@@ -213,6 +305,17 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
       if (Item.Var->hasReg() && Item.overlaps(Cur)) {
         Free[Item.Var->getRegNum()] = false; // Note: getRegNum not getRegNumTmp
         PrecoloredUnhandled[Item.Var->getRegNum()] = true;
+        // Disallow overlap if the preferred register is one of these
+        // precolored unhandled overlapping ranges.
+        if (AllowedToOverlap && Prefer &&

[jvoung (off chromium), 2014/09/25 16:42:11]

nit: I think technically, the "&& Prefer" check isn't needed after checking
AllowedToOverlap -- otherwise, some of the loops above seem to assume that
AllowedToOverlap => Prefer != NULL.

Also, Item.overlaps(Cur) so Cur.overlaps(Item) shouldn't be needed either?

[Jim Stichnoth, 2014/09/25 18:13:54]

Done.  I think I originally had that just to be absolutely sure the following
Prefer->getRegNumTmp() wasn't a null pointer dereference, but I've changed that
to use PreferReg so that issue is gone.
Nice, done.

+            Item.Var->getRegNum() == Prefer->getRegNumTmp() &&
+            Cur.overlaps(Item)) {
+          AllowedToOverlap = false;
+          if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+            Str << "Disabling Overlap due to UnhandledPrecolored " << *Item.Var
+                << " LIVE=" << Item.Var->getLiveRange() << "\n";
+          }
+        }
       }
     }
 
@@ -228,13 +331,9 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
       Str << "\n";
     }
 
-    Variable *Prefer = Cur.Var->getPreferredRegister();
-    int32_t PreferReg = Prefer && Prefer->hasRegTmp() ? Prefer->getRegNumTmp()
-                                                      : Variable::NoRegister;
-    bool AllowedToOverlap = Cur.Var->getRegisterOverlap() &&
-                            PreferReg != Variable::NoRegister &&
-                            RegMask[PreferReg] &&
-                            !PrecoloredUnhandled[PreferReg];

[jvoung (off chromium), 2014/09/25 16:42:11]

It now seems like PrecoloredUnhandled is no longer read (except in the debug
printing)?

[Jim Stichnoth, 2014/09/25 18:13:54]

True.  It's worth keeping for the diagnostics, so I added a comment.

+    int32_t PreferReg = Variable::NoRegister;
+    if (Prefer && Prefer->hasRegTmp())
+      PreferReg = Prefer->getRegNumTmp();
     if (PreferReg != Variable::NoRegister &&
         (AllowedToOverlap || Free[PreferReg])) {
       // First choice: a preferred register that is either free or is