1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "hard-reg-set.h"
33 #include "insn-config.h"
34 #include "insn-attr.h"
38 #include "sched-int.h"
40 #include "cfglayout.h"
49 #include "tree-pass.h"
51 #ifdef INSN_SCHEDULING
53 /* This file contains the implementation of the Swing Modulo Scheduler,
54 described in the following references:
55 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
56 Lifetime--sensitive modulo scheduling in a production environment.
57 IEEE Trans. on Comps., 50(3), March 2001
58 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
59 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
60 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
62 The basic structure is:
63 1. Build a data-dependence graph (DDG) for each loop.
64 2. Use the DDG to order the insns of a loop (not in topological order
65 necessarily, but rather) trying to place each insn after all its
66 predecessors _or_ after all its successors.
67 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
68 4. Use the ordering to perform list-scheduling of the loop:
69 1. Set II = MII. We will try to schedule the loop within II cycles.
70 2. Try to schedule the insns one by one according to the ordering.
71 For each insn compute an interval of cycles by considering already-
72 scheduled preds and succs (and associated latencies); try to place
73 the insn in the cycles of this window checking for potential
74 resource conflicts (using the DFA interface).
75 Note: this is different from the cycle-scheduling of schedule_insns;
76 here the insns are not scheduled monotonically top-down (nor bottom-
78 3. If failed in scheduling all insns - bump II++ and try again, unless
79 II reaches an upper bound MaxII, in which case report failure.
80 5. If we succeeded in scheduling the loop within II cycles, we now
81 generate prolog and epilog, decrease the counter of the loop, and
82 perform modulo variable expansion for live ranges that span more than
83 II cycles (i.e. use register copies to prevent a def from overwriting
84 itself before reaching the use).
88 /* This page defines partial-schedule structures and functions for
91 typedef struct partial_schedule
*partial_schedule_ptr
;
92 typedef struct ps_insn
*ps_insn_ptr
;
94 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
95 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
97 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
98 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
100 /* Perform signed modulo, always returning a non-negative value. */
101 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
103 /* The number of different iterations the nodes in ps span, assuming
104 the stage boundaries are placed efficiently. */
105 #define PS_STAGE_COUNT(ps) ((PS_MAX_CYCLE (ps) - PS_MIN_CYCLE (ps) \
106 + 1 + (ps)->ii - 1) / (ps)->ii)
108 /* A single instruction in the partial schedule. */
111 /* The corresponding DDG_NODE. */
114 /* The (absolute) cycle in which the PS instruction is scheduled.
115 Same as SCHED_TIME (node). */
118 /* The next/prev PS_INSN in the same row. */
119 ps_insn_ptr next_in_row
,
122 /* The number of nodes in the same row that come after this node. */
126 /* Holds the partial schedule as an array of II rows. Each entry of the
127 array points to a linked list of PS_INSNs, which represents the
128 instructions that are scheduled for that row. */
129 struct partial_schedule
131 int ii
; /* Number of rows in the partial schedule. */
132 int history
; /* Threshold for conflict checking using DFA. */
134 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
137 /* The earliest absolute cycle of an insn in the partial schedule. */
140 /* The latest absolute cycle of an insn in the partial schedule. */
143 ddg_ptr g
; /* The DDG of the insns in the partial schedule. */
146 /* We use this to record all the register replacements we do in
147 the kernel so we can undo SMS if it is not profitable. */
148 struct undo_replace_buff_elem
153 struct undo_replace_buff_elem
*next
;
158 static partial_schedule_ptr
create_partial_schedule (int ii
, ddg_ptr
, int history
);
159 static void free_partial_schedule (partial_schedule_ptr
);
160 static void reset_partial_schedule (partial_schedule_ptr
, int new_ii
);
161 void print_partial_schedule (partial_schedule_ptr
, FILE *);
162 static int kernel_number_of_cycles (rtx first_insn
, rtx last_insn
);
163 static ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr
,
164 ddg_node_ptr node
, int cycle
,
165 sbitmap must_precede
,
166 sbitmap must_follow
);
167 static void rotate_partial_schedule (partial_schedule_ptr
, int);
168 void set_row_column_for_ps (partial_schedule_ptr
);
169 static bool ps_unschedule_node (partial_schedule_ptr
, ddg_node_ptr
);
172 /* This page defines constants and structures for the modulo scheduling
175 /* As in haifa-sched.c: */
176 /* issue_rate is the number of insns that can be scheduled in the same
177 machine cycle. It can be defined in the config/mach/mach.h file,
178 otherwise we set it to 1. */
180 static int issue_rate
;
182 static int sms_order_nodes (ddg_ptr
, int, int * result
);
183 static void set_node_sched_params (ddg_ptr
);
184 static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr
, int, int, int *);
185 static void permute_partial_schedule (partial_schedule_ptr ps
, rtx last
);
186 static void generate_prolog_epilog (partial_schedule_ptr
,struct loop
* loop
, rtx
);
187 static void duplicate_insns_of_cycles (partial_schedule_ptr ps
,
188 int from_stage
, int to_stage
,
191 #define SCHED_ASAP(x) (((node_sched_params_ptr)(x)->aux.info)->asap)
192 #define SCHED_TIME(x) (((node_sched_params_ptr)(x)->aux.info)->time)
193 #define SCHED_FIRST_REG_MOVE(x) \
194 (((node_sched_params_ptr)(x)->aux.info)->first_reg_move)
195 #define SCHED_NREG_MOVES(x) \
196 (((node_sched_params_ptr)(x)->aux.info)->nreg_moves)
197 #define SCHED_ROW(x) (((node_sched_params_ptr)(x)->aux.info)->row)
198 #define SCHED_STAGE(x) (((node_sched_params_ptr)(x)->aux.info)->stage)
199 #define SCHED_COLUMN(x) (((node_sched_params_ptr)(x)->aux.info)->column)
201 /* The scheduling parameters held for each node. */
202 typedef struct node_sched_params
204 int asap
; /* A lower-bound on the absolute scheduling cycle. */
205 int time
; /* The absolute scheduling cycle (time >= asap). */
207 /* The following field (first_reg_move) is a pointer to the first
208 register-move instruction added to handle the modulo-variable-expansion
209 of the register defined by this node. This register-move copies the
210 original register defined by the node. */
213 /* The number of register-move instructions added, immediately preceding
217 int row
; /* Holds time % ii. */
218 int stage
; /* Holds time / ii. */
220 /* The column of a node inside the ps. If nodes u, v are on the same row,
221 u will precede v if column (u) < column (v). */
223 } *node_sched_params_ptr
;
226 /* The following three functions are copied from the current scheduler
227 code in order to use sched_analyze() for computing the dependencies.
228 They are used when initializing the sched_info structure. */
230 sms_print_insn (rtx insn
, int aligned ATTRIBUTE_UNUSED
)
234 sprintf (tmp
, "i%4d", INSN_UID (insn
));
239 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
240 regset cond_exec ATTRIBUTE_UNUSED
,
241 regset used ATTRIBUTE_UNUSED
,
242 regset set ATTRIBUTE_UNUSED
)
246 static struct sched_info sms_sched_info
=
255 compute_jump_reg_dependencies
,
260 NULL
, NULL
, NULL
, NULL
, NULL
,
261 #ifdef ENABLE_CHECKING
268 /* Return the register decremented and tested in INSN,
269 or zero if it is not a decrement-and-branch insn. */
272 doloop_register_get (rtx insn ATTRIBUTE_UNUSED
)
274 #ifdef HAVE_doloop_end
275 rtx pattern
, reg
, condition
;
280 pattern
= PATTERN (insn
);
281 condition
= doloop_condition_get (pattern
);
285 if (REG_P (XEXP (condition
, 0)))
286 reg
= XEXP (condition
, 0);
287 else if (GET_CODE (XEXP (condition
, 0)) == PLUS
288 && REG_P (XEXP (XEXP (condition
, 0), 0)))
289 reg
= XEXP (XEXP (condition
, 0), 0);
299 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
300 that the number of iterations is a compile-time constant. If so,
301 return the rtx that sets COUNT_REG to a constant, and set COUNT to
302 this constant. Otherwise return 0. */
304 const_iteration_count (rtx count_reg
, basic_block pre_header
,
305 HOST_WIDEST_INT
* count
)
313 get_ebb_head_tail (pre_header
, pre_header
, &head
, &tail
);
315 for (insn
= tail
; insn
!= PREV_INSN (head
); insn
= PREV_INSN (insn
))
316 if (INSN_P (insn
) && single_set (insn
) &&
317 rtx_equal_p (count_reg
, SET_DEST (single_set (insn
))))
319 rtx pat
= single_set (insn
);
321 if (GET_CODE (SET_SRC (pat
)) == CONST_INT
)
323 *count
= INTVAL (SET_SRC (pat
));
333 /* A very simple resource-based lower bound on the initiation interval.
334 ??? Improve the accuracy of this bound by considering the
335 utilization of various units. */
339 return (g
->num_nodes
/ issue_rate
);
343 /* Points to the array that contains the sched data for each node. */
344 static node_sched_params_ptr node_sched_params
;
346 /* Allocate sched_params for each node and initialize it. Assumes that
347 the aux field of each node contain the asap bound (computed earlier),
348 and copies it into the sched_params field. */
350 set_node_sched_params (ddg_ptr g
)
354 /* Allocate for each node in the DDG a place to hold the "sched_data". */
355 /* Initialize ASAP/ALAP/HIGHT to zero. */
356 node_sched_params
= (node_sched_params_ptr
)
357 xcalloc (g
->num_nodes
,
358 sizeof (struct node_sched_params
));
360 /* Set the pointer of the general data of the node to point to the
361 appropriate sched_params structure. */
362 for (i
= 0; i
< g
->num_nodes
; i
++)
364 /* Watch out for aliasing problems? */
365 node_sched_params
[i
].asap
= g
->nodes
[i
].aux
.count
;
366 g
->nodes
[i
].aux
.info
= &node_sched_params
[i
];
371 print_node_sched_params (FILE * file
, int num_nodes
)
377 for (i
= 0; i
< num_nodes
; i
++)
379 node_sched_params_ptr nsp
= &node_sched_params
[i
];
380 rtx reg_move
= nsp
->first_reg_move
;
383 fprintf (file
, "Node %d:\n", i
);
384 fprintf (file
, " asap = %d:\n", nsp
->asap
);
385 fprintf (file
, " time = %d:\n", nsp
->time
);
386 fprintf (file
, " nreg_moves = %d:\n", nsp
->nreg_moves
);
387 for (j
= 0; j
< nsp
->nreg_moves
; j
++)
389 fprintf (file
, " reg_move = ");
390 print_rtl_single (file
, reg_move
);
391 reg_move
= PREV_INSN (reg_move
);
396 /* Calculate an upper bound for II. SMS should not schedule the loop if it
397 requires more cycles than this bound. Currently set to the sum of the
398 longest latency edge for each node. Reset based on experiments. */
400 calculate_maxii (ddg_ptr g
)
405 for (i
= 0; i
< g
->num_nodes
; i
++)
407 ddg_node_ptr u
= &g
->nodes
[i
];
409 int max_edge_latency
= 0;
411 for (e
= u
->out
; e
; e
= e
->next_out
)
412 max_edge_latency
= MAX (max_edge_latency
, e
->latency
);
414 maxii
+= max_edge_latency
;
420 Breaking intra-loop register anti-dependences:
421 Each intra-loop register anti-dependence implies a cross-iteration true
422 dependence of distance 1. Therefore, we can remove such false dependencies
423 and figure out if the partial schedule broke them by checking if (for a
424 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
425 if so generate a register move. The number of such moves is equal to:
426 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
427 nreg_moves = ----------------------------------- + 1 - { dependence.
430 static struct undo_replace_buff_elem
*
431 generate_reg_moves (partial_schedule_ptr ps
)
436 struct undo_replace_buff_elem
*reg_move_replaces
= NULL
;
438 for (i
= 0; i
< g
->num_nodes
; i
++)
440 ddg_node_ptr u
= &g
->nodes
[i
];
442 int nreg_moves
= 0, i_reg_move
;
443 sbitmap
*uses_of_defs
;
445 rtx prev_reg
, old_reg
;
447 /* Compute the number of reg_moves needed for u, by looking at life
448 ranges started at u (excluding self-loops). */
449 for (e
= u
->out
; e
; e
= e
->next_out
)
450 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
452 int nreg_moves4e
= (SCHED_TIME (e
->dest
) - SCHED_TIME (e
->src
)) / ii
;
454 if (e
->distance
== 1)
455 nreg_moves4e
= (SCHED_TIME (e
->dest
) - SCHED_TIME (e
->src
) + ii
) / ii
;
457 /* If dest precedes src in the schedule of the kernel, then dest
458 will read before src writes and we can save one reg_copy. */
459 if (SCHED_ROW (e
->dest
) == SCHED_ROW (e
->src
)
460 && SCHED_COLUMN (e
->dest
) < SCHED_COLUMN (e
->src
))
463 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
469 /* Every use of the register defined by node may require a different
470 copy of this register, depending on the time the use is scheduled.
471 Set a bitmap vector, telling which nodes use each copy of this
473 uses_of_defs
= sbitmap_vector_alloc (nreg_moves
, g
->num_nodes
);
474 sbitmap_vector_zero (uses_of_defs
, nreg_moves
);
475 for (e
= u
->out
; e
; e
= e
->next_out
)
476 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
478 int dest_copy
= (SCHED_TIME (e
->dest
) - SCHED_TIME (e
->src
)) / ii
;
480 if (e
->distance
== 1)
481 dest_copy
= (SCHED_TIME (e
->dest
) - SCHED_TIME (e
->src
) + ii
) / ii
;
483 if (SCHED_ROW (e
->dest
) == SCHED_ROW (e
->src
)
484 && SCHED_COLUMN (e
->dest
) < SCHED_COLUMN (e
->src
))
488 SET_BIT (uses_of_defs
[dest_copy
- 1], e
->dest
->cuid
);
491 /* Now generate the reg_moves, attaching relevant uses to them. */
492 SCHED_NREG_MOVES (u
) = nreg_moves
;
493 old_reg
= prev_reg
= copy_rtx (SET_DEST (single_set (u
->insn
)));
494 last_reg_move
= u
->insn
;
496 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
498 unsigned int i_use
= 0;
499 rtx new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
500 rtx reg_move
= gen_move_insn (new_reg
, prev_reg
);
501 sbitmap_iterator sbi
;
503 add_insn_before (reg_move
, last_reg_move
);
504 last_reg_move
= reg_move
;
506 if (!SCHED_FIRST_REG_MOVE (u
))
507 SCHED_FIRST_REG_MOVE (u
) = reg_move
;
509 EXECUTE_IF_SET_IN_SBITMAP (uses_of_defs
[i_reg_move
], 0, i_use
, sbi
)
511 struct undo_replace_buff_elem
*rep
;
513 rep
= (struct undo_replace_buff_elem
*)
514 xcalloc (1, sizeof (struct undo_replace_buff_elem
));
515 rep
->insn
= g
->nodes
[i_use
].insn
;
516 rep
->orig_reg
= old_reg
;
517 rep
->new_reg
= new_reg
;
519 if (! reg_move_replaces
)
520 reg_move_replaces
= rep
;
523 rep
->next
= reg_move_replaces
;
524 reg_move_replaces
= rep
;
527 replace_rtx (g
->nodes
[i_use
].insn
, old_reg
, new_reg
);
532 sbitmap_vector_free (uses_of_defs
);
534 return reg_move_replaces
;
537 /* We call this when we want to undo the SMS schedule for a given loop.
538 One of the things that we do is to delete the register moves generated
539 for the sake of SMS; this function deletes the register move instructions
540 recorded in the undo buffer. */
542 undo_generate_reg_moves (partial_schedule_ptr ps
,
543 struct undo_replace_buff_elem
*reg_move_replaces
)
547 for (i
= 0; i
< ps
->g
->num_nodes
; i
++)
549 ddg_node_ptr u
= &ps
->g
->nodes
[i
];
551 rtx crr
= SCHED_FIRST_REG_MOVE (u
);
553 for (j
= 0; j
< SCHED_NREG_MOVES (u
); j
++)
555 prev
= PREV_INSN (crr
);
559 SCHED_FIRST_REG_MOVE (u
) = NULL_RTX
;
562 while (reg_move_replaces
)
564 struct undo_replace_buff_elem
*rep
= reg_move_replaces
;
566 reg_move_replaces
= reg_move_replaces
->next
;
567 replace_rtx (rep
->insn
, rep
->new_reg
, rep
->orig_reg
);
571 /* Free memory allocated for the undo buffer. */
573 free_undo_replace_buff (struct undo_replace_buff_elem
*reg_move_replaces
)
576 while (reg_move_replaces
)
578 struct undo_replace_buff_elem
*rep
= reg_move_replaces
;
580 reg_move_replaces
= reg_move_replaces
->next
;
585 /* Bump the SCHED_TIMEs of all nodes to start from zero. Set the values
586 of SCHED_ROW and SCHED_STAGE. */
588 normalize_sched_times (partial_schedule_ptr ps
)
592 int amount
= PS_MIN_CYCLE (ps
);
595 /* Don't include the closing branch assuming that it is the last node. */
596 for (i
= 0; i
< g
->num_nodes
- 1; i
++)
598 ddg_node_ptr u
= &g
->nodes
[i
];
599 int normalized_time
= SCHED_TIME (u
) - amount
;
601 gcc_assert (normalized_time
>= 0);
603 SCHED_TIME (u
) = normalized_time
;
604 SCHED_ROW (u
) = normalized_time
% ii
;
605 SCHED_STAGE (u
) = normalized_time
/ ii
;
609 /* Set SCHED_COLUMN of each node according to its position in PS. */
611 set_columns_for_ps (partial_schedule_ptr ps
)
615 for (row
= 0; row
< ps
->ii
; row
++)
617 ps_insn_ptr cur_insn
= ps
->rows
[row
];
620 for (; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
621 SCHED_COLUMN (cur_insn
->node
) = column
++;
625 /* Permute the insns according to their order in PS, from row 0 to
626 row ii-1, and position them right before LAST. This schedules
627 the insns of the loop kernel. */
629 permute_partial_schedule (partial_schedule_ptr ps
, rtx last
)
635 for (row
= 0; row
< ii
; row
++)
636 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
637 if (PREV_INSN (last
) != ps_ij
->node
->insn
)
638 reorder_insns_nobb (ps_ij
->node
->first_note
, ps_ij
->node
->insn
,
642 /* As part of undoing SMS we return to the original ordering of the
643 instructions inside the loop kernel. Given the partial schedule PS, this
644 function returns the ordering of the instruction according to their CUID
645 in the DDG (PS->G), which is the original order of the instruction before
648 undo_permute_partial_schedule (partial_schedule_ptr ps
, rtx last
)
652 for (i
= 0 ; i
< ps
->g
->num_nodes
; i
++)
653 if (last
== ps
->g
->nodes
[i
].insn
654 || last
== ps
->g
->nodes
[i
].first_note
)
656 else if (PREV_INSN (last
) != ps
->g
->nodes
[i
].insn
)
657 reorder_insns_nobb (ps
->g
->nodes
[i
].first_note
, ps
->g
->nodes
[i
].insn
,
661 /* Used to generate the prologue & epilogue. Duplicate the subset of
662 nodes whose stages are between FROM_STAGE and TO_STAGE (inclusive
663 of both), together with a prefix/suffix of their reg_moves. */
665 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
666 int to_stage
, int for_prolog
)
671 for (row
= 0; row
< ps
->ii
; row
++)
672 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
674 ddg_node_ptr u_node
= ps_ij
->node
;
676 rtx reg_move
= NULL_RTX
;
680 /* SCHED_STAGE (u_node) >= from_stage == 0. Generate increasing
681 number of reg_moves starting with the second occurrence of
682 u_node, which is generated if its SCHED_STAGE <= to_stage. */
683 i_reg_moves
= to_stage
- SCHED_STAGE (u_node
) + 1;
684 i_reg_moves
= MAX (i_reg_moves
, 0);
685 i_reg_moves
= MIN (i_reg_moves
, SCHED_NREG_MOVES (u_node
));
687 /* The reg_moves start from the *first* reg_move backwards. */
690 reg_move
= SCHED_FIRST_REG_MOVE (u_node
);
691 for (j
= 1; j
< i_reg_moves
; j
++)
692 reg_move
= PREV_INSN (reg_move
);
695 else /* It's for the epilog. */
697 /* SCHED_STAGE (u_node) <= to_stage. Generate all reg_moves,
698 starting to decrease one stage after u_node no longer occurs;
699 that is, generate all reg_moves until
700 SCHED_STAGE (u_node) == from_stage - 1. */
701 i_reg_moves
= SCHED_NREG_MOVES (u_node
)
702 - (from_stage
- SCHED_STAGE (u_node
) - 1);
703 i_reg_moves
= MAX (i_reg_moves
, 0);
704 i_reg_moves
= MIN (i_reg_moves
, SCHED_NREG_MOVES (u_node
));
706 /* The reg_moves start from the *last* reg_move forwards. */
709 reg_move
= SCHED_FIRST_REG_MOVE (u_node
);
710 for (j
= 1; j
< SCHED_NREG_MOVES (u_node
); j
++)
711 reg_move
= PREV_INSN (reg_move
);
715 for (j
= 0; j
< i_reg_moves
; j
++, reg_move
= NEXT_INSN (reg_move
))
716 emit_insn (copy_rtx (PATTERN (reg_move
)));
717 if (SCHED_STAGE (u_node
) >= from_stage
718 && SCHED_STAGE (u_node
) <= to_stage
)
719 duplicate_insn_chain (u_node
->first_note
, u_node
->insn
);
724 /* Generate the instructions (including reg_moves) for prolog & epilog. */
726 generate_prolog_epilog (partial_schedule_ptr ps
, struct loop
* loop
, rtx count_reg
)
729 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
732 /* Generate the prolog, inserting its insns on the loop-entry edge. */
736 /* Generate a subtract instruction at the beginning of the prolog to
737 adjust the loop count by STAGE_COUNT. */
738 emit_insn (gen_sub2_insn (count_reg
, GEN_INT (last_stage
)));
740 for (i
= 0; i
< last_stage
; i
++)
741 duplicate_insns_of_cycles (ps
, 0, i
, 1);
743 /* Put the prolog , on the one and only entry edge. */
744 e
= loop_preheader_edge (loop
);
745 loop_split_edge_with(e
, get_insns());
749 /* Generate the epilog, inserting its insns on the loop-exit edge. */
752 for (i
= 0; i
< last_stage
; i
++)
753 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, 0);
755 /* Put the epilogue on the one and only one exit edge. */
756 gcc_assert (loop
->single_exit
);
757 e
= loop
->single_exit
;
758 loop_split_edge_with(e
, get_insns());
762 /* Return the line note insn preceding INSN, for debugging. Taken from
765 find_line_note (rtx insn
)
767 for (; insn
; insn
= PREV_INSN (insn
))
769 && NOTE_LINE_NUMBER (insn
) >= 0)
775 /* Return true if all the BBs of the loop are empty except the
778 loop_single_full_bb_p (struct loop
*loop
)
781 basic_block
*bbs
= get_loop_body (loop
);
783 for (i
= 0; i
< loop
->num_nodes
; i
++)
786 bool empty_bb
= true;
788 if (bbs
[i
] == loop
->header
)
791 /* Make sure that basic blocks other than the header
792 have only notes labels or jumps. */
793 get_ebb_head_tail (bbs
[i
], bbs
[i
], &head
, &tail
);
794 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
796 if (NOTE_P (head
) || LABEL_P (head
)
797 || (INSN_P (head
) && JUMP_P (head
)))
813 /* A simple loop from SMS point of view; it is a loop that is composed of
814 either a single basic block or two BBs - a header and a latch. */
815 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
816 && (EDGE_COUNT (loop->latch->preds) == 1) \
817 && (EDGE_COUNT (loop->latch->succs) == 1))
819 /* Return true if the loop is in its canonical form and false if not.
820 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
822 loop_canon_p (struct loop
*loop
)
825 if (loop
->inner
|| ! loop
->outer
)
828 if (!loop
->single_exit
)
832 rtx line_note
= find_line_note (BB_END (loop
->header
));
834 fprintf (dump_file
, "SMS loop many exits ");
837 expanded_location xloc
;
838 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
839 fprintf (dump_file
, " %s %d (file, line)\n",
840 xloc
.file
, xloc
.line
);
846 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
850 rtx line_note
= find_line_note (BB_END (loop
->header
));
852 fprintf (dump_file
, "SMS loop many BBs. ");
855 expanded_location xloc
;
856 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
857 fprintf (dump_file
, " %s %d (file, line)\n",
858 xloc
.file
, xloc
.line
);
867 /* If there are more than one entry for the loop,
868 make it one by splitting the first entry edge and
869 redirecting the others to the new BB. */
871 canon_loop (struct loop
*loop
)
876 /* Avoid annoying special cases of edges going to exit
878 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR
->preds
)
879 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
880 loop_split_edge_with (e
, NULL_RTX
);
882 if (loop
->latch
== loop
->header
883 || EDGE_COUNT (loop
->latch
->succs
) > 1)
885 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
886 if (e
->src
== loop
->latch
)
888 loop_split_edge_with (e
, NULL_RTX
);
892 /* Main entry point, perform SMS scheduling on the loops of the function
893 that consist of single basic blocks. */
897 static int passes
= 0;
902 unsigned i
,num_loops
;
903 partial_schedule_ptr ps
;
906 basic_block bb
= NULL
;
907 /* vars to the versioning only if needed*/
909 basic_block condition_bb
= NULL
;
911 gcov_type trip_count
= 0;
913 loops
= loop_optimizer_init (LOOPS_HAVE_PREHEADERS
914 | LOOPS_HAVE_MARKED_SINGLE_EXITS
);
916 return; /* There is no loops to schedule. */
918 /* Initialize issue_rate. */
919 if (targetm
.sched
.issue_rate
)
921 int temp
= reload_completed
;
923 reload_completed
= 1;
924 issue_rate
= targetm
.sched
.issue_rate ();
925 reload_completed
= temp
;
930 /* Initialize the scheduler. */
931 current_sched_info
= &sms_sched_info
;
934 /* Init Data Flow analysis, to be used in interloop dep calculation. */
935 df
= df_init (DF_HARD_REGS
| DF_EQUIV_NOTES
| DF_SUBREGS
);
936 df_rd_add_problem (df
, 0);
937 df_ru_add_problem (df
, 0);
938 df_chain_add_problem (df
, DF_DU_CHAIN
| DF_UD_CHAIN
);
942 df_dump (df
, dump_file
);
944 /* Allocate memory to hold the DDG array one entry for each loop.
945 We use loop->num as index into this array. */
946 g_arr
= XCNEWVEC (ddg_ptr
, loops
->num
);
949 /* Build DDGs for all the relevant loops and hold them in G_ARR
950 indexed by the loop index. */
951 for (i
= 0; i
< loops
->num
; i
++)
955 struct loop
*loop
= loops
->parray
[i
];
958 if ((passes
++ > MAX_SMS_LOOP_NUMBER
) && (MAX_SMS_LOOP_NUMBER
!= -1))
961 fprintf (dump_file
, "SMS reached MAX_PASSES... \n");
966 if (! loop_canon_p (loop
))
969 if (! loop_single_full_bb_p (loop
))
974 get_ebb_head_tail (bb
, bb
, &head
, &tail
);
975 latch_edge
= loop_latch_edge (loop
);
976 gcc_assert (loop
->single_exit
);
977 if (loop
->single_exit
->count
)
978 trip_count
= latch_edge
->count
/ loop
->single_exit
->count
;
980 /* Perfrom SMS only on loops that their average count is above threshold. */
982 if ( latch_edge
->count
983 && (latch_edge
->count
< loop
->single_exit
->count
* SMS_LOOP_AVERAGE_COUNT_THRESHOLD
))
987 rtx line_note
= find_line_note (tail
);
991 expanded_location xloc
;
992 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
993 fprintf (dump_file
, "SMS bb %s %d (file, line)\n",
994 xloc
.file
, xloc
.line
);
996 fprintf (dump_file
, "SMS single-bb-loop\n");
997 if (profile_info
&& flag_branch_probabilities
)
999 fprintf (dump_file
, "SMS loop-count ");
1000 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1001 (HOST_WIDEST_INT
) bb
->count
);
1002 fprintf (dump_file
, "\n");
1003 fprintf (dump_file
, "SMS trip-count ");
1004 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1005 (HOST_WIDEST_INT
) trip_count
);
1006 fprintf (dump_file
, "\n");
1007 fprintf (dump_file
, "SMS profile-sum-max ");
1008 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1009 (HOST_WIDEST_INT
) profile_info
->sum_max
);
1010 fprintf (dump_file
, "\n");
1016 /* Make sure this is a doloop. */
1017 if ( !(count_reg
= doloop_register_get (tail
)))
1020 /* Don't handle BBs with calls or barriers, or !single_set insns. */
1021 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1024 || (INSN_P (insn
) && !JUMP_P (insn
)
1025 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
1028 if (insn
!= NEXT_INSN (tail
))
1033 fprintf (dump_file
, "SMS loop-with-call\n");
1034 else if (BARRIER_P (insn
))
1035 fprintf (dump_file
, "SMS loop-with-barrier\n");
1037 fprintf (dump_file
, "SMS loop-with-not-single-set\n");
1038 print_rtl_single (dump_file
, insn
);
1044 if (! (g
= create_ddg (bb
, df
, 0)))
1047 fprintf (dump_file
, "SMS doloop\n");
1054 /* Release Data Flow analysis data structures. */
1058 /* We don't want to perform SMS on new loops - created by versioning. */
1059 num_loops
= loops
->num
;
1060 /* Go over the built DDGs and perfrom SMS for each one of them. */
1061 for (i
= 0; i
< num_loops
; i
++)
1064 rtx count_reg
, count_init
;
1066 unsigned stage_count
= 0;
1067 HOST_WIDEST_INT loop_count
= 0;
1068 struct loop
*loop
= loops
->parray
[i
];
1070 if (! (g
= g_arr
[i
]))
1074 print_ddg (dump_file
, g
);
1076 get_ebb_head_tail (loop
->header
, loop
->header
, &head
, &tail
);
1078 latch_edge
= loop_latch_edge (loop
);
1079 gcc_assert (loop
->single_exit
);
1080 if (loop
->single_exit
->count
)
1081 trip_count
= latch_edge
->count
/ loop
->single_exit
->count
;
1085 rtx line_note
= find_line_note (tail
);
1089 expanded_location xloc
;
1090 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
1091 fprintf (dump_file
, "SMS bb %s %d (file, line)\n",
1092 xloc
.file
, xloc
.line
);
1094 fprintf (dump_file
, "SMS single-bb-loop\n");
1095 if (profile_info
&& flag_branch_probabilities
)
1097 fprintf (dump_file
, "SMS loop-count ");
1098 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1099 (HOST_WIDEST_INT
) bb
->count
);
1100 fprintf (dump_file
, "\n");
1101 fprintf (dump_file
, "SMS profile-sum-max ");
1102 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1103 (HOST_WIDEST_INT
) profile_info
->sum_max
);
1104 fprintf (dump_file
, "\n");
1106 fprintf (dump_file
, "SMS doloop\n");
1107 fprintf (dump_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1108 fprintf (dump_file
, "SMS num-loads %d\n", g
->num_loads
);
1109 fprintf (dump_file
, "SMS num-stores %d\n", g
->num_stores
);
1113 /* In case of th loop have doloop register it gets special
1115 count_init
= NULL_RTX
;
1116 if ((count_reg
= doloop_register_get (tail
)))
1118 basic_block pre_header
;
1120 pre_header
= loop_preheader_edge (loop
)->src
;
1121 count_init
= const_iteration_count (count_reg
, pre_header
,
1124 gcc_assert (count_reg
);
1126 if (dump_file
&& count_init
)
1128 fprintf (dump_file
, "SMS const-doloop ");
1129 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1131 fprintf (dump_file
, "\n");
1134 node_order
= XNEWVEC (int, g
->num_nodes
);
1136 mii
= 1; /* Need to pass some estimate of mii. */
1137 rec_mii
= sms_order_nodes (g
, mii
, node_order
);
1138 mii
= MAX (res_MII (g
), rec_mii
);
1139 maxii
= (calculate_maxii (g
) * SMS_MAX_II_FACTOR
) / 100;
1142 fprintf (dump_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1143 rec_mii
, mii
, maxii
);
1145 /* After sms_order_nodes and before sms_schedule_by_order, to copy over
1147 set_node_sched_params (g
);
1149 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
);
1152 stage_count
= PS_STAGE_COUNT (ps
);
1154 /* Stage count of 1 means that there is no interleaving between
1155 iterations, let the scheduling passes do the job. */
1157 || (count_init
&& (loop_count
<= stage_count
))
1158 || (flag_branch_probabilities
&& (trip_count
<= stage_count
)))
1162 fprintf (dump_file
, "SMS failed... \n");
1163 fprintf (dump_file
, "SMS sched-failed (stage-count=%d, loop-count=", stage_count
);
1164 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, loop_count
);
1165 fprintf (dump_file
, ", trip-count=");
1166 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, trip_count
);
1167 fprintf (dump_file
, ")\n");
1173 int orig_cycles
= kernel_number_of_cycles (BB_HEAD (g
->bb
), BB_END (g
->bb
));
1175 struct undo_replace_buff_elem
*reg_move_replaces
;
1180 "SMS succeeded %d %d (with ii, sc)\n", ps
->ii
,
1182 print_partial_schedule (ps
, dump_file
);
1184 "SMS Branch (%d) will later be scheduled at cycle %d.\n",
1185 g
->closing_branch
->cuid
, PS_MIN_CYCLE (ps
) - 1);
1188 /* Set the stage boundaries. If the DDG is built with closing_branch_deps,
1189 the closing_branch was scheduled and should appear in the last (ii-1)
1190 row. Otherwise, we are free to schedule the branch, and we let nodes
1191 that were scheduled at the first PS_MIN_CYCLE cycle appear in the first
1192 row; this should reduce stage_count to minimum. */
1193 normalize_sched_times (ps
);
1194 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
1195 set_columns_for_ps (ps
);
1197 /* Generate the kernel just to be able to measure its cycles. */
1198 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1199 reg_move_replaces
= generate_reg_moves (ps
);
1201 /* Get the number of cycles the new kernel expect to execute in. */
1202 new_cycles
= kernel_number_of_cycles (BB_HEAD (g
->bb
), BB_END (g
->bb
));
1204 /* Get back to the original loop so we can do loop versioning. */
1205 undo_permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1206 if (reg_move_replaces
)
1207 undo_generate_reg_moves (ps
, reg_move_replaces
);
1209 if ( new_cycles
>= orig_cycles
)
1211 /* SMS is not profitable so undo the permutation and reg move generation
1212 and return the kernel to its original state. */
1214 fprintf (dump_file
, "Undoing SMS because it is not profitable.\n");
1221 /* case the BCT count is not known , Do loop-versioning */
1222 if (count_reg
&& ! count_init
)
1224 rtx comp_rtx
= gen_rtx_fmt_ee (GT
, VOIDmode
, count_reg
,
1225 GEN_INT(stage_count
));
1227 nloop
= loop_version (loops
, loop
, comp_rtx
, &condition_bb
,
1231 /* Set new iteration count of loop kernel. */
1232 if (count_reg
&& count_init
)
1233 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1236 /* Now apply the scheduled kernel to the RTL of the loop. */
1237 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1239 /* Mark this loop as software pipelined so the later
1240 scheduling passes doesn't touch it. */
1241 if (! flag_resched_modulo_sched
)
1242 g
->bb
->flags
|= BB_DISABLE_SCHEDULE
;
1243 /* The life-info is not valid any more. */
1244 g
->bb
->flags
|= BB_DIRTY
;
1246 reg_move_replaces
= generate_reg_moves (ps
);
1248 print_node_sched_params (dump_file
, g
->num_nodes
);
1249 /* Generate prolog and epilog. */
1250 if (count_reg
&& !count_init
)
1251 generate_prolog_epilog (ps
, loop
, count_reg
);
1253 generate_prolog_epilog (ps
, loop
, NULL_RTX
);
1255 free_undo_replace_buff (reg_move_replaces
);
1258 free_partial_schedule (ps
);
1259 free (node_sched_params
);
1266 /* Release scheduler data, needed until now because of DFA. */
1268 loop_optimizer_finalize (loops
);
1271 /* The SMS scheduling algorithm itself
1272 -----------------------------------
1273 Input: 'O' an ordered list of insns of a loop.
1274 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1276 'Q' is the empty Set
1277 'PS' is the partial schedule; it holds the currently scheduled nodes with
1279 'PSP' previously scheduled predecessors.
1280 'PSS' previously scheduled successors.
1281 't(u)' the cycle where u is scheduled.
1282 'l(u)' is the latency of u.
1283 'd(v,u)' is the dependence distance from v to u.
1284 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1285 the node ordering phase.
1286 'check_hardware_resources_conflicts(u, PS, c)'
1287 run a trace around cycle/slot through DFA model
1288 to check resource conflicts involving instruction u
1289 at cycle c given the partial schedule PS.
1290 'add_to_partial_schedule_at_time(u, PS, c)'
1291 Add the node/instruction u to the partial schedule
1293 'calculate_register_pressure(PS)'
1294 Given a schedule of instructions, calculate the register
1295 pressure it implies. One implementation could be the
1296 maximum number of overlapping live ranges.
1297 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1298 registers available in the hardware.
1302 3. for each node u in O in pre-computed order
1303 4. if (PSP(u) != Q && PSS(u) == Q) then
1304 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1305 6. start = Early_start; end = Early_start + II - 1; step = 1
1306 11. else if (PSP(u) == Q && PSS(u) != Q) then
1307 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1308 13. start = Late_start; end = Late_start - II + 1; step = -1
1309 14. else if (PSP(u) != Q && PSS(u) != Q) then
1310 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1311 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1312 17. start = Early_start;
1313 18. end = min(Early_start + II - 1 , Late_start);
1315 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1316 21. start = ASAP(u); end = start + II - 1; step = 1
1320 24. for (c = start ; c != end ; c += step)
1321 25. if check_hardware_resources_conflicts(u, PS, c) then
1322 26. add_to_partial_schedule_at_time(u, PS, c)
1327 31. if (success == false) then
1329 33. if (II > maxII) then
1330 34. finish - failed to schedule
1335 39. if (calculate_register_pressure(PS) > maxRP) then
1338 42. compute epilogue & prologue
1339 43. finish - succeeded to schedule
1342 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1343 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1344 set to 0 to save compile time. */
1345 #define DFA_HISTORY SMS_DFA_HISTORY
1347 /* Given the partial schedule PS, this function calculates and returns the
1348 cycles in which we can schedule the node with the given index I.
1349 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1350 noticed that there are several cases in which we fail to SMS the loop
1351 because the sched window of a node is empty due to tight data-deps. In
1352 such cases we want to unschedule some of the predecessors/successors
1353 until we get non-empty scheduling window. It returns -1 if the
1354 scheduling window is empty and zero otherwise. */
1357 get_sched_window (partial_schedule_ptr ps
, int *nodes_order
, int i
,
1358 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
, int *end_p
)
1360 int start
, step
, end
;
1362 int u
= nodes_order
[i
];
1363 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
1364 sbitmap psp
= sbitmap_alloc (ps
->g
->num_nodes
);
1365 sbitmap pss
= sbitmap_alloc (ps
->g
->num_nodes
);
1366 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1367 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1371 /* 1. compute sched window for u (start, end, step). */
1374 psp_not_empty
= sbitmap_a_and_b_cg (psp
, u_node_preds
, sched_nodes
);
1375 pss_not_empty
= sbitmap_a_and_b_cg (pss
, u_node_succs
, sched_nodes
);
1377 if (psp_not_empty
&& !pss_not_empty
)
1379 int early_start
= INT_MIN
;
1382 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1384 ddg_node_ptr v_node
= e
->src
;
1385 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1387 int node_st
= SCHED_TIME (v_node
)
1388 + e
->latency
- (e
->distance
* ii
);
1390 early_start
= MAX (early_start
, node_st
);
1392 if (e
->data_type
== MEM_DEP
)
1393 end
= MIN (end
, SCHED_TIME (v_node
) + ii
- 1);
1396 start
= early_start
;
1397 end
= MIN (end
, early_start
+ ii
);
1401 else if (!psp_not_empty
&& pss_not_empty
)
1403 int late_start
= INT_MAX
;
1406 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1408 ddg_node_ptr v_node
= e
->dest
;
1409 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1411 late_start
= MIN (late_start
,
1412 SCHED_TIME (v_node
) - e
->latency
1413 + (e
->distance
* ii
));
1414 if (e
->data_type
== MEM_DEP
)
1415 end
= MAX (end
, SCHED_TIME (v_node
) - ii
+ 1);
1419 end
= MAX (end
, late_start
- ii
);
1423 else if (psp_not_empty
&& pss_not_empty
)
1425 int early_start
= INT_MIN
;
1426 int late_start
= INT_MAX
;
1430 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1432 ddg_node_ptr v_node
= e
->src
;
1434 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1436 early_start
= MAX (early_start
,
1437 SCHED_TIME (v_node
) + e
->latency
1438 - (e
->distance
* ii
));
1439 if (e
->data_type
== MEM_DEP
)
1440 end
= MIN (end
, SCHED_TIME (v_node
) + ii
- 1);
1443 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1445 ddg_node_ptr v_node
= e
->dest
;
1447 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1449 late_start
= MIN (late_start
,
1450 SCHED_TIME (v_node
) - e
->latency
1451 + (e
->distance
* ii
));
1452 if (e
->data_type
== MEM_DEP
)
1453 start
= MAX (start
, SCHED_TIME (v_node
) - ii
+ 1);
1456 start
= MAX (start
, early_start
);
1457 end
= MIN (end
, MIN (early_start
+ ii
, late_start
+ 1));
1460 else /* psp is empty && pss is empty. */
1462 start
= SCHED_ASAP (u_node
);
1473 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
1479 /* This function implements the scheduling algorithm for SMS according to the
1481 static partial_schedule_ptr
1482 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
)
1486 int try_again_with_larger_ii
= true;
1487 int num_nodes
= g
->num_nodes
;
1489 int start
, end
, step
; /* Place together into one struct? */
1490 sbitmap sched_nodes
= sbitmap_alloc (num_nodes
);
1491 sbitmap must_precede
= sbitmap_alloc (num_nodes
);
1492 sbitmap must_follow
= sbitmap_alloc (num_nodes
);
1493 sbitmap tobe_scheduled
= sbitmap_alloc (num_nodes
);
1495 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
, DFA_HISTORY
);
1497 sbitmap_ones (tobe_scheduled
);
1498 sbitmap_zero (sched_nodes
);
1500 while ((! sbitmap_equal (tobe_scheduled
, sched_nodes
)
1501 || try_again_with_larger_ii
) && ii
< maxii
)
1504 bool unscheduled_nodes
= false;
1507 fprintf(dump_file
, "Starting with ii=%d\n", ii
);
1508 if (try_again_with_larger_ii
)
1510 try_again_with_larger_ii
= false;
1511 sbitmap_zero (sched_nodes
);
1514 for (i
= 0; i
< num_nodes
; i
++)
1516 int u
= nodes_order
[i
];
1517 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
1518 rtx insn
= u_node
->insn
;
1522 RESET_BIT (tobe_scheduled
, u
);
1526 if (JUMP_P (insn
)) /* Closing branch handled later. */
1528 RESET_BIT (tobe_scheduled
, u
);
1532 if (TEST_BIT (sched_nodes
, u
))
1535 /* Try to get non-empty scheduling window. */
1537 while (get_sched_window (ps
, nodes_order
, i
, sched_nodes
, ii
, &start
, &step
, &end
) < 0
1540 unscheduled_nodes
= true;
1541 if (TEST_BIT (NODE_PREDECESSORS (u_node
), nodes_order
[j
- 1])
1542 || TEST_BIT (NODE_SUCCESSORS (u_node
), nodes_order
[j
- 1]))
1544 ps_unschedule_node (ps
, &ps
->g
->nodes
[nodes_order
[j
- 1]]);
1545 RESET_BIT (sched_nodes
, nodes_order
[j
- 1]);
1551 /* ??? Try backtracking instead of immediately ii++? */
1553 try_again_with_larger_ii
= true;
1554 reset_partial_schedule (ps
, ii
);
1557 /* 2. Try scheduling u in window. */
1559 fprintf(dump_file
, "Trying to schedule node %d in (%d .. %d) step %d\n",
1560 u
, start
, end
, step
);
1562 /* use must_follow & must_precede bitmaps to determine order
1563 of nodes within the cycle. */
1564 sbitmap_zero (must_precede
);
1565 sbitmap_zero (must_follow
);
1566 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1567 if (TEST_BIT (sched_nodes
, e
->src
->cuid
)
1568 && e
->latency
== (ii
* e
->distance
)
1569 && start
== SCHED_TIME (e
->src
))
1570 SET_BIT (must_precede
, e
->src
->cuid
);
1572 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1573 if (TEST_BIT (sched_nodes
, e
->dest
->cuid
)
1574 && e
->latency
== (ii
* e
->distance
)
1575 && end
== SCHED_TIME (e
->dest
))
1576 SET_BIT (must_follow
, e
->dest
->cuid
);
1579 if ((step
> 0 && start
< end
) || (step
< 0 && start
> end
))
1580 for (c
= start
; c
!= end
; c
+= step
)
1584 psi
= ps_add_node_check_conflicts (ps
, u_node
, c
,
1590 SCHED_TIME (u_node
) = c
;
1591 SET_BIT (sched_nodes
, u
);
1594 fprintf(dump_file
, "Schedule in %d\n", c
);
1600 /* ??? Try backtracking instead of immediately ii++? */
1602 try_again_with_larger_ii
= true;
1603 reset_partial_schedule (ps
, ii
);
1606 if (unscheduled_nodes
)
1609 /* ??? If (success), check register pressure estimates. */
1610 } /* Continue with next node. */
1611 } /* While try_again_with_larger_ii. */
1613 sbitmap_free (sched_nodes
);
1614 sbitmap_free (must_precede
);
1615 sbitmap_free (must_follow
);
1616 sbitmap_free (tobe_scheduled
);
1620 free_partial_schedule (ps
);
1627 /* This page implements the algorithm for ordering the nodes of a DDG
1628 for modulo scheduling, activated through the
1629 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
1631 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
1632 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
1633 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
1634 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
1635 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
1636 #define DEPTH(x) (ASAP ((x)))
1638 typedef struct node_order_params
* nopa
;
1640 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
1641 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
1642 static nopa
calculate_order_params (ddg_ptr
, int mii
);
1643 static int find_max_asap (ddg_ptr
, sbitmap
);
1644 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
1645 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
1647 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
1649 struct node_order_params
1656 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
1658 check_nodes_order (int *node_order
, int num_nodes
)
1661 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1665 for (i
= 0; i
< num_nodes
; i
++)
1667 int u
= node_order
[i
];
1669 gcc_assert (u
< num_nodes
&& u
>= 0 && !TEST_BIT (tmp
, u
));
1677 /* Order the nodes of G for scheduling and pass the result in
1678 NODE_ORDER. Also set aux.count of each node to ASAP.
1679 Return the recMII for the given DDG. */
1681 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
)
1685 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
1687 nopa nops
= calculate_order_params (g
, mii
);
1689 order_nodes_of_sccs (sccs
, node_order
);
1691 if (sccs
->num_sccs
> 0)
1692 /* First SCC has the largest recurrence_length. */
1693 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
1695 /* Save ASAP before destroying node_order_params. */
1696 for (i
= 0; i
< g
->num_nodes
; i
++)
1698 ddg_node_ptr v
= &g
->nodes
[i
];
1699 v
->aux
.count
= ASAP (v
);
1703 free_ddg_all_sccs (sccs
);
1704 check_nodes_order (node_order
, g
->num_nodes
);
1710 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
1713 ddg_ptr g
= all_sccs
->ddg
;
1714 int num_nodes
= g
->num_nodes
;
1715 sbitmap prev_sccs
= sbitmap_alloc (num_nodes
);
1716 sbitmap on_path
= sbitmap_alloc (num_nodes
);
1717 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1718 sbitmap ones
= sbitmap_alloc (num_nodes
);
1720 sbitmap_zero (prev_sccs
);
1721 sbitmap_ones (ones
);
1723 /* Perfrom the node ordering starting from the SCC with the highest recMII.
1724 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
1725 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
1727 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
1729 /* Add nodes on paths from previous SCCs to the current SCC. */
1730 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
1731 sbitmap_a_or_b (tmp
, scc
->nodes
, on_path
);
1733 /* Add nodes on paths from the current SCC to previous SCCs. */
1734 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
1735 sbitmap_a_or_b (tmp
, tmp
, on_path
);
1737 /* Remove nodes of previous SCCs from current extended SCC. */
1738 sbitmap_difference (tmp
, tmp
, prev_sccs
);
1740 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
1741 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
1744 /* Handle the remaining nodes that do not belong to any scc. Each call
1745 to order_nodes_in_scc handles a single connected component. */
1746 while (pos
< g
->num_nodes
)
1748 sbitmap_difference (tmp
, ones
, prev_sccs
);
1749 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
1751 sbitmap_free (prev_sccs
);
1752 sbitmap_free (on_path
);
1754 sbitmap_free (ones
);
1757 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
1758 static struct node_order_params
*
1759 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
)
1763 int num_nodes
= g
->num_nodes
;
1765 /* Allocate a place to hold ordering params for each node in the DDG. */
1766 nopa node_order_params_arr
;
1768 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
1769 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
1770 sizeof (struct node_order_params
));
1772 /* Set the aux pointer of each node to point to its order_params structure. */
1773 for (u
= 0; u
< num_nodes
; u
++)
1774 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
1776 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
1777 calculate ASAP, ALAP, mobility, distance, and height for each node
1778 in the dependence (direct acyclic) graph. */
1780 /* We assume that the nodes in the array are in topological order. */
1783 for (u
= 0; u
< num_nodes
; u
++)
1785 ddg_node_ptr u_node
= &g
->nodes
[u
];
1788 for (e
= u_node
->in
; e
; e
= e
->next_in
)
1789 if (e
->distance
== 0)
1790 ASAP (u_node
) = MAX (ASAP (u_node
),
1791 ASAP (e
->src
) + e
->latency
);
1792 max_asap
= MAX (max_asap
, ASAP (u_node
));
1795 for (u
= num_nodes
- 1; u
> -1; u
--)
1797 ddg_node_ptr u_node
= &g
->nodes
[u
];
1799 ALAP (u_node
) = max_asap
;
1800 HEIGHT (u_node
) = 0;
1801 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1802 if (e
->distance
== 0)
1804 ALAP (u_node
) = MIN (ALAP (u_node
),
1805 ALAP (e
->dest
) - e
->latency
);
1806 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
1807 HEIGHT (e
->dest
) + e
->latency
);
1811 return node_order_params_arr
;
1815 find_max_asap (ddg_ptr g
, sbitmap nodes
)
1820 sbitmap_iterator sbi
;
1822 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
1824 ddg_node_ptr u_node
= &g
->nodes
[u
];
1826 if (max_asap
< ASAP (u_node
))
1828 max_asap
= ASAP (u_node
);
1836 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
1840 int min_mob
= INT_MAX
;
1842 sbitmap_iterator sbi
;
1844 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
1846 ddg_node_ptr u_node
= &g
->nodes
[u
];
1848 if (max_hv
< HEIGHT (u_node
))
1850 max_hv
= HEIGHT (u_node
);
1851 min_mob
= MOB (u_node
);
1854 else if ((max_hv
== HEIGHT (u_node
))
1855 && (min_mob
> MOB (u_node
)))
1857 min_mob
= MOB (u_node
);
1865 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
1869 int min_mob
= INT_MAX
;
1871 sbitmap_iterator sbi
;
1873 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
1875 ddg_node_ptr u_node
= &g
->nodes
[u
];
1877 if (max_dv
< DEPTH (u_node
))
1879 max_dv
= DEPTH (u_node
);
1880 min_mob
= MOB (u_node
);
1883 else if ((max_dv
== DEPTH (u_node
))
1884 && (min_mob
> MOB (u_node
)))
1886 min_mob
= MOB (u_node
);
1893 /* Places the nodes of SCC into the NODE_ORDER array starting
1894 at position POS, according to the SMS ordering algorithm.
1895 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
1896 the NODE_ORDER array, starting from position zero. */
1898 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
1899 int * node_order
, int pos
)
1901 enum sms_direction dir
;
1902 int num_nodes
= g
->num_nodes
;
1903 sbitmap workset
= sbitmap_alloc (num_nodes
);
1904 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1905 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
1906 sbitmap predecessors
= sbitmap_alloc (num_nodes
);
1907 sbitmap successors
= sbitmap_alloc (num_nodes
);
1909 sbitmap_zero (predecessors
);
1910 find_predecessors (predecessors
, g
, nodes_ordered
);
1912 sbitmap_zero (successors
);
1913 find_successors (successors
, g
, nodes_ordered
);
1916 if (sbitmap_a_and_b_cg (tmp
, predecessors
, scc
))
1918 sbitmap_copy (workset
, tmp
);
1921 else if (sbitmap_a_and_b_cg (tmp
, successors
, scc
))
1923 sbitmap_copy (workset
, tmp
);
1930 sbitmap_zero (workset
);
1931 if ((u
= find_max_asap (g
, scc
)) >= 0)
1932 SET_BIT (workset
, u
);
1936 sbitmap_zero (zero_bitmap
);
1937 while (!sbitmap_equal (workset
, zero_bitmap
))
1940 ddg_node_ptr v_node
;
1941 sbitmap v_node_preds
;
1942 sbitmap v_node_succs
;
1946 while (!sbitmap_equal (workset
, zero_bitmap
))
1948 v
= find_max_hv_min_mob (g
, workset
);
1949 v_node
= &g
->nodes
[v
];
1950 node_order
[pos
++] = v
;
1951 v_node_succs
= NODE_SUCCESSORS (v_node
);
1952 sbitmap_a_and_b (tmp
, v_node_succs
, scc
);
1954 /* Don't consider the already ordered successors again. */
1955 sbitmap_difference (tmp
, tmp
, nodes_ordered
);
1956 sbitmap_a_or_b (workset
, workset
, tmp
);
1957 RESET_BIT (workset
, v
);
1958 SET_BIT (nodes_ordered
, v
);
1961 sbitmap_zero (predecessors
);
1962 find_predecessors (predecessors
, g
, nodes_ordered
);
1963 sbitmap_a_and_b (workset
, predecessors
, scc
);
1967 while (!sbitmap_equal (workset
, zero_bitmap
))
1969 v
= find_max_dv_min_mob (g
, workset
);
1970 v_node
= &g
->nodes
[v
];
1971 node_order
[pos
++] = v
;
1972 v_node_preds
= NODE_PREDECESSORS (v_node
);
1973 sbitmap_a_and_b (tmp
, v_node_preds
, scc
);
1975 /* Don't consider the already ordered predecessors again. */
1976 sbitmap_difference (tmp
, tmp
, nodes_ordered
);
1977 sbitmap_a_or_b (workset
, workset
, tmp
);
1978 RESET_BIT (workset
, v
);
1979 SET_BIT (nodes_ordered
, v
);
1982 sbitmap_zero (successors
);
1983 find_successors (successors
, g
, nodes_ordered
);
1984 sbitmap_a_and_b (workset
, successors
, scc
);
1988 sbitmap_free (workset
);
1989 sbitmap_free (zero_bitmap
);
1990 sbitmap_free (predecessors
);
1991 sbitmap_free (successors
);
1996 /* This page contains functions for manipulating partial-schedules during
1997 modulo scheduling. */
1999 /* Create a partial schedule and allocate a memory to hold II rows. */
2001 static partial_schedule_ptr
2002 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2004 partial_schedule_ptr ps
= XNEW (struct partial_schedule
);
2005 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2007 ps
->history
= history
;
2008 ps
->min_cycle
= INT_MAX
;
2009 ps
->max_cycle
= INT_MIN
;
2015 /* Free the PS_INSNs in rows array of the given partial schedule.
2016 ??? Consider caching the PS_INSN's. */
2018 free_ps_insns (partial_schedule_ptr ps
)
2022 for (i
= 0; i
< ps
->ii
; i
++)
2026 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2029 ps
->rows
[i
] = ps_insn
;
2035 /* Free all the memory allocated to the partial schedule. */
2038 free_partial_schedule (partial_schedule_ptr ps
)
2047 /* Clear the rows array with its PS_INSNs, and create a new one with
2051 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2056 if (new_ii
== ps
->ii
)
2058 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2059 * sizeof (ps_insn_ptr
));
2060 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2062 ps
->min_cycle
= INT_MAX
;
2063 ps
->max_cycle
= INT_MIN
;
2066 /* Prints the partial schedule as an ii rows array, for each rows
2067 print the ids of the insns in it. */
2069 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2073 for (i
= 0; i
< ps
->ii
; i
++)
2075 ps_insn_ptr ps_i
= ps
->rows
[i
];
2077 fprintf (dump
, "\n[CYCLE %d ]: ", i
);
2080 fprintf (dump
, "%d, ",
2081 INSN_UID (ps_i
->node
->insn
));
2082 ps_i
= ps_i
->next_in_row
;
2087 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2089 create_ps_insn (ddg_node_ptr node
, int rest_count
, int cycle
)
2091 ps_insn_ptr ps_i
= XNEW (struct ps_insn
);
2094 ps_i
->next_in_row
= NULL
;
2095 ps_i
->prev_in_row
= NULL
;
2096 ps_i
->row_rest_count
= rest_count
;
2097 ps_i
->cycle
= cycle
;
2103 /* Removes the given PS_INSN from the partial schedule. Returns false if the
2104 node is not found in the partial schedule, else returns true. */
2106 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2113 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2114 if (! ps_i
->prev_in_row
)
2116 if (ps_i
!= ps
->rows
[row
])
2119 ps
->rows
[row
] = ps_i
->next_in_row
;
2121 ps
->rows
[row
]->prev_in_row
= NULL
;
2125 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
2126 if (ps_i
->next_in_row
)
2127 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
2133 /* Unlike what literature describes for modulo scheduling (which focuses
2134 on VLIW machines) the order of the instructions inside a cycle is
2135 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2136 where the current instruction should go relative to the already
2137 scheduled instructions in the given cycle. Go over these
2138 instructions and find the first possible column to put it in. */
2140 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2141 sbitmap must_precede
, sbitmap must_follow
)
2143 ps_insn_ptr next_ps_i
;
2144 ps_insn_ptr first_must_follow
= NULL
;
2145 ps_insn_ptr last_must_precede
= NULL
;
2151 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2153 /* Find the first must follow and the last must precede
2154 and insert the node immediately after the must precede
2155 but make sure that it there is no must follow after it. */
2156 for (next_ps_i
= ps
->rows
[row
];
2158 next_ps_i
= next_ps_i
->next_in_row
)
2160 if (TEST_BIT (must_follow
, next_ps_i
->node
->cuid
)
2161 && ! first_must_follow
)
2162 first_must_follow
= next_ps_i
;
2163 if (TEST_BIT (must_precede
, next_ps_i
->node
->cuid
))
2165 /* If we have already met a node that must follow, then
2166 there is no possible column. */
2167 if (first_must_follow
)
2170 last_must_precede
= next_ps_i
;
2174 /* Now insert the node after INSERT_AFTER_PSI. */
2176 if (! last_must_precede
)
2178 ps_i
->next_in_row
= ps
->rows
[row
];
2179 ps_i
->prev_in_row
= NULL
;
2180 if (ps_i
->next_in_row
)
2181 ps_i
->next_in_row
->prev_in_row
= ps_i
;
2182 ps
->rows
[row
] = ps_i
;
2186 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
2187 last_must_precede
->next_in_row
= ps_i
;
2188 ps_i
->prev_in_row
= last_must_precede
;
2189 if (ps_i
->next_in_row
)
2190 ps_i
->next_in_row
->prev_in_row
= ps_i
;
2196 /* Advances the PS_INSN one column in its current row; returns false
2197 in failure and true in success. Bit N is set in MUST_FOLLOW if
2198 the node with cuid N must be come after the node pointed to by
2199 PS_I when scheduled in the same cycle. */
2201 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2202 sbitmap must_follow
)
2204 ps_insn_ptr prev
, next
;
2206 ddg_node_ptr next_node
;
2211 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2213 if (! ps_i
->next_in_row
)
2216 next_node
= ps_i
->next_in_row
->node
;
2218 /* Check if next_in_row is dependent on ps_i, both having same sched
2219 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
2220 if (TEST_BIT (must_follow
, next_node
->cuid
))
2223 /* Advance PS_I over its next_in_row in the doubly linked list. */
2224 prev
= ps_i
->prev_in_row
;
2225 next
= ps_i
->next_in_row
;
2227 if (ps_i
== ps
->rows
[row
])
2228 ps
->rows
[row
] = next
;
2230 ps_i
->next_in_row
= next
->next_in_row
;
2232 if (next
->next_in_row
)
2233 next
->next_in_row
->prev_in_row
= ps_i
;
2235 next
->next_in_row
= ps_i
;
2236 ps_i
->prev_in_row
= next
;
2238 next
->prev_in_row
= prev
;
2240 prev
->next_in_row
= next
;
2245 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
2246 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
2247 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
2248 before/after (respectively) the node pointed to by PS_I when scheduled
2249 in the same cycle. */
2251 add_node_to_ps (partial_schedule_ptr ps
, ddg_node_ptr node
, int cycle
,
2252 sbitmap must_precede
, sbitmap must_follow
)
2256 int row
= SMODULO (cycle
, ps
->ii
);
2259 && ps
->rows
[row
]->row_rest_count
>= issue_rate
)
2263 rest_count
+= ps
->rows
[row
]->row_rest_count
;
2265 ps_i
= create_ps_insn (node
, rest_count
, cycle
);
2267 /* Finds and inserts PS_I according to MUST_FOLLOW and
2269 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
2278 /* Advance time one cycle. Assumes DFA is being used. */
2280 advance_one_cycle (void)
2282 if (targetm
.sched
.dfa_pre_cycle_insn
)
2283 state_transition (curr_state
,
2284 targetm
.sched
.dfa_pre_cycle_insn ());
2286 state_transition (curr_state
, NULL
);
2288 if (targetm
.sched
.dfa_post_cycle_insn
)
2289 state_transition (curr_state
,
2290 targetm
.sched
.dfa_post_cycle_insn ());
2293 /* Given the kernel of a loop (from FIRST_INSN to LAST_INSN), finds
2294 the number of cycles according to DFA that the kernel fits in,
2295 we use this to check if we done well with SMS after we add
2296 register moves. In some cases register moves overhead makes
2297 it even worse than the original loop. We want SMS to be performed
2298 when it gives less cycles after register moves are added. */
2300 kernel_number_of_cycles (rtx first_insn
, rtx last_insn
)
2304 int can_issue_more
= issue_rate
;
2306 state_reset (curr_state
);
2308 for (insn
= first_insn
;
2309 insn
!= NULL_RTX
&& insn
!= last_insn
;
2310 insn
= NEXT_INSN (insn
))
2312 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
2315 /* Check if there is room for the current insn. */
2316 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
2319 advance_one_cycle ();
2320 can_issue_more
= issue_rate
;
2323 /* Update the DFA state and return with failure if the DFA found
2324 recource conflicts. */
2325 if (state_transition (curr_state
, insn
) >= 0)
2328 advance_one_cycle ();
2329 can_issue_more
= issue_rate
;
2332 if (targetm
.sched
.variable_issue
)
2334 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
2335 insn
, can_issue_more
);
2336 /* A naked CLOBBER or USE generates no instruction, so don't
2337 let them consume issue slots. */
2338 else if (GET_CODE (PATTERN (insn
)) != USE
2339 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2345 /* Checks if PS has resource conflicts according to DFA, starting from
2346 FROM cycle to TO cycle; returns true if there are conflicts and false
2347 if there are no conflicts. Assumes DFA is being used. */
2349 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
2353 state_reset (curr_state
);
2355 for (cycle
= from
; cycle
<= to
; cycle
++)
2357 ps_insn_ptr crr_insn
;
2358 /* Holds the remaining issue slots in the current row. */
2359 int can_issue_more
= issue_rate
;
2361 /* Walk through the DFA for the current row. */
2362 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
2364 crr_insn
= crr_insn
->next_in_row
)
2366 rtx insn
= crr_insn
->node
->insn
;
2371 /* Check if there is room for the current insn. */
2372 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
2375 /* Update the DFA state and return with failure if the DFA found
2376 recource conflicts. */
2377 if (state_transition (curr_state
, insn
) >= 0)
2380 if (targetm
.sched
.variable_issue
)
2382 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
2383 insn
, can_issue_more
);
2384 /* A naked CLOBBER or USE generates no instruction, so don't
2385 let them consume issue slots. */
2386 else if (GET_CODE (PATTERN (insn
)) != USE
2387 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2391 /* Advance the DFA to the next cycle. */
2392 advance_one_cycle ();
2397 /* Checks if the given node causes resource conflicts when added to PS at
2398 cycle C. If not the node is added to PS and returned; otherwise zero
2399 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
2400 cuid N must be come before/after (respectively) the node pointed to by
2401 PS_I when scheduled in the same cycle. */
2403 ps_add_node_check_conflicts (partial_schedule_ptr ps
, ddg_node_ptr n
,
2404 int c
, sbitmap must_precede
,
2405 sbitmap must_follow
)
2407 int has_conflicts
= 0;
2410 /* First add the node to the PS, if this succeeds check for
2411 conflicts, trying different issue slots in the same row. */
2412 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
2413 return NULL
; /* Failed to insert the node at the given cycle. */
2415 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
2417 && ps_has_conflicts (ps
,
2421 /* Try different issue slots to find one that the given node can be
2422 scheduled in without conflicts. */
2423 while (has_conflicts
)
2425 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
2427 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
2429 && ps_has_conflicts (ps
,
2436 remove_node_from_ps (ps
, ps_i
);
2440 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
2441 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
2445 /* Rotate the rows of PS such that insns scheduled at time
2446 START_CYCLE will appear in row 0. Updates max/min_cycles. */
2448 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
2450 int i
, row
, backward_rotates
;
2451 int last_row
= ps
->ii
- 1;
2453 if (start_cycle
== 0)
2456 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
2458 /* Revisit later and optimize this into a single loop. */
2459 for (i
= 0; i
< backward_rotates
; i
++)
2461 ps_insn_ptr first_row
= ps
->rows
[0];
2463 for (row
= 0; row
< last_row
; row
++)
2464 ps
->rows
[row
] = ps
->rows
[row
+1];
2466 ps
->rows
[last_row
] = first_row
;
2469 ps
->max_cycle
-= start_cycle
;
2470 ps
->min_cycle
-= start_cycle
;
2473 /* Remove the node N from the partial schedule PS; because we restart the DFA
2474 each time we want to check for resource conflicts; this is equivalent to
2475 unscheduling the node N. */
2477 ps_unschedule_node (partial_schedule_ptr ps
, ddg_node_ptr n
)
2480 int row
= SMODULO (SCHED_TIME (n
), ps
->ii
);
2482 if (row
< 0 || row
> ps
->ii
)
2485 for (ps_i
= ps
->rows
[row
];
2486 ps_i
&& ps_i
->node
!= n
;
2487 ps_i
= ps_i
->next_in_row
);
2491 return remove_node_from_ps (ps
, ps_i
);
2493 #endif /* INSN_SCHEDULING */
2496 gate_handle_sms (void)
2498 return (optimize
> 0 && flag_modulo_sched
);
2502 /* Run instruction scheduler. */
2503 /* Perform SMS module scheduling. */
2505 rest_of_handle_sms (void)
2507 #ifdef INSN_SCHEDULING
2510 /* We want to be able to create new pseudos. */
2512 /* Collect loop information to be used in SMS. */
2513 cfg_layout_initialize (CLEANUP_UPDATE_LIFE
);
2516 /* Update the life information, because we add pseudos. */
2517 max_regno
= max_reg_num ();
2518 allocate_reg_info (max_regno
, FALSE
, FALSE
);
2519 update_life_info (NULL
, UPDATE_LIFE_GLOBAL_RM_NOTES
,
2522 | PROP_KILL_DEAD_CODE
2523 | PROP_SCAN_DEAD_CODE
));
2527 /* Finalize layout changes. */
2529 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2530 bb
->aux
= bb
->next_bb
;
2531 cfg_layout_finalize ();
2532 free_dominance_info (CDI_DOMINATORS
);
2533 #endif /* INSN_SCHEDULING */
2537 struct tree_opt_pass pass_sms
=
2540 gate_handle_sms
, /* gate */
2541 rest_of_handle_sms
, /* execute */
2544 0, /* static_pass_number */
2546 0, /* properties_required */
2547 0, /* properties_provided */
2548 0, /* properties_destroyed */
2549 TODO_dump_func
, /* todo_flags_start */
2551 TODO_ggc_collect
, /* todo_flags_finish */