[SCEV] Don't use not expressions for implied conditions

[nikic]

Summary

SCEV currently tries to prove implications of x pred y by also trying to imply ~y pred ~x. This is expensive in terms of compile-time (in fact, the vast majority of isImpliedCond compile-time is spent here) and generally not fruitful. The issue is that this also swaps the operands and thus breaks canonical ordering. If originally we were trying to prove an implication like X > C1 => Y > C2, then we'll now try to prove X > C1 => C3 > ~Y, which will not work.

The only real case where we can get some use out of this transform is if the original conditions were in the form X > C1 => Y < C2, were then swapped to X > C1 => C2 > Y and are then swapped again here to X > C1 => ~Y > C3.

As such, handle this at a higher level, where we are doing the swapping in the first place. There's four different ways that we can line up a predicate and a swapped predicate, so we use some heuristics to pick some profitable way.

Because we now try this transform at a higher level (isImpliedCondOperands rather than isImpliedCondOperandsHelper), we can also prove additional facts. Of the added tests, one was proven previously while the other wasn't.

Compile-time: https://llvm-compile-time-tracker.com/compare.php?from=40bc309911f0f92ff8b8f64d28cb13a2292695ff&to=0c2feb97b5d529f816a54418bd008fcbbf53d98a&stat=instructions

[nikic]

llvm/test/Analysis/ScalarEvolution/zext-wrap.ll

18

This is a SCEV nowrap caching artifact -- the cached nowrap flags depend on which expressions get constructed. There's no actual change in which implied conditions here. I've put up D90338 as an experiment to improve handling of addrec nowrap flags.

[lebedev.ri]

llvm/lib/Analysis/ScalarEvolution.cpp

10773–10775

What happens if the predicate is swapped instead of operands?

[nikic]

Preserve transform at a higher level, where we are lining up swapped predicates.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

10773–10775

It's not possible to swap the predicate at this point, because this code already works on a single matching predicate only.

However, I think your general idea here is right. I've updated the patch to preserve this transform, but at a higher level: When we try to line up a predicate and a swapped predicate, using this approach allows us to do a "double swap" and thus avoid changing operand order. That allows us to preserve canonical operand ordering, and thus prove useful facts.

Because this is done at a higher level, we'll also try to apply more types of reasoning to the not-ed version.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

10345

nit: please replace <= with <- to make it crystal clear that it's implication and not le :)

10356

I wonder, is AddRec the only case where we expect constant to be on right hand side? I'm pretty sure we want it for most arithmetics we process. Do we regress if SCEVAddRecExpr is removed? This should give even better compile time effect.

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

1405

Nit: this thing should have <nsw>, and the fact being proved is actually not true without this flag.

1411

I think it can be strengthened to {0,+,1}<nuw><nsw> > 1, no?

[nikic]

Use different arrow for implication.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

10356

We canonicalize addrec to left and constant to right, so this only does the swap if *neither* is present.

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

1405

The <nw> here is based on the flags present in dump(). I think it doesn't actually matter because the implication we're effectively proving is that {0,+,1}<nuw><nsw> > 0 implies {-1,+,1} > -1. And for this part, just the nowrap flag on the left addrec are sufficient, the ones on the rhs are implied.

1411

We should be able to prove that, but don't. After negation, we'll try both {0,+,-1}<nw> < -1 -> {-1,+,-1}<nw> < -2 and {-1,+,1}<nsw> > 0 -> {0,+,1}<nuw><nsw> > 1, but can't prove either.

[mkazantsev]

LGTM, thanks!

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

1411

Wow, that expands the horizons of SCEV's ignorance :)

llvm/lib/Analysis/ScalarEvolution.cpp

