Re: Question about loop induction variables

["Richard Biener via gcc" <gcc@gcc.gnu.org>]

On Sun, May 7, 2017 at 11:22 AM, Fredrik Hederstierna
<fredrik.hederstierna@verisure.com> wrote:
> Hi,
>
> I have a question about loop induction variables, related to
>
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67213
>
> Consider a simple loop like
>
>   int ix;
>   for (ix = 0; ix < 6; ix++) {
>     data[ix] = ix;
>   }
>
> In this case variable 'ix' is used as counting variable for array index,
> but also used as value for storage, so in some sense its used in two different "ways".
>
> Several target architectures might have support to auto-increment pointer registers when storing or reading data,
> but if same variable is used as both array index to pointer and as data it might be more complicated?
>
> In the example above, it seems like GCC loop analyzer (for completely peeling) thinks 'ix' is an induction variable that can be folded away:
> from 'tree-ssa-loop-ivcanon.c':
>
>   Loop 1 iterates 5 times.
>   Loop 1 iterates at most 5 times.
>   Estimating sizes for loop 1
>    BB: 3, after_exit: 0
>     size:   0 _4 = (char) i_9;
>      Induction variable computation will be folded away.
>     size:   1 data[i_9] = _4;
>     size:   1 i_6 = i_9 + 1;   <----- OK?
>      Induction variable computation will be folded away.
>     size:   1 ivtmp_7 = ivtmp_1 - 1;
>      Induction variable computation will be folded away.
>     size:   2 if (ivtmp_7 != 0)
>      Exit condition will be eliminated in peeled copies.
>    BB: 4, after_exit: 1
>   size: 5-4, last_iteration: 5-2
>     Loop size: 5
>     Estimated size after unrolling: 5
>
> Then index 'ix' is considered to be a induction variable, but possibly it cannot be simply folded since its used in other ways as well?

Well, but all the listed stmts _can_ be folded away because the
starting value is zero and thus they "fold away" to constants.

> Though completely-peeling loop resulted in longer code:
>
>
>   int i;
>   char _4;
>   unsigned int ivtmp_7;
>   char _12;
>   unsigned int ivtmp_15;
>   char _19;
>   unsigned int ivtmp_22;
>   char _26;
>   unsigned int ivtmp_29;
>   char _33;
>   unsigned int ivtmp_36;
>   char _40;
>   unsigned int ivtmp_43;
>
>   <bb 2>:
>   _12 = 0;
>   data[0] = _12;
>   i_14 = 1;
>   ivtmp_15 = 5;
>   _19 = (char) i_14;
>   data[i_14] = _19;
>   i_21 = i_14 + 1;
>   ivtmp_22 = ivtmp_15 + 4294967295;
>   _26 = (char) i_21;
>   data[i_21] = _26;
>   i_28 = i_21 + 1;
>   ivtmp_29 = ivtmp_22 + 4294967295;
>   _33 = (char) i_28;
>   data[i_28] = _33;
>   i_35 = i_28 + 1;
>   ivtmp_36 = ivtmp_29 + 4294967295;
>   _40 = (char) i_35;
>   data[i_35] = _40;
>   i_42 = i_35 + 1;
>   ivtmp_43 = ivtmp_36 + 4294967295;
>   _4 = (char) i_42;
>   data[i_42] = _4;
>   i_6 = i_42 + 1;
>   ivtmp_7 = ivtmp_43 + 4294967295;
>   return;
>
>
> instead of original and shorter
>
>   int i;
>   unsigned int ivtmp_1;
>   char _4;
>   unsigned int ivtmp_7;
>
>   <bb 2>:
>
>   <bb 3>:
>   # i_9 = PHI <i_6(4), 0(2)>
>   # ivtmp_1 = PHI <ivtmp_7(4), 6(2)>
>   _4 = (char) i_9;
>   data[i_9] = _4;
>   i_6 = i_9 + 1;
>   ivtmp_7 = ivtmp_1 - 1;
>   if (ivtmp_7 != 0)
>     goto <bb 4>;
>   else
>     goto <bb 5>;
>
>   <bb 4>:
>   goto <bb 3>;
>
>   <bb 5>:
>   return;

