Subzero : Live Range Splitting after initial Register Allocation

src/IceRegAlloc.cpp

Index: src/IceRegAlloc.cpp
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index 06631bfe2125b55d5f420bde7c2447cddea780d6..c308f0da918a0080d3f92fd4fc2b3152a93e7f5c 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -113,7 +113,6 @@ void LinearScan::initForGlobal() {
   // register allocation since no overlap opportunities should be available and
   // it's more expensive to look for opportunities.
   FindOverlap = (Kind != RAK_Phi);
-  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.
@@ -168,7 +167,6 @@ bool LinearScan::livenessValidateIntervals(
   if (!BuildDefs::dump())
     return false;
 
-  const VarList &Vars = Func->getVariables();
   OstreamLocker L(Ctx);
   Ostream &Str = Ctx->getStrDump();
   for (SizeT VarNum : DefsWithoutUses) {
@@ -212,7 +210,6 @@ void LinearScan::initForInfOnly() {
   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.
@@ -325,13 +322,22 @@ void LinearScan::initForSecondChance() {
   }
 }
 
-void LinearScan::init(RegAllocKind Kind) {
+void LinearScan::init(RegAllocKind Kind, CfgSet<Variable *> ExtraVars,
+                      CfgSet<Variable *> ExcludeVars) {
   this->Kind = Kind;
   Unhandled.clear();
   UnhandledPrecolored.clear();
   Handled.clear();
   Inactive.clear();
   Active.clear();
+  Vars.clear();

[Jim Stichnoth, 2016/07/29 17:04:07]

You may want to do something like:

  Vars.reserve(Func->getVariables().size() + ExtraVars.size());

Could also subtract ExcludeVars.size() if you're sure that ExcludeVars is a
subset of Func->getVariables().

[manasijm, 2016/08/01 22:20:04]

Done.

+  for (auto *Var : Func->getVariables()) {
+    if (ExcludeVars.find(Var) == ExcludeVars.end())

[Jim Stichnoth, 2016/07/29 17:04:07]

I haven't studied the code that manages ExtraVars and ExcludeVars, so I could be
off base here.

I can imagine why you want ExtraVars to be sorted, but it doesn't seem to be
necessary for ExcludeVars.  As such, if there are a lot of excluded vars, the
complexity here could be O(N log N) instead of O(N).

You could solve this by using an unordered_set, or by doing a "parallel"
iteration through the two sorted collections.  The parallel iteration code is
tricky - see for example LiveRange::overlaps() - so I would prefer the
unordered_set.

Using unordered_set means that ExtraVars and ExcludeVars no longer have the same
type, which is a bit sad.  However, maybe ExtraVars should be an unordered_set
as well?  Again, I haven't looked at the code yet that builds up ExtraVars, but
maybe they're already in sorted order and you could use a CfgVector?  If not,
they could be inserted during the initial phase into an unordered_set, then
sorted here before inserting.  See
http://llvm.org/docs/ProgrammersManual.html#a-sorted-vector , and also a use of
that pattern in CfgNode::livenessAddIntervals().

+      Vars.push_back(Var);

[Jim Stichnoth, 2016/07/29 17:04:07]

I think we prefer emplace_back() instead of push_back().

[manasijm, 2016/08/01 22:20:04]

Done.

+  }
+  for (auto *ExtraVar : ExtraVars) {

[Jim Stichnoth, 2016/07/29 17:04:07]

You might be able to do something more compact like this:

  Vars.insert(Vars.end(), ExtraVars.begin(), ExtraVars.end());

though it's also nice to have consistent structure with the previous loop.

[manasijm, 2016/08/01 22:20:04]

Acknowledged.

+    Vars.push_back(ExtraVar);
+  }
 
   SizeT NumRegs = Target->getNumRegisters();
   RegAliases.resize(NumRegs);
@@ -464,8 +470,13 @@ void LinearScan::handleActiveRangeExpiredOrInactive(const Variable *Cur) {
       assert(Item->hasRegTmp());
       const auto &Aliases = *RegAliases[Item->getRegNumTmp()];
       for (RegNumT RegAlias : RegNumBVIter(Aliases)) {
-        --RegUses[RegAlias];
-        assert(RegUses[RegAlias] >= 0);
+        if (SplittingMode) {
+          if (RegUses[RegAlias] > 0)

[Jim Stichnoth, 2016/07/29 17:04:07]

This seems really suspicious, and I can't work out why it shouldn't be an error.
 Do you have a good example?

[manasijm, 2016/08/01 22:20:04]

Should have removed it before submitting. Thanks

+            --RegUses[RegAlias];
+        } else {
+          --RegUses[RegAlias];
+          assert(RegUses[RegAlias] >= 0);
+        }
       }
     }
   }
@@ -962,7 +973,8 @@ void LinearScan::scan(const SmallBitVector &RegMaskFull, bool Randomized) {
     } else {
       // Fallback: there are no free registers, so we look for the lowest-weight
       // register and see if Cur has higher weight.
-      handleNoFreeRegisters(Iter);
+      if (!SplittingMode)

[manasijm, 2016/08/01 22:20:04]

This turned out to be unnecessary too.

+        handleNoFreeRegisters(Iter);
     }
     dump(Func);
   }