/* The number of the region containing a block. */
static int *containing_rgn;
+/* The minimum probability of reaching a source block so that it will be
+ considered for speculative scheduling. */
+static int min_spec_prob;
+
#define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
#define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
#define BLOCK_TO_BB(block) (block_to_bb[block])
#define IS_DOMINATED(bb_src, bb_trg) \
( TEST_BIT (dom[bb_src], bb_trg) )
-/* Probability: Prob[i] is a float in [0, 1] which is the probability
- of bb i relative to the region entry. */
-static float *prob;
-
-/* The probability of bb_src, relative to bb_trg. Note, that while the
- 'prob[bb]' is a float in [0, 1], this macro returns an integer
- in [0, 100]. */
-#define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
- prob[bb_trg])))
+/* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
+ the probability of bb i relative to the region entry. */
+static int *prob;
/* Bit-set of edges, where bit i stands for edge i. */
typedef sbitmap edgeset;
#define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
#define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
-/* Parameters affecting the decision of rank_for_schedule().
- ??? Nope. But MIN_PROBABILITY is used in compute_trg_info. */
-#define MIN_PROBABILITY 40
-
/* Speculative scheduling functions. */
static int check_live_1 (int, rtx);
static void update_live_1 (int, rtx);
STACK, SP and DFS_NR are only used during the first traversal. */
/* Allocate and initialize variables for the first traversal. */
- max_hdr = xmalloc (last_basic_block * sizeof (int));
- dfs_nr = xcalloc (last_basic_block, sizeof (int));
- stack = xmalloc (n_edges * sizeof (edge_iterator));
+ max_hdr = XNEWVEC (int, last_basic_block);
+ dfs_nr = XCNEWVEC (int, last_basic_block);
+ stack = XNEWVEC (edge_iterator, n_edges);
inner = sbitmap_alloc (last_basic_block);
sbitmap_ones (inner);
/* Second traversal:find reducible inner loops and topologically sort
block of each region. */
- queue = xmalloc (n_basic_blocks * sizeof (int));
+ queue = XNEWVEC (int, n_basic_blocks);
/* Find blocks which are inner loop headers. We still have non-reducible
loops to consider at this point. */
static void
compute_dom_prob_ps (int bb)
{
- int pred_bb;
- int nr_out_edges, nr_rgn_out_edges;
- edge_iterator in_ei, out_ei;
- edge in_edge, out_edge;
+ edge_iterator in_ei;
+ edge in_edge;
- prob[bb] = 0.0;
if (IS_RGN_ENTRY (bb))
{
SET_BIT (dom[bb], 0);
- prob[bb] = 1.0;
+ prob[bb] = REG_BR_PROB_BASE;
return;
}
+ prob[bb] = 0;
+
/* Initialize dom[bb] to '111..1'. */
sbitmap_ones (dom[bb]);
FOR_EACH_EDGE (in_edge, in_ei, BASIC_BLOCK (BB_TO_BLOCK (bb))->preds)
{
+ int pred_bb;
+ edge out_edge;
+ edge_iterator out_ei;
+
if (in_edge->src == ENTRY_BLOCK_PTR)
continue;
sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
- nr_out_edges = 0;
- nr_rgn_out_edges = 0;
-
FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
- {
- ++nr_out_edges;
-
- /* The successor doesn't belong in the region? */
- if (out_edge->dest != EXIT_BLOCK_PTR
- && CONTAINING_RGN (out_edge->dest->index)
- != CONTAINING_RGN (BB_TO_BLOCK (bb)))
- ++nr_rgn_out_edges;
-
- SET_BIT (pot_split[bb], EDGE_TO_BIT (out_edge));
- }
+ SET_BIT (pot_split[bb], EDGE_TO_BIT (out_edge));
- /* Now nr_rgn_out_edges is the number of region-exit edges from
- pred, and nr_out_edges will be the number of pred out edges
- not leaving the region. */
- nr_out_edges -= nr_rgn_out_edges;
- if (nr_rgn_out_edges > 0)
- prob[bb] += 0.9 * prob[pred_bb] / nr_out_edges;
- else
- prob[bb] += prob[pred_bb] / nr_out_edges;
+ prob[bb] += ((prob[pred_bb] * in_edge->probability) / REG_BR_PROB_BASE);
}
SET_BIT (dom[bb], bb);
if (sched_verbose >= 2)
fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
- (int) (100.0 * prob[bb]));
+ (100 * prob[bb]) / REG_BR_PROB_BASE);
}
/* Functions for target info. */
sp = candidate_table + trg;
sp->is_valid = 1;
sp->is_speculative = 0;
- sp->src_prob = 100;
+ sp->src_prob = REG_BR_PROB_BASE;
- visited = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
+ visited = sbitmap_alloc (last_basic_block);
for (i = trg + 1; i < current_nr_blocks; i++)
{
sp->is_valid = IS_DOMINATED (i, trg);
if (sp->is_valid)
{
- sp->src_prob = GET_SRC_PROB (i, trg);
- sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
+ int tf = prob[trg], cf = prob[i];
+
+ /* In CFGs with low probability edges TF can possibly be zero. */
+ sp->src_prob = (tf ? ((cf * REG_BR_PROB_BASE) / tf) : 0);
+ sp->is_valid = (sp->src_prob >= min_spec_prob);
}
if (sp->is_valid)
block = el.first_member[j]->src;
FOR_EACH_EDGE (e, ei, block->succs)
{
- if (!TEST_BIT (visited,
- e->dest->index - (INVALID_BLOCK + 1)))
+ if (!TEST_BIT (visited, e->dest->index))
{
for (k = 0; k < el.nr_members; k++)
if (e == el.first_member[k])
if (k >= el.nr_members)
{
bblst_table[bblst_last++] = e->dest;
- SET_BIT (visited,
- e->dest->index - (INVALID_BLOCK + 1));
+ SET_BIT (visited, e->dest->index);
update_idx++;
}
}
/* Prepare current target block info. */
if (current_nr_blocks > 1)
{
- candidate_table = xmalloc (current_nr_blocks * sizeof (candidate));
+ candidate_table = XNEWVEC (candidate, current_nr_blocks);
bblst_last = 0;
/* bblst_table holds split blocks and update blocks for each block after
the TO blocks of region edges, so there can be at most rgn_nr_edges
of them. */
bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
- bblst_table = xmalloc (bblst_size * sizeof (basic_block));
+ bblst_table = XNEWVEC (basic_block, bblst_size);
edgelst_last = 0;
- edgelst_table = xmalloc (rgn_nr_edges * sizeof (edge));
+ edgelst_table = XNEWVEC (edge, rgn_nr_edges);
compute_trg_info (target_bb);
}
T = [addr]
C ? addr += 4
- !C ? X += 12
+ !C ? X += 12
C ? T += 1
- C ? jump foo
+ C ? jump foo
On a target with a one cycle stall on a memory access the optimal
sequence would be:
if (!reload_completed || ! JUMP_P (tail))
return;
- insn = PREV_INSN (tail);
+ insn = tail;
while (insn != head)
{
+ insn = PREV_INSN (insn);
+
/* Note that we want to add this dependency even when
sched_insns_conditions_mutex_p returns true. The whole point
is that we _want_ this dependency, even if these insns really
are independent. */
if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC)
add_dependence (tail, insn, REG_DEP_ANTI);
-
- insn = PREV_INSN (insn);
}
#endif
}
init_deps_global ();
/* Initializations for region data dependence analysis. */
- bb_deps = xmalloc (sizeof (struct deps) * current_nr_blocks);
+ bb_deps = XNEWVEC (struct deps, current_nr_blocks);
for (bb = 0; bb < current_nr_blocks; bb++)
init_deps (bb_deps + bb);
/* Compute interblock info: probabilities, split-edges, dominators, etc. */
if (current_nr_blocks > 1)
{
- prob = xmalloc ((current_nr_blocks) * sizeof (float));
+ prob = XNEWVEC (int, current_nr_blocks);
dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
sbitmap_vector_zero (dom, current_nr_blocks);
SET_EDGE_TO_BIT (e, rgn_nr_edges++);
}
- rgn_edges = xmalloc (rgn_nr_edges * sizeof (edge));
+ rgn_edges = XNEWVEC (edge, rgn_nr_edges);
rgn_nr_edges = 0;
FOR_EACH_BB (block)
{
int rgn;
nr_regions = 0;
- rgn_table = xmalloc ((n_basic_blocks) * sizeof (region));
- rgn_bb_table = xmalloc ((n_basic_blocks) * sizeof (int));
- block_to_bb = xmalloc ((last_basic_block) * sizeof (int));
- containing_rgn = xmalloc ((last_basic_block) * sizeof (int));
+ rgn_table = XNEWVEC (region, n_basic_blocks);
+ rgn_bb_table = XNEWVEC (int, n_basic_blocks);
+ block_to_bb = XNEWVEC (int, last_basic_block);
+ containing_rgn = XNEWVEC (int, last_basic_block);
/* Compute regions for scheduling. */
if (reload_completed
- || n_basic_blocks == 1
+ || n_basic_blocks == NUM_FIXED_BLOCKS + 1
|| !flag_schedule_interblock
|| is_cfg_nonregular ())
{
if (CHECK_DEAD_NOTES)
{
blocks = sbitmap_alloc (last_basic_block);
- deaths_in_region = xmalloc (sizeof (int) * nr_regions);
+ deaths_in_region = XNEWVEC (int, nr_regions);
/* Remove all death notes from the subroutine. */
for (rgn = 0; rgn < nr_regions; rgn++)
{
count_or_remove_death_notes (NULL, 1);
}
-/* The one entry point in this file. DUMP_FILE is the dump file for
- this pass. */
+/* The one entry point in this file. */
void
-schedule_insns (FILE *dump_file)
+schedule_insns (void)
{
sbitmap large_region_blocks, blocks;
int rgn;
/* Taking care of this degenerate case makes the rest of
this code simpler. */
- if (n_basic_blocks == 0)
+ if (n_basic_blocks == NUM_FIXED_BLOCKS)
return;
nr_inter = 0;
nr_spec = 0;
+ sched_init ();
- sched_init (dump_file);
+ min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE)
+ / 100);
init_regions ();
current_sched_info = ®ion_sched_info;
-
/* Schedule every region in the subroutine. */
for (rgn = 0; rgn < nr_regions; rgn++)
schedule_region (rgn);
}
/* Run instruction scheduler. */
-static void
+static unsigned int
rest_of_handle_sched (void)
{
#ifdef INSN_SCHEDULING
/* Do control and data sched analysis,
and write some of the results to dump file. */
- schedule_insns (dump_file);
+ schedule_insns ();
#endif
+ return 0;
}
static bool
}
/* Run second scheduling pass after reload. */
-static void
+static unsigned int
rest_of_handle_sched2 (void)
{
#ifdef INSN_SCHEDULING
if (flag_sched2_use_superblocks || flag_sched2_use_traces)
{
- schedule_ebbs (dump_file);
+ schedule_ebbs ();
/* No liveness updating code yet, but it should be easy to do.
reg-stack recomputes the liveness when needed for now. */
count_or_remove_death_notes (NULL, 1);
cleanup_cfg (CLEANUP_EXPENSIVE);
}
else
- schedule_insns (dump_file);
+ schedule_insns ();
#endif
+ return 0;
}
struct tree_opt_pass pass_sched =
OSDN Git Service
