1 /* Swing Modulo Scheduling implementation.
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, 59 Temple Place - Suite 330, Boston, MA
26 #include "coretypes.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
36 #include "insn-config.h"
37 #include "insn-attr.h"
41 #include "sched-int.h"
43 #include "cfglayout.h"
52 #ifdef INSN_SCHEDULING
54 /* This file contains the implementation of the Swing Modulo Scheduler,
55 described in the following references:
56 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
57 Lifetime--sensitive modulo scheduling in a production environment.
58 IEEE Trans. on Comps., 50(3), March 2001
59 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
60 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
61 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
63 The basic structure is:
64 1. Build a data-dependence graph (DDG) for each loop.
65 2. Use the DDG to order the insns of a loop (not in topological order
66 necessarily, but rather) trying to place each insn after all its
67 predecessors _or_ after all its successors.
68 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
69 4. Use the ordering to perform list-scheduling of the loop:
70 1. Set II = MII. We will try to schedule the loop within II cycles.
71 2. Try to schedule the insns one by one according to the ordering.
72 For each insn compute an interval of cycles by considering already-
73 scheduled preds and succs (and associated latencies); try to place
74 the insn in the cycles of this window checking for potential
75 resource conflicts (using the DFA interface).
76 Note: this is different from the cycle-scheduling of schedule_insns;
77 here the insns are not scheduled monotonically top-down (nor bottom-
79 3. If failed in scheduling all insns - bump II++ and try again, unless
80 II reaches an upper bound MaxII, in which case report failure.
81 5. If we succeeded in scheduling the loop within II cycles, we now
82 generate prolog and epilog, decrease the counter of the loop, and
83 perform modulo variable expansion for live ranges that span more than
84 II cycles (i.e. use register copies to prevent a def from overwriting
85 itself before reaching the use).
89 /* This page defines partial-schedule structures and functions for
92 typedef struct partial_schedule
*partial_schedule_ptr
;
93 typedef struct ps_insn
*ps_insn_ptr
;
95 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
96 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
98 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
99 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
101 /* Perform signed modulo, always returning a non-negative value. */
102 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
104 /* The number of different iterations the nodes in ps span, assuming
105 the stage boundaries are placed efficiently. */
106 #define PS_STAGE_COUNT(ps) ((PS_MAX_CYCLE (ps) - PS_MIN_CYCLE (ps) \
107 + 1 + (ps)->ii - 1) / (ps)->ii)
109 #define CFG_HOOKS cfg_layout_rtl_cfg_hooks
111 /* A single instruction in the partial schedule. */
114 /* The corresponding DDG_NODE. */
117 /* The (absolute) cycle in which the PS instruction is scheduled.
118 Same as SCHED_TIME (node). */
121 /* The next/prev PS_INSN in the same row. */
122 ps_insn_ptr next_in_row
,
125 /* The number of nodes in the same row that come after this node. */
129 /* Holds the partial schedule as an array of II rows. Each entry of the
130 array points to a linked list of PS_INSNs, which represents the
131 instructions that are scheduled for that row. */
132 struct partial_schedule
134 int ii
; /* Number of rows in the partial schedule. */
135 int history
; /* Threshold for conflict checking using DFA. */
137 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
140 /* The earliest absolute cycle of an insn in the partial schedule. */
143 /* The latest absolute cycle of an insn in the partial schedule. */
146 ddg_ptr g
; /* The DDG of the insns in the partial schedule. */
150 partial_schedule_ptr
create_partial_schedule (int ii
, ddg_ptr
, int history
);
151 void free_partial_schedule (partial_schedule_ptr
);
152 void reset_partial_schedule (partial_schedule_ptr
, int new_ii
);
153 void print_partial_schedule (partial_schedule_ptr
, FILE *);
154 ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr
,
155 ddg_node_ptr node
, int cycle
);
156 void rotate_partial_schedule (partial_schedule_ptr
, int);
157 void set_row_column_for_ps (partial_schedule_ptr
);
160 /* This page defines constants and structures for the modulo scheduling
163 /* As in haifa-sched.c: */
164 /* issue_rate is the number of insns that can be scheduled in the same
165 machine cycle. It can be defined in the config/mach/mach.h file,
166 otherwise we set it to 1. */
168 static int issue_rate
;
170 /* For printing statistics. */
171 static FILE *stats_file
;
173 static int sms_order_nodes (ddg_ptr
, int, int * result
);
174 static void set_node_sched_params (ddg_ptr
);
175 static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr
, int, int,
177 static void permute_partial_schedule (partial_schedule_ptr ps
, rtx last
);
178 static void generate_prolog_epilog (partial_schedule_ptr
, rtx
, rtx
, int);
179 static void duplicate_insns_of_cycles (partial_schedule_ptr ps
,
180 int from_stage
, int to_stage
,
184 #define SCHED_ASAP(x) (((node_sched_params_ptr)(x)->aux.info)->asap)
185 #define SCHED_TIME(x) (((node_sched_params_ptr)(x)->aux.info)->time)
186 #define SCHED_FIRST_REG_MOVE(x) \
187 (((node_sched_params_ptr)(x)->aux.info)->first_reg_move)
188 #define SCHED_NREG_MOVES(x) \
189 (((node_sched_params_ptr)(x)->aux.info)->nreg_moves)
190 #define SCHED_ROW(x) (((node_sched_params_ptr)(x)->aux.info)->row)
191 #define SCHED_STAGE(x) (((node_sched_params_ptr)(x)->aux.info)->stage)
192 #define SCHED_COLUMN(x) (((node_sched_params_ptr)(x)->aux.info)->column)
194 /* The scheduling parameters held for each node. */
195 typedef struct node_sched_params
197 int asap
; /* A lower-bound on the absolute scheduling cycle. */
198 int time
; /* The absolute scheduling cycle (time >= asap). */
200 /* The following field (first_reg_move) is a pointer to the first
201 register-move instruction added to handle the modulo-variable-expansion
202 of the register defined by this node. This register-move copies the
203 original register defined by the node. */
206 /* The number of register-move instructions added, immediately preceding
210 int row
; /* Holds time % ii. */
211 int stage
; /* Holds time / ii. */
213 /* The column of a node inside the ps. If nodes u, v are on the same row,
214 u will precede v if column (u) < column (v). */
216 } *node_sched_params_ptr
;
219 /* The following three functions are copied from the current scheduler
220 code in order to use sched_analyze() for computing the dependencies.
221 They are used when initializing the sched_info structure. */
223 sms_print_insn (rtx insn
, int aligned ATTRIBUTE_UNUSED
)
227 sprintf (tmp
, "i%4d", INSN_UID (insn
));
232 contributes_to_priority (rtx next
, rtx insn
)
234 return BLOCK_NUM (next
) == BLOCK_NUM (insn
);
238 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
239 regset cond_exec ATTRIBUTE_UNUSED
,
240 regset used ATTRIBUTE_UNUSED
,
241 regset set ATTRIBUTE_UNUSED
)
245 static struct sched_info sms_sched_info
=
253 contributes_to_priority
,
254 compute_jump_reg_dependencies
,
261 /* Return the register decremented and tested or zero if it is not a decrement
262 and branch jump insn (similar to doloop_condition_get). */
264 doloop_register_get (rtx insn
, rtx
*comp
)
266 rtx pattern
, cmp
, inc
, reg
, condition
;
268 if (GET_CODE (insn
) != JUMP_INSN
)
270 pattern
= PATTERN (insn
);
272 /* The canonical doloop pattern we expect is:
274 (parallel [(set (pc) (if_then_else (condition)
277 (set (reg) (plus (reg) (const_int -1)))
278 (additional clobbers and uses)])
280 where condition is further restricted to be
281 (ne (reg) (const_int 1)). */
283 if (GET_CODE (pattern
) != PARALLEL
)
286 cmp
= XVECEXP (pattern
, 0, 0);
287 inc
= XVECEXP (pattern
, 0, 1);
288 /* Return the compare rtx. */
291 /* Check for (set (reg) (something)). */
292 if (GET_CODE (inc
) != SET
|| ! REG_P (SET_DEST (inc
)))
295 /* Extract loop counter register. */
296 reg
= SET_DEST (inc
);
298 /* Check if something = (plus (reg) (const_int -1)). */
299 if (GET_CODE (SET_SRC (inc
)) != PLUS
300 || XEXP (SET_SRC (inc
), 0) != reg
301 || XEXP (SET_SRC (inc
), 1) != constm1_rtx
)
304 /* Check for (set (pc) (if_then_else (condition)
307 if (GET_CODE (cmp
) != SET
308 || SET_DEST (cmp
) != pc_rtx
309 || GET_CODE (SET_SRC (cmp
)) != IF_THEN_ELSE
310 || GET_CODE (XEXP (SET_SRC (cmp
), 1)) != LABEL_REF
311 || XEXP (SET_SRC (cmp
), 2) != pc_rtx
)
314 /* Extract loop termination condition. */
315 condition
= XEXP (SET_SRC (cmp
), 0);
317 /* Check if condition = (ne (reg) (const_int 1)), which is more
318 restrictive than the check in doloop_condition_get:
319 if ((GET_CODE (condition) != GE && GET_CODE (condition) != NE)
320 || GET_CODE (XEXP (condition, 1)) != CONST_INT). */
321 if (GET_CODE (condition
) != NE
322 || XEXP (condition
, 1) != const1_rtx
)
325 if (XEXP (condition
, 0) == reg
)
331 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
332 that the number of iterations is a compile-time constant. If so,
333 return the rtx that sets COUNT_REG to a constant, and set COUNT to
334 this constant. Otherwise return 0. */
336 const_iteration_count (rtx count_reg
, basic_block pre_header
,
337 HOST_WIDEST_INT
* count
)
341 get_block_head_tail (pre_header
->index
, &head
, &tail
);
343 for (insn
= tail
; insn
!= PREV_INSN (head
); insn
= PREV_INSN (insn
))
344 if (INSN_P (insn
) && single_set (insn
) &&
345 rtx_equal_p (count_reg
, SET_DEST (single_set (insn
))))
347 rtx pat
= single_set (insn
);
349 if (GET_CODE (SET_SRC (pat
)) == CONST_INT
)
351 *count
= INTVAL (SET_SRC (pat
));
361 /* A very simple resource-based lower bound on the initiation interval.
362 ??? Improve the accuracy of this bound by considering the
363 utilization of various units. */
367 return (g
->num_nodes
/ issue_rate
);
371 /* Points to the array that contains the sched data for each node. */
372 static node_sched_params_ptr node_sched_params
;
374 /* Allocate sched_params for each node and initialize it. Assumes that
375 the aux field of each node contain the asap bound (computed earlier),
376 and copies it into the sched_params field. */
378 set_node_sched_params (ddg_ptr g
)
382 /* Allocate for each node in the DDG a place to hold the "sched_data". */
383 /* Initialize ASAP/ALAP/HIGHT to zero. */
384 node_sched_params
= (node_sched_params_ptr
)
385 xcalloc (g
->num_nodes
,
386 sizeof (struct node_sched_params
));
388 /* Set the pointer of the general data of the node to point to the
389 appropriate sched_params structure. */
390 for (i
= 0; i
< g
->num_nodes
; i
++)
392 /* Watch out for aliasing problems? */
393 node_sched_params
[i
].asap
= g
->nodes
[i
].aux
.count
;
394 g
->nodes
[i
].aux
.info
= &node_sched_params
[i
];
399 print_node_sched_params (FILE * dump_file
, int num_nodes
)
403 for (i
= 0; i
< num_nodes
; i
++)
405 node_sched_params_ptr nsp
= &node_sched_params
[i
];
406 rtx reg_move
= nsp
->first_reg_move
;
409 fprintf (dump_file
, "Node %d:\n", i
);
410 fprintf (dump_file
, " asap = %d:\n", nsp
->asap
);
411 fprintf (dump_file
, " time = %d:\n", nsp
->time
);
412 fprintf (dump_file
, " nreg_moves = %d:\n", nsp
->nreg_moves
);
413 for (j
= 0; j
< nsp
->nreg_moves
; j
++)
415 fprintf (dump_file
, " reg_move = ");
416 print_rtl_single (dump_file
, reg_move
);
417 reg_move
= PREV_INSN (reg_move
);
422 /* Calculate an upper bound for II. SMS should not schedule the loop if it
423 requires more cycles than this bound. Currently set to the sum of the
424 longest latency edge for each node. Reset based on experiments. */
426 calculate_maxii (ddg_ptr g
)
431 for (i
= 0; i
< g
->num_nodes
; i
++)
433 ddg_node_ptr u
= &g
->nodes
[i
];
435 int max_edge_latency
= 0;
437 for (e
= u
->out
; e
; e
= e
->next_out
)
438 max_edge_latency
= MAX (max_edge_latency
, e
->latency
);
440 maxii
+= max_edge_latency
;
446 /* Given the partial schedule, generate register moves when the length
447 of the register live range is more than ii; the number of moves is
448 determined according to the following equation:
449 SCHED_TIME (use) - SCHED_TIME (def) { 1 broken loop-carried
450 nreg_moves = ----------------------------------- - { dependence.
452 This handles the modulo-variable-expansions (mve's) needed for the ps. */
454 generate_reg_moves (partial_schedule_ptr ps
)
460 for (i
= 0; i
< g
->num_nodes
; i
++)
462 ddg_node_ptr u
= &g
->nodes
[i
];
464 int nreg_moves
= 0, i_reg_move
;
465 sbitmap
*uses_of_defs
;
467 rtx prev_reg
, old_reg
;
469 /* Compute the number of reg_moves needed for u, by looking at life
470 ranges started at u (excluding self-loops). */
471 for (e
= u
->out
; e
; e
= e
->next_out
)
472 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
474 int nreg_moves4e
= (SCHED_TIME (e
->dest
) - SCHED_TIME (e
->src
)) / ii
;
476 /* If dest precedes src in the schedule of the kernel, then dest
477 will read before src writes and we can save one reg_copy. */
478 if (SCHED_ROW (e
->dest
) == SCHED_ROW (e
->src
)
479 && SCHED_COLUMN (e
->dest
) < SCHED_COLUMN (e
->src
))
482 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
488 /* Every use of the register defined by node may require a different
489 copy of this register, depending on the time the use is scheduled.
490 Set a bitmap vector, telling which nodes use each copy of this
492 uses_of_defs
= sbitmap_vector_alloc (nreg_moves
, g
->num_nodes
);
493 sbitmap_vector_zero (uses_of_defs
, nreg_moves
);
494 for (e
= u
->out
; e
; e
= e
->next_out
)
495 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
497 int dest_copy
= (SCHED_TIME (e
->dest
) - SCHED_TIME (e
->src
)) / ii
;
499 if (SCHED_ROW (e
->dest
) == SCHED_ROW (e
->src
)
500 && SCHED_COLUMN (e
->dest
) < SCHED_COLUMN (e
->src
))
504 SET_BIT (uses_of_defs
[dest_copy
- 1], e
->dest
->cuid
);
507 /* Now generate the reg_moves, attaching relevant uses to them. */
508 SCHED_NREG_MOVES (u
) = nreg_moves
;
509 old_reg
= prev_reg
= copy_rtx (SET_DEST (single_set (u
->insn
)));
510 last_reg_move
= u
->insn
;
512 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
515 rtx new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
516 rtx reg_move
= gen_move_insn (new_reg
, prev_reg
);
518 add_insn_before (reg_move
, last_reg_move
);
519 last_reg_move
= reg_move
;
521 if (!SCHED_FIRST_REG_MOVE (u
))
522 SCHED_FIRST_REG_MOVE (u
) = reg_move
;
524 EXECUTE_IF_SET_IN_SBITMAP (uses_of_defs
[i_reg_move
], 0, i_use
,
525 replace_rtx (g
->nodes
[i_use
].insn
, old_reg
, new_reg
));
532 /* Bump the SCHED_TIMEs of all nodes to start from zero. Set the values
533 of SCHED_ROW and SCHED_STAGE. */
535 normalize_sched_times (partial_schedule_ptr ps
)
539 int amount
= PS_MIN_CYCLE (ps
);
542 for (i
= 0; i
< g
->num_nodes
; i
++)
544 ddg_node_ptr u
= &g
->nodes
[i
];
545 int normalized_time
= SCHED_TIME (u
) - amount
;
547 if (normalized_time
< 0)
550 SCHED_TIME (u
) = normalized_time
;
551 SCHED_ROW (u
) = normalized_time
% ii
;
552 SCHED_STAGE (u
) = normalized_time
/ ii
;
556 /* Set SCHED_COLUMN of each node according to its position in PS. */
558 set_columns_for_ps (partial_schedule_ptr ps
)
562 for (row
= 0; row
< ps
->ii
; row
++)
564 ps_insn_ptr cur_insn
= ps
->rows
[row
];
567 for (; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
568 SCHED_COLUMN (cur_insn
->node
) = column
++;
572 /* Permute the insns according to their order in PS, from row 0 to
573 row ii-1, and position them right before LAST. This schedules
574 the insns of the loop kernel. */
576 permute_partial_schedule (partial_schedule_ptr ps
, rtx last
)
582 for (row
= 0; row
< ii
; row
++)
583 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
584 if (PREV_INSN (last
) != ps_ij
->node
->insn
)
585 reorder_insns_nobb (ps_ij
->node
->first_note
, ps_ij
->node
->insn
,
589 /* Used to generate the prologue & epilogue. Duplicate the subset of
590 nodes whose stages are between FROM_STAGE and TO_STAGE (inclusive
591 of both), together with a prefix/suffix of their reg_moves. */
593 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
594 int to_stage
, int for_prolog
)
599 for (row
= 0; row
< ps
->ii
; row
++)
600 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
602 ddg_node_ptr u_node
= ps_ij
->node
;
604 rtx reg_move
= NULL_RTX
;
608 /* SCHED_STAGE (u_node) >= from_stage == 0. Generate increasing
609 number of reg_moves starting with the second occurrence of
610 u_node, which is generated if its SCHED_STAGE <= to_stage. */
611 i_reg_moves
= to_stage
- SCHED_STAGE (u_node
);
612 i_reg_moves
= MAX (i_reg_moves
, 0);
613 i_reg_moves
= MIN (i_reg_moves
, SCHED_NREG_MOVES (u_node
));
615 /* The reg_moves start from the *first* reg_move backwards. */
618 reg_move
= SCHED_FIRST_REG_MOVE (u_node
);
619 for (j
= 1; j
< i_reg_moves
; j
++)
620 reg_move
= PREV_INSN (reg_move
);
623 else /* It's for the epilog. */
625 /* SCHED_STAGE (u_node) <= to_stage. Generate all reg_moves,
626 starting to decrease one stage after u_node no longer occurs;
627 that is, generate all reg_moves until
628 SCHED_STAGE (u_node) == from_stage - 1. */
629 i_reg_moves
= SCHED_NREG_MOVES (u_node
)
630 - (from_stage
- SCHED_STAGE (u_node
) - 1);
631 i_reg_moves
= MAX (i_reg_moves
, 0);
632 i_reg_moves
= MIN (i_reg_moves
, SCHED_NREG_MOVES (u_node
));
634 /* The reg_moves start from the *last* reg_move forwards. */
637 reg_move
= SCHED_FIRST_REG_MOVE (u_node
);
638 for (j
= 1; j
< SCHED_NREG_MOVES (u_node
); j
++)
639 reg_move
= PREV_INSN (reg_move
);
643 for (j
= 0; j
< i_reg_moves
; j
++, reg_move
= NEXT_INSN (reg_move
))
644 emit_insn (copy_rtx (PATTERN (reg_move
)));
646 if (SCHED_STAGE (u_node
) >= from_stage
647 && SCHED_STAGE (u_node
) <= to_stage
)
648 duplicate_insn_chain (u_node
->first_note
, u_node
->insn
);
653 /* Generate the instructions (including reg_moves) for prolog & epilog. */
655 generate_prolog_epilog (partial_schedule_ptr ps
, rtx orig_loop_beg
,
656 rtx orig_loop_end
, int unknown_count
)
659 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
661 rtx c_reg
= NULL_RTX
;
663 rtx precond_jump
= NULL_RTX
;
664 rtx precond_exit_label
= NULL_RTX
;
665 rtx precond_exit_label_insn
= NULL_RTX
;
666 rtx last_epilog_insn
= NULL_RTX
;
667 rtx loop_exit_label
= NULL_RTX
;
668 rtx loop_exit_label_insn
= NULL_RTX
;
669 rtx orig_loop_bct
= NULL_RTX
;
671 /* Loop header edge. */
673 if (e
->src
== ps
->g
->bb
)
676 /* Generate the prolog, inserting its insns on the loop-entry edge. */
679 /* This is the place where we want to insert the precondition. */
681 precond_jump
= emit_note (NOTE_INSN_DELETED
);
683 for (i
= 0; i
< last_stage
; i
++)
684 duplicate_insns_of_cycles (ps
, 0, i
, 1);
686 /* No need to call insert_insn_on_edge; we prepared the sequence. */
687 e
->insns
.r
= get_insns ();
690 /* Generate the epilog, inserting its insns on the loop-exit edge. */
693 for (i
= 0; i
< last_stage
; i
++)
694 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, 0);
696 last_epilog_insn
= emit_note (NOTE_INSN_DELETED
);
698 /* Emit the label where to put the original loop code. */
703 precond_exit_label
= gen_label_rtx ();
704 precond_exit_label_insn
= emit_label (precond_exit_label
);
706 /* Put the original loop code. */
707 reorder_insns_nobb (orig_loop_beg
, orig_loop_end
, precond_exit_label_insn
);
709 /* Change the label of the BCT to be the PRECOND_EXIT_LABEL. */
710 orig_loop_bct
= get_last_insn ();
711 c_reg
= doloop_register_get (orig_loop_bct
, &cmp
);
712 label
= XEXP (SET_SRC (cmp
), 1);
713 cond
= XEXP (SET_SRC (cmp
), 0);
715 if (! c_reg
|| GET_CODE (cond
) != NE
)
718 XEXP (label
, 0) = precond_exit_label
;
719 JUMP_LABEL (orig_loop_bct
) = precond_exit_label_insn
;
720 LABEL_NUSES (precond_exit_label_insn
)++;
722 /* Generate the loop exit label. */
723 loop_exit_label
= gen_label_rtx ();
724 loop_exit_label_insn
= emit_label (loop_exit_label
);
728 if (e
->dest
== ps
->g
->bb
)
731 e
->insns
.r
= get_insns ();
734 commit_edge_insertions ();
738 rtx precond_insns
, epilog_jump
, insert_after_insn
;
739 basic_block loop_exit_bb
= BLOCK_FOR_INSN (loop_exit_label_insn
);
740 basic_block epilog_bb
= BLOCK_FOR_INSN (last_epilog_insn
);
741 basic_block precond_bb
= BLOCK_FOR_INSN (precond_jump
);
742 basic_block orig_loop_bb
= BLOCK_FOR_INSN (precond_exit_label_insn
);
743 edge epilog_exit_edge
= epilog_bb
->succ
;
745 /* Do loop preconditioning to take care of cases were the loop count is
746 less than the stage count. Update the CFG properly. */
747 insert_after_insn
= precond_jump
;
749 c_reg
= doloop_register_get (ps
->g
->closing_branch
->insn
, &cmp
);
750 emit_cmp_and_jump_insns (c_reg
, GEN_INT (PS_STAGE_COUNT (ps
)), LT
, NULL
,
751 GET_MODE (c_reg
), 1, precond_exit_label
);
752 precond_insns
= get_insns ();
753 precond_jump
= get_last_insn ();
755 reorder_insns (precond_insns
, precond_jump
, insert_after_insn
);
757 /* Generate a subtract instruction at the beginning of the prolog to
758 adjust the loop count by STAGE_COUNT. */
759 emit_insn_after (gen_sub2_insn (c_reg
, GEN_INT (PS_STAGE_COUNT (ps
) - 1)),
761 update_bb_for_insn (precond_bb
);
762 delete_insn (insert_after_insn
);
764 /* Update label info for the precondition jump. */
765 JUMP_LABEL (precond_jump
) = precond_exit_label_insn
;
766 LABEL_NUSES (precond_exit_label_insn
)++;
768 /* Update the CFG. */
769 split_block (precond_bb
, precond_jump
);
770 make_edge (precond_bb
, orig_loop_bb
, 0);
772 /* Add a jump at end of the epilog to the LOOP_EXIT_LABEL to jump over the
773 original loop copy and update the CFG. */
774 epilog_jump
= emit_jump_insn_after (gen_jump (loop_exit_label
),
776 delete_insn (last_epilog_insn
);
777 JUMP_LABEL (epilog_jump
) = loop_exit_label_insn
;
778 LABEL_NUSES (loop_exit_label_insn
)++;
780 redirect_edge_succ (epilog_exit_edge
, loop_exit_bb
);
781 epilog_exit_edge
->flags
&= ~EDGE_FALLTHRU
;
782 emit_barrier_after (BB_END (epilog_bb
));
786 /* Return the line note insn preceding INSN, for debugging. Taken from
789 find_line_note (rtx insn
)
791 for (; insn
; insn
= PREV_INSN (insn
))
792 if (GET_CODE (insn
) == NOTE
793 && NOTE_LINE_NUMBER (insn
) >= 0)
799 /* Main entry point, perform SMS scheduling on the loops of the function
800 that consist of single basic blocks. */
802 sms_schedule (FILE *dump_file
)
804 static int passes
= 0;
807 basic_block bb
, pre_header
= NULL
;
811 partial_schedule_ptr ps
;
812 int max_bb_index
= last_basic_block
;
815 /* SMS uses the DFA interface. */
816 if (! targetm
.sched
.use_dfa_pipeline_interface
817 || ! (*targetm
.sched
.use_dfa_pipeline_interface
) ())
820 stats_file
= dump_file
;
823 /* Initialize issue_rate. */
824 if (targetm
.sched
.issue_rate
)
826 int temp
= reload_completed
;
828 reload_completed
= 1;
829 issue_rate
= (*targetm
.sched
.issue_rate
) ();
830 reload_completed
= temp
;
835 /* Initialize the scheduler. */
836 current_sched_info
= &sms_sched_info
;
839 /* Init Data Flow analysis, to be used in interloop dep calculation. */
841 df_analyze (df
, 0, DF_ALL
);
843 /* Allocate memory to hold the DDG array. */
844 g_arr
= xcalloc (max_bb_index
, sizeof (ddg_ptr
));
846 /* Build DDGs for all the relevant loops and hold them in G_ARR
847 indexed by the loop BB index. */
852 edge e
, pre_header_edge
;
857 /* Check if bb has two successors, one being itself. */
859 if (!e
|| !e
->succ_next
|| e
->succ_next
->succ_next
)
862 if (e
->dest
!= bb
&& e
->succ_next
->dest
!= bb
)
865 if ((e
->flags
& EDGE_COMPLEX
)
866 || (e
->succ_next
->flags
& EDGE_COMPLEX
))
869 /* Check if bb has two predecessors, one being itself. */
870 /* In view of above tests, suffices to check e->pred_next->pred_next? */
872 if (!e
|| !e
->pred_next
|| e
->pred_next
->pred_next
)
875 if (e
->src
!= bb
&& e
->pred_next
->src
!= bb
)
878 if ((e
->flags
& EDGE_COMPLEX
)
879 || (e
->pred_next
->flags
& EDGE_COMPLEX
))
883 if (passes
++ > MAX_SMS_LOOP_NUMBER
&& MAX_SMS_LOOP_NUMBER
!= -1)
886 fprintf (dump_file
, "SMS reached MAX_PASSES... \n");
890 get_block_head_tail (bb
->index
, &head
, &tail
);
891 pre_header_edge
= bb
->pred
;
892 if (bb
->pred
->src
!= bb
)
893 pre_header_edge
= bb
->pred
->pred_next
;
895 /* Perfrom SMS only on loops that their average count is above threshold. */
896 if (bb
->count
< pre_header_edge
->count
* SMS_LOOP_AVERAGE_COUNT_THRESHOLD
)
900 rtx line_note
= find_line_note (tail
);
904 expanded_location xloc
;
905 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
906 fprintf (stats_file
, "SMS bb %s %d (file, line)\n",
907 xloc
.file
, xloc
.line
);
909 fprintf (stats_file
, "SMS single-bb-loop\n");
910 if (profile_info
&& flag_branch_probabilities
)
912 fprintf (stats_file
, "SMS loop-count ");
913 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
914 (HOST_WIDEST_INT
) bb
->count
);
915 fprintf (stats_file
, "\n");
916 fprintf (stats_file
, "SMS preheader-count ");
917 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
918 (HOST_WIDEST_INT
) pre_header_edge
->count
);
919 fprintf (stats_file
, "\n");
920 fprintf (stats_file
, "SMS profile-sum-max ");
921 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
922 (HOST_WIDEST_INT
) profile_info
->sum_max
);
923 fprintf (stats_file
, "\n");
929 /* Make sure this is a doloop. */
930 if ( !(count_reg
= doloop_register_get (tail
, &comp
)))
935 pre_header
= e
->pred_next
->src
;
939 /* Don't handle BBs with calls or barriers, or !single_set insns. */
940 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
941 if (GET_CODE (insn
) == CALL_INSN
942 || GET_CODE (insn
) == BARRIER
943 || (INSN_P (insn
) && GET_CODE (insn
) != JUMP_INSN
944 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
947 if (insn
!= NEXT_INSN (tail
))
951 if (GET_CODE (insn
) == CALL_INSN
)
952 fprintf (stats_file
, "SMS loop-with-call\n");
953 else if (GET_CODE (insn
) == BARRIER
)
954 fprintf (stats_file
, "SMS loop-with-barrier\n");
956 fprintf (stats_file
, "SMS loop-with-not-single-set\n");
957 print_rtl_single (stats_file
, insn
);
963 if (! (g
= create_ddg (bb
, df
, 0)))
966 fprintf (stats_file
, "SMS doloop\n");
970 g_arr
[bb
->index
] = g
;
973 /* Release Data Flow analysis data structures. */
976 /* Go over the built DDGs and perfrom SMS for each one of them. */
977 for (i
= 0; i
< max_bb_index
; i
++)
980 rtx count_reg
, count_init
, comp
;
981 edge pre_header_edge
;
984 HOST_WIDEST_INT loop_count
= 0;
986 if (! (g
= g_arr
[i
]))
990 print_ddg (dump_file
, g
);
992 get_block_head_tail (g
->bb
->index
, &head
, &tail
);
994 pre_header_edge
= g
->bb
->pred
;
995 if (g
->bb
->pred
->src
!= g
->bb
)
996 pre_header_edge
= g
->bb
->pred
->pred_next
;
1000 rtx line_note
= find_line_note (tail
);
1004 expanded_location xloc
;
1005 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
1006 fprintf (stats_file
, "SMS bb %s %d (file, line)\n",
1007 xloc
.file
, xloc
.line
);
1009 fprintf (stats_file
, "SMS single-bb-loop\n");
1010 if (profile_info
&& flag_branch_probabilities
)
1012 fprintf (stats_file
, "SMS loop-count ");
1013 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1014 (HOST_WIDEST_INT
) bb
->count
);
1015 fprintf (stats_file
, "\n");
1016 fprintf (stats_file
, "SMS preheader-count ");
1017 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1018 (HOST_WIDEST_INT
) pre_header_edge
->count
);
1019 fprintf (stats_file
, "\n");
1020 fprintf (stats_file
, "SMS profile-sum-max ");
1021 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1022 (HOST_WIDEST_INT
) profile_info
->sum_max
);
1023 fprintf (stats_file
, "\n");
1025 fprintf (stats_file
, "SMS doloop\n");
1026 fprintf (stats_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1027 fprintf (stats_file
, "SMS num-loads %d\n", g
->num_loads
);
1028 fprintf (stats_file
, "SMS num-stores %d\n", g
->num_stores
);
1031 /* Make sure this is a doloop. */
1032 if ( !(count_reg
= doloop_register_get (tail
, &comp
)))
1035 /* This should be NULL_RTX if the count is unknown at compile time. */
1036 count_init
= const_iteration_count (count_reg
, pre_header
, &loop_count
);
1038 if (stats_file
&& count_init
)
1040 fprintf (stats_file
, "SMS const-doloop ");
1041 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
, loop_count
);
1042 fprintf (stats_file
, "\n");
1045 node_order
= (int *) xmalloc (sizeof (int) * g
->num_nodes
);
1047 mii
= 1; /* Need to pass some estimate of mii. */
1048 rec_mii
= sms_order_nodes (g
, mii
, node_order
);
1049 mii
= MAX (res_MII (g
), rec_mii
);
1050 maxii
= (calculate_maxii (g
) * SMS_MAX_II_FACTOR
) / 100;
1053 fprintf (stats_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1054 rec_mii
, mii
, maxii
);
1056 /* After sms_order_nodes and before sms_schedule_by_order, to copy over
1058 set_node_sched_params (g
);
1060 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
, dump_file
);
1063 stage_count
= PS_STAGE_COUNT (ps
);
1065 if (stage_count
== 0 || (count_init
&& (stage_count
> loop_count
)))
1068 fprintf (dump_file
, "SMS failed... \n");
1070 fprintf (stats_file
, "SMS sched-failed %d\n", stage_count
);
1074 rtx orig_loop_beg
= NULL_RTX
;
1075 rtx orig_loop_end
= NULL_RTX
;
1079 fprintf (stats_file
,
1080 "SMS succeeded %d %d (with ii, sc)\n", ps
->ii
,
1082 print_partial_schedule (ps
, dump_file
);
1084 "SMS Branch (%d) will later be scheduled at cycle %d.\n",
1085 g
->closing_branch
->cuid
, PS_MIN_CYCLE (ps
) - 1);
1088 /* Save the original loop if we want to do loop preconditioning in
1089 case the BCT count is not known. */
1095 /* Copy the original loop code before modifying it - so we can use
1097 for (i
= 0; i
< ps
->g
->num_nodes
; i
++)
1098 duplicate_insn_chain (ps
->g
->nodes
[i
].first_note
,
1099 ps
->g
->nodes
[i
].insn
);
1101 orig_loop_beg
= get_insns ();
1102 orig_loop_end
= get_last_insn ();
1105 /* Set the stage boundaries. If the DDG is built with closing_branch_deps,
1106 the closing_branch was scheduled and should appear in the last (ii-1)
1107 row. Otherwise, we are free to schedule the branch, and we let nodes
1108 that were scheduled at the first PS_MIN_CYCLE cycle appear in the first
1109 row; this should reduce stage_count to minimum. */
1110 normalize_sched_times (ps
);
1111 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
1112 set_columns_for_ps (ps
);
1114 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1115 generate_reg_moves (ps
);
1117 print_node_sched_params (dump_file
, g
->num_nodes
);
1119 /* Set new iteration count of loop kernel. */
1121 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1124 /* Generate prolog and epilog. */
1125 generate_prolog_epilog (ps
, orig_loop_beg
, orig_loop_end
,
1126 count_init
? 0 : 1);
1128 free_partial_schedule (ps
);
1129 free (node_sched_params
);
1134 /* Release scheduler data, needed until now because of DFA. */
1138 /* The SMS scheduling algorithm itself
1139 -----------------------------------
1140 Input: 'O' an ordered list of insns of a loop.
1141 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1143 'Q' is the empty Set
1144 'PS' is the partial schedule; it holds the currently scheduled nodes with
1146 'PSP' previously scheduled predecessors.
1147 'PSS' previously scheduled successors.
1148 't(u)' the cycle where u is scheduled.
1149 'l(u)' is the latency of u.
1150 'd(v,u)' is the dependence distance from v to u.
1151 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1152 the node ordering phase.
1153 'check_hardware_resources_conflicts(u, PS, c)'
1154 run a trace around cycle/slot through DFA model
1155 to check resource conflicts involving instruction u
1156 at cycle c given the partial schedule PS.
1157 'add_to_partial_schedule_at_time(u, PS, c)'
1158 Add the node/instruction u to the partial schedule
1160 'calculate_register_pressure(PS)'
1161 Given a schedule of instructions, calculate the register
1162 pressure it implies. One implementation could be the
1163 maximum number of overlapping live ranges.
1164 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1165 registers available in the hardware.
1169 3. for each node u in O in pre-computed order
1170 4. if (PSP(u) != Q && PSS(u) == Q) then
1171 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1172 6. start = Early_start; end = Early_start + II - 1; step = 1
1173 11. else if (PSP(u) == Q && PSS(u) != Q) then
1174 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1175 13. start = Late_start; end = Late_start - II + 1; step = -1
1176 14. else if (PSP(u) != Q && PSS(u) != Q) then
1177 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1178 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1179 17. start = Early_start;
1180 18. end = min(Early_start + II - 1 , Late_start);
1182 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1183 21. start = ASAP(u); end = start + II - 1; step = 1
1187 24. for (c = start ; c != end ; c += step)
1188 25. if check_hardware_resources_conflicts(u, PS, c) then
1189 26. add_to_partial_schedule_at_time(u, PS, c)
1194 31. if (success == false) then
1196 33. if (II > maxII) then
1197 34. finish - failed to schedule
1202 39. if (calculate_register_pressure(PS) > maxRP) then
1205 42. compute epilogue & prologue
1206 43. finish - succeeded to schedule
1209 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1210 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1211 set to 0 to save compile time. */
1212 #define DFA_HISTORY SMS_DFA_HISTORY
1214 static partial_schedule_ptr
1215 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
, FILE *dump_file
)
1219 int try_again_with_larger_ii
= true;
1220 int num_nodes
= g
->num_nodes
;
1222 int start
, end
, step
; /* Place together into one struct? */
1223 sbitmap sched_nodes
= sbitmap_alloc (num_nodes
);
1224 sbitmap psp
= sbitmap_alloc (num_nodes
);
1225 sbitmap pss
= sbitmap_alloc (num_nodes
);
1226 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
, DFA_HISTORY
);
1228 while (try_again_with_larger_ii
&& ii
< maxii
)
1231 fprintf(dump_file
, "Starting with ii=%d\n", ii
);
1232 try_again_with_larger_ii
= false;
1233 sbitmap_zero (sched_nodes
);
1235 for (i
= 0; i
< num_nodes
; i
++)
1237 int u
= nodes_order
[i
];
1238 ddg_node_ptr u_node
= &g
->nodes
[u
];
1239 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1240 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1243 rtx insn
= u_node
->insn
;
1248 if (GET_CODE (insn
) == JUMP_INSN
) /* Closing branch handled later. */
1251 /* 1. compute sched window for u (start, end, step). */
1254 psp_not_empty
= sbitmap_a_and_b_cg (psp
, u_node_preds
, sched_nodes
);
1255 pss_not_empty
= sbitmap_a_and_b_cg (pss
, u_node_succs
, sched_nodes
);
1257 if (psp_not_empty
&& !pss_not_empty
)
1259 int early_start
= 0;
1262 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1264 ddg_node_ptr v_node
= e
->src
;
1265 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1267 early_start
= MAX (early_start
,
1269 + e
->latency
- (e
->distance
* ii
));
1270 if (e
->data_type
== MEM_DEP
)
1271 end
= MIN (end
, SCHED_TIME (v_node
) + ii
- 1);
1274 start
= early_start
;
1275 end
= MIN (end
, early_start
+ ii
);
1279 else if (!psp_not_empty
&& pss_not_empty
)
1281 int late_start
= INT_MAX
;
1284 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1286 ddg_node_ptr v_node
= e
->dest
;
1287 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1289 late_start
= MIN (late_start
,
1290 SCHED_TIME (v_node
) - e
->latency
1291 + (e
->distance
* ii
));
1292 if (e
->data_type
== MEM_DEP
)
1293 end
= MAX (end
, SCHED_TIME (v_node
) - ii
+ 1);
1297 end
= MAX (end
, late_start
- ii
);
1301 else if (psp_not_empty
&& pss_not_empty
)
1303 int early_start
= 0;
1304 int late_start
= INT_MAX
;
1308 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1310 ddg_node_ptr v_node
= e
->src
;
1312 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1314 early_start
= MAX (early_start
,
1315 SCHED_TIME (v_node
) + e
->latency
1316 - (e
->distance
* ii
));
1317 if (e
->data_type
== MEM_DEP
)
1318 end
= MIN (end
, SCHED_TIME (v_node
) + ii
- 1);
1321 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1323 ddg_node_ptr v_node
= e
->dest
;
1325 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1327 late_start
= MIN (late_start
,
1328 SCHED_TIME (v_node
) - e
->latency
1329 + (e
->distance
* ii
));
1330 if (e
->data_type
== MEM_DEP
)
1331 start
= MAX (start
, SCHED_TIME (v_node
) - ii
+ 1);
1334 start
= MAX (start
, early_start
);
1335 end
= MIN (end
, MIN (early_start
+ ii
, late_start
+ 1));
1338 else /* psp is empty && pss is empty. */
1340 start
= SCHED_ASAP (u_node
);
1345 /* 2. Try scheduling u in window. */
1347 fprintf(dump_file
, "Trying to schedule node %d in (%d .. %d) step %d\n",
1348 u
, start
, end
, step
);
1351 if ((step
> 0 && start
< end
) || (step
< 0 && start
> end
))
1352 for (c
= start
; c
!= end
; c
+= step
)
1354 ps_insn_ptr psi
= ps_add_node_check_conflicts (ps
, u_node
, c
);
1358 SCHED_TIME (u_node
) = c
;
1359 SET_BIT (sched_nodes
, u
);
1362 fprintf(dump_file
, "Schedule in %d\n", c
);
1368 /* ??? Try backtracking instead of immediately ii++? */
1370 try_again_with_larger_ii
= true;
1371 reset_partial_schedule (ps
, ii
);
1374 /* ??? If (success), check register pressure estimates. */
1375 } /* Continue with next node. */
1376 } /* While try_again_with_larger_ii. */
1378 sbitmap_free (sched_nodes
);
1384 free_partial_schedule (ps
);
1391 /* This page implements the algorithm for ordering the nodes of a DDG
1392 for modulo scheduling, activated through the
1393 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
1395 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
1396 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
1397 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
1398 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
1399 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
1400 #define DEPTH(x) (ASAP ((x)))
1402 typedef struct node_order_params
* nopa
;
1404 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
1405 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
1406 static nopa
calculate_order_params (ddg_ptr
, int mii
);
1407 static int find_max_asap (ddg_ptr
, sbitmap
);
1408 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
1409 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
1411 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
1413 struct node_order_params
1420 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
1422 check_nodes_order (int *node_order
, int num_nodes
)
1425 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1429 for (i
= 0; i
< num_nodes
; i
++)
1431 int u
= node_order
[i
];
1433 if (u
>= num_nodes
|| u
< 0 || TEST_BIT (tmp
, u
))
1442 /* Order the nodes of G for scheduling and pass the result in
1443 NODE_ORDER. Also set aux.count of each node to ASAP.
1444 Return the recMII for the given DDG. */
1446 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
)
1450 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
1452 nopa nops
= calculate_order_params (g
, mii
);
1454 order_nodes_of_sccs (sccs
, node_order
);
1456 if (sccs
->num_sccs
> 0)
1457 /* First SCC has the largest recurrence_length. */
1458 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
1460 /* Save ASAP before destroying node_order_params. */
1461 for (i
= 0; i
< g
->num_nodes
; i
++)
1463 ddg_node_ptr v
= &g
->nodes
[i
];
1464 v
->aux
.count
= ASAP (v
);
1468 free_ddg_all_sccs (sccs
);
1469 check_nodes_order (node_order
, g
->num_nodes
);
1475 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
1478 ddg_ptr g
= all_sccs
->ddg
;
1479 int num_nodes
= g
->num_nodes
;
1480 sbitmap prev_sccs
= sbitmap_alloc (num_nodes
);
1481 sbitmap on_path
= sbitmap_alloc (num_nodes
);
1482 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1483 sbitmap ones
= sbitmap_alloc (num_nodes
);
1485 sbitmap_zero (prev_sccs
);
1486 sbitmap_ones (ones
);
1488 /* Perfrom the node ordering starting from the SCC with the highest recMII.
1489 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
1490 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
1492 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
1494 /* Add nodes on paths from previous SCCs to the current SCC. */
1495 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
1496 sbitmap_a_or_b (tmp
, scc
->nodes
, on_path
);
1498 /* Add nodes on paths from the current SCC to previous SCCs. */
1499 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
1500 sbitmap_a_or_b (tmp
, tmp
, on_path
);
1502 /* Remove nodes of previous SCCs from current extended SCC. */
1503 sbitmap_difference (tmp
, tmp
, prev_sccs
);
1505 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
1506 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
1509 /* Handle the remaining nodes that do not belong to any scc. Each call
1510 to order_nodes_in_scc handles a single connected component. */
1511 while (pos
< g
->num_nodes
)
1513 sbitmap_difference (tmp
, ones
, prev_sccs
);
1514 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
1516 sbitmap_free (prev_sccs
);
1517 sbitmap_free (on_path
);
1519 sbitmap_free (ones
);
1522 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
1523 static struct node_order_params
*
1524 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
)
1528 int num_nodes
= g
->num_nodes
;
1530 /* Allocate a place to hold ordering params for each node in the DDG. */
1531 nopa node_order_params_arr
;
1533 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
1534 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
1535 sizeof (struct node_order_params
));
1537 /* Set the aux pointer of each node to point to its order_params structure. */
1538 for (u
= 0; u
< num_nodes
; u
++)
1539 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
1541 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
1542 calculate ASAP, ALAP, mobility, distance, and height for each node
1543 in the dependence (direct acyclic) graph. */
1545 /* We assume that the nodes in the array are in topological order. */
1548 for (u
= 0; u
< num_nodes
; u
++)
1550 ddg_node_ptr u_node
= &g
->nodes
[u
];
1553 for (e
= u_node
->in
; e
; e
= e
->next_in
)
1554 if (e
->distance
== 0)
1555 ASAP (u_node
) = MAX (ASAP (u_node
),
1556 ASAP (e
->src
) + e
->latency
);
1557 max_asap
= MAX (max_asap
, ASAP (u_node
));
1560 for (u
= num_nodes
- 1; u
> -1; u
--)
1562 ddg_node_ptr u_node
= &g
->nodes
[u
];
1564 ALAP (u_node
) = max_asap
;
1565 HEIGHT (u_node
) = 0;
1566 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1567 if (e
->distance
== 0)
1569 ALAP (u_node
) = MIN (ALAP (u_node
),
1570 ALAP (e
->dest
) - e
->latency
);
1571 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
1572 HEIGHT (e
->dest
) + e
->latency
);
1576 return node_order_params_arr
;
1580 find_max_asap (ddg_ptr g
, sbitmap nodes
)
1586 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
,
1588 ddg_node_ptr u_node
= &g
->nodes
[u
];
1590 if (max_asap
< ASAP (u_node
))
1592 max_asap
= ASAP (u_node
);
1600 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
1604 int min_mob
= INT_MAX
;
1607 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
,
1609 ddg_node_ptr u_node
= &g
->nodes
[u
];
1611 if (max_hv
< HEIGHT (u_node
))
1613 max_hv
= HEIGHT (u_node
);
1614 min_mob
= MOB (u_node
);
1617 else if ((max_hv
== HEIGHT (u_node
))
1618 && (min_mob
> MOB (u_node
)))
1620 min_mob
= MOB (u_node
);
1628 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
1632 int min_mob
= INT_MAX
;
1635 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
,
1637 ddg_node_ptr u_node
= &g
->nodes
[u
];
1639 if (max_dv
< DEPTH (u_node
))
1641 max_dv
= DEPTH (u_node
);
1642 min_mob
= MOB (u_node
);
1645 else if ((max_dv
== DEPTH (u_node
))
1646 && (min_mob
> MOB (u_node
)))
1648 min_mob
= MOB (u_node
);
1655 /* Places the nodes of SCC into the NODE_ORDER array starting
1656 at position POS, according to the SMS ordering algorithm.
1657 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
1658 the NODE_ORDER array, starting from position zero. */
1660 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
1661 int * node_order
, int pos
)
1663 enum sms_direction dir
;
1664 int num_nodes
= g
->num_nodes
;
1665 sbitmap workset
= sbitmap_alloc (num_nodes
);
1666 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1667 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
1668 sbitmap predecessors
= sbitmap_alloc (num_nodes
);
1669 sbitmap successors
= sbitmap_alloc (num_nodes
);
1671 sbitmap_zero (predecessors
);
1672 find_predecessors (predecessors
, g
, nodes_ordered
);
1674 sbitmap_zero (successors
);
1675 find_successors (successors
, g
, nodes_ordered
);
1678 if (sbitmap_a_and_b_cg (tmp
, predecessors
, scc
))
1680 sbitmap_copy (workset
, tmp
);
1683 else if (sbitmap_a_and_b_cg (tmp
, successors
, scc
))
1685 sbitmap_copy (workset
, tmp
);
1692 sbitmap_zero (workset
);
1693 if ((u
= find_max_asap (g
, scc
)) >= 0)
1694 SET_BIT (workset
, u
);
1698 sbitmap_zero (zero_bitmap
);
1699 while (!sbitmap_equal (workset
, zero_bitmap
))
1702 ddg_node_ptr v_node
;
1703 sbitmap v_node_preds
;
1704 sbitmap v_node_succs
;
1708 while (!sbitmap_equal (workset
, zero_bitmap
))
1710 v
= find_max_hv_min_mob (g
, workset
);
1711 v_node
= &g
->nodes
[v
];
1712 node_order
[pos
++] = v
;
1713 v_node_succs
= NODE_SUCCESSORS (v_node
);
1714 sbitmap_a_and_b (tmp
, v_node_succs
, scc
);
1716 /* Don't consider the already ordered successors again. */
1717 sbitmap_difference (tmp
, tmp
, nodes_ordered
);
1718 sbitmap_a_or_b (workset
, workset
, tmp
);
1719 RESET_BIT (workset
, v
);
1720 SET_BIT (nodes_ordered
, v
);
1723 sbitmap_zero (predecessors
);
1724 find_predecessors (predecessors
, g
, nodes_ordered
);
1725 sbitmap_a_and_b (workset
, predecessors
, scc
);
1729 while (!sbitmap_equal (workset
, zero_bitmap
))
1731 v
= find_max_dv_min_mob (g
, workset
);
1732 v_node
= &g
->nodes
[v
];
1733 node_order
[pos
++] = v
;
1734 v_node_preds
= NODE_PREDECESSORS (v_node
);
1735 sbitmap_a_and_b (tmp
, v_node_preds
, scc
);
1737 /* Don't consider the already ordered predecessors again. */
1738 sbitmap_difference (tmp
, tmp
, nodes_ordered
);
1739 sbitmap_a_or_b (workset
, workset
, tmp
);
1740 RESET_BIT (workset
, v
);
1741 SET_BIT (nodes_ordered
, v
);
1744 sbitmap_zero (successors
);
1745 find_successors (successors
, g
, nodes_ordered
);
1746 sbitmap_a_and_b (workset
, successors
, scc
);
1750 sbitmap_free (workset
);
1751 sbitmap_free (zero_bitmap
);
1752 sbitmap_free (predecessors
);
1753 sbitmap_free (successors
);
1758 /* This page contains functions for manipulating partial-schedules during
1759 modulo scheduling. */
1761 /* Create a partial schedule and allocate a memory to hold II rows. */
1762 partial_schedule_ptr
1763 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
1765 partial_schedule_ptr ps
= (partial_schedule_ptr
)
1766 xmalloc (sizeof (struct partial_schedule
));
1767 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
1769 ps
->history
= history
;
1770 ps
->min_cycle
= INT_MAX
;
1771 ps
->max_cycle
= INT_MIN
;
1777 /* Free the PS_INSNs in rows array of the given partial schedule.
1778 ??? Consider caching the PS_INSN's. */
1780 free_ps_insns (partial_schedule_ptr ps
)
1784 for (i
= 0; i
< ps
->ii
; i
++)
1788 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
1791 ps
->rows
[i
] = ps_insn
;
1797 /* Free all the memory allocated to the partial schedule. */
1799 free_partial_schedule (partial_schedule_ptr ps
)
1808 /* Clear the rows array with its PS_INSNs, and create a new one with
1811 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
1816 if (new_ii
== ps
->ii
)
1818 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
1819 * sizeof (ps_insn_ptr
));
1820 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
1822 ps
->min_cycle
= INT_MAX
;
1823 ps
->max_cycle
= INT_MIN
;
1826 /* Prints the partial schedule as an ii rows array, for each rows
1827 print the ids of the insns in it. */
1829 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
1833 for (i
= 0; i
< ps
->ii
; i
++)
1835 ps_insn_ptr ps_i
= ps
->rows
[i
];
1837 fprintf (dump
, "\n[CYCLE %d ]: ", i
);
1840 fprintf (dump
, "%d, ",
1841 INSN_UID (ps_i
->node
->insn
));
1842 ps_i
= ps_i
->next_in_row
;
1847 /* Creates an object of PS_INSN and initializes it to the given parameters. */
1849 create_ps_insn (ddg_node_ptr node
, int rest_count
, int cycle
)
1851 ps_insn_ptr ps_i
= xmalloc (sizeof (struct ps_insn
));
1854 ps_i
->next_in_row
= NULL
;
1855 ps_i
->prev_in_row
= NULL
;
1856 ps_i
->row_rest_count
= rest_count
;
1857 ps_i
->cycle
= cycle
;
1863 /* Removes the given PS_INSN from the partial schedule. Returns false if the
1864 node is not found in the partial schedule, else returns true. */
1866 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
1873 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
1874 if (! ps_i
->prev_in_row
)
1876 if (ps_i
!= ps
->rows
[row
])
1879 ps
->rows
[row
] = ps_i
->next_in_row
;
1881 ps
->rows
[row
]->prev_in_row
= NULL
;
1885 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
1886 if (ps_i
->next_in_row
)
1887 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
1893 /* Advances the PS_INSN one column in its current row; returns false
1894 in failure and true in success. */
1896 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
1898 ps_insn_ptr prev
, next
;
1904 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
1906 if (! ps_i
->next_in_row
)
1909 /* Check if next_in_row is dependent on ps_i, both having same sched
1910 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
1911 if (ps_i
->cycle
== ps_i
->next_in_row
->cycle
)
1914 ddg_node_ptr next_node
= ps_i
->next_in_row
->node
;
1916 for (e
= ps_i
->node
->out
; e
; e
= e
->next_out
)
1917 if (e
->dest
== next_node
)
1921 /* Advace PS_I over its next_in_row in the doubly linked list. */
1922 prev
= ps_i
->prev_in_row
;
1923 next
= ps_i
->next_in_row
;
1925 if (ps_i
== ps
->rows
[row
])
1926 ps
->rows
[row
] = next
;
1928 ps_i
->next_in_row
= next
->next_in_row
;
1930 if (next
->next_in_row
)
1931 next
->next_in_row
->prev_in_row
= ps_i
;
1933 next
->next_in_row
= ps_i
;
1934 ps_i
->prev_in_row
= next
;
1936 next
->prev_in_row
= prev
;
1938 prev
->next_in_row
= next
;
1943 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
1944 Returns 0 if this is not possible and a PS_INSN otherwise. */
1946 add_node_to_ps (partial_schedule_ptr ps
, ddg_node_ptr node
, int cycle
)
1948 ps_insn_ptr ps_i
, next_ps_i
, advance_after
;
1950 int row
= SMODULO (cycle
, ps
->ii
);
1954 && ps
->rows
[row
]->row_rest_count
>= issue_rate
)
1958 rest_count
+= ps
->rows
[row
]->row_rest_count
;
1960 ps_i
= create_ps_insn (node
, rest_count
, cycle
);
1961 ps_i
->next_in_row
= ps
->rows
[row
];
1962 ps_i
->prev_in_row
= NULL
;
1963 if (ps_i
->next_in_row
)
1964 ps_i
->next_in_row
->prev_in_row
= ps_i
;
1965 ps
->rows
[row
] = ps_i
;
1967 /* Check if n is dependent on an insn already in row, having same cycle
1968 (typically ANTI_DEP). If so, n must skip over it. */
1969 advance_after
= NULL
;
1970 for (next_ps_i
= ps_i
->next_in_row
;
1972 next_ps_i
= next_ps_i
->next_in_row
)
1973 if (next_ps_i
->cycle
== cycle
)
1974 for (e
= node
->in
; e
; e
= e
->next_in
)
1975 if (e
->src
== next_ps_i
->node
)
1976 advance_after
= next_ps_i
;
1979 while (ps_i
->prev_in_row
!= advance_after
)
1980 if (!ps_insn_advance_column (ps
, ps_i
))
1982 remove_node_from_ps (ps
, ps_i
);
1989 /* Advance time one cycle. Assumes DFA is being used. */
1991 advance_one_cycle (void)
1993 if (targetm
.sched
.use_dfa_pipeline_interface
1994 && (*targetm
.sched
.use_dfa_pipeline_interface
) ())
1996 if (targetm
.sched
.dfa_pre_cycle_insn
)
1997 state_transition (curr_state
,
1998 (*targetm
.sched
.dfa_pre_cycle_insn
) ());
2000 state_transition (curr_state
, NULL
);
2002 if (targetm
.sched
.dfa_post_cycle_insn
)
2003 state_transition (curr_state
,
2004 (*targetm
.sched
.dfa_post_cycle_insn
) ());
2008 /* Checks if PS has resource conflicts according to DFA, starting from
2009 FROM cycle to TO cycle; returns true if there are conflicts and false
2010 if there are no conflicts. Assumes DFA is being used. */
2012 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
2016 if (! targetm
.sched
.use_dfa_pipeline_interface
2017 || ! (*targetm
.sched
.use_dfa_pipeline_interface
) ())
2020 state_reset (curr_state
);
2022 for (cycle
= from
; cycle
<= to
; cycle
++)
2024 ps_insn_ptr crr_insn
;
2025 /* Holds the remaining issue slots in the current row. */
2026 int can_issue_more
= issue_rate
;
2028 /* Walk through the DFA for the current row. */
2029 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
2031 crr_insn
= crr_insn
->next_in_row
)
2033 rtx insn
= crr_insn
->node
->insn
;
2038 /* Check if there is room for the current insn. */
2039 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
2042 /* Update the DFA state and return with failure if the DFA found
2043 recource conflicts. */
2044 if (state_transition (curr_state
, insn
) >= 0)
2047 if (targetm
.sched
.variable_issue
)
2049 (*targetm
.sched
.variable_issue
) (sched_dump
, sched_verbose
,
2050 insn
, can_issue_more
);
2051 /* A naked CLOBBER or USE generates no instruction, so don't
2052 let them consume issue slots. */
2053 else if (GET_CODE (PATTERN (insn
)) != USE
2054 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2058 /* Advance the DFA to the next cycle. */
2059 advance_one_cycle ();
2064 /* Checks if the given node causes resource conflicts when added to PS at
2065 cycle C. If not the node is added to PS and returned; otherwise zero
2068 ps_add_node_check_conflicts (partial_schedule_ptr ps
, ddg_node_ptr n
, int c
)
2070 int has_conflicts
= 0;
2073 /* First add the node to the PS, if this succeeds check for conflicts,
2074 trying different issue slots in the same row. */
2075 if (! (ps_i
= add_node_to_ps (ps
, n
, c
)))
2076 return NULL
; /* Failed to insert the node at the given cycle. */
2078 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
2080 && ps_has_conflicts (ps
,
2084 /* Try different issue slots to find one that the given node can be
2085 scheduled in without conflicts. */
2086 while (has_conflicts
)
2088 if (! ps_insn_advance_column (ps
, ps_i
))
2090 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
2092 && ps_has_conflicts (ps
,
2099 remove_node_from_ps (ps
, ps_i
);
2103 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
2104 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
2108 /* Rotate the rows of PS such that insns scheduled at time
2109 START_CYCLE will appear in row 0. Updates max/min_cycles. */
2111 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
2113 int i
, row
, backward_rotates
;
2114 int last_row
= ps
->ii
- 1;
2116 if (start_cycle
== 0)
2119 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
2121 /* Revisit later and optimize this into a single loop. */
2122 for (i
= 0; i
< backward_rotates
; i
++)
2124 ps_insn_ptr first_row
= ps
->rows
[0];
2126 for (row
= 0; row
< last_row
; row
++)
2127 ps
->rows
[row
] = ps
->rows
[row
+1];
2129 ps
->rows
[last_row
] = first_row
;
2132 ps
->max_cycle
-= start_cycle
;
2133 ps
->min_cycle
-= start_cycle
;
2136 #endif /* INSN_SCHEDULING*/