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"
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;
if (!var)
{
var = create_tmp_var (TREE_TYPE (base), "ivtmp");
add_referenced_tmp_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
{
if (!tree_expr_nonnegative_p (step)
&& may_negate_without_overflow_p (step))
{
incr_op = MINUS_EXPR;
step = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step));
}
}
}
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)
{
edge pe = loop_preheader_edge (loop);
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);
FOR_EACH_EDGE (e, ei, exit->preds)
add_phi_arg (&phi, use, e);
SSA_NAME_DEF_STMT (use) = def_stmt;
}
static void
add_exit_phis_var (tree var, bitmap livein, bitmap exits)
{
bitmap def;
int index;
basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
bitmap_iterator bi;
bitmap_clear_bit (livein, def_bb->index);
def = BITMAP_XMALLOC ();
bitmap_set_bit (def, def_bb->index);
compute_global_livein (livein, def);
BITMAP_XFREE (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_XMALLOC ();
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)
{
unsigned ver;
basic_block def_bb;
struct loop *def_loop;
if (TREE_CODE (use) != SSA_NAME)
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_XMALLOC ();
bitmap_set_bit (use_blocks[ver], bb->index);
if (!flow_bb_inside_loop_p (def_loop, bb))
mark_for_rewrite (use);
}
static void
find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks)
{
ssa_op_iter iter;
tree var;
basic_block bb = bb_for_stmt (stmt);
get_stmt_operands (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);
}
static void
find_uses_to_rename (bitmap *use_blocks)
{
basic_block bb;
block_stmt_iterator bsi;
tree phi;
unsigned i;
FOR_EACH_BB (bb)
{
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src,
PHI_ARG_DEF (phi, i), use_blocks);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
}
}
void
rewrite_into_loop_closed_ssa (void)
{
bitmap loop_exits = get_loops_exits ();
bitmap *use_blocks;
unsigned i;
bitmap names_to_rename;
gcc_assert (!any_marked_for_rewrite_p ());
use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
find_uses_to_rename (use_blocks);
names_to_rename = marked_ssa_names ();
add_exit_phis (names_to_rename, use_blocks, loop_exits);
for (i = 0; i < num_ssa_names; i++)
BITMAP_XFREE (use_blocks[i]);
free (use_blocks);
BITMAP_XFREE (loop_exits);
BITMAP_XFREE (names_to_rename);
rewrite_ssa_into_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)
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;
get_stmt_operands (stmt);
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
check_loop_closed_ssa_use (bb, var);
}
void
verify_loop_closed_ssa (void)
{
basic_block bb;
block_stmt_iterator bsi;
tree phi;
unsigned i;
verify_ssa ();
FOR_EACH_BB (bb)
{
for (phi = phi_nodes (bb); phi; phi = TREE_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 = TREE_CHAIN (phi))
{
op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, EDGE_SUCC (bb, 0));
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 (EDGE_COUNT (loop->latch->preds) > 1)
return NULL;
bb = EDGE_PRED (loop->latch, 0)->src;
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)->rbi->duplicated = 1;
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)->rbi->duplicated = 0;
}
static void
rename_variables (unsigned first_new_block, bitmap definitions)
{
unsigned i, copy_number = 0;
basic_block bb;
htab_t ssa_name_map = NULL;
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
{
bb = BASIC_BLOCK (i);
if (copy_number != (unsigned) bb->rbi->copy_number)
{
allocate_ssa_names (definitions, &ssa_name_map);
copy_number = bb->rbi->copy_number;
}
rewrite_to_new_ssa_names_bb (bb, ssa_name_map);
}
htab_delete (ssa_name_map);
}
static void
set_phi_def_stmts (basic_block bb)
{
tree phi;
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi;
}
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;
basic_block bb;
unsigned i;
tree phi, arg, map, def;
bitmap definitions;
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
gcc_assert (!any_marked_for_rewrite_p ());
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;
map = PENDING_STMT (e);
PENDING_STMT (e) = NULL;
for (phi = phi_nodes (e->dest), arg = map;
phi;
phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg))
{
def = TREE_VALUE (arg);
add_phi_arg (&phi, def, e);
}
gcc_assert (arg == NULL);
copy_phi_node_args (first_new_block);
definitions = marked_ssa_names ();
rename_variables (first_new_block, definitions);
unmark_all_for_rewrite ();
BITMAP_XFREE (definitions);
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
{
bb = BASIC_BLOCK (i);
set_phi_def_stmts (bb);
if (bb->rbi->copy_number == 1)
set_phi_def_stmts (bb->rbi->original);
}
scev_reset ();
#ifdef ENABLE_CHECKING
verify_loop_closed_ssa ();
#endif
return true;
}
static void
lv_adjust_loop_header_phi (basic_block first, basic_block second,
basic_block new_head, edge e)
{
tree phi1, phi2;
for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
phi2 && phi1;
phi2 = TREE_CHAIN (phi2), phi1 = TREE_CHAIN (phi1))
{
int i;
for (i = 0; i < PHI_NUM_ARGS (phi2); i++)
{
if (PHI_ARG_EDGE (phi2, i)->src == new_head)
{
tree def = PHI_ARG_DEF (phi2, i);
add_phi_arg (&phi1, def, e);
}
}
}
}
static basic_block
lv_adjust_loop_entry_edge (basic_block first_head,
basic_block second_head,
edge e,
tree cond_expr)
{
block_stmt_iterator bsi;
basic_block new_head = NULL;
tree goto1 = NULL_TREE;
tree goto2 = NULL_TREE;
tree new_cond_expr = NULL_TREE;
edge e0, e1;
gcc_assert (e->dest == second_head);
new_head = split_edge (e);
goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
bsi = bsi_start (new_head);
bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
e0 = EDGE_SUCC (new_head, 0);
e0->flags &= ~EDGE_FALLTHRU;
e0->flags |= EDGE_FALSE_VALUE;
e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE);
set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
return new_head;
}
static void
lv_update_pending_stmts (edge e)
{
basic_block dest;
tree phi, arg, def;
if (!PENDING_STMT (e))
return;
dest = e->dest;
for (phi = phi_nodes (dest), arg = PENDING_STMT (e);
phi;
phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg))
{
def = TREE_VALUE (arg);
add_phi_arg (&phi, def, e);
}
PENDING_STMT (e) = NULL;
}
struct loop *
tree_ssa_loop_version (struct loops *loops, struct loop * loop,
tree cond_expr, basic_block *condition_bb)
{
edge entry, latch_edge, exit, true_edge, false_edge;
basic_block first_head, second_head;
int irred_flag;
struct loop *nloop;
if (loop->inner)
return NULL;
entry = loop_preheader_edge (loop);
first_head = entry->dest;
irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1,
NULL, NULL, NULL, NULL, 0))
{
entry->flags |= irred_flag;
return NULL;
}
second_head = entry->dest;
*condition_bb = lv_adjust_loop_entry_edge (first_head, second_head, entry,
cond_expr);
latch_edge = EDGE_SUCC (loop->latch->rbi->copy, 0);
extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge);
nloop = loopify (loops,
latch_edge,
EDGE_PRED (loop->header->rbi->copy, 0),
*condition_bb, true_edge, false_edge,
false );
exit = loop->single_exit;
if (exit)
nloop->single_exit = find_edge (exit->src->rbi->copy, exit->dest);
lv_update_pending_stmts (latch_edge);
extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge);
lv_update_pending_stmts (false_edge);
if (irred_flag)
{
(*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP;
loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
EDGE_PRED ((*condition_bb), 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
}
loop_split_edge_with (loop_preheader_edge (loop), NULL);
loop_split_edge_with (loop_preheader_edge (nloop), NULL);
return nloop;
}