[Tree][Static Analyzer] Tree representing types and svalues type

[Tree][Static Analyzer] Tree representing types and svalues type

[Pierrick Philippe]

Hi David, hi all,

I was playing along with APIs from the Static Analyzer and encountered a
segfault in gcc/tree.cc:5068 (i.e. in function build2 and failure is due
to a
gcc_assert call), after a call to
ana::region_model::get_representative_tree.

From my debugging of the problem, I realized that the svalue which I
built with
the SA API as the following from an element_region (C sample):

    const ana::region *base = elm_reg->get_base_region();
    // base_ptr is the svalue passed to get_representative_tree
    const ana::svalue *base_ptr = base->get_ptr_svalue(
                                                                  
TYPE_POINTER_TO(base->get_type),
                                                                   base);

I realized that the SA resulting in the call to get_ptr_svalue has
NULL_TREE as
type (return by get_type on base_ptr).  And this is because TYPE_POINTER_TO
(base->get_type) is returning a NULL_TREE.  I found my way around by calling
build_pointer_type(base->get_type()) which is currently building the
expecting
type.

But from this, two questions raised in my mind:

1. Is it coherent for the ana::region_model_manager::get_ptr_svalue to
return a sval with a null type?

2. Can a tree view as a tree_type_common member have an uninitialized
pointer_to member?  I think, but definitely not sure) that the member is not
initialized here by some part of the compiler, because I think that the
inner
type of regions and svalues are build by the SA by using the TREE_TYPE macro
directly from the GIMPLE.  I ask this question to know if this is a bug
and I
should try to do a minimal example out of it, or if it is a intended
behavior
for any reason from the compiler.

Thank you for reading me,

Pierrick

Re: [Tree][Static Analyzer] Tree representing types and svalues type

[David Malcolm]

On Tue, 2024-01-16 at 15:44 +0100, Pierrick Philippe wrote:
> Hi David, hi all,

Hi Pierrick.

> 
> I was playing along with APIs from the Static Analyzer and
> encountered a
> segfault in gcc/tree.cc:5068 (i.e. in function build2 and failure is
> due
> to a
> gcc_assert call), after a call to
> ana::region_model::get_representative_tree.
> 
> From my debugging of the problem, I realized that the svalue which I
> built with
> the SA API as the following from an element_region (C sample):
> 
>     const ana::region *base = elm_reg->get_base_region();
>     // base_ptr is the svalue passed to get_representative_tree
>     const ana::svalue *base_ptr = base->get_ptr_svalue(
>                                                                   
> TYPE_POINTER_TO(base->get_type),
>                                                                   
> base);
> 
> I realized that the SA resulting in the call to get_ptr_svalue has
> NULL_TREE as
> type (return by get_type on base_ptr).  And this is because
> TYPE_POINTER_TO
> (base->get_type) is returning a NULL_TREE.  I found my way around by
> calling
> build_pointer_type(base->get_type()) which is currently building the
> expecting
> type.

I confess that I've been quite sloppy in places with types in the
analyzer, keeping track of them when it's easy, but letting them be
NULL in places where getting a type was hard, or apparently not
possible.

Sorry about this.

I think my implementation is a bit muddled about what an svalue
actually is.

Informally, I think of an svalue as a partial function from bit offsets
to values of the bits.  For example:
* region_svalue: e.g. bit offsets 0-63 are the pointer to REG;
undefined elsewhere
* constant_svalue: e.g. given (int)42, bit offsets 0-31 are the
constant 42, encoded in the target's usual way; undefined elsewhere
* unknown_svalue: undefined everywhere
...etc, and the above definition doesn't need svalues to have a type.

The above is rather vague: how should this work for unaryop_svalue and
binop_svalue; these need to have types, so that we can think of them as
e.g. 
* "bits 0-31 are the result of a signed 32-bit int addition of the
values of bits 0-32 from X and Y when considered as signed 32-bit int".
* "bits 0-31 are the result of zero-extending bits 0-7 of X and
treating the result as uint32_t".

In the meantime, you can't rely on an svalue having a non-NULL type,
and hence it's often not possible to get a representative tree from an
svalue, since tree expressions must have non-NULL types.


