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] Optimize x*x*x*x*x*x using 3 multiplications.


Hi,

On Thu, 31 Jul 2003, Zack Weinberg wrote:

> > I have a somewhat ugly patch for this problem which basically reorders all
> > operands of an associative, commutative operator into some canonical
> > order.  This makes CSEing them possible.
>
> We have to be careful ... is this optimization not forbidden in Fortran?
> (with the parentheses present, anyway)

I placed it at the same point were all the other reassociations are
already taking place in fold-const, so it shouldn't be more unsafe than it
was.  For the curious I attach some version in the works.  It's relative
to some 3.3 version, though and contains some dead code.


Ciao,
Michael.

Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.226.2.9
diff -u -p -r1.226.2.9 fold-const.c
--- fold-const.c	21 Jul 2003 19:07:12 -0000	1.226.2.9
+++ fold-const.c	30 Jul 2003 21:29:05 -0000
@@ -1011,6 +1011,233 @@ associate_trees (t1, t2, code, type)

   return fold (build (code, type, convert (type, t1), convert (type, t2)));
 }
+
+static tree tree_get_index PARAMS ((tree));
+static int indirect_ref_zero_ofs_p PARAMS ((tree));
+static int indirect_ref_nonzero_ofs_p PARAMS ((tree));
+static tree associate_trees_refs PARAMS ((tree, tree, enum tree_code, tree));
+static void split_tree_indirect_refs PARAMS ((tree, enum tree_code, tree));
+static void split_tree_for_reorder PARAMS ((tree, enum tree_code, tree));
+static int compare_trees PARAMS ((const PTR, const PTR));
+static tree reorder_memrefs PARAMS ((tree, tree, enum tree_code, tree));
+static tree reorder_summands PARAMS ((tree, tree, enum tree_code, tree));
+
+static tree
+tree_get_index (t)
+     tree t;
+{
+  if (TREE_CODE (t) == ARRAY_REF)
+    return TREE_OPERAND (t, 1);
+  else
+    {
+      t = TREE_OPERAND (t, 0);
+      if (TREE_CODE (t) != PLUS_EXPR)
+	return NULL_TREE;
+      return TREE_OPERAND (t, 1);
+    }
+}
+
+static int
+indirect_ref_nonzero_ofs_p (t)
+     tree t;
+{
+  tree i = tree_get_index (t);
+  if (i && TREE_CODE (i) == INTEGER_CST && !integer_zerop (i))
+    return 1;
+  return 0;
+}
+
+static int
+indirect_ref_zero_ofs_p (t)
+     tree t;
+{
+  tree i = tree_get_index (t);
+  if (!i)
+    return 1;
+  if (TREE_CODE (i) == INTEGER_CST && integer_zerop (i))
+    return 1;
+  return 0;
+}
+
+static tree
+associate_trees_refs (t1, t2, code, type)
+     tree t1, t2;
+     enum tree_code code;
+     tree type;
+{
+  if (t1 == 0)
+    return t2;
+  else if (t2 == 0)
+    return t1;
+  return build (code, type, convert (type, t1), convert (type, t2));
+}
+
+#define MAX_SUMMANDS 100
+static tree merged_z, merged_nz, merged_rest;
+static tree summands[MAX_SUMMANDS];
+static int num_summands;
+static void
+split_tree_indirect_refs (in, code, type)
+     tree in;
+     enum tree_code code;
+     tree type;
+{
+  /* Strip any conversions that don't change the machine mode or signedness.  */
+  STRIP_SIGN_NOPS (in);
+
+  if (TREE_CODE (in) == INDIRECT_REF || TREE_CODE (in) == ARRAY_REF)
+    {
+      if (indirect_ref_zero_ofs_p (in))
+        merged_z = associate_trees_refs (merged_z, in, code, type);
+      else if (indirect_ref_nonzero_ofs_p (in))
+        merged_nz = associate_trees_refs (merged_nz, in, code, type);
+      else
+        merged_rest = associate_trees_refs (merged_rest, in, code, type);
+    }
+  else if (TREE_CODE (in) == code)
+    {
+      tree op0 = TREE_OPERAND (in, 0);
+      tree op1 = TREE_OPERAND (in, 1);
+      split_tree_indirect_refs (op0, code, type);
+      split_tree_indirect_refs (op1, code, type);
+    }
+  else
+    merged_rest = associate_trees_refs (merged_rest, in, code, type);
+}
+
+static void
+split_tree_for_reorder (in, code, type)
+     tree in;
+     enum tree_code code;
+     tree type;
+{
+  /* Strip any conversions that don't change the machine mode or signedness.  */
+  STRIP_SIGN_NOPS (in);
+
+  if ((TREE_CODE (in) == INDIRECT_REF
+       || TREE_CODE (in) == ARRAY_REF
+       || TREE_CODE (in) == VAR_DECL)
+      && num_summands < MAX_SUMMANDS)
+    summands[num_summands++] = in;
+  else if (TREE_CODE (in) == code)
+    {
+      tree op0 = TREE_OPERAND (in, 0);
+      tree op1 = TREE_OPERAND (in, 1);
+      split_tree_for_reorder (op0, code, type);
+      split_tree_for_reorder (op1, code, type);
+    }
+  else
+    merged_rest = associate_trees_refs (merged_rest, in, code, type);
+}
+
+static int
+compare_trees (v1, v2)
+     const PTR v1;
+     const PTR v2;
+{
+  tree t1 = *((const tree *) v1);
+  tree t2 = *((const tree *) v2);
+
+  if (t1 == t2)
+    return 0;
+  /* Everything besides var_decls and indirect_refs last.  */
+  if (TREE_CODE (t1) != INDIRECT_REF
+      && TREE_CODE (t1) != ARRAY_REF
+      && TREE_CODE (t1) != VAR_DECL)
+    return 1;
+  if (TREE_CODE (t2) != INDIRECT_REF
+      && TREE_CODE (t2) != ARRAY_REF
+      && TREE_CODE (t2) != VAR_DECL)
+    return -1;
+  /* All indirect_refs with nonzero index before var_decls.
+     All indirect_refs with zero index after var_decls.  */
+  if (TREE_CODE (t1) != TREE_CODE (t2))
+    {
+      if (TREE_CODE (t1) == INDIRECT_REF || TREE_CODE (t1) == ARRAY_REF)
+        {
+	  if (indirect_ref_nonzero_ofs_p (t1))
+            return -1;
+	  else
+	    return 1;
+	}
+      /* t2 is a INDIRECT_REF or ARRAY_REF, so we can call that without
+	 checking.  */
+      else if (indirect_ref_nonzero_ofs_p (t2))
+	return 1;
+      else
+	return -1;
+    }
+  if (TREE_CODE (t1) == VAR_DECL)
+    {
+      if (IDENTIFIER_HASH_VALUE (DECL_NAME (t1))
+          < IDENTIFIER_HASH_VALUE (DECL_NAME (t2)))
+        return -1;
+      else
+	return 1;
+    }
+  /* We have two indirect_refs here.  */
+  if (indirect_ref_nonzero_ofs_p (t1) && indirect_ref_nonzero_ofs_p (t2))
+    /* As both had non-zero index, we know that tree_get_index() really
+       returns INTEGER_CST.  */
+    return tree_int_cst_compare (tree_get_index (t1), tree_get_index (t2));
+  else if (indirect_ref_zero_ofs_p (t1))
+    return 1;
+  else
+    return -1;
+}
+
+static tree
+reorder_memrefs (in0, in1, code, type)
+     tree in0, in1;
+     enum tree_code code;
+     tree type;
+{
+  tree ret = 0;
+  merged_z = 0;
+  merged_nz = 0;
+  merged_rest = 0;
+  /* XXX We can't yet handle MINUS_EXPR.  */
+  if (code == MINUS_EXPR)
+    return 0;
+  if (in0)
+    split_tree_indirect_refs (in0, code, type);
+  if (in1)
+    split_tree_indirect_refs (in1, code, type);
+  if (merged_nz || merged_z)
+    {
+      ret = associate_trees_refs (merged_nz, merged_z, code, type);
+      ret = associate_trees_refs (ret, merged_rest, code, type);
+    }
+  return ret;
+}
+
+static tree
+reorder_summands (in0, in1, code, type)
+     tree in0, in1;
+     enum tree_code code;
+     tree type;
+{
+  tree ret = 0;
+  merged_rest = 0;
+  num_summands = 0;
+  /* XXX We can't yet handle MINUS_EXPR.  */
+  if (code == MINUS_EXPR)
+    return 0;
+  if (in0)
+    split_tree_for_reorder (in0, code, type);
+  if (in1)
+    split_tree_for_reorder (in1, code, type);
+  if (num_summands > 2)
+    {
+      int i;
+      qsort (summands, num_summands, sizeof (tree), compare_trees);
+      ret = summands[0];
+      for (i = 1; i < num_summands; i++)
+        ret = associate_trees_refs (ret, summands[i], code, type);
+      ret = associate_trees_refs (ret, merged_rest, code, type);
+    }
+  return ret;
+}

 /* Combine two integer constants ARG1 and ARG2 under operation CODE
    to produce a new constant.
@@ -5378,11 +5605,16 @@ fold (expr)
 		   + (lit0 != 0) + (lit1 != 0)
 		   + (minus_lit0 != 0) + (minus_lit1 != 0)))
 	    {
+	      tree tmp;
+	      tmp = reorder_summands (var0, var1, code, type);
 	      /* Recombine MINUS_EXPR operands by using PLUS_EXPR.  */
 	      if (code == MINUS_EXPR)
 		code = PLUS_EXPR;

-	      var0 = associate_trees (var0, var1, code, type);
+	      if (tmp)
+		var0 = tmp;
+	      else
+	        var0 = associate_trees (var0, var1, code, type);
 	      con0 = associate_trees (con0, con1, code, type);
 	      lit0 = associate_trees (lit0, lit1, code, type);
 	      minus_lit0 = associate_trees (minus_lit0, minus_lit1, code, type);
@@ -5424,6 +5656,9 @@ fold (expr)
 	      con0 = associate_trees (con0, lit0, code, type);
 	      return convert (type, associate_trees (var0, con0, code, type));
 	    }
+	  var0 = reorder_summands (arg0, arg1, code, type);
+	  if (var0)
+	    return convert (type, var0);
 	}

     binary:


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