1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004-2015 Free Software Foundation, Inc.
3 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
26 #include "diagnostic-core.h"
29 #include "hard-reg-set.h"
39 #include "insn-config.h"
40 #include "insn-attr.h"
43 #include "dominance.h"
47 #include "basic-block.h"
48 #include "sched-int.h"
51 #include "double-int.h"
57 #include "insn-codes.h"
59 #include "statistics.h"
61 #include "fixed-value.h"
75 #include "tree-pass.h"
77 #include "loop-unroll.h"
79 #ifdef INSN_SCHEDULING
81 /* This file contains the implementation of the Swing Modulo Scheduler,
82 described in the following references:
83 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
84 Lifetime--sensitive modulo scheduling in a production environment.
85 IEEE Trans. on Comps., 50(3), March 2001
86 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
87 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
88 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
90 The basic structure is:
91 1. Build a data-dependence graph (DDG) for each loop.
92 2. Use the DDG to order the insns of a loop (not in topological order
93 necessarily, but rather) trying to place each insn after all its
94 predecessors _or_ after all its successors.
95 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
96 4. Use the ordering to perform list-scheduling of the loop:
97 1. Set II = MII. We will try to schedule the loop within II cycles.
98 2. Try to schedule the insns one by one according to the ordering.
99 For each insn compute an interval of cycles by considering already-
100 scheduled preds and succs (and associated latencies); try to place
101 the insn in the cycles of this window checking for potential
102 resource conflicts (using the DFA interface).
103 Note: this is different from the cycle-scheduling of schedule_insns;
104 here the insns are not scheduled monotonically top-down (nor bottom-
106 3. If failed in scheduling all insns - bump II++ and try again, unless
107 II reaches an upper bound MaxII, in which case report failure.
108 5. If we succeeded in scheduling the loop within II cycles, we now
109 generate prolog and epilog, decrease the counter of the loop, and
110 perform modulo variable expansion for live ranges that span more than
111 II cycles (i.e. use register copies to prevent a def from overwriting
112 itself before reaching the use).
114 SMS works with countable loops (1) whose control part can be easily
115 decoupled from the rest of the loop and (2) whose loop count can
116 be easily adjusted. This is because we peel a constant number of
117 iterations into a prologue and epilogue for which we want to avoid
118 emitting the control part, and a kernel which is to iterate that
119 constant number of iterations less than the original loop. So the
120 control part should be a set of insns clearly identified and having
121 its own iv, not otherwise used in the loop (at-least for now), which
122 initializes a register before the loop to the number of iterations.
123 Currently SMS relies on the do-loop pattern to recognize such loops,
124 where (1) the control part comprises of all insns defining and/or
125 using a certain 'count' register and (2) the loop count can be
126 adjusted by modifying this register prior to the loop.
127 TODO: Rely on cfgloop analysis instead. */
129 /* This page defines partial-schedule structures and functions for
130 modulo scheduling. */
132 typedef struct partial_schedule *partial_schedule_ptr;
133 typedef struct ps_insn *ps_insn_ptr;
135 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
136 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
138 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
139 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
141 /* Perform signed modulo, always returning a non-negative value. */
142 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
144 /* The number of different iterations the nodes in ps span, assuming
145 the stage boundaries are placed efficiently. */
146 #define CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \
148 /* The stage count of ps. */
149 #define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count)
151 /* A single instruction in the partial schedule. */
154 /* Identifies the instruction to be scheduled. Values smaller than
155 the ddg's num_nodes refer directly to ddg nodes. A value of
156 X - num_nodes refers to register move X. */
159 /* The (absolute) cycle in which the PS instruction is scheduled.
160 Same as SCHED_TIME (node). */
163 /* The next/prev PS_INSN in the same row. */
164 ps_insn_ptr next_in_row,
169 /* Information about a register move that has been added to a partial
171 struct ps_reg_move_info
173 /* The source of the move is defined by the ps_insn with id DEF.
174 The destination is used by the ps_insns with the ids in USES. */
178 /* The original form of USES' instructions used OLD_REG, but they
179 should now use NEW_REG. */
183 /* The number of consecutive stages that the move occupies. */
184 int num_consecutive_stages;
186 /* An instruction that sets NEW_REG to the correct value. The first
187 move associated with DEF will have an rhs of OLD_REG; later moves
188 use the result of the previous move. */
192 typedef struct ps_reg_move_info ps_reg_move_info;
194 /* Holds the partial schedule as an array of II rows. Each entry of the
195 array points to a linked list of PS_INSNs, which represents the
196 instructions that are scheduled for that row. */
197 struct partial_schedule
199 int ii; /* Number of rows in the partial schedule. */
200 int history; /* Threshold for conflict checking using DFA. */
202 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
205 /* All the moves added for this partial schedule. Index X has
206 a ps_insn id of X + g->num_nodes. */
207 vec<ps_reg_move_info> reg_moves;
209 /* rows_length[i] holds the number of instructions in the row.
210 It is used only (as an optimization) to back off quickly from
211 trying to schedule a node in a full row; that is, to avoid running
212 through futile DFA state transitions. */
215 /* The earliest absolute cycle of an insn in the partial schedule. */
218 /* The latest absolute cycle of an insn in the partial schedule. */
221 ddg_ptr g; /* The DDG of the insns in the partial schedule. */
223 int stage_count; /* The stage count of the partial schedule. */
227 static partial_schedule_ptr create_partial_schedule (int ii, ddg_ptr, int history);
228 static void free_partial_schedule (partial_schedule_ptr);
229 static void reset_partial_schedule (partial_schedule_ptr, int new_ii);
230 void print_partial_schedule (partial_schedule_ptr, FILE *);
231 static void verify_partial_schedule (partial_schedule_ptr, sbitmap);
232 static ps_insn_ptr ps_add_node_check_conflicts (partial_schedule_ptr,
233 int, int, sbitmap, sbitmap);
234 static void rotate_partial_schedule (partial_schedule_ptr, int);
235 void set_row_column_for_ps (partial_schedule_ptr);
236 static void ps_insert_empty_row (partial_schedule_ptr, int, sbitmap);
237 static int compute_split_row (sbitmap, int, int, int, ddg_node_ptr);
240 /* This page defines constants and structures for the modulo scheduling
243 static int sms_order_nodes (ddg_ptr, int, int *, int *);
244 static void set_node_sched_params (ddg_ptr);
245 static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int, int *);
246 static void permute_partial_schedule (partial_schedule_ptr, rtx_insn *);
247 static void generate_prolog_epilog (partial_schedule_ptr, struct loop *,
249 static int calculate_stage_count (partial_schedule_ptr, int);
250 static void calculate_must_precede_follow (ddg_node_ptr, int, int,
251 int, int, sbitmap, sbitmap, sbitmap);
252 static int get_sched_window (partial_schedule_ptr, ddg_node_ptr,
253 sbitmap, int, int *, int *, int *);
254 static bool try_scheduling_node_in_cycle (partial_schedule_ptr, int, int,
255 sbitmap, int *, sbitmap, sbitmap);
256 static void remove_node_from_ps (partial_schedule_ptr, ps_insn_ptr);
258 #define NODE_ASAP(node) ((node)->aux.count)
260 #define SCHED_PARAMS(x) (&node_sched_param_vec[x])
261 #define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
262 #define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
263 #define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
264 #define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
266 /* The scheduling parameters held for each node. */
267 typedef struct node_sched_params
269 int time; /* The absolute scheduling cycle. */
271 int row; /* Holds time % ii. */
272 int stage; /* Holds time / ii. */
274 /* The column of a node inside the ps. If nodes u, v are on the same row,
275 u will precede v if column (u) < column (v). */
277 } *node_sched_params_ptr;
279 typedef struct node_sched_params node_sched_params;
281 /* The following three functions are copied from the current scheduler
282 code in order to use sched_analyze() for computing the dependencies.
283 They are used when initializing the sched_info structure. */
285 sms_print_insn (const rtx_insn *insn, int aligned ATTRIBUTE_UNUSED)
289 sprintf (tmp, "i%4d", INSN_UID (insn));
294 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
295 regset used ATTRIBUTE_UNUSED)
299 static struct common_sched_info_def sms_common_sched_info;
301 static struct sched_deps_info_def sms_sched_deps_info =
303 compute_jump_reg_dependencies,
304 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
309 static struct haifa_sched_info sms_sched_info =
318 NULL, /* insn_finishes_block_p */
323 NULL, NULL, NULL, NULL,
328 /* Partial schedule instruction ID in PS is a register move. Return
329 information about it. */
330 static struct ps_reg_move_info *
331 ps_reg_move (partial_schedule_ptr ps, int id)
333 gcc_checking_assert (id >= ps->g->num_nodes);
334 return &ps->reg_moves[id - ps->g->num_nodes];
337 /* Return the rtl instruction that is being scheduled by partial schedule
338 instruction ID, which belongs to schedule PS. */
340 ps_rtl_insn (partial_schedule_ptr ps, int id)
342 if (id < ps->g->num_nodes)
343 return ps->g->nodes[id].insn;
345 return ps_reg_move (ps, id)->insn;
348 /* Partial schedule instruction ID, which belongs to PS, occurred in
349 the original (unscheduled) loop. Return the first instruction
350 in the loop that was associated with ps_rtl_insn (PS, ID).
351 If the instruction had some notes before it, this is the first
354 ps_first_note (partial_schedule_ptr ps, int id)
356 gcc_assert (id < ps->g->num_nodes);
357 return ps->g->nodes[id].first_note;
360 /* Return the number of consecutive stages that are occupied by
361 partial schedule instruction ID in PS. */
363 ps_num_consecutive_stages (partial_schedule_ptr ps, int id)
365 if (id < ps->g->num_nodes)
368 return ps_reg_move (ps, id)->num_consecutive_stages;
371 /* Given HEAD and TAIL which are the first and last insns in a loop;
372 return the register which controls the loop. Return zero if it has
373 more than one occurrence in the loop besides the control part or the
374 do-loop pattern is not of the form we expect. */
376 doloop_register_get (rtx_insn *head ATTRIBUTE_UNUSED, rtx_insn *tail ATTRIBUTE_UNUSED)
378 #ifdef HAVE_doloop_end
380 rtx_insn *insn, *first_insn_not_to_check;
385 /* TODO: Free SMS's dependence on doloop_condition_get. */
386 condition = doloop_condition_get (tail);
390 if (REG_P (XEXP (condition, 0)))
391 reg = XEXP (condition, 0);
392 else if (GET_CODE (XEXP (condition, 0)) == PLUS
393 && REG_P (XEXP (XEXP (condition, 0), 0)))
394 reg = XEXP (XEXP (condition, 0), 0);
398 /* Check that the COUNT_REG has no other occurrences in the loop
399 until the decrement. We assume the control part consists of
400 either a single (parallel) branch-on-count or a (non-parallel)
401 branch immediately preceded by a single (decrement) insn. */
402 first_insn_not_to_check = (GET_CODE (PATTERN (tail)) == PARALLEL ? tail
403 : prev_nondebug_insn (tail));
405 for (insn = head; insn != first_insn_not_to_check; insn = NEXT_INSN (insn))
406 if (!DEBUG_INSN_P (insn) && reg_mentioned_p (reg, insn))
410 fprintf (dump_file, "SMS count_reg found ");
411 print_rtl_single (dump_file, reg);
412 fprintf (dump_file, " outside control in insn:\n");
413 print_rtl_single (dump_file, insn);
425 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
426 that the number of iterations is a compile-time constant. If so,
427 return the rtx_insn that sets COUNT_REG to a constant, and set COUNT to
428 this constant. Otherwise return 0. */
430 const_iteration_count (rtx count_reg, basic_block pre_header,
434 rtx_insn *head, *tail;
439 get_ebb_head_tail (pre_header, pre_header, &head, &tail);
441 for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn))
442 if (NONDEBUG_INSN_P (insn) && single_set (insn) &&
443 rtx_equal_p (count_reg, SET_DEST (single_set (insn))))
445 rtx pat = single_set (insn);
447 if (CONST_INT_P (SET_SRC (pat)))
449 *count = INTVAL (SET_SRC (pat));
459 /* A very simple resource-based lower bound on the initiation interval.
460 ??? Improve the accuracy of this bound by considering the
461 utilization of various units. */
465 if (targetm.sched.sms_res_mii)
466 return targetm.sched.sms_res_mii (g);
468 return ((g->num_nodes - g->num_debug) / issue_rate);
472 /* A vector that contains the sched data for each ps_insn. */
473 static vec<node_sched_params> node_sched_param_vec;
475 /* Allocate sched_params for each node and initialize it. */
477 set_node_sched_params (ddg_ptr g)
479 node_sched_param_vec.truncate (0);
480 node_sched_param_vec.safe_grow_cleared (g->num_nodes);
483 /* Make sure that node_sched_param_vec has an entry for every move in PS. */
485 extend_node_sched_params (partial_schedule_ptr ps)
487 node_sched_param_vec.safe_grow_cleared (ps->g->num_nodes
488 + ps->reg_moves.length ());
491 /* Update the sched_params (time, row and stage) for node U using the II,
492 the CYCLE of U and MIN_CYCLE.
493 We're not simply taking the following
494 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
495 because the stages may not be aligned on cycle 0. */
497 update_node_sched_params (int u, int ii, int cycle, int min_cycle)
499 int sc_until_cycle_zero;
502 SCHED_TIME (u) = cycle;
503 SCHED_ROW (u) = SMODULO (cycle, ii);
505 /* The calculation of stage count is done adding the number
506 of stages before cycle zero and after cycle zero. */
507 sc_until_cycle_zero = CALC_STAGE_COUNT (-1, min_cycle, ii);
509 if (SCHED_TIME (u) < 0)
511 stage = CALC_STAGE_COUNT (-1, SCHED_TIME (u), ii);
512 SCHED_STAGE (u) = sc_until_cycle_zero - stage;
516 stage = CALC_STAGE_COUNT (SCHED_TIME (u), 0, ii);
517 SCHED_STAGE (u) = sc_until_cycle_zero + stage - 1;
522 print_node_sched_params (FILE *file, int num_nodes, partial_schedule_ptr ps)
528 for (i = 0; i < num_nodes; i++)
530 node_sched_params_ptr nsp = SCHED_PARAMS (i);
532 fprintf (file, "Node = %d; INSN = %d\n", i,
533 INSN_UID (ps_rtl_insn (ps, i)));
534 fprintf (file, " asap = %d:\n", NODE_ASAP (&ps->g->nodes[i]));
535 fprintf (file, " time = %d:\n", nsp->time);
536 fprintf (file, " stage = %d:\n", nsp->stage);
540 /* Set SCHED_COLUMN for each instruction in row ROW of PS. */
542 set_columns_for_row (partial_schedule_ptr ps, int row)
544 ps_insn_ptr cur_insn;
548 for (cur_insn = ps->rows[row]; cur_insn; cur_insn = cur_insn->next_in_row)
549 SCHED_COLUMN (cur_insn->id) = column++;
552 /* Set SCHED_COLUMN for each instruction in PS. */
554 set_columns_for_ps (partial_schedule_ptr ps)
558 for (row = 0; row < ps->ii; row++)
559 set_columns_for_row (ps, row);
562 /* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
563 Its single predecessor has already been scheduled, as has its
564 ddg node successors. (The move may have also another move as its
565 successor, in which case that successor will be scheduled later.)
567 The move is part of a chain that satisfies register dependencies
568 between a producing ddg node and various consuming ddg nodes.
569 If some of these dependencies have a distance of 1 (meaning that
570 the use is upward-exposed) then DISTANCE1_USES is nonnull and
571 contains the set of uses with distance-1 dependencies.
572 DISTANCE1_USES is null otherwise.
574 MUST_FOLLOW is a scratch bitmap that is big enough to hold
575 all current ps_insn ids.
577 Return true on success. */
579 schedule_reg_move (partial_schedule_ptr ps, int i_reg_move,
580 sbitmap distance1_uses, sbitmap must_follow)
583 int this_time, this_distance, this_start, this_end, this_latency;
584 int start, end, c, ii;
585 sbitmap_iterator sbi;
586 ps_reg_move_info *move;
590 move = ps_reg_move (ps, i_reg_move);
594 fprintf (dump_file, "Scheduling register move INSN %d; ii = %d"
595 ", min cycle = %d\n\n", INSN_UID (move->insn), ii,
597 print_rtl_single (dump_file, move->insn);
598 fprintf (dump_file, "\n%11s %11s %5s\n", "start", "end", "time");
599 fprintf (dump_file, "=========== =========== =====\n");
605 /* For dependencies of distance 1 between a producer ddg node A
606 and consumer ddg node B, we have a chain of dependencies:
608 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
610 where Mi is the ith move. For dependencies of distance 0 between
611 a producer ddg node A and consumer ddg node C, we have a chain of
614 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
616 where Mi' occupies the same position as Mi but occurs a stage later.
617 We can only schedule each move once, so if we have both types of
618 chain, we model the second as:
620 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
622 First handle the dependencies between the previously-scheduled
623 predecessor and the move. */
624 this_insn = ps_rtl_insn (ps, move->def);
625 this_latency = insn_latency (this_insn, move->insn);
626 this_distance = distance1_uses && move->def < ps->g->num_nodes ? 1 : 0;
627 this_time = SCHED_TIME (move->def) - this_distance * ii;
628 this_start = this_time + this_latency;
629 this_end = this_time + ii;
631 fprintf (dump_file, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
632 this_start, this_end, SCHED_TIME (move->def),
633 INSN_UID (this_insn), this_latency, this_distance,
634 INSN_UID (move->insn));
636 if (start < this_start)
641 /* Handle the dependencies between the move and previously-scheduled
643 EXECUTE_IF_SET_IN_BITMAP (move->uses, 0, u, sbi)
645 this_insn = ps_rtl_insn (ps, u);
646 this_latency = insn_latency (move->insn, this_insn);
647 if (distance1_uses && !bitmap_bit_p (distance1_uses, u))
651 this_time = SCHED_TIME (u) + this_distance * ii;
652 this_start = this_time - ii;
653 this_end = this_time - this_latency;
655 fprintf (dump_file, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
656 this_start, this_end, SCHED_TIME (u), INSN_UID (move->insn),
657 this_latency, this_distance, INSN_UID (this_insn));
659 if (start < this_start)
667 fprintf (dump_file, "----------- ----------- -----\n");
668 fprintf (dump_file, "%11d %11d %5s %s\n", start, end, "", "(max, min)");
671 bitmap_clear (must_follow);
672 bitmap_set_bit (must_follow, move->def);
674 start = MAX (start, end - (ii - 1));
675 for (c = end; c >= start; c--)
677 psi = ps_add_node_check_conflicts (ps, i_reg_move, c,
678 move->uses, must_follow);
681 update_node_sched_params (i_reg_move, ii, c, PS_MIN_CYCLE (ps));
683 fprintf (dump_file, "\nScheduled register move INSN %d at"
684 " time %d, row %d\n\n", INSN_UID (move->insn), c,
685 SCHED_ROW (i_reg_move));
691 fprintf (dump_file, "\nNo available slot\n\n");
697 Breaking intra-loop register anti-dependences:
698 Each intra-loop register anti-dependence implies a cross-iteration true
699 dependence of distance 1. Therefore, we can remove such false dependencies
700 and figure out if the partial schedule broke them by checking if (for a
701 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
702 if so generate a register move. The number of such moves is equal to:
703 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
704 nreg_moves = ----------------------------------- + 1 - { dependence.
708 schedule_reg_moves (partial_schedule_ptr ps)
714 for (i = 0; i < g->num_nodes; i++)
716 ddg_node_ptr u = &g->nodes[i];
718 int nreg_moves = 0, i_reg_move;
719 rtx prev_reg, old_reg;
723 sbitmap distance1_uses;
724 rtx set = single_set (u->insn);
726 /* Skip instructions that do not set a register. */
727 if ((set && !REG_P (SET_DEST (set))))
730 /* Compute the number of reg_moves needed for u, by looking at life
731 ranges started at u (excluding self-loops). */
732 distances[0] = distances[1] = false;
733 for (e = u->out; e; e = e->next_out)
734 if (e->type == TRUE_DEP && e->dest != e->src)
736 int nreg_moves4e = (SCHED_TIME (e->dest->cuid)
737 - SCHED_TIME (e->src->cuid)) / ii;
739 if (e->distance == 1)
740 nreg_moves4e = (SCHED_TIME (e->dest->cuid)
741 - SCHED_TIME (e->src->cuid) + ii) / ii;
743 /* If dest precedes src in the schedule of the kernel, then dest
744 will read before src writes and we can save one reg_copy. */
745 if (SCHED_ROW (e->dest->cuid) == SCHED_ROW (e->src->cuid)
746 && SCHED_COLUMN (e->dest->cuid) < SCHED_COLUMN (e->src->cuid))
749 if (nreg_moves4e >= 1)
751 /* !single_set instructions are not supported yet and
752 thus we do not except to encounter them in the loop
753 except from the doloop part. For the latter case
754 we assume no regmoves are generated as the doloop
755 instructions are tied to the branch with an edge. */
757 /* If the instruction contains auto-inc register then
758 validate that the regmov is being generated for the
759 target regsiter rather then the inc'ed register. */
760 gcc_assert (!autoinc_var_is_used_p (u->insn, e->dest->insn));
765 gcc_assert (e->distance < 2);
766 distances[e->distance] = true;
768 nreg_moves = MAX (nreg_moves, nreg_moves4e);
774 /* Create NREG_MOVES register moves. */
775 first_move = ps->reg_moves.length ();
776 ps->reg_moves.safe_grow_cleared (first_move + nreg_moves);
777 extend_node_sched_params (ps);
779 /* Record the moves associated with this node. */
780 first_move += ps->g->num_nodes;
782 /* Generate each move. */
783 old_reg = prev_reg = SET_DEST (single_set (u->insn));
784 for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
786 ps_reg_move_info *move = ps_reg_move (ps, first_move + i_reg_move);
788 move->def = i_reg_move > 0 ? first_move + i_reg_move - 1 : i;
789 move->uses = sbitmap_alloc (first_move + nreg_moves);
790 move->old_reg = old_reg;
791 move->new_reg = gen_reg_rtx (GET_MODE (prev_reg));
792 move->num_consecutive_stages = distances[0] && distances[1] ? 2 : 1;
793 move->insn = as_a <rtx_insn *> (gen_move_insn (move->new_reg,
794 copy_rtx (prev_reg)));
795 bitmap_clear (move->uses);
797 prev_reg = move->new_reg;
800 distance1_uses = distances[1] ? sbitmap_alloc (g->num_nodes) : NULL;
803 bitmap_clear (distance1_uses);
805 /* Every use of the register defined by node may require a different
806 copy of this register, depending on the time the use is scheduled.
807 Record which uses require which move results. */
808 for (e = u->out; e; e = e->next_out)
809 if (e->type == TRUE_DEP && e->dest != e->src)
811 int dest_copy = (SCHED_TIME (e->dest->cuid)
812 - SCHED_TIME (e->src->cuid)) / ii;
814 if (e->distance == 1)
815 dest_copy = (SCHED_TIME (e->dest->cuid)
816 - SCHED_TIME (e->src->cuid) + ii) / ii;
818 if (SCHED_ROW (e->dest->cuid) == SCHED_ROW (e->src->cuid)
819 && SCHED_COLUMN (e->dest->cuid) < SCHED_COLUMN (e->src->cuid))
824 ps_reg_move_info *move;
826 move = ps_reg_move (ps, first_move + dest_copy - 1);
827 bitmap_set_bit (move->uses, e->dest->cuid);
828 if (e->distance == 1)
829 bitmap_set_bit (distance1_uses, e->dest->cuid);
833 must_follow = sbitmap_alloc (first_move + nreg_moves);
834 for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
835 if (!schedule_reg_move (ps, first_move + i_reg_move,
836 distance1_uses, must_follow))
838 sbitmap_free (must_follow);
840 sbitmap_free (distance1_uses);
841 if (i_reg_move < nreg_moves)
847 /* Emit the moves associatied with PS. Apply the substitutions
848 associated with them. */
850 apply_reg_moves (partial_schedule_ptr ps)
852 ps_reg_move_info *move;
855 FOR_EACH_VEC_ELT (ps->reg_moves, i, move)
858 sbitmap_iterator sbi;
860 EXECUTE_IF_SET_IN_BITMAP (move->uses, 0, i_use, sbi)
862 replace_rtx (ps->g->nodes[i_use].insn, move->old_reg, move->new_reg);
863 df_insn_rescan (ps->g->nodes[i_use].insn);
868 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
869 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
870 will move to cycle zero. */
872 reset_sched_times (partial_schedule_ptr ps, int amount)
876 ps_insn_ptr crr_insn;
878 for (row = 0; row < ii; row++)
879 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
881 int u = crr_insn->id;
882 int normalized_time = SCHED_TIME (u) - amount;
883 int new_min_cycle = PS_MIN_CYCLE (ps) - amount;
887 /* Print the scheduling times after the rotation. */
888 rtx_insn *insn = ps_rtl_insn (ps, u);
890 fprintf (dump_file, "crr_insn->node=%d (insn id %d), "
891 "crr_insn->cycle=%d, min_cycle=%d", u,
892 INSN_UID (insn), normalized_time, new_min_cycle);
894 fprintf (dump_file, " (branch)");
895 fprintf (dump_file, "\n");
898 gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
899 gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
901 crr_insn->cycle = normalized_time;
902 update_node_sched_params (u, ii, normalized_time, new_min_cycle);
906 /* Permute the insns according to their order in PS, from row 0 to
907 row ii-1, and position them right before LAST. This schedules
908 the insns of the loop kernel. */
910 permute_partial_schedule (partial_schedule_ptr ps, rtx_insn *last)
916 for (row = 0; row < ii ; row++)
917 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
919 rtx_insn *insn = ps_rtl_insn (ps, ps_ij->id);
921 if (PREV_INSN (last) != insn)
923 if (ps_ij->id < ps->g->num_nodes)
924 reorder_insns_nobb (ps_first_note (ps, ps_ij->id), insn,
927 add_insn_before (insn, last, NULL);
932 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
933 respectively only if cycle C falls on the border of the scheduling
934 window boundaries marked by START and END cycles. STEP is the
935 direction of the window. */
937 set_must_precede_follow (sbitmap *tmp_follow, sbitmap must_follow,
938 sbitmap *tmp_precede, sbitmap must_precede, int c,
939 int start, int end, int step)
947 *tmp_precede = must_precede;
948 else /* step == -1. */
949 *tmp_follow = must_follow;
954 *tmp_follow = must_follow;
955 else /* step == -1. */
956 *tmp_precede = must_precede;
961 /* Return True if the branch can be moved to row ii-1 while
962 normalizing the partial schedule PS to start from cycle zero and thus
963 optimize the SC. Otherwise return False. */
965 optimize_sc (partial_schedule_ptr ps, ddg_ptr g)
967 int amount = PS_MIN_CYCLE (ps);
968 sbitmap sched_nodes = sbitmap_alloc (g->num_nodes);
969 int start, end, step;
972 int stage_count, stage_count_curr;
974 /* Compare the SC after normalization and SC after bringing the branch
975 to row ii-1. If they are equal just bail out. */
976 stage_count = calculate_stage_count (ps, amount);
978 calculate_stage_count (ps, SCHED_TIME (g->closing_branch->cuid) - (ii - 1));
980 if (stage_count == stage_count_curr)
983 fprintf (dump_file, "SMS SC already optimized.\n");
991 fprintf (dump_file, "SMS Trying to optimize branch location\n");
992 fprintf (dump_file, "SMS partial schedule before trial:\n");
993 print_partial_schedule (ps, dump_file);
996 /* First, normalize the partial scheduling. */
997 reset_sched_times (ps, amount);
998 rotate_partial_schedule (ps, amount);
1002 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
1004 print_partial_schedule (ps, dump_file);
1007 if (SMODULO (SCHED_TIME (g->closing_branch->cuid), ii) == ii - 1)
1013 bitmap_ones (sched_nodes);
1015 /* Calculate the new placement of the branch. It should be in row
1016 ii-1 and fall into it's scheduling window. */
1017 if (get_sched_window (ps, g->closing_branch, sched_nodes, ii, &start,
1021 ps_insn_ptr next_ps_i;
1022 int branch_cycle = SCHED_TIME (g->closing_branch->cuid);
1023 int row = SMODULO (branch_cycle, ps->ii);
1025 sbitmap must_precede, must_follow, tmp_precede, tmp_follow;
1029 fprintf (dump_file, "\nTrying to schedule node %d "
1030 "INSN = %d in (%d .. %d) step %d\n",
1031 g->closing_branch->cuid,
1032 (INSN_UID (g->closing_branch->insn)), start, end, step);
1034 gcc_assert ((step > 0 && start < end) || (step < 0 && start > end));
1037 c = start + ii - SMODULO (start, ii) - 1;
1038 gcc_assert (c >= start);
1044 "SMS failed to schedule branch at cycle: %d\n", c);
1050 c = start - SMODULO (start, ii) - 1;
1051 gcc_assert (c <= start);
1057 "SMS failed to schedule branch at cycle: %d\n", c);
1063 must_precede = sbitmap_alloc (g->num_nodes);
1064 must_follow = sbitmap_alloc (g->num_nodes);
1066 /* Try to schedule the branch is it's new cycle. */
1067 calculate_must_precede_follow (g->closing_branch, start, end,
1068 step, ii, sched_nodes,
1069 must_precede, must_follow);
1071 set_must_precede_follow (&tmp_follow, must_follow, &tmp_precede,
1072 must_precede, c, start, end, step);
1074 /* Find the element in the partial schedule related to the closing
1075 branch so we can remove it from it's current cycle. */
1076 for (next_ps_i = ps->rows[row];
1077 next_ps_i; next_ps_i = next_ps_i->next_in_row)
1078 if (next_ps_i->id == g->closing_branch->cuid)
1081 min_cycle = PS_MIN_CYCLE (ps) - SMODULO (PS_MIN_CYCLE (ps), ps->ii);
1082 remove_node_from_ps (ps, next_ps_i);
1084 try_scheduling_node_in_cycle (ps, g->closing_branch->cuid, c,
1085 sched_nodes, &num_splits,
1086 tmp_precede, tmp_follow);
1087 gcc_assert (num_splits == 0);
1092 "SMS failed to schedule branch at cycle: %d, "
1093 "bringing it back to cycle %d\n", c, branch_cycle);
1095 /* The branch was failed to be placed in row ii - 1.
1096 Put it back in it's original place in the partial
1098 set_must_precede_follow (&tmp_follow, must_follow, &tmp_precede,
1099 must_precede, branch_cycle, start, end,
1102 try_scheduling_node_in_cycle (ps, g->closing_branch->cuid,
1103 branch_cycle, sched_nodes,
1104 &num_splits, tmp_precede,
1106 gcc_assert (success && (num_splits == 0));
1111 /* The branch is placed in row ii - 1. */
1114 "SMS success in moving branch to cycle %d\n", c);
1116 update_node_sched_params (g->closing_branch->cuid, ii, c,
1121 /* This might have been added to a new first stage. */
1122 if (PS_MIN_CYCLE (ps) < min_cycle)
1123 reset_sched_times (ps, 0);
1125 free (must_precede);
1135 duplicate_insns_of_cycles (partial_schedule_ptr ps, int from_stage,
1136 int to_stage, rtx count_reg)
1141 for (row = 0; row < ps->ii; row++)
1142 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
1145 int first_u, last_u;
1148 /* Do not duplicate any insn which refers to count_reg as it
1149 belongs to the control part.
1150 The closing branch is scheduled as well and thus should
1152 TODO: This should be done by analyzing the control part of
1154 u_insn = ps_rtl_insn (ps, u);
1155 if (reg_mentioned_p (count_reg, u_insn)
1159 first_u = SCHED_STAGE (u);
1160 last_u = first_u + ps_num_consecutive_stages (ps, u) - 1;
1161 if (from_stage <= last_u && to_stage >= first_u)
1163 if (u < ps->g->num_nodes)
1164 duplicate_insn_chain (ps_first_note (ps, u), u_insn);
1166 emit_insn (copy_rtx (PATTERN (u_insn)));
1172 /* Generate the instructions (including reg_moves) for prolog & epilog. */
1174 generate_prolog_epilog (partial_schedule_ptr ps, struct loop *loop,
1175 rtx count_reg, rtx count_init)
1178 int last_stage = PS_STAGE_COUNT (ps) - 1;
1181 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1186 /* Generate instructions at the beginning of the prolog to
1187 adjust the loop count by STAGE_COUNT. If loop count is constant
1188 (count_init), this constant is adjusted by STAGE_COUNT in
1189 generate_prolog_epilog function. */
1190 rtx sub_reg = NULL_RTX;
1192 sub_reg = expand_simple_binop (GET_MODE (count_reg), MINUS, count_reg,
1193 gen_int_mode (last_stage,
1194 GET_MODE (count_reg)),
1195 count_reg, 1, OPTAB_DIRECT);
1196 gcc_assert (REG_P (sub_reg));
1197 if (REGNO (sub_reg) != REGNO (count_reg))
1198 emit_move_insn (count_reg, sub_reg);
1201 for (i = 0; i < last_stage; i++)
1202 duplicate_insns_of_cycles (ps, 0, i, count_reg);
1204 /* Put the prolog on the entry edge. */
1205 e = loop_preheader_edge (loop);
1206 split_edge_and_insert (e, get_insns ());
1207 if (!flag_resched_modulo_sched)
1208 e->dest->flags |= BB_DISABLE_SCHEDULE;
1212 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1215 for (i = 0; i < last_stage; i++)
1216 duplicate_insns_of_cycles (ps, i + 1, last_stage, count_reg);
1218 /* Put the epilogue on the exit edge. */
1219 gcc_assert (single_exit (loop));
1220 e = single_exit (loop);
1221 split_edge_and_insert (e, get_insns ());
1222 if (!flag_resched_modulo_sched)
1223 e->dest->flags |= BB_DISABLE_SCHEDULE;
1228 /* Mark LOOP as software pipelined so the later
1229 scheduling passes don't touch it. */
1231 mark_loop_unsched (struct loop *loop)
1234 basic_block *bbs = get_loop_body (loop);
1236 for (i = 0; i < loop->num_nodes; i++)
1237 bbs[i]->flags |= BB_DISABLE_SCHEDULE;
1242 /* Return true if all the BBs of the loop are empty except the
1245 loop_single_full_bb_p (struct loop *loop)
1248 basic_block *bbs = get_loop_body (loop);
1250 for (i = 0; i < loop->num_nodes ; i++)
1252 rtx_insn *head, *tail;
1253 bool empty_bb = true;
1255 if (bbs[i] == loop->header)
1258 /* Make sure that basic blocks other than the header
1259 have only notes labels or jumps. */
1260 get_ebb_head_tail (bbs[i], bbs[i], &head, &tail);
1261 for (; head != NEXT_INSN (tail); head = NEXT_INSN (head))
1263 if (NOTE_P (head) || LABEL_P (head)
1264 || (INSN_P (head) && (DEBUG_INSN_P (head) || JUMP_P (head))))
1280 /* Dump file:line from INSN's location info to dump_file. */
1283 dump_insn_location (rtx_insn *insn)
1285 if (dump_file && INSN_HAS_LOCATION (insn))
1287 expanded_location xloc = insn_location (insn);
1288 fprintf (dump_file, " %s:%i", xloc.file, xloc.line);
1292 /* A simple loop from SMS point of view; it is a loop that is composed of
1293 either a single basic block or two BBs - a header and a latch. */
1294 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1295 && (EDGE_COUNT (loop->latch->preds) == 1) \
1296 && (EDGE_COUNT (loop->latch->succs) == 1))
1298 /* Return true if the loop is in its canonical form and false if not.
1299 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1301 loop_canon_p (struct loop *loop)
1304 if (loop->inner || !loop_outer (loop))
1307 fprintf (dump_file, "SMS loop inner or !loop_outer\n");
1311 if (!single_exit (loop))
1315 rtx_insn *insn = BB_END (loop->header);
1317 fprintf (dump_file, "SMS loop many exits");
1318 dump_insn_location (insn);
1319 fprintf (dump_file, "\n");
1324 if (! SIMPLE_SMS_LOOP_P (loop) && ! loop_single_full_bb_p (loop))
1328 rtx_insn *insn = BB_END (loop->header);
1330 fprintf (dump_file, "SMS loop many BBs.");
1331 dump_insn_location (insn);
1332 fprintf (dump_file, "\n");
1340 /* If there are more than one entry for the loop,
1341 make it one by splitting the first entry edge and
1342 redirecting the others to the new BB. */
1344 canon_loop (struct loop *loop)
1349 /* Avoid annoying special cases of edges going to exit
1351 FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
1352 if ((e->flags & EDGE_FALLTHRU) && (EDGE_COUNT (e->src->succs) > 1))
1355 if (loop->latch == loop->header
1356 || EDGE_COUNT (loop->latch->succs) > 1)
1358 FOR_EACH_EDGE (e, i, loop->header->preds)
1359 if (e->src == loop->latch)
1367 setup_sched_infos (void)
1369 memcpy (&sms_common_sched_info, &haifa_common_sched_info,
1370 sizeof (sms_common_sched_info));
1371 sms_common_sched_info.sched_pass_id = SCHED_SMS_PASS;
1372 common_sched_info = &sms_common_sched_info;
1374 sched_deps_info = &sms_sched_deps_info;
1375 current_sched_info = &sms_sched_info;
1378 /* Probability in % that the sms-ed loop rolls enough so that optimized
1379 version may be entered. Just a guess. */
1380 #define PROB_SMS_ENOUGH_ITERATIONS 80
1382 /* Used to calculate the upper bound of ii. */
1383 #define MAXII_FACTOR 2
1385 /* Main entry point, perform SMS scheduling on the loops of the function
1386 that consist of single basic blocks. */
1393 int maxii, max_asap;
1394 partial_schedule_ptr ps;
1395 basic_block bb = NULL;
1397 basic_block condition_bb = NULL;
1399 gcov_type trip_count = 0;
1401 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1402 | LOOPS_HAVE_RECORDED_EXITS);
1403 if (number_of_loops (cfun) <= 1)
1405 loop_optimizer_finalize ();
1406 return; /* There are no loops to schedule. */
1409 /* Initialize issue_rate. */
1410 if (targetm.sched.issue_rate)
1412 int temp = reload_completed;
1414 reload_completed = 1;
1415 issue_rate = targetm.sched.issue_rate ();
1416 reload_completed = temp;
1421 /* Initialize the scheduler. */
1422 setup_sched_infos ();
1423 haifa_sched_init ();
1425 /* Allocate memory to hold the DDG array one entry for each loop.
1426 We use loop->num as index into this array. */
1427 g_arr = XCNEWVEC (ddg_ptr, number_of_loops (cfun));
1431 fprintf (dump_file, "\n\nSMS analysis phase\n");
1432 fprintf (dump_file, "===================\n\n");
1435 /* Build DDGs for all the relevant loops and hold them in G_ARR
1436 indexed by the loop index. */
1437 FOR_EACH_LOOP (loop, 0)
1439 rtx_insn *head, *tail;
1442 /* For debugging. */
1443 if (dbg_cnt (sms_sched_loop) == false)
1446 fprintf (dump_file, "SMS reached max limit... \n");
1453 rtx_insn *insn = BB_END (loop->header);
1455 fprintf (dump_file, "SMS loop num: %d", loop->num);
1456 dump_insn_location (insn);
1457 fprintf (dump_file, "\n");
1460 if (! loop_canon_p (loop))
1463 if (! loop_single_full_bb_p (loop))
1466 fprintf (dump_file, "SMS not loop_single_full_bb_p\n");
1472 get_ebb_head_tail (bb, bb, &head, &tail);
1473 latch_edge = loop_latch_edge (loop);
1474 gcc_assert (single_exit (loop));
1475 if (single_exit (loop)->count)
1476 trip_count = latch_edge->count / single_exit (loop)->count;
1478 /* Perform SMS only on loops that their average count is above threshold. */
1480 if ( latch_edge->count
1481 && (latch_edge->count < single_exit (loop)->count * SMS_LOOP_AVERAGE_COUNT_THRESHOLD))
1485 dump_insn_location (tail);
1486 fprintf (dump_file, "\nSMS single-bb-loop\n");
1487 if (profile_info && flag_branch_probabilities)
1489 fprintf (dump_file, "SMS loop-count ");
1490 fprintf (dump_file, "%"PRId64,
1491 (int64_t) bb->count);
1492 fprintf (dump_file, "\n");
1493 fprintf (dump_file, "SMS trip-count ");
1494 fprintf (dump_file, "%"PRId64,
1495 (int64_t) trip_count);
1496 fprintf (dump_file, "\n");
1497 fprintf (dump_file, "SMS profile-sum-max ");
1498 fprintf (dump_file, "%"PRId64,
1499 (int64_t) profile_info->sum_max);
1500 fprintf (dump_file, "\n");
1506 /* Make sure this is a doloop. */
1507 if ( !(count_reg = doloop_register_get (head, tail)))
1510 fprintf (dump_file, "SMS doloop_register_get failed\n");
1514 /* Don't handle BBs with calls or barriers
1515 or !single_set with the exception of instructions that include
1516 count_reg---these instructions are part of the control part
1517 that do-loop recognizes.
1518 ??? Should handle insns defining subregs. */
1519 for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn))
1525 || (NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
1526 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE
1527 && !reg_mentioned_p (count_reg, insn))
1528 || (INSN_P (insn) && (set = single_set (insn))
1529 && GET_CODE (SET_DEST (set)) == SUBREG))
1533 if (insn != NEXT_INSN (tail))
1538 fprintf (dump_file, "SMS loop-with-call\n");
1539 else if (BARRIER_P (insn))
1540 fprintf (dump_file, "SMS loop-with-barrier\n");
1541 else if ((NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
1542 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE))
1543 fprintf (dump_file, "SMS loop-with-not-single-set\n");
1545 fprintf (dump_file, "SMS loop with subreg in lhs\n");
1546 print_rtl_single (dump_file, insn);
1552 /* Always schedule the closing branch with the rest of the
1553 instructions. The branch is rotated to be in row ii-1 at the
1554 end of the scheduling procedure to make sure it's the last
1555 instruction in the iteration. */
1556 if (! (g = create_ddg (bb, 1)))
1559 fprintf (dump_file, "SMS create_ddg failed\n");
1563 g_arr[loop->num] = g;
1565 fprintf (dump_file, "...OK\n");
1570 fprintf (dump_file, "\nSMS transformation phase\n");
1571 fprintf (dump_file, "=========================\n\n");
1574 /* We don't want to perform SMS on new loops - created by versioning. */
1575 FOR_EACH_LOOP (loop, 0)
1577 rtx_insn *head, *tail;
1579 rtx_insn *count_init;
1580 int mii, rec_mii, stage_count, min_cycle;
1581 int64_t loop_count = 0;
1584 if (! (g = g_arr[loop->num]))
1589 rtx_insn *insn = BB_END (loop->header);
1591 fprintf (dump_file, "SMS loop num: %d", loop->num);
1592 dump_insn_location (insn);
1593 fprintf (dump_file, "\n");
1595 print_ddg (dump_file, g);
1598 get_ebb_head_tail (loop->header, loop->header, &head, &tail);
1600 latch_edge = loop_latch_edge (loop);
1601 gcc_assert (single_exit (loop));
1602 if (single_exit (loop)->count)
1603 trip_count = latch_edge->count / single_exit (loop)->count;
1607 dump_insn_location (tail);
1608 fprintf (dump_file, "\nSMS single-bb-loop\n");
1609 if (profile_info && flag_branch_probabilities)
1611 fprintf (dump_file, "SMS loop-count ");
1612 fprintf (dump_file, "%"PRId64,
1613 (int64_t) bb->count);
1614 fprintf (dump_file, "\n");
1615 fprintf (dump_file, "SMS profile-sum-max ");
1616 fprintf (dump_file, "%"PRId64,
1617 (int64_t) profile_info->sum_max);
1618 fprintf (dump_file, "\n");
1620 fprintf (dump_file, "SMS doloop\n");
1621 fprintf (dump_file, "SMS built-ddg %d\n", g->num_nodes);
1622 fprintf (dump_file, "SMS num-loads %d\n", g->num_loads);
1623 fprintf (dump_file, "SMS num-stores %d\n", g->num_stores);
1627 /* In case of th loop have doloop register it gets special
1630 if ((count_reg = doloop_register_get (head, tail)))
1632 basic_block pre_header;
1634 pre_header = loop_preheader_edge (loop)->src;
1635 count_init = const_iteration_count (count_reg, pre_header,
1638 gcc_assert (count_reg);
1640 if (dump_file && count_init)
1642 fprintf (dump_file, "SMS const-doloop ");
1643 fprintf (dump_file, "%"PRId64,
1645 fprintf (dump_file, "\n");
1648 node_order = XNEWVEC (int, g->num_nodes);
1650 mii = 1; /* Need to pass some estimate of mii. */
1651 rec_mii = sms_order_nodes (g, mii, node_order, &max_asap);
1652 mii = MAX (res_MII (g), rec_mii);
1653 maxii = MAX (max_asap, MAXII_FACTOR * mii);
1656 fprintf (dump_file, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1657 rec_mii, mii, maxii);
1661 set_node_sched_params (g);
1665 ps = sms_schedule_by_order (g, mii, maxii, node_order);
1669 /* Try to achieve optimized SC by normalizing the partial
1670 schedule (having the cycles start from cycle zero).
1671 The branch location must be placed in row ii-1 in the
1672 final scheduling. If failed, shift all instructions to
1673 position the branch in row ii-1. */
1674 opt_sc_p = optimize_sc (ps, g);
1676 stage_count = calculate_stage_count (ps, 0);
1679 /* Bring the branch to cycle ii-1. */
1680 int amount = (SCHED_TIME (g->closing_branch->cuid)
1684 fprintf (dump_file, "SMS schedule branch at cycle ii-1\n");
1686 stage_count = calculate_stage_count (ps, amount);
1689 gcc_assert (stage_count >= 1);
1692 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
1693 1 means that there is no interleaving between iterations thus
1694 we let the scheduling passes do the job in this case. */
1695 if (stage_count < PARAM_VALUE (PARAM_SMS_MIN_SC)
1696 || (count_init && (loop_count <= stage_count))
1697 || (flag_branch_probabilities && (trip_count <= stage_count)))
1701 fprintf (dump_file, "SMS failed... \n");
1702 fprintf (dump_file, "SMS sched-failed (stage-count=%d,"
1703 " loop-count=", stage_count);
1704 fprintf (dump_file, "%"PRId64, loop_count);
1705 fprintf (dump_file, ", trip-count=");
1706 fprintf (dump_file, "%"PRId64, trip_count);
1707 fprintf (dump_file, ")\n");
1714 /* Rotate the partial schedule to have the branch in row ii-1. */
1715 int amount = SCHED_TIME (g->closing_branch->cuid) - (ps->ii - 1);
1717 reset_sched_times (ps, amount);
1718 rotate_partial_schedule (ps, amount);
1721 set_columns_for_ps (ps);
1723 min_cycle = PS_MIN_CYCLE (ps) - SMODULO (PS_MIN_CYCLE (ps), ps->ii);
1724 if (!schedule_reg_moves (ps))
1727 free_partial_schedule (ps);
1731 /* Moves that handle incoming values might have been added
1732 to a new first stage. Bump the stage count if so.
1734 ??? Perhaps we could consider rotating the schedule here
1736 if (PS_MIN_CYCLE (ps) < min_cycle)
1738 reset_sched_times (ps, 0);
1742 /* The stage count should now be correct without rotation. */
1743 gcc_checking_assert (stage_count == calculate_stage_count (ps, 0));
1744 PS_STAGE_COUNT (ps) = stage_count;
1750 dump_insn_location (tail);
1751 fprintf (dump_file, " SMS succeeded %d %d (with ii, sc)\n",
1752 ps->ii, stage_count);
1753 print_partial_schedule (ps, dump_file);
1756 /* case the BCT count is not known , Do loop-versioning */
1757 if (count_reg && ! count_init)
1759 rtx comp_rtx = gen_rtx_GT (VOIDmode, count_reg,
1760 gen_int_mode (stage_count,
1761 GET_MODE (count_reg)));
1762 unsigned prob = (PROB_SMS_ENOUGH_ITERATIONS
1763 * REG_BR_PROB_BASE) / 100;
1765 loop_version (loop, comp_rtx, &condition_bb,
1766 prob, prob, REG_BR_PROB_BASE - prob,
1770 /* Set new iteration count of loop kernel. */
1771 if (count_reg && count_init)
1772 SET_SRC (single_set (count_init)) = GEN_INT (loop_count
1775 /* Now apply the scheduled kernel to the RTL of the loop. */
1776 permute_partial_schedule (ps, g->closing_branch->first_note);
1778 /* Mark this loop as software pipelined so the later
1779 scheduling passes don't touch it. */
1780 if (! flag_resched_modulo_sched)
1781 mark_loop_unsched (loop);
1783 /* The life-info is not valid any more. */
1784 df_set_bb_dirty (g->bb);
1786 apply_reg_moves (ps);
1788 print_node_sched_params (dump_file, g->num_nodes, ps);
1789 /* Generate prolog and epilog. */
1790 generate_prolog_epilog (ps, loop, count_reg, count_init);
1794 free_partial_schedule (ps);
1795 node_sched_param_vec.release ();
1802 /* Release scheduler data, needed until now because of DFA. */
1803 haifa_sched_finish ();
1804 loop_optimizer_finalize ();
1807 /* The SMS scheduling algorithm itself
1808 -----------------------------------
1809 Input: 'O' an ordered list of insns of a loop.
1810 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1812 'Q' is the empty Set
1813 'PS' is the partial schedule; it holds the currently scheduled nodes with
1815 'PSP' previously scheduled predecessors.
1816 'PSS' previously scheduled successors.
1817 't(u)' the cycle where u is scheduled.
1818 'l(u)' is the latency of u.
1819 'd(v,u)' is the dependence distance from v to u.
1820 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1821 the node ordering phase.
1822 'check_hardware_resources_conflicts(u, PS, c)'
1823 run a trace around cycle/slot through DFA model
1824 to check resource conflicts involving instruction u
1825 at cycle c given the partial schedule PS.
1826 'add_to_partial_schedule_at_time(u, PS, c)'
1827 Add the node/instruction u to the partial schedule
1829 'calculate_register_pressure(PS)'
1830 Given a schedule of instructions, calculate the register
1831 pressure it implies. One implementation could be the
1832 maximum number of overlapping live ranges.
1833 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1834 registers available in the hardware.
1838 3. for each node u in O in pre-computed order
1839 4. if (PSP(u) != Q && PSS(u) == Q) then
1840 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1841 6. start = Early_start; end = Early_start + II - 1; step = 1
1842 11. else if (PSP(u) == Q && PSS(u) != Q) then
1843 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1844 13. start = Late_start; end = Late_start - II + 1; step = -1
1845 14. else if (PSP(u) != Q && PSS(u) != Q) then
1846 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1847 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1848 17. start = Early_start;
1849 18. end = min(Early_start + II - 1 , Late_start);
1851 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1852 21. start = ASAP(u); end = start + II - 1; step = 1
1856 24. for (c = start ; c != end ; c += step)
1857 25. if check_hardware_resources_conflicts(u, PS, c) then
1858 26. add_to_partial_schedule_at_time(u, PS, c)
1863 31. if (success == false) then
1865 33. if (II > maxII) then
1866 34. finish - failed to schedule
1871 39. if (calculate_register_pressure(PS) > maxRP) then
1874 42. compute epilogue & prologue
1875 43. finish - succeeded to schedule
1877 ??? The algorithm restricts the scheduling window to II cycles.
1878 In rare cases, it may be better to allow windows of II+1 cycles.
1879 The window would then start and end on the same row, but with
1880 different "must precede" and "must follow" requirements. */
1882 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1883 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1884 set to 0 to save compile time. */
1885 #define DFA_HISTORY SMS_DFA_HISTORY
1887 /* A threshold for the number of repeated unsuccessful attempts to insert
1888 an empty row, before we flush the partial schedule and start over. */
1889 #define MAX_SPLIT_NUM 10
1890 /* Given the partial schedule PS, this function calculates and returns the
1891 cycles in which we can schedule the node with the given index I.
1892 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1893 noticed that there are several cases in which we fail to SMS the loop
1894 because the sched window of a node is empty due to tight data-deps. In
1895 such cases we want to unschedule some of the predecessors/successors
1896 until we get non-empty scheduling window. It returns -1 if the
1897 scheduling window is empty and zero otherwise. */
1900 get_sched_window (partial_schedule_ptr ps, ddg_node_ptr u_node,
1901 sbitmap sched_nodes, int ii, int *start_p, int *step_p,
1904 int start, step, end;
1905 int early_start, late_start;
1907 sbitmap psp = sbitmap_alloc (ps->g->num_nodes);
1908 sbitmap pss = sbitmap_alloc (ps->g->num_nodes);
1909 sbitmap u_node_preds = NODE_PREDECESSORS (u_node);
1910 sbitmap u_node_succs = NODE_SUCCESSORS (u_node);
1916 /* 1. compute sched window for u (start, end, step). */
1919 psp_not_empty = bitmap_and (psp, u_node_preds, sched_nodes);
1920 pss_not_empty = bitmap_and (pss, u_node_succs, sched_nodes);
1922 /* We first compute a forward range (start <= end), then decide whether
1924 early_start = INT_MIN;
1925 late_start = INT_MAX;
1933 if (dump_file && (psp_not_empty || pss_not_empty))
1935 fprintf (dump_file, "\nAnalyzing dependencies for node %d (INSN %d)"
1936 "; ii = %d\n\n", u_node->cuid, INSN_UID (u_node->insn), ii);
1937 fprintf (dump_file, "%11s %11s %11s %11s %5s\n",
1938 "start", "early start", "late start", "end", "time");
1939 fprintf (dump_file, "=========== =========== =========== ==========="
1942 /* Calculate early_start and limit end. Both bounds are inclusive. */
1944 for (e = u_node->in; e != 0; e = e->next_in)
1946 int v = e->src->cuid;
1948 if (bitmap_bit_p (sched_nodes, v))
1950 int p_st = SCHED_TIME (v);
1951 int earliest = p_st + e->latency - (e->distance * ii);
1952 int latest = (e->data_type == MEM_DEP ? p_st + ii - 1 : INT_MAX);
1956 fprintf (dump_file, "%11s %11d %11s %11d %5d",
1957 "", earliest, "", latest, p_st);
1958 print_ddg_edge (dump_file, e);
1959 fprintf (dump_file, "\n");
1962 early_start = MAX (early_start, earliest);
1963 end = MIN (end, latest);
1965 if (e->type == TRUE_DEP && e->data_type == REG_DEP)
1970 /* Calculate late_start and limit start. Both bounds are inclusive. */
1972 for (e = u_node->out; e != 0; e = e->next_out)
1974 int v = e->dest->cuid;
1976 if (bitmap_bit_p (sched_nodes, v))
1978 int s_st = SCHED_TIME (v);
1979 int earliest = (e->data_type == MEM_DEP ? s_st - ii + 1 : INT_MIN);
1980 int latest = s_st - e->latency + (e->distance * ii);
1984 fprintf (dump_file, "%11d %11s %11d %11s %5d",
1985 earliest, "", latest, "", s_st);
1986 print_ddg_edge (dump_file, e);
1987 fprintf (dump_file, "\n");
1990 start = MAX (start, earliest);
1991 late_start = MIN (late_start, latest);
1993 if (e->type == TRUE_DEP && e->data_type == REG_DEP)
1998 if (dump_file && (psp_not_empty || pss_not_empty))
2000 fprintf (dump_file, "----------- ----------- ----------- -----------"
2002 fprintf (dump_file, "%11d %11d %11d %11d %5s %s\n",
2003 start, early_start, late_start, end, "",
2004 "(max, max, min, min)");
2007 /* Get a target scheduling window no bigger than ii. */
2008 if (early_start == INT_MIN && late_start == INT_MAX)
2009 early_start = NODE_ASAP (u_node);
2010 else if (early_start == INT_MIN)
2011 early_start = late_start - (ii - 1);
2012 late_start = MIN (late_start, early_start + (ii - 1));
2014 /* Apply memory dependence limits. */
2015 start = MAX (start, early_start);
2016 end = MIN (end, late_start);
2018 if (dump_file && (psp_not_empty || pss_not_empty))
2019 fprintf (dump_file, "%11s %11d %11d %11s %5s final window\n",
2020 "", start, end, "", "");
2022 /* If there are at least as many successors as predecessors, schedule the
2023 node close to its successors. */
2024 if (pss_not_empty && count_succs >= count_preds)
2032 /* Now that we've finalized the window, make END an exclusive rather
2033 than an inclusive bound. */
2042 if ((start >= end && step == 1) || (start <= end && step == -1))
2045 fprintf (dump_file, "\nEmpty window: start=%d, end=%d, step=%d\n",
2053 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
2054 node currently been scheduled. At the end of the calculation
2055 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
2056 U_NODE which are (1) already scheduled in the first/last row of
2057 U_NODE's scheduling window, (2) whose dependence inequality with U
2058 becomes an equality when U is scheduled in this same row, and (3)
2059 whose dependence latency is zero.
2061 The first and last rows are calculated using the following parameters:
2062 START/END rows - The cycles that begins/ends the traversal on the window;
2063 searching for an empty cycle to schedule U_NODE.
2064 STEP - The direction in which we traverse the window.
2065 II - The initiation interval. */
2068 calculate_must_precede_follow (ddg_node_ptr u_node, int start, int end,
2069 int step, int ii, sbitmap sched_nodes,
2070 sbitmap must_precede, sbitmap must_follow)
2073 int first_cycle_in_window, last_cycle_in_window;
2075 gcc_assert (must_precede && must_follow);
2077 /* Consider the following scheduling window:
2078 {first_cycle_in_window, first_cycle_in_window+1, ...,
2079 last_cycle_in_window}. If step is 1 then the following will be
2080 the order we traverse the window: {start=first_cycle_in_window,
2081 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
2082 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
2083 end=first_cycle_in_window-1} if step is -1. */
2084 first_cycle_in_window = (step == 1) ? start : end - step;
2085 last_cycle_in_window = (step == 1) ? end - step : start;
2087 bitmap_clear (must_precede);
2088 bitmap_clear (must_follow);
2091 fprintf (dump_file, "\nmust_precede: ");
2093 /* Instead of checking if:
2094 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
2095 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
2096 first_cycle_in_window)
2098 we use the fact that latency is non-negative:
2099 SCHED_TIME (e->src) - (e->distance * ii) <=
2100 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
2101 first_cycle_in_window
2103 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
2104 for (e = u_node->in; e != 0; e = e->next_in)
2105 if (bitmap_bit_p (sched_nodes, e->src->cuid)
2106 && ((SCHED_TIME (e->src->cuid) - (e->distance * ii)) ==
2107 first_cycle_in_window))
2110 fprintf (dump_file, "%d ", e->src->cuid);
2112 bitmap_set_bit (must_precede, e->src->cuid);
2116 fprintf (dump_file, "\nmust_follow: ");
2118 /* Instead of checking if:
2119 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
2120 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
2121 last_cycle_in_window)
2123 we use the fact that latency is non-negative:
2124 SCHED_TIME (e->dest) + (e->distance * ii) >=
2125 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
2126 last_cycle_in_window
2128 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
2129 for (e = u_node->out; e != 0; e = e->next_out)
2130 if (bitmap_bit_p (sched_nodes, e->dest->cuid)
2131 && ((SCHED_TIME (e->dest->cuid) + (e->distance * ii)) ==
2132 last_cycle_in_window))
2135 fprintf (dump_file, "%d ", e->dest->cuid);
2137 bitmap_set_bit (must_follow, e->dest->cuid);
2141 fprintf (dump_file, "\n");
2144 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
2145 parameters to decide if that's possible:
2146 PS - The partial schedule.
2147 U - The serial number of U_NODE.
2148 NUM_SPLITS - The number of row splits made so far.
2149 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
2150 the first row of the scheduling window)
2151 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
2152 last row of the scheduling window) */
2155 try_scheduling_node_in_cycle (partial_schedule_ptr ps,
2156 int u, int cycle, sbitmap sched_nodes,
2157 int *num_splits, sbitmap must_precede,
2158 sbitmap must_follow)
2163 verify_partial_schedule (ps, sched_nodes);
2164 psi = ps_add_node_check_conflicts (ps, u, cycle, must_precede, must_follow);
2167 SCHED_TIME (u) = cycle;
2168 bitmap_set_bit (sched_nodes, u);
2172 fprintf (dump_file, "Scheduled w/o split in %d\n", cycle);
2179 /* This function implements the scheduling algorithm for SMS according to the
2181 static partial_schedule_ptr
2182 sms_schedule_by_order (ddg_ptr g, int mii, int maxii, int *nodes_order)
2185 int i, c, success, num_splits = 0;
2186 int flush_and_start_over = true;
2187 int num_nodes = g->num_nodes;
2188 int start, end, step; /* Place together into one struct? */
2189 sbitmap sched_nodes = sbitmap_alloc (num_nodes);
2190 sbitmap must_precede = sbitmap_alloc (num_nodes);
2191 sbitmap must_follow = sbitmap_alloc (num_nodes);
2192 sbitmap tobe_scheduled = sbitmap_alloc (num_nodes);
2194 partial_schedule_ptr ps = create_partial_schedule (ii, g, DFA_HISTORY);
2196 bitmap_ones (tobe_scheduled);
2197 bitmap_clear (sched_nodes);
2199 while (flush_and_start_over && (ii < maxii))
2203 fprintf (dump_file, "Starting with ii=%d\n", ii);
2204 flush_and_start_over = false;
2205 bitmap_clear (sched_nodes);
2207 for (i = 0; i < num_nodes; i++)
2209 int u = nodes_order[i];
2210 ddg_node_ptr u_node = &ps->g->nodes[u];
2211 rtx insn = u_node->insn;
2213 if (!NONDEBUG_INSN_P (insn))
2215 bitmap_clear_bit (tobe_scheduled, u);
2219 if (bitmap_bit_p (sched_nodes, u))
2222 /* Try to get non-empty scheduling window. */
2224 if (get_sched_window (ps, u_node, sched_nodes, ii, &start,
2228 fprintf (dump_file, "\nTrying to schedule node %d "
2229 "INSN = %d in (%d .. %d) step %d\n", u, (INSN_UID
2230 (g->nodes[u].insn)), start, end, step);
2232 gcc_assert ((step > 0 && start < end)
2233 || (step < 0 && start > end));
2235 calculate_must_precede_follow (u_node, start, end, step, ii,
2236 sched_nodes, must_precede,
2239 for (c = start; c != end; c += step)
2241 sbitmap tmp_precede, tmp_follow;
2243 set_must_precede_follow (&tmp_follow, must_follow,
2244 &tmp_precede, must_precede,
2245 c, start, end, step);
2247 try_scheduling_node_in_cycle (ps, u, c,
2249 &num_splits, tmp_precede,
2255 verify_partial_schedule (ps, sched_nodes);
2264 if (num_splits >= MAX_SPLIT_NUM)
2267 flush_and_start_over = true;
2268 verify_partial_schedule (ps, sched_nodes);
2269 reset_partial_schedule (ps, ii);
2270 verify_partial_schedule (ps, sched_nodes);
2275 /* The scheduling window is exclusive of 'end'
2276 whereas compute_split_window() expects an inclusive,
2279 split_row = compute_split_row (sched_nodes, start, end - 1,
2282 split_row = compute_split_row (sched_nodes, end + 1, start,
2285 ps_insert_empty_row (ps, split_row, sched_nodes);
2286 i--; /* Go back and retry node i. */
2289 fprintf (dump_file, "num_splits=%d\n", num_splits);
2292 /* ??? If (success), check register pressure estimates. */
2293 } /* Continue with next node. */
2294 } /* While flush_and_start_over. */
2297 free_partial_schedule (ps);
2301 gcc_assert (bitmap_equal_p (tobe_scheduled, sched_nodes));
2303 sbitmap_free (sched_nodes);
2304 sbitmap_free (must_precede);
2305 sbitmap_free (must_follow);
2306 sbitmap_free (tobe_scheduled);
2311 /* This function inserts a new empty row into PS at the position
2312 according to SPLITROW, keeping all already scheduled instructions
2313 intact and updating their SCHED_TIME and cycle accordingly. */
2315 ps_insert_empty_row (partial_schedule_ptr ps, int split_row,
2316 sbitmap sched_nodes)
2318 ps_insn_ptr crr_insn;
2319 ps_insn_ptr *rows_new;
2321 int new_ii = ii + 1;
2323 int *rows_length_new;
2325 verify_partial_schedule (ps, sched_nodes);
2327 /* We normalize sched_time and rotate ps to have only non-negative sched
2328 times, for simplicity of updating cycles after inserting new row. */
2329 split_row -= ps->min_cycle;
2330 split_row = SMODULO (split_row, ii);
2332 fprintf (dump_file, "split_row=%d\n", split_row);
2334 reset_sched_times (ps, PS_MIN_CYCLE (ps));
2335 rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
2337 rows_new = (ps_insn_ptr *) xcalloc (new_ii, sizeof (ps_insn_ptr));
2338 rows_length_new = (int *) xcalloc (new_ii, sizeof (int));
2339 for (row = 0; row < split_row; row++)
2341 rows_new[row] = ps->rows[row];
2342 rows_length_new[row] = ps->rows_length[row];
2343 ps->rows[row] = NULL;
2344 for (crr_insn = rows_new[row];
2345 crr_insn; crr_insn = crr_insn->next_in_row)
2347 int u = crr_insn->id;
2348 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii);
2350 SCHED_TIME (u) = new_time;
2351 crr_insn->cycle = new_time;
2352 SCHED_ROW (u) = new_time % new_ii;
2353 SCHED_STAGE (u) = new_time / new_ii;
2358 rows_new[split_row] = NULL;
2360 for (row = split_row; row < ii; row++)
2362 rows_new[row + 1] = ps->rows[row];
2363 rows_length_new[row + 1] = ps->rows_length[row];
2364 ps->rows[row] = NULL;
2365 for (crr_insn = rows_new[row + 1];
2366 crr_insn; crr_insn = crr_insn->next_in_row)
2368 int u = crr_insn->id;
2369 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii) + 1;
2371 SCHED_TIME (u) = new_time;
2372 crr_insn->cycle = new_time;
2373 SCHED_ROW (u) = new_time % new_ii;
2374 SCHED_STAGE (u) = new_time / new_ii;
2379 ps->min_cycle = ps->min_cycle + ps->min_cycle / ii
2380 + (SMODULO (ps->min_cycle, ii) >= split_row ? 1 : 0);
2381 ps->max_cycle = ps->max_cycle + ps->max_cycle / ii
2382 + (SMODULO (ps->max_cycle, ii) >= split_row ? 1 : 0);
2384 ps->rows = rows_new;
2385 free (ps->rows_length);
2386 ps->rows_length = rows_length_new;
2388 gcc_assert (ps->min_cycle >= 0);
2390 verify_partial_schedule (ps, sched_nodes);
2393 fprintf (dump_file, "min_cycle=%d, max_cycle=%d\n", ps->min_cycle,
2397 /* Given U_NODE which is the node that failed to be scheduled; LOW and
2398 UP which are the boundaries of it's scheduling window; compute using
2399 SCHED_NODES and II a row in the partial schedule that can be split
2400 which will separate a critical predecessor from a critical successor
2401 thereby expanding the window, and return it. */
2403 compute_split_row (sbitmap sched_nodes, int low, int up, int ii,
2404 ddg_node_ptr u_node)
2407 int lower = INT_MIN, upper = INT_MAX;
2412 for (e = u_node->in; e != 0; e = e->next_in)
2414 int v = e->src->cuid;
2416 if (bitmap_bit_p (sched_nodes, v)
2417 && (low == SCHED_TIME (v) + e->latency - (e->distance * ii)))
2418 if (SCHED_TIME (v) > lower)
2421 lower = SCHED_TIME (v);
2427 crit_cycle = SCHED_TIME (crit_pred) + 1;
2428 return SMODULO (crit_cycle, ii);
2431 for (e = u_node->out; e != 0; e = e->next_out)
2433 int v = e->dest->cuid;
2435 if (bitmap_bit_p (sched_nodes, v)
2436 && (up == SCHED_TIME (v) - e->latency + (e->distance * ii)))
2437 if (SCHED_TIME (v) < upper)
2440 upper = SCHED_TIME (v);
2446 crit_cycle = SCHED_TIME (crit_succ);
2447 return SMODULO (crit_cycle, ii);
2451 fprintf (dump_file, "Both crit_pred and crit_succ are NULL\n");
2453 return SMODULO ((low + up + 1) / 2, ii);
2457 verify_partial_schedule (partial_schedule_ptr ps, sbitmap sched_nodes)
2460 ps_insn_ptr crr_insn;
2462 for (row = 0; row < ps->ii; row++)
2466 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
2468 int u = crr_insn->id;
2471 gcc_assert (bitmap_bit_p (sched_nodes, u));
2472 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2473 popcount (sched_nodes) == number of insns in ps. */
2474 gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
2475 gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
2478 gcc_assert (ps->rows_length[row] == length);
2483 /* This page implements the algorithm for ordering the nodes of a DDG
2484 for modulo scheduling, activated through the
2485 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2487 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2488 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
2489 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
2490 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2491 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
2492 #define DEPTH(x) (ASAP ((x)))
2494 typedef struct node_order_params * nopa;
2496 static void order_nodes_of_sccs (ddg_all_sccs_ptr, int * result);
2497 static int order_nodes_in_scc (ddg_ptr, sbitmap, sbitmap, int*, int);
2498 static nopa calculate_order_params (ddg_ptr, int, int *);
2499 static int find_max_asap (ddg_ptr, sbitmap);
2500 static int find_max_hv_min_mob (ddg_ptr, sbitmap);
2501 static int find_max_dv_min_mob (ddg_ptr, sbitmap);
2503 enum sms_direction {BOTTOMUP, TOPDOWN};
2505 struct node_order_params
2512 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2514 check_nodes_order (int *node_order, int num_nodes)
2517 sbitmap tmp = sbitmap_alloc (num_nodes);
2522 fprintf (dump_file, "SMS final nodes order: \n");
2524 for (i = 0; i < num_nodes; i++)
2526 int u = node_order[i];
2529 fprintf (dump_file, "%d ", u);
2530 gcc_assert (u < num_nodes && u >= 0 && !bitmap_bit_p (tmp, u));
2532 bitmap_set_bit (tmp, u);
2536 fprintf (dump_file, "\n");
2541 /* Order the nodes of G for scheduling and pass the result in
2542 NODE_ORDER. Also set aux.count of each node to ASAP.
2543 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2545 sms_order_nodes (ddg_ptr g, int mii, int * node_order, int *pmax_asap)
2549 ddg_all_sccs_ptr sccs = create_ddg_all_sccs (g);
2551 nopa nops = calculate_order_params (g, mii, pmax_asap);
2554 print_sccs (dump_file, sccs, g);
2556 order_nodes_of_sccs (sccs, node_order);
2558 if (sccs->num_sccs > 0)
2559 /* First SCC has the largest recurrence_length. */
2560 rec_mii = sccs->sccs[0]->recurrence_length;
2562 /* Save ASAP before destroying node_order_params. */
2563 for (i = 0; i < g->num_nodes; i++)
2565 ddg_node_ptr v = &g->nodes[i];
2566 v->aux.count = ASAP (v);
2570 free_ddg_all_sccs (sccs);
2571 check_nodes_order (node_order, g->num_nodes);
2577 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs, int * node_order)
2580 ddg_ptr g = all_sccs->ddg;
2581 int num_nodes = g->num_nodes;
2582 sbitmap prev_sccs = sbitmap_alloc (num_nodes);
2583 sbitmap on_path = sbitmap_alloc (num_nodes);
2584 sbitmap tmp = sbitmap_alloc (num_nodes);
2585 sbitmap ones = sbitmap_alloc (num_nodes);
2587 bitmap_clear (prev_sccs);
2590 /* Perform the node ordering starting from the SCC with the highest recMII.
2591 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2592 for (i = 0; i < all_sccs->num_sccs; i++)
2594 ddg_scc_ptr scc = all_sccs->sccs[i];
2596 /* Add nodes on paths from previous SCCs to the current SCC. */
2597 find_nodes_on_paths (on_path, g, prev_sccs, scc->nodes);
2598 bitmap_ior (tmp, scc->nodes, on_path);
2600 /* Add nodes on paths from the current SCC to previous SCCs. */
2601 find_nodes_on_paths (on_path, g, scc->nodes, prev_sccs);
2602 bitmap_ior (tmp, tmp, on_path);
2604 /* Remove nodes of previous SCCs from current extended SCC. */
2605 bitmap_and_compl (tmp, tmp, prev_sccs);
2607 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
2608 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2611 /* Handle the remaining nodes that do not belong to any scc. Each call
2612 to order_nodes_in_scc handles a single connected component. */
2613 while (pos < g->num_nodes)
2615 bitmap_and_compl (tmp, ones, prev_sccs);
2616 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
2618 sbitmap_free (prev_sccs);
2619 sbitmap_free (on_path);
2621 sbitmap_free (ones);
2624 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2625 static struct node_order_params *
2626 calculate_order_params (ddg_ptr g, int mii ATTRIBUTE_UNUSED, int *pmax_asap)
2630 int num_nodes = g->num_nodes;
2632 /* Allocate a place to hold ordering params for each node in the DDG. */
2633 nopa node_order_params_arr;
2635 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2636 node_order_params_arr = (nopa) xcalloc (num_nodes,
2637 sizeof (struct node_order_params));
2639 /* Set the aux pointer of each node to point to its order_params structure. */
2640 for (u = 0; u < num_nodes; u++)
2641 g->nodes[u].aux.info = &node_order_params_arr[u];
2643 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2644 calculate ASAP, ALAP, mobility, distance, and height for each node
2645 in the dependence (direct acyclic) graph. */
2647 /* We assume that the nodes in the array are in topological order. */
2650 for (u = 0; u < num_nodes; u++)
2652 ddg_node_ptr u_node = &g->nodes[u];
2655 for (e = u_node->in; e; e = e->next_in)
2656 if (e->distance == 0)
2657 ASAP (u_node) = MAX (ASAP (u_node),
2658 ASAP (e->src) + e->latency);
2659 max_asap = MAX (max_asap, ASAP (u_node));
2662 for (u = num_nodes - 1; u > -1; u--)
2664 ddg_node_ptr u_node = &g->nodes[u];
2666 ALAP (u_node) = max_asap;
2667 HEIGHT (u_node) = 0;
2668 for (e = u_node->out; e; e = e->next_out)
2669 if (e->distance == 0)
2671 ALAP (u_node) = MIN (ALAP (u_node),
2672 ALAP (e->dest) - e->latency);
2673 HEIGHT (u_node) = MAX (HEIGHT (u_node),
2674 HEIGHT (e->dest) + e->latency);
2679 fprintf (dump_file, "\nOrder params\n");
2680 for (u = 0; u < num_nodes; u++)
2682 ddg_node_ptr u_node = &g->nodes[u];
2684 fprintf (dump_file, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u,
2685 ASAP (u_node), ALAP (u_node), HEIGHT (u_node));
2689 *pmax_asap = max_asap;
2690 return node_order_params_arr;
2694 find_max_asap (ddg_ptr g, sbitmap nodes)
2699 sbitmap_iterator sbi;
2701 EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi)
2703 ddg_node_ptr u_node = &g->nodes[u];
2705 if (max_asap < ASAP (u_node))
2707 max_asap = ASAP (u_node);
2715 find_max_hv_min_mob (ddg_ptr g, sbitmap nodes)
2719 int min_mob = INT_MAX;
2721 sbitmap_iterator sbi;
2723 EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi)
2725 ddg_node_ptr u_node = &g->nodes[u];
2727 if (max_hv < HEIGHT (u_node))
2729 max_hv = HEIGHT (u_node);
2730 min_mob = MOB (u_node);
2733 else if ((max_hv == HEIGHT (u_node))
2734 && (min_mob > MOB (u_node)))
2736 min_mob = MOB (u_node);
2744 find_max_dv_min_mob (ddg_ptr g, sbitmap nodes)
2748 int min_mob = INT_MAX;
2750 sbitmap_iterator sbi;
2752 EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi)
2754 ddg_node_ptr u_node = &g->nodes[u];
2756 if (max_dv < DEPTH (u_node))
2758 max_dv = DEPTH (u_node);
2759 min_mob = MOB (u_node);
2762 else if ((max_dv == DEPTH (u_node))
2763 && (min_mob > MOB (u_node)))
2765 min_mob = MOB (u_node);
2772 /* Places the nodes of SCC into the NODE_ORDER array starting
2773 at position POS, according to the SMS ordering algorithm.
2774 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2775 the NODE_ORDER array, starting from position zero. */
2777 order_nodes_in_scc (ddg_ptr g, sbitmap nodes_ordered, sbitmap scc,
2778 int * node_order, int pos)
2780 enum sms_direction dir;
2781 int num_nodes = g->num_nodes;
2782 sbitmap workset = sbitmap_alloc (num_nodes);
2783 sbitmap tmp = sbitmap_alloc (num_nodes);
2784 sbitmap zero_bitmap = sbitmap_alloc (num_nodes);
2785 sbitmap predecessors = sbitmap_alloc (num_nodes);
2786 sbitmap successors = sbitmap_alloc (num_nodes);
2788 bitmap_clear (predecessors);
2789 find_predecessors (predecessors, g, nodes_ordered);
2791 bitmap_clear (successors);
2792 find_successors (successors, g, nodes_ordered);
2795 if (bitmap_and (tmp, predecessors, scc))
2797 bitmap_copy (workset, tmp);
2800 else if (bitmap_and (tmp, successors, scc))
2802 bitmap_copy (workset, tmp);
2809 bitmap_clear (workset);
2810 if ((u = find_max_asap (g, scc)) >= 0)
2811 bitmap_set_bit (workset, u);
2815 bitmap_clear (zero_bitmap);
2816 while (!bitmap_equal_p (workset, zero_bitmap))
2819 ddg_node_ptr v_node;
2820 sbitmap v_node_preds;
2821 sbitmap v_node_succs;
2825 while (!bitmap_equal_p (workset, zero_bitmap))
2827 v = find_max_hv_min_mob (g, workset);
2828 v_node = &g->nodes[v];
2829 node_order[pos++] = v;
2830 v_node_succs = NODE_SUCCESSORS (v_node);
2831 bitmap_and (tmp, v_node_succs, scc);
2833 /* Don't consider the already ordered successors again. */
2834 bitmap_and_compl (tmp, tmp, nodes_ordered);
2835 bitmap_ior (workset, workset, tmp);
2836 bitmap_clear_bit (workset, v);
2837 bitmap_set_bit (nodes_ordered, v);
2840 bitmap_clear (predecessors);
2841 find_predecessors (predecessors, g, nodes_ordered);
2842 bitmap_and (workset, predecessors, scc);
2846 while (!bitmap_equal_p (workset, zero_bitmap))
2848 v = find_max_dv_min_mob (g, workset);
2849 v_node = &g->nodes[v];
2850 node_order[pos++] = v;
2851 v_node_preds = NODE_PREDECESSORS (v_node);
2852 bitmap_and (tmp, v_node_preds, scc);
2854 /* Don't consider the already ordered predecessors again. */
2855 bitmap_and_compl (tmp, tmp, nodes_ordered);
2856 bitmap_ior (workset, workset, tmp);
2857 bitmap_clear_bit (workset, v);
2858 bitmap_set_bit (nodes_ordered, v);
2861 bitmap_clear (successors);
2862 find_successors (successors, g, nodes_ordered);
2863 bitmap_and (workset, successors, scc);
2867 sbitmap_free (workset);
2868 sbitmap_free (zero_bitmap);
2869 sbitmap_free (predecessors);
2870 sbitmap_free (successors);
2875 /* This page contains functions for manipulating partial-schedules during
2876 modulo scheduling. */
2878 /* Create a partial schedule and allocate a memory to hold II rows. */
2880 static partial_schedule_ptr
2881 create_partial_schedule (int ii, ddg_ptr g, int history)
2883 partial_schedule_ptr ps = XNEW (struct partial_schedule);
2884 ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
2885 ps->rows_length = (int *) xcalloc (ii, sizeof (int));
2886 ps->reg_moves.create (0);
2888 ps->history = history;
2889 ps->min_cycle = INT_MAX;
2890 ps->max_cycle = INT_MIN;
2896 /* Free the PS_INSNs in rows array of the given partial schedule.
2897 ??? Consider caching the PS_INSN's. */
2899 free_ps_insns (partial_schedule_ptr ps)
2903 for (i = 0; i < ps->ii; i++)
2907 ps_insn_ptr ps_insn = ps->rows[i]->next_in_row;
2910 ps->rows[i] = ps_insn;
2916 /* Free all the memory allocated to the partial schedule. */
2919 free_partial_schedule (partial_schedule_ptr ps)
2921 ps_reg_move_info *move;
2927 FOR_EACH_VEC_ELT (ps->reg_moves, i, move)
2928 sbitmap_free (move->uses);
2929 ps->reg_moves.release ();
2933 free (ps->rows_length);
2937 /* Clear the rows array with its PS_INSNs, and create a new one with
2941 reset_partial_schedule (partial_schedule_ptr ps, int new_ii)
2946 if (new_ii == ps->ii)
2948 ps->rows = (ps_insn_ptr *) xrealloc (ps->rows, new_ii
2949 * sizeof (ps_insn_ptr));
2950 memset (ps->rows, 0, new_ii * sizeof (ps_insn_ptr));
2951 ps->rows_length = (int *) xrealloc (ps->rows_length, new_ii * sizeof (int));
2952 memset (ps->rows_length, 0, new_ii * sizeof (int));
2954 ps->min_cycle = INT_MAX;
2955 ps->max_cycle = INT_MIN;
2958 /* Prints the partial schedule as an ii rows array, for each rows
2959 print the ids of the insns in it. */
2961 print_partial_schedule (partial_schedule_ptr ps, FILE *dump)
2965 for (i = 0; i < ps->ii; i++)
2967 ps_insn_ptr ps_i = ps->rows[i];
2969 fprintf (dump, "\n[ROW %d ]: ", i);
2972 rtx_insn *insn = ps_rtl_insn (ps, ps_i->id);
2975 fprintf (dump, "%d (branch), ", INSN_UID (insn));
2977 fprintf (dump, "%d, ", INSN_UID (insn));
2979 ps_i = ps_i->next_in_row;
2984 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2986 create_ps_insn (int id, int cycle)
2988 ps_insn_ptr ps_i = XNEW (struct ps_insn);
2991 ps_i->next_in_row = NULL;
2992 ps_i->prev_in_row = NULL;
2993 ps_i->cycle = cycle;
2999 /* Removes the given PS_INSN from the partial schedule. */
3001 remove_node_from_ps (partial_schedule_ptr ps, ps_insn_ptr ps_i)
3005 gcc_assert (ps && ps_i);
3007 row = SMODULO (ps_i->cycle, ps->ii);
3008 if (! ps_i->prev_in_row)
3010 gcc_assert (ps_i == ps->rows[row]);
3011 ps->rows[row] = ps_i->next_in_row;
3013 ps->rows[row]->prev_in_row = NULL;
3017 ps_i->prev_in_row->next_in_row = ps_i->next_in_row;
3018 if (ps_i->next_in_row)
3019 ps_i->next_in_row->prev_in_row = ps_i->prev_in_row;
3022 ps->rows_length[row] -= 1;
3027 /* Unlike what literature describes for modulo scheduling (which focuses
3028 on VLIW machines) the order of the instructions inside a cycle is
3029 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
3030 where the current instruction should go relative to the already
3031 scheduled instructions in the given cycle. Go over these
3032 instructions and find the first possible column to put it in. */
3034 ps_insn_find_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
3035 sbitmap must_precede, sbitmap must_follow)
3037 ps_insn_ptr next_ps_i;
3038 ps_insn_ptr first_must_follow = NULL;
3039 ps_insn_ptr last_must_precede = NULL;
3040 ps_insn_ptr last_in_row = NULL;
3046 row = SMODULO (ps_i->cycle, ps->ii);
3048 /* Find the first must follow and the last must precede
3049 and insert the node immediately after the must precede
3050 but make sure that it there is no must follow after it. */
3051 for (next_ps_i = ps->rows[row];
3053 next_ps_i = next_ps_i->next_in_row)
3056 && bitmap_bit_p (must_follow, next_ps_i->id)
3057 && ! first_must_follow)
3058 first_must_follow = next_ps_i;
3059 if (must_precede && bitmap_bit_p (must_precede, next_ps_i->id))
3061 /* If we have already met a node that must follow, then
3062 there is no possible column. */
3063 if (first_must_follow)
3066 last_must_precede = next_ps_i;
3068 /* The closing branch must be the last in the row. */
3070 && bitmap_bit_p (must_precede, next_ps_i->id)
3071 && JUMP_P (ps_rtl_insn (ps, next_ps_i->id)))
3074 last_in_row = next_ps_i;
3077 /* The closing branch is scheduled as well. Make sure there is no
3078 dependent instruction after it as the branch should be the last
3079 instruction in the row. */
3080 if (JUMP_P (ps_rtl_insn (ps, ps_i->id)))
3082 if (first_must_follow)
3086 /* Make the branch the last in the row. New instructions
3087 will be inserted at the beginning of the row or after the
3088 last must_precede instruction thus the branch is guaranteed
3089 to remain the last instruction in the row. */
3090 last_in_row->next_in_row = ps_i;
3091 ps_i->prev_in_row = last_in_row;
3092 ps_i->next_in_row = NULL;
3095 ps->rows[row] = ps_i;
3099 /* Now insert the node after INSERT_AFTER_PSI. */
3101 if (! last_must_precede)
3103 ps_i->next_in_row = ps->rows[row];
3104 ps_i->prev_in_row = NULL;
3105 if (ps_i->next_in_row)
3106 ps_i->next_in_row->prev_in_row = ps_i;
3107 ps->rows[row] = ps_i;
3111 ps_i->next_in_row = last_must_precede->next_in_row;
3112 last_must_precede->next_in_row = ps_i;
3113 ps_i->prev_in_row = last_must_precede;
3114 if (ps_i->next_in_row)
3115 ps_i->next_in_row->prev_in_row = ps_i;
3121 /* Advances the PS_INSN one column in its current row; returns false
3122 in failure and true in success. Bit N is set in MUST_FOLLOW if
3123 the node with cuid N must be come after the node pointed to by
3124 PS_I when scheduled in the same cycle. */
3126 ps_insn_advance_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
3127 sbitmap must_follow)
3129 ps_insn_ptr prev, next;
3135 row = SMODULO (ps_i->cycle, ps->ii);
3137 if (! ps_i->next_in_row)
3140 /* Check if next_in_row is dependent on ps_i, both having same sched
3141 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
3142 if (must_follow && bitmap_bit_p (must_follow, ps_i->next_in_row->id))
3145 /* Advance PS_I over its next_in_row in the doubly linked list. */
3146 prev = ps_i->prev_in_row;
3147 next = ps_i->next_in_row;
3149 if (ps_i == ps->rows[row])
3150 ps->rows[row] = next;
3152 ps_i->next_in_row = next->next_in_row;
3154 if (next->next_in_row)
3155 next->next_in_row->prev_in_row = ps_i;
3157 next->next_in_row = ps_i;
3158 ps_i->prev_in_row = next;
3160 next->prev_in_row = prev;
3162 prev->next_in_row = next;
3167 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
3168 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
3169 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
3170 before/after (respectively) the node pointed to by PS_I when scheduled
3171 in the same cycle. */
3173 add_node_to_ps (partial_schedule_ptr ps, int id, int cycle,
3174 sbitmap must_precede, sbitmap must_follow)
3177 int row = SMODULO (cycle, ps->ii);
3179 if (ps->rows_length[row] >= issue_rate)
3182 ps_i = create_ps_insn (id, cycle);
3184 /* Finds and inserts PS_I according to MUST_FOLLOW and
3186 if (! ps_insn_find_column (ps, ps_i, must_precede, must_follow))
3192 ps->rows_length[row] += 1;
3196 /* Advance time one cycle. Assumes DFA is being used. */
3198 advance_one_cycle (void)
3200 if (targetm.sched.dfa_pre_cycle_insn)
3201 state_transition (curr_state,
3202 targetm.sched.dfa_pre_cycle_insn ());
3204 state_transition (curr_state, NULL);
3206 if (targetm.sched.dfa_post_cycle_insn)
3207 state_transition (curr_state,
3208 targetm.sched.dfa_post_cycle_insn ());
3213 /* Checks if PS has resource conflicts according to DFA, starting from
3214 FROM cycle to TO cycle; returns true if there are conflicts and false
3215 if there are no conflicts. Assumes DFA is being used. */
3217 ps_has_conflicts (partial_schedule_ptr ps, int from, int to)
3221 state_reset (curr_state);
3223 for (cycle = from; cycle <= to; cycle++)
3225 ps_insn_ptr crr_insn;
3226 /* Holds the remaining issue slots in the current row. */
3227 int can_issue_more = issue_rate;
3229 /* Walk through the DFA for the current row. */
3230 for (crr_insn = ps->rows[SMODULO (cycle, ps->ii)];
3232 crr_insn = crr_insn->next_in_row)
3234 rtx_insn *insn = ps_rtl_insn (ps, crr_insn->id);
3236 if (!NONDEBUG_INSN_P (insn))
3239 /* Check if there is room for the current insn. */
3240 if (!can_issue_more || state_dead_lock_p (curr_state))
3243 /* Update the DFA state and return with failure if the DFA found
3244 resource conflicts. */
3245 if (state_transition (curr_state, insn) >= 0)
3248 if (targetm.sched.variable_issue)
3250 targetm.sched.variable_issue (sched_dump, sched_verbose,
3251 insn, can_issue_more);
3252 /* A naked CLOBBER or USE generates no instruction, so don't
3253 let them consume issue slots. */
3254 else if (GET_CODE (PATTERN (insn)) != USE
3255 && GET_CODE (PATTERN (insn)) != CLOBBER)
3259 /* Advance the DFA to the next cycle. */
3260 advance_one_cycle ();
3265 /* Checks if the given node causes resource conflicts when added to PS at
3266 cycle C. If not the node is added to PS and returned; otherwise zero
3267 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
3268 cuid N must be come before/after (respectively) the node pointed to by
3269 PS_I when scheduled in the same cycle. */
3271 ps_add_node_check_conflicts (partial_schedule_ptr ps, int n,
3272 int c, sbitmap must_precede,
3273 sbitmap must_follow)
3275 int has_conflicts = 0;
3278 /* First add the node to the PS, if this succeeds check for
3279 conflicts, trying different issue slots in the same row. */
3280 if (! (ps_i = add_node_to_ps (ps, n, c, must_precede, must_follow)))
3281 return NULL; /* Failed to insert the node at the given cycle. */
3283 has_conflicts = ps_has_conflicts (ps, c, c)
3285 && ps_has_conflicts (ps,
3289 /* Try different issue slots to find one that the given node can be
3290 scheduled in without conflicts. */
3291 while (has_conflicts)
3293 if (! ps_insn_advance_column (ps, ps_i, must_follow))
3295 has_conflicts = ps_has_conflicts (ps, c, c)
3297 && ps_has_conflicts (ps,
3304 remove_node_from_ps (ps, ps_i);
3308 ps->min_cycle = MIN (ps->min_cycle, c);
3309 ps->max_cycle = MAX (ps->max_cycle, c);
3313 /* Calculate the stage count of the partial schedule PS. The calculation
3314 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3316 calculate_stage_count (partial_schedule_ptr ps, int rotation_amount)
3318 int new_min_cycle = PS_MIN_CYCLE (ps) - rotation_amount;
3319 int new_max_cycle = PS_MAX_CYCLE (ps) - rotation_amount;
3320 int stage_count = CALC_STAGE_COUNT (-1, new_min_cycle, ps->ii);
3322 /* The calculation of stage count is done adding the number of stages
3323 before cycle zero and after cycle zero. */
3324 stage_count += CALC_STAGE_COUNT (new_max_cycle, 0, ps->ii);
3329 /* Rotate the rows of PS such that insns scheduled at time
3330 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3332 rotate_partial_schedule (partial_schedule_ptr ps, int start_cycle)
3334 int i, row, backward_rotates;
3335 int last_row = ps->ii - 1;
3337 if (start_cycle == 0)
3340 backward_rotates = SMODULO (start_cycle, ps->ii);
3342 /* Revisit later and optimize this into a single loop. */
3343 for (i = 0; i < backward_rotates; i++)
3345 ps_insn_ptr first_row = ps->rows[0];
3346 int first_row_length = ps->rows_length[0];
3348 for (row = 0; row < last_row; row++)
3350 ps->rows[row] = ps->rows[row + 1];
3351 ps->rows_length[row] = ps->rows_length[row + 1];
3354 ps->rows[last_row] = first_row;
3355 ps->rows_length[last_row] = first_row_length;
3358 ps->max_cycle -= start_cycle;
3359 ps->min_cycle -= start_cycle;
3362 #endif /* INSN_SCHEDULING */
3364 /* Run instruction scheduler. */
3365 /* Perform SMS module scheduling. */
3369 const pass_data pass_data_sms =
3371 RTL_PASS, /* type */
3373 OPTGROUP_NONE, /* optinfo_flags */
3375 0, /* properties_required */
3376 0, /* properties_provided */
3377 0, /* properties_destroyed */
3378 0, /* todo_flags_start */
3379 TODO_df_finish, /* todo_flags_finish */
3382 class pass_sms : public rtl_opt_pass
3385 pass_sms (gcc::context *ctxt)
3386 : rtl_opt_pass (pass_data_sms, ctxt)
3389 /* opt_pass methods: */
3390 virtual bool gate (function *)
3392 return (optimize > 0 && flag_modulo_sched);
3395 virtual unsigned int execute (function *);
3397 }; // class pass_sms
3400 pass_sms::execute (function *fun ATTRIBUTE_UNUSED)
3402 #ifdef INSN_SCHEDULING
3405 /* Collect loop information to be used in SMS. */
3406 cfg_layout_initialize (0);
3409 /* Update the life information, because we add pseudos. */
3410 max_regno = max_reg_num ();
3412 /* Finalize layout changes. */
3413 FOR_EACH_BB_FN (bb, fun)
3414 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3415 bb->aux = bb->next_bb;
3416 free_dominance_info (CDI_DOMINATORS);
3417 cfg_layout_finalize ();
3418 #endif /* INSN_SCHEDULING */
3425 make_pass_sms (gcc::context *ctxt)
3427 return new pass_sms (ctxt);