> 
> But from this, two questions raised in my mind:
> 
> 1. Is it coherent for the ana::region_model_manager::get_ptr_svalue
> to
> return a sval with a null type?

It depends what you mean by "coherent"; given the sloppy approach
above, the answer is "yes".

> 
> 2. Can a tree view as a tree_type_common member have an uninitialized
> pointer_to member?

It shouldn't be uninitialized.  Perhaps the tree node isn't the right
kind?  You should use the TYPE_POINTER_TO macro to access the field,
which will use TYPE_CHECK to check that the node is a type in a debug
build of the compiler.

>   I think, but definitely not sure) that the member is not
> initialized here by some part of the compiler, because I think that
> the
> inner
> type of regions and svalues are build by the SA by using the
> TREE_TYPE macro
> directly from the GIMPLE.  I ask this question to know if this is a
> bug
> and I
> should try to do a minimal example out of it, or if it is a intended
> behavior
> for any reason from the compiler.

Sounds like a bug; please try to construct a minimal example.

Thanks
Dave

> 
> Thank you for reading me,
> 
> Pierrick
> 

Re: [Tree][Static Analyzer] Tree representing types and svalues type

[David Malcolm]

On Wed, 2024-01-17 at 17:52 -0500, David Malcolm wrote:
> On Tue, 2024-01-16 at 15:44 +0100, Pierrick Philippe wrote:
> > Hi David, hi all,
> 
> Hi Pierrick.
> 
> > 
> > I was playing along with APIs from the Static Analyzer and
> > encountered a
> > segfault in gcc/tree.cc:5068 (i.e. in function build2 and failure
> > is
> > due
> > to a
> > gcc_assert call), after a call to
> > ana::region_model::get_representative_tree.
> > 
> > From my debugging of the problem, I realized that the svalue which
> > I
> > built with
> > the SA API as the following from an element_region (C sample):
> > 
> >     const ana::region *base = elm_reg->get_base_region();
> >     // base_ptr is the svalue passed to get_representative_tree
> >     const ana::svalue *base_ptr = base->get_ptr_svalue(
> >                                                                   
> > TYPE_POINTER_TO(base->get_type),
> >                                                                   
> > base);
> > 
> > I realized that the SA resulting in the call to get_ptr_svalue has
> > NULL_TREE as
> > type (return by get_type on base_ptr).  And this is because
> > TYPE_POINTER_TO
> > (base->get_type) is returning a NULL_TREE.  I found my way around
> > by
> > calling
> > build_pointer_type(base->get_type()) which is currently building
> > the
> > expecting
> > type.
> 
> I confess that I've been quite sloppy in places with types in the
> analyzer, keeping track of them when it's easy, but letting them be
> NULL in places where getting a type was hard, or apparently not
> possible.
> 
> Sorry about this.
> 
> I think my implementation is a bit muddled about what an svalue
> actually is.
> 
> Informally, I think of an svalue as a partial function from bit
> offsets
> to values of the bits.  For example:
> * region_svalue: e.g. bit offsets 0-63 are the pointer to REG;
> undefined elsewhere
> * constant_svalue: e.g. given (int)42, bit offsets 0-31 are the
> constant 42, encoded in the target's usual way; undefined elsewhere
> * unknown_svalue: undefined everywhere
> ...etc, and the above definition doesn't need svalues to have a type.
> 
> The above is rather vague: how should this work for unaryop_svalue
> and
> binop_svalue; these need to have types, so that we can think of them
> as
> e.g. 
> * "bits 0-31 are the result of a signed 32-bit int addition of the
> values of bits 0-32 from X and Y when considered as signed 32-bit
> int".
> * "bits 0-31 are the result of zero-extending bits 0-7 of X and
> treating the result as uint32_t".
> 
> In the meantime, you can't rely on an svalue having a non-NULL type,
> and hence it's often not possible to get a representative tree from
> an
> svalue, since tree expressions must have non-NULL types.
> 
> 
> > 
> > But from this, two questions raised in my mind:
> > 
> > 1. Is it coherent for the ana::region_model_manager::get_ptr_svalue
> > to
> > return a sval with a null type?
> 
> It depends what you mean by "coherent"; given the sloppy approach
> above, the answer is "yes".
> 
> > 
> > 2. Can a tree view as a tree_type_common member have an
> > uninitialized
> > pointer_to member?
> 
> It shouldn't be uninitialized.  Perhaps the tree node isn't the right
> kind?  You should use the TYPE_POINTER_TO macro to access the field,
> which will use TYPE_CHECK to check that the node is a type in a debug
> build of the compiler.

