Subzero : Live Range Splitting after initial Register Allocation

src/IceTargetLowering.cpp

 //===- subzero/src/IceTargetLowering.cpp - Basic lowering implementation --===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief Implements the skeleton of the TargetLowering class.
 ///
 /// Specifically this invokes the appropriate lowering method for a given
 /// instruction kind and driving global register allocation. It also implements
 /// the non-deleted instruction iteration in LoweringContext.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "IceTargetLowering.h"
 
 #include "IceBitVector.h"
 #include "IceCfg.h" // setError()
 #include "IceCfgNode.h"
 #include "IceGlobalContext.h"
 #include "IceGlobalInits.h"
 #include "IceInstVarIter.h"
+#include "IceLiveness.h"
 #include "IceOperand.h"
 #include "IceRegAlloc.h"
 
 #include <string>
 #include <vector>
 
 #define TARGET_LOWERING_CLASS_FOR(t) Target_##t
 
 // We prevent target-specific implementation details from leaking outside their
 // implementations by forbidding #include of target-specific header files
@@ skipping 467 matching lines @@
     LinearScan.scan(RegMask, getFlags().getRandomizeRegisterAllocation());
     if (!LinearScan.hasEvictions())
       Repeat = false;
     Kind = RAK_SecondChance;
   } while (Repeat);
   // TODO(stichnot): Run the register allocator one more time to do stack slot
   // coalescing.  The idea would be to initialize the Unhandled list with the
   // set of Variables that have no register and a non-empty live range, and
   // model an infinite number of registers.  Maybe use the register aliasing
   // mechanism to get better packing of narrower slots.
+  if (getFlags().getSplitGlobalVars())
+    postRegallocSplitting(RegMask);
+}
+
+namespace {
+CfgVector<Inst *> getInstructionsInRange(CfgNode *Node, InstNumberT Start,
+                                         InstNumberT End) {
+  CfgVector<Inst *> Result;
+  bool Started = false;
+  auto Process = [&](InstList &Insts) {
+    for (auto &Instr : Insts) {
+      if (Instr.isDeleted()) {
+        continue;
+      }
+      if (Instr.getNumber() == Start) {
+        Started = true;
+      }
+      if (Started) {
+        Result.push_back(&Instr);

[Jim Stichnoth, 2016/08/02 05:57:50]

emplace_back ?

[manasijm, 2016/08/02 21:41:59]

Done.

+      }
+      if (Instr.getNumber() == End) {

[Jim Stichnoth, 2016/08/02 05:57:50]

Can this be ">=", just to be safe?  just in case the "End" instruction doesn't
actually exist, or is deleted

[manasijm, 2016/08/02 21:41:59]

That seems to result in missing a lot of opportunities. Added a comment.

+        break;
+      }
+    }
+  };
+  Process(Node->getPhis());
+  Process(Node->getInsts());
+  return Result;
+}
+}

[Jim Stichnoth, 2016/08/02 05:57:50]

add blank line afterwards

[manasijm, 2016/08/02 21:41:59]

Done.

