[LLVMdev] Loop rotation and loop inversion in LLVM?

[Paul Sokolovsky]

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:pmi...@gmail.com
_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Andrew Trick]

On May 16, 2013, at 5:07 PM, Paul Sokolovsky <pmi...@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