[RFC] Get rid of awkward semantics for subtypes

[RFC] Get rid of awkward semantics for subtypes

[Eric Botcazou]

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

Hi,

we're almost ready to get rid of the awkward semantics that is implemented in 
the middle-end and the optimizers for subtypes (INTEGER_TYPEs with a non-null 
TREE_TYPE); this should overall simplify things, make the support for invalid 
values in Ada more robust and expose more optimization opportunities.

Patches have already been written and tested (I've attached the non-gigi part 
we currently use, preparatory patches are required for gigi first).  All the 
subtypes are given maximal bounds for their precision, except for TYPE_DOMAIN 
of array types like in C, and thus become first class citizens.  This makes 
it possible to eliminate code in gigi, the gimplifier, the loop optimizer, 
the VRP pass, etc. needed to specifically support their special semantics.

This in turn means that the gimplification will eliminate most of the casts 
between subtypes and base types, making the optimizers more effective.  The 
exception will be the VRP pass, most notably when checks are off in Ada, so 
we'll need to be able to drive VRP differently from gigi.

Comments/suggestions welcome.


	* fold-const.c (fold_truth_not_expr) <CONVERT_EXPR>: Do not strip
	it if the destination type is boolean.
	* tree-chrec.c (avoid_arithmetics_in_type_p): Delete.
	(convert_affine_scev): Remove call to above function.
	(chrec_convert_aggressive): Likewise.
	* tree-scalar-evolution.c (follow_ssa_edge_expr) <PLUS_EXPR>:
	Propagate the type of the first operand.
	(follow_ssa_edge_in_rhs) <GIMPLE_BINARY_RHS>: Likewise
	* tree-ssa.c (useless_type_conversion_p_1): Do not specifically return
	false for conversions involving subtypes.
	* tree-vrp.c (vrp_val_max): Do not get to the base type.
	(vrp_val_min): Likewise.
	(needs_overflow_infinity): Do not special-case subtypes.
	(extract_range_from_unary_expr): Do not use the base types.


-- 
Eric Botcazou

[-- Attachment #2: p.diff --]
[-- Type: text/x-diff, Size: 7056 bytes --]

Index: tree-vrp.c
===================================================================
--- tree-vrp.c	(revision 145851)
+++ tree-vrp.c	(working copy)
@@ -121,7 +121,7 @@ DEF_VEC_ALLOC_O(switch_update, heap);
 static VEC (switch_update, heap) *to_update_switch_stmts;
 
 
-/* Return the maximum value for TYPEs base type.  */
+/* Return the maximum value for TYPE.  */
 
 static inline tree
 vrp_val_max (const_tree type)
@@ -129,14 +129,10 @@ vrp_val_max (const_tree type)
   if (!INTEGRAL_TYPE_P (type))
     return NULL_TREE;
 
-  /* For integer sub-types the values for the base type are relevant.  */
-  if (TREE_TYPE (type))
-    type = TREE_TYPE (type);
-
   return TYPE_MAX_VALUE (type);
 }
 
-/* Return the minimum value for TYPEs base type.  */
+/* Return the minimum value for TYPE.  */
 
 static inline tree
 vrp_val_min (const_tree type)
@@ -144,10 +140,6 @@ vrp_val_min (const_tree type)
   if (!INTEGRAL_TYPE_P (type))
     return NULL_TREE;
 
-  /* For integer sub-types the values for the base type are relevant.  */
-  if (TREE_TYPE (type))
-    type = TREE_TYPE (type);
-
   return TYPE_MIN_VALUE (type);
 }
 
