tree-ssa-loop-manip.c [plain text]
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "timevar.h"
#include "cfgloop.h"
#include "tree-pass.h"
#include "cfglayout.h"
#include "tree-scalar-evolution.h"
#include "params.h"
void
create_iv (tree base, tree step, tree var, struct loop *loop,
block_stmt_iterator *incr_pos, bool after,
tree *var_before, tree *var_after)
{
tree stmt, initial, step1, stmts;
tree vb, va;
enum tree_code incr_op = PLUS_EXPR;
edge pe = loop_preheader_edge (loop);
if (!var)
{
var = create_tmp_var (TREE_TYPE (base), "ivtmp");
add_referenced_var (var);
}
vb = make_ssa_name (var, NULL_TREE);
if (var_before)
*var_before = vb;
va = make_ssa_name (var, NULL_TREE);
if (var_after)
*var_after = va;
if (TREE_CODE (step) == INTEGER_CST)
{
if (TYPE_UNSIGNED (TREE_TYPE (step)))
{
step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
if (tree_int_cst_lt (step1, step))
{
incr_op = MINUS_EXPR;
step = step1;
}
}
else
{
bool ovf;
if (!tree_expr_nonnegative_warnv_p (step, &ovf)
&& may_negate_without_overflow_p (step))
{
incr_op = MINUS_EXPR;
step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
}
}
}
step = force_gimple_operand (step, &stmts, true, var);
if (stmts)
bsi_insert_on_edge_immediate_loop (pe, stmts);
stmt = build2 (MODIFY_EXPR, void_type_node, va,
build2 (incr_op, TREE_TYPE (base),
vb, step));
SSA_NAME_DEF_STMT (va) = stmt;
if (after)
bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
else
bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
initial = force_gimple_operand (base, &stmts, true, var);
if (stmts)
bsi_insert_on_edge_immediate_loop (pe, stmts);
stmt = create_phi_node (vb, loop->header);
SSA_NAME_DEF_STMT (vb) = stmt;
add_phi_arg (stmt, initial, loop_preheader_edge (loop));
add_phi_arg (stmt, va, loop_latch_edge (loop));
}
static void
add_exit_phis_edge (basic_block exit, tree use)
{
tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
basic_block def_bb = bb_for_stmt (def_stmt);
struct loop *def_loop;
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, exit->preds)
{
def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
if (!flow_bb_inside_loop_p (def_loop, e->dest))
break;
}
if (!e)
return;
phi = create_phi_node (use, exit);
create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi));
FOR_EACH_EDGE (e, ei, exit->preds)
add_phi_arg (phi, use, e);
}
static void
add_exit_phis_var (tree var, bitmap livein, bitmap exits)
{
bitmap def;
unsigned index;
basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
bitmap_iterator bi;
if (is_gimple_reg (var))
bitmap_clear_bit (livein, def_bb->index);
else
bitmap_set_bit (livein, def_bb->index);
def = BITMAP_ALLOC (NULL);
bitmap_set_bit (def, def_bb->index);
compute_global_livein (livein, def);
BITMAP_FREE (def);
EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
{
add_exit_phis_edge (BASIC_BLOCK (index), var);
}
}
static void
add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
{
unsigned i;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
{
add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
}
}
static bitmap
get_loops_exits (void)
{
bitmap exits = BITMAP_ALLOC (NULL);
basic_block bb;
edge e;
edge_iterator ei;
FOR_EACH_BB (bb)
{
FOR_EACH_EDGE (e, ei, bb->preds)
if (e->src != ENTRY_BLOCK_PTR
&& !flow_bb_inside_loop_p (e->src->loop_father, bb))
{
bitmap_set_bit (exits, bb->index);
break;
}
}
return exits;
}
static void
find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
bitmap need_phis)
{
unsigned ver;
basic_block def_bb;
struct loop *def_loop;
if (TREE_CODE (use) != SSA_NAME)
return;
if (!is_gimple_reg (use))
return;
ver = SSA_NAME_VERSION (use);
def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
if (!def_bb)
return;
def_loop = def_bb->loop_father;
if (!def_loop->outer)
return;
if (!use_blocks[ver])
use_blocks[ver] = BITMAP_ALLOC (NULL);
bitmap_set_bit (use_blocks[ver], bb->index);
bitmap_set_bit (need_phis, ver);
}
static void
find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis)
{
ssa_op_iter iter;
tree var;
basic_block bb = bb_for_stmt (stmt);
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
find_uses_to_rename_use (bb, var, use_blocks, need_phis);
}
static void
find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
{
block_stmt_iterator bsi;
edge e;
edge_iterator ei;
tree phi;
FOR_EACH_EDGE (e, ei, bb->succs)
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
use_blocks, need_phis);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis);
}
static void
find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
{
basic_block bb;
unsigned index;
bitmap_iterator bi;
if (changed_bbs && !bitmap_empty_p (changed_bbs))
{
EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
{
find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis);
}
}
else
{
FOR_EACH_BB (bb)
{
find_uses_to_rename_bb (bb, use_blocks, need_phis);
}
}
}
void
rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
{
bitmap loop_exits = get_loops_exits ();
bitmap *use_blocks;
unsigned i, old_num_ssa_names;
bitmap names_to_rename = BITMAP_ALLOC (NULL);
update_ssa (update_flag);
old_num_ssa_names = num_ssa_names;
use_blocks = XCNEWVEC (bitmap, old_num_ssa_names);
find_uses_to_rename (changed_bbs, use_blocks, names_to_rename);
add_exit_phis (names_to_rename, use_blocks, loop_exits);
for (i = 0; i < old_num_ssa_names; i++)
BITMAP_FREE (use_blocks[i]);
free (use_blocks);
BITMAP_FREE (loop_exits);
BITMAP_FREE (names_to_rename);
update_ssa (TODO_update_ssa);
}
static void
check_loop_closed_ssa_use (basic_block bb, tree use)
{
tree def;
basic_block def_bb;
if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use))
return;
def = SSA_NAME_DEF_STMT (use);
def_bb = bb_for_stmt (def);
gcc_assert (!def_bb
|| flow_bb_inside_loop_p (def_bb->loop_father, bb));
}
static void
check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
{
ssa_op_iter iter;
tree var;
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
check_loop_closed_ssa_use (bb, var);
}
void
verify_loop_closed_ssa (void)
{
basic_block bb;
block_stmt_iterator bsi;
tree phi;
unsigned i;
if (current_loops == NULL)
return;
verify_ssa (false);
FOR_EACH_BB (bb)
{
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
PHI_ARG_DEF (phi, i));
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
}
}
void
split_loop_exit_edge (edge exit)
{
basic_block dest = exit->dest;
basic_block bb = loop_split_edge_with (exit, NULL);
tree phi, new_phi, new_name, name;
use_operand_p op_p;
for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
{
op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
name = USE_FROM_PTR (op_p);
if (TREE_CODE (name) != SSA_NAME)
continue;
new_name = duplicate_ssa_name (name, NULL);
new_phi = create_phi_node (new_name, bb);
SSA_NAME_DEF_STMT (new_name) = new_phi;
add_phi_arg (new_phi, name, exit);
SET_USE (op_p, new_name);
}
}
basic_block
bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
{
basic_block src, dest, new_bb;
struct loop *loop_c;
src = e->src;
dest = e->dest;
loop_c = find_common_loop (src->loop_father, dest->loop_father);
new_bb = bsi_insert_on_edge_immediate (e, stmt);
if (!new_bb)
return NULL;
add_bb_to_loop (new_bb, loop_c);
if (dest->loop_father->latch == src)
dest->loop_father->latch = new_bb;
return new_bb;
}
basic_block
ip_end_pos (struct loop *loop)
{
return loop->latch;
}
basic_block
ip_normal_pos (struct loop *loop)
{
tree last;
basic_block bb;
edge exit;
if (!single_pred_p (loop->latch))
return NULL;
bb = single_pred (loop->latch);
last = last_stmt (bb);
if (TREE_CODE (last) != COND_EXPR)
return NULL;
exit = EDGE_SUCC (bb, 0);
if (exit->dest == loop->latch)
exit = EDGE_SUCC (bb, 1);
if (flow_bb_inside_loop_p (loop, exit->dest))
return NULL;
return bb;
}
void
standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
bool *insert_after)
{
basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
tree last = last_stmt (latch);
if (!bb
|| (last && TREE_CODE (last) != LABEL_EXPR))
{
*bsi = bsi_last (latch);
*insert_after = true;
}
else
{
*bsi = bsi_last (bb);
*insert_after = false;
}
}
static void
copy_phi_node_args (unsigned first_new_block)
{
unsigned i;
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
BASIC_BLOCK (i)->flags |= BB_DUPLICATED;
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
add_phi_args_after_copy_bb (BASIC_BLOCK (i));
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED;
}
bool
tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
struct loops *loops,
unsigned int ndupl, sbitmap wont_exit,
edge orig, edge *to_remove,
unsigned int *n_to_remove, int flags)
{
unsigned first_new_block;
if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
return false;
if (!(loops->state & LOOPS_HAVE_PREHEADERS))
return false;
#ifdef ENABLE_CHECKING
verify_loop_closed_ssa ();
#endif
first_new_block = last_basic_block;
if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
orig, to_remove, n_to_remove, flags))
return false;
flush_pending_stmts (e);
copy_phi_node_args (first_new_block);
scev_reset ();
return true;
}
static tree
build_if_stmt (tree cond, tree then_label, tree else_label)
{
return build3 (COND_EXPR, void_type_node,
cond,
build1 (GOTO_EXPR, void_type_node, then_label),
build1 (GOTO_EXPR, void_type_node, else_label));
}
bool
can_unroll_loop_p (struct loop *loop, unsigned factor,
struct tree_niter_desc *niter)
{
edge exit;
exit = single_dom_exit (loop);
if (!exit)
return false;
if (!number_of_iterations_exit (loop, exit, niter, false)
|| niter->cmp == ERROR_MARK
|| contains_abnormal_ssa_name_p (niter->may_be_zero)
|| contains_abnormal_ssa_name_p (niter->control.base)
|| contains_abnormal_ssa_name_p (niter->control.step)
|| contains_abnormal_ssa_name_p (niter->bound))
return false;
if (!can_duplicate_loop_p (loop))
return false;
if (tree_num_loop_insns (loop) * factor
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS))
return false;
return true;
}
static void
determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc,
unsigned factor, tree *enter_cond,
tree *exit_base, tree *exit_step,
enum tree_code *exit_cmp, tree *exit_bound)
{
tree stmts;
tree base = desc->control.base;
tree step = desc->control.step;
tree bound = desc->bound;
tree type = TREE_TYPE (base);
tree bigstep, delta;
tree min = lower_bound_in_type (type, type);
tree max = upper_bound_in_type (type, type);
enum tree_code cmp = desc->cmp;
tree cond = boolean_true_node, assum;
*enter_cond = boolean_false_node;
*exit_base = NULL_TREE;
*exit_step = NULL_TREE;
*exit_cmp = ERROR_MARK;
*exit_bound = NULL_TREE;
gcc_assert (cmp != ERROR_MARK);
if (cmp == NE_EXPR)
{
if (tree_int_cst_sign_bit (step))
cmp = GT_EXPR;
else
cmp = LT_EXPR;
}
else if (cmp == LT_EXPR)
{
gcc_assert (!tree_int_cst_sign_bit (step));
}
else if (cmp == GT_EXPR)
{
gcc_assert (tree_int_cst_sign_bit (step));
}
else
gcc_unreachable ();
if (!zero_p (desc->may_be_zero))
cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
invert_truthvalue (desc->may_be_zero),
cond);
bigstep = fold_build2 (MULT_EXPR, type, step,
build_int_cst_type (type, factor));
delta = fold_build2 (MINUS_EXPR, type, bigstep, step);
if (cmp == LT_EXPR)
assum = fold_build2 (GE_EXPR, boolean_type_node,
bound,
fold_build2 (PLUS_EXPR, type, min, delta));
else
assum = fold_build2 (LE_EXPR, boolean_type_node,
bound,
fold_build2 (PLUS_EXPR, type, max, delta));
cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
bound = fold_build2 (MINUS_EXPR, type, bound, delta);
assum = fold_build2 (cmp, boolean_type_node, base, bound);
cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE);
if (stmts)
bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
if (!is_gimple_condexpr (cond))
{
cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
if (stmts)
bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
}
*enter_cond = cond;
base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
if (stmts)
bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
if (stmts)
bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
*exit_base = base;
*exit_step = bigstep;
*exit_cmp = cmp;
*exit_bound = bound;
}
void
tree_unroll_loop (struct loops *loops, struct loop *loop, unsigned factor,
edge exit, struct tree_niter_desc *desc)
{
tree dont_exit, exit_if, ctr_before, ctr_after;
tree enter_main_cond, exit_base, exit_step, exit_bound;
enum tree_code exit_cmp;
tree phi_old_loop, phi_new_loop, phi_rest, init, next, new_init, var;
struct loop *new_loop;
basic_block rest, exit_bb;
edge old_entry, new_entry, old_latch, precond_edge, new_exit;
edge nonexit, new_nonexit;
block_stmt_iterator bsi;
use_operand_p op;
bool ok;
unsigned est_niter;
unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
sbitmap wont_exit;
est_niter = expected_loop_iterations (loop);
determine_exit_conditions (loop, desc, factor,
&enter_main_cond, &exit_base, &exit_step,
&exit_cmp, &exit_bound);
new_loop = loop_version (loops, loop, enter_main_cond, NULL, true);
gcc_assert (new_loop != NULL);
update_ssa (TODO_update_ssa);
dont_exit = ((exit->flags & EDGE_TRUE_VALUE)
? boolean_false_node
: boolean_true_node);
if (exit == EDGE_SUCC (exit->src, 0))
nonexit = EDGE_SUCC (exit->src, 1);
else
nonexit = EDGE_SUCC (exit->src, 0);
nonexit->probability = REG_BR_PROB_BASE;
exit->probability = 0;
nonexit->count += exit->count;
exit->count = 0;
exit_if = last_stmt (exit->src);
COND_EXPR_COND (exit_if) = dont_exit;
update_stmt (exit_if);
wont_exit = sbitmap_alloc (factor);
sbitmap_ones (wont_exit);
ok = tree_duplicate_loop_to_header_edge
(loop, loop_latch_edge (loop), loops, factor - 1,
wont_exit, NULL, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ);
free (wont_exit);
gcc_assert (ok);
update_ssa (TODO_update_ssa);
rest = loop_preheader_edge (new_loop)->src;
precond_edge = single_pred_edge (rest);
loop_split_edge_with (loop_latch_edge (loop), NULL);
exit_bb = single_pred (loop->latch);
new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
new_exit->count = loop_preheader_edge (loop)->count;
est_niter = est_niter / factor + 1;
new_exit->probability = REG_BR_PROB_BASE / est_niter;
new_nonexit = single_pred_edge (loop->latch);
new_nonexit->flags = EDGE_TRUE_VALUE;
new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
old_entry = loop_preheader_edge (loop);
new_entry = loop_preheader_edge (new_loop);
old_latch = loop_latch_edge (loop);
for (phi_old_loop = phi_nodes (loop->header),
phi_new_loop = phi_nodes (new_loop->header);
phi_old_loop;
phi_old_loop = PHI_CHAIN (phi_old_loop),
phi_new_loop = PHI_CHAIN (phi_new_loop))
{
init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry);
op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry);
gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch);
if (TREE_CODE (next) == SSA_NAME)
var = SSA_NAME_VAR (next);
else if (TREE_CODE (init) == SSA_NAME)
var = SSA_NAME_VAR (init);
else
{
var = create_tmp_var (TREE_TYPE (init), "unrinittmp");
add_referenced_var (var);
}
new_init = make_ssa_name (var, NULL_TREE);
phi_rest = create_phi_node (new_init, rest);
SSA_NAME_DEF_STMT (new_init) = phi_rest;
add_phi_arg (phi_rest, init, precond_edge);
add_phi_arg (phi_rest, next, new_exit);
SET_USE (op, new_init);
}
bsi = bsi_last (exit_bb);
create_iv (exit_base, exit_step, NULL_TREE, loop,
&bsi, true, &ctr_before, &ctr_after);
exit_if = build_if_stmt (build2 (exit_cmp, boolean_type_node, ctr_after,
exit_bound),
tree_block_label (loop->latch),
tree_block_label (rest));
bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT);
verify_flow_info ();
verify_dominators (CDI_DOMINATORS);
verify_loop_structure (loops);
verify_loop_closed_ssa ();
}