/* If-conversion for vectorizer.
- Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
+ Free Software Foundation, Inc.
Contributed by Devang Patel <dpatel@apple.com>
This file is part of GCC.
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
-/* This pass implements tree level if-conversion transformation of loops.
- Initial goal is to help vectorizer vectorize loops with conditions.
+/* This pass implements a tree level if-conversion of loops. Its
+ initial goal is to help the vectorizer to vectorize loops with
+ conditions.
A short description of if-conversion:
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
-#include "c-common.h"
#include "flags.h"
#include "timevar.h"
-#include "varray.h"
#include "rtl.h"
#include "basic-block.h"
#include "diagnostic.h"
#include "tree-pass.h"
#include "target.h"
-/* local function prototypes */
-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,
- block_stmt_iterator *);
-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, edge,
- tree, tree,
- block_stmt_iterator *);
-static void clean_predicate_lists (struct loop *loop);
-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 (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.
- 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 implemented). */
+/* Create a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP
+ to the new variable. */
-static bool
-tree_if_conversion (struct loop *loop, bool for_vectorizer)
+static gimple
+ifc_temp_var (tree type, tree exp)
{
- basic_block bb;
- block_stmt_iterator itr;
- unsigned int i;
+ const char *name = "_ifc_";
+ tree var, new_name;
+ gimple stmt;
- ifc_bbs = NULL;
+ /* Create new temporary variable. */
+ var = create_tmp_var (type, name);
+ add_referenced_var (var);
+
+ /* Build new statement to assign EXP to new variable. */
+ stmt = gimple_build_assign (var, exp);
+
+ /* Get SSA name for the new variable and set make new statement
+ its definition statement. */
+ new_name = make_ssa_name (var, stmt);
+ gimple_assign_set_lhs (stmt, new_name);
+ SSA_NAME_DEF_STMT (new_name) = stmt;
+ update_stmt (stmt);
+
+ return stmt;
+}
+
+/* Add condition NEW_COND to the predicate list of basic block BB. */
+
+static void
+add_to_predicate_list (basic_block bb, tree new_cond)
+{
+ tree cond = (tree) bb->aux;
+
+ if (cond)
+ cond = fold_build2_loc (EXPR_LOCATION (cond),
+ TRUTH_OR_EXPR, boolean_type_node,
+ unshare_expr (cond), new_cond);
+ else
+ cond = new_cond;
+
+ bb->aux = cond;
+}
+
+/* Add the condition COND to the previous condition PREV_COND, and add this
+ to the predicate list of the destination of edge E. GSI is the
+ place where the gimplification of the resulting condition should
+ output code. LOOP is the loop to be if-converted. */
+
+static tree
+add_to_dst_predicate_list (struct loop *loop, edge e,
+ tree prev_cond, tree cond,
+ gimple_stmt_iterator *gsi)
+{
+ tree new_cond = NULL_TREE;
+
+ if (!flow_bb_inside_loop_p (loop, e->dest))
+ return NULL_TREE;
- /* if-conversion is not appropriate for all loops. First, check if loop is
- if-convertible or not. */
- if (!if_convertible_loop_p (loop, for_vectorizer))
+ if (prev_cond == boolean_true_node || !prev_cond)
+ new_cond = unshare_expr (cond);
+ else
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file,"-------------------------\n");
- if (ifc_bbs)
- {
- free (ifc_bbs);
- ifc_bbs = NULL;
- }
- free_dominance_info (CDI_POST_DOMINATORS);
- return false;
+ tree tmp;
+ gimple tmp_stmt = NULL;
+
+ prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond),
+ true, NULL, true, GSI_SAME_STMT);
+
+ cond = force_gimple_operand_gsi (gsi, unshare_expr (cond),
+ true, NULL, true, GSI_SAME_STMT);
+
+ /* Add the condition COND to the e->aux field. In case the edge
+ destination is a PHI node, this condition will be added to
+ the block predicate to construct a complete condition. */
+ e->aux = cond;
+
+ tmp = build2 (TRUTH_AND_EXPR, boolean_type_node,
+ unshare_expr (prev_cond), cond);
+ tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
+ gsi_insert_before (gsi, tmp_stmt, GSI_SAME_STMT);
+ new_cond = gimple_assign_lhs (tmp_stmt);
}
- /* Do actual work now. */
- for (i = 0; i < loop->num_nodes; i++)
- {
- tree cond;
+ add_to_predicate_list (e->dest, new_cond);
+ return new_cond;
+}
- bb = ifc_bbs [i];
+/* Return true if one of the successor edges of BB exits LOOP. */
- /* Update condition using predicate list. */
- cond = bb->aux;
+static bool
+bb_with_exit_edge_p (struct loop *loop, basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
- /* Process all statements in this basic block.
- Remove conditional expression, if any, and annotate
- destination basic block(s) appropriately. */
- for (itr = bsi_start (bb); !bsi_end_p (itr); /* empty */)
- {
- tree t = bsi_stmt (itr);
- cond = tree_if_convert_stmt (loop, t, cond, &itr);
- if (!bsi_end_p (itr))
- bsi_next (&itr);
- }
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (loop_exit_edge_p (loop, e))
+ return true;
- /* If current bb has only one successor, then consider it as an
- unconditional goto. */
- if (single_succ_p (bb))
- {
- basic_block bb_n = single_succ (bb);
+ return false;
+}
- /* Successor bb inherits predicate of its predecessor. If there
- is no predicate in predecessor bb, then consider successor bb
- as always executed. */
- if (cond == NULL_TREE)
- cond = boolean_true_node;
+/* STMT is a GIMPLE_COND. Update two destination's predicate list.
+ Remove COND_EXPR, if it is not the exit condition of LOOP.
+ Otherwise update the exit condition of LOOP appropriately. GSI
+ points to the statement STMT. */
- add_to_predicate_list (bb_n, cond);
- }
- }
+static void
+tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
+ gimple_stmt_iterator *gsi)
+{
+ tree c2;
+ edge true_edge, false_edge;
+ location_t loc = gimple_location (stmt);
+ tree c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node,
+ gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
- /* Now, all statements are if-converted and basic blocks are
- annotated appropriately. Combine all basic block into one huge
- basic block. */
- combine_blocks (loop);
+ extract_true_false_edges_from_block (gimple_bb (stmt),
+ &true_edge, &false_edge);
- /* clean up */
- clean_predicate_lists (loop);
- free (ifc_bbs);
- ifc_bbs = NULL;
+ /* Add new condition into destination's predicate list. */
- return true;
+ /* If C is true, then TRUE_EDGE is taken. */
+ add_to_dst_predicate_list (loop, true_edge, cond, c, gsi);
+
+ /* 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, gsi);
+
+ /* Now this conditional statement is redundant. Remove it. But, do
+ not remove the exit condition! Update the exit condition using
+ the new condition. */
+ if (!bb_with_exit_edge_p (loop, gimple_bb (stmt)))
+ {
+ gsi_remove (gsi, true);
+ cond = NULL_TREE;
+ }
}
-/* 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. */
+/* If-convert stmt T which is part of LOOP.
+
+ If T is a GIMPLE_ASSIGN then it is converted into a conditional
+ modify expression using COND. For conditional expressions, add
+ a condition in the destination basic block's predicate list and
+ remove the conditional expression itself. GSI points to the
+ statement T. */
static tree
-tree_if_convert_stmt (struct loop * loop, tree t, tree cond,
- block_stmt_iterator *bsi)
+tree_if_convert_stmt (struct loop *loop, gimple t, tree cond,
+ gimple_stmt_iterator *gsi)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "------if-convert stmt\n");
- print_generic_stmt (dump_file, t, TDF_SLIM);
+ print_gimple_stmt (dump_file, t, 0, TDF_SLIM);
print_generic_stmt (dump_file, cond, TDF_SLIM);
}
- switch (TREE_CODE (t))
+ switch (gimple_code (t))
{
/* Labels are harmless here. */
- case LABEL_EXPR:
+ case GIMPLE_LABEL:
+ break;
+
+ case GIMPLE_DEBUG:
+ /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
+ if (gimple_debug_bind_p (gsi_stmt (*gsi)))
+ {
+ gimple_debug_bind_reset_value (gsi_stmt (*gsi));
+ update_stmt (gsi_stmt (*gsi));
+ }
break;
- 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
+ case GIMPLE_ASSIGN:
+ /* This GIMPLE_ASSIGN 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. */
+ value and now it will use this new value. This is OK because it does
+ not change the validity of the program. */
break;
- case COND_EXPR:
+ case GIMPLE_COND:
/* Update destination blocks' predicate list and remove this
condition expression. */
- tree_if_convert_cond_expr (loop, t, cond, bsi);
+ tree_if_convert_cond_stmt (loop, t, cond, gsi);
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 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,
- block_stmt_iterator *bsi)
-{
- tree c, c2;
- edge true_edge, false_edge;
- 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);
-
- /* Add new condition into destination's predicate list. */
-
- /* 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 (loop, bb_for_stmt (stmt)))
- {
- bsi_remove (bsi, true);
- cond = NULL_TREE;
- }
- return;
+ return cond;
}
-/* Return true, iff PHI is if-convertible. PHI is part of loop LOOP
+/* Return true when PHI is if-convertible. PHI is part of loop LOOP
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. */
+
+ 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. */
static bool
-if_convertible_phi_p (struct loop *loop, basic_block bb, tree phi)
+if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "-------------------------\n");
- print_generic_stmt (dump_file, phi, TDF_SLIM);
+ print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
}
- if (bb != loop->header && PHI_NUM_ARGS (phi) != 2)
+ if (bb != loop->header && gimple_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))))
+ if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi))))
{
imm_use_iterator imm_iter;
use_operand_p use_p;
fprintf (dump_file, "Virtual phi not on loop header.\n");
return false;
}
- FOR_EACH_IMM_USE_FAST (use_p, imm_iter, PHI_RESULT (phi))
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
{
- if (TREE_CODE (USE_STMT (use_p)) == PHI_NODE)
+ 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 true;
}
-/* Return true, if M_EXPR is if-convertible.
- GIMPLE_MODIFY_STMT is not if-convertible if,
- - It is not movable.
- - It could trap.
+/* Return true when STMT is if-convertible.
+
+ GIMPLE_ASSIGN statement is not if-convertible if,
+ - it is not movable,
+ - it could trap,
- LHS is not var decl.
- GIMPLE_MODIFY_STMT is part of block BB, which is inside loop LOOP.
-*/
+
+ GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */
static bool
-if_convertible_gimple_modify_stmt_p (struct loop *loop, basic_block bb,
- tree m_expr)
+if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
+ gimple stmt)
{
- tree lhs, rhs;
-
- if (TREE_CODE (m_expr) != GIMPLE_MODIFY_STMT)
- return false;
+ tree lhs = gimple_assign_lhs (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "-------------------------\n");
- print_generic_stmt (dump_file, m_expr, TDF_SLIM);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
- 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
+ if (stmt_ends_bb_p (stmt)
+ || gimple_has_volatile_ops (stmt)
|| (TREE_CODE (lhs) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
- || TREE_SIDE_EFFECTS (rhs))
+ || gimple_has_side_effects (stmt))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "stmt not suitable for ifcvt\n");
/* See if it needs speculative loading or not. */
if (bb != loop->header
- && tree_could_trap_p (GIMPLE_STMT_OPERAND (m_expr, 1)))
+ && gimple_assign_rhs_could_trap_p (stmt))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "tree could trap...\n");
return false;
}
- 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 (GIMPLE_STMT_OPERAND (m_expr, 0)) != SSA_NAME
+ 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_generic_stmt (dump_file, m_expr, TDF_SLIM);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
return false;
}
-
return true;
}
-/* 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. */
+/* Return true when STMT is if-convertible.
+
+ 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. */
static bool
-if_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt)
+if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
{
- switch (TREE_CODE (stmt))
+ switch (gimple_code (stmt))
{
- case LABEL_EXPR:
- break;
-
- case GIMPLE_MODIFY_STMT:
-
- if (!if_convertible_gimple_modify_stmt_p (loop, bb, stmt))
- return false;
- break;
+ case GIMPLE_LABEL:
+ case GIMPLE_DEBUG:
+ case GIMPLE_COND:
+ return true;
- case COND_EXPR:
- break;
+ case GIMPLE_ASSIGN:
+ return if_convertible_gimple_assign_stmt_p (loop, bb, stmt);
default:
/* Don't know what to do with 'em so don't do anything. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "don't know what to do\n");
- print_generic_stmt (dump_file, stmt, TDF_SLIM);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
return false;
break;
return true;
}
-/* Return true, iff BB is if-convertible.
- Note: This routine does _not_ check basic block statements and phis.
- 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.
- EXIT_BB_SEEN is true if basic block with exit edge is already seen.
- BB is inside loop LOOP. */
+/* Return true when BB is if-convertible. This routine does not check
+ basic block's statements and phis.
+
+ A basic block is not if-convertible if:
+ - it is non-empty and it is after the exit block (in BFS order),
+ - it is after the exit block but before the latch,
+ - its edges are not normal.
+
+ EXIT_BB is the basic block containing the exit of the LOOP. BB is
+ inside LOOP. */
static bool
if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
fprintf (dump_file, "non empty basic block after exit bb\n");
return false;
}
- else if (bb == loop->latch
+ else if (bb == loop->latch
&& bb != exit_bb
&& !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
{
(EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
{
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file,"Difficult to handle edges\n");
+ fprintf (dump_file, "Difficult to handle edges\n");
return false;
}
return true;
}
-/* 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 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). */
+/* Return true when all predecessor blocks of BB are visited. The
+ VISITED bitmap keeps track of the visited blocks. */
+
+static bool
+pred_blocks_visited_p (basic_block bb, bitmap *visited)
+{
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (!bitmap_bit_p (*visited, e->src->index))
+ return false;
+
+ return true;
+}
+
+/* Get body of a LOOP in suitable order for if-conversion. It is
+ caller's responsibility to deallocate basic block list.
+ If-conversion suitable order is, breadth first sort (BFS) order
+ with an additional constraint: select a block only if all its
+ predecessors are already selected. */
+
+static basic_block *
+get_loop_body_in_if_conv_order (const struct loop *loop)
+{
+ basic_block *blocks, *blocks_in_bfs_order;
+ basic_block bb;
+ bitmap visited;
+ unsigned int index = 0;
+ unsigned int visited_count = 0;
+
+ gcc_assert (loop->num_nodes);
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+
+ blocks = XCNEWVEC (basic_block, loop->num_nodes);
+ visited = BITMAP_ALLOC (NULL);
+
+ blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
+
+ index = 0;
+ while (index < loop->num_nodes)
+ {
+ bb = blocks_in_bfs_order [index];
+
+ if (bb->flags & BB_IRREDUCIBLE_LOOP)
+ {
+ free (blocks_in_bfs_order);
+ BITMAP_FREE (visited);
+ free (blocks);
+ return NULL;
+ }
+
+ if (!bitmap_bit_p (visited, bb->index))
+ {
+ if (pred_blocks_visited_p (bb, &visited)
+ || bb == loop->header)
+ {
+ /* This block is now visited. */
+ bitmap_set_bit (visited, bb->index);
+ blocks[visited_count++] = bb;
+ }
+ }
+
+ index++;
+
+ if (index == loop->num_nodes
+ && visited_count != loop->num_nodes)
+ /* Not done yet. */
+ index = 0;
+ }
+ free (blocks_in_bfs_order);
+ BITMAP_FREE (visited);
+ return blocks;
+}
+
+/* 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, bool for_vectorizer ATTRIBUTE_UNUSED)
+if_convertible_loop_p (struct loop *loop)
{
- tree phi;
basic_block bb;
- block_stmt_iterator itr;
+ gimple_stmt_iterator itr;
unsigned int i;
edge e;
edge_iterator ei;
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_convertible_stmt_p (loop, bb, bsi_stmt (itr)))
+ for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
+ if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
return false;
- /* ??? Check data dependency for vectorizer. */
- /* What about phi nodes ? */
- phi = phi_nodes (bb);
+ itr = gsi_start_phis (bb);
- /* Clear aux field of incoming edges to a bb with a phi node. */
- if (phi)
+ if (!gsi_end_p (itr))
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))
+ for (; !gsi_end_p (itr); gsi_next (&itr))
+ if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
return false;
if (bb_with_exit_edge_p (loop, bb))
exit_bb = bb;
}
- /* OK. Did not find any potential issues so go ahead in if-convert
- this loop. Now there is no looking back. */
if (dump_file)
fprintf (dump_file,"Applying if-conversion\n");
return true;
}
-/* Add condition COND into predicate list of basic block BB. */
-
-static void
-add_to_predicate_list (basic_block bb, tree new_cond)
-{
- tree cond = bb->aux;
-
- if (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 BB's predicate list. PREV_COND is
- existing condition. */
-
-static tree
-add_to_dst_predicate_list (struct loop * loop, edge e,
- tree prev_cond, tree cond,
- block_stmt_iterator *bsi)
-{
- tree new_cond = NULL_TREE;
-
- 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;
- tree tmp_stmt = NULL_TREE;
-
- prev_cond = force_gimple_operand_bsi (bsi, unshare_expr (prev_cond),
- true, NULL, true, BSI_SAME_STMT);
-
- cond = force_gimple_operand_bsi (bsi, unshare_expr (cond),
- true, NULL, true, 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 */
- 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 = GIMPLE_STMT_OPERAND (tmp_stmt, 0);
- }
- add_to_predicate_list (e->dest, new_cond);
- return new_cond;
-}
-
-/* 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. */
+/* During if-conversion, the bb->aux field is used to hold a predicate
+ list. This function cleans for all the basic blocks in the given
+ LOOP their predicate list. It also cleans up the e->aux field of
+ all the successor edges: e->aux is used to hold the true and false
+ conditions for conditional expressions. */
static void
clean_predicate_lists (struct loop *loop)
free (bb);
}
-/* Basic block BB has two predecessors. Using predecessor's aux field, set
- appropriate condition COND for the PHI node replacement. Return true block
- whose phi arguments are selected when cond is true. */
+/* Basic block BB has two predecessors. Using predecessor's bb->aux
+ field, set appropriate condition COND for the PHI node replacement.
+ Return true block whose phi arguments are selected when cond is
+ true. LOOP is the loop containing the if-converted region, GSI is
+ the place to insert the code for the if-conversion. */
static basic_block
-find_phi_replacement_condition (struct loop *loop,
+find_phi_replacement_condition (struct loop *loop,
basic_block bb, tree *cond,
- block_stmt_iterator *bsi)
+ gimple_stmt_iterator *gsi)
{
edge first_edge, second_edge;
tree tmp_cond;
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.
3)
S3: x = (c == d) ? b : a;
- S3 is preferred over S1 and S2*, Make 'b' first_bb and use
+ 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;
+ tmp_cond = (tree) (first_edge->src)->aux;
gcc_assert (tmp_cond);
if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
|| dominated_by_p (CDI_DOMINATORS,
second_edge->src, first_edge->src))
{
- *cond = (second_edge->src)->aux;
+ *cond = (tree) (second_edge->src)->aux;
- /* If there is a condition on an incoming edge,
- AND it with the incoming bb predicate. */
+ /* If there is a condition on an incoming edge, add it to the
+ incoming bb predicate. */
if (second_edge->aux)
*cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
- *cond, second_edge->aux);
+ *cond, (tree) 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. */
}
else
{
- /* FIRST_BB is not loop header */
- *cond = (first_edge->src)->aux;
+ *cond = (tree) (first_edge->src)->aux;
- /* If there is a condition on an incoming edge,
- AND it with the incoming bb predicate. */
+ /* If there is a condition on an incoming edge, add it to the
+ incoming bb predicate. */
if (first_edge->aux)
*cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
- *cond, first_edge->aux);
+ *cond, (tree) first_edge->aux);
}
- /* 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_bsi (bsi, unshare_expr (*cond),
+ /* 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, BSI_SAME_STMT);
+ true, GSI_SAME_STMT);
if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
{
- tree new_stmt;
+ gimple new_stmt;
new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
- bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
- *cond = GIMPLE_STMT_OPERAND (new_stmt, 0);
+ gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
+ *cond = gimple_assign_lhs (new_stmt);
}
gcc_assert (*cond);
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.
- When COND is true, phi arg from TRUE_BB is selected.
-*/
+
+ The generated code is inserted at GSI that points to the top of
+ basic block's statement list. When COND is true, phi arg from
+ TRUE_BB is selected. */
static void
-replace_phi_with_cond_gimple_modify_stmt (tree phi, tree cond,
+replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
basic_block true_bb,
- block_stmt_iterator *bsi)
+ gimple_stmt_iterator *gsi)
{
- tree new_stmt;
+ gimple new_stmt;
basic_block bb;
tree rhs;
tree arg_0, arg_1;
- gcc_assert (TREE_CODE (phi) == PHI_NODE);
-
- /* If this is not filtered earlier, then now it is too late. */
- gcc_assert (PHI_NUM_ARGS (phi) == 2);
+ gcc_assert (gimple_code (phi) == GIMPLE_PHI
+ && gimple_phi_num_args (phi) == 2);
- /* Find basic block and initialize iterator. */
- bb = bb_for_stmt (phi);
+ bb = gimple_bb (phi);
/* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
if (EDGE_PRED (bb, 1)->src == true_bb)
{
- arg_0 = PHI_ARG_DEF (phi, 1);
- arg_1 = PHI_ARG_DEF (phi, 0);
+ arg_0 = gimple_phi_arg_def (phi, 1);
+ arg_1 = gimple_phi_arg_def (phi, 0);
}
else
{
- arg_0 = PHI_ARG_DEF (phi, 0);
- arg_1 = PHI_ARG_DEF (phi, 1);
+ arg_0 = gimple_phi_arg_def (phi, 0);
+ arg_1 = gimple_phi_arg_def (phi, 1);
}
/* Build new RHS using selected condition and arguments. */
unshare_expr (cond), unshare_expr (arg_0),
unshare_expr (arg_1));
- /* 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;
-
- /* Insert using iterator. */
- bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
+ new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs);
+ SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
+ gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
update_stmt (new_stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "new phi replacement stmt\n");
- print_generic_stmt (dump_file, new_stmt, TDF_SLIM);
+ print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
}
}
-/* Process phi nodes for the given LOOP. Replace phi nodes with cond
- modify expr. */
+/* Process phi nodes for the given LOOP. Replace phi nodes with
+ conditional modify expressions. */
static void
process_phi_nodes (struct loop *loop)
unsigned int orig_loop_num_nodes = loop->num_nodes;
unsigned int i;
- /* Replace phi nodes with cond. modify expr. */
for (i = 1; i < orig_loop_num_nodes; i++)
{
- tree phi, cond = NULL_TREE;
- block_stmt_iterator bsi;
+ gimple phi;
+ tree cond = NULL_TREE;
+ gimple_stmt_iterator gsi, phi_gsi;
basic_block true_bb = NULL;
bb = ifc_bbs[i];
if (bb == loop->header)
continue;
- phi = phi_nodes (bb);
- bsi = bsi_after_labels (bb);
+ phi_gsi = gsi_start_phis (bb);
+ gsi = gsi_after_labels (bb);
- /* BB has two predecessors. Using predecessor's aux field, set
+ /* BB has two predecessors. Using predecessor's aux field, set
appropriate condition for the PHI node replacement. */
- if (phi)
- true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi);
+ if (!gsi_end_p (phi_gsi))
+ true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
- while (phi)
+ while (!gsi_end_p (phi_gsi))
{
- tree next = PHI_CHAIN (phi);
- replace_phi_with_cond_gimple_modify_stmt (phi, cond, true_bb, &bsi);
+ phi = gsi_stmt (phi_gsi);
+ replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
release_phi_node (phi);
- phi = next;
+ gsi_next (&phi_gsi);
}
- set_phi_nodes (bb, NULL_TREE);
+ set_phi_nodes (bb, NULL);
}
- 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 the basic blocks from LOOP into one or two super basic
+ blocks. Replace PHI nodes with conditional modify expressions. */
static void
combine_blocks (struct loop *loop)
/* 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. */
+ /* 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++)
{
{
if (exit_bb != loop->header)
{
- /* Connect this node with loop header. */
+ /* Connect this node to loop header. */
make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
}
}
else
{
- /* If the loop does not have exit then reconnect header and latch. */
+ /* If the loop does not have an exit, reconnect header and latch. */
make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
}
merge_target_bb = loop->header;
for (i = 1; i < orig_loop_num_nodes; i++)
{
- block_stmt_iterator bsi;
- tree_stmt_iterator last;
+ gimple_stmt_iterator gsi;
+ gimple_stmt_iterator last;
bb = ifc_bbs[i];
continue;
/* Remove labels and make stmts member of loop->header. */
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
{
- if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
- bsi_remove (&bsi, true);
+ if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
+ gsi_remove (&gsi, true);
else
{
- set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
- bsi_next (&bsi);
+ gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
+ gsi_next (&gsi);
}
}
/* Update stmt list. */
- 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, alloc_stmt_list());
+ last = gsi_last_bb (merge_target_bb);
+ gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
+ set_bb_seq (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 possible, merge loop header to the block with the exit edge.
+ This reduces the number of basic blocks to two, to please the
+ vectorizer that handles only loops with two nodes.
+
+ FIXME: Call 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 GIMPLE_MODIFY_STMT to assign EXP
- to the new variable. */
-
-static tree
-ifc_temp_var (tree type, tree exp)
-{
- const char *name = "_ifc_";
- tree var, stmt, new_name;
-
- if (is_gimple_reg (exp))
- return exp;
-
- /* Create new temporary variable. */
- var = create_tmp_var (type, name);
- add_referenced_var (var);
-
- /* Build new statement to assign EXP to new variable. */
- stmt = build_gimple_modify_stmt (var, exp);
-
- /* Get SSA name for the new variable and set make new statement
- its definition statement. */
- new_name = make_ssa_name (var, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = new_name;
- SSA_NAME_DEF_STMT (new_name) = stmt;
-
- return stmt;
-}
-
-
-/* Return TRUE iff, all pred blocks of BB are visited.
- Bitmap VISITED keeps history of visited blocks. */
+/* Main entry point: return true when LOOP is if-converted, otherwise
+ the loop remains unchanged. */
static bool
-pred_blocks_visited_p (basic_block bb, bitmap *visited)
+tree_if_conversion (struct loop *loop)
{
- edge e;
- edge_iterator ei;
- FOR_EACH_EDGE (e, ei, bb->preds)
- if (!bitmap_bit_p (*visited, e->src->index))
- return false;
-
- return true;
-}
-
-/* Get body of a LOOP in suitable order for if-conversion.
- It is caller's responsibility to deallocate basic block
- list. If-conversion suitable order is, BFS order with one
- additional constraint. Select block in BFS block, if all
- pred are already selected. */
-
-static basic_block *
-get_loop_body_in_if_conv_order (const struct loop *loop)
-{
- basic_block *blocks, *blocks_in_bfs_order;
- basic_block bb;
- bitmap visited;
- unsigned int index = 0;
- unsigned int visited_count = 0;
-
- gcc_assert (loop->num_nodes);
- gcc_assert (loop->latch != EXIT_BLOCK_PTR);
-
- blocks = XCNEWVEC (basic_block, loop->num_nodes);
- visited = BITMAP_ALLOC (NULL);
+ gimple_stmt_iterator itr;
+ unsigned int i;
- blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
+ ifc_bbs = NULL;
- index = 0;
- while (index < loop->num_nodes)
+ /* If-conversion is not appropriate for all loops. First, check if
+ the loop is if-convertible. */
+ if (!if_convertible_loop_p (loop))
{
- bb = blocks_in_bfs_order [index];
-
- if (bb->flags & BB_IRREDUCIBLE_LOOP)
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,"-------------------------\n");
+ if (ifc_bbs)
{
- free (blocks_in_bfs_order);
- BITMAP_FREE (visited);
- free (blocks);
- return NULL;
+ free (ifc_bbs);
+ ifc_bbs = NULL;
}
- if (!bitmap_bit_p (visited, bb->index))
+ free_dominance_info (CDI_POST_DOMINATORS);
+ return false;
+ }
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block bb = ifc_bbs [i];
+ tree cond = (tree) bb->aux;
+
+ /* Process all the statements in this basic block.
+ Remove conditional expression, if any, and annotate
+ destination basic block(s) appropriately. */
+ for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */)
{
- if (pred_blocks_visited_p (bb, &visited)
- || bb == loop->header)
- {
- /* This block is now visited. */
- bitmap_set_bit (visited, bb->index);
- blocks[visited_count++] = bb;
- }
+ gimple t = gsi_stmt (itr);
+ cond = tree_if_convert_stmt (loop, t, cond, &itr);
+ if (!gsi_end_p (itr))
+ gsi_next (&itr);
}
- index++;
- if (index == loop->num_nodes
- && visited_count != loop->num_nodes)
+
+ /* If current bb has only one successor, then consider it as an
+ unconditional goto. */
+ if (single_succ_p (bb))
{
- /* Not done yet. */
- index = 0;
+ basic_block bb_n = single_succ (bb);
+
+ /* The successor bb inherits the predicate of its
+ predecessor. If there is no predicate in the predecessor
+ bb, then consider the successor bb as always executed. */
+ if (cond == NULL_TREE)
+ cond = boolean_true_node;
+
+ add_to_predicate_list (bb_n, cond);
}
}
- free (blocks_in_bfs_order);
- BITMAP_FREE (visited);
- return blocks;
-}
-
-/* Return true if one of the basic block BB edge is exit of LOOP. */
-static bool
-bb_with_exit_edge_p (struct loop *loop, basic_block bb)
-{
- edge e;
- edge_iterator ei;
- bool exit_edge_found = false;
+ /* Now, all statements are if-converted and basic blocks are
+ annotated appropriately. Combine all the basic blocks into one
+ huge basic block. */
+ combine_blocks (loop);
- FOR_EACH_EDGE (e, ei, bb->succs)
- if (loop_exit_edge_p (loop, e))
- {
- exit_edge_found = true;
- break;
- }
+ /* clean up */
+ clean_predicate_lists (loop);
+ free (ifc_bbs);
+ ifc_bbs = NULL;
- return exit_edge_found;
+ return true;
}
/* Tree if-conversion pass management. */
return 0;
FOR_EACH_LOOP (li, loop, 0)
- {
- tree_if_conversion (loop, true);
- }
+ tree_if_conversion (loop);
+
return 0;
}
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
- 0, /* tv_id */
- PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
+ TV_NONE, /* tv_id */
+ PROP_cfg | PROP_ssa, /* 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_dump_func | TODO_verify_stmts | TODO_verify_flow
/* todo_flags_finish */
}
};