Re: TREE_UNCHANGING?

[Jason Merrill <jason at redhat dot com>]

>>>>> "Jason" == Jason Merrill <jason@redhat.com> writes:

>> Perhaps what I want is, rather, to tell the optimizer that the value will
>> not change behind its back; that the assignments we can see are all there
>> is.  That it can change, but cannot alias.

> It seems that restrict provides this sort of guarantee; in this testcase,
> can the compiler avoid doing two loads from *p?

>   int i;
>   void f ();
>   void g (int *__restrict p)
>   {
>     int j = *p;
>     f ();
>     j += *p;
>     i = j;
>   }

Here's a preliminary patch to implement those semantics, and to give all
vtable pointers a unique, restricted alias set.  Comments?

2002-05-10  Jason Merrill  <jason@redhat.com>

	* alias.c (alias_set_entry): Add restricted field.
	(alias_sets_conflict_p): Check it.
	(get_alias_set_entry_create): New function.
	(record_alias_subset): Factored out from here.
	(new_restricted_alias_set): New fn.
	(get_alias_set): Use it.
	* expr.h: Declare it.
	* cse.c (invalidate_memory): Hand off to invalidate.
	* cp/cp-lang.c (cxx_get_alias_set): Give vtbl_ptr_type_node a
	restricted alias set.

*** alias.c.~1~	Mon Apr 22 22:14:27 2002
--- alias.c	Fri May 10 16:58:49 2002
*************** Software Foundation, 59 Temple Place - S
*** 63,70 ****
     past immediate descendents, however, since we propagate all
     grandchildren up one level.
  
!    Alias set zero is implicitly a superset of all other alias sets.
!    However, this is no actual entry for alias set zero.  It is an
     error to attempt to explicitly construct a subset of zero.  */
  
  typedef struct alias_set_entry
--- 63,70 ----
     past immediate descendents, however, since we propagate all
     grandchildren up one level.
  
!    Alias set zero is implicitly a superset of all non-restricted alias
!    sets.  However, this is no actual entry for alias set zero.  It is an
     error to attempt to explicitly construct a subset of zero.  */
  
  typedef struct alias_set_entry
