Extract some constant factors from "SCEVAddExprs"

  Additive expressions can have constant factors too that we can extract
  and thereby simplify the internal representation. For now we do
  compute the gcd of all constant factors but only extract the same
  (possibly negated) factor if there is one.

llvm-svn: 267445

2 files changed, 78 insertions, 0 deletions

diff --git a/polly/lib/Support/SCEVValidator.cpp b/polly/lib/Support/SCEVValidator.cpp
index b43b897959e..b3b3d28e771 100644
--- a/polly/lib/Support/SCEVValidator.cpp
+++ b/polly/lib/Support/SCEVValidator.cpp
@@ -605,6 +605,32 @@ extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {
     return std::make_pair(ConstPart, S);
   }
 
+  if (auto *Add = dyn_cast<SCEVAddExpr>(S)) {
+    SmallVector<const SCEV *, 4> LeftOvers;
+    auto Op0Pair = extractConstantFactor(Add->getOperand(0), SE);
+    auto *Factor = Op0Pair.first;
+    if (SE.isKnownNegative(Factor)) {
+      Factor = cast<SCEVConstant>(SE.getNegativeSCEV(Factor));
+      LeftOvers.push_back(SE.getNegativeSCEV(Op0Pair.second));
+    } else {
+      LeftOvers.push_back(Op0Pair.second);
+    }
+
+    for (unsigned u = 1, e = Add->getNumOperands(); u < e; u++) {
+      auto OpUPair = extractConstantFactor(Add->getOperand(u), SE);
+      // TODO: Use something smarter than equality here, e.g., gcd.
+      if (Factor == OpUPair.first)
+        LeftOvers.push_back(OpUPair.second);
+      else if (Factor == SE.getNegativeSCEV(OpUPair.first))
+        LeftOvers.push_back(SE.getNegativeSCEV(OpUPair.second));
+      else
+        return std::make_pair(ConstPart, S);
+    }
+
+    auto *NewAdd = SE.getAddExpr(LeftOvers, Add->getNoWrapFlags());
+    return std::make_pair(Factor, NewAdd);
+  }
+
   auto *Mul = dyn_cast<SCEVMulExpr>(S);
   if (!Mul)
     return std::make_pair(ConstPart, S);
diff --git a/polly/test/ScopInfo/parameter_with_constant_factor_in_add.ll b/polly/test/ScopInfo/parameter_with_constant_factor_in_add.ll
new file mode 100644
index 00000000000..7a751780084
--- /dev/null
+++ b/polly/test/ScopInfo/parameter_with_constant_factor_in_add.ll
@@ -0,0 +1,52 @@
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; Check that the access function of the store is simple and concise
+;
+; CHECK: p0: {0,+,(-1 + (sext i32 (-1 * %smax188) to i64))<nsw>}<%for.cond261.preheader>
+;
+; CHECK:      MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:   [p_0] -> { Stmt_for_body276[i0] -> MemRef_A[p_0] };
+;
+; ModuleID = 'bugpoint-reduced-simplified.bc'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Function Attrs: nounwind uwtable
+define void @BPredPartitionCost(i32* %A) #0 {
+entry:
+  %curr_blk = alloca [16 x [16 x i32]], align 16
+  br label %for.cond261.preheader.lr.ph
+
+for.cond261.preheader.lr.ph:                      ; preds = %entry
+  %smax188 = select i1 undef, i32 undef, i32 -9
+  %0 = sub i32 0, %smax188
+  %1 = sext i32 %0 to i64
+  %2 = add i64 %1, -1
+  br label %for.cond261.preheader
+
+for.cond261.preheader:                            ; preds = %for.inc299, %for.cond261.preheader.lr.ph
+  %indvars.iv189 = phi i64 [ 0, %for.cond261.preheader.lr.ph ], [ %indvars.iv.next190, %for.inc299 ]
+  br i1 undef, label %for.cond273.preheader, label %for.inc299
+
+for.cond273.preheader:                            ; preds = %for.cond261.preheader
+  br label %for.body276
+
+for.body276:                                      ; preds = %for.body276, %for.cond273.preheader
+  %indvars.iv = phi i64 [ 0, %for.cond273.preheader ], [ %indvars.iv.next, %for.body276 ]
+  %3 = add nsw i64 0, %indvars.iv189
+  %arrayidx282 = getelementptr inbounds [16 x [16 x i32]], [16 x [16 x i32]]* %curr_blk, i64 0, i64 %3, i64 0
+  %4 = load i32, i32* %arrayidx282, align 4
+  %arridx = getelementptr i32, i32* %A, i64 %3
+  store i32 0, i32* %arridx, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br i1 false, label %for.body276, label %for.end291
+
+for.end291:                                       ; preds = %for.body276
+  unreachable
+
+for.inc299:                                       ; preds = %for.cond261.preheader
+  %indvars.iv.next190 = add i64 %indvars.iv189, %2
+  br i1 undef, label %for.cond261.preheader, label %if.end302
+
+if.end302:                                        ; preds = %for.inc299
+  ret void
+}