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
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 COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
26 #include "coretypes.h"
31 #include "hard-reg-set.h"
35 #include "insn-config.h"
36 #include "insn-attr.h"
40 #include "sched-int.h"
42 #include "cfglayout.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-
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
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. */
113 /* The corresponding DDG_NODE. */
116 /* The (absolute) cycle in which the PS instruction is scheduled.
117 Same as SCHED_TIME (node). */
120 /* The next/prev PS_INSN in the same row. */
121 ps_insn_ptr next_in_row
,
124 /* The number of nodes in the same row that come after this node. */
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). */
139 /* The earliest absolute cycle of an insn in the partial schedule. */
142 /* The latest absolute cycle of an insn in the partial schedule. */
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
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
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
,
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. */
215 /* The number of register-move instructions added, immediately preceding
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). */
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. */
232 sms_print_insn (rtx insn
, int aligned ATTRIBUTE_UNUSED
)
236 sprintf (tmp
, "i%4d", INSN_UID (insn
));
241 contributes_to_priority (rtx next
, rtx insn
)
243 return BLOCK_NUM (next
) == BLOCK_NUM (insn
);
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
=
262 contributes_to_priority
,
263 compute_jump_reg_dependencies
,
270 /* Return the register decremented and tested in INSN,
271 or zero if it is not a decrement-and-branch insn. */
274 doloop_register_get (rtx insn ATTRIBUTE_UNUSED
)
276 #ifdef HAVE_doloop_end
277 rtx pattern
, reg
, condition
;
282 pattern
= PATTERN (insn
);
283 condition
= doloop_condition_get (pattern
);
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);
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. */
306 const_iteration_count (rtx count_reg
, basic_block pre_header
,
307 HOST_WIDEST_INT
* count
)
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
));
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. */
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. */
352 set_node_sched_params (ddg_ptr g
)
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
];
373 print_node_sched_params (FILE * file
, int num_nodes
)
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
;
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. */
402 calculate_maxii (ddg_ptr g
)
407 for (i
= 0; i
< g
->num_nodes
; i
++)
409 ddg_node_ptr u
= &g
->nodes
[i
];
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
;
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.
432 static struct undo_replace_buff_elem
*
433 generate_reg_moves (partial_schedule_ptr ps
)
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
];
444 int nreg_moves
= 0, i_reg_move
;
445 sbitmap
*uses_of_defs
;
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
))
465 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
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
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
))
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
;
525 rep
->next
= reg_move_replaces
;
526 reg_move_replaces
= rep
;
529 replace_rtx (g
->nodes
[i_use
].insn
, old_reg
, new_reg
);
534 sbitmap_vector_free (uses_of_defs
);
536 return reg_move_replaces
;
539 /* We call this when we want to undo the SMS schedule for a given loop.
540 One of the things that we do is to delete the register moves generated
541 for the sake of SMS; this function deletes the register move instructions
542 recorded in the undo buffer. */
544 undo_generate_reg_moves (partial_schedule_ptr ps
,
545 struct undo_replace_buff_elem
*reg_move_replaces
)
549 for (i
= 0; i
< ps
->g
->num_nodes
; i
++)
551 ddg_node_ptr u
= &ps
->g
->nodes
[i
];
553 rtx crr
= SCHED_FIRST_REG_MOVE (u
);
555 for (j
= 0; j
< SCHED_NREG_MOVES (u
); j
++)
557 prev
= PREV_INSN (crr
);
561 SCHED_FIRST_REG_MOVE (u
) = NULL_RTX
;
564 while (reg_move_replaces
)
566 struct undo_replace_buff_elem
*rep
= reg_move_replaces
;
568 reg_move_replaces
= reg_move_replaces
->next
;
569 replace_rtx (rep
->insn
, rep
->new_reg
, rep
->orig_reg
);
573 /* Free memory allocated for the undo buffer. */
575 free_undo_replace_buff (struct undo_replace_buff_elem
*reg_move_replaces
)
578 while (reg_move_replaces
)
580 struct undo_replace_buff_elem
*rep
= reg_move_replaces
;
582 reg_move_replaces
= reg_move_replaces
->next
;
587 /* Bump the SCHED_TIMEs of all nodes to start from zero. Set the values
588 of SCHED_ROW and SCHED_STAGE. */
590 normalize_sched_times (partial_schedule_ptr ps
)
594 int amount
= PS_MIN_CYCLE (ps
);
597 /* Don't include the closing branch assuming that it is the last node. */
598 for (i
= 0; i
< g
->num_nodes
- 1; i
++)
600 ddg_node_ptr u
= &g
->nodes
[i
];
601 int normalized_time
= SCHED_TIME (u
) - amount
;
603 gcc_assert (normalized_time
>= 0);
605 SCHED_TIME (u
) = normalized_time
;
606 SCHED_ROW (u
) = normalized_time
% ii
;
607 SCHED_STAGE (u
) = normalized_time
/ ii
;
611 /* Set SCHED_COLUMN of each node according to its position in PS. */
613 set_columns_for_ps (partial_schedule_ptr ps
)
617 for (row
= 0; row
< ps
->ii
; row
++)
619 ps_insn_ptr cur_insn
= ps
->rows
[row
];
622 for (; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
623 SCHED_COLUMN (cur_insn
->node
) = column
++;
627 /* Permute the insns according to their order in PS, from row 0 to
628 row ii-1, and position them right before LAST. This schedules
629 the insns of the loop kernel. */
631 permute_partial_schedule (partial_schedule_ptr ps
, rtx last
)
637 for (row
= 0; row
< ii
; row
++)
638 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
639 if (PREV_INSN (last
) != ps_ij
->node
->insn
)
640 reorder_insns_nobb (ps_ij
->node
->first_note
, ps_ij
->node
->insn
,
644 /* As part of undoing SMS we return to the original ordering of the
645 instructions inside the loop kernel. Given the partial schedule PS, this
646 function returns the ordering of the instruction according to their CUID
647 in the DDG (PS->G), which is the original order of the instruction before
650 undo_permute_partial_schedule (partial_schedule_ptr ps
, rtx last
)
654 for (i
= 0 ; i
< ps
->g
->num_nodes
; i
++)
655 if (last
== ps
->g
->nodes
[i
].insn
656 || last
== ps
->g
->nodes
[i
].first_note
)
658 else if (PREV_INSN (last
) != ps
->g
->nodes
[i
].insn
)
659 reorder_insns_nobb (ps
->g
->nodes
[i
].first_note
, ps
->g
->nodes
[i
].insn
,
663 /* Used to generate the prologue & epilogue. Duplicate the subset of
664 nodes whose stages are between FROM_STAGE and TO_STAGE (inclusive
665 of both), together with a prefix/suffix of their reg_moves. */
667 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
668 int to_stage
, int for_prolog
)
673 for (row
= 0; row
< ps
->ii
; row
++)
674 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
676 ddg_node_ptr u_node
= ps_ij
->node
;
678 rtx reg_move
= NULL_RTX
;
682 /* SCHED_STAGE (u_node) >= from_stage == 0. Generate increasing
683 number of reg_moves starting with the second occurrence of
684 u_node, which is generated if its SCHED_STAGE <= to_stage. */
685 i_reg_moves
= to_stage
- SCHED_STAGE (u_node
) + 1;
686 i_reg_moves
= MAX (i_reg_moves
, 0);
687 i_reg_moves
= MIN (i_reg_moves
, SCHED_NREG_MOVES (u_node
));
689 /* The reg_moves start from the *first* reg_move backwards. */
692 reg_move
= SCHED_FIRST_REG_MOVE (u_node
);
693 for (j
= 1; j
< i_reg_moves
; j
++)
694 reg_move
= PREV_INSN (reg_move
);
697 else /* It's for the epilog. */
699 /* SCHED_STAGE (u_node) <= to_stage. Generate all reg_moves,
700 starting to decrease one stage after u_node no longer occurs;
701 that is, generate all reg_moves until
702 SCHED_STAGE (u_node) == from_stage - 1. */
703 i_reg_moves
= SCHED_NREG_MOVES (u_node
)
704 - (from_stage
- SCHED_STAGE (u_node
) - 1);
705 i_reg_moves
= MAX (i_reg_moves
, 0);
706 i_reg_moves
= MIN (i_reg_moves
, SCHED_NREG_MOVES (u_node
));
708 /* The reg_moves start from the *last* reg_move forwards. */
711 reg_move
= SCHED_FIRST_REG_MOVE (u_node
);
712 for (j
= 1; j
< SCHED_NREG_MOVES (u_node
); j
++)
713 reg_move
= PREV_INSN (reg_move
);
717 for (j
= 0; j
< i_reg_moves
; j
++, reg_move
= NEXT_INSN (reg_move
))
718 emit_insn (copy_rtx (PATTERN (reg_move
)));
719 if (SCHED_STAGE (u_node
) >= from_stage
720 && SCHED_STAGE (u_node
) <= to_stage
)
721 duplicate_insn_chain (u_node
->first_note
, u_node
->insn
);
726 /* Generate the instructions (including reg_moves) for prolog & epilog. */
728 generate_prolog_epilog (partial_schedule_ptr ps
, struct loop
* loop
, rtx count_reg
)
731 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
734 /* Generate the prolog, inserting its insns on the loop-entry edge. */
738 /* Generate a subtract instruction at the beginning of the prolog to
739 adjust the loop count by STAGE_COUNT. */
740 emit_insn (gen_sub2_insn (count_reg
, GEN_INT (last_stage
)));
742 for (i
= 0; i
< last_stage
; i
++)
743 duplicate_insns_of_cycles (ps
, 0, i
, 1);
745 /* Put the prolog , on the one and only entry edge. */
746 e
= loop_preheader_edge (loop
);
747 loop_split_edge_with(e
, get_insns());
751 /* Generate the epilog, inserting its insns on the loop-exit edge. */
754 for (i
= 0; i
< last_stage
; i
++)
755 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, 0);
757 /* Put the epilogue on the one and only one exit edge. */
758 gcc_assert (loop
->single_exit
);
759 e
= loop
->single_exit
;
760 loop_split_edge_with(e
, get_insns());
764 /* Return the line note insn preceding INSN, for debugging. Taken from
767 find_line_note (rtx insn
)
769 for (; insn
; insn
= PREV_INSN (insn
))
771 && NOTE_LINE_NUMBER (insn
) >= 0)
777 /* Return true if all the BBs of the loop are empty except the
780 loop_single_full_bb_p (struct loop
*loop
)
783 basic_block
*bbs
= get_loop_body (loop
);
785 for (i
= 0; i
< loop
->num_nodes
; i
++)
788 bool empty_bb
= true;
790 if (bbs
[i
] == loop
->header
)
793 /* Make sure that basic blocks other than the header
794 have only notes labels or jumps. */
795 get_block_head_tail (bbs
[i
]->index
, &head
, &tail
);
796 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
798 if (NOTE_P (head
) || LABEL_P (head
)
799 || (INSN_P (head
) && JUMP_P (head
)))
815 /* A simple loop from SMS point of view; it is a loop that is composed of
816 either a single basic block or two BBs - a header and a latch. */
817 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
818 && (EDGE_COUNT (loop->latch->preds) == 1) \
819 && (EDGE_COUNT (loop->latch->succs) == 1))
821 /* Return true if the loop is in its canonical form and false if not.
822 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
824 loop_canon_p (struct loop
*loop
)
827 if (loop
->inner
|| ! loop
->outer
)
830 if (!loop
->single_exit
)
834 rtx line_note
= find_line_note (BB_END (loop
->header
));
836 fprintf (dump_file
, "SMS loop many exits ");
839 expanded_location xloc
;
840 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
841 fprintf (dump_file
, " %s %d (file, line)\n",
842 xloc
.file
, xloc
.line
);
848 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
852 rtx line_note
= find_line_note (BB_END (loop
->header
));
854 fprintf (dump_file
, "SMS loop many BBs. ");
857 expanded_location xloc
;
858 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
859 fprintf (dump_file
, " %s %d (file, line)\n",
860 xloc
.file
, xloc
.line
);
869 /* If there are more than one entry for the loop,
870 make it one by splitting the first entry edge and
871 redirecting the others to the new BB. */
873 canon_loop (struct loop
*loop
)
878 /* Avoid annoying special cases of edges going to exit
880 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR
->preds
)
881 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
882 loop_split_edge_with (e
, NULL_RTX
);
884 if (loop
->latch
== loop
->header
885 || EDGE_COUNT (loop
->latch
->succs
) > 1)
887 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
888 if (e
->src
== loop
->latch
)
890 loop_split_edge_with (e
, NULL_RTX
);
894 /* Main entry point, perform SMS scheduling on the loops of the function
895 that consist of single basic blocks. */
899 static int passes
= 0;
904 unsigned i
,num_loops
;
905 partial_schedule_ptr ps
;
908 basic_block bb
= NULL
;
909 /* vars to the versioning only if needed*/
911 basic_block condition_bb
= NULL
;
913 gcov_type trip_count
= 0;
915 loops
= loop_optimizer_init (LOOPS_HAVE_PREHEADERS
916 | LOOPS_HAVE_MARKED_SINGLE_EXITS
);
918 return; /* There is no loops to schedule. */
920 /* Initialize issue_rate. */
921 if (targetm
.sched
.issue_rate
)
923 int temp
= reload_completed
;
925 reload_completed
= 1;
926 issue_rate
= targetm
.sched
.issue_rate ();
927 reload_completed
= temp
;
932 /* Initialize the scheduler. */
933 current_sched_info
= &sms_sched_info
;
936 /* Init Data Flow analysis, to be used in interloop dep calculation. */
937 df
= df_init (DF_HARD_REGS
| DF_EQUIV_NOTES
| DF_SUBREGS
);
938 df_rd_add_problem (df
);
939 df_ru_add_problem (df
);
940 df_chain_add_problem (df
, DF_DU_CHAIN
| DF_UD_CHAIN
);
943 /* Allocate memory to hold the DDG array one entry for each loop.
944 We use loop->num as index into this array. */
945 g_arr
= XCNEWVEC (ddg_ptr
, loops
->num
);
948 /* Build DDGs for all the relevant loops and hold them in G_ARR
949 indexed by the loop index. */
950 for (i
= 0; i
< loops
->num
; i
++)
954 struct loop
*loop
= loops
->parray
[i
];
957 if ((passes
++ > MAX_SMS_LOOP_NUMBER
) && (MAX_SMS_LOOP_NUMBER
!= -1))
960 fprintf (dump_file
, "SMS reached MAX_PASSES... \n");
965 if (! loop_canon_p (loop
))
968 if (! loop_single_full_bb_p (loop
))
973 get_block_head_tail (bb
->index
, &head
, &tail
);
974 latch_edge
= loop_latch_edge (loop
);
975 gcc_assert (loop
->single_exit
);
976 if (loop
->single_exit
->count
)
977 trip_count
= latch_edge
->count
/ loop
->single_exit
->count
;
979 /* Perfrom SMS only on loops that their average count is above threshold. */
981 if ( latch_edge
->count
982 && (latch_edge
->count
< loop
->single_exit
->count
* SMS_LOOP_AVERAGE_COUNT_THRESHOLD
))
986 rtx line_note
= find_line_note (tail
);
990 expanded_location xloc
;
991 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
992 fprintf (dump_file
, "SMS bb %s %d (file, line)\n",
993 xloc
.file
, xloc
.line
);
995 fprintf (dump_file
, "SMS single-bb-loop\n");
996 if (profile_info
&& flag_branch_probabilities
)
998 fprintf (dump_file
, "SMS loop-count ");
999 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1000 (HOST_WIDEST_INT
) bb
->count
);
1001 fprintf (dump_file
, "\n");
1002 fprintf (dump_file
, "SMS trip-count ");
1003 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1004 (HOST_WIDEST_INT
) trip_count
);
1005 fprintf (dump_file
, "\n");
1006 fprintf (dump_file
, "SMS profile-sum-max ");
1007 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1008 (HOST_WIDEST_INT
) profile_info
->sum_max
);
1009 fprintf (dump_file
, "\n");
1015 /* Make sure this is a doloop. */
1016 if ( !(count_reg
= doloop_register_get (tail
)))
1019 /* Don't handle BBs with calls or barriers, or !single_set insns. */
1020 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1023 || (INSN_P (insn
) && !JUMP_P (insn
)
1024 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
1027 if (insn
!= NEXT_INSN (tail
))
1032 fprintf (dump_file
, "SMS loop-with-call\n");
1033 else if (BARRIER_P (insn
))
1034 fprintf (dump_file
, "SMS loop-with-barrier\n");
1036 fprintf (dump_file
, "SMS loop-with-not-single-set\n");
1037 print_rtl_single (dump_file
, insn
);
1043 if (! (g
= create_ddg (bb
, df
, 0)))
1046 fprintf (dump_file
, "SMS doloop\n");
1053 /* Release Data Flow analysis data structures. */
1057 /* We don't want to perform SMS on new loops - created by versioning. */
1058 num_loops
= loops
->num
;
1059 /* Go over the built DDGs and perfrom SMS for each one of them. */
1060 for (i
= 0; i
< num_loops
; i
++)
1063 rtx count_reg
, count_init
;
1065 unsigned stage_count
= 0;
1066 HOST_WIDEST_INT loop_count
= 0;
1067 struct loop
*loop
= loops
->parray
[i
];
1069 if (! (g
= g_arr
[i
]))
1073 print_ddg (dump_file
, g
);
1075 get_block_head_tail (loop
->header
->index
, &head
, &tail
);
1077 latch_edge
= loop_latch_edge (loop
);
1078 gcc_assert (loop
->single_exit
);
1079 if (loop
->single_exit
->count
)
1080 trip_count
= latch_edge
->count
/ loop
->single_exit
->count
;
1084 rtx line_note
= find_line_note (tail
);
1088 expanded_location xloc
;
1089 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
1090 fprintf (dump_file
, "SMS bb %s %d (file, line)\n",
1091 xloc
.file
, xloc
.line
);
1093 fprintf (dump_file
, "SMS single-bb-loop\n");
1094 if (profile_info
&& flag_branch_probabilities
)
1096 fprintf (dump_file
, "SMS loop-count ");
1097 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1098 (HOST_WIDEST_INT
) bb
->count
);
1099 fprintf (dump_file
, "\n");
1100 fprintf (dump_file
, "SMS profile-sum-max ");
1101 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1102 (HOST_WIDEST_INT
) profile_info
->sum_max
);
1103 fprintf (dump_file
, "\n");
1105 fprintf (dump_file
, "SMS doloop\n");
1106 fprintf (dump_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1107 fprintf (dump_file
, "SMS num-loads %d\n", g
->num_loads
);
1108 fprintf (dump_file
, "SMS num-stores %d\n", g
->num_stores
);
1112 /* In case of th loop have doloop register it gets special
1114 count_init
= NULL_RTX
;
1115 if ((count_reg
= doloop_register_get (tail
)))
1117 basic_block pre_header
;
1119 pre_header
= loop_preheader_edge (loop
)->src
;
1120 count_init
= const_iteration_count (count_reg
, pre_header
,
1123 gcc_assert (count_reg
);
1125 if (dump_file
&& count_init
)
1127 fprintf (dump_file
, "SMS const-doloop ");
1128 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1130 fprintf (dump_file
, "\n");
1133 node_order
= XNEWVEC (int, g
->num_nodes
);
1135 mii
= 1; /* Need to pass some estimate of mii. */
1136 rec_mii
= sms_order_nodes (g
, mii
, node_order
);
1137 mii
= MAX (res_MII (g
), rec_mii
);
1138 maxii
= (calculate_maxii (g
) * SMS_MAX_II_FACTOR
) / 100;
1141 fprintf (dump_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1142 rec_mii
, mii
, maxii
);
1144 /* After sms_order_nodes and before sms_schedule_by_order, to copy over
1146 set_node_sched_params (g
);
1148 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
);
1151 stage_count
= PS_STAGE_COUNT (ps
);
1153 /* Stage count of 1 means that there is no interleaving between
1154 iterations, let the scheduling passes do the job. */
1156 || (count_init
&& (loop_count
<= stage_count
))
1157 || (flag_branch_probabilities
&& (trip_count
<= stage_count
)))
1161 fprintf (dump_file
, "SMS failed... \n");
1162 fprintf (dump_file
, "SMS sched-failed (stage-count=%d, loop-count=", stage_count
);
1163 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, loop_count
);
1164 fprintf (dump_file
, ", trip-count=");
1165 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, trip_count
);
1166 fprintf (dump_file
, ")\n");
1172 int orig_cycles
= kernel_number_of_cycles (BB_HEAD (g
->bb
), BB_END (g
->bb
));
1174 struct undo_replace_buff_elem
*reg_move_replaces
;
1179 "SMS succeeded %d %d (with ii, sc)\n", ps
->ii
,
1181 print_partial_schedule (ps
, dump_file
);
1183 "SMS Branch (%d) will later be scheduled at cycle %d.\n",
1184 g
->closing_branch
->cuid
, PS_MIN_CYCLE (ps
) - 1);
1187 /* Set the stage boundaries. If the DDG is built with closing_branch_deps,
1188 the closing_branch was scheduled and should appear in the last (ii-1)
1189 row. Otherwise, we are free to schedule the branch, and we let nodes
1190 that were scheduled at the first PS_MIN_CYCLE cycle appear in the first
1191 row; this should reduce stage_count to minimum. */
1192 normalize_sched_times (ps
);
1193 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
1194 set_columns_for_ps (ps
);
1196 /* Generate the kernel just to be able to measure its cycles. */
1197 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1198 reg_move_replaces
= generate_reg_moves (ps
);
1200 /* Get the number of cycles the new kernel expect to execute in. */
1201 new_cycles
= kernel_number_of_cycles (BB_HEAD (g
->bb
), BB_END (g
->bb
));
1203 /* Get back to the original loop so we can do loop versioning. */
1204 undo_permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1205 if (reg_move_replaces
)
1206 undo_generate_reg_moves (ps
, reg_move_replaces
);
1208 if ( new_cycles
>= orig_cycles
)
1210 /* SMS is not profitable so undo the permutation and reg move generation
1211 and return the kernel to its original state. */
1213 fprintf (dump_file
, "Undoing SMS because it is not profitable.\n");
1220 /* case the BCT count is not known , Do loop-versioning */
1221 if (count_reg
&& ! count_init
)
1223 rtx comp_rtx
= gen_rtx_fmt_ee (GT
, VOIDmode
, count_reg
,
1224 GEN_INT(stage_count
));
1226 nloop
= loop_version (loops
, loop
, comp_rtx
, &condition_bb
,
1230 /* Set new iteration count of loop kernel. */
1231 if (count_reg
&& count_init
)
1232 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1235 /* Now apply the scheduled kernel to the RTL of the loop. */
1236 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1238 /* Mark this loop as software pipelined so the later
1239 scheduling passes doesn't touch it. */
1240 if (! flag_resched_modulo_sched
)
1241 g
->bb
->flags
|= BB_DISABLE_SCHEDULE
;
1242 /* The life-info is not valid any more. */
1243 g
->bb
->flags
|= BB_DIRTY
;
1245 reg_move_replaces
= generate_reg_moves (ps
);
1247 print_node_sched_params (dump_file
, g
->num_nodes
);
1248 /* Generate prolog and epilog. */
1249 if (count_reg
&& !count_init
)
1250 generate_prolog_epilog (ps
, loop
, count_reg
);
1252 generate_prolog_epilog (ps
, loop
, NULL_RTX
);
1254 free_undo_replace_buff (reg_move_replaces
);
1257 free_partial_schedule (ps
);
1258 free (node_sched_params
);
1265 /* Release scheduler data, needed until now because of DFA. */
1267 loop_optimizer_finalize (loops
);
1270 /* The SMS scheduling algorithm itself
1271 -----------------------------------
1272 Input: 'O' an ordered list of insns of a loop.
1273 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1275 'Q' is the empty Set
1276 'PS' is the partial schedule; it holds the currently scheduled nodes with
1278 'PSP' previously scheduled predecessors.
1279 'PSS' previously scheduled successors.
1280 't(u)' the cycle where u is scheduled.
1281 'l(u)' is the latency of u.
1282 'd(v,u)' is the dependence distance from v to u.
1283 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1284 the node ordering phase.
1285 'check_hardware_resources_conflicts(u, PS, c)'
1286 run a trace around cycle/slot through DFA model
1287 to check resource conflicts involving instruction u
1288 at cycle c given the partial schedule PS.
1289 'add_to_partial_schedule_at_time(u, PS, c)'
1290 Add the node/instruction u to the partial schedule
1292 'calculate_register_pressure(PS)'
1293 Given a schedule of instructions, calculate the register
1294 pressure it implies. One implementation could be the
1295 maximum number of overlapping live ranges.
1296 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1297 registers available in the hardware.
1301 3. for each node u in O in pre-computed order
1302 4. if (PSP(u) != Q && PSS(u) == Q) then
1303 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1304 6. start = Early_start; end = Early_start + II - 1; step = 1
1305 11. else if (PSP(u) == Q && PSS(u) != Q) then
1306 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1307 13. start = Late_start; end = Late_start - II + 1; step = -1
1308 14. else if (PSP(u) != Q && PSS(u) != Q) then
1309 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1310 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1311 17. start = Early_start;
1312 18. end = min(Early_start + II - 1 , Late_start);
1314 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1315 21. start = ASAP(u); end = start + II - 1; step = 1
1319 24. for (c = start ; c != end ; c += step)
1320 25. if check_hardware_resources_conflicts(u, PS, c) then
1321 26. add_to_partial_schedule_at_time(u, PS, c)
1326 31. if (success == false) then
1328 33. if (II > maxII) then
1329 34. finish - failed to schedule
1334 39. if (calculate_register_pressure(PS) > maxRP) then
1337 42. compute epilogue & prologue
1338 43. finish - succeeded to schedule
1341 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1342 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1343 set to 0 to save compile time. */
1344 #define DFA_HISTORY SMS_DFA_HISTORY
1346 /* Given the partial schedule PS, this function calculates and returns the
1347 cycles in which we can schedule the node with the given index I.
1348 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1349 noticed that there are several cases in which we fail to SMS the loop
1350 because the sched window of a node is empty due to tight data-deps. In
1351 such cases we want to unschedule some of the predecessors/successors
1352 until we get non-empty scheduling window. It returns -1 if the
1353 scheduling window is empty and zero otherwise. */
1356 get_sched_window (partial_schedule_ptr ps
, int *nodes_order
, int i
,
1357 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
, int *end_p
)
1359 int start
, step
, end
;
1361 int u
= nodes_order
[i
];
1362 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
1363 sbitmap psp
= sbitmap_alloc (ps
->g
->num_nodes
);
1364 sbitmap pss
= sbitmap_alloc (ps
->g
->num_nodes
);
1365 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1366 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1370 /* 1. compute sched window for u (start, end, step). */
1373 psp_not_empty
= sbitmap_a_and_b_cg (psp
, u_node_preds
, sched_nodes
);
1374 pss_not_empty
= sbitmap_a_and_b_cg (pss
, u_node_succs
, sched_nodes
);
1376 if (psp_not_empty
&& !pss_not_empty
)
1378 int early_start
= INT_MIN
;
1381 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1383 ddg_node_ptr v_node
= e
->src
;
1384 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1386 int node_st
= SCHED_TIME (v_node
)
1387 + e
->latency
- (e
->distance
* ii
);
1389 early_start
= MAX (early_start
, node_st
);
1391 if (e
->data_type
== MEM_DEP
)
1392 end
= MIN (end
, SCHED_TIME (v_node
) + ii
- 1);
1395 start
= early_start
;
1396 end
= MIN (end
, early_start
+ ii
);
1400 else if (!psp_not_empty
&& pss_not_empty
)
1402 int late_start
= INT_MAX
;
1405 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1407 ddg_node_ptr v_node
= e
->dest
;
1408 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1410 late_start
= MIN (late_start
,
1411 SCHED_TIME (v_node
) - e
->latency
1412 + (e
->distance
* ii
));
1413 if (e
->data_type
== MEM_DEP
)
1414 end
= MAX (end
, SCHED_TIME (v_node
) - ii
+ 1);
1418 end
= MAX (end
, late_start
- ii
);
1422 else if (psp_not_empty
&& pss_not_empty
)
1424 int early_start
= INT_MIN
;
1425 int late_start
= INT_MAX
;
1429 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1431 ddg_node_ptr v_node
= e
->src
;
1433 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1435 early_start
= MAX (early_start
,
1436 SCHED_TIME (v_node
) + e
->latency
1437 - (e
->distance
* ii
));
1438 if (e
->data_type
== MEM_DEP
)
1439 end
= MIN (end
, SCHED_TIME (v_node
) + ii
- 1);
1442 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1444 ddg_node_ptr v_node
= e
->dest
;
1446 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1448 late_start
= MIN (late_start
,
1449 SCHED_TIME (v_node
) - e
->latency
1450 + (e
->distance
* ii
));
1451 if (e
->data_type
== MEM_DEP
)
1452 start
= MAX (start
, SCHED_TIME (v_node
) - ii
+ 1);
1455 start
= MAX (start
, early_start
);
1456 end
= MIN (end
, MIN (early_start
+ ii
, late_start
+ 1));
1459 else /* psp is empty && pss is empty. */
1461 start
= SCHED_ASAP (u_node
);
1472 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
1478 /* This function implements the scheduling algorithm for SMS according to the
1480 static partial_schedule_ptr
1481 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
)
1485 int try_again_with_larger_ii
= true;
1486 int num_nodes
= g
->num_nodes
;
1488 int start
, end
, step
; /* Place together into one struct? */
1489 sbitmap sched_nodes
= sbitmap_alloc (num_nodes
);
1490 sbitmap must_precede
= sbitmap_alloc (num_nodes
);
1491 sbitmap must_follow
= sbitmap_alloc (num_nodes
);
1492 sbitmap tobe_scheduled
= sbitmap_alloc (num_nodes
);
1494 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
, DFA_HISTORY
);
1496 sbitmap_ones (tobe_scheduled
);
1497 sbitmap_zero (sched_nodes
);
1499 while ((! sbitmap_equal (tobe_scheduled
, sched_nodes
)
1500 || try_again_with_larger_ii
) && ii
< maxii
)
1503 bool unscheduled_nodes
= false;
1506 fprintf(dump_file
, "Starting with ii=%d\n", ii
);
1507 if (try_again_with_larger_ii
)
1509 try_again_with_larger_ii
= false;
1510 sbitmap_zero (sched_nodes
);
1513 for (i
= 0; i
< num_nodes
; i
++)
1515 int u
= nodes_order
[i
];
1516 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
1517 rtx insn
= u_node
->insn
;
1521 RESET_BIT (tobe_scheduled
, u
);
1525 if (JUMP_P (insn
)) /* Closing branch handled later. */
1527 RESET_BIT (tobe_scheduled
, u
);
1531 if (TEST_BIT (sched_nodes
, u
))
1534 /* Try to get non-empty scheduling window. */
1536 while (get_sched_window (ps
, nodes_order
, i
, sched_nodes
, ii
, &start
, &step
, &end
) < 0
1539 unscheduled_nodes
= true;
1540 if (TEST_BIT (NODE_PREDECESSORS (u_node
), nodes_order
[j
- 1])
1541 || TEST_BIT (NODE_SUCCESSORS (u_node
), nodes_order
[j
- 1]))
1543 ps_unschedule_node (ps
, &ps
->g
->nodes
[nodes_order
[j
- 1]]);
1544 RESET_BIT (sched_nodes
, nodes_order
[j
- 1]);
1550 /* ??? Try backtracking instead of immediately ii++? */
1552 try_again_with_larger_ii
= true;
1553 reset_partial_schedule (ps
, ii
);
1556 /* 2. Try scheduling u in window. */
1558 fprintf(dump_file
, "Trying to schedule node %d in (%d .. %d) step %d\n",
1559 u
, start
, end
, step
);
1561 /* use must_follow & must_precede bitmaps to determine order
1562 of nodes within the cycle. */
1563 sbitmap_zero (must_precede
);
1564 sbitmap_zero (must_follow
);
1565 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1566 if (TEST_BIT (sched_nodes
, e
->src
->cuid
)
1567 && e
->latency
== (ii
* e
->distance
)
1568 && start
== SCHED_TIME (e
->src
))
1569 SET_BIT (must_precede
, e
->src
->cuid
);
1571 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1572 if (TEST_BIT (sched_nodes
, e
->dest
->cuid
)
1573 && e
->latency
== (ii
* e
->distance
)
1574 && end
== SCHED_TIME (e
->dest
))
1575 SET_BIT (must_follow
, e
->dest
->cuid
);
1578 if ((step
> 0 && start
< end
) || (step
< 0 && start
> end
))
1579 for (c
= start
; c
!= end
; c
+= step
)
1583 psi
= ps_add_node_check_conflicts (ps
, u_node
, c
,
1589 SCHED_TIME (u_node
) = c
;
1590 SET_BIT (sched_nodes
, u
);
1593 fprintf(dump_file
, "Schedule in %d\n", c
);
1599 /* ??? Try backtracking instead of immediately ii++? */
1601 try_again_with_larger_ii
= true;
1602 reset_partial_schedule (ps
, ii
);
1605 if (unscheduled_nodes
)
1608 /* ??? If (success), check register pressure estimates. */
1609 } /* Continue with next node. */
1610 } /* While try_again_with_larger_ii. */
1612 sbitmap_free (sched_nodes
);
1613 sbitmap_free (must_precede
);
1614 sbitmap_free (must_follow
);
1615 sbitmap_free (tobe_scheduled
);
1619 free_partial_schedule (ps
);
1626 /* This page implements the algorithm for ordering the nodes of a DDG
1627 for modulo scheduling, activated through the
1628 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
1630 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
1631 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
1632 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
1633 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
1634 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
1635 #define DEPTH(x) (ASAP ((x)))
1637 typedef struct node_order_params
* nopa
;
1639 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
1640 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
1641 static nopa
calculate_order_params (ddg_ptr
, int mii
);
1642 static int find_max_asap (ddg_ptr
, sbitmap
);
1643 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
1644 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
1646 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
1648 struct node_order_params
1655 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
1657 check_nodes_order (int *node_order
, int num_nodes
)
1660 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1664 for (i
= 0; i
< num_nodes
; i
++)
1666 int u
= node_order
[i
];
1668 gcc_assert (u
< num_nodes
&& u
>= 0 && !TEST_BIT (tmp
, u
));
1676 /* Order the nodes of G for scheduling and pass the result in
1677 NODE_ORDER. Also set aux.count of each node to ASAP.
1678 Return the recMII for the given DDG. */
1680 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
)
1684 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
1686 nopa nops
= calculate_order_params (g
, mii
);
1688 order_nodes_of_sccs (sccs
, node_order
);
1690 if (sccs
->num_sccs
> 0)
1691 /* First SCC has the largest recurrence_length. */
1692 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
1694 /* Save ASAP before destroying node_order_params. */
1695 for (i
= 0; i
< g
->num_nodes
; i
++)
1697 ddg_node_ptr v
= &g
->nodes
[i
];
1698 v
->aux
.count
= ASAP (v
);
1702 free_ddg_all_sccs (sccs
);
1703 check_nodes_order (node_order
, g
->num_nodes
);
1709 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
1712 ddg_ptr g
= all_sccs
->ddg
;
1713 int num_nodes
= g
->num_nodes
;
1714 sbitmap prev_sccs
= sbitmap_alloc (num_nodes
);
1715 sbitmap on_path
= sbitmap_alloc (num_nodes
);
1716 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1717 sbitmap ones
= sbitmap_alloc (num_nodes
);
1719 sbitmap_zero (prev_sccs
);
1720 sbitmap_ones (ones
);
1722 /* Perfrom the node ordering starting from the SCC with the highest recMII.
1723 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
1724 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
1726 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
1728 /* Add nodes on paths from previous SCCs to the current SCC. */
1729 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
1730 sbitmap_a_or_b (tmp
, scc
->nodes
, on_path
);
1732 /* Add nodes on paths from the current SCC to previous SCCs. */
1733 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
1734 sbitmap_a_or_b (tmp
, tmp
, on_path
);
1736 /* Remove nodes of previous SCCs from current extended SCC. */
1737 sbitmap_difference (tmp
, tmp
, prev_sccs
);
1739 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
1740 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
1743 /* Handle the remaining nodes that do not belong to any scc. Each call
1744 to order_nodes_in_scc handles a single connected component. */
1745 while (pos
< g
->num_nodes
)
1747 sbitmap_difference (tmp
, ones
, prev_sccs
);
1748 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
1750 sbitmap_free (prev_sccs
);
1751 sbitmap_free (on_path
);
1753 sbitmap_free (ones
);
1756 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
1757 static struct node_order_params
*
1758 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
)
1762 int num_nodes
= g
->num_nodes
;
1764 /* Allocate a place to hold ordering params for each node in the DDG. */
1765 nopa node_order_params_arr
;
1767 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
1768 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
1769 sizeof (struct node_order_params
));
1771 /* Set the aux pointer of each node to point to its order_params structure. */
1772 for (u
= 0; u
< num_nodes
; u
++)
1773 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
1775 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
1776 calculate ASAP, ALAP, mobility, distance, and height for each node
1777 in the dependence (direct acyclic) graph. */
1779 /* We assume that the nodes in the array are in topological order. */
1782 for (u
= 0; u
< num_nodes
; u
++)
1784 ddg_node_ptr u_node
= &g
->nodes
[u
];
1787 for (e
= u_node
->in
; e
; e
= e
->next_in
)
1788 if (e
->distance
== 0)
1789 ASAP (u_node
) = MAX (ASAP (u_node
),
1790 ASAP (e
->src
) + e
->latency
);
1791 max_asap
= MAX (max_asap
, ASAP (u_node
));
1794 for (u
= num_nodes
- 1; u
> -1; u
--)
1796 ddg_node_ptr u_node
= &g
->nodes
[u
];
1798 ALAP (u_node
) = max_asap
;
1799 HEIGHT (u_node
) = 0;
1800 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1801 if (e
->distance
== 0)
1803 ALAP (u_node
) = MIN (ALAP (u_node
),
1804 ALAP (e
->dest
) - e
->latency
);
1805 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
1806 HEIGHT (e
->dest
) + e
->latency
);
1810 return node_order_params_arr
;
1814 find_max_asap (ddg_ptr g
, sbitmap nodes
)
1819 sbitmap_iterator sbi
;
1821 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
1823 ddg_node_ptr u_node
= &g
->nodes
[u
];
1825 if (max_asap
< ASAP (u_node
))
1827 max_asap
= ASAP (u_node
);
1835 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
1839 int min_mob
= INT_MAX
;
1841 sbitmap_iterator sbi
;
1843 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
1845 ddg_node_ptr u_node
= &g
->nodes
[u
];
1847 if (max_hv
< HEIGHT (u_node
))
1849 max_hv
= HEIGHT (u_node
);
1850 min_mob
= MOB (u_node
);
1853 else if ((max_hv
== HEIGHT (u_node
))
1854 && (min_mob
> MOB (u_node
)))
1856 min_mob
= MOB (u_node
);
1864 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
1868 int min_mob
= INT_MAX
;
1870 sbitmap_iterator sbi
;
1872 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
1874 ddg_node_ptr u_node
= &g
->nodes
[u
];
1876 if (max_dv
< DEPTH (u_node
))
1878 max_dv
= DEPTH (u_node
);
1879 min_mob
= MOB (u_node
);
1882 else if ((max_dv
== DEPTH (u_node
))
1883 && (min_mob
> MOB (u_node
)))
1885 min_mob
= MOB (u_node
);
1892 /* Places the nodes of SCC into the NODE_ORDER array starting
1893 at position POS, according to the SMS ordering algorithm.
1894 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
1895 the NODE_ORDER array, starting from position zero. */
1897 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
1898 int * node_order
, int pos
)
1900 enum sms_direction dir
;
1901 int num_nodes
= g
->num_nodes
;
1902 sbitmap workset
= sbitmap_alloc (num_nodes
);
1903 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1904 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
1905 sbitmap predecessors
= sbitmap_alloc (num_nodes
);
1906 sbitmap successors
= sbitmap_alloc (num_nodes
);
1908 sbitmap_zero (predecessors
);
1909 find_predecessors (predecessors
, g
, nodes_ordered
);
1911 sbitmap_zero (successors
);
1912 find_successors (successors
, g
, nodes_ordered
);
1915 if (sbitmap_a_and_b_cg (tmp
, predecessors
, scc
))
1917 sbitmap_copy (workset
, tmp
);
1920 else if (sbitmap_a_and_b_cg (tmp
, successors
, scc
))
1922 sbitmap_copy (workset
, tmp
);
1929 sbitmap_zero (workset
);
1930 if ((u
= find_max_asap (g
, scc
)) >= 0)
1931 SET_BIT (workset
, u
);
1935 sbitmap_zero (zero_bitmap
);
1936 while (!sbitmap_equal (workset
, zero_bitmap
))
1939 ddg_node_ptr v_node
;
1940 sbitmap v_node_preds
;
1941 sbitmap v_node_succs
;
1945 while (!sbitmap_equal (workset
, zero_bitmap
))
1947 v
= find_max_hv_min_mob (g
, workset
);
1948 v_node
= &g
->nodes
[v
];
1949 node_order
[pos
++] = v
;
1950 v_node_succs
= NODE_SUCCESSORS (v_node
);
1951 sbitmap_a_and_b (tmp
, v_node_succs
, scc
);
1953 /* Don't consider the already ordered successors again. */
1954 sbitmap_difference (tmp
, tmp
, nodes_ordered
);
1955 sbitmap_a_or_b (workset
, workset
, tmp
);
1956 RESET_BIT (workset
, v
);
1957 SET_BIT (nodes_ordered
, v
);
1960 sbitmap_zero (predecessors
);
1961 find_predecessors (predecessors
, g
, nodes_ordered
);
1962 sbitmap_a_and_b (workset
, predecessors
, scc
);
1966 while (!sbitmap_equal (workset
, zero_bitmap
))
1968 v
= find_max_dv_min_mob (g
, workset
);
1969 v_node
= &g
->nodes
[v
];
1970 node_order
[pos
++] = v
;
1971 v_node_preds
= NODE_PREDECESSORS (v_node
);
1972 sbitmap_a_and_b (tmp
, v_node_preds
, scc
);
1974 /* Don't consider the already ordered predecessors again. */
1975 sbitmap_difference (tmp
, tmp
, nodes_ordered
);
1976 sbitmap_a_or_b (workset
, workset
, tmp
);
1977 RESET_BIT (workset
, v
);
1978 SET_BIT (nodes_ordered
, v
);
1981 sbitmap_zero (successors
);
1982 find_successors (successors
, g
, nodes_ordered
);
1983 sbitmap_a_and_b (workset
, successors
, scc
);
1987 sbitmap_free (workset
);
1988 sbitmap_free (zero_bitmap
);
1989 sbitmap_free (predecessors
);
1990 sbitmap_free (successors
);
1995 /* This page contains functions for manipulating partial-schedules during
1996 modulo scheduling. */
1998 /* Create a partial schedule and allocate a memory to hold II rows. */
2000 static partial_schedule_ptr
2001 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2003 partial_schedule_ptr ps
= XNEW (struct partial_schedule
);
2004 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2006 ps
->history
= history
;
2007 ps
->min_cycle
= INT_MAX
;
2008 ps
->max_cycle
= INT_MIN
;
2014 /* Free the PS_INSNs in rows array of the given partial schedule.
2015 ??? Consider caching the PS_INSN's. */
2017 free_ps_insns (partial_schedule_ptr ps
)
2021 for (i
= 0; i
< ps
->ii
; i
++)
2025 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2028 ps
->rows
[i
] = ps_insn
;
2034 /* Free all the memory allocated to the partial schedule. */
2037 free_partial_schedule (partial_schedule_ptr ps
)
2046 /* Clear the rows array with its PS_INSNs, and create a new one with
2050 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2055 if (new_ii
== ps
->ii
)
2057 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2058 * sizeof (ps_insn_ptr
));
2059 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2061 ps
->min_cycle
= INT_MAX
;
2062 ps
->max_cycle
= INT_MIN
;
2065 /* Prints the partial schedule as an ii rows array, for each rows
2066 print the ids of the insns in it. */
2068 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2072 for (i
= 0; i
< ps
->ii
; i
++)
2074 ps_insn_ptr ps_i
= ps
->rows
[i
];
2076 fprintf (dump
, "\n[CYCLE %d ]: ", i
);
2079 fprintf (dump
, "%d, ",
2080 INSN_UID (ps_i
->node
->insn
));
2081 ps_i
= ps_i
->next_in_row
;
2086 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2088 create_ps_insn (ddg_node_ptr node
, int rest_count
, int cycle
)
2090 ps_insn_ptr ps_i
= XNEW (struct ps_insn
);
2093 ps_i
->next_in_row
= NULL
;
2094 ps_i
->prev_in_row
= NULL
;
2095 ps_i
->row_rest_count
= rest_count
;
2096 ps_i
->cycle
= cycle
;
2102 /* Removes the given PS_INSN from the partial schedule. Returns false if the
2103 node is not found in the partial schedule, else returns true. */
2105 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2112 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2113 if (! ps_i
->prev_in_row
)
2115 if (ps_i
!= ps
->rows
[row
])
2118 ps
->rows
[row
] = ps_i
->next_in_row
;
2120 ps
->rows
[row
]->prev_in_row
= NULL
;
2124 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
2125 if (ps_i
->next_in_row
)
2126 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
2132 /* Unlike what literature describes for modulo scheduling (which focuses
2133 on VLIW machines) the order of the instructions inside a cycle is
2134 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2135 where the current instruction should go relative to the already
2136 scheduled instructions in the given cycle. Go over these
2137 instructions and find the first possible column to put it in. */
2139 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2140 sbitmap must_precede
, sbitmap must_follow
)
2142 ps_insn_ptr next_ps_i
;
2143 ps_insn_ptr first_must_follow
= NULL
;
2144 ps_insn_ptr last_must_precede
= NULL
;
2150 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2152 /* Find the first must follow and the last must precede
2153 and insert the node immediately after the must precede
2154 but make sure that it there is no must follow after it. */
2155 for (next_ps_i
= ps
->rows
[row
];
2157 next_ps_i
= next_ps_i
->next_in_row
)
2159 if (TEST_BIT (must_follow
, next_ps_i
->node
->cuid
)
2160 && ! first_must_follow
)
2161 first_must_follow
= next_ps_i
;
2162 if (TEST_BIT (must_precede
, next_ps_i
->node
->cuid
))
2164 /* If we have already met a node that must follow, then
2165 there is no possible column. */
2166 if (first_must_follow
)
2169 last_must_precede
= next_ps_i
;
2173 /* Now insert the node after INSERT_AFTER_PSI. */
2175 if (! last_must_precede
)
2177 ps_i
->next_in_row
= ps
->rows
[row
];
2178 ps_i
->prev_in_row
= NULL
;
2179 if (ps_i
->next_in_row
)
2180 ps_i
->next_in_row
->prev_in_row
= ps_i
;
2181 ps
->rows
[row
] = ps_i
;
2185 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
2186 last_must_precede
->next_in_row
= ps_i
;
2187 ps_i
->prev_in_row
= last_must_precede
;
2188 if (ps_i
->next_in_row
)
2189 ps_i
->next_in_row
->prev_in_row
= ps_i
;
2195 /* Advances the PS_INSN one column in its current row; returns false
2196 in failure and true in success. Bit N is set in MUST_FOLLOW if
2197 the node with cuid N must be come after the node pointed to by
2198 PS_I when scheduled in the same cycle. */
2200 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2201 sbitmap must_follow
)
2203 ps_insn_ptr prev
, next
;
2205 ddg_node_ptr next_node
;
2210 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2212 if (! ps_i
->next_in_row
)
2215 next_node
= ps_i
->next_in_row
->node
;
2217 /* Check if next_in_row is dependent on ps_i, both having same sched
2218 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
2219 if (TEST_BIT (must_follow
, next_node
->cuid
))
2222 /* Advance PS_I over its next_in_row in the doubly linked list. */
2223 prev
= ps_i
->prev_in_row
;
2224 next
= ps_i
->next_in_row
;
2226 if (ps_i
== ps
->rows
[row
])
2227 ps
->rows
[row
] = next
;
2229 ps_i
->next_in_row
= next
->next_in_row
;
2231 if (next
->next_in_row
)
2232 next
->next_in_row
->prev_in_row
= ps_i
;
2234 next
->next_in_row
= ps_i
;
2235 ps_i
->prev_in_row
= next
;
2237 next
->prev_in_row
= prev
;
2239 prev
->next_in_row
= next
;
2244 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
2245 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
2246 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
2247 before/after (respectively) the node pointed to by PS_I when scheduled
2248 in the same cycle. */
2250 add_node_to_ps (partial_schedule_ptr ps
, ddg_node_ptr node
, int cycle
,
2251 sbitmap must_precede
, sbitmap must_follow
)
2255 int row
= SMODULO (cycle
, ps
->ii
);
2258 && ps
->rows
[row
]->row_rest_count
>= issue_rate
)
2262 rest_count
+= ps
->rows
[row
]->row_rest_count
;
2264 ps_i
= create_ps_insn (node
, rest_count
, cycle
);
2266 /* Finds and inserts PS_I according to MUST_FOLLOW and
2268 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
2277 /* Advance time one cycle. Assumes DFA is being used. */
2279 advance_one_cycle (void)
2281 if (targetm
.sched
.dfa_pre_cycle_insn
)
2282 state_transition (curr_state
,
2283 targetm
.sched
.dfa_pre_cycle_insn ());
2285 state_transition (curr_state
, NULL
);
2287 if (targetm
.sched
.dfa_post_cycle_insn
)
2288 state_transition (curr_state
,
2289 targetm
.sched
.dfa_post_cycle_insn ());
2292 /* Given the kernel of a loop (from FIRST_INSN to LAST_INSN), finds
2293 the number of cycles according to DFA that the kernel fits in,
2294 we use this to check if we done well with SMS after we add
2295 register moves. In some cases register moves overhead makes
2296 it even worse than the original loop. We want SMS to be performed
2297 when it gives less cycles after register moves are added. */
2299 kernel_number_of_cycles (rtx first_insn
, rtx last_insn
)
2303 int can_issue_more
= issue_rate
;
2305 state_reset (curr_state
);
2307 for (insn
= first_insn
;
2308 insn
!= NULL_RTX
&& insn
!= last_insn
;
2309 insn
= NEXT_INSN (insn
))
2311 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
2314 /* Check if there is room for the current insn. */
2315 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
2318 advance_one_cycle ();
2319 can_issue_more
= issue_rate
;
2322 /* Update the DFA state and return with failure if the DFA found
2323 recource conflicts. */
2324 if (state_transition (curr_state
, insn
) >= 0)
2327 advance_one_cycle ();
2328 can_issue_more
= issue_rate
;
2331 if (targetm
.sched
.variable_issue
)
2333 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
2334 insn
, can_issue_more
);
2335 /* A naked CLOBBER or USE generates no instruction, so don't
2336 let them consume issue slots. */
2337 else if (GET_CODE (PATTERN (insn
)) != USE
2338 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2344 /* Checks if PS has resource conflicts according to DFA, starting from
2345 FROM cycle to TO cycle; returns true if there are conflicts and false
2346 if there are no conflicts. Assumes DFA is being used. */
2348 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
2352 state_reset (curr_state
);
2354 for (cycle
= from
; cycle
<= to
; cycle
++)
2356 ps_insn_ptr crr_insn
;
2357 /* Holds the remaining issue slots in the current row. */
2358 int can_issue_more
= issue_rate
;
2360 /* Walk through the DFA for the current row. */
2361 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
2363 crr_insn
= crr_insn
->next_in_row
)
2365 rtx insn
= crr_insn
->node
->insn
;
2370 /* Check if there is room for the current insn. */
2371 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
2374 /* Update the DFA state and return with failure if the DFA found
2375 recource conflicts. */
2376 if (state_transition (curr_state
, insn
) >= 0)
2379 if (targetm
.sched
.variable_issue
)
2381 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
2382 insn
, can_issue_more
);
2383 /* A naked CLOBBER or USE generates no instruction, so don't
2384 let them consume issue slots. */
2385 else if (GET_CODE (PATTERN (insn
)) != USE
2386 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2390 /* Advance the DFA to the next cycle. */
2391 advance_one_cycle ();
2396 /* Checks if the given node causes resource conflicts when added to PS at
2397 cycle C. If not the node is added to PS and returned; otherwise zero
2398 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
2399 cuid N must be come before/after (respectively) the node pointed to by
2400 PS_I when scheduled in the same cycle. */
2402 ps_add_node_check_conflicts (partial_schedule_ptr ps
, ddg_node_ptr n
,
2403 int c
, sbitmap must_precede
,
2404 sbitmap must_follow
)
2406 int has_conflicts
= 0;
2409 /* First add the node to the PS, if this succeeds check for
2410 conflicts, trying different issue slots in the same row. */
2411 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
2412 return NULL
; /* Failed to insert the node at the given cycle. */
2414 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
2416 && ps_has_conflicts (ps
,
2420 /* Try different issue slots to find one that the given node can be
2421 scheduled in without conflicts. */
2422 while (has_conflicts
)
2424 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
2426 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
2428 && ps_has_conflicts (ps
,
2435 remove_node_from_ps (ps
, ps_i
);
2439 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
2440 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
2444 /* Rotate the rows of PS such that insns scheduled at time
2445 START_CYCLE will appear in row 0. Updates max/min_cycles. */
2447 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
2449 int i
, row
, backward_rotates
;
2450 int last_row
= ps
->ii
- 1;
2452 if (start_cycle
== 0)
2455 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
2457 /* Revisit later and optimize this into a single loop. */
2458 for (i
= 0; i
< backward_rotates
; i
++)
2460 ps_insn_ptr first_row
= ps
->rows
[0];
2462 for (row
= 0; row
< last_row
; row
++)
2463 ps
->rows
[row
] = ps
->rows
[row
+1];
2465 ps
->rows
[last_row
] = first_row
;
2468 ps
->max_cycle
-= start_cycle
;
2469 ps
->min_cycle
-= start_cycle
;
2472 /* Remove the node N from the partial schedule PS; because we restart the DFA
2473 each time we want to check for resource conflicts; this is equivalent to
2474 unscheduling the node N. */
2476 ps_unschedule_node (partial_schedule_ptr ps
, ddg_node_ptr n
)
2479 int row
= SMODULO (SCHED_TIME (n
), ps
->ii
);
2481 if (row
< 0 || row
> ps
->ii
)
2484 for (ps_i
= ps
->rows
[row
];
2485 ps_i
&& ps_i
->node
!= n
;
2486 ps_i
= ps_i
->next_in_row
);
2490 return remove_node_from_ps (ps
, ps_i
);
2492 #endif /* INSN_SCHEDULING */
2495 gate_handle_sms (void)
2497 return (optimize
> 0 && flag_modulo_sched
);
2501 /* Run instruction scheduler. */
2502 /* Perform SMS module scheduling. */
2504 rest_of_handle_sms (void)
2506 #ifdef INSN_SCHEDULING
2509 /* We want to be able to create new pseudos. */
2511 /* Collect loop information to be used in SMS. */
2512 cfg_layout_initialize (CLEANUP_UPDATE_LIFE
);
2515 /* Update the life information, because we add pseudos. */
2516 max_regno
= max_reg_num ();
2517 allocate_reg_info (max_regno
, FALSE
, FALSE
);
2518 update_life_info (NULL
, UPDATE_LIFE_GLOBAL_RM_NOTES
,
2521 | PROP_KILL_DEAD_CODE
2522 | PROP_SCAN_DEAD_CODE
));
2526 /* Finalize layout changes. */
2528 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2529 bb
->aux
= bb
->next_bb
;
2530 cfg_layout_finalize ();
2531 free_dominance_info (CDI_DOMINATORS
);
2532 #endif /* INSN_SCHEDULING */
2535 struct tree_opt_pass pass_sms
=
2538 gate_handle_sms
, /* gate */
2539 rest_of_handle_sms
, /* execute */
2542 0, /* static_pass_number */
2544 0, /* properties_required */
2545 0, /* properties_provided */
2546 0, /* properties_destroyed */
2547 0, /* todo_flags_start */
2549 TODO_ggc_collect
, /* todo_flags_finish */