[Reassociate] Skip analysis of dead code to avoid infinite loop.
Summary:
It was detected that the reassociate pass could enter an inifite
loop when analysing dead code. Simply skipping to analyse basic
blocks that are dead avoids such problems (and as a side effect
we avoid spending time on optimising dead code).
The solution is using the same Reverse Post Order ordering of the
basic blocks when doing the optimisations, as when building the
precalculated rank map. A nice side-effect of this solution is
that we now know that we only try to do optimisations for blocks
with ranked instructions.
Fixes https://llvm.org/bugs/show_bug.cgi?id=30818
Reviewers: llvm-commits, davide, eli.friedman, mehdi_amini
Subscribers: dberlin
Differential Revision: https://reviews.llvm.org/D26154
llvm-svn: 285793
diff --git a/llvm/lib/Transforms/Scalar/Reassociate.cpp b/llvm/lib/Transforms/Scalar/Reassociate.cpp
index ac0d7b8..e8abb5b 100644
--- a/llvm/lib/Transforms/Scalar/Reassociate.cpp
+++ b/llvm/lib/Transforms/Scalar/Reassociate.cpp
@@ -145,7 +145,8 @@
return nullptr;
}
-void ReassociatePass::BuildRankMap(Function &F) {
+void ReassociatePass::BuildRankMap(Function &F,
+ ReversePostOrderTraversal<Function*> &RPOT) {
unsigned i = 2;
// Assign distinct ranks to function arguments.
@@ -154,7 +155,7 @@
DEBUG(dbgs() << "Calculated Rank[" << I->getName() << "] = " << i << "\n");
}
- ReversePostOrderTraversal<Function *> RPOT(&F);
+ // Traverse basic blocks in ReversePostOrder
for (BasicBlock *BB : RPOT) {
unsigned BBRank = RankMap[BB] = ++i << 16;
@@ -2174,11 +2175,19 @@
}
PreservedAnalyses ReassociatePass::run(Function &F, FunctionAnalysisManager &) {
+ // Get the functions basic blocks in Reverse Post Order. This order is used by
+ // BuildRankMap to pre calculate ranks correctly. It also excludes dead basic
+ // blocks (it has been seen that the analysis in this pass could hang when
+ // analysing dead basic blocks).
+ ReversePostOrderTraversal<Function *> RPOT(&F);
+
// Calculate the rank map for F.
- BuildRankMap(F);
+ BuildRankMap(F, RPOT);
MadeChange = false;
- for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
+ // Traverse the same blocks that was analysed by BuildRankMap.
+ for (BasicBlock *BI : RPOT) {
+ assert(RankMap.count(&*BI) && "BB should be ranked.");
// Optimize every instruction in the basic block.
for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;)
if (isInstructionTriviallyDead(&*II)) {