bool ScalarEvolution::isImpliedCondBalancedTypes(
 
   // Check whether the found predicate is the same as the desired predicate.
   if (FoundPred == Pred)
     return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, Context);
 
   // Check whether swapping the found predicate makes it the same as the
   // desired predicate.
   if (ICmpInst::getSwappedPredicate(FoundPred) == Pred) {
-    if (isa<SCEVConstant>(RHS))
+    // We can write the implication
+    // 0.  LHS Pred      RHS  <-   FoundLHS SwapPred  FoundRHS
+    // using one of the following ways:
+    // 1.  LHS Pred      RHS  <-   FoundRHS Pred      FoundLHS
+    // 2.  RHS SwapPred  LHS  <-   FoundLHS SwapPred  FoundRHS
+    // 3.  LHS Pred      RHS  <-  ~FoundLHS Pred     ~FoundRHS
+    // 4. ~LHS SwapPred ~RHS  <-   FoundLHS SwapPred  FoundRHS
+    // Forms 1. and 2. require swapping the operands of one condition. Don't
+    // do this if it would break canonical constant/addrec ordering.
+    if (!isa<SCEVConstant>(RHS) && !isa<SCEVAddRecExpr>(LHS))
+      return isImpliedCondOperands(FoundPred, RHS, LHS, FoundLHS, FoundRHS,
+                                   Context);
+    if (!isa<SCEVConstant>(FoundRHS) && !isa<SCEVAddRecExpr>(FoundLHS))
       return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS, Context);
-    else
-      return isImpliedCondOperands(ICmpInst::getSwappedPredicate(Pred), RHS,
-                                   LHS, FoundLHS, FoundRHS, Context);
+
+    // There's no clear preference between forms 3. and 4., try both.
+    return isImpliedCondOperands(FoundPred, getNotSCEV(LHS), getNotSCEV(RHS),
+                                 FoundLHS, FoundRHS, Context) ||
+           isImpliedCondOperands(Pred, LHS, RHS, getNotSCEV(FoundLHS),
+                                 getNotSCEV(FoundRHS), Context);
   }
 
   // Unsigned comparison is the same as signed comparison when both the operands
   // are non-negative.
   if (CmpInst::isUnsigned(FoundPred) &&
       CmpInst::getSignedPredicate(FoundPred) == Pred &&
       isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS))
     return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, Context);
bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,
   if (isImpliedCondOperandsViaNoOverflow(Pred, LHS, RHS, FoundLHS, FoundRHS))
     return true;
 
   if (isImpliedCondOperandsViaAddRecStart(Pred, LHS, RHS, FoundLHS, FoundRHS,
                                           Context))
     return true;
 
   return isImpliedCondOperandsHelper(Pred, LHS, RHS,
-                                     FoundLHS, FoundRHS) ||
-         // ~x < ~y --> x > y
-         isImpliedCondOperandsHelper(Pred, LHS, RHS,
-                                     getNotSCEV(FoundRHS),
-                                     getNotSCEV(FoundLHS));
+                                     FoundLHS, FoundRHS);
 }
 
 /// Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
 template <typename MinMaxExprType>
 static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr,
                                  const SCEV *Candidate) {
   const MinMaxExprType *MinMaxExpr = dyn_cast<MinMaxExprType>(MaybeMinMaxExpr);
   if (!MinMaxExpr)

llvm/test/Analysis/ScalarEvolution/zext-wrap.ll

 ; We should be able to find the range for this expression.
 ; CHECK: %l_95.0.i1 = phi i8
 ; CHECK: -->  {0,+,-1}<%bb.i> U: [2,1) S: [2,1){{ *}}Exits: 2
 
         %l_95.0.i1 = phi i8 [ %tmp1, %bb.i ], [ 0, %entry ]
 
 ; This cast shouldn't be folded into the addrec.
 ; CHECK: %tmp = zext i8 %l_95.0.i1 to i16
-; CHECK: -->  (zext i8 {0,+,-1}<nw><%bb.i> to i16){{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: 2
+; CHECK: -->  (zext i8 {0,+,-1}<%bb.i> to i16){{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: 2
 
         %tmp = zext i8 %l_95.0.i1 to i16
 
         %tmp1 = add i8 %l_95.0.i1, -1
         %phitmp = icmp eq i8 %tmp1, 1
         br i1 %phitmp, label %bb1.i.func_36.exit_crit_edge, label %bb.i
 
 bb1.i.func_36.exit_crit_edge:
         ret i16 %tmp
 }

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

static Optional<APInt> computeConstantDifference(ScalarEvolution &SE,
                                                    const SCEV *RHS) {
     return SE.computeConstantDifference(LHS, RHS);
   }
 
   static bool matchURem(ScalarEvolution &SE, const SCEV *Expr, const SCEV *&LHS,
                         const SCEV *&RHS) {
     return SE.matchURem(Expr, LHS, RHS);
   }
+
+  static bool isImpliedCond(
+      ScalarEvolution &SE, ICmpInst::Predicate Pred, const SCEV *LHS,
+      const SCEV *RHS, ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
+      const SCEV *FoundRHS) {
+    return SE.isImpliedCond(Pred, LHS, RHS, FoundPred, FoundLHS, FoundRHS);
+  }
 };
 
 TEST_F(ScalarEvolutionsTest, SCEVUnknownRAUW) {
   FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context),
                                               std::vector<Type *>(), false);
   Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);
   BasicBlock *BB = BasicBlock::Create(Context, "entry", F);
   ReturnInst::Create(Context, nullptr, BB);
runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
     // scalar-evolution-use-expensive-range-sharpening which is currently off.
     // Enable the check once it's switched true by default.
     // EXPECT_TRUE(SE.isBasicBlockEntryGuardedByCond(Backedge,
     //                                               ICmpInst::ICMP_UGT,
     //                                               IV, Zero));
   });
 }
 
