1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004, 2005
3 Free Software Foundation, Inc.
4 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
26 #include "coretypes.h"
31 #include "hard-reg-set.h"
35 #include "insn-config.h"
36 #include "insn-attr.h"
40 #include "sched-int.h"
42 #include "cfglayout.h"
51 #ifdef INSN_SCHEDULING
53 /* This file contains the implementation of the Swing Modulo Scheduler,
54 described in the following references:
55 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
56 Lifetime--sensitive modulo scheduling in a production environment.
57 IEEE Trans. on Comps., 50(3), March 2001
58 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
59 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
60 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
62 The basic structure is:
63 1. Build a data-dependence graph (DDG) for each loop.
64 2. Use the DDG to order the insns of a loop (not in topological order
65 necessarily, but rather) trying to place each insn after all its
66 predecessors _or_ after all its successors.
67 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
68 4. Use the ordering to perform list-scheduling of the loop:
69 1. Set II = MII. We will try to schedule the loop within II cycles.
70 2. Try to schedule the insns one by one according to the ordering.
71 For each insn compute an interval of cycles by considering already-
72 scheduled preds and succs (and associated latencies); try to place
73 the insn in the cycles of this window checking for potential
74 resource conflicts (using the DFA interface).
75 Note: this is different from the cycle-scheduling of schedule_insns;
76 here the insns are not scheduled monotonically top-down (nor bottom-
78 3. If failed in scheduling all insns - bump II++ and try again, unless
79 II reaches an upper bound MaxII, in which case report failure.
80 5. If we succeeded in scheduling the loop within II cycles, we now
81 generate prolog and epilog, decrease the counter of the loop, and
82 perform modulo variable expansion for live ranges that span more than
83 II cycles (i.e. use register copies to prevent a def from overwriting
84 itself before reaching the use).
88 /* This page defines partial-schedule structures and functions for
91 typedef struct partial_schedule *partial_schedule_ptr;
92 typedef struct ps_insn *ps_insn_ptr;
94 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
95 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
97 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
98 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
100 /* Perform signed modulo, always returning a non-negative value. */
101 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
103 /* The number of different iterations the nodes in ps span, assuming
104 the stage boundaries are placed efficiently. */
105 #define PS_STAGE_COUNT(ps) ((PS_MAX_CYCLE (ps) - PS_MIN_CYCLE (ps) \
106 + 1 + (ps)->ii - 1) / (ps)->ii)
108 #define CFG_HOOKS cfg_layout_rtl_cfg_hooks
110 /* A single instruction in the partial schedule. */
113 /* The corresponding DDG_NODE. */
116 /* The (absolute) cycle in which the PS instruction is scheduled.
117 Same as SCHED_TIME (node). */
120 /* The next/prev PS_INSN in the same row. */
121 ps_insn_ptr next_in_row,
124 /* The number of nodes in the same row that come after this node. */
128 /* Holds the partial schedule as an array of II rows. Each entry of the
129 array points to a linked list of PS_INSNs, which represents the
130 instructions that are scheduled for that row. */
131 struct partial_schedule
133 int ii; /* Number of rows in the partial schedule. */
134 int history; /* Threshold for conflict checking using DFA. */
136 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
139 /* The earliest absolute cycle of an insn in the partial schedule. */
142 /* The latest absolute cycle of an insn in the partial schedule. */
145 ddg_ptr g; /* The DDG of the insns in the partial schedule. */
148 /* We use this to record all the register replacements we do in
149 the kernel so we can undo SMS if it is not profitable. */
150 struct undo_replace_buff_elem
155 struct undo_replace_buff_elem *next;
160 partial_schedule_ptr create_partial_schedule (int ii, ddg_ptr, int history);
161 void free_partial_schedule (partial_schedule_ptr);
162 void reset_partial_schedule (partial_schedule_ptr, int new_ii);
163 void print_partial_schedule (partial_schedule_ptr, FILE *);
164 static int kernel_number_of_cycles (rtx first_insn, rtx last_insn);
165 static ps_insn_ptr ps_add_node_check_conflicts (partial_schedule_ptr,
166 ddg_node_ptr node, int cycle,
167 sbitmap must_precede,
168 sbitmap must_follow);
169 static void rotate_partial_schedule (partial_schedule_ptr, int);
170 void set_row_column_for_ps (partial_schedule_ptr);
171 static bool ps_unschedule_node (partial_schedule_ptr, ddg_node_ptr );
174 /* This page defines constants and structures for the modulo scheduling
177 /* As in haifa-sched.c: */
178 /* issue_rate is the number of insns that can be scheduled in the same
179 machine cycle. It can be defined in the config/mach/mach.h file,
180 otherwise we set it to 1. */
182 static int issue_rate;
184 /* For printing statistics. */
185 static FILE *stats_file;
187 static int sms_order_nodes (ddg_ptr, int, int * result);
188 static void set_node_sched_params (ddg_ptr);
189 static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int,
191 static void permute_partial_schedule (partial_schedule_ptr ps, rtx last);
192 static void generate_prolog_epilog (partial_schedule_ptr ,struct loop * loop, rtx);
193 static void duplicate_insns_of_cycles (partial_schedule_ptr ps,
194 int from_stage, int to_stage,
197 #define SCHED_ASAP(x) (((node_sched_params_ptr)(x)->aux.info)->asap)
198 #define SCHED_TIME(x) (((node_sched_params_ptr)(x)->aux.info)->time)
199 #define SCHED_FIRST_REG_MOVE(x) \
200 (((node_sched_params_ptr)(x)->aux.info)->first_reg_move)
201 #define SCHED_NREG_MOVES(x) \
202 (((node_sched_params_ptr)(x)->aux.info)->nreg_moves)
203 #define SCHED_ROW(x) (((node_sched_params_ptr)(x)->aux.info)->row)
204 #define SCHED_STAGE(x) (((node_sched_params_ptr)(x)->aux.info)->stage)
205 #define SCHED_COLUMN(x) (((node_sched_params_ptr)(x)->aux.info)->column)
207 /* The scheduling parameters held for each node. */
208 typedef struct node_sched_params
210 int asap; /* A lower-bound on the absolute scheduling cycle. */
211 int time; /* The absolute scheduling cycle (time >= asap). */
213 /* The following field (first_reg_move) is a pointer to the first
214 register-move instruction added to handle the modulo-variable-expansion
215 of the register defined by this node. This register-move copies the
216 original register defined by the node. */
219 /* The number of register-move instructions added, immediately preceding
223 int row; /* Holds time % ii. */
224 int stage; /* Holds time / ii. */
226 /* The column of a node inside the ps. If nodes u, v are on the same row,
227 u will precede v if column (u) < column (v). */
229 } *node_sched_params_ptr;
232 /* The following three functions are copied from the current scheduler
233 code in order to use sched_analyze() for computing the dependencies.
234 They are used when initializing the sched_info structure. */
236 sms_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED)
240 sprintf (tmp, "i%4d", INSN_UID (insn));
245 contributes_to_priority (rtx next, rtx insn)
247 return BLOCK_NUM (next) == BLOCK_NUM (insn);
251 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
252 regset cond_exec ATTRIBUTE_UNUSED,
253 regset used ATTRIBUTE_UNUSED,
254 regset set ATTRIBUTE_UNUSED)
258 static struct sched_info sms_sched_info =
266 contributes_to_priority,
267 compute_jump_reg_dependencies,
274 /* Return the register decremented and tested or zero if it is not a decrement
275 and branch jump insn (similar to doloop_condition_get). */
277 doloop_register_get (rtx insn, rtx *comp)
279 rtx pattern, cmp, inc, reg, condition;
283 pattern = PATTERN (insn);
285 /* The canonical doloop pattern we expect is:
287 (parallel [(set (pc) (if_then_else (condition)
290 (set (reg) (plus (reg) (const_int -1)))
291 (additional clobbers and uses)])
293 where condition is further restricted to be
294 (ne (reg) (const_int 1)). */
296 if (GET_CODE (pattern) != PARALLEL)
299 cmp = XVECEXP (pattern, 0, 0);
300 inc = XVECEXP (pattern, 0, 1);
301 /* Return the compare rtx. */
304 /* Check for (set (reg) (something)). */
305 if (GET_CODE (inc) != SET || ! REG_P (SET_DEST (inc)))
308 /* Extract loop counter register. */
309 reg = SET_DEST (inc);
311 /* Check if something = (plus (reg) (const_int -1)). */
312 if (GET_CODE (SET_SRC (inc)) != PLUS
313 || XEXP (SET_SRC (inc), 0) != reg
314 || XEXP (SET_SRC (inc), 1) != constm1_rtx)
317 /* Check for (set (pc) (if_then_else (condition)
320 if (GET_CODE (cmp) != SET
321 || SET_DEST (cmp) != pc_rtx
322 || GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE
323 || GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF
324 || XEXP (SET_SRC (cmp), 2) != pc_rtx)
327 /* Extract loop termination condition. */
328 condition = XEXP (SET_SRC (cmp), 0);
330 /* Check if condition = (ne (reg) (const_int 1)), which is more
331 restrictive than the check in doloop_condition_get:
332 if ((GET_CODE (condition) != GE && GET_CODE (condition) != NE)
333 || GET_CODE (XEXP (condition, 1)) != CONST_INT). */
334 if (GET_CODE (condition) != NE
335 || XEXP (condition, 1) != const1_rtx)
338 if (XEXP (condition, 0) == reg)
344 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
345 that the number of iterations is a compile-time constant. If so,
346 return the rtx that sets COUNT_REG to a constant, and set COUNT to
347 this constant. Otherwise return 0. */
349 const_iteration_count (rtx count_reg, basic_block pre_header,
350 HOST_WIDEST_INT * count)
358 get_block_head_tail (pre_header->index, &head, &tail);
360 for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn))
361 if (INSN_P (insn) && single_set (insn) &&
362 rtx_equal_p (count_reg, SET_DEST (single_set (insn))))
364 rtx pat = single_set (insn);
366 if (GET_CODE (SET_SRC (pat)) == CONST_INT)
368 *count = INTVAL (SET_SRC (pat));
378 /* A very simple resource-based lower bound on the initiation interval.
379 ??? Improve the accuracy of this bound by considering the
380 utilization of various units. */
384 return (g->num_nodes / issue_rate);
388 /* Points to the array that contains the sched data for each node. */
389 static node_sched_params_ptr node_sched_params;
391 /* Allocate sched_params for each node and initialize it. Assumes that
392 the aux field of each node contain the asap bound (computed earlier),
393 and copies it into the sched_params field. */
395 set_node_sched_params (ddg_ptr g)
399 /* Allocate for each node in the DDG a place to hold the "sched_data". */
400 /* Initialize ASAP/ALAP/HIGHT to zero. */
401 node_sched_params = (node_sched_params_ptr)
402 xcalloc (g->num_nodes,
403 sizeof (struct node_sched_params));
405 /* Set the pointer of the general data of the node to point to the
406 appropriate sched_params structure. */
407 for (i = 0; i < g->num_nodes; i++)
409 /* Watch out for aliasing problems? */
410 node_sched_params[i].asap = g->nodes[i].aux.count;
411 g->nodes[i].aux.info = &node_sched_params[i];
416 print_node_sched_params (FILE * dump_file, int num_nodes)
422 for (i = 0; i < num_nodes; i++)
424 node_sched_params_ptr nsp = &node_sched_params[i];
425 rtx reg_move = nsp->first_reg_move;
428 fprintf (dump_file, "Node %d:\n", i);
429 fprintf (dump_file, " asap = %d:\n", nsp->asap);
430 fprintf (dump_file, " time = %d:\n", nsp->time);
431 fprintf (dump_file, " nreg_moves = %d:\n", nsp->nreg_moves);
432 for (j = 0; j < nsp->nreg_moves; j++)
434 fprintf (dump_file, " reg_move = ");
435 print_rtl_single (dump_file, reg_move);
436 reg_move = PREV_INSN (reg_move);
441 /* Calculate an upper bound for II. SMS should not schedule the loop if it
442 requires more cycles than this bound. Currently set to the sum of the
443 longest latency edge for each node. Reset based on experiments. */
445 calculate_maxii (ddg_ptr g)
450 for (i = 0; i < g->num_nodes; i++)
452 ddg_node_ptr u = &g->nodes[i];
454 int max_edge_latency = 0;
456 for (e = u->out; e; e = e->next_out)
457 max_edge_latency = MAX (max_edge_latency, e->latency);
459 maxii += max_edge_latency;
465 Breaking intra-loop register anti-dependences:
466 Each intra-loop register anti-dependence implies a cross-iteration true
467 dependence of distance 1. Therefore, we can remove such false dependencies
468 and figure out if the partial schedule broke them by checking if (for a
469 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
470 if so generate a register move. The number of such moves is equal to:
471 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
472 nreg_moves = ----------------------------------- + 1 - { dependence.
475 static struct undo_replace_buff_elem *
476 generate_reg_moves (partial_schedule_ptr ps)
481 struct undo_replace_buff_elem *reg_move_replaces = NULL;
483 for (i = 0; i < g->num_nodes; i++)
485 ddg_node_ptr u = &g->nodes[i];
487 int nreg_moves = 0, i_reg_move;
488 sbitmap *uses_of_defs;
490 rtx prev_reg, old_reg;
492 /* Compute the number of reg_moves needed for u, by looking at life
493 ranges started at u (excluding self-loops). */
494 for (e = u->out; e; e = e->next_out)
495 if (e->type == TRUE_DEP && e->dest != e->src)
497 int nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
499 if (e->distance == 1)
500 nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
502 /* If dest precedes src in the schedule of the kernel, then dest
503 will read before src writes and we can save one reg_copy. */
504 if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)
505 && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))
508 nreg_moves = MAX (nreg_moves, nreg_moves4e);
514 /* Every use of the register defined by node may require a different
515 copy of this register, depending on the time the use is scheduled.
516 Set a bitmap vector, telling which nodes use each copy of this
518 uses_of_defs = sbitmap_vector_alloc (nreg_moves, g->num_nodes);
519 sbitmap_vector_zero (uses_of_defs, nreg_moves);
520 for (e = u->out; e; e = e->next_out)
521 if (e->type == TRUE_DEP && e->dest != e->src)
523 int dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
525 if (e->distance == 1)
526 dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
528 if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)
529 && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))
533 SET_BIT (uses_of_defs[dest_copy - 1], e->dest->cuid);
536 /* Now generate the reg_moves, attaching relevant uses to them. */
537 SCHED_NREG_MOVES (u) = nreg_moves;
538 old_reg = prev_reg = copy_rtx (SET_DEST (single_set (u->insn)));
539 last_reg_move = u->insn;
541 for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
544 rtx new_reg = gen_reg_rtx (GET_MODE (prev_reg));
545 rtx reg_move = gen_move_insn (new_reg, prev_reg);
547 add_insn_before (reg_move, last_reg_move);
548 last_reg_move = reg_move;
550 if (!SCHED_FIRST_REG_MOVE (u))
551 SCHED_FIRST_REG_MOVE (u) = reg_move;
553 EXECUTE_IF_SET_IN_SBITMAP (uses_of_defs[i_reg_move], 0, i_use,
555 struct undo_replace_buff_elem *rep;
557 rep = (struct undo_replace_buff_elem *)
558 xcalloc (1, sizeof (struct undo_replace_buff_elem));
559 rep->insn = g->nodes[i_use].insn;
560 rep->orig_reg = old_reg;
561 rep->new_reg = new_reg;
563 if (! reg_move_replaces)
564 reg_move_replaces = rep;
567 rep->next = reg_move_replaces;
568 reg_move_replaces = rep;
571 replace_rtx (g->nodes[i_use].insn, old_reg, new_reg);
577 return reg_move_replaces;
580 /* We call this when we want to undo the SMS schedule for a given loop.
581 One of the things that we do is to delete the register moves generated
582 for the sake of SMS; this function deletes the register move instructions
583 recorded in the undo buffer. */
585 undo_generate_reg_moves (partial_schedule_ptr ps,
586 struct undo_replace_buff_elem *reg_move_replaces)
590 for (i = 0; i < ps->g->num_nodes; i++)
592 ddg_node_ptr u = &ps->g->nodes[i];
594 rtx crr = SCHED_FIRST_REG_MOVE (u);
596 for (j = 0; j < SCHED_NREG_MOVES (u); j++)
598 prev = PREV_INSN (crr);
604 while (reg_move_replaces)
606 struct undo_replace_buff_elem *rep = reg_move_replaces;
608 reg_move_replaces = reg_move_replaces->next;
609 replace_rtx (rep->insn, rep->new_reg, rep->orig_reg);
613 /* Free memory allocated for the undo buffer. */
615 free_undo_replace_buff (struct undo_replace_buff_elem *reg_move_replaces)
618 while (reg_move_replaces)
620 struct undo_replace_buff_elem *rep = reg_move_replaces;
622 reg_move_replaces = reg_move_replaces->next;
627 /* Bump the SCHED_TIMEs of all nodes to start from zero. Set the values
628 of SCHED_ROW and SCHED_STAGE. */
630 normalize_sched_times (partial_schedule_ptr ps)
634 int amount = PS_MIN_CYCLE (ps);
637 /* Don't include the closing branch assuming that it is the last node. */
638 for (i = 0; i < g->num_nodes - 1; i++)
640 ddg_node_ptr u = &g->nodes[i];
641 int normalized_time = SCHED_TIME (u) - amount;
643 if (normalized_time < 0)
646 SCHED_TIME (u) = normalized_time;
647 SCHED_ROW (u) = normalized_time % ii;
648 SCHED_STAGE (u) = normalized_time / ii;
652 /* Set SCHED_COLUMN of each node according to its position in PS. */
654 set_columns_for_ps (partial_schedule_ptr ps)
658 for (row = 0; row < ps->ii; row++)
660 ps_insn_ptr cur_insn = ps->rows[row];
663 for (; cur_insn; cur_insn = cur_insn->next_in_row)
664 SCHED_COLUMN (cur_insn->node) = column++;
668 /* Permute the insns according to their order in PS, from row 0 to
669 row ii-1, and position them right before LAST. This schedules
670 the insns of the loop kernel. */
672 permute_partial_schedule (partial_schedule_ptr ps, rtx last)
678 for (row = 0; row < ii ; row++)
679 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
680 if (PREV_INSN (last) != ps_ij->node->insn)
681 reorder_insns_nobb (ps_ij->node->first_note, ps_ij->node->insn,
685 /* As part of undoing SMS we return to the original ordering of the
686 instructions inside the loop kernel. Given the partial schedule PS, this
687 function returns the ordering of the instruction according to their CUID
688 in the DDG (PS->G), which is the original order of the instruction before
691 undo_permute_partial_schedule (partial_schedule_ptr ps, rtx last)
695 for (i = 0 ; i < ps->g->num_nodes; i++)
696 if (last == ps->g->nodes[i].insn
697 || last == ps->g->nodes[i].first_note)
699 else if (PREV_INSN (last) != ps->g->nodes[i].insn)
700 reorder_insns_nobb (ps->g->nodes[i].first_note, ps->g->nodes[i].insn,
704 /* Used to generate the prologue & epilogue. Duplicate the subset of
705 nodes whose stages are between FROM_STAGE and TO_STAGE (inclusive
706 of both), together with a prefix/suffix of their reg_moves. */
708 duplicate_insns_of_cycles (partial_schedule_ptr ps, int from_stage,
709 int to_stage, int for_prolog)
714 for (row = 0; row < ps->ii; row++)
715 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
717 ddg_node_ptr u_node = ps_ij->node;
719 rtx reg_move = NULL_RTX;
723 /* SCHED_STAGE (u_node) >= from_stage == 0. Generate increasing
724 number of reg_moves starting with the second occurrence of
725 u_node, which is generated if its SCHED_STAGE <= to_stage. */
726 i_reg_moves = to_stage - SCHED_STAGE (u_node) + 1;
727 i_reg_moves = MAX (i_reg_moves, 0);
728 i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));
730 /* The reg_moves start from the *first* reg_move backwards. */
733 reg_move = SCHED_FIRST_REG_MOVE (u_node);
734 for (j = 1; j < i_reg_moves; j++)
735 reg_move = PREV_INSN (reg_move);
738 else /* It's for the epilog. */
740 /* SCHED_STAGE (u_node) <= to_stage. Generate all reg_moves,
741 starting to decrease one stage after u_node no longer occurs;
742 that is, generate all reg_moves until
743 SCHED_STAGE (u_node) == from_stage - 1. */
744 i_reg_moves = SCHED_NREG_MOVES (u_node)
745 - (from_stage - SCHED_STAGE (u_node) - 1);
746 i_reg_moves = MAX (i_reg_moves, 0);
747 i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));
749 /* The reg_moves start from the *last* reg_move forwards. */
752 reg_move = SCHED_FIRST_REG_MOVE (u_node);
753 for (j = 1; j < SCHED_NREG_MOVES (u_node); j++)
754 reg_move = PREV_INSN (reg_move);
758 for (j = 0; j < i_reg_moves; j++, reg_move = NEXT_INSN (reg_move))
759 emit_insn (copy_rtx (PATTERN (reg_move)));
760 if (SCHED_STAGE (u_node) >= from_stage
761 && SCHED_STAGE (u_node) <= to_stage)
762 duplicate_insn_chain (u_node->first_note, u_node->insn);
767 /* Generate the instructions (including reg_moves) for prolog & epilog. */
769 generate_prolog_epilog (partial_schedule_ptr ps, struct loop * loop, rtx count_reg)
772 int last_stage = PS_STAGE_COUNT (ps) - 1;
775 /* Generate the prolog, inserting its insns on the loop-entry edge. */
779 /* Generate a subtract instruction at the beginning of the prolog to
780 adjust the loop count by STAGE_COUNT. */
781 emit_insn (gen_sub2_insn (count_reg, GEN_INT (last_stage)));
783 for (i = 0; i < last_stage; i++)
784 duplicate_insns_of_cycles (ps, 0, i, 1);
786 /* Put the prolog , on the one and only entry edge. */
787 e = loop_preheader_edge (loop);
788 loop_split_edge_with(e , get_insns());
792 /* Generate the epilog, inserting its insns on the loop-exit edge. */
795 for (i = 0; i < last_stage; i++)
796 duplicate_insns_of_cycles (ps, i + 1, last_stage, 0);
798 /* Put the epilogue on the one and only one exit edge. */
799 gcc_assert (loop->single_exit);
800 e = loop->single_exit;
801 loop_split_edge_with(e , get_insns());
805 /* Return the line note insn preceding INSN, for debugging. Taken from
808 find_line_note (rtx insn)
810 for (; insn; insn = PREV_INSN (insn))
812 && NOTE_LINE_NUMBER (insn) >= 0)
818 /* Return true if all the BBs of the loop are empty except the
821 loop_single_full_bb_p (struct loop *loop)
824 basic_block *bbs = get_loop_body (loop);
826 for (i = 0; i < loop->num_nodes ; i++)
829 bool empty_bb = true;
831 if (bbs[i] == loop->header)
834 /* Make sure that basic blocks other than the header
835 have only notes labels or jumps. */
836 get_block_head_tail (bbs[i]->index, &head, &tail);
837 for (; head != NEXT_INSN (tail); head = NEXT_INSN (head))
839 if (NOTE_P (head) || LABEL_P (head)
840 || (INSN_P (head) && JUMP_P (head)))
856 /* A simple loop from SMS point of view; it is a loop that is composed of
857 either a single basic block or two BBs - a header and a latch. */
858 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
859 && (EDGE_COUNT (loop->latch->preds) == 1) \
860 && (EDGE_COUNT (loop->latch->succs) == 1))
862 /* Return true if the loop is in its canonical form and false if not.
863 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
865 loop_canon_p (struct loop *loop, FILE *dump_file)
868 if (loop->inner || ! loop->outer)
871 if (!loop->single_exit)
875 rtx line_note = find_line_note (BB_END (loop->header));
877 fprintf (dump_file, "SMS loop many exits ");
880 expanded_location xloc;
881 NOTE_EXPANDED_LOCATION (xloc, line_note);
882 fprintf (stats_file, " %s %d (file, line)\n",
883 xloc.file, xloc.line);
889 if (! SIMPLE_SMS_LOOP_P (loop) && ! loop_single_full_bb_p (loop))
893 rtx line_note = find_line_note (BB_END (loop->header));
895 fprintf (dump_file, "SMS loop many BBs. ");
898 expanded_location xloc;
899 NOTE_EXPANDED_LOCATION (xloc, line_note);
900 fprintf (stats_file, " %s %d (file, line)\n",
901 xloc.file, xloc.line);
910 /* If there are more than one entry for the loop,
911 make it one by splitting the first entry edge and
912 redirecting the others to the new BB. */
914 canon_loop (struct loop *loop)
919 /* Avoid annoying special cases of edges going to exit
921 FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR->preds)
922 if ((e->flags & EDGE_FALLTHRU) && (EDGE_COUNT (e->src->succs) > 1))
923 loop_split_edge_with (e, NULL_RTX);
925 if (loop->latch == loop->header
926 || EDGE_COUNT (loop->latch->succs) > 1)
928 FOR_EACH_EDGE (e, i, loop->header->preds)
929 if (e->src == loop->latch)
931 loop_split_edge_with (e, NULL_RTX);
935 /* Build the loop information without loop
936 canonization, the loop canonization will
937 be performed if the loop is SMSable. */
938 static struct loops *
939 build_loops_structure (FILE *dumpfile)
941 struct loops *loops = xcalloc (1, sizeof (struct loops));
943 /* Find the loops. */
945 if (flow_loops_find (loops) <= 1)
948 flow_loops_free (loops);
954 /* Not going to update these. */
955 free (loops->cfg.rc_order);
956 loops->cfg.rc_order = NULL;
957 free (loops->cfg.dfs_order);
958 loops->cfg.dfs_order = NULL;
960 create_preheaders (loops, CP_SIMPLE_PREHEADERS);
961 mark_single_exit_loops (loops);
963 flow_loops_dump (loops, dumpfile, NULL, 1);
965 #ifdef ENABLE_CHECKING
966 verify_dominators (CDI_DOMINATORS);
967 verify_loop_structure (loops);
973 /* Main entry point, perform SMS scheduling on the loops of the function
974 that consist of single basic blocks. */
976 sms_schedule (FILE *dump_file)
978 static int passes = 0;
983 unsigned i,num_loops;
984 partial_schedule_ptr ps;
987 basic_block bb = NULL;
988 /* vars to the versioning only if needed*/
990 basic_block condition_bb = NULL;
992 gcov_type trip_count = 0;
994 if (! (loops = build_loops_structure (dump_file)))
995 return; /* There is no loops to schedule. */
998 stats_file = dump_file;
1000 /* Initialize issue_rate. */
1001 if (targetm.sched.issue_rate)
1003 int temp = reload_completed;
1005 reload_completed = 1;
1006 issue_rate = (*targetm.sched.issue_rate) ();
1007 reload_completed = temp;
1012 /* Initialize the scheduler. */
1013 current_sched_info = &sms_sched_info;
1016 /* Init Data Flow analysis, to be used in interloop dep calculation. */
1018 df_analyze (df, 0, DF_ALL);
1020 /* Allocate memory to hold the DDG array one entry for each loop.
1021 We use loop->num as index into this array. */
1022 g_arr = xcalloc (loops->num, sizeof (ddg_ptr));
1025 /* Build DDGs for all the relevant loops and hold them in G_ARR
1026 indexed by the loop index. */
1027 for (i = 0; i < loops->num; i++)
1030 rtx count_reg, comp;
1031 struct loop *loop = loops->parray[i];
1033 /* For debugging. */
1034 if ((passes++ > MAX_SMS_LOOP_NUMBER) && (MAX_SMS_LOOP_NUMBER != -1))
1037 fprintf (dump_file, "SMS reached MAX_PASSES... \n");
1042 if (! loop_canon_p (loop, dump_file))
1045 if (! loop_single_full_bb_p (loop))
1050 get_block_head_tail (bb->index, &head, &tail);
1051 latch_edge = loop_latch_edge (loop);
1052 gcc_assert (loop->single_exit);
1053 if (loop->single_exit->count)
1054 trip_count = latch_edge->count / loop->single_exit->count;
1056 /* Perfrom SMS only on loops that their average count is above threshold. */
1058 if ( latch_edge->count
1059 && (latch_edge->count < loop->single_exit->count * SMS_LOOP_AVERAGE_COUNT_THRESHOLD))
1063 rtx line_note = find_line_note (tail);
1067 expanded_location xloc;
1068 NOTE_EXPANDED_LOCATION (xloc, line_note);
1069 fprintf (stats_file, "SMS bb %s %d (file, line)\n",
1070 xloc.file, xloc.line);
1072 fprintf (stats_file, "SMS single-bb-loop\n");
1073 if (profile_info && flag_branch_probabilities)
1075 fprintf (stats_file, "SMS loop-count ");
1076 fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
1077 (HOST_WIDEST_INT) bb->count);
1078 fprintf (stats_file, "\n");
1079 fprintf (stats_file, "SMS trip-count ");
1080 fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
1081 (HOST_WIDEST_INT) trip_count);
1082 fprintf (stats_file, "\n");
1083 fprintf (stats_file, "SMS profile-sum-max ");
1084 fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
1085 (HOST_WIDEST_INT) profile_info->sum_max);
1086 fprintf (stats_file, "\n");
1092 /* Make sure this is a doloop. */
1093 if ( !(count_reg = doloop_register_get (tail, &comp)))
1096 /* Don't handle BBs with calls or barriers, or !single_set insns. */
1097 for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn))
1100 || (INSN_P (insn) && !JUMP_P (insn)
1101 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE))
1104 if (insn != NEXT_INSN (tail))
1109 fprintf (stats_file, "SMS loop-with-call\n");
1110 else if (BARRIER_P (insn))
1111 fprintf (stats_file, "SMS loop-with-barrier\n");
1113 fprintf (stats_file, "SMS loop-with-not-single-set\n");
1114 print_rtl_single (stats_file, insn);
1120 if (! (g = create_ddg (bb, df, 0)))
1123 fprintf (stats_file, "SMS doloop\n");
1130 /* Release Data Flow analysis data structures. */
1133 /* We don't want to perform SMS on new loops - created by versioning. */
1134 num_loops = loops->num;
1135 /* Go over the built DDGs and perfrom SMS for each one of them. */
1136 for (i = 0; i < num_loops; i++)
1139 rtx count_reg, count_init, comp;
1141 unsigned stage_count = 0;
1142 HOST_WIDEST_INT loop_count = 0;
1143 struct loop *loop = loops->parray[i];
1145 if (! (g = g_arr[i]))
1149 print_ddg (dump_file, g);
1151 get_block_head_tail (loop->header->index, &head, &tail);
1153 latch_edge = loop_latch_edge (loop);
1154 gcc_assert (loop->single_exit);
1155 if (loop->single_exit->count)
1156 trip_count = latch_edge->count / loop->single_exit->count;
1160 rtx line_note = find_line_note (tail);
1164 expanded_location xloc;
1165 NOTE_EXPANDED_LOCATION (xloc, line_note);
1166 fprintf (stats_file, "SMS bb %s %d (file, line)\n",
1167 xloc.file, xloc.line);
1169 fprintf (stats_file, "SMS single-bb-loop\n");
1170 if (profile_info && flag_branch_probabilities)
1172 fprintf (stats_file, "SMS loop-count ");
1173 fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
1174 (HOST_WIDEST_INT) bb->count);
1175 fprintf (stats_file, "\n");
1176 fprintf (stats_file, "SMS profile-sum-max ");
1177 fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
1178 (HOST_WIDEST_INT) profile_info->sum_max);
1179 fprintf (stats_file, "\n");
1181 fprintf (stats_file, "SMS doloop\n");
1182 fprintf (stats_file, "SMS built-ddg %d\n", g->num_nodes);
1183 fprintf (stats_file, "SMS num-loads %d\n", g->num_loads);
1184 fprintf (stats_file, "SMS num-stores %d\n", g->num_stores);
1188 /* In case of th loop have doloop register it gets special
1190 count_init = NULL_RTX;
1191 if ((count_reg = doloop_register_get (tail, &comp)))
1193 basic_block pre_header;
1195 pre_header = loop_preheader_edge (loop)->src;
1196 count_init = const_iteration_count (count_reg, pre_header,
1199 gcc_assert (count_reg);
1201 if (stats_file && count_init)
1203 fprintf (stats_file, "SMS const-doloop ");
1204 fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
1206 fprintf (stats_file, "\n");
1209 node_order = (int *) xmalloc (sizeof (int) * g->num_nodes);
1211 mii = 1; /* Need to pass some estimate of mii. */
1212 rec_mii = sms_order_nodes (g, mii, node_order);
1213 mii = MAX (res_MII (g), rec_mii);
1214 maxii = (calculate_maxii (g) * SMS_MAX_II_FACTOR) / 100;
1217 fprintf (stats_file, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1218 rec_mii, mii, maxii);
1220 /* After sms_order_nodes and before sms_schedule_by_order, to copy over
1222 set_node_sched_params (g);
1224 ps = sms_schedule_by_order (g, mii, maxii, node_order, dump_file);
1227 stage_count = PS_STAGE_COUNT (ps);
1229 /* Stage count of 1 means that there is no interleaving between
1230 iterations, let the scheduling passes do the job. */
1232 || (count_init && (loop_count <= stage_count))
1233 || (flag_branch_probabilities && (trip_count <= stage_count)))
1237 fprintf (dump_file, "SMS failed... \n");
1238 fprintf (dump_file, "SMS sched-failed (stage-count=%d, loop-count=", stage_count);
1239 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, loop_count);
1240 fprintf (dump_file, ", trip-count=");
1241 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, trip_count);
1242 fprintf (dump_file, ")\n");
1248 int orig_cycles = kernel_number_of_cycles (BB_HEAD (g->bb), BB_END (g->bb));
1250 struct undo_replace_buff_elem *reg_move_replaces;
1254 fprintf (stats_file,
1255 "SMS succeeded %d %d (with ii, sc)\n", ps->ii,
1257 print_partial_schedule (ps, stats_file);
1258 fprintf (stats_file,
1259 "SMS Branch (%d) will later be scheduled at cycle %d.\n",
1260 g->closing_branch->cuid, PS_MIN_CYCLE (ps) - 1);
1263 /* Set the stage boundaries. If the DDG is built with closing_branch_deps,
1264 the closing_branch was scheduled and should appear in the last (ii-1)
1265 row. Otherwise, we are free to schedule the branch, and we let nodes
1266 that were scheduled at the first PS_MIN_CYCLE cycle appear in the first
1267 row; this should reduce stage_count to minimum. */
1268 normalize_sched_times (ps);
1269 rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
1270 set_columns_for_ps (ps);
1272 /* Generate the kernel just to be able to measure its cycles. */
1273 permute_partial_schedule (ps, g->closing_branch->first_note);
1274 reg_move_replaces = generate_reg_moves (ps);
1276 /* Get the number of cycles the new kernel expect to execute in. */
1277 new_cycles = kernel_number_of_cycles (BB_HEAD (g->bb), BB_END (g->bb));
1279 /* Get back to the original loop so we can do loop versioning. */
1280 undo_permute_partial_schedule (ps, g->closing_branch->first_note);
1281 if (reg_move_replaces)
1282 undo_generate_reg_moves (ps, reg_move_replaces);
1284 if ( new_cycles >= orig_cycles)
1286 /* SMS is not profitable so undo the permutation and reg move generation
1287 and return the kernel to its original state. */
1289 fprintf (dump_file, "Undoing SMS becuase it is not profitable.\n");
1296 /* case the BCT count is not known , Do loop-versioning */
1297 if (count_reg && ! count_init)
1299 rtx comp_rtx = gen_rtx_fmt_ee (GT, VOIDmode, count_reg,
1300 GEN_INT(stage_count));
1302 nloop = loop_version (loops, loop, comp_rtx, &condition_bb);
1305 /* Set new iteration count of loop kernel. */
1306 if (count_reg && count_init)
1307 SET_SRC (single_set (count_init)) = GEN_INT (loop_count
1310 /* Now apply the scheduled kernel to the RTL of the loop. */
1311 permute_partial_schedule (ps, g->closing_branch->first_note);
1313 /* Mark this loop as software pipelined so the later
1314 scheduling passes doesn't touch it. */
1315 if (! flag_resched_modulo_sched)
1316 g->bb->flags |= BB_DISABLE_SCHEDULE;
1317 /* The life-info is not valid any more. */
1318 g->bb->flags |= BB_DIRTY;
1320 reg_move_replaces = generate_reg_moves (ps);
1322 print_node_sched_params (dump_file, g->num_nodes);
1323 /* Generate prolog and epilog. */
1324 if (count_reg && !count_init)
1325 generate_prolog_epilog (ps, loop, count_reg);
1327 generate_prolog_epilog (ps, loop, NULL_RTX);
1329 free_undo_replace_buff (reg_move_replaces);
1332 free_partial_schedule (ps);
1333 free (node_sched_params);
1338 /* Release scheduler data, needed until now because of DFA. */
1340 loop_optimizer_finalize (loops, dump_file);
1343 /* The SMS scheduling algorithm itself
1344 -----------------------------------
1345 Input: 'O' an ordered list of insns of a loop.
1346 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1348 'Q' is the empty Set
1349 'PS' is the partial schedule; it holds the currently scheduled nodes with
1351 'PSP' previously scheduled predecessors.
1352 'PSS' previously scheduled successors.
1353 't(u)' the cycle where u is scheduled.
1354 'l(u)' is the latency of u.
1355 'd(v,u)' is the dependence distance from v to u.
1356 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1357 the node ordering phase.
1358 'check_hardware_resources_conflicts(u, PS, c)'
1359 run a trace around cycle/slot through DFA model
1360 to check resource conflicts involving instruction u
1361 at cycle c given the partial schedule PS.
1362 'add_to_partial_schedule_at_time(u, PS, c)'
1363 Add the node/instruction u to the partial schedule
1365 'calculate_register_pressure(PS)'
1366 Given a schedule of instructions, calculate the register
1367 pressure it implies. One implementation could be the
1368 maximum number of overlapping live ranges.
1369 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1370 registers available in the hardware.
1374 3. for each node u in O in pre-computed order
1375 4. if (PSP(u) != Q && PSS(u) == Q) then
1376 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1377 6. start = Early_start; end = Early_start + II - 1; step = 1
1378 11. else if (PSP(u) == Q && PSS(u) != Q) then
1379 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1380 13. start = Late_start; end = Late_start - II + 1; step = -1
1381 14. else if (PSP(u) != Q && PSS(u) != Q) then
1382 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1383 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1384 17. start = Early_start;
1385 18. end = min(Early_start + II - 1 , Late_start);
1387 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1388 21. start = ASAP(u); end = start + II - 1; step = 1
1392 24. for (c = start ; c != end ; c += step)
1393 25. if check_hardware_resources_conflicts(u, PS, c) then
1394 26. add_to_partial_schedule_at_time(u, PS, c)
1399 31. if (success == false) then
1401 33. if (II > maxII) then
1402 34. finish - failed to schedule
1407 39. if (calculate_register_pressure(PS) > maxRP) then
1410 42. compute epilogue & prologue
1411 43. finish - succeeded to schedule
1414 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1415 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1416 set to 0 to save compile time. */
1417 #define DFA_HISTORY SMS_DFA_HISTORY
1419 /* Given the partial schedule PS, this function calculates and returns the
1420 cycles in which we can schedule the node with the given index I.
1421 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1422 noticed that there are several cases in which we fail to SMS the loop
1423 because the sched window of a node is empty due to tight data-deps. In
1424 such cases we want to unschedule some of the predecessors/successors
1425 until we get non-empty scheduling window. It returns -1 if the
1426 scheduling window is empty and zero otherwise. */
1429 get_sched_window (partial_schedule_ptr ps, int *nodes_order, int i,
1430 sbitmap sched_nodes, int ii, int *start_p, int *step_p, int *end_p)
1432 int start, step, end;
1434 int u = nodes_order [i];
1435 ddg_node_ptr u_node = &ps->g->nodes[u];
1436 sbitmap psp = sbitmap_alloc (ps->g->num_nodes);
1437 sbitmap pss = sbitmap_alloc (ps->g->num_nodes);
1438 sbitmap u_node_preds = NODE_PREDECESSORS (u_node);
1439 sbitmap u_node_succs = NODE_SUCCESSORS (u_node);
1443 /* 1. compute sched window for u (start, end, step). */
1446 psp_not_empty = sbitmap_a_and_b_cg (psp, u_node_preds, sched_nodes);
1447 pss_not_empty = sbitmap_a_and_b_cg (pss, u_node_succs, sched_nodes);
1449 if (psp_not_empty && !pss_not_empty)
1451 int early_start = INT_MIN;
1454 for (e = u_node->in; e != 0; e = e->next_in)
1456 ddg_node_ptr v_node = e->src;
1457 if (TEST_BIT (sched_nodes, v_node->cuid))
1459 int node_st = SCHED_TIME (v_node)
1460 + e->latency - (e->distance * ii);
1462 early_start = MAX (early_start, node_st);
1464 if (e->data_type == MEM_DEP)
1465 end = MIN (end, SCHED_TIME (v_node) + ii - 1);
1468 start = early_start;
1469 end = MIN (end, early_start + ii);
1473 else if (!psp_not_empty && pss_not_empty)
1475 int late_start = INT_MAX;
1478 for (e = u_node->out; e != 0; e = e->next_out)
1480 ddg_node_ptr v_node = e->dest;
1481 if (TEST_BIT (sched_nodes, v_node->cuid))
1483 late_start = MIN (late_start,
1484 SCHED_TIME (v_node) - e->latency
1485 + (e->distance * ii));
1486 if (e->data_type == MEM_DEP)
1487 end = MAX (end, SCHED_TIME (v_node) - ii + 1);
1491 end = MAX (end, late_start - ii);
1495 else if (psp_not_empty && pss_not_empty)
1497 int early_start = INT_MIN;
1498 int late_start = INT_MAX;
1502 for (e = u_node->in; e != 0; e = e->next_in)
1504 ddg_node_ptr v_node = e->src;
1506 if (TEST_BIT (sched_nodes, v_node->cuid))
1508 early_start = MAX (early_start,
1509 SCHED_TIME (v_node) + e->latency
1510 - (e->distance * ii));
1511 if (e->data_type == MEM_DEP)
1512 end = MIN (end, SCHED_TIME (v_node) + ii - 1);
1515 for (e = u_node->out; e != 0; e = e->next_out)
1517 ddg_node_ptr v_node = e->dest;
1519 if (TEST_BIT (sched_nodes, v_node->cuid))
1521 late_start = MIN (late_start,
1522 SCHED_TIME (v_node) - e->latency
1523 + (e->distance * ii));
1524 if (e->data_type == MEM_DEP)
1525 start = MAX (start, SCHED_TIME (v_node) - ii + 1);
1528 start = MAX (start, early_start);
1529 end = MIN (end, MIN (early_start + ii, late_start + 1));
1532 else /* psp is empty && pss is empty. */
1534 start = SCHED_ASAP (u_node);
1545 if ((start >= end && step == 1) || (start <= end && step == -1))
1551 /* This function implements the scheduling algorithm for SMS according to the
1553 static partial_schedule_ptr
1554 sms_schedule_by_order (ddg_ptr g, int mii, int maxii, int *nodes_order, FILE *dump_file)
1558 int try_again_with_larger_ii = true;
1559 int num_nodes = g->num_nodes;
1561 int start, end, step; /* Place together into one struct? */
1562 sbitmap sched_nodes = sbitmap_alloc (num_nodes);
1563 sbitmap must_precede = sbitmap_alloc (num_nodes);
1564 sbitmap must_follow = sbitmap_alloc (num_nodes);
1565 sbitmap tobe_scheduled = sbitmap_alloc (num_nodes);
1567 partial_schedule_ptr ps = create_partial_schedule (ii, g, DFA_HISTORY);
1569 sbitmap_ones (tobe_scheduled);
1570 sbitmap_zero (sched_nodes);
1572 while ((! sbitmap_equal (tobe_scheduled, sched_nodes)
1573 || try_again_with_larger_ii ) && ii < maxii)
1576 bool unscheduled_nodes = false;
1579 fprintf(dump_file, "Starting with ii=%d\n", ii);
1580 if (try_again_with_larger_ii)
1582 try_again_with_larger_ii = false;
1583 sbitmap_zero (sched_nodes);
1586 for (i = 0; i < num_nodes; i++)
1588 int u = nodes_order[i];
1589 ddg_node_ptr u_node = &ps->g->nodes[u];
1590 rtx insn = u_node->insn;
1594 RESET_BIT (tobe_scheduled, u);
1598 if (JUMP_P (insn)) /* Closing branch handled later. */
1600 RESET_BIT (tobe_scheduled, u);
1604 if (TEST_BIT (sched_nodes, u))
1607 /* Try to get non-empty scheduling window. */
1609 while (get_sched_window (ps, nodes_order, i, sched_nodes, ii, &start, &step, &end) < 0
1612 unscheduled_nodes = true;
1613 if (TEST_BIT (NODE_PREDECESSORS (u_node), nodes_order[j - 1])
1614 || TEST_BIT (NODE_SUCCESSORS (u_node), nodes_order[j - 1]))
1616 ps_unschedule_node (ps, &ps->g->nodes[nodes_order[j - 1]]);
1617 RESET_BIT (sched_nodes, nodes_order [j - 1]);
1623 /* ??? Try backtracking instead of immediately ii++? */
1625 try_again_with_larger_ii = true;
1626 reset_partial_schedule (ps, ii);
1629 /* 2. Try scheduling u in window. */
1631 fprintf(dump_file, "Trying to schedule node %d in (%d .. %d) step %d\n",
1632 u, start, end, step);
1634 /* use must_follow & must_precede bitmaps to determine order
1635 of nodes within the cycle. */
1636 sbitmap_zero (must_precede);
1637 sbitmap_zero (must_follow);
1638 for (e = u_node->in; e != 0; e = e->next_in)
1639 if (TEST_BIT (sched_nodes, e->src->cuid)
1640 && e->latency == (ii * e->distance)
1641 && start == SCHED_TIME (e->src))
1642 SET_BIT (must_precede, e->src->cuid);
1644 for (e = u_node->out; e != 0; e = e->next_out)
1645 if (TEST_BIT (sched_nodes, e->dest->cuid)
1646 && e->latency == (ii * e->distance)
1647 && end == SCHED_TIME (e->dest))
1648 SET_BIT (must_follow, e->dest->cuid);
1651 if ((step > 0 && start < end) || (step < 0 && start > end))
1652 for (c = start; c != end; c += step)
1656 psi = ps_add_node_check_conflicts (ps, u_node, c,
1662 SCHED_TIME (u_node) = c;
1663 SET_BIT (sched_nodes, u);
1666 fprintf(dump_file, "Schedule in %d\n", c);
1672 /* ??? Try backtracking instead of immediately ii++? */
1674 try_again_with_larger_ii = true;
1675 reset_partial_schedule (ps, ii);
1678 if (unscheduled_nodes)
1681 /* ??? If (success), check register pressure estimates. */
1682 } /* Continue with next node. */
1683 } /* While try_again_with_larger_ii. */
1685 sbitmap_free (sched_nodes);
1689 free_partial_schedule (ps);
1696 /* This page implements the algorithm for ordering the nodes of a DDG
1697 for modulo scheduling, activated through the
1698 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
1700 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
1701 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
1702 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
1703 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
1704 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
1705 #define DEPTH(x) (ASAP ((x)))
1707 typedef struct node_order_params * nopa;
1709 static void order_nodes_of_sccs (ddg_all_sccs_ptr, int * result);
1710 static int order_nodes_in_scc (ddg_ptr, sbitmap, sbitmap, int*, int);
1711 static nopa calculate_order_params (ddg_ptr, int mii);
1712 static int find_max_asap (ddg_ptr, sbitmap);
1713 static int find_max_hv_min_mob (ddg_ptr, sbitmap);
1714 static int find_max_dv_min_mob (ddg_ptr, sbitmap);
1716 enum sms_direction {BOTTOMUP, TOPDOWN};
1718 struct node_order_params
1725 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
1727 check_nodes_order (int *node_order, int num_nodes)
1730 sbitmap tmp = sbitmap_alloc (num_nodes);
1734 for (i = 0; i < num_nodes; i++)
1736 int u = node_order[i];
1738 if (u >= num_nodes || u < 0 || TEST_BIT (tmp, u))
1747 /* Order the nodes of G for scheduling and pass the result in
1748 NODE_ORDER. Also set aux.count of each node to ASAP.
1749 Return the recMII for the given DDG. */
1751 sms_order_nodes (ddg_ptr g, int mii, int * node_order)
1755 ddg_all_sccs_ptr sccs = create_ddg_all_sccs (g);
1757 nopa nops = calculate_order_params (g, mii);
1759 order_nodes_of_sccs (sccs, node_order);
1761 if (sccs->num_sccs > 0)
1762 /* First SCC has the largest recurrence_length. */
1763 rec_mii = sccs->sccs[0]->recurrence_length;
1765 /* Save ASAP before destroying node_order_params. */
1766 for (i = 0; i < g->num_nodes; i++)
1768 ddg_node_ptr v = &g->nodes[i];
1769 v->aux.count = ASAP (v);
1773 free_ddg_all_sccs (sccs);
1774 check_nodes_order (node_order, g->num_nodes);
1780 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs, int * node_order)
1783 ddg_ptr g = all_sccs->ddg;
1784 int num_nodes = g->num_nodes;
1785 sbitmap prev_sccs = sbitmap_alloc (num_nodes);
1786 sbitmap on_path = sbitmap_alloc (num_nodes);
1787 sbitmap tmp = sbitmap_alloc (num_nodes);
1788 sbitmap ones = sbitmap_alloc (num_nodes);
1790 sbitmap_zero (prev_sccs);
1791 sbitmap_ones (ones);
1793 /* Perfrom the node ordering starting from the SCC with the highest recMII.
1794 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
1795 for (i = 0; i < all_sccs->num_sccs; i++)
1797 ddg_scc_ptr scc = all_sccs->sccs[i];
1799 /* Add nodes on paths from previous SCCs to the current SCC. */
1800 find_nodes_on_paths (on_path, g, prev_sccs, scc->nodes);
1801 sbitmap_a_or_b (tmp, scc->nodes, on_path);
1803 /* Add nodes on paths from the current SCC to previous SCCs. */
1804 find_nodes_on_paths (on_path, g, scc->nodes, prev_sccs);
1805 sbitmap_a_or_b (tmp, tmp, on_path);
1807 /* Remove nodes of previous SCCs from current extended SCC. */
1808 sbitmap_difference (tmp, tmp, prev_sccs);
1810 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
1811 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
1814 /* Handle the remaining nodes that do not belong to any scc. Each call
1815 to order_nodes_in_scc handles a single connected component. */
1816 while (pos < g->num_nodes)
1818 sbitmap_difference (tmp, ones, prev_sccs);
1819 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
1821 sbitmap_free (prev_sccs);
1822 sbitmap_free (on_path);
1824 sbitmap_free (ones);
1827 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
1828 static struct node_order_params *
1829 calculate_order_params (ddg_ptr g, int mii ATTRIBUTE_UNUSED)
1833 int num_nodes = g->num_nodes;
1835 /* Allocate a place to hold ordering params for each node in the DDG. */
1836 nopa node_order_params_arr;
1838 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
1839 node_order_params_arr = (nopa) xcalloc (num_nodes,
1840 sizeof (struct node_order_params));
1842 /* Set the aux pointer of each node to point to its order_params structure. */
1843 for (u = 0; u < num_nodes; u++)
1844 g->nodes[u].aux.info = &node_order_params_arr[u];
1846 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
1847 calculate ASAP, ALAP, mobility, distance, and height for each node
1848 in the dependence (direct acyclic) graph. */
1850 /* We assume that the nodes in the array are in topological order. */
1853 for (u = 0; u < num_nodes; u++)
1855 ddg_node_ptr u_node = &g->nodes[u];
1858 for (e = u_node->in; e; e = e->next_in)
1859 if (e->distance == 0)
1860 ASAP (u_node) = MAX (ASAP (u_node),
1861 ASAP (e->src) + e->latency);
1862 max_asap = MAX (max_asap, ASAP (u_node));
1865 for (u = num_nodes - 1; u > -1; u--)
1867 ddg_node_ptr u_node = &g->nodes[u];
1869 ALAP (u_node) = max_asap;
1870 HEIGHT (u_node) = 0;
1871 for (e = u_node->out; e; e = e->next_out)
1872 if (e->distance == 0)
1874 ALAP (u_node) = MIN (ALAP (u_node),
1875 ALAP (e->dest) - e->latency);
1876 HEIGHT (u_node) = MAX (HEIGHT (u_node),
1877 HEIGHT (e->dest) + e->latency);
1881 return node_order_params_arr;
1885 find_max_asap (ddg_ptr g, sbitmap nodes)
1891 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
1893 ddg_node_ptr u_node = &g->nodes[u];
1895 if (max_asap < ASAP (u_node))
1897 max_asap = ASAP (u_node);
1905 find_max_hv_min_mob (ddg_ptr g, sbitmap nodes)
1909 int min_mob = INT_MAX;
1912 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
1914 ddg_node_ptr u_node = &g->nodes[u];
1916 if (max_hv < HEIGHT (u_node))
1918 max_hv = HEIGHT (u_node);
1919 min_mob = MOB (u_node);
1922 else if ((max_hv == HEIGHT (u_node))
1923 && (min_mob > MOB (u_node)))
1925 min_mob = MOB (u_node);
1933 find_max_dv_min_mob (ddg_ptr g, sbitmap nodes)
1937 int min_mob = INT_MAX;
1940 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
1942 ddg_node_ptr u_node = &g->nodes[u];
1944 if (max_dv < DEPTH (u_node))
1946 max_dv = DEPTH (u_node);
1947 min_mob = MOB (u_node);
1950 else if ((max_dv == DEPTH (u_node))
1951 && (min_mob > MOB (u_node)))
1953 min_mob = MOB (u_node);
1960 /* Places the nodes of SCC into the NODE_ORDER array starting
1961 at position POS, according to the SMS ordering algorithm.
1962 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
1963 the NODE_ORDER array, starting from position zero. */
1965 order_nodes_in_scc (ddg_ptr g, sbitmap nodes_ordered, sbitmap scc,
1966 int * node_order, int pos)
1968 enum sms_direction dir;
1969 int num_nodes = g->num_nodes;
1970 sbitmap workset = sbitmap_alloc (num_nodes);
1971 sbitmap tmp = sbitmap_alloc (num_nodes);
1972 sbitmap zero_bitmap = sbitmap_alloc (num_nodes);
1973 sbitmap predecessors = sbitmap_alloc (num_nodes);
1974 sbitmap successors = sbitmap_alloc (num_nodes);
1976 sbitmap_zero (predecessors);
1977 find_predecessors (predecessors, g, nodes_ordered);
1979 sbitmap_zero (successors);
1980 find_successors (successors, g, nodes_ordered);
1983 if (sbitmap_a_and_b_cg (tmp, predecessors, scc))
1985 sbitmap_copy (workset, tmp);
1988 else if (sbitmap_a_and_b_cg (tmp, successors, scc))
1990 sbitmap_copy (workset, tmp);
1997 sbitmap_zero (workset);
1998 if ((u = find_max_asap (g, scc)) >= 0)
1999 SET_BIT (workset, u);
2003 sbitmap_zero (zero_bitmap);
2004 while (!sbitmap_equal (workset, zero_bitmap))
2007 ddg_node_ptr v_node;
2008 sbitmap v_node_preds;
2009 sbitmap v_node_succs;
2013 while (!sbitmap_equal (workset, zero_bitmap))
2015 v = find_max_hv_min_mob (g, workset);
2016 v_node = &g->nodes[v];
2017 node_order[pos++] = v;
2018 v_node_succs = NODE_SUCCESSORS (v_node);
2019 sbitmap_a_and_b (tmp, v_node_succs, scc);
2021 /* Don't consider the already ordered successors again. */
2022 sbitmap_difference (tmp, tmp, nodes_ordered);
2023 sbitmap_a_or_b (workset, workset, tmp);
2024 RESET_BIT (workset, v);
2025 SET_BIT (nodes_ordered, v);
2028 sbitmap_zero (predecessors);
2029 find_predecessors (predecessors, g, nodes_ordered);
2030 sbitmap_a_and_b (workset, predecessors, scc);
2034 while (!sbitmap_equal (workset, zero_bitmap))
2036 v = find_max_dv_min_mob (g, workset);
2037 v_node = &g->nodes[v];
2038 node_order[pos++] = v;
2039 v_node_preds = NODE_PREDECESSORS (v_node);
2040 sbitmap_a_and_b (tmp, v_node_preds, scc);
2042 /* Don't consider the already ordered predecessors again. */
2043 sbitmap_difference (tmp, tmp, nodes_ordered);
2044 sbitmap_a_or_b (workset, workset, tmp);
2045 RESET_BIT (workset, v);
2046 SET_BIT (nodes_ordered, v);
2049 sbitmap_zero (successors);
2050 find_successors (successors, g, nodes_ordered);
2051 sbitmap_a_and_b (workset, successors, scc);
2055 sbitmap_free (workset);
2056 sbitmap_free (zero_bitmap);
2057 sbitmap_free (predecessors);
2058 sbitmap_free (successors);
2063 /* This page contains functions for manipulating partial-schedules during
2064 modulo scheduling. */
2066 /* Create a partial schedule and allocate a memory to hold II rows. */
2067 partial_schedule_ptr
2068 create_partial_schedule (int ii, ddg_ptr g, int history)
2070 partial_schedule_ptr ps = (partial_schedule_ptr)
2071 xmalloc (sizeof (struct partial_schedule));
2072 ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
2074 ps->history = history;
2075 ps->min_cycle = INT_MAX;
2076 ps->max_cycle = INT_MIN;
2082 /* Free the PS_INSNs in rows array of the given partial schedule.
2083 ??? Consider caching the PS_INSN's. */
2085 free_ps_insns (partial_schedule_ptr ps)
2089 for (i = 0; i < ps->ii; i++)
2093 ps_insn_ptr ps_insn = ps->rows[i]->next_in_row;
2096 ps->rows[i] = ps_insn;
2102 /* Free all the memory allocated to the partial schedule. */
2104 free_partial_schedule (partial_schedule_ptr ps)
2113 /* Clear the rows array with its PS_INSNs, and create a new one with
2116 reset_partial_schedule (partial_schedule_ptr ps, int new_ii)
2121 if (new_ii == ps->ii)
2123 ps->rows = (ps_insn_ptr *) xrealloc (ps->rows, new_ii
2124 * sizeof (ps_insn_ptr));
2125 memset (ps->rows, 0, new_ii * sizeof (ps_insn_ptr));
2127 ps->min_cycle = INT_MAX;
2128 ps->max_cycle = INT_MIN;
2131 /* Prints the partial schedule as an ii rows array, for each rows
2132 print the ids of the insns in it. */
2134 print_partial_schedule (partial_schedule_ptr ps, FILE *dump)
2138 for (i = 0; i < ps->ii; i++)
2140 ps_insn_ptr ps_i = ps->rows[i];
2142 fprintf (dump, "\n[CYCLE %d ]: ", i);
2145 fprintf (dump, "%d, ",
2146 INSN_UID (ps_i->node->insn));
2147 ps_i = ps_i->next_in_row;
2152 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2154 create_ps_insn (ddg_node_ptr node, int rest_count, int cycle)
2156 ps_insn_ptr ps_i = xmalloc (sizeof (struct ps_insn));
2159 ps_i->next_in_row = NULL;
2160 ps_i->prev_in_row = NULL;
2161 ps_i->row_rest_count = rest_count;
2162 ps_i->cycle = cycle;
2168 /* Removes the given PS_INSN from the partial schedule. Returns false if the
2169 node is not found in the partial schedule, else returns true. */
2171 remove_node_from_ps (partial_schedule_ptr ps, ps_insn_ptr ps_i)
2178 row = SMODULO (ps_i->cycle, ps->ii);
2179 if (! ps_i->prev_in_row)
2181 if (ps_i != ps->rows[row])
2184 ps->rows[row] = ps_i->next_in_row;
2186 ps->rows[row]->prev_in_row = NULL;
2190 ps_i->prev_in_row->next_in_row = ps_i->next_in_row;
2191 if (ps_i->next_in_row)
2192 ps_i->next_in_row->prev_in_row = ps_i->prev_in_row;
2198 /* Unlike what literature describes for modulo scheduling (which focuses
2199 on VLIW machines) the order of the instructions inside a cycle is
2200 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2201 where the current instruction should go relative to the already
2202 scheduled instructions in the given cycle. Go over these
2203 instructions and find the first possible column to put it in. */
2205 ps_insn_find_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
2206 sbitmap must_precede, sbitmap must_follow)
2208 ps_insn_ptr next_ps_i;
2209 ps_insn_ptr first_must_follow = NULL;
2210 ps_insn_ptr last_must_precede = NULL;
2216 row = SMODULO (ps_i->cycle, ps->ii);
2218 /* Find the first must follow and the last must precede
2219 and insert the node immediately after the must precede
2220 but make sure that it there is no must follow after it. */
2221 for (next_ps_i = ps->rows[row];
2223 next_ps_i = next_ps_i->next_in_row)
2225 if (TEST_BIT (must_follow, next_ps_i->node->cuid)
2226 && ! first_must_follow)
2227 first_must_follow = next_ps_i;
2228 if (TEST_BIT (must_precede, next_ps_i->node->cuid))
2230 /* If we have already met a node that must follow, then
2231 there is no possible column. */
2232 if (first_must_follow)
2235 last_must_precede = next_ps_i;
2239 /* Now insert the node after INSERT_AFTER_PSI. */
2241 if (! last_must_precede)
2243 ps_i->next_in_row = ps->rows[row];
2244 ps_i->prev_in_row = NULL;
2245 if (ps_i->next_in_row)
2246 ps_i->next_in_row->prev_in_row = ps_i;
2247 ps->rows[row] = ps_i;
2251 ps_i->next_in_row = last_must_precede->next_in_row;
2252 last_must_precede->next_in_row = ps_i;
2253 ps_i->prev_in_row = last_must_precede;
2254 if (ps_i->next_in_row)
2255 ps_i->next_in_row->prev_in_row = ps_i;
2261 /* Advances the PS_INSN one column in its current row; returns false
2262 in failure and true in success. Bit N is set in MUST_FOLLOW if
2263 the node with cuid N must be come after the node pointed to by
2264 PS_I when scheduled in the same cycle. */
2266 ps_insn_advance_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
2267 sbitmap must_follow)
2269 ps_insn_ptr prev, next;
2271 ddg_node_ptr next_node;
2276 row = SMODULO (ps_i->cycle, ps->ii);
2278 if (! ps_i->next_in_row)
2281 next_node = ps_i->next_in_row->node;
2283 /* Check if next_in_row is dependent on ps_i, both having same sched
2284 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
2285 if (TEST_BIT (must_follow, next_node->cuid))
2288 /* Advance PS_I over its next_in_row in the doubly linked list. */
2289 prev = ps_i->prev_in_row;
2290 next = ps_i->next_in_row;
2292 if (ps_i == ps->rows[row])
2293 ps->rows[row] = next;
2295 ps_i->next_in_row = next->next_in_row;
2297 if (next->next_in_row)
2298 next->next_in_row->prev_in_row = ps_i;
2300 next->next_in_row = ps_i;
2301 ps_i->prev_in_row = next;
2303 next->prev_in_row = prev;
2305 prev->next_in_row = next;
2310 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
2311 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
2312 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
2313 before/after (respectively) the node pointed to by PS_I when scheduled
2314 in the same cycle. */
2316 add_node_to_ps (partial_schedule_ptr ps, ddg_node_ptr node, int cycle,
2317 sbitmap must_precede, sbitmap must_follow)
2321 int row = SMODULO (cycle, ps->ii);
2324 && ps->rows[row]->row_rest_count >= issue_rate)
2328 rest_count += ps->rows[row]->row_rest_count;
2330 ps_i = create_ps_insn (node, rest_count, cycle);
2332 /* Finds and inserts PS_I according to MUST_FOLLOW and
2334 if (! ps_insn_find_column (ps, ps_i, must_precede, must_follow))
2343 /* Advance time one cycle. Assumes DFA is being used. */
2345 advance_one_cycle (void)
2347 if (targetm.sched.dfa_pre_cycle_insn)
2348 state_transition (curr_state,
2349 (*targetm.sched.dfa_pre_cycle_insn) ());
2351 state_transition (curr_state, NULL);
2353 if (targetm.sched.dfa_post_cycle_insn)
2354 state_transition (curr_state,
2355 (*targetm.sched.dfa_post_cycle_insn) ());
2358 /* Given the kernel of a loop (from FIRST_INSN to LAST_INSN), finds
2359 the number of cycles according to DFA that the kernel fits in,
2360 we use this to check if we done well with SMS after we add
2361 register moves. In some cases register moves overhead makes
2362 it even worse than the original loop. We want SMS to be performed
2363 when it gives less cycles after register moves are added. */
2365 kernel_number_of_cycles (rtx first_insn, rtx last_insn)
2369 int can_issue_more = issue_rate;
2371 state_reset (curr_state);
2373 for (insn = first_insn;
2374 insn != NULL_RTX && insn != last_insn;
2375 insn = NEXT_INSN (insn))
2377 if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
2380 /* Check if there is room for the current insn. */
2381 if (!can_issue_more || state_dead_lock_p (curr_state))
2384 advance_one_cycle ();
2385 can_issue_more = issue_rate;
2388 /* Update the DFA state and return with failure if the DFA found
2389 recource conflicts. */
2390 if (state_transition (curr_state, insn) >= 0)
2393 advance_one_cycle ();
2394 can_issue_more = issue_rate;
2397 if (targetm.sched.variable_issue)
2399 (*targetm.sched.variable_issue) (sched_dump, sched_verbose,
2400 insn, can_issue_more);
2401 /* A naked CLOBBER or USE generates no instruction, so don't
2402 let them consume issue slots. */
2403 else if (GET_CODE (PATTERN (insn)) != USE
2404 && GET_CODE (PATTERN (insn)) != CLOBBER)
2410 /* Checks if PS has resource conflicts according to DFA, starting from
2411 FROM cycle to TO cycle; returns true if there are conflicts and false
2412 if there are no conflicts. Assumes DFA is being used. */
2414 ps_has_conflicts (partial_schedule_ptr ps, int from, int to)
2418 state_reset (curr_state);
2420 for (cycle = from; cycle <= to; cycle++)
2422 ps_insn_ptr crr_insn;
2423 /* Holds the remaining issue slots in the current row. */
2424 int can_issue_more = issue_rate;
2426 /* Walk through the DFA for the current row. */
2427 for (crr_insn = ps->rows[SMODULO (cycle, ps->ii)];
2429 crr_insn = crr_insn->next_in_row)
2431 rtx insn = crr_insn->node->insn;
2436 /* Check if there is room for the current insn. */
2437 if (!can_issue_more || state_dead_lock_p (curr_state))
2440 /* Update the DFA state and return with failure if the DFA found
2441 recource conflicts. */
2442 if (state_transition (curr_state, insn) >= 0)
2445 if (targetm.sched.variable_issue)
2447 (*targetm.sched.variable_issue) (sched_dump, sched_verbose,
2448 insn, can_issue_more);
2449 /* A naked CLOBBER or USE generates no instruction, so don't
2450 let them consume issue slots. */
2451 else if (GET_CODE (PATTERN (insn)) != USE
2452 && GET_CODE (PATTERN (insn)) != CLOBBER)
2456 /* Advance the DFA to the next cycle. */
2457 advance_one_cycle ();
2462 /* Checks if the given node causes resource conflicts when added to PS at
2463 cycle C. If not the node is added to PS and returned; otherwise zero
2464 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
2465 cuid N must be come before/after (respectively) the node pointed to by
2466 PS_I when scheduled in the same cycle. */
2468 ps_add_node_check_conflicts (partial_schedule_ptr ps, ddg_node_ptr n,
2469 int c, sbitmap must_precede,
2470 sbitmap must_follow)
2472 int has_conflicts = 0;
2475 /* First add the node to the PS, if this succeeds check for
2476 conflicts, trying different issue slots in the same row. */
2477 if (! (ps_i = add_node_to_ps (ps, n, c, must_precede, must_follow)))
2478 return NULL; /* Failed to insert the node at the given cycle. */
2480 has_conflicts = ps_has_conflicts (ps, c, c)
2482 && ps_has_conflicts (ps,
2486 /* Try different issue slots to find one that the given node can be
2487 scheduled in without conflicts. */
2488 while (has_conflicts)
2490 if (! ps_insn_advance_column (ps, ps_i, must_follow))
2492 has_conflicts = ps_has_conflicts (ps, c, c)
2494 && ps_has_conflicts (ps,
2501 remove_node_from_ps (ps, ps_i);
2505 ps->min_cycle = MIN (ps->min_cycle, c);
2506 ps->max_cycle = MAX (ps->max_cycle, c);
2510 /* Rotate the rows of PS such that insns scheduled at time
2511 START_CYCLE will appear in row 0. Updates max/min_cycles. */
2513 rotate_partial_schedule (partial_schedule_ptr ps, int start_cycle)
2515 int i, row, backward_rotates;
2516 int last_row = ps->ii - 1;
2518 if (start_cycle == 0)
2521 backward_rotates = SMODULO (start_cycle, ps->ii);
2523 /* Revisit later and optimize this into a single loop. */
2524 for (i = 0; i < backward_rotates; i++)
2526 ps_insn_ptr first_row = ps->rows[0];
2528 for (row = 0; row < last_row; row++)
2529 ps->rows[row] = ps->rows[row+1];
2531 ps->rows[last_row] = first_row;
2534 ps->max_cycle -= start_cycle;
2535 ps->min_cycle -= start_cycle;
2538 /* Remove the node N from the partial schedule PS; because we restart the DFA
2539 each time we want to check for resource conflicts; this is equivalent to
2540 unscheduling the node N. */
2542 ps_unschedule_node (partial_schedule_ptr ps, ddg_node_ptr n)
2545 int row = SMODULO (SCHED_TIME (n), ps->ii);
2547 if (row < 0 || row > ps->ii)
2550 for (ps_i = ps->rows[row];
2551 ps_i && ps_i->node != n;
2552 ps_i = ps_i->next_in_row);
2556 return remove_node_from_ps (ps, ps_i);
2558 #endif /* INSN_SCHEDULING*/