Subzero: Prune unreachable nodes after constructing the Cfg.
The gcc torture test suite has examples where there is a function call (to a routine that throws an exception or aborts or something), followed by an "unreachable" instruction, followed by more code that may e.g. return a value to the caller. In these examples, the code following the unreachable is itself unreachable.
Problems arise when the unreachable code references a variable defined in the reachable code. This triggers a liveness consistency error because the use of the variable has no reaching definition.
It's a bit surprising that LLVM actually allows this, but it does so we need to deal with it.
The solution is, after initial CFG construction, do a traversal starting from the entry node and then delete any undiscovered nodes.
There is code in Subzero that assumes Cfg::Nodes[i]->Number == i, so the nodes need to be renumbered after pruning. The alternative was to set Nodes[i]=nullptr and not change the node number, but that would mean peppering the code base with CfgNode null checks.
BUG= none
R=jvoung@chromium.org
Review URL: https://codereview.chromium.org/1027933002
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index e6a9cab..e0f48ab 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -108,9 +108,41 @@
getContext()->dumpTimers();
}
-void Cfg::computePredecessors() {
+void Cfg::computeInOutEdges() {
+ // Compute the out-edges.
for (CfgNode *Node : Nodes)
- Node->computePredecessors();
+ Node->computeSuccessors();
+
+ // Prune any unreachable nodes before computing in-edges.
+ SizeT NumNodes = getNumNodes();
+ llvm::BitVector Reachable(NumNodes);
+ llvm::BitVector Pending(NumNodes);
+ Pending.set(getEntryNode()->getIndex());
+ while (true) {
+ int Index = Pending.find_first();
+ if (Index == -1)
+ break;
+ Pending.reset(Index);
+ Reachable.set(Index);
+ CfgNode *Node = Nodes[Index];
+ assert(Node->getIndex() == (SizeT)Index);
+ for (CfgNode *Succ : Node->getOutEdges()) {
+ SizeT SuccIndex = Succ->getIndex();
+ if (!Reachable.test(SuccIndex))
+ Pending.set(SuccIndex);
+ }
+ }
+ SizeT Dest = 0;
+ for (SizeT Source = 0; Source < NumNodes; ++Source) {
+ if (Reachable.test(Source)) {
+ Nodes[Dest] = Nodes[Source];
+ Nodes[Dest]->resetIndex(Dest);
+ // Compute the in-edges.
+ Nodes[Dest]->computePredecessors();
+ ++Dest;
+ }
+ }
+ Nodes.resize(Dest);
}
void Cfg::renumberInstructions() {
diff --git a/src/IceCfg.h b/src/IceCfg.h
index b4c3748..8f74d07 100644
--- a/src/IceCfg.h
+++ b/src/IceCfg.h
@@ -135,9 +135,9 @@
// Passes over the CFG.
void translate();
// After the CFG is fully constructed, iterate over the nodes and
- // compute the predecessor edges, in the form of
- // CfgNode::InEdges[].
- void computePredecessors();
+ // compute the predecessor and successor edges, in the form of
+ // CfgNode::InEdges[] and CfgNode::OutEdges[].
+ void computeInOutEdges();
void renumberInstructions();
void placePhiLoads();
void placePhiStores();
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index 02b9aac..b5e9d86 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -69,11 +69,14 @@
// constructed, the computePredecessors() pass finalizes it by
// creating the InEdges list.
void CfgNode::computePredecessors() {
- OutEdges = Insts.rbegin()->getTerminatorEdges();
for (CfgNode *Succ : OutEdges)
Succ->InEdges.push_back(this);
}
+void CfgNode::computeSuccessors() {
+ OutEdges = Insts.rbegin()->getTerminatorEdges();
+}
+
// This does part 1 of Phi lowering, by creating a new dest variable
// for each Phi instruction, replacing the Phi instruction's dest with
// that variable, and adding an explicit assignment of the old dest to
@@ -605,19 +608,21 @@
// entry.
bool IsEntry = (Func->getEntryNode() == this);
if (!(IsEntry || Live == LiveOrig)) {
- // This is a fatal liveness consistency error. Print some
- // diagnostics and abort.
- Ostream &Str = Func->getContext()->getStrDump();
- Func->resetCurrentNode();
- Str << "LiveOrig-Live =";
- for (SizeT i = Live.size(); i < LiveOrig.size(); ++i) {
- if (LiveOrig.test(i)) {
- Str << " ";
- Liveness->getVariable(i, this)->dump(Func);
+ if (ALLOW_DUMP) {
+ // This is a fatal liveness consistency error. Print some
+ // diagnostics and abort.
+ Ostream &Str = Func->getContext()->getStrDump();
+ Func->resetCurrentNode();
+ Str << "LiveOrig-Live =";
+ for (SizeT i = Live.size(); i < LiveOrig.size(); ++i) {
+ if (LiveOrig.test(i)) {
+ Str << " ";
+ Liveness->getVariable(i, this)->dump(Func);
+ }
}
+ Str << "\n";
}
- Str << "\n";
- llvm_unreachable("Fatal inconsistency in liveness analysis");
+ llvm::report_fatal_error("Fatal inconsistency in liveness analysis");
}
bool Changed = false;
diff --git a/src/IceCfgNode.h b/src/IceCfgNode.h
index 3b5aff3..e4fe2f9 100644
--- a/src/IceCfgNode.h
+++ b/src/IceCfgNode.h
@@ -33,6 +33,7 @@
// Access the label number and name for this node.
SizeT getIndex() const { return Number; }
+ void resetIndex(SizeT NewNumber) { Number = NewNumber; }
IceString getName() const;
void setName(const IceString &NewName) {
// Make sure that the name can only be set once.
@@ -70,6 +71,7 @@
// Add a predecessor edge to the InEdges list for each of this
// node's successors.
void computePredecessors();
+ void computeSuccessors();
CfgNode *splitIncomingEdge(CfgNode *Pred, SizeT InEdgeIndex);
void placePhiLoads();
@@ -92,7 +94,7 @@
private:
CfgNode(Cfg *Func, SizeT LabelIndex);
Cfg *const Func;
- const SizeT Number; // label index
+ SizeT Number; // label index
Cfg::IdentifierIndexType NameIndex; // index into Cfg::NodeNames table
bool HasReturn; // does this block need an epilog?
bool NeedsPlacement;
diff --git a/src/IceConverter.cpp b/src/IceConverter.cpp
index a078a67..6b83b15 100644
--- a/src/IceConverter.cpp
+++ b/src/IceConverter.cpp
@@ -113,7 +113,7 @@
for (const BasicBlock &BBI : *F)
convertBasicBlock(&BBI);
Func->setEntryNode(mapBasicBlockToNode(&F->getEntryBlock()));
- Func->computePredecessors();
+ Func->computeInOutEdges();
Ice::Cfg::setCurrentCfg(nullptr);
Converter.translateFcn(std::move(Func));
diff --git a/src/PNaClTranslator.cpp b/src/PNaClTranslator.cpp
index 799ff94..35cdcf7 100644
--- a/src/PNaClTranslator.cpp
+++ b/src/PNaClTranslator.cpp
@@ -1920,7 +1920,7 @@
}
++Index;
}
- Func->computePredecessors();
+ Func->computeInOutEdges();
}
void FunctionParser::ReportInvalidBinaryOp(Ice::InstArithmetic::OpKind Op,
diff --git a/tests_lit/llvm2ice_tests/prune_unreachable.ll b/tests_lit/llvm2ice_tests/prune_unreachable.ll
new file mode 100644
index 0000000..0c77acd
--- /dev/null
+++ b/tests_lit/llvm2ice_tests/prune_unreachable.ll
@@ -0,0 +1,22 @@
+; This tests that unreachable basic blocks are pruned from the CFG, so that
+; liveness analysis doesn't detect inconsistencies.
+
+; RUN: %p2i -i %s --filetype=obj --disassemble --args -Om1 | FileCheck %s
+; RUN: %p2i -i %s --filetype=obj --disassemble --args -O2 | FileCheck %s
+
+declare void @abort()
+
+define i32 @unreachable_block() {
+entry:
+ ; ret_val has no reaching uses and so its assignment may be
+ ; dead-code eliminated.
+ %ret_val = add i32 undef, undef
+ call void @abort()
+ unreachable
+label:
+ ; ret_val has no reaching definitions, causing an inconsistency in
+ ; liveness analysis.
+ ret i32 %ret_val
+}
+
+; CHECK-LABEL: unreachable_block
