Use invariants in ScalarEvolution

[hfinkel]

Summary

This patch adds a basic (but important) use of invariants in ScalarEvolution. When SE is attempting to validate a condition guarding a loop (such as whether or not the loop count can be zero), this check should also include dominating invariants.

[hfinkel]

Renamed to llvm.assume.

[reames]

I'm not knowledgeable of this code, but I don't see anything which is obviously wrong. Feel free to take or ignore the ordering and style comments.

lib/Analysis/ScalarEvolution.cpp

6337

It seems like the assumption code could also apply here. The patterns are very similar.

I can't think of a case of the top of my head where this would be profitable though. Maybe something about pre and post alignment loops in vectorized code? (i.e. we can conclude that only one iteration is needed from alignment info)

6361

Shouldn't this be after the if(!LoopEntryPredicate) early return?

It also feels like it should be after the branch condition check since that's likely to be cheaper.

I even wonder if the assumption processing shouldn't be done as a separate loop to avoid searching out invariants in what might be a common case.

6365

You have this pattern of checks a lot in different changes. Time to extract a helper function somewhere common? isAssumeIntrinsic(Instruction* I)?

[hfinkel]

lib/Analysis/ScalarEvolution.cpp

6337

Good point. I also could not particularly think of a place where this would help, but the cost of finding the intrinsics and determining applicability here is low, so we might as well.

6361

It could be, but then I'd also need to split the early return (because we don't want it after the LoopEntryPredicate->isUnconditional() part of the early return). Thinking about it, splitting the early-return check is the cleaner thing to do.

6365

True. In many places I use the PatternMatch header facilities to make this easier, and I should perhaps do so more often (like here, for example).

[hfinkel]

Updated to use AssumptionTracker (and those review comments still relevant (hopefully I got them all)).

[hfinkel]

(will close)

[hfinkel]

r217348.

