Use parameter constraints provided via llvm.assume

  If an llvm.assume dominates the SCoP entry block and the assumed condition
  can be expressed as an affine inequality we will now add it to the context.

Differential Revision: http://reviews.llvm.org/D14413

llvm-svn: 252851

6 files changed, 301 insertions, 9 deletions

diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index b0686a8..b1c4eac 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -34,6 +34,7 @@
 using namespace llvm;
 
 namespace llvm {
+class AssumptionCache;
 class Loop;
 class LoopInfo;
 class PHINode;
@@ -1195,7 +1196,7 @@ private:
        unsigned MaxLoopDepth);
 
   /// @brief Initialize this ScopInfo .
-  void init(AliasAnalysis &AA);
+  void init(AliasAnalysis &AA, AssumptionCache &AC);
 
   /// @brief Add loop carried constraints to the header block of the loop @p L.
   ///
@@ -1280,7 +1281,10 @@ private:
   /// @brief Build the BoundaryContext based on the wrapping of expressions.
   void buildBoundaryContext();
 
-  /// @brief Add user provided parameter constraints to context.
+  /// @brief Add user provided parameter constraints to context (source code).
+  void addUserAssumptions(AssumptionCache &AC);
+
+  /// @brief Add user provided parameter constraints to context (command line).
   void addUserContext();
 
   /// @brief Add the bounds of the parameters to the context.
@@ -1698,7 +1702,7 @@ class ScopInfo : public RegionPass {
   void clear();
 
   // Build the SCoP for Region @p R.
-  void buildScop(Region &R, DominatorTree &DT);
+  void buildScop(Region &R, DominatorTree &DT, AssumptionCache &AC);
 
   /// @brief Build an instance of MemoryAccess from the Load/Store instruction.
   ///
diff --git a/polly/include/polly/Support/SCEVValidator.h b/polly/include/polly/Support/SCEVValidator.h
index 05b3109..f58510a 100644
--- a/polly/include/polly/Support/SCEVValidator.h
+++ b/polly/include/polly/Support/SCEVValidator.h
@@ -49,6 +49,13 @@ bool hasScalarDepsInsideRegion(const llvm::SCEV *S, const llvm::Region *R);
 bool isAffineExpr(const llvm::Region *R, const llvm::SCEV *Expression,
                   llvm::ScalarEvolution &SE, const llvm::Value *BaseAddress = 0,
                   InvariantLoadsSetTy *ILS = nullptr);
+
+/// @brief Check if @p V describes an affine parameter constraint in @p R.
+bool isAffineParamConstraint(llvm::Value *V, const llvm::Region *R,
+                             llvm::ScalarEvolution &SE,
+                             std::vector<const llvm::SCEV *> &Params,
+                             bool OrExpr = false);
+
 std::vector<const llvm::SCEV *>
 getParamsInAffineExpr(const llvm::Region *R, const llvm::SCEV *Expression,
                       llvm::ScalarEvolution &SE,
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index bb2dd56..c3d66df 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -30,6 +30,7 @@
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/RegionIterator.h"
@@ -1033,7 +1034,9 @@ buildConditionSets(Scop &S, SwitchInst *SI, Loop *L, __isl_keep isl_set *Domain,
 ///
 /// This will fill @p ConditionSets with the conditions under which control
 /// will be moved from @p TI to its successors. Hence, @p ConditionSets will
-/// have as many elements as @p TI has successors.
+/// have as many elements as @p TI has successors. If @p TI is nullptr the
+/// context under which @p Condition is true/false will be returned as the
+/// new elements of @p ConditionSets.
 static void
 buildConditionSets(Scop &S, Value *Condition, TerminatorInst *TI, Loop *L,
                    __isl_keep isl_set *Domain,
@@ -1067,7 +1070,7 @@ buildConditionSets(Scop &S, Value *Condition, TerminatorInst *TI, Loop *L,
            "Condition of exiting branch was neither constant nor ICmp!");
 
     ScalarEvolution &SE = *S.getSE();
-    BasicBlock *BB = TI->getParent();
+    BasicBlock *BB = TI ? TI->getParent() : nullptr;
     isl_pw_aff *LHS, *RHS;
     LHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L), BB);
     RHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L), BB);
@@ -1075,6 +1078,11 @@ buildConditionSets(Scop &S, Value *Condition, TerminatorInst *TI, Loop *L,
         buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain);
   }
 
