llvm dev - May 2013 - [LLVMdev] Loop rotation and loop inversion in LLVM?

Hello,

I'd be interested in knowing which pass performs loop inversion, i.e.
transforms while loop into do/while wrapped with if. So, it's pretty
easy to understand concept, http://en.wikipedia.org/wiki/Loop_inversion
provides description of how its done and motivation, googling gives
several relevant references, i.e. it's pretty settled term.

I also see this transform to be actually performed on trivial strlen
function by clang -O2. However opt --help or grepping LLVM doesn't give
any hints.

However, -loop-rotate calls attention, described as "A simple loop
rotation transformation." However, Wikipedia doesn't gives hits for
that related to compilation/optimization theory, nor google hits are
relevant either - mostly LLVM-related hits just mentioning the term.

Trying -loop-rotate, I see loop being converted to post-condition, but
don't see if wrapper around it.

So, can anyone suggest if LLVM loop rotation is related to loop
inversion in Wikipedia terms, and if not, what it is.

And I hope that this feedback will allow maintainers to make
documentation clearer and more user-friendly.


Thanks,
 Paul                          mailto:pmiscml at gmail.com

On May 16, 2013, at 5:07 PM, Paul Sokolovsky <pmiscml at gmail.com> wrote:
> Hello,
> 
> I'd be interested in knowing which pass performs loop inversion, i.e.
> transforms while loop into do/while wrapped with if. So, it's pretty
> easy to understand concept, http://en.wikipedia.org/wiki/Loop_inversion
> provides description of how its done and motivation, googling gives
> several relevant references, i.e. it's pretty settled term.
> 
> I also see this transform to be actually performed on trivial strlen
> function by clang -O2. However opt --help or grepping LLVM doesn't give
> any hints.
> 
> However, -loop-rotate calls attention, described as "A simple loop
> rotation transformation." However, Wikipedia doesn't gives hits
for
> that related to compilation/optimization theory, nor google hits are
> relevant either - mostly LLVM-related hits just mentioning the term.
> 
> Trying -loop-rotate, I see loop being converted to post-condition, but
> don't see if wrapper around it.
> 
> So, can anyone suggest if LLVM loop rotation is related to loop
> inversion in Wikipedia terms, and if not, what it is.
On simple ‘for’ loops, rotation degenerates to inversion. Rotation is a more
general transform that spans the range from inversion to loop peeling...

loop:
A
br X
B
br loop, Y

A’
br X
loop:
B
br Y
A
br loop, X

Sorry I don’t know of a text-book reference off-hand. I’ve seen it in practice
before and assumed it was pretty standard. In LLVM it’s mostly used to put loops
in a canonical form, but it’s also a cheap and dirty way to expose LICM. Another
benefit is simplifying trip count expressions.
> And I hope that this feedback will allow maintainers to make
> documentation clearer and more user-friendly.
Me too :) Not sure if I’ll get around to it, but I’d be happy to review a patch.

-Andy
> Thanks,
> Paul                          mailto:pmiscml at gmail.com
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130520/49bb14f9/attachment.html>