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

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

[dann at godzilla dot ics dot uci dot edu]

Given:

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.

-- 
           Summary: [tree-ssa] aliasing bug
           Product: gcc
           Version: tree-ssa
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dann at godzilla dot ics dot uci dot edu
                CC: gcc-bugs at gcc dot gnu dot org


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

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

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-03-19 01:26 -------
Confirmed (I do not know how to read .alias dumps yet):
Alias statistics for foo

Total alias queries:	0
Total alias mayalias results:	0
Total alias noalias results:	0
Total simple queries:	0
Total simple resolved:	0
Total TBAA queries:	0
Total TBAA resolved:	0
Total PTA queries:	0
Total PTA resolved:	0


Pointed-to sets for pointers in foo

Pointer b<D1045>_1, points-to anything
Pointer T.0<D1049>_2, points-to anything


Alias information for foo

b<D1045>, UID 0, type memory tag: TMT.2<D1057>, default def: b<D1045>_1
T.0<D1049>, UID 1, type memory tag: TMT.3<D1058>
TMT.2<D1057>, UID 3, is global, call clobbered
TMT.3<D1058>, UID 4, is global, call clobbered

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
           Keywords|                            |wrong-code
   Last reconfirmed|0000-00-00 00:00:00         |2004-03-19 01:26:51
               date|                            |
   Target Milestone|---                         |tree-ssa


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

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

[dnovillo at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |dnovillo at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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

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

[dnovillo at redhat dot com]

------- 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

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

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2004-03-20 03:59 -------
Subject: Bug 14643

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	tree-ssa-20020619-branch
Changes by:	dnovillo@gcc.gnu.org	2004-03-20 03:59:45

Modified files:
	gcc            : ChangeLog.tree-ssa tree-ssa-alias.c 
	gcc/testsuite  : ChangeLog.tree-ssa 
Added files:
	gcc/testsuite/gcc.dg/tree-ssa: 20040319-1.c 

Log message:
	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.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.tree-ssa.diff?cvsroot=gcc&only_with_tag=tree-ssa-20020619-branch&r1=1.1.2.1288&r2=1.1.2.1289
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-alias.c.diff?cvsroot=gcc&only_with_tag=tree-ssa-20020619-branch&r1=1.1.2.14&r2=1.1.2.15
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.tree-ssa.diff?cvsroot=gcc&only_with_tag=tree-ssa-20020619-branch&r1=1.1.2.193&r2=1.1.2.194
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/20040319-1.c.diff?cvsroot=gcc&only_with_tag=tree-ssa-20020619-branch&r1=NONE&r2=1.1.2.1



-- 


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

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

[dnovillo at gcc dot gnu dot org]

------- Additional Comments From dnovillo at gcc dot gnu dot org  2004-03-20 04:01 -------

Fixed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


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