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



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@125030 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 211 insertions, 0 deletions

diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c
index 43b251ddd90..87f379c8003 100644
--- a/gcc/tree-affine.c
+++ b/gcc/tree-affine.c
@@ -29,7 +29,9 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "output.h"
 #include "diagnostic.h"
 #include "tree-dump.h"
+#include "pointer-set.h"
 #include "tree-affine.h"
+#include "tree-gimple.h"
 
 /* Extends CST as appropriate for the affine combinations COMB.  */
 
@@ -493,3 +495,212 @@ aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
     aff_combination_add_product (c1, double_int_one, c2->rest, r);
   aff_combination_add_product (c1, c2->offset, NULL, r);
 }
+
+/* Returns the element of COMB whose value is VAL, or NULL if no such
+   element exists.  If IDX is not NULL, it is set to the index of VAL in
+   COMB.  */
+	      
+static struct aff_comb_elt *
+aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx)
+{
+  unsigned i;
+
+  for (i = 0; i < comb->n; i++)
+    if (operand_equal_p (comb->elts[i].val, val, 0))
+      {
+	if (idx)
+	  *idx = i;
+
+	return &comb->elts[i];
+      }
+
+  return NULL;
+}
+
+/* Element of the cache that maps ssa name NAME to its expanded form
+   as an affine expression EXPANSION.  */
+
+struct name_expansion
+{
+  aff_tree expansion;
+
+  /* True if the expansion for the name is just being generated.  */
+  unsigned in_progress : 1;
+};
+
+/* Similar to tree_to_aff_combination, but follows SSA name definitions
+   and expands them recursively.  CACHE is used to cache the expansions
+   of the ssa names, to avoid exponential time complexity for cases
+   like
+ 
+   a1 = a0 + a0;
+   a2 = a1 + a1;
+   a3 = a2 + a2;
+   ...  */
+
+void
+tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
+				struct pointer_map_t **cache)
+{
+  unsigned i;
+  aff_tree to_add, current, curre;
+  tree e, def, rhs;
+  double_int scale;
+  void **slot;
+  struct name_expansion *exp;
+
+  tree_to_aff_combination (expr, type, comb);
+  aff_combination_zero (&to_add, type);
+  for (i = 0; i < comb->n; i++)
+    {
+      e = comb->elts[i].val;
+      if (TREE_CODE (e) != SSA_NAME)
+	continue;
+      def = SSA_NAME_DEF_STMT (e);
+      if (TREE_CODE (def) != GIMPLE_MODIFY_STMT
+	  || GIMPLE_STMT_OPERAND (def, 0) != e)
+	continue;
+
+      rhs = GIMPLE_STMT_OPERAND (def, 1);
+      if (TREE_CODE (rhs) != SSA_NAME
+	  && !EXPR_P (rhs)
+	  && !is_gimple_min_invariant (rhs))
+	continue;
+
+      /* We do not know whether the reference retains its value at the
+	 place where the expansion is used.  */
+      if (REFERENCE_CLASS_P (rhs))
+	continue;
+
+      if (!*cache)
+	*cache = pointer_map_create ();
+      slot = pointer_map_insert (*cache, e);
+      exp = *slot;
+
+      if (!exp)
+	{
+	  exp = XNEW (struct name_expansion);
+	  exp->in_progress = 1;
+	  *slot = exp;
+	  tree_to_aff_combination_expand (rhs, type, &current, cache);
+	  exp->expansion = current;
+	  exp->in_progress = 0;
+	}
+      else
+	{
+	  /* Since we follow the definitions in the SSA form, we should not
+	     enter a cycle unless we pass through a phi node.  */
+	  gcc_assert (!exp->in_progress);
+	  current = exp->expansion;
+	}
+
+      /* Accumulate the new terms to TO_ADD, so that we do not modify
+	 COMB while traversing it; include the term -coef * E, to remove
+         it from COMB.  */
+      scale = comb->elts[i].coef;
+      aff_combination_zero (&curre, type);
+      aff_combination_add_elt (&curre, e, double_int_neg (scale));
+      aff_combination_scale (&current, scale);
+      aff_combination_add (&to_add, &current);
+      aff_combination_add (&to_add, &curre);
+    }
+  aff_combination_add (comb, &to_add);
+}
+
+/* Frees memory occupied by struct name_expansion in *VALUE.  Callback for
+   pointer_map_traverse.  */
+
+static bool
+free_name_expansion (void *key ATTRIBUTE_UNUSED, void **value,
+		     void *data ATTRIBUTE_UNUSED)
+{
+  struct name_expansion *exp = *value;
+
+  free (exp);
+  return true;
+}
+
+/* Frees memory allocated for the CACHE used by
+   tree_to_aff_combination_expand.  */
+
+void
+free_affine_expand_cache (struct pointer_map_t **cache)
+{
+  if (!*cache)
+    return;
+
+  pointer_map_traverse (*cache, free_name_expansion, NULL);
+  pointer_map_destroy (*cache);
+  *cache = NULL;
+}
+
+/* If VAL != CST * DIV for any constant CST, returns false.
+   Otherwise, if VAL != 0 (and hence CST != 0), and *MULT_SET is true,
+   additionally compares CST and MULT, and if they are different,
+   returns false.  Finally, if neither of these two cases occcur,
+   true is returned, and if CST != 0, CST is stored to MULT and
+   MULT_SET is set to true.  */
+
+static bool
+double_int_constant_multiple_p (double_int val, double_int div,
+				bool *mult_set, double_int *mult)
+{
+  double_int rem, cst;
+
+  if (double_int_zero_p (val))
+    return true;
+
+  if (double_int_zero_p (div))
+    return false;
+
+  cst = double_int_sdivmod (val, div, FLOOR_DIV_EXPR, &rem);
+  if (!double_int_zero_p (rem))
+    return false;
+
+  if (*mult_set && !double_int_equal_p (*mult, cst))
+    return false;
+
+  *mult_set = true;
+  *mult = cst;
+  return true;
+}
+
+/* Returns true if VAL = X * DIV for some constant X.  If this is the case,
+   X is stored to MULT.  */
+
+bool
+aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
+				     double_int *mult)
+{
+  bool mult_set = false;
+  unsigned i;
+
+  if (val->n == 0 && double_int_zero_p (val->offset))
+    {
+      *mult = double_int_zero;
+      return true;
+    }
+  if (val->n != div->n)
+    return false;
+
+  if (val->rest || div->rest)
+    return false;
+
+  if (!double_int_constant_multiple_p (val->offset, div->offset,
+				       &mult_set, mult))
+    return false;
+
+  for (i = 0; i < div->n; i++)
+    {
+      struct aff_comb_elt *elt
+	      = aff_combination_find_elt (val, div->elts[i].val, NULL);
+      if (!elt)
+	return false;
+      if (!double_int_constant_multiple_p (elt->coef, div->elts[i].coef,
+					   &mult_set, mult))
+	return false;
+    }
+
+  gcc_assert (mult_set);
+  return true;
+}