[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

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

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

lib/Transforms/InstCombine/InstructionCombining.cpp

if (Instruction *Result = visit(*I)) {
       MadeIRChange = true;
     }
   }
 
   Worklist.zap();
   return MadeIRChange;
 }
 
-/// Walk the function in depth-first order, adding all reachable code to the
+/// Walk the function in reverse post-order, 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 AddReachableCodeToWorklist(BasicBlock *BB, const DataLayout &DL,
-                                       SmallPtrSetImpl<BasicBlock *> &Visited,
-                                       InstCombineWorklist &ICWorklist,
-                                       const TargetLibraryInfo *TLI) {
+static bool AddReachableCodeToWorklist(
+    BasicBlock *BB, const DataLayout &DL,
+    SmallPtrSetImpl<BasicBlock *> &LiveBlocks, InstCombineWorklist &ICWorklist,
   bool MadeIRChange = false;
-  SmallVector<BasicBlock*, 256> Worklist;
-  Worklist.push_back(BB);
 
   SmallVector<Instruction*, 128> InstrsForInstCombineWorklist;
   DenseMap<Constant *, Constant *> FoldedConstants;
 
-  do {
-    BB = Worklist.pop_back_val();
+  ReversePostOrderTraversal<BasicBlock *> RPOT(BB);
+  LiveBlocks.insert(BB);
 
-    // 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 (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
       Instruction *Inst = &*BBI++;
 
       // ConstantProp instruction if trivially constant.
       if (!Inst->use_empty() &&
           (Inst->getNumOperands() == 0 || isa<Constant>(Inst->getOperand(0))))
for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
       }
 
       // Skip processing debug intrinsics in InstCombine. Processing these call instructions
       // consumes non-trivial amount of time and provides no value for the optimization.
       if (!isa<DbgInfoIntrinsic>(Inst))
         InstrsForInstCombineWorklist.push_back(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)) {
       if (BI->isConditional() && isa<ConstantInt>(BI->getCondition())) {
         bool CondVal = cast<ConstantInt>(BI->getCondition())->getZExtValue();
         BasicBlock *ReachableBB = BI->getSuccessor(!CondVal);
-        Worklist.push_back(ReachableBB);
+        LiveBlocks.insert(ReachableBB);
         continue;
       }
     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
       if (ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition())) {
-        Worklist.push_back(SI->findCaseValue(Cond)->getCaseSuccessor());
+        LiveBlocks.insert(SI->findCaseValue(Cond)->getCaseSuccessor());
         continue;
       }
     }
 
     for (BasicBlock *SuccBB : successors(TI))
-      Worklist.push_back(SuccBB);
-  } while (!Worklist.empty());
+      LiveBlocks.insert(SuccBB);
+  }
 
   // Once we've found all of the instructions to add to instcombine's worklist,
   // add them in reverse order.  This way instcombine will visit from the top
   // of the function down.  This jives well with the way that it adds all uses
   // of instructions to the worklist after doing a transformation, thus avoiding
   // some N^2 behavior in pathological cases.
   ICWorklist.reserve(InstrsForInstCombineWorklist.size());
   for (Instruction *Inst : reverse(InstrsForInstCombineWorklist)) {

 static bool prepareICWorklistFromFunction(Function &F, const DataLayout &DL,
                                           TargetLibraryInfo *TLI,
                                           InstCombineWorklist &ICWorklist) {
   bool MadeIRChange = false;
 
   // Do a depth-first traversal of the function, populate the worklist with
   // the reachable instructions.  Ignore blocks that are not reachable.  Keep
   // track of which blocks we visit.
-  SmallPtrSet<BasicBlock *, 32> Visited;
+  SmallPtrSet<BasicBlock *, 32> LiveBlocks;
   MadeIRChange |=
-      AddReachableCodeToWorklist(&F.front(), DL, Visited, ICWorklist, TLI);
+      AddReachableCodeToWorklist(&F.front(), DL, LiveBlocks, ICWorklist, TLI);
 
   // Do a quick scan over the function.  If we find any blocks that are
   // unreachable, remove any instructions inside of them.  This prevents
   // the instcombine code from having to deal with some bad special cases.
   for (BasicBlock &BB : F) {
-    if (Visited.count(&BB))
+    if (LiveBlocks.count(&BB))
       continue;
 
     unsigned NumDeadInstInBB = removeAllNonTerminatorAndEHPadInstructions(&BB);
     MadeIRChange |= NumDeadInstInBB > 0;
     NumDeadInst += NumDeadInstInBB;
   }
 
   return MadeIRChange;

test/Transforms/InstCombine/icmp-div-constant.ll

 define i32 @icmp_div2(i16 %a, i16 %c) {
 ; CHECK-LABEL: @icmp_div2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i16 [[A:%.*]], 0
 ; CHECK-NEXT:    br i1 [[TOBOOL]], label [[THEN:%.*]], label [[EXIT:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ -1, [[ENTRY:%.*]] ], [ 0, [[THEN]] ]
-; CHECK-NEXT:    ret i32 [[PHI]]
+; CHECK-NEXT:    ret i32 -1
 ;
 entry:
   %tobool = icmp eq i16 %a, 0
   br i1 %tobool, label %then, label %exit
 
 then:
   %div = sdiv i16 %c, 0
   %cmp = icmp ne i16 %div, 0

test/Transforms/InstCombine/pr44245.ll

 ; CHECK-LABEL: @test_2(
 ; CHECK-NEXT:  entry:
 ; 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:    store %type_2* undef, %type_2** null, align 536870912
 ; CHECK-NEXT:    br label [[COND_END144:%.*]]
 ; CHECK:       cond.false138:
 ; CHECK-NEXT:    store %type_2* undef, %type_2** null, align 536870912
 ; CHECK-NEXT:    br label [[COND_END144]]
 ; CHECK:       cond.end144:
 ; CHECK-NEXT:    br label [[WHILE_COND]]
 ;
 entry:

test/Transforms/InstCombine/store.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -instcombine -S | FileCheck %s
+; RUN: opt < %s -instcombine -instcombine-infinite-loop-threshold=2 -S | FileCheck %s
 
 define void @test1(i32* %P) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    store i32 123, i32* undef, align 4
 ; CHECK-NEXT:    store i32 undef, i32* null, align 536870912
 ; CHECK-NEXT:    ret void
 ;
   store i32 undef, i32* %P