This is an archive of the discontinued LLVM Phabricator instance.

Differential D35464

[Polly][ScopInfo] Add support for wrap-around of integers in unsigned comparisons
ClosedPublic

Authored by annanay25 on Jul 16 2017, 1:14 PM.

Details

Reviewers
Meinersbur
grosser
bollu
Commits
rG0865585eabeb: [ScopInfo] Add support for wrap-around of integers in unsigned comparisons.
rPLO308608: [ScopInfo] Add support for wrap-around of integers in unsigned comparisons.
rL308608: [ScopInfo] Add support for wrap-around of integers in unsigned comparisons.
Summary

This is one possible solution to implement wrap-arounds for integers in unsigned icmp operations. For example,

store i32 -1, i32* %A_addr
%0 = load i32, i32* %A_addr
%1 = icmp ult i32 %0, 0

%1 should hold false, because under the assumption of unsigned integers, -1 should wrap around to 2^32-1. However, previously. it was assumed that the MSB (Most Significant Bit - aka the Sign bit) was never set for integers in unsigned operations.

This patch modifies the buildConditionSets function in ScopInfo.cpp to give better information about the integers in these unsigned comparisons.

Diff Detail

Event Timeline

annanay25 created this revision.Jul 16 2017, 1:14 PM

List of failing tests:

Failing Tests (12):
    Polly :: Isl/CodeGen/20101103-signmissmatch.ll
    Polly :: Isl/CodeGen/ptrtoint_as_parameter.ll
    Polly :: Isl/CodeGen/two-scops-in-row-invalidate-scevs.ll
    Polly :: ScopInfo/complex_domain_binary_condition.ll
    Polly :: ScopInfo/long-compile-time-alias-analysis.ll
    Polly :: ScopInfo/run-time-check-many-array-disjuncts.ll
    Polly :: ScopInfo/simple_loop_unsigned.ll
    Polly :: ScopInfo/simple_loop_unsigned_2.ll
    Polly :: ScopInfo/simple_loop_unsigned_3.ll
    Polly :: ScopInfo/unsigned-condition.ll
    Polly :: ScopInfo/zero_ext_of_truncate.ll
    Polly :: ScopInfo/zero_ext_of_truncate_2.ll

  Expected Passes    : 885
  Expected Failures  : 11
  Unsupported Tests  : 43
  Unexpected Failures: 12
annanay25 updated this revision to Diff 106833.Jul 16 2017, 10:24 PM

Update: isl object handling.

Now-

Failing Tests (8):
    Polly :: Isl/CodeGen/20101103-signmissmatch.ll
    Polly :: Isl/CodeGen/ptrtoint_as_parameter.ll
    Polly :: ScopInfo/long-compile-time-alias-analysis.ll
    Polly :: ScopInfo/run-time-check-many-array-disjuncts.ll
    Polly :: ScopInfo/simple_loop_unsigned.ll
    Polly :: ScopInfo/simple_loop_unsigned_3.ll
    Polly :: ScopInfo/zero_ext_of_truncate.ll
    Polly :: ScopInfo/zero_ext_of_truncate_2.ll

  Expected Passes    : 890
  Expected Failures  : 11
  Unsupported Tests  : 43
  Unexpected Failures: 8
annanay25 retitled this revision from [Polly] Add support for wrap-around of integers in unsigned comparisons to [Polly][WIP] Add support for wrap-around of integers in unsigned comparisons.Jul 16 2017, 11:09 PM
annanay25 edited the summary of this revision. (Show Details)
annanay25 added inline comments.Jul 16 2017, 11:14 PM
lib/Analysis/ScopInfo.cpp
1649

@Meinersbur ;

One bug that I did not consider. Since LHS can have multiple dimensions, I cannot assume a _unit_ dimension in isl_pw_aff_read_from_str() as the spaces would then be incompatible.

annanay25 added inline comments.Jul 16 2017, 11:24 PM
lib/Analysis/ScopInfo.cpp
1649

Example:

isl_pw_aff_dump(LHS)
{ [i0, i1] -> [(28)] }

Crashes with:

polly/lib/External/isl/isl_map.c:3773: spaces don't match
Meinersbur edited edge metadata.Jul 17 2017, 5:16 AM

Thanks for the patch. This is what I had in mind. Tests still fail, though.

Can you make a test for all of the 4 cases? Shouldn't be difficult.

How did you make the diff? I cannot directly apply it because the tests are not marked as new files.

lib/Analysis/ScopInfo.cpp
1637

[Style] For that many if-cases, you case use a switch instead.

1645

[Style] In LLVM's coding style, local variable start with an upper case letter.

[Style] Use inline declarations

1649

[Serious] Do not create isl sets from string. You need the correct space: The one one LHS (isl_pw_aff_get_space). To create an pw_aff for 0, there is isl_pw_aff_zero_on_domain.

1660–1675

[Suggestion] Extract the common code into a function with parameter(s) for the case.

1669

[Style] We usually don have post-line comments, it makes the line longer with an already strict 80 column limit and clang-format doesn't make them look nice.

1725

Please avoid whitespace/unrelated changes.

test/ScopInfo/unsigned_wrap_ugt.ll
37

[Suggestion] Check for the domain of ifinbounds which should be something like 0 <= %j < 64.

Some comment in the test for what it is supposed to test would be nice.

annanay25 marked 9 inline comments as done.Jul 19 2017, 12:39 AM
annanay25 updated this revision to Diff 107257.Jul 19 2017, 12:43 AM
annanay25 retitled this revision from [Polly][WIP] Add support for wrap-around of integers in unsigned comparisons to [Polly][ScopInfo] Add support for wrap-around of integers in unsigned comparisons.

Addressed comments.

Currently -

Failing Tests (1):
    Polly :: ScopInfo/simple_loop_unsigned_3.ll

I think there is something fishy with this test case -

The exitcond in the test case is -

%exitcond = icmp ult i64 %sub, 0
br i1 %exitcond, label %bb, label %return

Which should essentially give an empty domain.

Meinersbur added a comment.Jul 19 2017, 5:29 AM

simple_loop_unsigned_3.ll has one iteration only: It resembles a do-while loop, therefore is executed exactly once since the exit condition is a tautology.

The correct domain therefore is [N] -> { Stmt_bb[0] } as you code correctly returns.

The code in you summary:

store i32 -1, %0
%1 = icmp ult i32 %0, 0

does not make sense (cannot store to %0 which is not a pointer). Can you revise it?

lib/Analysis/ScopInfo.cpp
1544

[Style] We use @param for documenting parameters.

1549

[Serious] InvalidDomainMap was updated to use isl C++ bindings. It now should be DenseMap<BasicBlock *, isl::set>. Please update to the latest trunk version of Polly.

[Style] Try to use variable names that are more abstract than what they were used. "SCEV_RHS" is not necessarily the right-hand-side. IsGreaterThan is implementation-specific.
Suggestions:
LHS => TestVal
RHS => UpperBound
IsGreaterThan => IsStrictUpperBound

1552–1553

[Style] You can save the assert and use

auto *ICond = cast<ICmpInst>(Condition);

The cast never returns null and checks that with an assert.

1560

[Suggestion] It would be slightly less confusing if the comment was using the "ge" operator and the order LHS/RHS are used below: LHS >= 0. Alternatively, you case use isl_pw_aff_le_set.

1569

[Suggestion] RHS > LHS or use isl_pw_aff_lt_set

1572

[Suggestion] RHS >= LHS or use isl_pw_aff_le_set

1638

[Style] Store SE.getSCEVAtScope(ICond->getOperand(0), L) and SE.getSCEVAtScope(ICond->getOperand(1), L) in a variable before the swtich. It is used in all cases.

test/ScopInfo/simple_loop_unsigned.ll
13

This is a nice improvement.

Meinersbur added a comment.Jul 19 2017, 5:29 AM

