1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004-2021 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 int calculate_stage_count (partial_schedule_ptr
, int);
214 static void calculate_must_precede_follow (ddg_node_ptr
, int, int,
215 int, int, sbitmap
, sbitmap
, sbitmap
);
216 static int get_sched_window (partial_schedule_ptr
, ddg_node_ptr
,
217 sbitmap
, int, int *, int *, int *);
218 static bool try_scheduling_node_in_cycle (partial_schedule_ptr
, int, int,
219 sbitmap
, int *, sbitmap
, sbitmap
);
220 static void remove_node_from_ps (partial_schedule_ptr
, ps_insn_ptr
);
222 #define NODE_ASAP(node) ((node)->aux.count)
224 #define SCHED_PARAMS(x) (&node_sched_param_vec[x])
225 #define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
226 #define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
227 #define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
228 #define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
230 /* The scheduling parameters held for each node. */
231 typedef struct node_sched_params
233 int time
; /* The absolute scheduling cycle. */
235 int row
; /* Holds time % ii. */
236 int stage
; /* Holds time / ii. */
238 /* The column of a node inside the ps. If nodes u, v are on the same row,
239 u will precede v if column (u) < column (v). */
241 } *node_sched_params_ptr
;
243 /* The following three functions are copied from the current scheduler
244 code in order to use sched_analyze() for computing the dependencies.
245 They are used when initializing the sched_info structure. */
247 sms_print_insn (const rtx_insn
*insn
, int aligned ATTRIBUTE_UNUSED
)
251 sprintf (tmp
, "i%4d", INSN_UID (insn
));
256 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
257 regset used ATTRIBUTE_UNUSED
)
261 static struct common_sched_info_def sms_common_sched_info
;
263 static struct sched_deps_info_def sms_sched_deps_info
=
265 compute_jump_reg_dependencies
,
266 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
271 static struct haifa_sched_info sms_sched_info
=
280 NULL
, /* insn_finishes_block_p */
285 NULL
, NULL
, NULL
, NULL
,
290 /* Partial schedule instruction ID in PS is a register move. Return
291 information about it. */
292 static struct ps_reg_move_info
*
293 ps_reg_move (partial_schedule_ptr ps
, int id
)
295 gcc_checking_assert (id
>= ps
->g
->num_nodes
);
296 return &ps
->reg_moves
[id
- ps
->g
->num_nodes
];
299 /* Return the rtl instruction that is being scheduled by partial schedule
300 instruction ID, which belongs to schedule PS. */
302 ps_rtl_insn (partial_schedule_ptr ps
, int id
)
304 if (id
< ps
->g
->num_nodes
)
305 return ps
->g
->nodes
[id
].insn
;
307 return ps_reg_move (ps
, id
)->insn
;
310 /* Partial schedule instruction ID, which belongs to PS, occurred in
311 the original (unscheduled) loop. Return the first instruction
312 in the loop that was associated with ps_rtl_insn (PS, ID).
313 If the instruction had some notes before it, this is the first
316 ps_first_note (partial_schedule_ptr ps
, int id
)
318 gcc_assert (id
< ps
->g
->num_nodes
);
319 return ps
->g
->nodes
[id
].first_note
;
322 /* Return the number of consecutive stages that are occupied by
323 partial schedule instruction ID in PS. */
325 ps_num_consecutive_stages (partial_schedule_ptr ps
, int id
)
327 if (id
< ps
->g
->num_nodes
)
330 return ps_reg_move (ps
, id
)->num_consecutive_stages
;
333 /* Given HEAD and TAIL which are the first and last insns in a loop;
334 return the register which controls the loop. Return zero if it has
335 more than one occurrence in the loop besides the control part or the
336 do-loop pattern is not of the form we expect. */
338 doloop_register_get (rtx_insn
*head
, rtx_insn
*tail
)
341 rtx_insn
*insn
, *first_insn_not_to_check
;
346 if (!targetm
.code_for_doloop_end
)
349 /* TODO: Free SMS's dependence on doloop_condition_get. */
350 condition
= doloop_condition_get (tail
);
354 if (REG_P (XEXP (condition
, 0)))
355 reg
= XEXP (condition
, 0);
356 else if (GET_CODE (XEXP (condition
, 0)) == PLUS
357 && REG_P (XEXP (XEXP (condition
, 0), 0)))
358 reg
= XEXP (XEXP (condition
, 0), 0);
362 /* Check that the COUNT_REG has no other occurrences in the loop
363 until the decrement. We assume the control part consists of
364 either a single (parallel) branch-on-count or a (non-parallel)
365 branch immediately preceded by a single (decrement) insn. */
366 first_insn_not_to_check
= (GET_CODE (PATTERN (tail
)) == PARALLEL
? tail
367 : prev_nondebug_insn (tail
));
369 for (insn
= head
; insn
!= first_insn_not_to_check
; insn
= NEXT_INSN (insn
))
370 if (NONDEBUG_INSN_P (insn
) && reg_mentioned_p (reg
, insn
))
374 fprintf (dump_file
, "SMS count_reg found ");
375 print_rtl_single (dump_file
, reg
);
376 fprintf (dump_file
, " outside control in insn:\n");
377 print_rtl_single (dump_file
, insn
);
386 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
387 that the number of iterations is a compile-time constant. If so,
388 return the rtx_insn that sets COUNT_REG to a constant, and set COUNT to
389 this constant. Otherwise return 0. */
391 const_iteration_count (rtx count_reg
, basic_block pre_header
,
392 int64_t *count
, bool* adjust_inplace
)
395 rtx_insn
*head
, *tail
;
397 *adjust_inplace
= false;
398 bool read_after
= false;
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 (single_set (insn
) && rtx_equal_p (count_reg
,
407 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
));
414 *adjust_inplace
= !read_after
;
420 else if (NONDEBUG_INSN_P (insn
) && reg_mentioned_p (count_reg
, insn
))
423 if (reg_set_p (count_reg
, insn
))
430 /* A very simple resource-based lower bound on the initiation interval.
431 ??? Improve the accuracy of this bound by considering the
432 utilization of various units. */
436 if (targetm
.sched
.sms_res_mii
)
437 return targetm
.sched
.sms_res_mii (g
);
439 return g
->num_nodes
/ issue_rate
;
443 /* A vector that contains the sched data for each ps_insn. */
444 static vec
<node_sched_params
> node_sched_param_vec
;
446 /* Allocate sched_params for each node and initialize it. */
448 set_node_sched_params (ddg_ptr g
)
450 node_sched_param_vec
.truncate (0);
451 node_sched_param_vec
.safe_grow_cleared (g
->num_nodes
, true);
454 /* Make sure that node_sched_param_vec has an entry for every move in PS. */
456 extend_node_sched_params (partial_schedule_ptr ps
)
458 node_sched_param_vec
.safe_grow_cleared (ps
->g
->num_nodes
459 + ps
->reg_moves
.length (), true);
462 /* Update the sched_params (time, row and stage) for node U using the II,
463 the CYCLE of U and MIN_CYCLE.
464 We're not simply taking the following
465 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
466 because the stages may not be aligned on cycle 0. */
468 update_node_sched_params (int u
, int ii
, int cycle
, int min_cycle
)
470 int sc_until_cycle_zero
;
473 SCHED_TIME (u
) = cycle
;
474 SCHED_ROW (u
) = SMODULO (cycle
, ii
);
476 /* The calculation of stage count is done adding the number
477 of stages before cycle zero and after cycle zero. */
478 sc_until_cycle_zero
= CALC_STAGE_COUNT (-1, min_cycle
, ii
);
480 if (SCHED_TIME (u
) < 0)
482 stage
= CALC_STAGE_COUNT (-1, SCHED_TIME (u
), ii
);
483 SCHED_STAGE (u
) = sc_until_cycle_zero
- stage
;
487 stage
= CALC_STAGE_COUNT (SCHED_TIME (u
), 0, ii
);
488 SCHED_STAGE (u
) = sc_until_cycle_zero
+ stage
- 1;
493 print_node_sched_params (FILE *file
, int num_nodes
, partial_schedule_ptr ps
)
499 for (i
= 0; i
< num_nodes
; i
++)
501 node_sched_params_ptr nsp
= SCHED_PARAMS (i
);
503 fprintf (file
, "Node = %d; INSN = %d\n", i
,
504 INSN_UID (ps_rtl_insn (ps
, i
)));
505 fprintf (file
, " asap = %d:\n", NODE_ASAP (&ps
->g
->nodes
[i
]));
506 fprintf (file
, " time = %d:\n", nsp
->time
);
507 fprintf (file
, " stage = %d:\n", nsp
->stage
);
511 /* Set SCHED_COLUMN for each instruction in row ROW of PS. */
513 set_columns_for_row (partial_schedule_ptr ps
, int row
)
515 ps_insn_ptr cur_insn
;
519 for (cur_insn
= ps
->rows
[row
]; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
520 SCHED_COLUMN (cur_insn
->id
) = column
++;
523 /* Set SCHED_COLUMN for each instruction in PS. */
525 set_columns_for_ps (partial_schedule_ptr ps
)
529 for (row
= 0; row
< ps
->ii
; row
++)
530 set_columns_for_row (ps
, row
);
533 /* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
534 Its single predecessor has already been scheduled, as has its
535 ddg node successors. (The move may have also another move as its
536 successor, in which case that successor will be scheduled later.)
538 The move is part of a chain that satisfies register dependencies
539 between a producing ddg node and various consuming ddg nodes.
540 If some of these dependencies have a distance of 1 (meaning that
541 the use is upward-exposed) then DISTANCE1_USES is nonnull and
542 contains the set of uses with distance-1 dependencies.
543 DISTANCE1_USES is null otherwise.
545 MUST_FOLLOW is a scratch bitmap that is big enough to hold
546 all current ps_insn ids.
548 Return true on success. */
550 schedule_reg_move (partial_schedule_ptr ps
, int i_reg_move
,
551 sbitmap distance1_uses
, sbitmap must_follow
)
554 int this_time
, this_distance
, this_start
, this_end
, this_latency
;
555 int start
, end
, c
, ii
;
556 sbitmap_iterator sbi
;
557 ps_reg_move_info
*move
;
561 move
= ps_reg_move (ps
, i_reg_move
);
565 fprintf (dump_file
, "Scheduling register move INSN %d; ii = %d"
566 ", min cycle = %d\n\n", INSN_UID (move
->insn
), ii
,
568 print_rtl_single (dump_file
, move
->insn
);
569 fprintf (dump_file
, "\n%11s %11s %5s\n", "start", "end", "time");
570 fprintf (dump_file
, "=========== =========== =====\n");
576 /* For dependencies of distance 1 between a producer ddg node A
577 and consumer ddg node B, we have a chain of dependencies:
579 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
581 where Mi is the ith move. For dependencies of distance 0 between
582 a producer ddg node A and consumer ddg node C, we have a chain of
585 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
587 where Mi' occupies the same position as Mi but occurs a stage later.
588 We can only schedule each move once, so if we have both types of
589 chain, we model the second as:
591 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
593 First handle the dependencies between the previously-scheduled
594 predecessor and the move. */
595 this_insn
= ps_rtl_insn (ps
, move
->def
);
596 this_latency
= insn_latency (this_insn
, move
->insn
);
597 this_distance
= distance1_uses
&& move
->def
< ps
->g
->num_nodes
? 1 : 0;
598 this_time
= SCHED_TIME (move
->def
) - this_distance
* ii
;
599 this_start
= this_time
+ this_latency
;
600 this_end
= this_time
+ ii
;
602 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
603 this_start
, this_end
, SCHED_TIME (move
->def
),
604 INSN_UID (this_insn
), this_latency
, this_distance
,
605 INSN_UID (move
->insn
));
607 if (start
< this_start
)
612 /* Handle the dependencies between the move and previously-scheduled
614 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, u
, sbi
)
616 this_insn
= ps_rtl_insn (ps
, u
);
617 this_latency
= insn_latency (move
->insn
, this_insn
);
618 if (distance1_uses
&& !bitmap_bit_p (distance1_uses
, u
))
622 this_time
= SCHED_TIME (u
) + this_distance
* ii
;
623 this_start
= this_time
- ii
;
624 this_end
= this_time
- this_latency
;
626 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
627 this_start
, this_end
, SCHED_TIME (u
), INSN_UID (move
->insn
),
628 this_latency
, this_distance
, INSN_UID (this_insn
));
630 if (start
< this_start
)
638 fprintf (dump_file
, "----------- ----------- -----\n");
639 fprintf (dump_file
, "%11d %11d %5s %s\n", start
, end
, "", "(max, min)");
642 bitmap_clear (must_follow
);
643 bitmap_set_bit (must_follow
, move
->def
);
645 start
= MAX (start
, end
- (ii
- 1));
646 for (c
= end
; c
>= start
; c
--)
648 psi
= ps_add_node_check_conflicts (ps
, i_reg_move
, c
,
649 move
->uses
, must_follow
);
652 update_node_sched_params (i_reg_move
, ii
, c
, PS_MIN_CYCLE (ps
));
654 fprintf (dump_file
, "\nScheduled register move INSN %d at"
655 " time %d, row %d\n\n", INSN_UID (move
->insn
), c
,
656 SCHED_ROW (i_reg_move
));
662 fprintf (dump_file
, "\nNo available slot\n\n");
668 Breaking intra-loop register anti-dependences:
669 Each intra-loop register anti-dependence implies a cross-iteration true
670 dependence of distance 1. Therefore, we can remove such false dependencies
671 and figure out if the partial schedule broke them by checking if (for a
672 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
673 if so generate a register move. The number of such moves is equal to:
674 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
675 nreg_moves = ----------------------------------- + 1 - { dependence.
679 schedule_reg_moves (partial_schedule_ptr ps
)
685 for (i
= 0; i
< g
->num_nodes
; i
++)
687 ddg_node_ptr u
= &g
->nodes
[i
];
689 int nreg_moves
= 0, i_reg_move
;
690 rtx prev_reg
, old_reg
;
693 sbitmap distance1_uses
;
694 rtx set
= single_set (u
->insn
);
696 /* Skip instructions that do not set a register. */
697 if (set
&& !REG_P (SET_DEST (set
)))
700 /* Compute the number of reg_moves needed for u, by looking at life
701 ranges started at u (excluding self-loops). */
702 distances
[0] = distances
[1] = false;
703 for (e
= u
->out
; e
; e
= e
->next_out
)
704 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
706 int nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
707 - SCHED_TIME (e
->src
->cuid
)) / ii
;
709 if (e
->distance
== 1)
710 nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
711 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
713 /* If dest precedes src in the schedule of the kernel, then dest
714 will read before src writes and we can save one reg_copy. */
715 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
716 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
719 if (nreg_moves4e
>= 1)
721 /* !single_set instructions are not supported yet and
722 thus we do not except to encounter them in the loop
723 except from the doloop part. For the latter case
724 we assume no regmoves are generated as the doloop
725 instructions are tied to the branch with an edge. */
727 /* If the instruction contains auto-inc register then
728 validate that the regmov is being generated for the
729 target regsiter rather then the inc'ed register. */
730 gcc_assert (!autoinc_var_is_used_p (u
->insn
, e
->dest
->insn
));
735 gcc_assert (e
->distance
< 2);
736 distances
[e
->distance
] = true;
738 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
744 /* Create NREG_MOVES register moves. */
745 first_move
= ps
->reg_moves
.length ();
746 ps
->reg_moves
.safe_grow_cleared (first_move
+ nreg_moves
, true);
747 extend_node_sched_params (ps
);
749 /* Record the moves associated with this node. */
750 first_move
+= ps
->g
->num_nodes
;
752 /* Generate each move. */
753 old_reg
= prev_reg
= SET_DEST (set
);
754 if (HARD_REGISTER_P (old_reg
))
757 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
759 ps_reg_move_info
*move
= ps_reg_move (ps
, first_move
+ i_reg_move
);
761 move
->def
= i_reg_move
> 0 ? first_move
+ i_reg_move
- 1 : i
;
762 move
->uses
= sbitmap_alloc (first_move
+ nreg_moves
);
763 move
->old_reg
= old_reg
;
764 move
->new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
765 move
->num_consecutive_stages
= distances
[0] && distances
[1] ? 2 : 1;
766 move
->insn
= gen_move_insn (move
->new_reg
, copy_rtx (prev_reg
));
767 bitmap_clear (move
->uses
);
769 prev_reg
= move
->new_reg
;
772 distance1_uses
= distances
[1] ? sbitmap_alloc (g
->num_nodes
) : NULL
;
775 bitmap_clear (distance1_uses
);
777 /* Every use of the register defined by node may require a different
778 copy of this register, depending on the time the use is scheduled.
779 Record which uses require which move results. */
780 for (e
= u
->out
; e
; e
= e
->next_out
)
781 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
783 int dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
784 - SCHED_TIME (e
->src
->cuid
)) / ii
;
786 if (e
->distance
== 1)
787 dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
788 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
790 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
791 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
796 ps_reg_move_info
*move
;
798 move
= ps_reg_move (ps
, first_move
+ dest_copy
- 1);
799 bitmap_set_bit (move
->uses
, e
->dest
->cuid
);
800 if (e
->distance
== 1)
801 bitmap_set_bit (distance1_uses
, e
->dest
->cuid
);
805 auto_sbitmap
must_follow (first_move
+ nreg_moves
);
806 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
807 if (!schedule_reg_move (ps
, first_move
+ i_reg_move
,
808 distance1_uses
, must_follow
))
811 sbitmap_free (distance1_uses
);
812 if (i_reg_move
< nreg_moves
)
818 /* Emit the moves associated with PS. Apply the substitutions
819 associated with them. */
821 apply_reg_moves (partial_schedule_ptr ps
)
823 ps_reg_move_info
*move
;
826 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
829 sbitmap_iterator sbi
;
831 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, i_use
, sbi
)
833 replace_rtx (ps
->g
->nodes
[i_use
].insn
, move
->old_reg
, move
->new_reg
);
834 df_insn_rescan (ps
->g
->nodes
[i_use
].insn
);
839 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
840 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
841 will move to cycle zero. */
843 reset_sched_times (partial_schedule_ptr ps
, int amount
)
847 ps_insn_ptr crr_insn
;
849 for (row
= 0; row
< ii
; row
++)
850 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
852 int u
= crr_insn
->id
;
853 int normalized_time
= SCHED_TIME (u
) - amount
;
854 int new_min_cycle
= PS_MIN_CYCLE (ps
) - amount
;
858 /* Print the scheduling times after the rotation. */
859 rtx_insn
*insn
= ps_rtl_insn (ps
, u
);
861 fprintf (dump_file
, "crr_insn->node=%d (insn id %d), "
862 "crr_insn->cycle=%d, min_cycle=%d", u
,
863 INSN_UID (insn
), normalized_time
, new_min_cycle
);
865 fprintf (dump_file
, " (branch)");
866 fprintf (dump_file
, "\n");
869 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
870 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
872 crr_insn
->cycle
= normalized_time
;
873 update_node_sched_params (u
, ii
, normalized_time
, new_min_cycle
);
877 /* Permute the insns according to their order in PS, from row 0 to
878 row ii-1, and position them right before LAST. This schedules
879 the insns of the loop kernel. */
881 permute_partial_schedule (partial_schedule_ptr ps
, rtx_insn
*last
)
887 for (row
= 0; row
< ii
; row
++)
888 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
890 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_ij
->id
);
892 if (PREV_INSN (last
) != insn
)
894 if (ps_ij
->id
< ps
->g
->num_nodes
)
895 reorder_insns_nobb (ps_first_note (ps
, ps_ij
->id
), insn
,
898 add_insn_before (insn
, last
, NULL
);
903 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
904 respectively only if cycle C falls on the border of the scheduling
905 window boundaries marked by START and END cycles. STEP is the
906 direction of the window. */
908 set_must_precede_follow (sbitmap
*tmp_follow
, sbitmap must_follow
,
909 sbitmap
*tmp_precede
, sbitmap must_precede
, int c
,
910 int start
, int end
, int step
)
918 *tmp_precede
= must_precede
;
919 else /* step == -1. */
920 *tmp_follow
= must_follow
;
925 *tmp_follow
= must_follow
;
926 else /* step == -1. */
927 *tmp_precede
= must_precede
;
932 /* Return True if the branch can be moved to row ii-1 while
933 normalizing the partial schedule PS to start from cycle zero and thus
934 optimize the SC. Otherwise return False. */
936 optimize_sc (partial_schedule_ptr ps
, ddg_ptr g
)
938 int amount
= PS_MIN_CYCLE (ps
);
939 int start
, end
, step
;
942 int stage_count
, stage_count_curr
;
944 /* Compare the SC after normalization and SC after bringing the branch
945 to row ii-1. If they are equal just bail out. */
946 stage_count
= calculate_stage_count (ps
, amount
);
948 calculate_stage_count (ps
, SCHED_TIME (g
->closing_branch
->cuid
) - (ii
- 1));
950 if (stage_count
== stage_count_curr
)
953 fprintf (dump_file
, "SMS SC already optimized.\n");
960 fprintf (dump_file
, "SMS Trying to optimize branch location\n");
961 fprintf (dump_file
, "SMS partial schedule before trial:\n");
962 print_partial_schedule (ps
, dump_file
);
965 /* First, normalize the partial scheduling. */
966 reset_sched_times (ps
, amount
);
967 rotate_partial_schedule (ps
, amount
);
971 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
973 print_partial_schedule (ps
, dump_file
);
976 if (SMODULO (SCHED_TIME (g
->closing_branch
->cuid
), ii
) == ii
- 1)
979 auto_sbitmap
sched_nodes (g
->num_nodes
);
980 bitmap_ones (sched_nodes
);
982 /* Calculate the new placement of the branch. It should be in row
983 ii-1 and fall into it's scheduling window. */
984 if (get_sched_window (ps
, g
->closing_branch
, sched_nodes
, ii
, &start
,
988 ps_insn_ptr next_ps_i
;
989 int branch_cycle
= SCHED_TIME (g
->closing_branch
->cuid
);
990 int row
= SMODULO (branch_cycle
, ps
->ii
);
992 sbitmap tmp_precede
, tmp_follow
;
996 fprintf (dump_file
, "\nTrying to schedule node %d "
997 "INSN = %d in (%d .. %d) step %d\n",
998 g
->closing_branch
->cuid
,
999 (INSN_UID (g
->closing_branch
->insn
)), start
, end
, step
);
1001 gcc_assert ((step
> 0 && start
< end
) || (step
< 0 && start
> end
));
1004 c
= start
+ ii
- SMODULO (start
, ii
) - 1;
1005 gcc_assert (c
>= start
);
1010 "SMS failed to schedule branch at cycle: %d\n", c
);
1016 c
= start
- SMODULO (start
, ii
) - 1;
1017 gcc_assert (c
<= start
);
1023 "SMS failed to schedule branch at cycle: %d\n", c
);
1028 auto_sbitmap
must_precede (g
->num_nodes
);
1029 auto_sbitmap
must_follow (g
->num_nodes
);
1031 /* Try to schedule the branch is it's new cycle. */
1032 calculate_must_precede_follow (g
->closing_branch
, start
, end
,
1033 step
, ii
, sched_nodes
,
1034 must_precede
, must_follow
);
1036 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1037 must_precede
, c
, start
, end
, step
);
1039 /* Find the element in the partial schedule related to the closing
1040 branch so we can remove it from it's current cycle. */
1041 for (next_ps_i
= ps
->rows
[row
];
1042 next_ps_i
; next_ps_i
= next_ps_i
->next_in_row
)
1043 if (next_ps_i
->id
== g
->closing_branch
->cuid
)
1046 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1047 remove_node_from_ps (ps
, next_ps_i
);
1049 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
, c
,
1050 sched_nodes
, &num_splits
,
1051 tmp_precede
, tmp_follow
);
1052 gcc_assert (num_splits
== 0);
1057 "SMS failed to schedule branch at cycle: %d, "
1058 "bringing it back to cycle %d\n", c
, branch_cycle
);
1060 /* The branch was failed to be placed in row ii - 1.
1061 Put it back in it's original place in the partial
1063 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1064 must_precede
, branch_cycle
, start
, end
,
1067 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
,
1068 branch_cycle
, sched_nodes
,
1069 &num_splits
, tmp_precede
,
1071 gcc_assert (success
&& (num_splits
== 0));
1076 /* The branch is placed in row ii - 1. */
1079 "SMS success in moving branch to cycle %d\n", c
);
1081 update_node_sched_params (g
->closing_branch
->cuid
, ii
, c
,
1086 /* This might have been added to a new first stage. */
1087 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1088 reset_sched_times (ps
, 0);
1095 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
1096 int to_stage
, rtx count_reg
, class loop
*loop
)
1102 for (row
= 0; row
< ps
->ii
; row
++)
1103 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
1106 int first_u
, last_u
;
1109 /* Do not duplicate any insn which refers to count_reg as it
1110 belongs to the control part.
1111 The closing branch is scheduled as well and thus should
1113 TODO: This should be done by analyzing the control part of
1115 u_insn
= ps_rtl_insn (ps
, u
);
1116 if (reg_mentioned_p (count_reg
, u_insn
)
1120 first_u
= SCHED_STAGE (u
);
1121 last_u
= first_u
+ ps_num_consecutive_stages (ps
, u
) - 1;
1122 if (from_stage
<= last_u
&& to_stage
>= first_u
)
1124 if (u
< ps
->g
->num_nodes
)
1125 duplicate_insn_chain (ps_first_note (ps
, u
), u_insn
,
1128 emit_insn (copy_rtx (PATTERN (u_insn
)));
1134 /* Generate the instructions (including reg_moves) for prolog & epilog. */
1136 generate_prolog_epilog (partial_schedule_ptr ps
, class loop
*loop
,
1137 rtx count_reg
, bool adjust_init
)
1140 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
1143 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1148 /* Generate instructions at the beginning of the prolog to
1149 adjust the loop count by STAGE_COUNT. If loop count is constant
1150 and it not used anywhere in prologue, this constant is adjusted by
1151 STAGE_COUNT outside of generate_prolog_epilog function. */
1152 rtx sub_reg
= NULL_RTX
;
1154 sub_reg
= expand_simple_binop (GET_MODE (count_reg
), MINUS
, count_reg
,
1155 gen_int_mode (last_stage
,
1156 GET_MODE (count_reg
)),
1157 count_reg
, 1, OPTAB_DIRECT
);
1158 gcc_assert (REG_P (sub_reg
));
1159 if (REGNO (sub_reg
) != REGNO (count_reg
))
1160 emit_move_insn (count_reg
, sub_reg
);
1163 for (i
= 0; i
< last_stage
; i
++)
1164 duplicate_insns_of_cycles (ps
, 0, i
, count_reg
, loop
);
1166 /* Put the prolog on the entry edge. */
1167 e
= loop_preheader_edge (loop
);
1168 split_edge_and_insert (e
, get_insns ());
1169 if (!flag_resched_modulo_sched
)
1170 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1174 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1177 for (i
= 0; i
< last_stage
; i
++)
1178 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, count_reg
, loop
);
1180 /* Put the epilogue on the exit edge. */
1181 gcc_assert (single_exit (loop
));
1182 e
= single_exit (loop
);
1183 split_edge_and_insert (e
, get_insns ());
1184 if (!flag_resched_modulo_sched
)
1185 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1190 /* Mark LOOP as software pipelined so the later
1191 scheduling passes don't touch it. */
1193 mark_loop_unsched (class loop
*loop
)
1196 basic_block
*bbs
= get_loop_body (loop
);
1198 for (i
= 0; i
< loop
->num_nodes
; i
++)
1199 bbs
[i
]->flags
|= BB_DISABLE_SCHEDULE
;
1204 /* Return true if all the BBs of the loop are empty except the
1207 loop_single_full_bb_p (class loop
*loop
)
1210 basic_block
*bbs
= get_loop_body (loop
);
1212 for (i
= 0; i
< loop
->num_nodes
; i
++)
1214 rtx_insn
*head
, *tail
;
1215 bool empty_bb
= true;
1217 if (bbs
[i
] == loop
->header
)
1220 /* Make sure that basic blocks other than the header
1221 have only notes labels or jumps. */
1222 get_ebb_head_tail (bbs
[i
], bbs
[i
], &head
, &tail
);
1223 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
1225 if (NOTE_P (head
) || LABEL_P (head
)
1226 || (INSN_P (head
) && (DEBUG_INSN_P (head
) || JUMP_P (head
))))
1242 /* Dump file:line from INSN's location info to dump_file. */
1245 dump_insn_location (rtx_insn
*insn
)
1247 if (dump_file
&& INSN_HAS_LOCATION (insn
))
1249 expanded_location xloc
= insn_location (insn
);
1250 fprintf (dump_file
, " %s:%i", xloc
.file
, xloc
.line
);
1254 /* A simple loop from SMS point of view; it is a loop that is composed of
1255 either a single basic block or two BBs - a header and a latch. */
1256 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1257 && (EDGE_COUNT (loop->latch->preds) == 1) \
1258 && (EDGE_COUNT (loop->latch->succs) == 1))
1260 /* Return true if the loop is in its canonical form and false if not.
1261 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1263 loop_canon_p (class loop
*loop
)
1266 if (loop
->inner
|| !loop_outer (loop
))
1269 fprintf (dump_file
, "SMS loop inner or !loop_outer\n");
1273 if (!single_exit (loop
))
1277 rtx_insn
*insn
= BB_END (loop
->header
);
1279 fprintf (dump_file
, "SMS loop many exits");
1280 dump_insn_location (insn
);
1281 fprintf (dump_file
, "\n");
1286 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
1290 rtx_insn
*insn
= BB_END (loop
->header
);
1292 fprintf (dump_file
, "SMS loop many BBs.");
1293 dump_insn_location (insn
);
1294 fprintf (dump_file
, "\n");
1302 /* If there are more than one entry for the loop,
1303 make it one by splitting the first entry edge and
1304 redirecting the others to the new BB. */
1306 canon_loop (class loop
*loop
)
1311 /* Avoid annoying special cases of edges going to exit
1313 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1314 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
1317 if (loop
->latch
== loop
->header
1318 || EDGE_COUNT (loop
->latch
->succs
) > 1)
1320 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
1321 if (e
->src
== loop
->latch
)
1329 setup_sched_infos (void)
1331 memcpy (&sms_common_sched_info
, &haifa_common_sched_info
,
1332 sizeof (sms_common_sched_info
));
1333 sms_common_sched_info
.sched_pass_id
= SCHED_SMS_PASS
;
1334 common_sched_info
= &sms_common_sched_info
;
1336 sched_deps_info
= &sms_sched_deps_info
;
1337 current_sched_info
= &sms_sched_info
;
1340 /* Probability in % that the sms-ed loop rolls enough so that optimized
1341 version may be entered. Just a guess. */
1342 #define PROB_SMS_ENOUGH_ITERATIONS 80
1344 /* Main entry point, perform SMS scheduling on the loops of the function
1345 that consist of single basic blocks. */
1352 int maxii
, max_asap
;
1353 partial_schedule_ptr ps
;
1354 basic_block bb
= NULL
;
1356 basic_block condition_bb
= NULL
;
1358 HOST_WIDE_INT trip_count
, max_trip_count
;
1360 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1361 | LOOPS_HAVE_RECORDED_EXITS
);
1362 if (number_of_loops (cfun
) <= 1)
1364 loop_optimizer_finalize ();
1365 return; /* There are no loops to schedule. */
1368 /* Initialize issue_rate. */
1369 if (targetm
.sched
.issue_rate
)
1371 int temp
= reload_completed
;
1373 reload_completed
= 1;
1374 issue_rate
= targetm
.sched
.issue_rate ();
1375 reload_completed
= temp
;
1380 /* Initialize the scheduler. */
1381 setup_sched_infos ();
1382 haifa_sched_init ();
1384 /* Allocate memory to hold the DDG array one entry for each loop.
1385 We use loop->num as index into this array. */
1386 g_arr
= XCNEWVEC (ddg_ptr
, number_of_loops (cfun
));
1390 fprintf (dump_file
, "\n\nSMS analysis phase\n");
1391 fprintf (dump_file
, "===================\n\n");
1394 /* Build DDGs for all the relevant loops and hold them in G_ARR
1395 indexed by the loop index. */
1396 FOR_EACH_LOOP (loop
, 0)
1398 rtx_insn
*head
, *tail
;
1401 /* For debugging. */
1402 if (dbg_cnt (sms_sched_loop
) == false)
1405 fprintf (dump_file
, "SMS reached max limit... \n");
1412 rtx_insn
*insn
= BB_END (loop
->header
);
1414 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1415 dump_insn_location (insn
);
1416 fprintf (dump_file
, "\n");
1419 if (! loop_canon_p (loop
))
1422 if (! loop_single_full_bb_p (loop
))
1425 fprintf (dump_file
, "SMS not loop_single_full_bb_p\n");
1431 get_ebb_head_tail (bb
, bb
, &head
, &tail
);
1432 latch_edge
= loop_latch_edge (loop
);
1433 gcc_assert (single_exit (loop
));
1434 trip_count
= get_estimated_loop_iterations_int (loop
);
1435 max_trip_count
= get_max_loop_iterations_int (loop
);
1437 /* Perform SMS only on loops that their average count is above threshold. */
1439 if ( latch_edge
->count () > profile_count::zero ()
1440 && (latch_edge
->count()
1441 < single_exit (loop
)->count ().apply_scale
1442 (param_sms_loop_average_count_threshold
, 1)))
1446 dump_insn_location (tail
);
1447 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1448 if (profile_info
&& flag_branch_probabilities
)
1450 fprintf (dump_file
, "SMS loop-count ");
1451 fprintf (dump_file
, "%" PRId64
,
1452 (int64_t) bb
->count
.to_gcov_type ());
1453 fprintf (dump_file
, "\n");
1454 fprintf (dump_file
, "SMS trip-count ");
1455 fprintf (dump_file
, "%" PRId64
"max %" PRId64
,
1456 (int64_t) trip_count
, (int64_t) max_trip_count
);
1457 fprintf (dump_file
, "\n");
1463 /* Make sure this is a doloop. */
1464 if ( !(count_reg
= doloop_register_get (head
, tail
)))
1467 fprintf (dump_file
, "SMS doloop_register_get failed\n");
1471 /* Don't handle BBs with calls or barriers
1472 or !single_set with the exception of instructions that include
1473 count_reg---these instructions are part of the control part
1474 that do-loop recognizes.
1475 ??? Should handle insns defining subregs. */
1476 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1482 || (NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1483 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
1484 && !reg_mentioned_p (count_reg
, insn
))
1485 || (INSN_P (insn
) && (set
= single_set (insn
))
1486 && GET_CODE (SET_DEST (set
)) == SUBREG
))
1490 if (insn
!= NEXT_INSN (tail
))
1495 fprintf (dump_file
, "SMS loop-with-call\n");
1496 else if (BARRIER_P (insn
))
1497 fprintf (dump_file
, "SMS loop-with-barrier\n");
1498 else if ((NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1499 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
1500 fprintf (dump_file
, "SMS loop-with-not-single-set\n");
1502 fprintf (dump_file
, "SMS loop with subreg in lhs\n");
1503 print_rtl_single (dump_file
, insn
);
1509 /* Always schedule the closing branch with the rest of the
1510 instructions. The branch is rotated to be in row ii-1 at the
1511 end of the scheduling procedure to make sure it's the last
1512 instruction in the iteration. */
1513 if (! (g
= create_ddg (bb
, 1)))
1516 fprintf (dump_file
, "SMS create_ddg failed\n");
1520 g_arr
[loop
->num
] = g
;
1522 fprintf (dump_file
, "...OK\n");
1527 fprintf (dump_file
, "\nSMS transformation phase\n");
1528 fprintf (dump_file
, "=========================\n\n");
1531 /* We don't want to perform SMS on new loops - created by versioning. */
1532 FOR_EACH_LOOP (loop
, 0)
1534 rtx_insn
*head
, *tail
;
1536 rtx_insn
*count_init
;
1537 int mii
, rec_mii
, stage_count
, min_cycle
;
1538 int64_t loop_count
= 0;
1539 bool opt_sc_p
, adjust_inplace
= false;
1540 basic_block pre_header
;
1542 if (! (g
= g_arr
[loop
->num
]))
1547 rtx_insn
*insn
= BB_END (loop
->header
);
1549 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1550 dump_insn_location (insn
);
1551 fprintf (dump_file
, "\n");
1553 print_ddg (dump_file
, g
);
1556 get_ebb_head_tail (loop
->header
, loop
->header
, &head
, &tail
);
1558 latch_edge
= loop_latch_edge (loop
);
1559 gcc_assert (single_exit (loop
));
1560 trip_count
= get_estimated_loop_iterations_int (loop
);
1561 max_trip_count
= get_max_loop_iterations_int (loop
);
1565 dump_insn_location (tail
);
1566 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1567 if (profile_info
&& flag_branch_probabilities
)
1569 fprintf (dump_file
, "SMS loop-count ");
1570 fprintf (dump_file
, "%" PRId64
,
1571 (int64_t) bb
->count
.to_gcov_type ());
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 count_reg
= doloop_register_get (head
, tail
);
1582 gcc_assert (count_reg
);
1584 pre_header
= loop_preheader_edge (loop
)->src
;
1585 count_init
= const_iteration_count (count_reg
, pre_header
, &loop_count
,
1588 if (dump_file
&& count_init
)
1590 fprintf (dump_file
, "SMS const-doloop ");
1591 fprintf (dump_file
, "%" PRId64
,
1593 fprintf (dump_file
, "\n");
1596 node_order
= XNEWVEC (int, g
->num_nodes
);
1598 mii
= 1; /* Need to pass some estimate of mii. */
1599 rec_mii
= sms_order_nodes (g
, mii
, node_order
, &max_asap
);
1600 mii
= MAX (res_MII (g
), rec_mii
);
1602 maxii
= MAX (max_asap
, param_sms_max_ii_factor
* mii
);
1605 fprintf (dump_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1606 rec_mii
, mii
, maxii
);
1610 set_node_sched_params (g
);
1614 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
);
1618 /* Try to achieve optimized SC by normalizing the partial
1619 schedule (having the cycles start from cycle zero).
1620 The branch location must be placed in row ii-1 in the
1621 final scheduling. If failed, shift all instructions to
1622 position the branch in row ii-1. */
1623 opt_sc_p
= optimize_sc (ps
, g
);
1625 stage_count
= calculate_stage_count (ps
, 0);
1628 /* Bring the branch to cycle ii-1. */
1629 int amount
= (SCHED_TIME (g
->closing_branch
->cuid
)
1633 fprintf (dump_file
, "SMS schedule branch at cycle ii-1\n");
1635 stage_count
= calculate_stage_count (ps
, amount
);
1638 gcc_assert (stage_count
>= 1);
1641 /* The default value of param_sms_min_sc is 2 as stage count of
1642 1 means that there is no interleaving between iterations thus
1643 we let the scheduling passes do the job in this case. */
1644 if (stage_count
< param_sms_min_sc
1645 || (count_init
&& (loop_count
<= stage_count
))
1646 || (max_trip_count
>= 0 && max_trip_count
<= stage_count
)
1647 || (trip_count
>= 0 && trip_count
<= stage_count
))
1651 fprintf (dump_file
, "SMS failed... \n");
1652 fprintf (dump_file
, "SMS sched-failed (stage-count=%d,"
1653 " loop-count=", stage_count
);
1654 fprintf (dump_file
, "%" PRId64
, loop_count
);
1655 fprintf (dump_file
, ", trip-count=");
1656 fprintf (dump_file
, "%" PRId64
"max %" PRId64
,
1657 (int64_t) trip_count
, (int64_t) max_trip_count
);
1658 fprintf (dump_file
, ")\n");
1665 /* Rotate the partial schedule to have the branch in row ii-1. */
1666 int amount
= SCHED_TIME (g
->closing_branch
->cuid
) - (ps
->ii
- 1);
1668 reset_sched_times (ps
, amount
);
1669 rotate_partial_schedule (ps
, amount
);
1672 set_columns_for_ps (ps
);
1674 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1675 if (!schedule_reg_moves (ps
))
1678 free_partial_schedule (ps
);
1682 /* Moves that handle incoming values might have been added
1683 to a new first stage. Bump the stage count if so.
1685 ??? Perhaps we could consider rotating the schedule here
1687 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1689 reset_sched_times (ps
, 0);
1693 /* The stage count should now be correct without rotation. */
1694 gcc_checking_assert (stage_count
== calculate_stage_count (ps
, 0));
1695 PS_STAGE_COUNT (ps
) = stage_count
;
1701 dump_insn_location (tail
);
1702 fprintf (dump_file
, " SMS succeeded %d %d (with ii, sc)\n",
1703 ps
->ii
, stage_count
);
1704 print_partial_schedule (ps
, dump_file
);
1711 /* When possible, set new iteration count of loop kernel in
1712 place. Otherwise, generate_prolog_epilog creates an insn
1714 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1720 /* case the BCT count is not known , Do loop-versioning */
1721 rtx comp_rtx
= gen_rtx_GT (VOIDmode
, count_reg
,
1722 gen_int_mode (stage_count
,
1723 GET_MODE (count_reg
)));
1724 profile_probability prob
= profile_probability::guessed_always ()
1725 .apply_scale (PROB_SMS_ENOUGH_ITERATIONS
, 100);
1727 loop_version (loop
, comp_rtx
, &condition_bb
,
1728 prob
, prob
.invert (),
1729 prob
, prob
.invert (), true);
1732 /* Now apply the scheduled kernel to the RTL of the loop. */
1733 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1735 /* Mark this loop as software pipelined so the later
1736 scheduling passes don't touch it. */
1737 if (! flag_resched_modulo_sched
)
1738 mark_loop_unsched (loop
);
1740 /* The life-info is not valid any more. */
1741 df_set_bb_dirty (g
->bb
);
1743 apply_reg_moves (ps
);
1745 print_node_sched_params (dump_file
, g
->num_nodes
, ps
);
1746 /* Generate prolog and epilog. */
1747 generate_prolog_epilog (ps
, loop
, count_reg
, !adjust_inplace
);
1751 free_partial_schedule (ps
);
1752 node_sched_param_vec
.release ();
1759 /* Release scheduler data, needed until now because of DFA. */
1760 haifa_sched_finish ();
1761 loop_optimizer_finalize ();
1764 /* The SMS scheduling algorithm itself
1765 -----------------------------------
1766 Input: 'O' an ordered list of insns of a loop.
1767 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1769 'Q' is the empty Set
1770 'PS' is the partial schedule; it holds the currently scheduled nodes with
1772 'PSP' previously scheduled predecessors.
1773 'PSS' previously scheduled successors.
1774 't(u)' the cycle where u is scheduled.
1775 'l(u)' is the latency of u.
1776 'd(v,u)' is the dependence distance from v to u.
1777 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1778 the node ordering phase.
1779 'check_hardware_resources_conflicts(u, PS, c)'
1780 run a trace around cycle/slot through DFA model
1781 to check resource conflicts involving instruction u
1782 at cycle c given the partial schedule PS.
1783 'add_to_partial_schedule_at_time(u, PS, c)'
1784 Add the node/instruction u to the partial schedule
1786 'calculate_register_pressure(PS)'
1787 Given a schedule of instructions, calculate the register
1788 pressure it implies. One implementation could be the
1789 maximum number of overlapping live ranges.
1790 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1791 registers available in the hardware.
1795 3. for each node u in O in pre-computed order
1796 4. if (PSP(u) != Q && PSS(u) == Q) then
1797 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1798 6. start = Early_start; end = Early_start + II - 1; step = 1
1799 11. else if (PSP(u) == Q && PSS(u) != Q) then
1800 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1801 13. start = Late_start; end = Late_start - II + 1; step = -1
1802 14. else if (PSP(u) != Q && PSS(u) != Q) then
1803 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1804 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1805 17. start = Early_start;
1806 18. end = min(Early_start + II - 1 , Late_start);
1808 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1809 21. start = ASAP(u); end = start + II - 1; step = 1
1813 24. for (c = start ; c != end ; c += step)
1814 25. if check_hardware_resources_conflicts(u, PS, c) then
1815 26. add_to_partial_schedule_at_time(u, PS, c)
1820 31. if (success == false) then
1822 33. if (II > maxII) then
1823 34. finish - failed to schedule
1828 39. if (calculate_register_pressure(PS) > maxRP) then
1831 42. compute epilogue & prologue
1832 43. finish - succeeded to schedule
1834 ??? The algorithm restricts the scheduling window to II cycles.
1835 In rare cases, it may be better to allow windows of II+1 cycles.
1836 The window would then start and end on the same row, but with
1837 different "must precede" and "must follow" requirements. */
1839 /* A threshold for the number of repeated unsuccessful attempts to insert
1840 an empty row, before we flush the partial schedule and start over. */
1841 #define MAX_SPLIT_NUM 10
1842 /* Given the partial schedule PS, this function calculates and returns the
1843 cycles in which we can schedule the node with the given index I.
1844 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1845 noticed that there are several cases in which we fail to SMS the loop
1846 because the sched window of a node is empty due to tight data-deps. In
1847 such cases we want to unschedule some of the predecessors/successors
1848 until we get non-empty scheduling window. It returns -1 if the
1849 scheduling window is empty and zero otherwise. */
1852 get_sched_window (partial_schedule_ptr ps
, ddg_node_ptr u_node
,
1853 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
,
1856 int start
, step
, end
;
1857 int early_start
, late_start
;
1859 auto_sbitmap
psp (ps
->g
->num_nodes
);
1860 auto_sbitmap
pss (ps
->g
->num_nodes
);
1861 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1862 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1868 /* 1. compute sched window for u (start, end, step). */
1871 psp_not_empty
= bitmap_and (psp
, u_node_preds
, sched_nodes
);
1872 pss_not_empty
= bitmap_and (pss
, u_node_succs
, sched_nodes
);
1874 /* We first compute a forward range (start <= end), then decide whether
1876 early_start
= INT_MIN
;
1877 late_start
= INT_MAX
;
1885 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1887 fprintf (dump_file
, "\nAnalyzing dependencies for node %d (INSN %d)"
1888 "; ii = %d\n\n", u_node
->cuid
, INSN_UID (u_node
->insn
), ii
);
1889 fprintf (dump_file
, "%11s %11s %11s %11s %5s\n",
1890 "start", "early start", "late start", "end", "time");
1891 fprintf (dump_file
, "=========== =========== =========== ==========="
1894 /* Calculate early_start and limit end. Both bounds are inclusive. */
1896 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1898 int v
= e
->src
->cuid
;
1900 if (bitmap_bit_p (sched_nodes
, v
))
1902 int p_st
= SCHED_TIME (v
);
1903 int earliest
= p_st
+ e
->latency
- (e
->distance
* ii
);
1904 int latest
= (e
->data_type
== MEM_DEP
? p_st
+ ii
- 1 : INT_MAX
);
1908 fprintf (dump_file
, "%11s %11d %11s %11d %5d",
1909 "", earliest
, "", latest
, p_st
);
1910 print_ddg_edge (dump_file
, e
);
1911 fprintf (dump_file
, "\n");
1914 early_start
= MAX (early_start
, earliest
);
1915 end
= MIN (end
, latest
);
1917 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1922 /* Calculate late_start and limit start. Both bounds are inclusive. */
1924 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1926 int v
= e
->dest
->cuid
;
1928 if (bitmap_bit_p (sched_nodes
, v
))
1930 int s_st
= SCHED_TIME (v
);
1931 int earliest
= (e
->data_type
== MEM_DEP
? s_st
- ii
+ 1 : INT_MIN
);
1932 int latest
= s_st
- e
->latency
+ (e
->distance
* ii
);
1936 fprintf (dump_file
, "%11d %11s %11d %11s %5d",
1937 earliest
, "", latest
, "", s_st
);
1938 print_ddg_edge (dump_file
, e
);
1939 fprintf (dump_file
, "\n");
1942 start
= MAX (start
, earliest
);
1943 late_start
= MIN (late_start
, latest
);
1945 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1950 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1952 fprintf (dump_file
, "----------- ----------- ----------- -----------"
1954 fprintf (dump_file
, "%11d %11d %11d %11d %5s %s\n",
1955 start
, early_start
, late_start
, end
, "",
1956 "(max, max, min, min)");
1959 /* Get a target scheduling window no bigger than ii. */
1960 if (early_start
== INT_MIN
&& late_start
== INT_MAX
)
1961 early_start
= NODE_ASAP (u_node
);
1962 else if (early_start
== INT_MIN
)
1963 early_start
= late_start
- (ii
- 1);
1964 late_start
= MIN (late_start
, early_start
+ (ii
- 1));
1966 /* Apply memory dependence limits. */
1967 start
= MAX (start
, early_start
);
1968 end
= MIN (end
, late_start
);
1970 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1971 fprintf (dump_file
, "%11s %11d %11d %11s %5s final window\n",
1972 "", start
, end
, "", "");
1974 /* If there are at least as many successors as predecessors, schedule the
1975 node close to its successors. */
1976 if (pss_not_empty
&& count_succs
>= count_preds
)
1978 std::swap (start
, end
);
1982 /* Now that we've finalized the window, make END an exclusive rather
1983 than an inclusive bound. */
1990 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
1993 fprintf (dump_file
, "\nEmpty window: start=%d, end=%d, step=%d\n",
2001 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
2002 node currently been scheduled. At the end of the calculation
2003 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
2004 U_NODE which are (1) already scheduled in the first/last row of
2005 U_NODE's scheduling window, (2) whose dependence inequality with U
2006 becomes an equality when U is scheduled in this same row, and (3)
2007 whose dependence latency is zero.
2009 The first and last rows are calculated using the following parameters:
2010 START/END rows - The cycles that begins/ends the traversal on the window;
2011 searching for an empty cycle to schedule U_NODE.
2012 STEP - The direction in which we traverse the window.
2013 II - The initiation interval. */
2016 calculate_must_precede_follow (ddg_node_ptr u_node
, int start
, int end
,
2017 int step
, int ii
, sbitmap sched_nodes
,
2018 sbitmap must_precede
, sbitmap must_follow
)
2021 int first_cycle_in_window
, last_cycle_in_window
;
2023 gcc_assert (must_precede
&& must_follow
);
2025 /* Consider the following scheduling window:
2026 {first_cycle_in_window, first_cycle_in_window+1, ...,
2027 last_cycle_in_window}. If step is 1 then the following will be
2028 the order we traverse the window: {start=first_cycle_in_window,
2029 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
2030 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
2031 end=first_cycle_in_window-1} if step is -1. */
2032 first_cycle_in_window
= (step
== 1) ? start
: end
- step
;
2033 last_cycle_in_window
= (step
== 1) ? end
- step
: start
;
2035 bitmap_clear (must_precede
);
2036 bitmap_clear (must_follow
);
2039 fprintf (dump_file
, "\nmust_precede: ");
2041 /* Instead of checking if:
2042 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
2043 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
2044 first_cycle_in_window)
2046 we use the fact that latency is non-negative:
2047 SCHED_TIME (e->src) - (e->distance * ii) <=
2048 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
2049 first_cycle_in_window
2051 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
2052 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2053 if (bitmap_bit_p (sched_nodes
, e
->src
->cuid
)
2054 && ((SCHED_TIME (e
->src
->cuid
) - (e
->distance
* ii
)) ==
2055 first_cycle_in_window
))
2058 fprintf (dump_file
, "%d ", e
->src
->cuid
);
2060 bitmap_set_bit (must_precede
, e
->src
->cuid
);
2064 fprintf (dump_file
, "\nmust_follow: ");
2066 /* Instead of checking if:
2067 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
2068 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
2069 last_cycle_in_window)
2071 we use the fact that latency is non-negative:
2072 SCHED_TIME (e->dest) + (e->distance * ii) >=
2073 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
2074 last_cycle_in_window
2076 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
2077 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2078 if (bitmap_bit_p (sched_nodes
, e
->dest
->cuid
)
2079 && ((SCHED_TIME (e
->dest
->cuid
) + (e
->distance
* ii
)) ==
2080 last_cycle_in_window
))
2083 fprintf (dump_file
, "%d ", e
->dest
->cuid
);
2085 bitmap_set_bit (must_follow
, e
->dest
->cuid
);
2089 fprintf (dump_file
, "\n");
2092 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
2093 parameters to decide if that's possible:
2094 PS - The partial schedule.
2095 U - The serial number of U_NODE.
2096 NUM_SPLITS - The number of row splits made so far.
2097 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
2098 the first row of the scheduling window)
2099 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
2100 last row of the scheduling window) */
2103 try_scheduling_node_in_cycle (partial_schedule_ptr ps
,
2104 int u
, int cycle
, sbitmap sched_nodes
,
2105 int *num_splits
, sbitmap must_precede
,
2106 sbitmap must_follow
)
2111 verify_partial_schedule (ps
, sched_nodes
);
2112 psi
= ps_add_node_check_conflicts (ps
, u
, cycle
, must_precede
, must_follow
);
2115 SCHED_TIME (u
) = cycle
;
2116 bitmap_set_bit (sched_nodes
, u
);
2120 fprintf (dump_file
, "Scheduled w/o split in %d\n", cycle
);
2127 /* This function implements the scheduling algorithm for SMS according to the
2129 static partial_schedule_ptr
2130 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
)
2133 int i
, c
, success
, num_splits
= 0;
2134 int flush_and_start_over
= true;
2135 int num_nodes
= g
->num_nodes
;
2136 int start
, end
, step
; /* Place together into one struct? */
2137 auto_sbitmap
sched_nodes (num_nodes
);
2138 auto_sbitmap
must_precede (num_nodes
);
2139 auto_sbitmap
must_follow (num_nodes
);
2140 auto_sbitmap
tobe_scheduled (num_nodes
);
2142 /* Value of param_sms_dfa_history is a limit on the number of cycles that
2143 resource conflicts can span. ??? Should be provided by DFA, and be
2144 dependent on the type of insn scheduled. Set to 0 by default to save
2146 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
,
2147 param_sms_dfa_history
);
2149 bitmap_ones (tobe_scheduled
);
2150 bitmap_clear (sched_nodes
);
2152 while (flush_and_start_over
&& (ii
< maxii
))
2156 fprintf (dump_file
, "Starting with ii=%d\n", ii
);
2157 flush_and_start_over
= false;
2158 bitmap_clear (sched_nodes
);
2160 for (i
= 0; i
< num_nodes
; i
++)
2162 int u
= nodes_order
[i
];
2163 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
2164 rtx_insn
*insn
= u_node
->insn
;
2166 gcc_checking_assert (NONDEBUG_INSN_P (insn
));
2168 if (bitmap_bit_p (sched_nodes
, u
))
2171 /* Try to get non-empty scheduling window. */
2173 if (get_sched_window (ps
, u_node
, sched_nodes
, ii
, &start
,
2177 fprintf (dump_file
, "\nTrying to schedule node %d "
2178 "INSN = %d in (%d .. %d) step %d\n", u
, (INSN_UID
2179 (g
->nodes
[u
].insn
)), start
, end
, step
);
2181 gcc_assert ((step
> 0 && start
< end
)
2182 || (step
< 0 && start
> end
));
2184 calculate_must_precede_follow (u_node
, start
, end
, step
, ii
,
2185 sched_nodes
, must_precede
,
2188 for (c
= start
; c
!= end
; c
+= step
)
2190 sbitmap tmp_precede
, tmp_follow
;
2192 set_must_precede_follow (&tmp_follow
, must_follow
,
2193 &tmp_precede
, must_precede
,
2194 c
, start
, end
, step
);
2196 try_scheduling_node_in_cycle (ps
, u
, c
,
2198 &num_splits
, tmp_precede
,
2204 verify_partial_schedule (ps
, sched_nodes
);
2213 if (num_splits
>= MAX_SPLIT_NUM
)
2216 flush_and_start_over
= true;
2217 verify_partial_schedule (ps
, sched_nodes
);
2218 reset_partial_schedule (ps
, ii
);
2219 verify_partial_schedule (ps
, sched_nodes
);
2224 /* The scheduling window is exclusive of 'end'
2225 whereas compute_split_window() expects an inclusive,
2228 split_row
= compute_split_row (sched_nodes
, start
, end
- 1,
2231 split_row
= compute_split_row (sched_nodes
, end
+ 1, start
,
2234 ps_insert_empty_row (ps
, split_row
, sched_nodes
);
2235 i
--; /* Go back and retry node i. */
2238 fprintf (dump_file
, "num_splits=%d\n", num_splits
);
2241 /* ??? If (success), check register pressure estimates. */
2242 } /* Continue with next node. */
2243 } /* While flush_and_start_over. */
2246 free_partial_schedule (ps
);
2250 gcc_assert (bitmap_equal_p (tobe_scheduled
, sched_nodes
));
2255 /* This function inserts a new empty row into PS at the position
2256 according to SPLITROW, keeping all already scheduled instructions
2257 intact and updating their SCHED_TIME and cycle accordingly. */
2259 ps_insert_empty_row (partial_schedule_ptr ps
, int split_row
,
2260 sbitmap sched_nodes
)
2262 ps_insn_ptr crr_insn
;
2263 ps_insn_ptr
*rows_new
;
2265 int new_ii
= ii
+ 1;
2267 int *rows_length_new
;
2269 verify_partial_schedule (ps
, sched_nodes
);
2271 /* We normalize sched_time and rotate ps to have only non-negative sched
2272 times, for simplicity of updating cycles after inserting new row. */
2273 split_row
-= ps
->min_cycle
;
2274 split_row
= SMODULO (split_row
, ii
);
2276 fprintf (dump_file
, "split_row=%d\n", split_row
);
2278 reset_sched_times (ps
, PS_MIN_CYCLE (ps
));
2279 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
2281 rows_new
= (ps_insn_ptr
*) xcalloc (new_ii
, sizeof (ps_insn_ptr
));
2282 rows_length_new
= (int *) xcalloc (new_ii
, sizeof (int));
2283 for (row
= 0; row
< split_row
; row
++)
2285 rows_new
[row
] = ps
->rows
[row
];
2286 rows_length_new
[row
] = ps
->rows_length
[row
];
2287 ps
->rows
[row
] = NULL
;
2288 for (crr_insn
= rows_new
[row
];
2289 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2291 int u
= crr_insn
->id
;
2292 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
);
2294 SCHED_TIME (u
) = new_time
;
2295 crr_insn
->cycle
= new_time
;
2296 SCHED_ROW (u
) = new_time
% new_ii
;
2297 SCHED_STAGE (u
) = new_time
/ new_ii
;
2302 rows_new
[split_row
] = NULL
;
2304 for (row
= split_row
; row
< ii
; row
++)
2306 rows_new
[row
+ 1] = ps
->rows
[row
];
2307 rows_length_new
[row
+ 1] = ps
->rows_length
[row
];
2308 ps
->rows
[row
] = NULL
;
2309 for (crr_insn
= rows_new
[row
+ 1];
2310 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2312 int u
= crr_insn
->id
;
2313 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
) + 1;
2315 SCHED_TIME (u
) = new_time
;
2316 crr_insn
->cycle
= new_time
;
2317 SCHED_ROW (u
) = new_time
% new_ii
;
2318 SCHED_STAGE (u
) = new_time
/ new_ii
;
2323 ps
->min_cycle
= ps
->min_cycle
+ ps
->min_cycle
/ ii
2324 + (SMODULO (ps
->min_cycle
, ii
) >= split_row
? 1 : 0);
2325 ps
->max_cycle
= ps
->max_cycle
+ ps
->max_cycle
/ ii
2326 + (SMODULO (ps
->max_cycle
, ii
) >= split_row
? 1 : 0);
2328 ps
->rows
= rows_new
;
2329 free (ps
->rows_length
);
2330 ps
->rows_length
= rows_length_new
;
2332 gcc_assert (ps
->min_cycle
>= 0);
2334 verify_partial_schedule (ps
, sched_nodes
);
2337 fprintf (dump_file
, "min_cycle=%d, max_cycle=%d\n", ps
->min_cycle
,
2341 /* Given U_NODE which is the node that failed to be scheduled; LOW and
2342 UP which are the boundaries of it's scheduling window; compute using
2343 SCHED_NODES and II a row in the partial schedule that can be split
2344 which will separate a critical predecessor from a critical successor
2345 thereby expanding the window, and return it. */
2347 compute_split_row (sbitmap sched_nodes
, int low
, int up
, int ii
,
2348 ddg_node_ptr u_node
)
2351 int lower
= INT_MIN
, upper
= INT_MAX
;
2356 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2358 int v
= e
->src
->cuid
;
2360 if (bitmap_bit_p (sched_nodes
, v
)
2361 && (low
== SCHED_TIME (v
) + e
->latency
- (e
->distance
* ii
)))
2362 if (SCHED_TIME (v
) > lower
)
2365 lower
= SCHED_TIME (v
);
2371 crit_cycle
= SCHED_TIME (crit_pred
) + 1;
2372 return SMODULO (crit_cycle
, ii
);
2375 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2377 int v
= e
->dest
->cuid
;
2379 if (bitmap_bit_p (sched_nodes
, v
)
2380 && (up
== SCHED_TIME (v
) - e
->latency
+ (e
->distance
* ii
)))
2381 if (SCHED_TIME (v
) < upper
)
2384 upper
= SCHED_TIME (v
);
2390 crit_cycle
= SCHED_TIME (crit_succ
);
2391 return SMODULO (crit_cycle
, ii
);
2395 fprintf (dump_file
, "Both crit_pred and crit_succ are NULL\n");
2397 return SMODULO ((low
+ up
+ 1) / 2, ii
);
2401 verify_partial_schedule (partial_schedule_ptr ps
, sbitmap sched_nodes
)
2404 ps_insn_ptr crr_insn
;
2406 for (row
= 0; row
< ps
->ii
; row
++)
2410 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2412 int u
= crr_insn
->id
;
2415 gcc_assert (bitmap_bit_p (sched_nodes
, u
));
2416 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2417 popcount (sched_nodes) == number of insns in ps. */
2418 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
2419 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
2422 gcc_assert (ps
->rows_length
[row
] == length
);
2427 /* This page implements the algorithm for ordering the nodes of a DDG
2428 for modulo scheduling, activated through the
2429 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2431 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2432 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
2433 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
2434 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2435 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
2436 #define DEPTH(x) (ASAP ((x)))
2438 typedef struct node_order_params
* nopa
;
2440 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
2441 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
2442 static nopa
calculate_order_params (ddg_ptr
, int, int *);
2443 static int find_max_asap (ddg_ptr
, sbitmap
);
2444 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
2445 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
2447 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
2449 struct node_order_params
2456 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2458 check_nodes_order (int *node_order
, int num_nodes
)
2461 auto_sbitmap
tmp (num_nodes
);
2466 fprintf (dump_file
, "SMS final nodes order: \n");
2468 for (i
= 0; i
< num_nodes
; i
++)
2470 int u
= node_order
[i
];
2473 fprintf (dump_file
, "%d ", u
);
2474 gcc_assert (u
< num_nodes
&& u
>= 0 && !bitmap_bit_p (tmp
, u
));
2476 bitmap_set_bit (tmp
, u
);
2480 fprintf (dump_file
, "\n");
2483 /* Order the nodes of G for scheduling and pass the result in
2484 NODE_ORDER. Also set aux.count of each node to ASAP.
2485 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2487 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
, int *pmax_asap
)
2491 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
2493 nopa nops
= calculate_order_params (g
, mii
, pmax_asap
);
2496 print_sccs (dump_file
, sccs
, g
);
2498 order_nodes_of_sccs (sccs
, node_order
);
2500 if (sccs
->num_sccs
> 0)
2501 /* First SCC has the largest recurrence_length. */
2502 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
2504 /* Save ASAP before destroying node_order_params. */
2505 for (i
= 0; i
< g
->num_nodes
; i
++)
2507 ddg_node_ptr v
= &g
->nodes
[i
];
2508 v
->aux
.count
= ASAP (v
);
2512 free_ddg_all_sccs (sccs
);
2513 check_nodes_order (node_order
, g
->num_nodes
);
2519 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
2522 ddg_ptr g
= all_sccs
->ddg
;
2523 int num_nodes
= g
->num_nodes
;
2524 auto_sbitmap
prev_sccs (num_nodes
);
2525 auto_sbitmap
on_path (num_nodes
);
2526 auto_sbitmap
tmp (num_nodes
);
2527 auto_sbitmap
ones (num_nodes
);
2529 bitmap_clear (prev_sccs
);
2532 /* Perform the node ordering starting from the SCC with the highest recMII.
2533 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2534 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
2536 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
2538 /* Add nodes on paths from previous SCCs to the current SCC. */
2539 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
2540 bitmap_ior (tmp
, scc
->nodes
, on_path
);
2542 /* Add nodes on paths from the current SCC to previous SCCs. */
2543 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
2544 bitmap_ior (tmp
, tmp
, on_path
);
2546 /* Remove nodes of previous SCCs from current extended SCC. */
2547 bitmap_and_compl (tmp
, tmp
, prev_sccs
);
2549 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2550 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2553 /* Handle the remaining nodes that do not belong to any scc. Each call
2554 to order_nodes_in_scc handles a single connected component. */
2555 while (pos
< g
->num_nodes
)
2557 bitmap_and_compl (tmp
, ones
, prev_sccs
);
2558 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2562 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2563 static struct node_order_params
*
2564 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
, int *pmax_asap
)
2568 int num_nodes
= g
->num_nodes
;
2570 /* Allocate a place to hold ordering params for each node in the DDG. */
2571 nopa node_order_params_arr
;
2573 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2574 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
2575 sizeof (struct node_order_params
));
2577 /* Set the aux pointer of each node to point to its order_params structure. */
2578 for (u
= 0; u
< num_nodes
; u
++)
2579 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
2581 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2582 calculate ASAP, ALAP, mobility, distance, and height for each node
2583 in the dependence (direct acyclic) graph. */
2585 /* We assume that the nodes in the array are in topological order. */
2588 for (u
= 0; u
< num_nodes
; u
++)
2590 ddg_node_ptr u_node
= &g
->nodes
[u
];
2593 for (e
= u_node
->in
; e
; e
= e
->next_in
)
2594 if (e
->distance
== 0)
2595 ASAP (u_node
) = MAX (ASAP (u_node
),
2596 ASAP (e
->src
) + e
->latency
);
2597 max_asap
= MAX (max_asap
, ASAP (u_node
));
2600 for (u
= num_nodes
- 1; u
> -1; u
--)
2602 ddg_node_ptr u_node
= &g
->nodes
[u
];
2604 ALAP (u_node
) = max_asap
;
2605 HEIGHT (u_node
) = 0;
2606 for (e
= u_node
->out
; e
; e
= e
->next_out
)
2607 if (e
->distance
== 0)
2609 ALAP (u_node
) = MIN (ALAP (u_node
),
2610 ALAP (e
->dest
) - e
->latency
);
2611 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
2612 HEIGHT (e
->dest
) + e
->latency
);
2617 fprintf (dump_file
, "\nOrder params\n");
2618 for (u
= 0; u
< num_nodes
; u
++)
2620 ddg_node_ptr u_node
= &g
->nodes
[u
];
2622 fprintf (dump_file
, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u
,
2623 ASAP (u_node
), ALAP (u_node
), HEIGHT (u_node
));
2627 *pmax_asap
= max_asap
;
2628 return node_order_params_arr
;
2632 find_max_asap (ddg_ptr g
, sbitmap nodes
)
2637 sbitmap_iterator sbi
;
2639 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2641 ddg_node_ptr u_node
= &g
->nodes
[u
];
2643 if (max_asap
< ASAP (u_node
))
2645 max_asap
= ASAP (u_node
);
2653 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
2657 int min_mob
= INT_MAX
;
2659 sbitmap_iterator sbi
;
2661 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2663 ddg_node_ptr u_node
= &g
->nodes
[u
];
2665 if (max_hv
< HEIGHT (u_node
))
2667 max_hv
= HEIGHT (u_node
);
2668 min_mob
= MOB (u_node
);
2671 else if ((max_hv
== HEIGHT (u_node
))
2672 && (min_mob
> MOB (u_node
)))
2674 min_mob
= MOB (u_node
);
2682 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
2686 int min_mob
= INT_MAX
;
2688 sbitmap_iterator sbi
;
2690 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2692 ddg_node_ptr u_node
= &g
->nodes
[u
];
2694 if (max_dv
< DEPTH (u_node
))
2696 max_dv
= DEPTH (u_node
);
2697 min_mob
= MOB (u_node
);
2700 else if ((max_dv
== DEPTH (u_node
))
2701 && (min_mob
> MOB (u_node
)))
2703 min_mob
= MOB (u_node
);
2710 /* Places the nodes of SCC into the NODE_ORDER array starting
2711 at position POS, according to the SMS ordering algorithm.
2712 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2713 the NODE_ORDER array, starting from position zero. */
2715 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
2716 int * node_order
, int pos
)
2718 enum sms_direction dir
;
2719 int num_nodes
= g
->num_nodes
;
2720 auto_sbitmap
workset (num_nodes
);
2721 auto_sbitmap
tmp (num_nodes
);
2722 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
2723 auto_sbitmap
predecessors (num_nodes
);
2724 auto_sbitmap
successors (num_nodes
);
2726 bitmap_clear (predecessors
);
2727 find_predecessors (predecessors
, g
, nodes_ordered
);
2729 bitmap_clear (successors
);
2730 find_successors (successors
, g
, nodes_ordered
);
2733 if (bitmap_and (tmp
, predecessors
, scc
))
2735 bitmap_copy (workset
, tmp
);
2738 else if (bitmap_and (tmp
, successors
, scc
))
2740 bitmap_copy (workset
, tmp
);
2747 bitmap_clear (workset
);
2748 if ((u
= find_max_asap (g
, scc
)) >= 0)
2749 bitmap_set_bit (workset
, u
);
2753 bitmap_clear (zero_bitmap
);
2754 while (!bitmap_equal_p (workset
, zero_bitmap
))
2757 ddg_node_ptr v_node
;
2758 sbitmap v_node_preds
;
2759 sbitmap v_node_succs
;
2763 while (!bitmap_equal_p (workset
, zero_bitmap
))
2765 v
= find_max_hv_min_mob (g
, workset
);
2766 v_node
= &g
->nodes
[v
];
2767 node_order
[pos
++] = v
;
2768 v_node_succs
= NODE_SUCCESSORS (v_node
);
2769 bitmap_and (tmp
, v_node_succs
, scc
);
2771 /* Don't consider the already ordered successors again. */
2772 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2773 bitmap_ior (workset
, workset
, tmp
);
2774 bitmap_clear_bit (workset
, v
);
2775 bitmap_set_bit (nodes_ordered
, v
);
2778 bitmap_clear (predecessors
);
2779 find_predecessors (predecessors
, g
, nodes_ordered
);
2780 bitmap_and (workset
, predecessors
, scc
);
2784 while (!bitmap_equal_p (workset
, zero_bitmap
))
2786 v
= find_max_dv_min_mob (g
, workset
);
2787 v_node
= &g
->nodes
[v
];
2788 node_order
[pos
++] = v
;
2789 v_node_preds
= NODE_PREDECESSORS (v_node
);
2790 bitmap_and (tmp
, v_node_preds
, scc
);
2792 /* Don't consider the already ordered predecessors again. */
2793 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2794 bitmap_ior (workset
, workset
, tmp
);
2795 bitmap_clear_bit (workset
, v
);
2796 bitmap_set_bit (nodes_ordered
, v
);
2799 bitmap_clear (successors
);
2800 find_successors (successors
, g
, nodes_ordered
);
2801 bitmap_and (workset
, successors
, scc
);
2804 sbitmap_free (zero_bitmap
);
2809 /* This page contains functions for manipulating partial-schedules during
2810 modulo scheduling. */
2812 /* Create a partial schedule and allocate a memory to hold II rows. */
2814 static partial_schedule_ptr
2815 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2817 partial_schedule_ptr ps
= XNEW (struct partial_schedule
);
2818 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2819 ps
->rows_length
= (int *) xcalloc (ii
, sizeof (int));
2820 ps
->reg_moves
.create (0);
2822 ps
->history
= history
;
2823 ps
->min_cycle
= INT_MAX
;
2824 ps
->max_cycle
= INT_MIN
;
2830 /* Free the PS_INSNs in rows array of the given partial schedule.
2831 ??? Consider caching the PS_INSN's. */
2833 free_ps_insns (partial_schedule_ptr ps
)
2837 for (i
= 0; i
< ps
->ii
; i
++)
2841 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2844 ps
->rows
[i
] = ps_insn
;
2850 /* Free all the memory allocated to the partial schedule. */
2853 free_partial_schedule (partial_schedule_ptr ps
)
2855 ps_reg_move_info
*move
;
2861 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
2862 sbitmap_free (move
->uses
);
2863 ps
->reg_moves
.release ();
2867 free (ps
->rows_length
);
2871 /* Clear the rows array with its PS_INSNs, and create a new one with
2875 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2880 if (new_ii
== ps
->ii
)
2882 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2883 * sizeof (ps_insn_ptr
));
2884 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2885 ps
->rows_length
= (int *) xrealloc (ps
->rows_length
, new_ii
* sizeof (int));
2886 memset (ps
->rows_length
, 0, new_ii
* sizeof (int));
2888 ps
->min_cycle
= INT_MAX
;
2889 ps
->max_cycle
= INT_MIN
;
2892 /* Prints the partial schedule as an ii rows array, for each rows
2893 print the ids of the insns in it. */
2895 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2899 for (i
= 0; i
< ps
->ii
; i
++)
2901 ps_insn_ptr ps_i
= ps
->rows
[i
];
2903 fprintf (dump
, "\n[ROW %d ]: ", i
);
2906 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_i
->id
);
2909 fprintf (dump
, "%d (branch), ", INSN_UID (insn
));
2911 fprintf (dump
, "%d, ", INSN_UID (insn
));
2913 ps_i
= ps_i
->next_in_row
;
2918 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2920 create_ps_insn (int id
, int cycle
)
2922 ps_insn_ptr ps_i
= XNEW (struct ps_insn
);
2925 ps_i
->next_in_row
= NULL
;
2926 ps_i
->prev_in_row
= NULL
;
2927 ps_i
->cycle
= cycle
;
2933 /* Removes the given PS_INSN from the partial schedule. */
2935 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2939 gcc_assert (ps
&& ps_i
);
2941 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2942 if (! ps_i
->prev_in_row
)
2944 gcc_assert (ps_i
== ps
->rows
[row
]);
2945 ps
->rows
[row
] = ps_i
->next_in_row
;
2947 ps
->rows
[row
]->prev_in_row
= NULL
;
2951 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
2952 if (ps_i
->next_in_row
)
2953 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
2956 ps
->rows_length
[row
] -= 1;
2961 /* Unlike what literature describes for modulo scheduling (which focuses
2962 on VLIW machines) the order of the instructions inside a cycle is
2963 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2964 where the current instruction should go relative to the already
2965 scheduled instructions in the given cycle. Go over these
2966 instructions and find the first possible column to put it in. */
2968 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2969 sbitmap must_precede
, sbitmap must_follow
)
2971 ps_insn_ptr next_ps_i
;
2972 ps_insn_ptr first_must_follow
= NULL
;
2973 ps_insn_ptr last_must_precede
= NULL
;
2974 ps_insn_ptr last_in_row
= NULL
;
2980 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2982 /* Find the first must follow and the last must precede
2983 and insert the node immediately after the must precede
2984 but make sure that it there is no must follow after it. */
2985 for (next_ps_i
= ps
->rows
[row
];
2987 next_ps_i
= next_ps_i
->next_in_row
)
2990 && bitmap_bit_p (must_follow
, next_ps_i
->id
)
2991 && ! first_must_follow
)
2992 first_must_follow
= next_ps_i
;
2993 if (must_precede
&& bitmap_bit_p (must_precede
, next_ps_i
->id
))
2995 /* If we have already met a node that must follow, then
2996 there is no possible column. */
2997 if (first_must_follow
)
3000 last_must_precede
= next_ps_i
;
3002 /* The closing branch must be the last in the row. */
3003 if (JUMP_P (ps_rtl_insn (ps
, next_ps_i
->id
)))
3006 last_in_row
= next_ps_i
;
3009 /* The closing branch is scheduled as well. Make sure there is no
3010 dependent instruction after it as the branch should be the last
3011 instruction in the row. */
3012 if (JUMP_P (ps_rtl_insn (ps
, ps_i
->id
)))
3014 if (first_must_follow
)
3018 /* Make the branch the last in the row. New instructions
3019 will be inserted at the beginning of the row or after the
3020 last must_precede instruction thus the branch is guaranteed
3021 to remain the last instruction in the row. */
3022 last_in_row
->next_in_row
= ps_i
;
3023 ps_i
->prev_in_row
= last_in_row
;
3024 ps_i
->next_in_row
= NULL
;
3027 ps
->rows
[row
] = ps_i
;
3031 /* Now insert the node after INSERT_AFTER_PSI. */
3033 if (! last_must_precede
)
3035 ps_i
->next_in_row
= ps
->rows
[row
];
3036 ps_i
->prev_in_row
= NULL
;
3037 if (ps_i
->next_in_row
)
3038 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3039 ps
->rows
[row
] = ps_i
;
3043 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
3044 last_must_precede
->next_in_row
= ps_i
;
3045 ps_i
->prev_in_row
= last_must_precede
;
3046 if (ps_i
->next_in_row
)
3047 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3053 /* Advances the PS_INSN one column in its current row; returns false
3054 in failure and true in success. Bit N is set in MUST_FOLLOW if
3055 the node with cuid N must be come after the node pointed to by
3056 PS_I when scheduled in the same cycle. */
3058 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
3059 sbitmap must_follow
)
3061 ps_insn_ptr prev
, next
;
3067 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3069 if (! ps_i
->next_in_row
)
3072 /* Check if next_in_row is dependent on ps_i, both having same sched
3073 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
3074 if (must_follow
&& bitmap_bit_p (must_follow
, ps_i
->next_in_row
->id
))
3077 /* Advance PS_I over its next_in_row in the doubly linked list. */
3078 prev
= ps_i
->prev_in_row
;
3079 next
= ps_i
->next_in_row
;
3081 if (ps_i
== ps
->rows
[row
])
3082 ps
->rows
[row
] = next
;
3084 ps_i
->next_in_row
= next
->next_in_row
;
3086 if (next
->next_in_row
)
3087 next
->next_in_row
->prev_in_row
= ps_i
;
3089 next
->next_in_row
= ps_i
;
3090 ps_i
->prev_in_row
= next
;
3092 next
->prev_in_row
= prev
;
3094 prev
->next_in_row
= next
;
3099 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
3100 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
3101 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
3102 before/after (respectively) the node pointed to by PS_I when scheduled
3103 in the same cycle. */
3105 add_node_to_ps (partial_schedule_ptr ps
, int id
, int cycle
,
3106 sbitmap must_precede
, sbitmap must_follow
)
3109 int row
= SMODULO (cycle
, ps
->ii
);
3111 if (ps
->rows_length
[row
] >= issue_rate
)
3114 ps_i
= create_ps_insn (id
, cycle
);
3116 /* Finds and inserts PS_I according to MUST_FOLLOW and
3118 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
3124 ps
->rows_length
[row
] += 1;
3128 /* Advance time one cycle. Assumes DFA is being used. */
3130 advance_one_cycle (void)
3132 if (targetm
.sched
.dfa_pre_cycle_insn
)
3133 state_transition (curr_state
,
3134 targetm
.sched
.dfa_pre_cycle_insn ());
3136 state_transition (curr_state
, NULL
);
3138 if (targetm
.sched
.dfa_post_cycle_insn
)
3139 state_transition (curr_state
,
3140 targetm
.sched
.dfa_post_cycle_insn ());
3145 /* Checks if PS has resource conflicts according to DFA, starting from
3146 FROM cycle to TO cycle; returns true if there are conflicts and false
3147 if there are no conflicts. Assumes DFA is being used. */
3149 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
3153 state_reset (curr_state
);
3155 for (cycle
= from
; cycle
<= to
; cycle
++)
3157 ps_insn_ptr crr_insn
;
3158 /* Holds the remaining issue slots in the current row. */
3159 int can_issue_more
= issue_rate
;
3161 /* Walk through the DFA for the current row. */
3162 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
3164 crr_insn
= crr_insn
->next_in_row
)
3166 rtx_insn
*insn
= ps_rtl_insn (ps
, crr_insn
->id
);
3168 /* Check if there is room for the current insn. */
3169 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
3172 /* Update the DFA state and return with failure if the DFA found
3173 resource conflicts. */
3174 if (state_transition (curr_state
, insn
) >= 0)
3177 if (targetm
.sched
.variable_issue
)
3179 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
3180 insn
, can_issue_more
);
3181 /* A naked CLOBBER or USE generates no instruction, so don't
3182 let them consume issue slots. */
3183 else if (GET_CODE (PATTERN (insn
)) != USE
3184 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3188 /* Advance the DFA to the next cycle. */
3189 advance_one_cycle ();
3194 /* Checks if the given node causes resource conflicts when added to PS at
3195 cycle C. If not the node is added to PS and returned; otherwise zero
3196 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
3197 cuid N must be come before/after (respectively) the node pointed to by
3198 PS_I when scheduled in the same cycle. */
3200 ps_add_node_check_conflicts (partial_schedule_ptr ps
, int n
,
3201 int c
, sbitmap must_precede
,
3202 sbitmap must_follow
)
3204 int i
, first
, amount
, has_conflicts
= 0;
3207 /* First add the node to the PS, if this succeeds check for
3208 conflicts, trying different issue slots in the same row. */
3209 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
3210 return NULL
; /* Failed to insert the node at the given cycle. */
3214 has_conflicts
= ps_has_conflicts (ps
, c
, c
);
3215 if (ps
->history
> 0 && !has_conflicts
)
3217 /* Check all 2h+1 intervals, starting from c-2h..c up to c..2h,
3218 but not more than ii intervals. */
3219 first
= c
- ps
->history
;
3220 amount
= 2 * ps
->history
+ 1;
3221 if (amount
> ps
->ii
)
3223 for (i
= first
; i
< first
+ amount
; i
++)
3225 has_conflicts
= ps_has_conflicts (ps
,
3234 /* Try different issue slots to find one that the given node can be
3235 scheduled in without conflicts. */
3236 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
3242 remove_node_from_ps (ps
, ps_i
);
3246 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
3247 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
3251 /* Calculate the stage count of the partial schedule PS. The calculation
3252 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3254 calculate_stage_count (partial_schedule_ptr ps
, int rotation_amount
)
3256 int new_min_cycle
= PS_MIN_CYCLE (ps
) - rotation_amount
;
3257 int new_max_cycle
= PS_MAX_CYCLE (ps
) - rotation_amount
;
3258 int stage_count
= CALC_STAGE_COUNT (-1, new_min_cycle
, ps
->ii
);
3260 /* The calculation of stage count is done adding the number of stages
3261 before cycle zero and after cycle zero. */
3262 stage_count
+= CALC_STAGE_COUNT (new_max_cycle
, 0, ps
->ii
);
3267 /* Rotate the rows of PS such that insns scheduled at time
3268 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3270 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
3272 int i
, row
, backward_rotates
;
3273 int last_row
= ps
->ii
- 1;
3275 if (start_cycle
== 0)
3278 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
3280 /* Revisit later and optimize this into a single loop. */
3281 for (i
= 0; i
< backward_rotates
; i
++)
3283 ps_insn_ptr first_row
= ps
->rows
[0];
3284 int first_row_length
= ps
->rows_length
[0];
3286 for (row
= 0; row
< last_row
; row
++)
3288 ps
->rows
[row
] = ps
->rows
[row
+ 1];
3289 ps
->rows_length
[row
] = ps
->rows_length
[row
+ 1];
3292 ps
->rows
[last_row
] = first_row
;
3293 ps
->rows_length
[last_row
] = first_row_length
;
3296 ps
->max_cycle
-= start_cycle
;
3297 ps
->min_cycle
-= start_cycle
;
3300 #endif /* INSN_SCHEDULING */
3302 /* Run instruction scheduler. */
3303 /* Perform SMS module scheduling. */
3307 const pass_data pass_data_sms
=
3309 RTL_PASS
, /* type */
3311 OPTGROUP_NONE
, /* optinfo_flags */
3313 0, /* properties_required */
3314 0, /* properties_provided */
3315 0, /* properties_destroyed */
3316 0, /* todo_flags_start */
3317 TODO_df_finish
, /* todo_flags_finish */
3320 class pass_sms
: public rtl_opt_pass
3323 pass_sms (gcc::context
*ctxt
)
3324 : rtl_opt_pass (pass_data_sms
, ctxt
)
3327 /* opt_pass methods: */
3328 virtual bool gate (function
*)
3330 return (optimize
> 0 && flag_modulo_sched
);
3333 virtual unsigned int execute (function
*);
3335 }; // class pass_sms
3338 pass_sms::execute (function
*fun ATTRIBUTE_UNUSED
)
3340 #ifdef INSN_SCHEDULING
3343 /* Collect loop information to be used in SMS. */
3344 cfg_layout_initialize (0);
3347 /* Update the life information, because we add pseudos. */
3348 max_regno
= max_reg_num ();
3350 /* Finalize layout changes. */
3351 FOR_EACH_BB_FN (bb
, fun
)
3352 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3353 bb
->aux
= bb
->next_bb
;
3354 free_dominance_info (CDI_DOMINATORS
);
3355 cfg_layout_finalize ();
3356 #endif /* INSN_SCHEDULING */
3363 make_pass_sms (gcc::context
*ctxt
)
3365 return new pass_sms (ctxt
);