+  // If no terminator was given we are only looking for parameter constraints
+  // under which @p Condition is true/false.
+  if (!TI)
+    ConsequenceCondSet = isl_set_params(ConsequenceCondSet);
+
   assert(ConsequenceCondSet);
   isl_set *AlternativeCondSet =
       isl_set_complement(isl_set_copy(ConsequenceCondSet));
@@ -1611,6 +1619,41 @@ void Scop::buildBoundaryContext() {
   trackAssumption(WRAPPING, BoundaryContext, DebugLoc());
 }
 
+void Scop::addUserAssumptions(AssumptionCache &AC) {
+  auto *R = &getRegion();
+  auto &F = *R->getEntry()->getParent();
+  for (auto &Assumption : AC.assumptions()) {
+    auto *CI = dyn_cast_or_null<CallInst>(Assumption);
+    if (!CI || CI->getNumArgOperands() != 1)
+      continue;
+    if (!DT.dominates(CI->getParent(), R->getEntry()))
+      continue;
+
+    auto *Val = CI->getArgOperand(0);
+    std::vector<const SCEV *> Params;
+    if (!isAffineParamConstraint(Val, R, *SE, Params)) {
+      emitOptimizationRemarkAnalysis(F.getContext(), DEBUG_TYPE, F,
+                                     CI->getDebugLoc(),
+                                     "Non-affine user assumption ignored.");
+      continue;
+    }
+
+    addParams(Params);
+
+    auto *L = LI.getLoopFor(CI->getParent());
+    SmallVector<isl_set *, 2> ConditionSets;
+    buildConditionSets(*this, Val, nullptr, L, Context, ConditionSets);
+    assert(ConditionSets.size() == 2);
+    isl_set_free(ConditionSets[1]);
+
+    auto *AssumptionCtx = ConditionSets[0];
+    emitOptimizationRemarkAnalysis(
+        F.getContext(), DEBUG_TYPE, F, CI->getDebugLoc(),
+        "Use user assumption: " + stringFromIslObj(AssumptionCtx));
+    Context = isl_set_intersect(Context, AssumptionCtx);
+  }
+}
+
 void Scop::addUserContext() {
   if (UserContextStr.empty())
     return;
@@ -2510,8 +2553,9 @@ Scop::Scop(Region &R, AccFuncMapType &AccFuncMap, ScopDetection &SD,
       Affinator(this), AssumedContext(nullptr), BoundaryContext(nullptr),
       Schedule(nullptr) {}
 
-void Scop::init(AliasAnalysis &AA) {
+void Scop::init(AliasAnalysis &AA, AssumptionCache &AC) {
   buildContext();
+  addUserAssumptions(AC);
   buildInvariantEquivalenceClasses();
 
   buildDomains(&R);
@@ -3814,7 +3858,7 @@ void ScopInfo::addPHIReadAccess(PHINode *PHI) {
                   MemoryAccess::PHI);
 }
 
-void ScopInfo::buildScop(Region &R, DominatorTree &DT) {
+void ScopInfo::buildScop(Region &R, DominatorTree &DT, AssumptionCache &AC) {
   unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD);
   scop = new Scop(R, AccFuncMap, *SD, *SE, DT, *LI, ctx, MaxLoopDepth);
 
@@ -3831,7 +3875,7 @@ void ScopInfo::buildScop(Region &R, DominatorTree &DT) {
   if (!R.getExitingBlock())
     buildAccessFunctions(R, *R.getExit(), nullptr, /* IsExitBlock */ true);
 
-  scop->init(*AA);
+  scop->init(*AA, AC);
 }
 
 void ScopInfo::print(raw_ostream &OS, const Module *) const {
@@ -3869,6 +3913,7 @@ void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
   AU.addRequiredTransitive<ScopDetection>();
   AU.addRequired<AAResultsWrapperPass>();
+  AU.addRequired<AssumptionCacheTracker>();
   AU.setPreservesAll();
 }
 
@@ -3884,13 +3929,14 @@ bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   TD = &F->getParent()->getDataLayout();
   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(*F);
 
   DebugLoc Beg, End;
   getDebugLocations(R, Beg, End);
   std::string Msg = "SCoP begins here.";
   emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, Beg, Msg);
 
-  buildScop(*R, DT);
+  buildScop(*R, DT, AC);
 
   DEBUG(scop->print(dbgs()));
 
@@ -3918,6 +3964,7 @@ INITIALIZE_PASS_BEGIN(ScopInfo, "polly-scops",
                       "Polly - Create polyhedral description of Scops", false,
                       false);
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker);
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
diff --git a/polly/lib/Support/SCEVValidator.cpp b/polly/lib/Support/SCEVValidator.cpp
index 9b3ce18..e22d3df 100644
--- a/polly/lib/Support/SCEVValidator.cpp
+++ b/polly/lib/Support/SCEVValidator.cpp
@@ -587,6 +587,44 @@ bool isAffineExpr(const Region *R, const SCEV *Expr, ScalarEvolution &SE,
   return Result.isValid();
 }
 
+static bool isAffineParamExpr(Value *V, const Region *R, ScalarEvolution &SE,
+                              std::vector<const SCEV *> &Params) {
+  auto *E = SE.getSCEV(V);
+  if (isa<SCEVCouldNotCompute>(E))
+    return false;
+
+  SCEVValidator Validator(R, SE, nullptr, nullptr);
+  ValidatorResult Result = Validator.visit(E);
+  if (!Result.isConstant())
+    return false;
+
+  auto ResultParams = Result.getParameters();
+  Params.insert(Params.end(), ResultParams.begin(), ResultParams.end());
+
+  return true;
+}
+
+bool isAffineParamConstraint(Value *V, const Region *R, ScalarEvolution &SE,
+                             std::vector<const SCEV *> &Params, bool OrExpr) {
+  if (auto *ICmp = dyn_cast<ICmpInst>(V)) {
+    return isAffineParamConstraint(ICmp->getOperand(0), R, SE, Params, true) &&
+           isAffineParamConstraint(ICmp->getOperand(1), R, SE, Params, true);
+  } else if (auto *BinOp = dyn_cast<BinaryOperator>(V)) {
+    auto Opcode = BinOp->getOpcode();
+    if (Opcode == Instruction::And || Opcode == Instruction::Or)
+      return isAffineParamConstraint(BinOp->getOperand(0), R, SE, Params,
+                                     false) &&
+             isAffineParamConstraint(BinOp->getOperand(1), R, SE, Params,
+                                     false);
+    /* Fall through */
+  }
+
+  if (!OrExpr)
+    return false;
+
+  return isAffineParamExpr(V, R, SE, Params);
+}
+
 std::vector<const SCEV *> getParamsInAffineExpr(const Region *R,
                                                 const SCEV *Expr,
                                                 ScalarEvolution &SE,
diff --git a/polly/test/ScopInfo/user_provided_assumptions.ll b/polly/test/ScopInfo/user_provided_assumptions.ll
new file mode 100644
index 0000000..437c33e
--- /dev/null
+++ b/polly/test/ScopInfo/user_provided_assumptions.ll
@@ -0,0 +1,122 @@
+; RUN: opt %loadPolly -pass-remarks-analysis="polly-scops" -polly-scops -analyze < %s 2>&1| FileCheck %s
+;
+; CHECK:      remark: <unknown>:0:0: SCoP begins here.
+; CHECK-NEXT: remark: <unknown>:0:0: Use user assumption: [M, N] -> {  : N <= 2147483647 - M }
+; CHECK-NEXT: remark: <unknown>:0:0: Use user assumption: [M, N] -> {  : N >= -2147483648 - M and N <= 2147483647 - M }
+; CHECK-NEXT: remark: <unknown>:0:0: Use user assumption: [M, N, Debug] -> {  : Debug = 0 and M <= 100 and M >= 1 and N <= 2147483647 - M and N >= -2147483648 - M }
+; CHECK-NEXT: remark: <unknown>:0:0: Use user assumption: [M, N, Debug] -> {  : Debug = 0 and N >= -2147483648 - M and N <= 2147483647 - M and M <= 100 and M >= 1 and N >= 1 }
+; CHECK-NEXT: remark: <unknown>:0:0: SCoP ends here.
+;
+; CHECK:      Context:
+; CHECK-NEXT:   [N, M, Debug] -> {  : Debug = 0 and N >= 1 and M <= 2147483647 - N and M <= 100 and M >= 1 }
+; CHECK-NEXT: Assumed Context:
+; CHECK-NEXT:   [N, M, Debug] -> {  :  }
+; CHECK-NEXT: Boundary Context:
+; CHECK-NEXT:   [N, M, Debug] -> {  :  }
+;
+;    #include <stdio.h>
+;
+;    void valid(int * restrict A, int * restrict B, int N, int M, int C[100][100], int Debug) {
+;      __builtin_assume(M <= 2147483647 - N);
+;      __builtin_assume(M >= -2147483648 - N);
+;      __builtin_assume(Debug == 0 && M <= 100 && M >= 1 && N >= 1);
+;      if (N + M == -1)
+;        C[0][0] = 0;
+;
+;      for (int i = 0; i < N; i++) {
+;        for (int j = 0; j != M; j++) {
+;          C[i][j] += A[i * M + j] + B[i + j];
+;        }
+;
+;        if (Debug)
+;          printf("Printf!");
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@.str = private unnamed_addr constant [8 x i8] c"Printf!\00", align 1
+
+define void @valid(i32* noalias %A, i32* noalias %B, i32 %N, i32 %M, [100 x i32]* %C, i32 %Debug) {
+entry:
+  %sub = sub nsw i32 2147483647, %N
+  %cmp = icmp sge i32 %sub, %M
+  call void @llvm.assume(i1 %cmp)
+  %conv = sext i32 %M to i64
+  %conv1 = sext i32 %N to i64
+  %sub2 = sub nsw i64 -2147483648, %conv1
+  %cmp3 = icmp sge i64 %conv, %sub2
+  call void @llvm.assume(i1 %cmp3)
+  %cmp5 = icmp eq i32 %Debug, 0
+  %cmp7 = icmp slt i32 %M, 101
+  %or.cond = and i1 %cmp5, %cmp7
+  %cmp10 = icmp sgt i32 %M, 0
+  %or.cond1 = and i1 %or.cond, %cmp10
+  %cmp12 = icmp sgt i32 %N, 0
+  call void @llvm.assume(i1 %or.cond1)
+  call void @llvm.assume(i1 %cmp12)
+  %add = add nsw i32 %N, %M
+  %cmp14 = icmp eq i32 %add, -1
+  br label %entry.split
+
+entry.split:
+  br i1 %cmp14, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %arrayidx16 = getelementptr inbounds [100 x i32], [100 x i32]* %C, i64 0, i64 0
+  store i32 0, i32* %arrayidx16, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  %M64 = sext i32 %M to i64
+  %N64 = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc.36, %if.end
+  %indvars.iv3 = phi i64 [ %indvars.iv.next4, %for.inc.36 ], [ 0, %if.end ]
+  %cmp17 = icmp slt i64 %indvars.iv3, %N64
+  br i1 %cmp17, label %for.cond.19, label %for.end.38
+
+for.cond.19:                                      ; preds = %for.cond, %for.body.22
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body.22 ], [ 0, %for.cond ]
+  %cmp20 = icmp eq i64 %indvars.iv, %M64
+  br i1 %cmp20, label %for.end, label %for.body.22
+
+for.body.22:                                      ; preds = %for.cond.19
+  %tmp9 = mul nsw i64 %indvars.iv3, %M64
+  %tmp10 = add nsw i64 %tmp9, %indvars.iv
+  %arrayidx24 = getelementptr inbounds i32, i32* %A, i64 %tmp10
+  %tmp11 = load i32, i32* %arrayidx24, align 4
+  %tmp12 = add nuw nsw i64 %indvars.iv3, %indvars.iv
+  %arrayidx27 = getelementptr inbounds i32, i32* %B, i64 %tmp12
+  %tmp13 = load i32, i32* %arrayidx27, align 4
+  %add28 = add nsw i32 %tmp11, %tmp13
+  %arrayidx32 = getelementptr inbounds [100 x i32], [100 x i32]* %C, i64 %indvars.iv3, i64 %indvars.iv
+  %tmp14 = load i32, i32* %arrayidx32, align 4
+  %add33 = add nsw i32 %tmp14, %add28
+  store i32 %add33, i32* %arrayidx32, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond.19
+
+for.end:                                          ; preds = %for.cond.19
+  %tobool = icmp eq i32 %Debug, 0
+  br i1 %tobool, label %for.inc.36, label %if.then.34
+
+if.then.34:                                       ; preds = %for.end
+  %call = call i32 (i8*, ...) @printf(i8* nonnull getelementptr inbounds ([8 x i8], [8 x i8]* @.str, i64 0, i64 0))
+  br label %for.inc.36
+
+for.inc.36:                                       ; preds = %for.end, %if.then.34
+  %indvars.iv.next4 = add nuw nsw i64 %indvars.iv3, 1
+  br label %for.cond
+
+for.end.38:                                       ; preds = %for.cond
+  ret void
+}
+
+; Function Attrs: nounwind
+declare void @llvm.assume(i1) #0
+
+declare i32 @printf(i8*, ...)
+
+attributes #0 = { nounwind }
diff --git a/polly/test/ScopInfo/user_provided_non_dominating_assumptions.ll b/polly/test/ScopInfo/user_provided_non_dominating_assumptions.ll
new file mode 100644
index 0000000..f891c90
--- /dev/null
+++ b/polly/test/ScopInfo/user_provided_non_dominating_assumptions.ll
@@ -0,0 +1,74 @@
+; RUN: opt %loadPolly -pass-remarks-analysis="polly-scops" -polly-scops < %s 2>&1| FileCheck %s
+;
+; CHECK:      remark: <unknown>:0:0: SCoP begins here.
+; CHECK-NEXT: remark: <unknown>:0:0: Inbounds assumption: [i, N, p_2, M] -> {  : N <= i or (N >= 1 + i and p_2 <= 0) or (N >= 1 + i and p_2 >= 1 and M >= p_2) }
+; CHECK-NEXT: remark: <unknown>:0:0: Inbounds assumption: [i, N, p_2] -> {  : N <= i or (N >= 1 + i and p_2 <= 100) }
+; CHECK-NEXT: remark: <unknown>:0:0: SCoP ends here.
+;
+;    void f(int *restrict A, int *restrict B, int i, int N, int M, int C[100][100]) {
+;      for (; i < N; i++) {
+;        __builtin_assume(N >= 0);
+;        for (int j = 0; j != M; j++) {
+;          __builtin_assume(N >= 0);
+;          C[i][j] += A[i * M + j] + B[i + j];
+;        }
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* noalias %A, i32* noalias %B, i32 %i, i32 %N, i32 %M, [100 x i32]* %C) {
+entry:
+  %tmp = zext i32 %M to i64
+  %tmp6 = sext i32 %i to i64
+  %tmp7 = sext i32 %N to i64
+  %tmp8 = sext i32 %M to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc.15, %entry
+  %indvars.iv3 = phi i64 [ %indvars.iv.next4, %for.inc.15 ], [ %tmp6, %entry ]
+  %cmp = icmp slt i64 %indvars.iv3, %tmp7
+  br i1 %cmp, label %for.body, label %for.end.17
+
+for.body:                                         ; preds = %for.cond
+  %cmp1 = icmp sgt i32 %N, -1
+  call void @llvm.assume(i1 %cmp1)
+  br label %for.cond.2
+
+for.cond.2:                                       ; preds = %for.inc, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %for.body ]
+  %cmp3 = icmp eq i64 %indvars.iv, %tmp
+  br i1 %cmp3, label %for.end, label %for.body.4
+
+for.body.4:                                       ; preds = %for.cond.2
+  %tmp9 = mul nsw i64 %indvars.iv3, %tmp8
+  %tmp10 = add nsw i64 %tmp9, %indvars.iv
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %tmp10
+  %tmp11 = load i32, i32* %arrayidx, align 4
+  %tmp12 = add nsw i64 %indvars.iv3, %indvars.iv
+  %arrayidx8 = getelementptr inbounds i32, i32* %B, i64 %tmp12
+  %tmp13 = load i32, i32* %arrayidx8, align 4
+  %add9 = add nsw i32 %tmp11, %tmp13
+  %arrayidx13 = getelementptr inbounds [100 x i32], [100 x i32]* %C, i64 %indvars.iv3, i64 %indvars.iv
+  %tmp14 = load i32, i32* %arrayidx13, align 4
+  %add14 = add nsw i32 %tmp14, %add9
+  store i32 %add14, i32* %arrayidx13, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body.4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond.2
+
+for.end:                                          ; preds = %for.cond.2
+  br label %for.inc.15
+
+for.inc.15:                                       ; preds = %for.end
+  %indvars.iv.next4 = add nsw i64 %indvars.iv3, 1
+  br label %for.cond
+
+for.end.17:                                       ; preds = %for.cond
+  ret void
+}
+
+declare void @llvm.assume(i1) #1
+