include/llvm/Analysis/ScalarEvolution.h

 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/DataTypes.h"
 #include <map>
 
 namespace llvm {
   class APInt;
+  class AssumptionTracker;
   class Constant;
   class ConstantInt;
   class DominatorTree;
   class Type;
   class ScalarEvolution;
   class DataLayout;
   class TargetLibraryInfo;
   class LLVMContext;
private:
     friend class SCEVCallbackVH;
     friend class SCEVExpander;
     friend class SCEVUnknown;
 
     /// F - The function we are analyzing.
     ///
     Function *F;
 
+    /// The tracker for @llvm.assume intrinsics in this function.
+    AssumptionTracker *AT;
+
     /// LI - The loop information for the function we are currently analyzing.
     ///
     LoopInfo *LI;
 
     /// The DataLayout information for the target we are targeting.
     ///
     const DataLayout *DL;
 

lib/Analysis/ScalarEvolution.cpp

 //  MS Thesis, Johnie Birch
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AssumptionTracker.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"

 
 // FIXME: Enable this with XDEBUG when the test suite is clean.
 static cl::opt<bool>
 VerifySCEV("verify-scev",
            cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"));
 
 INITIALIZE_PASS_BEGIN(ScalarEvolution, "scalar-evolution",
                 "Scalar Evolution Analysis", false, true)
+INITIALIZE_PASS_DEPENDENCY(AssumptionTracker)
 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
 INITIALIZE_PASS_END(ScalarEvolution, "scalar-evolution",
                 "Scalar Evolution Analysis", false, true)
 char ScalarEvolution::ID = 0;
 
 //===----------------------------------------------------------------------===//
ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L,
   if (!L) return true;
 
   BasicBlock *Latch = L->getLoopLatch();
   if (!Latch)
     return false;
 
   BranchInst *LoopContinuePredicate =
     dyn_cast<BranchInst>(Latch->getTerminator());
-  if (!LoopContinuePredicate ||
-      LoopContinuePredicate->isUnconditional())
-    return false;
-
-  return isImpliedCond(Pred, LHS, RHS,
-                       LoopContinuePredicate->getCondition(),
-                       LoopContinuePredicate->getSuccessor(0) != L->getHeader());
+  if (LoopContinuePredicate && LoopContinuePredicate->isConditional() &&
+      isImpliedCond(Pred, LHS, RHS,
+                    LoopContinuePredicate->getSuccessor(0) != L->getHeader()))
+    return true;
+
+  // Check conditions due to any @llvm.assume intrinsics.
+  for (auto &CI : AT->assumptions(F)) {
+    if (!DT->dominates(CI, Latch->getTerminator()))
+      continue;
+
+    if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
+      return true;
+  }
+
+  return false;
 }
 
 /// isLoopEntryGuardedByCond - Test whether entry to the loop is protected
 /// by a conditional between LHS and RHS.  This is used to help avoid max
 /// expressions in loop trip counts, and to eliminate casts.
 bool
 ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
                                           ICmpInst::Predicate Pred,
                                           const SCEV *LHS, const SCEV *RHS) {
   // Interpret a null as meaning no loop, where there is obviously no guard
   // (interprocedural conditions notwithstanding).
   if (!L) return false;
 
   // Starting at the loop predecessor, climb up the predecessor chain, as long
   // as there are predecessors that can be found that have unique successors
   // leading to the original header.
   for (std::pair<BasicBlock *, BasicBlock *>
          Pair(L->getLoopPredecessor(), L->getHeader());
        Pair.first;
        Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
 
     BranchInst *LoopEntryPredicate =
       dyn_cast<BranchInst>(Pair.first->getTerminator());
     if (!LoopEntryPredicate ||
         LoopEntryPredicate->isUnconditional())
       continue;
 
     if (isImpliedCond(Pred, LHS, RHS,
                       LoopEntryPredicate->getCondition(),
                       LoopEntryPredicate->getSuccessor(0) != Pair.second))
       return true;
   }
 
+  // Check conditions due to any @llvm.assume intrinsics.
+  for (auto &CI : AT->assumptions(F)) {
+    if (!DT->dominates(CI, L->getHeader()))
+      continue;
+
+    if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
+      return true;
+  }
+
   return false;
 }
 
 /// RAII wrapper to prevent recursive application of isImpliedCond.
 /// ScalarEvolution's PendingLoopPredicates set must be empty unless we are
 /// currently evaluating isImpliedCond.
 struct MarkPendingLoopPredicate {
   Value *Cond;

 ScalarEvolution::ScalarEvolution()
   : FunctionPass(ID), ValuesAtScopes(64), LoopDispositions(64),
     BlockDispositions(64), FirstUnknown(nullptr) {
   initializeScalarEvolutionPass(*PassRegistry::getPassRegistry());
 }
 
 bool ScalarEvolution::runOnFunction(Function &F) {
   this->F = &F;
+  AT = &getAnalysis<AssumptionTracker>();
   LI = &getAnalysis<LoopInfo>();
   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
   DL = DLP ? &DLP->getDataLayout() : nullptr;
   TLI = &getAnalysis<TargetLibraryInfo>();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   return false;
 }
 
void ScalarEvolution::releaseMemory() {
   UnsignedRanges.clear();
   SignedRanges.clear();
   UniqueSCEVs.clear();
   SCEVAllocator.Reset();
 }
 
 void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
+  AU.addRequired<AssumptionTracker>();
   AU.addRequiredTransitive<LoopInfo>();
   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
   AU.addRequired<TargetLibraryInfo>();
 }
 
 bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) {
   return !isa<SCEVCouldNotCompute>(getBackedgeTakenCount(L));
 }

test/Analysis/ScalarEvolution/nsw-offset-assume.ll

