Identifying a pointer to a structure

[Uday Khedker]

On 08/12/15 20:08, Richard Biener wrote:
> On Tue, Dec 8, 2015 at 3:35 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Tue, Dec 8, 2015 at 3:22 PM, Uday P. Khedker <uday@cse.iitb.ac.in> wrote:
>>>
>>> Richard Biener wrote on 12/03/2015 03:32 PM:
>>>> On Thu, Dec 3, 2015 at 8:54 AM, Uday P. Khedker <uday@cse.iitb.ac.in>
>>>> 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)
>> {
>>    <bb 2>:
>>    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;
>
>    <bb 2>:
>    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;
>
>    <bb 2>:
>    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.