[GSoC] Increase the coverage of Polly

Hi.

My plan would be:

1w Study sources of Polly and LLVM docs relating to analysis.
2w Create tests which demonstrate problems with NSW/NUW
3-4w Fix the handling of wrap overflows.
5w Complete middle term paperwork.
6w Create tests for each of cases which are not currently optimized (e.g. have min/max, sext/zext, trunc or unsigned comparisons in the loop bounds or memory accesses).
7w Learn how optimization process work for this examples.
8-10w Enable tests one by one.
11w Estimate SPEC 264ref performnace improvement (yes, I have access to one).
12w Complete paperwork.

I hope that it’s real to complete this plan in time

Hi.

Hi Vlad,

first of all it seems the conflict with raghesh was already solved. Nice.

Regarding your draft. It looks like a reasonable first version, but it obviously needs to be extended for the final application. I would also recommend to install Polly and try to find the first test cases that cannot be handled.

Some comments to your work plan:

My plan would be:

1w Study sources of Polly and LLVM docs relating to analysis

You should do this for your application. :wink: At least you should start. Did you already find the place in the scopdetection where we check if an access function is valid?

2w Create tests which demonstrate problems with NSW/NUW

I think it would be good to show at least one test case already in the application.

3-4w Fix the handling of wrap overflows.

What does need to be fixed? What is wrong at the moment? (there is obviously a problem as stated on the Polly wiki, but I believe it would be good to explain this to the audience. It will also be good for you to understand the actual problem in the code (In case you need help feel free to ask)).

5w Complete middle term paperwork.

What is middle term paperwork?

6w Create tests for each of cases which are not currently optimized
(e.g. have min/max, sext/zext, trunc or unsigned comparisons in the loop
bounds or memory accesses).

Again. Some test cases could already be shown in the application.

7w Learn how optimization process work for this examples.

I do not think you need to optimize here anything. It should be sufficient to recognize code that includes such statements and transform them into a polyhedral represenation. Optimizers like Pluto will automatically calculate the relevant optimizations, if you generate a correct polyhedral representation.

8-10w Enable tests one by one.

By 'Enable tests' do you mean implementing support for min/max .. expressions?

11w Estimate SPEC 264ref performnace improvement (yes, I have access to
one).

What do you plan to measure exactly? Runtime performance?

I think another very interesting thing would be an analysis that shows how much of the hot loops we can optimize. You can use such an analysis also to estimate the possible speedups we can achieve. Andreas (CCed) may be able to help you with some performance measurements he has already taken.

12w Complete paperwork.

What is paperwork? And why does is take a week?

I also think it would be great if you could keep track of the code coverage improvement you achieve on the llvm testsuite.

I added a lot of remarks, mainly because I am really interested in such a project. Please feel free to ask back if you need any help.

Cheers
Tobi

11w Estimate SPEC 264ref performnace improvement (yes, I have access to
one).

What do you plan to measure exactly? Runtime performance?

I think another very interesting thing would be an analysis that shows
how much of the hot loops we can optimize. You can use such an analysis
also to estimate the possible speedups we can achieve. Andreas (CCed)
may be able to help you with some performance measurements he has
already taken.

I think there are two metrics that are interesting:

First of all (ofc): Coverage improvement. In pure numbers: How
many SCoPs can be detected after coping with wrapping / min / max
Expressions.

Second: Increase of SCoP size. This can happen by detecting some more
cannonical regions as valid SCoPs that can be merged together with
surrounding SCoPs to form the maximum region that is a valid SCoP.

I can give you some patches to polly to get a profiling tool, it is not
yet clean enough to commit it, but it works reasonably well. :wink:

Andreas

Hi.

I see that to detect scops firstly we search for regions in CFG ( by
RegionInfo ) and then select regions that answer some requirements (
in ScopDetection ). Because only affine expressions in conditions and
bounds are permissible, we trying to get scalar expressions into
affine form by AffineSCEVIterator. At present there plugs for scev
types Truncate, ZeroExtend, SignExtend, UDivExpr, UMaxExpr , SMaxExpr.
Also there are no support for wrap flags NUW, NSW, NW. It can be
unsafe if we doesn't provide this information in polly IR.

