Subzero: Local variable splitting.

src/IceCfg.cpp

 //===- subzero/src/IceCfg.cpp - Control flow graph implementation ---------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 770 matching lines @@
     }
   }
 
   SizeT NodeIndex = 0;
   for (auto *Node : NewList) {
     Node->resetIndex(NodeIndex++);
   }
   Nodes = NewList;
 }
 
+namespace {
+
+/// VariableMap is a simple helper class for splitLocalVars(), that keeps track
+/// of the latest split version of the original Variables.  For each entry, the
+/// Variable is tagged with the CfgNode that it is valid in, so that we don't
+/// need to clear the entire Map[] vector for each block.
+class VariableMap {
+private:
+  VariableMap() = delete;
+  VariableMap(const VariableMap &) = delete;
+  VariableMap &operator=(const VariableMap &) = delete;
+
+  /// VarNodePair is basically std::pair<Variable*,CfgNode*> .
+  struct VarNodePair {
+    Variable *Var = nullptr;
+    const CfgNode *Node = nullptr;
+    VarNodePair() = default;
+
+  private:
+    VarNodePair(const VarNodePair &) = delete;
+    VarNodePair &operator=(const VarNodePair &) = delete;
+  };
+
+public:
+  explicit VariableMap(Cfg *Func)
+      : Func(Func), NumVars(Func->getNumVariables()), Map(NumVars) {}
+  /// Reset the mappings at the start of a block.
+  void reset(const CfgNode *CurNode) { Node = CurNode; }
+  /// Get Var's current mapping (or Var itself if it has no mapping yet).
+  Variable *get(Variable *Var) const {
+    const SizeT VarNum = getVarNum(Var);
+    Variable *MappedVar = Map[VarNum].Var;
+    if (MappedVar == nullptr)
+      return Var;
+    if (Map[VarNum].Node != Node)
+      return Var;
+    return MappedVar;
+  }
+  /// Create a new linked Variable in the LinkedTo chain, and set it as Var's
+  /// latest mapping.
+  Variable *makeLinked(Variable *Var) {
+    Variable *NewVar = Func->makeVariable(Var->getType());
+    NewVar->setRegClass(Var->getRegClass());
+    NewVar->setLinkedTo(get(Var));
+    const SizeT VarNum = getVarNum(Var);
+    Map[VarNum].Var = NewVar;
+    Map[VarNum].Node = Node;
+    return NewVar;
+  }
+  /// Given Var that is LinkedTo some other variable, re-splice it into the
+  /// LinkedTo chain so that the chain is ordered by Variable::getIndex().
+  void spliceBlockLocalLinkedToChain(Variable *Var) {
+    Variable *LinkedTo = Var->getLinkedTo();
+    assert(LinkedTo != nullptr);
+    assert(Var->getIndex() > LinkedTo->getIndex());
+    const SizeT VarNum = getVarNum(LinkedTo);
+    Variable *Link = Map[VarNum].Var;
+    if (Link == nullptr || Map[VarNum].Node != Node)
+      return;
+    Variable *LinkParent = Link->getLinkedTo();
+    while (LinkParent != nullptr && LinkParent->getIndex() >= Var->getIndex()) {
+      Link = LinkParent;
+      LinkParent = Link->getLinkedTo();
+    }
+    Var->setLinkedTo(LinkParent);
+    Link->setLinkedTo(Var);
+  }
+
+private:
+  Cfg *const Func;
+  // NumVars is for the size of the Map array.  It can be const because any new
+  // Variables created during the splitting pass don't need to be mapped.
+  const SizeT NumVars;
+  CfgVector<VarNodePair> Map;
+  const CfgNode *Node = nullptr;
+  /// Get Var's VarNum, and do some validation.
+  SizeT getVarNum(Variable *Var) const {
+    const SizeT VarNum = Var->getIndex();
+    assert(VarNum < NumVars);
+    return VarNum;
+  }
+};
+
+/// A Variable is "allocable" if it is a register allocation candidate but
+/// doesn't already have a register.
+bool isAllocable(const Variable *Var) {
+  if (Var == nullptr)
+    return false;
+  return !Var->hasReg() && Var->mayHaveReg();
+}
+
+/// A Variable is "inf" if it already has a register or is infinite-weight.
+bool isInf(const Variable *Var) {
+  if (Var == nullptr)
+    return false;
+  return Var->hasReg() || Var->mustHaveReg();
+}
+
+} // end of anonymous namespace
+
+/// Within each basic block, rewrite Variable references in terms of chained
+/// copies of the original Variable.  For example:
+///   A = B + C
+/// might be rewritten as:
+///   B1 = B
+///   C1 = C
+///   A = B + C
+///   A1 = A
+/// and then:
+///   D = A + B
+/// might be rewritten as:
+///   A2 = A1
+///   B2 = B1
+///   D = A1 + B1
+///   D1 = D
+///
+/// The purpose is to present the linear-scan register allocator with smaller
+/// live ranges, to help mitigate its "all or nothing" allocation strategy,
+/// while counting on its preference mechanism to keep the split versions in the
+/// same register when possible.
+///
+/// When creating new Variables, A2 is linked to A1 which is linked to A, and
+/// similar for the other Variable linked-to chains.  Rewrites apply only to
+/// Variables where mayHaveReg() is true.
+///
+/// At code emission time, redundant linked-to stack assignments will be
+/// recognized and elided.  To illustrate using the above example, if A1 gets a
+/// register but A and A2 are on the stack, the "A2=A1" store instruction is
+/// redundant since A and A2 share the same stack slot and A1 originated from A.
+///
+/// Simple assignment instructions are rewritten slightly differently, to take
+/// maximal advantage of Variables known to have registers.
+///
+/// In general, there may be several valid ways to rewrite an instruction: add
+/// the new assignment instruction either before or after the original
+/// instruction, and rewrite the original instruction with either the old or the
+/// new variable mapping.  We try to pick a strategy most likely to avoid
+/// potential performance problems.  For example, try to avoid storing to the
+/// stack and then immediately reloading from the same location.  One
+/// consequence is that code might be generated that loads a register from a
+/// stack location, followed almost immediately by another use of the same stack
+/// location, despite its value already being available in a register as a
+/// result of the first instruction.  However, the performance impact here is
+/// likely to be negligible, and a simple availability peephole optimization
+/// could clean it up.
+///
+/// This pass potentially adds a lot of new instructions and variables, and as
+/// such there are compile-time performance concerns, particularly with liveness
+/// analysis and register allocation.  Note that for liveness analysis, the new
+/// variables have single-block liveness, so they don't increase the size of the
+/// liveness bit vectors that need to be merged across blocks.  As a result, the
+/// performance impact is likely to be linearly related to the number of new
+/// instructions, rather than number of new variables times number of blocks
+/// which would be the case if they were multi-block variables.
+void Cfg::splitLocalVars() {
+  if (!getFlags().getSplitLocalVars())
+    return;
+  TimerMarker _(TimerStack::TT_splitLocalVars, this);
+  VariableMap VarMap(this);
+  // TODO(stichnot): Fix this mechanism for LinkedTo variables and stack slot
+  // assignment.
+  //
+  // To work around shortcomings with stack frame mapping, we want to arrange
+  // LinkedTo structure such that within one block, the LinkedTo structure
+  // leading to a root forms a list, not a tree.  A LinkedTo root can have
+  // multiple children linking to it, but only one per block.  Furthermore,
+  // because stack slot mapping processes variables in numerical order, the
+  // LinkedTo chain needs to be ordered such that when A->getLinkedTo()==B, then
+  // A->getIndex()>B->getIndex().

[John, 2016/08/01 14:17:31]

add spaces around ' > ' (the gt operator)

[Jim Stichnoth, 2016/08/01 15:13:50]

Done.

+  //
+  // To effect this, while processing a block we keep track of preexisting
+  // LinkedTo relationships via the LinkedToFixups vector, and at the end of the
+  // block we splice them in such that the block has a single chain for each
+  // root, ordered by getIndex() value.
+  CfgVector<Variable *> LinkedToFixups;
+  for (CfgNode *Node : getNodes()) {
+    // Clear the VarMap and LinkedToFixups at the start of every block.
+    VarMap.reset(Node);
+    LinkedToFixups.clear();
+    auto &Insts = Node->getInsts();
+    auto Iter = Insts.begin();
+    auto IterEnd = Insts.end();
+    // TODO(stichnot): Also create assignments/mappings for phi dest variables.
+    InstList::iterator NextIter;
+    const Inst *WaitingForLabel = nullptr;
+    const Inst *WaitingForBranchTo = nullptr;
+    for (; Iter != IterEnd; Iter = NextIter) {
+      NextIter = Iter;
+      ++NextIter;
+      Inst *Instr = iteratorToInst(Iter);
+      if (Instr->isDeleted())
+        continue;
+      Variable *Dest = Instr->getDest();
+
+      // Before doing any transformations, take care of the bookkeeping for
+      // intra-block branching.
+      //
+      // This is tricky because the transformation for one instruction may
+      // depend on a transformation for a previous instruction, but if that
+      // previous instruction is not dynamically executed due to intra-block
+      // control flow, it may lead to an inconsistent state and incorrect code.
+      //
+      // We want to handle some simple cases, and reject some others:
+      //
+      // 1. For something like a select instruction, we could have:
+      //   test cond
+      //   dest = src_false
+      //   branch conditionally to label
+      //   dest = src_true
+      //   label:
+      //
+      // Between the conditional branch and the label, we need to treat dest and
+      // src variables specially, specifically not creating any new state.
+      //
+      // 2. Some 64-bit atomic instructions may be lowered to a loop:
+      //   label:
+      //   ...
+      //   branch conditionally to label
+      //
+      // No special treatment is needed, but it's worth tracking so that case #1
+      // above can also be handled.
+      //
+      // 3. Advanced switch lowering can create really complex intra-block
+      // control flow, so when we recognize this, we should just stop splitting
+      // for the remainder of the block (which isn't much since a switch
+      // instruction is a terminator).
+      //
+      // 4. Other complex lowering, e.g. an i64 icmp on a 32-bit architecture,
+      // can result in an if/then/else like structure with two labels.  One
+      // possibility would be to suspect splitting for the remainder of the
+      // lowered instruction, and then resume for the remainder of the block,
+      // but since we don't have high-level instruction markers, we might as
+      // well just stop splitting for the remainder of the block.
+      if (Instr->isLabel()) {
+        // A Label instruction shouldn't have any operands, so it can be handled
+        // right here and then move on.
+        assert(Dest == nullptr);
+        assert(Instr->getSrcSize() == 0);
+        if (Instr == WaitingForLabel) {
+          // If we found the forward-branch-target Label instruction we're
+          // waiting for, then clear the WaitingForLabel state.
+          WaitingForLabel = nullptr;
+        } else if (WaitingForLabel == nullptr &&
+                   WaitingForBranchTo == nullptr) {
+          // If we found a new Label instruction while the WaitingFor* state is
+          // clear, then set things up for this being a backward branch target.
+          WaitingForBranchTo = Instr;
+        } else {
+          // We see something we don't understand, so skip to the next block.
+          break;
+        }
+        continue; // move to next instruction
+      }
+      if (const Inst *Label = Instr->getIntraBlockBranchTarget()) {
+        // An intra-block branch instruction shouldn't have any operands, so it
+        // can be handled right here and then move on.
+        assert(Dest == nullptr);
+        assert(Instr->getSrcSize() == 0);
+        if (WaitingForBranchTo == Label && WaitingForLabel == nullptr) {
+          WaitingForBranchTo = nullptr;
+        } else if (WaitingForBranchTo == nullptr &&
+                   (WaitingForLabel == nullptr || WaitingForLabel == Label)) {
+          WaitingForLabel = Label;
+        } else {
+          // We see something we don't understand, so skip to the next block.
+          break;
+        }
+        continue; // move to next instruction
+      }
+
+      // Intra-block bookkeeping is complete, now do the transformations.
+      static constexpr char AnInstructionHasNoName[] = "";
+      // We can limit the splitting to an arbitrary subset of the instructions,
+      // and still expect correct code.  As such, we can do instruction-subset
+      // bisection to help debug any problems in this pass.
+      if (!BuildDefs::minimal() &&
+          !getFlags().matchSplitInsts(AnInstructionHasNoName,
+                                      Instr->getNumber()))
+        continue;
+
+      if (!llvm::isa<InstTarget>(Instr)) {
+        // Ignore non-lowered instructions like FakeDef/FakeUse.
+        continue;
+      }
+      const bool IsUnconditionallyExecuted = (WaitingForLabel == nullptr);
+      const bool DestIsInf = isInf(Dest);
+      const bool DestIsAllocable = isAllocable(Dest);
+      // Note any preexisting LinkedTo relationships that were created during
+      // target lowering.
+      if (Dest != nullptr && Dest->getLinkedTo() != nullptr) {
+        LinkedToFixups.emplace_back(Dest);

[John, 2016/08/01 14:17:31]

Any reasons why you can't spliceBlockLocalLinkedToChain() here?

[Jim Stichnoth, 2016/08/01 15:13:50]

I no longer remember the exact scenario, but this was the first thing I tried
and it didn't work. :(

+      }
+      // Determine the transformation based on the kind of instruction, and
+      // whether its Variables are infinite-weight.  New instructions can be
+      // inserted before the current instruction via Iter, or after the current
+      // instruction via NextIter.
+      if (Instr->isVarAssign()) {
+        auto *SrcVar = llvm::cast<Variable>(Instr->getSrc(0));
+        const bool SrcIsInf = isInf(SrcVar);
+        const bool SrcIsAllocable = isAllocable(SrcVar);
+        if (DestIsInf && SrcIsInf) {
+          // The instruction:
+          //   t:inf = u:inf
+          // No transformation is needed.
+          continue;
+        } else if (DestIsInf && SrcIsAllocable &&
+                   Dest->getType() == Instr->getSrc(0)->getType()) {
+          // The instruction:
+          //   t:inf = v
+          // gets transformed to:
+          //   t:inf = v1
+          //   v2 = t:inf
+          // where:
+          //   v1 := map[v]
+          //   v2 := linkTo(v)
+          //   map[v] := v2
+          //
+          // If both v2 and its linkedToStackRoot get a stack slot, then
+          // "v2=t:inf" is recognized as a redundant assignment and elided.
+          //
+          // Note that if the dest and src types are different, then this is
+          // actually a truncation operation, which would make "v2=t:inf" an
+          // invalid instruction.  In this case, the type test will make it fall
+          // through to the general case below.
+          Variable *OldMapped = VarMap.get(SrcVar);
+          Instr->replaceSource(0, OldMapped);
+          if (IsUnconditionallyExecuted) {
+            // Only create new mapping state if the instruction is
+            // unconditionally executed.
+            Variable *NewMapped = VarMap.makeLinked(SrcVar);
+            Inst *Mov = Target->createLoweredMove(NewMapped, Dest);
+            Insts.insert(NextIter, Mov);
+          }
+          continue;
+        } else if (DestIsAllocable && SrcIsInf) {
+          // The instruction:
+          //   v = t:inf
+          // gets transformed to:
+          //   v = t:inf
+          //   v2 = t:inf
+          // where:
+          //   v2 := linkTo(v)
+          //   map[v] := v2
+          //
+          // If both v2 and v get a stack slot, then "v2=t:inf" is recognized as
+          // a redundant assignment and elided.
+          if (IsUnconditionallyExecuted) {
+            // Only create new mapping state if the instruction is
+            // unconditionally executed.
+            Variable *NewMapped = VarMap.makeLinked(Dest);
+            Inst *Mov = Target->createLoweredMove(NewMapped, SrcVar);
+            Insts.insert(NextIter, Mov);
+          } else {
+            // For a conditionally executed instruction, add a redefinition of
+            // the original Dest mapping, without creating a new linked
+            // variable.
+            Variable *OldMapped = VarMap.get(Dest);
+            Inst *Mov = Target->createLoweredMove(OldMapped, SrcVar);
+            Mov->setDestRedefined();
+            Insts.insert(NextIter, Mov);
+          }
+          continue;
+        }
+      }
+      // The (non-variable-assignment) instruction:
+      //   ... = F(v)
+      // where v is not infinite-weight, gets transformed to:
+      //   v2 = v1
+      //   ... = F(v1)
+      // where:
+      //   v1 := map[v]
+      //   v2 := linkTo(v)
+      //   map[v] := v2
+      // After that, if the "..." dest=u is not infinite-weight, append:
+      //   u2 = u
+      // where:
+      //   u2 := linkTo(u)
+      //   map[u] := u2
+      for (SizeT i = 0; i < Instr->getSrcSize(); ++i) {
+        // Iterate over the top-level src vars.  Don't bother to dig into
+        // e.g. MemOperands because their vars should all be infinite-weight.
+        // (This assumption would need to change if the pass were done
+        // pre-lowering.)
+        if (auto *SrcVar = llvm::dyn_cast<Variable>(Instr->getSrc(i))) {
+          const bool SrcIsAllocable = isAllocable(SrcVar);
+          if (SrcIsAllocable) {
+            Variable *OldMapped = VarMap.get(SrcVar);
+            if (IsUnconditionallyExecuted) {
+              Variable *NewMapped = VarMap.makeLinked(SrcVar);
+              Inst *Mov = Target->createLoweredMove(NewMapped, OldMapped);
+              Insts.insert(Iter, Mov);
+            }
+            Instr->replaceSource(i, OldMapped);
+          }
+        }
+      }
+      // Transformation of Dest is the same as the "v=t:inf" case above.
+      if (DestIsAllocable) {
+        if (IsUnconditionallyExecuted) {
+          Variable *NewMapped = VarMap.makeLinked(Dest);
+          Inst *Mov = Target->createLoweredMove(NewMapped, Dest);
+          Insts.insert(NextIter, Mov);
+        } else {
+          Variable *OldMapped = VarMap.get(Dest);
+          Inst *Mov = Target->createLoweredMove(OldMapped, Dest);
+          Mov->setDestRedefined();
+          Insts.insert(NextIter, Mov);
+        }
+      }
+    }
+    // Splice in any preexisting links into the single chain.
+    for (Variable *Var : LinkedToFixups) {
+      VarMap.spliceBlockLocalLinkedToChain(Var);
+    }
+  }
+  dump("After splitting local variables");
+}
+
 void Cfg::doArgLowering() {
   TimerMarker T(TimerStack::TT_doArgLowering, this);
   getTarget()->lowerArguments();
 }
 
 void Cfg::sortAndCombineAllocas(CfgVector<InstAlloca *> &Allocas,
                                 uint32_t CombinedAlignment, InstList &Insts,
                                 AllocaBaseVariableType BaseVariableType) {
   if (Allocas.empty())
     return;
@@ skipping 853 matching lines @@
     dump("After recomputing liveness for -decorate-asm");
   }
   OstreamLocker L(Ctx);
   Ostream &Str = Ctx->getStrEmit();
   const Assembler *Asm = getAssembler<>();
   const bool NeedSandboxing = getFlags().getUseSandboxing();
 
   emitTextHeader(FunctionName, Ctx, Asm);
   if (getFlags().getDecorateAsm()) {
     for (Variable *Var : getVariables()) {
-      if (Var->hasStackOffset() && !Var->isRematerializable()) {
+      if (Var->hasKnownStackOffset() && !Var->isRematerializable()) {
         Str << "\t" << Var->getSymbolicStackOffset() << " = "
             << Var->getStackOffset() << "\n";
       }
     }
   }
   for (CfgNode *Node : Nodes) {
     if (NeedSandboxing && Node->needsAlignment()) {
       Str << "\t" << Asm->getAlignDirective() << " "
           << Asm->getBundleAlignLog2Bytes() << "\n";
     }
@@ skipping 92 matching lines @@
     }
   }
   // Print each basic block
   for (CfgNode *Node : Nodes)
     Node->dump(this);
   if (isVerbose(IceV_Instructions))
     Str << "}\n";
 }
 
 } // end of namespace Ice