simple_loop_unsigned_3.ll has one iteration only: It resembles a do-while loop, therefore is executed exactly once since the exit condition is a tautology.

The correct domain therefore is [N] -> { Stmt_bb[0] } as you code correctly returns.

The code in you summary:

store i32 -1, %0
%1 = icmp ult i32 %0, 0

does not make sense (cannot store to %0 which is not a pointer). Can you revise it?

annanay25 marked 8 inline comments as done.Jul 19 2017, 9:52 PM
annanay25 updated this revision to Diff 107441.Jul 19 2017, 9:58 PM
annanay25 edited the summary of this revision. (Show Details)

Addressed comments.

@Meinersbur Please let me know of any changes to be made.

Closed by commit rL308608: [ScopInfo] Add support for wrap-around of integers in unsigned comparisons. (authored by Meinersbur). · Explain WhyJul 20 2017, 5:39 AM
This revision was automatically updated to reflect the committed changes.
Meinersbur added a comment.Jul 20 2017, 10:21 AM

Thank you.

Revision Contents

Diff 107441

lib/Analysis/ScopInfo.cpp

Show First 20 Lines • Show All 1,530 Lines • ▼ Show 20 LinesbuildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L,
ConditionSets[0] = setDimensionIds( ConditionSets[0] = setDimensionIds(
Domain, isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion)); Domain, isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion));
isl_pw_aff_free(LHS); isl_pw_aff_free(LHS);
return true; 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
MeinersburUnsubmitted
Done
ReplyInline Actions

[Style] We use @param for documenting parameters.

Meinersbur: [Style] We use `@param` for documenting parameters.
/// 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,
MeinersburUnsubmitted
Done
ReplyInline Actions

[Serious] InvalidDomainMap was updated to use isl C++ bindings. It now should be DenseMap<BasicBlock *, isl::set>. Please update to the latest trunk version of Polly.

[Style] Try to use variable names that are more abstract than what they were used. "SCEV_RHS" is not necessarily the right-hand-side. IsGreaterThan is implementation-specific.
Suggestions:
LHS => TestVal
RHS => UpperBound
IsGreaterThan => IsStrictUpperBound