+TEST_F(ScalarEvolutionsTest, ImpliedCond) {
+  LLVMContext C;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M = parseAssemblyString(
+      "define void @foo(i32 %len) { "
+      "entry: "
+      "  br label %loop "
+      "loop: "
+      "  %iv = phi i32 [ 0, %entry], [%iv.next, %loop] "
+      "  %iv.next = add nsw i32 %iv, 1 "
+      "  %cmp = icmp slt i32 %iv, %len "
+      "  br i1 %cmp, label %loop, label %exit "
+      "exit:"
+      "  ret void "
+      "}",
+      Err, C);
+
+  ASSERT_TRUE(M && "Could not parse module?");
+  ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
+
+  runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+    Instruction *IV = getInstructionByName(F, "iv");
+    Type *Ty = IV->getType();
+    const SCEV *Zero = SE.getZero(Ty);
+    const SCEV *MinusOne = SE.getMinusOne(Ty);
+    // {0,+,1}<nuw><nsw>
+    const SCEV *AddRec_0_1 = SE.getSCEV(IV);
+    // {0,+,-1}<nw>
+    const SCEV *AddRec_0_N1 = SE.getNegativeSCEV(AddRec_0_1);
+
+    // {0,+,1}<nuw><nsw> > 0  ->  {0,+,-1}<nw> < 0
+    EXPECT_TRUE(isImpliedCond(SE, ICmpInst::ICMP_SLT, AddRec_0_N1, Zero,
+                                  ICmpInst::ICMP_SGT, AddRec_0_1, Zero));
+    // {0,+,-1}<nw> < -1  ->  {0,+,1}<nuw><nsw> > 0
+    EXPECT_TRUE(isImpliedCond(SE, ICmpInst::ICMP_SGT, AddRec_0_1, Zero,
+                                  ICmpInst::ICMP_SLT, AddRec_0_N1, MinusOne));
+  });
+}
+
 TEST_F(ScalarEvolutionsTest, MatchURem) {
   LLVMContext C;
   SMDiagnostic Err;
   std::unique_ptr<Module> M = parseAssemblyString(
       "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
       " "
       "define void @test(i32 %a, i32 %b, i16 %c, i64 %d) {"
       "entry: "