alias sets & const objects

alias sets & const objects

[Jeffrey A Law]

According to nullstone we do a terrible job at handling aliasing for 
constant objects.

Consider this code (from Nullstone's web page):

const int const_array[];

                      void f (int *p, int i)
                      {
                        int x, y;
                        const int *q = &const_array[i];
                        x = *q;
                        *p = 5;
                        y = *q;
                        g (x, y);
                      }

In this particular case we now that Q points to a constant object.  Therefore,
the store into *P can not modify anything pointed to by Q.  Which in turn
makes one of the loads from Q redundant.

Note that this is only possible when we know what Q points to; a pointer to
a const is also allowed to point to a non-const object.

/* In a VAR_DECL, PARM_DECL or FIELD_DECL, or any kind of ..._REF node,
   nonzero means it may not be the lhs of an assignment.
   In a ..._TYPE node, means this type is const-qualified
   (but the macro TYPE_READONLY should be used instead of this macro
   when the node is a type).  */
#define TREE_READONLY(NODE) ((NODE)->common.readonly_flag)

Seems like we can check TREE_ONLY for the listed _DECLs and _REF nodes and
put them into a different alias set.

It was easy to get a proof of concept running in c_get_alias_set:

  /* In a VAR_DECL, PARM_DECL or FIELD_DECL, or any kind of ..._REF node,
     TREE_READONLY nonzero means it may not be the lhs of an assignment.

     Thus, we can use a different alias set to distinguish (for example)
     between a reference to a member of a constant array and a store
     through a pointer which points to the same base type as members
     in the array.

     This is unsafe for a _TYPE node since it merely means the type
     is const qualified and ANSI C allows a pointer to a const to
     point to both constant and nonconstant memory locations.  */
  if (TREE_READONLY (t)
      && (TREE_CODE (t) == VAR_DECL
          || TREE_CODE (t) == PARM_DECL
          || TREE_CODE (t) == FIELD_DECL
          || TREE_CODE_CLASS (TREE_CODE (t)) == 'r'))
    {
      return -2;
    }

Again, proof of concept.  -2 is a hack :-)


That worked find and dandy.  However, it is not complete.  Consider an auto
const variable with an initializer:

                      void f (int *p, int i)
                      {
                        const int const_array[] = {0};
                        int x, y;
                        const int *q = &const_array[i];
                        x = *q;
                        *p = 5;
                        y = *q;
                        g (x, y);
                      }


We have to emit an initializer for "const_array" which will involve a store
to memory.  We must be sure that we do not load from that memory location
before the initializing insn.

So long as we don't "lose" the alias set for the store and the loads from *q,
then the right thing will happen (the *_dependence routines know about this
special case).