@@ -188,11 +180,7 @@ vrp_val_is_min (const_tree val)
 static inline bool
 needs_overflow_infinity (const_tree type)
 {
-  return (INTEGRAL_TYPE_P (type)
-	  && !TYPE_OVERFLOW_WRAPS (type)
-	  /* Integer sub-types never overflow as they are never
-	     operands of arithmetic operators.  */
-	  && !(TREE_TYPE (type) && TREE_TYPE (type) != type));
+  return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type);
 }
 
 /* Return whether TYPE can support our overflow infinity
@@ -2708,13 +2696,6 @@ extract_range_from_unary_expr (value_ran
       tree inner_type = TREE_TYPE (op0);
       tree outer_type = type;
 
-      /* Always use base-types here.  This is important for the
-	 correct signedness.  */
-      if (TREE_TYPE (inner_type))
-	inner_type = TREE_TYPE (inner_type);
-      if (TREE_TYPE (outer_type))
-	outer_type = TREE_TYPE (outer_type);
-
       /* If VR0 is varying and we increase the type precision, assume
 	 a full range for the following transformation.  */
       if (vr0.type == VR_VARYING
Index: tree-scalar-evolution.c
===================================================================
--- tree-scalar-evolution.c	(revision 145851)
+++ tree-scalar-evolution.c	(working copy)
@@ -1182,6 +1182,7 @@ follow_ssa_edge_expr (struct loop *loop,
       /* This case is under the form "rhs0 +- rhs1".  */
       rhs0 = TREE_OPERAND (expr, 0);
       rhs1 = TREE_OPERAND (expr, 1);
+      type = TREE_TYPE (rhs0);
       STRIP_TYPE_NOPS (rhs0);
       STRIP_TYPE_NOPS (rhs1);
       return follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
@@ -1216,16 +1217,17 @@ static t_bool
 follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
 			gimple halting_phi, tree *evolution_of_loop, int limit)
 {
-  tree type = TREE_TYPE (gimple_assign_lhs (stmt));
   enum tree_code code = gimple_assign_rhs_code (stmt);
 
   switch (get_gimple_rhs_class (code))
     {
     case GIMPLE_BINARY_RHS:
-      return follow_ssa_edge_binary (loop, stmt, type,
-				     gimple_assign_rhs1 (stmt), code,
-				     gimple_assign_rhs2 (stmt),
-				     halting_phi, evolution_of_loop, limit);
+      {
+	tree rhs1 = gimple_assign_rhs1 (stmt);
+	return follow_ssa_edge_binary (loop, stmt, TREE_TYPE (rhs1), rhs1,
+				       code, gimple_assign_rhs2 (stmt),
+				       halting_phi, evolution_of_loop, limit);
+      }
     case GIMPLE_SINGLE_RHS:
       return follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
 				   halting_phi, evolution_of_loop, limit);
@@ -1233,6 +1235,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
       if (code == NOP_EXPR)
 	{
 	  /* This assignment is under the form "a_1 = (cast) rhs.  */
+	  tree type = TREE_TYPE (gimple_assign_lhs (stmt));
 	  t_bool res
 	    = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
 				    halting_phi, evolution_of_loop, limit);
Index: fold-const.c
===================================================================
--- fold-const.c	(revision 145851)
+++ fold-const.c	(working copy)
@@ -3732,10 +3732,12 @@ fold_truth_not_expr (tree arg)
       return invert_truthvalue (TREE_OPERAND (arg, 0));
 
     case NOP_EXPR:
+    case CONVERT_EXPR:
       if (TREE_CODE (TREE_TYPE (arg)) == BOOLEAN_TYPE)
 	return build1 (TRUTH_NOT_EXPR, type, arg);
 
-    case CONVERT_EXPR:
+      /* ... fall through ...  */
+
     case FLOAT_EXPR:
       return build1 (TREE_CODE (arg), type,
 		     invert_truthvalue (TREE_OPERAND (arg, 0)));
Index: tree-chrec.c
===================================================================
--- tree-chrec.c	(revision 145851)
+++ tree-chrec.c	(working copy)
@@ -1100,21 +1100,6 @@ nb_vars_in_chrec (tree chrec)
     }
 }
 
-/* Returns true if TYPE is a type in that we cannot directly perform
-   arithmetics, even though it is a scalar type.  */
-
-static bool
-avoid_arithmetics_in_type_p (const_tree type)
-{
-  /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed
-     in the subtype, but a base type must be used, and the result then can
-     be casted to the subtype.  */
-  if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != NULL_TREE)
-    return true;
-
-  return false;
-}
-
 static tree chrec_convert_1 (tree, tree, gimple, bool);
 
 /* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
@@ -1136,10 +1121,6 @@ convert_affine_scev (struct loop *loop,
   tree new_base, new_step;
   tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
 
-  /* If we cannot perform arithmetic in TYPE, avoid creating an scev.  */
-  if (avoid_arithmetics_in_type_p (type))
-    return false;
-
   /* In general,
      (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
      but we must check some assumptions.
@@ -1342,10 +1323,6 @@ chrec_convert_aggressive (tree type, tre
   if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
     return NULL_TREE;
 
-  /* If we cannot perform arithmetic in TYPE, avoid creating an scev.  */
-  if (avoid_arithmetics_in_type_p (type))
-    return NULL_TREE;
-
   rtype = POINTER_TYPE_P (type) ? sizetype : type;
 
   left = CHREC_LEFT (chrec);
