re PR tree-optimization/87985 (Compile-time and memory hog w/ -O1 -ftree-slp-vectorize)

2018-11-14  Richard Biener  <rguenther@suse.de>

	PR middle-end/87985
	* tree-data-ref.c (split_constant_offset): Add wrapper
	allocating a cache hash-map.
	(split_constant_offset_1): Cache results of expanding
	expressions from SSA def stmts.

	* gcc.dg/pr87985.c: New testcase.

From-SVN: r266147

1 files changed, 63 insertions, 19 deletions

diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index e8e68d7..1fe3236 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -95,10 +95,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-affine.h"
 #include "params.h"
 #include "builtins.h"
-#include "stringpool.h"
-#include "tree-vrp.h"
-#include "tree-ssanames.h"
 #include "tree-eh.h"
+#include "ssa.h"
 
 static struct datadep_stats
 {
@@ -584,6 +582,10 @@ debug_ddrs (vec<ddr_p> ddrs)
   dump_ddrs (stderr, ddrs);
 }
 
+static void
+split_constant_offset (tree exp, tree *var, tree *off,
+		       hash_map<tree, std::pair<tree, tree> > &cache);
+
 /* Helper function for split_constant_offset.  Expresses OP0 CODE OP1
    (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
    constant of type ssizetype, and returns true.  If we cannot do this
@@ -592,7 +594,8 @@ debug_ddrs (vec<ddr_p> ddrs)
 
 static bool
 split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
-			 tree *var, tree *off)
+			 tree *var, tree *off,
+			 hash_map<tree, std::pair<tree, tree> > &cache)
 {
   tree var0, var1;
   tree off0, off1;
@@ -613,8 +616,8 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
       /* FALLTHROUGH */
     case PLUS_EXPR:
     case MINUS_EXPR:
-      split_constant_offset (op0, &var0, &off0);
-      split_constant_offset (op1, &var1, &off1);
+      split_constant_offset (op0, &var0, &off0, cache);
+      split_constant_offset (op1, &var1, &off1, cache);
       *var = fold_build2 (code, type, var0, var1);
       *off = size_binop (ocode, off0, off1);
       return true;
@@ -623,7 +626,7 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
       if (TREE_CODE (op1) != INTEGER_CST)
 	return false;
 
-      split_constant_offset (op0, &var0, &off0);
+      split_constant_offset (op0, &var0, &off0, cache);
       *var = fold_build2 (MULT_EXPR, type, var0, op1);
       *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1));
       return true;
@@ -647,7 +650,7 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
 
 	if (poffset)
 	  {
-	    split_constant_offset (poffset, &poffset, &off1);
+	    split_constant_offset (poffset, &poffset, &off1, cache);
 	    off0 = size_binop (PLUS_EXPR, off0, off1);
 	    if (POINTER_TYPE_P (TREE_TYPE (base)))
 	      base = fold_build_pointer_plus (base, poffset);
@@ -691,18 +694,48 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
 	if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
 	  return false;
 
-	var0 = gimple_assign_rhs1 (def_stmt);
 	subcode = gimple_assign_rhs_code (def_stmt);
+
+	/* We are using a cache to avoid un-CSEing large amounts of code.  */
+	bool use_cache = false;
+	if (!has_single_use (op0)
+	    && (subcode == POINTER_PLUS_EXPR
+		|| subcode == PLUS_EXPR
+		|| subcode == MINUS_EXPR
+		|| subcode == MULT_EXPR
+		|| subcode == ADDR_EXPR
+		|| CONVERT_EXPR_CODE_P (subcode)))
+	  {
+	    use_cache = true;
+	    bool existed;
+	    std::pair<tree, tree> &e = cache.get_or_insert (op0, &existed);
+	    if (existed)
+	      {
+		if (integer_zerop (e.second))
+		  return false;
+		*var = e.first;
+		*off = e.second;
+		return true;
+	      }
+	    e = std::make_pair (op0, ssize_int (0));
+	  }
+
+	var0 = gimple_assign_rhs1 (def_stmt);
 	var1 = gimple_assign_rhs2 (def_stmt);
 
-	return split_constant_offset_1 (type, var0, subcode, var1, var, off);
+	bool res = split_constant_offset_1 (type, var0, subcode, var1,
+					    var, off, cache);
+	if (res && use_cache)
+	  *cache.get (op0) = std::make_pair (*var, *off);
+	return res;
       }
     CASE_CONVERT:
       {
-	/* We must not introduce undefined overflow, and we must not change the value.
-	   Hence we're okay if the inner type doesn't overflow to start with
-	   (pointer or signed), the outer type also is an integer or pointer
-	   and the outer precision is at least as large as the inner.  */
+	/* We must not introduce undefined overflow, and we must not change
+	   the value.  Hence we're okay if the inner type doesn't overflow
+	   to start with (pointer or signed), the outer type also is an
+	   integer or pointer and the outer precision is at least as large
+	   as the inner.  */
 	tree itype = TREE_TYPE (op0);
 	if ((POINTER_TYPE_P (itype)
 	     || (INTEGRAL_TYPE_P (itype) && !TYPE_OVERFLOW_TRAPS (itype)))
@@ -714,7 +747,7 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
 		/* Split the unconverted operand and try to prove that
 		   wrapping isn't a problem.  */
 		tree tmp_var, tmp_off;
-		split_constant_offset (op0, &tmp_var, &tmp_off);
+		split_constant_offset (op0, &tmp_var, &tmp_off, cache);
 
 		/* See whether we have an SSA_NAME whose range is known
 		   to be [A, B].  */
@@ -749,7 +782,7 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
 		*off = wide_int_to_tree (ssizetype, diff);
 	      }
 	    else
-	      split_constant_offset (op0, &var0, off);
+	      split_constant_offset (op0, &var0, off, cache);
 	    *var = fold_convert (type, var0);
 	    return true;
 	  }
@@ -764,8 +797,9 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
 /* Expresses EXP as VAR + OFF, where off is a constant.  The type of OFF
    will be ssizetype.  */
 
-void
-split_constant_offset (tree exp, tree *var, tree *off)
+static void
+split_constant_offset (tree exp, tree *var, tree *off,
+		       hash_map<tree, std::pair<tree, tree> > &cache)
 {
   tree type = TREE_TYPE (exp), op0, op1, e, o;
   enum tree_code code;
@@ -779,13 +813,23 @@ split_constant_offset (tree exp, tree *var, tree *off)
 
   code = TREE_CODE (exp);
   extract_ops_from_tree (exp, &code, &op0, &op1);
-  if (split_constant_offset_1 (type, op0, code, op1, &e, &o))
+  if (split_constant_offset_1 (type, op0, code, op1, &e, &o, cache))
     {
       *var = e;
       *off = o;
     }
 }
 
+void
+split_constant_offset (tree exp, tree *var, tree *off)
+{
+  static hash_map<tree, std::pair<tree, tree> > *cache;
+  if (!cache)
+    cache = new hash_map<tree, std::pair<tree, tree> > (37);
+  split_constant_offset (exp, var, off, *cache);
+  cache->empty ();
+}
+
 /* Returns the address ADDR of an object in a canonical shape (without nop
    casts, and with type of pointer to the object).  */