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

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

[Richard Guenther]

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:

                === g++ tests ===

FAIL: g++.dg/other/PR23205.C scan-assembler .stabs.*foobar:c=i
FAIL: g++.dg/tree-ssa/pr31307.C scan-tree-dump-not optimized "r.dst"
FAIL: g++.old-deja/g++.mike/warn1.C  (test for errors, line 12)
FAIL: g++.old-deja/g++.mike/warn1.C (test for excess errors)

                === gcc tests ===

FAIL: gcc.dg/debug/dwarf2/dwarf-die3.c scan-assembler-not DW_AT_inline
FAIL: gcc.dg/dfp/convert-dfp-round-thread.c execution test
FAIL: gcc.dg/20020425-1.c (test for excess errors)
FAIL: gcc.dg/dse.c scan-tree-dump-times dse1 "Deleted dead store" 2
FAIL: gcc.dg/pr19633.c (test for excess errors)
FAIL: gcc.dg/pr33645-3.c scan-assembler-not var1_t
FAIL: gcc.dg/uninit-B.c uninit i warning (test for warnings, line 12)
FAIL: gcc.dg/uninit-pr19430.c  (test for warnings, line 32)
FAIL: gcc.dg/uninit-pr19430.c uninitialized (test for warnings, line 41)
FAIL: gcc.dg/tree-prof/bb-reorg.c compilation,  -fprofile-use 
-D_PROFILE_USE
FAIL: gcc.dg/tree-prof/pr34999.c compilation,  -fprofile-use 
-D_PROFILE_USE
FAIL: gcc.dg/tree-ssa/20030807-7.c scan-tree-dump-times vrp1 "if " 1
FAIL: gcc.dg/tree-ssa/20031106-4.c scan-tree-dump-times optimized 
"link_error" 0
FAIL: gcc.dg/tree-ssa/alias-1.c scan-tree-dump-times optimized 
"link_error" 0
FAIL: gcc.dg/tree-ssa/alias-15.c scan-tree-dump-times alias "VUSE 
<m_.\\(D\\)>" 2
XPASS: gcc.dg/tree-ssa/alias-18.c scan-tree-dump fre "with 3"
XPASS: gcc.dg/tree-ssa/alias-18.c scan-tree-dump fre "with 8"
FAIL: gcc.dg/tree-ssa/alias-2.c scan-tree-dump-times optimized 
"link_error" 0
FAIL: gcc.dg/tree-ssa/ldist-11.c scan-tree-dump-times ldist "distributed: 
split to 2 loops" 1
FAIL: gcc.dg/tree-ssa/ldist-11.c scan-tree-dump-times ldist "generated 
memset zero" 1
FAIL: gcc.dg/tree-ssa/ldist-12.c scan-tree-dump-times ldist "distributed: 
split to 2 loops" 1
FAIL: gcc.dg/tree-ssa/loadpre8.c scan-tree-dump-times pre "Eliminated: 1" 
1
FAIL: gcc.dg/tree-ssa/loop-36.c scan-tree-dump-not dce2 "c.array"
FAIL: gcc.dg/tree-ssa/pr23382.c scan-tree-dump-times alias "VDEF <HEAP" 1
FAIL: gcc.dg/tree-ssa/pr23455.c scan-tree-dump-times pre "Eliminated: 3" 1
FAIL: gcc.dg/tree-ssa/pr24287.c scan-tree-dump-times optimized 
"link_error" 0
FAIL: gcc.dg/tree-ssa/pr26421.c scan-tree-dump-times alias "VDEF <a_" 2
FAIL: gcc.dg/tree-ssa/pr27799.c (test for excess errors)
FAIL: gcc.dg/tree-ssa/pr35286.c scan-tree-dump-times pre "Eliminated: 2" 1
FAIL: gcc.dg/tree-ssa/predcom-1.c scan-tree-dump-times pcom "looparound 
ref" 1
FAIL: gcc.dg/tree-ssa/ssa-ccp-2.c scan-tree-dump-times optimized 
"link_error" 0
FAIL: gcc.dg/tree-ssa/ssa-dse-6.c scan-tree-dump-times dse1 "local1 = " 1
FAIL: gcc.dg/tree-ssa/ssa-dse-6.c scan-tree-dump-times dse1 "local2 = " 1
FAIL: gcc.dg/tree-ssa/ssa-dse-7.c scan-tree-dump-times dse1 "glob1 = " 1
FAIL: gcc.dg/tree-ssa/ssa-dse-7.c scan-tree-dump-times dse1 "glob2 = " 1
FAIL: gcc.dg/tree-ssa/ssa-fre-14.c scan-tree-dump fre "Inserted .* &a"
FAIL: gcc.dg/tree-ssa/ssa-fre-14.c scan-tree-dump fre "Replaced tmp1.data"
FAIL: gcc.dg/tree-ssa/ssa-fre-15.c scan-tree-dump fre "Replaced"
FAIL: gcc.dg/tree-ssa/structopt-2.c scan-tree-dump-times optimized "a.e" 0
FAIL: gcc.dg/tree-ssa/structopt-2.c scan-tree-dump-times optimized "a.f" 0
FAIL: gcc.dg/tree-ssa/structopt-2.c scan-tree-dump-times optimized "a.g" 0
FAIL: gcc.dg/tree-ssa/structopt-2.c scan-tree-dump-times optimized "b.e" 0
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
FAIL: gcc.dg/vect/vect-62.c scan-tree-dump-times vect "vectorized 1 loops" 
1
FAIL: gcc.dg/vect/vect-67.c scan-tree-dump-times vect "vectorized 1 loops" 
1
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
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
FAIL: gcc.dg/vect/slp-19.c scan-tree-dump-times vect "vectorizing stmts 
using SLP" 3
FAIL: gcc.dg/vect/no-vfa-vect-43.c scan-tree-dump-times vect "vectorized 1 
loops" 1
FAIL: gcc.dg/vect/no-scevccp-outer-13.c scan-tree-dump-times vect "OUTER 
LOOP VECTORIZED." 1
FAIL: gcc.dg/vect/no-scevccp-outer-6.c scan-tree-dump-times vect "OUTER 
LOOP VECTORIZED." 1
FAIL: gcc.dg/vect/no-scevccp-outer-7.c scan-tree-dump-times vect "OUTER 
LOOP VECTORIZED." 1
FAIL: gcc.target/i386/pr34256.c scan-assembler-times mov 2

                === gfortran tests ===

