Subzero: Optimize live range overlaps() computation through trimming.
The main optimization is for the repeated overlaps() calls against the Inactive set, by iteratively trimming away the early sections of the Inactive live ranges that can no longer overlap with Cur.
A more minor optimization doesn't bother checking pure point-valued Inactive ranges for expiring or reactivating.
BUG= none
R=jvoung@chromium.org
Review URL: https://codereview.chromium.org/627203002
diff --git a/src/IceOperand.cpp b/src/IceOperand.cpp
index c631e80..9ecfd31 100644
--- a/src/IceOperand.cpp
+++ b/src/IceOperand.cpp
@@ -105,10 +105,11 @@
}
// Returns true if there is any overlap between the two live ranges.
-bool LiveRange::overlaps(const LiveRange &Other) const {
+bool LiveRange::overlaps(const LiveRange &Other, bool UseTrimmed) const {
// Do a two-finger walk through the two sorted lists of segments.
- RangeType::const_iterator I1 = Range.begin(), I2 = Other.Range.begin();
- RangeType::const_iterator E1 = Range.end(), E2 = Other.Range.end();
+ auto I1 = (UseTrimmed ? TrimmedBegin : Range.begin()),
+ I2 = (UseTrimmed ? Other.TrimmedBegin : Other.Range.begin());
+ auto E1 = Range.end(), E2 = Other.Range.end();
while (I1 != E1 && I2 != E2) {
if (I1->second <= I2->first) {
++I1;
@@ -123,16 +124,17 @@
return false;
}
-bool LiveRange::overlaps(InstNumberT OtherBegin) const {
+bool LiveRange::overlapsInst(InstNumberT OtherBegin, bool UseTrimmed) const {
if (!IsNonpoints)
return false;
bool Result = false;
- for (const RangeElementType &I : Range) {
- if (OtherBegin < I.first) {
+ for (auto I = (UseTrimmed ? TrimmedBegin : Range.begin()), E = Range.end();
+ I != E; ++I) {
+ if (OtherBegin < I->first) {
Result = false;
break;
}
- if (OtherBegin < I.second) {
+ if (OtherBegin < I->second) {
Result = true;
break;
}
@@ -158,6 +160,11 @@
return false;
}
+void LiveRange::trim(InstNumberT Lower) {
+ while (TrimmedBegin != Range.end() && TrimmedBegin->second <= Lower)
+ ++TrimmedBegin;
+}
+
IceString Variable::getName() const {
if (!Name.empty())
return Name;
@@ -221,6 +228,9 @@
// 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);
const bool IsFromDef = true;
const bool IsImplicit = false;
diff --git a/src/IceOperand.h b/src/IceOperand.h
index 798da0b..cbe0095 100644
--- a/src/IceOperand.h
+++ b/src/IceOperand.h
@@ -303,19 +303,24 @@
void reset() {
Range.clear();
Weight.setWeight(0);
+ untrim();
IsNonpoints = false;
}
void addSegment(InstNumberT Start, InstNumberT End);
bool endsBefore(const LiveRange &Other) const;
- bool overlaps(const LiveRange &Other) const;
- bool overlaps(InstNumberT OtherBegin) const;
+ bool overlaps(const LiveRange &Other, bool UseTrimmed = false) const;
+ bool overlapsInst(InstNumberT OtherBegin, bool UseTrimmed = false) const;
bool containsValue(InstNumberT Value) const;
bool isEmpty() const { return Range.empty(); }
+ bool isNonpoints() const { return IsNonpoints; }
InstNumberT getStart() const {
return Range.empty() ? -1 : Range.begin()->first;
}
+ void untrim() { TrimmedBegin = Range.begin(); }
+ void trim(InstNumberT Lower);
+
RegWeight getWeight() const { return Weight; }
void setWeight(const RegWeight &NewWeight) { Weight = NewWeight; }
void addWeight(uint32_t Delta) { Weight.addWeight(Delta); }
@@ -336,6 +341,15 @@
#endif
RangeType Range;
RegWeight Weight;
+ // TrimmedBegin is an optimization for the overlaps() computation.
+ // Since the linear-scan algorithm always calls it as overlaps(Cur)
+ // and Cur advances monotonically according to live range start, we
+ // can optimize overlaps() by ignoring all segments that end before
+ // the start of Cur's range. The linear-scan code enables this by
+ // calling trim() on the ranges of interest as Cur advances. Note
+ // that linear-scan also has to initialize TrimmedBegin at the
+ // beginning by calling untrim().
+ RangeType::const_iterator TrimmedBegin;
// IsNonpoints keeps track of whether the live range contains at
// least one interval where Start!=End. If it is empty or has the
// form [x,x),[y,y),...,[z,z), then overlaps(InstNumberT) is
@@ -404,6 +418,8 @@
Live.addWeight(WeightDelta * Weight.getWeight());
}
void setLiveRangeInfiniteWeight() { Live.setWeight(RegWeight::Inf); }
+ void trimLiveRange(InstNumberT Start) { Live.trim(Start); }
+ void untrimLiveRange() { Live.untrim(); }
Variable *getLo() const { return LoVar; }
Variable *getHi() const { return HiVar; }
@@ -509,10 +525,8 @@
MultiBlockState MultiBlock;
const CfgNode *SingleUseNode;
const CfgNode *SingleDefNode;
- // All definitions of the variable are collected here, in the order
- // encountered. Definitions in the same basic block are in
- // instruction order, but there's no guarantee for the basic block
- // order.
+ // All definitions of the variable are collected here, in increasing
+ // order of instruction number.
InstDefList Definitions;
};
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index 2d00db0..14e08d2 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -24,11 +24,18 @@
namespace {
// Returns true if Var has any definitions within Item's live range.
+// TODO(stichnot): Consider trimming the Definitions list similar to
+// how the live ranges are trimmed, since all the overlapsDefs() tests
+// are whether some variable's definitions overlap Cur, and trimming
+// is with respect Cur.start. Initial tests show no measurable
+// performance difference, so we'll keep the code simple for now.
bool overlapsDefs(const Cfg *Func, const LiveRangeWrapper &Item,
const Variable *Var) {
- const InstDefList &Defs = Func->getVMetadata()->getDefinitions(Var);
+ const bool UseTrimmed = true;
+ VariablesMetadata *VMetadata = Func->getVMetadata();
+ const InstDefList &Defs = VMetadata->getDefinitions(Var);
for (size_t i = 0; i < Defs.size(); ++i) {
- if (Item.range().overlaps(Defs[i]->getNumber()))
+ if (Item.range().overlapsInst(Defs[i]->getNumber(), UseTrimmed))
return true;
}
return false;
@@ -37,10 +44,11 @@
void dumpDisableOverlap(const Cfg *Func, const Variable *Var,
const char *Reason) {
if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+ VariablesMetadata *VMetadata = Func->getVMetadata();
Ostream &Str = Func->getContext()->getStrDump();
Str << "Disabling Overlap due to " << Reason << " " << *Var
<< " LIVE=" << Var->getLiveRange() << " Defs=";
- const InstDefList &Defs = Func->getVMetadata()->getDefinitions(Var);
+ const InstDefList &Defs = VMetadata->getDefinitions(Var);
for (size_t i = 0; i < Defs.size(); ++i) {
if (i > 0)
Str << ",";
@@ -95,6 +103,7 @@
// it was never referenced.
if (Var->getLiveRange().isEmpty())
continue;
+ Var->untrimLiveRange();
LiveRangeWrapper R(Var);
Unhandled.insert(R);
if (Var->hasReg()) {
@@ -156,6 +165,7 @@
Next = I;
++Next;
LiveRangeWrapper Item = *I;
+ Item.Var->trimLiveRange(Cur.range().getStart());
bool Moved = false;
if (Item.endsBefore(Cur)) {
// Move Item from Active to Handled list.
@@ -192,6 +202,16 @@
Next = I;
++Next;
LiveRangeWrapper Item = *I;
+ Item.Var->trimLiveRange(Cur.range().getStart());
+ // As an optimization, don't bother checking pure point-valued
+ // Inactive ranges, because the overlapsStart() test will never
+ // succeed, and the endsBefore() test will generally only
+ // succeed after the last call instruction, which statistically
+ // happens near the end. TODO(stichnot): Consider suppressing
+ // this check every N iterations in case calls are only at the
+ // beginning of the function.
+ if (!Item.range().isNonpoints())
+ continue;
if (Item.endsBefore(Cur)) {
// Move Item from Inactive to Handled list.
if (Verbose) {
diff --git a/src/IceRegAlloc.h b/src/IceRegAlloc.h
index 99ed908..2dd9dac 100644
--- a/src/IceRegAlloc.h
+++ b/src/IceRegAlloc.h
@@ -34,10 +34,12 @@
return range().endsBefore(Other.range());
}
bool overlaps(const LiveRangeWrapper &Other) const {
- return range().overlaps(Other.range());
+ const bool UseTrimmed = true;
+ return range().overlaps(Other.range(), UseTrimmed);
}
bool overlapsStart(const LiveRangeWrapper &Other) const {
- return range().overlaps(Other.range().getStart());
+ const bool UseTrimmed = true;
+ return range().overlapsInst(Other.range().getStart(), UseTrimmed);
}
Variable *const Var;
void dump(const Cfg *Func) const;
