Latent PTA bug?

Latent PTA bug?

[Richard Guenther]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1677 bytes --]

Hi all!

I reduced my array aliasing libstdc++ failures to the following
testcase:

struct iterator
{
    int* ptr;
    iterator(int* _ptr) : ptr(_ptr) {}
};

struct container {
    int* first;
    container(int* _first) : first(_first) {}
    iterator begin() { return iterator(first); }
};

bool includes(const iterator&);

bool test4()
{
    int array[] = {2, 4};
    container con(array);
    return includes(con.begin());
}

the weird thing now is, that the alias1 dump contains

  #   SFT.2_19 = V_MAY_DEF <SFT.2_2>;
  #   SFT.4_20 = V_MAY_DEF <SFT.4_15>;
  D.1797_16 = includes (&D.1794);

i.e. it misses the V_MAY_DEF for SFT.1  (array, UID 1783, int[2], is 
addressable, sub-vars: { SFT.2 SFT.1 }), while the alias2 dump
is ok:

  #   SFT.1_9 = V_MAY_DEF <SFT.1_3>;
  #   SFT.2_19 = V_MAY_DEF <SFT.2_2>;
  #   SFT.4_20 = V_MAY_DEF <SFT.4_15>;
  D.1797_16 = includes (&D.1794);

unfortunately, at that time DCE already decided to remove the
array[1] initialization.

The difference seems to be in the Pointed-to sets;  alias1 contains

SFT.0_10
SFT.3_6
SFT.4_14
SFT.5_12
_first_5, its value escapes, points-to vars: { SFT.2 }
D.1810_8, points-to vars: { SFT.2 }
_ptr_9, its value escapes, points-to vars: { SFT.2 }

while alias2 is only

SFT.0_10
SFT.3_6
SFT.4_14
SFT.5_12
_ptr_8, points-to vars: { }


So maybe from there we miscompute flow-insensitive alias information
which differs in only

- SFT.1, UID 1815, int, is addressable, default def: SFT.1_3
+ SFT.1, UID 1815, int, is addressable, call clobbered, default def: SFT.1_3


I attached the two alias dumps for reference.  Maybe you can point
out what is going wrong - I'm somewhat lost here.

Thanks,
Richard.