Meinersbur: [Serious] `InvalidDomainMap` was updated to use isl C++ bindings. It now should be `…
const SCEV *SCEV_UpperBound,
DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
bool IsStrictUpperBound) {
MeinersburUnsubmitted
Done
ReplyInline Actions

[Style] You can save the assert and use

auto *ICond = cast<ICmpInst>(Condition);

The cast never returns null and checks that with an assert.

Meinersbur: [Style] You can save the assert and use ``` auto *ICond = cast<ICmpInst>(Condition); ``` The…
// 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);
MeinersburUnsubmitted
Done
ReplyInline Actions

[Suggestion] It would be slightly less confusing if the comment was using the "ge" operator and the order LHS/RHS are used below: LHS >= 0. Alternatively, you case use isl_pw_aff_le_set.

Meinersbur: [Suggestion] It would be slightly less confusing if the comment was using the "ge" operator and…
// 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
MeinersburUnsubmitted
Done
ReplyInline Actions

[Suggestion] RHS > LHS or use isl_pw_aff_lt_set

Meinersbur: [Suggestion] `RHS > LHS` or use `isl_pw_aff_lt_set`
Second = isl_pw_aff_lt_set(TestVal, UpperBound);
else
// TestVal <= UpperBound
MeinersburUnsubmitted
Done
ReplyInline Actions

[Suggestion] RHS >= LHS or use isl_pw_aff_le_set

Meinersbur: [Suggestion] `RHS >= LHS` or use `isl_pw_aff_le_set`
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 /// Build the conditions sets for the branch condition @p Condition in
/// the @p Domain. /// the @p Domain.
/// ///
/// This will fill @p ConditionSets with the conditions under which control /// This will fill @p ConditionSets with the conditions under which control
/// will be moved from @p TI to its successors. Hence, @p ConditionSets will /// will be moved from @p TI to its successors. Hence, @p ConditionSets will
/// have as many elements as @p TI has successors. If @p TI is nullptr the /// have as many elements as @p TI has successors. If @p TI is nullptr the
/// context under which @p Condition is true/false will be returned as the /// context under which @p Condition is true/false will be returned as the
/// new elements of @p ConditionSets. /// new elements of @p ConditionSets.
Show All 38 Lines assert(ICond &&
"Condition of exiting branch was neither constant nor ICmp!"); "Condition of exiting branch was neither constant nor ICmp!");
ScalarEvolution &SE = *S.getSE(); ScalarEvolution &SE = *S.getSE();
isl_pw_aff *LHS, *RHS; isl_pw_aff *LHS, *RHS;
// For unsigned comparisons we assumed the signed bit of neither operand // For unsigned comparisons we assumed the signed bit of neither operand
// to be set. The comparison is equal to a signed comparison under this // to be set. The comparison is equal to a signed comparison under this
// assumption. // assumption.
bool NonNeg = ICond->isUnsigned(); bool NonNeg = ICond->isUnsigned();
LHS = getPwAff(S, BB, InvalidDomainMap, const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L),
SE.getSCEVAtScope(ICond->getOperand(0), L), NonNeg); *RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L);
RHS = getPwAff(S, BB, InvalidDomainMap,
SE.getSCEVAtScope(ICond->getOperand(1), L), NonNeg); switch (ICond->getPredicate()) {
MeinersburUnsubmitted
Done
ReplyInline Actions

[Style] For that many if-cases, you case use a switch instead.

Meinersbur: [Style] For that many if-cases, you case use a `switch` instead.
case ICmpInst::ICMP_ULT:
MeinersburUnsubmitted
Done
ReplyInline Actions

[Style] Store SE.getSCEVAtScope(ICond->getOperand(0), L) and SE.getSCEVAtScope(ICond->getOperand(1), L) in a variable before the swtich. It is used in all cases.

Meinersbur: [Style] Store `SE.getSCEVAtScope(ICond->getOperand(0), L)` and `SE.getSCEVAtScope(ICond…
ConsequenceCondSet =
buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
RightOperand, InvalidDomainMap, true);
break;
case ICmpInst::ICMP_ULE:
ConsequenceCondSet =
buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
MeinersburUnsubmitted
Done
ReplyInline Actions

[Style] In LLVM's coding style, local variable start with an upper case letter.

[Style] Use inline declarations

Meinersbur: [Style] In LLVM's coding style, local variable start with an upper case letter. [Style] Use…
RightOperand, InvalidDomainMap, false);
break;
case ICmpInst::ICMP_UGT:
ConsequenceCondSet =
annanay25AuthorUnsubmitted
Done
ReplyInline Actions

@Meinersbur ;

One bug that I did not consider. Since LHS can have multiple dimensions, I cannot assume a _unit_ dimension in isl_pw_aff_read_from_str() as the spaces would then be incompatible.

annanay25: @Meinersbur ; One bug that I did not consider. Since `LHS` can have multiple dimensions, I…
annanay25AuthorUnsubmitted
Done
ReplyInline Actions

Example:

isl_pw_aff_dump(LHS)
{ [i0, i1] -> [(28)] }

Crashes with:

