Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Delinearization fails when loop indexes are in reverse order #19710

Closed
tobiasgrosser opened this issue Apr 4, 2014 · 5 comments
Closed

Delinearization fails when loop indexes are in reverse order #19710

tobiasgrosser opened this issue Apr 4, 2014 · 5 comments
Assignees
Labels
bugzilla Issues migrated from bugzilla loopoptim

Comments

@tobiasgrosser
Copy link
Contributor

Bugzilla Link 19336
Resolution FIXED
Resolved on Sep 10, 2014 03:28
Version trunk
OS Linux
Attachments Reduced test case
CC @sebpop

Extended Description

We can sucessfully delinearize this piece of code:

A[][dim_size];

for (i = 0; i < n; i++)_
for (j = 0; j < n; j++)
A[i][j]

AddRec: {{%A,+,(4 * %dim_size)}<%loop.i>,+,4}<%loop.j>
Base offset: %A
ArrayDecl[UnknownSize][%dim_size] with elements of 4 bytes.
ArrayRef[{0,+,1}<%loop.i>][{0,+,1}<%loop.j>]

but fail for:

A[][dim_size];

for (i = 0; i < n; i++)_
for (j = 0; j < n; j++)
A[j][i]

AddRec: {{%A,+,4}<%loop.i>,+,(4 * %dim_size)}<%loop.j>
Base offset: %A
ArrayDecl[UnknownSize][1] with elements of 4 bytes.
ArrayRef[{0,+,1}<%loop.i>][{0,+,%dim_size}<%loop.j>]

@tobiasgrosser
Copy link
Contributor Author

assigned to @sebpop

@sebpop
Copy link
Mannequin

sebpop mannequin commented Apr 4, 2014

I will fix this.

@sebpop
Copy link
Mannequin

sebpop mannequin commented Apr 4, 2014

but fail for:

A[][dim_size];

for (i = 0; i < n; i++)_
for (j = 0; j < n; j++)
A[j][i]

AddRec: {{%A,+,4}<%loop.i>,+,(4 * %dim_size)}<%loop.j>
Base offset: %A
ArrayDecl[UnknownSize][1] with elements of 4 bytes.
ArrayRef[{0,+,1}<%loop.i>][{0,+,%dim_size}<%loop.j>]

This is a correct delinearization, although it is not a very useful one:

  • the size of the inner dimension is 1: ArrayDecl[UnknownSize][1]
  • the stride of the inner dimension is parametric: [{0,+,%dim_size}<%loop.j>]

I think we should be able to modify SCEV->delinearize to "prefer" a non
parametric strides, and that would also solve the strange dimension size "1".

@tobiasgrosser
Copy link
Contributor Author

but fail for:

A[][dim_size];

for (i = 0; i < n; i++)_
for (j = 0; j < n; j++)
A[j][i]

AddRec: {{%A,+,4}<%loop.i>,+,(4 * %dim_size)}<%loop.j>
Base offset: %A
ArrayDecl[UnknownSize][1] with elements of 4 bytes.
ArrayRef[{0,+,1}<%loop.i>][{0,+,%dim_size}<%loop.j>]

This is a correct delinearization, although it is not a very useful one:

  • the size of the inner dimension is 1: ArrayDecl[UnknownSize][1]
  • the stride of the inner dimension is parametric: [{0,+,%dim_size}<%loop.j>]

I think we should be able to modify SCEV->delinearize to "prefer" a non
parametric strides, and that would also solve the strange dimension size "1".

Yes, non parametric strides should be preferred. With this stride, we can not really do a lot.

Tobi

@tobiasgrosser
Copy link
Contributor Author

I just tested with 217336 and this works. The corresponding test case is part of
Polly since 208233.

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 9, 2021
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bugzilla Issues migrated from bugzilla loopoptim
Projects
None yet
Development

No branches or pull requests

1 participant