[InstCombine] Add PHINode operands to worklist on instruction erasure

[luke]

Summary

If a phi node has one use, and that user has only one use itself, and
that one use is in turn the phi node, then the phi node is erased.
Simultaneously, whenever an instruction is erased, its operands are
added to the worklist as their use counts have changed.

But it's possible that the operand now only has one use and that use is
a phi node: So add the phi node to worklist so the phi node elimination
can occur.

This prevents the need to do lots of cascading iterations over a
function when eliminating phi nodes unlocks more potential phi node
eliminations.

Fixes #50564

[luke]

Remove erroneous include

[luke]

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

422

Will this cause much extra work?
It certainly improves the pathological case in https://github.com/llvm/llvm-project/issues/50564, but not sure how this affects day to day cases.

The PHI node elimination that kicks in is at InstCombinePHI.cpp:1439

cpp
 // If this phi has a single use, and if that use just computes a value for 
 // the next iteration of a loop, delete the phi.  This occurs with unused 
 // induction variables, e.g. "for (int j = 0; ; ++j);".  Detecting this 
 // common case here is good because the only other things that catch this 
 // are induction variable analysis (sometimes) and ADCE, which is only run 
 // late. 
 if (PHIUser->hasOneUse() && 
     (isa<BinaryOperator>(PHIUser) || isa<GetElementPtrInst>(PHIUser)) && 
     PHIUser->user_back() == &PN) { 
   return replaceInstUsesWith(PN, PoisonValue::get(PN.getType())); 
 }

Another possible idea could be to somehow invert this and instead check on every instruction if it has one use that's a phi node.

[luke]

llvm/test/Transforms/InstCombine/phi-elimination-iteration.ll

17

Prior to this patch, three iterations are carried out because the %phi.a isn't added to the worklist

[nikic]

Hm, this feels very hacky. I don't like the idea of adjusting the worklist management for specific patterns.

To suggest a possible alternative, it might be possible to extend isDeadPHICycle(), by making it look through side-effect free instructions, as well as multiple users. This will allow it to remove larger dead phi cycles, so it would not just peel off one phi cycle at a time, but could remove the whole graph at once. (Of course subject to the visitation limit -- with the current one of 16, that would mean we could remove 8 nested phi cycles in one go, which is probably good enough?)

llvm/test/Transforms/InstCombine/phi-elimination-iteration.ll

1

Use -instcombine-infinite-loop-threshold=2 to make sure it folds in one iteration instead.

[luke]

In D142293#4079311, @nikic wrote:

Hm, this feels very hacky. I don't like the idea of adjusting the worklist management for specific patterns.

To suggest a possible alternative, it might be possible to extend isDeadPHICycle(), by making it look through side-effect free instructions, as well as multiple users. This will allow it to remove larger dead phi cycles, so it would not just peel off one phi cycle at a time, but could remove the whole graph at once. (Of course subject to the visitation limit -- with the current one of 16, that would mean we could remove 8 nested phi cycles in one go, which is probably good enough?)

I agree, I'm not a huge fan of this either. That sounds like a better direction: I'll look into it, thanks

[nikic]

Marking this as changes requested for now, we'll can go back to it if that doesn't work out.

[luke]

Superseded by D142551

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
   Instruction *eraseInstFromFunction(Instruction &I) override {
     LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
     assert(I.use_empty() && "Cannot erase instruction that is used!");
     salvageDebugInfo(I);
 
     // Make sure that we reprocess all operands now that we reduced their
     // use counts.
     for (Use &Operand : I.operands())
-      if (auto *Inst = dyn_cast<Instruction>(Operand))
+      if (auto *Inst = dyn_cast<Instruction>(Operand)) {
         Worklist.add(Inst);
+        // If this instruction uses a phi node then we need to process the phi
+        // node, as it may potentially be able to delete it
+        for (Use &OpOp : Inst->operands())
+          if (auto *PN = dyn_cast<PHINode>(OpOp))
+            Worklist.add(PN);
+      }
 
     Worklist.remove(&I);
     I.eraseFromParent();
     MadeIRChange = true;
     return nullptr; // Don't do anything with FI
   }
 
   OverflowResult computeOverflow(

llvm/test/Transforms/InstCombine/phi-elimination-iteration.ll

+; RUN: opt < %s -passes=instcombine -S -debug 2>&1 | FileCheck %s
+define void @f() {
+entry:
+  br label %a
+a:
+  %phi.a = phi i32 [ 0, %entry ], [ %x, %a ]
+  %x = add i32 %phi.a, 1
+  br i1 false, label %a, label %b
+b:
+  %phi.b = phi i32 [ %x, %a ], [ %y, %b ]
+  %y = add i32 %phi.b, 1
+  br label %b
+}
+
+; CHECK: INSTCOMBINE ITERATION #1
+; CHECK: INSTCOMBINE ITERATION #2
+; CHECK-NOT: INSTCOMBINE ITERATION #3
+; CHECK-LABEL: a:
+; CHECK-NEXT:    br i1 false, label %a, label %b
+; CHECK-LABEL: b:
+; CHECK-NEXT:    br label %b