[InstSimplify] remove quadratic time looping (PR42771)

[spatel]

Summary

The test case from:
https://bugs.llvm.org/show_bug.cgi?id=42771
...shows a ~30x slowdown caused by the awkward loop iteration (rL207302) that is seemingly done just to avoid invalidating the instruction iterator. We can instead delay instruction deletion until we reach the end of the block (or we could delay until we reach the end of all blocks).

There's a test diff here for a degenerate case with llvm.assume that I didn't step through, but I think that's caused because isInstructionTriviallyDead() may not be true for a function call even if that call has no uses.

This change probably doesn't result in much overall compile-time improvement because we call -instsimplify as a standalone pass only once in the standard -O2 opt pipeline from what I see.

[foad]

There's a test diff here for a degenerate case with llvm.assume that I didn't step through, but I think that's caused because isInstructionTriviallyDead() may not be true for a function call even if that call has no uses.

The old code would visit %cond1, notice the @llvm.assume, record an assumption that %x==3, and then (because of the "When instructions get deleted re-iterate instead" case) *revisit* the %add and find that it can now be simplified using the assumption. I don't know how important it is to preserve this kind of behaviour.

[spatel]

In D65336#1602727, @foad wrote:

There's a test diff here for a degenerate case with llvm.assume that I didn't step through, but I think that's caused because isInstructionTriviallyDead() may not be true for a function call even if that call has no uses.

The old code would visit %cond1, notice the @llvm.assume, record an assumption that %x==3, and then (because of the "When instructions get deleted re-iterate instead" case) *revisit* the %add and find that it can now be simplified using the assumption. I don't know how important it is to preserve this kind of behaviour.

It's not important IMO. That test has conflicting assumptions, so we're really just making sure we don't crash. If we're still propagating info from legitimate assumptions, we should be fine.

[foad]

llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp

44–61

Why did you change the logic here? Now we might try to simplify an instruction that has no uses but is not trivially dead, which at least makes the comment on L45 slightly wrong.

[spatel]

llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp

44–61

See comment at line 55 - just because an instruction (a call at least) has no uses does not mean it can not be simplified. I think we should use isInstructionTriviallyDead() as our point of truth here rather than mixing that with a use check.

I'll update the comment at line 45 if you agree.

[foad]

llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp

44–61

just because an instruction (a call at least) has no uses does not mean it can not be simplified

As I understand it, there is no point simplifying an instruction that has no uses. "Simplifying" does not change the instruction at all, it just returns a pointer to another (simpler) Value that users of the original instruction could use instead. If there are no users, there is no point doing this.

[spatel]

llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp

44–61

Ok, that sounds good. So let's only try to simplify if an instruction is not trivially dead *and* it has uses. We can only delete the trivially dead, so we only add those to the dead instructions list.

[spatel]

Patch updated:
Don't bother trying to simplify an instruction if it has no uses (restores the previous logic).

[foad]

Looks OK to me now, thanks.

As a follow-up I might try rewriting the whole thing as a worklist algorithm. At the moment it'll do another pass through the whole function even if there is only one instruction left on the ToSimplify list, which seems pretty wasteful. Although as you say, it might not make any difference to overall compile time.

[bjope]

llvm/trunk/lib/Transforms/Scalar/InstSimplifyPass.cpp

47 ↗

