#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "toplev.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "regs.h"
#include "function.h"
#include "flags.h"
#include "insn-config.h"
#include "insn-attr.h"
#include "except.h"
#include "toplev.h"
#include "recog.h"
#include "sched-int.h"
#include "target.h"
#ifdef INSN_SCHEDULING
static int issue_rate;
int sched_verbose = 0;
FILE *sched_dump = 0;
static int old_max_uid;
struct haifa_insn_data *h_i_d;
#define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note)
#define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
static rtx *line_note_head;
static rtx note_list;
static rtx *insn_queue;
static int q_ptr = 0;
static int q_size = 0;
#define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
#define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
state_t curr_state;
static size_t dfa_state_size;
static char *ready_try;
struct ready_list
{
rtx *vec;
int veclen;
int first;
int n_ready;
};
static int may_trap_exp (rtx, int);
#define CONST_BASED_ADDRESS_P(x) \
(REG_P (x) \
|| ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
|| (GET_CODE (x) == LO_SUM)) \
&& (CONSTANT_P (XEXP (x, 0)) \
|| CONSTANT_P (XEXP (x, 1)))))
static int
may_trap_exp (rtx x, int is_store)
{
enum rtx_code code;
if (x == 0)
return TRAP_FREE;
code = GET_CODE (x);
if (is_store)
{
if (code == MEM && may_trap_p (x))
return TRAP_RISKY;
else
return TRAP_FREE;
}
if (code == MEM)
{
if (MEM_VOLATILE_P (x))
return IRISKY;
if (!may_trap_p (x))
return IFREE;
if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
return PFREE_CANDIDATE;
return PRISKY_CANDIDATE;
}
else
{
const char *fmt;
int i, insn_class = TRAP_FREE;
if (may_trap_p (x))
return TRAP_RISKY;
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
{
int tmp_class = may_trap_exp (XEXP (x, i), is_store);
insn_class = WORST_CLASS (insn_class, tmp_class);
}
else if (fmt[i] == 'E')
{
int j;
for (j = 0; j < XVECLEN (x, i); j++)
{
int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
insn_class = WORST_CLASS (insn_class, tmp_class);
if (insn_class == TRAP_RISKY || insn_class == IRISKY)
break;
}
}
if (insn_class == TRAP_RISKY || insn_class == IRISKY)
break;
}
return insn_class;
}
}
int
haifa_classify_insn (rtx insn)
{
rtx pat = PATTERN (insn);
int tmp_class = TRAP_FREE;
int insn_class = TRAP_FREE;
enum rtx_code code;
if (GET_CODE (pat) == PARALLEL)
{
int i, len = XVECLEN (pat, 0);
for (i = len - 1; i >= 0; i--)
{
code = GET_CODE (XVECEXP (pat, 0, i));
switch (code)
{
case CLOBBER:
tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
break;
case SET:
tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
if (tmp_class == TRAP_RISKY)
break;
tmp_class
= WORST_CLASS (tmp_class,
may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)),
0));
break;
case COND_EXEC:
case TRAP_IF:
tmp_class = TRAP_RISKY;
break;
default:
;
}
insn_class = WORST_CLASS (insn_class, tmp_class);
if (insn_class == TRAP_RISKY || insn_class == IRISKY)
break;
}
}
else
{
code = GET_CODE (pat);
switch (code)
{
case CLOBBER:
tmp_class = may_trap_exp (XEXP (pat, 0), 1);
break;
case SET:
tmp_class = may_trap_exp (SET_DEST (pat), 1);
if (tmp_class == TRAP_RISKY)
break;
tmp_class =
WORST_CLASS (tmp_class,
may_trap_exp (SET_SRC (pat), 0));
break;
case COND_EXEC:
case TRAP_IF:
tmp_class = TRAP_RISKY;
break;
default:;
}
insn_class = tmp_class;
}
return insn_class;
}
static int priority (rtx);
static int rank_for_schedule (const void *, const void *);
static void swap_sort (rtx *, int);
static void queue_insn (rtx, int);
static int schedule_insn (rtx, struct ready_list *, int);
static int find_set_reg_weight (rtx);
static void find_insn_reg_weight (int);
static void adjust_priority (rtx);
static void advance_one_cycle (void);
static rtx unlink_other_notes (rtx, rtx);
static rtx unlink_line_notes (rtx, rtx);
static rtx reemit_notes (rtx, rtx);
static rtx *ready_lastpos (struct ready_list *);
static void ready_sort (struct ready_list *);
static rtx ready_remove_first (struct ready_list *);
static void queue_to_ready (struct ready_list *);
static int early_queue_to_ready (state_t, struct ready_list *);
static void debug_ready_list (struct ready_list *);
static rtx move_insn1 (rtx, rtx);
static rtx move_insn (rtx, rtx);
static rtx ready_element (struct ready_list *, int);
static rtx ready_remove (struct ready_list *, int);
static int max_issue (struct ready_list *, int *);
static rtx choose_ready (struct ready_list *);
#endif
struct sched_info *current_sched_info;
#ifndef INSN_SCHEDULING
void
schedule_insns (FILE *dump_file ATTRIBUTE_UNUSED)
{
}
#else
static rtx last_scheduled_insn;
HAIFA_INLINE int
insn_cost (rtx insn, rtx link, rtx used)
{
int cost = INSN_COST (insn);
if (cost < 0)
{
if (recog_memoized (insn) < 0)
{
INSN_COST (insn) = 0;
return 0;
}
else
{
cost = insn_default_latency (insn);
if (cost < 0)
cost = 0;
INSN_COST (insn) = cost;
}
}
if (link == 0 || used == 0)
return cost;
if (recog_memoized (used) < 0)
cost = 0;
else
{
if (INSN_CODE (insn) >= 0)
{
if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
cost = 0;
else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
{
cost = (insn_default_latency (insn)
- insn_default_latency (used));
if (cost <= 0)
cost = 1;
}
else if (bypass_p (insn))
cost = insn_latency (insn, used);
}
if (targetm.sched.adjust_cost)
cost = targetm.sched.adjust_cost (used, link, insn, cost);
if (cost < 0)
cost = 0;
}
return cost;
}
static int
priority (rtx insn)
{
rtx link;
if (! INSN_P (insn))
return 0;
if (! INSN_PRIORITY_KNOWN (insn))
{
int this_priority = 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;
next = XEXP (link, 0);
if (! (*current_sched_info->contributes_to_priority) (next, 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;
INSN_PRIORITY_KNOWN (insn) = 1;
}
return INSN_PRIORITY (insn);
}
#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 (const void *x, const void *y)
{
rtx tmp = *(const rtx *) y;
rtx tmp2 = *(const rtx *) x;
rtx link;
int tmp_class, tmp2_class, depend_count1, depend_count2;
int val, priority_val, weight_val, info_val;
if (SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
return SCHED_GROUP_P (tmp2) ? 1 : -1;
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;
info_val = (*current_sched_info->rank) (tmp, tmp2);
if (info_val)
return info_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 (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;
}
HAIFA_INLINE static void
queue_insn (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 (sched_dump, ";;\t\tReady-->Q: insn %s: ",
(*current_sched_info->print_insn) (insn, 0));
fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
}
}
HAIFA_INLINE static rtx *
ready_lastpos (struct ready_list *ready)
{
if (ready->n_ready == 0)
abort ();
return ready->vec + ready->first - ready->n_ready + 1;
}
HAIFA_INLINE void
ready_add (struct ready_list *ready, rtx insn)
{
if (ready->first == ready->n_ready)
{
memmove (ready->vec + ready->veclen - ready->n_ready,
ready_lastpos (ready),
ready->n_ready * sizeof (rtx));
ready->first = ready->veclen - 1;
}
ready->vec[ready->first - ready->n_ready] = insn;
ready->n_ready++;
}
HAIFA_INLINE static rtx
ready_remove_first (struct ready_list *ready)
{
rtx t;
if (ready->n_ready == 0)
abort ();
t = ready->vec[ready->first--];
ready->n_ready--;
if (ready->n_ready == 0)
ready->first = ready->veclen - 1;
return t;
}
HAIFA_INLINE static rtx
ready_element (struct ready_list *ready, int index)
{
#ifdef ENABLE_CHECKING
if (ready->n_ready == 0 || index >= ready->n_ready)
abort ();
#endif
return ready->vec[ready->first - index];
}
HAIFA_INLINE static rtx
ready_remove (struct ready_list *ready, int index)
{
rtx t;
int i;
if (index == 0)
return ready_remove_first (ready);
if (ready->n_ready == 0 || index >= ready->n_ready)
abort ();
t = ready->vec[ready->first - index];
ready->n_ready--;
for (i = index; i < ready->n_ready; i++)
ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
return t;
}
HAIFA_INLINE static void
ready_sort (struct ready_list *ready)
{
rtx *first = ready_lastpos (ready);
SCHED_SORT (first, ready->n_ready);
}
HAIFA_INLINE static void
adjust_priority (rtx prev)
{
if (targetm.sched.adjust_priority)
INSN_PRIORITY (prev) =
targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
}
HAIFA_INLINE static void
advance_one_cycle (void)
{
if (targetm.sched.dfa_pre_cycle_insn)
state_transition (curr_state,
targetm.sched.dfa_pre_cycle_insn ());
state_transition (curr_state, NULL);
if (targetm.sched.dfa_post_cycle_insn)
state_transition (curr_state,
targetm.sched.dfa_post_cycle_insn ());
}
static int last_clock_var;
static int
schedule_insn (rtx insn, struct ready_list *ready, int clock)
{
rtx link;
int advance = 0;
int premature_issue = 0;
if (sched_verbose >= 1)
{
char buf[2048];
print_insn (buf, insn, 0);
buf[40] = 0;
fprintf (sched_dump, ";;\t%3i--> %-40s:", clock, buf);
if (recog_memoized (insn) < 0)
fprintf (sched_dump, "nothing");
else
print_reservation (sched_dump, insn);
fputc ('\n', sched_dump);
}
if (INSN_TICK (insn) > clock)
{
premature_issue = INSN_TICK (insn) - clock;
}
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 + premature_issue);
if ((INSN_DEP_COUNT (next) -= 1) == 0)
{
int effective_cost = INSN_TICK (next) - clock;
if (! (*current_sched_info->new_ready) (next))
continue;
if (sched_verbose >= 2)
{
fprintf (sched_dump, ";;\t\tdependences resolved: insn %s ",
(*current_sched_info->print_insn) (next, 0));
if (effective_cost < 1)
fprintf (sched_dump, "into ready\n");
else
fprintf (sched_dump, "into queue with cost=%d\n",
effective_cost);
}
adjust_priority (next);
if (effective_cost < 1)
ready_add (ready, next);
else
{
queue_insn (next, effective_cost);
if (SCHED_GROUP_P (next) && advance < effective_cost)
advance = effective_cost;
}
}
}
if (issue_rate > 1
&& GET_CODE (PATTERN (insn)) != USE
&& GET_CODE (PATTERN (insn)) != CLOBBER)
{
if (reload_completed)
PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
last_clock_var = clock;
}
return advance;
}
static rtx
unlink_other_notes (rtx insn, rtx tail)
{
rtx prev = PREV_INSN (insn);
while (insn != tail && NOTE_P (insn))
{
rtx next = NEXT_INSN (insn);
if (prev)
NEXT_INSN (prev) = next;
if (next)
PREV_INSN (next) = prev;
if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
&& 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 (rtx insn, rtx tail)
{
rtx prev = PREV_INSN (insn);
while (insn != tail && NOTE_P (insn))
{
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;
}
void
get_block_head_tail (int b, rtx *headp, rtx *tailp)
{
rtx head = BB_HEAD (BASIC_BLOCK (b));
rtx tail = BB_END (BASIC_BLOCK (b));
while (head != tail)
{
if (NOTE_P (head))
head = NEXT_INSN (head);
else if (NOTE_P (tail))
tail = PREV_INSN (tail);
else if (LABEL_P (head))
head = NEXT_INSN (head);
else
break;
}
*headp = head;
*tailp = tail;
}
int
no_real_insns_p (rtx head, rtx tail)
{
while (head != NEXT_INSN (tail))
{
if (!NOTE_P (head) && !LABEL_P (head))
return 0;
head = NEXT_INSN (head);
}
return 1;
}
void
rm_line_notes (rtx head, rtx tail)
{
rtx next_tail;
rtx insn;
next_tail = NEXT_INSN (tail);
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
{
rtx prev;
if (NOTE_P (insn))
{
prev = insn;
insn = unlink_line_notes (insn, next_tail);
if (prev == tail)
abort ();
if (prev == head)
abort ();
if (insn == next_tail)
abort ();
}
}
}
void
save_line_notes (int b, rtx head, rtx tail)
{
rtx next_tail;
rtx line = line_note_head[b];
rtx insn;
next_tail = NEXT_INSN (tail);
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0)
line = insn;
else
LINE_NOTE (insn) = line;
}
void
restore_line_notes (rtx head, rtx tail)
{
rtx line, note, prev, new;
int added_notes = 0;
rtx next_tail, insn;
head = head;
next_tail = NEXT_INSN (tail);
for (line = head; line; line = PREV_INSN (line))
if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
break;
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0)
line = insn;
else if (!NOTE_P (insn)
&& INSN_UID (insn) < old_max_uid
&& (note = LINE_NOTE (insn)) != 0
&& note != line
&& (line == 0
#ifdef USE_MAPPED_LOCATION
|| NOTE_SOURCE_LOCATION (note) != NOTE_SOURCE_LOCATION (line)
#else
|| NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
|| NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)
#endif
))
{
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);
#ifndef USE_MAPPED_LOCATION
NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
#endif
}
}
if (sched_verbose && added_notes)
fprintf (sched_dump, ";; added %d line-number notes\n", added_notes);
}
void
rm_redundant_line_notes (void)
{
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 (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0)
{
if (active_insn == 0)
{
notes++;
SET_INSN_DELETED (insn);
}
else if (line
#ifdef USE_MAPPED_LOCATION
&& NOTE_SOURCE_LOCATION (line) == NOTE_SOURCE_LOCATION (insn)
#else
&& NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
&& NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn)
#endif
)
{
notes++;
SET_INSN_DELETED (line);
line = insn;
}
else
line = insn;
active_insn = 0;
}
else if (!((NOTE_P (insn)
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
|| (NONJUMP_INSN_P (insn)
&& (GET_CODE (PATTERN (insn)) == USE
|| GET_CODE (PATTERN (insn)) == CLOBBER))))
active_insn++;
if (sched_verbose && notes)
fprintf (sched_dump, ";; deleted %d line-number notes\n", notes);
}
void
rm_other_notes (rtx head, rtx tail)
{
rtx next_tail;
rtx insn;
note_list = 0;
if (head == tail && (! INSN_P (head)))
return;
next_tail = NEXT_INSN (tail);
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
{
rtx prev;
if (NOTE_P (insn))
{
prev = insn;
insn = unlink_other_notes (insn, next_tail);
if (prev == tail)
abort ();
if (prev == head)
abort ();
if (insn == next_tail)
abort ();
}
}
}
static int
find_set_reg_weight (rtx x)
{
if (GET_CODE (x) == CLOBBER
&& register_operand (SET_DEST (x), VOIDmode))
return 1;
if (GET_CODE (x) == SET
&& register_operand (SET_DEST (x), VOIDmode))
{
if (REG_P (SET_DEST (x)))
{
if (!reg_mentioned_p (SET_DEST (x), SET_SRC (x)))
return 1;
else
return 0;
}
return 1;
}
return 0;
}
static void
find_insn_reg_weight (int b)
{
rtx insn, next_tail, head, tail;
get_block_head_tail (b, &head, &tail);
next_tail = NEXT_INSN (tail);
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
{
int reg_weight = 0;
rtx x;
if (! INSN_P (insn))
continue;
x = PATTERN (insn);
reg_weight += find_set_reg_weight (x);
if (GET_CODE (x) == PARALLEL)
{
int j;
for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
{
x = XVECEXP (PATTERN (insn), 0, j);
reg_weight += find_set_reg_weight (x);
}
}
for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
{
if (REG_NOTE_KIND (x) == REG_DEAD
|| REG_NOTE_KIND (x) == REG_UNUSED)
reg_weight--;
}
INSN_REG_WEIGHT (insn) = reg_weight;
}
}
static int clock_var;
static void
queue_to_ready (struct ready_list *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 (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
(*current_sched_info->print_insn) (insn, 0));
ready_add (ready, insn);
if (sched_verbose >= 2)
fprintf (sched_dump, "moving to ready without stalls\n");
}
insn_queue[q_ptr] = 0;
if (ready->n_ready == 0)
{
int stalls;
for (stalls = 1; stalls <= max_insn_queue_index; 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 (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
(*current_sched_info->print_insn) (insn, 0));
ready_add (ready, insn);
if (sched_verbose >= 2)
fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
}
insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
advance_one_cycle ();
break;
}
advance_one_cycle ();
}
q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
clock_var += stalls;
}
}
static bool
ok_for_early_queue_removal (rtx insn)
{
int n_cycles;
rtx prev_insn = last_scheduled_insn;
if (targetm.sched.is_costly_dependence)
{
for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
{
for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn))
{
rtx dep_link = 0;
int dep_cost;
if (!NOTE_P (prev_insn))
{
dep_link = find_insn_list (insn, INSN_DEPEND (prev_insn));
if (dep_link)
{
dep_cost = insn_cost (prev_insn, dep_link, insn) ;
if (targetm.sched.is_costly_dependence (prev_insn, insn,
dep_link, dep_cost,
flag_sched_stalled_insns_dep - n_cycles))
return false;
}
}
if (GET_MODE (prev_insn) == TImode)
break;
}
if (!prev_insn)
break;
prev_insn = PREV_INSN (prev_insn);
}
}
return true;
}
static int
early_queue_to_ready (state_t state, struct ready_list *ready)
{
rtx insn;
rtx link;
rtx next_link;
rtx prev_link;
bool move_to_ready;
int cost;
state_t temp_state = alloca (dfa_state_size);
int stalls;
int insns_removed = 0;
if (! flag_sched_stalled_insns)
return 0;
for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
{
if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
{
if (sched_verbose > 6)
fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
prev_link = 0;
while (link)
{
next_link = XEXP (link, 1);
insn = XEXP (link, 0);
if (insn && sched_verbose > 6)
print_rtl_single (sched_dump, insn);
memcpy (temp_state, state, dfa_state_size);
if (recog_memoized (insn) < 0)
cost = 0;
else
cost = state_transition (temp_state, insn);
if (sched_verbose >= 6)
fprintf (sched_dump, "transition cost = %d\n", cost);
move_to_ready = false;
if (cost < 0)
{
move_to_ready = ok_for_early_queue_removal (insn);
if (move_to_ready == true)
{
q_size -= 1;
ready_add (ready, insn);
if (prev_link)
XEXP (prev_link, 1) = next_link;
else
insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
free_INSN_LIST_node (link);
if (sched_verbose >= 2)
fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
(*current_sched_info->print_insn) (insn, 0));
insns_removed++;
if (insns_removed == flag_sched_stalled_insns)
return insns_removed;
}
}
if (move_to_ready == false)
prev_link = link;
link = next_link;
}
}
}
return insns_removed;
}
static void
debug_ready_list (struct ready_list *ready)
{
rtx *p;
int i;
if (ready->n_ready == 0)
{
fprintf (sched_dump, "\n");
return;
}
p = ready_lastpos (ready);
for (i = 0; i < ready->n_ready; i++)
fprintf (sched_dump, " %s", (*current_sched_info->print_insn) (p[i], 0));
fprintf (sched_dump, "\n");
}
static rtx
move_insn1 (rtx insn, rtx 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 (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_SAVE_NOTE)
{
enum insn_note note_type = INTVAL (XEXP (note, 0));
last = emit_note_before (note_type, last);
remove_note (insn, note);
}
}
return retval;
}
static rtx
move_insn (rtx insn, rtx last)
{
rtx retval = NULL;
move_insn1 (insn, last);
if (retval == NULL_RTX)
retval = reemit_notes (insn, insn);
else
reemit_notes (insn, insn);
SCHED_GROUP_P (insn) = 0;
return retval;
}
struct choice_entry
{
int index;
int rest;
int n;
state_t state;
};
static struct choice_entry *choice_stack;
static int cycle_issued_insns;
static int max_lookahead_tries;
static int cached_first_cycle_multipass_dfa_lookahead = 0;
static int cached_issue_rate = 0;
static int
max_issue (struct ready_list *ready, int *index)
{
int n, i, all, n_ready, best, delay, tries_num;
struct choice_entry *top;
rtx insn;
best = 0;
memcpy (choice_stack->state, curr_state, dfa_state_size);
top = choice_stack;
top->rest = cached_first_cycle_multipass_dfa_lookahead;
top->n = 0;
n_ready = ready->n_ready;
for (all = i = 0; i < n_ready; i++)
if (!ready_try [i])
all++;
i = 0;
tries_num = 0;
for (;;)
{
if (top->rest == 0 || i >= n_ready)
{
if (top == choice_stack)
break;
if (best < top - choice_stack && ready_try [0])
{
best = top - choice_stack;
*index = choice_stack [1].index;
if (top->n == issue_rate - cycle_issued_insns || best == all)
break;
}
i = top->index;
ready_try [i] = 0;
top--;
memcpy (curr_state, top->state, dfa_state_size);
}
else if (!ready_try [i])
{
tries_num++;
if (tries_num > max_lookahead_tries)
break;
insn = ready_element (ready, i);
delay = state_transition (curr_state, insn);
if (delay < 0)
{
if (state_dead_lock_p (curr_state))
top->rest = 0;
else
top->rest--;
n = top->n;
if (memcmp (top->state, curr_state, dfa_state_size) != 0)
n++;
top++;
top->rest = cached_first_cycle_multipass_dfa_lookahead;
top->index = i;
top->n = n;
memcpy (top->state, curr_state, dfa_state_size);
ready_try [i] = 1;
i = -1;
}
}
i++;
}
while (top != choice_stack)
{
ready_try [top->index] = 0;
top--;
}
memcpy (curr_state, choice_stack->state, dfa_state_size);
return best;
}
static rtx
choose_ready (struct ready_list *ready)
{
int lookahead = 0;
if (targetm.sched.first_cycle_multipass_dfa_lookahead)
lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0)))
return ready_remove_first (ready);
else
{
int index = 0, i;
rtx insn;
if (cached_first_cycle_multipass_dfa_lookahead != lookahead)
{
cached_first_cycle_multipass_dfa_lookahead = lookahead;
max_lookahead_tries = 100;
for (i = 0; i < issue_rate; i++)
max_lookahead_tries *= lookahead;
}
insn = ready_element (ready, 0);
if (INSN_CODE (insn) < 0)
return ready_remove_first (ready);
for (i = 1; i < ready->n_ready; i++)
{
insn = ready_element (ready, i);
ready_try [i]
= (INSN_CODE (insn) < 0
|| (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
&& !targetm.sched.first_cycle_multipass_dfa_lookahead_guard (insn)));
}
if (max_issue (ready, &index) == 0)
return ready_remove_first (ready);
else
return ready_remove (ready, index);
}
}
void
schedule_block (int b, int rgn_n_insns)
{
struct ready_list ready;
int i, first_cycle_insn_p;
int can_issue_more;
state_t temp_state = NULL;
int sort_p, advance, start_clock_var;
rtx prev_head = current_sched_info->prev_head;
rtx next_tail = current_sched_info->next_tail;
rtx head = NEXT_INSN (prev_head);
rtx tail = PREV_INSN (next_tail);
if (head == tail && (! INSN_P (head)))
abort ();
if (sched_verbose)
{
fprintf (sched_dump, ";; ======================================================\n");
fprintf (sched_dump,
";; -- basic block %d from %d to %d -- %s reload\n",
b, INSN_UID (head), INSN_UID (tail),
(reload_completed ? "after" : "before"));
fprintf (sched_dump, ";; ======================================================\n");
fprintf (sched_dump, "\n");
}
state_reset (curr_state);
ready.veclen = rgn_n_insns + 1 + issue_rate;
ready.first = ready.veclen - 1;
ready.vec = xmalloc (ready.veclen * sizeof (rtx));
ready.n_ready = 0;
temp_state = alloca (dfa_state_size);
ready_try = xcalloc ((rgn_n_insns + 1), sizeof (char));
choice_stack = xmalloc ((rgn_n_insns + 1)
* sizeof (struct choice_entry));
for (i = 0; i <= rgn_n_insns; i++)
choice_stack[i].state = xmalloc (dfa_state_size);
(*current_sched_info->init_ready_list) (&ready);
if (targetm.sched.md_init)
targetm.sched.md_init (sched_dump, sched_verbose, ready.veclen);
last_scheduled_insn = prev_head;
q_ptr = 0;
q_size = 0;
insn_queue = alloca ((max_insn_queue_index + 1) * sizeof (rtx));
memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
last_clock_var = -1;
clock_var = -1;
advance = 0;
sort_p = TRUE;
while ((*current_sched_info->schedule_more_p) ())
{
do
{
start_clock_var = clock_var;
clock_var++;
advance_one_cycle ();
queue_to_ready (&ready);
if (ready.n_ready == 0)
abort ();
if (sched_verbose >= 2)
{
fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
debug_ready_list (&ready);
}
advance -= clock_var - start_clock_var;
}
while (advance > 0);
if (sort_p)
{
ready_sort (&ready);
if (sched_verbose >= 2)
{
fprintf (sched_dump, ";;\t\tReady list after ready_sort: ");
debug_ready_list (&ready);
}
}
if (sort_p && targetm.sched.reorder
&& (ready.n_ready == 0
|| !SCHED_GROUP_P (ready_element (&ready, 0))))
can_issue_more =
targetm.sched.reorder (sched_dump, sched_verbose,
ready_lastpos (&ready),
&ready.n_ready, clock_var);
else
can_issue_more = issue_rate;
first_cycle_insn_p = 1;
cycle_issued_insns = 0;
for (;;)
{
rtx insn;
int cost;
bool asm_p = false;
if (sched_verbose >= 2)
{
fprintf (sched_dump, ";;\tReady list (t =%3d): ",
clock_var);
debug_ready_list (&ready);
}
if (ready.n_ready == 0
&& can_issue_more
&& reload_completed)
{
if (sched_verbose >= 6)
fprintf(sched_dump,";;\t\tSecond chance\n");
memcpy (temp_state, curr_state, dfa_state_size);
if (early_queue_to_ready (temp_state, &ready))
ready_sort (&ready);
}
if (ready.n_ready == 0 || !can_issue_more
|| state_dead_lock_p (curr_state)
|| !(*current_sched_info->schedule_more_p) ())
break;
if (sort_p)
insn = choose_ready (&ready);
else
insn = ready_remove_first (&ready);
if (targetm.sched.dfa_new_cycle
&& targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
insn, last_clock_var,
clock_var, &sort_p))
{
ready_add (&ready, insn);
break;
}
sort_p = TRUE;
memcpy (temp_state, curr_state, dfa_state_size);
if (recog_memoized (insn) < 0)
{
asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
|| asm_noperands (PATTERN (insn)) >= 0);
if (!first_cycle_insn_p && asm_p)
cost = 1;
else
cost = 0;
}
else
{
cost = state_transition (temp_state, insn);
if (cost < 0)
cost = 0;
else if (cost == 0)
cost = 1;
}
if (cost >= 1)
{
queue_insn (insn, cost);
if (SCHED_GROUP_P (insn))
{
advance = cost;
break;
}
continue;
}
if (! (*current_sched_info->can_schedule_ready_p) (insn))
goto next;
last_scheduled_insn = move_insn (insn, last_scheduled_insn);
if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
cycle_issued_insns++;
memcpy (curr_state, temp_state, dfa_state_size);
if (targetm.sched.variable_issue)
can_issue_more =
targetm.sched.variable_issue (sched_dump, sched_verbose,
insn, can_issue_more);
else if (GET_CODE (PATTERN (insn)) != USE
&& GET_CODE (PATTERN (insn)) != CLOBBER)
can_issue_more--;
advance = schedule_insn (insn, &ready, clock_var);
if (advance == 0 && asm_p)
advance = 1;
if (advance != 0)
break;
next:
first_cycle_insn_p = 0;
if (ready.n_ready > 0)
ready_sort (&ready);
if (targetm.sched.reorder2
&& (ready.n_ready == 0
|| !SCHED_GROUP_P (ready_element (&ready, 0))))
{
can_issue_more =
targetm.sched.reorder2 (sched_dump, sched_verbose,
ready.n_ready
? ready_lastpos (&ready) : NULL,
&ready.n_ready, clock_var);
}
}
}
if (targetm.sched.md_finish)
targetm.sched.md_finish (sched_dump, sched_verbose);
if (sched_verbose)
{
fprintf (sched_dump, ";;\tReady list (final): ");
debug_ready_list (&ready);
}
if (current_sched_info->queue_must_finish_empty && q_size != 0)
abort ();
head = NEXT_INSN (prev_head);
tail = last_scheduled_insn;
if (!reload_completed)
{
rtx insn, link, next;
for (insn = head; insn != tail; insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
{
next = XEXP (link, 0);
INSN_TICK (next) -= clock_var;
}
}
}
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 (sched_verbose)
{
fprintf (sched_dump, ";; total time = %d\n;; new head = %d\n",
clock_var, INSN_UID (head));
fprintf (sched_dump, ";; new tail = %d\n\n",
INSN_UID (tail));
}
current_sched_info->head = head;
current_sched_info->tail = tail;
free (ready.vec);
free (ready_try);
for (i = 0; i <= rgn_n_insns; i++)
free (choice_stack [i].state);
free (choice_stack);
}
int
set_priorities (rtx head, rtx tail)
{
rtx insn;
int n_insn;
int sched_max_insns_priority =
current_sched_info->sched_max_insns_priority;
rtx prev_head;
prev_head = PREV_INSN (head);
if (head == tail && (! INSN_P (head)))
return 0;
n_insn = 0;
sched_max_insns_priority = 0;
for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
{
if (NOTE_P (insn))
continue;
n_insn++;
(void) priority (insn);
if (INSN_PRIORITY_KNOWN (insn))
sched_max_insns_priority =
MAX (sched_max_insns_priority, INSN_PRIORITY (insn));
}
sched_max_insns_priority += 1;
current_sched_info->sched_max_insns_priority =
sched_max_insns_priority;
return n_insn;
}
void
sched_init (FILE *dump_file)
{
int luid;
basic_block b;
rtx insn;
int i;
#ifdef HAVE_cc0
flag_schedule_speculative_load = 0;
#endif
sched_verbose = sched_verbose_param;
if (sched_verbose_param == 0 && dump_file)
sched_verbose = 1;
sched_dump = ((sched_verbose_param >= 10 || !dump_file)
? stderr : dump_file);
if (targetm.sched.issue_rate)
issue_rate = targetm.sched.issue_rate ();
else
issue_rate = 1;
if (cached_issue_rate != issue_rate)
{
cached_issue_rate = issue_rate;
cached_first_cycle_multipass_dfa_lookahead = 0;
}
old_max_uid = get_max_uid () + 1;
h_i_d = xcalloc (old_max_uid, sizeof (*h_i_d));
for (i = 0; i < old_max_uid; i++)
h_i_d [i].cost = -1;
if (targetm.sched.init_dfa_pre_cycle_insn)
targetm.sched.init_dfa_pre_cycle_insn ();
if (targetm.sched.init_dfa_post_cycle_insn)
targetm.sched.init_dfa_post_cycle_insn ();
dfa_start ();
dfa_state_size = state_size ();
curr_state = xmalloc (dfa_state_size);
h_i_d[0].luid = 0;
luid = 1;
FOR_EACH_BB (b)
for (insn = BB_HEAD (b); ; insn = NEXT_INSN (insn))
{
INSN_LUID (insn) = luid;
if (!NOTE_P (insn))
++luid;
if (insn == BB_END (b))
break;
}
init_dependency_caches (luid);
init_alias_analysis ();
if (write_symbols != NO_DEBUG)
{
rtx line;
line_note_head = xcalloc (last_basic_block, sizeof (rtx));
FOR_EACH_BB (b)
{
for (line = BB_HEAD (b); line; line = PREV_INSN (line))
if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
{
line_note_head[b->index] = line;
break;
}
for (line = BB_HEAD (b); line; line = NEXT_INSN (line))
{
if (INSN_P (line))
break;
if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
line_note_head[b->index] = line;
}
}
}
insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
if (NEXT_INSN (insn) == 0
|| (!NOTE_P (insn)
&& !LABEL_P (insn)
&& !BARRIER_P (NEXT_INSN (insn))))
{
emit_note_after (NOTE_INSN_DELETED, BB_END (EXIT_BLOCK_PTR->prev_bb));
BB_END (EXIT_BLOCK_PTR->prev_bb) = PREV_INSN (BB_END (EXIT_BLOCK_PTR->prev_bb));
}
FOR_EACH_BB_REVERSE (b)
find_insn_reg_weight (b->index);
if (targetm.sched.md_init_global)
targetm.sched.md_init_global (sched_dump, sched_verbose, old_max_uid);
}
void
sched_finish (void)
{
free (h_i_d);
free (curr_state);
dfa_finish ();
free_dependency_caches ();
end_alias_analysis ();
if (write_symbols != NO_DEBUG)
free (line_note_head);
if (targetm.sched.md_finish_global)
targetm.sched.md_finish_global (sched_dump, sched_verbose);
}
#endif