[LSR] Fix crash in Phi node with EHPad block

[lorenz]

Summary

This fixes a crash I observed in issue #48708 where the LSR
pass tries to insert an instruction in a basic block with only a
catchswitch statement in there. This happens because the Phi node
being evaluated assumes the same value for different basic blocks.

If the basic block associated with the incoming value of the operand
being evaluated has an EHPad terminator LSR skips optimizing it.
But if that incoming value can come from multiple different blocks
there can be some incoming basic blocks which are terminated in
an EHPad. If these are then rewritten in RewriteForPhi the ones
containing an EHPad terminator will hit the "Insertion point must
be a normal instruction" assert in AdjustInsertPositionForExpand.

This fix makes CollectLoopInvariantFixupsAndFormulae also ignore
cases where the same value has another incoming basic block with an
EHPad, same as it already does in case the primary value has one.

[lorenz]

Reviewers: Please note that I'm completely unfamiliar with the LLVM codebase. This might be complete nonsense. But it does fix my issue.

[qcolombet]

Hi,

Could you add a test case exposing the problem?

Ideally something that just needs to run LSR: opt -loop-reduce problematic_ir.ll -S -o -

Cheers,
-Quentin

[lorenz]

@qcolombet Have a look at the associated bug at https://bugs.llvm.org/show_bug.cgi?id=48708, there's a minimized IR reproducer in there.

[qcolombet]

@qcolombet Have a look at the associated bug at https://bugs.llvm.org/show_bug.cgi?id=48708, there's a minimized IR reproducer in there.

Great! Could you add that to this patch?

[lorenz]

Add reproducer as test case

[lorenz]

@qcolombet Friendly ping

[qcolombet]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3491

Period at the end of comments.

3496

Instead of iterating through all the incoming values, can we use Use::getOperandNo to only check the relevant one?

llvm/test/Transforms/LoopStrengthReduce/X86/issue48708.ll

1 ↗

(On Diff #333171)

Could you add check lines to make sure we do something sensible?
No crashing doesn't mean we are correct :).

2 ↗

(On Diff #333171)

Could you add a comment on what this test is checking and what we should/shouldn't observe here?
In particular putting the PR id here is a good idea.

3 ↗

(On Diff #333171)

Could you change the name of the test case to something more descriptive?

11 ↗

(On Diff #333171)

Could you get rid of the implicit variables (%[0-9]+)?
You can use opt -instnamer -S for that.

[omjavaid]

@lorenz are you still working on this issue? We are seeing this issue on LLVM for Windows on Arm while compiling TensorFlow with clang-cl.

[lorenz]

Improved test case and description of what condition this fixes exactly

[lorenz]

Remove leftover include

[lorenz]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3496

No, this won't work because this bug is specifically about handling cases where a single incoming value shows up multiple times from different basic blocks. It is necessary to look at all basic blocks.

[lorenz]

Pinging @qcolombet @reames

[lorenz]

Another ping for @qcolombet @lebedev.ri @reames after a month

[lorenz]

Thanks for the review! I don't have commit permission so arc land doesn't work for me. Can somebody land this?

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

else if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
           UserInst->getParent() :
           cast<PHINode>(UserInst)->getIncomingBlock(
             PHINode::getIncomingValueNumForOperand(U.getOperandNo()));
         if (!DT.dominates(L->getHeader(), UseBB))
           continue;
         // Don't bother if the instruction is in a BB which ends in an EHPad.
         if (UseBB->getTerminator()->isEHPad())
           continue;
+
+        // Ignore cases in which the currently-examined value could come from
+        // a basic block terminated with an EHPad. This checks all incoming
+        // blocks of the phi node since it is possible that the same incoming
+        // value comes from multiple basic blocks, only some of which may end
+        // in an EHPad. If any of them do, a subsequent rewrite attempt by this
+        // pass would try to insert instructions into an EHPad, hitting an
+        // assertion.
+        if (isa<PHINode>(UserInst)) {
+          const auto *PhiNode = cast<PHINode>(UserInst);
+          bool HasIncompatibleEHPTerminatedBlock = false;
+          llvm::Value *ExpectedValue = U;
+          for (unsigned int I = 0; I < PhiNode->getNumIncomingValues(); I++) {
+            if (PhiNode->getIncomingValue(I) == ExpectedValue) {
+              if (PhiNode->getIncomingBlock(I)->getTerminator()->isEHPad()) {
+                HasIncompatibleEHPTerminatedBlock = true;
+                break;
+              }
+            }
+          }
+          if (HasIncompatibleEHPTerminatedBlock) {
+            continue;
+          }
+        }
+
         // Don't bother rewriting PHIs in catchswitch blocks.
         if (isa<CatchSwitchInst>(UserInst->getParent()->getTerminator()))
           continue;
         // Ignore uses which are part of other SCEV expressions, to avoid
         // analyzing them multiple times.
         if (SE.isSCEVable(UserInst->getType())) {
           const SCEV *UserS = SE.getSCEV(const_cast<Instruction *>(UserInst));
           // If the user is a no-op, look through to its uses.

llvm/test/Transforms/LoopStrengthReduce/phi_ehpad_ignore_sameval.ll

+; This tests that LoopStrengthReduce ignores possible optimizations that are
+; not realizable because they would require rewriting EHPad-class instructions.
+; If this type of optimization is attempted it will hit the
+; "Insertion point must be a normal instruction" assertion.
+;
+; See also https://bugs.llvm.org/show_bug.cgi?id=48708
+;
+; RUN: opt -loop-reduce -S %s
+
+target datalayout = "e-m:w-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:6:2:64-S128"
+
+%"class.std::allocator" = type { i8 }
+%"class.absl::Storage" = type {}
+
+define void @0() personality i8* undef {
+init1:
+  %i14 = invoke i8* undef(i8* null, i8 0)
+          to label %init2 unwind label %unwind
+
+init2:                                            ; preds = %init1
+  %i19 = select i1 undef, %"class.std::allocator"* null, %"class.std::allocator"* null
+  br label %loop
+
+loop:                                             ; preds = %loop.increment, %init2
+  %i21 = phi i64 [ %i24, %loop.increment ], [ 0, %init2 ]
+  %i22 = getelementptr %"class.std::allocator", %"class.std::allocator"* %i19, i64 %i21
+  invoke void undef(i8* null, %"class.std::allocator"* null, %"class.std::allocator"* %i22)
+          to label %loop.increment unwind label %loop.unwind
+
+loop.increment:                                   ; preds = %loop
+  %i24 = add i64 %i21, 1
+  br label %loop
+
+loop.unwind:                                      ; preds = %loop
+  %i26 = catchswitch within none [label %loop.catch] unwind label %unwind
+
+loop.catch:                                       ; preds = %loop.unwind
+  %i28 = catchpad within %i26 []
+  catchret from %i28 to label %caught
+
+caught:                                           ; preds = %loop.catch
+  invoke void undef(%"class.absl::Storage"* null)
+          to label %unreach unwind label %unwind
+
+unreach:                                          ; preds = %caught
+  unreachable
+
+unwind:                                           ; preds = %caught, %loop.unwind, %init1
+  ; This phi node triggers the issue in combination with the optimizable loop
+  ; above. It contains %i19 twice, once from %caught (which doesn't have an
+  ; EHPad) and once from %loop.unwind, which does have one.
+  %i32 = phi %"class.std::allocator"* [ %i19, %loop.unwind ], [ %i19, %caught ], [ null, %init1 ]
+  %i33 = cleanuppad within none []
+  cleanupret from %i33 unwind to caller
+}