Subzero: Implement InstList in terms of llvm::ilist<> .
Use LLVM's intrusive list ADT template to implement instruction lists. This embeds prev/next pointers into the instruction, and as such, iterators essentially double as instruction pointers. This means stripping off one level of indirection when dereferencing, and also the range-based for loop can't be used.
The performance difference in translation time seems to be 1-2%.
I tried to also do this for the much less used PhiList and AssignList, but ran into SFINAE problems.
BUG= none
R=jvoung@chromium.org
Review URL: https://codereview.chromium.org/709533002
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index 8e73499..b461d68 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -318,7 +318,8 @@
Ostream &Str = Ctx->getStrDump();
for (CfgNode *Node : Nodes) {
Inst *FirstInst = NULL;
- for (Inst *Inst : Node->getInsts()) {
+ for (auto Inst = Node->getInsts().begin(), E = Node->getInsts().end();
+ Inst != E; ++Inst) {
if (Inst->isDeleted())
continue;
if (FirstInst == NULL)
@@ -337,7 +338,8 @@
// 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() &&
+ if (static_cast<class Inst *>(Inst) != FirstInst &&
+ !Inst->isDestNonKillable() &&
Dest->getLiveRange().containsValue(InstNumber - 1, IsDest))
Invalid = true;
if (Invalid) {
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index 543f4e9..07246a2 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -59,7 +59,7 @@
InstNumberT FirstNumber = Func->getNextInstNumber();
for (InstPhi *I : Phis)
I->renumber(Func);
- for (Inst *I : Insts)
+ for (auto I = Insts.begin(), E = Insts.end(); I != E; ++I)
I->renumber(Func);
InstCountEstimate = Func->getNextInstNumber() - FirstNumber;
}
@@ -69,7 +69,7 @@
// constructed, the computePredecessors() pass finalizes it by
// creating the InEdges list.
void CfgNode::computePredecessors() {
- OutEdges = (*Insts.rbegin())->getTerminatorEdges();
+ OutEdges = Insts.rbegin()->getTerminatorEdges();
for (CfgNode *Succ : OutEdges)
Succ->InEdges.push_back(this);
}
@@ -117,7 +117,7 @@
// Confirm that InsertionPoint is a terminator instruction. Calling
// getTerminatorEdges() on a non-terminator instruction will cause
// an llvm_unreachable().
- (void)(*InsertionPoint)->getTerminatorEdges();
+ (void)InsertionPoint->getTerminatorEdges();
// SafeInsertionPoint is always immediately before the terminator
// instruction. If the block ends in a compare and conditional
// branch, it's better to place the Phi store before the compare so
@@ -167,13 +167,13 @@
// instruction, and the previous instruction is a compare
// instruction, then we move the insertion point before the compare
// instruction so as not to interfere with compare/branch fusing.
- if (InstBr *Branch = llvm::dyn_cast<InstBr>(*InsertionPoint)) {
+ if (InstBr *Branch = llvm::dyn_cast<InstBr>(InsertionPoint)) {
if (!Branch->isUnconditional()) {
if (InsertionPoint != Insts.begin()) {
--InsertionPoint;
- if (llvm::isa<InstIcmp>(*InsertionPoint) ||
- llvm::isa<InstFcmp>(*InsertionPoint)) {
- CmpInstDest = (*InsertionPoint)->getDest();
+ if (llvm::isa<InstIcmp>(InsertionPoint) ||
+ llvm::isa<InstFcmp>(InsertionPoint)) {
+ CmpInstDest = InsertionPoint->getDest();
} else {
++InsertionPoint;
}
@@ -250,8 +250,8 @@
Found = false;
for (auto I = Pred->getInsts().rbegin(), E = Pred->getInsts().rend();
!Found && I != E; ++I) {
- if (!(*I)->isDeleted()) {
- Found = (*I)->repointEdge(this, NewNode);
+ if (!I->isDeleted()) {
+ Found = I->repointEdge(this, NewNode);
}
}
assert(Found);
@@ -530,9 +530,9 @@
// Process regular instructions in reverse order.
// TODO(stichnot): Use llvm::make_range with LLVM 3.5.
for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) {
- if ((*I)->isDeleted())
+ if (I->isDeleted())
continue;
- (*I)->livenessLightweight(Func, Live);
+ I->livenessLightweight(Func, Live);
}
for (InstPhi *I : Phis) {
if (I->isDeleted())
@@ -573,9 +573,9 @@
// Process regular instructions in reverse order.
for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) {
- if ((*I)->isDeleted())
+ if (I->isDeleted())
continue;
- (*I)->liveness((*I)->getNumber(), Live, Liveness, LiveBegin, LiveEnd);
+ I->liveness(I->getNumber(), Live, Liveness, LiveBegin, LiveEnd);
}
// Process phis in forward order so that we can override the
// instruction number to be that of the earliest phi instruction in
@@ -654,7 +654,7 @@
LastInstNum = I->getNumber();
}
// Process instructions
- for (Inst *I : Insts) {
+ for (auto I = Insts.begin(), E = Insts.end(); I != E; ++I) {
I->deleteIfDead();
if (I->isDeleted())
continue;
@@ -753,7 +753,7 @@
if (InEdges.empty())
return;
Inst *Branch = NULL;
- for (Inst *I : Insts) {
+ for (auto I = Insts.begin(), E = Insts.end(); I != E; ++I) {
if (I->isDeleted())
continue;
if (I->isUnconditionalBranch())
@@ -776,7 +776,8 @@
OutEdges.front()->InEdges.push_back(Pred);
}
}
- for (Inst *I : Pred->getInsts()) {
+ for (auto I = Pred->getInsts().begin(), E = Pred->getInsts().end();
+ I != E; ++I) {
if (!I->isDeleted())
I->repointEdge(this, OutEdges.front());
}
@@ -795,7 +796,7 @@
// first opportunity, unless there is some target lowering where we
// have the possibility of multiple such optimizations per block
// (currently not the case for x86 lowering).
- for (Inst *I : Insts) {
+ for (auto I = Insts.begin(), E = Insts.end(); I != E; ++I) {
if (!I->isDeleted()) {
Target->doBranchOpt(I, NextNode);
}
@@ -901,7 +902,7 @@
Inst *Instr = Phi;
Instr->emit(Func);
}
- for (Inst *I : Insts) {
+ for (auto I = Insts.begin(), E = Insts.end(); I != E; ++I) {
if (I->isDeleted())
continue;
if (I->isRedundantAssign()) {
@@ -931,7 +932,7 @@
Inst *Instr = Phi;
Instr->emitIAS(Func);
}
- for (Inst *I : Insts) {
+ for (auto I = Insts.begin(), E = Insts.end(); I != E; ++I) {
if (I->isDeleted())
continue;
if (I->isRedundantAssign())
@@ -982,7 +983,7 @@
if (Func->getContext()->isVerbose(IceV_Instructions)) {
for (InstPhi *I : Phis)
I->dumpDecorated(Func);
- for (Inst *I : Insts)
+ for (auto I = Insts.begin(), E = Insts.end(); I != E; ++I)
I->dumpDecorated(Func);
}
// Dump the live-out variables.
diff --git a/src/IceCfgNode.h b/src/IceCfgNode.h
index 9cde8c1..279b07f 100644
--- a/src/IceCfgNode.h
+++ b/src/IceCfgNode.h
@@ -17,6 +17,7 @@
#define SUBZERO_SRC_ICECFGNODE_H
#include "IceDefs.h"
+#include "IceInst.h" // InstList traits
namespace Ice {
diff --git a/src/IceDefs.h b/src/IceDefs.h
index 2f0547e..9812e3e 100644
--- a/src/IceDefs.h
+++ b/src/IceDefs.h
@@ -28,6 +28,8 @@
#include <vector>
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/ilist.h"
+#include "llvm/ADT/ilist_node.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Casting.h"
@@ -56,7 +58,7 @@
// TODO: Switch over to LLVM's ADT container classes.
// http://llvm.org/docs/ProgrammersManual.html#picking-the-right-data-structure-for-a-task
typedef std::string IceString;
-typedef std::list<Inst *> InstList;
+typedef llvm::ilist<Inst> InstList;
typedef std::list<InstAssign *> AssignList;
typedef std::list<InstPhi *> PhiList;
typedef std::vector<Variable *> VarList;
diff --git a/src/IceInst.h b/src/IceInst.h
index 7c96e3f..71da0b3 100644
--- a/src/IceInst.h
+++ b/src/IceInst.h
@@ -34,7 +34,7 @@
// InstHighLevel and InstTarget. High-level ICE instructions inherit
// from InstHighLevel, and low-level (target-specific) ICE
// instructions inherit from InstTarget.
-class Inst {
+class Inst : public llvm::ilist_node<Inst> {
Inst(const Inst &) = delete;
Inst &operator=(const Inst &) = delete;
@@ -838,4 +838,22 @@
} // end of namespace Ice
+// Override the default ilist traits so that Inst's private ctor and
+// deleted dtor aren't invoked.
+template <>
+struct llvm::ilist_traits<Ice::Inst> : public llvm::ilist_default_traits<
+ Ice::Inst> {
+ Ice::Inst *createSentinel() const {
+ return static_cast<Ice::Inst *>(&Sentinel);
+ }
+ static void destroySentinel(Ice::Inst *) {}
+ Ice::Inst *provideInitialHead() const { return createSentinel(); }
+ Ice::Inst *ensureHead(Ice::Inst *) const { return createSentinel(); }
+ static void noteHead(Ice::Inst *, Ice::Inst *) {}
+ void deleteNode(Ice::Inst *) {}
+
+private:
+ mutable ilist_half_node<Ice::Inst> Sentinel;
+};
+
#endif // SUBZERO_SRC_ICEINST_H
diff --git a/src/IceOperand.cpp b/src/IceOperand.cpp
index 8cf181a..7870d180 100644
--- a/src/IceOperand.cpp
+++ b/src/IceOperand.cpp
@@ -347,7 +347,8 @@
}
}
- for (Inst *I : Node->getInsts()) {
+ for (auto I = Node->getInsts().begin(), E = Node->getInsts().end(); I != E;
+ ++I) {
if (I->isDeleted())
continue;
// Note: The implicit definitions (and uses) from InstFakeKill are
diff --git a/src/IceTargetLowering.cpp b/src/IceTargetLowering.cpp
index 350605b..5661ad9 100644
--- a/src/IceTargetLowering.cpp
+++ b/src/IceTargetLowering.cpp
@@ -62,7 +62,7 @@
}
void LoweringContext::skipDeleted(InstList::iterator &I) const {
- while (I != End && (*I)->isDeleted())
+ while (I != End && I->isDeleted())
++I;
}
@@ -116,7 +116,7 @@
bool TargetLowering::shouldDoNopInsertion() const { return DoNopInsertion; }
void TargetLowering::doNopInsertion() {
- Inst *I = *Context.getCur();
+ Inst *I = Context.getCur();
bool ShouldSkip = llvm::isa<InstFakeUse>(I) || llvm::isa<InstFakeDef>(I) ||
llvm::isa<InstFakeKill>(I) || I->isRedundantAssign() ||
I->isDeleted();
@@ -141,7 +141,7 @@
// instructions it consumes.
void TargetLowering::lower() {
assert(!Context.atEnd());
- Inst *Inst = *Context.getCur();
+ Inst *Inst = Context.getCur();
// Mark the current instruction as deleted before lowering,
// otherwise the Dest variable will likely get marked as non-SSA.
// See Variable::setDefinition().
diff --git a/src/IceTargetLowering.h b/src/IceTargetLowering.h
index 4bfe4b4..a8b0fcc 100644
--- a/src/IceTargetLowering.h
+++ b/src/IceTargetLowering.h
@@ -45,13 +45,13 @@
Inst *getNextInst() const {
if (Next == End)
return NULL;
- return *Next;
+ return Next;
}
Inst *getNextInst(InstList::iterator &Iter) const {
advanceForward(Iter);
if (Iter == End)
return NULL;
- return *Iter;
+ return Iter;
}
CfgNode *getNode() const { return Node; }
bool atEnd() const { return Cur == End; }
diff --git a/src/IceTargetLoweringX8632.cpp b/src/IceTargetLoweringX8632.cpp
index c975d88..ad80792 100644
--- a/src/IceTargetLoweringX8632.cpp
+++ b/src/IceTargetLoweringX8632.cpp
@@ -3826,7 +3826,7 @@
}
void TargetX8632::doAddressOptLoad() {
- Inst *Inst = *Context.getCur();
+ Inst *Inst = Context.getCur();
Variable *Dest = Inst->getDest();
Operand *Addr = Inst->getSrc(0);
Variable *Index = NULL;
@@ -4004,7 +4004,7 @@
}
void TargetX8632::doAddressOptStore() {
- InstStore *Inst = llvm::cast<InstStore>(*Context.getCur());
+ InstStore *Inst = llvm::cast<InstStore>(Context.getCur());
Operand *Data = Inst->getData();
Operand *Addr = Inst->getAddr();
Variable *Index = NULL;
@@ -4502,7 +4502,7 @@
if (Ctx->getOptLevel() != Opt_m1) {
// Find two-address non-SSA instructions where Dest==Src0, and set
// the DestNonKillable flag to keep liveness analysis consistent.
- for (Inst *Inst : Context) {
+ for (auto Inst = Context.begin(), E = Context.end(); Inst != E; ++Inst) {
if (Inst->isDeleted())
continue;
if (Variable *Dest = Inst->getDest()) {
@@ -4529,7 +4529,7 @@
// The first pass also keeps track of which instruction is the last
// use for each infinite-weight variable. After the last use, the
// variable is released to the free list.
- for (Inst *Inst : Context) {
+ for (auto Inst = Context.begin(), E = Context.end(); Inst != E; ++Inst) {
if (Inst->isDeleted())
continue;
// Don't consider a FakeKill instruction, because (currently) it
@@ -4560,7 +4560,7 @@
// The second pass colors infinite-weight variables.
llvm::SmallBitVector AvailableRegisters = WhiteList;
llvm::SmallBitVector FreedRegisters(WhiteList.size());
- for (Inst *Inst : Context) {
+ for (auto Inst = Context.begin(), E = Context.end(); Inst != E; ++Inst) {
FreedRegisters.reset();
if (Inst->isDeleted())
continue;
