slot combination and alias analysis

slot combination and alias analysis

[mike stump]

I'm I correct in assuming that the code:

void
combine_temp_slots ()
{
  struct temp_slot *p, *q;
  struct temp_slot *prev_p, *prev_q;
  int num_slots;

  /* We can't combine slots, because the information about which slot
     is in which alias set will be lost.  */
  if (flag_strict_aliasing)
    return;

is now more pessimistic than it needs to be?

It seems that with:

  /* See if the first alias set is a subset of the second.  */
  ase = get_alias_set_entry (set1);

of alias_sets_conflict_p (set1, set2), that it would be possible to
generate a new alias set, and have it inherit from the two parents
(using record_alias_subset) that are being combined.  Since we
inherit, the conflict catcher will notice, and have exactly the right
information later.  If it pessimizese code too much (due to the extra
conflicts), maybe we should only do this for -Os?  Personally I can't
imagine that it would hurt performance more than 0.1%.

What do you think?

Re: slot combination and alias analysis

[Richard Henderson]

On Fri, Oct 05, 2001 at 04:41:43PM -0700, mike stump wrote:
> It seems that with:
> 
>   /* See if the first alias set is a subset of the second.  */
>   ase = get_alias_set_entry (set1);
> 
> of alias_sets_conflict_p (set1, set2), that it would be possible to
> generate a new alias set, and have it inherit from the two parents
> (using record_alias_subset) that are being combined.

Yes, that is possible.  What isn't (or wasn't) is to track down all
of the MEMs we've generated that reference that stack slot to update
their alias sets.

Perhaps with Kenner's changes to use MEM_ATTRS a struct we no longer
need to actually track down the MEMs, we can just walk the structs
to find the slots.


r~

Re: slot combination and alias analysis

[Richard Kenner]

    You have two function bodies.  In one, it does { float f; ... }, in
    the other, it does { double d; ... }, they reference at least one byte
    in common through the magic of inlining.  The optimizer knows that
    they don't conflict, but the stack frame code just allocates a block
    (unknown), and then uses it.  Unfortunately, one of the uses can be
    known, say the first float.  In the second, instead of being just an
    unknown block, the memory is used as a known double.  Since a known
    float and a known double can never conflict, we know we can reorder
    the memory references.  But, we see that this would be wrong.  

Yes, but I don't see how it can happen.  The allocation of the two blocks
for the frames of the inlined functions cannot overlap, or at least I
don't think so.

Re: slot combination and alias analysis

[mike stump]

> Date: Sat, 6 Oct 01 07:09:08 EDT
> From: kenner@vlsi1.ultra.nyu.edu (Richard Kenner)
> To: mrs@windriver.com
> Cc: gcc@gcc.gnu.org

> But the code later in the function handles the case where one type is
> unknown and, I think, does it correctly.

Yes, this is what I thought at the start of yesterday too.  Then I
investigated the code.  I don't hold that opinion anymore.

You have two function bodies.  In one, it does { float f; ... }, in
the other, it does { double d; ... }, they reference at least one byte
in common through the magic of inlining.  The optimizer knows that
they don't conflict, but the stack frame code just allocates a block
(unknown), and then uses it.  Unfortunately, one of the uses can be
known, say the first float.  In the second, instead of being just an
unknown block, the memory is used as a known double.  Since a known
float and a known double can never conflict, we know we can reorder
the memory references.  But, we see that this would be wrong.  I
already said that the memory blocks allocated overlap.  Hence, we must
go out of our way, to ensure they never conflict:

!   /* The alias set for the slot.  If the alias set is zero, we don't
!      know anything about the alias set of the slot.  We must only
!      reuse a slot if it is assigned an object of the same alias set.
!      Otherwise, the rest of the compiler may assume that the new use
!      of the slot cannot alias the old use of the slot, which is
!      false.  If the slot has alias set zero, then we can't reuse the
!      slot at all, since we have no idea what alias set may have been
!      imposed on the memory.  For example, if the stack slot is the
!      call frame for an inline functioned, we have no idea what alias
!      sets will be assigned to various pieces of the call frame.  */

From the original wording, before your change.  I think I now
understand what Mark meant.  His use of the term alias set 0 is
unfortunate.  -1 would be closer, or maybe -2.  0 already had a
meaning, and it means that you will never have to worry about this
memory and other memory conflicting.  But, in our case, it is a we
can't know, and further, someone else may have assigned any alias set
for the memory and used it in that fashion.  This goes well beyond an
alias set 0 use.

This is in part why I asked about the subset/superset stuff.  That
would be fairly coarse, but would be better than no reuse.  Better,
would be an aggregate scheme.  I think the semantics we may want
exactly match the new code that you put in.

Mark, is my understanding of why you had that code correct?  Do you
see any reason why we could do what kenner did?  I don't think we can,
as a local use of a float can overlap the use of a float in an inline
function body, and one of them would be known, and the other unknown,
and the current code would reuse the slot.

Re: slot combination and alias analysis

[Richard Kenner]

    I think I can spot a bug (in one of your changes):

    int
    objects_must_conflict_p (t1, t2)
     tree t1, t2;
    {
      /* If neither has a type specified, we don't know if they'll conflict
         because we may be using them to store objects of various types, for
         example the argument and local variables areas of inlined functions.  */
      if (t1 == 0 && t2 == 0)
        return 0;

    The previous version did the equivalent of:

      if (t1 == 0 || t2 == 0)
        return 0;

Right. That was a change I meant to make.

    The reasoning is that an unknown type (the abuse of alias set zero in
    the old code), can be remapped to any alias set beyond our ability to
    know about it (say, by function inlining), and that the slots won't
    necessarily conflict.

But the code later in the function handles the case where one type is
unknown and, I think, does it correctly.

Re: slot combination and alias analysis

[mike stump]

> Date: Fri, 5 Oct 01 21:20:42 EDT
> From: kenner@vlsi1.ultra.nyu.edu (Richard Kenner)
> To: rth@redhat.com
> Cc: gcc@gcc.gnu.org

> The whole issue of reusing temp slots is much trickier than it seems
> and I'm still not sure we have it right.

I think I can spot a bug (in one of your changes):

int
objects_must_conflict_p (t1, t2)
     tree t1, t2;
{
  /* If neither has a type specified, we don't know if they'll conflict
     because we may be using them to store objects of various types, for
     example the argument and local variables areas of inlined functions.  */
  if (t1 == 0 && t2 == 0)
    return 0;

The previous version did the equivalent of:

int
objects_must_conflict_p (t1, t2)
     tree t1, t2;
{
  /* If neither has a type specified, we don't know if they'll conflict
     because we may be using them to store objects of various types, for
     example the argument and local variables areas of inlined functions.  */
  if (t1 == 0 || t2 == 0)
    return 0;

I think.  It was previously:

        || (alias_set && p->alias_set == alias_set))

which meant if either was zero, it would be false.  The reasoning is
that an unknown type (the abuse of alias set zero in the old code),
can be remapped to any alias set beyond our ability to know about it
(say, by function inlining), and that the slots won't necessarily
conflict.

Re: slot combination and alias analysis

[Richard Kenner]

    Perhaps with Kenner's changes to use MEM_ATTRS a struct we no longer
    need to actually track down the MEMs, we can just walk the structs
    to find the slots.

I wasn't planing on creating a linkage between the MEM_ATTRS structure and
the temp slot structure.  One could be created, but I think that would be
the only usage of it.

The whole issue of reusing temp slots is much trickier than it seems and
I'm still not sure we have it right.