I think that it *can* be NULL, though (as opposed to uninitialized).  I
believe that this field is essentially a cache for build_pointer_type
and build_pointer_type_for_mode, so that we can lazily create pointers
to types on demand.  (But I could be wrong here)

Dave

> 
> >   I think, but definitely not sure) that the member is not
> > initialized here by some part of the compiler, because I think that
> > the
> > inner
> > type of regions and svalues are build by the SA by using the
> > TREE_TYPE macro
> > directly from the GIMPLE.  I ask this question to know if this is a
> > bug
> > and I
> > should try to do a minimal example out of it, or if it is a
> > intended
> > behavior
> > for any reason from the compiler.
> 
> Sounds like a bug; please try to construct a minimal example.
> 
> Thanks
> Dave
> 
> > 
> > Thank you for reading me,
> > 
> > Pierrick
> > 
> 

Re: [Tree][Static Analyzer] Tree representing types and svalues type

[Pierrick Philippe]

[-- Attachment #1: Type: text/plain, Size: 2991 bytes --]

On 17/01/2024 23:52, David Malcolm wrote:
> On Tue, 2024-01-16 at 15:44 +0100, Pierrick Philippe wrote:
>> Hi David, hi all,
> Hi Pierrick.
First, thanks for you answer.
[stripping]
> I confess that I've been quite sloppy in places with types in the
> analyzer, keeping track of them when it's easy, but letting them be
> NULL in places where getting a type was hard, or apparently not
> possible.
>
> Sorry about this.
>
> I think my implementation is a bit muddled about what an svalue
> actually is.
>
> Informally, I think of an svalue as a partial function from bit offsets
> to values of the bits.  For example:
> * region_svalue: e.g. bit offsets 0-63 are the pointer to REG;
> undefined elsewhere
> * constant_svalue: e.g. given (int)42, bit offsets 0-31 are the
> constant 42, encoded in the target's usual way; undefined elsewhere
> * unknown_svalue: undefined everywhere
> ...etc, and the above definition doesn't need svalues to have a type.
>
> The above is rather vague: how should this work for unaryop_svalue and
> binop_svalue; these need to have types, so that we can think of them as
> e.g. 
> * "bits 0-31 are the result of a signed 32-bit int addition of the
> values of bits 0-32 from X and Y when considered as signed 32-bit int".
> * "bits 0-31 are the result of zero-extending bits 0-7 of X and
> treating the result as uint32_t".

I do understand, but here, the thing is that the analyzer built a
region_svalue without any type. And thought it was a bit weird.

But I do get your point here.

> In the meantime, you can't rely on an svalue having a non-NULL type,
> and hence it's often not possible to get a representative tree from an
> svalue, since tree expressions must have non-NULL types.

But then, shouldn't the analyzer have a defensive approach in
get_representative_tree and return a NULL_TREE in such cases? Because
the segfault is happening behind the scene. Maybe it shouldn't, I have
no idea what would be the best approach here.

>> But from this, two questions raised in my mind:
>>
>> 1. Is it coherent for the ana::region_model_manager::get_ptr_svalue
>> to
>> return a sval with a null type?
> It depends what you mean by "coherent"; given the sloppy approach
> above, the answer is "yes".
(nod)
>> 2. Can a tree view as a tree_type_common member have an uninitialized
>> pointer_to member?
> It shouldn't be uninitialized.  Perhaps the tree node isn't the right
> kind?  You should use the TYPE_POINTER_TO macro to access the field,
> which will use TYPE_CHECK to check that the node is a type in a debug
> build of the compiler.
Well, I'm pretty sure I didn't build it myself and only used macros
and API functions to get that type. And this is what is confusing me.

[stripping]

> Sounds like a bug; please try to construct a minimal example.
Sure, I'll try to build a minimal example.
Will have to use a plugin to do so though, hope that won't be a problem.

Thanks,
Pierrick

> Thanks
> Dave
>
>> Thank you for reading me,
>>
>> Pierrick