From: Trevor Saunders <tbsaunde+...@tbsaunde.org>
gcc/ChangeLog:
2016-04-19 Trevor Saunders <tbsaunde+...@tbsaunde.org>
* haifa-sched.c (queue_insn): Adjust.
(queue_remove): Likewise.
(check_clobbered_conditions): Likewise.
(struct haifa_saved_data): Make insn_queue a vector.
(save_backtrack_point): Adjust.
(toggle_cancelled_flags): Likewise.
(restore_last_backtrack_point): Likewise.
(free_topmost_backtrack_point): Likewise.
(queue_to_ready): Likewise.
(early_queue_to_ready): Likewise.
(autopref_multipass_dfa_lookahead_guard): Likewise.
(schedule_block): Likewise.
---
gcc/haifa-sched.c | 205 +++++++++++++++++++++++++++---------------------------
1 file changed, 101 insertions(+), 104 deletions(-)
diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index e972531..0721ec5 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -122,6 +122,7 @@ along with GCC; see the file COPYING3. If not see
other NOTE insns are grouped in their same relative order at the
beginning of basic blocks and regions that have been scheduled. */
+#define INCLUDE_ALGORITHM
#include "config.h"
#include "system.h"
#include "coretypes.h"
@@ -320,7 +321,7 @@ bool adding_bb_to_current_region_p = true;
the base maximal time of functional unit reservations and getting a
result. This is the longest time an insn may be queued. */
-static rtx_insn_list **insn_queue;
+static vec<rtx_insn *> *insn_queue;
static int q_ptr = 0;
static int q_size = 0;
#define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
@@ -2826,13 +2827,12 @@ HAIFA_INLINE static void
queue_insn (rtx_insn *insn, int n_cycles, const char *reason)
{
int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
- rtx_insn_list *link = alloc_INSN_LIST (insn, insn_queue[next_q]);
int new_tick;
gcc_assert (n_cycles <= max_insn_queue_index);
gcc_assert (!DEBUG_INSN_P (insn));
- insn_queue[next_q] = link;
+ insn_queue[next_q].safe_push (insn);
q_size += 1;
if (sched_verbose >= 2)
@@ -2861,14 +2861,26 @@ queue_insn (rtx_insn *insn, int n_cycles, const char
*reason)
}
}
-/* Remove INSN from queue. */
+/* Remove INSN at idx from queue. */
+static void
+queue_remove (unsigned int q, unsigned int idx)
+{
+ QUEUE_INDEX (insn_queue[q][idx]) = QUEUE_NOWHERE;
+ insn_queue[q].ordered_remove (idx);
+ q_size--;
+}
+
+/* Remove insn from the queue. */
+
static void
queue_remove (rtx_insn *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;
+
+ unsigned int q = QUEUE_INDEX (insn);
+ unsigned int idx = std::find (insn_queue[q].begin (), insn_queue[q].end (),
+ insn) - insn_queue[q].begin ();
+ queue_remove (q, idx);
}
/* Return a pointer to the bottom of the ready list, i.e. the insn
@@ -3267,17 +3279,16 @@ check_clobbered_conditions (rtx_insn *insn)
}
for (i = 0; i <= max_insn_queue_index; i++)
{
- rtx_insn_list *link;
int q = NEXT_Q_AFTER (q_ptr, i);
- restart_queue:
- for (link = insn_queue[q]; link; link = link->next ())
+ unsigned int len = insn_queue[q].length ();
+ for (unsigned int i = len - 1; i < len; i--)
{
- rtx_insn *x = link->insn ();
+ rtx_insn *x = insn_queue[q][i];
if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
{
queue_remove (x);
- goto restart_queue;
+ i = insn_queue[q].length ();
}
}
}
@@ -4277,7 +4288,7 @@ struct haifa_saved_data
/* We don't need to save q_ptr, as its value is arbitrary and we can set it
to 0 when restoring. */
int q_size;
- rtx_insn_list **insn_queue;
+ vec<rtx_insn *> *insn_queue;
/* Describe pattern replacements that occurred since this backtrack point
was queued. */
@@ -4328,12 +4339,12 @@ save_backtrack_point (struct delay_pair *pair,
save->ready.vec = XNEWVEC (rtx_insn *, ready.veclen);
memcpy (save->ready.vec, ready.vec, ready.veclen * sizeof (rtx));
- save->insn_queue = XNEWVEC (rtx_insn_list *, max_insn_queue_index + 1);
+ save->insn_queue = XNEWVEC (vec<rtx_insn *>, max_insn_queue_index + 1);
save->q_size = q_size;
for (i = 0; i <= max_insn_queue_index; i++)
{
int q = NEXT_Q_AFTER (q_ptr, i);
- save->insn_queue[i] = copy_INSN_LIST (insn_queue[q]);
+ save->insn_queue[i] = insn_queue[q].copy ();
}
save->clock_var = clock_var;
@@ -4403,10 +4414,10 @@ toggle_cancelled_flags (bool set)
for (i = 0; i <= max_insn_queue_index; i++)
{
int q = NEXT_Q_AFTER (q_ptr, i);
- rtx_insn_list *link;
- for (link = insn_queue[q]; link; link = link->next ())
+ unsigned int len = insn_queue[q].length ();
+ for (unsigned int i = len - 1; i < len; i--)
{
- rtx_insn *insn = link->insn ();
+ rtx_insn *insn = insn_queue[q][i];
FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
if (!DEBUG_INSN_P (DEP_PRO (dep)))
{
@@ -4546,14 +4557,14 @@ restore_last_backtrack_point (struct sched_block_state
*psched_block)
for (i = 0; i <= max_insn_queue_index; i++)
{
int q = NEXT_Q_AFTER (q_ptr, i);
-
- for (rtx_insn_list *link = insn_queue[q]; link; link = link->next ())
+ unsigned int len = insn_queue[q].length ();
+ for (unsigned int i = len - 1; i < len; i--)
{
- rtx_insn *x = link->insn ();
+ rtx_insn *x = insn_queue[q][i];
QUEUE_INDEX (x) = QUEUE_NOWHERE;
INSN_TICK (x) = INVALID_TICK;
}
- free_INSN_LIST_list (&insn_queue[q]);
+ insn_queue[q].release ();
}
free (ready.vec);
@@ -4577,11 +4588,13 @@ restore_last_backtrack_point (struct sched_block_state
*psched_block)
{
int q = NEXT_Q_AFTER (q_ptr, i);
+ insn_queue[q].release ();
insn_queue[q] = save->insn_queue[q];
- for (rtx_insn_list *link = insn_queue[q]; link; link = link->next ())
+ unsigned int len = insn_queue[q].length ();
+ for (unsigned int j = len - 1; j < len; j--)
{
- rtx_insn *x = link->insn ();
+ rtx_insn *x = insn_queue[q][j];
QUEUE_INDEX (x) = i;
TODO_SPEC (x) = recompute_todo_spec (x, true);
INSN_TICK (x) = save->clock_var + i;
@@ -4651,7 +4664,7 @@ free_topmost_backtrack_point (bool reset_tick)
if (current_sched_info->restore_state)
free (save->fe_saved_data);
for (i = 0; i <= max_insn_queue_index; i++)
- free_INSN_LIST_list (&save->insn_queue[i]);
+ save->insn_queue[i].release ();
free (save->insn_queue);
free (save->curr_state);
free (save->ready.vec);
@@ -5090,7 +5103,6 @@ static void
queue_to_ready (struct ready_list *ready)
{
rtx_insn *insn;
- rtx_insn_list *link;
rtx_insn *skip_insn;
q_ptr = NEXT_Q (q_ptr);
@@ -5104,9 +5116,10 @@ queue_to_ready (struct ready_list *ready)
/* Add all pending insns that can be scheduled without stalls to the
ready list. */
- for (link = insn_queue[q_ptr]; link; link = link->next ())
+ unsigned int len = insn_queue[q_ptr].length ();
+ for (unsigned int i = len - 1; i < len; i--)
{
- insn = link->insn ();
+ insn = insn_queue[q_ptr][i];
q_size -= 1;
if (sched_verbose >= 2)
@@ -5140,7 +5153,7 @@ queue_to_ready (struct ready_list *ready)
fprintf (sched_dump, "moving to ready without stalls\n");
}
}
- free_INSN_LIST_list (&insn_queue[q_ptr]);
+ insn_queue[q_ptr].release ();
/* 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. */
@@ -5150,11 +5163,13 @@ queue_to_ready (struct ready_list *ready)
for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
{
- if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
+ int q = NEXT_Q_AFTER (q_ptr, stalls);
+ if (!insn_queue[q].is_empty ())
{
- for (; link; link = link->next ())
+ unsigned int len = insn_queue[q].length ();
+ for (unsigned int i = len - 1; i < len; i--)
{
- insn = link->insn ();
+ insn = insn_queue[q][i];
q_size -= 1;
if (sched_verbose >= 2)
@@ -5165,7 +5180,7 @@ queue_to_ready (struct ready_list *ready)
if (sched_verbose >= 2)
fprintf (sched_dump, "moving to ready with %d stalls\n",
stalls);
}
- free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
+ insn_queue[q].release ();
advance_one_cycle ();
@@ -5245,9 +5260,6 @@ static int
early_queue_to_ready (state_t state, struct ready_list *ready)
{
rtx_insn *insn;
- rtx_insn_list *link;
- rtx_insn_list *next_link;
- rtx_insn_list *prev_link;
bool move_to_ready;
int cost;
state_t temp_state = alloca (dfa_state_size);
@@ -5273,66 +5285,54 @@ early_queue_to_ready (state_t state, struct ready_list
*ready)
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);
+ if (insn_queue[NEXT_Q_AFTER (q_ptr, stalls)].is_empty ())
+ continue;
- prev_link = 0;
- while (link)
- {
- next_link = link->next ();
- insn = link->insn ();
- if (insn && sched_verbose > 6)
- print_rtl_single (sched_dump, insn);
-
- memcpy (temp_state, state, dfa_state_size);
- if (recog_memoized (insn) < 0)
- /* non-negative to indicate that it's not ready
- to avoid infinite Q->R->Q->R... */
- cost = 0;
- else
- cost = state_transition (temp_state, insn);
+ if (sched_verbose > 6)
+ fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
- if (sched_verbose >= 6)
- fprintf (sched_dump, "transition cost = %d\n", cost);
+ unsigned int len = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)].length ();
+ for (unsigned int i = len - 1; i < len; i--)
+ {
+ insn = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)][i];
+ if (insn && sched_verbose > 6)
+ print_rtl_single (sched_dump, insn);
+
+ memcpy (temp_state, state, dfa_state_size);
+ if (recog_memoized (insn) < 0)
+ /* non-negative to indicate that it's not ready
+ to avoid infinite Q->R->Q->R... */
+ cost = 0;
+ else
+ cost = state_transition (temp_state, insn);
- move_to_ready = false;
- if (cost < 0)
- {
- move_to_ready = ok_for_early_queue_removal (insn);
- if (move_to_ready == true)
- {
- /* move from Q to R */
- q_size -= 1;
- ready_add (ready, insn, false);
+ if (sched_verbose >= 6)
+ fprintf (sched_dump, "transition cost = %d\n", cost);
- if (prev_link)
- XEXP (prev_link, 1) = next_link;
- else
- insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
+ move_to_ready = false;
+ if (cost < 0)
+ {
+ move_to_ready = ok_for_early_queue_removal (insn);
+ if (move_to_ready == true)
+ {
+ /* move from Q to R */
+ q_size -= 1;
+ ready_add (ready, insn, false);
- free_INSN_LIST_node (link);
+ insn_queue[NEXT_Q_AFTER (q_ptr, stalls)].ordered_remove (i);
- if (sched_verbose >= 2)
- fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
- (*current_sched_info->print_insn) (insn, 0));
+ 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)
- /* Remove no more than flag_sched_stalled_insns insns
- from Q at a time. */
- return insns_removed;
- }
+ insns_removed++;
+ if (insns_removed == flag_sched_stalled_insns)
+ /* Remove no more than flag_sched_stalled_insns insns
+ from Q at a time. */
+ return insns_removed;
}
-
- if (move_to_ready == false)
- prev_link = link;
-
- link = next_link;
- } /* while link */
- } /* if link */
-
+ }
+ } /* while link */
} /* for stalls.. */
return insns_removed;
@@ -5845,7 +5845,7 @@ autopref_multipass_dfa_lookahead_guard (rtx_insn *insn1,
int ready_index)
/* Everything from the current queue slot should have been moved to
the ready list. */
- gcc_assert (insn_queue[NEXT_Q_AFTER (q_ptr, 0)] == NULL_RTX);
+ gcc_assert (insn_queue[NEXT_Q_AFTER (q_ptr, 0)].is_empty ());
int n_stalls = PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) - 1;
if (n_stalls > max_insn_queue_index)
@@ -5853,11 +5853,12 @@ autopref_multipass_dfa_lookahead_guard (rtx_insn
*insn1, int ready_index)
for (int stalls = 1; stalls <= n_stalls; ++stalls)
{
- for (rtx_insn_list *link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)];
- link != NULL_RTX;
- link = link->next ())
+ const vec<rtx_insn *> &insns =
+ insn_queue[NEXT_Q_AFTER (q_ptr, stalls)];
+ unsigned int len = insns.length ();
+ for (unsigned int j = len - 1; j < len; j--)
{
- rtx_insn *insn2 = link->insn ();
+ rtx_insn *insn2 = insns[j];
r = autopref_multipass_dfa_lookahead_guard_1 (insn1, insn2,
write);
if (r)
@@ -6578,7 +6579,7 @@ schedule_block (basic_block *target_bb, state_t
init_state)
q_ptr = 0;
q_size = 0;
- insn_queue = XALLOCAVEC (rtx_insn_list *, max_insn_queue_index + 1);
+ insn_queue = XALLOCAVEC (vec<rtx_insn *>, max_insn_queue_index + 1);
memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
/* Start just before the beginning of time. */
@@ -7045,13 +7046,10 @@ schedule_block (basic_block *target_bb, state_t
init_state)
}
for (i = 0; i <= max_insn_queue_index; i++)
{
- rtx_insn_list *link;
- while ((link = insn_queue[i]) != NULL)
+ rtx_insn *x;
+ while ((x = insn_queue[i].pop ()))
{
- rtx_insn *x = link->insn ();
- insn_queue[i] = link->next ();
QUEUE_INDEX (x) = QUEUE_NOWHERE;
- free_INSN_LIST_node (link);
resolve_dependencies (x);
}
}
@@ -7086,16 +7084,15 @@ schedule_block (basic_block *target_bb, state_t
init_state)
if (q_size)
for (i = 0; i <= max_insn_queue_index; i++)
{
- rtx_insn_list *link;
- for (link = insn_queue[i]; link; link = link->next ())
+ unsigned int len = insn_queue[i].length ();
+ for (unsigned int j = len - 1; j < len; j--)
{
- rtx_insn *x;
+ rtx_insn *x = insn_queue[i][j];
- x = link->insn ();
QUEUE_INDEX (x) = QUEUE_NOWHERE;
TODO_SPEC (x) = HARD_DEP;
}
- free_INSN_LIST_list (&insn_queue[i]);
+ insn_queue[i].release ();
}
}
--
2.7.4
