thr3ads.net - llvm dev - [llvm-dev] Question about Unrolling Loop with Multiple Exits [Jul 2021]

If this information is useful, please help other people find it:
Share via:

Philip Reames via llvm-dev

2021-Jul-16 17:26 UTC

[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> *On Behalf Of 
> *Philip Reames via llvm-dev
> *Sent:* 16 July 2021 15:52
> *To:* Jingu Kang <Jingu.Kang at arm.com>; 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/ef2cd4c8/attachment.html>

Jingu Kang via llvm-dev

2021-Jul-16 19:09 UTC

head link

[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>

llvm dev - Jul 2021 - Question about Unrolling Loop with Multiple Exits

[llvm-dev] Question about Unrolling Loop with Multiple Exits

[llvm-dev] Question about Unrolling Loop with Multiple Exits