Index: include/polly/ScopDetectionDiagnostic.h =================================================================== --- include/polly/ScopDetectionDiagnostic.h +++ include/polly/ScopDetectionDiagnostic.h @@ -68,7 +68,6 @@ rrkAffFunc, rrkUndefCond, rrkInvalidCond, - rrkUnsignedCond, rrkUndefOperand, rrkNonAffBranch, rrkNoBasePtr, @@ -346,32 +345,6 @@ }; //===----------------------------------------------------------------------===// -/// @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 { //===--------------------------------------------------------------------===// Index: lib/Analysis/ScopDetection.cpp =================================================================== --- lib/Analysis/ScopDetection.cpp +++ lib/Analysis/ScopDetection.cpp @@ -149,11 +149,6 @@ cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory)); -static cl::opt AllowUnsigned("polly-allow-unsigned", - cl::desc("Allow unsigned expressions"), - cl::Hidden, cl::init(false), cl::ZeroOrMore, - cl::cat(PollyCategory)); - static cl::opt TrackFailures("polly-detect-track-failures", cl::desc("Track failure strings in detecting scop regions"), @@ -385,13 +380,6 @@ } ICmpInst *ICmp = cast(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(Context, /*Assert=*/true, BI, &BB); // Are both operands of the ICmp affine? if (isa(ICmp->getOperand(0)) || Index: lib/Analysis/ScopDetectionDiagnostic.cpp =================================================================== --- lib/Analysis/ScopDetectionDiagnostic.cpp +++ lib/Analysis/ScopDetectionDiagnostic.cpp @@ -196,22 +196,6 @@ } //===----------------------------------------------------------------------===// -// 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 { Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -1317,6 +1317,15 @@ 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()) { + 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); } Index: test/ScopInfo/simple_loop_unsigned.ll =================================================================== --- /dev/null +++ test/ScopInfo/simple_loop_unsigned.ll @@ -0,0 +1,42 @@ +; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s + +; void f(int a[], int N) { +; int i; +; for (i = 0; i < N; ++i) +; a[i] = i; +; } + +; CHECK: Assumed Context: +; CHECK-NEXT: [N] -> { : N >= 0 } +; +; CHECK: Arrays { +; CHECK-NEXT: i64 MemRef_a[*]; // Element size 8 +; CHECK-NEXT: } +; +; CHECK: Statements { +; CHECK-NEXT: Stmt_bb +; CHECK-NEXT: Domain := +; CHECK-NEXT: [N] -> { Stmt_bb[i0] : 0 <= i0 < N; Stmt_bb[0] : N <= 0 }; +; CHECK-NEXT: Schedule := +; CHECK-NEXT: [N] -> { Stmt_bb[i0] -> [i0] : i0 < N; Stmt_bb[0] -> [0] : N <= 0 }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_bb[i0] -> MemRef_a[i0] }; +; CHECK-NEXT: } + +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 +} Index: test/ScopInfo/simple_loop_unsigned_2.ll =================================================================== --- /dev/null +++ test/ScopInfo/simple_loop_unsigned_2.ll @@ -0,0 +1,42 @@ +; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s + +; void f(int a[], unsigned N) { +; unsigned i; +; for (i = N; i > 0; --i) +; a[i] = i; +; } + +; CHECK: Assumed Context: +; CHECK-NEXT: [N] -> { : N > 0 } +; +; CHECK: Arrays { +; CHECK-NEXT: i64 MemRef_a[*]; // Element size 8 +; CHECK-NEXT: } +; +; CHECK: Statements { +; CHECK-NEXT: Stmt_bb +; CHECK-NEXT: Domain := +; CHECK-NEXT: [N] -> { Stmt_bb[i0] : 0 <= i0 < N; Stmt_bb[0] : N <= 0 }; +; CHECK-NEXT: Schedule := +; CHECK-NEXT: [N] -> { Stmt_bb[i0] -> [i0] : i0 < N; Stmt_bb[0] -> [0] : N <= 0 }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_bb[i0] -> MemRef_a[N - i0] }; +; CHECK-NEXT: } + +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 +} Index: test/ScopInfo/simple_loop_unsigned_3.ll =================================================================== --- /dev/null +++ test/ScopInfo/simple_loop_unsigned_3.ll @@ -0,0 +1,45 @@ +; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s + +; void f(int a[], unsigned N) { +; unsigned i; +; for (i = 1000; N - i < 0; --i) +; a[i] = i; +; } + +; CHECK: Assumed Context: +; CHECK-NEXT: [N] -> { : } +; CHECK: Invalid Context: +; CHECK-NEXT: [N] -> { : N <= -9223372036854774808 } +; +; CHECK: Arrays { +; CHECK-NEXT: i64 MemRef_a[*]; // Element size 8 +; CHECK-NEXT: } +; +; CHECK: Statements { +; CHECK-NEXT: Stmt_bb +; CHECK-NEXT: Domain := +; CHECK-NEXT: [N] -> { Stmt_bb[i0] : 0 < i0 <= 1000 - N; Stmt_bb[0] }; +; CHECK-NEXT: Schedule := +; CHECK-NEXT: [N] -> { Stmt_bb[i0] -> [i0] : 0 < i0 <= 1000 - N; Stmt_bb[0] -> [0] }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_bb[i0] -> MemRef_a[1000 - i0] }; +; CHECK-NEXT: } + +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 +} Index: test/ScopInfo/unsigned-condition.ll =================================================================== --- test/ScopInfo/unsigned-condition.ll +++ 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,24 @@ ; 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: 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: } + 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 +49,3 @@ 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: }