/* If-conversion for vectorizer.
- Copyright (C) 2004 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005 Free Software Foundation, Inc.
Contributed by Devang Patel <dpatel@apple.com>
This file is part of GCC.
A short description of if-conversion:
- o Decide if a loop is if-convertable or not.
+ o Decide if a loop is if-convertible or not.
o Walk all loop basic blocks in breadth first order (BFS order).
o Remove conditional statements (at the end of basic block)
and propagate condition into destination basic blocks'
block_stmt_iterator *);
static void tree_if_convert_cond_expr (struct loop *, tree, tree,
block_stmt_iterator *);
-static bool if_convertable_phi_p (struct loop *, basic_block, tree);
-static bool if_convertable_modify_expr_p (struct loop *, basic_block, tree);
-static bool if_convertable_stmt_p (struct loop *, basic_block, tree);
-static bool if_convertable_bb_p (struct loop *, basic_block, bool);
-static bool if_convertable_loop_p (struct loop *, bool);
+static bool if_convertible_phi_p (struct loop *, basic_block, tree);
+static bool if_convertible_modify_expr_p (struct loop *, basic_block, tree);
+static bool if_convertible_stmt_p (struct loop *, basic_block, tree);
+static bool if_convertible_bb_p (struct loop *, basic_block, bool);
+static bool if_convertible_loop_p (struct loop *, bool);
static void add_to_predicate_list (basic_block, tree);
static tree add_to_dst_predicate_list (struct loop * loop, basic_block, tree, tree,
block_stmt_iterator *);
static tree ifc_temp_var (tree, tree);
static bool pred_blocks_visited_p (basic_block, bitmap *);
static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop);
-static bool bb_with_exit_edge_p (basic_block);
+static bool bb_with_exit_edge_p (struct loop *, basic_block);
/* List of basic blocks in if-conversion-suitable order. */
static basic_block *ifc_bbs;
ifc_bbs = NULL;
/* if-conversion is not appropriate for all loops. First, check if loop is
- if-convertable or not. */
- if (!if_convertable_loop_p (loop, for_vectorizer))
+ if-convertible or not. */
+ if (!if_convertible_loop_p (loop, for_vectorizer))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,"-------------------------\n");
/* If current bb has only one successor, then consider it as an
unconditional goto. */
- if (EDGE_COUNT (bb->succs) == 1)
+ if (single_succ_p (bb))
{
- basic_block bb_n = EDGE_SUCC (bb, 0)->dest;
+ basic_block bb_n = single_succ (bb);
if (cond != NULL_TREE)
add_to_predicate_list (bb_n, cond);
cond = NULL_TREE;
tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond,
block_stmt_iterator *bsi)
{
- tree c, c2, new_cond;
+ tree c, c2;
edge true_edge, false_edge;
- new_cond = NULL_TREE;
gcc_assert (TREE_CODE (stmt) == COND_EXPR);
- c = TREE_OPERAND (stmt, 0);
+ c = COND_EXPR_COND (stmt);
/* Create temp. for condition. */
if (!is_gimple_condexpr (c))
/* Add new condition into destination's predicate list. */
/* If 'c' is true then TRUE_EDGE is taken. */
- new_cond = add_to_dst_predicate_list (loop, true_edge->dest, cond,
- unshare_expr (c), bsi);
+ add_to_dst_predicate_list (loop, true_edge->dest, cond,
+ unshare_expr (c), bsi);
if (!is_gimple_reg(c) && is_gimple_condexpr (c))
{
/* Now this conditional statement is redundant. Remove it.
But, do not remove exit condition! Update exit condition
using new condition. */
- if (!bb_with_exit_edge_p (bb_for_stmt (stmt)))
+ if (!bb_with_exit_edge_p (loop, bb_for_stmt (stmt)))
{
bsi_remove (bsi);
cond = NULL_TREE;
return;
}
-/* Return true, iff PHI is if-convertable. PHI is part of loop LOOP
+/* Return true, iff PHI is if-convertible. PHI is part of loop LOOP
and it belongs to basic block BB.
- PHI is not if-convertable
+ PHI is not if-convertible
- if it has more than 2 arguments.
- Virtual PHI is immediately used in another PHI node. */
static bool
-if_convertable_phi_p (struct loop *loop, basic_block bb, tree phi)
+if_convertible_phi_p (struct loop *loop, basic_block bb, tree phi)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
return true;
}
-/* Return true, if M_EXPR is if-convertable.
- MODIFY_EXPR is not if-convertable if,
+/* Return true, if M_EXPR is if-convertible.
+ MODIFY_EXPR is not if-convertible if,
- It is not movable.
- It could trap.
- LHS is not var decl.
*/
static bool
-if_convertable_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr)
+if_convertible_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME
&& bb != loop->header
- && !bb_with_exit_edge_p (bb))
+ && !bb_with_exit_edge_p (loop, bb))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
return true;
}
-/* Return true, iff STMT is if-convertable.
- Statement is if-convertable if,
- - It is if-convertable MODIFY_EXPR
+/* Return true, iff STMT is if-convertible.
+ Statement is if-convertible if,
+ - It is if-convertible MODIFY_EXPR
- IT is LABEL_EXPR, GOTO_EXPR or COND_EXPR.
STMT is inside block BB, which is inside loop LOOP. */
static bool
-if_convertable_stmt_p (struct loop *loop, basic_block bb, tree stmt)
+if_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt)
{
switch (TREE_CODE (stmt))
{
case MODIFY_EXPR:
- if (!if_convertable_modify_expr_p (loop, bb, stmt))
+ if (!if_convertible_modify_expr_p (loop, bb, stmt))
return false;
break;
return true;
}
-/* Return true, iff BB is if-convertable.
+/* Return true, iff BB is if-convertible.
Note: This routine does _not_ check basic block statements and phis.
- Basic block is not if-convertable if,
+ Basic block is not if-convertible if,
- Basic block is non-empty and it is after exit block (in BFS order).
- Basic block is after exit block but before latch.
- Basic block edge(s) is not normal.
BB is inside loop LOOP. */
static bool
-if_convertable_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen)
+if_convertible_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen)
{
edge e;
edge_iterator ei;
return true;
}
-/* Return true, iff LOOP is if-convertable.
- LOOP is if-convertable if,
+/* Return true, iff 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 convertable. See above for
+ - If its basic blocks and phi nodes are if convertible. See above for
more info.
FOR_VECTORIZER enables vectorizer specific checks. For example, support
for vector conditions, data dependency checks etc.. (Not implemented yet). */
static bool
-if_convertable_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
+if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
{
tree phi;
basic_block bb;
return false;
}
- flow_loop_scan (loop, LOOP_ALL);
-
/* If only one block, no need for if-conversion. */
if (loop->num_nodes <= 2)
{
}
/* More than one loop exit is too much to handle. */
- if (loop->num_exits > 1)
+ if (!loop->single_exit)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "multiple exits\n");
/* 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 ( e->flags & EDGE_LOOP_EXIT)
- return false;
+ {
+ if (loop_exit_edge_p (loop, e))
+ return false;
+ }
compute_immediate_uses (TDFA_USE_OPS|TDFA_USE_VOPS, NULL);
{
bb = ifc_bbs[i];
- if (!if_convertable_bb_p (loop, bb, exit_bb_seen))
+ if (!if_convertible_bb_p (loop, bb, exit_bb_seen))
return false;
/* Check statements. */
for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr))
- if (!if_convertable_stmt_p (loop, bb, bsi_stmt (itr)))
+ if (!if_convertible_stmt_p (loop, bb, bsi_stmt (itr)))
return false;
/* ??? Check data dependency for vectorizer. */
/* What about phi nodes ? */
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- if (!if_convertable_phi_p (loop, bb, phi))
+ if (!if_convertible_phi_p (loop, bb, phi))
return false;
- if (bb_with_exit_edge_p (bb))
+ if (bb_with_exit_edge_p (loop, bb))
exit_bb_seen = true;
}
new_cond = unshare_expr (cond);
else
{
- tree tmp_stmt;
+ tree tmp;
+ tree tmp_stmt = NULL_TREE;
+ tree tmp_stmts1 = NULL_TREE;
+ tree tmp_stmts2 = NULL_TREE;
+ prev_cond = force_gimple_operand (unshare_expr (prev_cond),
+ &tmp_stmts1, true, NULL);
+ if (tmp_stmts1)
+ bsi_insert_before (bsi, tmp_stmts1, BSI_SAME_STMT);
+
+ cond = force_gimple_operand (unshare_expr (cond),
+ &tmp_stmts2, true, NULL);
+ if (tmp_stmts2)
+ bsi_insert_before (bsi, tmp_stmts2, BSI_SAME_STMT);
+
/* new_cond == prev_cond AND cond */
- tree tmp = build (TRUTH_AND_EXPR, boolean_type_node,
- unshare_expr (prev_cond), cond);
+ tmp = build (TRUTH_AND_EXPR, boolean_type_node,
+ unshare_expr (prev_cond), cond);
tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT);
new_cond = TREE_OPERAND (tmp_stmt, 0);
static void
clean_predicate_lists (struct loop *loop)
{
+ basic_block *bb;
unsigned int i;
-
+ bb = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
- ifc_bbs[i]->aux = NULL;
+ bb[i]->aux = NULL;
+
+ free (bb);
}
/* Basic block BB has two predecessors. Using predecessor's aux field, set
arg_1 = NULL_TREE;
/* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
- if (PHI_ARG_EDGE(phi, 1)->src == true_bb)
+ if (EDGE_PRED (bb, 1)->src == true_bb)
{
arg_0 = PHI_ARG_DEF (phi, 1);
arg_1 = PHI_ARG_DEF (phi, 0);
continue;
phi = phi_nodes (bb);
- bsi = bsi_start (bb);
+ bsi = bsi_after_labels (bb);
/* BB has two predecessors. Using predecessor's aux field, set
appropriate condition for the PHI node replacement. */
while (phi)
{
- tree next = TREE_CHAIN (phi);
+ tree next = PHI_CHAIN (phi);
replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi);
release_phi_node (phi);
phi = next;
basic_block bb, exit_bb, merge_target_bb;
unsigned int orig_loop_num_nodes = loop->num_nodes;
unsigned int i;
+ unsigned int n_exits;
+ get_loop_exit_edges (loop, &n_exits);
/* Process phi nodes to prepare blocks for merge. */
process_phi_nodes (loop);
bb = ifc_bbs[i];
- if (!exit_bb && bb_with_exit_edge_p (bb))
+ if (!exit_bb && bb_with_exit_edge_p (loop, bb))
exit_bb = bb;
if (bb == exit_bb)
{
- edge new_e;
edge_iterator ei;
/* Connect this node with loop header. */
- new_e = make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU);
+ make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU);
set_immediate_dominator (CDI_DOMINATORS, bb, ifc_bbs[0]);
if (exit_bb != loop->latch)
{
/* Redirect non-exit edge to loop->latch. */
FOR_EACH_EDGE (e, ei, bb->succs)
- if (!(e->flags & EDGE_LOOP_EXIT))
- {
- redirect_edge_and_branch (e, loop->latch);
- set_immediate_dominator (CDI_DOMINATORS, loop->latch, bb);
- }
+ {
+ if (!loop_exit_edge_p (loop, e))
+ {
+ redirect_edge_and_branch (e, loop->latch);
+ set_immediate_dominator (CDI_DOMINATORS, loop->latch, bb);
+ }
+ }
}
continue;
}
continue;
/* It is time to remove this basic block. First remove edges. */
- while (EDGE_COUNT (bb->succs) > 0)
- ssa_remove_edge (EDGE_SUCC (bb, 0));
while (EDGE_COUNT (bb->preds) > 0)
- ssa_remove_edge (EDGE_PRED (bb, 0));
+ remove_edge (EDGE_PRED (bb, 0));
+
+ /* This is loop latch and loop does not have exit then do not
+ delete this basic block. Just remove its PREDS and reconnect
+ loop->header and loop->latch blocks. */
+ if (bb == loop->latch && n_exits == 0)
+ {
+ make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
+ set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
+ continue;
+ }
+
+ while (EDGE_COUNT (bb->succs) > 0)
+ remove_edge (EDGE_SUCC (bb, 0));
/* Remove labels and make stmts member of loop->header. */
for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
stmt = build (MODIFY_EXPR, type, var, exp);
/* Get SSA name for the new variable and set make new statement
- its definition statment. */
+ its definition statement. */
new_name = make_ssa_name (var, stmt);
TREE_OPERAND (stmt, 0) = new_name;
SSA_NAME_DEF_STMT (new_name) = stmt;
gcc_assert (loop->latch != EXIT_BLOCK_PTR);
blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
- visited = BITMAP_XMALLOC ();
+ visited = BITMAP_ALLOC (NULL);
blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
}
}
free (blocks_in_bfs_order);
- BITMAP_XFREE (visited);
+ BITMAP_FREE (visited);
return blocks;
}
-/* Return true if one of the basic block BB edge is loop exit. */
+/* Return true if one of the basic block BB edge is exit of LOOP. */
static bool
-bb_with_exit_edge_p (basic_block bb)
+bb_with_exit_edge_p (struct loop *loop, basic_block bb)
{
edge e;
edge_iterator ei;
bool exit_edge_found = false;
FOR_EACH_EDGE (e, ei, bb->succs)
- if (e->flags & EDGE_LOOP_EXIT)
+ if (loop_exit_edge_p (loop, e))
{
exit_edge_found = true;
break;
OSDN Git Service