Well, we lose the alias set for the store. :(

This particular example will generate a (mem (addressof (reg) -2), which is
good.  The load also has alias set -2.

However, when we go to remove the addressof expression the alias set gets
recomputed.  When we retroactively put regs into the stack, the alias set is
computed based solely on the type and we lose the readonly property.

And now that we have different alias sets for the store and the load nothing
will prevent the load from moving to a point before the store and we can lose.

I'm a little unsure how to proceed.  We could try to get more information down
into put_reg_into_stack, or we could try to copy the alias set after we purge
the addressof.

I also wonder if our handling of ARRAY_TYPE is a little pessimistic.  If the
ARRAY_TYPE is marked with TREE_READONLY, aside from the initializer, can
anything else ever write into the array?

I suspect this isn't terribly important.  Then again, we're seeing more and
more const uses, so maybe it is worth some effort to try and handle this case
better.

jeff

Re: alias sets & const objects

[Mark Mitchell]

>>>>> "Jeffrey" == Jeffrey A Law <law@hurl.cygnus.com> writes:

    Jeffrey> According to nullstone we do a terrible job at handling
    Jeffrey> aliasing for constant objects.

I've had patches to do this for a couple of months, and do it right.
They're not big, but I'm not quite done with them.  I'll dust them up
and submit them in the next week or two.

-- 
Mark Mitchell 			mark@markmitchell.com
Mark Mitchell Consulting	http://www.markmitchell.com

Re: alias sets & const objects

[Jeffrey A Law]

  In message < 199901241745.JAA04219@linux1.markmitchell.com >you write:
  > >>>>> "Jeffrey" == Jeffrey A Law <law@hurl.cygnus.com> writes:
  > 
  >     Jeffrey> According to nullstone we do a terrible job at handling
  >     Jeffrey> aliasing for constant objects.
  > 
  > I've had patches to do this for a couple of months, and do it right.
  > They're not big, but I'm not quite done with them.  I'll dust them up
  > and submit them in the next week or two.
Very cool.  Presumably they also handle the problem I pointed out with
"losing" the alias set when we have to throw a reg onto the stack?

jeff

Re: alias sets & const objects

[Jeffrey A Law]

  In message < 199901241745.JAA04219@linux1.markmitchell.com >you write:
  > >>>>> "Jeffrey" == Jeffrey A Law <law@hurl.cygnus.com> writes:
  > 
  >     Jeffrey> According to nullstone we do a terrible job at handling
  >     Jeffrey> aliasing for constant objects.
  > 
  > I've had patches to do this for a couple of months, and do it right.
  > They're not big, but I'm not quite done with them.  I'll dust them up
  > and submit them in the next week or two.
Very cool.  Presumably they also handle the problem I pointed out with
"losing" the alias set when we have to throw a reg onto the stack?

jeff

alias sets & const objects

[Jeffrey A Law]

According to nullstone we do a terrible job at handling aliasing for 
constant objects.

Consider this code (from Nullstone's web page):

const int const_array[];

                      void f (int *p, int i)
                      {
                        int x, y;
                        const int *q = &const_array[i];
                        x = *q;
                        *p = 5;
                        y = *q;
                        g (x, y);
                      }

In this particular case we now that Q points to a constant object.  Therefore,
the store into *P can not modify anything pointed to by Q.  Which in turn
makes one of the loads from Q redundant.

Note that this is only possible when we know what Q points to; a pointer to
a const is also allowed to point to a non-const object.

/* In a VAR_DECL, PARM_DECL or FIELD_DECL, or any kind of ..._REF node,
   nonzero means it may not be the lhs of an assignment.
   In a ..._TYPE node, means this type is const-qualified
   (but the macro TYPE_READONLY should be used instead of this macro
   when the node is a type).  */
#define TREE_READONLY(NODE) ((NODE)->common.readonly_flag)

Seems like we can check TREE_ONLY for the listed _DECLs and _REF nodes and
put them into a different alias set.

It was easy to get a proof of concept running in c_get_alias_set:

  /* In a VAR_DECL, PARM_DECL or FIELD_DECL, or any kind of ..._REF node,
     TREE_READONLY nonzero means it may not be the lhs of an assignment.

     Thus, we can use a different alias set to distinguish (for example)
     between a reference to a member of a constant array and a store
     through a pointer which points to the same base type as members
     in the array.

     This is unsafe for a _TYPE node since it merely means the type
     is const qualified and ANSI C allows a pointer to a const to
     point to both constant and nonconstant memory locations.  */
  if (TREE_READONLY (t)
      && (TREE_CODE (t) == VAR_DECL
          || TREE_CODE (t) == PARM_DECL
          || TREE_CODE (t) == FIELD_DECL
          || TREE_CODE_CLASS (TREE_CODE (t)) == 'r'))
    {
      return -2;
    }

Again, proof of concept.  -2 is a hack :-)


That worked find and dandy.  However, it is not complete.  Consider an auto
const variable with an initializer:

                      void f (int *p, int i)
                      {
                        const int const_array[] = {0};
                        int x, y;
                        const int *q = &const_array[i];
                        x = *q;
                        *p = 5;
                        y = *q;
                        g (x, y);
                      }


We have to emit an initializer for "const_array" which will involve a store
to memory.  We must be sure that we do not load from that memory location
before the initializing insn.

So long as we don't "lose" the alias set for the store and the loads from *q,
then the right thing will happen (the *_dependence routines know about this
special case).

Well, we lose the alias set for the store. :(

This particular example will generate a (mem (addressof (reg) -2), which is
good.  The load also has alias set -2.

However, when we go to remove the addressof expression the alias set gets
recomputed.  When we retroactively put regs into the stack, the alias set is
computed based solely on the type and we lose the readonly property.

And now that we have different alias sets for the store and the load nothing
will prevent the load from moving to a point before the store and we can lose.

I'm a little unsure how to proceed.  We could try to get more information down
into put_reg_into_stack, or we could try to copy the alias set after we purge
the addressof.

I also wonder if our handling of ARRAY_TYPE is a little pessimistic.  If the
ARRAY_TYPE is marked with TREE_READONLY, aside from the initializer, can
anything else ever write into the array?

I suspect this isn't terribly important.  Then again, we're seeing more and
more const uses, so maybe it is worth some effort to try and handle this case
better.

jeff

Re: alias sets & const objects

[Mark Mitchell]

>>>>> "Jeffrey" == Jeffrey A Law <law@hurl.cygnus.com> writes:

    Jeffrey> According to nullstone we do a terrible job at handling
    Jeffrey> aliasing for constant objects.

I've had patches to do this for a couple of months, and do it right.
They're not big, but I'm not quite done with them.  I'll dust them up
and submit them in the next week or two.

-- 
Mark Mitchell 			mark@markmitchell.com
Mark Mitchell Consulting	http://www.markmitchell.com