[-- Attachment #2: alias1 dump --]
[-- Type: TEXT/PLAIN, Size: 4594 bytes --]


;; Function bool test4() (_Z5test4v)

Points-to analysis

Constraints:

ANYTHING = &ANYTHING
READONLY = &ANYTHING
INTEGER = &ANYTHING
ANYOFFSET = &ANYOFFSET
_first_5 = &array
con = _first_5
D.1810_8 = con
_ptr_9 = D.1810_8
D.1809 = _ptr_9
D.1796 = D.1809
D.1794 = D.1796
D.1797_16 = &ANYTHING

Collapsing static cycles and doing variable substitution:
Collapsing con into _first_5
Collapsing D.1810_8 into _first_5
Collapsing _ptr_9 into _first_5
Collapsing D.1809 into _first_5
Collapsing D.1796 into _first_5
Collapsing D.1794 into _first_5

Solving graph:

Points-to sets

NULL = { }
ANYTHING = { ANYTHING }
READONLY = { ANYTHING }
INTEGER = { ANYTHING }
ANYOFFSET = { ANYOFFSET }
_first_5 = { array }
array = { }
array.1 = { }
con = { array }
D.1810_8 = { array }
_ptr_9 = { array }
D.1809 = { array }
D.1796 = { array }
D.1794 = { array }
D.1797_16 = { ANYTHING }

test4: Total number of aliased vops: 0

Referenced variables in test4: 17

Variable: SFT.0, UID 1814, int *, default def: SFT.0_10

Variable: SFT.1, UID 1815, int, is addressable, default def: SFT.1_3

Variable: _first, UID 1808, int *

Variable: D.1809, UID 1809, struct iterator, sub-vars: { SFT.0 }

Variable: D.1810, UID 1810, int *

Variable: _ptr, UID 1811, int *

Variable: <retval>, UID 1782, int

Variable: array, UID 1783, int[2], is addressable, sub-vars: { SFT.2 SFT.1 }

Variable: con, UID 1784, struct container, sub-vars: { SFT.3 }

Variable: SFT.2, UID 1816, int, is addressable, call clobbered, default def: SFT.2_1

Variable: SFT.3, UID 1817, int *, default def: SFT.3_6

Variable: SFT.4, UID 1818, int *, is addressable, call clobbered, default def: SFT.4_14

Variable: SFT.5, UID 1819, int *, default def: SFT.5_12

Variable: D.1794, UID 1794, struct iterator, is addressable, sub-vars: { SFT.4 }

Variable: D.1795, UID 1795, int

Variable: D.1796, UID 1796, struct iterator, sub-vars: { SFT.5 }

Variable: D.1797, UID 1797, bool



Pointed-to sets for pointers in bool test4()

SFT.0_10
SFT.3_6
SFT.4_14
SFT.5_12
_first_5, its value escapes, points-to vars: { SFT.2 }
D.1810_8, points-to vars: { SFT.2 }
_ptr_9, its value escapes, points-to vars: { SFT.2 }


Flow-insensitive alias information for bool test4()

Aliased symbols

SFT.1, UID 1815, int, is addressable, default def: SFT.1_3
array, UID 1783, int[2], is addressable, sub-vars: { SFT.2 SFT.1 }
SFT.2, UID 1816, int, is addressable, call clobbered, default def: SFT.2_1
SFT.4, UID 1818, int *, is addressable, call clobbered, default def: SFT.4_14
D.1794, UID 1794, struct iterator, is addressable, sub-vars: { SFT.4 }

Dereferenced pointers


Type memory tags



Flow-sensitive alias information for bool test4()

SSA_NAME pointers


Name memory tags




Registering new PHI nodes in block #-1



Registering new PHI nodes in block #0

Updating SSA information for statement array[0] = 2;

Updating SSA information for statement array[1] = 4;

Updating SSA information for statement con.first = _first_5;

Updating SSA information for statement D.1810_8 = con.first;

Updating SSA information for statement D.1809.ptr = _ptr_9;

Updating SSA information for statement D.1796 = D.1809;

Updating SSA information for statement D.1794 = D.1796;

Updating SSA information for statement D.1797_16 = includes (&D.1794);



Symbols to be put in SSA form

array con D.1794 D.1809 SFT.0 SFT.1 SFT.2 SFT.3 SFT.4 

Incremental SSA update started at block: -1

Number of blocks in CFG: 1
Number of blocks to update: 1 (100%)

Affected blocks: 0 


bool test4() ()
{
  int * _ptr;
  struct iterator D.1809;
  int * D.1810;
  struct iterator D.1809;
  int * _first;
  struct container con;
  int array[2];
  bool D.1797;
  struct iterator D.1796;
  struct iterator D.1794;
  int D.1795;

<bb 0>:
  #   SFT.2_2 = V_MUST_DEF <SFT.2_1>;
  array[0] = 2;
  #   SFT.1_4 = V_MUST_DEF <SFT.1_3>;
  array[1] = 4;
  _first_5 = &array[0];
  #   SFT.3_7 = V_MUST_DEF <SFT.3_6>;
  con.first = _first_5;
  #   VUSE <SFT.3_7>;
  D.1810_8 = con.first;
  _ptr_9 = D.1810_8;
  #   SFT.0_11 = V_MUST_DEF <SFT.0_10>;
  D.1809.ptr = _ptr_9;
  #   SFT.5_13 = V_MUST_DEF <SFT.5_12>;
  #   VUSE <SFT.0_11>;
  D.1796 = D.1809;
  #   SFT.4_15 = V_MUST_DEF <SFT.4_14>;
  #   VUSE <SFT.5_13>;
  D.1794 = D.1796;
  #   SFT.2_19 = V_MAY_DEF <SFT.2_2>;
  #   SFT.4_20 = V_MAY_DEF <SFT.4_15>;
  D.1797_16 = includes (&D.1794);
  D.1795_17 = (int) D.1797_16;
  return D.1795_17;

}



[-- Attachment #3: alias2 dump --]
[-- Type: TEXT/PLAIN, Size: 3875 bytes --]


;; Function bool test4() (_Z5test4v)

Points-to analysis

Constraints:

ANYTHING = &ANYTHING
READONLY = &ANYTHING
INTEGER = &ANYTHING
ANYOFFSET = &ANYOFFSET
con = &array
_ptr_8 = &array
D.1809 = &array
D.1796 = D.1809
D.1794 = D.1796
D.1797_16 = &ANYTHING

Collapsing static cycles and doing variable substitution:
Collapsing D.1796 into D.1809
Collapsing D.1794 into D.1809

Solving graph:

Points-to sets

NULL = { }
ANYTHING = { ANYTHING }
READONLY = { ANYTHING }
INTEGER = { ANYTHING }
ANYOFFSET = { ANYOFFSET }
con = { array }
array = { }
array.1 = { }
_ptr_8 = { array }
D.1809 = { array }
D.1796 = { array }
D.1794 = { array }
D.1797_16 = { ANYTHING }

test4: Total number of aliased vops: 0

Referenced variables in test4: 17

Variable: SFT.0, UID 1814, int *, default def: SFT.0_10

Variable: SFT.1, UID 1815, int, is addressable, call clobbered, default def: SFT.1_3

Variable: _first, UID 1808, int *

Variable: D.1809, UID 1809, struct iterator, sub-vars: { SFT.0 }

Variable: D.1810, UID 1810, int *

Variable: _ptr, UID 1811, int *

Variable: <retval>, UID 1782, int

Variable: array, UID 1783, int[2], is addressable, sub-vars: { SFT.2 SFT.1 }

Variable: con, UID 1784, struct container, sub-vars: { SFT.3 }

Variable: SFT.2, UID 1816, int, is addressable, call clobbered, default def: SFT.2_1

Variable: SFT.3, UID 1817, int *, default def: SFT.3_6

Variable: SFT.4, UID 1818, int *, is addressable, call clobbered, default def: SFT.4_14

Variable: SFT.5, UID 1819, int *, default def: SFT.5_12

Variable: D.1794, UID 1794, struct iterator, is addressable, sub-vars: { SFT.4 }

Variable: D.1795, UID 1795, int

Variable: D.1796, UID 1796, struct iterator, sub-vars: { SFT.5 }

Variable: D.1797, UID 1797, bool



Pointed-to sets for pointers in bool test4()

SFT.0_10
SFT.3_6
SFT.4_14
SFT.5_12
_ptr_8, points-to vars: { }


Flow-insensitive alias information for bool test4()

Aliased symbols

SFT.1, UID 1815, int, is addressable, call clobbered, default def: SFT.1_3
array, UID 1783, int[2], is addressable, sub-vars: { SFT.2 SFT.1 }
SFT.2, UID 1816, int, is addressable, call clobbered, default def: SFT.2_1
SFT.4, UID 1818, int *, is addressable, call clobbered, default def: SFT.4_14
D.1794, UID 1794, struct iterator, is addressable, sub-vars: { SFT.4 }

Dereferenced pointers


Type memory tags



Flow-sensitive alias information for bool test4()

SSA_NAME pointers


Name memory tags




Registering new PHI nodes in block #-1



Registering new PHI nodes in block #0

Updating SSA information for statement array[0] = 2;

Updating SSA information for statement D.1794 = D.1796;

Updating SSA information for statement D.1797_16 = includes (&D.1794);



Symbols to be put in SSA form

array D.1794 SFT.1 SFT.2 SFT.4 

Incremental SSA update started at block: -1

Number of blocks in CFG: 1
Number of blocks to update: 1 (100%)

Affected blocks: 0 


bool test4() ()
{
  int * _ptr;
  struct iterator D.1809;
  int * D.1810;
  struct iterator D.1809;
  int * _first;
  struct container con;
  int array[2];
  bool D.1797;
  struct iterator D.1796;
  struct iterator D.1794;
  int D.1795;

<bb 0>:
  #   SFT.2_2 = V_MUST_DEF <SFT.2_1>;
  array[0] = 2;
  #   SFT.3_7 = V_MUST_DEF <SFT.3_6>;
  con.first = &array[0];
  _ptr_8 = &array[0];
  #   SFT.0_11 = V_MUST_DEF <SFT.0_10>;
  D.1809.ptr = &array[0];
  #   SFT.5_13 = V_MUST_DEF <SFT.5_12>;
  #   VUSE <SFT.0_11>;
  D.1796 = D.1809;
  #   SFT.4_15 = V_MUST_DEF <SFT.4_14>;
  #   VUSE <SFT.5_13>;
  D.1794 = D.1796;
  #   SFT.1_9 = V_MAY_DEF <SFT.1_3>;
  #   SFT.2_19 = V_MAY_DEF <SFT.2_2>;
  #   SFT.4_20 = V_MAY_DEF <SFT.4_15>;
  D.1797_16 = includes (&D.1794);
  D.1795_17 = (int) D.1797_16;
  return D.1795_17;

}

Re: Latent PTA bug?

[Daniel Berlin]

On Wed, 2005-07-27 at 13:08 +0200, Richard Guenther wrote:
> Hi all!
> 
> I reduced my array aliasing libstdc++ failures to the following
> testcase:
> 
> struct iterator
> {
>     int* ptr;
>     iterator(int* _ptr) : ptr(_ptr) {}
> };
> 
> struct container {
>     int* first;
>     container(int* _first) : first(_first) {}
>     iterator begin() { return iterator(first); }
> };
> 
> bool includes(const iterator&);
> 
> bool test4()
> {
>     int array[] = {2, 4};
>     container con(array);
>     return includes(con.begin());
> }
> 
> the weird thing now is, that the alias1 dump contains
> 
>   #   SFT.2_19 = V_MAY_DEF <SFT.2_2>;
>   #   SFT.4_20 = V_MAY_DEF <SFT.4_15>;
>   D.1797_16 = includes (&D.1794);

We get this right, you are doing something wrong in the conversion:

PTA calculates the set to be (in alias2):
_ptr_8 = { array }


and in alias1:

_ptr_9 = { array }

Which is right.

It looks like you aren't converting your new subvars right, or
something.

--Dan

Re: Latent PTA bug?

[Diego Novillo]

On Wed, Jul 27, 2005 at 01:08:38PM +0200, Richard Guenther wrote:

> Points-to sets
> 
> _first_5 = { array }
> array = { }
> array.1 = { }
> con = { array }
> D.1810_8 = { array }
> _ptr_9 = { array }
> D.1809 = { array }
> D.1796 = { array }
> D.1794 = { array }
> D.1797_16 = { ANYTHING }
> 
[ ... ]
> Points-to sets
> 
> con = { array }
> array = { }
> array.1 = { }
> _ptr_8 = { array }
> D.1809 = { array }
> D.1796 = { array }
> D.1794 = { array }
> D.1797_16 = { ANYTHING }
> 
PT solutions are correct.  It seems like you are not translating
them correctly in find_what_p_points_to().

Re: Latent PTA bug?

[Richard Guenther]

C testcase ;)

typedef struct { int *p; } X;
void includes(const X *);
void test4(void)
{
  int array[2] = { 2, 4 };
  X i;
  int * _p;
  _p = array;
  i.p = _p;
  includes(&i);
}

if you change that to

  i.p = array;

it works... !?  But I note this in the failing case:

Pointed-to sets for pointers in test4

SFT.2_6
_p_5, its value escapes, points-to vars: { SFT.1 }

i.e. while we see that the temporary pointer points to array[0], for
SFT.2_6 (i.p) we don't see anything?  So if we'd see { SFT.1 } here, too,
we'd be wrong in both cases.  -> aka my bug, correct?  So why don't
we get the points-to set for SFT.2_6?

Richard.

Re: Latent PTA bug?

[Diego Novillo]

On Wed, Jul 27, 2005 at 03:09:09PM +0200, Richard Guenther wrote:

> i.e. while we see that the temporary pointer points to array[0], for
> SFT.2_6 (i.p) we don't see anything?  So if we'd see { SFT.1 } here, too,
> we'd be wrong in both cases.  -> aka my bug, correct?
>
What is SFT.1?  array[0]?  Yes, that's your bug.  may-alias sets
should have all of array's SFTs.

> So why don't we get the points-to set for SFT.2_6?
>
The solver does not operate on SFTs.  Both _p_5 and i should
point to array here.

Re: Latent PTA bug?

[Richard Guenther]

On Wed, 27 Jul 2005, Diego Novillo wrote:

> On Wed, Jul 27, 2005 at 03:09:09PM +0200, Richard Guenther wrote:
> 
> > i.e. while we see that the temporary pointer points to array[0], for
> > SFT.2_6 (i.p) we don't see anything?  So if we'd see { SFT.1 } here, too,
> > we'd be wrong in both cases.  -> aka my bug, correct?
> >
> What is SFT.1?  array[0]?  Yes, that's your bug.  may-alias sets
> should have all of array's SFTs.
> 
> > So why don't we get the points-to set for SFT.2_6?
> >
> The solver does not operate on SFTs.  Both _p_5 and i should
> point to array here.

This seems to fix it.  Am I poking at the right place? ;)


