#include "config.h"
#include "system.h"
#include "toplev.h"
#include "rtl.h"
#include "basic-block.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"
#include "insn-config.h"
#include "insn-attr.h"
#include "except.h"
#include "toplev.h"
#include "recog.h"
extern char *reg_known_equiv_p;
extern rtx *reg_known_value;
#ifdef INSN_SCHEDULING
static int target_units = 0;
static int issue_rate;
#ifndef ISSUE_RATE
#define ISSUE_RATE 1
#endif
#define MAX_RGN_BLOCKS 10
#define MAX_RGN_INSNS 100
static int sched_verbose_param = 0;
static int sched_verbose = 0;
static int nr_inter, nr_spec;
static FILE *dump = 0;
void
fix_sched_param (param, val)
char *param, *val;
{
if (!strcmp (param, "verbose"))
sched_verbose_param = atoi (val);
else
warning ("fix_sched_param: unknown param: %s", param);
}
static int *sched_reg_n_calls_crossed;
static int *sched_reg_live_length;
static int *sched_reg_basic_block;
static int current_block_num;
static rtx *reg_last_uses;
static rtx *reg_last_sets;
static rtx *reg_last_clobbers;
static regset reg_pending_sets;
static regset reg_pending_clobbers;
static int reg_pending_sets_all;
static int *insn_luid;
#define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
static int *insn_priority;
#define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
static short *insn_costs;
#define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
static short *insn_units;
#define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
static int *insn_reg_weight;
#define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
static rtx *insn_depend;
#define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
static int *insn_dep_count;
#define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
static unsigned int *insn_blockage;
#define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
#define UNIT_BITS 5
#define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
#define ENCODE_BLOCKAGE(U, R) \
(((U) << BLOCKAGE_BITS \
| MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
| MAX_BLOCKAGE_COST (R))
#define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
#define BLOCKAGE_RANGE(B) \
(((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
| ((B) & BLOCKAGE_MASK))
#define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
#define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
#define DONE_PRIORITY -1
#define MAX_PRIORITY 0x7fffffff
#define TAIL_PRIORITY 0x7ffffffe
#define LAUNCH_PRIORITY 0x7f000001
#define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
#define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
static int *insn_ref_count;
#define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
static rtx *line_note;
#define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
static rtx *line_note_head;
static rtx note_list;
static regset bb_live_regs;
static regset old_live_regs;
static rtx dead_notes;
static rtx insn_queue[INSN_QUEUE_SIZE];
static int q_ptr = 0;
static int q_size = 0;
#define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
#define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
static int *insn_tick;
#define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
struct sometimes
{
int regno;
int live_length;
int calls_crossed;
};
static void add_dependence PROTO ((rtx, rtx, enum reg_note));
static void remove_dependence PROTO ((rtx, rtx));
static rtx find_insn_list PROTO ((rtx, rtx));
static int insn_unit PROTO ((rtx));
static unsigned int blockage_range PROTO ((int, rtx));
static void clear_units PROTO ((void));
static int actual_hazard_this_instance PROTO ((int, int, rtx, int, int));
static void schedule_unit PROTO ((int, rtx, int));
static int actual_hazard PROTO ((int, rtx, int, int));
static int potential_hazard PROTO ((int, rtx, int));
static int insn_cost PROTO ((rtx, rtx, rtx));
static int priority PROTO ((rtx));
static void free_pending_lists PROTO ((void));
static void add_insn_mem_dependence PROTO ((rtx *, rtx *, rtx, rtx));
static void flush_pending_lists PROTO ((rtx, int));
static void sched_analyze_1 PROTO ((rtx, rtx));
static void sched_analyze_2 PROTO ((rtx, rtx));
static void sched_analyze_insn PROTO ((rtx, rtx, rtx));
static void sched_analyze PROTO ((rtx, rtx));
static void sched_note_set PROTO ((rtx, int));
static int rank_for_schedule PROTO ((const GENERIC_PTR, const GENERIC_PTR));
static void swap_sort PROTO ((rtx *, int));
static void queue_insn PROTO ((rtx, int));
static int schedule_insn PROTO ((rtx, rtx *, int, int));
static void create_reg_dead_note PROTO ((rtx, rtx));
static void attach_deaths PROTO ((rtx, rtx, int));
static void attach_deaths_insn PROTO ((rtx));
static int new_sometimes_live PROTO ((struct sometimes *, int, int));
static void finish_sometimes_live PROTO ((struct sometimes *, int));
static int schedule_block PROTO ((int, int));
static void split_hard_reg_notes PROTO ((rtx, rtx, rtx));
static void new_insn_dead_notes PROTO ((rtx, rtx, rtx, rtx));
static void update_n_sets PROTO ((rtx, int));
static char *safe_concat PROTO ((char *, char *, char *));
static int insn_issue_delay PROTO ((rtx));
static int birthing_insn_p PROTO ((rtx));
static void adjust_priority PROTO ((rtx));
static int *insn_orig_block;
#define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
static char *cant_move;
#define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
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])
extern rtx forced_labels;
static int is_cfg_nonregular PROTO ((void));
static int build_control_flow PROTO ((int_list_ptr *, int_list_ptr *,
int *, int *));
static void new_edge PROTO ((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 PROTO ((void));
static void find_single_block_region PROTO ((void));
static void find_rgns PROTO ((int_list_ptr *, int_list_ptr *,
int *, int *, sbitmap *));
static int too_large PROTO ((int, int *, int *));
extern void debug_live PROTO ((int, int));
static int current_nr_blocks;
static int current_blocks;
#define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
typedef unsigned HOST_WIDE_INT *bitset;
typedef struct
{
int *first_member;
int nr_members;
}
bitlst;
static int bitlst_table_last;
static int bitlst_table_size;
static int *bitlst_table;
static char bitset_member PROTO ((bitset, int, int));
static void extract_bitlst PROTO ((bitset, int, 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 PROTO ((int, int, edgelst *));
static void compute_trg_info PROTO ((int));
void debug_candidate PROTO ((int));
void debug_candidates PROTO ((int));
typedef bitset bbset;
static int bbset_size;
static bbset *dom;
#define IS_RGN_ENTRY(bb) (!bb)
#define IS_DOMINATED(bb_src, bb_trg) \
( bitset_member (dom[bb_src], bb_trg, bbset_size) )
static float *prob;
#define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
prob[bb_trg])))
typedef bitset edgeset;
static int rgn_nr_edges;
static int *rgn_edges;
static int edgeset_size;
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 PROTO ((int));
#define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
#define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
#define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
#define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
#define MIN_DIFF_PRIORITY 2
#define MIN_PROBABILITY 40
#define MIN_PROB_DIFF 10
static int check_live_1 PROTO ((int, rtx));
static void update_live_1 PROTO ((int, rtx));
static int check_live PROTO ((rtx, int));
static void update_live PROTO ((rtx, int));
static void set_spec_fed PROTO ((rtx));
static int is_pfree PROTO ((rtx, int, int));
static int find_conditional_protection PROTO ((rtx, int));
static int is_conditionally_protected PROTO ((rtx, int, int));
static int may_trap_exp PROTO ((rtx, int));
static int haifa_classify_insn PROTO ((rtx));
static int is_prisky PROTO ((rtx, int, int));
static int is_exception_free PROTO ((rtx, int, int));
static char find_insn_mem_list PROTO ((rtx, rtx, rtx, rtx));
static void compute_block_forward_dependences PROTO ((int));
static void init_rgn_data_dependences PROTO ((int));
static void add_branch_dependences PROTO ((rtx, rtx));
static void compute_block_backward_dependences PROTO ((int));
void debug_dependencies PROTO ((void));
static rtx unlink_other_notes PROTO ((rtx, rtx));
static rtx unlink_line_notes PROTO ((rtx, rtx));
static void rm_line_notes PROTO ((int));
static void save_line_notes PROTO ((int));
static void restore_line_notes PROTO ((int));
static void rm_redundant_line_notes PROTO ((void));
static void rm_other_notes PROTO ((rtx, rtx));
static rtx reemit_notes PROTO ((rtx, rtx));
static void get_block_head_tail PROTO ((int, rtx *, rtx *));
static void find_pre_sched_live PROTO ((int));
static void find_post_sched_live PROTO ((int));
static void update_reg_usage PROTO ((void));
static int queue_to_ready PROTO ((rtx [], int));
static void debug_ready_list PROTO ((rtx[], int));
static void init_target_units PROTO ((void));
static void insn_print_units PROTO ((rtx));
static int get_visual_tbl_length PROTO ((void));
static void init_block_visualization PROTO ((void));
static void print_block_visualization PROTO ((int, char *));
static void visualize_scheduled_insns PROTO ((int, int));
static void visualize_no_unit PROTO ((rtx));
static void visualize_stall_cycles PROTO ((int, int));
static void print_exp PROTO ((char *, rtx, int));
static void print_value PROTO ((char *, rtx, int));
static void print_pattern PROTO ((char *, rtx, int));
static void print_insn PROTO ((char *, rtx, int));
void debug_reg_vector PROTO ((regset));
static rtx move_insn1 PROTO ((rtx, rtx));
static rtx move_insn PROTO ((rtx, rtx));
static rtx group_leader PROTO ((rtx));
static int set_priorities PROTO ((int));
static void init_rtx_vector PROTO ((rtx **, rtx *, int, int));
static void schedule_region PROTO ((int));
#endif
#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
static rtx unused_insn_list;
static rtx unused_expr_list;
static void free_list PROTO ((rtx *, rtx *));
static rtx alloc_INSN_LIST PROTO ((rtx, rtx));
static rtx alloc_EXPR_LIST PROTO ((int, rtx, rtx));
static void
free_list (listp, unused_listp)
rtx *listp, *unused_listp;
{
register rtx link, prev_link;
if (*listp == 0)
return;
prev_link = *listp;
link = XEXP (prev_link, 1);
while (link)
{
prev_link = link;
link = XEXP (link, 1);
}
XEXP (prev_link, 1) = *unused_listp;
*unused_listp = *listp;
*listp = 0;
}
static rtx
alloc_INSN_LIST (val, next)
rtx val, next;
{
rtx r;
if (unused_insn_list)
{
r = unused_insn_list;
unused_insn_list = XEXP (r, 1);
XEXP (r, 0) = val;
XEXP (r, 1) = next;
PUT_REG_NOTE_KIND (r, VOIDmode);
}
else
r = gen_rtx_INSN_LIST (VOIDmode, val, next);
return r;
}
static rtx
alloc_EXPR_LIST (kind, val, next)
int kind;
rtx val, next;
{
rtx r;
if (unused_expr_list)
{
r = unused_expr_list;
unused_expr_list = XEXP (r, 1);
XEXP (r, 0) = val;
XEXP (r, 1) = next;
PUT_REG_NOTE_KIND (r, kind);
}
else
r = gen_rtx_EXPR_LIST (kind, val, next);
return r;
}
static void
add_dependence (insn, elem, dep_type)
rtx insn;
rtx elem;
enum reg_note dep_type;
{
rtx link, next;
if (insn == elem)
return;
if (GET_CODE (elem) == NOTE)
return;
next = NEXT_INSN (elem);
#ifdef HAVE_cc0
while (next && GET_CODE (next) == NOTE)
next = NEXT_INSN (next);
#endif
if (next && SCHED_GROUP_P (next)
&& GET_CODE (next) != CODE_LABEL)
{
while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
&& GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
next = NEXT_INSN (next);
if (insn == next)
return;
elem = next;
}
#ifdef INSN_SCHEDULING
if (GET_CODE (insn) == CALL_INSN
&& (INSN_BB (elem) != INSN_BB (insn)))
return;
#endif
for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
if (XEXP (link, 0) == elem)
{
if ((int) dep_type < (int) REG_NOTE_KIND (link))
PUT_REG_NOTE_KIND (link, dep_type);
return;
}
link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
LOG_LINKS (insn) = link;
PUT_REG_NOTE_KIND (link, dep_type);
}
static void
remove_dependence (insn, elem)
rtx insn;
rtx elem;
{
rtx prev, link, next;
int found = 0;
for (prev = 0, link = LOG_LINKS (insn); link; link = next)
{
next = XEXP (link, 1);
if (XEXP (link, 0) == elem)
{
if (prev)
XEXP (prev, 1) = next;
else
LOG_LINKS (insn) = next;
XEXP (link, 1) = unused_insn_list;
unused_insn_list = link;
found = 1;
}
else
prev = link;
}
if (!found)
abort ();
return;
}
#ifndef INSN_SCHEDULING
void
schedule_insns (dump_file)
FILE *dump_file;
{
}
#else
#ifndef __GNUC__
#define __inline
#endif
#ifndef HAIFA_INLINE
#define HAIFA_INLINE __inline
#endif
static rtx pending_read_insns;
static rtx pending_read_mems;
static rtx pending_write_insns;
static rtx pending_write_mems;
static int pending_lists_length;
static rtx last_pending_memory_flush;
static rtx last_function_call;
static rtx sched_before_next_call;
static rtx last_scheduled_insn;
static rtx **bb_reg_last_uses;
static rtx **bb_reg_last_sets;
static rtx **bb_reg_last_clobbers;
static rtx *bb_pending_read_insns;
static rtx *bb_pending_read_mems;
static rtx *bb_pending_write_insns;
static rtx *bb_pending_write_mems;
static int *bb_pending_lists_length;
static rtx *bb_last_pending_memory_flush;
static rtx *bb_last_function_call;
static rtx *bb_sched_before_next_call;
static int
is_cfg_nonregular ()
{
int 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 (exception_handler_labels)
return 1;
for (b = 0; b < n_basic_blocks; b++)
for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
{
code = GET_CODE (insn);
if (GET_RTX_CLASS (code) == 'i')
{
rtx note;
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_LABEL)
return 1;
}
if (insn == BLOCK_END (b))
break;
}
return 0;
}
static int
build_control_flow (s_preds, s_succs, num_preds, num_succs)
int_list_ptr *s_preds;
int_list_ptr *s_succs;
int *num_preds;
int *num_succs;
{
int i;
int_list_ptr succ;
int unreachable;
nr_edges = 0;
unreachable = 0;
for (i = 0; i < n_basic_blocks; i++)
{
nr_edges += num_succs[i];
if (num_preds[i] == 0
|| (num_preds[i] == 1 && INT_LIST_VAL (s_preds[i]) == i))
unreachable = 1;
}
nr_edges += 2;
in_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
out_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
bzero ((char *) in_edges, n_basic_blocks * sizeof (int));
bzero ((char *) out_edges, n_basic_blocks * sizeof (int));
edge_table = (haifa_edge *) xmalloc ((nr_edges) * sizeof (haifa_edge));
bzero ((char *) edge_table, ((nr_edges) * sizeof (haifa_edge)));
nr_edges = 0;
for (i = 0; i < n_basic_blocks; i++)
for (succ = s_succs[i]; succ; succ = succ->next)
{
if (INT_LIST_VAL (succ) != EXIT_BLOCK)
new_edge (i, INT_LIST_VAL (succ));
}
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;
}
}
#define BITSET_UNION(set1, set2, len) \
do { register bitset tp = set1, sp = set2; \
register int i; \
for (i = 0; i < len; i++) \
*(tp++) |= *(sp++); } while (0)
#define BITSET_INTER(set1, set2, len) \
do { register bitset tp = set1, sp = set2; \
register int i; \
for (i = 0; i < len; i++) \
*(tp++) &= *(sp++); } while (0)
#define BITSET_DIFFER(set1, set2, len) \
do { register bitset tp = set1, sp = set2; \
register int i; \
for (i = 0; i < len; i++) \
*(tp++) &= ~*(sp++); } while (0)
#define BITSET_INVERT(set, len) \
do { register bitset tmpset = set; \
register int i; \
for (i = 0; i < len; i++, tmpset++) \
*tmpset = ~*tmpset; } while (0)
#define BITSET_ADD(set, index, len) \
{ \
if (index >= HOST_BITS_PER_WIDE_INT * len) \
abort (); \
else \
set[index/HOST_BITS_PER_WIDE_INT] |= \
1 << (index % HOST_BITS_PER_WIDE_INT); \
}
#define BITSET_REMOVE(set, index, len) \
{ \
if (index >= HOST_BITS_PER_WIDE_INT * len) \
abort (); \
else \
set[index/HOST_BITS_PER_WIDE_INT] &= \
~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
}
static char
bitset_member (set, index, len)
bitset set;
int index, len;
{
if (index >= HOST_BITS_PER_WIDE_INT * len)
abort ();
return (set[index / HOST_BITS_PER_WIDE_INT] &
1 << (index % HOST_BITS_PER_WIDE_INT)) ? 1 : 0;
}
static void
extract_bitlst (set, len, bl)
bitset set;
int len;
bitlst *bl;
{
int i, j, offset;
unsigned HOST_WIDE_INT word;
bitlst_table_last = 0;
bl->first_member = &bitlst_table[bitlst_table_last];
bl->nr_members = 0;
for (i = 0; i < len; i++)
{
word = set[i];
offset = i * HOST_BITS_PER_WIDE_INT;
for (j = 0; word; j++)
{
if (word & 1)
{
bitlst_table[bitlst_table_last++] = offset;
(bl->nr_members)++;
}
word >>= 1;
++offset;
}
}
}
void
debug_regions ()
{
int rgn, bb;
fprintf (dump, "\n;; ------------ REGIONS ----------\n\n");
for (rgn = 0; rgn < nr_regions; rgn++)
{
fprintf (dump, ";;\trgn %d nr_blocks %d:\n", rgn,
rgn_table[rgn].rgn_nr_blocks);
fprintf (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 (dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
}
fprintf (dump, "\n\n");
}
}
static void
find_single_block_region ()
{
int i;
for (i = 0; i < n_basic_blocks; i++)
{
rgn_bb_table[i] = i;
RGN_NR_BLOCKS (i) = 1;
RGN_BLOCKS (i) = i;
CONTAINING_RGN (i) = i;
BLOCK_TO_BB (i) = 0;
}
nr_regions = n_basic_blocks;
}
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 (s_preds, s_succs, num_preds, num_succs, dom)
int_list_ptr *s_preds;
int_list_ptr *s_succs;
int *num_preds;
int *num_succs;
sbitmap *dom;
{
int *max_hdr, *dfs_nr, *stack, *queue, *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;
sbitmap passed;
sbitmap header;
sbitmap inner;
sbitmap in_queue;
sbitmap in_stack;
max_hdr = (int *) alloca (n_basic_blocks * sizeof (int));
dfs_nr = (int *) alloca (n_basic_blocks * sizeof (int));
bzero ((char *) dfs_nr, n_basic_blocks * sizeof (int));
stack = (int *) alloca (nr_edges * sizeof (int));
inner = sbitmap_alloc (n_basic_blocks);
sbitmap_ones (inner);
header = sbitmap_alloc (n_basic_blocks);
sbitmap_zero (header);
passed = sbitmap_alloc (nr_edges);
sbitmap_zero (passed);
in_queue = sbitmap_alloc (n_basic_blocks);
sbitmap_zero (in_queue);
in_stack = sbitmap_alloc (n_basic_blocks);
sbitmap_zero (in_stack);
for (i = 0; i < n_basic_blocks; 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);
}
unreachable = 0;
for (i = 0; i < n_basic_blocks; i++)
if (dfs_nr[i] == 0)
{
unreachable = 1;
break;
}
degree = dfs_nr;
for (i = 0; i < n_basic_blocks; i++)
degree[i] = num_preds[i];
if (!unreachable)
{
if (no_loops)
SET_BIT (header, 0);
queue = (int *) alloca (n_basic_blocks * sizeof (int));
for (i = 0; i < n_basic_blocks; i++)
{
if (TEST_BIT (header, i) && TEST_BIT (inner, i))
{
int_list_ptr ps;
int j;
for (j = 0; j < n_basic_blocks; j++)
{
if (i == max_hdr[j] && i != j)
{
if (!TEST_BIT (dom[j], i))
break;
}
}
if (j != n_basic_blocks)
continue;
head = tail = -1;
too_large_failure = 0;
loop_head = max_hdr[i];
for (ps = s_succs[i]; ps; ps = ps->next)
if (INT_LIST_VAL (ps) != EXIT_BLOCK
&& INT_LIST_VAL (ps) != ENTRY_BLOCK)
--degree[INT_LIST_VAL(ps)];
num_bbs = 1;
num_insns = (INSN_LUID (BLOCK_END (i))
- INSN_LUID (BLOCK_HEAD (i)));
if (no_loops)
{
for (j = 0; j < n_basic_blocks; j++)
if (num_succs[j] == 1
&& INT_LIST_VAL (s_succs[j]) == EXIT_BLOCK)
{
queue[++tail] = j;
SET_BIT (in_queue, j);
if (too_large (j, &num_bbs, &num_insns))
{
too_large_failure = 1;
break;
}
}
}
else
{
int_list_ptr ps;
for (ps = s_preds[i]; ps; ps = ps->next)
{
node = INT_LIST_VAL (ps);
if (node == ENTRY_BLOCK || node == EXIT_BLOCK)
continue;
if (max_hdr[node] == loop_head && node != i)
{
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)
{
int_list_ptr ps;
child = queue[++head];
for (ps = s_preds[child]; ps; ps = ps->next)
{
node = INT_LIST_VAL (ps);
if (node == ENTRY_BLOCK || node == EXIT_BLOCK
|| max_hdr[node] != loop_head)
{
tail = -1;
break;
}
else if (!TEST_BIT (in_queue, node) && node != i)
{
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[i] = -1;
rgn_bb_table[idx] = i;
RGN_NR_BLOCKS (nr_regions) = num_bbs;
RGN_BLOCKS (nr_regions) = idx++;
CONTAINING_RGN (i) = nr_regions;
BLOCK_TO_BB (i) = count = 0;
while (tail >= 0)
{
int_list_ptr ps;
if (head < 0)
head = tail;
child = queue[head];
if (degree[child] == 0)
{
degree[child] = -1;
rgn_bb_table[idx++] = child;
BLOCK_TO_BB (child) = ++count;
CONTAINING_RGN (child) = nr_regions;
queue[head] = queue[tail--];
for (ps = s_succs[child]; ps; ps = ps->next)
if (INT_LIST_VAL (ps) != ENTRY_BLOCK
&& INT_LIST_VAL (ps) != EXIT_BLOCK)
--degree[INT_LIST_VAL (ps)];
}
else
--head;
}
++nr_regions;
}
}
}
}
for (i = 0; i < n_basic_blocks; i++)
if (degree[i] >= 0)
{
rgn_bb_table[idx] = i;
RGN_NR_BLOCKS (nr_regions) = 1;
RGN_BLOCKS (nr_regions) = idx++;
CONTAINING_RGN (i) = nr_regions++;
BLOCK_TO_BB (i) = 0;
}
free (passed);
free (header);
free (inner);
free (in_queue);
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))
{
BITSET_ADD (dom[bb], 0, bbset_size);
prob[bb] = 1.0;
return;
}
fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
BITSET_INVERT (dom[bb], bbset_size);
do
{
pred = FROM_BLOCK (nxt_in_edge);
BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
edgeset_size);
BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
nr_out_edges = 1;
nr_rgn_out_edges = 0;
fst_out_edge = OUT_EDGES (pred);
nxt_out_edge = NEXT_OUT (fst_out_edge);
BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
edgeset_size);
BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
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;
BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
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);
BITSET_ADD (dom[bb], bb, bbset_size);
BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
if (sched_verbose >= 2)
fprintf (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;
{
int es = edgeset_size;
edgeset src = (edgeset) alloca (es * sizeof (HOST_WIDE_INT));
while (es--)
src[es] = (pot_split[bb_src])[es];
BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
extract_bitlst (src, edgeset_size, bl);
}
static void
compute_trg_info (trg)
int trg;
{
register 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)
{
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_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
{
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_idx++;
}
nxt_edge = NEXT_OUT (nxt_edge);
}
while (fst_edge != nxt_edge);
}
sp->update_bbs.nr_members = update_idx;
}
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 (dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
fprintf (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 (dump, " %d ", b);
}
fprintf (dump, "\n");
fprintf (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 (dump, " %d ", b);
}
fprintf (dump, "\n");
}
else
{
fprintf (dump, " src %d equivalent\n", BB_TO_BLOCK (i));
}
}
void
debug_candidates (trg)
int trg;
{
int i;
fprintf (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;
{
register int i;
register int regno;
register 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
&& GET_MODE (reg) == BLKmode)
{
register int i;
for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
if (check_live_1 (src, XVECEXP (reg, 0, i)))
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;
{
register int i;
register int regno;
register 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
&& GET_MODE (reg) == BLKmode)
{
register int i;
for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
update_live_1 (src, XVECEXP (reg, 0, i));
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)
char *fed_by_spec_load;
char *is_load_insn;
#define IS_REACHABLE(bb_from, bb_to) \
(bb_from == bb_to \
|| IS_RGN_ENTRY (bb_from) \
|| (bitset_member (ancestor_edges[bb_to], \
EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
edgeset_size)))
#define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
#define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
#define CONST_BASED_ADDRESS_P(x) \
(GET_CODE (x) == REG \
|| ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
|| (GET_CODE (x) == LO_SUM)) \
&& (GET_CODE (XEXP (x, 0)) == CONST_INT \
|| GET_CODE (XEXP (x, 1)) == CONST_INT)))
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 (INSN_BLOCK (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 (INSN_BLOCK (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;
register 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) == INSN_BLOCK (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)
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
{
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 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 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;
}
HAIFA_INLINE static rtx
find_insn_list (insn, list)
rtx insn;
rtx list;
{
while (list)
{
if (XEXP (list, 0) == insn)
return list;
list = XEXP (list, 1);
}
return 0;
}
HAIFA_INLINE static char
find_insn_mem_list (insn, x, list, list1)
rtx insn, x;
rtx list, list1;
{
while (list)
{
if (XEXP (list, 0) == insn
&& XEXP (list1, 0) == x)
return 1;
list = XEXP (list, 1);
list1 = XEXP (list1, 1);
}
return 0;
}
HAIFA_INLINE static int
insn_unit (insn)
rtx insn;
{
register int unit = INSN_UNIT (insn);
if (unit == 0)
{
recog_memoized (insn);
if (INSN_CODE (insn) < 0)
unit = -1;
else
{
unit = function_units_used (insn);
if (unit >= 0)
unit++;
}
if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
|| unit >= 0
|| (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
INSN_UNIT (insn) = unit;
}
return (unit > 0 ? unit - 1 : unit);
}
HAIFA_INLINE static unsigned int
blockage_range (unit, insn)
int unit;
rtx insn;
{
unsigned int blockage = INSN_BLOCKAGE (insn);
unsigned int range;
if ((int) UNIT_BLOCKED (blockage) != unit + 1)
{
range = function_units[unit].blockage_range_function (insn);
if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
}
else
range = BLOCKAGE_RANGE (blockage);
return range;
}
static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
static int unit_n_insns[FUNCTION_UNITS_SIZE];
static void
clear_units ()
{
bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
bzero ((char *) unit_tick, sizeof (unit_tick));
bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
}
HAIFA_INLINE static int
insn_issue_delay (insn)
rtx insn;
{
int i, delay = 0;
int unit = insn_unit (insn);
if (unit >= 0)
{
if (function_units[unit].blockage_range_function &&
function_units[unit].blockage_function)
delay = function_units[unit].blockage_function (insn, insn);
}
else
for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
if ((unit & 1) != 0 && function_units[i].blockage_range_function
&& function_units[i].blockage_function)
delay = MAX (delay, function_units[i].blockage_function (insn, insn));
return delay;
}
HAIFA_INLINE static int
actual_hazard_this_instance (unit, instance, insn, clock, cost)
int unit, instance, clock, cost;
rtx insn;
{
int tick = unit_tick[instance];
if (tick - clock > cost)
{
if (function_units[unit].blockage_range_function)
{
if (function_units[unit].blockage_function)
tick += (function_units[unit].blockage_function
(unit_last_insn[instance], insn)
- function_units[unit].max_blockage);
else
tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
- function_units[unit].max_blockage);
}
if (tick - clock > cost)
cost = tick - clock;
}
return cost;
}
HAIFA_INLINE static void
schedule_unit (unit, insn, clock)
int unit, clock;
rtx insn;
{
int i;
if (unit >= 0)
{
int instance = unit;
#if MAX_MULTIPLICITY > 1
for (i = function_units[unit].multiplicity - 1; i > 0; i--)
{
if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
break;
instance += FUNCTION_UNITS_SIZE;
}
#endif
unit_last_insn[instance] = insn;
unit_tick[instance] = (clock + function_units[unit].max_blockage);
}
else
for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
if ((unit & 1) != 0)
schedule_unit (i, insn, clock);
}
HAIFA_INLINE static int
actual_hazard (unit, insn, clock, cost)
int unit, clock, cost;
rtx insn;
{
int i;
if (unit >= 0)
{
int instance = unit;
int best_cost = actual_hazard_this_instance (unit, instance, insn,
clock, cost);
int this_cost;
#if MAX_MULTIPLICITY > 1
if (best_cost > cost)
{
for (i = function_units[unit].multiplicity - 1; i > 0; i--)
{
instance += FUNCTION_UNITS_SIZE;
this_cost = actual_hazard_this_instance (unit, instance, insn,
clock, cost);
if (this_cost < best_cost)
{
best_cost = this_cost;
if (this_cost <= cost)
break;
}
}
}
#endif
cost = MAX (cost, best_cost);
}
else
for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
if ((unit & 1) != 0)
cost = actual_hazard (i, insn, clock, cost);
return cost;
}
HAIFA_INLINE static int
potential_hazard (unit, insn, cost)
int unit, cost;
rtx insn;
{
int i, ncost;
unsigned int minb, maxb;
if (unit >= 0)
{
minb = maxb = function_units[unit].max_blockage;
if (maxb > 1)
{
if (function_units[unit].blockage_range_function)
{
maxb = minb = blockage_range (unit, insn);
maxb = MAX_BLOCKAGE_COST (maxb);
minb = MIN_BLOCKAGE_COST (minb);
}
if (maxb > 1)
{
ncost = minb * 0x40 + maxb;
ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
if (ncost > cost)
cost = ncost;
}
}
}
else
for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
if ((unit & 1) != 0)
cost = potential_hazard (i, insn, cost);
return cost;
}
HAIFA_INLINE static int
insn_cost (insn, link, used)
rtx insn, link, used;
{
register int cost = INSN_COST (insn);
if (cost == 0)
{
recog_memoized (insn);
if (INSN_CODE (insn) < 0)
{
INSN_COST (insn) = 1;
return 1;
}
else
{
cost = result_ready_cost (insn);
if (cost < 1)
cost = 1;
INSN_COST (insn) = cost;
}
}
if (link == 0 && used == 0)
return cost;
recog_memoized (used);
if (INSN_CODE (used) < 0)
LINK_COST_FREE (link) = 1;
if (LINK_COST_FREE (link))
cost = 1;
#ifdef ADJUST_COST
else if (!LINK_COST_ZERO (link))
{
int ncost = cost;
ADJUST_COST (used, link, insn, ncost);
if (ncost <= 1)
LINK_COST_FREE (link) = ncost = 1;
if (cost == ncost)
LINK_COST_ZERO (link) = 1;
cost = ncost;
}
#endif
return cost;
}
static int
priority (insn)
rtx insn;
{
int this_priority;
rtx link;
if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
return 0;
if ((this_priority = INSN_PRIORITY (insn)) == 0)
{
if (INSN_DEPEND (insn) == 0)
this_priority = insn_cost (insn, 0, 0);
else
for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
{
rtx next;
int next_priority;
if (RTX_INTEGRATED_P (link))
continue;
next = XEXP (link, 0);
if (INSN_BLOCK (next) != INSN_BLOCK (insn))
continue;
next_priority = insn_cost (insn, link, next) + priority (next);
if (next_priority > this_priority)
this_priority = next_priority;
}
INSN_PRIORITY (insn) = this_priority;
}
return this_priority;
}
static void
free_pending_lists ()
{
if (current_nr_blocks <= 1)
{
free_list (&pending_read_insns, &unused_insn_list);
free_list (&pending_write_insns, &unused_insn_list);
free_list (&pending_read_mems, &unused_expr_list);
free_list (&pending_write_mems, &unused_expr_list);
}
else
{
int bb;
for (bb = 0; bb < current_nr_blocks; bb++)
{
free_list (&bb_pending_read_insns[bb], &unused_insn_list);
free_list (&bb_pending_write_insns[bb], &unused_insn_list);
free_list (&bb_pending_read_mems[bb], &unused_expr_list);
free_list (&bb_pending_write_mems[bb], &unused_expr_list);
}
}
}
static void
add_insn_mem_dependence (insn_list, mem_list, insn, mem)
rtx *insn_list, *mem_list, insn, mem;
{
register rtx link;
link = alloc_INSN_LIST (insn, *insn_list);
*insn_list = link;
link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
*mem_list = link;
pending_lists_length++;
}
static void
flush_pending_lists (insn, only_write)
rtx insn;
int only_write;
{
rtx u;
rtx link;
while (pending_read_insns && ! only_write)
{
add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
link = pending_read_insns;
pending_read_insns = XEXP (pending_read_insns, 1);
XEXP (link, 1) = unused_insn_list;
unused_insn_list = link;
link = pending_read_mems;
pending_read_mems = XEXP (pending_read_mems, 1);
XEXP (link, 1) = unused_expr_list;
unused_expr_list = link;
}
while (pending_write_insns)
{
add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
link = pending_write_insns;
pending_write_insns = XEXP (pending_write_insns, 1);
XEXP (link, 1) = unused_insn_list;
unused_insn_list = link;
link = pending_write_mems;
pending_write_mems = XEXP (pending_write_mems, 1);
XEXP (link, 1) = unused_expr_list;
unused_expr_list = link;
}
pending_lists_length = 0;
for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
free_list (&last_pending_memory_flush, &unused_insn_list);
last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
}
static void
sched_analyze_1 (x, insn)
rtx x;
rtx insn;
{
register int regno;
register rtx dest = SET_DEST (x);
enum rtx_code code = GET_CODE (x);
if (dest == 0)
return;
if (GET_CODE (dest) == PARALLEL
&& GET_MODE (dest) == BLKmode)
{
register int i;
for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
sched_analyze_1 (XVECEXP (dest, 0, i), insn);
if (GET_CODE (x) == SET)
sched_analyze_2 (SET_SRC (x), insn);
return;
}
while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
{
if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
{
sched_analyze_2 (XEXP (dest, 1), insn);
sched_analyze_2 (XEXP (dest, 2), insn);
}
dest = SUBREG_REG (dest);
}
if (GET_CODE (dest) == REG)
{
register int i;
regno = REGNO (dest);
if (regno < FIRST_PSEUDO_REGISTER)
{
i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
while (--i >= 0)
{
rtx u;
for (u = reg_last_uses[regno + i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
if (code == SET)
{
reg_last_uses[regno + i] = 0;
for (u = reg_last_clobbers[regno + i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
SET_REGNO_REG_SET (reg_pending_sets, regno + i);
}
else
SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
if (global_regs[regno + i]
|| (code == SET && call_used_regs[regno + i]))
for (u = last_function_call; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
}
}
else
{
rtx u;
for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
if (code == SET)
{
reg_last_uses[regno] = 0;
for (u = reg_last_clobbers[regno]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
SET_REGNO_REG_SET (reg_pending_sets, regno);
}
else
SET_REGNO_REG_SET (reg_pending_clobbers, regno);
if (!reload_completed
&& reg_known_equiv_p[regno]
&& GET_CODE (reg_known_value[regno]) == MEM)
sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
if (REG_N_CALLS_CROSSED (regno) == 0)
for (u = last_function_call; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
}
}
else if (GET_CODE (dest) == MEM)
{
if (pending_lists_length > 32)
{
flush_pending_lists (insn, 0);
}
else
{
rtx u;
rtx pending, pending_mem;
pending = pending_read_insns;
pending_mem = pending_read_mems;
while (pending)
{
if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
if (anti_dependence (XEXP (pending_mem, 0), dest))
add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
pending = XEXP (pending, 1);
pending_mem = XEXP (pending_mem, 1);
}
pending = pending_write_insns;
pending_mem = pending_write_mems;
while (pending)
{
if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
if (output_dependence (XEXP (pending_mem, 0), dest))
add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
pending = XEXP (pending, 1);
pending_mem = XEXP (pending_mem, 1);
}
for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
insn, dest);
}
sched_analyze_2 (XEXP (dest, 0), insn);
}
if (GET_CODE (x) == SET)
sched_analyze_2 (SET_SRC (x), insn);
}
static void
sched_analyze_2 (x, insn)
rtx x;
rtx insn;
{
register int i;
register int j;
register enum rtx_code code;
register char *fmt;
if (x == 0)
return;
code = GET_CODE (x);
switch (code)
{
case CONST_INT:
case CONST_DOUBLE:
case SYMBOL_REF:
case CONST:
case LABEL_REF:
return;
#ifdef HAVE_cc0
case CC0:
{
rtx link, prev;
SCHED_GROUP_P (insn) = 1;
prev = prev_nonnote_insn (insn);
if (find_insn_list (prev, LOG_LINKS (insn)))
remove_dependence (insn, prev);
for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
return;
}
#endif
case REG:
{
rtx u;
int regno = REGNO (x);
if (regno < FIRST_PSEUDO_REGISTER)
{
int i;
i = HARD_REGNO_NREGS (regno, GET_MODE (x));
while (--i >= 0)
{
reg_last_uses[regno + i]
= alloc_INSN_LIST (insn, reg_last_uses[regno + i]);
for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
for (u = reg_last_clobbers[regno + i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
if ((call_used_regs[regno + i] || global_regs[regno + i]))
for (u = last_function_call; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
}
}
else
{
reg_last_uses[regno] = alloc_INSN_LIST (insn, reg_last_uses[regno]);
for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
for (u = reg_last_clobbers[regno]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
if (!reload_completed
&& reg_known_equiv_p[regno]
&& GET_CODE (reg_known_value[regno]) == MEM)
sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
if (REG_N_CALLS_CROSSED (regno) == 0)
add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
}
return;
}
case MEM:
{
rtx u;
rtx pending, pending_mem;
pending = pending_read_insns;
pending_mem = pending_read_mems;
while (pending)
{
if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
if (read_dependence (XEXP (pending_mem, 0), x))
add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
pending = XEXP (pending, 1);
pending_mem = XEXP (pending_mem, 1);
}
pending = pending_write_insns;
pending_mem = pending_write_mems;
while (pending)
{
if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
x, rtx_varies_p))
add_dependence (insn, XEXP (pending, 0), 0);
pending = XEXP (pending, 1);
pending_mem = XEXP (pending_mem, 1);
}
for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
insn, x);
sched_analyze_2 (XEXP (x, 0), insn);
return;
}
case TRAP_IF:
flush_pending_lists (insn, 1);
break;
case ASM_OPERANDS:
case ASM_INPUT:
case UNSPEC_VOLATILE:
{
rtx u;
if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
{
int max_reg = max_reg_num ();
for (i = 0; i < max_reg; i++)
{
for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
reg_last_uses[i] = 0;
for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
}
reg_pending_sets_all = 1;
flush_pending_lists (insn, 0);
}
if (code == ASM_OPERANDS)
{
for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
return;
}
break;
}
case PRE_DEC:
case POST_DEC:
case PRE_INC:
case POST_INC:
sched_analyze_2 (XEXP (x, 0), insn);
sched_analyze_1 (x, insn);
return;
default:
break;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
sched_analyze_2 (XEXP (x, i), insn);
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
sched_analyze_2 (XVECEXP (x, i, j), insn);
}
}
static void
sched_analyze_insn (x, insn, loop_notes)
rtx x, insn;
rtx loop_notes;
{
register RTX_CODE code = GET_CODE (x);
rtx link;
int maxreg = max_reg_num ();
int i;
if (code == SET || code == CLOBBER)
sched_analyze_1 (x, insn);
else if (code == PARALLEL)
{
register int i;
for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
{
code = GET_CODE (XVECEXP (x, 0, i));
if (code == SET || code == CLOBBER)
sched_analyze_1 (XVECEXP (x, 0, i), insn);
else
sched_analyze_2 (XVECEXP (x, 0, i), insn);
}
}
else
sched_analyze_2 (x, insn);
if (GET_CODE (insn) == CALL_INSN)
for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
{
if (GET_CODE (XEXP (link, 0)) == CLOBBER)
sched_analyze_1 (XEXP (link, 0), insn);
else
sched_analyze_2 (XEXP (link, 0), insn);
}
if (loop_notes)
{
int max_reg = max_reg_num ();
int schedule_barrier_found = 0;
rtx link;
link = loop_notes;
while (XEXP (link, 1))
{
if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
|| INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
|| INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
|| INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END
|| INTVAL (XEXP (link, 0)) == NOTE_INSN_SETJMP)
schedule_barrier_found = 1;
link = XEXP (link, 1);
}
XEXP (link, 1) = REG_NOTES (insn);
REG_NOTES (insn) = loop_notes;
if (schedule_barrier_found)
{
for (i = 0; i < max_reg; i++)
{
rtx u;
for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
reg_last_uses[i] = 0;
for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
}
reg_pending_sets_all = 1;
flush_pending_lists (insn, 0);
}
}
EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
{
free_list (®_last_sets[i], &unused_insn_list);
free_list (®_last_clobbers[i],
&unused_insn_list);
reg_last_sets[i]
= alloc_INSN_LIST (insn, NULL_RTX);
});
EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
{
reg_last_clobbers[i]
= alloc_INSN_LIST (insn, reg_last_clobbers[i]);
});
CLEAR_REG_SET (reg_pending_sets);
CLEAR_REG_SET (reg_pending_clobbers);
if (reg_pending_sets_all)
{
for (i = 0; i < maxreg; i++)
{
free_list (®_last_sets[i], &unused_insn_list);
reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
}
reg_pending_sets_all = 0;
}
if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
{
rtx dep_insn;
rtx prev_dep_insn;
prev_dep_insn = insn;
dep_insn = PREV_INSN (insn);
while (GET_CODE (dep_insn) == INSN
&& GET_CODE (PATTERN (dep_insn)) == USE
&& GET_CODE (XEXP (PATTERN (dep_insn), 0)) == REG)
{
SCHED_GROUP_P (prev_dep_insn) = 1;
for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
prev_dep_insn = dep_insn;
dep_insn = PREV_INSN (dep_insn);
}
}
}
static void
sched_analyze (head, tail)
rtx head, tail;
{
register rtx insn;
register rtx u;
rtx loop_notes = 0;
for (insn = head;; insn = NEXT_INSN (insn))
{
if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
{
if (GET_CODE (insn) == JUMP_INSN)
last_pending_memory_flush
= alloc_INSN_LIST (insn, last_pending_memory_flush);
sched_analyze_insn (PATTERN (insn), insn, loop_notes);
loop_notes = 0;
}
else if (GET_CODE (insn) == CALL_INSN)
{
rtx x;
register int i;
CANT_MOVE (insn) = 1;
if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
&& NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
{
int max_reg = max_reg_num ();
for (i = 0; i < max_reg; i++)
{
for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
reg_last_uses[i] = 0;
for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
}
reg_pending_sets_all = 1;
REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
GEN_INT (0),
REG_NOTES (insn));
REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
GEN_INT (NOTE_INSN_SETJMP),
REG_NOTES (insn));
}
else
{
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (call_used_regs[i] || global_regs[i])
{
for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
SET_REGNO_REG_SET (reg_pending_clobbers, i);
}
}
x = LOG_LINKS (sched_before_next_call);
while (x)
{
add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
x = XEXP (x, 1);
}
LOG_LINKS (sched_before_next_call) = 0;
sched_analyze_insn (PATTERN (insn), insn, loop_notes);
loop_notes = 0;
flush_pending_lists (insn, CONST_CALL_P (insn));
free_list(&last_function_call, &unused_insn_list);
last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
}
else if (GET_CODE (insn) == NOTE
&& (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_START
|| NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END))
{
loop_notes = alloc_EXPR_LIST (REG_DEAD, NOTE_RANGE_INFO (insn),
loop_notes);
loop_notes = alloc_EXPR_LIST (REG_DEAD,
GEN_INT (NOTE_LINE_NUMBER (insn)),
loop_notes);
}
else if (GET_CODE (insn) == NOTE
&& (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
|| NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
|| NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
|| NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
|| (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
&& GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
{
loop_notes = alloc_EXPR_LIST (REG_DEAD,
GEN_INT (NOTE_BLOCK_NUMBER (insn)),
loop_notes);
loop_notes = alloc_EXPR_LIST (REG_DEAD,
GEN_INT (NOTE_LINE_NUMBER (insn)),
loop_notes);
CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
}
if (insn == tail)
return;
}
abort ();
}
static void
sched_note_set (x, death)
rtx x;
int death;
{
register int regno;
register rtx reg = SET_DEST (x);
int subreg_p = 0;
if (reg == 0)
return;
if (GET_CODE (reg) == PARALLEL
&& GET_MODE (reg) == BLKmode)
{
register int i;
for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
sched_note_set (XVECEXP (reg, 0, i), death);
return;
}
while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
|| GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
{
if (GET_CODE (reg) != SUBREG
|| REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
subreg_p = 1;
reg = SUBREG_REG (reg);
}
if (GET_CODE (reg) != REG)
return;
regno = REGNO (reg);
if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
{
if (death)
{
if (subreg_p)
return;
if (regno < FIRST_PSEUDO_REGISTER)
{
int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
while (--j >= 0)
{
CLEAR_REGNO_REG_SET (bb_live_regs, regno + j);
}
}
else
{
if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
sched_reg_basic_block[regno] = current_block_num;
else if (sched_reg_basic_block[regno] != current_block_num)
sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
CLEAR_REGNO_REG_SET (bb_live_regs, regno);
}
}
else
{
if (regno < FIRST_PSEUDO_REGISTER)
{
int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
while (--j >= 0)
{
SET_REGNO_REG_SET (bb_live_regs, regno + j);
}
}
else
{
SET_REGNO_REG_SET (bb_live_regs, regno);
}
}
}
}
#define SCHED_SORT(READY, N_READY) \
do { if ((N_READY) == 2) \
swap_sort (READY, N_READY); \
else if ((N_READY) > 2) \
qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
while (0)
static int
rank_for_schedule (x, y)
const GENERIC_PTR x;
const GENERIC_PTR y;
{
rtx tmp = *(rtx *)y;
rtx tmp2 = *(rtx *)x;
rtx link;
int tmp_class, tmp2_class, depend_count1, depend_count2;
int val, priority_val, spec_val, prob_val, weight_val;
priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
if (priority_val)
return priority_val;
if (!reload_completed &&
(weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
return (weight_val);
if (INSN_BB (tmp) != INSN_BB (tmp2))
{
if ((INSN_BB (tmp2) == target_bb) && (INSN_BB (tmp) != target_bb))
return 1;
if ((INSN_BB (tmp) == target_bb) && (INSN_BB (tmp2) != target_bb))
return -1;
if ((spec_val = IS_SPECULATIVE_INSN (tmp) - IS_SPECULATIVE_INSN (tmp2)))
return (spec_val);
prob_val = INSN_PROBABILITY (tmp2) - INSN_PROBABILITY (tmp);
if (prob_val)
return (prob_val);
}
if (last_scheduled_insn)
{
link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
tmp_class = 3;
else if (REG_NOTE_KIND (link) == 0)
tmp_class = 1;
else
tmp_class = 2;
link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
tmp2_class = 3;
else if (REG_NOTE_KIND (link) == 0)
tmp2_class = 1;
else
tmp2_class = 2;
if ((val = tmp2_class - tmp_class))
return val;
}
depend_count1 = 0;
for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
depend_count1++;
depend_count2 = 0;
for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
depend_count2++;
val = depend_count2 - depend_count1;
if (val)
return val;
return INSN_LUID (tmp) - INSN_LUID (tmp2);
}
HAIFA_INLINE static void
swap_sort (a, n)
rtx *a;
int n;
{
rtx insn = a[n - 1];
int i = n - 2;
while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
{
a[i + 1] = a[i];
i -= 1;
}
a[i + 1] = insn;
}
static int max_priority;
HAIFA_INLINE static void
queue_insn (insn, n_cycles)
rtx insn;
int n_cycles;
{
int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
insn_queue[next_q] = link;
q_size += 1;
if (sched_verbose >= 2)
{
fprintf (dump, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn));
if (INSN_BB (insn) != target_bb)
fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
fprintf (dump, "queued for %d cycles.\n", n_cycles);
}
}
HAIFA_INLINE static int
birthing_insn_p (pat)
rtx pat;
{
int j;
if (reload_completed == 1)
return 0;
if (GET_CODE (pat) == SET
&& (GET_CODE (SET_DEST (pat)) == REG
|| (GET_CODE (SET_DEST (pat)) == PARALLEL
&& GET_MODE (SET_DEST (pat)) == BLKmode)))
{
rtx dest = SET_DEST (pat);
int i;
if (GET_CODE (dest) == REG)
{
i = REGNO (dest);
if (REGNO_REG_SET_P (bb_live_regs, i))
return (REG_N_SETS (i) == 1);
}
else
{
for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
{
int regno = REGNO (SET_DEST (XVECEXP (dest, 0, i)));
if (REGNO_REG_SET_P (bb_live_regs, regno))
return (REG_N_SETS (regno) == 1);
}
}
return 0;
}
if (GET_CODE (pat) == PARALLEL)
{
for (j = 0; j < XVECLEN (pat, 0); j++)
if (birthing_insn_p (XVECEXP (pat, 0, j)))
return 1;
}
return 0;
}
HAIFA_INLINE static void
adjust_priority (prev)
rtx prev;
{
if (reload_completed == 0)
{
rtx note;
int n_deaths = 0;
for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_DEAD)
n_deaths += 1;
switch (n_deaths)
{
default:
INSN_PRIORITY (prev) >>= 3;
break;
case 3:
INSN_PRIORITY (prev) >>= 2;
break;
case 2:
case 1:
INSN_PRIORITY (prev) >>= 1;
break;
case 0:
if (birthing_insn_p (PATTERN (prev)))
{
int max = max_priority;
if (max > INSN_PRIORITY (prev))
INSN_PRIORITY (prev) = max;
}
break;
}
#ifdef ADJUST_PRIORITY
ADJUST_PRIORITY (prev);
#endif
}
}
static int last_clock_var;
static int
schedule_insn (insn, ready, n_ready, clock)
rtx insn;
rtx *ready;
int n_ready;
int clock;
{
rtx link;
int unit;
unit = insn_unit (insn);
if (sched_verbose >= 2)
{
fprintf (dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ", INSN_UID (insn));
insn_print_units (insn);
fprintf (dump, "\n");
}
if (sched_verbose && unit == -1)
visualize_no_unit (insn);
if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
schedule_unit (unit, insn, clock);
if (INSN_DEPEND (insn) == 0)
return n_ready;
if (n_ready > 0)
max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
else
max_priority = INSN_PRIORITY (insn);
for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
{
rtx next = XEXP (link, 0);
int cost = insn_cost (insn, link, next);
INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
if ((INSN_DEP_COUNT (next) -= 1) == 0)
{
int effective_cost = INSN_TICK (next) - clock;
if (INSN_BB (next) != target_bb
&& (!IS_VALID (INSN_BB (next))
|| CANT_MOVE (next)
|| (IS_SPECULATIVE_INSN (next)
&& (insn_issue_delay (next) > 3
|| !check_live (next, INSN_BB (next))
|| !is_exception_free (next, INSN_BB (next), target_bb)))))
continue;
if (sched_verbose >= 2)
{
fprintf (dump, ";;\t\tdependences resolved: insn %d ", INSN_UID (next));
if (current_nr_blocks > 1 && INSN_BB (next) != target_bb)
fprintf (dump, "/b%d ", INSN_BLOCK (next));
if (effective_cost <= 1)
fprintf (dump, "into ready\n");
else
fprintf (dump, "into queue with cost=%d\n", effective_cost);
}
adjust_priority (next);
if (effective_cost <= 1)
ready[n_ready++] = next;
else
queue_insn (next, effective_cost);
}
}
if (reload_completed && issue_rate > 1)
{
PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
last_clock_var = clock;
}
return n_ready;
}
static void
create_reg_dead_note (reg, insn)
rtx reg, insn;
{
rtx link;
if (dead_notes == 0)
{
if (current_nr_blocks <= 1)
abort ();
else
link = alloc_EXPR_LIST (REG_DEAD, NULL_RTX, NULL_RTX);
}
else
{
int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
: HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
int reg_note_regs;
link = dead_notes;
reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
: HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
GET_MODE (XEXP (link, 0))));
while (reg_note_regs < regs_killed)
{
link = XEXP (link, 1);
if (link == NULL_RTX && current_nr_blocks <= 1)
abort ();
else if (link == NULL_RTX)
link = alloc_EXPR_LIST (REG_DEAD, gen_rtx_REG (word_mode, 0),
NULL_RTX);
reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
: HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
GET_MODE (XEXP (link, 0))));
}
dead_notes = XEXP (link, 1);
while (reg_note_regs > regs_killed)
{
rtx temp_reg, temp_link;
temp_reg = gen_rtx_REG (word_mode, 0);
temp_link = alloc_EXPR_LIST (REG_DEAD, temp_reg, dead_notes);
dead_notes = temp_link;
reg_note_regs--;
}
}
XEXP (link, 0) = reg;
XEXP (link, 1) = REG_NOTES (insn);
REG_NOTES (insn) = link;
}
static void
attach_deaths (x, insn, set_p)
rtx x;
rtx insn;
int set_p;
{
register int i;
register int j;
register enum rtx_code code;
register char *fmt;
if (x == 0)
return;
code = GET_CODE (x);
switch (code)
{
case CONST_INT:
case CONST_DOUBLE:
case LABEL_REF:
case SYMBOL_REF:
case CONST:
case CODE_LABEL:
case PC:
case CC0:
return;
case REG:
{
register int regno;
int some_needed;
int all_needed;
if (set_p)
return;
regno = REGNO (x);
all_needed = some_needed = REGNO_REG_SET_P (old_live_regs, regno);
if (regno < FIRST_PSEUDO_REGISTER)
{
int n;
n = HARD_REGNO_NREGS (regno, GET_MODE (x));
while (--n > 0)
{
int needed = (REGNO_REG_SET_P (old_live_regs, regno + n));
some_needed |= needed;
all_needed &= needed;
}
}
if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
{
if (! (regno == FRAME_POINTER_REGNUM
&& (! reload_completed || frame_pointer_needed))
#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
&& ! (regno == HARD_FRAME_POINTER_REGNUM
&& (! reload_completed || frame_pointer_needed))
#endif
#if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
&& ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
#endif
&& regno != STACK_POINTER_REGNUM)
{
if (! all_needed && ! dead_or_set_p (insn, x))
{
if (regno < FIRST_PSEUDO_REGISTER
&& HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
{
int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
while (--n >= 0)
some_needed |= dead_or_set_regno_p (insn, regno + n);
}
if (! some_needed)
create_reg_dead_note (x, insn);
else
{
int i;
for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
i >= 0; i--)
if (! REGNO_REG_SET_P (old_live_regs, regno+i)
&& ! dead_or_set_regno_p (insn, regno + i))
create_reg_dead_note (gen_rtx_REG (reg_raw_mode[regno + i],
regno + i),
insn);
}
}
}
if (regno < FIRST_PSEUDO_REGISTER)
{
int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
while (--j >= 0)
{
SET_REGNO_REG_SET (bb_live_regs, regno + j);
}
}
else
{
if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
sched_reg_basic_block[regno] = current_block_num;
else if (sched_reg_basic_block[regno] != current_block_num)
sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
SET_REGNO_REG_SET (bb_live_regs, regno);
}
}
return;
}
case MEM:
attach_deaths (XEXP (x, 0), insn, 0);
return;
case SUBREG:
attach_deaths (SUBREG_REG (x), insn,
set_p && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
<= UNITS_PER_WORD)
|| (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
== GET_MODE_SIZE (GET_MODE ((x))))));
return;
case STRICT_LOW_PART:
attach_deaths (XEXP (x, 0), insn, 0);
return;
case ZERO_EXTRACT:
case SIGN_EXTRACT:
attach_deaths (XEXP (x, 0), insn, 0);
attach_deaths (XEXP (x, 1), insn, 0);
attach_deaths (XEXP (x, 2), insn, 0);
return;
case PARALLEL:
if (set_p
&& GET_MODE (x) == BLKmode)
{
for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
return;
}
default:
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
attach_deaths (XEXP (x, i), insn, 0);
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
attach_deaths (XVECEXP (x, i, j), insn, 0);
}
}
}
static void
attach_deaths_insn (insn)
rtx insn;
{
rtx x = PATTERN (insn);
register RTX_CODE code = GET_CODE (x);
rtx link;
if (code == SET)
{
attach_deaths (SET_SRC (x), insn, 0);
attach_deaths (SET_DEST (x), insn, 1);
}
else if (code == PARALLEL)
{
register int i;
for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
{
code = GET_CODE (XVECEXP (x, 0, i));
if (code == SET)
{
attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
}
else if (code != CLOBBER)
attach_deaths (XVECEXP (x, 0, i), insn, 0);
}
}
else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == MEM)
attach_deaths (XEXP (XEXP (x, 0), 0), insn, 0);
else if (code != CLOBBER)
attach_deaths (x, insn, 0);
if (GET_CODE (insn) == CALL_INSN)
for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
attach_deaths (XEXP (XEXP (link, 0), 0), insn,
GET_CODE (XEXP (link, 0)) == CLOBBER);
}
static rtx
unlink_other_notes (insn, tail)
rtx insn, tail;
{
rtx prev = PREV_INSN (insn);
while (insn != tail && GET_CODE (insn) == NOTE)
{
rtx next = NEXT_INSN (insn);
if (prev)
NEXT_INSN (prev) = next;
if (next)
PREV_INSN (next) = prev;
if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_START
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
{
PREV_INSN (insn) = note_list;
if (note_list)
NEXT_INSN (note_list) = insn;
note_list = insn;
}
insn = next;
}
return insn;
}
static rtx
unlink_line_notes (insn, tail)
rtx insn, tail;
{
rtx prev = PREV_INSN (insn);
while (insn != tail && GET_CODE (insn) == NOTE)
{
rtx next = NEXT_INSN (insn);
if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
{
if (prev)
NEXT_INSN (prev) = next;
if (next)
PREV_INSN (next) = prev;
LINE_NOTE (insn) = insn;
}
else
prev = insn;
insn = next;
}
return insn;
}
HAIFA_INLINE static void
get_block_head_tail (bb, headp, tailp)
int bb;
rtx *headp;
rtx *tailp;
{
rtx head;
rtx tail;
int b;
b = BB_TO_BLOCK (bb);
head = BLOCK_HEAD (b);
tail = BLOCK_END (b);
while (head != tail)
{
if (GET_CODE (head) == NOTE)
head = NEXT_INSN (head);
else if (GET_CODE (tail) == NOTE)
tail = PREV_INSN (tail);
else if (GET_CODE (head) == CODE_LABEL)
head = NEXT_INSN (head);
else
break;
}
*headp = head;
*tailp = tail;
}
static void
rm_line_notes (bb)
int bb;
{
rtx next_tail;
rtx tail;
rtx head;
rtx insn;
get_block_head_tail (bb, &head, &tail);
if (head == tail
&& (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
return;
next_tail = NEXT_INSN (tail);
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
{
rtx prev;
if (GET_CODE (insn) == NOTE)
{
prev = insn;
insn = unlink_line_notes (insn, next_tail);
if (prev == tail)
abort ();
if (prev == head)
abort ();
if (insn == next_tail)
abort ();
}
}
}
static void
save_line_notes (bb)
int bb;
{
rtx head, tail;
rtx next_tail;
rtx line = line_note_head[BB_TO_BLOCK (bb)];
rtx insn;
get_block_head_tail (bb, &head, &tail);
next_tail = NEXT_INSN (tail);
for (insn = BLOCK_HEAD (BB_TO_BLOCK (bb));
insn != next_tail;
insn = NEXT_INSN (insn))
if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
line = insn;
else
LINE_NOTE (insn) = line;
}
static void
restore_line_notes (bb)
int bb;
{
rtx line, note, prev, new;
int added_notes = 0;
int b;
rtx head, next_tail, insn;
b = BB_TO_BLOCK (bb);
head = BLOCK_HEAD (b);
next_tail = NEXT_INSN (BLOCK_END (b));
for (line = head; line; line = PREV_INSN (line))
if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
break;
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
line = insn;
else if (GET_CODE (insn) != NOTE
&& (note = LINE_NOTE (insn)) != 0
&& note != line
&& (line == 0
|| NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
|| NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
{
line = note;
prev = PREV_INSN (insn);
if (LINE_NOTE (note))
{
LINE_NOTE (note) = 0;
PREV_INSN (note) = prev;
NEXT_INSN (prev) = note;
PREV_INSN (insn) = note;
NEXT_INSN (note) = insn;
}
else
{
added_notes++;
new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
}
}
if (sched_verbose && added_notes)
fprintf (dump, ";; added %d line-number notes\n", added_notes);
}
static void
rm_redundant_line_notes ()
{
rtx line = 0;
rtx insn = get_insns ();
int active_insn = 0;
int notes = 0;
for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
{
if (active_insn == 0)
{
notes++;
NOTE_SOURCE_FILE (insn) = 0;
NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
}
else if (line
&& NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
&& NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
{
notes++;
NOTE_SOURCE_FILE (line) = 0;
NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
line = insn;
}
else
line = insn;
active_insn = 0;
}
else if (!((GET_CODE (insn) == NOTE
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
|| (GET_CODE (insn) == INSN
&& (GET_CODE (PATTERN (insn)) == USE
|| GET_CODE (PATTERN (insn)) == CLOBBER))))
active_insn++;
if (sched_verbose && notes)
fprintf (dump, ";; deleted %d line-number notes\n", notes);
}
static void
rm_other_notes (head, tail)
rtx head;
rtx tail;
{
rtx next_tail;
rtx insn;
if (head == tail
&& (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
return;
next_tail = NEXT_INSN (tail);
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
{
rtx prev;
if (GET_CODE (insn) == NOTE)
{
prev = insn;
insn = unlink_other_notes (insn, next_tail);
if (prev == tail)
abort ();
if (prev == head)
abort ();
if (insn == next_tail)
abort ();
}
}
}
static int
new_sometimes_live (regs_sometimes_live, regno, sometimes_max)
struct sometimes *regs_sometimes_live;
int regno;
int sometimes_max;
{
register struct sometimes *p;
if (regno >= max_regno)
abort ();
p = ®s_sometimes_live[sometimes_max];
p->regno = regno;
p->live_length = 0;
p->calls_crossed = 0;
sometimes_max++;
return sometimes_max;
}
static void
finish_sometimes_live (regs_sometimes_live, sometimes_max)
struct sometimes *regs_sometimes_live;
int sometimes_max;
{
int i;
for (i = 0; i < sometimes_max; i++)
{
register struct sometimes *p = ®s_sometimes_live[i];
int regno = p->regno;
sched_reg_live_length[regno] += p->live_length;
sched_reg_n_calls_crossed[regno] += p->calls_crossed;
}
}
static void
find_pre_sched_live (bb)
int bb;
{
rtx insn, next_tail, head, tail;
int b = BB_TO_BLOCK (bb);
get_block_head_tail (bb, &head, &tail);
COPY_REG_SET (bb_live_regs, BASIC_BLOCK (b)->global_live_at_start);
next_tail = NEXT_INSN (tail);
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
{
rtx prev, next, link;
int reg_weight = 0;
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
if (GET_CODE (PATTERN (insn)) == SET
|| GET_CODE (PATTERN (insn)) == CLOBBER)
{
sched_note_set (PATTERN (insn), 0);
reg_weight++;
}
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)
{
sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
reg_weight++;
}
for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
}
if (GET_CODE (insn) == CALL_INSN)
{
int j;
for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
if (call_used_regs[j] && !global_regs[j]
&& ! fixed_regs[j])
{
SET_REGNO_REG_SET (bb_live_regs, j);
}
}
for (prev = 0, link = REG_NOTES (insn); link; link = next)
{
next = XEXP (link, 1);
if ((REG_NOTE_KIND (link) == REG_DEAD
|| REG_NOTE_KIND (link) == REG_UNUSED)
&& GET_CODE (XEXP (link, 0)) == REG)
{
register int regno = REGNO (XEXP (link, 0));
reg_weight--;
if (REG_NOTE_KIND (link) == REG_DEAD)
{
if (prev)
XEXP (prev, 1) = next;
else
REG_NOTES (insn) = next;
XEXP (link, 1) = dead_notes;
dead_notes = link;
}
else
prev = link;
if (regno < FIRST_PSEUDO_REGISTER)
{
int j = HARD_REGNO_NREGS (regno,
GET_MODE (XEXP (link, 0)));
while (--j >= 0)
{
CLEAR_REGNO_REG_SET (bb_live_regs, regno+j);
}
}
else
{
CLEAR_REGNO_REG_SET (bb_live_regs, regno);
}
}
else
prev = link;
}
}
INSN_REG_WEIGHT (insn) = reg_weight;
}
}
static void
find_post_sched_live (bb)
int bb;
{
int sometimes_max;
int j, i;
int b;
rtx insn;
rtx head, tail, prev_head, next_tail;
register struct sometimes *regs_sometimes_live;
b = BB_TO_BLOCK (bb);
if (current_nr_blocks > 1)
{
int e;
int first_edge;
first_edge = e = OUT_EDGES (b);
CLEAR_REG_SET (bb_live_regs);
if (e)
do
{
int b_succ;
b_succ = TO_BLOCK (e);
IOR_REG_SET (bb_live_regs,
BASIC_BLOCK (b_succ)->global_live_at_start);
e = NEXT_OUT (e);
}
while (e != first_edge);
}
get_block_head_tail (bb, &head, &tail);
next_tail = NEXT_INSN (tail);
prev_head = PREV_INSN (head);
EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, i,
{
sched_reg_basic_block[i] = REG_BLOCK_GLOBAL;
});
if (NEXT_INSN (prev_head) == tail
&& (GET_RTX_CLASS (GET_CODE (tail)) != 'i'))
{
if (current_nr_blocks > 1)
COPY_REG_SET (BASIC_BLOCK (b)->global_live_at_start, bb_live_regs);
return;
}
b = BB_TO_BLOCK (bb);
current_block_num = b;
old_live_regs = ALLOCA_REG_SET ();
regs_sometimes_live
= (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
sometimes_max = 0;
sometimes_max = 0;
COPY_REG_SET (old_live_regs, bb_live_regs);
EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, 0, j,
{
sometimes_max
= new_sometimes_live (regs_sometimes_live,
j, sometimes_max);
});
for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
continue;
if (GET_CODE (PATTERN (insn)) == SET
|| GET_CODE (PATTERN (insn)) == CLOBBER)
sched_note_set (PATTERN (insn), 1);
else if (GET_CODE (PATTERN (insn)) == PARALLEL)
{
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)
sched_note_set (XVECEXP (PATTERN (insn), 0, j), 1);
}
if (GET_CODE (insn) == CALL_INSN)
{
register struct sometimes *p;
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (call_used_regs[i] && ! global_regs[i]
&& ! fixed_regs[i])
{
CLEAR_REGNO_REG_SET (bb_live_regs, i);
}
p = regs_sometimes_live;
for (i = 0; i < sometimes_max; i++, p++)
if (REGNO_REG_SET_P (bb_live_regs, p->regno))
p->calls_crossed += 1;
}
attach_deaths_insn (insn);
EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs, old_live_regs, 0, j,
{
sometimes_max
= new_sometimes_live (regs_sometimes_live,
j, sometimes_max);
});
IOR_REG_SET (old_live_regs, bb_live_regs);
for (i = 0; i < sometimes_max; i++)
{
register struct sometimes *p = ®s_sometimes_live[i];
int regno = p->regno;
p->live_length += 1;
if (!REGNO_REG_SET_P (bb_live_regs, regno))
{
sched_reg_live_length[regno] += p->live_length;
sched_reg_n_calls_crossed[regno] += p->calls_crossed;
CLEAR_REGNO_REG_SET (old_live_regs, p->regno);
*p = regs_sometimes_live[--sometimes_max];
i--;
}
}
}
finish_sometimes_live (regs_sometimes_live, sometimes_max);
if (current_nr_blocks > 1)
COPY_REG_SET (BASIC_BLOCK (b)->global_live_at_start, bb_live_regs);
FREE_REG_SET (old_live_regs);
}
static void
update_reg_usage ()
{
int regno;
if (n_basic_blocks > 0)
EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, regno,
{
sched_reg_basic_block[regno]
= REG_BLOCK_GLOBAL;
});
for (regno = 0; regno < max_regno; regno++)
if (sched_reg_live_length[regno])
{
if (sched_verbose)
{
if (REG_LIVE_LENGTH (regno) > sched_reg_live_length[regno])
fprintf (dump,
";; register %d life shortened from %d to %d\n",
regno, REG_LIVE_LENGTH (regno),
sched_reg_live_length[regno]);
else if (REG_LIVE_LENGTH (regno) < sched_reg_live_length[regno]
&& REG_LIVE_LENGTH (regno) >= 0)
fprintf (dump,
";; register %d life extended from %d to %d\n",
regno, REG_LIVE_LENGTH (regno),
sched_reg_live_length[regno]);
if (!REG_N_CALLS_CROSSED (regno)
&& sched_reg_n_calls_crossed[regno])
fprintf (dump,
";; register %d now crosses calls\n", regno);
else if (REG_N_CALLS_CROSSED (regno)
&& !sched_reg_n_calls_crossed[regno]
&& REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
fprintf (dump,
";; register %d no longer crosses calls\n", regno);
if (REG_BASIC_BLOCK (regno) != sched_reg_basic_block[regno]
&& sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
&& REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
fprintf (dump,
";; register %d changed basic block from %d to %d\n",
regno, REG_BASIC_BLOCK(regno),
sched_reg_basic_block[regno]);
}
if (REG_LIVE_LENGTH (regno) >= 0)
REG_LIVE_LENGTH (regno) = sched_reg_live_length[regno];
if (sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
&& REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
REG_BASIC_BLOCK(regno) = sched_reg_basic_block[regno];
if (sched_reg_n_calls_crossed[regno]
|| REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
REG_N_CALLS_CROSSED (regno) = sched_reg_n_calls_crossed[regno];
}
}
static int clock_var;
static int
queue_to_ready (ready, n_ready)
rtx ready[];
int n_ready;
{
rtx insn;
rtx link;
q_ptr = NEXT_Q (q_ptr);
for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
{
insn = XEXP (link, 0);
q_size -= 1;
if (sched_verbose >= 2)
fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
ready[n_ready++] = insn;
if (sched_verbose >= 2)
fprintf (dump, "moving to ready without stalls\n");
}
insn_queue[q_ptr] = 0;
if (n_ready == 0)
{
register int stalls;
for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
{
if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
{
for (; link; link = XEXP (link, 1))
{
insn = XEXP (link, 0);
q_size -= 1;
if (sched_verbose >= 2)
fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
ready[n_ready++] = insn;
if (sched_verbose >= 2)
fprintf (dump, "moving to ready with %d stalls\n", stalls);
}
insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
if (n_ready)
break;
}
}
if (sched_verbose && stalls)
visualize_stall_cycles (BB_TO_BLOCK (target_bb), stalls);
q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
clock_var += stalls;
}
return n_ready;
}
static void
debug_ready_list (ready, n_ready)
rtx ready[];
int n_ready;
{
int i;
for (i = 0; i < n_ready; i++)
{
fprintf (dump, " %d", INSN_UID (ready[i]));
if (current_nr_blocks > 1 && INSN_BB (ready[i]) != target_bb)
fprintf (dump, "/b%d", INSN_BLOCK (ready[i]));
}
fprintf (dump, "\n");
}
static void
insn_print_units (insn)
rtx insn;
{
int i;
int unit = insn_unit (insn);
if (unit == -1)
fprintf (dump, "none");
else if (unit >= 0)
fprintf (dump, "%s", function_units[unit].name);
else
{
fprintf (dump, "[");
for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
if (unit & 1)
{
fprintf (dump, "%s", function_units[i].name);
if (unit != 1)
fprintf (dump, " ");
}
fprintf (dump, "]");
}
}
#define MAX_VISUAL_LINES 100
#define INSN_LEN 30
int n_visual_lines;
char *visual_tbl;
int n_vis_no_unit;
rtx vis_no_unit[10];
static void
init_target_units ()
{
rtx insn;
int unit;
for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
continue;
unit = insn_unit (insn);
if (unit < 0)
target_units |= ~unit;
else
target_units |= (1 << unit);
}
}
static int
get_visual_tbl_length ()
{
int unit, i;
int n, n1;
char *s;
s = (char *) alloca (INSN_LEN + 5);
sprintf (s, " %33s", "uname");
n1 = strlen (s);
n = strlen (";; ");
n += n1;
for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
if (function_units[unit].bitmask & target_units)
for (i = 0; i < function_units[unit].multiplicity; i++)
n += n1;
n += n1;
n += strlen ("\n") + 2;
return (MAX_VISUAL_LINES * n);
}
static void
init_block_visualization ()
{
strcpy (visual_tbl, "");
n_visual_lines = 0;
n_vis_no_unit = 0;
}
#define BUF_LEN 256
static char *
safe_concat (buf, cur, str)
char *buf;
char *cur;
char *str;
{
char *end = buf + BUF_LEN - 2;
int c;
if (cur > end)
{
*end = '\0';
return end;
}
while (cur < end && (c = *str++) != '\0')
*cur++ = c;
*cur = '\0';
return cur;
}
static void
print_exp (buf, x, verbose)
char *buf;
rtx x;
int verbose;
{
char tmp[BUF_LEN];
char *st[4];
char *cur = buf;
char *fun = (char *)0;
char *sep;
rtx op[4];
int i;
for (i = 0; i < 4; i++)
{
st[i] = (char *)0;
op[i] = NULL_RTX;
}
switch (GET_CODE (x))
{
case PLUS:
op[0] = XEXP (x, 0);
if (GET_CODE (XEXP (x, 1)) == CONST_INT
&& INTVAL (XEXP (x, 1)) < 0)
{
st[1] = "-";
op[1] = GEN_INT (-INTVAL (XEXP (x, 1)));
}
else
{
st[1] = "+";
op[1] = XEXP (x, 1);
}
break;
case LO_SUM:
op[0] = XEXP (x, 0);
st[1] = "+low(";
op[1] = XEXP (x, 1);
st[2] = ")";
break;
case MINUS:
op[0] = XEXP (x, 0);
st[1] = "-";
op[1] = XEXP (x, 1);
break;
case COMPARE:
fun = "cmp";
op[0] = XEXP (x, 0);
op[1] = XEXP (x, 1);
break;
case NEG:
st[0] = "-";
op[0] = XEXP (x, 0);
break;
case MULT:
op[0] = XEXP (x, 0);
st[1] = "*";
op[1] = XEXP (x, 1);
break;
case DIV:
op[0] = XEXP (x, 0);
st[1] = "/";
op[1] = XEXP (x, 1);
break;
case UDIV:
fun = "udiv";
op[0] = XEXP (x, 0);
op[1] = XEXP (x, 1);
break;
case MOD:
op[0] = XEXP (x, 0);
st[1] = "%";
op[1] = XEXP (x, 1);
break;
case UMOD:
fun = "umod";
op[0] = XEXP (x, 0);
op[1] = XEXP (x, 1);
break;
case SMIN:
fun = "smin";
op[0] = XEXP (x, 0);
op[1] = XEXP (x, 1);
break;
case SMAX:
fun = "smax";
op[0] = XEXP (x, 0);
op[1] = XEXP (x, 1);
break;
case UMIN:
fun = "umin";
op[0] = XEXP (x, 0);
op[1] = XEXP (x, 1);
break;
case UMAX:
fun = "umax";
op[0] = XEXP (x, 0);
op[1] = XEXP (x, 1);
break;
case NOT:
st[0] = "!";
op[0] = XEXP (x, 0);
break;
case AND:
op[0] = XEXP (x, 0);
st[1] = "&";
op[1] = XEXP (x, 1);
break;
case IOR:
op[0] = XEXP (x, 0);
st[1] = "|";
op[1] = XEXP (x, 1);
break;
case XOR:
op[0] = XEXP (x, 0);
st[1] = "^";
op[1] = XEXP (x, 1);
break;
case ASHIFT:
op[0] = XEXP (x, 0);
st[1] = "<<";
op[1] = XEXP (x, 1);
break;
case LSHIFTRT:
op[0] = XEXP (x, 0);
st[1] = " 0>>";
op[1] = XEXP (x, 1);
break;
case ASHIFTRT:
op[0] = XEXP (x, 0);
st[1] = ">>";
op[1] = XEXP (x, 1);
break;
case ROTATE:
op[0] = XEXP (x, 0);
st[1] = "<-<";
op[1] = XEXP (x, 1);
break;
case ROTATERT:
op[0] = XEXP (x, 0);
st[1] = ">->";
op[1] = XEXP (x, 1);
break;
case ABS:
fun = "abs";
op[0] = XEXP (x, 0);
break;
case SQRT:
fun = "sqrt";
op[0] = XEXP (x, 0);
break;
case FFS:
fun = "ffs";
op[0] = XEXP (x, 0);
break;
case EQ:
op[0] = XEXP (x, 0);
st[1] = "==";
op[1] = XEXP (x, 1);
break;
case NE:
op[0] = XEXP (x, 0);
st[1] = "!=";
op[1] = XEXP (x, 1);
break;
case GT:
op[0] = XEXP (x, 0);
st[1] = ">";
op[1] = XEXP (x, 1);
break;
case GTU:
fun = "gtu";
op[0] = XEXP (x, 0);
op[1] = XEXP (x, 1);
break;
case LT:
op[0] = XEXP (x, 0);
st[1] = "<";
op[1] = XEXP (x, 1);
break;
case LTU:
fun = "ltu";
op[0] = XEXP (x, 0);
op[1] = XEXP (x, 1);
break;
case GE:
op[0] = XEXP (x, 0);
st[1] = ">=";
op[1] = XEXP (x, 1);
break;
case GEU:
fun = "geu";
op[0] = XEXP (x, 0);
op[1] = XEXP (x, 1);
break;
case LE:
op[0] = XEXP (x, 0);
st[1] = "<=";
op[1] = XEXP (x, 1);
break;
case LEU:
fun = "leu";
op[0] = XEXP (x, 0);
op[1] = XEXP (x, 1);
break;
case SIGN_EXTRACT:
fun = (verbose) ? "sign_extract" : "sxt";
op[0] = XEXP (x, 0);
op[1] = XEXP (x, 1);
op[2] = XEXP (x, 2);
break;
case ZERO_EXTRACT:
fun = (verbose) ? "zero_extract" : "zxt";
op[0] = XEXP (x, 0);
op[1] = XEXP (x, 1);
op[2] = XEXP (x, 2);
break;
case SIGN_EXTEND:
fun = (verbose) ? "sign_extend" : "sxn";
op[0] = XEXP (x, 0);
break;
case ZERO_EXTEND:
fun = (verbose) ? "zero_extend" : "zxn";
op[0] = XEXP (x, 0);
break;
case FLOAT_EXTEND:
fun = (verbose) ? "float_extend" : "fxn";
op[0] = XEXP (x, 0);
break;
case TRUNCATE:
fun = (verbose) ? "trunc" : "trn";
op[0] = XEXP (x, 0);
break;
case FLOAT_TRUNCATE:
fun = (verbose) ? "float_trunc" : "ftr";
op[0] = XEXP (x, 0);
break;
case FLOAT:
fun = (verbose) ? "float" : "flt";
op[0] = XEXP (x, 0);
break;
case UNSIGNED_FLOAT:
fun = (verbose) ? "uns_float" : "ufl";
op[0] = XEXP (x, 0);
break;
case FIX:
fun = "fix";
op[0] = XEXP (x, 0);
break;
case UNSIGNED_FIX:
fun = (verbose) ? "uns_fix" : "ufx";
op[0] = XEXP (x, 0);
break;
case PRE_DEC:
st[0] = "--";
op[0] = XEXP (x, 0);
break;
case PRE_INC:
st[0] = "++";
op[0] = XEXP (x, 0);
break;
case POST_DEC:
op[0] = XEXP (x, 0);
st[1] = "--";
break;
case POST_INC:
op[0] = XEXP (x, 0);
st[1] = "++";
break;
case CALL:
st[0] = "call ";
op[0] = XEXP (x, 0);
if (verbose)
{
st[1] = " argc:";
op[1] = XEXP (x, 1);
}
break;
case IF_THEN_ELSE:
st[0] = "{(";
op[0] = XEXP (x, 0);
st[1] = ")?";
op[1] = XEXP (x, 1);
st[2] = ":";
op[2] = XEXP (x, 2);
st[3] = "}";
break;
case TRAP_IF:
fun = "trap_if";
op[0] = TRAP_CONDITION (x);
break;
case UNSPEC:
case UNSPEC_VOLATILE:
{
cur = safe_concat (buf, cur, "unspec");
if (GET_CODE (x) == UNSPEC_VOLATILE)
cur = safe_concat (buf, cur, "/v");
cur = safe_concat (buf, cur, "[");
sep = "";
for (i = 0; i < XVECLEN (x, 0); i++)
{
print_pattern (tmp, XVECEXP (x, 0, i), verbose);
cur = safe_concat (buf, cur, sep);
cur = safe_concat (buf, cur, tmp);
sep = ",";
}
cur = safe_concat (buf, cur, "] ");
sprintf (tmp, "%d", XINT (x, 1));
cur = safe_concat (buf, cur, tmp);
}
break;
default:
st[0] = GET_RTX_NAME (GET_CODE (x));
break;
}
if (fun)
{
cur = safe_concat (buf, cur, fun);
cur = safe_concat (buf, cur, "(");
}
for (i = 0; i < 4; i++)
{
if (st[i])
cur = safe_concat (buf, cur, st[i]);
if (op[i])
{
if (fun && i != 0)
cur = safe_concat (buf, cur, ",");
print_value (tmp, op[i], verbose);
cur = safe_concat (buf, cur, tmp);
}
}
if (fun)
cur = safe_concat (buf, cur, ")");
}
static void
print_value (buf, x, verbose)
char *buf;
rtx x;
int verbose;
{
char t[BUF_LEN];
char *cur = buf;
switch (GET_CODE (x))
{
case CONST_INT:
sprintf (t, HOST_WIDE_INT_PRINT_HEX, INTVAL (x));
cur = safe_concat (buf, cur, t);
break;
case CONST_DOUBLE:
sprintf (t, "<0x%lx,0x%lx>", (long)XWINT (x, 2), (long)XWINT (x, 3));
cur = safe_concat (buf, cur, t);
break;
case CONST_STRING:
cur = safe_concat (buf, cur, "\"");
cur = safe_concat (buf, cur, XSTR (x, 0));
cur = safe_concat (buf, cur, "\"");
break;
case SYMBOL_REF:
cur = safe_concat (buf, cur, "`");
cur = safe_concat (buf, cur, XSTR (x, 0));
cur = safe_concat (buf, cur, "'");
break;
case LABEL_REF:
sprintf (t, "L%d", INSN_UID (XEXP (x, 0)));
cur = safe_concat (buf, cur, t);
break;
case CONST:
print_value (t, XEXP (x, 0), verbose);
cur = safe_concat (buf, cur, "const(");
cur = safe_concat (buf, cur, t);
cur = safe_concat (buf, cur, ")");
break;
case HIGH:
print_value (t, XEXP (x, 0), verbose);
cur = safe_concat (buf, cur, "high(");
cur = safe_concat (buf, cur, t);
cur = safe_concat (buf, cur, ")");
break;
case REG:
if (REGNO (x) < FIRST_PSEUDO_REGISTER)
{
int c = reg_names[ REGNO (x) ][0];
if (c >= '0' && c <= '9')
cur = safe_concat (buf, cur, "%");
cur = safe_concat (buf, cur, reg_names[ REGNO (x) ]);
}
else
{
sprintf (t, "r%d", REGNO (x));
cur = safe_concat (buf, cur, t);
}
break;
case SUBREG:
print_value (t, SUBREG_REG (x), verbose);
cur = safe_concat (buf, cur, t);
sprintf (t, "#%d", SUBREG_WORD (x));
cur = safe_concat (buf, cur, t);
break;
case SCRATCH:
cur = safe_concat (buf, cur, "scratch");
break;
case CC0:
cur = safe_concat (buf, cur, "cc0");
break;
case PC:
cur = safe_concat (buf, cur, "pc");
break;
case MEM:
print_value (t, XEXP (x, 0), verbose);
cur = safe_concat (buf, cur, "[");
cur = safe_concat (buf, cur, t);
cur = safe_concat (buf, cur, "]");
break;
default:
print_exp (t, x, verbose);
cur = safe_concat (buf, cur, t);
break;
}
}
static void
print_pattern (buf, x, verbose)
char *buf;
rtx x;
int verbose;
{
char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
switch (GET_CODE (x))
{
case SET:
print_value (t1, SET_DEST (x), verbose);
print_value (t2, SET_SRC (x), verbose);
sprintf (buf, "%s=%s", t1, t2);
break;
case RETURN:
sprintf (buf, "return");
break;
case CALL:
print_exp (buf, x, verbose);
break;
case CLOBBER:
print_value (t1, XEXP (x, 0), verbose);
sprintf (buf, "clobber %s", t1);
break;
case USE:
print_value (t1, XEXP (x, 0), verbose);
sprintf (buf, "use %s", t1);
break;
case PARALLEL:
{
int i;
sprintf (t1, "{");
for (i = 0; i < XVECLEN (x, 0); i++)
{
print_pattern (t2, XVECEXP (x, 0, i), verbose);
sprintf (t3, "%s%s;", t1, t2);
strcpy (t1, t3);
}
sprintf (buf, "%s}", t1);
}
break;
case SEQUENCE:
{
int i;
sprintf (t1, "%%{");
for (i = 0; i < XVECLEN (x, 0); i++)
{
print_insn (t2, XVECEXP (x, 0, i), verbose);
sprintf (t3, "%s%s;", t1, t2);
strcpy (t1, t3);
}
sprintf (buf, "%s%%}", t1);
}
break;
case ASM_INPUT:
sprintf (buf, "asm {%s}", XSTR (x, 0));
break;
case ADDR_VEC:
break;
case ADDR_DIFF_VEC:
print_value (buf, XEXP (x, 0), verbose);
break;
case TRAP_IF:
print_value (t1, TRAP_CONDITION (x), verbose);
sprintf (buf, "trap_if %s", t1);
break;
case UNSPEC:
{
int i;
sprintf (t1, "unspec{");
for (i = 0; i < XVECLEN (x, 0); i++)
{
print_pattern (t2, XVECEXP (x, 0, i), verbose);
sprintf (t3, "%s%s;", t1, t2);
strcpy (t1, t3);
}
sprintf (buf, "%s}", t1);
}
break;
case UNSPEC_VOLATILE:
{
int i;
sprintf (t1, "unspec/v{");
for (i = 0; i < XVECLEN (x, 0); i++)
{
print_pattern (t2, XVECEXP (x, 0, i), verbose);
sprintf (t3, "%s%s;", t1, t2);
strcpy (t1, t3);
}
sprintf (buf, "%s}", t1);
}
break;
default:
print_value (buf, x, verbose);
}
}
static void
print_insn (buf, x, verbose)
char *buf;
rtx x;
int verbose;
{
char t[BUF_LEN];
rtx insn = x;
switch (GET_CODE (x))
{
case INSN:
print_pattern (t, PATTERN (x), verbose);
if (verbose)
sprintf (buf, "b%d: i% 4d: %s", INSN_BB (x),
INSN_UID (x), t);
else
sprintf (buf, "%-4d %s", INSN_UID (x), t);
break;
case JUMP_INSN:
print_pattern (t, PATTERN (x), verbose);
if (verbose)
sprintf (buf, "b%d: i% 4d: jump %s", INSN_BB (x),
INSN_UID (x), t);
else
sprintf (buf, "%-4d %s", INSN_UID (x), t);
break;
case CALL_INSN:
x = PATTERN (insn);
if (GET_CODE (x) == PARALLEL)
{
x = XVECEXP (x, 0, 0);
print_pattern (t, x, verbose);
}
else
strcpy (t, "call <...>");
if (verbose)
sprintf (buf, "b%d: i% 4d: %s", INSN_BB (insn),
INSN_UID (insn), t);
else
sprintf (buf, "%-4d %s", INSN_UID (insn), t);
break;
case CODE_LABEL:
sprintf (buf, "L%d:", INSN_UID (x));
break;
case BARRIER:
sprintf (buf, "i% 4d: barrier", INSN_UID (x));
break;
case NOTE:
if (NOTE_LINE_NUMBER (x) > 0)
sprintf (buf, "%4d note \"%s\" %d", INSN_UID (x),
NOTE_SOURCE_FILE (x), NOTE_LINE_NUMBER (x));
else
sprintf (buf, "%4d %s", INSN_UID (x),
GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x)));
break;
default:
if (verbose)
{
sprintf (buf, "Not an INSN at all\n");
debug_rtx (x);
}
else
sprintf (buf, "i%-4d <What?>", INSN_UID (x));
}
}
static void
print_block_visualization (b, s)
int b;
char *s;
{
int unit, i;
fprintf (dump, "\n;; ==================== scheduling visualization for block %d %s \n", b, s);
fprintf (dump, ";; %-8s", "clock");
for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
if (function_units[unit].bitmask & target_units)
for (i = 0; i < function_units[unit].multiplicity; i++)
fprintf (dump, " %-33s", function_units[unit].name);
fprintf (dump, " %-8s\n", "no-unit");
fprintf (dump, ";; %-8s", "=====");
for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
if (function_units[unit].bitmask & target_units)
for (i = 0; i < function_units[unit].multiplicity; i++)
fprintf (dump, " %-33s", "==============================");
fprintf (dump, " %-8s\n", "=======");
fprintf (dump, "%s\n", visual_tbl);
}
static void
visualize_no_unit (insn)
rtx insn;
{
vis_no_unit[n_vis_no_unit] = insn;
n_vis_no_unit++;
}
static void
visualize_scheduled_insns (b, clock)
int b, clock;
{
int i, unit;
if (n_visual_lines >= MAX_VISUAL_LINES)
{
print_block_visualization (b, "(incomplete)");
init_block_visualization ();
}
n_visual_lines++;
sprintf (visual_tbl + strlen (visual_tbl), ";; %-8d", clock);
for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
if (function_units[unit].bitmask & target_units)
for (i = 0; i < function_units[unit].multiplicity; i++)
{
int instance = unit + i * FUNCTION_UNITS_SIZE;
rtx insn = unit_last_insn[instance];
if (insn &&
actual_hazard_this_instance (unit, instance, insn, clock, 0))
{
char str[BUF_LEN];
print_insn (str, insn, 0);
str[INSN_LEN] = '\0';
sprintf (visual_tbl + strlen (visual_tbl), " %-33s", str);
}
else
sprintf (visual_tbl + strlen (visual_tbl), " %-33s", "------------------------------");
}
for (i = 0; i < n_vis_no_unit; i++)
sprintf (visual_tbl + strlen (visual_tbl), " %-8d",
INSN_UID (vis_no_unit[i]));
n_vis_no_unit = 0;
sprintf (visual_tbl + strlen (visual_tbl), "\n");
}
static void
visualize_stall_cycles (b, stalls)
int b, stalls;
{
int i;
if (n_visual_lines >= MAX_VISUAL_LINES)
{
print_block_visualization (b, "(incomplete)");
init_block_visualization ();
}
n_visual_lines++;
sprintf (visual_tbl + strlen (visual_tbl), ";; ");
for (i = 0; i < stalls; i++)
sprintf (visual_tbl + strlen (visual_tbl), ".");
sprintf (visual_tbl + strlen (visual_tbl), "\n");
}
static rtx
move_insn1 (insn, last)
rtx insn, last;
{
NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
NEXT_INSN (insn) = NEXT_INSN (last);
PREV_INSN (NEXT_INSN (last)) = insn;
NEXT_INSN (last) = insn;
PREV_INSN (insn) = last;
return insn;
}
static rtx
reemit_notes (insn, last)
rtx insn;
rtx last;
{
rtx note, retval;
retval = last;
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
{
if (REG_NOTE_KIND (note) == REG_DEAD
&& GET_CODE (XEXP (note, 0)) == CONST_INT)
{
int note_type = INTVAL (XEXP (note, 0));
if (note_type == NOTE_INSN_SETJMP)
{
retval = emit_note_after (NOTE_INSN_SETJMP, insn);
CONST_CALL_P (retval) = CONST_CALL_P (note);
remove_note (insn, note);
note = XEXP (note, 1);
}
else if (note_type == NOTE_INSN_RANGE_START
|| note_type == NOTE_INSN_RANGE_END)
{
last = emit_note_before (note_type, last);
remove_note (insn, note);
note = XEXP (note, 1);
NOTE_RANGE_INFO (last) = XEXP (note, 0);
}
else
{
last = emit_note_before (INTVAL (XEXP (note, 0)), last);
remove_note (insn, note);
note = XEXP (note, 1);
NOTE_BLOCK_NUMBER (last) = INTVAL (XEXP (note, 0));
}
remove_note (insn, note);
}
}
return retval;
}
static rtx
move_insn (insn, last)
rtx insn, last;
{
rtx retval = NULL;
while (SCHED_GROUP_P (insn))
{
rtx prev = PREV_INSN (insn);
move_insn1 (insn, last);
if (retval == NULL_RTX)
retval = reemit_notes (insn, insn);
else
reemit_notes (insn, insn);
insn = prev;
}
move_insn1 (insn, last);
if (retval == NULL_RTX)
retval = reemit_notes (insn, insn);
else
reemit_notes (insn, insn);
return retval;
}
static rtx
group_leader (insn)
rtx insn;
{
rtx prev;
do
{
prev = insn;
insn = next_nonnote_insn (insn);
}
while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
return prev;
}
static int
schedule_block (bb, rgn_n_insns)
int bb;
int rgn_n_insns;
{
rtx insn, last;
rtx *ready;
int i;
int n_ready = 0;
int can_issue_more;
int b = BB_TO_BLOCK (bb);
int target_n_insns = 0;
int sched_target_n_insns = 0;
int sched_n_insns = 0;
#define NEED_NOTHING 0
#define NEED_HEAD 1
#define NEED_TAIL 2
int new_needs;
rtx prev_head;
rtx next_tail;
rtx head;
rtx tail;
int bb_src;
get_block_head_tail (bb, &head, &tail);
if (GET_RTX_CLASS (GET_CODE (head)) == 'i')
{
rtx note;
for (note = REG_NOTES (head); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_DEAD
&& GET_CODE (XEXP (note, 0)) == CONST_INT)
remove_note (head, note);
}
next_tail = NEXT_INSN (tail);
prev_head = PREV_INSN (head);
if (head == tail
&& (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
return (sched_n_insns);
if (sched_verbose)
{
fprintf (dump, ";; ======================================================\n");
fprintf (dump,
";; -- basic block %d from %d to %d -- %s reload\n",
b, INSN_UID (BLOCK_HEAD (b)), INSN_UID (BLOCK_END (b)),
(reload_completed ? "after" : "before"));
fprintf (dump, ";; ======================================================\n");
fprintf (dump, "\n");
visual_tbl = (char *) alloca (get_visual_tbl_length ());
init_block_visualization ();
}
note_list = 0;
rm_other_notes (head, tail);
target_bb = bb;
if (current_nr_blocks > 1)
{
candidate_table = (candidate *) alloca (current_nr_blocks * sizeof (candidate));
bblst_last = 0;
bblst_size = (current_nr_blocks - bb) * rgn_nr_edges * 2;
bblst_table = (int *) alloca (bblst_size * sizeof (int));
bitlst_table_last = 0;
bitlst_table_size = rgn_nr_edges;
bitlst_table = (int *) alloca (rgn_nr_edges * sizeof (int));
compute_trg_info (bb);
}
clear_units ();
ready = (rtx *) alloca ((rgn_n_insns + 1) * sizeof (rtx));
if (sched_verbose >= 5)
debug_dependencies ();
n_ready = 0;
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
{
rtx next;
if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
continue;
next = NEXT_INSN (insn);
if (INSN_DEP_COUNT (insn) == 0
&& (SCHED_GROUP_P (next) == 0 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
ready[n_ready++] = insn;
if (!(SCHED_GROUP_P (insn)))
target_n_insns++;
}
for (bb_src = 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_src, &head, &tail);
src_next_tail = NEXT_INSN (tail);
src_head = head;
if (head == tail
&& (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
continue;
for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
continue;
if (!CANT_MOVE (insn)
&& (!IS_SPECULATIVE_INSN (insn)
|| (insn_issue_delay (insn) <= 3
&& check_live (insn, bb_src)
&& is_exception_free (insn, bb_src, target_bb))))
{
rtx next;
next = NEXT_INSN (insn);
if (INSN_DEP_COUNT (insn) == 0
&& (SCHED_GROUP_P (next) == 0
|| GET_RTX_CLASS (GET_CODE (next)) != 'i'))
ready[n_ready++] = insn;
}
}
}
#ifdef MD_SCHED_INIT
MD_SCHED_INIT (dump, sched_verbose);
#endif
last_scheduled_insn = 0;
SCHED_SORT (ready, n_ready);
#ifdef MD_SCHED_REORDER
MD_SCHED_REORDER (dump, sched_verbose, ready, n_ready);
#endif
if (sched_verbose >= 2)
{
fprintf (dump, ";;\t\tReady list initially: ");
debug_ready_list (ready, n_ready);
}
q_ptr = 0;
q_size = 0;
clock_var = 0;
last_clock_var = 0;
bzero ((char *) insn_queue, sizeof (insn_queue));
last = prev_head;
new_needs = (NEXT_INSN (prev_head) == BLOCK_HEAD (b)
? NEED_HEAD : NEED_NOTHING);
if (PREV_INSN (next_tail) == BLOCK_END (b))
new_needs |= NEED_TAIL;
while (sched_target_n_insns < target_n_insns)
{
int b1;
clock_var++;
n_ready = queue_to_ready (ready, n_ready);
if (n_ready == 0)
abort ();
if (sched_verbose >= 2)
{
fprintf (dump, ";;\t\tReady list after queue_to_ready: ");
debug_ready_list (ready, n_ready);
}
SCHED_SORT (ready, n_ready);
#ifdef MD_SCHED_REORDER
MD_SCHED_REORDER (dump, sched_verbose, ready, n_ready);
#endif
if (sched_verbose)
{
fprintf (dump, "\n;;\tReady list (t =%3d): ", clock_var);
debug_ready_list (ready, n_ready);
}
can_issue_more = issue_rate;
for (i = n_ready - 1; i >= 0 && can_issue_more; i--)
{
rtx insn = ready[i];
int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
if (cost > 1)
{
queue_insn (insn, cost);
ready[i] = ready[--n_ready];
}
else if (cost == 0)
{
if (INSN_BB (insn) != target_bb)
{
rtx temp;
if (IS_SPECULATIVE_INSN (insn))
{
if (!check_live (insn, INSN_BB (insn)))
{
ready[i] = ready[--n_ready];
continue;
}
update_live (insn, INSN_BB (insn));
if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
set_spec_fed (insn);
nr_spec++;
}
nr_inter++;
temp = insn;
while (SCHED_GROUP_P (temp))
temp = PREV_INSN (temp);
b1 = INSN_BLOCK (temp);
if (temp == BLOCK_HEAD (b1)
&& insn == BLOCK_END (b1))
{
emit_note_after (NOTE_INSN_DELETED, insn);
BLOCK_END (b1) = NEXT_INSN (insn);
BLOCK_HEAD (b1) = NEXT_INSN (insn);
}
else if (insn == BLOCK_END (b1))
{
BLOCK_END (b1) = PREV_INSN (temp);
}
else if (temp == BLOCK_HEAD (b1))
{
BLOCK_HEAD (b1) = NEXT_INSN (insn);
}
}
else
{
sched_target_n_insns++;
}
last_scheduled_insn = insn;
last = move_insn (insn, last);
sched_n_insns++;
#ifdef MD_SCHED_VARIABLE_ISSUE
MD_SCHED_VARIABLE_ISSUE (dump, sched_verbose, insn, can_issue_more);
#else
can_issue_more--;
#endif
n_ready = schedule_insn (insn, ready, n_ready, clock_var);
ready[i] = ready[--n_ready];
if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
break;
}
}
if (sched_verbose)
{
visualize_scheduled_insns (b, clock_var);
}
}
if (sched_verbose)
{
fprintf (dump, ";;\tReady list (final): ");
debug_ready_list (ready, n_ready);
print_block_visualization (b, "");
}
if (current_nr_blocks > 1)
if (!flag_schedule_interblock && q_size != 0)
abort ();
head = NEXT_INSN (prev_head);
tail = last;
if (note_list != 0)
{
rtx note_head = note_list;
while (PREV_INSN (note_head))
{
note_head = PREV_INSN (note_head);
}
PREV_INSN (note_head) = PREV_INSN (head);
NEXT_INSN (PREV_INSN (head)) = note_head;
PREV_INSN (head) = note_list;
NEXT_INSN (note_list) = head;
head = note_head;
}
if (new_needs & NEED_HEAD)
BLOCK_HEAD (b) = head;
if (new_needs & NEED_TAIL)
BLOCK_END (b) = tail;
if (sched_verbose)
{
fprintf (dump, ";; total time = %d\n;; new basic block head = %d\n",
clock_var, INSN_UID (BLOCK_HEAD (b)));
fprintf (dump, ";; new basic block end = %d\n\n",
INSN_UID (BLOCK_END (b)));
}
return (sched_n_insns);
}
extern void
debug_reg_vector (s)
regset s;
{
int regno;
EXECUTE_IF_SET_IN_REG_SET (s, 0, regno,
{
fprintf (dump, " %d", regno);
});
fprintf (dump, "\n");
}
static void
compute_block_forward_dependences (bb)
int bb;
{
rtx insn, link;
rtx tail, head;
rtx next_tail;
enum reg_note dep_type;
get_block_head_tail (bb, &head, &tail);
next_tail = NEXT_INSN (tail);
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
continue;
insn = group_leader (insn);
for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
{
rtx x = group_leader (XEXP (link, 0));
rtx new_link;
if (x != XEXP (link, 0))
continue;
if (GET_CODE (x) == NOTE || INSN_DELETED_P (x))
continue;
if (find_insn_list (insn, INSN_DEPEND (x)))
continue;
new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
dep_type = REG_NOTE_KIND (link);
PUT_REG_NOTE_KIND (new_link, dep_type);
INSN_DEPEND (x) = new_link;
INSN_DEP_COUNT (insn) += 1;
}
}
}
__inline static void
init_rgn_data_dependences (n_bbs)
int n_bbs;
{
int bb;
bzero ((char *) bb_pending_read_insns, n_bbs * sizeof (rtx));
bzero ((char *) bb_pending_read_mems, n_bbs * sizeof (rtx));
bzero ((char *) bb_pending_write_insns, n_bbs * sizeof (rtx));
bzero ((char *) bb_pending_write_mems, n_bbs * sizeof (rtx));
bzero ((char *) bb_pending_lists_length, n_bbs * sizeof (rtx));
bzero ((char *) bb_last_pending_memory_flush, n_bbs * sizeof (rtx));
bzero ((char *) bb_last_function_call, n_bbs * sizeof (rtx));
bzero ((char *) bb_sched_before_next_call, n_bbs * sizeof (rtx));
for (bb = 0; bb < n_bbs; bb++)
{
bb_sched_before_next_call[bb] =
gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
NULL_RTX, 0, NULL_RTX, NULL_RTX);
LOG_LINKS (bb_sched_before_next_call[bb]) = 0;
}
}
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
#ifdef HAVE_cc0
|| sets_cc0_p (PATTERN (insn))
#endif
))
|| 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;
while (SCHED_GROUP_P (insn))
{
rtx temp = prev_nonnote_insn (insn);
add_dependence (insn, temp, REG_DEP_ANTI);
insn = temp;
}
}
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 (!find_insn_list (last, LOG_LINKS (insn)))
add_dependence (last, insn, REG_DEP_ANTI);
INSN_REF_COUNT (insn) = 1;
while (SCHED_GROUP_P (insn))
insn = prev_nonnote_insn (insn);
}
}
static void
compute_block_backward_dependences (bb)
int bb;
{
int b;
rtx x;
rtx head, tail;
int max_reg = max_reg_num ();
b = BB_TO_BLOCK (bb);
if (current_nr_blocks == 1)
{
reg_last_uses = (rtx *) alloca (max_reg * sizeof (rtx));
reg_last_sets = (rtx *) alloca (max_reg * sizeof (rtx));
reg_last_clobbers = (rtx *) alloca (max_reg * sizeof (rtx));
bzero ((char *) reg_last_uses, max_reg * sizeof (rtx));
bzero ((char *) reg_last_sets, max_reg * sizeof (rtx));
bzero ((char *) reg_last_clobbers, max_reg * sizeof (rtx));
pending_read_insns = 0;
pending_read_mems = 0;
pending_write_insns = 0;
pending_write_mems = 0;
pending_lists_length = 0;
last_function_call = 0;
last_pending_memory_flush = 0;
sched_before_next_call
= gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
NULL_RTX, 0, NULL_RTX, NULL_RTX);
LOG_LINKS (sched_before_next_call) = 0;
}
else
{
reg_last_uses = bb_reg_last_uses[bb];
reg_last_sets = bb_reg_last_sets[bb];
reg_last_clobbers = bb_reg_last_clobbers[bb];
pending_read_insns = bb_pending_read_insns[bb];
pending_read_mems = bb_pending_read_mems[bb];
pending_write_insns = bb_pending_write_insns[bb];
pending_write_mems = bb_pending_write_mems[bb];
pending_lists_length = bb_pending_lists_length[bb];
last_function_call = bb_last_function_call[bb];
last_pending_memory_flush = bb_last_pending_memory_flush[bb];
sched_before_next_call = bb_sched_before_next_call[bb];
}
get_block_head_tail (bb, &head, &tail);
sched_analyze (head, tail);
add_branch_dependences (head, tail);
if (current_nr_blocks > 1)
{
int e, first_edge;
int b_succ, bb_succ;
int reg;
rtx link_insn, link_mem;
rtx u;
bb_pending_read_insns[bb] = pending_read_insns;
bb_pending_read_mems[bb] = pending_read_mems;
bb_pending_write_insns[bb] = pending_write_insns;
bb_pending_write_mems[bb] = pending_write_mems;
first_edge = e = OUT_EDGES (b);
if (e > 0)
do
{
b_succ = TO_BLOCK (e);
bb_succ = BLOCK_TO_BB (b_succ);
if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
|| bb_succ <= bb)
{
e = NEXT_OUT (e);
continue;
}
for (reg = 0; reg < max_reg; reg++)
{
for (u = reg_last_uses[reg]; u; u = XEXP (u, 1))
{
if (find_insn_list (XEXP (u, 0), (bb_reg_last_uses[bb_succ])[reg]))
continue;
(bb_reg_last_uses[bb_succ])[reg]
= alloc_INSN_LIST (XEXP (u, 0),
(bb_reg_last_uses[bb_succ])[reg]);
}
for (u = reg_last_sets[reg]; u; u = XEXP (u, 1))
{
if (find_insn_list (XEXP (u, 0), (bb_reg_last_sets[bb_succ])[reg]))
continue;
(bb_reg_last_sets[bb_succ])[reg]
= alloc_INSN_LIST (XEXP (u, 0),
(bb_reg_last_sets[bb_succ])[reg]);
}
for (u = reg_last_clobbers[reg]; u; u = XEXP (u, 1))
{
if (find_insn_list (XEXP (u, 0), (bb_reg_last_clobbers[bb_succ])[reg]))
continue;
(bb_reg_last_clobbers[bb_succ])[reg]
= alloc_INSN_LIST (XEXP (u, 0),
(bb_reg_last_clobbers[bb_succ])[reg]);
}
}
link_insn = pending_read_insns;
link_mem = pending_read_mems;
while (link_insn)
{
if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
bb_pending_read_insns[bb_succ],
bb_pending_read_mems[bb_succ])))
add_insn_mem_dependence (&bb_pending_read_insns[bb_succ],
&bb_pending_read_mems[bb_succ],
XEXP (link_insn, 0), XEXP (link_mem, 0));
link_insn = XEXP (link_insn, 1);
link_mem = XEXP (link_mem, 1);
}
link_insn = pending_write_insns;
link_mem = pending_write_mems;
while (link_insn)
{
if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
bb_pending_write_insns[bb_succ],
bb_pending_write_mems[bb_succ])))
add_insn_mem_dependence (&bb_pending_write_insns[bb_succ],
&bb_pending_write_mems[bb_succ],
XEXP (link_insn, 0), XEXP (link_mem, 0));
link_insn = XEXP (link_insn, 1);
link_mem = XEXP (link_mem, 1);
}
for (u = last_function_call; u; u = XEXP (u, 1))
{
if (find_insn_list (XEXP (u, 0), bb_last_function_call[bb_succ]))
continue;
bb_last_function_call[bb_succ]
= alloc_INSN_LIST (XEXP (u, 0),
bb_last_function_call[bb_succ]);
}
for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
{
if (find_insn_list (XEXP (u, 0), bb_last_pending_memory_flush[bb_succ]))
continue;
bb_last_pending_memory_flush[bb_succ]
= alloc_INSN_LIST (XEXP (u, 0),
bb_last_pending_memory_flush[bb_succ]);
}
x = LOG_LINKS (sched_before_next_call);
for (; x; x = XEXP (x, 1))
add_dependence (bb_sched_before_next_call[bb_succ],
XEXP (x, 0), REG_DEP_ANTI);
e = NEXT_OUT (e);
}
while (e != first_edge);
}
for (b = 0; b < max_reg; ++b)
{
if (reg_last_clobbers[b])
free_list (®_last_clobbers[b], &unused_insn_list);
if (reg_last_sets[b])
free_list (®_last_sets[b], &unused_insn_list);
if (reg_last_uses[b])
free_list (®_last_uses[b], &unused_insn_list);
}
if (current_nr_blocks > 1)
{
bb_reg_last_uses[bb] = (rtx *) NULL_RTX;
bb_reg_last_sets[bb] = (rtx *) NULL_RTX;
bb_reg_last_clobbers[bb] = (rtx *) NULL_RTX;
}
}
void
debug_dependencies ()
{
int bb;
fprintf (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, &head, &tail);
next_tail = NEXT_INSN (tail);
fprintf (dump, "\n;; --- Region Dependences --- b %d bb %d \n",
BB_TO_BLOCK (bb), bb);
fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
"insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
"----", "----", "--", "---", "----", "----", "--------", "-----");
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
{
rtx link;
int unit, range;
if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
{
int n;
fprintf (dump, ";; %6d ", INSN_UID (insn));
if (GET_CODE (insn) == NOTE)
{
n = NOTE_LINE_NUMBER (insn);
if (n < 0)
fprintf (dump, "%s\n", GET_NOTE_INSN_NAME (n));
else
fprintf (dump, "line %d, file %s\n", n,
NOTE_SOURCE_FILE (insn));
}
else
fprintf (dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
continue;
}
unit = insn_unit (insn);
range = (unit < 0
|| function_units[unit].blockage_range_function == 0) ? 0 :
function_units[unit].blockage_range_function (insn);
fprintf (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 (dump, "\t: ");
for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
fprintf (dump, "%d ", INSN_UID (XEXP (link, 0)));
fprintf (dump, "\n");
}
}
}
fprintf (dump, "\n");
}
static int
set_priorities (bb)
int bb;
{
rtx insn;
int n_insn;
rtx tail;
rtx prev_head;
rtx head;
get_block_head_tail (bb, &head, &tail);
prev_head = PREV_INSN (head);
if (head == tail
&& (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
return 0;
n_insn = 0;
for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
{
if (GET_CODE (insn) == NOTE)
continue;
if (!(SCHED_GROUP_P (insn)))
n_insn++;
(void) priority (insn);
}
return n_insn;
}
static void
init_rtx_vector (vector, space, nelts, bytes_per_elt)
rtx **vector;
rtx *space;
int nelts;
int bytes_per_elt;
{
register int i;
register rtx *p = space;
for (i = 0; i < nelts; i++)
{
vector[i] = p;
p += bytes_per_elt / sizeof (*p);
}
}
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);
reg_pending_sets = ALLOCA_REG_SET ();
reg_pending_clobbers = ALLOCA_REG_SET ();
reg_pending_sets_all = 0;
if (current_nr_blocks > 1)
{
rtx *space;
int maxreg = max_reg_num ();
bb_reg_last_uses = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
init_rtx_vector (bb_reg_last_uses, space, current_nr_blocks,
maxreg * sizeof (rtx *));
bb_reg_last_sets = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
init_rtx_vector (bb_reg_last_sets, space, current_nr_blocks,
maxreg * sizeof (rtx *));
bb_reg_last_clobbers =
(rtx **) alloca (current_nr_blocks * sizeof (rtx *));
space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
init_rtx_vector (bb_reg_last_clobbers, space, current_nr_blocks,
maxreg * sizeof (rtx *));
bb_pending_read_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
bb_pending_read_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
bb_pending_write_insns =
(rtx *) alloca (current_nr_blocks * sizeof (rtx));
bb_pending_write_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
bb_pending_lists_length =
(int *) alloca (current_nr_blocks * sizeof (int));
bb_last_pending_memory_flush =
(rtx *) alloca (current_nr_blocks * sizeof (rtx));
bb_last_function_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
bb_sched_before_next_call =
(rtx *) alloca (current_nr_blocks * sizeof (rtx));
init_rgn_data_dependences (current_nr_blocks);
}
for (bb = 0; bb < current_nr_blocks; bb++)
compute_block_backward_dependences (bb);
for (bb = current_nr_blocks - 1; bb >= 0; bb--)
compute_block_forward_dependences (bb);
dead_notes = 0;
for (bb = 0; bb < current_nr_blocks; bb++)
{
if (reload_completed == 0)
find_pre_sched_live (bb);
if (write_symbols != NO_DEBUG)
{
save_line_notes (bb);
rm_line_notes (bb);
}
rgn_n_insns += set_priorities (bb);
}
if (current_nr_blocks > 1)
{
int i;
prob = (float *) alloca ((current_nr_blocks) * sizeof (float));
bbset_size = current_nr_blocks / HOST_BITS_PER_WIDE_INT + 1;
dom = (bbset *) alloca (current_nr_blocks * sizeof (bbset));
for (i = 0; i < current_nr_blocks; i++)
{
dom[i] = (bbset) alloca (bbset_size * sizeof (HOST_WIDE_INT));
bzero ((char *) dom[i], bbset_size * sizeof (HOST_WIDE_INT));
}
rgn_nr_edges = 0;
edge_to_bit = (int *) alloca (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 *) alloca (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;
edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
pot_split = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
ancestor_edges = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
for (i = 0; i < current_nr_blocks; i++)
{
pot_split[i] =
(edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
bzero ((char *) pot_split[i],
edgeset_size * sizeof (HOST_WIDE_INT));
ancestor_edges[i] =
(edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
bzero ((char *) ancestor_edges[i],
edgeset_size * sizeof (HOST_WIDE_INT));
}
for (bb = 0; bb < current_nr_blocks; bb++)
compute_dom_prob_ps (bb);
}
for (bb = 0; bb < current_nr_blocks; bb++)
{
sched_rgn_n_insns += schedule_block (bb, rgn_n_insns);
#ifdef USE_C_ALLOCA
alloca (0);
#endif
}
if (sched_rgn_n_insns != rgn_n_insns)
abort ();
if (reload_completed == 0)
{
for (bb = current_nr_blocks - 1; bb >= 0; bb--)
find_post_sched_live (bb);
if (current_nr_blocks <= 1)
if (dead_notes != 0)
abort ();
}
if (write_symbols != NO_DEBUG)
{
for (bb = 0; bb < current_nr_blocks; bb++)
restore_line_notes (bb);
}
free_pending_lists ();
FREE_REG_SET (reg_pending_sets);
FREE_REG_SET (reg_pending_clobbers);
}
static void
split_hard_reg_notes (note, first, last)
rtx note, first, last;
{
rtx reg, temp, link;
int n_regs, i, new_reg;
rtx insn;
if (REG_NOTE_KIND (note) != REG_DEAD)
abort ();
reg = XEXP (note, 0);
n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
for (i = 0; i < n_regs; i++)
{
new_reg = REGNO (reg) + i;
for (insn = last;; insn = PREV_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
&& (temp = regno_use_in (new_reg, PATTERN (insn))))
{
link = alloc_EXPR_LIST (REG_DEAD, temp, REG_NOTES (insn));
REG_NOTES (insn) = link;
i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
break;
}
if (insn == first)
break;
}
}
}
static void
new_insn_dead_notes (pat, insn, last, orig_insn)
rtx pat, insn, last, orig_insn;
{
rtx dest, tem, set;
dest = XEXP (pat, 0);
while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == STRICT_LOW_PART
|| GET_CODE (dest) == SIGN_EXTRACT)
dest = XEXP (dest, 0);
if (GET_CODE (dest) == REG)
{
if (reg_referenced_p (dest, PATTERN (orig_insn)))
return;
for (tem = last; tem != insn; tem = PREV_INSN (tem))
{
if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
&& reg_overlap_mentioned_p (dest, PATTERN (tem))
&& (set = single_set (tem)))
{
rtx tem_dest = SET_DEST (set);
while (GET_CODE (tem_dest) == ZERO_EXTRACT
|| GET_CODE (tem_dest) == SUBREG
|| GET_CODE (tem_dest) == STRICT_LOW_PART
|| GET_CODE (tem_dest) == SIGN_EXTRACT)
tem_dest = XEXP (tem_dest, 0);
if (!rtx_equal_p (tem_dest, dest))
{
if (!find_regno_note (tem, REG_UNUSED, REGNO (dest))
&& !find_regno_note (tem, REG_DEAD, REGNO (dest)))
{
rtx note = alloc_EXPR_LIST (REG_DEAD, dest,
REG_NOTES (tem));
REG_NOTES (tem) = note;
}
break;
}
else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
break;
}
}
if (tem == insn)
{
int live_after_orig_insn = 0;
rtx pattern = PATTERN (orig_insn);
int i;
if (GET_CODE (pat) == CLOBBER)
{
rtx note = alloc_EXPR_LIST (REG_UNUSED, dest, REG_NOTES (insn));
REG_NOTES (insn) = note;
return;
}
if (GET_CODE (pattern) == SET)
{
if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
live_after_orig_insn = 1;
}
else if (GET_CODE (pattern) == PARALLEL)
{
for (i = 0; i < XVECLEN (pattern, 0); i++)
if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
&& reg_overlap_mentioned_p (dest,
SET_DEST (XVECEXP (pattern,
0, i))))
live_after_orig_insn = 1;
}
if (!live_after_orig_insn)
abort ();
}
}
}
static void
update_n_sets (x, inc)
rtx x;
int inc;
{
rtx dest = SET_DEST (x);
while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
dest = SUBREG_REG (dest);
if (GET_CODE (dest) == REG)
{
int regno = REGNO (dest);
if (regno < FIRST_PSEUDO_REGISTER)
{
register int i;
int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
for (i = regno; i < endregno; i++)
REG_N_SETS (i) += inc;
}
else
REG_N_SETS (regno) += inc;
}
}
void
update_flow_info (notes, first, last, orig_insn)
rtx notes;
rtx first, last;
rtx orig_insn;
{
rtx insn, note;
rtx next;
rtx orig_dest, temp;
rtx set;
orig_dest = single_set (orig_insn);
if (orig_dest)
orig_dest = SET_DEST (orig_dest);
for (note = notes; note; note = next)
{
next = XEXP (note, 1);
switch (REG_NOTE_KIND (note))
{
case REG_DEAD:
case REG_UNUSED:
for (insn = last;; insn = PREV_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
&& reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
{
temp = XEXP (note, 0);
if (REG_NOTE_KIND (note) == REG_DEAD
&& GET_CODE (temp) == REG
&& REGNO (temp) < FIRST_PSEUDO_REGISTER
&& HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
split_hard_reg_notes (note, first, last);
else
{
XEXP (note, 1) = REG_NOTES (insn);
REG_NOTES (insn) = note;
}
if (REG_NOTE_KIND (note) == REG_UNUSED
&& GET_CODE (XEXP (note, 0)) != SCRATCH
&& !dead_or_set_p (insn, XEXP (note, 0)))
PUT_REG_NOTE_KIND (note, REG_DEAD);
break;
}
if (insn == first)
{
if (REG_NOTE_KIND (note) != REG_UNUSED)
abort ();
break;
}
}
break;
case REG_WAS_0:
if (GET_CODE (XEXP (note, 0)) == NOTE
|| INSN_DELETED_P (XEXP (note, 0)))
break;
if (!orig_dest)
abort ();
for (insn = first;; insn = NEXT_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
&& (temp = single_set (insn))
&& rtx_equal_p (SET_DEST (temp), orig_dest))
{
XEXP (note, 1) = REG_NOTES (insn);
REG_NOTES (insn) = note;
break;
}
if (GET_CODE (orig_dest) == REG
&& REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
&& HARD_REGNO_NREGS (REGNO (orig_dest),
GET_MODE (orig_dest)) > 1)
break;
if (insn == last)
abort ();
}
break;
case REG_EQUAL:
case REG_EQUIV:
if (!orig_dest)
break;
case REG_NO_CONFLICT:
if (!orig_dest)
abort ();
for (insn = last;; insn = PREV_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
&& (temp = single_set (insn))
&& rtx_equal_p (SET_DEST (temp), orig_dest))
{
XEXP (note, 1) = REG_NOTES (insn);
REG_NOTES (insn) = note;
break;
}
if (insn == first)
{
if (GET_CODE (orig_dest) == REG
&& REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
&& HARD_REGNO_NREGS (REGNO (orig_dest),
GET_MODE (orig_dest)) > 1)
break;
if (GET_CODE (orig_dest) == MEM
&& SIZE_FOR_MODE (orig_dest) > UNITS_PER_WORD)
break;
abort ();
}
}
break;
case REG_LIBCALL:
XEXP (note, 1) = REG_NOTES (first);
REG_NOTES (first) = note;
insn = XEXP (note, 0);
note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
if (note)
XEXP (note, 0) = first;
break;
case REG_EXEC_COUNT:
XEXP (note, 1) = REG_NOTES (first);
REG_NOTES (first) = note;
break;
case REG_RETVAL:
XEXP (note, 1) = REG_NOTES (last);
REG_NOTES (last) = note;
insn = XEXP (note, 0);
note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
if (note)
XEXP (note, 0) = last;
break;
case REG_NONNEG:
case REG_BR_PROB:
for (insn = last;; insn = PREV_INSN (insn))
{
if (GET_CODE (insn) == JUMP_INSN)
{
XEXP (note, 1) = REG_NOTES (insn);
REG_NOTES (insn) = note;
break;
}
if (insn == first)
abort ();
}
break;
case REG_INC:
if (reload_completed)
break;
abort ();
case REG_LABEL:
for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
&& reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
{
REG_NOTES (insn) = alloc_EXPR_LIST (REG_LABEL,
XEXP (note, 0),
REG_NOTES (insn));
}
break;
case REG_CC_SETTER:
case REG_CC_USER:
default:
abort ();
}
}
for (insn = first; insn != last; insn = NEXT_INSN (insn))
{
rtx pat;
int i;
pat = PATTERN (insn);
if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
new_insn_dead_notes (pat, insn, last, orig_insn);
else if (GET_CODE (pat) == PARALLEL)
{
for (i = 0; i < XVECLEN (pat, 0); i++)
if (GET_CODE (XVECEXP (pat, 0, i)) == SET
|| GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
}
}
set = single_set (last);
if (set)
{
rtx dest = SET_DEST (set);
while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == STRICT_LOW_PART
|| GET_CODE (dest) == SIGN_EXTRACT)
dest = XEXP (dest, 0);
if (GET_CODE (dest) == REG
&& (REGNO (dest) >= FIRST_PSEUDO_REGISTER
|| ! global_regs[REGNO (dest)]))
{
rtx stop_insn = PREV_INSN (first);
insn = last;
if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
{
for (insn = PREV_INSN (insn); insn != first;
insn = PREV_INSN (insn))
{
if ((set = single_set (insn))
&& reg_mentioned_p (dest, SET_DEST (set))
&& ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
break;
}
}
for (insn = PREV_INSN (insn); insn != stop_insn;
insn = PREV_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
&& reg_mentioned_p (dest, PATTERN (insn))
&& (set = single_set (insn)))
{
rtx insn_dest = SET_DEST (set);
while (GET_CODE (insn_dest) == ZERO_EXTRACT
|| GET_CODE (insn_dest) == SUBREG
|| GET_CODE (insn_dest) == STRICT_LOW_PART
|| GET_CODE (insn_dest) == SIGN_EXTRACT)
insn_dest = XEXP (insn_dest, 0);
if (insn_dest != dest)
{
note = alloc_EXPR_LIST (REG_DEAD, dest, REG_NOTES (insn));
REG_NOTES (insn) = note;
break;
}
}
}
}
}
if (orig_dest && GET_CODE (orig_dest) == REG)
{
int found_orig_dest = 0;
int found_split_dest = 0;
for (insn = first;; insn = NEXT_INSN (insn))
{
rtx pat;
int i;
if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
continue;
pat = PATTERN (insn);
i = GET_CODE (pat) == PARALLEL ? XVECLEN (pat, 0) : 0;
set = pat;
for (;;)
{
if (GET_CODE (set) == SET)
{
if (GET_CODE (SET_DEST (set)) == REG
&& REGNO (SET_DEST (set)) == REGNO (orig_dest))
{
found_orig_dest = 1;
break;
}
else if (GET_CODE (SET_DEST (set)) == SUBREG
&& SUBREG_REG (SET_DEST (set)) == orig_dest)
{
found_split_dest = 1;
break;
}
}
if (--i < 0)
break;
set = XVECEXP (pat, 0, i);
}
if (insn == last)
break;
}
if (found_split_dest)
{
for (insn = first; insn; insn = PREV_INSN (insn))
{
if (GET_CODE (insn) == CODE_LABEL
|| GET_CODE (insn) == JUMP_INSN)
break;
else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
&& reg_mentioned_p (orig_dest, insn))
{
note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
if (note)
remove_note (insn, note);
}
}
}
else if (!found_orig_dest)
{
int i, regno;
if (REGNO (orig_dest) >= FIRST_PSEUDO_REGISTER)
abort ();
regno = REGNO (orig_dest);
for (i = HARD_REGNO_NREGS (regno, GET_MODE (orig_dest)) - 1;
i >= 0; i--)
if (! refers_to_regno_p (regno + i, regno + i + 1, orig_insn,
NULL_PTR))
break;
if (i >= 0)
abort ();
}
}
{
rtx x = PATTERN (orig_insn);
RTX_CODE code = GET_CODE (x);
if (code == SET || code == CLOBBER)
update_n_sets (x, -1);
else if (code == PARALLEL)
{
int i;
for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
{
code = GET_CODE (XVECEXP (x, 0, i));
if (code == SET || code == CLOBBER)
update_n_sets (XVECEXP (x, 0, i), -1);
}
}
for (insn = first;; insn = NEXT_INSN (insn))
{
x = PATTERN (insn);
code = GET_CODE (x);
if (code == SET || code == CLOBBER)
update_n_sets (x, 1);
else if (code == PARALLEL)
{
int i;
for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
{
code = GET_CODE (XVECEXP (x, 0, i));
if (code == SET || code == CLOBBER)
update_n_sets (XVECEXP (x, 0, i), 1);
}
}
if (insn == last)
break;
}
}
}
void
schedule_insns (dump_file)
FILE *dump_file;
{
int max_uid;
int b;
rtx insn;
int rgn;
int luid;
#ifdef HAVE_cc0
flag_schedule_speculative_load = 0;
#endif
if (n_basic_blocks == 0)
return;
sched_verbose = sched_verbose_param;
if (sched_verbose_param == 0 && dump_file)
sched_verbose = 1;
dump = ((sched_verbose_param >= 10 || !dump_file) ? stderr : dump_file);
nr_inter = 0;
nr_spec = 0;
if (reload_completed == 0 || !flag_schedule_insns)
{
unused_insn_list = 0;
unused_expr_list = 0;
}
issue_rate = ISSUE_RATE;
for (b = 0; b < n_basic_blocks; b++)
split_block_insns (b, 1);
max_uid = (get_max_uid () + 1);
cant_move = (char *) xmalloc (max_uid * sizeof (char));
bzero ((char *) cant_move, max_uid * sizeof (char));
fed_by_spec_load = (char *) xmalloc (max_uid * sizeof (char));
bzero ((char *) fed_by_spec_load, max_uid * sizeof (char));
is_load_insn = (char *) xmalloc (max_uid * sizeof (char));
bzero ((char *) is_load_insn, max_uid * sizeof (char));
insn_orig_block = (int *) xmalloc (max_uid * sizeof (int));
insn_luid = (int *) xmalloc (max_uid * sizeof (int));
luid = 0;
for (b = 0; b < n_basic_blocks; b++)
for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
{
INSN_BLOCK (insn) = b;
INSN_LUID (insn) = luid++;
if (insn == BLOCK_END (b))
break;
}
if (reload_completed)
{
int b;
rtx insn;
for (b = 0; b < n_basic_blocks; b++)
for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
{
rtx link, prev;
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
prev = NULL_RTX;
link = LOG_LINKS (insn);
while (link)
{
rtx x = XEXP (link, 0);
if (INSN_BLOCK (x) != b)
{
remove_dependence (insn, x);
link = prev ? XEXP (prev, 1) : LOG_LINKS (insn);
}
else
prev = link, link = XEXP (prev, 1);
}
}
if (insn == BLOCK_END (b))
break;
}
}
nr_regions = 0;
rgn_table = (region *) alloca ((n_basic_blocks) * sizeof (region));
rgn_bb_table = (int *) alloca ((n_basic_blocks) * sizeof (int));
block_to_bb = (int *) alloca ((n_basic_blocks) * sizeof (int));
containing_rgn = (int *) alloca ((n_basic_blocks) * 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
{
int_list_ptr *s_preds, *s_succs;
int *num_preds, *num_succs;
sbitmap *dom, *pdom;
s_preds = (int_list_ptr *) alloca (n_basic_blocks
* sizeof (int_list_ptr));
s_succs = (int_list_ptr *) alloca (n_basic_blocks
* sizeof (int_list_ptr));
num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
pdom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
compute_dominators (dom, pdom, s_preds, s_succs);
if (build_control_flow (s_preds, s_succs, num_preds, num_succs) != 0)
find_single_block_region ();
else
find_rgns (s_preds, s_succs, num_preds, num_succs, dom);
if (sched_verbose >= 3)
debug_regions ();
free_bb_mem ();
free (dom);
free (pdom);
}
}
insn_priority = (int *) xmalloc (max_uid * sizeof (int));
insn_reg_weight = (int *) xmalloc (max_uid * sizeof (int));
insn_tick = (int *) xmalloc (max_uid * sizeof (int));
insn_costs = (short *) xmalloc (max_uid * sizeof (short));
insn_units = (short *) xmalloc (max_uid * sizeof (short));
insn_blockage = (unsigned int *) xmalloc (max_uid * sizeof (unsigned int));
insn_ref_count = (int *) xmalloc (max_uid * sizeof (int));
insn_dep_count = (int *) xmalloc (max_uid * sizeof (int));
insn_depend = (rtx *) xmalloc (max_uid * sizeof (rtx));
if (reload_completed == 0)
{
int i;
sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
sched_reg_basic_block = (int *) alloca (max_regno * sizeof (int));
bb_live_regs = ALLOCA_REG_SET ();
bzero ((char *) sched_reg_n_calls_crossed, max_regno * sizeof (int));
bzero ((char *) sched_reg_live_length, max_regno * sizeof (int));
for (i = 0; i < max_regno; i++)
sched_reg_basic_block[i] = REG_BLOCK_UNKNOWN;
}
else
{
sched_reg_n_calls_crossed = 0;
sched_reg_live_length = 0;
bb_live_regs = 0;
}
init_alias_analysis ();
if (write_symbols != NO_DEBUG)
{
rtx line;
line_note = (rtx *) xmalloc (max_uid * sizeof (rtx));
bzero ((char *) line_note, max_uid * sizeof (rtx));
line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
bzero ((char *) line_note_head, n_basic_blocks * sizeof (rtx));
for (b = 0; b < n_basic_blocks; b++)
for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line))
if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
{
line_note_head[b] = line;
break;
}
}
bzero ((char *) insn_priority, max_uid * sizeof (int));
bzero ((char *) insn_reg_weight, max_uid * sizeof (int));
bzero ((char *) insn_tick, max_uid * sizeof (int));
bzero ((char *) insn_costs, max_uid * sizeof (short));
bzero ((char *) insn_units, max_uid * sizeof (short));
bzero ((char *) insn_blockage, max_uid * sizeof (unsigned int));
bzero ((char *) insn_ref_count, max_uid * sizeof (int));
bzero ((char *) insn_depend, max_uid * sizeof (rtx));
bzero ((char *) insn_dep_count, max_uid * sizeof (int));
if (sched_verbose)
init_target_units ();
insn = BLOCK_END (n_basic_blocks - 1);
if (NEXT_INSN (insn) == 0
|| (GET_CODE (insn) != NOTE
&& GET_CODE (insn) != CODE_LABEL
&& !(GET_CODE (insn) == JUMP_INSN
&& GET_CODE (NEXT_INSN (insn)) == BARRIER)))
emit_note_after (NOTE_INSN_DELETED, BLOCK_END (n_basic_blocks - 1));
for (rgn = 0; rgn < nr_regions; rgn++)
{
schedule_region (rgn);
#ifdef USE_C_ALLOCA
alloca (0);
#endif
}
if (reload_completed)
reposition_prologue_and_epilogue_notes (get_insns ());
if (write_symbols != NO_DEBUG)
rm_redundant_line_notes ();
if (reload_completed == 0)
update_reg_usage ();
if (sched_verbose)
{
if (reload_completed == 0 && flag_schedule_interblock)
{
fprintf (dump, "\n;; Procedure interblock/speculative motions == %d/%d \n",
nr_inter, nr_spec);
}
else
{
if (nr_inter > 0)
abort ();
}
fprintf (dump, "\n\n");
}
free (cant_move);
free (fed_by_spec_load);
free (is_load_insn);
free (insn_orig_block);
free (insn_luid);
free (insn_priority);
free (insn_reg_weight);
free (insn_tick);
free (insn_costs);
free (insn_units);
free (insn_blockage);
free (insn_ref_count);
free (insn_dep_count);
free (insn_depend);
if (write_symbols != NO_DEBUG)
free (line_note);
if (bb_live_regs)
FREE_REG_SET (bb_live_regs);
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;
}
}
#endif