[PATCH] Fix and re-enable field-sensitive PTA
Daniel Berlin
dberlin@dberlin.org
Wed Jul 2 16:20:00 GMT 2008
This is fine for me.
On Wed, Jul 2, 2008 at 8:56 AM, Richard Guenther <rguenther@suse.de> wrote:
>
> This patch fixes the call-clobbering code if you enable
> field-sensitive PTA. The issue is that for computing of the
> ESCAPED and the CALLUSED sets we need to compute reachability.
> With field-sensitive PTA this is no longer equivalent to
> transitively closing the PTA solution.
>
> Consider a struct with fields f.a and f.b. With a call foo (&f)
> you end up with the constraint
>
> ESCAPED = &f.a
>
> but foo can also reach f.b through the pointer. The fix is to
> treat all variables as un-split during solving of the
>
> ESCAPED = *ESCAPED
>
> constraint, thus adding all sub-fields to the solution whenever
> at least one sub-field of the variable appears in the solution.
>
> This is what the patch does. It also re-enables field-sensitive PTA
> at -O2 and higher, the behavior being on-par with the 4.3 branch now.
>
> With some followups (or before this dependent on timing) I'll
> shrink the variable_info struct somewhat and reduce the amount of
> uninteresting fields generated, so we might be able to shrink the
> 100 in max-fields-for-field-sensitive somewhat.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for trunk?
>
> Thanks,
> Richard.
>
> 2008-07-02 Richard Guenther <rguenther@suse.de>
>
> * tree-ssa-structalias.c (lookup_vi_for_tree): Declare.
> (do_sd_constraint): Handle a dereference of ESCAPED and CALLUSED
> properly to compute the reachability set if we do field-sensitive
> PTA.
> * invoke.texi (max-fields-for-field-sensitive): Document default.
> * opts.c (decode_options): Set max-fields-for-field-sensitive to
> 100 for optimize >= 2.
>
> * gcc.dg/tree-ssa/pta-callused.c: New testcase.
>
> Index: trunk/gcc/tree-ssa-structalias.c
> ===================================================================
> *** trunk.orig/gcc/tree-ssa-structalias.c 2008-07-02
> 13:24:11.000000000 +0200
> --- trunk/gcc/tree-ssa-structalias.c 2008-07-02 13:32:41.000000000 +0200
> *************** struct variable_info
> *** 262,267 ****
> --- 262,268 ----
> typedef struct variable_info *varinfo_t;
>
> static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
> + static varinfo_t lookup_vi_for_tree (tree);
>
> /* Pool of variable info structures. */
> static alloc_pool variable_info_pool;
> *************** do_sd_constraint (constraint_graph_t gra
> *** 1406,1411 ****
> --- 1407,1453 ----
> goto done;
> }
>
> + /* For x = *ESCAPED and x = *CALLUSED we want to compute the
> + reachability set of the rhs var. As a pointer to a sub-field
> + of a variable can also reach all other fields of the variable
> + we simply have to expand the solution to contain all sub-fields
> + 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 = lookup_vi_for_tree (get_varinfo (j)->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);
> + }
> + }
> +
> /* 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)
> Index: trunk/gcc/doc/invoke.texi
> ===================================================================
> *** trunk.orig/gcc/doc/invoke.texi 2008-07-02 13:24:20.000000000 +0200
> --- trunk/gcc/doc/invoke.texi 2008-07-02 13:25:40.000000000 +0200
> *************** duplicated when threading jumps.
> *** 7323,7329 ****
>
> @item max-fields-for-field-sensitive
> Maximum number of fields in a structure we will treat in
> ! a field sensitive manner during pointer analysis.
>
> @item prefetch-latency
> Estimate on average number of instructions that are executed before
> --- 7323,7330 ----
>
> @item max-fields-for-field-sensitive
> Maximum number of fields in a structure we will treat in
> ! a field sensitive manner during pointer analysis. The default is zero
> ! for -O0, and -O1 and 100 for -Os, -O2, and -O3.
>
> @item prefetch-latency
> Estimate on average number of instructions that are executed before
> Index: trunk/gcc/opts.c
> ===================================================================
> *** trunk.orig/gcc/opts.c 2008-07-02 13:24:11.000000000 +0200
> --- trunk/gcc/opts.c 2008-07-02 13:25:40.000000000 +0200
> *************** decode_options (unsigned int argc, const
> *** 903,908 ****
> --- 903,911 ----
>
> /* Allow more virtual operators to increase alias precision. */
> set_param_value ("max-aliased-vops", 500);
> + + /* Track fields in field-sensitive alias analysis. */
> + set_param_value ("max-fields-for-field-sensitive", 100);
> }
>
> if (optimize >= 3)
> Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/pta-callused.c
> ===================================================================
> *** /dev/null 1970-01-01 00:00:00.000000000 +0000
> --- trunk/gcc/testsuite/gcc.dg/tree-ssa/pta-callused.c 2008-07-02
> 13:25:40.000000000 +0200
> ***************
> *** 0 ****
> --- 1,27 ----
> + /* { dg-do compile } */
> + /* { dg-options "-O2 --param max-fields-for-field-sensitive=2
> -fdump-tree-alias" } */
> + + struct Foo {
> + int *p, *q;
> + };
> + + int foo (int ***x) __attribute__((pure));
> + + int bar (int b)
> + {
> + int i;
> + struct Foo f;
> + int *p, **q;
> + p = &i;
> + f.p = &i;
> + f.q = f.p;
> + if (b)
> + q = &f.p;
> + else
> + q = &f.q;
> + return foo (&q);
> + }
> + + /* { dg-final { scan-tree-dump "CALLUSED = { f f.q i q }" "alias" } } */
> + /* { dg-final { cleanup-tree-dump "alias" } } */
> +
>
More information about the Gcc-patches
mailing list