Page MenuHomePhabricator

[Polly][WIP] Do not use isl_set_project_out to get all loop prefixes
ClosedPublic

Authored by gareevroman on Aug 3 2017, 11:55 AM.

Details

Summary

In some cases, getPartialTilePrefixes cannot produce the desired set of prefixes of the vector loop that have exactly VectorWidth iterations. A possible reason is the unexpected behavior of the isl_set_project_out function.

This patch introduces a temporary solution of that problem.

P.S.: I haven't managed to get a reduced test case to understand whether isl_set_project_out produces the wrong or unexpected result yet. I would be very grateful for your ideas about it.

Diff Detail

Repository
rL LLVM

Event Timeline

gareevroman created this revision.Aug 3 2017, 11:55 AM
grosser edited edge metadata.Aug 3 2017, 11:47 PM

Hi Roman,

thank you for the update. The function drop_constraints_involving_dims seems to accidentally drop more constraints that involve outer dimensions, but this does not seem to be a change we actually understand well. I wonder if the problem is rather that you isolate -- assuming a single loop vector dimension -- but in the end more than one loop dimension is unrolled? Should we not rather isolate the full multi-dimensional tile that is unrolled?

grosser requested changes to this revision.Aug 3 2017, 11:47 PM

Mark this as requesting changes, to be notified on reply.

This revision now requires changes to proceed.Aug 3 2017, 11:47 PM
gareevroman requested review of this revision.Aug 4 2017, 9:30 AM
gareevroman edited edge metadata.

Hi Roman,

thank you for the update.

Hi Tobias,

thanks for the reply.

The function drop_constraints_involving_dims seems to accidentally drop more constraints that involve outer dimensions, but this does not seem to be a change we actually understand well.

Please, correct me if I'm wrong, but I think it's fine to drop more constraints because it should help to get the same result:

As far as I understand, if we drop all constraints involving the dimension that represents the vector loop, we get a set that contains all loop prefixes of the loop.

Subsequently, we constraint the last dimension to get a set, which has exactly VectorWidth iterations, subtract the iteration domain from it, and project out the vector loop dimension to get a set of prefixes, which don't have exactly VectorWidth iterations or don't belong to the domain (since we could drop some constraints).

Subsequently, we subtract the set from the set built on the first stage to get the desired prefixes.

Previously, on the first stage, we projected out the last dimension to get only prefixes of the vector loop.

I wonder if the problem is rather that you isolate -- assuming a single loop vector dimension -- but in the end more than one loop dimension is unrolled? Should we not rather isolate the full multi-dimensional tile that is unrolled?

I think it's fine, because we get partial tile prefixes of the innermost loop first. Subsequently, we get partial tile prefixes of the previous loop using that set of prefixes instead of the iteration domain.

Hi Roman,

thank you for the update.

Hi Tobias,

thanks for the reply.

The function drop_constraints_involving_dims seems to accidentally drop more constraints that involve outer dimensions, but this does not seem to be a change we actually understand well.

Please, correct me if I'm wrong, but I think it's fine to drop more constraints because it should help to get the same result:

This will not result in incorrect program output, but it will be rather fragile as it just happens to work by accident due to the way the given set is modeled today. If it does not work with projection, our approach is likely not fully correct. As I know you are under time constraints I spent the morning debugging this myself. Please see the latest email "Isolation with non-convex conditions" to the isl mailing list for some infos about the bug. It seems isl is over-approximating the isolated set, in case the set is non convex. This pulls iterations that require conditions in the innermost loop. I am fine committing this as a temporary workaround if you are happy to fix it after your the deadline. In this case, just put a TODO note for us to not forget.

As far as I understand, if we drop all constraints involving the dimension that represents the vector loop, we get a set that contains all loop prefixes of the loop.
Let me think what you are doing
Subsequently, we constraint the last dimension to get a set, which has exactly VectorWidth iterations, subtract the iteration domain from it, and project out the vector loop dimension to get a set of prefixes, which don't have exactly VectorWidth iterations or don't belong to the domain (since we could drop some constraints).

Subsequently, we subtract the set from the set built on the first stage to get the desired prefixes.

Previously, on the first stage, we projected out the last dimension to get only prefixes of the vector loop.

I wonder if the problem is rather that you isolate -- assuming a single loop vector dimension -- but in the end more than one loop dimension is unrolled? Should we not rather isolate the full multi-dimensional tile that is unrolled?

I think it's fine, because we get partial tile prefixes of the innermost loop first. Subsequently, we get partial tile prefixes of the previous loop using that set of prefixes instead of the iteration domain.

Yes, I think we take the right approach, but did not really reason about non-convex isolate conditions. Let's see what Sven thinks about this.

Best,
Tobias

Hi Roman,

thank you for the update.

Hi Tobias,

thanks for the reply.

The function drop_constraints_involving_dims seems to accidentally drop more constraints that involve outer dimensions, but this does not seem to be a change we actually understand well.

Please, correct me if I'm wrong, but I think it's fine to drop more constraints because it should help to get the same result:

This will not result in incorrect program output, but it will be rather fragile as it just happens to work by accident due to the way the given set is modeled today. If it does not work with projection, our approach is likely not fully correct. As I know you are under time constraints I spent the morning debugging this myself. Please see the latest email "Isolation with non-convex conditions" to the isl mailing list for some infos about the bug. It seems isl is over-approximating the isolated set, in case the set is non convex. This pulls iterations that require conditions in the innermost loop. I am fine committing this as a temporary workaround if you are happy to fix it after your the deadline. In this case, just put a TODO note for us to not forget.

Thank you very much! Yes, I'm happy to fix it after the deadline. However, I think it'd be good to get Sven's answer first.

grosser accepted this revision.Aug 6 2017, 3:05 AM

OK, then please commit.

This revision is now accepted and ready to land.Aug 6 2017, 3:05 AM

Hi Roman,

any plans to commit this? I am currently experimenting with the matmul optimization and it would be really useful to have all patches in. Can you also push the 2nd patch?

This revision was automatically updated to reflect the committed changes.