+void TargetLowering::postRegallocSplitting(const SmallBitVector &RegMask) {
+  // Splits the live ranges of global(/multi block) variables and runs the
+  // register allocator to find registers for as many of the new variables as
+  // possible.
+  // TODO(manasijm): Merge the small liveranges back into multi-block ones when
+  // the variables get the same register. This will reduce the amount of new
+  // instructions inserted. This might involve a full dataflow analysis.
+  // Also, modify the preference mechanism in the register allocator to match.
+
+  TimerMarker _(TimerStack::TT_splitGlobalVars, Func);
+  CfgSet<Variable *> SplitCandidates;
+
+  // Find variables that does not have registers but are allowed to. Also skip

[Jim Stichnoth, 2016/08/02 05:57:50]

that do not

[manasijm, 2016/08/02 21:41:59]

Done.

+  // variables with single segment live ranges as they are not split further in
+  // this function.
+  for (Variable *Var : Func->getVariables()) {
+    if (!Var->mustNotHaveReg() && !Var->hasReg()) {
+      if (Var->getLiveRange().getNumSegments() > 1)
+        SplitCandidates.insert(Var);
+    }
+  }
+  if (SplitCandidates.empty())
+    return;
+
+  CfgSet<Variable *> ExtraVars;
+
+  struct UseInfo {
+    Variable *Replacing = nullptr;
+    Inst *FirstUse = nullptr;
+    Inst *LastDef = nullptr;
+    SizeT UseCount = 0;
+  };
+  CfgUnorderedMap<Variable *, UseInfo> VarInfo;
+  // Split the live ranges of the viable variables by node.
+  // Compute metadata (UseInfo) for each of the resulting variables.
+  for (auto *Var : SplitCandidates) {
+    for (auto &Segment : Var->getLiveRange().getSegments()) {
+      UseInfo Info;
+      Info.Replacing = Var;
+      auto *Node = Var->getLiveRange().getNodeForSegment(Segment.first);
+
+      for (auto *Instr :
+           getInstructionsInRange(Node, Segment.first, Segment.second)) {
+        for (SizeT i = 0; i < Instr->getSrcSize(); ++i) {
+          for (SizeT j = 0; j < Instr->getSrc(i)->getNumVars(); ++j) {

[Jim Stichnoth, 2016/08/02 05:57:50]

For local variable splitting, I made the assumption that any variables without a
register must appear as a top-level operand, i.e. the "for j" loop is not
needed.

You could do that here.  But if not, can you use the FOREACH_VAR_IN_INST macro?

[manasijm, 2016/08/02 21:41:59]

Done.

+            auto *Var = Instr->getSrc(i)->getVar(j);
+            if (Var == Info.Replacing) {
+              if (Info.FirstUse == nullptr && !llvm::isa<InstPhi>(Instr)) {
+                Info.FirstUse = Instr;
+              }
+              Info.UseCount++;
+            }
+          }
+        }
+        if (Instr->getDest() == Info.Replacing && !llvm::isa<InstPhi>(Instr)) {

[Jim Stichnoth, 2016/08/02 05:57:50]

It looks like Phi instructions are not considered for src operands or for the
dest variable, so can they be rejected in the loop over instructions?

However, I don't understand why they should be rejected when considering dest
variables.  Add a comment to describe?  Maybe a TODO if it's a mystery?

[manasijm, 2016/08/02 21:41:59]

Done.

[Jim Stichnoth, 2016/08/04 01:59:17]

I don't see any new comment or TODO on this issue?

+          Info.LastDef = Instr;
+        }
+      }
+
+      static constexpr SizeT MinUseThreshold = 3;
+      // Skip if variable has less than `MinUseThreshold` uses in the segment.
+      if (Info.UseCount < MinUseThreshold)
+        continue;
+
+      if (!Info.FirstUse && !Info.LastDef) {
+        continue;
+      }
+
+      LiveRange LR;
+      LR.addSegment(Segment);
+      Variable *NewVar = Func->makeVariable(Var->getType());
+
+      NewVar->setLiveRange(LR);
+
+      VarInfo[NewVar] = Info;
+
+      ExtraVars.insert(NewVar);
+    }
+  }
+  // Run the register allocator with all these new variables included
+  LinearScan RegAlloc(Func);
+  RegAlloc.init(RAK_Global, SplitCandidates);
+  RegAlloc.scan(RegMask, getFlags().getRandomizeRegisterAllocation());
+
+  // Modify the Cfg to use the new variables that now now have registers.

[Jim Stichnoth, 2016/08/02 05:57:50]

now now

[manasijm, 2016/08/02 21:41:59]

Done.

+  for (auto *ExtraVar : ExtraVars) {
+    if (!ExtraVar->hasReg()) {
+      continue;
+    }
+
+    auto &Info = VarInfo[ExtraVar];
+
+    assert(ExtraVar->getLiveRange().getSegments().size() == 1);
+    auto Segment = ExtraVar->getLiveRange().getSegments()[0];
+
+    auto *Node =
+        Info.Replacing->getLiveRange().getNodeForSegment(Segment.first);
+
+    auto RelevantInsts =
+        getInstructionsInRange(Node, Segment.first, Segment.second);
+
+    if (RelevantInsts.empty())
+      continue;
+
+    // Replace old variables
+    for (auto *Instr : RelevantInsts) {
+      if (llvm::isa<InstPhi>(Instr))
+        continue;
+      for (SizeT i = 0; i < Instr->getSrcSize(); ++i) {
+        // It's safe to iterate over the top-level src operands rather than
+        // using
+        // FOREACH_VAR_IN_INST(), because any variables inside e.g. mem operands
+        // should already have registers.
+        if (auto *Var = llvm::dyn_cast<Variable>(Instr->getSrc(i))) {
+          if (Var == Info.Replacing) {
+            Instr->replaceSource(i, ExtraVar);
+          }
+        }
+      }
+      if (Instr->getDest() == Info.Replacing) {
+        Instr->replaceDest(ExtraVar);
+      }
+    }
+
+    assert(Info.FirstUse != Info.LastDef);
+    assert(Info.FirstUse || Info.LastDef);
+
+    // Insert spill code
+    if (Info.FirstUse != nullptr) {
+      auto *NewInst =
+          Func->getTarget()->createLoweredMove(ExtraVar, Info.Replacing);
+      Node->getInsts().insert(instToIterator(Info.FirstUse), NewInst);
+    }
+    if (Info.LastDef != nullptr) {
+      auto *NewInst =
+          Func->getTarget()->createLoweredMove(Info.Replacing, ExtraVar);
+      Node->getInsts().insertAfter(instToIterator(Info.LastDef), NewInst);
+    }
+  }
 }
 
 void TargetLowering::markRedefinitions() {
   // Find (non-SSA) instructions where the Dest variable appears in some source
   // operand, and set the IsDestRedefined flag to keep liveness analysis
   // consistent.
   for (auto Instr = Context.getCur(), E = Context.getNext(); Instr != E;
        ++Instr) {
     if (Instr->isDeleted())
       continue;
@@ skipping 414 matching lines @@
   case TARGET_LOWERING_CLASS_FOR(X):                                           \
     return ::X::createTargetHeaderLowering(Ctx);
 #include "SZTargets.def"
 #undef SUBZERO_TARGET
   }
 }
 
 TargetHeaderLowering::~TargetHeaderLowering() = default;
 
 } // end of namespace Ice