This is an archive of the discontinued LLVM Phabricator instance.

[Unfinished] Use modulo semantic to generate non-wrap assumptions
ClosedPublic

Authored by jdoerfert on Apr 19 2015, 11:46 AM.

Details

Summary

This will allow to generate non-wrap assumptions for memory accesess.
We compare the old isl representation of the access functions with
the one computed with modulo semantic.

Notes:

  • We will use all range information for parameters (even full ranges) to simplify the assumptions.
  • We will respect the nsw flags when computing the modulo representation.

Some but not all test cases have been adjusted.

Diff Detail

Event Timeline

jdoerfert updated this revision to Diff 23995.Apr 19 2015, 11:46 AM
jdoerfert retitled this revision from to [Unfinished] Use modulo semantic to generate non-wrap assumptions.
jdoerfert updated this object.
jdoerfert edited the test plan for this revision. (Show Details)
jdoerfert added subscribers: Restricted Project, Unknown Object (MLST).
grosser edited edge metadata.Apr 19 2015, 3:18 PM

Hi Johannes,

this patch looks already great. I its overall structure and only have a couple of minor comments (see below).

We may also want to add a test case A[128 * p] to test the modulo path.

Best,
Tobias

lib/Analysis/ScopInfo.cpp
94–97

indicate

108

Why do you call this function 'NonWrap'? Is the point of this function not to add the integer wrapping? Could a name like 'addIntegerWrapping()' be a better fit?

131

UseModulo (start with uppercase)

143

A comment explaining how we implement the modulo of signed types might be helpful.

res = ((res + 2^7) mod (2 ^ 8)) - 2^7

144

Leftover.

147

Leftover.

278

This assert now fires for a couple of test cases, e.g. :
test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll

296

It seems you used this change remove the special case of isZero(). This special-case-removal seems partially unrelated. Maybe you want to commit this cleanup ahead of time (no review needed).

test/ScopInfo/simple_loop_1.ll
18

Not necessary, but if you commit these changes separately (no review required), we can see that most of the time we have indeed sufficient nsw information.

test/ScopInfo/wraping_signed_expr_1.ll
22

The C code uses chars, but here %N and %p are i64. Is this intended? I would actually prefer a version using 'char' to see bounds that are easier to understand.

32

Would it make sense to add a version that lacks the 'nsw' flag here?

test/ScopInfo/wraping_signed_expr_1_long.ll
21 ↗(On Diff #23995)

char <> i64 mismatch

test/ScopInfo/wraping_signed_expr_5.ll
6

Missing change.

Some comments, new version is coming soon.

lib/Analysis/ScopInfo.cpp
94–97

Done.

108

is

addModuloSemantic

fine?

131

Done.

143

Done.

144

Done.

147

Done.

278

I haven't looked at all the testcases yet but I am aware that some fail (hence the [Unfinished] part).
I'll check what happens here.

296

I will split it into a separate patch. It is needed as the new SCEV we introduced doesn't have to original flags and I don't see how we can keep them with the transformation we apply.

test/ScopInfo/wraping_signed_expr_1.ll
32

I have to check.

I commited first parts of this patch already, however there are still two problems I wanted to discuss before we move forward.

  1. A few (~8) tests in lnt fail, at least one of them times out when the complement of the isl_set is computed as the set has multiple existentially quantified variables. I tried to use the domain on which both functions are equal to avoid the complement but I cannot get the constraints on the parameters that way.
  2. We currently assume parameters to be signed (e.g., use the signed range information about them) but this will use unsigned modulo semantic (e.g., mod bitwidth) to compute valid parameter combinations. First, this makes it hard to generate tests with small bounds and it additionally makes it hard to argue about the test cases we can generate. I am currently not even sure this is safe. An example for this clash of interpretation below:
// Let T be an integer type of width W
char *A = ...
T N = ...                   //   N    is in [-2^(W-1) : 2^(W-1) - 1]
for (T i = 0; i <= N; i++)  //   i    is in [     0   : 2^(W-1) - 1]
  A[i + 43] = ...           // i + 43 is in [    43   : 2^(W-1) + 42] which is non-wrapping modulo 2^W

I commited first parts of this patch already, however there are still two problems I wanted to discuss before we move forward.

I followed this. Nice.

  1. A few (~8) tests in lnt fail, at least one of them times out when the complement of the isl_set is computed as the set has multiple existentially quantified variables. I tried to use the domain on which both functions are equal to avoid the complement but I cannot get the constraints on the parameters that way.

You do not happen to have a (minimal?) test case that shows this behavior?

  1. We currently assume parameters to be signed (e.g., use the signed range information about them) but this will use unsigned modulo semantic (e.g., mod bitwidth) to compute valid parameter combinations.

What do you mean by "this"?

The 'res = ((res + 2^7) mod (2 ^ 8)) - 2^7' models wrapping of signed types, which
is what we want for signed types. Can you point me to where exactly we use 'signed modulo semantic'?

First, this makes it hard to generate tests with small bounds and it additionally makes it hard to argue about the test cases we can generate. I am currently not even sure this is safe. An example for this clash of interpretation below:

// Let T be an integer type of width W
char *A = ...
T N = ...                   //   N    is in [-2^(W-1) : 2^(W-1) - 1]
for (T i = 0; i <= N; i++)  //   i    is in [     0   : 2^(W-1) - 1]
  A[i + 43] = ...           // i + 43 is in [    43   : 2^(W-1) + 42] which is non-wrapping modulo 2^W

Should the expression i + 43 not also be modeled with signed arithmetic? Which means it is expected to be smaller than 2^(W-1)?

Best,
Tobias

jdoerfert updated this revision to Diff 24503.Apr 27 2015, 2:15 PM
jdoerfert edited edge metadata.

Modified tests and added wrapping tests including two that show huge slowdowns

@Tobias You were right about the modulo thing... I was confused and mixed things up.

I also attaced to test cases that show fast and slow behaviour depending on the position of the sext or the presence of a multiplication.

Thanks for the update.

The patch looks good indeed.

I unfortunately I don't have a solution handy for the modulo issue. In the worst case we just put a compute-out here, but first we should understand why this complement is so expensive for isl (complements and subtracts sometimes are) and possibly run it through Sven to see if there is something we can optimize? We could also extract this as a 5 line isl test case and give it to Sven.

Best,
Tobias

lib/Analysis/ScopInfo.cpp
85

semantics

94

semantics

145

"represents Expr in modulo semantic"

What do you mean here? As you state right after, overflow is known to never happen. Hence, I don't see how this expression
defines overflow semantics. Maybe just say that we know overflow is undefined and are free to choose the definition to
use in our model. As wrapping is computationally more difficult to model we avoid it when allowed.

test/ScopInfo/wraping_signed_expr_2.ll
9

i + 30

some comments

lib/Analysis/ScopInfo.cpp
85

done.

94

done.

145

It depends on the interpretation of the nsw flag. I assumed it is a certificate/proof that no overflow can happen, thus the expression is equal to the expression with modulo semantics. You say it is only well defined if this is the case, thus it is not always equal but we can ignore the cases it is not.

test/ScopInfo/wraping_signed_expr_2.ll
9

done.

This revision was automatically updated to reflect the committed changes.