//===- subzero/src/IceVariableSplitting.cpp - Local variable splitting ----===//
//
// The Subzero Code Generator
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
///
/// \file
/// \brief Aggressive block-local variable splitting to improve linear-scan
/// register allocation.
///
//===----------------------------------------------------------------------===//
#include "IceVariableSplitting.h"
#include "IceCfg.h"
#include "IceCfgNode.h"
#include "IceClFlags.h"
#include "IceInst.h"
#include "IceOperand.h"
#include "IceTargetLowering.h"
namespace Ice {
namespace {
/// 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();
}
/// VariableMap is a simple helper class that keeps track of the latest split
/// version of the original Variables, as well as the instruction containing the
/// last use of the Variable within the current block. 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;
struct VarInfo {
/// MappedVar is the latest mapped/split version of the Variable.
Variable *MappedVar = nullptr;
/// MappedVarNode is the block in which MappedVar is valid.
const CfgNode *MappedVarNode = nullptr;
/// LastUseInst is the last instruction in the block that uses the Variable
/// as a source operand.
const Inst *LastUseInst = nullptr;
/// LastUseNode is the block in which LastUseInst is valid.
const CfgNode *LastUseNode = nullptr;
VarInfo() = default;
private:
VarInfo(const VarInfo &) = delete;
VarInfo &operator=(const VarInfo &) = 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;
// Do a prepass through all the instructions, marking which instruction is
// the last use of each Variable within the block.
for (const Inst &Instr : Node->getInsts()) {
if (Instr.isDeleted())
continue;
for (SizeT i = 0; i < Instr.getSrcSize(); ++i) {
if (auto *SrcVar = llvm::dyn_cast<Variable>(Instr.getSrc(i))) {
const SizeT VarNum = getVarNum(SrcVar);
Map[VarNum].LastUseInst = &Instr;
Map[VarNum].LastUseNode = Node;
}
}
}
}
/// 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].MappedVar;
if (MappedVar == nullptr)
return Var;
if (Map[VarNum].MappedVarNode != 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].MappedVar = NewVar;
Map[VarNum].MappedVarNode = 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].MappedVar;
if (Link == nullptr || Map[VarNum].MappedVarNode != Node)
return;
Variable *LinkParent = Link->getLinkedTo();
while (LinkParent != nullptr && LinkParent->getIndex() >= Var->getIndex()) {
Link = LinkParent;
LinkParent = Link->getLinkedTo();
}
Var->setLinkedTo(LinkParent);
Link->setLinkedTo(Var);
}
/// Return whether the given Variable has any uses as a source operand within
/// the current block. If it has no source operand uses, but is assigned as a
/// dest variable in some instruction in the block, then we needn't bother
/// splitting it.
bool isDestUsedInBlock(const Variable *Dest) const {
return Map[getVarNum(Dest)].LastUseNode == Node;
}
/// Return whether the given instruction is the last use of the given Variable
/// within the current block. If it is, then we needn't bother splitting the
/// Variable at this instruction.
bool isInstLastUseOfVar(const Variable *Var, const Inst *Instr) {
return Map[getVarNum(Var)].LastUseInst == Instr;
}
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<VarInfo> Map;
const CfgNode *Node = nullptr;
/// Get Var's VarNum, and do some validation.
SizeT getVarNum(const Variable *Var) const {
const SizeT VarNum = Var->getIndex();
assert(VarNum < NumVars);
return VarNum;
}
};
/// LocalVariableSplitter tracks the necessary splitting state across
/// instructions.
class LocalVariableSplitter {
LocalVariableSplitter() = delete;
LocalVariableSplitter(const LocalVariableSplitter &) = delete;
LocalVariableSplitter &operator=(const LocalVariableSplitter &) = delete;
public:
explicit LocalVariableSplitter(Cfg *Func)
: Target(Func->getTarget()), VarMap(Func) {}
/// setNode() is called before processing the instructions of a block.
void setNode(CfgNode *CurNode) {
Node = CurNode;
VarMap.reset(Node);
LinkedToFixups.clear();
}
/// finalizeNode() is called after all instructions in the block are
/// processed.
void finalizeNode() {
// Splice in any preexisting LinkedTo links into the single chain. These
// are the ones that were recorded during setInst().
for (Variable *Var : LinkedToFixups) {
VarMap.spliceBlockLocalLinkedToChain(Var);
}
}
/// setInst() is called before processing the next instruction. The iterators
/// are the insertion points for a new instructions, depending on whether the
/// new instruction should be inserted before or after the current
/// instruction.
void setInst(Inst *CurInst, InstList::iterator Cur, InstList::iterator Next) {
Instr = CurInst;
Dest = Instr->getDest();
IterCur = Cur;
IterNext = Next;
ShouldSkipRemainingInstructions = false;
// Note any preexisting LinkedTo relationships that were created during
// target lowering. Record them in LinkedToFixups which is then processed
// in finalizeNode().
if (Dest != nullptr && Dest->getLinkedTo() != nullptr) {
LinkedToFixups.emplace_back(Dest);
}
}
bool shouldSkipRemainingInstructions() const {
return ShouldSkipRemainingInstructions;
}
bool isUnconditionallyExecuted() const { return WaitingForLabel == nullptr; }
/// Note: the handle*() functions return true to indicate that the instruction
/// has now been handled and that the instruction loop should continue to the
/// next instruction in the block (and return false otherwise). In addition,
/// they set the ShouldSkipRemainingInstructions flag to indicate that no more
/// instructions in the block should be processed.
/// Handle an "unwanted" instruction by returning true;
bool handleUnwantedInstruction() {
// 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.
static constexpr char AnInstructionHasNoName[] = "";
if (!BuildDefs::minimal() &&
!getFlags().matchSplitInsts(AnInstructionHasNoName,
Instr->getNumber())) {
return true;
}
if (!llvm::isa<InstTarget>(Instr)) {
// Ignore non-lowered instructions like FakeDef/FakeUse.
return true;
}
return false;
}
/// Process a potential label instruction.
bool handleLabel() {
if (!Instr->isLabel())
return false;
// 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.
ShouldSkipRemainingInstructions = true;
}
return true;
}
/// Process a potential intra-block branch instruction.
bool handleIntraBlockBranch() {
const Inst *Label = Instr->getIntraBlockBranchTarget();
if (Label == nullptr)
return false;
// 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.
ShouldSkipRemainingInstructions = true;
}
return true;
}
/// Specially process a potential "Variable=Variable" assignment instruction,
/// when it conforms to certain patterns.
bool handleSimpleVarAssign() {
if (!Instr->isVarAssign())
return false;
const bool DestIsInf = isInf(Dest);
const bool DestIsAllocable = isAllocable(Dest);
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.
return true;
}
if (DestIsInf && SrcIsAllocable && Dest->getType() == SrcVar->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.
if (!VarMap.isInstLastUseOfVar(SrcVar, Instr)) {
Variable *NewMapped = VarMap.makeLinked(SrcVar);
Inst *Mov = Target->createLoweredMove(NewMapped, Dest);
Node->getInsts().insert(IterNext, Mov);
}
}
return true;
}
if (DestIsAllocable && SrcIsInf) {
if (!VarMap.isDestUsedInBlock(Dest)) {
return true;
}
// 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);
Node->getInsts().insert(IterNext, 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();
Node->getInsts().insert(IterNext, Mov);
}
return true;
}
assert(!ShouldSkipRemainingInstructions);
return false;
}
/// Process the dest Variable of a Phi instruction.
bool handlePhi() {
assert(llvm::isa<InstPhi>(Instr));
const bool DestIsAllocable = isAllocable(Dest);
if (!DestIsAllocable)
return true;
if (!VarMap.isDestUsedInBlock(Dest))
return true;
Variable *NewMapped = VarMap.makeLinked(Dest);
Inst *Mov = Target->createLoweredMove(NewMapped, Dest);
Node->getInsts().insert(IterCur, Mov);
return true;
}
/// Process an arbitrary instruction.
bool handleGeneralInst() {
const bool DestIsAllocable = isAllocable(Dest);
// 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()) {
if (!VarMap.isInstLastUseOfVar(SrcVar, Instr)) {
Variable *NewMapped = VarMap.makeLinked(SrcVar);
Inst *Mov = Target->createLoweredMove(NewMapped, OldMapped);
Node->getInsts().insert(IterCur, Mov);
}
}
Instr->replaceSource(i, OldMapped);
}
}
}
// Transformation of Dest is the same as the "v=t:inf" case above.
if (DestIsAllocable && VarMap.isDestUsedInBlock(Dest)) {
if (isUnconditionallyExecuted()) {
Variable *NewMapped = VarMap.makeLinked(Dest);
Inst *Mov = Target->createLoweredMove(NewMapped, Dest);
Node->getInsts().insert(IterNext, Mov);
} else {
Variable *OldMapped = VarMap.get(Dest);
Inst *Mov = Target->createLoweredMove(OldMapped, Dest);
Mov->setDestRedefined();
Node->getInsts().insert(IterNext, Mov);
}
}
return true;
}
private:
TargetLowering *Target;
CfgNode *Node = nullptr;
Inst *Instr = nullptr;
Variable *Dest = nullptr;
InstList::iterator IterCur;
InstList::iterator IterNext;
bool ShouldSkipRemainingInstructions = false;
VariableMap VarMap;
CfgVector<Variable *> LinkedToFixups;
/// WaitingForLabel and WaitingForBranchTo are for tracking intra-block
/// control flow.
const Inst *WaitingForLabel = nullptr;
const Inst *WaitingForBranchTo = nullptr;
};
} // 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 splitBlockLocalVariables(Cfg *Func) {
if (!getFlags().getSplitLocalVars())
return;
TimerMarker _(TimerStack::TT_splitLocalVars, Func);
LocalVariableSplitter Splitter(Func);
// 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().
//
// 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 : Func->getNodes()) {
// Clear the VarMap and LinkedToFixups at the start of every block.
LinkedToFixups.clear();
Splitter.setNode(Node);
auto &Insts = Node->getInsts();
auto Iter = Insts.begin();
auto IterEnd = Insts.end();
// TODO(stichnot): Figure out why Phi processing usually degrades
// performance. Disable for now.
static constexpr bool ProcessPhis = false;
if (ProcessPhis) {
for (Inst &Instr : Node->getPhis()) {
if (Instr.isDeleted())
continue;
Splitter.setInst(&Instr, Iter, Iter);
Splitter.handlePhi();
}
}
InstList::iterator NextIter;
for (; Iter != IterEnd && !Splitter.shouldSkipRemainingInstructions();
Iter = NextIter) {
NextIter = Iter;
++NextIter;
Inst *Instr = iteratorToInst(Iter);
if (Instr->isDeleted())
continue;
Splitter.setInst(Instr, Iter, NextIter);
// 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 (Splitter.handleLabel())
continue;
if (Splitter.handleIntraBlockBranch())
continue;
if (Splitter.handleUnwantedInstruction())
continue;
// Intra-block bookkeeping is complete, now do the transformations.
// 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 (Splitter.handleSimpleVarAssign())
continue;
if (Splitter.handleGeneralInst())
continue;
}
Splitter.finalizeNode();
}
Func->dump("After splitting local variables");
}
} // end of namespace Ice