This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] if-conversion of loops with conditionals containing memory loads and stores
- From: Sebastian Pop <sebpop at gmail dot com>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>, Richard Guenther <rguenther at suse dot de>
- Date: Tue, 22 Jun 2010 15:17:24 -0500
- Subject: [patch] if-conversion of loops with conditionals containing memory loads and stores
Hi,
The attached patches (on top of the previous patch set) are needed to
if-convert the DCT loop kernel of FFmpeg.
0009 replaces the memory writes that are in predicated basic blocks
with a full write: "if (cond) A[i] = foo" is replaced with "A[i] =
cond ? foo : A[i]". In order to do this, the patch replaces the call
to gimple_assign_rhs_could_trap_p with gimple_could_trap_p, as we now
have to check that the LHS of assign stmts in conditions do not trap.
In order to if-convert the DCT kernel:
for (i = 0; i <= nCoeffs; i++)
{
level = block[i];
if (level)
{
if (level < 0)
{
level = level * qmul - qadd;
}
else
{
level = level * qmul + qadd;
}
block[i] = level;
}
}
0010 proves that the accesses to an array in a loop do not trap (more
(than the original non-if-converted loop)) if they are executed at
every iteration. In this DCT kernel, the read into block[i] happens
at every iteration, and thus the if-converted writes into block[i]
will not trap more than the original code.
The attached patches are the same as previously posted, with the
exception of this part from 0009:
(if_convertible_gimple_assign_stmt_p): Do not handle types that do
not match is_gimple_reg_type.
+ if (!is_gimple_reg_type (TREE_TYPE (lhs)))
+ return false;
+
this makes the patch pass with the extra checks added by Richi to
avoid operands of the COND_EXPR to contain memory loads or stores.
These two patches passed regstrap with BOOT_CFLAGS= -g -O3 -msse2 on
amd64-linux on top of the 8 other patches submitted separately.
Ok for trunk?
Thanks,
Sebastian Pop
--
AMD / Open Source Compiler Engineering / GNU Tools
From 271ec63d648bfb24dc6dc3c720f7a588200689f1 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Thu, 29 Apr 2010 12:09:03 -0500
Subject: [PATCH 09/10] Predicate all the memory writes.
* tree-if-conv.c (if_convertible_phi_p): Allow virtual phi nodes.
(if_convertible_gimple_assign_stmt_p): Allow memory reads and writes.
Do not handle types that do not match is_gimple_reg_type.
Remove loop and bb parameters. Call gimple_could_trap_p instead of
gimple_assign_rhs_could_trap_p, as now LHS can contain memory refs.
(if_convertible_stmt_p): Remove loop and bb parameters. Update calls
to if_convertible_gimple_assign_stmt_p.
(if_convertible_loop_p): Update call to if_convertible_stmt_p.
(gimplify_condition): New.
(find_phi_replacement_condition): Outline gimplify_condition.
Call it.
(replace_phi_with_cond_gimple_assign_stmt): Renamed
predicate_scalar_phi. Do not handle virtual phi nodes.
(process_phi_nodes): Renamed predicate_all_scalar_phis.
Call predicate_scalar_phi.
(predicate_mem_writes): New.
(combine_blocks): Call predicate_all_scalar_phis and
predicate_mem_writes.
(tree_if_conversion): Call mark_sym_for_renaming.
(main_tree_if_conversion): Call update_ssa.
* gcc.dg/tree-ssa/ifc-4.c: New.
* gcc.dg/tree-ssa/ifc-7.c: New.
---
gcc/testsuite/gcc.dg/tree-ssa/ifc-4.c | 53 +++++++++++
gcc/testsuite/gcc.dg/tree-ssa/ifc-7.c | 29 ++++++
gcc/tree-if-conv.c | 153 +++++++++++++++++++--------------
3 files changed, 169 insertions(+), 66 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-4.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-7.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-4.c b/gcc/testsuite/gcc.dg/tree-ssa/ifc-4.c
new file mode 100644
index 0000000..beb1a0e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-4.c
@@ -0,0 +1,53 @@
+/* { dg-do compile } */
+/* { dg-options "-c -O2 -ftree-vectorize -fdump-tree-ifcvt-stats" { target *-*-* } } */
+
+struct ht
+{
+ void * (*alloc_subobject) (int);
+};
+typedef struct cpp_reader cpp_reader;
+typedef struct cpp_token cpp_token;
+typedef struct cpp_macro cpp_macro;
+enum cpp_ttype
+{
+ CPP_PASTE,
+};
+struct cpp_token {
+ __extension__ enum cpp_ttype type : 8;
+} cpp_comment_table;
+struct cpp_macro {
+ union cpp_macro_u
+ {
+ cpp_token * tokens;
+ } exp;
+ unsigned int count;
+};
+struct cpp_reader
+{
+ struct ht *hash_table;
+};
+create_iso_definition (cpp_reader *pfile, cpp_macro *macro)
+{
+ unsigned int num_extra_tokens = 0;
+ {
+ cpp_token *tokns =
+ (cpp_token *) pfile->hash_table->alloc_subobject (sizeof (cpp_token)
+ * macro->count);
+ {
+ cpp_token *normal_dest = tokns;
+ cpp_token *extra_dest = tokns + macro->count - num_extra_tokens;
+ unsigned int i;
+ for (i = 0; i < macro->count; i++)
+ {
+ if (macro->exp.tokens[i].type == CPP_PASTE)
+ *extra_dest++ = macro->exp.tokens[i];
+ else
+ *normal_dest++ = macro->exp.tokens[i];
+ }
+ }
+ }
+}
+
+/* This cannot be if-converted because the stores are to aggregate types. */
+/* { dg-final { scan-tree-dump-times "Applying if-conversion" 0 "ifcvt" } } */
+/* { dg-final { cleanup-tree-dump "ifcvt" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-7.c b/gcc/testsuite/gcc.dg/tree-ssa/ifc-7.c
new file mode 100644
index 0000000..4d26dc7
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-7.c
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-c -O2 -ftree-vectorize" { target *-*-* } } */
+
+typedef struct eqn_d
+{
+ int *coef;
+} *eqn;
+typedef struct omega_pb_d
+{
+ eqn subs;
+} *omega_pb;
+
+omega_pb omega_solve_problem (omega_pb);
+
+omega_pb
+omega_solve_geq (omega_pb pb, int n)
+{
+ int i, e;
+ int j = 0;
+
+ for (e = n - 1; e >= 0; e--)
+ if (pb->subs[e].coef[i] != pb->subs[e].coef[j])
+ {
+ pb->subs[e].coef[i] = j;
+ pb->subs[e].coef[j] = i;
+ }
+
+ return omega_solve_problem (pb);
+}
diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index 759920c..3ae6c85 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -328,9 +328,7 @@ bb_with_exit_edge_p (struct loop *loop, basic_block bb)
and it belongs to basic block BB.
PHI is not if-convertible if:
- - it has more than 2 arguments,
- - virtual PHI is immediately used in another PHI node,
- - virtual PHI on BB other than header. */
+ - it has more than 2 arguments. */
static bool
if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
@@ -348,28 +346,6 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
return false;
}
- if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi))))
- {
- imm_use_iterator imm_iter;
- use_operand_p use_p;
-
- if (bb != loop->header)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Virtual phi not on loop header.\n");
- return false;
- }
- FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
- {
- if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Difficult to handle this virtual phi.\n");
- return false;
- }
- }
- }
-
return true;
}
@@ -378,13 +354,10 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
GIMPLE_ASSIGN statement is not if-convertible if,
- it is not movable,
- it could trap,
- - LHS is not var decl.
-
- GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */
+ - LHS is not var decl. */
static bool
-if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
- gimple stmt)
+if_convertible_gimple_assign_stmt_p (gimple stmt)
{
tree lhs = gimple_assign_lhs (stmt);
@@ -394,6 +367,9 @@ if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
+ if (!is_gimple_reg_type (TREE_TYPE (lhs)))
+ return false;
+
/* Some of these constrains might be too conservative. */
if (stmt_ends_bb_p (stmt)
|| gimple_has_volatile_ops (stmt)
@@ -406,25 +382,13 @@ if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
return false;
}
- if (gimple_assign_rhs_could_trap_p (stmt))
+ if (gimple_could_trap_p (stmt))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "tree could trap...\n");
return false;
}
- if (TREE_CODE (lhs) != SSA_NAME
- && bb != loop->header
- && !bb_with_exit_edge_p (loop, bb))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "LHS is not var\n");
- print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
- }
- return false;
- }
-
return true;
}
@@ -432,12 +396,10 @@ if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
A statement is if-convertible if:
- it is an if-convertible GIMPLE_ASSGIN,
- - it is a GIMPLE_LABEL or a GIMPLE_COND.
-
- STMT is inside BB, which is inside loop LOOP. */
+ - it is a GIMPLE_LABEL or a GIMPLE_COND. */
static bool
-if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
+if_convertible_stmt_p (gimple stmt)
{
switch (gimple_code (stmt))
{
@@ -447,7 +409,7 @@ if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
return true;
case GIMPLE_ASSIGN:
- return if_convertible_gimple_assign_stmt_p (loop, bb, stmt);
+ return if_convertible_gimple_assign_stmt_p (stmt);
default:
/* Don't know what to do with 'em so don't do anything. */
@@ -818,7 +780,7 @@ if_convertible_loop_p (struct loop *loop)
continue;
for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
- if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
+ if (!if_convertible_stmt_p (gsi_stmt (itr)))
return false;
}
@@ -838,7 +800,7 @@ if_convertible_loop_p (struct loop *loop)
static basic_block
find_phi_replacement_condition (struct loop *loop,
basic_block bb, tree *cond,
- gimple_stmt_iterator *gsi)
+ gimple_stmt_iterator *gsi)
{
edge first_edge, second_edge;
tree tmp_cond;
@@ -923,8 +885,9 @@ find_phi_replacement_condition (struct loop *loop,
return first_edge->src;
}
-/* Replace PHI node with conditional modify expr using COND. This
- routine does not handle PHI nodes with more than two arguments.
+/* Replace a scalar PHI node with a COND_EXPR using COND as condition.
+ This routine does not handle PHI nodes with more than two
+ arguments.
For example,
S1: A = PHI <x1(1), x2(5)
@@ -936,18 +899,22 @@ find_phi_replacement_condition (struct loop *loop,
TRUE_BB is selected. */
static void
-replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
- basic_block true_bb,
- gimple_stmt_iterator *gsi)
+predicate_scalar_phi (gimple phi, tree cond,
+ basic_block true_bb,
+ gimple_stmt_iterator *gsi)
{
gimple new_stmt;
basic_block bb;
- tree rhs;
- tree arg;
+ tree rhs, res, arg;
gcc_assert (gimple_code (phi) == GIMPLE_PHI
&& gimple_phi_num_args (phi) == 2);
+ res = gimple_phi_result (phi);
+ /* Do not handle virtual phi nodes. */
+ if (!is_gimple_reg (SSA_NAME_VAR (res)))
+ return;
+
bb = gimple_bb (phi);
arg = degenerate_phi_result (phi);
@@ -969,11 +936,11 @@ replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
}
/* Build new RHS using selected condition and arguments. */
- rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
+ rhs = build3 (COND_EXPR, TREE_TYPE (res),
unshare_expr (cond), arg_0, arg_1);
}
- new_stmt = gimple_build_assign (PHI_RESULT (phi), rhs);
+ new_stmt = gimple_build_assign (res, rhs);
SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
update_stmt (new_stmt);
@@ -985,11 +952,11 @@ replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
}
}
-/* Replaces in LOOP all the phi nodes other than those in the
+/* Replaces in LOOP all the scalar phi nodes other than those in the
LOOP->header block with conditional modify expressions. */
static void
-ifconvert_phi_nodes (struct loop *loop)
+predicate_all_scalar_phis (struct loop *loop)
{
basic_block bb;
unsigned int orig_loop_num_nodes = loop->num_nodes;
@@ -1018,7 +985,7 @@ ifconvert_phi_nodes (struct loop *loop)
while (!gsi_end_p (phi_gsi))
{
phi = gsi_stmt (phi_gsi);
- replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
+ predicate_scalar_phi (phi, cond, true_bb, &gsi);
release_phi_node (phi);
gsi_next (&phi_gsi);
}
@@ -1039,6 +1006,7 @@ insert_gimplified_predicates (loop_p loop)
{
basic_block bb = ifc_bbs[i];
gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
+ gimple_stmt_iterator gsi = gsi_after_labels (bb);
if (!is_predicated (bb))
{
@@ -1051,8 +1019,6 @@ insert_gimplified_predicates (loop_p loop)
if (stmts)
{
- gimple_stmt_iterator gsi = gsi_after_labels (bb);
-
gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
/* Once the sequence is code generated, set it to NULL. */
@@ -1061,6 +1027,56 @@ insert_gimplified_predicates (loop_p loop)
}
}
+/* Predicate each write to memory in LOOP.
+
+ Replace a statement "A[i] = foo" with "A[i] = cond ? foo : A[i]"
+ with the condition COND determined from the predicate of the basic
+ block containing the statement. */
+
+static void
+predicate_mem_writes (loop_p loop)
+{
+ unsigned int i, orig_loop_num_nodes = loop->num_nodes;
+
+ for (i = 1; i < orig_loop_num_nodes; i++)
+ {
+ gimple_stmt_iterator gsi;
+ basic_block bb = ifc_bbs[i];
+ tree cond = bb_predicate (bb);
+
+ if (is_true_predicate (cond))
+ continue;
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ if (is_gimple_assign (gsi_stmt (gsi))
+ && gimple_vdef (gsi_stmt (gsi)))
+ {
+ gimple new_stmt, lhs_stmt, rhs_stmt;
+ gimple stmt = gsi_stmt (gsi);
+ tree lhs = gimple_get_lhs (stmt);
+ tree rhs = gimple_op (stmt, 1);
+
+ gcc_assert (gimple_num_ops (stmt) == 2);
+
+ rhs_stmt = ifc_temp_var (TREE_TYPE (rhs), unshare_expr (rhs));
+ gsi_insert_before (&gsi, rhs_stmt, GSI_SAME_STMT);
+ rhs = gimple_get_lhs (rhs_stmt);
+
+ lhs_stmt = ifc_temp_var (TREE_TYPE (lhs), unshare_expr (lhs));
+ gsi_insert_before (&gsi, lhs_stmt, GSI_SAME_STMT);
+ lhs = gimple_get_lhs (lhs_stmt);
+
+ cond = unshare_expr (cond);
+ rhs = build3 (COND_EXPR, TREE_TYPE (lhs), cond, rhs, lhs);
+
+ new_stmt = ifc_temp_var (TREE_TYPE (lhs), rhs);
+ gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
+ gimple_set_op (stmt, 1, gimple_get_lhs (new_stmt));
+ update_stmt (stmt);
+ }
+ }
+}
+
/* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
other than the exit and latch of the LOOP. Also resets the
GIMPLE_DEBUG information. */
@@ -1117,7 +1133,8 @@ combine_blocks (struct loop *loop)
remove_conditions_and_labels (loop);
insert_gimplified_predicates (loop);
- ifconvert_phi_nodes (loop);
+ predicate_all_scalar_phis (loop);
+ predicate_mem_writes (loop);
/* Merge basic blocks: first remove all the edges in the loop,
except for those from the exit block. */
@@ -1219,6 +1236,7 @@ tree_if_conversion (struct loop *loop)
blocks into one huge basic block doing the if-conversion
on-the-fly. */
combine_blocks (loop);
+ mark_sym_for_renaming (gimple_vop (cfun));
changed = true;
cleanup:
@@ -1252,7 +1270,10 @@ main_tree_if_conversion (void)
changed |= tree_if_conversion (loop);
if (changed)
- cleanup_tree_cfg ();
+ {
+ cleanup_tree_cfg ();
+ update_ssa (TODO_update_ssa);
+ }
#ifdef ENABLE_CHECKING
verify_loop_structure ();
--
1.7.0.4
From d260c90bc66d257ee5c410c05f713cb6ab0c268c Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Thu, 20 May 2010 16:23:17 -0500
Subject: [PATCH 10/10] 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): New.
* tree-if-conv.c (is_true_predicate): New.
(is_predicated): Call is_true_predicate.
(ifcvt_memrefs_will_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 | 31 +++++++
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 | 24 +++++
gcc/tree-if-conv.c | 150 +++++++++++++++++++++++++------
9 files changed, 206 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 1a10f31..b2082a0 100644
--- a/gcc/gimple.c
+++ b/gcc/gimple.c
@@ -2365,24 +2365,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))
{
@@ -2411,7 +2401,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 210a622..371cede 100644
--- a/gcc/gimple.h
+++ b/gcc/gimple.h
@@ -879,6 +879,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..2ca1ac9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-5.c
@@ -0,0 +1,31 @@
+/* { 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)
+ {
+ 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..95a734a 100644
--- a/gcc/tree-data-ref.h
+++ b/gcc/tree-data-ref.h
@@ -417,6 +417,30 @@ 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 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 (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 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 3ae6c85..9ee276f 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -349,6 +349,96 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
return true;
}
+/* Return true when the memory references of STMT will trap in the
+ if-converted code: i.e., when the data references of STMT are
+ executed unconditionally in the loop it is possible to say that in
+ the if-converted code there will not be more traps than in the
+ original non if-converted code. Supposing that the data refs are
+ accessed in basic blocks predicated differently, if it is possible
+ to prove that the same data references are executed at every
+ iteration, then the if-converted code won't have more traps than
+ the original code. */
+
+static bool
+ifcvt_memrefs_will_trap (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 true;
+ }
+
+ return false;
+}
+
+/* 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_will_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 +447,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 +473,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 +490,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 +500,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 +783,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 +823,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);
-
- free_data_refs (refs);
- free_dependence_relations (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);
- 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 +839,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 +847,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 +867,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;
+ goto cleanup;
- /* For non predicated BBs, don't check their statements. */
- if (!is_predicated (bb))
- continue;
-
- 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