Subzero: Register allocator performance improvements and simplifications.
This removes the redundancy between live ranges stored in the Variable and those stored in Liveness, by removing the Liveness copy. After liveness analysis, live ranges are constructed directly into the Variable.
Also, the LiveRangeWrapper is removed and Variable * is directly used instead. The original thought behind LiveRangeWrapper was that it could be extended to include live range splitting. However, when/if live range splitting is implemented, it will probably involve creating a new variable with its own live range, and carrying around some extra bookkeeping until the split is committed, so such a wrapper probably won't be needed.
BUG= none
R=jvoung@chromium.org
Review URL: https://codereview.chromium.org/656023002
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index c30e02a..b9deb01 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -219,32 +219,21 @@
// "r=arg1+arg2", both args may be assigned the same register.
for (SizeT I = 0; I < Args.size(); ++I) {
Variable *Arg = Args[I];
- if (!Live->getLiveRange(Arg).isEmpty()) {
+ 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.
- Live->addLiveRange(Arg, -1, 0, 0);
+ Arg->addLiveRange(-1, 0, 0);
}
// Do the same for i64 args that may have been lowered into i32
// Lo and Hi components.
Variable *Lo = Arg->getLo();
- if (Lo && !Live->getLiveRange(Lo).isEmpty())
- Live->addLiveRange(Lo, -1, 0, 0);
+ if (Lo && !Lo->getLiveRange().isEmpty())
+ Lo->addLiveRange(-1, 0, 0);
Variable *Hi = Arg->getHi();
- if (Hi && !Live->getLiveRange(Hi).isEmpty())
- Live->addLiveRange(Hi, -1, 0, 0);
- }
- // Copy Liveness::LiveRanges into individual variables. TODO:
- // Remove Variable::LiveRange and redirect to
- // Liveness::LiveRanges. TODO: make sure Variable weights
- // are applied properly.
- SizeT NumVars = Variables.size();
- for (SizeT i = 0; i < NumVars; ++i) {
- Variable *Var = Variables[i];
- Var->setLiveRange(Live->getLiveRange(Var));
- if (Var->getWeight().isInf())
- Var->setLiveRangeInfiniteWeight();
+ if (Hi && !Hi->getLiveRange().isEmpty())
+ Hi->addLiveRange(-1, 0, 0);
}
}
}
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index 502bec5..767c9c3 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -357,16 +357,6 @@
return Changed;
}
-#ifndef NDEBUG
-namespace {
-
-bool comparePair(const LiveBeginEndMapEntry &A, const LiveBeginEndMapEntry &B) {
- return A.first == B.first;
-}
-
-} // end of anonymous namespace
-#endif // NDEBUG
-
// 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
@@ -406,7 +396,7 @@
for (SizeT Src = 0; Src < NumSrcs; ++Src) {
Variable *Var = llvm::cast<Variable>(I->getSrc(Src));
InstNumberT InstNumber = I->getNumber();
- Liveness->addLiveRange(Var, InstNumber, InstNumber, 1);
+ Var->addLiveRange(InstNumber, InstNumber, 1);
}
}
}
@@ -424,9 +414,15 @@
std::sort(MapBegin.begin(), MapBegin.end());
std::sort(MapEnd.begin(), MapEnd.end());
// Verify there are no duplicates.
- assert(std::adjacent_find(MapBegin.begin(), MapBegin.end(), comparePair) ==
+ struct ComparePair {
+ bool operator()(const LiveBeginEndMapEntry &A,
+ const LiveBeginEndMapEntry &B) {
+ return A.first == B.first;
+ }
+ };
+ assert(std::adjacent_find(MapBegin.begin(), MapBegin.end(), ComparePair()) ==
MapBegin.end());
- assert(std::adjacent_find(MapEnd.begin(), MapEnd.end(), comparePair) ==
+ assert(std::adjacent_find(MapEnd.begin(), MapEnd.end(), ComparePair()) ==
MapEnd.end());
LivenessBV LiveInAndOut = LiveIn;
@@ -453,15 +449,15 @@
Variable *Var = Liveness->getVariable(i, this);
if (!Var->getIgnoreLiveness()) {
if (LB > LE) {
- Liveness->addLiveRange(Var, FirstInstNum, LE, 1);
- Liveness->addLiveRange(Var, LB, LastInstNum + 1, 1);
+ Var->addLiveRange(FirstInstNum, LE, 1);
+ Var->addLiveRange(LB, LastInstNum + 1, 1);
// Assert that Var is a global variable by checking that its
// liveness index is less than the number of globals. This
// ensures that the LiveInAndOut[] access is valid.
assert(i < Liveness->getNumGlobalVars());
LiveInAndOut[i] = false;
} else {
- Liveness->addLiveRange(Var, LB, LE, 1);
+ Var->addLiveRange(LB, LE, 1);
}
}
if (i == i1)
@@ -473,7 +469,7 @@
for (int i = LiveInAndOut.find_first(); i != -1;
i = LiveInAndOut.find_next(i)) {
Variable *Var = Liveness->getVariable(i, this);
- Liveness->addLiveRange(Var, FirstInstNum, LastInstNum + 1, 1);
+ Var->addLiveRange(FirstInstNum, LastInstNum + 1, 1);
}
}
diff --git a/src/IceLiveness.cpp b/src/IceLiveness.cpp
index 0960bd8..79578a5 100644
--- a/src/IceLiveness.cpp
+++ b/src/IceLiveness.cpp
@@ -35,8 +35,6 @@
VariablesMetadata *VMetadata = Func->getVMetadata();
Nodes.resize(NumNodes);
VarToLiveMap.resize(NumVars);
- if (Mode == Liveness_Intervals)
- LiveRanges.resize(NumVars);
// Count the number of globals, and the number of locals for each
// block.
@@ -98,16 +96,4 @@
return Nodes[NodeIndex].LiveToVarMap[LiveIndex - NumGlobals];
}
-void Liveness::addLiveRange(Variable *Var, InstNumberT Start, InstNumberT End,
- uint32_t WeightDelta) {
- LiveRange &LiveRange = LiveRanges[Var->getIndex()];
- assert(WeightDelta != RegWeight::Inf);
- LiveRange.addSegment(Start, End);
- LiveRange.addWeight(WeightDelta);
-}
-
-LiveRange &Liveness::getLiveRange(Variable *Var) {
- return LiveRanges[Var->getIndex()];
-}
-
} // end of namespace Ice
diff --git a/src/IceLiveness.h b/src/IceLiveness.h
index 2949d56..4c6da6c 100644
--- a/src/IceLiveness.h
+++ b/src/IceLiveness.h
@@ -52,6 +52,9 @@
};
class Liveness {
+ Liveness(const Liveness &) = delete;
+ Liveness &operator=(const Liveness &) = delete;
+
public:
Liveness(Cfg *Func, LivenessMode Mode)
: Func(Func), Mode(Mode), NumGlobals(0) {}
@@ -76,9 +79,6 @@
LiveBeginEndMap *getLiveEnd(const CfgNode *Node) {
return &Nodes[Node->getIndex()].LiveEnd;
}
- LiveRange &getLiveRange(Variable *Var);
- void addLiveRange(Variable *Var, InstNumberT Start, InstNumberT End,
- uint32_t WeightDelta);
private:
Cfg *Func;
@@ -92,10 +92,6 @@
// LiveToVarMap is analogous to LivenessNode::LiveToVarMap, but for
// non-local variables.
std::vector<Variable *> LiveToVarMap;
- // LiveRanges maps a Variable::Number to its live range.
- std::vector<LiveRange> LiveRanges;
- Liveness(const Liveness &) = delete;
- Liveness &operator=(const Liveness &) = delete;
};
} // end of namespace Ice
diff --git a/src/IceOperand.h b/src/IceOperand.h
index 9a31606..9d864fc 100644
--- a/src/IceOperand.h
+++ b/src/IceOperand.h
@@ -412,6 +412,7 @@
void setWeight(uint32_t NewWeight) { Weight = NewWeight; }
void setWeightInfinite() { Weight = RegWeight::Inf; }
+ LiveRange &getLiveRange() { return Live; }
const LiveRange &getLiveRange() const { return Live; }
void setLiveRange(const LiveRange &Range) { Live = Range; }
void resetLiveRange() { Live.reset(); }
@@ -426,6 +427,17 @@
void setLiveRangeInfiniteWeight() { Live.setWeight(RegWeight::Inf); }
void trimLiveRange(InstNumberT Start) { Live.trim(Start); }
void untrimLiveRange() { Live.untrim(); }
+ bool rangeEndsBefore(const Variable *Other) const {
+ return Live.endsBefore(Other->Live);
+ }
+ bool rangeOverlaps(const Variable *Other) const {
+ const bool UseTrimmed = true;
+ return Live.overlaps(Other->Live, UseTrimmed);
+ }
+ bool rangeOverlapsStart(const Variable *Other) const {
+ const bool UseTrimmed = true;
+ return Live.overlapsInst(Other->Live.getStart(), UseTrimmed);
+ }
Variable *getLo() const { return LoVar; }
Variable *getHi() const { return HiVar; }
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index 0e1e9b7..b5c3315 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -29,13 +29,12 @@
// 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) {
+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);
for (size_t i = 0; i < Defs.size(); ++i) {
- if (Item.range().overlapsInst(Defs[i]->getNumber(), UseTrimmed))
+ if (Item->getLiveRange().overlapsInst(Defs[i]->getNumber(), UseTrimmed))
return true;
}
return false;
@@ -58,12 +57,14 @@
}
}
-bool compareRanges(const LiveRangeWrapper &L, const LiveRangeWrapper &R) {
- InstNumberT Lstart = L.Var->getLiveRange().getStart();
- InstNumberT Rstart = R.Var->getLiveRange().getStart();
- if (Lstart == Rstart)
- return L.Var->getIndex() < R.Var->getIndex();
- return Lstart < Rstart;
+void dumpLiveRange(const Variable *Var, const Cfg *Func) {
+ Ostream &Str = Func->getContext()->getStrDump();
+ const static size_t BufLen = 30;
+ char buf[BufLen];
+ snprintf(buf, BufLen, "%2d", Var->getRegNumTmp());
+ Str << "R=" << buf << " V=";
+ Var->dump(Func);
+ Str << " Range=" << Var->getLiveRange();
}
} // end of anonymous namespace
@@ -108,18 +109,26 @@
if (Var->getLiveRange().isEmpty())
continue;
Var->untrimLiveRange();
- LiveRangeWrapper R(Var);
- Unhandled.push_back(R);
+ Unhandled.push_back(Var);
if (Var->hasReg()) {
Var->setRegNumTmp(Var->getRegNum());
Var->setLiveRangeInfiniteWeight();
- UnhandledPrecolored.push_back(R);
+ UnhandledPrecolored.push_back(Var);
}
}
+ struct CompareRanges {
+ bool operator()(const Variable *L, const Variable *R) {
+ InstNumberT Lstart = L->getLiveRange().getStart();
+ InstNumberT Rstart = R->getLiveRange().getStart();
+ if (Lstart == Rstart)
+ return L->getIndex() < R->getIndex();
+ return Lstart < Rstart;
+ }
+ };
// Do a reverse sort so that erasing elements (from the end) is fast.
- std::sort(Unhandled.rbegin(), Unhandled.rend(), compareRanges);
+ std::sort(Unhandled.rbegin(), Unhandled.rend(), CompareRanges());
std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(),
- compareRanges);
+ CompareRanges());
}
// RegUses[I] is the number of live ranges (variables) that register
@@ -134,36 +143,35 @@
UnorderedRanges::iterator Next;
while (!Unhandled.empty()) {
- LiveRangeWrapper Cur = Unhandled.back();
+ Variable *Cur = Unhandled.back();
Unhandled.pop_back();
if (Verbose) {
Str << "\nConsidering ";
- Cur.dump(Func);
+ dumpLiveRange(Cur, Func);
Str << "\n";
}
const llvm::SmallBitVector RegMask =
- RegMaskFull &
- Func->getTarget()->getRegisterSetForType(Cur.Var->getType());
+ RegMaskFull & Func->getTarget()->getRegisterSetForType(Cur->getType());
// Check for precolored ranges. If Cur is precolored, it
// definitely gets that register. Previously processed live
// ranges would have avoided that register due to it being
// precolored. Future processed live ranges won't evict that
// register because the live range has infinite weight.
- if (Cur.Var->hasReg()) {
- int32_t RegNum = Cur.Var->getRegNum();
+ if (Cur->hasReg()) {
+ int32_t RegNum = Cur->getRegNum();
// RegNumTmp should have already been set above.
- assert(Cur.Var->getRegNumTmp() == RegNum);
+ assert(Cur->getRegNumTmp() == RegNum);
if (Verbose) {
Str << "Precoloring ";
- Cur.dump(Func);
+ dumpLiveRange(Cur, Func);
Str << "\n";
}
Active.push_back(Cur);
assert(RegUses[RegNum] >= 0);
++RegUses[RegNum];
assert(!UnhandledPrecolored.empty());
- assert(UnhandledPrecolored.back().Var == Cur.Var);
+ assert(UnhandledPrecolored.back() == Cur);
UnhandledPrecolored.pop_back();
continue;
}
@@ -172,23 +180,23 @@
for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) {
Next = I;
++Next;
- LiveRangeWrapper Item = *I;
- Item.Var->trimLiveRange(Cur.range().getStart());
+ Variable *Item = *I;
+ Item->trimLiveRange(Cur->getLiveRange().getStart());
bool Moved = false;
- if (Item.endsBefore(Cur)) {
+ if (Item->rangeEndsBefore(Cur)) {
// Move Item from Active to Handled list.
if (Verbose) {
Str << "Expiring ";
- Item.dump(Func);
+ dumpLiveRange(Item, Func);
Str << "\n";
}
Handled.splice(Handled.end(), Active, I);
Moved = true;
- } else if (!Item.overlapsStart(Cur)) {
+ } else if (!Item->rangeOverlapsStart(Cur)) {
// Move Item from Active to Inactive list.
if (Verbose) {
Str << "Inactivating ";
- Item.dump(Func);
+ dumpLiveRange(Item, Func);
Str << "\n";
}
Inactive.splice(Inactive.end(), Active, I);
@@ -196,8 +204,8 @@
}
if (Moved) {
// Decrement Item from RegUses[].
- assert(Item.Var->hasRegTmp());
- int32_t RegNum = Item.Var->getRegNumTmp();
+ assert(Item->hasRegTmp());
+ int32_t RegNum = Item->getRegNumTmp();
--RegUses[RegNum];
assert(RegUses[RegNum] >= 0);
}
@@ -207,36 +215,36 @@
for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) {
Next = I;
++Next;
- LiveRangeWrapper Item = *I;
- Item.Var->trimLiveRange(Cur.range().getStart());
+ Variable *Item = *I;
+ Item->trimLiveRange(Cur->getLiveRange().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, and the rangeEndsBefore() 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())
+ if (!Item->getLiveRange().isNonpoints())
continue;
- if (Item.endsBefore(Cur)) {
+ if (Item->rangeEndsBefore(Cur)) {
// Move Item from Inactive to Handled list.
if (Verbose) {
Str << "Expiring ";
- Item.dump(Func);
+ dumpLiveRange(Item, Func);
Str << "\n";
}
Handled.splice(Handled.end(), Inactive, I);
- } else if (Item.overlapsStart(Cur)) {
+ } else if (Item->rangeOverlapsStart(Cur)) {
// Move Item from Inactive to Active list.
if (Verbose) {
Str << "Reactivating ";
- Item.dump(Func);
+ dumpLiveRange(Item, Func);
Str << "\n";
}
Active.splice(Active.end(), Inactive, I);
// Increment Item in RegUses[].
- assert(Item.Var->hasRegTmp());
- int32_t RegNum = Item.Var->getRegNumTmp();
+ assert(Item->hasRegTmp());
+ int32_t RegNum = Item->getRegNumTmp();
assert(RegUses[RegNum] >= 0);
++RegUses[RegNum];
}
@@ -263,10 +271,10 @@
Variable *Prefer = NULL;
int32_t PreferReg = Variable::NoRegister;
bool AllowOverlap = false;
- if (const Inst *DefInst = VMetadata->getFirstDefinition(Cur.Var)) {
- assert(DefInst->getDest() == Cur.Var);
+ if (const Inst *DefInst = VMetadata->getFirstDefinition(Cur)) {
+ assert(DefInst->getDest() == Cur);
bool IsAssign = DefInst->isSimpleAssign();
- bool IsSingleDef = !VMetadata->isMultiDef(Cur.Var);
+ bool IsSingleDef = !VMetadata->isMultiDef(Cur);
for (SizeT i = 0; i < DefInst->getSrcSize(); ++i) {
// TODO(stichnot): Iterate through the actual Variables of the
// instruction, not just the source operands. This could
@@ -303,9 +311,9 @@
// Remove registers from the Free[] list where an Inactive range
// overlaps with the current range.
- for (const LiveRangeWrapper &Item : Inactive) {
- if (Item.overlaps(Cur)) {
- int32_t RegNum = Item.Var->getRegNumTmp();
+ for (const Variable *Item : Inactive) {
+ if (Item->rangeOverlaps(Cur)) {
+ int32_t RegNum = Item->getRegNumTmp();
// Don't assert(Free[RegNum]) because in theory (though
// probably never in practice) there could be two inactive
// variables that were marked with AllowOverlap.
@@ -313,10 +321,10 @@
// Disable AllowOverlap if an Inactive variable, which is not
// Prefer, shares Prefer's register, and has a definition
// within Cur's live range.
- if (AllowOverlap && Item.Var != Prefer && RegNum == PreferReg &&
- overlapsDefs(Func, Cur, Item.Var)) {
+ if (AllowOverlap && Item != Prefer && RegNum == PreferReg &&
+ overlapsDefs(Func, Cur, Item)) {
AllowOverlap = false;
- dumpDisableOverlap(Func, Item.Var, "Inactive");
+ dumpDisableOverlap(Func, Item, "Inactive");
}
}
}
@@ -324,12 +332,12 @@
// Disable AllowOverlap if an Active variable, which is not
// Prefer, shares Prefer's register, and has a definition within
// Cur's live range.
- for (const LiveRangeWrapper &Item : Active) {
- int32_t RegNum = Item.Var->getRegNumTmp();
- if (Item.Var != Prefer && RegNum == PreferReg &&
- overlapsDefs(Func, Cur, Item.Var)) {
+ for (const Variable *Item : Active) {
+ int32_t RegNum = Item->getRegNumTmp();
+ if (Item != Prefer && RegNum == PreferReg &&
+ overlapsDefs(Func, Cur, Item)) {
AllowOverlap = false;
- dumpDisableOverlap(Func, Item.Var, "Active");
+ dumpDisableOverlap(Func, Item, "Active");
}
}
@@ -338,19 +346,19 @@
// Remove registers from the Free[] list where an Unhandled
// precolored range overlaps with the current range, and set those
// registers to infinite weight so that they aren't candidates for
- // eviction. Cur.endsBefore(Item) is an early exit check that
- // turns a guaranteed O(N^2) algorithm into expected linear
+ // eviction. Cur->rangeEndsBefore(Item) is an early exit check
+ // that turns a guaranteed O(N^2) algorithm into expected linear
// complexity.
llvm::SmallBitVector PrecoloredUnhandledMask(RegMask.size());
// Note: PrecoloredUnhandledMask is only used for dumping.
for (auto I = UnhandledPrecolored.rbegin(), E = UnhandledPrecolored.rend();
I != E; ++I) {
- LiveRangeWrapper &Item = *I;
- assert(Item.Var->hasReg());
- if (Cur.endsBefore(Item))
+ Variable *Item = *I;
+ assert(Item->hasReg());
+ if (Cur->rangeEndsBefore(Item))
break;
- if (Item.overlaps(Cur)) {
- int32_t ItemReg = Item.Var->getRegNum(); // Note: not getRegNumTmp()
+ if (Item->rangeOverlaps(Cur)) {
+ int32_t ItemReg = Item->getRegNum(); // Note: not getRegNumTmp()
Weights[ItemReg].setWeight(RegWeight::Inf);
Free[ItemReg] = false;
PrecoloredUnhandledMask[ItemReg] = true;
@@ -358,7 +366,7 @@
// these precolored unhandled overlapping ranges.
if (AllowOverlap && ItemReg == PreferReg) {
AllowOverlap = false;
- dumpDisableOverlap(Func, Item.Var, "PrecoloredUnhandled");
+ dumpDisableOverlap(Func, Item, "PrecoloredUnhandled");
}
}
}
@@ -378,10 +386,10 @@
if (Prefer && (AllowOverlap || Free[PreferReg])) {
// First choice: a preferred register that is either free or is
// allowed to overlap with its linked variable.
- Cur.Var->setRegNumTmp(PreferReg);
+ Cur->setRegNumTmp(PreferReg);
if (Verbose) {
Str << "Preferring ";
- Cur.dump(Func);
+ dumpLiveRange(Cur, Func);
Str << "\n";
}
assert(RegUses[PreferReg] >= 0);
@@ -392,10 +400,10 @@
// affinity is considered, is there a strategy better than just
// picking the lowest-numbered available register?
int32_t RegNum = Free.find_first();
- Cur.Var->setRegNumTmp(RegNum);
+ Cur->setRegNumTmp(RegNum);
if (Verbose) {
Str << "Allocating ";
- Cur.dump(Func);
+ dumpLiveRange(Cur, Func);
Str << "\n";
}
assert(RegUses[RegNum] >= 0);
@@ -405,18 +413,18 @@
// Fallback: there are no free registers, so we look for the
// lowest-weight register and see if Cur has higher weight.
// Check Active ranges.
- for (const LiveRangeWrapper &Item : Active) {
- assert(Item.overlaps(Cur));
- int32_t RegNum = Item.Var->getRegNumTmp();
- assert(Item.Var->hasRegTmp());
- Weights[RegNum].addWeight(Item.range().getWeight());
+ for (const Variable *Item : Active) {
+ assert(Item->rangeOverlaps(Cur));
+ int32_t RegNum = Item->getRegNumTmp();
+ assert(Item->hasRegTmp());
+ Weights[RegNum].addWeight(Item->getLiveRange().getWeight());
}
// Same as above, but check Inactive ranges instead of Active.
- for (const LiveRangeWrapper &Item : Inactive) {
- int32_t RegNum = Item.Var->getRegNumTmp();
- assert(Item.Var->hasRegTmp());
- if (Item.overlaps(Cur))
- Weights[RegNum].addWeight(Item.range().getWeight());
+ for (const Variable *Item : Inactive) {
+ int32_t RegNum = Item->getRegNumTmp();
+ assert(Item->hasRegTmp());
+ if (Item->rangeOverlaps(Cur))
+ Weights[RegNum].addWeight(Item->getLiveRange().getWeight());
}
// All the weights are now calculated. Find the register with
@@ -430,12 +438,12 @@
MinWeightIndex = i;
}
- if (Cur.range().getWeight() <= Weights[MinWeightIndex]) {
+ if (Cur->getLiveRange().getWeight() <= Weights[MinWeightIndex]) {
// Cur doesn't have priority over any other live ranges, so
// don't allocate any register to it, and move it to the
// Handled state.
Handled.push_back(Cur);
- if (Cur.range().getWeight().isInf()) {
+ if (Cur->getLiveRange().getWeight().isInf()) {
Func->setError("Unable to find a physical register for an "
"infinite-weight live range");
}
@@ -445,16 +453,16 @@
for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) {
Next = I;
++Next;
- LiveRangeWrapper Item = *I;
- if (Item.Var->getRegNumTmp() == MinWeightIndex) {
+ Variable *Item = *I;
+ if (Item->getRegNumTmp() == MinWeightIndex) {
if (Verbose) {
Str << "Evicting ";
- Item.dump(Func);
+ dumpLiveRange(Item, Func);
Str << "\n";
}
--RegUses[MinWeightIndex];
assert(RegUses[MinWeightIndex] >= 0);
- Item.Var->setRegNumTmp(Variable::NoRegister);
+ Item->setRegNumTmp(Variable::NoRegister);
Handled.splice(Handled.end(), Active, I);
}
}
@@ -462,8 +470,8 @@
for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) {
Next = I;
++Next;
- LiveRangeWrapper Item = *I;
- // Note: The Item.overlaps(Cur) clause is not part of the
+ Variable *Item = *I;
+ // Note: The Item->rangeOverlaps(Cur) clause is not part of the
// description of AssignMemLoc() in the original paper. But
// there doesn't seem to be any need to evict an inactive
// live range that doesn't overlap with the live range
@@ -472,25 +480,25 @@
// currently-inactive live range. The most common situation
// for this would be a scratch register kill set for call
// instructions.
- if (Item.Var->getRegNumTmp() == MinWeightIndex &&
- Item.overlaps(Cur)) {
+ if (Item->getRegNumTmp() == MinWeightIndex &&
+ Item->rangeOverlaps(Cur)) {
if (Verbose) {
Str << "Evicting ";
- Item.dump(Func);
+ dumpLiveRange(Item, Func);
Str << "\n";
}
- Item.Var->setRegNumTmp(Variable::NoRegister);
+ Item->setRegNumTmp(Variable::NoRegister);
Handled.splice(Handled.end(), Inactive, I);
}
}
// Assign the register to Cur.
- Cur.Var->setRegNumTmp(MinWeightIndex);
+ Cur->setRegNumTmp(MinWeightIndex);
assert(RegUses[MinWeightIndex] >= 0);
++RegUses[MinWeightIndex];
Active.push_back(Cur);
if (Verbose) {
Str << "Allocating ";
- Cur.dump(Func);
+ dumpLiveRange(Cur, Func);
Str << "\n";
}
}
@@ -498,31 +506,31 @@
dump(Func);
}
// Move anything Active or Inactive to Handled for easier handling.
- for (const LiveRangeWrapper &I : Active)
+ for (Variable *I : Active)
Handled.push_back(I);
Active.clear();
- for (const LiveRangeWrapper &I : Inactive)
+ for (Variable *I : Inactive)
Handled.push_back(I);
Inactive.clear();
dump(Func);
// Finish up by assigning RegNumTmp->RegNum for each Variable.
- for (const LiveRangeWrapper &Item : Handled) {
- int32_t RegNum = Item.Var->getRegNumTmp();
+ for (Variable *Item : Handled) {
+ int32_t RegNum = Item->getRegNumTmp();
if (Verbose) {
- if (!Item.Var->hasRegTmp()) {
+ if (!Item->hasRegTmp()) {
Str << "Not assigning ";
- Item.Var->dump(Func);
+ Item->dump(Func);
Str << "\n";
} else {
- Str << (RegNum == Item.Var->getRegNum() ? "Reassigning " : "Assigning ")
+ Str << (RegNum == Item->getRegNum() ? "Reassigning " : "Assigning ")
<< Func->getTarget()->getRegName(RegNum, IceType_i32) << "(r"
<< RegNum << ") to ";
- Item.Var->dump(Func);
+ Item->dump(Func);
Str << "\n";
}
}
- Item.Var->setRegNum(Item.Var->getRegNumTmp());
+ Item->setRegNum(Item->getRegNumTmp());
}
// TODO: Consider running register allocation one more time, with
@@ -539,16 +547,6 @@
// ======================== Dump routines ======================== //
-void LiveRangeWrapper::dump(const Cfg *Func) const {
- Ostream &Str = Func->getContext()->getStrDump();
- const static size_t BufLen = 30;
- char buf[BufLen];
- snprintf(buf, BufLen, "%2d", Var->getRegNumTmp());
- Str << "R=" << buf << " V=";
- Var->dump(Func);
- Str << " Range=" << range();
-}
-
void LinearScan::dump(Cfg *Func) const {
Ostream &Str = Func->getContext()->getStrDump();
if (!Func->getContext()->isVerbose(IceV_LinearScan))
@@ -556,23 +554,23 @@
Func->resetCurrentNode();
Str << "**** Current regalloc state:\n";
Str << "++++++ Handled:\n";
- for (const LiveRangeWrapper &Item : Handled) {
- Item.dump(Func);
+ for (const Variable *Item : Handled) {
+ dumpLiveRange(Item, Func);
Str << "\n";
}
Str << "++++++ Unhandled:\n";
for (auto I = Unhandled.rbegin(), E = Unhandled.rend(); I != E; ++I) {
- I->dump(Func);
+ dumpLiveRange(*I, Func);
Str << "\n";
}
Str << "++++++ Active:\n";
- for (const LiveRangeWrapper &Item : Active) {
- Item.dump(Func);
+ for (const Variable *Item : Active) {
+ dumpLiveRange(Item, Func);
Str << "\n";
}
Str << "++++++ Inactive:\n";
- for (const LiveRangeWrapper &Item : Inactive) {
- Item.dump(Func);
+ for (const Variable *Item : Inactive) {
+ dumpLiveRange(Item, Func);
Str << "\n";
}
}
diff --git a/src/IceRegAlloc.h b/src/IceRegAlloc.h
index f181a27..0742cc1 100644
--- a/src/IceRegAlloc.h
+++ b/src/IceRegAlloc.h
@@ -7,10 +7,9 @@
//
//===----------------------------------------------------------------------===//
//
-// This file declares the data structures used during linear-scan
-// register allocation. This includes LiveRangeWrapper which
-// encapsulates a variable and its live range, and LinearScan which
-// holds the various work queues for the linear-scan algorithm.
+// This file declares the LinearScan data structure used during
+// linear-scan register allocation, which holds the various work
+// queues for the linear-scan algorithm.
//
//===----------------------------------------------------------------------===//
@@ -22,34 +21,10 @@
namespace Ice {
-// Currently this just wraps a Variable pointer, so in principle we
-// could use containers of Variable* instead of LiveRangeWrapper. But
-// in the future, we may want to do more complex things such as live
-// range splitting, and keeping a wrapper should make that simpler.
-class LiveRangeWrapper {
-public:
- LiveRangeWrapper(Variable *Var) : Var(Var) {}
- const LiveRange &range() const { return Var->getLiveRange(); }
- bool endsBefore(const LiveRangeWrapper &Other) const {
- return range().endsBefore(Other.range());
- }
- bool overlaps(const LiveRangeWrapper &Other) const {
- const bool UseTrimmed = true;
- return range().overlaps(Other.range(), UseTrimmed);
- }
- bool overlapsStart(const LiveRangeWrapper &Other) const {
- const bool UseTrimmed = true;
- return range().overlapsInst(Other.range().getStart(), UseTrimmed);
- }
- Variable *Var;
- void dump(const Cfg *Func) const;
-
-private:
- // LiveRangeWrapper(const LiveRangeWrapper &) = delete;
- // LiveRangeWrapper &operator=(const LiveRangeWrapper &) = delete;
-};
-
class LinearScan {
+ LinearScan(const LinearScan &) = delete;
+ LinearScan &operator=(const LinearScan &) = delete;
+
public:
LinearScan(Cfg *Func) : Func(Func) {}
void scan(const llvm::SmallBitVector &RegMask);
@@ -57,15 +32,13 @@
private:
Cfg *const Func;
- typedef std::vector<LiveRangeWrapper> OrderedRanges;
- typedef std::list<LiveRangeWrapper> UnorderedRanges;
+ typedef std::vector<Variable *> OrderedRanges;
+ typedef std::list<Variable *> UnorderedRanges;
OrderedRanges Unhandled;
// UnhandledPrecolored is a subset of Unhandled, specially collected
// for faster processing.
OrderedRanges UnhandledPrecolored;
UnorderedRanges Active, Inactive, Handled;
- LinearScan(const LinearScan &) = delete;
- LinearScan &operator=(const LinearScan &) = delete;
};
} // end of namespace Ice
