[llvm-dev] Question about Unrolling Loop with Multiple Exits
Jingu Kang via llvm-dev
llvm-dev at lists.llvm.org
Fri Jul 16 12:09:42 PDT 2021
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>
More information about the llvm-dev
mailing list