#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "toplev.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "regs.h"
#include "function.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 "sched-int.h"
#include "target.h"
#include "timevar.h"
#include "tree-pass.h"
#ifdef ENABLE_LLVM
#undef INSN_SCHEDULING
#endif
#if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING)
#define CHECK_DEAD_NOTES 1
#else
#define CHECK_DEAD_NOTES 0
#endif
#ifdef INSN_SCHEDULING
#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)
static int nr_inter, nr_spec;
static int is_cfg_nonregular (void);
static bool sched_is_disabled_for_current_region_p (void);
typedef struct
{
int rgn_nr_blocks;
int rgn_blocks;
unsigned int dont_calc_deps : 1;
unsigned int has_real_ebb : 1;
}
region;
static int nr_regions;
static region *rgn_table;
static int *rgn_bb_table;
static int *block_to_bb;
static int *containing_rgn;
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_rgns (void);
static void extend_rgns (int *, int *, sbitmap, int *);
static bool too_large (int, int *, int *);
extern void debug_live (int, int);
static int current_nr_blocks;
static int current_blocks;
static int rgn_n_insns;
#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])
typedef struct
{
basic_block *first_member;
int nr_members;
}
bblst;
typedef struct
{
char is_valid;
char is_speculative;
int src_prob;
bblst split_bbs;
bblst update_bbs;
}
candidate;
static candidate *candidate_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 SRC_PROB(src) ( candidate_table[src].src_prob )
static int target_bb;
typedef struct
{
edge *first_member;
int nr_members;
}
edgelst;
static edge *edgelst_table;
static int edgelst_last;
static void extract_edgelst (sbitmap, edgelst *);
static void split_edges (int, int, edgelst *);
static void compute_trg_info (int);
void debug_candidate (int);
void debug_candidates (int);
static sbitmap *dom;
#define IS_RGN_ENTRY(bb) (!bb)
#define IS_DOMINATED(bb_src, bb_trg) \
( TEST_BIT (dom[bb_src], bb_trg) )
static int *prob;
typedef sbitmap edgeset;
static int rgn_nr_edges;
static edge *rgn_edges;
#define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
#define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
static edgeset *pot_split;
static edgeset *ancestor_edges;
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)))
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 is_conditionally_protected (rtx, int, int);
static int is_prisky (rtx, int, int);
static int is_exception_free (rtx, int, int);
static bool sets_likely_spilled (rtx);
static void sets_likely_spilled_1 (rtx, rtx, void *);
static void add_branch_dependences (rtx, rtx);
static void compute_block_backward_dependences (int);
void debug_dependencies (void);
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 free_pending_lists (void);
static int
is_cfg_nonregular (void)
{
basic_block b;
rtx insn;
if (nonlocal_goto_handler_labels)
return 1;
if (forced_labels)
return 1;
if (current_function_has_exception_handlers ())
return 1;
FOR_EACH_BB (b)
FOR_BB_INSNS (b, insn)
{
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;
}
else if (JUMP_P (insn) && computed_jump_p (insn))
return 1;
}
FOR_EACH_BB (b)
{
if (EDGE_COUNT (b->preds) == 0
|| (single_pred_p (b)
&& single_pred (b) == b))
return 1;
}
return 0;
}
static void
extract_edgelst (sbitmap set, edgelst *el)
{
unsigned int i = 0;
sbitmap_iterator sbi;
edgelst_last = 0;
el->first_member = &edgelst_table[edgelst_last];
el->nr_members = 0;
EXECUTE_IF_SET_IN_SBITMAP (set, 0, i, sbi)
{
edgelst_table[edgelst_last++] = rgn_edges[i];
el->nr_members++;
}
}
void
debug_regions (void)
{
int rgn, bb;
fprintf (sched_dump, "\n;; ------------ REGIONS ----------\n\n");
for (rgn = 0; rgn < nr_regions; rgn++)
{
fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
rgn_table[rgn].rgn_nr_blocks);
fprintf (sched_dump, ";;\tbb/block: ");
current_blocks = RGN_BLOCKS (rgn);
for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
fprintf (sched_dump, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
fprintf (sched_dump, "\n\n");
}
}
static void
find_single_block_region (void)
{
basic_block bb;
nr_regions = 0;
FOR_EACH_BB (bb)
{
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++;
}
}
static bool
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))));
return ((*num_bbs > PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS))
|| (*num_insns > PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS)));
}
#define UPDATE_LOOP_RELATIONS(blk, hdr) \
{ \
if (max_hdr[blk] == -1) \
max_hdr[blk] = hdr; \
else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
RESET_BIT (inner, hdr); \
else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
{ \
RESET_BIT (inner,max_hdr[blk]); \
max_hdr[blk] = hdr; \
} \
}
static void
find_rgns (void)
{
int *max_hdr, *dfs_nr, *degree;
char no_loops = 1;
int node, child, loop_head, i, head, tail;
int count = 0, sp, idx = 0;
edge_iterator current_edge;
edge_iterator *stack;
int num_bbs, num_insns, unreachable;
int too_large_failure;
basic_block bb;
sbitmap header;
sbitmap inner;
sbitmap in_queue;
sbitmap in_stack;
max_hdr = XNEWVEC (int, last_basic_block);
dfs_nr = XCNEWVEC (int, last_basic_block);
stack = XNEWVEC (edge_iterator, n_edges);
inner = sbitmap_alloc (last_basic_block);
sbitmap_ones (inner);
header = sbitmap_alloc (last_basic_block);
sbitmap_zero (header);
in_queue = sbitmap_alloc (last_basic_block);
sbitmap_zero (in_queue);
in_stack = sbitmap_alloc (last_basic_block);
sbitmap_zero (in_stack);
for (i = 0; i < last_basic_block; i++)
max_hdr[i] = -1;
#define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
#define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR)->succs);
sp = -1;
while (1)
{
if (EDGE_PASSED (current_edge))
{
while (sp >= 0 && EDGE_PASSED (current_edge))
{
current_edge = stack[sp--];
node = ei_edge (current_edge)->src->index;
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]))
UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
ei_next (¤t_edge);
}
if (sp < 0 && EDGE_PASSED (current_edge))
break;
continue;
}
node = ei_edge (current_edge)->src->index;
gcc_assert (node != ENTRY_BLOCK);
SET_BIT (in_stack, node);
dfs_nr[node] = ++count;
child = ei_edge (current_edge)->dest->index;
if (child == EXIT_BLOCK)
{
SET_EDGE_PASSED (current_edge);
ei_next (¤t_edge);
continue;
}
if (TEST_BIT (in_stack, child))
{
no_loops = 0;
SET_BIT (header, child);
UPDATE_LOOP_RELATIONS (node, child);
SET_EDGE_PASSED (current_edge);
ei_next (¤t_edge);
continue;
}
if (dfs_nr[child])
{
if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
SET_EDGE_PASSED (current_edge);
ei_next (¤t_edge);
continue;
}
stack[++sp] = current_edge;
SET_EDGE_PASSED (current_edge);
current_edge = ei_start (ei_edge (current_edge)->dest->succs);
}
FOR_ALL_BB (bb)
{
edge_iterator ei;
edge e;
FOR_EACH_EDGE (e, ei, bb->succs)
e->aux = NULL;
}
unreachable = 0;
FOR_EACH_BB (bb)
if (dfs_nr[bb->index] == 0)
{
unreachable = 1;
break;
}
degree = dfs_nr;
FOR_EACH_BB (bb)
degree[bb->index] = EDGE_COUNT (bb->preds);
if (!unreachable)
{
int *queue, *degree1 = NULL;
sbitmap extended_rgn_header = NULL;
bool extend_regions_p;
if (no_loops)
SET_BIT (header, 0);
queue = XNEWVEC (int, n_basic_blocks);
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);
}
FOR_EACH_BB (bb)
{
if (TEST_BIT (header, bb->index) && TEST_BIT (inner, bb->index))
{
edge e;
edge_iterator ei;
basic_block jbb;
FOR_EACH_BB (jbb)
{
if (bb->index == max_hdr[jbb->index] && bb != jbb)
{
if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))
break;
}
}
if (jbb != EXIT_BLOCK_PTR)
continue;
head = tail = -1;
too_large_failure = 0;
loop_head = max_hdr[bb->index];
if (extend_regions_p)
memcpy (degree1, degree, last_basic_block * sizeof (int));
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest != EXIT_BLOCK_PTR)
--degree[e->dest->index];
num_bbs = 1;
num_insns = (INSN_LUID (BB_END (bb))
- INSN_LUID (BB_HEAD (bb)));
if (no_loops)
{
FOR_EACH_BB (jbb)
if (single_succ_p (jbb)
&& single_succ (jbb) == EXIT_BLOCK_PTR)
{
queue[++tail] = jbb->index;
SET_BIT (in_queue, jbb->index);
if (too_large (jbb->index, &num_bbs, &num_insns))
{
too_large_failure = 1;
break;
}
}
}
else
{
edge e;
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (e->src == ENTRY_BLOCK_PTR)
continue;
node = e->src->index;
if (max_hdr[node] == loop_head && node != bb->index)
{
queue[++tail] = node;
SET_BIT (in_queue, node);
if (too_large (node, &num_bbs, &num_insns))
{
too_large_failure = 1;
break;
}
}
}
}
while (head < tail && !too_large_failure)
{
edge e;
child = queue[++head];
FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->preds)
{
node = e->src->index;
if (e->src == ENTRY_BLOCK_PTR
|| max_hdr[node] != loop_head)
{
tail = -1;
break;
}
else if (!TEST_BIT (in_queue, node) && node != bb->index)
{
queue[++tail] = node;
SET_BIT (in_queue, node);
if (too_large (node, &num_bbs, &num_insns))
{
too_large_failure = 1;
break;
}
}
}
}
if (tail >= 0 && !too_large_failure)
{
degree[bb->index] = -1;
rgn_bb_table[idx] = bb->index;
RGN_NR_BLOCKS (nr_regions) = num_bbs;
RGN_BLOCKS (nr_regions) = idx++;
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) = count = 0;
while (tail >= 0)
{
if (head < 0)
head = tail;
child = queue[head];
if (degree[child] == 0)
{
edge e;
degree[child] = -1;
rgn_bb_table[idx++] = child;
BLOCK_TO_BB (child) = ++count;
CONTAINING_RGN (child) = nr_regions;
queue[head] = queue[tail--];
FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->succs)
if (e->dest != EXIT_BLOCK_PTR)
--degree[e->dest->index];
}
else
--head;
}
++nr_regions;
}
else if (extend_regions_p)
{
int *t = degree;
degree = degree1;
degree1 = t;
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest != EXIT_BLOCK_PTR)
SET_BIT (extended_rgn_header, e->dest->index);
}
}
}
free (queue);
if (extend_regions_p)
{
free (degree1);
sbitmap_a_or_b (header, header, extended_rgn_header);
sbitmap_free (extended_rgn_header);
extend_rgns (degree, &idx, header, max_hdr);
}
}
FOR_EACH_BB (bb)
if (degree[bb->index] >= 0)
{
rgn_bb_table[idx] = bb->index;
RGN_NR_BLOCKS (nr_regions) = 1;
RGN_BLOCKS (nr_regions) = idx++;
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;
}
free (max_hdr);
free (degree);
free (stack);
sbitmap_free (header);
sbitmap_free (inner);
sbitmap_free (in_queue);
sbitmap_free (in_stack);
}
static int gather_region_statistics (int **);
static void print_region_statistics (int *, int, int *, int);
static int
gather_region_statistics (int **rsp)
{
int i, *a = 0, a_sz = 0;
for (i = 0; i < nr_regions; i++)
{
int nr_blocks = RGN_NR_BLOCKS (i);
gcc_assert (nr_blocks >= 1);
if (nr_blocks > a_sz)
{
a = xrealloc (a, nr_blocks * sizeof (*a));
do
a[a_sz++] = 0;
while (a_sz != nr_blocks);
}
a[nr_blocks - 1]++;
}
*rsp = a;
return a_sz;
}
static void
print_region_statistics (int *s1, int s1_sz, int *s2, int s2_sz)
{
int i;
for (i = 1; i < s2_sz; i++)
{
int n1, n2;
n2 = s2[i];
if (n2 == 0)
continue;
if (i >= s1_sz)
n1 = 0;
else
n1 = s1[i];
fprintf (sched_dump, ";; Region extension statistics: size %d: " \
"was %d + %d more\n", i + 1, n1, n2 - n1);
}
}
static 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;
max_iter = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS);
max_hdr = xmalloc (last_basic_block * sizeof (*max_hdr));
order = xmalloc (last_basic_block * sizeof (*order));
post_order_compute (order, false);
for (i = nblocks - 1; i >= 0; i--)
{
int bbn = order[i];
if (degree[bbn] >= 0)
{
max_hdr[bbn] = bbn;
rescan = 1;
}
else
max_hdr[bbn] = -1;
}
while (rescan && iter < max_iter)
{
rescan = 0;
for (i = nblocks - 1; i >= 0; i--)
{
edge e;
edge_iterator ei;
int bbn = order[i];
if (max_hdr[bbn] != -1 && !TEST_BIT (header, bbn))
{
int hdr = -1;
FOR_EACH_EDGE (e, ei, BASIC_BLOCK (bbn)->preds)
{
int predn = e->src->index;
if (predn != ENTRY_BLOCK
&& max_hdr[predn] != -1
&& loop_hdr[bbn] == loop_hdr[predn])
{
if (hdr == -1)
hdr = max_hdr[predn];
else if (hdr != max_hdr[predn])
{
hdr = bbn;
break;
}
}
else
{
hdr = bbn;
break;
}
}
if (hdr == bbn)
{
SET_BIT (header, bbn);
rescan = 1;
}
else
gcc_assert (hdr != -1);
max_hdr[bbn] = hdr;
}
}
iter++;
}
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;
if (sched_verbose >= 6)
s1_sz = gather_region_statistics (&s1);
for (i = nblocks - 1; i >= 0; i--)
{
int bbn = order[i];
if (max_hdr[bbn] == bbn)
{
edge e;
edge_iterator ei;
int num_bbs = 0, j, num_insns = 0, large;
large = too_large (bbn, &num_bbs, &num_insns);
degree[bbn] = -1;
rgn_bb_table[idx] = bbn;
RGN_BLOCKS (nr_regions) = idx++;
RGN_DONT_CALC_DEPS (nr_regions) = 0;
RGN_HAS_REAL_EBB (nr_regions) = 0;
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)
degree[e->dest->index]--;
if (!large)
for (j = i - 1; j >= 0; j--)
{
int succn = order[j];
if (max_hdr[succn] == bbn)
{
if ((large = too_large (succn, &num_bbs, &num_insns)))
break;
}
}
if (large)
{
RGN_NR_BLOCKS (nr_regions) = 1;
nr_regions++;
}
num_bbs = 1;
for (j = i - 1; j >= 0; j--)
{
int succn = order[j];
if (max_hdr[succn] == bbn)
{
gcc_assert (degree[succn] == 0);
degree[succn] = -1;
rgn_bb_table[idx] = succn;
BLOCK_TO_BB (succn) = large ? 0 : num_bbs++;
CONTAINING_RGN (succn) = nr_regions;
if (large)
{
RGN_BLOCKS (nr_regions) = idx;
RGN_NR_BLOCKS (nr_regions) = 1;
RGN_DONT_CALC_DEPS (nr_regions) = 0;
RGN_HAS_REAL_EBB (nr_regions) = 0;
nr_regions++;
}
idx++;
FOR_EACH_EDGE (e, ei, BASIC_BLOCK (succn)->succs)
if (e->dest != EXIT_BLOCK_PTR)
degree[e->dest->index]--;
}
}
if (!large)
{
RGN_NR_BLOCKS (nr_regions) = num_bbs;
nr_regions++;
}
}
}
if (sched_verbose >= 6)
{
int *s2, s2_sz;
s2_sz = gather_region_statistics (&s2);
print_region_statistics (s1, s1_sz, s2, s2_sz);
free (s1);
free (s2);
}
}
free (order);
free (max_hdr);
*idxp = idx;
}
static void
compute_dom_prob_ps (int bb)
{
edge_iterator in_ei;
edge in_edge;
gcc_assert (ebb_head [bb] == bb + current_blocks);
if (IS_RGN_ENTRY (bb))
{
SET_BIT (dom[bb], 0);
prob[bb] = REG_BR_PROB_BASE;
return;
}
prob[bb] = 0;
sbitmap_ones (dom[bb]);
FOR_EACH_EDGE (in_edge, in_ei, BASIC_BLOCK (BB_TO_BLOCK (bb))->preds)
{
int pred_bb;
edge out_edge;
edge_iterator out_ei;
if (in_edge->src == ENTRY_BLOCK_PTR)
continue;
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],
ancestor_edges[bb], ancestor_edges[pred_bb]);
SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
sbitmap_a_or_b (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);
}
SET_BIT (dom[bb], bb);
sbitmap_difference (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),
(100 * prob[bb]) / REG_BR_PROB_BASE);
}
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_difference (src, src, pot_split[bb_trg]);
extract_edgelst (src, bl);
sbitmap_free (src);
}
static void
compute_trg_info (int trg)
{
candidate *sp;
edgelst el;
int i, j, k, update_idx;
basic_block block;
sbitmap visited;
edge_iterator ei;
edge e;
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);
for (i = trg + 1; i < current_nr_blocks; i++)
{
sp = candidate_table + i;
sp->is_valid = IS_DOMINATED (i, trg);
if (sp->is_valid)
{
int tf = prob[trg], cf = prob[i];
sp->src_prob = (tf ? ((cf * REG_BR_PROB_BASE) / tf) : 0);
sp->is_valid = (sp->src_prob >= min_spec_prob);
}
if (sp->is_valid)
{
split_edges (i, trg, &el);
sp->is_speculative = (el.nr_members) ? 1 : 0;
if (sp->is_speculative && !flag_schedule_speculative)
sp->is_valid = 0;
}
if (sp->is_valid)
{
sp->split_bbs.first_member = &bblst_table[bblst_last];
sp->split_bbs.nr_members = el.nr_members;
for (j = 0; j < el.nr_members; bblst_last++, j++)
bblst_table[bblst_last] = el.first_member[j]->dest;
sp->update_bbs.first_member = &bblst_table[bblst_last];
update_idx = 0;
sbitmap_zero (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))
{
for (k = 0; k < el.nr_members; k++)
if (e == el.first_member[k])
break;
if (k >= el.nr_members)
{
bblst_table[bblst_last++] = e->dest;
SET_BIT (visited, e->dest->index);
update_idx++;
}
}
}
}
sp->update_bbs.nr_members = update_idx;
gcc_assert (bblst_last <= bblst_size);
}
else
{
sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
sp->is_speculative = 0;
sp->src_prob = 0;
}
}
sbitmap_free (visited);
}
void
debug_candidate (int i)
{
if (!candidate_table[i].is_valid)
return;
if (candidate_table[i].is_speculative)
{
int j;
fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
fprintf (sched_dump, "split path: ");
for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
{
int b = candidate_table[i].split_bbs.first_member[j]->index;
fprintf (sched_dump, " %d ", b);
}
fprintf (sched_dump, "\n");
fprintf (sched_dump, "update path: ");
for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
{
int b = candidate_table[i].update_bbs.first_member[j]->index;
fprintf (sched_dump, " %d ", b);
}
fprintf (sched_dump, "\n");
}
else
{
fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
}
}
void
debug_candidates (int trg)
{
int i;
fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
BB_TO_BLOCK (trg), trg);
for (i = trg + 1; i < current_nr_blocks; i++)
debug_candidate (i);
}
static int
check_live_1 (int src, rtx x)
{
int i;
int regno;
rtx reg = SET_DEST (x);
if (reg == 0)
return 1;
while (GET_CODE (reg) == SUBREG
|| GET_CODE (reg) == ZERO_EXTRACT
|| GET_CODE (reg) == STRICT_LOW_PART)
reg = XEXP (reg, 0);
if (GET_CODE (reg) == PARALLEL)
{
int i;
for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
return 1;
return 0;
}
if (!REG_P (reg))
return 1;
regno = REGNO (reg);
if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
{
return 0;
}
else
{
if (regno < FIRST_PSEUDO_REGISTER)
{
int j = hard_regno_nregs[regno][GET_MODE (reg)];
while (--j >= 0)
{
for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
{
basic_block b = candidate_table[src].split_bbs.first_member[i];
gcc_assert (glat_start[b->index]
|| CONTAINING_RGN (b->index)
!= CONTAINING_RGN (BB_TO_BLOCK (src)));
if (!glat_start[b->index]
|| REGNO_REG_SET_P (glat_start[b->index],
regno + j))
{
return 0;
}
}
}
}
else
{
for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
{
basic_block b = candidate_table[src].split_bbs.first_member[i];
gcc_assert (glat_start[b->index]
|| CONTAINING_RGN (b->index)
!= CONTAINING_RGN (BB_TO_BLOCK (src)));
if (!glat_start[b->index]
|| REGNO_REG_SET_P (glat_start[b->index], regno))
{
return 0;
}
}
}
}
return 1;
}
static void
update_live_1 (int src, rtx x)
{
int i;
int regno;
rtx reg = SET_DEST (x);
if (reg == 0)
return;
while (GET_CODE (reg) == SUBREG
|| GET_CODE (reg) == ZERO_EXTRACT
|| GET_CODE (reg) == STRICT_LOW_PART)
reg = XEXP (reg, 0);
if (GET_CODE (reg) == PARALLEL)
{
int i;
for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
return;
}
if (!REG_P (reg))
return;
regno = REGNO (reg);
if (regno >= FIRST_PSEUDO_REGISTER || !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 (glat_start[b->index], regno + j);
}
}
}
else
{
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 (glat_start[b->index], regno);
}
}
}
}
static int
check_live (rtx insn, int src)
{
if (GET_CODE (PATTERN (insn)) == SET
|| GET_CODE (PATTERN (insn)) == CLOBBER)
return check_live_1 (src, PATTERN (insn));
else if (GET_CODE (PATTERN (insn)) == PARALLEL)
{
int j;
for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
|| GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
&& !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
return 0;
return 1;
}
return 1;
}
static void
update_live (rtx insn, int src)
{
if (GET_CODE (PATTERN (insn)) == SET
|| GET_CODE (PATTERN (insn)) == CLOBBER)
update_live_1 (src, PATTERN (insn));
else if (GET_CODE (PATTERN (insn)) == PARALLEL)
{
int j;
for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
|| GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
}
}
#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)))))))
static void
set_spec_fed (rtx load_insn)
{
rtx link;
for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
if (GET_MODE (link) == VOIDmode)
FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
}
static int
find_conditional_protection (rtx insn, int load_insn_bb)
{
rtx link;
for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
{
rtx next = XEXP (link, 0);
if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
&& IS_REACHABLE (INSN_BB (next), load_insn_bb)
&& load_insn_bb != INSN_BB (next)
&& GET_MODE (link) == VOIDmode
&& (JUMP_P (next)
|| find_conditional_protection (next, load_insn_bb)))
return 1;
}
return 0;
}
static int
is_conditionally_protected (rtx load_insn, int bb_src, int bb_trg)
{
rtx link;
for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
{
rtx insn1 = XEXP (link, 0);
if (GET_MODE (link) != VOIDmode
|| JUMP_P (insn1))
continue;
if (INSN_BB (insn1) == bb_src
|| (CONTAINING_RGN (BLOCK_NUM (insn1))
!= CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
|| (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
&& !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
continue;
if (find_conditional_protection (insn1, bb_src))
return 1;
return is_conditionally_protected (insn1, bb_src, bb_trg);
}
return 0;
}
static int
is_pfree (rtx load_insn, int bb_src, int bb_trg)
{
rtx back_link;
candidate *candp = candidate_table + bb_src;
if (candp->split_bbs.nr_members != 1)
return 0;
for (back_link = LOG_LINKS (load_insn);
back_link; back_link = XEXP (back_link, 1))
{
rtx insn1 = XEXP (back_link, 0);
if (GET_MODE (back_link) == VOIDmode)
{
rtx fore_link;
for (fore_link = INSN_DEPEND (insn1);
fore_link; fore_link = XEXP (fore_link, 1))
{
rtx insn2 = XEXP (fore_link, 0);
if (GET_MODE (fore_link) == VOIDmode)
{
if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
continue;
if (INSN_BB (insn2) == bb_trg)
return 1;
if (*(candp->split_bbs.first_member) == BLOCK_FOR_INSN (insn2))
return 1;
}
}
}
}
return 0;
}
static int
is_prisky (rtx load_insn, int bb_src, int bb_trg)
{
if (FED_BY_SPEC_LOAD (load_insn))
return 1;
if (LOG_LINKS (load_insn) == NULL)
return 1;
if (is_conditionally_protected (load_insn, bb_src, bb_trg))
return 1;
return 0;
}
static int
is_exception_free (rtx insn, int bb_src, int bb_trg)
{
int insn_class = haifa_classify_insn (insn);
switch (insn_class)
{
case TRAP_FREE:
return 1;
case TRAP_RISKY:
return 0;
default:;
}
if (!flag_schedule_speculative_load)
return 0;
IS_LOAD_INSN (insn) = 1;
switch (insn_class)
{
case IFREE:
return (1);
case IRISKY:
return 0;
case PFREE_CANDIDATE:
if (is_pfree (insn, bb_src, bb_trg))
return 1;
case PRISKY_CANDIDATE:
if (!flag_schedule_speculative_load_dangerous
|| is_prisky (insn, bb_src, bb_trg))
return 0;
break;
default:;
}
return flag_schedule_speculative_load_dangerous;
}
static int sched_target_n_insns;
static int target_n_insns;
static int sched_n_insns;
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 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 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 check_dead_notes1 (int, sbitmap);
#ifdef ENABLE_CHECKING
static int region_head_or_leaf_p (basic_block, int);
#endif
static int
schedule_more_p (void)
{
return sched_target_n_insns < target_n_insns;
}
static void
init_ready_list (void)
{
rtx prev_head = current_sched_info->prev_head;
rtx next_tail = current_sched_info->next_tail;
int bb_src;
rtx insn;
target_n_insns = 0;
sched_target_n_insns = 0;
sched_n_insns = 0;
if (sched_verbose >= 5)
debug_dependencies ();
if (current_nr_blocks > 1)
{
candidate_table = XNEWVEC (candidate, current_nr_blocks);
bblst_last = 0;
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);
}
for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
{
try_ready (insn);
target_n_insns++;
gcc_assert (!(TODO_SPEC (insn) & BEGIN_CONTROL));
}
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;
get_ebb_head_tail (EBB_FIRST_BB (bb_src), EBB_LAST_BB (bb_src),
&head, &tail);
src_next_tail = NEXT_INSN (tail);
src_head = head;
for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
if (INSN_P (insn))
try_ready (insn);
}
}
static int
can_schedule_ready_p (rtx insn)
{
if (INSN_BB (insn) != target_bb
&& IS_SPECULATIVE_INSN (insn)
&& !check_live (insn, INSN_BB (insn)))
return 0;
else
return 1;
}
static void
begin_schedule_ready (rtx insn, rtx last ATTRIBUTE_UNUSED)
{
if (INSN_BB (insn) != target_bb)
{
if (IS_SPECULATIVE_INSN (insn))
{
gcc_assert (check_live (insn, INSN_BB (insn)));
update_live (insn, INSN_BB (insn));
if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
set_spec_fed (insn);
nr_spec++;
}
nr_inter++;
}
else
{
sched_target_n_insns++;
}
sched_n_insns++;
}
static ds_t
new_ready (rtx next, ds_t ts)
{
if (INSN_BB (next) != target_bb)
{
int not_ex_free = 0;
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)
> PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY))
|| IS_SPECULATION_CHECK_P (next)
|| !check_live (next, INSN_BB (next))
|| (not_ex_free = !is_exception_free (next, INSN_BB (next),
target_bb)))))
{
if (not_ex_free
&& current_sched_info->flags & DO_SPECULATION)
ts = set_dep_weak (ts, BEGIN_CONTROL, MAX_DEP_WEAK);
else
ts = (ts & ~SPECULATIVE) | HARD_DEP;
}
}
return ts;
}
static const char *
rgn_print_insn (rtx insn, int aligned)
{
static char tmp[80];
if (aligned)
sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
else
{
if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
else
sprintf (tmp, "%d", INSN_UID (insn));
}
return tmp;
}
static int
rgn_rank (rtx insn1, rtx insn2)
{
if (INSN_BB (insn1) != INSN_BB (insn2))
{
int spec_val, prob_val;
if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
return 1;
if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
return -1;
spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
if (spec_val)
return spec_val;
prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
if (prob_val)
return prob_val;
}
return 0;
}
static int
contributes_to_priority (rtx next, rtx insn)
{
return BLOCK_TO_BB (BLOCK_NUM (next)) == BLOCK_TO_BB (BLOCK_NUM (insn));
}
static void
compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
regset cond_exec ATTRIBUTE_UNUSED,
regset used ATTRIBUTE_UNUSED,
regset set ATTRIBUTE_UNUSED)
{
}
static struct sched_info region_sched_info =
{
init_ready_list,
can_schedule_ready_p,
schedule_more_p,
new_ready,
rgn_rank,
rgn_print_insn,
contributes_to_priority,
compute_jump_reg_dependencies,
NULL, NULL,
NULL, NULL,
0, 0, 0,
add_remove_insn,
begin_schedule_ready,
add_block1,
advance_target_bb,
fix_recovery_cfg,
#ifdef ENABLE_CHECKING
region_head_or_leaf_p,
#endif
SCHED_RGN | USE_GLAT
#ifdef ENABLE_CHECKING
| DETACH_LIFE_INFO
#endif
};
static bool
sets_likely_spilled (rtx pat)
{
bool ret = false;
note_stores (pat, sets_likely_spilled_1, &ret);
return ret;
}
static void
sets_likely_spilled_1 (rtx x, rtx pat, void *data)
{
bool *ret = (bool *) data;
if (GET_CODE (pat) == SET
&& REG_P (x)
&& REGNO (x) < FIRST_PSEUDO_REGISTER
&& CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x))))
*ret = true;
}
static void
add_branch_dependences (rtx head, rtx tail)
{
rtx insn, last;
insn = tail;
last = 0;
while (CALL_P (insn)
|| JUMP_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
|| (!reload_completed
&& sets_likely_spilled (PATTERN (insn)))))
|| NOTE_P (insn))
{
if (!NOTE_P (insn))
{
if (last != 0 && !find_insn_list (insn, LOG_LINKS (last)))
{
if (! sched_insns_conditions_mutex_p (last, insn))
add_dependence (last, insn, REG_DEP_ANTI);
INSN_REF_COUNT (insn)++;
}
CANT_MOVE (insn) = 1;
last = insn;
}
if (insn == head)
break;
insn = PREV_INSN (insn);
}
insn = last;
if (insn != 0)
while (insn != head)
{
insn = prev_nonnote_insn (insn);
if (INSN_REF_COUNT (insn) != 0)
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 (!reload_completed || ! JUMP_P (tail))
return;
insn = tail;
while (insn != head)
{
insn = PREV_INSN (insn);
if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC)
add_dependence (tail, insn, REG_DEP_ANTI);
}
#endif
}
static struct deps *bb_deps;
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 void
concat_insn_mem_list (rtx copy_insns, rtx copy_mems, rtx *old_insns_p,
rtx *old_mems_p)
{
rtx new_insns = *old_insns_p;
rtx 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);
}
*old_insns_p = new_insns;
*old_mems_p = new_mems;
}
static void
propagate_deps (int bb, struct deps *pred_deps)
{
basic_block block = BASIC_BLOCK (BB_TO_BLOCK (bb));
edge_iterator ei;
edge e;
FOR_EACH_EDGE (e, ei, block->succs)
{
struct deps *succ_deps;
unsigned reg;
reg_set_iterator rsi;
if (e->dest == EXIT_BLOCK_PTR
|| 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);
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);
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_lists_length += pred_deps->pending_lists_length;
succ_deps->pending_flush_length += pred_deps->pending_flush_length;
succ_deps->last_function_call
= concat_INSN_LIST (pred_deps->last_function_call,
succ_deps->last_function_call);
succ_deps->sched_before_next_call
= concat_INSN_LIST (pred_deps->sched_before_next_call,
succ_deps->sched_before_next_call);
}
bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
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;
pred_deps->pending_read_insns = 0;
pred_deps->pending_read_mems = 0;
pred_deps->pending_write_insns = 0;
pred_deps->pending_write_mems = 0;
}
static void
compute_block_backward_dependences (int bb)
{
rtx head, tail;
struct deps tmp_deps;
tmp_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);
sched_analyze (&tmp_deps, head, tail);
add_branch_dependences (head, tail);
if (current_nr_blocks > 1)
propagate_deps (bb, &tmp_deps);
free_deps (&tmp_deps);
}
static void
free_pending_lists (void)
{
int bb;
for (bb = 0; bb < current_nr_blocks; bb++)
{
free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
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);
}
}
void
debug_dependencies (void)
{
int bb;
fprintf (sched_dump, ";; --------------- forward dependences: ------------ \n");
for (bb = 0; bb < current_nr_blocks; bb++)
{
rtx head, tail;
rtx next_tail;
rtx insn;
gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
next_tail = NEXT_INSN (tail);
fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
BB_TO_BLOCK (bb), bb);
fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
"insn", "code", "bb", "dep", "prio", "cost",
"reservation");
fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
"----", "----", "--", "---", "----", "----",
"-----------");
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
{
rtx link;
if (! INSN_P (insn))
{
int n;
fprintf (sched_dump, ";; %6d ", INSN_UID (insn));
if (NOTE_P (insn))
{
n = NOTE_LINE_NUMBER (insn);
if (n < 0)
fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
else
{
expanded_location xloc;
NOTE_EXPANDED_LOCATION (xloc, insn);
fprintf (sched_dump, "line %d, file %s\n",
xloc.line, xloc.file);
}
}
else
fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
continue;
}
fprintf (sched_dump,
";; %s%5d%6d%6d%6d%6d%6d ",
(SCHED_GROUP_P (insn) ? "+" : " "),
INSN_UID (insn),
INSN_CODE (insn),
INSN_BB (insn),
INSN_DEP_COUNT (insn),
INSN_PRIORITY (insn),
insn_cost (insn, 0, 0));
if (recog_memoized (insn) < 0)
fprintf (sched_dump, "nothing");
else
print_reservation (sched_dump, insn);
fprintf (sched_dump, "\t: ");
for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
fprintf (sched_dump, "%d ", INSN_UID (XEXP (link, 0)));
fprintf (sched_dump, "\n");
}
}
fprintf (sched_dump, "\n");
}
static 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))
return false;
return true;
}
static void
schedule_region (int rgn)
{
basic_block block;
edge_iterator ei;
edge e;
int bb;
int sched_rgn_n_insns = 0;
rgn_n_insns = 0;
current_nr_blocks = RGN_NR_BLOCKS (rgn);
current_blocks = RGN_BLOCKS (rgn);
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;
if (sched_is_disabled_for_current_region_p ())
return;
if (!RGN_DONT_CALC_DEPS (rgn))
{
init_deps_global ();
bb_deps = XNEWVEC (struct deps, current_nr_blocks);
for (bb = 0; bb < current_nr_blocks; bb++)
init_deps (bb_deps + bb);
for (bb = 0; bb < current_nr_blocks; bb++)
compute_block_backward_dependences (bb);
for (bb = current_nr_blocks - 1; bb >= 0; bb--)
{
rtx head, tail;
gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
compute_forward_dependences (head, tail);
if (targetm.sched.dependencies_evaluation_hook)
targetm.sched.dependencies_evaluation_hook (head, tail);
}
free_pending_lists ();
finish_deps_global ();
free (bb_deps);
}
else
gcc_assert (current_nr_blocks == 1);
current_sched_info->sched_max_insns_priority = 0;
for (bb = 0; bb < current_nr_blocks; bb++)
{
rtx head, tail;
gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
rgn_n_insns += set_priorities (head, tail);
}
current_sched_info->sched_max_insns_priority++;
if (current_nr_blocks > 1)
{
prob = XNEWVEC (int, current_nr_blocks);
dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
sbitmap_vector_zero (dom, current_nr_blocks);
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++);
}
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;
}
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);
for (bb = 0; bb < current_nr_blocks; bb++)
compute_dom_prob_ps (bb);
FOR_EACH_BB (block)
{
if (CONTAINING_RGN (block->index) != rgn)
continue;
FOR_EACH_EDGE (e, ei, block->succs)
e->aux = NULL;
}
}
for (bb = 0; bb < current_nr_blocks; bb++)
{
basic_block first_bb, last_bb, curr_bb;
rtx head, tail;
int b = BB_TO_BLOCK (bb);
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;
}
current_sched_info->prev_head = PREV_INSN (head);
current_sched_info->next_tail = NEXT_INSN (tail);
if (write_symbols != NO_DEBUG)
{
save_line_notes (b, head, tail);
rm_line_notes (head, tail);
}
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
gcc_unreachable ();
rm_other_notes (head, tail);
unlink_bb_notes (first_bb, last_bb);
target_bb = bb;
gcc_assert (flag_schedule_interblock || current_nr_blocks == 1);
current_sched_info->queue_must_finish_empty = current_nr_blocks == 1;
curr_bb = first_bb;
schedule_block (&curr_bb, rgn_n_insns);
gcc_assert (EBB_FIRST_BB (bb) == first_bb);
sched_rgn_n_insns += sched_n_insns;
if (current_nr_blocks > 1)
{
free (candidate_table);
free (bblst_table);
free (edgelst_table);
}
}
gcc_assert (sched_rgn_n_insns == rgn_n_insns);
if (write_symbols != NO_DEBUG)
{
for (bb = 0; bb < current_nr_blocks; bb++)
{
rtx head, tail;
get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
restore_line_notes (head, tail);
}
}
if (current_nr_blocks > 1)
{
free (prob);
sbitmap_vector_free (dom);
sbitmap_vector_free (pot_split);
sbitmap_vector_free (ancestor_edges);
free (rgn_edges);
}
}
static int *deaths_in_region;
static void
init_regions (void)
{
sbitmap blocks;
int rgn;
nr_regions = 0;
rgn_table = 0;
rgn_bb_table = 0;
block_to_bb = 0;
containing_rgn = 0;
extend_regions ();
if (reload_completed
|| n_basic_blocks == NUM_FIXED_BLOCKS + 1
|| !flag_schedule_interblock
|| is_cfg_nonregular ())
{
find_single_block_region ();
}
else
{
calculate_dominance_info (CDI_DOMINATORS);
find_rgns ();
if (sched_verbose >= 3)
debug_regions ();
free_dominance_info (CDI_DOMINATORS);
}
RGN_BLOCKS (nr_regions) = RGN_BLOCKS (nr_regions - 1) +
RGN_NR_BLOCKS (nr_regions - 1);
if (CHECK_DEAD_NOTES)
{
blocks = sbitmap_alloc (last_basic_block);
deaths_in_region = XNEWVEC (int, nr_regions);
for (rgn = 0; rgn < nr_regions; rgn++)
check_dead_notes1 (rgn, blocks);
sbitmap_free (blocks);
}
else
count_or_remove_death_notes (NULL, 1);
}
void
schedule_insns (void)
{
sbitmap large_region_blocks, blocks;
int rgn;
int any_large_regions;
basic_block bb;
if (n_basic_blocks == NUM_FIXED_BLOCKS)
return;
nr_inter = 0;
nr_spec = 0;
current_sched_info = ®ion_sched_info;
sched_init ();
min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE)
/ 100);
init_regions ();
ebb_head = 0;
for (rgn = 0; rgn < nr_regions; rgn++)
schedule_region (rgn);
free(ebb_head);
if (current_sched_info->flags & DETACH_LIFE_INFO)
attach_life_info ();
allocate_reg_life_data ();
any_large_regions = 0;
large_region_blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (large_region_blocks);
FOR_EACH_BB (bb)
SET_BIT (large_region_blocks, bb->index);
blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (blocks);
for (rgn = 0; rgn < nr_regions; rgn++)
if (RGN_NR_BLOCKS (rgn) > 1
|| RGN_HAS_REAL_EBB (rgn)
|| !glat_start[rgn_bb_table[RGN_BLOCKS (rgn)]])
any_large_regions = 1;
else
{
SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
RESET_BIT (large_region_blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
}
update_life_info (blocks, UPDATE_LIFE_LOCAL,
(reload_completed ? PROP_DEATH_NOTES
: (PROP_DEATH_NOTES | PROP_REG_INFO)));
if (any_large_regions)
{
update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL,
(reload_completed ? PROP_DEATH_NOTES
: (PROP_DEATH_NOTES | PROP_REG_INFO)));
#ifdef ENABLE_CHECKING
check_reg_live (true);
#endif
}
if (CHECK_DEAD_NOTES)
{
for (rgn = 0; rgn < nr_regions; rgn++)
if (RGN_NR_BLOCKS (rgn) == 1)
{
sbitmap_zero (blocks);
SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
gcc_assert (deaths_in_region[rgn]
== count_or_remove_death_notes (blocks, 0));
}
free (deaths_in_region);
}
if (reload_completed)
reposition_prologue_and_epilogue_notes (get_insns ());
if (write_symbols != NO_DEBUG)
rm_redundant_line_notes ();
if (sched_verbose)
{
if (reload_completed == 0 && flag_schedule_interblock)
{
fprintf (sched_dump,
"\n;; Procedure interblock/speculative motions == %d/%d \n",
nr_inter, nr_spec);
}
else
gcc_assert (nr_inter <= 0);
fprintf (sched_dump, "\n\n");
}
free (rgn_table);
free (rgn_bb_table);
free (block_to_bb);
free (containing_rgn);
sched_finish ();
sbitmap_free (blocks);
sbitmap_free (large_region_blocks);
}
static void
add_remove_insn (rtx insn, int remove_p)
{
if (!remove_p)
rgn_n_insns++;
else
rgn_n_insns--;
if (INSN_BB (insn) == target_bb)
{
if (!remove_p)
target_n_insns++;
else
target_n_insns--;
}
}
static 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);
}
static void
add_block1 (basic_block bb, basic_block after)
{
extend_regions ();
if (after == 0 || after == EXIT_BLOCK_PTR)
{
int i;
i = RGN_BLOCKS (nr_regions);
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;
if (CHECK_DEAD_NOTES)
{
sbitmap blocks = sbitmap_alloc (last_basic_block);
deaths_in_region = xrealloc (deaths_in_region, nr_regions *
sizeof (*deaths_in_region));
check_dead_notes1 (nr_regions - 1, blocks);
sbitmap_free (blocks);
}
}
else
{
int i, pos;
BLOCK_TO_BB (bb->index) = BLOCK_TO_BB (after->index);
i = BLOCK_TO_BB (after->index) + 1;
pos = ebb_head[i] - 1;
for (; rgn_bb_table[pos] != after->index; pos--);
pos++;
gcc_assert (pos > ebb_head[i - 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++)
RGN_BLOCKS (i)++;
}
}
static void
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--);
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++;
gcc_assert (new_pos > ebb_head[BLOCK_TO_BB (bbi)]);
gcc_assert (new_pos < old_pos);
memmove (rgn_bb_table + new_pos + 1,
rgn_bb_table + new_pos,
(old_pos - new_pos) * sizeof (*rgn_bb_table));
rgn_bb_table[new_pos] = check_bb_nexti;
for (i = BLOCK_TO_BB (bbi) + 1; i <= BLOCK_TO_BB (check_bbi); i++)
ebb_head[i]++;
}
static basic_block
advance_target_bb (basic_block bb, rtx insn)
{
if (insn)
return 0;
gcc_assert (BLOCK_TO_BB (bb->index) == target_bb
&& BLOCK_TO_BB (bb->next_bb->index) == target_bb);
return bb->next_bb;
}
static void
check_dead_notes1 (int rgn, sbitmap blocks)
{
int b;
sbitmap_zero (blocks);
for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]);
deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1);
}
#ifdef ENABLE_CHECKING
static int
region_head_or_leaf_p (basic_block bb, int leaf_p)
{
if (!leaf_p)
return bb->index == rgn_bb_table[RGN_BLOCKS (CONTAINING_RGN (bb->index))];
else
{
int i;
edge e;
edge_iterator ei;
i = CONTAINING_RGN (bb->index);
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest != EXIT_BLOCK_PTR
&& CONTAINING_RGN (e->dest->index) == i
&& e->dest != bb)
return 0;
return 1;
}
}
#endif
#endif
static bool
gate_handle_sched (void)
{
#ifdef INSN_SCHEDULING
return flag_schedule_insns;
#else
return 0;
#endif
}
static unsigned int
rest_of_handle_sched (void)
{
#ifdef INSN_SCHEDULING
schedule_insns ();
#endif
return 0;
}
static bool
gate_handle_sched2 (void)
{
#ifdef INSN_SCHEDULING
return optimize > 0 && flag_schedule_insns_after_reload;
#else
return 0;
#endif
}
static unsigned int
rest_of_handle_sched2 (void)
{
#ifdef INSN_SCHEDULING
split_all_insns (1);
if (flag_sched2_use_superblocks || flag_sched2_use_traces)
{
schedule_ebbs ();
count_or_remove_death_notes (NULL, 1);
cleanup_cfg (CLEANUP_EXPENSIVE);
}
else
schedule_insns ();
#endif
return 0;
}
struct tree_opt_pass pass_sched =
{
"sched1",
gate_handle_sched,
rest_of_handle_sched,
NULL,
NULL,
0,
TV_SCHED,
0,
0,
0,
0,
TODO_dump_func |
TODO_ggc_collect,
'S'
};
struct tree_opt_pass pass_sched2 =
{
"sched2",
gate_handle_sched2,
rest_of_handle_sched2,
NULL,
NULL,
0,
TV_SCHED2,
0,
0,
0,
0,
TODO_dump_func |
TODO_ggc_collect,
'R'
};