PR32632 Add a case to remove loop compare

[evstupac]

Summary

The patch add a case to eliminate comparisons like:

for (i = 84; i > 1; i--)
 for (j = i; j < i; j++)

which exit at first loop iteration.

Build and lit tests are passed.
No significant performance changes.
spec2000 - build same all
spec2006 - build same all, but 400 and 433 (with less than 1% gain).

[efriedma]

Scalar evolution can already analyze the given testcase on trunk. Output of "opt -analyze -scalar-evolution":

Determining loop execution counts for: @foo
Loop %for.cond4: backedge-taken count is 6
Loop %for.cond4: max backedge-taken count is 6
Loop %for.cond4: Predicated backedge-taken count is 6
 Predicates:

Loop %for.cond4: Trip multiple is 7
Loop %for.cond1: backedge-taken count is 0
Loop %for.cond1: max backedge-taken count is 0
Loop %for.cond1: Predicated backedge-taken count is 0
 Predicates:

Loop %for.cond1: Trip multiple is 1
Loop %for.cond: backedge-taken count is 83
Loop %for.cond: max backedge-taken count is 83
Loop %for.cond: Predicated backedge-taken count is 83
 Predicates:

Loop %for.cond: Trip multiple is 84

[evstupac]

In D34117#778323, @efriedma wrote:

Scalar evolution can already analyze the given testcase on trunk. Output of "opt -analyze -scalar-evolution":

Right. The reason I'm trying to apply this patch is that the case could be resolved earlier.
It is possible to understand that the predicate is constant here. Why not to do this at "isKnownPredicate"?
There are other cases, that could be caught by BECount - should we remove them from "isKnownPredicate"?

[efriedma]

I'm not convinced it makes sense to invest any effort into loops with a backedge-taken count of zero. Yes, maybe we simplify the exit condition slightly earlier, but does that actually do us any good in practice?

There are other cases, that could be caught by BECount - should we remove them from "isKnownPredicate"?

I don't think there's any other code in isKnownPredicate that specifically checks for exit conditions? Not all comparisons against an AddRec are checks which exit the loop.

include/llvm/Analysis/ScalarEvolution.h

public:
   /// Test if the given expression is known to be non-positive.
   ///
   bool isKnownNonPositive(const SCEV *S);
 
   /// Test if the given expression is known to be non-zero.
   ///
   bool isKnownNonZero(const SCEV *S);
 
+  /// Test if first iteration of a loop exits it.
+  bool isLoopFirstIterationExit(const Loop *L, bool ExitOperand,
+                                ICmpInst::Predicate Pred,
+                                const SCEV *LHS, const SCEV *RHS);
+
   /// Test if the given expression is known to satisfy the condition described
   /// by Pred, LHS, and RHS.
   ///
   bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
                         const SCEV *RHS);
 
   /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X"
   /// is monotonically increasing or decreasing.  In the former case set

lib/Analysis/ScalarEvolution.cpp

if (const SCEVUnknown *BU = dyn_cast<SCEVUnknown>(B))
         if (const Instruction *BI = dyn_cast<Instruction>(BU->getValue()))
           if (ComputesEqualValues(AI, BI))
             return true;
 
   // Otherwise assume they may have a different value.
   return false;
 }
 
