[LLVMdev] [GSoC] Increase the coverage of Polly

[Vlad Krylov]

2011/4/8 ether zhhb <etherzhhb at gmail.com>:
> Hi,
>
> 2011/4/8 Vlad Krylov <krvladislav at gmail.com>:
>> 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 :)
>


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 at gmail.com
skype: krvladislav

[1] http://www.keldysh.ru/dvm/dvmhtm1107/eng/index.html
[2] Aho, Sethi, Ullman. Compilers: Principles, Techniques and Tools