[SCEV] Check inverse eagerly in isBasicBlockEntryGuardedByCond [NFC]

[reames]

Summary

This is an attempt at a compile time optimization for SCEV. (Pending data) The basic idea is to check both the predicate and it's inverse at the same time while walking the CFG.

This should help in two cases:

1. In the case where the inverse can be proven closer to the query context, running the entire search for the predicate before trying the inverse is very wasteful.
2. In the case where we can't prove either, we've reduced memory traffic by performing a single CFG walk instead of two.

This could hurt for the case where we prove the predicate since we've run the inverse logic along the way. My intuition is that the benefit will outweigh the cost, but let's see what the data says.

Note: The test changes are in dead code, and thus either result is equally correct.

[lebedev.ri]

Appears to be worse overall: https://llvm-compile-time-tracker.com/compare.php?from=19d2c65ddd757997785163709800f837857f686d&to=c1a140ac610725bdc4b3c27c3c72766111916b1b&stat=instructions

[reames]

Abandoned as theory and practice don't match per the measurements.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
 
   /// Test whether entry to the loop is protected by a conditional between LHS
   /// and RHS.  This is used to help avoid max expressions in loop trip
   /// counts, and to eliminate casts.
   bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
                                 const SCEV *LHS, const SCEV *RHS);
 
   /// Test whether entry to the basic block is protected by a conditional
-  /// between LHS and RHS.
-  bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB,
-                                      ICmpInst::Predicate Pred, const SCEV *LHS,
-                                      const SCEV *RHS);
+  /// between LHS and RHS.  Returns true if proven by dominating control flow,
+  /// false if disproven, or None if we can't tell.
+  Optional<bool>
+  isBasicBlockEntryGuardedByCond(const BasicBlock *BB,
 
   /// Test whether the backedge of the loop is protected by a conditional
   /// between LHS and RHS.  This is used to eliminate casts.
   bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
                                    const SCEV *LHS, const SCEV *RHS);
 
   /// Returns the maximum trip count of the loop if it is a single-exit
   /// loop and we can compute a small maximum for that loop.

llvm/lib/Analysis/ScalarEvolution.cpp

 Optional<bool>
 ScalarEvolution::evaluatePredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS,
                                      const SCEV *RHS,
                                      const Instruction *Context) {
   Optional<bool> KnownWithoutContext = evaluatePredicate(Pred, LHS, RHS);
   if (KnownWithoutContext)
     return KnownWithoutContext;
 
-  if (isBasicBlockEntryGuardedByCond(Context->getParent(), Pred, LHS, RHS))
-    return true;
-  else if (isBasicBlockEntryGuardedByCond(Context->getParent(),
-                                          ICmpInst::getInversePredicate(Pred),
-                                          LHS, RHS))
-    return false;
-  return None;
+  return isBasicBlockEntryGuardedByCond(Context->getParent(), Pred, LHS, RHS);
 }
 
 bool ScalarEvolution::isKnownOnEveryIteration(ICmpInst::Predicate Pred,
                                               const SCEVAddRecExpr *LHS,
                                               const SCEV *RHS) {
   const Loop *L = LHS->getLoop();
   return isLoopEntryGuardedByCond(L, Pred, LHS->getStart(), RHS) &&
          isLoopBackedgeGuardedByCond(L, Pred, LHS->getPostIncExpr(*this), RHS);
if (DominatingEdge.isSingleEdge()) {
                         BB != ContinuePredicate->getSuccessor(0)))
         return true;
     }
   }
 
   return false;
 }
 
