1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
27 #include "diagnostic-core.h"
30 #include "hard-reg-set.h"
34 #include "insn-config.h"
35 #include "insn-attr.h"
38 #include "sched-int.h"
40 #include "cfglayout.h"
48 #include "tree-pass.h"
52 #ifdef INSN_SCHEDULING
54 /* This file contains the implementation of the Swing Modulo Scheduler,
55 described in the following references:
56 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
57 Lifetime--sensitive modulo scheduling in a production environment.
58 IEEE Trans. on Comps., 50(3), March 2001
59 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
60 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
61 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
63 The basic structure is:
64 1. Build a data-dependence graph (DDG) for each loop.
65 2. Use the DDG to order the insns of a loop (not in topological order
66 necessarily, but rather) trying to place each insn after all its
67 predecessors _or_ after all its successors.
68 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
69 4. Use the ordering to perform list-scheduling of the loop:
70 1. Set II = MII. We will try to schedule the loop within II cycles.
71 2. Try to schedule the insns one by one according to the ordering.
72 For each insn compute an interval of cycles by considering already-
73 scheduled preds and succs (and associated latencies); try to place
74 the insn in the cycles of this window checking for potential
75 resource conflicts (using the DFA interface).
76 Note: this is different from the cycle-scheduling of schedule_insns;
77 here the insns are not scheduled monotonically top-down (nor bottom-
79 3. If failed in scheduling all insns - bump II++ and try again, unless
80 II reaches an upper bound MaxII, in which case report failure.
81 5. If we succeeded in scheduling the loop within II cycles, we now
82 generate prolog and epilog, decrease the counter of the loop, and
83 perform modulo variable expansion for live ranges that span more than
84 II cycles (i.e. use register copies to prevent a def from overwriting
85 itself before reaching the use).
87 SMS works with countable loops (1) whose control part can be easily
88 decoupled from the rest of the loop and (2) whose loop count can
89 be easily adjusted. This is because we peel a constant number of
90 iterations into a prologue and epilogue for which we want to avoid
91 emitting the control part, and a kernel which is to iterate that
92 constant number of iterations less than the original loop. So the
93 control part should be a set of insns clearly identified and having
94 its own iv, not otherwise used in the loop (at-least for now), which
95 initializes a register before the loop to the number of iterations.
96 Currently SMS relies on the do-loop pattern to recognize such loops,
97 where (1) the control part comprises of all insns defining and/or
98 using a certain 'count' register and (2) the loop count can be
99 adjusted by modifying this register prior to the loop.
100 TODO: Rely on cfgloop analysis instead. */
102 /* This page defines partial-schedule structures and functions for
103 modulo scheduling. */
105 typedef struct partial_schedule *partial_schedule_ptr;
106 typedef struct ps_insn *ps_insn_ptr;
108 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
109 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
111 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
112 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
114 /* Perform signed modulo, always returning a non-negative value. */
115 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
117 /* The number of different iterations the nodes in ps span, assuming
118 the stage boundaries are placed efficiently. */
119 #define CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \
121 /* The stage count of ps. */
122 #define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count)
124 /* A single instruction in the partial schedule. */
127 /* The corresponding DDG_NODE. */
130 /* The (absolute) cycle in which the PS instruction is scheduled.
131 Same as SCHED_TIME (node). */
134 /* The next/prev PS_INSN in the same row. */
135 ps_insn_ptr next_in_row,
140 /* Holds the partial schedule as an array of II rows. Each entry of the
141 array points to a linked list of PS_INSNs, which represents the
142 instructions that are scheduled for that row. */
143 struct partial_schedule
145 int ii; /* Number of rows in the partial schedule. */
146 int history; /* Threshold for conflict checking using DFA. */
148 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
151 /* rows_length[i] holds the number of instructions in the row.
152 It is used only (as an optimization) to back off quickly from
153 trying to schedule a node in a full row; that is, to avoid running
154 through futile DFA state transitions. */
157 /* The earliest absolute cycle of an insn in the partial schedule. */
160 /* The latest absolute cycle of an insn in the partial schedule. */
163 ddg_ptr g; /* The DDG of the insns in the partial schedule. */
165 int stage_count; /* The stage count of the partial schedule. */
169 static partial_schedule_ptr create_partial_schedule (int ii, ddg_ptr, int history);
170 static void free_partial_schedule (partial_schedule_ptr);
171 static void reset_partial_schedule (partial_schedule_ptr, int new_ii);
172 void print_partial_schedule (partial_schedule_ptr, FILE *);
173 static void verify_partial_schedule (partial_schedule_ptr, sbitmap);
174 static ps_insn_ptr ps_add_node_check_conflicts (partial_schedule_ptr,
175 ddg_node_ptr node, int cycle,
176 sbitmap must_precede,
177 sbitmap must_follow);
178 static void rotate_partial_schedule (partial_schedule_ptr, int);
179 void set_row_column_for_ps (partial_schedule_ptr);
180 static void ps_insert_empty_row (partial_schedule_ptr, int, sbitmap);
181 static int compute_split_row (sbitmap, int, int, int, ddg_node_ptr);
184 /* This page defines constants and structures for the modulo scheduling
187 static int sms_order_nodes (ddg_ptr, int, int *, int *);
188 static void set_node_sched_params (ddg_ptr);
189 static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int, int *);
190 static void permute_partial_schedule (partial_schedule_ptr, rtx);
191 static void generate_prolog_epilog (partial_schedule_ptr, struct loop *,
193 static void duplicate_insns_of_cycles (partial_schedule_ptr,
195 static int calculate_stage_count (partial_schedule_ptr, int);
196 static void calculate_must_precede_follow (ddg_node_ptr, int, int,
197 int, int, sbitmap, sbitmap, sbitmap);
198 static int get_sched_window (partial_schedule_ptr, ddg_node_ptr,
199 sbitmap, int, int *, int *, int *);
200 static bool try_scheduling_node_in_cycle (partial_schedule_ptr, ddg_node_ptr,
201 int, int, sbitmap, int *, sbitmap,
203 static void remove_node_from_ps (partial_schedule_ptr, ps_insn_ptr);
205 #define SCHED_ASAP(x) (((node_sched_params_ptr)(x)->aux.info)->asap)
206 #define SCHED_TIME(x) (((node_sched_params_ptr)(x)->aux.info)->time)
207 #define SCHED_FIRST_REG_MOVE(x) \
208 (((node_sched_params_ptr)(x)->aux.info)->first_reg_move)
209 #define SCHED_NREG_MOVES(x) \
210 (((node_sched_params_ptr)(x)->aux.info)->nreg_moves)
211 #define SCHED_ROW(x) (((node_sched_params_ptr)(x)->aux.info)->row)
212 #define SCHED_STAGE(x) (((node_sched_params_ptr)(x)->aux.info)->stage)
213 #define SCHED_COLUMN(x) (((node_sched_params_ptr)(x)->aux.info)->column)
215 /* The scheduling parameters held for each node. */
216 typedef struct node_sched_params
218 int asap; /* A lower-bound on the absolute scheduling cycle. */
219 int time; /* The absolute scheduling cycle (time >= asap). */
221 /* The following field (first_reg_move) is a pointer to the first
222 register-move instruction added to handle the modulo-variable-expansion
223 of the register defined by this node. This register-move copies the
224 original register defined by the node. */
227 /* The number of register-move instructions added, immediately preceding
231 int row; /* Holds time % ii. */
232 int stage; /* Holds time / ii. */
234 /* The column of a node inside the ps. If nodes u, v are on the same row,
235 u will precede v if column (u) < column (v). */
237 } *node_sched_params_ptr;
240 /* The following three functions are copied from the current scheduler
241 code in order to use sched_analyze() for computing the dependencies.
242 They are used when initializing the sched_info structure. */
244 sms_print_insn (const_rtx insn, int aligned ATTRIBUTE_UNUSED)
248 sprintf (tmp, "i%4d", INSN_UID (insn));
253 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
254 regset used ATTRIBUTE_UNUSED)
258 static struct common_sched_info_def sms_common_sched_info;
260 static struct sched_deps_info_def sms_sched_deps_info =
262 compute_jump_reg_dependencies,
263 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
268 static struct haifa_sched_info sms_sched_info =
277 NULL, /* insn_finishes_block_p */
282 NULL, NULL, NULL, NULL,
287 /* Given HEAD and TAIL which are the first and last insns in a loop;
288 return the register which controls the loop. Return zero if it has
289 more than one occurrence in the loop besides the control part or the
290 do-loop pattern is not of the form we expect. */
292 doloop_register_get (rtx head ATTRIBUTE_UNUSED, rtx tail ATTRIBUTE_UNUSED)
294 #ifdef HAVE_doloop_end
295 rtx reg, condition, insn, first_insn_not_to_check;
300 /* TODO: Free SMS's dependence on doloop_condition_get. */
301 condition = doloop_condition_get (tail);
305 if (REG_P (XEXP (condition, 0)))
306 reg = XEXP (condition, 0);
307 else if (GET_CODE (XEXP (condition, 0)) == PLUS
308 && REG_P (XEXP (XEXP (condition, 0), 0)))
309 reg = XEXP (XEXP (condition, 0), 0);
313 /* Check that the COUNT_REG has no other occurrences in the loop
314 until the decrement. We assume the control part consists of
315 either a single (parallel) branch-on-count or a (non-parallel)
316 branch immediately preceded by a single (decrement) insn. */
317 first_insn_not_to_check = (GET_CODE (PATTERN (tail)) == PARALLEL ? tail
318 : prev_nondebug_insn (tail));
320 for (insn = head; insn != first_insn_not_to_check; insn = NEXT_INSN (insn))
321 if (!DEBUG_INSN_P (insn) && reg_mentioned_p (reg, insn))
325 fprintf (dump_file, "SMS count_reg found ");
326 print_rtl_single (dump_file, reg);
327 fprintf (dump_file, " outside control in insn:\n");
328 print_rtl_single (dump_file, insn);
340 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
341 that the number of iterations is a compile-time constant. If so,
342 return the rtx that sets COUNT_REG to a constant, and set COUNT to
343 this constant. Otherwise return 0. */
345 const_iteration_count (rtx count_reg, basic_block pre_header,
346 HOST_WIDEST_INT * count)
354 get_ebb_head_tail (pre_header, pre_header, &head, &tail);
356 for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn))
357 if (NONDEBUG_INSN_P (insn) && single_set (insn) &&
358 rtx_equal_p (count_reg, SET_DEST (single_set (insn))))
360 rtx pat = single_set (insn);
362 if (CONST_INT_P (SET_SRC (pat)))
364 *count = INTVAL (SET_SRC (pat));
374 /* A very simple resource-based lower bound on the initiation interval.
375 ??? Improve the accuracy of this bound by considering the
376 utilization of various units. */
380 if (targetm.sched.sms_res_mii)
381 return targetm.sched.sms_res_mii (g);
383 return ((g->num_nodes - g->num_debug) / issue_rate);
387 /* Points to the array that contains the sched data for each node. */
388 static node_sched_params_ptr node_sched_params;
390 /* Allocate sched_params for each node and initialize it. Assumes that
391 the aux field of each node contain the asap bound (computed earlier),
392 and copies it into the sched_params field. */
394 set_node_sched_params (ddg_ptr g)
398 /* Allocate for each node in the DDG a place to hold the "sched_data". */
399 /* Initialize ASAP/ALAP/HIGHT to zero. */
400 node_sched_params = (node_sched_params_ptr)
401 xcalloc (g->num_nodes,
402 sizeof (struct node_sched_params));
404 /* Set the pointer of the general data of the node to point to the
405 appropriate sched_params structure. */
406 for (i = 0; i < g->num_nodes; i++)
408 /* Watch out for aliasing problems? */
409 node_sched_params[i].asap = g->nodes[i].aux.count;
410 g->nodes[i].aux.info = &node_sched_params[i];
415 print_node_sched_params (FILE *file, int num_nodes, ddg_ptr g)
421 for (i = 0; i < num_nodes; i++)
423 node_sched_params_ptr nsp = &node_sched_params[i];
424 rtx reg_move = nsp->first_reg_move;
427 fprintf (file, "Node = %d; INSN = %d\n", i,
428 (INSN_UID (g->nodes[i].insn)));
429 fprintf (file, " asap = %d:\n", nsp->asap);
430 fprintf (file, " time = %d:\n", nsp->time);
431 fprintf (file, " nreg_moves = %d:\n", nsp->nreg_moves);
432 for (j = 0; j < nsp->nreg_moves; j++)
434 fprintf (file, " reg_move = ");
435 print_rtl_single (file, reg_move);
436 reg_move = PREV_INSN (reg_move);
442 Breaking intra-loop register anti-dependences:
443 Each intra-loop register anti-dependence implies a cross-iteration true
444 dependence of distance 1. Therefore, we can remove such false dependencies
445 and figure out if the partial schedule broke them by checking if (for a
446 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
447 if so generate a register move. The number of such moves is equal to:
448 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
449 nreg_moves = ----------------------------------- + 1 - { dependence.
453 generate_reg_moves (partial_schedule_ptr ps, bool rescan)
459 for (i = 0; i < g->num_nodes; i++)
461 ddg_node_ptr u = &g->nodes[i];
463 int nreg_moves = 0, i_reg_move;
464 sbitmap *uses_of_defs;
466 rtx prev_reg, old_reg;
467 rtx set = single_set (u->insn);
469 /* Skip instructions that do not set a register. */
470 if ((set && !REG_P (SET_DEST (set))))
473 /* Compute the number of reg_moves needed for u, by looking at life
474 ranges started at u (excluding self-loops). */
475 for (e = u->out; e; e = e->next_out)
476 if (e->type == TRUE_DEP && e->dest != e->src)
478 int nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
480 if (e->distance == 1)
481 nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
483 /* If dest precedes src in the schedule of the kernel, then dest
484 will read before src writes and we can save one reg_copy. */
485 if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)
486 && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))
489 if (nreg_moves4e >= 1)
491 /* !single_set instructions are not supported yet and
492 thus we do not except to encounter them in the loop
493 except from the doloop part. For the latter case
494 we assume no regmoves are generated as the doloop
495 instructions are tied to the branch with an edge. */
497 /* If the instruction contains auto-inc register then
498 validate that the regmov is being generated for the
499 target regsiter rather then the inc'ed register. */
500 gcc_assert (!autoinc_var_is_used_p (u->insn, e->dest->insn));
503 nreg_moves = MAX (nreg_moves, nreg_moves4e);
509 /* Every use of the register defined by node may require a different
510 copy of this register, depending on the time the use is scheduled.
511 Set a bitmap vector, telling which nodes use each copy of this
513 uses_of_defs = sbitmap_vector_alloc (nreg_moves, g->num_nodes);
514 sbitmap_vector_zero (uses_of_defs, nreg_moves);
515 for (e = u->out; e; e = e->next_out)
516 if (e->type == TRUE_DEP && e->dest != e->src)
518 int dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
520 if (e->distance == 1)
521 dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
523 if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)
524 && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))
528 SET_BIT (uses_of_defs[dest_copy - 1], e->dest->cuid);
531 /* Now generate the reg_moves, attaching relevant uses to them. */
532 SCHED_NREG_MOVES (u) = nreg_moves;
533 old_reg = prev_reg = copy_rtx (SET_DEST (single_set (u->insn)));
534 /* Insert the reg-moves right before the notes which precede
535 the insn they relates to. */
536 last_reg_move = u->first_note;
538 for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
540 unsigned int i_use = 0;
541 rtx new_reg = gen_reg_rtx (GET_MODE (prev_reg));
542 rtx reg_move = gen_move_insn (new_reg, prev_reg);
543 sbitmap_iterator sbi;
545 add_insn_before (reg_move, last_reg_move, NULL);
546 last_reg_move = reg_move;
548 if (!SCHED_FIRST_REG_MOVE (u))
549 SCHED_FIRST_REG_MOVE (u) = reg_move;
551 EXECUTE_IF_SET_IN_SBITMAP (uses_of_defs[i_reg_move], 0, i_use, sbi)
553 replace_rtx (g->nodes[i_use].insn, old_reg, new_reg);
555 df_insn_rescan (g->nodes[i_use].insn);
560 sbitmap_vector_free (uses_of_defs);
564 /* Update the sched_params (time, row and stage) for node U using the II,
565 the CYCLE of U and MIN_CYCLE.
566 We're not simply taking the following
567 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
568 because the stages may not be aligned on cycle 0. */
570 update_node_sched_params (ddg_node_ptr u, int ii, int cycle, int min_cycle)
572 int sc_until_cycle_zero;
575 SCHED_TIME (u) = cycle;
576 SCHED_ROW (u) = SMODULO (cycle, ii);
578 /* The calculation of stage count is done adding the number
579 of stages before cycle zero and after cycle zero. */
580 sc_until_cycle_zero = CALC_STAGE_COUNT (-1, min_cycle, ii);
582 if (SCHED_TIME (u) < 0)
584 stage = CALC_STAGE_COUNT (-1, SCHED_TIME (u), ii);
585 SCHED_STAGE (u) = sc_until_cycle_zero - stage;
589 stage = CALC_STAGE_COUNT (SCHED_TIME (u), 0, ii);
590 SCHED_STAGE (u) = sc_until_cycle_zero + stage - 1;
594 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
595 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
596 will move to cycle zero. */
598 reset_sched_times (partial_schedule_ptr ps, int amount)
602 ps_insn_ptr crr_insn;
604 for (row = 0; row < ii; row++)
605 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
607 ddg_node_ptr u = crr_insn->node;
608 int normalized_time = SCHED_TIME (u) - amount;
609 int new_min_cycle = PS_MIN_CYCLE (ps) - amount;
613 /* Print the scheduling times after the rotation. */
614 fprintf (dump_file, "crr_insn->node=%d (insn id %d), "
615 "crr_insn->cycle=%d, min_cycle=%d", crr_insn->node->cuid,
616 INSN_UID (crr_insn->node->insn), normalized_time,
618 if (JUMP_P (crr_insn->node->insn))
619 fprintf (dump_file, " (branch)");
620 fprintf (dump_file, "\n");
623 gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
624 gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
626 crr_insn->cycle = normalized_time;
627 update_node_sched_params (u, ii, normalized_time, new_min_cycle);
631 /* Set SCHED_COLUMN of each node according to its position in PS. */
633 set_columns_for_ps (partial_schedule_ptr ps)
637 for (row = 0; row < ps->ii; row++)
639 ps_insn_ptr cur_insn = ps->rows[row];
642 for (; cur_insn; cur_insn = cur_insn->next_in_row)
643 SCHED_COLUMN (cur_insn->node) = column++;
647 /* Permute the insns according to their order in PS, from row 0 to
648 row ii-1, and position them right before LAST. This schedules
649 the insns of the loop kernel. */
651 permute_partial_schedule (partial_schedule_ptr ps, rtx last)
657 for (row = 0; row < ii ; row++)
658 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
659 if (PREV_INSN (last) != ps_ij->node->insn)
660 reorder_insns_nobb (ps_ij->node->first_note, ps_ij->node->insn,
664 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
665 respectively only if cycle C falls on the border of the scheduling
666 window boundaries marked by START and END cycles. STEP is the
667 direction of the window. */
669 set_must_precede_follow (sbitmap *tmp_follow, sbitmap must_follow,
670 sbitmap *tmp_precede, sbitmap must_precede, int c,
671 int start, int end, int step)
679 *tmp_precede = must_precede;
680 else /* step == -1. */
681 *tmp_follow = must_follow;
686 *tmp_follow = must_follow;
687 else /* step == -1. */
688 *tmp_precede = must_precede;
693 /* Return True if the branch can be moved to row ii-1 while
694 normalizing the partial schedule PS to start from cycle zero and thus
695 optimize the SC. Otherwise return False. */
697 optimize_sc (partial_schedule_ptr ps, ddg_ptr g)
699 int amount = PS_MIN_CYCLE (ps);
700 sbitmap sched_nodes = sbitmap_alloc (g->num_nodes);
701 int start, end, step;
704 int stage_count, stage_count_curr;
706 /* Compare the SC after normalization and SC after bringing the branch
707 to row ii-1. If they are equal just bail out. */
708 stage_count = calculate_stage_count (ps, amount);
710 calculate_stage_count (ps, SCHED_TIME (g->closing_branch) - (ii - 1));
712 if (stage_count == stage_count_curr)
715 fprintf (dump_file, "SMS SC already optimized.\n");
723 fprintf (dump_file, "SMS Trying to optimize branch location\n");
724 fprintf (dump_file, "SMS partial schedule before trial:\n");
725 print_partial_schedule (ps, dump_file);
728 /* First, normalize the partial scheduling. */
729 reset_sched_times (ps, amount);
730 rotate_partial_schedule (ps, amount);
734 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
736 print_partial_schedule (ps, dump_file);
739 if (SMODULO (SCHED_TIME (g->closing_branch), ii) == ii - 1)
745 sbitmap_ones (sched_nodes);
747 /* Calculate the new placement of the branch. It should be in row
748 ii-1 and fall into it's scheduling window. */
749 if (get_sched_window (ps, g->closing_branch, sched_nodes, ii, &start,
753 ps_insn_ptr next_ps_i;
754 int branch_cycle = SCHED_TIME (g->closing_branch);
755 int row = SMODULO (branch_cycle, ps->ii);
757 sbitmap must_precede, must_follow, tmp_precede, tmp_follow;
761 fprintf (dump_file, "\nTrying to schedule node %d "
762 "INSN = %d in (%d .. %d) step %d\n",
763 g->closing_branch->cuid,
764 (INSN_UID (g->closing_branch->insn)), start, end, step);
766 gcc_assert ((step > 0 && start < end) || (step < 0 && start > end));
769 c = start + ii - SMODULO (start, ii) - 1;
770 gcc_assert (c >= start);
776 "SMS failed to schedule branch at cycle: %d\n", c);
782 c = start - SMODULO (start, ii) - 1;
783 gcc_assert (c <= start);
789 "SMS failed to schedule branch at cycle: %d\n", c);
795 must_precede = sbitmap_alloc (g->num_nodes);
796 must_follow = sbitmap_alloc (g->num_nodes);
798 /* Try to schedule the branch is it's new cycle. */
799 calculate_must_precede_follow (g->closing_branch, start, end,
800 step, ii, sched_nodes,
801 must_precede, must_follow);
803 set_must_precede_follow (&tmp_follow, must_follow, &tmp_precede,
804 must_precede, c, start, end, step);
806 /* Find the element in the partial schedule related to the closing
807 branch so we can remove it from it's current cycle. */
808 for (next_ps_i = ps->rows[row];
809 next_ps_i; next_ps_i = next_ps_i->next_in_row)
810 if (next_ps_i->node->cuid == g->closing_branch->cuid)
813 remove_node_from_ps (ps, next_ps_i);
815 try_scheduling_node_in_cycle (ps, g->closing_branch,
816 g->closing_branch->cuid, c,
817 sched_nodes, &num_splits,
818 tmp_precede, tmp_follow);
819 gcc_assert (num_splits == 0);
824 "SMS failed to schedule branch at cycle: %d, "
825 "bringing it back to cycle %d\n", c, branch_cycle);
827 /* The branch was failed to be placed in row ii - 1.
828 Put it back in it's original place in the partial
830 set_must_precede_follow (&tmp_follow, must_follow, &tmp_precede,
831 must_precede, branch_cycle, start, end,
834 try_scheduling_node_in_cycle (ps, g->closing_branch,
835 g->closing_branch->cuid,
836 branch_cycle, sched_nodes,
837 &num_splits, tmp_precede,
839 gcc_assert (success && (num_splits == 0));
844 /* The branch is placed in row ii - 1. */
847 "SMS success in moving branch to cycle %d\n", c);
849 update_node_sched_params (g->closing_branch, ii, c,
864 duplicate_insns_of_cycles (partial_schedule_ptr ps, int from_stage,
865 int to_stage, int for_prolog, rtx count_reg)
870 for (row = 0; row < ps->ii; row++)
871 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
873 ddg_node_ptr u_node = ps_ij->node;
875 rtx reg_move = NULL_RTX;
877 /* Do not duplicate any insn which refers to count_reg as it
878 belongs to the control part.
879 The closing branch is scheduled as well and thus should
881 TODO: This should be done by analyzing the control part of
883 if (reg_mentioned_p (count_reg, u_node->insn)
884 || JUMP_P (ps_ij->node->insn))
889 /* SCHED_STAGE (u_node) >= from_stage == 0. Generate increasing
890 number of reg_moves starting with the second occurrence of
891 u_node, which is generated if its SCHED_STAGE <= to_stage. */
892 i_reg_moves = to_stage - SCHED_STAGE (u_node) + 1;
893 i_reg_moves = MAX (i_reg_moves, 0);
894 i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));
896 /* The reg_moves start from the *first* reg_move backwards. */
899 reg_move = SCHED_FIRST_REG_MOVE (u_node);
900 for (j = 1; j < i_reg_moves; j++)
901 reg_move = PREV_INSN (reg_move);
904 else /* It's for the epilog. */
906 /* SCHED_STAGE (u_node) <= to_stage. Generate all reg_moves,
907 starting to decrease one stage after u_node no longer occurs;
908 that is, generate all reg_moves until
909 SCHED_STAGE (u_node) == from_stage - 1. */
910 i_reg_moves = SCHED_NREG_MOVES (u_node)
911 - (from_stage - SCHED_STAGE (u_node) - 1);
912 i_reg_moves = MAX (i_reg_moves, 0);
913 i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));
915 /* The reg_moves start from the *last* reg_move forwards. */
918 reg_move = SCHED_FIRST_REG_MOVE (u_node);
919 for (j = 1; j < SCHED_NREG_MOVES (u_node); j++)
920 reg_move = PREV_INSN (reg_move);
924 for (j = 0; j < i_reg_moves; j++, reg_move = NEXT_INSN (reg_move))
925 emit_insn (copy_rtx (PATTERN (reg_move)));
926 if (SCHED_STAGE (u_node) >= from_stage
927 && SCHED_STAGE (u_node) <= to_stage)
928 duplicate_insn_chain (u_node->first_note, u_node->insn);
933 /* Generate the instructions (including reg_moves) for prolog & epilog. */
935 generate_prolog_epilog (partial_schedule_ptr ps, struct loop *loop,
936 rtx count_reg, rtx count_init)
939 int last_stage = PS_STAGE_COUNT (ps) - 1;
942 /* Generate the prolog, inserting its insns on the loop-entry edge. */
947 /* Generate instructions at the beginning of the prolog to
948 adjust the loop count by STAGE_COUNT. If loop count is constant
949 (count_init), this constant is adjusted by STAGE_COUNT in
950 generate_prolog_epilog function. */
951 rtx sub_reg = NULL_RTX;
953 sub_reg = expand_simple_binop (GET_MODE (count_reg), MINUS,
954 count_reg, GEN_INT (last_stage),
955 count_reg, 1, OPTAB_DIRECT);
956 gcc_assert (REG_P (sub_reg));
957 if (REGNO (sub_reg) != REGNO (count_reg))
958 emit_move_insn (count_reg, sub_reg);
961 for (i = 0; i < last_stage; i++)
962 duplicate_insns_of_cycles (ps, 0, i, 1, count_reg);
964 /* Put the prolog on the entry edge. */
965 e = loop_preheader_edge (loop);
966 split_edge_and_insert (e, get_insns ());
970 /* Generate the epilog, inserting its insns on the loop-exit edge. */
973 for (i = 0; i < last_stage; i++)
974 duplicate_insns_of_cycles (ps, i + 1, last_stage, 0, count_reg);
976 /* Put the epilogue on the exit edge. */
977 gcc_assert (single_exit (loop));
978 e = single_exit (loop);
979 split_edge_and_insert (e, get_insns ());
983 /* Return true if all the BBs of the loop are empty except the
986 loop_single_full_bb_p (struct loop *loop)
989 basic_block *bbs = get_loop_body (loop);
991 for (i = 0; i < loop->num_nodes ; i++)
994 bool empty_bb = true;
996 if (bbs[i] == loop->header)
999 /* Make sure that basic blocks other than the header
1000 have only notes labels or jumps. */
1001 get_ebb_head_tail (bbs[i], bbs[i], &head, &tail);
1002 for (; head != NEXT_INSN (tail); head = NEXT_INSN (head))
1004 if (NOTE_P (head) || LABEL_P (head)
1005 || (INSN_P (head) && (DEBUG_INSN_P (head) || JUMP_P (head))))
1021 /* A simple loop from SMS point of view; it is a loop that is composed of
1022 either a single basic block or two BBs - a header and a latch. */
1023 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1024 && (EDGE_COUNT (loop->latch->preds) == 1) \
1025 && (EDGE_COUNT (loop->latch->succs) == 1))
1027 /* Return true if the loop is in its canonical form and false if not.
1028 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1030 loop_canon_p (struct loop *loop)
1033 if (loop->inner || !loop_outer (loop))
1036 fprintf (dump_file, "SMS loop inner or !loop_outer\n");
1040 if (!single_exit (loop))
1044 rtx insn = BB_END (loop->header);
1046 fprintf (dump_file, "SMS loop many exits ");
1047 fprintf (dump_file, " %s %d (file, line)\n",
1048 insn_file (insn), insn_line (insn));
1053 if (! SIMPLE_SMS_LOOP_P (loop) && ! loop_single_full_bb_p (loop))
1057 rtx insn = BB_END (loop->header);
1059 fprintf (dump_file, "SMS loop many BBs. ");
1060 fprintf (dump_file, " %s %d (file, line)\n",
1061 insn_file (insn), insn_line (insn));
1069 /* If there are more than one entry for the loop,
1070 make it one by splitting the first entry edge and
1071 redirecting the others to the new BB. */
1073 canon_loop (struct loop *loop)
1078 /* Avoid annoying special cases of edges going to exit
1080 FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR->preds)
1081 if ((e->flags & EDGE_FALLTHRU) && (EDGE_COUNT (e->src->succs) > 1))
1084 if (loop->latch == loop->header
1085 || EDGE_COUNT (loop->latch->succs) > 1)
1087 FOR_EACH_EDGE (e, i, loop->header->preds)
1088 if (e->src == loop->latch)
1096 setup_sched_infos (void)
1098 memcpy (&sms_common_sched_info, &haifa_common_sched_info,
1099 sizeof (sms_common_sched_info));
1100 sms_common_sched_info.sched_pass_id = SCHED_SMS_PASS;
1101 common_sched_info = &sms_common_sched_info;
1103 sched_deps_info = &sms_sched_deps_info;
1104 current_sched_info = &sms_sched_info;
1107 /* Probability in % that the sms-ed loop rolls enough so that optimized
1108 version may be entered. Just a guess. */
1109 #define PROB_SMS_ENOUGH_ITERATIONS 80
1111 /* Used to calculate the upper bound of ii. */
1112 #define MAXII_FACTOR 2
1114 /* Main entry point, perform SMS scheduling on the loops of the function
1115 that consist of single basic blocks. */
1122 int maxii, max_asap;
1124 partial_schedule_ptr ps;
1125 basic_block bb = NULL;
1127 basic_block condition_bb = NULL;
1129 gcov_type trip_count = 0;
1131 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1132 | LOOPS_HAVE_RECORDED_EXITS);
1133 if (number_of_loops () <= 1)
1135 loop_optimizer_finalize ();
1136 return; /* There are no loops to schedule. */
1139 /* Initialize issue_rate. */
1140 if (targetm.sched.issue_rate)
1142 int temp = reload_completed;
1144 reload_completed = 1;
1145 issue_rate = targetm.sched.issue_rate ();
1146 reload_completed = temp;
1151 /* Initialize the scheduler. */
1152 setup_sched_infos ();
1153 haifa_sched_init ();
1155 /* Allocate memory to hold the DDG array one entry for each loop.
1156 We use loop->num as index into this array. */
1157 g_arr = XCNEWVEC (ddg_ptr, number_of_loops ());
1161 fprintf (dump_file, "\n\nSMS analysis phase\n");
1162 fprintf (dump_file, "===================\n\n");
1165 /* Build DDGs for all the relevant loops and hold them in G_ARR
1166 indexed by the loop index. */
1167 FOR_EACH_LOOP (li, loop, 0)
1172 /* For debugging. */
1173 if (dbg_cnt (sms_sched_loop) == false)
1176 fprintf (dump_file, "SMS reached max limit... \n");
1183 rtx insn = BB_END (loop->header);
1185 fprintf (dump_file, "SMS loop num: %d, file: %s, line: %d\n",
1186 loop->num, insn_file (insn), insn_line (insn));
1190 if (! loop_canon_p (loop))
1193 if (! loop_single_full_bb_p (loop))
1196 fprintf (dump_file, "SMS not loop_single_full_bb_p\n");
1202 get_ebb_head_tail (bb, bb, &head, &tail);
1203 latch_edge = loop_latch_edge (loop);
1204 gcc_assert (single_exit (loop));
1205 if (single_exit (loop)->count)
1206 trip_count = latch_edge->count / single_exit (loop)->count;
1208 /* Perform SMS only on loops that their average count is above threshold. */
1210 if ( latch_edge->count
1211 && (latch_edge->count < single_exit (loop)->count * SMS_LOOP_AVERAGE_COUNT_THRESHOLD))
1215 fprintf (dump_file, " %s %d (file, line)\n",
1216 insn_file (tail), insn_line (tail));
1217 fprintf (dump_file, "SMS single-bb-loop\n");
1218 if (profile_info && flag_branch_probabilities)
1220 fprintf (dump_file, "SMS loop-count ");
1221 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1222 (HOST_WIDEST_INT) bb->count);
1223 fprintf (dump_file, "\n");
1224 fprintf (dump_file, "SMS trip-count ");
1225 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1226 (HOST_WIDEST_INT) trip_count);
1227 fprintf (dump_file, "\n");
1228 fprintf (dump_file, "SMS profile-sum-max ");
1229 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1230 (HOST_WIDEST_INT) profile_info->sum_max);
1231 fprintf (dump_file, "\n");
1237 /* Make sure this is a doloop. */
1238 if ( !(count_reg = doloop_register_get (head, tail)))
1241 fprintf (dump_file, "SMS doloop_register_get failed\n");
1245 /* Don't handle BBs with calls or barriers
1246 or !single_set with the exception of instructions that include
1247 count_reg---these instructions are part of the control part
1248 that do-loop recognizes.
1249 ??? Should handle insns defining subregs. */
1250 for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn))
1256 || (NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
1257 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE
1258 && !reg_mentioned_p (count_reg, insn))
1259 || (INSN_P (insn) && (set = single_set (insn))
1260 && GET_CODE (SET_DEST (set)) == SUBREG))
1264 if (insn != NEXT_INSN (tail))
1269 fprintf (dump_file, "SMS loop-with-call\n");
1270 else if (BARRIER_P (insn))
1271 fprintf (dump_file, "SMS loop-with-barrier\n");
1272 else if ((NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
1273 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE))
1274 fprintf (dump_file, "SMS loop-with-not-single-set\n");
1276 fprintf (dump_file, "SMS loop with subreg in lhs\n");
1277 print_rtl_single (dump_file, insn);
1283 /* Always schedule the closing branch with the rest of the
1284 instructions. The branch is rotated to be in row ii-1 at the
1285 end of the scheduling procedure to make sure it's the last
1286 instruction in the iteration. */
1287 if (! (g = create_ddg (bb, 1)))
1290 fprintf (dump_file, "SMS create_ddg failed\n");
1294 g_arr[loop->num] = g;
1296 fprintf (dump_file, "...OK\n");
1301 fprintf (dump_file, "\nSMS transformation phase\n");
1302 fprintf (dump_file, "=========================\n\n");
1305 /* We don't want to perform SMS on new loops - created by versioning. */
1306 FOR_EACH_LOOP (li, loop, 0)
1309 rtx count_reg, count_init;
1311 unsigned stage_count = 0;
1312 HOST_WIDEST_INT loop_count = 0;
1313 bool opt_sc_p = false;
1315 if (! (g = g_arr[loop->num]))
1320 rtx insn = BB_END (loop->header);
1322 fprintf (dump_file, "SMS loop num: %d, file: %s, line: %d\n",
1323 loop->num, insn_file (insn), insn_line (insn));
1325 print_ddg (dump_file, g);
1328 get_ebb_head_tail (loop->header, loop->header, &head, &tail);
1330 latch_edge = loop_latch_edge (loop);
1331 gcc_assert (single_exit (loop));
1332 if (single_exit (loop)->count)
1333 trip_count = latch_edge->count / single_exit (loop)->count;
1337 fprintf (dump_file, " %s %d (file, line)\n",
1338 insn_file (tail), insn_line (tail));
1339 fprintf (dump_file, "SMS single-bb-loop\n");
1340 if (profile_info && flag_branch_probabilities)
1342 fprintf (dump_file, "SMS loop-count ");
1343 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1344 (HOST_WIDEST_INT) bb->count);
1345 fprintf (dump_file, "\n");
1346 fprintf (dump_file, "SMS profile-sum-max ");
1347 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1348 (HOST_WIDEST_INT) profile_info->sum_max);
1349 fprintf (dump_file, "\n");
1351 fprintf (dump_file, "SMS doloop\n");
1352 fprintf (dump_file, "SMS built-ddg %d\n", g->num_nodes);
1353 fprintf (dump_file, "SMS num-loads %d\n", g->num_loads);
1354 fprintf (dump_file, "SMS num-stores %d\n", g->num_stores);
1358 /* In case of th loop have doloop register it gets special
1360 count_init = NULL_RTX;
1361 if ((count_reg = doloop_register_get (head, tail)))
1363 basic_block pre_header;
1365 pre_header = loop_preheader_edge (loop)->src;
1366 count_init = const_iteration_count (count_reg, pre_header,
1369 gcc_assert (count_reg);
1371 if (dump_file && count_init)
1373 fprintf (dump_file, "SMS const-doloop ");
1374 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1376 fprintf (dump_file, "\n");
1379 node_order = XNEWVEC (int, g->num_nodes);
1381 mii = 1; /* Need to pass some estimate of mii. */
1382 rec_mii = sms_order_nodes (g, mii, node_order, &max_asap);
1383 mii = MAX (res_MII (g), rec_mii);
1384 maxii = MAX (max_asap, MAXII_FACTOR * mii);
1387 fprintf (dump_file, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1388 rec_mii, mii, maxii);
1390 /* After sms_order_nodes and before sms_schedule_by_order, to copy over
1392 set_node_sched_params (g);
1394 ps = sms_schedule_by_order (g, mii, maxii, node_order);
1398 /* Try to achieve optimized SC by normalizing the partial
1399 schedule (having the cycles start from cycle zero).
1400 The branch location must be placed in row ii-1 in the
1401 final scheduling. If failed, shift all instructions to
1402 position the branch in row ii-1. */
1403 opt_sc_p = optimize_sc (ps, g);
1405 stage_count = calculate_stage_count (ps, 0);
1408 /* Bring the branch to cycle ii-1. */
1409 int amount = SCHED_TIME (g->closing_branch) - (ps->ii - 1);
1412 fprintf (dump_file, "SMS schedule branch at cycle ii-1\n");
1414 stage_count = calculate_stage_count (ps, amount);
1417 gcc_assert (stage_count >= 1);
1418 PS_STAGE_COUNT (ps) = stage_count;
1421 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
1422 1 means that there is no interleaving between iterations thus
1423 we let the scheduling passes do the job in this case. */
1424 if (stage_count < (unsigned) PARAM_VALUE (PARAM_SMS_MIN_SC)
1425 || (count_init && (loop_count <= stage_count))
1426 || (flag_branch_probabilities && (trip_count <= stage_count)))
1430 fprintf (dump_file, "SMS failed... \n");
1431 fprintf (dump_file, "SMS sched-failed (stage-count=%d, loop-count=", stage_count);
1432 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, loop_count);
1433 fprintf (dump_file, ", trip-count=");
1434 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, trip_count);
1435 fprintf (dump_file, ")\n");
1442 /* Rotate the partial schedule to have the branch in row ii-1. */
1443 int amount = SCHED_TIME (g->closing_branch) - (ps->ii - 1);
1445 reset_sched_times (ps, amount);
1446 rotate_partial_schedule (ps, amount);
1449 set_columns_for_ps (ps);
1456 "%s:%d SMS succeeded %d %d (with ii, sc)\n",
1457 insn_file (tail), insn_line (tail), ps->ii, stage_count);
1458 print_partial_schedule (ps, dump_file);
1461 /* case the BCT count is not known , Do loop-versioning */
1462 if (count_reg && ! count_init)
1464 rtx comp_rtx = gen_rtx_fmt_ee (GT, VOIDmode, count_reg,
1465 GEN_INT(stage_count));
1466 unsigned prob = (PROB_SMS_ENOUGH_ITERATIONS
1467 * REG_BR_PROB_BASE) / 100;
1469 loop_version (loop, comp_rtx, &condition_bb,
1470 prob, prob, REG_BR_PROB_BASE - prob,
1474 /* Set new iteration count of loop kernel. */
1475 if (count_reg && count_init)
1476 SET_SRC (single_set (count_init)) = GEN_INT (loop_count
1479 /* Now apply the scheduled kernel to the RTL of the loop. */
1480 permute_partial_schedule (ps, g->closing_branch->first_note);
1482 /* Mark this loop as software pipelined so the later
1483 scheduling passes doesn't touch it. */
1484 if (! flag_resched_modulo_sched)
1485 g->bb->flags |= BB_DISABLE_SCHEDULE;
1486 /* The life-info is not valid any more. */
1487 df_set_bb_dirty (g->bb);
1489 generate_reg_moves (ps, true);
1491 print_node_sched_params (dump_file, g->num_nodes, g);
1492 /* Generate prolog and epilog. */
1493 generate_prolog_epilog (ps, loop, count_reg, count_init);
1496 free_partial_schedule (ps);
1497 free (node_sched_params);
1504 /* Release scheduler data, needed until now because of DFA. */
1505 haifa_sched_finish ();
1506 loop_optimizer_finalize ();
1509 /* The SMS scheduling algorithm itself
1510 -----------------------------------
1511 Input: 'O' an ordered list of insns of a loop.
1512 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1514 'Q' is the empty Set
1515 'PS' is the partial schedule; it holds the currently scheduled nodes with
1517 'PSP' previously scheduled predecessors.
1518 'PSS' previously scheduled successors.
1519 't(u)' the cycle where u is scheduled.
1520 'l(u)' is the latency of u.
1521 'd(v,u)' is the dependence distance from v to u.
1522 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1523 the node ordering phase.
1524 'check_hardware_resources_conflicts(u, PS, c)'
1525 run a trace around cycle/slot through DFA model
1526 to check resource conflicts involving instruction u
1527 at cycle c given the partial schedule PS.
1528 'add_to_partial_schedule_at_time(u, PS, c)'
1529 Add the node/instruction u to the partial schedule
1531 'calculate_register_pressure(PS)'
1532 Given a schedule of instructions, calculate the register
1533 pressure it implies. One implementation could be the
1534 maximum number of overlapping live ranges.
1535 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1536 registers available in the hardware.
1540 3. for each node u in O in pre-computed order
1541 4. if (PSP(u) != Q && PSS(u) == Q) then
1542 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1543 6. start = Early_start; end = Early_start + II - 1; step = 1
1544 11. else if (PSP(u) == Q && PSS(u) != Q) then
1545 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1546 13. start = Late_start; end = Late_start - II + 1; step = -1
1547 14. else if (PSP(u) != Q && PSS(u) != Q) then
1548 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1549 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1550 17. start = Early_start;
1551 18. end = min(Early_start + II - 1 , Late_start);
1553 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1554 21. start = ASAP(u); end = start + II - 1; step = 1
1558 24. for (c = start ; c != end ; c += step)
1559 25. if check_hardware_resources_conflicts(u, PS, c) then
1560 26. add_to_partial_schedule_at_time(u, PS, c)
1565 31. if (success == false) then
1567 33. if (II > maxII) then
1568 34. finish - failed to schedule
1573 39. if (calculate_register_pressure(PS) > maxRP) then
1576 42. compute epilogue & prologue
1577 43. finish - succeeded to schedule
1580 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1581 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1582 set to 0 to save compile time. */
1583 #define DFA_HISTORY SMS_DFA_HISTORY
1585 /* A threshold for the number of repeated unsuccessful attempts to insert
1586 an empty row, before we flush the partial schedule and start over. */
1587 #define MAX_SPLIT_NUM 10
1588 /* Given the partial schedule PS, this function calculates and returns the
1589 cycles in which we can schedule the node with the given index I.
1590 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1591 noticed that there are several cases in which we fail to SMS the loop
1592 because the sched window of a node is empty due to tight data-deps. In
1593 such cases we want to unschedule some of the predecessors/successors
1594 until we get non-empty scheduling window. It returns -1 if the
1595 scheduling window is empty and zero otherwise. */
1598 get_sched_window (partial_schedule_ptr ps, ddg_node_ptr u_node,
1599 sbitmap sched_nodes, int ii, int *start_p, int *step_p,
1602 int start, step, end;
1603 int early_start, late_start;
1605 sbitmap psp = sbitmap_alloc (ps->g->num_nodes);
1606 sbitmap pss = sbitmap_alloc (ps->g->num_nodes);
1607 sbitmap u_node_preds = NODE_PREDECESSORS (u_node);
1608 sbitmap u_node_succs = NODE_SUCCESSORS (u_node);
1614 /* 1. compute sched window for u (start, end, step). */
1617 psp_not_empty = sbitmap_a_and_b_cg (psp, u_node_preds, sched_nodes);
1618 pss_not_empty = sbitmap_a_and_b_cg (pss, u_node_succs, sched_nodes);
1620 /* We first compute a forward range (start <= end), then decide whether
1622 early_start = INT_MIN;
1623 late_start = INT_MAX;
1631 if (dump_file && (psp_not_empty || pss_not_empty))
1633 fprintf (dump_file, "\nAnalyzing dependencies for node %d (INSN %d)"
1634 "; ii = %d\n\n", u_node->cuid, INSN_UID (u_node->insn), ii);
1635 fprintf (dump_file, "%11s %11s %11s %11s %5s\n",
1636 "start", "early start", "late start", "end", "time");
1637 fprintf (dump_file, "=========== =========== =========== ==========="
1640 /* Calculate early_start and limit end. Both bounds are inclusive. */
1642 for (e = u_node->in; e != 0; e = e->next_in)
1644 ddg_node_ptr v_node = e->src;
1646 if (TEST_BIT (sched_nodes, v_node->cuid))
1648 int p_st = SCHED_TIME (v_node);
1649 int earliest = p_st + e->latency - (e->distance * ii);
1650 int latest = (e->data_type == MEM_DEP ? p_st + ii - 1 : INT_MAX);
1654 fprintf (dump_file, "%11s %11d %11s %11d %5d",
1655 "", earliest, "", latest, p_st);
1656 print_ddg_edge (dump_file, e);
1657 fprintf (dump_file, "\n");
1660 early_start = MAX (early_start, earliest);
1661 end = MIN (end, latest);
1663 if (e->type == TRUE_DEP && e->data_type == REG_DEP)
1668 /* Calculate late_start and limit start. Both bounds are inclusive. */
1670 for (e = u_node->out; e != 0; e = e->next_out)
1672 ddg_node_ptr v_node = e->dest;
1674 if (TEST_BIT (sched_nodes, v_node->cuid))
1676 int s_st = SCHED_TIME (v_node);
1677 int earliest = (e->data_type == MEM_DEP ? s_st - ii + 1 : INT_MIN);
1678 int latest = s_st - e->latency + (e->distance * ii);
1682 fprintf (dump_file, "%11d %11s %11d %11s %5d",
1683 earliest, "", latest, "", s_st);
1684 print_ddg_edge (dump_file, e);
1685 fprintf (dump_file, "\n");
1688 start = MAX (start, earliest);
1689 late_start = MIN (late_start, latest);
1691 if (e->type == TRUE_DEP && e->data_type == REG_DEP)
1696 if (dump_file && (psp_not_empty || pss_not_empty))
1698 fprintf (dump_file, "----------- ----------- ----------- -----------"
1700 fprintf (dump_file, "%11d %11d %11d %11d %5s %s\n",
1701 start, early_start, late_start, end, "",
1702 "(max, max, min, min)");
1705 /* Get a target scheduling window no bigger than ii. */
1706 if (early_start == INT_MIN && late_start == INT_MAX)
1707 early_start = SCHED_ASAP (u_node);
1708 else if (early_start == INT_MIN)
1709 early_start = late_start - (ii - 1);
1710 late_start = MIN (late_start, early_start + (ii - 1));
1712 /* Apply memory dependence limits. */
1713 start = MAX (start, early_start);
1714 end = MIN (end, late_start);
1716 if (dump_file && (psp_not_empty || pss_not_empty))
1717 fprintf (dump_file, "%11s %11d %11d %11s %5s final window\n",
1718 "", start, end, "", "");
1720 /* If there are at least as many successors as predecessors, schedule the
1721 node close to its successors. */
1722 if (pss_not_empty && count_succs >= count_preds)
1730 /* Now that we've finalized the window, make END an exclusive rather
1731 than an inclusive bound. */
1740 if ((start >= end && step == 1) || (start <= end && step == -1))
1743 fprintf (dump_file, "\nEmpty window: start=%d, end=%d, step=%d\n",
1751 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
1752 node currently been scheduled. At the end of the calculation
1753 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
1754 U_NODE which are (1) already scheduled in the first/last row of
1755 U_NODE's scheduling window, (2) whose dependence inequality with U
1756 becomes an equality when U is scheduled in this same row, and (3)
1757 whose dependence latency is zero.
1759 The first and last rows are calculated using the following parameters:
1760 START/END rows - The cycles that begins/ends the traversal on the window;
1761 searching for an empty cycle to schedule U_NODE.
1762 STEP - The direction in which we traverse the window.
1763 II - The initiation interval. */
1766 calculate_must_precede_follow (ddg_node_ptr u_node, int start, int end,
1767 int step, int ii, sbitmap sched_nodes,
1768 sbitmap must_precede, sbitmap must_follow)
1771 int first_cycle_in_window, last_cycle_in_window;
1773 gcc_assert (must_precede && must_follow);
1775 /* Consider the following scheduling window:
1776 {first_cycle_in_window, first_cycle_in_window+1, ...,
1777 last_cycle_in_window}. If step is 1 then the following will be
1778 the order we traverse the window: {start=first_cycle_in_window,
1779 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
1780 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
1781 end=first_cycle_in_window-1} if step is -1. */
1782 first_cycle_in_window = (step == 1) ? start : end - step;
1783 last_cycle_in_window = (step == 1) ? end - step : start;
1785 sbitmap_zero (must_precede);
1786 sbitmap_zero (must_follow);
1789 fprintf (dump_file, "\nmust_precede: ");
1791 /* Instead of checking if:
1792 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
1793 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
1794 first_cycle_in_window)
1796 we use the fact that latency is non-negative:
1797 SCHED_TIME (e->src) - (e->distance * ii) <=
1798 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
1799 first_cycle_in_window
1801 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
1802 for (e = u_node->in; e != 0; e = e->next_in)
1803 if (TEST_BIT (sched_nodes, e->src->cuid)
1804 && ((SCHED_TIME (e->src) - (e->distance * ii)) ==
1805 first_cycle_in_window))
1808 fprintf (dump_file, "%d ", e->src->cuid);
1810 SET_BIT (must_precede, e->src->cuid);
1814 fprintf (dump_file, "\nmust_follow: ");
1816 /* Instead of checking if:
1817 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
1818 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
1819 last_cycle_in_window)
1821 we use the fact that latency is non-negative:
1822 SCHED_TIME (e->dest) + (e->distance * ii) >=
1823 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
1824 last_cycle_in_window
1826 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
1827 for (e = u_node->out; e != 0; e = e->next_out)
1828 if (TEST_BIT (sched_nodes, e->dest->cuid)
1829 && ((SCHED_TIME (e->dest) + (e->distance * ii)) ==
1830 last_cycle_in_window))
1833 fprintf (dump_file, "%d ", e->dest->cuid);
1835 SET_BIT (must_follow, e->dest->cuid);
1839 fprintf (dump_file, "\n");
1842 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
1843 parameters to decide if that's possible:
1844 PS - The partial schedule.
1845 U - The serial number of U_NODE.
1846 NUM_SPLITS - The number of row splits made so far.
1847 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
1848 the first row of the scheduling window)
1849 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
1850 last row of the scheduling window) */
1853 try_scheduling_node_in_cycle (partial_schedule_ptr ps, ddg_node_ptr u_node,
1854 int u, int cycle, sbitmap sched_nodes,
1855 int *num_splits, sbitmap must_precede,
1856 sbitmap must_follow)
1861 verify_partial_schedule (ps, sched_nodes);
1862 psi = ps_add_node_check_conflicts (ps, u_node, cycle,
1863 must_precede, must_follow);
1866 SCHED_TIME (u_node) = cycle;
1867 SET_BIT (sched_nodes, u);
1871 fprintf (dump_file, "Scheduled w/o split in %d\n", cycle);
1878 /* This function implements the scheduling algorithm for SMS according to the
1880 static partial_schedule_ptr
1881 sms_schedule_by_order (ddg_ptr g, int mii, int maxii, int *nodes_order)
1884 int i, c, success, num_splits = 0;
1885 int flush_and_start_over = true;
1886 int num_nodes = g->num_nodes;
1887 int start, end, step; /* Place together into one struct? */
1888 sbitmap sched_nodes = sbitmap_alloc (num_nodes);
1889 sbitmap must_precede = sbitmap_alloc (num_nodes);
1890 sbitmap must_follow = sbitmap_alloc (num_nodes);
1891 sbitmap tobe_scheduled = sbitmap_alloc (num_nodes);
1893 partial_schedule_ptr ps = create_partial_schedule (ii, g, DFA_HISTORY);
1895 sbitmap_ones (tobe_scheduled);
1896 sbitmap_zero (sched_nodes);
1898 while (flush_and_start_over && (ii < maxii))
1902 fprintf (dump_file, "Starting with ii=%d\n", ii);
1903 flush_and_start_over = false;
1904 sbitmap_zero (sched_nodes);
1906 for (i = 0; i < num_nodes; i++)
1908 int u = nodes_order[i];
1909 ddg_node_ptr u_node = &ps->g->nodes[u];
1910 rtx insn = u_node->insn;
1912 if (!NONDEBUG_INSN_P (insn))
1914 RESET_BIT (tobe_scheduled, u);
1918 if (TEST_BIT (sched_nodes, u))
1921 /* Try to get non-empty scheduling window. */
1923 if (get_sched_window (ps, u_node, sched_nodes, ii, &start,
1927 fprintf (dump_file, "\nTrying to schedule node %d "
1928 "INSN = %d in (%d .. %d) step %d\n", u, (INSN_UID
1929 (g->nodes[u].insn)), start, end, step);
1931 gcc_assert ((step > 0 && start < end)
1932 || (step < 0 && start > end));
1934 calculate_must_precede_follow (u_node, start, end, step, ii,
1935 sched_nodes, must_precede,
1938 for (c = start; c != end; c += step)
1940 sbitmap tmp_precede, tmp_follow;
1942 set_must_precede_follow (&tmp_follow, must_follow,
1943 &tmp_precede, must_precede,
1944 c, start, end, step);
1946 try_scheduling_node_in_cycle (ps, u_node, u, c,
1948 &num_splits, tmp_precede,
1954 verify_partial_schedule (ps, sched_nodes);
1963 if (num_splits >= MAX_SPLIT_NUM)
1966 flush_and_start_over = true;
1967 verify_partial_schedule (ps, sched_nodes);
1968 reset_partial_schedule (ps, ii);
1969 verify_partial_schedule (ps, sched_nodes);
1974 /* The scheduling window is exclusive of 'end'
1975 whereas compute_split_window() expects an inclusive,
1978 split_row = compute_split_row (sched_nodes, start, end - 1,
1981 split_row = compute_split_row (sched_nodes, end + 1, start,
1984 ps_insert_empty_row (ps, split_row, sched_nodes);
1985 i--; /* Go back and retry node i. */
1988 fprintf (dump_file, "num_splits=%d\n", num_splits);
1991 /* ??? If (success), check register pressure estimates. */
1992 } /* Continue with next node. */
1993 } /* While flush_and_start_over. */
1996 free_partial_schedule (ps);
2000 gcc_assert (sbitmap_equal (tobe_scheduled, sched_nodes));
2002 sbitmap_free (sched_nodes);
2003 sbitmap_free (must_precede);
2004 sbitmap_free (must_follow);
2005 sbitmap_free (tobe_scheduled);
2010 /* This function inserts a new empty row into PS at the position
2011 according to SPLITROW, keeping all already scheduled instructions
2012 intact and updating their SCHED_TIME and cycle accordingly. */
2014 ps_insert_empty_row (partial_schedule_ptr ps, int split_row,
2015 sbitmap sched_nodes)
2017 ps_insn_ptr crr_insn;
2018 ps_insn_ptr *rows_new;
2020 int new_ii = ii + 1;
2022 int *rows_length_new;
2024 verify_partial_schedule (ps, sched_nodes);
2026 /* We normalize sched_time and rotate ps to have only non-negative sched
2027 times, for simplicity of updating cycles after inserting new row. */
2028 split_row -= ps->min_cycle;
2029 split_row = SMODULO (split_row, ii);
2031 fprintf (dump_file, "split_row=%d\n", split_row);
2033 reset_sched_times (ps, PS_MIN_CYCLE (ps));
2034 rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
2036 rows_new = (ps_insn_ptr *) xcalloc (new_ii, sizeof (ps_insn_ptr));
2037 rows_length_new = (int *) xcalloc (new_ii, sizeof (int));
2038 for (row = 0; row < split_row; row++)
2040 rows_new[row] = ps->rows[row];
2041 rows_length_new[row] = ps->rows_length[row];
2042 ps->rows[row] = NULL;
2043 for (crr_insn = rows_new[row];
2044 crr_insn; crr_insn = crr_insn->next_in_row)
2046 ddg_node_ptr u = crr_insn->node;
2047 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii);
2049 SCHED_TIME (u) = new_time;
2050 crr_insn->cycle = new_time;
2051 SCHED_ROW (u) = new_time % new_ii;
2052 SCHED_STAGE (u) = new_time / new_ii;
2057 rows_new[split_row] = NULL;
2059 for (row = split_row; row < ii; row++)
2061 rows_new[row + 1] = ps->rows[row];
2062 rows_length_new[row + 1] = ps->rows_length[row];
2063 ps->rows[row] = NULL;
2064 for (crr_insn = rows_new[row + 1];
2065 crr_insn; crr_insn = crr_insn->next_in_row)
2067 ddg_node_ptr u = crr_insn->node;
2068 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii) + 1;
2070 SCHED_TIME (u) = new_time;
2071 crr_insn->cycle = new_time;
2072 SCHED_ROW (u) = new_time % new_ii;
2073 SCHED_STAGE (u) = new_time / new_ii;
2078 ps->min_cycle = ps->min_cycle + ps->min_cycle / ii
2079 + (SMODULO (ps->min_cycle, ii) >= split_row ? 1 : 0);
2080 ps->max_cycle = ps->max_cycle + ps->max_cycle / ii
2081 + (SMODULO (ps->max_cycle, ii) >= split_row ? 1 : 0);
2083 ps->rows = rows_new;
2084 free (ps->rows_length);
2085 ps->rows_length = rows_length_new;
2087 gcc_assert (ps->min_cycle >= 0);
2089 verify_partial_schedule (ps, sched_nodes);
2092 fprintf (dump_file, "min_cycle=%d, max_cycle=%d\n", ps->min_cycle,
2096 /* Given U_NODE which is the node that failed to be scheduled; LOW and
2097 UP which are the boundaries of it's scheduling window; compute using
2098 SCHED_NODES and II a row in the partial schedule that can be split
2099 which will separate a critical predecessor from a critical successor
2100 thereby expanding the window, and return it. */
2102 compute_split_row (sbitmap sched_nodes, int low, int up, int ii,
2103 ddg_node_ptr u_node)
2106 int lower = INT_MIN, upper = INT_MAX;
2107 ddg_node_ptr crit_pred = NULL;
2108 ddg_node_ptr crit_succ = NULL;
2111 for (e = u_node->in; e != 0; e = e->next_in)
2113 ddg_node_ptr v_node = e->src;
2115 if (TEST_BIT (sched_nodes, v_node->cuid)
2116 && (low == SCHED_TIME (v_node) + e->latency - (e->distance * ii)))
2117 if (SCHED_TIME (v_node) > lower)
2120 lower = SCHED_TIME (v_node);
2124 if (crit_pred != NULL)
2126 crit_cycle = SCHED_TIME (crit_pred) + 1;
2127 return SMODULO (crit_cycle, ii);
2130 for (e = u_node->out; e != 0; e = e->next_out)
2132 ddg_node_ptr v_node = e->dest;
2133 if (TEST_BIT (sched_nodes, v_node->cuid)
2134 && (up == SCHED_TIME (v_node) - e->latency + (e->distance * ii)))
2135 if (SCHED_TIME (v_node) < upper)
2138 upper = SCHED_TIME (v_node);
2142 if (crit_succ != NULL)
2144 crit_cycle = SCHED_TIME (crit_succ);
2145 return SMODULO (crit_cycle, ii);
2149 fprintf (dump_file, "Both crit_pred and crit_succ are NULL\n");
2151 return SMODULO ((low + up + 1) / 2, ii);
2155 verify_partial_schedule (partial_schedule_ptr ps, sbitmap sched_nodes)
2158 ps_insn_ptr crr_insn;
2160 for (row = 0; row < ps->ii; row++)
2164 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
2166 ddg_node_ptr u = crr_insn->node;
2169 gcc_assert (TEST_BIT (sched_nodes, u->cuid));
2170 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2171 popcount (sched_nodes) == number of insns in ps. */
2172 gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
2173 gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
2176 gcc_assert (ps->rows_length[row] == length);
2181 /* This page implements the algorithm for ordering the nodes of a DDG
2182 for modulo scheduling, activated through the
2183 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2185 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2186 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
2187 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
2188 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2189 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
2190 #define DEPTH(x) (ASAP ((x)))
2192 typedef struct node_order_params * nopa;
2194 static void order_nodes_of_sccs (ddg_all_sccs_ptr, int * result);
2195 static int order_nodes_in_scc (ddg_ptr, sbitmap, sbitmap, int*, int);
2196 static nopa calculate_order_params (ddg_ptr, int, int *);
2197 static int find_max_asap (ddg_ptr, sbitmap);
2198 static int find_max_hv_min_mob (ddg_ptr, sbitmap);
2199 static int find_max_dv_min_mob (ddg_ptr, sbitmap);
2201 enum sms_direction {BOTTOMUP, TOPDOWN};
2203 struct node_order_params
2210 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2212 check_nodes_order (int *node_order, int num_nodes)
2215 sbitmap tmp = sbitmap_alloc (num_nodes);
2220 fprintf (dump_file, "SMS final nodes order: \n");
2222 for (i = 0; i < num_nodes; i++)
2224 int u = node_order[i];
2227 fprintf (dump_file, "%d ", u);
2228 gcc_assert (u < num_nodes && u >= 0 && !TEST_BIT (tmp, u));
2234 fprintf (dump_file, "\n");
2239 /* Order the nodes of G for scheduling and pass the result in
2240 NODE_ORDER. Also set aux.count of each node to ASAP.
2241 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2243 sms_order_nodes (ddg_ptr g, int mii, int * node_order, int *pmax_asap)
2247 ddg_all_sccs_ptr sccs = create_ddg_all_sccs (g);
2249 nopa nops = calculate_order_params (g, mii, pmax_asap);
2252 print_sccs (dump_file, sccs, g);
2254 order_nodes_of_sccs (sccs, node_order);
2256 if (sccs->num_sccs > 0)
2257 /* First SCC has the largest recurrence_length. */
2258 rec_mii = sccs->sccs[0]->recurrence_length;
2260 /* Save ASAP before destroying node_order_params. */
2261 for (i = 0; i < g->num_nodes; i++)
2263 ddg_node_ptr v = &g->nodes[i];
2264 v->aux.count = ASAP (v);
2268 free_ddg_all_sccs (sccs);
2269 check_nodes_order (node_order, g->num_nodes);
2275 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs, int * node_order)
2278 ddg_ptr g = all_sccs->ddg;
2279 int num_nodes = g->num_nodes;
2280 sbitmap prev_sccs = sbitmap_alloc (num_nodes);
2281 sbitmap on_path = sbitmap_alloc (num_nodes);
2282 sbitmap tmp = sbitmap_alloc (num_nodes);
2283 sbitmap ones = sbitmap_alloc (num_nodes);
2285 sbitmap_zero (prev_sccs);
2286 sbitmap_ones (ones);
2288 /* Perform the node ordering starting from the SCC with the highest recMII.
2289 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2290 for (i = 0; i < all_sccs->num_sccs; i++)
2292 ddg_scc_ptr scc = all_sccs->sccs[i];
2294 /* Add nodes on paths from previous SCCs to the current SCC. */
2295 find_nodes_on_paths (on_path, g, prev_sccs, scc->nodes);
2296 sbitmap_a_or_b (tmp, scc->nodes, on_path);
2298 /* Add nodes on paths from the current SCC to previous SCCs. */
2299 find_nodes_on_paths (on_path, g, scc->nodes, prev_sccs);
2300 sbitmap_a_or_b (tmp, tmp, on_path);
2302 /* Remove nodes of previous SCCs from current extended SCC. */
2303 sbitmap_difference (tmp, tmp, prev_sccs);
2305 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
2306 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2309 /* Handle the remaining nodes that do not belong to any scc. Each call
2310 to order_nodes_in_scc handles a single connected component. */
2311 while (pos < g->num_nodes)
2313 sbitmap_difference (tmp, ones, prev_sccs);
2314 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
2316 sbitmap_free (prev_sccs);
2317 sbitmap_free (on_path);
2319 sbitmap_free (ones);
2322 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2323 static struct node_order_params *
2324 calculate_order_params (ddg_ptr g, int mii ATTRIBUTE_UNUSED, int *pmax_asap)
2328 int num_nodes = g->num_nodes;
2330 /* Allocate a place to hold ordering params for each node in the DDG. */
2331 nopa node_order_params_arr;
2333 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2334 node_order_params_arr = (nopa) xcalloc (num_nodes,
2335 sizeof (struct node_order_params));
2337 /* Set the aux pointer of each node to point to its order_params structure. */
2338 for (u = 0; u < num_nodes; u++)
2339 g->nodes[u].aux.info = &node_order_params_arr[u];
2341 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2342 calculate ASAP, ALAP, mobility, distance, and height for each node
2343 in the dependence (direct acyclic) graph. */
2345 /* We assume that the nodes in the array are in topological order. */
2348 for (u = 0; u < num_nodes; u++)
2350 ddg_node_ptr u_node = &g->nodes[u];
2353 for (e = u_node->in; e; e = e->next_in)
2354 if (e->distance == 0)
2355 ASAP (u_node) = MAX (ASAP (u_node),
2356 ASAP (e->src) + e->latency);
2357 max_asap = MAX (max_asap, ASAP (u_node));
2360 for (u = num_nodes - 1; u > -1; u--)
2362 ddg_node_ptr u_node = &g->nodes[u];
2364 ALAP (u_node) = max_asap;
2365 HEIGHT (u_node) = 0;
2366 for (e = u_node->out; e; e = e->next_out)
2367 if (e->distance == 0)
2369 ALAP (u_node) = MIN (ALAP (u_node),
2370 ALAP (e->dest) - e->latency);
2371 HEIGHT (u_node) = MAX (HEIGHT (u_node),
2372 HEIGHT (e->dest) + e->latency);
2377 fprintf (dump_file, "\nOrder params\n");
2378 for (u = 0; u < num_nodes; u++)
2380 ddg_node_ptr u_node = &g->nodes[u];
2382 fprintf (dump_file, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u,
2383 ASAP (u_node), ALAP (u_node), HEIGHT (u_node));
2387 *pmax_asap = max_asap;
2388 return node_order_params_arr;
2392 find_max_asap (ddg_ptr g, sbitmap nodes)
2397 sbitmap_iterator sbi;
2399 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
2401 ddg_node_ptr u_node = &g->nodes[u];
2403 if (max_asap < ASAP (u_node))
2405 max_asap = ASAP (u_node);
2413 find_max_hv_min_mob (ddg_ptr g, sbitmap nodes)
2417 int min_mob = INT_MAX;
2419 sbitmap_iterator sbi;
2421 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
2423 ddg_node_ptr u_node = &g->nodes[u];
2425 if (max_hv < HEIGHT (u_node))
2427 max_hv = HEIGHT (u_node);
2428 min_mob = MOB (u_node);
2431 else if ((max_hv == HEIGHT (u_node))
2432 && (min_mob > MOB (u_node)))
2434 min_mob = MOB (u_node);
2442 find_max_dv_min_mob (ddg_ptr g, sbitmap nodes)
2446 int min_mob = INT_MAX;
2448 sbitmap_iterator sbi;
2450 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
2452 ddg_node_ptr u_node = &g->nodes[u];
2454 if (max_dv < DEPTH (u_node))
2456 max_dv = DEPTH (u_node);
2457 min_mob = MOB (u_node);
2460 else if ((max_dv == DEPTH (u_node))
2461 && (min_mob > MOB (u_node)))
2463 min_mob = MOB (u_node);
2470 /* Places the nodes of SCC into the NODE_ORDER array starting
2471 at position POS, according to the SMS ordering algorithm.
2472 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2473 the NODE_ORDER array, starting from position zero. */
2475 order_nodes_in_scc (ddg_ptr g, sbitmap nodes_ordered, sbitmap scc,
2476 int * node_order, int pos)
2478 enum sms_direction dir;
2479 int num_nodes = g->num_nodes;
2480 sbitmap workset = sbitmap_alloc (num_nodes);
2481 sbitmap tmp = sbitmap_alloc (num_nodes);
2482 sbitmap zero_bitmap = sbitmap_alloc (num_nodes);
2483 sbitmap predecessors = sbitmap_alloc (num_nodes);
2484 sbitmap successors = sbitmap_alloc (num_nodes);
2486 sbitmap_zero (predecessors);
2487 find_predecessors (predecessors, g, nodes_ordered);
2489 sbitmap_zero (successors);
2490 find_successors (successors, g, nodes_ordered);
2493 if (sbitmap_a_and_b_cg (tmp, predecessors, scc))
2495 sbitmap_copy (workset, tmp);
2498 else if (sbitmap_a_and_b_cg (tmp, successors, scc))
2500 sbitmap_copy (workset, tmp);
2507 sbitmap_zero (workset);
2508 if ((u = find_max_asap (g, scc)) >= 0)
2509 SET_BIT (workset, u);
2513 sbitmap_zero (zero_bitmap);
2514 while (!sbitmap_equal (workset, zero_bitmap))
2517 ddg_node_ptr v_node;
2518 sbitmap v_node_preds;
2519 sbitmap v_node_succs;
2523 while (!sbitmap_equal (workset, zero_bitmap))
2525 v = find_max_hv_min_mob (g, workset);
2526 v_node = &g->nodes[v];
2527 node_order[pos++] = v;
2528 v_node_succs = NODE_SUCCESSORS (v_node);
2529 sbitmap_a_and_b (tmp, v_node_succs, scc);
2531 /* Don't consider the already ordered successors again. */
2532 sbitmap_difference (tmp, tmp, nodes_ordered);
2533 sbitmap_a_or_b (workset, workset, tmp);
2534 RESET_BIT (workset, v);
2535 SET_BIT (nodes_ordered, v);
2538 sbitmap_zero (predecessors);
2539 find_predecessors (predecessors, g, nodes_ordered);
2540 sbitmap_a_and_b (workset, predecessors, scc);
2544 while (!sbitmap_equal (workset, zero_bitmap))
2546 v = find_max_dv_min_mob (g, workset);
2547 v_node = &g->nodes[v];
2548 node_order[pos++] = v;
2549 v_node_preds = NODE_PREDECESSORS (v_node);
2550 sbitmap_a_and_b (tmp, v_node_preds, scc);
2552 /* Don't consider the already ordered predecessors again. */
2553 sbitmap_difference (tmp, tmp, nodes_ordered);
2554 sbitmap_a_or_b (workset, workset, tmp);
2555 RESET_BIT (workset, v);
2556 SET_BIT (nodes_ordered, v);
2559 sbitmap_zero (successors);
2560 find_successors (successors, g, nodes_ordered);
2561 sbitmap_a_and_b (workset, successors, scc);
2565 sbitmap_free (workset);
2566 sbitmap_free (zero_bitmap);
2567 sbitmap_free (predecessors);
2568 sbitmap_free (successors);
2573 /* This page contains functions for manipulating partial-schedules during
2574 modulo scheduling. */
2576 /* Create a partial schedule and allocate a memory to hold II rows. */
2578 static partial_schedule_ptr
2579 create_partial_schedule (int ii, ddg_ptr g, int history)
2581 partial_schedule_ptr ps = XNEW (struct partial_schedule);
2582 ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
2583 ps->rows_length = (int *) xcalloc (ii, sizeof (int));
2585 ps->history = history;
2586 ps->min_cycle = INT_MAX;
2587 ps->max_cycle = INT_MIN;
2593 /* Free the PS_INSNs in rows array of the given partial schedule.
2594 ??? Consider caching the PS_INSN's. */
2596 free_ps_insns (partial_schedule_ptr ps)
2600 for (i = 0; i < ps->ii; i++)
2604 ps_insn_ptr ps_insn = ps->rows[i]->next_in_row;
2607 ps->rows[i] = ps_insn;
2613 /* Free all the memory allocated to the partial schedule. */
2616 free_partial_schedule (partial_schedule_ptr ps)
2622 free (ps->rows_length);
2626 /* Clear the rows array with its PS_INSNs, and create a new one with
2630 reset_partial_schedule (partial_schedule_ptr ps, int new_ii)
2635 if (new_ii == ps->ii)
2637 ps->rows = (ps_insn_ptr *) xrealloc (ps->rows, new_ii
2638 * sizeof (ps_insn_ptr));
2639 memset (ps->rows, 0, new_ii * sizeof (ps_insn_ptr));
2640 ps->rows_length = (int *) xrealloc (ps->rows_length, new_ii * sizeof (int));
2641 memset (ps->rows_length, 0, new_ii * sizeof (int));
2643 ps->min_cycle = INT_MAX;
2644 ps->max_cycle = INT_MIN;
2647 /* Prints the partial schedule as an ii rows array, for each rows
2648 print the ids of the insns in it. */
2650 print_partial_schedule (partial_schedule_ptr ps, FILE *dump)
2654 for (i = 0; i < ps->ii; i++)
2656 ps_insn_ptr ps_i = ps->rows[i];
2658 fprintf (dump, "\n[ROW %d ]: ", i);
2661 if (JUMP_P (ps_i->node->insn))
2662 fprintf (dump, "%d (branch), ",
2663 INSN_UID (ps_i->node->insn));
2665 fprintf (dump, "%d, ",
2666 INSN_UID (ps_i->node->insn));
2668 ps_i = ps_i->next_in_row;
2673 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2675 create_ps_insn (ddg_node_ptr node, int cycle)
2677 ps_insn_ptr ps_i = XNEW (struct ps_insn);
2680 ps_i->next_in_row = NULL;
2681 ps_i->prev_in_row = NULL;
2682 ps_i->cycle = cycle;
2688 /* Removes the given PS_INSN from the partial schedule. */
2690 remove_node_from_ps (partial_schedule_ptr ps, ps_insn_ptr ps_i)
2694 gcc_assert (ps && ps_i);
2696 row = SMODULO (ps_i->cycle, ps->ii);
2697 if (! ps_i->prev_in_row)
2699 gcc_assert (ps_i == ps->rows[row]);
2700 ps->rows[row] = ps_i->next_in_row;
2702 ps->rows[row]->prev_in_row = NULL;
2706 ps_i->prev_in_row->next_in_row = ps_i->next_in_row;
2707 if (ps_i->next_in_row)
2708 ps_i->next_in_row->prev_in_row = ps_i->prev_in_row;
2711 ps->rows_length[row] -= 1;
2716 /* Unlike what literature describes for modulo scheduling (which focuses
2717 on VLIW machines) the order of the instructions inside a cycle is
2718 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2719 where the current instruction should go relative to the already
2720 scheduled instructions in the given cycle. Go over these
2721 instructions and find the first possible column to put it in. */
2723 ps_insn_find_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
2724 sbitmap must_precede, sbitmap must_follow)
2726 ps_insn_ptr next_ps_i;
2727 ps_insn_ptr first_must_follow = NULL;
2728 ps_insn_ptr last_must_precede = NULL;
2729 ps_insn_ptr last_in_row = NULL;
2735 row = SMODULO (ps_i->cycle, ps->ii);
2737 /* Find the first must follow and the last must precede
2738 and insert the node immediately after the must precede
2739 but make sure that it there is no must follow after it. */
2740 for (next_ps_i = ps->rows[row];
2742 next_ps_i = next_ps_i->next_in_row)
2744 if (must_follow && TEST_BIT (must_follow, next_ps_i->node->cuid)
2745 && ! first_must_follow)
2746 first_must_follow = next_ps_i;
2747 if (must_precede && TEST_BIT (must_precede, next_ps_i->node->cuid))
2749 /* If we have already met a node that must follow, then
2750 there is no possible column. */
2751 if (first_must_follow)
2754 last_must_precede = next_ps_i;
2756 /* The closing branch must be the last in the row. */
2758 && TEST_BIT (must_precede, next_ps_i->node->cuid)
2759 && JUMP_P (next_ps_i->node->insn))
2762 last_in_row = next_ps_i;
2765 /* The closing branch is scheduled as well. Make sure there is no
2766 dependent instruction after it as the branch should be the last
2767 instruction in the row. */
2768 if (JUMP_P (ps_i->node->insn))
2770 if (first_must_follow)
2774 /* Make the branch the last in the row. New instructions
2775 will be inserted at the beginning of the row or after the
2776 last must_precede instruction thus the branch is guaranteed
2777 to remain the last instruction in the row. */
2778 last_in_row->next_in_row = ps_i;
2779 ps_i->prev_in_row = last_in_row;
2780 ps_i->next_in_row = NULL;
2783 ps->rows[row] = ps_i;
2787 /* Now insert the node after INSERT_AFTER_PSI. */
2789 if (! last_must_precede)
2791 ps_i->next_in_row = ps->rows[row];
2792 ps_i->prev_in_row = NULL;
2793 if (ps_i->next_in_row)
2794 ps_i->next_in_row->prev_in_row = ps_i;
2795 ps->rows[row] = ps_i;
2799 ps_i->next_in_row = last_must_precede->next_in_row;
2800 last_must_precede->next_in_row = ps_i;
2801 ps_i->prev_in_row = last_must_precede;
2802 if (ps_i->next_in_row)
2803 ps_i->next_in_row->prev_in_row = ps_i;
2809 /* Advances the PS_INSN one column in its current row; returns false
2810 in failure and true in success. Bit N is set in MUST_FOLLOW if
2811 the node with cuid N must be come after the node pointed to by
2812 PS_I when scheduled in the same cycle. */
2814 ps_insn_advance_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
2815 sbitmap must_follow)
2817 ps_insn_ptr prev, next;
2819 ddg_node_ptr next_node;
2824 row = SMODULO (ps_i->cycle, ps->ii);
2826 if (! ps_i->next_in_row)
2829 next_node = ps_i->next_in_row->node;
2831 /* Check if next_in_row is dependent on ps_i, both having same sched
2832 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
2833 if (must_follow && TEST_BIT (must_follow, next_node->cuid))
2836 /* Advance PS_I over its next_in_row in the doubly linked list. */
2837 prev = ps_i->prev_in_row;
2838 next = ps_i->next_in_row;
2840 if (ps_i == ps->rows[row])
2841 ps->rows[row] = next;
2843 ps_i->next_in_row = next->next_in_row;
2845 if (next->next_in_row)
2846 next->next_in_row->prev_in_row = ps_i;
2848 next->next_in_row = ps_i;
2849 ps_i->prev_in_row = next;
2851 next->prev_in_row = prev;
2853 prev->next_in_row = next;
2858 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
2859 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
2860 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
2861 before/after (respectively) the node pointed to by PS_I when scheduled
2862 in the same cycle. */
2864 add_node_to_ps (partial_schedule_ptr ps, ddg_node_ptr node, int cycle,
2865 sbitmap must_precede, sbitmap must_follow)
2868 int row = SMODULO (cycle, ps->ii);
2870 if (ps->rows_length[row] >= issue_rate)
2873 ps_i = create_ps_insn (node, cycle);
2875 /* Finds and inserts PS_I according to MUST_FOLLOW and
2877 if (! ps_insn_find_column (ps, ps_i, must_precede, must_follow))
2883 ps->rows_length[row] += 1;
2887 /* Advance time one cycle. Assumes DFA is being used. */
2889 advance_one_cycle (void)
2891 if (targetm.sched.dfa_pre_cycle_insn)
2892 state_transition (curr_state,
2893 targetm.sched.dfa_pre_cycle_insn ());
2895 state_transition (curr_state, NULL);
2897 if (targetm.sched.dfa_post_cycle_insn)
2898 state_transition (curr_state,
2899 targetm.sched.dfa_post_cycle_insn ());
2904 /* Checks if PS has resource conflicts according to DFA, starting from
2905 FROM cycle to TO cycle; returns true if there are conflicts and false
2906 if there are no conflicts. Assumes DFA is being used. */
2908 ps_has_conflicts (partial_schedule_ptr ps, int from, int to)
2912 state_reset (curr_state);
2914 for (cycle = from; cycle <= to; cycle++)
2916 ps_insn_ptr crr_insn;
2917 /* Holds the remaining issue slots in the current row. */
2918 int can_issue_more = issue_rate;
2920 /* Walk through the DFA for the current row. */
2921 for (crr_insn = ps->rows[SMODULO (cycle, ps->ii)];
2923 crr_insn = crr_insn->next_in_row)
2925 rtx insn = crr_insn->node->insn;
2927 if (!NONDEBUG_INSN_P (insn))
2930 /* Check if there is room for the current insn. */
2931 if (!can_issue_more || state_dead_lock_p (curr_state))
2934 /* Update the DFA state and return with failure if the DFA found
2935 resource conflicts. */
2936 if (state_transition (curr_state, insn) >= 0)
2939 if (targetm.sched.variable_issue)
2941 targetm.sched.variable_issue (sched_dump, sched_verbose,
2942 insn, can_issue_more);
2943 /* A naked CLOBBER or USE generates no instruction, so don't
2944 let them consume issue slots. */
2945 else if (GET_CODE (PATTERN (insn)) != USE
2946 && GET_CODE (PATTERN (insn)) != CLOBBER)
2950 /* Advance the DFA to the next cycle. */
2951 advance_one_cycle ();
2956 /* Checks if the given node causes resource conflicts when added to PS at
2957 cycle C. If not the node is added to PS and returned; otherwise zero
2958 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
2959 cuid N must be come before/after (respectively) the node pointed to by
2960 PS_I when scheduled in the same cycle. */
2962 ps_add_node_check_conflicts (partial_schedule_ptr ps, ddg_node_ptr n,
2963 int c, sbitmap must_precede,
2964 sbitmap must_follow)
2966 int has_conflicts = 0;
2969 /* First add the node to the PS, if this succeeds check for
2970 conflicts, trying different issue slots in the same row. */
2971 if (! (ps_i = add_node_to_ps (ps, n, c, must_precede, must_follow)))
2972 return NULL; /* Failed to insert the node at the given cycle. */
2974 has_conflicts = ps_has_conflicts (ps, c, c)
2976 && ps_has_conflicts (ps,
2980 /* Try different issue slots to find one that the given node can be
2981 scheduled in without conflicts. */
2982 while (has_conflicts)
2984 if (! ps_insn_advance_column (ps, ps_i, must_follow))
2986 has_conflicts = ps_has_conflicts (ps, c, c)
2988 && ps_has_conflicts (ps,
2995 remove_node_from_ps (ps, ps_i);
2999 ps->min_cycle = MIN (ps->min_cycle, c);
3000 ps->max_cycle = MAX (ps->max_cycle, c);
3004 /* Calculate the stage count of the partial schedule PS. The calculation
3005 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3007 calculate_stage_count (partial_schedule_ptr ps, int rotation_amount)
3009 int new_min_cycle = PS_MIN_CYCLE (ps) - rotation_amount;
3010 int new_max_cycle = PS_MAX_CYCLE (ps) - rotation_amount;
3011 int stage_count = CALC_STAGE_COUNT (-1, new_min_cycle, ps->ii);
3013 /* The calculation of stage count is done adding the number of stages
3014 before cycle zero and after cycle zero. */
3015 stage_count += CALC_STAGE_COUNT (new_max_cycle, 0, ps->ii);
3020 /* Rotate the rows of PS such that insns scheduled at time
3021 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3023 rotate_partial_schedule (partial_schedule_ptr ps, int start_cycle)
3025 int i, row, backward_rotates;
3026 int last_row = ps->ii - 1;
3028 if (start_cycle == 0)
3031 backward_rotates = SMODULO (start_cycle, ps->ii);
3033 /* Revisit later and optimize this into a single loop. */
3034 for (i = 0; i < backward_rotates; i++)
3036 ps_insn_ptr first_row = ps->rows[0];
3037 int first_row_length = ps->rows_length[0];
3039 for (row = 0; row < last_row; row++)
3041 ps->rows[row] = ps->rows[row + 1];
3042 ps->rows_length[row] = ps->rows_length[row + 1];
3045 ps->rows[last_row] = first_row;
3046 ps->rows_length[last_row] = first_row_length;
3049 ps->max_cycle -= start_cycle;
3050 ps->min_cycle -= start_cycle;
3053 #endif /* INSN_SCHEDULING */
3056 gate_handle_sms (void)
3058 return (optimize > 0 && flag_modulo_sched);
3062 /* Run instruction scheduler. */
3063 /* Perform SMS module scheduling. */
3065 rest_of_handle_sms (void)
3067 #ifdef INSN_SCHEDULING
3070 /* Collect loop information to be used in SMS. */
3071 cfg_layout_initialize (0);
3074 /* Update the life information, because we add pseudos. */
3075 max_regno = max_reg_num ();
3077 /* Finalize layout changes. */
3079 if (bb->next_bb != EXIT_BLOCK_PTR)
3080 bb->aux = bb->next_bb;
3081 free_dominance_info (CDI_DOMINATORS);
3082 cfg_layout_finalize ();
3083 #endif /* INSN_SCHEDULING */
3087 struct rtl_opt_pass pass_sms =
3092 gate_handle_sms, /* gate */
3093 rest_of_handle_sms, /* execute */
3096 0, /* static_pass_number */
3098 0, /* properties_required */
3099 0, /* properties_provided */
3100 0, /* properties_destroyed */
3101 0, /* todo_flags_start */
3104 | TODO_verify_rtl_sharing
3105 | TODO_ggc_collect /* todo_flags_finish */