passes.texi: Document predictive commoning.

	* doc/passes.texi: Document predictive commoning.
	* doc/invoke.texi (-fpredictive-commoning): Document.
	* opts.c (decode_options): Enable flag_predictive_commoning on -O3.
	* tree-ssa-loop-im.c (get_lsm_tmp_name): Export.  Allow
	adding indices to the generated name.
	(schedule_sm): Pass 0 to get_lsm_tmp_name.
	* tree-ssa-loop-niter.c (stmt_dominates_stmt_p): Export.
	* tree-pretty-print.c (op_symbol_1): Renamed to ...
	(op_symbol_code): ... and exported.
	(dump_omp_clause, op_symbol): Use op_symbol_code
	instead of op_symbol_1.
	* tree-pass.h (pass_predcom): Declare.
	* timevar.def (TV_PREDCOM): New timevar.
	* tree-ssa-loop.c (run_tree_predictive_commoning,
	gate_tree_predictive_commoning, pass_predcom): New.
	* tree-data-ref.c (find_data_references_in_loop): Find the
	references in dominance order.
	(canonicalize_base_object_address): Ensure that the result has
	pointer type.
	(dr_analyze_innermost): Export.
	(create_data_ref): Code to fail for references with invariant
	address moved ...
	(find_data_references_in_stmt): ... here.
	* tree-data-ref.h (dr_analyze_innermost): Declare.
	* tree-affine.c: Include tree-gimple.h and hashtab.h.
	(aff_combination_find_elt, name_expansion_hash,
	name_expansion_eq, tree_to_aff_combination_expand,
	double_int_constant_multiple_p, aff_combination_constant_multiple_p):
	New functions.
	* tree-affine.h (aff_combination_constant_multiple_p,
	tree_to_aff_combination_expand): Declare.
	* tree-predcom.c: New file.
	* common.opt (fpredictive-commoning): New option.
	* tree-flow.h (op_symbol_code, tree_predictive_commoning,
	stmt_dominates_stmt_p, get_lsm_tmp_name): Declare.
	* Makefile.in (tree-predcom.o): Add.
	(tree-affine.o): Add TREE_GIMPLE_H dependency.
	* passes.c (init_optimization_passes):  Add dceloop after
	copy propagation in loop optimizer.  Add predictive commoning
	to loop optimizer passes.

	* gcc.dg/tree-ssa/predcom-1.c: New test.
	* gcc.dg/tree-ssa/predcom-2.c: New test.
	* gcc.dg/tree-ssa/predcom-3.c: New test.
	* gcc.dg/tree-ssa/predcom-4.c: New test.
	* gcc.dg/tree-ssa/predcom-5.c: New test.
	* gcc.dg/vect/dump-tree-dceloop-pr26359.c: Test dceloop2 dumps.

From-SVN: r125030

2 files changed, 22 insertions, 2 deletions

diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 47b68d7..023cf72 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -334,7 +334,7 @@ Objective-C and Objective-C++ Dialects}.
 -ffinite-math-only  -fno-signed-zeros @gol
 -fno-toplevel-reorder -fno-trapping-math  -fno-zero-initialized-in-bss @gol
 -fomit-frame-pointer  -foptimize-register-move @gol
--foptimize-sibling-calls  -fprefetch-loop-arrays @gol
+-foptimize-sibling-calls  -fpredictive-commoning -fprefetch-loop-arrays @gol
 -fprofile-generate -fprofile-use @gol
 -fregmove  -frename-registers @gol
 -freorder-blocks  -freorder-blocks-and-partition -freorder-functions @gol
@@ -5001,7 +5001,8 @@ invoking @option{-O2} on programs that use computed gotos.
 @opindex O3
 Optimize yet more.  @option{-O3} turns on all optimizations specified by
 @option{-O2} and also turns on the @option{-finline-functions},
-@option{-funswitch-loops} and @option{-fgcse-after-reload} options.
+@option{-funswitch-loops}, @option{-fpredictive-commoning} and
+@option{-fgcse-after-reload} options.
 
 @item -O0
 @opindex O0
@@ -5712,6 +5713,14 @@ This optimization is enabled by default.
 With this option, the compiler will create multiple copies of some
 local variables when unrolling a loop which can result in superior code.
 
+@item -fpredictive-commoning
+@opindex fpredictive-commoning
+Perform predictive commoning optimization, i.e., reusing computations
+(especially memory loads and stores) performed in previous
+iterations of loops.
+
+This option is enabled at level @option{-O3}.
+
 @item -fprefetch-loop-arrays
 @opindex fprefetch-loop-arrays
 If supported by the target machine, generate instructions to prefetch
diff --git a/gcc/doc/passes.texi b/gcc/doc/passes.texi
index 5c44999..b4eef60 100644
--- a/gcc/doc/passes.texi
+++ b/gcc/doc/passes.texi
@@ -602,6 +602,17 @@ This pass completely unrolls loops with few iterations.  The pass
 is located in @file{tree-ssa-loop-ivcanon.c} and described by
 @code{pass_complete_unroll}.
 
+@item Predictive commoning
+
+This pass makes the code reuse the computations from the previous
+iterations of the loops, especially loads and stores to memory.
+It does so by storing the values of these computations to a bank
+of temporary variables that are rotated at the end of loop.  To avoid
+the need for this rotation, the loop is then unrolled and the copies
+of the loop body are rewritten to use the appropriate version of
+the temporary variable.  This pass is located in @file{tree-predcom.c}
+and described by @code{pass_predcom}.
+
 @item Array prefetching
 
 This pass issues prefetch instructions for array references inside