Hi,
Tree if-conversion sometimes cannot convert conditional array reference into
unconditional one. Root cause is GCC conservatively assumes newly introduced
array reference could be out of array bound and thus trapping. This patch
improves the situation by proving the converted unconditional array reference
is within array bound using loop niter information. To be specific, it checks
every index of array reference to see if it's within bound in
ifcvt_memrefs_wont_trap. This patch also factors out base_object_writable
checking if the base object is writable or not.
Bootstrap and test on x86_64 and aarch64, is it OK?
Thanks,
bin
2016-04-28 Bin Cheng <bin.ch...@arm.com>
* tree-if-conv.c (tree-ssa-loop.h): Include header file.
(tree-ssa-loop-niter.h): Ditto.
(idx_within_array_bound, ref_within_array_bound): New functions.
(ifcvt_memrefs_wont_trap): Check if array ref is within bound.
Factor out check on writable base object to ...
(base_object_writable): ... here.
diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index 2d14901..170e644 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -106,6 +106,8 @@ along with GCC; see the file COPYING3. If not see
#include "cfgloop.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
+#include "tree-ssa-loop.h"
+#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop-ivopts.h"
#include "tree-ssa-address.h"
#include "dbgcnt.h"
@@ -771,6 +773,132 @@ hash_memrefs_baserefs_and_store_DRs_read_written_info
(data_reference_p a)
}
}
+/* Return TRUE if can prove the index IDX of an array reference REF is
+ within array bound. Return false otherwise. */
+
+static bool
+idx_within_array_bound (tree ref, tree *idx, void *dta)
+{
+ widest_int niter;
+ tree ev, init, step;
+ tree low, high, type, unsigned_type, delta, valid_niter, step_abs, e;
+ bool sign;
+ struct loop *loop = (struct loop*) dta;
+
+ /* Only support within-bound access for array references. */
+ if (TREE_CODE (ref) != ARRAY_REF)
+ return false;
+
+ /* For arrays at the end of the structure, we are not guaranteed that they
+ do not really extend over their declared size. However, for arrays of
+ size greater than one, this is unlikely to be intended. */
+ if (array_at_struct_end_p (ref))
+ return false;
+
+ ev = analyze_scalar_evolution (loop, *idx);
+ ev = instantiate_parameters (loop, ev);
+ init = initial_condition (ev);
+ step = evolution_part_in_loop_num (ev, loop->num);
+
+ if (!init || TREE_CODE (init) != INTEGER_CST
+ || !step || TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
+ return false;
+
+ low = array_ref_low_bound (ref);
+ high = array_ref_up_bound (ref);
+
+ /* The case of nonconstant bounds could be handled, but it would be
+ complicated. */
+ if (TREE_CODE (low) != INTEGER_CST || !integer_zerop (low)
+ || !high || TREE_CODE (high) != INTEGER_CST)
+ return false;
+
+ sign = tree_int_cst_sign_bit (step);
+ type = TREE_TYPE (step);
+
+ /* In case the relevant bound of the array does not fit in type, or
+ it does, but bound + step (in type) still belongs into the range of the
+ array, the index may wrap and still stay within the range of the array
+ (consider e.g. if the array is indexed by the full range of
+ unsigned char).
+
+ To make things simpler, we require both bounds to fit into type, although
+ there are cases where this would not be strictly necessary. */
+ if (!int_fits_type_p (high, type) || !int_fits_type_p (low, type))
+ return false;
+
+ low = fold_convert (type, low);
+ high = fold_convert (type, high);
+
+ /* Check if the first idx is within bound. */
+ if (tree_int_cst_compare (init, low) < 0
+ || tree_int_cst_compare (init, high) > 0)
+ return false;
+
+ /* Don't issue signed overflow warnings. */
+ fold_defer_overflow_warnings ();
+
+ unsigned_type = unsigned_type_for (type);
+ init = fold_convert (unsigned_type, init);
+ if (sign)
+ {
+ tree extreme = fold_convert (unsigned_type, low);
+ delta = fold_build2 (MINUS_EXPR, unsigned_type, init, extreme);
+ step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
+ fold_convert (unsigned_type, step));
+ }
+ else
+ {
+ tree extreme = fold_convert (unsigned_type, high);
+ delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, init);
+ step_abs = fold_convert (unsigned_type, step);
+ }
+ valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
+
+ /* Check if idx is within bound through all niter of loop. */
+ if (max_loop_iterations (loop, &niter)
+ && wi::fits_to_tree_p (niter, TREE_TYPE (valid_niter))
+ && (e = fold_binary (GT_EXPR, boolean_type_node, valid_niter,
+ wide_int_to_tree (TREE_TYPE (valid_niter),
+ niter))) != NULL
+ && integer_nonzerop (e))
+ {
+ fold_undefer_and_ignore_overflow_warnings ();
+ return true;
+ }
+ fold_undefer_and_ignore_overflow_warnings ();
+
+ return false;
+}
+
+/* Return TRUE if ref is a within bound array reference. */
+
+static bool
+ref_within_array_bound (gimple *stmt, tree ref)
+{
+ struct loop *loop = loop_containing_stmt (stmt);
+
+ gcc_assert (loop != NULL);
+ return for_each_index (&ref, idx_within_array_bound, loop);
+}
+
+
+/* Given a memory reference expression T, return TRUE if base object
+ it refers to is writable. The base object of a memory reference
+ is the main object being referenced, which is returned by function
+ get_base_address. */
+
+static bool
+base_object_writable (tree ref)
+{
+ tree base_tree = get_base_address (ref);
+
+ return (base_tree
+ && DECL_P (base_tree)
+ && decl_binds_to_current_def_p (base_tree)
+ && !TREE_READONLY (base_tree));
+}
+
/* Return true when the memory references of STMT won't trap in the
if-converted code. There are two things that we have to check for:
@@ -830,16 +958,20 @@ ifcvt_memrefs_wont_trap (gimple *stmt,
vec<data_reference_p> drs)
if (base_master_dr
&& DR_BASE_W_UNCONDITIONALLY (*base_master_dr))
return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES);
- else
- {
- /* or the base is know to be not readonly. */
- tree base_tree = get_base_address (DR_REF (a));
- if (DECL_P (base_tree)
- && decl_binds_to_current_def_p (base_tree)
- && ! TREE_READONLY (base_tree))
- return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES);
- }
+ /* or the base is known to be not readonly. */
+ else if (base_object_writable (DR_REF (a)))
+ return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES);
}
+
+ /* If a is within-bound array references then ... */
+ if (ref_within_array_bound (stmt, DR_REF (a)))
+ {
+ if (DR_IS_READ (a))
+ return true;
+ else if (base_object_writable (DR_REF (a)))
+ return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES);
+ }
+
return false;
}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-10.c
b/gcc/testsuite/gcc.dg/tree-ssa/ifc-10.c
new file mode 100644
index 0000000..d35b6d4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-10.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-Ofast -fdump-tree-ifcvt-details" } */
+/* { dg-require-visibility "" } */
+
+int b[256] = {0}, y;
+void bar (int *);
+int foo (int x, int n)
+{
+ int i;
+ int a[128];
+
+ for (i = 0; i < n; i++)
+ {
+ a[i] = i;
+ if (x > i)
+ b[i] = y;
+ }
+ bar (a);
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Applying if-conversion" 1 "ifcvt" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-9.c
b/gcc/testsuite/gcc.dg/tree-ssa/ifc-9.c
new file mode 100644
index 0000000..25a28db
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-9.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-Ofast -fdump-tree-ifcvt-details" } */
+/* { dg-require-visibility "" } */
+
+extern int b[256], y;
+void bar (int *, int);
+int foo (int x, int n)
+{
+ int i;
+ int a[128];
+
+ for (i = 0; i < n; i++)
+ {
+ a[i] = i;
+ if (x > i)
+ y = b[i];
+ }
+ bar (a, y);
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Applying if-conversion" 1 "ifcvt" } } */
