1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004-2014 Free Software Foundation, Inc.
3 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
26 #include "diagnostic-core.h"
29 #include "hard-reg-set.h"
33 #include "insn-config.h"
34 #include "insn-attr.h"
37 #include "sched-int.h"
44 #include "tree-pass.h"
48 #ifdef INSN_SCHEDULING
50 /* This file contains the implementation of the Swing Modulo Scheduler,
51 described in the following references:
52 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
53 Lifetime--sensitive modulo scheduling in a production environment.
54 IEEE Trans. on Comps., 50(3), March 2001
55 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
56 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
57 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
59 The basic structure is:
60 1. Build a data-dependence graph (DDG) for each loop.
61 2. Use the DDG to order the insns of a loop (not in topological order
62 necessarily, but rather) trying to place each insn after all its
63 predecessors _or_ after all its successors.
64 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
65 4. Use the ordering to perform list-scheduling of the loop:
66 1. Set II = MII. We will try to schedule the loop within II cycles.
67 2. Try to schedule the insns one by one according to the ordering.
68 For each insn compute an interval of cycles by considering already-
69 scheduled preds and succs (and associated latencies); try to place
70 the insn in the cycles of this window checking for potential
71 resource conflicts (using the DFA interface).
72 Note: this is different from the cycle-scheduling of schedule_insns;
73 here the insns are not scheduled monotonically top-down (nor bottom-
75 3. If failed in scheduling all insns - bump II++ and try again, unless
76 II reaches an upper bound MaxII, in which case report failure.
77 5. If we succeeded in scheduling the loop within II cycles, we now
78 generate prolog and epilog, decrease the counter of the loop, and
79 perform modulo variable expansion for live ranges that span more than
80 II cycles (i.e. use register copies to prevent a def from overwriting
81 itself before reaching the use).
83 SMS works with countable loops (1) whose control part can be easily
84 decoupled from the rest of the loop and (2) whose loop count can
85 be easily adjusted. This is because we peel a constant number of
86 iterations into a prologue and epilogue for which we want to avoid
87 emitting the control part, and a kernel which is to iterate that
88 constant number of iterations less than the original loop. So the
89 control part should be a set of insns clearly identified and having
90 its own iv, not otherwise used in the loop (at-least for now), which
91 initializes a register before the loop to the number of iterations.
92 Currently SMS relies on the do-loop pattern to recognize such loops,
93 where (1) the control part comprises of all insns defining and/or
94 using a certain 'count' register and (2) the loop count can be
95 adjusted by modifying this register prior to the loop.
96 TODO: Rely on cfgloop analysis instead. */
98 /* This page defines partial-schedule structures and functions for
101 typedef struct partial_schedule
*partial_schedule_ptr
;
102 typedef struct ps_insn
*ps_insn_ptr
;
104 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
105 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
107 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
108 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
110 /* Perform signed modulo, always returning a non-negative value. */
111 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
113 /* The number of different iterations the nodes in ps span, assuming
114 the stage boundaries are placed efficiently. */
115 #define CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \
117 /* The stage count of ps. */
118 #define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count)
120 /* A single instruction in the partial schedule. */
123 /* Identifies the instruction to be scheduled. Values smaller than
124 the ddg's num_nodes refer directly to ddg nodes. A value of
125 X - num_nodes refers to register move X. */
128 /* The (absolute) cycle in which the PS instruction is scheduled.
129 Same as SCHED_TIME (node). */
132 /* The next/prev PS_INSN in the same row. */
133 ps_insn_ptr next_in_row
,
138 /* Information about a register move that has been added to a partial
140 struct ps_reg_move_info
142 /* The source of the move is defined by the ps_insn with id DEF.
143 The destination is used by the ps_insns with the ids in USES. */
147 /* The original form of USES' instructions used OLD_REG, but they
148 should now use NEW_REG. */
152 /* The number of consecutive stages that the move occupies. */
153 int num_consecutive_stages
;
155 /* An instruction that sets NEW_REG to the correct value. The first
156 move associated with DEF will have an rhs of OLD_REG; later moves
157 use the result of the previous move. */
161 typedef struct ps_reg_move_info ps_reg_move_info
;
163 /* Holds the partial schedule as an array of II rows. Each entry of the
164 array points to a linked list of PS_INSNs, which represents the
165 instructions that are scheduled for that row. */
166 struct partial_schedule
168 int ii
; /* Number of rows in the partial schedule. */
169 int history
; /* Threshold for conflict checking using DFA. */
171 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
174 /* All the moves added for this partial schedule. Index X has
175 a ps_insn id of X + g->num_nodes. */
176 vec
<ps_reg_move_info
> reg_moves
;
178 /* rows_length[i] holds the number of instructions in the row.
179 It is used only (as an optimization) to back off quickly from
180 trying to schedule a node in a full row; that is, to avoid running
181 through futile DFA state transitions. */
184 /* The earliest absolute cycle of an insn in the partial schedule. */
187 /* The latest absolute cycle of an insn in the partial schedule. */
190 ddg_ptr g
; /* The DDG of the insns in the partial schedule. */
192 int stage_count
; /* The stage count of the partial schedule. */
196 static partial_schedule_ptr
create_partial_schedule (int ii
, ddg_ptr
, int history
);
197 static void free_partial_schedule (partial_schedule_ptr
);
198 static void reset_partial_schedule (partial_schedule_ptr
, int new_ii
);
199 void print_partial_schedule (partial_schedule_ptr
, FILE *);
200 static void verify_partial_schedule (partial_schedule_ptr
, sbitmap
);
201 static ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr
,
202 int, int, sbitmap
, sbitmap
);
203 static void rotate_partial_schedule (partial_schedule_ptr
, int);
204 void set_row_column_for_ps (partial_schedule_ptr
);
205 static void ps_insert_empty_row (partial_schedule_ptr
, int, sbitmap
);
206 static int compute_split_row (sbitmap
, int, int, int, ddg_node_ptr
);
209 /* This page defines constants and structures for the modulo scheduling
212 static int sms_order_nodes (ddg_ptr
, int, int *, int *);
213 static void set_node_sched_params (ddg_ptr
);
214 static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr
, int, int, int *);
215 static void permute_partial_schedule (partial_schedule_ptr
, rtx_insn
*);
216 static void generate_prolog_epilog (partial_schedule_ptr
, struct loop
*,
218 static int calculate_stage_count (partial_schedule_ptr
, int);
219 static void calculate_must_precede_follow (ddg_node_ptr
, int, int,
220 int, int, sbitmap
, sbitmap
, sbitmap
);
221 static int get_sched_window (partial_schedule_ptr
, ddg_node_ptr
,
222 sbitmap
, int, int *, int *, int *);
223 static bool try_scheduling_node_in_cycle (partial_schedule_ptr
, int, int,
224 sbitmap
, int *, sbitmap
, sbitmap
);
225 static void remove_node_from_ps (partial_schedule_ptr
, ps_insn_ptr
);
227 #define NODE_ASAP(node) ((node)->aux.count)
229 #define SCHED_PARAMS(x) (&node_sched_param_vec[x])
230 #define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
231 #define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
232 #define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
233 #define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
235 /* The scheduling parameters held for each node. */
236 typedef struct node_sched_params
238 int time
; /* The absolute scheduling cycle. */
240 int row
; /* Holds time % ii. */
241 int stage
; /* Holds time / ii. */
243 /* The column of a node inside the ps. If nodes u, v are on the same row,
244 u will precede v if column (u) < column (v). */
246 } *node_sched_params_ptr
;
248 typedef struct node_sched_params node_sched_params
;
250 /* The following three functions are copied from the current scheduler
251 code in order to use sched_analyze() for computing the dependencies.
252 They are used when initializing the sched_info structure. */
254 sms_print_insn (const rtx_insn
*insn
, int aligned ATTRIBUTE_UNUSED
)
258 sprintf (tmp
, "i%4d", INSN_UID (insn
));
263 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
264 regset used ATTRIBUTE_UNUSED
)
268 static struct common_sched_info_def sms_common_sched_info
;
270 static struct sched_deps_info_def sms_sched_deps_info
=
272 compute_jump_reg_dependencies
,
273 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
278 static struct haifa_sched_info sms_sched_info
=
287 NULL
, /* insn_finishes_block_p */
292 NULL
, NULL
, NULL
, NULL
,
297 /* Partial schedule instruction ID in PS is a register move. Return
298 information about it. */
299 static struct ps_reg_move_info
*
300 ps_reg_move (partial_schedule_ptr ps
, int id
)
302 gcc_checking_assert (id
>= ps
->g
->num_nodes
);
303 return &ps
->reg_moves
[id
- ps
->g
->num_nodes
];
306 /* Return the rtl instruction that is being scheduled by partial schedule
307 instruction ID, which belongs to schedule PS. */
309 ps_rtl_insn (partial_schedule_ptr ps
, int id
)
311 if (id
< ps
->g
->num_nodes
)
312 return ps
->g
->nodes
[id
].insn
;
314 return ps_reg_move (ps
, id
)->insn
;
317 /* Partial schedule instruction ID, which belongs to PS, occurred in
318 the original (unscheduled) loop. Return the first instruction
319 in the loop that was associated with ps_rtl_insn (PS, ID).
320 If the instruction had some notes before it, this is the first
323 ps_first_note (partial_schedule_ptr ps
, int id
)
325 gcc_assert (id
< ps
->g
->num_nodes
);
326 return ps
->g
->nodes
[id
].first_note
;
329 /* Return the number of consecutive stages that are occupied by
330 partial schedule instruction ID in PS. */
332 ps_num_consecutive_stages (partial_schedule_ptr ps
, int id
)
334 if (id
< ps
->g
->num_nodes
)
337 return ps_reg_move (ps
, id
)->num_consecutive_stages
;
340 /* Given HEAD and TAIL which are the first and last insns in a loop;
341 return the register which controls the loop. Return zero if it has
342 more than one occurrence in the loop besides the control part or the
343 do-loop pattern is not of the form we expect. */
345 doloop_register_get (rtx_insn
*head ATTRIBUTE_UNUSED
, rtx_insn
*tail ATTRIBUTE_UNUSED
)
347 #ifdef HAVE_doloop_end
349 rtx_insn
*insn
, *first_insn_not_to_check
;
354 /* TODO: Free SMS's dependence on doloop_condition_get. */
355 condition
= doloop_condition_get (tail
);
359 if (REG_P (XEXP (condition
, 0)))
360 reg
= XEXP (condition
, 0);
361 else if (GET_CODE (XEXP (condition
, 0)) == PLUS
362 && REG_P (XEXP (XEXP (condition
, 0), 0)))
363 reg
= XEXP (XEXP (condition
, 0), 0);
367 /* Check that the COUNT_REG has no other occurrences in the loop
368 until the decrement. We assume the control part consists of
369 either a single (parallel) branch-on-count or a (non-parallel)
370 branch immediately preceded by a single (decrement) insn. */
371 first_insn_not_to_check
= (GET_CODE (PATTERN (tail
)) == PARALLEL
? tail
372 : prev_nondebug_insn (tail
));
374 for (insn
= head
; insn
!= first_insn_not_to_check
; insn
= NEXT_INSN (insn
))
375 if (!DEBUG_INSN_P (insn
) && reg_mentioned_p (reg
, insn
))
379 fprintf (dump_file
, "SMS count_reg found ");
380 print_rtl_single (dump_file
, reg
);
381 fprintf (dump_file
, " outside control in insn:\n");
382 print_rtl_single (dump_file
, insn
);
394 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
395 that the number of iterations is a compile-time constant. If so,
396 return the rtx_insn that sets COUNT_REG to a constant, and set COUNT to
397 this constant. Otherwise return 0. */
399 const_iteration_count (rtx count_reg
, basic_block pre_header
,
403 rtx_insn
*head
, *tail
;
408 get_ebb_head_tail (pre_header
, pre_header
, &head
, &tail
);
410 for (insn
= tail
; insn
!= PREV_INSN (head
); insn
= PREV_INSN (insn
))
411 if (NONDEBUG_INSN_P (insn
) && single_set (insn
) &&
412 rtx_equal_p (count_reg
, SET_DEST (single_set (insn
))))
414 rtx pat
= single_set (insn
);
416 if (CONST_INT_P (SET_SRC (pat
)))
418 *count
= INTVAL (SET_SRC (pat
));
428 /* A very simple resource-based lower bound on the initiation interval.
429 ??? Improve the accuracy of this bound by considering the
430 utilization of various units. */
434 if (targetm
.sched
.sms_res_mii
)
435 return targetm
.sched
.sms_res_mii (g
);
437 return ((g
->num_nodes
- g
->num_debug
) / issue_rate
);
441 /* A vector that contains the sched data for each ps_insn. */
442 static vec
<node_sched_params
> node_sched_param_vec
;
444 /* Allocate sched_params for each node and initialize it. */
446 set_node_sched_params (ddg_ptr g
)
448 node_sched_param_vec
.truncate (0);
449 node_sched_param_vec
.safe_grow_cleared (g
->num_nodes
);
452 /* Make sure that node_sched_param_vec has an entry for every move in PS. */
454 extend_node_sched_params (partial_schedule_ptr ps
)
456 node_sched_param_vec
.safe_grow_cleared (ps
->g
->num_nodes
457 + ps
->reg_moves
.length ());
460 /* Update the sched_params (time, row and stage) for node U using the II,
461 the CYCLE of U and MIN_CYCLE.
462 We're not simply taking the following
463 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
464 because the stages may not be aligned on cycle 0. */
466 update_node_sched_params (int u
, int ii
, int cycle
, int min_cycle
)
468 int sc_until_cycle_zero
;
471 SCHED_TIME (u
) = cycle
;
472 SCHED_ROW (u
) = SMODULO (cycle
, ii
);
474 /* The calculation of stage count is done adding the number
475 of stages before cycle zero and after cycle zero. */
476 sc_until_cycle_zero
= CALC_STAGE_COUNT (-1, min_cycle
, ii
);
478 if (SCHED_TIME (u
) < 0)
480 stage
= CALC_STAGE_COUNT (-1, SCHED_TIME (u
), ii
);
481 SCHED_STAGE (u
) = sc_until_cycle_zero
- stage
;
485 stage
= CALC_STAGE_COUNT (SCHED_TIME (u
), 0, ii
);
486 SCHED_STAGE (u
) = sc_until_cycle_zero
+ stage
- 1;
491 print_node_sched_params (FILE *file
, int num_nodes
, partial_schedule_ptr ps
)
497 for (i
= 0; i
< num_nodes
; i
++)
499 node_sched_params_ptr nsp
= SCHED_PARAMS (i
);
501 fprintf (file
, "Node = %d; INSN = %d\n", i
,
502 INSN_UID (ps_rtl_insn (ps
, i
)));
503 fprintf (file
, " asap = %d:\n", NODE_ASAP (&ps
->g
->nodes
[i
]));
504 fprintf (file
, " time = %d:\n", nsp
->time
);
505 fprintf (file
, " stage = %d:\n", nsp
->stage
);
509 /* Set SCHED_COLUMN for each instruction in row ROW of PS. */
511 set_columns_for_row (partial_schedule_ptr ps
, int row
)
513 ps_insn_ptr cur_insn
;
517 for (cur_insn
= ps
->rows
[row
]; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
518 SCHED_COLUMN (cur_insn
->id
) = column
++;
521 /* Set SCHED_COLUMN for each instruction in PS. */
523 set_columns_for_ps (partial_schedule_ptr ps
)
527 for (row
= 0; row
< ps
->ii
; row
++)
528 set_columns_for_row (ps
, row
);
531 /* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
532 Its single predecessor has already been scheduled, as has its
533 ddg node successors. (The move may have also another move as its
534 successor, in which case that successor will be scheduled later.)
536 The move is part of a chain that satisfies register dependencies
537 between a producing ddg node and various consuming ddg nodes.
538 If some of these dependencies have a distance of 1 (meaning that
539 the use is upward-exposed) then DISTANCE1_USES is nonnull and
540 contains the set of uses with distance-1 dependencies.
541 DISTANCE1_USES is null otherwise.
543 MUST_FOLLOW is a scratch bitmap that is big enough to hold
544 all current ps_insn ids.
546 Return true on success. */
548 schedule_reg_move (partial_schedule_ptr ps
, int i_reg_move
,
549 sbitmap distance1_uses
, sbitmap must_follow
)
552 int this_time
, this_distance
, this_start
, this_end
, this_latency
;
553 int start
, end
, c
, ii
;
554 sbitmap_iterator sbi
;
555 ps_reg_move_info
*move
;
559 move
= ps_reg_move (ps
, i_reg_move
);
563 fprintf (dump_file
, "Scheduling register move INSN %d; ii = %d"
564 ", min cycle = %d\n\n", INSN_UID (move
->insn
), ii
,
566 print_rtl_single (dump_file
, move
->insn
);
567 fprintf (dump_file
, "\n%11s %11s %5s\n", "start", "end", "time");
568 fprintf (dump_file
, "=========== =========== =====\n");
574 /* For dependencies of distance 1 between a producer ddg node A
575 and consumer ddg node B, we have a chain of dependencies:
577 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
579 where Mi is the ith move. For dependencies of distance 0 between
580 a producer ddg node A and consumer ddg node C, we have a chain of
583 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
585 where Mi' occupies the same position as Mi but occurs a stage later.
586 We can only schedule each move once, so if we have both types of
587 chain, we model the second as:
589 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
591 First handle the dependencies between the previously-scheduled
592 predecessor and the move. */
593 this_insn
= ps_rtl_insn (ps
, move
->def
);
594 this_latency
= insn_latency (this_insn
, move
->insn
);
595 this_distance
= distance1_uses
&& move
->def
< ps
->g
->num_nodes
? 1 : 0;
596 this_time
= SCHED_TIME (move
->def
) - this_distance
* ii
;
597 this_start
= this_time
+ this_latency
;
598 this_end
= this_time
+ ii
;
600 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
601 this_start
, this_end
, SCHED_TIME (move
->def
),
602 INSN_UID (this_insn
), this_latency
, this_distance
,
603 INSN_UID (move
->insn
));
605 if (start
< this_start
)
610 /* Handle the dependencies between the move and previously-scheduled
612 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, u
, sbi
)
614 this_insn
= ps_rtl_insn (ps
, u
);
615 this_latency
= insn_latency (move
->insn
, this_insn
);
616 if (distance1_uses
&& !bitmap_bit_p (distance1_uses
, u
))
620 this_time
= SCHED_TIME (u
) + this_distance
* ii
;
621 this_start
= this_time
- ii
;
622 this_end
= this_time
- this_latency
;
624 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
625 this_start
, this_end
, SCHED_TIME (u
), INSN_UID (move
->insn
),
626 this_latency
, this_distance
, INSN_UID (this_insn
));
628 if (start
< this_start
)
636 fprintf (dump_file
, "----------- ----------- -----\n");
637 fprintf (dump_file
, "%11d %11d %5s %s\n", start
, end
, "", "(max, min)");
640 bitmap_clear (must_follow
);
641 bitmap_set_bit (must_follow
, move
->def
);
643 start
= MAX (start
, end
- (ii
- 1));
644 for (c
= end
; c
>= start
; c
--)
646 psi
= ps_add_node_check_conflicts (ps
, i_reg_move
, c
,
647 move
->uses
, must_follow
);
650 update_node_sched_params (i_reg_move
, ii
, c
, PS_MIN_CYCLE (ps
));
652 fprintf (dump_file
, "\nScheduled register move INSN %d at"
653 " time %d, row %d\n\n", INSN_UID (move
->insn
), c
,
654 SCHED_ROW (i_reg_move
));
660 fprintf (dump_file
, "\nNo available slot\n\n");
666 Breaking intra-loop register anti-dependences:
667 Each intra-loop register anti-dependence implies a cross-iteration true
668 dependence of distance 1. Therefore, we can remove such false dependencies
669 and figure out if the partial schedule broke them by checking if (for a
670 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
671 if so generate a register move. The number of such moves is equal to:
672 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
673 nreg_moves = ----------------------------------- + 1 - { dependence.
677 schedule_reg_moves (partial_schedule_ptr ps
)
683 for (i
= 0; i
< g
->num_nodes
; i
++)
685 ddg_node_ptr u
= &g
->nodes
[i
];
687 int nreg_moves
= 0, i_reg_move
;
688 rtx prev_reg
, old_reg
;
692 sbitmap distance1_uses
;
693 rtx set
= single_set (u
->insn
);
695 /* Skip instructions that do not set a register. */
696 if ((set
&& !REG_P (SET_DEST (set
))))
699 /* Compute the number of reg_moves needed for u, by looking at life
700 ranges started at u (excluding self-loops). */
701 distances
[0] = distances
[1] = false;
702 for (e
= u
->out
; e
; e
= e
->next_out
)
703 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
705 int nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
706 - SCHED_TIME (e
->src
->cuid
)) / ii
;
708 if (e
->distance
== 1)
709 nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
710 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
712 /* If dest precedes src in the schedule of the kernel, then dest
713 will read before src writes and we can save one reg_copy. */
714 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
715 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
718 if (nreg_moves4e
>= 1)
720 /* !single_set instructions are not supported yet and
721 thus we do not except to encounter them in the loop
722 except from the doloop part. For the latter case
723 we assume no regmoves are generated as the doloop
724 instructions are tied to the branch with an edge. */
726 /* If the instruction contains auto-inc register then
727 validate that the regmov is being generated for the
728 target regsiter rather then the inc'ed register. */
729 gcc_assert (!autoinc_var_is_used_p (u
->insn
, e
->dest
->insn
));
734 gcc_assert (e
->distance
< 2);
735 distances
[e
->distance
] = true;
737 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
743 /* Create NREG_MOVES register moves. */
744 first_move
= ps
->reg_moves
.length ();
745 ps
->reg_moves
.safe_grow_cleared (first_move
+ nreg_moves
);
746 extend_node_sched_params (ps
);
748 /* Record the moves associated with this node. */
749 first_move
+= ps
->g
->num_nodes
;
751 /* Generate each move. */
752 old_reg
= prev_reg
= SET_DEST (single_set (u
->insn
));
753 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
755 ps_reg_move_info
*move
= ps_reg_move (ps
, first_move
+ i_reg_move
);
757 move
->def
= i_reg_move
> 0 ? first_move
+ i_reg_move
- 1 : i
;
758 move
->uses
= sbitmap_alloc (first_move
+ nreg_moves
);
759 move
->old_reg
= old_reg
;
760 move
->new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
761 move
->num_consecutive_stages
= distances
[0] && distances
[1] ? 2 : 1;
762 move
->insn
= as_a
<rtx_insn
*> (gen_move_insn (move
->new_reg
,
763 copy_rtx (prev_reg
)));
764 bitmap_clear (move
->uses
);
766 prev_reg
= move
->new_reg
;
769 distance1_uses
= distances
[1] ? sbitmap_alloc (g
->num_nodes
) : NULL
;
772 bitmap_clear (distance1_uses
);
774 /* Every use of the register defined by node may require a different
775 copy of this register, depending on the time the use is scheduled.
776 Record which uses require which move results. */
777 for (e
= u
->out
; e
; e
= e
->next_out
)
778 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
780 int dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
781 - SCHED_TIME (e
->src
->cuid
)) / ii
;
783 if (e
->distance
== 1)
784 dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
785 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
787 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
788 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
793 ps_reg_move_info
*move
;
795 move
= ps_reg_move (ps
, first_move
+ dest_copy
- 1);
796 bitmap_set_bit (move
->uses
, e
->dest
->cuid
);
797 if (e
->distance
== 1)
798 bitmap_set_bit (distance1_uses
, e
->dest
->cuid
);
802 must_follow
= sbitmap_alloc (first_move
+ nreg_moves
);
803 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
804 if (!schedule_reg_move (ps
, first_move
+ i_reg_move
,
805 distance1_uses
, must_follow
))
807 sbitmap_free (must_follow
);
809 sbitmap_free (distance1_uses
);
810 if (i_reg_move
< nreg_moves
)
816 /* Emit the moves associatied with PS. Apply the substitutions
817 associated with them. */
819 apply_reg_moves (partial_schedule_ptr ps
)
821 ps_reg_move_info
*move
;
824 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
827 sbitmap_iterator sbi
;
829 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, i_use
, sbi
)
831 replace_rtx (ps
->g
->nodes
[i_use
].insn
, move
->old_reg
, move
->new_reg
);
832 df_insn_rescan (ps
->g
->nodes
[i_use
].insn
);
837 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
838 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
839 will move to cycle zero. */
841 reset_sched_times (partial_schedule_ptr ps
, int amount
)
845 ps_insn_ptr crr_insn
;
847 for (row
= 0; row
< ii
; row
++)
848 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
850 int u
= crr_insn
->id
;
851 int normalized_time
= SCHED_TIME (u
) - amount
;
852 int new_min_cycle
= PS_MIN_CYCLE (ps
) - amount
;
856 /* Print the scheduling times after the rotation. */
857 rtx_insn
*insn
= ps_rtl_insn (ps
, u
);
859 fprintf (dump_file
, "crr_insn->node=%d (insn id %d), "
860 "crr_insn->cycle=%d, min_cycle=%d", u
,
861 INSN_UID (insn
), normalized_time
, new_min_cycle
);
863 fprintf (dump_file
, " (branch)");
864 fprintf (dump_file
, "\n");
867 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
868 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
870 crr_insn
->cycle
= normalized_time
;
871 update_node_sched_params (u
, ii
, normalized_time
, new_min_cycle
);
875 /* Permute the insns according to their order in PS, from row 0 to
876 row ii-1, and position them right before LAST. This schedules
877 the insns of the loop kernel. */
879 permute_partial_schedule (partial_schedule_ptr ps
, rtx_insn
*last
)
885 for (row
= 0; row
< ii
; row
++)
886 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
888 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_ij
->id
);
890 if (PREV_INSN (last
) != insn
)
892 if (ps_ij
->id
< ps
->g
->num_nodes
)
893 reorder_insns_nobb (ps_first_note (ps
, ps_ij
->id
), insn
,
896 add_insn_before (insn
, last
, NULL
);
901 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
902 respectively only if cycle C falls on the border of the scheduling
903 window boundaries marked by START and END cycles. STEP is the
904 direction of the window. */
906 set_must_precede_follow (sbitmap
*tmp_follow
, sbitmap must_follow
,
907 sbitmap
*tmp_precede
, sbitmap must_precede
, int c
,
908 int start
, int end
, int step
)
916 *tmp_precede
= must_precede
;
917 else /* step == -1. */
918 *tmp_follow
= must_follow
;
923 *tmp_follow
= must_follow
;
924 else /* step == -1. */
925 *tmp_precede
= must_precede
;
930 /* Return True if the branch can be moved to row ii-1 while
931 normalizing the partial schedule PS to start from cycle zero and thus
932 optimize the SC. Otherwise return False. */
934 optimize_sc (partial_schedule_ptr ps
, ddg_ptr g
)
936 int amount
= PS_MIN_CYCLE (ps
);
937 sbitmap sched_nodes
= sbitmap_alloc (g
->num_nodes
);
938 int start
, end
, step
;
941 int stage_count
, stage_count_curr
;
943 /* Compare the SC after normalization and SC after bringing the branch
944 to row ii-1. If they are equal just bail out. */
945 stage_count
= calculate_stage_count (ps
, amount
);
947 calculate_stage_count (ps
, SCHED_TIME (g
->closing_branch
->cuid
) - (ii
- 1));
949 if (stage_count
== stage_count_curr
)
952 fprintf (dump_file
, "SMS SC already optimized.\n");
960 fprintf (dump_file
, "SMS Trying to optimize branch location\n");
961 fprintf (dump_file
, "SMS partial schedule before trial:\n");
962 print_partial_schedule (ps
, dump_file
);
965 /* First, normalize the partial scheduling. */
966 reset_sched_times (ps
, amount
);
967 rotate_partial_schedule (ps
, amount
);
971 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
973 print_partial_schedule (ps
, dump_file
);
976 if (SMODULO (SCHED_TIME (g
->closing_branch
->cuid
), ii
) == ii
- 1)
982 bitmap_ones (sched_nodes
);
984 /* Calculate the new placement of the branch. It should be in row
985 ii-1 and fall into it's scheduling window. */
986 if (get_sched_window (ps
, g
->closing_branch
, sched_nodes
, ii
, &start
,
990 ps_insn_ptr next_ps_i
;
991 int branch_cycle
= SCHED_TIME (g
->closing_branch
->cuid
);
992 int row
= SMODULO (branch_cycle
, ps
->ii
);
994 sbitmap must_precede
, must_follow
, tmp_precede
, tmp_follow
;
998 fprintf (dump_file
, "\nTrying to schedule node %d "
999 "INSN = %d in (%d .. %d) step %d\n",
1000 g
->closing_branch
->cuid
,
1001 (INSN_UID (g
->closing_branch
->insn
)), start
, end
, step
);
1003 gcc_assert ((step
> 0 && start
< end
) || (step
< 0 && start
> end
));
1006 c
= start
+ ii
- SMODULO (start
, ii
) - 1;
1007 gcc_assert (c
>= start
);
1013 "SMS failed to schedule branch at cycle: %d\n", c
);
1019 c
= start
- SMODULO (start
, ii
) - 1;
1020 gcc_assert (c
<= start
);
1026 "SMS failed to schedule branch at cycle: %d\n", c
);
1032 must_precede
= sbitmap_alloc (g
->num_nodes
);
1033 must_follow
= sbitmap_alloc (g
->num_nodes
);
1035 /* Try to schedule the branch is it's new cycle. */
1036 calculate_must_precede_follow (g
->closing_branch
, start
, end
,
1037 step
, ii
, sched_nodes
,
1038 must_precede
, must_follow
);
1040 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1041 must_precede
, c
, start
, end
, step
);
1043 /* Find the element in the partial schedule related to the closing
1044 branch so we can remove it from it's current cycle. */
1045 for (next_ps_i
= ps
->rows
[row
];
1046 next_ps_i
; next_ps_i
= next_ps_i
->next_in_row
)
1047 if (next_ps_i
->id
== g
->closing_branch
->cuid
)
1050 remove_node_from_ps (ps
, next_ps_i
);
1052 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
, c
,
1053 sched_nodes
, &num_splits
,
1054 tmp_precede
, tmp_follow
);
1055 gcc_assert (num_splits
== 0);
1060 "SMS failed to schedule branch at cycle: %d, "
1061 "bringing it back to cycle %d\n", c
, branch_cycle
);
1063 /* The branch was failed to be placed in row ii - 1.
1064 Put it back in it's original place in the partial
1066 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1067 must_precede
, branch_cycle
, start
, end
,
1070 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
,
1071 branch_cycle
, sched_nodes
,
1072 &num_splits
, tmp_precede
,
1074 gcc_assert (success
&& (num_splits
== 0));
1079 /* The branch is placed in row ii - 1. */
1082 "SMS success in moving branch to cycle %d\n", c
);
1084 update_node_sched_params (g
->closing_branch
->cuid
, ii
, c
,
1089 free (must_precede
);
1099 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
1100 int to_stage
, rtx count_reg
)
1105 for (row
= 0; row
< ps
->ii
; row
++)
1106 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
1109 int first_u
, last_u
;
1112 /* Do not duplicate any insn which refers to count_reg as it
1113 belongs to the control part.
1114 The closing branch is scheduled as well and thus should
1116 TODO: This should be done by analyzing the control part of
1118 u_insn
= ps_rtl_insn (ps
, u
);
1119 if (reg_mentioned_p (count_reg
, u_insn
)
1123 first_u
= SCHED_STAGE (u
);
1124 last_u
= first_u
+ ps_num_consecutive_stages (ps
, u
) - 1;
1125 if (from_stage
<= last_u
&& to_stage
>= first_u
)
1127 if (u
< ps
->g
->num_nodes
)
1128 duplicate_insn_chain (ps_first_note (ps
, u
), u_insn
);
1130 emit_insn (copy_rtx (PATTERN (u_insn
)));
1136 /* Generate the instructions (including reg_moves) for prolog & epilog. */
1138 generate_prolog_epilog (partial_schedule_ptr ps
, struct loop
*loop
,
1139 rtx count_reg
, rtx count_init
)
1142 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
1145 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1150 /* Generate instructions at the beginning of the prolog to
1151 adjust the loop count by STAGE_COUNT. If loop count is constant
1152 (count_init), this constant is adjusted by STAGE_COUNT in
1153 generate_prolog_epilog function. */
1154 rtx sub_reg
= NULL_RTX
;
1156 sub_reg
= expand_simple_binop (GET_MODE (count_reg
), MINUS
, count_reg
,
1157 gen_int_mode (last_stage
,
1158 GET_MODE (count_reg
)),
1159 count_reg
, 1, OPTAB_DIRECT
);
1160 gcc_assert (REG_P (sub_reg
));
1161 if (REGNO (sub_reg
) != REGNO (count_reg
))
1162 emit_move_insn (count_reg
, sub_reg
);
1165 for (i
= 0; i
< last_stage
; i
++)
1166 duplicate_insns_of_cycles (ps
, 0, i
, count_reg
);
1168 /* Put the prolog on the entry edge. */
1169 e
= loop_preheader_edge (loop
);
1170 split_edge_and_insert (e
, get_insns ());
1171 if (!flag_resched_modulo_sched
)
1172 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1176 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1179 for (i
= 0; i
< last_stage
; i
++)
1180 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, count_reg
);
1182 /* Put the epilogue on the exit edge. */
1183 gcc_assert (single_exit (loop
));
1184 e
= single_exit (loop
);
1185 split_edge_and_insert (e
, get_insns ());
1186 if (!flag_resched_modulo_sched
)
1187 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1192 /* Mark LOOP as software pipelined so the later
1193 scheduling passes don't touch it. */
1195 mark_loop_unsched (struct loop
*loop
)
1198 basic_block
*bbs
= get_loop_body (loop
);
1200 for (i
= 0; i
< loop
->num_nodes
; i
++)
1201 bbs
[i
]->flags
|= BB_DISABLE_SCHEDULE
;
1206 /* Return true if all the BBs of the loop are empty except the
1209 loop_single_full_bb_p (struct loop
*loop
)
1212 basic_block
*bbs
= get_loop_body (loop
);
1214 for (i
= 0; i
< loop
->num_nodes
; i
++)
1216 rtx_insn
*head
, *tail
;
1217 bool empty_bb
= true;
1219 if (bbs
[i
] == loop
->header
)
1222 /* Make sure that basic blocks other than the header
1223 have only notes labels or jumps. */
1224 get_ebb_head_tail (bbs
[i
], bbs
[i
], &head
, &tail
);
1225 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
1227 if (NOTE_P (head
) || LABEL_P (head
)
1228 || (INSN_P (head
) && (DEBUG_INSN_P (head
) || JUMP_P (head
))))
1244 /* Dump file:line from INSN's location info to dump_file. */
1247 dump_insn_location (rtx_insn
*insn
)
1249 if (dump_file
&& INSN_HAS_LOCATION (insn
))
1251 expanded_location xloc
= insn_location (insn
);
1252 fprintf (dump_file
, " %s:%i", xloc
.file
, xloc
.line
);
1256 /* A simple loop from SMS point of view; it is a loop that is composed of
1257 either a single basic block or two BBs - a header and a latch. */
1258 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1259 && (EDGE_COUNT (loop->latch->preds) == 1) \
1260 && (EDGE_COUNT (loop->latch->succs) == 1))
1262 /* Return true if the loop is in its canonical form and false if not.
1263 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1265 loop_canon_p (struct loop
*loop
)
1268 if (loop
->inner
|| !loop_outer (loop
))
1271 fprintf (dump_file
, "SMS loop inner or !loop_outer\n");
1275 if (!single_exit (loop
))
1279 rtx_insn
*insn
= BB_END (loop
->header
);
1281 fprintf (dump_file
, "SMS loop many exits");
1282 dump_insn_location (insn
);
1283 fprintf (dump_file
, "\n");
1288 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
1292 rtx_insn
*insn
= BB_END (loop
->header
);
1294 fprintf (dump_file
, "SMS loop many BBs.");
1295 dump_insn_location (insn
);
1296 fprintf (dump_file
, "\n");
1304 /* If there are more than one entry for the loop,
1305 make it one by splitting the first entry edge and
1306 redirecting the others to the new BB. */
1308 canon_loop (struct loop
*loop
)
1313 /* Avoid annoying special cases of edges going to exit
1315 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1316 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
1319 if (loop
->latch
== loop
->header
1320 || EDGE_COUNT (loop
->latch
->succs
) > 1)
1322 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
1323 if (e
->src
== loop
->latch
)
1331 setup_sched_infos (void)
1333 memcpy (&sms_common_sched_info
, &haifa_common_sched_info
,
1334 sizeof (sms_common_sched_info
));
1335 sms_common_sched_info
.sched_pass_id
= SCHED_SMS_PASS
;
1336 common_sched_info
= &sms_common_sched_info
;
1338 sched_deps_info
= &sms_sched_deps_info
;
1339 current_sched_info
= &sms_sched_info
;
1342 /* Probability in % that the sms-ed loop rolls enough so that optimized
1343 version may be entered. Just a guess. */
1344 #define PROB_SMS_ENOUGH_ITERATIONS 80
1346 /* Used to calculate the upper bound of ii. */
1347 #define MAXII_FACTOR 2
1349 /* Main entry point, perform SMS scheduling on the loops of the function
1350 that consist of single basic blocks. */
1357 int maxii
, max_asap
;
1358 partial_schedule_ptr ps
;
1359 basic_block bb
= NULL
;
1361 basic_block condition_bb
= NULL
;
1363 gcov_type trip_count
= 0;
1365 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1366 | LOOPS_HAVE_RECORDED_EXITS
);
1367 if (number_of_loops (cfun
) <= 1)
1369 loop_optimizer_finalize ();
1370 return; /* There are no loops to schedule. */
1373 /* Initialize issue_rate. */
1374 if (targetm
.sched
.issue_rate
)
1376 int temp
= reload_completed
;
1378 reload_completed
= 1;
1379 issue_rate
= targetm
.sched
.issue_rate ();
1380 reload_completed
= temp
;
1385 /* Initialize the scheduler. */
1386 setup_sched_infos ();
1387 haifa_sched_init ();
1389 /* Allocate memory to hold the DDG array one entry for each loop.
1390 We use loop->num as index into this array. */
1391 g_arr
= XCNEWVEC (ddg_ptr
, number_of_loops (cfun
));
1395 fprintf (dump_file
, "\n\nSMS analysis phase\n");
1396 fprintf (dump_file
, "===================\n\n");
1399 /* Build DDGs for all the relevant loops and hold them in G_ARR
1400 indexed by the loop index. */
1401 FOR_EACH_LOOP (loop
, 0)
1403 rtx_insn
*head
, *tail
;
1406 /* For debugging. */
1407 if (dbg_cnt (sms_sched_loop
) == false)
1410 fprintf (dump_file
, "SMS reached max limit... \n");
1417 rtx_insn
*insn
= BB_END (loop
->header
);
1419 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1420 dump_insn_location (insn
);
1421 fprintf (dump_file
, "\n");
1424 if (! loop_canon_p (loop
))
1427 if (! loop_single_full_bb_p (loop
))
1430 fprintf (dump_file
, "SMS not loop_single_full_bb_p\n");
1436 get_ebb_head_tail (bb
, bb
, &head
, &tail
);
1437 latch_edge
= loop_latch_edge (loop
);
1438 gcc_assert (single_exit (loop
));
1439 if (single_exit (loop
)->count
)
1440 trip_count
= latch_edge
->count
/ single_exit (loop
)->count
;
1442 /* Perform SMS only on loops that their average count is above threshold. */
1444 if ( latch_edge
->count
1445 && (latch_edge
->count
< single_exit (loop
)->count
* SMS_LOOP_AVERAGE_COUNT_THRESHOLD
))
1449 dump_insn_location (tail
);
1450 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1451 if (profile_info
&& flag_branch_probabilities
)
1453 fprintf (dump_file
, "SMS loop-count ");
1454 fprintf (dump_file
, "%"PRId64
,
1455 (int64_t) bb
->count
);
1456 fprintf (dump_file
, "\n");
1457 fprintf (dump_file
, "SMS trip-count ");
1458 fprintf (dump_file
, "%"PRId64
,
1459 (int64_t) trip_count
);
1460 fprintf (dump_file
, "\n");
1461 fprintf (dump_file
, "SMS profile-sum-max ");
1462 fprintf (dump_file
, "%"PRId64
,
1463 (int64_t) profile_info
->sum_max
);
1464 fprintf (dump_file
, "\n");
1470 /* Make sure this is a doloop. */
1471 if ( !(count_reg
= doloop_register_get (head
, tail
)))
1474 fprintf (dump_file
, "SMS doloop_register_get failed\n");
1478 /* Don't handle BBs with calls or barriers
1479 or !single_set with the exception of instructions that include
1480 count_reg---these instructions are part of the control part
1481 that do-loop recognizes.
1482 ??? Should handle insns defining subregs. */
1483 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1489 || (NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1490 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
1491 && !reg_mentioned_p (count_reg
, insn
))
1492 || (INSN_P (insn
) && (set
= single_set (insn
))
1493 && GET_CODE (SET_DEST (set
)) == SUBREG
))
1497 if (insn
!= NEXT_INSN (tail
))
1502 fprintf (dump_file
, "SMS loop-with-call\n");
1503 else if (BARRIER_P (insn
))
1504 fprintf (dump_file
, "SMS loop-with-barrier\n");
1505 else if ((NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1506 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
1507 fprintf (dump_file
, "SMS loop-with-not-single-set\n");
1509 fprintf (dump_file
, "SMS loop with subreg in lhs\n");
1510 print_rtl_single (dump_file
, insn
);
1516 /* Always schedule the closing branch with the rest of the
1517 instructions. The branch is rotated to be in row ii-1 at the
1518 end of the scheduling procedure to make sure it's the last
1519 instruction in the iteration. */
1520 if (! (g
= create_ddg (bb
, 1)))
1523 fprintf (dump_file
, "SMS create_ddg failed\n");
1527 g_arr
[loop
->num
] = g
;
1529 fprintf (dump_file
, "...OK\n");
1534 fprintf (dump_file
, "\nSMS transformation phase\n");
1535 fprintf (dump_file
, "=========================\n\n");
1538 /* We don't want to perform SMS on new loops - created by versioning. */
1539 FOR_EACH_LOOP (loop
, 0)
1541 rtx_insn
*head
, *tail
;
1542 rtx count_reg
, count_init
;
1543 int mii
, rec_mii
, stage_count
, min_cycle
;
1544 int64_t loop_count
= 0;
1547 if (! (g
= g_arr
[loop
->num
]))
1552 rtx_insn
*insn
= BB_END (loop
->header
);
1554 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1555 dump_insn_location (insn
);
1556 fprintf (dump_file
, "\n");
1558 print_ddg (dump_file
, g
);
1561 get_ebb_head_tail (loop
->header
, loop
->header
, &head
, &tail
);
1563 latch_edge
= loop_latch_edge (loop
);
1564 gcc_assert (single_exit (loop
));
1565 if (single_exit (loop
)->count
)
1566 trip_count
= latch_edge
->count
/ single_exit (loop
)->count
;
1570 dump_insn_location (tail
);
1571 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1572 if (profile_info
&& flag_branch_probabilities
)
1574 fprintf (dump_file
, "SMS loop-count ");
1575 fprintf (dump_file
, "%"PRId64
,
1576 (int64_t) bb
->count
);
1577 fprintf (dump_file
, "\n");
1578 fprintf (dump_file
, "SMS profile-sum-max ");
1579 fprintf (dump_file
, "%"PRId64
,
1580 (int64_t) profile_info
->sum_max
);
1581 fprintf (dump_file
, "\n");
1583 fprintf (dump_file
, "SMS doloop\n");
1584 fprintf (dump_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1585 fprintf (dump_file
, "SMS num-loads %d\n", g
->num_loads
);
1586 fprintf (dump_file
, "SMS num-stores %d\n", g
->num_stores
);
1590 /* In case of th loop have doloop register it gets special
1592 count_init
= NULL_RTX
;
1593 if ((count_reg
= doloop_register_get (head
, tail
)))
1595 basic_block pre_header
;
1597 pre_header
= loop_preheader_edge (loop
)->src
;
1598 count_init
= const_iteration_count (count_reg
, pre_header
,
1601 gcc_assert (count_reg
);
1603 if (dump_file
&& count_init
)
1605 fprintf (dump_file
, "SMS const-doloop ");
1606 fprintf (dump_file
, "%"PRId64
,
1608 fprintf (dump_file
, "\n");
1611 node_order
= XNEWVEC (int, g
->num_nodes
);
1613 mii
= 1; /* Need to pass some estimate of mii. */
1614 rec_mii
= sms_order_nodes (g
, mii
, node_order
, &max_asap
);
1615 mii
= MAX (res_MII (g
), rec_mii
);
1616 maxii
= MAX (max_asap
, MAXII_FACTOR
* mii
);
1619 fprintf (dump_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1620 rec_mii
, mii
, maxii
);
1624 set_node_sched_params (g
);
1628 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
);
1632 /* Try to achieve optimized SC by normalizing the partial
1633 schedule (having the cycles start from cycle zero).
1634 The branch location must be placed in row ii-1 in the
1635 final scheduling. If failed, shift all instructions to
1636 position the branch in row ii-1. */
1637 opt_sc_p
= optimize_sc (ps
, g
);
1639 stage_count
= calculate_stage_count (ps
, 0);
1642 /* Bring the branch to cycle ii-1. */
1643 int amount
= (SCHED_TIME (g
->closing_branch
->cuid
)
1647 fprintf (dump_file
, "SMS schedule branch at cycle ii-1\n");
1649 stage_count
= calculate_stage_count (ps
, amount
);
1652 gcc_assert (stage_count
>= 1);
1655 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
1656 1 means that there is no interleaving between iterations thus
1657 we let the scheduling passes do the job in this case. */
1658 if (stage_count
< PARAM_VALUE (PARAM_SMS_MIN_SC
)
1659 || (count_init
&& (loop_count
<= stage_count
))
1660 || (flag_branch_probabilities
&& (trip_count
<= stage_count
)))
1664 fprintf (dump_file
, "SMS failed... \n");
1665 fprintf (dump_file
, "SMS sched-failed (stage-count=%d,"
1666 " loop-count=", stage_count
);
1667 fprintf (dump_file
, "%"PRId64
, loop_count
);
1668 fprintf (dump_file
, ", trip-count=");
1669 fprintf (dump_file
, "%"PRId64
, trip_count
);
1670 fprintf (dump_file
, ")\n");
1677 /* Rotate the partial schedule to have the branch in row ii-1. */
1678 int amount
= SCHED_TIME (g
->closing_branch
->cuid
) - (ps
->ii
- 1);
1680 reset_sched_times (ps
, amount
);
1681 rotate_partial_schedule (ps
, amount
);
1684 set_columns_for_ps (ps
);
1686 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1687 if (!schedule_reg_moves (ps
))
1690 free_partial_schedule (ps
);
1694 /* Moves that handle incoming values might have been added
1695 to a new first stage. Bump the stage count if so.
1697 ??? Perhaps we could consider rotating the schedule here
1699 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1701 reset_sched_times (ps
, 0);
1705 /* The stage count should now be correct without rotation. */
1706 gcc_checking_assert (stage_count
== calculate_stage_count (ps
, 0));
1707 PS_STAGE_COUNT (ps
) = stage_count
;
1713 dump_insn_location (tail
);
1714 fprintf (dump_file
, " SMS succeeded %d %d (with ii, sc)\n",
1715 ps
->ii
, stage_count
);
1716 print_partial_schedule (ps
, dump_file
);
1719 /* case the BCT count is not known , Do loop-versioning */
1720 if (count_reg
&& ! count_init
)
1722 rtx comp_rtx
= gen_rtx_GT (VOIDmode
, count_reg
,
1723 gen_int_mode (stage_count
,
1724 GET_MODE (count_reg
)));
1725 unsigned prob
= (PROB_SMS_ENOUGH_ITERATIONS
1726 * REG_BR_PROB_BASE
) / 100;
1728 loop_version (loop
, comp_rtx
, &condition_bb
,
1729 prob
, prob
, REG_BR_PROB_BASE
- prob
,
1733 /* Set new iteration count of loop kernel. */
1734 if (count_reg
&& count_init
)
1735 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1738 /* Now apply the scheduled kernel to the RTL of the loop. */
1739 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1741 /* Mark this loop as software pipelined so the later
1742 scheduling passes don't touch it. */
1743 if (! flag_resched_modulo_sched
)
1744 mark_loop_unsched (loop
);
1746 /* The life-info is not valid any more. */
1747 df_set_bb_dirty (g
->bb
);
1749 apply_reg_moves (ps
);
1751 print_node_sched_params (dump_file
, g
->num_nodes
, ps
);
1752 /* Generate prolog and epilog. */
1753 generate_prolog_epilog (ps
, loop
, count_reg
, count_init
);
1757 free_partial_schedule (ps
);
1758 node_sched_param_vec
.release ();
1765 /* Release scheduler data, needed until now because of DFA. */
1766 haifa_sched_finish ();
1767 loop_optimizer_finalize ();
1770 /* The SMS scheduling algorithm itself
1771 -----------------------------------
1772 Input: 'O' an ordered list of insns of a loop.
1773 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1775 'Q' is the empty Set
1776 'PS' is the partial schedule; it holds the currently scheduled nodes with
1778 'PSP' previously scheduled predecessors.
1779 'PSS' previously scheduled successors.
1780 't(u)' the cycle where u is scheduled.
1781 'l(u)' is the latency of u.
1782 'd(v,u)' is the dependence distance from v to u.
1783 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1784 the node ordering phase.
1785 'check_hardware_resources_conflicts(u, PS, c)'
1786 run a trace around cycle/slot through DFA model
1787 to check resource conflicts involving instruction u
1788 at cycle c given the partial schedule PS.
1789 'add_to_partial_schedule_at_time(u, PS, c)'
1790 Add the node/instruction u to the partial schedule
1792 'calculate_register_pressure(PS)'
1793 Given a schedule of instructions, calculate the register
1794 pressure it implies. One implementation could be the
1795 maximum number of overlapping live ranges.
1796 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1797 registers available in the hardware.
1801 3. for each node u in O in pre-computed order
1802 4. if (PSP(u) != Q && PSS(u) == Q) then
1803 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1804 6. start = Early_start; end = Early_start + II - 1; step = 1
1805 11. else if (PSP(u) == Q && PSS(u) != Q) then
1806 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1807 13. start = Late_start; end = Late_start - II + 1; step = -1
1808 14. else if (PSP(u) != Q && PSS(u) != Q) then
1809 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1810 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1811 17. start = Early_start;
1812 18. end = min(Early_start + II - 1 , Late_start);
1814 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1815 21. start = ASAP(u); end = start + II - 1; step = 1
1819 24. for (c = start ; c != end ; c += step)
1820 25. if check_hardware_resources_conflicts(u, PS, c) then
1821 26. add_to_partial_schedule_at_time(u, PS, c)
1826 31. if (success == false) then
1828 33. if (II > maxII) then
1829 34. finish - failed to schedule
1834 39. if (calculate_register_pressure(PS) > maxRP) then
1837 42. compute epilogue & prologue
1838 43. finish - succeeded to schedule
1840 ??? The algorithm restricts the scheduling window to II cycles.
1841 In rare cases, it may be better to allow windows of II+1 cycles.
1842 The window would then start and end on the same row, but with
1843 different "must precede" and "must follow" requirements. */
1845 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1846 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1847 set to 0 to save compile time. */
1848 #define DFA_HISTORY SMS_DFA_HISTORY
1850 /* A threshold for the number of repeated unsuccessful attempts to insert
1851 an empty row, before we flush the partial schedule and start over. */
1852 #define MAX_SPLIT_NUM 10
1853 /* Given the partial schedule PS, this function calculates and returns the
1854 cycles in which we can schedule the node with the given index I.
1855 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1856 noticed that there are several cases in which we fail to SMS the loop
1857 because the sched window of a node is empty due to tight data-deps. In
1858 such cases we want to unschedule some of the predecessors/successors
1859 until we get non-empty scheduling window. It returns -1 if the
1860 scheduling window is empty and zero otherwise. */
1863 get_sched_window (partial_schedule_ptr ps
, ddg_node_ptr u_node
,
1864 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
,
1867 int start
, step
, end
;
1868 int early_start
, late_start
;
1870 sbitmap psp
= sbitmap_alloc (ps
->g
->num_nodes
);
1871 sbitmap pss
= sbitmap_alloc (ps
->g
->num_nodes
);
1872 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1873 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1879 /* 1. compute sched window for u (start, end, step). */
1882 psp_not_empty
= bitmap_and (psp
, u_node_preds
, sched_nodes
);
1883 pss_not_empty
= bitmap_and (pss
, u_node_succs
, sched_nodes
);
1885 /* We first compute a forward range (start <= end), then decide whether
1887 early_start
= INT_MIN
;
1888 late_start
= INT_MAX
;
1896 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1898 fprintf (dump_file
, "\nAnalyzing dependencies for node %d (INSN %d)"
1899 "; ii = %d\n\n", u_node
->cuid
, INSN_UID (u_node
->insn
), ii
);
1900 fprintf (dump_file
, "%11s %11s %11s %11s %5s\n",
1901 "start", "early start", "late start", "end", "time");
1902 fprintf (dump_file
, "=========== =========== =========== ==========="
1905 /* Calculate early_start and limit end. Both bounds are inclusive. */
1907 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1909 int v
= e
->src
->cuid
;
1911 if (bitmap_bit_p (sched_nodes
, v
))
1913 int p_st
= SCHED_TIME (v
);
1914 int earliest
= p_st
+ e
->latency
- (e
->distance
* ii
);
1915 int latest
= (e
->data_type
== MEM_DEP
? p_st
+ ii
- 1 : INT_MAX
);
1919 fprintf (dump_file
, "%11s %11d %11s %11d %5d",
1920 "", earliest
, "", latest
, p_st
);
1921 print_ddg_edge (dump_file
, e
);
1922 fprintf (dump_file
, "\n");
1925 early_start
= MAX (early_start
, earliest
);
1926 end
= MIN (end
, latest
);
1928 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1933 /* Calculate late_start and limit start. Both bounds are inclusive. */
1935 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1937 int v
= e
->dest
->cuid
;
1939 if (bitmap_bit_p (sched_nodes
, v
))
1941 int s_st
= SCHED_TIME (v
);
1942 int earliest
= (e
->data_type
== MEM_DEP
? s_st
- ii
+ 1 : INT_MIN
);
1943 int latest
= s_st
- e
->latency
+ (e
->distance
* ii
);
1947 fprintf (dump_file
, "%11d %11s %11d %11s %5d",
1948 earliest
, "", latest
, "", s_st
);
1949 print_ddg_edge (dump_file
, e
);
1950 fprintf (dump_file
, "\n");
1953 start
= MAX (start
, earliest
);
1954 late_start
= MIN (late_start
, latest
);
1956 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1961 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1963 fprintf (dump_file
, "----------- ----------- ----------- -----------"
1965 fprintf (dump_file
, "%11d %11d %11d %11d %5s %s\n",
1966 start
, early_start
, late_start
, end
, "",
1967 "(max, max, min, min)");
1970 /* Get a target scheduling window no bigger than ii. */
1971 if (early_start
== INT_MIN
&& late_start
== INT_MAX
)
1972 early_start
= NODE_ASAP (u_node
);
1973 else if (early_start
== INT_MIN
)
1974 early_start
= late_start
- (ii
- 1);
1975 late_start
= MIN (late_start
, early_start
+ (ii
- 1));
1977 /* Apply memory dependence limits. */
1978 start
= MAX (start
, early_start
);
1979 end
= MIN (end
, late_start
);
1981 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1982 fprintf (dump_file
, "%11s %11d %11d %11s %5s final window\n",
1983 "", start
, end
, "", "");
1985 /* If there are at least as many successors as predecessors, schedule the
1986 node close to its successors. */
1987 if (pss_not_empty
&& count_succs
>= count_preds
)
1995 /* Now that we've finalized the window, make END an exclusive rather
1996 than an inclusive bound. */
2005 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
2008 fprintf (dump_file
, "\nEmpty window: start=%d, end=%d, step=%d\n",
2016 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
2017 node currently been scheduled. At the end of the calculation
2018 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
2019 U_NODE which are (1) already scheduled in the first/last row of
2020 U_NODE's scheduling window, (2) whose dependence inequality with U
2021 becomes an equality when U is scheduled in this same row, and (3)
2022 whose dependence latency is zero.
2024 The first and last rows are calculated using the following parameters:
2025 START/END rows - The cycles that begins/ends the traversal on the window;
2026 searching for an empty cycle to schedule U_NODE.
2027 STEP - The direction in which we traverse the window.
2028 II - The initiation interval. */
2031 calculate_must_precede_follow (ddg_node_ptr u_node
, int start
, int end
,
2032 int step
, int ii
, sbitmap sched_nodes
,
2033 sbitmap must_precede
, sbitmap must_follow
)
2036 int first_cycle_in_window
, last_cycle_in_window
;
2038 gcc_assert (must_precede
&& must_follow
);
2040 /* Consider the following scheduling window:
2041 {first_cycle_in_window, first_cycle_in_window+1, ...,
2042 last_cycle_in_window}. If step is 1 then the following will be
2043 the order we traverse the window: {start=first_cycle_in_window,
2044 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
2045 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
2046 end=first_cycle_in_window-1} if step is -1. */
2047 first_cycle_in_window
= (step
== 1) ? start
: end
- step
;
2048 last_cycle_in_window
= (step
== 1) ? end
- step
: start
;
2050 bitmap_clear (must_precede
);
2051 bitmap_clear (must_follow
);
2054 fprintf (dump_file
, "\nmust_precede: ");
2056 /* Instead of checking if:
2057 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
2058 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
2059 first_cycle_in_window)
2061 we use the fact that latency is non-negative:
2062 SCHED_TIME (e->src) - (e->distance * ii) <=
2063 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
2064 first_cycle_in_window
2066 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
2067 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2068 if (bitmap_bit_p (sched_nodes
, e
->src
->cuid
)
2069 && ((SCHED_TIME (e
->src
->cuid
) - (e
->distance
* ii
)) ==
2070 first_cycle_in_window
))
2073 fprintf (dump_file
, "%d ", e
->src
->cuid
);
2075 bitmap_set_bit (must_precede
, e
->src
->cuid
);
2079 fprintf (dump_file
, "\nmust_follow: ");
2081 /* Instead of checking if:
2082 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
2083 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
2084 last_cycle_in_window)
2086 we use the fact that latency is non-negative:
2087 SCHED_TIME (e->dest) + (e->distance * ii) >=
2088 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
2089 last_cycle_in_window
2091 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
2092 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2093 if (bitmap_bit_p (sched_nodes
, e
->dest
->cuid
)
2094 && ((SCHED_TIME (e
->dest
->cuid
) + (e
->distance
* ii
)) ==
2095 last_cycle_in_window
))
2098 fprintf (dump_file
, "%d ", e
->dest
->cuid
);
2100 bitmap_set_bit (must_follow
, e
->dest
->cuid
);
2104 fprintf (dump_file
, "\n");
2107 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
2108 parameters to decide if that's possible:
2109 PS - The partial schedule.
2110 U - The serial number of U_NODE.
2111 NUM_SPLITS - The number of row splits made so far.
2112 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
2113 the first row of the scheduling window)
2114 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
2115 last row of the scheduling window) */
2118 try_scheduling_node_in_cycle (partial_schedule_ptr ps
,
2119 int u
, int cycle
, sbitmap sched_nodes
,
2120 int *num_splits
, sbitmap must_precede
,
2121 sbitmap must_follow
)
2126 verify_partial_schedule (ps
, sched_nodes
);
2127 psi
= ps_add_node_check_conflicts (ps
, u
, cycle
, must_precede
, must_follow
);
2130 SCHED_TIME (u
) = cycle
;
2131 bitmap_set_bit (sched_nodes
, u
);
2135 fprintf (dump_file
, "Scheduled w/o split in %d\n", cycle
);
2142 /* This function implements the scheduling algorithm for SMS according to the
2144 static partial_schedule_ptr
2145 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
)
2148 int i
, c
, success
, num_splits
= 0;
2149 int flush_and_start_over
= true;
2150 int num_nodes
= g
->num_nodes
;
2151 int start
, end
, step
; /* Place together into one struct? */
2152 sbitmap sched_nodes
= sbitmap_alloc (num_nodes
);
2153 sbitmap must_precede
= sbitmap_alloc (num_nodes
);
2154 sbitmap must_follow
= sbitmap_alloc (num_nodes
);
2155 sbitmap tobe_scheduled
= sbitmap_alloc (num_nodes
);
2157 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
, DFA_HISTORY
);
2159 bitmap_ones (tobe_scheduled
);
2160 bitmap_clear (sched_nodes
);
2162 while (flush_and_start_over
&& (ii
< maxii
))
2166 fprintf (dump_file
, "Starting with ii=%d\n", ii
);
2167 flush_and_start_over
= false;
2168 bitmap_clear (sched_nodes
);
2170 for (i
= 0; i
< num_nodes
; i
++)
2172 int u
= nodes_order
[i
];
2173 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
2174 rtx insn
= u_node
->insn
;
2176 if (!NONDEBUG_INSN_P (insn
))
2178 bitmap_clear_bit (tobe_scheduled
, u
);
2182 if (bitmap_bit_p (sched_nodes
, u
))
2185 /* Try to get non-empty scheduling window. */
2187 if (get_sched_window (ps
, u_node
, sched_nodes
, ii
, &start
,
2191 fprintf (dump_file
, "\nTrying to schedule node %d "
2192 "INSN = %d in (%d .. %d) step %d\n", u
, (INSN_UID
2193 (g
->nodes
[u
].insn
)), start
, end
, step
);
2195 gcc_assert ((step
> 0 && start
< end
)
2196 || (step
< 0 && start
> end
));
2198 calculate_must_precede_follow (u_node
, start
, end
, step
, ii
,
2199 sched_nodes
, must_precede
,
2202 for (c
= start
; c
!= end
; c
+= step
)
2204 sbitmap tmp_precede
, tmp_follow
;
2206 set_must_precede_follow (&tmp_follow
, must_follow
,
2207 &tmp_precede
, must_precede
,
2208 c
, start
, end
, step
);
2210 try_scheduling_node_in_cycle (ps
, u
, c
,
2212 &num_splits
, tmp_precede
,
2218 verify_partial_schedule (ps
, sched_nodes
);
2227 if (num_splits
>= MAX_SPLIT_NUM
)
2230 flush_and_start_over
= true;
2231 verify_partial_schedule (ps
, sched_nodes
);
2232 reset_partial_schedule (ps
, ii
);
2233 verify_partial_schedule (ps
, sched_nodes
);
2238 /* The scheduling window is exclusive of 'end'
2239 whereas compute_split_window() expects an inclusive,
2242 split_row
= compute_split_row (sched_nodes
, start
, end
- 1,
2245 split_row
= compute_split_row (sched_nodes
, end
+ 1, start
,
2248 ps_insert_empty_row (ps
, split_row
, sched_nodes
);
2249 i
--; /* Go back and retry node i. */
2252 fprintf (dump_file
, "num_splits=%d\n", num_splits
);
2255 /* ??? If (success), check register pressure estimates. */
2256 } /* Continue with next node. */
2257 } /* While flush_and_start_over. */
2260 free_partial_schedule (ps
);
2264 gcc_assert (bitmap_equal_p (tobe_scheduled
, sched_nodes
));
2266 sbitmap_free (sched_nodes
);
2267 sbitmap_free (must_precede
);
2268 sbitmap_free (must_follow
);
2269 sbitmap_free (tobe_scheduled
);
2274 /* This function inserts a new empty row into PS at the position
2275 according to SPLITROW, keeping all already scheduled instructions
2276 intact and updating their SCHED_TIME and cycle accordingly. */
2278 ps_insert_empty_row (partial_schedule_ptr ps
, int split_row
,
2279 sbitmap sched_nodes
)
2281 ps_insn_ptr crr_insn
;
2282 ps_insn_ptr
*rows_new
;
2284 int new_ii
= ii
+ 1;
2286 int *rows_length_new
;
2288 verify_partial_schedule (ps
, sched_nodes
);
2290 /* We normalize sched_time and rotate ps to have only non-negative sched
2291 times, for simplicity of updating cycles after inserting new row. */
2292 split_row
-= ps
->min_cycle
;
2293 split_row
= SMODULO (split_row
, ii
);
2295 fprintf (dump_file
, "split_row=%d\n", split_row
);
2297 reset_sched_times (ps
, PS_MIN_CYCLE (ps
));
2298 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
2300 rows_new
= (ps_insn_ptr
*) xcalloc (new_ii
, sizeof (ps_insn_ptr
));
2301 rows_length_new
= (int *) xcalloc (new_ii
, sizeof (int));
2302 for (row
= 0; row
< split_row
; row
++)
2304 rows_new
[row
] = ps
->rows
[row
];
2305 rows_length_new
[row
] = ps
->rows_length
[row
];
2306 ps
->rows
[row
] = NULL
;
2307 for (crr_insn
= rows_new
[row
];
2308 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2310 int u
= crr_insn
->id
;
2311 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
);
2313 SCHED_TIME (u
) = new_time
;
2314 crr_insn
->cycle
= new_time
;
2315 SCHED_ROW (u
) = new_time
% new_ii
;
2316 SCHED_STAGE (u
) = new_time
/ new_ii
;
2321 rows_new
[split_row
] = NULL
;
2323 for (row
= split_row
; row
< ii
; row
++)
2325 rows_new
[row
+ 1] = ps
->rows
[row
];
2326 rows_length_new
[row
+ 1] = ps
->rows_length
[row
];
2327 ps
->rows
[row
] = NULL
;
2328 for (crr_insn
= rows_new
[row
+ 1];
2329 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2331 int u
= crr_insn
->id
;
2332 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
) + 1;
2334 SCHED_TIME (u
) = new_time
;
2335 crr_insn
->cycle
= new_time
;
2336 SCHED_ROW (u
) = new_time
% new_ii
;
2337 SCHED_STAGE (u
) = new_time
/ new_ii
;
2342 ps
->min_cycle
= ps
->min_cycle
+ ps
->min_cycle
/ ii
2343 + (SMODULO (ps
->min_cycle
, ii
) >= split_row
? 1 : 0);
2344 ps
->max_cycle
= ps
->max_cycle
+ ps
->max_cycle
/ ii
2345 + (SMODULO (ps
->max_cycle
, ii
) >= split_row
? 1 : 0);
2347 ps
->rows
= rows_new
;
2348 free (ps
->rows_length
);
2349 ps
->rows_length
= rows_length_new
;
2351 gcc_assert (ps
->min_cycle
>= 0);
2353 verify_partial_schedule (ps
, sched_nodes
);
2356 fprintf (dump_file
, "min_cycle=%d, max_cycle=%d\n", ps
->min_cycle
,
2360 /* Given U_NODE which is the node that failed to be scheduled; LOW and
2361 UP which are the boundaries of it's scheduling window; compute using
2362 SCHED_NODES and II a row in the partial schedule that can be split
2363 which will separate a critical predecessor from a critical successor
2364 thereby expanding the window, and return it. */
2366 compute_split_row (sbitmap sched_nodes
, int low
, int up
, int ii
,
2367 ddg_node_ptr u_node
)
2370 int lower
= INT_MIN
, upper
= INT_MAX
;
2375 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2377 int v
= e
->src
->cuid
;
2379 if (bitmap_bit_p (sched_nodes
, v
)
2380 && (low
== SCHED_TIME (v
) + e
->latency
- (e
->distance
* ii
)))
2381 if (SCHED_TIME (v
) > lower
)
2384 lower
= SCHED_TIME (v
);
2390 crit_cycle
= SCHED_TIME (crit_pred
) + 1;
2391 return SMODULO (crit_cycle
, ii
);
2394 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2396 int v
= e
->dest
->cuid
;
2398 if (bitmap_bit_p (sched_nodes
, v
)
2399 && (up
== SCHED_TIME (v
) - e
->latency
+ (e
->distance
* ii
)))
2400 if (SCHED_TIME (v
) < upper
)
2403 upper
= SCHED_TIME (v
);
2409 crit_cycle
= SCHED_TIME (crit_succ
);
2410 return SMODULO (crit_cycle
, ii
);
2414 fprintf (dump_file
, "Both crit_pred and crit_succ are NULL\n");
2416 return SMODULO ((low
+ up
+ 1) / 2, ii
);
2420 verify_partial_schedule (partial_schedule_ptr ps
, sbitmap sched_nodes
)
2423 ps_insn_ptr crr_insn
;
2425 for (row
= 0; row
< ps
->ii
; row
++)
2429 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2431 int u
= crr_insn
->id
;
2434 gcc_assert (bitmap_bit_p (sched_nodes
, u
));
2435 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2436 popcount (sched_nodes) == number of insns in ps. */
2437 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
2438 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
2441 gcc_assert (ps
->rows_length
[row
] == length
);
2446 /* This page implements the algorithm for ordering the nodes of a DDG
2447 for modulo scheduling, activated through the
2448 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2450 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2451 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
2452 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
2453 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2454 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
2455 #define DEPTH(x) (ASAP ((x)))
2457 typedef struct node_order_params
* nopa
;
2459 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
2460 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
2461 static nopa
calculate_order_params (ddg_ptr
, int, int *);
2462 static int find_max_asap (ddg_ptr
, sbitmap
);
2463 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
2464 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
2466 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
2468 struct node_order_params
2475 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2477 check_nodes_order (int *node_order
, int num_nodes
)
2480 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2485 fprintf (dump_file
, "SMS final nodes order: \n");
2487 for (i
= 0; i
< num_nodes
; i
++)
2489 int u
= node_order
[i
];
2492 fprintf (dump_file
, "%d ", u
);
2493 gcc_assert (u
< num_nodes
&& u
>= 0 && !bitmap_bit_p (tmp
, u
));
2495 bitmap_set_bit (tmp
, u
);
2499 fprintf (dump_file
, "\n");
2504 /* Order the nodes of G for scheduling and pass the result in
2505 NODE_ORDER. Also set aux.count of each node to ASAP.
2506 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2508 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
, int *pmax_asap
)
2512 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
2514 nopa nops
= calculate_order_params (g
, mii
, pmax_asap
);
2517 print_sccs (dump_file
, sccs
, g
);
2519 order_nodes_of_sccs (sccs
, node_order
);
2521 if (sccs
->num_sccs
> 0)
2522 /* First SCC has the largest recurrence_length. */
2523 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
2525 /* Save ASAP before destroying node_order_params. */
2526 for (i
= 0; i
< g
->num_nodes
; i
++)
2528 ddg_node_ptr v
= &g
->nodes
[i
];
2529 v
->aux
.count
= ASAP (v
);
2533 free_ddg_all_sccs (sccs
);
2534 check_nodes_order (node_order
, g
->num_nodes
);
2540 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
2543 ddg_ptr g
= all_sccs
->ddg
;
2544 int num_nodes
= g
->num_nodes
;
2545 sbitmap prev_sccs
= sbitmap_alloc (num_nodes
);
2546 sbitmap on_path
= sbitmap_alloc (num_nodes
);
2547 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2548 sbitmap ones
= sbitmap_alloc (num_nodes
);
2550 bitmap_clear (prev_sccs
);
2553 /* Perform the node ordering starting from the SCC with the highest recMII.
2554 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2555 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
2557 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
2559 /* Add nodes on paths from previous SCCs to the current SCC. */
2560 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
2561 bitmap_ior (tmp
, scc
->nodes
, on_path
);
2563 /* Add nodes on paths from the current SCC to previous SCCs. */
2564 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
2565 bitmap_ior (tmp
, tmp
, on_path
);
2567 /* Remove nodes of previous SCCs from current extended SCC. */
2568 bitmap_and_compl (tmp
, tmp
, prev_sccs
);
2570 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2571 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2574 /* Handle the remaining nodes that do not belong to any scc. Each call
2575 to order_nodes_in_scc handles a single connected component. */
2576 while (pos
< g
->num_nodes
)
2578 bitmap_and_compl (tmp
, ones
, prev_sccs
);
2579 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2581 sbitmap_free (prev_sccs
);
2582 sbitmap_free (on_path
);
2584 sbitmap_free (ones
);
2587 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2588 static struct node_order_params
*
2589 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
, int *pmax_asap
)
2593 int num_nodes
= g
->num_nodes
;
2595 /* Allocate a place to hold ordering params for each node in the DDG. */
2596 nopa node_order_params_arr
;
2598 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2599 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
2600 sizeof (struct node_order_params
));
2602 /* Set the aux pointer of each node to point to its order_params structure. */
2603 for (u
= 0; u
< num_nodes
; u
++)
2604 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
2606 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2607 calculate ASAP, ALAP, mobility, distance, and height for each node
2608 in the dependence (direct acyclic) graph. */
2610 /* We assume that the nodes in the array are in topological order. */
2613 for (u
= 0; u
< num_nodes
; u
++)
2615 ddg_node_ptr u_node
= &g
->nodes
[u
];
2618 for (e
= u_node
->in
; e
; e
= e
->next_in
)
2619 if (e
->distance
== 0)
2620 ASAP (u_node
) = MAX (ASAP (u_node
),
2621 ASAP (e
->src
) + e
->latency
);
2622 max_asap
= MAX (max_asap
, ASAP (u_node
));
2625 for (u
= num_nodes
- 1; u
> -1; u
--)
2627 ddg_node_ptr u_node
= &g
->nodes
[u
];
2629 ALAP (u_node
) = max_asap
;
2630 HEIGHT (u_node
) = 0;
2631 for (e
= u_node
->out
; e
; e
= e
->next_out
)
2632 if (e
->distance
== 0)
2634 ALAP (u_node
) = MIN (ALAP (u_node
),
2635 ALAP (e
->dest
) - e
->latency
);
2636 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
2637 HEIGHT (e
->dest
) + e
->latency
);
2642 fprintf (dump_file
, "\nOrder params\n");
2643 for (u
= 0; u
< num_nodes
; u
++)
2645 ddg_node_ptr u_node
= &g
->nodes
[u
];
2647 fprintf (dump_file
, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u
,
2648 ASAP (u_node
), ALAP (u_node
), HEIGHT (u_node
));
2652 *pmax_asap
= max_asap
;
2653 return node_order_params_arr
;
2657 find_max_asap (ddg_ptr g
, sbitmap nodes
)
2662 sbitmap_iterator sbi
;
2664 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2666 ddg_node_ptr u_node
= &g
->nodes
[u
];
2668 if (max_asap
< ASAP (u_node
))
2670 max_asap
= ASAP (u_node
);
2678 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
2682 int min_mob
= INT_MAX
;
2684 sbitmap_iterator sbi
;
2686 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2688 ddg_node_ptr u_node
= &g
->nodes
[u
];
2690 if (max_hv
< HEIGHT (u_node
))
2692 max_hv
= HEIGHT (u_node
);
2693 min_mob
= MOB (u_node
);
2696 else if ((max_hv
== HEIGHT (u_node
))
2697 && (min_mob
> MOB (u_node
)))
2699 min_mob
= MOB (u_node
);
2707 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
2711 int min_mob
= INT_MAX
;
2713 sbitmap_iterator sbi
;
2715 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2717 ddg_node_ptr u_node
= &g
->nodes
[u
];
2719 if (max_dv
< DEPTH (u_node
))
2721 max_dv
= DEPTH (u_node
);
2722 min_mob
= MOB (u_node
);
2725 else if ((max_dv
== DEPTH (u_node
))
2726 && (min_mob
> MOB (u_node
)))
2728 min_mob
= MOB (u_node
);
2735 /* Places the nodes of SCC into the NODE_ORDER array starting
2736 at position POS, according to the SMS ordering algorithm.
2737 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2738 the NODE_ORDER array, starting from position zero. */
2740 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
2741 int * node_order
, int pos
)
2743 enum sms_direction dir
;
2744 int num_nodes
= g
->num_nodes
;
2745 sbitmap workset
= sbitmap_alloc (num_nodes
);
2746 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2747 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
2748 sbitmap predecessors
= sbitmap_alloc (num_nodes
);
2749 sbitmap successors
= sbitmap_alloc (num_nodes
);
2751 bitmap_clear (predecessors
);
2752 find_predecessors (predecessors
, g
, nodes_ordered
);
2754 bitmap_clear (successors
);
2755 find_successors (successors
, g
, nodes_ordered
);
2758 if (bitmap_and (tmp
, predecessors
, scc
))
2760 bitmap_copy (workset
, tmp
);
2763 else if (bitmap_and (tmp
, successors
, scc
))
2765 bitmap_copy (workset
, tmp
);
2772 bitmap_clear (workset
);
2773 if ((u
= find_max_asap (g
, scc
)) >= 0)
2774 bitmap_set_bit (workset
, u
);
2778 bitmap_clear (zero_bitmap
);
2779 while (!bitmap_equal_p (workset
, zero_bitmap
))
2782 ddg_node_ptr v_node
;
2783 sbitmap v_node_preds
;
2784 sbitmap v_node_succs
;
2788 while (!bitmap_equal_p (workset
, zero_bitmap
))
2790 v
= find_max_hv_min_mob (g
, workset
);
2791 v_node
= &g
->nodes
[v
];
2792 node_order
[pos
++] = v
;
2793 v_node_succs
= NODE_SUCCESSORS (v_node
);
2794 bitmap_and (tmp
, v_node_succs
, scc
);
2796 /* Don't consider the already ordered successors again. */
2797 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2798 bitmap_ior (workset
, workset
, tmp
);
2799 bitmap_clear_bit (workset
, v
);
2800 bitmap_set_bit (nodes_ordered
, v
);
2803 bitmap_clear (predecessors
);
2804 find_predecessors (predecessors
, g
, nodes_ordered
);
2805 bitmap_and (workset
, predecessors
, scc
);
2809 while (!bitmap_equal_p (workset
, zero_bitmap
))
2811 v
= find_max_dv_min_mob (g
, workset
);
2812 v_node
= &g
->nodes
[v
];
2813 node_order
[pos
++] = v
;
2814 v_node_preds
= NODE_PREDECESSORS (v_node
);
2815 bitmap_and (tmp
, v_node_preds
, scc
);
2817 /* Don't consider the already ordered predecessors again. */
2818 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2819 bitmap_ior (workset
, workset
, tmp
);
2820 bitmap_clear_bit (workset
, v
);
2821 bitmap_set_bit (nodes_ordered
, v
);
2824 bitmap_clear (successors
);
2825 find_successors (successors
, g
, nodes_ordered
);
2826 bitmap_and (workset
, successors
, scc
);
2830 sbitmap_free (workset
);
2831 sbitmap_free (zero_bitmap
);
2832 sbitmap_free (predecessors
);
2833 sbitmap_free (successors
);
2838 /* This page contains functions for manipulating partial-schedules during
2839 modulo scheduling. */
2841 /* Create a partial schedule and allocate a memory to hold II rows. */
2843 static partial_schedule_ptr
2844 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2846 partial_schedule_ptr ps
= XNEW (struct partial_schedule
);
2847 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2848 ps
->rows_length
= (int *) xcalloc (ii
, sizeof (int));
2849 ps
->reg_moves
.create (0);
2851 ps
->history
= history
;
2852 ps
->min_cycle
= INT_MAX
;
2853 ps
->max_cycle
= INT_MIN
;
2859 /* Free the PS_INSNs in rows array of the given partial schedule.
2860 ??? Consider caching the PS_INSN's. */
2862 free_ps_insns (partial_schedule_ptr ps
)
2866 for (i
= 0; i
< ps
->ii
; i
++)
2870 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2873 ps
->rows
[i
] = ps_insn
;
2879 /* Free all the memory allocated to the partial schedule. */
2882 free_partial_schedule (partial_schedule_ptr ps
)
2884 ps_reg_move_info
*move
;
2890 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
2891 sbitmap_free (move
->uses
);
2892 ps
->reg_moves
.release ();
2896 free (ps
->rows_length
);
2900 /* Clear the rows array with its PS_INSNs, and create a new one with
2904 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2909 if (new_ii
== ps
->ii
)
2911 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2912 * sizeof (ps_insn_ptr
));
2913 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2914 ps
->rows_length
= (int *) xrealloc (ps
->rows_length
, new_ii
* sizeof (int));
2915 memset (ps
->rows_length
, 0, new_ii
* sizeof (int));
2917 ps
->min_cycle
= INT_MAX
;
2918 ps
->max_cycle
= INT_MIN
;
2921 /* Prints the partial schedule as an ii rows array, for each rows
2922 print the ids of the insns in it. */
2924 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2928 for (i
= 0; i
< ps
->ii
; i
++)
2930 ps_insn_ptr ps_i
= ps
->rows
[i
];
2932 fprintf (dump
, "\n[ROW %d ]: ", i
);
2935 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_i
->id
);
2938 fprintf (dump
, "%d (branch), ", INSN_UID (insn
));
2940 fprintf (dump
, "%d, ", INSN_UID (insn
));
2942 ps_i
= ps_i
->next_in_row
;
2947 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2949 create_ps_insn (int id
, int cycle
)
2951 ps_insn_ptr ps_i
= XNEW (struct ps_insn
);
2954 ps_i
->next_in_row
= NULL
;
2955 ps_i
->prev_in_row
= NULL
;
2956 ps_i
->cycle
= cycle
;
2962 /* Removes the given PS_INSN from the partial schedule. */
2964 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2968 gcc_assert (ps
&& ps_i
);
2970 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2971 if (! ps_i
->prev_in_row
)
2973 gcc_assert (ps_i
== ps
->rows
[row
]);
2974 ps
->rows
[row
] = ps_i
->next_in_row
;
2976 ps
->rows
[row
]->prev_in_row
= NULL
;
2980 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
2981 if (ps_i
->next_in_row
)
2982 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
2985 ps
->rows_length
[row
] -= 1;
2990 /* Unlike what literature describes for modulo scheduling (which focuses
2991 on VLIW machines) the order of the instructions inside a cycle is
2992 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2993 where the current instruction should go relative to the already
2994 scheduled instructions in the given cycle. Go over these
2995 instructions and find the first possible column to put it in. */
2997 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2998 sbitmap must_precede
, sbitmap must_follow
)
3000 ps_insn_ptr next_ps_i
;
3001 ps_insn_ptr first_must_follow
= NULL
;
3002 ps_insn_ptr last_must_precede
= NULL
;
3003 ps_insn_ptr last_in_row
= NULL
;
3009 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3011 /* Find the first must follow and the last must precede
3012 and insert the node immediately after the must precede
3013 but make sure that it there is no must follow after it. */
3014 for (next_ps_i
= ps
->rows
[row
];
3016 next_ps_i
= next_ps_i
->next_in_row
)
3019 && bitmap_bit_p (must_follow
, next_ps_i
->id
)
3020 && ! first_must_follow
)
3021 first_must_follow
= next_ps_i
;
3022 if (must_precede
&& bitmap_bit_p (must_precede
, next_ps_i
->id
))
3024 /* If we have already met a node that must follow, then
3025 there is no possible column. */
3026 if (first_must_follow
)
3029 last_must_precede
= next_ps_i
;
3031 /* The closing branch must be the last in the row. */
3033 && bitmap_bit_p (must_precede
, next_ps_i
->id
)
3034 && JUMP_P (ps_rtl_insn (ps
, next_ps_i
->id
)))
3037 last_in_row
= next_ps_i
;
3040 /* The closing branch is scheduled as well. Make sure there is no
3041 dependent instruction after it as the branch should be the last
3042 instruction in the row. */
3043 if (JUMP_P (ps_rtl_insn (ps
, ps_i
->id
)))
3045 if (first_must_follow
)
3049 /* Make the branch the last in the row. New instructions
3050 will be inserted at the beginning of the row or after the
3051 last must_precede instruction thus the branch is guaranteed
3052 to remain the last instruction in the row. */
3053 last_in_row
->next_in_row
= ps_i
;
3054 ps_i
->prev_in_row
= last_in_row
;
3055 ps_i
->next_in_row
= NULL
;
3058 ps
->rows
[row
] = ps_i
;
3062 /* Now insert the node after INSERT_AFTER_PSI. */
3064 if (! last_must_precede
)
3066 ps_i
->next_in_row
= ps
->rows
[row
];
3067 ps_i
->prev_in_row
= NULL
;
3068 if (ps_i
->next_in_row
)
3069 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3070 ps
->rows
[row
] = ps_i
;
3074 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
3075 last_must_precede
->next_in_row
= ps_i
;
3076 ps_i
->prev_in_row
= last_must_precede
;
3077 if (ps_i
->next_in_row
)
3078 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3084 /* Advances the PS_INSN one column in its current row; returns false
3085 in failure and true in success. Bit N is set in MUST_FOLLOW if
3086 the node with cuid N must be come after the node pointed to by
3087 PS_I when scheduled in the same cycle. */
3089 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
3090 sbitmap must_follow
)
3092 ps_insn_ptr prev
, next
;
3098 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3100 if (! ps_i
->next_in_row
)
3103 /* Check if next_in_row is dependent on ps_i, both having same sched
3104 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
3105 if (must_follow
&& bitmap_bit_p (must_follow
, ps_i
->next_in_row
->id
))
3108 /* Advance PS_I over its next_in_row in the doubly linked list. */
3109 prev
= ps_i
->prev_in_row
;
3110 next
= ps_i
->next_in_row
;
3112 if (ps_i
== ps
->rows
[row
])
3113 ps
->rows
[row
] = next
;
3115 ps_i
->next_in_row
= next
->next_in_row
;
3117 if (next
->next_in_row
)
3118 next
->next_in_row
->prev_in_row
= ps_i
;
3120 next
->next_in_row
= ps_i
;
3121 ps_i
->prev_in_row
= next
;
3123 next
->prev_in_row
= prev
;
3125 prev
->next_in_row
= next
;
3130 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
3131 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
3132 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
3133 before/after (respectively) the node pointed to by PS_I when scheduled
3134 in the same cycle. */
3136 add_node_to_ps (partial_schedule_ptr ps
, int id
, int cycle
,
3137 sbitmap must_precede
, sbitmap must_follow
)
3140 int row
= SMODULO (cycle
, ps
->ii
);
3142 if (ps
->rows_length
[row
] >= issue_rate
)
3145 ps_i
= create_ps_insn (id
, cycle
);
3147 /* Finds and inserts PS_I according to MUST_FOLLOW and
3149 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
3155 ps
->rows_length
[row
] += 1;
3159 /* Advance time one cycle. Assumes DFA is being used. */
3161 advance_one_cycle (void)
3163 if (targetm
.sched
.dfa_pre_cycle_insn
)
3164 state_transition (curr_state
,
3165 targetm
.sched
.dfa_pre_cycle_insn ());
3167 state_transition (curr_state
, NULL
);
3169 if (targetm
.sched
.dfa_post_cycle_insn
)
3170 state_transition (curr_state
,
3171 targetm
.sched
.dfa_post_cycle_insn ());
3176 /* Checks if PS has resource conflicts according to DFA, starting from
3177 FROM cycle to TO cycle; returns true if there are conflicts and false
3178 if there are no conflicts. Assumes DFA is being used. */
3180 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
3184 state_reset (curr_state
);
3186 for (cycle
= from
; cycle
<= to
; cycle
++)
3188 ps_insn_ptr crr_insn
;
3189 /* Holds the remaining issue slots in the current row. */
3190 int can_issue_more
= issue_rate
;
3192 /* Walk through the DFA for the current row. */
3193 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
3195 crr_insn
= crr_insn
->next_in_row
)
3197 rtx_insn
*insn
= ps_rtl_insn (ps
, crr_insn
->id
);
3199 if (!NONDEBUG_INSN_P (insn
))
3202 /* Check if there is room for the current insn. */
3203 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
3206 /* Update the DFA state and return with failure if the DFA found
3207 resource conflicts. */
3208 if (state_transition (curr_state
, insn
) >= 0)
3211 if (targetm
.sched
.variable_issue
)
3213 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
3214 insn
, can_issue_more
);
3215 /* A naked CLOBBER or USE generates no instruction, so don't
3216 let them consume issue slots. */
3217 else if (GET_CODE (PATTERN (insn
)) != USE
3218 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3222 /* Advance the DFA to the next cycle. */
3223 advance_one_cycle ();
3228 /* Checks if the given node causes resource conflicts when added to PS at
3229 cycle C. If not the node is added to PS and returned; otherwise zero
3230 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
3231 cuid N must be come before/after (respectively) the node pointed to by
3232 PS_I when scheduled in the same cycle. */
3234 ps_add_node_check_conflicts (partial_schedule_ptr ps
, int n
,
3235 int c
, sbitmap must_precede
,
3236 sbitmap must_follow
)
3238 int has_conflicts
= 0;
3241 /* First add the node to the PS, if this succeeds check for
3242 conflicts, trying different issue slots in the same row. */
3243 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
3244 return NULL
; /* Failed to insert the node at the given cycle. */
3246 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3248 && ps_has_conflicts (ps
,
3252 /* Try different issue slots to find one that the given node can be
3253 scheduled in without conflicts. */
3254 while (has_conflicts
)
3256 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
3258 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3260 && ps_has_conflicts (ps
,
3267 remove_node_from_ps (ps
, ps_i
);
3271 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
3272 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
3276 /* Calculate the stage count of the partial schedule PS. The calculation
3277 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3279 calculate_stage_count (partial_schedule_ptr ps
, int rotation_amount
)
3281 int new_min_cycle
= PS_MIN_CYCLE (ps
) - rotation_amount
;
3282 int new_max_cycle
= PS_MAX_CYCLE (ps
) - rotation_amount
;
3283 int stage_count
= CALC_STAGE_COUNT (-1, new_min_cycle
, ps
->ii
);
3285 /* The calculation of stage count is done adding the number of stages
3286 before cycle zero and after cycle zero. */
3287 stage_count
+= CALC_STAGE_COUNT (new_max_cycle
, 0, ps
->ii
);
3292 /* Rotate the rows of PS such that insns scheduled at time
3293 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3295 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
3297 int i
, row
, backward_rotates
;
3298 int last_row
= ps
->ii
- 1;
3300 if (start_cycle
== 0)
3303 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
3305 /* Revisit later and optimize this into a single loop. */
3306 for (i
= 0; i
< backward_rotates
; i
++)
3308 ps_insn_ptr first_row
= ps
->rows
[0];
3309 int first_row_length
= ps
->rows_length
[0];
3311 for (row
= 0; row
< last_row
; row
++)
3313 ps
->rows
[row
] = ps
->rows
[row
+ 1];
3314 ps
->rows_length
[row
] = ps
->rows_length
[row
+ 1];
3317 ps
->rows
[last_row
] = first_row
;
3318 ps
->rows_length
[last_row
] = first_row_length
;
3321 ps
->max_cycle
-= start_cycle
;
3322 ps
->min_cycle
-= start_cycle
;
3325 #endif /* INSN_SCHEDULING */
3327 /* Run instruction scheduler. */
3328 /* Perform SMS module scheduling. */
3332 const pass_data pass_data_sms
=
3334 RTL_PASS
, /* type */
3336 OPTGROUP_NONE
, /* optinfo_flags */
3338 0, /* properties_required */
3339 0, /* properties_provided */
3340 0, /* properties_destroyed */
3341 0, /* todo_flags_start */
3342 TODO_df_finish
, /* todo_flags_finish */
3345 class pass_sms
: public rtl_opt_pass
3348 pass_sms (gcc::context
*ctxt
)
3349 : rtl_opt_pass (pass_data_sms
, ctxt
)
3352 /* opt_pass methods: */
3353 virtual bool gate (function
*)
3355 return (optimize
> 0 && flag_modulo_sched
);
3358 virtual unsigned int execute (function
*);
3360 }; // class pass_sms
3363 pass_sms::execute (function
*fun ATTRIBUTE_UNUSED
)
3365 #ifdef INSN_SCHEDULING
3368 /* Collect loop information to be used in SMS. */
3369 cfg_layout_initialize (0);
3372 /* Update the life information, because we add pseudos. */
3373 max_regno
= max_reg_num ();
3375 /* Finalize layout changes. */
3376 FOR_EACH_BB_FN (bb
, fun
)
3377 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3378 bb
->aux
= bb
->next_bb
;
3379 free_dominance_info (CDI_DOMINATORS
);
3380 cfg_layout_finalize ();
3381 #endif /* INSN_SCHEDULING */
3388 make_pass_sms (gcc::context
*ctxt
)
3390 return new pass_sms (ctxt
);