[GSoC 2016] Polly as an Analysis pass - Midterm report

Dear Community,

I would like to summarize my work till date for GSoC 2016.

Till the current phase of my project, I have mostly focused on developing the necessary infrastructure to use analysis results from Polly in LLVM.

Initial plan as mentioned in the proposal:

For the first month:-

  1. Decouple ScopInfo pass from Polly’s pass chain and provide capability to create SCoP(Static Control Parts) objects from arbitrary SESE regions.

  2. Implement new passes ScopInfoWrapperPass and DependenceInfoWrapperPass as Function Passes.

  3. Provide an interface to Polly’s dependence analysis which can be directly queried from LLVM transformation passes such as Loop Vectorizer.

For the next phase:-

  1. Cache the dependences computed by Polly for a given SCoP and provide methods to invalidate the analysis results when the SCoP changes.

  2. Demonstrate the power and usefulness of the interface by integrating it with Loop Vectorizer or other clients, for example, client that requires loop trip count, etc.

Current Status:

  1. Decoupling SCoP object creation from pass logic is complete and has been addressed under D20770, D20831 and D20912 review items. Patches have been accepted and committed.

  2. Implemented two new function passes in Polly namely ScopInfoWrapperPass (D20962) and DependenceInfoWrapperPass (D21105). These are required to bypass the RegionPassManager.

  3. ScopInfoWrapperPass addresses creating SCoP objects for the whole function.

  4. DependenceInfoWrapperPass addresses constructing polyhedral dependences for all the SCoP objects of a function.

  5. These patches are currently under review and I am incorporating changes as suggested by the Polly community.

  6. Implemented first version of an interface to Polly’s analysis passes- PolyhedralInfo pass (D21486). Implemented isParallel(Loop *) interface to check parallelism of a loop.

Pending Work:

  1. Complete the interface - PolyhederalInfo pass. Currently I am working on providing more interfaces to check whether a loop is vectorizable or not and to get loop trip count.
  • isVectorizable(Loop *L, *MinDepDistance)

  • getLoopTripCount(Loop *)

  1. Work on caching Polly’s analysis results properly and provide methods to invalidate the analysis results when the SCoP changes.

  2. Demonstrate the power and usefulness of the interface by integrating it with Loop Vectorizer.

Below are the list of patches I sent during this period:-

D20770, D20831, D20912, D20962, D21105, D21486

I thank Johannes, Tobias, Michael, Ether and others for all the support/feedback/advises. Especially, Johannes for the time spent in hangouts, which we have been having two times a week.

Looking forward for your suggestions and comments.

Regards,

Utpal Bora

Ph.D. Scholar
Computer Science & Engineering

IIT Hyderabad

http://utpalbora.github.io

Dear Community,

I would like to summarize my work till date for GSoC 2016.

Hi Utpal,

thank you for this update.

Till the current phase of my project, I have mostly focused on
developing the necessary infrastructure to use analysis results from
Polly in LLVM.

Initial plan as mentioned in the proposal:

For the first month:-

1.

    Decouple ScopInfo pass from Polly’s pass chain and provide
    capability to create SCoP(Static Control Parts) objects from
    arbitrary SESE regions.

2.

    Implement new passes ScopInfoWrapperPass and
    DependenceInfoWrapperPass as Function Passes.

3.

    Provide an interface to Polly’s dependence analysis which can be
    directly queried from LLVM transformation passes such as Loop
    Vectorizer.

This seems to have been gone very nicely. I see that some of the patches
are still in the review process. Could you elaborate on their status and
what is still needed to get them committed.

For the next phase:-

4.

    Cache the dependences computed by Polly for a given SCoP and provide
    methods to invalidate the analysis results when the SCoP changes.

5.

    Demonstrate the power and usefulness of the interface by integrating
    it with Loop Vectorizer or other clients, for example, client that
    requires loop trip count, etc.

Current Status:

