[LoopPredication] Miscompile due to sinking of widenable condition into loop

[xortator]

https://godbolt.org/z/8j953fhT6

Run opt -passes=loop-predication on the following IR:

define i32 @test() {
entry:
  %wc = call i1 @llvm.experimental.widenable.condition()
  br label %outer_loop

outer_backedge:                                   ; preds = %always, %never
  call void @print()
  %cnt.next = add i32 %cnt, 1
  br label %outer_loop

outer_loop:                                       ; preds = %outer_backedge, %entry
  %cnt = phi i32 [0, %entry], [%cnt.next, %outer_backedge]
  br i1 %wc, label %inner_loop.preheader, label %exit

inner_loop.preheader:                             ; preds = %outer_loop
  br label %inner_loop

inner_loop:                                       ; preds = %never, %inner_loop.preheader
  %iv = phi i32 [ %iv.next, %never ], [ 2, %inner_loop.preheader ]
  %iv.next = add nuw nsw i32 %iv, 1
  br i1 false, label %never, label %always

never:                                            ; preds = %inner_loop
  %icmp = icmp ugt i32 %iv.next, 37
  br i1 %icmp, label %outer_backedge, label %inner_loop

exit:                                             ; preds = %outer_loop
  %cnt.lcssa = phi i32 [%cnt, %outer_loop]
  ret i32 %cnt.lcssa

always:                                           ; preds = %inner_loop
  br label %outer_backedge
}

declare void @print()

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(inaccessiblemem: readwrite)
declare noundef i1 @llvm.experimental.widenable.condition() #0

attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(inaccessiblemem: readwrite) }

Result:

; ModuleID = './reduced.ll'
source_filename = "./reduced.ll"

define void @test() {
entry:
  br label %outer_loop

outer_backedge.loopexit:                          ; preds = %never
  br label %outer_backedge

outer_backedge:                                   ; preds = %outer_backedge.loopexit, %always
  br label %outer_loop

outer_loop:                                       ; preds = %outer_backedge, %entry
  %wc = call i1 @llvm.experimental.widenable.condition()
  br i1 %wc, label %inner_loop.preheader, label %exit

inner_loop.preheader:                             ; preds = %outer_loop
  br label %inner_loop

inner_loop:                                       ; preds = %never, %inner_loop.preheader
  %iv = phi i32 [ %iv.next, %never ], [ 2, %inner_loop.preheader ]
  %iv.next = add nuw nsw i32 %iv, 1
  br i1 false, label %never, label %always

never:                                            ; preds = %inner_loop
  %icmp = icmp ugt i32 %iv.next, 37
  br i1 %icmp, label %outer_backedge.loopexit, label %inner_loop

exit:                                             ; preds = %outer_loop
  ret void

always:                                           ; preds = %inner_loop
  br label %outer_backedge
}

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(inaccessiblemem: readwrite)
declare noundef i1 @llvm.experimental.widenable.condition() #0

attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(inaccessiblemem: readwrite) }

The issue is similar to #60234 (but then it was in Guard Widening). We are not allowed to sink widenable conditions into loops. Here is why it is a miscompile:

The behavior of program before the transform is limited to 2 scenarios:

• If %wc is true, branch will always go into the inner loop, and the program will infinitely call @print(). Program never returns.
• If %wc is false, program returns 0, and @print() is never called.

This allows us to optimize return value to ret i32 0 (IndVars actually does it, but it also eliminates some other code and breaks the example for unrelated reasons).

After the reansform, %wc is computed in the loop. It means that the legal scenario is that the program calls @print() 10 times and then exits, returning 10. It was impossible scenario before the transform.

This code in Loop Predication is wrong: https://gitlab.azulsystems.com/dev/orca/-/blob/master/llvm/lib/Transforms/Scalar/LoopPredication.cpp#L1195

[xortator]

[LoopPredication] Fix where we generate widened condition. PR61963

Loop predication's predicateLoopExit pass does two incorrect things:

It sinks the widenable call into the loop, thereby converting an invariant condition to a variant one
It widens the widenable call at a branch thereby converting the branch into a loop-varying one.

The latter is problematic when the branch may have been loop-invariant
and prior optimizations (such as indvars) may have relied on this
fact, and updated the deopt state accordingly.

Now, when we widen this with a loop-varying condition, the deopt state
is no longer correct.
https://github.com/llvm/llvm-project/issues/61963 fixed.

Differential Revision: https://reviews.llvm.org/D147662