+; RUN: opt < %s -S -analyze -scalar-evolution | FileCheck %s
+
+; ScalarEvolution should be able to fold away the sign-extensions
+; on this loop with a primary induction variable incremented with
+; a nsw add of 2 (this test is derived from the nsw-offset.ll test, but uses an
+; assume instead of a preheader conditional branch to guard the loop).
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
+
+define void @foo(i32 %no, double* nocapture %d, double* nocapture %q) nounwind {
+entry:
+  %n = and i32 %no, 4294967294
+  %0 = icmp sgt i32 %n, 0                         ; <i1> [#uses=1]
+  tail call void @llvm.assume(i1 %0)
+  br label %bb.nph
+
+bb.nph:                                           ; preds = %entry
+  br label %bb
+
+bb:                                               ; preds = %bb.nph, %bb1
+  %i.01 = phi i32 [ %16, %bb1 ], [ 0, %bb.nph ]   ; <i32> [#uses=5]
+
+; CHECK: %1 = sext i32 %i.01 to i64
+; CHECK: -->  {0,+,2}<nuw><nsw><%bb>
+  %1 = sext i32 %i.01 to i64                      ; <i64> [#uses=1]
+
+; CHECK: %2 = getelementptr inbounds double* %d, i64 %1
+; CHECK: -->  {%d,+,16}<nsw><%bb>
+  %2 = getelementptr inbounds double* %d, i64 %1  ; <double*> [#uses=1]
+
+  %3 = load double* %2, align 8                   ; <double> [#uses=1]
+  %4 = sext i32 %i.01 to i64                      ; <i64> [#uses=1]
+  %5 = getelementptr inbounds double* %q, i64 %4  ; <double*> [#uses=1]
+  %6 = load double* %5, align 8                   ; <double> [#uses=1]
+  %7 = or i32 %i.01, 1                            ; <i32> [#uses=1]
+
+; CHECK: %8 = sext i32 %7 to i64
+; CHECK: -->  {1,+,2}<nuw><nsw><%bb>
+  %8 = sext i32 %7 to i64                         ; <i64> [#uses=1]
+
+; CHECK: %9 = getelementptr inbounds double* %q, i64 %8
+; CHECK: {(8 + %q),+,16}<nsw><%bb>
+  %9 = getelementptr inbounds double* %q, i64 %8  ; <double*> [#uses=1]
+
+; Artificially repeat the above three instructions, this time using
+; add nsw instead of or.
+  %t7 = add nsw i32 %i.01, 1                            ; <i32> [#uses=1]
+
+; CHECK: %t8 = sext i32 %t7 to i64
+; CHECK: -->  {1,+,2}<nuw><nsw><%bb>
+  %t8 = sext i32 %t7 to i64                         ; <i64> [#uses=1]
+
+; CHECK: %t9 = getelementptr inbounds double* %q, i64 %t8
+; CHECK: {(8 + %q),+,16}<nsw><%bb>
+  %t9 = getelementptr inbounds double* %q, i64 %t8  ; <double*> [#uses=1]
+
+  %10 = load double* %9, align 8                  ; <double> [#uses=1]
+  %11 = fadd double %6, %10                       ; <double> [#uses=1]
+  %12 = fadd double %11, 3.200000e+00             ; <double> [#uses=1]
+  %13 = fmul double %3, %12                       ; <double> [#uses=1]
+  %14 = sext i32 %i.01 to i64                     ; <i64> [#uses=1]
+  %15 = getelementptr inbounds double* %d, i64 %14 ; <double*> [#uses=1]
+  store double %13, double* %15, align 8
+  %16 = add nsw i32 %i.01, 2                      ; <i32> [#uses=2]
+  br label %bb1
+
+bb1:                                              ; preds = %bb
+  %17 = icmp slt i32 %16, %n                      ; <i1> [#uses=1]
+  br i1 %17, label %bb, label %bb1.return_crit_edge
+
+bb1.return_crit_edge:                             ; preds = %bb1
+  br label %return
+
+return:                                           ; preds = %bb1.return_crit_edge, %entry
+  ret void
+}
+
+declare void @llvm.assume(i1) nounwind
+
+; Note: Without the preheader assume, there is an 'smax' in the
+; backedge-taken count expression:
+; CHECK: Loop %bb: backedge-taken count is ((-1 + (2 * (%no /u 2))) /u 2)
+; CHECK: Loop %bb: max backedge-taken count is 1073741822