[SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts.

[sanjoy]

Summary

If the trip count of a specific backedge is N, then we know that
backedge is effectively guarded by the condition {0,+,1} u< N. This
change teaches SCEV to use this condition to prove things in
isLoopBackedgeGuardedByCond.

Depends on D12948
Depends on D12949

[sanjoy]

• rebase on top of changes to D12948

[hfinkel]

lib/Analysis/ScalarEvolution.cpp

7008 ↗

(On Diff #35133)

already computed => already-computed

7010 ↗

(On Diff #35133)

It seems like we should add a comment in ScalarEvolution.h somewhere that isLoopBackedgeGuardedByCond will potentially-return more-accurate answers if you compute the look trip count first.

This seems unfortunate, but I suppose we can't force the trip-count computation here because we might infinitely recurse?

7019 ↗

(On Diff #35133)

Don't we know that SCEV::FlagNW | SCEV::FlagNUW here? Otherwise, it would not really be a trip count, would it?

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

7010 ↗

(On Diff #35133)

This seems unfortunate, but I suppose we can't force the trip-count
computation here because we might infinitely recurse?

My motivation was to avoid burning excessive compile time computing
loop trip counts we'll never use. But on second thought, this sounds
like a silly optimization -- even calling getSCEV will sometimes end
up causing the loop's trip count to be computed, so micro-optimizing
it away here does not make sense. I'll change this to a direct call
to getBackedgeTakenInfo.

Btw, I don't think we'll end up with infinite recursion here. If
getBackedgeTakenInfo ends up recursively calling this code, the
recursive call to getBackedgeTakenInfo should return "could not
compute" as the backedge trip for Latch, so we won't make the second
recursive call to isImpliedCond.

7019 ↗

(On Diff #35133)

Yes, will fix.

[sanjoy]

• address hal's review. Making the loop counter <nw> and <nuw> changed the output of an existing test case (zext-wrap.ll) -- an induction variable is now reported as <nw> when it wasn't before. This inference is correct, so I didn't actually bother trying to verify further.

[hfinkel]

LGTM.

[yaron.keren]

Please see http://llvm.org/pr24952

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L,
 
   // We don't want more than one activation of the following loops on the stack
   // -- that can lead to O(n!) time complexity.
   if (WalkingBEDominatingConds)
     return false;
 
   SaveAndRestore<bool> ClearOnExit(WalkingBEDominatingConds, true);
 
+  // See if we can exploit a trip count to prove the predicate.
+  const auto &BETakenInfo = getBackedgeTakenInfo(L);
+  const SCEV *LatchBECount = BETakenInfo.getExact(Latch, this);
+  if (LatchBECount != getCouldNotCompute()) {
+    // We know that Latch branches back to the loop header exactly
+    // LatchBECount times.  This means the backdege condition at Latch is
+    // equivalent to  "{0,+,1} u< LatchBECount".
+    Type *Ty = LatchBECount->getType();
+    auto NoWrapFlags = SCEV::NoWrapFlags(SCEV::FlagNUW | SCEV::FlagNW);
+    const SCEV *LoopCounter =
+      getAddRecExpr(getZero(Ty), getOne(Ty), L, NoWrapFlags);
+    if (isImpliedCond(Pred, LHS, RHS, ICmpInst::ICMP_ULT, LoopCounter,
+                      LatchBECount))
+      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, Latch->getTerminator()))
       continue;
 

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

 ; RUN: opt < %s -analyze -scalar-evolution | FileCheck %s
 ; PR4569
 
 define i16 @main() nounwind {
 entry:
         br label %bb.i
 
 bb.i:           ; preds = %bb1.i, %bb.nph
         %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}<%bb.i> to i16){{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: 2
+; CHECK: -->  (zext i8 {0,+,-1}<nw><%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/trunk/test/Transforms/IndVarSimplify/eliminate-comparison.ll

; CHECK: be:
   call void @side_effect()
   %be.cond = icmp slt i32 %iv.2, %len
   br i1 %be.cond, label %loop, label %leave
 
  leave:
   ret void
 }
 
-!0 = !{i32 0, i32 2147483647}
+define i1 @func_18(i16* %tmp20, i32* %len.addr) {
+; CHECK-LABEL: @func_18(
+entry:
+  %len = load i32, i32* %len.addr, !range !0
+  %tmp18 = icmp eq i32 %len, 0
+  br i1 %tmp18, label %bb2, label %bb0.preheader
+
+bb0.preheader:
+  br label %bb0
+
+bb0:
+; CHECK: bb0:
+  %var_0.in = phi i32 [ %var_0, %bb1 ], [ %len, %bb0.preheader ]
+  %var_1 = phi i32 [ %tmp30, %bb1 ], [ 0, %bb0.preheader ]
+  %var_0 = add nsw i32 %var_0.in, -1
+  %tmp23 = icmp ult i32 %var_1, %len
+; CHECK: br i1 true, label %stay, label %bb2.loopexit
+  br i1 %tmp23, label %stay, label %bb2
+
+stay:
+; CHECK: stay:
+  %tmp25 = getelementptr inbounds i16, i16* %tmp20, i32 %var_1
+  %tmp26 = load i16, i16* %tmp25
+  %tmp29 = icmp eq i16 %tmp26, 0
+  br i1 %tmp29, label %bb1, label %bb2
+
+bb1:
+  %tmp30 = add i32 %var_1, 1
+  %tmp31 = icmp eq i32 %var_0, 0
+  br i1 %tmp31, label %bb3, label %bb0
+
+bb2:
+  ret i1 false
 
+bb3:
+  ret i1 true
+}
+
+!0 = !{i32 0, i32 2147483647}