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.
Initial goal is to help vectorizer vectorize loops with conditions.
#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 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 bool if_convertible_phi_p (struct loop *, basic_block, tree);
static bool if_convertible_modify_expr_p (struct loop *, basic_block, tree);
static bool if_convertible_stmt_p (struct loop *, basic_block, tree);
-static bool if_convertible_bb_p (struct loop *, basic_block, bool);
+static bool if_convertible_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, basic_block, tree, tree,
block_stmt_iterator *);
static void clean_predicate_lists (struct loop *loop);
-static basic_block find_phi_replacement_condition (basic_block, tree *,
+static basic_block find_phi_replacement_condition (struct loop *loop,
+ basic_block, tree *,
block_stmt_iterator *);
static void replace_phi_with_cond_modify_expr (tree, tree, basic_block,
block_stmt_iterator *);
ifc_bbs = NULL;
}
free_dominance_info (CDI_POST_DOMINATORS);
- free_df ();
return false;
}
/* If current bb has only one successor, then consider it as an
unconditional goto. */
- if (EDGE_COUNT (bb->succs) == 1)
+ if (single_succ_p (bb))
{
- basic_block bb_n = EDGE_SUCC (bb, 0)->dest;
+ basic_block bb_n = single_succ (bb);
if (cond != NULL_TREE)
add_to_predicate_list (bb_n, cond);
cond = NULL_TREE;
clean_predicate_lists (loop);
free (ifc_bbs);
ifc_bbs = NULL;
- free_df ();
return true;
}
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;
- break;
-
case COND_EXPR:
/* Update destination blocks' predicate list and remove this
condition expression. */
tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond,
block_stmt_iterator *bsi)
{
- tree c, c2, new_cond;
+ tree c, c2;
edge true_edge, false_edge;
- new_cond = NULL_TREE;
gcc_assert (TREE_CODE (stmt) == COND_EXPR);
c = COND_EXPR_COND (stmt);
- /* Create temp. for condition. */
- if (!is_gimple_condexpr (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);
- }
-
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. */
- new_cond = add_to_dst_predicate_list (loop, true_edge->dest, cond,
- unshare_expr (c), bsi);
-
- if (!is_gimple_reg(c) && is_gimple_condexpr (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_to_dst_predicate_list (loop, true_edge->dest, cond,
+ unshare_expr (c), bsi);
/* If 'c' is false then FALSE_EDGE is taken. */
c2 = invert_truthvalue (unshare_expr (c));
using new condition. */
if (!bb_with_exit_edge_p (loop, bb_for_stmt (stmt)))
{
- bsi_remove (bsi);
+ bsi_remove (bsi, true);
cond = NULL_TREE;
}
return;
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, iff STMT is if-convertible.
Statement is if-convertible if,
- It is if-convertible MODIFY_EXPR
- - IT is LABEL_EXPR, GOTO_EXPR or COND_EXPR.
+ - IT is LABEL_EXPR or COND_EXPR.
STMT is inside block BB, which is inside loop LOOP. */
static bool
return false;
break;
- case GOTO_EXPR:
case COND_EXPR:
break;
BB is inside loop LOOP. */
static bool
-if_convertible_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen)
+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 adventurous and handle only normal edges. */
unsigned int i;
edge e;
edge_iterator ei;
- bool exit_bb_seen = false;
+ basic_block exit_bb = NULL;
/* Handle only inner most loop. */
if (!loop || loop->inner)
return false;
}
- compute_immediate_uses (TDFA_USE_OPS|TDFA_USE_VOPS, NULL);
-
calculate_dominance_info (CDI_DOMINATORS);
calculate_dominance_info (CDI_POST_DOMINATORS);
{
bb = ifc_bbs[i];
- if (!if_convertible_bb_p (loop, bb, exit_bb_seen))
+ if (!if_convertible_bb_p (loop, bb, exit_bb))
return false;
/* Check statements. */
return false;
if (bb_with_exit_edge_p (loop, bb))
- exit_bb_seen = true;
+ exit_bb = bb;
}
/* OK. Did not find any potential issues so go ahead in if-convert
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;
bsi_insert_before (bsi, tmp_stmts2, BSI_SAME_STMT);
/* new_cond == prev_cond AND cond */
- 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);
whose phi arguments are selected when cond is true. */
static basic_block
-find_phi_replacement_condition (basic_block bb, tree *cond,
+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;
- basic_block true_bb = NULL;
+ basic_block first_bb = NULL;
+ basic_block second_bb = NULL;
tree tmp_cond;
- edge_iterator ei;
- FOR_EACH_EDGE (e, ei, bb->preds)
- {
- if (p1 == NULL)
- p1 = e->src;
- else
- {
- gcc_assert (!p2);
- p2 = e->src;
- }
- }
+ gcc_assert (EDGE_COUNT (bb->preds) == 2);
+ first_bb = (EDGE_PRED (bb, 0))->src;
+ second_bb = (EDGE_PRED (bb, 1))->src;
- /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
- tmp_cond = p1->aux;
+ /* 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.
+
+ 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_bb->aux;
if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
{
- *cond = p2->aux;
- true_bb = p2;
+ basic_block tmp_bb;
+ tmp_bb = first_bb;
+ first_bb = second_bb;
+ second_bb = tmp_bb;
}
- else
+
+ /* Check if FIRST_BB is loop header or not and make sure that
+ FIRST_BB does not dominate SECOND_BB. */
+ if (first_bb == loop->header
+ || dominated_by_p (CDI_DOMINATORS, second_bb, first_bb))
{
- *cond = p1->aux;
- true_bb = p1;
+ tmp_cond = second_bb->aux;
+ if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
+ {
+ /* Select non loop header condition but do not switch basic blocks. */
+ *cond = invert_truthvalue (unshare_expr (tmp_cond));
+ }
+ else
+ {
+ /* Select non loop header condition. */
+ first_bb = second_bb;
+ *cond = first_bb->aux;
+ }
}
+ else
+ /* FIRST_BB is not loop header */
+ *cond = first_bb->aux;
/* Create temp. for the condition. Vectorizer prefers to have gimple
value as condition. Various targets use different means to communicate
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);
+ bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
*cond = TREE_OPERAND (new_stmt, 0);
}
gcc_assert (*cond);
- return true_bb;
+ return first_bb;
}
}
/* Build new RHS using selected condition and arguments. */
- rhs = build (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
- unshare_expr (cond), unshare_expr (arg_0),
- unshare_expr (arg_1));
+ rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
+ unshare_expr (cond), unshare_expr (arg_0),
+ unshare_expr (arg_1));
/* Create new MODIFY expression using RHS. */
- new_stmt = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
- unshare_expr (PHI_RESULT (phi)), rhs);
+ new_stmt = build2 (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
+ 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))
{
/* 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 (bb, &cond, &bsi);
+ true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi);
while (phi)
{
release_phi_node (phi);
phi = next;
}
- bb_ann (bb)->phi_nodes = NULL;
+ bb->phi_nodes = NULL;
}
return;
}
basic_block bb, exit_bb, merge_target_bb;
unsigned int orig_loop_num_nodes = loop->num_nodes;
unsigned int i;
+ unsigned int n_exits;
+ edge *exits;
+ exits = get_loop_exit_edges (loop, &n_exits);
+ free (exits);
/* Process phi nodes to prepare blocks for merge. */
process_phi_nodes (loop);
if (bb == exit_bb)
{
- edge new_e;
edge_iterator ei;
/* Connect this node with loop header. */
- new_e = make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU);
+ make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU);
set_immediate_dominator (CDI_DOMINATORS, bb, ifc_bbs[0]);
if (exit_bb != loop->latch)
remove_edge (EDGE_PRED (bb, 0));
/* This is loop latch and loop does not have exit then do not
- delete this basic block. Just remove its PREDS and reconnect
- loop->header and loop->latch blocks. */
- if (bb == loop->latch && loop->num_exits == 0)
- {
- make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
- set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
+ delete this basic block. Just remove its PREDS and reconnect
+ loop->header and loop->latch blocks. */
+ if (bb == loop->latch && n_exits == 0)
+ {
+ make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
+ set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
continue;
- }
+ }
while (EDGE_COUNT (bb->succs) > 0)
remove_edge (EDGE_SUCC (bb, 0));
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);
add_referenced_tmp_var (var);
/* Build new statement to assign EXP to new variable. */
- stmt = build (MODIFY_EXPR, type, var, exp);
+ stmt = build2 (MODIFY_EXPR, type, var, exp);
/* Get SSA name for the new variable and set make new statement
its definition statement. */
gcc_assert (loop->num_nodes);
gcc_assert (loop->latch != EXIT_BLOCK_PTR);
- blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
+ blocks = XCNEWVEC (basic_block, loop->num_nodes);
visited = BITMAP_ALLOC (NULL);
blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
/* Tree if-conversion pass management. */
-static void
+static unsigned int
main_tree_if_conversion (void)
{
unsigned i, loop_num;
struct loop *loop;
if (!current_loops)
- return;
+ return 0;
loop_num = current_loops->num;
for (i = 0; i < loop_num; i++)
tree_if_conversion (loop, true);
}
-
+ return 0;
}
static bool
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 */
- 0 /* letter */
+ "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
