[GuardUtils] Allow intermmediate blocks between widenable branch and deopt block

[nikic]

llvm/lib/Analysis/GuardUtils.cpp

54

Could cause an infinite loop if DeoptBB is part of a trivial cycle?

[apilipenko]

Why do we even care that an edge from a widenable condition branch terminates with a deopt? Widenable condition alone should be enough for widening.

We might want to know that a widened condition will result in a deopt for profitability purposes. We know that a deopt path is very unlikely and the runtime will be able to heal from the widening if we go that path. But we can check for these concerns separately and explicitly. We can use BFI to determine if a path is rare. We can introduce a new metadata to mark branches that can be healed after widening.

BTW, we use make implicit metadata for a similar purpose - to indicate that a branch can be "speculated" and the runtime can heal from this speculation.

[skatkov]

In D151082#4363081, @apilipenko wrote:

Why do we even care that an edge from a widenable condition branch terminates with a deopt? Widenable condition alone should be enough for widening.

We might want to know that a widened condition will result in a deopt for profitability purposes. We know that a deopt path is very unlikely and the runtime will be able to heal from the widening if we go that path. But we can check for these concerns separately and explicitly. We can use BFI to determine if a path is rare. We can introduce a new metadata to mark branches that can be healed after widening.

BTW, we use make implicit metadata for a similar purpose - to indicate that a branch can be "speculated" and the runtime can heal from this speculation.

Generally, I agree. But I propose to move step by step. This patch slightly increase the scope of optimization and does not touch what you mentioned as potential profitability.
I think that significant increase of an optimization scope might be done but it is a separate project. We can return to it back if needed.

llvm/lib/Analysis/GuardUtils.cpp

54

Thanks, fixed.

[anna]

LGTM. I agree we can do the refactoring to profitability as follow-up.

llvm/lib/Analysis/GuardUtils.cpp

41

JFI: As part of the follow-up where the check is for profitability, rather than this being needed for functional correctness, we can collapse this entire block into IsBlockFollowedByDeoptOrUnreachable (since we need not check for mayHaveSideEffects).

[anna]

llvm/lib/Analysis/GuardUtils.cpp

41

that API has also the benefit it has a cut-off for successor walking: MaxDeoptOrUnreachableSuccessorCheckDepth.

