/* 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>
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
- the same data reference with predicates that add up (OR-up) to the
- true predicate: this ensures that the data reference A is touched
+ 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
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++)
- if (DR_STMT (b) != stmt
- && same_data_refs (a, b))
- {
- tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
+ {
+ tree ref_base_a = DR_REF (a);
+ tree ref_base_b = DR_REF (b);
- if (is_true_predicate (cb)
- || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb),
- ca, cb)))
- {
- found = true;
- break;
- }
+ 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)
- return false;
+ {
+ DR_RW_UNCONDITIONALLY (a) = 0;
+ return false;
+ }
}
return true;
for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++)
if (DR_STMT (a) == stmt
- && !DR_IS_READ (a))
+ && 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_READ (b)
+ && DR_IS_WRITE (b)
&& same_data_refs_base_objects (a, b))
{
tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
- if (is_true_predicate (cb)
+ 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)
- return false;
+ {
+ DR_WRITTEN_AT_LEAST_ONCE (a) = 0;
+ return false;
+ }
}
return true;
case GIMPLE_ASSIGN:
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. */
if (dump_file && (dump_flags & TDF_DETAILS))
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;
}
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, cond, unshare_expr (c));
/* If C is false, then FALSE_EDGE is taken. */
c2 = invert_truthvalue_loc (loc, unshare_expr (c));
+ tem = canonicalize_cond_expr_cond (c2);
+ if (tem)
+ c2 = tem;
add_to_dst_predicate_list (loop, false_edge, cond, c2);
cond = NULL_TREE;
static bool
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)
{
/* Don't if-convert the loop when the data dependences cannot be
computed: the loop won't be vectorized in that case. */
- res = compute_data_dependences_for_loop (loop, true, refs, ddrs);
+ 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);
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];
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)
refs = VEC_alloc (data_reference_p, heap, 5);
ddrs = VEC_alloc (ddr_p, heap, 25);
- res = if_convertible_loop_p_1 (loop, &refs, &ddrs);
+ 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;
{
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;
}
OSDN Git Service
