#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "errors.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-flow.h"
#include "tree-dump.h"
#include "cfgloop.h"
#include "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
#include "target.h"
static void 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_modify_expr_p (struct loop *, basic_block, tree);
static bool if_convertible_stmt_p (struct loop *, basic_block, tree);
static bool if_convertible_bb_p (struct loop *, basic_block, bool);
static bool if_convertible_loop_p (struct loop *, bool);
static void add_to_predicate_list (basic_block, tree);
static tree add_to_dst_predicate_list (struct loop * loop, basic_block, tree, tree,
block_stmt_iterator *);
static void clean_predicate_lists (struct loop *loop);
static basic_block find_phi_replacement_condition (basic_block, tree *,
block_stmt_iterator *);
static void replace_phi_with_cond_modify_expr (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 basic_block *ifc_bbs;
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 (!if_convertible_loop_p (loop, for_vectorizer))
{
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);
free_df ();
return false;
}
cond = NULL_TREE;
for (i = 0; i < loop->num_nodes; i++)
{
bb = ifc_bbs [i];
cond = bb->aux;
for (itr = bsi_start (bb); !bsi_end_p (itr); )
{
tree t = bsi_stmt (itr);
cond = tree_if_convert_stmt (loop, t, cond, &itr);
if (!bsi_end_p (itr))
bsi_next (&itr);
}
if (EDGE_COUNT (bb->succs) == 1)
{
basic_block bb_n = EDGE_SUCC (bb, 0)->dest;
if (cond != NULL_TREE)
add_to_predicate_list (bb_n, cond);
cond = NULL_TREE;
}
}
combine_blocks (loop);
clean_predicate_lists (loop);
free (ifc_bbs);
ifc_bbs = NULL;
free_df ();
return true;
}
static tree
tree_if_convert_stmt (struct loop * loop, tree t, tree cond,
block_stmt_iterator *bsi)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "------if-convert stmt\n");
print_generic_stmt (dump_file, t, TDF_SLIM);
print_generic_stmt (dump_file, cond, TDF_SLIM);
}
switch (TREE_CODE (t))
{
case LABEL_EXPR:
break;
case MODIFY_EXPR:
break;
case GOTO_EXPR:
add_to_predicate_list (bb_for_stmt (TREE_OPERAND (t, 1)), cond);
bsi_remove (bsi);
cond = NULL_TREE;
break;
case COND_EXPR:
tree_if_convert_cond_expr (loop, t, cond, bsi);
cond = NULL_TREE;
break;
default:
gcc_unreachable ();
}
return cond;
}
static void
tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond,
block_stmt_iterator *bsi)
{
tree c, c2, new_cond;
edge true_edge, false_edge;
new_cond = NULL_TREE;
gcc_assert (TREE_CODE (stmt) == COND_EXPR);
c = COND_EXPR_COND (stmt);
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);
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);
}
c2 = invert_truthvalue (unshare_expr (c));
add_to_dst_predicate_list (loop, false_edge->dest, cond, c2, bsi);
if (!bb_with_exit_edge_p (bb_for_stmt (stmt)))
{
bsi_remove (bsi);
cond = NULL_TREE;
}
return;
}
static bool
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++)
{
tree use = immediate_use (df, j);
if (TREE_CODE (use) == PHI_NODE)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Difficult to handle this virtual phi.\n");
return false;
}
}
}
return true;
}
static bool
if_convertible_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "-------------------------\n");
print_generic_stmt (dump_file, m_expr, TDF_SLIM);
}
if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "stmt is movable. Don't take risk\n");
return false;
}
if (bb != loop->header
&& tree_could_trap_p (TREE_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 (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "CALL_EXPR \n");
return false;
}
if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME
&& bb != loop->header
&& !bb_with_exit_edge_p (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);
}
return false;
}
return true;
}
static bool
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_convertible_modify_expr_p (loop, bb, stmt))
return false;
break;
case GOTO_EXPR:
case COND_EXPR:
break;
default:
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);
}
return false;
break;
}
return true;
}
static bool
if_convertible_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen)
{
edge e;
edge_iterator ei;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "----------[%d]-------------\n", bb->index);
if (exit_bb_seen)
{
if (bb != loop->latch)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "basic block after exit bb but before latch\n");
return false;
}
else if (!empty_block_p (bb))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "non empty basic block after exit bb\n");
return false;
}
}
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))
fprintf (dump_file,"Difficult to handle edges\n");
return false;
}
return true;
}
static bool
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;
edge_iterator ei;
bool exit_bb_seen = false;
if (!loop || loop->inner)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "not inner most loop\n");
return false;
}
flow_loop_scan (loop, LOOP_ALL);
if (loop->num_nodes <= 2)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "less than 2 basic blocks\n");
return false;
}
if (loop->num_exits > 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "multiple exits\n");
return false;
}
FOR_EACH_EDGE (e, ei, loop->header->succs)
if ( e->flags & EDGE_LOOP_EXIT)
return false;
compute_immediate_uses (TDFA_USE_OPS|TDFA_USE_VOPS, NULL);
calculate_dominance_info (CDI_DOMINATORS);
calculate_dominance_info (CDI_POST_DOMINATORS);
ifc_bbs = get_loop_body_in_if_conv_order (loop);
if (!ifc_bbs)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,"Irreducible loop\n");
free_dominance_info (CDI_POST_DOMINATORS);
return false;
}
for (i = 0; i < loop->num_nodes; i++)
{
bb = ifc_bbs[i];
if (!if_convertible_bb_p (loop, bb, exit_bb_seen))
return false;
for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr))
if (!if_convertible_stmt_p (loop, bb, bsi_stmt (itr)))
return false;
for (phi = phi_nodes (bb); 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 (dump_file)
fprintf (dump_file,"Applying if-conversion\n");
free_dominance_info (CDI_POST_DOMINATORS);
return true;
}
static void
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));
else
cond = new_cond;
bb->aux = cond;
}
static tree
add_to_dst_predicate_list (struct loop * loop, basic_block bb,
tree prev_cond, tree cond,
block_stmt_iterator *bsi)
{
tree new_cond = NULL_TREE;
if (!flow_bb_inside_loop_p (loop, bb))
return NULL_TREE;
if (prev_cond == boolean_true_node || !prev_cond)
new_cond = unshare_expr (cond);
else
{
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);
tmp = build (TRUTH_AND_EXPR, boolean_type_node,
unshare_expr (prev_cond), cond);
tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT);
new_cond = TREE_OPERAND (tmp_stmt, 0);
}
add_to_predicate_list (bb, new_cond);
return new_cond;
}
static void
clean_predicate_lists (struct loop *loop)
{
basic_block *bb;
unsigned int i;
bb = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
bb[i]->aux = NULL;
free (bb);
}
static basic_block
find_phi_replacement_condition (basic_block bb, tree *cond,
block_stmt_iterator *bsi)
{
edge e;
basic_block p1 = NULL;
basic_block p2 = NULL;
basic_block true_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;
}
}
tmp_cond = p1->aux;
if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
{
*cond = p2->aux;
true_bb = p2;
}
else
{
*cond = p1->aux;
true_bb = p1;
}
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);
}
gcc_assert (*cond);
return true_bb;
}
static void
replace_phi_with_cond_modify_expr (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;
gcc_assert (TREE_CODE (phi) == PHI_NODE);
gcc_assert (PHI_NUM_ARGS (phi) == 2);
bb = bb_for_stmt (phi);
new_stmt = NULL_TREE;
arg_0 = NULL_TREE;
arg_1 = NULL_TREE;
if (EDGE_PRED (bb, 1)->src == true_bb)
{
arg_0 = PHI_ARG_DEF (phi, 1);
arg_1 = PHI_ARG_DEF (phi, 0);
}
else
{
arg_0 = PHI_ARG_DEF (phi, 0);
arg_1 = PHI_ARG_DEF (phi, 1);
}
rhs = build (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
unshare_expr (cond), unshare_expr (arg_0),
unshare_expr (arg_1));
new_stmt = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
unshare_expr (PHI_RESULT (phi)), rhs);
SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
set_bb_for_stmt (new_stmt, bb);
bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT);
bsi_next (bsi);
modify_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);
}
}
static void
process_phi_nodes (struct loop *loop)
{
basic_block bb;
unsigned int orig_loop_num_nodes = loop->num_nodes;
unsigned int i;
for (i = 1; i < orig_loop_num_nodes; i++)
{
tree phi, cond = NULL_TREE;
block_stmt_iterator bsi;
basic_block true_bb = NULL;
bb = ifc_bbs[i];
if (bb == loop->header)
continue;
phi = phi_nodes (bb);
bsi = bsi_after_labels (bb);
if (phi)
true_bb = find_phi_replacement_condition (bb, &cond, &bsi);
while (phi)
{
tree next = PHI_CHAIN (phi);
replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi);
release_phi_node (phi);
phi = next;
}
bb_ann (bb)->phi_nodes = NULL;
}
return;
}
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;
unsigned int n_exits;
edge *exits = get_loop_exit_edges (loop, &n_exits);
process_phi_nodes (loop);
exit_bb = NULL;
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 (!exit_bb && bb_with_exit_edge_p (bb))
exit_bb = bb;
if (bb == exit_bb)
{
edge new_e;
edge_iterator ei;
new_e = make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU);
set_immediate_dominator (CDI_DOMINATORS, bb, ifc_bbs[0]);
if (exit_bb != loop->latch)
{
FOR_EACH_EDGE (e, ei, bb->succs)
if (!(e->flags & EDGE_LOOP_EXIT))
{
redirect_edge_and_branch (e, loop->latch);
set_immediate_dominator (CDI_DOMINATORS, loop->latch, bb);
}
}
continue;
}
if (bb == loop->latch && empty_block_p (bb))
continue;
while (EDGE_COUNT (bb->preds) > 0)
remove_edge (EDGE_PRED (bb, 0));
if (bb == loop->latch && n_exits == 0)
{
exits = NULL;
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);
else
{
set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
bsi_next (&bsi);
}
}
last = tsi_last (merge_target_bb->stmt_list);
tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT);
bb->stmt_list = NULL;
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);
if (bb == loop->latch)
loop->latch = merge_target_bb;
remove_bb_from_loops (bb);
expunge_block (bb);
}
if (exit_bb
&& loop->header != loop->latch
&& exit_bb != loop->latch
&& empty_block_p (loop->latch))
{
if (can_merge_blocks_p (loop->header, exit_bb))
{
remove_bb_from_loops (exit_bb);
merge_blocks (loop->header, exit_bb);
}
}
}
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;
var = create_tmp_var (type, name);
add_referenced_tmp_var (var);
stmt = build (MODIFY_EXPR, type, var, exp);
new_name = make_ssa_name (var, stmt);
TREE_OPERAND (stmt, 0) = new_name;
SSA_NAME_DEF_STMT (new_name) = stmt;
return stmt;
}
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;
}
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 = xcalloc (loop->num_nodes, sizeof (basic_block));
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)
{
bitmap_set_bit (visited, bb->index);
blocks[visited_count++] = bb;
}
}
index++;
if (index == loop->num_nodes
&& visited_count != loop->num_nodes)
{
index = 0;
}
}
free (blocks_in_bfs_order);
BITMAP_FREE (visited);
return blocks;
}
static bool
bb_with_exit_edge_p (basic_block bb)
{
edge e;
edge_iterator ei;
bool exit_edge_found = false;
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->flags & EDGE_LOOP_EXIT)
{
exit_edge_found = true;
break;
}
return exit_edge_found;
}
static void
main_tree_if_conversion (void)
{
unsigned i, loop_num;
struct loop *loop;
if (!current_loops)
return;
loop_num = current_loops->num;
for (i = 0; i < loop_num; i++)
{
loop = current_loops->parray[i];
if (!loop)
continue;
tree_if_conversion (loop, true);
}
}
static bool
gate_tree_if_conversion (void)
{
return flag_tree_vectorize != 0;
}
struct tree_opt_pass pass_if_conversion =
{
"ifcvt",
gate_tree_if_conversion,
main_tree_if_conversion,
NULL,
NULL,
0,
0,
PROP_cfg | PROP_ssa | PROP_alias,
0,
0,
TODO_dump_func,
TODO_dump_func
| TODO_verify_ssa
| TODO_verify_stmts
| TODO_verify_flow,
0
};