So I will mainly improve AffineSCEVIterator. Now I should to show test
cases indicating that
- loops with above-listed types expressions cannot be converted to the
polyhedral representation
- wrap flags are ignored and this can bring to broken programs (in
fact, here I need some clarification)

Do I understand correctly?

I have some QA skills. Is Polly in need of autoconf, cmake, buildbot
setting up? Maybe this will be my tasks for first weeks

5 ÁÐÒÅÌÑ 2011šÇ. 16:39 ÐÏÌØÚÏ×ÁÔÅÌØ Tobias Grosser
<grosser@fim.uni-passau.de> ÎÁÐÉÓÁÌ:

Hi,

Hi.

I see that to detect scops firstly we search for regions in CFG ( by
RegionInfo ) and then select regions that answer some requirements (
in ScopDetection ). Because only affine expressions in conditions and
bounds are permissible, we trying to get scalar expressions into
affine form by AffineSCEVIterator. At present there plugs for scev
types Truncate, ZeroExtend, SignExtend, UDivExpr, UMaxExpr , SMaxExpr.
Also there are no support for wrap flags NUW, NSW, NW. It can be
unsafe if we doesn't provide this information in polly IR.

Yes, if AffineSCEVIterator can iterate Truncate, ZeroExtend and
SignExtend correctly, polly can accept much more Scops.

So I will mainly improve AffineSCEVIterator. Now I should to show test
cases indicating that
- loops with above-listed types expressions cannot be converted to the
polyhedral representation
- wrap flags are ignored and this can bring to broken programs (in
fact, here I need some clarification)

Do I understand correctly?

I think so.

I have some QA skills. Is Polly in need of autoconf, cmake, buildbot
setting up? Maybe this will be my tasks for first weeks

Looking forward to working with you :slight_smile:

best regards
ether

How to feed pocc by jscop files which are made with -polly-export-jscop?

Hi,

Hi.

I see that to detect scops firstly we search for regions in CFG ( by
RegionInfo ) and then select regions that answer some requirements (
in ScopDetection ). Because only affine expressions in conditions and
bounds are permissible, we trying to get scalar expressions into
affine form by AffineSCEVIterator. At present there plugs for scev
types Truncate, ZeroExtend, SignExtend, UDivExpr, UMaxExpr , SMaxExpr.
Also there are no support for wrap flags NUW, NSW, NW. It can be
unsafe if we doesn't provide this information in polly IR.

Yes, if AffineSCEVIterator can iterate Truncate, ZeroExtend and
SignExtend correctly, polly can accept much more Scops.

So I will mainly improve AffineSCEVIterator. Now I should to show test
cases indicating that
- loops with above-listed types expressions cannot be converted to the
polyhedral representation
- wrap flags are ignored and this can bring to broken programs (in
fact, here I need some clarification)

Do I understand correctly?

I think so.

I have some QA skills. Is Polly in need of autoconf, cmake, buildbot
setting up? Maybe this will be my tasks for first weeks

Looking forward to working with you :slight_smile:

ether, does it mean that you can be the mentor?

best regards
ether

My proposal is here. Test cases will be added later. I would be
pleased to hear some critical comments from you.

= Proposal

Polly uses own representation based on the polyhedral model. Polly has
ScopDetection component which detects parts of the control flow graph
which are candidates to be presented in the polyhedral representation.
These parts are called Static Control Parts (SCoP). There is a
requirement for SCoP that it can only contain affine linear
expressionsin loop bounds and conditions. To understand if expressions
suit to restriction ScopDetection converts it to affine linear form if
possible. Currently ScopDetection supports only basic expressions add,
addrec, mul and lacks support of min, max, sext, zext, trunc. For
effectiveness it's good to detect as many as possible SCoPs, so the
missed support should be added.
Other problem is the following. Although ScopDetection support add and
mul, it doesn't handle overflows "no signed wrap" and "no unsigned
wrap". It can be unsafe if we don’t provide the pollyhedral
representation with this information, so we can't guarantee it's safe
to compile programs using Polly.
My proposal is to solve these two problems by adding corresponding support.

= Timeline

