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 /* Identifies the instruction to be scheduled. Values smaller than
128 the ddg's num_nodes refer directly to ddg nodes. A value of
129 X - num_nodes refers to register move X. */
132 /* The (absolute) cycle in which the PS instruction is scheduled.
133 Same as SCHED_TIME (node). */
136 /* The next/prev PS_INSN in the same row. */
137 ps_insn_ptr next_in_row,
142 /* Information about a register move that has been added to a partial
144 struct ps_reg_move_info
146 /* The source of the move is defined by the ps_insn with id DEF.
147 The destination is used by the ps_insns with the ids in USES. */
151 /* The original form of USES' instructions used OLD_REG, but they
152 should now use NEW_REG. */
156 /* The number of consecutive stages that the move occupies. */
157 int num_consecutive_stages;
159 /* An instruction that sets NEW_REG to the correct value. The first
160 move associated with DEF will have an rhs of OLD_REG; later moves
161 use the result of the previous move. */
165 typedef struct ps_reg_move_info ps_reg_move_info;
166 DEF_VEC_O (ps_reg_move_info);
167 DEF_VEC_ALLOC_O (ps_reg_move_info, heap);
169 /* Holds the partial schedule as an array of II rows. Each entry of the
170 array points to a linked list of PS_INSNs, which represents the
171 instructions that are scheduled for that row. */
172 struct partial_schedule
174 int ii; /* Number of rows in the partial schedule. */
175 int history; /* Threshold for conflict checking using DFA. */
177 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
180 /* All the moves added for this partial schedule. Index X has
181 a ps_insn id of X + g->num_nodes. */
182 VEC (ps_reg_move_info, heap) *reg_moves;
184 /* rows_length[i] holds the number of instructions in the row.
185 It is used only (as an optimization) to back off quickly from
186 trying to schedule a node in a full row; that is, to avoid running
187 through futile DFA state transitions. */
190 /* The earliest absolute cycle of an insn in the partial schedule. */
193 /* The latest absolute cycle of an insn in the partial schedule. */
196 ddg_ptr g; /* The DDG of the insns in the partial schedule. */
198 int stage_count; /* The stage count of the partial schedule. */
202 static partial_schedule_ptr create_partial_schedule (int ii, ddg_ptr, int history);
203 static void free_partial_schedule (partial_schedule_ptr);
204 static void reset_partial_schedule (partial_schedule_ptr, int new_ii);
205 void print_partial_schedule (partial_schedule_ptr, FILE *);
206 static void verify_partial_schedule (partial_schedule_ptr, sbitmap);
207 static ps_insn_ptr ps_add_node_check_conflicts (partial_schedule_ptr,
208 int, int, sbitmap, sbitmap);
209 static void rotate_partial_schedule (partial_schedule_ptr, int);
210 void set_row_column_for_ps (partial_schedule_ptr);
211 static void ps_insert_empty_row (partial_schedule_ptr, int, sbitmap);
212 static int compute_split_row (sbitmap, int, int, int, ddg_node_ptr);
215 /* This page defines constants and structures for the modulo scheduling
218 static int sms_order_nodes (ddg_ptr, int, int *, int *);
219 static void set_node_sched_params (ddg_ptr);
220 static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int, int *);
221 static void permute_partial_schedule (partial_schedule_ptr, rtx);
222 static void generate_prolog_epilog (partial_schedule_ptr, struct loop *,
224 static int calculate_stage_count (partial_schedule_ptr, int);
225 static void calculate_must_precede_follow (ddg_node_ptr, int, int,
226 int, int, sbitmap, sbitmap, sbitmap);
227 static int get_sched_window (partial_schedule_ptr, ddg_node_ptr,
228 sbitmap, int, int *, int *, int *);
229 static bool try_scheduling_node_in_cycle (partial_schedule_ptr, int, int,
230 sbitmap, int *, sbitmap, sbitmap);
231 static void remove_node_from_ps (partial_schedule_ptr, ps_insn_ptr);
233 #define NODE_ASAP(node) ((node)->aux.count)
235 #define SCHED_PARAMS(x) VEC_index (node_sched_params, node_sched_param_vec, x)
236 #define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
237 #define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
238 #define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
239 #define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
241 /* The scheduling parameters held for each node. */
242 typedef struct node_sched_params
244 int time; /* The absolute scheduling cycle. */
246 int row; /* Holds time % ii. */
247 int stage; /* Holds time / ii. */
249 /* The column of a node inside the ps. If nodes u, v are on the same row,
250 u will precede v if column (u) < column (v). */
252 } *node_sched_params_ptr;
254 typedef struct node_sched_params node_sched_params;
255 DEF_VEC_O (node_sched_params);
256 DEF_VEC_ALLOC_O (node_sched_params, heap);
258 /* The following three functions are copied from the current scheduler
259 code in order to use sched_analyze() for computing the dependencies.
260 They are used when initializing the sched_info structure. */
262 sms_print_insn (const_rtx insn, int aligned ATTRIBUTE_UNUSED)
266 sprintf (tmp, "i%4d", INSN_UID (insn));
271 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
272 regset used ATTRIBUTE_UNUSED)
276 static struct common_sched_info_def sms_common_sched_info;
278 static struct sched_deps_info_def sms_sched_deps_info =
280 compute_jump_reg_dependencies,
281 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
286 static struct haifa_sched_info sms_sched_info =
295 NULL, /* insn_finishes_block_p */
300 NULL, NULL, NULL, NULL,
305 /* Partial schedule instruction ID in PS is a register move. Return
306 information about it. */
307 static struct ps_reg_move_info *
308 ps_reg_move (partial_schedule_ptr ps, int id)
310 gcc_checking_assert (id >= ps->g->num_nodes);
311 return VEC_index (ps_reg_move_info, ps->reg_moves, id - ps->g->num_nodes);
314 /* Return the rtl instruction that is being scheduled by partial schedule
315 instruction ID, which belongs to schedule PS. */
317 ps_rtl_insn (partial_schedule_ptr ps, int id)
319 if (id < ps->g->num_nodes)
320 return ps->g->nodes[id].insn;
322 return ps_reg_move (ps, id)->insn;
325 /* Partial schedule instruction ID, which belongs to PS, occured in
326 the original (unscheduled) loop. Return the first instruction
327 in the loop that was associated with ps_rtl_insn (PS, ID).
328 If the instruction had some notes before it, this is the first
331 ps_first_note (partial_schedule_ptr ps, int id)
333 gcc_assert (id < ps->g->num_nodes);
334 return ps->g->nodes[id].first_note;
337 /* Return the number of consecutive stages that are occupied by
338 partial schedule instruction ID in PS. */
340 ps_num_consecutive_stages (partial_schedule_ptr ps, int id)
342 if (id < ps->g->num_nodes)
345 return ps_reg_move (ps, id)->num_consecutive_stages;
348 /* Given HEAD and TAIL which are the first and last insns in a loop;
349 return the register which controls the loop. Return zero if it has
350 more than one occurrence in the loop besides the control part or the
351 do-loop pattern is not of the form we expect. */
353 doloop_register_get (rtx head ATTRIBUTE_UNUSED, rtx tail ATTRIBUTE_UNUSED)
355 #ifdef HAVE_doloop_end
356 rtx reg, condition, insn, first_insn_not_to_check;
361 /* TODO: Free SMS's dependence on doloop_condition_get. */
362 condition = doloop_condition_get (tail);
366 if (REG_P (XEXP (condition, 0)))
367 reg = XEXP (condition, 0);
368 else if (GET_CODE (XEXP (condition, 0)) == PLUS
369 && REG_P (XEXP (XEXP (condition, 0), 0)))
370 reg = XEXP (XEXP (condition, 0), 0);
374 /* Check that the COUNT_REG has no other occurrences in the loop
375 until the decrement. We assume the control part consists of
376 either a single (parallel) branch-on-count or a (non-parallel)
377 branch immediately preceded by a single (decrement) insn. */
378 first_insn_not_to_check = (GET_CODE (PATTERN (tail)) == PARALLEL ? tail
379 : prev_nondebug_insn (tail));
381 for (insn = head; insn != first_insn_not_to_check; insn = NEXT_INSN (insn))
382 if (!DEBUG_INSN_P (insn) && reg_mentioned_p (reg, insn))
386 fprintf (dump_file, "SMS count_reg found ");
387 print_rtl_single (dump_file, reg);
388 fprintf (dump_file, " outside control in insn:\n");
389 print_rtl_single (dump_file, insn);
401 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
402 that the number of iterations is a compile-time constant. If so,
403 return the rtx that sets COUNT_REG to a constant, and set COUNT to
404 this constant. Otherwise return 0. */
406 const_iteration_count (rtx count_reg, basic_block pre_header,
407 HOST_WIDEST_INT * count)
415 get_ebb_head_tail (pre_header, pre_header, &head, &tail);
417 for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn))
418 if (NONDEBUG_INSN_P (insn) && single_set (insn) &&
419 rtx_equal_p (count_reg, SET_DEST (single_set (insn))))
421 rtx pat = single_set (insn);
423 if (CONST_INT_P (SET_SRC (pat)))
425 *count = INTVAL (SET_SRC (pat));
435 /* A very simple resource-based lower bound on the initiation interval.
436 ??? Improve the accuracy of this bound by considering the
437 utilization of various units. */
441 if (targetm.sched.sms_res_mii)
442 return targetm.sched.sms_res_mii (g);
444 return ((g->num_nodes - g->num_debug) / issue_rate);
448 /* A vector that contains the sched data for each ps_insn. */
449 static VEC (node_sched_params, heap) *node_sched_param_vec;
451 /* Allocate sched_params for each node and initialize it. */
453 set_node_sched_params (ddg_ptr g)
455 VEC_truncate (node_sched_params, node_sched_param_vec, 0);
456 VEC_safe_grow_cleared (node_sched_params, heap,
457 node_sched_param_vec, g->num_nodes);
460 /* Make sure that node_sched_param_vec has an entry for every move in PS. */
462 extend_node_sched_params (partial_schedule_ptr ps)
464 VEC_safe_grow_cleared (node_sched_params, heap, node_sched_param_vec,
465 ps->g->num_nodes + VEC_length (ps_reg_move_info,
469 /* Update the sched_params (time, row and stage) for node U using the II,
470 the CYCLE of U and MIN_CYCLE.
471 We're not simply taking the following
472 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
473 because the stages may not be aligned on cycle 0. */
475 update_node_sched_params (int u, int ii, int cycle, int min_cycle)
477 int sc_until_cycle_zero;
480 SCHED_TIME (u) = cycle;
481 SCHED_ROW (u) = SMODULO (cycle, ii);
483 /* The calculation of stage count is done adding the number
484 of stages before cycle zero and after cycle zero. */
485 sc_until_cycle_zero = CALC_STAGE_COUNT (-1, min_cycle, ii);
487 if (SCHED_TIME (u) < 0)
489 stage = CALC_STAGE_COUNT (-1, SCHED_TIME (u), ii);
490 SCHED_STAGE (u) = sc_until_cycle_zero - stage;
494 stage = CALC_STAGE_COUNT (SCHED_TIME (u), 0, ii);
495 SCHED_STAGE (u) = sc_until_cycle_zero + stage - 1;
500 print_node_sched_params (FILE *file, int num_nodes, partial_schedule_ptr ps)
506 for (i = 0; i < num_nodes; i++)
508 node_sched_params_ptr nsp = SCHED_PARAMS (i);
510 fprintf (file, "Node = %d; INSN = %d\n", i,
511 INSN_UID (ps_rtl_insn (ps, i)));
512 fprintf (file, " asap = %d:\n", NODE_ASAP (&ps->g->nodes[i]));
513 fprintf (file, " time = %d:\n", nsp->time);
514 fprintf (file, " stage = %d:\n", nsp->stage);
518 /* Set SCHED_COLUMN for each instruction in row ROW of PS. */
520 set_columns_for_row (partial_schedule_ptr ps, int row)
522 ps_insn_ptr cur_insn;
526 for (cur_insn = ps->rows[row]; cur_insn; cur_insn = cur_insn->next_in_row)
527 SCHED_COLUMN (cur_insn->id) = column++;
530 /* Set SCHED_COLUMN for each instruction in PS. */
532 set_columns_for_ps (partial_schedule_ptr ps)
536 for (row = 0; row < ps->ii; row++)
537 set_columns_for_row (ps, row);
540 /* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
541 Its single predecessor has already been scheduled, as has its
542 ddg node successors. (The move may have also another move as its
543 successor, in which case that successor will be scheduled later.)
545 The move is part of a chain that satisfies register dependencies
546 between a producing ddg node and various consuming ddg nodes.
547 If some of these dependencies have a distance of 1 (meaning that
548 the use is upward-exposed) then DISTANCE1_USES is nonnull and
549 contains the set of uses with distance-1 dependencies.
550 DISTANCE1_USES is null otherwise.
552 MUST_FOLLOW is a scratch bitmap that is big enough to hold
553 all current ps_insn ids.
555 Return true on success. */
557 schedule_reg_move (partial_schedule_ptr ps, int i_reg_move,
558 sbitmap distance1_uses, sbitmap must_follow)
561 int this_time, this_distance, this_start, this_end, this_latency;
562 int start, end, c, ii;
563 sbitmap_iterator sbi;
564 ps_reg_move_info *move;
568 move = ps_reg_move (ps, i_reg_move);
572 fprintf (dump_file, "Scheduling register move INSN %d; ii = %d"
573 ", min cycle = %d\n\n", INSN_UID (move->insn), ii,
575 print_rtl_single (dump_file, move->insn);
576 fprintf (dump_file, "\n%11s %11s %5s\n", "start", "end", "time");
577 fprintf (dump_file, "=========== =========== =====\n");
583 /* For dependencies of distance 1 between a producer ddg node A
584 and consumer ddg node B, we have a chain of dependencies:
586 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
588 where Mi is the ith move. For dependencies of distance 0 between
589 a producer ddg node A and consumer ddg node C, we have a chain of
592 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
594 where Mi' occupies the same position as Mi but occurs a stage later.
595 We can only schedule each move once, so if we have both types of
596 chain, we model the second as:
598 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
600 First handle the dependencies between the previously-scheduled
601 predecessor and the move. */
602 this_insn = ps_rtl_insn (ps, move->def);
603 this_latency = insn_latency (this_insn, move->insn);
604 this_distance = distance1_uses && move->def < ps->g->num_nodes ? 1 : 0;
605 this_time = SCHED_TIME (move->def) - this_distance * ii;
606 this_start = this_time + this_latency;
607 this_end = this_time + ii;
609 fprintf (dump_file, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
610 this_start, this_end, SCHED_TIME (move->def),
611 INSN_UID (this_insn), this_latency, this_distance,
612 INSN_UID (move->insn));
614 if (start < this_start)
619 /* Handle the dependencies between the move and previously-scheduled
621 EXECUTE_IF_SET_IN_SBITMAP (move->uses, 0, u, sbi)
623 this_insn = ps_rtl_insn (ps, u);
624 this_latency = insn_latency (move->insn, this_insn);
625 if (distance1_uses && !TEST_BIT (distance1_uses, u))
629 this_time = SCHED_TIME (u) + this_distance * ii;
630 this_start = this_time - ii;
631 this_end = this_time - this_latency;
633 fprintf (dump_file, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
634 this_start, this_end, SCHED_TIME (u), INSN_UID (move->insn),
635 this_latency, this_distance, INSN_UID (this_insn));
637 if (start < this_start)
645 fprintf (dump_file, "----------- ----------- -----\n");
646 fprintf (dump_file, "%11d %11d %5s %s\n", start, end, "", "(max, min)");
649 sbitmap_zero (must_follow);
650 SET_BIT (must_follow, move->def);
652 start = MAX (start, end - (ii - 1));
653 for (c = end; c >= start; c--)
655 psi = ps_add_node_check_conflicts (ps, i_reg_move, c,
656 move->uses, must_follow);
659 update_node_sched_params (i_reg_move, ii, c, PS_MIN_CYCLE (ps));
661 fprintf (dump_file, "\nScheduled register move INSN %d at"
662 " time %d, row %d\n\n", INSN_UID (move->insn), c,
663 SCHED_ROW (i_reg_move));
669 fprintf (dump_file, "\nNo available slot\n\n");
675 Breaking intra-loop register anti-dependences:
676 Each intra-loop register anti-dependence implies a cross-iteration true
677 dependence of distance 1. Therefore, we can remove such false dependencies
678 and figure out if the partial schedule broke them by checking if (for a
679 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
680 if so generate a register move. The number of such moves is equal to:
681 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
682 nreg_moves = ----------------------------------- + 1 - { dependence.
686 schedule_reg_moves (partial_schedule_ptr ps)
692 for (i = 0; i < g->num_nodes; i++)
694 ddg_node_ptr u = &g->nodes[i];
696 int nreg_moves = 0, i_reg_move;
697 rtx prev_reg, old_reg;
701 sbitmap distance1_uses;
702 rtx set = single_set (u->insn);
704 /* Skip instructions that do not set a register. */
705 if ((set && !REG_P (SET_DEST (set))))
708 /* Compute the number of reg_moves needed for u, by looking at life
709 ranges started at u (excluding self-loops). */
710 distances[0] = distances[1] = false;
711 for (e = u->out; e; e = e->next_out)
712 if (e->type == TRUE_DEP && e->dest != e->src)
714 int nreg_moves4e = (SCHED_TIME (e->dest->cuid)
715 - SCHED_TIME (e->src->cuid)) / ii;
717 if (e->distance == 1)
718 nreg_moves4e = (SCHED_TIME (e->dest->cuid)
719 - SCHED_TIME (e->src->cuid) + ii) / ii;
721 /* If dest precedes src in the schedule of the kernel, then dest
722 will read before src writes and we can save one reg_copy. */
723 if (SCHED_ROW (e->dest->cuid) == SCHED_ROW (e->src->cuid)
724 && SCHED_COLUMN (e->dest->cuid) < SCHED_COLUMN (e->src->cuid))
727 if (nreg_moves4e >= 1)
729 /* !single_set instructions are not supported yet and
730 thus we do not except to encounter them in the loop
731 except from the doloop part. For the latter case
732 we assume no regmoves are generated as the doloop
733 instructions are tied to the branch with an edge. */
735 /* If the instruction contains auto-inc register then
736 validate that the regmov is being generated for the
737 target regsiter rather then the inc'ed register. */
738 gcc_assert (!autoinc_var_is_used_p (u->insn, e->dest->insn));
743 gcc_assert (e->distance < 2);
744 distances[e->distance] = true;
746 nreg_moves = MAX (nreg_moves, nreg_moves4e);
752 /* Create NREG_MOVES register moves. */
753 first_move = VEC_length (ps_reg_move_info, ps->reg_moves);
754 VEC_safe_grow_cleared (ps_reg_move_info, heap, ps->reg_moves,
755 first_move + nreg_moves);
756 extend_node_sched_params (ps);
758 /* Record the moves associated with this node. */
759 first_move += ps->g->num_nodes;
761 /* Generate each move. */
762 old_reg = prev_reg = SET_DEST (single_set (u->insn));
763 for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
765 ps_reg_move_info *move = ps_reg_move (ps, first_move + i_reg_move);
767 move->def = i_reg_move > 0 ? first_move + i_reg_move - 1 : i;
768 move->uses = sbitmap_alloc (first_move + nreg_moves);
769 move->old_reg = old_reg;
770 move->new_reg = gen_reg_rtx (GET_MODE (prev_reg));
771 move->num_consecutive_stages = distances[0] && distances[1] ? 2 : 1;
772 move->insn = gen_move_insn (move->new_reg, copy_rtx (prev_reg));
773 sbitmap_zero (move->uses);
775 prev_reg = move->new_reg;
778 distance1_uses = distances[1] ? sbitmap_alloc (g->num_nodes) : NULL;
780 /* Every use of the register defined by node may require a different
781 copy of this register, depending on the time the use is scheduled.
782 Record which uses require which move results. */
783 for (e = u->out; e; e = e->next_out)
784 if (e->type == TRUE_DEP && e->dest != e->src)
786 int dest_copy = (SCHED_TIME (e->dest->cuid)
787 - SCHED_TIME (e->src->cuid)) / ii;
789 if (e->distance == 1)
790 dest_copy = (SCHED_TIME (e->dest->cuid)
791 - SCHED_TIME (e->src->cuid) + ii) / ii;
793 if (SCHED_ROW (e->dest->cuid) == SCHED_ROW (e->src->cuid)
794 && SCHED_COLUMN (e->dest->cuid) < SCHED_COLUMN (e->src->cuid))
799 ps_reg_move_info *move;
801 move = ps_reg_move (ps, first_move + dest_copy - 1);
802 SET_BIT (move->uses, e->dest->cuid);
803 if (e->distance == 1)
804 SET_BIT (distance1_uses, e->dest->cuid);
808 must_follow = sbitmap_alloc (first_move + nreg_moves);
809 for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
810 if (!schedule_reg_move (ps, first_move + i_reg_move,
811 distance1_uses, must_follow))
813 sbitmap_free (must_follow);
815 sbitmap_free (distance1_uses);
816 if (i_reg_move < nreg_moves)
822 /* Emit the moves associatied with PS. Apply the substitutions
823 associated with them. */
825 apply_reg_moves (partial_schedule_ptr ps)
827 ps_reg_move_info *move;
830 FOR_EACH_VEC_ELT (ps_reg_move_info, ps->reg_moves, i, move)
833 sbitmap_iterator sbi;
835 EXECUTE_IF_SET_IN_SBITMAP (move->uses, 0, i_use, sbi)
837 replace_rtx (ps->g->nodes[i_use].insn, move->old_reg, move->new_reg);
838 df_insn_rescan (ps->g->nodes[i_use].insn);
843 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
844 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
845 will move to cycle zero. */
847 reset_sched_times (partial_schedule_ptr ps, int amount)
851 ps_insn_ptr crr_insn;
853 for (row = 0; row < ii; row++)
854 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
856 int u = crr_insn->id;
857 int normalized_time = SCHED_TIME (u) - amount;
858 int new_min_cycle = PS_MIN_CYCLE (ps) - amount;
862 /* Print the scheduling times after the rotation. */
863 rtx insn = ps_rtl_insn (ps, u);
865 fprintf (dump_file, "crr_insn->node=%d (insn id %d), "
866 "crr_insn->cycle=%d, min_cycle=%d", u,
867 INSN_UID (insn), normalized_time, new_min_cycle);
869 fprintf (dump_file, " (branch)");
870 fprintf (dump_file, "\n");
873 gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
874 gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
876 crr_insn->cycle = normalized_time;
877 update_node_sched_params (u, ii, normalized_time, new_min_cycle);
881 /* Permute the insns according to their order in PS, from row 0 to
882 row ii-1, and position them right before LAST. This schedules
883 the insns of the loop kernel. */
885 permute_partial_schedule (partial_schedule_ptr ps, rtx last)
891 for (row = 0; row < ii ; row++)
892 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
894 rtx insn = ps_rtl_insn (ps, ps_ij->id);
896 if (PREV_INSN (last) != insn)
898 if (ps_ij->id < ps->g->num_nodes)
899 reorder_insns_nobb (ps_first_note (ps, ps_ij->id), insn,
902 add_insn_before (insn, last, NULL);
907 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
908 respectively only if cycle C falls on the border of the scheduling
909 window boundaries marked by START and END cycles. STEP is the
910 direction of the window. */
912 set_must_precede_follow (sbitmap *tmp_follow, sbitmap must_follow,
913 sbitmap *tmp_precede, sbitmap must_precede, int c,
914 int start, int end, int step)
922 *tmp_precede = must_precede;
923 else /* step == -1. */
924 *tmp_follow = must_follow;
929 *tmp_follow = must_follow;
930 else /* step == -1. */
931 *tmp_precede = must_precede;
936 /* Return True if the branch can be moved to row ii-1 while
937 normalizing the partial schedule PS to start from cycle zero and thus
938 optimize the SC. Otherwise return False. */
940 optimize_sc (partial_schedule_ptr ps, ddg_ptr g)
942 int amount = PS_MIN_CYCLE (ps);
943 sbitmap sched_nodes = sbitmap_alloc (g->num_nodes);
944 int start, end, step;
947 int stage_count, stage_count_curr;
949 /* Compare the SC after normalization and SC after bringing the branch
950 to row ii-1. If they are equal just bail out. */
951 stage_count = calculate_stage_count (ps, amount);
953 calculate_stage_count (ps, SCHED_TIME (g->closing_branch->cuid) - (ii - 1));
955 if (stage_count == stage_count_curr)
958 fprintf (dump_file, "SMS SC already optimized.\n");
966 fprintf (dump_file, "SMS Trying to optimize branch location\n");
967 fprintf (dump_file, "SMS partial schedule before trial:\n");
968 print_partial_schedule (ps, dump_file);
971 /* First, normalize the partial scheduling. */
972 reset_sched_times (ps, amount);
973 rotate_partial_schedule (ps, amount);
977 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
979 print_partial_schedule (ps, dump_file);
982 if (SMODULO (SCHED_TIME (g->closing_branch->cuid), ii) == ii - 1)
988 sbitmap_ones (sched_nodes);
990 /* Calculate the new placement of the branch. It should be in row
991 ii-1 and fall into it's scheduling window. */
992 if (get_sched_window (ps, g->closing_branch, sched_nodes, ii, &start,
996 ps_insn_ptr next_ps_i;
997 int branch_cycle = SCHED_TIME (g->closing_branch->cuid);
998 int row = SMODULO (branch_cycle, ps->ii);
1000 sbitmap must_precede, must_follow, tmp_precede, tmp_follow;
1004 fprintf (dump_file, "\nTrying to schedule node %d "
1005 "INSN = %d in (%d .. %d) step %d\n",
1006 g->closing_branch->cuid,
1007 (INSN_UID (g->closing_branch->insn)), start, end, step);
1009 gcc_assert ((step > 0 && start < end) || (step < 0 && start > end));
1012 c = start + ii - SMODULO (start, ii) - 1;
1013 gcc_assert (c >= start);
1019 "SMS failed to schedule branch at cycle: %d\n", c);
1025 c = start - SMODULO (start, ii) - 1;
1026 gcc_assert (c <= start);
1032 "SMS failed to schedule branch at cycle: %d\n", c);
1038 must_precede = sbitmap_alloc (g->num_nodes);
1039 must_follow = sbitmap_alloc (g->num_nodes);
1041 /* Try to schedule the branch is it's new cycle. */
1042 calculate_must_precede_follow (g->closing_branch, start, end,
1043 step, ii, sched_nodes,
1044 must_precede, must_follow);
1046 set_must_precede_follow (&tmp_follow, must_follow, &tmp_precede,
1047 must_precede, c, start, end, step);
1049 /* Find the element in the partial schedule related to the closing
1050 branch so we can remove it from it's current cycle. */
1051 for (next_ps_i = ps->rows[row];
1052 next_ps_i; next_ps_i = next_ps_i->next_in_row)
1053 if (next_ps_i->id == g->closing_branch->cuid)
1056 remove_node_from_ps (ps, next_ps_i);
1058 try_scheduling_node_in_cycle (ps, g->closing_branch->cuid, c,
1059 sched_nodes, &num_splits,
1060 tmp_precede, tmp_follow);
1061 gcc_assert (num_splits == 0);
1066 "SMS failed to schedule branch at cycle: %d, "
1067 "bringing it back to cycle %d\n", c, branch_cycle);
1069 /* The branch was failed to be placed in row ii - 1.
1070 Put it back in it's original place in the partial
1072 set_must_precede_follow (&tmp_follow, must_follow, &tmp_precede,
1073 must_precede, branch_cycle, start, end,
1076 try_scheduling_node_in_cycle (ps, g->closing_branch->cuid,
1077 branch_cycle, sched_nodes,
1078 &num_splits, tmp_precede,
1080 gcc_assert (success && (num_splits == 0));
1085 /* The branch is placed in row ii - 1. */
1088 "SMS success in moving branch to cycle %d\n", c);
1090 update_node_sched_params (g->closing_branch->cuid, ii, c,
1095 free (must_precede);
1105 duplicate_insns_of_cycles (partial_schedule_ptr ps, int from_stage,
1106 int to_stage, rtx count_reg)
1111 for (row = 0; row < ps->ii; row++)
1112 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
1115 int first_u, last_u;
1118 /* Do not duplicate any insn which refers to count_reg as it
1119 belongs to the control part.
1120 The closing branch is scheduled as well and thus should
1122 TODO: This should be done by analyzing the control part of
1124 u_insn = ps_rtl_insn (ps, u);
1125 if (reg_mentioned_p (count_reg, u_insn)
1129 first_u = SCHED_STAGE (u);
1130 last_u = first_u + ps_num_consecutive_stages (ps, u) - 1;
1131 if (from_stage <= last_u && to_stage >= first_u)
1133 if (u < ps->g->num_nodes)
1134 duplicate_insn_chain (ps_first_note (ps, u), u_insn);
1136 emit_insn (copy_rtx (PATTERN (u_insn)));
1142 /* Generate the instructions (including reg_moves) for prolog & epilog. */
1144 generate_prolog_epilog (partial_schedule_ptr ps, struct loop *loop,
1145 rtx count_reg, rtx count_init)
1148 int last_stage = PS_STAGE_COUNT (ps) - 1;
1151 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1156 /* Generate instructions at the beginning of the prolog to
1157 adjust the loop count by STAGE_COUNT. If loop count is constant
1158 (count_init), this constant is adjusted by STAGE_COUNT in
1159 generate_prolog_epilog function. */
1160 rtx sub_reg = NULL_RTX;
1162 sub_reg = expand_simple_binop (GET_MODE (count_reg), MINUS,
1163 count_reg, GEN_INT (last_stage),
1164 count_reg, 1, OPTAB_DIRECT);
1165 gcc_assert (REG_P (sub_reg));
1166 if (REGNO (sub_reg) != REGNO (count_reg))
1167 emit_move_insn (count_reg, sub_reg);
1170 for (i = 0; i < last_stage; i++)
1171 duplicate_insns_of_cycles (ps, 0, i, count_reg);
1173 /* Put the prolog on the entry edge. */
1174 e = loop_preheader_edge (loop);
1175 split_edge_and_insert (e, get_insns ());
1176 if (!flag_resched_modulo_sched)
1177 e->dest->flags |= BB_DISABLE_SCHEDULE;
1181 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1184 for (i = 0; i < last_stage; i++)
1185 duplicate_insns_of_cycles (ps, i + 1, last_stage, count_reg);
1187 /* Put the epilogue on the exit edge. */
1188 gcc_assert (single_exit (loop));
1189 e = single_exit (loop);
1190 split_edge_and_insert (e, get_insns ());
1191 if (!flag_resched_modulo_sched)
1192 e->dest->flags |= BB_DISABLE_SCHEDULE;
1197 /* Mark LOOP as software pipelined so the later
1198 scheduling passes don't touch it. */
1200 mark_loop_unsched (struct loop *loop)
1203 basic_block *bbs = get_loop_body (loop);
1205 for (i = 0; i < loop->num_nodes; i++)
1206 bbs[i]->flags |= BB_DISABLE_SCHEDULE;
1211 /* Return true if all the BBs of the loop are empty except the
1214 loop_single_full_bb_p (struct loop *loop)
1217 basic_block *bbs = get_loop_body (loop);
1219 for (i = 0; i < loop->num_nodes ; i++)
1222 bool empty_bb = true;
1224 if (bbs[i] == loop->header)
1227 /* Make sure that basic blocks other than the header
1228 have only notes labels or jumps. */
1229 get_ebb_head_tail (bbs[i], bbs[i], &head, &tail);
1230 for (; head != NEXT_INSN (tail); head = NEXT_INSN (head))
1232 if (NOTE_P (head) || LABEL_P (head)
1233 || (INSN_P (head) && (DEBUG_INSN_P (head) || JUMP_P (head))))
1249 /* A simple loop from SMS point of view; it is a loop that is composed of
1250 either a single basic block or two BBs - a header and a latch. */
1251 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1252 && (EDGE_COUNT (loop->latch->preds) == 1) \
1253 && (EDGE_COUNT (loop->latch->succs) == 1))
1255 /* Return true if the loop is in its canonical form and false if not.
1256 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1258 loop_canon_p (struct loop *loop)
1261 if (loop->inner || !loop_outer (loop))
1264 fprintf (dump_file, "SMS loop inner or !loop_outer\n");
1268 if (!single_exit (loop))
1272 rtx insn = BB_END (loop->header);
1274 fprintf (dump_file, "SMS loop many exits ");
1275 fprintf (dump_file, " %s %d (file, line)\n",
1276 insn_file (insn), insn_line (insn));
1281 if (! SIMPLE_SMS_LOOP_P (loop) && ! loop_single_full_bb_p (loop))
1285 rtx insn = BB_END (loop->header);
1287 fprintf (dump_file, "SMS loop many BBs. ");
1288 fprintf (dump_file, " %s %d (file, line)\n",
1289 insn_file (insn), insn_line (insn));
1297 /* If there are more than one entry for the loop,
1298 make it one by splitting the first entry edge and
1299 redirecting the others to the new BB. */
1301 canon_loop (struct loop *loop)
1306 /* Avoid annoying special cases of edges going to exit
1308 FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR->preds)
1309 if ((e->flags & EDGE_FALLTHRU) && (EDGE_COUNT (e->src->succs) > 1))
1312 if (loop->latch == loop->header
1313 || EDGE_COUNT (loop->latch->succs) > 1)
1315 FOR_EACH_EDGE (e, i, loop->header->preds)
1316 if (e->src == loop->latch)
1324 setup_sched_infos (void)
1326 memcpy (&sms_common_sched_info, &haifa_common_sched_info,
1327 sizeof (sms_common_sched_info));
1328 sms_common_sched_info.sched_pass_id = SCHED_SMS_PASS;
1329 common_sched_info = &sms_common_sched_info;
1331 sched_deps_info = &sms_sched_deps_info;
1332 current_sched_info = &sms_sched_info;
1335 /* Probability in % that the sms-ed loop rolls enough so that optimized
1336 version may be entered. Just a guess. */
1337 #define PROB_SMS_ENOUGH_ITERATIONS 80
1339 /* Used to calculate the upper bound of ii. */
1340 #define MAXII_FACTOR 2
1342 /* Main entry point, perform SMS scheduling on the loops of the function
1343 that consist of single basic blocks. */
1350 int maxii, max_asap;
1352 partial_schedule_ptr ps;
1353 basic_block bb = NULL;
1355 basic_block condition_bb = NULL;
1357 gcov_type trip_count = 0;
1359 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1360 | LOOPS_HAVE_RECORDED_EXITS);
1361 if (number_of_loops () <= 1)
1363 loop_optimizer_finalize ();
1364 return; /* There are no loops to schedule. */
1367 /* Initialize issue_rate. */
1368 if (targetm.sched.issue_rate)
1370 int temp = reload_completed;
1372 reload_completed = 1;
1373 issue_rate = targetm.sched.issue_rate ();
1374 reload_completed = temp;
1379 /* Initialize the scheduler. */
1380 setup_sched_infos ();
1381 haifa_sched_init ();
1383 /* Allocate memory to hold the DDG array one entry for each loop.
1384 We use loop->num as index into this array. */
1385 g_arr = XCNEWVEC (ddg_ptr, number_of_loops ());
1389 fprintf (dump_file, "\n\nSMS analysis phase\n");
1390 fprintf (dump_file, "===================\n\n");
1393 /* Build DDGs for all the relevant loops and hold them in G_ARR
1394 indexed by the loop index. */
1395 FOR_EACH_LOOP (li, loop, 0)
1400 /* For debugging. */
1401 if (dbg_cnt (sms_sched_loop) == false)
1404 fprintf (dump_file, "SMS reached max limit... \n");
1411 rtx insn = BB_END (loop->header);
1413 fprintf (dump_file, "SMS loop num: %d, file: %s, line: %d\n",
1414 loop->num, insn_file (insn), insn_line (insn));
1418 if (! loop_canon_p (loop))
1421 if (! loop_single_full_bb_p (loop))
1424 fprintf (dump_file, "SMS not loop_single_full_bb_p\n");
1430 get_ebb_head_tail (bb, bb, &head, &tail);
1431 latch_edge = loop_latch_edge (loop);
1432 gcc_assert (single_exit (loop));
1433 if (single_exit (loop)->count)
1434 trip_count = latch_edge->count / single_exit (loop)->count;
1436 /* Perform SMS only on loops that their average count is above threshold. */
1438 if ( latch_edge->count
1439 && (latch_edge->count < single_exit (loop)->count * SMS_LOOP_AVERAGE_COUNT_THRESHOLD))
1443 fprintf (dump_file, " %s %d (file, line)\n",
1444 insn_file (tail), insn_line (tail));
1445 fprintf (dump_file, "SMS single-bb-loop\n");
1446 if (profile_info && flag_branch_probabilities)
1448 fprintf (dump_file, "SMS loop-count ");
1449 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1450 (HOST_WIDEST_INT) bb->count);
1451 fprintf (dump_file, "\n");
1452 fprintf (dump_file, "SMS trip-count ");
1453 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1454 (HOST_WIDEST_INT) trip_count);
1455 fprintf (dump_file, "\n");
1456 fprintf (dump_file, "SMS profile-sum-max ");
1457 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1458 (HOST_WIDEST_INT) profile_info->sum_max);
1459 fprintf (dump_file, "\n");
1465 /* Make sure this is a doloop. */
1466 if ( !(count_reg = doloop_register_get (head, tail)))
1469 fprintf (dump_file, "SMS doloop_register_get failed\n");
1473 /* Don't handle BBs with calls or barriers
1474 or !single_set with the exception of instructions that include
1475 count_reg---these instructions are part of the control part
1476 that do-loop recognizes.
1477 ??? Should handle insns defining subregs. */
1478 for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn))
1484 || (NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
1485 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE
1486 && !reg_mentioned_p (count_reg, insn))
1487 || (INSN_P (insn) && (set = single_set (insn))
1488 && GET_CODE (SET_DEST (set)) == SUBREG))
1492 if (insn != NEXT_INSN (tail))
1497 fprintf (dump_file, "SMS loop-with-call\n");
1498 else if (BARRIER_P (insn))
1499 fprintf (dump_file, "SMS loop-with-barrier\n");
1500 else if ((NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
1501 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE))
1502 fprintf (dump_file, "SMS loop-with-not-single-set\n");
1504 fprintf (dump_file, "SMS loop with subreg in lhs\n");
1505 print_rtl_single (dump_file, insn);
1511 /* Always schedule the closing branch with the rest of the
1512 instructions. The branch is rotated to be in row ii-1 at the
1513 end of the scheduling procedure to make sure it's the last
1514 instruction in the iteration. */
1515 if (! (g = create_ddg (bb, 1)))
1518 fprintf (dump_file, "SMS create_ddg failed\n");
1522 g_arr[loop->num] = g;
1524 fprintf (dump_file, "...OK\n");
1529 fprintf (dump_file, "\nSMS transformation phase\n");
1530 fprintf (dump_file, "=========================\n\n");
1533 /* We don't want to perform SMS on new loops - created by versioning. */
1534 FOR_EACH_LOOP (li, loop, 0)
1537 rtx count_reg, count_init;
1538 int mii, rec_mii, stage_count, min_cycle;
1539 HOST_WIDEST_INT loop_count = 0;
1542 if (! (g = g_arr[loop->num]))
1547 rtx insn = BB_END (loop->header);
1549 fprintf (dump_file, "SMS loop num: %d, file: %s, line: %d\n",
1550 loop->num, insn_file (insn), insn_line (insn));
1552 print_ddg (dump_file, g);
1555 get_ebb_head_tail (loop->header, loop->header, &head, &tail);
1557 latch_edge = loop_latch_edge (loop);
1558 gcc_assert (single_exit (loop));
1559 if (single_exit (loop)->count)
1560 trip_count = latch_edge->count / single_exit (loop)->count;
1564 fprintf (dump_file, " %s %d (file, line)\n",
1565 insn_file (tail), insn_line (tail));
1566 fprintf (dump_file, "SMS single-bb-loop\n");
1567 if (profile_info && flag_branch_probabilities)
1569 fprintf (dump_file, "SMS loop-count ");
1570 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1571 (HOST_WIDEST_INT) bb->count);
1572 fprintf (dump_file, "\n");
1573 fprintf (dump_file, "SMS profile-sum-max ");
1574 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1575 (HOST_WIDEST_INT) profile_info->sum_max);
1576 fprintf (dump_file, "\n");
1578 fprintf (dump_file, "SMS doloop\n");
1579 fprintf (dump_file, "SMS built-ddg %d\n", g->num_nodes);
1580 fprintf (dump_file, "SMS num-loads %d\n", g->num_loads);
1581 fprintf (dump_file, "SMS num-stores %d\n", g->num_stores);
1585 /* In case of th loop have doloop register it gets special
1587 count_init = NULL_RTX;
1588 if ((count_reg = doloop_register_get (head, tail)))
1590 basic_block pre_header;
1592 pre_header = loop_preheader_edge (loop)->src;
1593 count_init = const_iteration_count (count_reg, pre_header,
1596 gcc_assert (count_reg);
1598 if (dump_file && count_init)
1600 fprintf (dump_file, "SMS const-doloop ");
1601 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1603 fprintf (dump_file, "\n");
1606 node_order = XNEWVEC (int, g->num_nodes);
1608 mii = 1; /* Need to pass some estimate of mii. */
1609 rec_mii = sms_order_nodes (g, mii, node_order, &max_asap);
1610 mii = MAX (res_MII (g), rec_mii);
1611 maxii = MAX (max_asap, MAXII_FACTOR * mii);
1614 fprintf (dump_file, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1615 rec_mii, mii, maxii);
1619 set_node_sched_params (g);
1623 ps = sms_schedule_by_order (g, mii, maxii, node_order);
1627 /* Try to achieve optimized SC by normalizing the partial
1628 schedule (having the cycles start from cycle zero).
1629 The branch location must be placed in row ii-1 in the
1630 final scheduling. If failed, shift all instructions to
1631 position the branch in row ii-1. */
1632 opt_sc_p = optimize_sc (ps, g);
1634 stage_count = calculate_stage_count (ps, 0);
1637 /* Bring the branch to cycle ii-1. */
1638 int amount = (SCHED_TIME (g->closing_branch->cuid)
1642 fprintf (dump_file, "SMS schedule branch at cycle ii-1\n");
1644 stage_count = calculate_stage_count (ps, amount);
1647 gcc_assert (stage_count >= 1);
1650 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
1651 1 means that there is no interleaving between iterations thus
1652 we let the scheduling passes do the job in this case. */
1653 if (stage_count < PARAM_VALUE (PARAM_SMS_MIN_SC)
1654 || (count_init && (loop_count <= stage_count))
1655 || (flag_branch_probabilities && (trip_count <= stage_count)))
1659 fprintf (dump_file, "SMS failed... \n");
1660 fprintf (dump_file, "SMS sched-failed (stage-count=%d,"
1661 " loop-count=", stage_count);
1662 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, loop_count);
1663 fprintf (dump_file, ", trip-count=");
1664 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, trip_count);
1665 fprintf (dump_file, ")\n");
1672 /* Rotate the partial schedule to have the branch in row ii-1. */
1673 int amount = SCHED_TIME (g->closing_branch->cuid) - (ps->ii - 1);
1675 reset_sched_times (ps, amount);
1676 rotate_partial_schedule (ps, amount);
1679 set_columns_for_ps (ps);
1681 min_cycle = PS_MIN_CYCLE (ps) - SMODULO (PS_MIN_CYCLE (ps), ps->ii);
1682 if (!schedule_reg_moves (ps))
1685 free_partial_schedule (ps);
1689 /* Moves that handle incoming values might have been added
1690 to a new first stage. Bump the stage count if so.
1692 ??? Perhaps we could consider rotating the schedule here
1694 if (PS_MIN_CYCLE (ps) < min_cycle)
1696 reset_sched_times (ps, 0);
1700 /* The stage count should now be correct without rotation. */
1701 gcc_checking_assert (stage_count == calculate_stage_count (ps, 0));
1702 PS_STAGE_COUNT (ps) = stage_count;
1709 "%s:%d SMS succeeded %d %d (with ii, sc)\n",
1710 insn_file (tail), insn_line (tail), ps->ii, stage_count);
1711 print_partial_schedule (ps, dump_file);
1714 /* case the BCT count is not known , Do loop-versioning */
1715 if (count_reg && ! count_init)
1717 rtx comp_rtx = gen_rtx_fmt_ee (GT, VOIDmode, count_reg,
1718 GEN_INT(stage_count));
1719 unsigned prob = (PROB_SMS_ENOUGH_ITERATIONS
1720 * REG_BR_PROB_BASE) / 100;
1722 loop_version (loop, comp_rtx, &condition_bb,
1723 prob, prob, REG_BR_PROB_BASE - prob,
1727 /* Set new iteration count of loop kernel. */
1728 if (count_reg && count_init)
1729 SET_SRC (single_set (count_init)) = GEN_INT (loop_count
1732 /* Now apply the scheduled kernel to the RTL of the loop. */
1733 permute_partial_schedule (ps, g->closing_branch->first_note);
1735 /* Mark this loop as software pipelined so the later
1736 scheduling passes don't touch it. */
1737 if (! flag_resched_modulo_sched)
1738 mark_loop_unsched (loop);
1740 /* The life-info is not valid any more. */
1741 df_set_bb_dirty (g->bb);
1743 apply_reg_moves (ps);
1745 print_node_sched_params (dump_file, g->num_nodes, ps);
1746 /* Generate prolog and epilog. */
1747 generate_prolog_epilog (ps, loop, count_reg, count_init);
1751 free_partial_schedule (ps);
1752 VEC_free (node_sched_params, heap, node_sched_param_vec);
1759 /* Release scheduler data, needed until now because of DFA. */
1760 haifa_sched_finish ();
1761 loop_optimizer_finalize ();
1764 /* The SMS scheduling algorithm itself
1765 -----------------------------------
1766 Input: 'O' an ordered list of insns of a loop.
1767 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1769 'Q' is the empty Set
1770 'PS' is the partial schedule; it holds the currently scheduled nodes with
1772 'PSP' previously scheduled predecessors.
1773 'PSS' previously scheduled successors.
1774 't(u)' the cycle where u is scheduled.
1775 'l(u)' is the latency of u.
1776 'd(v,u)' is the dependence distance from v to u.
1777 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1778 the node ordering phase.
1779 'check_hardware_resources_conflicts(u, PS, c)'
1780 run a trace around cycle/slot through DFA model
1781 to check resource conflicts involving instruction u
1782 at cycle c given the partial schedule PS.
1783 'add_to_partial_schedule_at_time(u, PS, c)'
1784 Add the node/instruction u to the partial schedule
1786 'calculate_register_pressure(PS)'
1787 Given a schedule of instructions, calculate the register
1788 pressure it implies. One implementation could be the
1789 maximum number of overlapping live ranges.
1790 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1791 registers available in the hardware.
1795 3. for each node u in O in pre-computed order
1796 4. if (PSP(u) != Q && PSS(u) == Q) then
1797 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1798 6. start = Early_start; end = Early_start + II - 1; step = 1
1799 11. else if (PSP(u) == Q && PSS(u) != Q) then
1800 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1801 13. start = Late_start; end = Late_start - II + 1; step = -1
1802 14. else if (PSP(u) != Q && PSS(u) != Q) then
1803 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1804 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1805 17. start = Early_start;
1806 18. end = min(Early_start + II - 1 , Late_start);
1808 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1809 21. start = ASAP(u); end = start + II - 1; step = 1
1813 24. for (c = start ; c != end ; c += step)
1814 25. if check_hardware_resources_conflicts(u, PS, c) then
1815 26. add_to_partial_schedule_at_time(u, PS, c)
1820 31. if (success == false) then
1822 33. if (II > maxII) then
1823 34. finish - failed to schedule
1828 39. if (calculate_register_pressure(PS) > maxRP) then
1831 42. compute epilogue & prologue
1832 43. finish - succeeded to schedule
1834 ??? The algorithm restricts the scheduling window to II cycles.
1835 In rare cases, it may be better to allow windows of II+1 cycles.
1836 The window would then start and end on the same row, but with
1837 different "must precede" and "must follow" requirements. */
1839 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1840 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1841 set to 0 to save compile time. */
1842 #define DFA_HISTORY SMS_DFA_HISTORY
1844 /* A threshold for the number of repeated unsuccessful attempts to insert
1845 an empty row, before we flush the partial schedule and start over. */
1846 #define MAX_SPLIT_NUM 10
1847 /* Given the partial schedule PS, this function calculates and returns the
1848 cycles in which we can schedule the node with the given index I.
1849 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1850 noticed that there are several cases in which we fail to SMS the loop
1851 because the sched window of a node is empty due to tight data-deps. In
1852 such cases we want to unschedule some of the predecessors/successors
1853 until we get non-empty scheduling window. It returns -1 if the
1854 scheduling window is empty and zero otherwise. */
1857 get_sched_window (partial_schedule_ptr ps, ddg_node_ptr u_node,
1858 sbitmap sched_nodes, int ii, int *start_p, int *step_p,
1861 int start, step, end;
1862 int early_start, late_start;
1864 sbitmap psp = sbitmap_alloc (ps->g->num_nodes);
1865 sbitmap pss = sbitmap_alloc (ps->g->num_nodes);
1866 sbitmap u_node_preds = NODE_PREDECESSORS (u_node);
1867 sbitmap u_node_succs = NODE_SUCCESSORS (u_node);
1873 /* 1. compute sched window for u (start, end, step). */
1876 psp_not_empty = sbitmap_a_and_b_cg (psp, u_node_preds, sched_nodes);
1877 pss_not_empty = sbitmap_a_and_b_cg (pss, u_node_succs, sched_nodes);
1879 /* We first compute a forward range (start <= end), then decide whether
1881 early_start = INT_MIN;
1882 late_start = INT_MAX;
1890 if (dump_file && (psp_not_empty || pss_not_empty))
1892 fprintf (dump_file, "\nAnalyzing dependencies for node %d (INSN %d)"
1893 "; ii = %d\n\n", u_node->cuid, INSN_UID (u_node->insn), ii);
1894 fprintf (dump_file, "%11s %11s %11s %11s %5s\n",
1895 "start", "early start", "late start", "end", "time");
1896 fprintf (dump_file, "=========== =========== =========== ==========="
1899 /* Calculate early_start and limit end. Both bounds are inclusive. */
1901 for (e = u_node->in; e != 0; e = e->next_in)
1903 int v = e->src->cuid;
1905 if (TEST_BIT (sched_nodes, v))
1907 int p_st = SCHED_TIME (v);
1908 int earliest = p_st + e->latency - (e->distance * ii);
1909 int latest = (e->data_type == MEM_DEP ? p_st + ii - 1 : INT_MAX);
1913 fprintf (dump_file, "%11s %11d %11s %11d %5d",
1914 "", earliest, "", latest, p_st);
1915 print_ddg_edge (dump_file, e);
1916 fprintf (dump_file, "\n");
1919 early_start = MAX (early_start, earliest);
1920 end = MIN (end, latest);
1922 if (e->type == TRUE_DEP && e->data_type == REG_DEP)
1927 /* Calculate late_start and limit start. Both bounds are inclusive. */
1929 for (e = u_node->out; e != 0; e = e->next_out)
1931 int v = e->dest->cuid;
1933 if (TEST_BIT (sched_nodes, v))
1935 int s_st = SCHED_TIME (v);
1936 int earliest = (e->data_type == MEM_DEP ? s_st - ii + 1 : INT_MIN);
1937 int latest = s_st - e->latency + (e->distance * ii);
1941 fprintf (dump_file, "%11d %11s %11d %11s %5d",
1942 earliest, "", latest, "", s_st);
1943 print_ddg_edge (dump_file, e);
1944 fprintf (dump_file, "\n");
1947 start = MAX (start, earliest);
1948 late_start = MIN (late_start, latest);
1950 if (e->type == TRUE_DEP && e->data_type == REG_DEP)
1955 if (dump_file && (psp_not_empty || pss_not_empty))
1957 fprintf (dump_file, "----------- ----------- ----------- -----------"
1959 fprintf (dump_file, "%11d %11d %11d %11d %5s %s\n",
1960 start, early_start, late_start, end, "",
1961 "(max, max, min, min)");
1964 /* Get a target scheduling window no bigger than ii. */
1965 if (early_start == INT_MIN && late_start == INT_MAX)
1966 early_start = NODE_ASAP (u_node);
1967 else if (early_start == INT_MIN)
1968 early_start = late_start - (ii - 1);
1969 late_start = MIN (late_start, early_start + (ii - 1));
1971 /* Apply memory dependence limits. */
1972 start = MAX (start, early_start);
1973 end = MIN (end, late_start);
1975 if (dump_file && (psp_not_empty || pss_not_empty))
1976 fprintf (dump_file, "%11s %11d %11d %11s %5s final window\n",
1977 "", start, end, "", "");
1979 /* If there are at least as many successors as predecessors, schedule the
1980 node close to its successors. */
1981 if (pss_not_empty && count_succs >= count_preds)
1989 /* Now that we've finalized the window, make END an exclusive rather
1990 than an inclusive bound. */
1999 if ((start >= end && step == 1) || (start <= end && step == -1))
2002 fprintf (dump_file, "\nEmpty window: start=%d, end=%d, step=%d\n",
2010 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
2011 node currently been scheduled. At the end of the calculation
2012 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
2013 U_NODE which are (1) already scheduled in the first/last row of
2014 U_NODE's scheduling window, (2) whose dependence inequality with U
2015 becomes an equality when U is scheduled in this same row, and (3)
2016 whose dependence latency is zero.
2018 The first and last rows are calculated using the following parameters:
2019 START/END rows - The cycles that begins/ends the traversal on the window;
2020 searching for an empty cycle to schedule U_NODE.
2021 STEP - The direction in which we traverse the window.
2022 II - The initiation interval. */
2025 calculate_must_precede_follow (ddg_node_ptr u_node, int start, int end,
2026 int step, int ii, sbitmap sched_nodes,
2027 sbitmap must_precede, sbitmap must_follow)
2030 int first_cycle_in_window, last_cycle_in_window;
2032 gcc_assert (must_precede && must_follow);
2034 /* Consider the following scheduling window:
2035 {first_cycle_in_window, first_cycle_in_window+1, ...,
2036 last_cycle_in_window}. If step is 1 then the following will be
2037 the order we traverse the window: {start=first_cycle_in_window,
2038 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
2039 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
2040 end=first_cycle_in_window-1} if step is -1. */
2041 first_cycle_in_window = (step == 1) ? start : end - step;
2042 last_cycle_in_window = (step == 1) ? end - step : start;
2044 sbitmap_zero (must_precede);
2045 sbitmap_zero (must_follow);
2048 fprintf (dump_file, "\nmust_precede: ");
2050 /* Instead of checking if:
2051 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
2052 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
2053 first_cycle_in_window)
2055 we use the fact that latency is non-negative:
2056 SCHED_TIME (e->src) - (e->distance * ii) <=
2057 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
2058 first_cycle_in_window
2060 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
2061 for (e = u_node->in; e != 0; e = e->next_in)
2062 if (TEST_BIT (sched_nodes, e->src->cuid)
2063 && ((SCHED_TIME (e->src->cuid) - (e->distance * ii)) ==
2064 first_cycle_in_window))
2067 fprintf (dump_file, "%d ", e->src->cuid);
2069 SET_BIT (must_precede, e->src->cuid);
2073 fprintf (dump_file, "\nmust_follow: ");
2075 /* Instead of checking if:
2076 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
2077 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
2078 last_cycle_in_window)
2080 we use the fact that latency is non-negative:
2081 SCHED_TIME (e->dest) + (e->distance * ii) >=
2082 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
2083 last_cycle_in_window
2085 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
2086 for (e = u_node->out; e != 0; e = e->next_out)
2087 if (TEST_BIT (sched_nodes, e->dest->cuid)
2088 && ((SCHED_TIME (e->dest->cuid) + (e->distance * ii)) ==
2089 last_cycle_in_window))
2092 fprintf (dump_file, "%d ", e->dest->cuid);
2094 SET_BIT (must_follow, e->dest->cuid);
2098 fprintf (dump_file, "\n");
2101 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
2102 parameters to decide if that's possible:
2103 PS - The partial schedule.
2104 U - The serial number of U_NODE.
2105 NUM_SPLITS - The number of row splits made so far.
2106 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
2107 the first row of the scheduling window)
2108 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
2109 last row of the scheduling window) */
2112 try_scheduling_node_in_cycle (partial_schedule_ptr ps,
2113 int u, int cycle, sbitmap sched_nodes,
2114 int *num_splits, sbitmap must_precede,
2115 sbitmap must_follow)
2120 verify_partial_schedule (ps, sched_nodes);
2121 psi = ps_add_node_check_conflicts (ps, u, cycle, must_precede, must_follow);
2124 SCHED_TIME (u) = cycle;
2125 SET_BIT (sched_nodes, u);
2129 fprintf (dump_file, "Scheduled w/o split in %d\n", cycle);
2136 /* This function implements the scheduling algorithm for SMS according to the
2138 static partial_schedule_ptr
2139 sms_schedule_by_order (ddg_ptr g, int mii, int maxii, int *nodes_order)
2142 int i, c, success, num_splits = 0;
2143 int flush_and_start_over = true;
2144 int num_nodes = g->num_nodes;
2145 int start, end, step; /* Place together into one struct? */
2146 sbitmap sched_nodes = sbitmap_alloc (num_nodes);
2147 sbitmap must_precede = sbitmap_alloc (num_nodes);
2148 sbitmap must_follow = sbitmap_alloc (num_nodes);
2149 sbitmap tobe_scheduled = sbitmap_alloc (num_nodes);
2151 partial_schedule_ptr ps = create_partial_schedule (ii, g, DFA_HISTORY);
2153 sbitmap_ones (tobe_scheduled);
2154 sbitmap_zero (sched_nodes);
2156 while (flush_and_start_over && (ii < maxii))
2160 fprintf (dump_file, "Starting with ii=%d\n", ii);
2161 flush_and_start_over = false;
2162 sbitmap_zero (sched_nodes);
2164 for (i = 0; i < num_nodes; i++)
2166 int u = nodes_order[i];
2167 ddg_node_ptr u_node = &ps->g->nodes[u];
2168 rtx insn = u_node->insn;
2170 if (!NONDEBUG_INSN_P (insn))
2172 RESET_BIT (tobe_scheduled, u);
2176 if (TEST_BIT (sched_nodes, u))
2179 /* Try to get non-empty scheduling window. */
2181 if (get_sched_window (ps, u_node, sched_nodes, ii, &start,
2185 fprintf (dump_file, "\nTrying to schedule node %d "
2186 "INSN = %d in (%d .. %d) step %d\n", u, (INSN_UID
2187 (g->nodes[u].insn)), start, end, step);
2189 gcc_assert ((step > 0 && start < end)
2190 || (step < 0 && start > end));
2192 calculate_must_precede_follow (u_node, start, end, step, ii,
2193 sched_nodes, must_precede,
2196 for (c = start; c != end; c += step)
2198 sbitmap tmp_precede, tmp_follow;
2200 set_must_precede_follow (&tmp_follow, must_follow,
2201 &tmp_precede, must_precede,
2202 c, start, end, step);
2204 try_scheduling_node_in_cycle (ps, u, c,
2206 &num_splits, tmp_precede,
2212 verify_partial_schedule (ps, sched_nodes);
2221 if (num_splits >= MAX_SPLIT_NUM)
2224 flush_and_start_over = true;
2225 verify_partial_schedule (ps, sched_nodes);
2226 reset_partial_schedule (ps, ii);
2227 verify_partial_schedule (ps, sched_nodes);
2232 /* The scheduling window is exclusive of 'end'
2233 whereas compute_split_window() expects an inclusive,
2236 split_row = compute_split_row (sched_nodes, start, end - 1,
2239 split_row = compute_split_row (sched_nodes, end + 1, start,
2242 ps_insert_empty_row (ps, split_row, sched_nodes);
2243 i--; /* Go back and retry node i. */
2246 fprintf (dump_file, "num_splits=%d\n", num_splits);
2249 /* ??? If (success), check register pressure estimates. */
2250 } /* Continue with next node. */
2251 } /* While flush_and_start_over. */
2254 free_partial_schedule (ps);
2258 gcc_assert (sbitmap_equal (tobe_scheduled, sched_nodes));
2260 sbitmap_free (sched_nodes);
2261 sbitmap_free (must_precede);
2262 sbitmap_free (must_follow);
2263 sbitmap_free (tobe_scheduled);
2268 /* This function inserts a new empty row into PS at the position
2269 according to SPLITROW, keeping all already scheduled instructions
2270 intact and updating their SCHED_TIME and cycle accordingly. */
2272 ps_insert_empty_row (partial_schedule_ptr ps, int split_row,
2273 sbitmap sched_nodes)
2275 ps_insn_ptr crr_insn;
2276 ps_insn_ptr *rows_new;
2278 int new_ii = ii + 1;
2280 int *rows_length_new;
2282 verify_partial_schedule (ps, sched_nodes);
2284 /* We normalize sched_time and rotate ps to have only non-negative sched
2285 times, for simplicity of updating cycles after inserting new row. */
2286 split_row -= ps->min_cycle;
2287 split_row = SMODULO (split_row, ii);
2289 fprintf (dump_file, "split_row=%d\n", split_row);
2291 reset_sched_times (ps, PS_MIN_CYCLE (ps));
2292 rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
2294 rows_new = (ps_insn_ptr *) xcalloc (new_ii, sizeof (ps_insn_ptr));
2295 rows_length_new = (int *) xcalloc (new_ii, sizeof (int));
2296 for (row = 0; row < split_row; row++)
2298 rows_new[row] = ps->rows[row];
2299 rows_length_new[row] = ps->rows_length[row];
2300 ps->rows[row] = NULL;
2301 for (crr_insn = rows_new[row];
2302 crr_insn; crr_insn = crr_insn->next_in_row)
2304 int u = crr_insn->id;
2305 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii);
2307 SCHED_TIME (u) = new_time;
2308 crr_insn->cycle = new_time;
2309 SCHED_ROW (u) = new_time % new_ii;
2310 SCHED_STAGE (u) = new_time / new_ii;
2315 rows_new[split_row] = NULL;
2317 for (row = split_row; row < ii; row++)
2319 rows_new[row + 1] = ps->rows[row];
2320 rows_length_new[row + 1] = ps->rows_length[row];
2321 ps->rows[row] = NULL;
2322 for (crr_insn = rows_new[row + 1];
2323 crr_insn; crr_insn = crr_insn->next_in_row)
2325 int u = crr_insn->id;
2326 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii) + 1;
2328 SCHED_TIME (u) = new_time;
2329 crr_insn->cycle = new_time;
2330 SCHED_ROW (u) = new_time % new_ii;
2331 SCHED_STAGE (u) = new_time / new_ii;
2336 ps->min_cycle = ps->min_cycle + ps->min_cycle / ii
2337 + (SMODULO (ps->min_cycle, ii) >= split_row ? 1 : 0);
2338 ps->max_cycle = ps->max_cycle + ps->max_cycle / ii
2339 + (SMODULO (ps->max_cycle, ii) >= split_row ? 1 : 0);
2341 ps->rows = rows_new;
2342 free (ps->rows_length);
2343 ps->rows_length = rows_length_new;
2345 gcc_assert (ps->min_cycle >= 0);
2347 verify_partial_schedule (ps, sched_nodes);
2350 fprintf (dump_file, "min_cycle=%d, max_cycle=%d\n", ps->min_cycle,
2354 /* Given U_NODE which is the node that failed to be scheduled; LOW and
2355 UP which are the boundaries of it's scheduling window; compute using
2356 SCHED_NODES and II a row in the partial schedule that can be split
2357 which will separate a critical predecessor from a critical successor
2358 thereby expanding the window, and return it. */
2360 compute_split_row (sbitmap sched_nodes, int low, int up, int ii,
2361 ddg_node_ptr u_node)
2364 int lower = INT_MIN, upper = INT_MAX;
2369 for (e = u_node->in; e != 0; e = e->next_in)
2371 int v = e->src->cuid;
2373 if (TEST_BIT (sched_nodes, v)
2374 && (low == SCHED_TIME (v) + e->latency - (e->distance * ii)))
2375 if (SCHED_TIME (v) > lower)
2378 lower = SCHED_TIME (v);
2384 crit_cycle = SCHED_TIME (crit_pred) + 1;
2385 return SMODULO (crit_cycle, ii);
2388 for (e = u_node->out; e != 0; e = e->next_out)
2390 int v = e->dest->cuid;
2392 if (TEST_BIT (sched_nodes, v)
2393 && (up == SCHED_TIME (v) - e->latency + (e->distance * ii)))
2394 if (SCHED_TIME (v) < upper)
2397 upper = SCHED_TIME (v);
2403 crit_cycle = SCHED_TIME (crit_succ);
2404 return SMODULO (crit_cycle, ii);
2408 fprintf (dump_file, "Both crit_pred and crit_succ are NULL\n");
2410 return SMODULO ((low + up + 1) / 2, ii);
2414 verify_partial_schedule (partial_schedule_ptr ps, sbitmap sched_nodes)
2417 ps_insn_ptr crr_insn;
2419 for (row = 0; row < ps->ii; row++)
2423 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
2425 int u = crr_insn->id;
2428 gcc_assert (TEST_BIT (sched_nodes, u));
2429 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2430 popcount (sched_nodes) == number of insns in ps. */
2431 gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
2432 gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
2435 gcc_assert (ps->rows_length[row] == length);
2440 /* This page implements the algorithm for ordering the nodes of a DDG
2441 for modulo scheduling, activated through the
2442 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2444 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2445 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
2446 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
2447 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2448 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
2449 #define DEPTH(x) (ASAP ((x)))
2451 typedef struct node_order_params * nopa;
2453 static void order_nodes_of_sccs (ddg_all_sccs_ptr, int * result);
2454 static int order_nodes_in_scc (ddg_ptr, sbitmap, sbitmap, int*, int);
2455 static nopa calculate_order_params (ddg_ptr, int, int *);
2456 static int find_max_asap (ddg_ptr, sbitmap);
2457 static int find_max_hv_min_mob (ddg_ptr, sbitmap);
2458 static int find_max_dv_min_mob (ddg_ptr, sbitmap);
2460 enum sms_direction {BOTTOMUP, TOPDOWN};
2462 struct node_order_params
2469 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2471 check_nodes_order (int *node_order, int num_nodes)
2474 sbitmap tmp = sbitmap_alloc (num_nodes);
2479 fprintf (dump_file, "SMS final nodes order: \n");
2481 for (i = 0; i < num_nodes; i++)
2483 int u = node_order[i];
2486 fprintf (dump_file, "%d ", u);
2487 gcc_assert (u < num_nodes && u >= 0 && !TEST_BIT (tmp, u));
2493 fprintf (dump_file, "\n");
2498 /* Order the nodes of G for scheduling and pass the result in
2499 NODE_ORDER. Also set aux.count of each node to ASAP.
2500 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2502 sms_order_nodes (ddg_ptr g, int mii, int * node_order, int *pmax_asap)
2506 ddg_all_sccs_ptr sccs = create_ddg_all_sccs (g);
2508 nopa nops = calculate_order_params (g, mii, pmax_asap);
2511 print_sccs (dump_file, sccs, g);
2513 order_nodes_of_sccs (sccs, node_order);
2515 if (sccs->num_sccs > 0)
2516 /* First SCC has the largest recurrence_length. */
2517 rec_mii = sccs->sccs[0]->recurrence_length;
2519 /* Save ASAP before destroying node_order_params. */
2520 for (i = 0; i < g->num_nodes; i++)
2522 ddg_node_ptr v = &g->nodes[i];
2523 v->aux.count = ASAP (v);
2527 free_ddg_all_sccs (sccs);
2528 check_nodes_order (node_order, g->num_nodes);
2534 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs, int * node_order)
2537 ddg_ptr g = all_sccs->ddg;
2538 int num_nodes = g->num_nodes;
2539 sbitmap prev_sccs = sbitmap_alloc (num_nodes);
2540 sbitmap on_path = sbitmap_alloc (num_nodes);
2541 sbitmap tmp = sbitmap_alloc (num_nodes);
2542 sbitmap ones = sbitmap_alloc (num_nodes);
2544 sbitmap_zero (prev_sccs);
2545 sbitmap_ones (ones);
2547 /* Perform the node ordering starting from the SCC with the highest recMII.
2548 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2549 for (i = 0; i < all_sccs->num_sccs; i++)
2551 ddg_scc_ptr scc = all_sccs->sccs[i];
2553 /* Add nodes on paths from previous SCCs to the current SCC. */
2554 find_nodes_on_paths (on_path, g, prev_sccs, scc->nodes);
2555 sbitmap_a_or_b (tmp, scc->nodes, on_path);
2557 /* Add nodes on paths from the current SCC to previous SCCs. */
2558 find_nodes_on_paths (on_path, g, scc->nodes, prev_sccs);
2559 sbitmap_a_or_b (tmp, tmp, on_path);
2561 /* Remove nodes of previous SCCs from current extended SCC. */
2562 sbitmap_difference (tmp, tmp, prev_sccs);
2564 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
2565 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2568 /* Handle the remaining nodes that do not belong to any scc. Each call
2569 to order_nodes_in_scc handles a single connected component. */
2570 while (pos < g->num_nodes)
2572 sbitmap_difference (tmp, ones, prev_sccs);
2573 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
2575 sbitmap_free (prev_sccs);
2576 sbitmap_free (on_path);
2578 sbitmap_free (ones);
2581 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2582 static struct node_order_params *
2583 calculate_order_params (ddg_ptr g, int mii ATTRIBUTE_UNUSED, int *pmax_asap)
2587 int num_nodes = g->num_nodes;
2589 /* Allocate a place to hold ordering params for each node in the DDG. */
2590 nopa node_order_params_arr;
2592 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2593 node_order_params_arr = (nopa) xcalloc (num_nodes,
2594 sizeof (struct node_order_params));
2596 /* Set the aux pointer of each node to point to its order_params structure. */
2597 for (u = 0; u < num_nodes; u++)
2598 g->nodes[u].aux.info = &node_order_params_arr[u];
2600 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2601 calculate ASAP, ALAP, mobility, distance, and height for each node
2602 in the dependence (direct acyclic) graph. */
2604 /* We assume that the nodes in the array are in topological order. */
2607 for (u = 0; u < num_nodes; u++)
2609 ddg_node_ptr u_node = &g->nodes[u];
2612 for (e = u_node->in; e; e = e->next_in)
2613 if (e->distance == 0)
2614 ASAP (u_node) = MAX (ASAP (u_node),
2615 ASAP (e->src) + e->latency);
2616 max_asap = MAX (max_asap, ASAP (u_node));
2619 for (u = num_nodes - 1; u > -1; u--)
2621 ddg_node_ptr u_node = &g->nodes[u];
2623 ALAP (u_node) = max_asap;
2624 HEIGHT (u_node) = 0;
2625 for (e = u_node->out; e; e = e->next_out)
2626 if (e->distance == 0)
2628 ALAP (u_node) = MIN (ALAP (u_node),
2629 ALAP (e->dest) - e->latency);
2630 HEIGHT (u_node) = MAX (HEIGHT (u_node),
2631 HEIGHT (e->dest) + e->latency);
2636 fprintf (dump_file, "\nOrder params\n");
2637 for (u = 0; u < num_nodes; u++)
2639 ddg_node_ptr u_node = &g->nodes[u];
2641 fprintf (dump_file, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u,
2642 ASAP (u_node), ALAP (u_node), HEIGHT (u_node));
2646 *pmax_asap = max_asap;
2647 return node_order_params_arr;
2651 find_max_asap (ddg_ptr g, sbitmap nodes)
2656 sbitmap_iterator sbi;
2658 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
2660 ddg_node_ptr u_node = &g->nodes[u];
2662 if (max_asap < ASAP (u_node))
2664 max_asap = ASAP (u_node);
2672 find_max_hv_min_mob (ddg_ptr g, sbitmap nodes)
2676 int min_mob = INT_MAX;
2678 sbitmap_iterator sbi;
2680 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
2682 ddg_node_ptr u_node = &g->nodes[u];
2684 if (max_hv < HEIGHT (u_node))
2686 max_hv = HEIGHT (u_node);
2687 min_mob = MOB (u_node);
2690 else if ((max_hv == HEIGHT (u_node))
2691 && (min_mob > MOB (u_node)))
2693 min_mob = MOB (u_node);
2701 find_max_dv_min_mob (ddg_ptr g, sbitmap nodes)
2705 int min_mob = INT_MAX;
2707 sbitmap_iterator sbi;
2709 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
2711 ddg_node_ptr u_node = &g->nodes[u];
2713 if (max_dv < DEPTH (u_node))
2715 max_dv = DEPTH (u_node);
2716 min_mob = MOB (u_node);
2719 else if ((max_dv == DEPTH (u_node))
2720 && (min_mob > MOB (u_node)))
2722 min_mob = MOB (u_node);
2729 /* Places the nodes of SCC into the NODE_ORDER array starting
2730 at position POS, according to the SMS ordering algorithm.
2731 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2732 the NODE_ORDER array, starting from position zero. */
2734 order_nodes_in_scc (ddg_ptr g, sbitmap nodes_ordered, sbitmap scc,
2735 int * node_order, int pos)
2737 enum sms_direction dir;
2738 int num_nodes = g->num_nodes;
2739 sbitmap workset = sbitmap_alloc (num_nodes);
2740 sbitmap tmp = sbitmap_alloc (num_nodes);
2741 sbitmap zero_bitmap = sbitmap_alloc (num_nodes);
2742 sbitmap predecessors = sbitmap_alloc (num_nodes);
2743 sbitmap successors = sbitmap_alloc (num_nodes);
2745 sbitmap_zero (predecessors);
2746 find_predecessors (predecessors, g, nodes_ordered);
2748 sbitmap_zero (successors);
2749 find_successors (successors, g, nodes_ordered);
2752 if (sbitmap_a_and_b_cg (tmp, predecessors, scc))
2754 sbitmap_copy (workset, tmp);
2757 else if (sbitmap_a_and_b_cg (tmp, successors, scc))
2759 sbitmap_copy (workset, tmp);
2766 sbitmap_zero (workset);
2767 if ((u = find_max_asap (g, scc)) >= 0)
2768 SET_BIT (workset, u);
2772 sbitmap_zero (zero_bitmap);
2773 while (!sbitmap_equal (workset, zero_bitmap))
2776 ddg_node_ptr v_node;
2777 sbitmap v_node_preds;
2778 sbitmap v_node_succs;
2782 while (!sbitmap_equal (workset, zero_bitmap))
2784 v = find_max_hv_min_mob (g, workset);
2785 v_node = &g->nodes[v];
2786 node_order[pos++] = v;
2787 v_node_succs = NODE_SUCCESSORS (v_node);
2788 sbitmap_a_and_b (tmp, v_node_succs, scc);
2790 /* Don't consider the already ordered successors again. */
2791 sbitmap_difference (tmp, tmp, nodes_ordered);
2792 sbitmap_a_or_b (workset, workset, tmp);
2793 RESET_BIT (workset, v);
2794 SET_BIT (nodes_ordered, v);
2797 sbitmap_zero (predecessors);
2798 find_predecessors (predecessors, g, nodes_ordered);
2799 sbitmap_a_and_b (workset, predecessors, scc);
2803 while (!sbitmap_equal (workset, zero_bitmap))
2805 v = find_max_dv_min_mob (g, workset);
2806 v_node = &g->nodes[v];
2807 node_order[pos++] = v;
2808 v_node_preds = NODE_PREDECESSORS (v_node);
2809 sbitmap_a_and_b (tmp, v_node_preds, scc);
2811 /* Don't consider the already ordered predecessors again. */
2812 sbitmap_difference (tmp, tmp, nodes_ordered);
2813 sbitmap_a_or_b (workset, workset, tmp);
2814 RESET_BIT (workset, v);
2815 SET_BIT (nodes_ordered, v);
2818 sbitmap_zero (successors);
2819 find_successors (successors, g, nodes_ordered);
2820 sbitmap_a_and_b (workset, successors, scc);
2824 sbitmap_free (workset);
2825 sbitmap_free (zero_bitmap);
2826 sbitmap_free (predecessors);
2827 sbitmap_free (successors);
2832 /* This page contains functions for manipulating partial-schedules during
2833 modulo scheduling. */
2835 /* Create a partial schedule and allocate a memory to hold II rows. */
2837 static partial_schedule_ptr
2838 create_partial_schedule (int ii, ddg_ptr g, int history)
2840 partial_schedule_ptr ps = XNEW (struct partial_schedule);
2841 ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
2842 ps->rows_length = (int *) xcalloc (ii, sizeof (int));
2843 ps->reg_moves = NULL;
2845 ps->history = history;
2846 ps->min_cycle = INT_MAX;
2847 ps->max_cycle = INT_MIN;
2853 /* Free the PS_INSNs in rows array of the given partial schedule.
2854 ??? Consider caching the PS_INSN's. */
2856 free_ps_insns (partial_schedule_ptr ps)
2860 for (i = 0; i < ps->ii; i++)
2864 ps_insn_ptr ps_insn = ps->rows[i]->next_in_row;
2867 ps->rows[i] = ps_insn;
2873 /* Free all the memory allocated to the partial schedule. */
2876 free_partial_schedule (partial_schedule_ptr ps)
2878 ps_reg_move_info *move;
2884 FOR_EACH_VEC_ELT (ps_reg_move_info, ps->reg_moves, i, move)
2885 sbitmap_free (move->uses);
2886 VEC_free (ps_reg_move_info, heap, ps->reg_moves);
2890 free (ps->rows_length);
2894 /* Clear the rows array with its PS_INSNs, and create a new one with
2898 reset_partial_schedule (partial_schedule_ptr ps, int new_ii)
2903 if (new_ii == ps->ii)
2905 ps->rows = (ps_insn_ptr *) xrealloc (ps->rows, new_ii
2906 * sizeof (ps_insn_ptr));
2907 memset (ps->rows, 0, new_ii * sizeof (ps_insn_ptr));
2908 ps->rows_length = (int *) xrealloc (ps->rows_length, new_ii * sizeof (int));
2909 memset (ps->rows_length, 0, new_ii * sizeof (int));
2911 ps->min_cycle = INT_MAX;
2912 ps->max_cycle = INT_MIN;
2915 /* Prints the partial schedule as an ii rows array, for each rows
2916 print the ids of the insns in it. */
2918 print_partial_schedule (partial_schedule_ptr ps, FILE *dump)
2922 for (i = 0; i < ps->ii; i++)
2924 ps_insn_ptr ps_i = ps->rows[i];
2926 fprintf (dump, "\n[ROW %d ]: ", i);
2929 rtx insn = ps_rtl_insn (ps, ps_i->id);
2932 fprintf (dump, "%d (branch), ", INSN_UID (insn));
2934 fprintf (dump, "%d, ", INSN_UID (insn));
2936 ps_i = ps_i->next_in_row;
2941 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2943 create_ps_insn (int id, int cycle)
2945 ps_insn_ptr ps_i = XNEW (struct ps_insn);
2948 ps_i->next_in_row = NULL;
2949 ps_i->prev_in_row = NULL;
2950 ps_i->cycle = cycle;
2956 /* Removes the given PS_INSN from the partial schedule. */
2958 remove_node_from_ps (partial_schedule_ptr ps, ps_insn_ptr ps_i)
2962 gcc_assert (ps && ps_i);
2964 row = SMODULO (ps_i->cycle, ps->ii);
2965 if (! ps_i->prev_in_row)
2967 gcc_assert (ps_i == ps->rows[row]);
2968 ps->rows[row] = ps_i->next_in_row;
2970 ps->rows[row]->prev_in_row = NULL;
2974 ps_i->prev_in_row->next_in_row = ps_i->next_in_row;
2975 if (ps_i->next_in_row)
2976 ps_i->next_in_row->prev_in_row = ps_i->prev_in_row;
2979 ps->rows_length[row] -= 1;
2984 /* Unlike what literature describes for modulo scheduling (which focuses
2985 on VLIW machines) the order of the instructions inside a cycle is
2986 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2987 where the current instruction should go relative to the already
2988 scheduled instructions in the given cycle. Go over these
2989 instructions and find the first possible column to put it in. */
2991 ps_insn_find_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
2992 sbitmap must_precede, sbitmap must_follow)
2994 ps_insn_ptr next_ps_i;
2995 ps_insn_ptr first_must_follow = NULL;
2996 ps_insn_ptr last_must_precede = NULL;
2997 ps_insn_ptr last_in_row = NULL;
3003 row = SMODULO (ps_i->cycle, ps->ii);
3005 /* Find the first must follow and the last must precede
3006 and insert the node immediately after the must precede
3007 but make sure that it there is no must follow after it. */
3008 for (next_ps_i = ps->rows[row];
3010 next_ps_i = next_ps_i->next_in_row)
3013 && TEST_BIT (must_follow, next_ps_i->id)
3014 && ! first_must_follow)
3015 first_must_follow = next_ps_i;
3016 if (must_precede && TEST_BIT (must_precede, next_ps_i->id))
3018 /* If we have already met a node that must follow, then
3019 there is no possible column. */
3020 if (first_must_follow)
3023 last_must_precede = next_ps_i;
3025 /* The closing branch must be the last in the row. */
3027 && TEST_BIT (must_precede, next_ps_i->id)
3028 && JUMP_P (ps_rtl_insn (ps, next_ps_i->id)))
3031 last_in_row = next_ps_i;
3034 /* The closing branch is scheduled as well. Make sure there is no
3035 dependent instruction after it as the branch should be the last
3036 instruction in the row. */
3037 if (JUMP_P (ps_rtl_insn (ps, ps_i->id)))
3039 if (first_must_follow)
3043 /* Make the branch the last in the row. New instructions
3044 will be inserted at the beginning of the row or after the
3045 last must_precede instruction thus the branch is guaranteed
3046 to remain the last instruction in the row. */
3047 last_in_row->next_in_row = ps_i;
3048 ps_i->prev_in_row = last_in_row;
3049 ps_i->next_in_row = NULL;
3052 ps->rows[row] = ps_i;
3056 /* Now insert the node after INSERT_AFTER_PSI. */
3058 if (! last_must_precede)
3060 ps_i->next_in_row = ps->rows[row];
3061 ps_i->prev_in_row = NULL;
3062 if (ps_i->next_in_row)
3063 ps_i->next_in_row->prev_in_row = ps_i;
3064 ps->rows[row] = ps_i;
3068 ps_i->next_in_row = last_must_precede->next_in_row;
3069 last_must_precede->next_in_row = ps_i;
3070 ps_i->prev_in_row = last_must_precede;
3071 if (ps_i->next_in_row)
3072 ps_i->next_in_row->prev_in_row = ps_i;
3078 /* Advances the PS_INSN one column in its current row; returns false
3079 in failure and true in success. Bit N is set in MUST_FOLLOW if
3080 the node with cuid N must be come after the node pointed to by
3081 PS_I when scheduled in the same cycle. */
3083 ps_insn_advance_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
3084 sbitmap must_follow)
3086 ps_insn_ptr prev, next;
3092 row = SMODULO (ps_i->cycle, ps->ii);
3094 if (! ps_i->next_in_row)
3097 /* Check if next_in_row is dependent on ps_i, both having same sched
3098 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
3099 if (must_follow && TEST_BIT (must_follow, ps_i->next_in_row->id))
3102 /* Advance PS_I over its next_in_row in the doubly linked list. */
3103 prev = ps_i->prev_in_row;
3104 next = ps_i->next_in_row;
3106 if (ps_i == ps->rows[row])
3107 ps->rows[row] = next;
3109 ps_i->next_in_row = next->next_in_row;
3111 if (next->next_in_row)
3112 next->next_in_row->prev_in_row = ps_i;
3114 next->next_in_row = ps_i;
3115 ps_i->prev_in_row = next;
3117 next->prev_in_row = prev;
3119 prev->next_in_row = next;
3124 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
3125 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
3126 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
3127 before/after (respectively) the node pointed to by PS_I when scheduled
3128 in the same cycle. */
3130 add_node_to_ps (partial_schedule_ptr ps, int id, int cycle,
3131 sbitmap must_precede, sbitmap must_follow)
3134 int row = SMODULO (cycle, ps->ii);
3136 if (ps->rows_length[row] >= issue_rate)
3139 ps_i = create_ps_insn (id, cycle);
3141 /* Finds and inserts PS_I according to MUST_FOLLOW and
3143 if (! ps_insn_find_column (ps, ps_i, must_precede, must_follow))
3149 ps->rows_length[row] += 1;
3153 /* Advance time one cycle. Assumes DFA is being used. */
3155 advance_one_cycle (void)
3157 if (targetm.sched.dfa_pre_cycle_insn)
3158 state_transition (curr_state,
3159 targetm.sched.dfa_pre_cycle_insn ());
3161 state_transition (curr_state, NULL);
3163 if (targetm.sched.dfa_post_cycle_insn)
3164 state_transition (curr_state,
3165 targetm.sched.dfa_post_cycle_insn ());
3170 /* Checks if PS has resource conflicts according to DFA, starting from
3171 FROM cycle to TO cycle; returns true if there are conflicts and false
3172 if there are no conflicts. Assumes DFA is being used. */
3174 ps_has_conflicts (partial_schedule_ptr ps, int from, int to)
3178 state_reset (curr_state);
3180 for (cycle = from; cycle <= to; cycle++)
3182 ps_insn_ptr crr_insn;
3183 /* Holds the remaining issue slots in the current row. */
3184 int can_issue_more = issue_rate;
3186 /* Walk through the DFA for the current row. */
3187 for (crr_insn = ps->rows[SMODULO (cycle, ps->ii)];
3189 crr_insn = crr_insn->next_in_row)
3191 rtx insn = ps_rtl_insn (ps, crr_insn->id);
3193 if (!NONDEBUG_INSN_P (insn))
3196 /* Check if there is room for the current insn. */
3197 if (!can_issue_more || state_dead_lock_p (curr_state))
3200 /* Update the DFA state and return with failure if the DFA found
3201 resource conflicts. */
3202 if (state_transition (curr_state, insn) >= 0)
3205 if (targetm.sched.variable_issue)
3207 targetm.sched.variable_issue (sched_dump, sched_verbose,
3208 insn, can_issue_more);
3209 /* A naked CLOBBER or USE generates no instruction, so don't
3210 let them consume issue slots. */
3211 else if (GET_CODE (PATTERN (insn)) != USE
3212 && GET_CODE (PATTERN (insn)) != CLOBBER)
3216 /* Advance the DFA to the next cycle. */
3217 advance_one_cycle ();
3222 /* Checks if the given node causes resource conflicts when added to PS at
3223 cycle C. If not the node is added to PS and returned; otherwise zero
3224 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
3225 cuid N must be come before/after (respectively) the node pointed to by
3226 PS_I when scheduled in the same cycle. */
3228 ps_add_node_check_conflicts (partial_schedule_ptr ps, int n,
3229 int c, sbitmap must_precede,
3230 sbitmap must_follow)
3232 int has_conflicts = 0;
3235 /* First add the node to the PS, if this succeeds check for
3236 conflicts, trying different issue slots in the same row. */
3237 if (! (ps_i = add_node_to_ps (ps, n, c, must_precede, must_follow)))
3238 return NULL; /* Failed to insert the node at the given cycle. */
3240 has_conflicts = ps_has_conflicts (ps, c, c)
3242 && ps_has_conflicts (ps,
3246 /* Try different issue slots to find one that the given node can be
3247 scheduled in without conflicts. */
3248 while (has_conflicts)
3250 if (! ps_insn_advance_column (ps, ps_i, must_follow))
3252 has_conflicts = ps_has_conflicts (ps, c, c)
3254 && ps_has_conflicts (ps,
3261 remove_node_from_ps (ps, ps_i);
3265 ps->min_cycle = MIN (ps->min_cycle, c);
3266 ps->max_cycle = MAX (ps->max_cycle, c);
3270 /* Calculate the stage count of the partial schedule PS. The calculation
3271 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3273 calculate_stage_count (partial_schedule_ptr ps, int rotation_amount)
3275 int new_min_cycle = PS_MIN_CYCLE (ps) - rotation_amount;
3276 int new_max_cycle = PS_MAX_CYCLE (ps) - rotation_amount;
3277 int stage_count = CALC_STAGE_COUNT (-1, new_min_cycle, ps->ii);
3279 /* The calculation of stage count is done adding the number of stages
3280 before cycle zero and after cycle zero. */
3281 stage_count += CALC_STAGE_COUNT (new_max_cycle, 0, ps->ii);
3286 /* Rotate the rows of PS such that insns scheduled at time
3287 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3289 rotate_partial_schedule (partial_schedule_ptr ps, int start_cycle)
3291 int i, row, backward_rotates;
3292 int last_row = ps->ii - 1;
3294 if (start_cycle == 0)
3297 backward_rotates = SMODULO (start_cycle, ps->ii);
3299 /* Revisit later and optimize this into a single loop. */
3300 for (i = 0; i < backward_rotates; i++)
3302 ps_insn_ptr first_row = ps->rows[0];
3303 int first_row_length = ps->rows_length[0];
3305 for (row = 0; row < last_row; row++)
3307 ps->rows[row] = ps->rows[row + 1];
3308 ps->rows_length[row] = ps->rows_length[row + 1];
3311 ps->rows[last_row] = first_row;
3312 ps->rows_length[last_row] = first_row_length;
3315 ps->max_cycle -= start_cycle;
3316 ps->min_cycle -= start_cycle;
3319 #endif /* INSN_SCHEDULING */
3322 gate_handle_sms (void)
3324 return (optimize > 0 && flag_modulo_sched);
3328 /* Run instruction scheduler. */
3329 /* Perform SMS module scheduling. */
3331 rest_of_handle_sms (void)
3333 #ifdef INSN_SCHEDULING
3336 /* Collect loop information to be used in SMS. */
3337 cfg_layout_initialize (0);
3340 /* Update the life information, because we add pseudos. */
3341 max_regno = max_reg_num ();
3343 /* Finalize layout changes. */
3345 if (bb->next_bb != EXIT_BLOCK_PTR)
3346 bb->aux = bb->next_bb;
3347 free_dominance_info (CDI_DOMINATORS);
3348 cfg_layout_finalize ();
3349 #endif /* INSN_SCHEDULING */
3353 struct rtl_opt_pass pass_sms =
3358 gate_handle_sms, /* gate */
3359 rest_of_handle_sms, /* execute */
3362 0, /* static_pass_number */
3364 0, /* properties_required */
3365 0, /* properties_provided */
3366 0, /* properties_destroyed */
3367 0, /* todo_flags_start */
3370 | TODO_verify_rtl_sharing
3371 | TODO_ggc_collect /* todo_flags_finish */