*************** set_uids_in_ptset (bitmap into, bitmap f
*** 3246,3252 ****
        else if (TREE_CODE (vi->decl) == VAR_DECL 
  	       || TREE_CODE (vi->decl) == PARM_DECL)
  	{
! 	  if (found_anyoffset
  	      && var_can_have_subvars (vi->decl)
  	      && get_subvars_for_var (vi->decl))
  	    {
--- 3294,3301 ----
        else if (TREE_CODE (vi->decl) == VAR_DECL 
  	       || TREE_CODE (vi->decl) == PARM_DECL)
  	{
! 	  if ((found_anyoffset
! 	       || TREE_CODE (TREE_TYPE (vi->decl)) == ARRAY_TYPE)
  	      && var_can_have_subvars (vi->decl)
  	      && get_subvars_for_var (vi->decl))
  	    {

Re: Latent PTA bug?

[Daniel Berlin]

On Wed, 2005-07-27 at 16:02 +0200, Richard Guenther wrote:
> On Wed, 27 Jul 2005, Diego Novillo wrote:
> 
> > On Wed, Jul 27, 2005 at 03:09:09PM +0200, Richard Guenther wrote:
> > 
> > > i.e. while we see that the temporary pointer points to array[0], for
> > > SFT.2_6 (i.p) we don't see anything?  So if we'd see { SFT.1 } here, too,
> > > we'd be wrong in both cases.  -> aka my bug, correct?
> > >
> > What is SFT.1?  array[0]?  Yes, that's your bug.  may-alias sets
> > should have all of array's SFTs.
> > 
> > > So why don't we get the points-to set for SFT.2_6?
> > >
> > The solver does not operate on SFTs.  Both _p_5 and i should
> > point to array here.
> 
> This seems to fix it.  Am I poking at the right place? ;)

More or less.
What you want to say is that when we have &array, that we add anyoffset
to the points-to set, like we do with taking the address of the
structure.