This is an archive of the discontinued LLVM Phabricator instance.

[Polly] Added support for modulo expressions
Needs ReviewPublic

Authored by jdoerfert on Sep 10 2014, 5:23 AM.

Details

Reviewers
simbuerg
dpeixott
Summary
The support is limited to signed modulo access and condition
expressions with a constant right hand side, e.g., A[i % 2] or
A[i % 9]. Test cases are modified according to this new feature and
new test cases are added.

Diff Detail

Event Timeline

jdoerfert updated this revision to Diff 13535.Sep 10 2014, 5:23 AM
jdoerfert retitled this revision from to [Polly] Added support for modulo expressions.
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.Jan 24 2015, 8:53 AM

I looked through the test files and I have the feeling there is a some redundancy. For example, the following files are identical, except for the constants used:

non_affine_but_modulo_access_1023.ll
non_affine_but_modulo_access_3.ll
non_affine_but_modulo_access_4.ll
non_affine_but_modulo_access_5.ll
non_affine_but_modulo_access_6.ll

non_affine_but_modulo_loop_bound_constant_7.ll
non_affine_but_modulo_loop_bound_constant_9.ll
non_affine_but_modulo_loop_bound_parameter.ll

non_affine_but_modulo_condition_3.ll
non_affine_but_modulo_condition_5.ll

non_affine_but_modulo_condition_4.ll
non_affine_but_modulo_condition_8.ll

Test coverage in general is good, but my feeling is that these tests may not increase test coverage, but rather distract from the test that cover the relevant cases.

lib/Analysis/ScopInfo.cpp
76

This would not be needed, if we just focus on constants in the RHS. (see below)

192

This can be folded into the if below.

201

This can be folded into the if above.

207

The operand of this truncate expression and correspondingly the dividend of this remainder operation can become negative. It may be worth a test case (example attached) and a comment on why aff_mod_val models this pattern
correctly despite the fact that for negative dividends of the srem expression, it is not the right choice.

310

I like the idea of extending our analysis across unknowns. This is indeed a very nice approach.

326

This is a lot of code, just to get a constant. Assuming we run an instruction simplification pass before Polly, can it really happen that RHS is not an explicit constant? If we assume the RHS is always a constant, we could simplify this by directly converting BO->getOperand(1) to an isl_pw_aff.

Also, as previously discussed, the use of isl's aff_mod_val() is incorrect for cases where the LHS is negative, as the semantics of isl_aff_mod and srem differ.

lib/Support/SCEVValidator.cpp
98

The change of the return type does not seem to be used in this patch.

Moving class -> const is an obvious improvement. As it is unrelated to the patch, I would suggest to commit it directly as "obvious".

386

It would be nice to add a corresponding DEBUG statement to this INVALID instruction, which explains why the statement is refused (this is done consistently in this class).

389

Is the "!Op1.isValid() ||" part here needed?

Also, the patch refuses this piece of code which was previously accepted:

void foo(float *A, long a, long b) {
	for (long i = 0; i < (a % b); i++)
		A[i] = 1;
}
test/DeadCodeElimination/non-affine-affine-mix.ll
9

Great that you preserve this file.

test/DeadCodeElimination/non-affine-but-modulo-and-affine-mix.ll
15

Maybe make this a CHECK-NOT: Stmt_S1?

test/ScopDetect/non_affine_but_modulo_access.ll
7

Nice that we can detect this now!

test/ScopInfo/NonAffine/indirect_array_write.ll
8

Is this in any way related to modulos? If not and this just makes the filename more understandable, this could be committed separately.

test/ScopInfo/NonAffine/non_affine_but_modulo_condition_8.ll
14

The test cases fail ATM for me, because of the additional '0's in the scattering

test/ScopInfo/NonAffine/non_affine_but_modulo_loop_bound_constant_7.ll
16

Interesting. I like this test case.

test/ScopInfo/reduction_alternating_base.ll
12

Nice!

I added some comments and will change than patch accordingly. I will also split two smaller parts and remove some test cases for which I unfortunately can't remember the exact reason I added them. Anyway, thanks for the review.

lib/Analysis/ScopInfo.cpp
207

I'll add that.

326

The second concern is important and I will correct that. Regarding the first, I'm not sure, maybe if we check this in the ScopDetection we can just assume a constant RHS here. I'm not sure which is better and do not have any arguments for one or another, so we should just choose one. (Or we do a isa<ConstantInt>(BO->getOperand(1)) here?)

lib/Support/SCEVValidator.cpp
98

This was an artifact (I used it at some point but apperently I changed it again). I will commit the const part and forget about the return type

386

I can change this to return Op0 if to make it clear that the DEBUG message was already produced in the recursive step.
Or did I miss something?

389

Good points. I'll address both.

test/DeadCodeElimination/non-affine-but-modulo-and-affine-mix.ll
15

Agreed.

test/ScopInfo/NonAffine/non_affine_but_modulo_condition_8.ll
14

I'll change it ...

I added some comments and will change than patch accordingly. I will also split two smaller parts and remove some test cases for which I unfortunately can't remember the exact reason I added them. Anyway, thanks for the review.

Hi Johannes,

I updated and committed a first part of this patch in r240518 containing only the support for the srem instruction and incorporating the changes we discussed here.

Best,
Tobias

Hi Johannes,

I am still waiting for feedback on this patch. I already added some of the code into Polly, but especially the power-of-two test cases do not work yet and would be worth adding. In case you find time to complete this patch, this would be great.

grosser resigned from this revision.Jun 11 2016, 3:08 AM
grosser removed a reviewer: grosser.

Hi Johannes,

as you did not update this patch since a while, it seems to not be of interest at the moment. To clean up my patch review log I remove myself as a reviewer. Feel free to add me again when you get back to this.

Best,
Tobias

sebpop resigned from this revision.Sep 19 2016, 1:21 PM
sebpop removed a reviewer: sebpop.