Re: Add overflow infinity handling to VRP

[Ian Lance Taylor <iant at google dot com>]

Andrew Pinski <pinskia@physics.uc.edu> writes:

> > 
> > VRP currently uses TYPE_MAX_VALUE and TYPE_MIN_VALUE as infinity.
> > However, it is somewhat vague about the notion of overflow.  For
> > example, if a range has a max of TYPE_MAX_VALUE, and VRP subtracts 1,
> > the max will become TYPE_MAX_VALUE - 1.  That is not appropriate if
> > the max was set to TYPE_MAX_VALUE due to a signed overflow.  (It is
> > also possible that this might lead VRP to an incorrect conclusion in
> > some cases, although I didn't try to prove that.)
> 
> What VRP is doing is treating an overflow as a saturtation rather than
> pegging it to a specific value which is what your patch does.
> Saturation is actually the normal way of treating signed type overflow
> rather than wrapping so you are treading a standard way for a non
> standard way which is worse than the current behavior I think.

That makes no sense to me.  No common processor saturates on signed
overflow.  All common processors wrap on signed overflow.

Moreover, it's not really accurate to imply that VRP currently models
signed overflow as saturation.  VRP currently does not distinguish
TYPE_MAX from an overflow value.  That is not the same as saturating,
because VRP also uses TYPE_MAX to represent values that increase
steadily during loops.  I don't have a good word for what VRP does
today, but saturation is not it.

> > Index: gcc/tree-vrp.c
> > ===================================================================
> > --- gcc/tree-vrp.c	(revision 120343)
> > +++ gcc/tree-vrp.c	(working copy)
> > @@ -90,6 +90,151 @@ static sbitmap blocks_visited;
> >     of values that SSA name N_I may take.  */
> >  static value_range_t **vr_value;
> >  
> > +/* Hash table of minimum and maximum infinity values for types.  */
> > +static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
> > +  htab_t vrp_type_infinity_hash;
> > +
> 
> Is there really a good reason to put this hashtable in GC memory?

It points to trees created via copy_node.  The hashtable is the only
thing which will point to those objects.  If we don't use GC memory,
we risk memory lossage.

> > +  min = copy_node (TYPE_MIN_VALUE (type));
> > +  max = copy_node (TYPE_MAX_VALUE (type));
> 
> > +  h->hash = hash;
> > +  h->from = type;
> > +  h->to = tree_cons (min, max, NULL_TREE);
> 
> Also it seems a better idea to have a better way of doing this hash table.
> Like not using tree_map but a new struct which contains a hash, a type, and
> a min and max.  Using tree_cons just creates a Linked list for no reason and
> the memory usage adds up quickly if you a lot of types (which can happen for
> Ada).

I doubt that even Ada uses all that many signed integer types for
which VRP needs to record an overflow value.  You're right that this
could in principle be moved into non-GC memory.  But it's always going
to be an insignificant amount of memory.

> To me this should be controlled by a flag since this actually changes how we 
> treat signed type overflow because it makes signed type overflow a little more
> defined in that once an overflow happened, the variable is pegged at the min/max
> value.  Before signed type overflow was treated as a saturation which seems like
> a better way of representing signed type overflow.

I disagree.

Ian