*************** typedef struct alias_set_entry
*** 81,86 ****
--- 81,91 ----
       `int', `double', `float', and `struct S'.  */
    splay_tree children;
  
+   /* Nonzero if the alias set corresponds to the referent of a restricted
+      pointer or the equivalent, which means that it does not conflict with
+      alias set zero.  */
+   int restricted;
+ 
    /* Nonzero if would have a child of zero: this effectively makes this
       alias set the same as alias set zero.  */
    int has_zero_child;
*************** static int mems_in_disjoint_alias_sets_p
*** 100,105 ****
--- 105,111 ----
  static int insert_subset_children       PARAMS ((splay_tree_node, void*));
  static tree find_base_decl		PARAMS ((tree));
  static alias_set_entry get_alias_set_entry PARAMS ((HOST_WIDE_INT));
+ static alias_set_entry get_alias_set_entry_create PARAMS ((HOST_WIDE_INT));
  static rtx fixed_scalar_and_varying_struct_p PARAMS ((rtx, rtx, rtx, rtx,
  						      int (*) (rtx, int)));
  static int aliases_everything_p         PARAMS ((rtx));
*************** get_alias_set_entry (alias_set)
*** 212,217 ****
--- 218,245 ----
    return sn != 0 ? ((alias_set_entry) sn->value) : 0;
  }
  
+ /* Like get_alias_set_entry, but inserts a new entry if there isn't one
+    already.  */
+ 
+ static alias_set_entry
+ get_alias_set_entry_create (alias_set)
+      HOST_WIDE_INT alias_set;
+ {
+   alias_set_entry ase = get_alias_set_entry (alias_set);
+   if (ase == 0) 
+     {
+       ase
+ 	= (alias_set_entry) xmalloc (sizeof (struct alias_set_entry));
+       ase->alias_set = alias_set;
+       ase->children 
+ 	= splay_tree_new (splay_tree_compare_ints, 0, 0);
+       ase->has_zero_child = 0;
+       splay_tree_insert (alias_sets, (splay_tree_key) alias_set,
+ 			 (splay_tree_value) ase);
+     }
+   return ase;
+ }
+ 
  /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
     the two MEMs cannot alias each other.  */
  
*************** int
*** 255,271 ****
  alias_sets_conflict_p (set1, set2)
       HOST_WIDE_INT set1, set2;
  {
!   alias_set_entry ase;
  
    /* If have no alias set information for one of the operands, we have
!      to assume it can alias anything.  */
!   if (set1 == 0 || set2 == 0
!       /* If the two alias sets are the same, they may alias.  */
!       || set1 == set2)
      return 1;
  
    /* See if the first alias set is a subset of the second.  */
!   ase = get_alias_set_entry (set1);
    if (ase != 0
        && (ase->has_zero_child
  	  || splay_tree_lookup (ase->children,
--- 283,305 ----
  alias_sets_conflict_p (set1, set2)
       HOST_WIDE_INT set1, set2;
  {
!   alias_set_entry ase, ase1, ase2;
! 
!   /* If the two alias sets are the same, they may alias.  */
!   if (set1 == set2)
!     return 1;
! 
!   ase1 = get_alias_set_entry (set1);
!   ase2 = get_alias_set_entry (set2);
  
    /* If have no alias set information for one of the operands, we have
!      to assume it can alias anything except a restricted set.  */
!   if ((set1 == 0 && !(ase2 && ase2->restricted))
!       || (set2 == 0 && !(ase1 && ase1->restricted)))
      return 1;
  
    /* See if the first alias set is a subset of the second.  */
!   ase = ase1;
    if (ase != 0
        && (ase->has_zero_child
  	  || splay_tree_lookup (ase->children,
*************** alias_sets_conflict_p (set1, set2)
*** 273,279 ****
      return 1;
  
    /* Now do the same, but with the alias sets reversed.  */
!   ase = get_alias_set_entry (set2);
    if (ase != 0
        && (ase->has_zero_child
  	  || splay_tree_lookup (ase->children,
--- 307,313 ----
      return 1;
  
    /* Now do the same, but with the alias sets reversed.  */
!   ase = ase2;
    if (ase != 0
        && (ase->has_zero_child
  	  || splay_tree_lookup (ase->children,
*************** get_alias_set (t)
*** 513,519 ****
  		    ;
  		  else
  		    {
! 		      DECL_POINTER_ALIAS_SET (decl) = new_alias_set ();
  		      record_alias_subset  (pointed_to_alias_set,
  					    DECL_POINTER_ALIAS_SET (decl));
  		    }
--- 547,554 ----
  		    ;
  		  else
  		    {
! 		      DECL_POINTER_ALIAS_SET (decl)
! 			= new_restricted_alias_set ();
  		      record_alias_subset  (pointed_to_alias_set,
  					    DECL_POINTER_ALIAS_SET (decl));
  		    }
*************** new_alias_set ()
*** 597,602 ****
--- 632,648 ----
      return 0;
  }
  
+ /* Like new_alias_set, but also record that the new set is restricted.  */
+ 
+ HOST_WIDE_INT
+ new_restricted_alias_set ()
+ {
+   HOST_WIDE_INT set = new_alias_set ();
+   alias_set_entry ase = get_alias_set_entry_create (set);
+   ase->restricted = 1;
+   return set;
+ }
+ 
  /* Indicate that things in SUBSET can alias things in SUPERSET, but
     not vice versa.  For example, in C, a store to an `int' can alias a
     structure containing an `int', but not vice versa.  Here, the
*************** record_alias_subset (superset, subset)
*** 622,641 ****
    if (superset == 0)
      abort ();
  
!   superset_entry = get_alias_set_entry (superset);
!   if (superset_entry == 0) 
!     {
!       /* Create an entry for the SUPERSET, so that we have a place to
! 	 attach the SUBSET.  */
!       superset_entry
! 	= (alias_set_entry) xmalloc (sizeof (struct alias_set_entry));
!       superset_entry->alias_set = superset;
!       superset_entry->children 
! 	= splay_tree_new (splay_tree_compare_ints, 0, 0);
!       superset_entry->has_zero_child = 0;
!       splay_tree_insert (alias_sets, (splay_tree_key) superset,
! 			 (splay_tree_value) superset_entry);
!     }
  
    if (subset == 0)
      superset_entry->has_zero_child = 1;
--- 668,676 ----
    if (superset == 0)
      abort ();
  
!   /* Create an entry for the SUPERSET, so that we have a place to
!      attach the SUBSET.  */
!   superset_entry = get_alias_set_entry_create (superset);
  
    if (subset == 0)
      superset_entry->has_zero_child = 1;
*** cse.c.~1~	Thu May  9 11:20:36 2002
--- cse.c	Fri May 10 16:47:06 2002
*************** check_dependence (x, data)
*** 1828,1842 ****
  
  /* Remove from the hash table, or mark as invalid, all expressions whose
     values could be altered by storing in X.  X is a register, a subreg, or
!    a memory reference with nonvarying address (because, when a memory
!    reference with a varying address is stored in, all memory references are
!    removed by invalidate_memory so specific invalidation is superfluous).
!    FULL_MODE, if not VOIDmode, indicates that this much should be
!    invalidated instead of just the amount indicated by the mode of X.  This
!    is only used for bitfield stores into memory.
! 
!    A nonvarying address may be just a register or just a symbol reference,
!    or it may be either of those plus a numeric offset.  */
  
  static void
  invalidate (x, full_mode)
--- 1828,1836 ----
  
  /* Remove from the hash table, or mark as invalid, all expressions whose
     values could be altered by storing in X.  X is a register, a subreg, or
!    a memory reference.  FULL_MODE, if not VOIDmode, indicates that this
!    much should be invalidated instead of just the amount indicated by the
!    mode of X.  This is only used for bitfield stores into memory.  */
  
  static void
  invalidate (x, full_mode)
*************** cse_insn (insn, libcall_insn)
*** 6341,6356 ****
  static void
  invalidate_memory ()
  {
!   int i;
!   struct table_elt *p, *next;
! 
!   for (i = 0; i < HASH_SIZE; i++)
!     for (p = table[i]; p; p = next)
!       {
! 	next = p->next_same_hash;
! 	if (p->in_memory)
! 	  remove_from_table (p, i);
!       }
  }
  
  /* If ADDR is an address that implicitly affects the stack pointer, return
--- 6335,6341 ----
  static void
  invalidate_memory ()
  {
!   invalidate (gen_rtx_MEM (BLKmode, const0_rtx), VOIDmode);
  }
  
  /* If ADDR is an address that implicitly affects the stack pointer, return
*** cp/cp-lang.c.~1~	Thu Apr 25 19:03:43 2002
--- cp/cp-lang.c	Fri May 10 16:34:32 2002
*************** Boston, MA 02111-1307, USA.  */
*** 25,30 ****
--- 25,32 ----
  #include "cp-tree.h"
  #include "c-common.h"
  #include "toplev.h"
+ #include "rtl.h"
+ #include "expr.h"
  #include "langhooks.h"
  #include "langhooks-def.h"
  
*************** cxx_get_alias_set (t)
*** 258,263 ****
--- 260,272 ----
    if (!ok_to_generate_alias_set_for_type(t))
      return 0;
  
+   if (t == vtbl_ptr_type_node)
+     {
+       /* Vtable pointer lookups don't alias with anything else.  */
+       TYPE_ALIAS_SET (t) = new_restricted_alias_set ();
+       return TYPE_ALIAS_SET (t);
+     }
+ 
    return c_common_get_alias_set (t);
  }
  
*** expr.h.~1~	Wed Apr  3 21:15:52 2002
--- expr.h	Fri May 10 16:31:46 2002
*************** extern void record_base_value		PARAMS ((
*** 358,363 ****
--- 358,364 ----
  extern void record_alias_subset         PARAMS ((HOST_WIDE_INT,
  						 HOST_WIDE_INT));
  extern HOST_WIDE_INT new_alias_set		PARAMS ((void));
+ extern HOST_WIDE_INT new_restricted_alias_set	PARAMS ((void));
  extern int can_address_p		PARAMS ((tree));
  
  /* Functions from expr.c:  */