(On Diff #212054)

I think we need to set Changed = true here as well.

I've got a test case like this:

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -instsimplify -S -o /dev/null -debug-pass=Details 2>&1 | FileCheck --check-prefix DETAILS %s
; RUN: opt < %s -instsimplify -S -o - | FileCheck %s

; Verify that InstSimplifyLegacyPass notifies the pass manager about changes
; being made (when a call is removed CGSCC must be updated).
;
; DETAILS: Made Modification 'Remove redundant instructions' on Function 'main'

define internal void @func_1(i64* nocapture readnone %0) #0 {
; CHECK-LABEL: @func_1(
; CHECK-NEXT:    unreachable
;
  unreachable
}

define i16 @main(i16 %0, i16** nocapture readnone %1) #1 {
; CHECK-LABEL: @main(
; CHECK-NEXT:  bb1:
; CHECK-NEXT:    unreachable
;
bb1:
  call void @func_1(i64* undef)
  unreachable
}

attributes #0 = { noinline norecurse nounwind readnone }
attributes #1 = { norecurse nounwind readnone }

that show that we do not propagate to pass managers that we have removed a call otherwise.

My original reproducer ended up with

opt: ../include/llvm/Analysis/CallGraph.h:180: llvm::CallGraphNode::~CallGraphNode(): Assertion `NumReferences == 0 && "Node deleted while references remain"' failed.

due to not cleaning up the call graph after removing the call.

I'll upload a patch for this (assuming it is the correct solution).

Although, I've also noticed that the same assert was seen in https://bugs.llvm.org/show_bug.cgi?id=42751, and https://bugs.llvm.org/show_bug.cgi?id=42787 is also related to calls being optimized away (afaict). InstSimpllify is not involved in those two PRs. So it might be something else that makes isInstructionTriviallyDead returning that certain calls can be removed nowadays (such as recent changes regarding functions attributes). It should be valid for a FunctionPass to delete a call right, or is it interprocedural to for example look at function attributes to determine that the callee has no side effects? It is illegal for a FunctionPass to inspect a function other than the one being optimized. Is looking at function attributes the same as "inspecting" the callee?

[bjope]

llvm/trunk/lib/Transforms/Scalar/InstSimplifyPass.cpp

47 ↗

(On Diff #212054)

Suggested fixup is up for review here: https://reviews.llvm.org/D65973

llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp

 STATISTIC(NumSimplified, "Number of redundant instructions removed");
 
 static bool runImpl(Function &F, const SimplifyQuery &SQ,
                     OptimizationRemarkEmitter *ORE) {
   SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
   bool Changed = false;
 
   do {
-    for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
-      // Here be subtlety: the iterator must be incremented before the loop
-      // body (not sure why), so a range-for loop won't work here.
-      for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
-        Instruction *I = &*BI++;
-        // The first time through the loop ToSimplify is empty and we try to
-        // simplify all instructions.  On later iterations ToSimplify is not
+    for (BasicBlock &BB : F) {
+      SmallVector<Instruction *, 8> DeadInstsInBB;
+      for (Instruction &I : BB) {
+        // The first time through the loop, ToSimplify is empty and we try to
+        // simplify all instructions. On later iterations, ToSimplify is not
         // empty and we only bother simplifying instructions that are in it.
-        if (!ToSimplify->empty() && !ToSimplify->count(I))
+        if (!ToSimplify->empty() && !ToSimplify->count(&I))
           continue;
 
-        // Don't waste time simplifying unused instructions.
-        if (!I->use_empty()) {
-          if (Value *V = SimplifyInstruction(I, SQ, ORE)) {
+        // Don't waste time simplifying dead/unused instructions.
+        if (isInstructionTriviallyDead(&I)) {
+          DeadInstsInBB.push_back(&I);
+        } else if (!I.use_empty()) {
+          if (Value *V = SimplifyInstruction(&I, SQ, ORE)) {
             // Mark all uses for resimplification next time round the loop.
-            for (User *U : I->users())
+            for (User *U : I.users())
               Next->insert(cast<Instruction>(U));
-            I->replaceAllUsesWith(V);
+            I.replaceAllUsesWith(V);
             ++NumSimplified;
             Changed = true;
+            // A call can get simplified, but it may not be trivially dead.
+            if (isInstructionTriviallyDead(&I))
+              DeadInstsInBB.push_back(&I);
           }
         }
-        if (RecursivelyDeleteTriviallyDeadInstructions(I, SQ.TLI)) {
-          // RecursivelyDeleteTriviallyDeadInstruction can remove more than one
-          // instruction, so simply incrementing the iterator does not work.
-          // When instructions get deleted re-iterate instead.
-          BI = BB->begin();
-          BE = BB->end();
-          Changed = true;
-        }
       }
+      RecursivelyDeleteTriviallyDeadInstructions(DeadInstsInBB, SQ.TLI);
     }
 
     // Place the list of instructions to simplify on the next loop iteration
     // into ToSimplify.
     std::swap(ToSimplify, Next);
     Next->clear();
   } while (!ToSimplify->empty());
 

llvm/test/Transforms/InstSimplify/assume.ll

;
   %a = alloca i32
   %t1 = ptrtoint i32* %a to i64, !dbg !9
   %cond = icmp eq i64 %t1, 3
   call void @llvm.assume(i1 %cond)
   ret i64 %t1
 }
 
 ; Similar to above: there's no way to know which assumption is truthful,
-; so just don't crash. The second icmp+assume gets processed later, so that
-; determines the return value.
+; so just don't crash.
 
 define i8 @conflicting_assumptions(i8 %x) !dbg !10 {
 ; CHECK-LABEL: @conflicting_assumptions(
+; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X:%.*]], 1, !dbg !10
 ; CHECK-NEXT:    call void @llvm.assume(i1 false)
-; CHECK-NEXT:    [[COND2:%.*]] = icmp eq i8 %x, 4
+; CHECK-NEXT:    [[COND2:%.*]] = icmp eq i8 [[X]], 4
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[COND2]])
-; CHECK-NEXT:    ret i8 5
+; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %add = add i8 %x, 1, !dbg !11
   %cond1 = icmp eq i8 %x, 3
   call void @llvm.assume(i1 %cond1)
   %cond2 = icmp eq i8 %x, 4
   call void @llvm.assume(i1 %cond2)
   ret i8 %add
 }