This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] if-conversion of loops with conditionals containing memory loads and stores
On Wed, Jun 23, 2010 at 15:05, Sebastian Pop <sebpop@gmail.com> wrote:
> On Wed, Jun 23, 2010 at 14:04, Joseph S. Myers <joseph@codesourcery.com> wrote:
>> Not just the C++0x memory model, but you also need to be sure that A[i] is
>> a valid pointer to writable memory - not an out-of-range or unaligned
>> pointer (if A[i] is always *read*, you can be sure of that, and simply
>> forming the address &A[i] means it is either valid or one past the end of
>> an array),
>
> The patch 0010 tries to prove that the data reference A[i] occurs either
> in read or write mode at every iteration of the loop.
>
>> not a pointer to readonly memory (remember that in C it's valid
>> to cast a pointer-to-const to pointer-to-non-const, so just because the
>> target type isn't const qualified doesn't mean you can actually write to
>> the memory).
>
> I have not checked this. ?So if I understand correctly, to prove that
> an array is not const qualified, one has to prove that there exists at
> least one unconditional write to the array.
>
The attached patch implements the missing check for writable memory:
for every predicated write to memory, we check that there exists an
unconditional write to the same base object.
This passed regression test on amd64-linux. Ok with these changes?
Thanks,
Sebastian Pop
--
AMD / Open Source Compiler Engineering / GNU Tools
From 4fa1128f635fc3afcb1df7bcf4ab543343a203ef Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Thu, 20 May 2010 16:23:17 -0500
Subject: [PATCH 5/5] Do not check whether memory references accessed in every iteration trap.
* gimple.c (gimple_op_could_trap_p): Outlined from
gimple_could_trap_p_1.
(gimple_could_trap_p_1): Call gimple_op_could_trap_p.
* gimple.h (gimple_op_could_trap_p): Declared.
* tree-data-ref.h (same_data_refs_base_objects): New.
(same_data_refs): New.
* tree-if-conv.c (is_true_predicate): New.
(is_predicated): Call is_true_predicate.
(memrefs_read_or_written_unconditionally): New.
(write_memrefs_written_at_least_once): New.
(ifcvt_memrefs_wont_trap): New.
(operations_could_trap): New.
(ifcvt_could_trap_p): New.
(if_convertible_gimple_assign_stmt_p): Call ifcvt_could_trap_p.
Gets a vector of data refs.
(if_convertible_stmt_p): Same.
(if_convertible_loop_p): Before freeing the data refs vector,
pass it to if_convertible_stmt_p.
* gcc.dg/tree-ssa/ifc-5.c: New.
* gcc.dg/vect/vect-ifcvt-18.c: XFail-ed.
* gcc.dg/vect/vect-cond-1.c: Update pattern.
* gcc.dg/vect/vect-cond-3.c: Same.
* gcc.dg/vect/vect-cond-4.c: Same.
* gcc.dg/vect/vect-cond-6.c: Same.
---
gcc/gimple.c | 38 ++++--
gcc/gimple.h | 1 +
gcc/testsuite/gcc.dg/tree-ssa/ifc-5.c | 24 ++++
gcc/testsuite/gcc.dg/vect/vect-cond-1.c | 2 +-
gcc/testsuite/gcc.dg/vect/vect-cond-3.c | 2 +-
gcc/testsuite/gcc.dg/vect/vect-cond-4.c | 2 +-
gcc/testsuite/gcc.dg/vect/vect-cond-6.c | 1 +
gcc/tree-data-ref.h | 34 +++++
gcc/tree-if-conv.c | 212 +++++++++++++++++++++++++++----
9 files changed, 271 insertions(+), 45 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-5.c
diff --git a/gcc/gimple.c b/gcc/gimple.c
index 0a5f6fb..8bd3530 100644
--- a/gcc/gimple.c
+++ b/gcc/gimple.c
@@ -2382,24 +2382,14 @@ gimple_rhs_has_side_effects (const_gimple s)
return false;
}
+/* Helper for gimple_could_trap_p_1. Return true if the operation of
+ S can trap. */
-/* Helper for gimple_could_trap_p and gimple_assign_rhs_could_trap_p.
- Return true if S can trap. If INCLUDE_LHS is true and S is a
- GIMPLE_ASSIGN, the LHS of the assignment is also checked.
- Otherwise, only the RHS of the assignment is checked. */
-
-static bool
-gimple_could_trap_p_1 (gimple s, bool include_lhs)
+bool
+gimple_op_could_trap_p (gimple s)
{
- unsigned i, start;
- tree t, div = NULL_TREE;
enum tree_code op;
-
- start = (is_gimple_assign (s) && !include_lhs) ? 1 : 0;
-
- for (i = start; i < gimple_num_ops (s); i++)
- if (tree_could_trap_p (gimple_op (s, i)))
- return true;
+ tree t, div = NULL_TREE;
switch (gimple_code (s))
{
@@ -2428,7 +2418,25 @@ gimple_could_trap_p_1 (gimple s, bool include_lhs)
}
return false;
+}
+
+/* Helper for gimple_could_trap_p and gimple_assign_rhs_could_trap_p.
+ Return true if S can trap. If INCLUDE_LHS is true and S is a
+ GIMPLE_ASSIGN, the LHS of the assignment is also checked.
+ Otherwise, only the RHS of the assignment is checked. */
+
+static bool
+gimple_could_trap_p_1 (gimple s, bool include_lhs)
+{
+ unsigned i, start;
+
+ start = (is_gimple_assign (s) && !include_lhs) ? 1 : 0;
+
+ for (i = start; i < gimple_num_ops (s); i++)
+ if (tree_could_trap_p (gimple_op (s, i)))
+ return true;
+ return gimple_op_could_trap_p (s);
}
diff --git a/gcc/gimple.h b/gcc/gimple.h
index ffc3441..386f44f 100644
--- a/gcc/gimple.h
+++ b/gcc/gimple.h
@@ -886,6 +886,7 @@ gimple gimple_build_cond_from_tree (tree, tree, tree);
void gimple_cond_set_condition_from_tree (gimple, tree);
bool gimple_has_side_effects (const_gimple);
bool gimple_rhs_has_side_effects (const_gimple);
+bool gimple_op_could_trap_p (gimple);
bool gimple_could_trap_p (gimple);
bool gimple_assign_rhs_could_trap_p (gimple);
void gimple_regimplify_operands (gimple, gimple_stmt_iterator *);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-5.c b/gcc/testsuite/gcc.dg/tree-ssa/ifc-5.c
new file mode 100644
index 0000000..a9cc816
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-5.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-options "-c -O2 -ftree-vectorize -fdump-tree-ifcvt-stats" { target *-*-* } } */
+
+void
+dct_unquantize_h263_inter_c (short *block, int n, int qscale, int nCoeffs)
+{
+ int i, level, qmul, qadd;
+
+ qadd = (qscale - 1) | 1;
+ qmul = qscale << 1;
+
+ for (i = 0; i <= nCoeffs; i++)
+ {
+ level = block[i];
+ if (level < 0)
+ level = level * qmul - qadd;
+ else
+ level = level * qmul + qadd;
+ block[i] = level;
+ }
+}
+
+/* { dg-final { scan-tree-dump-times "Applying if-conversion" 1 "ifcvt" } } */
+/* { dg-final { cleanup-tree-dump "ifcvt" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-cond-1.c b/gcc/testsuite/gcc.dg/vect/vect-cond-1.c
index 4ee6713..888e5cb 100644
--- a/gcc/testsuite/gcc.dg/vect/vect-cond-1.c
+++ b/gcc/testsuite/gcc.dg/vect/vect-cond-1.c
@@ -52,7 +52,7 @@ int main (void)
return 0;
}
-/* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 1 "vect" { xfail vect_no_align } } } */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" } } */
/* { dg-final { cleanup-tree-dump "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-cond-3.c b/gcc/testsuite/gcc.dg/vect/vect-cond-3.c
index 56cfbb2..42b9f35 100644
--- a/gcc/testsuite/gcc.dg/vect/vect-cond-3.c
+++ b/gcc/testsuite/gcc.dg/vect/vect-cond-3.c
@@ -60,7 +60,7 @@ int main (void)
return 0;
}
-/* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 1 "vect" { xfail vect_no_align } } } */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" } } */
/* { dg-final { cleanup-tree-dump "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-cond-4.c b/gcc/testsuite/gcc.dg/vect/vect-cond-4.c
index c3a1585..1d1d8fc 100644
--- a/gcc/testsuite/gcc.dg/vect/vect-cond-4.c
+++ b/gcc/testsuite/gcc.dg/vect/vect-cond-4.c
@@ -57,7 +57,7 @@ int main (void)
return 0;
}
-/* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 1 "vect" { xfail vect_no_align } } } */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" } } */
/* { dg-final { cleanup-tree-dump "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-cond-6.c b/gcc/testsuite/gcc.dg/vect/vect-cond-6.c
index e5e9391..7820444 100644
--- a/gcc/testsuite/gcc.dg/vect/vect-cond-6.c
+++ b/gcc/testsuite/gcc.dg/vect/vect-cond-6.c
@@ -56,5 +56,6 @@ int main ()
}
/* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 1 "vect" } } */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
/* { dg-final { cleanup-tree-dump "vect" } } */
diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h
index eff5348..391d6fc 100644
--- a/gcc/tree-data-ref.h
+++ b/gcc/tree-data-ref.h
@@ -417,6 +417,40 @@ extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *);
extern bool dr_may_alias_p (const struct data_reference *,
const struct data_reference *);
+
+/* Return true when the base objects of data references A and B are
+ the same memory object. */
+
+static inline bool
+same_data_refs_base_objects (data_reference_p a, data_reference_p b)
+{
+ return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
+ && dr_may_alias_p (a, b)
+ && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
+}
+
+/* Return true when the data references A and B are accessing the same
+ memory object with the same access functions. */
+
+static inline bool
+same_data_refs (data_reference_p a, data_reference_p b)
+{
+ unsigned int i;
+
+ /* The references are exactly the same. */
+ if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
+ return true;
+
+ if (!same_data_refs_base_objects (a, b))
+ return false;
+
+ for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
+ if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
+ return false;
+
+ return true;
+}
+
/* Return true when the DDR contains two data references that have the
same access functions. */
diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index 8d72a97..7ae61e6 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -349,6 +349,158 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
return true;
}
+/* Returns true when the memory references of STMT are read or written
+ unconditionally. */
+
+static bool
+memrefs_read_or_written_unconditionally (gimple stmt,
+ VEC (data_reference_p, heap) *refs)
+{
+ struct data_reference *a, *b;
+ unsigned int i, j;
+ tree cond = unfold_ssa_names (bb_predicate (gimple_bb (stmt)), 5);
+
+ for (i = 0; VEC_iterate (data_reference_p, refs, i, a); i++)
+ if (DR_STMT (a) == stmt)
+ {
+ for (j = 0; VEC_iterate (data_reference_p, refs, j, b); j++)
+ if (i != j && same_data_refs (a, b))
+ {
+ basic_block bb;
+
+ if (!is_predicated (gimple_bb (DR_STMT (b))))
+ {
+ cond = boolean_true_node;
+ break;
+ }
+
+ bb = gimple_bb (DR_STMT (b));
+ cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, cond,
+ unfold_ssa_names (bb_predicate (bb), 5));
+
+ if (is_true_predicate (cond))
+ break;
+ }
+
+ if (!is_true_predicate (cond))
+ return false;
+ }
+
+ return true;
+}
+
+/* Returns true when the memory references of STMT are unconditionally
+ written. */
+
+static bool
+write_memrefs_written_at_least_once (gimple stmt,
+ VEC (data_reference_p, heap) *refs)
+{
+ struct data_reference *a, *b;
+ unsigned int i, j;
+ tree cond = unfold_ssa_names (bb_predicate (gimple_bb (stmt)), 5);
+
+ for (i = 0; VEC_iterate (data_reference_p, refs, i, a); i++)
+ if (DR_STMT (a) == stmt
+ && !DR_IS_READ (a))
+ {
+ for (j = 0; VEC_iterate (data_reference_p, refs, j, b); j++)
+ if (i != j
+ && !DR_IS_READ (b)
+ && same_data_refs_base_objects (a, b))
+ {
+ basic_block bb;
+
+ if (!is_predicated (gimple_bb (DR_STMT (b))))
+ {
+ cond = boolean_true_node;
+ break;
+ }
+
+ bb = gimple_bb (DR_STMT (b));
+ cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, cond,
+ unfold_ssa_names (bb_predicate (bb), 5));
+
+ if (is_true_predicate (cond))
+ break;
+ }
+
+ if (!is_true_predicate (cond))
+ return false;
+ }
+
+ return true;
+}
+
+/* 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:
+
+ - writes to memory occur to writable memory: if-conversion of
+ memory writes transforms the conditional memory writes into
+ unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
+ into "A[i] = cond ? foo : A[i]", and as the write to memory may not
+ be executed at all in the original code, it may be a readonly
+ memory. To check that A is not const-qualified, we check that
+ there exists at least an unconditional write to A in the current
+ function.
+
+ - reads or writes to memory are valid memory accesses for every
+ iteration. To check that the memory accesses are correctly formed
+ and that we are allowed to read and write in these locations, we
+ check that the memory accesses to be if-converted occur at every
+ iteration unconditionally. */
+
+static bool
+ifcvt_memrefs_wont_trap (gimple stmt, VEC (data_reference_p, heap) *refs)
+{
+ return write_memrefs_written_at_least_once (stmt, refs)
+ && memrefs_read_or_written_unconditionally (stmt, refs);
+}
+
+/* Same as gimple_could_trap_p_1, returns true when the statement S
+ could trap, but do not check the memory references. */
+
+static bool
+operations_could_trap (gimple s)
+{
+ unsigned i;
+
+ for (i = 0; i < gimple_num_ops (s); i++)
+ {
+ tree expr = gimple_op (s, i);
+
+ switch (TREE_CODE (expr))
+ {
+ case ARRAY_REF:
+ case INDIRECT_REF:
+ case ALIGN_INDIRECT_REF:
+ case MISALIGNED_INDIRECT_REF:
+ break;
+
+ default:
+ if (tree_could_trap_p (expr))
+ return true;
+ }
+ }
+
+ return gimple_op_could_trap_p (s);
+}
+
+/* Wrapper around gimple_could_trap_p refined for the needs of the
+ if-conversion. Try to prove that the memory accesses of STMT could
+ not trap in the innermost loop containing STMT. */
+
+static bool
+ifcvt_could_trap_p (gimple stmt, VEC (data_reference_p, heap) *refs)
+{
+ if (gimple_has_mem_ops (stmt)
+ && ifcvt_memrefs_wont_trap (stmt, refs)
+ && !operations_could_trap (stmt))
+ return false;
+
+ return gimple_could_trap_p (stmt);
+}
+
/* Return true when STMT is if-convertible.
GIMPLE_ASSIGN statement is not if-convertible if,
@@ -357,7 +509,8 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
- LHS is not var decl. */
static bool
-if_convertible_gimple_assign_stmt_p (gimple stmt)
+if_convertible_gimple_assign_stmt_p (gimple stmt,
+ VEC (data_reference_p, heap) *refs)
{
tree lhs = gimple_assign_lhs (stmt);
@@ -382,7 +535,7 @@ if_convertible_gimple_assign_stmt_p (gimple stmt)
return false;
}
- if (gimple_could_trap_p (stmt))
+ if (ifcvt_could_trap_p (stmt, refs))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "tree could trap...\n");
@@ -399,7 +552,7 @@ if_convertible_gimple_assign_stmt_p (gimple stmt)
- it is a GIMPLE_LABEL or a GIMPLE_COND. */
static bool
-if_convertible_stmt_p (gimple stmt)
+if_convertible_stmt_p (gimple stmt, VEC (data_reference_p, heap) *refs)
{
switch (gimple_code (stmt))
{
@@ -409,7 +562,7 @@ if_convertible_stmt_p (gimple stmt)
return true;
case GIMPLE_ASSIGN:
- return if_convertible_gimple_assign_stmt_p (stmt);
+ return if_convertible_gimple_assign_stmt_p (stmt, refs);
default:
/* Don't know what to do with 'em so don't do anything. */
@@ -692,6 +845,9 @@ if_convertible_loop_p (struct loop *loop)
edge e;
edge_iterator ei;
basic_block exit_bb = NULL;
+ bool res = false;
+ VEC (data_reference_p, heap) *refs;
+ VEC (ddr_p, heap) *ddrs;
/* Handle only innermost loop. */
if (!loop || loop->inner)
@@ -729,18 +885,14 @@ if_convertible_loop_p (struct loop *loop)
/* Don't if-convert the loop when the data dependences cannot be
computed: the loop won't be vectorized in that case. */
- {
- VEC (data_reference_p, heap) *refs = VEC_alloc (data_reference_p, heap, 5);
- VEC (ddr_p, heap) *ddrs = VEC_alloc (ddr_p, heap, 25);
- bool res = compute_data_dependences_for_loop (loop, true, &refs, &ddrs);
+ refs = VEC_alloc (data_reference_p, heap, 5);
+ ddrs = VEC_alloc (ddr_p, heap, 25);
+ res = compute_data_dependences_for_loop (loop, true, &refs, &ddrs);
- free_data_refs (refs);
- free_dependence_relations (ddrs);
-
- if (!res)
- return false;
- }
+ if (!res)
+ goto cleanup;
+ res = false;
calculate_dominance_info (CDI_DOMINATORS);
/* Allow statements that can be handled during if-conversion. */
@@ -749,7 +901,7 @@ if_convertible_loop_p (struct loop *loop)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Irreducible loop\n");
- return false;
+ goto cleanup;
}
for (i = 0; i < loop->num_nodes; i++)
@@ -757,14 +909,18 @@ if_convertible_loop_p (struct loop *loop)
basic_block bb = ifc_bbs[i];
if (!if_convertible_bb_p (loop, bb, exit_bb))
- return false;
+ goto cleanup;
if (bb_with_exit_edge_p (loop, bb))
exit_bb = bb;
}
- if (!predicate_bbs (loop))
- return false;
+ res = predicate_bbs (loop);
+
+ if (!res)
+ goto cleanup;
+
+ res = false;
for (i = 0; i < loop->num_nodes; i++)
{
@@ -773,21 +929,23 @@ if_convertible_loop_p (struct loop *loop)
for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
- return false;
-
- /* For non predicated BBs, don't check their statements. */
- if (!is_predicated (bb))
- continue;
+ goto cleanup;
- for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
- if (!if_convertible_stmt_p (gsi_stmt (itr)))
- return false;
+ /* Check the if-convertibility of statements in predicated BBs. */
+ if (is_predicated (bb))
+ for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
+ if (!if_convertible_stmt_p (gsi_stmt (itr), refs))
+ goto cleanup;
}
+ res = true;
if (dump_file)
fprintf (dump_file, "Applying if-conversion\n");
- return true;
+ cleanup:
+ free_data_refs (refs);
+ free_dependence_relations (ddrs);
+ return res;
}
/* Basic block BB has two predecessors. Using predecessor's bb
--
1.7.0.4