1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
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"
27 #include "diagnostic-core.h"
30 #include "hard-reg-set.h"
34 #include "insn-config.h"
35 #include "insn-attr.h"
38 #include "sched-int.h"
40 #include "cfglayout.h"
48 #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 CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \
121 /* The stage count of ps. */
122 #define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count)
124 /* A single instruction in the partial schedule. */
127 /* The corresponding DDG_NODE. */
130 /* The (absolute) cycle in which the PS instruction is scheduled.
131 Same as SCHED_TIME (node). */
134 /* The next/prev PS_INSN in the same row. */
135 ps_insn_ptr next_in_row,
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 /* rows_length[i] holds the number of instructions in the row.
152 It is used only (as an optimization) to back off quickly from
153 trying to schedule a node in a full row; that is, to avoid running
154 through futile DFA state transitions. */
157 /* The earliest absolute cycle of an insn in the partial schedule. */
160 /* The latest absolute cycle of an insn in the partial schedule. */
163 ddg_ptr g; /* The DDG of the insns in the partial schedule. */
165 int stage_count; /* The stage count of the partial schedule. */
168 /* We use this to record all the register replacements we do in
169 the kernel so we can undo SMS if it is not profitable. */
170 struct undo_replace_buff_elem
175 struct undo_replace_buff_elem *next;
180 static partial_schedule_ptr create_partial_schedule (int ii, ddg_ptr, int history);
181 static void free_partial_schedule (partial_schedule_ptr);
182 static void reset_partial_schedule (partial_schedule_ptr, int new_ii);
183 void print_partial_schedule (partial_schedule_ptr, FILE *);
184 static void verify_partial_schedule (partial_schedule_ptr, sbitmap);
185 static ps_insn_ptr ps_add_node_check_conflicts (partial_schedule_ptr,
186 ddg_node_ptr node, int cycle,
187 sbitmap must_precede,
188 sbitmap must_follow);
189 static void rotate_partial_schedule (partial_schedule_ptr, int);
190 void set_row_column_for_ps (partial_schedule_ptr);
191 static void ps_insert_empty_row (partial_schedule_ptr, int, sbitmap);
192 static int compute_split_row (sbitmap, int, int, int, ddg_node_ptr);
195 /* This page defines constants and structures for the modulo scheduling
198 static int sms_order_nodes (ddg_ptr, int, int *, int *);
199 static void set_node_sched_params (ddg_ptr);
200 static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int, int *);
201 static void permute_partial_schedule (partial_schedule_ptr, rtx);
202 static void generate_prolog_epilog (partial_schedule_ptr, struct loop *,
204 static void duplicate_insns_of_cycles (partial_schedule_ptr,
206 static int calculate_stage_count (partial_schedule_ptr ps);
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 (const_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 used ATTRIBUTE_UNUSED)
260 static struct common_sched_info_def sms_common_sched_info;
262 static struct sched_deps_info_def sms_sched_deps_info =
264 compute_jump_reg_dependencies,
265 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
270 static struct haifa_sched_info sms_sched_info =
279 NULL, /* insn_finishes_block_p */
284 NULL, NULL, NULL, NULL,
289 /* Given HEAD and TAIL which are the first and last insns in a loop;
290 return the register which controls the loop. Return zero if it has
291 more than one occurrence in the loop besides the control part or the
292 do-loop pattern is not of the form we expect. */
294 doloop_register_get (rtx head ATTRIBUTE_UNUSED, rtx tail ATTRIBUTE_UNUSED)
296 #ifdef HAVE_doloop_end
297 rtx reg, condition, insn, first_insn_not_to_check;
302 /* TODO: Free SMS's dependence on doloop_condition_get. */
303 condition = doloop_condition_get (tail);
307 if (REG_P (XEXP (condition, 0)))
308 reg = XEXP (condition, 0);
309 else if (GET_CODE (XEXP (condition, 0)) == PLUS
310 && REG_P (XEXP (XEXP (condition, 0), 0)))
311 reg = XEXP (XEXP (condition, 0), 0);
315 /* Check that the COUNT_REG has no other occurrences in the loop
316 until the decrement. We assume the control part consists of
317 either a single (parallel) branch-on-count or a (non-parallel)
318 branch immediately preceded by a single (decrement) insn. */
319 first_insn_not_to_check = (GET_CODE (PATTERN (tail)) == PARALLEL ? tail
320 : prev_nondebug_insn (tail));
322 for (insn = head; insn != first_insn_not_to_check; insn = NEXT_INSN (insn))
323 if (!DEBUG_INSN_P (insn) && reg_mentioned_p (reg, insn))
327 fprintf (dump_file, "SMS count_reg found ");
328 print_rtl_single (dump_file, reg);
329 fprintf (dump_file, " outside control in insn:\n");
330 print_rtl_single (dump_file, insn);
342 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
343 that the number of iterations is a compile-time constant. If so,
344 return the rtx that sets COUNT_REG to a constant, and set COUNT to
345 this constant. Otherwise return 0. */
347 const_iteration_count (rtx count_reg, basic_block pre_header,
348 HOST_WIDEST_INT * count)
356 get_ebb_head_tail (pre_header, pre_header, &head, &tail);
358 for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn))
359 if (NONDEBUG_INSN_P (insn) && single_set (insn) &&
360 rtx_equal_p (count_reg, SET_DEST (single_set (insn))))
362 rtx pat = single_set (insn);
364 if (CONST_INT_P (SET_SRC (pat)))
366 *count = INTVAL (SET_SRC (pat));
376 /* A very simple resource-based lower bound on the initiation interval.
377 ??? Improve the accuracy of this bound by considering the
378 utilization of various units. */
382 if (targetm.sched.sms_res_mii)
383 return targetm.sched.sms_res_mii (g);
385 return ((g->num_nodes - g->num_debug) / issue_rate);
389 /* Points to the array that contains the sched data for each node. */
390 static node_sched_params_ptr node_sched_params;
392 /* Allocate sched_params for each node and initialize it. Assumes that
393 the aux field of each node contain the asap bound (computed earlier),
394 and copies it into the sched_params field. */
396 set_node_sched_params (ddg_ptr g)
400 /* Allocate for each node in the DDG a place to hold the "sched_data". */
401 /* Initialize ASAP/ALAP/HIGHT to zero. */
402 node_sched_params = (node_sched_params_ptr)
403 xcalloc (g->num_nodes,
404 sizeof (struct node_sched_params));
406 /* Set the pointer of the general data of the node to point to the
407 appropriate sched_params structure. */
408 for (i = 0; i < g->num_nodes; i++)
410 /* Watch out for aliasing problems? */
411 node_sched_params[i].asap = g->nodes[i].aux.count;
412 g->nodes[i].aux.info = &node_sched_params[i];
417 print_node_sched_params (FILE *file, int num_nodes, ddg_ptr g)
423 for (i = 0; i < num_nodes; i++)
425 node_sched_params_ptr nsp = &node_sched_params[i];
426 rtx reg_move = nsp->first_reg_move;
429 fprintf (file, "Node = %d; INSN = %d\n", i,
430 (INSN_UID (g->nodes[i].insn)));
431 fprintf (file, " asap = %d:\n", nsp->asap);
432 fprintf (file, " time = %d:\n", nsp->time);
433 fprintf (file, " nreg_moves = %d:\n", nsp->nreg_moves);
434 for (j = 0; j < nsp->nreg_moves; j++)
436 fprintf (file, " reg_move = ");
437 print_rtl_single (file, reg_move);
438 reg_move = PREV_INSN (reg_move);
444 Breaking intra-loop register anti-dependences:
445 Each intra-loop register anti-dependence implies a cross-iteration true
446 dependence of distance 1. Therefore, we can remove such false dependencies
447 and figure out if the partial schedule broke them by checking if (for a
448 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
449 if so generate a register move. The number of such moves is equal to:
450 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
451 nreg_moves = ----------------------------------- + 1 - { dependence.
454 static struct undo_replace_buff_elem *
455 generate_reg_moves (partial_schedule_ptr ps, bool rescan)
460 struct undo_replace_buff_elem *reg_move_replaces = NULL;
462 for (i = 0; i < g->num_nodes; i++)
464 ddg_node_ptr u = &g->nodes[i];
466 int nreg_moves = 0, i_reg_move;
467 sbitmap *uses_of_defs;
469 rtx prev_reg, old_reg;
471 /* Compute the number of reg_moves needed for u, by looking at life
472 ranges started at u (excluding self-loops). */
473 for (e = u->out; e; e = e->next_out)
474 if (e->type == TRUE_DEP && e->dest != e->src)
476 int nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
478 if (e->distance == 1)
479 nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
481 /* If dest precedes src in the schedule of the kernel, then dest
482 will read before src writes and we can save one reg_copy. */
483 if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)
484 && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))
487 nreg_moves = MAX (nreg_moves, nreg_moves4e);
493 /* Every use of the register defined by node may require a different
494 copy of this register, depending on the time the use is scheduled.
495 Set a bitmap vector, telling which nodes use each copy of this
497 uses_of_defs = sbitmap_vector_alloc (nreg_moves, g->num_nodes);
498 sbitmap_vector_zero (uses_of_defs, nreg_moves);
499 for (e = u->out; e; e = e->next_out)
500 if (e->type == TRUE_DEP && e->dest != e->src)
502 int dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
504 if (e->distance == 1)
505 dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
507 if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)
508 && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))
512 SET_BIT (uses_of_defs[dest_copy - 1], e->dest->cuid);
515 /* Now generate the reg_moves, attaching relevant uses to them. */
516 SCHED_NREG_MOVES (u) = nreg_moves;
517 old_reg = prev_reg = copy_rtx (SET_DEST (single_set (u->insn)));
518 /* Insert the reg-moves right before the notes which precede
519 the insn they relates to. */
520 last_reg_move = u->first_note;
522 for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
524 unsigned int i_use = 0;
525 rtx new_reg = gen_reg_rtx (GET_MODE (prev_reg));
526 rtx reg_move = gen_move_insn (new_reg, prev_reg);
527 sbitmap_iterator sbi;
529 add_insn_before (reg_move, last_reg_move, NULL);
530 last_reg_move = reg_move;
532 if (!SCHED_FIRST_REG_MOVE (u))
533 SCHED_FIRST_REG_MOVE (u) = reg_move;
535 EXECUTE_IF_SET_IN_SBITMAP (uses_of_defs[i_reg_move], 0, i_use, sbi)
537 struct undo_replace_buff_elem *rep;
539 rep = (struct undo_replace_buff_elem *)
540 xcalloc (1, sizeof (struct undo_replace_buff_elem));
541 rep->insn = g->nodes[i_use].insn;
542 rep->orig_reg = old_reg;
543 rep->new_reg = new_reg;
545 if (! reg_move_replaces)
546 reg_move_replaces = rep;
549 rep->next = reg_move_replaces;
550 reg_move_replaces = rep;
553 replace_rtx (g->nodes[i_use].insn, old_reg, new_reg);
555 df_insn_rescan (g->nodes[i_use].insn);
560 sbitmap_vector_free (uses_of_defs);
562 return reg_move_replaces;
565 /* Free memory allocated for the undo buffer. */
567 free_undo_replace_buff (struct undo_replace_buff_elem *reg_move_replaces)
570 while (reg_move_replaces)
572 struct undo_replace_buff_elem *rep = reg_move_replaces;
574 reg_move_replaces = reg_move_replaces->next;
579 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
580 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
581 will move to cycle zero. */
583 reset_sched_times (partial_schedule_ptr ps, int amount)
587 ps_insn_ptr crr_insn;
589 for (row = 0; row < ii; row++)
590 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
592 ddg_node_ptr u = crr_insn->node;
593 int normalized_time = SCHED_TIME (u) - amount;
594 int new_min_cycle = PS_MIN_CYCLE (ps) - amount;
595 int sc_until_cycle_zero, stage;
599 /* Print the scheduling times after the rotation. */
600 fprintf (dump_file, "crr_insn->node=%d (insn id %d), "
601 "crr_insn->cycle=%d, min_cycle=%d", crr_insn->node->cuid,
602 INSN_UID (crr_insn->node->insn), normalized_time,
604 if (JUMP_P (crr_insn->node->insn))
605 fprintf (dump_file, " (branch)");
606 fprintf (dump_file, "\n");
609 gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
610 gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
611 SCHED_TIME (u) = normalized_time;
612 SCHED_ROW (u) = SMODULO (normalized_time, ii);
614 /* The calculation of stage count is done adding the number
615 of stages before cycle zero and after cycle zero. */
616 sc_until_cycle_zero = CALC_STAGE_COUNT (-1, new_min_cycle, ii);
618 if (SCHED_TIME (u) < 0)
620 stage = CALC_STAGE_COUNT (-1, SCHED_TIME (u), ii);
621 SCHED_STAGE (u) = sc_until_cycle_zero - stage;
625 stage = CALC_STAGE_COUNT (SCHED_TIME (u), 0, ii);
626 SCHED_STAGE (u) = sc_until_cycle_zero + stage - 1;
631 /* Set SCHED_COLUMN of each node according to its position in PS. */
633 set_columns_for_ps (partial_schedule_ptr ps)
637 for (row = 0; row < ps->ii; row++)
639 ps_insn_ptr cur_insn = ps->rows[row];
642 for (; cur_insn; cur_insn = cur_insn->next_in_row)
643 SCHED_COLUMN (cur_insn->node) = column++;
647 /* Permute the insns according to their order in PS, from row 0 to
648 row ii-1, and position them right before LAST. This schedules
649 the insns of the loop kernel. */
651 permute_partial_schedule (partial_schedule_ptr ps, rtx last)
657 for (row = 0; row < ii ; row++)
658 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
659 if (PREV_INSN (last) != ps_ij->node->insn)
660 reorder_insns_nobb (ps_ij->node->first_note, ps_ij->node->insn,
665 duplicate_insns_of_cycles (partial_schedule_ptr ps, int from_stage,
666 int to_stage, int for_prolog, rtx count_reg)
671 for (row = 0; row < ps->ii; row++)
672 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
674 ddg_node_ptr u_node = ps_ij->node;
676 rtx reg_move = NULL_RTX;
678 /* Do not duplicate any insn which refers to count_reg as it
679 belongs to the control part.
680 The closing branch is scheduled as well and thus should
682 TODO: This should be done by analyzing the control part of
684 if (reg_mentioned_p (count_reg, u_node->insn)
685 || JUMP_P (ps_ij->node->insn))
690 /* SCHED_STAGE (u_node) >= from_stage == 0. Generate increasing
691 number of reg_moves starting with the second occurrence of
692 u_node, which is generated if its SCHED_STAGE <= to_stage. */
693 i_reg_moves = to_stage - SCHED_STAGE (u_node) + 1;
694 i_reg_moves = MAX (i_reg_moves, 0);
695 i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));
697 /* The reg_moves start from the *first* reg_move backwards. */
700 reg_move = SCHED_FIRST_REG_MOVE (u_node);
701 for (j = 1; j < i_reg_moves; j++)
702 reg_move = PREV_INSN (reg_move);
705 else /* It's for the epilog. */
707 /* SCHED_STAGE (u_node) <= to_stage. Generate all reg_moves,
708 starting to decrease one stage after u_node no longer occurs;
709 that is, generate all reg_moves until
710 SCHED_STAGE (u_node) == from_stage - 1. */
711 i_reg_moves = SCHED_NREG_MOVES (u_node)
712 - (from_stage - SCHED_STAGE (u_node) - 1);
713 i_reg_moves = MAX (i_reg_moves, 0);
714 i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));
716 /* The reg_moves start from the *last* reg_move forwards. */
719 reg_move = SCHED_FIRST_REG_MOVE (u_node);
720 for (j = 1; j < SCHED_NREG_MOVES (u_node); j++)
721 reg_move = PREV_INSN (reg_move);
725 for (j = 0; j < i_reg_moves; j++, reg_move = NEXT_INSN (reg_move))
726 emit_insn (copy_rtx (PATTERN (reg_move)));
727 if (SCHED_STAGE (u_node) >= from_stage
728 && SCHED_STAGE (u_node) <= to_stage)
729 duplicate_insn_chain (u_node->first_note, u_node->insn);
734 /* Generate the instructions (including reg_moves) for prolog & epilog. */
736 generate_prolog_epilog (partial_schedule_ptr ps, struct loop *loop,
737 rtx count_reg, rtx count_init)
740 int last_stage = PS_STAGE_COUNT (ps) - 1;
743 /* Generate the prolog, inserting its insns on the loop-entry edge. */
748 /* Generate instructions at the beginning of the prolog to
749 adjust the loop count by STAGE_COUNT. If loop count is constant
750 (count_init), this constant is adjusted by STAGE_COUNT in
751 generate_prolog_epilog function. */
752 rtx sub_reg = NULL_RTX;
754 sub_reg = expand_simple_binop (GET_MODE (count_reg), MINUS,
755 count_reg, GEN_INT (last_stage),
756 count_reg, 1, OPTAB_DIRECT);
757 gcc_assert (REG_P (sub_reg));
758 if (REGNO (sub_reg) != REGNO (count_reg))
759 emit_move_insn (count_reg, sub_reg);
762 for (i = 0; i < last_stage; i++)
763 duplicate_insns_of_cycles (ps, 0, i, 1, count_reg);
765 /* Put the prolog on the entry edge. */
766 e = loop_preheader_edge (loop);
767 split_edge_and_insert (e, get_insns ());
771 /* Generate the epilog, inserting its insns on the loop-exit edge. */
774 for (i = 0; i < last_stage; i++)
775 duplicate_insns_of_cycles (ps, i + 1, last_stage, 0, count_reg);
777 /* Put the epilogue on the exit edge. */
778 gcc_assert (single_exit (loop));
779 e = single_exit (loop);
780 split_edge_and_insert (e, get_insns ());
784 /* Return true if all the BBs of the loop are empty except the
787 loop_single_full_bb_p (struct loop *loop)
790 basic_block *bbs = get_loop_body (loop);
792 for (i = 0; i < loop->num_nodes ; i++)
795 bool empty_bb = true;
797 if (bbs[i] == loop->header)
800 /* Make sure that basic blocks other than the header
801 have only notes labels or jumps. */
802 get_ebb_head_tail (bbs[i], bbs[i], &head, &tail);
803 for (; head != NEXT_INSN (tail); head = NEXT_INSN (head))
805 if (NOTE_P (head) || LABEL_P (head)
806 || (INSN_P (head) && (DEBUG_INSN_P (head) || JUMP_P (head))))
822 /* A simple loop from SMS point of view; it is a loop that is composed of
823 either a single basic block or two BBs - a header and a latch. */
824 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
825 && (EDGE_COUNT (loop->latch->preds) == 1) \
826 && (EDGE_COUNT (loop->latch->succs) == 1))
828 /* Return true if the loop is in its canonical form and false if not.
829 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
831 loop_canon_p (struct loop *loop)
834 if (loop->inner || !loop_outer (loop))
837 fprintf (dump_file, "SMS loop inner or !loop_outer\n");
841 if (!single_exit (loop))
845 rtx insn = BB_END (loop->header);
847 fprintf (dump_file, "SMS loop many exits ");
848 fprintf (dump_file, " %s %d (file, line)\n",
849 insn_file (insn), insn_line (insn));
854 if (! SIMPLE_SMS_LOOP_P (loop) && ! loop_single_full_bb_p (loop))
858 rtx insn = BB_END (loop->header);
860 fprintf (dump_file, "SMS loop many BBs. ");
861 fprintf (dump_file, " %s %d (file, line)\n",
862 insn_file (insn), insn_line (insn));
870 /* If there are more than one entry for the loop,
871 make it one by splitting the first entry edge and
872 redirecting the others to the new BB. */
874 canon_loop (struct loop *loop)
879 /* Avoid annoying special cases of edges going to exit
881 FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR->preds)
882 if ((e->flags & EDGE_FALLTHRU) && (EDGE_COUNT (e->src->succs) > 1))
885 if (loop->latch == loop->header
886 || EDGE_COUNT (loop->latch->succs) > 1)
888 FOR_EACH_EDGE (e, i, loop->header->preds)
889 if (e->src == loop->latch)
897 setup_sched_infos (void)
899 memcpy (&sms_common_sched_info, &haifa_common_sched_info,
900 sizeof (sms_common_sched_info));
901 sms_common_sched_info.sched_pass_id = SCHED_SMS_PASS;
902 common_sched_info = &sms_common_sched_info;
904 sched_deps_info = &sms_sched_deps_info;
905 current_sched_info = &sms_sched_info;
908 /* Probability in % that the sms-ed loop rolls enough so that optimized
909 version may be entered. Just a guess. */
910 #define PROB_SMS_ENOUGH_ITERATIONS 80
912 /* Used to calculate the upper bound of ii. */
913 #define MAXII_FACTOR 2
915 /* Main entry point, perform SMS scheduling on the loops of the function
916 that consist of single basic blocks. */
925 partial_schedule_ptr ps;
926 basic_block bb = NULL;
928 basic_block condition_bb = NULL;
930 gcov_type trip_count = 0;
932 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
933 | LOOPS_HAVE_RECORDED_EXITS);
934 if (number_of_loops () <= 1)
936 loop_optimizer_finalize ();
937 return; /* There are no loops to schedule. */
940 /* Initialize issue_rate. */
941 if (targetm.sched.issue_rate)
943 int temp = reload_completed;
945 reload_completed = 1;
946 issue_rate = targetm.sched.issue_rate ();
947 reload_completed = temp;
952 /* Initialize the scheduler. */
953 setup_sched_infos ();
956 /* Allocate memory to hold the DDG array one entry for each loop.
957 We use loop->num as index into this array. */
958 g_arr = XCNEWVEC (ddg_ptr, number_of_loops ());
962 fprintf (dump_file, "\n\nSMS analysis phase\n");
963 fprintf (dump_file, "===================\n\n");
966 /* Build DDGs for all the relevant loops and hold them in G_ARR
967 indexed by the loop index. */
968 FOR_EACH_LOOP (li, loop, 0)
974 if (dbg_cnt (sms_sched_loop) == false)
977 fprintf (dump_file, "SMS reached max limit... \n");
984 rtx insn = BB_END (loop->header);
986 fprintf (dump_file, "SMS loop num: %d, file: %s, line: %d\n",
987 loop->num, insn_file (insn), insn_line (insn));
991 if (! loop_canon_p (loop))
994 if (! loop_single_full_bb_p (loop))
997 fprintf (dump_file, "SMS not loop_single_full_bb_p\n");
1003 get_ebb_head_tail (bb, bb, &head, &tail);
1004 latch_edge = loop_latch_edge (loop);
1005 gcc_assert (single_exit (loop));
1006 if (single_exit (loop)->count)
1007 trip_count = latch_edge->count / single_exit (loop)->count;
1009 /* Perform SMS only on loops that their average count is above threshold. */
1011 if ( latch_edge->count
1012 && (latch_edge->count < single_exit (loop)->count * SMS_LOOP_AVERAGE_COUNT_THRESHOLD))
1016 fprintf (dump_file, " %s %d (file, line)\n",
1017 insn_file (tail), insn_line (tail));
1018 fprintf (dump_file, "SMS single-bb-loop\n");
1019 if (profile_info && flag_branch_probabilities)
1021 fprintf (dump_file, "SMS loop-count ");
1022 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1023 (HOST_WIDEST_INT) bb->count);
1024 fprintf (dump_file, "\n");
1025 fprintf (dump_file, "SMS trip-count ");
1026 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1027 (HOST_WIDEST_INT) trip_count);
1028 fprintf (dump_file, "\n");
1029 fprintf (dump_file, "SMS profile-sum-max ");
1030 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1031 (HOST_WIDEST_INT) profile_info->sum_max);
1032 fprintf (dump_file, "\n");
1038 /* Make sure this is a doloop. */
1039 if ( !(count_reg = doloop_register_get (head, tail)))
1042 fprintf (dump_file, "SMS doloop_register_get failed\n");
1046 /* Don't handle BBs with calls or barriers or auto-increment insns
1047 (to avoid creating invalid reg-moves for the auto-increment insns),
1048 or !single_set with the exception of instructions that include
1049 count_reg---these instructions are part of the control part
1050 that do-loop recognizes.
1051 ??? Should handle auto-increment insns.
1052 ??? Should handle insns defining subregs. */
1053 for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn))
1059 || (NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
1060 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE
1061 && !reg_mentioned_p (count_reg, insn))
1062 || (FIND_REG_INC_NOTE (insn, NULL_RTX) != 0)
1063 || (INSN_P (insn) && (set = single_set (insn))
1064 && GET_CODE (SET_DEST (set)) == SUBREG))
1068 if (insn != NEXT_INSN (tail))
1073 fprintf (dump_file, "SMS loop-with-call\n");
1074 else if (BARRIER_P (insn))
1075 fprintf (dump_file, "SMS loop-with-barrier\n");
1076 else if (FIND_REG_INC_NOTE (insn, NULL_RTX) != 0)
1077 fprintf (dump_file, "SMS reg inc\n");
1078 else if ((NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
1079 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE))
1080 fprintf (dump_file, "SMS loop-with-not-single-set\n");
1082 fprintf (dump_file, "SMS loop with subreg in lhs\n");
1083 print_rtl_single (dump_file, insn);
1089 /* Always schedule the closing branch with the rest of the
1090 instructions. The branch is rotated to be in row ii-1 at the
1091 end of the scheduling procedure to make sure it's the last
1092 instruction in the iteration. */
1093 if (! (g = create_ddg (bb, 1)))
1096 fprintf (dump_file, "SMS create_ddg failed\n");
1100 g_arr[loop->num] = g;
1102 fprintf (dump_file, "...OK\n");
1107 fprintf (dump_file, "\nSMS transformation phase\n");
1108 fprintf (dump_file, "=========================\n\n");
1111 /* We don't want to perform SMS on new loops - created by versioning. */
1112 FOR_EACH_LOOP (li, loop, 0)
1115 rtx count_reg, count_init;
1117 unsigned stage_count = 0;
1118 HOST_WIDEST_INT loop_count = 0;
1120 if (! (g = g_arr[loop->num]))
1125 rtx insn = BB_END (loop->header);
1127 fprintf (dump_file, "SMS loop num: %d, file: %s, line: %d\n",
1128 loop->num, insn_file (insn), insn_line (insn));
1130 print_ddg (dump_file, g);
1133 get_ebb_head_tail (loop->header, loop->header, &head, &tail);
1135 latch_edge = loop_latch_edge (loop);
1136 gcc_assert (single_exit (loop));
1137 if (single_exit (loop)->count)
1138 trip_count = latch_edge->count / single_exit (loop)->count;
1142 fprintf (dump_file, " %s %d (file, line)\n",
1143 insn_file (tail), insn_line (tail));
1144 fprintf (dump_file, "SMS single-bb-loop\n");
1145 if (profile_info && flag_branch_probabilities)
1147 fprintf (dump_file, "SMS loop-count ");
1148 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1149 (HOST_WIDEST_INT) bb->count);
1150 fprintf (dump_file, "\n");
1151 fprintf (dump_file, "SMS profile-sum-max ");
1152 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1153 (HOST_WIDEST_INT) profile_info->sum_max);
1154 fprintf (dump_file, "\n");
1156 fprintf (dump_file, "SMS doloop\n");
1157 fprintf (dump_file, "SMS built-ddg %d\n", g->num_nodes);
1158 fprintf (dump_file, "SMS num-loads %d\n", g->num_loads);
1159 fprintf (dump_file, "SMS num-stores %d\n", g->num_stores);
1163 /* In case of th loop have doloop register it gets special
1165 count_init = NULL_RTX;
1166 if ((count_reg = doloop_register_get (head, tail)))
1168 basic_block pre_header;
1170 pre_header = loop_preheader_edge (loop)->src;
1171 count_init = const_iteration_count (count_reg, pre_header,
1174 gcc_assert (count_reg);
1176 if (dump_file && count_init)
1178 fprintf (dump_file, "SMS const-doloop ");
1179 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1181 fprintf (dump_file, "\n");
1184 node_order = XNEWVEC (int, g->num_nodes);
1186 mii = 1; /* Need to pass some estimate of mii. */
1187 rec_mii = sms_order_nodes (g, mii, node_order, &max_asap);
1188 mii = MAX (res_MII (g), rec_mii);
1189 maxii = MAX (max_asap, MAXII_FACTOR * mii);
1192 fprintf (dump_file, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1193 rec_mii, mii, maxii);
1195 /* After sms_order_nodes and before sms_schedule_by_order, to copy over
1197 set_node_sched_params (g);
1199 ps = sms_schedule_by_order (g, mii, maxii, node_order);
1203 stage_count = calculate_stage_count (ps);
1204 gcc_assert(stage_count >= 1);
1205 PS_STAGE_COUNT(ps) = stage_count;
1208 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
1209 1 means that there is no interleaving between iterations thus
1210 we let the scheduling passes do the job in this case. */
1211 if (stage_count < (unsigned) PARAM_VALUE (PARAM_SMS_MIN_SC)
1212 || (count_init && (loop_count <= stage_count))
1213 || (flag_branch_probabilities && (trip_count <= stage_count)))
1217 fprintf (dump_file, "SMS failed... \n");
1218 fprintf (dump_file, "SMS sched-failed (stage-count=%d, loop-count=", stage_count);
1219 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, loop_count);
1220 fprintf (dump_file, ", trip-count=");
1221 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, trip_count);
1222 fprintf (dump_file, ")\n");
1227 struct undo_replace_buff_elem *reg_move_replaces;
1228 int amount = SCHED_TIME (g->closing_branch) + 1;
1230 /* Set the stage boundaries. The closing_branch was scheduled
1231 and should appear in the last (ii-1) row. */
1232 reset_sched_times (ps, amount);
1233 rotate_partial_schedule (ps, amount);
1234 set_columns_for_ps (ps);
1241 "SMS succeeded %d %d (with ii, sc)\n", ps->ii,
1243 print_partial_schedule (ps, dump_file);
1246 /* case the BCT count is not known , Do loop-versioning */
1247 if (count_reg && ! count_init)
1249 rtx comp_rtx = gen_rtx_fmt_ee (GT, VOIDmode, count_reg,
1250 GEN_INT(stage_count));
1251 unsigned prob = (PROB_SMS_ENOUGH_ITERATIONS
1252 * REG_BR_PROB_BASE) / 100;
1254 loop_version (loop, comp_rtx, &condition_bb,
1255 prob, prob, REG_BR_PROB_BASE - prob,
1259 /* Set new iteration count of loop kernel. */
1260 if (count_reg && count_init)
1261 SET_SRC (single_set (count_init)) = GEN_INT (loop_count
1264 /* Now apply the scheduled kernel to the RTL of the loop. */
1265 permute_partial_schedule (ps, g->closing_branch->first_note);
1267 /* Mark this loop as software pipelined so the later
1268 scheduling passes doesn't touch it. */
1269 if (! flag_resched_modulo_sched)
1270 g->bb->flags |= BB_DISABLE_SCHEDULE;
1271 /* The life-info is not valid any more. */
1272 df_set_bb_dirty (g->bb);
1274 reg_move_replaces = generate_reg_moves (ps, true);
1276 print_node_sched_params (dump_file, g->num_nodes, g);
1277 /* Generate prolog and epilog. */
1278 generate_prolog_epilog (ps, loop, count_reg, count_init);
1280 free_undo_replace_buff (reg_move_replaces);
1283 free_partial_schedule (ps);
1284 free (node_sched_params);
1291 /* Release scheduler data, needed until now because of DFA. */
1292 haifa_sched_finish ();
1293 loop_optimizer_finalize ();
1296 /* The SMS scheduling algorithm itself
1297 -----------------------------------
1298 Input: 'O' an ordered list of insns of a loop.
1299 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1301 'Q' is the empty Set
1302 'PS' is the partial schedule; it holds the currently scheduled nodes with
1304 'PSP' previously scheduled predecessors.
1305 'PSS' previously scheduled successors.
1306 't(u)' the cycle where u is scheduled.
1307 'l(u)' is the latency of u.
1308 'd(v,u)' is the dependence distance from v to u.
1309 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1310 the node ordering phase.
1311 'check_hardware_resources_conflicts(u, PS, c)'
1312 run a trace around cycle/slot through DFA model
1313 to check resource conflicts involving instruction u
1314 at cycle c given the partial schedule PS.
1315 'add_to_partial_schedule_at_time(u, PS, c)'
1316 Add the node/instruction u to the partial schedule
1318 'calculate_register_pressure(PS)'
1319 Given a schedule of instructions, calculate the register
1320 pressure it implies. One implementation could be the
1321 maximum number of overlapping live ranges.
1322 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1323 registers available in the hardware.
1327 3. for each node u in O in pre-computed order
1328 4. if (PSP(u) != Q && PSS(u) == Q) then
1329 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1330 6. start = Early_start; end = Early_start + II - 1; step = 1
1331 11. else if (PSP(u) == Q && PSS(u) != Q) then
1332 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1333 13. start = Late_start; end = Late_start - II + 1; step = -1
1334 14. else if (PSP(u) != Q && PSS(u) != Q) then
1335 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1336 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1337 17. start = Early_start;
1338 18. end = min(Early_start + II - 1 , Late_start);
1340 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1341 21. start = ASAP(u); end = start + II - 1; step = 1
1345 24. for (c = start ; c != end ; c += step)
1346 25. if check_hardware_resources_conflicts(u, PS, c) then
1347 26. add_to_partial_schedule_at_time(u, PS, c)
1352 31. if (success == false) then
1354 33. if (II > maxII) then
1355 34. finish - failed to schedule
1360 39. if (calculate_register_pressure(PS) > maxRP) then
1363 42. compute epilogue & prologue
1364 43. finish - succeeded to schedule
1367 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1368 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1369 set to 0 to save compile time. */
1370 #define DFA_HISTORY SMS_DFA_HISTORY
1372 /* A threshold for the number of repeated unsuccessful attempts to insert
1373 an empty row, before we flush the partial schedule and start over. */
1374 #define MAX_SPLIT_NUM 10
1375 /* Given the partial schedule PS, this function calculates and returns the
1376 cycles in which we can schedule the node with the given index I.
1377 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1378 noticed that there are several cases in which we fail to SMS the loop
1379 because the sched window of a node is empty due to tight data-deps. In
1380 such cases we want to unschedule some of the predecessors/successors
1381 until we get non-empty scheduling window. It returns -1 if the
1382 scheduling window is empty and zero otherwise. */
1385 get_sched_window (partial_schedule_ptr ps, int *nodes_order, int i,
1386 sbitmap sched_nodes, int ii, int *start_p, int *step_p, int *end_p)
1388 int start, step, end;
1390 int u = nodes_order [i];
1391 ddg_node_ptr u_node = &ps->g->nodes[u];
1392 sbitmap psp = sbitmap_alloc (ps->g->num_nodes);
1393 sbitmap pss = sbitmap_alloc (ps->g->num_nodes);
1394 sbitmap u_node_preds = NODE_PREDECESSORS (u_node);
1395 sbitmap u_node_succs = NODE_SUCCESSORS (u_node);
1399 /* 1. compute sched window for u (start, end, step). */
1402 psp_not_empty = sbitmap_a_and_b_cg (psp, u_node_preds, sched_nodes);
1403 pss_not_empty = sbitmap_a_and_b_cg (pss, u_node_succs, sched_nodes);
1405 if (psp_not_empty && !pss_not_empty)
1407 int early_start = INT_MIN;
1410 for (e = u_node->in; e != 0; e = e->next_in)
1412 ddg_node_ptr v_node = e->src;
1416 fprintf (dump_file, "\nProcessing edge: ");
1417 print_ddg_edge (dump_file, e);
1419 "\nScheduling %d (%d) in psp_not_empty,"
1420 " checking p %d (%d): ", u_node->cuid,
1421 INSN_UID (u_node->insn), v_node->cuid, INSN_UID
1425 if (TEST_BIT (sched_nodes, v_node->cuid))
1427 int p_st = SCHED_TIME (v_node);
1430 MAX (early_start, p_st + e->latency - (e->distance * ii));
1434 "pred st = %d; early_start = %d; latency: %d",
1435 p_st, early_start, e->latency);
1437 if (e->data_type == MEM_DEP)
1438 end = MIN (end, SCHED_TIME (v_node) + ii - 1);
1441 fprintf (dump_file, "the node is not scheduled\n");
1443 start = early_start;
1444 end = MIN (end, early_start + ii);
1445 /* Schedule the node close to it's predecessors. */
1450 "\nScheduling %d (%d) in a window (%d..%d) with step %d\n",
1451 u_node->cuid, INSN_UID (u_node->insn), start, end, step);
1454 else if (!psp_not_empty && pss_not_empty)
1456 int late_start = INT_MAX;
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 pss_not_empty,"
1469 " checking s %d (%d): ", u_node->cuid,
1470 INSN_UID (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,
1479 s_st - e->latency + (e->distance * ii));
1483 "succ st = %d; late_start = %d; latency = %d",
1484 s_st, late_start, e->latency);
1486 if (e->data_type == MEM_DEP)
1487 end = MAX (end, SCHED_TIME (v_node) - ii + 1);
1489 fprintf (dump_file, "end = %d\n", end);
1493 fprintf (dump_file, "the node is not scheduled\n");
1497 end = MAX (end, late_start - ii);
1498 /* Schedule the node close to it's successors. */
1503 "\nScheduling %d (%d) in a window (%d..%d) with step %d\n",
1504 u_node->cuid, INSN_UID (u_node->insn), start, end, step);
1508 else if (psp_not_empty && pss_not_empty)
1510 int early_start = INT_MIN;
1511 int late_start = INT_MAX;
1512 int count_preds = 0;
1513 int count_succs = 0;
1517 for (e = u_node->in; e != 0; e = e->next_in)
1519 ddg_node_ptr v_node = e->src;
1523 fprintf (dump_file, "\nProcessing edge:");
1524 print_ddg_edge (dump_file, e);
1526 "\nScheduling %d (%d) in psp_pss_not_empty,"
1527 " checking p %d (%d): ", u_node->cuid, INSN_UID
1528 (u_node->insn), v_node->cuid, INSN_UID
1532 if (TEST_BIT (sched_nodes, v_node->cuid))
1534 int p_st = SCHED_TIME (v_node);
1536 early_start = MAX (early_start,
1538 - (e->distance * ii));
1542 "pred st = %d; early_start = %d; latency = %d",
1543 p_st, early_start, e->latency);
1545 if (e->type == TRUE_DEP && e->data_type == REG_DEP)
1548 if (e->data_type == MEM_DEP)
1549 end = MIN (end, SCHED_TIME (v_node) + ii - 1);
1552 fprintf (dump_file, "the node is not scheduled\n");
1555 for (e = u_node->out; e != 0; e = e->next_out)
1557 ddg_node_ptr v_node = e->dest;
1561 fprintf (dump_file, "\nProcessing edge:");
1562 print_ddg_edge (dump_file, e);
1564 "\nScheduling %d (%d) in psp_pss_not_empty,"
1565 " checking s %d (%d): ", u_node->cuid, INSN_UID
1566 (u_node->insn), v_node->cuid, INSN_UID
1570 if (TEST_BIT (sched_nodes, v_node->cuid))
1572 int s_st = SCHED_TIME (v_node);
1574 late_start = MIN (late_start,
1576 + (e->distance * ii));
1580 "succ st = %d; late_start = %d; latency = %d",
1581 s_st, late_start, e->latency);
1583 if (e->type == TRUE_DEP && e->data_type == REG_DEP)
1586 if (e->data_type == MEM_DEP)
1587 start = MAX (start, SCHED_TIME (v_node) - ii + 1);
1590 fprintf (dump_file, "the node is not scheduled\n");
1593 start = MAX (start, early_start);
1594 end = MIN (end, MIN (early_start + ii, late_start + 1));
1596 /* If there are more successors than predecessors schedule the
1597 node close to it's successors. */
1598 if (count_succs >= count_preds)
1600 int old_start = start;
1603 end = old_start - 1;
1607 else /* psp is empty && pss is empty. */
1609 start = SCHED_ASAP (u_node);
1620 if ((start >= end && step == 1) || (start <= end && step == -1))
1623 fprintf (dump_file, "\nEmpty window: start=%d, end=%d, step=%d\n",
1631 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
1632 node currently been scheduled. At the end of the calculation
1633 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
1634 U_NODE which are (1) already scheduled in the first/last row of
1635 U_NODE's scheduling window, (2) whose dependence inequality with U
1636 becomes an equality when U is scheduled in this same row, and (3)
1637 whose dependence latency is zero.
1639 The first and last rows are calculated using the following parameters:
1640 START/END rows - The cycles that begins/ends the traversal on the window;
1641 searching for an empty cycle to schedule U_NODE.
1642 STEP - The direction in which we traverse the window.
1643 II - The initiation interval. */
1646 calculate_must_precede_follow (ddg_node_ptr u_node, int start, int end,
1647 int step, int ii, sbitmap sched_nodes,
1648 sbitmap must_precede, sbitmap must_follow)
1651 int first_cycle_in_window, last_cycle_in_window;
1653 gcc_assert (must_precede && must_follow);
1655 /* Consider the following scheduling window:
1656 {first_cycle_in_window, first_cycle_in_window+1, ...,
1657 last_cycle_in_window}. If step is 1 then the following will be
1658 the order we traverse the window: {start=first_cycle_in_window,
1659 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
1660 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
1661 end=first_cycle_in_window-1} if step is -1. */
1662 first_cycle_in_window = (step == 1) ? start : end - step;
1663 last_cycle_in_window = (step == 1) ? end - step : start;
1665 sbitmap_zero (must_precede);
1666 sbitmap_zero (must_follow);
1669 fprintf (dump_file, "\nmust_precede: ");
1671 /* Instead of checking if:
1672 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
1673 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
1674 first_cycle_in_window)
1676 we use the fact that latency is non-negative:
1677 SCHED_TIME (e->src) - (e->distance * ii) <=
1678 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
1679 first_cycle_in_window
1681 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
1682 for (e = u_node->in; e != 0; e = e->next_in)
1683 if (TEST_BIT (sched_nodes, e->src->cuid)
1684 && ((SCHED_TIME (e->src) - (e->distance * ii)) ==
1685 first_cycle_in_window))
1688 fprintf (dump_file, "%d ", e->src->cuid);
1690 SET_BIT (must_precede, e->src->cuid);
1694 fprintf (dump_file, "\nmust_follow: ");
1696 /* Instead of checking if:
1697 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
1698 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
1699 last_cycle_in_window)
1701 we use the fact that latency is non-negative:
1702 SCHED_TIME (e->dest) + (e->distance * ii) >=
1703 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
1704 last_cycle_in_window
1706 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
1707 for (e = u_node->out; e != 0; e = e->next_out)
1708 if (TEST_BIT (sched_nodes, e->dest->cuid)
1709 && ((SCHED_TIME (e->dest) + (e->distance * ii)) ==
1710 last_cycle_in_window))
1713 fprintf (dump_file, "%d ", e->dest->cuid);
1715 SET_BIT (must_follow, e->dest->cuid);
1719 fprintf (dump_file, "\n");
1722 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
1723 parameters to decide if that's possible:
1724 PS - The partial schedule.
1725 U - The serial number of U_NODE.
1726 NUM_SPLITS - The number of row splits made so far.
1727 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
1728 the first row of the scheduling window)
1729 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
1730 last row of the scheduling window) */
1733 try_scheduling_node_in_cycle (partial_schedule_ptr ps, ddg_node_ptr u_node,
1734 int u, int cycle, sbitmap sched_nodes,
1735 int *num_splits, sbitmap must_precede,
1736 sbitmap must_follow)
1741 verify_partial_schedule (ps, sched_nodes);
1742 psi = ps_add_node_check_conflicts (ps, u_node, cycle,
1743 must_precede, must_follow);
1746 SCHED_TIME (u_node) = cycle;
1747 SET_BIT (sched_nodes, u);
1751 fprintf (dump_file, "Scheduled w/o split in %d\n", cycle);
1758 /* This function implements the scheduling algorithm for SMS according to the
1760 static partial_schedule_ptr
1761 sms_schedule_by_order (ddg_ptr g, int mii, int maxii, int *nodes_order)
1764 int i, c, success, num_splits = 0;
1765 int flush_and_start_over = true;
1766 int num_nodes = g->num_nodes;
1767 int start, end, step; /* Place together into one struct? */
1768 sbitmap sched_nodes = sbitmap_alloc (num_nodes);
1769 sbitmap must_precede = sbitmap_alloc (num_nodes);
1770 sbitmap must_follow = sbitmap_alloc (num_nodes);
1771 sbitmap tobe_scheduled = sbitmap_alloc (num_nodes);
1773 partial_schedule_ptr ps = create_partial_schedule (ii, g, DFA_HISTORY);
1775 sbitmap_ones (tobe_scheduled);
1776 sbitmap_zero (sched_nodes);
1778 while (flush_and_start_over && (ii < maxii))
1782 fprintf (dump_file, "Starting with ii=%d\n", ii);
1783 flush_and_start_over = false;
1784 sbitmap_zero (sched_nodes);
1786 for (i = 0; i < num_nodes; i++)
1788 int u = nodes_order[i];
1789 ddg_node_ptr u_node = &ps->g->nodes[u];
1790 rtx insn = u_node->insn;
1792 if (!NONDEBUG_INSN_P (insn))
1794 RESET_BIT (tobe_scheduled, u);
1798 if (TEST_BIT (sched_nodes, u))
1801 /* Try to get non-empty scheduling window. */
1803 if (get_sched_window (ps, nodes_order, i, sched_nodes, ii, &start,
1807 fprintf (dump_file, "\nTrying to schedule node %d \
1808 INSN = %d in (%d .. %d) step %d\n", u, (INSN_UID
1809 (g->nodes[u].insn)), start, end, step);
1811 gcc_assert ((step > 0 && start < end)
1812 || (step < 0 && start > end));
1814 calculate_must_precede_follow (u_node, start, end, step, ii,
1815 sched_nodes, must_precede,
1818 for (c = start; c != end; c += step)
1820 sbitmap tmp_precede = NULL;
1821 sbitmap tmp_follow = NULL;
1826 tmp_precede = must_precede;
1827 else /* step == -1. */
1828 tmp_follow = must_follow;
1830 if (c == end - step)
1833 tmp_follow = must_follow;
1834 else /* step == -1. */
1835 tmp_precede = must_precede;
1839 try_scheduling_node_in_cycle (ps, u_node, u, c,
1841 &num_splits, tmp_precede,
1847 verify_partial_schedule (ps, sched_nodes);
1856 if (num_splits >= MAX_SPLIT_NUM)
1859 flush_and_start_over = true;
1860 verify_partial_schedule (ps, sched_nodes);
1861 reset_partial_schedule (ps, ii);
1862 verify_partial_schedule (ps, sched_nodes);
1867 /* The scheduling window is exclusive of 'end'
1868 whereas compute_split_window() expects an inclusive,
1871 split_row = compute_split_row (sched_nodes, start, end - 1,
1874 split_row = compute_split_row (sched_nodes, end + 1, start,
1877 ps_insert_empty_row (ps, split_row, sched_nodes);
1878 i--; /* Go back and retry node i. */
1881 fprintf (dump_file, "num_splits=%d\n", num_splits);
1884 /* ??? If (success), check register pressure estimates. */
1885 } /* Continue with next node. */
1886 } /* While flush_and_start_over. */
1889 free_partial_schedule (ps);
1893 gcc_assert (sbitmap_equal (tobe_scheduled, sched_nodes));
1895 sbitmap_free (sched_nodes);
1896 sbitmap_free (must_precede);
1897 sbitmap_free (must_follow);
1898 sbitmap_free (tobe_scheduled);
1903 /* This function inserts a new empty row into PS at the position
1904 according to SPLITROW, keeping all already scheduled instructions
1905 intact and updating their SCHED_TIME and cycle accordingly. */
1907 ps_insert_empty_row (partial_schedule_ptr ps, int split_row,
1908 sbitmap sched_nodes)
1910 ps_insn_ptr crr_insn;
1911 ps_insn_ptr *rows_new;
1913 int new_ii = ii + 1;
1915 int *rows_length_new;
1917 verify_partial_schedule (ps, sched_nodes);
1919 /* We normalize sched_time and rotate ps to have only non-negative sched
1920 times, for simplicity of updating cycles after inserting new row. */
1921 split_row -= ps->min_cycle;
1922 split_row = SMODULO (split_row, ii);
1924 fprintf (dump_file, "split_row=%d\n", split_row);
1926 reset_sched_times (ps, PS_MIN_CYCLE (ps));
1927 rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
1929 rows_new = (ps_insn_ptr *) xcalloc (new_ii, sizeof (ps_insn_ptr));
1930 rows_length_new = (int *) xcalloc (new_ii, sizeof (int));
1931 for (row = 0; row < split_row; row++)
1933 rows_new[row] = ps->rows[row];
1934 rows_length_new[row] = ps->rows_length[row];
1935 ps->rows[row] = NULL;
1936 for (crr_insn = rows_new[row];
1937 crr_insn; crr_insn = crr_insn->next_in_row)
1939 ddg_node_ptr u = crr_insn->node;
1940 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii);
1942 SCHED_TIME (u) = new_time;
1943 crr_insn->cycle = new_time;
1944 SCHED_ROW (u) = new_time % new_ii;
1945 SCHED_STAGE (u) = new_time / new_ii;
1950 rows_new[split_row] = NULL;
1952 for (row = split_row; row < ii; row++)
1954 rows_new[row + 1] = ps->rows[row];
1955 rows_length_new[row + 1] = ps->rows_length[row];
1956 ps->rows[row] = NULL;
1957 for (crr_insn = rows_new[row + 1];
1958 crr_insn; crr_insn = crr_insn->next_in_row)
1960 ddg_node_ptr u = crr_insn->node;
1961 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii) + 1;
1963 SCHED_TIME (u) = new_time;
1964 crr_insn->cycle = new_time;
1965 SCHED_ROW (u) = new_time % new_ii;
1966 SCHED_STAGE (u) = new_time / new_ii;
1971 ps->min_cycle = ps->min_cycle + ps->min_cycle / ii
1972 + (SMODULO (ps->min_cycle, ii) >= split_row ? 1 : 0);
1973 ps->max_cycle = ps->max_cycle + ps->max_cycle / ii
1974 + (SMODULO (ps->max_cycle, ii) >= split_row ? 1 : 0);
1976 ps->rows = rows_new;
1977 free (ps->rows_length);
1978 ps->rows_length = rows_length_new;
1980 gcc_assert (ps->min_cycle >= 0);
1982 verify_partial_schedule (ps, sched_nodes);
1985 fprintf (dump_file, "min_cycle=%d, max_cycle=%d\n", ps->min_cycle,
1989 /* Given U_NODE which is the node that failed to be scheduled; LOW and
1990 UP which are the boundaries of it's scheduling window; compute using
1991 SCHED_NODES and II a row in the partial schedule that can be split
1992 which will separate a critical predecessor from a critical successor
1993 thereby expanding the window, and return it. */
1995 compute_split_row (sbitmap sched_nodes, int low, int up, int ii,
1996 ddg_node_ptr u_node)
1999 int lower = INT_MIN, upper = INT_MAX;
2000 ddg_node_ptr crit_pred = NULL;
2001 ddg_node_ptr crit_succ = NULL;
2004 for (e = u_node->in; e != 0; e = e->next_in)
2006 ddg_node_ptr v_node = e->src;
2008 if (TEST_BIT (sched_nodes, v_node->cuid)
2009 && (low == SCHED_TIME (v_node) + e->latency - (e->distance * ii)))
2010 if (SCHED_TIME (v_node) > lower)
2013 lower = SCHED_TIME (v_node);
2017 if (crit_pred != NULL)
2019 crit_cycle = SCHED_TIME (crit_pred) + 1;
2020 return SMODULO (crit_cycle, ii);
2023 for (e = u_node->out; e != 0; e = e->next_out)
2025 ddg_node_ptr v_node = e->dest;
2026 if (TEST_BIT (sched_nodes, v_node->cuid)
2027 && (up == SCHED_TIME (v_node) - e->latency + (e->distance * ii)))
2028 if (SCHED_TIME (v_node) < upper)
2031 upper = SCHED_TIME (v_node);
2035 if (crit_succ != NULL)
2037 crit_cycle = SCHED_TIME (crit_succ);
2038 return SMODULO (crit_cycle, ii);
2042 fprintf (dump_file, "Both crit_pred and crit_succ are NULL\n");
2044 return SMODULO ((low + up + 1) / 2, ii);
2048 verify_partial_schedule (partial_schedule_ptr ps, sbitmap sched_nodes)
2051 ps_insn_ptr crr_insn;
2053 for (row = 0; row < ps->ii; row++)
2057 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
2059 ddg_node_ptr u = crr_insn->node;
2062 gcc_assert (TEST_BIT (sched_nodes, u->cuid));
2063 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2064 popcount (sched_nodes) == number of insns in ps. */
2065 gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
2066 gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
2069 gcc_assert (ps->rows_length[row] == length);
2074 /* This page implements the algorithm for ordering the nodes of a DDG
2075 for modulo scheduling, activated through the
2076 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2078 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2079 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
2080 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
2081 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2082 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
2083 #define DEPTH(x) (ASAP ((x)))
2085 typedef struct node_order_params * nopa;
2087 static void order_nodes_of_sccs (ddg_all_sccs_ptr, int * result);
2088 static int order_nodes_in_scc (ddg_ptr, sbitmap, sbitmap, int*, int);
2089 static nopa calculate_order_params (ddg_ptr, int, int *);
2090 static int find_max_asap (ddg_ptr, sbitmap);
2091 static int find_max_hv_min_mob (ddg_ptr, sbitmap);
2092 static int find_max_dv_min_mob (ddg_ptr, sbitmap);
2094 enum sms_direction {BOTTOMUP, TOPDOWN};
2096 struct node_order_params
2103 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2105 check_nodes_order (int *node_order, int num_nodes)
2108 sbitmap tmp = sbitmap_alloc (num_nodes);
2113 fprintf (dump_file, "SMS final nodes order: \n");
2115 for (i = 0; i < num_nodes; i++)
2117 int u = node_order[i];
2120 fprintf (dump_file, "%d ", u);
2121 gcc_assert (u < num_nodes && u >= 0 && !TEST_BIT (tmp, u));
2127 fprintf (dump_file, "\n");
2132 /* Order the nodes of G for scheduling and pass the result in
2133 NODE_ORDER. Also set aux.count of each node to ASAP.
2134 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2136 sms_order_nodes (ddg_ptr g, int mii, int * node_order, int *pmax_asap)
2140 ddg_all_sccs_ptr sccs = create_ddg_all_sccs (g);
2142 nopa nops = calculate_order_params (g, mii, pmax_asap);
2145 print_sccs (dump_file, sccs, g);
2147 order_nodes_of_sccs (sccs, node_order);
2149 if (sccs->num_sccs > 0)
2150 /* First SCC has the largest recurrence_length. */
2151 rec_mii = sccs->sccs[0]->recurrence_length;
2153 /* Save ASAP before destroying node_order_params. */
2154 for (i = 0; i < g->num_nodes; i++)
2156 ddg_node_ptr v = &g->nodes[i];
2157 v->aux.count = ASAP (v);
2161 free_ddg_all_sccs (sccs);
2162 check_nodes_order (node_order, g->num_nodes);
2168 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs, int * node_order)
2171 ddg_ptr g = all_sccs->ddg;
2172 int num_nodes = g->num_nodes;
2173 sbitmap prev_sccs = sbitmap_alloc (num_nodes);
2174 sbitmap on_path = sbitmap_alloc (num_nodes);
2175 sbitmap tmp = sbitmap_alloc (num_nodes);
2176 sbitmap ones = sbitmap_alloc (num_nodes);
2178 sbitmap_zero (prev_sccs);
2179 sbitmap_ones (ones);
2181 /* Perform the node ordering starting from the SCC with the highest recMII.
2182 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2183 for (i = 0; i < all_sccs->num_sccs; i++)
2185 ddg_scc_ptr scc = all_sccs->sccs[i];
2187 /* Add nodes on paths from previous SCCs to the current SCC. */
2188 find_nodes_on_paths (on_path, g, prev_sccs, scc->nodes);
2189 sbitmap_a_or_b (tmp, scc->nodes, on_path);
2191 /* Add nodes on paths from the current SCC to previous SCCs. */
2192 find_nodes_on_paths (on_path, g, scc->nodes, prev_sccs);
2193 sbitmap_a_or_b (tmp, tmp, on_path);
2195 /* Remove nodes of previous SCCs from current extended SCC. */
2196 sbitmap_difference (tmp, tmp, prev_sccs);
2198 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
2199 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2202 /* Handle the remaining nodes that do not belong to any scc. Each call
2203 to order_nodes_in_scc handles a single connected component. */
2204 while (pos < g->num_nodes)
2206 sbitmap_difference (tmp, ones, prev_sccs);
2207 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
2209 sbitmap_free (prev_sccs);
2210 sbitmap_free (on_path);
2212 sbitmap_free (ones);
2215 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2216 static struct node_order_params *
2217 calculate_order_params (ddg_ptr g, int mii ATTRIBUTE_UNUSED, int *pmax_asap)
2221 int num_nodes = g->num_nodes;
2223 /* Allocate a place to hold ordering params for each node in the DDG. */
2224 nopa node_order_params_arr;
2226 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2227 node_order_params_arr = (nopa) xcalloc (num_nodes,
2228 sizeof (struct node_order_params));
2230 /* Set the aux pointer of each node to point to its order_params structure. */
2231 for (u = 0; u < num_nodes; u++)
2232 g->nodes[u].aux.info = &node_order_params_arr[u];
2234 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2235 calculate ASAP, ALAP, mobility, distance, and height for each node
2236 in the dependence (direct acyclic) graph. */
2238 /* We assume that the nodes in the array are in topological order. */
2241 for (u = 0; u < num_nodes; u++)
2243 ddg_node_ptr u_node = &g->nodes[u];
2246 for (e = u_node->in; e; e = e->next_in)
2247 if (e->distance == 0)
2248 ASAP (u_node) = MAX (ASAP (u_node),
2249 ASAP (e->src) + e->latency);
2250 max_asap = MAX (max_asap, ASAP (u_node));
2253 for (u = num_nodes - 1; u > -1; u--)
2255 ddg_node_ptr u_node = &g->nodes[u];
2257 ALAP (u_node) = max_asap;
2258 HEIGHT (u_node) = 0;
2259 for (e = u_node->out; e; e = e->next_out)
2260 if (e->distance == 0)
2262 ALAP (u_node) = MIN (ALAP (u_node),
2263 ALAP (e->dest) - e->latency);
2264 HEIGHT (u_node) = MAX (HEIGHT (u_node),
2265 HEIGHT (e->dest) + e->latency);
2270 fprintf (dump_file, "\nOrder params\n");
2271 for (u = 0; u < num_nodes; u++)
2273 ddg_node_ptr u_node = &g->nodes[u];
2275 fprintf (dump_file, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u,
2276 ASAP (u_node), ALAP (u_node), HEIGHT (u_node));
2280 *pmax_asap = max_asap;
2281 return node_order_params_arr;
2285 find_max_asap (ddg_ptr g, sbitmap nodes)
2290 sbitmap_iterator sbi;
2292 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
2294 ddg_node_ptr u_node = &g->nodes[u];
2296 if (max_asap < ASAP (u_node))
2298 max_asap = ASAP (u_node);
2306 find_max_hv_min_mob (ddg_ptr g, sbitmap nodes)
2310 int min_mob = INT_MAX;
2312 sbitmap_iterator sbi;
2314 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
2316 ddg_node_ptr u_node = &g->nodes[u];
2318 if (max_hv < HEIGHT (u_node))
2320 max_hv = HEIGHT (u_node);
2321 min_mob = MOB (u_node);
2324 else if ((max_hv == HEIGHT (u_node))
2325 && (min_mob > MOB (u_node)))
2327 min_mob = MOB (u_node);
2335 find_max_dv_min_mob (ddg_ptr g, sbitmap nodes)
2339 int min_mob = INT_MAX;
2341 sbitmap_iterator sbi;
2343 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
2345 ddg_node_ptr u_node = &g->nodes[u];
2347 if (max_dv < DEPTH (u_node))
2349 max_dv = DEPTH (u_node);
2350 min_mob = MOB (u_node);
2353 else if ((max_dv == DEPTH (u_node))
2354 && (min_mob > MOB (u_node)))
2356 min_mob = MOB (u_node);
2363 /* Places the nodes of SCC into the NODE_ORDER array starting
2364 at position POS, according to the SMS ordering algorithm.
2365 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2366 the NODE_ORDER array, starting from position zero. */
2368 order_nodes_in_scc (ddg_ptr g, sbitmap nodes_ordered, sbitmap scc,
2369 int * node_order, int pos)
2371 enum sms_direction dir;
2372 int num_nodes = g->num_nodes;
2373 sbitmap workset = sbitmap_alloc (num_nodes);
2374 sbitmap tmp = sbitmap_alloc (num_nodes);
2375 sbitmap zero_bitmap = sbitmap_alloc (num_nodes);
2376 sbitmap predecessors = sbitmap_alloc (num_nodes);
2377 sbitmap successors = sbitmap_alloc (num_nodes);
2379 sbitmap_zero (predecessors);
2380 find_predecessors (predecessors, g, nodes_ordered);
2382 sbitmap_zero (successors);
2383 find_successors (successors, g, nodes_ordered);
2386 if (sbitmap_a_and_b_cg (tmp, predecessors, scc))
2388 sbitmap_copy (workset, tmp);
2391 else if (sbitmap_a_and_b_cg (tmp, successors, scc))
2393 sbitmap_copy (workset, tmp);
2400 sbitmap_zero (workset);
2401 if ((u = find_max_asap (g, scc)) >= 0)
2402 SET_BIT (workset, u);
2406 sbitmap_zero (zero_bitmap);
2407 while (!sbitmap_equal (workset, zero_bitmap))
2410 ddg_node_ptr v_node;
2411 sbitmap v_node_preds;
2412 sbitmap v_node_succs;
2416 while (!sbitmap_equal (workset, zero_bitmap))
2418 v = find_max_hv_min_mob (g, workset);
2419 v_node = &g->nodes[v];
2420 node_order[pos++] = v;
2421 v_node_succs = NODE_SUCCESSORS (v_node);
2422 sbitmap_a_and_b (tmp, v_node_succs, scc);
2424 /* Don't consider the already ordered successors again. */
2425 sbitmap_difference (tmp, tmp, nodes_ordered);
2426 sbitmap_a_or_b (workset, workset, tmp);
2427 RESET_BIT (workset, v);
2428 SET_BIT (nodes_ordered, v);
2431 sbitmap_zero (predecessors);
2432 find_predecessors (predecessors, g, nodes_ordered);
2433 sbitmap_a_and_b (workset, predecessors, scc);
2437 while (!sbitmap_equal (workset, zero_bitmap))
2439 v = find_max_dv_min_mob (g, workset);
2440 v_node = &g->nodes[v];
2441 node_order[pos++] = v;
2442 v_node_preds = NODE_PREDECESSORS (v_node);
2443 sbitmap_a_and_b (tmp, v_node_preds, scc);
2445 /* Don't consider the already ordered predecessors again. */
2446 sbitmap_difference (tmp, tmp, nodes_ordered);
2447 sbitmap_a_or_b (workset, workset, tmp);
2448 RESET_BIT (workset, v);
2449 SET_BIT (nodes_ordered, v);
2452 sbitmap_zero (successors);
2453 find_successors (successors, g, nodes_ordered);
2454 sbitmap_a_and_b (workset, successors, scc);
2458 sbitmap_free (workset);
2459 sbitmap_free (zero_bitmap);
2460 sbitmap_free (predecessors);
2461 sbitmap_free (successors);
2466 /* This page contains functions for manipulating partial-schedules during
2467 modulo scheduling. */
2469 /* Create a partial schedule and allocate a memory to hold II rows. */
2471 static partial_schedule_ptr
2472 create_partial_schedule (int ii, ddg_ptr g, int history)
2474 partial_schedule_ptr ps = XNEW (struct partial_schedule);
2475 ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
2476 ps->rows_length = (int *) xcalloc (ii, sizeof (int));
2478 ps->history = history;
2479 ps->min_cycle = INT_MAX;
2480 ps->max_cycle = INT_MIN;
2486 /* Free the PS_INSNs in rows array of the given partial schedule.
2487 ??? Consider caching the PS_INSN's. */
2489 free_ps_insns (partial_schedule_ptr ps)
2493 for (i = 0; i < ps->ii; i++)
2497 ps_insn_ptr ps_insn = ps->rows[i]->next_in_row;
2500 ps->rows[i] = ps_insn;
2506 /* Free all the memory allocated to the partial schedule. */
2509 free_partial_schedule (partial_schedule_ptr ps)
2515 free (ps->rows_length);
2519 /* Clear the rows array with its PS_INSNs, and create a new one with
2523 reset_partial_schedule (partial_schedule_ptr ps, int new_ii)
2528 if (new_ii == ps->ii)
2530 ps->rows = (ps_insn_ptr *) xrealloc (ps->rows, new_ii
2531 * sizeof (ps_insn_ptr));
2532 memset (ps->rows, 0, new_ii * sizeof (ps_insn_ptr));
2533 ps->rows_length = (int *) xrealloc (ps->rows_length, new_ii * sizeof (int));
2534 memset (ps->rows_length, 0, new_ii * sizeof (int));
2536 ps->min_cycle = INT_MAX;
2537 ps->max_cycle = INT_MIN;
2540 /* Prints the partial schedule as an ii rows array, for each rows
2541 print the ids of the insns in it. */
2543 print_partial_schedule (partial_schedule_ptr ps, FILE *dump)
2547 for (i = 0; i < ps->ii; i++)
2549 ps_insn_ptr ps_i = ps->rows[i];
2551 fprintf (dump, "\n[ROW %d ]: ", i);
2554 if (JUMP_P (ps_i->node->insn))
2555 fprintf (dump, "%d (branch), ",
2556 INSN_UID (ps_i->node->insn));
2558 fprintf (dump, "%d, ",
2559 INSN_UID (ps_i->node->insn));
2561 ps_i = ps_i->next_in_row;
2566 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2568 create_ps_insn (ddg_node_ptr node, int cycle)
2570 ps_insn_ptr ps_i = XNEW (struct ps_insn);
2573 ps_i->next_in_row = NULL;
2574 ps_i->prev_in_row = NULL;
2575 ps_i->cycle = cycle;
2581 /* Removes the given PS_INSN from the partial schedule. Returns false if the
2582 node is not found in the partial schedule, else returns true. */
2584 remove_node_from_ps (partial_schedule_ptr ps, ps_insn_ptr ps_i)
2591 row = SMODULO (ps_i->cycle, ps->ii);
2592 if (! ps_i->prev_in_row)
2594 if (ps_i != ps->rows[row])
2597 ps->rows[row] = ps_i->next_in_row;
2599 ps->rows[row]->prev_in_row = NULL;
2603 ps_i->prev_in_row->next_in_row = ps_i->next_in_row;
2604 if (ps_i->next_in_row)
2605 ps_i->next_in_row->prev_in_row = ps_i->prev_in_row;
2608 ps->rows_length[row] -= 1;
2613 /* Unlike what literature describes for modulo scheduling (which focuses
2614 on VLIW machines) the order of the instructions inside a cycle is
2615 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2616 where the current instruction should go relative to the already
2617 scheduled instructions in the given cycle. Go over these
2618 instructions and find the first possible column to put it in. */
2620 ps_insn_find_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
2621 sbitmap must_precede, sbitmap must_follow)
2623 ps_insn_ptr next_ps_i;
2624 ps_insn_ptr first_must_follow = NULL;
2625 ps_insn_ptr last_must_precede = NULL;
2626 ps_insn_ptr last_in_row = NULL;
2632 row = SMODULO (ps_i->cycle, ps->ii);
2634 /* Find the first must follow and the last must precede
2635 and insert the node immediately after the must precede
2636 but make sure that it there is no must follow after it. */
2637 for (next_ps_i = ps->rows[row];
2639 next_ps_i = next_ps_i->next_in_row)
2641 if (must_follow && TEST_BIT (must_follow, next_ps_i->node->cuid)
2642 && ! first_must_follow)
2643 first_must_follow = next_ps_i;
2644 if (must_precede && TEST_BIT (must_precede, next_ps_i->node->cuid))
2646 /* If we have already met a node that must follow, then
2647 there is no possible column. */
2648 if (first_must_follow)
2651 last_must_precede = next_ps_i;
2653 /* The closing branch must be the last in the row. */
2655 && TEST_BIT (must_precede, next_ps_i->node->cuid)
2656 && JUMP_P (next_ps_i->node->insn))
2659 last_in_row = next_ps_i;
2662 /* The closing branch is scheduled as well. Make sure there is no
2663 dependent instruction after it as the branch should be the last
2664 instruction in the row. */
2665 if (JUMP_P (ps_i->node->insn))
2667 if (first_must_follow)
2671 /* Make the branch the last in the row. New instructions
2672 will be inserted at the beginning of the row or after the
2673 last must_precede instruction thus the branch is guaranteed
2674 to remain the last instruction in the row. */
2675 last_in_row->next_in_row = ps_i;
2676 ps_i->prev_in_row = last_in_row;
2677 ps_i->next_in_row = NULL;
2680 ps->rows[row] = ps_i;
2684 /* Now insert the node after INSERT_AFTER_PSI. */
2686 if (! last_must_precede)
2688 ps_i->next_in_row = ps->rows[row];
2689 ps_i->prev_in_row = NULL;
2690 if (ps_i->next_in_row)
2691 ps_i->next_in_row->prev_in_row = ps_i;
2692 ps->rows[row] = ps_i;
2696 ps_i->next_in_row = last_must_precede->next_in_row;
2697 last_must_precede->next_in_row = ps_i;
2698 ps_i->prev_in_row = last_must_precede;
2699 if (ps_i->next_in_row)
2700 ps_i->next_in_row->prev_in_row = ps_i;
2706 /* Advances the PS_INSN one column in its current row; returns false
2707 in failure and true in success. Bit N is set in MUST_FOLLOW if
2708 the node with cuid N must be come after the node pointed to by
2709 PS_I when scheduled in the same cycle. */
2711 ps_insn_advance_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
2712 sbitmap must_follow)
2714 ps_insn_ptr prev, next;
2716 ddg_node_ptr next_node;
2721 row = SMODULO (ps_i->cycle, ps->ii);
2723 if (! ps_i->next_in_row)
2726 next_node = ps_i->next_in_row->node;
2728 /* Check if next_in_row is dependent on ps_i, both having same sched
2729 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
2730 if (must_follow && TEST_BIT (must_follow, next_node->cuid))
2733 /* Advance PS_I over its next_in_row in the doubly linked list. */
2734 prev = ps_i->prev_in_row;
2735 next = ps_i->next_in_row;
2737 if (ps_i == ps->rows[row])
2738 ps->rows[row] = next;
2740 ps_i->next_in_row = next->next_in_row;
2742 if (next->next_in_row)
2743 next->next_in_row->prev_in_row = ps_i;
2745 next->next_in_row = ps_i;
2746 ps_i->prev_in_row = next;
2748 next->prev_in_row = prev;
2750 prev->next_in_row = next;
2755 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
2756 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
2757 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
2758 before/after (respectively) the node pointed to by PS_I when scheduled
2759 in the same cycle. */
2761 add_node_to_ps (partial_schedule_ptr ps, ddg_node_ptr node, int cycle,
2762 sbitmap must_precede, sbitmap must_follow)
2765 int row = SMODULO (cycle, ps->ii);
2767 if (ps->rows_length[row] >= issue_rate)
2770 ps_i = create_ps_insn (node, cycle);
2772 /* Finds and inserts PS_I according to MUST_FOLLOW and
2774 if (! ps_insn_find_column (ps, ps_i, must_precede, must_follow))
2780 ps->rows_length[row] += 1;
2784 /* Advance time one cycle. Assumes DFA is being used. */
2786 advance_one_cycle (void)
2788 if (targetm.sched.dfa_pre_cycle_insn)
2789 state_transition (curr_state,
2790 targetm.sched.dfa_pre_cycle_insn ());
2792 state_transition (curr_state, NULL);
2794 if (targetm.sched.dfa_post_cycle_insn)
2795 state_transition (curr_state,
2796 targetm.sched.dfa_post_cycle_insn ());
2801 /* Checks if PS has resource conflicts according to DFA, starting from
2802 FROM cycle to TO cycle; returns true if there are conflicts and false
2803 if there are no conflicts. Assumes DFA is being used. */
2805 ps_has_conflicts (partial_schedule_ptr ps, int from, int to)
2809 state_reset (curr_state);
2811 for (cycle = from; cycle <= to; cycle++)
2813 ps_insn_ptr crr_insn;
2814 /* Holds the remaining issue slots in the current row. */
2815 int can_issue_more = issue_rate;
2817 /* Walk through the DFA for the current row. */
2818 for (crr_insn = ps->rows[SMODULO (cycle, ps->ii)];
2820 crr_insn = crr_insn->next_in_row)
2822 rtx insn = crr_insn->node->insn;
2824 if (!NONDEBUG_INSN_P (insn))
2827 /* Check if there is room for the current insn. */
2828 if (!can_issue_more || state_dead_lock_p (curr_state))
2831 /* Update the DFA state and return with failure if the DFA found
2832 resource conflicts. */
2833 if (state_transition (curr_state, insn) >= 0)
2836 if (targetm.sched.variable_issue)
2838 targetm.sched.variable_issue (sched_dump, sched_verbose,
2839 insn, can_issue_more);
2840 /* A naked CLOBBER or USE generates no instruction, so don't
2841 let them consume issue slots. */
2842 else if (GET_CODE (PATTERN (insn)) != USE
2843 && GET_CODE (PATTERN (insn)) != CLOBBER)
2847 /* Advance the DFA to the next cycle. */
2848 advance_one_cycle ();
2853 /* Checks if the given node causes resource conflicts when added to PS at
2854 cycle C. If not the node is added to PS and returned; otherwise zero
2855 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
2856 cuid N must be come before/after (respectively) the node pointed to by
2857 PS_I when scheduled in the same cycle. */
2859 ps_add_node_check_conflicts (partial_schedule_ptr ps, ddg_node_ptr n,
2860 int c, sbitmap must_precede,
2861 sbitmap must_follow)
2863 int has_conflicts = 0;
2866 /* First add the node to the PS, if this succeeds check for
2867 conflicts, trying different issue slots in the same row. */
2868 if (! (ps_i = add_node_to_ps (ps, n, c, must_precede, must_follow)))
2869 return NULL; /* Failed to insert the node at the given cycle. */
2871 has_conflicts = ps_has_conflicts (ps, c, c)
2873 && ps_has_conflicts (ps,
2877 /* Try different issue slots to find one that the given node can be
2878 scheduled in without conflicts. */
2879 while (has_conflicts)
2881 if (! ps_insn_advance_column (ps, ps_i, must_follow))
2883 has_conflicts = ps_has_conflicts (ps, c, c)
2885 && ps_has_conflicts (ps,
2892 remove_node_from_ps (ps, ps_i);
2896 ps->min_cycle = MIN (ps->min_cycle, c);
2897 ps->max_cycle = MAX (ps->max_cycle, c);
2901 /* Calculate the stage count of the partial schedule PS. The calculation
2902 takes into account the rotation to bring the closing branch to row
2905 calculate_stage_count (partial_schedule_ptr ps)
2907 int rotation_amount = (SCHED_TIME (ps->g->closing_branch)) + 1;
2908 int new_min_cycle = PS_MIN_CYCLE (ps) - rotation_amount;
2909 int new_max_cycle = PS_MAX_CYCLE (ps) - rotation_amount;
2910 int stage_count = CALC_STAGE_COUNT (-1, new_min_cycle, ps->ii);
2912 /* The calculation of stage count is done adding the number of stages
2913 before cycle zero and after cycle zero. */
2914 stage_count += CALC_STAGE_COUNT (new_max_cycle, 0, ps->ii);
2919 /* Rotate the rows of PS such that insns scheduled at time
2920 START_CYCLE will appear in row 0. Updates max/min_cycles. */
2922 rotate_partial_schedule (partial_schedule_ptr ps, int start_cycle)
2924 int i, row, backward_rotates;
2925 int last_row = ps->ii - 1;
2927 if (start_cycle == 0)
2930 backward_rotates = SMODULO (start_cycle, ps->ii);
2932 /* Revisit later and optimize this into a single loop. */
2933 for (i = 0; i < backward_rotates; i++)
2935 ps_insn_ptr first_row = ps->rows[0];
2936 int first_row_length = ps->rows_length[0];
2938 for (row = 0; row < last_row; row++)
2940 ps->rows[row] = ps->rows[row + 1];
2941 ps->rows_length[row] = ps->rows_length[row + 1];
2944 ps->rows[last_row] = first_row;
2945 ps->rows_length[last_row] = first_row_length;
2948 ps->max_cycle -= start_cycle;
2949 ps->min_cycle -= start_cycle;
2952 #endif /* INSN_SCHEDULING */
2955 gate_handle_sms (void)
2957 return (optimize > 0 && flag_modulo_sched);
2961 /* Run instruction scheduler. */
2962 /* Perform SMS module scheduling. */
2964 rest_of_handle_sms (void)
2966 #ifdef INSN_SCHEDULING
2969 /* Collect loop information to be used in SMS. */
2970 cfg_layout_initialize (0);
2973 /* Update the life information, because we add pseudos. */
2974 max_regno = max_reg_num ();
2976 /* Finalize layout changes. */
2978 if (bb->next_bb != EXIT_BLOCK_PTR)
2979 bb->aux = bb->next_bb;
2980 free_dominance_info (CDI_DOMINATORS);
2981 cfg_layout_finalize ();
2982 #endif /* INSN_SCHEDULING */
2986 struct rtl_opt_pass pass_sms =
2991 gate_handle_sms, /* gate */
2992 rest_of_handle_sms, /* execute */
2995 0, /* static_pass_number */
2997 0, /* properties_required */
2998 0, /* properties_provided */
2999 0, /* properties_destroyed */
3000 0, /* todo_flags_start */
3003 | TODO_verify_rtl_sharing
3004 | TODO_ggc_collect /* todo_flags_finish */