Use modulo semantic to generate non-integer-overflow assumptions
This will allow to generate non-wrap assumptions for integer expressions
that are part of the SCoP. We compare the common isl representation of
the expression with one computed with modulo semantic. For all parameter
combinations they are not equal we can have integer overflows.
The nsw flags are respected when the modulo representation is computed,
nuw and nw flags are ignored for now.
In order to not increase compile time to much, the non-wrap assumptions
are collected in a separate boundary context instead of the assumed
context. This helps compile time as the boundary context can become
complex and it is therefor not advised to use it in other operations
except runtime check generation. However, the assumed context is e.g.,
used to tighten dependences. While the boundary context might help to
tighten the assumed context it is doubtful that it will help in practice
(it does not effect lnt much) as the boundary (or no-wrap assumptions)
only restrict the very end of the possible value range of parameters.
PET uses a different approach to compute the no-wrap context, though lnt runs
have shown that this version performs slightly better for us.
llvm-svn: 247732
diff --git a/polly/test/ScopInfo/wraping_signed_expr_0.ll b/polly/test/ScopInfo/wraping_signed_expr_0.ll
new file mode 100644
index 0000000..f03bff3
--- /dev/null
+++ b/polly/test/ScopInfo/wraping_signed_expr_0.ll
@@ -0,0 +1,71 @@
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+;
+; void f(int *A, char N, char p) {
+; for (char i = 0; i < N; i++) {
+; A[i + 3] = 0;
+; }
+; }
+;
+; The wrap function has no inbounds GEP but the nowrap function has. Therefore,
+; we will add the assumption that i+1 won't overflow only to the former.
+;
+; CHECK: Function: wrap
+; CHECK: Boundary Context:
+; CHECK: [N] -> { : N <= 125 }
+;
+;
+; FIXME: This is a negative test as nowrap should not need an assumed context.
+; However %tmp5 in @nowrap is translated to the SCEV <3,+,1><nw><%bb2>
+; which lacks the <nsw> flags we would need to avoid runtime checks.
+;
+; CHECK: Function: nowrap
+; CHECK: Boundary Context:
+; CHECK-NOT: [N] -> { : }
+;
+target datalayout = "e-m:e-i8:64-f80:128-n8:16:32:64-S128"
+
+define void @wrap(i32* %A, i8 %N, i8 %p) {
+bb:
+ br label %bb2
+
+bb2: ; preds = %bb7, %bb
+ %indvars.iv = phi i8 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+ %tmp3 = icmp slt i8 %indvars.iv, %N
+ br i1 %tmp3, label %bb4, label %bb8
+
+bb4: ; preds = %bb2
+ %tmp5 = add i8 %indvars.iv, 3
+ %tmp6 = getelementptr i32, i32* %A, i8 %tmp5
+ store i32 0, i32* %tmp6, align 4
+ br label %bb7
+
+bb7: ; preds = %bb4
+ %indvars.iv.next = add nsw nuw i8 %indvars.iv, 1
+ br label %bb2
+
+bb8: ; preds = %bb2
+ ret void
+}
+
+define void @nowrap(i32* %A, i8 %N, i8 %p) {
+bb:
+ br label %bb2
+
+bb2: ; preds = %bb7, %bb
+ %indvars.iv = phi i8 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+ %tmp3 = icmp slt i8 %indvars.iv, %N
+ br i1 %tmp3, label %bb4, label %bb8
+
+bb4: ; preds = %bb2
+ %tmp5 = add nsw nuw i8 %indvars.iv, 3
+ %tmp6 = getelementptr inbounds i32, i32* %A, i8 %tmp5
+ store i32 0, i32* %tmp6, align 4
+ br label %bb7
+
+bb7: ; preds = %bb4
+ %indvars.iv.next = add nsw nuw i8 %indvars.iv, 1
+ br label %bb2
+
+bb8: ; preds = %bb2
+ ret void
+}