So there are "checkpoints": Truncate, ZeroExtend, SignExtend,
UdivExpr, UMaxExpr, SMaxExpr expressions and NSW/NUW wrap flags.
My work will consist of the following steps:

Weeks 1-2.
Speeding-up. Implementing support for NSW/NUW wrap flags.

Weeks 3-4.
Implementing support for UMaxExpr, SMaxExpr.

Weeks 5-6.
Implementing support for ZeroExtend, SignExtend,
Interim progress report.

Weeks 7.
Implementing support for Truncate.

Weeks 8.
Implementing support for UDivExpr.

Weeks 9-12.
Refactoring and documentation.
Measurement of achieved results on
benchmarks for coverage improvements.
Final report.

At each step I will add create tests for it.
To prevent technical and organizational problems I will send as small
patches as possible as soon as possible.

= Why the project is interesting for me

I want to dive into the world of real compiler technology and software
development. An open-source project like LLVM-Polly is great
opportunity to do useful things and acquire good knowledge and
experience.

= Benefits for LLVM

o LLVM will be able to optimize a wider variety of programs.
o After adding support of wrap flags there will be a guarantee that
Polly produces correct transformation of any kind of LLVM IR.

= About Me

I am a fourth year student at Moscow State University, Department of
Computational Mathematics and Cybernetics.
My research area refers to parallelization on multiprocessor and
multimachine system. I participate in the university development of
parallel computing [1].
I have some compiler knowledge. I am familiar with common compiler
theory [2] and GCC internals. My completed projects include
implementing simple shell interpreter in C, Oberon interpreter in
Java, SQL interpreter in C++. Also I have some knowledge in parallel
programming with MPI and OpenMP. I worked on IBM BlueGene.

= Contacts
mail: krvladislav@gmail.com
skype: krvladislav

[1] DVM system - in English
[2] Aho, Sethi, Ullman. Compilers: Principles, Techniques and Tools

Hi,

Hi.

I see that to detect scops firstly we search for regions in CFG ( by
RegionInfo ) and then select regions that answer some requirements (
in ScopDetection ). Because only affine expressions in conditions and
bounds are permissible, we trying to get scalar expressions into
affine form by AffineSCEVIterator. At present there plugs for scev
types Truncate, ZeroExtend, SignExtend, UDivExpr, UMaxExpr , SMaxExpr.
Also there are no support for wrap flags NUW, NSW, NW. It can be
unsafe if we doesn't provide this information in polly IR.

Yes, if AffineSCEVIterator can iterate Truncate, ZeroExtend and
SignExtend correctly, polly can accept much more Scops.

So I will mainly improve AffineSCEVIterator. Now I should to show test
cases indicating that
- loops with above-listed types expressions cannot be converted to the
polyhedral representation
- wrap flags are ignored and this can bring to broken programs (in
fact, here I need some clarification)

Do I understand correctly?

I think so.

Sounds good.

The easiest example you can create is probably a simple if condition even without any loops.

void (int n, int m) {
   if (0 > n + m)
     A[0] = 0;
   else
     A[1] = 1;
  }

Let's assume those ints overflow (nsw is removed from LLVM-IR), we cannot just add the condition 0 > n + m to the polyhedral model, but we need to add a condition that models the overflow (include a modulo of the data size). In case the nsw is provided, there is no need to add the modulo stuff, which is a lot more efficient to calculate.

I have some QA skills. Is Polly in need of autoconf, cmake, buildbot
setting up? Maybe this will be my tasks for first weeks

Looking forward to working with you :slight_smile:

Mentioned later. You should set up regular LLVM test-suite runs, as you may highly increase coverage which may show some currently hidden bugs.

ether, does it mean that you can be the mentor?

ether:
if you like to mentor you may apply at the gsoc website. I can co-mentor this project if needed (and the project is accepted).

best regards
ether

My proposal is here. Test cases will be added later. I would be
pleased to hear some critical comments from you.

Nice.

= Proposal

