[SCEV] Add llvm.experimental.guard conditions to applyLoopGuards()

[caojoshua]

Summary

Conditions for dominating branches and llvm.assumes are already
collected. This also adds conditions from guards.

[caojoshua]

This comment was removed by caojoshua.

[nikic]

We should add support for guard intrinsics to AssumptionCache instead. For all practical purposes, they need the same handling, and it makes little sense that we keep implementing separate handling for assumes and guards each time.

[caojoshua]

In D141243#4035889, @nikic wrote:

We should add support for guard intrinsics to AssumptionCache instead. For all practical purposes, they need the same handling, and it makes little sense that we keep implementing separate handling for assumes and guards each time.

I agree with this thought, but this adds a lot of discussion and investigation to a simple PR. I've created https://github.com/llvm/llvm-project/issues/59901 to discuss this issue (can you leave your thoughts in the thread?), and I would not mind personally working on it.

In my opinion, we can still land this review, and work on this as a separate issue. Does this make sense?

[nikic]

In D141243#4036908, @caojoshua wrote:

In D141243#4035889, @nikic wrote:

We should add support for guard intrinsics to AssumptionCache instead. For all practical purposes, they need the same handling, and it makes little sense that we keep implementing separate handling for assumes and guards each time.

I agree with this thought, but this adds a lot of discussion and investigation to a simple PR. I've created https://github.com/llvm/llvm-project/issues/59901 to discuss this issue (can you leave your thoughts in the thread?), and I would not mind personally working on it.

In my opinion, we can still land this review, and work on this as a separate issue. Does this make sense?

Sure, as long as someone is working on fixing this properly, we can land this in the meantime. LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

15024

const SCEV *

llvm/lib/Analysis/ScalarEvolution.cpp

auto CollectCondition = [&](ICmpInst::Predicate Predicate, const SCEV *LHS,
     if (Predicate == CmpInst::ICMP_EQ && RHSC &&
         RHSC->getValue()->isNullValue()) {
       // If LHS is A % B, i.e. A % B == 0, rewrite A to (A /u B) * B to
       // explicitly express that.
       const SCEV *URemLHS = nullptr;
       const SCEV *URemRHS = nullptr;
       if (matchURem(LHS, URemLHS, URemRHS)) {
         if (const SCEVUnknown *LHSUnknown = dyn_cast<SCEVUnknown>(URemLHS)) {
-          auto Multiple = getMulExpr(getUDivExpr(URemLHS, URemRHS), URemRHS);
+          const auto *Multiple = getMulExpr(getUDivExpr(URemLHS, URemRHS), URemRHS);
           RewriteMap[LHSUnknown] = Multiple;
           ExprsToRewrite.push_back(LHSUnknown);
           return;
         }
       }
     }
 
     // Do not apply information for constants or if RHS contains an AddRec.
auto CollectCondition = [&](ICmpInst::Predicate Predicate, const SCEV *LHS,
 
     if (RewrittenRHS) {
       RewriteMap[LHS] = RewrittenRHS;
       if (LHS == RewrittenLHS)
         ExprsToRewrite.push_back(LHS);
     }
   };
 
+  BasicBlock *Header = L->getHeader();
   SmallVector<PointerIntPair<Value *, 1, bool>> Terms;
   // First, collect information from assumptions dominating the loop.
   for (auto &AssumeVH : AC.assumptions()) {
     if (!AssumeVH)
       continue;
     auto *AssumeI = cast<CallInst>(AssumeVH);
-    if (!DT.dominates(AssumeI, L->getHeader()))
+    if (!DT.dominates(AssumeI, Header))
       continue;
     Terms.emplace_back(AssumeI->getOperand(0), true);
   }
 
-  // Second, collect conditions from dominating branches. Starting at the loop
+  // Second, collect information from llvm.experimental.guards dominating the loop.
+  auto *GuardDecl = F.getParent()->getFunction(
+      Intrinsic::getName(Intrinsic::experimental_guard));
+  if (GuardDecl)
+    for (const auto *GU : GuardDecl->users())
+      if (const auto *Guard = dyn_cast<IntrinsicInst>(GU))
+        if (Guard->getFunction() == Header->getParent() && DT.dominates(Guard, Header))
+          Terms.emplace_back(Guard->getArgOperand(0), true);
+
+  // Third, collect conditions from dominating branches. Starting at the loop
   // predecessor, climb up the predecessor chain, as long as there are
   // predecessors that can be found that have unique successors leading to the
   // original header.
   // TODO: share this logic with isLoopEntryGuardedByCond.
   for (std::pair<const BasicBlock *, const BasicBlock *> Pair(
-           L->getLoopPredecessor(), L->getHeader());
+           L->getLoopPredecessor(), Header);
        Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
 
     const BranchInst *LoopEntryPredicate =
         dyn_cast<BranchInst>(Pair.first->getTerminator());
     if (!LoopEntryPredicate || LoopEntryPredicate->isUnconditional())
       continue;
 
     Terms.emplace_back(LoopEntryPredicate->getCondition(),

llvm/test/Analysis/ScalarEvolution/trip-multiple-guard-info.ll

for.body:
   %inc = add nuw nsw i32 %i.010, 1
   %cmp2 = icmp ult i32 %inc, %num
   br i1 %cmp2, label %for.body, label %exit
 
 exit:
   ret void
 }
 
+define void @test_trip_multiple_4_guard(i32 %num) {
+; CHECK-LABEL: 'test_trip_multiple_4_guard'
+; CHECK-NEXT:  Classifying expressions for: @test_trip_multiple_4
+; CHECK-NEXT:    %u = urem i32 %num, 4
+; CHECK-NEXT:    --> (zext i2 (trunc i32 %num to i2) to i32) U: [0,4) S: [0,4)
+; CHECK-NEXT:    %i.010 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %num) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    %inc = add nuw nsw i32 %i.010, 1
+; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%for.body> U: [1,-2147483648) S: [1,-2147483648) Exits: %num LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @test_trip_multiple_4
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
+; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -2
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 4
+;
+entry:
+  %u = urem i32 %num, 4
+  %cmp = icmp eq i32 %u, 0
+  call void(i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  %cmp.1 = icmp uge i32 %num, 4
+  call void(i1, ...) @llvm.experimental.guard(i1 %cmp.1) [ "deopt"() ]
+  br label %for.body
+
+for.body:
+  %i.010 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %inc = add nuw nsw i32 %i.010, 1
+  %cmp2 = icmp ult i32 %inc, %num
+  br i1 %cmp2, label %for.body, label %exit
+
+exit:
+  ret void
+}
+
 
 define void @test_trip_multiple_4_ugt_5(i32 %num) {
 ; CHECK-LABEL: 'test_trip_multiple_4_ugt_5'
 ; CHECK-NEXT:  Classifying expressions for: @test_trip_multiple_4_ugt_5
 ; CHECK-NEXT:    %u = urem i32 %num, 4
 ; CHECK-NEXT:    --> (zext i2 (trunc i32 %num to i2) to i32) U: [0,4) S: [0,4)
 ; CHECK-NEXT:    %i.010 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %num) LoopDispositions: { %for.body: Computable }
for.body:
   %cmp.1 = icmp ne i64 %iv.next, %N
   br i1 %cmp.1, label %for.body, label %exit
 
 exit:
   ret void
 }
 
 declare void @llvm.assume(i1)
+declare void @llvm.experimental.guard(i1, ...)