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
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: krvladislavCheers Tobi
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 >