Subzero : Live Range Splitting after initial Register Allocation

src/IceTargetLowering.cpp

Index: src/IceTargetLowering.cpp
diff --git a/src/IceTargetLowering.cpp b/src/IceTargetLowering.cpp
index 1b9ca23bfe49eb96b1bc0dcc5ad38d72965c9adf..c4f3336c25329bc5c253ce0bf15c6dd2d75061cf 100644
--- a/src/IceTargetLowering.cpp
+++ b/src/IceTargetLowering.cpp
@@ -26,6 +26,7 @@
 #include "IceInstVarIter.h"
 #include "IceOperand.h"
 #include "IceRegAlloc.h"
+#include "IceLiveness.h"

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

sort

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

Done.

 
 #include <string>
 #include <vector>
@@ -511,6 +512,156 @@ void TargetLowering::regAlloc(RegAllocKind Kind) {
   // 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().getGlobalSplitting())
+    postRegallocSplitting(LinearScan, RegMask);
+}

[Jim Stichnoth, 2016/07/29 19:14:31]

blank line after this

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

Done.

+namespace {
+CfgVector<Inst *> GetInstructionsInRange(CfgNode *Node, InstNumberT Start,

[Jim Stichnoth, 2016/07/29 19:14:31]

Does this function assume that instruction numbers are monotonically increasing?
 such as the case after renumbering.

If so, I would make a few changes:

1. Document this.

2. Add an assert as instructions are processed to validate this.

3. Use the standard "if (Instr.isDeleted()) continue;" at the start of the loop
body.

4. Change the "== End" comparison in the loop to ">= End", and maybe move that
test to the top of the loop body.

[Jim Stichnoth, 2016/07/29 19:14:31]

lowercase getInstructionsInRange per coding style

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

Done.

+                                         InstNumberT End) {
+  CfgVector<Inst *> Result;
+  bool Started = false;
+  auto Process = [&](InstList &Insts) {
+    for (auto &Inst : Insts) {

[Jim Stichnoth, 2016/07/29 19:14:32]

Name this Instr instead of Inst which is a type name.

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

Done.

+      if (!Started) {

[Jim Stichnoth, 2016/07/29 19:14:31]

Restructure as "if (Started) ... else ..."

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

Acknowledged.

+        if (Inst.getNumber() == Start) {
+          if (!Inst.isDeleted()) {
+            Result.push_back(&Inst);
+          }
+          Started = true;
+        } else {

[Jim Stichnoth, 2016/07/29 19:14:31]

Is the "else continue" necessary?  It doesn't look like there's any code left in
the loop body to execute.

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

Acknowledged.

+          continue;
+        }
+      } else {
+        if (Inst.getNumber() == End) {
+          break;
+        } else {
+          if (!Inst.isDeleted()) {
+            Result.push_back(&Inst);
+          }
+        }
+      }
+    }
+  };
+  Process(Node->getPhis());
+  Process(Node->getInsts());
+  return Result;
+}
+}
+void TargetLowering::postRegallocSplitting(LinearScan &RegAllocator,

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

These days we avoid passing by non-const ref, so make this "LinearScan
*RegAllocator".

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

Not passing a LinearScan object anymore.

+                                           const SmallBitVector &RegMask) {
+  TimerMarker T(TimerStack::TT_globalSplitting, Func->getContext());

[Jim Stichnoth, 2016/07/29 19:14:31]

Newer Subzero style is to name this "_" instead of "T" (assuming there isn't
already an RAII variable named "_").

Also, use the ctor that takes a Cfg rather than GlobalContext pointer.

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

Done.

+  CfgSet<Variable *> SplitCandidates;
+  for (Variable *Var : Func->getVariables()) {

[Jim Stichnoth, 2016/07/29 19:14:31]

Please add some documentation in the code as to what's going on.  It doesn't
have to be excessive, but at least describe each of the 3 top-level loops.

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

Done.

+    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;
+  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)) {

[Jim Stichnoth, 2016/07/29 19:14:32]

(This might be too much to ask for an initial feature that is behind a flag, so
at the very least document it with a TODO.)

I suspect a lot of time (and memory) is spent copying instruction ranges into
vectors of instruction pointers.  Could you instead return begin and end
iterators?  Since instruction ranges come from getPhis() and getInsts(), you
would probably want an iterator wrapper that allows you to iterate over phis and
insts sequentially and transparently.  (Such an iterator would be nice in a
couple other places that iterate identically over both lists.)

I suppose this could break down or be tricky if you need to add new instructions
while you iterate.

In this case, the handful (I suppose) of new instructions could be added at the
end after the iteration has completed.

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

Acknowledged.

+        for (SizeT i = 0; i < Instr->getSrcSize(); ++i) {
+          for (SizeT j = 0; j < Instr->getSrc(i)->getNumVars(); ++j) {
+            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)) {
+          Info.LastDef = Instr;
+        }
+      }
+      if (Info.UseCount < 3)

[Jim Stichnoth, 2016/07/29 19:14:31]

Use a static constexpr variable to self-document this magic constant.

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

Done.

+        continue;
+
+      if (!Info.FirstUse && !Info.LastDef) {
+        continue;
+      }
+
+      LiveRange LR;
+      LR.addSegment(Segment);
+      Variable *NewVar = Variable::create(
+          Func, Var->getType(), Func->getNumVariables() + ExtraVars.size());
+      NewVar->setLiveRange(LR);
+
+      VarInfo[NewVar] = Info;
+
+      ExtraVars.insert(NewVar);
+    }
+  }
+  RegAllocator.init(RAK_Global, ExtraVars, SplitCandidates);
+  RegAllocator.setSplittingMode();
+  RegAllocator.scan(RegMask, getFlags().getRandomizeRegisterAllocation());
+
+  for (auto *ExtraVar : ExtraVars) {
+    if (ExtraVar->hasReg()) {

[Jim Stichnoth, 2016/07/29 19:14:31]

how about:

  if (!ExtraVar->hasReg())
    continue;

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

Done.

+      Func->addVariable(ExtraVar);

[Jim Stichnoth, 2016/07/29 19:14:31]

I'm not thrilled about how these extra variables are created, especially the
idea that Variable::Number is no longer const -- what's to prevent some future
well-meaning code from changing a variable's Number and invalidating all the
assumptions about persistence?

What if you create these variables the normal way, and just leave them unused in
Cfg::Variables[] ?

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

Done.

+
+      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;
+
+      for (auto *Instr : RelevantInsts) {
+        if (llvm::isa<InstPhi>(Instr))
+          continue;
+        for (SizeT i = 0; i < Instr->getSrcSize(); ++i) {

[Jim Stichnoth, 2016/07/29 19:14:31]

Document that 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.

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

Copied this as is. :)

+          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);
+
+      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() {