Jingu Kang via llvm-dev
2021-Jul-16 19:09 UTC
[llvm-dev] Question about Unrolling Loop with Multiple Exits
Sorry for poor example...
The AArch64 assembly output of the example from gcc is as below. The loop is
unrolled 7 times. I have written some comments to explain how the assembly code
is mapped to C source code. As you can see on `.L3` label, the 'if (*s++ !=
'\n')' block is unrolled 7 times.
stp x29, x30, [sp, -48]!
mov x29, sp
stp x19, x20, [sp, 16]
mov x19, x0 --> x19 is char *s
mov x20, x1 --> x20 is char *end
str x21, [sp, 32]
orr x21, x3, x2 --> x21 is check1 | check2
.L70:
sub x0, x20, x19 --> x0 = end - s;
add x1, x0, 1
ands x2, x1, 7 --> unroll count is 7
beq .L3 --> .L3 is inside while loop. if (*s++ !=
'\n')
cmp x19, x20 --> while(s <= end)
bhi .L2 --> .L2 is label ret1.
ldrb w3, [x19], 1 --> start of remainder
cmp w3, 10
beq .L71
cmp x2, 1
beq .L3
cmp x2, 2
beq .L49
cmp x2, 3
beq .L50
cmp x2, 4
beq .L51
cmp x2, 5
beq .L52
cmp x2, 6
beq .L53
ldrb w4, [x19], 1
cmp w4, 10
bne .L53
.L71:
cbz x21, .L4 --> if(check1 || check2)
bl foo()
mov x19, x0
cbz x0, .L2 --> if (!s) goto ret1;
.L4: --> if(boo(s)) goto ret0;
mov x0, x19
bl boo(char*)
cbz w0, .L70
mov w0, 0
ldp x19, x20, [sp, 16]
ldr x21, [sp, 32]
ldp x29, x30, [sp], 48
ret
.L53: --> if (*s++ != '\n') for remainder
ldrb w5, [x19], 1
cmp w5, 10
beq .L71
.L52: --> if (*s++ != '\n') for remainder
ldrb w6, [x19], 1
cmp w6, 10
beq .L71
.L51: --> if (*s++ != '\n') for remainder
ldrb w7, [x19], 1
cmp w7, 10
beq .L71
.L50: --> if (*s++ != '\n') for remainder
ldrb w8, [x19], 1
cmp w8, 10
beq .L71
.L49: --> if (*s++ != '\n') for remainder
ldrb w9, [x19], 1
cmp w9, 10
beq .L71
.L3: --> if (*s++ != '\n'), 7 times unrolled
cmp x19, x20
bhi .L2
ldrb w10, [x19]
add x19, x19, 1
mov x11, x19
cmp w10, 10
beq .L71
ldrb w12, [x19], 1
cmp w12, 10
beq .L71
ldrb w13, [x11, 1]
add x19, x11, 2
cmp w13, 10
beq .L71
ldrb w14, [x11, 2]
add x19, x11, 3
cmp w14, 10
beq .L71
ldrb w15, [x11, 3]
add x19, x11, 4
cmp w15, 10
beq .L71
ldrb w16, [x11, 4]
add x19, x11, 5
cmp w16, 10
beq .L71
ldrb w17, [x11, 5]
add x19, x11, 6
cmp w17, 10
beq .L71
ldrb w18, [x11, 6]
add x19, x11, 7
cmp w18, 10
beq .L71
b .L3
.L2: --> label ret1
mov w0, 1
ldp x19, x20, [sp, 16]
ldr x21, [sp, 32]
ldp x29, x30, [sp], 48
ret
I am sorry for showing you assembly output directly... It looks like the rtl
level's unroll pass of gcc unrolls above loop and I need to check it next
week. Once I have clear idea about above unrolling from gcc, let me reduce the
example more and let you know.
Thanks
JinGu Kang
From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Philip
Reames via llvm-dev
Sent: 16 July 2021 18:27
To: Jingu Kang <Jingu.Kang at arm.com>
Cc: llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] Question about Unrolling Loop with Multiple Exits
On 7/16/21 9:29 AM, Jingu Kang wrote:
Hi Philip,
Thanks for your kind reply.
> A) Are you measuring on tip of tree?� There were changes for multiple
exit unrolling which landed very recently.
Yep, I am investigating benchmarks with llvm tip and I can see the llvm fails to
unroll some loops with multiple exits.> B) One of your exits does not dominate your latch.� Those are generally
hard
> C) This example does not seem to require gotos.� I strongly suggest
reducing your test cases if you want more informed commentary.�
�
I am looking at perlbench recently and it has `goto` statements inside loop. The
example is a reduced case.
Right, but the gotos aren't relevant for your reduced test.� You can
reduce further.
When I look at the gcc�s output of the example, it looks like gcc unrolls only
the below `if` statement block�
�
��� if (*s++ != '\n')
����� continue;
Your phrasing here does not parse for me.� Can you restate this with different
wording and maybe a fully worked example?
�
Thanks
JinGu Kang
�
From: llvm-dev <llvm-dev-bounces at
lists.llvm.org><mailto:llvm-dev-bounces at lists.llvm.org> On Behalf Of
Philip Reames via llvm-dev
Sent: 16 July 2021 15:52
To: Jingu Kang <Jingu.Kang at arm.com><mailto:Jingu.Kang at
arm.com>; llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] Question about Unrolling Loop with Multiple Exits
�
A) Are you measuring on tip of tree?� There were changes for multiple exit
unrolling which landed very recently.
B) One of your exits does not dominate your latch.� Those are generally
hard.�
C) This example does not seem to require gotos.� I strongly suggest reducing
your test cases if you want more informed commentary.�
Philip
On 7/16/21 7:42 AM, Jingu Kang via llvm-dev wrote:
Hi All,
�
While I am investigating benchmarks, I have found loops which llvm fails to
unroll because the loops have multiple exits.
For example,
�
char *foo(void);
int boo(char *s);
�
int test(char *s, char *end, char *check1, char *check2) {
� while (s <= end) {
��� if (*s++ != '\n')
����� continue;
��� if (check1 || check2) {
����� s = foo();
����� if (!s)
������� goto ret1;
��� }��
����if (boo(s))
����� goto ret0;
� }
� goto ret1;
�
ret0:
� return 0;
ret1:
� return 1;
}
�
Above code causes below messages from LoopUnroll pass.
�
Bailout for multi-exit handling when latch exit has >1 predecessor.
Multiple exit/exiting blocks in loop and multi-exit unrolling not enabled!
�
I can see the option `unroll-runtime-multi-exit` and comments about it. I wonder
there are already reviews for the work on phabriactor or some people are working
on it.
If someone knows information about it, please share it.
�
Thanks
JinGu Kang
�
�
�
�
�
�
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto: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/20210716/21350135/attachment.html>
Philip Reames via llvm-dev
2021-Jul-16 19:11 UTC
[llvm-dev] Question about Unrolling Loop with Multiple Exits
Jingu, I'm not fluent in AArch64 assembly, sorry. If you want more meaningful commentary, you'll need to reduce your c++ example further, and give a better explanation of what you expect the unroller to do for you. Philip On 7/16/21 12:09 PM, Jingu Kang wrote:> > Sorry for poor example… > > The AArch64 assembly output of the example from gcc is as below. The > loop is unrolled 7 times. I have written some comments to explain how > the assembly code is mapped to C source code. As you can see on `.L3` > label, the ‘if (*s++ != '\n')’ block is unrolled 7 times. > > stp x29, x30, [sp, -48]! > > mov x29, sp > > stp x19, x20, [sp, 16] > > mov x19, x0 --> x19 is char *s > > mov x20, x1 --> x20 is char *end > > str x21, [sp, 32] > > orr x21, x3, x2 --> x21 is check1 | check2 > > .L70: > > sub x0, x20, x19 --> x0 = end - s; > > add x1, x0, 1 > > ands x2, x1, 7 --> unroll count is 7 > > beq .L3 --> .L3 is inside while loop. if (*s++ != '\n') > > cmp x19, x20 --> while(s <= end) > > bhi .L2 --> .L2 is label ret1. > > ldrb w3, [x19], 1 --> start of remainder > > cmp w3, 10 > > beq .L71 > > cmp x2, 1 > > beq .L3 > > cmp x2, 2 > > beq .L49 > > cmp x2, 3 > > beq .L50 > > cmp x2, 4 > > beq .L51 > > cmp x2, 5 > > beq .L52 > > cmp x2, 6 > > beq .L53 > > ldrb w4, [x19], 1 > > cmp w4, 10 > > bne .L53 > > .L71: > > cbz x21, .L4 --> if(check1 || check2) > > bl foo() > > mov x19, x0 > > cbz x0, .L2 --> if (!s) goto ret1; > > .L4: --> if(boo(s)) goto ret0; > > mov x0, x19 > > bl boo(char*) > > cbz w0, .L70 > > mov w0, 0 > > ldp x19, x20, [sp, 16] > > ldr x21, [sp, 32] > > ldp x29, x30, [sp], 48 > > ret > > .L53: --> if (*s++ != '\n') for remainder > > ldrb w5, [x19], 1 > > cmp w5, 10 > > beq .L71 > > .L52: --> if (*s++ != '\n') for remainder > > ldrb w6, [x19], 1 > > cmp w6, 10 > > beq .L71 > > .L51: --> if (*s++ != '\n') for remainder > > ldrb w7, [x19], 1 > > cmp w7, 10 > > beq .L71 > > .L50: --> if (*s++ != '\n') for remainder > > ldrb w8, [x19], 1 > > cmp w8, 10 > > beq .L71 > > .L49: --> if (*s++ != '\n') for remainder > > ldrb w9, [x19], 1 > > cmp w9, 10 > > beq .L71 > > .L3: --> if (*s++ != '\n'), 7 times unrolled > > cmp x19, x20 > > bhi .L2 > > ldrb w10, [x19] > > add x19, x19, 1 > > mov x11, x19 > > cmp w10, 10 > > beq .L71 > > ldrb w12, [x19], 1 > > cmp w12, 10 > > beq .L71 > > ldrb w13, [x11, 1] > > add x19, x11, 2 > > cmp w13, 10 > > beq .L71 > > ldrb w14, [x11, 2] > > add x19, x11, 3 > > cmp w14, 10 > > beq .L71 > > ldrb w15, [x11, 3] > > add x19, x11, 4 > > cmp w15, 10 > > beq .L71 > > ldrb w16, [x11, 4] > > add x19, x11, 5 > > cmp w16, 10 > > beq .L71 > > ldrb w17, [x11, 5] > > add x19, x11, 6 > > cmp w17, 10 > > beq .L71 > > ldrb w18, [x11, 6] > > add x19, x11, 7 > > cmp w18, 10 > > beq .L71 > > b .L3 > > .L2: --> label ret1 > > mov w0, 1 > > ldp x19, x20, [sp, 16] > > ldr x21, [sp, 32] > > ldp x29, x30, [sp], 48 > > ret > > I am sorry for showing you assembly output directly… It looks like the > rtl level’s unroll pass of gcc unrolls above loop and I need to check > it next week. Once I have clear idea about above unrolling from gcc, > let me reduce the example more and let you know. > > Thanks > > JinGu Kang > > *From:* llvm-dev <llvm-dev-bounces at lists.llvm.org> *On Behalf Of > *Philip Reames via llvm-dev > *Sent:* 16 July 2021 18:27 > *To:* Jingu Kang <Jingu.Kang at arm.com> > *Cc:* llvm-dev at lists.llvm.org > *Subject:* Re: [llvm-dev] Question about Unrolling Loop with Multiple > Exits > > On 7/16/21 9:29 AM, Jingu Kang wrote: > > Hi Philip, > > Thanks for your kind reply. > > > A) Are you measuring on tip of tree?� There were changes for > multiple exit unrolling which landed very recently. > > Yep, I am investigating benchmarks with llvm tip and I can see the > llvm fails to unroll some loops with multiple exits. > > > B) One of your exits does not dominate your latch.� Those are > generally hard > > > C) This example does not seem to require gotos.� I strongly > suggest reducing your test cases if you want more informed > commentary.� > > � > > I am looking at perlbench recently and it has `goto` statements > inside loop. The example is a reduced case. > > Right, but the gotos aren't relevant for your reduced test.� You can > reduce further. > > When I look at the gcc�s output of the example, it looks like > gcc unrolls only the below `if` statement block� > > � > > ��� if (*s++ != '\n') > > ����� continue; > > Your phrasing here does not parse for me.� Can you restate this with > different wording and maybe a fully worked example? > > � > > Thanks > > JinGu Kang > > � > > *From:* llvm-dev <llvm-dev-bounces at lists.llvm.org> > <mailto:llvm-dev-bounces at lists.llvm.org> *On Behalf Of *Philip > Reames via llvm-dev > *Sent:* 16 July 2021 15:52 > *To:* Jingu Kang <Jingu.Kang at arm.com> <mailto:Jingu.Kang at arm.com>; > llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> > *Subject:* Re: [llvm-dev] Question about Unrolling Loop with > Multiple Exits > > � > > A) Are you measuring on tip of tree?� There were changes for > multiple exit unrolling which landed very recently. > > B) One of your exits does not dominate your latch.� Those are > generally hard.� > > C) This example does not seem to require gotos.� I strongly > suggest reducing your test cases if you want more informed > commentary.� > > Philip > > On 7/16/21 7:42 AM, Jingu Kang via llvm-dev wrote: > > Hi All, > > � > > While I am investigating benchmarks, I have found loops which > llvm fails to unroll because the loops have multiple exits. > > For example, > > � > > char *foo(void); > > int boo(char *s); > > � > > int test(char *s, char *end, char *check1, char *check2) { > > � while (s <= end) { > > ��� if (*s++ != '\n') > > ����� continue; > > ��� if (check1 || check2) { > > ����� s = foo(); > > ����� if (!s) > > ������� goto ret1; > > ��� }�� > > ����if (boo(s)) > > ����� goto ret0; > > � } > > � goto ret1; > > � > > ret0: > > � return 0; > > ret1: > > � return 1; > > } > > � > > Above code causes below messages from LoopUnroll pass. > > � > > Bailout for multi-exit handling when latch exit has >1 > predecessor. > > Multiple exit/exiting blocks in loop and multi-exit unrolling > not enabled! > > � > > I can see the option `unroll-runtime-multi-exit` and comments > about it. I wonder there are already reviews for the work on > phabriactor or some people are working on it. > > If someone knows information about it, please share it. > > � > > Thanks > > JinGu Kang > > � > > � > > � > > � > > � > > � > > > > > _______________________________________________ > > LLVM Developers mailing list > > llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> > > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <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/20210716/003b4b1c/attachment.html>