This is an archive of the discontinued LLVM Phabricator instance.

[Polly] Allow overflow of indices with constant dimensions size
ClosedPublic

Authored by Meinersbur on Apr 7 2016, 4:27 PM.

Details

Summary

Allow overflow of indices into the next higher dimension if it has constant length. E.g.

float A[32][2];
((float*)A)[5];

is effectively the same as

A[2][1];

This can happen since r265379 as a side effect if ScopDetection recognizes an access as affine, but ScopInfo rejects the GetElementPtr.

Diff Detail

Repository
rL LLVM

Event Timeline

Meinersbur updated this revision to Diff 52973.Apr 7 2016, 4:27 PM
Meinersbur retitled this revision from to [Polly] Allow overflow of indices with constant dimensions size.
Meinersbur updated this object.
Meinersbur added reviewers: grosser, Unknown Object (User).
Meinersbur added a project: Restricted Project.
Meinersbur added subscribers: pollydev, llvm-commits.

Not meant as fix for PR27195. It does not fix the vec-delin.ll test case. The uploaded test case delinearization-fixed-size.ll seems unrelated to the first one. Tobias already partially fixed that latter in r265379.

lib/Analysis/ScopInfo.cpp
343 ↗(On Diff #52973)

Removing this causes a lot more changes in unit tests.

test/ScopInfo/multidim_fixedsize_multi_offset.ll
12 ↗(On Diff #52973)

The scop was only rejected because the computed MemoryAccess was

{ [i0] -> MemRef_A[0, 2 + 2i0] }

which is unconditionally out of bounds.

test/ScopInfo/process_added_dimensions.ll
3–4 ↗(On Diff #52973)

The unit test is accepted and I don't find anything wrong. Can somebody double-check?

Especially because there is no hoisted load, but MemRef_call[5, 5, 0] is the correct access (instead of MemRef_call[0, 0, 2240])

38 ↗(On Diff #52973)

Stmt_for_cond40_preheader_5 would disappear without this change as %.pre160 is otherwise unused.

Meinersbur added inline comments.Apr 8 2016, 6:41 AM
test/ScopInfo/multidim_fixedsize_multi_offset.ll
12 ↗(On Diff #52973)

Just to add that this is not wrong; The out of bounds conditions are added to the RTCs. That is, even if the computed linear are not completely out of bounds, only the executions where it is within the last dimension' bounds run the optimized version.

That is, r265379 is not only a 'partial fix', but a complete one; This patch only extents the context so more executions can run the optimized version.

Meinersbur edited reviewers, added: jdoerfert; removed: Unknown Object (User).Apr 8 2016, 6:42 AM
grosser accepted this revision.Apr 11 2016, 1:23 AM
grosser edited edge metadata.

Hi Michael,

very nice change. I just have some minor comments.

Best,
Tobias

lib/Analysis/ScopInfo.cpp
332 ↗(On Diff #52973)

constant length -> constant size

338 ↗(On Diff #52973)

indicies -> indices

343 ↗(On Diff #52973)

This is a large and mostly independent piece of code. It would probably make sense to put this into its own function.

test/ScopInfo/multidim_fixedsize_multi_offset.ll
28 ↗(On Diff #52973)

through

test/ScopInfo/process_added_dimensions.ll
3–4 ↗(On Diff #52973)

Looks good to me.

This revision is now accepted and ready to land.Apr 11 2016, 1:23 AM
Meinersbur updated this revision to Diff 53228.Apr 11 2016, 5:50 AM
Meinersbur edited edge metadata.
Meinersbur marked 4 inline comments as done.

Apply tobias' hints; add more comments.

Will try with LNT before committing.

This revision was automatically updated to reflect the committed changes.

What is the assume context? can we check them in the testcase?

Contexts added if r266323.

looks good to me