Subzero : Live Range Splitting after initial Register Allocation

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 95 matching lines @@
 // analysis to have calculated live ranges.
 void LinearScan::initForGlobal() {
   TimerMarker T(TimerStack::TT_initUnhandled, Func);
   FindPreference = true;
   // For full register allocation, normally we want to enable FindOverlap
   // (meaning we look for opportunities for two overlapping live ranges to
   // safely share the same register). However, we disable it for phi-lowering
   // 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.
   for (Variable *Var : Vars) {
     // Don't consider rematerializable variables.
     if (Var->isRematerializable())
       continue;
     // Explicitly don't consider zero-weight variables, which are meant to be
     // spill slots.
     if (Var->mustNotHaveReg())
@@ skipping 34 matching lines @@
     const DefUseErrorList &DefsWithoutUses,
     const DefUseErrorList &UsesBeforeDefs,
     const CfgVector<InstNumberT> &LRBegin,
     const CfgVector<InstNumberT> &LREnd) const {
   if (DefsWithoutUses.empty() && UsesBeforeDefs.empty())
     return true;
 
   if (!BuildDefs::dump())
     return false;
 
-  const VarList &Vars = Func->getVariables();
   OstreamLocker L(Ctx);
   Ostream &Str = Ctx->getStrDump();
   for (SizeT VarNum : DefsWithoutUses) {
     Variable *Var = Vars[VarNum];
     Str << "LR def without use, instruction " << LRBegin[VarNum]
         << ", variable " << Var->getName() << "\n";
   }
   for (SizeT VarNum : UsesBeforeDefs) {
     Variable *Var = Vars[VarNum];
     Str << "LR use before def, instruction " << LREnd[VarNum] << ", variable "
@@ skipping 23 matching lines @@
 //
 // * Because live ranges are a single segment, the Inactive 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.
   CfgVector<InstNumberT> LRBegin(Vars.size(), Inst::NumberSentinel);
   CfgVector<InstNumberT> LREnd(Vars.size(), Inst::NumberSentinel);
   DefUseErrorList DefsWithoutUses, UsesBeforeDefs;
   for (CfgNode *Node : Func->getNodes()) {
     for (Inst &Instr : Node->getInsts()) {
       if (Instr.isDeleted())
         continue;
@@ skipping 92 matching lines @@
       UnhandledPrecolored.push_back(Var);
       Unhandled.push_back(Var);
     }
   }
   for (Variable *Var : Evicted) {
     Var->untrimLiveRange();
     Unhandled.push_back(Var);
   }
 }
 
-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);
   for (SizeT Reg = 0; Reg < NumRegs; ++Reg) {
     RegAliases[Reg] = &Target->getAliasesForRegister(RegNumT::fromInt(Reg));
   }
 
   switch (Kind) {
   case RAK_Unknown:
     llvm::report_fatal_error("Invalid RAK_Unknown");
@@ skipping 112 matching lines @@
       // Move Item from Active to Inactive list.
       dumpLiveRangeTrace("Inactivating ", Item);
       moveItem(Active, Index, Inactive);
       Moved = true;
     }
     if (Moved) {
       // Decrement Item from RegUses[].
       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);
+        }
       }
     }
   }
 }
 
 void LinearScan::handleInactiveRangeExpiredOrReactivated(const Variable *Cur) {
   for (SizeT I = Inactive.size(); I > 0; --I) {
     const SizeT Index = I - 1;
     Variable *Item = Inactive[Index];
     Item->trimLiveRange(Cur->getLiveRange().getStart());
@@ skipping 476 matching lines @@
       // First choice: a preferred register that is either free or is allowed to
       // overlap with its linked variable.
       allocatePreferredRegister(Iter);
     } else if (Iter.Free.any()) {
       // Second choice: any free register.
       constexpr bool Filtered = true;
       allocateFreeRegister(Iter, Filtered);
     } 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);
   }
 
   // Move anything Active or Inactive to Handled for easier handling.
   Handled.insert(Handled.end(), Active.begin(), Active.end());
   Active.clear();
   Handled.insert(Handled.end(), Inactive.begin(), Inactive.end());
   Inactive.clear();
   dump(Func);
@@ skipping 42 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const Variable *Item : Inactive) {
     dumpLiveRange(Item, Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice