1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004, 2005, 2006
3 Free Software Foundation, Inc.
4 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
26 #include "coretypes.h"
31 #include "hard-reg-set.h"
35 #include "insn-config.h"
36 #include "insn-attr.h"
40 #include "sched-int.h"
42 #include "cfglayout.h"
51 #include "tree-pass.h"
53 #ifdef INSN_SCHEDULING
55 /* This file contains the implementation of the Swing Modulo Scheduler,
56 described in the following references:
57 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
58 Lifetime--sensitive modulo scheduling in a production environment.
59 IEEE Trans. on Comps., 50(3), March 2001
60 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
61 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
62 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
64 The basic structure is:
65 1. Build a data-dependence graph (DDG) for each loop.
66 2. Use the DDG to order the insns of a loop (not in topological order
67 necessarily, but rather) trying to place each insn after all its
68 predecessors _or_ after all its successors.
69 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
70 4. Use the ordering to perform list-scheduling of the loop:
71 1. Set II = MII. We will try to schedule the loop within II cycles.
72 2. Try to schedule the insns one by one according to the ordering.
73 For each insn compute an interval of cycles by considering already-
74 scheduled preds and succs (and associated latencies); try to place
75 the insn in the cycles of this window checking for potential
76 resource conflicts (using the DFA interface).
77 Note: this is different from the cycle-scheduling of schedule_insns;
78 here the insns are not scheduled monotonically top-down (nor bottom-
80 3. If failed in scheduling all insns - bump II++ and try again, unless
81 II reaches an upper bound MaxII, in which case report failure.
82 5. If we succeeded in scheduling the loop within II cycles, we now
83 generate prolog and epilog, decrease the counter of the loop, and
84 perform modulo variable expansion for live ranges that span more than
85 II cycles (i.e. use register copies to prevent a def from overwriting
86 itself before reaching the use).
90 /* This page defines partial-schedule structures and functions for
93 typedef struct partial_schedule
*partial_schedule_ptr
;
94 typedef struct ps_insn
*ps_insn_ptr
;
96 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
97 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
99 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
100 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
102 /* Perform signed modulo, always returning a non-negative value. */
103 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
105 /* The number of different iterations the nodes in ps span, assuming
106 the stage boundaries are placed efficiently. */
107 #define PS_STAGE_COUNT(ps) ((PS_MAX_CYCLE (ps) - PS_MIN_CYCLE (ps) \
108 + 1 + (ps)->ii - 1) / (ps)->ii)
110 /* A single instruction in the partial schedule. */
113 /* The corresponding DDG_NODE. */
116 /* The (absolute) cycle in which the PS instruction is scheduled.
117 Same as SCHED_TIME (node). */
120 /* The next/prev PS_INSN in the same row. */
121 ps_insn_ptr next_in_row
,
124 /* The number of nodes in the same row that come after this node. */
128 /* Holds the partial schedule as an array of II rows. Each entry of the
129 array points to a linked list of PS_INSNs, which represents the
130 instructions that are scheduled for that row. */
131 struct partial_schedule
133 int ii
; /* Number of rows in the partial schedule. */
134 int history
; /* Threshold for conflict checking using DFA. */
136 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
139 /* The earliest absolute cycle of an insn in the partial schedule. */
142 /* The latest absolute cycle of an insn in the partial schedule. */
145 ddg_ptr g
; /* The DDG of the insns in the partial schedule. */
148 /* We use this to record all the register replacements we do in
149 the kernel so we can undo SMS if it is not profitable. */
150 struct undo_replace_buff_elem
155 struct undo_replace_buff_elem
*next
;
160 static partial_schedule_ptr
create_partial_schedule (int ii
, ddg_ptr
, int history
);
161 static void free_partial_schedule (partial_schedule_ptr
);
162 static void reset_partial_schedule (partial_schedule_ptr
, int new_ii
);
163 void print_partial_schedule (partial_schedule_ptr
, FILE *);
164 static int kernel_number_of_cycles (rtx first_insn
, rtx last_insn
);
165 static ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr
,
166 ddg_node_ptr node
, int cycle
,
167 sbitmap must_precede
,
168 sbitmap must_follow
);
169 static void rotate_partial_schedule (partial_schedule_ptr
, int);
170 void set_row_column_for_ps (partial_schedule_ptr
);
171 static bool ps_unschedule_node (partial_schedule_ptr
, ddg_node_ptr
);
174 /* This page defines constants and structures for the modulo scheduling
177 /* As in haifa-sched.c: */
178 /* issue_rate is the number of insns that can be scheduled in the same
179 machine cycle. It can be defined in the config/mach/mach.h file,
180 otherwise we set it to 1. */
182 static int issue_rate
;
184 /* For printing statistics. */
185 static FILE *stats_file
;
187 static int sms_order_nodes (ddg_ptr
, int, int * result
);
188 static void set_node_sched_params (ddg_ptr
);
189 static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr
, int, int,
191 static void permute_partial_schedule (partial_schedule_ptr ps
, rtx last
);
192 static void generate_prolog_epilog (partial_schedule_ptr
,struct loop
* loop
, rtx
);
193 static void duplicate_insns_of_cycles (partial_schedule_ptr ps
,
194 int from_stage
, int to_stage
,
197 #define SCHED_ASAP(x) (((node_sched_params_ptr)(x)->aux.info)->asap)
198 #define SCHED_TIME(x) (((node_sched_params_ptr)(x)->aux.info)->time)
199 #define SCHED_FIRST_REG_MOVE(x) \
200 (((node_sched_params_ptr)(x)->aux.info)->first_reg_move)
201 #define SCHED_NREG_MOVES(x) \
202 (((node_sched_params_ptr)(x)->aux.info)->nreg_moves)
203 #define SCHED_ROW(x) (((node_sched_params_ptr)(x)->aux.info)->row)
204 #define SCHED_STAGE(x) (((node_sched_params_ptr)(x)->aux.info)->stage)
205 #define SCHED_COLUMN(x) (((node_sched_params_ptr)(x)->aux.info)->column)
207 /* The scheduling parameters held for each node. */
208 typedef struct node_sched_params
210 int asap
; /* A lower-bound on the absolute scheduling cycle. */
211 int time
; /* The absolute scheduling cycle (time >= asap). */
213 /* The following field (first_reg_move) is a pointer to the first
214 register-move instruction added to handle the modulo-variable-expansion
215 of the register defined by this node. This register-move copies the
216 original register defined by the node. */
219 /* The number of register-move instructions added, immediately preceding
223 int row
; /* Holds time % ii. */
224 int stage
; /* Holds time / ii. */
226 /* The column of a node inside the ps. If nodes u, v are on the same row,
227 u will precede v if column (u) < column (v). */
229 } *node_sched_params_ptr
;
232 /* The following three functions are copied from the current scheduler
233 code in order to use sched_analyze() for computing the dependencies.
234 They are used when initializing the sched_info structure. */
236 sms_print_insn (rtx insn
, int aligned ATTRIBUTE_UNUSED
)
240 sprintf (tmp
, "i%4d", INSN_UID (insn
));
245 contributes_to_priority (rtx next
, rtx insn
)
247 return BLOCK_NUM (next
) == BLOCK_NUM (insn
);
251 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
252 regset cond_exec ATTRIBUTE_UNUSED
,
253 regset used ATTRIBUTE_UNUSED
,
254 regset set ATTRIBUTE_UNUSED
)
258 static struct sched_info sms_sched_info
=
266 contributes_to_priority
,
267 compute_jump_reg_dependencies
,
274 /* Return the register decremented and tested in INSN,
275 or zero if it is not a decrement-and-branch insn. */
278 doloop_register_get (rtx insn ATTRIBUTE_UNUSED
)
280 #ifdef HAVE_doloop_end
281 rtx pattern
, reg
, condition
;
286 pattern
= PATTERN (insn
);
287 condition
= doloop_condition_get (pattern
);
291 if (REG_P (XEXP (condition
, 0)))
292 reg
= XEXP (condition
, 0);
293 else if (GET_CODE (XEXP (condition
, 0)) == PLUS
294 && REG_P (XEXP (XEXP (condition
, 0), 0)))
295 reg
= XEXP (XEXP (condition
, 0), 0);
305 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
306 that the number of iterations is a compile-time constant. If so,
307 return the rtx that sets COUNT_REG to a constant, and set COUNT to
308 this constant. Otherwise return 0. */
310 const_iteration_count (rtx count_reg
, basic_block pre_header
,
311 HOST_WIDEST_INT
* count
)
319 get_block_head_tail (pre_header
->index
, &head
, &tail
);
321 for (insn
= tail
; insn
!= PREV_INSN (head
); insn
= PREV_INSN (insn
))
322 if (INSN_P (insn
) && single_set (insn
) &&
323 rtx_equal_p (count_reg
, SET_DEST (single_set (insn
))))
325 rtx pat
= single_set (insn
);
327 if (GET_CODE (SET_SRC (pat
)) == CONST_INT
)
329 *count
= INTVAL (SET_SRC (pat
));
339 /* A very simple resource-based lower bound on the initiation interval.
340 ??? Improve the accuracy of this bound by considering the
341 utilization of various units. */
345 return (g
->num_nodes
/ issue_rate
);
349 /* Points to the array that contains the sched data for each node. */
350 static node_sched_params_ptr node_sched_params
;
352 /* Allocate sched_params for each node and initialize it. Assumes that
353 the aux field of each node contain the asap bound (computed earlier),
354 and copies it into the sched_params field. */
356 set_node_sched_params (ddg_ptr g
)
360 /* Allocate for each node in the DDG a place to hold the "sched_data". */
361 /* Initialize ASAP/ALAP/HIGHT to zero. */
362 node_sched_params
= (node_sched_params_ptr
)
363 xcalloc (g
->num_nodes
,
364 sizeof (struct node_sched_params
));
366 /* Set the pointer of the general data of the node to point to the
367 appropriate sched_params structure. */
368 for (i
= 0; i
< g
->num_nodes
; i
++)
370 /* Watch out for aliasing problems? */
371 node_sched_params
[i
].asap
= g
->nodes
[i
].aux
.count
;
372 g
->nodes
[i
].aux
.info
= &node_sched_params
[i
];
377 print_node_sched_params (FILE * dump_file
, int num_nodes
)
383 for (i
= 0; i
< num_nodes
; i
++)
385 node_sched_params_ptr nsp
= &node_sched_params
[i
];
386 rtx reg_move
= nsp
->first_reg_move
;
389 fprintf (dump_file
, "Node %d:\n", i
);
390 fprintf (dump_file
, " asap = %d:\n", nsp
->asap
);
391 fprintf (dump_file
, " time = %d:\n", nsp
->time
);
392 fprintf (dump_file
, " nreg_moves = %d:\n", nsp
->nreg_moves
);
393 for (j
= 0; j
< nsp
->nreg_moves
; j
++)
395 fprintf (dump_file
, " reg_move = ");
396 print_rtl_single (dump_file
, reg_move
);
397 reg_move
= PREV_INSN (reg_move
);
402 /* Calculate an upper bound for II. SMS should not schedule the loop if it
403 requires more cycles than this bound. Currently set to the sum of the
404 longest latency edge for each node. Reset based on experiments. */
406 calculate_maxii (ddg_ptr g
)
411 for (i
= 0; i
< g
->num_nodes
; i
++)
413 ddg_node_ptr u
= &g
->nodes
[i
];
415 int max_edge_latency
= 0;
417 for (e
= u
->out
; e
; e
= e
->next_out
)
418 max_edge_latency
= MAX (max_edge_latency
, e
->latency
);
420 maxii
+= max_edge_latency
;
426 Breaking intra-loop register anti-dependences:
427 Each intra-loop register anti-dependence implies a cross-iteration true
428 dependence of distance 1. Therefore, we can remove such false dependencies
429 and figure out if the partial schedule broke them by checking if (for a
430 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
431 if so generate a register move. The number of such moves is equal to:
432 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
433 nreg_moves = ----------------------------------- + 1 - { dependence.
436 static struct undo_replace_buff_elem
*
437 generate_reg_moves (partial_schedule_ptr ps
)
442 struct undo_replace_buff_elem
*reg_move_replaces
= NULL
;
444 for (i
= 0; i
< g
->num_nodes
; i
++)
446 ddg_node_ptr u
= &g
->nodes
[i
];
448 int nreg_moves
= 0, i_reg_move
;
449 sbitmap
*uses_of_defs
;
451 rtx prev_reg
, old_reg
;
453 /* Compute the number of reg_moves needed for u, by looking at life
454 ranges started at u (excluding self-loops). */
455 for (e
= u
->out
; e
; e
= e
->next_out
)
456 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
458 int nreg_moves4e
= (SCHED_TIME (e
->dest
) - SCHED_TIME (e
->src
)) / ii
;
460 if (e
->distance
== 1)
461 nreg_moves4e
= (SCHED_TIME (e
->dest
) - SCHED_TIME (e
->src
) + ii
) / ii
;
463 /* If dest precedes src in the schedule of the kernel, then dest
464 will read before src writes and we can save one reg_copy. */
465 if (SCHED_ROW (e
->dest
) == SCHED_ROW (e
->src
)
466 && SCHED_COLUMN (e
->dest
) < SCHED_COLUMN (e
->src
))
469 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
475 /* Every use of the register defined by node may require a different
476 copy of this register, depending on the time the use is scheduled.
477 Set a bitmap vector, telling which nodes use each copy of this
479 uses_of_defs
= sbitmap_vector_alloc (nreg_moves
, g
->num_nodes
);
480 sbitmap_vector_zero (uses_of_defs
, nreg_moves
);
481 for (e
= u
->out
; e
; e
= e
->next_out
)
482 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
484 int dest_copy
= (SCHED_TIME (e
->dest
) - SCHED_TIME (e
->src
)) / ii
;
486 if (e
->distance
== 1)
487 dest_copy
= (SCHED_TIME (e
->dest
) - SCHED_TIME (e
->src
) + ii
) / ii
;
489 if (SCHED_ROW (e
->dest
) == SCHED_ROW (e
->src
)
490 && SCHED_COLUMN (e
->dest
) < SCHED_COLUMN (e
->src
))
494 SET_BIT (uses_of_defs
[dest_copy
- 1], e
->dest
->cuid
);
497 /* Now generate the reg_moves, attaching relevant uses to them. */
498 SCHED_NREG_MOVES (u
) = nreg_moves
;
499 old_reg
= prev_reg
= copy_rtx (SET_DEST (single_set (u
->insn
)));
500 last_reg_move
= u
->insn
;
502 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
504 unsigned int i_use
= 0;
505 rtx new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
506 rtx reg_move
= gen_move_insn (new_reg
, prev_reg
);
507 sbitmap_iterator sbi
;
509 add_insn_before (reg_move
, last_reg_move
);
510 last_reg_move
= reg_move
;
512 if (!SCHED_FIRST_REG_MOVE (u
))
513 SCHED_FIRST_REG_MOVE (u
) = reg_move
;
515 EXECUTE_IF_SET_IN_SBITMAP (uses_of_defs
[i_reg_move
], 0, i_use
, sbi
)
517 struct undo_replace_buff_elem
*rep
;
519 rep
= (struct undo_replace_buff_elem
*)
520 xcalloc (1, sizeof (struct undo_replace_buff_elem
));
521 rep
->insn
= g
->nodes
[i_use
].insn
;
522 rep
->orig_reg
= old_reg
;
523 rep
->new_reg
= new_reg
;
525 if (! reg_move_replaces
)
526 reg_move_replaces
= rep
;
529 rep
->next
= reg_move_replaces
;
530 reg_move_replaces
= rep
;
533 replace_rtx (g
->nodes
[i_use
].insn
, old_reg
, new_reg
);
539 return reg_move_replaces
;
542 /* We call this when we want to undo the SMS schedule for a given loop.
543 One of the things that we do is to delete the register moves generated
544 for the sake of SMS; this function deletes the register move instructions
545 recorded in the undo buffer. */
547 undo_generate_reg_moves (partial_schedule_ptr ps
,
548 struct undo_replace_buff_elem
*reg_move_replaces
)
552 for (i
= 0; i
< ps
->g
->num_nodes
; i
++)
554 ddg_node_ptr u
= &ps
->g
->nodes
[i
];
556 rtx crr
= SCHED_FIRST_REG_MOVE (u
);
558 for (j
= 0; j
< SCHED_NREG_MOVES (u
); j
++)
560 prev
= PREV_INSN (crr
);
564 SCHED_FIRST_REG_MOVE (u
) = NULL_RTX
;
567 while (reg_move_replaces
)
569 struct undo_replace_buff_elem
*rep
= reg_move_replaces
;
571 reg_move_replaces
= reg_move_replaces
->next
;
572 replace_rtx (rep
->insn
, rep
->new_reg
, rep
->orig_reg
);
576 /* Free memory allocated for the undo buffer. */
578 free_undo_replace_buff (struct undo_replace_buff_elem
*reg_move_replaces
)
581 while (reg_move_replaces
)
583 struct undo_replace_buff_elem
*rep
= reg_move_replaces
;
585 reg_move_replaces
= reg_move_replaces
->next
;
590 /* Bump the SCHED_TIMEs of all nodes to start from zero. Set the values
591 of SCHED_ROW and SCHED_STAGE. */
593 normalize_sched_times (partial_schedule_ptr ps
)
597 int amount
= PS_MIN_CYCLE (ps
);
600 /* Don't include the closing branch assuming that it is the last node. */
601 for (i
= 0; i
< g
->num_nodes
- 1; i
++)
603 ddg_node_ptr u
= &g
->nodes
[i
];
604 int normalized_time
= SCHED_TIME (u
) - amount
;
606 gcc_assert (normalized_time
>= 0);
608 SCHED_TIME (u
) = normalized_time
;
609 SCHED_ROW (u
) = normalized_time
% ii
;
610 SCHED_STAGE (u
) = normalized_time
/ ii
;
614 /* Set SCHED_COLUMN of each node according to its position in PS. */
616 set_columns_for_ps (partial_schedule_ptr ps
)
620 for (row
= 0; row
< ps
->ii
; row
++)
622 ps_insn_ptr cur_insn
= ps
->rows
[row
];
625 for (; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
626 SCHED_COLUMN (cur_insn
->node
) = column
++;
630 /* Permute the insns according to their order in PS, from row 0 to
631 row ii-1, and position them right before LAST. This schedules
632 the insns of the loop kernel. */
634 permute_partial_schedule (partial_schedule_ptr ps
, rtx last
)
640 for (row
= 0; row
< ii
; row
++)
641 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
642 if (PREV_INSN (last
) != ps_ij
->node
->insn
)
643 reorder_insns_nobb (ps_ij
->node
->first_note
, ps_ij
->node
->insn
,
647 /* As part of undoing SMS we return to the original ordering of the
648 instructions inside the loop kernel. Given the partial schedule PS, this
649 function returns the ordering of the instruction according to their CUID
650 in the DDG (PS->G), which is the original order of the instruction before
653 undo_permute_partial_schedule (partial_schedule_ptr ps
, rtx last
)
657 for (i
= 0 ; i
< ps
->g
->num_nodes
; i
++)
658 if (last
== ps
->g
->nodes
[i
].insn
659 || last
== ps
->g
->nodes
[i
].first_note
)
661 else if (PREV_INSN (last
) != ps
->g
->nodes
[i
].insn
)
662 reorder_insns_nobb (ps
->g
->nodes
[i
].first_note
, ps
->g
->nodes
[i
].insn
,
666 /* Used to generate the prologue & epilogue. Duplicate the subset of
667 nodes whose stages are between FROM_STAGE and TO_STAGE (inclusive
668 of both), together with a prefix/suffix of their reg_moves. */
670 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
671 int to_stage
, int for_prolog
)
676 for (row
= 0; row
< ps
->ii
; row
++)
677 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
679 ddg_node_ptr u_node
= ps_ij
->node
;
681 rtx reg_move
= NULL_RTX
;
685 /* SCHED_STAGE (u_node) >= from_stage == 0. Generate increasing
686 number of reg_moves starting with the second occurrence of
687 u_node, which is generated if its SCHED_STAGE <= to_stage. */
688 i_reg_moves
= to_stage
- SCHED_STAGE (u_node
) + 1;
689 i_reg_moves
= MAX (i_reg_moves
, 0);
690 i_reg_moves
= MIN (i_reg_moves
, SCHED_NREG_MOVES (u_node
));
692 /* The reg_moves start from the *first* reg_move backwards. */
695 reg_move
= SCHED_FIRST_REG_MOVE (u_node
);
696 for (j
= 1; j
< i_reg_moves
; j
++)
697 reg_move
= PREV_INSN (reg_move
);
700 else /* It's for the epilog. */
702 /* SCHED_STAGE (u_node) <= to_stage. Generate all reg_moves,
703 starting to decrease one stage after u_node no longer occurs;
704 that is, generate all reg_moves until
705 SCHED_STAGE (u_node) == from_stage - 1. */
706 i_reg_moves
= SCHED_NREG_MOVES (u_node
)
707 - (from_stage
- SCHED_STAGE (u_node
) - 1);
708 i_reg_moves
= MAX (i_reg_moves
, 0);
709 i_reg_moves
= MIN (i_reg_moves
, SCHED_NREG_MOVES (u_node
));
711 /* The reg_moves start from the *last* reg_move forwards. */
714 reg_move
= SCHED_FIRST_REG_MOVE (u_node
);
715 for (j
= 1; j
< SCHED_NREG_MOVES (u_node
); j
++)
716 reg_move
= PREV_INSN (reg_move
);
720 for (j
= 0; j
< i_reg_moves
; j
++, reg_move
= NEXT_INSN (reg_move
))
721 emit_insn (copy_rtx (PATTERN (reg_move
)));
722 if (SCHED_STAGE (u_node
) >= from_stage
723 && SCHED_STAGE (u_node
) <= to_stage
)
724 duplicate_insn_chain (u_node
->first_note
, u_node
->insn
);
729 /* Generate the instructions (including reg_moves) for prolog & epilog. */
731 generate_prolog_epilog (partial_schedule_ptr ps
, struct loop
* loop
, rtx count_reg
)
734 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
737 /* Generate the prolog, inserting its insns on the loop-entry edge. */
741 /* Generate a subtract instruction at the beginning of the prolog to
742 adjust the loop count by STAGE_COUNT. */
743 emit_insn (gen_sub2_insn (count_reg
, GEN_INT (last_stage
)));
745 for (i
= 0; i
< last_stage
; i
++)
746 duplicate_insns_of_cycles (ps
, 0, i
, 1);
748 /* Put the prolog , on the one and only entry edge. */
749 e
= loop_preheader_edge (loop
);
750 loop_split_edge_with(e
, get_insns());
754 /* Generate the epilog, inserting its insns on the loop-exit edge. */
757 for (i
= 0; i
< last_stage
; i
++)
758 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, 0);
760 /* Put the epilogue on the one and only one exit edge. */
761 gcc_assert (loop
->single_exit
);
762 e
= loop
->single_exit
;
763 loop_split_edge_with(e
, get_insns());
767 /* Return the line note insn preceding INSN, for debugging. Taken from
770 find_line_note (rtx insn
)
772 for (; insn
; insn
= PREV_INSN (insn
))
774 && NOTE_LINE_NUMBER (insn
) >= 0)
780 /* Return true if all the BBs of the loop are empty except the
783 loop_single_full_bb_p (struct loop
*loop
)
786 basic_block
*bbs
= get_loop_body (loop
);
788 for (i
= 0; i
< loop
->num_nodes
; i
++)
791 bool empty_bb
= true;
793 if (bbs
[i
] == loop
->header
)
796 /* Make sure that basic blocks other than the header
797 have only notes labels or jumps. */
798 get_block_head_tail (bbs
[i
]->index
, &head
, &tail
);
799 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
801 if (NOTE_P (head
) || LABEL_P (head
)
802 || (INSN_P (head
) && JUMP_P (head
)))
818 /* A simple loop from SMS point of view; it is a loop that is composed of
819 either a single basic block or two BBs - a header and a latch. */
820 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
821 && (EDGE_COUNT (loop->latch->preds) == 1) \
822 && (EDGE_COUNT (loop->latch->succs) == 1))
824 /* Return true if the loop is in its canonical form and false if not.
825 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
827 loop_canon_p (struct loop
*loop
, FILE *dump_file
)
830 if (loop
->inner
|| ! loop
->outer
)
833 if (!loop
->single_exit
)
837 rtx line_note
= find_line_note (BB_END (loop
->header
));
839 fprintf (dump_file
, "SMS loop many exits ");
842 expanded_location xloc
;
843 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
844 fprintf (stats_file
, " %s %d (file, line)\n",
845 xloc
.file
, xloc
.line
);
851 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
855 rtx line_note
= find_line_note (BB_END (loop
->header
));
857 fprintf (dump_file
, "SMS loop many BBs. ");
860 expanded_location xloc
;
861 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
862 fprintf (stats_file
, " %s %d (file, line)\n",
863 xloc
.file
, xloc
.line
);
872 /* If there are more than one entry for the loop,
873 make it one by splitting the first entry edge and
874 redirecting the others to the new BB. */
876 canon_loop (struct loop
*loop
)
881 /* Avoid annoying special cases of edges going to exit
883 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR
->preds
)
884 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
885 loop_split_edge_with (e
, NULL_RTX
);
887 if (loop
->latch
== loop
->header
888 || EDGE_COUNT (loop
->latch
->succs
) > 1)
890 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
891 if (e
->src
== loop
->latch
)
893 loop_split_edge_with (e
, NULL_RTX
);
897 /* Build the loop information without loop
898 canonization, the loop canonization will
899 be performed if the loop is SMSable. */
900 static struct loops
*
901 build_loops_structure (FILE *dumpfile
)
903 struct loops
*loops
= xcalloc (1, sizeof (struct loops
));
905 /* Find the loops. */
907 if (flow_loops_find (loops
) <= 1)
910 flow_loops_free (loops
);
916 /* Not going to update these. */
917 free (loops
->cfg
.rc_order
);
918 loops
->cfg
.rc_order
= NULL
;
919 free (loops
->cfg
.dfs_order
);
920 loops
->cfg
.dfs_order
= NULL
;
922 create_preheaders (loops
, CP_SIMPLE_PREHEADERS
);
923 mark_single_exit_loops (loops
);
925 flow_loops_dump (loops
, dumpfile
, NULL
, 1);
927 #ifdef ENABLE_CHECKING
928 verify_dominators (CDI_DOMINATORS
);
929 verify_loop_structure (loops
);
935 /* Main entry point, perform SMS scheduling on the loops of the function
936 that consist of single basic blocks. */
938 sms_schedule (FILE *dump_file
)
940 static int passes
= 0;
945 unsigned i
,num_loops
;
946 partial_schedule_ptr ps
;
949 basic_block bb
= NULL
;
950 /* vars to the versioning only if needed*/
952 basic_block condition_bb
= NULL
;
954 gcov_type trip_count
= 0;
956 if (! (loops
= build_loops_structure (dump_file
)))
957 return; /* There is no loops to schedule. */
960 stats_file
= dump_file
;
962 /* Initialize issue_rate. */
963 if (targetm
.sched
.issue_rate
)
965 int temp
= reload_completed
;
967 reload_completed
= 1;
968 issue_rate
= targetm
.sched
.issue_rate ();
969 reload_completed
= temp
;
974 /* Initialize the scheduler. */
975 current_sched_info
= &sms_sched_info
;
978 /* Init Data Flow analysis, to be used in interloop dep calculation. */
979 df
= df_init (DF_HARD_REGS
| DF_EQUIV_NOTES
| DF_SUBREGS
);
980 df_rd_add_problem (df
);
981 df_ru_add_problem (df
);
982 df_chain_add_problem (df
, DF_DU_CHAIN
| DF_UD_CHAIN
);
985 /* Allocate memory to hold the DDG array one entry for each loop.
986 We use loop->num as index into this array. */
987 g_arr
= xcalloc (loops
->num
, sizeof (ddg_ptr
));
990 /* Build DDGs for all the relevant loops and hold them in G_ARR
991 indexed by the loop index. */
992 for (i
= 0; i
< loops
->num
; i
++)
996 struct loop
*loop
= loops
->parray
[i
];
999 if ((passes
++ > MAX_SMS_LOOP_NUMBER
) && (MAX_SMS_LOOP_NUMBER
!= -1))
1002 fprintf (dump_file
, "SMS reached MAX_PASSES... \n");
1007 if (! loop_canon_p (loop
, dump_file
))
1010 if (! loop_single_full_bb_p (loop
))
1015 get_block_head_tail (bb
->index
, &head
, &tail
);
1016 latch_edge
= loop_latch_edge (loop
);
1017 gcc_assert (loop
->single_exit
);
1018 if (loop
->single_exit
->count
)
1019 trip_count
= latch_edge
->count
/ loop
->single_exit
->count
;
1021 /* Perfrom SMS only on loops that their average count is above threshold. */
1023 if ( latch_edge
->count
1024 && (latch_edge
->count
< loop
->single_exit
->count
* SMS_LOOP_AVERAGE_COUNT_THRESHOLD
))
1028 rtx line_note
= find_line_note (tail
);
1032 expanded_location xloc
;
1033 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
1034 fprintf (stats_file
, "SMS bb %s %d (file, line)\n",
1035 xloc
.file
, xloc
.line
);
1037 fprintf (stats_file
, "SMS single-bb-loop\n");
1038 if (profile_info
&& flag_branch_probabilities
)
1040 fprintf (stats_file
, "SMS loop-count ");
1041 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1042 (HOST_WIDEST_INT
) bb
->count
);
1043 fprintf (stats_file
, "\n");
1044 fprintf (stats_file
, "SMS trip-count ");
1045 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1046 (HOST_WIDEST_INT
) trip_count
);
1047 fprintf (stats_file
, "\n");
1048 fprintf (stats_file
, "SMS profile-sum-max ");
1049 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1050 (HOST_WIDEST_INT
) profile_info
->sum_max
);
1051 fprintf (stats_file
, "\n");
1057 /* Make sure this is a doloop. */
1058 if ( !(count_reg
= doloop_register_get (tail
)))
1061 /* Don't handle BBs with calls or barriers, or !single_set insns. */
1062 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1065 || (INSN_P (insn
) && !JUMP_P (insn
)
1066 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
1069 if (insn
!= NEXT_INSN (tail
))
1074 fprintf (stats_file
, "SMS loop-with-call\n");
1075 else if (BARRIER_P (insn
))
1076 fprintf (stats_file
, "SMS loop-with-barrier\n");
1078 fprintf (stats_file
, "SMS loop-with-not-single-set\n");
1079 print_rtl_single (stats_file
, insn
);
1085 if (! (g
= create_ddg (bb
, df
, 0)))
1088 fprintf (stats_file
, "SMS doloop\n");
1095 /* Release Data Flow analysis data structures. */
1099 /* We don't want to perform SMS on new loops - created by versioning. */
1100 num_loops
= loops
->num
;
1101 /* Go over the built DDGs and perfrom SMS for each one of them. */
1102 for (i
= 0; i
< num_loops
; i
++)
1105 rtx count_reg
, count_init
;
1107 unsigned stage_count
= 0;
1108 HOST_WIDEST_INT loop_count
= 0;
1109 struct loop
*loop
= loops
->parray
[i
];
1111 if (! (g
= g_arr
[i
]))
1115 print_ddg (dump_file
, g
);
1117 get_block_head_tail (loop
->header
->index
, &head
, &tail
);
1119 latch_edge
= loop_latch_edge (loop
);
1120 gcc_assert (loop
->single_exit
);
1121 if (loop
->single_exit
->count
)
1122 trip_count
= latch_edge
->count
/ loop
->single_exit
->count
;
1126 rtx line_note
= find_line_note (tail
);
1130 expanded_location xloc
;
1131 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
1132 fprintf (stats_file
, "SMS bb %s %d (file, line)\n",
1133 xloc
.file
, xloc
.line
);
1135 fprintf (stats_file
, "SMS single-bb-loop\n");
1136 if (profile_info
&& flag_branch_probabilities
)
1138 fprintf (stats_file
, "SMS loop-count ");
1139 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1140 (HOST_WIDEST_INT
) bb
->count
);
1141 fprintf (stats_file
, "\n");
1142 fprintf (stats_file
, "SMS profile-sum-max ");
1143 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1144 (HOST_WIDEST_INT
) profile_info
->sum_max
);
1145 fprintf (stats_file
, "\n");
1147 fprintf (stats_file
, "SMS doloop\n");
1148 fprintf (stats_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1149 fprintf (stats_file
, "SMS num-loads %d\n", g
->num_loads
);
1150 fprintf (stats_file
, "SMS num-stores %d\n", g
->num_stores
);
1154 /* In case of th loop have doloop register it gets special
1156 count_init
= NULL_RTX
;
1157 if ((count_reg
= doloop_register_get (tail
)))
1159 basic_block pre_header
;
1161 pre_header
= loop_preheader_edge (loop
)->src
;
1162 count_init
= const_iteration_count (count_reg
, pre_header
,
1165 gcc_assert (count_reg
);
1167 if (stats_file
&& count_init
)
1169 fprintf (stats_file
, "SMS const-doloop ");
1170 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1172 fprintf (stats_file
, "\n");
1175 node_order
= (int *) xmalloc (sizeof (int) * g
->num_nodes
);
1177 mii
= 1; /* Need to pass some estimate of mii. */
1178 rec_mii
= sms_order_nodes (g
, mii
, node_order
);
1179 mii
= MAX (res_MII (g
), rec_mii
);
1180 maxii
= (calculate_maxii (g
) * SMS_MAX_II_FACTOR
) / 100;
1183 fprintf (stats_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1184 rec_mii
, mii
, maxii
);
1186 /* After sms_order_nodes and before sms_schedule_by_order, to copy over
1188 set_node_sched_params (g
);
1190 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
, dump_file
);
1193 stage_count
= PS_STAGE_COUNT (ps
);
1195 /* Stage count of 1 means that there is no interleaving between
1196 iterations, let the scheduling passes do the job. */
1198 || (count_init
&& (loop_count
<= stage_count
))
1199 || (flag_branch_probabilities
&& (trip_count
<= stage_count
)))
1203 fprintf (dump_file
, "SMS failed... \n");
1204 fprintf (dump_file
, "SMS sched-failed (stage-count=%d, loop-count=", stage_count
);
1205 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, loop_count
);
1206 fprintf (dump_file
, ", trip-count=");
1207 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, trip_count
);
1208 fprintf (dump_file
, ")\n");
1214 int orig_cycles
= kernel_number_of_cycles (BB_HEAD (g
->bb
), BB_END (g
->bb
));
1216 struct undo_replace_buff_elem
*reg_move_replaces
;
1220 fprintf (stats_file
,
1221 "SMS succeeded %d %d (with ii, sc)\n", ps
->ii
,
1223 print_partial_schedule (ps
, stats_file
);
1224 fprintf (stats_file
,
1225 "SMS Branch (%d) will later be scheduled at cycle %d.\n",
1226 g
->closing_branch
->cuid
, PS_MIN_CYCLE (ps
) - 1);
1229 /* Set the stage boundaries. If the DDG is built with closing_branch_deps,
1230 the closing_branch was scheduled and should appear in the last (ii-1)
1231 row. Otherwise, we are free to schedule the branch, and we let nodes
1232 that were scheduled at the first PS_MIN_CYCLE cycle appear in the first
1233 row; this should reduce stage_count to minimum. */
1234 normalize_sched_times (ps
);
1235 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
1236 set_columns_for_ps (ps
);
1238 /* Generate the kernel just to be able to measure its cycles. */
1239 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1240 reg_move_replaces
= generate_reg_moves (ps
);
1242 /* Get the number of cycles the new kernel expect to execute in. */
1243 new_cycles
= kernel_number_of_cycles (BB_HEAD (g
->bb
), BB_END (g
->bb
));
1245 /* Get back to the original loop so we can do loop versioning. */
1246 undo_permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1247 if (reg_move_replaces
)
1248 undo_generate_reg_moves (ps
, reg_move_replaces
);
1250 if ( new_cycles
>= orig_cycles
)
1252 /* SMS is not profitable so undo the permutation and reg move generation
1253 and return the kernel to its original state. */
1255 fprintf (dump_file
, "Undoing SMS because it is not profitable.\n");
1262 /* case the BCT count is not known , Do loop-versioning */
1263 if (count_reg
&& ! count_init
)
1265 rtx comp_rtx
= gen_rtx_fmt_ee (GT
, VOIDmode
, count_reg
,
1266 GEN_INT(stage_count
));
1268 nloop
= loop_version (loops
, loop
, comp_rtx
, &condition_bb
,
1272 /* Set new iteration count of loop kernel. */
1273 if (count_reg
&& count_init
)
1274 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1277 /* Now apply the scheduled kernel to the RTL of the loop. */
1278 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1280 /* Mark this loop as software pipelined so the later
1281 scheduling passes doesn't touch it. */
1282 if (! flag_resched_modulo_sched
)
1283 g
->bb
->flags
|= BB_DISABLE_SCHEDULE
;
1284 /* The life-info is not valid any more. */
1285 g
->bb
->flags
|= BB_DIRTY
;
1287 reg_move_replaces
= generate_reg_moves (ps
);
1289 print_node_sched_params (dump_file
, g
->num_nodes
);
1290 /* Generate prolog and epilog. */
1291 if (count_reg
&& !count_init
)
1292 generate_prolog_epilog (ps
, loop
, count_reg
);
1294 generate_prolog_epilog (ps
, loop
, NULL_RTX
);
1296 free_undo_replace_buff (reg_move_replaces
);
1299 free_partial_schedule (ps
);
1300 free (node_sched_params
);
1305 /* Release scheduler data, needed until now because of DFA. */
1307 loop_optimizer_finalize (loops
, dump_file
);
1310 /* The SMS scheduling algorithm itself
1311 -----------------------------------
1312 Input: 'O' an ordered list of insns of a loop.
1313 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1315 'Q' is the empty Set
1316 'PS' is the partial schedule; it holds the currently scheduled nodes with
1318 'PSP' previously scheduled predecessors.
1319 'PSS' previously scheduled successors.
1320 't(u)' the cycle where u is scheduled.
1321 'l(u)' is the latency of u.
1322 'd(v,u)' is the dependence distance from v to u.
1323 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1324 the node ordering phase.
1325 'check_hardware_resources_conflicts(u, PS, c)'
1326 run a trace around cycle/slot through DFA model
1327 to check resource conflicts involving instruction u
1328 at cycle c given the partial schedule PS.
1329 'add_to_partial_schedule_at_time(u, PS, c)'
1330 Add the node/instruction u to the partial schedule
1332 'calculate_register_pressure(PS)'
1333 Given a schedule of instructions, calculate the register
1334 pressure it implies. One implementation could be the
1335 maximum number of overlapping live ranges.
1336 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1337 registers available in the hardware.
1341 3. for each node u in O in pre-computed order
1342 4. if (PSP(u) != Q && PSS(u) == Q) then
1343 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1344 6. start = Early_start; end = Early_start + II - 1; step = 1
1345 11. else if (PSP(u) == Q && PSS(u) != Q) then
1346 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1347 13. start = Late_start; end = Late_start - II + 1; step = -1
1348 14. else if (PSP(u) != Q && PSS(u) != Q) then
1349 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1350 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1351 17. start = Early_start;
1352 18. end = min(Early_start + II - 1 , Late_start);
1354 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1355 21. start = ASAP(u); end = start + II - 1; step = 1
1359 24. for (c = start ; c != end ; c += step)
1360 25. if check_hardware_resources_conflicts(u, PS, c) then
1361 26. add_to_partial_schedule_at_time(u, PS, c)
1366 31. if (success == false) then
1368 33. if (II > maxII) then
1369 34. finish - failed to schedule
1374 39. if (calculate_register_pressure(PS) > maxRP) then
1377 42. compute epilogue & prologue
1378 43. finish - succeeded to schedule
1381 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1382 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1383 set to 0 to save compile time. */
1384 #define DFA_HISTORY SMS_DFA_HISTORY
1386 /* Given the partial schedule PS, this function calculates and returns the
1387 cycles in which we can schedule the node with the given index I.
1388 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1389 noticed that there are several cases in which we fail to SMS the loop
1390 because the sched window of a node is empty due to tight data-deps. In
1391 such cases we want to unschedule some of the predecessors/successors
1392 until we get non-empty scheduling window. It returns -1 if the
1393 scheduling window is empty and zero otherwise. */
1396 get_sched_window (partial_schedule_ptr ps
, int *nodes_order
, int i
,
1397 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
, int *end_p
)
1399 int start
, step
, end
;
1401 int u
= nodes_order
[i
];
1402 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
1403 sbitmap psp
= sbitmap_alloc (ps
->g
->num_nodes
);
1404 sbitmap pss
= sbitmap_alloc (ps
->g
->num_nodes
);
1405 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1406 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1410 /* 1. compute sched window for u (start, end, step). */
1413 psp_not_empty
= sbitmap_a_and_b_cg (psp
, u_node_preds
, sched_nodes
);
1414 pss_not_empty
= sbitmap_a_and_b_cg (pss
, u_node_succs
, sched_nodes
);
1416 if (psp_not_empty
&& !pss_not_empty
)
1418 int early_start
= INT_MIN
;
1421 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1423 ddg_node_ptr v_node
= e
->src
;
1424 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1426 int node_st
= SCHED_TIME (v_node
)
1427 + e
->latency
- (e
->distance
* ii
);
1429 early_start
= MAX (early_start
, node_st
);
1431 if (e
->data_type
== MEM_DEP
)
1432 end
= MIN (end
, SCHED_TIME (v_node
) + ii
- 1);
1435 start
= early_start
;
1436 end
= MIN (end
, early_start
+ ii
);
1440 else if (!psp_not_empty
&& pss_not_empty
)
1442 int late_start
= INT_MAX
;
1445 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1447 ddg_node_ptr v_node
= e
->dest
;
1448 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1450 late_start
= MIN (late_start
,
1451 SCHED_TIME (v_node
) - e
->latency
1452 + (e
->distance
* ii
));
1453 if (e
->data_type
== MEM_DEP
)
1454 end
= MAX (end
, SCHED_TIME (v_node
) - ii
+ 1);
1458 end
= MAX (end
, late_start
- ii
);
1462 else if (psp_not_empty
&& pss_not_empty
)
1464 int early_start
= INT_MIN
;
1465 int late_start
= INT_MAX
;
1469 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1471 ddg_node_ptr v_node
= e
->src
;
1473 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1475 early_start
= MAX (early_start
,
1476 SCHED_TIME (v_node
) + e
->latency
1477 - (e
->distance
* ii
));
1478 if (e
->data_type
== MEM_DEP
)
1479 end
= MIN (end
, SCHED_TIME (v_node
) + ii
- 1);
1482 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1484 ddg_node_ptr v_node
= e
->dest
;
1486 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1488 late_start
= MIN (late_start
,
1489 SCHED_TIME (v_node
) - e
->latency
1490 + (e
->distance
* ii
));
1491 if (e
->data_type
== MEM_DEP
)
1492 start
= MAX (start
, SCHED_TIME (v_node
) - ii
+ 1);
1495 start
= MAX (start
, early_start
);
1496 end
= MIN (end
, MIN (early_start
+ ii
, late_start
+ 1));
1499 else /* psp is empty && pss is empty. */
1501 start
= SCHED_ASAP (u_node
);
1512 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
1518 /* This function implements the scheduling algorithm for SMS according to the
1520 static partial_schedule_ptr
1521 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
, FILE *dump_file
)
1525 int try_again_with_larger_ii
= true;
1526 int num_nodes
= g
->num_nodes
;
1528 int start
, end
, step
; /* Place together into one struct? */
1529 sbitmap sched_nodes
= sbitmap_alloc (num_nodes
);
1530 sbitmap must_precede
= sbitmap_alloc (num_nodes
);
1531 sbitmap must_follow
= sbitmap_alloc (num_nodes
);
1532 sbitmap tobe_scheduled
= sbitmap_alloc (num_nodes
);
1534 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
, DFA_HISTORY
);
1536 sbitmap_ones (tobe_scheduled
);
1537 sbitmap_zero (sched_nodes
);
1539 while ((! sbitmap_equal (tobe_scheduled
, sched_nodes
)
1540 || try_again_with_larger_ii
) && ii
< maxii
)
1543 bool unscheduled_nodes
= false;
1546 fprintf(dump_file
, "Starting with ii=%d\n", ii
);
1547 if (try_again_with_larger_ii
)
1549 try_again_with_larger_ii
= false;
1550 sbitmap_zero (sched_nodes
);
1553 for (i
= 0; i
< num_nodes
; i
++)
1555 int u
= nodes_order
[i
];
1556 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
1557 rtx insn
= u_node
->insn
;
1561 RESET_BIT (tobe_scheduled
, u
);
1565 if (JUMP_P (insn
)) /* Closing branch handled later. */
1567 RESET_BIT (tobe_scheduled
, u
);
1571 if (TEST_BIT (sched_nodes
, u
))
1574 /* Try to get non-empty scheduling window. */
1576 while (get_sched_window (ps
, nodes_order
, i
, sched_nodes
, ii
, &start
, &step
, &end
) < 0
1579 unscheduled_nodes
= true;
1580 if (TEST_BIT (NODE_PREDECESSORS (u_node
), nodes_order
[j
- 1])
1581 || TEST_BIT (NODE_SUCCESSORS (u_node
), nodes_order
[j
- 1]))
1583 ps_unschedule_node (ps
, &ps
->g
->nodes
[nodes_order
[j
- 1]]);
1584 RESET_BIT (sched_nodes
, nodes_order
[j
- 1]);
1590 /* ??? Try backtracking instead of immediately ii++? */
1592 try_again_with_larger_ii
= true;
1593 reset_partial_schedule (ps
, ii
);
1596 /* 2. Try scheduling u in window. */
1598 fprintf(dump_file
, "Trying to schedule node %d in (%d .. %d) step %d\n",
1599 u
, start
, end
, step
);
1601 /* use must_follow & must_precede bitmaps to determine order
1602 of nodes within the cycle. */
1603 sbitmap_zero (must_precede
);
1604 sbitmap_zero (must_follow
);
1605 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1606 if (TEST_BIT (sched_nodes
, e
->src
->cuid
)
1607 && e
->latency
== (ii
* e
->distance
)
1608 && start
== SCHED_TIME (e
->src
))
1609 SET_BIT (must_precede
, e
->src
->cuid
);
1611 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1612 if (TEST_BIT (sched_nodes
, e
->dest
->cuid
)
1613 && e
->latency
== (ii
* e
->distance
)
1614 && end
== SCHED_TIME (e
->dest
))
1615 SET_BIT (must_follow
, e
->dest
->cuid
);
1618 if ((step
> 0 && start
< end
) || (step
< 0 && start
> end
))
1619 for (c
= start
; c
!= end
; c
+= step
)
1623 psi
= ps_add_node_check_conflicts (ps
, u_node
, c
,
1629 SCHED_TIME (u_node
) = c
;
1630 SET_BIT (sched_nodes
, u
);
1633 fprintf(dump_file
, "Schedule in %d\n", c
);
1639 /* ??? Try backtracking instead of immediately ii++? */
1641 try_again_with_larger_ii
= true;
1642 reset_partial_schedule (ps
, ii
);
1645 if (unscheduled_nodes
)
1648 /* ??? If (success), check register pressure estimates. */
1649 } /* Continue with next node. */
1650 } /* While try_again_with_larger_ii. */
1652 sbitmap_free (sched_nodes
);
1656 free_partial_schedule (ps
);
1663 /* This page implements the algorithm for ordering the nodes of a DDG
1664 for modulo scheduling, activated through the
1665 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
1667 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
1668 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
1669 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
1670 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
1671 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
1672 #define DEPTH(x) (ASAP ((x)))
1674 typedef struct node_order_params
* nopa
;
1676 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
1677 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
1678 static nopa
calculate_order_params (ddg_ptr
, int mii
);
1679 static int find_max_asap (ddg_ptr
, sbitmap
);
1680 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
1681 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
1683 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
1685 struct node_order_params
1692 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
1694 check_nodes_order (int *node_order
, int num_nodes
)
1697 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1701 for (i
= 0; i
< num_nodes
; i
++)
1703 int u
= node_order
[i
];
1705 gcc_assert (u
< num_nodes
&& u
>= 0 && !TEST_BIT (tmp
, u
));
1713 /* Order the nodes of G for scheduling and pass the result in
1714 NODE_ORDER. Also set aux.count of each node to ASAP.
1715 Return the recMII for the given DDG. */
1717 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
)
1721 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
1723 nopa nops
= calculate_order_params (g
, mii
);
1725 order_nodes_of_sccs (sccs
, node_order
);
1727 if (sccs
->num_sccs
> 0)
1728 /* First SCC has the largest recurrence_length. */
1729 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
1731 /* Save ASAP before destroying node_order_params. */
1732 for (i
= 0; i
< g
->num_nodes
; i
++)
1734 ddg_node_ptr v
= &g
->nodes
[i
];
1735 v
->aux
.count
= ASAP (v
);
1739 free_ddg_all_sccs (sccs
);
1740 check_nodes_order (node_order
, g
->num_nodes
);
1746 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
1749 ddg_ptr g
= all_sccs
->ddg
;
1750 int num_nodes
= g
->num_nodes
;
1751 sbitmap prev_sccs
= sbitmap_alloc (num_nodes
);
1752 sbitmap on_path
= sbitmap_alloc (num_nodes
);
1753 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1754 sbitmap ones
= sbitmap_alloc (num_nodes
);
1756 sbitmap_zero (prev_sccs
);
1757 sbitmap_ones (ones
);
1759 /* Perfrom the node ordering starting from the SCC with the highest recMII.
1760 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
1761 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
1763 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
1765 /* Add nodes on paths from previous SCCs to the current SCC. */
1766 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
1767 sbitmap_a_or_b (tmp
, scc
->nodes
, on_path
);
1769 /* Add nodes on paths from the current SCC to previous SCCs. */
1770 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
1771 sbitmap_a_or_b (tmp
, tmp
, on_path
);
1773 /* Remove nodes of previous SCCs from current extended SCC. */
1774 sbitmap_difference (tmp
, tmp
, prev_sccs
);
1776 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
1777 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
1780 /* Handle the remaining nodes that do not belong to any scc. Each call
1781 to order_nodes_in_scc handles a single connected component. */
1782 while (pos
< g
->num_nodes
)
1784 sbitmap_difference (tmp
, ones
, prev_sccs
);
1785 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
1787 sbitmap_free (prev_sccs
);
1788 sbitmap_free (on_path
);
1790 sbitmap_free (ones
);
1793 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
1794 static struct node_order_params
*
1795 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
)
1799 int num_nodes
= g
->num_nodes
;
1801 /* Allocate a place to hold ordering params for each node in the DDG. */
1802 nopa node_order_params_arr
;
1804 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
1805 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
1806 sizeof (struct node_order_params
));
1808 /* Set the aux pointer of each node to point to its order_params structure. */
1809 for (u
= 0; u
< num_nodes
; u
++)
1810 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
1812 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
1813 calculate ASAP, ALAP, mobility, distance, and height for each node
1814 in the dependence (direct acyclic) graph. */
1816 /* We assume that the nodes in the array are in topological order. */
1819 for (u
= 0; u
< num_nodes
; u
++)
1821 ddg_node_ptr u_node
= &g
->nodes
[u
];
1824 for (e
= u_node
->in
; e
; e
= e
->next_in
)
1825 if (e
->distance
== 0)
1826 ASAP (u_node
) = MAX (ASAP (u_node
),
1827 ASAP (e
->src
) + e
->latency
);
1828 max_asap
= MAX (max_asap
, ASAP (u_node
));
1831 for (u
= num_nodes
- 1; u
> -1; u
--)
1833 ddg_node_ptr u_node
= &g
->nodes
[u
];
1835 ALAP (u_node
) = max_asap
;
1836 HEIGHT (u_node
) = 0;
1837 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1838 if (e
->distance
== 0)
1840 ALAP (u_node
) = MIN (ALAP (u_node
),
1841 ALAP (e
->dest
) - e
->latency
);
1842 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
1843 HEIGHT (e
->dest
) + e
->latency
);
1847 return node_order_params_arr
;
1851 find_max_asap (ddg_ptr g
, sbitmap nodes
)
1856 sbitmap_iterator sbi
;
1858 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
1860 ddg_node_ptr u_node
= &g
->nodes
[u
];
1862 if (max_asap
< ASAP (u_node
))
1864 max_asap
= ASAP (u_node
);
1872 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
1876 int min_mob
= INT_MAX
;
1878 sbitmap_iterator sbi
;
1880 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
1882 ddg_node_ptr u_node
= &g
->nodes
[u
];
1884 if (max_hv
< HEIGHT (u_node
))
1886 max_hv
= HEIGHT (u_node
);
1887 min_mob
= MOB (u_node
);
1890 else if ((max_hv
== HEIGHT (u_node
))
1891 && (min_mob
> MOB (u_node
)))
1893 min_mob
= MOB (u_node
);
1901 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
1905 int min_mob
= INT_MAX
;
1907 sbitmap_iterator sbi
;
1909 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
1911 ddg_node_ptr u_node
= &g
->nodes
[u
];
1913 if (max_dv
< DEPTH (u_node
))
1915 max_dv
= DEPTH (u_node
);
1916 min_mob
= MOB (u_node
);
1919 else if ((max_dv
== DEPTH (u_node
))
1920 && (min_mob
> MOB (u_node
)))
1922 min_mob
= MOB (u_node
);
1929 /* Places the nodes of SCC into the NODE_ORDER array starting
1930 at position POS, according to the SMS ordering algorithm.
1931 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
1932 the NODE_ORDER array, starting from position zero. */
1934 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
1935 int * node_order
, int pos
)
1937 enum sms_direction dir
;
1938 int num_nodes
= g
->num_nodes
;
1939 sbitmap workset
= sbitmap_alloc (num_nodes
);
1940 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1941 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
1942 sbitmap predecessors
= sbitmap_alloc (num_nodes
);
1943 sbitmap successors
= sbitmap_alloc (num_nodes
);
1945 sbitmap_zero (predecessors
);
1946 find_predecessors (predecessors
, g
, nodes_ordered
);
1948 sbitmap_zero (successors
);
1949 find_successors (successors
, g
, nodes_ordered
);
1952 if (sbitmap_a_and_b_cg (tmp
, predecessors
, scc
))
1954 sbitmap_copy (workset
, tmp
);
1957 else if (sbitmap_a_and_b_cg (tmp
, successors
, scc
))
1959 sbitmap_copy (workset
, tmp
);
1966 sbitmap_zero (workset
);
1967 if ((u
= find_max_asap (g
, scc
)) >= 0)
1968 SET_BIT (workset
, u
);
1972 sbitmap_zero (zero_bitmap
);
1973 while (!sbitmap_equal (workset
, zero_bitmap
))
1976 ddg_node_ptr v_node
;
1977 sbitmap v_node_preds
;
1978 sbitmap v_node_succs
;
1982 while (!sbitmap_equal (workset
, zero_bitmap
))
1984 v
= find_max_hv_min_mob (g
, workset
);
1985 v_node
= &g
->nodes
[v
];
1986 node_order
[pos
++] = v
;
1987 v_node_succs
= NODE_SUCCESSORS (v_node
);
1988 sbitmap_a_and_b (tmp
, v_node_succs
, scc
);
1990 /* Don't consider the already ordered successors again. */
1991 sbitmap_difference (tmp
, tmp
, nodes_ordered
);
1992 sbitmap_a_or_b (workset
, workset
, tmp
);
1993 RESET_BIT (workset
, v
);
1994 SET_BIT (nodes_ordered
, v
);
1997 sbitmap_zero (predecessors
);
1998 find_predecessors (predecessors
, g
, nodes_ordered
);
1999 sbitmap_a_and_b (workset
, predecessors
, scc
);
2003 while (!sbitmap_equal (workset
, zero_bitmap
))
2005 v
= find_max_dv_min_mob (g
, workset
);
2006 v_node
= &g
->nodes
[v
];
2007 node_order
[pos
++] = v
;
2008 v_node_preds
= NODE_PREDECESSORS (v_node
);
2009 sbitmap_a_and_b (tmp
, v_node_preds
, scc
);
2011 /* Don't consider the already ordered predecessors again. */
2012 sbitmap_difference (tmp
, tmp
, nodes_ordered
);
2013 sbitmap_a_or_b (workset
, workset
, tmp
);
2014 RESET_BIT (workset
, v
);
2015 SET_BIT (nodes_ordered
, v
);
2018 sbitmap_zero (successors
);
2019 find_successors (successors
, g
, nodes_ordered
);
2020 sbitmap_a_and_b (workset
, successors
, scc
);
2024 sbitmap_free (workset
);
2025 sbitmap_free (zero_bitmap
);
2026 sbitmap_free (predecessors
);
2027 sbitmap_free (successors
);
2032 /* This page contains functions for manipulating partial-schedules during
2033 modulo scheduling. */
2035 /* Create a partial schedule and allocate a memory to hold II rows. */
2037 static partial_schedule_ptr
2038 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2040 partial_schedule_ptr ps
= (partial_schedule_ptr
)
2041 xmalloc (sizeof (struct partial_schedule
));
2042 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2044 ps
->history
= history
;
2045 ps
->min_cycle
= INT_MAX
;
2046 ps
->max_cycle
= INT_MIN
;
2052 /* Free the PS_INSNs in rows array of the given partial schedule.
2053 ??? Consider caching the PS_INSN's. */
2055 free_ps_insns (partial_schedule_ptr ps
)
2059 for (i
= 0; i
< ps
->ii
; i
++)
2063 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2066 ps
->rows
[i
] = ps_insn
;
2072 /* Free all the memory allocated to the partial schedule. */
2075 free_partial_schedule (partial_schedule_ptr ps
)
2084 /* Clear the rows array with its PS_INSNs, and create a new one with
2088 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2093 if (new_ii
== ps
->ii
)
2095 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2096 * sizeof (ps_insn_ptr
));
2097 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2099 ps
->min_cycle
= INT_MAX
;
2100 ps
->max_cycle
= INT_MIN
;
2103 /* Prints the partial schedule as an ii rows array, for each rows
2104 print the ids of the insns in it. */
2106 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2110 for (i
= 0; i
< ps
->ii
; i
++)
2112 ps_insn_ptr ps_i
= ps
->rows
[i
];
2114 fprintf (dump
, "\n[CYCLE %d ]: ", i
);
2117 fprintf (dump
, "%d, ",
2118 INSN_UID (ps_i
->node
->insn
));
2119 ps_i
= ps_i
->next_in_row
;
2124 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2126 create_ps_insn (ddg_node_ptr node
, int rest_count
, int cycle
)
2128 ps_insn_ptr ps_i
= xmalloc (sizeof (struct ps_insn
));
2131 ps_i
->next_in_row
= NULL
;
2132 ps_i
->prev_in_row
= NULL
;
2133 ps_i
->row_rest_count
= rest_count
;
2134 ps_i
->cycle
= cycle
;
2140 /* Removes the given PS_INSN from the partial schedule. Returns false if the
2141 node is not found in the partial schedule, else returns true. */
2143 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2150 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2151 if (! ps_i
->prev_in_row
)
2153 if (ps_i
!= ps
->rows
[row
])
2156 ps
->rows
[row
] = ps_i
->next_in_row
;
2158 ps
->rows
[row
]->prev_in_row
= NULL
;
2162 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
2163 if (ps_i
->next_in_row
)
2164 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
2170 /* Unlike what literature describes for modulo scheduling (which focuses
2171 on VLIW machines) the order of the instructions inside a cycle is
2172 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2173 where the current instruction should go relative to the already
2174 scheduled instructions in the given cycle. Go over these
2175 instructions and find the first possible column to put it in. */
2177 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2178 sbitmap must_precede
, sbitmap must_follow
)
2180 ps_insn_ptr next_ps_i
;
2181 ps_insn_ptr first_must_follow
= NULL
;
2182 ps_insn_ptr last_must_precede
= NULL
;
2188 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2190 /* Find the first must follow and the last must precede
2191 and insert the node immediately after the must precede
2192 but make sure that it there is no must follow after it. */
2193 for (next_ps_i
= ps
->rows
[row
];
2195 next_ps_i
= next_ps_i
->next_in_row
)
2197 if (TEST_BIT (must_follow
, next_ps_i
->node
->cuid
)
2198 && ! first_must_follow
)
2199 first_must_follow
= next_ps_i
;
2200 if (TEST_BIT (must_precede
, next_ps_i
->node
->cuid
))
2202 /* If we have already met a node that must follow, then
2203 there is no possible column. */
2204 if (first_must_follow
)
2207 last_must_precede
= next_ps_i
;
2211 /* Now insert the node after INSERT_AFTER_PSI. */
2213 if (! last_must_precede
)
2215 ps_i
->next_in_row
= ps
->rows
[row
];
2216 ps_i
->prev_in_row
= NULL
;
2217 if (ps_i
->next_in_row
)
2218 ps_i
->next_in_row
->prev_in_row
= ps_i
;
2219 ps
->rows
[row
] = ps_i
;
2223 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
2224 last_must_precede
->next_in_row
= ps_i
;
2225 ps_i
->prev_in_row
= last_must_precede
;
2226 if (ps_i
->next_in_row
)
2227 ps_i
->next_in_row
->prev_in_row
= ps_i
;
2233 /* Advances the PS_INSN one column in its current row; returns false
2234 in failure and true in success. Bit N is set in MUST_FOLLOW if
2235 the node with cuid N must be come after the node pointed to by
2236 PS_I when scheduled in the same cycle. */
2238 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2239 sbitmap must_follow
)
2241 ps_insn_ptr prev
, next
;
2243 ddg_node_ptr next_node
;
2248 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2250 if (! ps_i
->next_in_row
)
2253 next_node
= ps_i
->next_in_row
->node
;
2255 /* Check if next_in_row is dependent on ps_i, both having same sched
2256 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
2257 if (TEST_BIT (must_follow
, next_node
->cuid
))
2260 /* Advance PS_I over its next_in_row in the doubly linked list. */
2261 prev
= ps_i
->prev_in_row
;
2262 next
= ps_i
->next_in_row
;
2264 if (ps_i
== ps
->rows
[row
])
2265 ps
->rows
[row
] = next
;
2267 ps_i
->next_in_row
= next
->next_in_row
;
2269 if (next
->next_in_row
)
2270 next
->next_in_row
->prev_in_row
= ps_i
;
2272 next
->next_in_row
= ps_i
;
2273 ps_i
->prev_in_row
= next
;
2275 next
->prev_in_row
= prev
;
2277 prev
->next_in_row
= next
;
2282 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
2283 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
2284 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
2285 before/after (respectively) the node pointed to by PS_I when scheduled
2286 in the same cycle. */
2288 add_node_to_ps (partial_schedule_ptr ps
, ddg_node_ptr node
, int cycle
,
2289 sbitmap must_precede
, sbitmap must_follow
)
2293 int row
= SMODULO (cycle
, ps
->ii
);
2296 && ps
->rows
[row
]->row_rest_count
>= issue_rate
)
2300 rest_count
+= ps
->rows
[row
]->row_rest_count
;
2302 ps_i
= create_ps_insn (node
, rest_count
, cycle
);
2304 /* Finds and inserts PS_I according to MUST_FOLLOW and
2306 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
2315 /* Advance time one cycle. Assumes DFA is being used. */
2317 advance_one_cycle (void)
2319 if (targetm
.sched
.dfa_pre_cycle_insn
)
2320 state_transition (curr_state
,
2321 targetm
.sched
.dfa_pre_cycle_insn ());
2323 state_transition (curr_state
, NULL
);
2325 if (targetm
.sched
.dfa_post_cycle_insn
)
2326 state_transition (curr_state
,
2327 targetm
.sched
.dfa_post_cycle_insn ());
2330 /* Given the kernel of a loop (from FIRST_INSN to LAST_INSN), finds
2331 the number of cycles according to DFA that the kernel fits in,
2332 we use this to check if we done well with SMS after we add
2333 register moves. In some cases register moves overhead makes
2334 it even worse than the original loop. We want SMS to be performed
2335 when it gives less cycles after register moves are added. */
2337 kernel_number_of_cycles (rtx first_insn
, rtx last_insn
)
2341 int can_issue_more
= issue_rate
;
2343 state_reset (curr_state
);
2345 for (insn
= first_insn
;
2346 insn
!= NULL_RTX
&& insn
!= last_insn
;
2347 insn
= NEXT_INSN (insn
))
2349 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
2352 /* Check if there is room for the current insn. */
2353 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
2356 advance_one_cycle ();
2357 can_issue_more
= issue_rate
;
2360 /* Update the DFA state and return with failure if the DFA found
2361 recource conflicts. */
2362 if (state_transition (curr_state
, insn
) >= 0)
2365 advance_one_cycle ();
2366 can_issue_more
= issue_rate
;
2369 if (targetm
.sched
.variable_issue
)
2371 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
2372 insn
, can_issue_more
);
2373 /* A naked CLOBBER or USE generates no instruction, so don't
2374 let them consume issue slots. */
2375 else if (GET_CODE (PATTERN (insn
)) != USE
2376 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2382 /* Checks if PS has resource conflicts according to DFA, starting from
2383 FROM cycle to TO cycle; returns true if there are conflicts and false
2384 if there are no conflicts. Assumes DFA is being used. */
2386 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
2390 state_reset (curr_state
);
2392 for (cycle
= from
; cycle
<= to
; cycle
++)
2394 ps_insn_ptr crr_insn
;
2395 /* Holds the remaining issue slots in the current row. */
2396 int can_issue_more
= issue_rate
;
2398 /* Walk through the DFA for the current row. */
2399 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
2401 crr_insn
= crr_insn
->next_in_row
)
2403 rtx insn
= crr_insn
->node
->insn
;
2408 /* Check if there is room for the current insn. */
2409 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
2412 /* Update the DFA state and return with failure if the DFA found
2413 recource conflicts. */
2414 if (state_transition (curr_state
, insn
) >= 0)
2417 if (targetm
.sched
.variable_issue
)
2419 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
2420 insn
, can_issue_more
);
2421 /* A naked CLOBBER or USE generates no instruction, so don't
2422 let them consume issue slots. */
2423 else if (GET_CODE (PATTERN (insn
)) != USE
2424 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2428 /* Advance the DFA to the next cycle. */
2429 advance_one_cycle ();
2434 /* Checks if the given node causes resource conflicts when added to PS at
2435 cycle C. If not the node is added to PS and returned; otherwise zero
2436 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
2437 cuid N must be come before/after (respectively) the node pointed to by
2438 PS_I when scheduled in the same cycle. */
2440 ps_add_node_check_conflicts (partial_schedule_ptr ps
, ddg_node_ptr n
,
2441 int c
, sbitmap must_precede
,
2442 sbitmap must_follow
)
2444 int has_conflicts
= 0;
2447 /* First add the node to the PS, if this succeeds check for
2448 conflicts, trying different issue slots in the same row. */
2449 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
2450 return NULL
; /* Failed to insert the node at the given cycle. */
2452 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
2454 && ps_has_conflicts (ps
,
2458 /* Try different issue slots to find one that the given node can be
2459 scheduled in without conflicts. */
2460 while (has_conflicts
)
2462 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
2464 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
2466 && ps_has_conflicts (ps
,
2473 remove_node_from_ps (ps
, ps_i
);
2477 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
2478 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
2482 /* Rotate the rows of PS such that insns scheduled at time
2483 START_CYCLE will appear in row 0. Updates max/min_cycles. */
2485 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
2487 int i
, row
, backward_rotates
;
2488 int last_row
= ps
->ii
- 1;
2490 if (start_cycle
== 0)
2493 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
2495 /* Revisit later and optimize this into a single loop. */
2496 for (i
= 0; i
< backward_rotates
; i
++)
2498 ps_insn_ptr first_row
= ps
->rows
[0];
2500 for (row
= 0; row
< last_row
; row
++)
2501 ps
->rows
[row
] = ps
->rows
[row
+1];
2503 ps
->rows
[last_row
] = first_row
;
2506 ps
->max_cycle
-= start_cycle
;
2507 ps
->min_cycle
-= start_cycle
;
2510 /* Remove the node N from the partial schedule PS; because we restart the DFA
2511 each time we want to check for resource conflicts; this is equivalent to
2512 unscheduling the node N. */
2514 ps_unschedule_node (partial_schedule_ptr ps
, ddg_node_ptr n
)
2517 int row
= SMODULO (SCHED_TIME (n
), ps
->ii
);
2519 if (row
< 0 || row
> ps
->ii
)
2522 for (ps_i
= ps
->rows
[row
];
2523 ps_i
&& ps_i
->node
!= n
;
2524 ps_i
= ps_i
->next_in_row
);
2528 return remove_node_from_ps (ps
, ps_i
);
2530 #endif /* INSN_SCHEDULING */
2533 gate_handle_sms (void)
2535 return (optimize
> 0 && flag_modulo_sched
);
2539 /* Run instruction scheduler. */
2540 /* Perform SMS module scheduling. */
2542 rest_of_handle_sms (void)
2544 #ifdef INSN_SCHEDULING
2547 /* We want to be able to create new pseudos. */
2549 /* Collect loop information to be used in SMS. */
2550 cfg_layout_initialize (CLEANUP_UPDATE_LIFE
);
2551 sms_schedule (dump_file
);
2553 /* Update the life information, because we add pseudos. */
2554 max_regno
= max_reg_num ();
2555 allocate_reg_info (max_regno
, FALSE
, FALSE
);
2556 update_life_info (NULL
, UPDATE_LIFE_GLOBAL_RM_NOTES
,
2559 | PROP_KILL_DEAD_CODE
2560 | PROP_SCAN_DEAD_CODE
));
2564 /* Finalize layout changes. */
2566 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2567 bb
->aux
= bb
->next_bb
;
2568 cfg_layout_finalize ();
2569 free_dominance_info (CDI_DOMINATORS
);
2570 #endif /* INSN_SCHEDULING */
2573 struct tree_opt_pass pass_sms
=
2576 gate_handle_sms
, /* gate */
2577 rest_of_handle_sms
, /* execute */
2580 0, /* static_pass_number */
2582 0, /* properties_required */
2583 0, /* properties_provided */
2584 0, /* properties_destroyed */
2585 0, /* todo_flags_start */
2587 TODO_ggc_collect
, /* todo_flags_finish */