[InstCombine] Process blocks in RPO

[nikic]

Summary

InstComine currently processes blocks in some ill-defined depth-first order. This can break the usual invariant that the operands of an instruction should be simplified before the instruction itself, if uses across basic blocks (particularly inside phi nodes) are involved.

This patch switches the initial worklist population to use RPO instead, which will ensure that predecessors are visited before successors (back-edges notwithstanding).

This allows us to fold more cases within a single InstCombine iteration. The broader context here is that I want to limit InstCombine to a single iteration in the future (removing the current fix-point iteration), which will give a large (5% end-to-end) compile-time improvement without substantial optimization impact. However, this requires eliminating as many cases where we fail to reach the fix point in one iteration as possible, and the current worklist population order is one of the main issues.

In the meantime, this does cause a small compile-time regression of about 0.1% (http://llvm-compile-time-tracker.com/compare.php?from=725fcf40c3e55b2c03a1ed2326375984c0a8560f&to=8d0280338cd9409ec6fa4dbf86f4c2a9dfa57c60&stat=instructions:u), because calculating RPO is more expensive than one would think.

[xbolva00]

Thanks, useful!

Did you observe any (positive) compile time changes?

test/Transforms/InstCombine/store.ll

2 ↗

(On Diff #247284)

since -infinite-loop-threshold now serves as a max treshold value, should we rename it?

-instcombine-iterations-threshold?

[nikic]

In D75362#1898366, @xbolva00 wrote:

Did you observe any (positive) compile time changes?

I don't expect visible improvement from (just) this change, because it affects few cases (less than 1% of our InstCombine tests). My hope is that we can remove fixpoint iteration from InstCombine entirely in the future, once all the known issues are resolved. I'm still not sure if that's realistic, but I'm getting pretty close now...

test/Transforms/InstCombine/store.ll

2 ↗

(On Diff #247284)

Yes, the "infinite loop" terminology doesn't make a lot of sense for this usage. We also have a -instcombine-max-iterations setting, so it's a bit tricky to distinguish these two limits (one just stops, the other reports a fatal error).

[nikic]

Reduce cost by computing RPOT only once.

[nikic]

In D75362#1898366, @xbolva00 wrote:

Did you observe any (positive) compile time changes?

It turned out that computing the RPO order is more expensive than I expected... After optimizing a bit, this change still clocks in as a 0.15% regression.

[lebedev.ri]

This looks good to me.
@spatel?

[spatel]

In D75362#1961474, @lebedev.ri wrote:

This looks good to me.
@spatel?

I don't have a sense of the value/cost trade-off other than what is noted in this review, so I don't have anything useful to say here.
Let's add some other reviewers and see if anyone else has experience/ideas.

[efriedma]

A depth-first search is enough to ensure some predecessor of every block is visited before that block. So the benefit of RPO is to change that to all (non-loop) predecessors, which I guess helps optimizations involving PHI nodes?

I'm surprised this shows up in the compile-time statistics that way. Given the cost of everything else instcombine does, an RPO traversal shouldn't rank very high. Maybe worth adding timers to check whether the time is actually in this function, or we end up doing more work due to the order of instructions in the worklist. (Maybe we should be using SmallVector in ReversePostOrderTraversal?)

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

[nikic]

Rebase. Compile-time impact is still about the same: http://llvm-compile-time-tracker.com/compare.php?from=d734edfe7c13d1b8e32d75a5df897ef0d9b69302&to=9419472abcffeed5401e27c340dfc249dbef5d18&stat=instructions:u

[nikic]

This still seems like the right thing to do, but not pursing it right now.

[nikic]

Rebase and put up for review again.

[nikic]

Rebase

[nikic]

Rebase due to test changes

[aeubanks]

lgtm, assuming it's still necessary for D154579

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

 //   ... etc.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
 #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"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/CFG.h"
if (auto *MD = dyn_cast<MDNode>(MDOperand))
       return !UsedAliasScopesAndLists.contains(MD) ||
              !UsedNoAliasScopesAndLists.contains(MD);
 
     // Not an MDNode ? throw away.
     return true;
   }
 };
 
-/// 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,
+                              InstructionWorklist &ICWorklist,
+                              ReversePostOrderTraversal<BasicBlock *> &RPOT) {
   bool MadeIRChange = false;
-  SmallPtrSet<BasicBlock *, 32> Visited;
-  SmallVector<BasicBlock*, 256> Worklist;
-  Worklist.push_back(&F.front());
+  SmallPtrSet<BasicBlock *, 32> LiveBlocks;
+  LiveBlocks.insert(&F.front());
 
   SmallVector<Instruction *, 128> InstrsForInstructionWorklist;
   DenseMap<Constant *, Constant *> 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)) {
       // ConstantProp instruction if trivially constant.
       if (!Inst.use_empty() &&
           (Inst.getNumOperands() == 0 || isa<Constant>(Inst.getOperand(0))))
         if (Constant *C = ConstantFoldInstruction(&Inst, DL, TLI)) {
           LLVM_DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << Inst
for (Instruction &Inst : llvm::make_early_inc_range(*BB)) {
       // these call instructions consumes non-trivial amount of time and
       // provides no value for the optimization.
       if (!Inst.isDebugOrPseudoInst()) {
         InstrsForInstructionWorklist.push_back(&Inst);
         SeenAliasScopes.analyse(&Inst);
       }
     }
 
-    // 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<BranchInst>(TI); BI && BI->isConditional()) {
       if (isa<UndefValue>(BI->getCondition()))
         // Branch on undef is UB.
         continue;
       if (auto *Cond = dyn_cast<ConstantInt>(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<SwitchInst>(TI)) {
       if (isa<UndefValue>(SI->getCondition()))
         // Switch on undef is UB.
         continue;
       if (auto *Cond = dyn_cast<ConstantInt>(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;
     unsigned NumDeadDbgInstInBB;
     std::tie(NumDeadInstInBB, NumDeadDbgInstInBB) =
         removeAllNonTerminatorAndEHPadInstructions(&BB);
 
     MadeIRChange |= NumDeadInstInBB + NumDeadDbgInstInBB > 0;
static bool combineInstructionsOverFunction(
   IRBuilder<TargetFolder, IRBuilderCallbackInserter> Builder(
       F.getContext(), TargetFolder(DL),
       IRBuilderCallbackInserter([&Worklist, &AC](Instruction *I) {
         Worklist.add(I);
         if (auto *Assume = dyn_cast<AssumeInst>(I))
           AC.registerAssumption(Assume);
       }));
 
+  ReversePostOrderTraversal<BasicBlock *> RPOT(&F.front());
+
   // Lower dbg.declare intrinsics otherwise their value may be clobbered
   // by instcombiner.
   bool MadeIRChange = false;
   if (ShouldLowerDbgDeclare)
     MadeIRChange = LowerDbgDeclare(F);
 
   // Iterate while there is work to do.
   unsigned Iteration = 0;
if (Iteration > MaxIterations) {
                         << " on " << F.getName()
                         << " reached; stopping before reaching a fixpoint\n");
       break;
     }
 
     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);
     IC.MaxArraySizeForCombine = MaxArraySize;
 
     if (!IC.run())
       break;
 

llvm/test/Transforms/InstCombine/oss_fuzz_32759.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 target datalayout = "n32"
 
 define i1 @oss_fuzz_32759(i1 %y, i1 %c1) {
 ; CHECK-LABEL: @oss_fuzz_32759(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[COND_TRUE:%.*]], label [[END:%.*]]
 ; 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
 
 cond.true:                                        ; preds = %entry
   %zy = zext i1 %y to i32
   %B6 = shl i32 %zy, 2147483647
   %B3 = ashr i32 %B6, 2147483647

llvm/test/Transforms/InstCombine/pr44245.ll

 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 ; CHECK:       while.cond:
 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
 ; CHECK:       for.cond:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[COND_TRUE133:%.*]], label [[COND_FALSE138:%.*]]
 ; 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:
   br label %while.cond
 
 while.cond:                                       ; preds = %cond.end144, %entry
   %link.0 = phi ptr [ undef, %entry ], [ %cond145, %cond.end144 ]
   br label %for.cond

llvm/test/Transforms/InstCombine/select.ll

 ; PR14131
 define void @test64(i32 %p, i16 %b, i1 %c1) noreturn {
 ; CHECK-LABEL: @test64(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[LOR_RHS:%.*]], label [[LOR_END:%.*]]
 ; 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:
 ; CHECK-NEXT:    br label [[WHILE_BODY:%.*]]
 ; CHECK:       while.body:
 ; CHECK-NEXT:    br label [[WHILE_BODY]]
 ;
 entry:

llvm/test/Transforms/InstCombine/store.ll

 ; 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.
 define void @store_of_undef(ptr %P) {
 ; CHECK-LABEL: @store_of_undef(
 ; CHECK-NEXT:    ret void
 ;
   store i32 undef, ptr %P