1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004-2017 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"
37 #include "insn-attr.h"
39 #include "sched-int.h"
44 #include "tree-pass.h"
46 #include "loop-unroll.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 /* Holds the partial schedule as an array of II rows. Each entry of the
162 array points to a linked list of PS_INSNs, which represents the
163 instructions that are scheduled for that row. */
164 struct partial_schedule
166 int ii
; /* Number of rows in the partial schedule. */
167 int history
; /* Threshold for conflict checking using DFA. */
169 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
172 /* All the moves added for this partial schedule. Index X has
173 a ps_insn id of X + g->num_nodes. */
174 vec
<ps_reg_move_info
> reg_moves
;
176 /* rows_length[i] holds the number of instructions in the row.
177 It is used only (as an optimization) to back off quickly from
178 trying to schedule a node in a full row; that is, to avoid running
179 through futile DFA state transitions. */
182 /* The earliest absolute cycle of an insn in the partial schedule. */
185 /* The latest absolute cycle of an insn in the partial schedule. */
188 ddg_ptr g
; /* The DDG of the insns in the partial schedule. */
190 int stage_count
; /* The stage count of the partial schedule. */
194 static partial_schedule_ptr
create_partial_schedule (int ii
, ddg_ptr
, int history
);
195 static void free_partial_schedule (partial_schedule_ptr
);
196 static void reset_partial_schedule (partial_schedule_ptr
, int new_ii
);
197 void print_partial_schedule (partial_schedule_ptr
, FILE *);
198 static void verify_partial_schedule (partial_schedule_ptr
, sbitmap
);
199 static ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr
,
200 int, int, sbitmap
, sbitmap
);
201 static void rotate_partial_schedule (partial_schedule_ptr
, int);
202 void set_row_column_for_ps (partial_schedule_ptr
);
203 static void ps_insert_empty_row (partial_schedule_ptr
, int, sbitmap
);
204 static int compute_split_row (sbitmap
, int, int, int, ddg_node_ptr
);
207 /* This page defines constants and structures for the modulo scheduling
210 static int sms_order_nodes (ddg_ptr
, int, int *, int *);
211 static void set_node_sched_params (ddg_ptr
);
212 static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr
, int, int, int *);
213 static void permute_partial_schedule (partial_schedule_ptr
, rtx_insn
*);
214 static void generate_prolog_epilog (partial_schedule_ptr
, struct loop
*,
216 static int calculate_stage_count (partial_schedule_ptr
, int);
217 static void calculate_must_precede_follow (ddg_node_ptr
, int, int,
218 int, int, sbitmap
, sbitmap
, sbitmap
);
219 static int get_sched_window (partial_schedule_ptr
, ddg_node_ptr
,
220 sbitmap
, int, int *, int *, int *);
221 static bool try_scheduling_node_in_cycle (partial_schedule_ptr
, int, int,
222 sbitmap
, int *, sbitmap
, sbitmap
);
223 static void remove_node_from_ps (partial_schedule_ptr
, ps_insn_ptr
);
225 #define NODE_ASAP(node) ((node)->aux.count)
227 #define SCHED_PARAMS(x) (&node_sched_param_vec[x])
228 #define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
229 #define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
230 #define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
231 #define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
233 /* The scheduling parameters held for each node. */
234 typedef struct node_sched_params
236 int time
; /* The absolute scheduling cycle. */
238 int row
; /* Holds time % ii. */
239 int stage
; /* Holds time / ii. */
241 /* The column of a node inside the ps. If nodes u, v are on the same row,
242 u will precede v if column (u) < column (v). */
244 } *node_sched_params_ptr
;
246 /* The following three functions are copied from the current scheduler
247 code in order to use sched_analyze() for computing the dependencies.
248 They are used when initializing the sched_info structure. */
250 sms_print_insn (const rtx_insn
*insn
, int aligned ATTRIBUTE_UNUSED
)
254 sprintf (tmp
, "i%4d", INSN_UID (insn
));
259 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
260 regset used ATTRIBUTE_UNUSED
)
264 static struct common_sched_info_def sms_common_sched_info
;
266 static struct sched_deps_info_def sms_sched_deps_info
=
268 compute_jump_reg_dependencies
,
269 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
274 static struct haifa_sched_info sms_sched_info
=
283 NULL
, /* insn_finishes_block_p */
288 NULL
, NULL
, NULL
, NULL
,
293 /* Partial schedule instruction ID in PS is a register move. Return
294 information about it. */
295 static struct ps_reg_move_info
*
296 ps_reg_move (partial_schedule_ptr ps
, int id
)
298 gcc_checking_assert (id
>= ps
->g
->num_nodes
);
299 return &ps
->reg_moves
[id
- ps
->g
->num_nodes
];
302 /* Return the rtl instruction that is being scheduled by partial schedule
303 instruction ID, which belongs to schedule PS. */
305 ps_rtl_insn (partial_schedule_ptr ps
, int id
)
307 if (id
< ps
->g
->num_nodes
)
308 return ps
->g
->nodes
[id
].insn
;
310 return ps_reg_move (ps
, id
)->insn
;
313 /* Partial schedule instruction ID, which belongs to PS, occurred in
314 the original (unscheduled) loop. Return the first instruction
315 in the loop that was associated with ps_rtl_insn (PS, ID).
316 If the instruction had some notes before it, this is the first
319 ps_first_note (partial_schedule_ptr ps
, int id
)
321 gcc_assert (id
< ps
->g
->num_nodes
);
322 return ps
->g
->nodes
[id
].first_note
;
325 /* Return the number of consecutive stages that are occupied by
326 partial schedule instruction ID in PS. */
328 ps_num_consecutive_stages (partial_schedule_ptr ps
, int id
)
330 if (id
< ps
->g
->num_nodes
)
333 return ps_reg_move (ps
, id
)->num_consecutive_stages
;
336 /* Given HEAD and TAIL which are the first and last insns in a loop;
337 return the register which controls the loop. Return zero if it has
338 more than one occurrence in the loop besides the control part or the
339 do-loop pattern is not of the form we expect. */
341 doloop_register_get (rtx_insn
*head
, rtx_insn
*tail
)
344 rtx_insn
*insn
, *first_insn_not_to_check
;
349 if (!targetm
.code_for_doloop_end
)
352 /* TODO: Free SMS's dependence on doloop_condition_get. */
353 condition
= doloop_condition_get (tail
);
357 if (REG_P (XEXP (condition
, 0)))
358 reg
= XEXP (condition
, 0);
359 else if (GET_CODE (XEXP (condition
, 0)) == PLUS
360 && REG_P (XEXP (XEXP (condition
, 0), 0)))
361 reg
= XEXP (XEXP (condition
, 0), 0);
365 /* Check that the COUNT_REG has no other occurrences in the loop
366 until the decrement. We assume the control part consists of
367 either a single (parallel) branch-on-count or a (non-parallel)
368 branch immediately preceded by a single (decrement) insn. */
369 first_insn_not_to_check
= (GET_CODE (PATTERN (tail
)) == PARALLEL
? tail
370 : prev_nondebug_insn (tail
));
372 for (insn
= head
; insn
!= first_insn_not_to_check
; insn
= NEXT_INSN (insn
))
373 if (!DEBUG_INSN_P (insn
) && reg_mentioned_p (reg
, insn
))
377 fprintf (dump_file
, "SMS count_reg found ");
378 print_rtl_single (dump_file
, reg
);
379 fprintf (dump_file
, " outside control in insn:\n");
380 print_rtl_single (dump_file
, insn
);
389 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
390 that the number of iterations is a compile-time constant. If so,
391 return the rtx_insn that sets COUNT_REG to a constant, and set COUNT to
392 this constant. Otherwise return 0. */
394 const_iteration_count (rtx count_reg
, basic_block pre_header
,
398 rtx_insn
*head
, *tail
;
403 get_ebb_head_tail (pre_header
, pre_header
, &head
, &tail
);
405 for (insn
= tail
; insn
!= PREV_INSN (head
); insn
= PREV_INSN (insn
))
406 if (NONDEBUG_INSN_P (insn
) && single_set (insn
) &&
407 rtx_equal_p (count_reg
, SET_DEST (single_set (insn
))))
409 rtx pat
= single_set (insn
);
411 if (CONST_INT_P (SET_SRC (pat
)))
413 *count
= INTVAL (SET_SRC (pat
));
423 /* A very simple resource-based lower bound on the initiation interval.
424 ??? Improve the accuracy of this bound by considering the
425 utilization of various units. */
429 if (targetm
.sched
.sms_res_mii
)
430 return targetm
.sched
.sms_res_mii (g
);
432 return ((g
->num_nodes
- g
->num_debug
) / issue_rate
);
436 /* A vector that contains the sched data for each ps_insn. */
437 static vec
<node_sched_params
> node_sched_param_vec
;
439 /* Allocate sched_params for each node and initialize it. */
441 set_node_sched_params (ddg_ptr g
)
443 node_sched_param_vec
.truncate (0);
444 node_sched_param_vec
.safe_grow_cleared (g
->num_nodes
);
447 /* Make sure that node_sched_param_vec has an entry for every move in PS. */
449 extend_node_sched_params (partial_schedule_ptr ps
)
451 node_sched_param_vec
.safe_grow_cleared (ps
->g
->num_nodes
452 + ps
->reg_moves
.length ());
455 /* Update the sched_params (time, row and stage) for node U using the II,
456 the CYCLE of U and MIN_CYCLE.
457 We're not simply taking the following
458 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
459 because the stages may not be aligned on cycle 0. */
461 update_node_sched_params (int u
, int ii
, int cycle
, int min_cycle
)
463 int sc_until_cycle_zero
;
466 SCHED_TIME (u
) = cycle
;
467 SCHED_ROW (u
) = SMODULO (cycle
, ii
);
469 /* The calculation of stage count is done adding the number
470 of stages before cycle zero and after cycle zero. */
471 sc_until_cycle_zero
= CALC_STAGE_COUNT (-1, min_cycle
, ii
);
473 if (SCHED_TIME (u
) < 0)
475 stage
= CALC_STAGE_COUNT (-1, SCHED_TIME (u
), ii
);
476 SCHED_STAGE (u
) = sc_until_cycle_zero
- stage
;
480 stage
= CALC_STAGE_COUNT (SCHED_TIME (u
), 0, ii
);
481 SCHED_STAGE (u
) = sc_until_cycle_zero
+ stage
- 1;
486 print_node_sched_params (FILE *file
, int num_nodes
, partial_schedule_ptr ps
)
492 for (i
= 0; i
< num_nodes
; i
++)
494 node_sched_params_ptr nsp
= SCHED_PARAMS (i
);
496 fprintf (file
, "Node = %d; INSN = %d\n", i
,
497 INSN_UID (ps_rtl_insn (ps
, i
)));
498 fprintf (file
, " asap = %d:\n", NODE_ASAP (&ps
->g
->nodes
[i
]));
499 fprintf (file
, " time = %d:\n", nsp
->time
);
500 fprintf (file
, " stage = %d:\n", nsp
->stage
);
504 /* Set SCHED_COLUMN for each instruction in row ROW of PS. */
506 set_columns_for_row (partial_schedule_ptr ps
, int row
)
508 ps_insn_ptr cur_insn
;
512 for (cur_insn
= ps
->rows
[row
]; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
513 SCHED_COLUMN (cur_insn
->id
) = column
++;
516 /* Set SCHED_COLUMN for each instruction in PS. */
518 set_columns_for_ps (partial_schedule_ptr ps
)
522 for (row
= 0; row
< ps
->ii
; row
++)
523 set_columns_for_row (ps
, row
);
526 /* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
527 Its single predecessor has already been scheduled, as has its
528 ddg node successors. (The move may have also another move as its
529 successor, in which case that successor will be scheduled later.)
531 The move is part of a chain that satisfies register dependencies
532 between a producing ddg node and various consuming ddg nodes.
533 If some of these dependencies have a distance of 1 (meaning that
534 the use is upward-exposed) then DISTANCE1_USES is nonnull and
535 contains the set of uses with distance-1 dependencies.
536 DISTANCE1_USES is null otherwise.
538 MUST_FOLLOW is a scratch bitmap that is big enough to hold
539 all current ps_insn ids.
541 Return true on success. */
543 schedule_reg_move (partial_schedule_ptr ps
, int i_reg_move
,
544 sbitmap distance1_uses
, sbitmap must_follow
)
547 int this_time
, this_distance
, this_start
, this_end
, this_latency
;
548 int start
, end
, c
, ii
;
549 sbitmap_iterator sbi
;
550 ps_reg_move_info
*move
;
554 move
= ps_reg_move (ps
, i_reg_move
);
558 fprintf (dump_file
, "Scheduling register move INSN %d; ii = %d"
559 ", min cycle = %d\n\n", INSN_UID (move
->insn
), ii
,
561 print_rtl_single (dump_file
, move
->insn
);
562 fprintf (dump_file
, "\n%11s %11s %5s\n", "start", "end", "time");
563 fprintf (dump_file
, "=========== =========== =====\n");
569 /* For dependencies of distance 1 between a producer ddg node A
570 and consumer ddg node B, we have a chain of dependencies:
572 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
574 where Mi is the ith move. For dependencies of distance 0 between
575 a producer ddg node A and consumer ddg node C, we have a chain of
578 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
580 where Mi' occupies the same position as Mi but occurs a stage later.
581 We can only schedule each move once, so if we have both types of
582 chain, we model the second as:
584 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
586 First handle the dependencies between the previously-scheduled
587 predecessor and the move. */
588 this_insn
= ps_rtl_insn (ps
, move
->def
);
589 this_latency
= insn_latency (this_insn
, move
->insn
);
590 this_distance
= distance1_uses
&& move
->def
< ps
->g
->num_nodes
? 1 : 0;
591 this_time
= SCHED_TIME (move
->def
) - this_distance
* ii
;
592 this_start
= this_time
+ this_latency
;
593 this_end
= this_time
+ ii
;
595 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
596 this_start
, this_end
, SCHED_TIME (move
->def
),
597 INSN_UID (this_insn
), this_latency
, this_distance
,
598 INSN_UID (move
->insn
));
600 if (start
< this_start
)
605 /* Handle the dependencies between the move and previously-scheduled
607 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, u
, sbi
)
609 this_insn
= ps_rtl_insn (ps
, u
);
610 this_latency
= insn_latency (move
->insn
, this_insn
);
611 if (distance1_uses
&& !bitmap_bit_p (distance1_uses
, u
))
615 this_time
= SCHED_TIME (u
) + this_distance
* ii
;
616 this_start
= this_time
- ii
;
617 this_end
= this_time
- this_latency
;
619 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
620 this_start
, this_end
, SCHED_TIME (u
), INSN_UID (move
->insn
),
621 this_latency
, this_distance
, INSN_UID (this_insn
));
623 if (start
< this_start
)
631 fprintf (dump_file
, "----------- ----------- -----\n");
632 fprintf (dump_file
, "%11d %11d %5s %s\n", start
, end
, "", "(max, min)");
635 bitmap_clear (must_follow
);
636 bitmap_set_bit (must_follow
, move
->def
);
638 start
= MAX (start
, end
- (ii
- 1));
639 for (c
= end
; c
>= start
; c
--)
641 psi
= ps_add_node_check_conflicts (ps
, i_reg_move
, c
,
642 move
->uses
, must_follow
);
645 update_node_sched_params (i_reg_move
, ii
, c
, PS_MIN_CYCLE (ps
));
647 fprintf (dump_file
, "\nScheduled register move INSN %d at"
648 " time %d, row %d\n\n", INSN_UID (move
->insn
), c
,
649 SCHED_ROW (i_reg_move
));
655 fprintf (dump_file
, "\nNo available slot\n\n");
661 Breaking intra-loop register anti-dependences:
662 Each intra-loop register anti-dependence implies a cross-iteration true
663 dependence of distance 1. Therefore, we can remove such false dependencies
664 and figure out if the partial schedule broke them by checking if (for a
665 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
666 if so generate a register move. The number of such moves is equal to:
667 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
668 nreg_moves = ----------------------------------- + 1 - { dependence.
672 schedule_reg_moves (partial_schedule_ptr ps
)
678 for (i
= 0; i
< g
->num_nodes
; i
++)
680 ddg_node_ptr u
= &g
->nodes
[i
];
682 int nreg_moves
= 0, i_reg_move
;
683 rtx prev_reg
, old_reg
;
686 sbitmap distance1_uses
;
687 rtx set
= single_set (u
->insn
);
689 /* Skip instructions that do not set a register. */
690 if ((set
&& !REG_P (SET_DEST (set
))))
693 /* Compute the number of reg_moves needed for u, by looking at life
694 ranges started at u (excluding self-loops). */
695 distances
[0] = distances
[1] = false;
696 for (e
= u
->out
; e
; e
= e
->next_out
)
697 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
699 int nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
700 - SCHED_TIME (e
->src
->cuid
)) / ii
;
702 if (e
->distance
== 1)
703 nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
704 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
706 /* If dest precedes src in the schedule of the kernel, then dest
707 will read before src writes and we can save one reg_copy. */
708 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
709 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
712 if (nreg_moves4e
>= 1)
714 /* !single_set instructions are not supported yet and
715 thus we do not except to encounter them in the loop
716 except from the doloop part. For the latter case
717 we assume no regmoves are generated as the doloop
718 instructions are tied to the branch with an edge. */
720 /* If the instruction contains auto-inc register then
721 validate that the regmov is being generated for the
722 target regsiter rather then the inc'ed register. */
723 gcc_assert (!autoinc_var_is_used_p (u
->insn
, e
->dest
->insn
));
728 gcc_assert (e
->distance
< 2);
729 distances
[e
->distance
] = true;
731 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
737 /* Create NREG_MOVES register moves. */
738 first_move
= ps
->reg_moves
.length ();
739 ps
->reg_moves
.safe_grow_cleared (first_move
+ nreg_moves
);
740 extend_node_sched_params (ps
);
742 /* Record the moves associated with this node. */
743 first_move
+= ps
->g
->num_nodes
;
745 /* Generate each move. */
746 old_reg
= prev_reg
= SET_DEST (single_set (u
->insn
));
747 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
749 ps_reg_move_info
*move
= ps_reg_move (ps
, first_move
+ i_reg_move
);
751 move
->def
= i_reg_move
> 0 ? first_move
+ i_reg_move
- 1 : i
;
752 move
->uses
= sbitmap_alloc (first_move
+ nreg_moves
);
753 move
->old_reg
= old_reg
;
754 move
->new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
755 move
->num_consecutive_stages
= distances
[0] && distances
[1] ? 2 : 1;
756 move
->insn
= gen_move_insn (move
->new_reg
, copy_rtx (prev_reg
));
757 bitmap_clear (move
->uses
);
759 prev_reg
= move
->new_reg
;
762 distance1_uses
= distances
[1] ? sbitmap_alloc (g
->num_nodes
) : NULL
;
765 bitmap_clear (distance1_uses
);
767 /* Every use of the register defined by node may require a different
768 copy of this register, depending on the time the use is scheduled.
769 Record which uses require which move results. */
770 for (e
= u
->out
; e
; e
= e
->next_out
)
771 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
773 int dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
774 - SCHED_TIME (e
->src
->cuid
)) / ii
;
776 if (e
->distance
== 1)
777 dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
778 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
780 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
781 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
786 ps_reg_move_info
*move
;
788 move
= ps_reg_move (ps
, first_move
+ dest_copy
- 1);
789 bitmap_set_bit (move
->uses
, e
->dest
->cuid
);
790 if (e
->distance
== 1)
791 bitmap_set_bit (distance1_uses
, e
->dest
->cuid
);
795 auto_sbitmap
must_follow (first_move
+ nreg_moves
);
796 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
797 if (!schedule_reg_move (ps
, first_move
+ i_reg_move
,
798 distance1_uses
, must_follow
))
801 sbitmap_free (distance1_uses
);
802 if (i_reg_move
< nreg_moves
)
808 /* Emit the moves associated with PS. Apply the substitutions
809 associated with them. */
811 apply_reg_moves (partial_schedule_ptr ps
)
813 ps_reg_move_info
*move
;
816 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
819 sbitmap_iterator sbi
;
821 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, i_use
, sbi
)
823 replace_rtx (ps
->g
->nodes
[i_use
].insn
, move
->old_reg
, move
->new_reg
);
824 df_insn_rescan (ps
->g
->nodes
[i_use
].insn
);
829 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
830 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
831 will move to cycle zero. */
833 reset_sched_times (partial_schedule_ptr ps
, int amount
)
837 ps_insn_ptr crr_insn
;
839 for (row
= 0; row
< ii
; row
++)
840 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
842 int u
= crr_insn
->id
;
843 int normalized_time
= SCHED_TIME (u
) - amount
;
844 int new_min_cycle
= PS_MIN_CYCLE (ps
) - amount
;
848 /* Print the scheduling times after the rotation. */
849 rtx_insn
*insn
= ps_rtl_insn (ps
, u
);
851 fprintf (dump_file
, "crr_insn->node=%d (insn id %d), "
852 "crr_insn->cycle=%d, min_cycle=%d", u
,
853 INSN_UID (insn
), normalized_time
, new_min_cycle
);
855 fprintf (dump_file
, " (branch)");
856 fprintf (dump_file
, "\n");
859 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
860 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
862 crr_insn
->cycle
= normalized_time
;
863 update_node_sched_params (u
, ii
, normalized_time
, new_min_cycle
);
867 /* Permute the insns according to their order in PS, from row 0 to
868 row ii-1, and position them right before LAST. This schedules
869 the insns of the loop kernel. */
871 permute_partial_schedule (partial_schedule_ptr ps
, rtx_insn
*last
)
877 for (row
= 0; row
< ii
; row
++)
878 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
880 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_ij
->id
);
882 if (PREV_INSN (last
) != insn
)
884 if (ps_ij
->id
< ps
->g
->num_nodes
)
885 reorder_insns_nobb (ps_first_note (ps
, ps_ij
->id
), insn
,
888 add_insn_before (insn
, last
, NULL
);
893 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
894 respectively only if cycle C falls on the border of the scheduling
895 window boundaries marked by START and END cycles. STEP is the
896 direction of the window. */
898 set_must_precede_follow (sbitmap
*tmp_follow
, sbitmap must_follow
,
899 sbitmap
*tmp_precede
, sbitmap must_precede
, int c
,
900 int start
, int end
, int step
)
908 *tmp_precede
= must_precede
;
909 else /* step == -1. */
910 *tmp_follow
= must_follow
;
915 *tmp_follow
= must_follow
;
916 else /* step == -1. */
917 *tmp_precede
= must_precede
;
922 /* Return True if the branch can be moved to row ii-1 while
923 normalizing the partial schedule PS to start from cycle zero and thus
924 optimize the SC. Otherwise return False. */
926 optimize_sc (partial_schedule_ptr ps
, ddg_ptr g
)
928 int amount
= PS_MIN_CYCLE (ps
);
929 int start
, end
, step
;
932 int stage_count
, stage_count_curr
;
934 /* Compare the SC after normalization and SC after bringing the branch
935 to row ii-1. If they are equal just bail out. */
936 stage_count
= calculate_stage_count (ps
, amount
);
938 calculate_stage_count (ps
, SCHED_TIME (g
->closing_branch
->cuid
) - (ii
- 1));
940 if (stage_count
== stage_count_curr
)
943 fprintf (dump_file
, "SMS SC already optimized.\n");
950 fprintf (dump_file
, "SMS Trying to optimize branch location\n");
951 fprintf (dump_file
, "SMS partial schedule before trial:\n");
952 print_partial_schedule (ps
, dump_file
);
955 /* First, normalize the partial scheduling. */
956 reset_sched_times (ps
, amount
);
957 rotate_partial_schedule (ps
, amount
);
961 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
963 print_partial_schedule (ps
, dump_file
);
966 if (SMODULO (SCHED_TIME (g
->closing_branch
->cuid
), ii
) == ii
- 1)
969 auto_sbitmap
sched_nodes (g
->num_nodes
);
970 bitmap_ones (sched_nodes
);
972 /* Calculate the new placement of the branch. It should be in row
973 ii-1 and fall into it's scheduling window. */
974 if (get_sched_window (ps
, g
->closing_branch
, sched_nodes
, ii
, &start
,
978 ps_insn_ptr next_ps_i
;
979 int branch_cycle
= SCHED_TIME (g
->closing_branch
->cuid
);
980 int row
= SMODULO (branch_cycle
, ps
->ii
);
982 sbitmap tmp_precede
, tmp_follow
;
986 fprintf (dump_file
, "\nTrying to schedule node %d "
987 "INSN = %d in (%d .. %d) step %d\n",
988 g
->closing_branch
->cuid
,
989 (INSN_UID (g
->closing_branch
->insn
)), start
, end
, step
);
991 gcc_assert ((step
> 0 && start
< end
) || (step
< 0 && start
> end
));
994 c
= start
+ ii
- SMODULO (start
, ii
) - 1;
995 gcc_assert (c
>= start
);
1000 "SMS failed to schedule branch at cycle: %d\n", c
);
1006 c
= start
- SMODULO (start
, ii
) - 1;
1007 gcc_assert (c
<= start
);
1013 "SMS failed to schedule branch at cycle: %d\n", c
);
1018 auto_sbitmap
must_precede (g
->num_nodes
);
1019 auto_sbitmap
must_follow (g
->num_nodes
);
1021 /* Try to schedule the branch is it's new cycle. */
1022 calculate_must_precede_follow (g
->closing_branch
, start
, end
,
1023 step
, ii
, sched_nodes
,
1024 must_precede
, must_follow
);
1026 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1027 must_precede
, c
, start
, end
, step
);
1029 /* Find the element in the partial schedule related to the closing
1030 branch so we can remove it from it's current cycle. */
1031 for (next_ps_i
= ps
->rows
[row
];
1032 next_ps_i
; next_ps_i
= next_ps_i
->next_in_row
)
1033 if (next_ps_i
->id
== g
->closing_branch
->cuid
)
1036 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1037 remove_node_from_ps (ps
, next_ps_i
);
1039 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
, c
,
1040 sched_nodes
, &num_splits
,
1041 tmp_precede
, tmp_follow
);
1042 gcc_assert (num_splits
== 0);
1047 "SMS failed to schedule branch at cycle: %d, "
1048 "bringing it back to cycle %d\n", c
, branch_cycle
);
1050 /* The branch was failed to be placed in row ii - 1.
1051 Put it back in it's original place in the partial
1053 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1054 must_precede
, branch_cycle
, start
, end
,
1057 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
,
1058 branch_cycle
, sched_nodes
,
1059 &num_splits
, tmp_precede
,
1061 gcc_assert (success
&& (num_splits
== 0));
1066 /* The branch is placed in row ii - 1. */
1069 "SMS success in moving branch to cycle %d\n", c
);
1071 update_node_sched_params (g
->closing_branch
->cuid
, ii
, c
,
1076 /* This might have been added to a new first stage. */
1077 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1078 reset_sched_times (ps
, 0);
1085 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
1086 int to_stage
, rtx count_reg
)
1091 for (row
= 0; row
< ps
->ii
; row
++)
1092 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
1095 int first_u
, last_u
;
1098 /* Do not duplicate any insn which refers to count_reg as it
1099 belongs to the control part.
1100 The closing branch is scheduled as well and thus should
1102 TODO: This should be done by analyzing the control part of
1104 u_insn
= ps_rtl_insn (ps
, u
);
1105 if (reg_mentioned_p (count_reg
, u_insn
)
1109 first_u
= SCHED_STAGE (u
);
1110 last_u
= first_u
+ ps_num_consecutive_stages (ps
, u
) - 1;
1111 if (from_stage
<= last_u
&& to_stage
>= first_u
)
1113 if (u
< ps
->g
->num_nodes
)
1114 duplicate_insn_chain (ps_first_note (ps
, u
), u_insn
);
1116 emit_insn (copy_rtx (PATTERN (u_insn
)));
1122 /* Generate the instructions (including reg_moves) for prolog & epilog. */
1124 generate_prolog_epilog (partial_schedule_ptr ps
, struct loop
*loop
,
1125 rtx count_reg
, rtx count_init
)
1128 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
1131 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1136 /* Generate instructions at the beginning of the prolog to
1137 adjust the loop count by STAGE_COUNT. If loop count is constant
1138 (count_init), this constant is adjusted by STAGE_COUNT in
1139 generate_prolog_epilog function. */
1140 rtx sub_reg
= NULL_RTX
;
1142 sub_reg
= expand_simple_binop (GET_MODE (count_reg
), MINUS
, count_reg
,
1143 gen_int_mode (last_stage
,
1144 GET_MODE (count_reg
)),
1145 count_reg
, 1, OPTAB_DIRECT
);
1146 gcc_assert (REG_P (sub_reg
));
1147 if (REGNO (sub_reg
) != REGNO (count_reg
))
1148 emit_move_insn (count_reg
, sub_reg
);
1151 for (i
= 0; i
< last_stage
; i
++)
1152 duplicate_insns_of_cycles (ps
, 0, i
, count_reg
);
1154 /* Put the prolog on the entry edge. */
1155 e
= loop_preheader_edge (loop
);
1156 split_edge_and_insert (e
, get_insns ());
1157 if (!flag_resched_modulo_sched
)
1158 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1162 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1165 for (i
= 0; i
< last_stage
; i
++)
1166 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, count_reg
);
1168 /* Put the epilogue on the exit edge. */
1169 gcc_assert (single_exit (loop
));
1170 e
= single_exit (loop
);
1171 split_edge_and_insert (e
, get_insns ());
1172 if (!flag_resched_modulo_sched
)
1173 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1178 /* Mark LOOP as software pipelined so the later
1179 scheduling passes don't touch it. */
1181 mark_loop_unsched (struct loop
*loop
)
1184 basic_block
*bbs
= get_loop_body (loop
);
1186 for (i
= 0; i
< loop
->num_nodes
; i
++)
1187 bbs
[i
]->flags
|= BB_DISABLE_SCHEDULE
;
1192 /* Return true if all the BBs of the loop are empty except the
1195 loop_single_full_bb_p (struct loop
*loop
)
1198 basic_block
*bbs
= get_loop_body (loop
);
1200 for (i
= 0; i
< loop
->num_nodes
; i
++)
1202 rtx_insn
*head
, *tail
;
1203 bool empty_bb
= true;
1205 if (bbs
[i
] == loop
->header
)
1208 /* Make sure that basic blocks other than the header
1209 have only notes labels or jumps. */
1210 get_ebb_head_tail (bbs
[i
], bbs
[i
], &head
, &tail
);
1211 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
1213 if (NOTE_P (head
) || LABEL_P (head
)
1214 || (INSN_P (head
) && (DEBUG_INSN_P (head
) || JUMP_P (head
))))
1230 /* Dump file:line from INSN's location info to dump_file. */
1233 dump_insn_location (rtx_insn
*insn
)
1235 if (dump_file
&& INSN_HAS_LOCATION (insn
))
1237 expanded_location xloc
= insn_location (insn
);
1238 fprintf (dump_file
, " %s:%i", xloc
.file
, xloc
.line
);
1242 /* A simple loop from SMS point of view; it is a loop that is composed of
1243 either a single basic block or two BBs - a header and a latch. */
1244 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1245 && (EDGE_COUNT (loop->latch->preds) == 1) \
1246 && (EDGE_COUNT (loop->latch->succs) == 1))
1248 /* Return true if the loop is in its canonical form and false if not.
1249 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1251 loop_canon_p (struct loop
*loop
)
1254 if (loop
->inner
|| !loop_outer (loop
))
1257 fprintf (dump_file
, "SMS loop inner or !loop_outer\n");
1261 if (!single_exit (loop
))
1265 rtx_insn
*insn
= BB_END (loop
->header
);
1267 fprintf (dump_file
, "SMS loop many exits");
1268 dump_insn_location (insn
);
1269 fprintf (dump_file
, "\n");
1274 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
1278 rtx_insn
*insn
= BB_END (loop
->header
);
1280 fprintf (dump_file
, "SMS loop many BBs.");
1281 dump_insn_location (insn
);
1282 fprintf (dump_file
, "\n");
1290 /* If there are more than one entry for the loop,
1291 make it one by splitting the first entry edge and
1292 redirecting the others to the new BB. */
1294 canon_loop (struct loop
*loop
)
1299 /* Avoid annoying special cases of edges going to exit
1301 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1302 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
1305 if (loop
->latch
== loop
->header
1306 || EDGE_COUNT (loop
->latch
->succs
) > 1)
1308 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
1309 if (e
->src
== loop
->latch
)
1317 setup_sched_infos (void)
1319 memcpy (&sms_common_sched_info
, &haifa_common_sched_info
,
1320 sizeof (sms_common_sched_info
));
1321 sms_common_sched_info
.sched_pass_id
= SCHED_SMS_PASS
;
1322 common_sched_info
= &sms_common_sched_info
;
1324 sched_deps_info
= &sms_sched_deps_info
;
1325 current_sched_info
= &sms_sched_info
;
1328 /* Probability in % that the sms-ed loop rolls enough so that optimized
1329 version may be entered. Just a guess. */
1330 #define PROB_SMS_ENOUGH_ITERATIONS 80
1332 /* Used to calculate the upper bound of ii. */
1333 #define MAXII_FACTOR 2
1335 /* Main entry point, perform SMS scheduling on the loops of the function
1336 that consist of single basic blocks. */
1343 int maxii
, max_asap
;
1344 partial_schedule_ptr ps
;
1345 basic_block bb
= NULL
;
1347 basic_block condition_bb
= NULL
;
1349 gcov_type trip_count
= 0;
1351 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1352 | LOOPS_HAVE_RECORDED_EXITS
);
1353 if (number_of_loops (cfun
) <= 1)
1355 loop_optimizer_finalize ();
1356 return; /* There are no loops to schedule. */
1359 /* Initialize issue_rate. */
1360 if (targetm
.sched
.issue_rate
)
1362 int temp
= reload_completed
;
1364 reload_completed
= 1;
1365 issue_rate
= targetm
.sched
.issue_rate ();
1366 reload_completed
= temp
;
1371 /* Initialize the scheduler. */
1372 setup_sched_infos ();
1373 haifa_sched_init ();
1375 /* Allocate memory to hold the DDG array one entry for each loop.
1376 We use loop->num as index into this array. */
1377 g_arr
= XCNEWVEC (ddg_ptr
, number_of_loops (cfun
));
1381 fprintf (dump_file
, "\n\nSMS analysis phase\n");
1382 fprintf (dump_file
, "===================\n\n");
1385 /* Build DDGs for all the relevant loops and hold them in G_ARR
1386 indexed by the loop index. */
1387 FOR_EACH_LOOP (loop
, 0)
1389 rtx_insn
*head
, *tail
;
1392 /* For debugging. */
1393 if (dbg_cnt (sms_sched_loop
) == false)
1396 fprintf (dump_file
, "SMS reached max limit... \n");
1403 rtx_insn
*insn
= BB_END (loop
->header
);
1405 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1406 dump_insn_location (insn
);
1407 fprintf (dump_file
, "\n");
1410 if (! loop_canon_p (loop
))
1413 if (! loop_single_full_bb_p (loop
))
1416 fprintf (dump_file
, "SMS not loop_single_full_bb_p\n");
1422 get_ebb_head_tail (bb
, bb
, &head
, &tail
);
1423 latch_edge
= loop_latch_edge (loop
);
1424 gcc_assert (single_exit (loop
));
1425 if (single_exit (loop
)->count
> profile_count::zero ())
1426 trip_count
= latch_edge
->count
.to_gcov_type ()
1427 / single_exit (loop
)->count
.to_gcov_type ();
1429 /* Perform SMS only on loops that their average count is above threshold. */
1431 if ( latch_edge
->count
> profile_count::zero ()
1432 && (latch_edge
->count
1433 < single_exit (loop
)->count
.apply_scale
1434 (SMS_LOOP_AVERAGE_COUNT_THRESHOLD
, 1)))
1438 dump_insn_location (tail
);
1439 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1440 if (profile_info
&& flag_branch_probabilities
)
1442 fprintf (dump_file
, "SMS loop-count ");
1443 fprintf (dump_file
, "%" PRId64
,
1444 (int64_t) bb
->count
.to_gcov_type ());
1445 fprintf (dump_file
, "\n");
1446 fprintf (dump_file
, "SMS trip-count ");
1447 fprintf (dump_file
, "%" PRId64
,
1448 (int64_t) trip_count
);
1449 fprintf (dump_file
, "\n");
1450 fprintf (dump_file
, "SMS profile-sum-max ");
1451 fprintf (dump_file
, "%" PRId64
,
1452 (int64_t) profile_info
->sum_max
);
1453 fprintf (dump_file
, "\n");
1459 /* Make sure this is a doloop. */
1460 if ( !(count_reg
= doloop_register_get (head
, tail
)))
1463 fprintf (dump_file
, "SMS doloop_register_get failed\n");
1467 /* Don't handle BBs with calls or barriers
1468 or !single_set with the exception of instructions that include
1469 count_reg---these instructions are part of the control part
1470 that do-loop recognizes.
1471 ??? Should handle insns defining subregs. */
1472 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1478 || (NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1479 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
1480 && !reg_mentioned_p (count_reg
, insn
))
1481 || (INSN_P (insn
) && (set
= single_set (insn
))
1482 && GET_CODE (SET_DEST (set
)) == SUBREG
))
1486 if (insn
!= NEXT_INSN (tail
))
1491 fprintf (dump_file
, "SMS loop-with-call\n");
1492 else if (BARRIER_P (insn
))
1493 fprintf (dump_file
, "SMS loop-with-barrier\n");
1494 else if ((NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1495 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
1496 fprintf (dump_file
, "SMS loop-with-not-single-set\n");
1498 fprintf (dump_file
, "SMS loop with subreg in lhs\n");
1499 print_rtl_single (dump_file
, insn
);
1505 /* Always schedule the closing branch with the rest of the
1506 instructions. The branch is rotated to be in row ii-1 at the
1507 end of the scheduling procedure to make sure it's the last
1508 instruction in the iteration. */
1509 if (! (g
= create_ddg (bb
, 1)))
1512 fprintf (dump_file
, "SMS create_ddg failed\n");
1516 g_arr
[loop
->num
] = g
;
1518 fprintf (dump_file
, "...OK\n");
1523 fprintf (dump_file
, "\nSMS transformation phase\n");
1524 fprintf (dump_file
, "=========================\n\n");
1527 /* We don't want to perform SMS on new loops - created by versioning. */
1528 FOR_EACH_LOOP (loop
, 0)
1530 rtx_insn
*head
, *tail
;
1532 rtx_insn
*count_init
;
1533 int mii
, rec_mii
, stage_count
, min_cycle
;
1534 int64_t loop_count
= 0;
1537 if (! (g
= g_arr
[loop
->num
]))
1542 rtx_insn
*insn
= BB_END (loop
->header
);
1544 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1545 dump_insn_location (insn
);
1546 fprintf (dump_file
, "\n");
1548 print_ddg (dump_file
, g
);
1551 get_ebb_head_tail (loop
->header
, loop
->header
, &head
, &tail
);
1553 latch_edge
= loop_latch_edge (loop
);
1554 gcc_assert (single_exit (loop
));
1555 if (single_exit (loop
)->count
> profile_count::zero ())
1556 trip_count
= latch_edge
->count
.to_gcov_type ()
1557 / single_exit (loop
)->count
.to_gcov_type ();
1561 dump_insn_location (tail
);
1562 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1563 if (profile_info
&& flag_branch_probabilities
)
1565 fprintf (dump_file
, "SMS loop-count ");
1566 fprintf (dump_file
, "%" PRId64
,
1567 (int64_t) bb
->count
.to_gcov_type ());
1568 fprintf (dump_file
, "\n");
1569 fprintf (dump_file
, "SMS profile-sum-max ");
1570 fprintf (dump_file
, "%" PRId64
,
1571 (int64_t) profile_info
->sum_max
);
1572 fprintf (dump_file
, "\n");
1574 fprintf (dump_file
, "SMS doloop\n");
1575 fprintf (dump_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1576 fprintf (dump_file
, "SMS num-loads %d\n", g
->num_loads
);
1577 fprintf (dump_file
, "SMS num-stores %d\n", g
->num_stores
);
1581 /* In case of th loop have doloop register it gets special
1584 if ((count_reg
= doloop_register_get (head
, tail
)))
1586 basic_block pre_header
;
1588 pre_header
= loop_preheader_edge (loop
)->src
;
1589 count_init
= const_iteration_count (count_reg
, pre_header
,
1592 gcc_assert (count_reg
);
1594 if (dump_file
&& count_init
)
1596 fprintf (dump_file
, "SMS const-doloop ");
1597 fprintf (dump_file
, "%" PRId64
,
1599 fprintf (dump_file
, "\n");
1602 node_order
= XNEWVEC (int, g
->num_nodes
);
1604 mii
= 1; /* Need to pass some estimate of mii. */
1605 rec_mii
= sms_order_nodes (g
, mii
, node_order
, &max_asap
);
1606 mii
= MAX (res_MII (g
), rec_mii
);
1607 maxii
= MAX (max_asap
, MAXII_FACTOR
* mii
);
1610 fprintf (dump_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1611 rec_mii
, mii
, maxii
);
1615 set_node_sched_params (g
);
1619 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
);
1623 /* Try to achieve optimized SC by normalizing the partial
1624 schedule (having the cycles start from cycle zero).
1625 The branch location must be placed in row ii-1 in the
1626 final scheduling. If failed, shift all instructions to
1627 position the branch in row ii-1. */
1628 opt_sc_p
= optimize_sc (ps
, g
);
1630 stage_count
= calculate_stage_count (ps
, 0);
1633 /* Bring the branch to cycle ii-1. */
1634 int amount
= (SCHED_TIME (g
->closing_branch
->cuid
)
1638 fprintf (dump_file
, "SMS schedule branch at cycle ii-1\n");
1640 stage_count
= calculate_stage_count (ps
, amount
);
1643 gcc_assert (stage_count
>= 1);
1646 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
1647 1 means that there is no interleaving between iterations thus
1648 we let the scheduling passes do the job in this case. */
1649 if (stage_count
< PARAM_VALUE (PARAM_SMS_MIN_SC
)
1650 || (count_init
&& (loop_count
<= stage_count
))
1651 || (flag_branch_probabilities
&& (trip_count
<= stage_count
)))
1655 fprintf (dump_file
, "SMS failed... \n");
1656 fprintf (dump_file
, "SMS sched-failed (stage-count=%d,"
1657 " loop-count=", stage_count
);
1658 fprintf (dump_file
, "%" PRId64
, loop_count
);
1659 fprintf (dump_file
, ", trip-count=");
1660 fprintf (dump_file
, "%" PRId64
, trip_count
);
1661 fprintf (dump_file
, ")\n");
1668 /* Rotate the partial schedule to have the branch in row ii-1. */
1669 int amount
= SCHED_TIME (g
->closing_branch
->cuid
) - (ps
->ii
- 1);
1671 reset_sched_times (ps
, amount
);
1672 rotate_partial_schedule (ps
, amount
);
1675 set_columns_for_ps (ps
);
1677 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1678 if (!schedule_reg_moves (ps
))
1681 free_partial_schedule (ps
);
1685 /* Moves that handle incoming values might have been added
1686 to a new first stage. Bump the stage count if so.
1688 ??? Perhaps we could consider rotating the schedule here
1690 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1692 reset_sched_times (ps
, 0);
1696 /* The stage count should now be correct without rotation. */
1697 gcc_checking_assert (stage_count
== calculate_stage_count (ps
, 0));
1698 PS_STAGE_COUNT (ps
) = stage_count
;
1704 dump_insn_location (tail
);
1705 fprintf (dump_file
, " SMS succeeded %d %d (with ii, sc)\n",
1706 ps
->ii
, stage_count
);
1707 print_partial_schedule (ps
, dump_file
);
1710 /* case the BCT count is not known , Do loop-versioning */
1711 if (count_reg
&& ! count_init
)
1713 rtx comp_rtx
= gen_rtx_GT (VOIDmode
, count_reg
,
1714 gen_int_mode (stage_count
,
1715 GET_MODE (count_reg
)));
1716 profile_probability prob
= profile_probability::guessed_always ()
1717 .apply_scale (PROB_SMS_ENOUGH_ITERATIONS
, 100);
1719 loop_version (loop
, comp_rtx
, &condition_bb
,
1720 prob
, prob
.invert (),
1721 prob
.to_reg_br_prob_base (),
1722 prob
.invert ().to_reg_br_prob_base (),
1726 /* Set new iteration count of loop kernel. */
1727 if (count_reg
&& count_init
)
1728 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1731 /* Now apply the scheduled kernel to the RTL of the loop. */
1732 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1734 /* Mark this loop as software pipelined so the later
1735 scheduling passes don't touch it. */
1736 if (! flag_resched_modulo_sched
)
1737 mark_loop_unsched (loop
);
1739 /* The life-info is not valid any more. */
1740 df_set_bb_dirty (g
->bb
);
1742 apply_reg_moves (ps
);
1744 print_node_sched_params (dump_file
, g
->num_nodes
, ps
);
1745 /* Generate prolog and epilog. */
1746 generate_prolog_epilog (ps
, loop
, count_reg
, count_init
);
1750 free_partial_schedule (ps
);
1751 node_sched_param_vec
.release ();
1758 /* Release scheduler data, needed until now because of DFA. */
1759 haifa_sched_finish ();
1760 loop_optimizer_finalize ();
1763 /* The SMS scheduling algorithm itself
1764 -----------------------------------
1765 Input: 'O' an ordered list of insns of a loop.
1766 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1768 'Q' is the empty Set
1769 'PS' is the partial schedule; it holds the currently scheduled nodes with
1771 'PSP' previously scheduled predecessors.
1772 'PSS' previously scheduled successors.
1773 't(u)' the cycle where u is scheduled.
1774 'l(u)' is the latency of u.
1775 'd(v,u)' is the dependence distance from v to u.
1776 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1777 the node ordering phase.
1778 'check_hardware_resources_conflicts(u, PS, c)'
1779 run a trace around cycle/slot through DFA model
1780 to check resource conflicts involving instruction u
1781 at cycle c given the partial schedule PS.
1782 'add_to_partial_schedule_at_time(u, PS, c)'
1783 Add the node/instruction u to the partial schedule
1785 'calculate_register_pressure(PS)'
1786 Given a schedule of instructions, calculate the register
1787 pressure it implies. One implementation could be the
1788 maximum number of overlapping live ranges.
1789 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1790 registers available in the hardware.
1794 3. for each node u in O in pre-computed order
1795 4. if (PSP(u) != Q && PSS(u) == Q) then
1796 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1797 6. start = Early_start; end = Early_start + II - 1; step = 1
1798 11. else if (PSP(u) == Q && PSS(u) != Q) then
1799 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1800 13. start = Late_start; end = Late_start - II + 1; step = -1
1801 14. else if (PSP(u) != Q && PSS(u) != Q) then
1802 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1803 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1804 17. start = Early_start;
1805 18. end = min(Early_start + II - 1 , Late_start);
1807 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1808 21. start = ASAP(u); end = start + II - 1; step = 1
1812 24. for (c = start ; c != end ; c += step)
1813 25. if check_hardware_resources_conflicts(u, PS, c) then
1814 26. add_to_partial_schedule_at_time(u, PS, c)
1819 31. if (success == false) then
1821 33. if (II > maxII) then
1822 34. finish - failed to schedule
1827 39. if (calculate_register_pressure(PS) > maxRP) then
1830 42. compute epilogue & prologue
1831 43. finish - succeeded to schedule
1833 ??? The algorithm restricts the scheduling window to II cycles.
1834 In rare cases, it may be better to allow windows of II+1 cycles.
1835 The window would then start and end on the same row, but with
1836 different "must precede" and "must follow" requirements. */
1838 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1839 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1840 set to 0 to save compile time. */
1841 #define DFA_HISTORY SMS_DFA_HISTORY
1843 /* A threshold for the number of repeated unsuccessful attempts to insert
1844 an empty row, before we flush the partial schedule and start over. */
1845 #define MAX_SPLIT_NUM 10
1846 /* Given the partial schedule PS, this function calculates and returns the
1847 cycles in which we can schedule the node with the given index I.
1848 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1849 noticed that there are several cases in which we fail to SMS the loop
1850 because the sched window of a node is empty due to tight data-deps. In
1851 such cases we want to unschedule some of the predecessors/successors
1852 until we get non-empty scheduling window. It returns -1 if the
1853 scheduling window is empty and zero otherwise. */
1856 get_sched_window (partial_schedule_ptr ps
, ddg_node_ptr u_node
,
1857 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
,
1860 int start
, step
, end
;
1861 int early_start
, late_start
;
1863 auto_sbitmap
psp (ps
->g
->num_nodes
);
1864 auto_sbitmap
pss (ps
->g
->num_nodes
);
1865 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1866 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1872 /* 1. compute sched window for u (start, end, step). */
1875 psp_not_empty
= bitmap_and (psp
, u_node_preds
, sched_nodes
);
1876 pss_not_empty
= bitmap_and (pss
, u_node_succs
, sched_nodes
);
1878 /* We first compute a forward range (start <= end), then decide whether
1880 early_start
= INT_MIN
;
1881 late_start
= INT_MAX
;
1889 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1891 fprintf (dump_file
, "\nAnalyzing dependencies for node %d (INSN %d)"
1892 "; ii = %d\n\n", u_node
->cuid
, INSN_UID (u_node
->insn
), ii
);
1893 fprintf (dump_file
, "%11s %11s %11s %11s %5s\n",
1894 "start", "early start", "late start", "end", "time");
1895 fprintf (dump_file
, "=========== =========== =========== ==========="
1898 /* Calculate early_start and limit end. Both bounds are inclusive. */
1900 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1902 int v
= e
->src
->cuid
;
1904 if (bitmap_bit_p (sched_nodes
, v
))
1906 int p_st
= SCHED_TIME (v
);
1907 int earliest
= p_st
+ e
->latency
- (e
->distance
* ii
);
1908 int latest
= (e
->data_type
== MEM_DEP
? p_st
+ ii
- 1 : INT_MAX
);
1912 fprintf (dump_file
, "%11s %11d %11s %11d %5d",
1913 "", earliest
, "", latest
, p_st
);
1914 print_ddg_edge (dump_file
, e
);
1915 fprintf (dump_file
, "\n");
1918 early_start
= MAX (early_start
, earliest
);
1919 end
= MIN (end
, latest
);
1921 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1926 /* Calculate late_start and limit start. Both bounds are inclusive. */
1928 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1930 int v
= e
->dest
->cuid
;
1932 if (bitmap_bit_p (sched_nodes
, v
))
1934 int s_st
= SCHED_TIME (v
);
1935 int earliest
= (e
->data_type
== MEM_DEP
? s_st
- ii
+ 1 : INT_MIN
);
1936 int latest
= s_st
- e
->latency
+ (e
->distance
* ii
);
1940 fprintf (dump_file
, "%11d %11s %11d %11s %5d",
1941 earliest
, "", latest
, "", s_st
);
1942 print_ddg_edge (dump_file
, e
);
1943 fprintf (dump_file
, "\n");
1946 start
= MAX (start
, earliest
);
1947 late_start
= MIN (late_start
, latest
);
1949 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1954 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1956 fprintf (dump_file
, "----------- ----------- ----------- -----------"
1958 fprintf (dump_file
, "%11d %11d %11d %11d %5s %s\n",
1959 start
, early_start
, late_start
, end
, "",
1960 "(max, max, min, min)");
1963 /* Get a target scheduling window no bigger than ii. */
1964 if (early_start
== INT_MIN
&& late_start
== INT_MAX
)
1965 early_start
= NODE_ASAP (u_node
);
1966 else if (early_start
== INT_MIN
)
1967 early_start
= late_start
- (ii
- 1);
1968 late_start
= MIN (late_start
, early_start
+ (ii
- 1));
1970 /* Apply memory dependence limits. */
1971 start
= MAX (start
, early_start
);
1972 end
= MIN (end
, late_start
);
1974 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1975 fprintf (dump_file
, "%11s %11d %11d %11s %5s final window\n",
1976 "", start
, end
, "", "");
1978 /* If there are at least as many successors as predecessors, schedule the
1979 node close to its successors. */
1980 if (pss_not_empty
&& count_succs
>= count_preds
)
1982 std::swap (start
, end
);
1986 /* Now that we've finalized the window, make END an exclusive rather
1987 than an inclusive bound. */
1994 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
1997 fprintf (dump_file
, "\nEmpty window: start=%d, end=%d, step=%d\n",
2005 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
2006 node currently been scheduled. At the end of the calculation
2007 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
2008 U_NODE which are (1) already scheduled in the first/last row of
2009 U_NODE's scheduling window, (2) whose dependence inequality with U
2010 becomes an equality when U is scheduled in this same row, and (3)
2011 whose dependence latency is zero.
2013 The first and last rows are calculated using the following parameters:
2014 START/END rows - The cycles that begins/ends the traversal on the window;
2015 searching for an empty cycle to schedule U_NODE.
2016 STEP - The direction in which we traverse the window.
2017 II - The initiation interval. */
2020 calculate_must_precede_follow (ddg_node_ptr u_node
, int start
, int end
,
2021 int step
, int ii
, sbitmap sched_nodes
,
2022 sbitmap must_precede
, sbitmap must_follow
)
2025 int first_cycle_in_window
, last_cycle_in_window
;
2027 gcc_assert (must_precede
&& must_follow
);
2029 /* Consider the following scheduling window:
2030 {first_cycle_in_window, first_cycle_in_window+1, ...,
2031 last_cycle_in_window}. If step is 1 then the following will be
2032 the order we traverse the window: {start=first_cycle_in_window,
2033 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
2034 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
2035 end=first_cycle_in_window-1} if step is -1. */
2036 first_cycle_in_window
= (step
== 1) ? start
: end
- step
;
2037 last_cycle_in_window
= (step
== 1) ? end
- step
: start
;
2039 bitmap_clear (must_precede
);
2040 bitmap_clear (must_follow
);
2043 fprintf (dump_file
, "\nmust_precede: ");
2045 /* Instead of checking if:
2046 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
2047 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
2048 first_cycle_in_window)
2050 we use the fact that latency is non-negative:
2051 SCHED_TIME (e->src) - (e->distance * ii) <=
2052 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
2053 first_cycle_in_window
2055 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
2056 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2057 if (bitmap_bit_p (sched_nodes
, e
->src
->cuid
)
2058 && ((SCHED_TIME (e
->src
->cuid
) - (e
->distance
* ii
)) ==
2059 first_cycle_in_window
))
2062 fprintf (dump_file
, "%d ", e
->src
->cuid
);
2064 bitmap_set_bit (must_precede
, e
->src
->cuid
);
2068 fprintf (dump_file
, "\nmust_follow: ");
2070 /* Instead of checking if:
2071 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
2072 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
2073 last_cycle_in_window)
2075 we use the fact that latency is non-negative:
2076 SCHED_TIME (e->dest) + (e->distance * ii) >=
2077 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
2078 last_cycle_in_window
2080 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
2081 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2082 if (bitmap_bit_p (sched_nodes
, e
->dest
->cuid
)
2083 && ((SCHED_TIME (e
->dest
->cuid
) + (e
->distance
* ii
)) ==
2084 last_cycle_in_window
))
2087 fprintf (dump_file
, "%d ", e
->dest
->cuid
);
2089 bitmap_set_bit (must_follow
, e
->dest
->cuid
);
2093 fprintf (dump_file
, "\n");
2096 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
2097 parameters to decide if that's possible:
2098 PS - The partial schedule.
2099 U - The serial number of U_NODE.
2100 NUM_SPLITS - The number of row splits made so far.
2101 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
2102 the first row of the scheduling window)
2103 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
2104 last row of the scheduling window) */
2107 try_scheduling_node_in_cycle (partial_schedule_ptr ps
,
2108 int u
, int cycle
, sbitmap sched_nodes
,
2109 int *num_splits
, sbitmap must_precede
,
2110 sbitmap must_follow
)
2115 verify_partial_schedule (ps
, sched_nodes
);
2116 psi
= ps_add_node_check_conflicts (ps
, u
, cycle
, must_precede
, must_follow
);
2119 SCHED_TIME (u
) = cycle
;
2120 bitmap_set_bit (sched_nodes
, u
);
2124 fprintf (dump_file
, "Scheduled w/o split in %d\n", cycle
);
2131 /* This function implements the scheduling algorithm for SMS according to the
2133 static partial_schedule_ptr
2134 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
)
2137 int i
, c
, success
, num_splits
= 0;
2138 int flush_and_start_over
= true;
2139 int num_nodes
= g
->num_nodes
;
2140 int start
, end
, step
; /* Place together into one struct? */
2141 auto_sbitmap
sched_nodes (num_nodes
);
2142 auto_sbitmap
must_precede (num_nodes
);
2143 auto_sbitmap
must_follow (num_nodes
);
2144 auto_sbitmap
tobe_scheduled (num_nodes
);
2146 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
, DFA_HISTORY
);
2148 bitmap_ones (tobe_scheduled
);
2149 bitmap_clear (sched_nodes
);
2151 while (flush_and_start_over
&& (ii
< maxii
))
2155 fprintf (dump_file
, "Starting with ii=%d\n", ii
);
2156 flush_and_start_over
= false;
2157 bitmap_clear (sched_nodes
);
2159 for (i
= 0; i
< num_nodes
; i
++)
2161 int u
= nodes_order
[i
];
2162 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
2163 rtx_insn
*insn
= u_node
->insn
;
2165 if (!NONDEBUG_INSN_P (insn
))
2167 bitmap_clear_bit (tobe_scheduled
, u
);
2171 if (bitmap_bit_p (sched_nodes
, u
))
2174 /* Try to get non-empty scheduling window. */
2176 if (get_sched_window (ps
, u_node
, sched_nodes
, ii
, &start
,
2180 fprintf (dump_file
, "\nTrying to schedule node %d "
2181 "INSN = %d in (%d .. %d) step %d\n", u
, (INSN_UID
2182 (g
->nodes
[u
].insn
)), start
, end
, step
);
2184 gcc_assert ((step
> 0 && start
< end
)
2185 || (step
< 0 && start
> end
));
2187 calculate_must_precede_follow (u_node
, start
, end
, step
, ii
,
2188 sched_nodes
, must_precede
,
2191 for (c
= start
; c
!= end
; c
+= step
)
2193 sbitmap tmp_precede
, tmp_follow
;
2195 set_must_precede_follow (&tmp_follow
, must_follow
,
2196 &tmp_precede
, must_precede
,
2197 c
, start
, end
, step
);
2199 try_scheduling_node_in_cycle (ps
, u
, c
,
2201 &num_splits
, tmp_precede
,
2207 verify_partial_schedule (ps
, sched_nodes
);
2216 if (num_splits
>= MAX_SPLIT_NUM
)
2219 flush_and_start_over
= true;
2220 verify_partial_schedule (ps
, sched_nodes
);
2221 reset_partial_schedule (ps
, ii
);
2222 verify_partial_schedule (ps
, sched_nodes
);
2227 /* The scheduling window is exclusive of 'end'
2228 whereas compute_split_window() expects an inclusive,
2231 split_row
= compute_split_row (sched_nodes
, start
, end
- 1,
2234 split_row
= compute_split_row (sched_nodes
, end
+ 1, start
,
2237 ps_insert_empty_row (ps
, split_row
, sched_nodes
);
2238 i
--; /* Go back and retry node i. */
2241 fprintf (dump_file
, "num_splits=%d\n", num_splits
);
2244 /* ??? If (success), check register pressure estimates. */
2245 } /* Continue with next node. */
2246 } /* While flush_and_start_over. */
2249 free_partial_schedule (ps
);
2253 gcc_assert (bitmap_equal_p (tobe_scheduled
, sched_nodes
));
2258 /* This function inserts a new empty row into PS at the position
2259 according to SPLITROW, keeping all already scheduled instructions
2260 intact and updating their SCHED_TIME and cycle accordingly. */
2262 ps_insert_empty_row (partial_schedule_ptr ps
, int split_row
,
2263 sbitmap sched_nodes
)
2265 ps_insn_ptr crr_insn
;
2266 ps_insn_ptr
*rows_new
;
2268 int new_ii
= ii
+ 1;
2270 int *rows_length_new
;
2272 verify_partial_schedule (ps
, sched_nodes
);
2274 /* We normalize sched_time and rotate ps to have only non-negative sched
2275 times, for simplicity of updating cycles after inserting new row. */
2276 split_row
-= ps
->min_cycle
;
2277 split_row
= SMODULO (split_row
, ii
);
2279 fprintf (dump_file
, "split_row=%d\n", split_row
);
2281 reset_sched_times (ps
, PS_MIN_CYCLE (ps
));
2282 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
2284 rows_new
= (ps_insn_ptr
*) xcalloc (new_ii
, sizeof (ps_insn_ptr
));
2285 rows_length_new
= (int *) xcalloc (new_ii
, sizeof (int));
2286 for (row
= 0; row
< split_row
; row
++)
2288 rows_new
[row
] = ps
->rows
[row
];
2289 rows_length_new
[row
] = ps
->rows_length
[row
];
2290 ps
->rows
[row
] = NULL
;
2291 for (crr_insn
= rows_new
[row
];
2292 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2294 int u
= crr_insn
->id
;
2295 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
);
2297 SCHED_TIME (u
) = new_time
;
2298 crr_insn
->cycle
= new_time
;
2299 SCHED_ROW (u
) = new_time
% new_ii
;
2300 SCHED_STAGE (u
) = new_time
/ new_ii
;
2305 rows_new
[split_row
] = NULL
;
2307 for (row
= split_row
; row
< ii
; row
++)
2309 rows_new
[row
+ 1] = ps
->rows
[row
];
2310 rows_length_new
[row
+ 1] = ps
->rows_length
[row
];
2311 ps
->rows
[row
] = NULL
;
2312 for (crr_insn
= rows_new
[row
+ 1];
2313 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2315 int u
= crr_insn
->id
;
2316 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
) + 1;
2318 SCHED_TIME (u
) = new_time
;
2319 crr_insn
->cycle
= new_time
;
2320 SCHED_ROW (u
) = new_time
% new_ii
;
2321 SCHED_STAGE (u
) = new_time
/ new_ii
;
2326 ps
->min_cycle
= ps
->min_cycle
+ ps
->min_cycle
/ ii
2327 + (SMODULO (ps
->min_cycle
, ii
) >= split_row
? 1 : 0);
2328 ps
->max_cycle
= ps
->max_cycle
+ ps
->max_cycle
/ ii
2329 + (SMODULO (ps
->max_cycle
, ii
) >= split_row
? 1 : 0);
2331 ps
->rows
= rows_new
;
2332 free (ps
->rows_length
);
2333 ps
->rows_length
= rows_length_new
;
2335 gcc_assert (ps
->min_cycle
>= 0);
2337 verify_partial_schedule (ps
, sched_nodes
);
2340 fprintf (dump_file
, "min_cycle=%d, max_cycle=%d\n", ps
->min_cycle
,
2344 /* Given U_NODE which is the node that failed to be scheduled; LOW and
2345 UP which are the boundaries of it's scheduling window; compute using
2346 SCHED_NODES and II a row in the partial schedule that can be split
2347 which will separate a critical predecessor from a critical successor
2348 thereby expanding the window, and return it. */
2350 compute_split_row (sbitmap sched_nodes
, int low
, int up
, int ii
,
2351 ddg_node_ptr u_node
)
2354 int lower
= INT_MIN
, upper
= INT_MAX
;
2359 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2361 int v
= e
->src
->cuid
;
2363 if (bitmap_bit_p (sched_nodes
, v
)
2364 && (low
== SCHED_TIME (v
) + e
->latency
- (e
->distance
* ii
)))
2365 if (SCHED_TIME (v
) > lower
)
2368 lower
= SCHED_TIME (v
);
2374 crit_cycle
= SCHED_TIME (crit_pred
) + 1;
2375 return SMODULO (crit_cycle
, ii
);
2378 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2380 int v
= e
->dest
->cuid
;
2382 if (bitmap_bit_p (sched_nodes
, v
)
2383 && (up
== SCHED_TIME (v
) - e
->latency
+ (e
->distance
* ii
)))
2384 if (SCHED_TIME (v
) < upper
)
2387 upper
= SCHED_TIME (v
);
2393 crit_cycle
= SCHED_TIME (crit_succ
);
2394 return SMODULO (crit_cycle
, ii
);
2398 fprintf (dump_file
, "Both crit_pred and crit_succ are NULL\n");
2400 return SMODULO ((low
+ up
+ 1) / 2, ii
);
2404 verify_partial_schedule (partial_schedule_ptr ps
, sbitmap sched_nodes
)
2407 ps_insn_ptr crr_insn
;
2409 for (row
= 0; row
< ps
->ii
; row
++)
2413 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2415 int u
= crr_insn
->id
;
2418 gcc_assert (bitmap_bit_p (sched_nodes
, u
));
2419 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2420 popcount (sched_nodes) == number of insns in ps. */
2421 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
2422 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
2425 gcc_assert (ps
->rows_length
[row
] == length
);
2430 /* This page implements the algorithm for ordering the nodes of a DDG
2431 for modulo scheduling, activated through the
2432 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2434 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2435 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
2436 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
2437 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2438 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
2439 #define DEPTH(x) (ASAP ((x)))
2441 typedef struct node_order_params
* nopa
;
2443 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
2444 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
2445 static nopa
calculate_order_params (ddg_ptr
, int, int *);
2446 static int find_max_asap (ddg_ptr
, sbitmap
);
2447 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
2448 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
2450 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
2452 struct node_order_params
2459 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2461 check_nodes_order (int *node_order
, int num_nodes
)
2464 auto_sbitmap
tmp (num_nodes
);
2469 fprintf (dump_file
, "SMS final nodes order: \n");
2471 for (i
= 0; i
< num_nodes
; i
++)
2473 int u
= node_order
[i
];
2476 fprintf (dump_file
, "%d ", u
);
2477 gcc_assert (u
< num_nodes
&& u
>= 0 && !bitmap_bit_p (tmp
, u
));
2479 bitmap_set_bit (tmp
, u
);
2483 fprintf (dump_file
, "\n");
2486 /* Order the nodes of G for scheduling and pass the result in
2487 NODE_ORDER. Also set aux.count of each node to ASAP.
2488 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2490 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
, int *pmax_asap
)
2494 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
2496 nopa nops
= calculate_order_params (g
, mii
, pmax_asap
);
2499 print_sccs (dump_file
, sccs
, g
);
2501 order_nodes_of_sccs (sccs
, node_order
);
2503 if (sccs
->num_sccs
> 0)
2504 /* First SCC has the largest recurrence_length. */
2505 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
2507 /* Save ASAP before destroying node_order_params. */
2508 for (i
= 0; i
< g
->num_nodes
; i
++)
2510 ddg_node_ptr v
= &g
->nodes
[i
];
2511 v
->aux
.count
= ASAP (v
);
2515 free_ddg_all_sccs (sccs
);
2516 check_nodes_order (node_order
, g
->num_nodes
);
2522 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
2525 ddg_ptr g
= all_sccs
->ddg
;
2526 int num_nodes
= g
->num_nodes
;
2527 auto_sbitmap
prev_sccs (num_nodes
);
2528 auto_sbitmap
on_path (num_nodes
);
2529 auto_sbitmap
tmp (num_nodes
);
2530 auto_sbitmap
ones (num_nodes
);
2532 bitmap_clear (prev_sccs
);
2535 /* Perform the node ordering starting from the SCC with the highest recMII.
2536 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2537 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
2539 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
2541 /* Add nodes on paths from previous SCCs to the current SCC. */
2542 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
2543 bitmap_ior (tmp
, scc
->nodes
, on_path
);
2545 /* Add nodes on paths from the current SCC to previous SCCs. */
2546 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
2547 bitmap_ior (tmp
, tmp
, on_path
);
2549 /* Remove nodes of previous SCCs from current extended SCC. */
2550 bitmap_and_compl (tmp
, tmp
, prev_sccs
);
2552 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2553 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2556 /* Handle the remaining nodes that do not belong to any scc. Each call
2557 to order_nodes_in_scc handles a single connected component. */
2558 while (pos
< g
->num_nodes
)
2560 bitmap_and_compl (tmp
, ones
, prev_sccs
);
2561 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2565 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2566 static struct node_order_params
*
2567 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
, int *pmax_asap
)
2571 int num_nodes
= g
->num_nodes
;
2573 /* Allocate a place to hold ordering params for each node in the DDG. */
2574 nopa node_order_params_arr
;
2576 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2577 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
2578 sizeof (struct node_order_params
));
2580 /* Set the aux pointer of each node to point to its order_params structure. */
2581 for (u
= 0; u
< num_nodes
; u
++)
2582 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
2584 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2585 calculate ASAP, ALAP, mobility, distance, and height for each node
2586 in the dependence (direct acyclic) graph. */
2588 /* We assume that the nodes in the array are in topological order. */
2591 for (u
= 0; u
< num_nodes
; u
++)
2593 ddg_node_ptr u_node
= &g
->nodes
[u
];
2596 for (e
= u_node
->in
; e
; e
= e
->next_in
)
2597 if (e
->distance
== 0)
2598 ASAP (u_node
) = MAX (ASAP (u_node
),
2599 ASAP (e
->src
) + e
->latency
);
2600 max_asap
= MAX (max_asap
, ASAP (u_node
));
2603 for (u
= num_nodes
- 1; u
> -1; u
--)
2605 ddg_node_ptr u_node
= &g
->nodes
[u
];
2607 ALAP (u_node
) = max_asap
;
2608 HEIGHT (u_node
) = 0;
2609 for (e
= u_node
->out
; e
; e
= e
->next_out
)
2610 if (e
->distance
== 0)
2612 ALAP (u_node
) = MIN (ALAP (u_node
),
2613 ALAP (e
->dest
) - e
->latency
);
2614 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
2615 HEIGHT (e
->dest
) + e
->latency
);
2620 fprintf (dump_file
, "\nOrder params\n");
2621 for (u
= 0; u
< num_nodes
; u
++)
2623 ddg_node_ptr u_node
= &g
->nodes
[u
];
2625 fprintf (dump_file
, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u
,
2626 ASAP (u_node
), ALAP (u_node
), HEIGHT (u_node
));
2630 *pmax_asap
= max_asap
;
2631 return node_order_params_arr
;
2635 find_max_asap (ddg_ptr g
, sbitmap nodes
)
2640 sbitmap_iterator sbi
;
2642 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2644 ddg_node_ptr u_node
= &g
->nodes
[u
];
2646 if (max_asap
< ASAP (u_node
))
2648 max_asap
= ASAP (u_node
);
2656 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
2660 int min_mob
= INT_MAX
;
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_hv
< HEIGHT (u_node
))
2670 max_hv
= HEIGHT (u_node
);
2671 min_mob
= MOB (u_node
);
2674 else if ((max_hv
== HEIGHT (u_node
))
2675 && (min_mob
> MOB (u_node
)))
2677 min_mob
= MOB (u_node
);
2685 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
2689 int min_mob
= INT_MAX
;
2691 sbitmap_iterator sbi
;
2693 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2695 ddg_node_ptr u_node
= &g
->nodes
[u
];
2697 if (max_dv
< DEPTH (u_node
))
2699 max_dv
= DEPTH (u_node
);
2700 min_mob
= MOB (u_node
);
2703 else if ((max_dv
== DEPTH (u_node
))
2704 && (min_mob
> MOB (u_node
)))
2706 min_mob
= MOB (u_node
);
2713 /* Places the nodes of SCC into the NODE_ORDER array starting
2714 at position POS, according to the SMS ordering algorithm.
2715 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2716 the NODE_ORDER array, starting from position zero. */
2718 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
2719 int * node_order
, int pos
)
2721 enum sms_direction dir
;
2722 int num_nodes
= g
->num_nodes
;
2723 auto_sbitmap
workset (num_nodes
);
2724 auto_sbitmap
tmp (num_nodes
);
2725 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
2726 auto_sbitmap
predecessors (num_nodes
);
2727 auto_sbitmap
successors (num_nodes
);
2729 bitmap_clear (predecessors
);
2730 find_predecessors (predecessors
, g
, nodes_ordered
);
2732 bitmap_clear (successors
);
2733 find_successors (successors
, g
, nodes_ordered
);
2736 if (bitmap_and (tmp
, predecessors
, scc
))
2738 bitmap_copy (workset
, tmp
);
2741 else if (bitmap_and (tmp
, successors
, scc
))
2743 bitmap_copy (workset
, tmp
);
2750 bitmap_clear (workset
);
2751 if ((u
= find_max_asap (g
, scc
)) >= 0)
2752 bitmap_set_bit (workset
, u
);
2756 bitmap_clear (zero_bitmap
);
2757 while (!bitmap_equal_p (workset
, zero_bitmap
))
2760 ddg_node_ptr v_node
;
2761 sbitmap v_node_preds
;
2762 sbitmap v_node_succs
;
2766 while (!bitmap_equal_p (workset
, zero_bitmap
))
2768 v
= find_max_hv_min_mob (g
, workset
);
2769 v_node
= &g
->nodes
[v
];
2770 node_order
[pos
++] = v
;
2771 v_node_succs
= NODE_SUCCESSORS (v_node
);
2772 bitmap_and (tmp
, v_node_succs
, scc
);
2774 /* Don't consider the already ordered successors again. */
2775 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2776 bitmap_ior (workset
, workset
, tmp
);
2777 bitmap_clear_bit (workset
, v
);
2778 bitmap_set_bit (nodes_ordered
, v
);
2781 bitmap_clear (predecessors
);
2782 find_predecessors (predecessors
, g
, nodes_ordered
);
2783 bitmap_and (workset
, predecessors
, scc
);
2787 while (!bitmap_equal_p (workset
, zero_bitmap
))
2789 v
= find_max_dv_min_mob (g
, workset
);
2790 v_node
= &g
->nodes
[v
];
2791 node_order
[pos
++] = v
;
2792 v_node_preds
= NODE_PREDECESSORS (v_node
);
2793 bitmap_and (tmp
, v_node_preds
, scc
);
2795 /* Don't consider the already ordered predecessors again. */
2796 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2797 bitmap_ior (workset
, workset
, tmp
);
2798 bitmap_clear_bit (workset
, v
);
2799 bitmap_set_bit (nodes_ordered
, v
);
2802 bitmap_clear (successors
);
2803 find_successors (successors
, g
, nodes_ordered
);
2804 bitmap_and (workset
, successors
, scc
);
2807 sbitmap_free (zero_bitmap
);
2812 /* This page contains functions for manipulating partial-schedules during
2813 modulo scheduling. */
2815 /* Create a partial schedule and allocate a memory to hold II rows. */
2817 static partial_schedule_ptr
2818 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2820 partial_schedule_ptr ps
= XNEW (struct partial_schedule
);
2821 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2822 ps
->rows_length
= (int *) xcalloc (ii
, sizeof (int));
2823 ps
->reg_moves
.create (0);
2825 ps
->history
= history
;
2826 ps
->min_cycle
= INT_MAX
;
2827 ps
->max_cycle
= INT_MIN
;
2833 /* Free the PS_INSNs in rows array of the given partial schedule.
2834 ??? Consider caching the PS_INSN's. */
2836 free_ps_insns (partial_schedule_ptr ps
)
2840 for (i
= 0; i
< ps
->ii
; i
++)
2844 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2847 ps
->rows
[i
] = ps_insn
;
2853 /* Free all the memory allocated to the partial schedule. */
2856 free_partial_schedule (partial_schedule_ptr ps
)
2858 ps_reg_move_info
*move
;
2864 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
2865 sbitmap_free (move
->uses
);
2866 ps
->reg_moves
.release ();
2870 free (ps
->rows_length
);
2874 /* Clear the rows array with its PS_INSNs, and create a new one with
2878 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2883 if (new_ii
== ps
->ii
)
2885 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2886 * sizeof (ps_insn_ptr
));
2887 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2888 ps
->rows_length
= (int *) xrealloc (ps
->rows_length
, new_ii
* sizeof (int));
2889 memset (ps
->rows_length
, 0, new_ii
* sizeof (int));
2891 ps
->min_cycle
= INT_MAX
;
2892 ps
->max_cycle
= INT_MIN
;
2895 /* Prints the partial schedule as an ii rows array, for each rows
2896 print the ids of the insns in it. */
2898 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2902 for (i
= 0; i
< ps
->ii
; i
++)
2904 ps_insn_ptr ps_i
= ps
->rows
[i
];
2906 fprintf (dump
, "\n[ROW %d ]: ", i
);
2909 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_i
->id
);
2912 fprintf (dump
, "%d (branch), ", INSN_UID (insn
));
2914 fprintf (dump
, "%d, ", INSN_UID (insn
));
2916 ps_i
= ps_i
->next_in_row
;
2921 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2923 create_ps_insn (int id
, int cycle
)
2925 ps_insn_ptr ps_i
= XNEW (struct ps_insn
);
2928 ps_i
->next_in_row
= NULL
;
2929 ps_i
->prev_in_row
= NULL
;
2930 ps_i
->cycle
= cycle
;
2936 /* Removes the given PS_INSN from the partial schedule. */
2938 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2942 gcc_assert (ps
&& ps_i
);
2944 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2945 if (! ps_i
->prev_in_row
)
2947 gcc_assert (ps_i
== ps
->rows
[row
]);
2948 ps
->rows
[row
] = ps_i
->next_in_row
;
2950 ps
->rows
[row
]->prev_in_row
= NULL
;
2954 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
2955 if (ps_i
->next_in_row
)
2956 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
2959 ps
->rows_length
[row
] -= 1;
2964 /* Unlike what literature describes for modulo scheduling (which focuses
2965 on VLIW machines) the order of the instructions inside a cycle is
2966 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2967 where the current instruction should go relative to the already
2968 scheduled instructions in the given cycle. Go over these
2969 instructions and find the first possible column to put it in. */
2971 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2972 sbitmap must_precede
, sbitmap must_follow
)
2974 ps_insn_ptr next_ps_i
;
2975 ps_insn_ptr first_must_follow
= NULL
;
2976 ps_insn_ptr last_must_precede
= NULL
;
2977 ps_insn_ptr last_in_row
= NULL
;
2983 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2985 /* Find the first must follow and the last must precede
2986 and insert the node immediately after the must precede
2987 but make sure that it there is no must follow after it. */
2988 for (next_ps_i
= ps
->rows
[row
];
2990 next_ps_i
= next_ps_i
->next_in_row
)
2993 && bitmap_bit_p (must_follow
, next_ps_i
->id
)
2994 && ! first_must_follow
)
2995 first_must_follow
= next_ps_i
;
2996 if (must_precede
&& bitmap_bit_p (must_precede
, next_ps_i
->id
))
2998 /* If we have already met a node that must follow, then
2999 there is no possible column. */
3000 if (first_must_follow
)
3003 last_must_precede
= next_ps_i
;
3005 /* The closing branch must be the last in the row. */
3007 && bitmap_bit_p (must_precede
, next_ps_i
->id
)
3008 && JUMP_P (ps_rtl_insn (ps
, next_ps_i
->id
)))
3011 last_in_row
= next_ps_i
;
3014 /* The closing branch is scheduled as well. Make sure there is no
3015 dependent instruction after it as the branch should be the last
3016 instruction in the row. */
3017 if (JUMP_P (ps_rtl_insn (ps
, ps_i
->id
)))
3019 if (first_must_follow
)
3023 /* Make the branch the last in the row. New instructions
3024 will be inserted at the beginning of the row or after the
3025 last must_precede instruction thus the branch is guaranteed
3026 to remain the last instruction in the row. */
3027 last_in_row
->next_in_row
= ps_i
;
3028 ps_i
->prev_in_row
= last_in_row
;
3029 ps_i
->next_in_row
= NULL
;
3032 ps
->rows
[row
] = ps_i
;
3036 /* Now insert the node after INSERT_AFTER_PSI. */
3038 if (! last_must_precede
)
3040 ps_i
->next_in_row
= ps
->rows
[row
];
3041 ps_i
->prev_in_row
= NULL
;
3042 if (ps_i
->next_in_row
)
3043 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3044 ps
->rows
[row
] = ps_i
;
3048 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
3049 last_must_precede
->next_in_row
= ps_i
;
3050 ps_i
->prev_in_row
= last_must_precede
;
3051 if (ps_i
->next_in_row
)
3052 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3058 /* Advances the PS_INSN one column in its current row; returns false
3059 in failure and true in success. Bit N is set in MUST_FOLLOW if
3060 the node with cuid N must be come after the node pointed to by
3061 PS_I when scheduled in the same cycle. */
3063 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
3064 sbitmap must_follow
)
3066 ps_insn_ptr prev
, next
;
3072 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3074 if (! ps_i
->next_in_row
)
3077 /* Check if next_in_row is dependent on ps_i, both having same sched
3078 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
3079 if (must_follow
&& bitmap_bit_p (must_follow
, ps_i
->next_in_row
->id
))
3082 /* Advance PS_I over its next_in_row in the doubly linked list. */
3083 prev
= ps_i
->prev_in_row
;
3084 next
= ps_i
->next_in_row
;
3086 if (ps_i
== ps
->rows
[row
])
3087 ps
->rows
[row
] = next
;
3089 ps_i
->next_in_row
= next
->next_in_row
;
3091 if (next
->next_in_row
)
3092 next
->next_in_row
->prev_in_row
= ps_i
;
3094 next
->next_in_row
= ps_i
;
3095 ps_i
->prev_in_row
= next
;
3097 next
->prev_in_row
= prev
;
3099 prev
->next_in_row
= next
;
3104 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
3105 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
3106 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
3107 before/after (respectively) the node pointed to by PS_I when scheduled
3108 in the same cycle. */
3110 add_node_to_ps (partial_schedule_ptr ps
, int id
, int cycle
,
3111 sbitmap must_precede
, sbitmap must_follow
)
3114 int row
= SMODULO (cycle
, ps
->ii
);
3116 if (ps
->rows_length
[row
] >= issue_rate
)
3119 ps_i
= create_ps_insn (id
, cycle
);
3121 /* Finds and inserts PS_I according to MUST_FOLLOW and
3123 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
3129 ps
->rows_length
[row
] += 1;
3133 /* Advance time one cycle. Assumes DFA is being used. */
3135 advance_one_cycle (void)
3137 if (targetm
.sched
.dfa_pre_cycle_insn
)
3138 state_transition (curr_state
,
3139 targetm
.sched
.dfa_pre_cycle_insn ());
3141 state_transition (curr_state
, NULL
);
3143 if (targetm
.sched
.dfa_post_cycle_insn
)
3144 state_transition (curr_state
,
3145 targetm
.sched
.dfa_post_cycle_insn ());
3150 /* Checks if PS has resource conflicts according to DFA, starting from
3151 FROM cycle to TO cycle; returns true if there are conflicts and false
3152 if there are no conflicts. Assumes DFA is being used. */
3154 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
3158 state_reset (curr_state
);
3160 for (cycle
= from
; cycle
<= to
; cycle
++)
3162 ps_insn_ptr crr_insn
;
3163 /* Holds the remaining issue slots in the current row. */
3164 int can_issue_more
= issue_rate
;
3166 /* Walk through the DFA for the current row. */
3167 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
3169 crr_insn
= crr_insn
->next_in_row
)
3171 rtx_insn
*insn
= ps_rtl_insn (ps
, crr_insn
->id
);
3173 if (!NONDEBUG_INSN_P (insn
))
3176 /* Check if there is room for the current insn. */
3177 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
3180 /* Update the DFA state and return with failure if the DFA found
3181 resource conflicts. */
3182 if (state_transition (curr_state
, insn
) >= 0)
3185 if (targetm
.sched
.variable_issue
)
3187 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
3188 insn
, can_issue_more
);
3189 /* A naked CLOBBER or USE generates no instruction, so don't
3190 let them consume issue slots. */
3191 else if (GET_CODE (PATTERN (insn
)) != USE
3192 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3196 /* Advance the DFA to the next cycle. */
3197 advance_one_cycle ();
3202 /* Checks if the given node causes resource conflicts when added to PS at
3203 cycle C. If not the node is added to PS and returned; otherwise zero
3204 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
3205 cuid N must be come before/after (respectively) the node pointed to by
3206 PS_I when scheduled in the same cycle. */
3208 ps_add_node_check_conflicts (partial_schedule_ptr ps
, int n
,
3209 int c
, sbitmap must_precede
,
3210 sbitmap must_follow
)
3212 int has_conflicts
= 0;
3215 /* First add the node to the PS, if this succeeds check for
3216 conflicts, trying different issue slots in the same row. */
3217 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
3218 return NULL
; /* Failed to insert the node at the given cycle. */
3220 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3222 && ps_has_conflicts (ps
,
3226 /* Try different issue slots to find one that the given node can be
3227 scheduled in without conflicts. */
3228 while (has_conflicts
)
3230 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
3232 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3234 && ps_has_conflicts (ps
,
3241 remove_node_from_ps (ps
, ps_i
);
3245 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
3246 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
3250 /* Calculate the stage count of the partial schedule PS. The calculation
3251 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3253 calculate_stage_count (partial_schedule_ptr ps
, int rotation_amount
)
3255 int new_min_cycle
= PS_MIN_CYCLE (ps
) - rotation_amount
;
3256 int new_max_cycle
= PS_MAX_CYCLE (ps
) - rotation_amount
;
3257 int stage_count
= CALC_STAGE_COUNT (-1, new_min_cycle
, ps
->ii
);
3259 /* The calculation of stage count is done adding the number of stages
3260 before cycle zero and after cycle zero. */
3261 stage_count
+= CALC_STAGE_COUNT (new_max_cycle
, 0, ps
->ii
);
3266 /* Rotate the rows of PS such that insns scheduled at time
3267 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3269 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
3271 int i
, row
, backward_rotates
;
3272 int last_row
= ps
->ii
- 1;
3274 if (start_cycle
== 0)
3277 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
3279 /* Revisit later and optimize this into a single loop. */
3280 for (i
= 0; i
< backward_rotates
; i
++)
3282 ps_insn_ptr first_row
= ps
->rows
[0];
3283 int first_row_length
= ps
->rows_length
[0];
3285 for (row
= 0; row
< last_row
; row
++)
3287 ps
->rows
[row
] = ps
->rows
[row
+ 1];
3288 ps
->rows_length
[row
] = ps
->rows_length
[row
+ 1];
3291 ps
->rows
[last_row
] = first_row
;
3292 ps
->rows_length
[last_row
] = first_row_length
;
3295 ps
->max_cycle
-= start_cycle
;
3296 ps
->min_cycle
-= start_cycle
;
3299 #endif /* INSN_SCHEDULING */
3301 /* Run instruction scheduler. */
3302 /* Perform SMS module scheduling. */
3306 const pass_data pass_data_sms
=
3308 RTL_PASS
, /* type */
3310 OPTGROUP_NONE
, /* optinfo_flags */
3312 0, /* properties_required */
3313 0, /* properties_provided */
3314 0, /* properties_destroyed */
3315 0, /* todo_flags_start */
3316 TODO_df_finish
, /* todo_flags_finish */
3319 class pass_sms
: public rtl_opt_pass
3322 pass_sms (gcc::context
*ctxt
)
3323 : rtl_opt_pass (pass_data_sms
, ctxt
)
3326 /* opt_pass methods: */
3327 virtual bool gate (function
*)
3329 return (optimize
> 0 && flag_modulo_sched
);
3332 virtual unsigned int execute (function
*);
3334 }; // class pass_sms
3337 pass_sms::execute (function
*fun ATTRIBUTE_UNUSED
)
3339 #ifdef INSN_SCHEDULING
3342 /* Collect loop information to be used in SMS. */
3343 cfg_layout_initialize (0);
3346 /* Update the life information, because we add pseudos. */
3347 max_regno
= max_reg_num ();
3349 /* Finalize layout changes. */
3350 FOR_EACH_BB_FN (bb
, fun
)
3351 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3352 bb
->aux
= bb
->next_bb
;
3353 free_dominance_info (CDI_DOMINATORS
);
3354 cfg_layout_finalize ();
3355 #endif /* INSN_SCHEDULING */
3362 make_pass_sms (gcc::context
*ctxt
)
3364 return new pass_sms (ctxt
);