Index: tree-ssa.c
===================================================================
--- tree-ssa.c	(revision 145851)
+++ tree-ssa.c	(working copy)
@@ -923,19 +923,9 @@ useless_type_conversion_p_1 (tree outer_
 	  || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
 	return false;
 
-      /* Conversions from a non-base to a base type are not useless.
-	 This way we preserve the invariant to do arithmetic in
-	 base types only.  */
-      if (TREE_TYPE (inner_type)
-	  && TREE_TYPE (inner_type) != inner_type
-	  && (TREE_TYPE (outer_type) == outer_type
-	      || TREE_TYPE (outer_type) == NULL_TREE))
-	return false;
-
       /* We don't need to preserve changes in the types minimum or
 	 maximum value in general as these do not generate code
 	 unless the types precisions are different.  */
-
       return true;
     }
 

Re: [RFC] Get rid of awkward semantics for subtypes

[Richard Kenner]

> we're almost ready to get rid of the awkward semantics that is
> implemented in the middle-end and the optimizers for subtypes
> (INTEGER_TYPEs with a non-null TREE_TYPE); this should overall simplify
> things, make the support for invalid values in Ada more robust and expose
> more optimization opportunities.

Let me say more about this since the issue here is very subtle.

If we have a type with TYPE_MIN_VALUE of 10 and TYPE_MAX_VALUE of 20, what
we'ree declaring to the middle-end is "any valid value of this type is
between 10 and 20".  That's consistent with Ada's usage.  The problem is
when you pose the question "what if the value is *invalid*?" (e.g., an
uninitialized variable that happens to be outside the range).  The
assumption of the middle-end, which is the case for C-like languages, is
that it's undefined.  This means the compiler is free to generate code
under the assumption it *is* valid, because *any* result is acceptable if
it isn't valid.

For Ada, there are two issues.  First, there's a language-defined way of
asking "is this object valid?" and it has to work.  If the compiler assumes
all values have to be valid, clearly it can't.  But the more major problem
is that an invalid value is *not* undefined (what Ada call "erroneous") in
Ada.  Instead, it's something weaker called a "bounded error" and there are
limit on "how bad it can get".  For example, if a variable is invalid, it
must have *the same* invalid value each time.

The middle-end says "for the result to be defined, the value must be valid,
so we assume it is".  But for Ada, the proper statement is "if I can prove
the valid is valid, then we can assume it's in the range for the type".

There are many cases when you can prove the value can be treated as valid.
One interesting case is based on the fact that suppressing a
language-defined check is erroneous if that check would fail.  So, for

	A: = B + 1;

you *can* assume A is valid.  That assignment *requires* a check and if the
check is suppressed and would fail, then the result is undefined
("erroneous") if A is invalid, which is the semantics that the middle-end
currently has.  There are many other cases when you can statically
determine that a variable must be valid.

So the "proper" way of dealing with this would be to have VRP propagate a
"valid" property using fairly easy-to-state rules and then only assume a
value within the subtype bounds if it can prove it to be valid (otherwise,
the type bounds must be used).

We've thought about doing this, but it's a lot of work and the benefit
isn't clear.  From a theoretical point of view, the more an optimizer knows
about a program, the better it can do and knowing that valid values are in
specified ranges certainly conveys some information. One could also argue
that such information is even more valuable in an IPA context.

But from a practical point of view, it's much less clear.  How much does
the range information actually buy in practice?  In how many cases do we
know that a variable will always be valid?  Might there be something about
that subset that makes the range information less useful for it?  We just
don't know the answers to these questions.

But in the absence of doing that, the present situation is problematic.
It's true that only the most pedantic programmer would care about the
distinction between a "bounded error" and "erroneous behavior", so one
could argue that this problem isn't that serious, but there do exist such
people in the Ada world.  Similarly, it's possible to find some solutions
to the "test for validity" case that don't involve the full solution above,
but they're also work.  But the existance of both problems together suggest
that the present situation isn't workable and it's not clear that it's
worth fixing "properly" at this time.

Because this decision may be revisited and it may be found worthwhile to
add the mechanism above and "do this right", it's important that we not
remove code that supports the ranges unless absolutely necessary because
doing so would greatly increase the amount of working needed to do this
right and thus make it even less likely.  (And, in any event, these types
*are* needed for array bounds, so must be supported at some level.)

Re: [RFC] Get rid of awkward semantics for subtypes

[Robert Dewar]

Richard Kenner wrote:

> There are many cases when you can prove the value can be treated as valid.
> One interesting case is based on the fact that suppressing a
> language-defined check is erroneous if that check would fail.  So, for
> 
> 	A: = B + 1;
> 
> you *can* assume A is valid.

Yes, but I don't think it is a good idea to do so. I think you get
unexpected behavior if you make this kind of assumption, and I do
not think anyone has demonstrated sufficient optimization advantage
to make it worth while to get this unexpected behavior. The compiler
should not assume validity unless it can prove that the value is
actually in the declared range in my opinion.

> So the "proper" way of dealing with this would be to have VRP propagate a
> "valid" property using fairly easy-to-state rules and then only assume a
> value within the subtype bounds if it can prove it to be valid (otherwise,
> the type bounds must be used).
> 
> We've thought about doing this, but it's a lot of work and the benefit
> isn't clear.  From a theoretical point of view, the more an optimizer knows
> about a program, the better it can do and knowing that valid values are in
> specified ranges certainly conveys some information. One could also argue
> that such information is even more valuable in an IPA context.
> 
> But from a practical point of view, it's much less clear.  How much does
> the range information actually buy in practice?  In how many cases do we
> know that a variable will always be valid?  Might there be something about
> that subset that makes the range information less useful for it?  We just
> don't know the answers to these questions.

Right, although what you say is theoretically true, I doubt in practice
it will make a difference in performance, and it will sure lead to
surprises for the programmer.
> 
> But in the absence of doing that, the present situation is problematic.
> It's true that only the most pedantic programmer would care about the
> distinction between a "bounded error" and "erroneous behavior",

I disagree, the rules in Ada 95 are formulated so that programmers do
NOT see unexpected behavior from e.g. uninitialized values, if such
a value is invalid, the program behaves in some reasonable way, and
is NOT erroneous, and that's definitely important.

> so one
> could argue that this problem isn't that serious, but there do exist such
> people in the Ada world.  Similarly, it's possible to find some solutions
> to the "test for validity" case that don't involve the full solution above,
> but they're also work.  But the existance of both problems together suggest
> that the present situation isn't workable and it's not clear that it's
> worth fixing "properly" at this time.

The current situation (which this change corrects) is not only 
theoretically wrong, but I think is pragmatically undesirable, in
that it can indeed result in unexpected results.

If you have

   X, Y : Integer range 1 .. 10;

and X has the value 11 and Y has the value 10

then when you write

    if X > Y then ...

you expect this to be true.

Formal Ada semantics says that it MUST be true if X is merely invalid
(e.g. results from an uninitialized variable). Richard is pointing out
that it is allowed to be false if X is abnormal because the program is
erroneous in this case (e.g. if the value in X comes from a missed
suppressed overflow check).

Yes, true, but it is still 100% undesirable to give anything else than
true here.

Once again, my view is that the compiler should not assume that
variables are in the required range unless it can prove that they
are actually in that range, it is not good enough to prove they
are valid in the absence of erroneousness.

In practice, gcc will often be able to deduce the actual ranges
anyway, e.g. if you write

(for the above declarations)

X := X + 1;
Y := Y + 1;

and you have checks enabled, then the check will inform gcc that
the variables are now in the range 1 .. 10.

The kind of case Richard is talking about is the following:

    subtype R is Integer range 1 .. 10;
    X : R := 1;
    A : array (R) of Integer;

    X := X + 1;
    A (X) := 10;

    --  can we assume X is in range 1..10 and avoid the check

If checks are enabled for both assignments, the answer is
yes, since the first assignment will do the check. Currently
the front end will generate checks for the array subscript,
but gcc should be able to eliminate the second check, based
on the knowledge from the first check.

If checks are disabled for both assignments, the answer is
yes, since the second assignment is erroneous if X is out
of range (and I think any programmer would expect random
memory destruction in this case, as we would get in C
with no checks).

The one case where Richard's argument holds theoretically,
is when checks are disabled for the first assignment and
enabled for the second assignment.

In this case, theoretically the compiler can omit the
check in the second case, since it can determine that
either X is in range or the program is erroneous.

However I think it is not a good idea to take advantage
of this permission:

a) in any case it will happen very rarely in practice
b) there is no demonstration that this will be worthwhile
c) it leads to unexpected behavior.

I think programmers expect a check to be present if
checks are enabled for the second assignment.

> Because this decision may be revisited and it may be found worthwhile to
> add the mechanism above and "do this right", it's important that we not
> remove code that supports the ranges unless absolutely necessary because
> doing so would greatly increase the amount of working needed to do this
> right and thus make it even less likely.  (And, in any event, these types
> *are* needed for array bounds, so must be supported at some level.)

*that* seems reasonable

Re: [RFC] Get rid of awkward semantics for subtypes

[Dave Korn]

Robert Dewar wrote:

> The compiler
> should not assume validity unless it can prove that the value is
> actually in the declared range in my opinion.

  We could add a "-fstrict-validity=" by analogy to "-fstrict-alias=".  Ada
and C would want to have different default settings I imagine.

    cheers,
      DaveK

Re: [RFC] Get rid of awkward semantics for subtypes

[Richard Guenther]

On Fri, Apr 10, 2009 at 12:03 AM, Eric Botcazou <ebotcazou@adacore.com> wrote:
> Hi,
>
> we're almost ready to get rid of the awkward semantics that is implemented in
> the middle-end and the optimizers for subtypes (INTEGER_TYPEs with a non-null
> TREE_TYPE); this should overall simplify things, make the support for invalid
> values in Ada more robust and expose more optimization opportunities.
>
> Patches have already been written and tested (I've attached the non-gigi part
> we currently use, preparatory patches are required for gigi first).  All the
> subtypes are given maximal bounds for their precision, except for TYPE_DOMAIN
> of array types like in C, and thus become first class citizens.  This makes
> it possible to eliminate code in gigi, the gimplifier, the loop optimizer,
> the VRP pass, etc. needed to specifically support their special semantics.
>
> This in turn means that the gimplification will eliminate most of the casts
> between subtypes and base types, making the optimizers more effective.  The
> exception will be the VRP pass, most notably when checks are off in Ada, so
> we'll need to be able to drive VRP differently from gigi.

I wonder what this exception in VRP looks like?  I also wonder if adding a test
to the gimplifier that all integral typed DECL types have NULL TREE_TYPE
and TYPE_MIN/MAX_VALUE according to their TYPE_PRECISION would
pass with your changes (there may be such odd cases with other frontends ...).

Thanks for this work - in general I support this (well, you know that ;)).

Richard.

>
> Comments/suggestions welcome.
>
>
>        * fold-const.c (fold_truth_not_expr) <CONVERT_EXPR>: Do not strip
>        it if the destination type is boolean.
>        * tree-chrec.c (avoid_arithmetics_in_type_p): Delete.
>        (convert_affine_scev): Remove call to above function.
>        (chrec_convert_aggressive): Likewise.
>        * tree-scalar-evolution.c (follow_ssa_edge_expr) <PLUS_EXPR>:
>        Propagate the type of the first operand.
>        (follow_ssa_edge_in_rhs) <GIMPLE_BINARY_RHS>: Likewise
>        * tree-ssa.c (useless_type_conversion_p_1): Do not specifically return
>        false for conversions involving subtypes.
>        * tree-vrp.c (vrp_val_max): Do not get to the base type.
>        (vrp_val_min): Likewise.
>        (needs_overflow_infinity): Do not special-case subtypes.
>        (extract_range_from_unary_expr): Do not use the base types.
>
>
> --
> Eric Botcazou
>

Re: [RFC] Get rid of awkward semantics for subtypes

[Robert Dewar]

Dave Korn wrote:
> Robert Dewar wrote:
> 
>> The compiler
>> should not assume validity unless it can prove that the value is
>> actually in the declared range in my opinion.
> 
>   We could add a "-fstrict-validity=" by analogy to "-fstrict-alias=".  Ada
> and C would want to have different default settings I imagine.

Well I don't think C has this issue, since it does not have subtype
ranges??? Anyway I would not object to such a switch, providing that
the default is -fno-strict-validity!
> 
>     cheers,
>       DaveK
> 

Re: [RFC] Get rid of awkward semantics for subtypes

[Eric Botcazou]

> I wonder what this exception in VRP looks like?

I wasn't specifically referring to an exception in VRP.  I think that, when 
checks are off, it would be sufficient for gigi to emit sort of assertions
for arguments on function entry (like your VRP patch did) and for return 
values on function calls; VRP would then just propagate them.

Could ASSERT_EXPR be used for this purpose, i.e. could it be made a first 
class GENERIC (or GIMPLE) expression that front-ends could emit (during 
gimplification)?

> I also wonder if adding a test to the gimplifier that all integral typed
> DECL types have NULL TREE_TYPE and TYPE_MIN/MAX_VALUE according to their
> TYPE_PRECISION would pass with your changes (there may be such odd cases
> with other frontends ...).

Note that the changes don't eliminate subtypes (gigi generates the same 
GENERIC code), their actual bounds are only made private to gigi and their 
visible bounds set to that of the base type; IOW there is no lowering pass, 
except for the gimplification that will remove unnecessary casts.

I think that the invariant should be that all integral types that appear in 
the code (types for declarations and expressions) have maximal bounds for 
their precision; "range" types should only be descriptive.

-- 
Eric Botcazou

Re: [RFC] Get rid of awkward semantics for subtypes

[Richard Guenther]

On Sun, Apr 12, 2009 at 9:37 AM, Eric Botcazou <ebotcazou@adacore.com> wrote:
>> I wonder what this exception in VRP looks like?
>
> I wasn't specifically referring to an exception in VRP.  I think that, when
> checks are off, it would be sufficient for gigi to emit sort of assertions
> for arguments on function entry (like your VRP patch did) and for return
> values on function calls; VRP would then just propagate them.
>
> Could ASSERT_EXPR be used for this purpose, i.e. could it be made a first
> class GENERIC (or GIMPLE) expression that front-ends could emit (during
> gimplification)?

Yes, we could do that.  Though a simpler form may be preferable, like
directly specifying a constant range/anti-range instead of encoding these
in (multiple) ASSERT_EXPRs.

I will think of something.

As for Ada - both function entry and exit constraints will be checked by
the caller/callee, correct?  So that once you inline VRP should be able
to derive the ranges from existing checks?  Thus - a IPA VRP pass should
be able to verify these properties across functions?

>> I also wonder if adding a test to the gimplifier that all integral typed
>> DECL types have NULL TREE_TYPE and TYPE_MIN/MAX_VALUE according to their
>> TYPE_PRECISION would pass with your changes (there may be such odd cases
>> with other frontends ...).
>
> Note that the changes don't eliminate subtypes (gigi generates the same
> GENERIC code), their actual bounds are only made private to gigi and their
> visible bounds set to that of the base type; IOW there is no lowering pass,
> except for the gimplification that will remove unnecessary casts.
>
> I think that the invariant should be that all integral types that appear in
> the code (types for declarations and expressions) have maximal bounds for
> their precision; "range" types should only be descriptive.

Yes, I agree.  I volunteer to prepare a verification pass that asserts this
property during gimplification.

Thanks,
Richard.

Re: [RFC] Get rid of awkward semantics for subtypes

[Eric Botcazou]

> Yes, we could do that.  Though a simpler form may be preferable, like
> directly specifying a constant range/anti-range instead of encoding these
> in (multiple) ASSERT_EXPRs.
>
> I will think of something.

Thanks.

> As for Ada - both function entry and exit constraints will be checked by
> the caller/callee, correct?  So that once you inline VRP should be able
> to derive the ranges from existing checks?  Thus - a IPA VRP pass should
> be able to verify these properties across functions?

No, the model used by GNAT is "lazy" validity checks: the various validity 
checks are emitted just before uses of the value that are deemed sufficiently 
dangerous, as controlled by -gnatVx.  Parameter and return values are not
checked, unless explicitly requested.

VRP should be able to derive ranges when checks are present, but we would also 
need to be able to force ranges at will when checks are not present.

-- 
Eric Botcazou

Re: [RFC] Get rid of awkward semantics for subtypes

[Richard Guenther]

On Fri, Apr 10, 2009 at 12:03 AM, Eric Botcazou <ebotcazou@adacore.com> wrote:
> Hi,
>
> we're almost ready to get rid of the awkward semantics that is implemented in
> the middle-end and the optimizers for subtypes (INTEGER_TYPEs with a non-null
> TREE_TYPE); this should overall simplify things, make the support for invalid
> values in Ada more robust and expose more optimization opportunities.
>
> Patches have already been written and tested (I've attached the non-gigi part
> we currently use, preparatory patches are required for gigi first).  All the
> subtypes are given maximal bounds for their precision, except for TYPE_DOMAIN
> of array types like in C, and thus become first class citizens.  This makes
> it possible to eliminate code in gigi, the gimplifier, the loop optimizer,
> the VRP pass, etc. needed to specifically support their special semantics.
>
> This in turn means that the gimplification will eliminate most of the casts
> between subtypes and base types, making the optimizers more effective.  The
> exception will be the VRP pass, most notably when checks are off in Ada, so
> we'll need to be able to drive VRP differently from gigi.
>
> Comments/suggestions welcome.
>
>
>        * fold-const.c (fold_truth_not_expr) <CONVERT_EXPR>: Do not strip
>        it if the destination type is boolean.
>        * tree-chrec.c (avoid_arithmetics_in_type_p): Delete.
>        (convert_affine_scev): Remove call to above function.
>        (chrec_convert_aggressive): Likewise.
>        * tree-scalar-evolution.c (follow_ssa_edge_expr) <PLUS_EXPR>:
>        Propagate the type of the first operand.
>        (follow_ssa_edge_in_rhs) <GIMPLE_BINARY_RHS>: Likewise
>        * tree-ssa.c (useless_type_conversion_p_1): Do not specifically return
>        false for conversions involving subtypes.
>        * tree-vrp.c (vrp_val_max): Do not get to the base type.
>        (vrp_val_min): Likewise.
>        (needs_overflow_infinity): Do not special-case subtypes.
>        (extract_range_from_unary_expr): Do not use the base types.

What is missing to go forward with this plan?  I am hitting type consistency
problems again while trying to fix PR39999 ... :/

Richard.

Re: [RFC] Get rid of awkward semantics for subtypes

[Eric Botcazou]

> What is missing to go forward with this plan?

Almost nothing, but I'm benchmarking the change and I'm seeing degradation in 
some cases because move IVs are exposed and so are -fivopts' warts.

> I am hitting type consistency problems again while trying to fix PR39999 ...

Ideally this should be independent.

-- 
Eric Botcazou

Re: [RFC] Get rid of awkward semantics for subtypes

[Richard Guenther]

On Wed, May 6, 2009 at 9:04 PM, Eric Botcazou <ebotcazou@adacore.com> wrote:
>> What is missing to go forward with this plan?
>
> Almost nothing, but I'm benchmarking the change and I'm seeing degradation in
> some cases because move IVs are exposed and so are -fivopts' warts.
>
>> I am hitting type consistency problems again while trying to fix PR39999 ...
>
> Ideally this should be independent.

Yes.  But we have invalid IL before PRE (arithmetic in subtypes) and PRE manages
to expose this fact in a way that type checking complains ... :/  I
have now tested
4 variants of the obvious fix and all fail one way or the other
because of this issue.
For 4.4 it's easier because type checking won't notice it there ;)

Richard.

Re: [RFC] Get rid of awkward semantics for subtypes

[Richard Guenther]

