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
