[SCEV][NFC][CT] Cheaper handling of guards in isBasicBlockEntryGuardedByCond

[mkazantsev]

Summary

Handle guards uniformly with assumes, rather than iterating through all
block instructions in attempt to find them.

[nikic]

LG if this is faster for you in practice.

Though I do have to wonder: Why are we not tracking guard intrinsics in AssumptionCache? Iterating over users of the declaration has the disadvantage that you may be looking at guards in many other functions, and that it will run into issues when we try to parallelize the pass manager. It seems like tracking them in AC the same way as assumptions shouldn't be too hard.

[mkazantsev]

Good question. I guess we just never got to do it. And parallelizing the PM will face much more problem than that. For example, we sometimes see a situation in SCEV when condition A implies B, but when we simplify A (e.g. replace with invariant), B is not always implyable. How many of these do we have - I don't know.

[mkazantsev]

In D129874#3659515, @nikic wrote:

LG if this is faster for you in practice.

Though I do have to wonder: Why are we not tracking guard intrinsics in AssumptionCache? Iterating over users of the declaration has the disadvantage that you may be looking at guards in many other functions, and that it will run into issues when we try to parallelize the pass manager. It seems like tracking them in AC the same way as assumptions shouldn't be too hard.

We don't really see impact because SCEV in our pipeline takes negligible time far less than noise. :( But hypothetically, this should be better because guards are not so numerous usually.

llvm/lib/Analysis/ScalarEvolution.cpp

bool ScalarEvolution::isBasicBlockEntryGuardedByCond(const BasicBlock *BB,
   if (ProvingStrictComparison) {
     auto ProofFn = [&](ICmpInst::Predicate P) {
       return isKnownViaNonRecursiveReasoning(P, LHS, RHS);
     };
     if (SplitAndProve(ProofFn))
       return true;
   }
 
-  // Try to prove (Pred, LHS, RHS) using isImpliedViaGuard.
-  auto ProveViaGuard = [&](const BasicBlock *Block) {
-    if (isImpliedViaGuard(Block, Pred, LHS, RHS))
-      return true;
-    if (ProvingStrictComparison) {
-      auto ProofFn = [&](ICmpInst::Predicate P) {
-        return isImpliedViaGuard(Block, P, LHS, RHS);
-      };
-      if (SplitAndProve(ProofFn))
-        return true;
-    }
-    return false;
-  };
-
   // Try to prove (Pred, LHS, RHS) using isImpliedCond.
   auto ProveViaCond = [&](const Value *Condition, bool Inverse) {
     const Instruction *CtxI = &BB->front();
     if (isImpliedCond(Pred, LHS, RHS, Condition, Inverse, CtxI))
       return true;
     if (ProvingStrictComparison) {
       auto ProofFn = [&](ICmpInst::Predicate P) {
         return isImpliedCond(P, LHS, RHS, Condition, Inverse, CtxI);
bool ScalarEvolution::isBasicBlockEntryGuardedByCond(const BasicBlock *BB,
   const Loop *ContainingLoop = LI.getLoopFor(BB);
   const BasicBlock *PredBB;
   if (ContainingLoop && ContainingLoop->getHeader() == BB)
     PredBB = ContainingLoop->getLoopPredecessor();
   else
     PredBB = BB->getSinglePredecessor();
   for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
        Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
-    if (ProveViaGuard(Pair.first))
-      return true;
-
     const BranchInst *BlockEntryPredicate =
         dyn_cast<BranchInst>(Pair.first->getTerminator());
     if (!BlockEntryPredicate || BlockEntryPredicate->isUnconditional())
       continue;
 
     if (ProveViaCond(BlockEntryPredicate->getCondition(),
                      BlockEntryPredicate->getSuccessor(0) != Pair.second))
       return true;
   }
 
   // Check conditions due to any @llvm.assume intrinsics.
   for (auto &AssumeVH : AC.assumptions()) {
     if (!AssumeVH)
       continue;
     auto *CI = cast<CallInst>(AssumeVH);
     if (!DT.dominates(CI, BB))
       continue;
 
     if (ProveViaCond(CI->getArgOperand(0), false))
       return true;
   }
 
+  // Check conditions due to any @llvm.experimental.guard intrinsics.
+  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() == BB->getParent() && DT.dominates(Guard, BB))
+          if (ProveViaCond(Guard->getArgOperand(0), false))
+            return true;
+  }
   return false;
 }
 
 bool ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
                                                ICmpInst::Predicate Pred,
                                                const SCEV *LHS,
                                                const SCEV *RHS) {
   // Interpret a null as meaning no loop, where there is obviously no guard