This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Patch: Support IA-64 speculation [4/5]
- From: Maxim Kuvyrkov <mkuvyrkov at ispras dot ru>
- To: "Vladimir N. Makarov" <vmakarov at redhat dot com>
- Cc: gcc-patches at gcc dot gnu dot org, Andrey Belevantsev <abel at ispras dot ru>
- Date: Wed, 15 Mar 2006 22:40:19 -0500
- Subject: Re: Patch: Support IA-64 speculation [4/5]
- References: <43AC335D.1080201@ispras.ru> <43FF1398.9010007@redhat.com>
Vladimir N. Makarov wrote:
Maxim Kuvyrkov wrote:
Hi,
This patch fixes computation of instruction INSN_TICK - the minimum
clock time, when instruction can be scheduled.
...
The patch was bootstrapped and regtested on the 20051125 weekly
snapshot on ia64-linux and i686-linux.
Ok for mainline?
This patch is ok. I have just few minor comments which you should
fix. Please, wait for subsequent patches review before committing
this and the previous patch into the mainline.
Thanks for fixing some comments and removing redundant code besides
implementing the speculation.
There was no other way :)
This is the latest version of patch. Currently the tests on i386 and
ia64 are still running and if they'll be ok, I'll commit this patch.
--
Maxim
2006-03-15 Maxim Kuvyrkov <mkuvyrkov@ispras.ru>
* sched-int.h (struct haifa_insn_data): New fields: resolved_deps,
inter_tick, queue_index.
(struct sched_info): Change signature of init_ready_list field.
Adjust all initializations.
(RESOLVED_DEPS): New access macro.
(ready_add): Remove prototype.
(try_ready): Add prototype.
* sched-rgn.c (init_ready_list): Use try_ready.
(schedule_region): Initialize
current_sched_info->{sched_max_insns_priority, queue_must_finish_empty}.
* sched-ebb.c (new_ready): Remove. Adjust ebb_sched_info.
(init_ready_list): Use try_ready.
(schedule_ebb): Initialize current_sched_info->sched_max_insns_priority.
* lists.c (remove_list_elem): Remove `static'.
(remove_free_INSN_LIST_elem): New function.
* rtl.h (remove_list_elem, remove_free_INSN_LIST_elem): Add prototypes.
* haifa-sched.c (INTER_TICK, QUEUE_INDEX): New macros.
(INVALID_TICK, MIN_TICK, QUEUE_SCHEDULED, QUEUE_NOWHERE, QUEUE_READY):
New constants.
(readyp): New variable.
(queue_remove, ready_remove_insn, fix_inter_tick, fix_tick_ready,
change_queue_index, resolve_dep): New static functions.
(try_ready): New function. Adjust callers in sched-rgn.c and
sched-ebb.c to use it instead of ready_add.
(clock_var): Move at the begining of file.
(rank_for_schedule): Fix typo.
(queue_insn): Add assertion. Handle QUEUE_INDEX.
(ready_lastpos): Enforce assertion.
(ready_add): Make it static. Handle QUEUE_INDEX. Add new argument,
update all callers.
(ready_remove_first, ready_remove): Handle QUEUE_INDEX.
(schedule_insn): Rewrite to use try_ready and resolve_dep.
(queue_to_ready): Use free_INSN_LIST_list.
(early_queue_to_ready): Fix typo.
(schedule_block): Init readyp. Move init_ready_list call after the
initialization of clock_var. Fix error in rejecting insn by
targetm.sched.dfa_new_cycle. Add call to fix_inter_tick. Remove code
that previously corrected INSN_TICKs. Add code for handling
QUEUE_INDEX.
(set_priorities): Fix typo.
(sched_init): Initialize INSN_TICK, INTER_TICK and QUEUE_INDEX.
Clarify comment and code that keeps current_sched_info->next_tail
non-null.
--- sched-ebb.c (/fortuna/regions/gcc) (revision 133)
+++ sched-ebb.c (/fortuna/insn-tick/gcc) (revision 133)
@@ -49,9 +49,8 @@ static int target_n_insns;
static int sched_n_insns;
/* Implementations of the sched_info functions for region scheduling. */
-static void init_ready_list (struct ready_list *);
+static void init_ready_list (void);
static int can_schedule_ready_p (rtx);
-static int new_ready (rtx);
static int schedule_more_p (void);
static const char *ebb_print_insn (rtx, int);
static int rank (rtx, rtx);
@@ -76,7 +75,7 @@ schedule_more_p (void)
once before scheduling a set of insns. */
static void
-init_ready_list (struct ready_list *ready)
+init_ready_list (void)
{
rtx prev_head = current_sched_info->prev_head;
rtx next_tail = current_sched_info->next_tail;
@@ -95,8 +94,7 @@ init_ready_list (struct ready_list *read
Count number of insns in the target block being scheduled. */
for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
{
- if (INSN_DEP_COUNT (insn) == 0)
- ready_add (ready, insn);
+ try_ready (insn);
target_n_insns++;
}
}
@@ -111,15 +109,6 @@ can_schedule_ready_p (rtx insn ATTRIBUTE
return 1;
}
-/* Called after INSN has all its dependencies resolved. Return nonzero
- if it should be moved to the ready list or the queue, or zero if we
- should silently discard it. */
-static int
-new_ready (rtx next ATTRIBUTE_UNUSED)
-{
- return 1;
-}
-
/* Return a string that contains the insn uid and optionally anything else
necessary to identify this insn in an output. It's valid to use a
static buffer for this. The ALIGNED parameter should cause the string
@@ -197,7 +186,7 @@ static struct sched_info ebb_sched_info
init_ready_list,
can_schedule_ready_p,
schedule_more_p,
- new_ready,
+ NULL,
rank,
ebb_print_insn,
contributes_to_priority,
@@ -524,7 +513,9 @@ schedule_ebb (rtx head, rtx tail)
targetm.sched.dependencies_evaluation_hook (head, tail);
/* Set priorities. */
+ current_sched_info->sched_max_insns_priority = 0;
n_insns = set_priorities (head, tail);
+ current_sched_info->sched_max_insns_priority++;
current_sched_info->prev_head = PREV_INSN (head);
current_sched_info->next_tail = NEXT_INSN (tail);
--- lists.c (/fortuna/regions/gcc) (revision 133)
+++ lists.c (/fortuna/insn-tick/gcc) (revision 133)
@@ -98,7 +98,7 @@ remove_list_node (rtx *listp)
/* Removes corresponding to ELEM node from the list pointed to by LISTP.
Returns that node. */
-static rtx
+rtx
remove_list_elem (rtx elem, rtx *listp)
{
rtx node;
@@ -241,4 +241,12 @@ remove_free_DEPS_LIST_elem (rtx elem, rt
free_DEPS_LIST_node (remove_list_elem (elem, listp));
}
+/* Remove and free corresponding to ELEM node in the INSN_LIST pointed to
+ by LISTP. */
+void
+remove_free_INSN_LIST_elem (rtx elem, rtx *listp)
+{
+ free_INSN_LIST_node (remove_list_elem (elem, listp));
+}
+
#include "gt-lists.h"
--- haifa-sched.c (/fortuna/regions/gcc) (revision 133)
+++ haifa-sched.c (/fortuna/insn-tick/gcc) (revision 133)
@@ -187,6 +187,13 @@ 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)
+#define INTER_TICK(INSN) (h_i_d[INSN_UID (INSN)].inter_tick)
+
+/* If INSN_TICK of an instruction is equal to INVALID_TICK,
+ then it should be recalculated from scratch. */
+#define INVALID_TICK (-(max_insn_queue_index + 1))
+/* The minimal value of the INSN_TICK of an instruction. */
+#define MIN_TICK (-max_insn_queue_index)
/* Vector indexed by basic block number giving the starting line-number
for each basic block. */
@@ -236,7 +243,7 @@ static rtx note_list;
/* Implement a circular buffer to delay instructions until sufficient
time has passed. For the new pipeline description interface,
- MAX_INSN_QUEUE_INDEX is a power of two minus one which is larger
+ MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
than maximal time of instruction execution computed by genattr.c on
the base maximal time of functional unit reservations and getting a
result. This is the longest time an insn may be queued. */
@@ -247,6 +254,17 @@ 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)
+#define QUEUE_SCHEDULED (-3)
+#define QUEUE_NOWHERE (-2)
+#define QUEUE_READY (-1)
+/* QUEUE_SCHEDULED - INSN is scheduled.
+ QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
+ queue or ready list.
+ QUEUE_READY - INSN is in ready list.
+ N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
+
+#define QUEUE_INDEX(INSN) (h_i_d[INSN_UID (INSN)].queue_index)
+
/* The following variable value refers for all current and future
reservations of the processor units. */
state_t curr_state;
@@ -275,6 +293,12 @@ struct ready_list
int n_ready;
};
+/* The pointer to the ready list. */
+static struct ready_list *readyp;
+
+/* Scheduling clock. */
+static int clock_var;
+
static int may_trap_exp (rtx, int);
/* Nonzero iff the address is comprised from at most 1 register. */
@@ -442,7 +466,7 @@ 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 schedule_insn (rtx);
static int find_set_reg_weight (rtx);
static void find_insn_reg_weight (int);
static void adjust_priority (rtx);
@@ -476,6 +500,7 @@ static rtx unlink_line_notes (rtx, rtx);
static rtx reemit_notes (rtx, rtx);
static rtx *ready_lastpos (struct ready_list *);
+static void ready_add (struct ready_list *, rtx, bool);
static void ready_sort (struct ready_list *);
static rtx ready_remove_first (struct ready_list *);
@@ -491,10 +516,16 @@ static rtx move_insn (rtx, rtx);
on the first cycle. */
static rtx ready_element (struct ready_list *, int);
static rtx ready_remove (struct ready_list *, int);
+static void ready_remove_insn (rtx);
static int max_issue (struct ready_list *, int *);
static rtx choose_ready (struct ready_list *);
+static void fix_inter_tick (rtx, rtx);
+static int fix_tick_ready (rtx);
+static void change_queue_index (rtx, int);
+static void resolve_dep (rtx, rtx);
+
#endif /* INSN_SCHEDULING */
/* Point to state used for the current scheduling pass. */
@@ -663,7 +694,7 @@ rank_for_schedule (const void *x, const
return info_val;
/* Compare insns based on their relation to the last-scheduled-insn. */
- if (last_scheduled_insn)
+ if (INSN_P (last_scheduled_insn))
{
/* Classify the instructions into three classes:
1) Data dependent on last schedule insn.
@@ -736,6 +767,9 @@ 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]);
+
+ gcc_assert (n_cycles <= max_insn_queue_index);
+
insn_queue[next_q] = link;
q_size += 1;
@@ -746,6 +780,18 @@ queue_insn (rtx insn, int n_cycles)
fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
}
+
+ QUEUE_INDEX (insn) = next_q;
+}
+
+/* Remove INSN from queue. */
+static void
+queue_remove (rtx insn)
+{
+ gcc_assert (QUEUE_INDEX (insn) >= 0);
+ remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
+ q_size--;
+ QUEUE_INDEX (insn) = QUEUE_NOWHERE;
}
/* Return a pointer to the bottom of the ready list, i.e. the insn
@@ -754,25 +800,45 @@ queue_insn (rtx insn, int n_cycles)
HAIFA_INLINE static rtx *
ready_lastpos (struct ready_list *ready)
{
- gcc_assert (ready->n_ready);
+ gcc_assert (ready->n_ready >= 1);
return ready->vec + ready->first - ready->n_ready + 1;
}
-/* Add an element INSN to the ready list so that it ends up with the lowest
- priority. */
+/* Add an element INSN to the ready list so that it ends up with the
+ lowest/highest priority dependending on FIRST_P. */
-HAIFA_INLINE void
-ready_add (struct ready_list *ready, rtx insn)
+HAIFA_INLINE static void
+ready_add (struct ready_list *ready, rtx insn, bool first_p)
{
- if (ready->first == ready->n_ready)
+ if (!first_p)
{
- memmove (ready->vec + ready->veclen - ready->n_ready,
- ready_lastpos (ready),
- ready->n_ready * sizeof (rtx));
- ready->first = ready->veclen - 1;
+ 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->vec[ready->first - ready->n_ready] = insn;
+ else
+ {
+ if (ready->first == ready->veclen - 1)
+ {
+ if (ready->n_ready)
+ /* ready_lastpos() fails when called with (ready->n_ready == 0). */
+ memmove (ready->vec + ready->veclen - ready->n_ready - 1,
+ ready_lastpos (ready),
+ ready->n_ready * sizeof (rtx));
+ ready->first = ready->veclen - 2;
+ }
+ ready->vec[++(ready->first)] = insn;
+ }
+
ready->n_ready++;
+
+ gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
+ QUEUE_INDEX (insn) = QUEUE_READY;
}
/* Remove the element with the highest priority from the ready list and
@@ -789,6 +855,10 @@ ready_remove_first (struct ready_list *r
/* If the queue becomes empty, reset it. */
if (ready->n_ready == 0)
ready->first = ready->veclen - 1;
+
+ gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
+ QUEUE_INDEX (t) = QUEUE_NOWHERE;
+
return t;
}
@@ -825,9 +895,24 @@ ready_remove (struct ready_list *ready,
ready->n_ready--;
for (i = index; i < ready->n_ready; i++)
ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
+ QUEUE_INDEX (t) = QUEUE_NOWHERE;
return t;
}
+/* Remove INSN from the ready list. */
+static void
+ready_remove_insn (rtx insn)
+{
+ int i;
+
+ for (i = 0; i < readyp->n_ready; i++)
+ if (ready_element (readyp, i) == insn)
+ {
+ ready_remove (readyp, i);
+ return;
+ }
+ gcc_unreachable ();
+}
/* Sort the ready list READY by ascending priority, using the SCHED_SORT
macro. */
@@ -883,11 +968,10 @@ static int last_clock_var;
zero for insns in a schedule group). */
static int
-schedule_insn (rtx insn, struct ready_list *ready, int clock)
+schedule_insn (rtx insn)
{
rtx link;
int advance = 0;
- int premature_issue = 0;
if (sched_verbose >= 1)
{
@@ -895,7 +979,7 @@ schedule_insn (rtx insn, struct ready_li
print_insn (buf, insn, 0);
buf[40] = 0;
- fprintf (sched_dump, ";;\t%3i--> %-40s:", clock, buf);
+ fprintf (sched_dump, ";;\t%3i--> %-40s:", clock_var, buf);
if (recog_memoized (insn) < 0)
fprintf (sched_dump, "nothing");
@@ -904,52 +988,44 @@ schedule_insn (rtx insn, struct ready_li
fputc ('\n', sched_dump);
}
- if (INSN_TICK (insn) > clock)
- {
- /* 'insn' has been prematurely moved from the queue to the
- ready list. */
- premature_issue = INSN_TICK (insn) - clock;
- }
+ /* Scheduling instruction should have all its dependencies resolved and
+ should have been removed from the ready list. */
+ gcc_assert (INSN_DEP_COUNT (insn) == 0);
+ gcc_assert (!LOG_LINKS (insn));
+ gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
+
+ QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
+
+ /* Now we can free RESOLVED_DEPS list. */
+ if (current_sched_info->flags & USE_DEPS_LIST)
+ free_DEPS_LIST_list (&RESOLVED_DEPS (insn));
+ else
+ free_INSN_LIST_list (&RESOLVED_DEPS (insn));
+
+ gcc_assert (INSN_TICK (insn) >= MIN_TICK);
+ if (INSN_TICK (insn) > clock_var)
+ /* INSN has been prematurely moved from the queue to the ready list.
+ This is possible only if following flag is set. */
+ gcc_assert (flag_sched_stalled_insns);
+
+ /* ??? Probably, if INSN is scheduled prematurely, we should leave
+ INSN_TICK untouched. This is a machine-dependent issue, actually. */
+ INSN_TICK (insn) = clock_var;
- for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
+ /* Update dependent instructions. */
+ for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
{
+ int effective_cost;
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);
- }
+ resolve_dep (next, insn);
- /* Adjust the priority of NEXT and either put it on the ready
- list or queue it. */
- 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;
- }
- }
+ effective_cost = try_ready (next);
+
+ if (effective_cost >= 0
+ && SCHED_GROUP_P (next)
+ && advance < effective_cost)
+ advance = effective_cost;
}
/* Annotate the instruction with issue information -- TImode
@@ -962,9 +1038,10 @@ schedule_insn (rtx insn, struct ready_li
&& GET_CODE (PATTERN (insn)) != CLOBBER)
{
if (reload_completed)
- PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
- last_clock_var = clock;
+ PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
+ last_clock_var = clock_var;
}
+
return advance;
}
@@ -1354,9 +1431,6 @@ find_insn_reg_weight (int b)
}
}
-/* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
-static int clock_var;
-
/* Move insns that became ready to fire from queue to ready list. */
static void
@@ -1378,11 +1452,11 @@ queue_to_ready (struct ready_list *ready
fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
(*current_sched_info->print_insn) (insn, 0));
- ready_add (ready, insn);
+ ready_add (ready, insn, false);
if (sched_verbose >= 2)
fprintf (sched_dump, "moving to ready without stalls\n");
}
- insn_queue[q_ptr] = 0;
+ free_INSN_LIST_list (&insn_queue[q_ptr]);
/* If there are no ready insns, stall until one is ready and add all
of the pending insns at that point to the ready list. */
@@ -1403,11 +1477,11 @@ queue_to_ready (struct ready_list *ready
fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
(*current_sched_info->print_insn) (insn, 0));
- ready_add (ready, insn);
+ ready_add (ready, insn, false);
if (sched_verbose >= 2)
fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
}
- insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
+ free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
advance_one_cycle ();
@@ -1542,7 +1616,7 @@ early_queue_to_ready (state_t state, str
{
/* move from Q to R */
q_size -= 1;
- ready_add (ready, insn);
+ ready_add (ready, insn, false);
if (prev_link)
XEXP (prev_link, 1) = next_link;
@@ -1557,7 +1631,8 @@ early_queue_to_ready (state_t state, str
insns_removed++;
if (insns_removed == flag_sched_stalled_insns)
- /* Remove only one insn from Q at a time. */
+ /* Remove no more than flag_sched_stalled_insns insns
+ from Q at a time. */
return insns_removed;
}
}
@@ -1872,6 +1947,7 @@ schedule_block (int b, int rgn_n_insns)
state_reset (curr_state);
/* Allocate the ready list. */
+ readyp = &ready;
ready.veclen = rgn_n_insns + 1 + issue_rate;
ready.first = ready.veclen - 1;
ready.vec = XNEWVEC (rtx, ready.veclen);
@@ -1884,8 +1960,6 @@ schedule_block (int b, int rgn_n_insns)
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);
@@ -1899,10 +1973,16 @@ schedule_block (int b, int rgn_n_insns)
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;
/* Start just before the beginning of time. */
clock_var = -1;
+
+ /* We need queue and ready lists and clock_var be initialized
+ in try_ready () (which is called through init_ready_list ()). */
+ (*current_sched_info->init_ready_list) ();
+
+ last_clock_var = -1;
+
advance = 0;
sort_p = TRUE;
@@ -2002,9 +2082,20 @@ schedule_block (int b, int rgn_n_insns)
&& targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
insn, last_clock_var,
clock_var, &sort_p))
+ /* SORT_P is used by the target to override sorting
+ of the ready list. This is needed when the target
+ has modified its internal structures expecting that
+ the insn will be issued next. As we need the insn
+ to have the highest priority (so it will be returned by
+ the ready_remove_first call above), we invoke
+ ready_add (&ready, insn, true).
+ But, still, there is one issue: INSN can be later
+ discarded by scheduler's front end through
+ current_sched_info->can_schedule_ready_p, hence, won't
+ be issued next. */
{
- ready_add (&ready, insn);
- break;
+ ready_add (&ready, insn, true);
+ break;
}
sort_p = TRUE;
@@ -2051,8 +2142,10 @@ schedule_block (int b, int rgn_n_insns)
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);
+ {
+ cycle_issued_insns++;
+ memcpy (curr_state, temp_state, dfa_state_size);
+ }
if (targetm.sched.variable_issue)
can_issue_more =
@@ -2064,7 +2157,7 @@ schedule_block (int b, int rgn_n_insns)
&& GET_CODE (PATTERN (insn)) != CLOBBER)
can_issue_more--;
- advance = schedule_insn (insn, &ready, clock_var);
+ advance = schedule_insn (insn);
/* After issuing an asm insn we should start a new cycle. */
if (advance == 0 && asm_p)
@@ -2094,9 +2187,6 @@ schedule_block (int b, int rgn_n_insns)
}
}
- if (targetm.sched.md_finish)
- targetm.sched.md_finish (sched_dump, sched_verbose);
-
/* Debug info. */
if (sched_verbose)
{
@@ -2104,17 +2194,24 @@ schedule_block (int b, int rgn_n_insns)
debug_ready_list (&ready);
}
- /* Sanity check -- queue must be empty now. Meaningless if region has
- multiple bbs. */
- gcc_assert (!current_sched_info->queue_must_finish_empty || !q_size);
+ if (current_sched_info->queue_must_finish_empty)
+ /* Sanity check -- queue must be empty now. Meaningless if region has
+ multiple bbs. */
+ gcc_assert (!q_size && !ready.n_ready);
+ else
+ {
+ /* We must maintain QUEUE_INDEX between blocks in region. */
+ for (i = ready.n_ready - 1; i >= 0; i--)
+ QUEUE_INDEX (ready_element (&ready, i)) = QUEUE_NOWHERE;
- /* Update head/tail boundaries. */
- head = NEXT_INSN (prev_head);
- tail = last_scheduled_insn;
-
- if (!reload_completed)
- {
- rtx insn, link, next;
+ if (q_size)
+ for (i = 0; i <= max_insn_queue_index; i++)
+ {
+ rtx link;
+ for (link = insn_queue[i]; link; link = XEXP (link, 1))
+ QUEUE_INDEX (XEXP (link, 0)) = QUEUE_NOWHERE;
+ free_INSN_LIST_list (&insn_queue[i]);
+ }
/* INSN_TICK (minimum clock tick at which the insn becomes
ready) may be not correct for the insn in the subsequent
@@ -2122,17 +2219,16 @@ schedule_block (int b, int rgn_n_insns)
`clock_var' or modify INSN_TICK. It is better to keep
clock_var value equal to 0 at the start of a basic block.
Therefore we modify INSN_TICK here. */
- 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;
- }
- }
+ fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
}
+ if (targetm.sched.md_finish)
+ targetm.sched.md_finish (sched_dump, sched_verbose);
+
+ /* Update head/tail boundaries. */
+ head = NEXT_INSN (prev_head);
+ tail = last_scheduled_insn;
+
/* Restore-other-notes: NOTE_LIST is the end of a chain of notes
previously found among the insns. Insert them at the beginning
of the insns. */
@@ -2183,16 +2279,15 @@ set_priorities (rtx head, rtx tail)
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;
+
+ prev_head = PREV_INSN (head);
for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
{
- if (NOTE_P (insn))
+ if (!INSN_P (insn))
continue;
n_insn++;
@@ -2202,9 +2297,8 @@ set_priorities (rtx head, rtx tail)
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;
+
+ current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
return n_insn;
}
@@ -2253,7 +2347,12 @@ sched_init (void)
h_i_d = XCNEWVEC (struct haifa_insn_data, old_max_uid);
for (i = 0; i < old_max_uid; i++)
- h_i_d [i].cost = -1;
+ {
+ h_i_d[i].cost = -1;
+ h_i_d[i].queue_index = QUEUE_NOWHERE;
+ h_i_d[i].tick = INVALID_TICK;
+ h_i_d[i].inter_tick = INVALID_TICK;
+ }
if (targetm.sched.init_dfa_pre_cycle_insn)
targetm.sched.init_dfa_pre_cycle_insn ();
@@ -2320,8 +2419,7 @@ sched_init (void)
}
}
- /* ??? Add a NOTE after the last insn of the last basic block. It is not
- known why this is done. */
+ /* The following is done to keep current_sched_info->next_tail non null. */
insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
if (NEXT_INSN (insn) == 0
@@ -2330,9 +2428,9 @@ sched_init (void)
/* Don't emit a NOTE if it would end up before a BARRIER. */
&& !BARRIER_P (NEXT_INSN (insn))))
{
- emit_note_after (NOTE_INSN_DELETED, BB_END (EXIT_BLOCK_PTR->prev_bb));
+ emit_note_after (NOTE_INSN_DELETED, insn);
/* Make insn to appear outside BB. */
- BB_END (EXIT_BLOCK_PTR->prev_bb) = PREV_INSN (BB_END (EXIT_BLOCK_PTR->prev_bb));
+ BB_END (EXIT_BLOCK_PTR->prev_bb) = insn;
}
/* Compute INSN_REG_WEIGHT for all blocks. We must do this before
@@ -2362,4 +2460,208 @@ sched_finish (void)
current_sched_info = NULL;
}
+
+/* Fix INSN_TICKs of the instructions in the current block as well as
+ INSN_TICKs of their dependants.
+ HEAD and TAIL are the begin and the end of the current scheduled block. */
+static void
+fix_inter_tick (rtx head, rtx tail)
+{
+ /* Set of instructions with corrected INSN_TICK. */
+ bitmap_head processed;
+ int next_clock = clock_var + 1;
+
+ bitmap_initialize (&processed, 0);
+
+ /* Iterates over scheduled instructions and fix their INSN_TICKs and
+ INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
+ across different blocks. */
+ for (tail = NEXT_INSN (tail); head != tail; head = NEXT_INSN (head))
+ {
+ if (INSN_P (head))
+ {
+ int tick;
+ rtx link;
+
+ tick = INSN_TICK (head);
+ gcc_assert (tick >= MIN_TICK);
+
+ /* Fix INSN_TICK of instruction from just scheduled block. */
+ if (!bitmap_bit_p (&processed, INSN_LUID (head)))
+ {
+ bitmap_set_bit (&processed, INSN_LUID (head));
+ tick -= next_clock;
+
+ if (tick < MIN_TICK)
+ tick = MIN_TICK;
+
+ INSN_TICK (head) = tick;
+ }
+
+ for (link = INSN_DEPEND (head); link; link = XEXP (link, 1))
+ {
+ rtx next;
+
+ next = XEXP (link, 0);
+ tick = INSN_TICK (next);
+
+ if (tick != INVALID_TICK
+ /* If NEXT has its INSN_TICK calculated, fix it.
+ If not - it will be properly calculated from
+ scratch later in fix_tick_ready. */
+ && !bitmap_bit_p (&processed, INSN_LUID (next)))
+ {
+ bitmap_set_bit (&processed, INSN_LUID (next));
+ tick -= next_clock;
+
+ if (tick < MIN_TICK)
+ tick = MIN_TICK;
+
+ if (tick > INTER_TICK (next))
+ INTER_TICK (next) = tick;
+ else
+ tick = INTER_TICK (next);
+
+ INSN_TICK (next) = tick;
+ }
+ }
+ }
+ }
+ bitmap_clear (&processed);
+}
+
+/* Check if NEXT is ready to be added to the ready or queue list.
+ If "yes", add it to the proper list.
+ Returns:
+ -1 - is not ready yet,
+ 0 - added to the ready list,
+ 0 < N - queued for N cycles. */
+int
+try_ready (rtx next)
+{
+ if (LOG_LINKS (next)
+ || (current_sched_info->new_ready
+ && !current_sched_info->new_ready (next)))
+ {
+ gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);
+ return -1;
+ }
+
+ if (sched_verbose >= 2)
+ fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s\n",
+ (*current_sched_info->print_insn) (next, 0));
+
+ adjust_priority (next);
+
+ return fix_tick_ready (next);
+}
+
+/* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
+static int
+fix_tick_ready (rtx next)
+{
+ rtx link;
+ int tick, delay;
+
+ link = RESOLVED_DEPS (next);
+
+ if (link)
+ {
+ int full_p;
+
+ tick = INSN_TICK (next);
+ /* if tick is note equals to INVALID_TICK, then update
+ INSN_TICK of NEXT with the most recent resolved dependence
+ cost. Overwise, recalculate from scratch. */
+ full_p = tick == INVALID_TICK;
+ do
+ {
+ rtx pro;
+ int tick1;
+
+ pro = XEXP (link, 0);
+ gcc_assert (INSN_TICK (pro) >= MIN_TICK);
+ /* We should specify FORWARD link to insn_cost,
+ but are giving a BACKWARD one.
+ This is ok, because only REG_NOTE_KIND of link is used.
+ May be substitute LINK with REG_NOTE_KIND? */
+ tick1 = INSN_TICK (pro) + insn_cost (pro, link, next);
+ if (tick1 > tick)
+ tick = tick1;
+ }
+ while ((link = XEXP (link, 1)) && full_p);
+ }
+ else
+ tick = -1;
+
+ INSN_TICK (next) = tick;
+
+ delay = tick - clock_var;
+ if (delay <= 0)
+ delay = QUEUE_READY;
+
+ change_queue_index (next, delay);
+
+ return delay;
+}
+
+/* Move NEXT to the proper queue list with (DELAY >= 1),
+ or add it to the ready list (DELAY == QUEUE_READY),
+ or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
+static void
+change_queue_index (rtx next, int delay)
+{
+ int i = QUEUE_INDEX (next);
+
+ gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index
+ && delay != 0);
+ gcc_assert (i != QUEUE_SCHEDULED);
+
+ if ((delay > 0 && NEXT_Q_AFTER (q_ptr, delay) == i)
+ || (delay < 0 && delay == i))
+ /* We have nothing to do. */
+ return;
+
+ /* Remove NEXT from whereever it is now. */
+ if (i == QUEUE_READY)
+ ready_remove_insn (next);
+ else if (i >= 0)
+ queue_remove (next);
+
+ /* Add it to the proper place. */
+ if (delay == QUEUE_READY)
+ ready_add (readyp, next, false);
+ else if (delay >= 1)
+ queue_insn (next, delay);
+
+ if (sched_verbose >= 2)
+ {
+ fprintf (sched_dump, ";;\t\ttick updated: insn %s",
+ (*current_sched_info->print_insn) (next, 0));
+
+ if (delay == QUEUE_READY)
+ fprintf (sched_dump, " into ready\n");
+ else if (delay >= 1)
+ fprintf (sched_dump, " into queue with cost=%d\n", delay);
+ else
+ fprintf (sched_dump, " removed from ready or queue lists\n");
+ }
+}
+
+/* INSN is being scheduled. Resolve the dependence between INSN and NEXT. */
+static void
+resolve_dep (rtx next, rtx insn)
+{
+ rtx dep;
+
+ INSN_DEP_COUNT (next)--;
+
+ dep = remove_list_elem (insn, &LOG_LINKS (next));
+ XEXP (dep, 1) = RESOLVED_DEPS (next);
+ RESOLVED_DEPS (next) = dep;
+
+ gcc_assert ((INSN_DEP_COUNT (next) != 0 || !LOG_LINKS (next))
+ && (LOG_LINKS (next) || INSN_DEP_COUNT (next) == 0));
+}
+
#endif /* INSN_SCHEDULING */
--- rtl.h (/fortuna/regions/gcc) (revision 133)
+++ rtl.h (/fortuna/insn-tick/gcc) (revision 133)
@@ -1756,6 +1756,8 @@ rtx alloc_EXPR_LIST (int, rtx, rtx);
void free_DEPS_LIST_list (rtx *);
rtx alloc_DEPS_LIST (rtx, rtx, HOST_WIDE_INT);
void remove_free_DEPS_LIST_elem (rtx, rtx *);
+void remove_free_INSN_LIST_elem (rtx, rtx *);
+rtx remove_list_elem (rtx, rtx *);
/* regclass.c */
--- sched-int.h (/fortuna/regions/gcc) (revision 133)
+++ sched-int.h (/fortuna/insn-tick/gcc) (revision 133)
@@ -142,7 +142,7 @@ struct sched_info
{
/* Add all insns that are initially ready to the ready list. Called once
before scheduling a set of insns. */
- void (*init_ready_list) (struct ready_list *);
+ void (*init_ready_list) (void);
/* Called after taking an insn from the ready list. Returns nonzero if
this insn can be scheduled, nonzero if we should silently discard it. */
int (*can_schedule_ready_p) (rtx);
@@ -203,6 +203,10 @@ struct haifa_insn_data
it represents forward dependencies. */
rtx depend;
+ /* A list of scheduled producers of the instruction. Links are being moved
+ from LOG_LINKS to RESOLVED_DEPS during scheduling. */
+ rtx resolved_deps;
+
/* The line number note in effect for each insn. For line number
notes, this indicates whether the note may be reused. */
rtx line_note;
@@ -225,6 +229,13 @@ struct haifa_insn_data
used to note timing constraints for the insns in the pending list. */
int tick;
+ /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
+ subsequent blocks in a region. */
+ int inter_tick;
+
+ /* See comment on QUEUE_INDEX macro in haifa-sched.c. */
+ int queue_index;
+
short cost;
/* This weight is an estimation of the insn's contribution to
@@ -252,6 +263,7 @@ extern struct haifa_insn_data *h_i_d;
/* Accessor macros for h_i_d. There are more in haifa-sched.c and
sched-rgn.c. */
#define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend)
+#define RESOLVED_DEPS(INSN) (h_i_d[INSN_UID (INSN)].resolved_deps)
#define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid)
#define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move)
#define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count)
@@ -513,6 +525,6 @@ extern void schedule_block (int, int);
extern void sched_init (void);
extern void sched_finish (void);
-extern void ready_add (struct ready_list *, rtx);
+extern int try_ready (rtx);
#endif /* GCC_SCHED_INT_H */
--- sched-rgn.c (/fortuna/regions/gcc) (revision 133)
+++ sched-rgn.c (/fortuna/insn-tick/gcc) (revision 133)
@@ -1884,7 +1884,7 @@ static int sched_n_insns;
static int last_was_jump;
/* Implementations of the sched_info functions for region scheduling. */
-static void init_ready_list (struct ready_list *);
+static void init_ready_list (void);
static int can_schedule_ready_p (rtx);
static int new_ready (rtx);
static int schedule_more_p (void);
@@ -1905,7 +1905,7 @@ schedule_more_p (void)
once before scheduling a set of insns. */
static void
-init_ready_list (struct ready_list *ready)
+init_ready_list (void)
{
rtx prev_head = current_sched_info->prev_head;
rtx next_tail = current_sched_info->next_tail;
@@ -1943,15 +1943,8 @@ init_ready_list (struct ready_list *read
/* Initialize ready list with all 'ready' insns in target block.
Count number of insns in the target block being scheduled. */
for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
- {
- if (INSN_DEP_COUNT (insn) == 0)
- {
- ready_add (ready, insn);
-
- if (targetm.sched.adjust_priority)
- INSN_PRIORITY (insn) =
- targetm.sched.adjust_priority (insn, INSN_PRIORITY (insn));
- }
+ {
+ try_ready (insn);
target_n_insns++;
}
@@ -1970,26 +1963,8 @@ init_ready_list (struct ready_list *read
src_head = head;
for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
- {
- if (! INSN_P (insn))
- continue;
-
- if (!CANT_MOVE (insn)
- && (!IS_SPECULATIVE_INSN (insn)
- || ((recog_memoized (insn) < 0
- || min_insn_conflict_delay (curr_state,
- insn, insn) <= 3)
- && check_live (insn, bb_src)
- && is_exception_free (insn, bb_src, target_bb))))
- if (INSN_DEP_COUNT (insn) == 0)
- {
- ready_add (ready, insn);
-
- if (targetm.sched.adjust_priority)
- INSN_PRIORITY (insn) =
- targetm.sched.adjust_priority (insn, INSN_PRIORITY (insn));
- }
- }
+ if (INSN_P (insn))
+ try_ready (insn);
}
}
@@ -2638,6 +2613,7 @@ schedule_region (int rgn)
}
/* Set priorities. */
+ current_sched_info->sched_max_insns_priority = 0;
for (bb = 0; bb < current_nr_blocks; bb++)
{
rtx head, tail;
@@ -2645,6 +2621,7 @@ schedule_region (int rgn)
rgn_n_insns += set_priorities (head, tail);
}
+ current_sched_info->sched_max_insns_priority++;
/* Compute interblock info: probabilities, split-edges, dominators, etc. */
if (current_nr_blocks > 1)
@@ -2727,8 +2704,8 @@ schedule_region (int rgn)
target_bb = bb;
- current_sched_info->queue_must_finish_empty
- = current_nr_blocks > 1 && !flag_schedule_interblock;
+ gcc_assert (flag_schedule_interblock || current_nr_blocks == 1);
+ current_sched_info->queue_must_finish_empty = current_nr_blocks == 1;
schedule_block (b, rgn_n_insns);
sched_rgn_n_insns += sched_n_insns;