Polly uses own representation based on the polyhedral model. Polly has
ScopDetection component which detects parts of the control flow graph
which are candidates to be presented in the polyhedral representation.
These parts are called Static Control Parts (SCoP). There is a
requirement for SCoP that it can only contain affine linear
expressionsin loop bounds and conditions. To understand if expressions
suit to restriction ScopDetection converts it to affine linear form if
possible. Currently ScopDetection supports only basic expressions add,
addrec, mul and lacks support of min, max, sext, zext, trunc. For
effectiveness it's good to detect as many as possible SCoPs, so the
missed support should be added.
Other problem is the following. Although ScopDetection support add and
mul, it doesn't handle overflows "no signed wrap" and "no unsigned
wrap". It can be unsafe if we don’t provide the pollyhedral
representation with this information, so we can't guarantee it's safe
to compile programs using Polly.
My proposal is to solve these two problems by adding corresponding support.

= Timeline

So there are "checkpoints": Truncate, ZeroExtend, SignExtend,
UdivExpr, UMaxExpr, SMaxExpr expressions and NSW/NUW wrap flags.
My work will consist of the following steps:

Weeks 1-2.
Speeding-up. Implementing support for NSW/NUW wrap flags.

This may actually take some more time. I expect some changes to scalar evolution.

Weeks 3-4.
Implementing support for UMaxExpr, SMaxExpr.

I would propose a different order. Probably the easiest stuff to get working are the *Extend things. Truncate should also be simple and more difficult are the max expressions. I would also postpone the unsigned stuff as this needs more changes in Polly (UMaxExpr, ZeroExtend), as the signed things.

Weeks 5-6.
Implementing support for ZeroExtend, SignExtend,
Interim progress report.

Weeks 7.
Implementing support for Truncate.

Weeks 8.
Implementing support for UDivExpr.

Weeks 9-12.
Refactoring and documentation.
Measurement of achieved results on
benchmarks for coverage improvements.
Final report.

You should definitely get in touch with Andreas. He has a good tool to measure SCoP coverage (Andreas, time to commit it upstream ;-))

At each step I will add create tests for it.
To prevent technical and organizational problems I will send as small
patches as possible as soon as possible.

I would probably put at least a week or two to set up a LLVM nightly test server testing the LLVM test-suite. We currently are pretty stable, and as you will increase the coverage of Polly quite a bit, we need to make sure to detect hidden bugs as early as possible.

= Why the project is interesting for me

I want to dive into the world of real compiler technology and software
development. An open-source project like LLVM-Polly is great
opportunity to do useful things and acquire good knowledge and
experience.

= Benefits for LLVM

o LLVM will be able to optimize a wider variety of programs.
o After adding support of wrap flags there will be a guarantee that
Polly produces correct transformation of any kind of LLVM IR.

= About Me

I am a fourth year student at Moscow State University, Department of
Computational Mathematics and Cybernetics.
My research area refers to parallelization on multiprocessor and
multimachine system. I participate in the university development of
parallel computing [1].
I have some compiler knowledge. I am familiar with common compiler
theory [2] and GCC internals. My completed projects include
implementing simple shell interpreter in C, Oberon interpreter in
Java, SQL interpreter in C++. Also I have some knowledge in parallel
programming with MPI and OpenMP. I worked on IBM BlueGene.

If you like to get started, a first patch may be to allow Polly to detect SCoPs with unknown access functions (access functions we cannot represent). Instead of adding an access function for those accesses, we should treat them as possibly accessing the whole array.

If you need any help with this, just ask on the mailing list. (You do not need come up with a full implementation, but e.g. adding a flag to the SCoP detection, that allows such accesses in the SCoP detection would be a good start).

= Contacts
mail: krvladislav@gmail.com
skype: krvladislav

Cheers
Tobi

Oops! I mistook UDT for CDT! I've missed deadline, so...

Mh, bad luck. I am afraid we cannot change anything about this. :frowning:

You are welcome to work on this project anyway, though unfortunately we will not be able to provide GSoC funding.

Cheers
Tobi

That does not work. You need support for scoplib as explained here:
http://wiki.llvm.org/Polyhedral_optimization_framework#Install_Pocc_.28Optional.29

To run pocc I propose to just use

./utils/pollycc -fpluto file.c -d -commands

This will also show you the exact commands used to run pocc.

Tobi