[SCEV] Prove implications of different type via truncation

[mkazantsev]

Summary

When we need to prove implication of expressions of different type width,
the default strategy is to widen everything to wider type and prove in this
type. This does not interact well with AddRecs with negative steps and
unsigned predicates: such AddRec will likely not have a nuw flag, and its
zext to wider type will not be an AddRec. In contraty, trunc of an AddRec
in some cases can easily be proved to be an AddRec too.

This patch introduces an alternative way to handling implications of different
type widths. If we can prove that wider type values actually fit in the narrow type,
we truncate them and prove the implication in narrow type.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/srem.ll

32

Bug in underpying patch.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/srem.ll

32

It happens just because we create zero extend SCEV (and not proving further ule). A subject for a follow-up fix.

[fhahn]

LGTM, thanks! As mentioned inline, I think it would be good to have a fix for the issue pointed out ready before the change goes in.

llvm/test/Analysis/ScalarEvolution/srem.ll

32

It would probably be good to have a fix lined up before this goes in

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/srem.ll

32

Agreed, I'm looking into it. Thanks!

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/srem.ll

32

Root cause here: by the moment when we query this, nuw flag is not set and one of rules in range computation does not apply. General problem: we don't drop constant ranges when we update flags when we should.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/srem.ll

32

Fix: https://reviews.llvm.org/D89847

The problem is old, general and exists regardless of this patch. So I don't think it should be holding it away.

[mkazantsev]

The underlying patch D89381 was reverted again, and nothing will work without it. Reopenning until this has beeen resolved.

[uabelho]

Hi @mkazantsev ,

The following hang started occuring with this patch:
https://bugs.llvm.org/show_bug.cgi?id=51869

I've also seen hangs in loop-idiom-recognizer with the patch so I suppose many passes using SCEV might run into the same kind of problems.

[bjope]

In D89548#3009262, @uabelho wrote:

Hi @mkazantsev ,

The following hang started occuring with this patch:
https://bugs.llvm.org/show_bug.cgi?id=51869

I've also seen hangs in loop-idiom-recognizer with the patch so I suppose many passes using SCEV might run into the same kind of problems.

I haven't tried to revert this patch, but maybe that should be explored (as it seems broken in the sense that it might cause infinite looping / severe compile time regressions)?

[bjope]

In D89548#3026933, @bjope wrote:

In D89548#3009262, @uabelho wrote:

Hi @mkazantsev ,

The following hang started occuring with this patch:
https://bugs.llvm.org/show_bug.cgi?id=51869

I've also seen hangs in loop-idiom-recognizer with the patch so I suppose many passes using SCEV might run into the same kind of problems.

I haven't tried to revert this patch, but maybe that should be explored (as it seems broken in the sense that it might cause infinite looping / severe compile time regressions)?

Not a pure revert, but here is a patch to disable this feature by default: https://reviews.llvm.org/D111066

