Patchwork Patch to fix compiler ICE due to bad PRE

login
register
mail settings
Submitter Xinliang David Li
Date April 19, 2012, 6:51 p.m.
Message ID <CAAkRFZLFh7XG22DkpR4mQ9ABKvaOQL6u2uHM9Xqi3YfNyy5xsQ@mail.gmail.com>
Download mbox | patch
Permalink /patch/153851/
State New
Headers show

Comments

Xinliang David Li - April 19, 2012, 6:51 p.m.
Compiling the attached test case with -O2 using the trunk compiler,
the compiler will ICE. The proposed patch is also attached. The test
is under going, but I like to have discussion on the right fix first.

thanks,

David

Analysis:
-------------

Here is what is happening:

BB6 : (Successor: BB8)
  MEM_19 = phi(MEM_24, MEM_25)
  t_9 = operator new (100)@MEM_19 (--> MEM_26)
  mem_ref(pp_6, -16).x@MEM_26 = t_9 (-->MEM_27)   --> (1)

BB8:
  ...
  MEM_20 = PHI(MEM_27, MEM_24)
  ....
  d.2348_15 = mem_ref(pp_6, -16).x@MEM_20


In the loop header BB3 (which dominates BB6 and BB8),

   BB3:
    ..
    pp_31 = phi (pp_6, 0);
    ...
    pp_6 = pp_31 + 16



In PRE, ANTIC_IN(BB8) includes mem_ref(pp_31,0),x@MEM_20.  After phi
translate, ANTIC_OUT(BB6) gets mem_ref(pp_31,0).x@MEM_27.  However
this expression gets propagated into ANTIC_IN(BB6) even though the
memory expression is killed by (1). The root cause is that the alias
oracle reports that mem_ref(pp_6, -16) and mem_ref(pp_31, 0) are not
aliased as their points-to set do not intersect.

As as consequence of the bad aliasing, the operator new calls gets
transformed into an gimple assignment -- this gimple assignment
becomes the defining statement for MEM_26. In a  later UD chain walk,
the memory chain stops (and triggers the assert) at this new
assignment statement because there is no associated vuse for it.


Test case
--------------

The case is synthesized -- the real world examples involve lots of inlining etc.


int g, *gp[100];
struct V {
  int* x;
  int y;
};

void foo (V **p, V* end, int i)
{
  *p = 0;
  V* pp = *p;
  int s = 100;
  for (; pp < end; )
    {
      pp++;
      (pp-1)->x = &g;
      if (g)
        {
          if (g>10)
            g++;
          int *t = (int*) operator new (100);
         (pp-1)->x = t;
        }
      else
        s--;
     gp[end-pp] = (pp-1)->x + s;
  }
}


Patch
---------
Richard Guenther - April 20, 2012, 8:41 a.m.
On Thu, Apr 19, 2012 at 8:51 PM, Xinliang David Li <davidxl@google.com> wrote:
> Compiling the attached test case with -O2 using the trunk compiler,
> the compiler will ICE. The proposed patch is also attached. The test
> is under going, but I like to have discussion on the right fix first.

The patch doesn't look correct.  There needs to be a VUSE, if not then
sth else is wrong.

I'm looking into it.

Richard.

