On 08/12/15 20:08, Richard Biener wrote:
On Tue, Dec 8, 2015 at 3:35 PM, Richard Biener
wrote:
On Tue, Dec 8, 2015 at 3:22 PM, Uday P. Khedker wrote:
Richard Biener wrote on 12/03/2015 03:32 PM:
On Thu, Dec 3, 2015 at 8:54 AM, Uday P. Khedker
wrote:
We are implementing points-to analysis in GCC 4.7.2 and need to
distinguish
between
pointers to scalars and the pointers to structures. This distinction by
using the TYPE (TREE_TYPE)
hierarchy of the tree node of the pointer. We have two questions:
(a) Is it sufficient to check for the presence of RECORD_TYPE in type
hierarchy?
(b) Is it safe to assume that the RECORD_TYPE always appears as a leaf
node
in
the type description of any pointer to structure?
As an example, the tree nodes of a pointer to an integer (y) and a
pointer
to a structure (f)
below. It seems to support our hunch.
Yes, your observations are correct with respect to types.
But you can't rely on the pointer type for determining what kind of
object apointer points to.
First because of int *p = &s.i; with struct { int i; ... } s; points
to an int but it also points
to the start of an aggregate (and so can be trivially casted to a
pointer to s). Second because
GCCs middle-end (thus GIMPLE) ignores pointer types completely so you can
have
an SSA name a_1 of type int *X and a dereference a_1->b.c (thus a_1 points
to a
structure object even though it is of type int *).
Thanks for this word of caution :)
We understand your example (where SSA variable a_1 is of type int * and it
is dereferenced as a_1->b.c) with the following explanation: Since GIMPLE
based transformations ignore the type information completely, it could
differ flow sensitively for variables and is left implicit. In other words,
the type of a variable in an expression could differ from its type available
in VAR_DECL. For the above example, the type of a_1 in VAR_DECL is int *
whereas it is actually used as a pointer to a struct in the expression
a_1->b.c because of some code transformations.
Fortunately, we do not need the flow sensitive type of a variable in every
expression.
Our basic need is much simpler: We would like to know if a pointer is used
for iteratively accessing a recursive data structure (such as a list), in a
loop or recursive invocation as illustrated below. Due to some
transformations, can a pointer to int show up for such accesses in GIMPLE or
would it always have RECORD_TYPE in its type expression for such limited
situations?
while (...)
{
x = x->f;
...
}
At the source level, x is guaranteed to be a pointer to a struct. Our
question is: Does this guarantee hold in GIMPLE in the limited situations of
such iterative accesses to a recursive data structure?
No, it doesn't.
In particular, if this guarantee does not hold for a sequential access
pattern such as below, it is a non-issue for us.
x = x->f;
x = x->f;
x = x->f;
struct X { struct X *f; };
struct X *foo (void *p)
{
p = ((struct X *)p)->f;
p = ((struct X *)p)->f;
p = ((struct X *)p)->f;
return p;
}
is represented as
foo (void * p)
{
:
p_3 = MEM[(struct X *)p_2(D)].f;
p_4 = MEM[(struct X *)p_3].f;
p_5 = MEM[(struct X *)p_4].f;
return p_5;
}
all pointer types are void *. At accesses you have types of access of course,
but the pointers themselves can have any pointer type (such as void * here
or int * if you change the type of p).
Or
struct X { struct X *f; };
struct X *foo (void *p)
{
struct X **q = &((struct X *)p)->f;
p = *q;
q = &((struct X *)p)->f;
p = *q;
q = &((struct X *)p)->f;
p = *q;
return p;
}
foo (void * p)
{
struct X * * q;
:
p_4 = MEM[(struct X * *)p_1(D)];
p_6 = MEM[(struct X * *)p_4];
p_8 = MEM[(struct X * *)p_6];
return p_8;
}
or if you make q void ** then
foo (void * p)
{
void * * q;
:
p_4 = MEM[(void * *)p_1(D)];
p_6 = MEM[(void * *)p_4];
p_8 = MEM[(void * *)p_6];
return p_8;
}
Thanks for detailed explanations with illustrative examples. We needed
type information only to distinguish between iterative accesses in a
chain of non-struct pointers and a chain of struct pointers involving
the first field (because its offset it 0). For other fields, we are able
to make the distinctions. Looks like we will have to dive deeper in
building pointer assignment constraints borrowed from
tree-ssa-structalias.c (which is the part we understand least because
the student who adapted it has graduated long ago). Hope to find the
bandwidth to do it some time.
Thanks and regards,
Uday.
