Subzero: Improve performance of liveness analysis and live range construction.
The key performance problem was that the per-block LiveBegin and LiveEnd vectors were dense with respect to the multi-block "global" variables, even though very few of the global variables are ever live within the block. This led to large vectors needlessly initialized and iterated over.
The new approach is to accumulate two small vectors of <variable,instruction_number> tuples (LiveBegin and LiveEnd) as each block is processed, then sort the vectors and iterate over them in parallel to construct the live ranges.
Some of the anomalies in the original liveness analysis code have been straightened out:
1. Variables have an IgnoreLiveness attribute to suppress analysis. This is currently used only on the esp register.
2. Instructions have a DestNonKillable attribute which causes the Dest variable not to be marked as starting a new live range at that instruction. This is used when a variable is non-SSA and has more than one assignment within a block, but we want to treat it as a single live range. This lets the variable have zero or one live range begins or ends within a block. DestNonKillable is derived automatically for two-address instructions, and annotated manually in a few other cases.
This is tested by comparing the O2 asm output in each Spec2K component. In theory, the output should be the same except for some differences in pseudo-instructions output as comments. However, some actual differences showed up, related to the i64 shl instruction followed by trunc to i32. This turned out to be a liveness bug that was accidentally fixed.
BUG= none
R=jvoung@chromium.org
Review URL: https://codereview.chromium.org/652633002
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index 83d8e26..c30e02a 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -205,9 +205,9 @@
// 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.
- TimerMarker T1(TimerStack::TT_liveRange, this);
for (CfgNode *Node : Nodes)
Node->livenessPostprocess(Mode, getLiveness());
if (Mode == Liveness_Intervals) {
@@ -246,7 +246,6 @@
if (Var->getWeight().isInf())
Var->setLiveRangeInfiniteWeight();
}
- dump();
}
}
@@ -257,24 +256,37 @@
bool Valid = true;
Ostream &Str = Ctx->getStrDump();
for (CfgNode *Node : Nodes) {
+ Inst *FirstInst = NULL;
for (Inst *Inst : Node->getInsts()) {
if (Inst->isDeleted())
continue;
if (llvm::isa<InstFakeKill>(Inst))
continue;
+ if (FirstInst == NULL)
+ FirstInst = Inst;
InstNumberT InstNumber = Inst->getNumber();
- Variable *Dest = Inst->getDest();
- if (Dest) {
- // TODO: This instruction should actually begin Dest's live
- // range, so we could probably test that this instruction is
- // the beginning of some segment of Dest's live range. But
- // this wouldn't work with non-SSA temporaries during
- // lowering.
- if (!Dest->getLiveRange().containsValue(InstNumber)) {
- Valid = false;
- Str << "Liveness error: inst " << Inst->getNumber() << " dest ";
- Dest->dump(this);
- Str << " live range " << Dest->getLiveRange() << "\n";
+ if (Variable *Dest = Inst->getDest()) {
+ if (!Dest->getIgnoreLiveness()) {
+ bool Invalid = false;
+ const bool IsDest = true;
+ if (!Dest->getLiveRange().containsValue(InstNumber, IsDest))
+ Invalid = true;
+ // Check that this instruction actually *begins* Dest's live
+ // range, by checking that Dest is not live in the previous
+ // instruction. As a special exception, we don't check this
+ // for the first instruction of the block, because a Phi
+ // temporary may be live at the end of the previous block,
+ // and if it is also assigned in the first instruction of
+ // this block, the adjacent live ranges get merged.
+ if (Inst != FirstInst && !Inst->isDestNonKillable() &&
+ Dest->getLiveRange().containsValue(InstNumber - 1, IsDest))
+ Invalid = true;
+ if (Invalid) {
+ Valid = false;
+ Str << "Liveness error: inst " << Inst->getNumber() << " dest ";
+ Dest->dump(this);
+ Str << " live range " << Dest->getLiveRange() << "\n";
+ }
}
}
for (SizeT I = 0; I < Inst->getSrcSize(); ++I) {
@@ -282,7 +294,9 @@
SizeT NumVars = Src->getNumVars();
for (SizeT J = 0; J < NumVars; ++J) {
const Variable *Var = Src->getVar(J);
- if (!Var->getLiveRange().containsValue(InstNumber)) {
+ const bool IsDest = false;
+ if (!Var->getIgnoreLiveness() &&
+ !Var->getLiveRange().containsValue(InstNumber, IsDest)) {
Valid = false;
Str << "Liveness error: inst " << Inst->getNumber() << " var ";
Var->dump(this);
