Re: fold_convert question

Re: fold_convert question

[Richard Kenner]

    What I don't understand is why have two different ARRAY types in the
    first place?

Two different subtypes, for example.

    This seems very inefficient.  As a new GCC developer I would like to
    see that types be correctly done in the front-end and middle-end.
    Saying two types are compatible but having a VIEW_CONVERT is just
    wrong.

No, it's not.  In the GENERIC tree, we require that the tree be precisely
type-correct.  The VIEW_CONVERT_EXPR serves that purpose.  For GIMPLE,
we weaken the type-correctness to compatible types.  At that point, the
VIEW_CONVERT_EXPR isn't needed and is removed.

Re: fold_convert question

[Richard Kenner]

    Solving the tree combination problem in a general way that allows
    us to remove the useless type conversion, forward propagation,
    expression reassociation and related problems should be high on
    our todo list once we change focus from 4.0 to 4.1.

I agree. But the tree combiner should also be able to compute the sorts of
data that the RTL combiner produces (which bits are known zero and how
many copies of the sign bit we know we have).  How to do this was discussed
at the last summit.

Re: fold_convert question

[Eric Botcazou]

>     It seems to me we'd be best off turning:
>
>       ADDR_EXPR <pointer_type <record_type>>
>         VIEW_CONVERT_EXPR <record_type>
>           NOP_EXPR <integer_type1>
>             ARRAY_REF <integer_type2>
>
>     Into
>
>     NOP_EXPR <integer_type1>
>       ADDR_EXPR <pointer_type <integer_type2>>
>         ARRAY_REF <integer_type2>
>
> I assume you mean the NOP_EXPR's type to be a pointer to integer_type1.
> I thought we had code in gimplify.c to do that once, actually.  It
> shouldn't be hard and I agree that it makes the most sense.

OK, thanks to both of you for the tip.  I'll try in the next few days and see 
how that fares.

-- 
Eric Botcazou

Re: fold_convert question

[Jeffrey A Law]

On Fri, 2004-10-15 at 19:27, Roger Sayle wrote:

> <rant apologies="in advance">
> tree_ssa_useless_type_conversion is an unfortunate hack to work around
> the fact that tree-ssa doesn't yet have a combiner pass.
You can certainly look at it that way.  I wouldn't lose a lot of
sleep if we found a way to make the useless type conversion stuff
go away, either by having a combiner pass, defining a type system
that doesn't get in the way of the optimizers, or some yet unknown
optimization techniques.

The primary purpose in identifying useless type conversions is to
identify that two SSA_NAMEs have equivalent values and types which
are "close enough" that we can use them interchangably.   ie, 
constant/copy propagation. 

When I look at the base SSA optimizers we have in place the most
glaring omission is clearly a tree combiner.  In fact, we have
multiple special purpose tree combiners in-place and even more
submitted and yet more lying around as proof of concept code, but
no general solution for tree combination.

Solving the tree combination problem in a general way that allows
us to remove the useless type conversion, forward propagation,
expression reassociation and related problems should be high on
our todo list once we change focus from 4.0 to 4.1.

jeff

Re: fold_convert question

[Richard Kenner]

    It seems to me we'd be best off turning:

      ADDR_EXPR <pointer_type <record_type>>
        VIEW_CONVERT_EXPR <record_type>
          NOP_EXPR <integer_type1>
            ARRAY_REF <integer_type2>

    Into

    NOP_EXPR <integer_type1>
      ADDR_EXPR <pointer_type <integer_type2>>
        ARRAY_REF <integer_type2>

I assume you mean the NOP_EXPR's type to be a pointer to integer_type1.
I thought we had code in gimplify.c to do that once, actually.  It
shouldn't be hard and I agree that it makes the most sense.

Re: fold_convert question

[Jeffrey A Law]

On Sat, 2004-10-16 at 06:33, Eric Botcazou wrote:
> > If there's anything I can do to help you investigate/fix c61008a
> > that avoids further degenerating the middle-end's type system, I'd
> > be happy to help.  Ultimately, this might be a loosing crusade,
> > but I couldn't forgive myself if I didn't try.  Worst case scenario
> > of tweaking useless_type_conversions is that we miss some optimizations
> > (until we get a tree-ssa combiner), but of perverting fold_convert
> > is that we regress many difficult to diagnose code generation bugs.
> 
> I ran into another problem with tree_ssa_useless_type_conversion, which 
> prevents the Ada RTS from building on SPARC and PPC (PR middle-end/17793).
> 
> The front-end generates
> 
>   ADDR_EXPR <pointer_type <record_type>>
>     VIEW_CONVERT_EXPR <record_type>
>       NOP_EXPR <integer_type1>
>         ARRAY_REF <integer_type2>
> 
> with integer_type1 and integer_type2 not compatible.
> 
> The gimplifier (gimplify_addr_expr) turns this into
> 
>   ADDR_EXPR <pointer_type <integer_type1>>
>     NOP_EXPR <integer_type1>
>       ARRAY_REF <integer_type2>
> 
> and then STRIP_USELESS_TYPE_CONVERSION removes the NOP because of
> 
>   /* If both the inner and outer types are integral types, then the
>      conversion is not necessary if they have the same mode and
>      signedness and precision, and both or neither are boolean.  Some
>      code assumes an invariant that boolean types stay boolean and do
>      not become 1-bit bit-field types.  Note that types with precision
>      not using all bits of the mode (such as bit-field types in C)
>      mean that testing of precision is necessary.  */
>   else if (INTEGRAL_TYPE_P (inner_type)
>            && INTEGRAL_TYPE_P (outer_type)
> 	   && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
> 	   && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
> 	   && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
>     {
>       bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
>       bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
>       if (first_boolean == second_boolean)
> 	return true;
>     }
> 
> so we end up with
> 
>   ADDR_EXPR <pointer_type <integer_type1>>
>     ARRAY_REF <integer_type2>
> 
> which causes the gimplifier to later ICE in check_pointer_types_r because 
> cpt_same_type returns false for (integer_type1, integer_type2).
> 
> 
> On the one hand, it seems to me that this is a consistency problem within the 
> gimplifier and that cpt_same_type should accept the pairs of types deemed 
> equivalent by tree_ssa_useless_type_conversion.  On the other hand, 
> check_pointer_types_r seems to be very strict on purpose so perhaps the NOP 
> should not have been stripped in the first place.
> 
> What do (both of) you think about that?  Thanks in advance.
It seems to me we'd be best off turning:

  ADDR_EXPR <pointer_type <record_type>>
    VIEW_CONVERT_EXPR <record_type>
      NOP_EXPR <integer_type1>
        ARRAY_REF <integer_type2>

Into

NOP_EXPR <integer_type1>
  ADDR_EXPR <pointer_type <integer_type2>>
    ARRAY_REF <integer_type2>

I don't know how difficult that would be though.

Jeff

Re: fold_convert question

[Eric Botcazou]

> If there's anything I can do to help you investigate/fix c61008a
> that avoids further degenerating the middle-end's type system, I'd
> be happy to help.  Ultimately, this might be a loosing crusade,
> but I couldn't forgive myself if I didn't try.  Worst case scenario
> of tweaking useless_type_conversions is that we miss some optimizations
> (until we get a tree-ssa combiner), but of perverting fold_convert
> is that we regress many difficult to diagnose code generation bugs.

I ran into another problem with tree_ssa_useless_type_conversion, which 
prevents the Ada RTS from building on SPARC and PPC (PR middle-end/17793).

The front-end generates

  ADDR_EXPR <pointer_type <record_type>>
    VIEW_CONVERT_EXPR <record_type>
      NOP_EXPR <integer_type1>
        ARRAY_REF <integer_type2>

with integer_type1 and integer_type2 not compatible.

The gimplifier (gimplify_addr_expr) turns this into

  ADDR_EXPR <pointer_type <integer_type1>>
    NOP_EXPR <integer_type1>
      ARRAY_REF <integer_type2>

and then STRIP_USELESS_TYPE_CONVERSION removes the NOP because of

  /* If both the inner and outer types are integral types, then the
     conversion is not necessary if they have the same mode and
     signedness and precision, and both or neither are boolean.  Some
     code assumes an invariant that boolean types stay boolean and do
     not become 1-bit bit-field types.  Note that types with precision
     not using all bits of the mode (such as bit-field types in C)
     mean that testing of precision is necessary.  */
  else if (INTEGRAL_TYPE_P (inner_type)
           && INTEGRAL_TYPE_P (outer_type)
	   && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
	   && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
	   && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
    {
      bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
      bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
      if (first_boolean == second_boolean)
	return true;
    }

so we end up with

  ADDR_EXPR <pointer_type <integer_type1>>
    ARRAY_REF <integer_type2>

which causes the gimplifier to later ICE in check_pointer_types_r because 
cpt_same_type returns false for (integer_type1, integer_type2).


On the one hand, it seems to me that this is a consistency problem within the 
gimplifier and that cpt_same_type should accept the pairs of types deemed 
equivalent by tree_ssa_useless_type_conversion.  On the other hand, 
check_pointer_types_r seems to be very strict on purpose so perhaps the NOP 
should not have been stripped in the first place.

What do (both of) you think about that?  Thanks in advance.

-- 
Eric Botcazou

Re: fold_convert question

[Andrew Pinski]

On Oct 15, 2004, at 11:14 PM, Richard Kenner wrote:

>     But "fold" itself calls "fold_convert" to ensure/force a tree to a
>     specified type.  i.e. fold_convert is called for both generic, 
> gimple
>     and potentially even by front-ends that don't use tree-ssa.
>
> Hmm ...


What I don't understand is why have two different ARRAY types in the
first place?

This seems very inefficient.  As a new GCC developer I would like to
see that types be correctly done in the front-end and middle-end.
Saying two types are compatible but having a VIEW_CONVERT is just
wrong.

Thanks,
Andrew Pinski

Re: fold_convert question

[Richard Kenner]

    But "fold" itself calls "fold_convert" to ensure/force a tree to a
    specified type.  i.e. fold_convert is called for both generic, gimple
    and potentially even by front-ends that don't use tree-ssa.

Hmm ...

    I agree completely that the problem is one of consistency, but I would
    argue that the bug is in (this use of) STRIP_USELESS_TYPE_CONVERSIONS.
    It's not that fold_convert is broken, but that the VIEW_CONVERT_EXPR
    shouldn't have been stripped off in the first place.   I probably wouldn't
    consider the conversion of an ARRAY_TYPE to a scalar to be useless?

It's not a conversion between arrays and scalars, but between two
ARRAY_TYPEs.  Otherwise, they wouldn't have been compartible!
(Ada says that two ARRAY_TYPEs are compatible if the component types
are compatible and the bounds are the same.)

    Indeed the fact that VIEW_CONVERT_EXPR is only used by Ada probably
    helps explain why S_U_T_C is overly aggressive in removing it.  For
    the majority of front-ends (and Ada uses) fold_convert does the right
    thing.

I added the removal of the VIEW_CONVERT_EXPR to S_U_T_C and I still believe
it should be there.

    tree_ssa_useless_type_conversion is an unfortunate hack to work around
    the fact that tree-ssa doesn't yet have a combiner pass.  Without a
    combiner, the optimization passes can only see one statement and its
    operands at a time, so the "necessary" type conversions required to
    keep operands consistent often create a "horizon affect" where
    optimization opportunities are missed due to the local nature of SSA
    form.

Perhaps, but I don't see it that way.  It's always better to keep code at any
level of representation as simple as possible.  If we have conversions that
we know aren't going to generate any code, the earlier we remove them the
better.

    If there's anything I can do to help you investigate/fix c61008a
    that avoids further degenerating the middle-end's type system, I'd
    be happy to help.  Ultimately, this might be a loosing crusade,
    but I couldn't forgive myself if I didn't try.  Worst case scenario
    of tweaking useless_type_conversions is that we miss some optimizations
    (until we get a tree-ssa combiner), but of perverting fold_convert
    is that we regress many difficult to diagnose code generation bugs.

The investigation of that failure is, to a large extent, secondary.

We have the larger problem of being careful to define what "type correctness"
means at tree level.  I previously thought it was uniformly agreed that it
means "strictly correct" in GENERIC and "compatible" (as defined by the lang
hook) in GIMPLE.  So the first question we need to answer is if that's
correct or not.

If it is, then we need to understand which of the tests fold_convert ought to
use based on when it's called.  It may well be that the bug here is in the
caller, which shouldn't be calling it if the types are already compatible.

Re: fold_convert question

[Roger Sayle]

On Fri, 15 Oct 2004, Richard Kenner wrote:
>     No, fold_convert is required to be strongly type safe by the GCC
>     middle-end.
>
> I'm confused.  I thought the rules are that GIMPLE is *not* strongly
> type safe.  We remove all conversions between compatible types.
> So the definition for GIMPLE is compatible types, not identical types.
>
>     [Likewise calling fold on a tree of type T, must always return
>     a tree of type T]
>
> Right, because "fold" is called on GENERIC, but fold_convert only on
> GIMPLE and the typing rules are different.

But "fold" itself calls "fold_convert" to ensure/force a tree to a
specified type.  i.e. fold_convert is called for both generic, gimple
and potentially even by front-ends that don't use tree-ssa.


>     Besides, the phrase "types are compatible" is purely a front-end
>     concept, that doesn't exist in the middle-end.
>
> Sure it does!  See STRIP_USELESS_TYPE_CONVERSION.
>
> The issue is the call from setup_one_parameter.  It wants to make sure
> that the argument is converted to the type of the parameter.  In the
> original GENERIC tree of the CALL_EXPR in this case, it was converted to
> that type with a VIEW_CONVERT_EXPR.  But that was stripped off because
> the types were compatible.  Then when the call was inlined, we tried to
> convert it back, but couldn't at middle-end level because it was an
> ARRAY_TYPE.
>
>     As an Ada person, I'm sure you appreciate not having fold_convert
>     impose any notion of "type compatability" on gigi's trees, other
>     than the semantics implied by the original trees themselves.
>
> Exactly the other way around: I expect the middle-end to consistently
> use the language hook that says what's compatible and what isn't.  If it's
> not going to do that, then it shouldn't trip "useless" type conversions!

I agree completely that the problem is one of consistency, but I would
argue that the bug is in (this use of) STRIP_USELESS_TYPE_CONVERSIONS.
It's not that fold_convert is broken, but that the VIEW_CONVERT_EXPR
shouldn't have been stripped off in the first place.   I probably wouldn't
consider the conversion of an ARRAY_TYPE to a scalar to be useless?
Indeed the fact that VIEW_CONVERT_EXPR is only used by Ada probably
helps explain why S_U_T_C is overly aggressive in removing it.  For
the majority of front-ends (and Ada uses) fold_convert does the right
thing.



<rant apologies="in advance">
tree_ssa_useless_type_conversion is an unfortunate hack to work around
the fact that tree-ssa doesn't yet have a combiner pass.  Without a
combiner, the optimization passes can only see one statement and its
operands at a time, so the "necessary" type conversions required to
keep operands consistent often create a "horizon affect" where
optimization opportunities are missed due to the local nature of SSA form.
Rather than improve/fix the optimizers, it was decided more expedient
to instead corrupt the compiler's type system.  Amongst the curious
side-effects of using front-end type checking in the middle-end's
intermediate representation is that the set of transformations applied
to the same tree/function, differ depending upon which front-end is in
use.  i.e. a loop may vectorize in C++ or gfortran but not in C and
Java.  This situation, where the semantics of the type system is not
explicit in the intermediate language, will only make things difficult
once GCC pushes to "whirl"-like persistent intermediate representations.
Indeed we're already unable to perform interprocedural optimizations
between languages, even though we use the same gimple representations
for all front-ends.  <humour>Perhaps we should use/inline RTL?</humour>

I'm already disappointed that a use of lang_hooks has crept into
fold_convert.  It was orginally approved as a short-term fix (a.k.a.
hack), but when time came to remove it, people complained that it was
required for IMA!  Worse there have even been comments on the lists
about avoiding calls to fold_convert dues to the performance penalty
of this undesirable lang_hooks.types_compatible_p call!!
</rant>


If there's anything I can do to help you investigate/fix c61008a
that avoids further degenerating the middle-end's type system, I'd
be happy to help.  Ultimately, this might be a loosing crusade,
but I couldn't forgive myself if I didn't try.  Worst case scenario
of tweaking useless_type_conversions is that we miss some optimizations
(until we get a tree-ssa combiner), but of perverting fold_convert
is that we regress many difficult to diagnose code generation bugs.

Roger
--

Re: fold_convert question

[Richard Kenner]

    No, fold_convert is required to be strongly type safe by the GCC
    middle-end.

I'm confused.  I thought the rules are that GIMPLE is *not* strongly
type safe.  We remove all conversions between compatible types.
So the definition for GIMPLE is compatible types, not identical types.

Subsequent to sending my last email I discovered that this relevant to
the ACATS failure in c61008a, though fixing this isn't enough, since
something else is broken (I don't know what yet, but I suspect its the
type replacement for inlining).

The issue is the call from setup_one_parameter.  It wants to make sure
that the argument is converted to the type of the parameter.  In the
original GENERIC tree of the CALL_EXPR in this case, it was converted to
that type with a VIEW_CONVERT_EXPR.  But that was stripped off because
the types were compatible.  Then when the call was inlined, we tried to
convert it back, but couldn't at middle-end level because it was an
ARRAY_TYPE.

      If a function calls fold_convert (T, X), then the tree
        type of the returned expression will/must always be T.

    i.e.  TREE_TYPE (fold_convert (T, X)) == T

I don't see why.  Isn't it enough that they be compatible (in the
meaning of the lang hook)?

    [Likewise calling fold on a tree of type T, must always return
    a tree of type T]

Right, because "fold" is called on GENERIC, but fold_convert only on
GIMPLE and the typing rules are different.

    Besides, the phrase "types are compatible" is purely a front-end
    concept, that doesn't exist in the middle-end.  

Sure it does!  See STRIP_USELESS_TYPE_CONVERSION.

    As an Ada person, I'm sure you appreciate not having fold_convert
    impose any notion of "type compatability" on gigi's trees, other
    than the semantics implied by the original trees themselves.

Exactly the other way around: I expect the middle-end to consistently
use the language hook that says what's compatible and what isn't.  If it's
not going to do that, then it shouldn't trip "useless" type conversions!

Re: fold_convert question

[Roger Sayle]

Doh!  I sent my response to the wrong list...


On Fri, 15 Oct 2004, Richard Kenner wrote:
> Right now, it does nothing only if the original and resulting type
> are the same. That seems wrong to me.  Shouldn't it also do nothing
> if the types are compatible?

No, fold_convert is required to be strongly type safe by the GCC
middle-end.  If a function calls fold_convert (T, X), then the tree
type of the returned expression will/must always be T.

i.e.  TREE_TYPE (fold_convert (T, X)) == T

Without these semantics the only way to force a tree to type T,
would be to construct either a NOP_EXPR or a CONVERT_EXPR.  And
then once you think about optimization, for example if X is already
of type T, you'll understand precisely what fold_convert does,
i.e. the equivalent of "fold (build1 (NOP_EXPR, T, X))".

[Likewise calling fold on a tree of type T, must always return
a tree of type T]


Besides, the phrase "types are compatible" is purely a front-end
concept, that doesn't exist in the middle-end.  If a front-end
requires type conversion with some notion of "type compatability"
it should call "convert".  Once gimplified, however, the compiler's
middle-end and tree-ssa passes should only be using fold_convert.


As an Ada person, I'm sure you appreciate not having fold_convert
impose any notion of "type compatability" on gigi's trees, other
than the semantics implied by the original trees themselves.

Roger
--

fold_convert question

[Richard Kenner]

Right now, it does nothing only if the original and resulting type
are the same. That seems wrong to me.  Shouldn't it also do nothing if
the types are compatible?

I don't have any specific bug here, but I did notice this when looking
for another bug (that wasn't caused by this).