Remove jumps over empty blocks.
After contracting a node reorder it as unreachable even if it
hasn't yet been placed.
BUG=
R=jvoung@chromium.org, jvoung, stichnot
Review URL: https://codereview.chromium.org/1246173003.
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index f7b1a8c..7e91508 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -259,6 +259,8 @@
// placed, while maintaining the same relative ordering among already
// placed nodes.
void Cfg::reorderNodes() {
+ // TODO(ascull): it would be nice if the switch tests were always followed
+ // by the default case to allow for fall through.
typedef std::list<CfgNode *> PlacedList;
PlacedList Placed; // Nodes with relative placement locked down
PlacedList Unreachable; // Unreachable nodes
@@ -271,6 +273,14 @@
// --PlaceIndex and assert() statements before moving to the next
// node.
do {
+ if (Node != getEntryNode() && Node->getInEdges().empty()) {
+ // The node has essentially been deleted since it is not a
+ // successor of any other node.
+ Unreachable.push_back(Node);
+ PlaceIndex[Node->getIndex()] = Unreachable.end();
+ Node->setNeedsPlacement(false);
+ continue;
+ }
if (!Node->needsPlacement()) {
// Add to the end of the Placed list.
Placed.push_back(Node);
@@ -278,13 +288,6 @@
continue;
}
Node->setNeedsPlacement(false);
- if (Node != getEntryNode() && Node->getInEdges().empty()) {
- // The node has essentially been deleted since it is not a
- // successor of any other node.
- Unreachable.push_back(Node);
- PlaceIndex[Node->getIndex()] = Unreachable.end();
- continue;
- }
// Assume for now that the unplaced node is from edge-splitting
// and therefore has 1 in-edge and 1 out-edge (actually, possibly
// more than 1 in-edge if the predecessor node was contracted).
@@ -521,8 +524,7 @@
void Cfg::doBranchOpt() {
TimerMarker T(TimerStack::TT_doBranchOpt, this);
for (auto I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
- auto NextNode = I;
- ++NextNode;
+ auto NextNode = I + 1;
(*I)->doBranchOpt(NextNode == E ? nullptr : *NextNode);
}
}
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index 60214c7..a901753 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -730,41 +730,46 @@
}
Branch->setDeleted();
assert(OutEdges.size() == 1);
+ CfgNode *Successor = OutEdges.front();
// Repoint all this node's in-edges to this node's successor, unless
// this node's successor is actually itself (in which case the
// statement "OutEdges.front()->InEdges.push_back(Pred)" could
// invalidate the iterator over this->InEdges).
- if (OutEdges.front() != this) {
+ if (Successor != this) {
for (CfgNode *Pred : InEdges) {
- for (auto I = Pred->OutEdges.begin(), E = Pred->OutEdges.end(); I != E;
- ++I) {
- if (*I == this) {
- *I = OutEdges.front();
- OutEdges.front()->InEdges.push_back(Pred);
+ for (CfgNode *&I : Pred->OutEdges) {
+ if (I == this) {
+ I = Successor;
+ Successor->InEdges.push_back(Pred);
}
}
for (Inst &I : Pred->getInsts()) {
if (!I.isDeleted())
- I.repointEdges(this, OutEdges.front());
+ I.repointEdges(this, Successor);
}
}
+
+ // Remove the in-edge to the successor to allow node reordering to make
+ // better decisions. For example it's more helpful to place a node after
+ // a reachable predecessor than an unreachable one (like the one we just
+ // contracted).
+ Successor->InEdges.erase(
+ std::find(Successor->InEdges.begin(), Successor->InEdges.end(), this));
}
InEdges.clear();
- // Don't bother removing the single out-edge, which would also
- // require finding the corresponding in-edge in the successor and
- // removing it.
}
void CfgNode::doBranchOpt(const CfgNode *NextNode) {
TargetLowering *Target = Func->getTarget();
- // Check every instruction for a branch optimization opportunity.
- // It may be more efficient to iterate in reverse and stop after the
- // 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) {
+ // Find the first opportunity for branch optimization (which will be the last
+ // instruction in the block) and stop. This is sufficient unless there is some
+ // target lowering where we have the possibility of multiple optimizations per
+ // block. Take care with switch lowering as there are multiple unconditional
+ // branches and only the last can be deleted.
+ for (Inst &I : reverse_range(Insts)) {
if (!I.isDeleted()) {
Target->doBranchOpt(&I, NextNode);
+ return;
}
}
}
diff --git a/tests_lit/llvm2ice_tests/adv-switch-opt.ll b/tests_lit/llvm2ice_tests/adv-switch-opt.ll
index 7aa832a..1d10931 100644
--- a/tests_lit/llvm2ice_tests/adv-switch-opt.ll
+++ b/tests_lit/llvm2ice_tests/adv-switch-opt.ll
@@ -143,7 +143,6 @@
; CHECK-NEXT: je
; CHECK-NEXT: cmp {{.*}},0xea
; CHECK-NEXT: je
-; CHECK-NEXT: jmp
; Test for correct 64-bit lowering.
; TODO(ascull): this should generate better code like the 32-bit version
diff --git a/tests_lit/llvm2ice_tests/branch-opt.ll b/tests_lit/llvm2ice_tests/branch-opt.ll
index 94bcd0f..24b6adb 100644
--- a/tests_lit/llvm2ice_tests/branch-opt.ll
+++ b/tests_lit/llvm2ice_tests/branch-opt.ll
@@ -169,3 +169,37 @@
; ARM32OM1: bx lr
; ARM32OM1: bl
; ARM32OM1: bx lr
+
+; Unconditional branches to the block after a contracted block should be
+; removed.
+define void @testUncondToBlockAfterContract() {
+entry:
+ call void @dummy()
+ br label %target
+contract:
+ br label %target
+target:
+ call void @dummy()
+ ret void
+}
+
+; O2-LABEL: testUncondToBlockAfterContract
+; O2: call
+; There will be nops for bundle align to end (for NaCl), but there should
+; not be a branch.
+; O2-NOT: j
+; O2: call
+
+; OM1-LABEL: testUncondToBlockAfterContract
+; OM1: call
+; OM1-NEXT: jmp
+; OM1: call
+
+; ARM32O2-LABEL: testUncondToBlockAfterContract
+; ARM32O2: bl {{.*}} dummy
+; ARM32O2-NEXT: bl {{.*}} dummy
+
+; ARM32OM1-LABEL: testUncondToBlockAfterContract
+; ARM32OM1: bl {{.*}} dummy
+; ARM32OM1-NEXT: b
+; ARM32OM1-NEXT: bl {{.*}} dummy
