Move beta-related functionality from Clay to OSL

[ftynse]

A significant amount of theoretical work on polyhedral tools is written in terms of beta-prefixes and beta-vectors, while the only tool that seems to have this concept implemented is Clay. It seems reasonable for me to introduce an entity osl_beta and move multiple clay_beta_* functions to OSL so that other tools can use it. For example, finding a statement by its beta is rather useful functionality. For example, Candl expects statements sorted by beta-vectors, but can not do it itself without duplicating Clay functionality. Beta is a scop-related notion, rather than Clay-specific. Introducing more functionality to osl may make it heavier, but I don't think it will make reading/writing any slower since betas are extracted from osl_* structures upon request.

[Ced]

Interesting proposal. I have a mixed feeling about it though. My main problem is a scattering is not forced to be encoded using beta. Checking that a SCoP has beta everywhere is not a simple problem (it looks simple, but believe me, it is not). So it would be useful only for specific user. Do you see enough use for beta outside Clay for such a move ?

Also note that beta are nice in Clay, but in general we are talking now about "schedule trees". But I'm not going to develop that anytime soon :-D.

[Lnc]

We need a way to identify statements without use their position in the linked list (it is not robust).

If we can not use betas, I propose a statement id in the statement structure (or in the statement extensions). The statement id is a number (size_t id;) and an other number that corresponds to the scattering relation part. It is simple :) "schedule trees" is a better solution ?

If it is complicated to check and re-generate the beta in the scattering, maybe we can add these functions in OpenScop.

[ftynse]

@Ced Even though checking if a SCoP has beta everywhere is a hard problem, I'd like to have this check at some point for not calling Clay on "wrong" SCoPs. I have introduced a sanity_check function into Clay already.

@Ced I agree with @Lnc that beta will be used for mostly identification purposes, in Candl for example to match statements from two SCoPs with each other. The benefit of using a beta rather than an integer ID is that it allows to select a subset of statements by using beta-prefixes or wildcarding of some kind. I believe it is the case with schedule trees also.

Ironically, Clay has beta tree implemented, but does not seem to be using it.

[Ced]

On Mon, Jun 30, 2014 at 9:55 AM, Alexander Zinenko <notifications@github.com

wrote:

@Ced https://github.com/Ced Even though checking if a SCoP has beta everywhere is a hard problem, I'd like to have this check at some point for not calling Clay on "wrong" SCoPs. I have introduced a sanity_check function into Clay already.

I did it some time ago in CLooG (CLooG tries to find beta-like dimensions -called scalar dimensions, because their processing is trivial). Sven found some bugs and moved that part directly in isl, so I don't really know how it is done now. We could reintroduce that in osl, but it would be some work.

Because we master the complete chain, maybe it would be more convenient and simple to have a statement extension which would provide some semantics about each scattering output dimension and could be generated by Clan. In such a case it would be natural to have functions to manipulate betas and even more in osl.

Here is a paper that explains what we could imagine about the semantics (not simply alpha/beta): http://impact.gforge.inria.fr/impact2014/papers/impact2014-verdoolaege.pdf

Note that I like to have more semantics about the scattering as much as I dislike to break the scattering relation into schedule tree. It's very convenient to have a general mathematical approach, so I would prefer to keep the scattering relation intact and to have additional semantics information next to it.

@Ced https://github.com/Ced I agree with @Lnc https://github.com/Lnc that beta will be used for mostly identification purposes, in Candl for example to match statements from two SCoPs with each other. The benefit of using a beta rather than an integer ID is that it allows to select a subset of statements by using beta-prefixes or wildcarding of some kind. I believe it is the case with schedule trees also.

I think @Lnc needs also a clear way to tell that a given statement body in a SCoP relates to a given statement body in the original program. If yes, isn't the right place for such information in the body ?

Ironically, Clay has beta tree implemented, but does not seem to be using it.

Reply to this email directly or view it on GitHub https://github.com/periscop/openscop/issues/25#issuecomment-47503867.

[ftynse]

I tend to agree that extension for the semantic information is a good solution. My concern is the possible duplication of the data between relation and extension or between multiple extensions (as we already have with body and extbody).

I had a need for statement identification to track changes in the code representation. With scattering relation unions it should not be a problem anymore. Candl seems to be the only user of statement identifiers then.