/* Swing Modulo Scheduling implementation.
- Copyright (C) 2004-2015 Free Software Foundation, Inc.
+ Copyright (C) 2004-2020 Free Software Foundation, Inc.
Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "backend.h"
-#include "cfghooks.h"
-#include "tree.h"
+#include "target.h"
#include "rtl.h"
+#include "tree.h"
+#include "cfghooks.h"
#include "df.h"
-#include "diagnostic-core.h"
-#include "tm_p.h"
+#include "memmodel.h"
+#include "optabs.h"
#include "regs.h"
+#include "emit-rtl.h"
+#include "gcov-io.h"
#include "profile.h"
-#include "flags.h"
-#include "insn-config.h"
#include "insn-attr.h"
-#include "except.h"
-#include "recog.h"
#include "cfgrtl.h"
#include "sched-int.h"
-#include "target.h"
#include "cfgloop.h"
-#include "alias.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 "ddg.h"
#include "tree-pass.h"
#include "dbgcnt.h"
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_insn *);
-static void generate_prolog_epilog (partial_schedule_ptr, struct loop *,
+static void generate_prolog_epilog (partial_schedule_ptr, class loop *,
rtx, rtx);
static int calculate_stage_count (partial_schedule_ptr, int);
static void calculate_must_precede_follow (ddg_node_ptr, int, int,
: prev_nondebug_insn (tail));
for (insn = head; insn != first_insn_not_to_check; insn = NEXT_INSN (insn))
- if (!DEBUG_INSN_P (insn) && reg_mentioned_p (reg, insn))
+ if (NONDEBUG_INSN_P (insn) && reg_mentioned_p (reg, insn))
{
if (dump_file)
{
if (targetm.sched.sms_res_mii)
return targetm.sched.sms_res_mii (g);
- return ((g->num_nodes - g->num_debug) / issue_rate);
+ return g->num_nodes / issue_rate;
}
rtx prev_reg, old_reg;
int first_move;
int distances[2];
- sbitmap must_follow;
sbitmap distance1_uses;
rtx set = single_set (u->insn);
/* Skip instructions that do not set a register. */
- if ((set && !REG_P (SET_DEST (set))))
+ if (set && !REG_P (SET_DEST (set)))
continue;
-
+
/* Compute the number of reg_moves needed for u, by looking at life
ranges started at u (excluding self-loops). */
distances[0] = distances[1] = false;
first_move += ps->g->num_nodes;
/* Generate each move. */
- old_reg = prev_reg = SET_DEST (single_set (u->insn));
+ old_reg = prev_reg = SET_DEST (set);
+ if (HARD_REGISTER_P (old_reg))
+ return false;
+
for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
{
ps_reg_move_info *move = ps_reg_move (ps, first_move + i_reg_move);
}
}
- must_follow = sbitmap_alloc (first_move + nreg_moves);
+ auto_sbitmap must_follow (first_move + nreg_moves);
for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
if (!schedule_reg_move (ps, first_move + i_reg_move,
distance1_uses, must_follow))
break;
- sbitmap_free (must_follow);
if (distance1_uses)
sbitmap_free (distance1_uses);
if (i_reg_move < nreg_moves)
return true;
}
-/* Emit the moves associatied with PS. Apply the substitutions
+/* Emit the moves associated with PS. Apply the substitutions
associated with them. */
static void
apply_reg_moves (partial_schedule_ptr ps)
optimize_sc (partial_schedule_ptr ps, ddg_ptr g)
{
int amount = PS_MIN_CYCLE (ps);
- sbitmap sched_nodes = sbitmap_alloc (g->num_nodes);
int start, end, step;
int ii = ps->ii;
bool ok = false;
if (dump_file)
fprintf (dump_file, "SMS SC already optimized.\n");
- ok = false;
- goto clear;
+ return false;
}
if (dump_file)
}
if (SMODULO (SCHED_TIME (g->closing_branch->cuid), ii) == ii - 1)
- {
- ok = true;
- goto clear;
- }
+ return true;
+ auto_sbitmap sched_nodes (g->num_nodes);
bitmap_ones (sched_nodes);
/* Calculate the new placement of the branch. It should be in row
int branch_cycle = SCHED_TIME (g->closing_branch->cuid);
int row = SMODULO (branch_cycle, ps->ii);
int num_splits = 0;
- sbitmap must_precede, must_follow, tmp_precede, tmp_follow;
- int c;
+ sbitmap tmp_precede, tmp_follow;
+ int min_cycle, c;
if (dump_file)
fprintf (dump_file, "\nTrying to schedule node %d "
gcc_assert (c >= start);
if (c >= end)
{
- ok = false;
if (dump_file)
fprintf (dump_file,
"SMS failed to schedule branch at cycle: %d\n", c);
- goto clear;
+ return false;
}
}
else
if (dump_file)
fprintf (dump_file,
"SMS failed to schedule branch at cycle: %d\n", c);
- ok = false;
- goto clear;
+ return false;
}
}
- must_precede = sbitmap_alloc (g->num_nodes);
- must_follow = sbitmap_alloc (g->num_nodes);
+ auto_sbitmap must_precede (g->num_nodes);
+ auto_sbitmap must_follow (g->num_nodes);
/* Try to schedule the branch is it's new cycle. */
calculate_must_precede_follow (g->closing_branch, start, end,
if (next_ps_i->id == g->closing_branch->cuid)
break;
+ min_cycle = PS_MIN_CYCLE (ps) - SMODULO (PS_MIN_CYCLE (ps), ps->ii);
remove_node_from_ps (ps, next_ps_i);
success =
try_scheduling_node_in_cycle (ps, g->closing_branch->cuid, c,
ok = true;
}
- free (must_precede);
- free (must_follow);
+ /* This might have been added to a new first stage. */
+ if (PS_MIN_CYCLE (ps) < min_cycle)
+ reset_sched_times (ps, 0);
}
-clear:
- free (sched_nodes);
return ok;
}
/* Generate the instructions (including reg_moves) for prolog & epilog. */
static void
-generate_prolog_epilog (partial_schedule_ptr ps, struct loop *loop,
+generate_prolog_epilog (partial_schedule_ptr ps, class loop *loop,
rtx count_reg, rtx count_init)
{
int i;
/* Mark LOOP as software pipelined so the later
scheduling passes don't touch it. */
static void
-mark_loop_unsched (struct loop *loop)
+mark_loop_unsched (class loop *loop)
{
unsigned i;
basic_block *bbs = get_loop_body (loop);
/* Return true if all the BBs of the loop are empty except the
loop header. */
static bool
-loop_single_full_bb_p (struct loop *loop)
+loop_single_full_bb_p (class loop *loop)
{
unsigned i;
basic_block *bbs = get_loop_body (loop);
/* Return true if the loop is in its canonical form and false if not.
i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
static bool
-loop_canon_p (struct loop *loop)
+loop_canon_p (class loop *loop)
{
if (loop->inner || !loop_outer (loop))
make it one by splitting the first entry edge and
redirecting the others to the new BB. */
static void
-canon_loop (struct loop *loop)
+canon_loop (class loop *loop)
{
edge e;
edge_iterator i;
version may be entered. Just a guess. */
#define PROB_SMS_ENOUGH_ITERATIONS 80
-/* Used to calculate the upper bound of ii. */
-#define MAXII_FACTOR 2
-
/* Main entry point, perform SMS scheduling on the loops of the function
that consist of single basic blocks. */
static void
int maxii, max_asap;
partial_schedule_ptr ps;
basic_block bb = NULL;
- struct loop *loop;
+ class loop *loop;
basic_block condition_bb = NULL;
edge latch_edge;
- gcov_type trip_count = 0;
+ HOST_WIDE_INT trip_count, max_trip_count;
loop_optimizer_init (LOOPS_HAVE_PREHEADERS
| LOOPS_HAVE_RECORDED_EXITS);
get_ebb_head_tail (bb, bb, &head, &tail);
latch_edge = loop_latch_edge (loop);
gcc_assert (single_exit (loop));
- if (single_exit (loop)->count)
- trip_count = latch_edge->count / single_exit (loop)->count;
+ trip_count = get_estimated_loop_iterations_int (loop);
+ max_trip_count = get_max_loop_iterations_int (loop);
/* Perform SMS only on loops that their average count is above threshold. */
- if ( latch_edge->count
- && (latch_edge->count < single_exit (loop)->count * SMS_LOOP_AVERAGE_COUNT_THRESHOLD))
+ if ( latch_edge->count () > profile_count::zero ()
+ && (latch_edge->count()
+ < single_exit (loop)->count ().apply_scale
+ (param_sms_loop_average_count_threshold, 1)))
{
if (dump_file)
{
{
fprintf (dump_file, "SMS loop-count ");
fprintf (dump_file, "%" PRId64,
- (int64_t) bb->count);
+ (int64_t) bb->count.to_gcov_type ());
fprintf (dump_file, "\n");
fprintf (dump_file, "SMS trip-count ");
- fprintf (dump_file, "%" PRId64,
- (int64_t) trip_count);
+ fprintf (dump_file, "%" PRId64 "max %" PRId64,
+ (int64_t) trip_count, (int64_t) max_trip_count);
fprintf (dump_file, "\n");
- fprintf (dump_file, "SMS profile-sum-max ");
- fprintf (dump_file, "%" PRId64,
- (int64_t) profile_info->sum_max);
- fprintf (dump_file, "\n");
}
}
continue;
latch_edge = loop_latch_edge (loop);
gcc_assert (single_exit (loop));
- if (single_exit (loop)->count)
- trip_count = latch_edge->count / single_exit (loop)->count;
+ trip_count = get_estimated_loop_iterations_int (loop);
+ max_trip_count = get_max_loop_iterations_int (loop);
if (dump_file)
{
{
fprintf (dump_file, "SMS loop-count ");
fprintf (dump_file, "%" PRId64,
- (int64_t) bb->count);
- fprintf (dump_file, "\n");
- fprintf (dump_file, "SMS profile-sum-max ");
- fprintf (dump_file, "%" PRId64,
- (int64_t) profile_info->sum_max);
+ (int64_t) bb->count.to_gcov_type ());
fprintf (dump_file, "\n");
}
fprintf (dump_file, "SMS doloop\n");
mii = 1; /* Need to pass some estimate of mii. */
rec_mii = sms_order_nodes (g, mii, node_order, &max_asap);
mii = MAX (res_MII (g), rec_mii);
- maxii = MAX (max_asap, MAXII_FACTOR * mii);
+ mii = MAX (mii, 1);
+ maxii = MAX (max_asap, param_sms_max_ii_factor * mii);
if (dump_file)
fprintf (dump_file, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
gcc_assert (stage_count >= 1);
}
- /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
+ /* The default value of param_sms_min_sc is 2 as stage count of
1 means that there is no interleaving between iterations thus
we let the scheduling passes do the job in this case. */
- if (stage_count < PARAM_VALUE (PARAM_SMS_MIN_SC)
+ if (stage_count < param_sms_min_sc
|| (count_init && (loop_count <= stage_count))
- || (flag_branch_probabilities && (trip_count <= stage_count)))
+ || (max_trip_count >= 0 && max_trip_count <= stage_count)
+ || (trip_count >= 0 && trip_count <= stage_count))
{
if (dump_file)
{
" loop-count=", stage_count);
fprintf (dump_file, "%" PRId64, loop_count);
fprintf (dump_file, ", trip-count=");
- fprintf (dump_file, "%" PRId64, trip_count);
+ fprintf (dump_file, "%" PRId64 "max %" PRId64,
+ (int64_t) trip_count, (int64_t) max_trip_count);
fprintf (dump_file, ")\n");
}
break;
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;
+ profile_probability prob = profile_probability::guessed_always ()
+ .apply_scale (PROB_SMS_ENOUGH_ITERATIONS, 100);
loop_version (loop, comp_rtx, &condition_bb,
- prob, prob, REG_BR_PROB_BASE - prob,
- true);
+ prob, prob.invert (),
+ prob, prob.invert (), true);
}
/* Set new iteration count of loop kernel. */
The window would then start and end on the same row, but with
different "must precede" and "must follow" requirements. */
-/* A limit on the number of cycles that resource conflicts can span. ??? Should
- be provided by DFA, and be dependent on the type of insn scheduled. Currently
- set to 0 to save compile time. */
-#define DFA_HISTORY SMS_DFA_HISTORY
-
/* A threshold for the number of repeated unsuccessful attempts to insert
an empty row, before we flush the partial schedule and start over. */
#define MAX_SPLIT_NUM 10
int start, step, end;
int early_start, late_start;
ddg_edge_ptr e;
- sbitmap psp = sbitmap_alloc (ps->g->num_nodes);
- sbitmap pss = sbitmap_alloc (ps->g->num_nodes);
+ auto_sbitmap psp (ps->g->num_nodes);
+ auto_sbitmap pss (ps->g->num_nodes);
sbitmap u_node_preds = NODE_PREDECESSORS (u_node);
sbitmap u_node_succs = NODE_SUCCESSORS (u_node);
int psp_not_empty;
*start_p = start;
*step_p = step;
*end_p = end;
- sbitmap_free (psp);
- sbitmap_free (pss);
if ((start >= end && step == 1) || (start <= end && step == -1))
{
int flush_and_start_over = true;
int num_nodes = g->num_nodes;
int start, end, step; /* Place together into one struct? */
- sbitmap sched_nodes = sbitmap_alloc (num_nodes);
- sbitmap must_precede = sbitmap_alloc (num_nodes);
- sbitmap must_follow = sbitmap_alloc (num_nodes);
- sbitmap tobe_scheduled = sbitmap_alloc (num_nodes);
-
- partial_schedule_ptr ps = create_partial_schedule (ii, g, DFA_HISTORY);
+ auto_sbitmap sched_nodes (num_nodes);
+ auto_sbitmap must_precede (num_nodes);
+ auto_sbitmap must_follow (num_nodes);
+ auto_sbitmap tobe_scheduled (num_nodes);
+
+ /* Value of param_sms_dfa_history is a limit on the number of cycles that
+ resource conflicts can span. ??? Should be provided by DFA, and be
+ dependent on the type of insn scheduled. Set to 0 by default to save
+ compile time. */
+ partial_schedule_ptr ps = create_partial_schedule (ii, g,
+ param_sms_dfa_history);
bitmap_ones (tobe_scheduled);
bitmap_clear (sched_nodes);
ddg_node_ptr u_node = &ps->g->nodes[u];
rtx_insn *insn = u_node->insn;
- if (!NONDEBUG_INSN_P (insn))
- {
- bitmap_clear_bit (tobe_scheduled, u);
- continue;
- }
+ gcc_checking_assert (NONDEBUG_INSN_P (insn));
if (bitmap_bit_p (sched_nodes, u))
continue;
else
gcc_assert (bitmap_equal_p (tobe_scheduled, sched_nodes));
- sbitmap_free (sched_nodes);
- sbitmap_free (must_precede);
- sbitmap_free (must_follow);
- sbitmap_free (tobe_scheduled);
-
return ps;
}
check_nodes_order (int *node_order, int num_nodes)
{
int i;
- sbitmap tmp = sbitmap_alloc (num_nodes);
+ auto_sbitmap tmp (num_nodes);
bitmap_clear (tmp);
if (dump_file)
fprintf (dump_file, "\n");
-
- sbitmap_free (tmp);
}
/* Order the nodes of G for scheduling and pass the result in
int i, pos = 0;
ddg_ptr g = all_sccs->ddg;
int num_nodes = g->num_nodes;
- sbitmap prev_sccs = sbitmap_alloc (num_nodes);
- sbitmap on_path = sbitmap_alloc (num_nodes);
- sbitmap tmp = sbitmap_alloc (num_nodes);
- sbitmap ones = sbitmap_alloc (num_nodes);
+ auto_sbitmap prev_sccs (num_nodes);
+ auto_sbitmap on_path (num_nodes);
+ auto_sbitmap tmp (num_nodes);
+ auto_sbitmap ones (num_nodes);
bitmap_clear (prev_sccs);
bitmap_ones (ones);
bitmap_and_compl (tmp, ones, prev_sccs);
pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
}
- sbitmap_free (prev_sccs);
- sbitmap_free (on_path);
- sbitmap_free (tmp);
- sbitmap_free (ones);
}
/* MII is needed if we consider backarcs (that do not close recursive cycles). */
{
enum sms_direction dir;
int num_nodes = g->num_nodes;
- sbitmap workset = sbitmap_alloc (num_nodes);
- sbitmap tmp = sbitmap_alloc (num_nodes);
+ auto_sbitmap workset (num_nodes);
+ auto_sbitmap tmp (num_nodes);
sbitmap zero_bitmap = sbitmap_alloc (num_nodes);
- sbitmap predecessors = sbitmap_alloc (num_nodes);
- sbitmap successors = sbitmap_alloc (num_nodes);
+ auto_sbitmap predecessors (num_nodes);
+ auto_sbitmap successors (num_nodes);
bitmap_clear (predecessors);
find_predecessors (predecessors, g, nodes_ordered);
bitmap_and (workset, successors, scc);
}
}
- sbitmap_free (tmp);
- sbitmap_free (workset);
sbitmap_free (zero_bitmap);
- sbitmap_free (predecessors);
- sbitmap_free (successors);
return pos;
}
last_must_precede = next_ps_i;
}
/* The closing branch must be the last in the row. */
- if (must_precede
- && bitmap_bit_p (must_precede, next_ps_i->id)
- && JUMP_P (ps_rtl_insn (ps, next_ps_i->id)))
+ if (JUMP_P (ps_rtl_insn (ps, next_ps_i->id)))
return false;
last_in_row = next_ps_i;
{
rtx_insn *insn = ps_rtl_insn (ps, crr_insn->id);
- if (!NONDEBUG_INSN_P (insn))
- continue;
-
/* Check if there is room for the current insn. */
if (!can_issue_more || state_dead_lock_p (curr_state))
return true;
int c, sbitmap must_precede,
sbitmap must_follow)
{
- int has_conflicts = 0;
+ int i, first, amount, has_conflicts = 0;
ps_insn_ptr ps_i;
/* First add the node to the PS, if this succeeds check for
if (! (ps_i = add_node_to_ps (ps, n, c, must_precede, must_follow)))
return NULL; /* Failed to insert the node at the given cycle. */
- has_conflicts = ps_has_conflicts (ps, c, c)
- || (ps->history > 0
- && ps_has_conflicts (ps,
- c - ps->history,
- c + ps->history));
-
- /* Try different issue slots to find one that the given node can be
- scheduled in without conflicts. */
- while (has_conflicts)
+ while (1)
{
+ has_conflicts = ps_has_conflicts (ps, c, c);
+ if (ps->history > 0 && !has_conflicts)
+ {
+ /* Check all 2h+1 intervals, starting from c-2h..c up to c..2h,
+ but not more than ii intervals. */
+ first = c - ps->history;
+ amount = 2 * ps->history + 1;
+ if (amount > ps->ii)
+ amount = ps->ii;
+ for (i = first; i < first + amount; i++)
+ {
+ has_conflicts = ps_has_conflicts (ps,
+ i - ps->history,
+ i + ps->history);
+ if (has_conflicts)
+ break;
+ }
+ }
+ if (!has_conflicts)
+ break;
+ /* Try different issue slots to find one that the given node can be
+ scheduled in without conflicts. */
if (! ps_insn_advance_column (ps, ps_i, must_follow))
break;
- has_conflicts = ps_has_conflicts (ps, c, c)
- || (ps->history > 0
- && ps_has_conflicts (ps,
- c - ps->history,
- c + ps->history));
}
if (has_conflicts)
projects / gcc.git / blobdiff