[PATCH][alias] Reduce virtual operands to a single one
Dorit Nuzman
DORIT@il.ibm.com
Sun Sep 21 15:15:00 GMT 2008
>
> This initial patch changes the representation of memory conflicts in
> the gimple IL to a single virtual operand symbol per function.
>
> With this we can simplify the data structures used for keeping track
> of virtual defs/uses. We can also simplify the operand scanner a lot
> and can get rid of all non-points-to work during alias computation.
>
> The downside is that this patch exposes existing weakness in our
> optimizers more, as if we would have partitioned all symbols into
> a single set. This makes the following testcases fail on the branch
> for now:
...
> FAIL: gcc.dg/vect/vect-42.c scan-tree-dump-times vect "Vectorizing an
> unaligned access" 2
> FAIL: gcc.dg/vect/vect-42.c scan-tree-dump-times vect "Alignment of
access
> forced using peeling" 1
In this testcase we can't tell that a write through a restrict pointer
(which is a function argument) does not overlap with reads from local
arrays. As a result we vectorize using loop-versioning controled by a
run-time aliasing test. This in turn forces us to handle misalignment using
loop-versioning (rather than peeling, cause right now we don't support
peeling combined with versioning, and these are the only ways we currently
support misaligned stores). Without the aliasing problem, the loop is
vectorized using peeling to align the store.
"
=== vect_analyze_dependences ===
vect-42.c:36: note: versioning for alias required: can't determine
dependence between pb[i_59] and *D.2074_6
vect-42.c:36: note: mark for run-time aliasing test between pb[i_59] and
*D.2074_6
vect-42.c:36: note: versioning for alias required: can't determine
dependence between pc[i_59] and *D.2074_6
vect-42.c:36: note: mark for run-time aliasing test between pc[i_59] and
*D.2074_6
...
vect-42.c:36: note: === vect_enhance_data_refs_alignment ===
vect-42.c:36: note: Unknown misalignment, is_packed = 0
vect-42.c:36: note: Alignment of access forced using versioning.
vect-42.c:36: note: Versioning for alignment will be applied.
"
> FAIL: gcc.dg/vect/vect-62.c scan-tree-dump-times vect "vectorized 1
loops"
> 1
looks like on the branch pre is more powerful, as it moves the load into
the latch block; as a result the latch block is not empty, and we fail to
vectorize (with -fno-tree-pre vectorization succeeds).
> FAIL: gcc.dg/vect/vect-67.c scan-tree-dump-times vect "vectorized 1
loops"
> 1
unrelated to aliasing, occurs also on mainline (see
http://gcc.gnu.org/ml/gcc-patches/2008-07/msg01638.html)
> FAIL: gcc.dg/vect/vect-96.c scan-tree-dump-times vect "Vectorizing an
> unaligned access" 1
> FAIL: gcc.dg/vect/vect-96.c scan-tree-dump-times vect "Alignment of
access
> forced using peeling" 1).
we can't distinguish between a write through a (local) pointer to a global
array (which is a field in a struct), and a read from a local array. the
result is like vect-42.c.
> FAIL: gcc.dg/vect/vect-multitypes-6.c scan-tree-dump-times vect
> "vectorized 1 loops" 1
> FAIL: gcc.dg/vect/vect-multitypes-6.c scan-tree-dump-times vect
> "Vectorizing an unaligned access" 6
We can't tell that writes to local arrays do no overlap with reads through
(restrict) pointers (which are function arguments). As a result we try to
vectorize using loop-versioning controled by a run-time aliasing test,
however there are too many checks required, so we bail out:
"
=== vect_prune_runtime_alias_test_list ===
vect-multitypes-6.c:34: note: disable versioning for alias - max number of
generated checks exceeded.
vect-multitypes-6.c:34: note: too long list of versioning for alias
run-time tests.
"
(with --param vect-max-version-for-alias-checks=20 we do vectorize the
loop).
> FAIL: gcc.dg/vect/slp-19.c scan-tree-dump-times vect "vectorizing stmts
> using SLP" 3
The problem is with the loop at line 17: with trunk we detect that one of
the elements of array 'in' is read twice, so we generate overall 8 loads
(reusing one of them). On the alias branch we do not eliminate the extra
load. All the reads and write are from/to local arrays, by the way. This
results in 9 loads, which the vectorizer interperts as a complicated SLP
permutation, so instead it is vectorized across iterations rather than
using SLP:
"
slp-19.c:17: note: Load permutation 0 1 2 4 5 6 7 8
slp-19.c:17: note: Build SLP failed: unsupported load permutation out
[D.2646_11] = D.2647_12;
"
> FAIL: gcc.dg/vect/no-vfa-vect-43.c scan-tree-dump-times vect "vectorized
1
> loops" 1
we can't tell that reads through a pointer (which is a function argument)
do not overlap with a write to a local array. As a result we try to
vectorize the loop using loop-versioning controled by a run-time aliasing
test, however this testcase doe not allow that (--param
vect-max-version-for-alias-checks=0), so vectorization fails.
> FAIL: gcc.dg/vect/no-scevccp-outer-13.c scan-tree-dump-times vect "OUTER
> LOOP VECTORIZED." 1
unrelated to aliasing, occurs also on mainline (see
http://gcc.gnu.org/ml/gcc-patches/2008-07/msg01638.html)
> FAIL: gcc.dg/vect/no-scevccp-outer-6.c scan-tree-dump-times vect "OUTER
> LOOP VECTORIZED." 1
we can't tell that a read through a (restrict) pointer (which is a function
argument) does not overlap with write to a local arrays. As a result we try
to vectorize the outer-loop using loop-versioning controled by a run-time
aliasing test, however this capability is not yet supported for outer-loops
(the inner loop does get vectorized).
> FAIL: gcc.dg/vect/no-scevccp-outer-7.c scan-tree-dump-times vect "OUTER
> LOOP VECTORIZED." 1
unrelated to aliasing, occurs also on mainline (see
http://gcc.gnu.org/ml/gcc-patches/2008-07/msg01638.html)
I'll go ahead and open PRs for these as requested,
> FAIL: gfortran.dg/vect/vect-2.f90 -O scan-tree-dump-times vect
> "Alignment of access forced using peeling" 3
> FAIL: gfortran.dg/vect/vect-3.f90 -O scan-tree-dump-times vect
> "Alignment of access forced using peeling" 1
> FAIL: gfortran.dg/vect/vect-3.f90 -O scan-tree-dump-times vect
> "Vectorizing an unaligned access" 1
> FAIL: gfortran.dg/vect/vect-4.f90 -O scan-tree-dump-times vect
> "Alignment of access forced using peeling" 1
> FAIL: gfortran.dg/vect/vect-4.f90 -O scan-tree-dump-times vect
> "Vectorizing an unaligned access" 1
> FAIL: gfortran.dg/vect/pr32377.f90 -O scan-tree-dump-times vect
> "vectorized 2 loops" 1
> FAIL: gfortran.dg/vect/no-vfa-pr32377.f90 scan-tree-dump-times vect
> "vectorized 2 loops" 1
>
I have yet to check the fortran failures,
dorit
>
> which is not too bad.
>
> The plan is to delay the cleanup parts to ease merging and to concentrate
> on the individual optimizer problems. Help is appreciated here, even
> if it is just analyzing the above fails - I'd suggest to file bugreports
> about the issues as they are latent on the trunk.
>
> Bootstrapped on x86_64-unknown-linux-gnu, installed on the branch.
>
> Thanks,
> Richard.
>
> 2008-09-19 Richard Guenther <rguenther@suse.de>
>
> * tree-flow.h (struct gimple_df): New member vop.
> * tree-flow-inline.h (gimple_vop): New function.
> * tree-ssa-alias.c (create_vop_var): New function.
> (compute_may_aliases): Call it.
> * tree-ssa-operands.c (append_vdef): Always append
> the single gimple vop.
> (append_vuse): Likewise.
> * tree-ssa.c (verify_ssa_name): Verify all VOPs are
> based on the single gimple vop.
>
> Index: alias-improvements/gcc/tree-flow-inline.h
> ===================================================================
> *** alias-improvements.orig/gcc/tree-flow-inline.h 2008-09-18 17:
> 08:00.000000000 +0200
> --- alias-improvements/gcc/tree-flow-inline.h 2008-09-18 17:28:48.
> 000000000 +0200
> *************** gimple_nonlocal_all (const struct functi
> *** 101,106 ****
> --- 101,114 ----
> return fun->gimple_df->nonlocal_all;
> }
>
> + /* Artificial variable used for the virtual operand FUD chain. */
> + static inline tree
> + gimple_vop (const struct function *fun)
> + {
> + gcc_assert (fun && fun->gimple_df);
> + return fun->gimple_df->vop;
> + }
> +
> /* Initialize the hashtable iterator HTI to point to hashtable TABLE */
>
> static inline void *
> Index: alias-improvements/gcc/tree-flow.h
> ===================================================================
> *** alias-improvements.orig/gcc/tree-flow.h 2008-09-18 17:08:00.
> 000000000 +0200
> --- alias-improvements/gcc/tree-flow.h 2008-09-18 17:29:01.000000000
+0200
> *************** struct gimple_df GTY(())
> *** 151,156 ****
> --- 151,159 ----
> /* Array of all SSA_NAMEs used in the function. */
> VEC(tree,gc) *ssa_names;
>
> + /* Artificial variable used for the virtual operand FUD chain. */
> + tree vop;
> +
> /* Artificial variable used to model the effects of function calls.
*/
> tree global_var;
>
> Index: alias-improvements/gcc/tree-ssa-alias.c
> ===================================================================
> *** alias-improvements.orig/gcc/tree-ssa-alias.c 2008-09-18 17:08:
> 00.000000000 +0200
> --- alias-improvements/gcc/tree-ssa-alias.c 2008-09-18 17:32:32.
> 000000000 +0200
> *************** static void setup_pointers_and_addressab
> *** 242,247 ****
> --- 242,248 ----
> static void update_alias_info (struct alias_info *);
> static void create_global_var (void);
> static void maybe_create_global_var (void);
> + static void create_vop_var (void);
> static void set_pt_anything (tree);
>
> void debug_mp_info (VEC(mem_sym_stats_t,heap) *);
> *************** compute_may_aliases (void)
> *** 1748,1753 ****
> --- 1749,1757 ----
>
> memset (&alias_stats, 0, sizeof (alias_stats));
>
> + if (!gimple_vop (cfun))
> + create_vop_var ();
> +
> /* Initialize aliasing information. */
> ai = init_alias_info ();
>
> *************** create_global_var (void)
> *** 3386,3391 ****
> --- 3390,3420 ----
> }
>
>
> + /* Create the VOP variable, an artificial global variable to act as a
> + representative of all of the virtual operands FUD chain. */
> +
> + static void
> + create_vop_var (void)
> + {
> + tree global_var = build_decl (VAR_DECL, get_identifier (".MEM"),
> + void_type_node);
> + DECL_ARTIFICIAL (global_var) = 1;
> + TREE_READONLY (global_var) = 0;
> + DECL_EXTERNAL (global_var) = 1;
> + TREE_STATIC (global_var) = 1;
> + TREE_USED (global_var) = 1;
> + DECL_CONTEXT (global_var) = NULL_TREE;
> + TREE_THIS_VOLATILE (global_var) = 0;
> + TREE_ADDRESSABLE (global_var) = 0;
> +
> + create_var_ann (global_var);
> + mark_call_clobbered (global_var, ESCAPE_UNKNOWN);
> + add_referenced_var (global_var);
> + mark_sym_for_renaming (global_var);
> + cfun->gimple_df->vop = global_var;
> + }
> +
> +
> /* Dump alias statistics on FILE. */
>
> static void
> Index: alias-improvements/gcc/tree-ssa-operands.c
> ===================================================================
> *** alias-improvements.orig/gcc/tree-ssa-operands.c 2008-09-18 17:
> 08:00.000000000 +0200
> --- alias-improvements/gcc/tree-ssa-operands.c 2008-09-18 18:06:
> 54.000000000 +0200
> *************** append_use (tree *use_p)
> *** 1097,1104 ****
> static inline void
> append_vdef (tree var)
> {
> ! tree sym;
>
> if (TREE_CODE (var) != SSA_NAME)
> {
> tree mpt;
> --- 1097,1120 ----
> static inline void
> append_vdef (tree var)
> {
> ! tree vop = gimple_vop (cfun);
> ! var_ann_t ann;
>
> + if (TREE_CODE (var) == VAR_DECL
> + || TREE_CODE (var) == PARM_DECL
> + || TREE_CODE (var) == RESULT_DECL)
> + bitmap_set_bit (build_stores, DECL_UID (var));
> +
> + if (!vop)
> + return;
> + ann = var_ann (vop);
> + if (ann->in_vdef_list)
> + return;
> + ann->in_vdef_list = true;
> + VEC_safe_push (tree, heap, build_vdefs, vop);
> + /* ??? Necessary? */
> + bitmap_set_bit (build_stores, DECL_UID (vop));
> + #if 0
> if (TREE_CODE (var) != SSA_NAME)
> {
> tree mpt;
> *************** append_vdef (tree var)
> *** 1122,1127 ****
> --- 1138,1144 ----
>
> VEC_safe_push (tree, heap, build_vdefs, var);
> bitmap_set_bit (build_stores, DECL_UID (sym));
> + #endif
> }
>
>
> *************** append_vdef (tree var)
> *** 1130,1135 ****
> --- 1147,1173 ----
> static inline void
> append_vuse (tree var)
> {
> + tree vop = gimple_vop (cfun);
> + var_ann_t ann;
> +
> + if (TREE_CODE (var) == VAR_DECL
> + || TREE_CODE (var) == PARM_DECL
> + || TREE_CODE (var) == RESULT_DECL)
> + bitmap_set_bit (build_loads, DECL_UID (var));
> +
> + if (!vop)
> + return;
> + ann = var_ann (vop);
> + if (ann->in_vuse_list)
> + return;
> + if (!ann->in_vdef_list)
> + {
> + ann->in_vuse_list = true;
> + VEC_safe_push (tree, heap, build_vuses, vop);
> + }
> + /* ??? Necessary? */
> + bitmap_set_bit (build_loads, DECL_UID (vop));
> + #if 0
> tree sym;
>
> if (TREE_CODE (var) != SSA_NAME)
> *************** append_vuse (tree var)
> *** 1162,1167 ****
> --- 1200,1206 ----
>
> VEC_safe_push (tree, heap, build_vuses, var);
> bitmap_set_bit (build_loads, DECL_UID (sym));
> + #endif
> }
>
>
> Index: alias-improvements/gcc/tree-ssa.c
> ===================================================================
> *** alias-improvements.orig/gcc/tree-ssa.c 2008-09-18 17:08:00.
> 000000000 +0200
> --- alias-improvements/gcc/tree-ssa.c 2008-09-19 11:40:00.000000000
+0200
> *************** verify_ssa_name (tree ssa_name, bool is_
> *** 271,276 ****
> --- 271,282 ----
> return true;
> }
>
> + if (is_virtual && SSA_NAME_VAR (ssa_name) != gimple_vop (cfun))
> + {
> + error ("virtual SSA name for non-VOP decl");
> + return true;
> + }
> +
> if (!is_virtual && !is_gimple_reg (ssa_name))
> {
> error ("found a real definition for a non-register");
More information about the Gcc-patches
mailing list