/* List of basic blocks in if-conversion-suitable order. */
static basic_block *ifc_bbs;
-/* Create a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP
- to the new variable. */
+/* 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). */
static gimple
ifc_temp_var (tree type, tree exp)
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 (prev_cond == boolean_true_node || !prev_cond)
- new_cond = unshare_expr (cond);
- else
+ /* 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))
{
tree tmp;
gimple tmp_stmt = NULL;
return false;
}
-/* 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. */
+ /* 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;
static void
tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
tree c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node,
gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
- extract_true_false_edges_from_block (gimple_bb (stmt),
- &true_edge, &false_edge);
+ /* Now, all statements are if-converted and basic blocks are
+ annotated appropriately. Combine all basic block into one huge
+ basic block. */
+ combine_blocks (loop);
/* Add new condition into destination's predicate list. */
}
/* 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. */
+ If T is a GIMPLE_ASSIGN then 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, gimple t, tree cond,
default:
gcc_unreachable ();
}
-
return cond;
}
-/* Return true when PHI is if-convertible. PHI is part of loop LOOP
- and it belongs to basic block BB.
+/* STMT is a GIMPLE_COND. Update two destination's predicate list.
+ Remove COND_EXPR, if it is not the loop exit condition. Otherwise
+ update loop exit condition appropriately. GSI is the iterator
+ used to traverse statement list. STMT is part of loop LOOP. */
+
+static void
+tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
+ gimple_stmt_iterator *gsi)
+{
+ tree c, c2;
+ edge true_edge, false_edge;
+ location_t loc = gimple_location (stmt);
+
+ gcc_assert (gimple_code (stmt) == GIMPLE_COND);
+
+ c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node,
+ gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
- PHI is not if-convertible if:
- - it has more than 2 arguments,
+ extract_true_false_edges_from_block (gimple_bb (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, 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 exit condition! Update exit condition
+ using new condition. */
+ if (!bb_with_exit_edge_p (loop, gimple_bb (stmt)))
+ {
+ gsi_remove (gsi, true);
+ cond = NULL_TREE;
+ }
+ return;
+}
+
+/* Return true, iff 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. */
- it is not movable,
- it could trap,
- LHS is not var decl.
-
GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */
static bool
return true;
}
-/* 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. */
+/* Return true, iff STMT is if-convertible.
+ Statement is if-convertible if,
+ - it is if-convertible GIMPLE_ASSGIN,
+ - it is GIMPLE_LABEL or GIMPLE_COND.
+ STMT is inside block BB, which is inside loop LOOP. */
static bool
if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
return true;
}
-/* 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. */
+/* 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. */
static bool
if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
return true;
}
-/* Return true when all predecessor blocks of BB are visited. The
- VISITED bitmap keeps track of the visited blocks. */
+/* 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). */
static bool
pred_blocks_visited_p (basic_block bb, bitmap *visited)
return true;
}
-/* 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. */
+/* Add condition COND into 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 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,
+ gimple_stmt_iterator *gsi)
+{
+ 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;
+ 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 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);
+ gsi_insert_before (gsi, tmp_stmt, GSI_SAME_STMT);
+ new_cond = gimple_assign_lhs (tmp_stmt);
+ }
+ 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. */
static void
clean_predicate_lists (struct loop *loop)
free (bb);
}
-/* 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. */
+/* 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. */
static basic_block
find_phi_replacement_condition (struct loop *loop,
delete_basic_block (bb);
}
- /* 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. */
+ /* 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);
}
-/* Main entry point: return true when LOOP is if-converted, otherwise
- the loop remains unchanged. */
+/* Make a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP
+ to the new variable. */
+
+static gimple
+ifc_temp_var (tree type, tree exp)
+{
+ const char *name = "_ifc_";
+ tree var, new_name;
+ gimple stmt;
+
+ /* 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;
+}
+
+
+/* Return TRUE iff, all pred blocks of BB are visited.
+ Bitmap VISITED keeps history of visited blocks. */
static bool
tree_if_conversion (struct loop *loop)
{
- gimple_stmt_iterator itr;
- unsigned int i;
+ 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);
ifc_bbs = NULL;
free (ifc_bbs);
ifc_bbs = NULL;
}
- 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 (!bitmap_bit_p (visited, bb->index))
{
gimple t = gsi_stmt (itr);
cond = tree_if_convert_stmt (loop, t, cond, &itr);
gsi_next (&itr);
}
- /* 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);
-
- /* 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;
+ index++;
- add_to_predicate_list (bb_n, cond);
- }
+ if (index == loop->num_nodes
+ && visited_count != loop->num_nodes)
+ /* Not done yet. */
+ index = 0;
}
/* Now, all statements are if-converted and basic blocks are
OSDN Git Service
