Re: [PATCH] Fix PR56478

[Marek Polacek <polacek at redhat dot com>]

On Fri, Mar 01, 2013 at 11:10:40AM +0100, Richard Biener wrote:
> Don't use NULL_TREE built_int_cst - doing so hints at that you want to
> use double_ints.  Generally doing computation with trees is expensive.
> You want to avoid that at all cost.  Use double-ints (yeah, you have to
> use the clunky divmod_with_overflow interface).

So this is a WIP patch, which uses double_ints.  I apologize for my
dumbness, but I haven't figured out how to do the normalization here.
It's probably something simple, but...  The point of the normalization
would be that when multiplying the normalized number with 10000 (aka
REG_BR_PROB_BASE), the result fits into plain int, right?
If you could suggest what to do with that, that would be appreciated.

Thanks.

--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -1028,13 +1028,13 @@ static bool
 is_comparison_with_loop_invariant_p (gimple stmt, struct loop *loop,
 				     tree *loop_invariant,
 				     enum tree_code *compare_code,
-				     int *loop_step,
+				     tree *loop_step,
 				     tree *loop_iv_base)
 {
   tree op0, op1, bound, base;
   affine_iv iv0, iv1;
   enum tree_code code;
-  int step;
+  tree step;
 
   code = gimple_cond_code (stmt);
   *loop_invariant = NULL;
@@ -1077,7 +1077,7 @@ is_comparison_with_loop_invariant_p (gimple stmt, struct loop *loop,
       bound = iv0.base;
       base = iv1.base;
       if (host_integerp (iv1.step, 0))
-	step = tree_low_cst (iv1.step, 0);
+	step = iv1.step;
       else
 	return false;
     }
@@ -1086,7 +1086,7 @@ is_comparison_with_loop_invariant_p (gimple stmt, struct loop *loop,
       bound = iv1.base;
       base = iv0.base;
       if (host_integerp (iv0.step, 0))
-	step = tree_low_cst (iv0.step, 0);  
+	step = iv0.step;
       else
 	return false;
     }
@@ -1154,6 +1154,16 @@ expr_coherent_p (tree t1, tree t2)
     return false;
 }
 
+static double_int
+normalize (double_int n)
+{
+  int msb = HOST_BITS_PER_WIDE_INT - clz_hwi (n.to_shwi ());
+  if (msb > HOST_BITS_PER_INT - 16)
+    {}
+    // ??? n = n.rshift (?, ?, ?);
+  return n;
+}
+
 /* Predict branch probability of BB when BB contains a branch that compares
    an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
    loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
@@ -1178,7 +1188,7 @@ predict_iv_comparison (struct loop *loop, basic_block bb,
   gimple stmt;
   tree compare_var, compare_base;
   enum tree_code compare_code;
-  int compare_step;
+  tree compare_step;
   edge then_edge;
   edge_iterator ei;
 
@@ -1224,34 +1234,68 @@ predict_iv_comparison (struct loop *loop, basic_block bb,
       && host_integerp (compare_base, 0))
     {
       int probability;
-      HOST_WIDE_INT compare_count;
-      HOST_WIDE_INT loop_bound = tree_low_cst (loop_bound_var, 0);
-      HOST_WIDE_INT compare_bound = tree_low_cst (compare_var, 0);
-      HOST_WIDE_INT base = tree_low_cst (compare_base, 0);
-      HOST_WIDE_INT loop_count = (loop_bound - base) / compare_step;
-
-      if ((compare_step > 0)
+      bool of, overflow = false;
+      double_int mod, compare_count, tem, loop_count;
+
+      double_int loop_bound = tree_to_double_int (loop_bound_var);
+      double_int compare_bound = tree_to_double_int (compare_var);
+      double_int base = tree_to_double_int (compare_base);
+      double_int compare_step = tree_to_double_int (compare_step);
+
+      /* (loop_bound - base) / compare_step */
+      tem = loop_bound.sub_with_overflow (base, &of);
+      overflow |= of;
+      loop_count = tem.divmod_with_overflow (compare_step,
+					      0, TRUNC_DIV_EXPR,
+					      &mod, &of);
+      overflow |= of;
+
+      if ((compare_step.scmp (double_int_zero) == 1)
           ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
-	compare_count = (loop_bound - compare_bound) / compare_step;
+	{
+	  /* (loop_bound - compare_bound) / compare_step */
+	  tem = loop_bound.sub_with_overflow (compare_bound, &of);
+	  overflow |= of;
+	  compare_count = tem.divmod_with_overflow (compare_step,
+						     0, TRUNC_DIV_EXPR,
+						     &mod, &of);
+	  overflow |= of;
+	}
       else
-	compare_count = (compare_bound - base) / compare_step;
-
+        {
+	  /* (compare_bound - base) / compare_step */
+	  tem = compare_bound.sub_with_overflow (base, &of);
+	  overflow |= of;
+          compare_count = tem.divmod_with_overflow (compare_step,
+						     0, TRUNC_DIV_EXPR,
+						     &mod, &of);
+	  overflow |= of;
+	}
       if (compare_code == LE_EXPR || compare_code == GE_EXPR)
-	compare_count ++;
+	++compare_count;
       if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
-	loop_count ++;
-      if (compare_count < 0)
-	compare_count = 0;
-      if (loop_count < 0)
-	loop_count = 0;
-
-      if (loop_count == 0)
+	++loop_count;
+      if (compare_count.scmp (double_int_zero) == -1)
+        compare_count = double_int_zero;
+      if (loop_count.scmp (double_int_zero) == -1)
+        loop_count = double_int_zero;
+      if (loop_count.scmp (double_int_zero) == 0)
 	probability = 0;
-      else if (compare_count > loop_count)
+      else if (compare_count.scmp (loop_count) == 1)
 	probability = REG_BR_PROB_BASE;
       else
-	probability = (double) REG_BR_PROB_BASE * compare_count / loop_count;
-      predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
+        {
+	  tem = compare_count.divmod_with_overflow (loop_count,
+						     0, TRUNC_DIV_EXPR,
+						     &mod, &of);
+	  overflow |= of;
+	  gcc_assert (REG_BR_PROB_BASE < 65536);
+	  probability = (double) REG_BR_PROB_BASE * normalize (tem).to_shwi ();
+	}
+
+      if (!overflow)
+        predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
+
       return;
     }
 
@@ -1402,7 +1446,7 @@ predict_loops (void)
       edge ex;
       struct nb_iter_bound *nb_iter;
       enum tree_code loop_bound_code = ERROR_MARK;
-      int loop_bound_step = 0;
+      tree loop_bound_step = NULL;
       tree loop_bound_var = NULL;
       tree loop_iv_base = NULL;
       gimple stmt = NULL;
@@ -1549,7 +1593,7 @@ predict_loops (void)
 	  if (loop_bound_var)
 	    predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
 				   loop_bound_code,
-				   loop_bound_step);
+				   tree_low_cst (loop_bound_step, 0));
 	}
 
       /* Free basic blocks from get_loop_body.  */

	Marek