[PATCH] Fix PR33870, alias bug with SFTs and pointers

[Richard Guenther <rguenther at suse dot de>]

In this bug we manage to prune SFTs for a subvariable because we
TBAA pruned the SFT for offset zero and as such do not have the
SFT as pointed-to anchor as we iterate through all possible anchors
interpreting the [offset, size[ access relative to it searching
for SFTs touched.

Fixed by always considering offset zero as anchor.  Note though,
even while offset zero is special, there might be a testcase where
we prune an anchor in the middle of a structure which we really
can't recover here.  Shouldn't we iterate through the pt_vars set
instead for this purpose?  The current state looks somewhat fragile.

Richard.


2007-10-23  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/33870
	* tree-ssa-operands.c (add_vars_for_offset): Always consider
	an SFT based on a pointer to offset zero of the parent var.
	Reduce code duplication.

	* gcc.dg/tree-ssa/alias-15.c: New testcase.
	* gcc.c-torture/execute/pr33870.c: Likewise.

Index: tree-ssa-operands.c
===================================================================
*** tree-ssa-operands.c	(revision 129582)
--- tree-ssa-operands.c	(working copy)
*************** add_vars_for_offset (tree full_ref, tree
*** 1404,1410 ****
       NULL).
       Any var for which we didn't create SFT's can't be
       distinguished.  */
!   if (!full_ref || (offset == 0 && size != -1)
        || (TREE_CODE (var) != STRUCT_FIELD_TAG
  	  && (!var_can_have_subvars (var) || !get_subvars_for_var (var))))
      {
--- 1404,1411 ----
       NULL).
       Any var for which we didn't create SFT's can't be
       distinguished.  */
!   if (!full_ref
!       || (offset == 0 && size != -1)
        || (TREE_CODE (var) != STRUCT_FIELD_TAG
  	  && (!var_can_have_subvars (var) || !get_subvars_for_var (var))))
      {
*************** add_vars_for_offset (tree full_ref, tree
*** 1417,1468 ****
  	append_vuse (var);
        return true;
      }
!   else if (TREE_CODE (var) == STRUCT_FIELD_TAG)
      {      
!       if (size == -1)
  	{
! 	  bool added = false;
! 	  subvar_t sv = get_subvars_for_var (SFT_PARENT_VAR (var));
! 	  for (; sv; sv = sv->next)
! 	    {
! 	      if (overlap_subvar (SFT_OFFSET (var) + offset, size,
! 				  sv->var, NULL)
! 		  && access_can_touch_variable (full_ref, sv->var,
! 						offset, size))
! 		{
! 		  added = true;
! 		  if (is_def)
! 		    append_vdef (sv->var);
! 		  else
! 		    append_vuse (sv->var);
! 		}
! 	    }
! 	  return added;
  	}
!       else
  	{
! 	  bool added = false;
! 	  subvar_t sv = get_subvars_for_var (SFT_PARENT_VAR (var));
! 	  for (; sv; sv = sv->next)
  	    {
! 	      /* Once we hit the end of the parts that could touch,
! 		 stop looking.  */
! 	      if (SFT_OFFSET (var) + offset + size <= SFT_OFFSET (sv->var))
! 		break;
! 	      if (overlap_subvar (SFT_OFFSET (var) + offset, size,
! 				  sv->var, NULL)
! 		  && access_can_touch_variable (full_ref, sv->var, offset, 
! 						size))
! 		{
! 		  added = true;
! 		  if (is_def)
! 		    append_vdef (sv->var);
! 		  else
! 		    append_vuse (sv->var);
! 		}
  	    }
- 	  return added;
  	}
      }
    
    return false;
--- 1418,1462 ----
  	append_vuse (var);
        return true;
      }
! 
!   /* VAR can be a pointed-to location, so look for overlapping SFTs
!      if the access [offset, size[ was relative to that location.  */
!   if (TREE_CODE (var) == STRUCT_FIELD_TAG)
      {      
!       bool added = false;
!       subvar_t sv = get_subvars_for_var (SFT_PARENT_VAR (var));
! 
!       /* We always have to consider the SFT itself.  This is because we
! 	 might have pruned the SFT for offset zero during TBAA.  */
!       if (overlap_subvar (offset, size, var, NULL)
! 	  && access_can_touch_variable (full_ref, var, offset, size))
  	{
! 	  added = true;
! 	  if (is_def)
! 	    append_vdef (var);
! 	  else
! 	    append_vuse (var);
  	}
! 
!       for (; sv; sv = sv->next)
  	{
! 	  /* Once we hit the end of the parts that could touch,
! 	     stop looking.  */
! 	  if (size != -1
! 	      && SFT_OFFSET (var) + offset + size <= SFT_OFFSET (sv->var))
! 	    break;
! 	  if (overlap_subvar (SFT_OFFSET (var) + offset, size,
! 			      sv->var, NULL)
! 	      && access_can_touch_variable (full_ref, sv->var, offset, size))
  	    {
! 	      added = true;
! 	      if (is_def)
! 		append_vdef (sv->var);
! 	      else
! 		append_vuse (sv->var);
  	    }
  	}
+       return added;
      }
    
    return false;
Index: testsuite/gcc.dg/tree-ssa/alias-15.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/alias-15.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/alias-15.c	(revision 0)
***************
*** 0 ****
--- 1,20 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fno-early-inlining -fdump-tree-salias-vops-details" } */
+ 
+ struct foo {
+   int a;
+   struct X {
+     int b[4];
+   } b;
+ } m;
+ static inline struct X *wrap(struct X *p) { return p; }
+ int test2(void)
+ {
+   struct X *p = wrap(&m.b);
+   /* Both memory references need to alias the same SFT.  */
+   return p->b[3] - m.b.b[3];
+ }
+ 
+ /* { dg-final { scan-tree-dump "SFT.1 created for var m offset 128" "salias" } } */
+ /* { dg-final { scan-tree-dump-times "VUSE <SFT.1_" 2 "salias" } } */
+ /* { dg-final { cleanup-tree-dump "salias" } } */
Index: testsuite/gcc.c-torture/execute/pr33870.c
===================================================================
*** testsuite/gcc.c-torture/execute/pr33870.c	(revision 0)
--- testsuite/gcc.c-torture/execute/pr33870.c	(revision 0)
***************
*** 0 ****
--- 1,87 ----
+ extern void abort (void);
+ 
+ typedef struct PgHdr PgHdr;
+ typedef unsigned char u8;
+ struct PgHdr {
+   unsigned int pgno;
+   PgHdr *pNextHash, *pPrevHash;
+   PgHdr *pNextFree, *pPrevFree;
+   PgHdr *pNextAll;
+   u8 inJournal;
+   short int nRef;
+   PgHdr *pDirty, *pPrevDirty;
+   unsigned int notUsed;
+ };
+ 
+ static inline PgHdr *merge_pagelist(PgHdr *pA, PgHdr *pB)
+ {
+   PgHdr result;
+   PgHdr *pTail;
+   pTail = &result;
+   while( pA && pB ){
+     if( pA->pgno<pB->pgno ){
+       pTail->pDirty = pA;
+       pTail = pA;
+       pA = pA->pDirty;
+     }else{
+       pTail->pDirty = pB;
+       pTail = pB;
+       pB = pB->pDirty;
+     }
+   }
+   if( pA ){
+     pTail->pDirty = pA;
+   }else if( pB ){
+     pTail->pDirty = pB;
+   }else{
+     pTail->pDirty = 0;
+   }
+   return result.pDirty;
+ }
+ 
+ PgHdr * __attribute__((noinline)) sort_pagelist(PgHdr *pIn)
+ {
+   PgHdr *a[25], *p;
+   int i;
+   __builtin_memset (a, 0, sizeof (a));
+   while( pIn ){
+     p = pIn;
+     pIn = p->pDirty;
+     p->pDirty = 0;
+     for(i=0; i<25 -1; i++){
+       if( a[i]==0 ){
+         a[i] = p;
+         break;
+       }else{
+         p = merge_pagelist(a[i], p);
+         a[i] = 0;
+       }
+     }
+     if( i==25 -1 ){
+       a[i] = merge_pagelist(a[i], p);
+     }
+   }
+   p = a[0];
+   for(i=1; i<25; i++){
+     p = merge_pagelist (p, a[i]);
+   }
+   return p;
+ }
+ 
+ int main()
+ {
+   PgHdr a[5];
+   PgHdr *p;
+   a[0].pgno = 5;
+   a[0].pDirty = &a[1];
+   a[1].pgno = 4;
+   a[1].pDirty = &a[2];
+   a[2].pgno = 1;
+   a[2].pDirty = &a[3];
+   a[3].pgno = 3;
+   a[3].pDirty = 0;
+   p = sort_pagelist (&a[0]);
+   if (p->pDirty == p)
+     abort ();
+   return 0;
+ }