This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][alias-improvements] Handle unknown offsets in PTA
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Cc: Daniel Berlin <dberlin at dberlin dot org>
- Date: Sat, 31 Jan 2009 20:06:14 +0100 (CET)
- Subject: [PATCH][alias-improvements] Handle unknown offsets in PTA
This implements handling of unknown offset constraints in the PTA
solver (by using a special offset value). Now the only thing where
we (needlessly) fall back to anything is negative constant offsets
(to be addressed with a followup patch). Pointer offsets
only need special handling with field-sensitive analysis. There
if your points-to set S includes x.N then the constraint
y = S + off needs to add all fields of x to the solution of y.
With that we can for the following
x = &a.k[0];
q = &x[i];
tell that q points to x instead of anything.
Bootstrapped and tested on x86_64-unknown-linux-gnu. This XPASSes
some vectorizer tests (including one that falsely claims that
vectorizing is impossible).
Danny, you may remember me talking about this solver/constraint
support for this - are you ok with the general approach?
Thanks,
Richard.
2009-01-31 Richard Guenther <rguenther@suse.de>
PR tree-optimization/38049
* tree-ssa-structalias.c (UNKNOWN_OFFSET): Define special value.
(solution_set_expand): New helper function split out from ...
(do_sd_constraint): ... here.
(solution_set_add): Handle UNKNOWN_OFFSET.
(do_sd_constraint): Likewise.
(do_ds_constraint): Likewise.
(get_constraint_for_ptr_offset): Handle unknown offsets.
* gcc.dg/torture/pta-ptrarith-3.c: New testcase.
* gcc.dg/tree-ssa/pta-ptrarith-1.c: Likewise.
* gcc.dg/tree-ssa/pta-ptrarith-2.c: Likewise.
* gcc.dg/vect/no-vfa-vect-43.c: Adjust.
Index: gcc/tree-ssa-structalias.c
===================================================================
*** gcc/tree-ssa-structalias.c.orig 2009-01-31 17:36:37.000000000 +0100
--- gcc/tree-ssa-structalias.c 2009-01-31 18:05:03.000000000 +0100
*************** struct constraint_expr
*** 410,415 ****
--- 410,418 ----
unsigned HOST_WIDE_INT offset;
};
+ /* Use 0x8000... as special unknown offset. */
+ #define UNKNOWN_OFFSET (unsigned HOST_WIDE_INT)1 << (HOST_BITS_PER_WIDE_INT-1)
+
typedef struct constraint_expr ce_s;
DEF_VEC_O(ce_s);
DEF_VEC_ALLOC_O(ce_s, heap);
*************** constraint_set_union (VEC(constraint_t,h
*** 824,829 ****
--- 827,883 ----
}
}
+ /* Expands the solution in SET to all sub-fields of variables included.
+ Union the expanded result into RESULT, the difference into DELTA if
+ that is non-NULL. Returns true if DELTA is non-empty. */
+
+ static bool
+ solution_set_expand (bitmap result, bitmap delta, bitmap set)
+ {
+ bitmap_iterator bi;
+ bitmap vars = NULL;
+ unsigned j;
+ bool flag = false;
+
+ /* In a first pass record all variables we need to add all
+ sub-fields off. This avoids quadratic behavior. */
+ EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
+ {
+ varinfo_t v = get_varinfo (j);
+ if (v->is_full_var)
+ continue;
+
+ v = lookup_vi_for_tree (v->decl);
+ if (v->next != NULL)
+ {
+ if (vars == NULL)
+ vars = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (vars, v->id);
+ }
+ }
+ /* In the second pass now do the addition to the solution and
+ to speed up solving add it to the delta as well. */
+ if (vars != NULL)
+ {
+ EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
+ {
+ varinfo_t v = get_varinfo (j);
+ for (; v != NULL; v = v->next)
+ {
+ if (bitmap_set_bit (result, v->id))
+ {
+ flag = true;
+ if (delta)
+ bitmap_set_bit (delta, v->id);
+ }
+ }
+ }
+ BITMAP_FREE (vars);
+ }
+
+ return flag;
+ }
+
/* Take a solution set SET, add OFFSET to each member of the set, and
overwrite SET with the result when done. */
*************** solution_set_add (bitmap set, unsigned H
*** 834,839 ****
--- 888,901 ----
unsigned int i;
bitmap_iterator bi;
+ /* If the offset is unknown we have to expand the solution to
+ all subfields. */
+ if (offset == UNKNOWN_OFFSET)
+ {
+ solution_set_expand (set, NULL, set);
+ return;
+ }
+
EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
{
varinfo_t vi = get_varinfo (i);
*************** do_sd_constraint (constraint_graph_t gra
*** 1501,1506 ****
--- 1563,1569 ----
bitmap sol = get_varinfo (lhs)->solution;
unsigned int j;
bitmap_iterator bi;
+ unsigned HOST_WIDE_INT roffset;
/* For x = *ESCAPED and x = *CALLUSED we want to compute the
reachability set of the rhs var. As a pointer to a sub-field
*************** do_sd_constraint (constraint_graph_t gra
*** 1509,1551 ****
if one sub-field is contained. */
if (c->rhs.var == escaped_id
|| c->rhs.var == callused_id)
! {
! bitmap vars = NULL;
! /* In a first pass record all variables we need to add all
! sub-fields off. This avoids quadratic behavior. */
! EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
! {
! varinfo_t v = get_varinfo (j);
! if (v->is_full_var)
! continue;
!
! v = lookup_vi_for_tree (v->decl);
! if (v->next != NULL)
! {
! if (vars == NULL)
! vars = BITMAP_ALLOC (NULL);
! bitmap_set_bit (vars, v->id);
! }
! }
! /* In the second pass now do the addition to the solution and
! to speed up solving add it to the delta as well. */
! if (vars != NULL)
! {
! EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
! {
! varinfo_t v = get_varinfo (j);
! for (; v != NULL; v = v->next)
! {
! if (bitmap_set_bit (sol, v->id))
! {
! flag = true;
! bitmap_set_bit (delta, v->id);
! }
! }
! }
! BITMAP_FREE (vars);
! }
! }
if (bitmap_bit_p (delta, anything_id))
{
--- 1572,1578 ----
if one sub-field is contained. */
if (c->rhs.var == escaped_id
|| c->rhs.var == callused_id)
! flag |= solution_set_expand (sol, delta, delta);
if (bitmap_bit_p (delta, anything_id))
{
*************** do_sd_constraint (constraint_graph_t gra
*** 1553,1563 ****
goto done;
}
/* For each variable j in delta (Sol(y)), add
an edge in the graph from j to x, and union Sol(j) into Sol(x). */
EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
{
- unsigned HOST_WIDE_INT roffset = c->rhs.offset;
if (type_safe (j, &roffset))
{
varinfo_t v;
--- 1580,1596 ----
goto done;
}
+ roffset = c->rhs.offset;
+ if (roffset == UNKNOWN_OFFSET)
+ {
+ flag |= solution_set_expand (sol, delta, delta);
+ roffset = 0;
+ }
+
/* For each variable j in delta (Sol(y)), add
an edge in the graph from j to x, and union Sol(j) into Sol(x). */
EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
{
if (type_safe (j, &roffset))
{
varinfo_t v;
*************** do_ds_constraint (constraint_t c, bitmap
*** 1607,1612 ****
--- 1640,1646 ----
bitmap sol = get_varinfo (rhs)->solution;
unsigned int j;
bitmap_iterator bi;
+ unsigned HOST_WIDE_INT loff;
if (bitmap_bit_p (sol, anything_id))
{
*************** do_ds_constraint (constraint_t c, bitmap
*** 1638,1648 ****
return;
}
/* For each member j of delta (Sol(x)), add an edge from y to j and
union Sol(y) into Sol(j) */
EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
{
- unsigned HOST_WIDE_INT loff = c->lhs.offset;
if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var))
{
varinfo_t v;
--- 1672,1688 ----
return;
}
+ loff = c->lhs.offset;
+ if (loff == UNKNOWN_OFFSET)
+ {
+ solution_set_expand (sol, delta, delta);
+ loff = 0;
+ }
+
/* For each member j of delta (Sol(x)), add an edge from y to j and
union Sol(y) into Sol(j) */
EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
{
if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var))
{
varinfo_t v;
*************** get_constraint_for_ptr_offset (tree ptr,
*** 2779,2799 ****
struct constraint_expr *c;
unsigned int j, n;
unsigned HOST_WIDE_INT rhsunitoffset, rhsoffset;
- varinfo_t vi;
- tree var;
/* If we do not do field-sensitive PTA adding offsets to pointers
does not change the points-to solution. */
! if (!use_field_sensitive
! /* The same is true if we are offsetting a variable that has not
! been decomposed.
! ??? This can be done more generally as well, with support in
! the solver. */
! || (TREE_CODE (ptr) == ADDR_EXPR
! && (var = get_base_address (TREE_OPERAND (ptr, 0)))
! && DECL_P (var)
! && (vi = get_vi_for_tree (var))
! && vi->is_full_var))
{
get_constraint_for (ptr, results);
return;
--- 2819,2828 ----
struct constraint_expr *c;
unsigned int j, n;
unsigned HOST_WIDE_INT rhsunitoffset, rhsoffset;
/* If we do not do field-sensitive PTA adding offsets to pointers
does not change the points-to solution. */
! if (!use_field_sensitive)
{
get_constraint_for (ptr, results);
return;
*************** get_constraint_for_ptr_offset (tree ptr,
*** 2802,2831 ****
/* If the offset is not a non-negative integer constant that fits
in a HOST_WIDE_INT, we have to fall back to a conservative
solution which includes all sub-fields of all pointed-to
! variables of ptr.
! ??? As we do not have the ability to express this, fall back
! to anything. */
if (!host_integerp (offset, 1))
{
! struct constraint_expr temp;
! temp.var = anything_id;
! temp.type = SCALAR;
! temp.offset = 0;
! VEC_safe_push (ce_s, heap, *results, &temp);
! return;
! }
!
! /* Make sure the bit-offset also fits. */
! rhsunitoffset = TREE_INT_CST_LOW (offset);
! rhsoffset = rhsunitoffset * BITS_PER_UNIT;
! if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
! {
! struct constraint_expr temp;
! temp.var = anything_id;
! temp.type = SCALAR;
! temp.offset = 0;
! VEC_safe_push (ce_s, heap, *results, &temp);
! return;
}
get_constraint_for (ptr, results);
--- 2831,2846 ----
/* If the offset is not a non-negative integer constant that fits
in a HOST_WIDE_INT, we have to fall back to a conservative
solution which includes all sub-fields of all pointed-to
! variables of ptr. */
if (!host_integerp (offset, 1))
+ rhsoffset = UNKNOWN_OFFSET;
+ else
{
! /* Make sure the bit-offset also fits. */
! rhsunitoffset = TREE_INT_CST_LOW (offset);
! rhsoffset = rhsunitoffset * BITS_PER_UNIT;
! if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
! rhsoffset = UNKNOWN_OFFSET;
}
get_constraint_for (ptr, results);
*************** get_constraint_for_ptr_offset (tree ptr,
*** 2842,2848 ****
curr = get_varinfo (c->var);
if (c->type == ADDRESSOF
! && !curr->is_full_var)
{
varinfo_t temp, curr = get_varinfo (c->var);
--- 2857,2864 ----
curr = get_varinfo (c->var);
if (c->type == ADDRESSOF
! && !curr->is_full_var
! && rhsoffset != UNKNOWN_OFFSET)
{
varinfo_t temp, curr = get_varinfo (c->var);
*************** get_constraint_for_ptr_offset (tree ptr,
*** 2887,2892 ****
--- 2903,2924 ----
/* If this varinfo represents a full variable just use it. */
&& curr->is_full_var)
c->offset = 0;
+ else if (c->type == ADDRESSOF
+ /* If we do not know the offset add all subfields. */
+ && rhsoffset == UNKNOWN_OFFSET)
+ {
+ varinfo_t temp = lookup_vi_for_tree (curr->decl);
+ do
+ {
+ struct constraint_expr c2;
+ c2.var = temp->id;
+ c2.type = ADDRESSOF;
+ c2.offset = 0;
+ VEC_safe_push (ce_s, heap, *results, &c2);
+ temp = temp->next;
+ }
+ while (temp);
+ }
else
c->offset = rhsoffset;
}
Index: gcc/testsuite/gcc.dg/torture/pta-ptrarith-3.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/torture/pta-ptrarith-3.c 2009-01-31 17:36:51.000000000 +0100
***************
*** 0 ****
--- 1,37 ----
+ /* { dg-do run } */
+ /* { dg-options "-fdump-tree-alias" } */
+ /* { dg-skip-if "" { *-*-* } { "-O0" } { "" } } */
+
+ extern void abort (void);
+ struct X {
+ int *p;
+ int *q;
+ int *r;
+ };
+ int __attribute__((noinline))
+ foo(int i, int j, int k, int off)
+ {
+ struct X x;
+ int **p, *q;
+ x.p = &i;
+ x.q = &j;
+ x.r = &k;
+ p = &x.q;
+ p += off;
+ /* *p points to { i, j, k } */
+ q = *p;
+ return *q;
+ }
+ int main()
+ {
+ if (foo(1, 2, 3, -1) != 1)
+ abort ();
+ if (foo(1, 2, 3, 0) != 2)
+ abort ();
+ if (foo(1, 2, 3, 1) != 3)
+ abort ();
+ return 0;
+ }
+
+ /* { dg-final { scan-tree-dump "q_., is dereferenced, points-to vars: { i j k }" "alias" } } */
+ /* { dg-final { cleanup-tree-dump "alias" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/pta-ptrarith-1.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/pta-ptrarith-1.c 2009-01-31 17:36:51.000000000 +0100
***************
*** 0 ****
--- 1,26 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fno-tree-ccp -fdump-tree-alias" } */
+
+ extern void abort (void);
+ struct X {
+ int *p;
+ int *q;
+ int *r;
+ };
+ int __attribute__((noinline))
+ foo(int i, int j, int k, int off)
+ {
+ struct X x;
+ int **p, *q;
+ x.p = &i;
+ x.q = &j;
+ x.r = &k;
+ p = &x.q;
+ p += 1;
+ /* *p points to { k } */
+ q = *p;
+ return *q;
+ }
+
+ /* { dg-final { scan-tree-dump "q_., is dereferenced, points-to vars: { k }" "alias" } } */
+ /* { dg-final { cleanup-tree-dump "alias" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/pta-ptrarith-2.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/pta-ptrarith-2.c 2009-01-31 17:36:51.000000000 +0100
***************
*** 0 ****
--- 1,27 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fno-tree-ccp -fdump-tree-alias" } */
+
+ extern void abort (void);
+ struct X {
+ int *p;
+ int *q;
+ int *r;
+ };
+ int __attribute__((noinline))
+ foo(int i, int j, int k, int off)
+ {
+ struct X x;
+ int **p, *q;
+ x.p = &i;
+ x.q = &j;
+ x.r = &k;
+ p = &x.q;
+ p -= 1;
+ /* *p points to { i } */
+ q = *p;
+ return *q;
+ }
+
+ /* ??? We do not support negative offsets yet. */
+ /* { dg-final { scan-tree-dump "q_., is dereferenced, points-to vars: { i }" "alias" { xfail *-*-* } } } */
+ /* { dg-final { cleanup-tree-dump "alias" } } */
Index: gcc/testsuite/gcc.dg/vect/no-vfa-vect-43.c
===================================================================
*** gcc/testsuite/gcc.dg/vect/no-vfa-vect-43.c.orig 2009-01-31 19:53:30.000000000 +0100
--- gcc/testsuite/gcc.dg/vect/no-vfa-vect-43.c 2009-01-31 19:55:43.000000000 +0100
*************** main1 (float *pa)
*** 28,34 ****
float pb[N] __attribute__ ((__aligned__(16))) = {0,3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54,57};
float pc[N] __attribute__ ((__aligned__(16))) = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
! /* Not vectorizable: pa may alias pb and/or pc, since their addresses escape. */
for (i = 0; i < N; i++)
{
pa[i] = pb[i] * pc[i];
--- 28,35 ----
float pb[N] __attribute__ ((__aligned__(16))) = {0,3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54,57};
float pc[N] __attribute__ ((__aligned__(16))) = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
! /* Vectorizable: pa may not alias pb and/or pc, even though their
! addresses escape. &pa would need to escape to point to escaped memory. */
for (i = 0; i < N; i++)
{
pa[i] = pb[i] * pc[i];
*************** int main (void)
*** 74,79 ****
return 0;
}
! /* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
/* { dg-final { scan-tree-dump-times "Alignment of access forced using versioning" 1 "vect" { target vect_no_align } } } */
/* { dg-final { cleanup-tree-dump "vect" } } */
--- 75,80 ----
return 0;
}
! /* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" } } */
/* { dg-final { scan-tree-dump-times "Alignment of access forced using versioning" 1 "vect" { target vect_no_align } } } */
/* { dg-final { cleanup-tree-dump "vect" } } */