On Wed, May 6, 2009 at 9:17 PM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Wed, May 6, 2009 at 9:04 PM, Eric Botcazou <ebotcazou@adacore.com> wrote:
>>> What is missing to go forward with this plan?
>>
>> Almost nothing, but I'm benchmarking the change and I'm seeing degradation in
>> some cases because move IVs are exposed and so are -fivopts' warts.
>>
>>> I am hitting type consistency problems again while trying to fix PR39999 ...
>>
>> Ideally this should be independent.
>
> Yes.  But we have invalid IL before PRE (arithmetic in subtypes) and PRE manages
> to expose this fact in a way that type checking complains ... :/  I
> have now tested
> 4 variants of the obvious fix and all fail one way or the other
> because of this issue.
> For 4.4 it's easier because type checking won't notice it there ;)

I wonder for example about

 <integer_type 0x2b1d770a3300 integer
    type <integer_type 0x2b1d76cbe540 integer sizes-gimplified
asm_written public visited SI
        size <integer_cst 0x2b1d76cb0a20 constant 32>
        unit size <integer_cst 0x2b1d76cb0690 constant 4>
        align 32 symtab 1993070176 alias set -1 canonical type
0x2b1d76cbe540 precision 32 min <integer_cst 0x2b1d76cb0990
-2147483648> max <integer_cst 0x2b1d76cb09c0 2147483647>
        pointer_to_this <pointer_type 0x2b1d76ccc6c0>>
    sizes-gimplified asm_written public visited SI size <integer_cst
0x2b1d76cb0a20 32> unit size <integer_cst 0x2b1d76cb0690 4>
    align 32 symtab 2001622336 alias set 0 canonical type
0x2b1d770a3300 precision 32 min <integer_cst 0x2b1d76cb0990
-2147483648> max <integer_cst 0x2b1d76cb09c0 2147483647> RM size
<integer_cst 0x2b1d76cb0a20 32>
    chain <type_decl 0x2b1d770a33c0 integer>>

it seems the base type here is exactly the same as the subtype?

In the particular case IVOPTs is creating arithmetic in that type.  Or
maybe fold.

Richard.

Re: [RFC] Get rid of awkward semantics for subtypes

[Eric Botcazou]

> I wonder for example about
>
>  <integer_type 0x2b1d770a3300 integer
>     type <integer_type 0x2b1d76cbe540 integer sizes-gimplified
> asm_written public visited SI
>         size <integer_cst 0x2b1d76cb0a20 constant 32>
>         unit size <integer_cst 0x2b1d76cb0690 constant 4>
>         align 32 symtab 1993070176 alias set -1 canonical type
> 0x2b1d76cbe540 precision 32 min <integer_cst 0x2b1d76cb0990
> -2147483648> max <integer_cst 0x2b1d76cb09c0 2147483647>
>         pointer_to_this <pointer_type 0x2b1d76ccc6c0>>
>     sizes-gimplified asm_written public visited SI size <integer_cst
> 0x2b1d76cb0a20 32> unit size <integer_cst 0x2b1d76cb0690 4>
>     align 32 symtab 2001622336 alias set 0 canonical type
> 0x2b1d770a3300 precision 32 min <integer_cst 0x2b1d76cb0990
> -2147483648> max <integer_cst 0x2b1d76cb09c0 2147483647> RM size
> <integer_cst 0x2b1d76cb0a20 32>
>     chain <type_decl 0x2b1d770a33c0 integer>>
>
> it seems the base type here is exactly the same as the subtype?

Yes, don't be too surprised, gigi even creates extra subtypes (not present in 
the language) to work around its own quirks. :-)

> In the particular case IVOPTs is creating arithmetic in that type.  Or
> maybe fold.

Yes, IVOPTs does that.  I needed this patchlet

*************** generic_type_for (tree type)
*** 1978,1983 ****
--- 1978,1990 ----
    if (POINTER_TYPE_P (type))
      return ptr_type_node;
  
+   /* Return the appropriate type to do unsigned arithmetics.  */
+   if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type))
+     type = TREE_TYPE (type);
+ 
+   if (TREE_CODE (type) != INTEGER_TYPE)
+     return lang_hooks.types.type_for_size (TYPE_PRECISION (type), 1);
+ 
    if (TYPE_UNSIGNED (type))
      return type;

when I was experimenting with another approach to the subtype problem.
  
-- 
Eric Botcazou