1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004, 2005, 2006, 2007
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 3, 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 COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
30 #include "hard-reg-set.h"
34 #include "insn-config.h"
35 #include "insn-attr.h"
39 #include "sched-int.h"
41 #include "cfglayout.h"
49 #include "tree-pass.h"
52 #ifdef INSN_SCHEDULING
54 /* This file contains the implementation of the Swing Modulo Scheduler,
55 described in the following references:
56 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
57 Lifetime--sensitive modulo scheduling in a production environment.
58 IEEE Trans. on Comps., 50(3), March 2001
59 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
60 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
61 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
63 The basic structure is:
64 1. Build a data-dependence graph (DDG) for each loop.
65 2. Use the DDG to order the insns of a loop (not in topological order
66 necessarily, but rather) trying to place each insn after all its
67 predecessors _or_ after all its successors.
68 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
69 4. Use the ordering to perform list-scheduling of the loop:
70 1. Set II = MII. We will try to schedule the loop within II cycles.
71 2. Try to schedule the insns one by one according to the ordering.
72 For each insn compute an interval of cycles by considering already-
73 scheduled preds and succs (and associated latencies); try to place
74 the insn in the cycles of this window checking for potential
75 resource conflicts (using the DFA interface).
76 Note: this is different from the cycle-scheduling of schedule_insns;
77 here the insns are not scheduled monotonically top-down (nor bottom-
79 3. If failed in scheduling all insns - bump II++ and try again, unless
80 II reaches an upper bound MaxII, in which case report failure.
81 5. If we succeeded in scheduling the loop within II cycles, we now
82 generate prolog and epilog, decrease the counter of the loop, and
83 perform modulo variable expansion for live ranges that span more than
84 II cycles (i.e. use register copies to prevent a def from overwriting
85 itself before reaching the use).
87 SMS works with countable loops (1) whose control part can be easily
88 decoupled from the rest of the loop and (2) whose loop count can
89 be easily adjusted. This is because we peel a constant number of
90 iterations into a prologue and epilogue for which we want to avoid
91 emitting the control part, and a kernel which is to iterate that
92 constant number of iterations less than the original loop. So the
93 control part should be a set of insns clearly identified and having
94 its own iv, not otherwise used in the loop (at-least for now), which
95 initializes a register before the loop to the number of iterations.
96 Currently SMS relies on the do-loop pattern to recognize such loops,
97 where (1) the control part comprises of all insns defining and/or
98 using a certain 'count' register and (2) the loop count can be
99 adjusted by modifying this register prior to the loop.
100 TODO: Rely on cfgloop analysis instead. */
102 /* This page defines partial-schedule structures and functions for
103 modulo scheduling. */
105 typedef struct partial_schedule *partial_schedule_ptr;
106 typedef struct ps_insn *ps_insn_ptr;
108 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
109 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
111 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
112 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
114 /* Perform signed modulo, always returning a non-negative value. */
115 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
117 /* The number of different iterations the nodes in ps span, assuming
118 the stage boundaries are placed efficiently. */
119 #define PS_STAGE_COUNT(ps) ((PS_MAX_CYCLE (ps) - PS_MIN_CYCLE (ps) \
120 + 1 + (ps)->ii - 1) / (ps)->ii)
122 /* A single instruction in the partial schedule. */
125 /* The corresponding DDG_NODE. */
128 /* The (absolute) cycle in which the PS instruction is scheduled.
129 Same as SCHED_TIME (node). */
132 /* The next/prev PS_INSN in the same row. */
133 ps_insn_ptr next_in_row,
136 /* The number of nodes in the same row that come after this node. */
140 /* Holds the partial schedule as an array of II rows. Each entry of the
141 array points to a linked list of PS_INSNs, which represents the
142 instructions that are scheduled for that row. */
143 struct partial_schedule
145 int ii; /* Number of rows in the partial schedule. */
146 int history; /* Threshold for conflict checking using DFA. */
148 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
151 /* The earliest absolute cycle of an insn in the partial schedule. */
154 /* The latest absolute cycle of an insn in the partial schedule. */
157 ddg_ptr g; /* The DDG of the insns in the partial schedule. */
160 /* We use this to record all the register replacements we do in
161 the kernel so we can undo SMS if it is not profitable. */
162 struct undo_replace_buff_elem
167 struct undo_replace_buff_elem *next;
172 static partial_schedule_ptr create_partial_schedule (int ii, ddg_ptr, int history);
173 static void free_partial_schedule (partial_schedule_ptr);
174 static void reset_partial_schedule (partial_schedule_ptr, int new_ii);
175 void print_partial_schedule (partial_schedule_ptr, FILE *);
176 static void verify_partial_schedule (partial_schedule_ptr, sbitmap);
177 static ps_insn_ptr ps_add_node_check_conflicts (partial_schedule_ptr,
178 ddg_node_ptr node, int cycle,
179 sbitmap must_precede,
180 sbitmap must_follow);
181 static void rotate_partial_schedule (partial_schedule_ptr, int);
182 void set_row_column_for_ps (partial_schedule_ptr);
183 static void ps_insert_empty_row (partial_schedule_ptr, int, sbitmap);
184 static int compute_split_row (sbitmap, int, int, int, ddg_node_ptr);
187 /* This page defines constants and structures for the modulo scheduling
190 /* As in haifa-sched.c: */
191 /* issue_rate is the number of insns that can be scheduled in the same
192 machine cycle. It can be defined in the config/mach/mach.h file,
193 otherwise we set it to 1. */
195 static int issue_rate;
197 static int sms_order_nodes (ddg_ptr, int, int * result);
198 static void set_node_sched_params (ddg_ptr);
199 static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int, int *);
200 static void permute_partial_schedule (partial_schedule_ptr ps, rtx last);
201 static void generate_prolog_epilog (partial_schedule_ptr, struct loop *loop,
203 static void duplicate_insns_of_cycles (partial_schedule_ptr ps,
204 int from_stage, int to_stage,
205 int is_prolog, rtx count_reg);
207 #define SCHED_ASAP(x) (((node_sched_params_ptr)(x)->aux.info)->asap)
208 #define SCHED_TIME(x) (((node_sched_params_ptr)(x)->aux.info)->time)
209 #define SCHED_FIRST_REG_MOVE(x) \
210 (((node_sched_params_ptr)(x)->aux.info)->first_reg_move)
211 #define SCHED_NREG_MOVES(x) \
212 (((node_sched_params_ptr)(x)->aux.info)->nreg_moves)
213 #define SCHED_ROW(x) (((node_sched_params_ptr)(x)->aux.info)->row)
214 #define SCHED_STAGE(x) (((node_sched_params_ptr)(x)->aux.info)->stage)
215 #define SCHED_COLUMN(x) (((node_sched_params_ptr)(x)->aux.info)->column)
217 /* The scheduling parameters held for each node. */
218 typedef struct node_sched_params
220 int asap; /* A lower-bound on the absolute scheduling cycle. */
221 int time; /* The absolute scheduling cycle (time >= asap). */
223 /* The following field (first_reg_move) is a pointer to the first
224 register-move instruction added to handle the modulo-variable-expansion
225 of the register defined by this node. This register-move copies the
226 original register defined by the node. */
229 /* The number of register-move instructions added, immediately preceding
233 int row; /* Holds time % ii. */
234 int stage; /* Holds time / ii. */
236 /* The column of a node inside the ps. If nodes u, v are on the same row,
237 u will precede v if column (u) < column (v). */
239 } *node_sched_params_ptr;
242 /* The following three functions are copied from the current scheduler
243 code in order to use sched_analyze() for computing the dependencies.
244 They are used when initializing the sched_info structure. */
246 sms_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED)
250 sprintf (tmp, "i%4d", INSN_UID (insn));
255 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
256 regset cond_exec ATTRIBUTE_UNUSED,
257 regset used ATTRIBUTE_UNUSED,
258 regset set ATTRIBUTE_UNUSED)
262 static struct sched_info sms_sched_info =
271 compute_jump_reg_dependencies,
276 NULL, NULL, NULL, NULL, NULL,
281 /* Given HEAD and TAIL which are the first and last insns in a loop;
282 return the register which controls the loop. Return zero if it has
283 more than one occurrence in the loop besides the control part or the
284 do-loop pattern is not of the form we expect. */
286 doloop_register_get (rtx head ATTRIBUTE_UNUSED, rtx tail ATTRIBUTE_UNUSED)
288 #ifdef HAVE_doloop_end
289 rtx reg, condition, insn, first_insn_not_to_check;
294 /* TODO: Free SMS's dependence on doloop_condition_get. */
295 condition = doloop_condition_get (tail);
299 if (REG_P (XEXP (condition, 0)))
300 reg = XEXP (condition, 0);
301 else if (GET_CODE (XEXP (condition, 0)) == PLUS
302 && REG_P (XEXP (XEXP (condition, 0), 0)))
303 reg = XEXP (XEXP (condition, 0), 0);
307 /* Check that the COUNT_REG has no other occurrences in the loop
308 until the decrement. We assume the control part consists of
309 either a single (parallel) branch-on-count or a (non-parallel)
310 branch immediately preceded by a single (decrement) insn. */
311 first_insn_not_to_check = (GET_CODE (PATTERN (tail)) == PARALLEL ? tail
314 for (insn = head; insn != first_insn_not_to_check; insn = NEXT_INSN (insn))
315 if (reg_mentioned_p (reg, insn))
319 fprintf (dump_file, "SMS count_reg found ");
320 print_rtl_single (dump_file, reg);
321 fprintf (dump_file, " outside control in insn:\n");
322 print_rtl_single (dump_file, insn);
334 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
335 that the number of iterations is a compile-time constant. If so,
336 return the rtx that sets COUNT_REG to a constant, and set COUNT to
337 this constant. Otherwise return 0. */
339 const_iteration_count (rtx count_reg, basic_block pre_header,
340 HOST_WIDEST_INT * count)
348 get_ebb_head_tail (pre_header, pre_header, &head, &tail);
350 for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn))
351 if (INSN_P (insn) && single_set (insn) &&
352 rtx_equal_p (count_reg, SET_DEST (single_set (insn))))
354 rtx pat = single_set (insn);
356 if (GET_CODE (SET_SRC (pat)) == CONST_INT)
358 *count = INTVAL (SET_SRC (pat));
368 /* A very simple resource-based lower bound on the initiation interval.
369 ??? Improve the accuracy of this bound by considering the
370 utilization of various units. */
374 if (targetm.sched.sms_res_mii)
375 return targetm.sched.sms_res_mii (g);
377 return (g->num_nodes / issue_rate);
381 /* Points to the array that contains the sched data for each node. */
382 static node_sched_params_ptr node_sched_params;
384 /* Allocate sched_params for each node and initialize it. Assumes that
385 the aux field of each node contain the asap bound (computed earlier),
386 and copies it into the sched_params field. */
388 set_node_sched_params (ddg_ptr g)
392 /* Allocate for each node in the DDG a place to hold the "sched_data". */
393 /* Initialize ASAP/ALAP/HIGHT to zero. */
394 node_sched_params = (node_sched_params_ptr)
395 xcalloc (g->num_nodes,
396 sizeof (struct node_sched_params));
398 /* Set the pointer of the general data of the node to point to the
399 appropriate sched_params structure. */
400 for (i = 0; i < g->num_nodes; i++)
402 /* Watch out for aliasing problems? */
403 node_sched_params[i].asap = g->nodes[i].aux.count;
404 g->nodes[i].aux.info = &node_sched_params[i];
409 print_node_sched_params (FILE *file, int num_nodes, ddg_ptr g)
415 for (i = 0; i < num_nodes; i++)
417 node_sched_params_ptr nsp = &node_sched_params[i];
418 rtx reg_move = nsp->first_reg_move;
421 fprintf (file, "Node = %d; INSN = %d\n", i,
422 (INSN_UID (g->nodes[i].insn)));
423 fprintf (file, " asap = %d:\n", nsp->asap);
424 fprintf (file, " time = %d:\n", nsp->time);
425 fprintf (file, " nreg_moves = %d:\n", nsp->nreg_moves);
426 for (j = 0; j < nsp->nreg_moves; j++)
428 fprintf (file, " reg_move = ");
429 print_rtl_single (file, reg_move);
430 reg_move = PREV_INSN (reg_move);
436 Breaking intra-loop register anti-dependences:
437 Each intra-loop register anti-dependence implies a cross-iteration true
438 dependence of distance 1. Therefore, we can remove such false dependencies
439 and figure out if the partial schedule broke them by checking if (for a
440 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
441 if so generate a register move. The number of such moves is equal to:
442 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
443 nreg_moves = ----------------------------------- + 1 - { dependence.
446 static struct undo_replace_buff_elem *
447 generate_reg_moves (partial_schedule_ptr ps, bool rescan)
452 struct undo_replace_buff_elem *reg_move_replaces = NULL;
454 for (i = 0; i < g->num_nodes; i++)
456 ddg_node_ptr u = &g->nodes[i];
458 int nreg_moves = 0, i_reg_move;
459 sbitmap *uses_of_defs;
461 rtx prev_reg, old_reg;
463 /* Compute the number of reg_moves needed for u, by looking at life
464 ranges started at u (excluding self-loops). */
465 for (e = u->out; e; e = e->next_out)
466 if (e->type == TRUE_DEP && e->dest != e->src)
468 int nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
470 if (e->distance == 1)
471 nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
473 /* If dest precedes src in the schedule of the kernel, then dest
474 will read before src writes and we can save one reg_copy. */
475 if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)
476 && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))
479 nreg_moves = MAX (nreg_moves, nreg_moves4e);
485 /* Every use of the register defined by node may require a different
486 copy of this register, depending on the time the use is scheduled.
487 Set a bitmap vector, telling which nodes use each copy of this
489 uses_of_defs = sbitmap_vector_alloc (nreg_moves, g->num_nodes);
490 sbitmap_vector_zero (uses_of_defs, nreg_moves);
491 for (e = u->out; e; e = e->next_out)
492 if (e->type == TRUE_DEP && e->dest != e->src)
494 int dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
496 if (e->distance == 1)
497 dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
499 if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)
500 && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))
504 SET_BIT (uses_of_defs[dest_copy - 1], e->dest->cuid);
507 /* Now generate the reg_moves, attaching relevant uses to them. */
508 SCHED_NREG_MOVES (u) = nreg_moves;
509 old_reg = prev_reg = copy_rtx (SET_DEST (single_set (u->insn)));
510 last_reg_move = u->insn;
512 for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
514 unsigned int i_use = 0;
515 rtx new_reg = gen_reg_rtx (GET_MODE (prev_reg));
516 rtx reg_move = gen_move_insn (new_reg, prev_reg);
517 sbitmap_iterator sbi;
519 add_insn_before (reg_move, last_reg_move, NULL);
520 last_reg_move = reg_move;
522 if (!SCHED_FIRST_REG_MOVE (u))
523 SCHED_FIRST_REG_MOVE (u) = reg_move;
525 EXECUTE_IF_SET_IN_SBITMAP (uses_of_defs[i_reg_move], 0, i_use, sbi)
527 struct undo_replace_buff_elem *rep;
529 rep = (struct undo_replace_buff_elem *)
530 xcalloc (1, sizeof (struct undo_replace_buff_elem));
531 rep->insn = g->nodes[i_use].insn;
532 rep->orig_reg = old_reg;
533 rep->new_reg = new_reg;
535 if (! reg_move_replaces)
536 reg_move_replaces = rep;
539 rep->next = reg_move_replaces;
540 reg_move_replaces = rep;
543 replace_rtx (g->nodes[i_use].insn, old_reg, new_reg);
545 df_insn_rescan (g->nodes[i_use].insn);
550 sbitmap_vector_free (uses_of_defs);
552 return reg_move_replaces;
555 /* Free memory allocated for the undo buffer. */
557 free_undo_replace_buff (struct undo_replace_buff_elem *reg_move_replaces)
560 while (reg_move_replaces)
562 struct undo_replace_buff_elem *rep = reg_move_replaces;
564 reg_move_replaces = reg_move_replaces->next;
569 /* Bump the SCHED_TIMEs of all nodes to start from zero. Set the values
570 of SCHED_ROW and SCHED_STAGE. */
572 normalize_sched_times (partial_schedule_ptr ps)
575 int amount = PS_MIN_CYCLE (ps);
577 ps_insn_ptr crr_insn;
579 for (row = 0; row < ii; row++)
580 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
582 ddg_node_ptr u = crr_insn->node;
583 int normalized_time = SCHED_TIME (u) - amount;
586 fprintf (dump_file, "crr_insn->node=%d, crr_insn->cycle=%d,\
587 min_cycle=%d\n", crr_insn->node->cuid, SCHED_TIME
589 gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
590 gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
591 SCHED_TIME (u) = normalized_time;
592 SCHED_ROW (u) = normalized_time % ii;
593 SCHED_STAGE (u) = normalized_time / ii;
597 /* Set SCHED_COLUMN of each node according to its position in PS. */
599 set_columns_for_ps (partial_schedule_ptr ps)
603 for (row = 0; row < ps->ii; row++)
605 ps_insn_ptr cur_insn = ps->rows[row];
608 for (; cur_insn; cur_insn = cur_insn->next_in_row)
609 SCHED_COLUMN (cur_insn->node) = column++;
613 /* Permute the insns according to their order in PS, from row 0 to
614 row ii-1, and position them right before LAST. This schedules
615 the insns of the loop kernel. */
617 permute_partial_schedule (partial_schedule_ptr ps, rtx last)
623 for (row = 0; row < ii ; row++)
624 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
625 if (PREV_INSN (last) != ps_ij->node->insn)
626 reorder_insns_nobb (ps_ij->node->first_note, ps_ij->node->insn,
631 duplicate_insns_of_cycles (partial_schedule_ptr ps, int from_stage,
632 int to_stage, int for_prolog, rtx count_reg)
637 for (row = 0; row < ps->ii; row++)
638 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
640 ddg_node_ptr u_node = ps_ij->node;
642 rtx reg_move = NULL_RTX;
644 /* Do not duplicate any insn which refers to count_reg as it
645 belongs to the control part.
646 TODO: This should be done by analyzing the control part of
648 if (reg_mentioned_p (count_reg, u_node->insn))
653 /* SCHED_STAGE (u_node) >= from_stage == 0. Generate increasing
654 number of reg_moves starting with the second occurrence of
655 u_node, which is generated if its SCHED_STAGE <= to_stage. */
656 i_reg_moves = to_stage - SCHED_STAGE (u_node) + 1;
657 i_reg_moves = MAX (i_reg_moves, 0);
658 i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));
660 /* The reg_moves start from the *first* reg_move backwards. */
663 reg_move = SCHED_FIRST_REG_MOVE (u_node);
664 for (j = 1; j < i_reg_moves; j++)
665 reg_move = PREV_INSN (reg_move);
668 else /* It's for the epilog. */
670 /* SCHED_STAGE (u_node) <= to_stage. Generate all reg_moves,
671 starting to decrease one stage after u_node no longer occurs;
672 that is, generate all reg_moves until
673 SCHED_STAGE (u_node) == from_stage - 1. */
674 i_reg_moves = SCHED_NREG_MOVES (u_node)
675 - (from_stage - SCHED_STAGE (u_node) - 1);
676 i_reg_moves = MAX (i_reg_moves, 0);
677 i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));
679 /* The reg_moves start from the *last* reg_move forwards. */
682 reg_move = SCHED_FIRST_REG_MOVE (u_node);
683 for (j = 1; j < SCHED_NREG_MOVES (u_node); j++)
684 reg_move = PREV_INSN (reg_move);
688 for (j = 0; j < i_reg_moves; j++, reg_move = NEXT_INSN (reg_move))
689 emit_insn (copy_rtx (PATTERN (reg_move)));
690 if (SCHED_STAGE (u_node) >= from_stage
691 && SCHED_STAGE (u_node) <= to_stage)
692 duplicate_insn_chain (u_node->first_note, u_node->insn);
697 /* Generate the instructions (including reg_moves) for prolog & epilog. */
699 generate_prolog_epilog (partial_schedule_ptr ps, struct loop *loop,
700 rtx count_reg, rtx count_init)
703 int last_stage = PS_STAGE_COUNT (ps) - 1;
706 /* Generate the prolog, inserting its insns on the loop-entry edge. */
711 /* Generate instructions at the beginning of the prolog to
712 adjust the loop count by STAGE_COUNT. If loop count is constant
713 (count_init), this constant is adjusted by STAGE_COUNT in
714 generate_prolog_epilog function. */
715 rtx sub_reg = NULL_RTX;
717 sub_reg = expand_simple_binop (GET_MODE (count_reg), MINUS,
718 count_reg, GEN_INT (last_stage),
719 count_reg, 1, OPTAB_DIRECT);
720 gcc_assert (REG_P (sub_reg));
721 if (REGNO (sub_reg) != REGNO (count_reg))
722 emit_move_insn (count_reg, sub_reg);
725 for (i = 0; i < last_stage; i++)
726 duplicate_insns_of_cycles (ps, 0, i, 1, count_reg);
728 /* Put the prolog on the entry edge. */
729 e = loop_preheader_edge (loop);
730 split_edge_and_insert (e, get_insns ());
734 /* Generate the epilog, inserting its insns on the loop-exit edge. */
737 for (i = 0; i < last_stage; i++)
738 duplicate_insns_of_cycles (ps, i + 1, last_stage, 0, count_reg);
740 /* Put the epilogue on the exit edge. */
741 gcc_assert (single_exit (loop));
742 e = single_exit (loop);
743 split_edge_and_insert (e, get_insns ());
747 /* Return true if all the BBs of the loop are empty except the
750 loop_single_full_bb_p (struct loop *loop)
753 basic_block *bbs = get_loop_body (loop);
755 for (i = 0; i < loop->num_nodes ; i++)
758 bool empty_bb = true;
760 if (bbs[i] == loop->header)
763 /* Make sure that basic blocks other than the header
764 have only notes labels or jumps. */
765 get_ebb_head_tail (bbs[i], bbs[i], &head, &tail);
766 for (; head != NEXT_INSN (tail); head = NEXT_INSN (head))
768 if (NOTE_P (head) || LABEL_P (head)
769 || (INSN_P (head) && JUMP_P (head)))
785 /* A simple loop from SMS point of view; it is a loop that is composed of
786 either a single basic block or two BBs - a header and a latch. */
787 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
788 && (EDGE_COUNT (loop->latch->preds) == 1) \
789 && (EDGE_COUNT (loop->latch->succs) == 1))
791 /* Return true if the loop is in its canonical form and false if not.
792 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
794 loop_canon_p (struct loop *loop)
797 if (loop->inner || !loop_outer (loop))
800 if (!single_exit (loop))
804 rtx insn = BB_END (loop->header);
806 fprintf (dump_file, "SMS loop many exits ");
807 fprintf (dump_file, " %s %d (file, line)\n",
808 insn_file (insn), insn_line (insn));
813 if (! SIMPLE_SMS_LOOP_P (loop) && ! loop_single_full_bb_p (loop))
817 rtx insn = BB_END (loop->header);
819 fprintf (dump_file, "SMS loop many BBs. ");
820 fprintf (dump_file, " %s %d (file, line)\n",
821 insn_file (insn), insn_line (insn));
829 /* If there are more than one entry for the loop,
830 make it one by splitting the first entry edge and
831 redirecting the others to the new BB. */
833 canon_loop (struct loop *loop)
838 /* Avoid annoying special cases of edges going to exit
840 FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR->preds)
841 if ((e->flags & EDGE_FALLTHRU) && (EDGE_COUNT (e->src->succs) > 1))
844 if (loop->latch == loop->header
845 || EDGE_COUNT (loop->latch->succs) > 1)
847 FOR_EACH_EDGE (e, i, loop->header->preds)
848 if (e->src == loop->latch)
854 /* Probability in % that the sms-ed loop rolls enough so that optimized
855 version may be entered. Just a guess. */
856 #define PROB_SMS_ENOUGH_ITERATIONS 80
858 /* Used to calculate the upper bound of ii. */
859 #define MAXII_FACTOR 2
861 /* Main entry point, perform SMS scheduling on the loops of the function
862 that consist of single basic blocks. */
871 partial_schedule_ptr ps;
872 basic_block bb = NULL;
874 basic_block condition_bb = NULL;
876 gcov_type trip_count = 0;
878 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
879 | LOOPS_HAVE_RECORDED_EXITS);
880 if (number_of_loops () <= 1)
882 loop_optimizer_finalize ();
883 return; /* There are no loops to schedule. */
886 /* Initialize issue_rate. */
887 if (targetm.sched.issue_rate)
889 int temp = reload_completed;
891 reload_completed = 1;
892 issue_rate = targetm.sched.issue_rate ();
893 reload_completed = temp;
898 /* Initialize the scheduler. */
899 current_sched_info = &sms_sched_info;
901 /* Init Data Flow analysis, to be used in interloop dep calculation. */
902 df_set_flags (DF_LR_RUN_DCE);
903 df_rd_add_problem ();
904 df_note_add_problem ();
905 df_chain_add_problem (DF_DU_CHAIN + DF_UD_CHAIN);
907 regstat_compute_calls_crossed ();
910 /* Allocate memory to hold the DDG array one entry for each loop.
911 We use loop->num as index into this array. */
912 g_arr = XCNEWVEC (ddg_ptr, number_of_loops ());
914 /* Build DDGs for all the relevant loops and hold them in G_ARR
915 indexed by the loop index. */
916 FOR_EACH_LOOP (li, loop, 0)
922 if (dbg_cnt (sms_sched_loop) == false)
925 fprintf (dump_file, "SMS reached max limit... \n");
930 if (! loop_canon_p (loop))
933 if (! loop_single_full_bb_p (loop))
938 get_ebb_head_tail (bb, bb, &head, &tail);
939 latch_edge = loop_latch_edge (loop);
940 gcc_assert (single_exit (loop));
941 if (single_exit (loop)->count)
942 trip_count = latch_edge->count / single_exit (loop)->count;
944 /* Perfrom SMS only on loops that their average count is above threshold. */
946 if ( latch_edge->count
947 && (latch_edge->count < single_exit (loop)->count * SMS_LOOP_AVERAGE_COUNT_THRESHOLD))
951 fprintf (dump_file, " %s %d (file, line)\n",
952 insn_file (tail), insn_line (tail));
953 fprintf (dump_file, "SMS single-bb-loop\n");
954 if (profile_info && flag_branch_probabilities)
956 fprintf (dump_file, "SMS loop-count ");
957 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
958 (HOST_WIDEST_INT) bb->count);
959 fprintf (dump_file, "\n");
960 fprintf (dump_file, "SMS trip-count ");
961 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
962 (HOST_WIDEST_INT) trip_count);
963 fprintf (dump_file, "\n");
964 fprintf (dump_file, "SMS profile-sum-max ");
965 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
966 (HOST_WIDEST_INT) profile_info->sum_max);
967 fprintf (dump_file, "\n");
973 /* Make sure this is a doloop. */
974 if ( !(count_reg = doloop_register_get (head, tail)))
977 /* Don't handle BBs with calls or barriers, or !single_set insns,
978 or auto-increment insns (to avoid creating invalid reg-moves
979 for the auto-increment insns).
980 ??? Should handle auto-increment insns.
981 ??? Should handle insns defining subregs. */
982 for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn))
988 || (INSN_P (insn) && !JUMP_P (insn)
989 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE)
990 || (FIND_REG_INC_NOTE (insn, NULL_RTX) != 0)
991 || (INSN_P (insn) && (set = single_set (insn))
992 && GET_CODE (SET_DEST (set)) == SUBREG))
996 if (insn != NEXT_INSN (tail))
1001 fprintf (dump_file, "SMS loop-with-call\n");
1002 else if (BARRIER_P (insn))
1003 fprintf (dump_file, "SMS loop-with-barrier\n");
1004 else if (FIND_REG_INC_NOTE (insn, NULL_RTX) != 0)
1005 fprintf (dump_file, "SMS reg inc\n");
1006 else if ((INSN_P (insn) && !JUMP_P (insn)
1007 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE))
1008 fprintf (dump_file, "SMS loop-with-not-single-set\n");
1010 fprintf (dump_file, "SMS loop with subreg in lhs\n");
1011 print_rtl_single (dump_file, insn);
1017 if (! (g = create_ddg (bb, 0)))
1020 fprintf (dump_file, "SMS doloop\n");
1024 g_arr[loop->num] = g;
1027 /* We don't want to perform SMS on new loops - created by versioning. */
1028 FOR_EACH_LOOP (li, loop, 0)
1031 rtx count_reg, count_init;
1033 unsigned stage_count = 0;
1034 HOST_WIDEST_INT loop_count = 0;
1036 if (! (g = g_arr[loop->num]))
1040 print_ddg (dump_file, g);
1042 get_ebb_head_tail (loop->header, loop->header, &head, &tail);
1044 latch_edge = loop_latch_edge (loop);
1045 gcc_assert (single_exit (loop));
1046 if (single_exit (loop)->count)
1047 trip_count = latch_edge->count / single_exit (loop)->count;
1051 fprintf (dump_file, " %s %d (file, line)\n",
1052 insn_file (tail), insn_line (tail));
1053 fprintf (dump_file, "SMS single-bb-loop\n");
1054 if (profile_info && flag_branch_probabilities)
1056 fprintf (dump_file, "SMS loop-count ");
1057 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1058 (HOST_WIDEST_INT) bb->count);
1059 fprintf (dump_file, "\n");
1060 fprintf (dump_file, "SMS profile-sum-max ");
1061 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1062 (HOST_WIDEST_INT) profile_info->sum_max);
1063 fprintf (dump_file, "\n");
1065 fprintf (dump_file, "SMS doloop\n");
1066 fprintf (dump_file, "SMS built-ddg %d\n", g->num_nodes);
1067 fprintf (dump_file, "SMS num-loads %d\n", g->num_loads);
1068 fprintf (dump_file, "SMS num-stores %d\n", g->num_stores);
1072 /* In case of th loop have doloop register it gets special
1074 count_init = NULL_RTX;
1075 if ((count_reg = doloop_register_get (head, tail)))
1077 basic_block pre_header;
1079 pre_header = loop_preheader_edge (loop)->src;
1080 count_init = const_iteration_count (count_reg, pre_header,
1083 gcc_assert (count_reg);
1085 if (dump_file && count_init)
1087 fprintf (dump_file, "SMS const-doloop ");
1088 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1090 fprintf (dump_file, "\n");
1093 node_order = XNEWVEC (int, g->num_nodes);
1095 mii = 1; /* Need to pass some estimate of mii. */
1096 rec_mii = sms_order_nodes (g, mii, node_order);
1097 mii = MAX (res_MII (g), rec_mii);
1098 maxii = MAXII_FACTOR * mii;
1101 fprintf (dump_file, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1102 rec_mii, mii, maxii);
1104 /* After sms_order_nodes and before sms_schedule_by_order, to copy over
1106 set_node_sched_params (g);
1108 ps = sms_schedule_by_order (g, mii, maxii, node_order);
1111 stage_count = PS_STAGE_COUNT (ps);
1113 /* Stage count of 1 means that there is no interleaving between
1114 iterations, let the scheduling passes do the job. */
1116 || (count_init && (loop_count <= stage_count))
1117 || (flag_branch_probabilities && (trip_count <= stage_count)))
1121 fprintf (dump_file, "SMS failed... \n");
1122 fprintf (dump_file, "SMS sched-failed (stage-count=%d, loop-count=", stage_count);
1123 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, loop_count);
1124 fprintf (dump_file, ", trip-count=");
1125 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, trip_count);
1126 fprintf (dump_file, ")\n");
1132 struct undo_replace_buff_elem *reg_move_replaces;
1137 "SMS succeeded %d %d (with ii, sc)\n", ps->ii,
1139 print_partial_schedule (ps, dump_file);
1141 "SMS Branch (%d) will later be scheduled at cycle %d.\n",
1142 g->closing_branch->cuid, PS_MIN_CYCLE (ps) - 1);
1145 /* Set the stage boundaries. If the DDG is built with closing_branch_deps,
1146 the closing_branch was scheduled and should appear in the last (ii-1)
1147 row. Otherwise, we are free to schedule the branch, and we let nodes
1148 that were scheduled at the first PS_MIN_CYCLE cycle appear in the first
1149 row; this should reduce stage_count to minimum.
1150 TODO: Revisit the issue of scheduling the insns of the
1151 control part relative to the branch when the control part
1152 has more than one insn. */
1153 normalize_sched_times (ps);
1154 rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
1155 set_columns_for_ps (ps);
1159 /* case the BCT count is not known , Do loop-versioning */
1160 if (count_reg && ! count_init)
1162 rtx comp_rtx = gen_rtx_fmt_ee (GT, VOIDmode, count_reg,
1163 GEN_INT(stage_count));
1164 unsigned prob = (PROB_SMS_ENOUGH_ITERATIONS
1165 * REG_BR_PROB_BASE) / 100;
1167 loop_version (loop, comp_rtx, &condition_bb,
1168 prob, prob, REG_BR_PROB_BASE - prob,
1172 /* Set new iteration count of loop kernel. */
1173 if (count_reg && count_init)
1174 SET_SRC (single_set (count_init)) = GEN_INT (loop_count
1177 /* Now apply the scheduled kernel to the RTL of the loop. */
1178 permute_partial_schedule (ps, g->closing_branch->first_note);
1180 /* Mark this loop as software pipelined so the later
1181 scheduling passes doesn't touch it. */
1182 if (! flag_resched_modulo_sched)
1183 g->bb->flags |= BB_DISABLE_SCHEDULE;
1184 /* The life-info is not valid any more. */
1185 df_set_bb_dirty (g->bb);
1187 reg_move_replaces = generate_reg_moves (ps, true);
1189 print_node_sched_params (dump_file, g->num_nodes, g);
1190 /* Generate prolog and epilog. */
1191 generate_prolog_epilog (ps, loop, count_reg, count_init);
1193 free_undo_replace_buff (reg_move_replaces);
1196 free_partial_schedule (ps);
1197 free (node_sched_params);
1202 regstat_free_calls_crossed ();
1205 /* Release scheduler data, needed until now because of DFA. */
1207 loop_optimizer_finalize ();
1210 /* The SMS scheduling algorithm itself
1211 -----------------------------------
1212 Input: 'O' an ordered list of insns of a loop.
1213 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1215 'Q' is the empty Set
1216 'PS' is the partial schedule; it holds the currently scheduled nodes with
1218 'PSP' previously scheduled predecessors.
1219 'PSS' previously scheduled successors.
1220 't(u)' the cycle where u is scheduled.
1221 'l(u)' is the latency of u.
1222 'd(v,u)' is the dependence distance from v to u.
1223 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1224 the node ordering phase.
1225 'check_hardware_resources_conflicts(u, PS, c)'
1226 run a trace around cycle/slot through DFA model
1227 to check resource conflicts involving instruction u
1228 at cycle c given the partial schedule PS.
1229 'add_to_partial_schedule_at_time(u, PS, c)'
1230 Add the node/instruction u to the partial schedule
1232 'calculate_register_pressure(PS)'
1233 Given a schedule of instructions, calculate the register
1234 pressure it implies. One implementation could be the
1235 maximum number of overlapping live ranges.
1236 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1237 registers available in the hardware.
1241 3. for each node u in O in pre-computed order
1242 4. if (PSP(u) != Q && PSS(u) == Q) then
1243 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1244 6. start = Early_start; end = Early_start + II - 1; step = 1
1245 11. else if (PSP(u) == Q && PSS(u) != Q) then
1246 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1247 13. start = Late_start; end = Late_start - II + 1; step = -1
1248 14. else if (PSP(u) != Q && PSS(u) != Q) then
1249 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1250 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1251 17. start = Early_start;
1252 18. end = min(Early_start + II - 1 , Late_start);
1254 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1255 21. start = ASAP(u); end = start + II - 1; step = 1
1259 24. for (c = start ; c != end ; c += step)
1260 25. if check_hardware_resources_conflicts(u, PS, c) then
1261 26. add_to_partial_schedule_at_time(u, PS, c)
1266 31. if (success == false) then
1268 33. if (II > maxII) then
1269 34. finish - failed to schedule
1274 39. if (calculate_register_pressure(PS) > maxRP) then
1277 42. compute epilogue & prologue
1278 43. finish - succeeded to schedule
1281 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1282 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1283 set to 0 to save compile time. */
1284 #define DFA_HISTORY SMS_DFA_HISTORY
1286 /* A threshold for the number of repeated unsuccessful attempts to insert
1287 an empty row, before we flush the partial schedule and start over. */
1288 #define MAX_SPLIT_NUM 10
1289 /* Given the partial schedule PS, this function calculates and returns the
1290 cycles in which we can schedule the node with the given index I.
1291 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1292 noticed that there are several cases in which we fail to SMS the loop
1293 because the sched window of a node is empty due to tight data-deps. In
1294 such cases we want to unschedule some of the predecessors/successors
1295 until we get non-empty scheduling window. It returns -1 if the
1296 scheduling window is empty and zero otherwise. */
1299 get_sched_window (partial_schedule_ptr ps, int *nodes_order, int i,
1300 sbitmap sched_nodes, int ii, int *start_p, int *step_p, int *end_p)
1302 int start, step, end;
1304 int u = nodes_order [i];
1305 ddg_node_ptr u_node = &ps->g->nodes[u];
1306 sbitmap psp = sbitmap_alloc (ps->g->num_nodes);
1307 sbitmap pss = sbitmap_alloc (ps->g->num_nodes);
1308 sbitmap u_node_preds = NODE_PREDECESSORS (u_node);
1309 sbitmap u_node_succs = NODE_SUCCESSORS (u_node);
1313 /* 1. compute sched window for u (start, end, step). */
1316 psp_not_empty = sbitmap_a_and_b_cg (psp, u_node_preds, sched_nodes);
1317 pss_not_empty = sbitmap_a_and_b_cg (pss, u_node_succs, sched_nodes);
1319 if (psp_not_empty && !pss_not_empty)
1321 int early_start = INT_MIN;
1324 for (e = u_node->in; e != 0; e = e->next_in)
1326 ddg_node_ptr v_node = e->src;
1330 fprintf (dump_file, "\nProcessing edge: ");
1331 print_ddg_edge (dump_file, e);
1333 "\nScheduling %d (%d) in psp_not_empty,"
1334 " checking p %d (%d): ", u_node->cuid,
1335 INSN_UID (u_node->insn), v_node->cuid, INSN_UID
1339 if (TEST_BIT (sched_nodes, v_node->cuid))
1341 int p_st = SCHED_TIME (v_node);
1344 MAX (early_start, p_st + e->latency - (e->distance * ii));
1347 fprintf (dump_file, "pred st = %d; early_start = %d; ", p_st,
1350 if (e->data_type == MEM_DEP)
1351 end = MIN (end, SCHED_TIME (v_node) + ii - 1);
1354 fprintf (dump_file, "the node is not scheduled\n");
1356 start = early_start;
1357 end = MIN (end, early_start + ii);
1362 "\nScheduling %d (%d) in a window (%d..%d) with step %d\n",
1363 u_node->cuid, INSN_UID (u_node->insn), start, end, step);
1366 else if (!psp_not_empty && pss_not_empty)
1368 int late_start = INT_MAX;
1371 for (e = u_node->out; e != 0; e = e->next_out)
1373 ddg_node_ptr v_node = e->dest;
1377 fprintf (dump_file, "\nProcessing edge:");
1378 print_ddg_edge (dump_file, e);
1380 "\nScheduling %d (%d) in pss_not_empty,"
1381 " checking s %d (%d): ", u_node->cuid,
1382 INSN_UID (u_node->insn), v_node->cuid, INSN_UID
1386 if (TEST_BIT (sched_nodes, v_node->cuid))
1388 int s_st = SCHED_TIME (v_node);
1390 late_start = MIN (late_start,
1391 s_st - e->latency + (e->distance * ii));
1394 fprintf (dump_file, "succ st = %d; late_start = %d;", s_st,
1397 if (e->data_type == MEM_DEP)
1398 end = MAX (end, SCHED_TIME (v_node) - ii + 1);
1400 fprintf (dump_file, "end = %d\n", end);
1404 fprintf (dump_file, "the node is not scheduled\n");
1408 end = MAX (end, late_start - ii);
1413 "\nScheduling %d (%d) in a window (%d..%d) with step %d\n",
1414 u_node->cuid, INSN_UID (u_node->insn), start, end, step);
1418 else if (psp_not_empty && pss_not_empty)
1420 int early_start = INT_MIN;
1421 int late_start = INT_MAX;
1425 for (e = u_node->in; e != 0; e = e->next_in)
1427 ddg_node_ptr v_node = e->src;
1431 fprintf (dump_file, "\nProcessing edge:");
1432 print_ddg_edge (dump_file, e);
1434 "\nScheduling %d (%d) in psp_pss_not_empty,"
1435 " checking p %d (%d): ", u_node->cuid, INSN_UID
1436 (u_node->insn), v_node->cuid, INSN_UID
1440 if (TEST_BIT (sched_nodes, v_node->cuid))
1442 int p_st = SCHED_TIME (v_node);
1444 early_start = MAX (early_start,
1446 - (e->distance * ii));
1449 fprintf (dump_file, "pred st = %d; early_start = %d;", p_st,
1452 if (e->data_type == MEM_DEP)
1453 end = MIN (end, SCHED_TIME (v_node) + ii - 1);
1456 fprintf (dump_file, "the node is not scheduled\n");
1459 for (e = u_node->out; e != 0; e = e->next_out)
1461 ddg_node_ptr v_node = e->dest;
1465 fprintf (dump_file, "\nProcessing edge:");
1466 print_ddg_edge (dump_file, e);
1468 "\nScheduling %d (%d) in psp_pss_not_empty,"
1469 " checking s %d (%d): ", u_node->cuid, INSN_UID
1470 (u_node->insn), v_node->cuid, INSN_UID
1474 if (TEST_BIT (sched_nodes, v_node->cuid))
1476 int s_st = SCHED_TIME (v_node);
1478 late_start = MIN (late_start,
1480 + (e->distance * ii));
1483 fprintf (dump_file, "succ st = %d; late_start = %d;", s_st,
1486 if (e->data_type == MEM_DEP)
1487 start = MAX (start, SCHED_TIME (v_node) - ii + 1);
1490 fprintf (dump_file, "the node is not scheduled\n");
1493 start = MAX (start, early_start);
1494 end = MIN (end, MIN (early_start + ii, late_start + 1));
1497 else /* psp is empty && pss is empty. */
1499 start = SCHED_ASAP (u_node);
1510 if ((start >= end && step == 1) || (start <= end && step == -1))
1513 fprintf (dump_file, "\nEmpty window: start=%d, end=%d, step=%d\n",
1521 /* This function implements the scheduling algorithm for SMS according to the
1523 static partial_schedule_ptr
1524 sms_schedule_by_order (ddg_ptr g, int mii, int maxii, int *nodes_order)
1527 int i, c, success, num_splits = 0;
1528 int flush_and_start_over = true;
1529 int num_nodes = g->num_nodes;
1532 int start, end, step; /* Place together into one struct? */
1533 sbitmap sched_nodes = sbitmap_alloc (num_nodes);
1534 sbitmap must_precede = sbitmap_alloc (num_nodes);
1535 sbitmap must_follow = sbitmap_alloc (num_nodes);
1536 sbitmap tobe_scheduled = sbitmap_alloc (num_nodes);
1538 partial_schedule_ptr ps = create_partial_schedule (ii, g, DFA_HISTORY);
1540 sbitmap_ones (tobe_scheduled);
1541 sbitmap_zero (sched_nodes);
1543 while (flush_and_start_over && (ii < maxii))
1547 fprintf (dump_file, "Starting with ii=%d\n", ii);
1548 flush_and_start_over = false;
1549 sbitmap_zero (sched_nodes);
1551 for (i = 0; i < num_nodes; i++)
1553 int u = nodes_order[i];
1554 ddg_node_ptr u_node = &ps->g->nodes[u];
1555 rtx insn = u_node->insn;
1559 RESET_BIT (tobe_scheduled, u);
1563 if (JUMP_P (insn)) /* Closing branch handled later. */
1565 RESET_BIT (tobe_scheduled, u);
1569 if (TEST_BIT (sched_nodes, u))
1572 /* Try to get non-empty scheduling window. */
1574 if (get_sched_window (ps, nodes_order, i, sched_nodes, ii, &start,
1578 fprintf (dump_file, "\nTrying to schedule node %d \
1579 INSN = %d in (%d .. %d) step %d\n", u, (INSN_UID
1580 (g->nodes[u].insn)), start, end, step);
1581 /* Use must_follow & must_precede bitmaps to determine order
1582 of nodes within the cycle. */
1584 /* use must_follow & must_precede bitmaps to determine order
1585 of nodes within the cycle. */
1586 sbitmap_zero (must_precede);
1587 sbitmap_zero (must_follow);
1588 /* TODO: We can add an insn to the must_precede or must_follow
1589 bitmaps only if it has tight dependence to U and they
1590 both scheduled in the same row. The current check is less
1591 conservative and content with the fact that both U and the
1592 insn are scheduled in the same row. */
1593 for (e = u_node->in; e != 0; e = e->next_in)
1594 if (TEST_BIT (sched_nodes, e->src->cuid)
1595 && (SMODULO (SCHED_TIME (e->src), ii) ==
1596 SMODULO (start, ii)))
1597 SET_BIT (must_precede, e->src->cuid);
1599 for (e = u_node->out; e != 0; e = e->next_out)
1600 if (TEST_BIT (sched_nodes, e->dest->cuid)
1601 && (SMODULO (SCHED_TIME (e->dest), ii) ==
1602 SMODULO ((end - step), ii)))
1603 SET_BIT (must_follow, e->dest->cuid);
1605 gcc_assert ((step > 0 && start < end)
1606 || (step < 0 && start > end));
1608 for (c = start; c != end; c += step)
1610 verify_partial_schedule (ps, sched_nodes);
1612 psi = ps_add_node_check_conflicts (ps, u_node, c,
1618 SCHED_TIME (u_node) = c;
1619 SET_BIT (sched_nodes, u);
1623 fprintf (dump_file, "Scheduled w/o split in %d\n", c);
1628 verify_partial_schedule (ps, sched_nodes);
1637 if (num_splits >= MAX_SPLIT_NUM)
1640 flush_and_start_over = true;
1641 verify_partial_schedule (ps, sched_nodes);
1642 reset_partial_schedule (ps, ii);
1643 verify_partial_schedule (ps, sched_nodes);
1649 split_row = compute_split_row (sched_nodes, start, end,
1652 split_row = compute_split_row (sched_nodes, end, start,
1655 ps_insert_empty_row (ps, split_row, sched_nodes);
1656 i--; /* Go back and retry node i. */
1659 fprintf (dump_file, "num_splits=%d\n", num_splits);
1662 /* ??? If (success), check register pressure estimates. */
1663 } /* Continue with next node. */
1664 } /* While flush_and_start_over. */
1667 free_partial_schedule (ps);
1671 gcc_assert (sbitmap_equal (tobe_scheduled, sched_nodes));
1673 sbitmap_free (sched_nodes);
1674 sbitmap_free (must_precede);
1675 sbitmap_free (must_follow);
1676 sbitmap_free (tobe_scheduled);
1681 /* This function inserts a new empty row into PS at the position
1682 according to SPLITROW, keeping all already scheduled instructions
1683 intact and updating their SCHED_TIME and cycle accordingly. */
1685 ps_insert_empty_row (partial_schedule_ptr ps, int split_row,
1686 sbitmap sched_nodes)
1688 ps_insn_ptr crr_insn;
1689 ps_insn_ptr *rows_new;
1691 int new_ii = ii + 1;
1694 verify_partial_schedule (ps, sched_nodes);
1696 /* We normalize sched_time and rotate ps to have only non-negative sched
1697 times, for simplicity of updating cycles after inserting new row. */
1698 split_row -= ps->min_cycle;
1699 split_row = SMODULO (split_row, ii);
1701 fprintf (dump_file, "split_row=%d\n", split_row);
1703 normalize_sched_times (ps);
1704 rotate_partial_schedule (ps, ps->min_cycle);
1706 rows_new = (ps_insn_ptr *) xcalloc (new_ii, sizeof (ps_insn_ptr));
1707 for (row = 0; row < split_row; row++)
1709 rows_new[row] = ps->rows[row];
1710 ps->rows[row] = NULL;
1711 for (crr_insn = rows_new[row];
1712 crr_insn; crr_insn = crr_insn->next_in_row)
1714 ddg_node_ptr u = crr_insn->node;
1715 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii);
1717 SCHED_TIME (u) = new_time;
1718 crr_insn->cycle = new_time;
1719 SCHED_ROW (u) = new_time % new_ii;
1720 SCHED_STAGE (u) = new_time / new_ii;
1725 rows_new[split_row] = NULL;
1727 for (row = split_row; row < ii; row++)
1729 rows_new[row + 1] = ps->rows[row];
1730 ps->rows[row] = NULL;
1731 for (crr_insn = rows_new[row + 1];
1732 crr_insn; crr_insn = crr_insn->next_in_row)
1734 ddg_node_ptr u = crr_insn->node;
1735 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii) + 1;
1737 SCHED_TIME (u) = new_time;
1738 crr_insn->cycle = new_time;
1739 SCHED_ROW (u) = new_time % new_ii;
1740 SCHED_STAGE (u) = new_time / new_ii;
1745 ps->min_cycle = ps->min_cycle + ps->min_cycle / ii
1746 + (SMODULO (ps->min_cycle, ii) >= split_row ? 1 : 0);
1747 ps->max_cycle = ps->max_cycle + ps->max_cycle / ii
1748 + (SMODULO (ps->max_cycle, ii) >= split_row ? 1 : 0);
1750 ps->rows = rows_new;
1752 gcc_assert (ps->min_cycle >= 0);
1754 verify_partial_schedule (ps, sched_nodes);
1757 fprintf (dump_file, "min_cycle=%d, max_cycle=%d\n", ps->min_cycle,
1761 /* Given U_NODE which is the node that failed to be scheduled; LOW and
1762 UP which are the boundaries of it's scheduling window; compute using
1763 SCHED_NODES and II a row in the partial schedule that can be split
1764 which will separate a critical predecessor from a critical successor
1765 thereby expanding the window, and return it. */
1767 compute_split_row (sbitmap sched_nodes, int low, int up, int ii,
1768 ddg_node_ptr u_node)
1771 int lower = INT_MIN, upper = INT_MAX;
1772 ddg_node_ptr crit_pred = NULL;
1773 ddg_node_ptr crit_succ = NULL;
1776 for (e = u_node->in; e != 0; e = e->next_in)
1778 ddg_node_ptr v_node = e->src;
1780 if (TEST_BIT (sched_nodes, v_node->cuid)
1781 && (low == SCHED_TIME (v_node) + e->latency - (e->distance * ii)))
1782 if (SCHED_TIME (v_node) > lower)
1785 lower = SCHED_TIME (v_node);
1789 if (crit_pred != NULL)
1791 crit_cycle = SCHED_TIME (crit_pred) + 1;
1792 return SMODULO (crit_cycle, ii);
1795 for (e = u_node->out; e != 0; e = e->next_out)
1797 ddg_node_ptr v_node = e->dest;
1798 if (TEST_BIT (sched_nodes, v_node->cuid)
1799 && (up == SCHED_TIME (v_node) - e->latency + (e->distance * ii)))
1800 if (SCHED_TIME (v_node) < upper)
1803 upper = SCHED_TIME (v_node);
1807 if (crit_succ != NULL)
1809 crit_cycle = SCHED_TIME (crit_succ);
1810 return SMODULO (crit_cycle, ii);
1814 fprintf (dump_file, "Both crit_pred and crit_succ are NULL\n");
1816 return SMODULO ((low + up + 1) / 2, ii);
1820 verify_partial_schedule (partial_schedule_ptr ps, sbitmap sched_nodes)
1823 ps_insn_ptr crr_insn;
1825 for (row = 0; row < ps->ii; row++)
1826 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
1828 ddg_node_ptr u = crr_insn->node;
1830 gcc_assert (TEST_BIT (sched_nodes, u->cuid));
1831 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
1832 popcount (sched_nodes) == number of insns in ps. */
1833 gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
1834 gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
1839 /* This page implements the algorithm for ordering the nodes of a DDG
1840 for modulo scheduling, activated through the
1841 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
1843 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
1844 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
1845 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
1846 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
1847 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
1848 #define DEPTH(x) (ASAP ((x)))
1850 typedef struct node_order_params * nopa;
1852 static void order_nodes_of_sccs (ddg_all_sccs_ptr, int * result);
1853 static int order_nodes_in_scc (ddg_ptr, sbitmap, sbitmap, int*, int);
1854 static nopa calculate_order_params (ddg_ptr, int mii);
1855 static int find_max_asap (ddg_ptr, sbitmap);
1856 static int find_max_hv_min_mob (ddg_ptr, sbitmap);
1857 static int find_max_dv_min_mob (ddg_ptr, sbitmap);
1859 enum sms_direction {BOTTOMUP, TOPDOWN};
1861 struct node_order_params
1868 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
1870 check_nodes_order (int *node_order, int num_nodes)
1873 sbitmap tmp = sbitmap_alloc (num_nodes);
1878 fprintf (dump_file, "SMS final nodes order: \n");
1880 for (i = 0; i < num_nodes; i++)
1882 int u = node_order[i];
1885 fprintf (dump_file, "%d ", u);
1886 gcc_assert (u < num_nodes && u >= 0 && !TEST_BIT (tmp, u));
1892 fprintf (dump_file, "\n");
1897 /* Order the nodes of G for scheduling and pass the result in
1898 NODE_ORDER. Also set aux.count of each node to ASAP.
1899 Return the recMII for the given DDG. */
1901 sms_order_nodes (ddg_ptr g, int mii, int * node_order)
1905 ddg_all_sccs_ptr sccs = create_ddg_all_sccs (g);
1907 nopa nops = calculate_order_params (g, mii);
1910 print_sccs (dump_file, sccs, g);
1912 order_nodes_of_sccs (sccs, node_order);
1914 if (sccs->num_sccs > 0)
1915 /* First SCC has the largest recurrence_length. */
1916 rec_mii = sccs->sccs[0]->recurrence_length;
1918 /* Save ASAP before destroying node_order_params. */
1919 for (i = 0; i < g->num_nodes; i++)
1921 ddg_node_ptr v = &g->nodes[i];
1922 v->aux.count = ASAP (v);
1926 free_ddg_all_sccs (sccs);
1927 check_nodes_order (node_order, g->num_nodes);
1933 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs, int * node_order)
1936 ddg_ptr g = all_sccs->ddg;
1937 int num_nodes = g->num_nodes;
1938 sbitmap prev_sccs = sbitmap_alloc (num_nodes);
1939 sbitmap on_path = sbitmap_alloc (num_nodes);
1940 sbitmap tmp = sbitmap_alloc (num_nodes);
1941 sbitmap ones = sbitmap_alloc (num_nodes);
1943 sbitmap_zero (prev_sccs);
1944 sbitmap_ones (ones);
1946 /* Perfrom the node ordering starting from the SCC with the highest recMII.
1947 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
1948 for (i = 0; i < all_sccs->num_sccs; i++)
1950 ddg_scc_ptr scc = all_sccs->sccs[i];
1952 /* Add nodes on paths from previous SCCs to the current SCC. */
1953 find_nodes_on_paths (on_path, g, prev_sccs, scc->nodes);
1954 sbitmap_a_or_b (tmp, scc->nodes, on_path);
1956 /* Add nodes on paths from the current SCC to previous SCCs. */
1957 find_nodes_on_paths (on_path, g, scc->nodes, prev_sccs);
1958 sbitmap_a_or_b (tmp, tmp, on_path);
1960 /* Remove nodes of previous SCCs from current extended SCC. */
1961 sbitmap_difference (tmp, tmp, prev_sccs);
1963 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
1964 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
1967 /* Handle the remaining nodes that do not belong to any scc. Each call
1968 to order_nodes_in_scc handles a single connected component. */
1969 while (pos < g->num_nodes)
1971 sbitmap_difference (tmp, ones, prev_sccs);
1972 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
1974 sbitmap_free (prev_sccs);
1975 sbitmap_free (on_path);
1977 sbitmap_free (ones);
1980 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
1981 static struct node_order_params *
1982 calculate_order_params (ddg_ptr g, int mii ATTRIBUTE_UNUSED)
1986 int num_nodes = g->num_nodes;
1988 /* Allocate a place to hold ordering params for each node in the DDG. */
1989 nopa node_order_params_arr;
1991 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
1992 node_order_params_arr = (nopa) xcalloc (num_nodes,
1993 sizeof (struct node_order_params));
1995 /* Set the aux pointer of each node to point to its order_params structure. */
1996 for (u = 0; u < num_nodes; u++)
1997 g->nodes[u].aux.info = &node_order_params_arr[u];
1999 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2000 calculate ASAP, ALAP, mobility, distance, and height for each node
2001 in the dependence (direct acyclic) graph. */
2003 /* We assume that the nodes in the array are in topological order. */
2006 for (u = 0; u < num_nodes; u++)
2008 ddg_node_ptr u_node = &g->nodes[u];
2011 for (e = u_node->in; e; e = e->next_in)
2012 if (e->distance == 0)
2013 ASAP (u_node) = MAX (ASAP (u_node),
2014 ASAP (e->src) + e->latency);
2015 max_asap = MAX (max_asap, ASAP (u_node));
2018 for (u = num_nodes - 1; u > -1; u--)
2020 ddg_node_ptr u_node = &g->nodes[u];
2022 ALAP (u_node) = max_asap;
2023 HEIGHT (u_node) = 0;
2024 for (e = u_node->out; e; e = e->next_out)
2025 if (e->distance == 0)
2027 ALAP (u_node) = MIN (ALAP (u_node),
2028 ALAP (e->dest) - e->latency);
2029 HEIGHT (u_node) = MAX (HEIGHT (u_node),
2030 HEIGHT (e->dest) + e->latency);
2035 fprintf (dump_file, "\nOrder params\n");
2036 for (u = 0; u < num_nodes; u++)
2038 ddg_node_ptr u_node = &g->nodes[u];
2040 fprintf (dump_file, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u,
2041 ASAP (u_node), ALAP (u_node), HEIGHT (u_node));
2045 return node_order_params_arr;
2049 find_max_asap (ddg_ptr g, sbitmap nodes)
2054 sbitmap_iterator sbi;
2056 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
2058 ddg_node_ptr u_node = &g->nodes[u];
2060 if (max_asap < ASAP (u_node))
2062 max_asap = ASAP (u_node);
2070 find_max_hv_min_mob (ddg_ptr g, sbitmap nodes)
2074 int min_mob = INT_MAX;
2076 sbitmap_iterator sbi;
2078 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
2080 ddg_node_ptr u_node = &g->nodes[u];
2082 if (max_hv < HEIGHT (u_node))
2084 max_hv = HEIGHT (u_node);
2085 min_mob = MOB (u_node);
2088 else if ((max_hv == HEIGHT (u_node))
2089 && (min_mob > MOB (u_node)))
2091 min_mob = MOB (u_node);
2099 find_max_dv_min_mob (ddg_ptr g, sbitmap nodes)
2103 int min_mob = INT_MAX;
2105 sbitmap_iterator sbi;
2107 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
2109 ddg_node_ptr u_node = &g->nodes[u];
2111 if (max_dv < DEPTH (u_node))
2113 max_dv = DEPTH (u_node);
2114 min_mob = MOB (u_node);
2117 else if ((max_dv == DEPTH (u_node))
2118 && (min_mob > MOB (u_node)))
2120 min_mob = MOB (u_node);
2127 /* Places the nodes of SCC into the NODE_ORDER array starting
2128 at position POS, according to the SMS ordering algorithm.
2129 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2130 the NODE_ORDER array, starting from position zero. */
2132 order_nodes_in_scc (ddg_ptr g, sbitmap nodes_ordered, sbitmap scc,
2133 int * node_order, int pos)
2135 enum sms_direction dir;
2136 int num_nodes = g->num_nodes;
2137 sbitmap workset = sbitmap_alloc (num_nodes);
2138 sbitmap tmp = sbitmap_alloc (num_nodes);
2139 sbitmap zero_bitmap = sbitmap_alloc (num_nodes);
2140 sbitmap predecessors = sbitmap_alloc (num_nodes);
2141 sbitmap successors = sbitmap_alloc (num_nodes);
2143 sbitmap_zero (predecessors);
2144 find_predecessors (predecessors, g, nodes_ordered);
2146 sbitmap_zero (successors);
2147 find_successors (successors, g, nodes_ordered);
2150 if (sbitmap_a_and_b_cg (tmp, predecessors, scc))
2152 sbitmap_copy (workset, tmp);
2155 else if (sbitmap_a_and_b_cg (tmp, successors, scc))
2157 sbitmap_copy (workset, tmp);
2164 sbitmap_zero (workset);
2165 if ((u = find_max_asap (g, scc)) >= 0)
2166 SET_BIT (workset, u);
2170 sbitmap_zero (zero_bitmap);
2171 while (!sbitmap_equal (workset, zero_bitmap))
2174 ddg_node_ptr v_node;
2175 sbitmap v_node_preds;
2176 sbitmap v_node_succs;
2180 while (!sbitmap_equal (workset, zero_bitmap))
2182 v = find_max_hv_min_mob (g, workset);
2183 v_node = &g->nodes[v];
2184 node_order[pos++] = v;
2185 v_node_succs = NODE_SUCCESSORS (v_node);
2186 sbitmap_a_and_b (tmp, v_node_succs, scc);
2188 /* Don't consider the already ordered successors again. */
2189 sbitmap_difference (tmp, tmp, nodes_ordered);
2190 sbitmap_a_or_b (workset, workset, tmp);
2191 RESET_BIT (workset, v);
2192 SET_BIT (nodes_ordered, v);
2195 sbitmap_zero (predecessors);
2196 find_predecessors (predecessors, g, nodes_ordered);
2197 sbitmap_a_and_b (workset, predecessors, scc);
2201 while (!sbitmap_equal (workset, zero_bitmap))
2203 v = find_max_dv_min_mob (g, workset);
2204 v_node = &g->nodes[v];
2205 node_order[pos++] = v;
2206 v_node_preds = NODE_PREDECESSORS (v_node);
2207 sbitmap_a_and_b (tmp, v_node_preds, scc);
2209 /* Don't consider the already ordered predecessors again. */
2210 sbitmap_difference (tmp, tmp, nodes_ordered);
2211 sbitmap_a_or_b (workset, workset, tmp);
2212 RESET_BIT (workset, v);
2213 SET_BIT (nodes_ordered, v);
2216 sbitmap_zero (successors);
2217 find_successors (successors, g, nodes_ordered);
2218 sbitmap_a_and_b (workset, successors, scc);
2222 sbitmap_free (workset);
2223 sbitmap_free (zero_bitmap);
2224 sbitmap_free (predecessors);
2225 sbitmap_free (successors);
2230 /* This page contains functions for manipulating partial-schedules during
2231 modulo scheduling. */
2233 /* Create a partial schedule and allocate a memory to hold II rows. */
2235 static partial_schedule_ptr
2236 create_partial_schedule (int ii, ddg_ptr g, int history)
2238 partial_schedule_ptr ps = XNEW (struct partial_schedule);
2239 ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
2241 ps->history = history;
2242 ps->min_cycle = INT_MAX;
2243 ps->max_cycle = INT_MIN;
2249 /* Free the PS_INSNs in rows array of the given partial schedule.
2250 ??? Consider caching the PS_INSN's. */
2252 free_ps_insns (partial_schedule_ptr ps)
2256 for (i = 0; i < ps->ii; i++)
2260 ps_insn_ptr ps_insn = ps->rows[i]->next_in_row;
2263 ps->rows[i] = ps_insn;
2269 /* Free all the memory allocated to the partial schedule. */
2272 free_partial_schedule (partial_schedule_ptr ps)
2281 /* Clear the rows array with its PS_INSNs, and create a new one with
2285 reset_partial_schedule (partial_schedule_ptr ps, int new_ii)
2290 if (new_ii == ps->ii)
2292 ps->rows = (ps_insn_ptr *) xrealloc (ps->rows, new_ii
2293 * sizeof (ps_insn_ptr));
2294 memset (ps->rows, 0, new_ii * sizeof (ps_insn_ptr));
2296 ps->min_cycle = INT_MAX;
2297 ps->max_cycle = INT_MIN;
2300 /* Prints the partial schedule as an ii rows array, for each rows
2301 print the ids of the insns in it. */
2303 print_partial_schedule (partial_schedule_ptr ps, FILE *dump)
2307 for (i = 0; i < ps->ii; i++)
2309 ps_insn_ptr ps_i = ps->rows[i];
2311 fprintf (dump, "\n[CYCLE %d ]: ", i);
2314 fprintf (dump, "%d, ",
2315 INSN_UID (ps_i->node->insn));
2316 ps_i = ps_i->next_in_row;
2321 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2323 create_ps_insn (ddg_node_ptr node, int rest_count, int cycle)
2325 ps_insn_ptr ps_i = XNEW (struct ps_insn);
2328 ps_i->next_in_row = NULL;
2329 ps_i->prev_in_row = NULL;
2330 ps_i->row_rest_count = rest_count;
2331 ps_i->cycle = cycle;
2337 /* Removes the given PS_INSN from the partial schedule. Returns false if the
2338 node is not found in the partial schedule, else returns true. */
2340 remove_node_from_ps (partial_schedule_ptr ps, ps_insn_ptr ps_i)
2347 row = SMODULO (ps_i->cycle, ps->ii);
2348 if (! ps_i->prev_in_row)
2350 if (ps_i != ps->rows[row])
2353 ps->rows[row] = ps_i->next_in_row;
2355 ps->rows[row]->prev_in_row = NULL;
2359 ps_i->prev_in_row->next_in_row = ps_i->next_in_row;
2360 if (ps_i->next_in_row)
2361 ps_i->next_in_row->prev_in_row = ps_i->prev_in_row;
2367 /* Unlike what literature describes for modulo scheduling (which focuses
2368 on VLIW machines) the order of the instructions inside a cycle is
2369 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2370 where the current instruction should go relative to the already
2371 scheduled instructions in the given cycle. Go over these
2372 instructions and find the first possible column to put it in. */
2374 ps_insn_find_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
2375 sbitmap must_precede, sbitmap must_follow)
2377 ps_insn_ptr next_ps_i;
2378 ps_insn_ptr first_must_follow = NULL;
2379 ps_insn_ptr last_must_precede = NULL;
2385 row = SMODULO (ps_i->cycle, ps->ii);
2387 /* Find the first must follow and the last must precede
2388 and insert the node immediately after the must precede
2389 but make sure that it there is no must follow after it. */
2390 for (next_ps_i = ps->rows[row];
2392 next_ps_i = next_ps_i->next_in_row)
2394 if (TEST_BIT (must_follow, next_ps_i->node->cuid)
2395 && ! first_must_follow)
2396 first_must_follow = next_ps_i;
2397 if (TEST_BIT (must_precede, next_ps_i->node->cuid))
2399 /* If we have already met a node that must follow, then
2400 there is no possible column. */
2401 if (first_must_follow)
2404 last_must_precede = next_ps_i;
2408 /* Now insert the node after INSERT_AFTER_PSI. */
2410 if (! last_must_precede)
2412 ps_i->next_in_row = ps->rows[row];
2413 ps_i->prev_in_row = NULL;
2414 if (ps_i->next_in_row)
2415 ps_i->next_in_row->prev_in_row = ps_i;
2416 ps->rows[row] = ps_i;
2420 ps_i->next_in_row = last_must_precede->next_in_row;
2421 last_must_precede->next_in_row = ps_i;
2422 ps_i->prev_in_row = last_must_precede;
2423 if (ps_i->next_in_row)
2424 ps_i->next_in_row->prev_in_row = ps_i;
2430 /* Advances the PS_INSN one column in its current row; returns false
2431 in failure and true in success. Bit N is set in MUST_FOLLOW if
2432 the node with cuid N must be come after the node pointed to by
2433 PS_I when scheduled in the same cycle. */
2435 ps_insn_advance_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
2436 sbitmap must_follow)
2438 ps_insn_ptr prev, next;
2440 ddg_node_ptr next_node;
2445 row = SMODULO (ps_i->cycle, ps->ii);
2447 if (! ps_i->next_in_row)
2450 next_node = ps_i->next_in_row->node;
2452 /* Check if next_in_row is dependent on ps_i, both having same sched
2453 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
2454 if (TEST_BIT (must_follow, next_node->cuid))
2457 /* Advance PS_I over its next_in_row in the doubly linked list. */
2458 prev = ps_i->prev_in_row;
2459 next = ps_i->next_in_row;
2461 if (ps_i == ps->rows[row])
2462 ps->rows[row] = next;
2464 ps_i->next_in_row = next->next_in_row;
2466 if (next->next_in_row)
2467 next->next_in_row->prev_in_row = ps_i;
2469 next->next_in_row = ps_i;
2470 ps_i->prev_in_row = next;
2472 next->prev_in_row = prev;
2474 prev->next_in_row = next;
2479 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
2480 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
2481 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
2482 before/after (respectively) the node pointed to by PS_I when scheduled
2483 in the same cycle. */
2485 add_node_to_ps (partial_schedule_ptr ps, ddg_node_ptr node, int cycle,
2486 sbitmap must_precede, sbitmap must_follow)
2490 int row = SMODULO (cycle, ps->ii);
2493 && ps->rows[row]->row_rest_count >= issue_rate)
2497 rest_count += ps->rows[row]->row_rest_count;
2499 ps_i = create_ps_insn (node, rest_count, cycle);
2501 /* Finds and inserts PS_I according to MUST_FOLLOW and
2503 if (! ps_insn_find_column (ps, ps_i, must_precede, must_follow))
2512 /* Advance time one cycle. Assumes DFA is being used. */
2514 advance_one_cycle (void)
2516 if (targetm.sched.dfa_pre_cycle_insn)
2517 state_transition (curr_state,
2518 targetm.sched.dfa_pre_cycle_insn ());
2520 state_transition (curr_state, NULL);
2522 if (targetm.sched.dfa_post_cycle_insn)
2523 state_transition (curr_state,
2524 targetm.sched.dfa_post_cycle_insn ());
2529 /* Checks if PS has resource conflicts according to DFA, starting from
2530 FROM cycle to TO cycle; returns true if there are conflicts and false
2531 if there are no conflicts. Assumes DFA is being used. */
2533 ps_has_conflicts (partial_schedule_ptr ps, int from, int to)
2537 state_reset (curr_state);
2539 for (cycle = from; cycle <= to; cycle++)
2541 ps_insn_ptr crr_insn;
2542 /* Holds the remaining issue slots in the current row. */
2543 int can_issue_more = issue_rate;
2545 /* Walk through the DFA for the current row. */
2546 for (crr_insn = ps->rows[SMODULO (cycle, ps->ii)];
2548 crr_insn = crr_insn->next_in_row)
2550 rtx insn = crr_insn->node->insn;
2555 /* Check if there is room for the current insn. */
2556 if (!can_issue_more || state_dead_lock_p (curr_state))
2559 /* Update the DFA state and return with failure if the DFA found
2560 recource conflicts. */
2561 if (state_transition (curr_state, insn) >= 0)
2564 if (targetm.sched.variable_issue)
2566 targetm.sched.variable_issue (sched_dump, sched_verbose,
2567 insn, can_issue_more);
2568 /* A naked CLOBBER or USE generates no instruction, so don't
2569 let them consume issue slots. */
2570 else if (GET_CODE (PATTERN (insn)) != USE
2571 && GET_CODE (PATTERN (insn)) != CLOBBER)
2575 /* Advance the DFA to the next cycle. */
2576 advance_one_cycle ();
2581 /* Checks if the given node causes resource conflicts when added to PS at
2582 cycle C. If not the node is added to PS and returned; otherwise zero
2583 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
2584 cuid N must be come before/after (respectively) the node pointed to by
2585 PS_I when scheduled in the same cycle. */
2587 ps_add_node_check_conflicts (partial_schedule_ptr ps, ddg_node_ptr n,
2588 int c, sbitmap must_precede,
2589 sbitmap must_follow)
2591 int has_conflicts = 0;
2594 /* First add the node to the PS, if this succeeds check for
2595 conflicts, trying different issue slots in the same row. */
2596 if (! (ps_i = add_node_to_ps (ps, n, c, must_precede, must_follow)))
2597 return NULL; /* Failed to insert the node at the given cycle. */
2599 has_conflicts = ps_has_conflicts (ps, c, c)
2601 && ps_has_conflicts (ps,
2605 /* Try different issue slots to find one that the given node can be
2606 scheduled in without conflicts. */
2607 while (has_conflicts)
2609 if (! ps_insn_advance_column (ps, ps_i, must_follow))
2611 has_conflicts = ps_has_conflicts (ps, c, c)
2613 && ps_has_conflicts (ps,
2620 remove_node_from_ps (ps, ps_i);
2624 ps->min_cycle = MIN (ps->min_cycle, c);
2625 ps->max_cycle = MAX (ps->max_cycle, c);
2629 /* Rotate the rows of PS such that insns scheduled at time
2630 START_CYCLE will appear in row 0. Updates max/min_cycles. */
2632 rotate_partial_schedule (partial_schedule_ptr ps, int start_cycle)
2634 int i, row, backward_rotates;
2635 int last_row = ps->ii - 1;
2637 if (start_cycle == 0)
2640 backward_rotates = SMODULO (start_cycle, ps->ii);
2642 /* Revisit later and optimize this into a single loop. */
2643 for (i = 0; i < backward_rotates; i++)
2645 ps_insn_ptr first_row = ps->rows[0];
2647 for (row = 0; row < last_row; row++)
2648 ps->rows[row] = ps->rows[row+1];
2650 ps->rows[last_row] = first_row;
2653 ps->max_cycle -= start_cycle;
2654 ps->min_cycle -= start_cycle;
2657 #endif /* INSN_SCHEDULING */
2660 gate_handle_sms (void)
2662 return (optimize > 0 && flag_modulo_sched);
2666 /* Run instruction scheduler. */
2667 /* Perform SMS module scheduling. */
2669 rest_of_handle_sms (void)
2671 #ifdef INSN_SCHEDULING
2674 /* Collect loop information to be used in SMS. */
2675 cfg_layout_initialize (0);
2678 /* Update the life information, because we add pseudos. */
2679 max_regno = max_reg_num ();
2681 /* Finalize layout changes. */
2683 if (bb->next_bb != EXIT_BLOCK_PTR)
2684 bb->aux = bb->next_bb;
2685 free_dominance_info (CDI_DOMINATORS);
2686 cfg_layout_finalize ();
2687 #endif /* INSN_SCHEDULING */
2691 struct tree_opt_pass pass_sms =
2694 gate_handle_sms, /* gate */
2695 rest_of_handle_sms, /* execute */
2698 0, /* static_pass_number */
2700 0, /* properties_required */
2701 0, /* properties_provided */
2702 0, /* properties_destroyed */
2703 TODO_dump_func, /* todo_flags_start */
2704 TODO_df_finish | TODO_verify_rtl_sharing |
2706 TODO_ggc_collect, /* todo_flags_finish */