[LICM] Do not hoist widenable conditions

[mkazantsev]

Summary

Despite the fact that it is legal, it is not profitable. Because of bug described at
https://github.com/llvm/llvm-project/issues/60234, now the guard widening is
only possible when condtion we want to add is available at the point of the
widenable_condition() of dominating guard. It means that, if all such calls are
hoisted out of loop, and the loop conditions depend on loop-variants, we cannot
widen. Hoisting is otherwise not helpful, because it does not introduce any
optimization opportunities.

[skatkov]

The change itself looks reasonable.

However it would be interesting to know the motivation this check has been added.

llvm/lib/Transforms/Scalar/LICM.cpp

1231–1232

why don't you want just to remove this match?
In my understanding by default LICM will touch it...

@apilipenko, this match has been added at https://reviews.llvm.org/D69907. Do you know any specific motivation to allow hoisting of widenable condition intrinsic? May be anything is missing?

[mkazantsev]

Hoisting was added in D69907. @apilipenko @reames do you agree it's a good enough reason to not do it?

llvm/lib/Transforms/Scalar/LICM.cpp

1231–1232

I want to keep the comment in anyways.

[mkazantsev]

Removed check, comment moved to test file.

[skatkov]

llvm/test/Transforms/LICM/explicit_guards.ll

7

I would move your comment here. This seems to be dedicated test for hoisting.

[mkazantsev]

Moved comment to other file.

[apilipenko]

Looks good to me. I don't think we had a specific motivation in mind for that change. And now we know a clear reason not to LICM widenable conditions.

llvm/test/Transforms/LICM/explicit_guards.ll

9

; Widenable conditions don't actually alias anything or throw, however
; hoisting them is not profitable because it may prevent guard widening in the loop.

llvm/lib/Transforms/Scalar/LICM.cpp

if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     // across control flow.
     if (CI->isConvergent())
       return false;
 
     using namespace PatternMatch;
     if (match(CI, m_Intrinsic<Intrinsic::assume>()))
       // Assumes don't actually alias anything or throw
       return true;
 
