A case exposing code sink issue

[Richard Guenther]

On Thu, Dec 22, 2011 at 9:25 AM, Jiangning Liu <jiangning.liu@arm.com> wrote:
>> Yes, the number of iterations of the i loop simply is too difficult fo
>> our loop iteration calculator to comprehend:
>>
>>   for (i=k; i<500; i+=k)
>>
>> iterates for roundup((500-k)/k) time.  In particular if the step is
>> non-constant our nr-of-iteration calculator gives up.
>>
>
> I'm trying to give an even smaller case,
>
> int a[512] ;
> int *a_p ;
>
> int f(int k)
> {
>        int i ;
>
>        for(i=0; i<k; i++)
>        {
>                a_p = &a[i] ;
>                *a_p = 7 ;
>        }
> }
>
> For this case, we have a very simple loop step "i++", then we would have the
> GIMPLE before expand like below,
>
> <bb 5>:
>  # i_13 = PHI <i_6(5), 0(4)>
>  # ivtmp.10_9 = PHI <ivtmp.10_1(5), ivtmp.10_15(4)>
>  a_p_lsm.6_4 = &a[i_13];
>  ivtmp.10_1 = ivtmp.10_9 + 4;
>  D.4085_16 = (void *) ivtmp.10_1;
>  MEM[base: D.4085_16, offset: 0B] = 7;
>  i_6 = i_13 + 1;
>  if (i_6 != k_3(D))
>    goto <bb 5>;
>  else
>    goto <bb 6>;
>
> <bb 6>:
>  # a_p_lsm.6_11 = PHI <a_p_lsm.6_4(5)>
>  a_p = a_p_lsm.6_11;
>  goto <bb 3>;
>
> Why can't we still sunk &a[i_13] out of loop? For example, I expect to
> generate the code like below,
>
> <bb 5>:
>  # i_13 = PHI <i_6(5), 0(4)>
>  # ivtmp.10_9 = PHI <ivtmp.10_1(5), ivtmp.10_15(4)>
>  i_14 = i_13;
>  ivtmp.10_1 = ivtmp.10_9 + 4;
>  D.4085_16 = (void *) ivtmp.10_1;
>  MEM[base: D.4085_16, offset: 0B] = 7;
>  i_6 = i_13 + 1;
>  if (i_6 != k_3(D))
>    goto <bb 5>;
>  else
>    goto <bb 6>;
>
> <bb 6>:
>  # a_p_lsm.6_11 = PHI <a_p_lsm.6_4(5)>
>  a_p_lsm.6_4 = &a[i_14];
>  a_p = a_p_lsm.6_11;
>  goto <bb 3>;
>
> This way the computation of &a[i] would be saved within the loop.
>
> Any idea?

The job to do this is final value replacement, not sinking (we do not
sink non-invariant expressions - you'd have to translate them through
the loop-closed SSA exit PHI node, certainly doable, patches welcome ;)).

Richard.

> Thanks,
> -Jiangning
>
>
>