/* If-conversion for vectorizer.
- Copyright (C) 2004 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
Contributed by Devang Patel <dpatel@apple.com>
This file is part of GCC.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
-/* This pass implements tree level if-conversion transformation of loops.
+/* This pass implements tree level if-conversion transformation of loops.
Initial goal is to help vectorizer vectorize loops with conditions.
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 propogate condition into destination basic blcoks'
+ and propagate condition into destination basic blocks'
predicate list.
o Replace modify expression with conditional modify expression
using current basic block's condition.
# i_23 = PHI <0(0), i_18(10)>;
<L0>:;
j_15 = A[i_23];
-
+
<L3>:;
iftmp.2_4 = j_15 > 41 ? 42 : 0;
A[i_23] = iftmp.2_4;
i_18 = i_23 + 1;
if (i_18 <= 15) goto <L19>; else goto <L18>;
-
+
<L19>:;
goto <bb 1> (<L0>);
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "errors.h"
#include "tree.h"
#include "c-common.h"
#include "flags.h"
#include "target.h"
/* local function prototypes */
-static void main_tree_if_conversion (void);
-static tree tree_if_convert_stmt (struct loop *loop, tree, tree,
+static unsigned int main_tree_if_conversion (void);
+static tree tree_if_convert_stmt (struct loop *loop, tree, tree,
block_stmt_iterator *);
-static void tree_if_convert_cond_expr (struct loop *, tree, tree,
+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_gimple_modify_stmt_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, basic_block);
+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, tree, tree, tree,
+static tree add_to_dst_predicate_list (struct loop * loop, edge,
+ tree, tree,
block_stmt_iterator *);
static void clean_predicate_lists (struct loop *loop);
-static bool find_phi_replacement_condition (basic_block, tree *,
- block_stmt_iterator *);
-static void replace_phi_with_cond_modify_expr (tree, tree, bool,
+static basic_block find_phi_replacement_condition (struct loop *loop,
+ basic_block, tree *,
+ block_stmt_iterator *);
+static void replace_phi_with_cond_gimple_modify_stmt (tree, tree, basic_block,
block_stmt_iterator *);
static void process_phi_nodes (struct loop *);
static void combine_blocks (struct loop *);
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;
/* Main entry point.
Apply if-conversion to the LOOP. Return true if successful otherwise return
- false. If false is returned then loop remains unchanged.
+ false. If false is returned then loop remains unchanged.
FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used
for vectorizer or not. If it is used for vectorizer, additional checks are
- used. (Vectorization checks are not yet imlemented). */
+ used. (Vectorization checks are not yet implemented). */
-bool
+static bool
tree_if_conversion (struct loop *loop, bool for_vectorizer)
{
basic_block bb;
block_stmt_iterator itr;
- tree cond;
unsigned int i;
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");
ifc_bbs = NULL;
}
free_dominance_info (CDI_POST_DOMINATORS);
- free_df ();
return false;
}
- cond = NULL_TREE;
-
/* Do actual work now. */
- for (i = 0; i < loop->num_nodes; i++)
+ for (i = 0; i < loop->num_nodes; i++)
{
+ tree cond;
+
bb = ifc_bbs [i];
/* Update condition using predicate list. */
cond = bb->aux;
/* Process all statements in this basic block.
- Remove conditional expresion, if any, and annotate
+ Remove conditional expression, if any, and annotate
destination basic block(s) appropriately. */
for (itr = bsi_start (bb); !bsi_end_p (itr); /* empty */)
{
bsi_next (&itr);
}
- /* If current bb has only one successor, then consider it as an
+ /* If current bb has only one successor, then consider it as an
unconditional goto. */
- if (bb->succ && !bb->succ->succ_next)
+ if (single_succ_p (bb))
{
- basic_block bb_n = bb->succ->dest;
+ basic_block bb_n = single_succ (bb);
if (cond != NULL_TREE)
add_to_predicate_list (bb_n, cond);
- cond = NULL_TREE;
}
}
clean_predicate_lists (loop);
free (ifc_bbs);
ifc_bbs = NULL;
- free_df ();
return true;
}
-/* if-convert stmt T which is part of LOOP.
- If T is a MODIFY_EXPR than it is converted into conditional modify
- expression using COND. For conditional expressions, add condition in the
- destination basic block's predicate list and remove conditional
- expression itself. BSI is the iterator used to traverse statements of
+/* if-convert stmt T which is part of LOOP.
+ If T is a GIMPLE_MODIFY_STMT than it is converted into conditional modify
+ expression using COND. For conditional expressions, add condition in the
+ destination basic block's predicate list and remove conditional
+ expression itself. BSI is the iterator used to traverse statements of
loop. It is used here when it is required to delete current statement. */
static tree
-tree_if_convert_stmt (struct loop * loop, tree t, tree cond,
+tree_if_convert_stmt (struct loop * loop, tree t, tree cond,
block_stmt_iterator *bsi)
{
if (dump_file && (dump_flags & TDF_DETAILS))
case LABEL_EXPR:
break;
- case MODIFY_EXPR:
- /* This modify_expr is killing previous value of LHS. Appropriate value will
- be selected by PHI node based on condition. It is possible that before
- this transformation, PHI nodes was selecting default value and now it will
- use this new value. This is OK because it does not change validity the
- program. */
- break;
-
- case GOTO_EXPR:
- /* Unconditional goto */
- add_to_predicate_list (bb_for_stmt (TREE_OPERAND (t, 1)), cond);
- bsi_remove (bsi);
- cond = NULL_TREE;
+ case GIMPLE_MODIFY_STMT:
+ /* This GIMPLE_MODIFY_STMT is killing previous value of LHS. Appropriate
+ value will be selected by PHI node based on condition. It is possible
+ that before this transformation, PHI nodes was selecting default
+ value and now it will use this new value. This is OK because it does
+ not change validity the program. */
break;
case COND_EXPR:
/* Update destination blocks' predicate list and remove this
condition expression. */
tree_if_convert_cond_expr (loop, t, cond, bsi);
- cond = NULL_TREE;
- break;
-
- default:
- abort ();
+ cond = NULL_TREE;
break;
+
+ default:
+ gcc_unreachable ();
}
return cond;
}
/* STMT is COND_EXPR. Update two destination's predicate list.
Remove COND_EXPR, if it is not the loop exit condition. Otherwise
- update loop exit condition appropriatly. BSI is the iterator
+ update loop exit condition appropriately. BSI is the iterator
used to traverse statement list. STMT is part of loop LOOP. */
static void
-tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond,
+tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond,
block_stmt_iterator *bsi)
{
- tree then_clause, else_clause, c, new_cond;
- new_cond = NULL_TREE;
+ tree c, c2;
+ edge true_edge, false_edge;
-#ifdef ENABLE_CHECKING
- if (TREE_CODE (stmt) != COND_EXPR)
- abort ();
-#endif
+ gcc_assert (TREE_CODE (stmt) == COND_EXPR);
+
+ c = COND_EXPR_COND (stmt);
+
+ extract_true_false_edges_from_block (bb_for_stmt (stmt),
+ &true_edge, &false_edge);
- c = TREE_OPERAND (stmt, 0);
- then_clause = TREE_OPERAND (stmt, 1);
- else_clause = TREE_OPERAND (stmt, 2);
-
- /* Create temp. for condition. */
- if (!is_gimple_reg (c))
- {
- tree new_stmt;
- new_stmt = ifc_temp_var (TREE_TYPE (c), unshare_expr (c));
- bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
- c = TREE_OPERAND (new_stmt, 0);
- }
-
/* Add new condition into destination's predicate list. */
- if (then_clause)
- /* if 'c' is true then then_clause is reached. */
- new_cond = add_to_dst_predicate_list (loop, then_clause, cond, c, bsi);
-
- if (else_clause)
- {
- /* if 'c' is false then else_clause is reached. */
- tree c2 = build1 (TRUTH_NOT_EXPR,
- boolean_type_node,
- unshare_expr (c));
- add_to_dst_predicate_list (loop, else_clause, cond, c2, bsi);
- }
- /* Now this conditional statement is redundent. Remove it.
+ /* If 'c' is true then TRUE_EDGE is taken. */
+ add_to_dst_predicate_list (loop, true_edge, cond,
+ unshare_expr (c), bsi);
+
+ /* If 'c' is false then FALSE_EDGE is taken. */
+ c2 = invert_truthvalue (unshare_expr (c));
+ add_to_dst_predicate_list (loop, false_edge, cond, c2, bsi);
+
+ /* 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);
+ bsi_remove (bsi, true);
cond = NULL_TREE;
}
- else if (new_cond != NULL_TREE)
- {
- TREE_OPERAND (stmt, 0) = new_cond;
- modify_stmt (stmt);
- }
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))
{
fprintf (dump_file, "-------------------------\n");
print_generic_stmt (dump_file, phi, TDF_SLIM);
}
-
+
if (bb != loop->header && PHI_NUM_ARGS (phi) != 2)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "More than two phi node args.\n");
return false;
}
-
+
if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
{
- int j;
- dataflow_t df = get_immediate_uses (phi);
- int num_uses = num_immediate_uses (df);
- for (j = 0; j < num_uses; j++)
+ imm_use_iterator imm_iter;
+ use_operand_p use_p;
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, PHI_RESULT (phi))
{
- tree use = immediate_use (df, j);
- if (TREE_CODE (use) == PHI_NODE)
+ if (TREE_CODE (USE_STMT (use_p)) == PHI_NODE)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Difficult to handle this virtual phi.\n");
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.
+ GIMPLE_MODIFY_STMT is not if-convertible if,
- It is not movable.
- It could trap.
- LHS is not var decl.
- MODIFY_EXPR is part of block BB, which is inside loop LOOP.
+ GIMPLE_MODIFY_STMT is part of block BB, which is inside loop LOOP.
*/
static bool
-if_convertable_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr)
+if_convertible_gimple_modify_stmt_p (struct loop *loop, basic_block bb,
+ tree m_expr)
{
+ tree lhs, rhs;
+
+ if (TREE_CODE (m_expr) != GIMPLE_MODIFY_STMT)
+ return false;
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "-------------------------\n");
print_generic_stmt (dump_file, m_expr, TDF_SLIM);
}
-
- /* Be conservative and do not handle immovable expressions. */
- if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE)
+
+ lhs = GIMPLE_STMT_OPERAND (m_expr, 0);
+ rhs = GIMPLE_STMT_OPERAND (m_expr, 1);
+
+ /* Some of these constrains might be too conservative. */
+ if (stmt_ends_bb_p (m_expr) || stmt_ann (m_expr)->has_volatile_ops
+ || (TREE_CODE (lhs) == SSA_NAME
+ && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
+ || TREE_SIDE_EFFECTS (rhs))
{
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "stmt is movable. Don't take risk\n");
+ fprintf (dump_file, "stmt not suitable for ifcvt\n");
return false;
}
/* See if it needs speculative loading or not. */
- if (bb != loop->header
- && tree_could_trap_p (TREE_OPERAND (m_expr, 1)))
+ if (bb != loop->header
+ && tree_could_trap_p (GIMPLE_STMT_OPERAND (m_expr, 1)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "tree could trap...\n");
return false;
}
- if (TREE_CODE (TREE_OPERAND (m_expr, 1)) == CALL_EXPR)
+ if (TREE_CODE (GIMPLE_STMT_OPERAND (m_expr, 1)) == CALL_EXPR)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "CALL_EXPR \n");
return false;
}
- if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME
+ if (TREE_CODE (GIMPLE_STMT_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-converatable MODIFY_EXPR
- - IT is LABEL_EXPR, GOTO_EXPR or COND_EXPR.
+/* Return true, iff STMT is if-convertible.
+ Statement is if-convertible if,
+ - It is if-convertible GIMPLE_MODIFY_STMT
+ - IT is LABEL_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 LABEL_EXPR:
break;
-
- case MODIFY_EXPR:
-
- if (!if_convertable_modify_expr_p (loop, bb, stmt))
+
+ case GIMPLE_MODIFY_STMT:
+
+ if (!if_convertible_gimple_modify_stmt_p (loop, bb, stmt))
return false;
break;
-
- case GOTO_EXPR:
+
case COND_EXPR:
break;
-
+
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, 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-converatable if,
- - Basic block is non-empty and it is after exit block (in BFS order).
+ 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.
+ - Basic block edge(s) is not normal.
EXIT_BB_SEEN is true if basic block with exit edge is already seen.
- BB is inside loop LOOP. */
+ BB is inside loop LOOP. */
-static bool
-if_convertable_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen)
+static bool
+if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
{
edge e;
+ edge_iterator ei;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "----------[%d]-------------\n", bb->index);
-
- if (exit_bb_seen)
+
+ if (exit_bb)
{
if (bb != loop->latch)
{
fprintf (dump_file, "non empty basic block after exit bb\n");
return false;
}
+ else if (bb == loop->latch
+ && bb != exit_bb
+ && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "latch is not dominated by exit_block\n");
+ return false;
+ }
}
-
- /* Be less adveturous and handle only normal edges. */
- for (e = bb->succ; e; e = e->succ_next)
- if (e->flags &
+
+ /* Be less adventurous and handle only normal edges. */
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e->flags &
(EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
{
if (dump_file && (dump_flags & TDF_DETAILS))
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
- more info.
+ - Loop header is not the exit edge.
+ - 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;
block_stmt_iterator itr;
unsigned int i;
edge e;
- bool exit_bb_seen = false;
+ edge_iterator ei;
+ basic_block exit_bb = NULL;
/* Handle only inner most loop. */
if (!loop || loop->inner)
fprintf (dump_file, "not inner most loop\n");
return false;
}
-
- flow_loop_scan (loop, LOOP_ALL);
/* 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 thant 2 basic blocks\n");
+ fprintf (dump_file, "less than 2 basic blocks\n");
return false;
}
-
+
/* More than one loop exit is too much to handle. */
- if (loop->num_exits > 1)
+ if (!single_exit (loop))
{
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 (e = loop->header->succ; e; e = e->succ_next)
- if ( e->flags & EDGE_LOOP_EXIT)
- return false;
-
- compute_immediate_uses (TDFA_USE_OPS|TDFA_USE_VOPS, NULL);
+ FOR_EACH_EDGE (e, ei, loop->header->succs)
+ {
+ if (loop_exit_edge_p (loop, e))
+ return false;
+ }
calculate_dominance_info (CDI_DOMINATORS);
calculate_dominance_info (CDI_POST_DOMINATORS);
free_dominance_info (CDI_POST_DOMINATORS);
return false;
}
-
+
for (i = 0; i < loop->num_nodes; i++)
{
bb = ifc_bbs[i];
- if (!if_convertable_bb_p (loop, bb, exit_bb_seen))
+ if (!if_convertible_bb_p (loop, bb, exit_bb))
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 = TREE_CHAIN (phi))
- if (!if_convertable_phi_p (loop, bb, phi))
+ phi = phi_nodes (bb);
+
+ /* Clear aux field of incoming edges to a bb with a phi node. */
+ if (phi)
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ e->aux = NULL;
+
+ /* Check statements. */
+ for (; phi; phi = PHI_CHAIN (phi))
+ if (!if_convertible_phi_p (loop, bb, phi))
return false;
- if (bb_with_exit_edge_p (bb))
- exit_bb_seen = true;
+ if (bb_with_exit_edge_p (loop, bb))
+ exit_bb = bb;
}
/* OK. Did not find any potential issues so go ahead in if-convert
add_to_predicate_list (basic_block bb, tree new_cond)
{
tree cond = bb->aux;
-
+
if (cond)
- cond = fold (build (TRUTH_OR_EXPR, boolean_type_node,
- unshare_expr (cond), new_cond));
+ cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
+ unshare_expr (cond), new_cond);
else
cond = new_cond;
bb->aux = cond;
}
-/* Add condition COND into DST's predicate list. PREV_COND is
+/* Add condition COND into BB's predicate list. PREV_COND is
existing condition. */
static tree
-add_to_dst_predicate_list (struct loop * loop, tree dst,
+add_to_dst_predicate_list (struct loop * loop, edge e,
tree prev_cond, tree cond,
block_stmt_iterator *bsi)
{
- basic_block bb;
tree new_cond = NULL_TREE;
-#ifdef ENABLE_CHECKING
- if (TREE_CODE (dst) != GOTO_EXPR)
- abort ();
-#endif
- bb = label_to_block (TREE_OPERAND (dst, 0));
- if (!flow_bb_inside_loop_p (loop, bb))
+ if (!flow_bb_inside_loop_p (loop, e->dest))
return NULL_TREE;
if (prev_cond == boolean_true_node || !prev_cond)
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);
+
+ /* Add the condition to aux field of the edge. In case edge
+ destination is a PHI node, this condition will be ANDed with
+ block predicate to construct complete condition. */
+ e->aux = cond;
+
/* new_cond == prev_cond AND cond */
- tree tmp = build (TRUTH_AND_EXPR, boolean_type_node,
- unshare_expr (prev_cond), cond);
+ tmp = build2 (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);
+ new_cond = GIMPLE_STMT_OPERAND (tmp_stmt, 0);
}
- add_to_predicate_list (bb, new_cond);
+ add_to_predicate_list (e->dest, new_cond);
return new_cond;
}
-/* During if-conversion aux field from basic block is used to hold predicate
- list. Clean each basic block's predicate list for the given LOOP. */
+/* During if-conversion aux field from basic block structure is used to hold
+ predicate list. Clean each basic block's predicate list for the given LOOP.
+ Also clean aux field of successor edges, used to hold true and false
+ condition from conditional expression. */
static void
clean_predicate_lists (struct loop *loop)
{
+ basic_block *bb;
unsigned int i;
+ edge e;
+ edge_iterator ei;
+ bb = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
- ifc_bbs[i]->aux = NULL;
+ {
+ bb[i]->aux = NULL;
+ FOR_EACH_EDGE (e, ei, bb[i]->succs)
+ e->aux = NULL;
+ }
+ free (bb);
}
/* Basic block BB has two predecessors. Using predecessor's aux field, set
- appropriate condition COND for the PHI node replacement. Return true if
- phi arguments are condition is selected from second predecessor. */
+ appropriate condition COND for the PHI node replacement. Return true block
+ whose phi arguments are selected when cond is true. */
-static bool
-find_phi_replacement_condition (basic_block bb, tree *cond,
+static basic_block
+find_phi_replacement_condition (struct loop *loop,
+ basic_block bb, tree *cond,
block_stmt_iterator *bsi)
{
- edge e;
- basic_block p1 = NULL;
- basic_block p2 = NULL;
- bool switch_args = false;
- tree tmp_cond;
+ edge first_edge, second_edge;
+ tree tmp_cond, new_stmts;
+
+ gcc_assert (EDGE_COUNT (bb->preds) == 2);
+ first_edge = EDGE_PRED (bb, 0);
+ second_edge = EDGE_PRED (bb, 1);
+
+ /* Use condition based on following criteria:
+ 1)
+ S1: x = !c ? a : b;
+
+ S2: x = c ? b : a;
+
+ S2 is preferred over S1. Make 'b' first_bb and use its condition.
+
+ 2) Do not make loop header first_bb.
- for (e = bb->pred; e; e = e->pred_next)
+ 3)
+ S1: x = !(c == d)? a : b;
+
+ S21: t1 = c == d;
+ S22: x = t1 ? b : a;
+
+ S3: x = (c == d) ? b : a;
+
+ S3 is preferred over S1 and S2*, Make 'b' first_bb and use
+ its condition.
+
+ 4) If pred B is dominated by pred A then use pred B's condition.
+ See PR23115. */
+
+ /* Select condition that is not TRUTH_NOT_EXPR. */
+ tmp_cond = (first_edge->src)->aux;
+ if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
{
- if (p1 == NULL)
- p1 = e->src;
- else if (p2 == NULL)
- p2 = e->src;
- else
- /* More than two predecessors. This is not expected. */
- abort ();
+ edge tmp_edge;
+
+ tmp_edge = first_edge;
+ first_edge = second_edge;
+ second_edge = tmp_edge;
}
- /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
- tmp_cond = p1->aux;
- if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
+ /* Check if FIRST_BB is loop header or not and make sure that
+ FIRST_BB does not dominate SECOND_BB. */
+ if (first_edge->src == loop->header
+ || dominated_by_p (CDI_DOMINATORS,
+ second_edge->src, first_edge->src))
{
- *cond = p2->aux;
- switch_args = true;
+ *cond = (second_edge->src)->aux;
+
+ /* If there is a condition on an incoming edge,
+ AND it with the incoming bb predicate. */
+ if (second_edge->aux)
+ *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
+ *cond, second_edge->aux);
+
+ if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
+ /* We can be smart here and choose inverted
+ condition without switching bbs. */
+ *cond = invert_truthvalue (*cond);
+ else
+ /* Select non loop header bb. */
+ first_edge = second_edge;
}
else
{
- *cond = p1->aux;
- switch_args = false;
+ /* FIRST_BB is not loop header */
+ *cond = (first_edge->src)->aux;
+
+ /* If there is a condition on an incoming edge,
+ AND it with the incoming bb predicate. */
+ if (first_edge->aux)
+ *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
+ *cond, first_edge->aux);
}
-
- /* Create temp. for the condition. Vectorizier prefers to have gimple
- value as condition. Various targets use different means to communicate
- condition in vector compare operation. Using gimple value allows compiler
+
+ /* Create temp. for the condition. Vectorizer prefers to have gimple
+ value as condition. Various targets use different means to communicate
+ condition in vector compare operation. Using gimple value allows compiler
to emit vector compare and select RTL without exposing compare's result. */
+ *cond = force_gimple_operand (*cond, &new_stmts, false, NULL_TREE);
+ if (new_stmts)
+ bsi_insert_before (bsi, new_stmts, BSI_SAME_STMT);
if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
{
tree new_stmt;
new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
- bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT);
- bsi_next (bsi);
- *cond = TREE_OPERAND (new_stmt, 0);
+ bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
+ *cond = GIMPLE_STMT_OPERAND (new_stmt, 0);
}
-#ifdef ENABLE_CHECKING
- if (*cond == NULL_TREE)
- abort ();
-#endif
+ gcc_assert (*cond);
- return switch_args;
+ 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 PHI node with conditional modify expr using COND.
+ This routine does not handle PHI nodes with more than two arguments.
For example,
S1: A = PHI <x1(1), x2(5)
is converted into,
S2: A = cond ? x1 : x2;
S2 is inserted at the top of basic block's statement list.
- PHI arguments are switched if SWITCH_ARGS is true.
+ When COND is true, phi arg from TRUE_BB is selected.
*/
static void
-replace_phi_with_cond_modify_expr (tree phi, tree cond, bool switch_args,
- block_stmt_iterator *bsi)
+replace_phi_with_cond_gimple_modify_stmt (tree phi, tree cond,
+ basic_block true_bb,
+ block_stmt_iterator *bsi)
{
tree new_stmt;
basic_block bb;
tree rhs;
tree arg_0, arg_1;
-#ifdef ENABLE_CHECKING
- if (TREE_CODE (phi) != PHI_NODE)
- abort ();
-
+ gcc_assert (TREE_CODE (phi) == PHI_NODE);
+
/* If this is not filtered earlier, then now it is too late. */
- if (PHI_NUM_ARGS (phi) != 2)
- abort ();
-#endif
+ gcc_assert (PHI_NUM_ARGS (phi) == 2);
/* Find basic block and initialize iterator. */
bb = bb_for_stmt (phi);
- new_stmt = NULL_TREE;
- arg_0 = NULL_TREE;
- arg_1 = NULL_TREE;
-
/* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
- if (switch_args)
+ if (EDGE_PRED (bb, 1)->src == true_bb)
{
arg_0 = PHI_ARG_DEF (phi, 1);
arg_1 = PHI_ARG_DEF (phi, 0);
arg_1 = PHI_ARG_DEF (phi, 1);
}
- /* Build new RHS using selected condtion and arguments. */
- rhs = build (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
- unshare_expr (cond), unshare_expr (arg_0),
- unshare_expr (arg_1));
+ /* Build new RHS using selected condition and arguments. */
+ rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
+ unshare_expr (cond), unshare_expr (arg_0),
+ unshare_expr (arg_1));
- /* Create new MODIFY expresstion using RHS. */
- new_stmt = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
- unshare_expr (PHI_RESULT (phi)), rhs);
+ /* Create new MODIFY expression using RHS. */
+ new_stmt = build_gimple_modify_stmt (unshare_expr (PHI_RESULT (phi)), rhs);
/* Make new statement definition of the original phi result. */
SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
- /* Set basic block and insert using iterator. */
- set_bb_for_stmt (new_stmt, bb);
-
- bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT);
- bsi_next (bsi);
-
- modify_stmt (new_stmt);
+ /* Insert using iterator. */
+ bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
+ update_stmt (new_stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
}
}
-/* Process phi nodes for the given LOOP. Replace phi nodes with cond
+/* Process phi nodes for the given LOOP. Replace phi nodes with cond
modify expr. */
static void
{
tree phi, cond;
block_stmt_iterator bsi;
- bool switch_args = false;
+ basic_block true_bb = NULL;
bb = ifc_bbs[i];
-
- if (bb == loop->header || bb == loop->latch)
+
+ if (bb == loop->header)
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. */
if (phi)
- switch_args = find_phi_replacement_condition (bb, &cond, &bsi);
+ true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi);
while (phi)
{
- tree next = TREE_CHAIN (phi);
- replace_phi_with_cond_modify_expr (phi, cond, switch_args, &bsi);
+ tree next = PHI_CHAIN (phi);
+ replace_phi_with_cond_gimple_modify_stmt (phi, cond, true_bb, &bsi);
release_phi_node (phi);
phi = next;
}
- bb_ann (bb)->phi_nodes = NULL;
+ set_phi_nodes (bb, NULL_TREE);
}
return;
}
-/* Combine all basic block from the given LOOP into one or two super
- basic block. Replace PHI nodes with conditional modify expression. */
+/* Combine all basic block from the given LOOP into one or two super
+ basic block. Replace PHI nodes with conditional modify expression. */
static void
combine_blocks (struct loop *loop)
basic_block bb, exit_bb, merge_target_bb;
unsigned int orig_loop_num_nodes = loop->num_nodes;
unsigned int i;
+ edge e;
+ edge_iterator ei;
/* Process phi nodes to prepare blocks for merge. */
process_phi_nodes (loop);
+ /* Merge basic blocks. First remove all the edges in the loop, except
+ for those from the exit block. */
exit_bb = NULL;
+ for (i = 0; i < orig_loop_num_nodes; i++)
+ {
+ bb = ifc_bbs[i];
+ if (bb_with_exit_edge_p (loop, bb))
+ {
+ exit_bb = bb;
+ break;
+ }
+ }
+ gcc_assert (exit_bb != loop->latch);
- /* Merge basic blocks */
- merge_target_bb = loop->header;
for (i = 1; i < orig_loop_num_nodes; i++)
{
- edge e;
- block_stmt_iterator bsi;
- tree_stmt_iterator last;
-
bb = ifc_bbs[i];
- if (bb == loop->latch)
- continue;
-
- if (!exit_bb && bb_with_exit_edge_p (bb))
- exit_bb = bb;
-
- if (bb == exit_bb)
+ for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
{
- edge new_e;
+ if (e->src == exit_bb)
+ ei_next (&ei);
+ else
+ remove_edge (e);
+ }
+ }
+ if (exit_bb != NULL)
+ {
+ if (exit_bb != loop->header)
+ {
/* Connect this node with loop header. */
- new_e = make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU);
- set_immediate_dominator (CDI_DOMINATORS, bb, ifc_bbs[0]);
+ make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
+ set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
+ }
- if (exit_bb != loop->latch)
- {
- /* Redirect non-exit edge to loop->latch. */
- for (e = bb->succ; e; e = e->succ_next)
- if (!(e->flags & EDGE_LOOP_EXIT))
- {
- redirect_edge_and_branch (e, loop->latch);
- set_immediate_dominator (CDI_DOMINATORS, loop->latch, bb);
- }
- }
- continue;
+ /* Redirect non-exit edges to loop->latch. */
+ FOR_EACH_EDGE (e, ei, exit_bb->succs)
+ {
+ if (!loop_exit_edge_p (loop, e))
+ redirect_edge_and_branch (e, loop->latch);
}
+ set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
+ }
+ else
+ {
+ /* If the loop does not have exit then reconnect header and latch. */
+ make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
+ set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
+ }
- /* It is time to remove this basic block. First remove edges. */
- while (bb->succ != NULL)
- ssa_remove_edge (bb->succ);
- while (bb->pred != NULL)
- ssa_remove_edge (bb->pred);
+ merge_target_bb = loop->header;
+ for (i = 1; i < orig_loop_num_nodes; i++)
+ {
+ block_stmt_iterator bsi;
+ tree_stmt_iterator last;
+
+ bb = ifc_bbs[i];
+
+ if (bb == exit_bb || bb == loop->latch)
+ continue;
/* Remove labels and make stmts member of loop->header. */
for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
{
if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
- bsi_remove (&bsi);
+ bsi_remove (&bsi, true);
else
{
set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
}
/* Update stmt list. */
- last = tsi_last (merge_target_bb->stmt_list);
- tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT);
- bb->stmt_list = NULL;
-
- /* Update dominator info. */
- if (dom_computed[CDI_DOMINATORS])
- delete_from_dominance_info (CDI_DOMINATORS, bb);
- if (dom_computed[CDI_POST_DOMINATORS])
- delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
-
- /* Remove basic block. */
- remove_bb_from_loops (bb);
- expunge_block (bb);
+ last = tsi_last (bb_stmt_list (merge_target_bb));
+ tsi_link_after (&last, bb_stmt_list (bb), TSI_NEW_STMT);
+ set_bb_stmt_list (bb, NULL);
+
+ delete_basic_block (bb);
}
+
+ /* Now if possible, merge loop header and block with exit edge.
+ This reduces number of basic blocks to 2. Auto vectorizer addresses
+ loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */
+ if (exit_bb
+ && exit_bb != loop->header
+ && can_merge_blocks_p (loop->header, exit_bb))
+ merge_blocks (loop->header, exit_bb);
}
-/* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP
+/* Make new temp variable of type TYPE. Add GIMPLE_MODIFY_STMT to assign EXP
to the new variable. */
static tree
/* Create new temporary variable. */
var = create_tmp_var (type, name);
- add_referenced_tmp_var (var);
+ add_referenced_var (var);
+
+ /* Build new statement to assign EXP to new variable. */
+ stmt = build_gimple_modify_stmt (var, exp);
- /* Build new statement to assigne EXP to new variable. */
- 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;
+ GIMPLE_STMT_OPERAND (stmt, 0) = new_name;
SSA_NAME_DEF_STMT (new_name) = stmt;
return stmt;
pred_blocks_visited_p (basic_block bb, bitmap *visited)
{
edge e;
- for (e = bb->pred; e; e = e->pred_next)
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb->preds)
if (!bitmap_bit_p (*visited, e->src->index))
return false;
-
+
return true;
}
additional constraint. Select block in BFS block, if all
pred are already selected. */
-static basic_block *
+static basic_block *
get_loop_body_in_if_conv_order (const struct loop *loop)
{
basic_block *blocks, *blocks_in_bfs_order;
unsigned int index = 0;
unsigned int visited_count = 0;
- if (!loop->num_nodes)
- abort ();
-
- if (loop->latch == EXIT_BLOCK_PTR)
- abort ();
+ gcc_assert (loop->num_nodes);
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR);
- blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
- visited = BITMAP_XMALLOC ();
+ blocks = XCNEWVEC (basic_block, loop->num_nodes);
+ visited = BITMAP_ALLOC (NULL);
blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
while (index < loop->num_nodes)
{
bb = blocks_in_bfs_order [index];
-
+
if (bb->flags & BB_IRREDUCIBLE_LOOP)
{
free (blocks_in_bfs_order);
}
}
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 (e = bb->succ; e && !exit_edge_found ; e = e->succ_next)
- if (e->flags & EDGE_LOOP_EXIT)
- exit_edge_found = true;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (loop_exit_edge_p (loop, e))
+ {
+ exit_edge_found = true;
+ break;
+ }
return exit_edge_found;
}
/* Tree if-conversion pass management. */
-static void
+static unsigned int
main_tree_if_conversion (void)
{
- unsigned i, loop_num;
+ loop_iterator li;
struct loop *loop;
- if (!current_loops)
- return;
+ if (number_of_loops () <= 1)
+ return 0;
- loop_num = current_loops->num;
- for (i = 0; i < loop_num; i++)
+ FOR_EACH_LOOP (li, loop, 0)
{
- loop = current_loops->parray[i];
- if (!loop)
- continue;
-
tree_if_conversion (loop, true);
}
-
+ return 0;
}
static bool
gate_tree_if_conversion (void)
{
- return true;
+ return flag_tree_vectorize != 0;
}
struct tree_opt_pass pass_if_conversion =
{
- "ifcvt", /* name */
- gate_tree_if_conversion, /* gate */
- main_tree_if_conversion, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- 0, /* tv_id */
- PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- TODO_dump_func, /* todo_flags_start */
- TODO_dump_func
- | TODO_verify_ssa
- | TODO_verify_stmts
- | TODO_verify_flow /* todo_flags_finish */
+ "ifcvt", /* name */
+ gate_tree_if_conversion, /* gate */
+ main_tree_if_conversion, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow,
+ /* todo_flags_finish */
+ 0 /* letter */
};
-
OSDN Git Service