+/// True if we exit on the first loop iteration
+bool
+ScalarEvolution::isLoopFirstIterationExit(const Loop *L, bool ExitOperand,
+                                          ICmpInst::Predicate Pred,
+                                          const SCEV *LHS, const SCEV *RHS) {
+  if (!L)
+    return false;
+  BasicBlock *Header = L->getHeader();
+  const BranchInst *BI = dyn_cast<BranchInst>(Header->getTerminator());
+  if (!BI || BI->isUnconditional())
+    return false;
+  CmpInst *CmpI = dyn_cast<CmpInst>(BI->getCondition());
+  if (!CmpI || CmpI->getPredicate() != Pred)
+    return false;
+  if (!HasSameValue(LHS, getSCEV(CmpI->getOperand(0))) ||
+      !HasSameValue(RHS, getSCEV(CmpI->getOperand(1))))
+    return false;
+  if (ICmpInst::isTrueWhenEqual(Pred) && ExitOperand &&
+      !L->contains(BI->getSuccessor(0)) && L->contains(BI->getSuccessor(1)))
+    return true;
+  if (ICmpInst::isFalseWhenEqual(Pred) && !ExitOperand &&
+      L->contains(BI->getSuccessor(0)) && !L->contains(BI->getSuccessor(1)))
+    return true;
+  return false;
+}
+
 bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred,
                                            const SCEV *&LHS, const SCEV *&RHS,
                                            unsigned Depth) {
   bool Changed = false;
 
   // If we hit the max recursion limit bail out.
   if (Depth >= 3)
     return false;
 
+  if (const SCEVAddRecExpr *LAR = dyn_cast<SCEVAddRecExpr>(LHS)) {
+    const Loop *L = LAR->getLoop();
+    if (isLoopInvariant(RHS, L) && HasSameValue(LAR->getStart(), RHS)) {
+      if (isLoopFirstIterationExit(L, true, Pred, LHS, RHS))
+        goto trivially_true;
+      else if (isLoopFirstIterationExit(L, false, Pred, LHS, RHS))
+        goto trivially_false;
+    }
+  }
+  if (const SCEVAddRecExpr *RAR = dyn_cast<SCEVAddRecExpr>(RHS)) {
+    const Loop *L = RAR->getLoop();
+    if (isLoopInvariant(LHS, L) && HasSameValue(RAR->getStart(), LHS)) {
+      if (isLoopFirstIterationExit(L, true, Pred, LHS, RHS))
+        goto trivially_true;
+      else if (isLoopFirstIterationExit(L, false, Pred, LHS, RHS))
+        goto trivially_false;
+    }
+  }
   // Canonicalize a constant to the right side.
   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
     // Check for both operands constant.
     if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
       if (ConstantExpr::getICmp(Pred,
                                 LHSC->getValue(),
                                 RHSC->getValue())->isNullValue())
         goto trivially_false;

test/Transforms/IndVarSimplify/first_iter_exit.ll

+; RUN: opt < %s -S -indvars | FileCheck %s
+
+; The test checks if we can remove first iteration exit compare:
+;  for (i = 84; i > 1; i--)
+;   for (j = i; j < i; j++)
+;     ...
+
+; CHECK: for.cond1:
+; CHECK-NEXT: br i1 false
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+@b = common global [100 x i32] zeroinitializer, align 16
+@a = common global [100 x i32] zeroinitializer, align 16
+
+; Function Attrs: nounwind uwtable
+define void @foo() local_unnamed_addr {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc12, %entry
+  %i.0 = phi i32 [ 84, %entry ], [ %dec, %for.inc12 ]
+  %cmp = icmp ugt i32 %i.0, 1
+  br i1 %cmp, label %for.cond1.preheader, label %for.end13
+
+for.cond1.preheader:                              ; preds = %for.cond
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.cond1.preheader, %for.inc9
+  %j.0 = phi i32 [ %inc10, %for.inc9 ], [ %i.0, %for.cond1.preheader ]
+  %cmp2 = icmp ult i32 %j.0, %i.0
+  br i1 %cmp2, label %for.cond4.preheader, label %for.inc12
+
+for.cond4.preheader:                              ; preds = %for.cond1
+  br label %for.cond4
+
+for.cond4:                                        ; preds = %for.cond4.preheader, %for.body6
+  %k.0 = phi i32 [ %inc, %for.body6 ], [ 1, %for.cond4.preheader ]
+  %cmp5 = icmp ult i32 %k.0, 7
+  br i1 %cmp5, label %for.body6, label %for.inc9
+
+for.body6:                                        ; preds = %for.cond4
+  %idxprom = zext i32 %k.0 to i64
+  %arrayidx = getelementptr inbounds [100 x i32], [100 x i32]* @b, i64 0, i64 %idxprom
+  %0 = load i32, i32* %arrayidx, align 4
+  %idxprom7 = zext i32 %i.0 to i64
+  %arrayidx8 = getelementptr inbounds [100 x i32], [100 x i32]* @a, i64 0, i64 %idxprom7
+  store i32 %0, i32* %arrayidx8, align 4
+  %inc = add nuw nsw i32 %k.0, 1
+  br label %for.cond4
+
+for.inc9:                                         ; preds = %for.cond4
+  %inc10 = add i32 %j.0, 1
+  br label %for.cond1
+
+for.inc12:                                        ; preds = %for.cond1
+  %dec = add i32 %i.0, -1
+  br label %for.cond
+
+for.end13:                                        ; preds = %for.cond
+  ret void
+}