-    if (match(CI, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
-      // Widenable conditions don't actually alias anything or throw
-      return true;
-
     // Handle simple cases by querying alias analysis.
     MemoryEffects Behavior = AA->getMemoryEffects(CI);
     if (Behavior.doesNotAccessMemory())
       return true;
     if (Behavior.onlyReadsMemory()) {
       // A readonly argmemonly function only reads from memory pointed to by
       // it's arguments with arbitrary offsets.  If we can prove there are no
       // writes to this memory in the loop, we can hoist or sink.
       if (Behavior.onlyAccessesArgPointees()) {

llvm/test/Transforms/GuardWidening/two_forms_behavior_consistency.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt -S -passes="guard-widening,make-guards-explicit,simplifycfg" < %s        | FileCheck %s --check-prefixes=INTRINSIC_FORM
 ; RUN: opt -S -passes="make-guards-explicit,guard-widening,simplifycfg" < %s        | FileCheck %s --check-prefixes=BRANCH_FORM
 ; RUN: opt -S -passes="make-guards-explicit,loop-mssa(licm),guard-widening,simplifycfg" < %s        | FileCheck %s --check-prefixes=BRANCH_FORM_LICM
 
 declare i1 @cond() readonly
 
 ; FIXME We want to make sure that guard widening works in the same way, no matter what form of
 ;       guards it is dealing with.
-; FIXME We also want to make sure that LICM doesn't mess with widenable conditions, what might
-;       make things more complex.
+; We also want to make sure that LICM doesn't mess with widenable conditions, what might
+; make things more complex.
+
 define void @test_01(i32 %a, i32 %b, i32 %c, i32 %d) {
 ; INTRINSIC_FORM-LABEL: define void @test_01
 ; INTRINSIC_FORM-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32 [[D:%.*]]) {
 ; INTRINSIC_FORM-NEXT:  entry:
 ; INTRINSIC_FORM-NEXT:    br label [[LOOP:%.*]]
 ; INTRINSIC_FORM:       loop:
 ; INTRINSIC_FORM-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[GUARDED:%.*]] ]
 ; INTRINSIC_FORM-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1

 ; BRANCH_FORM-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; BRANCH_FORM-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; BRANCH_FORM:       exit:
 ; BRANCH_FORM-NEXT:    ret void
 ;
 ; BRANCH_FORM_LICM-LABEL: define void @test_01
 ; BRANCH_FORM_LICM-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32 [[D:%.*]]) {
 ; BRANCH_FORM_LICM-NEXT:  entry:
-; BRANCH_FORM_LICM-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; BRANCH_FORM_LICM-NEXT:    [[WIDENABLE_COND3:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; BRANCH_FORM_LICM-NEXT:    [[WIDENABLE_COND7:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; BRANCH_FORM_LICM-NEXT:    [[WIDENABLE_COND11:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; BRANCH_FORM_LICM-NEXT:    br label [[LOOP:%.*]]
 ; BRANCH_FORM_LICM:       loop:
-; BRANCH_FORM_LICM-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[GUARDED9:%.*]] ]
+; BRANCH_FORM_LICM-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[GUARDED5:%.*]] ]
 ; BRANCH_FORM_LICM-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; BRANCH_FORM_LICM-NEXT:    [[C1:%.*]] = icmp ult i32 [[IV]], [[A]]
-; BRANCH_FORM_LICM-NEXT:    [[EXIPLICIT_GUARD_COND:%.*]] = and i1 [[C1]], [[WIDENABLE_COND]]
 ; BRANCH_FORM_LICM-NEXT:    [[C2:%.*]] = icmp ult i32 [[IV]], [[B]]
-; BRANCH_FORM_LICM-NEXT:    [[EXIPLICIT_GUARD_COND4:%.*]] = and i1 [[C2]], [[WIDENABLE_COND3]]
-; BRANCH_FORM_LICM-NEXT:    [[OR_COND:%.*]] = select i1 [[EXIPLICIT_GUARD_COND]], i1 [[EXIPLICIT_GUARD_COND4]], i1 false
-; BRANCH_FORM_LICM-NEXT:    br i1 [[OR_COND]], label [[GUARDED1:%.*]], label [[DEOPT:%.*]], !prof [[PROF0:![0-9]+]]
+; BRANCH_FORM_LICM-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[C1]], [[C2]]
+; BRANCH_FORM_LICM-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; BRANCH_FORM_LICM-NEXT:    [[EXIPLICIT_GUARD_COND:%.*]] = and i1 [[WIDE_CHK]], [[WIDENABLE_COND]]
+; BRANCH_FORM_LICM-NEXT:    br i1 [[EXIPLICIT_GUARD_COND]], label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof [[PROF0:![0-9]+]]
 ; BRANCH_FORM_LICM:       deopt:
 ; BRANCH_FORM_LICM-NEXT:    call void (...) @llvm.experimental.deoptimize.isVoid() [ "deopt"() ]
 ; BRANCH_FORM_LICM-NEXT:    ret void
-; BRANCH_FORM_LICM:       guarded1:
+; BRANCH_FORM_LICM:       guarded:
+; BRANCH_FORM_LICM-NEXT:    [[WIDENABLE_COND3:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; BRANCH_FORM_LICM-NEXT:    [[EXIPLICIT_GUARD_COND4:%.*]] = and i1 [[C2]], [[WIDENABLE_COND3]]
 ; BRANCH_FORM_LICM-NEXT:    [[C3:%.*]] = icmp ult i32 [[IV]], [[C]]
-; BRANCH_FORM_LICM-NEXT:    [[EXIPLICIT_GUARD_COND8:%.*]] = and i1 [[C3]], [[WIDENABLE_COND7]]
 ; BRANCH_FORM_LICM-NEXT:    [[C4:%.*]] = icmp ult i32 [[IV]], [[D]]
-; BRANCH_FORM_LICM-NEXT:    [[EXIPLICIT_GUARD_COND12:%.*]] = and i1 [[C4]], [[WIDENABLE_COND11]]
-; BRANCH_FORM_LICM-NEXT:    [[OR_COND13:%.*]] = select i1 [[EXIPLICIT_GUARD_COND8]], i1 [[EXIPLICIT_GUARD_COND12]], i1 false
-; BRANCH_FORM_LICM-NEXT:    br i1 [[OR_COND13]], label [[GUARDED9]], label [[DEOPT6:%.*]], !prof [[PROF0]]
+; BRANCH_FORM_LICM-NEXT:    [[WIDE_CHK13:%.*]] = and i1 [[C3]], [[C4]]
+; BRANCH_FORM_LICM-NEXT:    [[WIDENABLE_COND7:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; BRANCH_FORM_LICM-NEXT:    [[EXIPLICIT_GUARD_COND8:%.*]] = and i1 [[WIDE_CHK13]], [[WIDENABLE_COND7]]
+; BRANCH_FORM_LICM-NEXT:    br i1 [[EXIPLICIT_GUARD_COND8]], label [[GUARDED5]], label [[DEOPT6:%.*]], !prof [[PROF0]]
 ; BRANCH_FORM_LICM:       deopt6:
 ; BRANCH_FORM_LICM-NEXT:    call void (...) @llvm.experimental.deoptimize.isVoid() [ "deopt"() ]
 ; BRANCH_FORM_LICM-NEXT:    ret void
-; BRANCH_FORM_LICM:       guarded9:
+; BRANCH_FORM_LICM:       guarded5:
+; BRANCH_FORM_LICM-NEXT:    [[WIDENABLE_COND11:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; BRANCH_FORM_LICM-NEXT:    [[EXIPLICIT_GUARD_COND12:%.*]] = and i1 [[C4]], [[WIDENABLE_COND11]]
 ; BRANCH_FORM_LICM-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; BRANCH_FORM_LICM-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; BRANCH_FORM_LICM:       exit:
 ; BRANCH_FORM_LICM-NEXT:    ret void
 ;
 entry:
   br label %loop
 

llvm/test/Transforms/LICM/explicit_guards.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,make-guards-explicit,loop-mssa(licm)' < %s | FileCheck %s
 
 declare void @llvm.experimental.guard(i1,...)
 declare void @maythrow()
 
 ; Make sure that we do not hoist widenable_cond out of loop.
-define void @hoist_widenable_cond(i1 %cond, i32 %N, i32 %M) {
-; CHECK-LABEL: @hoist_widenable_cond(
+; Widenable conditions don't actually alias anything or throw, however
+; hoisting them is not profitable because it can prevent guard widening
+; in loop.
+; If we want to widen guards in branch form, we need to generate them
+; at the point of widenable_condition call
+; (see https://github.com/llvm/llvm-project/issues/60234). Because of
+; this, hoisting a widenable condition out of loop can make widening of
+; in-loop conditions impossible (e.g. if they depend on loop variant). On
+; the other hand, hoisting of the WC doesn't really see profitable,
+; because it will be optimized away later anyways. So the test checks that
+; LICM will not move it out of loop.
+define void @do_not_hoist_widenable_cond(i1 %cond, i32 %N, i32 %M) {
+; CHECK-LABEL: @do_not_hoist_widenable_cond(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[GUARDED:%.*]] ]
 ; CHECK-NEXT:    [[GUARD_COND:%.*]] = icmp slt i32 [[IV]], [[N:%.*]]
+; CHECK-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[EXIPLICIT_GUARD_COND:%.*]] = and i1 [[GUARD_COND]], [[WIDENABLE_COND]]
-; CHECK-NEXT:    br i1 [[EXIPLICIT_GUARD_COND]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
+; CHECK-NEXT:    br i1 [[EXIPLICIT_GUARD_COND]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0:![0-9]+]]
 ; CHECK:       deopt:
 ; CHECK-NEXT:    call void (...) @llvm.experimental.deoptimize.isVoid() [ "deopt"() ]
 ; CHECK-NEXT:    ret void
 ; CHECK:       guarded:
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV]], [[M:%.*]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
loop:
   %loop_cond = icmp slt i32 %iv, %M
   %iv.next = add i32 %iv, 1
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret void
 }
 
-define void @hoist_widenable_cond_speculate(i1 %cond, i32 %N, i32 %M) {
-; CHECK-LABEL: @hoist_widenable_cond_speculate(
+define void @do_not_hoist_widenable_cond_speculate(i1 %cond, i32 %N, i32 %M) {
+; CHECK-LABEL: @do_not_hoist_widenable_cond_speculate(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[GUARDED:%.*]] ]
 ; CHECK-NEXT:    [[GUARD_COND:%.*]] = icmp slt i32 [[IV]], [[N:%.*]]
 ; CHECK-NEXT:    call void @maythrow()
+; CHECK-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[EXIPLICIT_GUARD_COND:%.*]] = and i1 [[GUARD_COND]], [[WIDENABLE_COND]]
-; CHECK-NEXT:    br i1 [[EXIPLICIT_GUARD_COND]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
+; CHECK-NEXT:    br i1 [[EXIPLICIT_GUARD_COND]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
 ; CHECK:       deopt:
 ; CHECK-NEXT:    call void (...) @llvm.experimental.deoptimize.isVoid() [ "deopt"() ]
 ; CHECK-NEXT:    ret void
 ; CHECK:       guarded:
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV]], [[M:%.*]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:

 exit:
   ret void
 }
 
 
 define void @hoist_invariant_load(i1 %cond, ptr %np, i32 %M) {
 ; CHECK-LABEL: @hoist_invariant_load(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[N:%.*]] = load i32, ptr [[NP:%.*]]
-; CHECK-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; CHECK-NEXT:    [[N:%.*]] = load i32, ptr [[NP:%.*]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[GUARDED:%.*]] ]
 ; CHECK-NEXT:    [[GUARD_COND:%.*]] = icmp slt i32 [[IV]], [[N]]
+; CHECK-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[EXIPLICIT_GUARD_COND:%.*]] = and i1 [[GUARD_COND]], [[WIDENABLE_COND]]
-; CHECK-NEXT:    br i1 [[EXIPLICIT_GUARD_COND]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
+; CHECK-NEXT:    br i1 [[EXIPLICIT_GUARD_COND]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
 ; CHECK:       deopt:
 ; CHECK-NEXT:    call void (...) @llvm.experimental.deoptimize.isVoid() [ "deopt"() ]
 ; CHECK-NEXT:    ret void
 ; CHECK:       guarded:
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV]], [[M:%.*]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit: