#include "config.h"
#include "system.h"
#include "toplev.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "basic-block.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 "sched-int.h"
#include "target.h"
#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)
#define MAX_RGN_BLOCKS 10
#define MAX_RGN_INSNS 100
static int nr_inter, nr_spec;
typedef struct
{
int from_block;
int to_block;
int next_in;
int next_out;
}
haifa_edge;
static haifa_edge *edge_table;
#define NEXT_IN(edge) (edge_table[edge].next_in)
#define NEXT_OUT(edge) (edge_table[edge].next_out)
#define FROM_BLOCK(edge) (edge_table[edge].from_block)
#define TO_BLOCK(edge) (edge_table[edge].to_block)
static int nr_edges;
static int *in_edges;
static int *out_edges;
#define IN_EDGES(block) (in_edges[block])
#define OUT_EDGES(block) (out_edges[block])
static int is_cfg_nonregular PARAMS ((void));
static int build_control_flow PARAMS ((struct edge_list *));
static void new_edge PARAMS ((int, int));
typedef struct
{
int rgn_nr_blocks;
int rgn_blocks;
}
region;
static int nr_regions;
static region *rgn_table;
static int *rgn_bb_table;
static int *block_to_bb;
static int *containing_rgn;
#define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
#define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
#define BLOCK_TO_BB(block) (block_to_bb[block])
#define CONTAINING_RGN(block) (containing_rgn[block])
void debug_regions PARAMS ((void));
static void find_single_block_region PARAMS ((void));
static void find_rgns PARAMS ((struct edge_list *, dominance_info));
static int too_large PARAMS ((int, int *, int *));
extern void debug_live PARAMS ((int, int));
static int current_nr_blocks;
static int current_blocks;
#define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
typedef struct
{
int *first_member;
int nr_members;
}
bitlst;
static int bitlst_table_last;
static int *bitlst_table;
static void extract_bitlst PARAMS ((sbitmap, bitlst *));
typedef bitlst bblst;
typedef struct
{
char is_valid;
char is_speculative;
int src_prob;
bblst split_bbs;
bblst update_bbs;
}
candidate;
static candidate *candidate_table;
static int *bblst_table, 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 bitlst edgelst;
static void split_edges PARAMS ((int, int, edgelst *));
static void compute_trg_info PARAMS ((int));
void debug_candidate PARAMS ((int));
void debug_candidates PARAMS ((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 float *prob;
#define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
prob[bb_trg])))
typedef sbitmap edgeset;
static int rgn_nr_edges;
static int *rgn_edges;
static int *edge_to_bit;
#define EDGE_TO_BIT(edge) (edge_to_bit[edge])
static edgeset *pot_split;
static edgeset *ancestor_edges;
static void compute_dom_prob_ps PARAMS ((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)))
#define MIN_PROBABILITY 40
static int check_live_1 PARAMS ((int, rtx));
static void update_live_1 PARAMS ((int, rtx));
static int check_live PARAMS ((rtx, int));
static void update_live PARAMS ((rtx, int));
static void set_spec_fed PARAMS ((rtx));
static int is_pfree PARAMS ((rtx, int, int));
static int find_conditional_protection PARAMS ((rtx, int));
static int is_conditionally_protected PARAMS ((rtx, int, int));
static int may_trap_exp PARAMS ((rtx, int));
static int haifa_classify_insn PARAMS ((rtx));
static int is_prisky PARAMS ((rtx, int, int));
static int is_exception_free PARAMS ((rtx, int, int));
static bool sets_likely_spilled PARAMS ((rtx));
static void sets_likely_spilled_1 PARAMS ((rtx, rtx, void *));
static void add_branch_dependences PARAMS ((rtx, rtx));
static void compute_block_backward_dependences PARAMS ((int));
void debug_dependencies PARAMS ((void));
static void init_regions PARAMS ((void));
static void schedule_region PARAMS ((int));
static rtx concat_INSN_LIST PARAMS ((rtx, rtx));
static void concat_insn_mem_list PARAMS ((rtx, rtx, rtx *, rtx *));
static void propagate_deps PARAMS ((int, struct deps *));
static void free_pending_lists PARAMS ((void));
static int
is_cfg_nonregular ()
{
basic_block b;
rtx insn;
RTX_CODE code;
if (nonlocal_goto_handler_labels)
return 1;
if (forced_labels)
return 1;
if (current_function_has_computed_jump)
return 1;
if (current_function_has_exception_handlers ())
return 1;
FOR_EACH_BB (b)
for (insn = b->head;; insn = NEXT_INSN (insn))
{
code = GET_CODE (insn);
if (GET_RTX_CLASS (code) == 'i' && code != JUMP_INSN)
{
rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
if (note
&& ! (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
&& find_reg_note (NEXT_INSN (insn), REG_LABEL,
XEXP (note, 0))))
return 1;
}
if (insn == b->end)
break;
}
return 0;
}
static int
build_control_flow (edge_list)
struct edge_list *edge_list;
{
int i, unreachable, num_edges;
basic_block b;
num_edges = NUM_EDGES (edge_list);
unreachable = 0;
FOR_EACH_BB (b)
{
if (b->pred == NULL
|| (b->pred->src == b
&& b->pred->pred_next == NULL))
unreachable = 1;
}
in_edges = (int *) xcalloc (last_basic_block, sizeof (int));
out_edges = (int *) xcalloc (last_basic_block, sizeof (int));
edge_table = (haifa_edge *) xcalloc (num_edges, sizeof (haifa_edge));
nr_edges = 0;
for (i = 0; i < num_edges; i++)
{
edge e = INDEX_EDGE (edge_list, i);
if (e->dest != EXIT_BLOCK_PTR
&& e->src != ENTRY_BLOCK_PTR)
new_edge (e->src->index, e->dest->index);
}
nr_edges++;
return unreachable;
}
static void
new_edge (source, target)
int source, target;
{
int e, next_edge;
int curr_edge, fst_edge;
fst_edge = curr_edge = OUT_EDGES (source);
while (curr_edge)
{
if (FROM_BLOCK (curr_edge) == source
&& TO_BLOCK (curr_edge) == target)
{
return;
}
curr_edge = NEXT_OUT (curr_edge);
if (fst_edge == curr_edge)
break;
}
e = ++nr_edges;
FROM_BLOCK (e) = source;
TO_BLOCK (e) = target;
if (OUT_EDGES (source))
{
next_edge = NEXT_OUT (OUT_EDGES (source));
NEXT_OUT (OUT_EDGES (source)) = e;
NEXT_OUT (e) = next_edge;
}
else
{
OUT_EDGES (source) = e;
NEXT_OUT (e) = e;
}
if (IN_EDGES (target))
{
next_edge = NEXT_IN (IN_EDGES (target));
NEXT_IN (IN_EDGES (target)) = e;
NEXT_IN (e) = next_edge;
}
else
{
IN_EDGES (target) = e;
NEXT_IN (e) = e;
}
}
static void
extract_bitlst (set, bl)
sbitmap set;
bitlst *bl;
{
int i;
bitlst_table_last = 0;
bl->first_member = &bitlst_table[bitlst_table_last];
bl->nr_members = 0;
EXECUTE_IF_SET_IN_SBITMAP (set, 0, i,
{
bitlst_table[bitlst_table_last++] = i;
(bl->nr_members)++;
});
}
void
debug_regions ()
{
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: ");
for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
{
current_blocks = RGN_BLOCKS (rgn);
if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
abort ();
fprintf (sched_dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
}
fprintf (sched_dump, "\n\n");
}
}
static void
find_single_block_region ()
{
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;
CONTAINING_RGN (bb->index) = nr_regions;
BLOCK_TO_BB (bb->index) = 0;
nr_regions++;
}
}
static int
too_large (block, num_bbs, num_insns)
int block, *num_bbs, *num_insns;
{
(*num_bbs)++;
(*num_insns) += (INSN_LUID (BLOCK_END (block)) -
INSN_LUID (BLOCK_HEAD (block)));
if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
return 1;
else
return 0;
}
#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 (edge_list, dom)
struct edge_list *edge_list;
dominance_info dom;
{
int *max_hdr, *dfs_nr, *stack, *degree;
char no_loops = 1;
int node, child, loop_head, i, head, tail;
int count = 0, sp, idx = 0, current_edge = out_edges[0];
int num_bbs, num_insns, unreachable;
int too_large_failure;
basic_block bb;
sbitmap passed;
sbitmap header;
sbitmap inner;
sbitmap in_queue;
sbitmap in_stack;
int num_edges = NUM_EDGES (edge_list);
max_hdr = (int *) xmalloc (last_basic_block * sizeof (int));
dfs_nr = (int *) xcalloc (last_basic_block, sizeof (int));
stack = (int *) xmalloc (nr_edges * sizeof (int));
inner = sbitmap_alloc (last_basic_block);
sbitmap_ones (inner);
header = sbitmap_alloc (last_basic_block);
sbitmap_zero (header);
passed = sbitmap_alloc (nr_edges);
sbitmap_zero (passed);
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;
sp = -1;
while (1)
{
if (current_edge == 0 || TEST_BIT (passed, current_edge))
{
while (sp >= 0
&& (current_edge == 0 || TEST_BIT (passed, current_edge)))
{
current_edge = stack[sp--];
node = FROM_BLOCK (current_edge);
child = TO_BLOCK (current_edge);
RESET_BIT (in_stack, child);
if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
current_edge = NEXT_OUT (current_edge);
}
if (sp < 0 && TEST_BIT (passed, current_edge))
break;
continue;
}
node = FROM_BLOCK (current_edge);
child = TO_BLOCK (current_edge);
SET_BIT (in_stack, node);
dfs_nr[node] = ++count;
if (TEST_BIT (in_stack, child))
{
no_loops = 0;
SET_BIT (header, child);
UPDATE_LOOP_RELATIONS (node, child);
SET_BIT (passed, current_edge);
current_edge = NEXT_OUT (current_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_BIT (passed, current_edge);
current_edge = NEXT_OUT (current_edge);
continue;
}
stack[++sp] = current_edge;
SET_BIT (passed, current_edge);
current_edge = OUT_EDGES (child);
if (current_edge == 0)
dfs_nr[child] = ++count;
}
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] = 0;
for (i = 0; i < num_edges; i++)
{
edge e = INDEX_EDGE (edge_list, i);
if (e->dest != EXIT_BLOCK_PTR)
degree[e->dest->index]++;
}
if (!unreachable)
{
int *queue;
if (no_loops)
SET_BIT (header, 0);
queue = (int *) xmalloc (n_basic_blocks * sizeof (int));
FOR_EACH_BB (bb)
{
if (TEST_BIT (header, bb->index) && TEST_BIT (inner, bb->index))
{
edge e;
basic_block jbb;
FOR_EACH_BB (jbb)
{
if (bb->index == max_hdr[jbb->index] && bb != jbb)
{
if (!dominated_by_p (dom, jbb, bb))
break;
}
}
if (jbb != EXIT_BLOCK_PTR)
continue;
head = tail = -1;
too_large_failure = 0;
loop_head = max_hdr[bb->index];
for (e = bb->succ; e; e = e->succ_next)
if (e->dest != EXIT_BLOCK_PTR)
--degree[e->dest->index];
num_bbs = 1;
num_insns = (INSN_LUID (bb->end)
- INSN_LUID (bb->head));
if (no_loops)
{
FOR_EACH_BB (jbb)
if (jbb->succ
&& jbb->succ->dest == EXIT_BLOCK_PTR
&& jbb->succ->succ_next == NULL)
{
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 (e = bb->pred; e; e = e->pred_next)
{
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 (e = BASIC_BLOCK (child)->pred; e; e = e->pred_next)
{
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++;
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 (e = BASIC_BLOCK (child)->succ;
e;
e = e->succ_next)
if (e->dest != EXIT_BLOCK_PTR)
--degree[e->dest->index];
}
else
--head;
}
++nr_regions;
}
}
}
free (queue);
}
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++;
CONTAINING_RGN (bb->index) = nr_regions++;
BLOCK_TO_BB (bb->index) = 0;
}
free (max_hdr);
free (dfs_nr);
free (stack);
sbitmap_free (passed);
sbitmap_free (header);
sbitmap_free (inner);
sbitmap_free (in_queue);
sbitmap_free (in_stack);
}
static void
compute_dom_prob_ps (bb)
int bb;
{
int nxt_in_edge, fst_in_edge, pred;
int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
prob[bb] = 0.0;
if (IS_RGN_ENTRY (bb))
{
SET_BIT (dom[bb], 0);
prob[bb] = 1.0;
return;
}
fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
sbitmap_ones (dom[bb]);
do
{
pred = FROM_BLOCK (nxt_in_edge);
sbitmap_a_and_b (dom[bb], dom[bb], dom[BLOCK_TO_BB (pred)]);
sbitmap_a_or_b (ancestor_edges[bb], ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)]);
SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge));
nr_out_edges = 1;
nr_rgn_out_edges = 0;
fst_out_edge = OUT_EDGES (pred);
nxt_out_edge = NEXT_OUT (fst_out_edge);
sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[BLOCK_TO_BB (pred)]);
SET_BIT (pot_split[bb], EDGE_TO_BIT (fst_out_edge));
if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
CONTAINING_RGN (BB_TO_BLOCK (bb)))
++nr_rgn_out_edges;
while (fst_out_edge != nxt_out_edge)
{
++nr_out_edges;
if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
CONTAINING_RGN (BB_TO_BLOCK (bb)))
++nr_rgn_out_edges;
SET_BIT (pot_split[bb], EDGE_TO_BIT (nxt_out_edge));
nxt_out_edge = NEXT_OUT (nxt_out_edge);
}
nr_out_edges -= nr_rgn_out_edges;
if (nr_rgn_out_edges > 0)
prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
else
prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
nxt_in_edge = NEXT_IN (nxt_in_edge);
}
while (fst_in_edge != nxt_in_edge);
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),
(int) (100.0 * prob[bb]));
}
static void
split_edges (bb_src, bb_trg, bl)
int bb_src;
int bb_trg;
edgelst *bl;
{
sbitmap src = (edgeset) sbitmap_alloc (pot_split[bb_src]->n_bits);
sbitmap_copy (src, pot_split[bb_src]);
sbitmap_difference (src, src, pot_split[bb_trg]);
extract_bitlst (src, bl);
sbitmap_free (src);
}
static void
compute_trg_info (trg)
int trg;
{
candidate *sp;
edgelst el;
int check_block, update_idx;
int i, j, k, fst_edge, nxt_edge;
sp = candidate_table + trg;
sp->is_valid = 1;
sp->is_speculative = 0;
sp->src_prob = 100;
for (i = trg + 1; i < current_nr_blocks; i++)
{
sp = candidate_table + i;
sp->is_valid = IS_DOMINATED (i, trg);
if (sp->is_valid)
{
sp->src_prob = GET_SRC_PROB (i, trg);
sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
}
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)
{
char *update_blocks;
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] =
TO_BLOCK (rgn_edges[el.first_member[j]]);
sp->update_bbs.first_member = &bblst_table[bblst_last];
update_blocks = (char *) alloca (last_basic_block);
memset (update_blocks, 0, last_basic_block);
update_idx = 0;
for (j = 0; j < el.nr_members; j++)
{
check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
fst_edge = nxt_edge = OUT_EDGES (check_block);
do
{
if (! update_blocks[TO_BLOCK (nxt_edge)])
{
for (k = 0; k < el.nr_members; k++)
if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
break;
if (k >= el.nr_members)
{
bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
update_blocks[TO_BLOCK (nxt_edge)] = 1;
update_idx++;
}
}
nxt_edge = NEXT_OUT (nxt_edge);
}
while (fst_edge != nxt_edge);
}
sp->update_bbs.nr_members = update_idx;
if (bblst_last > bblst_size)
abort ();
}
else
{
sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
sp->is_speculative = 0;
sp->src_prob = 0;
}
}
}
void
debug_candidate (i)
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];
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];
fprintf (sched_dump, " %d ", b);
}
fprintf (sched_dump, "\n");
}
else
{
fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
}
}
void
debug_candidates (trg)
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 (src, x)
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) == SIGN_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 (GET_CODE (reg) != 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++)
{
int b = candidate_table[src].split_bbs.first_member[i];
if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
regno + j))
{
return 0;
}
}
}
}
else
{
for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
{
int b = candidate_table[src].split_bbs.first_member[i];
if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
{
return 0;
}
}
}
}
return 1;
}
static void
update_live_1 (src, x)
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) == SIGN_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 (GET_CODE (reg) != 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++)
{
int b = candidate_table[src].update_bbs.first_member[i];
SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
regno + j);
}
}
}
else
{
for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
{
int b = candidate_table[src].update_bbs.first_member[i];
SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
}
}
}
}
static int
check_live (insn, src)
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 (insn, src)
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));
}
}
enum INSN_TRAP_CLASS
{
TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
};
#define WORST_CLASS(class1, class2) \
((class1 > class2) ? class1 : class2)
#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 (IN_EDGES (BB_TO_BLOCK (bb_from))))))
#define CONST_BASED_ADDRESS_P(x) \
(GET_CODE (x) == REG \
|| ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
|| (GET_CODE (x) == LO_SUM)) \
&& (CONSTANT_P (XEXP (x, 0)) \
|| CONSTANT_P (XEXP (x, 1)))))
static void
set_spec_fed (load_insn)
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 (insn, load_insn_bb)
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
&& (GET_CODE (next) == JUMP_INSN
|| find_conditional_protection (next, load_insn_bb)))
return 1;
}
return 0;
}
static int
is_conditionally_protected (load_insn, bb_src, bb_trg)
rtx load_insn;
int bb_src, 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
|| GET_CODE (insn1) == JUMP_INSN)
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 (load_insn, bb_src, bb_trg)
rtx load_insn;
int bb_src, 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_NUM (insn2))
return 1;
}
}
}
}
return 0;
}
static int
may_trap_exp (x, is_store)
rtx x;
int is_store;
{
enum rtx_code code;
if (x == 0)
return TRAP_FREE;
code = GET_CODE (x);
if (is_store)
{
if (code == MEM && may_trap_p (x))
return TRAP_RISKY;
else
return TRAP_FREE;
}
if (code == MEM)
{
if (MEM_VOLATILE_P (x))
return IRISKY;
if (!may_trap_p (x))
return IFREE;
if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
return PFREE_CANDIDATE;
return PRISKY_CANDIDATE;
}
else
{
const char *fmt;
int i, insn_class = TRAP_FREE;
if (may_trap_p (x))
return TRAP_RISKY;
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
{
int tmp_class = may_trap_exp (XEXP (x, i), is_store);
insn_class = WORST_CLASS (insn_class, tmp_class);
}
else if (fmt[i] == 'E')
{
int j;
for (j = 0; j < XVECLEN (x, i); j++)
{
int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
insn_class = WORST_CLASS (insn_class, tmp_class);
if (insn_class == TRAP_RISKY || insn_class == IRISKY)
break;
}
}
if (insn_class == TRAP_RISKY || insn_class == IRISKY)
break;
}
return insn_class;
}
}
static int
haifa_classify_insn (insn)
rtx insn;
{
rtx pat = PATTERN (insn);
int tmp_class = TRAP_FREE;
int insn_class = TRAP_FREE;
enum rtx_code code;
if (GET_CODE (pat) == PARALLEL)
{
int i, len = XVECLEN (pat, 0);
for (i = len - 1; i >= 0; i--)
{
code = GET_CODE (XVECEXP (pat, 0, i));
switch (code)
{
case CLOBBER:
tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
break;
case SET:
tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
if (tmp_class == TRAP_RISKY)
break;
tmp_class
= WORST_CLASS (tmp_class,
may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)),
0));
break;
case COND_EXEC:
case TRAP_IF:
tmp_class = TRAP_RISKY;
break;
default:
;
}
insn_class = WORST_CLASS (insn_class, tmp_class);
if (insn_class == TRAP_RISKY || insn_class == IRISKY)
break;
}
}
else
{
code = GET_CODE (pat);
switch (code)
{
case CLOBBER:
tmp_class = may_trap_exp (XEXP (pat, 0), 1);
break;
case SET:
tmp_class = may_trap_exp (SET_DEST (pat), 1);
if (tmp_class == TRAP_RISKY)
break;
tmp_class =
WORST_CLASS (tmp_class,
may_trap_exp (SET_SRC (pat), 0));
break;
case COND_EXEC:
case TRAP_IF:
tmp_class = TRAP_RISKY;
break;
default:;
}
insn_class = tmp_class;
}
return insn_class;
}
static int
is_prisky (load_insn, bb_src, bb_trg)
rtx load_insn;
int bb_src, 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 (insn, bb_src, bb_trg)
rtx insn;
int bb_src, 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 int last_was_jump;
static void init_ready_list PARAMS ((struct ready_list *));
static int can_schedule_ready_p PARAMS ((rtx));
static int new_ready PARAMS ((rtx));
static int schedule_more_p PARAMS ((void));
static const char *rgn_print_insn PARAMS ((rtx, int));
static int rgn_rank PARAMS ((rtx, rtx));
static int contributes_to_priority PARAMS ((rtx, rtx));
static void compute_jump_reg_dependencies PARAMS ((rtx, regset));
static int
schedule_more_p ()
{
return ! last_was_jump && sched_target_n_insns < target_n_insns;
}
static void
init_ready_list (ready)
struct ready_list *ready;
{
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;
last_was_jump = 0;
if (sched_verbose >= 5)
debug_dependencies ();
if (current_nr_blocks > 1)
{
candidate_table = (candidate *) xmalloc (current_nr_blocks
* sizeof (candidate));
bblst_last = 0;
bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
bblst_table = (int *) xmalloc (bblst_size * sizeof (int));
bitlst_table_last = 0;
bitlst_table = (int *) xmalloc (rgn_nr_edges * sizeof (int));
compute_trg_info (target_bb);
}
for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
{
if (INSN_DEP_COUNT (insn) == 0)
ready_add (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;
get_block_head_tail (BB_TO_BLOCK (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))
continue;
if (!CANT_MOVE (insn)
&& (!IS_SPECULATIVE_INSN (insn)
|| ((((!targetm.sched.use_dfa_pipeline_interface
|| !(*targetm.sched.use_dfa_pipeline_interface) ())
&& insn_issue_delay (insn) <= 3)
|| (targetm.sched.use_dfa_pipeline_interface
&& (*targetm.sched.use_dfa_pipeline_interface) ()
&& (recog_memoized (insn) < 0
|| min_insn_conflict_delay (curr_state,
insn, insn) <= 3)))
&& check_live (insn, bb_src)
&& is_exception_free (insn, bb_src, target_bb))))
if (INSN_DEP_COUNT (insn) == 0)
ready_add (ready, insn);
}
}
}
static int
can_schedule_ready_p (insn)
rtx insn;
{
if (GET_CODE (insn) == JUMP_INSN)
last_was_jump = 1;
if (INSN_BB (insn) != target_bb)
{
basic_block b1;
if (IS_SPECULATIVE_INSN (insn))
{
if (!check_live (insn, INSN_BB (insn)))
return 0;
update_live (insn, INSN_BB (insn));
if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
set_spec_fed (insn);
nr_spec++;
}
nr_inter++;
b1 = BLOCK_FOR_INSN (insn);
if (insn == b1->head && insn == b1->end)
{
rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
b1->head = note;
b1->end = note;
}
else if (insn == b1->end)
{
b1->end = PREV_INSN (insn);
}
else if (insn == b1->head)
{
b1->head = NEXT_INSN (insn);
}
}
else
{
sched_target_n_insns++;
}
sched_n_insns++;
return 1;
}
static int
new_ready (next)
rtx next;
{
if (INSN_BB (next) != target_bb
&& (!IS_VALID (INSN_BB (next))
|| CANT_MOVE (next)
|| (IS_SPECULATIVE_INSN (next)
&& (0
|| (targetm.sched.use_dfa_pipeline_interface
&& (*targetm.sched.use_dfa_pipeline_interface) ()
&& recog_memoized (next) >= 0
&& min_insn_conflict_delay (curr_state, next,
next) > 3)
|| ((!targetm.sched.use_dfa_pipeline_interface
|| !(*targetm.sched.use_dfa_pipeline_interface) ())
&& insn_issue_delay (next) > 3)
|| !check_live (next, INSN_BB (next))
|| !is_exception_free (next, INSN_BB (next), target_bb)))))
return 0;
return 1;
}
static const char *
rgn_print_insn (insn, aligned)
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 (insn1, insn2)
rtx insn1, 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 (next, insn)
rtx next, insn;
{
return BLOCK_NUM (next) == BLOCK_NUM (insn);
}
static void
compute_jump_reg_dependencies (insn, set)
rtx insn 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
};
static bool
sets_likely_spilled (pat)
rtx pat;
{
bool ret = false;
note_stores (pat, sets_likely_spilled_1, &ret);
return ret;
}
static void
sets_likely_spilled_1 (x, pat, data)
rtx x, 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 (head, tail)
rtx head, tail;
{
rtx insn, last;
insn = tail;
last = 0;
while (GET_CODE (insn) == CALL_INSN
|| GET_CODE (insn) == JUMP_INSN
|| (GET_CODE (insn) == 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)))))
|| GET_CODE (insn) == NOTE)
{
if (GET_CODE (insn) != NOTE)
{
if (last != 0 && !find_insn_list (insn, LOG_LINKS (last)))
{
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;
add_dependence (last, insn, REG_DEP_ANTI);
INSN_REF_COUNT (insn) = 1;
}
}
static struct deps *bb_deps;
static rtx
concat_INSN_LIST (copy, old)
rtx copy, 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 (copy_insns, copy_mems, old_insns_p, old_mems_p)
rtx copy_insns, copy_mems;
rtx *old_insns_p, *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 (bb, pred_deps)
int bb;
struct deps *pred_deps;
{
int b = BB_TO_BLOCK (bb);
int e, first_edge;
first_edge = e = OUT_EDGES (b);
if (e > 0)
do
{
int b_succ = TO_BLOCK (e);
int bb_succ = BLOCK_TO_BB (b_succ);
struct deps *succ_deps = bb_deps + bb_succ;
int reg;
if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
|| bb_succ <= bb)
{
e = NEXT_OUT (e);
continue;
}
EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg,
{
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);
e = NEXT_OUT (e);
}
while (e != first_edge);
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 (bb)
int bb;
{
rtx head, tail;
struct deps tmp_deps;
tmp_deps = bb_deps[bb];
get_block_head_tail (BB_TO_BLOCK (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 ()
{
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 ()
{
int bb;
fprintf (sched_dump, ";; --------------- forward dependences: ------------ \n");
for (bb = 0; bb < current_nr_blocks; bb++)
{
if (1)
{
rtx head, tail;
rtx next_tail;
rtx insn;
get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
next_tail = NEXT_INSN (tail);
fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
BB_TO_BLOCK (bb), bb);
if (targetm.sched.use_dfa_pipeline_interface
&& (*targetm.sched.use_dfa_pipeline_interface) ())
{
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",
"----", "----", "--", "---", "----", "----",
"-----------");
}
else
{
fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
"insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\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 (GET_CODE (insn) == NOTE)
{
n = NOTE_LINE_NUMBER (insn);
if (n < 0)
fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
else
fprintf (sched_dump, "line %d, file %s\n", n,
NOTE_SOURCE_FILE (insn));
}
else
fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
continue;
}
if (targetm.sched.use_dfa_pipeline_interface
&& (*targetm.sched.use_dfa_pipeline_interface) ())
{
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);
}
else
{
int unit = insn_unit (insn);
int range
= (unit < 0
|| function_units[unit].blockage_range_function == 0
? 0
: function_units[unit].blockage_range_function (insn));
fprintf (sched_dump,
";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
(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),
(int) MIN_BLOCKAGE_COST (range),
(int) MAX_BLOCKAGE_COST (range));
insn_print_units (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 void
schedule_region (rgn)
int rgn;
{
int bb;
int rgn_n_insns = 0;
int sched_rgn_n_insns = 0;
current_nr_blocks = RGN_NR_BLOCKS (rgn);
current_blocks = RGN_BLOCKS (rgn);
init_deps_global ();
bb_deps = (struct deps *) xmalloc (sizeof (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;
get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
compute_forward_dependences (head, tail);
if (targetm.sched.dependencies_evaluation_hook)
targetm.sched.dependencies_evaluation_hook (head, tail);
}
for (bb = 0; bb < current_nr_blocks; bb++)
{
rtx head, tail;
get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
rgn_n_insns += set_priorities (head, tail);
}
if (current_nr_blocks > 1)
{
int i;
prob = (float *) xmalloc ((current_nr_blocks) * sizeof (float));
dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
sbitmap_vector_zero (dom, current_nr_blocks);
rgn_nr_edges = 0;
edge_to_bit = (int *) xmalloc (nr_edges * sizeof (int));
for (i = 1; i < nr_edges; i++)
if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
EDGE_TO_BIT (i) = rgn_nr_edges++;
rgn_edges = (int *) xmalloc (rgn_nr_edges * sizeof (int));
rgn_nr_edges = 0;
for (i = 1; i < nr_edges; i++)
if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
rgn_edges[rgn_nr_edges++] = i;
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 (bb = 0; bb < current_nr_blocks; bb++)
{
rtx head, tail;
int b = BB_TO_BLOCK (bb);
get_block_head_tail (b, &head, &tail);
if (no_real_insns_p (head, tail))
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);
note = XEXP (note, 1);
remove_note (head, note);
}
}
rm_other_notes (head, tail);
target_bb = bb;
current_sched_info->queue_must_finish_empty
= current_nr_blocks > 1 && !flag_schedule_interblock;
schedule_block (b, rgn_n_insns);
sched_rgn_n_insns += sched_n_insns;
if (head == BLOCK_HEAD (b))
BLOCK_HEAD (b) = current_sched_info->head;
if (tail == BLOCK_END (b))
BLOCK_END (b) = current_sched_info->tail;
if (current_nr_blocks > 1)
{
free (candidate_table);
free (bblst_table);
free (bitlst_table);
}
}
if (sched_rgn_n_insns != rgn_n_insns)
abort ();
if (write_symbols != NO_DEBUG)
{
for (bb = 0; bb < current_nr_blocks; bb++)
{
rtx head, tail;
get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
restore_line_notes (head, tail);
}
}
free_pending_lists ();
finish_deps_global ();
free (bb_deps);
if (current_nr_blocks > 1)
{
free (prob);
sbitmap_vector_free (dom);
sbitmap_vector_free (pot_split);
sbitmap_vector_free (ancestor_edges);
free (edge_to_bit);
free (rgn_edges);
}
}
static int *deaths_in_region;
static void
init_regions ()
{
sbitmap blocks;
int rgn;
nr_regions = 0;
rgn_table = (region *) xmalloc ((n_basic_blocks) * sizeof (region));
rgn_bb_table = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
block_to_bb = (int *) xmalloc ((last_basic_block) * sizeof (int));
containing_rgn = (int *) xmalloc ((last_basic_block) * sizeof (int));
if (reload_completed
|| n_basic_blocks == 1
|| !flag_schedule_interblock)
{
find_single_block_region ();
}
else
{
if (is_cfg_nonregular ())
{
find_single_block_region ();
}
else
{
dominance_info dom;
struct edge_list *edge_list;
edge_list = create_edge_list ();
dom = calculate_dominance_info (CDI_DOMINATORS);
if (build_control_flow (edge_list) != 0)
find_single_block_region ();
else
find_rgns (edge_list, dom);
if (sched_verbose >= 3)
debug_regions ();
free_edge_list (edge_list);
free_dominance_info (dom);
}
}
if (CHECK_DEAD_NOTES)
{
blocks = sbitmap_alloc (last_basic_block);
deaths_in_region = (int *) xmalloc (sizeof (int) * nr_regions);
for (rgn = 0; rgn < nr_regions; rgn++)
{
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);
}
sbitmap_free (blocks);
}
else
count_or_remove_death_notes (NULL, 1);
}
void
schedule_insns (dump_file)
FILE *dump_file;
{
sbitmap large_region_blocks, blocks;
int rgn;
int any_large_regions;
basic_block bb;
if (n_basic_blocks == 0)
return;
nr_inter = 0;
nr_spec = 0;
sched_init (dump_file);
init_regions ();
current_sched_info = ®ion_sched_info;
for (rgn = 0; rgn < nr_regions; rgn++)
schedule_region (rgn);
allocate_reg_life_data ();
compute_bb_for_insn ();
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)
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,
PROP_DEATH_NOTES | PROP_REG_INFO);
}
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)]);
if (deaths_in_region[rgn]
!= count_or_remove_death_notes (blocks, 0))
abort ();
}
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
{
if (nr_inter > 0)
abort ();
}
fprintf (sched_dump, "\n\n");
}
free (rgn_table);
free (rgn_bb_table);
free (block_to_bb);
free (containing_rgn);
sched_finish ();
if (edge_table)
{
free (edge_table);
edge_table = NULL;
}
if (in_edges)
{
free (in_edges);
in_edges = NULL;
}
if (out_edges)
{
free (out_edges);
out_edges = NULL;
}
sbitmap_free (blocks);
sbitmap_free (large_region_blocks);
}
#endif