-bool ScalarEvolution::isBasicBlockEntryGuardedByCond(const BasicBlock *BB,
-                                                     ICmpInst::Predicate Pred,
-                                                     const SCEV *LHS,
-                                                     const SCEV *RHS) {
+Optional<bool>
+ScalarEvolution::isBasicBlockEntryGuardedByCond(const BasicBlock *BB,
   if (VerifyIR)
     assert(!verifyFunction(*BB->getParent(), &dbgs()) &&
            "This cannot be done on broken IR!");
 
+  const auto InversePred = ICmpInst::getInversePredicate(Pred);
+
   // If we cannot prove strict comparison (e.g. a > b), maybe we can prove
   // the facts (a >= b && a != b) separately. A typical situation is when the
   // non-strict comparison is known from ranges and non-equality is known from
   // dominating predicates. If we are proving strict comparison, we always try
   // to prove non-equality and non-strict comparison separately.
   auto NonStrictPredicate = ICmpInst::getNonStrictPredicate(Pred);
   const bool ProvingStrictComparison = (Pred != NonStrictPredicate);
   bool ProvedNonStrictComparison = false;
   bool ProvedNonEquality = false;
 
   auto SplitAndProve =
-    [&](std::function<bool(ICmpInst::Predicate)> Fn) -> bool {
-    if (!ProvedNonStrictComparison)
+    [&](std::function<bool(ICmpInst::Predicate)> Fn) -> Optional<bool> {
+    if (!ProvedNonStrictComparison) {
+      if (Fn(ICmpInst::getInversePredicate(NonStrictPredicate)))
+        return false;
       ProvedNonStrictComparison = Fn(NonStrictPredicate);
-    if (!ProvedNonEquality)
+    }
+    if (!ProvedNonEquality) {
+      if (Fn(ICmpInst::ICMP_EQ))
+        return false;
       ProvedNonEquality = Fn(ICmpInst::ICMP_NE);
+    }
     if (ProvedNonStrictComparison && ProvedNonEquality)
       return true;
-    return false;
+    return None;
   };
 
   if (ProvingStrictComparison) {
     auto ProofFn = [&](ICmpInst::Predicate P) {
       return isKnownViaNonRecursiveReasoning(P, LHS, RHS);
     };
-    if (SplitAndProve(ProofFn))
-      return true;
+    if (auto Opt = SplitAndProve(ProofFn))
+      return Opt;
   }
 
   // Try to prove (Pred, LHS, RHS) using isImpliedViaGuard.
-  auto ProveViaGuard = [&](const BasicBlock *Block) {
+  auto ProveViaGuard = [&](const BasicBlock *Block) -> Optional<bool> {
     if (isImpliedViaGuard(Block, Pred, LHS, RHS))
       return true;
+    if (isImpliedViaGuard(Block, InversePred, LHS, RHS))
+      return false;
+
     if (ProvingStrictComparison) {
       auto ProofFn = [&](ICmpInst::Predicate P) {
         return isImpliedViaGuard(Block, P, LHS, RHS);
       };
-      if (SplitAndProve(ProofFn))
-        return true;
+      if (auto Opt = SplitAndProve(ProofFn))
+        return Opt;
     }
-    return false;
+    return None;
   };
 
   // Try to prove (Pred, LHS, RHS) using isImpliedCond.
-  auto ProveViaCond = [&](const Value *Condition, bool Inverse) {
+  auto ProveViaCond = [&](const Value *Condition, bool Inverse)
+    -> Optional<bool> {
     const Instruction *Context = &BB->front();
     if (isImpliedCond(Pred, LHS, RHS, Condition, Inverse, Context))
       return true;
+    if (isImpliedCond(InversePred, LHS, RHS, Condition, Inverse, Context))
+      return false;
     if (ProvingStrictComparison) {
       auto ProofFn = [&](ICmpInst::Predicate P) {
         return isImpliedCond(P, LHS, RHS, Condition, Inverse, Context);
       };
-      if (SplitAndProve(ProofFn))
-        return true;
+      if (auto Opt = SplitAndProve(ProofFn))
+        return Opt;
     }
-    return false;
+    return None;
   };
 
   // Starting at the block's predecessor, climb up the predecessor chain, as long
   // as there are predecessors that can be found that have unique successors
   // leading to the original block.
   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;
+    if (auto Opt = ProveViaGuard(Pair.first))
+      return Opt;
 
     const BranchInst *LoopEntryPredicate =
         dyn_cast<BranchInst>(Pair.first->getTerminator());
     if (!LoopEntryPredicate ||
         LoopEntryPredicate->isUnconditional())
       continue;
 
-    if (ProveViaCond(LoopEntryPredicate->getCondition(),
-                     LoopEntryPredicate->getSuccessor(0) != Pair.second))
-      return true;
+    bool Inverse = LoopEntryPredicate->getSuccessor(0) != Pair.second;
+    if (auto Opt = ProveViaCond(LoopEntryPredicate->getCondition(), Inverse))
+      return Opt;
   }
 
   // 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;
+    if (auto Opt = ProveViaCond(CI->getArgOperand(0), false))
+      return Opt;
   }
 
-  return false;
+  return None;
 }
 
 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
   // (interprocedural conditions notwithstanding).
   if (!L)
     return false;
 
   // Both LHS and RHS must be available at loop entry.
   assert(isAvailableAtLoopEntry(LHS, L) &&
          "LHS is not available at Loop Entry");
   assert(isAvailableAtLoopEntry(RHS, L) &&
          "RHS is not available at Loop Entry");
 
   if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
     return true;
 
-  return isBasicBlockEntryGuardedByCond(L->getHeader(), Pred, LHS, RHS);
+  auto ResOpt = isBasicBlockEntryGuardedByCond(L->getHeader(), Pred, LHS, RHS);
+  return ResOpt && *ResOpt;
 }
 
 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
                                     const SCEV *RHS,
                                     const Value *FoundCondValue, bool Inverse,
                                     const Instruction *Context) {
   // False conditions implies anything. Do not bother analyzing it further.
   if (FoundCondValue ==

llvm/test/Transforms/IndVarSimplify/2011-10-27-lftrnull.ll

 ; CHECK-NEXT:    br label [[FOR_BODY_I86:%.*]]
 ; CHECK:       for.body.i86:
 ; CHECK-NEXT:    [[CMP196_I:%.*]] = icmp ult i32 0, undef
 ; CHECK-NEXT:    br i1 [[CMP196_I]], label [[FOR_BODY21_LR_PH_I:%.*]], label [[FOR_END_I129:%.*]]
 ; CHECK:       for.body21.lr.ph.i:
 ; CHECK-NEXT:    br label [[FOR_BODY21_I:%.*]]
 ; CHECK:       for.body21.i:
 ; CHECK-NEXT:    [[DESTYPIXELPTR_010_I:%.*]] = phi i8* [ null, [[FOR_BODY21_LR_PH_I]] ], [ [[INCDEC_PTR_I:%.*]], [[IF_END_I126:%.*]] ]
+; CHECK-NEXT:    [[X_09_I:%.*]] = phi i32 [ 0, [[FOR_BODY21_LR_PH_I]] ], [ [[INC_I125:%.*]], [[IF_END_I126]] ]
 ; CHECK-NEXT:    br i1 undef, label [[IF_END_I126]], label [[IF_ELSE_I124:%.*]]
 ; CHECK:       if.else.i124:
 ; CHECK-NEXT:    store i8 undef, i8* [[DESTYPIXELPTR_010_I]], align 1
 ; CHECK-NEXT:    br label [[IF_END_I126]]
 ; CHECK:       if.end.i126:
 ; CHECK-NEXT:    [[INCDEC_PTR_I]] = getelementptr inbounds i8, i8* [[DESTYPIXELPTR_010_I]], i32 1
-; CHECK-NEXT:    br i1 true, label [[FOR_BODY21_I]], label [[FOR_END_I129_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[INC_I125]] = add nuw i32 [[X_09_I]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[INC_I125]], undef
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY21_I]], label [[FOR_END_I129_LOOPEXIT:%.*]]
 ; CHECK:       for.end.i129.loopexit:
 ; CHECK-NEXT:    br label [[FOR_END_I129]]
 ; CHECK:       for.end.i129:
 ; CHECK-NEXT:    br i1 false, label [[FOR_BODY_I86]], label [[WHILE_COND_LOOPEXIT:%.*]]
 ; CHECK:       while.end:
 ; CHECK-NEXT:    br label [[BAIL:%.*]]
 ; CHECK:       bail:
 ; CHECK-NEXT:    unreachable

llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll

 ; CHECK:       general_case24:
 ; CHECK-NEXT:    br i1 false, label [[LOOP2_PREHEADER:%.*]], label [[LOOP2_EXIT]]
 ; CHECK:       loop2.preheader:
 ; CHECK-NEXT:    [[TMP0:%.*]] = udiv i64 14, [[INDVARS_IV]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = udiv i64 60392, [[TMP0]]
 ; CHECK-NEXT:    br label [[LOOP2:%.*]]
 ; CHECK:       loop2:
 ; CHECK-NEXT:    [[INDVARS_IV1:%.*]] = phi i64 [ [[TMP1]], [[LOOP2_PREHEADER]] ], [ [[INDVARS_IV_NEXT2:%.*]], [[LOOP2]] ]
-; CHECK-NEXT:    [[INDVARS_IV_NEXT2]] = add nuw nsw i64 [[INDVARS_IV1]], -1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT2]] = add nsw i64 [[INDVARS_IV1]], -1
 ; CHECK-NEXT:    [[I4:%.*]] = load atomic i64, i64* [[P1:%.*]] unordered, align 8
 ; CHECK-NEXT:    [[I6:%.*]] = sub i64 [[I4]], [[INDVARS_IV_NEXT2]]
 ; CHECK-NEXT:    store atomic i64 [[I6]], i64* [[P1]] unordered, align 8
 ; CHECK-NEXT:    br i1 true, label [[LOOP2_EXIT_LOOPEXIT:%.*]], label [[LOOP2]]
 ; CHECK:       loop2.exit.loopexit:
 ; CHECK-NEXT:    br label [[LOOP2_EXIT]]
 ; CHECK:       loop2.exit:
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1

