Subzero: Speed up VariablesMetadata initialization.
Currently, O2 calls VariablesMetadata::init() 4 times:
- Twice for liveness analysis, where only multi-block use information is needed for dealing with sparse bit vectors.
- Once for address mode inference, where single-definition information is needed.
- Once for register allocation, where all information is needed, including the set of all definitions which is needed for determining AllowOverlap.
So we limit the amount of data we gather based on the actual need.
BUG= none
R=jvoung@chromium.org
Review URL: https://codereview.chromium.org/650613003
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index e63c928..bca941e 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -164,7 +164,7 @@
// doesn't need to iterate until convergence.
void Cfg::livenessLightweight() {
TimerMarker T(TimerStack::TT_livenessLightweight, this);
- getVMetadata()->init();
+ getVMetadata()->init(VMK_Uses);
for (CfgNode *Node : Nodes)
Node->livenessLightweight();
}
@@ -172,7 +172,7 @@
void Cfg::liveness(LivenessMode Mode) {
TimerMarker T(TimerStack::TT_liveness, this);
Live.reset(new Liveness(this, Mode));
- getVMetadata()->init();
+ getVMetadata()->init(VMK_Uses);
Live->init();
// Initialize with all nodes needing to be processed.
llvm::BitVector NeedToProcess(Nodes.size(), true);
diff --git a/src/IceOperand.cpp b/src/IceOperand.cpp
index 3f7d0bf..3285e6d 100644
--- a/src/IceOperand.cpp
+++ b/src/IceOperand.cpp
@@ -185,8 +185,10 @@
return V;
}
-void VariableTracking::markUse(const Inst *Instr, const CfgNode *Node,
- bool IsFromDef, bool IsImplicit) {
+void VariableTracking::markUse(MetadataKind TrackingKind, const Inst *Instr,
+ const CfgNode *Node, bool IsFromDef,
+ bool IsImplicit) {
+ (void)TrackingKind;
if (MultiBlock == MBS_MultiBlock)
return;
// TODO(stichnot): If the use occurs as a source operand in the
@@ -227,19 +229,31 @@
}
}
-void VariableTracking::markDef(const Inst *Instr, const CfgNode *Node) {
+void VariableTracking::markDef(MetadataKind TrackingKind, const Inst *Instr,
+ const CfgNode *Node) {
// TODO(stichnot): If the definition occurs in the last instruction
// of the block, consider not marking this as a separate use. But
// be careful not to omit all uses of the variable if markDef() and
// markUse() both use this optimization.
assert(Node);
// Verify that instructions are added in increasing order.
- assert(Definitions.empty() ||
- Instr->getNumber() >= Definitions.back()->getNumber());
- Definitions.push_back(Instr);
+#ifndef NDEBUG
+ if (TrackingKind == VMK_All) {
+ const Inst *LastInstruction =
+ Definitions.empty() ? FirstOrSingleDefinition : Definitions.back();
+ assert(LastInstruction == NULL ||
+ Instr->getNumber() >= LastInstruction->getNumber());
+ }
+#endif
const bool IsFromDef = true;
const bool IsImplicit = false;
- markUse(Instr, Node, IsFromDef, IsImplicit);
+ markUse(TrackingKind, Instr, Node, IsFromDef, IsImplicit);
+ if (TrackingKind == VMK_Uses)
+ return;
+ if (FirstOrSingleDefinition == NULL)
+ FirstOrSingleDefinition = Instr;
+ else if (TrackingKind == VMK_All)
+ Definitions.push_back(Instr);
switch (MultiDef) {
case MDS_Unknown:
assert(SingleDefNode == NULL);
@@ -275,8 +289,8 @@
return NULL;
case MDS_SingleDef:
case MDS_MultiDefSingleBlock:
- assert(!Definitions.empty());
- return Definitions[0];
+ assert(FirstOrSingleDefinition);
+ return FirstOrSingleDefinition;
}
}
@@ -287,13 +301,14 @@
case MDS_MultiDefSingleBlock:
return NULL;
case MDS_SingleDef:
- assert(!Definitions.empty());
- return Definitions[0];
+ assert(FirstOrSingleDefinition);
+ return FirstOrSingleDefinition;
}
}
-void VariablesMetadata::init() {
+void VariablesMetadata::init(MetadataKind TrackingKind) {
TimerMarker T(TimerStack::TT_vmetadata, Func);
+ Kind = TrackingKind;
Metadata.clear();
Metadata.resize(Func->getNumVariables());
@@ -303,7 +318,8 @@
const CfgNode *EntryNode = Func->getEntryNode();
const bool IsFromDef = false;
const bool IsImplicit = true;
- Metadata[Var->getIndex()].markUse(NoInst, EntryNode, IsFromDef, IsImplicit);
+ Metadata[Var->getIndex()]
+ .markUse(Kind, NoInst, EntryNode, IsFromDef, IsImplicit);
}
for (CfgNode *Node : Func->getNodes()) {
@@ -318,14 +334,14 @@
Variable *Var = llvm::cast<Variable>(I->getSrc(SrcNum));
SizeT VarNum = Var->getIndex();
assert(VarNum < Metadata.size());
- Metadata[VarNum].markDef(Kill, Node);
+ Metadata[VarNum].markDef(Kind, Kill, Node);
}
continue; // no point in executing the rest
}
if (Variable *Dest = I->getDest()) {
SizeT DestNum = Dest->getIndex();
assert(DestNum < Metadata.size());
- Metadata[DestNum].markDef(I, Node);
+ Metadata[DestNum].markDef(Kind, I, Node);
}
for (SizeT SrcNum = 0; SrcNum < I->getSrcSize(); ++SrcNum) {
Operand *Src = I->getSrc(SrcNum);
@@ -336,7 +352,7 @@
assert(VarNum < Metadata.size());
const bool IsFromDef = false;
const bool IsImplicit = false;
- Metadata[VarNum].markUse(I, Node, IsFromDef, IsImplicit);
+ Metadata[VarNum].markUse(Kind, I, Node, IsFromDef, IsImplicit);
}
}
}
@@ -344,6 +360,7 @@
}
bool VariablesMetadata::isMultiDef(const Variable *Var) const {
+ assert(Kind != VMK_Uses);
if (Var->getIsArg())
return false;
if (!isTracked(Var))
@@ -364,6 +381,7 @@
}
const Inst *VariablesMetadata::getFirstDefinition(const Variable *Var) const {
+ assert(Kind != VMK_Uses);
if (!isTracked(Var))
return NULL; // conservative answer
SizeT VarNum = Var->getIndex();
@@ -371,6 +389,7 @@
}
const Inst *VariablesMetadata::getSingleDefinition(const Variable *Var) const {
+ assert(Kind != VMK_Uses);
if (!isTracked(Var))
return NULL; // conservative answer
SizeT VarNum = Var->getIndex();
@@ -378,11 +397,12 @@
}
const InstDefList &
-VariablesMetadata::getDefinitions(const Variable *Var) const {
+VariablesMetadata::getLatterDefinitions(const Variable *Var) const {
+ assert(Kind == VMK_All);
if (!isTracked(Var))
return NoDefinitions;
SizeT VarNum = Var->getIndex();
- return Metadata[VarNum].getDefinitions();
+ return Metadata[VarNum].getLatterDefinitions();
}
const CfgNode *VariablesMetadata::getLocalUseNode(const Variable *Var) const {
diff --git a/src/IceOperand.h b/src/IceOperand.h
index 3465ce5..6d31127 100644
--- a/src/IceOperand.h
+++ b/src/IceOperand.h
@@ -516,6 +516,11 @@
Variable *VarsReal[1];
};
+enum MetadataKind {
+ VMK_Uses, // Track only uses, not defs
+ VMK_SingleDefs, // Track uses+defs, but only record single def
+ VMK_All // Track uses+defs, including full def list
+};
typedef std::vector<const Inst *> InstDefList;
// VariableTracking tracks the metadata for a single variable. It is
@@ -539,16 +544,17 @@
};
VariableTracking()
: MultiDef(MDS_Unknown), MultiBlock(MBS_Unknown), SingleUseNode(NULL),
- SingleDefNode(NULL) {}
+ SingleDefNode(NULL), FirstOrSingleDefinition(NULL) {}
MultiDefState getMultiDef() const { return MultiDef; }
MultiBlockState getMultiBlock() const { return MultiBlock; }
const Inst *getFirstDefinition() const;
const Inst *getSingleDefinition() const;
- const InstDefList &getDefinitions() const { return Definitions; }
+ const InstDefList &getLatterDefinitions() const { return Definitions; }
const CfgNode *getNode() const { return SingleUseNode; }
- void markUse(const Inst *Instr, const CfgNode *Node, bool IsFromDef,
- bool IsImplicit);
- void markDef(const Inst *Instr, const CfgNode *Node);
+ void markUse(MetadataKind TrackingKind, const Inst *Instr,
+ const CfgNode *Node, bool IsFromDef, bool IsImplicit);
+ void markDef(MetadataKind TrackingKind, const Inst *Instr,
+ const CfgNode *Node);
private:
MultiDefState MultiDef;
@@ -557,7 +563,8 @@
const CfgNode *SingleDefNode;
// All definitions of the variable are collected here, in increasing
// order of instruction number.
- InstDefList Definitions;
+ InstDefList Definitions; // Only used if Kind==VMK_All
+ const Inst *FirstOrSingleDefinition; // == Definitions[0] if Kind==VMK_All
};
// VariablesMetadata analyzes and summarizes the metadata for the
@@ -570,7 +577,7 @@
VariablesMetadata(const Cfg *Func) : Func(Func) {}
// Initialize the state by traversing all instructions/variables in
// the CFG.
- void init();
+ void init(MetadataKind TrackingKind);
// Returns whether the given Variable is tracked in this object. It
// should only return false if changes were made to the CFG after
// running init(), in which case the state is stale and the results
@@ -594,7 +601,7 @@
const Inst *getSingleDefinition(const Variable *Var) const;
// Returns the list of all definition instructions of the given
// Variable.
- const InstDefList &getDefinitions(const Variable *Var) const;
+ const InstDefList &getLatterDefinitions(const Variable *Var) const;
// Returns whether the given Variable is live across multiple
// blocks. Mainly, this is used to partition Variables into
@@ -610,6 +617,7 @@
private:
const Cfg *Func;
+ MetadataKind Kind;
std::vector<VariableTracking> Metadata;
const static InstDefList NoDefinitions;
};
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index b5c3315..1b4d0c2 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -32,7 +32,10 @@
bool overlapsDefs(const Cfg *Func, const Variable *Item, const Variable *Var) {
const bool UseTrimmed = true;
VariablesMetadata *VMetadata = Func->getVMetadata();
- const InstDefList &Defs = VMetadata->getDefinitions(Var);
+ if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var))
+ if (Item->getLiveRange().overlapsInst(FirstDef->getNumber(), UseTrimmed))
+ return true;
+ const InstDefList &Defs = VMetadata->getLatterDefinitions(Var);
for (size_t i = 0; i < Defs.size(); ++i) {
if (Item->getLiveRange().overlapsInst(Defs[i]->getNumber(), UseTrimmed))
return true;
@@ -47,11 +50,11 @@
Ostream &Str = Func->getContext()->getStrDump();
Str << "Disabling Overlap due to " << Reason << " " << *Var
<< " LIVE=" << Var->getLiveRange() << " Defs=";
- const InstDefList &Defs = VMetadata->getDefinitions(Var);
+ if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var))
+ Str << FirstDef->getNumber();
+ const InstDefList &Defs = VMetadata->getLatterDefinitions(Var);
for (size_t i = 0; i < Defs.size(); ++i) {
- if (i > 0)
- Str << ",";
- Str << Defs[i]->getNumber();
+ Str << "," << Defs[i]->getNumber();
}
Str << "\n";
}
diff --git a/src/IceTargetLoweringX8632.cpp b/src/IceTargetLoweringX8632.cpp
index dfb1fda..232acdd 100644
--- a/src/IceTargetLoweringX8632.cpp
+++ b/src/IceTargetLoweringX8632.cpp
@@ -329,7 +329,7 @@
Func->dump("After Phi lowering");
// Address mode optimization.
- Func->getVMetadata()->init();
+ Func->getVMetadata()->init(VMK_SingleDefs);
Func->doAddressOpt();
// Argument lowering
@@ -372,7 +372,7 @@
// The post-codegen dump is done here, after liveness analysis and
// associated cleanup, to make the dump cleaner and more useful.
Func->dump("After initial x8632 codegen");
- Func->getVMetadata()->init();
+ Func->getVMetadata()->init(VMK_All);
regAlloc();
if (Func->hasError())
return;
