[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

3452

Period at the end of comments.

3457

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

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

2

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

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

11

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

3457

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;
+
+        // Check if a PHI node has reference-equal inputs which are terminated
+        // with non-splittable instructions
+        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/X86/issue48708.ll

+; 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.absl::Storage" = type {}
+%"struct.absl::allocator_traits" = type {}
+%"struct.absl::StorageView" = type { %"class.std::allocator"*, i32, i32 }
+%"class.std::allocator" = type { i8 }
+%"class.std::move_iterator" = type { i8 }
+
+define void @0(%"class.absl::Storage"* %0, %"struct.absl::allocator_traits" %1) personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
+  %3 = alloca %"struct.absl::StorageView", align 8
+  %4 = alloca i8, align 1
+  %5 = alloca %"class.std::move_iterator", align 8
+  %6 = bitcast %"struct.absl::StorageView"* %3 to i8*
+  %7 = call i8 @"forward@V"(i8 undef)
+  %8 = call %"class.std::allocator"* @"forward@PEAV"(%"class.std::allocator"* null)
+  %9 = getelementptr i8, i8* %4
+  %10 = getelementptr %"struct.absl::StorageView", %"struct.absl::StorageView"* %3, i64 0, i32 0
+  %11 = load %"class.std::allocator"*, %"class.std::allocator"** %10, align 8
+  %12 = invoke %"class.std::move_iterator"* @"move_iterator"(%"class.std::move_iterator"* %5, %"class.std::allocator"* %11)
+          to label %13 unwind label %33
+
+13:                                               ; preds = %2
+  %14 = getelementptr %"class.std::move_iterator", %"class.std::move_iterator"* %5, i64 0, i32 0
+  %15 = load i8, i8* %14, align 1
+  %16 = invoke i8* @"IteratorValueAdapter"(i8* %4, i8 5)
+          to label %17 unwind label %33
+
+17:                                               ; preds = %13
+  %18 = getelementptr %"struct.absl::StorageView", %"struct.absl::StorageView"* %3, i64 0, i32 2
+  %19 = load i32, i32* %18, align 4
+  %20 = icmp eq i32 9, 0
+  %21 = select i1 %20, %"class.std::allocator"* %8, %"class.std::allocator"* null
+  br label %22
+
+22:                                               ; preds = %25, %17
+  %23 = phi i64 [ %26, %25 ], [ 0, %17 ]
+  %24 = getelementptr %"class.std::allocator", %"class.std::allocator"* %21, i64 %23
+  invoke void @"ConstructNext"(i8* %4, %"class.std::allocator"* null, %"class.std::allocator"* %24)
+          to label %25 unwind label %27
+
+25:                                               ; preds = %22
+  %26 = add i64 %23, 1
+  br label %22
+
+27:                                               ; preds = %22
+  %28 = catchswitch within none [label %29] unwind label %33
+
+29:                                               ; preds = %27
+  %30 = catchpad within %28 []
+  catchret from %30 to label %31
+
+31:                                               ; preds = %29
+  invoke void @"SetIsAllocated"(%"class.absl::Storage"* %0)
+          to label %32 unwind label %33
+
+32:                                               ; preds = %31
+  unreachable
+
+33:                                               ; preds = %31, %27, %13, %2
+  %34 = phi %"class.std::allocator"* [ %21, %27 ], [ %21, %31 ], [ %8, %13 ], [ %8, %2 ]
+  %35 = cleanuppad within none []
+  cleanupret from %35 unwind to caller
+}
+
+declare %"class.std::move_iterator"* @"move_iterator"(%"class.std::move_iterator"*, %"class.std::allocator"*)
+declare i32 @__CxxFrameHandler3(...)
+declare i8* @"IteratorValueAdapter"(i8*, i8)
+declare void @"SetIsAllocated"(%"class.absl::Storage"*)
+declare i8 @"forward@V"(i8)
+declare %"class.std::allocator"* @"forward@PEAV"(%"class.std::allocator"*)
+declare void @"ConstructNext"(i8*, %"class.std::allocator"*, %"class.std::allocator"*)