/* Swing Modulo Scheduling implementation.
- Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
- Free Software Foundation, Inc.
+ Copyright (C) 2004-2015 Free Software Foundation, Inc.
Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
This file is part of GCC.
#include "hard-reg-set.h"
#include "regs.h"
#include "function.h"
+#include "profile.h"
#include "flags.h"
#include "insn-config.h"
#include "insn-attr.h"
#include "except.h"
#include "recog.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfgrtl.h"
+#include "predict.h"
+#include "basic-block.h"
#include "sched-int.h"
#include "target.h"
#include "cfgloop.h"
+#include "alias.h"
+#include "symtab.h"
+#include "tree.h"
+#include "insn-codes.h"
+#include "optabs.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "calls.h"
+#include "emit-rtl.h"
+#include "varasm.h"
+#include "stmt.h"
#include "expr.h"
#include "params.h"
#include "gcov-io.h"
+#include "sbitmap.h"
+#include "df.h"
#include "ddg.h"
#include "tree-pass.h"
#include "dbgcnt.h"
-#include "df.h"
+#include "loop-unroll.h"
#ifdef INSN_SCHEDULING
/* An instruction that sets NEW_REG to the correct value. The first
move associated with DEF will have an rhs of OLD_REG; later moves
use the result of the previous move. */
- rtx insn;
+ rtx_insn *insn;
};
typedef struct ps_reg_move_info ps_reg_move_info;
-DEF_VEC_O (ps_reg_move_info);
-DEF_VEC_ALLOC_O (ps_reg_move_info, heap);
/* Holds the partial schedule as an array of II rows. Each entry of the
array points to a linked list of PS_INSNs, which represents the
/* All the moves added for this partial schedule. Index X has
a ps_insn id of X + g->num_nodes. */
- VEC (ps_reg_move_info, heap) *reg_moves;
+ vec<ps_reg_move_info> reg_moves;
/* rows_length[i] holds the number of instructions in the row.
It is used only (as an optimization) to back off quickly from
static int sms_order_nodes (ddg_ptr, int, int *, int *);
static void set_node_sched_params (ddg_ptr);
static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int, int *);
-static void permute_partial_schedule (partial_schedule_ptr, rtx);
+static void permute_partial_schedule (partial_schedule_ptr, rtx_insn *);
static void generate_prolog_epilog (partial_schedule_ptr, struct loop *,
rtx, rtx);
static int calculate_stage_count (partial_schedule_ptr, int);
#define NODE_ASAP(node) ((node)->aux.count)
-#define SCHED_PARAMS(x) (&VEC_index (node_sched_params, node_sched_param_vec, x))
+#define SCHED_PARAMS(x) (&node_sched_param_vec[x])
#define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
#define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
#define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
} *node_sched_params_ptr;
typedef struct node_sched_params node_sched_params;
-DEF_VEC_O (node_sched_params);
-DEF_VEC_ALLOC_O (node_sched_params, heap);
\f
/* The following three functions are copied from the current scheduler
code in order to use sched_analyze() for computing the dependencies.
They are used when initializing the sched_info structure. */
static const char *
-sms_print_insn (const_rtx insn, int aligned ATTRIBUTE_UNUSED)
+sms_print_insn (const rtx_insn *insn, int aligned ATTRIBUTE_UNUSED)
{
static char tmp[80];
ps_reg_move (partial_schedule_ptr ps, int id)
{
gcc_checking_assert (id >= ps->g->num_nodes);
- return &VEC_index (ps_reg_move_info, ps->reg_moves, id - ps->g->num_nodes);
+ return &ps->reg_moves[id - ps->g->num_nodes];
}
/* Return the rtl instruction that is being scheduled by partial schedule
instruction ID, which belongs to schedule PS. */
-static rtx
+static rtx_insn *
ps_rtl_insn (partial_schedule_ptr ps, int id)
{
if (id < ps->g->num_nodes)
in the loop that was associated with ps_rtl_insn (PS, ID).
If the instruction had some notes before it, this is the first
of those notes. */
-static rtx
+static rtx_insn *
ps_first_note (partial_schedule_ptr ps, int id)
{
gcc_assert (id < ps->g->num_nodes);
more than one occurrence in the loop besides the control part or the
do-loop pattern is not of the form we expect. */
static rtx
-doloop_register_get (rtx head ATTRIBUTE_UNUSED, rtx tail ATTRIBUTE_UNUSED)
+doloop_register_get (rtx_insn *head ATTRIBUTE_UNUSED, rtx_insn *tail ATTRIBUTE_UNUSED)
{
#ifdef HAVE_doloop_end
- rtx reg, condition, insn, first_insn_not_to_check;
+ rtx reg, condition;
+ rtx_insn *insn, *first_insn_not_to_check;
if (!JUMP_P (tail))
return NULL_RTX;
/* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
that the number of iterations is a compile-time constant. If so,
- return the rtx that sets COUNT_REG to a constant, and set COUNT to
+ return the rtx_insn that sets COUNT_REG to a constant, and set COUNT to
this constant. Otherwise return 0. */
-static rtx
+static rtx_insn *
const_iteration_count (rtx count_reg, basic_block pre_header,
- HOST_WIDEST_INT * count)
+ int64_t * count)
{
- rtx insn;
- rtx head, tail;
+ rtx_insn *insn;
+ rtx_insn *head, *tail;
if (! pre_header)
- return NULL_RTX;
+ return NULL;
get_ebb_head_tail (pre_header, pre_header, &head, &tail);
return insn;
}
- return NULL_RTX;
+ return NULL;
}
- return NULL_RTX;
+ return NULL;
}
/* A very simple resource-based lower bound on the initiation interval.
/* A vector that contains the sched data for each ps_insn. */
-static VEC (node_sched_params, heap) *node_sched_param_vec;
+static vec<node_sched_params> node_sched_param_vec;
/* Allocate sched_params for each node and initialize it. */
static void
set_node_sched_params (ddg_ptr g)
{
- VEC_truncate (node_sched_params, node_sched_param_vec, 0);
- VEC_safe_grow_cleared (node_sched_params, heap,
- node_sched_param_vec, g->num_nodes);
+ node_sched_param_vec.truncate (0);
+ node_sched_param_vec.safe_grow_cleared (g->num_nodes);
}
/* Make sure that node_sched_param_vec has an entry for every move in PS. */
static void
extend_node_sched_params (partial_schedule_ptr ps)
{
- VEC_safe_grow_cleared (node_sched_params, heap, node_sched_param_vec,
- ps->g->num_nodes + VEC_length (ps_reg_move_info,
- ps->reg_moves));
+ node_sched_param_vec.safe_grow_cleared (ps->g->num_nodes
+ + ps->reg_moves.length ());
}
/* Update the sched_params (time, row and stage) for node U using the II,
int start, end, c, ii;
sbitmap_iterator sbi;
ps_reg_move_info *move;
- rtx this_insn;
+ rtx_insn *this_insn;
ps_insn_ptr psi;
move = ps_reg_move (ps, i_reg_move);
/* Handle the dependencies between the move and previously-scheduled
successors. */
- EXECUTE_IF_SET_IN_SBITMAP (move->uses, 0, u, sbi)
+ EXECUTE_IF_SET_IN_BITMAP (move->uses, 0, u, sbi)
{
this_insn = ps_rtl_insn (ps, u);
this_latency = insn_latency (move->insn, this_insn);
continue;
/* Create NREG_MOVES register moves. */
- first_move = VEC_length (ps_reg_move_info, ps->reg_moves);
- VEC_safe_grow_cleared (ps_reg_move_info, heap, ps->reg_moves,
- first_move + nreg_moves);
+ first_move = ps->reg_moves.length ();
+ ps->reg_moves.safe_grow_cleared (first_move + nreg_moves);
extend_node_sched_params (ps);
/* Record the moves associated with this node. */
distance1_uses = distances[1] ? sbitmap_alloc (g->num_nodes) : NULL;
+ if (distance1_uses)
+ bitmap_clear (distance1_uses);
+
/* Every use of the register defined by node may require a different
copy of this register, depending on the time the use is scheduled.
Record which uses require which move results. */
ps_reg_move_info *move;
int i;
- FOR_EACH_VEC_ELT (ps_reg_move_info, ps->reg_moves, i, move)
+ FOR_EACH_VEC_ELT (ps->reg_moves, i, move)
{
unsigned int i_use;
sbitmap_iterator sbi;
- EXECUTE_IF_SET_IN_SBITMAP (move->uses, 0, i_use, sbi)
+ EXECUTE_IF_SET_IN_BITMAP (move->uses, 0, i_use, sbi)
{
replace_rtx (ps->g->nodes[i_use].insn, move->old_reg, move->new_reg);
df_insn_rescan (ps->g->nodes[i_use].insn);
if (dump_file)
{
/* Print the scheduling times after the rotation. */
- rtx insn = ps_rtl_insn (ps, u);
+ rtx_insn *insn = ps_rtl_insn (ps, u);
fprintf (dump_file, "crr_insn->node=%d (insn id %d), "
"crr_insn->cycle=%d, min_cycle=%d", u,
row ii-1, and position them right before LAST. This schedules
the insns of the loop kernel. */
static void
-permute_partial_schedule (partial_schedule_ptr ps, rtx last)
+permute_partial_schedule (partial_schedule_ptr ps, rtx_insn *last)
{
int ii = ps->ii;
int row;
for (row = 0; row < ii ; row++)
for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
{
- rtx insn = ps_rtl_insn (ps, ps_ij->id);
+ rtx_insn *insn = ps_rtl_insn (ps, ps_ij->id);
if (PREV_INSN (last) != insn)
{
{
int u = ps_ij->id;
int first_u, last_u;
- rtx u_insn;
+ rtx_insn *u_insn;
/* Do not duplicate any insn which refers to count_reg as it
belongs to the control part.
generate_prolog_epilog function. */
rtx sub_reg = NULL_RTX;
- sub_reg = expand_simple_binop (GET_MODE (count_reg), MINUS,
- count_reg, GEN_INT (last_stage),
+ sub_reg = expand_simple_binop (GET_MODE (count_reg), MINUS, count_reg,
+ gen_int_mode (last_stage,
+ GET_MODE (count_reg)),
count_reg, 1, OPTAB_DIRECT);
gcc_assert (REG_P (sub_reg));
if (REGNO (sub_reg) != REGNO (count_reg))
for (i = 0; i < loop->num_nodes ; i++)
{
- rtx head, tail;
+ rtx_insn *head, *tail;
bool empty_bb = true;
if (bbs[i] == loop->header)
/* Dump file:line from INSN's location info to dump_file. */
static void
-dump_insn_location (rtx insn)
+dump_insn_location (rtx_insn *insn)
{
- if (dump_file && INSN_LOCATION (insn))
+ if (dump_file && INSN_HAS_LOCATION (insn))
{
- const char *file = insn_file (insn);
- if (file)
- fprintf (dump_file, " %s:%i", file, insn_line (insn));
+ expanded_location xloc = insn_location (insn);
+ fprintf (dump_file, " %s:%i", xloc.file, xloc.line);
}
}
{
if (dump_file)
{
- rtx insn = BB_END (loop->header);
+ rtx_insn *insn = BB_END (loop->header);
fprintf (dump_file, "SMS loop many exits");
dump_insn_location (insn);
{
if (dump_file)
{
- rtx insn = BB_END (loop->header);
+ rtx_insn *insn = BB_END (loop->header);
fprintf (dump_file, "SMS loop many BBs.");
dump_insn_location (insn);
/* Avoid annoying special cases of edges going to exit
block. */
- FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR->preds)
+ FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
if ((e->flags & EDGE_FALLTHRU) && (EDGE_COUNT (e->src->succs) > 1))
split_edge (e);
static void
sms_schedule (void)
{
- rtx insn;
+ rtx_insn *insn;
ddg_ptr *g_arr, g;
int * node_order;
int maxii, max_asap;
- loop_iterator li;
partial_schedule_ptr ps;
basic_block bb = NULL;
struct loop *loop;
loop_optimizer_init (LOOPS_HAVE_PREHEADERS
| LOOPS_HAVE_RECORDED_EXITS);
- if (number_of_loops () <= 1)
+ if (number_of_loops (cfun) <= 1)
{
loop_optimizer_finalize ();
return; /* There are no loops to schedule. */
/* Allocate memory to hold the DDG array one entry for each loop.
We use loop->num as index into this array. */
- g_arr = XCNEWVEC (ddg_ptr, number_of_loops ());
+ g_arr = XCNEWVEC (ddg_ptr, number_of_loops (cfun));
if (dump_file)
{
/* Build DDGs for all the relevant loops and hold them in G_ARR
indexed by the loop index. */
- FOR_EACH_LOOP (li, loop, 0)
+ FOR_EACH_LOOP (loop, 0)
{
- rtx head, tail;
+ rtx_insn *head, *tail;
rtx count_reg;
/* For debugging. */
if (dump_file)
fprintf (dump_file, "SMS reached max limit... \n");
- FOR_EACH_LOOP_BREAK (li);
+ break;
}
if (dump_file)
{
- rtx insn = BB_END (loop->header);
+ rtx_insn *insn = BB_END (loop->header);
fprintf (dump_file, "SMS loop num: %d", loop->num);
dump_insn_location (insn);
if (profile_info && flag_branch_probabilities)
{
fprintf (dump_file, "SMS loop-count ");
- fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
- (HOST_WIDEST_INT) bb->count);
+ fprintf (dump_file, "%" PRId64,
+ (int64_t) bb->count);
fprintf (dump_file, "\n");
fprintf (dump_file, "SMS trip-count ");
- fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
- (HOST_WIDEST_INT) trip_count);
+ fprintf (dump_file, "%" PRId64,
+ (int64_t) trip_count);
fprintf (dump_file, "\n");
fprintf (dump_file, "SMS profile-sum-max ");
- fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
- (HOST_WIDEST_INT) profile_info->sum_max);
+ fprintf (dump_file, "%" PRId64,
+ (int64_t) profile_info->sum_max);
fprintf (dump_file, "\n");
}
}
}
/* We don't want to perform SMS on new loops - created by versioning. */
- FOR_EACH_LOOP (li, loop, 0)
+ FOR_EACH_LOOP (loop, 0)
{
- rtx head, tail;
- rtx count_reg, count_init;
+ rtx_insn *head, *tail;
+ rtx count_reg;
+ rtx_insn *count_init;
int mii, rec_mii, stage_count, min_cycle;
- HOST_WIDEST_INT loop_count = 0;
+ int64_t loop_count = 0;
bool opt_sc_p;
if (! (g = g_arr[loop->num]))
if (dump_file)
{
- rtx insn = BB_END (loop->header);
+ rtx_insn *insn = BB_END (loop->header);
fprintf (dump_file, "SMS loop num: %d", loop->num);
dump_insn_location (insn);
if (profile_info && flag_branch_probabilities)
{
fprintf (dump_file, "SMS loop-count ");
- fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
- (HOST_WIDEST_INT) bb->count);
+ fprintf (dump_file, "%" PRId64,
+ (int64_t) bb->count);
fprintf (dump_file, "\n");
fprintf (dump_file, "SMS profile-sum-max ");
- fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
- (HOST_WIDEST_INT) profile_info->sum_max);
+ fprintf (dump_file, "%" PRId64,
+ (int64_t) profile_info->sum_max);
fprintf (dump_file, "\n");
}
fprintf (dump_file, "SMS doloop\n");
/* In case of th loop have doloop register it gets special
handling. */
- count_init = NULL_RTX;
+ count_init = NULL;
if ((count_reg = doloop_register_get (head, tail)))
{
basic_block pre_header;
if (dump_file && count_init)
{
fprintf (dump_file, "SMS const-doloop ");
- fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
+ fprintf (dump_file, "%" PRId64,
loop_count);
fprintf (dump_file, "\n");
}
fprintf (dump_file, "SMS failed... \n");
fprintf (dump_file, "SMS sched-failed (stage-count=%d,"
" loop-count=", stage_count);
- fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, loop_count);
+ fprintf (dump_file, "%" PRId64, loop_count);
fprintf (dump_file, ", trip-count=");
- fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, trip_count);
+ fprintf (dump_file, "%" PRId64, trip_count);
fprintf (dump_file, ")\n");
}
break;
/* case the BCT count is not known , Do loop-versioning */
if (count_reg && ! count_init)
{
- rtx comp_rtx = gen_rtx_fmt_ee (GT, VOIDmode, count_reg,
- GEN_INT(stage_count));
+ rtx comp_rtx = gen_rtx_GT (VOIDmode, count_reg,
+ gen_int_mode (stage_count,
+ GET_MODE (count_reg)));
unsigned prob = (PROB_SMS_ENOUGH_ITERATIONS
* REG_BR_PROB_BASE) / 100;
}
free_partial_schedule (ps);
- VEC_free (node_sched_params, heap, node_sched_param_vec);
+ node_sched_param_vec.release ();
free (node_order);
free_ddg (g);
}
node close to its successors. */
if (pss_not_empty && count_succs >= count_preds)
{
- int tmp = end;
- end = start;
- start = tmp;
+ std::swap (start, end);
step = -1;
}
{
int u = nodes_order[i];
ddg_node_ptr u_node = &ps->g->nodes[u];
- rtx insn = u_node->insn;
+ rtx_insn *insn = u_node->insn;
if (!NONDEBUG_INSN_P (insn))
{
int result = -1;
sbitmap_iterator sbi;
- EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
+ EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi)
{
ddg_node_ptr u_node = &g->nodes[u];
int result = -1;
sbitmap_iterator sbi;
- EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
+ EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi)
{
ddg_node_ptr u_node = &g->nodes[u];
int result = -1;
sbitmap_iterator sbi;
- EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
+ EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi)
{
ddg_node_ptr u_node = &g->nodes[u];
partial_schedule_ptr ps = XNEW (struct partial_schedule);
ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
ps->rows_length = (int *) xcalloc (ii, sizeof (int));
- ps->reg_moves = NULL;
+ ps->reg_moves.create (0);
ps->ii = ii;
ps->history = history;
ps->min_cycle = INT_MAX;
if (!ps)
return;
- FOR_EACH_VEC_ELT (ps_reg_move_info, ps->reg_moves, i, move)
+ FOR_EACH_VEC_ELT (ps->reg_moves, i, move)
sbitmap_free (move->uses);
- VEC_free (ps_reg_move_info, heap, ps->reg_moves);
+ ps->reg_moves.release ();
free_ps_insns (ps);
free (ps->rows);
fprintf (dump, "\n[ROW %d ]: ", i);
while (ps_i)
{
- rtx insn = ps_rtl_insn (ps, ps_i->id);
+ rtx_insn *insn = ps_rtl_insn (ps, ps_i->id);
if (JUMP_P (insn))
fprintf (dump, "%d (branch), ", INSN_UID (insn));
crr_insn;
crr_insn = crr_insn->next_in_row)
{
- rtx insn = ps_rtl_insn (ps, crr_insn->id);
+ rtx_insn *insn = ps_rtl_insn (ps, crr_insn->id);
if (!NONDEBUG_INSN_P (insn))
continue;
#endif /* INSN_SCHEDULING */
\f
-static bool
-gate_handle_sms (void)
+/* Run instruction scheduler. */
+/* Perform SMS module scheduling. */
+
+namespace {
+
+const pass_data pass_data_sms =
+{
+ RTL_PASS, /* type */
+ "sms", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_SMS, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_df_finish, /* todo_flags_finish */
+};
+
+class pass_sms : public rtl_opt_pass
+{
+public:
+ pass_sms (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_sms, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *)
{
return (optimize > 0 && flag_modulo_sched);
}
+ virtual unsigned int execute (function *);
-/* Run instruction scheduler. */
-/* Perform SMS module scheduling. */
-static unsigned int
-rest_of_handle_sms (void)
+}; // class pass_sms
+
+unsigned int
+pass_sms::execute (function *fun ATTRIBUTE_UNUSED)
{
#ifdef INSN_SCHEDULING
basic_block bb;
max_regno = max_reg_num ();
/* Finalize layout changes. */
- FOR_EACH_BB (bb)
- if (bb->next_bb != EXIT_BLOCK_PTR)
+ FOR_EACH_BB_FN (bb, fun)
+ if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
bb->aux = bb->next_bb;
free_dominance_info (CDI_DOMINATORS);
cfg_layout_finalize ();
return 0;
}
-struct rtl_opt_pass pass_sms =
-{
- {
- RTL_PASS,
- "sms", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- gate_handle_sms, /* gate */
- rest_of_handle_sms, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_SMS, /* tv_id */
- 0, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_df_finish
- | TODO_verify_flow
- | TODO_verify_rtl_sharing
- | TODO_ggc_collect /* todo_flags_finish */
- }
-};
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_sms (gcc::context *ctxt)
+{
+ return new pass_sms (ctxt);
+}