Re: Why can't copy renaming capture this assignment?

Re: Why can't copy renaming capture this assignment?

[Richard Guenther]

On Sat, Mar 31, 2012 at 6:23 AM, Jiangning Liu <jiangning.liu@arm.com> wrote:
> Hi,
>
> For this small case,
>
> char garr[100];
> void f(void)
> {
>        unsigned short h, s;
>
>        s = 20;
>
>        for (h = 1; h < (s-1); h++)
>        {
>                garr[h] = 0;
>        }
> }
>
> After copyrename3, we have the following dump,
>
> f ()
> {
>  short unsigned int h;
>  int D.4066;
>
> <bb 2>:
>  D.4066_14 = 1;
>  if (D.4066_14 <= 18)
>    goto <bb 3>;
>  else
>    goto <bb 4>;
>
> <bb 3>:
>  # h_15 = PHI <h_8(3), 1(2)>
>  # D.4066_16 = PHI <D.4066_4(3), D.4066_14(2)>
>  garr[D.4066_16] = 0;
>  h_8 = h_15 + 1;
>  D.4066_4 = (int) h_8;
>  if (D.4066_4 <= 18)
>    goto <bb 3>;
>  else
>    goto <bb 4>;
>
> <bb 4>:
>  return;
>
> }
>
> copy renaming fails to capture the assignment statement "D.4066_4 = (int)
> h_8;" to trigger renaming partition coalesce.
>
> I find gimple_assign_single_p invoked by gimple_assign_ssa_name_copy_p
> always returns false, because for this statement " gs->gsbase.subcode" is
> NOP_EXPR rather than GIMPLE_SINGLE_RHS.
>
> Should subcode be correctly initialized anywhere to fix this problem?
>
> BTW, my expectation after copy renaming is like below,
>
> f ()
> {
>  int D.4679;
>
> <bb 2>:
>  D.4679_7 = 1;
>  if (D.4679_7 != 19)
>    goto <bb 3>;
>  else
>    goto <bb 4>;
>
> <bb 3>:
>  # D.4679_15 = PHI <D.4679_4(3), D.4679_7(2)>
>  # D.4679_17 = PHI <D.4679_14(3), 1(2)>
>  garr[D.4679_15] = 0;
>  D.4679_14 = D.4679_17 + 1;
>  D.4679_4 = D.4679_14;
>  if (D.4679_4 != 19)
>    goto <bb 3>;
>  else
>    goto <bb 4>;
>
> <bb 4>:
>  return;
>
> }

Err - you completely lost the fact that h was short instead of int.

Richard.

> and then PRE can finally remove that redundancy for symbol D.xxxx away.
>
> Thanks,
> -Jiangning
>
>
>
>
>

Re: Why can't copy renaming capture this assignment?

[Richard Guenther]

2012/4/3 Jiangning Liu <liujiangning1@gmail.com>:
>
> 在 2012-4-2 下午4:37，"Richard Guenther" <richard.guenther@gmail.com>写道：
>
>
>>
>> On Sat, Mar 31, 2012 at 6:23 AM, Jiangning Liu <jiangning.liu@arm.com>
>> wrote:
>> > Hi,
>> >
>> > For this small case,
>> >
>> > char garr[100];
>> > void f(void)
>> > {
>> >        unsigned short h, s;
>> >
>> >        s = 20;
>> >
>> >        for (h = 1; h < (s-1); h++)
>> >        {
>> >                garr[h] = 0;
>> >        }
>> > }
>> >
>> > After copyrename3, we have the following dump,
>> >
>> > f ()
>> > {
>> >  short unsigned int h;
>> >  int D.4066;
>> >
>> > <bb 2>:
>> >  D.4066_14 = 1;
>> >  if (D.4066_14 <= 18)
>> >    goto <bb 3>;
>> >  else
>> >    goto <bb 4>;
>> >
>> > <bb 3>:
>> >  # h_15 = PHI <h_8(3), 1(2)>
>> >  # D.4066_16 = PHI <D.4066_4(3), D.4066_14(2)>
>> >  garr[D.4066_16] = 0;
>> >  h_8 = h_15 + 1;
>> >  D.4066_4 = (int) h_8;
>> >  if (D.4066_4 <= 18)
>> >    goto <bb 3>;
>> >  else
>> >    goto <bb 4>;
>> >
>> > <bb 4>:
>> >  return;
>> >
>> > }
>> >
>> > copy renaming fails to capture the assignment statement "D.4066_4 =
>> > (int)
>> > h_8;" to trigger renaming partition coalesce.
>> >
>> > I find gimple_assign_single_p invoked by gimple_assign_ssa_name_copy_p
>> > always returns false, because for this statement " gs->gsbase.subcode"
>> > is
>> > NOP_EXPR rather than GIMPLE_SINGLE_RHS.
>> >
>> > Should subcode be correctly initialized anywhere to fix this problem?
>> >
>> > BTW, my expectation after copy renaming is like below,
>> >
>> > f ()
>> > {
>> >  int D.4679;
>> >
>> > <bb 2>:
>> >  D.4679_7 = 1;
>> >  if (D.4679_7 != 19)
>> >    goto <bb 3>;
>> >  else
>> >    goto <bb 4>;
>> >
>> > <bb 3>:
>> >  # D.4679_15 = PHI <D.4679_4(3), D.4679_7(2)>
>> >  # D.4679_17 = PHI <D.4679_14(3), 1(2)>
>> >  garr[D.4679_15] = 0;
>> >  D.4679_14 = D.4679_17 + 1;
>> >  D.4679_4 = D.4679_14;
>> >  if (D.4679_4 != 19)
>> >    goto <bb 3>;
>> >  else
>> >    goto <bb 4>;
>> >
>> > <bb 4>:
>> >  return;
>> >
>> > }
>>
>> Err - you completely lost the fact that h was short instead of int.
>>
>> Richard.
>>
>> > and then PRE can finally remove that redundancy for symbol D.xxxx away.
>
> Hi Richard,
>
> Well, actually I noticed that, but which optimization would be able to
> handle this case and finally get that redundancy removed, if copy renaming
> can't detect this? It's quite obviouse that h and D.xxxx contain the same
> data, right? Or are you implying we should neither generate an integer type
> of temp variable D.xxxx nor generate this temp variable in previouse pass at
> all?

