[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

10552–10554

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

10552–10554

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

10124

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

10135

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 ↗

(On Diff #303489)

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

1411 ↗

(On Diff #303489)

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

10135

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 ↗

(On Diff #303489)

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 ↗

(On Diff #303489)

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 ↗

(On Diff #303489)

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))
       return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS, Context);
     else
       return isImpliedCondOperands(ICmpInst::getSwappedPredicate(Pred), RHS,
                                    LHS, FoundLHS, 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);
 
   // Check if we can make progress by sharpening ranges.
   if (FoundPred == ICmpInst::ICMP_NE &&
       (isa<SCEVConstant>(FoundLHS) || isa<SCEVConstant>(FoundRHS))) {
 
     const SCEVConstant *C = nullptr;
     const SCEV *V = nullptr;
 
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
 }