pr26026: udiv and umod optimization

[Alan Modra]

On Thu, Feb 09, 2006 at 08:35:20AM -0700, Jeffrey A Law wrote:
> The second alternative would be to walk the def-use chain back one
> step for the divisor and see if the divisor is set from a 1 << X
> style operation.  This would be trivial to implement inside the
> existing simplification code.

Like so?  My first foray into tree-ssa, so I won't be surprised if
there is a better way to do this..  Bootstrapped and regression tested
powerpc64-linux.

	PR tree-optimization/26026
	* tree-vrp.c (simplify_div_or_mod_using_ranges): Replace rhs_code
	param with is_div.  Support optimisation of div and mod by
	power of two shifted left a variable amout.  Tidy.
	(simplify_stmt_using_ranges): Similarly.  Also support FLOOR_DIV_EXPR
	and FLOOR_MOD_EXPR.

Index: tree-vrp.c
===================================================================
--- tree-vrp.c	(revision 110783)
+++ tree-vrp.c	(working copy)
@@ -3962,37 +3962,68 @@ varying:
    than zero and the second operand is an exact power of two.  */
 
 static void
-simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code)
+simplify_div_or_mod_using_ranges (tree stmt, tree rhs, bool is_div)
 {
-  tree val = NULL;
-  tree op = TREE_OPERAND (rhs, 0);
-  value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
+  tree op0 = TREE_OPERAND (rhs, 0);
+  bool ok;
 
-  if (TYPE_UNSIGNED (TREE_TYPE (op)))
+  if (TYPE_UNSIGNED (TREE_TYPE (op0)))
     {
-      val = integer_one_node;
+      ok = true;
     }
   else
     {
+      tree val;
+      value_range_t *vr = get_value_range (op0);
+
       val = compare_range_with_value (GT_EXPR, vr, integer_zero_node);
+      ok = val && integer_onep (val);
     }
 
-  if (val && integer_onep (val))
+  if (ok)
     {
       tree t;
-      tree op0 = TREE_OPERAND (rhs, 0);
       tree op1 = TREE_OPERAND (rhs, 1);
 
-      if (rhs_code == TRUNC_DIV_EXPR)
+      if (is_div)
 	{
-	  t = build_int_cst (NULL_TREE, tree_log2 (op1));
+	  if (TREE_CODE (op1) == SSA_NAME)
+	    {
+	      /* op1 = C << N, C a power of two.  */
+	      tree defexp = TREE_OPERAND (SSA_NAME_DEF_STMT (op1), 1);
+	      int pow2 = tree_log2 (TREE_OPERAND (defexp, 0));
+
+	      t = TREE_OPERAND (defexp, 1);
+	      if (pow2 != 0)
+		{
+		  /* tmp = N + log2(C).  */
+		  block_stmt_iterator bsi = bsi_for_stmt (stmt);
+
+		  t = gimplify_build2 (&bsi, PLUS_EXPR, TREE_TYPE (t),
+				       t, build_int_cst (NULL_TREE, pow2));
+		}
+	    }
+	  else
+	    t = build_int_cst (NULL_TREE, tree_log2 (op1));
+
 	  t = build2 (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
 	}
       else
 	{
-	  t = build_int_cst (TREE_TYPE (op1), 1);
-	  t = int_const_binop (MINUS_EXPR, op1, t, 0);
-	  t = fold_convert (TREE_TYPE (op0), t);
+	  if (TREE_CODE (op1) == SSA_NAME)
+	    {
+	      block_stmt_iterator bsi = bsi_for_stmt (stmt);
+
+	      t = TREE_OPERAND (SSA_NAME_DEF_STMT (op1), 0);
+	      t = build2 (MINUS_EXPR, TREE_TYPE (t), t, integer_one_node);
+	      t = fold_convert (TREE_TYPE (op0), t);
+	      t = gimplify_val (&bsi, TREE_TYPE (op0), t);
+	    }
+	  else
+	    {
+	      t = int_const_binop (MINUS_EXPR, op1, integer_one_node, 0);
+	      t = fold_convert (TREE_TYPE (op0), t);
+	    }
 	  t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
 	}
 
@@ -4202,9 +4233,29 @@ simplify_stmt_using_ranges (tree stmt)
 	 and BIT_AND_EXPR respectively if the first operand is greater
 	 than zero and the second operand is an exact power of two.  */
       if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
-	  && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
-	  && integer_pow2p (TREE_OPERAND (rhs, 1)))
-	simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code);
+	  && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
+	{
+	  tree t = TREE_OPERAND (rhs, 1);
+
+	  /* Also handle an exact power of two shifted left a variable
+	     amount.  */
+	  if (TREE_CODE (t) == SSA_NAME)
+	    {
+	      t = SSA_NAME_DEF_STMT (t);
+	      if (TREE_CODE (t) != MODIFY_EXPR)
+		return;
+
+	      t = TREE_OPERAND (t, 1);
+	      if (TREE_CODE (t) != LSHIFT_EXPR)
+		return;
+
+	      t = TREE_OPERAND (t, 0);
+	    }
+
+	  if (integer_pow2p (t))
+	    simplify_div_or_mod_using_ranges (stmt, rhs,
+					      rhs_code == TRUNC_DIV_EXPR);
+	}
 
       /* Transform ABS (X) into X or -X as appropriate.  */
       if (rhs_code == ABS_EXPR

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre