/* Instruction scheduling pass.
- Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
- 2001, 2002, 2003, 2004, 2005, 2006, 2007
- Free Software Foundation, Inc.
+ Copyright (C) 1992-2015 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 "toplev.h"
+#include "diagnostic-core.h"
#include "rtl.h"
#include "tm_p.h"
#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 "toplev.h"
#include "recog.h"
-#include "cfglayout.h"
#include "params.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfganal.h"
+#include "predict.h"
+#include "basic-block.h"
#include "sched-int.h"
+#include "sel-sched.h"
#include "target.h"
-#include "timevar.h"
#include "tree-pass.h"
#include "dbgcnt.h"
+#include "emit-rtl.h"
#ifdef INSN_SCHEDULING
+
/* Some accessor macros for h_i_d members only used within this file. */
-#define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count)
-#define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load)
-#define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn)
+#define FED_BY_SPEC_LOAD(INSN) (HID (INSN)->fed_by_spec_load)
+#define IS_LOAD_INSN(INSN) (HID (insn)->is_load_insn)
/* nr_inter/spec counts interblock/speculative motion for the function. */
static int nr_inter, nr_spec;
static int is_cfg_nonregular (void);
-static bool sched_is_disabled_for_current_region_p (void);
-
-/* A region is the main entity for interblock scheduling: insns
- are allowed to move between blocks in the same region, along
- control flow graph edges, in the 'up' direction. */
-typedef struct
-{
- /* Number of extended basic blocks in region. */
- int rgn_nr_blocks;
- /* cblocks in the region (actually index in rgn_bb_table). */
- int rgn_blocks;
- /* Dependencies for this region are already computed. Basically, indicates,
- that this is a recovery block. */
- unsigned int dont_calc_deps : 1;
- /* This region has at least one non-trivial ebb. */
- unsigned int has_real_ebb : 1;
-}
-region;
/* Number of regions in the procedure. */
-static int nr_regions;
+int nr_regions = 0;
+
+/* Same as above before adding any new regions. */
+static int nr_regions_initial = 0;
/* Table of region descriptions. */
-static region *rgn_table;
+region *rgn_table = NULL;
/* Array of lists of regions' blocks. */
-static int *rgn_bb_table;
+int *rgn_bb_table = NULL;
/* Topological order of blocks in the region (if b2 is reachable from
b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
always referred to by either block or b, while its topological
order name (in the region) is referred to by bb. */
-static int *block_to_bb;
+int *block_to_bb = NULL;
/* The number of the region containing a block. */
-static int *containing_rgn;
+int *containing_rgn = NULL;
+
+/* ebb_head [i] - is index in rgn_bb_table of the head basic block of i'th ebb.
+ Currently we can get a ebb only through splitting of currently
+ scheduling block, therefore, we don't need ebb_head array for every region,
+ hence, its sufficient to hold it for current one only. */
+int *ebb_head = NULL;
/* 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 RGN_DONT_CALC_DEPS(rgn) (rgn_table[rgn].dont_calc_deps)
-#define RGN_HAS_REAL_EBB(rgn) (rgn_table[rgn].has_real_ebb)
-#define BLOCK_TO_BB(block) (block_to_bb[block])
-#define CONTAINING_RGN(block) (containing_rgn[block])
-
-void debug_regions (void);
-static void find_single_block_region (void);
+static void find_single_block_region (bool);
static void find_rgns (void);
-static void extend_rgns (int *, int *, sbitmap, int *);
static bool too_large (int, int *, int *);
-extern void debug_live (int, int);
-
/* Blocks of the current region being scheduled. */
-static int current_nr_blocks;
-static int current_blocks;
+int current_nr_blocks;
+int current_blocks;
-static int rgn_n_insns;
+/* A speculative motion requires checking live information on the path
+ from 'source' to 'target'. The split blocks are those to be checked.
+ After a speculative motion, live information should be modified in
+ the 'update' blocks.
+
+ Lists of split and update blocks for each candidate of the current
+ target are in array bblst_table. */
+static basic_block *bblst_table;
+static int bblst_size, bblst_last;
-/* The mapping from ebb to block. */
-/* ebb_head [i] - is index in rgn_bb_table, while
- EBB_HEAD (i) - is basic block index.
- BASIC_BLOCK (EBB_HEAD (i)) - head of ebb. */
-#define BB_TO_BLOCK(ebb) (rgn_bb_table[ebb_head[ebb]])
-#define EBB_FIRST_BB(ebb) BASIC_BLOCK (BB_TO_BLOCK (ebb))
-#define EBB_LAST_BB(ebb) BASIC_BLOCK (rgn_bb_table[ebb_head[ebb + 1] - 1])
+/* Arrays that hold the DFA state at the end of a basic block, to re-use
+ as the initial state at the start of successor blocks. The BB_STATE
+ array holds the actual DFA state, and BB_STATE_ARRAY[I] is a pointer
+ into BB_STATE for basic block I. FIXME: This should be a vec. */
+static char *bb_state_array = NULL;
+static state_t *bb_state = NULL;
/* Target info declarations.
candidate;
static candidate *candidate_table;
-
-/* A speculative motion requires checking live information on the path
- from 'source' to 'target'. The split blocks are those to be checked.
- After a speculative motion, live information should be modified in
- the 'update' blocks.
-
- Lists of split and update blocks for each candidate of the current
- target are in array bblst_table. */
-static basic_block *bblst_table;
-static int bblst_size, bblst_last;
-
-#define IS_VALID(src) ( candidate_table[src].is_valid )
-#define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
+#define IS_VALID(src) (candidate_table[src].is_valid)
+#define IS_SPECULATIVE(src) (candidate_table[src].is_speculative)
+#define IS_SPECULATIVE_INSN(INSN) \
+ (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
#define SRC_PROB(src) ( candidate_table[src].src_prob )
/* The bb being currently scheduled. */
-static int target_bb;
+int target_bb;
/* List of edges. */
typedef struct
static void extract_edgelst (sbitmap, edgelst *);
-
/* Target info functions. */
static void split_edges (int, int, edgelst *);
static void compute_trg_info (int);
/* Is bb_src dominated by bb_trg. */
#define IS_DOMINATED(bb_src, bb_trg) \
-( TEST_BIT (dom[bb_src], bb_trg) )
+( bitmap_bit_p (dom[bb_src], 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. */
/* For every bb, a set of its ancestor edges. */
static edgeset *ancestor_edges;
-/* Array of EBBs sizes. Currently we can get a ebb only through
- splitting of currently scheduling block, therefore, we don't need
- ebb_head array for every region, its sufficient to hold it only
- for current one. */
-static int *ebb_head;
-
-static void compute_dom_prob_ps (int);
-
#define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
-#define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
-#define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
/* Speculative scheduling functions. */
static int check_live_1 (int, rtx);
static void update_live_1 (int, rtx);
-static int check_live (rtx, int);
-static void update_live (rtx, int);
-static void set_spec_fed (rtx);
static int is_pfree (rtx, int, int);
-static int find_conditional_protection (rtx, int);
+static int find_conditional_protection (rtx_insn *, int);
static int is_conditionally_protected (rtx, int, int);
static int is_prisky (rtx, int, int);
-static int is_exception_free (rtx, int, int);
+static int is_exception_free (rtx_insn *, int, int);
static bool sets_likely_spilled (rtx);
static void sets_likely_spilled_1 (rtx, const_rtx, void *);
-static void add_branch_dependences (rtx, rtx);
+static void add_branch_dependences (rtx_insn *, rtx_insn *);
static void compute_block_dependences (int);
-static void init_regions (void);
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 concat_insn_mem_list (rtx_insn_list *, rtx_expr_list *,
+ rtx_insn_list **, rtx_expr_list **);
+static void propagate_deps (int, struct deps_desc *);
static void free_pending_lists (void);
/* Functions for construction of the control flow graph. */
is_cfg_nonregular (void)
{
basic_block b;
- rtx insn;
+ rtx_insn *insn;
/* If we have a label that could be the target of a nonlocal goto, then
the cfg is not well structured. */
if (current_function_has_exception_handlers ())
return 1;
- /* If we have non-jumping insns which refer to labels, then we consider
- the cfg not well structured. */
- FOR_EACH_BB (b)
+ /* If we have insns which refer to labels as non-jumped-to operands,
+ then we consider the cfg not well structured. */
+ FOR_EACH_BB_FN (b, cfun)
FOR_BB_INSNS (b, insn)
{
- /* Check for labels referred by non-jump insns. */
- if (NONJUMP_INSN_P (insn) || CALL_P (insn))
- {
- rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
- if (note
- && ! (JUMP_P (NEXT_INSN (insn))
- && find_reg_note (NEXT_INSN (insn), REG_LABEL,
- XEXP (note, 0))))
- return 1;
- }
+ rtx note, set, dest;
+ rtx_insn *next;
+
/* If this function has a computed jump, then we consider the cfg
not well structured. */
- else if (JUMP_P (insn) && computed_jump_p (insn))
+ if (JUMP_P (insn) && computed_jump_p (insn))
+ return 1;
+
+ if (!INSN_P (insn))
+ continue;
+
+ note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX);
+ if (note == NULL_RTX)
+ continue;
+
+ /* For that label not to be seen as a referred-to label, this
+ must be a single-set which is feeding a jump *only*. This
+ could be a conditional jump with the label split off for
+ machine-specific reasons or a casesi/tablejump. */
+ next = next_nonnote_insn (insn);
+ if (next == NULL_RTX
+ || !JUMP_P (next)
+ || (JUMP_LABEL (next) != XEXP (note, 0)
+ && find_reg_note (next, REG_LABEL_TARGET,
+ XEXP (note, 0)) == NULL_RTX)
+ || BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (next))
+ return 1;
+
+ set = single_set (insn);
+ if (set == NULL_RTX)
+ return 1;
+
+ dest = SET_DEST (set);
+ if (!REG_P (dest) || !dead_or_set_p (next, dest))
return 1;
}
Unreachable loops with a single block are detected here. This
test is redundant with the one in find_rgns, but it's much
cheaper to go ahead and catch the trivial case here. */
- FOR_EACH_BB (b)
+ FOR_EACH_BB_FN (b, cfun)
{
if (EDGE_COUNT (b->preds) == 0
|| (single_pred_p (b)
el->nr_members = 0;
/* Iterate over each word in the bitset. */
- EXECUTE_IF_SET_IN_SBITMAP (set, 0, i, sbi)
+ EXECUTE_IF_SET_IN_BITMAP (set, 0, i, sbi)
{
edgelst_table[edgelst_last++] = rgn_edges[i];
el->nr_members++;
/* 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. */
+
+DEBUG_FUNCTION void
+debug_region (int rgn)
+{
+ int bb;
+
+ fprintf (stderr, "\n;; ------------ REGION %d ----------\n\n", rgn);
+ fprintf (stderr, ";;\trgn %d nr_blocks %d:\n", rgn,
+ rgn_table[rgn].rgn_nr_blocks);
+ fprintf (stderr, ";;\tbb/block: ");
+
+ /* We don't have ebb_head initialized yet, so we can't use
+ BB_TO_BLOCK (). */
+ current_blocks = RGN_BLOCKS (rgn);
+
+ for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
+ fprintf (stderr, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
+
+ fprintf (stderr, "\n\n");
+
+ for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
+ {
+ dump_bb (stderr,
+ BASIC_BLOCK_FOR_FN (cfun, rgn_bb_table[current_blocks + bb]),
+ 0, TDF_SLIM | TDF_BLOCKS);
+ fprintf (stderr, "\n");
+ }
+
+ fprintf (stderr, "\n");
+
+}
+
+/* True when a bb with index BB_INDEX contained in region RGN. */
+static bool
+bb_in_region_p (int bb_index, int rgn)
+{
+ int i;
+
+ for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
+ if (rgn_bb_table[current_blocks + i] == bb_index)
+ return true;
+
+ return false;
+}
+
+/* Dump region RGN to file F using dot syntax. */
+void
+dump_region_dot (FILE *f, int rgn)
+{
+ int i;
+
+ fprintf (f, "digraph Region_%d {\n", rgn);
+
+ /* We don't have ebb_head initialized yet, so we can't use
+ BB_TO_BLOCK (). */
+ current_blocks = RGN_BLOCKS (rgn);
+
+ for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
+ {
+ edge e;
+ edge_iterator ei;
+ int src_bb_num = rgn_bb_table[current_blocks + i];
+ basic_block bb = BASIC_BLOCK_FOR_FN (cfun, src_bb_num);
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (bb_in_region_p (e->dest->index, rgn))
+ fprintf (f, "\t%d -> %d\n", src_bb_num, e->dest->index);
+ }
+ fprintf (f, "}\n");
+}
+
+/* The same, but first open a file specified by FNAME. */
+void
+dump_region_dot_file (const char *fname, int rgn)
+{
+ FILE *f = fopen (fname, "wt");
+ dump_region_dot (f, rgn);
+ fclose (f);
+}
+
/* Build a single block region for each basic block in the function.
This allows for using the same code for interblock and basic block
scheduling. */
static void
-find_single_block_region (void)
+find_single_block_region (bool ebbs_p)
{
- basic_block bb;
+ basic_block bb, ebb_start;
+ int i = 0;
nr_regions = 0;
- FOR_EACH_BB (bb)
+ if (ebbs_p) {
+ int probability_cutoff;
+ if (profile_info && flag_branch_probabilities)
+ probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
+ else
+ probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
+ probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
+
+ FOR_EACH_BB_FN (ebb_start, cfun)
+ {
+ RGN_NR_BLOCKS (nr_regions) = 0;
+ RGN_BLOCKS (nr_regions) = i;
+ RGN_DONT_CALC_DEPS (nr_regions) = 0;
+ RGN_HAS_REAL_EBB (nr_regions) = 0;
+
+ for (bb = ebb_start; ; bb = bb->next_bb)
+ {
+ edge e;
+
+ rgn_bb_table[i] = bb->index;
+ RGN_NR_BLOCKS (nr_regions)++;
+ CONTAINING_RGN (bb->index) = nr_regions;
+ BLOCK_TO_BB (bb->index) = i - RGN_BLOCKS (nr_regions);
+ i++;
+
+ if (bb->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
+ || LABEL_P (BB_HEAD (bb->next_bb)))
+ break;
+
+ e = find_fallthru_edge (bb->succs);
+ if (! e)
+ break;
+ if (e->probability <= probability_cutoff)
+ break;
+ }
+
+ ebb_start = bb;
+ nr_regions++;
+ }
+ }
+ else
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ rgn_bb_table[nr_regions] = bb->index;
+ RGN_NR_BLOCKS (nr_regions) = 1;
+ RGN_BLOCKS (nr_regions) = nr_regions;
+ RGN_DONT_CALC_DEPS (nr_regions) = 0;
+ RGN_HAS_REAL_EBB (nr_regions) = 0;
+
+ CONTAINING_RGN (bb->index) = nr_regions;
+ BLOCK_TO_BB (bb->index) = 0;
+ nr_regions++;
+ }
+}
+
+/* Estimate number of the insns in the BB. */
+static int
+rgn_estimate_number_of_insns (basic_block bb)
+{
+ int count;
+
+ count = INSN_LUID (BB_END (bb)) - INSN_LUID (BB_HEAD (bb));
+
+ if (MAY_HAVE_DEBUG_INSNS)
{
- rgn_bb_table[nr_regions] = bb->index;
- RGN_NR_BLOCKS (nr_regions) = 1;
- RGN_BLOCKS (nr_regions) = nr_regions;
- RGN_DONT_CALC_DEPS (nr_regions) = 0;
- RGN_HAS_REAL_EBB (nr_regions) = 0;
- CONTAINING_RGN (bb->index) = nr_regions;
- BLOCK_TO_BB (bb->index) = 0;
- nr_regions++;
+ rtx_insn *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
too_large (int block, int *num_bbs, int *num_insns)
{
(*num_bbs)++;
- (*num_insns) += (INSN_LUID (BB_END (BASIC_BLOCK (block)))
- - INSN_LUID (BB_HEAD (BASIC_BLOCK (block))));
+ (*num_insns) += (common_sched_info->estimate_number_of_insns
+ (BASIC_BLOCK_FOR_FN (cfun, block)));
return ((*num_bbs > PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS))
|| (*num_insns > PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS)));
if (max_hdr[blk] == -1) \
max_hdr[blk] = hdr; \
else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
- RESET_BIT (inner, hdr); \
+ bitmap_clear_bit (inner, hdr); \
else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
{ \
- RESET_BIT (inner,max_hdr[blk]); \
+ bitmap_clear_bit (inner,max_hdr[blk]); \
max_hdr[blk] = hdr; \
} \
}
of edge tables. That would simplify it somewhat. */
static void
-find_rgns (void)
+haifa_find_rgns (void)
{
int *max_hdr, *dfs_nr, *degree;
char no_loops = 1;
STACK, SP and DFS_NR are only used during the first traversal. */
/* Allocate and initialize variables for the first traversal. */
- max_hdr = XNEWVEC (int, last_basic_block);
- dfs_nr = XCNEWVEC (int, last_basic_block);
- stack = XNEWVEC (edge_iterator, n_edges);
+ max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
+ dfs_nr = XCNEWVEC (int, last_basic_block_for_fn (cfun));
+ stack = XNEWVEC (edge_iterator, n_edges_for_fn (cfun));
- inner = sbitmap_alloc (last_basic_block);
- sbitmap_ones (inner);
+ inner = sbitmap_alloc (last_basic_block_for_fn (cfun));
+ bitmap_ones (inner);
- header = sbitmap_alloc (last_basic_block);
- sbitmap_zero (header);
+ header = sbitmap_alloc (last_basic_block_for_fn (cfun));
+ bitmap_clear (header);
- in_queue = sbitmap_alloc (last_basic_block);
- sbitmap_zero (in_queue);
+ in_queue = sbitmap_alloc (last_basic_block_for_fn (cfun));
+ bitmap_clear (in_queue);
- in_stack = sbitmap_alloc (last_basic_block);
- sbitmap_zero (in_stack);
+ in_stack = sbitmap_alloc (last_basic_block_for_fn (cfun));
+ bitmap_clear (in_stack);
- for (i = 0; i < last_basic_block; i++)
+ for (i = 0; i < last_basic_block_for_fn (cfun); i++)
max_hdr[i] = -1;
#define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
/* DFS traversal to find inner loops in the cfg. */
- current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR)->succs);
+ current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))->succs);
sp = -1;
while (1)
gcc_assert (node != ENTRY_BLOCK);
child = ei_edge (current_edge)->dest->index;
gcc_assert (child != EXIT_BLOCK);
- RESET_BIT (in_stack, child);
- if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
+ bitmap_clear_bit (in_stack, child);
+ if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
ei_next (¤t_edge);
}
/* Process a node. */
node = ei_edge (current_edge)->src->index;
gcc_assert (node != ENTRY_BLOCK);
- SET_BIT (in_stack, node);
+ bitmap_set_bit (in_stack, node);
dfs_nr[node] = ++count;
/* We don't traverse to the exit block. */
/* If the successor is in the stack, then we've found a loop.
Mark the loop, if it is not a natural loop, then it will
be rejected during the second traversal. */
- if (TEST_BIT (in_stack, child))
+ if (bitmap_bit_p (in_stack, child))
{
no_loops = 0;
- SET_BIT (header, child);
+ bitmap_set_bit (header, child);
UPDATE_LOOP_RELATIONS (node, child);
SET_EDGE_PASSED (current_edge);
ei_next (¤t_edge);
with a new edge. */
if (dfs_nr[child])
{
- if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
+ if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
SET_EDGE_PASSED (current_edge);
ei_next (¤t_edge);
}
/* Reset ->aux field used by EDGE_PASSED. */
- FOR_ALL_BB (bb)
+ FOR_ALL_BB_FN (bb, cfun)
{
edge_iterator ei;
edge e;
the entry node by placing a nonzero value in dfs_nr. Thus if
dfs_nr is zero for any block, then it must be unreachable. */
unreachable = 0;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
if (dfs_nr[bb->index] == 0)
{
unreachable = 1;
to hold degree counts. */
degree = dfs_nr;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
degree[bb->index] = EDGE_COUNT (bb->preds);
/* Do not perform region scheduling if there are any unreachable
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;
if (no_loops)
- SET_BIT (header, 0);
+ bitmap_set_bit (header, 0);
/* Second traversal:find reducible inner loops and topologically sort
block of each region. */
- queue = XNEWVEC (int, n_basic_blocks);
-
+ queue = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+
extend_regions_p = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS) > 0;
if (extend_regions_p)
{
- degree1 = xmalloc (last_basic_block * sizeof (int));
- extended_rgn_header = sbitmap_alloc (last_basic_block);
- sbitmap_zero (extended_rgn_header);
+ degree1 = XNEWVEC (int, last_basic_block_for_fn (cfun));
+ extended_rgn_header =
+ sbitmap_alloc (last_basic_block_for_fn (cfun));
+ bitmap_clear (extended_rgn_header);
}
/* Find blocks which are inner loop headers. We still have non-reducible
loops to consider at this point. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
- if (TEST_BIT (header, bb->index) && TEST_BIT (inner, bb->index))
+ if (bitmap_bit_p (header, bb->index) && bitmap_bit_p (inner, bb->index))
{
edge e;
edge_iterator ei;
If there exists a block that is not dominated by the loop
header, then the block is reachable from outside the loop
and thus the loop is not a natural loop. */
- FOR_EACH_BB (jbb)
+ FOR_EACH_BB_FN (jbb, cfun)
{
/* First identify blocks in the loop, except for the loop
entry block. */
/* If we exited the loop early, then I is the header of
a non-reducible loop and we should quit processing it
now. */
- if (jbb != EXIT_BLOCK_PTR)
+ if (jbb != EXIT_BLOCK_PTR_FOR_FN (cfun))
continue;
/* I is a header of an inner loop, or block 0 in a subroutine
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));
-
+ memcpy (degree1, degree,
+ last_basic_block_for_fn (cfun) * sizeof (int));
+
/* Decrease degree of all I's successors for topological
ordering. */
FOR_EACH_EDGE (e, ei, bb->succs)
- if (e->dest != EXIT_BLOCK_PTR)
+ if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
--degree[e->dest->index];
/* Estimate # insns, and count # blocks in the region. */
num_bbs = 1;
- num_insns = (INSN_LUID (BB_END (bb))
- - INSN_LUID (BB_HEAD (bb)));
+ num_insns = common_sched_info->estimate_number_of_insns (bb);
/* Find all loop latches (blocks with back edges to the loop
header) or all the leaf blocks in the cfg has no loops.
Place those blocks into the queue. */
if (no_loops)
{
- FOR_EACH_BB (jbb)
+ FOR_EACH_BB_FN (jbb, cfun)
/* Leaf nodes have only a single successor which must
be EXIT_BLOCK. */
if (single_succ_p (jbb)
- && single_succ (jbb) == EXIT_BLOCK_PTR)
+ && single_succ (jbb) == EXIT_BLOCK_PTR_FOR_FN (cfun))
{
queue[++tail] = jbb->index;
- SET_BIT (in_queue, jbb->index);
+ bitmap_set_bit (in_queue, jbb->index);
if (too_large (jbb->index, &num_bbs, &num_insns))
{
FOR_EACH_EDGE (e, ei, bb->preds)
{
- if (e->src == ENTRY_BLOCK_PTR)
+ if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
continue;
node = e->src->index;
{
/* This is a loop latch. */
queue[++tail] = node;
- SET_BIT (in_queue, node);
+ bitmap_set_bit (in_queue, node);
if (too_large (node, &num_bbs, &num_insns))
{
edge e;
child = queue[++head];
- FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->preds)
+ FOR_EACH_EDGE (e, ei,
+ BASIC_BLOCK_FOR_FN (cfun, child)->preds)
{
node = e->src->index;
/* See discussion above about nodes not marked as in
this loop during the initial DFS traversal. */
- if (e->src == ENTRY_BLOCK_PTR
+ if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
|| max_hdr[node] != loop_head)
{
tail = -1;
break;
}
- else if (!TEST_BIT (in_queue, node) && node != bb->index)
+ else if (!bitmap_bit_p (in_queue, node) && node != bb->index)
{
queue[++tail] = node;
- SET_BIT (in_queue, node);
+ bitmap_set_bit (in_queue, node);
if (too_large (node, &num_bbs, &num_insns))
{
CONTAINING_RGN (child) = nr_regions;
queue[head] = queue[tail--];
- FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->succs)
- if (e->dest != EXIT_BLOCK_PTR)
+ FOR_EACH_EDGE (e, ei,
+ BASIC_BLOCK_FOR_FN (cfun,
+ child)->succs)
+ if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
--degree[e->dest->index];
}
else
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. */
FOR_EACH_EDGE (e, ei, bb->succs)
- if (e->dest != EXIT_BLOCK_PTR)
- SET_BIT (extended_rgn_header, e->dest->index);
+ if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
+ bitmap_set_bit (extended_rgn_header, e->dest->index);
}
}
}
if (extend_regions_p)
{
free (degree1);
-
- sbitmap_a_or_b (header, header, extended_rgn_header);
+
+ bitmap_ior (header, header, extended_rgn_header);
sbitmap_free (extended_rgn_header);
-
+
extend_rgns (degree, &idx, header, max_hdr);
}
}
/* Any block that did not end up in a region is placed into a region
by itself. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
if (degree[bb->index] >= 0)
{
rgn_bb_table[idx] = bb->index;
sbitmap_free (in_stack);
}
+
+/* Wrapper function.
+ If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
+ regions. Otherwise just call find_rgns_haifa. */
+static void
+find_rgns (void)
+{
+ if (sel_sched_p () && flag_sel_sched_pipelining)
+ sel_find_rgns ();
+ else
+ haifa_find_rgns ();
+}
+
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 = xrealloc (a, nr_blocks * sizeof (*a));
+ {
+ a = XRESIZEVEC (int, a, nr_blocks);
do
a[a_sz++] = 0;
while (a_sz != nr_blocks);
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++)
{
LOOP_HDR - mapping from block to the containing loop
(two blocks can reside within one region if they have
the same loop header). */
-static void
+void
extend_rgns (int *degree, int *idxp, sbitmap header, int *loop_hdr)
{
int *order, i, rescan = 0, idx = *idxp, iter = 0, max_iter, *max_hdr;
- int nblocks = n_basic_blocks - NUM_FIXED_BLOCKS;
+ int nblocks = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
max_iter = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS);
- max_hdr = xmalloc (last_basic_block * sizeof (*max_hdr));
+ max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
- order = xmalloc (last_basic_block * sizeof (*order));
+ order = XNEWVEC (int, last_basic_block_for_fn (cfun));
post_order_compute (order, false, false);
for (i = nblocks - 1; i >= 0; 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
- set of all basic blocks, thus the algorithm is guaranteed to terminate. */
+ 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))
+
+ if (max_hdr[bbn] != -1 && !bitmap_bit_p (header, bbn))
{
int hdr = -1;
- FOR_EACH_EDGE (e, ei, BASIC_BLOCK (bbn)->preds)
+ FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->preds)
{
int predn = e->src->index;
{
hdr = bbn;
break;
- }
+ }
}
else
/* BB starts its own region. */
{
hdr = bbn;
break;
- }
+ }
}
-
+
if (hdr == bbn)
{
/* If BB start its own region,
update set of headers with BB. */
- SET_BIT (header, bbn);
+ bitmap_set_bit (header, bbn);
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;
CONTAINING_RGN (bbn) = nr_regions;
BLOCK_TO_BB (bbn) = 0;
- FOR_EACH_EDGE (e, ei, BASIC_BLOCK (bbn)->succs)
- if (e->dest != EXIT_BLOCK_PTR)
+ FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->succs)
+ if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
degree[e->dest->index]--;
if (!large)
{
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)
+
+ FOR_EACH_EDGE (e, ei,
+ BASIC_BLOCK_FOR_FN (cfun, succn)->succs)
+ if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
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);
+ bitmap_set_bit (dom[bb], 0);
prob[bb] = REG_BR_PROB_BASE;
return;
}
prob[bb] = 0;
/* Initialize dom[bb] to '111..1'. */
- sbitmap_ones (dom[bb]);
+ bitmap_ones (dom[bb]);
- FOR_EACH_EDGE (in_edge, in_ei, BASIC_BLOCK (BB_TO_BLOCK (bb))->preds)
+ FOR_EACH_EDGE (in_edge, in_ei,
+ BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb))->preds)
{
int pred_bb;
edge out_edge;
edge_iterator out_ei;
- if (in_edge->src == ENTRY_BLOCK_PTR)
+ if (in_edge->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
continue;
pred_bb = BLOCK_TO_BB (in_edge->src->index);
- sbitmap_a_and_b (dom[bb], dom[bb], dom[pred_bb]);
- sbitmap_a_or_b (ancestor_edges[bb],
+ bitmap_and (dom[bb], dom[bb], dom[pred_bb]);
+ bitmap_ior (ancestor_edges[bb],
ancestor_edges[bb], ancestor_edges[pred_bb]);
- SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
+ bitmap_set_bit (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
- sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
+ bitmap_ior (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
- SET_BIT (pot_split[bb], EDGE_TO_BIT (out_edge));
-
- prob[bb] += ((prob[pred_bb] * in_edge->probability) / REG_BR_PROB_BASE);
+ bitmap_set_bit (pot_split[bb], EDGE_TO_BIT (out_edge));
+
+ prob[bb] += combine_probabilities (prob[pred_bb], in_edge->probability);
+ // The rounding divide in combine_probabilities can result in an extra
+ // probability increment propagating along 50-50 edges. Eventually when
+ // the edges re-merge, the accumulated probability can go slightly above
+ // REG_BR_PROB_BASE.
+ if (prob[bb] > REG_BR_PROB_BASE)
+ prob[bb] = REG_BR_PROB_BASE;
}
- SET_BIT (dom[bb], bb);
- sbitmap_difference (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
+ bitmap_set_bit (dom[bb], bb);
+ bitmap_and_compl (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
if (sched_verbose >= 2)
fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
static void
split_edges (int bb_src, int bb_trg, edgelst *bl)
{
- sbitmap src = sbitmap_alloc (pot_split[bb_src]->n_bits);
- sbitmap_copy (src, pot_split[bb_src]);
+ sbitmap src = sbitmap_alloc (SBITMAP_SIZE (pot_split[bb_src]));
+ bitmap_copy (src, pot_split[bb_src]);
- sbitmap_difference (src, src, pot_split[bb_trg]);
+ bitmap_and_compl (src, src, pot_split[bb_trg]);
extract_edgelst (src, bl);
sbitmap_free (src);
}
compute_trg_info (int trg)
{
candidate *sp;
- edgelst el;
+ edgelst el = { NULL, 0 };
int i, j, k, update_idx;
basic_block block;
sbitmap visited;
edge_iterator ei;
edge e;
+ candidate_table = XNEWVEC (candidate, current_nr_blocks);
+
+ bblst_last = 0;
+ /* bblst_table holds split blocks and update blocks for each block after
+ the current one in the region. split blocks and update blocks are
+ 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 = XNEWVEC (basic_block, bblst_size);
+
+ edgelst_last = 0;
+ edgelst_table = XNEWVEC (edge, rgn_nr_edges);
+
/* Define some of the fields for the target bb as well. */
sp = candidate_table + trg;
sp->is_valid = 1;
sp->is_speculative = 0;
sp->src_prob = REG_BR_PROB_BASE;
- visited = sbitmap_alloc (last_basic_block);
+ visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
for (i = trg + 1; i < current_nr_blocks; i++)
{
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->src_prob = (tf ? GCOV_COMPUTE_SCALE (cf, tf) : 0);
sp->is_valid = (sp->src_prob >= min_spec_prob);
}
overrunning the end of the bblst_table. */
update_idx = 0;
- sbitmap_zero (visited);
+ bitmap_clear (visited);
for (j = 0; j < el.nr_members; j++)
{
block = el.first_member[j]->src;
FOR_EACH_EDGE (e, ei, block->succs)
{
- if (!TEST_BIT (visited, e->dest->index))
+ if (!bitmap_bit_p (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);
+ bitmap_set_bit (visited, e->dest->index);
update_idx++;
}
}
sbitmap_free (visited);
}
+/* Free the computed target info. */
+static void
+free_trg_info (void)
+{
+ free (candidate_table);
+ free (bblst_table);
+ free (edgelst_table);
+}
+
/* 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;
if (regno < FIRST_PSEUDO_REGISTER)
{
/* Check for hard registers. */
- int j = hard_regno_nregs[regno][GET_MODE (reg)];
+ int j = REG_NREGS (reg);
while (--j >= 0)
{
for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
int t = bitmap_bit_p (¬_in_df, b->index);
/* We can have split blocks, that were recently generated.
- such blocks are always outside current region. */
+ Such blocks are always outside current region. */
gcc_assert (!t || (CONTAINING_RGN (b->index)
!= CONTAINING_RGN (BB_TO_BLOCK (src))));
regno = REGNO (reg);
- if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
+ if (! HARD_REGISTER_NUM_P (regno)
+ || !global_regs[regno])
{
- if (regno < FIRST_PSEUDO_REGISTER)
- {
- int j = hard_regno_nregs[regno][GET_MODE (reg)];
- while (--j >= 0)
- {
- for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
- {
- basic_block b = candidate_table[src].update_bbs.first_member[i];
-
- SET_REGNO_REG_SET (df_get_live_in (b), regno + j);
- }
- }
- }
- else
+ for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
{
- for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
- {
- basic_block b = candidate_table[src].update_bbs.first_member[i];
-
- SET_REGNO_REG_SET (df_get_live_in (b), regno);
- }
+ basic_block b = candidate_table[src].update_bbs.first_member[i];
+ bitmap_set_range (df_get_live_in (b), regno, REG_NREGS (reg));
}
}
}
ready-list or before the scheduling. */
static int
-check_live (rtx insn, int src)
+check_live (rtx_insn *insn, int src)
{
/* Find the registers set by instruction. */
if (GET_CODE (PATTERN (insn)) == SET
block src to trg. */
static void
-update_live (rtx insn, int src)
+update_live (rtx_insn *insn, int src)
{
/* Find the registers set by instruction. */
if (GET_CODE (PATTERN (insn)) == SET
#define IS_REACHABLE(bb_from, bb_to) \
(bb_from == bb_to \
|| IS_RGN_ENTRY (bb_from) \
- || (TEST_BIT (ancestor_edges[bb_to], \
- EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK (BB_TO_BLOCK (bb_from)))))))
+ || (bitmap_bit_p (ancestor_edges[bb_to], \
+ EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK_FOR_FN (cfun, \
+ BB_TO_BLOCK (bb_from)))))))
/* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
branch depending on insn, that guards the speculative load. */
static int
-find_conditional_protection (rtx insn, int load_insn_bb)
+find_conditional_protection (rtx_insn *insn, int load_insn_bb)
{
sd_iterator_def sd_it;
dep_t dep;
/* Iterate through DEF-USE forward dependences. */
FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
{
- rtx next = DEP_CON (dep);
+ rtx_insn *next = DEP_CON (dep);
if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
/* Returns 1 if the same insn1 that participates in the computation
of load_insn's address is feeding a conditional branch that is
- guarding on load_insn. This is true if we find a the two DEF-USE
+ guarding on load_insn. This is true if we find two DEF-USE
chains:
insn1 -> ... -> conditional-branch
insn1 -> ... -> load_insn,
- and if a flow path exist:
+ and if a flow path exists:
insn1 -> ... -> conditional-branch -> ... -> load_insn,
and if insn1 is on the path
region-entry -> ... -> bb_trg -> ... load_insn.
FOR_EACH_DEP (load_insn, SD_LIST_BACK, sd_it, dep)
{
- rtx insn1 = DEP_PRO (dep);
+ rtx_insn *insn1 = DEP_PRO (dep);
/* Must be a DEF-USE dependence upon non-branch. */
if (DEP_TYPE (dep) != REG_DEP_TRUE
FOR_EACH_DEP (load_insn, SD_LIST_BACK, back_sd_it, back_dep)
{
- rtx insn1 = DEP_PRO (back_dep);
+ rtx_insn *insn1 = DEP_PRO (back_dep);
if (DEP_TYPE (back_dep) == REG_DEP_TRUE)
/* Found a DEF-USE dependence (insn1, load_insn). */
FOR_EACH_DEP (insn1, SD_LIST_FORW, fore_sd_it, fore_dep)
{
- rtx insn2 = DEP_CON (fore_dep);
+ rtx_insn *insn2 = DEP_CON (fore_dep);
if (DEP_TYPE (fore_dep) == REG_DEP_TRUE)
{
and 0 otherwise. */
static int
-is_exception_free (rtx insn, int bb_src, int bb_trg)
+is_exception_free (rtx_insn *insn, int bb_src, int bb_trg)
{
int insn_class = haifa_classify_insn (insn);
/* Implementations of the sched_info functions for region scheduling. */
static void init_ready_list (void);
-static int can_schedule_ready_p (rtx);
-static void begin_schedule_ready (rtx, rtx);
-static ds_t new_ready (rtx, ds_t);
+static int can_schedule_ready_p (rtx_insn *);
+static void begin_schedule_ready (rtx_insn *);
+static ds_t new_ready (rtx_insn *, ds_t);
static int schedule_more_p (void);
-static const char *rgn_print_insn (rtx, int);
-static int rgn_rank (rtx, rtx);
-static int contributes_to_priority (rtx, rtx);
-static void compute_jump_reg_dependencies (rtx, regset, regset, regset);
+static const char *rgn_print_insn (const rtx_insn *, int);
+static int rgn_rank (rtx_insn *, rtx_insn *);
+static void compute_jump_reg_dependencies (rtx, regset);
/* Functions for speculative scheduling. */
-static void add_remove_insn (rtx, int);
-static void extend_regions (void);
-static void add_block1 (basic_block, basic_block);
-static void fix_recovery_cfg (int, int, int);
-static basic_block advance_target_bb (basic_block, rtx);
-
-static void debug_rgn_dependencies (int);
+static void rgn_add_remove_insn (rtx_insn *, int);
+static void rgn_add_block (basic_block, basic_block);
+static void rgn_fix_recovery_cfg (int, int, int);
+static basic_block advance_target_bb (basic_block, rtx_insn *);
/* Return nonzero if there are more insns that should be scheduled. */
static void
init_ready_list (void)
{
- rtx prev_head = current_sched_info->prev_head;
- rtx next_tail = current_sched_info->next_tail;
+ rtx_insn *prev_head = current_sched_info->prev_head;
+ rtx_insn *next_tail = current_sched_info->next_tail;
int bb_src;
- rtx insn;
+ rtx_insn *insn;
target_n_insns = 0;
sched_target_n_insns = 0;
/* Prepare current target block info. */
if (current_nr_blocks > 1)
- {
- candidate_table = XNEWVEC (candidate, current_nr_blocks);
-
- bblst_last = 0;
- /* bblst_table holds split blocks and update blocks for each block after
- the current one in the region. split blocks and update blocks are
- 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 = XNEWVEC (basic_block, bblst_size);
-
- edgelst_last = 0;
- edgelst_table = XNEWVEC (edge, rgn_nr_edges);
-
- compute_trg_info (target_bb);
- }
+ compute_trg_info (target_bb);
/* 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))
- {
+ {
+ gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
+ TODO_SPEC (insn) = HARD_DEP;
try_ready (insn);
target_n_insns++;
for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
if (IS_VALID (bb_src))
{
- rtx src_head;
- rtx src_next_tail;
- rtx tail, head;
+ rtx_insn *src_head;
+ rtx_insn *src_next_tail;
+ rtx_insn *tail, *head;
get_ebb_head_tail (EBB_FIRST_BB (bb_src), EBB_LAST_BB (bb_src),
&head, &tail);
for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
if (INSN_P (insn))
- try_ready (insn);
+ {
+ gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
+ TODO_SPEC (insn) = HARD_DEP;
+ try_ready (insn);
+ }
}
}
insn can be scheduled, nonzero if we should silently discard it. */
static int
-can_schedule_ready_p (rtx insn)
+can_schedule_ready_p (rtx_insn *insn)
{
/* An interblock motion? */
if (INSN_BB (insn) != target_bb
&& IS_SPECULATIVE_INSN (insn)
&& !check_live (insn, INSN_BB (insn)))
- return 0;
+ return 0;
else
return 1;
}
can_schedule_ready_p () differs from the one passed to
begin_schedule_ready (). */
static void
-begin_schedule_ready (rtx insn, rtx last ATTRIBUTE_UNUSED)
+begin_schedule_ready (rtx_insn *insn)
{
/* An interblock motion? */
if (INSN_BB (insn) != target_bb)
Return nonzero if it should be moved to the ready list or the queue, or zero
if we should silently discard it. */
static ds_t
-new_ready (rtx next, ds_t ts)
+new_ready (rtx_insn *next, ds_t ts)
{
if (INSN_BB (next) != target_bb)
{
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))
if (not_ex_free
/* We are here because is_exception_free () == false.
But we possibly can handle that with control speculation. */
- && (current_sched_info->flags & DO_SPECULATION)
- && (spec_info->mask & BEGIN_CONTROL))
- /* Here we got new control-speculative instruction. */
- ts = set_dep_weak (ts, BEGIN_CONTROL, MAX_DEP_WEAK);
+ && sched_deps_info->generate_spec_deps
+ && spec_info->mask & BEGIN_CONTROL)
+ {
+ ds_t new_ds;
+
+ /* Add control speculation to NEXT's dependency type. */
+ new_ds = set_dep_weak (ts, BEGIN_CONTROL, MAX_DEP_WEAK);
+
+ /* Check if NEXT can be speculated with new dependency type. */
+ if (sched_insn_is_legitimate_for_speculation_p (next, new_ds))
+ /* Here we got new control-speculative instruction. */
+ ts = new_ds;
+ else
+ /* NEXT isn't ready yet. */
+ ts = DEP_POSTPONED;
+ }
else
- ts = (ts & ~SPECULATIVE) | HARD_DEP;
+ /* NEXT isn't ready yet. */
+ ts = DEP_POSTPONED;
}
}
-
+
return ts;
}
to be formatted so that multiple output lines will line up nicely. */
static const char *
-rgn_print_insn (rtx insn, int aligned)
+rgn_print_insn (const rtx_insn *insn, int aligned)
{
static char tmp[80];
is to be preferred. Zero if they are equally good. */
static int
-rgn_rank (rtx insn1, rtx insn2)
+rgn_rank (rtx_insn *insn1, rtx_insn *insn2)
{
/* Some comparison make sense in interblock scheduling only. */
if (INSN_BB (insn1) != INSN_BB (insn2))
return nonzero if we should include this dependence in priority
calculations. */
-static int
-contributes_to_priority (rtx next, rtx insn)
+int
+contributes_to_priority (rtx_insn *next, rtx_insn *insn)
{
/* NEXT and INSN reside in one ebb. */
return BLOCK_TO_BB (BLOCK_NUM (next)) == BLOCK_TO_BB (BLOCK_NUM (insn));
}
-/* INSN is a JUMP_INSN, COND_SET is the set of registers that are
- conditionally set before INSN. Store the set of registers that
- must be considered as used by this jump in USED and that of
- registers that must be considered as set in SET. */
+/* INSN is a JUMP_INSN. Store the set of registers that must be
+ considered as used by this jump in USED. */
static void
compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
- regset cond_exec ATTRIBUTE_UNUSED,
- regset used ATTRIBUTE_UNUSED,
- regset set ATTRIBUTE_UNUSED)
+ regset used ATTRIBUTE_UNUSED)
{
/* Nothing to do here, since we postprocess jumps in
add_branch_dependences. */
}
+/* This variable holds common_sched_info hooks and data relevant to
+ the interblock scheduler. */
+static struct common_sched_info_def rgn_common_sched_info;
+
+
+/* This holds data for the dependence analysis relevant to
+ the interblock scheduler. */
+static struct sched_deps_info_def rgn_sched_deps_info;
+
+/* This holds constant data used for initializing the above structure
+ for the Haifa scheduler. */
+static const struct sched_deps_info_def rgn_const_sched_deps_info =
+ {
+ compute_jump_reg_dependencies,
+ NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
+ 0, 0, 0
+ };
+
+/* Same as above, but for the selective scheduler. */
+static const struct sched_deps_info_def rgn_const_sel_sched_deps_info =
+ {
+ compute_jump_reg_dependencies,
+ NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
+ 0, 0, 0
+ };
+
+/* Return true if scheduling INSN will trigger finish of scheduling
+ current block. */
+static bool
+rgn_insn_finishes_block_p (rtx_insn *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). */
-static struct sched_info region_sched_info =
+static const struct haifa_sched_info rgn_const_sched_info =
{
init_ready_list,
can_schedule_ready_p,
rgn_rank,
rgn_print_insn,
contributes_to_priority,
- compute_jump_reg_dependencies,
+ rgn_insn_finishes_block_p,
NULL, NULL,
NULL, NULL,
- 0, 0, 0,
+ 0, 0,
- add_remove_insn,
+ rgn_add_remove_insn,
begin_schedule_ready,
- add_block1,
+ NULL,
advance_target_bb,
- fix_recovery_cfg,
+ NULL, NULL,
SCHED_RGN
};
-/* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register. */
+/* This variable holds the data and hooks needed to the Haifa scheduler backend
+ for the interblock scheduler frontend. */
+static struct haifa_sched_info rgn_sched_info;
+
+/* Returns maximum priority that an insn was assigned to. */
+
+int
+get_rgn_sched_max_insns_priority (void)
+{
+ return rgn_sched_info.sched_max_insns_priority;
+}
+
+/* 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;
}
+/* A bitmap to note insns that participate in any dependency. Used in
+ add_branch_dependences. */
+static sbitmap insn_referenced;
+
/* Add dependences so that branches are scheduled to run last in their
block. */
-
static void
-add_branch_dependences (rtx head, rtx tail)
+add_branch_dependences (rtx_insn *head, rtx_insn *tail)
{
- rtx insn, last;
+ rtx_insn *insn, *last;
/* For all branches, calls, uses, clobbers, cc0 setters, and instructions
that can throw exceptions, force them to remain in order at the end of
cc0 setters remain at the end because they can't be moved away from
their cc0 user.
+ Predecessors of SCHED_GROUP_P instructions at the end remain at the end.
+
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)
- || JUMP_P (insn)
+ || JUMP_P (insn) || JUMP_TABLE_DATA_P (insn)
|| (NONJUMP_INSN_P (insn)
&& (GET_CODE (PATTERN (insn)) == USE
|| GET_CODE (PATTERN (insn)) == CLOBBER
|| can_throw_internal (insn)
-#ifdef HAVE_cc0
- || sets_cc0_p (PATTERN (insn))
-#endif
+ || (HAVE_cc0 && sets_cc0_p (PATTERN (insn)))
|| (!reload_completed
&& sets_likely_spilled (PATTERN (insn)))))
- || NOTE_P (insn))
+ || NOTE_P (insn)
+ || (last != 0 && SCHED_GROUP_P (last)))
{
if (!NOTE_P (insn))
{
{
if (! sched_insns_conditions_mutex_p (last, insn))
add_dependence (last, insn, REG_DEP_ANTI);
- INSN_REF_COUNT (insn)++;
+ bitmap_set_bit (insn_referenced, INSN_LUID (insn));
}
CANT_MOVE (insn) = 1;
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 (INSN_REF_COUNT (insn) != 0)
+ if (bitmap_bit_p (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);
- INSN_REF_COUNT (insn) = 1;
}
-#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.
possible improvement for handling COND_EXECs in this scheduler: it
could remove always-true predicates. */
- if (!reload_completed || ! JUMP_P (tail))
+ if (!reload_completed || ! (JUMP_P (tail) || JUMP_TABLE_DATA_P (tail)))
return;
insn = tail;
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;
-
-/* Duplicate the INSN_LIST elements of COPY and prepend them to OLD. */
-
-static rtx
-concat_INSN_LIST (rtx copy, rtx old)
-{
- rtx new = old;
- for (; copy ; copy = XEXP (copy, 1))
- new = alloc_INSN_LIST (XEXP (copy, 0), new);
- return new;
-}
+static struct deps_desc *bb_deps;
static void
-concat_insn_mem_list (rtx copy_insns, rtx copy_mems, rtx *old_insns_p,
- rtx *old_mems_p)
+concat_insn_mem_list (rtx_insn_list *copy_insns,
+ rtx_expr_list *copy_mems,
+ rtx_insn_list **old_insns_p,
+ rtx_expr_list **old_mems_p)
{
- rtx new_insns = *old_insns_p;
- rtx new_mems = *old_mems_p;
+ rtx_insn_list *new_insns = *old_insns_p;
+ rtx_expr_list *new_mems = *old_mems_p;
while (copy_insns)
{
- new_insns = alloc_INSN_LIST (XEXP (copy_insns, 0), new_insns);
- new_mems = alloc_EXPR_LIST (VOIDmode, XEXP (copy_mems, 0), new_mems);
- copy_insns = XEXP (copy_insns, 1);
- copy_mems = XEXP (copy_mems, 1);
+ new_insns = alloc_INSN_LIST (copy_insns->insn (), new_insns);
+ new_mems = alloc_EXPR_LIST (VOIDmode, copy_mems->element (), new_mems);
+ copy_insns = copy_insns->next ();
+ copy_mems = copy_mems->next ();
}
*old_insns_p = new_insns;
*old_mems_p = new_mems;
}
+/* Join PRED_DEPS to the SUCC_DEPS. */
+void
+deps_join (struct deps_desc *succ_deps, struct deps_desc *pred_deps)
+{
+ unsigned reg;
+ reg_set_iterator rsi;
+
+ /* The reg_last lists are inherited by successor. */
+ EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi)
+ {
+ struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
+ struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
+
+ 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;
+ succ_rl->clobbers_length += pred_rl->clobbers_length;
+ }
+ IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
+
+ /* Mem read/write lists are inherited by successor. */
+ concat_insn_mem_list (pred_deps->pending_read_insns,
+ pred_deps->pending_read_mems,
+ &succ_deps->pending_read_insns,
+ &succ_deps->pending_read_mems);
+ concat_insn_mem_list (pred_deps->pending_write_insns,
+ pred_deps->pending_write_mems,
+ &succ_deps->pending_write_insns,
+ &succ_deps->pending_write_mems);
+
+ succ_deps->pending_jump_insns
+ = concat_INSN_LIST (pred_deps->pending_jump_insns,
+ succ_deps->pending_jump_insns);
+ succ_deps->last_pending_memory_flush
+ = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
+ succ_deps->last_pending_memory_flush);
+
+ succ_deps->pending_read_list_length += pred_deps->pending_read_list_length;
+ succ_deps->pending_write_list_length += pred_deps->pending_write_list_length;
+ succ_deps->pending_flush_length += pred_deps->pending_flush_length;
+
+ /* last_function_call is inherited by successor. */
+ succ_deps->last_function_call
+ = 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,
+ succ_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));
+ basic_block block = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb));
edge_iterator ei;
edge e;
/* bb's structures are inherited by its successors. */
FOR_EACH_EDGE (e, ei, block->succs)
{
- struct deps *succ_deps;
- unsigned reg;
- reg_set_iterator rsi;
-
/* Only bbs "below" bb, in the same region, are interesting. */
- if (e->dest == EXIT_BLOCK_PTR
+ if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
|| CONTAINING_RGN (block->index) != CONTAINING_RGN (e->dest->index)
|| BLOCK_TO_BB (e->dest->index) <= bb)
continue;
- succ_deps = bb_deps + BLOCK_TO_BB (e->dest->index);
-
- /* The reg_last lists are inherited by successor. */
- EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi)
- {
- struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
- struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
-
- 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->clobbers = concat_INSN_LIST (pred_rl->clobbers,
- succ_rl->clobbers);
- succ_rl->uses_length += pred_rl->uses_length;
- succ_rl->clobbers_length += pred_rl->clobbers_length;
- }
- IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
-
- /* Mem read/write lists are inherited by successor. */
- concat_insn_mem_list (pred_deps->pending_read_insns,
- pred_deps->pending_read_mems,
- &succ_deps->pending_read_insns,
- &succ_deps->pending_read_mems);
- concat_insn_mem_list (pred_deps->pending_write_insns,
- pred_deps->pending_write_mems,
- &succ_deps->pending_write_insns,
- &succ_deps->pending_write_mems);
-
- succ_deps->last_pending_memory_flush
- = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
- succ_deps->last_pending_memory_flush);
-
- succ_deps->pending_read_list_length
- += pred_deps->pending_read_list_length;
- succ_deps->pending_write_list_length
- += pred_deps->pending_write_list_length;
- succ_deps->pending_flush_length += pred_deps->pending_flush_length;
-
- /* last_function_call is inherited by successor. */
- succ_deps->last_function_call
- = concat_INSN_LIST (pred_deps->last_function_call,
- succ_deps->last_function_call);
-
- /* sched_before_next_call is inherited by successor. */
- succ_deps->sched_before_next_call
- = concat_INSN_LIST (pred_deps->sched_before_next_call,
- succ_deps->sched_before_next_call);
+ deps_join (bb_deps + BLOCK_TO_BB (e->dest->index), pred_deps);
}
/* These lists should point to the right place, for correct
bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
+ bb_deps[bb].pending_jump_insns = pred_deps->pending_jump_insns;
/* Can't allow these to be freed twice. */
pred_deps->pending_read_insns = 0;
pred_deps->pending_read_mems = 0;
pred_deps->pending_write_insns = 0;
pred_deps->pending_write_mems = 0;
+ pred_deps->pending_jump_insns = 0;
}
/* Compute dependences inside bb. In a multiple blocks region:
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
static void
compute_block_dependences (int bb)
{
- rtx head, tail;
- struct deps tmp_deps;
+ rtx_insn *head, *tail;
+ struct deps_desc tmp_deps;
tmp_deps = bb_deps[bb];
get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
sched_analyze (&tmp_deps, head, tail);
- add_branch_dependences (head, tail);
+
+ /* Selective scheduling handles control dependencies by itself. */
+ if (!sel_sched_p ())
+ add_branch_dependences (head, tail);
if (current_nr_blocks > 1)
propagate_deps (bb, &tmp_deps);
static void
free_block_dependencies (int bb)
{
- rtx head;
- rtx tail;
+ rtx_insn *head;
+ rtx_insn *tail;
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);
}
free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
+ free_INSN_LIST_list (&bb_deps[bb].pending_jump_insns);
}
}
\f
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;
for (bb = from_bb; bb < current_nr_blocks; bb++)
{
- rtx head, tail;
+ rtx_insn *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);
fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
BB_TO_BLOCK (bb), bb);
/* Print dependencies information for instructions between HEAD and TAIL.
??? This function would probably fit best in haifa-sched.c. */
-void debug_dependencies (rtx head, rtx tail)
+void debug_dependencies (rtx_insn *head, rtx_insn *tail)
{
- rtx insn;
- rtx next_tail = NEXT_INSN (tail);
+ rtx_insn *insn;
+ rtx_insn *next_tail = NEXT_INSN (tail);
fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
"insn", "code", "bb", "dep", "prio", "cost",
INSN_UID (insn),
INSN_CODE (insn),
BLOCK_NUM (insn),
- sd_lists_size (insn, SD_LIST_BACK),
- INSN_PRIORITY (insn),
- insn_cost (insn));
+ sched_emulate_haifa_p ? -1 : sd_lists_size (insn, SD_LIST_BACK),
+ (sel_sched_p () ? (sched_emulate_haifa_p ? -1
+ : INSN_PRIORITY (insn))
+ : INSN_PRIORITY (insn)),
+ (sel_sched_p () ? (sched_emulate_haifa_p ? -1
+ : insn_cost (insn))
+ : insn_cost (insn)));
if (recog_memoized (insn) < 0)
fprintf (sched_dump, "nothing");
dep_t dep;
FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
- fprintf (sched_dump, "%d ", INSN_UID (DEP_CON (dep)));
+ fprintf (sched_dump, "%d%s%s ", INSN_UID (DEP_CON (dep)),
+ DEP_NONREG (dep) ? "n" : "",
+ DEP_MULTIPLE (dep) ? "m" : "");
}
fprintf (sched_dump, "\n");
}
\f
/* Returns true if all the basic blocks of the current region have
NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
-static bool
+bool
sched_is_disabled_for_current_region_p (void)
{
int bb;
for (bb = 0; bb < current_nr_blocks; bb++)
- if (!(BASIC_BLOCK (BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE))
+ if (!(BASIC_BLOCK_FOR_FN (cfun,
+ BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE))
return false;
return true;
}
-/* Schedule a region. A region is either an inner loop, a loop-free
- subroutine, or a single basic block. Each bb in the region is
- scheduled after its flow predecessors. */
-
-static void
-schedule_region (int rgn)
+/* 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
+ the selective scheduling only. */
+void
+free_rgn_deps (void)
{
- basic_block block;
- edge_iterator ei;
- edge e;
int bb;
- int sched_rgn_n_insns = 0;
-
- rgn_n_insns = 0;
- /* Set variables for the current region. */
- current_nr_blocks = RGN_NR_BLOCKS (rgn);
- current_blocks = RGN_BLOCKS (rgn);
-
- /* See comments in add_block1, for what reasons we allocate +1 element. */
- ebb_head = xrealloc (ebb_head, (current_nr_blocks + 1) * sizeof (*ebb_head));
- for (bb = 0; bb <= current_nr_blocks; bb++)
- ebb_head[bb] = current_blocks + bb;
-
- /* Don't schedule region that is marked by
- NOTE_DISABLE_SCHED_OF_BLOCK. */
- if (sched_is_disabled_for_current_region_p ())
- return;
- if (!RGN_DONT_CALC_DEPS (rgn))
+ for (bb = 0; bb < current_nr_blocks; bb++)
{
- init_deps_global ();
+ rtx_insn *head, *tail;
- /* Initializations for region data dependence analysis. */
- bb_deps = XNEWVEC (struct deps, current_nr_blocks);
- for (bb = 0; bb < current_nr_blocks; bb++)
- init_deps (bb_deps + bb);
+ 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 dependencies. */
- for (bb = 0; bb < current_nr_blocks; bb++)
- compute_block_dependences (bb);
+ sched_free_deps (head, tail, false);
+ }
+}
- free_pending_lists ();
+static int rgn_n_insns;
- finish_deps_global ();
+/* Compute insn priority for a current region. */
+void
+compute_priorities (void)
+{
+ int bb;
- free (bb_deps);
- }
- else
- /* This is a recovery block. It is always a single block region. */
- gcc_assert (current_nr_blocks == 1);
-
- /* Set priorities. */
current_sched_info->sched_max_insns_priority = 0;
for (bb = 0; bb < current_nr_blocks; bb++)
{
- rtx head, tail;
-
+ rtx_insn *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++;
+}
- /* Compute interblock info: probabilities, split-edges, dominators, etc. */
- if (current_nr_blocks > 1)
+/* (Re-)initialize the arrays of DFA states at the end of each basic block.
+
+ SAVED_LAST_BASIC_BLOCK is the previous length of the arrays. It must be
+ zero for the first call to this function, to allocate the arrays for the
+ first time.
+
+ This function is called once during initialization of the scheduler, and
+ called again to resize the arrays if new basic blocks have been created,
+ for example for speculation recovery code. */
+
+static void
+realloc_bb_state_array (int saved_last_basic_block)
+{
+ char *old_bb_state_array = bb_state_array;
+ size_t lbb = (size_t) last_basic_block_for_fn (cfun);
+ size_t slbb = (size_t) saved_last_basic_block;
+
+ /* Nothing to do if nothing changed since the last time this was called. */
+ if (saved_last_basic_block == last_basic_block_for_fn (cfun))
+ return;
+
+ /* The selective scheduler doesn't use the state arrays. */
+ if (sel_sched_p ())
{
- prob = XNEWVEC (int, current_nr_blocks);
+ gcc_assert (bb_state_array == NULL && bb_state == NULL);
+ return;
+ }
- dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
- sbitmap_vector_zero (dom, current_nr_blocks);
+ gcc_checking_assert (saved_last_basic_block == 0
+ || (bb_state_array != NULL && bb_state != NULL));
- /* Use ->aux to implement EDGE_TO_BIT mapping. */
- rgn_nr_edges = 0;
- FOR_EACH_BB (block)
- {
- if (CONTAINING_RGN (block->index) != rgn)
- continue;
- FOR_EACH_EDGE (e, ei, block->succs)
- SET_EDGE_TO_BIT (e, rgn_nr_edges++);
- }
+ bb_state_array = XRESIZEVEC (char, bb_state_array, lbb * dfa_state_size);
+ bb_state = XRESIZEVEC (state_t, bb_state, lbb);
- rgn_edges = XNEWVEC (edge, rgn_nr_edges);
- rgn_nr_edges = 0;
- FOR_EACH_BB (block)
- {
- if (CONTAINING_RGN (block->index) != rgn)
- continue;
- FOR_EACH_EDGE (e, ei, block->succs)
- rgn_edges[rgn_nr_edges++] = e;
- }
+ /* If BB_STATE_ARRAY has moved, fixup all the state pointers array.
+ Otherwise only fixup the newly allocated ones. For the state
+ array itself, only initialize the new entries. */
+ bool bb_state_array_moved = (bb_state_array != old_bb_state_array);
+ for (size_t i = bb_state_array_moved ? 0 : slbb; i < lbb; i++)
+ bb_state[i] = (state_t) (bb_state_array + i * dfa_state_size);
+ for (size_t i = slbb; i < lbb; i++)
+ state_reset (bb_state[i]);
+}
- /* Split edges. */
- pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
- sbitmap_vector_zero (pot_split, current_nr_blocks);
- ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
- sbitmap_vector_zero (ancestor_edges, current_nr_blocks);
+/* Free the arrays of DFA states at the end of each basic block. */
- /* Compute probabilities, dominators, split_edges. */
- for (bb = 0; bb < current_nr_blocks; bb++)
- compute_dom_prob_ps (bb);
+static void
+free_bb_state_array (void)
+{
+ free (bb_state_array);
+ free (bb_state);
+ bb_state_array = NULL;
+ bb_state = NULL;
+}
- /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
- /* We don't need them anymore. But we want to avoid duplication of
- aux fields in the newly created edges. */
- FOR_EACH_BB (block)
+/* Schedule a region. A region is either an inner loop, a loop-free
+ subroutine, or a single basic block. Each bb in the region is
+ scheduled after its flow predecessors. */
+
+static void
+schedule_region (int rgn)
+{
+ int bb;
+ int sched_rgn_n_insns = 0;
+
+ rgn_n_insns = 0;
+
+ /* Do not support register pressure sensitive scheduling for the new regions
+ as we don't update the liveness info for them. */
+ if (sched_pressure != SCHED_PRESSURE_NONE
+ && rgn >= nr_regions_initial)
+ {
+ free_global_sched_pressure_data ();
+ sched_pressure = SCHED_PRESSURE_NONE;
+ }
+
+ rgn_setup_region (rgn);
+
+ /* Don't schedule region that is marked by
+ NOTE_DISABLE_SCHED_OF_BLOCK. */
+ if (sched_is_disabled_for_current_region_p ())
+ return;
+
+ sched_rgn_compute_dependencies (rgn);
+
+ sched_rgn_local_init (rgn);
+
+ /* Set priorities. */
+ compute_priorities ();
+
+ sched_extend_ready_list (rgn_n_insns);
+
+ if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
+ {
+ sched_init_region_reg_pressure_info ();
+ for (bb = 0; bb < current_nr_blocks; bb++)
{
- if (CONTAINING_RGN (block->index) != rgn)
- continue;
- FOR_EACH_EDGE (e, ei, block->succs)
- e->aux = NULL;
- }
+ basic_block first_bb, last_bb;
+ rtx_insn *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++)
{
basic_block first_bb, last_bb, curr_bb;
- rtx head, tail;
+ rtx_insn *head, *tail;
first_bb = EBB_FIRST_BB (bb);
last_bb = EBB_LAST_BB (bb);
current_sched_info->prev_head = PREV_INSN (head);
current_sched_info->next_tail = NEXT_INSN (tail);
-
- /* rm_other_notes only removes notes which are _inside_ the
- block---that is, it won't remove notes before the first real insn
- or after the last real insn of the block. So if the first insn
- has a REG_SAVE_NOTE which would otherwise be emitted before the
- insn, it is redundant with the note before the start of the
- block, and so we have to take it out. */
- if (INSN_P (head))
- {
- rtx note;
-
- for (note = REG_NOTES (head); note; note = XEXP (note, 1))
- if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
- remove_note (head, note);
- }
- else
- /* This means that first block in ebb is empty.
- It looks to me as an impossible thing. There at least should be
- a recovery check, that caused the splitting. */
- gcc_unreachable ();
-
- /* Remove remaining note insns from the block, save them in
- note_list. These notes are restored at the end of
- schedule_block (). */
- rm_other_notes (head, tail);
+ remove_notes (head, tail);
unlink_bb_notes (first_bb, last_bb);
curr_bb = first_bb;
if (dbg_cnt (sched_block))
{
- schedule_block (&curr_bb, rgn_n_insns);
- gcc_assert (EBB_FIRST_BB (bb) == first_bb);
- sched_rgn_n_insns += sched_n_insns;
+ edge f;
+ int saved_last_basic_block = last_basic_block_for_fn (cfun);
+
+ schedule_block (&curr_bb, bb_state[first_bb->index]);
+ gcc_assert (EBB_FIRST_BB (bb) == first_bb);
+ sched_rgn_n_insns += sched_n_insns;
+ realloc_bb_state_array (saved_last_basic_block);
+ f = find_fallthru_edge (last_bb->succs);
+ if (f && f->probability * 100 / REG_BR_PROB_BASE >=
+ PARAM_VALUE (PARAM_SCHED_STATE_EDGE_PROB_CUTOFF))
+ {
+ memcpy (bb_state[f->dest->index], curr_state,
+ dfa_state_size);
+ if (sched_verbose >= 5)
+ fprintf (sched_dump, "saving state for edge %d->%d\n",
+ f->src->index, f->dest->index);
+ }
}
else
{
/* Clean up. */
if (current_nr_blocks > 1)
- {
- free (candidate_table);
- free (bblst_table);
- free (edgelst_table);
- }
+ free_trg_info ();
}
/* Sanity check: verify that all region insns were scheduled. */
gcc_assert (sched_rgn_n_insns == rgn_n_insns);
- /* Done with this region. */
+ sched_finish_ready_list ();
- if (current_nr_blocks > 1)
- {
- free (prob);
- sbitmap_vector_free (dom);
- sbitmap_vector_free (pot_split);
- sbitmap_vector_free (ancestor_edges);
- free (rgn_edges);
- }
+ /* Done with this region. */
+ sched_rgn_local_finish ();
/* Free dependencies. */
for (bb = 0; bb < current_nr_blocks; ++bb)
/* Initialize data structures for region scheduling. */
-static void
-init_regions (void)
+void
+sched_rgn_init (bool single_blocks_p)
{
- nr_regions = 0;
- rgn_table = 0;
- rgn_bb_table = 0;
- block_to_bb = 0;
- containing_rgn = 0;
+ min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE)
+ / 100);
+
+ nr_inter = 0;
+ nr_spec = 0;
+
extend_regions ();
+ CONTAINING_RGN (ENTRY_BLOCK) = -1;
+ CONTAINING_RGN (EXIT_BLOCK) = -1;
+
+ realloc_bb_state_array (0);
+
/* Compute regions for scheduling. */
- if (reload_completed
- || n_basic_blocks == NUM_FIXED_BLOCKS + 1
+ if (single_blocks_p
+ || n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS + 1
|| !flag_schedule_interblock
|| is_cfg_nonregular ())
{
- find_single_block_region ();
+ find_single_block_region (sel_sched_p ());
}
else
{
/* Compute the dominators and post dominators. */
- calculate_dominance_info (CDI_DOMINATORS);
+ if (!sel_sched_p ())
+ calculate_dominance_info (CDI_DOMINATORS);
/* Find regions. */
find_rgns ();
/* For now. This will move as more and more of haifa is converted
to using the cfg code. */
- free_dominance_info (CDI_DOMINATORS);
+ if (!sel_sched_p ())
+ free_dominance_info (CDI_DOMINATORS);
}
- RGN_BLOCKS (nr_regions) = RGN_BLOCKS (nr_regions - 1) +
- RGN_NR_BLOCKS (nr_regions - 1);
-}
-/* The one entry point in this file. */
+ gcc_assert (0 < nr_regions && nr_regions <= n_basic_blocks_for_fn (cfun));
+
+ RGN_BLOCKS (nr_regions) = (RGN_BLOCKS (nr_regions - 1) +
+ RGN_NR_BLOCKS (nr_regions - 1));
+ nr_regions_initial = nr_regions;
+}
+/* Free data structures for region scheduling. */
void
-schedule_insns (void)
+sched_rgn_finish (void)
{
- int rgn;
-
- /* Taking care of this degenerate case makes the rest of
- this code simpler. */
- if (n_basic_blocks == NUM_FIXED_BLOCKS)
- return;
+ free_bb_state_array ();
- nr_inter = 0;
- nr_spec = 0;
-
- /* We need current_sched_info in init_dependency_caches, which is
- invoked via sched_init. */
- current_sched_info = ®ion_sched_info;
-
- df_set_flags (DF_LR_RUN_DCE);
- df_note_add_problem ();
- df_analyze ();
- regstat_compute_calls_crossed ();
-
- sched_init ();
-
- bitmap_initialize (¬_in_df, 0);
- bitmap_clear (¬_in_df);
-
- min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE)
- / 100);
-
- init_regions ();
-
- /* EBB_HEAD is a region-scope structure. But we realloc it for
- each region to save time/memory/something else. */
- ebb_head = 0;
-
- /* Schedule every region in the subroutine. */
- for (rgn = 0; rgn < nr_regions; rgn++)
- if (dbg_cnt (sched_region))
- schedule_region (rgn);
-
- free(ebb_head);
/* Reposition the prologue and epilogue notes in case we moved the
prologue/epilogue insns. */
if (reload_completed)
if (sched_verbose)
{
- if (reload_completed == 0 && flag_schedule_interblock)
+ if (reload_completed == 0
+ && flag_schedule_interblock)
{
fprintf (sched_dump,
"\n;; Procedure interblock/speculative motions == %d/%d \n",
fprintf (sched_dump, "\n\n");
}
- /* Clean up. */
+ nr_regions = 0;
+
free (rgn_table);
+ rgn_table = NULL;
+
free (rgn_bb_table);
+ rgn_bb_table = NULL;
+
free (block_to_bb);
+ block_to_bb = NULL;
+
free (containing_rgn);
+ containing_rgn = NULL;
- regstat_free_calls_crossed ();
+ free (ebb_head);
+ ebb_head = NULL;
+}
+/* Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
+ point to the region RGN. */
+void
+rgn_setup_region (int rgn)
+{
+ int 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. */
+ ebb_head = XRESIZEVEC (int, ebb_head, current_nr_blocks + 1);
+ for (bb = 0; bb <= current_nr_blocks; bb++)
+ ebb_head[bb] = current_blocks + bb;
+}
+
+/* Compute instruction dependencies in region RGN. */
+void
+sched_rgn_compute_dependencies (int rgn)
+{
+ if (!RGN_DONT_CALC_DEPS (rgn))
+ {
+ int bb;
+
+ if (sel_sched_p ())
+ sched_emulate_haifa_p = 1;
+
+ init_deps_global ();
+
+ /* Initializations for region data dependence analysis. */
+ bb_deps = XNEWVEC (struct deps_desc, current_nr_blocks);
+ for (bb = 0; bb < current_nr_blocks; bb++)
+ init_deps (bb_deps + bb, false);
+
+ /* Initialize bitmap used in add_branch_dependences. */
+ insn_referenced = sbitmap_alloc (sched_max_luid);
+ bitmap_clear (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 ();
+ free (bb_deps);
+
+ /* We don't want to recalculate this twice. */
+ RGN_DONT_CALC_DEPS (rgn) = 1;
+
+ if (sel_sched_p ())
+ sched_emulate_haifa_p = 0;
+ }
+ else
+ /* (This is a recovery block. It is always a single block region.)
+ OR (We use selective scheduling.) */
+ gcc_assert (current_nr_blocks == 1 || sel_sched_p ());
+}
+
+/* Init region data structures. Returns true if this region should
+ not be scheduled. */
+void
+sched_rgn_local_init (int rgn)
+{
+ int bb;
+
+ /* Compute interblock info: probabilities, split-edges, dominators, etc. */
+ if (current_nr_blocks > 1)
+ {
+ basic_block block;
+ edge e;
+ edge_iterator ei;
+
+ prob = XNEWVEC (int, current_nr_blocks);
+
+ dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
+ bitmap_vector_clear (dom, current_nr_blocks);
+
+ /* Use ->aux to implement EDGE_TO_BIT mapping. */
+ rgn_nr_edges = 0;
+ FOR_EACH_BB_FN (block, cfun)
+ {
+ if (CONTAINING_RGN (block->index) != rgn)
+ continue;
+ FOR_EACH_EDGE (e, ei, block->succs)
+ SET_EDGE_TO_BIT (e, rgn_nr_edges++);
+ }
+
+ rgn_edges = XNEWVEC (edge, rgn_nr_edges);
+ rgn_nr_edges = 0;
+ FOR_EACH_BB_FN (block, cfun)
+ {
+ if (CONTAINING_RGN (block->index) != rgn)
+ continue;
+ FOR_EACH_EDGE (e, ei, block->succs)
+ rgn_edges[rgn_nr_edges++] = e;
+ }
+
+ /* Split edges. */
+ pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
+ bitmap_vector_clear (pot_split, current_nr_blocks);
+ ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
+ bitmap_vector_clear (ancestor_edges, current_nr_blocks);
+
+ /* Compute probabilities, dominators, split_edges. */
+ for (bb = 0; bb < current_nr_blocks; bb++)
+ compute_dom_prob_ps (bb);
+
+ /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
+ /* We don't need them anymore. But we want to avoid duplication of
+ aux fields in the newly created edges. */
+ FOR_EACH_BB_FN (block, cfun)
+ {
+ if (CONTAINING_RGN (block->index) != rgn)
+ continue;
+ FOR_EACH_EDGE (e, ei, block->succs)
+ e->aux = NULL;
+ }
+ }
+}
+
+/* Free data computed for the finished region. */
+void
+sched_rgn_local_free (void)
+{
+ free (prob);
+ sbitmap_vector_free (dom);
+ sbitmap_vector_free (pot_split);
+ sbitmap_vector_free (ancestor_edges);
+ free (rgn_edges);
+}
+
+/* Free data computed for the finished region. */
+void
+sched_rgn_local_finish (void)
+{
+ if (current_nr_blocks > 1 && !sel_sched_p ())
+ {
+ sched_rgn_local_free ();
+ }
+}
+
+/* Setup scheduler infos. */
+void
+rgn_setup_common_sched_info (void)
+{
+ memcpy (&rgn_common_sched_info, &haifa_common_sched_info,
+ sizeof (rgn_common_sched_info));
+
+ rgn_common_sched_info.fix_recovery_cfg = rgn_fix_recovery_cfg;
+ rgn_common_sched_info.add_block = rgn_add_block;
+ rgn_common_sched_info.estimate_number_of_insns
+ = rgn_estimate_number_of_insns;
+ rgn_common_sched_info.sched_pass_id = SCHED_RGN_PASS;
+
+ common_sched_info = &rgn_common_sched_info;
+}
+
+/* Setup all *_sched_info structures (for the Haifa frontend
+ and for the dependence analysis) in the interblock scheduler. */
+void
+rgn_setup_sched_infos (void)
+{
+ if (!sel_sched_p ())
+ memcpy (&rgn_sched_deps_info, &rgn_const_sched_deps_info,
+ sizeof (rgn_sched_deps_info));
+ else
+ memcpy (&rgn_sched_deps_info, &rgn_const_sel_sched_deps_info,
+ sizeof (rgn_sched_deps_info));
+
+ sched_deps_info = &rgn_sched_deps_info;
+
+ memcpy (&rgn_sched_info, &rgn_const_sched_info, sizeof (rgn_sched_info));
+ current_sched_info = &rgn_sched_info;
+}
+
+/* The one entry point in this file. */
+void
+schedule_insns (void)
+{
+ int rgn;
+
+ /* Taking care of this degenerate case makes the rest of
+ this code simpler. */
+ if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
+ return;
+
+ rgn_setup_common_sched_info ();
+ rgn_setup_sched_infos ();
+
+ haifa_sched_init ();
+ sched_rgn_init (reload_completed);
+
+ bitmap_initialize (¬_in_df, 0);
bitmap_clear (¬_in_df);
- sched_finish ();
+ /* Schedule every region in the subroutine. */
+ for (rgn = 0; rgn < nr_regions; rgn++)
+ if (dbg_cnt (sched_region))
+ schedule_region (rgn);
+
+ /* Clean up. */
+ sched_rgn_finish ();
+ bitmap_clear (¬_in_df);
+
+ haifa_sched_finish ();
}
/* INSN has been added to/removed from current region. */
static void
-add_remove_insn (rtx insn, int remove_p)
+rgn_add_remove_insn (rtx_insn *insn, int remove_p)
{
if (!remove_p)
rgn_n_insns++;
}
/* Extend internal data structures. */
-static void
+void
extend_regions (void)
{
- rgn_table = XRESIZEVEC (region, rgn_table, n_basic_blocks);
- rgn_bb_table = XRESIZEVEC (int, rgn_bb_table, n_basic_blocks);
- block_to_bb = XRESIZEVEC (int, block_to_bb, last_basic_block);
- containing_rgn = XRESIZEVEC (int, containing_rgn, last_basic_block);
+ rgn_table = XRESIZEVEC (region, rgn_table, n_basic_blocks_for_fn (cfun));
+ rgn_bb_table = XRESIZEVEC (int, rgn_bb_table,
+ n_basic_blocks_for_fn (cfun));
+ block_to_bb = XRESIZEVEC (int, block_to_bb,
+ last_basic_block_for_fn (cfun));
+ containing_rgn = XRESIZEVEC (int, containing_rgn,
+ last_basic_block_for_fn (cfun));
+}
+
+void
+rgn_make_new_region_out_of_new_block (basic_block bb)
+{
+ int i;
+
+ i = RGN_BLOCKS (nr_regions);
+ /* I - first free position in rgn_bb_table. */
+
+ rgn_bb_table[i] = bb->index;
+ RGN_NR_BLOCKS (nr_regions) = 1;
+ RGN_HAS_REAL_EBB (nr_regions) = 0;
+ RGN_DONT_CALC_DEPS (nr_regions) = 0;
+ CONTAINING_RGN (bb->index) = nr_regions;
+ BLOCK_TO_BB (bb->index) = 0;
+
+ nr_regions++;
+
+ RGN_BLOCKS (nr_regions) = i + 1;
}
/* BB was added to ebb after AFTER. */
static void
-add_block1 (basic_block bb, basic_block after)
+rgn_add_block (basic_block bb, basic_block after)
{
extend_regions ();
-
bitmap_set_bit (¬_in_df, bb->index);
- if (after == 0 || after == EXIT_BLOCK_PTR)
+ if (after == 0 || after == EXIT_BLOCK_PTR_FOR_FN (cfun))
{
- int i;
-
- i = RGN_BLOCKS (nr_regions);
- /* I - first free position in rgn_bb_table. */
-
- rgn_bb_table[i] = bb->index;
- RGN_NR_BLOCKS (nr_regions) = 1;
- RGN_DONT_CALC_DEPS (nr_regions) = after == EXIT_BLOCK_PTR;
- RGN_HAS_REAL_EBB (nr_regions) = 0;
- CONTAINING_RGN (bb->index) = nr_regions;
- BLOCK_TO_BB (bb->index) = 0;
-
- nr_regions++;
-
- RGN_BLOCKS (nr_regions) = i + 1;
+ rgn_make_new_region_out_of_new_block (bb);
+ RGN_DONT_CALC_DEPS (nr_regions - 1) = (after
+ == EXIT_BLOCK_PTR_FOR_FN (cfun));
}
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. */
/* Now POS is the index of the last block in the region. */
/* Find index of basic block AFTER. */
- for (; rgn_bb_table[pos] != after->index; pos--);
+ for (; rgn_bb_table[pos] != after->index; pos--)
+ ;
pos++;
gcc_assert (pos > ebb_head[i - 1]);
/* 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++)
For parameter meaning please refer to
sched-int.h: struct sched_info: fix_recovery_cfg. */
static void
-fix_recovery_cfg (int bbi, int check_bbi, int check_bb_nexti)
+rgn_fix_recovery_cfg (int bbi, int check_bbi, int check_bb_nexti)
{
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--);
+ old_pos--)
+ ;
gcc_assert (old_pos > ebb_head[BLOCK_TO_BB (check_bbi)]);
for (new_pos = ebb_head[BLOCK_TO_BB (bbi) + 1] - 1;
rgn_bb_table[new_pos] != bbi;
- new_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,
/* Return next block in ebb chain. For parameter meaning please refer to
sched-int.h: struct sched_info: advance_target_bb. */
static basic_block
-advance_target_bb (basic_block bb, rtx insn)
+advance_target_bb (basic_block bb, rtx_insn *insn)
{
if (insn)
return 0;
#endif
\f
-static bool
-gate_handle_sched (void)
+/* Run instruction scheduler. */
+static unsigned int
+rest_of_handle_live_range_shrinkage (void)
{
#ifdef INSN_SCHEDULING
- return flag_schedule_insns && dbg_cnt (sched_func);
-#else
- return 0;
+ int saved;
+
+ initialize_live_range_shrinkage ();
+ saved = flag_schedule_interblock;
+ flag_schedule_interblock = false;
+ schedule_insns ();
+ flag_schedule_interblock = saved;
+ finish_live_range_shrinkage ();
#endif
+ return 0;
}
/* Run instruction scheduler. */
rest_of_handle_sched (void)
{
#ifdef INSN_SCHEDULING
- schedule_insns ();
+ if (flag_selective_scheduling
+ && ! maybe_skip_selective_scheduling ())
+ run_selective_scheduling ();
+ else
+ schedule_insns ();
#endif
return 0;
}
-static bool
-gate_handle_sched2 (void)
+/* Run second scheduling pass after reload. */
+static unsigned int
+rest_of_handle_sched2 (void)
{
#ifdef INSN_SCHEDULING
- return optimize > 0 && flag_schedule_insns_after_reload
- && dbg_cnt (sched2_func);
-#else
- return 0;
+ if (flag_selective_scheduling2
+ && ! maybe_skip_selective_scheduling ())
+ run_selective_scheduling ();
+ else
+ {
+ /* Do control and data sched analysis again,
+ and write some more of the results to dump file. */
+ if (flag_sched2_use_superblocks)
+ schedule_ebbs ();
+ else
+ schedule_insns ();
+ }
#endif
+ return 0;
}
-/* Run second scheduling pass after reload. */
static unsigned int
-rest_of_handle_sched2 (void)
+rest_of_handle_sched_fusion (void)
{
#ifdef INSN_SCHEDULING
- /* 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)
- schedule_ebbs ();
- else
- schedule_insns ();
+ sched_fusion = true;
+ schedule_insns ();
+ sched_fusion = false;
#endif
return 0;
}
-struct tree_opt_pass pass_sched =
-{
- "sched1", /* name */
- gate_handle_sched, /* gate */
- rest_of_handle_sched, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_SCHED, /* tv_id */
- 0, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_df_finish | TODO_verify_rtl_sharing |
- TODO_dump_func |
- TODO_verify_flow |
- TODO_ggc_collect, /* todo_flags_finish */
- 'S' /* letter */
+namespace {
+
+const pass_data pass_data_live_range_shrinkage =
+{
+ RTL_PASS, /* type */
+ "lr_shrinkage", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_LIVE_RANGE_SHRINKAGE, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_df_finish, /* todo_flags_finish */
};
-struct tree_opt_pass pass_sched2 =
-{
- "sched2", /* name */
- gate_handle_sched2, /* gate */
- rest_of_handle_sched2, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_SCHED2, /* tv_id */
- 0, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_df_finish | TODO_verify_rtl_sharing |
- TODO_dump_func |
- TODO_verify_flow |
- TODO_ggc_collect, /* todo_flags_finish */
- 'R' /* letter */
+class pass_live_range_shrinkage : public rtl_opt_pass
+{
+public:
+ pass_live_range_shrinkage(gcc::context *ctxt)
+ : rtl_opt_pass(pass_data_live_range_shrinkage, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *)
+ {
+#ifdef INSN_SCHEDULING
+ return flag_live_range_shrinkage;
+#else
+ return 0;
+#endif
+ }
+
+ virtual unsigned int execute (function *)
+ {
+ return rest_of_handle_live_range_shrinkage ();
+ }
+
+}; // class pass_live_range_shrinkage
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_live_range_shrinkage (gcc::context *ctxt)
+{
+ return new pass_live_range_shrinkage (ctxt);
+}
+
+namespace {
+
+const pass_data pass_data_sched =
+{
+ RTL_PASS, /* type */
+ "sched1", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_SCHED, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_df_finish, /* todo_flags_finish */
};
+class pass_sched : public rtl_opt_pass
+{
+public:
+ pass_sched (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_sched, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *);
+ virtual unsigned int execute (function *) { return rest_of_handle_sched (); }
+
+}; // class pass_sched
+
+bool
+pass_sched::gate (function *)
+{
+#ifdef INSN_SCHEDULING
+ return optimize > 0 && flag_schedule_insns && dbg_cnt (sched_func);
+#else
+ return 0;
+#endif
+}
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_sched (gcc::context *ctxt)
+{
+ return new pass_sched (ctxt);
+}
+
+namespace {
+
+const pass_data pass_data_sched2 =
+{
+ RTL_PASS, /* type */
+ "sched2", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_SCHED2, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_df_finish, /* todo_flags_finish */
+};
+
+class pass_sched2 : public rtl_opt_pass
+{
+public:
+ pass_sched2 (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_sched2, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *);
+ virtual unsigned int execute (function *)
+ {
+ return rest_of_handle_sched2 ();
+ }
+
+}; // class pass_sched2
+
+bool
+pass_sched2::gate (function *)
+{
+#ifdef INSN_SCHEDULING
+ return optimize > 0 && flag_schedule_insns_after_reload
+ && !targetm.delay_sched2 && dbg_cnt (sched2_func);
+#else
+ return 0;
+#endif
+}
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_sched2 (gcc::context *ctxt)
+{
+ return new pass_sched2 (ctxt);
+}
+
+namespace {
+
+const pass_data pass_data_sched_fusion =
+{
+ RTL_PASS, /* type */
+ "sched_fusion", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_SCHED_FUSION, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_df_finish, /* todo_flags_finish */
+};
+
+class pass_sched_fusion : public rtl_opt_pass
+{
+public:
+ pass_sched_fusion (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_sched_fusion, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *);
+ virtual unsigned int execute (function *)
+ {
+ return rest_of_handle_sched_fusion ();
+ }
+
+}; // class pass_sched2
+
+bool
+pass_sched_fusion::gate (function *)
+{
+#ifdef INSN_SCHEDULING
+ /* Scheduling fusion relies on peephole2 to do real fusion work,
+ so only enable it if peephole2 is in effect. */
+ return (optimize > 0 && flag_peephole2
+ && flag_schedule_fusion && targetm.sched.fusion_priority != NULL);
+#else
+ return 0;
+#endif
+}
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_sched_fusion (gcc::context *ctxt)
+{
+ return new pass_sched_fusion (ctxt);
+}