> thanks,
>
> David
>
> Analysis:
> -------------
>
> Here is what is happening:
>
> BB6 : (Successor: BB8)
>  MEM_19 = phi(MEM_24, MEM_25)
>  t_9 = operator new (100)@MEM_19 (--> MEM_26)
>  mem_ref(pp_6, -16).x@MEM_26 = t_9 (-->MEM_27)   --> (1)
>
> BB8:
>  ...
>  MEM_20 = PHI(MEM_27, MEM_24)
>  ....
>  d.2348_15 = mem_ref(pp_6, -16).x@MEM_20
>
>
> In the loop header BB3 (which dominates BB6 and BB8),
>
>   BB3:
>    ..
>    pp_31 = phi (pp_6, 0);
>    ...
>    pp_6 = pp_31 + 16
>
>
>
> In PRE, ANTIC_IN(BB8) includes mem_ref(pp_31,0),x@MEM_20.  After phi
> translate, ANTIC_OUT(BB6) gets mem_ref(pp_31,0).x@MEM_27.  However
> this expression gets propagated into ANTIC_IN(BB6) even though the
> memory expression is killed by (1). The root cause is that the alias
> oracle reports that mem_ref(pp_6, -16) and mem_ref(pp_31, 0) are not
> aliased as their points-to set do not intersect.
>
> As as consequence of the bad aliasing, the operator new calls gets
> transformed into an gimple assignment -- this gimple assignment
> becomes the defining statement for MEM_26. In a  later UD chain walk,
> the memory chain stops (and triggers the assert) at this new
> assignment statement because there is no associated vuse for it.
>
>
> Test case
> --------------
>
> The case is synthesized -- the real world examples involve lots of inlining etc.
>
>
> int g, *gp[100];
> struct V {
>  int* x;
>  int y;
> };
>
> void foo (V **p, V* end, int i)
> {
>  *p = 0;
>  V* pp = *p;
>  int s = 100;
>  for (; pp < end; )
>    {
>      pp++;
>      (pp-1)->x = &g;
>      if (g)
>        {
>          if (g>10)
>            g++;
>          int *t = (int*) operator new (100);
>         (pp-1)->x = t;
>        }
>      else
>        s--;
>     gp[end-pp] = (pp-1)->x + s;
>  }
> }
>
>
> Patch
> ---------
>
>
> Index: tree-ssa-structalias.c
> ===================================================================
> --- tree-ssa-structalias.c      (revision 186600)
> +++ tree-ssa-structalias.c      (working copy)
> @@ -6137,6 +6137,9 @@ pt_solutions_intersect_1 (struct pt_solu
>   if (pt1->anything || pt2->anything)
>     return true;
>
> +  if (pt1->null && pt2->null)
> +    return true;
> +
>   /* If either points to unknown global memory and the other points to
>      any global memory they alias.  */
>   if ((pt1->nonlocal
Richard Guenther - April 20, 2012, 10:07 a.m.
On Fri, Apr 20, 2012 at 10:41 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Thu, Apr 19, 2012 at 8:51 PM, Xinliang David Li <davidxl@google.com> wrote:
>> Compiling the attached test case with -O2 using the trunk compiler,
>> the compiler will ICE. The proposed patch is also attached. The test
>> is under going, but I like to have discussion on the right fix first.
>
> The patch doesn't look correct.  There needs to be a VUSE, if not then
> sth else is wrong.
>
> I'm looking into it.

It is propagate_tree_value_into_stmt not properly updating SSA form.  The
following patch fixes that - but it looks bogus that PRE sees

  t_12 = new 1000;

as equivalent to t_12 = &g.

Which is a separate issue.  I suppose you can make a runtime testcase
out of it and file a bug?

Thanks,
Richard.

> Richard.
>
>> thanks,
>>
>> David
>>
>> Analysis:
>> -------------
>>
>> Here is what is happening:
>>
>> BB6 : (Successor: BB8)
>>  MEM_19 = phi(MEM_24, MEM_25)
>>  t_9 = operator new (100)@MEM_19 (--> MEM_26)
>>  mem_ref(pp_6, -16).x@MEM_26 = t_9 (-->MEM_27)   --> (1)
>>
>> BB8:
>>  ...
>>  MEM_20 = PHI(MEM_27, MEM_24)
>>  ....
>>  d.2348_15 = mem_ref(pp_6, -16).x@MEM_20
>>
>>
>> In the loop header BB3 (which dominates BB6 and BB8),
>>
>>   BB3:
>>    ..
>>    pp_31 = phi (pp_6, 0);
>>    ...
>>    pp_6 = pp_31 + 16
>>
>>
>>
>> In PRE, ANTIC_IN(BB8) includes mem_ref(pp_31,0),x@MEM_20.  After phi
>> translate, ANTIC_OUT(BB6) gets mem_ref(pp_31,0).x@MEM_27.  However
>> this expression gets propagated into ANTIC_IN(BB6) even though the
>> memory expression is killed by (1). The root cause is that the alias
>> oracle reports that mem_ref(pp_6, -16) and mem_ref(pp_31, 0) are not
>> aliased as their points-to set do not intersect.
>>
>> As as consequence of the bad aliasing, the operator new calls gets
>> transformed into an gimple assignment -- this gimple assignment
>> becomes the defining statement for MEM_26. In a  later UD chain walk,
>> the memory chain stops (and triggers the assert) at this new
>> assignment statement because there is no associated vuse for it.
>>
>>
>> Test case
>> --------------
>>
>> The case is synthesized -- the real world examples involve lots of inlining etc.
>>
>>
>> int g, *gp[100];
>> struct V {
>>  int* x;
>>  int y;
>> };
>>
>> void foo (V **p, V* end, int i)
>> {
>>  *p = 0;
>>  V* pp = *p;
>>  int s = 100;
>>  for (; pp < end; )
>>    {
>>      pp++;
>>      (pp-1)->x = &g;
>>      if (g)
>>        {
>>          if (g>10)
>>            g++;
>>          int *t = (int*) operator new (100);
>>         (pp-1)->x = t;
>>        }
>>      else
>>        s--;
>>     gp[end-pp] = (pp-1)->x + s;
>>  }
>> }
>>
>>
>> Patch
>> ---------
>>
>>
>> Index: tree-ssa-structalias.c
>> ===================================================================
>> --- tree-ssa-structalias.c      (revision 186600)
>> +++ tree-ssa-structalias.c      (working copy)
>> @@ -6137,6 +6137,9 @@ pt_solutions_intersect_1 (struct pt_solu
>>   if (pt1->anything || pt2->anything)
>>     return true;
>>
>> +  if (pt1->null && pt2->null)
>> +    return true;
>> +
>>   /* If either points to unknown global memory and the other points to
>>      any global memory they alias.  */
>>   if ((pt1->nonlocal
Richard Guenther - April 20, 2012, 11:50 a.m.
On Fri, Apr 20, 2012 at 12:07 PM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Fri, Apr 20, 2012 at 10:41 AM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>> On Thu, Apr 19, 2012 at 8:51 PM, Xinliang David Li <davidxl@google.com> wrote:
>>> Compiling the attached test case with -O2 using the trunk compiler,
>>> the compiler will ICE. The proposed patch is also attached. The test
>>> is under going, but I like to have discussion on the right fix first.
>>
>> The patch doesn't look correct.  There needs to be a VUSE, if not then
>> sth else is wrong.
>>
>> I'm looking into it.
>
> It is propagate_tree_value_into_stmt not properly updating SSA form.  The
> following patch fixes that - but it looks bogus that PRE sees
>
>  t_12 = new 1000;
>
> as equivalent to t_12 = &g.
>
> Which is a separate issue.  I suppose you can make a runtime testcase
> out of it and file a bug?

Somewhat simplified testcase that still performs the bogus replacement:

int g, *gp;
int *bar();
void foo (int ***p, int** end, int b)
{
  *p = 0;
  int** pp = *p;
  for (;;)
    {
      pp++;
      *pp = &g;
      if (b)
        {
          if (b>1)
            g = 0;
          int *t = bar ();
          *pp = t;  <--- b
        }
      gp = *pp;   <--- a
    }
}

we note the bogus equivalency when trying to insert *pp from <--- a into
its predecessors.  The translated expr in the if (b) block is
{mem_ref<8B>,pp_1}@.MEM_16 with a leader 't' which looks ok.

But then we are trying to insert *pp from <--- b into its predecessors.
Not sure why - but I suppose we removed 't' because it is in TMP_GEN
but left *pp as EXP_GEN.  *pp ends up in ANTIC_IN because
clean does not consider *pp = t clobbering it - which is kind of correct - pp
points to NULL only, so storing into it cannot possibly alter what *pp points
to.  Well, all of this is undefined territory, so if not ICEing then this is no
longer a bug (not wrong-code - just an interesting side-effect of
undefinedness).

Richard.

> Thanks,
> Richard.
>
>> Richard.
>>
>>> thanks,
>>>
>>> David
>>>
>>> Analysis:
>>> -------------
>>>
>>> Here is what is happening:
>>>
>>> BB6 : (Successor: BB8)
>>>  MEM_19 = phi(MEM_24, MEM_25)
>>>  t_9 = operator new (100)@MEM_19 (--> MEM_26)
>>>  mem_ref(pp_6, -16).x@MEM_26 = t_9 (-->MEM_27)   --> (1)
>>>
>>> BB8:
>>>  ...
>>>  MEM_20 = PHI(MEM_27, MEM_24)
>>>  ....
>>>  d.2348_15 = mem_ref(pp_6, -16).x@MEM_20
>>>
>>>
>>> In the loop header BB3 (which dominates BB6 and BB8),
>>>
>>>   BB3:
>>>    ..
>>>    pp_31 = phi (pp_6, 0);
>>>    ...
>>>    pp_6 = pp_31 + 16
>>>
>>>
>>>
>>> In PRE, ANTIC_IN(BB8) includes mem_ref(pp_31,0),x@MEM_20.  After phi
>>> translate, ANTIC_OUT(BB6) gets mem_ref(pp_31,0).x@MEM_27.  However
>>> this expression gets propagated into ANTIC_IN(BB6) even though the
>>> memory expression is killed by (1). The root cause is that the alias
>>> oracle reports that mem_ref(pp_6, -16) and mem_ref(pp_31, 0) are not
>>> aliased as their points-to set do not intersect.
>>>
>>> As as consequence of the bad aliasing, the operator new calls gets
>>> transformed into an gimple assignment -- this gimple assignment
>>> becomes the defining statement for MEM_26. In a  later UD chain walk,
>>> the memory chain stops (and triggers the assert) at this new
>>> assignment statement because there is no associated vuse for it.
>>>
>>>
>>> Test case
>>> --------------
>>>
>>> The case is synthesized -- the real world examples involve lots of inlining etc.
>>>
>>>
>>> int g, *gp[100];
>>> struct V {
>>>  int* x;
>>>  int y;
>>> };
>>>
>>> void foo (V **p, V* end, int i)
>>> {
>>>  *p = 0;
>>>  V* pp = *p;
>>>  int s = 100;
>>>  for (; pp < end; )
>>>    {
>>>      pp++;
>>>      (pp-1)->x = &g;
>>>      if (g)
>>>        {
>>>          if (g>10)
>>>            g++;
>>>          int *t = (int*) operator new (100);
>>>         (pp-1)->x = t;
>>>        }
>>>      else
>>>        s--;
>>>     gp[end-pp] = (pp-1)->x + s;
>>>  }
>>> }
>>>
>>>
>>> Patch
>>> ---------
>>>
>>>
>>> Index: tree-ssa-structalias.c
>>> ===================================================================
>>> --- tree-ssa-structalias.c      (revision 186600)
>>> +++ tree-ssa-structalias.c      (working copy)
>>> @@ -6137,6 +6137,9 @@ pt_solutions_intersect_1 (struct pt_solu
>>>   if (pt1->anything || pt2->anything)
>>>     return true;
>>>
>>> +  if (pt1->null && pt2->null)
>>> +    return true;
>>> +
>>>   /* If either points to unknown global memory and the other points to
>>>      any global memory they alias.  */
>>>   if ((pt1->nonlocal
Xinliang David Li - April 20, 2012, 4:16 p.m.
On Fri, Apr 20, 2012 at 4:50 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Fri, Apr 20, 2012 at 12:07 PM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>> On Fri, Apr 20, 2012 at 10:41 AM, Richard Guenther
>> <richard.guenther@gmail.com> wrote:
>>> On Thu, Apr 19, 2012 at 8:51 PM, Xinliang David Li <davidxl@google.com> wrote:
>>>> Compiling the attached test case with -O2 using the trunk compiler,
>>>> the compiler will ICE. The proposed patch is also attached. The test
>>>> is under going, but I like to have discussion on the right fix first.
>>>
>>> The patch doesn't look correct.  There needs to be a VUSE, if not then
>>> sth else is wrong.
>>>
>>> I'm looking into it.
>>
>> It is propagate_tree_value_into_stmt not properly updating SSA form.  The
>> following patch fixes that - but it looks bogus that PRE sees
>>
>>  t_12 = new 1000;
>>
>> as equivalent to t_12 = &g.
>>
>> Which is a separate issue.  I suppose you can make a runtime testcase
>> out of it and file a bug?
>
> Somewhat simplified testcase that still performs the bogus replacement:
>
> int g, *gp;
> int *bar();
> void foo (int ***p, int** end, int b)
> {
>  *p = 0;
>  int** pp = *p;
>  for (;;)
>    {
>      pp++;
>      *pp = &g;
>      if (b)
>        {
>          if (b>1)
>            g = 0;
>          int *t = bar ();
>          *pp = t;  <--- b
>        }
>      gp = *pp;   <--- a
>    }
> }
>
> we note the bogus equivalency when trying to insert *pp from <--- a into
> its predecessors.  The translated expr in the if (b) block is
> {mem_ref<8B>,pp_1}@.MEM_16 with a leader 't' which looks ok.
>
> But then we are trying to insert *pp from <--- b into its predecessors.
> Not sure why - but I suppose we removed 't' because it is in TMP_GEN
> but left *pp as EXP_GEN.  *pp ends up in ANTIC_IN because
> clean does not consider *pp = t clobbering it -

Yes, this is what is happening -- I should have made it clearer. The
*pp from <--a end up in ANTIC_IN of BB(<--b) after translation which
is incorrect. The clean(..) method is supposed to remove the invalid
expressions, but the value_dies_in_block_x returns false because the
no-alias returned.


>which is kind of correct - pp
> points to NULL only, so storing into it cannot possibly alter what *pp points
> to.  Well, all of this is undefined territory, so if not ICEing then this is no
> longer a bug (not wrong-code - just an interesting side-effect of
> undefinedness).

Yes -- that is why whatever fix should be ok  as the code won't be
executed at runtime.   For the pointer to null case, for some targets,
the null dress can be legal then the aliaser's behavior will be wrong.

thanks,

David


>
> Richard.
>
>> Thanks,
>> Richard.
>>
>>> Richard.
>>>
>>>> thanks,
>>>>
>>>> David
>>>>
>>>> Analysis:
>>>> -------------
>>>>
>>>> Here is what is happening:
>>>>
>>>> BB6 : (Successor: BB8)
>>>>  MEM_19 = phi(MEM_24, MEM_25)
>>>>  t_9 = operator new (100)@MEM_19 (--> MEM_26)
>>>>  mem_ref(pp_6, -16).x@MEM_26 = t_9 (-->MEM_27)   --> (1)
>>>>
>>>> BB8:
>>>>  ...
>>>>  MEM_20 = PHI(MEM_27, MEM_24)
>>>>  ....
>>>>  d.2348_15 = mem_ref(pp_6, -16).x@MEM_20
>>>>
>>>>
>>>> In the loop header BB3 (which dominates BB6 and BB8),
>>>>
>>>>   BB3:
>>>>    ..
>>>>    pp_31 = phi (pp_6, 0);
>>>>    ...
>>>>    pp_6 = pp_31 + 16
>>>>
>>>>
>>>>
>>>> In PRE, ANTIC_IN(BB8) includes mem_ref(pp_31,0),x@MEM_20.  After phi
>>>> translate, ANTIC_OUT(BB6) gets mem_ref(pp_31,0).x@MEM_27.  However
>>>> this expression gets propagated into ANTIC_IN(BB6) even though the
>>>> memory expression is killed by (1). The root cause is that the alias
>>>> oracle reports that mem_ref(pp_6, -16) and mem_ref(pp_31, 0) are not
>>>> aliased as their points-to set do not intersect.
>>>>
>>>> As as consequence of the bad aliasing, the operator new calls gets
>>>> transformed into an gimple assignment -- this gimple assignment
>>>> becomes the defining statement for MEM_26. In a  later UD chain walk,
>>>> the memory chain stops (and triggers the assert) at this new
>>>> assignment statement because there is no associated vuse for it.
>>>>
>>>>
>>>> Test case
>>>> --------------
>>>>
>>>> The case is synthesized -- the real world examples involve lots of inlining etc.
>>>>
>>>>
>>>> int g, *gp[100];
>>>> struct V {
>>>>  int* x;
>>>>  int y;
>>>> };
>>>>
>>>> void foo (V **p, V* end, int i)
>>>> {
>>>>  *p = 0;
>>>>  V* pp = *p;
>>>>  int s = 100;
>>>>  for (; pp < end; )
>>>>    {
>>>>      pp++;
>>>>      (pp-1)->x = &g;
>>>>      if (g)
>>>>        {
>>>>          if (g>10)
>>>>            g++;
>>>>          int *t = (int*) operator new (100);
>>>>         (pp-1)->x = t;
>>>>        }
>>>>      else
>>>>        s--;
>>>>     gp[end-pp] = (pp-1)->x + s;
>>>>  }
>>>> }
>>>>
>>>>
>>>> Patch
>>>> ---------
>>>>
>>>>
>>>> Index: tree-ssa-structalias.c
>>>> ===================================================================
>>>> --- tree-ssa-structalias.c      (revision 186600)
>>>> +++ tree-ssa-structalias.c      (working copy)
>>>> @@ -6137,6 +6137,9 @@ pt_solutions_intersect_1 (struct pt_solu
>>>>   if (pt1->anything || pt2->anything)
>>>>     return true;
>>>>
>>>> +  if (pt1->null && pt2->null)
>>>> +    return true;
>>>> +
>>>>   /* If either points to unknown global memory and the other points to
>>>>      any global memory they alias.  */
>>>>   if ((pt1->nonlocal
Xinliang David Li - April 20, 2012, 4:20 p.m.
On Fri, Apr 20, 2012 at 3:07 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Fri, Apr 20, 2012 at 10:41 AM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>> On Thu, Apr 19, 2012 at 8:51 PM, Xinliang David Li <davidxl@google.com> wrote:
>>> Compiling the attached test case with -O2 using the trunk compiler,
>>> the compiler will ICE. The proposed patch is also attached. The test
>>> is under going, but I like to have discussion on the right fix first.
>>
>> The patch doesn't look correct.  There needs to be a VUSE, if not then
>> sth else is wrong.
>>
>> I'm looking into it.
>
> It is propagate_tree_value_into_stmt not properly updating SSA form.  The
> following patch fixes that - but it looks bogus that PRE sees

great! thanks for the fix.

>
>  t_12 = new 1000;
>
> as equivalent to t_12 = &g.
>
> Which is a separate issue.  I suppose you can make a runtime testcase
> out of it and file a bug?
>

As you have noticed, this bogus transformation won't be executed at
runtime (either dead code or will trigger segfault).

thanks,

David

> Thanks,
> Richard.
>
>> Richard.
>>
>>> thanks,
>>>
>>> David
>>>
>>> Analysis:
>>> -------------
>>>
>>> Here is what is happening:
>>>
>>> BB6 : (Successor: BB8)
>>>  MEM_19 = phi(MEM_24, MEM_25)
>>>  t_9 = operator new (100)@MEM_19 (--> MEM_26)
>>>  mem_ref(pp_6, -16).x@MEM_26 = t_9 (-->MEM_27)   --> (1)
>>>
>>> BB8:
>>>  ...
>>>  MEM_20 = PHI(MEM_27, MEM_24)
>>>  ....
>>>  d.2348_15 = mem_ref(pp_6, -16).x@MEM_20
>>>
>>>
>>> In the loop header BB3 (which dominates BB6 and BB8),
>>>
>>>   BB3:
>>>    ..
>>>    pp_31 = phi (pp_6, 0);
>>>    ...
>>>    pp_6 = pp_31 + 16
>>>
>>>
>>>
>>> In PRE, ANTIC_IN(BB8) includes mem_ref(pp_31,0),x@MEM_20.  After phi
>>> translate, ANTIC_OUT(BB6) gets mem_ref(pp_31,0).x@MEM_27.  However
>>> this expression gets propagated into ANTIC_IN(BB6) even though the
>>> memory expression is killed by (1). The root cause is that the alias
>>> oracle reports that mem_ref(pp_6, -16) and mem_ref(pp_31, 0) are not
>>> aliased as their points-to set do not intersect.
>>>
>>> As as consequence of the bad aliasing, the operator new calls gets
>>> transformed into an gimple assignment -- this gimple assignment
>>> becomes the defining statement for MEM_26. In a  later UD chain walk,
>>> the memory chain stops (and triggers the assert) at this new
>>> assignment statement because there is no associated vuse for it.
>>>
>>>
>>> Test case
>>> --------------
>>>
>>> The case is synthesized -- the real world examples involve lots of inlining etc.
>>>
>>>
>>> int g, *gp[100];
>>> struct V {
>>>  int* x;
>>>  int y;
>>> };
>>>
>>> void foo (V **p, V* end, int i)
>>> {
>>>  *p = 0;
>>>  V* pp = *p;
>>>  int s = 100;
>>>  for (; pp < end; )
>>>    {
>>>      pp++;
>>>      (pp-1)->x = &g;
>>>      if (g)
>>>        {
>>>          if (g>10)
>>>            g++;
>>>          int *t = (int*) operator new (100);
>>>         (pp-1)->x = t;
>>>        }
>>>      else
>>>        s--;
>>>     gp[end-pp] = (pp-1)->x + s;
>>>  }
>>> }
>>>
>>>
>>> Patch
>>> ---------
>>>
>>>
>>> Index: tree-ssa-structalias.c
>>> ===================================================================
>>> --- tree-ssa-structalias.c      (revision 186600)
>>> +++ tree-ssa-structalias.c      (working copy)
>>> @@ -6137,6 +6137,9 @@ pt_solutions_intersect_1 (struct pt_solu
>>>   if (pt1->anything || pt2->anything)
>>>     return true;
>>>
>>> +  if (pt1->null && pt2->null)
>>> +    return true;
>>> +
>>>   /* If either points to unknown global memory and the other points to
>>>      any global memory they alias.  */
>>>   if ((pt1->nonlocal
Richard Guenther - April 23, 2012, 9:30 a.m.
On Fri, Apr 20, 2012 at 6:16 PM, Xinliang David Li <davidxl@google.com> wrote:
> On Fri, Apr 20, 2012 at 4:50 AM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>> On Fri, Apr 20, 2012 at 12:07 PM, Richard Guenther
>> <richard.guenther@gmail.com> wrote:
>>> On Fri, Apr 20, 2012 at 10:41 AM, Richard Guenther
>>> <richard.guenther@gmail.com> wrote:
>>>> On Thu, Apr 19, 2012 at 8:51 PM, Xinliang David Li <davidxl@google.com> wrote:
>>>>> Compiling the attached test case with -O2 using the trunk compiler,
>>>>> the compiler will ICE. The proposed patch is also attached. The test
>>>>> is under going, but I like to have discussion on the right fix first.
>>>>
>>>> The patch doesn't look correct.  There needs to be a VUSE, if not then
>>>> sth else is wrong.
>>>>
>>>> I'm looking into it.
>>>
>>> It is propagate_tree_value_into_stmt not properly updating SSA form.  The
>>> following patch fixes that - but it looks bogus that PRE sees
>>>
>>>  t_12 = new 1000;
>>>
>>> as equivalent to t_12 = &g.
>>>
>>> Which is a separate issue.  I suppose you can make a runtime testcase
>>> out of it and file a bug?
>>
>> Somewhat simplified testcase that still performs the bogus replacement:
>>
>> int g, *gp;
>> int *bar();
>> void foo (int ***p, int** end, int b)
>> {
>>  *p = 0;
>>  int** pp = *p;
>>  for (;;)
>>    {
>>      pp++;
>>      *pp = &g;
>>      if (b)
>>        {
>>          if (b>1)
>>            g = 0;
>>          int *t = bar ();
>>          *pp = t;  <--- b
>>        }
>>      gp = *pp;   <--- a
>>    }
>> }
>>
>> we note the bogus equivalency when trying to insert *pp from <--- a into
>> its predecessors.  The translated expr in the if (b) block is
>> {mem_ref<8B>,pp_1}@.MEM_16 with a leader 't' which looks ok.
>>
>> But then we are trying to insert *pp from <--- b into its predecessors.
>> Not sure why - but I suppose we removed 't' because it is in TMP_GEN
>> but left *pp as EXP_GEN.  *pp ends up in ANTIC_IN because
>> clean does not consider *pp = t clobbering it -
>
> Yes, this is what is happening -- I should have made it clearer. The
> *pp from <--a end up in ANTIC_IN of BB(<--b) after translation which
> is incorrect. The clean(..) method is supposed to remove the invalid
> expressions, but the value_dies_in_block_x returns false because the
> no-alias returned.
>
>
>>which is kind of correct - pp
>> points to NULL only, so storing into it cannot possibly alter what *pp points
>> to.  Well, all of this is undefined territory, so if not ICEing then this is no
>> longer a bug (not wrong-code - just an interesting side-effect of
>> undefinedness).
>
> Yes -- that is why whatever fix should be ok  as the code won't be
> executed at runtime.   For the pointer to null case, for some targets,
> the null dress can be legal then the aliaser's behavior will be wrong.

Yes.  Those need to enable -fno-delete-null-pointer-checks and the aliaser
will no longer derive pt_null then.

Richard.

> thanks,
>
> David
>
>
>>
>> Richard.
>>
>>> Thanks,
>>> Richard.
>>>
>>>> Richard.
>>>>
>>>>> thanks,
>>>>>
>>>>> David
>>>>>
>>>>> Analysis:
>>>>> -------------
>>>>>
>>>>> Here is what is happening:
>>>>>
>>>>> BB6 : (Successor: BB8)
>>>>>  MEM_19 = phi(MEM_24, MEM_25)
>>>>>  t_9 = operator new (100)@MEM_19 (--> MEM_26)
>>>>>  mem_ref(pp_6, -16).x@MEM_26 = t_9 (-->MEM_27)   --> (1)
>>>>>
>>>>> BB8:
>>>>>  ...
>>>>>  MEM_20 = PHI(MEM_27, MEM_24)
>>>>>  ....
>>>>>  d.2348_15 = mem_ref(pp_6, -16).x@MEM_20
>>>>>
>>>>>
>>>>> In the loop header BB3 (which dominates BB6 and BB8),
>>>>>
>>>>>   BB3:
>>>>>    ..
>>>>>    pp_31 = phi (pp_6, 0);
>>>>>    ...
>>>>>    pp_6 = pp_31 + 16
>>>>>
>>>>>
>>>>>
>>>>> In PRE, ANTIC_IN(BB8) includes mem_ref(pp_31,0),x@MEM_20.  After phi
>>>>> translate, ANTIC_OUT(BB6) gets mem_ref(pp_31,0).x@MEM_27.  However
>>>>> this expression gets propagated into ANTIC_IN(BB6) even though the
>>>>> memory expression is killed by (1). The root cause is that the alias
>>>>> oracle reports that mem_ref(pp_6, -16) and mem_ref(pp_31, 0) are not
>>>>> aliased as their points-to set do not intersect.
>>>>>
>>>>> As as consequence of the bad aliasing, the operator new calls gets
>>>>> transformed into an gimple assignment -- this gimple assignment
>>>>> becomes the defining statement for MEM_26. In a  later UD chain walk,
>>>>> the memory chain stops (and triggers the assert) at this new
>>>>> assignment statement because there is no associated vuse for it.
>>>>>
>>>>>
>>>>> Test case
>>>>> --------------
>>>>>
>>>>> The case is synthesized -- the real world examples involve lots of inlining etc.
>>>>>
>>>>>
>>>>> int g, *gp[100];
>>>>> struct V {
>>>>>  int* x;
>>>>>  int y;
>>>>> };
>>>>>
>>>>> void foo (V **p, V* end, int i)
>>>>> {
>>>>>  *p = 0;
>>>>>  V* pp = *p;
>>>>>  int s = 100;
>>>>>  for (; pp < end; )
>>>>>    {
>>>>>      pp++;
>>>>>      (pp-1)->x = &g;
>>>>>      if (g)
>>>>>        {
>>>>>          if (g>10)
>>>>>            g++;
>>>>>          int *t = (int*) operator new (100);
>>>>>         (pp-1)->x = t;
>>>>>        }
>>>>>      else
>>>>>        s--;
>>>>>     gp[end-pp] = (pp-1)->x + s;
>>>>>  }
>>>>> }
>>>>>
>>>>>
>>>>> Patch
>>>>> ---------
>>>>>
>>>>>
>>>>> Index: tree-ssa-structalias.c
>>>>> ===================================================================
>>>>> --- tree-ssa-structalias.c      (revision 186600)
>>>>> +++ tree-ssa-structalias.c      (working copy)
>>>>> @@ -6137,6 +6137,9 @@ pt_solutions_intersect_1 (struct pt_solu
>>>>>   if (pt1->anything || pt2->anything)
>>>>>     return true;
>>>>>
>>>>> +  if (pt1->null && pt2->null)
>>>>> +    return true;
>>>>> +
>>>>>   /* If either points to unknown global memory and the other points to
>>>>>      any global memory they alias.  */
>>>>>   if ((pt1->nonlocal

Patch

Index: tree-ssa-structalias.c
===================================================================
--- tree-ssa-structalias.c      (revision 186600)
+++ tree-ssa-structalias.c      (working copy)
@@ -6137,6 +6137,9 @@  pt_solutions_intersect_1 (struct pt_solu
   if (pt1->anything || pt2->anything)
     return true;

+  if (pt1->null && pt2->null)
+    return true;
+
   /* If either points to unknown global memory and the other points to
      any global memory they alias.  */
   if ((pt1->nonlocal