diff --git a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp --- a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -36,6 +36,7 @@ #include "llvm/ADT/APInt.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" @@ -4108,31 +4109,29 @@ } }; -/// Populate the IC worklist from a function, by walking it in depth-first -/// order and adding all reachable code to the worklist. +/// Populate the IC worklist from a function, by walking it in reverse +/// post-order and adding all reachable code to the worklist. /// /// This has a couple of tricks to make the code faster and more powerful. In /// particular, we constant fold and DCE instructions as we go, to avoid adding /// them to the worklist (this significantly speeds up instcombine on code where /// many instructions are dead or constant). Additionally, if we find a branch /// whose condition is a known constant, we only visit the reachable successors. -static bool prepareICWorklistFromFunction(Function &F, const DataLayout &DL, - const TargetLibraryInfo *TLI, - InstructionWorklist &ICWorklist) { +static bool +prepareICWorklistFromFunction(Function &F, const DataLayout &DL, + const TargetLibraryInfo *TLI, + InstructionWorklist &ICWorklist, + ReversePostOrderTraversal &RPOT) { bool MadeIRChange = false; - SmallPtrSet Visited; - SmallVector Worklist; - Worklist.push_back(&F.front()); + SmallPtrSet LiveBlocks; + LiveBlocks.insert(&F.front()); SmallVector InstrsForInstructionWorklist; DenseMap FoldedConstants; AliasScopeTracker SeenAliasScopes; - do { - BasicBlock *BB = Worklist.pop_back_val(); - - // We have now visited this block! If we've already been here, ignore it. - if (!Visited.insert(BB).second) + for (BasicBlock *BB : RPOT) { + if (!LiveBlocks.count(BB)) continue; for (Instruction &Inst : llvm::make_early_inc_range(*BB)) { @@ -4178,8 +4177,8 @@ } } - // Recursively visit successors. If this is a branch or switch on a - // constant, only visit the reachable successor. + // If this is a branch or switch on a constant, mark only the single + // live successor. Otherwise assume all successors are live. Instruction *TI = BB->getTerminator(); if (BranchInst *BI = dyn_cast(TI); BI && BI->isConditional()) { if (isa(BI->getCondition())) @@ -4188,7 +4187,7 @@ if (auto *Cond = dyn_cast(BI->getCondition())) { bool CondVal = Cond->getZExtValue(); BasicBlock *ReachableBB = BI->getSuccessor(!CondVal); - Worklist.push_back(ReachableBB); + LiveBlocks.insert(ReachableBB); continue; } } else if (SwitchInst *SI = dyn_cast(TI)) { @@ -4196,19 +4195,20 @@ // Switch on undef is UB. continue; if (auto *Cond = dyn_cast(SI->getCondition())) { - Worklist.push_back(SI->findCaseValue(Cond)->getCaseSuccessor()); + LiveBlocks.insert(SI->findCaseValue(Cond)->getCaseSuccessor()); continue; } } - append_range(Worklist, successors(TI)); - } while (!Worklist.empty()); + for (BasicBlock *SuccBB : successors(TI)) + LiveBlocks.insert(SuccBB); + } // Remove instructions inside unreachable blocks. This prevents the // instcombine code from having to deal with some bad special cases, and // reduces use counts of instructions. for (BasicBlock &BB : F) { - if (Visited.count(&BB)) + if (LiveBlocks.count(&BB)) continue; unsigned NumDeadInstInBB; @@ -4262,6 +4262,8 @@ AC.registerAssumption(Assume); })); + ReversePostOrderTraversal RPOT(&F.front()); + // Lower dbg.declare intrinsics otherwise their value may be clobbered // by instcombiner. bool MadeIRChange = false; @@ -4290,7 +4292,7 @@ LLVM_DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on " << F.getName() << "\n"); - MadeIRChange |= prepareICWorklistFromFunction(F, DL, &TLI, Worklist); + MadeIRChange |= prepareICWorklistFromFunction(F, DL, &TLI, Worklist, RPOT); InstCombinerImpl IC(Worklist, Builder, F.hasMinSize(), AA, AC, TLI, TTI, DT, ORE, BFI, PSI, DL, LI); diff --git a/llvm/test/Transforms/InstCombine/oss_fuzz_32759.ll b/llvm/test/Transforms/InstCombine/oss_fuzz_32759.ll --- a/llvm/test/Transforms/InstCombine/oss_fuzz_32759.ll +++ b/llvm/test/Transforms/InstCombine/oss_fuzz_32759.ll @@ -9,7 +9,7 @@ ; CHECK: cond.true: ; CHECK-NEXT: br label [[END]] ; CHECK: end: -; CHECK-NEXT: ret i1 [[C1]] +; CHECK-NEXT: ret i1 false ; entry: br i1 %c1, label %cond.true, label %end diff --git a/llvm/test/Transforms/InstCombine/pr44245.ll b/llvm/test/Transforms/InstCombine/pr44245.ll --- a/llvm/test/Transforms/InstCombine/pr44245.ll +++ b/llvm/test/Transforms/InstCombine/pr44245.ll @@ -157,9 +157,9 @@ ; CHECK: cond.true133: ; CHECK-NEXT: br label [[COND_END144:%.*]] ; CHECK: cond.false138: -; CHECK-NEXT: store i1 true, ptr poison, align 1 ; CHECK-NEXT: br label [[COND_END144]] ; CHECK: cond.end144: +; CHECK-NEXT: store i1 true, ptr poison, align 1 ; CHECK-NEXT: br label [[WHILE_COND]] ; entry: diff --git a/llvm/test/Transforms/InstCombine/select.ll b/llvm/test/Transforms/InstCombine/select.ll --- a/llvm/test/Transforms/InstCombine/select.ll +++ b/llvm/test/Transforms/InstCombine/select.ll @@ -960,7 +960,7 @@ ; CHECK: lor.rhs: ; CHECK-NEXT: br label [[LOR_END]] ; CHECK: lor.end: -; CHECK-NEXT: br i1 true, label [[COND_END17:%.*]], label [[COND_FALSE16:%.*]] +; CHECK-NEXT: br i1 poison, label [[COND_END17:%.*]], label [[COND_FALSE16:%.*]] ; CHECK: cond.false16: ; CHECK-NEXT: br label [[COND_END17]] ; CHECK: cond.end17: diff --git a/llvm/test/Transforms/InstCombine/store.ll b/llvm/test/Transforms/InstCombine/store.ll --- a/llvm/test/Transforms/InstCombine/store.ll +++ b/llvm/test/Transforms/InstCombine/store.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt < %s -passes=instcombine -S | FileCheck %s +; RUN: opt < %s -passes=instcombine -instcombine-infinite-loop-threshold=2 -S | FileCheck %s ; FIXME: This is technically incorrect because it might overwrite a poison ; value. Stop folding it once #52930 is resolved.