[Bug optimization/14643] [tree-ssa] aliasing bug

["dnovillo at redhat dot com" <gcc-bugzilla at gcc dot gnu dot org>]

------- Additional Comments From dnovillo at redhat dot com  2004-03-20 03:55 -------
Subject: Re: [tree-ssa] aliasing bug

On Thu, 2004-03-18 at 20:22, dann at godzilla dot ics dot uci dot edu
wrote:

> struct bar { int count;  int *arr;};
> 
> void foo (struct bar *b)
> {
>   b->count = 0;
>   *(b->arr) = 2;
>   if (b->count != 0)  link_error ();
> }
> 
> "if" should not be optimized, but it currently is.
>
Indeed.  The problem in this case is that we have no addressable
variables in function foo().  The aliasing code compares every type tag
against every addressable variable to compute alias sets.

We never compare type tags to each other because it is not necessary if
we have addressable variables.  Addressable variables act as the alias
tags that populate may-alias sets.

Fixed by detecting this case and using memory tags as addressable
variables when we have none to work with.  Added an executable version
of this code as gcc.dg/tree-ssa/20040319-1.c.

Bootstrapped and tested on x86 and x86-64.


Diego.


	PR optimization/14643
	* tree-ssa-alias.c (group_aliases_into): Don't add a variable
	to its own may-alias set.
	(create_alias_map_for): New.
	(setup_pointers_and_addressables): Call it.
	Fix allocation of AI->ADDRESSABLE_VARS and AI->POINTERS.
	If there are no addressable variables and more than one
	dereferenced pointers, add type tags to the ADDRESSABLE_VARS
	array.
	(get_tmt_for): Add comment about using alias set equality when
	checking for existing tags.

testsuite/ChangeLog.tree-ssa:

	* gcc.dg/tree-ssa/20040319-1.c: New test.

Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-alias.c,v
retrieving revision 1.1.2.14
diff -d -c -p -r1.1.2.14 tree-ssa-alias.c
*** tree-ssa-alias.c	19 Mar 2004 02:07:25 -0000	1.1.2.14
--- tree-ssa-alias.c	20 Mar 2004 01:00:18 -0000
*************** group_aliases_into (tree tag, sbitmap ta
*** 880,886 ****
        /* Make TAG the unique alias of VAR.  */
        ann->is_alias_tag = 0;
        ann->may_aliases = NULL;
!       add_may_alias (var, tag);
  
        /* Reduce total number of virtual operands contributed
  	 by TAG on behalf of VAR.  Notice that the references to VAR
--- 880,891 ----
        /* Make TAG the unique alias of VAR.  */
        ann->is_alias_tag = 0;
        ann->may_aliases = NULL;
! 
!       /* Note that VAR and TAG may be the same if the function has no
! 	 addressable variables (see the discussion at the end of
! 	 setup_pointers_and_addressables). */
!       if (var != tag)
! 	add_may_alias (var, tag);
  
        /* Reduce total number of virtual operands contributed
  	 by TAG on behalf of VAR.  Notice that the references to VAR
*************** group_aliases (struct alias_info *ai)
*** 1071,1076 ****
--- 1076,1098 ----
  }
  
  
+ /* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS.  */
+ 
+ static void
+ create_alias_map_for (tree var, struct alias_info *ai)
+ {
+   struct alias_map_d *alias_map;
+   alias_map = xcalloc (1, sizeof (*alias_map));
+   alias_map->var = var;
+ 
+   if (TREE_CODE (TREE_TYPE (var)) == ARRAY_TYPE)
+     alias_map->set = get_alias_set (TREE_TYPE (TREE_TYPE (var)));
+   else
+     alias_map->set = get_alias_set (var);
+   ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
+ }
+ 
+ 
  /* Create memory tags for all the dereferenced pointers and build the
     ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias
     sets.  Based on the address escape and points-to information collected
*************** setup_pointers_and_addressables (struct 
*** 1109,1116 ****
       because some TREE_ADDRESSABLE variables will be marked
       non-addressable below and only pointers with unique type tags are
       going to be added to POINTERS.  */
!   ai->addressable_vars = xcalloc (num_addressable_vars, sizeof (tree));
!   ai->pointers = xcalloc (num_pointers, sizeof (tree));
    ai->num_addressable_vars = 0;
    ai->num_pointers = 0;
  
--- 1131,1139 ----
       because some TREE_ADDRESSABLE variables will be marked
       non-addressable below and only pointers with unique type tags are
       going to be added to POINTERS.  */
!   ai->addressable_vars = xcalloc (num_addressable_vars,
! 				  sizeof (struct alias_map_d *));
!   ai->pointers = xcalloc (num_pointers, sizeof (struct alias_map_d *));
    ai->num_addressable_vars = 0;
    ai->num_pointers = 0;
  
*************** setup_pointers_and_addressables (struct 
*** 1157,1172 ****
           entry in ADDRESSABLE_VARS for VAR.  */
        if (may_be_aliased (var))
  	{
! 	  /* Create a new alias set entry for VAR.  */
! 	  struct alias_map_d *alias_map;
! 	  alias_map = xcalloc (1, sizeof (*alias_map));
! 	  alias_map->var = var;
! 
! 	  if (TREE_CODE (TREE_TYPE (var)) == ARRAY_TYPE)
! 	    alias_map->set = get_alias_set (TREE_TYPE (TREE_TYPE (var)));
! 	  else
! 	    alias_map->set = get_alias_set (var);
! 	  ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
  	  bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
  	}
  
--- 1180,1186 ----
           entry in ADDRESSABLE_VARS for VAR.  */
        if (may_be_aliased (var))
  	{
! 	  create_alias_map_for (var, ai);
  	  bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
  	}
  
*************** setup_pointers_and_addressables (struct 
*** 1204,1209 ****
--- 1218,1258 ----
  	  ai->num_references[t_ann->uid] += ai->num_references[v_ann->uid];
  	}
      }
+ 
+   /* If we found no addressable variables, but we have more than one
+      pointer, we will need to check for conflicts between the
+      pointers.  Otherwise, we would miss alias relations as in
+      testsuite/gcc.dg/tree-ssa/20040319-1.c:
+ 
+ 		struct bar { int count;  int *arr;};
+ 
+ 		void foo (struct bar *b)
+ 		{
+ 		  b->count = 0;
+ 		  *(b->arr) = 2;
+ 		  if (b->count == 0)
+ 		    abort ();
+ 		}
+ 
+      b->count and *(b->arr) could be aliased if b->arr == &b->count.
+      To do this, we add all the memory tags for the pointers in
+      AI->POINTERS to AI->ADDRESSABLE_VARS, so that
+      compute_flow_insensitive_aliasing will naturally compare every
+      pointer to every type tag.  */
+   if (ai->num_addressable_vars == 0
+       && ai->num_pointers > 1)
+     {
+       free (ai->addressable_vars);
+       ai->addressable_vars = xcalloc (ai->num_pointers,
+ 				      sizeof (struct alias_map_d *));
+       ai->num_addressable_vars = 0;
+       for (i = 0; i < ai->num_pointers; i++)
+ 	{
+ 	  struct alias_map_d *p = ai->pointers[i];
+ 	  tree tag = var_ann (p->var)->type_mem_tag;
+ 	  create_alias_map_for (tag, ai);
+ 	}
+     }
  }
  
  
