Hi,
For the specific case reported in PR62173, overflow check on SCEV can be
improved using range information. Precisely, it's range information of ssa
name in IV's base that helps, rather than range information of the IV
itself. Since the IV is computed in the form of "IV_var = <var_base,
IV_var_offset>" in loop header, we can derive that var_base takes IV_var's
range information in the loop. Even though this may not hold in other parts
of program. To address this, this patch iterates each phi node in loop's
header and propagates range information from IV to base var. Of course, the
range information should be restored after IVOPTs. For now, we only
propagate IV's range information to base var if it hasn't had it. This can
be extended to refine the existing range information.
Moreover, because of loop header copying, it's very likely to have entry
condition for the loop. we also use this to further improve the range
information. The patch does this by iterating upwards in dominator tree.
Actually the range information wouldn't be enough in this exact case.
I was told this causes small regression in some benchmark. But I did saw
inner-most loops are improved obviously with this and the hotspot of that
benchmark isn't affected at all. I will further go through all the code
changes later. Also there are couple of possible improvement, for example,
factor out the macro; don't iterate dominating tree repeatedly for each phi
node.
It passes bootstrap and regtest on both x86_64 and aarch64. But I would
like to hear more comments on the idea itself then do some refinement.
So any comments?
Thanks,
bin
2015-02-13 Bin Cheng <bin.ch...@arm.com>
PR tree-optimization/62173
* tree-ssa-loop-niter.h (split_to_var_and_offset): Expose it.
(refine_bounds_using_guard): Expose it. Change parameters by
using below, up directly.
* tree-ssa-loop-niter.c (split_to_var_and_offset): Expose it.
(refine_bounds_using_guard): Expose it. Change parameters by
using below, up directly.
(bound_difference): Change arguments.
(scev_probably_wraps_p): Use range info when checking wrap behavior.
* tree-ssa-loop-ivopts.c (name_range_info_map): New field in struct
ivopts_data.
(tree_ssa_iv_optimize_init): Initialize name_range_info_map.
(tree_ssa_iv_optimize_finalize): Release name_range_info_map.
(MAX_DOMINATORS_TO_WALK): New macro.
(refine_ssa_name_range_info, refine_range_info_for_loop)
(restore_range_info_for_loop): New functions.
(tree_ssa_iv_optimize): Refine and restore range info for loop.
gcc/testsuite/ChangeLog
2015-02-13 Bin Cheng <bin.ch...@arm.com>
PR tree-optimization/62173
* gcc.dg/tree-ssa/pr62173.c: New test.Index: gcc/testsuite/gcc.dg/tree-ssa/pr62173.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/pr62173.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/pr62173.c (revision 0)
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ivopts" } */
+
+void foo (char);
+void bar(int i)
+{
+ char A[10];
+ int d = 0;
+ while (i > 0)
+ A[d++] = i--;
+
+ while (d > 0)
+ foo (A[d--]);
+}
+
+/* { dg-final { scan-tree-dump-not "A\\\[d_\[0-9\]*" "ivopts"} } */
+/* { dg-final { cleanup-tree-dump "ivopts" } } */
Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c (revision 219574)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -344,6 +344,8 @@ struct ivopts_data
/* Cache used by tree_to_aff_combination_expand. */
hash_map<tree, name_expansion *> *name_expansion_cache;
+ hash_map<tree, range_info_def *> *name_range_info_map;
+
/* The maximum invariant id. */
unsigned max_inv_id;
@@ -898,6 +900,7 @@ tree_ssa_iv_optimize_init (struct ivopts_data *dat
data->inv_expr_tab = new hash_table<iv_inv_expr_hasher> (10);
data->inv_expr_id = 0;
data->name_expansion_cache = NULL;
+ data->name_range_info_map = NULL;
decl_rtl_to_reset.create (20);
}
@@ -6897,6 +6900,8 @@ tree_ssa_iv_optimize_finalize (struct ivopts_data
delete data->inv_expr_tab;
data->inv_expr_tab = NULL;
free_affine_expand_cache (&data->name_expansion_cache);
+ delete data->name_range_info_map;
+ data->name_range_info_map = NULL;
}
/* Returns true if the loop body BODY includes any function calls. */
@@ -6999,6 +7004,151 @@ finish:
return changed;
}
+/* Propagate range information from LHS to ARG with respect to LOOP.
+ This function also walks dominators of LOOP's header and uses the
+ entry guards to refine the propagated range information for ARG.
+
+ Currently we propagate range information if there is no existing
+ information for ARG, this can be improved for cases in which ARG
+ has less accurate information than LHS. */
+
+#define MAX_DOMINATORS_TO_WALK (8)
+
+static void
+refine_ssa_name_range_info (struct ivopts_data *data,
+ struct loop *loop, tree lhs, tree arg)
+{
+ int cnt = 1;
+ basic_block bb;
+ wide_int minv, maxv;
+ range_info_def *ri_arg;
+ enum value_range_type vrp_type;
+ mpz_t minm, maxm, zerom, arg_off;
+ tree arg_var, type = TREE_TYPE (arg);
+
+ vrp_type = get_range_info (arg, &minv, &maxv);
+
+ if (vrp_type == VR_RANGE || vrp_type == VR_ANTI_RANGE)
+ return;
+
+ vrp_type = get_range_info (lhs, &minv, &maxv);
+ if (vrp_type != VR_RANGE)
+ return;
+
+ if (data->name_range_info_map == NULL)
+ data->name_range_info_map = new hash_map<tree, range_info_def *>;
+
+ /* Record old range info for arg in map. */
+ ri_arg = SSA_NAME_RANGE_INFO (arg);
+ data->name_range_info_map->put (arg, ri_arg);
+
+ /* Keep refining range information for arg with dominators of
+ the loop header. */
+ mpz_init (minm);
+ mpz_init (maxm);
+ mpz_init (zerom);
+ mpz_init (arg_off);
+ split_to_var_and_offset (arg, &arg_var, arg_off);
+ wi::to_mpz (minv, minm, TYPE_SIGN (type));
+ wi::to_mpz (maxv, maxm, TYPE_SIGN (type));
+ wi::to_mpz (integer_zero_node, zerom, TYPE_SIGN (type));
+ for (bb = get_immediate_dominator (CDI_DOMINATORS, loop->header);
+ bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK;
+ bb = get_immediate_dominator (CDI_DOMINATORS, bb))
+ {
+ edge e;
+ tree c0, c1;
+ gimple cond;
+ enum tree_code cmp;
+
+ if (!single_pred_p (bb))
+ continue;
+ e = single_pred_edge (bb);
+
+ if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
+ continue;
+
+ cond = last_stmt (e->src);
+ c0 = gimple_cond_lhs (cond);
+ cmp = gimple_cond_code (cond);
+ c1 = gimple_cond_rhs (cond);
+
+ if (e->flags & EDGE_FALSE_VALUE)
+ cmp = invert_tree_comparison (cmp, false);
+
+ /* Refine bounds with respect to condition "c0 cmp c1". */
+ refine_bounds_using_guard (type, arg_var, arg_off, integer_zero_node,
+ zerom, c0, cmp, c1, minm, maxm);
+ ++cnt;
+ }
+ minv = wi::from_mpz (type, minm, false);
+ maxv = wi::from_mpz (type, maxm, false);
+ mpz_clear (minm);
+ mpz_clear (maxm);
+ mpz_clear (zerom);
+ mpz_clear (arg_off);
+ /* Set new range info for arg. */
+ set_range_info (arg, vrp_type, minv, maxv);
+}
+
+/* Refine range information for ssa names used in LOOP's header.
+ Given below loop,
+
+ Loop_1:
+ # RANGE [0, 10]
+ lhs_1 = PHI <x_1(D), lhs_2>;
+ ...
+ # RANGE [0, 9]
+ lhs_2 = lhs_1 + step;
+ goto <Loop_1>;
+
+ We can propagate RANGE[0, 10] to x_1(D) and use this information
+ in Loop_1. */
+
+static void
+refine_range_info_for_loop (struct ivopts_data *data, struct loop *loop)
+{
+ gphi *phi;
+ tree lhs, arg;
+ gphi_iterator psi;
+
+ for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
+ {
+ phi = psi.phi ();
+ if (gimple_vuse (phi))
+ continue;
+
+ lhs = PHI_RESULT (phi);
+ arg = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
+ if (TREE_CODE (lhs) != SSA_NAME
+ || TREE_CODE (arg) != SSA_NAME
+ || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+ || !INTEGRAL_TYPE_P (TREE_TYPE (arg)))
+ continue;
+
+ refine_ssa_name_range_info (data, loop, lhs, arg);
+ }
+ return;
+}
+
+/* Restore range information for LOOP. */
+
+static void
+restore_range_info_for_loop (struct ivopts_data *data,
+ struct loop *loop ATTRIBUTE_UNUSED)
+{
+ if (data->name_range_info_map)
+ {
+ hash_map<tree, range_info_def *>::iterator iter
+ = data->name_range_info_map->begin ();
+ for (; iter != data->name_range_info_map->end (); ++iter)
+ {
+ SSA_NAME_RANGE_INFO ((*iter).first) = NULL;
+ data->name_range_info_map->remove ((*iter).first);
+ }
+ }
+}
+
/* Main entry point. Optimizes induction variables in loops. */
void
@@ -7015,7 +7165,9 @@ tree_ssa_iv_optimize (void)
if (dump_file && (dump_flags & TDF_DETAILS))
flow_loop_dump (loop, dump_file, NULL, 1);
+ refine_range_info_for_loop (&data, loop);
tree_ssa_iv_optimize_loop (&data, loop);
+ restore_range_info_for_loop (&data, loop);
}
tree_ssa_iv_optimize_finalize (&data);
Index: gcc/tree-ssa-loop-niter.c
===================================================================
--- gcc/tree-ssa-loop-niter.c (revision 219574)
+++ gcc/tree-ssa-loop-niter.c (working copy)
@@ -96,7 +96,7 @@ typedef struct
/* Splits expression EXPR to a variable part VAR and constant OFFSET. */
-static void
+void
split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
{
tree type = TREE_TYPE (expr);
@@ -295,11 +295,11 @@ bound_difference_of_offsetted_base (tree type, mpz
difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
and stores it to BNDS. */
-static void
+void
refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
tree vary, mpz_t offy,
tree c0, enum tree_code cmp, tree c1,
- bounds *bnds)
+ mpz_t below, mpz_t up)
{
tree varc0, varc1, tmp, ctype;
mpz_t offc0, offc1, loffx, loffy, bnd;
@@ -434,13 +434,13 @@ refine_bounds_using_guard (tree type, tree varx, m
if (lbound)
{
mpz_neg (bnd, bnd);
- if (mpz_cmp (bnds->below, bnd) < 0)
- mpz_set (bnds->below, bnd);
+ if (mpz_cmp (below, bnd) < 0)
+ mpz_set (below, bnd);
}
else
{
- if (mpz_cmp (bnd, bnds->up) < 0)
- mpz_set (bnds->up, bnd);
+ if (mpz_cmp (bnd, up) < 0)
+ mpz_set (up, bnd);
}
mpz_clear (bnd);
}
@@ -540,7 +540,7 @@ bound_difference (struct loop *loop, tree x, tree
cmp = invert_tree_comparison (cmp, false);
refine_bounds_using_guard (type, varx, offx, vary, offy,
- c0, cmp, c1, bnds);
+ c0, cmp, c1, bnds->below, bnds->up);
++cnt;
}
@@ -3852,12 +3852,20 @@ scev_probably_wraps_p (tree base, tree step,
bound of the type, and verify that the loop is exited before this
occurs. */
unsigned_type = unsigned_type_for (type);
- base = fold_convert (unsigned_type, base);
if (tree_int_cst_sign_bit (step))
{
tree extreme = fold_convert (unsigned_type,
lower_bound_in_type (type, type));
+ wide_int min, max;
+
+ if (TREE_CODE (base) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (base))
+ && get_range_info (base, &min, &max) == VR_RANGE)
+ base = wide_int_to_tree (unsigned_type, max);
+ else
+ base = fold_convert (unsigned_type, base);
+
delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
fold_convert (unsigned_type, step));
@@ -3866,6 +3874,15 @@ scev_probably_wraps_p (tree base, tree step,
{
tree extreme = fold_convert (unsigned_type,
upper_bound_in_type (type, type));
+ wide_int min, max;
+
+ if (TREE_CODE (base) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (base))
+ && get_range_info (base, &min, &max) == VR_RANGE)
+ base = wide_int_to_tree (unsigned_type, min);
+ else
+ base = fold_convert (unsigned_type, base);
+
delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
step_abs = fold_convert (unsigned_type, step);
}
Index: gcc/tree-ssa-loop-niter.h
===================================================================
--- gcc/tree-ssa-loop-niter.h (revision 219574)
+++ gcc/tree-ssa-loop-niter.h (working copy)
@@ -20,6 +20,11 @@ along with GCC; see the file COPYING3. If not see
#ifndef GCC_TREE_SSA_LOOP_NITER_H
#define GCC_TREE_SSA_LOOP_NITER_H
+extern void split_to_var_and_offset (tree expr, tree *var, mpz_t offset);
+extern void refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
+ tree vary, mpz_t offy,
+ tree c0, enum tree_code cmp, tree c1,
+ mpz_t below, mpz_t up);
extern tree expand_simple_operations (tree);
extern bool loop_only_exit_p (const struct loop *, const_edge);
extern bool number_of_iterations_exit (struct loop *, edge,