FAIL: gfortran.dg/ldist-1.f90  -O  scan-tree-dump-times ldist 
"distributed: split to 4 loops" 1
FAIL: gfortran.dg/reassoc_4.f  -O  scan-tree-dump-times reassoc1 "[0-9] 
\\* " 22
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


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

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

[Dorit Nuzman]

...
> 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
> FAIL: gcc.dg/vect/vect-62.c scan-tree-dump-times vect "vectorized 1
loops"
> 1
> FAIL: gcc.dg/vect/vect-67.c scan-tree-dump-times vect "vectorized 1
loops"
> 1
> 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
> 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
> FAIL: gcc.dg/vect/slp-19.c scan-tree-dump-times vect "vectorizing stmts
> using SLP" 3
> FAIL: gcc.dg/vect/no-vfa-vect-43.c scan-tree-dump-times vect "vectorized
1
> loops" 1
> FAIL: gcc.dg/vect/no-scevccp-outer-13.c scan-tree-dump-times vect "OUTER
> LOOP VECTORIZED." 1
> FAIL: gcc.dg/vect/no-scevccp-outer-6.c scan-tree-dump-times vect "OUTER
> LOOP VECTORIZED." 1
> FAIL: gcc.dg/vect/no-scevccp-outer-7.c scan-tree-dump-times vect "OUTER
> LOOP VECTORIZED." 1
> FAIL: gcc.target/i386/pr34256.c scan-assembler-times mov 2
>
>                 === gfortran tests ===
>
...
> 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
>
>
> 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.
>

