[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