/* If-conversion for vectorizer.
- Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
+ Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
Free Software Foundation, Inc.
Contributed by Devang Patel <dpatel@apple.com>
static inline void
set_bb_predicate (basic_block bb, tree cond)
{
+ gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
+ && is_gimple_condexpr (TREE_OPERAND (cond, 0)))
+ || is_gimple_condexpr (cond));
((bb_predicate_p) bb->aux)->predicate = cond;
}
static inline void
add_to_predicate_list (basic_block bb, tree nc)
{
- tree bc;
+ tree bc, *tp;
if (is_true_predicate (nc))
return;
{
bc = bb_predicate (bb);
bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
+ if (is_true_predicate (bc))
+ {
+ reset_bb_predicate (bb);
+ return;
+ }
}
- if (!is_gimple_condexpr (bc))
+ /* Allow a TRUTH_NOT_EXPR around the main predicate. */
+ if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
+ tp = &TREE_OPERAND (bc, 0);
+ else
+ tp = &bc;
+ if (!is_gimple_condexpr (*tp))
{
gimple_seq stmts;
- bc = force_gimple_operand (bc, &stmts, true, NULL_TREE);
+ *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE);
add_bb_predicate_gimplified_stmts (bb, stmts);
}
-
- if (is_true_predicate (bc))
- reset_bb_predicate (bb);
- else
- set_bb_predicate (bb, bc);
+ set_bb_predicate (bb, bc);
}
/* Add the condition COND to the previous condition PREV_COND, and add
return true;
}
+/* Records the status of a data reference. This struct is attached to
+ each DR->aux field. */
+
+struct ifc_dr {
+ /* -1 when not initialized, 0 when false, 1 when true. */
+ int written_at_least_once;
+
+ /* -1 when not initialized, 0 when false, 1 when true. */
+ int rw_unconditionally;
+};
+
+#define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
+#define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
+#define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
+
+/* Returns true when the memory references of STMT are read or written
+ unconditionally. In other words, this function returns true when
+ for every data reference A in STMT there exist other accesses to
+ a data reference with the same base with predicates that add up (OR-up) to
+ the true predicate: this ensures that the data reference A is touched
+ (read or written) on every iteration of the if-converted loop. */
+
+static bool
+memrefs_read_or_written_unconditionally (gimple stmt,
+ VEC (data_reference_p, heap) *drs)
+{
+ int i, j;
+ data_reference_p a, b;
+ tree ca = bb_predicate (gimple_bb (stmt));
+
+ for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++)
+ if (DR_STMT (a) == stmt)
+ {
+ bool found = false;
+ int x = DR_RW_UNCONDITIONALLY (a);
+
+ if (x == 0)
+ return false;
+
+ if (x == 1)
+ continue;
+
+ for (j = 0; VEC_iterate (data_reference_p, drs, j, b); j++)
+ {
+ tree ref_base_a = DR_REF (a);
+ tree ref_base_b = DR_REF (b);
+
+ if (DR_STMT (b) == stmt)
+ continue;
+
+ while (TREE_CODE (ref_base_a) == COMPONENT_REF
+ || TREE_CODE (ref_base_a) == IMAGPART_EXPR
+ || TREE_CODE (ref_base_a) == REALPART_EXPR)
+ ref_base_a = TREE_OPERAND (ref_base_a, 0);
+
+ while (TREE_CODE (ref_base_b) == COMPONENT_REF
+ || TREE_CODE (ref_base_b) == IMAGPART_EXPR
+ || TREE_CODE (ref_base_b) == REALPART_EXPR)
+ ref_base_b = TREE_OPERAND (ref_base_b, 0);
+
+ if (!operand_equal_p (ref_base_a, ref_base_b, 0))
+ {
+ tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
+
+ if (DR_RW_UNCONDITIONALLY (b) == 1
+ || is_true_predicate (cb)
+ || is_true_predicate (ca
+ = fold_or_predicates (EXPR_LOCATION (cb), ca, cb)))
+ {
+ DR_RW_UNCONDITIONALLY (a) = 1;
+ DR_RW_UNCONDITIONALLY (b) = 1;
+ found = true;
+ break;
+ }
+ }
+ }
+
+ if (!found)
+ {
+ DR_RW_UNCONDITIONALLY (a) = 0;
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/* Returns true when the memory references of STMT are unconditionally
+ written. In other words, this function returns true when for every
+ data reference A written in STMT, there exist other writes to the
+ same data reference with predicates that add up (OR-up) to the true
+ predicate: this ensures that the data reference A is written on
+ every iteration of the if-converted loop. */
+
+static bool
+write_memrefs_written_at_least_once (gimple stmt,
+ VEC (data_reference_p, heap) *drs)
+{
+ int i, j;
+ data_reference_p a, b;
+ tree ca = bb_predicate (gimple_bb (stmt));
+
+ for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++)
+ if (DR_STMT (a) == stmt
+ && DR_IS_WRITE (a))
+ {
+ bool found = false;
+ int x = DR_WRITTEN_AT_LEAST_ONCE (a);
+
+ if (x == 0)
+ return false;
+
+ if (x == 1)
+ continue;
+
+ for (j = 0; VEC_iterate (data_reference_p, drs, j, b); j++)
+ if (DR_STMT (b) != stmt
+ && DR_IS_WRITE (b)
+ && same_data_refs_base_objects (a, b))
+ {
+ tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
+
+ if (DR_WRITTEN_AT_LEAST_ONCE (b) == 1
+ || is_true_predicate (cb)
+ || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb),
+ ca, cb)))
+ {
+ DR_WRITTEN_AT_LEAST_ONCE (a) = 1;
+ DR_WRITTEN_AT_LEAST_ONCE (b) = 1;
+ found = true;
+ break;
+ }
+ }
+
+ if (!found)
+ {
+ DR_WRITTEN_AT_LEAST_ONCE (a) = 0;
+ 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);
+}
+
+/* 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_vuse (stmt)
+ && !gimple_could_trap_p_1 (stmt, false, false)
+ && ifcvt_memrefs_wont_trap (stmt, refs))
+ return false;
+
+ return gimple_could_trap_p (stmt);
+}
+
/* Return true when STMT is if-convertible.
GIMPLE_ASSIGN statement is not if-convertible if,
- 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);
basic_block bb;
if (flag_tree_loop_if_convert_stores)
{
- 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");
- 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))
{
return true;
case GIMPLE_ASSIGN:
- return if_convertible_gimple_assign_stmt_p (stmt);
+ return if_convertible_gimple_assign_stmt_p (stmt, refs);
+
+ case GIMPLE_CALL:
+ {
+ tree fndecl = gimple_call_fndecl (stmt);
+ if (fndecl)
+ {
+ int flags = gimple_call_flags (stmt);
+ if ((flags & ECF_CONST)
+ && !(flags & ECF_LOOPING_CONST_OR_PURE)
+ /* We can only vectorize some builtins at the moment,
+ so restrict if-conversion to those. */
+ && DECL_BUILT_IN (fndecl))
+ return true;
+ }
+ return false;
+ }
default:
/* Don't know what to do with 'em so don't do anything. */
return true;
}
+/* Return true when BB post-dominates all its predecessors. */
+
+static bool
+bb_postdominates_preds (basic_block bb)
+{
+ unsigned i;
+
+ for (i = 0; i < EDGE_COUNT (bb->preds); i++)
+ if (!dominated_by_p (CDI_POST_DOMINATORS, EDGE_PRED (bb, i)->src, bb))
+ return false;
+
+ return true;
+}
+
/* Return true when BB is if-convertible. This routine does not check
basic block's statements and phis.
return false;
}
+ if (EDGE_COUNT (bb->preds) == 2
+ && bb != loop->header
+ && !bb_postdominates_preds (bb))
+ return false;
+
return true;
}
}
cond = bb_predicate (bb);
- if (cond
- && bb != loop->header)
- {
- gimple_seq stmts;
-
- cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
- add_bb_predicate_gimplified_stmts (bb, stmts);
- }
for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
{
case GIMPLE_COND:
{
- tree c2;
+ tree c2, tem;
edge true_edge, false_edge;
location_t loc = gimple_location (stmt);
tree c = fold_build2_loc (loc, gimple_cond_code (stmt),
&true_edge, &false_edge);
/* If C is true, then TRUE_EDGE is taken. */
- add_to_dst_predicate_list (loop, true_edge, cond, c);
+ add_to_dst_predicate_list (loop, true_edge,
+ unshare_expr (cond),
+ unshare_expr (c));
/* If C is false, then FALSE_EDGE is taken. */
c2 = invert_truthvalue_loc (loc, unshare_expr (c));
- add_to_dst_predicate_list (loop, false_edge, cond, c2);
+ tem = canonicalize_cond_expr_cond (c2);
+ if (tem)
+ c2 = tem;
+ add_to_dst_predicate_list (loop, false_edge,
+ unshare_expr (cond), c2);
cond = NULL_TREE;
break;
return true;
}
-/* Return true when LOOP is if-convertible.
- LOOP is if-convertible if:
- - it is innermost,
- - it has two or more basic blocks,
- - it has only one exit,
- - loop header is not the exit edge,
- - if its basic blocks and phi nodes are if convertible. */
+/* Return true when LOOP is if-convertible. This is a helper function
+ for if_convertible_loop_p. REFS and DDRS are initialized and freed
+ in if_convertible_loop_p. */
static bool
-if_convertible_loop_p (struct loop *loop)
+if_convertible_loop_p_1 (struct loop *loop,
+ VEC (loop_p, heap) **loop_nest,
+ VEC (data_reference_p, heap) **refs,
+ VEC (ddr_p, heap) **ddrs)
{
+ bool res;
unsigned int i;
- edge e;
- edge_iterator ei;
basic_block exit_bb = NULL;
- /* Handle only innermost loop. */
- if (!loop || loop->inner)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "not innermost loop\n");
- return false;
- }
-
- /* If only one block, no need for if-conversion. */
- if (loop->num_nodes <= 2)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "less than 2 basic blocks\n");
- return false;
- }
-
- /* More than one loop exit is too much to handle. */
- if (!single_exit (loop))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "multiple exits\n");
- return false;
- }
-
- /* ??? Check target's vector conditional operation support for vectorizer. */
-
- /* If one of the loop header's edge is exit edge then do not apply
- if-conversion. */
- FOR_EACH_EDGE (e, ei, loop->header->succs)
- {
- if (loop_exit_edge_p (loop, e))
- return false;
- }
-
/* 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);
-
- if (!res)
- return false;
- }
+ res = compute_data_dependences_for_loop (loop, true, loop_nest, refs, ddrs);
+ if (!res)
+ return false;
calculate_dominance_info (CDI_DOMINATORS);
+ calculate_dominance_info (CDI_POST_DOMINATORS);
/* Allow statements that can be handled during if-conversion. */
ifc_bbs = get_loop_body_in_if_conv_order (loop);
exit_bb = bb;
}
- if (!predicate_bbs (loop))
+ res = predicate_bbs (loop);
+ if (!res)
return false;
+ if (flag_tree_loop_if_convert_stores)
+ {
+ data_reference_p dr;
+
+ for (i = 0; VEC_iterate (data_reference_p, *refs, i, dr); i++)
+ {
+ dr->aux = XNEW (struct ifc_dr);
+ DR_WRITTEN_AT_LEAST_ONCE (dr) = -1;
+ DR_RW_UNCONDITIONALLY (dr) = -1;
+ }
+ }
+
for (i = 0; i < loop->num_nodes; i++)
{
basic_block bb = ifc_bbs[i];
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;
-
- 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))
+ return false;
}
if (dump_file)
return true;
}
+/* Return true when LOOP is if-convertible.
+ LOOP is if-convertible if:
+ - it is innermost,
+ - it has two or more basic blocks,
+ - it has only one exit,
+ - loop header is not the exit edge,
+ - if its basic blocks and phi nodes are if convertible. */
+
+static bool
+if_convertible_loop_p (struct loop *loop)
+{
+ edge e;
+ edge_iterator ei;
+ bool res = false;
+ VEC (data_reference_p, heap) *refs;
+ VEC (ddr_p, heap) *ddrs;
+ VEC (loop_p, heap) *loop_nest;
+
+ /* Handle only innermost loop. */
+ if (!loop || loop->inner)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "not innermost loop\n");
+ return false;
+ }
+
+ /* If only one block, no need for if-conversion. */
+ if (loop->num_nodes <= 2)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "less than 2 basic blocks\n");
+ return false;
+ }
+
+ /* More than one loop exit is too much to handle. */
+ if (!single_exit (loop))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "multiple exits\n");
+ return false;
+ }
+
+ /* If one of the loop header's edge is an exit edge then do not
+ apply if-conversion. */
+ FOR_EACH_EDGE (e, ei, loop->header->succs)
+ if (loop_exit_edge_p (loop, e))
+ return false;
+
+ refs = VEC_alloc (data_reference_p, heap, 5);
+ ddrs = VEC_alloc (ddr_p, heap, 25);
+ loop_nest = VEC_alloc (loop_p, heap, 3);
+ res = if_convertible_loop_p_1 (loop, &loop_nest, &refs, &ddrs);
+
+ if (flag_tree_loop_if_convert_stores)
+ {
+ data_reference_p dr;
+ unsigned int i;
+
+ for (i = 0; VEC_iterate (data_reference_p, refs, i, dr); i++)
+ free (dr->aux);
+ }
+
+ VEC_free (loop_p, heap, loop_nest);
+ free_data_refs (refs);
+ free_dependence_relations (ddrs);
+ return res;
+}
+
/* Basic block BB has two predecessors. Using predecessor's bb
predicate, set an appropriate condition COND for the PHI node
replacement. Return the true block whose phi arguments are
*cond = bb_predicate (second_edge->src);
if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
- *cond = invert_truthvalue (*cond);
+ *cond = TREE_OPERAND (*cond, 0);
else
/* Select non loop header bb. */
first_edge = second_edge;
else
*cond = bb_predicate (first_edge->src);
- /* Gimplify the condition: the vectorizer prefers to have gimple
- values as conditions. Various targets use different means to
- communicate conditions in vector compare operations. Using a
- gimple value allows the compiler to emit vector compare and
- select RTL without exposing compare's result. */
- *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
- false, NULL_TREE,
- true, GSI_SAME_STMT);
- if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
- *cond = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond), gsi);
-
- gcc_assert (*cond);
+ /* Gimplify the condition to a valid cond-expr conditonal operand. */
+ *cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (*cond),
+ is_gimple_condexpr, NULL_TREE,
+ true, GSI_SAME_STMT);
return first_edge->src;
}
{
gimple new_stmt;
basic_block bb;
- tree rhs, res, arg;
+ tree rhs, res, arg, scev;
gcc_assert (gimple_code (phi) == GIMPLE_PHI
&& gimple_phi_num_args (phi) == 2);
bb = gimple_bb (phi);
- arg = degenerate_phi_result (phi);
- if (arg)
+ if ((arg = degenerate_phi_result (phi))
+ || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
+ res))
+ && !chrec_contains_undetermined (scev)
+ && scev != res
+ && (arg = gimple_phi_arg_def (phi, 0))))
rhs = arg;
else
{
arg_1 = gimple_phi_arg_def (phi, 1);
}
+ gcc_checking_assert (bb == bb->loop_father->header
+ || bb_postdominates_preds (bb));
+
/* Build new RHS using selected condition and arguments. */
rhs = build3 (COND_EXPR, TREE_TYPE (res),
unshare_expr (cond), arg_0, arg_1);
for (i = 0; i < orig_loop_num_nodes; i++)
{
bb = ifc_bbs[i];
+ free_bb_predicate (bb);
if (bb_with_exit_edge_p (loop, bb))
{
exit_bb = bb;
&& exit_bb != loop->header
&& can_merge_blocks_p (loop->header, exit_bb))
merge_blocks (loop->header, exit_bb);
+
+ free (ifc_bbs);
+ ifc_bbs = NULL;
}
/* If-convert LOOP when it is legal. For the moment this pass has no
if (changed && flag_tree_loop_if_convert_stores)
todo |= TODO_update_ssa_only_virtuals;
+ free_dominance_info (CDI_POST_DOMINATORS);
+
return todo;
}
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_verify_stmts | TODO_verify_flow
+ TODO_verify_stmts | TODO_verify_flow
/* todo_flags_finish */
}
};
OSDN Git Service
