2006-02-09 Kaz Kojima <kkojima@gcc.gnu.org>
[official-gcc.git] / gcc / modulo-sched.c
blob86bf1a3a14f2a6eab489787c9893f4dcfbe07e2f
1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004, 2005, 2006
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 2, or (at your option) any later
11 version.
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
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21 02110-1301, USA. */
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "tm.h"
28 #include "toplev.h"
29 #include "rtl.h"
30 #include "tm_p.h"
31 #include "hard-reg-set.h"
32 #include "regs.h"
33 #include "function.h"
34 #include "flags.h"
35 #include "insn-config.h"
36 #include "insn-attr.h"
37 #include "except.h"
38 #include "toplev.h"
39 #include "recog.h"
40 #include "sched-int.h"
41 #include "target.h"
42 #include "cfglayout.h"
43 #include "cfgloop.h"
44 #include "cfghooks.h"
45 #include "expr.h"
46 #include "params.h"
47 #include "gcov-io.h"
48 #include "df.h"
49 #include "ddg.h"
50 #include "timevar.h"
51 #include "tree-pass.h"
53 #ifdef INSN_SCHEDULING
55 /* This file contains the implementation of the Swing Modulo Scheduler,
56 described in the following references:
57 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
58 Lifetime--sensitive modulo scheduling in a production environment.
59 IEEE Trans. on Comps., 50(3), March 2001
60 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
61 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
62 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
64 The basic structure is:
65 1. Build a data-dependence graph (DDG) for each loop.
66 2. Use the DDG to order the insns of a loop (not in topological order
67 necessarily, but rather) trying to place each insn after all its
68 predecessors _or_ after all its successors.
69 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
70 4. Use the ordering to perform list-scheduling of the loop:
71 1. Set II = MII. We will try to schedule the loop within II cycles.
72 2. Try to schedule the insns one by one according to the ordering.
73 For each insn compute an interval of cycles by considering already-
74 scheduled preds and succs (and associated latencies); try to place
75 the insn in the cycles of this window checking for potential
76 resource conflicts (using the DFA interface).
77 Note: this is different from the cycle-scheduling of schedule_insns;
78 here the insns are not scheduled monotonically top-down (nor bottom-
79 up).
80 3. If failed in scheduling all insns - bump II++ and try again, unless
81 II reaches an upper bound MaxII, in which case report failure.
82 5. If we succeeded in scheduling the loop within II cycles, we now
83 generate prolog and epilog, decrease the counter of the loop, and
84 perform modulo variable expansion for live ranges that span more than
85 II cycles (i.e. use register copies to prevent a def from overwriting
86 itself before reaching the use).
90 /* This page defines partial-schedule structures and functions for
91 modulo scheduling. */
93 typedef struct partial_schedule *partial_schedule_ptr;
94 typedef struct ps_insn *ps_insn_ptr;
96 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
97 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
99 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
100 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
102 /* Perform signed modulo, always returning a non-negative value. */
103 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
105 /* The number of different iterations the nodes in ps span, assuming
106 the stage boundaries are placed efficiently. */
107 #define PS_STAGE_COUNT(ps) ((PS_MAX_CYCLE (ps) - PS_MIN_CYCLE (ps) \
108 + 1 + (ps)->ii - 1) / (ps)->ii)
110 /* A single instruction in the partial schedule. */
111 struct ps_insn
113 /* The corresponding DDG_NODE. */
114 ddg_node_ptr node;
116 /* The (absolute) cycle in which the PS instruction is scheduled.
117 Same as SCHED_TIME (node). */
118 int cycle;
120 /* The next/prev PS_INSN in the same row. */
121 ps_insn_ptr next_in_row,
122 prev_in_row;
124 /* The number of nodes in the same row that come after this node. */
125 int row_rest_count;
128 /* Holds the partial schedule as an array of II rows. Each entry of the
129 array points to a linked list of PS_INSNs, which represents the
130 instructions that are scheduled for that row. */
131 struct partial_schedule
133 int ii; /* Number of rows in the partial schedule. */
134 int history; /* Threshold for conflict checking using DFA. */
136 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
137 ps_insn_ptr *rows;
139 /* The earliest absolute cycle of an insn in the partial schedule. */
140 int min_cycle;
142 /* The latest absolute cycle of an insn in the partial schedule. */
143 int max_cycle;
145 ddg_ptr g; /* The DDG of the insns in the partial schedule. */
148 /* We use this to record all the register replacements we do in
149 the kernel so we can undo SMS if it is not profitable. */
150 struct undo_replace_buff_elem
152 rtx insn;
153 rtx orig_reg;
154 rtx new_reg;
155 struct undo_replace_buff_elem *next;
160 static partial_schedule_ptr create_partial_schedule (int ii, ddg_ptr, int history);
161 static void free_partial_schedule (partial_schedule_ptr);
162 static void reset_partial_schedule (partial_schedule_ptr, int new_ii);
163 void print_partial_schedule (partial_schedule_ptr, FILE *);
164 static int kernel_number_of_cycles (rtx first_insn, rtx last_insn);
165 static ps_insn_ptr ps_add_node_check_conflicts (partial_schedule_ptr,
166 ddg_node_ptr node, int cycle,
167 sbitmap must_precede,
168 sbitmap must_follow);
169 static void rotate_partial_schedule (partial_schedule_ptr, int);
170 void set_row_column_for_ps (partial_schedule_ptr);
171 static bool ps_unschedule_node (partial_schedule_ptr, ddg_node_ptr );
174 /* This page defines constants and structures for the modulo scheduling
175 driver. */
177 /* As in haifa-sched.c: */
178 /* issue_rate is the number of insns that can be scheduled in the same
179 machine cycle. It can be defined in the config/mach/mach.h file,
180 otherwise we set it to 1. */
182 static int issue_rate;
184 static int sms_order_nodes (ddg_ptr, int, int * result);
185 static void set_node_sched_params (ddg_ptr);
186 static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int, int *);
187 static void permute_partial_schedule (partial_schedule_ptr ps, rtx last);
188 static void generate_prolog_epilog (partial_schedule_ptr ,struct loop * loop, rtx);
189 static void duplicate_insns_of_cycles (partial_schedule_ptr ps,
190 int from_stage, int to_stage,
191 int is_prolog);
193 #define SCHED_ASAP(x) (((node_sched_params_ptr)(x)->aux.info)->asap)
194 #define SCHED_TIME(x) (((node_sched_params_ptr)(x)->aux.info)->time)
195 #define SCHED_FIRST_REG_MOVE(x) \
196 (((node_sched_params_ptr)(x)->aux.info)->first_reg_move)
197 #define SCHED_NREG_MOVES(x) \
198 (((node_sched_params_ptr)(x)->aux.info)->nreg_moves)
199 #define SCHED_ROW(x) (((node_sched_params_ptr)(x)->aux.info)->row)
200 #define SCHED_STAGE(x) (((node_sched_params_ptr)(x)->aux.info)->stage)
201 #define SCHED_COLUMN(x) (((node_sched_params_ptr)(x)->aux.info)->column)
203 /* The scheduling parameters held for each node. */
204 typedef struct node_sched_params
206 int asap; /* A lower-bound on the absolute scheduling cycle. */
207 int time; /* The absolute scheduling cycle (time >= asap). */
209 /* The following field (first_reg_move) is a pointer to the first
210 register-move instruction added to handle the modulo-variable-expansion
211 of the register defined by this node. This register-move copies the
212 original register defined by the node. */
213 rtx first_reg_move;
215 /* The number of register-move instructions added, immediately preceding
216 first_reg_move. */
217 int nreg_moves;
219 int row; /* Holds time % ii. */
220 int stage; /* Holds time / ii. */
222 /* The column of a node inside the ps. If nodes u, v are on the same row,
223 u will precede v if column (u) < column (v). */
224 int column;
225 } *node_sched_params_ptr;
228 /* The following three functions are copied from the current scheduler
229 code in order to use sched_analyze() for computing the dependencies.
230 They are used when initializing the sched_info structure. */
231 static const char *
232 sms_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED)
234 static char tmp[80];
236 sprintf (tmp, "i%4d", INSN_UID (insn));
237 return tmp;
240 static int
241 contributes_to_priority (rtx next, rtx insn)
243 return BLOCK_NUM (next) == BLOCK_NUM (insn);
246 static void
247 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
248 regset cond_exec ATTRIBUTE_UNUSED,
249 regset used ATTRIBUTE_UNUSED,
250 regset set ATTRIBUTE_UNUSED)
254 static struct sched_info sms_sched_info =
256 NULL,
257 NULL,
258 NULL,
259 NULL,
260 NULL,
261 sms_print_insn,
262 contributes_to_priority,
263 compute_jump_reg_dependencies,
264 NULL, NULL,
265 NULL, NULL,
266 0, 0, 0
270 /* Return the register decremented and tested in INSN,
271 or zero if it is not a decrement-and-branch insn. */
273 static rtx
274 doloop_register_get (rtx insn ATTRIBUTE_UNUSED)
276 #ifdef HAVE_doloop_end
277 rtx pattern, reg, condition;
279 if (! JUMP_P (insn))
280 return NULL_RTX;
282 pattern = PATTERN (insn);
283 condition = doloop_condition_get (pattern);
284 if (! condition)
285 return NULL_RTX;
287 if (REG_P (XEXP (condition, 0)))
288 reg = XEXP (condition, 0);
289 else if (GET_CODE (XEXP (condition, 0)) == PLUS
290 && REG_P (XEXP (XEXP (condition, 0), 0)))
291 reg = XEXP (XEXP (condition, 0), 0);
292 else
293 gcc_unreachable ();
295 return reg;
296 #else
297 return NULL_RTX;
298 #endif
301 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
302 that the number of iterations is a compile-time constant. If so,
303 return the rtx that sets COUNT_REG to a constant, and set COUNT to
304 this constant. Otherwise return 0. */
305 static rtx
306 const_iteration_count (rtx count_reg, basic_block pre_header,
307 HOST_WIDEST_INT * count)
309 rtx insn;
310 rtx head, tail;
312 if (! pre_header)
313 return NULL_RTX;
315 get_block_head_tail (pre_header->index, &head, &tail);
317 for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn))
318 if (INSN_P (insn) && single_set (insn) &&
319 rtx_equal_p (count_reg, SET_DEST (single_set (insn))))
321 rtx pat = single_set (insn);
323 if (GET_CODE (SET_SRC (pat)) == CONST_INT)
325 *count = INTVAL (SET_SRC (pat));
326 return insn;
329 return NULL_RTX;
332 return NULL_RTX;
335 /* A very simple resource-based lower bound on the initiation interval.
336 ??? Improve the accuracy of this bound by considering the
337 utilization of various units. */
338 static int
339 res_MII (ddg_ptr g)
341 return (g->num_nodes / issue_rate);
345 /* Points to the array that contains the sched data for each node. */
346 static node_sched_params_ptr node_sched_params;
348 /* Allocate sched_params for each node and initialize it. Assumes that
349 the aux field of each node contain the asap bound (computed earlier),
350 and copies it into the sched_params field. */
351 static void
352 set_node_sched_params (ddg_ptr g)
354 int i;
356 /* Allocate for each node in the DDG a place to hold the "sched_data". */
357 /* Initialize ASAP/ALAP/HIGHT to zero. */
358 node_sched_params = (node_sched_params_ptr)
359 xcalloc (g->num_nodes,
360 sizeof (struct node_sched_params));
362 /* Set the pointer of the general data of the node to point to the
363 appropriate sched_params structure. */
364 for (i = 0; i < g->num_nodes; i++)
366 /* Watch out for aliasing problems? */
367 node_sched_params[i].asap = g->nodes[i].aux.count;
368 g->nodes[i].aux.info = &node_sched_params[i];
372 static void
373 print_node_sched_params (FILE * file, int num_nodes)
375 int i;
377 if (! file)
378 return;
379 for (i = 0; i < num_nodes; i++)
381 node_sched_params_ptr nsp = &node_sched_params[i];
382 rtx reg_move = nsp->first_reg_move;
383 int j;
385 fprintf (file, "Node %d:\n", i);
386 fprintf (file, " asap = %d:\n", nsp->asap);
387 fprintf (file, " time = %d:\n", nsp->time);
388 fprintf (file, " nreg_moves = %d:\n", nsp->nreg_moves);
389 for (j = 0; j < nsp->nreg_moves; j++)
391 fprintf (file, " reg_move = ");
392 print_rtl_single (file, reg_move);
393 reg_move = PREV_INSN (reg_move);
398 /* Calculate an upper bound for II. SMS should not schedule the loop if it
399 requires more cycles than this bound. Currently set to the sum of the
400 longest latency edge for each node. Reset based on experiments. */
401 static int
402 calculate_maxii (ddg_ptr g)
404 int i;
405 int maxii = 0;
407 for (i = 0; i < g->num_nodes; i++)
409 ddg_node_ptr u = &g->nodes[i];
410 ddg_edge_ptr e;
411 int max_edge_latency = 0;
413 for (e = u->out; e; e = e->next_out)
414 max_edge_latency = MAX (max_edge_latency, e->latency);
416 maxii += max_edge_latency;
418 return maxii;
422 Breaking intra-loop register anti-dependences:
423 Each intra-loop register anti-dependence implies a cross-iteration true
424 dependence of distance 1. Therefore, we can remove such false dependencies
425 and figure out if the partial schedule broke them by checking if (for a
426 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
427 if so generate a register move. The number of such moves is equal to:
428 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
429 nreg_moves = ----------------------------------- + 1 - { dependence.
430 ii { 1 if not.
432 static struct undo_replace_buff_elem *
433 generate_reg_moves (partial_schedule_ptr ps)
435 ddg_ptr g = ps->g;
436 int ii = ps->ii;
437 int i;
438 struct undo_replace_buff_elem *reg_move_replaces = NULL;
440 for (i = 0; i < g->num_nodes; i++)
442 ddg_node_ptr u = &g->nodes[i];
443 ddg_edge_ptr e;
444 int nreg_moves = 0, i_reg_move;
445 sbitmap *uses_of_defs;
446 rtx last_reg_move;
447 rtx prev_reg, old_reg;
449 /* Compute the number of reg_moves needed for u, by looking at life
450 ranges started at u (excluding self-loops). */
451 for (e = u->out; e; e = e->next_out)
452 if (e->type == TRUE_DEP && e->dest != e->src)
454 int nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
456 if (e->distance == 1)
457 nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
459 /* If dest precedes src in the schedule of the kernel, then dest
460 will read before src writes and we can save one reg_copy. */
461 if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)
462 && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))
463 nreg_moves4e--;
465 nreg_moves = MAX (nreg_moves, nreg_moves4e);
468 if (nreg_moves == 0)
469 continue;
471 /* Every use of the register defined by node may require a different
472 copy of this register, depending on the time the use is scheduled.
473 Set a bitmap vector, telling which nodes use each copy of this
474 register. */
475 uses_of_defs = sbitmap_vector_alloc (nreg_moves, g->num_nodes);
476 sbitmap_vector_zero (uses_of_defs, nreg_moves);
477 for (e = u->out; e; e = e->next_out)
478 if (e->type == TRUE_DEP && e->dest != e->src)
480 int dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
482 if (e->distance == 1)
483 dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
485 if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)
486 && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))
487 dest_copy--;
489 if (dest_copy)
490 SET_BIT (uses_of_defs[dest_copy - 1], e->dest->cuid);
493 /* Now generate the reg_moves, attaching relevant uses to them. */
494 SCHED_NREG_MOVES (u) = nreg_moves;
495 old_reg = prev_reg = copy_rtx (SET_DEST (single_set (u->insn)));
496 last_reg_move = u->insn;
498 for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
500 unsigned int i_use = 0;
501 rtx new_reg = gen_reg_rtx (GET_MODE (prev_reg));
502 rtx reg_move = gen_move_insn (new_reg, prev_reg);
503 sbitmap_iterator sbi;
505 add_insn_before (reg_move, last_reg_move);
506 last_reg_move = reg_move;
508 if (!SCHED_FIRST_REG_MOVE (u))
509 SCHED_FIRST_REG_MOVE (u) = reg_move;
511 EXECUTE_IF_SET_IN_SBITMAP (uses_of_defs[i_reg_move], 0, i_use, sbi)
513 struct undo_replace_buff_elem *rep;
515 rep = (struct undo_replace_buff_elem *)
516 xcalloc (1, sizeof (struct undo_replace_buff_elem));
517 rep->insn = g->nodes[i_use].insn;
518 rep->orig_reg = old_reg;
519 rep->new_reg = new_reg;
521 if (! reg_move_replaces)
522 reg_move_replaces = rep;
523 else
525 rep->next = reg_move_replaces;
526 reg_move_replaces = rep;
529 replace_rtx (g->nodes[i_use].insn, old_reg, new_reg);
532 prev_reg = new_reg;
535 return reg_move_replaces;
538 /* We call this when we want to undo the SMS schedule for a given loop.
539 One of the things that we do is to delete the register moves generated
540 for the sake of SMS; this function deletes the register move instructions
541 recorded in the undo buffer. */
542 static void
543 undo_generate_reg_moves (partial_schedule_ptr ps,
544 struct undo_replace_buff_elem *reg_move_replaces)
546 int i,j;
548 for (i = 0; i < ps->g->num_nodes; i++)
550 ddg_node_ptr u = &ps->g->nodes[i];
551 rtx prev;
552 rtx crr = SCHED_FIRST_REG_MOVE (u);
554 for (j = 0; j < SCHED_NREG_MOVES (u); j++)
556 prev = PREV_INSN (crr);
557 delete_insn (crr);
558 crr = prev;
560 SCHED_FIRST_REG_MOVE (u) = NULL_RTX;
563 while (reg_move_replaces)
565 struct undo_replace_buff_elem *rep = reg_move_replaces;
567 reg_move_replaces = reg_move_replaces->next;
568 replace_rtx (rep->insn, rep->new_reg, rep->orig_reg);
572 /* Free memory allocated for the undo buffer. */
573 static void
574 free_undo_replace_buff (struct undo_replace_buff_elem *reg_move_replaces)
577 while (reg_move_replaces)
579 struct undo_replace_buff_elem *rep = reg_move_replaces;
581 reg_move_replaces = reg_move_replaces->next;
582 free (rep);
586 /* Bump the SCHED_TIMEs of all nodes to start from zero. Set the values
587 of SCHED_ROW and SCHED_STAGE. */
588 static void
589 normalize_sched_times (partial_schedule_ptr ps)
591 int i;
592 ddg_ptr g = ps->g;
593 int amount = PS_MIN_CYCLE (ps);
594 int ii = ps->ii;
596 /* Don't include the closing branch assuming that it is the last node. */
597 for (i = 0; i < g->num_nodes - 1; i++)
599 ddg_node_ptr u = &g->nodes[i];
600 int normalized_time = SCHED_TIME (u) - amount;
602 gcc_assert (normalized_time >= 0);
604 SCHED_TIME (u) = normalized_time;
605 SCHED_ROW (u) = normalized_time % ii;
606 SCHED_STAGE (u) = normalized_time / ii;
610 /* Set SCHED_COLUMN of each node according to its position in PS. */
611 static void
612 set_columns_for_ps (partial_schedule_ptr ps)
614 int row;
616 for (row = 0; row < ps->ii; row++)
618 ps_insn_ptr cur_insn = ps->rows[row];
619 int column = 0;
621 for (; cur_insn; cur_insn = cur_insn->next_in_row)
622 SCHED_COLUMN (cur_insn->node) = column++;
626 /* Permute the insns according to their order in PS, from row 0 to
627 row ii-1, and position them right before LAST. This schedules
628 the insns of the loop kernel. */
629 static void
630 permute_partial_schedule (partial_schedule_ptr ps, rtx last)
632 int ii = ps->ii;
633 int row;
634 ps_insn_ptr ps_ij;
636 for (row = 0; row < ii ; row++)
637 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
638 if (PREV_INSN (last) != ps_ij->node->insn)
639 reorder_insns_nobb (ps_ij->node->first_note, ps_ij->node->insn,
640 PREV_INSN (last));
643 /* As part of undoing SMS we return to the original ordering of the
644 instructions inside the loop kernel. Given the partial schedule PS, this
645 function returns the ordering of the instruction according to their CUID
646 in the DDG (PS->G), which is the original order of the instruction before
647 performing SMS. */
648 static void
649 undo_permute_partial_schedule (partial_schedule_ptr ps, rtx last)
651 int i;
653 for (i = 0 ; i < ps->g->num_nodes; i++)
654 if (last == ps->g->nodes[i].insn
655 || last == ps->g->nodes[i].first_note)
656 break;
657 else if (PREV_INSN (last) != ps->g->nodes[i].insn)
658 reorder_insns_nobb (ps->g->nodes[i].first_note, ps->g->nodes[i].insn,
659 PREV_INSN (last));
662 /* Used to generate the prologue & epilogue. Duplicate the subset of
663 nodes whose stages are between FROM_STAGE and TO_STAGE (inclusive
664 of both), together with a prefix/suffix of their reg_moves. */
665 static void
666 duplicate_insns_of_cycles (partial_schedule_ptr ps, int from_stage,
667 int to_stage, int for_prolog)
669 int row;
670 ps_insn_ptr ps_ij;
672 for (row = 0; row < ps->ii; row++)
673 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
675 ddg_node_ptr u_node = ps_ij->node;
676 int j, i_reg_moves;
677 rtx reg_move = NULL_RTX;
679 if (for_prolog)
681 /* SCHED_STAGE (u_node) >= from_stage == 0. Generate increasing
682 number of reg_moves starting with the second occurrence of
683 u_node, which is generated if its SCHED_STAGE <= to_stage. */
684 i_reg_moves = to_stage - SCHED_STAGE (u_node) + 1;
685 i_reg_moves = MAX (i_reg_moves, 0);
686 i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));
688 /* The reg_moves start from the *first* reg_move backwards. */
689 if (i_reg_moves)
691 reg_move = SCHED_FIRST_REG_MOVE (u_node);
692 for (j = 1; j < i_reg_moves; j++)
693 reg_move = PREV_INSN (reg_move);
696 else /* It's for the epilog. */
698 /* SCHED_STAGE (u_node) <= to_stage. Generate all reg_moves,
699 starting to decrease one stage after u_node no longer occurs;
700 that is, generate all reg_moves until
701 SCHED_STAGE (u_node) == from_stage - 1. */
702 i_reg_moves = SCHED_NREG_MOVES (u_node)
703 - (from_stage - SCHED_STAGE (u_node) - 1);
704 i_reg_moves = MAX (i_reg_moves, 0);
705 i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));
707 /* The reg_moves start from the *last* reg_move forwards. */
708 if (i_reg_moves)
710 reg_move = SCHED_FIRST_REG_MOVE (u_node);
711 for (j = 1; j < SCHED_NREG_MOVES (u_node); j++)
712 reg_move = PREV_INSN (reg_move);
716 for (j = 0; j < i_reg_moves; j++, reg_move = NEXT_INSN (reg_move))
717 emit_insn (copy_rtx (PATTERN (reg_move)));
718 if (SCHED_STAGE (u_node) >= from_stage
719 && SCHED_STAGE (u_node) <= to_stage)
720 duplicate_insn_chain (u_node->first_note, u_node->insn);
725 /* Generate the instructions (including reg_moves) for prolog & epilog. */
726 static void
727 generate_prolog_epilog (partial_schedule_ptr ps, struct loop * loop, rtx count_reg)
729 int i;
730 int last_stage = PS_STAGE_COUNT (ps) - 1;
731 edge e;
733 /* Generate the prolog, inserting its insns on the loop-entry edge. */
734 start_sequence ();
736 if (count_reg)
737 /* Generate a subtract instruction at the beginning of the prolog to
738 adjust the loop count by STAGE_COUNT. */
739 emit_insn (gen_sub2_insn (count_reg, GEN_INT (last_stage)));
741 for (i = 0; i < last_stage; i++)
742 duplicate_insns_of_cycles (ps, 0, i, 1);
744 /* Put the prolog , on the one and only entry edge. */
745 e = loop_preheader_edge (loop);
746 loop_split_edge_with(e , get_insns());
748 end_sequence ();
750 /* Generate the epilog, inserting its insns on the loop-exit edge. */
751 start_sequence ();
753 for (i = 0; i < last_stage; i++)
754 duplicate_insns_of_cycles (ps, i + 1, last_stage, 0);
756 /* Put the epilogue on the one and only one exit edge. */
757 gcc_assert (loop->single_exit);
758 e = loop->single_exit;
759 loop_split_edge_with(e , get_insns());
760 end_sequence ();
763 /* Return the line note insn preceding INSN, for debugging. Taken from
764 emit-rtl.c. */
765 static rtx
766 find_line_note (rtx insn)
768 for (; insn; insn = PREV_INSN (insn))
769 if (NOTE_P (insn)
770 && NOTE_LINE_NUMBER (insn) >= 0)
771 break;
773 return insn;
776 /* Return true if all the BBs of the loop are empty except the
777 loop header. */
778 static bool
779 loop_single_full_bb_p (struct loop *loop)
781 unsigned i;
782 basic_block *bbs = get_loop_body (loop);
784 for (i = 0; i < loop->num_nodes ; i++)
786 rtx head, tail;
787 bool empty_bb = true;
789 if (bbs[i] == loop->header)
790 continue;
792 /* Make sure that basic blocks other than the header
793 have only notes labels or jumps. */
794 get_block_head_tail (bbs[i]->index, &head, &tail);
795 for (; head != NEXT_INSN (tail); head = NEXT_INSN (head))
797 if (NOTE_P (head) || LABEL_P (head)
798 || (INSN_P (head) && JUMP_P (head)))
799 continue;
800 empty_bb = false;
801 break;
804 if (! empty_bb)
806 free (bbs);
807 return false;
810 free (bbs);
811 return true;
814 /* A simple loop from SMS point of view; it is a loop that is composed of
815 either a single basic block or two BBs - a header and a latch. */
816 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
817 && (EDGE_COUNT (loop->latch->preds) == 1) \
818 && (EDGE_COUNT (loop->latch->succs) == 1))
820 /* Return true if the loop is in its canonical form and false if not.
821 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
822 static bool
823 loop_canon_p (struct loop *loop)
826 if (loop->inner || ! loop->outer)
827 return false;
829 if (!loop->single_exit)
831 if (dump_file)
833 rtx line_note = find_line_note (BB_END (loop->header));
835 fprintf (dump_file, "SMS loop many exits ");
836 if (line_note)
838 expanded_location xloc;
839 NOTE_EXPANDED_LOCATION (xloc, line_note);
840 fprintf (dump_file, " %s %d (file, line)\n",
841 xloc.file, xloc.line);
844 return false;
847 if (! SIMPLE_SMS_LOOP_P (loop) && ! loop_single_full_bb_p (loop))
849 if (dump_file)
851 rtx line_note = find_line_note (BB_END (loop->header));
853 fprintf (dump_file, "SMS loop many BBs. ");
854 if (line_note)
856 expanded_location xloc;
857 NOTE_EXPANDED_LOCATION (xloc, line_note);
858 fprintf (dump_file, " %s %d (file, line)\n",
859 xloc.file, xloc.line);
862 return false;
865 return true;
868 /* If there are more than one entry for the loop,
869 make it one by splitting the first entry edge and
870 redirecting the others to the new BB. */
871 static void
872 canon_loop (struct loop *loop)
874 edge e;
875 edge_iterator i;
877 /* Avoid annoying special cases of edges going to exit
878 block. */
879 FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR->preds)
880 if ((e->flags & EDGE_FALLTHRU) && (EDGE_COUNT (e->src->succs) > 1))
881 loop_split_edge_with (e, NULL_RTX);
883 if (loop->latch == loop->header
884 || EDGE_COUNT (loop->latch->succs) > 1)
886 FOR_EACH_EDGE (e, i, loop->header->preds)
887 if (e->src == loop->latch)
888 break;
889 loop_split_edge_with (e, NULL_RTX);
893 /* Main entry point, perform SMS scheduling on the loops of the function
894 that consist of single basic blocks. */
895 static void
896 sms_schedule (void)
898 static int passes = 0;
899 rtx insn;
900 ddg_ptr *g_arr, g;
901 int * node_order;
902 int maxii;
903 unsigned i,num_loops;
904 partial_schedule_ptr ps;
905 struct df *df;
906 struct loops *loops;
907 basic_block bb = NULL;
908 /* vars to the versioning only if needed*/
909 struct loop * nloop;
910 basic_block condition_bb = NULL;
911 edge latch_edge;
912 gcov_type trip_count = 0;
914 loops = loop_optimizer_init (LOOPS_HAVE_PREHEADERS
915 | LOOPS_HAVE_MARKED_SINGLE_EXITS);
916 if (!loops)
917 return; /* There is no loops to schedule. */
919 /* Initialize issue_rate. */
920 if (targetm.sched.issue_rate)
922 int temp = reload_completed;
924 reload_completed = 1;
925 issue_rate = targetm.sched.issue_rate ();
926 reload_completed = temp;
928 else
929 issue_rate = 1;
931 /* Initialize the scheduler. */
932 current_sched_info = &sms_sched_info;
933 sched_init ();
935 /* Init Data Flow analysis, to be used in interloop dep calculation. */
936 df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES | DF_SUBREGS);
937 df_rd_add_problem (df);
938 df_ru_add_problem (df);
939 df_chain_add_problem (df, DF_DU_CHAIN | DF_UD_CHAIN);
940 df_analyze (df);
942 /* Allocate memory to hold the DDG array one entry for each loop.
943 We use loop->num as index into this array. */
944 g_arr = XCNEWVEC (ddg_ptr, loops->num);
947 /* Build DDGs for all the relevant loops and hold them in G_ARR
948 indexed by the loop index. */
949 for (i = 0; i < loops->num; i++)
951 rtx head, tail;
952 rtx count_reg;
953 struct loop *loop = loops->parray[i];
955 /* For debugging. */
956 if ((passes++ > MAX_SMS_LOOP_NUMBER) && (MAX_SMS_LOOP_NUMBER != -1))
958 if (dump_file)
959 fprintf (dump_file, "SMS reached MAX_PASSES... \n");
961 break;
964 if (! loop_canon_p (loop))
965 continue;
967 if (! loop_single_full_bb_p (loop))
968 continue;
970 bb = loop->header;
972 get_block_head_tail (bb->index, &head, &tail);
973 latch_edge = loop_latch_edge (loop);
974 gcc_assert (loop->single_exit);
975 if (loop->single_exit->count)
976 trip_count = latch_edge->count / loop->single_exit->count;
978 /* Perfrom SMS only on loops that their average count is above threshold. */
980 if ( latch_edge->count
981 && (latch_edge->count < loop->single_exit->count * SMS_LOOP_AVERAGE_COUNT_THRESHOLD))
983 if (dump_file)
985 rtx line_note = find_line_note (tail);
987 if (line_note)
989 expanded_location xloc;
990 NOTE_EXPANDED_LOCATION (xloc, line_note);
991 fprintf (dump_file, "SMS bb %s %d (file, line)\n",
992 xloc.file, xloc.line);
994 fprintf (dump_file, "SMS single-bb-loop\n");
995 if (profile_info && flag_branch_probabilities)
997 fprintf (dump_file, "SMS loop-count ");
998 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
999 (HOST_WIDEST_INT) bb->count);
1000 fprintf (dump_file, "\n");
1001 fprintf (dump_file, "SMS trip-count ");
1002 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1003 (HOST_WIDEST_INT) trip_count);
1004 fprintf (dump_file, "\n");
1005 fprintf (dump_file, "SMS profile-sum-max ");
1006 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1007 (HOST_WIDEST_INT) profile_info->sum_max);
1008 fprintf (dump_file, "\n");
1011 continue;
1014 /* Make sure this is a doloop. */
1015 if ( !(count_reg = doloop_register_get (tail)))
1016 continue;
1018 /* Don't handle BBs with calls or barriers, or !single_set insns. */
1019 for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn))
1020 if (CALL_P (insn)
1021 || BARRIER_P (insn)
1022 || (INSN_P (insn) && !JUMP_P (insn)
1023 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE))
1024 break;
1026 if (insn != NEXT_INSN (tail))
1028 if (dump_file)
1030 if (CALL_P (insn))
1031 fprintf (dump_file, "SMS loop-with-call\n");
1032 else if (BARRIER_P (insn))
1033 fprintf (dump_file, "SMS loop-with-barrier\n");
1034 else
1035 fprintf (dump_file, "SMS loop-with-not-single-set\n");
1036 print_rtl_single (dump_file, insn);
1039 continue;
1042 if (! (g = create_ddg (bb, df, 0)))
1044 if (dump_file)
1045 fprintf (dump_file, "SMS doloop\n");
1046 continue;
1049 g_arr[i] = g;
1052 /* Release Data Flow analysis data structures. */
1053 df_finish (df);
1054 df = NULL;
1056 /* We don't want to perform SMS on new loops - created by versioning. */
1057 num_loops = loops->num;
1058 /* Go over the built DDGs and perfrom SMS for each one of them. */
1059 for (i = 0; i < num_loops; i++)
1061 rtx head, tail;
1062 rtx count_reg, count_init;
1063 int mii, rec_mii;
1064 unsigned stage_count = 0;
1065 HOST_WIDEST_INT loop_count = 0;
1066 struct loop *loop = loops->parray[i];
1068 if (! (g = g_arr[i]))
1069 continue;
1071 if (dump_file)
1072 print_ddg (dump_file, g);
1074 get_block_head_tail (loop->header->index, &head, &tail);
1076 latch_edge = loop_latch_edge (loop);
1077 gcc_assert (loop->single_exit);
1078 if (loop->single_exit->count)
1079 trip_count = latch_edge->count / loop->single_exit->count;
1081 if (dump_file)
1083 rtx line_note = find_line_note (tail);
1085 if (line_note)
1087 expanded_location xloc;
1088 NOTE_EXPANDED_LOCATION (xloc, line_note);
1089 fprintf (dump_file, "SMS bb %s %d (file, line)\n",
1090 xloc.file, xloc.line);
1092 fprintf (dump_file, "SMS single-bb-loop\n");
1093 if (profile_info && flag_branch_probabilities)
1095 fprintf (dump_file, "SMS loop-count ");
1096 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1097 (HOST_WIDEST_INT) bb->count);
1098 fprintf (dump_file, "\n");
1099 fprintf (dump_file, "SMS profile-sum-max ");
1100 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1101 (HOST_WIDEST_INT) profile_info->sum_max);
1102 fprintf (dump_file, "\n");
1104 fprintf (dump_file, "SMS doloop\n");
1105 fprintf (dump_file, "SMS built-ddg %d\n", g->num_nodes);
1106 fprintf (dump_file, "SMS num-loads %d\n", g->num_loads);
1107 fprintf (dump_file, "SMS num-stores %d\n", g->num_stores);
1111 /* In case of th loop have doloop register it gets special
1112 handling. */
1113 count_init = NULL_RTX;
1114 if ((count_reg = doloop_register_get (tail)))
1116 basic_block pre_header;
1118 pre_header = loop_preheader_edge (loop)->src;
1119 count_init = const_iteration_count (count_reg, pre_header,
1120 &loop_count);
1122 gcc_assert (count_reg);
1124 if (dump_file && count_init)
1126 fprintf (dump_file, "SMS const-doloop ");
1127 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1128 loop_count);
1129 fprintf (dump_file, "\n");
1132 node_order = XNEWVEC (int, g->num_nodes);
1134 mii = 1; /* Need to pass some estimate of mii. */
1135 rec_mii = sms_order_nodes (g, mii, node_order);
1136 mii = MAX (res_MII (g), rec_mii);
1137 maxii = (calculate_maxii (g) * SMS_MAX_II_FACTOR) / 100;
1139 if (dump_file)
1140 fprintf (dump_file, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1141 rec_mii, mii, maxii);
1143 /* After sms_order_nodes and before sms_schedule_by_order, to copy over
1144 ASAP. */
1145 set_node_sched_params (g);
1147 ps = sms_schedule_by_order (g, mii, maxii, node_order);
1149 if (ps)
1150 stage_count = PS_STAGE_COUNT (ps);
1152 /* Stage count of 1 means that there is no interleaving between
1153 iterations, let the scheduling passes do the job. */
1154 if (stage_count < 1
1155 || (count_init && (loop_count <= stage_count))
1156 || (flag_branch_probabilities && (trip_count <= stage_count)))
1158 if (dump_file)
1160 fprintf (dump_file, "SMS failed... \n");
1161 fprintf (dump_file, "SMS sched-failed (stage-count=%d, loop-count=", stage_count);
1162 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, loop_count);
1163 fprintf (dump_file, ", trip-count=");
1164 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, trip_count);
1165 fprintf (dump_file, ")\n");
1167 continue;
1169 else
1171 int orig_cycles = kernel_number_of_cycles (BB_HEAD (g->bb), BB_END (g->bb));
1172 int new_cycles;
1173 struct undo_replace_buff_elem *reg_move_replaces;
1175 if (dump_file)
1177 fprintf (dump_file,
1178 "SMS succeeded %d %d (with ii, sc)\n", ps->ii,
1179 stage_count);
1180 print_partial_schedule (ps, dump_file);
1181 fprintf (dump_file,
1182 "SMS Branch (%d) will later be scheduled at cycle %d.\n",
1183 g->closing_branch->cuid, PS_MIN_CYCLE (ps) - 1);
1186 /* Set the stage boundaries. If the DDG is built with closing_branch_deps,
1187 the closing_branch was scheduled and should appear in the last (ii-1)
1188 row. Otherwise, we are free to schedule the branch, and we let nodes
1189 that were scheduled at the first PS_MIN_CYCLE cycle appear in the first
1190 row; this should reduce stage_count to minimum. */
1191 normalize_sched_times (ps);
1192 rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
1193 set_columns_for_ps (ps);
1195 /* Generate the kernel just to be able to measure its cycles. */
1196 permute_partial_schedule (ps, g->closing_branch->first_note);
1197 reg_move_replaces = generate_reg_moves (ps);
1199 /* Get the number of cycles the new kernel expect to execute in. */
1200 new_cycles = kernel_number_of_cycles (BB_HEAD (g->bb), BB_END (g->bb));
1202 /* Get back to the original loop so we can do loop versioning. */
1203 undo_permute_partial_schedule (ps, g->closing_branch->first_note);
1204 if (reg_move_replaces)
1205 undo_generate_reg_moves (ps, reg_move_replaces);
1207 if ( new_cycles >= orig_cycles)
1209 /* SMS is not profitable so undo the permutation and reg move generation
1210 and return the kernel to its original state. */
1211 if (dump_file)
1212 fprintf (dump_file, "Undoing SMS because it is not profitable.\n");
1215 else
1217 canon_loop (loop);
1219 /* case the BCT count is not known , Do loop-versioning */
1220 if (count_reg && ! count_init)
1222 rtx comp_rtx = gen_rtx_fmt_ee (GT, VOIDmode, count_reg,
1223 GEN_INT(stage_count));
1225 nloop = loop_version (loops, loop, comp_rtx, &condition_bb,
1226 true);
1229 /* Set new iteration count of loop kernel. */
1230 if (count_reg && count_init)
1231 SET_SRC (single_set (count_init)) = GEN_INT (loop_count
1232 - stage_count + 1);
1234 /* Now apply the scheduled kernel to the RTL of the loop. */
1235 permute_partial_schedule (ps, g->closing_branch->first_note);
1237 /* Mark this loop as software pipelined so the later
1238 scheduling passes doesn't touch it. */
1239 if (! flag_resched_modulo_sched)
1240 g->bb->flags |= BB_DISABLE_SCHEDULE;
1241 /* The life-info is not valid any more. */
1242 g->bb->flags |= BB_DIRTY;
1244 reg_move_replaces = generate_reg_moves (ps);
1245 if (dump_file)
1246 print_node_sched_params (dump_file, g->num_nodes);
1247 /* Generate prolog and epilog. */
1248 if (count_reg && !count_init)
1249 generate_prolog_epilog (ps, loop, count_reg);
1250 else
1251 generate_prolog_epilog (ps, loop, NULL_RTX);
1253 free_undo_replace_buff (reg_move_replaces);
1256 free_partial_schedule (ps);
1257 free (node_sched_params);
1258 free (node_order);
1259 free_ddg (g);
1262 /* Release scheduler data, needed until now because of DFA. */
1263 sched_finish ();
1264 loop_optimizer_finalize (loops);
1267 /* The SMS scheduling algorithm itself
1268 -----------------------------------
1269 Input: 'O' an ordered list of insns of a loop.
1270 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1272 'Q' is the empty Set
1273 'PS' is the partial schedule; it holds the currently scheduled nodes with
1274 their cycle/slot.
1275 'PSP' previously scheduled predecessors.
1276 'PSS' previously scheduled successors.
1277 't(u)' the cycle where u is scheduled.
1278 'l(u)' is the latency of u.
1279 'd(v,u)' is the dependence distance from v to u.
1280 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1281 the node ordering phase.
1282 'check_hardware_resources_conflicts(u, PS, c)'
1283 run a trace around cycle/slot through DFA model
1284 to check resource conflicts involving instruction u
1285 at cycle c given the partial schedule PS.
1286 'add_to_partial_schedule_at_time(u, PS, c)'
1287 Add the node/instruction u to the partial schedule
1288 PS at time c.
1289 'calculate_register_pressure(PS)'
1290 Given a schedule of instructions, calculate the register
1291 pressure it implies. One implementation could be the
1292 maximum number of overlapping live ranges.
1293 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1294 registers available in the hardware.
1296 1. II = MII.
1297 2. PS = empty list
1298 3. for each node u in O in pre-computed order
1299 4. if (PSP(u) != Q && PSS(u) == Q) then
1300 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1301 6. start = Early_start; end = Early_start + II - 1; step = 1
1302 11. else if (PSP(u) == Q && PSS(u) != Q) then
1303 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1304 13. start = Late_start; end = Late_start - II + 1; step = -1
1305 14. else if (PSP(u) != Q && PSS(u) != Q) then
1306 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1307 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1308 17. start = Early_start;
1309 18. end = min(Early_start + II - 1 , Late_start);
1310 19. step = 1
1311 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1312 21. start = ASAP(u); end = start + II - 1; step = 1
1313 22. endif
1315 23. success = false
1316 24. for (c = start ; c != end ; c += step)
1317 25. if check_hardware_resources_conflicts(u, PS, c) then
1318 26. add_to_partial_schedule_at_time(u, PS, c)
1319 27. success = true
1320 28. break
1321 29. endif
1322 30. endfor
1323 31. if (success == false) then
1324 32. II = II + 1
1325 33. if (II > maxII) then
1326 34. finish - failed to schedule
1327 35. endif
1328 36. goto 2.
1329 37. endif
1330 38. endfor
1331 39. if (calculate_register_pressure(PS) > maxRP) then
1332 40. goto 32.
1333 41. endif
1334 42. compute epilogue & prologue
1335 43. finish - succeeded to schedule
1338 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1339 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1340 set to 0 to save compile time. */
1341 #define DFA_HISTORY SMS_DFA_HISTORY
1343 /* Given the partial schedule PS, this function calculates and returns the
1344 cycles in which we can schedule the node with the given index I.
1345 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1346 noticed that there are several cases in which we fail to SMS the loop
1347 because the sched window of a node is empty due to tight data-deps. In
1348 such cases we want to unschedule some of the predecessors/successors
1349 until we get non-empty scheduling window. It returns -1 if the
1350 scheduling window is empty and zero otherwise. */
1352 static int
1353 get_sched_window (partial_schedule_ptr ps, int *nodes_order, int i,
1354 sbitmap sched_nodes, int ii, int *start_p, int *step_p, int *end_p)
1356 int start, step, end;
1357 ddg_edge_ptr e;
1358 int u = nodes_order [i];
1359 ddg_node_ptr u_node = &ps->g->nodes[u];
1360 sbitmap psp = sbitmap_alloc (ps->g->num_nodes);
1361 sbitmap pss = sbitmap_alloc (ps->g->num_nodes);
1362 sbitmap u_node_preds = NODE_PREDECESSORS (u_node);
1363 sbitmap u_node_succs = NODE_SUCCESSORS (u_node);
1364 int psp_not_empty;
1365 int pss_not_empty;
1367 /* 1. compute sched window for u (start, end, step). */
1368 sbitmap_zero (psp);
1369 sbitmap_zero (pss);
1370 psp_not_empty = sbitmap_a_and_b_cg (psp, u_node_preds, sched_nodes);
1371 pss_not_empty = sbitmap_a_and_b_cg (pss, u_node_succs, sched_nodes);
1373 if (psp_not_empty && !pss_not_empty)
1375 int early_start = INT_MIN;
1377 end = INT_MAX;
1378 for (e = u_node->in; e != 0; e = e->next_in)
1380 ddg_node_ptr v_node = e->src;
1381 if (TEST_BIT (sched_nodes, v_node->cuid))
1383 int node_st = SCHED_TIME (v_node)
1384 + e->latency - (e->distance * ii);
1386 early_start = MAX (early_start, node_st);
1388 if (e->data_type == MEM_DEP)
1389 end = MIN (end, SCHED_TIME (v_node) + ii - 1);
1392 start = early_start;
1393 end = MIN (end, early_start + ii);
1394 step = 1;
1397 else if (!psp_not_empty && pss_not_empty)
1399 int late_start = INT_MAX;
1401 end = INT_MIN;
1402 for (e = u_node->out; e != 0; e = e->next_out)
1404 ddg_node_ptr v_node = e->dest;
1405 if (TEST_BIT (sched_nodes, v_node->cuid))
1407 late_start = MIN (late_start,
1408 SCHED_TIME (v_node) - e->latency
1409 + (e->distance * ii));
1410 if (e->data_type == MEM_DEP)
1411 end = MAX (end, SCHED_TIME (v_node) - ii + 1);
1414 start = late_start;
1415 end = MAX (end, late_start - ii);
1416 step = -1;
1419 else if (psp_not_empty && pss_not_empty)
1421 int early_start = INT_MIN;
1422 int late_start = INT_MAX;
1424 start = INT_MIN;
1425 end = INT_MAX;
1426 for (e = u_node->in; e != 0; e = e->next_in)
1428 ddg_node_ptr v_node = e->src;
1430 if (TEST_BIT (sched_nodes, v_node->cuid))
1432 early_start = MAX (early_start,
1433 SCHED_TIME (v_node) + e->latency
1434 - (e->distance * ii));
1435 if (e->data_type == MEM_DEP)
1436 end = MIN (end, SCHED_TIME (v_node) + ii - 1);
1439 for (e = u_node->out; e != 0; e = e->next_out)
1441 ddg_node_ptr v_node = e->dest;
1443 if (TEST_BIT (sched_nodes, v_node->cuid))
1445 late_start = MIN (late_start,
1446 SCHED_TIME (v_node) - e->latency
1447 + (e->distance * ii));
1448 if (e->data_type == MEM_DEP)
1449 start = MAX (start, SCHED_TIME (v_node) - ii + 1);
1452 start = MAX (start, early_start);
1453 end = MIN (end, MIN (early_start + ii, late_start + 1));
1454 step = 1;
1456 else /* psp is empty && pss is empty. */
1458 start = SCHED_ASAP (u_node);
1459 end = start + ii;
1460 step = 1;
1463 *start_p = start;
1464 *step_p = step;
1465 *end_p = end;
1466 sbitmap_free (psp);
1467 sbitmap_free (pss);
1469 if ((start >= end && step == 1) || (start <= end && step == -1))
1470 return -1;
1471 else
1472 return 0;
1475 /* This function implements the scheduling algorithm for SMS according to the
1476 above algorithm. */
1477 static partial_schedule_ptr
1478 sms_schedule_by_order (ddg_ptr g, int mii, int maxii, int *nodes_order)
1480 int ii = mii;
1481 int i, c, success;
1482 int try_again_with_larger_ii = true;
1483 int num_nodes = g->num_nodes;
1484 ddg_edge_ptr e;
1485 int start, end, step; /* Place together into one struct? */
1486 sbitmap sched_nodes = sbitmap_alloc (num_nodes);
1487 sbitmap must_precede = sbitmap_alloc (num_nodes);
1488 sbitmap must_follow = sbitmap_alloc (num_nodes);
1489 sbitmap tobe_scheduled = sbitmap_alloc (num_nodes);
1491 partial_schedule_ptr ps = create_partial_schedule (ii, g, DFA_HISTORY);
1493 sbitmap_ones (tobe_scheduled);
1494 sbitmap_zero (sched_nodes);
1496 while ((! sbitmap_equal (tobe_scheduled, sched_nodes)
1497 || try_again_with_larger_ii ) && ii < maxii)
1499 int j;
1500 bool unscheduled_nodes = false;
1502 if (dump_file)
1503 fprintf(dump_file, "Starting with ii=%d\n", ii);
1504 if (try_again_with_larger_ii)
1506 try_again_with_larger_ii = false;
1507 sbitmap_zero (sched_nodes);
1510 for (i = 0; i < num_nodes; i++)
1512 int u = nodes_order[i];
1513 ddg_node_ptr u_node = &ps->g->nodes[u];
1514 rtx insn = u_node->insn;
1516 if (!INSN_P (insn))
1518 RESET_BIT (tobe_scheduled, u);
1519 continue;
1522 if (JUMP_P (insn)) /* Closing branch handled later. */
1524 RESET_BIT (tobe_scheduled, u);
1525 continue;
1528 if (TEST_BIT (sched_nodes, u))
1529 continue;
1531 /* Try to get non-empty scheduling window. */
1532 j = i;
1533 while (get_sched_window (ps, nodes_order, i, sched_nodes, ii, &start, &step, &end) < 0
1534 && j > 0)
1536 unscheduled_nodes = true;
1537 if (TEST_BIT (NODE_PREDECESSORS (u_node), nodes_order[j - 1])
1538 || TEST_BIT (NODE_SUCCESSORS (u_node), nodes_order[j - 1]))
1540 ps_unschedule_node (ps, &ps->g->nodes[nodes_order[j - 1]]);
1541 RESET_BIT (sched_nodes, nodes_order [j - 1]);
1543 j--;
1545 if (j < 0)
1547 /* ??? Try backtracking instead of immediately ii++? */
1548 ii++;
1549 try_again_with_larger_ii = true;
1550 reset_partial_schedule (ps, ii);
1551 break;
1553 /* 2. Try scheduling u in window. */
1554 if (dump_file)
1555 fprintf(dump_file, "Trying to schedule node %d in (%d .. %d) step %d\n",
1556 u, start, end, step);
1558 /* use must_follow & must_precede bitmaps to determine order
1559 of nodes within the cycle. */
1560 sbitmap_zero (must_precede);
1561 sbitmap_zero (must_follow);
1562 for (e = u_node->in; e != 0; e = e->next_in)
1563 if (TEST_BIT (sched_nodes, e->src->cuid)
1564 && e->latency == (ii * e->distance)
1565 && start == SCHED_TIME (e->src))
1566 SET_BIT (must_precede, e->src->cuid);
1568 for (e = u_node->out; e != 0; e = e->next_out)
1569 if (TEST_BIT (sched_nodes, e->dest->cuid)
1570 && e->latency == (ii * e->distance)
1571 && end == SCHED_TIME (e->dest))
1572 SET_BIT (must_follow, e->dest->cuid);
1574 success = 0;
1575 if ((step > 0 && start < end) || (step < 0 && start > end))
1576 for (c = start; c != end; c += step)
1578 ps_insn_ptr psi;
1580 psi = ps_add_node_check_conflicts (ps, u_node, c,
1581 must_precede,
1582 must_follow);
1584 if (psi)
1586 SCHED_TIME (u_node) = c;
1587 SET_BIT (sched_nodes, u);
1588 success = 1;
1589 if (dump_file)
1590 fprintf(dump_file, "Schedule in %d\n", c);
1591 break;
1594 if (!success)
1596 /* ??? Try backtracking instead of immediately ii++? */
1597 ii++;
1598 try_again_with_larger_ii = true;
1599 reset_partial_schedule (ps, ii);
1600 break;
1602 if (unscheduled_nodes)
1603 break;
1605 /* ??? If (success), check register pressure estimates. */
1606 } /* Continue with next node. */
1607 } /* While try_again_with_larger_ii. */
1609 sbitmap_free (sched_nodes);
1611 if (ii >= maxii)
1613 free_partial_schedule (ps);
1614 ps = NULL;
1616 return ps;
1620 /* This page implements the algorithm for ordering the nodes of a DDG
1621 for modulo scheduling, activated through the
1622 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
1624 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
1625 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
1626 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
1627 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
1628 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
1629 #define DEPTH(x) (ASAP ((x)))
1631 typedef struct node_order_params * nopa;
1633 static void order_nodes_of_sccs (ddg_all_sccs_ptr, int * result);
1634 static int order_nodes_in_scc (ddg_ptr, sbitmap, sbitmap, int*, int);
1635 static nopa calculate_order_params (ddg_ptr, int mii);
1636 static int find_max_asap (ddg_ptr, sbitmap);
1637 static int find_max_hv_min_mob (ddg_ptr, sbitmap);
1638 static int find_max_dv_min_mob (ddg_ptr, sbitmap);
1640 enum sms_direction {BOTTOMUP, TOPDOWN};
1642 struct node_order_params
1644 int asap;
1645 int alap;
1646 int height;
1649 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
1650 static void
1651 check_nodes_order (int *node_order, int num_nodes)
1653 int i;
1654 sbitmap tmp = sbitmap_alloc (num_nodes);
1656 sbitmap_zero (tmp);
1658 for (i = 0; i < num_nodes; i++)
1660 int u = node_order[i];
1662 gcc_assert (u < num_nodes && u >= 0 && !TEST_BIT (tmp, u));
1664 SET_BIT (tmp, u);
1667 sbitmap_free (tmp);
1670 /* Order the nodes of G for scheduling and pass the result in
1671 NODE_ORDER. Also set aux.count of each node to ASAP.
1672 Return the recMII for the given DDG. */
1673 static int
1674 sms_order_nodes (ddg_ptr g, int mii, int * node_order)
1676 int i;
1677 int rec_mii = 0;
1678 ddg_all_sccs_ptr sccs = create_ddg_all_sccs (g);
1680 nopa nops = calculate_order_params (g, mii);
1682 order_nodes_of_sccs (sccs, node_order);
1684 if (sccs->num_sccs > 0)
1685 /* First SCC has the largest recurrence_length. */
1686 rec_mii = sccs->sccs[0]->recurrence_length;
1688 /* Save ASAP before destroying node_order_params. */
1689 for (i = 0; i < g->num_nodes; i++)
1691 ddg_node_ptr v = &g->nodes[i];
1692 v->aux.count = ASAP (v);
1695 free (nops);
1696 free_ddg_all_sccs (sccs);
1697 check_nodes_order (node_order, g->num_nodes);
1699 return rec_mii;
1702 static void
1703 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs, int * node_order)
1705 int i, pos = 0;
1706 ddg_ptr g = all_sccs->ddg;
1707 int num_nodes = g->num_nodes;
1708 sbitmap prev_sccs = sbitmap_alloc (num_nodes);
1709 sbitmap on_path = sbitmap_alloc (num_nodes);
1710 sbitmap tmp = sbitmap_alloc (num_nodes);
1711 sbitmap ones = sbitmap_alloc (num_nodes);
1713 sbitmap_zero (prev_sccs);
1714 sbitmap_ones (ones);
1716 /* Perfrom the node ordering starting from the SCC with the highest recMII.
1717 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
1718 for (i = 0; i < all_sccs->num_sccs; i++)
1720 ddg_scc_ptr scc = all_sccs->sccs[i];
1722 /* Add nodes on paths from previous SCCs to the current SCC. */
1723 find_nodes_on_paths (on_path, g, prev_sccs, scc->nodes);
1724 sbitmap_a_or_b (tmp, scc->nodes, on_path);
1726 /* Add nodes on paths from the current SCC to previous SCCs. */
1727 find_nodes_on_paths (on_path, g, scc->nodes, prev_sccs);
1728 sbitmap_a_or_b (tmp, tmp, on_path);
1730 /* Remove nodes of previous SCCs from current extended SCC. */
1731 sbitmap_difference (tmp, tmp, prev_sccs);
1733 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
1734 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
1737 /* Handle the remaining nodes that do not belong to any scc. Each call
1738 to order_nodes_in_scc handles a single connected component. */
1739 while (pos < g->num_nodes)
1741 sbitmap_difference (tmp, ones, prev_sccs);
1742 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
1744 sbitmap_free (prev_sccs);
1745 sbitmap_free (on_path);
1746 sbitmap_free (tmp);
1747 sbitmap_free (ones);
1750 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
1751 static struct node_order_params *
1752 calculate_order_params (ddg_ptr g, int mii ATTRIBUTE_UNUSED)
1754 int u;
1755 int max_asap;
1756 int num_nodes = g->num_nodes;
1757 ddg_edge_ptr e;
1758 /* Allocate a place to hold ordering params for each node in the DDG. */
1759 nopa node_order_params_arr;
1761 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
1762 node_order_params_arr = (nopa) xcalloc (num_nodes,
1763 sizeof (struct node_order_params));
1765 /* Set the aux pointer of each node to point to its order_params structure. */
1766 for (u = 0; u < num_nodes; u++)
1767 g->nodes[u].aux.info = &node_order_params_arr[u];
1769 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
1770 calculate ASAP, ALAP, mobility, distance, and height for each node
1771 in the dependence (direct acyclic) graph. */
1773 /* We assume that the nodes in the array are in topological order. */
1775 max_asap = 0;
1776 for (u = 0; u < num_nodes; u++)
1778 ddg_node_ptr u_node = &g->nodes[u];
1780 ASAP (u_node) = 0;
1781 for (e = u_node->in; e; e = e->next_in)
1782 if (e->distance == 0)
1783 ASAP (u_node) = MAX (ASAP (u_node),
1784 ASAP (e->src) + e->latency);
1785 max_asap = MAX (max_asap, ASAP (u_node));
1788 for (u = num_nodes - 1; u > -1; u--)
1790 ddg_node_ptr u_node = &g->nodes[u];
1792 ALAP (u_node) = max_asap;
1793 HEIGHT (u_node) = 0;
1794 for (e = u_node->out; e; e = e->next_out)
1795 if (e->distance == 0)
1797 ALAP (u_node) = MIN (ALAP (u_node),
1798 ALAP (e->dest) - e->latency);
1799 HEIGHT (u_node) = MAX (HEIGHT (u_node),
1800 HEIGHT (e->dest) + e->latency);
1804 return node_order_params_arr;
1807 static int
1808 find_max_asap (ddg_ptr g, sbitmap nodes)
1810 unsigned int u = 0;
1811 int max_asap = -1;
1812 int result = -1;
1813 sbitmap_iterator sbi;
1815 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
1817 ddg_node_ptr u_node = &g->nodes[u];
1819 if (max_asap < ASAP (u_node))
1821 max_asap = ASAP (u_node);
1822 result = u;
1825 return result;
1828 static int
1829 find_max_hv_min_mob (ddg_ptr g, sbitmap nodes)
1831 unsigned int u = 0;
1832 int max_hv = -1;
1833 int min_mob = INT_MAX;
1834 int result = -1;
1835 sbitmap_iterator sbi;
1837 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
1839 ddg_node_ptr u_node = &g->nodes[u];
1841 if (max_hv < HEIGHT (u_node))
1843 max_hv = HEIGHT (u_node);
1844 min_mob = MOB (u_node);
1845 result = u;
1847 else if ((max_hv == HEIGHT (u_node))
1848 && (min_mob > MOB (u_node)))
1850 min_mob = MOB (u_node);
1851 result = u;
1854 return result;
1857 static int
1858 find_max_dv_min_mob (ddg_ptr g, sbitmap nodes)
1860 unsigned int u = 0;
1861 int max_dv = -1;
1862 int min_mob = INT_MAX;
1863 int result = -1;
1864 sbitmap_iterator sbi;
1866 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
1868 ddg_node_ptr u_node = &g->nodes[u];
1870 if (max_dv < DEPTH (u_node))
1872 max_dv = DEPTH (u_node);
1873 min_mob = MOB (u_node);
1874 result = u;
1876 else if ((max_dv == DEPTH (u_node))
1877 && (min_mob > MOB (u_node)))
1879 min_mob = MOB (u_node);
1880 result = u;
1883 return result;
1886 /* Places the nodes of SCC into the NODE_ORDER array starting
1887 at position POS, according to the SMS ordering algorithm.
1888 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
1889 the NODE_ORDER array, starting from position zero. */
1890 static int
1891 order_nodes_in_scc (ddg_ptr g, sbitmap nodes_ordered, sbitmap scc,
1892 int * node_order, int pos)
1894 enum sms_direction dir;
1895 int num_nodes = g->num_nodes;
1896 sbitmap workset = sbitmap_alloc (num_nodes);
1897 sbitmap tmp = sbitmap_alloc (num_nodes);
1898 sbitmap zero_bitmap = sbitmap_alloc (num_nodes);
1899 sbitmap predecessors = sbitmap_alloc (num_nodes);
1900 sbitmap successors = sbitmap_alloc (num_nodes);
1902 sbitmap_zero (predecessors);
1903 find_predecessors (predecessors, g, nodes_ordered);
1905 sbitmap_zero (successors);
1906 find_successors (successors, g, nodes_ordered);
1908 sbitmap_zero (tmp);
1909 if (sbitmap_a_and_b_cg (tmp, predecessors, scc))
1911 sbitmap_copy (workset, tmp);
1912 dir = BOTTOMUP;
1914 else if (sbitmap_a_and_b_cg (tmp, successors, scc))
1916 sbitmap_copy (workset, tmp);
1917 dir = TOPDOWN;
1919 else
1921 int u;
1923 sbitmap_zero (workset);
1924 if ((u = find_max_asap (g, scc)) >= 0)
1925 SET_BIT (workset, u);
1926 dir = BOTTOMUP;
1929 sbitmap_zero (zero_bitmap);
1930 while (!sbitmap_equal (workset, zero_bitmap))
1932 int v;
1933 ddg_node_ptr v_node;
1934 sbitmap v_node_preds;
1935 sbitmap v_node_succs;
1937 if (dir == TOPDOWN)
1939 while (!sbitmap_equal (workset, zero_bitmap))
1941 v = find_max_hv_min_mob (g, workset);
1942 v_node = &g->nodes[v];
1943 node_order[pos++] = v;
1944 v_node_succs = NODE_SUCCESSORS (v_node);
1945 sbitmap_a_and_b (tmp, v_node_succs, scc);
1947 /* Don't consider the already ordered successors again. */
1948 sbitmap_difference (tmp, tmp, nodes_ordered);
1949 sbitmap_a_or_b (workset, workset, tmp);
1950 RESET_BIT (workset, v);
1951 SET_BIT (nodes_ordered, v);
1953 dir = BOTTOMUP;
1954 sbitmap_zero (predecessors);
1955 find_predecessors (predecessors, g, nodes_ordered);
1956 sbitmap_a_and_b (workset, predecessors, scc);
1958 else
1960 while (!sbitmap_equal (workset, zero_bitmap))
1962 v = find_max_dv_min_mob (g, workset);
1963 v_node = &g->nodes[v];
1964 node_order[pos++] = v;
1965 v_node_preds = NODE_PREDECESSORS (v_node);
1966 sbitmap_a_and_b (tmp, v_node_preds, scc);
1968 /* Don't consider the already ordered predecessors again. */
1969 sbitmap_difference (tmp, tmp, nodes_ordered);
1970 sbitmap_a_or_b (workset, workset, tmp);
1971 RESET_BIT (workset, v);
1972 SET_BIT (nodes_ordered, v);
1974 dir = TOPDOWN;
1975 sbitmap_zero (successors);
1976 find_successors (successors, g, nodes_ordered);
1977 sbitmap_a_and_b (workset, successors, scc);
1980 sbitmap_free (tmp);
1981 sbitmap_free (workset);
1982 sbitmap_free (zero_bitmap);
1983 sbitmap_free (predecessors);
1984 sbitmap_free (successors);
1985 return pos;
1989 /* This page contains functions for manipulating partial-schedules during
1990 modulo scheduling. */
1992 /* Create a partial schedule and allocate a memory to hold II rows. */
1994 static partial_schedule_ptr
1995 create_partial_schedule (int ii, ddg_ptr g, int history)
1997 partial_schedule_ptr ps = XNEW (struct partial_schedule);
1998 ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
1999 ps->ii = ii;
2000 ps->history = history;
2001 ps->min_cycle = INT_MAX;
2002 ps->max_cycle = INT_MIN;
2003 ps->g = g;
2005 return ps;
2008 /* Free the PS_INSNs in rows array of the given partial schedule.
2009 ??? Consider caching the PS_INSN's. */
2010 static void
2011 free_ps_insns (partial_schedule_ptr ps)
2013 int i;
2015 for (i = 0; i < ps->ii; i++)
2017 while (ps->rows[i])
2019 ps_insn_ptr ps_insn = ps->rows[i]->next_in_row;
2021 free (ps->rows[i]);
2022 ps->rows[i] = ps_insn;
2024 ps->rows[i] = NULL;
2028 /* Free all the memory allocated to the partial schedule. */
2030 static void
2031 free_partial_schedule (partial_schedule_ptr ps)
2033 if (!ps)
2034 return;
2035 free_ps_insns (ps);
2036 free (ps->rows);
2037 free (ps);
2040 /* Clear the rows array with its PS_INSNs, and create a new one with
2041 NEW_II rows. */
2043 static void
2044 reset_partial_schedule (partial_schedule_ptr ps, int new_ii)
2046 if (!ps)
2047 return;
2048 free_ps_insns (ps);
2049 if (new_ii == ps->ii)
2050 return;
2051 ps->rows = (ps_insn_ptr *) xrealloc (ps->rows, new_ii
2052 * sizeof (ps_insn_ptr));
2053 memset (ps->rows, 0, new_ii * sizeof (ps_insn_ptr));
2054 ps->ii = new_ii;
2055 ps->min_cycle = INT_MAX;
2056 ps->max_cycle = INT_MIN;
2059 /* Prints the partial schedule as an ii rows array, for each rows
2060 print the ids of the insns in it. */
2061 void
2062 print_partial_schedule (partial_schedule_ptr ps, FILE *dump)
2064 int i;
2066 for (i = 0; i < ps->ii; i++)
2068 ps_insn_ptr ps_i = ps->rows[i];
2070 fprintf (dump, "\n[CYCLE %d ]: ", i);
2071 while (ps_i)
2073 fprintf (dump, "%d, ",
2074 INSN_UID (ps_i->node->insn));
2075 ps_i = ps_i->next_in_row;
2080 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2081 static ps_insn_ptr
2082 create_ps_insn (ddg_node_ptr node, int rest_count, int cycle)
2084 ps_insn_ptr ps_i = XNEW (struct ps_insn);
2086 ps_i->node = node;
2087 ps_i->next_in_row = NULL;
2088 ps_i->prev_in_row = NULL;
2089 ps_i->row_rest_count = rest_count;
2090 ps_i->cycle = cycle;
2092 return ps_i;
2096 /* Removes the given PS_INSN from the partial schedule. Returns false if the
2097 node is not found in the partial schedule, else returns true. */
2098 static bool
2099 remove_node_from_ps (partial_schedule_ptr ps, ps_insn_ptr ps_i)
2101 int row;
2103 if (!ps || !ps_i)
2104 return false;
2106 row = SMODULO (ps_i->cycle, ps->ii);
2107 if (! ps_i->prev_in_row)
2109 if (ps_i != ps->rows[row])
2110 return false;
2112 ps->rows[row] = ps_i->next_in_row;
2113 if (ps->rows[row])
2114 ps->rows[row]->prev_in_row = NULL;
2116 else
2118 ps_i->prev_in_row->next_in_row = ps_i->next_in_row;
2119 if (ps_i->next_in_row)
2120 ps_i->next_in_row->prev_in_row = ps_i->prev_in_row;
2122 free (ps_i);
2123 return true;
2126 /* Unlike what literature describes for modulo scheduling (which focuses
2127 on VLIW machines) the order of the instructions inside a cycle is
2128 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2129 where the current instruction should go relative to the already
2130 scheduled instructions in the given cycle. Go over these
2131 instructions and find the first possible column to put it in. */
2132 static bool
2133 ps_insn_find_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
2134 sbitmap must_precede, sbitmap must_follow)
2136 ps_insn_ptr next_ps_i;
2137 ps_insn_ptr first_must_follow = NULL;
2138 ps_insn_ptr last_must_precede = NULL;
2139 int row;
2141 if (! ps_i)
2142 return false;
2144 row = SMODULO (ps_i->cycle, ps->ii);
2146 /* Find the first must follow and the last must precede
2147 and insert the node immediately after the must precede
2148 but make sure that it there is no must follow after it. */
2149 for (next_ps_i = ps->rows[row];
2150 next_ps_i;
2151 next_ps_i = next_ps_i->next_in_row)
2153 if (TEST_BIT (must_follow, next_ps_i->node->cuid)
2154 && ! first_must_follow)
2155 first_must_follow = next_ps_i;
2156 if (TEST_BIT (must_precede, next_ps_i->node->cuid))
2158 /* If we have already met a node that must follow, then
2159 there is no possible column. */
2160 if (first_must_follow)
2161 return false;
2162 else
2163 last_must_precede = next_ps_i;
2167 /* Now insert the node after INSERT_AFTER_PSI. */
2169 if (! last_must_precede)
2171 ps_i->next_in_row = ps->rows[row];
2172 ps_i->prev_in_row = NULL;
2173 if (ps_i->next_in_row)
2174 ps_i->next_in_row->prev_in_row = ps_i;
2175 ps->rows[row] = ps_i;
2177 else
2179 ps_i->next_in_row = last_must_precede->next_in_row;
2180 last_must_precede->next_in_row = ps_i;
2181 ps_i->prev_in_row = last_must_precede;
2182 if (ps_i->next_in_row)
2183 ps_i->next_in_row->prev_in_row = ps_i;
2186 return true;
2189 /* Advances the PS_INSN one column in its current row; returns false
2190 in failure and true in success. Bit N is set in MUST_FOLLOW if
2191 the node with cuid N must be come after the node pointed to by
2192 PS_I when scheduled in the same cycle. */
2193 static int
2194 ps_insn_advance_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
2195 sbitmap must_follow)
2197 ps_insn_ptr prev, next;
2198 int row;
2199 ddg_node_ptr next_node;
2201 if (!ps || !ps_i)
2202 return false;
2204 row = SMODULO (ps_i->cycle, ps->ii);
2206 if (! ps_i->next_in_row)
2207 return false;
2209 next_node = ps_i->next_in_row->node;
2211 /* Check if next_in_row is dependent on ps_i, both having same sched
2212 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
2213 if (TEST_BIT (must_follow, next_node->cuid))
2214 return false;
2216 /* Advance PS_I over its next_in_row in the doubly linked list. */
2217 prev = ps_i->prev_in_row;
2218 next = ps_i->next_in_row;
2220 if (ps_i == ps->rows[row])
2221 ps->rows[row] = next;
2223 ps_i->next_in_row = next->next_in_row;
2225 if (next->next_in_row)
2226 next->next_in_row->prev_in_row = ps_i;
2228 next->next_in_row = ps_i;
2229 ps_i->prev_in_row = next;
2231 next->prev_in_row = prev;
2232 if (prev)
2233 prev->next_in_row = next;
2235 return true;
2238 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
2239 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
2240 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
2241 before/after (respectively) the node pointed to by PS_I when scheduled
2242 in the same cycle. */
2243 static ps_insn_ptr
2244 add_node_to_ps (partial_schedule_ptr ps, ddg_node_ptr node, int cycle,
2245 sbitmap must_precede, sbitmap must_follow)
2247 ps_insn_ptr ps_i;
2248 int rest_count = 1;
2249 int row = SMODULO (cycle, ps->ii);
2251 if (ps->rows[row]
2252 && ps->rows[row]->row_rest_count >= issue_rate)
2253 return NULL;
2255 if (ps->rows[row])
2256 rest_count += ps->rows[row]->row_rest_count;
2258 ps_i = create_ps_insn (node, rest_count, cycle);
2260 /* Finds and inserts PS_I according to MUST_FOLLOW and
2261 MUST_PRECEDE. */
2262 if (! ps_insn_find_column (ps, ps_i, must_precede, must_follow))
2264 free (ps_i);
2265 return NULL;
2268 return ps_i;
2271 /* Advance time one cycle. Assumes DFA is being used. */
2272 static void
2273 advance_one_cycle (void)
2275 if (targetm.sched.dfa_pre_cycle_insn)
2276 state_transition (curr_state,
2277 targetm.sched.dfa_pre_cycle_insn ());
2279 state_transition (curr_state, NULL);
2281 if (targetm.sched.dfa_post_cycle_insn)
2282 state_transition (curr_state,
2283 targetm.sched.dfa_post_cycle_insn ());
2286 /* Given the kernel of a loop (from FIRST_INSN to LAST_INSN), finds
2287 the number of cycles according to DFA that the kernel fits in,
2288 we use this to check if we done well with SMS after we add
2289 register moves. In some cases register moves overhead makes
2290 it even worse than the original loop. We want SMS to be performed
2291 when it gives less cycles after register moves are added. */
2292 static int
2293 kernel_number_of_cycles (rtx first_insn, rtx last_insn)
2295 int cycles = 0;
2296 rtx insn;
2297 int can_issue_more = issue_rate;
2299 state_reset (curr_state);
2301 for (insn = first_insn;
2302 insn != NULL_RTX && insn != last_insn;
2303 insn = NEXT_INSN (insn))
2305 if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
2306 continue;
2308 /* Check if there is room for the current insn. */
2309 if (!can_issue_more || state_dead_lock_p (curr_state))
2311 cycles ++;
2312 advance_one_cycle ();
2313 can_issue_more = issue_rate;
2316 /* Update the DFA state and return with failure if the DFA found
2317 recource conflicts. */
2318 if (state_transition (curr_state, insn) >= 0)
2320 cycles ++;
2321 advance_one_cycle ();
2322 can_issue_more = issue_rate;
2325 if (targetm.sched.variable_issue)
2326 can_issue_more =
2327 targetm.sched.variable_issue (sched_dump, sched_verbose,
2328 insn, can_issue_more);
2329 /* A naked CLOBBER or USE generates no instruction, so don't
2330 let them consume issue slots. */
2331 else if (GET_CODE (PATTERN (insn)) != USE
2332 && GET_CODE (PATTERN (insn)) != CLOBBER)
2333 can_issue_more--;
2335 return cycles;
2338 /* Checks if PS has resource conflicts according to DFA, starting from
2339 FROM cycle to TO cycle; returns true if there are conflicts and false
2340 if there are no conflicts. Assumes DFA is being used. */
2341 static int
2342 ps_has_conflicts (partial_schedule_ptr ps, int from, int to)
2344 int cycle;
2346 state_reset (curr_state);
2348 for (cycle = from; cycle <= to; cycle++)
2350 ps_insn_ptr crr_insn;
2351 /* Holds the remaining issue slots in the current row. */
2352 int can_issue_more = issue_rate;
2354 /* Walk through the DFA for the current row. */
2355 for (crr_insn = ps->rows[SMODULO (cycle, ps->ii)];
2356 crr_insn;
2357 crr_insn = crr_insn->next_in_row)
2359 rtx insn = crr_insn->node->insn;
2361 if (!INSN_P (insn))
2362 continue;
2364 /* Check if there is room for the current insn. */
2365 if (!can_issue_more || state_dead_lock_p (curr_state))
2366 return true;
2368 /* Update the DFA state and return with failure if the DFA found
2369 recource conflicts. */
2370 if (state_transition (curr_state, insn) >= 0)
2371 return true;
2373 if (targetm.sched.variable_issue)
2374 can_issue_more =
2375 targetm.sched.variable_issue (sched_dump, sched_verbose,
2376 insn, can_issue_more);
2377 /* A naked CLOBBER or USE generates no instruction, so don't
2378 let them consume issue slots. */
2379 else if (GET_CODE (PATTERN (insn)) != USE
2380 && GET_CODE (PATTERN (insn)) != CLOBBER)
2381 can_issue_more--;
2384 /* Advance the DFA to the next cycle. */
2385 advance_one_cycle ();
2387 return false;
2390 /* Checks if the given node causes resource conflicts when added to PS at
2391 cycle C. If not the node is added to PS and returned; otherwise zero
2392 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
2393 cuid N must be come before/after (respectively) the node pointed to by
2394 PS_I when scheduled in the same cycle. */
2395 ps_insn_ptr
2396 ps_add_node_check_conflicts (partial_schedule_ptr ps, ddg_node_ptr n,
2397 int c, sbitmap must_precede,
2398 sbitmap must_follow)
2400 int has_conflicts = 0;
2401 ps_insn_ptr ps_i;
2403 /* First add the node to the PS, if this succeeds check for
2404 conflicts, trying different issue slots in the same row. */
2405 if (! (ps_i = add_node_to_ps (ps, n, c, must_precede, must_follow)))
2406 return NULL; /* Failed to insert the node at the given cycle. */
2408 has_conflicts = ps_has_conflicts (ps, c, c)
2409 || (ps->history > 0
2410 && ps_has_conflicts (ps,
2411 c - ps->history,
2412 c + ps->history));
2414 /* Try different issue slots to find one that the given node can be
2415 scheduled in without conflicts. */
2416 while (has_conflicts)
2418 if (! ps_insn_advance_column (ps, ps_i, must_follow))
2419 break;
2420 has_conflicts = ps_has_conflicts (ps, c, c)
2421 || (ps->history > 0
2422 && ps_has_conflicts (ps,
2423 c - ps->history,
2424 c + ps->history));
2427 if (has_conflicts)
2429 remove_node_from_ps (ps, ps_i);
2430 return NULL;
2433 ps->min_cycle = MIN (ps->min_cycle, c);
2434 ps->max_cycle = MAX (ps->max_cycle, c);
2435 return ps_i;
2438 /* Rotate the rows of PS such that insns scheduled at time
2439 START_CYCLE will appear in row 0. Updates max/min_cycles. */
2440 void
2441 rotate_partial_schedule (partial_schedule_ptr ps, int start_cycle)
2443 int i, row, backward_rotates;
2444 int last_row = ps->ii - 1;
2446 if (start_cycle == 0)
2447 return;
2449 backward_rotates = SMODULO (start_cycle, ps->ii);
2451 /* Revisit later and optimize this into a single loop. */
2452 for (i = 0; i < backward_rotates; i++)
2454 ps_insn_ptr first_row = ps->rows[0];
2456 for (row = 0; row < last_row; row++)
2457 ps->rows[row] = ps->rows[row+1];
2459 ps->rows[last_row] = first_row;
2462 ps->max_cycle -= start_cycle;
2463 ps->min_cycle -= start_cycle;
2466 /* Remove the node N from the partial schedule PS; because we restart the DFA
2467 each time we want to check for resource conflicts; this is equivalent to
2468 unscheduling the node N. */
2469 static bool
2470 ps_unschedule_node (partial_schedule_ptr ps, ddg_node_ptr n)
2472 ps_insn_ptr ps_i;
2473 int row = SMODULO (SCHED_TIME (n), ps->ii);
2475 if (row < 0 || row > ps->ii)
2476 return false;
2478 for (ps_i = ps->rows[row];
2479 ps_i && ps_i->node != n;
2480 ps_i = ps_i->next_in_row);
2481 if (!ps_i)
2482 return false;
2484 return remove_node_from_ps (ps, ps_i);
2486 #endif /* INSN_SCHEDULING */
2488 static bool
2489 gate_handle_sms (void)
2491 return (optimize > 0 && flag_modulo_sched);
2495 /* Run instruction scheduler. */
2496 /* Perform SMS module scheduling. */
2497 static void
2498 rest_of_handle_sms (void)
2500 #ifdef INSN_SCHEDULING
2501 basic_block bb;
2503 /* We want to be able to create new pseudos. */
2504 no_new_pseudos = 0;
2505 /* Collect loop information to be used in SMS. */
2506 cfg_layout_initialize (CLEANUP_UPDATE_LIFE);
2507 sms_schedule ();
2509 /* Update the life information, because we add pseudos. */
2510 max_regno = max_reg_num ();
2511 allocate_reg_info (max_regno, FALSE, FALSE);
2512 update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
2513 (PROP_DEATH_NOTES
2514 | PROP_REG_INFO
2515 | PROP_KILL_DEAD_CODE
2516 | PROP_SCAN_DEAD_CODE));
2518 no_new_pseudos = 1;
2520 /* Finalize layout changes. */
2521 FOR_EACH_BB (bb)
2522 if (bb->next_bb != EXIT_BLOCK_PTR)
2523 bb->aux = bb->next_bb;
2524 cfg_layout_finalize ();
2525 free_dominance_info (CDI_DOMINATORS);
2526 #endif /* INSN_SCHEDULING */
2529 struct tree_opt_pass pass_sms =
2531 "sms", /* name */
2532 gate_handle_sms, /* gate */
2533 rest_of_handle_sms, /* execute */
2534 NULL, /* sub */
2535 NULL, /* next */
2536 0, /* static_pass_number */
2537 TV_SMS, /* tv_id */
2538 0, /* properties_required */
2539 0, /* properties_provided */
2540 0, /* properties_destroyed */
2541 0, /* todo_flags_start */
2542 TODO_dump_func |
2543 TODO_ggc_collect, /* todo_flags_finish */
2544 'm' /* letter */