summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/ScopDetectionDiagnostic.h27
-rw-r--r--polly/lib/Analysis/ScopDetection.cpp12
-rw-r--r--polly/lib/Analysis/ScopDetectionDiagnostic.cpp16
-rw-r--r--polly/lib/Analysis/ScopInfo.cpp12
-rw-r--r--polly/test/ScopInfo/simple_loop_unsigned.ll32
-rw-r--r--polly/test/ScopInfo/simple_loop_unsigned_2.ll25
-rw-r--r--polly/test/ScopInfo/simple_loop_unsigned_3.ll26
-rw-r--r--polly/test/ScopInfo/unsigned-condition.ll27
8 files changed, 107 insertions, 70 deletions
diff --git a/polly/include/polly/ScopDetectionDiagnostic.h b/polly/include/polly/ScopDetectionDiagnostic.h
index 4f16a1c7b52..6db80964b08 100644
--- a/polly/include/polly/ScopDetectionDiagnostic.h
+++ b/polly/include/polly/ScopDetectionDiagnostic.h
@@ -68,7 +68,6 @@ enum RejectReasonKind {
rrkAffFunc,
rrkUndefCond,
rrkInvalidCond,
- rrkUnsignedCond,
rrkUndefOperand,
rrkNonAffBranch,
rrkNoBasePtr,
@@ -346,32 +345,6 @@ public:
};
//===----------------------------------------------------------------------===//
-/// @brief Captures an condition on unsigned values
-///
-/// We do not yet allow conditions on unsigend values
-class ReportUnsignedCond : public ReportAffFunc {
- //===--------------------------------------------------------------------===//
-
- // The BasicBlock we found the broken condition in.
- BasicBlock *BB;
-
-public:
- ReportUnsignedCond(const Instruction *Inst, BasicBlock *BB)
- : ReportAffFunc(rrkUnsignedCond, Inst), BB(BB) {}
-
- /// @name LLVM-RTTI interface
- //@{
- static bool classof(const RejectReason *RR);
- //@}
-
- /// @name RejectReason interface
- //@{
- virtual std::string getMessage() const override;
- virtual std::string getEndUserMessage() const override;
- //@}
-};
-
-//===----------------------------------------------------------------------===//
/// @brief Captures an undefined operand.
class ReportUndefOperand : public ReportAffFunc {
//===--------------------------------------------------------------------===//
diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index 2e1caf51b10..4ee92fcfa93 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -149,11 +149,6 @@ static cl::opt<bool>
cl::Hidden, cl::init(false), cl::ZeroOrMore,
cl::cat(PollyCategory));
-static cl::opt<bool> AllowUnsigned("polly-allow-unsigned",
- cl::desc("Allow unsigned expressions"),
- cl::Hidden, cl::init(false), cl::ZeroOrMore,
- cl::cat(PollyCategory));
-
static cl::opt<bool, true>
TrackFailures("polly-detect-track-failures",
cl::desc("Track failure strings in detecting scop regions"),
@@ -385,13 +380,6 @@ bool ScopDetection::isValidBranch(BasicBlock &BB, BranchInst *BI,
}
ICmpInst *ICmp = cast<ICmpInst>(Condition);
- // Unsigned comparisons are not allowed. They trigger overflow problems
- // in the code generation.
- //
- // TODO: This is not sufficient and just hides bugs. However it does pretty
- // well.
- if (ICmp->isUnsigned() && !AllowUnsigned)
- return invalid<ReportUnsignedCond>(Context, /*Assert=*/true, BI, &BB);
// Are both operands of the ICmp affine?
if (isa<UndefValue>(ICmp->getOperand(0)) ||
diff --git a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
index 5d5a1a43f8e..25b121bc3ae 100644
--- a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
+++ b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
@@ -196,22 +196,6 @@ bool ReportInvalidCond::classof(const RejectReason *RR) {
}
//===----------------------------------------------------------------------===//
-// ReportUnsignedCond.
-
-std::string ReportUnsignedCond::getMessage() const {
- return ("Condition in BB '" + BB->getName()).str() +
- "' performs a comparision on (not yet supported) unsigned integers.";
-}
-
-std::string ReportUnsignedCond::getEndUserMessage() const {
- return "Unsupported comparision on unsigned integers encountered";
-}
-
-bool ReportUnsignedCond::classof(const RejectReason *RR) {
- return RR->getKind() == rrkUnsignedCond;
-}
-
-//===----------------------------------------------------------------------===//
// ReportUndefOperand.
std::string ReportUndefOperand::getMessage() const {
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 3b8770afa9a..014919634ed 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1317,6 +1317,18 @@ buildConditionSets(ScopStmt &Stmt, Value *Condition, TerminatorInst *TI,
isl_pw_aff *LHS, *RHS;
LHS = Stmt.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L));
RHS = Stmt.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L));
+
+ if (ICond->isUnsigned()) {
+ // For unsigned comparisons we assumed the signed bit of neither operand
+ // to be set. The comparison is equal to a signed comparison under this
+ // assumption.
+ auto *BB = Stmt.getEntryBlock();
+ S.recordAssumption(UNSIGNED, isl_pw_aff_nonneg_set(isl_pw_aff_copy(LHS)),
+ TI->getDebugLoc(), AS_ASSUMPTION, BB);
+ S.recordAssumption(UNSIGNED, isl_pw_aff_nonneg_set(isl_pw_aff_copy(RHS)),
+ TI->getDebugLoc(), AS_ASSUMPTION, BB);
+ }
+
ConsequenceCondSet =
buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain);
}
diff --git a/polly/test/ScopInfo/simple_loop_unsigned.ll b/polly/test/ScopInfo/simple_loop_unsigned.ll
new file mode 100644
index 00000000000..0f451f2cc2b
--- /dev/null
+++ b/polly/test/ScopInfo/simple_loop_unsigned.ll
@@ -0,0 +1,32 @@
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+
+; void f(int a[], unsigned N) {
+; unsigned i;
+; do {
+; a[i] = i;
+; } while (++i <= N);
+; }
+
+; CHECK: Assumed Context:
+; CHECK-NEXT: [N] -> { : N >= 0 }
+;
+; CHECK: Domain :=
+; CHECK-NEXT: [N] -> { Stmt_bb[i0] : 0 <= i0 < N; Stmt_bb[0] : N <= 0 };
+
+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 @f(i64* nocapture %a, i64 %N) nounwind {
+entry:
+ br label %bb
+
+bb: ; preds = %bb, %entry
+ %i = phi i64 [ 0, %entry ], [ %i.inc, %bb ]
+ %scevgep = getelementptr inbounds i64, i64* %a, i64 %i
+ store i64 %i, i64* %scevgep
+ %i.inc = add nsw i64 %i, 1
+ %exitcond = icmp uge i64 %i.inc, %N
+ br i1 %exitcond, label %return, label %bb
+
+return: ; preds = %bb, %entry
+ ret void
+}
diff --git a/polly/test/ScopInfo/simple_loop_unsigned_2.ll b/polly/test/ScopInfo/simple_loop_unsigned_2.ll
new file mode 100644
index 00000000000..744bf2771ad
--- /dev/null
+++ b/polly/test/ScopInfo/simple_loop_unsigned_2.ll
@@ -0,0 +1,25 @@
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+
+; CHECK: Assumed Context:
+; CHECK-NEXT: [N] -> { : N > 0 }
+;
+; CHECK: Domain :=
+; CHECK-NEXT: [N] -> { Stmt_bb[i0] : 0 <= i0 < N; Stmt_bb[0] : N <= 0 };
+;
+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 @f(i64* nocapture %a, i64 %N) nounwind {
+entry:
+ br label %bb
+
+bb: ; preds = %bb, %entry
+ %i = phi i64 [ %N, %entry ], [ %i.dec, %bb ]
+ %scevgep = getelementptr inbounds i64, i64* %a, i64 %i
+ store i64 %i, i64* %scevgep
+ %i.dec = add nsw i64 %i, -1
+ %exitcond = icmp ugt i64 %i.dec, 0
+ br i1 %exitcond, label %bb, label %return
+
+return: ; preds = %bb, %entry
+ ret void
+}
diff --git a/polly/test/ScopInfo/simple_loop_unsigned_3.ll b/polly/test/ScopInfo/simple_loop_unsigned_3.ll
new file mode 100644
index 00000000000..d495b68b466
--- /dev/null
+++ b/polly/test/ScopInfo/simple_loop_unsigned_3.ll
@@ -0,0 +1,26 @@
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+
+; CHECK: Assumed Context:
+; CHECK-NEXT: [N] -> { : }
+;
+; CHECK: Domain :=
+; CHECK-NEXT: [N] -> { Stmt_bb[i0] : 0 < i0 <= 1000 - N; Stmt_bb[0] };
+
+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 @f(i64* nocapture %a, i64 %N) nounwind {
+entry:
+ br label %bb
+
+bb: ; preds = %bb, %entry
+ %i = phi i64 [ 1000, %entry ], [ %i.dec, %bb ]
+ %scevgep = getelementptr inbounds i64, i64* %a, i64 %i
+ store i64 %i, i64* %scevgep
+ %i.dec = add nsw i64 %i, -1
+ %sub = sub nsw i64 %N, %i
+ %exitcond = icmp ult i64 %sub, 0
+ br i1 %exitcond, label %bb, label %return
+
+return: ; preds = %bb, %entry
+ ret void
+}
diff --git a/polly/test/ScopInfo/unsigned-condition.ll b/polly/test/ScopInfo/unsigned-condition.ll
index 69c815e8cd2..57c1039a495 100644
--- a/polly/test/ScopInfo/unsigned-condition.ll
+++ b/polly/test/ScopInfo/unsigned-condition.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly -polly-scops -analyze -polly-allow-unsigned < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
; void f(int a[], int N, unsigned P) {
; int i;
@@ -7,6 +7,17 @@
; a[i] = i;
; }
+; The assumed context is the universe because the "signed-unsigned assumption"
+; [P, N] -> { : N > 0 and P >= 0 }
+; is implied by the execution domain. Thus if something is executed this
+; assumption will hold.
+
+; CHECK: Assumed Context:
+; CHECK-NEXT: [P, N] -> { : }
+;
+; CHECK: Domain :=
+; CHECK-NEXT: [P, N] -> { Stmt_store[i0] : P >= 42 and 0 <= i0 < N };
+
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 @f(i64* nocapture %a, i64 %N, i64 %P) nounwind {
@@ -31,17 +42,3 @@ bb.backedge:
return:
ret void
}
-
-
-; CHECK: Assumed Context:
-; CHECK-NEXT: [P, N] -> { : }
-;
-; CHECK: Statements {
-; CHECK-NEXT: Stmt_store
-; CHECK-NEXT: Domain :=
-; CHECK-NEXT: [P, N] -> { Stmt_store[i0] : P >= 42 and 0 <= i0 < N };
-; CHECK-NEXT: Schedule :=
-; CHECK-NEXT: [P, N] -> { Stmt_store[i0] -> [i0] };
-; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
-; CHECK-NEXT: [P, N] -> { Stmt_store[i0] -> MemRef_a[i0] };
-; CHECK-NEXT: }
OpenPOWER on IntegriCloud