[llvm-dev] questionabout loop rotation

Mon Mar 23 20:07:41 PDT 2020

Hi Jerry,

First of all, it's useful if you send the examples in https://godbolt.org/.
It's useful for you too, because you can run llvm parts remotely.
Second, it's useful if you pass your examples through a pass like -sroa [1]
or -mem2reg [2] so that you can have a code
that follows SSA kind flow (i.e. using PHI nodes) and not memory kind flow
(i.e. using loads and stores).
Probably your example came straight out of Clang which generates the
simplest possible IR.

If you put your example through -sroa, you will end with something like
that: https://godbolt.org/z/EKW_YQ
I also removed the BB %for.cond.2 because it was unused (you can actually
see that it has no preds).
Same for %cmp1 and %cmp2. Finally, I put the C equivalent code on the top.

Ok now, what loop rotation will do. You can see that in godbolt actually by
passing the -loop-rotate argument.
But let's understand more. If you read the loop terminology part I
referenced above, you can see that loop rotation
converts loops to do-while loops. So, this is what we expect. We also
expect that it will insert a guard.
Because it can't guarantee in any way that the loop will execute at least
once.

Here's the output: https://godbolt.org/z/FTced-

At the LLVM IR level there are a couple of important things. First of all,
the check was previously on the "top"
(which is the header which is the BB of the loop that dominates all others)
while now has been moved to the "bottom"
(i.e. the latch, which is the block that branches back to the header).

There is also another thing that happened: The loop is simplified. You can
read when a loop is simplified
in the loop terminology. It was before, because the %entry was the
preheader, it had a latch
and it had dedicated exists. But loop rotation broke that, so it had to
re-simplify it. In that case,
it inserted 2 blocks: for.body.lr.ph, so that the loop has a preheader.
Also, for.cond.for.end_crit_edge, so that the loop has dedicated exists.
Because otherwise,
an exiting block of the loop jumps to %for.end but also %entry jumps there,
which is not part of the loop.

Although in this case this block also acts as an LCSSA closing phi node but
that's another story.
I'll not go into that because there's no doc yet.

This is not a representative case of loop rotation because it does not
really enable other optimizations
that e.g. could hoist things into the preheader because they know that the
loop is executed at least
once (check the loop terminology examples in the end).

As for loop peeling, I don't think there's a specific pass that does that.
There's a part of loop unrolling
that does loop peeling but I think it needs PGO last time I saw. I don't
think loop peeling in this
loop would do anything. It doesn't seem to be anything interesting to do
here. If you had a comparison
inside, like let's say if (i < 2), _then_ it could start doing very
interesting things. Consider
that loop rotation, because of the guard, will guarantee that the loop will
execute at least once.
So then you can peel off the first 2 iterations outside (and before) the
loop (but inside the guard) and remove this if
completely.

Btw, off-topic but you might want to see what -indvars does to this loop.
It's one of the amazing cases
that a O(n) algorithm is converted to O(1).

Best,
Stefanos

[1] https://llvm.org/docs/Passes.html#sroa-scalar-replacement-of-aggregates
[2] https://llvm.org/docs/Passes.html#mem2reg-promote-memory-to-register

Στις Τρί, 24 Μαρ 2020 στις 3:43 π.μ., ο/η 林政宗 via llvm-dev <
llvm-dev at lists.llvm.org> έγραψε:

> Hi,
> Johannes
>
> Maybe I'm not that clear, my question is how the loop rotation pass would
> transform the example I sent you before.
> what would loop rotation do? And what would loop peeling do?
>
> Thanks,
> Jerry
>
>
>
>
>
>
> At 2020-03-20 15:25:28, "Johannes Doerfert" <johannesdoerfert at gmail.com>
> wrote:
>
> Hi Jerry,
>
>
> I cannot follow your example nor do I understand your question.
>
> Could you please post a minimal but complete LLVM-IR example and rephrase
> the question.
>
>
> Thanks,
>
>   Johannes
>
>
>
> On 3/19/20 8:47 PM, 林政宗 via llvm-dev wrote:
>
> Hi,
> I have read an email from the mail list. And I have a question about loop
> rotation. What is it if it is the case below.
> --------------------------------------------------------------------------
> loop:
> A br X B br Y C br loop, Z
> ------------------------------------------------- Thanks! Jerry [LLVMdev]
> Loop rotation and loop inversion in LLVM? *Andrew Trick* atrick at
> apple.com *Mon May 20 10:36:00 PDT 2013*
>
>    - Previous message: [LLVMdev] Loop rotation and loop inversion in
>    LLVM? <http://lists.llvm.org/pipermail/llvm-dev/2013-May/062185.html>
>    - Next message: [LLVMdev] Vararg Intrinsics still supported?
>    <http://lists.llvm.org/pipermail/llvm-dev/2013-May/062186.html>
>    - *Messages sorted by:* [ date ]
>    <http://lists.llvm.org/pipermail/llvm-dev/2013-May/date.html#62260> [
>    thread ]
>    <http://lists.llvm.org/pipermail/llvm-dev/2013-May/thread.html#62260> [
>    subject ]
>    <http://lists.llvm.org/pipermail/llvm-dev/2013-May/subject.html#62260> [
>    author ]
>    <http://lists.llvm.org/pipermail/llvm-dev/2013-May/author.html#62260>
>
> ------------------------------
>
> On May 16, 2013, at 5:07 PM, Paul Sokolovsky <pmiscml at gmail.com <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>> 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 <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 <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> *>* _______________________________________________
> *>* LLVM Developers mailing list
> *>* LLVMdev at cs.uiuc.edu <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>         http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/>
> *>* http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev <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>
>
>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing listllvm-dev at lists.llvm.orghttps://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200324/928a05a3/attachment.html>