*************** get_tmt_for (tree ptr, struct alias_info
*** 1768,1774 ****
    HOST_WIDE_INT tag_set = get_alias_set (tag_type);
  
    /* To avoid creating unnecessary memory tags, only create one memory tag
!      per alias set class.  */
    for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++)
      {
        struct alias_map_d *curr = ai->pointers[i];
--- 1817,1829 ----
    HOST_WIDE_INT tag_set = get_alias_set (tag_type);
  
    /* To avoid creating unnecessary memory tags, only create one memory tag
!      per alias set class.  Note that it may be tempting to group
!      memory tags based on conflicting alias sets instead of
!      equivalence.  That would be wrong because alias sets are not
!      necessarily transitive (as demonstrated by the libstdc++ test
!      23_containers/vector/cons/4.cc).  Given three alias sets A, B, C
!      such that conflicts (A, B) == true and conflicts (A, C) == true,
!      it does not necessarily follow that conflicts (B, C) == true.  */
    for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++)
      {
        struct alias_map_d *curr = ai->pointers[i];
Index: testsuite/gcc.dg/tree-ssa/20040319-1.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/20040319-1.c
diff -N testsuite/gcc.dg/tree-ssa/20040319-1.c
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- testsuite/gcc.dg/tree-ssa/20040319-1.c	20 Mar 2004 01:00:18 -0000
***************
*** 0 ****
--- 1,25 ----
+ /* { dg-do run } */
+ /* { dg-options "-O2" } */
+ 
+ /* Test derived from PR 14643.  When a function has no addressable
+    variables but 2 or more pointers have conflicting memory tags, they
+    were not being processed by the type based alias analyzer,
+    resulting in optimizations removing a non-redundant load.  */
+ 
+ struct bar { int count;  int *arr;};
+ 
+ void foo (struct bar *b)
+ {
+   b->count = 0;
+   *(b->arr) = 2;
+   if (b->count == 0)	/* b->count can't be assumed to be 0 here.  */
+     abort ();
+ }
+ 
+ main ()
+ {
+   struct bar x;
+   x.arr = &x.count;
+   foo (&x);
+   return 0;
+ }



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14643