[llvm-dev] questionabout loop rotation

[林政宗 via llvm-dev]

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>