1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004, 2005
3 Free Software Foundation, Inc.
4 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
26 #include "coretypes.h"
31 #include "hard-reg-set.h"
35 #include "insn-config.h"
36 #include "insn-attr.h"
40 #include "sched-int.h"
42 #include "cfglayout.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 partial_schedule_ptr
create_partial_schedule (int ii
, ddg_ptr
, int history
);
159 void free_partial_schedule (partial_schedule_ptr
);
160 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 /* For printing statistics. */
183 static FILE *stats_file
;
185 static int sms_order_nodes (ddg_ptr
, int, int * result
);
186 static void set_node_sched_params (ddg_ptr
);
187 static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr
, int, int,
189 static void permute_partial_schedule (partial_schedule_ptr ps
, rtx last
);
190 static void generate_prolog_epilog (partial_schedule_ptr
,struct loop
* loop
, rtx
);
191 static void duplicate_insns_of_cycles (partial_schedule_ptr ps
,
192 int from_stage
, int to_stage
,
195 #define SCHED_ASAP(x) (((node_sched_params_ptr)(x)->aux.info)->asap)
196 #define SCHED_TIME(x) (((node_sched_params_ptr)(x)->aux.info)->time)
197 #define SCHED_FIRST_REG_MOVE(x) \
198 (((node_sched_params_ptr)(x)->aux.info)->first_reg_move)
199 #define SCHED_NREG_MOVES(x) \
200 (((node_sched_params_ptr)(x)->aux.info)->nreg_moves)
201 #define SCHED_ROW(x) (((node_sched_params_ptr)(x)->aux.info)->row)
202 #define SCHED_STAGE(x) (((node_sched_params_ptr)(x)->aux.info)->stage)
203 #define SCHED_COLUMN(x) (((node_sched_params_ptr)(x)->aux.info)->column)
205 /* The scheduling parameters held for each node. */
206 typedef struct node_sched_params
208 int asap
; /* A lower-bound on the absolute scheduling cycle. */
209 int time
; /* The absolute scheduling cycle (time >= asap). */
211 /* The following field (first_reg_move) is a pointer to the first
212 register-move instruction added to handle the modulo-variable-expansion
213 of the register defined by this node. This register-move copies the
214 original register defined by the node. */
217 /* The number of register-move instructions added, immediately preceding
221 int row
; /* Holds time % ii. */
222 int stage
; /* Holds time / ii. */
224 /* The column of a node inside the ps. If nodes u, v are on the same row,
225 u will precede v if column (u) < column (v). */
227 } *node_sched_params_ptr
;
230 /* The following three functions are copied from the current scheduler
231 code in order to use sched_analyze() for computing the dependencies.
232 They are used when initializing the sched_info structure. */
234 sms_print_insn (rtx insn
, int aligned ATTRIBUTE_UNUSED
)
238 sprintf (tmp
, "i%4d", INSN_UID (insn
));
243 contributes_to_priority (rtx next
, rtx insn
)
245 return BLOCK_NUM (next
) == BLOCK_NUM (insn
);
249 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
250 regset cond_exec ATTRIBUTE_UNUSED
,
251 regset used ATTRIBUTE_UNUSED
,
252 regset set ATTRIBUTE_UNUSED
)
256 static struct sched_info sms_sched_info
=
264 contributes_to_priority
,
265 compute_jump_reg_dependencies
,
272 /* Return the register decremented and tested in INSN,
273 or zero if it is not a decrement-and-branch insn. */
276 doloop_register_get (rtx insn
)
278 rtx pattern
, reg
, condition
;
283 pattern
= PATTERN (insn
);
284 condition
= doloop_condition_get (pattern
);
288 if (REG_P (XEXP (condition
, 0)))
289 reg
= XEXP (condition
, 0);
290 else if (GET_CODE (XEXP (condition
, 0)) == PLUS
291 && REG_P (XEXP (XEXP (condition
, 0), 0)))
292 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_block_head_tail (pre_header
->index
, &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 * dump_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 (dump_file
, "Node %d:\n", i
);
384 fprintf (dump_file
, " asap = %d:\n", nsp
->asap
);
385 fprintf (dump_file
, " time = %d:\n", nsp
->time
);
386 fprintf (dump_file
, " nreg_moves = %d:\n", nsp
->nreg_moves
);
387 for (j
= 0; j
< nsp
->nreg_moves
; j
++)
389 fprintf (dump_file
, " reg_move = ");
390 print_rtl_single (dump_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
++)
499 rtx new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
500 rtx reg_move
= gen_move_insn (new_reg
, prev_reg
);
502 add_insn_before (reg_move
, last_reg_move
);
503 last_reg_move
= reg_move
;
505 if (!SCHED_FIRST_REG_MOVE (u
))
506 SCHED_FIRST_REG_MOVE (u
) = reg_move
;
508 EXECUTE_IF_SET_IN_SBITMAP (uses_of_defs
[i_reg_move
], 0, i_use
,
510 struct undo_replace_buff_elem
*rep
;
512 rep
= (struct undo_replace_buff_elem
*)
513 xcalloc (1, sizeof (struct undo_replace_buff_elem
));
514 rep
->insn
= g
->nodes
[i_use
].insn
;
515 rep
->orig_reg
= old_reg
;
516 rep
->new_reg
= new_reg
;
518 if (! reg_move_replaces
)
519 reg_move_replaces
= rep
;
522 rep
->next
= reg_move_replaces
;
523 reg_move_replaces
= rep
;
526 replace_rtx (g
->nodes
[i_use
].insn
, old_reg
, new_reg
);
532 return reg_move_replaces
;
535 /* We call this when we want to undo the SMS schedule for a given loop.
536 One of the things that we do is to delete the register moves generated
537 for the sake of SMS; this function deletes the register move instructions
538 recorded in the undo buffer. */
540 undo_generate_reg_moves (partial_schedule_ptr ps
,
541 struct undo_replace_buff_elem
*reg_move_replaces
)
545 for (i
= 0; i
< ps
->g
->num_nodes
; i
++)
547 ddg_node_ptr u
= &ps
->g
->nodes
[i
];
549 rtx crr
= SCHED_FIRST_REG_MOVE (u
);
551 for (j
= 0; j
< SCHED_NREG_MOVES (u
); j
++)
553 prev
= PREV_INSN (crr
);
557 SCHED_FIRST_REG_MOVE (u
) = NULL_RTX
;
560 while (reg_move_replaces
)
562 struct undo_replace_buff_elem
*rep
= reg_move_replaces
;
564 reg_move_replaces
= reg_move_replaces
->next
;
565 replace_rtx (rep
->insn
, rep
->new_reg
, rep
->orig_reg
);
569 /* Free memory allocated for the undo buffer. */
571 free_undo_replace_buff (struct undo_replace_buff_elem
*reg_move_replaces
)
574 while (reg_move_replaces
)
576 struct undo_replace_buff_elem
*rep
= reg_move_replaces
;
578 reg_move_replaces
= reg_move_replaces
->next
;
583 /* Bump the SCHED_TIMEs of all nodes to start from zero. Set the values
584 of SCHED_ROW and SCHED_STAGE. */
586 normalize_sched_times (partial_schedule_ptr ps
)
590 int amount
= PS_MIN_CYCLE (ps
);
593 /* Don't include the closing branch assuming that it is the last node. */
594 for (i
= 0; i
< g
->num_nodes
- 1; i
++)
596 ddg_node_ptr u
= &g
->nodes
[i
];
597 int normalized_time
= SCHED_TIME (u
) - amount
;
599 gcc_assert (normalized_time
>= 0);
601 SCHED_TIME (u
) = normalized_time
;
602 SCHED_ROW (u
) = normalized_time
% ii
;
603 SCHED_STAGE (u
) = normalized_time
/ ii
;
607 /* Set SCHED_COLUMN of each node according to its position in PS. */
609 set_columns_for_ps (partial_schedule_ptr ps
)
613 for (row
= 0; row
< ps
->ii
; row
++)
615 ps_insn_ptr cur_insn
= ps
->rows
[row
];
618 for (; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
619 SCHED_COLUMN (cur_insn
->node
) = column
++;
623 /* Permute the insns according to their order in PS, from row 0 to
624 row ii-1, and position them right before LAST. This schedules
625 the insns of the loop kernel. */
627 permute_partial_schedule (partial_schedule_ptr ps
, rtx last
)
633 for (row
= 0; row
< ii
; row
++)
634 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
635 if (PREV_INSN (last
) != ps_ij
->node
->insn
)
636 reorder_insns_nobb (ps_ij
->node
->first_note
, ps_ij
->node
->insn
,
640 /* As part of undoing SMS we return to the original ordering of the
641 instructions inside the loop kernel. Given the partial schedule PS, this
642 function returns the ordering of the instruction according to their CUID
643 in the DDG (PS->G), which is the original order of the instruction before
646 undo_permute_partial_schedule (partial_schedule_ptr ps
, rtx last
)
650 for (i
= 0 ; i
< ps
->g
->num_nodes
; i
++)
651 if (last
== ps
->g
->nodes
[i
].insn
652 || last
== ps
->g
->nodes
[i
].first_note
)
654 else if (PREV_INSN (last
) != ps
->g
->nodes
[i
].insn
)
655 reorder_insns_nobb (ps
->g
->nodes
[i
].first_note
, ps
->g
->nodes
[i
].insn
,
659 /* Used to generate the prologue & epilogue. Duplicate the subset of
660 nodes whose stages are between FROM_STAGE and TO_STAGE (inclusive
661 of both), together with a prefix/suffix of their reg_moves. */
663 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
664 int to_stage
, int for_prolog
)
669 for (row
= 0; row
< ps
->ii
; row
++)
670 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
672 ddg_node_ptr u_node
= ps_ij
->node
;
674 rtx reg_move
= NULL_RTX
;
678 /* SCHED_STAGE (u_node) >= from_stage == 0. Generate increasing
679 number of reg_moves starting with the second occurrence of
680 u_node, which is generated if its SCHED_STAGE <= to_stage. */
681 i_reg_moves
= to_stage
- SCHED_STAGE (u_node
) + 1;
682 i_reg_moves
= MAX (i_reg_moves
, 0);
683 i_reg_moves
= MIN (i_reg_moves
, SCHED_NREG_MOVES (u_node
));
685 /* The reg_moves start from the *first* reg_move backwards. */
688 reg_move
= SCHED_FIRST_REG_MOVE (u_node
);
689 for (j
= 1; j
< i_reg_moves
; j
++)
690 reg_move
= PREV_INSN (reg_move
);
693 else /* It's for the epilog. */
695 /* SCHED_STAGE (u_node) <= to_stage. Generate all reg_moves,
696 starting to decrease one stage after u_node no longer occurs;
697 that is, generate all reg_moves until
698 SCHED_STAGE (u_node) == from_stage - 1. */
699 i_reg_moves
= SCHED_NREG_MOVES (u_node
)
700 - (from_stage
- SCHED_STAGE (u_node
) - 1);
701 i_reg_moves
= MAX (i_reg_moves
, 0);
702 i_reg_moves
= MIN (i_reg_moves
, SCHED_NREG_MOVES (u_node
));
704 /* The reg_moves start from the *last* reg_move forwards. */
707 reg_move
= SCHED_FIRST_REG_MOVE (u_node
);
708 for (j
= 1; j
< SCHED_NREG_MOVES (u_node
); j
++)
709 reg_move
= PREV_INSN (reg_move
);
713 for (j
= 0; j
< i_reg_moves
; j
++, reg_move
= NEXT_INSN (reg_move
))
714 emit_insn (copy_rtx (PATTERN (reg_move
)));
715 if (SCHED_STAGE (u_node
) >= from_stage
716 && SCHED_STAGE (u_node
) <= to_stage
)
717 duplicate_insn_chain (u_node
->first_note
, u_node
->insn
);
722 /* Generate the instructions (including reg_moves) for prolog & epilog. */
724 generate_prolog_epilog (partial_schedule_ptr ps
, struct loop
* loop
, rtx count_reg
)
727 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
730 /* Generate the prolog, inserting its insns on the loop-entry edge. */
734 /* Generate a subtract instruction at the beginning of the prolog to
735 adjust the loop count by STAGE_COUNT. */
736 emit_insn (gen_sub2_insn (count_reg
, GEN_INT (last_stage
)));
738 for (i
= 0; i
< last_stage
; i
++)
739 duplicate_insns_of_cycles (ps
, 0, i
, 1);
741 /* Put the prolog , on the one and only entry edge. */
742 e
= loop_preheader_edge (loop
);
743 loop_split_edge_with(e
, get_insns());
747 /* Generate the epilog, inserting its insns on the loop-exit edge. */
750 for (i
= 0; i
< last_stage
; i
++)
751 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, 0);
753 /* Put the epilogue on the one and only one exit edge. */
754 gcc_assert (loop
->single_exit
);
755 e
= loop
->single_exit
;
756 loop_split_edge_with(e
, get_insns());
760 /* Return the line note insn preceding INSN, for debugging. Taken from
763 find_line_note (rtx insn
)
765 for (; insn
; insn
= PREV_INSN (insn
))
767 && NOTE_LINE_NUMBER (insn
) >= 0)
773 /* Return true if all the BBs of the loop are empty except the
776 loop_single_full_bb_p (struct loop
*loop
)
779 basic_block
*bbs
= get_loop_body (loop
);
781 for (i
= 0; i
< loop
->num_nodes
; i
++)
784 bool empty_bb
= true;
786 if (bbs
[i
] == loop
->header
)
789 /* Make sure that basic blocks other than the header
790 have only notes labels or jumps. */
791 get_block_head_tail (bbs
[i
]->index
, &head
, &tail
);
792 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
794 if (NOTE_P (head
) || LABEL_P (head
)
795 || (INSN_P (head
) && JUMP_P (head
)))
811 /* A simple loop from SMS point of view; it is a loop that is composed of
812 either a single basic block or two BBs - a header and a latch. */
813 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
814 && (EDGE_COUNT (loop->latch->preds) == 1) \
815 && (EDGE_COUNT (loop->latch->succs) == 1))
817 /* Return true if the loop is in its canonical form and false if not.
818 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
820 loop_canon_p (struct loop
*loop
, FILE *dump_file
)
823 if (loop
->inner
|| ! loop
->outer
)
826 if (!loop
->single_exit
)
830 rtx line_note
= find_line_note (BB_END (loop
->header
));
832 fprintf (dump_file
, "SMS loop many exits ");
835 expanded_location xloc
;
836 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
837 fprintf (stats_file
, " %s %d (file, line)\n",
838 xloc
.file
, xloc
.line
);
844 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
848 rtx line_note
= find_line_note (BB_END (loop
->header
));
850 fprintf (dump_file
, "SMS loop many BBs. ");
853 expanded_location xloc
;
854 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
855 fprintf (stats_file
, " %s %d (file, line)\n",
856 xloc
.file
, xloc
.line
);
865 /* If there are more than one entry for the loop,
866 make it one by splitting the first entry edge and
867 redirecting the others to the new BB. */
869 canon_loop (struct loop
*loop
)
874 /* Avoid annoying special cases of edges going to exit
876 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR
->preds
)
877 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
878 loop_split_edge_with (e
, NULL_RTX
);
880 if (loop
->latch
== loop
->header
881 || EDGE_COUNT (loop
->latch
->succs
) > 1)
883 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
884 if (e
->src
== loop
->latch
)
886 loop_split_edge_with (e
, NULL_RTX
);
890 /* Build the loop information without loop
891 canonization, the loop canonization will
892 be performed if the loop is SMSable. */
893 static struct loops
*
894 build_loops_structure (FILE *dumpfile
)
896 struct loops
*loops
= xcalloc (1, sizeof (struct loops
));
898 /* Find the loops. */
900 if (flow_loops_find (loops
) <= 1)
903 flow_loops_free (loops
);
909 /* Not going to update these. */
910 free (loops
->cfg
.rc_order
);
911 loops
->cfg
.rc_order
= NULL
;
912 free (loops
->cfg
.dfs_order
);
913 loops
->cfg
.dfs_order
= NULL
;
915 create_preheaders (loops
, CP_SIMPLE_PREHEADERS
);
916 mark_single_exit_loops (loops
);
918 flow_loops_dump (loops
, dumpfile
, NULL
, 1);
920 #ifdef ENABLE_CHECKING
921 verify_dominators (CDI_DOMINATORS
);
922 verify_loop_structure (loops
);
928 /* Main entry point, perform SMS scheduling on the loops of the function
929 that consist of single basic blocks. */
931 sms_schedule (FILE *dump_file
)
933 static int passes
= 0;
938 unsigned i
,num_loops
;
939 partial_schedule_ptr ps
;
942 basic_block bb
= NULL
;
943 /* vars to the versioning only if needed*/
945 basic_block condition_bb
= NULL
;
947 gcov_type trip_count
= 0;
949 if (! (loops
= build_loops_structure (dump_file
)))
950 return; /* There is no loops to schedule. */
953 stats_file
= dump_file
;
955 /* Initialize issue_rate. */
956 if (targetm
.sched
.issue_rate
)
958 int temp
= reload_completed
;
960 reload_completed
= 1;
961 issue_rate
= targetm
.sched
.issue_rate ();
962 reload_completed
= temp
;
967 /* Initialize the scheduler. */
968 current_sched_info
= &sms_sched_info
;
971 /* Init Data Flow analysis, to be used in interloop dep calculation. */
973 df_analyze (df
, 0, DF_ALL
);
975 /* Allocate memory to hold the DDG array one entry for each loop.
976 We use loop->num as index into this array. */
977 g_arr
= xcalloc (loops
->num
, sizeof (ddg_ptr
));
980 /* Build DDGs for all the relevant loops and hold them in G_ARR
981 indexed by the loop index. */
982 for (i
= 0; i
< loops
->num
; i
++)
986 struct loop
*loop
= loops
->parray
[i
];
989 if ((passes
++ > MAX_SMS_LOOP_NUMBER
) && (MAX_SMS_LOOP_NUMBER
!= -1))
992 fprintf (dump_file
, "SMS reached MAX_PASSES... \n");
997 if (! loop_canon_p (loop
, dump_file
))
1000 if (! loop_single_full_bb_p (loop
))
1005 get_block_head_tail (bb
->index
, &head
, &tail
);
1006 latch_edge
= loop_latch_edge (loop
);
1007 gcc_assert (loop
->single_exit
);
1008 if (loop
->single_exit
->count
)
1009 trip_count
= latch_edge
->count
/ loop
->single_exit
->count
;
1011 /* Perfrom SMS only on loops that their average count is above threshold. */
1013 if ( latch_edge
->count
1014 && (latch_edge
->count
< loop
->single_exit
->count
* SMS_LOOP_AVERAGE_COUNT_THRESHOLD
))
1018 rtx line_note
= find_line_note (tail
);
1022 expanded_location xloc
;
1023 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
1024 fprintf (stats_file
, "SMS bb %s %d (file, line)\n",
1025 xloc
.file
, xloc
.line
);
1027 fprintf (stats_file
, "SMS single-bb-loop\n");
1028 if (profile_info
&& flag_branch_probabilities
)
1030 fprintf (stats_file
, "SMS loop-count ");
1031 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1032 (HOST_WIDEST_INT
) bb
->count
);
1033 fprintf (stats_file
, "\n");
1034 fprintf (stats_file
, "SMS trip-count ");
1035 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1036 (HOST_WIDEST_INT
) trip_count
);
1037 fprintf (stats_file
, "\n");
1038 fprintf (stats_file
, "SMS profile-sum-max ");
1039 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1040 (HOST_WIDEST_INT
) profile_info
->sum_max
);
1041 fprintf (stats_file
, "\n");
1047 /* Make sure this is a doloop. */
1048 if ( !(count_reg
= doloop_register_get (tail
)))
1051 /* Don't handle BBs with calls or barriers, or !single_set insns. */
1052 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1055 || (INSN_P (insn
) && !JUMP_P (insn
)
1056 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
1059 if (insn
!= NEXT_INSN (tail
))
1064 fprintf (stats_file
, "SMS loop-with-call\n");
1065 else if (BARRIER_P (insn
))
1066 fprintf (stats_file
, "SMS loop-with-barrier\n");
1068 fprintf (stats_file
, "SMS loop-with-not-single-set\n");
1069 print_rtl_single (stats_file
, insn
);
1075 if (! (g
= create_ddg (bb
, df
, 0)))
1078 fprintf (stats_file
, "SMS doloop\n");
1085 /* Release Data Flow analysis data structures. */
1088 /* We don't want to perform SMS on new loops - created by versioning. */
1089 num_loops
= loops
->num
;
1090 /* Go over the built DDGs and perfrom SMS for each one of them. */
1091 for (i
= 0; i
< num_loops
; i
++)
1094 rtx count_reg
, count_init
;
1096 unsigned stage_count
= 0;
1097 HOST_WIDEST_INT loop_count
= 0;
1098 struct loop
*loop
= loops
->parray
[i
];
1100 if (! (g
= g_arr
[i
]))
1104 print_ddg (dump_file
, g
);
1106 get_block_head_tail (loop
->header
->index
, &head
, &tail
);
1108 latch_edge
= loop_latch_edge (loop
);
1109 gcc_assert (loop
->single_exit
);
1110 if (loop
->single_exit
->count
)
1111 trip_count
= latch_edge
->count
/ loop
->single_exit
->count
;
1115 rtx line_note
= find_line_note (tail
);
1119 expanded_location xloc
;
1120 NOTE_EXPANDED_LOCATION (xloc
, line_note
);
1121 fprintf (stats_file
, "SMS bb %s %d (file, line)\n",
1122 xloc
.file
, xloc
.line
);
1124 fprintf (stats_file
, "SMS single-bb-loop\n");
1125 if (profile_info
&& flag_branch_probabilities
)
1127 fprintf (stats_file
, "SMS loop-count ");
1128 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1129 (HOST_WIDEST_INT
) bb
->count
);
1130 fprintf (stats_file
, "\n");
1131 fprintf (stats_file
, "SMS profile-sum-max ");
1132 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1133 (HOST_WIDEST_INT
) profile_info
->sum_max
);
1134 fprintf (stats_file
, "\n");
1136 fprintf (stats_file
, "SMS doloop\n");
1137 fprintf (stats_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1138 fprintf (stats_file
, "SMS num-loads %d\n", g
->num_loads
);
1139 fprintf (stats_file
, "SMS num-stores %d\n", g
->num_stores
);
1143 /* In case of th loop have doloop register it gets special
1145 count_init
= NULL_RTX
;
1146 if ((count_reg
= doloop_register_get (tail
)))
1148 basic_block pre_header
;
1150 pre_header
= loop_preheader_edge (loop
)->src
;
1151 count_init
= const_iteration_count (count_reg
, pre_header
,
1154 gcc_assert (count_reg
);
1156 if (stats_file
&& count_init
)
1158 fprintf (stats_file
, "SMS const-doloop ");
1159 fprintf (stats_file
, HOST_WIDEST_INT_PRINT_DEC
,
1161 fprintf (stats_file
, "\n");
1164 node_order
= (int *) xmalloc (sizeof (int) * g
->num_nodes
);
1166 mii
= 1; /* Need to pass some estimate of mii. */
1167 rec_mii
= sms_order_nodes (g
, mii
, node_order
);
1168 mii
= MAX (res_MII (g
), rec_mii
);
1169 maxii
= (calculate_maxii (g
) * SMS_MAX_II_FACTOR
) / 100;
1172 fprintf (stats_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1173 rec_mii
, mii
, maxii
);
1175 /* After sms_order_nodes and before sms_schedule_by_order, to copy over
1177 set_node_sched_params (g
);
1179 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
, dump_file
);
1182 stage_count
= PS_STAGE_COUNT (ps
);
1184 /* Stage count of 1 means that there is no interleaving between
1185 iterations, let the scheduling passes do the job. */
1187 || (count_init
&& (loop_count
<= stage_count
))
1188 || (flag_branch_probabilities
&& (trip_count
<= stage_count
)))
1192 fprintf (dump_file
, "SMS failed... \n");
1193 fprintf (dump_file
, "SMS sched-failed (stage-count=%d, loop-count=", stage_count
);
1194 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, loop_count
);
1195 fprintf (dump_file
, ", trip-count=");
1196 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, trip_count
);
1197 fprintf (dump_file
, ")\n");
1203 int orig_cycles
= kernel_number_of_cycles (BB_HEAD (g
->bb
), BB_END (g
->bb
));
1205 struct undo_replace_buff_elem
*reg_move_replaces
;
1209 fprintf (stats_file
,
1210 "SMS succeeded %d %d (with ii, sc)\n", ps
->ii
,
1212 print_partial_schedule (ps
, stats_file
);
1213 fprintf (stats_file
,
1214 "SMS Branch (%d) will later be scheduled at cycle %d.\n",
1215 g
->closing_branch
->cuid
, PS_MIN_CYCLE (ps
) - 1);
1218 /* Set the stage boundaries. If the DDG is built with closing_branch_deps,
1219 the closing_branch was scheduled and should appear in the last (ii-1)
1220 row. Otherwise, we are free to schedule the branch, and we let nodes
1221 that were scheduled at the first PS_MIN_CYCLE cycle appear in the first
1222 row; this should reduce stage_count to minimum. */
1223 normalize_sched_times (ps
);
1224 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
1225 set_columns_for_ps (ps
);
1227 /* Generate the kernel just to be able to measure its cycles. */
1228 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1229 reg_move_replaces
= generate_reg_moves (ps
);
1231 /* Get the number of cycles the new kernel expect to execute in. */
1232 new_cycles
= kernel_number_of_cycles (BB_HEAD (g
->bb
), BB_END (g
->bb
));
1234 /* Get back to the original loop so we can do loop versioning. */
1235 undo_permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1236 if (reg_move_replaces
)
1237 undo_generate_reg_moves (ps
, reg_move_replaces
);
1239 if ( new_cycles
>= orig_cycles
)
1241 /* SMS is not profitable so undo the permutation and reg move generation
1242 and return the kernel to its original state. */
1244 fprintf (dump_file
, "Undoing SMS because it is not profitable.\n");
1251 /* case the BCT count is not known , Do loop-versioning */
1252 if (count_reg
&& ! count_init
)
1254 rtx comp_rtx
= gen_rtx_fmt_ee (GT
, VOIDmode
, count_reg
,
1255 GEN_INT(stage_count
));
1257 nloop
= loop_version (loops
, loop
, comp_rtx
, &condition_bb
);
1260 /* Set new iteration count of loop kernel. */
1261 if (count_reg
&& count_init
)
1262 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1265 /* Now apply the scheduled kernel to the RTL of the loop. */
1266 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1268 /* Mark this loop as software pipelined so the later
1269 scheduling passes doesn't touch it. */
1270 if (! flag_resched_modulo_sched
)
1271 g
->bb
->flags
|= BB_DISABLE_SCHEDULE
;
1272 /* The life-info is not valid any more. */
1273 g
->bb
->flags
|= BB_DIRTY
;
1275 reg_move_replaces
= generate_reg_moves (ps
);
1277 print_node_sched_params (dump_file
, g
->num_nodes
);
1278 /* Generate prolog and epilog. */
1279 if (count_reg
&& !count_init
)
1280 generate_prolog_epilog (ps
, loop
, count_reg
);
1282 generate_prolog_epilog (ps
, loop
, NULL_RTX
);
1284 free_undo_replace_buff (reg_move_replaces
);
1287 free_partial_schedule (ps
);
1288 free (node_sched_params
);
1293 /* Release scheduler data, needed until now because of DFA. */
1295 loop_optimizer_finalize (loops
, dump_file
);
1298 /* The SMS scheduling algorithm itself
1299 -----------------------------------
1300 Input: 'O' an ordered list of insns of a loop.
1301 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1303 'Q' is the empty Set
1304 'PS' is the partial schedule; it holds the currently scheduled nodes with
1306 'PSP' previously scheduled predecessors.
1307 'PSS' previously scheduled successors.
1308 't(u)' the cycle where u is scheduled.
1309 'l(u)' is the latency of u.
1310 'd(v,u)' is the dependence distance from v to u.
1311 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1312 the node ordering phase.
1313 'check_hardware_resources_conflicts(u, PS, c)'
1314 run a trace around cycle/slot through DFA model
1315 to check resource conflicts involving instruction u
1316 at cycle c given the partial schedule PS.
1317 'add_to_partial_schedule_at_time(u, PS, c)'
1318 Add the node/instruction u to the partial schedule
1320 'calculate_register_pressure(PS)'
1321 Given a schedule of instructions, calculate the register
1322 pressure it implies. One implementation could be the
1323 maximum number of overlapping live ranges.
1324 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1325 registers available in the hardware.
1329 3. for each node u in O in pre-computed order
1330 4. if (PSP(u) != Q && PSS(u) == Q) then
1331 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1332 6. start = Early_start; end = Early_start + II - 1; step = 1
1333 11. else if (PSP(u) == Q && PSS(u) != Q) then
1334 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1335 13. start = Late_start; end = Late_start - II + 1; step = -1
1336 14. else if (PSP(u) != Q && PSS(u) != Q) then
1337 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1338 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1339 17. start = Early_start;
1340 18. end = min(Early_start + II - 1 , Late_start);
1342 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1343 21. start = ASAP(u); end = start + II - 1; step = 1
1347 24. for (c = start ; c != end ; c += step)
1348 25. if check_hardware_resources_conflicts(u, PS, c) then
1349 26. add_to_partial_schedule_at_time(u, PS, c)
1354 31. if (success == false) then
1356 33. if (II > maxII) then
1357 34. finish - failed to schedule
1362 39. if (calculate_register_pressure(PS) > maxRP) then
1365 42. compute epilogue & prologue
1366 43. finish - succeeded to schedule
1369 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1370 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1371 set to 0 to save compile time. */
1372 #define DFA_HISTORY SMS_DFA_HISTORY
1374 /* Given the partial schedule PS, this function calculates and returns the
1375 cycles in which we can schedule the node with the given index I.
1376 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1377 noticed that there are several cases in which we fail to SMS the loop
1378 because the sched window of a node is empty due to tight data-deps. In
1379 such cases we want to unschedule some of the predecessors/successors
1380 until we get non-empty scheduling window. It returns -1 if the
1381 scheduling window is empty and zero otherwise. */
1384 get_sched_window (partial_schedule_ptr ps
, int *nodes_order
, int i
,
1385 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
, int *end_p
)
1387 int start
, step
, end
;
1389 int u
= nodes_order
[i
];
1390 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
1391 sbitmap psp
= sbitmap_alloc (ps
->g
->num_nodes
);
1392 sbitmap pss
= sbitmap_alloc (ps
->g
->num_nodes
);
1393 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1394 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1398 /* 1. compute sched window for u (start, end, step). */
1401 psp_not_empty
= sbitmap_a_and_b_cg (psp
, u_node_preds
, sched_nodes
);
1402 pss_not_empty
= sbitmap_a_and_b_cg (pss
, u_node_succs
, sched_nodes
);
1404 if (psp_not_empty
&& !pss_not_empty
)
1406 int early_start
= INT_MIN
;
1409 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1411 ddg_node_ptr v_node
= e
->src
;
1412 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1414 int node_st
= SCHED_TIME (v_node
)
1415 + e
->latency
- (e
->distance
* ii
);
1417 early_start
= MAX (early_start
, node_st
);
1419 if (e
->data_type
== MEM_DEP
)
1420 end
= MIN (end
, SCHED_TIME (v_node
) + ii
- 1);
1423 start
= early_start
;
1424 end
= MIN (end
, early_start
+ ii
);
1428 else if (!psp_not_empty
&& pss_not_empty
)
1430 int late_start
= INT_MAX
;
1433 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1435 ddg_node_ptr v_node
= e
->dest
;
1436 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1438 late_start
= MIN (late_start
,
1439 SCHED_TIME (v_node
) - e
->latency
1440 + (e
->distance
* ii
));
1441 if (e
->data_type
== MEM_DEP
)
1442 end
= MAX (end
, SCHED_TIME (v_node
) - ii
+ 1);
1446 end
= MAX (end
, late_start
- ii
);
1450 else if (psp_not_empty
&& pss_not_empty
)
1452 int early_start
= INT_MIN
;
1453 int late_start
= INT_MAX
;
1457 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1459 ddg_node_ptr v_node
= e
->src
;
1461 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1463 early_start
= MAX (early_start
,
1464 SCHED_TIME (v_node
) + e
->latency
1465 - (e
->distance
* ii
));
1466 if (e
->data_type
== MEM_DEP
)
1467 end
= MIN (end
, SCHED_TIME (v_node
) + ii
- 1);
1470 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1472 ddg_node_ptr v_node
= e
->dest
;
1474 if (TEST_BIT (sched_nodes
, v_node
->cuid
))
1476 late_start
= MIN (late_start
,
1477 SCHED_TIME (v_node
) - e
->latency
1478 + (e
->distance
* ii
));
1479 if (e
->data_type
== MEM_DEP
)
1480 start
= MAX (start
, SCHED_TIME (v_node
) - ii
+ 1);
1483 start
= MAX (start
, early_start
);
1484 end
= MIN (end
, MIN (early_start
+ ii
, late_start
+ 1));
1487 else /* psp is empty && pss is empty. */
1489 start
= SCHED_ASAP (u_node
);
1500 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
1506 /* This function implements the scheduling algorithm for SMS according to the
1508 static partial_schedule_ptr
1509 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
, FILE *dump_file
)
1513 int try_again_with_larger_ii
= true;
1514 int num_nodes
= g
->num_nodes
;
1516 int start
, end
, step
; /* Place together into one struct? */
1517 sbitmap sched_nodes
= sbitmap_alloc (num_nodes
);
1518 sbitmap must_precede
= sbitmap_alloc (num_nodes
);
1519 sbitmap must_follow
= sbitmap_alloc (num_nodes
);
1520 sbitmap tobe_scheduled
= sbitmap_alloc (num_nodes
);
1522 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
, DFA_HISTORY
);
1524 sbitmap_ones (tobe_scheduled
);
1525 sbitmap_zero (sched_nodes
);
1527 while ((! sbitmap_equal (tobe_scheduled
, sched_nodes
)
1528 || try_again_with_larger_ii
) && ii
< maxii
)
1531 bool unscheduled_nodes
= false;
1534 fprintf(dump_file
, "Starting with ii=%d\n", ii
);
1535 if (try_again_with_larger_ii
)
1537 try_again_with_larger_ii
= false;
1538 sbitmap_zero (sched_nodes
);
1541 for (i
= 0; i
< num_nodes
; i
++)
1543 int u
= nodes_order
[i
];
1544 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
1545 rtx insn
= u_node
->insn
;
1549 RESET_BIT (tobe_scheduled
, u
);
1553 if (JUMP_P (insn
)) /* Closing branch handled later. */
1555 RESET_BIT (tobe_scheduled
, u
);
1559 if (TEST_BIT (sched_nodes
, u
))
1562 /* Try to get non-empty scheduling window. */
1564 while (get_sched_window (ps
, nodes_order
, i
, sched_nodes
, ii
, &start
, &step
, &end
) < 0
1567 unscheduled_nodes
= true;
1568 if (TEST_BIT (NODE_PREDECESSORS (u_node
), nodes_order
[j
- 1])
1569 || TEST_BIT (NODE_SUCCESSORS (u_node
), nodes_order
[j
- 1]))
1571 ps_unschedule_node (ps
, &ps
->g
->nodes
[nodes_order
[j
- 1]]);
1572 RESET_BIT (sched_nodes
, nodes_order
[j
- 1]);
1578 /* ??? Try backtracking instead of immediately ii++? */
1580 try_again_with_larger_ii
= true;
1581 reset_partial_schedule (ps
, ii
);
1584 /* 2. Try scheduling u in window. */
1586 fprintf(dump_file
, "Trying to schedule node %d in (%d .. %d) step %d\n",
1587 u
, start
, end
, step
);
1589 /* use must_follow & must_precede bitmaps to determine order
1590 of nodes within the cycle. */
1591 sbitmap_zero (must_precede
);
1592 sbitmap_zero (must_follow
);
1593 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1594 if (TEST_BIT (sched_nodes
, e
->src
->cuid
)
1595 && e
->latency
== (ii
* e
->distance
)
1596 && start
== SCHED_TIME (e
->src
))
1597 SET_BIT (must_precede
, e
->src
->cuid
);
1599 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1600 if (TEST_BIT (sched_nodes
, e
->dest
->cuid
)
1601 && e
->latency
== (ii
* e
->distance
)
1602 && end
== SCHED_TIME (e
->dest
))
1603 SET_BIT (must_follow
, e
->dest
->cuid
);
1606 if ((step
> 0 && start
< end
) || (step
< 0 && start
> end
))
1607 for (c
= start
; c
!= end
; c
+= step
)
1611 psi
= ps_add_node_check_conflicts (ps
, u_node
, c
,
1617 SCHED_TIME (u_node
) = c
;
1618 SET_BIT (sched_nodes
, u
);
1621 fprintf(dump_file
, "Schedule in %d\n", c
);
1627 /* ??? Try backtracking instead of immediately ii++? */
1629 try_again_with_larger_ii
= true;
1630 reset_partial_schedule (ps
, ii
);
1633 if (unscheduled_nodes
)
1636 /* ??? If (success), check register pressure estimates. */
1637 } /* Continue with next node. */
1638 } /* While try_again_with_larger_ii. */
1640 sbitmap_free (sched_nodes
);
1644 free_partial_schedule (ps
);
1651 /* This page implements the algorithm for ordering the nodes of a DDG
1652 for modulo scheduling, activated through the
1653 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
1655 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
1656 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
1657 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
1658 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
1659 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
1660 #define DEPTH(x) (ASAP ((x)))
1662 typedef struct node_order_params
* nopa
;
1664 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
1665 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
1666 static nopa
calculate_order_params (ddg_ptr
, int mii
);
1667 static int find_max_asap (ddg_ptr
, sbitmap
);
1668 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
1669 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
1671 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
1673 struct node_order_params
1680 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
1682 check_nodes_order (int *node_order
, int num_nodes
)
1685 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1689 for (i
= 0; i
< num_nodes
; i
++)
1691 int u
= node_order
[i
];
1693 gcc_assert (u
< num_nodes
&& u
>= 0 && !TEST_BIT (tmp
, u
));
1701 /* Order the nodes of G for scheduling and pass the result in
1702 NODE_ORDER. Also set aux.count of each node to ASAP.
1703 Return the recMII for the given DDG. */
1705 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
)
1709 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
1711 nopa nops
= calculate_order_params (g
, mii
);
1713 order_nodes_of_sccs (sccs
, node_order
);
1715 if (sccs
->num_sccs
> 0)
1716 /* First SCC has the largest recurrence_length. */
1717 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
1719 /* Save ASAP before destroying node_order_params. */
1720 for (i
= 0; i
< g
->num_nodes
; i
++)
1722 ddg_node_ptr v
= &g
->nodes
[i
];
1723 v
->aux
.count
= ASAP (v
);
1727 free_ddg_all_sccs (sccs
);
1728 check_nodes_order (node_order
, g
->num_nodes
);
1734 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
1737 ddg_ptr g
= all_sccs
->ddg
;
1738 int num_nodes
= g
->num_nodes
;
1739 sbitmap prev_sccs
= sbitmap_alloc (num_nodes
);
1740 sbitmap on_path
= sbitmap_alloc (num_nodes
);
1741 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1742 sbitmap ones
= sbitmap_alloc (num_nodes
);
1744 sbitmap_zero (prev_sccs
);
1745 sbitmap_ones (ones
);
1747 /* Perfrom the node ordering starting from the SCC with the highest recMII.
1748 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
1749 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
1751 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
1753 /* Add nodes on paths from previous SCCs to the current SCC. */
1754 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
1755 sbitmap_a_or_b (tmp
, scc
->nodes
, on_path
);
1757 /* Add nodes on paths from the current SCC to previous SCCs. */
1758 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
1759 sbitmap_a_or_b (tmp
, tmp
, on_path
);
1761 /* Remove nodes of previous SCCs from current extended SCC. */
1762 sbitmap_difference (tmp
, tmp
, prev_sccs
);
1764 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
1765 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
1768 /* Handle the remaining nodes that do not belong to any scc. Each call
1769 to order_nodes_in_scc handles a single connected component. */
1770 while (pos
< g
->num_nodes
)
1772 sbitmap_difference (tmp
, ones
, prev_sccs
);
1773 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
1775 sbitmap_free (prev_sccs
);
1776 sbitmap_free (on_path
);
1778 sbitmap_free (ones
);
1781 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
1782 static struct node_order_params
*
1783 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
)
1787 int num_nodes
= g
->num_nodes
;
1789 /* Allocate a place to hold ordering params for each node in the DDG. */
1790 nopa node_order_params_arr
;
1792 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
1793 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
1794 sizeof (struct node_order_params
));
1796 /* Set the aux pointer of each node to point to its order_params structure. */
1797 for (u
= 0; u
< num_nodes
; u
++)
1798 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
1800 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
1801 calculate ASAP, ALAP, mobility, distance, and height for each node
1802 in the dependence (direct acyclic) graph. */
1804 /* We assume that the nodes in the array are in topological order. */
1807 for (u
= 0; u
< num_nodes
; u
++)
1809 ddg_node_ptr u_node
= &g
->nodes
[u
];
1812 for (e
= u_node
->in
; e
; e
= e
->next_in
)
1813 if (e
->distance
== 0)
1814 ASAP (u_node
) = MAX (ASAP (u_node
),
1815 ASAP (e
->src
) + e
->latency
);
1816 max_asap
= MAX (max_asap
, ASAP (u_node
));
1819 for (u
= num_nodes
- 1; u
> -1; u
--)
1821 ddg_node_ptr u_node
= &g
->nodes
[u
];
1823 ALAP (u_node
) = max_asap
;
1824 HEIGHT (u_node
) = 0;
1825 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1826 if (e
->distance
== 0)
1828 ALAP (u_node
) = MIN (ALAP (u_node
),
1829 ALAP (e
->dest
) - e
->latency
);
1830 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
1831 HEIGHT (e
->dest
) + e
->latency
);
1835 return node_order_params_arr
;
1839 find_max_asap (ddg_ptr g
, sbitmap nodes
)
1845 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
,
1847 ddg_node_ptr u_node
= &g
->nodes
[u
];
1849 if (max_asap
< ASAP (u_node
))
1851 max_asap
= ASAP (u_node
);
1859 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
1863 int min_mob
= INT_MAX
;
1866 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
,
1868 ddg_node_ptr u_node
= &g
->nodes
[u
];
1870 if (max_hv
< HEIGHT (u_node
))
1872 max_hv
= HEIGHT (u_node
);
1873 min_mob
= MOB (u_node
);
1876 else if ((max_hv
== HEIGHT (u_node
))
1877 && (min_mob
> MOB (u_node
)))
1879 min_mob
= MOB (u_node
);
1887 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
1891 int min_mob
= INT_MAX
;
1894 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
,
1896 ddg_node_ptr u_node
= &g
->nodes
[u
];
1898 if (max_dv
< DEPTH (u_node
))
1900 max_dv
= DEPTH (u_node
);
1901 min_mob
= MOB (u_node
);
1904 else if ((max_dv
== DEPTH (u_node
))
1905 && (min_mob
> MOB (u_node
)))
1907 min_mob
= MOB (u_node
);
1914 /* Places the nodes of SCC into the NODE_ORDER array starting
1915 at position POS, according to the SMS ordering algorithm.
1916 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
1917 the NODE_ORDER array, starting from position zero. */
1919 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
1920 int * node_order
, int pos
)
1922 enum sms_direction dir
;
1923 int num_nodes
= g
->num_nodes
;
1924 sbitmap workset
= sbitmap_alloc (num_nodes
);
1925 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1926 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
1927 sbitmap predecessors
= sbitmap_alloc (num_nodes
);
1928 sbitmap successors
= sbitmap_alloc (num_nodes
);
1930 sbitmap_zero (predecessors
);
1931 find_predecessors (predecessors
, g
, nodes_ordered
);
1933 sbitmap_zero (successors
);
1934 find_successors (successors
, g
, nodes_ordered
);
1937 if (sbitmap_a_and_b_cg (tmp
, predecessors
, scc
))
1939 sbitmap_copy (workset
, tmp
);
1942 else if (sbitmap_a_and_b_cg (tmp
, successors
, scc
))
1944 sbitmap_copy (workset
, tmp
);
1951 sbitmap_zero (workset
);
1952 if ((u
= find_max_asap (g
, scc
)) >= 0)
1953 SET_BIT (workset
, u
);
1957 sbitmap_zero (zero_bitmap
);
1958 while (!sbitmap_equal (workset
, zero_bitmap
))
1961 ddg_node_ptr v_node
;
1962 sbitmap v_node_preds
;
1963 sbitmap v_node_succs
;
1967 while (!sbitmap_equal (workset
, zero_bitmap
))
1969 v
= find_max_hv_min_mob (g
, workset
);
1970 v_node
= &g
->nodes
[v
];
1971 node_order
[pos
++] = v
;
1972 v_node_succs
= NODE_SUCCESSORS (v_node
);
1973 sbitmap_a_and_b (tmp
, v_node_succs
, scc
);
1975 /* Don't consider the already ordered successors 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 (predecessors
);
1983 find_predecessors (predecessors
, g
, nodes_ordered
);
1984 sbitmap_a_and_b (workset
, predecessors
, scc
);
1988 while (!sbitmap_equal (workset
, zero_bitmap
))
1990 v
= find_max_dv_min_mob (g
, workset
);
1991 v_node
= &g
->nodes
[v
];
1992 node_order
[pos
++] = v
;
1993 v_node_preds
= NODE_PREDECESSORS (v_node
);
1994 sbitmap_a_and_b (tmp
, v_node_preds
, scc
);
1996 /* Don't consider the already ordered predecessors again. */
1997 sbitmap_difference (tmp
, tmp
, nodes_ordered
);
1998 sbitmap_a_or_b (workset
, workset
, tmp
);
1999 RESET_BIT (workset
, v
);
2000 SET_BIT (nodes_ordered
, v
);
2003 sbitmap_zero (successors
);
2004 find_successors (successors
, g
, nodes_ordered
);
2005 sbitmap_a_and_b (workset
, successors
, scc
);
2009 sbitmap_free (workset
);
2010 sbitmap_free (zero_bitmap
);
2011 sbitmap_free (predecessors
);
2012 sbitmap_free (successors
);
2017 /* This page contains functions for manipulating partial-schedules during
2018 modulo scheduling. */
2020 /* Create a partial schedule and allocate a memory to hold II rows. */
2021 partial_schedule_ptr
2022 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2024 partial_schedule_ptr ps
= (partial_schedule_ptr
)
2025 xmalloc (sizeof (struct partial_schedule
));
2026 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2028 ps
->history
= history
;
2029 ps
->min_cycle
= INT_MAX
;
2030 ps
->max_cycle
= INT_MIN
;
2036 /* Free the PS_INSNs in rows array of the given partial schedule.
2037 ??? Consider caching the PS_INSN's. */
2039 free_ps_insns (partial_schedule_ptr ps
)
2043 for (i
= 0; i
< ps
->ii
; i
++)
2047 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2050 ps
->rows
[i
] = ps_insn
;
2056 /* Free all the memory allocated to the partial schedule. */
2058 free_partial_schedule (partial_schedule_ptr ps
)
2067 /* Clear the rows array with its PS_INSNs, and create a new one with
2070 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2075 if (new_ii
== ps
->ii
)
2077 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2078 * sizeof (ps_insn_ptr
));
2079 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2081 ps
->min_cycle
= INT_MAX
;
2082 ps
->max_cycle
= INT_MIN
;
2085 /* Prints the partial schedule as an ii rows array, for each rows
2086 print the ids of the insns in it. */
2088 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2092 for (i
= 0; i
< ps
->ii
; i
++)
2094 ps_insn_ptr ps_i
= ps
->rows
[i
];
2096 fprintf (dump
, "\n[CYCLE %d ]: ", i
);
2099 fprintf (dump
, "%d, ",
2100 INSN_UID (ps_i
->node
->insn
));
2101 ps_i
= ps_i
->next_in_row
;
2106 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2108 create_ps_insn (ddg_node_ptr node
, int rest_count
, int cycle
)
2110 ps_insn_ptr ps_i
= xmalloc (sizeof (struct ps_insn
));
2113 ps_i
->next_in_row
= NULL
;
2114 ps_i
->prev_in_row
= NULL
;
2115 ps_i
->row_rest_count
= rest_count
;
2116 ps_i
->cycle
= cycle
;
2122 /* Removes the given PS_INSN from the partial schedule. Returns false if the
2123 node is not found in the partial schedule, else returns true. */
2125 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2132 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2133 if (! ps_i
->prev_in_row
)
2135 if (ps_i
!= ps
->rows
[row
])
2138 ps
->rows
[row
] = ps_i
->next_in_row
;
2140 ps
->rows
[row
]->prev_in_row
= NULL
;
2144 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
2145 if (ps_i
->next_in_row
)
2146 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
2152 /* Unlike what literature describes for modulo scheduling (which focuses
2153 on VLIW machines) the order of the instructions inside a cycle is
2154 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2155 where the current instruction should go relative to the already
2156 scheduled instructions in the given cycle. Go over these
2157 instructions and find the first possible column to put it in. */
2159 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2160 sbitmap must_precede
, sbitmap must_follow
)
2162 ps_insn_ptr next_ps_i
;
2163 ps_insn_ptr first_must_follow
= NULL
;
2164 ps_insn_ptr last_must_precede
= NULL
;
2170 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2172 /* Find the first must follow and the last must precede
2173 and insert the node immediately after the must precede
2174 but make sure that it there is no must follow after it. */
2175 for (next_ps_i
= ps
->rows
[row
];
2177 next_ps_i
= next_ps_i
->next_in_row
)
2179 if (TEST_BIT (must_follow
, next_ps_i
->node
->cuid
)
2180 && ! first_must_follow
)
2181 first_must_follow
= next_ps_i
;
2182 if (TEST_BIT (must_precede
, next_ps_i
->node
->cuid
))
2184 /* If we have already met a node that must follow, then
2185 there is no possible column. */
2186 if (first_must_follow
)
2189 last_must_precede
= next_ps_i
;
2193 /* Now insert the node after INSERT_AFTER_PSI. */
2195 if (! last_must_precede
)
2197 ps_i
->next_in_row
= ps
->rows
[row
];
2198 ps_i
->prev_in_row
= NULL
;
2199 if (ps_i
->next_in_row
)
2200 ps_i
->next_in_row
->prev_in_row
= ps_i
;
2201 ps
->rows
[row
] = ps_i
;
2205 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
2206 last_must_precede
->next_in_row
= ps_i
;
2207 ps_i
->prev_in_row
= last_must_precede
;
2208 if (ps_i
->next_in_row
)
2209 ps_i
->next_in_row
->prev_in_row
= ps_i
;
2215 /* Advances the PS_INSN one column in its current row; returns false
2216 in failure and true in success. Bit N is set in MUST_FOLLOW if
2217 the node with cuid N must be come after the node pointed to by
2218 PS_I when scheduled in the same cycle. */
2220 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2221 sbitmap must_follow
)
2223 ps_insn_ptr prev
, next
;
2225 ddg_node_ptr next_node
;
2230 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2232 if (! ps_i
->next_in_row
)
2235 next_node
= ps_i
->next_in_row
->node
;
2237 /* Check if next_in_row is dependent on ps_i, both having same sched
2238 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
2239 if (TEST_BIT (must_follow
, next_node
->cuid
))
2242 /* Advance PS_I over its next_in_row in the doubly linked list. */
2243 prev
= ps_i
->prev_in_row
;
2244 next
= ps_i
->next_in_row
;
2246 if (ps_i
== ps
->rows
[row
])
2247 ps
->rows
[row
] = next
;
2249 ps_i
->next_in_row
= next
->next_in_row
;
2251 if (next
->next_in_row
)
2252 next
->next_in_row
->prev_in_row
= ps_i
;
2254 next
->next_in_row
= ps_i
;
2255 ps_i
->prev_in_row
= next
;
2257 next
->prev_in_row
= prev
;
2259 prev
->next_in_row
= next
;
2264 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
2265 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
2266 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
2267 before/after (respectively) the node pointed to by PS_I when scheduled
2268 in the same cycle. */
2270 add_node_to_ps (partial_schedule_ptr ps
, ddg_node_ptr node
, int cycle
,
2271 sbitmap must_precede
, sbitmap must_follow
)
2275 int row
= SMODULO (cycle
, ps
->ii
);
2278 && ps
->rows
[row
]->row_rest_count
>= issue_rate
)
2282 rest_count
+= ps
->rows
[row
]->row_rest_count
;
2284 ps_i
= create_ps_insn (node
, rest_count
, cycle
);
2286 /* Finds and inserts PS_I according to MUST_FOLLOW and
2288 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
2297 /* Advance time one cycle. Assumes DFA is being used. */
2299 advance_one_cycle (void)
2301 if (targetm
.sched
.dfa_pre_cycle_insn
)
2302 state_transition (curr_state
,
2303 targetm
.sched
.dfa_pre_cycle_insn ());
2305 state_transition (curr_state
, NULL
);
2307 if (targetm
.sched
.dfa_post_cycle_insn
)
2308 state_transition (curr_state
,
2309 targetm
.sched
.dfa_post_cycle_insn ());
2312 /* Given the kernel of a loop (from FIRST_INSN to LAST_INSN), finds
2313 the number of cycles according to DFA that the kernel fits in,
2314 we use this to check if we done well with SMS after we add
2315 register moves. In some cases register moves overhead makes
2316 it even worse than the original loop. We want SMS to be performed
2317 when it gives less cycles after register moves are added. */
2319 kernel_number_of_cycles (rtx first_insn
, rtx last_insn
)
2323 int can_issue_more
= issue_rate
;
2325 state_reset (curr_state
);
2327 for (insn
= first_insn
;
2328 insn
!= NULL_RTX
&& insn
!= last_insn
;
2329 insn
= NEXT_INSN (insn
))
2331 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
2334 /* Check if there is room for the current insn. */
2335 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
2338 advance_one_cycle ();
2339 can_issue_more
= issue_rate
;
2342 /* Update the DFA state and return with failure if the DFA found
2343 recource conflicts. */
2344 if (state_transition (curr_state
, insn
) >= 0)
2347 advance_one_cycle ();
2348 can_issue_more
= issue_rate
;
2351 if (targetm
.sched
.variable_issue
)
2353 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
2354 insn
, can_issue_more
);
2355 /* A naked CLOBBER or USE generates no instruction, so don't
2356 let them consume issue slots. */
2357 else if (GET_CODE (PATTERN (insn
)) != USE
2358 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2364 /* Checks if PS has resource conflicts according to DFA, starting from
2365 FROM cycle to TO cycle; returns true if there are conflicts and false
2366 if there are no conflicts. Assumes DFA is being used. */
2368 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
2372 state_reset (curr_state
);
2374 for (cycle
= from
; cycle
<= to
; cycle
++)
2376 ps_insn_ptr crr_insn
;
2377 /* Holds the remaining issue slots in the current row. */
2378 int can_issue_more
= issue_rate
;
2380 /* Walk through the DFA for the current row. */
2381 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
2383 crr_insn
= crr_insn
->next_in_row
)
2385 rtx insn
= crr_insn
->node
->insn
;
2390 /* Check if there is room for the current insn. */
2391 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
2394 /* Update the DFA state and return with failure if the DFA found
2395 recource conflicts. */
2396 if (state_transition (curr_state
, insn
) >= 0)
2399 if (targetm
.sched
.variable_issue
)
2401 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
2402 insn
, can_issue_more
);
2403 /* A naked CLOBBER or USE generates no instruction, so don't
2404 let them consume issue slots. */
2405 else if (GET_CODE (PATTERN (insn
)) != USE
2406 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2410 /* Advance the DFA to the next cycle. */
2411 advance_one_cycle ();
2416 /* Checks if the given node causes resource conflicts when added to PS at
2417 cycle C. If not the node is added to PS and returned; otherwise zero
2418 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
2419 cuid N must be come before/after (respectively) the node pointed to by
2420 PS_I when scheduled in the same cycle. */
2422 ps_add_node_check_conflicts (partial_schedule_ptr ps
, ddg_node_ptr n
,
2423 int c
, sbitmap must_precede
,
2424 sbitmap must_follow
)
2426 int has_conflicts
= 0;
2429 /* First add the node to the PS, if this succeeds check for
2430 conflicts, trying different issue slots in the same row. */
2431 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
2432 return NULL
; /* Failed to insert the node at the given cycle. */
2434 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
2436 && ps_has_conflicts (ps
,
2440 /* Try different issue slots to find one that the given node can be
2441 scheduled in without conflicts. */
2442 while (has_conflicts
)
2444 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
2446 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
2448 && ps_has_conflicts (ps
,
2455 remove_node_from_ps (ps
, ps_i
);
2459 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
2460 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
2464 /* Rotate the rows of PS such that insns scheduled at time
2465 START_CYCLE will appear in row 0. Updates max/min_cycles. */
2467 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
2469 int i
, row
, backward_rotates
;
2470 int last_row
= ps
->ii
- 1;
2472 if (start_cycle
== 0)
2475 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
2477 /* Revisit later and optimize this into a single loop. */
2478 for (i
= 0; i
< backward_rotates
; i
++)
2480 ps_insn_ptr first_row
= ps
->rows
[0];
2482 for (row
= 0; row
< last_row
; row
++)
2483 ps
->rows
[row
] = ps
->rows
[row
+1];
2485 ps
->rows
[last_row
] = first_row
;
2488 ps
->max_cycle
-= start_cycle
;
2489 ps
->min_cycle
-= start_cycle
;
2492 /* Remove the node N from the partial schedule PS; because we restart the DFA
2493 each time we want to check for resource conflicts; this is equivalent to
2494 unscheduling the node N. */
2496 ps_unschedule_node (partial_schedule_ptr ps
, ddg_node_ptr n
)
2499 int row
= SMODULO (SCHED_TIME (n
), ps
->ii
);
2501 if (row
< 0 || row
> ps
->ii
)
2504 for (ps_i
= ps
->rows
[row
];
2505 ps_i
&& ps_i
->node
!= n
;
2506 ps_i
= ps_i
->next_in_row
);
2510 return remove_node_from_ps (ps
, ps_i
);
2512 #endif /* INSN_SCHEDULING*/