[LICM] Hoist widenable condition when it's the only non-invariant operand of its user

[skatkov]

llvm/lib/Transforms/Scalar/LICM.cpp

1243

Why do you need to iterate over uses instead of users?

[mkazantsev]

llvm/lib/Transforms/Scalar/LICM.cpp

1240

Imagine case:
Test 1:

c1 = load // can be hoisted
wc = call widenable_condition()
and = c1 & wc

Test 2:

wc = call widenable_condition()
c1 = load // can be hoisted
and = c1 & wc

If c1 is processed first and gets hoisted, then you also hoist wc and then and. But if wc is processed first, c1 is not yet made invariant, then you don't hoist neither wc nor and. I think you can construct a test demonstrating that by just putting wc ahead of c1.

The right solution would be to handle this when processing the user of wc (in this case it is and). If all of instruction's operands that are not loop-invariant are single-use widenable conditions, then all of them can be hoisted together with the and. In this case, you have a guarantee that everything that is not wc and that is hoistable has already been hoisted.

llvm/lib/Transforms/Scalar/LICM.cpp

if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     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>())) {
+      // Hoist widenable condition when it's the only non-invariant operand of
+      // its user
+      for (const Use &U : CI->uses())
+        if (const Instruction *UI = dyn_cast<Instruction>(U.getUser()))
+          for (const Use &Op : UI->operands()) {
+            const Instruction *OpI = dyn_cast<Instruction>(Op.get());
+            if (OpI && OpI != &I && !CurLoop->isLoopInvariant(OpI))
+              return false;
+          }
+      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.

llvm/test/Transforms/LICM/explicit_guards.ll

 
 ; TODO: Hoist widenable condition out of loop since it's the only
 ; non-invariant operand of its user
 define void @hoist_widenable_cond(ptr %p, i32 %x) {
 ; CHECK-LABEL: @hoist_widenable_cond(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LOAD:%.*]] = load atomic i32, ptr [[P:%.*]] unordered, align 8
 ; CHECK-NEXT:    [[ICMP7:%.*]] = icmp ult i32 0, [[LOAD]]
+; CHECK-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; CHECK-NEXT:    [[EXIPLICIT_GUARD_COND:%.*]] = and i1 [[ICMP7]], [[WIDENABLE_COND]]
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop.header:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[ICMP:%.*]] = icmp ult i32 [[IV]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[ICMP]], label [[LOOP_BODY:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.body:
-; CHECK-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; CHECK-NEXT:    [[EXIPLICIT_GUARD_COND:%.*]] = and i1 [[ICMP7]], [[WIDENABLE_COND]]
 ; CHECK-NEXT:    br i1 [[EXIPLICIT_GUARD_COND]], label [[GUARDED1:%.*]], label [[DEOPT:%.*]], !prof [[PROF0]]
 ; CHECK:       deopt:
 ; CHECK-NEXT:    call void (...) @llvm.experimental.deoptimize.isVoid(i32 13) [ "deopt"() ]
 ; CHECK-NEXT:    ret void
 ; CHECK:       guarded1:
 ; CHECK-NEXT:    br label [[GUARDED]]
 ; CHECK:       guarded:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1