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"
46 #include "hard-reg-set.h"
48 #ifdef INSN_SCHEDULING
50 /* This file contains the implementation of the Swing Modulo Scheduler,
51 described in the following references:
52 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
53 Lifetime--sensitive modulo scheduling in a production environment.
54 IEEE Trans. on Comps., 50(3), March 2001
55 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
56 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
57 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
59 The basic structure is:
60 1. Build a data-dependence graph (DDG) for each loop.
61 2. Use the DDG to order the insns of a loop (not in topological order
62 necessarily, but rather) trying to place each insn after all its
63 predecessors _or_ after all its successors.
64 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
65 4. Use the ordering to perform list-scheduling of the loop:
66 1. Set II = MII. We will try to schedule the loop within II cycles.
67 2. Try to schedule the insns one by one according to the ordering.
68 For each insn compute an interval of cycles by considering already-
69 scheduled preds and succs (and associated latencies); try to place
70 the insn in the cycles of this window checking for potential
71 resource conflicts (using the DFA interface).
72 Note: this is different from the cycle-scheduling of schedule_insns;
73 here the insns are not scheduled monotonically top-down (nor bottom-
75 3. If failed in scheduling all insns - bump II++ and try again, unless
76 II reaches an upper bound MaxII, in which case report failure.
77 5. If we succeeded in scheduling the loop within II cycles, we now
78 generate prolog and epilog, decrease the counter of the loop, and
79 perform modulo variable expansion for live ranges that span more than
80 II cycles (i.e. use register copies to prevent a def from overwriting
81 itself before reaching the use).
83 SMS works with countable loops (1) whose control part can be easily
84 decoupled from the rest of the loop and (2) whose loop count can
85 be easily adjusted. This is because we peel a constant number of
86 iterations into a prologue and epilogue for which we want to avoid
87 emitting the control part, and a kernel which is to iterate that
88 constant number of iterations less than the original loop. So the
89 control part should be a set of insns clearly identified and having
90 its own iv, not otherwise used in the loop (at-least for now), which
91 initializes a register before the loop to the number of iterations.
92 Currently SMS relies on the do-loop pattern to recognize such loops,
93 where (1) the control part comprises of all insns defining and/or
94 using a certain 'count' register and (2) the loop count can be
95 adjusted by modifying this register prior to the loop.
96 TODO: Rely on cfgloop analysis instead. */
98 /* This page defines partial-schedule structures and functions for
101 typedef struct partial_schedule
*partial_schedule_ptr
;
102 typedef struct ps_insn
*ps_insn_ptr
;
104 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
105 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
107 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
108 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
110 /* Perform signed modulo, always returning a non-negative value. */
111 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
113 /* The number of different iterations the nodes in ps span, assuming
114 the stage boundaries are placed efficiently. */
115 #define CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \
117 /* The stage count of ps. */
118 #define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count)
120 /* A single instruction in the partial schedule. */
123 /* Identifies the instruction to be scheduled. Values smaller than
124 the ddg's num_nodes refer directly to ddg nodes. A value of
125 X - num_nodes refers to register move X. */
128 /* The (absolute) cycle in which the PS instruction is scheduled.
129 Same as SCHED_TIME (node). */
132 /* The next/prev PS_INSN in the same row. */
133 ps_insn_ptr next_in_row
,
138 /* Information about a register move that has been added to a partial
140 struct ps_reg_move_info
142 /* The source of the move is defined by the ps_insn with id DEF.
143 The destination is used by the ps_insns with the ids in USES. */
147 /* The original form of USES' instructions used OLD_REG, but they
148 should now use NEW_REG. */
152 /* The number of consecutive stages that the move occupies. */
153 int num_consecutive_stages
;
155 /* An instruction that sets NEW_REG to the correct value. The first
156 move associated with DEF will have an rhs of OLD_REG; later moves
157 use the result of the previous move. */
161 /* Holds the partial schedule as an array of II rows. Each entry of the
162 array points to a linked list of PS_INSNs, which represents the
163 instructions that are scheduled for that row. */
164 struct partial_schedule
166 int ii
; /* Number of rows in the partial schedule. */
167 int history
; /* Threshold for conflict checking using DFA. */
169 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
172 /* All the moves added for this partial schedule. Index X has
173 a ps_insn id of X + g->num_nodes. */
174 vec
<ps_reg_move_info
> reg_moves
;
176 /* rows_length[i] holds the number of instructions in the row.
177 It is used only (as an optimization) to back off quickly from
178 trying to schedule a node in a full row; that is, to avoid running
179 through futile DFA state transitions. */
182 /* The earliest absolute cycle of an insn in the partial schedule. */
185 /* The latest absolute cycle of an insn in the partial schedule. */
188 ddg_ptr g
; /* The DDG of the insns in the partial schedule. */
190 int stage_count
; /* The stage count of the partial schedule. */
194 static partial_schedule_ptr
create_partial_schedule (int ii
, ddg_ptr
, int history
);
195 static void free_partial_schedule (partial_schedule_ptr
);
196 static void reset_partial_schedule (partial_schedule_ptr
, int new_ii
);
197 void print_partial_schedule (partial_schedule_ptr
, FILE *);
198 static void verify_partial_schedule (partial_schedule_ptr
, sbitmap
);
199 static ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr
,
200 int, int, sbitmap
, sbitmap
);
201 static void rotate_partial_schedule (partial_schedule_ptr
, int);
202 void set_row_column_for_ps (partial_schedule_ptr
);
203 static void ps_insert_empty_row (partial_schedule_ptr
, int, sbitmap
);
204 static int compute_split_row (sbitmap
, int, int, int, ddg_node_ptr
);
207 /* This page defines constants and structures for the modulo scheduling
210 static int sms_order_nodes (ddg_ptr
, int, int *, int *);
211 static void set_node_sched_params (ddg_ptr
);
212 static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr
, int, int, int *);
213 static void permute_partial_schedule (partial_schedule_ptr
, rtx_insn
*);
214 static int calculate_stage_count (partial_schedule_ptr
, int);
215 static void calculate_must_precede_follow (ddg_node_ptr
, int, int,
216 int, int, sbitmap
, sbitmap
, sbitmap
);
217 static int get_sched_window (partial_schedule_ptr
, ddg_node_ptr
,
218 sbitmap
, int, int *, int *, int *);
219 static bool try_scheduling_node_in_cycle (partial_schedule_ptr
, int, int,
220 sbitmap
, int *, sbitmap
, sbitmap
);
221 static void remove_node_from_ps (partial_schedule_ptr
, ps_insn_ptr
);
223 #define NODE_ASAP(node) ((node)->aux.count)
225 #define SCHED_PARAMS(x) (&node_sched_param_vec[x])
226 #define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
227 #define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
228 #define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
229 #define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
231 /* The scheduling parameters held for each node. */
232 typedef struct node_sched_params
234 int time
; /* The absolute scheduling cycle. */
236 int row
; /* Holds time % ii. */
237 int stage
; /* Holds time / ii. */
239 /* The column of a node inside the ps. If nodes u, v are on the same row,
240 u will precede v if column (u) < column (v). */
242 } *node_sched_params_ptr
;
244 /* The following three functions are copied from the current scheduler
245 code in order to use sched_analyze() for computing the dependencies.
246 They are used when initializing the sched_info structure. */
248 sms_print_insn (const rtx_insn
*insn
, int aligned ATTRIBUTE_UNUSED
)
252 sprintf (tmp
, "i%4d", INSN_UID (insn
));
257 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
258 regset used ATTRIBUTE_UNUSED
)
262 static struct common_sched_info_def sms_common_sched_info
;
264 static struct sched_deps_info_def sms_sched_deps_info
=
266 compute_jump_reg_dependencies
,
267 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
272 static struct haifa_sched_info sms_sched_info
=
281 NULL
, /* insn_finishes_block_p */
286 NULL
, NULL
, NULL
, NULL
,
291 /* Partial schedule instruction ID in PS is a register move. Return
292 information about it. */
293 static struct ps_reg_move_info
*
294 ps_reg_move (partial_schedule_ptr ps
, int id
)
296 gcc_checking_assert (id
>= ps
->g
->num_nodes
);
297 return &ps
->reg_moves
[id
- ps
->g
->num_nodes
];
300 /* Return the rtl instruction that is being scheduled by partial schedule
301 instruction ID, which belongs to schedule PS. */
303 ps_rtl_insn (partial_schedule_ptr ps
, int id
)
305 if (id
< ps
->g
->num_nodes
)
306 return ps
->g
->nodes
[id
].insn
;
308 return ps_reg_move (ps
, id
)->insn
;
311 /* Partial schedule instruction ID, which belongs to PS, occurred in
312 the original (unscheduled) loop. Return the first instruction
313 in the loop that was associated with ps_rtl_insn (PS, ID).
314 If the instruction had some notes before it, this is the first
317 ps_first_note (partial_schedule_ptr ps
, int id
)
319 gcc_assert (id
< ps
->g
->num_nodes
);
320 return ps
->g
->nodes
[id
].first_note
;
323 /* Return the number of consecutive stages that are occupied by
324 partial schedule instruction ID in PS. */
326 ps_num_consecutive_stages (partial_schedule_ptr ps
, int id
)
328 if (id
< ps
->g
->num_nodes
)
331 return ps_reg_move (ps
, id
)->num_consecutive_stages
;
334 /* Given HEAD and TAIL which are the first and last insns in a loop;
335 return the register which controls the loop. Return zero if it has
336 more than one occurrence in the loop besides the control part or the
337 do-loop pattern is not of the form we expect. */
339 doloop_register_get (rtx_insn
*head
, rtx_insn
*tail
)
342 rtx_insn
*insn
, *first_insn_not_to_check
;
347 if (!targetm
.code_for_doloop_end
)
350 /* TODO: Free SMS's dependence on doloop_condition_get. */
351 condition
= doloop_condition_get (tail
);
355 if (REG_P (XEXP (condition
, 0)))
356 reg
= XEXP (condition
, 0);
357 else if (GET_CODE (XEXP (condition
, 0)) == PLUS
358 && REG_P (XEXP (XEXP (condition
, 0), 0)))
359 reg
= XEXP (XEXP (condition
, 0), 0);
363 /* Check that the COUNT_REG has no other occurrences in the loop
364 until the decrement. We assume the control part consists of
365 either a single (parallel) branch-on-count or a (non-parallel)
366 branch immediately preceded by a single (decrement) insn. */
367 first_insn_not_to_check
= (GET_CODE (PATTERN (tail
)) == PARALLEL
? tail
368 : prev_nondebug_insn (tail
));
370 for (insn
= head
; insn
!= first_insn_not_to_check
; insn
= NEXT_INSN (insn
))
371 if (NONDEBUG_INSN_P (insn
) && reg_mentioned_p (reg
, insn
))
375 fprintf (dump_file
, "SMS count_reg found ");
376 print_rtl_single (dump_file
, reg
);
377 fprintf (dump_file
, " outside control in insn:\n");
378 print_rtl_single (dump_file
, insn
);
387 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
388 that the number of iterations is a compile-time constant. If so,
389 return the rtx_insn that sets COUNT_REG to a constant, and set COUNT to
390 this constant. Otherwise return 0. */
392 const_iteration_count (rtx count_reg
, basic_block pre_header
,
393 int64_t *count
, bool* adjust_inplace
)
396 rtx_insn
*head
, *tail
;
398 *adjust_inplace
= false;
399 bool read_after
= false;
404 get_ebb_head_tail (pre_header
, pre_header
, &head
, &tail
);
406 for (insn
= tail
; insn
!= PREV_INSN (head
); insn
= PREV_INSN (insn
))
407 if (single_set (insn
) && rtx_equal_p (count_reg
,
408 SET_DEST (single_set (insn
))))
410 rtx pat
= single_set (insn
);
412 if (CONST_INT_P (SET_SRC (pat
)))
414 *count
= INTVAL (SET_SRC (pat
));
415 *adjust_inplace
= !read_after
;
421 else if (NONDEBUG_INSN_P (insn
) && reg_mentioned_p (count_reg
, insn
))
424 if (reg_set_p (count_reg
, insn
))
431 /* A very simple resource-based lower bound on the initiation interval.
432 ??? Improve the accuracy of this bound by considering the
433 utilization of various units. */
437 if (targetm
.sched
.sms_res_mii
)
438 return targetm
.sched
.sms_res_mii (g
);
440 return g
->num_nodes
/ issue_rate
;
444 /* A vector that contains the sched data for each ps_insn. */
445 static vec
<node_sched_params
> node_sched_param_vec
;
447 /* Allocate sched_params for each node and initialize it. */
449 set_node_sched_params (ddg_ptr g
)
451 node_sched_param_vec
.truncate (0);
452 node_sched_param_vec
.safe_grow_cleared (g
->num_nodes
, true);
455 /* Make sure that node_sched_param_vec has an entry for every move in PS. */
457 extend_node_sched_params (partial_schedule_ptr ps
)
459 node_sched_param_vec
.safe_grow_cleared (ps
->g
->num_nodes
460 + ps
->reg_moves
.length (), true);
463 /* Update the sched_params (time, row and stage) for node U using the II,
464 the CYCLE of U and MIN_CYCLE.
465 We're not simply taking the following
466 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
467 because the stages may not be aligned on cycle 0. */
469 update_node_sched_params (int u
, int ii
, int cycle
, int min_cycle
)
471 int sc_until_cycle_zero
;
474 SCHED_TIME (u
) = cycle
;
475 SCHED_ROW (u
) = SMODULO (cycle
, ii
);
477 /* The calculation of stage count is done adding the number
478 of stages before cycle zero and after cycle zero. */
479 sc_until_cycle_zero
= CALC_STAGE_COUNT (-1, min_cycle
, ii
);
481 if (SCHED_TIME (u
) < 0)
483 stage
= CALC_STAGE_COUNT (-1, SCHED_TIME (u
), ii
);
484 SCHED_STAGE (u
) = sc_until_cycle_zero
- stage
;
488 stage
= CALC_STAGE_COUNT (SCHED_TIME (u
), 0, ii
);
489 SCHED_STAGE (u
) = sc_until_cycle_zero
+ stage
- 1;
494 print_node_sched_params (FILE *file
, int num_nodes
, partial_schedule_ptr ps
)
500 for (i
= 0; i
< num_nodes
; i
++)
502 node_sched_params_ptr nsp
= SCHED_PARAMS (i
);
504 fprintf (file
, "Node = %d; INSN = %d\n", i
,
505 INSN_UID (ps_rtl_insn (ps
, i
)));
506 fprintf (file
, " asap = %d:\n", NODE_ASAP (&ps
->g
->nodes
[i
]));
507 fprintf (file
, " time = %d:\n", nsp
->time
);
508 fprintf (file
, " stage = %d:\n", nsp
->stage
);
512 /* Set SCHED_COLUMN for each instruction in row ROW of PS. */
514 set_columns_for_row (partial_schedule_ptr ps
, int row
)
516 ps_insn_ptr cur_insn
;
520 for (cur_insn
= ps
->rows
[row
]; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
521 SCHED_COLUMN (cur_insn
->id
) = column
++;
524 /* Set SCHED_COLUMN for each instruction in PS. */
526 set_columns_for_ps (partial_schedule_ptr ps
)
530 for (row
= 0; row
< ps
->ii
; row
++)
531 set_columns_for_row (ps
, row
);
534 /* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
535 Its single predecessor has already been scheduled, as has its
536 ddg node successors. (The move may have also another move as its
537 successor, in which case that successor will be scheduled later.)
539 The move is part of a chain that satisfies register dependencies
540 between a producing ddg node and various consuming ddg nodes.
541 If some of these dependencies have a distance of 1 (meaning that
542 the use is upward-exposed) then DISTANCE1_USES is nonnull and
543 contains the set of uses with distance-1 dependencies.
544 DISTANCE1_USES is null otherwise.
546 MUST_FOLLOW is a scratch bitmap that is big enough to hold
547 all current ps_insn ids.
549 Return true on success. */
551 schedule_reg_move (partial_schedule_ptr ps
, int i_reg_move
,
552 sbitmap distance1_uses
, sbitmap must_follow
)
555 int this_time
, this_distance
, this_start
, this_end
, this_latency
;
556 int start
, end
, c
, ii
;
557 sbitmap_iterator sbi
;
558 ps_reg_move_info
*move
;
562 move
= ps_reg_move (ps
, i_reg_move
);
566 fprintf (dump_file
, "Scheduling register move INSN %d; ii = %d"
567 ", min cycle = %d\n\n", INSN_UID (move
->insn
), ii
,
569 print_rtl_single (dump_file
, move
->insn
);
570 fprintf (dump_file
, "\n%11s %11s %5s\n", "start", "end", "time");
571 fprintf (dump_file
, "=========== =========== =====\n");
577 /* For dependencies of distance 1 between a producer ddg node A
578 and consumer ddg node B, we have a chain of dependencies:
580 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
582 where Mi is the ith move. For dependencies of distance 0 between
583 a producer ddg node A and consumer ddg node C, we have a chain of
586 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
588 where Mi' occupies the same position as Mi but occurs a stage later.
589 We can only schedule each move once, so if we have both types of
590 chain, we model the second as:
592 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
594 First handle the dependencies between the previously-scheduled
595 predecessor and the move. */
596 this_insn
= ps_rtl_insn (ps
, move
->def
);
597 this_latency
= insn_latency (this_insn
, move
->insn
);
598 this_distance
= distance1_uses
&& move
->def
< ps
->g
->num_nodes
? 1 : 0;
599 this_time
= SCHED_TIME (move
->def
) - this_distance
* ii
;
600 this_start
= this_time
+ this_latency
;
601 this_end
= this_time
+ ii
;
603 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
604 this_start
, this_end
, SCHED_TIME (move
->def
),
605 INSN_UID (this_insn
), this_latency
, this_distance
,
606 INSN_UID (move
->insn
));
608 if (start
< this_start
)
613 /* Handle the dependencies between the move and previously-scheduled
615 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, u
, sbi
)
617 this_insn
= ps_rtl_insn (ps
, u
);
618 this_latency
= insn_latency (move
->insn
, this_insn
);
619 if (distance1_uses
&& !bitmap_bit_p (distance1_uses
, u
))
623 this_time
= SCHED_TIME (u
) + this_distance
* ii
;
624 this_start
= this_time
- ii
;
625 this_end
= this_time
- this_latency
;
627 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
628 this_start
, this_end
, SCHED_TIME (u
), INSN_UID (move
->insn
),
629 this_latency
, this_distance
, INSN_UID (this_insn
));
631 if (start
< this_start
)
639 fprintf (dump_file
, "----------- ----------- -----\n");
640 fprintf (dump_file
, "%11d %11d %5s %s\n", start
, end
, "", "(max, min)");
643 bitmap_clear (must_follow
);
644 bitmap_set_bit (must_follow
, move
->def
);
646 start
= MAX (start
, end
- (ii
- 1));
647 for (c
= end
; c
>= start
; c
--)
649 psi
= ps_add_node_check_conflicts (ps
, i_reg_move
, c
,
650 move
->uses
, must_follow
);
653 update_node_sched_params (i_reg_move
, ii
, c
, PS_MIN_CYCLE (ps
));
655 fprintf (dump_file
, "\nScheduled register move INSN %d at"
656 " time %d, row %d\n\n", INSN_UID (move
->insn
), c
,
657 SCHED_ROW (i_reg_move
));
663 fprintf (dump_file
, "\nNo available slot\n\n");
669 Breaking intra-loop register anti-dependences:
670 Each intra-loop register anti-dependence implies a cross-iteration true
671 dependence of distance 1. Therefore, we can remove such false dependencies
672 and figure out if the partial schedule broke them by checking if (for a
673 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
674 if so generate a register move. The number of such moves is equal to:
675 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
676 nreg_moves = ----------------------------------- + 1 - { dependence.
680 schedule_reg_moves (partial_schedule_ptr ps
)
686 for (i
= 0; i
< g
->num_nodes
; i
++)
688 ddg_node_ptr u
= &g
->nodes
[i
];
690 int nreg_moves
= 0, i_reg_move
;
691 rtx prev_reg
, old_reg
;
694 sbitmap distance1_uses
;
695 rtx set
= single_set (u
->insn
);
697 /* Skip instructions that do not set a register. */
698 if (set
&& !REG_P (SET_DEST (set
)))
701 /* Compute the number of reg_moves needed for u, by looking at life
702 ranges started at u (excluding self-loops). */
703 distances
[0] = distances
[1] = false;
704 for (e
= u
->out
; e
; e
= e
->next_out
)
705 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
707 int nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
708 - SCHED_TIME (e
->src
->cuid
)) / ii
;
710 if (e
->distance
== 1)
711 nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
712 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
714 /* If dest precedes src in the schedule of the kernel, then dest
715 will read before src writes and we can save one reg_copy. */
716 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
717 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
720 if (nreg_moves4e
>= 1)
722 /* !single_set instructions are not supported yet and
723 thus we do not except to encounter them in the loop
724 except from the doloop part. For the latter case
725 we assume no regmoves are generated as the doloop
726 instructions are tied to the branch with an edge. */
728 /* If the instruction contains auto-inc register then
729 validate that the regmov is being generated for the
730 target regsiter rather then the inc'ed register. */
731 gcc_assert (!autoinc_var_is_used_p (u
->insn
, e
->dest
->insn
));
736 gcc_assert (e
->distance
< 2);
737 distances
[e
->distance
] = true;
739 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
745 /* Create NREG_MOVES register moves. */
746 first_move
= ps
->reg_moves
.length ();
747 ps
->reg_moves
.safe_grow_cleared (first_move
+ nreg_moves
, true);
748 extend_node_sched_params (ps
);
750 /* Record the moves associated with this node. */
751 first_move
+= ps
->g
->num_nodes
;
753 /* Generate each move. */
754 old_reg
= prev_reg
= SET_DEST (set
);
755 if (HARD_REGISTER_P (old_reg
))
758 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
760 ps_reg_move_info
*move
= ps_reg_move (ps
, first_move
+ i_reg_move
);
762 move
->def
= i_reg_move
> 0 ? first_move
+ i_reg_move
- 1 : i
;
763 move
->uses
= sbitmap_alloc (first_move
+ nreg_moves
);
764 move
->old_reg
= old_reg
;
765 move
->new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
766 move
->num_consecutive_stages
= distances
[0] && distances
[1] ? 2 : 1;
767 move
->insn
= gen_move_insn (move
->new_reg
, copy_rtx (prev_reg
));
768 bitmap_clear (move
->uses
);
770 prev_reg
= move
->new_reg
;
773 distance1_uses
= distances
[1] ? sbitmap_alloc (g
->num_nodes
) : NULL
;
776 bitmap_clear (distance1_uses
);
778 /* Every use of the register defined by node may require a different
779 copy of this register, depending on the time the use is scheduled.
780 Record which uses require which move results. */
781 for (e
= u
->out
; e
; e
= e
->next_out
)
782 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
784 int dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
785 - SCHED_TIME (e
->src
->cuid
)) / ii
;
787 if (e
->distance
== 1)
788 dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
789 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
791 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
792 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
797 ps_reg_move_info
*move
;
799 move
= ps_reg_move (ps
, first_move
+ dest_copy
- 1);
800 bitmap_set_bit (move
->uses
, e
->dest
->cuid
);
801 if (e
->distance
== 1)
802 bitmap_set_bit (distance1_uses
, e
->dest
->cuid
);
806 auto_sbitmap
must_follow (first_move
+ nreg_moves
);
807 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
808 if (!schedule_reg_move (ps
, first_move
+ i_reg_move
,
809 distance1_uses
, must_follow
))
812 sbitmap_free (distance1_uses
);
813 if (i_reg_move
< nreg_moves
)
819 /* Emit the moves associated with PS. Apply the substitutions
820 associated with them. */
822 apply_reg_moves (partial_schedule_ptr ps
)
824 ps_reg_move_info
*move
;
827 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
830 sbitmap_iterator sbi
;
832 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, i_use
, sbi
)
834 replace_rtx (ps
->g
->nodes
[i_use
].insn
, move
->old_reg
, move
->new_reg
);
835 df_insn_rescan (ps
->g
->nodes
[i_use
].insn
);
840 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
841 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
842 will move to cycle zero. */
844 reset_sched_times (partial_schedule_ptr ps
, int amount
)
848 ps_insn_ptr crr_insn
;
850 for (row
= 0; row
< ii
; row
++)
851 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
853 int u
= crr_insn
->id
;
854 int normalized_time
= SCHED_TIME (u
) - amount
;
855 int new_min_cycle
= PS_MIN_CYCLE (ps
) - amount
;
859 /* Print the scheduling times after the rotation. */
860 rtx_insn
*insn
= ps_rtl_insn (ps
, u
);
862 fprintf (dump_file
, "crr_insn->node=%d (insn id %d), "
863 "crr_insn->cycle=%d, min_cycle=%d", u
,
864 INSN_UID (insn
), normalized_time
, new_min_cycle
);
866 fprintf (dump_file
, " (branch)");
867 fprintf (dump_file
, "\n");
870 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
871 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
873 crr_insn
->cycle
= normalized_time
;
874 update_node_sched_params (u
, ii
, normalized_time
, new_min_cycle
);
878 /* Permute the insns according to their order in PS, from row 0 to
879 row ii-1, and position them right before LAST. This schedules
880 the insns of the loop kernel. */
882 permute_partial_schedule (partial_schedule_ptr ps
, rtx_insn
*last
)
888 for (row
= 0; row
< ii
; row
++)
889 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
891 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_ij
->id
);
893 if (PREV_INSN (last
) != insn
)
895 if (ps_ij
->id
< ps
->g
->num_nodes
)
896 reorder_insns_nobb (ps_first_note (ps
, ps_ij
->id
), insn
,
899 add_insn_before (insn
, last
, NULL
);
904 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
905 respectively only if cycle C falls on the border of the scheduling
906 window boundaries marked by START and END cycles. STEP is the
907 direction of the window. */
909 set_must_precede_follow (sbitmap
*tmp_follow
, sbitmap must_follow
,
910 sbitmap
*tmp_precede
, sbitmap must_precede
, int c
,
911 int start
, int end
, int step
)
919 *tmp_precede
= must_precede
;
920 else /* step == -1. */
921 *tmp_follow
= must_follow
;
926 *tmp_follow
= must_follow
;
927 else /* step == -1. */
928 *tmp_precede
= must_precede
;
933 /* Return True if the branch can be moved to row ii-1 while
934 normalizing the partial schedule PS to start from cycle zero and thus
935 optimize the SC. Otherwise return False. */
937 optimize_sc (partial_schedule_ptr ps
, ddg_ptr g
)
939 int amount
= PS_MIN_CYCLE (ps
);
940 int start
, end
, step
;
943 int stage_count
, stage_count_curr
;
945 /* Compare the SC after normalization and SC after bringing the branch
946 to row ii-1. If they are equal just bail out. */
947 stage_count
= calculate_stage_count (ps
, amount
);
949 calculate_stage_count (ps
, SCHED_TIME (g
->closing_branch
->cuid
) - (ii
- 1));
951 if (stage_count
== stage_count_curr
)
954 fprintf (dump_file
, "SMS SC already optimized.\n");
961 fprintf (dump_file
, "SMS Trying to optimize branch location\n");
962 fprintf (dump_file
, "SMS partial schedule before trial:\n");
963 print_partial_schedule (ps
, dump_file
);
966 /* First, normalize the partial scheduling. */
967 reset_sched_times (ps
, amount
);
968 rotate_partial_schedule (ps
, amount
);
972 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
974 print_partial_schedule (ps
, dump_file
);
977 if (SMODULO (SCHED_TIME (g
->closing_branch
->cuid
), ii
) == ii
- 1)
980 auto_sbitmap
sched_nodes (g
->num_nodes
);
981 bitmap_ones (sched_nodes
);
983 /* Calculate the new placement of the branch. It should be in row
984 ii-1 and fall into it's scheduling window. */
985 if (get_sched_window (ps
, g
->closing_branch
, sched_nodes
, ii
, &start
,
989 ps_insn_ptr next_ps_i
;
990 int branch_cycle
= SCHED_TIME (g
->closing_branch
->cuid
);
991 int row
= SMODULO (branch_cycle
, ps
->ii
);
993 sbitmap tmp_precede
, tmp_follow
;
997 fprintf (dump_file
, "\nTrying to schedule node %d "
998 "INSN = %d in (%d .. %d) step %d\n",
999 g
->closing_branch
->cuid
,
1000 (INSN_UID (g
->closing_branch
->insn
)), start
, end
, step
);
1002 gcc_assert ((step
> 0 && start
< end
) || (step
< 0 && start
> end
));
1005 c
= start
+ ii
- SMODULO (start
, ii
) - 1;
1006 gcc_assert (c
>= start
);
1011 "SMS failed to schedule branch at cycle: %d\n", c
);
1017 c
= start
- SMODULO (start
, ii
) - 1;
1018 gcc_assert (c
<= start
);
1024 "SMS failed to schedule branch at cycle: %d\n", c
);
1029 auto_sbitmap
must_precede (g
->num_nodes
);
1030 auto_sbitmap
must_follow (g
->num_nodes
);
1032 /* Try to schedule the branch is it's new cycle. */
1033 calculate_must_precede_follow (g
->closing_branch
, start
, end
,
1034 step
, ii
, sched_nodes
,
1035 must_precede
, must_follow
);
1037 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1038 must_precede
, c
, start
, end
, step
);
1040 /* Find the element in the partial schedule related to the closing
1041 branch so we can remove it from it's current cycle. */
1042 for (next_ps_i
= ps
->rows
[row
];
1043 next_ps_i
; next_ps_i
= next_ps_i
->next_in_row
)
1044 if (next_ps_i
->id
== g
->closing_branch
->cuid
)
1047 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1048 remove_node_from_ps (ps
, next_ps_i
);
1050 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
, c
,
1051 sched_nodes
, &num_splits
,
1052 tmp_precede
, tmp_follow
);
1053 gcc_assert (num_splits
== 0);
1058 "SMS failed to schedule branch at cycle: %d, "
1059 "bringing it back to cycle %d\n", c
, branch_cycle
);
1061 /* The branch was failed to be placed in row ii - 1.
1062 Put it back in it's original place in the partial
1064 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1065 must_precede
, branch_cycle
, start
, end
,
1068 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
,
1069 branch_cycle
, sched_nodes
,
1070 &num_splits
, tmp_precede
,
1072 gcc_assert (success
&& (num_splits
== 0));
1077 /* The branch is placed in row ii - 1. */
1080 "SMS success in moving branch to cycle %d\n", c
);
1082 update_node_sched_params (g
->closing_branch
->cuid
, ii
, c
,
1087 /* This might have been added to a new first stage. */
1088 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1089 reset_sched_times (ps
, 0);
1096 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
1097 int to_stage
, rtx count_reg
, class loop
*loop
)
1103 for (row
= 0; row
< ps
->ii
; row
++)
1104 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
1107 int first_u
, last_u
;
1110 /* Do not duplicate any insn which refers to count_reg as it
1111 belongs to the control part.
1112 The closing branch is scheduled as well and thus should
1114 TODO: This should be done by analyzing the control part of
1116 u_insn
= ps_rtl_insn (ps
, u
);
1117 if (reg_mentioned_p (count_reg
, u_insn
)
1121 first_u
= SCHED_STAGE (u
);
1122 last_u
= first_u
+ ps_num_consecutive_stages (ps
, u
) - 1;
1123 if (from_stage
<= last_u
&& to_stage
>= first_u
)
1125 if (u
< ps
->g
->num_nodes
)
1126 duplicate_insn_chain (ps_first_note (ps
, u
), u_insn
,
1129 emit_insn (copy_rtx (PATTERN (u_insn
)));
1135 /* Generate the instructions (including reg_moves) for prolog & epilog. */
1137 generate_prolog_epilog (partial_schedule_ptr ps
, class loop
*loop
,
1138 rtx count_reg
, bool adjust_init
)
1141 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
1144 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1149 /* Generate instructions at the beginning of the prolog to
1150 adjust the loop count by STAGE_COUNT. If loop count is constant
1151 and it not used anywhere in prologue, this constant is adjusted by
1152 STAGE_COUNT outside of generate_prolog_epilog function. */
1153 rtx sub_reg
= NULL_RTX
;
1155 sub_reg
= expand_simple_binop (GET_MODE (count_reg
), MINUS
, count_reg
,
1156 gen_int_mode (last_stage
,
1157 GET_MODE (count_reg
)),
1158 count_reg
, 1, OPTAB_DIRECT
);
1159 gcc_assert (REG_P (sub_reg
));
1160 if (REGNO (sub_reg
) != REGNO (count_reg
))
1161 emit_move_insn (count_reg
, sub_reg
);
1164 for (i
= 0; i
< last_stage
; i
++)
1165 duplicate_insns_of_cycles (ps
, 0, i
, count_reg
, loop
);
1167 /* Put the prolog on the entry edge. */
1168 e
= loop_preheader_edge (loop
);
1169 split_edge_and_insert (e
, get_insns ());
1170 if (!flag_resched_modulo_sched
)
1171 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1175 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1178 for (i
= 0; i
< last_stage
; i
++)
1179 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, count_reg
, loop
);
1181 /* Put the epilogue on the exit edge. */
1182 gcc_assert (single_exit (loop
));
1183 e
= single_exit (loop
);
1184 split_edge_and_insert (e
, get_insns ());
1185 if (!flag_resched_modulo_sched
)
1186 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1191 /* Mark LOOP as software pipelined so the later
1192 scheduling passes don't touch it. */
1194 mark_loop_unsched (class loop
*loop
)
1197 basic_block
*bbs
= get_loop_body (loop
);
1199 for (i
= 0; i
< loop
->num_nodes
; i
++)
1200 bbs
[i
]->flags
|= BB_DISABLE_SCHEDULE
;
1205 /* Return true if all the BBs of the loop are empty except the
1208 loop_single_full_bb_p (class loop
*loop
)
1211 basic_block
*bbs
= get_loop_body (loop
);
1213 for (i
= 0; i
< loop
->num_nodes
; i
++)
1215 rtx_insn
*head
, *tail
;
1216 bool empty_bb
= true;
1218 if (bbs
[i
] == loop
->header
)
1221 /* Make sure that basic blocks other than the header
1222 have only notes labels or jumps. */
1223 get_ebb_head_tail (bbs
[i
], bbs
[i
], &head
, &tail
);
1224 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
1226 if (NOTE_P (head
) || LABEL_P (head
)
1227 || (INSN_P (head
) && (DEBUG_INSN_P (head
) || JUMP_P (head
))))
1243 /* Dump file:line from INSN's location info to dump_file. */
1246 dump_insn_location (rtx_insn
*insn
)
1248 if (dump_file
&& INSN_HAS_LOCATION (insn
))
1250 expanded_location xloc
= insn_location (insn
);
1251 fprintf (dump_file
, " %s:%i", xloc
.file
, xloc
.line
);
1255 /* A simple loop from SMS point of view; it is a loop that is composed of
1256 either a single basic block or two BBs - a header and a latch. */
1257 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1258 && (EDGE_COUNT (loop->latch->preds) == 1) \
1259 && (EDGE_COUNT (loop->latch->succs) == 1))
1261 /* Return true if the loop is in its canonical form and false if not.
1262 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1264 loop_canon_p (class loop
*loop
)
1267 if (loop
->inner
|| !loop_outer (loop
))
1270 fprintf (dump_file
, "SMS loop inner or !loop_outer\n");
1274 if (!single_exit (loop
))
1278 rtx_insn
*insn
= BB_END (loop
->header
);
1280 fprintf (dump_file
, "SMS loop many exits");
1281 dump_insn_location (insn
);
1282 fprintf (dump_file
, "\n");
1287 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
1291 rtx_insn
*insn
= BB_END (loop
->header
);
1293 fprintf (dump_file
, "SMS loop many BBs.");
1294 dump_insn_location (insn
);
1295 fprintf (dump_file
, "\n");
1303 /* If there are more than one entry for the loop,
1304 make it one by splitting the first entry edge and
1305 redirecting the others to the new BB. */
1307 canon_loop (class loop
*loop
)
1312 /* Avoid annoying special cases of edges going to exit
1314 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1315 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
1318 if (loop
->latch
== loop
->header
1319 || EDGE_COUNT (loop
->latch
->succs
) > 1)
1321 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
1322 if (e
->src
== loop
->latch
)
1330 setup_sched_infos (void)
1332 memcpy (&sms_common_sched_info
, &haifa_common_sched_info
,
1333 sizeof (sms_common_sched_info
));
1334 sms_common_sched_info
.sched_pass_id
= SCHED_SMS_PASS
;
1335 common_sched_info
= &sms_common_sched_info
;
1337 sched_deps_info
= &sms_sched_deps_info
;
1338 current_sched_info
= &sms_sched_info
;
1341 /* Probability in % that the sms-ed loop rolls enough so that optimized
1342 version may be entered. Just a guess. */
1343 #define PROB_SMS_ENOUGH_ITERATIONS 80
1345 /* Main entry point, perform SMS scheduling on the loops of the function
1346 that consist of single basic blocks. */
1353 int maxii
, max_asap
;
1354 partial_schedule_ptr ps
;
1355 basic_block bb
= NULL
;
1357 basic_block condition_bb
= NULL
;
1359 HOST_WIDE_INT trip_count
, max_trip_count
;
1360 HARD_REG_SET prohibited_regs
;
1362 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1363 | LOOPS_HAVE_RECORDED_EXITS
);
1364 if (number_of_loops (cfun
) <= 1)
1366 loop_optimizer_finalize ();
1367 return; /* There are no loops to schedule. */
1370 /* Initialize issue_rate. */
1371 if (targetm
.sched
.issue_rate
)
1373 int temp
= reload_completed
;
1375 reload_completed
= 1;
1376 issue_rate
= targetm
.sched
.issue_rate ();
1377 reload_completed
= temp
;
1382 /* Initialize the scheduler. */
1383 setup_sched_infos ();
1384 haifa_sched_init ();
1386 /* Allocate memory to hold the DDG array one entry for each loop.
1387 We use loop->num as index into this array. */
1388 g_arr
= XCNEWVEC (ddg_ptr
, number_of_loops (cfun
));
1390 REG_SET_TO_HARD_REG_SET (prohibited_regs
, &df
->regular_block_artificial_uses
);
1394 fprintf (dump_file
, "\n\nSMS analysis phase\n");
1395 fprintf (dump_file
, "===================\n\n");
1398 /* Build DDGs for all the relevant loops and hold them in G_ARR
1399 indexed by the loop index. */
1400 FOR_EACH_LOOP (loop
, 0)
1402 rtx_insn
*head
, *tail
;
1405 /* For debugging. */
1406 if (dbg_cnt (sms_sched_loop
) == false)
1409 fprintf (dump_file
, "SMS reached max limit... \n");
1416 rtx_insn
*insn
= BB_END (loop
->header
);
1418 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1419 dump_insn_location (insn
);
1420 fprintf (dump_file
, "\n");
1423 if (! loop_canon_p (loop
))
1426 if (! loop_single_full_bb_p (loop
))
1429 fprintf (dump_file
, "SMS not loop_single_full_bb_p\n");
1435 get_ebb_head_tail (bb
, bb
, &head
, &tail
);
1436 latch_edge
= loop_latch_edge (loop
);
1437 gcc_assert (single_exit (loop
));
1438 trip_count
= get_estimated_loop_iterations_int (loop
);
1439 max_trip_count
= get_max_loop_iterations_int (loop
);
1441 /* Perform SMS only on loops that their average count is above threshold. */
1443 if ( latch_edge
->count () > profile_count::zero ()
1444 && (latch_edge
->count()
1445 < single_exit (loop
)->count ().apply_scale
1446 (param_sms_loop_average_count_threshold
, 1)))
1450 dump_insn_location (tail
);
1451 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1452 if (profile_info
&& flag_branch_probabilities
)
1454 fprintf (dump_file
, "SMS loop-count ");
1455 fprintf (dump_file
, "%" PRId64
,
1456 (int64_t) bb
->count
.to_gcov_type ());
1457 fprintf (dump_file
, "\n");
1458 fprintf (dump_file
, "SMS trip-count ");
1459 fprintf (dump_file
, "%" PRId64
"max %" PRId64
,
1460 (int64_t) trip_count
, (int64_t) max_trip_count
);
1461 fprintf (dump_file
, "\n");
1467 /* Make sure this is a doloop. */
1468 if ( !(count_reg
= doloop_register_get (head
, tail
)))
1471 fprintf (dump_file
, "SMS doloop_register_get failed\n");
1475 /* Don't handle BBs with calls or barriers
1476 or !single_set with the exception of do-loop control part insns.
1477 ??? Should handle insns defining subregs. */
1478 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1483 CLEAR_HARD_REG_SET (regs
);
1484 note_stores (insn
, record_hard_reg_sets
, ®s
);
1485 if (hard_reg_set_intersect_p (regs
, prohibited_regs
))
1491 || (INSN_P (insn
) && single_set (insn
)
1492 && GET_CODE (SET_DEST (single_set (insn
))) == SUBREG
)
1493 /* Not a single set. */
1494 || (NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1495 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
1496 /* But non-single-set allowed in one special case. */
1497 && (insn
!= prev_nondebug_insn (tail
)
1498 || !reg_mentioned_p (count_reg
, insn
))))
1502 if (insn
!= NEXT_INSN (tail
))
1507 fprintf (dump_file
, "SMS loop-with-call\n");
1508 else if (BARRIER_P (insn
))
1509 fprintf (dump_file
, "SMS loop-with-barrier\n");
1510 else if (INSN_P (insn
) && single_set (insn
)
1511 && GET_CODE (SET_DEST (single_set (insn
))) == SUBREG
)
1512 fprintf (dump_file
, "SMS loop with subreg in lhs\n");
1515 "SMS loop-with-not-single-set-or-prohibited-reg\n");
1517 print_rtl_single (dump_file
, insn
);
1523 /* Always schedule the closing branch with the rest of the
1524 instructions. The branch is rotated to be in row ii-1 at the
1525 end of the scheduling procedure to make sure it's the last
1526 instruction in the iteration. */
1527 if (! (g
= create_ddg (bb
, 1)))
1530 fprintf (dump_file
, "SMS create_ddg failed\n");
1534 g_arr
[loop
->num
] = g
;
1536 fprintf (dump_file
, "...OK\n");
1541 fprintf (dump_file
, "\nSMS transformation phase\n");
1542 fprintf (dump_file
, "=========================\n\n");
1545 /* We don't want to perform SMS on new loops - created by versioning. */
1546 FOR_EACH_LOOP (loop
, 0)
1548 rtx_insn
*head
, *tail
;
1550 rtx_insn
*count_init
;
1551 int mii
, rec_mii
, stage_count
, min_cycle
;
1552 int64_t loop_count
= 0;
1553 bool opt_sc_p
, adjust_inplace
= false;
1554 basic_block pre_header
;
1556 if (! (g
= g_arr
[loop
->num
]))
1561 rtx_insn
*insn
= BB_END (loop
->header
);
1563 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1564 dump_insn_location (insn
);
1565 fprintf (dump_file
, "\n");
1567 print_ddg (dump_file
, g
);
1570 get_ebb_head_tail (loop
->header
, loop
->header
, &head
, &tail
);
1572 latch_edge
= loop_latch_edge (loop
);
1573 gcc_assert (single_exit (loop
));
1574 trip_count
= get_estimated_loop_iterations_int (loop
);
1575 max_trip_count
= get_max_loop_iterations_int (loop
);
1579 dump_insn_location (tail
);
1580 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1581 if (profile_info
&& flag_branch_probabilities
)
1583 fprintf (dump_file
, "SMS loop-count ");
1584 fprintf (dump_file
, "%" PRId64
,
1585 (int64_t) bb
->count
.to_gcov_type ());
1586 fprintf (dump_file
, "\n");
1588 fprintf (dump_file
, "SMS doloop\n");
1589 fprintf (dump_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1590 fprintf (dump_file
, "SMS num-loads %d\n", g
->num_loads
);
1591 fprintf (dump_file
, "SMS num-stores %d\n", g
->num_stores
);
1595 count_reg
= doloop_register_get (head
, tail
);
1596 gcc_assert (count_reg
);
1598 pre_header
= loop_preheader_edge (loop
)->src
;
1599 count_init
= const_iteration_count (count_reg
, pre_header
, &loop_count
,
1602 if (dump_file
&& count_init
)
1604 fprintf (dump_file
, "SMS const-doloop ");
1605 fprintf (dump_file
, "%" PRId64
,
1607 fprintf (dump_file
, "\n");
1610 node_order
= XNEWVEC (int, g
->num_nodes
);
1612 mii
= 1; /* Need to pass some estimate of mii. */
1613 rec_mii
= sms_order_nodes (g
, mii
, node_order
, &max_asap
);
1614 mii
= MAX (res_MII (g
), rec_mii
);
1616 maxii
= MAX (max_asap
, param_sms_max_ii_factor
* mii
);
1619 fprintf (dump_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1620 rec_mii
, mii
, maxii
);
1624 set_node_sched_params (g
);
1628 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
);
1632 /* Try to achieve optimized SC by normalizing the partial
1633 schedule (having the cycles start from cycle zero).
1634 The branch location must be placed in row ii-1 in the
1635 final scheduling. If failed, shift all instructions to
1636 position the branch in row ii-1. */
1637 opt_sc_p
= optimize_sc (ps
, g
);
1639 stage_count
= calculate_stage_count (ps
, 0);
1642 /* Bring the branch to cycle ii-1. */
1643 int amount
= (SCHED_TIME (g
->closing_branch
->cuid
)
1647 fprintf (dump_file
, "SMS schedule branch at cycle ii-1\n");
1649 stage_count
= calculate_stage_count (ps
, amount
);
1652 gcc_assert (stage_count
>= 1);
1655 /* The default value of param_sms_min_sc is 2 as stage count of
1656 1 means that there is no interleaving between iterations thus
1657 we let the scheduling passes do the job in this case. */
1658 if (stage_count
< param_sms_min_sc
1659 || (count_init
&& (loop_count
<= stage_count
))
1660 || (max_trip_count
>= 0 && max_trip_count
<= stage_count
)
1661 || (trip_count
>= 0 && trip_count
<= stage_count
))
1665 fprintf (dump_file
, "SMS failed... \n");
1666 fprintf (dump_file
, "SMS sched-failed (stage-count=%d,"
1667 " loop-count=", stage_count
);
1668 fprintf (dump_file
, "%" PRId64
, loop_count
);
1669 fprintf (dump_file
, ", trip-count=");
1670 fprintf (dump_file
, "%" PRId64
"max %" PRId64
,
1671 (int64_t) trip_count
, (int64_t) max_trip_count
);
1672 fprintf (dump_file
, ")\n");
1679 /* Rotate the partial schedule to have the branch in row ii-1. */
1680 int amount
= SCHED_TIME (g
->closing_branch
->cuid
) - (ps
->ii
- 1);
1682 reset_sched_times (ps
, amount
);
1683 rotate_partial_schedule (ps
, amount
);
1686 set_columns_for_ps (ps
);
1688 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1689 if (!schedule_reg_moves (ps
))
1692 free_partial_schedule (ps
);
1696 /* Moves that handle incoming values might have been added
1697 to a new first stage. Bump the stage count if so.
1699 ??? Perhaps we could consider rotating the schedule here
1701 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1703 reset_sched_times (ps
, 0);
1707 /* The stage count should now be correct without rotation. */
1708 gcc_checking_assert (stage_count
== calculate_stage_count (ps
, 0));
1709 PS_STAGE_COUNT (ps
) = stage_count
;
1715 dump_insn_location (tail
);
1716 fprintf (dump_file
, " SMS succeeded %d %d (with ii, sc)\n",
1717 ps
->ii
, stage_count
);
1718 print_partial_schedule (ps
, dump_file
);
1725 /* When possible, set new iteration count of loop kernel in
1726 place. Otherwise, generate_prolog_epilog creates an insn
1728 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1734 /* case the BCT count is not known , Do loop-versioning */
1735 rtx comp_rtx
= gen_rtx_GT (VOIDmode
, count_reg
,
1736 gen_int_mode (stage_count
,
1737 GET_MODE (count_reg
)));
1738 profile_probability prob
= profile_probability::guessed_always ()
1739 .apply_scale (PROB_SMS_ENOUGH_ITERATIONS
, 100);
1741 loop_version (loop
, comp_rtx
, &condition_bb
,
1742 prob
, prob
.invert (),
1743 prob
, prob
.invert (), true);
1746 /* Now apply the scheduled kernel to the RTL of the loop. */
1747 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1749 /* Mark this loop as software pipelined so the later
1750 scheduling passes don't touch it. */
1751 if (! flag_resched_modulo_sched
)
1752 mark_loop_unsched (loop
);
1754 /* The life-info is not valid any more. */
1755 df_set_bb_dirty (g
->bb
);
1757 apply_reg_moves (ps
);
1759 print_node_sched_params (dump_file
, g
->num_nodes
, ps
);
1760 /* Generate prolog and epilog. */
1761 generate_prolog_epilog (ps
, loop
, count_reg
, !adjust_inplace
);
1765 free_partial_schedule (ps
);
1766 node_sched_param_vec
.release ();
1773 /* Release scheduler data, needed until now because of DFA. */
1774 haifa_sched_finish ();
1775 loop_optimizer_finalize ();
1778 /* The SMS scheduling algorithm itself
1779 -----------------------------------
1780 Input: 'O' an ordered list of insns of a loop.
1781 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1783 'Q' is the empty Set
1784 'PS' is the partial schedule; it holds the currently scheduled nodes with
1786 'PSP' previously scheduled predecessors.
1787 'PSS' previously scheduled successors.
1788 't(u)' the cycle where u is scheduled.
1789 'l(u)' is the latency of u.
1790 'd(v,u)' is the dependence distance from v to u.
1791 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1792 the node ordering phase.
1793 'check_hardware_resources_conflicts(u, PS, c)'
1794 run a trace around cycle/slot through DFA model
1795 to check resource conflicts involving instruction u
1796 at cycle c given the partial schedule PS.
1797 'add_to_partial_schedule_at_time(u, PS, c)'
1798 Add the node/instruction u to the partial schedule
1800 'calculate_register_pressure(PS)'
1801 Given a schedule of instructions, calculate the register
1802 pressure it implies. One implementation could be the
1803 maximum number of overlapping live ranges.
1804 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1805 registers available in the hardware.
1809 3. for each node u in O in pre-computed order
1810 4. if (PSP(u) != Q && PSS(u) == Q) then
1811 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1812 6. start = Early_start; end = Early_start + II - 1; step = 1
1813 11. else if (PSP(u) == Q && PSS(u) != Q) then
1814 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1815 13. start = Late_start; end = Late_start - II + 1; step = -1
1816 14. else if (PSP(u) != Q && PSS(u) != Q) then
1817 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1818 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1819 17. start = Early_start;
1820 18. end = min(Early_start + II - 1 , Late_start);
1822 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1823 21. start = ASAP(u); end = start + II - 1; step = 1
1827 24. for (c = start ; c != end ; c += step)
1828 25. if check_hardware_resources_conflicts(u, PS, c) then
1829 26. add_to_partial_schedule_at_time(u, PS, c)
1834 31. if (success == false) then
1836 33. if (II > maxII) then
1837 34. finish - failed to schedule
1842 39. if (calculate_register_pressure(PS) > maxRP) then
1845 42. compute epilogue & prologue
1846 43. finish - succeeded to schedule
1848 ??? The algorithm restricts the scheduling window to II cycles.
1849 In rare cases, it may be better to allow windows of II+1 cycles.
1850 The window would then start and end on the same row, but with
1851 different "must precede" and "must follow" requirements. */
1853 /* A threshold for the number of repeated unsuccessful attempts to insert
1854 an empty row, before we flush the partial schedule and start over. */
1855 #define MAX_SPLIT_NUM 10
1856 /* Given the partial schedule PS, this function calculates and returns the
1857 cycles in which we can schedule the node with the given index I.
1858 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1859 noticed that there are several cases in which we fail to SMS the loop
1860 because the sched window of a node is empty due to tight data-deps. In
1861 such cases we want to unschedule some of the predecessors/successors
1862 until we get non-empty scheduling window. It returns -1 if the
1863 scheduling window is empty and zero otherwise. */
1866 get_sched_window (partial_schedule_ptr ps
, ddg_node_ptr u_node
,
1867 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
,
1870 int start
, step
, end
;
1871 int early_start
, late_start
;
1873 auto_sbitmap
psp (ps
->g
->num_nodes
);
1874 auto_sbitmap
pss (ps
->g
->num_nodes
);
1875 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1876 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1882 /* 1. compute sched window for u (start, end, step). */
1885 psp_not_empty
= bitmap_and (psp
, u_node_preds
, sched_nodes
);
1886 pss_not_empty
= bitmap_and (pss
, u_node_succs
, sched_nodes
);
1888 /* We first compute a forward range (start <= end), then decide whether
1890 early_start
= INT_MIN
;
1891 late_start
= INT_MAX
;
1899 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1901 fprintf (dump_file
, "\nAnalyzing dependencies for node %d (INSN %d)"
1902 "; ii = %d\n\n", u_node
->cuid
, INSN_UID (u_node
->insn
), ii
);
1903 fprintf (dump_file
, "%11s %11s %11s %11s %5s\n",
1904 "start", "early start", "late start", "end", "time");
1905 fprintf (dump_file
, "=========== =========== =========== ==========="
1908 /* Calculate early_start and limit end. Both bounds are inclusive. */
1910 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1912 int v
= e
->src
->cuid
;
1914 if (bitmap_bit_p (sched_nodes
, v
))
1916 int p_st
= SCHED_TIME (v
);
1917 int earliest
= p_st
+ e
->latency
- (e
->distance
* ii
);
1918 int latest
= (e
->data_type
== MEM_DEP
? p_st
+ ii
- 1 : INT_MAX
);
1922 fprintf (dump_file
, "%11s %11d %11s %11d %5d",
1923 "", earliest
, "", latest
, p_st
);
1924 print_ddg_edge (dump_file
, e
);
1925 fprintf (dump_file
, "\n");
1928 early_start
= MAX (early_start
, earliest
);
1929 end
= MIN (end
, latest
);
1931 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1936 /* Calculate late_start and limit start. Both bounds are inclusive. */
1938 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1940 int v
= e
->dest
->cuid
;
1942 if (bitmap_bit_p (sched_nodes
, v
))
1944 int s_st
= SCHED_TIME (v
);
1945 int earliest
= (e
->data_type
== MEM_DEP
? s_st
- ii
+ 1 : INT_MIN
);
1946 int latest
= s_st
- e
->latency
+ (e
->distance
* ii
);
1950 fprintf (dump_file
, "%11d %11s %11d %11s %5d",
1951 earliest
, "", latest
, "", s_st
);
1952 print_ddg_edge (dump_file
, e
);
1953 fprintf (dump_file
, "\n");
1956 start
= MAX (start
, earliest
);
1957 late_start
= MIN (late_start
, latest
);
1959 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1964 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1966 fprintf (dump_file
, "----------- ----------- ----------- -----------"
1968 fprintf (dump_file
, "%11d %11d %11d %11d %5s %s\n",
1969 start
, early_start
, late_start
, end
, "",
1970 "(max, max, min, min)");
1973 /* Get a target scheduling window no bigger than ii. */
1974 if (early_start
== INT_MIN
&& late_start
== INT_MAX
)
1975 early_start
= NODE_ASAP (u_node
);
1976 else if (early_start
== INT_MIN
)
1977 early_start
= late_start
- (ii
- 1);
1978 late_start
= MIN (late_start
, early_start
+ (ii
- 1));
1980 /* Apply memory dependence limits. */
1981 start
= MAX (start
, early_start
);
1982 end
= MIN (end
, late_start
);
1984 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1985 fprintf (dump_file
, "%11s %11d %11d %11s %5s final window\n",
1986 "", start
, end
, "", "");
1988 /* If there are at least as many successors as predecessors, schedule the
1989 node close to its successors. */
1990 if (pss_not_empty
&& count_succs
>= count_preds
)
1992 std::swap (start
, end
);
1996 /* Now that we've finalized the window, make END an exclusive rather
1997 than an inclusive bound. */
2004 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
2007 fprintf (dump_file
, "\nEmpty window: start=%d, end=%d, step=%d\n",
2015 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
2016 node currently been scheduled. At the end of the calculation
2017 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
2018 U_NODE which are (1) already scheduled in the first/last row of
2019 U_NODE's scheduling window, (2) whose dependence inequality with U
2020 becomes an equality when U is scheduled in this same row, and (3)
2021 whose dependence latency is zero.
2023 The first and last rows are calculated using the following parameters:
2024 START/END rows - The cycles that begins/ends the traversal on the window;
2025 searching for an empty cycle to schedule U_NODE.
2026 STEP - The direction in which we traverse the window.
2027 II - The initiation interval. */
2030 calculate_must_precede_follow (ddg_node_ptr u_node
, int start
, int end
,
2031 int step
, int ii
, sbitmap sched_nodes
,
2032 sbitmap must_precede
, sbitmap must_follow
)
2035 int first_cycle_in_window
, last_cycle_in_window
;
2037 gcc_assert (must_precede
&& must_follow
);
2039 /* Consider the following scheduling window:
2040 {first_cycle_in_window, first_cycle_in_window+1, ...,
2041 last_cycle_in_window}. If step is 1 then the following will be
2042 the order we traverse the window: {start=first_cycle_in_window,
2043 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
2044 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
2045 end=first_cycle_in_window-1} if step is -1. */
2046 first_cycle_in_window
= (step
== 1) ? start
: end
- step
;
2047 last_cycle_in_window
= (step
== 1) ? end
- step
: start
;
2049 bitmap_clear (must_precede
);
2050 bitmap_clear (must_follow
);
2053 fprintf (dump_file
, "\nmust_precede: ");
2055 /* Instead of checking if:
2056 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
2057 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
2058 first_cycle_in_window)
2060 we use the fact that latency is non-negative:
2061 SCHED_TIME (e->src) - (e->distance * ii) <=
2062 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
2063 first_cycle_in_window
2065 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
2066 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2067 if (bitmap_bit_p (sched_nodes
, e
->src
->cuid
)
2068 && ((SCHED_TIME (e
->src
->cuid
) - (e
->distance
* ii
)) ==
2069 first_cycle_in_window
))
2072 fprintf (dump_file
, "%d ", e
->src
->cuid
);
2074 bitmap_set_bit (must_precede
, e
->src
->cuid
);
2078 fprintf (dump_file
, "\nmust_follow: ");
2080 /* Instead of checking if:
2081 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
2082 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
2083 last_cycle_in_window)
2085 we use the fact that latency is non-negative:
2086 SCHED_TIME (e->dest) + (e->distance * ii) >=
2087 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
2088 last_cycle_in_window
2090 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
2091 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2092 if (bitmap_bit_p (sched_nodes
, e
->dest
->cuid
)
2093 && ((SCHED_TIME (e
->dest
->cuid
) + (e
->distance
* ii
)) ==
2094 last_cycle_in_window
))
2097 fprintf (dump_file
, "%d ", e
->dest
->cuid
);
2099 bitmap_set_bit (must_follow
, e
->dest
->cuid
);
2103 fprintf (dump_file
, "\n");
2106 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
2107 parameters to decide if that's possible:
2108 PS - The partial schedule.
2109 U - The serial number of U_NODE.
2110 NUM_SPLITS - The number of row splits made so far.
2111 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
2112 the first row of the scheduling window)
2113 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
2114 last row of the scheduling window) */
2117 try_scheduling_node_in_cycle (partial_schedule_ptr ps
,
2118 int u
, int cycle
, sbitmap sched_nodes
,
2119 int *num_splits
, sbitmap must_precede
,
2120 sbitmap must_follow
)
2125 verify_partial_schedule (ps
, sched_nodes
);
2126 psi
= ps_add_node_check_conflicts (ps
, u
, cycle
, must_precede
, must_follow
);
2129 SCHED_TIME (u
) = cycle
;
2130 bitmap_set_bit (sched_nodes
, u
);
2134 fprintf (dump_file
, "Scheduled w/o split in %d\n", cycle
);
2141 /* This function implements the scheduling algorithm for SMS according to the
2143 static partial_schedule_ptr
2144 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
)
2147 int i
, c
, success
, num_splits
= 0;
2148 int flush_and_start_over
= true;
2149 int num_nodes
= g
->num_nodes
;
2150 int start
, end
, step
; /* Place together into one struct? */
2151 auto_sbitmap
sched_nodes (num_nodes
);
2152 auto_sbitmap
must_precede (num_nodes
);
2153 auto_sbitmap
must_follow (num_nodes
);
2154 auto_sbitmap
tobe_scheduled (num_nodes
);
2156 /* Value of param_sms_dfa_history is a limit on the number of cycles that
2157 resource conflicts can span. ??? Should be provided by DFA, and be
2158 dependent on the type of insn scheduled. Set to 0 by default to save
2160 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
,
2161 param_sms_dfa_history
);
2163 bitmap_ones (tobe_scheduled
);
2164 bitmap_clear (sched_nodes
);
2166 while (flush_and_start_over
&& (ii
< maxii
))
2170 fprintf (dump_file
, "Starting with ii=%d\n", ii
);
2171 flush_and_start_over
= false;
2172 bitmap_clear (sched_nodes
);
2174 for (i
= 0; i
< num_nodes
; i
++)
2176 int u
= nodes_order
[i
];
2177 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
2178 rtx_insn
*insn
= u_node
->insn
;
2180 gcc_checking_assert (NONDEBUG_INSN_P (insn
));
2182 if (bitmap_bit_p (sched_nodes
, u
))
2185 /* Try to get non-empty scheduling window. */
2187 if (get_sched_window (ps
, u_node
, sched_nodes
, ii
, &start
,
2191 fprintf (dump_file
, "\nTrying to schedule node %d "
2192 "INSN = %d in (%d .. %d) step %d\n", u
, (INSN_UID
2193 (g
->nodes
[u
].insn
)), start
, end
, step
);
2195 gcc_assert ((step
> 0 && start
< end
)
2196 || (step
< 0 && start
> end
));
2198 calculate_must_precede_follow (u_node
, start
, end
, step
, ii
,
2199 sched_nodes
, must_precede
,
2202 for (c
= start
; c
!= end
; c
+= step
)
2204 sbitmap tmp_precede
, tmp_follow
;
2206 set_must_precede_follow (&tmp_follow
, must_follow
,
2207 &tmp_precede
, must_precede
,
2208 c
, start
, end
, step
);
2210 try_scheduling_node_in_cycle (ps
, u
, c
,
2212 &num_splits
, tmp_precede
,
2218 verify_partial_schedule (ps
, sched_nodes
);
2227 if (num_splits
>= MAX_SPLIT_NUM
)
2230 flush_and_start_over
= true;
2231 verify_partial_schedule (ps
, sched_nodes
);
2232 reset_partial_schedule (ps
, ii
);
2233 verify_partial_schedule (ps
, sched_nodes
);
2238 /* The scheduling window is exclusive of 'end'
2239 whereas compute_split_window() expects an inclusive,
2242 split_row
= compute_split_row (sched_nodes
, start
, end
- 1,
2245 split_row
= compute_split_row (sched_nodes
, end
+ 1, start
,
2248 ps_insert_empty_row (ps
, split_row
, sched_nodes
);
2249 i
--; /* Go back and retry node i. */
2252 fprintf (dump_file
, "num_splits=%d\n", num_splits
);
2255 /* ??? If (success), check register pressure estimates. */
2256 } /* Continue with next node. */
2257 } /* While flush_and_start_over. */
2260 free_partial_schedule (ps
);
2264 gcc_assert (bitmap_equal_p (tobe_scheduled
, sched_nodes
));
2269 /* This function inserts a new empty row into PS at the position
2270 according to SPLITROW, keeping all already scheduled instructions
2271 intact and updating their SCHED_TIME and cycle accordingly. */
2273 ps_insert_empty_row (partial_schedule_ptr ps
, int split_row
,
2274 sbitmap sched_nodes
)
2276 ps_insn_ptr crr_insn
;
2277 ps_insn_ptr
*rows_new
;
2279 int new_ii
= ii
+ 1;
2281 int *rows_length_new
;
2283 verify_partial_schedule (ps
, sched_nodes
);
2285 /* We normalize sched_time and rotate ps to have only non-negative sched
2286 times, for simplicity of updating cycles after inserting new row. */
2287 split_row
-= ps
->min_cycle
;
2288 split_row
= SMODULO (split_row
, ii
);
2290 fprintf (dump_file
, "split_row=%d\n", split_row
);
2292 reset_sched_times (ps
, PS_MIN_CYCLE (ps
));
2293 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
2295 rows_new
= (ps_insn_ptr
*) xcalloc (new_ii
, sizeof (ps_insn_ptr
));
2296 rows_length_new
= (int *) xcalloc (new_ii
, sizeof (int));
2297 for (row
= 0; row
< split_row
; row
++)
2299 rows_new
[row
] = ps
->rows
[row
];
2300 rows_length_new
[row
] = ps
->rows_length
[row
];
2301 ps
->rows
[row
] = NULL
;
2302 for (crr_insn
= rows_new
[row
];
2303 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2305 int u
= crr_insn
->id
;
2306 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
);
2308 SCHED_TIME (u
) = new_time
;
2309 crr_insn
->cycle
= new_time
;
2310 SCHED_ROW (u
) = new_time
% new_ii
;
2311 SCHED_STAGE (u
) = new_time
/ new_ii
;
2316 rows_new
[split_row
] = NULL
;
2318 for (row
= split_row
; row
< ii
; row
++)
2320 rows_new
[row
+ 1] = ps
->rows
[row
];
2321 rows_length_new
[row
+ 1] = ps
->rows_length
[row
];
2322 ps
->rows
[row
] = NULL
;
2323 for (crr_insn
= rows_new
[row
+ 1];
2324 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2326 int u
= crr_insn
->id
;
2327 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
) + 1;
2329 SCHED_TIME (u
) = new_time
;
2330 crr_insn
->cycle
= new_time
;
2331 SCHED_ROW (u
) = new_time
% new_ii
;
2332 SCHED_STAGE (u
) = new_time
/ new_ii
;
2337 ps
->min_cycle
= ps
->min_cycle
+ ps
->min_cycle
/ ii
2338 + (SMODULO (ps
->min_cycle
, ii
) >= split_row
? 1 : 0);
2339 ps
->max_cycle
= ps
->max_cycle
+ ps
->max_cycle
/ ii
2340 + (SMODULO (ps
->max_cycle
, ii
) >= split_row
? 1 : 0);
2342 ps
->rows
= rows_new
;
2343 free (ps
->rows_length
);
2344 ps
->rows_length
= rows_length_new
;
2346 gcc_assert (ps
->min_cycle
>= 0);
2348 verify_partial_schedule (ps
, sched_nodes
);
2351 fprintf (dump_file
, "min_cycle=%d, max_cycle=%d\n", ps
->min_cycle
,
2355 /* Given U_NODE which is the node that failed to be scheduled; LOW and
2356 UP which are the boundaries of it's scheduling window; compute using
2357 SCHED_NODES and II a row in the partial schedule that can be split
2358 which will separate a critical predecessor from a critical successor
2359 thereby expanding the window, and return it. */
2361 compute_split_row (sbitmap sched_nodes
, int low
, int up
, int ii
,
2362 ddg_node_ptr u_node
)
2365 int lower
= INT_MIN
, upper
= INT_MAX
;
2370 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2372 int v
= e
->src
->cuid
;
2374 if (bitmap_bit_p (sched_nodes
, v
)
2375 && (low
== SCHED_TIME (v
) + e
->latency
- (e
->distance
* ii
)))
2376 if (SCHED_TIME (v
) > lower
)
2379 lower
= SCHED_TIME (v
);
2385 crit_cycle
= SCHED_TIME (crit_pred
) + 1;
2386 return SMODULO (crit_cycle
, ii
);
2389 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2391 int v
= e
->dest
->cuid
;
2393 if (bitmap_bit_p (sched_nodes
, v
)
2394 && (up
== SCHED_TIME (v
) - e
->latency
+ (e
->distance
* ii
)))
2395 if (SCHED_TIME (v
) < upper
)
2398 upper
= SCHED_TIME (v
);
2404 crit_cycle
= SCHED_TIME (crit_succ
);
2405 return SMODULO (crit_cycle
, ii
);
2409 fprintf (dump_file
, "Both crit_pred and crit_succ are NULL\n");
2411 return SMODULO ((low
+ up
+ 1) / 2, ii
);
2415 verify_partial_schedule (partial_schedule_ptr ps
, sbitmap sched_nodes
)
2418 ps_insn_ptr crr_insn
;
2420 for (row
= 0; row
< ps
->ii
; row
++)
2424 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2426 int u
= crr_insn
->id
;
2429 gcc_assert (bitmap_bit_p (sched_nodes
, u
));
2430 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2431 popcount (sched_nodes) == number of insns in ps. */
2432 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
2433 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
2436 gcc_assert (ps
->rows_length
[row
] == length
);
2441 /* This page implements the algorithm for ordering the nodes of a DDG
2442 for modulo scheduling, activated through the
2443 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2445 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2446 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
2447 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
2448 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2449 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
2450 #define DEPTH(x) (ASAP ((x)))
2452 typedef struct node_order_params
* nopa
;
2454 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
2455 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
2456 static nopa
calculate_order_params (ddg_ptr
, int, int *);
2457 static int find_max_asap (ddg_ptr
, sbitmap
);
2458 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
2459 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
2461 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
2463 struct node_order_params
2470 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2472 check_nodes_order (int *node_order
, int num_nodes
)
2475 auto_sbitmap
tmp (num_nodes
);
2480 fprintf (dump_file
, "SMS final nodes order: \n");
2482 for (i
= 0; i
< num_nodes
; i
++)
2484 int u
= node_order
[i
];
2487 fprintf (dump_file
, "%d ", u
);
2488 gcc_assert (u
< num_nodes
&& u
>= 0 && !bitmap_bit_p (tmp
, u
));
2490 bitmap_set_bit (tmp
, u
);
2494 fprintf (dump_file
, "\n");
2497 /* Order the nodes of G for scheduling and pass the result in
2498 NODE_ORDER. Also set aux.count of each node to ASAP.
2499 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2501 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
, int *pmax_asap
)
2505 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
2507 nopa nops
= calculate_order_params (g
, mii
, pmax_asap
);
2510 print_sccs (dump_file
, sccs
, g
);
2512 order_nodes_of_sccs (sccs
, node_order
);
2514 if (sccs
->num_sccs
> 0)
2515 /* First SCC has the largest recurrence_length. */
2516 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
2518 /* Save ASAP before destroying node_order_params. */
2519 for (i
= 0; i
< g
->num_nodes
; i
++)
2521 ddg_node_ptr v
= &g
->nodes
[i
];
2522 v
->aux
.count
= ASAP (v
);
2526 free_ddg_all_sccs (sccs
);
2527 check_nodes_order (node_order
, g
->num_nodes
);
2533 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
2536 ddg_ptr g
= all_sccs
->ddg
;
2537 int num_nodes
= g
->num_nodes
;
2538 auto_sbitmap
prev_sccs (num_nodes
);
2539 auto_sbitmap
on_path (num_nodes
);
2540 auto_sbitmap
tmp (num_nodes
);
2541 auto_sbitmap
ones (num_nodes
);
2543 bitmap_clear (prev_sccs
);
2546 /* Perform the node ordering starting from the SCC with the highest recMII.
2547 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2548 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
2550 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
2552 /* Add nodes on paths from previous SCCs to the current SCC. */
2553 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
2554 bitmap_ior (tmp
, scc
->nodes
, on_path
);
2556 /* Add nodes on paths from the current SCC to previous SCCs. */
2557 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
2558 bitmap_ior (tmp
, tmp
, on_path
);
2560 /* Remove nodes of previous SCCs from current extended SCC. */
2561 bitmap_and_compl (tmp
, tmp
, prev_sccs
);
2563 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2564 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2567 /* Handle the remaining nodes that do not belong to any scc. Each call
2568 to order_nodes_in_scc handles a single connected component. */
2569 while (pos
< g
->num_nodes
)
2571 bitmap_and_compl (tmp
, ones
, prev_sccs
);
2572 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2576 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2577 static struct node_order_params
*
2578 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
, int *pmax_asap
)
2582 int num_nodes
= g
->num_nodes
;
2584 /* Allocate a place to hold ordering params for each node in the DDG. */
2585 nopa node_order_params_arr
;
2587 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2588 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
2589 sizeof (struct node_order_params
));
2591 /* Set the aux pointer of each node to point to its order_params structure. */
2592 for (u
= 0; u
< num_nodes
; u
++)
2593 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
2595 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2596 calculate ASAP, ALAP, mobility, distance, and height for each node
2597 in the dependence (direct acyclic) graph. */
2599 /* We assume that the nodes in the array are in topological order. */
2602 for (u
= 0; u
< num_nodes
; u
++)
2604 ddg_node_ptr u_node
= &g
->nodes
[u
];
2607 for (e
= u_node
->in
; e
; e
= e
->next_in
)
2608 if (e
->distance
== 0)
2609 ASAP (u_node
) = MAX (ASAP (u_node
),
2610 ASAP (e
->src
) + e
->latency
);
2611 max_asap
= MAX (max_asap
, ASAP (u_node
));
2614 for (u
= num_nodes
- 1; u
> -1; u
--)
2616 ddg_node_ptr u_node
= &g
->nodes
[u
];
2618 ALAP (u_node
) = max_asap
;
2619 HEIGHT (u_node
) = 0;
2620 for (e
= u_node
->out
; e
; e
= e
->next_out
)
2621 if (e
->distance
== 0)
2623 ALAP (u_node
) = MIN (ALAP (u_node
),
2624 ALAP (e
->dest
) - e
->latency
);
2625 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
2626 HEIGHT (e
->dest
) + e
->latency
);
2631 fprintf (dump_file
, "\nOrder params\n");
2632 for (u
= 0; u
< num_nodes
; u
++)
2634 ddg_node_ptr u_node
= &g
->nodes
[u
];
2636 fprintf (dump_file
, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u
,
2637 ASAP (u_node
), ALAP (u_node
), HEIGHT (u_node
));
2641 *pmax_asap
= max_asap
;
2642 return node_order_params_arr
;
2646 find_max_asap (ddg_ptr g
, sbitmap nodes
)
2651 sbitmap_iterator sbi
;
2653 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2655 ddg_node_ptr u_node
= &g
->nodes
[u
];
2657 if (max_asap
< ASAP (u_node
))
2659 max_asap
= ASAP (u_node
);
2667 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
2671 int min_mob
= INT_MAX
;
2673 sbitmap_iterator sbi
;
2675 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2677 ddg_node_ptr u_node
= &g
->nodes
[u
];
2679 if (max_hv
< HEIGHT (u_node
))
2681 max_hv
= HEIGHT (u_node
);
2682 min_mob
= MOB (u_node
);
2685 else if ((max_hv
== HEIGHT (u_node
))
2686 && (min_mob
> MOB (u_node
)))
2688 min_mob
= MOB (u_node
);
2696 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
2700 int min_mob
= INT_MAX
;
2702 sbitmap_iterator sbi
;
2704 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2706 ddg_node_ptr u_node
= &g
->nodes
[u
];
2708 if (max_dv
< DEPTH (u_node
))
2710 max_dv
= DEPTH (u_node
);
2711 min_mob
= MOB (u_node
);
2714 else if ((max_dv
== DEPTH (u_node
))
2715 && (min_mob
> MOB (u_node
)))
2717 min_mob
= MOB (u_node
);
2724 /* Places the nodes of SCC into the NODE_ORDER array starting
2725 at position POS, according to the SMS ordering algorithm.
2726 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2727 the NODE_ORDER array, starting from position zero. */
2729 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
2730 int * node_order
, int pos
)
2732 enum sms_direction dir
;
2733 int num_nodes
= g
->num_nodes
;
2734 auto_sbitmap
workset (num_nodes
);
2735 auto_sbitmap
tmp (num_nodes
);
2736 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
2737 auto_sbitmap
predecessors (num_nodes
);
2738 auto_sbitmap
successors (num_nodes
);
2740 bitmap_clear (predecessors
);
2741 find_predecessors (predecessors
, g
, nodes_ordered
);
2743 bitmap_clear (successors
);
2744 find_successors (successors
, g
, nodes_ordered
);
2747 if (bitmap_and (tmp
, predecessors
, scc
))
2749 bitmap_copy (workset
, tmp
);
2752 else if (bitmap_and (tmp
, successors
, scc
))
2754 bitmap_copy (workset
, tmp
);
2761 bitmap_clear (workset
);
2762 if ((u
= find_max_asap (g
, scc
)) >= 0)
2763 bitmap_set_bit (workset
, u
);
2767 bitmap_clear (zero_bitmap
);
2768 while (!bitmap_equal_p (workset
, zero_bitmap
))
2771 ddg_node_ptr v_node
;
2772 sbitmap v_node_preds
;
2773 sbitmap v_node_succs
;
2777 while (!bitmap_equal_p (workset
, zero_bitmap
))
2779 v
= find_max_hv_min_mob (g
, workset
);
2780 v_node
= &g
->nodes
[v
];
2781 node_order
[pos
++] = v
;
2782 v_node_succs
= NODE_SUCCESSORS (v_node
);
2783 bitmap_and (tmp
, v_node_succs
, scc
);
2785 /* Don't consider the already ordered successors again. */
2786 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2787 bitmap_ior (workset
, workset
, tmp
);
2788 bitmap_clear_bit (workset
, v
);
2789 bitmap_set_bit (nodes_ordered
, v
);
2792 bitmap_clear (predecessors
);
2793 find_predecessors (predecessors
, g
, nodes_ordered
);
2794 bitmap_and (workset
, predecessors
, scc
);
2798 while (!bitmap_equal_p (workset
, zero_bitmap
))
2800 v
= find_max_dv_min_mob (g
, workset
);
2801 v_node
= &g
->nodes
[v
];
2802 node_order
[pos
++] = v
;
2803 v_node_preds
= NODE_PREDECESSORS (v_node
);
2804 bitmap_and (tmp
, v_node_preds
, scc
);
2806 /* Don't consider the already ordered predecessors again. */
2807 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2808 bitmap_ior (workset
, workset
, tmp
);
2809 bitmap_clear_bit (workset
, v
);
2810 bitmap_set_bit (nodes_ordered
, v
);
2813 bitmap_clear (successors
);
2814 find_successors (successors
, g
, nodes_ordered
);
2815 bitmap_and (workset
, successors
, scc
);
2818 sbitmap_free (zero_bitmap
);
2823 /* This page contains functions for manipulating partial-schedules during
2824 modulo scheduling. */
2826 /* Create a partial schedule and allocate a memory to hold II rows. */
2828 static partial_schedule_ptr
2829 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2831 partial_schedule_ptr ps
= XNEW (struct partial_schedule
);
2832 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2833 ps
->rows_length
= (int *) xcalloc (ii
, sizeof (int));
2834 ps
->reg_moves
.create (0);
2836 ps
->history
= history
;
2837 ps
->min_cycle
= INT_MAX
;
2838 ps
->max_cycle
= INT_MIN
;
2844 /* Free the PS_INSNs in rows array of the given partial schedule.
2845 ??? Consider caching the PS_INSN's. */
2847 free_ps_insns (partial_schedule_ptr ps
)
2851 for (i
= 0; i
< ps
->ii
; i
++)
2855 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2858 ps
->rows
[i
] = ps_insn
;
2864 /* Free all the memory allocated to the partial schedule. */
2867 free_partial_schedule (partial_schedule_ptr ps
)
2869 ps_reg_move_info
*move
;
2875 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
2876 sbitmap_free (move
->uses
);
2877 ps
->reg_moves
.release ();
2881 free (ps
->rows_length
);
2885 /* Clear the rows array with its PS_INSNs, and create a new one with
2889 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2894 if (new_ii
== ps
->ii
)
2896 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2897 * sizeof (ps_insn_ptr
));
2898 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2899 ps
->rows_length
= (int *) xrealloc (ps
->rows_length
, new_ii
* sizeof (int));
2900 memset (ps
->rows_length
, 0, new_ii
* sizeof (int));
2902 ps
->min_cycle
= INT_MAX
;
2903 ps
->max_cycle
= INT_MIN
;
2906 /* Prints the partial schedule as an ii rows array, for each rows
2907 print the ids of the insns in it. */
2909 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2913 for (i
= 0; i
< ps
->ii
; i
++)
2915 ps_insn_ptr ps_i
= ps
->rows
[i
];
2917 fprintf (dump
, "\n[ROW %d ]: ", i
);
2920 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_i
->id
);
2923 fprintf (dump
, "%d (branch), ", INSN_UID (insn
));
2925 fprintf (dump
, "%d, ", INSN_UID (insn
));
2927 ps_i
= ps_i
->next_in_row
;
2932 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2934 create_ps_insn (int id
, int cycle
)
2936 ps_insn_ptr ps_i
= XNEW (struct ps_insn
);
2939 ps_i
->next_in_row
= NULL
;
2940 ps_i
->prev_in_row
= NULL
;
2941 ps_i
->cycle
= cycle
;
2947 /* Removes the given PS_INSN from the partial schedule. */
2949 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2953 gcc_assert (ps
&& ps_i
);
2955 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2956 if (! ps_i
->prev_in_row
)
2958 gcc_assert (ps_i
== ps
->rows
[row
]);
2959 ps
->rows
[row
] = ps_i
->next_in_row
;
2961 ps
->rows
[row
]->prev_in_row
= NULL
;
2965 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
2966 if (ps_i
->next_in_row
)
2967 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
2970 ps
->rows_length
[row
] -= 1;
2975 /* Unlike what literature describes for modulo scheduling (which focuses
2976 on VLIW machines) the order of the instructions inside a cycle is
2977 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2978 where the current instruction should go relative to the already
2979 scheduled instructions in the given cycle. Go over these
2980 instructions and find the first possible column to put it in. */
2982 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2983 sbitmap must_precede
, sbitmap must_follow
)
2985 ps_insn_ptr next_ps_i
;
2986 ps_insn_ptr first_must_follow
= NULL
;
2987 ps_insn_ptr last_must_precede
= NULL
;
2988 ps_insn_ptr last_in_row
= NULL
;
2994 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2996 /* Find the first must follow and the last must precede
2997 and insert the node immediately after the must precede
2998 but make sure that it there is no must follow after it. */
2999 for (next_ps_i
= ps
->rows
[row
];
3001 next_ps_i
= next_ps_i
->next_in_row
)
3004 && bitmap_bit_p (must_follow
, next_ps_i
->id
)
3005 && ! first_must_follow
)
3006 first_must_follow
= next_ps_i
;
3007 if (must_precede
&& bitmap_bit_p (must_precede
, next_ps_i
->id
))
3009 /* If we have already met a node that must follow, then
3010 there is no possible column. */
3011 if (first_must_follow
)
3014 last_must_precede
= next_ps_i
;
3016 /* The closing branch must be the last in the row. */
3017 if (JUMP_P (ps_rtl_insn (ps
, next_ps_i
->id
)))
3020 last_in_row
= next_ps_i
;
3023 /* The closing branch is scheduled as well. Make sure there is no
3024 dependent instruction after it as the branch should be the last
3025 instruction in the row. */
3026 if (JUMP_P (ps_rtl_insn (ps
, ps_i
->id
)))
3028 if (first_must_follow
)
3032 /* Make the branch the last in the row. New instructions
3033 will be inserted at the beginning of the row or after the
3034 last must_precede instruction thus the branch is guaranteed
3035 to remain the last instruction in the row. */
3036 last_in_row
->next_in_row
= ps_i
;
3037 ps_i
->prev_in_row
= last_in_row
;
3038 ps_i
->next_in_row
= NULL
;
3041 ps
->rows
[row
] = ps_i
;
3045 /* Now insert the node after INSERT_AFTER_PSI. */
3047 if (! last_must_precede
)
3049 ps_i
->next_in_row
= ps
->rows
[row
];
3050 ps_i
->prev_in_row
= NULL
;
3051 if (ps_i
->next_in_row
)
3052 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3053 ps
->rows
[row
] = ps_i
;
3057 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
3058 last_must_precede
->next_in_row
= ps_i
;
3059 ps_i
->prev_in_row
= last_must_precede
;
3060 if (ps_i
->next_in_row
)
3061 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3067 /* Advances the PS_INSN one column in its current row; returns false
3068 in failure and true in success. Bit N is set in MUST_FOLLOW if
3069 the node with cuid N must be come after the node pointed to by
3070 PS_I when scheduled in the same cycle. */
3072 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
3073 sbitmap must_follow
)
3075 ps_insn_ptr prev
, next
;
3081 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3083 if (! ps_i
->next_in_row
)
3086 /* Check if next_in_row is dependent on ps_i, both having same sched
3087 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
3088 if (must_follow
&& bitmap_bit_p (must_follow
, ps_i
->next_in_row
->id
))
3091 /* Advance PS_I over its next_in_row in the doubly linked list. */
3092 prev
= ps_i
->prev_in_row
;
3093 next
= ps_i
->next_in_row
;
3095 if (ps_i
== ps
->rows
[row
])
3096 ps
->rows
[row
] = next
;
3098 ps_i
->next_in_row
= next
->next_in_row
;
3100 if (next
->next_in_row
)
3101 next
->next_in_row
->prev_in_row
= ps_i
;
3103 next
->next_in_row
= ps_i
;
3104 ps_i
->prev_in_row
= next
;
3106 next
->prev_in_row
= prev
;
3108 prev
->next_in_row
= next
;
3113 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
3114 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
3115 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
3116 before/after (respectively) the node pointed to by PS_I when scheduled
3117 in the same cycle. */
3119 add_node_to_ps (partial_schedule_ptr ps
, int id
, int cycle
,
3120 sbitmap must_precede
, sbitmap must_follow
)
3123 int row
= SMODULO (cycle
, ps
->ii
);
3125 if (ps
->rows_length
[row
] >= issue_rate
)
3128 ps_i
= create_ps_insn (id
, cycle
);
3130 /* Finds and inserts PS_I according to MUST_FOLLOW and
3132 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
3138 ps
->rows_length
[row
] += 1;
3142 /* Advance time one cycle. Assumes DFA is being used. */
3144 advance_one_cycle (void)
3146 if (targetm
.sched
.dfa_pre_cycle_insn
)
3147 state_transition (curr_state
,
3148 targetm
.sched
.dfa_pre_cycle_insn ());
3150 state_transition (curr_state
, NULL
);
3152 if (targetm
.sched
.dfa_post_cycle_insn
)
3153 state_transition (curr_state
,
3154 targetm
.sched
.dfa_post_cycle_insn ());
3159 /* Checks if PS has resource conflicts according to DFA, starting from
3160 FROM cycle to TO cycle; returns true if there are conflicts and false
3161 if there are no conflicts. Assumes DFA is being used. */
3163 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
3167 state_reset (curr_state
);
3169 for (cycle
= from
; cycle
<= to
; cycle
++)
3171 ps_insn_ptr crr_insn
;
3172 /* Holds the remaining issue slots in the current row. */
3173 int can_issue_more
= issue_rate
;
3175 /* Walk through the DFA for the current row. */
3176 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
3178 crr_insn
= crr_insn
->next_in_row
)
3180 rtx_insn
*insn
= ps_rtl_insn (ps
, crr_insn
->id
);
3182 /* Check if there is room for the current insn. */
3183 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
3186 /* Update the DFA state and return with failure if the DFA found
3187 resource conflicts. */
3188 if (state_transition (curr_state
, insn
) >= 0)
3191 if (targetm
.sched
.variable_issue
)
3193 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
3194 insn
, can_issue_more
);
3195 /* A naked CLOBBER or USE generates no instruction, so don't
3196 let them consume issue slots. */
3197 else if (GET_CODE (PATTERN (insn
)) != USE
3198 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3202 /* Advance the DFA to the next cycle. */
3203 advance_one_cycle ();
3208 /* Checks if the given node causes resource conflicts when added to PS at
3209 cycle C. If not the node is added to PS and returned; otherwise zero
3210 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
3211 cuid N must be come before/after (respectively) the node pointed to by
3212 PS_I when scheduled in the same cycle. */
3214 ps_add_node_check_conflicts (partial_schedule_ptr ps
, int n
,
3215 int c
, sbitmap must_precede
,
3216 sbitmap must_follow
)
3218 int i
, first
, amount
, has_conflicts
= 0;
3221 /* First add the node to the PS, if this succeeds check for
3222 conflicts, trying different issue slots in the same row. */
3223 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
3224 return NULL
; /* Failed to insert the node at the given cycle. */
3228 has_conflicts
= ps_has_conflicts (ps
, c
, c
);
3229 if (ps
->history
> 0 && !has_conflicts
)
3231 /* Check all 2h+1 intervals, starting from c-2h..c up to c..2h,
3232 but not more than ii intervals. */
3233 first
= c
- ps
->history
;
3234 amount
= 2 * ps
->history
+ 1;
3235 if (amount
> ps
->ii
)
3237 for (i
= first
; i
< first
+ amount
; i
++)
3239 has_conflicts
= ps_has_conflicts (ps
,
3248 /* Try different issue slots to find one that the given node can be
3249 scheduled in without conflicts. */
3250 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
3256 remove_node_from_ps (ps
, ps_i
);
3260 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
3261 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
3265 /* Calculate the stage count of the partial schedule PS. The calculation
3266 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3268 calculate_stage_count (partial_schedule_ptr ps
, int rotation_amount
)
3270 int new_min_cycle
= PS_MIN_CYCLE (ps
) - rotation_amount
;
3271 int new_max_cycle
= PS_MAX_CYCLE (ps
) - rotation_amount
;
3272 int stage_count
= CALC_STAGE_COUNT (-1, new_min_cycle
, ps
->ii
);
3274 /* The calculation of stage count is done adding the number of stages
3275 before cycle zero and after cycle zero. */
3276 stage_count
+= CALC_STAGE_COUNT (new_max_cycle
, 0, ps
->ii
);
3281 /* Rotate the rows of PS such that insns scheduled at time
3282 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3284 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
3286 int i
, row
, backward_rotates
;
3287 int last_row
= ps
->ii
- 1;
3289 if (start_cycle
== 0)
3292 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
3294 /* Revisit later and optimize this into a single loop. */
3295 for (i
= 0; i
< backward_rotates
; i
++)
3297 ps_insn_ptr first_row
= ps
->rows
[0];
3298 int first_row_length
= ps
->rows_length
[0];
3300 for (row
= 0; row
< last_row
; row
++)
3302 ps
->rows
[row
] = ps
->rows
[row
+ 1];
3303 ps
->rows_length
[row
] = ps
->rows_length
[row
+ 1];
3306 ps
->rows
[last_row
] = first_row
;
3307 ps
->rows_length
[last_row
] = first_row_length
;
3310 ps
->max_cycle
-= start_cycle
;
3311 ps
->min_cycle
-= start_cycle
;
3314 #endif /* INSN_SCHEDULING */
3316 /* Run instruction scheduler. */
3317 /* Perform SMS module scheduling. */
3321 const pass_data pass_data_sms
=
3323 RTL_PASS
, /* type */
3325 OPTGROUP_NONE
, /* optinfo_flags */
3327 0, /* properties_required */
3328 0, /* properties_provided */
3329 0, /* properties_destroyed */
3330 0, /* todo_flags_start */
3331 TODO_df_finish
, /* todo_flags_finish */
3334 class pass_sms
: public rtl_opt_pass
3337 pass_sms (gcc::context
*ctxt
)
3338 : rtl_opt_pass (pass_data_sms
, ctxt
)
3341 /* opt_pass methods: */
3342 virtual bool gate (function
*)
3344 return (optimize
> 0 && flag_modulo_sched
);
3347 virtual unsigned int execute (function
*);
3349 }; // class pass_sms
3352 pass_sms::execute (function
*fun ATTRIBUTE_UNUSED
)
3354 #ifdef INSN_SCHEDULING
3357 /* Collect loop information to be used in SMS. */
3358 cfg_layout_initialize (0);
3361 /* Update the life information, because we add pseudos. */
3362 max_regno
= max_reg_num ();
3364 /* Finalize layout changes. */
3365 FOR_EACH_BB_FN (bb
, fun
)
3366 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3367 bb
->aux
= bb
->next_bb
;
3368 free_dominance_info (CDI_DOMINATORS
);
3369 cfg_layout_finalize ();
3370 #endif /* INSN_SCHEDULING */
3377 make_pass_sms (gcc::context
*ctxt
)
3379 return new pass_sms (ctxt
);