llvm/lib/Analysis/ScalarEvolution.cpp

 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
                                     const SCEV *RHS,
                                     ICmpInst::Predicate FoundPred,
                                     const SCEV *FoundLHS, const SCEV *FoundRHS,
                                     const Instruction *Context) {
   // Balance the types.
   if (getTypeSizeInBits(LHS->getType()) <
       getTypeSizeInBits(FoundLHS->getType())) {
+    // For unsigned and equality predicates, try to prove that both found
+    // operands fit into narrow unsigned range. If so, try to prove facts in
+    // narrow types.
+    if (!CmpInst::isSigned(FoundPred)) {
+      auto *NarrowType = LHS->getType();
+      auto *WideType = FoundLHS->getType();
+      auto BitWidth = getTypeSizeInBits(NarrowType);
+      const SCEV *MaxValue = getZeroExtendExpr(
+          getConstant(APInt::getMaxValue(BitWidth)), WideType);
+      if (isKnownPredicate(ICmpInst::ICMP_ULE, FoundLHS, MaxValue) &&
+          isKnownPredicate(ICmpInst::ICMP_ULE, FoundRHS, MaxValue)) {
+        const SCEV *TruncFoundLHS = getTruncateExpr(FoundLHS, NarrowType);
+        const SCEV *TruncFoundRHS = getTruncateExpr(FoundRHS, NarrowType);
+        if (isImpliedCondBalancedTypes(Pred, LHS, RHS, FoundPred, TruncFoundLHS,
+                                       TruncFoundRHS, Context))
+          return true;
+      }
+    }
+
     if (CmpInst::isSigned(Pred)) {
       LHS = getSignExtendExpr(LHS, FoundLHS->getType());
       RHS = getSignExtendExpr(RHS, FoundLHS->getType());
     } else {
       LHS = getZeroExtendExpr(LHS, FoundLHS->getType());
       RHS = getZeroExtendExpr(RHS, FoundLHS->getType());
     }
   } else if (getTypeSizeInBits(LHS->getType()) >

llvm/test/Analysis/ScalarEvolution/srem.ll

 ; CHECK-NEXT:    --> %1 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
 ; CHECK-NEXT:    %call = call i32 @_Z3adji(i32 %1)
 ; CHECK-NEXT:    --> %call U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
 ; CHECK-NEXT:    %2 = load i32, i32* %arrayidx, align 4
 ; CHECK-NEXT:    --> %2 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
 ; CHECK-NEXT:    %add = add nsw i32 %2, %call
 ; CHECK-NEXT:    --> (%2 + %call) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
 ; CHECK-NEXT:    %inc = add nsw i32 %i.0, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><%for.cond> U: [1,0) S: [1,0) Exits: (1 + %width) LoopDispositions: { %for.cond: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><%for.cond> U: full-set S: full-set Exits: (1 + %width) LoopDispositions: { %for.cond: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @_Z4loopi
 ; CHECK-NEXT:  Loop %for.cond: backedge-taken count is %width
 ; CHECK-NEXT:  Loop %for.cond: max backedge-taken count is -1
 ; CHECK-NEXT:  Loop %for.cond: Predicated backedge-taken count is %width
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %for.cond: Trip multiple is 1
 ;
 entry:

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
     ASSERT_TRUE(Guarded);
     EXPECT_TRUE(
         SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_ULT, Y, X));
     EXPECT_TRUE(
         SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_UGT, X, Y));
   });
 }
 
+TEST_F(ScalarEvolutionsTest, ProveImplicationViaNarrowing) {
+  LLVMContext C;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M = parseAssemblyString(
+      "define i32 @foo(i32 %start, i32* %q) { "
+      "entry: "
+      "  %wide.start = zext i32 %start to i64 "
+      "  br label %loop "
+      "loop: "
+      "  %wide.iv = phi i64 [%wide.start, %entry], [%wide.iv.next, %backedge] "
+      "  %iv = phi i32 [%start, %entry], [%iv.next, %backedge] "
+      "  %cond = icmp eq i64 %wide.iv, 0 "
+      "  br i1 %cond, label %exit, label %backedge "
+      "backedge: "
+      "  %iv.next = add i32 %iv, -1 "
+      "  %index = zext i32 %iv.next to i64 "
+      "  %load.addr = getelementptr i32, i32* %q, i64 %index "
+      "  %stop = load i32, i32* %load.addr "
+      "  %loop.cond = icmp eq i32 %stop, 0 "
+      "  %wide.iv.next = add nsw i64 %wide.iv, -1 "
+      "  br i1 %loop.cond, label %loop, label %failure "
+      "exit: "
+      "  ret i32 0 "
+      "failure: "
+      "  unreachable "
+      "} ",
+      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) {
+    auto *IV = SE.getSCEV(getInstructionByName(F, "iv"));
+    auto *Zero = SE.getZero(IV->getType());
+    auto *Backedge = getInstructionByName(F, "iv.next")->getParent();
+    ASSERT_TRUE(Backedge);
+    (void)IV;
+    (void)Zero;
+    // FIXME: This can only be proved with turned on option
+    // 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));
+  });
+}
+
 }  // end namespace llvm