Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -1536,6 +1536,47 @@ return true; } +/// Build condition sets for unsigned ICmpInst(s). +/// Special handling is required for unsigned operands to ensure that if +/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst +/// it should wrap around. +/// +/// @param IsStrictUpperBound holds information on the predicate relation +/// between TestVal and UpperBound, i.e, +/// TestVal < UpperBound OR TestVal <= UpperBound +static __isl_give isl_set * +buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition, + __isl_keep isl_set *Domain, const SCEV *SCEV_TestVal, + const SCEV *SCEV_UpperBound, + DenseMap &InvalidDomainMap, + bool IsStrictUpperBound) { + + // Do not take NonNeg assumption on TestVal + // as it might have MSB (Sign bit) set. + isl_pw_aff *TestVal = getPwAff(S, BB, InvalidDomainMap, SCEV_TestVal, false); + // Take NonNeg assumption on UpperBound. + isl_pw_aff *UpperBound = + getPwAff(S, BB, InvalidDomainMap, SCEV_UpperBound, true); + + // 0 <= TestVal + isl_set *First = + isl_pw_aff_le_set(isl_pw_aff_zero_on_domain(isl_local_space_from_space( + isl_pw_aff_get_domain_space(TestVal))), + isl_pw_aff_copy(TestVal)); + + isl_set *Second; + if (IsStrictUpperBound) + // TestVal < UpperBound + Second = isl_pw_aff_lt_set(TestVal, UpperBound); + else + // TestVal <= UpperBound + Second = isl_pw_aff_le_set(TestVal, UpperBound); + + isl_set *ConsequenceCondSet = isl_set_intersect(First, Second); + ConsequenceCondSet = setDimensionIds(Domain, ConsequenceCondSet); + return ConsequenceCondSet; +} + /// Build the conditions sets for the branch condition @p Condition in /// the @p Domain. /// @@ -1590,12 +1631,37 @@ // to be set. The comparison is equal to a signed comparison under this // assumption. bool NonNeg = ICond->isUnsigned(); - LHS = getPwAff(S, BB, InvalidDomainMap, - SE.getSCEVAtScope(ICond->getOperand(0), L), NonNeg); - RHS = getPwAff(S, BB, InvalidDomainMap, - SE.getSCEVAtScope(ICond->getOperand(1), L), NonNeg); - ConsequenceCondSet = - buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain); + const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L), + *RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L); + + switch (ICond->getPredicate()) { + case ICmpInst::ICMP_ULT: + ConsequenceCondSet = + buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand, + RightOperand, InvalidDomainMap, true); + break; + case ICmpInst::ICMP_ULE: + ConsequenceCondSet = + buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand, + RightOperand, InvalidDomainMap, false); + break; + case ICmpInst::ICMP_UGT: + ConsequenceCondSet = + buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand, + LeftOperand, InvalidDomainMap, true); + break; + case ICmpInst::ICMP_UGE: + ConsequenceCondSet = + buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand, + LeftOperand, InvalidDomainMap, false); + break; + default: + LHS = getPwAff(S, BB, InvalidDomainMap, LeftOperand, NonNeg); + RHS = getPwAff(S, BB, InvalidDomainMap, RightOperand, NonNeg); + ConsequenceCondSet = + buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain); + break; + } } // If no terminator was given we are only looking for parameter constraints Index: polly/trunk/test/ScopInfo/simple_loop_unsigned.ll =================================================================== --- polly/trunk/test/ScopInfo/simple_loop_unsigned.ll +++ polly/trunk/test/ScopInfo/simple_loop_unsigned.ll @@ -10,10 +10,10 @@ ; CHECK: Assumed Context: ; CHECK-NEXT: [N] -> { : } ; CHECK-NEXT: Invalid Context: -; CHECK-NEXT: [N] -> { : N < 0 } +; CHECK-NEXT: [N] -> { : 1 = 0 } ; ; CHECK: Domain := -; CHECK-NEXT: [N] -> { Stmt_bb[i0] : 0 <= i0 < N; Stmt_bb[0] : N <= 0 }; +; 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" Index: polly/trunk/test/ScopInfo/simple_loop_unsigned_3.ll =================================================================== --- polly/trunk/test/ScopInfo/simple_loop_unsigned_3.ll +++ polly/trunk/test/ScopInfo/simple_loop_unsigned_3.ll @@ -4,7 +4,7 @@ ; CHECK-NEXT: [N] -> { : } ; ; CHECK: Domain := -; CHECK-NEXT: [N] -> { Stmt_bb[i0] : 0 < i0 <= 1000 - N; Stmt_bb[0] }; +; CHECK-NEXT: [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" Index: polly/trunk/test/ScopInfo/unsigned_wrap_uge.ll =================================================================== --- polly/trunk/test/ScopInfo/unsigned_wrap_uge.ll +++ polly/trunk/test/ScopInfo/unsigned_wrap_uge.ll @@ -0,0 +1,46 @@ +; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s +; +; Unsigned wrap-around check. +; +; for (int i = -1; i < 65 ; i ++ ) +; if ( 63 >= (unsigned)i ) +; A[i] = 42; + + +define void @func(double* noalias nonnull %A) { +entry: + br label %for + + for: + %j = phi i32 [-1, %entry], [%j.inc, %inc] + %j.cmp = icmp slt i32 %j, 65 + br i1 %j.cmp, label %body, label %exit + + body: + %inbounds = icmp uge i32 63, %j + br i1 %inbounds, label %ifinbounds, label %ifoutbounds + + ifinbounds: + %A_idx = getelementptr inbounds double, double* %A, i32 %j + store double 42.0, double* %A_idx + br label %inc + + ifoutbounds: + br label %inc + + inc: + %j.inc = add nuw nsw i32 %j, 1 + br label %for + + exit: + br label %return + + return: + ret void +} + + +; CHECK: Region: %for---%return +; CHECK: Domain := +; CHECK-NEXT: { Stmt_ifinbounds[i0] : 0 < i0 <= 64 }; + Index: polly/trunk/test/ScopInfo/unsigned_wrap_ugt.ll =================================================================== --- polly/trunk/test/ScopInfo/unsigned_wrap_ugt.ll +++ polly/trunk/test/ScopInfo/unsigned_wrap_ugt.ll @@ -0,0 +1,46 @@ +; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s +; +; Unsigned wrap-around check. +; +; for (int i = -1; i < 65 ; i ++ ) +; if ( 64 > (unsigned)i ) +; A[i] = 42; + + +define void @func(double* noalias nonnull %A) { +entry: + br label %for + + for: + %j = phi i32 [-1, %entry], [%j.inc, %inc] + %j.cmp = icmp slt i32 %j, 65 + br i1 %j.cmp, label %body, label %exit + + body: + %inbounds = icmp ugt i32 64, %j + br i1 %inbounds, label %ifinbounds, label %ifoutbounds + + ifinbounds: + %A_idx = getelementptr inbounds double, double* %A, i32 %j + store double 42.0, double* %A_idx + br label %inc + + ifoutbounds: + br label %inc + + inc: + %j.inc = add nuw nsw i32 %j, 1 + br label %for + + exit: + br label %return + + return: + ret void +} + + +; CHECK: Region: %for---%return +; CHECK: Domain := +; CHECK-NEXT: { Stmt_ifinbounds[i0] : 0 < i0 <= 64 }; + Index: polly/trunk/test/ScopInfo/unsigned_wrap_ule.ll =================================================================== --- polly/trunk/test/ScopInfo/unsigned_wrap_ule.ll +++ polly/trunk/test/ScopInfo/unsigned_wrap_ule.ll @@ -0,0 +1,46 @@ +; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s +; +; Unsigned wrap-around check. +; +; for (int i = -1; i < 65 ; i ++ ) +; if ( (unsigned)i <= 63 ) +; A[i] = 42; + + +define void @func(double* noalias nonnull %A) { +entry: + br label %for + + for: + %j = phi i32 [-1, %entry], [%j.inc, %inc] + %j.cmp = icmp slt i32 %j, 65 + br i1 %j.cmp, label %body, label %exit + + body: + %inbounds = icmp ule i32 %j, 63 + br i1 %inbounds, label %ifinbounds, label %ifoutbounds + + ifinbounds: + %A_idx = getelementptr inbounds double, double* %A, i32 %j + store double 42.0, double* %A_idx + br label %inc + + ifoutbounds: + br label %inc + + inc: + %j.inc = add nuw nsw i32 %j, 1 + br label %for + + exit: + br label %return + + return: + ret void +} + + +; CHECK: Region: %for---%return +; CHECK: Domain := +; CHECK-NEXT: { Stmt_ifinbounds[i0] : 0 < i0 <= 64 }; + Index: polly/trunk/test/ScopInfo/unsigned_wrap_ult.ll =================================================================== --- polly/trunk/test/ScopInfo/unsigned_wrap_ult.ll +++ polly/trunk/test/ScopInfo/unsigned_wrap_ult.ll @@ -0,0 +1,46 @@ +; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s +; +; Unsigned wrap-around check. +; +; for (int i = -1; i < 65 ; i ++ ) +; if ( (unsigned)i < 64 ) +; A[i] = 42; + + +define void @func(double* noalias nonnull %A) { +entry: + br label %for + + for: + %j = phi i32 [-1, %entry], [%j.inc, %inc] + %j.cmp = icmp slt i32 %j, 65 + br i1 %j.cmp, label %body, label %exit + + body: + %inbounds = icmp ult i32 %j, 64 + br i1 %inbounds, label %ifinbounds, label %ifoutbounds + + ifinbounds: + %A_idx = getelementptr inbounds double, double* %A, i32 %j + store double 42.0, double* %A_idx + br label %inc + + ifoutbounds: + br label %inc + + inc: + %j.inc = add nuw nsw i32 %j, 1 + br label %for + + exit: + br label %return + + return: + ret void +} + + +; CHECK: Region: %for---%return +; CHECK: Domain := +; CHECK-NEXT: { Stmt_ifinbounds[i0] : 0 < i0 <= 64 }; + Index: polly/trunk/test/ScopInfo/zero_ext_of_truncate.ll =================================================================== --- polly/trunk/test/ScopInfo/zero_ext_of_truncate.ll +++ polly/trunk/test/ScopInfo/zero_ext_of_truncate.ll @@ -16,7 +16,7 @@ ; CHECK-NEXT: [N, tmp, M] -> { : N < 0 or (N > 0 and tmp >= 128) or (N > 0 and tmp < 0) or (N > 0 and M < 0) } ; ; CHECK: Domain := -; CHECK-NEXT: [N, tmp, M] -> { Stmt_if_then[i0] : M > tmp and 0 <= i0 < N }; +; CHECK-NEXT: [N, tmp, M] -> { Stmt_if_then[i0] : tmp >= 0 and M > tmp and 0 <= i0 < N }; ; target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" Index: polly/trunk/test/ScopInfo/zero_ext_of_truncate_2.ll =================================================================== --- polly/trunk/test/ScopInfo/zero_ext_of_truncate_2.ll +++ polly/trunk/test/ScopInfo/zero_ext_of_truncate_2.ll @@ -15,7 +15,7 @@ ; CHECK-NEXT: [N, tmp] -> { : N > 0 and (tmp < 0 or tmp >= 2147483648) } ; ; CHECK: Domain := -; CHECK-NEXT: [N, tmp] -> { Stmt_if_then[i0] : i0 > tmp and 0 <= i0 < N }; +; CHECK-NEXT: [N, tmp] -> { Stmt_if_then[i0] : tmp >= 0 and tmp < i0 < N }; ; target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"