The cost metrics assume constant propagation happened which in the
above code didn't yet:

>   i_14 = 1;
>   _19 = (char) i_14;
...

So you are comparing (visually) apples and oranges.

>
> Example for ARM target machine code it became longer:
>
> 0000001c <test_iter_6>:
>   1c:   e59f3030        ldr     r3, [pc, #48]   ; 54 <test_iter_6+0x38>
>   20:   e3a02000        mov     r2, #0
>   24:   e5c32000        strb    r2, [r3]
>   28:   e3a02001        mov     r2, #1
>   2c:   e5c32001        strb    r2, [r3, #1]
>   30:   e3a02002        mov     r2, #2
>   34:   e5c32002        strb    r2, [r3, #2]
>   38:   e3a02003        mov     r2, #3
>   3c:   e5c32003        strb    r2, [r3, #3]
>   40:   e3a02004        mov     r2, #4
>   44:   e5c32004        strb    r2, [r3, #4]
>   48:   e3a02005        mov     r2, #5
>   4c:   e5c32005        strb    r2, [r3, #5]
>   50:   e12fff1e        bx      lr
>   54:   00000000        .word   0x00000000
>
> compared to if complete-loop-peeling was not done
>
> 0000001c <test_iter_6>:
>   1c:   e59f2014        ldr     r2, [pc, #20]   ; 38 <test_iter_6+0x1c>
>   20:   e3a03000        mov     r3, #0
>   24:   e7c33002        strb    r3, [r3, r2]
>   28:   e2833001        add     r3, r3, #1
>   2c:   e3530006        cmp     r3, #6
>   30:   1afffffb        bne     24 <test_iter_6+0x8>
>   34:   e12fff1e        bx      lr
>   38:   00000000        .word   0x00000000
>
> Producing 15 instead of 8 words, giving ~100% larger code size.
>
> And same for x86 arch:
>
>    f:   c6 05 00 00 00 00 00    movb   $0x0,0x0(%rip)        # 16
> <test_iter_6+0x7>
>   16:   c6 05 00 00 00 00 01    movb   $0x1,0x0(%rip)        # 1d
> <test_iter_6+0xe>
>   1d:   c6 05 00 00 00 00 02    movb   $0x2,0x0(%rip)        # 24
> <test_iter_6+0x15>
>   24:   c6 05 00 00 00 00 03    movb   $0x3,0x0(%rip)        # 2b
> <test_iter_6+0x1c>
>   2b:   c6 05 00 00 00 00 04    movb   $0x4,0x0(%rip)        # 32
> <test_iter_6+0x23>
>   32:   c6 05 00 00 00 00 05    movb   $0x5,0x0(%rip)        # 39
> <test_iter_6+0x2a>
>   39:   c3                      retq
>
>
> Without complete-loop-peeling done:
>
>    f:   31 c0                   xor    %eax,%eax
>   11:   88 80 00 00 00 00       mov    %al,0x0(%rax)
>   17:   48 ff c0                inc    %rax
>   1a:   48 83 f8 06             cmp    $0x6,%rax
>   1e:   75 f1                   jne    11 <test_iter_6+0x2>
>   20:   c3                      retq
>
>
> Producing 43 instead of 18 bytes, ~140% bigger code size.
>
> Should a variable be considered to be induction variable also when its used both as LHS array index and RHS data value in same loop?
> Since its cross-target for both ARM and x86, does it origin in some cost estimation on how 'ix' or other induction variables will be folded or not in the final target code?

Yes, the "heuristic" is off in some cases (it adds some optimistic
factor of followup optimization opportunities IIRC).  But not for
the reason you think.

Richard.

> Thanks, Kind Regards,
> Fredrik
>