I am involved in a project where one of the aims is to study the effects of different parallelization strategies on efficiency, power consumption etc. The idea is to do automated design space exploration by varying some parameters (e.g. number of tasks) and measuring their effect. Since we are already using LLVM for other purposes, we thought about using LLVM for analysis and then OpenMP for compilation. The idea was to use the LLVM back end to spit out C code with OpenMP directives. However, looking at the C code that llc produces, it seems that this might be a non-starter, as loops have already been turned into gotos in the generated C. I suspect we may need to do something else, but if anyone has any bright ideas on how to use LLVM for this purpose, I'd be very grateful. TIA, -- Pertti
On Nov 27, 2007, at 4:48 AM, Pertti Kellomäki wrote:> I am involved in a project where one of the aims is to > study the effects of different parallelization strategies > on efficiency, power consumption etc. The idea is to > do automated design space exploration by varying some > parameters (e.g. number of tasks) and measuring their effect. > > Since we are already using LLVM for other purposes,cool. Is it listed at http://llvm.org/Users.html ?> we thought > about using LLVM for analysis and then OpenMP for compilation. > The idea was to use the LLVM back end to spit out C code with > OpenMP directives. However, looking at the C code that llc > produces, it seems that this might be a non-starter, as loops > have already been turned into gotos in the generated C. > > I suspect we may need to do something else, but if anyone has > any bright ideas on how to use LLVM for this purpose, I'd be > very grateful.If you're using llvm-gcc-4.0 to get llvm bitcode for analysis then front-end is ignoring OpenMP pragmas. if you're trying to use llvm- gcc-4.2 then most likely it won't work, because llvm bitcode emitter has not been updated to handle OpenMP. If you're getting llvm bitcode (without going through llvm-gcc) and somehow annotating it with OpenMP instructions (I don't know how) then also I CBackend, which is used by llc, won't be able to handle it at the moment. In simple words, LLVM is not OpenMP ready yet. The easiest route would be to update llvm bitcode converter in llvm- gcc-4.2 such that llvm bitcode converter operates on GCC trees after OpenMP lowering phase is executed. If you're interested, we welcome contribution on OpenMP front. - Devang
Devang Patel wrote:> cool. Is it listed at http://llvm.org/Users.html ?Doesn't seem to be. I'll have to prod the guys.> If you're using llvm-gcc-4.0 to get llvm bitcode for analysis then > front-end is ignoring OpenMP pragmas. if you're trying to use llvm- > gcc-4.2 then most likely it won't work, because llvm bitcode emitter > has not been updated to handle OpenMP. If you're getting llvm > bitcode (without going through llvm-gcc) and somehow annotating it > with OpenMP instructions (I don't know how) then also I CBackend, > which is used by llc, won't be able to handle it at the moment.Thanks for the information. The vague idea was to annotate bitcode with OpenMP instructions or maybe modify OpenMP instructions present in the original source. But it seems that this would not be possible at least in a straightforward fashion.> If you're interested, we welcome contribution on OpenMP front.We'd be happy to contribute, if something eventually comes out. -- Pertti
Hi, Pertti Kellomäki wrote:> Since we are already using LLVM for other purposes, we thought > about using LLVM for analysis and then OpenMP for compilation. > The idea was to use the LLVM back end to spit out C code with > OpenMP directives. However, looking at the C code that llc > produces, it seems that this might be a non-starter, as loops > have already been turned into gotos in the generated C. > > I suspect we may need to do something else, but if anyone has > any bright ideas on how to use LLVM for this purpose, I'd be > very grateful.I have some ideas, but I'm not sure if they are bright...:) 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 achieve? If you know a loop is parallelizable, it is possible, in general, in LLVM to extract it (its blocks) into a new function. In the place of the original loop a code spawning some threads calling this new function can be inserted. Each function call gets different iteration range for the loop. If you're interested I can send you a very simplified but working example that demonstrates it (it's about 500 lines). --Wojtek
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