llvm/lib/Analysis/GuardUtils.cpp

 }
 
 bool llvm::isGuardAsWidenableBranch(const User *U) {
   Value *Condition, *WidenableCondition;
   BasicBlock *GuardedBB, *DeoptBB;
   if (!parseWidenableBranch(U, Condition, WidenableCondition, GuardedBB,
                             DeoptBB))
     return false;
+  SmallPtrSet<const BasicBlock *, 2> Visited;
+  Visited.insert(DeoptBB);
+  do {
     for (auto &Insn : *DeoptBB) {
       if (match(&Insn, m_Intrinsic<Intrinsic::experimental_deoptimize>()))
         return true;
       if (Insn.mayHaveSideEffects())
         return false;
     }
+    DeoptBB = DeoptBB->getUniqueSuccessor();
+    if (!DeoptBB)
+      return false;
+  } while (Visited.insert(DeoptBB).second);
   return false;
 }
 
 bool llvm::parseWidenableBranch(const User *U, Value *&Condition,
                                 Value *&WidenableCondition,
                                 BasicBlock *&IfTrueBB, BasicBlock *&IfFalseBB) {
 
   Use *C, *WC;
   if (parseWidenableBranch(const_cast<User*>(U), C, WC, IfTrueBB, IfFalseBB)) {
     if (C)
       Condition = C->get();
     else
       Condition = ConstantInt::getTrue(IfTrueBB->getContext());
     WidenableCondition = WC->get();
     return true;

llvm/test/Transforms/LoopPredication/basic_widenable_branch_guards.ll

guarded:                                          ; preds = %loop
   %continue = icmp ult i32 %i.next, %n
   br i1 %continue, label %loop, label %exit, !prof !2
 
 exit:                                             ; preds = %guarded, %entry
   %result = phi i32 [ 0, %entry ], [ %loop.acc.next, %guarded ]
   ret i32 %result
 }
 
+define i32 @unsigned_loop_0_to_n_ult_check_deep_deopt(ptr %array, i32 %length, i32 %n) {
+; CHECK-LABEL: @unsigned_loop_0_to_n_ult_check_deep_deopt(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[N:%.*]], 0
+; CHECK-NEXT:    br i1 [[TMP5]], label [[EXIT:%.*]], label [[LOOP_PREHEADER:%.*]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ule i32 [[N]], [[LENGTH:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 0, [[LENGTH]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[TMP1]], [[TMP0]]
+; CHECK-NEXT:    [[TMP3:%.*]] = freeze i1 [[TMP2]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH]]
+; CHECK-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; CHECK-NEXT:    [[TMP4:%.*]] = and i1 [[TMP3]], [[WIDENABLE_COND]]
+; CHECK-NEXT:    br i1 [[TMP4]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
+; CHECK:       deopt:
+; CHECK-NEXT:    br label [[REAL_DEOPT:%.*]]
+; CHECK:       real_deopt:
+; CHECK-NEXT:    [[DEOPTCALL:%.*]] = call i32 (...) @llvm.experimental.deoptimize.i32(i32 9) [ "deopt"() ]
+; CHECK-NEXT:    ret i32 [[DEOPTCALL]]
+; CHECK:       guarded:
+; CHECK-NEXT:    call void @llvm.assume(i1 [[WITHIN_BOUNDS]])
+; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
+; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY:%.*]], i64 [[I_I64]]
+; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, ptr [[ARRAY_I_PTR]], align 4
+; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
+; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
+; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
+; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]], !prof [[PROF1]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    [[LOOP_ACC_NEXT_LCSSA:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_ACC_NEXT_LCSSA]], [[EXIT_LOOPEXIT]] ]
+; CHECK-NEXT:    ret i32 [[RESULT]]
+;
+entry:
+  %tmp5 = icmp eq i32 %n, 0
+  br i1 %tmp5, label %exit, label %loop.preheader
+
+loop.preheader:                                   ; preds = %entry
+  br label %loop
+
+loop:                                             ; preds = %guarded, %loop.preheader
+  %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
+  %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
+  %within.bounds = icmp ult i32 %i, %length
+  %widenable_cond = call i1 @llvm.experimental.widenable.condition()
+  %exiplicit_guard_cond = and i1 %within.bounds, %widenable_cond
+  br i1 %exiplicit_guard_cond, label %guarded, label %deopt, !prof !0
+
+deopt:                                            ; preds = %loop
+  br label %real_deopt
+
+real_deopt:                                       ; preds = %deopt
+  %deoptcall = call i32 (...) @llvm.experimental.deoptimize.i32(i32 9) [ "deopt"() ]
+  ret i32 %deoptcall
+
+guarded:                                          ; preds = %loop
+  %i.i64 = zext i32 %i to i64
+  %array.i.ptr = getelementptr inbounds i32, ptr %array, i64 %i.i64
+  %array.i = load i32, ptr %array.i.ptr, align 4
+  %loop.acc.next = add i32 %loop.acc, %array.i
+  %i.next = add nuw i32 %i, 1
+  %continue = icmp ult i32 %i.next, %n
+  br i1 %continue, label %loop, label %exit, !prof !2
+
+exit:                                             ; preds = %guarded, %entry
+  %result = phi i32 [ 0, %entry ], [ %loop.acc.next, %guarded ]
+  ret i32 %result
+}
+
 declare i32 @llvm.experimental.deoptimize.i32(...)
 
 ; Function Attrs: inaccessiblememonly nounwind
 declare i1 @llvm.experimental.widenable.condition() #0
 
 attributes #0 = { inaccessiblememonly nounwind }
 
 !0 = !{!"branch_weights", i32 1048576, i32 1}
 !1 = !{i32 1, i32 -2147483648}
 !2 = !{!"branch_weights", i32 1024, i32 1}