This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH][alias] Reduce virtual operands to a single one


> >
> > 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.
> "
>

this is new PR37695.

> > 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).
>
>

this is new PR37698 (there are other occurences of non-empty latch-block
preventing vectorization, unrelated to alias branch, e.g. PR28643 and
PR33447)

> > 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.
>

this is new PR37699.

>
> > 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).
>

this is new PR37694.

>
> > 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;
> "
>

this is new PR37700.

> > 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.
>
>

this is also included in PR37699

> > 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).
>

this also falls into PR37694.

>
> > 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

In all of the above we can't tell that subroutine arguments don't alias.
e.g., X,Y in "SUBROUTINE SAXPY(X,Y,A)".
As a result the vectorizer applies loop-versioning with runtime aliasing
test, which also means it will handle misalignment using versioning instead
of peeling:
"
versioning for alias required: can't determine dependence between (*x_32
(D))[D.1518_28] and (*y_29(D))[D.1518_28]
vect-3.f90:6: note: mark for run-time aliasing test between (*x_32
(D))[D.1518_28] and (*y_29(D))[D.1518_28]
...
vect-3.f90:6: note: Alignment of access forced using versioning.
vect-3.f90:6: note: Versioning for alignment will be applied.
"

This is new PR37692.


> > 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
> >

On the alias branch can't prove that number of iteratios is non zero:

Analyzing # of iterations of loop 1
  exit condition [2, + , 1](no_overflow) < D.1554_60
  bounds on difference of bases: -2147483650 ... 2147483645
  result:
    zero if D.1554_60 <= 1
    # of iterations (character(kind=4)) D.1554_60 + 0x0fffffffe, bounded by
2147483645
  (set_nb_iterations_in_loop = scev_not_known))
(get_loop_exit_condition
  if (D.1554_60 <= S.10_78)
)

pr32377.f90:9: note: not vectorized: number of iterations cannot be
computed.
pr32377.f90:9: note: bad loop form.:
pr32377.f90:4: note: vectorized 0 loops in function.

Using mainline we have:

Analyzing # of iterations of loop 1
  exit condition [2, + , 1](no_overflow) < D.1416_112
  bounds on difference of bases: 0 ... 2147483645
  result:
    # of iterations (character(kind=4)) D.1416_112 + 0x0fffffffe, bounded
by 2147483645
  (set_nb_iterations_in_loop = (character(kind=4)) D.1416_112 +
0x0fffffffe))

pr32377.f90:9: note: ==> get_loop_niters:(character(kind=4)) D.1416_112 +
0x0ffffffff(get_loop_exit_condition
  if (S.10_78 >= D.1416_112)
)

pr32377.f90:9: note: Symbolic number of iterations is (character(kind=4))
D.1416_112 + 0x0ffffffff

This is new PR37693.


HTH,
dorit


>
> 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");
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]