/* Instruction scheduling pass.
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
- 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
+ 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010
Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
#include "system.h"
#include "coretypes.h"
#include "tm.h"
+#include "diagnostic-core.h"
#include "toplev.h"
#include "rtl.h"
#include "tm_p.h"
static void schedule_region (int);
static rtx concat_INSN_LIST (rtx, rtx);
static void concat_insn_mem_list (rtx, rtx, rtx *, rtx *);
-static void propagate_deps (int, struct deps *);
+static void propagate_deps (int, struct deps_desc *);
static void free_pending_lists (void);
/* Functions for construction of the control flow graph. */
/* Print the regions, for debugging purposes. Callable from debugger. */
-void
+DEBUG_FUNCTION void
debug_regions (void)
{
int rgn, bb;
/* Print the region's basic blocks. */
-void
+DEBUG_FUNCTION void
debug_region (int rgn)
{
int bb;
}
/* The same, but first open a file specified by FNAME. */
-void
+void
dump_region_dot_file (const char *fname, int rgn)
{
FILE *f = fopen (fname, "wt");
for (bb = ebb_start; ; bb = bb->next_bb)
{
edge e;
- edge_iterator ei;
rgn_bb_table[i] = bb->index;
RGN_NR_BLOCKS (nr_regions)++;
if (bb->next_bb == EXIT_BLOCK_PTR
|| LABEL_P (BB_HEAD (bb->next_bb)))
break;
-
- FOR_EACH_EDGE (e, ei, bb->succs)
- if ((e->flags & EDGE_FALLTHRU) != 0)
- break;
+
+ e = find_fallthru_edge (bb->succs);
if (! e)
break;
if (e->probability <= probability_cutoff)
static int
rgn_estimate_number_of_insns (basic_block bb)
{
- return INSN_LUID (BB_END (bb)) - INSN_LUID (BB_HEAD (bb));
+ int count;
+
+ count = INSN_LUID (BB_END (bb)) - INSN_LUID (BB_HEAD (bb));
+
+ if (MAY_HAVE_DEBUG_INSNS)
+ {
+ rtx insn;
+
+ FOR_BB_INSNS (bb, insn)
+ if (DEBUG_INSN_P (insn))
+ count--;
+ }
+
+ return count;
}
/* Update number of blocks and the estimate for number of insns
int *queue, *degree1 = NULL;
/* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
there basic blocks, which are forced to be region heads.
- This is done to try to assemble few smaller regions
+ This is done to try to assemble few smaller regions
from a too_large region. */
sbitmap extended_rgn_header = NULL;
bool extend_regions_p;
block of each region. */
queue = XNEWVEC (int, n_basic_blocks);
-
+
extend_regions_p = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS) > 0;
if (extend_regions_p)
{
loop_head = max_hdr[bb->index];
if (extend_regions_p)
- /* We save degree in case when we meet a too_large region
- and cancel it. We need a correct degree later when
+ /* We save degree in case when we meet a too_large region
+ and cancel it. We need a correct degree later when
calling extend_rgns. */
memcpy (degree1, degree, last_basic_block * sizeof (int));
-
+
/* Decrease degree of all I's successors for topological
ordering. */
FOR_EACH_EDGE (e, ei, bb->succs)
degree = degree1;
degree1 = t;
-
+
/* And force successors of BB to be region heads.
This may provide several smaller regions instead
of one too_large region. */
if (extend_regions_p)
{
free (degree1);
-
+
sbitmap_a_or_b (header, header, extended_rgn_header);
sbitmap_free (extended_rgn_header);
-
+
extend_rgns (degree, &idx, header, max_hdr);
}
}
static int gather_region_statistics (int **);
static void print_region_statistics (int *, int, int *, int);
-/* Calculate the histogram that shows the number of regions having the
- given number of basic blocks, and store it in the RSP array. Return
+/* Calculate the histogram that shows the number of regions having the
+ given number of basic blocks, and store it in the RSP array. Return
the size of this array. */
static int
gather_region_statistics (int **rsp)
gcc_assert (nr_blocks >= 1);
if (nr_blocks > a_sz)
- {
+ {
a = XRESIZEVEC (int, a, nr_blocks);
do
a[a_sz++] = 0;
return a_sz;
}
-/* Print regions statistics. S1 and S2 denote the data before and after
+/* Print regions statistics. S1 and S2 denote the data before and after
calling extend_rgns, respectively. */
static void
print_region_statistics (int *s1, int s1_sz, int *s2, int s2_sz)
{
int i;
-
- /* We iterate until s2_sz because extend_rgns does not decrease
+
+ /* We iterate until s2_sz because extend_rgns does not decrease
the maximal region size. */
for (i = 1; i < s2_sz; i++)
{
/* This block already was processed in find_rgns. */
max_hdr[bbn] = -1;
}
-
+
/* The idea is to topologically walk through CFG in top-down order.
During the traversal, if all the predecessors of a node are
marked to be in the same region (they all have the same max_hdr),
- then current node is also marked to be a part of that region.
+ then current node is also marked to be a part of that region.
Otherwise the node starts its own region.
- CFG should be traversed until no further changes are made. On each
- iteration the set of the region heads is extended (the set of those
- blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
+ CFG should be traversed until no further changes are made. On each
+ iteration the set of the region heads is extended (the set of those
+ blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
set of all basic blocks, thus the algorithm is guaranteed to
terminate. */
while (rescan && iter < max_iter)
{
rescan = 0;
-
+
for (i = nblocks - 1; i >= 0; i--)
{
edge e;
edge_iterator ei;
int bbn = order[i];
-
+
if (max_hdr[bbn] != -1 && !TEST_BIT (header, bbn))
{
int hdr = -1;
{
hdr = bbn;
break;
- }
+ }
}
else
/* BB starts its own region. */
{
hdr = bbn;
break;
- }
+ }
}
-
+
if (hdr == bbn)
{
/* If BB start its own region,
rescan = 1;
}
else
- gcc_assert (hdr != -1);
+ gcc_assert (hdr != -1);
max_hdr[bbn] = hdr;
}
iter++;
}
-
+
/* Statistics were gathered on the SPEC2000 package of tests with
mainline weekly snapshot gcc-4.1-20051015 on ia64.
-
+
Statistics for SPECint:
1 iteration : 1751 cases (38.7%)
2 iterations: 2770 cases (61.3%)
Blocks wrapped in regions by find_rgns without extension: 18295 blocks
Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
(We don't count single block regions here).
-
+
Statistics for SPECfp:
1 iteration : 621 cases (35.9%)
2 iterations: 1110 cases (64.1%)
This can be overridden with max-sched-extend-regions-iters parameter:
0 - disable region extension,
N > 0 - do at most N iterations. */
-
+
if (sched_verbose && iter != 0)
fprintf (sched_dump, ";; Region extension iterations: %d%s\n", iter,
rescan ? "... failed" : "");
-
+
if (!rescan && iter != 0)
{
int *s1 = NULL, s1_sz = 0;
edge e;
edge_iterator ei;
int num_bbs = 0, j, num_insns = 0, large;
-
+
large = too_large (bbn, &num_bbs, &num_insns);
degree[bbn] = -1;
{
RGN_NR_BLOCKS (nr_regions) = 1;
nr_regions++;
- }
+ }
num_bbs = 1;
int succn = order[j];
if (max_hdr[succn] == bbn)
- /* This cycle iterates over all basic blocks, that
+ /* This cycle iterates over all basic blocks, that
are supposed to be in the region with head BBN,
and wraps them into that region (or in single
block region). */
gcc_assert (degree[succn] == 0);
degree[succn] = -1;
- rgn_bb_table[idx] = succn;
+ rgn_bb_table[idx] = succn;
BLOCK_TO_BB (succn) = large ? 0 : num_bbs++;
CONTAINING_RGN (succn) = nr_regions;
}
idx++;
-
+
FOR_EACH_EDGE (e, ei, BASIC_BLOCK (succn)->succs)
if (e->dest != EXIT_BLOCK_PTR)
degree[e->dest->index]--;
{
int *s2, s2_sz;
- /* Get the new statistics and print the comparison with the
+ /* Get the new statistics and print the comparison with the
one before calling this function. */
s2_sz = gather_region_statistics (&s2);
print_region_statistics (s1, s1_sz, s2, s2_sz);
free (s2);
}
}
-
+
free (order);
free (max_hdr);
- *idxp = idx;
+ *idxp = idx;
}
/* Functions for regions scheduling information. */
/* We shouldn't have any real ebbs yet. */
gcc_assert (ebb_head [bb] == bb + current_blocks);
-
+
if (IS_RGN_ENTRY (bb))
{
SET_BIT (dom[bb], 0);
/* Print candidates info, for debugging purposes. Callable from debugger. */
-void
+DEBUG_FUNCTION void
debug_candidate (int i)
{
if (!candidate_table[i].is_valid)
/* Print candidates info, for debugging purposes. Callable from debugger. */
-void
+DEBUG_FUNCTION void
debug_candidates (int trg)
{
int i;
/* Initialize ready list with all 'ready' insns in target block.
Count number of insns in the target block being scheduled. */
for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
- {
+ {
try_ready (insn);
target_n_insns++;
src_head = head;
for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
- if (INSN_P (insn))
+ if (INSN_P (insn) && !BOUNDARY_DEBUG_INSN_P (insn))
try_ready (insn);
}
}
if (INSN_BB (insn) != target_bb
&& IS_SPECULATIVE_INSN (insn)
&& !check_live (insn, INSN_BB (insn)))
- return 0;
+ return 0;
else
return 1;
}
int not_ex_free = 0;
/* For speculative insns, before inserting to ready/queue,
- check live, exception-free, and issue-delay. */
+ check live, exception-free, and issue-delay. */
if (!IS_VALID (INSN_BB (next))
|| CANT_MOVE (next)
|| (IS_SPECULATIVE_INSN (next)
&& ((recog_memoized (next) >= 0
- && min_insn_conflict_delay (curr_state, next, next)
+ && min_insn_conflict_delay (curr_state, next, next)
> PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY))
|| IS_SPECULATION_CHECK_P (next)
|| !check_live (next, INSN_BB (next))
ts = (ts & ~SPECULATIVE) | HARD_DEP;
}
}
-
+
return ts;
}
add_branch_dependences. */
}
-/* This variable holds common_sched_info hooks and data relevant to
+/* This variable holds common_sched_info hooks and data relevant to
the interblock scheduler. */
static struct common_sched_info_def rgn_common_sched_info;
0, 0, 0
};
+/* Return true if scheduling INSN will trigger finish of scheduling
+ current block. */
+static bool
+rgn_insn_finishes_block_p (rtx insn)
+{
+ if (INSN_BB (insn) == target_bb
+ && sched_target_n_insns + 1 == target_n_insns)
+ /* INSN is the last not-scheduled instruction in the current block. */
+ return true;
+
+ return false;
+}
+
/* Used in schedule_insns to initialize current_sched_info for scheduling
regions (or single basic blocks). */
rgn_rank,
rgn_print_insn,
contributes_to_priority,
+ rgn_insn_finishes_block_p,
NULL, NULL,
NULL, NULL,
return rgn_sched_info.sched_max_insns_priority;
}
-/* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register. */
+/* Determine if PAT sets a TARGET_CLASS_LIKELY_SPILLED_P register. */
static bool
sets_likely_spilled (rtx pat)
if (GET_CODE (pat) == SET
&& REG_P (x)
- && REGNO (x) < FIRST_PSEUDO_REGISTER
- && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x))))
+ && HARD_REGISTER_P (x)
+ && targetm.class_likely_spilled_p (REGNO_REG_CLASS (REGNO (x))))
*ret = true;
}
COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
- Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values)
- are not moved before reload because we can wind up with register
+ Insns setting TARGET_CLASS_LIKELY_SPILLED_P registers (usually return
+ values) are not moved before reload because we can wind up with register
allocation failures. */
+ while (tail != head && DEBUG_INSN_P (tail))
+ tail = PREV_INSN (tail);
+
insn = tail;
last = 0;
while (CALL_P (insn)
if (insn == head)
break;
- insn = PREV_INSN (insn);
+ do
+ insn = PREV_INSN (insn);
+ while (insn != head && DEBUG_INSN_P (insn));
}
/* Make sure these insns are scheduled last in their block. */
{
insn = prev_nonnote_insn (insn);
- if (TEST_BIT (insn_referenced, INSN_LUID (insn)))
+ if (TEST_BIT (insn_referenced, INSN_LUID (insn))
+ || DEBUG_INSN_P (insn))
continue;
if (! sched_insns_conditions_mutex_p (last, insn))
add_dependence (last, insn, REG_DEP_ANTI);
}
-#ifdef HAVE_conditional_execution
+ if (!targetm.have_conditional_execution ())
+ return;
+
/* Finally, if the block ends in a jump, and we are doing intra-block
scheduling, make sure that the branch depends on any COND_EXEC insns
inside the block to avoid moving the COND_EXECs past the branch insn.
if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC)
add_dependence (tail, insn, REG_DEP_ANTI);
}
-#endif
}
/* Data structures for the computation of data dependences in a regions. We
the variables of its predecessors. When the analysis for a bb completes,
we save the contents to the corresponding bb_deps[bb] variable. */
-static struct deps *bb_deps;
+static struct deps_desc *bb_deps;
/* Duplicate the INSN_LIST elements of COPY and prepend them to OLD. */
/* Join PRED_DEPS to the SUCC_DEPS. */
void
-deps_join (struct deps *succ_deps, struct deps *pred_deps)
+deps_join (struct deps_desc *succ_deps, struct deps_desc *pred_deps)
{
unsigned reg;
reg_set_iterator rsi;
succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
+ succ_rl->implicit_sets
+ = concat_INSN_LIST (pred_rl->implicit_sets, succ_rl->implicit_sets);
succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
succ_rl->clobbers);
succ_rl->uses_length += pred_rl->uses_length;
= concat_INSN_LIST (pred_deps->last_function_call,
succ_deps->last_function_call);
+ /* last_function_call_may_noreturn is inherited by successor. */
+ succ_deps->last_function_call_may_noreturn
+ = concat_INSN_LIST (pred_deps->last_function_call_may_noreturn,
+ succ_deps->last_function_call_may_noreturn);
+
/* sched_before_next_call is inherited by successor. */
succ_deps->sched_before_next_call
= concat_INSN_LIST (pred_deps->sched_before_next_call,
/* After computing the dependencies for block BB, propagate the dependencies
found in TMP_DEPS to the successors of the block. */
static void
-propagate_deps (int bb, struct deps *pred_deps)
+propagate_deps (int bb, struct deps_desc *pred_deps)
{
basic_block block = BASIC_BLOCK (BB_TO_BLOCK (bb));
edge_iterator ei;
bb's successors.
Specifically for reg-reg data dependences, the block insns are
- scanned by sched_analyze () top-to-bottom. Two lists are
+ scanned by sched_analyze () top-to-bottom. Three lists are
maintained by sched_analyze (): reg_last[].sets for register DEFs,
- and reg_last[].uses for register USEs.
+ reg_last[].implicit_sets for implicit hard register DEFs, and
+ reg_last[].uses for register USEs.
When analysis is completed for bb, we update for its successors:
; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
+ ; - IMPLICIT_DEFS[succ] = Union (IMPLICIT_DEFS [succ], IMPLICIT_DEFS [bb])
; - USES[succ] = Union (USES [succ], DEFS [bb])
The mechanism for computing mem-mem data dependence is very
compute_block_dependences (int bb)
{
rtx head, tail;
- struct deps tmp_deps;
+ struct deps_desc tmp_deps;
tmp_deps = bb_deps[bb];
get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
+ if (no_real_insns_p (head, tail))
+ return;
+
sched_free_deps (head, tail, true);
}
Callable from debugger. */
/* Print dependences for debugging starting from FROM_BB.
Callable from debugger. */
-void
+DEBUG_FUNCTION void
debug_rgn_dependencies (int from_bb)
{
int bb;
return true;
}
-/* Free all region dependencies saved in INSN_BACK_DEPS and
+/* Free all region dependencies saved in INSN_BACK_DEPS and
INSN_RESOLVED_BACK_DEPS. The Haifa scheduler does this on the fly
- when scheduling, so this function is supposed to be called from
+ when scheduling, so this function is supposed to be called from
the selective scheduling only. */
void
free_rgn_deps (void)
for (bb = 0; bb < current_nr_blocks; bb++)
{
rtx head, tail;
-
+
gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
/* Compute insn priority for a current region. */
void
-compute_priorities (void)
+compute_priorities (void)
{
int bb;
for (bb = 0; bb < current_nr_blocks; bb++)
{
rtx head, tail;
-
+
gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
+ if (no_real_insns_p (head, tail))
+ continue;
+
rgn_n_insns += set_priorities (head, tail);
}
current_sched_info->sched_max_insns_priority++;
sched_extend_ready_list (rgn_n_insns);
+ if (sched_pressure_p)
+ {
+ sched_init_region_reg_pressure_info ();
+ for (bb = 0; bb < current_nr_blocks; bb++)
+ {
+ basic_block first_bb, last_bb;
+ rtx head, tail;
+
+ first_bb = EBB_FIRST_BB (bb);
+ last_bb = EBB_LAST_BB (bb);
+
+ get_ebb_head_tail (first_bb, last_bb, &head, &tail);
+
+ if (no_real_insns_p (head, tail))
+ {
+ gcc_assert (first_bb == last_bb);
+ continue;
+ }
+ sched_setup_bb_reg_pressure_info (first_bb, PREV_INSN (head));
+ }
+ }
+
/* Now we can schedule all blocks. */
for (bb = 0; bb < current_nr_blocks; bb++)
{
/* Set variables for the current region. */
current_nr_blocks = RGN_NR_BLOCKS (rgn);
current_blocks = RGN_BLOCKS (rgn);
-
+
/* EBB_HEAD is a region-scope structure. But we realloc it for
each region to save time/memory/something else.
See comments in add_block1, for what reasons we allocate +1 element. */
init_deps_global ();
/* Initializations for region data dependence analysis. */
- bb_deps = XNEWVEC (struct deps, current_nr_blocks);
+ bb_deps = XNEWVEC (struct deps_desc, current_nr_blocks);
for (bb = 0; bb < current_nr_blocks; bb++)
- init_deps (bb_deps + bb);
+ init_deps (bb_deps + bb, false);
/* Initialize bitmap used in add_branch_dependences. */
insn_referenced = sbitmap_alloc (sched_max_luid);
sbitmap_zero (insn_referenced);
-
+
/* Compute backward dependencies. */
for (bb = 0; bb < current_nr_blocks; bb++)
compute_block_dependences (bb);
-
+
sbitmap_free (insn_referenced);
free_pending_lists ();
finish_deps_global ();
sched_rgn_local_init (int rgn)
{
int bb;
-
+
/* Compute interblock info: probabilities, split-edges, dominators, etc. */
if (current_nr_blocks > 1)
{
}
/* Free data computed for the finished region. */
-void
+void
sched_rgn_local_free (void)
{
free (prob);
BLOCK_TO_BB (bb->index) = 0;
nr_regions++;
-
+
RGN_BLOCKS (nr_regions) = i + 1;
}
RGN_DONT_CALC_DEPS (nr_regions - 1) = (after == EXIT_BLOCK_PTR);
}
else
- {
+ {
int i, pos;
/* We need to fix rgn_table, block_to_bb, containing_rgn
BLOCK_TO_BB (bb->index) = BLOCK_TO_BB (after->index);
/* We extend ebb_head to one more position to
- easily find the last position of the last ebb in
+ easily find the last position of the last ebb in
the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
is _always_ valid for access. */
/* Source position: ebb_head[i]
Destination position: ebb_head[i] + 1
- Last position:
+ Last position:
RGN_BLOCKS (nr_regions) - 1
Number of elements to copy: (last_position) - (source_position) + 1
*/
-
+
memmove (rgn_bb_table + pos + 1,
rgn_bb_table + pos,
((RGN_BLOCKS (nr_regions) - 1) - (pos) + 1)
* sizeof (*rgn_bb_table));
rgn_bb_table[pos] = bb->index;
-
+
for (; i <= current_nr_blocks; i++)
ebb_head [i]++;
i = CONTAINING_RGN (after->index);
CONTAINING_RGN (bb->index) = i;
-
+
RGN_HAS_REAL_EBB (i) = 1;
for (++i; i <= nr_regions; i++)
int old_pos, new_pos, i;
BLOCK_TO_BB (check_bb_nexti) = BLOCK_TO_BB (bbi);
-
+
for (old_pos = ebb_head[BLOCK_TO_BB (check_bbi) + 1] - 1;
rgn_bb_table[old_pos] != check_bb_nexti;
old_pos--);
new_pos--);
new_pos++;
gcc_assert (new_pos > ebb_head[BLOCK_TO_BB (bbi)]);
-
+
gcc_assert (new_pos < old_pos);
memmove (rgn_bb_table + new_pos + 1,
gate_handle_sched2 (void)
{
#ifdef INSN_SCHEDULING
- return optimize > 0 && flag_schedule_insns_after_reload
+ return optimize > 0 && flag_schedule_insns_after_reload
&& dbg_cnt (sched2_func);
#else
return 0;
{
/* Do control and data sched analysis again,
and write some more of the results to dump file. */
- if (flag_sched2_use_superblocks || flag_sched2_use_traces)
+ if (flag_sched2_use_superblocks)
schedule_ebbs ();
else
schedule_insns ();
TODO_ggc_collect /* todo_flags_finish */
}
};
-