Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -1530,6 +1530,46 @@ 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. +/// +/// @p IsGreaterThan holds information on the predicate relation between +/// RHS and LHS, i.e, LHS < RHS or LHS <= RHS +static __isl_give isl_set *buildUnsignedConditionSets( + Scop &S, BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain, + const SCEV *SCEV_LHS, const SCEV *SCEV_RHS, + DenseMap &InvalidDomainMap, + bool IsGreaterThan) { + + auto *ICond = dyn_cast(Condition); + assert(ICond && "Condition of exiting branch was neither constant nor ICmp!"); + + // 0 <= LHS < RHS OR 0 <= LHS <= RHS + // But assuming LHS might have MSB set. + isl_pw_aff *LHS = getPwAff(S, BB, InvalidDomainMap, SCEV_LHS, false); + isl_pw_aff *RHS = getPwAff(S, BB, InvalidDomainMap, SCEV_RHS, true); + + // 0 <= LHS + isl_set *First = + isl_pw_aff_ge_set(isl_pw_aff_copy(LHS), + isl_pw_aff_zero_on_domain(isl_local_space_from_space( + isl_pw_aff_get_domain_space(LHS)))); + + isl_set *Second; + if (IsGreaterThan) + // LHS < RHS + Second = isl_pw_aff_gt_set(RHS, LHS); + else + // LHS <= RHS + Second = isl_pw_aff_ge_set(RHS, LHS); + + 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. /// @@ -1584,12 +1624,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); + + switch (ICond->getPredicate()) { + case ICmpInst::ICMP_ULT: + ConsequenceCondSet = buildUnsignedConditionSets( + S, BB, Condition, Domain, SE.getSCEVAtScope(ICond->getOperand(0), L), + SE.getSCEVAtScope(ICond->getOperand(1), L), InvalidDomainMap, true); + break; + case ICmpInst::ICMP_ULE: + ConsequenceCondSet = buildUnsignedConditionSets( + S, BB, Condition, Domain, SE.getSCEVAtScope(ICond->getOperand(0), L), + SE.getSCEVAtScope(ICond->getOperand(1), L), InvalidDomainMap, false); + break; + case ICmpInst::ICMP_UGT: + ConsequenceCondSet = buildUnsignedConditionSets( + S, BB, Condition, Domain, SE.getSCEVAtScope(ICond->getOperand(1), L), + SE.getSCEVAtScope(ICond->getOperand(0), L), InvalidDomainMap, true); + break; + case ICmpInst::ICMP_UGE: + ConsequenceCondSet = buildUnsignedConditionSets( + S, BB, Condition, Domain, SE.getSCEVAtScope(ICond->getOperand(1), L), + SE.getSCEVAtScope(ICond->getOperand(0), L), InvalidDomainMap, false); + break; + default: + 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); + break; + } } // If no terminator was given we are only looking for parameter constraints Index: test/ScopInfo/simple_loop_unsigned.ll =================================================================== --- test/ScopInfo/simple_loop_unsigned.ll +++ 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: test/ScopInfo/unsigned_wrap_uge.ll =================================================================== --- /dev/null +++ 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: test/ScopInfo/unsigned_wrap_ugt.ll =================================================================== --- /dev/null +++ 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: test/ScopInfo/unsigned_wrap_ule.ll =================================================================== --- /dev/null +++ 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: test/ScopInfo/unsigned_wrap_ult.ll =================================================================== --- /dev/null +++ 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: test/ScopInfo/zero_ext_of_truncate.ll =================================================================== --- test/ScopInfo/zero_ext_of_truncate.ll +++ 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: test/ScopInfo/zero_ext_of_truncate_2.ll =================================================================== --- test/ScopInfo/zero_ext_of_truncate_2.ll +++ 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"