three of the vectorizer testcase FAILs above occur also on the trunk
(vect-67.c, no-scevccp-outer-7.c, no-scevccp-outer-13.c: these three are
due to the PRE changes from a couple months ago, see
http://gcc.gnu.org/ml/gcc-patches/2008-07/msg01638.html).

The rest - I'll have a look,

dorit

> 1

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

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

[Dorit Nuzman]

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

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

[Diego Novillo]

On Fri, Sep 19, 2008 at 07:51, Richard Guenther <rguenther@suse.de> wrote:

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


I don't disagree with this, but if we are going to force all the
memory optimizers to use the alias oracle for disambiguating, then all
of the memory partitioning code can be removed.  Also, a good chunk of
the operand scanning can be removed as well.

One consequence of having a single, universal VOP is that the memory
SSA web will be extremely dense.  Could this be a performance problem
for the oracle?  A single VOP is merely a marker that says whether a
statement makes a memory reference, for that we don't need VOPs,
calling gimple_references_memory_p() would be enough for that.

Another consequence is that now the memory SSA web is so useless that
optimizers dealing with memory have no choice but to consult the
oracle.  This could be a good thing, though one of the goals of the
mem-ssa web was to provide not-horrible defaults for passes that
didn't want to be bothered with being too precise.

Maybe we could default the memory partitioning to something like
type-based partitioning?  This gives you a sparser mem-ssa web, very
few virtual operands and maybe it makes the job of the oracle easier,
by providing more entry points.

If having a sparser memory SSA web doesn't help the alias oracle, then
none of this matters, of course.


Diego.

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

[Richard Guenther]

On Tue, 23 Sep 2008, Diego Novillo wrote:

> On Fri, Sep 19, 2008 at 07:51, Richard Guenther <rguenther@suse.de> wrote:
> 
> > 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.
> 
> 
> I don't disagree with this, but if we are going to force all the
> memory optimizers to use the alias oracle for disambiguating, then all
> of the memory partitioning code can be removed.  Also, a good chunk of
> the operand scanning can be removed as well.

Yes.

> One consequence of having a single, universal VOP is that the memory
> SSA web will be extremely dense.  Could this be a performance problem
> for the oracle?  A single VOP is merely a marker that says whether a
> statement makes a memory reference, for that we don't need VOPs,
> calling gimple_references_memory_p() would be enough for that.

With the memory SSA web we can still walk statements with memory access
efficiently.  Of course the alias oracle needs to do some caching both
for walks and alias queries.  I want to do this on the branch as well.

> Another consequence is that now the memory SSA web is so useless that
> optimizers dealing with memory have no choice but to consult the
> oracle.  This could be a good thing, though one of the goals of the
> mem-ssa web was to provide not-horrible defaults for passes that
> didn't want to be bothered with being too precise.

Sure.  But the one unfixable problem with the current scheme is that
we have to be able to build VOPs by looking at a single statement only.
This makes a lean and still reasonable precise SSA web impossible
mainly due to the fact that we have to over-represent the necessary
conflicts.

> Maybe we could default the memory partitioning to something like
> type-based partitioning?  This gives you a sparser mem-ssa web, very
> few virtual operands and maybe it makes the job of the oracle easier,
> by providing more entry points.

It doesn't work.  For example reasonable precise would be to use a
single tag for all pointers and the variables tag for plain accesses.
Still this gives you all type-aliased virtual operands on the pointer
accesses.  If we would build the VOP SSA web at alias computation time
we could in theory prune it down to just contain the minimal necessary
edges to represent all conflicts - but this breaks down once you
update a statement and re-build operands just for this statement.

> If having a sparser memory SSA web doesn't help the alias oracle, then
> none of this matters, of course.

Well, it matters if we do not convert existing passes to use the oracle.
IMHO the current benefits of the memory SSA web simply doesn't outweight
its cost.

Richard.

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

[Dorit Nuzman]

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

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

[Richard Guenther]

Thanks Dorit for all the analysis work!  I have created a meta-bug
to track PRs blocking the alias-improvements branch, PR37696.

Richard.