On Nov 29, 2007, at 11:11 AM, Wojciech Matyjewicz wrote:> As you have noticed, loops aren't represented directly in the LLVM IR. > However, there are analysis passes which may be helpful to > "reconstruct" > them. For example: LoopInfo pass detects natural loops (as sets of > basic > blocks) and ScalarEvolution pass finds loop induction variables (and > also does many other things). Using them and some own solutions it > should be possible to detect most loops that are potential candidates > for parallelization. Is this what you would like to achieveRight now, one big missing piece in this puzzle is - dependence analysis. - Devang
Devang Patel wrote:> Right now, one big missing piece in this puzzle is - dependence > analysis.Right. I was only trying to say that it shouldn't be very difficult to find these for/do loops which are interesting from the parallelization perspective (in general, not all for/do loops can be reconstructed). As for the dependence analysis, I need this piece for my project, and I am preparing myself to write it. I am currently studying some papers, but haven't yet decided on the method. Maybe some of you have experience in the area and would like to advise me something? In the next few days I am going to take a look at the methods based on chains of recurrences algebra. They seem particularly interesting because chrecs are already implemented in the scalar evolution pass. Given the limited time I have for the project, I don't know how precise (and buggy;)) my implementation will be. However, if it appears to be usable, I'll be happy to contribute. --Wojtek
On Thu, 29 Nov 2007, Wojciech Matyjewicz wrote:> As for the dependence analysis, I need this piece for my project, and I > am preparing myself to write it.Great!> I am currently studying some papers, but haven't yet decided on the > method. Maybe some of you have experience in the area and would like to > advise me something? In the next few days I am going to take a look at > the methods based on chains of recurrences algebra. They seem > particularly interesting because chrecs are already implemented in the > scalar evolution pass.Yes, I'd strongly suggest implementing one of the approaches based on the chrec analysis we have in the scev pass. -Chris -- http://nondot.org/sabre/ http://llvm.org/
Wojciech Matyjewicz wrote:> As for the dependence analysis, I need this piece for my project, and I > am preparing myself to write it. I am currently studying some papers, > but haven't yet decided on the method. Maybe some of you have experience > in the area and would like to advise me something?I recently read Allen & Kennedy's book Optimizing Compilers for Modern Architectures - A Dependence Based Approah. It is extermely useful if you are interested in analysis and transformations for parallelization (ILP, vectorization, multiprocessing). <http://www.amazon.com/Optimizing-Compilers-Modern-Architectures-Dependence-based/dp/1558602860/ref=sr_1_9?ie=UTF8&s=books&qid=1196410806&sr=1-9> One caveat though: look up the errata on the net right from the start, as there are lots of typos at least in the printing I have. -- Pertti