1.

    Decoupling SCoP object creation from pass logic is complete and has
    been addressed under D20770 <http://reviews.llvm.org/D20770>, D20831
    <http://reviews.llvm.org/D20831>and D20912
    <http://reviews.llvm.org/D20912>review items. Patches have been
    accepted and committed.

2.

    Implemented two new function passes in Polly namely
    ScopInfoWrapperPass (D20962 <http://reviews.llvm.org/D20962>) and
    DependenceInfoWrapperPass (D21105 <http://reviews.llvm.org/D21105>).
    These are required to bypass the RegionPassManager.

     1.

        ScopInfoWrapperPass addresses creating SCoP objects for the
        whole function.

     2.

        DependenceInfoWrapperPass addresses constructing polyhedral
        dependences for all the SCoP objects of a function.

3.

    These patches are currently under review and I am incorporating
    changes as suggested by the Polly community.

4.

    Implemented first version of an interface to Polly's analysis
    passes- PolyhedralInfo pass (D21486
    <http://reviews.llvm.org/D21486>). Implemented isParallel(Loop *)
    interface to check parallelism of a loop.

Pending Work:

1.

    Complete the interface - PolyhederalInfo pass. Currently I am
    working on providing more interfaces to check whether a loop is
    vectorizable or not and to get loop trip count.

      *

        isVectorizable(Loop *L, *MinDepDistance)

      *

        getLoopTripCount(Loop *)

2.

    Work on caching Polly's analysis results properly and provide
    methods to invalidate the analysis results when the SCoP changes.

3.

    Demonstrate the power and usefulness of the interface by integrating
    it with Loop Vectorizer.

Below are the list of patches I sent during this period:-

D20770 <http://reviews.llvm.org/D20770>, D20831
<http://reviews.llvm.org/D20831>, D20912
<http://reviews.llvm.org/D20912>, D20962
<http://reviews.llvm.org/D20962>, D21105
<http://reviews.llvm.org/D21105>, D21486 <http://reviews.llvm.org/D21486>

I thank Johannes, Tobias, Michael, Ether and others for all the
support/feedback/advises. Especially, Johannes for the time spent in
hangouts, which we have been having two times a week.

Very nice, indeed and thanks Johannes for taking the time for such close
mentoring. To make sure we are all up-to-date it would be great if you
could send brief meeting notes that summarize your hangout discussions.

Best,
Tobias

Hello Tobias,

Please see my comments below.

> Dear Community,
>
>
> I would like to summarize my work till date for GSoC 2016.

Hi Utpal,

thank you for this update.

> Till the current phase of my project, I have mostly focused on
> developing the necessary infrastructure to use analysis results from
> Polly in LLVM.
>
>
> Initial plan as mentioned in the proposal:
>
> For the first month:-
>
> 1.
>
> Decouple ScopInfo pass from Polly’s pass chain and provide
> capability to create SCoP(Static Control Parts) objects from
> arbitrary SESE regions.
>
> 2.
>
> Implement new passes ScopInfoWrapperPass and
> DependenceInfoWrapperPass as Function Passes.
>
> 3.
>
> Provide an interface to Polly’s dependence analysis which can be
> directly queried from LLVM transformation passes such as Loop
> Vectorizer.

This seems to have been gone very nicely. I see that some of the patches
are still in the review process. Could you elaborate on their status and
what is still needed to get them committed.

Patches D20912 and D20962 are ready for commit.

For patches D21105 and D21486 I am working on review comments and will be
ready for commit by this weekend.

> For the next phase:-
>
> 4.
>
> Cache the dependences computed by Polly for a given SCoP and provide
> methods to invalidate the analysis results when the SCoP changes.
>
> 5.
>
> Demonstrate the power and usefulness of the interface by integrating
> it with Loop Vectorizer or other clients, for example, client that
> requires loop trip count, etc.
>
>
> Current Status:
>
> 1.
>
> Decoupling SCoP object creation from pass logic is complete and has
> been addressed under D20770 <http://reviews.llvm.org/D20770>, D20831
> <http://reviews.llvm.org/D20831>and D20912
> <http://reviews.llvm.org/D20912>review items. Patches have been
> accepted and committed.
>
> 2.
>
> Implemented two new function passes in Polly namely
> ScopInfoWrapperPass (D20962 <http://reviews.llvm.org/D20962>) and
> DependenceInfoWrapperPass (D21105 <http://reviews.llvm.org/D21105>).
> These are required to bypass the RegionPassManager.
>
> 1.
>
> ScopInfoWrapperPass addresses creating SCoP objects for the
> whole function.
>
> 2.
>
> DependenceInfoWrapperPass addresses constructing polyhedral
> dependences for all the SCoP objects of a function.
>
> 3.
>
> These patches are currently under review and I am incorporating
> changes as suggested by the Polly community.
>
> 4.
>
> Implemented first version of an interface to Polly's analysis
> passes- PolyhedralInfo pass (D21486
> <http://reviews.llvm.org/D21486>). Implemented isParallel(Loop *)
> interface to check parallelism of a loop.
>
>
> Pending Work:
>
> 1.
>
> Complete the interface - PolyhederalInfo pass. Currently I am
> working on providing more interfaces to check whether a loop is
> vectorizable or not and to get loop trip count.
>
> *
>
> isVectorizable(Loop *L, *MinDepDistance)
>
> *
>
> getLoopTripCount(Loop *)
>
> 2.
>
> Work on caching Polly's analysis results properly and provide
> methods to invalidate the analysis results when the SCoP changes.
>
> 3.
>
> Demonstrate the power and usefulness of the interface by integrating
> it with Loop Vectorizer.
>
>
> Below are the list of patches I sent during this period:-
>
> D20770 <http://reviews.llvm.org/D20770>, D20831
> <http://reviews.llvm.org/D20831>, D20912
> <http://reviews.llvm.org/D20912>, D20962
> <http://reviews.llvm.org/D20962>, D21105
> <http://reviews.llvm.org/D21105>, D21486 <http://reviews.llvm.org/D21486
>
>
>
> I thank Johannes, Tobias, Michael, Ether and others for all the
> support/feedback/advises. Especially, Johannes for the time spent in
> hangouts, which we have been having two times a week.

Very nice, indeed and thanks Johannes for taking the time for such close
mentoring. To make sure we are all up-to-date it would be great if you
could send brief meeting notes that summarize your hangout discussions.

Ok, I will send the notes form now on. Some of the notes are maintained

here
<https://drive.google.com/folderview?id=0B6y_K1BShACaZHVuTHF5ZWdmeUE&usp=sharing>
.

Best,
Tobias

Thank you.

Regards,
Utpal Bora

Hello Tobias,

Please see my comments below.

    > 3.
    >
    > Provide an interface to Polly’s dependence analysis which can be
    > directly queried from LLVM transformation passes such as Loop
    > Vectorizer.

    This seems to have been gone very nicely. I see that some of the patches
    are still in the review process. Could you elaborate on their status and
    what is still needed to get them committed.

Patches D20912 and D20962 are ready for commit.
For patches D21105 and D21486 I am working on review comments and will
be ready for commit by this weekend.

Great. Feel free to upstream them with Johannes help.

    > I thank Johannes, Tobias, Michael, Ether and others for all the
    > support/feedback/advises. Especially, Johannes for the time spent in
    > hangouts, which we have been having two times a week.

    Very nice, indeed and thanks Johannes for taking the time for such close
    mentoring. To make sure we are all up-to-date it would be great if you
    could send brief meeting notes that summarize your hangout discussions.

Ok, I will send the notes form now on. Some of the notes are maintained
here
<https://drive.google.com/folderview?id=0B6y_K1BShACaZHVuTHF5ZWdmeUE&usp=sharing>.

Great you guys took notes. This is precisely what I have been looking
for. Sending them out will be great to keep us all on the same page.

Best,
Tobias