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 Trickatrick at apple.com Mon May 20 10:36:00 PDT 2013 Previous message: [LLVMdev] Loop rotation and loop inversion in LLVM? Next message: [LLVMdev] Vararg Intrinsics still supported? Messages sorted by:[ date ][ thread ][ subject ][ author ] 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.eduhttp://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> -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200320/b07ff28e/attachment.html>
Johannes Doerfert via llvm-dev
2020-Mar-20 07:25 UTC
[llvm-dev] questionabout loop rotation
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 />/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 / > -------------- next part -------------- > An HTML attachment was scrubbed... > URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130520/49bb14f9/attachment.html> > ** > > > > > _______________________________________________ > 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/20200320/30675d16/attachment-0001.html>
Stefanos Baziotis via llvm-dev
2020-Mar-20 11:54 UTC
[llvm-dev] questionabout loop rotation
Hi Jerry, I also didn't understand the example. Note that very recently, documentation about loop terminology was added to the loop terminology: https://llvm.org/docs/LoopTerminology.html#rotated-loops. We tried to do it in a tutorial style so it may help. If it does not answer your question, please post the LLVM IR example. Kind regards, Stefanos Στις Παρ, 20 Μαρ 2020 στις 9:26 π.μ., ο/η Johannes Doerfert via llvm-dev < llvm-dev at lists.llvm.org> έγραψε:> 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/20200320/fe1b445d/attachment.html>
Hi,
sorry for not describing it clearly. I modified a simple generated IR for
for-loop. The example is as below:
---------------------------------------------------------------------------------------------------------------------
; Function Attrs: noinline nounwind optnone
define dso_local i32 @test(i32 %max, i32 %cmp1, i32 %cmp2) #0 {
entry:
%max.addr = alloca i32, align 4
%cmp1.addr = alloca i32, align4
%cmp2.addr = alloca i32, align4
%result = alloca i32, align 4
%i = alloca i32, align 4
store i32 %max, i32* %max.addr, align 4
store i32 0, i32* %result, align 4
store i32 0, i32* %i, align 4
br label %for.cond
for.cond: ; preds = %for.inc, %entry
%0 = load i32, i32* %i, align 4
%1 = load i32, i32* %max.addr, align 4
%cmp = icmp sle i32 %0, %1
br i1 %cmp, label %for.body, label %for.end
for.cond.2:
%6 = load i32, i32* %cmp1.addr, align4
%7 = load i32, i32* %cmp2.addr, align4
%cmp.2 = icmp sle i32 %6, %7
br i1 %cmp.2, label %for.body, label %for.end
for.body: ; preds = %for.cond
%2 = load i32, i32* %i, align 4
%3 = load i32, i32* %result, align 4
%add = add nsw i32 %3, %2
store i32 %add, i32* %result, align 4
br label %for.inc
for.inc: ; preds = %for.body
%4 = load i32, i32* %i, align 4
%inc = add nsw i32 %4, 1
store i32 %inc, i32* %i, align 4
br label %for.cond
for.end: ; preds = %for.cond
%5 = load i32, i32* %result, align 4
ret i32 %5
}
---------------------------------------------------------------------------------------------------------------------
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 Trickatrick at apple.com Mon May 20 10:36:00 PDT 2013
Previous message: [LLVMdev] Loop rotation and loop inversion in LLVM?
Next message: [LLVMdev] Vararg Intrinsics still supported?
Messages sorted by:[ date ][ thread ][ subject ][ author ]
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.eduhttp://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>
_______________________________________________
LLVM Developers mailing list
llvm-dev at
lists.llvm.orghttps://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/943a4636/attachment-0001.html>
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 Trickatrick at apple.com Mon May 20 10:36:00 PDT 2013 Previous message: [LLVMdev] Loop rotation and loop inversion in LLVM? Next message: [LLVMdev] Vararg Intrinsics still supported? Messages sorted by:[ date ][ thread ][ subject ][ author ] 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.eduhttp://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> _______________________________________________ LLVM Developers mailing list llvm-dev at lists.llvm.orghttps://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/17af1205/attachment.html>