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 "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>
 
 #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
 // anywhere outside their own files. To create target-specific objects
 // (TargetLowering, TargetDataLowering, and TargetHeaderLowering) we use the
@@ skipping 465 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().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() {
   // 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