Renato Golin
2015-Jun-03 20:13 UTC
[LLVMdev] Replacing a repetitive sequence of code with a loop
On 3 June 2015 at 19:57, Benjamin Kramer <benny.kra at gmail.com> wrote:> There's a loop reroll pass in LLVM trunk that should do exactly this transformation.Though that's a loop pass (runOnLoop). What you could do is add a previous pass that would recognize the pattern and create a loop of 1 iteration around the code and then run the reroll pass. If your pattern recognition is too good, it'll be redundant with the reroll pass, so I'm not sure how to do that without duplicating effort or destroying the IR (in case you're wrong). Adding 1-iteration loops to all functions won't work either. You'll have to balance the heuristics and make the pass optional, maybe with a pragma to help the compiler. cheers, --renato
Philip Reames
2015-Jun-03 20:28 UTC
[LLVMdev] Replacing a repetitive sequence of code with a loop
On 06/03/2015 01:13 PM, Renato Golin wrote:> On 3 June 2015 at 19:57, Benjamin Kramer <benny.kra at gmail.com> wrote: >> There's a loop reroll pass in LLVM trunk that should do exactly this transformation. > Though that's a loop pass (runOnLoop). What you could do is add a > previous pass that would recognize the pattern and create a loop of 1 > iteration around the code and then run the reroll pass.This sounds like we should need a separate pass which forms loops from straight line code. I would strongly suggest only forming loops when you can find at least two iterations. We can probably share most of the code with the existing reroller, but the wrapper pass needs a slightly different interface.> > If your pattern recognition is too good, it'll be redundant with the > reroll pass, so I'm not sure how to do that without duplicating effort > or destroying the IR (in case you're wrong). Adding 1-iteration loops > to all functions won't work either. You'll have to balance the > heuristics and make the pass optional, maybe with a pragma to help the > compiler. > > cheers, > --renato > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Frank Winter
2015-Jun-03 22:26 UTC
[LLVMdev] Replacing a repetitive sequence of code with a loop
Ok, I will do some code reading;the reroll pass seems seems a good
starting point.
Renato, thanks for the hint that this is actually a loop pass! You're
right that it's not always beneficial to roll things up. However in this
particular case I don't worry about insisting to roll the code into a
loop no matter what, i.e. not looking at heuristics etc. In the given
application it will always be beneficial to roll it, this is an a priori
assumption.(the example I posted is far smaller than what the
application generates).
All functions are generated at runtime with the builder (I am not coming
from a higher level language). Thus, I could embed the whole function in
a loop with one iteration. I will probably try this, just to see what
the reroll pass thinks about it.It will not solve everything. In real
world code the code junks can become quite large (over 1000
instructions) and I doubt that the reroller can handle that in it's
current state.
There's onemore thing.The resulting loops will have high iteration
counts so that it would make sense to use all available CPU cores and
distribute the iterations among them. As far as I can see it, threading
must be taken care of 'outside of the LLVM IR', right? Coming from the
shown code, I would need a mechanism that modifies the starting and
ending iteration of the loop and exposes those as arguments to the
function, right? Aka,
define void @vec_plus_vec(int %start_iteration, int %end_iteration,
float* noalias %arg0, float* noalias %arg1, float* noalias %arg2) {
entrypoint:
and from the calling code (OMP probably) call the function from each thread with
thread number matching start/stop parameters. Does anyone see any other solution
to threading than this?
Thanks,
Frank
On 06/03/2015 04:28 PM, Philip Reames wrote:>
>
> On 06/03/2015 01:13 PM, Renato Golin wrote:
>> On 3 June 2015 at 19:57, Benjamin Kramer <benny.kra at gmail.com>
wrote:
>>> There's a loop reroll pass in LLVM trunk that should do exactly
this
>>> transformation.
>> Though that's a loop pass (runOnLoop). What you could do is add a
>> previous pass that would recognize the pattern and create a loop of 1
>> iteration around the code and then run the reroll pass.
> This sounds like we should need a separate pass which forms loops from
> straight line code. I would strongly suggest only forming loops when
> you can find at least two iterations. We can probably share most of
> the code with the existing reroller, but the wrapper pass needs a
> slightly different interface.
>>
>> If your pattern recognition is too good, it'll be redundant with
the
>> reroll pass, so I'm not sure how to do that without duplicating
effort
>> or destroying the IR (in case you're wrong). Adding 1-iteration
loops
>> to all functions won't work either. You'll have to balance the
>> heuristics and make the pass optional, maybe with a pragma to help the
>> compiler.
>>
>> cheers,
>> --renato
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Frank Winter
2015-Jun-03 22:28 UTC
[LLVMdev] Replacing a repetitive sequence of code with a loop
Sorry for the spam. I think my mailer screws up badly. Frank On 06/03/2015 06:22 PM, Frank Winter wrote:> Ok, I will do some code reading;the reroll pass seems seems a good > starting point. > > Renato, thanks for the hint that this is actually a loop pass! You're > right that it's not always beneficial to roll things up. However in > this particular case I don't worry about insisting to roll the code > into a loop no matter what, i.e. not looking at heuristics etc. In the > given application it will always be beneficial to roll it, this is an > a priori assumption.(the example I posted is far smaller than what the > application generates). > > All functions are generated at runtime with the builder (I am not > coming from a higher level language). Thus, I could embed the whole > function in a loop with one iteration. I will probably try this, just > to see what the reroll pass thinks about it.It will not solve > everything. In real world code the code junks can become quite large > (over 1000 instructions) and I doubt tha > > There's onemore thing.The resulting loops will have high iteration > counts so that it would make sense to use all available CPU cores and > distribute the iterations among the cores. As far as I can see > threading must be taken care of 'outside of the LLVM IR', right? > Coming from the shown code, I would need an mechanism that modifies > the starting and ending iteration of the loop and exposes those as > arguments to the function, right? Aka, > > define void @vec_plus_vec(int %start_iteration, int %end_iteration, float* noalias %arg0, float* noalias %arg1, float* noalias %arg2) { > entrypoint: > > and then call the function from each thread with thread number matching start/stop parameters. > > Does anyone see any other solution to threading than this? > > Thanks, > Frank > > > > > > > On 06/03/2015 04:28 PM, Philip Reames wrote: >> >> >> On 06/03/2015 01:13 PM, Renato Golin wrote: >>> On 3 June 2015 at 19:57, Benjamin Kramer <benny.kra at gmail.com> wrote: >>>> There's a loop reroll pass in LLVM trunk that should do exactly >>>> this transformation. >>> Though that's a loop pass (runOnLoop). What you could do is add a >>> previous pass that would recognize the pattern and create a loop of 1 >>> iteration around the code and then run the reroll pass. >> This sounds like we should need a separate pass which forms loops >> from straight line code. I would strongly suggest only forming loops >> when you can find at least two iterations. We can probably share >> most of the code with the existing reroller, but the wrapper pass >> needs a slightly different interface. >>> >>> If your pattern recognition is too good, it'll be redundant with the >>> reroll pass, so I'm not sure how to do that without duplicating effort >>> or destroying the IR (in case you're wrong). Adding 1-iteration loops >>> to all functions won't work either. You'll have to balance the >>> heuristics and make the pass optional, maybe with a pragma to help the >>> compiler. >>> >>> cheers, >>> --renato >>> _______________________________________________ >>> LLVM Developers mailing list >>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > -- > ---------------------------------------------- > Dr Frank Winter, Staff Scientist > Thomas Jefferson National Accelerator Facility > 12000 Jefferson Ave, Newport News, 23606, USA > +1-757-269-6448,fwinter at jlab.org > ------------------------------------------------ ---------------------------------------------- Dr Frank Winter, Staff Scientist Thomas Jefferson National Accelerator Facility 12000 Jefferson Ave, Newport News, 23606, USA +1-757-269-6448, fwinter at jlab.org ---------------------------------------------- -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150603/11957324/attachment.html>