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

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

Details

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

Repository
rL LLVM
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

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
1602 ↗(On Diff #106833)

@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
1602 ↗(On Diff #106833)

Example:

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

Crashes with:

polly/lib/External/isl/isl_map.c:3773: spaces don't match

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
1590 ↗(On Diff #106833)

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

1598 ↗(On Diff #106833)

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

[Style] Use inline declarations

1602 ↗(On Diff #106833)

[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.

1613–1628 ↗(On Diff #106833)

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

1622 ↗(On Diff #106833)

[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.

1678 ↗(On Diff #106833)

Please avoid whitespace/unrelated changes.

test/ScopInfo/unsigned_wrap_ugt.ll
36 ↗(On Diff #106833)

[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 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.

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
1538 ↗(On Diff #107257)

[Style] We use @param for documenting parameters.

1543 ↗(On Diff #107257)

[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

1546–1547 ↗(On Diff #107257)

[Style] You can save the assert and use

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

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

1554 ↗(On Diff #107257)

[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.

1563 ↗(On Diff #107257)

[Suggestion] RHS > LHS or use isl_pw_aff_lt_set

1566 ↗(On Diff #107257)

[Suggestion] RHS >= LHS or use isl_pw_aff_le_set

1631 ↗(On Diff #107257)

[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 ↗(On Diff #107257)

This is a nice improvement.

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.

This revision was automatically updated to reflect the committed changes.