#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "ggc.h"
#include "tree.h"
#include "target.h"
#include "rtl.h"
#include "basic-block.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "timevar.h"
#include "cfgloop.h"
#include "cfglayout.h"
#include "expr.h"
#include "optabs.h"
#include "params.h"
#include "toplev.h"
#include "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "input.h"
#include "debug.h"
#include "tree-vectorizer.h"
#include "tree-pass.h"
static struct loop *slpeel_tree_duplicate_loop_to_edge_cfg
(struct loop *, struct loops *, edge);
static void slpeel_update_phis_for_duplicate_loop
(struct loop *, struct loop *, bool after);
static void slpeel_update_phi_nodes_for_guard1
(edge, struct loop *, bool, basic_block *, bitmap *);
static void slpeel_update_phi_nodes_for_guard2
(edge, struct loop *, bool, basic_block *);
static edge slpeel_add_loop_guard (basic_block, tree, basic_block, basic_block);
static void rename_use_op (use_operand_p);
static void rename_variables_in_bb (basic_block);
static void rename_variables_in_loop (struct loop *);
static void vect_set_dump_settings (void);
FILE *vect_dump;
enum verbosity_levels vect_verbosity_level = MAX_VERBOSITY_LEVEL;
unsigned int vect_loops_num;
static LOC vect_loop_location;
bitmap vect_vnames_to_rename;
static void
rename_use_op (use_operand_p op_p)
{
tree new_name;
if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
return;
new_name = get_current_def (USE_FROM_PTR (op_p));
if (!new_name)
return;
SET_USE (op_p, new_name);
}
static void
rename_variables_in_bb (basic_block bb)
{
tree phi;
block_stmt_iterator bsi;
tree stmt;
use_operand_p use_p;
ssa_op_iter iter;
edge e;
edge_iterator ei;
struct loop *loop = bb->loop_father;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt = bsi_stmt (bsi);
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
(SSA_OP_ALL_USES | SSA_OP_ALL_KILLS))
rename_use_op (use_p);
}
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (!flow_bb_inside_loop_p (loop, e->dest))
continue;
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e));
}
}
static void
rename_variables_in_loop (struct loop *loop)
{
unsigned i;
basic_block *bbs;
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
rename_variables_in_bb (bbs[i]);
free (bbs);
}
static void
slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
struct loop *new_loop, bool after)
{
tree new_ssa_name;
tree phi_new, phi_orig;
tree def;
edge orig_loop_latch = loop_latch_edge (orig_loop);
edge orig_entry_e = loop_preheader_edge (orig_loop);
edge new_loop_exit_e = new_loop->single_exit;
edge new_loop_entry_e = loop_preheader_edge (new_loop);
edge entry_arg_e = (after ? orig_loop_latch : orig_entry_e);
for (phi_new = phi_nodes (new_loop->header),
phi_orig = phi_nodes (orig_loop->header);
phi_new && phi_orig;
phi_new = PHI_CHAIN (phi_new), phi_orig = PHI_CHAIN (phi_orig))
{
def = PHI_ARG_DEF_FROM_EDGE (phi_orig, entry_arg_e);
add_phi_arg (phi_new, def, new_loop_entry_e);
def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
if (TREE_CODE (def) != SSA_NAME)
continue;
new_ssa_name = get_current_def (def);
if (!new_ssa_name)
{
new_ssa_name = PHI_RESULT (phi_new);
}
add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop));
if (!after)
{
gcc_assert (new_loop_exit_e == orig_entry_e);
SET_PHI_ARG_DEF (phi_orig,
new_loop_exit_e->dest_idx,
new_ssa_name);
}
}
}
static void
slpeel_update_phi_nodes_for_guard1 (edge guard_edge, struct loop *loop,
bool is_new_loop, basic_block *new_exit_bb,
bitmap *defs)
{
tree orig_phi, new_phi;
tree update_phi, update_phi2;
tree guard_arg, loop_arg;
basic_block new_merge_bb = guard_edge->dest;
edge e = EDGE_SUCC (new_merge_bb, 0);
basic_block update_bb = e->dest;
basic_block orig_bb = loop->header;
edge new_exit_e;
tree current_new_name;
tree name;
*new_exit_bb = split_edge (loop->single_exit);
add_bb_to_loop (*new_exit_bb, loop->outer);
new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
for (orig_phi = phi_nodes (orig_bb), update_phi = phi_nodes (update_bb);
orig_phi && update_phi;
orig_phi = PHI_CHAIN (orig_phi), update_phi = PHI_CHAIN (update_phi))
{
name = PHI_RESULT (orig_phi);
if (!is_gimple_reg (SSA_NAME_VAR (name)))
bitmap_set_bit (vect_vnames_to_rename, SSA_NAME_VERSION (name));
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
new_merge_bb);
loop_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, EDGE_SUCC (loop->latch, 0));
guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, loop_preheader_edge (loop));
add_phi_arg (new_phi, loop_arg, new_exit_e);
add_phi_arg (new_phi, guard_arg, guard_edge);
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == loop_arg
|| PHI_ARG_DEF_FROM_EDGE (update_phi, e) == guard_arg);
SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
update_phi2 = new_phi;
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
*new_exit_bb);
add_phi_arg (new_phi, loop_arg, loop->single_exit);
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
if (is_new_loop)
current_new_name = loop_arg;
else
{
current_new_name = get_current_def (loop_arg);
if (!current_new_name)
continue;
}
gcc_assert (get_current_def (current_new_name) == NULL_TREE);
set_current_def (current_new_name, PHI_RESULT (new_phi));
bitmap_set_bit (*defs, SSA_NAME_VERSION (current_new_name));
}
set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
}
static void
slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop,
bool is_new_loop, basic_block *new_exit_bb)
{
tree orig_phi, new_phi;
tree update_phi, update_phi2;
tree guard_arg, loop_arg;
basic_block new_merge_bb = guard_edge->dest;
edge e = EDGE_SUCC (new_merge_bb, 0);
basic_block update_bb = e->dest;
edge new_exit_e;
tree orig_def, orig_def_new_name;
tree new_name, new_name2;
tree arg;
*new_exit_bb = split_edge (loop->single_exit);
add_bb_to_loop (*new_exit_bb, loop->outer);
new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
for (update_phi = phi_nodes (update_bb); update_phi;
update_phi = PHI_CHAIN (update_phi))
{
orig_phi = update_phi;
orig_def = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
if (TREE_CODE (orig_def) != SSA_NAME)
continue;
orig_def_new_name = get_current_def (orig_def);
arg = NULL_TREE;
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
new_merge_bb);
new_name = orig_def;
new_name2 = NULL_TREE;
if (orig_def_new_name)
{
new_name = orig_def_new_name;
new_name2 = get_current_def (new_name);
}
if (is_new_loop)
{
guard_arg = orig_def;
loop_arg = new_name;
}
else
{
guard_arg = new_name;
loop_arg = orig_def;
}
if (new_name2)
guard_arg = new_name2;
add_phi_arg (new_phi, loop_arg, new_exit_e);
add_phi_arg (new_phi, guard_arg, guard_edge);
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == orig_def);
SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
update_phi2 = new_phi;
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
*new_exit_bb);
add_phi_arg (new_phi, loop_arg, loop->single_exit);
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
if (guard_arg == new_name2)
continue;
arg = guard_arg;
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
guard_edge->src);
gcc_assert (EDGE_COUNT (guard_edge->src->preds) == 1);
add_phi_arg (new_phi, arg, EDGE_PRED (guard_edge->src, 0));
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, guard_edge)
== guard_arg);
SET_PHI_ARG_DEF (update_phi2, guard_edge->dest_idx, PHI_RESULT (new_phi));
}
set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
}
void
slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters)
{
tree indx_before_incr, indx_after_incr, cond_stmt, cond;
tree orig_cond;
edge exit_edge = loop->single_exit;
block_stmt_iterator loop_cond_bsi;
block_stmt_iterator incr_bsi;
bool insert_after;
tree begin_label = tree_block_label (loop->latch);
tree exit_label = tree_block_label (loop->single_exit->dest);
tree init = build_int_cst (TREE_TYPE (niters), 0);
tree step = build_int_cst (TREE_TYPE (niters), 1);
tree then_label;
tree else_label;
LOC loop_loc;
orig_cond = get_loop_exit_condition (loop);
gcc_assert (orig_cond);
loop_cond_bsi = bsi_for_stmt (orig_cond);
standard_iv_increment_position (loop, &incr_bsi, &insert_after);
create_iv (init, step, NULL_TREE, loop,
&incr_bsi, insert_after, &indx_before_incr, &indx_after_incr);
if (exit_edge->flags & EDGE_TRUE_VALUE)
{
cond = build2 (GE_EXPR, boolean_type_node, indx_after_incr, niters);
then_label = build1 (GOTO_EXPR, void_type_node, exit_label);
else_label = build1 (GOTO_EXPR, void_type_node, begin_label);
}
else
{
cond = build2 (LT_EXPR, boolean_type_node, indx_after_incr, niters);
then_label = build1 (GOTO_EXPR, void_type_node, begin_label);
else_label = build1 (GOTO_EXPR, void_type_node, exit_label);
}
cond_stmt = build3 (COND_EXPR, TREE_TYPE (orig_cond), cond,
then_label, else_label);
bsi_insert_before (&loop_cond_bsi, cond_stmt, BSI_SAME_STMT);
bsi_remove (&loop_cond_bsi, true);
loop_loc = find_loop_location (loop);
if (dump_file && (dump_flags & TDF_DETAILS))
{
if (loop_loc != UNKNOWN_LOC)
fprintf (dump_file, "\nloop at %s:%d: ",
LOC_FILE (loop_loc), LOC_LINE (loop_loc));
print_generic_expr (dump_file, cond_stmt, TDF_SLIM);
}
loop->nb_iterations = niters;
}
static struct loop *
slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, struct loops *loops,
edge e)
{
struct loop *new_loop;
basic_block *new_bbs, *bbs;
bool at_exit;
bool was_imm_dom;
basic_block exit_dest;
tree phi, phi_arg;
at_exit = (e == loop->single_exit);
if (!at_exit && e != loop_preheader_edge (loop))
return NULL;
bbs = get_loop_body (loop);
if (!can_copy_bbs_p (bbs, loop->num_nodes))
{
free (bbs);
return NULL;
}
new_loop = duplicate_loop (loops, loop, loop->outer);
if (!new_loop)
{
free (bbs);
return NULL;
}
exit_dest = loop->single_exit->dest;
was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
exit_dest) == loop->header ?
true : false);
new_bbs = XNEWVEC (basic_block, loop->num_nodes);
copy_bbs (bbs, loop->num_nodes, new_bbs,
&loop->single_exit, 1, &new_loop->single_exit, NULL,
e->src);
for (phi = phi_nodes (exit_dest); phi; phi = PHI_CHAIN (phi))
{
phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, loop->single_exit);
if (phi_arg)
{
edge new_loop_exit_edge;
if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
else
new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
add_phi_arg (phi, phi_arg, new_loop_exit_edge);
}
}
if (at_exit)
{
redirect_edge_and_branch_force (e, new_loop->header);
set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
if (was_imm_dom)
set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
}
else
{
edge new_exit_e;
edge entry_e = loop_preheader_edge (loop);
basic_block preheader = entry_e->src;
if (!flow_bb_inside_loop_p (new_loop,
EDGE_SUCC (new_loop->header, 0)->dest))
new_exit_e = EDGE_SUCC (new_loop->header, 0);
else
new_exit_e = EDGE_SUCC (new_loop->header, 1);
redirect_edge_and_branch_force (new_exit_e, loop->header);
set_immediate_dominator (CDI_DOMINATORS, loop->header,
new_exit_e->src);
for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
{
phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
if (phi_arg)
add_phi_arg (phi, phi_arg, new_exit_e);
}
redirect_edge_and_branch_force (entry_e, new_loop->header);
set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
}
free (new_bbs);
free (bbs);
return new_loop;
}
static edge
slpeel_add_loop_guard (basic_block guard_bb, tree cond, basic_block exit_bb,
basic_block dom_bb)
{
block_stmt_iterator bsi;
edge new_e, enter_e;
tree cond_stmt, then_label, else_label;
enter_e = EDGE_SUCC (guard_bb, 0);
enter_e->flags &= ~EDGE_FALLTHRU;
enter_e->flags |= EDGE_FALSE_VALUE;
bsi = bsi_last (guard_bb);
then_label = build1 (GOTO_EXPR, void_type_node,
tree_block_label (exit_bb));
else_label = build1 (GOTO_EXPR, void_type_node,
tree_block_label (enter_e->dest));
cond_stmt = build3 (COND_EXPR, void_type_node, cond,
then_label, else_label);
bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
new_e = make_edge (guard_bb, exit_bb, EDGE_TRUE_VALUE);
set_immediate_dominator (CDI_DOMINATORS, exit_bb, dom_bb);
return new_e;
}
bool
slpeel_can_duplicate_loop_p (struct loop *loop, edge e)
{
edge exit_e = loop->single_exit;
edge entry_e = loop_preheader_edge (loop);
tree orig_cond = get_loop_exit_condition (loop);
block_stmt_iterator loop_exit_bsi = bsi_last (exit_e->src);
if (need_ssa_update_p ())
return false;
if (loop->inner
|| !loop->outer
|| loop->num_nodes != 2
|| !empty_block_p (loop->latch)
|| !loop->single_exit
|| (!orig_cond || orig_cond != bsi_stmt (loop_exit_bsi))
|| (e != exit_e && e != entry_e))
return false;
return true;
}
#ifdef ENABLE_CHECKING
void
slpeel_verify_cfg_after_peeling (struct loop *first_loop,
struct loop *second_loop)
{
basic_block loop1_exit_bb = first_loop->single_exit->dest;
basic_block loop2_entry_bb = loop_preheader_edge (second_loop)->src;
basic_block loop1_entry_bb = loop_preheader_edge (first_loop)->src;
gcc_assert (EDGE_COUNT (loop1_exit_bb->succs) == 2);
gcc_assert (EDGE_COUNT (loop2_entry_bb->preds) == 2
&& ((EDGE_PRED (loop2_entry_bb, 0)->src == loop1_exit_bb
&& EDGE_PRED (loop2_entry_bb, 1)->src == loop1_entry_bb)
|| (EDGE_PRED (loop2_entry_bb, 1)->src == loop1_exit_bb
&& EDGE_PRED (loop2_entry_bb, 0)->src == loop1_entry_bb)));
}
#endif
struct loop*
slpeel_tree_peel_loop_to_edge (struct loop *loop, struct loops *loops,
edge e, tree first_niters,
tree niters, bool update_first_loop_count)
{
struct loop *new_loop = NULL, *first_loop, *second_loop;
edge skip_e;
tree pre_condition;
bitmap definitions;
basic_block bb_before_second_loop, bb_after_second_loop;
basic_block bb_before_first_loop;
basic_block bb_between_loops;
basic_block new_exit_bb;
edge exit_e = loop->single_exit;
LOC loop_loc;
if (!slpeel_can_duplicate_loop_p (loop, e))
return NULL;
tree_register_cfg_hooks ();
if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, loops, e)))
{
loop_loc = find_loop_location (loop);
if (dump_file && (dump_flags & TDF_DETAILS))
{
if (loop_loc != UNKNOWN_LOC)
fprintf (dump_file, "\n%s:%d: note: ",
LOC_FILE (loop_loc), LOC_LINE (loop_loc));
fprintf (dump_file, "tree_duplicate_loop_to_edge_cfg failed.\n");
}
return NULL;
}
if (e == exit_e)
{
first_loop = loop;
second_loop = new_loop;
}
else
{
first_loop = new_loop;
second_loop = loop;
}
definitions = ssa_names_to_replace ();
slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
rename_variables_in_loop (new_loop);
bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
add_bb_to_loop (bb_before_first_loop, first_loop->outer);
bb_before_second_loop = split_edge (first_loop->single_exit);
add_bb_to_loop (bb_before_second_loop, first_loop->outer);
pre_condition =
fold_build2 (LE_EXPR, boolean_type_node, first_niters,
build_int_cst (TREE_TYPE (first_niters), 0));
skip_e = slpeel_add_loop_guard (bb_before_first_loop, pre_condition,
bb_before_second_loop, bb_before_first_loop);
slpeel_update_phi_nodes_for_guard1 (skip_e, first_loop,
first_loop == new_loop,
&new_exit_bb, &definitions);
bb_between_loops = new_exit_bb;
bb_after_second_loop = split_edge (second_loop->single_exit);
add_bb_to_loop (bb_after_second_loop, second_loop->outer);
pre_condition =
fold_build2 (EQ_EXPR, boolean_type_node, first_niters, niters);
skip_e = slpeel_add_loop_guard (bb_between_loops, pre_condition,
bb_after_second_loop, bb_before_first_loop);
slpeel_update_phi_nodes_for_guard2 (skip_e, second_loop,
second_loop == new_loop, &new_exit_bb);
if (update_first_loop_count)
slpeel_make_loop_iterate_ntimes (first_loop, first_niters);
BITMAP_FREE (definitions);
delete_update_ssa ();
return new_loop;
}
LOC
find_loop_location (struct loop *loop)
{
tree node = NULL_TREE;
basic_block bb;
block_stmt_iterator si;
if (!loop)
return UNKNOWN_LOC;
node = get_loop_exit_condition (loop);
if (node && EXPR_P (node) && EXPR_HAS_LOCATION (node)
&& EXPR_FILENAME (node) && EXPR_LINENO (node))
return EXPR_LOC (node);
if (!loop->header)
return UNKNOWN_LOC;
bb = loop->header;
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
node = bsi_stmt (si);
if (node && EXPR_P (node) && EXPR_HAS_LOCATION (node))
return EXPR_LOC (node);
}
return UNKNOWN_LOC;
}
void
vect_set_verbosity_level (const char *val)
{
unsigned int vl;
vl = atoi (val);
if (vl < MAX_VERBOSITY_LEVEL)
vect_verbosity_level = vl;
else
vect_verbosity_level = MAX_VERBOSITY_LEVEL - 1;
}
static void
vect_set_dump_settings (void)
{
vect_dump = dump_file;
if (vect_verbosity_level != MAX_VERBOSITY_LEVEL)
{
if (!dump_file)
vect_dump = stderr;
return;
}
if (dump_file && (dump_flags & TDF_DETAILS))
vect_verbosity_level = REPORT_DETAILS;
else if (dump_file && (dump_flags & TDF_STATS))
vect_verbosity_level = REPORT_UNVECTORIZED_LOOPS;
else
vect_verbosity_level = REPORT_NONE;
gcc_assert (dump_file || vect_verbosity_level == REPORT_NONE);
}
bool
vect_print_dump_info (enum verbosity_levels vl)
{
if (vl > vect_verbosity_level)
return false;
if (!current_function_decl || !vect_dump)
return false;
if (vect_loop_location == UNKNOWN_LOC)
fprintf (vect_dump, "\n%s:%d: note: ",
DECL_SOURCE_FILE (current_function_decl),
DECL_SOURCE_LINE (current_function_decl));
else
fprintf (vect_dump, "\n%s:%d: note: ",
LOC_FILE (vect_loop_location), LOC_LINE (vect_loop_location));
return true;
}
stmt_vec_info
new_stmt_vec_info (tree stmt, loop_vec_info loop_vinfo)
{
stmt_vec_info res;
res = (stmt_vec_info) xcalloc (1, sizeof (struct _stmt_vec_info));
STMT_VINFO_TYPE (res) = undef_vec_info_type;
STMT_VINFO_STMT (res) = stmt;
STMT_VINFO_LOOP_VINFO (res) = loop_vinfo;
STMT_VINFO_RELEVANT_P (res) = 0;
STMT_VINFO_LIVE_P (res) = 0;
STMT_VINFO_VECTYPE (res) = NULL;
STMT_VINFO_VEC_STMT (res) = NULL;
STMT_VINFO_IN_PATTERN_P (res) = false;
STMT_VINFO_RELATED_STMT (res) = NULL;
STMT_VINFO_DATA_REF (res) = NULL;
if (TREE_CODE (stmt) == PHI_NODE)
STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type;
else
STMT_VINFO_DEF_TYPE (res) = vect_loop_def;
STMT_VINFO_SAME_ALIGN_REFS (res) = VEC_alloc (dr_p, heap, 5);
return res;
}
loop_vec_info
new_loop_vec_info (struct loop *loop)
{
loop_vec_info res;
basic_block *bbs;
block_stmt_iterator si;
unsigned int i;
res = (loop_vec_info) xcalloc (1, sizeof (struct _loop_vec_info));
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
basic_block bb = bbs[i];
tree phi;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
stmt_ann_t ann = get_stmt_ann (phi);
set_stmt_info (ann, new_stmt_vec_info (phi, res));
}
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
tree stmt = bsi_stmt (si);
stmt_ann_t ann;
ann = stmt_ann (stmt);
set_stmt_info (ann, new_stmt_vec_info (stmt, res));
}
}
LOOP_VINFO_LOOP (res) = loop;
LOOP_VINFO_BBS (res) = bbs;
LOOP_VINFO_EXIT_COND (res) = NULL;
LOOP_VINFO_NITERS (res) = NULL;
LOOP_VINFO_VECTORIZABLE_P (res) = 0;
LOOP_PEELING_FOR_ALIGNMENT (res) = 0;
LOOP_VINFO_VECT_FACTOR (res) = 0;
LOOP_VINFO_DATAREFS (res) = VEC_alloc (data_reference_p, heap, 10);
LOOP_VINFO_DDRS (res) = VEC_alloc (ddr_p, heap, 10 * 10);
LOOP_VINFO_UNALIGNED_DR (res) = NULL;
LOOP_VINFO_MAY_MISALIGN_STMTS (res)
= VEC_alloc (tree, heap, PARAM_VALUE (PARAM_VECT_MAX_VERSION_CHECKS));
return res;
}
void
destroy_loop_vec_info (loop_vec_info loop_vinfo)
{
struct loop *loop;
basic_block *bbs;
int nbbs;
block_stmt_iterator si;
int j;
if (!loop_vinfo)
return;
loop = LOOP_VINFO_LOOP (loop_vinfo);
bbs = LOOP_VINFO_BBS (loop_vinfo);
nbbs = loop->num_nodes;
for (j = 0; j < nbbs; j++)
{
basic_block bb = bbs[j];
tree phi;
stmt_vec_info stmt_info;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
stmt_ann_t ann = stmt_ann (phi);
stmt_info = vinfo_for_stmt (phi);
free (stmt_info);
set_stmt_info (ann, NULL);
}
for (si = bsi_start (bb); !bsi_end_p (si); )
{
tree stmt = bsi_stmt (si);
stmt_ann_t ann = stmt_ann (stmt);
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
if (stmt_info)
{
bool remove_stmt_p = false;
tree orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
if (orig_stmt)
{
stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt);
if (orig_stmt_info
&& STMT_VINFO_IN_PATTERN_P (orig_stmt_info))
remove_stmt_p = true;
}
VEC_free (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmt_info));
free (stmt_info);
set_stmt_info (ann, NULL);
if (remove_stmt_p)
bsi_remove (&si, true);
}
bsi_next (&si);
}
}
free (LOOP_VINFO_BBS (loop_vinfo));
free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo));
free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
VEC_free (tree, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
free (loop_vinfo);
}
bool
vect_can_force_dr_alignment_p (tree decl, unsigned int alignment)
{
if (TREE_CODE (decl) != VAR_DECL)
return false;
if (DECL_EXTERNAL (decl))
return false;
if (TREE_ASM_WRITTEN (decl))
return false;
if (TREE_STATIC (decl))
return (alignment <= MAX_OFILE_ALIGNMENT);
else
return (alignment <= PREFERRED_STACK_BOUNDARY);
}
tree
get_vectype_for_scalar_type (tree scalar_type)
{
enum machine_mode inner_mode = TYPE_MODE (scalar_type);
int nbytes = GET_MODE_SIZE (inner_mode);
int nunits;
tree vectype;
if (nbytes == 0 || nbytes >= UNITS_PER_SIMD_WORD)
return NULL_TREE;
nunits = UNITS_PER_SIMD_WORD / nbytes;
vectype = build_vector_type (scalar_type, nunits);
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "get vectype with %d units of type ", nunits);
print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
}
if (!vectype)
return NULL_TREE;
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "vectype: ");
print_generic_expr (vect_dump, vectype, TDF_SLIM);
}
if (!VECTOR_MODE_P (TYPE_MODE (vectype))
&& !INTEGRAL_MODE_P (TYPE_MODE (vectype)))
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "mode not supported by target.");
return NULL_TREE;
}
return vectype;
}
enum dr_alignment_support
vect_supportable_dr_alignment (struct data_reference *dr)
{
tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr)));
enum machine_mode mode = (int) TYPE_MODE (vectype);
if (aligned_access_p (dr))
return dr_aligned;
if (DR_IS_READ (dr))
{
if (vec_realign_load_optab->handlers[mode].insn_code != CODE_FOR_nothing
&& (!targetm.vectorize.builtin_mask_for_load
|| targetm.vectorize.builtin_mask_for_load ()))
return dr_unaligned_software_pipeline;
if (movmisalign_optab->handlers[mode].insn_code != CODE_FOR_nothing)
return dr_unaligned_supported;
}
return dr_unaligned_unsupported;
}
bool
vect_is_simple_use (tree operand, loop_vec_info loop_vinfo, tree *def_stmt,
tree *def, enum vect_def_type *dt)
{
basic_block bb;
stmt_vec_info stmt_vinfo;
struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
*def_stmt = NULL_TREE;
*def = NULL_TREE;
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "vect_is_simple_use: operand ");
print_generic_expr (vect_dump, operand, TDF_SLIM);
}
if (TREE_CODE (operand) == INTEGER_CST || TREE_CODE (operand) == REAL_CST)
{
*dt = vect_constant_def;
return true;
}
if (TREE_CODE (operand) != SSA_NAME)
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "not ssa-name.");
return false;
}
*def_stmt = SSA_NAME_DEF_STMT (operand);
if (*def_stmt == NULL_TREE )
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "no def_stmt.");
return false;
}
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "def_stmt: ");
print_generic_expr (vect_dump, *def_stmt, TDF_SLIM);
}
if (IS_EMPTY_STMT (*def_stmt))
{
tree arg = TREE_OPERAND (*def_stmt, 0);
if (TREE_CODE (arg) == INTEGER_CST || TREE_CODE (arg) == REAL_CST)
{
*def = operand;
*dt = vect_invariant_def;
return true;
}
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "Unexpected empty stmt.");
return false;
}
bb = bb_for_stmt (*def_stmt);
if (!flow_bb_inside_loop_p (loop, bb))
*dt = vect_invariant_def;
else
{
stmt_vinfo = vinfo_for_stmt (*def_stmt);
*dt = STMT_VINFO_DEF_TYPE (stmt_vinfo);
}
if (*dt == vect_unknown_def_type)
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "Unsupported pattern.");
return false;
}
if (*dt == vect_reduction_def && TREE_CODE (*def_stmt) != PHI_NODE)
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "reduction used in loop.");
return false;
}
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "type of def: %d.",*dt);
switch (TREE_CODE (*def_stmt))
{
case PHI_NODE:
*def = PHI_RESULT (*def_stmt);
gcc_assert (*dt == vect_induction_def || *dt == vect_reduction_def
|| *dt == vect_invariant_def);
break;
case MODIFY_EXPR:
*def = TREE_OPERAND (*def_stmt, 0);
gcc_assert (*dt == vect_loop_def || *dt == vect_invariant_def);
break;
default:
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "unsupported defining stmt: ");
return false;
}
if (*dt == vect_induction_def)
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "induction not supported.");
return false;
}
return true;
}
bool
reduction_code_for_scalar_code (enum tree_code code,
enum tree_code *reduc_code)
{
switch (code)
{
case MAX_EXPR:
*reduc_code = REDUC_MAX_EXPR;
return true;
case MIN_EXPR:
*reduc_code = REDUC_MIN_EXPR;
return true;
case PLUS_EXPR:
*reduc_code = REDUC_PLUS_EXPR;
return true;
default:
return false;
}
}
tree
vect_is_simple_reduction (struct loop *loop, tree phi)
{
edge latch_e = loop_latch_edge (loop);
tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
tree def_stmt, def1, def2;
enum tree_code code;
int op_type;
tree operation, op1, op2;
tree type;
if (TREE_CODE (loop_arg) != SSA_NAME)
{
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "reduction: not ssa_name: ");
print_generic_expr (vect_dump, loop_arg, TDF_SLIM);
}
return NULL_TREE;
}
def_stmt = SSA_NAME_DEF_STMT (loop_arg);
if (!def_stmt)
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "reduction: no def_stmt.");
return NULL_TREE;
}
if (TREE_CODE (def_stmt) != MODIFY_EXPR)
{
if (vect_print_dump_info (REPORT_DETAILS))
{
print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
}
return NULL_TREE;
}
operation = TREE_OPERAND (def_stmt, 1);
code = TREE_CODE (operation);
if (!commutative_tree_code (code) || !associative_tree_code (code))
{
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "reduction: not commutative/associative: ");
print_generic_expr (vect_dump, operation, TDF_SLIM);
}
return NULL_TREE;
}
op_type = TREE_CODE_LENGTH (code);
if (op_type != binary_op)
{
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "reduction: not binary operation: ");
print_generic_expr (vect_dump, operation, TDF_SLIM);
}
return NULL_TREE;
}
op1 = TREE_OPERAND (operation, 0);
op2 = TREE_OPERAND (operation, 1);
if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
{
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "reduction: uses not ssa_names: ");
print_generic_expr (vect_dump, operation, TDF_SLIM);
}
return NULL_TREE;
}
type = TREE_TYPE (operation);
if (TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op1))
|| TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op2)))
{
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "reduction: multiple types: operation type: ");
print_generic_expr (vect_dump, type, TDF_SLIM);
fprintf (vect_dump, ", operands types: ");
print_generic_expr (vect_dump, TREE_TYPE (op1), TDF_SLIM);
fprintf (vect_dump, ",");
print_generic_expr (vect_dump, TREE_TYPE (op2), TDF_SLIM);
}
return NULL_TREE;
}
if (SCALAR_FLOAT_TYPE_P (type) && !flag_unsafe_math_optimizations)
{
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "reduction: unsafe fp math optimization: ");
print_generic_expr (vect_dump, operation, TDF_SLIM);
}
return NULL_TREE;
}
else if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_TRAPS (type))
{
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "reduction: unsafe int math optimization: ");
print_generic_expr (vect_dump, operation, TDF_SLIM);
}
return NULL_TREE;
}
def1 = SSA_NAME_DEF_STMT (op1);
def2 = SSA_NAME_DEF_STMT (op2);
if (!def1 || !def2)
{
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "reduction: no defs for operands: ");
print_generic_expr (vect_dump, operation, TDF_SLIM);
}
return NULL_TREE;
}
if (TREE_CODE (def1) == MODIFY_EXPR
&& flow_bb_inside_loop_p (loop, bb_for_stmt (def1))
&& def2 == phi)
{
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "detected reduction:");
print_generic_expr (vect_dump, operation, TDF_SLIM);
}
return def_stmt;
}
else if (TREE_CODE (def2) == MODIFY_EXPR
&& flow_bb_inside_loop_p (loop, bb_for_stmt (def2))
&& def1 == phi)
{
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "detected reduction: need to swap operands:");
print_generic_expr (vect_dump, operation, TDF_SLIM);
}
swap_tree_operands (def_stmt, &TREE_OPERAND (operation, 0),
&TREE_OPERAND (operation, 1));
return def_stmt;
}
else
{
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "reduction: unknown pattern.");
print_generic_expr (vect_dump, operation, TDF_SLIM);
}
return NULL_TREE;
}
}
bool
vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init,
tree * step)
{
tree init_expr;
tree step_expr;
tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb);
if (evolution_part == NULL_TREE)
return false;
if (tree_is_chrec (evolution_part))
return false;
step_expr = evolution_part;
init_expr = unshare_expr (initial_condition_in_loop_num (access_fn,
loop_nb));
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "step: ");
print_generic_expr (vect_dump, step_expr, TDF_SLIM);
fprintf (vect_dump, ", init: ");
print_generic_expr (vect_dump, init_expr, TDF_SLIM);
}
*init = init_expr;
*step = step_expr;
if (TREE_CODE (step_expr) != INTEGER_CST)
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "step unknown.");
return false;
}
return true;
}
void
vectorize_loops (struct loops *loops)
{
unsigned int i;
unsigned int num_vectorized_loops = 0;
vect_set_dump_settings ();
vect_vnames_to_rename = BITMAP_ALLOC (NULL);
vect_loops_num = loops->num;
for (i = 1; i < vect_loops_num; i++)
{
loop_vec_info loop_vinfo;
struct loop *loop = loops->parray[i];
if (!loop)
continue;
vect_loop_location = find_loop_location (loop);
loop_vinfo = vect_analyze_loop (loop);
loop->aux = loop_vinfo;
if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
continue;
vect_transform_loop (loop_vinfo, loops);
DECL_STRUCT_FUNCTION (current_function_decl)->uses_vector = 1;
if (flag_opt_diary && debug_hooks->opt_diary_entry)
(*debug_hooks->opt_diary_entry) (OD_msg_loop_vectorized,
*vect_loop_location);
num_vectorized_loops++;
}
vect_loop_location = UNKNOWN_LOC;
if (vect_print_dump_info (REPORT_VECTORIZED_LOOPS))
fprintf (vect_dump, "vectorized %u loops in function.\n",
num_vectorized_loops);
BITMAP_FREE (vect_vnames_to_rename);
for (i = 1; i < vect_loops_num; i++)
{
struct loop *loop = loops->parray[i];
loop_vec_info loop_vinfo;
if (!loop)
continue;
loop_vinfo = loop->aux;
destroy_loop_vec_info (loop_vinfo);
loop->aux = NULL;
}
}