llvm dev - Mar 2007 - [LLVMdev] Back end loop invariant opt

Hi All,

It seems to me that there is potential for doing some target  
independent loop invariant optimizations in the back end, but prior  
to instruction selection. For instance, I noticed that the loop  
invariant constant generated for a loop bounds check is still stuck  
inside the loop. Likewise constant address generated for globals  
accessed within a loop are generated on each iteration, even though  
they are invariant.

I'm most familiar with LLVM's target interface and code gen and I'm
not fully up to speed on the optimization framework. Is there an  
existing optimization pass that handles these cases that I've failed  
to properly enable or hook into? Is there something that inherently  
prevents these from being target independent optimizations, requiring  
a target specific opt pass? Is this simply an optimization pass that  
hasn't been implemented yet, but is a good idea?

Thanks
--
Christopher Lamb
christopher.lamb at gmail.com


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20070324/75e58c54/attachment.html>

On Mar 25, 2007, at 2:21 AM, Chris Lattner wrote:
> On Sat, 24 Mar 2007, Christopher Lamb wrote:
>> It seems to me that there is potential for doing some target  
>> independent loop
>> invariant optimizations in the back end, but prior to instruction  
>> selection.
>
> I assume you mean after instruction selection?
I assumed that to be target independent the pass would need to be  
before instruction selection, but I guess if the pass more like the  
basic block/ branch analysis that would make sense.
>
>> For instance, I noticed that the loop invariant constant generated  
>> for a loop
>> bounds check is still stuck inside the loop. Likewise constant  
>> address
>> generated for globals accessed within a loop are generated on each  
>> iteration,
>> even though they are invariant.
>
> Yes, this is a known issue.  The plan is to implement a machine- 
> code level
> pass that hoists machine instrs out of loops after instruction  
> selection
> has been performed.  This is important, because isel is the pass that
> exposes most of the issues that need hoisting (e.g. load immediate
> instructions, etc).
Isn't it possible to tell that certain DAG nodes are loop invariant  
prior to instruction selection, such as a constant or global address  
node?
>
>> I'm most familiar with LLVM's target interface and code gen and
>> I'm not fully
>> up to speed on the optimization framework. Is there an existing  
>> optimization
>> pass that handles these cases that I've failed to properly enable  
>> or hook
>> into? Is there something that inherently prevents these from being  
>> target
>> independent optimizations, requiring a target specific opt pass?  
>> Is this
>> simply an optimization pass that hasn't been implemented yet, but  
>> is a good
>> idea?
>
> The later.  On targets with few registers, LICM can be very bad.   
> Our plan
> is to implement rematerialization in the register allocator to  
> counteract
> this.  In any case, I think that LICM should definitely be done, and
> targets can choose to use it or not based on their register file,  
> before
> remat is done.
Is there more information (PR?) on the schedule for this work and who  
is involved? I may not be experienced enough to make much of a  
contribution yet, but I'd like to keep tabs on it.

--
Christopher Lamb
christopher.lamb at gmail.com


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20070325/9f26fc81/attachment.html>

On Sat, 24 Mar 2007, Christopher Lamb wrote:
> It seems to me that there is potential for doing some target independent
loop
> invariant optimizations in the back end, but prior to instruction
selection.
I assume you mean after instruction selection?
> For instance, I noticed that the loop invariant constant generated for a
loop
> bounds check is still stuck inside the loop. Likewise constant address 
> generated for globals accessed within a loop are generated on each
iteration,
> even though they are invariant.
Yes, this is a known issue.  The plan is to implement a machine-code level 
pass that hoists machine instrs out of loops after instruction selection 
has been performed.  This is important, because isel is the pass that 
exposes most of the issues that need hoisting (e.g. load immediate 
instructions, etc).
> I'm most familiar with LLVM's target interface and code gen and
I'm not fully
> up to speed on the optimization framework. Is there an existing
optimization
> pass that handles these cases that I've failed to properly enable or
hook
> into? Is there something that inherently prevents these from being target 
> independent optimizations, requiring a target specific opt pass? Is this 
> simply an optimization pass that hasn't been implemented yet, but is a
good
> idea?
The later.  On targets with few registers, LICM can be very bad.  Our plan 
is to implement rematerialization in the register allocator to counteract 
this.  In any case, I think that LICM should definitely be done, and 
targets can choose to use it or not based on their register file, before 
remat is done.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/