They don't contain the same 'data' (their data has different size).  They
contain the same value.  If you want to get rid of either you have to get
rid of, or rewrite, all uses of either.  In this case

<bb 2>:
 D.4066_14 = 1;
 if (D.4066_14 <= 18)
   goto <bb 3>;
 else
   goto <bb 4>;

<bb 3>:
 # h_15 = PHI <h_8(3), 1(2)>
 # D.4066_16 = PHI <D.4066_4(3), D.4066_14(2)>
 garr[D.4066_16] = 0;
 h_8 = h_15 + 1;
 D.4066_4 = (int) h_8;
 if (D.4066_4 <= 18)
   goto <bb 3>;
 else
   goto <bb 4>;

<bb 4>:
 return;

you'd want to use h_8 in the comparison.  forwprop would do this if
there were a single use only of D.4066_4 (well, I suppose it would, it
at least seems not to do this if there is the PHI node around).  The
PHI node is harder - the type used in the array indexing does not
really matter, so using h_8 would be ok there, but you would need to
rewrite the PHI node.  You can _not_ rewrite the h_8 definition to
use D.4066 and type 'int' because overflow on that would be undefined
while h may wrap just fine (well, at least not without value-range analysis).

So.  I suppose the right pass to handle the above is a combination
of value-numbering and value-range analysis - you have to prove
equality of h and D.4066 which is not mapping to either exactly
because of the differing types.  I suppose VN could be relaxed
in its type compatibility requirements (but that would be a pretty
disrupting change) and value-number D.4066_4 equal to h_8.  Eliminating
the redundancy then would have to cope with the type incompatibility
and decide that h_8 is the one to keep (because we can't rewrite the
addition).

So I suppose for this specific case a pass that performs type promotion/demotion
(as was discussed repeatedly) would be a better thing, and an enablement
of trivial redundancy removal.

Richard.

>
> Thanks,
> ~Jiangning
>
>> >
>> > Thanks,
>> > -Jiangning
>> >
>> >
>> >
>> >
>> >

Re: Why can't copy renaming capture this assignment?

[Richard Guenther]

On Wed, Apr 4, 2012 at 1:27 AM, Jiangning Liu <liujiangning1@gmail.com> wrote:
>
>> So I suppose for this specific case a pass that performs type
>> promotion/demotion
>> (as was discussed repeatedly) would be a better thing, and an enablement
>> of trivial redundancy removal.
>>
> This case is from a real  benchmark and this problem introduces huge

A "real benchmark"?  That gave me a laugh ;)

> performance loss, because it is in the nested kernel loop. Do you know who
> is working on this type promotion/demotion pass? I think it should be
> handled in a very early stage if we need that.

Not sure if anybody is working on it, but talks were between me, Jakub,
Kai and Andrew (public on this list).

Richard.

> Thanks,
> -Jiangning
>
>> Richard.

Why can't copy renaming capture this assignment?

[Jiangning Liu]

Hi,

For this small case, 

char garr[100];
void f(void)
{
        unsigned short h, s;

        s = 20;

        for (h = 1; h < (s-1); h++)
        {
                garr[h] = 0;
        }
}

After copyrename3, we have the following dump,

f ()
{
  short unsigned int h;
  int D.4066;

<bb 2>:
  D.4066_14 = 1;
  if (D.4066_14 <= 18)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  # h_15 = PHI <h_8(3), 1(2)>
  # D.4066_16 = PHI <D.4066_4(3), D.4066_14(2)>
  garr[D.4066_16] = 0;
  h_8 = h_15 + 1;
  D.4066_4 = (int) h_8;
  if (D.4066_4 <= 18)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 4>:
  return;

}

copy renaming fails to capture the assignment statement "D.4066_4 = (int)
h_8;" to trigger renaming partition coalesce. 

I find gimple_assign_single_p invoked by gimple_assign_ssa_name_copy_p
always returns false, because for this statement " gs->gsbase.subcode" is
NOP_EXPR rather than GIMPLE_SINGLE_RHS.

Should subcode be correctly initialized anywhere to fix this problem?

BTW, my expectation after copy renaming is like below, 

f ()
{
  int D.4679;

<bb 2>:
  D.4679_7 = 1;
  if (D.4679_7 != 19)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  # D.4679_15 = PHI <D.4679_4(3), D.4679_7(2)>
  # D.4679_17 = PHI <D.4679_14(3), 1(2)>
  garr[D.4679_15] = 0;
  D.4679_14 = D.4679_17 + 1;
  D.4679_4 = D.4679_14;
  if (D.4679_4 != 19)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 4>:
  return;

}

and then PRE can finally remove that redundancy for symbol D.xxxx away.

Thanks,
-Jiangning