Subzero: Clean up live range construction.
Moves the deletion of newly dead instructions into the main liveness() routine. The old livenessPostProcess() routine is renamed and now used purely for live range construction.
The hack is removed in which live in-args have a custom live range segment added to avoid an artifact of the live ranges. It is replaced with a gentler hack that extends the instruction numbering range of the initial basic block to avoid the artifact.
Since special live range segments no longer need to be prepended, the live range representation is simplified and we can always assume that segments are being appended, never prepended (and as before, never added to the middle).
Some magic constants involving special instruction numbers are replaced with symbolic constants.
BUG= none
R=jvoung@chromium.org
Review URL: https://codereview.chromium.org/802003003
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index 0bd6b36..a328d21 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -26,7 +26,8 @@
Cfg::Cfg(GlobalContext *Ctx)
: Ctx(Ctx), FunctionName(""), ReturnType(IceType_void),
IsInternalLinkage(false), HasError(false), FocusedTiming(false),
- ErrorMessage(""), Entry(NULL), NextInstNumber(1), Live(nullptr),
+ ErrorMessage(""), Entry(NULL), NextInstNumber(Inst::NumberInitial),
+ Live(nullptr),
Target(TargetLowering::createLowering(Ctx->getTargetArch(), this)),
VMetadata(new VariablesMetadata(this)),
TargetAssembler(
@@ -96,7 +97,7 @@
void Cfg::renumberInstructions() {
TimerMarker T(TimerStack::TT_renumberInstructions, this);
- NextInstNumber = 1;
+ NextInstNumber = Inst::NumberInitial;
for (CfgNode *Node : Nodes)
Node->renumberInstructions();
}
@@ -256,7 +257,6 @@
llvm::BitVector NeedToProcess(Nodes.size(), true);
while (NeedToProcess.any()) {
// Iterate in reverse topological order to speed up convergence.
- // TODO(stichnot): Use llvm::make_range with LLVM 3.5.
for (auto I = Nodes.rbegin(), E = Nodes.rend(); I != E; ++I) {
CfgNode *Node = *I;
if (NeedToProcess[Node->getIndex()]) {
@@ -276,38 +276,45 @@
for (Variable *Var : Variables)
Var->resetLiveRange();
}
- // Collect timing for just the portion that constructs the live
- // range intervals based on the end-of-live-range computation, for a
- // finer breakdown of the cost.
- TimerMarker T1(TimerStack::TT_liveRange, this);
- // Make a final pass over instructions to delete dead instructions
- // and build each Variable's live range.
- for (CfgNode *Node : Nodes)
- Node->livenessPostprocess(Mode, getLiveness());
- if (Mode == Liveness_Intervals) {
- // Special treatment for live in-args. Their liveness needs to
- // extend beyond the beginning of the function, otherwise an arg
- // whose only use is in the first instruction will end up having
- // the trivial live range [1,1) and will *not* interfere with
- // other arguments. So if the first instruction of the method is
- // "r=arg1+arg2", both args may be assigned the same register.
- for (SizeT I = 0; I < Args.size(); ++I) {
- Variable *Arg = Args[I];
- if (!Arg->getLiveRange().isEmpty()) {
- // Add live range [-1,0) with weight 0. TODO: Here and below,
- // use better symbolic constants along the lines of
- // Inst::NumberDeleted and Inst::NumberSentinel instead of -1
- // and 0.
- Arg->addLiveRange(-1, 0, 0);
+ // Make a final pass over each node to delete dead instructions,
+ // collect the first and last instruction numbers, and add live
+ // range segments for that node.
+ for (CfgNode *Node : Nodes) {
+ InstNumberT FirstInstNum = Inst::NumberSentinel;
+ InstNumberT LastInstNum = Inst::NumberSentinel;
+ for (auto I = Node->getPhis().begin(), E = Node->getPhis().end(); I != E;
+ ++I) {
+ I->deleteIfDead();
+ if (Mode == Liveness_Intervals && !I->isDeleted()) {
+ if (FirstInstNum == Inst::NumberSentinel)
+ FirstInstNum = I->getNumber();
+ assert(I->getNumber() > LastInstNum);
+ LastInstNum = I->getNumber();
}
- // Do the same for i64 args that may have been lowered into i32
- // Lo and Hi components.
- Variable *Lo = Arg->getLo();
- if (Lo && !Lo->getLiveRange().isEmpty())
- Lo->addLiveRange(-1, 0, 0);
- Variable *Hi = Arg->getHi();
- if (Hi && !Hi->getLiveRange().isEmpty())
- Hi->addLiveRange(-1, 0, 0);
+ }
+ for (auto I = Node->getInsts().begin(), E = Node->getInsts().end(); I != E;
+ ++I) {
+ I->deleteIfDead();
+ if (Mode == Liveness_Intervals && !I->isDeleted()) {
+ if (FirstInstNum == Inst::NumberSentinel)
+ FirstInstNum = I->getNumber();
+ assert(I->getNumber() > LastInstNum);
+ LastInstNum = I->getNumber();
+ }
+ }
+ if (Mode == Liveness_Intervals) {
+ // Special treatment for live in-args. Their liveness needs to
+ // extend beyond the beginning of the function, otherwise an arg
+ // whose only use is in the first instruction will end up having
+ // the trivial live range [2,2) and will *not* interfere with
+ // other arguments. So if the first instruction of the method
+ // is "r=arg1+arg2", both args may be assigned the same
+ // register. This is accomplished by extending the entry
+ // block's instruction range from [2,n) to [1,n) which will
+ // transform the problematic [2,2) live ranges into [1,2).
+ if (FirstInstNum == Inst::NumberInitial)
+ FirstInstNum = Inst::NumberExtended;
+ Node->livenessAddIntervals(getLiveness(), FirstInstNum, LastInstNum);
}
}
}
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index 1623731..42731ad 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -639,40 +639,16 @@
return Changed;
}
-// Now that basic liveness is complete, remove dead instructions that
-// were tentatively marked as dead, and compute actual live ranges.
-// It is assumed that within a single basic block, a live range begins
-// at most once and ends at most once. This is certainly true for
-// pure SSA form. It is also true once phis are lowered, since each
+// Once basic liveness is complete, compute actual live ranges. It is
+// assumed that within a single basic block, a live range begins at
+// most once and ends at most once. This is certainly true for pure
+// SSA form. It is also true once phis are lowered, since each
// assignment to the phi-based temporary is in a different basic
// block, and there is a single read that ends the live in the basic
// block that contained the actual phi instruction.
-void CfgNode::livenessPostprocess(LivenessMode Mode, Liveness *Liveness) {
- InstNumberT FirstInstNum = Inst::NumberSentinel;
- InstNumberT LastInstNum = Inst::NumberSentinel;
- // Process phis in any order. Process only Dest operands.
- for (auto I = Phis.begin(), E = Phis.end(); I != E; ++I) {
- I->deleteIfDead();
- if (I->isDeleted())
- continue;
- if (FirstInstNum == Inst::NumberSentinel)
- FirstInstNum = I->getNumber();
- assert(I->getNumber() > LastInstNum);
- LastInstNum = I->getNumber();
- }
- // Process instructions
- for (auto I = Insts.begin(), E = Insts.end(); I != E; ++I) {
- I->deleteIfDead();
- if (I->isDeleted())
- continue;
- if (FirstInstNum == Inst::NumberSentinel)
- FirstInstNum = I->getNumber();
- assert(I->getNumber() > LastInstNum);
- LastInstNum = I->getNumber();
- }
- if (Mode != Liveness_Intervals)
- return;
- TimerMarker T1(TimerStack::TT_liveRangeCtor, Func);
+void CfgNode::livenessAddIntervals(Liveness *Liveness, InstNumberT FirstInstNum,
+ InstNumberT LastInstNum) {
+ TimerMarker T1(TimerStack::TT_liveRange, Func);
SizeT NumVars = Liveness->getNumVarsInNode(this);
LivenessBV &LiveIn = Liveness->getLiveIn(this);
diff --git a/src/IceCfgNode.h b/src/IceCfgNode.h
index 0d6e911..c5b9ac5 100644
--- a/src/IceCfgNode.h
+++ b/src/IceCfgNode.h
@@ -80,7 +80,8 @@
void genCode();
void livenessLightweight();
bool liveness(Liveness *Liveness);
- void livenessPostprocess(LivenessMode Mode, Liveness *Liveness);
+ void livenessAddIntervals(Liveness *Liveness, InstNumberT FirstInstNum,
+ InstNumberT LastInstNum);
void contractIfEmpty();
void doBranchOpt(const CfgNode *NextNode);
void emit(Cfg *Func) const;
diff --git a/src/IceInst.h b/src/IceInst.h
index 15751d3..5bfabe9 100644
--- a/src/IceInst.h
+++ b/src/IceInst.h
@@ -69,7 +69,12 @@
InstNumberT getNumber() const { return Number; }
void renumber(Cfg *Func);
- enum { NumberDeleted = -1, NumberSentinel = 0 };
+ enum {
+ NumberDeleted = -1,
+ NumberSentinel = 0,
+ NumberInitial = 2,
+ NumberExtended = NumberInitial - 1
+ };
bool isDeleted() const { return Deleted; }
void setDeleted() { Deleted = true; }
diff --git a/src/IceOperand.cpp b/src/IceOperand.cpp
index 615c81c..bf5546f 100644
--- a/src/IceOperand.cpp
+++ b/src/IceOperand.cpp
@@ -33,25 +33,14 @@
}
void LiveRange::addSegment(InstNumberT Start, InstNumberT End) {
- if (Range.empty()) {
- Range.push_back(RangeElementType(Start, End));
- return;
- }
- // Special case for faking in-arg liveness.
- if (End < Range.front().first) {
- assert(Start < 0);
- // This is inefficient with Range as a std::vector, but there are
- // generally very few arguments compared to the total number of
- // variables with non-empty live ranges.
- Range.insert(Range.begin(), RangeElementType(Start, End));
- return;
- }
- InstNumberT CurrentEnd = Range.back().second;
- assert(Start >= CurrentEnd);
- // Check for merge opportunity.
- if (Start == CurrentEnd) {
- Range.back().second = End;
- return;
+ if (!Range.empty()) {
+ // Check for merge opportunity.
+ InstNumberT CurrentEnd = Range.back().second;
+ assert(Start >= CurrentEnd);
+ if (Start == CurrentEnd) {
+ Range.back().second = End;
+ return;
+ }
}
Range.push_back(RangeElementType(Start, End));
}
diff --git a/src/IceTimerTree.def b/src/IceTimerTree.def
index 1fbd709..3139a81 100644
--- a/src/IceTimerTree.def
+++ b/src/IceTimerTree.def
@@ -31,7 +31,6 @@
X(initUnhandled) \
X(linearScan) \
X(liveRange) \
- X(liveRangeCtor) \
X(liveness) \
X(livenessLightweight) \
X(llvmConvert) \
