This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH][alias-improvements] Handle unknown offsets in PTA
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: Richard Guenther <rguenther at suse dot de>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Sun, 1 Feb 2009 15:55:30 -0500
- Subject: Re: [PATCH][alias-improvements] Handle unknown offsets in PTA
- References: <alpine.LNX.2.00.0901312000120.5870@zhemvz.fhfr.qr>
On Sat, Jan 31, 2009 at 2:06 PM, Richard Guenther <rguenther@suse.de> wrote:
>
> 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.
>
This is fine, but it may actually be better to make it a separate
constraint type.
The way you have it now will mean less offline optimization.
For example, given two other pointer equivalent variables who have a
constraint with unknown offset, with the below we will not merge them,
when in fact, we could since they will still end up with the same
points-to set.
(This could also be taken care of by special casing UNKNOWN_OFFSET in
offline optimizations)
> 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" } } */
>