[LLVMdev] [GSoC] Increase the coverage of Polly

[Vlad Krylov]

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


2011/4/9 Tobias Grosser <grosser at fim.uni-passau.de>:
> On 04/08/2011 08:35 PM, Vlad Krylov wrote:
>>
>> 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.
>
> 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 :)
>
>
> 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 at gmail.com
>> skype: krvladislav
>
> Cheers
> Tobi
>