[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

already computed => already-computed

7010

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

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

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

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

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;
 
   WalkingBEDominatingConds = true;
   ClearWalkingBEDominatingCondsOnExit ClearOnExit(*this);
 
+  // See if we can exploit an already computed trip count to prove the
+  // predicate.
+  auto BECountIt = BackedgeTakenCounts.find(L);
+  if (BECountIt != BackedgeTakenCounts.end()) {
+    const SCEV *LatchBECount = BECountIt->second.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();
+      const SCEV *LoopCounter =
+          getAddRecExpr(getZero(Ty), getOne(Ty), L, SCEV::FlagAnyWrap);
+      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;
 

test/Transforms/IndVarSimplify/eliminate-comparison.ll

be:
   call void @side_effect()
   %be.cond = icmp ult i32 %iv, %len
   br i1 %be.cond, label %loop, label %leave
 
  leave:
   ret void
 }
 
-!0 = !{i32 0, i32 2147483647}
+define i1 @func_16(i16* %tmp20, i32* %len.addr) {
+; CHECK-LABEL: @func_16(
+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}