[PATCH] Fix PRs 60429 and 60485, PTA offset constraints

[Richard Biener <rguenther at suse dot de>]

This fixes offsetted constraint handling in the constraint builder
and the solver.  The existing code didn't consider non-equal-sized
fields and thus missed including all those that are overlapping
a offsetted variable.

Fixed like the following, bootstrapped and tested on 
x86_64-unknown-linux-gnu and applied to trunk sofar
(needs massaging to apply to 4.8 or 4.7).

[bah, points-to should support unit-testing - it's incredibly hard
to cover all bases - the testcases cover only two touched paths,
maybe time to revive and improve my -Otest idea...]

Richard.

2014-03-11  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/60429
	PR tree-optimization/60485
	* tree-ssa-structalias.c (set_union_with_increment): Properly
	take into account all fields that overlap the shifted vars.
	(do_sd_constraint): Likewise.
	(do_ds_constraint): Likewise.
	(get_constraint_for_ptr_offset): Likewise.

	* gcc.dg/pr60485-1.c: New testcase.
	* gcc.dg/pr60485-2.c: Likewise.

Index: gcc/tree-ssa-structalias.c
===================================================================
*** gcc/tree-ssa-structalias.c	(revision 208448)
--- gcc/tree-ssa-structalias.c	(working copy)
*************** set_union_with_increment  (bitmap to, bi
*** 993,1015 ****
  	changed |= bitmap_set_bit (to, i);
        else
  	{
! 	  unsigned HOST_WIDE_INT fieldoffset = vi->offset + inc;
  
  	  /* If the offset makes the pointer point to before the
  	     variable use offset zero for the field lookup.  */
! 	  if (inc < 0
! 	      && fieldoffset > vi->offset)
! 	    fieldoffset = 0;
! 
! 	  vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
! 
! 	  changed |= bitmap_set_bit (to, vi->id);
! 	  /* If the result is not exactly at fieldoffset include the next
! 	     field as well.  See get_constraint_for_ptr_offset for more
! 	     rationale.  */
! 	  if (vi->offset != fieldoffset
! 	      && vi->next != 0)
! 	    changed |= bitmap_set_bit (to, vi->next);
  	}
      }
  
--- 993,1020 ----
  	changed |= bitmap_set_bit (to, i);
        else
  	{
! 	  HOST_WIDE_INT fieldoffset = vi->offset + inc;
! 	  unsigned HOST_WIDE_INT size = vi->size;
  
  	  /* If the offset makes the pointer point to before the
  	     variable use offset zero for the field lookup.  */
! 	  if (fieldoffset < 0)
! 	    vi = get_varinfo (vi->head);
! 	  else
! 	    vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
! 
! 	  do
! 	    {
! 	      changed |= bitmap_set_bit (to, vi->id);
! 	      if (vi->is_full_var
! 		  || vi->next == 0)
! 		break;
! 
! 	      /* We have to include all fields that overlap the current field
! 	         shifted by inc.  */
! 	      vi = vi_next (vi);
! 	    }
! 	  while (vi->offset < fieldoffset + size);
  	}
      }
  
*************** do_sd_constraint (constraint_graph_t gra
*** 1618,1633 ****
      {
        varinfo_t v = get_varinfo (j);
        HOST_WIDE_INT fieldoffset = v->offset + roffset;
        unsigned int t;
  
        if (v->is_full_var)
! 	fieldoffset = v->offset;
        else if (roffset != 0)
! 	v = first_vi_for_offset (v, fieldoffset);
!       /* If the access is outside of the variable we can ignore it.  */
!       if (!v)
! 	continue;
  
        do
  	{
  	  t = find (v->id);
--- 1623,1643 ----
      {
        varinfo_t v = get_varinfo (j);
        HOST_WIDE_INT fieldoffset = v->offset + roffset;
+       unsigned HOST_WIDE_INT size = v->size;
        unsigned int t;
  
        if (v->is_full_var)
! 	;
        else if (roffset != 0)
! 	{
! 	  if (fieldoffset < 0)
! 	    v = get_varinfo (v->head);
! 	  else
! 	    v = first_or_preceding_vi_for_offset (v, fieldoffset);
! 	}
  
+       /* We have to include all fields that overlap the current field
+ 	 shifted by roffset.  */
        do
  	{
  	  t = find (v->id);
*************** do_sd_constraint (constraint_graph_t gra
*** 1644,1659 ****
  		   && add_graph_edge (graph, lhs, t))
  	    flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
  
! 	  /* If the variable is not exactly at the requested offset
! 	     we have to include the next one.  */
! 	  if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
  	      || v->next == 0)
  	    break;
  
  	  v = vi_next (v);
- 	  fieldoffset = v->offset;
  	}
!       while (1);
      }
  
  done:
--- 1654,1666 ----
  		   && add_graph_edge (graph, lhs, t))
  	    flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
  
! 	  if (v->is_full_var
  	      || v->next == 0)
  	    break;
  
  	  v = vi_next (v);
  	}
!       while (v->offset < fieldoffset + size);
      }
  
  done:
*************** do_ds_constraint (constraint_t c, bitmap
*** 1716,1730 ****
        varinfo_t v = get_varinfo (j);
        unsigned int t;
        HOST_WIDE_INT fieldoffset = v->offset + loff;
  
        if (v->is_full_var)
! 	fieldoffset = v->offset;
        else if (loff != 0)
! 	v = first_vi_for_offset (v, fieldoffset);
!       /* If the access is outside of the variable we can ignore it.  */
!       if (!v)
! 	continue;
  
        do
  	{
  	  if (v->may_have_pointers)
--- 1723,1742 ----
        varinfo_t v = get_varinfo (j);
        unsigned int t;
        HOST_WIDE_INT fieldoffset = v->offset + loff;
+       unsigned HOST_WIDE_INT size = v->size;
  
        if (v->is_full_var)
! 	;
        else if (loff != 0)
! 	{
! 	  if (fieldoffset < 0)
! 	    v = get_varinfo (v->head);
! 	  else
! 	    v = first_or_preceding_vi_for_offset (v, fieldoffset);
! 	}
  
+       /* We have to include all fields that overlap the current field
+ 	 shifted by loff.  */
        do
  	{
  	  if (v->may_have_pointers)
*************** do_ds_constraint (constraint_t c, bitmap
*** 1750,1765 ****
  		bitmap_set_bit (changed, t);
  	    }
  
! 	  /* If the variable is not exactly at the requested offset
! 	     we have to include the next one.  */
! 	  if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
  	      || v->next == 0)
  	    break;
  
  	  v = vi_next (v);
- 	  fieldoffset = v->offset;
  	}
!       while (1);
      }
  }
  
--- 1762,1774 ----
  		bitmap_set_bit (changed, t);
  	    }
  
! 	  if (v->is_full_var
  	      || v->next == 0)
  	    break;
  
  	  v = vi_next (v);
  	}
!       while (v->offset < fieldoffset + size);
      }
  }
  
*************** get_constraint_for_ptr_offset (tree ptr,
*** 3109,3143 ****
  	  varinfo_t temp;
  	  unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
  
! 	  /* Search the sub-field which overlaps with the
! 	     pointed-to offset.  If the result is outside of the variable
! 	     we have to provide a conservative result, as the variable is
! 	     still reachable from the resulting pointer (even though it
! 	     technically cannot point to anything).  The last and first
! 	     sub-fields are such conservative results.
! 	     ???  If we always had a sub-field for &object + 1 then
! 	     we could represent this in a more precise way.  */
  	  if (rhsoffset < 0
  	      && curr->offset < offset)
  	    offset = 0;
- 	  temp = first_or_preceding_vi_for_offset (curr, offset);
  
! 	  /* If the found variable is not exactly at the pointed to
! 	     result, we have to include the next variable in the
! 	     solution as well.  Otherwise two increments by offset / 2
! 	     do not result in the same or a conservative superset
! 	     solution.  */
! 	  if (temp->offset != offset
! 	      && temp->next != 0)
  	    {
  	      struct constraint_expr c2;
! 	      c2.var = temp->next;
  	      c2.type = ADDRESSOF;
  	      c2.offset = 0;
  	      results->safe_push (c2);
  	    }
- 	  c.var = temp->id;
- 	  c.offset = 0;
  	}
        else
  	c.offset = rhsoffset;
--- 3118,3147 ----
  	  varinfo_t temp;
  	  unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
  
! 	  /* If curr->offset + rhsoffset is less than zero adjust it.  */
  	  if (rhsoffset < 0
  	      && curr->offset < offset)
  	    offset = 0;
  
! 	  /* We have to include all fields that overlap the current
! 	     field shifted by rhsoffset.  And we include at least
! 	     the last or the first field of the variable to represent
! 	     reachability of off-bound addresses, in particular &object + 1,
! 	     conservatively correct.  */
! 	  temp = first_or_preceding_vi_for_offset (curr, offset);
! 	  c.var = temp->id;
! 	  c.offset = 0;
! 	  temp = vi_next (temp);
! 	  while (temp
! 		 && temp->offset < offset + curr->size)
  	    {
  	      struct constraint_expr c2;
! 	      c2.var = temp->id;
  	      c2.type = ADDRESSOF;
  	      c2.offset = 0;
  	      results->safe_push (c2);
+ 	      temp = vi_next (temp);
  	    }
  	}
        else
  	c.offset = rhsoffset;
Index: gcc/testsuite/gcc.dg/pr60485-1.c
===================================================================
*** gcc/testsuite/gcc.dg/pr60485-1.c	(revision 0)
--- gcc/testsuite/gcc.dg/pr60485-1.c	(working copy)
***************
*** 0 ****
--- 1,29 ----
+ /* { dg-do run } */
+ /* { dg-options "-O2" } */
+ 
+ extern void abort (void);
+ struct S {
+     int *i[4];
+     int *p1;
+     int *p2;
+     int *p3;
+     int *p4;
+ };
+ int **b;
+ int main()
+ {
+   int i = 1;
+   struct S s;
+   s.p3 = &i;
+   int **p;
+   if (b)
+     p = b;
+   else
+     p = &s.i[2];
+   p += 4;
+   if (!b)
+     **p = 0;
+   if (i != 0)
+     abort ();
+   return i;
+ }
Index: gcc/testsuite/gcc.dg/pr60485-2.c
===================================================================
*** gcc/testsuite/gcc.dg/pr60485-2.c	(revision 0)
--- gcc/testsuite/gcc.dg/pr60485-2.c	(working copy)
***************
*** 0 ****
--- 1,38 ----
+ /* { dg-do run } */
+ /* { dg-options "-O2" } */
+ 
+ extern void abort (void);
+ struct S {
+     int *i[4];
+     int *p1;
+     int *p2;
+     int *p3;
+     int *p4;
+     int **x;
+ };
+ int **b;
+ int main()
+ {
+   int i = 1;
+   struct S s;
+   s.p3 = &i;
+   int **p;
+   if (b)
+     p = b;
+   else
+     p = &s.i[2];
+   p += 4;
+   /* prevert fowrprop from creating an offsetted sd constraint and
+      preserve the pointer offsetting constraint.  */
+   s.x = p;
+   p = s.x;
+   if (!b)
+     {
+       int *z = *p;
+       /* z should point to i (and non-local/escaped).  */
+       *z = 0;
+     }
+   if (i != 0)
+     abort ();
+   return i;
+ }