polly/lib/External/isl/isl_map.c:3773: spaces don't match
annanay25: Example: ``` isl_pw_aff_dump(LHS) { [i0, i1] -> [(28)] } ``` Crashes with: ```…
MeinersburUnsubmitted
Done
ReplyInline Actions

[Serious] Do not create isl sets from string. You need the correct space: The one one LHS (isl_pw_aff_get_space). To create an pw_aff for 0, there is isl_pw_aff_zero_on_domain.

Meinersbur: [Serious] Do not create isl sets from string. You need the correct space: The one one LHS…
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 = ConsequenceCondSet =
buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain); buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain);
break;
}
} }
// If no terminator was given we are only looking for parameter constraints // If no terminator was given we are only looking for parameter constraints
// under which @p Condition is true/false. // under which @p Condition is true/false.
if (!TI) if (!TI)
MeinersburUnsubmitted
Done
ReplyInline Actions

[Style] We usually don have post-line comments, it makes the line longer with an already strict 80 column limit and clang-format doesn't make them look nice.

Meinersbur: [Style] We usually don have post-line comments, it makes the line longer with an already strict…
ConsequenceCondSet = isl_set_params(ConsequenceCondSet); ConsequenceCondSet = isl_set_params(ConsequenceCondSet);
assert(ConsequenceCondSet); assert(ConsequenceCondSet);
ConsequenceCondSet = isl_set_coalesce( ConsequenceCondSet = isl_set_coalesce(
isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain))); isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain)));
isl_set *AlternativeCondSet = nullptr; isl_set *AlternativeCondSet = nullptr;
MeinersburUnsubmitted
Done
ReplyInline Actions

[Suggestion] Extract the common code into a function with parameter(s) for the case.

Meinersbur: [Suggestion] Extract the common code into a function with parameter(s) for the case.
bool TooComplex = bool TooComplex =
isl_set_n_basic_set(ConsequenceCondSet) >= MaxDisjunctsInDomain; isl_set_n_basic_set(ConsequenceCondSet) >= MaxDisjunctsInDomain;
if (!TooComplex) { if (!TooComplex) {
AlternativeCondSet = isl_set_subtract(isl_set_copy(Domain), AlternativeCondSet = isl_set_subtract(isl_set_copy(Domain),
isl_set_copy(ConsequenceCondSet)); isl_set_copy(ConsequenceCondSet));
TooComplex = TooComplex =
isl_set_n_basic_set(AlternativeCondSet) >= MaxDisjunctsInDomain; isl_set_n_basic_set(AlternativeCondSet) >= MaxDisjunctsInDomain;
Show All 33 LinesbuildConditionSets(Scop &S, BasicBlock *BB, TerminatorInst *TI, Loop *L,
if (TI->getNumSuccessors() == 1) { if (TI->getNumSuccessors() == 1) {
ConditionSets.push_back(isl_set_copy(Domain)); ConditionSets.push_back(isl_set_copy(Domain));
return true; return true;
} }
Value *Condition = getConditionFromTerminator(TI); Value *Condition = getConditionFromTerminator(TI);
assert(Condition && "No condition for Terminator"); assert(Condition && "No condition for Terminator");
return buildConditionSets(S, BB, Condition, TI, L, Domain, InvalidDomainMap, return buildConditionSets(S, BB, Condition, TI, L, Domain, InvalidDomainMap,
MeinersburUnsubmitted
Done
ReplyInline Actions

Please avoid whitespace/unrelated changes.

Meinersbur: Please avoid whitespace/unrelated changes.
ConditionSets); ConditionSets);
} }
void ScopStmt::buildDomain() { void ScopStmt::buildDomain() {
isl_id *Id = isl_id_alloc(getIslCtx(), getBaseName(), this); isl_id *Id = isl_id_alloc(getIslCtx(), getBaseName(), this);
Domain = getParent()->getDomainConditions(this); Domain = getParent()->getDomainConditions(this);
Domain = isl_set_set_tuple_id(Domain, Id); Domain = isl_set_set_tuple_id(Domain, Id);
▲ Show 20 Lines • Show All 3,531 Lines • Show Last 20 Lines

test/ScopInfo/simple_loop_unsigned.ll

; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
; void f(int a[], unsigned N) { ; void f(int a[], unsigned N) {
; unsigned i; ; unsigned i;
; do { ; do {
; a[i] = i; ; a[i] = i;
; } while (++i <= N); ; } while (++i <= N);
; } ; }
; CHECK: Assumed Context: ; CHECK: Assumed Context:
; CHECK-NEXT: [N] -> { : } ; CHECK-NEXT: [N] -> { : }
; CHECK-NEXT: Invalid Context: ; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: [N] -> { : N < 0 } ; CHECK-NEXT: [N] -> { : 1 = 0 }
MeinersburUnsubmitted
Done
ReplyInline Actions

This is a nice improvement.

Meinersbur: This is a nice improvement.
; ;
; CHECK: Domain := ; 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" 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 { define void @f(i64* nocapture %a, i64 %N) nounwind {
entry: entry:
br label %bb br label %bb
bb: ; preds = %bb, %entry bb: ; preds = %bb, %entry
Show All 10 Lines

test/ScopInfo/simple_loop_unsigned_3.ll

; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
; CHECK: Assumed Context: ; CHECK: Assumed Context:
; CHECK-NEXT: [N] -> { : } ; CHECK-NEXT: [N] -> { : }
; ;
; CHECK: Domain := ; 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" 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 { define void @f(i64* nocapture %a, i64 %N) nounwind {
entry: entry:
br label %bb br label %bb
bb: ; preds = %bb, %entry bb: ; preds = %bb, %entry
Show All 11 Lines

test/ScopInfo/unsigned_wrap_uge.ll

  • This file was added.
; 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 };

test/ScopInfo/unsigned_wrap_ugt.ll

  • This file was added.
; 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
MeinersburUnsubmitted
Done
ReplyInline Actions

[Suggestion] Check for the domain of ifinbounds which should be something like 0 <= %j < 64.

Some comment in the test for what it is supposed to test would be nice.

Meinersbur: [Suggestion] Check for the domain of `ifinbounds` which should be something like `0 <= %j < 64`.
return:
ret void
}
; CHECK: Region: %for---%return
; CHECK: Domain :=
; CHECK-NEXT: { Stmt_ifinbounds[i0] : 0 < i0 <= 64 };

test/ScopInfo/unsigned_wrap_ule.ll

  • This file was added.
; 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 };

test/ScopInfo/unsigned_wrap_ult.ll

  • This file was added.
; 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 };

test/ScopInfo/zero_ext_of_truncate.ll

Show All 10 Lines
; ;
; FIXME: The truncated value should be a paramter. ; FIXME: The truncated value should be a paramter.
; CHECK: Assumed Context: ; CHECK: Assumed Context:
; CHECK-NEXT: [N, tmp, M] -> { : } ; CHECK-NEXT: [N, tmp, M] -> { : }
; CHECK-NEXT: Invalid Context: ; CHECK-NEXT: Invalid Context:
; 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-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: 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" target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
define void @f(i32* noalias %I, i32* noalias %A, i32 %N, i32 %M) { define void @f(i32* noalias %I, i32* noalias %A, i32 %N, i32 %M) {
entry: entry:
br label %for.cond br label %for.cond
for.cond: ; preds = %for.inc, %entry for.cond: ; preds = %for.inc, %entry
Show All 28 Lines

test/ScopInfo/zero_ext_of_truncate_2.ll

Show All 9 Lines
; } ; }
; ;
; CHECK: Assumed Context: ; CHECK: Assumed Context:
; CHECK-NEXT: [N, tmp] -> { : } ; CHECK-NEXT: [N, tmp] -> { : }
; CHECK-NEXT: Invalid Context: ; CHECK-NEXT: Invalid Context:
; CHECK-NEXT: [N, tmp] -> { : N > 0 and (tmp < 0 or tmp >= 2147483648) } ; CHECK-NEXT: [N, tmp] -> { : N > 0 and (tmp < 0 or tmp >= 2147483648) }
; ;
; CHECK: Domain := ; 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" target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
define void @f(i64* noalias %I, i32* noalias %A, i32 %N, i32 %M) { define void @f(i64* noalias %I, i32* noalias %A, i32 %N, i32 %M) {
entry: entry:
br label %for.cond br label %for.cond
for.cond: ; preds = %for.inc, %entry for.cond: ; preds = %for.inc, %entry
Show All 29 Lines