1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004-2019 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"
43 #include "tree-pass.h"
45 #include "loop-unroll.h"
47 #ifdef INSN_SCHEDULING
49 /* This file contains the implementation of the Swing Modulo Scheduler,
50 described in the following references:
51 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
52 Lifetime--sensitive modulo scheduling in a production environment.
53 IEEE Trans. on Comps., 50(3), March 2001
54 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
55 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
56 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
58 The basic structure is:
59 1. Build a data-dependence graph (DDG) for each loop.
60 2. Use the DDG to order the insns of a loop (not in topological order
61 necessarily, but rather) trying to place each insn after all its
62 predecessors _or_ after all its successors.
63 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
64 4. Use the ordering to perform list-scheduling of the loop:
65 1. Set II = MII. We will try to schedule the loop within II cycles.
66 2. Try to schedule the insns one by one according to the ordering.
67 For each insn compute an interval of cycles by considering already-
68 scheduled preds and succs (and associated latencies); try to place
69 the insn in the cycles of this window checking for potential
70 resource conflicts (using the DFA interface).
71 Note: this is different from the cycle-scheduling of schedule_insns;
72 here the insns are not scheduled monotonically top-down (nor bottom-
74 3. If failed in scheduling all insns - bump II++ and try again, unless
75 II reaches an upper bound MaxII, in which case report failure.
76 5. If we succeeded in scheduling the loop within II cycles, we now
77 generate prolog and epilog, decrease the counter of the loop, and
78 perform modulo variable expansion for live ranges that span more than
79 II cycles (i.e. use register copies to prevent a def from overwriting
80 itself before reaching the use).
82 SMS works with countable loops (1) whose control part can be easily
83 decoupled from the rest of the loop and (2) whose loop count can
84 be easily adjusted. This is because we peel a constant number of
85 iterations into a prologue and epilogue for which we want to avoid
86 emitting the control part, and a kernel which is to iterate that
87 constant number of iterations less than the original loop. So the
88 control part should be a set of insns clearly identified and having
89 its own iv, not otherwise used in the loop (at-least for now), which
90 initializes a register before the loop to the number of iterations.
91 Currently SMS relies on the do-loop pattern to recognize such loops,
92 where (1) the control part comprises of all insns defining and/or
93 using a certain 'count' register and (2) the loop count can be
94 adjusted by modifying this register prior to the loop.
95 TODO: Rely on cfgloop analysis instead. */
97 /* This page defines partial-schedule structures and functions for
100 typedef struct partial_schedule
*partial_schedule_ptr
;
101 typedef struct ps_insn
*ps_insn_ptr
;
103 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
104 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
106 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
107 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
109 /* Perform signed modulo, always returning a non-negative value. */
110 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
112 /* The number of different iterations the nodes in ps span, assuming
113 the stage boundaries are placed efficiently. */
114 #define CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \
116 /* The stage count of ps. */
117 #define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count)
119 /* A single instruction in the partial schedule. */
122 /* Identifies the instruction to be scheduled. Values smaller than
123 the ddg's num_nodes refer directly to ddg nodes. A value of
124 X - num_nodes refers to register move X. */
127 /* The (absolute) cycle in which the PS instruction is scheduled.
128 Same as SCHED_TIME (node). */
131 /* The next/prev PS_INSN in the same row. */
132 ps_insn_ptr next_in_row
,
137 /* Information about a register move that has been added to a partial
139 struct ps_reg_move_info
141 /* The source of the move is defined by the ps_insn with id DEF.
142 The destination is used by the ps_insns with the ids in USES. */
146 /* The original form of USES' instructions used OLD_REG, but they
147 should now use NEW_REG. */
151 /* The number of consecutive stages that the move occupies. */
152 int num_consecutive_stages
;
154 /* An instruction that sets NEW_REG to the correct value. The first
155 move associated with DEF will have an rhs of OLD_REG; later moves
156 use the result of the previous move. */
160 /* Holds the partial schedule as an array of II rows. Each entry of the
161 array points to a linked list of PS_INSNs, which represents the
162 instructions that are scheduled for that row. */
163 struct partial_schedule
165 int ii
; /* Number of rows in the partial schedule. */
166 int history
; /* Threshold for conflict checking using DFA. */
168 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
171 /* All the moves added for this partial schedule. Index X has
172 a ps_insn id of X + g->num_nodes. */
173 vec
<ps_reg_move_info
> reg_moves
;
175 /* rows_length[i] holds the number of instructions in the row.
176 It is used only (as an optimization) to back off quickly from
177 trying to schedule a node in a full row; that is, to avoid running
178 through futile DFA state transitions. */
181 /* The earliest absolute cycle of an insn in the partial schedule. */
184 /* The latest absolute cycle of an insn in the partial schedule. */
187 ddg_ptr g
; /* The DDG of the insns in the partial schedule. */
189 int stage_count
; /* The stage count of the partial schedule. */
193 static partial_schedule_ptr
create_partial_schedule (int ii
, ddg_ptr
, int history
);
194 static void free_partial_schedule (partial_schedule_ptr
);
195 static void reset_partial_schedule (partial_schedule_ptr
, int new_ii
);
196 void print_partial_schedule (partial_schedule_ptr
, FILE *);
197 static void verify_partial_schedule (partial_schedule_ptr
, sbitmap
);
198 static ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr
,
199 int, int, sbitmap
, sbitmap
);
200 static void rotate_partial_schedule (partial_schedule_ptr
, int);
201 void set_row_column_for_ps (partial_schedule_ptr
);
202 static void ps_insert_empty_row (partial_schedule_ptr
, int, sbitmap
);
203 static int compute_split_row (sbitmap
, int, int, int, ddg_node_ptr
);
206 /* This page defines constants and structures for the modulo scheduling
209 static int sms_order_nodes (ddg_ptr
, int, int *, int *);
210 static void set_node_sched_params (ddg_ptr
);
211 static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr
, int, int, int *);
212 static void permute_partial_schedule (partial_schedule_ptr
, rtx_insn
*);
213 static void generate_prolog_epilog (partial_schedule_ptr
, class loop
*,
215 static int calculate_stage_count (partial_schedule_ptr
, int);
216 static void calculate_must_precede_follow (ddg_node_ptr
, int, int,
217 int, int, sbitmap
, sbitmap
, sbitmap
);
218 static int get_sched_window (partial_schedule_ptr
, ddg_node_ptr
,
219 sbitmap
, int, int *, int *, int *);
220 static bool try_scheduling_node_in_cycle (partial_schedule_ptr
, int, int,
221 sbitmap
, int *, sbitmap
, sbitmap
);
222 static void remove_node_from_ps (partial_schedule_ptr
, ps_insn_ptr
);
224 #define NODE_ASAP(node) ((node)->aux.count)
226 #define SCHED_PARAMS(x) (&node_sched_param_vec[x])
227 #define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
228 #define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
229 #define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
230 #define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
232 /* The scheduling parameters held for each node. */
233 typedef struct node_sched_params
235 int time
; /* The absolute scheduling cycle. */
237 int row
; /* Holds time % ii. */
238 int stage
; /* Holds time / ii. */
240 /* The column of a node inside the ps. If nodes u, v are on the same row,
241 u will precede v if column (u) < column (v). */
243 } *node_sched_params_ptr
;
245 /* The following three functions are copied from the current scheduler
246 code in order to use sched_analyze() for computing the dependencies.
247 They are used when initializing the sched_info structure. */
249 sms_print_insn (const rtx_insn
*insn
, int aligned ATTRIBUTE_UNUSED
)
253 sprintf (tmp
, "i%4d", INSN_UID (insn
));
258 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
259 regset used ATTRIBUTE_UNUSED
)
263 static struct common_sched_info_def sms_common_sched_info
;
265 static struct sched_deps_info_def sms_sched_deps_info
=
267 compute_jump_reg_dependencies
,
268 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
273 static struct haifa_sched_info sms_sched_info
=
282 NULL
, /* insn_finishes_block_p */
287 NULL
, NULL
, NULL
, NULL
,
292 /* Partial schedule instruction ID in PS is a register move. Return
293 information about it. */
294 static struct ps_reg_move_info
*
295 ps_reg_move (partial_schedule_ptr ps
, int id
)
297 gcc_checking_assert (id
>= ps
->g
->num_nodes
);
298 return &ps
->reg_moves
[id
- ps
->g
->num_nodes
];
301 /* Return the rtl instruction that is being scheduled by partial schedule
302 instruction ID, which belongs to schedule PS. */
304 ps_rtl_insn (partial_schedule_ptr ps
, int id
)
306 if (id
< ps
->g
->num_nodes
)
307 return ps
->g
->nodes
[id
].insn
;
309 return ps_reg_move (ps
, id
)->insn
;
312 /* Partial schedule instruction ID, which belongs to PS, occurred in
313 the original (unscheduled) loop. Return the first instruction
314 in the loop that was associated with ps_rtl_insn (PS, ID).
315 If the instruction had some notes before it, this is the first
318 ps_first_note (partial_schedule_ptr ps
, int id
)
320 gcc_assert (id
< ps
->g
->num_nodes
);
321 return ps
->g
->nodes
[id
].first_note
;
324 /* Return the number of consecutive stages that are occupied by
325 partial schedule instruction ID in PS. */
327 ps_num_consecutive_stages (partial_schedule_ptr ps
, int id
)
329 if (id
< ps
->g
->num_nodes
)
332 return ps_reg_move (ps
, id
)->num_consecutive_stages
;
335 /* Given HEAD and TAIL which are the first and last insns in a loop;
336 return the register which controls the loop. Return zero if it has
337 more than one occurrence in the loop besides the control part or the
338 do-loop pattern is not of the form we expect. */
340 doloop_register_get (rtx_insn
*head
, rtx_insn
*tail
)
343 rtx_insn
*insn
, *first_insn_not_to_check
;
348 if (!targetm
.code_for_doloop_end
)
351 /* TODO: Free SMS's dependence on doloop_condition_get. */
352 condition
= doloop_condition_get (tail
);
356 if (REG_P (XEXP (condition
, 0)))
357 reg
= XEXP (condition
, 0);
358 else if (GET_CODE (XEXP (condition
, 0)) == PLUS
359 && REG_P (XEXP (XEXP (condition
, 0), 0)))
360 reg
= XEXP (XEXP (condition
, 0), 0);
364 /* Check that the COUNT_REG has no other occurrences in the loop
365 until the decrement. We assume the control part consists of
366 either a single (parallel) branch-on-count or a (non-parallel)
367 branch immediately preceded by a single (decrement) insn. */
368 first_insn_not_to_check
= (GET_CODE (PATTERN (tail
)) == PARALLEL
? tail
369 : prev_nondebug_insn (tail
));
371 for (insn
= head
; insn
!= first_insn_not_to_check
; insn
= NEXT_INSN (insn
))
372 if (!DEBUG_INSN_P (insn
) && reg_mentioned_p (reg
, insn
))
376 fprintf (dump_file
, "SMS count_reg found ");
377 print_rtl_single (dump_file
, reg
);
378 fprintf (dump_file
, " outside control in insn:\n");
379 print_rtl_single (dump_file
, insn
);
388 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
389 that the number of iterations is a compile-time constant. If so,
390 return the rtx_insn that sets COUNT_REG to a constant, and set COUNT to
391 this constant. Otherwise return 0. */
393 const_iteration_count (rtx count_reg
, basic_block pre_header
,
397 rtx_insn
*head
, *tail
;
402 get_ebb_head_tail (pre_header
, pre_header
, &head
, &tail
);
404 for (insn
= tail
; insn
!= PREV_INSN (head
); insn
= PREV_INSN (insn
))
405 if (NONDEBUG_INSN_P (insn
) && single_set (insn
) &&
406 rtx_equal_p (count_reg
, SET_DEST (single_set (insn
))))
408 rtx pat
= single_set (insn
);
410 if (CONST_INT_P (SET_SRC (pat
)))
412 *count
= INTVAL (SET_SRC (pat
));
422 /* A very simple resource-based lower bound on the initiation interval.
423 ??? Improve the accuracy of this bound by considering the
424 utilization of various units. */
428 if (targetm
.sched
.sms_res_mii
)
429 return targetm
.sched
.sms_res_mii (g
);
431 return ((g
->num_nodes
- g
->num_debug
) / issue_rate
);
435 /* A vector that contains the sched data for each ps_insn. */
436 static vec
<node_sched_params
> node_sched_param_vec
;
438 /* Allocate sched_params for each node and initialize it. */
440 set_node_sched_params (ddg_ptr g
)
442 node_sched_param_vec
.truncate (0);
443 node_sched_param_vec
.safe_grow_cleared (g
->num_nodes
);
446 /* Make sure that node_sched_param_vec has an entry for every move in PS. */
448 extend_node_sched_params (partial_schedule_ptr ps
)
450 node_sched_param_vec
.safe_grow_cleared (ps
->g
->num_nodes
451 + ps
->reg_moves
.length ());
454 /* Update the sched_params (time, row and stage) for node U using the II,
455 the CYCLE of U and MIN_CYCLE.
456 We're not simply taking the following
457 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
458 because the stages may not be aligned on cycle 0. */
460 update_node_sched_params (int u
, int ii
, int cycle
, int min_cycle
)
462 int sc_until_cycle_zero
;
465 SCHED_TIME (u
) = cycle
;
466 SCHED_ROW (u
) = SMODULO (cycle
, ii
);
468 /* The calculation of stage count is done adding the number
469 of stages before cycle zero and after cycle zero. */
470 sc_until_cycle_zero
= CALC_STAGE_COUNT (-1, min_cycle
, ii
);
472 if (SCHED_TIME (u
) < 0)
474 stage
= CALC_STAGE_COUNT (-1, SCHED_TIME (u
), ii
);
475 SCHED_STAGE (u
) = sc_until_cycle_zero
- stage
;
479 stage
= CALC_STAGE_COUNT (SCHED_TIME (u
), 0, ii
);
480 SCHED_STAGE (u
) = sc_until_cycle_zero
+ stage
- 1;
485 print_node_sched_params (FILE *file
, int num_nodes
, partial_schedule_ptr ps
)
491 for (i
= 0; i
< num_nodes
; i
++)
493 node_sched_params_ptr nsp
= SCHED_PARAMS (i
);
495 fprintf (file
, "Node = %d; INSN = %d\n", i
,
496 INSN_UID (ps_rtl_insn (ps
, i
)));
497 fprintf (file
, " asap = %d:\n", NODE_ASAP (&ps
->g
->nodes
[i
]));
498 fprintf (file
, " time = %d:\n", nsp
->time
);
499 fprintf (file
, " stage = %d:\n", nsp
->stage
);
503 /* Set SCHED_COLUMN for each instruction in row ROW of PS. */
505 set_columns_for_row (partial_schedule_ptr ps
, int row
)
507 ps_insn_ptr cur_insn
;
511 for (cur_insn
= ps
->rows
[row
]; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
512 SCHED_COLUMN (cur_insn
->id
) = column
++;
515 /* Set SCHED_COLUMN for each instruction in PS. */
517 set_columns_for_ps (partial_schedule_ptr ps
)
521 for (row
= 0; row
< ps
->ii
; row
++)
522 set_columns_for_row (ps
, row
);
525 /* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
526 Its single predecessor has already been scheduled, as has its
527 ddg node successors. (The move may have also another move as its
528 successor, in which case that successor will be scheduled later.)
530 The move is part of a chain that satisfies register dependencies
531 between a producing ddg node and various consuming ddg nodes.
532 If some of these dependencies have a distance of 1 (meaning that
533 the use is upward-exposed) then DISTANCE1_USES is nonnull and
534 contains the set of uses with distance-1 dependencies.
535 DISTANCE1_USES is null otherwise.
537 MUST_FOLLOW is a scratch bitmap that is big enough to hold
538 all current ps_insn ids.
540 Return true on success. */
542 schedule_reg_move (partial_schedule_ptr ps
, int i_reg_move
,
543 sbitmap distance1_uses
, sbitmap must_follow
)
546 int this_time
, this_distance
, this_start
, this_end
, this_latency
;
547 int start
, end
, c
, ii
;
548 sbitmap_iterator sbi
;
549 ps_reg_move_info
*move
;
553 move
= ps_reg_move (ps
, i_reg_move
);
557 fprintf (dump_file
, "Scheduling register move INSN %d; ii = %d"
558 ", min cycle = %d\n\n", INSN_UID (move
->insn
), ii
,
560 print_rtl_single (dump_file
, move
->insn
);
561 fprintf (dump_file
, "\n%11s %11s %5s\n", "start", "end", "time");
562 fprintf (dump_file
, "=========== =========== =====\n");
568 /* For dependencies of distance 1 between a producer ddg node A
569 and consumer ddg node B, we have a chain of dependencies:
571 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
573 where Mi is the ith move. For dependencies of distance 0 between
574 a producer ddg node A and consumer ddg node C, we have a chain of
577 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
579 where Mi' occupies the same position as Mi but occurs a stage later.
580 We can only schedule each move once, so if we have both types of
581 chain, we model the second as:
583 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
585 First handle the dependencies between the previously-scheduled
586 predecessor and the move. */
587 this_insn
= ps_rtl_insn (ps
, move
->def
);
588 this_latency
= insn_latency (this_insn
, move
->insn
);
589 this_distance
= distance1_uses
&& move
->def
< ps
->g
->num_nodes
? 1 : 0;
590 this_time
= SCHED_TIME (move
->def
) - this_distance
* ii
;
591 this_start
= this_time
+ this_latency
;
592 this_end
= this_time
+ ii
;
594 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
595 this_start
, this_end
, SCHED_TIME (move
->def
),
596 INSN_UID (this_insn
), this_latency
, this_distance
,
597 INSN_UID (move
->insn
));
599 if (start
< this_start
)
604 /* Handle the dependencies between the move and previously-scheduled
606 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, u
, sbi
)
608 this_insn
= ps_rtl_insn (ps
, u
);
609 this_latency
= insn_latency (move
->insn
, this_insn
);
610 if (distance1_uses
&& !bitmap_bit_p (distance1_uses
, u
))
614 this_time
= SCHED_TIME (u
) + this_distance
* ii
;
615 this_start
= this_time
- ii
;
616 this_end
= this_time
- this_latency
;
618 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
619 this_start
, this_end
, SCHED_TIME (u
), INSN_UID (move
->insn
),
620 this_latency
, this_distance
, INSN_UID (this_insn
));
622 if (start
< this_start
)
630 fprintf (dump_file
, "----------- ----------- -----\n");
631 fprintf (dump_file
, "%11d %11d %5s %s\n", start
, end
, "", "(max, min)");
634 bitmap_clear (must_follow
);
635 bitmap_set_bit (must_follow
, move
->def
);
637 start
= MAX (start
, end
- (ii
- 1));
638 for (c
= end
; c
>= start
; c
--)
640 psi
= ps_add_node_check_conflicts (ps
, i_reg_move
, c
,
641 move
->uses
, must_follow
);
644 update_node_sched_params (i_reg_move
, ii
, c
, PS_MIN_CYCLE (ps
));
646 fprintf (dump_file
, "\nScheduled register move INSN %d at"
647 " time %d, row %d\n\n", INSN_UID (move
->insn
), c
,
648 SCHED_ROW (i_reg_move
));
654 fprintf (dump_file
, "\nNo available slot\n\n");
660 Breaking intra-loop register anti-dependences:
661 Each intra-loop register anti-dependence implies a cross-iteration true
662 dependence of distance 1. Therefore, we can remove such false dependencies
663 and figure out if the partial schedule broke them by checking if (for a
664 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
665 if so generate a register move. The number of such moves is equal to:
666 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
667 nreg_moves = ----------------------------------- + 1 - { dependence.
671 schedule_reg_moves (partial_schedule_ptr ps
)
677 for (i
= 0; i
< g
->num_nodes
; i
++)
679 ddg_node_ptr u
= &g
->nodes
[i
];
681 int nreg_moves
= 0, i_reg_move
;
682 rtx prev_reg
, old_reg
;
685 sbitmap distance1_uses
;
686 rtx set
= single_set (u
->insn
);
688 /* Skip instructions that do not set a register. */
689 if (set
&& !REG_P (SET_DEST (set
)))
692 /* Compute the number of reg_moves needed for u, by looking at life
693 ranges started at u (excluding self-loops). */
694 distances
[0] = distances
[1] = false;
695 for (e
= u
->out
; e
; e
= e
->next_out
)
696 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
698 int nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
699 - SCHED_TIME (e
->src
->cuid
)) / ii
;
701 if (e
->distance
== 1)
702 nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
703 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
705 /* If dest precedes src in the schedule of the kernel, then dest
706 will read before src writes and we can save one reg_copy. */
707 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
708 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
711 if (nreg_moves4e
>= 1)
713 /* !single_set instructions are not supported yet and
714 thus we do not except to encounter them in the loop
715 except from the doloop part. For the latter case
716 we assume no regmoves are generated as the doloop
717 instructions are tied to the branch with an edge. */
719 /* If the instruction contains auto-inc register then
720 validate that the regmov is being generated for the
721 target regsiter rather then the inc'ed register. */
722 gcc_assert (!autoinc_var_is_used_p (u
->insn
, e
->dest
->insn
));
727 gcc_assert (e
->distance
< 2);
728 distances
[e
->distance
] = true;
730 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
736 /* Create NREG_MOVES register moves. */
737 first_move
= ps
->reg_moves
.length ();
738 ps
->reg_moves
.safe_grow_cleared (first_move
+ nreg_moves
);
739 extend_node_sched_params (ps
);
741 /* Record the moves associated with this node. */
742 first_move
+= ps
->g
->num_nodes
;
744 /* Generate each move. */
745 old_reg
= prev_reg
= SET_DEST (set
);
746 if (HARD_REGISTER_P (old_reg
))
749 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
751 ps_reg_move_info
*move
= ps_reg_move (ps
, first_move
+ i_reg_move
);
753 move
->def
= i_reg_move
> 0 ? first_move
+ i_reg_move
- 1 : i
;
754 move
->uses
= sbitmap_alloc (first_move
+ nreg_moves
);
755 move
->old_reg
= old_reg
;
756 move
->new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
757 move
->num_consecutive_stages
= distances
[0] && distances
[1] ? 2 : 1;
758 move
->insn
= gen_move_insn (move
->new_reg
, copy_rtx (prev_reg
));
759 bitmap_clear (move
->uses
);
761 prev_reg
= move
->new_reg
;
764 distance1_uses
= distances
[1] ? sbitmap_alloc (g
->num_nodes
) : NULL
;
767 bitmap_clear (distance1_uses
);
769 /* Every use of the register defined by node may require a different
770 copy of this register, depending on the time the use is scheduled.
771 Record which uses require which move results. */
772 for (e
= u
->out
; e
; e
= e
->next_out
)
773 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
775 int dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
776 - SCHED_TIME (e
->src
->cuid
)) / ii
;
778 if (e
->distance
== 1)
779 dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
780 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
782 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
783 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
788 ps_reg_move_info
*move
;
790 move
= ps_reg_move (ps
, first_move
+ dest_copy
- 1);
791 bitmap_set_bit (move
->uses
, e
->dest
->cuid
);
792 if (e
->distance
== 1)
793 bitmap_set_bit (distance1_uses
, e
->dest
->cuid
);
797 auto_sbitmap
must_follow (first_move
+ nreg_moves
);
798 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
799 if (!schedule_reg_move (ps
, first_move
+ i_reg_move
,
800 distance1_uses
, must_follow
))
803 sbitmap_free (distance1_uses
);
804 if (i_reg_move
< nreg_moves
)
810 /* Emit the moves associated with PS. Apply the substitutions
811 associated with them. */
813 apply_reg_moves (partial_schedule_ptr ps
)
815 ps_reg_move_info
*move
;
818 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
821 sbitmap_iterator sbi
;
823 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, i_use
, sbi
)
825 replace_rtx (ps
->g
->nodes
[i_use
].insn
, move
->old_reg
, move
->new_reg
);
826 df_insn_rescan (ps
->g
->nodes
[i_use
].insn
);
831 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
832 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
833 will move to cycle zero. */
835 reset_sched_times (partial_schedule_ptr ps
, int amount
)
839 ps_insn_ptr crr_insn
;
841 for (row
= 0; row
< ii
; row
++)
842 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
844 int u
= crr_insn
->id
;
845 int normalized_time
= SCHED_TIME (u
) - amount
;
846 int new_min_cycle
= PS_MIN_CYCLE (ps
) - amount
;
850 /* Print the scheduling times after the rotation. */
851 rtx_insn
*insn
= ps_rtl_insn (ps
, u
);
853 fprintf (dump_file
, "crr_insn->node=%d (insn id %d), "
854 "crr_insn->cycle=%d, min_cycle=%d", u
,
855 INSN_UID (insn
), normalized_time
, new_min_cycle
);
857 fprintf (dump_file
, " (branch)");
858 fprintf (dump_file
, "\n");
861 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
862 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
864 crr_insn
->cycle
= normalized_time
;
865 update_node_sched_params (u
, ii
, normalized_time
, new_min_cycle
);
869 /* Permute the insns according to their order in PS, from row 0 to
870 row ii-1, and position them right before LAST. This schedules
871 the insns of the loop kernel. */
873 permute_partial_schedule (partial_schedule_ptr ps
, rtx_insn
*last
)
879 for (row
= 0; row
< ii
; row
++)
880 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
882 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_ij
->id
);
884 if (PREV_INSN (last
) != insn
)
886 if (ps_ij
->id
< ps
->g
->num_nodes
)
887 reorder_insns_nobb (ps_first_note (ps
, ps_ij
->id
), insn
,
890 add_insn_before (insn
, last
, NULL
);
895 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
896 respectively only if cycle C falls on the border of the scheduling
897 window boundaries marked by START and END cycles. STEP is the
898 direction of the window. */
900 set_must_precede_follow (sbitmap
*tmp_follow
, sbitmap must_follow
,
901 sbitmap
*tmp_precede
, sbitmap must_precede
, int c
,
902 int start
, int end
, int step
)
910 *tmp_precede
= must_precede
;
911 else /* step == -1. */
912 *tmp_follow
= must_follow
;
917 *tmp_follow
= must_follow
;
918 else /* step == -1. */
919 *tmp_precede
= must_precede
;
924 /* Return True if the branch can be moved to row ii-1 while
925 normalizing the partial schedule PS to start from cycle zero and thus
926 optimize the SC. Otherwise return False. */
928 optimize_sc (partial_schedule_ptr ps
, ddg_ptr g
)
930 int amount
= PS_MIN_CYCLE (ps
);
931 int start
, end
, step
;
934 int stage_count
, stage_count_curr
;
936 /* Compare the SC after normalization and SC after bringing the branch
937 to row ii-1. If they are equal just bail out. */
938 stage_count
= calculate_stage_count (ps
, amount
);
940 calculate_stage_count (ps
, SCHED_TIME (g
->closing_branch
->cuid
) - (ii
- 1));
942 if (stage_count
== stage_count_curr
)
945 fprintf (dump_file
, "SMS SC already optimized.\n");
952 fprintf (dump_file
, "SMS Trying to optimize branch location\n");
953 fprintf (dump_file
, "SMS partial schedule before trial:\n");
954 print_partial_schedule (ps
, dump_file
);
957 /* First, normalize the partial scheduling. */
958 reset_sched_times (ps
, amount
);
959 rotate_partial_schedule (ps
, amount
);
963 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
965 print_partial_schedule (ps
, dump_file
);
968 if (SMODULO (SCHED_TIME (g
->closing_branch
->cuid
), ii
) == ii
- 1)
971 auto_sbitmap
sched_nodes (g
->num_nodes
);
972 bitmap_ones (sched_nodes
);
974 /* Calculate the new placement of the branch. It should be in row
975 ii-1 and fall into it's scheduling window. */
976 if (get_sched_window (ps
, g
->closing_branch
, sched_nodes
, ii
, &start
,
980 ps_insn_ptr next_ps_i
;
981 int branch_cycle
= SCHED_TIME (g
->closing_branch
->cuid
);
982 int row
= SMODULO (branch_cycle
, ps
->ii
);
984 sbitmap tmp_precede
, tmp_follow
;
988 fprintf (dump_file
, "\nTrying to schedule node %d "
989 "INSN = %d in (%d .. %d) step %d\n",
990 g
->closing_branch
->cuid
,
991 (INSN_UID (g
->closing_branch
->insn
)), start
, end
, step
);
993 gcc_assert ((step
> 0 && start
< end
) || (step
< 0 && start
> end
));
996 c
= start
+ ii
- SMODULO (start
, ii
) - 1;
997 gcc_assert (c
>= start
);
1002 "SMS failed to schedule branch at cycle: %d\n", c
);
1008 c
= start
- SMODULO (start
, ii
) - 1;
1009 gcc_assert (c
<= start
);
1015 "SMS failed to schedule branch at cycle: %d\n", c
);
1020 auto_sbitmap
must_precede (g
->num_nodes
);
1021 auto_sbitmap
must_follow (g
->num_nodes
);
1023 /* Try to schedule the branch is it's new cycle. */
1024 calculate_must_precede_follow (g
->closing_branch
, start
, end
,
1025 step
, ii
, sched_nodes
,
1026 must_precede
, must_follow
);
1028 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1029 must_precede
, c
, start
, end
, step
);
1031 /* Find the element in the partial schedule related to the closing
1032 branch so we can remove it from it's current cycle. */
1033 for (next_ps_i
= ps
->rows
[row
];
1034 next_ps_i
; next_ps_i
= next_ps_i
->next_in_row
)
1035 if (next_ps_i
->id
== g
->closing_branch
->cuid
)
1038 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1039 remove_node_from_ps (ps
, next_ps_i
);
1041 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
, c
,
1042 sched_nodes
, &num_splits
,
1043 tmp_precede
, tmp_follow
);
1044 gcc_assert (num_splits
== 0);
1049 "SMS failed to schedule branch at cycle: %d, "
1050 "bringing it back to cycle %d\n", c
, branch_cycle
);
1052 /* The branch was failed to be placed in row ii - 1.
1053 Put it back in it's original place in the partial
1055 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1056 must_precede
, branch_cycle
, start
, end
,
1059 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
,
1060 branch_cycle
, sched_nodes
,
1061 &num_splits
, tmp_precede
,
1063 gcc_assert (success
&& (num_splits
== 0));
1068 /* The branch is placed in row ii - 1. */
1071 "SMS success in moving branch to cycle %d\n", c
);
1073 update_node_sched_params (g
->closing_branch
->cuid
, ii
, c
,
1078 /* This might have been added to a new first stage. */
1079 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1080 reset_sched_times (ps
, 0);
1087 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
1088 int to_stage
, rtx count_reg
)
1093 for (row
= 0; row
< ps
->ii
; row
++)
1094 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
1097 int first_u
, last_u
;
1100 /* Do not duplicate any insn which refers to count_reg as it
1101 belongs to the control part.
1102 The closing branch is scheduled as well and thus should
1104 TODO: This should be done by analyzing the control part of
1106 u_insn
= ps_rtl_insn (ps
, u
);
1107 if (reg_mentioned_p (count_reg
, u_insn
)
1111 first_u
= SCHED_STAGE (u
);
1112 last_u
= first_u
+ ps_num_consecutive_stages (ps
, u
) - 1;
1113 if (from_stage
<= last_u
&& to_stage
>= first_u
)
1115 if (u
< ps
->g
->num_nodes
)
1116 duplicate_insn_chain (ps_first_note (ps
, u
), u_insn
);
1118 emit_insn (copy_rtx (PATTERN (u_insn
)));
1124 /* Generate the instructions (including reg_moves) for prolog & epilog. */
1126 generate_prolog_epilog (partial_schedule_ptr ps
, class loop
*loop
,
1127 rtx count_reg
, rtx count_init
)
1130 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
1133 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1138 /* Generate instructions at the beginning of the prolog to
1139 adjust the loop count by STAGE_COUNT. If loop count is constant
1140 (count_init), this constant is adjusted by STAGE_COUNT in
1141 generate_prolog_epilog function. */
1142 rtx sub_reg
= NULL_RTX
;
1144 sub_reg
= expand_simple_binop (GET_MODE (count_reg
), MINUS
, count_reg
,
1145 gen_int_mode (last_stage
,
1146 GET_MODE (count_reg
)),
1147 count_reg
, 1, OPTAB_DIRECT
);
1148 gcc_assert (REG_P (sub_reg
));
1149 if (REGNO (sub_reg
) != REGNO (count_reg
))
1150 emit_move_insn (count_reg
, sub_reg
);
1153 for (i
= 0; i
< last_stage
; i
++)
1154 duplicate_insns_of_cycles (ps
, 0, i
, count_reg
);
1156 /* Put the prolog on the entry edge. */
1157 e
= loop_preheader_edge (loop
);
1158 split_edge_and_insert (e
, get_insns ());
1159 if (!flag_resched_modulo_sched
)
1160 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1164 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1167 for (i
= 0; i
< last_stage
; i
++)
1168 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, count_reg
);
1170 /* Put the epilogue on the exit edge. */
1171 gcc_assert (single_exit (loop
));
1172 e
= single_exit (loop
);
1173 split_edge_and_insert (e
, get_insns ());
1174 if (!flag_resched_modulo_sched
)
1175 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1180 /* Mark LOOP as software pipelined so the later
1181 scheduling passes don't touch it. */
1183 mark_loop_unsched (class loop
*loop
)
1186 basic_block
*bbs
= get_loop_body (loop
);
1188 for (i
= 0; i
< loop
->num_nodes
; i
++)
1189 bbs
[i
]->flags
|= BB_DISABLE_SCHEDULE
;
1194 /* Return true if all the BBs of the loop are empty except the
1197 loop_single_full_bb_p (class loop
*loop
)
1200 basic_block
*bbs
= get_loop_body (loop
);
1202 for (i
= 0; i
< loop
->num_nodes
; i
++)
1204 rtx_insn
*head
, *tail
;
1205 bool empty_bb
= true;
1207 if (bbs
[i
] == loop
->header
)
1210 /* Make sure that basic blocks other than the header
1211 have only notes labels or jumps. */
1212 get_ebb_head_tail (bbs
[i
], bbs
[i
], &head
, &tail
);
1213 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
1215 if (NOTE_P (head
) || LABEL_P (head
)
1216 || (INSN_P (head
) && (DEBUG_INSN_P (head
) || JUMP_P (head
))))
1232 /* Dump file:line from INSN's location info to dump_file. */
1235 dump_insn_location (rtx_insn
*insn
)
1237 if (dump_file
&& INSN_HAS_LOCATION (insn
))
1239 expanded_location xloc
= insn_location (insn
);
1240 fprintf (dump_file
, " %s:%i", xloc
.file
, xloc
.line
);
1244 /* A simple loop from SMS point of view; it is a loop that is composed of
1245 either a single basic block or two BBs - a header and a latch. */
1246 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1247 && (EDGE_COUNT (loop->latch->preds) == 1) \
1248 && (EDGE_COUNT (loop->latch->succs) == 1))
1250 /* Return true if the loop is in its canonical form and false if not.
1251 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1253 loop_canon_p (class loop
*loop
)
1256 if (loop
->inner
|| !loop_outer (loop
))
1259 fprintf (dump_file
, "SMS loop inner or !loop_outer\n");
1263 if (!single_exit (loop
))
1267 rtx_insn
*insn
= BB_END (loop
->header
);
1269 fprintf (dump_file
, "SMS loop many exits");
1270 dump_insn_location (insn
);
1271 fprintf (dump_file
, "\n");
1276 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
1280 rtx_insn
*insn
= BB_END (loop
->header
);
1282 fprintf (dump_file
, "SMS loop many BBs.");
1283 dump_insn_location (insn
);
1284 fprintf (dump_file
, "\n");
1292 /* If there are more than one entry for the loop,
1293 make it one by splitting the first entry edge and
1294 redirecting the others to the new BB. */
1296 canon_loop (class loop
*loop
)
1301 /* Avoid annoying special cases of edges going to exit
1303 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1304 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
1307 if (loop
->latch
== loop
->header
1308 || EDGE_COUNT (loop
->latch
->succs
) > 1)
1310 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
1311 if (e
->src
== loop
->latch
)
1319 setup_sched_infos (void)
1321 memcpy (&sms_common_sched_info
, &haifa_common_sched_info
,
1322 sizeof (sms_common_sched_info
));
1323 sms_common_sched_info
.sched_pass_id
= SCHED_SMS_PASS
;
1324 common_sched_info
= &sms_common_sched_info
;
1326 sched_deps_info
= &sms_sched_deps_info
;
1327 current_sched_info
= &sms_sched_info
;
1330 /* Probability in % that the sms-ed loop rolls enough so that optimized
1331 version may be entered. Just a guess. */
1332 #define PROB_SMS_ENOUGH_ITERATIONS 80
1334 /* Used to calculate the upper bound of ii. */
1335 #define MAXII_FACTOR 2
1337 /* Main entry point, perform SMS scheduling on the loops of the function
1338 that consist of single basic blocks. */
1345 int maxii
, max_asap
;
1346 partial_schedule_ptr ps
;
1347 basic_block bb
= NULL
;
1349 basic_block condition_bb
= NULL
;
1351 HOST_WIDE_INT trip_count
, max_trip_count
;
1353 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1354 | LOOPS_HAVE_RECORDED_EXITS
);
1355 if (number_of_loops (cfun
) <= 1)
1357 loop_optimizer_finalize ();
1358 return; /* There are no loops to schedule. */
1361 /* Initialize issue_rate. */
1362 if (targetm
.sched
.issue_rate
)
1364 int temp
= reload_completed
;
1366 reload_completed
= 1;
1367 issue_rate
= targetm
.sched
.issue_rate ();
1368 reload_completed
= temp
;
1373 /* Initialize the scheduler. */
1374 setup_sched_infos ();
1375 haifa_sched_init ();
1377 /* Allocate memory to hold the DDG array one entry for each loop.
1378 We use loop->num as index into this array. */
1379 g_arr
= XCNEWVEC (ddg_ptr
, number_of_loops (cfun
));
1383 fprintf (dump_file
, "\n\nSMS analysis phase\n");
1384 fprintf (dump_file
, "===================\n\n");
1387 /* Build DDGs for all the relevant loops and hold them in G_ARR
1388 indexed by the loop index. */
1389 FOR_EACH_LOOP (loop
, 0)
1391 rtx_insn
*head
, *tail
;
1394 /* For debugging. */
1395 if (dbg_cnt (sms_sched_loop
) == false)
1398 fprintf (dump_file
, "SMS reached max limit... \n");
1405 rtx_insn
*insn
= BB_END (loop
->header
);
1407 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1408 dump_insn_location (insn
);
1409 fprintf (dump_file
, "\n");
1412 if (! loop_canon_p (loop
))
1415 if (! loop_single_full_bb_p (loop
))
1418 fprintf (dump_file
, "SMS not loop_single_full_bb_p\n");
1424 get_ebb_head_tail (bb
, bb
, &head
, &tail
);
1425 latch_edge
= loop_latch_edge (loop
);
1426 gcc_assert (single_exit (loop
));
1427 trip_count
= get_estimated_loop_iterations_int (loop
);
1428 max_trip_count
= get_max_loop_iterations_int (loop
);
1430 /* Perform SMS only on loops that their average count is above threshold. */
1432 if ( latch_edge
->count () > profile_count::zero ()
1433 && (latch_edge
->count()
1434 < single_exit (loop
)->count ().apply_scale
1435 (param_sms_loop_average_count_threshold
, 1)))
1439 dump_insn_location (tail
);
1440 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1441 if (profile_info
&& flag_branch_probabilities
)
1443 fprintf (dump_file
, "SMS loop-count ");
1444 fprintf (dump_file
, "%" PRId64
,
1445 (int64_t) bb
->count
.to_gcov_type ());
1446 fprintf (dump_file
, "\n");
1447 fprintf (dump_file
, "SMS trip-count ");
1448 fprintf (dump_file
, "%" PRId64
"max %" PRId64
,
1449 (int64_t) trip_count
, (int64_t) max_trip_count
);
1450 fprintf (dump_file
, "\n");
1456 /* Make sure this is a doloop. */
1457 if ( !(count_reg
= doloop_register_get (head
, tail
)))
1460 fprintf (dump_file
, "SMS doloop_register_get failed\n");
1464 /* Don't handle BBs with calls or barriers
1465 or !single_set with the exception of instructions that include
1466 count_reg---these instructions are part of the control part
1467 that do-loop recognizes.
1468 ??? Should handle insns defining subregs. */
1469 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1475 || (NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1476 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
1477 && !reg_mentioned_p (count_reg
, insn
))
1478 || (INSN_P (insn
) && (set
= single_set (insn
))
1479 && GET_CODE (SET_DEST (set
)) == SUBREG
))
1483 if (insn
!= NEXT_INSN (tail
))
1488 fprintf (dump_file
, "SMS loop-with-call\n");
1489 else if (BARRIER_P (insn
))
1490 fprintf (dump_file
, "SMS loop-with-barrier\n");
1491 else if ((NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1492 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
1493 fprintf (dump_file
, "SMS loop-with-not-single-set\n");
1495 fprintf (dump_file
, "SMS loop with subreg in lhs\n");
1496 print_rtl_single (dump_file
, insn
);
1502 /* Always schedule the closing branch with the rest of the
1503 instructions. The branch is rotated to be in row ii-1 at the
1504 end of the scheduling procedure to make sure it's the last
1505 instruction in the iteration. */
1506 if (! (g
= create_ddg (bb
, 1)))
1509 fprintf (dump_file
, "SMS create_ddg failed\n");
1513 g_arr
[loop
->num
] = g
;
1515 fprintf (dump_file
, "...OK\n");
1520 fprintf (dump_file
, "\nSMS transformation phase\n");
1521 fprintf (dump_file
, "=========================\n\n");
1524 /* We don't want to perform SMS on new loops - created by versioning. */
1525 FOR_EACH_LOOP (loop
, 0)
1527 rtx_insn
*head
, *tail
;
1529 rtx_insn
*count_init
;
1530 int mii
, rec_mii
, stage_count
, min_cycle
;
1531 int64_t loop_count
= 0;
1534 if (! (g
= g_arr
[loop
->num
]))
1539 rtx_insn
*insn
= BB_END (loop
->header
);
1541 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1542 dump_insn_location (insn
);
1543 fprintf (dump_file
, "\n");
1545 print_ddg (dump_file
, g
);
1548 get_ebb_head_tail (loop
->header
, loop
->header
, &head
, &tail
);
1550 latch_edge
= loop_latch_edge (loop
);
1551 gcc_assert (single_exit (loop
));
1552 trip_count
= get_estimated_loop_iterations_int (loop
);
1553 max_trip_count
= get_max_loop_iterations_int (loop
);
1557 dump_insn_location (tail
);
1558 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1559 if (profile_info
&& flag_branch_probabilities
)
1561 fprintf (dump_file
, "SMS loop-count ");
1562 fprintf (dump_file
, "%" PRId64
,
1563 (int64_t) bb
->count
.to_gcov_type ());
1564 fprintf (dump_file
, "\n");
1566 fprintf (dump_file
, "SMS doloop\n");
1567 fprintf (dump_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1568 fprintf (dump_file
, "SMS num-loads %d\n", g
->num_loads
);
1569 fprintf (dump_file
, "SMS num-stores %d\n", g
->num_stores
);
1573 /* In case of th loop have doloop register it gets special
1576 if ((count_reg
= doloop_register_get (head
, tail
)))
1578 basic_block pre_header
;
1580 pre_header
= loop_preheader_edge (loop
)->src
;
1581 count_init
= const_iteration_count (count_reg
, pre_header
,
1584 gcc_assert (count_reg
);
1586 if (dump_file
&& count_init
)
1588 fprintf (dump_file
, "SMS const-doloop ");
1589 fprintf (dump_file
, "%" PRId64
,
1591 fprintf (dump_file
, "\n");
1594 node_order
= XNEWVEC (int, g
->num_nodes
);
1596 mii
= 1; /* Need to pass some estimate of mii. */
1597 rec_mii
= sms_order_nodes (g
, mii
, node_order
, &max_asap
);
1598 mii
= MAX (res_MII (g
), rec_mii
);
1600 maxii
= MAX (max_asap
, MAXII_FACTOR
* mii
);
1603 fprintf (dump_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1604 rec_mii
, mii
, maxii
);
1608 set_node_sched_params (g
);
1612 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
);
1616 /* Try to achieve optimized SC by normalizing the partial
1617 schedule (having the cycles start from cycle zero).
1618 The branch location must be placed in row ii-1 in the
1619 final scheduling. If failed, shift all instructions to
1620 position the branch in row ii-1. */
1621 opt_sc_p
= optimize_sc (ps
, g
);
1623 stage_count
= calculate_stage_count (ps
, 0);
1626 /* Bring the branch to cycle ii-1. */
1627 int amount
= (SCHED_TIME (g
->closing_branch
->cuid
)
1631 fprintf (dump_file
, "SMS schedule branch at cycle ii-1\n");
1633 stage_count
= calculate_stage_count (ps
, amount
);
1636 gcc_assert (stage_count
>= 1);
1639 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
1640 1 means that there is no interleaving between iterations thus
1641 we let the scheduling passes do the job in this case. */
1642 if (stage_count
< param_sms_min_sc
1643 || (count_init
&& (loop_count
<= stage_count
))
1644 || (max_trip_count
>= 0 && max_trip_count
<= stage_count
)
1645 || (trip_count
>= 0 && trip_count
<= stage_count
))
1649 fprintf (dump_file
, "SMS failed... \n");
1650 fprintf (dump_file
, "SMS sched-failed (stage-count=%d,"
1651 " loop-count=", stage_count
);
1652 fprintf (dump_file
, "%" PRId64
, loop_count
);
1653 fprintf (dump_file
, ", trip-count=");
1654 fprintf (dump_file
, "%" PRId64
"max %" PRId64
,
1655 (int64_t) trip_count
, (int64_t) max_trip_count
);
1656 fprintf (dump_file
, ")\n");
1663 /* Rotate the partial schedule to have the branch in row ii-1. */
1664 int amount
= SCHED_TIME (g
->closing_branch
->cuid
) - (ps
->ii
- 1);
1666 reset_sched_times (ps
, amount
);
1667 rotate_partial_schedule (ps
, amount
);
1670 set_columns_for_ps (ps
);
1672 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1673 if (!schedule_reg_moves (ps
))
1676 free_partial_schedule (ps
);
1680 /* Moves that handle incoming values might have been added
1681 to a new first stage. Bump the stage count if so.
1683 ??? Perhaps we could consider rotating the schedule here
1685 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1687 reset_sched_times (ps
, 0);
1691 /* The stage count should now be correct without rotation. */
1692 gcc_checking_assert (stage_count
== calculate_stage_count (ps
, 0));
1693 PS_STAGE_COUNT (ps
) = stage_count
;
1699 dump_insn_location (tail
);
1700 fprintf (dump_file
, " SMS succeeded %d %d (with ii, sc)\n",
1701 ps
->ii
, stage_count
);
1702 print_partial_schedule (ps
, dump_file
);
1705 /* case the BCT count is not known , Do loop-versioning */
1706 if (count_reg
&& ! count_init
)
1708 rtx comp_rtx
= gen_rtx_GT (VOIDmode
, count_reg
,
1709 gen_int_mode (stage_count
,
1710 GET_MODE (count_reg
)));
1711 profile_probability prob
= profile_probability::guessed_always ()
1712 .apply_scale (PROB_SMS_ENOUGH_ITERATIONS
, 100);
1714 loop_version (loop
, comp_rtx
, &condition_bb
,
1715 prob
, prob
.invert (),
1716 prob
, prob
.invert (), true);
1719 /* Set new iteration count of loop kernel. */
1720 if (count_reg
&& count_init
)
1721 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1724 /* Now apply the scheduled kernel to the RTL of the loop. */
1725 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1727 /* Mark this loop as software pipelined so the later
1728 scheduling passes don't touch it. */
1729 if (! flag_resched_modulo_sched
)
1730 mark_loop_unsched (loop
);
1732 /* The life-info is not valid any more. */
1733 df_set_bb_dirty (g
->bb
);
1735 apply_reg_moves (ps
);
1737 print_node_sched_params (dump_file
, g
->num_nodes
, ps
);
1738 /* Generate prolog and epilog. */
1739 generate_prolog_epilog (ps
, loop
, count_reg
, count_init
);
1743 free_partial_schedule (ps
);
1744 node_sched_param_vec
.release ();
1751 /* Release scheduler data, needed until now because of DFA. */
1752 haifa_sched_finish ();
1753 loop_optimizer_finalize ();
1756 /* The SMS scheduling algorithm itself
1757 -----------------------------------
1758 Input: 'O' an ordered list of insns of a loop.
1759 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1761 'Q' is the empty Set
1762 'PS' is the partial schedule; it holds the currently scheduled nodes with
1764 'PSP' previously scheduled predecessors.
1765 'PSS' previously scheduled successors.
1766 't(u)' the cycle where u is scheduled.
1767 'l(u)' is the latency of u.
1768 'd(v,u)' is the dependence distance from v to u.
1769 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1770 the node ordering phase.
1771 'check_hardware_resources_conflicts(u, PS, c)'
1772 run a trace around cycle/slot through DFA model
1773 to check resource conflicts involving instruction u
1774 at cycle c given the partial schedule PS.
1775 'add_to_partial_schedule_at_time(u, PS, c)'
1776 Add the node/instruction u to the partial schedule
1778 'calculate_register_pressure(PS)'
1779 Given a schedule of instructions, calculate the register
1780 pressure it implies. One implementation could be the
1781 maximum number of overlapping live ranges.
1782 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1783 registers available in the hardware.
1787 3. for each node u in O in pre-computed order
1788 4. if (PSP(u) != Q && PSS(u) == Q) then
1789 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1790 6. start = Early_start; end = Early_start + II - 1; step = 1
1791 11. else if (PSP(u) == Q && PSS(u) != Q) then
1792 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1793 13. start = Late_start; end = Late_start - II + 1; step = -1
1794 14. else if (PSP(u) != Q && PSS(u) != Q) then
1795 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1796 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1797 17. start = Early_start;
1798 18. end = min(Early_start + II - 1 , Late_start);
1800 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1801 21. start = ASAP(u); end = start + II - 1; step = 1
1805 24. for (c = start ; c != end ; c += step)
1806 25. if check_hardware_resources_conflicts(u, PS, c) then
1807 26. add_to_partial_schedule_at_time(u, PS, c)
1812 31. if (success == false) then
1814 33. if (II > maxII) then
1815 34. finish - failed to schedule
1820 39. if (calculate_register_pressure(PS) > maxRP) then
1823 42. compute epilogue & prologue
1824 43. finish - succeeded to schedule
1826 ??? The algorithm restricts the scheduling window to II cycles.
1827 In rare cases, it may be better to allow windows of II+1 cycles.
1828 The window would then start and end on the same row, but with
1829 different "must precede" and "must follow" requirements. */
1831 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1832 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1833 set to 0 to save compile time. */
1834 #define DFA_HISTORY param_sms_dfa_history
1836 /* A threshold for the number of repeated unsuccessful attempts to insert
1837 an empty row, before we flush the partial schedule and start over. */
1838 #define MAX_SPLIT_NUM 10
1839 /* Given the partial schedule PS, this function calculates and returns the
1840 cycles in which we can schedule the node with the given index I.
1841 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1842 noticed that there are several cases in which we fail to SMS the loop
1843 because the sched window of a node is empty due to tight data-deps. In
1844 such cases we want to unschedule some of the predecessors/successors
1845 until we get non-empty scheduling window. It returns -1 if the
1846 scheduling window is empty and zero otherwise. */
1849 get_sched_window (partial_schedule_ptr ps
, ddg_node_ptr u_node
,
1850 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
,
1853 int start
, step
, end
;
1854 int early_start
, late_start
;
1856 auto_sbitmap
psp (ps
->g
->num_nodes
);
1857 auto_sbitmap
pss (ps
->g
->num_nodes
);
1858 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1859 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1865 /* 1. compute sched window for u (start, end, step). */
1868 psp_not_empty
= bitmap_and (psp
, u_node_preds
, sched_nodes
);
1869 pss_not_empty
= bitmap_and (pss
, u_node_succs
, sched_nodes
);
1871 /* We first compute a forward range (start <= end), then decide whether
1873 early_start
= INT_MIN
;
1874 late_start
= INT_MAX
;
1882 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1884 fprintf (dump_file
, "\nAnalyzing dependencies for node %d (INSN %d)"
1885 "; ii = %d\n\n", u_node
->cuid
, INSN_UID (u_node
->insn
), ii
);
1886 fprintf (dump_file
, "%11s %11s %11s %11s %5s\n",
1887 "start", "early start", "late start", "end", "time");
1888 fprintf (dump_file
, "=========== =========== =========== ==========="
1891 /* Calculate early_start and limit end. Both bounds are inclusive. */
1893 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1895 int v
= e
->src
->cuid
;
1897 if (bitmap_bit_p (sched_nodes
, v
))
1899 int p_st
= SCHED_TIME (v
);
1900 int earliest
= p_st
+ e
->latency
- (e
->distance
* ii
);
1901 int latest
= (e
->data_type
== MEM_DEP
? p_st
+ ii
- 1 : INT_MAX
);
1905 fprintf (dump_file
, "%11s %11d %11s %11d %5d",
1906 "", earliest
, "", latest
, p_st
);
1907 print_ddg_edge (dump_file
, e
);
1908 fprintf (dump_file
, "\n");
1911 early_start
= MAX (early_start
, earliest
);
1912 end
= MIN (end
, latest
);
1914 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1919 /* Calculate late_start and limit start. Both bounds are inclusive. */
1921 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1923 int v
= e
->dest
->cuid
;
1925 if (bitmap_bit_p (sched_nodes
, v
))
1927 int s_st
= SCHED_TIME (v
);
1928 int earliest
= (e
->data_type
== MEM_DEP
? s_st
- ii
+ 1 : INT_MIN
);
1929 int latest
= s_st
- e
->latency
+ (e
->distance
* ii
);
1933 fprintf (dump_file
, "%11d %11s %11d %11s %5d",
1934 earliest
, "", latest
, "", s_st
);
1935 print_ddg_edge (dump_file
, e
);
1936 fprintf (dump_file
, "\n");
1939 start
= MAX (start
, earliest
);
1940 late_start
= MIN (late_start
, latest
);
1942 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1947 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1949 fprintf (dump_file
, "----------- ----------- ----------- -----------"
1951 fprintf (dump_file
, "%11d %11d %11d %11d %5s %s\n",
1952 start
, early_start
, late_start
, end
, "",
1953 "(max, max, min, min)");
1956 /* Get a target scheduling window no bigger than ii. */
1957 if (early_start
== INT_MIN
&& late_start
== INT_MAX
)
1958 early_start
= NODE_ASAP (u_node
);
1959 else if (early_start
== INT_MIN
)
1960 early_start
= late_start
- (ii
- 1);
1961 late_start
= MIN (late_start
, early_start
+ (ii
- 1));
1963 /* Apply memory dependence limits. */
1964 start
= MAX (start
, early_start
);
1965 end
= MIN (end
, late_start
);
1967 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1968 fprintf (dump_file
, "%11s %11d %11d %11s %5s final window\n",
1969 "", start
, end
, "", "");
1971 /* If there are at least as many successors as predecessors, schedule the
1972 node close to its successors. */
1973 if (pss_not_empty
&& count_succs
>= count_preds
)
1975 std::swap (start
, end
);
1979 /* Now that we've finalized the window, make END an exclusive rather
1980 than an inclusive bound. */
1987 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
1990 fprintf (dump_file
, "\nEmpty window: start=%d, end=%d, step=%d\n",
1998 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
1999 node currently been scheduled. At the end of the calculation
2000 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
2001 U_NODE which are (1) already scheduled in the first/last row of
2002 U_NODE's scheduling window, (2) whose dependence inequality with U
2003 becomes an equality when U is scheduled in this same row, and (3)
2004 whose dependence latency is zero.
2006 The first and last rows are calculated using the following parameters:
2007 START/END rows - The cycles that begins/ends the traversal on the window;
2008 searching for an empty cycle to schedule U_NODE.
2009 STEP - The direction in which we traverse the window.
2010 II - The initiation interval. */
2013 calculate_must_precede_follow (ddg_node_ptr u_node
, int start
, int end
,
2014 int step
, int ii
, sbitmap sched_nodes
,
2015 sbitmap must_precede
, sbitmap must_follow
)
2018 int first_cycle_in_window
, last_cycle_in_window
;
2020 gcc_assert (must_precede
&& must_follow
);
2022 /* Consider the following scheduling window:
2023 {first_cycle_in_window, first_cycle_in_window+1, ...,
2024 last_cycle_in_window}. If step is 1 then the following will be
2025 the order we traverse the window: {start=first_cycle_in_window,
2026 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
2027 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
2028 end=first_cycle_in_window-1} if step is -1. */
2029 first_cycle_in_window
= (step
== 1) ? start
: end
- step
;
2030 last_cycle_in_window
= (step
== 1) ? end
- step
: start
;
2032 bitmap_clear (must_precede
);
2033 bitmap_clear (must_follow
);
2036 fprintf (dump_file
, "\nmust_precede: ");
2038 /* Instead of checking if:
2039 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
2040 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
2041 first_cycle_in_window)
2043 we use the fact that latency is non-negative:
2044 SCHED_TIME (e->src) - (e->distance * ii) <=
2045 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
2046 first_cycle_in_window
2048 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
2049 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2050 if (bitmap_bit_p (sched_nodes
, e
->src
->cuid
)
2051 && ((SCHED_TIME (e
->src
->cuid
) - (e
->distance
* ii
)) ==
2052 first_cycle_in_window
))
2055 fprintf (dump_file
, "%d ", e
->src
->cuid
);
2057 bitmap_set_bit (must_precede
, e
->src
->cuid
);
2061 fprintf (dump_file
, "\nmust_follow: ");
2063 /* Instead of checking if:
2064 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
2065 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
2066 last_cycle_in_window)
2068 we use the fact that latency is non-negative:
2069 SCHED_TIME (e->dest) + (e->distance * ii) >=
2070 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
2071 last_cycle_in_window
2073 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
2074 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2075 if (bitmap_bit_p (sched_nodes
, e
->dest
->cuid
)
2076 && ((SCHED_TIME (e
->dest
->cuid
) + (e
->distance
* ii
)) ==
2077 last_cycle_in_window
))
2080 fprintf (dump_file
, "%d ", e
->dest
->cuid
);
2082 bitmap_set_bit (must_follow
, e
->dest
->cuid
);
2086 fprintf (dump_file
, "\n");
2089 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
2090 parameters to decide if that's possible:
2091 PS - The partial schedule.
2092 U - The serial number of U_NODE.
2093 NUM_SPLITS - The number of row splits made so far.
2094 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
2095 the first row of the scheduling window)
2096 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
2097 last row of the scheduling window) */
2100 try_scheduling_node_in_cycle (partial_schedule_ptr ps
,
2101 int u
, int cycle
, sbitmap sched_nodes
,
2102 int *num_splits
, sbitmap must_precede
,
2103 sbitmap must_follow
)
2108 verify_partial_schedule (ps
, sched_nodes
);
2109 psi
= ps_add_node_check_conflicts (ps
, u
, cycle
, must_precede
, must_follow
);
2112 SCHED_TIME (u
) = cycle
;
2113 bitmap_set_bit (sched_nodes
, u
);
2117 fprintf (dump_file
, "Scheduled w/o split in %d\n", cycle
);
2124 /* This function implements the scheduling algorithm for SMS according to the
2126 static partial_schedule_ptr
2127 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
)
2130 int i
, c
, success
, num_splits
= 0;
2131 int flush_and_start_over
= true;
2132 int num_nodes
= g
->num_nodes
;
2133 int start
, end
, step
; /* Place together into one struct? */
2134 auto_sbitmap
sched_nodes (num_nodes
);
2135 auto_sbitmap
must_precede (num_nodes
);
2136 auto_sbitmap
must_follow (num_nodes
);
2137 auto_sbitmap
tobe_scheduled (num_nodes
);
2139 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
, DFA_HISTORY
);
2141 bitmap_ones (tobe_scheduled
);
2142 bitmap_clear (sched_nodes
);
2144 while (flush_and_start_over
&& (ii
< maxii
))
2148 fprintf (dump_file
, "Starting with ii=%d\n", ii
);
2149 flush_and_start_over
= false;
2150 bitmap_clear (sched_nodes
);
2152 for (i
= 0; i
< num_nodes
; i
++)
2154 int u
= nodes_order
[i
];
2155 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
2156 rtx_insn
*insn
= u_node
->insn
;
2158 if (!NONDEBUG_INSN_P (insn
))
2160 bitmap_clear_bit (tobe_scheduled
, u
);
2164 if (bitmap_bit_p (sched_nodes
, u
))
2167 /* Try to get non-empty scheduling window. */
2169 if (get_sched_window (ps
, u_node
, sched_nodes
, ii
, &start
,
2173 fprintf (dump_file
, "\nTrying to schedule node %d "
2174 "INSN = %d in (%d .. %d) step %d\n", u
, (INSN_UID
2175 (g
->nodes
[u
].insn
)), start
, end
, step
);
2177 gcc_assert ((step
> 0 && start
< end
)
2178 || (step
< 0 && start
> end
));
2180 calculate_must_precede_follow (u_node
, start
, end
, step
, ii
,
2181 sched_nodes
, must_precede
,
2184 for (c
= start
; c
!= end
; c
+= step
)
2186 sbitmap tmp_precede
, tmp_follow
;
2188 set_must_precede_follow (&tmp_follow
, must_follow
,
2189 &tmp_precede
, must_precede
,
2190 c
, start
, end
, step
);
2192 try_scheduling_node_in_cycle (ps
, u
, c
,
2194 &num_splits
, tmp_precede
,
2200 verify_partial_schedule (ps
, sched_nodes
);
2209 if (num_splits
>= MAX_SPLIT_NUM
)
2212 flush_and_start_over
= true;
2213 verify_partial_schedule (ps
, sched_nodes
);
2214 reset_partial_schedule (ps
, ii
);
2215 verify_partial_schedule (ps
, sched_nodes
);
2220 /* The scheduling window is exclusive of 'end'
2221 whereas compute_split_window() expects an inclusive,
2224 split_row
= compute_split_row (sched_nodes
, start
, end
- 1,
2227 split_row
= compute_split_row (sched_nodes
, end
+ 1, start
,
2230 ps_insert_empty_row (ps
, split_row
, sched_nodes
);
2231 i
--; /* Go back and retry node i. */
2234 fprintf (dump_file
, "num_splits=%d\n", num_splits
);
2237 /* ??? If (success), check register pressure estimates. */
2238 } /* Continue with next node. */
2239 } /* While flush_and_start_over. */
2242 free_partial_schedule (ps
);
2246 gcc_assert (bitmap_equal_p (tobe_scheduled
, sched_nodes
));
2251 /* This function inserts a new empty row into PS at the position
2252 according to SPLITROW, keeping all already scheduled instructions
2253 intact and updating their SCHED_TIME and cycle accordingly. */
2255 ps_insert_empty_row (partial_schedule_ptr ps
, int split_row
,
2256 sbitmap sched_nodes
)
2258 ps_insn_ptr crr_insn
;
2259 ps_insn_ptr
*rows_new
;
2261 int new_ii
= ii
+ 1;
2263 int *rows_length_new
;
2265 verify_partial_schedule (ps
, sched_nodes
);
2267 /* We normalize sched_time and rotate ps to have only non-negative sched
2268 times, for simplicity of updating cycles after inserting new row. */
2269 split_row
-= ps
->min_cycle
;
2270 split_row
= SMODULO (split_row
, ii
);
2272 fprintf (dump_file
, "split_row=%d\n", split_row
);
2274 reset_sched_times (ps
, PS_MIN_CYCLE (ps
));
2275 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
2277 rows_new
= (ps_insn_ptr
*) xcalloc (new_ii
, sizeof (ps_insn_ptr
));
2278 rows_length_new
= (int *) xcalloc (new_ii
, sizeof (int));
2279 for (row
= 0; row
< split_row
; row
++)
2281 rows_new
[row
] = ps
->rows
[row
];
2282 rows_length_new
[row
] = ps
->rows_length
[row
];
2283 ps
->rows
[row
] = NULL
;
2284 for (crr_insn
= rows_new
[row
];
2285 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2287 int u
= crr_insn
->id
;
2288 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
);
2290 SCHED_TIME (u
) = new_time
;
2291 crr_insn
->cycle
= new_time
;
2292 SCHED_ROW (u
) = new_time
% new_ii
;
2293 SCHED_STAGE (u
) = new_time
/ new_ii
;
2298 rows_new
[split_row
] = NULL
;
2300 for (row
= split_row
; row
< ii
; row
++)
2302 rows_new
[row
+ 1] = ps
->rows
[row
];
2303 rows_length_new
[row
+ 1] = ps
->rows_length
[row
];
2304 ps
->rows
[row
] = NULL
;
2305 for (crr_insn
= rows_new
[row
+ 1];
2306 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2308 int u
= crr_insn
->id
;
2309 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
) + 1;
2311 SCHED_TIME (u
) = new_time
;
2312 crr_insn
->cycle
= new_time
;
2313 SCHED_ROW (u
) = new_time
% new_ii
;
2314 SCHED_STAGE (u
) = new_time
/ new_ii
;
2319 ps
->min_cycle
= ps
->min_cycle
+ ps
->min_cycle
/ ii
2320 + (SMODULO (ps
->min_cycle
, ii
) >= split_row
? 1 : 0);
2321 ps
->max_cycle
= ps
->max_cycle
+ ps
->max_cycle
/ ii
2322 + (SMODULO (ps
->max_cycle
, ii
) >= split_row
? 1 : 0);
2324 ps
->rows
= rows_new
;
2325 free (ps
->rows_length
);
2326 ps
->rows_length
= rows_length_new
;
2328 gcc_assert (ps
->min_cycle
>= 0);
2330 verify_partial_schedule (ps
, sched_nodes
);
2333 fprintf (dump_file
, "min_cycle=%d, max_cycle=%d\n", ps
->min_cycle
,
2337 /* Given U_NODE which is the node that failed to be scheduled; LOW and
2338 UP which are the boundaries of it's scheduling window; compute using
2339 SCHED_NODES and II a row in the partial schedule that can be split
2340 which will separate a critical predecessor from a critical successor
2341 thereby expanding the window, and return it. */
2343 compute_split_row (sbitmap sched_nodes
, int low
, int up
, int ii
,
2344 ddg_node_ptr u_node
)
2347 int lower
= INT_MIN
, upper
= INT_MAX
;
2352 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2354 int v
= e
->src
->cuid
;
2356 if (bitmap_bit_p (sched_nodes
, v
)
2357 && (low
== SCHED_TIME (v
) + e
->latency
- (e
->distance
* ii
)))
2358 if (SCHED_TIME (v
) > lower
)
2361 lower
= SCHED_TIME (v
);
2367 crit_cycle
= SCHED_TIME (crit_pred
) + 1;
2368 return SMODULO (crit_cycle
, ii
);
2371 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2373 int v
= e
->dest
->cuid
;
2375 if (bitmap_bit_p (sched_nodes
, v
)
2376 && (up
== SCHED_TIME (v
) - e
->latency
+ (e
->distance
* ii
)))
2377 if (SCHED_TIME (v
) < upper
)
2380 upper
= SCHED_TIME (v
);
2386 crit_cycle
= SCHED_TIME (crit_succ
);
2387 return SMODULO (crit_cycle
, ii
);
2391 fprintf (dump_file
, "Both crit_pred and crit_succ are NULL\n");
2393 return SMODULO ((low
+ up
+ 1) / 2, ii
);
2397 verify_partial_schedule (partial_schedule_ptr ps
, sbitmap sched_nodes
)
2400 ps_insn_ptr crr_insn
;
2402 for (row
= 0; row
< ps
->ii
; row
++)
2406 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2408 int u
= crr_insn
->id
;
2411 gcc_assert (bitmap_bit_p (sched_nodes
, u
));
2412 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2413 popcount (sched_nodes) == number of insns in ps. */
2414 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
2415 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
2418 gcc_assert (ps
->rows_length
[row
] == length
);
2423 /* This page implements the algorithm for ordering the nodes of a DDG
2424 for modulo scheduling, activated through the
2425 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2427 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2428 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
2429 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
2430 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2431 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
2432 #define DEPTH(x) (ASAP ((x)))
2434 typedef struct node_order_params
* nopa
;
2436 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
2437 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
2438 static nopa
calculate_order_params (ddg_ptr
, int, int *);
2439 static int find_max_asap (ddg_ptr
, sbitmap
);
2440 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
2441 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
2443 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
2445 struct node_order_params
2452 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2454 check_nodes_order (int *node_order
, int num_nodes
)
2457 auto_sbitmap
tmp (num_nodes
);
2462 fprintf (dump_file
, "SMS final nodes order: \n");
2464 for (i
= 0; i
< num_nodes
; i
++)
2466 int u
= node_order
[i
];
2469 fprintf (dump_file
, "%d ", u
);
2470 gcc_assert (u
< num_nodes
&& u
>= 0 && !bitmap_bit_p (tmp
, u
));
2472 bitmap_set_bit (tmp
, u
);
2476 fprintf (dump_file
, "\n");
2479 /* Order the nodes of G for scheduling and pass the result in
2480 NODE_ORDER. Also set aux.count of each node to ASAP.
2481 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2483 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
, int *pmax_asap
)
2487 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
2489 nopa nops
= calculate_order_params (g
, mii
, pmax_asap
);
2492 print_sccs (dump_file
, sccs
, g
);
2494 order_nodes_of_sccs (sccs
, node_order
);
2496 if (sccs
->num_sccs
> 0)
2497 /* First SCC has the largest recurrence_length. */
2498 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
2500 /* Save ASAP before destroying node_order_params. */
2501 for (i
= 0; i
< g
->num_nodes
; i
++)
2503 ddg_node_ptr v
= &g
->nodes
[i
];
2504 v
->aux
.count
= ASAP (v
);
2508 free_ddg_all_sccs (sccs
);
2509 check_nodes_order (node_order
, g
->num_nodes
);
2515 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
2518 ddg_ptr g
= all_sccs
->ddg
;
2519 int num_nodes
= g
->num_nodes
;
2520 auto_sbitmap
prev_sccs (num_nodes
);
2521 auto_sbitmap
on_path (num_nodes
);
2522 auto_sbitmap
tmp (num_nodes
);
2523 auto_sbitmap
ones (num_nodes
);
2525 bitmap_clear (prev_sccs
);
2528 /* Perform the node ordering starting from the SCC with the highest recMII.
2529 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2530 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
2532 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
2534 /* Add nodes on paths from previous SCCs to the current SCC. */
2535 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
2536 bitmap_ior (tmp
, scc
->nodes
, on_path
);
2538 /* Add nodes on paths from the current SCC to previous SCCs. */
2539 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
2540 bitmap_ior (tmp
, tmp
, on_path
);
2542 /* Remove nodes of previous SCCs from current extended SCC. */
2543 bitmap_and_compl (tmp
, tmp
, prev_sccs
);
2545 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2546 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2549 /* Handle the remaining nodes that do not belong to any scc. Each call
2550 to order_nodes_in_scc handles a single connected component. */
2551 while (pos
< g
->num_nodes
)
2553 bitmap_and_compl (tmp
, ones
, prev_sccs
);
2554 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2558 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2559 static struct node_order_params
*
2560 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
, int *pmax_asap
)
2564 int num_nodes
= g
->num_nodes
;
2566 /* Allocate a place to hold ordering params for each node in the DDG. */
2567 nopa node_order_params_arr
;
2569 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2570 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
2571 sizeof (struct node_order_params
));
2573 /* Set the aux pointer of each node to point to its order_params structure. */
2574 for (u
= 0; u
< num_nodes
; u
++)
2575 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
2577 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2578 calculate ASAP, ALAP, mobility, distance, and height for each node
2579 in the dependence (direct acyclic) graph. */
2581 /* We assume that the nodes in the array are in topological order. */
2584 for (u
= 0; u
< num_nodes
; u
++)
2586 ddg_node_ptr u_node
= &g
->nodes
[u
];
2589 for (e
= u_node
->in
; e
; e
= e
->next_in
)
2590 if (e
->distance
== 0)
2591 ASAP (u_node
) = MAX (ASAP (u_node
),
2592 ASAP (e
->src
) + e
->latency
);
2593 max_asap
= MAX (max_asap
, ASAP (u_node
));
2596 for (u
= num_nodes
- 1; u
> -1; u
--)
2598 ddg_node_ptr u_node
= &g
->nodes
[u
];
2600 ALAP (u_node
) = max_asap
;
2601 HEIGHT (u_node
) = 0;
2602 for (e
= u_node
->out
; e
; e
= e
->next_out
)
2603 if (e
->distance
== 0)
2605 ALAP (u_node
) = MIN (ALAP (u_node
),
2606 ALAP (e
->dest
) - e
->latency
);
2607 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
2608 HEIGHT (e
->dest
) + e
->latency
);
2613 fprintf (dump_file
, "\nOrder params\n");
2614 for (u
= 0; u
< num_nodes
; u
++)
2616 ddg_node_ptr u_node
= &g
->nodes
[u
];
2618 fprintf (dump_file
, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u
,
2619 ASAP (u_node
), ALAP (u_node
), HEIGHT (u_node
));
2623 *pmax_asap
= max_asap
;
2624 return node_order_params_arr
;
2628 find_max_asap (ddg_ptr g
, sbitmap nodes
)
2633 sbitmap_iterator sbi
;
2635 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2637 ddg_node_ptr u_node
= &g
->nodes
[u
];
2639 if (max_asap
< ASAP (u_node
))
2641 max_asap
= ASAP (u_node
);
2649 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
2653 int min_mob
= INT_MAX
;
2655 sbitmap_iterator sbi
;
2657 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2659 ddg_node_ptr u_node
= &g
->nodes
[u
];
2661 if (max_hv
< HEIGHT (u_node
))
2663 max_hv
= HEIGHT (u_node
);
2664 min_mob
= MOB (u_node
);
2667 else if ((max_hv
== HEIGHT (u_node
))
2668 && (min_mob
> MOB (u_node
)))
2670 min_mob
= MOB (u_node
);
2678 find_max_dv_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_dv
< DEPTH (u_node
))
2692 max_dv
= DEPTH (u_node
);
2693 min_mob
= MOB (u_node
);
2696 else if ((max_dv
== DEPTH (u_node
))
2697 && (min_mob
> MOB (u_node
)))
2699 min_mob
= MOB (u_node
);
2706 /* Places the nodes of SCC into the NODE_ORDER array starting
2707 at position POS, according to the SMS ordering algorithm.
2708 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2709 the NODE_ORDER array, starting from position zero. */
2711 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
2712 int * node_order
, int pos
)
2714 enum sms_direction dir
;
2715 int num_nodes
= g
->num_nodes
;
2716 auto_sbitmap
workset (num_nodes
);
2717 auto_sbitmap
tmp (num_nodes
);
2718 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
2719 auto_sbitmap
predecessors (num_nodes
);
2720 auto_sbitmap
successors (num_nodes
);
2722 bitmap_clear (predecessors
);
2723 find_predecessors (predecessors
, g
, nodes_ordered
);
2725 bitmap_clear (successors
);
2726 find_successors (successors
, g
, nodes_ordered
);
2729 if (bitmap_and (tmp
, predecessors
, scc
))
2731 bitmap_copy (workset
, tmp
);
2734 else if (bitmap_and (tmp
, successors
, scc
))
2736 bitmap_copy (workset
, tmp
);
2743 bitmap_clear (workset
);
2744 if ((u
= find_max_asap (g
, scc
)) >= 0)
2745 bitmap_set_bit (workset
, u
);
2749 bitmap_clear (zero_bitmap
);
2750 while (!bitmap_equal_p (workset
, zero_bitmap
))
2753 ddg_node_ptr v_node
;
2754 sbitmap v_node_preds
;
2755 sbitmap v_node_succs
;
2759 while (!bitmap_equal_p (workset
, zero_bitmap
))
2761 v
= find_max_hv_min_mob (g
, workset
);
2762 v_node
= &g
->nodes
[v
];
2763 node_order
[pos
++] = v
;
2764 v_node_succs
= NODE_SUCCESSORS (v_node
);
2765 bitmap_and (tmp
, v_node_succs
, scc
);
2767 /* Don't consider the already ordered successors again. */
2768 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2769 bitmap_ior (workset
, workset
, tmp
);
2770 bitmap_clear_bit (workset
, v
);
2771 bitmap_set_bit (nodes_ordered
, v
);
2774 bitmap_clear (predecessors
);
2775 find_predecessors (predecessors
, g
, nodes_ordered
);
2776 bitmap_and (workset
, predecessors
, scc
);
2780 while (!bitmap_equal_p (workset
, zero_bitmap
))
2782 v
= find_max_dv_min_mob (g
, workset
);
2783 v_node
= &g
->nodes
[v
];
2784 node_order
[pos
++] = v
;
2785 v_node_preds
= NODE_PREDECESSORS (v_node
);
2786 bitmap_and (tmp
, v_node_preds
, scc
);
2788 /* Don't consider the already ordered predecessors again. */
2789 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2790 bitmap_ior (workset
, workset
, tmp
);
2791 bitmap_clear_bit (workset
, v
);
2792 bitmap_set_bit (nodes_ordered
, v
);
2795 bitmap_clear (successors
);
2796 find_successors (successors
, g
, nodes_ordered
);
2797 bitmap_and (workset
, successors
, scc
);
2800 sbitmap_free (zero_bitmap
);
2805 /* This page contains functions for manipulating partial-schedules during
2806 modulo scheduling. */
2808 /* Create a partial schedule and allocate a memory to hold II rows. */
2810 static partial_schedule_ptr
2811 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2813 partial_schedule_ptr ps
= XNEW (struct partial_schedule
);
2814 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2815 ps
->rows_length
= (int *) xcalloc (ii
, sizeof (int));
2816 ps
->reg_moves
.create (0);
2818 ps
->history
= history
;
2819 ps
->min_cycle
= INT_MAX
;
2820 ps
->max_cycle
= INT_MIN
;
2826 /* Free the PS_INSNs in rows array of the given partial schedule.
2827 ??? Consider caching the PS_INSN's. */
2829 free_ps_insns (partial_schedule_ptr ps
)
2833 for (i
= 0; i
< ps
->ii
; i
++)
2837 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2840 ps
->rows
[i
] = ps_insn
;
2846 /* Free all the memory allocated to the partial schedule. */
2849 free_partial_schedule (partial_schedule_ptr ps
)
2851 ps_reg_move_info
*move
;
2857 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
2858 sbitmap_free (move
->uses
);
2859 ps
->reg_moves
.release ();
2863 free (ps
->rows_length
);
2867 /* Clear the rows array with its PS_INSNs, and create a new one with
2871 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2876 if (new_ii
== ps
->ii
)
2878 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2879 * sizeof (ps_insn_ptr
));
2880 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2881 ps
->rows_length
= (int *) xrealloc (ps
->rows_length
, new_ii
* sizeof (int));
2882 memset (ps
->rows_length
, 0, new_ii
* sizeof (int));
2884 ps
->min_cycle
= INT_MAX
;
2885 ps
->max_cycle
= INT_MIN
;
2888 /* Prints the partial schedule as an ii rows array, for each rows
2889 print the ids of the insns in it. */
2891 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2895 for (i
= 0; i
< ps
->ii
; i
++)
2897 ps_insn_ptr ps_i
= ps
->rows
[i
];
2899 fprintf (dump
, "\n[ROW %d ]: ", i
);
2902 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_i
->id
);
2905 fprintf (dump
, "%d (branch), ", INSN_UID (insn
));
2907 fprintf (dump
, "%d, ", INSN_UID (insn
));
2909 ps_i
= ps_i
->next_in_row
;
2914 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2916 create_ps_insn (int id
, int cycle
)
2918 ps_insn_ptr ps_i
= XNEW (struct ps_insn
);
2921 ps_i
->next_in_row
= NULL
;
2922 ps_i
->prev_in_row
= NULL
;
2923 ps_i
->cycle
= cycle
;
2929 /* Removes the given PS_INSN from the partial schedule. */
2931 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2935 gcc_assert (ps
&& ps_i
);
2937 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2938 if (! ps_i
->prev_in_row
)
2940 gcc_assert (ps_i
== ps
->rows
[row
]);
2941 ps
->rows
[row
] = ps_i
->next_in_row
;
2943 ps
->rows
[row
]->prev_in_row
= NULL
;
2947 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
2948 if (ps_i
->next_in_row
)
2949 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
2952 ps
->rows_length
[row
] -= 1;
2957 /* Unlike what literature describes for modulo scheduling (which focuses
2958 on VLIW machines) the order of the instructions inside a cycle is
2959 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2960 where the current instruction should go relative to the already
2961 scheduled instructions in the given cycle. Go over these
2962 instructions and find the first possible column to put it in. */
2964 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2965 sbitmap must_precede
, sbitmap must_follow
)
2967 ps_insn_ptr next_ps_i
;
2968 ps_insn_ptr first_must_follow
= NULL
;
2969 ps_insn_ptr last_must_precede
= NULL
;
2970 ps_insn_ptr last_in_row
= NULL
;
2976 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2978 /* Find the first must follow and the last must precede
2979 and insert the node immediately after the must precede
2980 but make sure that it there is no must follow after it. */
2981 for (next_ps_i
= ps
->rows
[row
];
2983 next_ps_i
= next_ps_i
->next_in_row
)
2986 && bitmap_bit_p (must_follow
, next_ps_i
->id
)
2987 && ! first_must_follow
)
2988 first_must_follow
= next_ps_i
;
2989 if (must_precede
&& bitmap_bit_p (must_precede
, next_ps_i
->id
))
2991 /* If we have already met a node that must follow, then
2992 there is no possible column. */
2993 if (first_must_follow
)
2996 last_must_precede
= next_ps_i
;
2998 /* The closing branch must be the last in the row. */
2999 if (JUMP_P (ps_rtl_insn (ps
, next_ps_i
->id
)))
3002 last_in_row
= next_ps_i
;
3005 /* The closing branch is scheduled as well. Make sure there is no
3006 dependent instruction after it as the branch should be the last
3007 instruction in the row. */
3008 if (JUMP_P (ps_rtl_insn (ps
, ps_i
->id
)))
3010 if (first_must_follow
)
3014 /* Make the branch the last in the row. New instructions
3015 will be inserted at the beginning of the row or after the
3016 last must_precede instruction thus the branch is guaranteed
3017 to remain the last instruction in the row. */
3018 last_in_row
->next_in_row
= ps_i
;
3019 ps_i
->prev_in_row
= last_in_row
;
3020 ps_i
->next_in_row
= NULL
;
3023 ps
->rows
[row
] = ps_i
;
3027 /* Now insert the node after INSERT_AFTER_PSI. */
3029 if (! last_must_precede
)
3031 ps_i
->next_in_row
= ps
->rows
[row
];
3032 ps_i
->prev_in_row
= NULL
;
3033 if (ps_i
->next_in_row
)
3034 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3035 ps
->rows
[row
] = ps_i
;
3039 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
3040 last_must_precede
->next_in_row
= ps_i
;
3041 ps_i
->prev_in_row
= last_must_precede
;
3042 if (ps_i
->next_in_row
)
3043 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3049 /* Advances the PS_INSN one column in its current row; returns false
3050 in failure and true in success. Bit N is set in MUST_FOLLOW if
3051 the node with cuid N must be come after the node pointed to by
3052 PS_I when scheduled in the same cycle. */
3054 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
3055 sbitmap must_follow
)
3057 ps_insn_ptr prev
, next
;
3063 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3065 if (! ps_i
->next_in_row
)
3068 /* Check if next_in_row is dependent on ps_i, both having same sched
3069 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
3070 if (must_follow
&& bitmap_bit_p (must_follow
, ps_i
->next_in_row
->id
))
3073 /* Advance PS_I over its next_in_row in the doubly linked list. */
3074 prev
= ps_i
->prev_in_row
;
3075 next
= ps_i
->next_in_row
;
3077 if (ps_i
== ps
->rows
[row
])
3078 ps
->rows
[row
] = next
;
3080 ps_i
->next_in_row
= next
->next_in_row
;
3082 if (next
->next_in_row
)
3083 next
->next_in_row
->prev_in_row
= ps_i
;
3085 next
->next_in_row
= ps_i
;
3086 ps_i
->prev_in_row
= next
;
3088 next
->prev_in_row
= prev
;
3090 prev
->next_in_row
= next
;
3095 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
3096 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
3097 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
3098 before/after (respectively) the node pointed to by PS_I when scheduled
3099 in the same cycle. */
3101 add_node_to_ps (partial_schedule_ptr ps
, int id
, int cycle
,
3102 sbitmap must_precede
, sbitmap must_follow
)
3105 int row
= SMODULO (cycle
, ps
->ii
);
3107 if (ps
->rows_length
[row
] >= issue_rate
)
3110 ps_i
= create_ps_insn (id
, cycle
);
3112 /* Finds and inserts PS_I according to MUST_FOLLOW and
3114 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
3120 ps
->rows_length
[row
] += 1;
3124 /* Advance time one cycle. Assumes DFA is being used. */
3126 advance_one_cycle (void)
3128 if (targetm
.sched
.dfa_pre_cycle_insn
)
3129 state_transition (curr_state
,
3130 targetm
.sched
.dfa_pre_cycle_insn ());
3132 state_transition (curr_state
, NULL
);
3134 if (targetm
.sched
.dfa_post_cycle_insn
)
3135 state_transition (curr_state
,
3136 targetm
.sched
.dfa_post_cycle_insn ());
3141 /* Checks if PS has resource conflicts according to DFA, starting from
3142 FROM cycle to TO cycle; returns true if there are conflicts and false
3143 if there are no conflicts. Assumes DFA is being used. */
3145 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
3149 state_reset (curr_state
);
3151 for (cycle
= from
; cycle
<= to
; cycle
++)
3153 ps_insn_ptr crr_insn
;
3154 /* Holds the remaining issue slots in the current row. */
3155 int can_issue_more
= issue_rate
;
3157 /* Walk through the DFA for the current row. */
3158 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
3160 crr_insn
= crr_insn
->next_in_row
)
3162 rtx_insn
*insn
= ps_rtl_insn (ps
, crr_insn
->id
);
3164 if (!NONDEBUG_INSN_P (insn
))
3167 /* Check if there is room for the current insn. */
3168 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
3171 /* Update the DFA state and return with failure if the DFA found
3172 resource conflicts. */
3173 if (state_transition (curr_state
, insn
) >= 0)
3176 if (targetm
.sched
.variable_issue
)
3178 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
3179 insn
, can_issue_more
);
3180 /* A naked CLOBBER or USE generates no instruction, so don't
3181 let them consume issue slots. */
3182 else if (GET_CODE (PATTERN (insn
)) != USE
3183 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3187 /* Advance the DFA to the next cycle. */
3188 advance_one_cycle ();
3193 /* Checks if the given node causes resource conflicts when added to PS at
3194 cycle C. If not the node is added to PS and returned; otherwise zero
3195 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
3196 cuid N must be come before/after (respectively) the node pointed to by
3197 PS_I when scheduled in the same cycle. */
3199 ps_add_node_check_conflicts (partial_schedule_ptr ps
, int n
,
3200 int c
, sbitmap must_precede
,
3201 sbitmap must_follow
)
3203 int has_conflicts
= 0;
3206 /* First add the node to the PS, if this succeeds check for
3207 conflicts, trying different issue slots in the same row. */
3208 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
3209 return NULL
; /* Failed to insert the node at the given cycle. */
3211 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3213 && ps_has_conflicts (ps
,
3217 /* Try different issue slots to find one that the given node can be
3218 scheduled in without conflicts. */
3219 while (has_conflicts
)
3221 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
3223 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3225 && ps_has_conflicts (ps
,
3232 remove_node_from_ps (ps
, ps_i
);
3236 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
3237 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
3241 /* Calculate the stage count of the partial schedule PS. The calculation
3242 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3244 calculate_stage_count (partial_schedule_ptr ps
, int rotation_amount
)
3246 int new_min_cycle
= PS_MIN_CYCLE (ps
) - rotation_amount
;
3247 int new_max_cycle
= PS_MAX_CYCLE (ps
) - rotation_amount
;
3248 int stage_count
= CALC_STAGE_COUNT (-1, new_min_cycle
, ps
->ii
);
3250 /* The calculation of stage count is done adding the number of stages
3251 before cycle zero and after cycle zero. */
3252 stage_count
+= CALC_STAGE_COUNT (new_max_cycle
, 0, ps
->ii
);
3257 /* Rotate the rows of PS such that insns scheduled at time
3258 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3260 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
3262 int i
, row
, backward_rotates
;
3263 int last_row
= ps
->ii
- 1;
3265 if (start_cycle
== 0)
3268 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
3270 /* Revisit later and optimize this into a single loop. */
3271 for (i
= 0; i
< backward_rotates
; i
++)
3273 ps_insn_ptr first_row
= ps
->rows
[0];
3274 int first_row_length
= ps
->rows_length
[0];
3276 for (row
= 0; row
< last_row
; row
++)
3278 ps
->rows
[row
] = ps
->rows
[row
+ 1];
3279 ps
->rows_length
[row
] = ps
->rows_length
[row
+ 1];
3282 ps
->rows
[last_row
] = first_row
;
3283 ps
->rows_length
[last_row
] = first_row_length
;
3286 ps
->max_cycle
-= start_cycle
;
3287 ps
->min_cycle
-= start_cycle
;
3290 #endif /* INSN_SCHEDULING */
3292 /* Run instruction scheduler. */
3293 /* Perform SMS module scheduling. */
3297 const pass_data pass_data_sms
=
3299 RTL_PASS
, /* type */
3301 OPTGROUP_NONE
, /* optinfo_flags */
3303 0, /* properties_required */
3304 0, /* properties_provided */
3305 0, /* properties_destroyed */
3306 0, /* todo_flags_start */
3307 TODO_df_finish
, /* todo_flags_finish */
3310 class pass_sms
: public rtl_opt_pass
3313 pass_sms (gcc::context
*ctxt
)
3314 : rtl_opt_pass (pass_data_sms
, ctxt
)
3317 /* opt_pass methods: */
3318 virtual bool gate (function
*)
3320 return (optimize
> 0 && flag_modulo_sched
);
3323 virtual unsigned int execute (function
*);
3325 }; // class pass_sms
3328 pass_sms::execute (function
*fun ATTRIBUTE_UNUSED
)
3330 #ifdef INSN_SCHEDULING
3333 /* Collect loop information to be used in SMS. */
3334 cfg_layout_initialize (0);
3337 /* Update the life information, because we add pseudos. */
3338 max_regno
= max_reg_num ();
3340 /* Finalize layout changes. */
3341 FOR_EACH_BB_FN (bb
, fun
)
3342 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3343 bb
->aux
= bb
->next_bb
;
3344 free_dominance_info (CDI_DOMINATORS
);
3345 cfg_layout_finalize ();
3346 #endif /* INSN_SCHEDULING */
3353 make_pass_sms (gcc::context
*ctxt
)
3355 return new pass_sms (ctxt
);