llvm/test/Transforms/IndVarSimplify/eliminate-comparison.ll

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4
 ; CHECK-NEXT:    [[LEN_ADD_5:%.*]] = add i32 [[LEN]], -5
 ; CHECK-NEXT:    [[ENTRY_COND_0:%.*]] = icmp slt i32 [[LEN]], -2147483643
 ; CHECK-NEXT:    [[ENTRY_COND_1:%.*]] = icmp slt i32 -6, [[LEN_ADD_5]]
 ; CHECK-NEXT:    [[ENTRY_COND:%.*]] = and i1 [[ENTRY_COND_0]], [[ENTRY_COND_1]]
 ; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
 ; CHECK:       loop.preheader:
-; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LEN]], i32 0)
-; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[SMAX]], -5
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ -6, [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    call void @side_effect()
-; CHECK-NEXT:    [[IV_INC]] = add nsw i32 [[IV]], 1
-; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BE:%.*]], label [[LEAVE_LOOPEXIT:%.*]]
 ; CHECK:       be:
 ; CHECK-NEXT:    call void @side_effect()
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[TMP0]]
-; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
+; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[LEAVE_LOOPEXIT]]
 ; CHECK:       leave.loopexit:
 ; CHECK-NEXT:    br label [[LEAVE]]
 ; CHECK:       leave:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %len = load i32, i32* %len.ptr
   %len.add.5 = add i32 %len, -5