1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004-2014 Free Software Foundation, Inc.
3 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
26 #include "diagnostic-core.h"
29 #include "hard-reg-set.h"
39 #include "insn-config.h"
40 #include "insn-attr.h"
43 #include "sched-int.h"
50 #include "tree-pass.h"
53 #include "loop-unroll.h"
55 #ifdef INSN_SCHEDULING
57 /* This file contains the implementation of the Swing Modulo Scheduler,
58 described in the following references:
59 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
60 Lifetime--sensitive modulo scheduling in a production environment.
61 IEEE Trans. on Comps., 50(3), March 2001
62 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
63 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
64 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
66 The basic structure is:
67 1. Build a data-dependence graph (DDG) for each loop.
68 2. Use the DDG to order the insns of a loop (not in topological order
69 necessarily, but rather) trying to place each insn after all its
70 predecessors _or_ after all its successors.
71 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
72 4. Use the ordering to perform list-scheduling of the loop:
73 1. Set II = MII. We will try to schedule the loop within II cycles.
74 2. Try to schedule the insns one by one according to the ordering.
75 For each insn compute an interval of cycles by considering already-
76 scheduled preds and succs (and associated latencies); try to place
77 the insn in the cycles of this window checking for potential
78 resource conflicts (using the DFA interface).
79 Note: this is different from the cycle-scheduling of schedule_insns;
80 here the insns are not scheduled monotonically top-down (nor bottom-
82 3. If failed in scheduling all insns - bump II++ and try again, unless
83 II reaches an upper bound MaxII, in which case report failure.
84 5. If we succeeded in scheduling the loop within II cycles, we now
85 generate prolog and epilog, decrease the counter of the loop, and
86 perform modulo variable expansion for live ranges that span more than
87 II cycles (i.e. use register copies to prevent a def from overwriting
88 itself before reaching the use).
90 SMS works with countable loops (1) whose control part can be easily
91 decoupled from the rest of the loop and (2) whose loop count can
92 be easily adjusted. This is because we peel a constant number of
93 iterations into a prologue and epilogue for which we want to avoid
94 emitting the control part, and a kernel which is to iterate that
95 constant number of iterations less than the original loop. So the
96 control part should be a set of insns clearly identified and having
97 its own iv, not otherwise used in the loop (at-least for now), which
98 initializes a register before the loop to the number of iterations.
99 Currently SMS relies on the do-loop pattern to recognize such loops,
100 where (1) the control part comprises of all insns defining and/or
101 using a certain 'count' register and (2) the loop count can be
102 adjusted by modifying this register prior to the loop.
103 TODO: Rely on cfgloop analysis instead. */
105 /* This page defines partial-schedule structures and functions for
106 modulo scheduling. */
108 typedef struct partial_schedule
*partial_schedule_ptr
;
109 typedef struct ps_insn
*ps_insn_ptr
;
111 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
112 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
114 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
115 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
117 /* Perform signed modulo, always returning a non-negative value. */
118 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
120 /* The number of different iterations the nodes in ps span, assuming
121 the stage boundaries are placed efficiently. */
122 #define CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \
124 /* The stage count of ps. */
125 #define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count)
127 /* A single instruction in the partial schedule. */
130 /* Identifies the instruction to be scheduled. Values smaller than
131 the ddg's num_nodes refer directly to ddg nodes. A value of
132 X - num_nodes refers to register move X. */
135 /* The (absolute) cycle in which the PS instruction is scheduled.
136 Same as SCHED_TIME (node). */
139 /* The next/prev PS_INSN in the same row. */
140 ps_insn_ptr next_in_row
,
145 /* Information about a register move that has been added to a partial
147 struct ps_reg_move_info
149 /* The source of the move is defined by the ps_insn with id DEF.
150 The destination is used by the ps_insns with the ids in USES. */
154 /* The original form of USES' instructions used OLD_REG, but they
155 should now use NEW_REG. */
159 /* The number of consecutive stages that the move occupies. */
160 int num_consecutive_stages
;
162 /* An instruction that sets NEW_REG to the correct value. The first
163 move associated with DEF will have an rhs of OLD_REG; later moves
164 use the result of the previous move. */
168 typedef struct ps_reg_move_info ps_reg_move_info
;
170 /* Holds the partial schedule as an array of II rows. Each entry of the
171 array points to a linked list of PS_INSNs, which represents the
172 instructions that are scheduled for that row. */
173 struct partial_schedule
175 int ii
; /* Number of rows in the partial schedule. */
176 int history
; /* Threshold for conflict checking using DFA. */
178 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
181 /* All the moves added for this partial schedule. Index X has
182 a ps_insn id of X + g->num_nodes. */
183 vec
<ps_reg_move_info
> reg_moves
;
185 /* rows_length[i] holds the number of instructions in the row.
186 It is used only (as an optimization) to back off quickly from
187 trying to schedule a node in a full row; that is, to avoid running
188 through futile DFA state transitions. */
191 /* The earliest absolute cycle of an insn in the partial schedule. */
194 /* The latest absolute cycle of an insn in the partial schedule. */
197 ddg_ptr g
; /* The DDG of the insns in the partial schedule. */
199 int stage_count
; /* The stage count of the partial schedule. */
203 static partial_schedule_ptr
create_partial_schedule (int ii
, ddg_ptr
, int history
);
204 static void free_partial_schedule (partial_schedule_ptr
);
205 static void reset_partial_schedule (partial_schedule_ptr
, int new_ii
);
206 void print_partial_schedule (partial_schedule_ptr
, FILE *);
207 static void verify_partial_schedule (partial_schedule_ptr
, sbitmap
);
208 static ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr
,
209 int, int, sbitmap
, sbitmap
);
210 static void rotate_partial_schedule (partial_schedule_ptr
, int);
211 void set_row_column_for_ps (partial_schedule_ptr
);
212 static void ps_insert_empty_row (partial_schedule_ptr
, int, sbitmap
);
213 static int compute_split_row (sbitmap
, int, int, int, ddg_node_ptr
);
216 /* This page defines constants and structures for the modulo scheduling
219 static int sms_order_nodes (ddg_ptr
, int, int *, int *);
220 static void set_node_sched_params (ddg_ptr
);
221 static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr
, int, int, int *);
222 static void permute_partial_schedule (partial_schedule_ptr
, rtx_insn
*);
223 static void generate_prolog_epilog (partial_schedule_ptr
, struct loop
*,
225 static int calculate_stage_count (partial_schedule_ptr
, int);
226 static void calculate_must_precede_follow (ddg_node_ptr
, int, int,
227 int, int, sbitmap
, sbitmap
, sbitmap
);
228 static int get_sched_window (partial_schedule_ptr
, ddg_node_ptr
,
229 sbitmap
, int, int *, int *, int *);
230 static bool try_scheduling_node_in_cycle (partial_schedule_ptr
, int, int,
231 sbitmap
, int *, sbitmap
, sbitmap
);
232 static void remove_node_from_ps (partial_schedule_ptr
, ps_insn_ptr
);
234 #define NODE_ASAP(node) ((node)->aux.count)
236 #define SCHED_PARAMS(x) (&node_sched_param_vec[x])
237 #define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
238 #define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
239 #define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
240 #define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
242 /* The scheduling parameters held for each node. */
243 typedef struct node_sched_params
245 int time
; /* The absolute scheduling cycle. */
247 int row
; /* Holds time % ii. */
248 int stage
; /* Holds time / ii. */
250 /* The column of a node inside the ps. If nodes u, v are on the same row,
251 u will precede v if column (u) < column (v). */
253 } *node_sched_params_ptr
;
255 typedef struct node_sched_params node_sched_params
;
257 /* The following three functions are copied from the current scheduler
258 code in order to use sched_analyze() for computing the dependencies.
259 They are used when initializing the sched_info structure. */
261 sms_print_insn (const rtx_insn
*insn
, int aligned ATTRIBUTE_UNUSED
)
265 sprintf (tmp
, "i%4d", INSN_UID (insn
));
270 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
271 regset used ATTRIBUTE_UNUSED
)
275 static struct common_sched_info_def sms_common_sched_info
;
277 static struct sched_deps_info_def sms_sched_deps_info
=
279 compute_jump_reg_dependencies
,
280 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
285 static struct haifa_sched_info sms_sched_info
=
294 NULL
, /* insn_finishes_block_p */
299 NULL
, NULL
, NULL
, NULL
,
304 /* Partial schedule instruction ID in PS is a register move. Return
305 information about it. */
306 static struct ps_reg_move_info
*
307 ps_reg_move (partial_schedule_ptr ps
, int id
)
309 gcc_checking_assert (id
>= ps
->g
->num_nodes
);
310 return &ps
->reg_moves
[id
- ps
->g
->num_nodes
];
313 /* Return the rtl instruction that is being scheduled by partial schedule
314 instruction ID, which belongs to schedule PS. */
316 ps_rtl_insn (partial_schedule_ptr ps
, int id
)
318 if (id
< ps
->g
->num_nodes
)
319 return ps
->g
->nodes
[id
].insn
;
321 return ps_reg_move (ps
, id
)->insn
;
324 /* Partial schedule instruction ID, which belongs to PS, occurred in
325 the original (unscheduled) loop. Return the first instruction
326 in the loop that was associated with ps_rtl_insn (PS, ID).
327 If the instruction had some notes before it, this is the first
330 ps_first_note (partial_schedule_ptr ps
, int id
)
332 gcc_assert (id
< ps
->g
->num_nodes
);
333 return ps
->g
->nodes
[id
].first_note
;
336 /* Return the number of consecutive stages that are occupied by
337 partial schedule instruction ID in PS. */
339 ps_num_consecutive_stages (partial_schedule_ptr ps
, int id
)
341 if (id
< ps
->g
->num_nodes
)
344 return ps_reg_move (ps
, id
)->num_consecutive_stages
;
347 /* Given HEAD and TAIL which are the first and last insns in a loop;
348 return the register which controls the loop. Return zero if it has
349 more than one occurrence in the loop besides the control part or the
350 do-loop pattern is not of the form we expect. */
352 doloop_register_get (rtx_insn
*head ATTRIBUTE_UNUSED
, rtx_insn
*tail ATTRIBUTE_UNUSED
)
354 #ifdef HAVE_doloop_end
356 rtx_insn
*insn
, *first_insn_not_to_check
;
361 /* TODO: Free SMS's dependence on doloop_condition_get. */
362 condition
= doloop_condition_get (tail
);
366 if (REG_P (XEXP (condition
, 0)))
367 reg
= XEXP (condition
, 0);
368 else if (GET_CODE (XEXP (condition
, 0)) == PLUS
369 && REG_P (XEXP (XEXP (condition
, 0), 0)))
370 reg
= XEXP (XEXP (condition
, 0), 0);
374 /* Check that the COUNT_REG has no other occurrences in the loop
375 until the decrement. We assume the control part consists of
376 either a single (parallel) branch-on-count or a (non-parallel)
377 branch immediately preceded by a single (decrement) insn. */
378 first_insn_not_to_check
= (GET_CODE (PATTERN (tail
)) == PARALLEL
? tail
379 : prev_nondebug_insn (tail
));
381 for (insn
= head
; insn
!= first_insn_not_to_check
; insn
= NEXT_INSN (insn
))
382 if (!DEBUG_INSN_P (insn
) && reg_mentioned_p (reg
, insn
))
386 fprintf (dump_file
, "SMS count_reg found ");
387 print_rtl_single (dump_file
, reg
);
388 fprintf (dump_file
, " outside control in insn:\n");
389 print_rtl_single (dump_file
, insn
);
401 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
402 that the number of iterations is a compile-time constant. If so,
403 return the rtx_insn that sets COUNT_REG to a constant, and set COUNT to
404 this constant. Otherwise return 0. */
406 const_iteration_count (rtx count_reg
, basic_block pre_header
,
410 rtx_insn
*head
, *tail
;
415 get_ebb_head_tail (pre_header
, pre_header
, &head
, &tail
);
417 for (insn
= tail
; insn
!= PREV_INSN (head
); insn
= PREV_INSN (insn
))
418 if (NONDEBUG_INSN_P (insn
) && single_set (insn
) &&
419 rtx_equal_p (count_reg
, SET_DEST (single_set (insn
))))
421 rtx pat
= single_set (insn
);
423 if (CONST_INT_P (SET_SRC (pat
)))
425 *count
= INTVAL (SET_SRC (pat
));
435 /* A very simple resource-based lower bound on the initiation interval.
436 ??? Improve the accuracy of this bound by considering the
437 utilization of various units. */
441 if (targetm
.sched
.sms_res_mii
)
442 return targetm
.sched
.sms_res_mii (g
);
444 return ((g
->num_nodes
- g
->num_debug
) / issue_rate
);
448 /* A vector that contains the sched data for each ps_insn. */
449 static vec
<node_sched_params
> node_sched_param_vec
;
451 /* Allocate sched_params for each node and initialize it. */
453 set_node_sched_params (ddg_ptr g
)
455 node_sched_param_vec
.truncate (0);
456 node_sched_param_vec
.safe_grow_cleared (g
->num_nodes
);
459 /* Make sure that node_sched_param_vec has an entry for every move in PS. */
461 extend_node_sched_params (partial_schedule_ptr ps
)
463 node_sched_param_vec
.safe_grow_cleared (ps
->g
->num_nodes
464 + ps
->reg_moves
.length ());
467 /* Update the sched_params (time, row and stage) for node U using the II,
468 the CYCLE of U and MIN_CYCLE.
469 We're not simply taking the following
470 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
471 because the stages may not be aligned on cycle 0. */
473 update_node_sched_params (int u
, int ii
, int cycle
, int min_cycle
)
475 int sc_until_cycle_zero
;
478 SCHED_TIME (u
) = cycle
;
479 SCHED_ROW (u
) = SMODULO (cycle
, ii
);
481 /* The calculation of stage count is done adding the number
482 of stages before cycle zero and after cycle zero. */
483 sc_until_cycle_zero
= CALC_STAGE_COUNT (-1, min_cycle
, ii
);
485 if (SCHED_TIME (u
) < 0)
487 stage
= CALC_STAGE_COUNT (-1, SCHED_TIME (u
), ii
);
488 SCHED_STAGE (u
) = sc_until_cycle_zero
- stage
;
492 stage
= CALC_STAGE_COUNT (SCHED_TIME (u
), 0, ii
);
493 SCHED_STAGE (u
) = sc_until_cycle_zero
+ stage
- 1;
498 print_node_sched_params (FILE *file
, int num_nodes
, partial_schedule_ptr ps
)
504 for (i
= 0; i
< num_nodes
; i
++)
506 node_sched_params_ptr nsp
= SCHED_PARAMS (i
);
508 fprintf (file
, "Node = %d; INSN = %d\n", i
,
509 INSN_UID (ps_rtl_insn (ps
, i
)));
510 fprintf (file
, " asap = %d:\n", NODE_ASAP (&ps
->g
->nodes
[i
]));
511 fprintf (file
, " time = %d:\n", nsp
->time
);
512 fprintf (file
, " stage = %d:\n", nsp
->stage
);
516 /* Set SCHED_COLUMN for each instruction in row ROW of PS. */
518 set_columns_for_row (partial_schedule_ptr ps
, int row
)
520 ps_insn_ptr cur_insn
;
524 for (cur_insn
= ps
->rows
[row
]; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
525 SCHED_COLUMN (cur_insn
->id
) = column
++;
528 /* Set SCHED_COLUMN for each instruction in PS. */
530 set_columns_for_ps (partial_schedule_ptr ps
)
534 for (row
= 0; row
< ps
->ii
; row
++)
535 set_columns_for_row (ps
, row
);
538 /* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
539 Its single predecessor has already been scheduled, as has its
540 ddg node successors. (The move may have also another move as its
541 successor, in which case that successor will be scheduled later.)
543 The move is part of a chain that satisfies register dependencies
544 between a producing ddg node and various consuming ddg nodes.
545 If some of these dependencies have a distance of 1 (meaning that
546 the use is upward-exposed) then DISTANCE1_USES is nonnull and
547 contains the set of uses with distance-1 dependencies.
548 DISTANCE1_USES is null otherwise.
550 MUST_FOLLOW is a scratch bitmap that is big enough to hold
551 all current ps_insn ids.
553 Return true on success. */
555 schedule_reg_move (partial_schedule_ptr ps
, int i_reg_move
,
556 sbitmap distance1_uses
, sbitmap must_follow
)
559 int this_time
, this_distance
, this_start
, this_end
, this_latency
;
560 int start
, end
, c
, ii
;
561 sbitmap_iterator sbi
;
562 ps_reg_move_info
*move
;
566 move
= ps_reg_move (ps
, i_reg_move
);
570 fprintf (dump_file
, "Scheduling register move INSN %d; ii = %d"
571 ", min cycle = %d\n\n", INSN_UID (move
->insn
), ii
,
573 print_rtl_single (dump_file
, move
->insn
);
574 fprintf (dump_file
, "\n%11s %11s %5s\n", "start", "end", "time");
575 fprintf (dump_file
, "=========== =========== =====\n");
581 /* For dependencies of distance 1 between a producer ddg node A
582 and consumer ddg node B, we have a chain of dependencies:
584 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
586 where Mi is the ith move. For dependencies of distance 0 between
587 a producer ddg node A and consumer ddg node C, we have a chain of
590 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
592 where Mi' occupies the same position as Mi but occurs a stage later.
593 We can only schedule each move once, so if we have both types of
594 chain, we model the second as:
596 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
598 First handle the dependencies between the previously-scheduled
599 predecessor and the move. */
600 this_insn
= ps_rtl_insn (ps
, move
->def
);
601 this_latency
= insn_latency (this_insn
, move
->insn
);
602 this_distance
= distance1_uses
&& move
->def
< ps
->g
->num_nodes
? 1 : 0;
603 this_time
= SCHED_TIME (move
->def
) - this_distance
* ii
;
604 this_start
= this_time
+ this_latency
;
605 this_end
= this_time
+ ii
;
607 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
608 this_start
, this_end
, SCHED_TIME (move
->def
),
609 INSN_UID (this_insn
), this_latency
, this_distance
,
610 INSN_UID (move
->insn
));
612 if (start
< this_start
)
617 /* Handle the dependencies between the move and previously-scheduled
619 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, u
, sbi
)
621 this_insn
= ps_rtl_insn (ps
, u
);
622 this_latency
= insn_latency (move
->insn
, this_insn
);
623 if (distance1_uses
&& !bitmap_bit_p (distance1_uses
, u
))
627 this_time
= SCHED_TIME (u
) + this_distance
* ii
;
628 this_start
= this_time
- ii
;
629 this_end
= this_time
- this_latency
;
631 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
632 this_start
, this_end
, SCHED_TIME (u
), INSN_UID (move
->insn
),
633 this_latency
, this_distance
, INSN_UID (this_insn
));
635 if (start
< this_start
)
643 fprintf (dump_file
, "----------- ----------- -----\n");
644 fprintf (dump_file
, "%11d %11d %5s %s\n", start
, end
, "", "(max, min)");
647 bitmap_clear (must_follow
);
648 bitmap_set_bit (must_follow
, move
->def
);
650 start
= MAX (start
, end
- (ii
- 1));
651 for (c
= end
; c
>= start
; c
--)
653 psi
= ps_add_node_check_conflicts (ps
, i_reg_move
, c
,
654 move
->uses
, must_follow
);
657 update_node_sched_params (i_reg_move
, ii
, c
, PS_MIN_CYCLE (ps
));
659 fprintf (dump_file
, "\nScheduled register move INSN %d at"
660 " time %d, row %d\n\n", INSN_UID (move
->insn
), c
,
661 SCHED_ROW (i_reg_move
));
667 fprintf (dump_file
, "\nNo available slot\n\n");
673 Breaking intra-loop register anti-dependences:
674 Each intra-loop register anti-dependence implies a cross-iteration true
675 dependence of distance 1. Therefore, we can remove such false dependencies
676 and figure out if the partial schedule broke them by checking if (for a
677 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
678 if so generate a register move. The number of such moves is equal to:
679 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
680 nreg_moves = ----------------------------------- + 1 - { dependence.
684 schedule_reg_moves (partial_schedule_ptr ps
)
690 for (i
= 0; i
< g
->num_nodes
; i
++)
692 ddg_node_ptr u
= &g
->nodes
[i
];
694 int nreg_moves
= 0, i_reg_move
;
695 rtx prev_reg
, old_reg
;
699 sbitmap distance1_uses
;
700 rtx set
= single_set (u
->insn
);
702 /* Skip instructions that do not set a register. */
703 if ((set
&& !REG_P (SET_DEST (set
))))
706 /* Compute the number of reg_moves needed for u, by looking at life
707 ranges started at u (excluding self-loops). */
708 distances
[0] = distances
[1] = false;
709 for (e
= u
->out
; e
; e
= e
->next_out
)
710 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
712 int nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
713 - SCHED_TIME (e
->src
->cuid
)) / ii
;
715 if (e
->distance
== 1)
716 nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
717 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
719 /* If dest precedes src in the schedule of the kernel, then dest
720 will read before src writes and we can save one reg_copy. */
721 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
722 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
725 if (nreg_moves4e
>= 1)
727 /* !single_set instructions are not supported yet and
728 thus we do not except to encounter them in the loop
729 except from the doloop part. For the latter case
730 we assume no regmoves are generated as the doloop
731 instructions are tied to the branch with an edge. */
733 /* If the instruction contains auto-inc register then
734 validate that the regmov is being generated for the
735 target regsiter rather then the inc'ed register. */
736 gcc_assert (!autoinc_var_is_used_p (u
->insn
, e
->dest
->insn
));
741 gcc_assert (e
->distance
< 2);
742 distances
[e
->distance
] = true;
744 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
750 /* Create NREG_MOVES register moves. */
751 first_move
= ps
->reg_moves
.length ();
752 ps
->reg_moves
.safe_grow_cleared (first_move
+ nreg_moves
);
753 extend_node_sched_params (ps
);
755 /* Record the moves associated with this node. */
756 first_move
+= ps
->g
->num_nodes
;
758 /* Generate each move. */
759 old_reg
= prev_reg
= SET_DEST (single_set (u
->insn
));
760 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
762 ps_reg_move_info
*move
= ps_reg_move (ps
, first_move
+ i_reg_move
);
764 move
->def
= i_reg_move
> 0 ? first_move
+ i_reg_move
- 1 : i
;
765 move
->uses
= sbitmap_alloc (first_move
+ nreg_moves
);
766 move
->old_reg
= old_reg
;
767 move
->new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
768 move
->num_consecutive_stages
= distances
[0] && distances
[1] ? 2 : 1;
769 move
->insn
= as_a
<rtx_insn
*> (gen_move_insn (move
->new_reg
,
770 copy_rtx (prev_reg
)));
771 bitmap_clear (move
->uses
);
773 prev_reg
= move
->new_reg
;
776 distance1_uses
= distances
[1] ? sbitmap_alloc (g
->num_nodes
) : NULL
;
779 bitmap_clear (distance1_uses
);
781 /* Every use of the register defined by node may require a different
782 copy of this register, depending on the time the use is scheduled.
783 Record which uses require which move results. */
784 for (e
= u
->out
; e
; e
= e
->next_out
)
785 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
787 int dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
788 - SCHED_TIME (e
->src
->cuid
)) / ii
;
790 if (e
->distance
== 1)
791 dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
792 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
794 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
795 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
800 ps_reg_move_info
*move
;
802 move
= ps_reg_move (ps
, first_move
+ dest_copy
- 1);
803 bitmap_set_bit (move
->uses
, e
->dest
->cuid
);
804 if (e
->distance
== 1)
805 bitmap_set_bit (distance1_uses
, e
->dest
->cuid
);
809 must_follow
= sbitmap_alloc (first_move
+ nreg_moves
);
810 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
811 if (!schedule_reg_move (ps
, first_move
+ i_reg_move
,
812 distance1_uses
, must_follow
))
814 sbitmap_free (must_follow
);
816 sbitmap_free (distance1_uses
);
817 if (i_reg_move
< nreg_moves
)
823 /* Emit the moves associatied with PS. Apply the substitutions
824 associated with them. */
826 apply_reg_moves (partial_schedule_ptr ps
)
828 ps_reg_move_info
*move
;
831 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
834 sbitmap_iterator sbi
;
836 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, i_use
, sbi
)
838 replace_rtx (ps
->g
->nodes
[i_use
].insn
, move
->old_reg
, move
->new_reg
);
839 df_insn_rescan (ps
->g
->nodes
[i_use
].insn
);
844 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
845 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
846 will move to cycle zero. */
848 reset_sched_times (partial_schedule_ptr ps
, int amount
)
852 ps_insn_ptr crr_insn
;
854 for (row
= 0; row
< ii
; row
++)
855 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
857 int u
= crr_insn
->id
;
858 int normalized_time
= SCHED_TIME (u
) - amount
;
859 int new_min_cycle
= PS_MIN_CYCLE (ps
) - amount
;
863 /* Print the scheduling times after the rotation. */
864 rtx_insn
*insn
= ps_rtl_insn (ps
, u
);
866 fprintf (dump_file
, "crr_insn->node=%d (insn id %d), "
867 "crr_insn->cycle=%d, min_cycle=%d", u
,
868 INSN_UID (insn
), normalized_time
, new_min_cycle
);
870 fprintf (dump_file
, " (branch)");
871 fprintf (dump_file
, "\n");
874 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
875 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
877 crr_insn
->cycle
= normalized_time
;
878 update_node_sched_params (u
, ii
, normalized_time
, new_min_cycle
);
882 /* Permute the insns according to their order in PS, from row 0 to
883 row ii-1, and position them right before LAST. This schedules
884 the insns of the loop kernel. */
886 permute_partial_schedule (partial_schedule_ptr ps
, rtx_insn
*last
)
892 for (row
= 0; row
< ii
; row
++)
893 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
895 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_ij
->id
);
897 if (PREV_INSN (last
) != insn
)
899 if (ps_ij
->id
< ps
->g
->num_nodes
)
900 reorder_insns_nobb (ps_first_note (ps
, ps_ij
->id
), insn
,
903 add_insn_before (insn
, last
, NULL
);
908 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
909 respectively only if cycle C falls on the border of the scheduling
910 window boundaries marked by START and END cycles. STEP is the
911 direction of the window. */
913 set_must_precede_follow (sbitmap
*tmp_follow
, sbitmap must_follow
,
914 sbitmap
*tmp_precede
, sbitmap must_precede
, int c
,
915 int start
, int end
, int step
)
923 *tmp_precede
= must_precede
;
924 else /* step == -1. */
925 *tmp_follow
= must_follow
;
930 *tmp_follow
= must_follow
;
931 else /* step == -1. */
932 *tmp_precede
= must_precede
;
937 /* Return True if the branch can be moved to row ii-1 while
938 normalizing the partial schedule PS to start from cycle zero and thus
939 optimize the SC. Otherwise return False. */
941 optimize_sc (partial_schedule_ptr ps
, ddg_ptr g
)
943 int amount
= PS_MIN_CYCLE (ps
);
944 sbitmap sched_nodes
= sbitmap_alloc (g
->num_nodes
);
945 int start
, end
, step
;
948 int stage_count
, stage_count_curr
;
950 /* Compare the SC after normalization and SC after bringing the branch
951 to row ii-1. If they are equal just bail out. */
952 stage_count
= calculate_stage_count (ps
, amount
);
954 calculate_stage_count (ps
, SCHED_TIME (g
->closing_branch
->cuid
) - (ii
- 1));
956 if (stage_count
== stage_count_curr
)
959 fprintf (dump_file
, "SMS SC already optimized.\n");
967 fprintf (dump_file
, "SMS Trying to optimize branch location\n");
968 fprintf (dump_file
, "SMS partial schedule before trial:\n");
969 print_partial_schedule (ps
, dump_file
);
972 /* First, normalize the partial scheduling. */
973 reset_sched_times (ps
, amount
);
974 rotate_partial_schedule (ps
, amount
);
978 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
980 print_partial_schedule (ps
, dump_file
);
983 if (SMODULO (SCHED_TIME (g
->closing_branch
->cuid
), ii
) == ii
- 1)
989 bitmap_ones (sched_nodes
);
991 /* Calculate the new placement of the branch. It should be in row
992 ii-1 and fall into it's scheduling window. */
993 if (get_sched_window (ps
, g
->closing_branch
, sched_nodes
, ii
, &start
,
997 ps_insn_ptr next_ps_i
;
998 int branch_cycle
= SCHED_TIME (g
->closing_branch
->cuid
);
999 int row
= SMODULO (branch_cycle
, ps
->ii
);
1001 sbitmap must_precede
, must_follow
, tmp_precede
, tmp_follow
;
1005 fprintf (dump_file
, "\nTrying to schedule node %d "
1006 "INSN = %d in (%d .. %d) step %d\n",
1007 g
->closing_branch
->cuid
,
1008 (INSN_UID (g
->closing_branch
->insn
)), start
, end
, step
);
1010 gcc_assert ((step
> 0 && start
< end
) || (step
< 0 && start
> end
));
1013 c
= start
+ ii
- SMODULO (start
, ii
) - 1;
1014 gcc_assert (c
>= start
);
1020 "SMS failed to schedule branch at cycle: %d\n", c
);
1026 c
= start
- SMODULO (start
, ii
) - 1;
1027 gcc_assert (c
<= start
);
1033 "SMS failed to schedule branch at cycle: %d\n", c
);
1039 must_precede
= sbitmap_alloc (g
->num_nodes
);
1040 must_follow
= sbitmap_alloc (g
->num_nodes
);
1042 /* Try to schedule the branch is it's new cycle. */
1043 calculate_must_precede_follow (g
->closing_branch
, start
, end
,
1044 step
, ii
, sched_nodes
,
1045 must_precede
, must_follow
);
1047 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1048 must_precede
, c
, start
, end
, step
);
1050 /* Find the element in the partial schedule related to the closing
1051 branch so we can remove it from it's current cycle. */
1052 for (next_ps_i
= ps
->rows
[row
];
1053 next_ps_i
; next_ps_i
= next_ps_i
->next_in_row
)
1054 if (next_ps_i
->id
== g
->closing_branch
->cuid
)
1057 remove_node_from_ps (ps
, next_ps_i
);
1059 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
, c
,
1060 sched_nodes
, &num_splits
,
1061 tmp_precede
, tmp_follow
);
1062 gcc_assert (num_splits
== 0);
1067 "SMS failed to schedule branch at cycle: %d, "
1068 "bringing it back to cycle %d\n", c
, branch_cycle
);
1070 /* The branch was failed to be placed in row ii - 1.
1071 Put it back in it's original place in the partial
1073 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1074 must_precede
, branch_cycle
, start
, end
,
1077 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
,
1078 branch_cycle
, sched_nodes
,
1079 &num_splits
, tmp_precede
,
1081 gcc_assert (success
&& (num_splits
== 0));
1086 /* The branch is placed in row ii - 1. */
1089 "SMS success in moving branch to cycle %d\n", c
);
1091 update_node_sched_params (g
->closing_branch
->cuid
, ii
, c
,
1096 free (must_precede
);
1106 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
1107 int to_stage
, rtx count_reg
)
1112 for (row
= 0; row
< ps
->ii
; row
++)
1113 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
1116 int first_u
, last_u
;
1119 /* Do not duplicate any insn which refers to count_reg as it
1120 belongs to the control part.
1121 The closing branch is scheduled as well and thus should
1123 TODO: This should be done by analyzing the control part of
1125 u_insn
= ps_rtl_insn (ps
, u
);
1126 if (reg_mentioned_p (count_reg
, u_insn
)
1130 first_u
= SCHED_STAGE (u
);
1131 last_u
= first_u
+ ps_num_consecutive_stages (ps
, u
) - 1;
1132 if (from_stage
<= last_u
&& to_stage
>= first_u
)
1134 if (u
< ps
->g
->num_nodes
)
1135 duplicate_insn_chain (ps_first_note (ps
, u
), u_insn
);
1137 emit_insn (copy_rtx (PATTERN (u_insn
)));
1143 /* Generate the instructions (including reg_moves) for prolog & epilog. */
1145 generate_prolog_epilog (partial_schedule_ptr ps
, struct loop
*loop
,
1146 rtx count_reg
, rtx count_init
)
1149 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
1152 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1157 /* Generate instructions at the beginning of the prolog to
1158 adjust the loop count by STAGE_COUNT. If loop count is constant
1159 (count_init), this constant is adjusted by STAGE_COUNT in
1160 generate_prolog_epilog function. */
1161 rtx sub_reg
= NULL_RTX
;
1163 sub_reg
= expand_simple_binop (GET_MODE (count_reg
), MINUS
, count_reg
,
1164 gen_int_mode (last_stage
,
1165 GET_MODE (count_reg
)),
1166 count_reg
, 1, OPTAB_DIRECT
);
1167 gcc_assert (REG_P (sub_reg
));
1168 if (REGNO (sub_reg
) != REGNO (count_reg
))
1169 emit_move_insn (count_reg
, sub_reg
);
1172 for (i
= 0; i
< last_stage
; i
++)
1173 duplicate_insns_of_cycles (ps
, 0, i
, count_reg
);
1175 /* Put the prolog on the entry edge. */
1176 e
= loop_preheader_edge (loop
);
1177 split_edge_and_insert (e
, get_insns ());
1178 if (!flag_resched_modulo_sched
)
1179 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1183 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1186 for (i
= 0; i
< last_stage
; i
++)
1187 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, count_reg
);
1189 /* Put the epilogue on the exit edge. */
1190 gcc_assert (single_exit (loop
));
1191 e
= single_exit (loop
);
1192 split_edge_and_insert (e
, get_insns ());
1193 if (!flag_resched_modulo_sched
)
1194 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1199 /* Mark LOOP as software pipelined so the later
1200 scheduling passes don't touch it. */
1202 mark_loop_unsched (struct loop
*loop
)
1205 basic_block
*bbs
= get_loop_body (loop
);
1207 for (i
= 0; i
< loop
->num_nodes
; i
++)
1208 bbs
[i
]->flags
|= BB_DISABLE_SCHEDULE
;
1213 /* Return true if all the BBs of the loop are empty except the
1216 loop_single_full_bb_p (struct loop
*loop
)
1219 basic_block
*bbs
= get_loop_body (loop
);
1221 for (i
= 0; i
< loop
->num_nodes
; i
++)
1223 rtx_insn
*head
, *tail
;
1224 bool empty_bb
= true;
1226 if (bbs
[i
] == loop
->header
)
1229 /* Make sure that basic blocks other than the header
1230 have only notes labels or jumps. */
1231 get_ebb_head_tail (bbs
[i
], bbs
[i
], &head
, &tail
);
1232 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
1234 if (NOTE_P (head
) || LABEL_P (head
)
1235 || (INSN_P (head
) && (DEBUG_INSN_P (head
) || JUMP_P (head
))))
1251 /* Dump file:line from INSN's location info to dump_file. */
1254 dump_insn_location (rtx_insn
*insn
)
1256 if (dump_file
&& INSN_HAS_LOCATION (insn
))
1258 expanded_location xloc
= insn_location (insn
);
1259 fprintf (dump_file
, " %s:%i", xloc
.file
, xloc
.line
);
1263 /* A simple loop from SMS point of view; it is a loop that is composed of
1264 either a single basic block or two BBs - a header and a latch. */
1265 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1266 && (EDGE_COUNT (loop->latch->preds) == 1) \
1267 && (EDGE_COUNT (loop->latch->succs) == 1))
1269 /* Return true if the loop is in its canonical form and false if not.
1270 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1272 loop_canon_p (struct loop
*loop
)
1275 if (loop
->inner
|| !loop_outer (loop
))
1278 fprintf (dump_file
, "SMS loop inner or !loop_outer\n");
1282 if (!single_exit (loop
))
1286 rtx_insn
*insn
= BB_END (loop
->header
);
1288 fprintf (dump_file
, "SMS loop many exits");
1289 dump_insn_location (insn
);
1290 fprintf (dump_file
, "\n");
1295 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
1299 rtx_insn
*insn
= BB_END (loop
->header
);
1301 fprintf (dump_file
, "SMS loop many BBs.");
1302 dump_insn_location (insn
);
1303 fprintf (dump_file
, "\n");
1311 /* If there are more than one entry for the loop,
1312 make it one by splitting the first entry edge and
1313 redirecting the others to the new BB. */
1315 canon_loop (struct loop
*loop
)
1320 /* Avoid annoying special cases of edges going to exit
1322 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1323 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
1326 if (loop
->latch
== loop
->header
1327 || EDGE_COUNT (loop
->latch
->succs
) > 1)
1329 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
1330 if (e
->src
== loop
->latch
)
1338 setup_sched_infos (void)
1340 memcpy (&sms_common_sched_info
, &haifa_common_sched_info
,
1341 sizeof (sms_common_sched_info
));
1342 sms_common_sched_info
.sched_pass_id
= SCHED_SMS_PASS
;
1343 common_sched_info
= &sms_common_sched_info
;
1345 sched_deps_info
= &sms_sched_deps_info
;
1346 current_sched_info
= &sms_sched_info
;
1349 /* Probability in % that the sms-ed loop rolls enough so that optimized
1350 version may be entered. Just a guess. */
1351 #define PROB_SMS_ENOUGH_ITERATIONS 80
1353 /* Used to calculate the upper bound of ii. */
1354 #define MAXII_FACTOR 2
1356 /* Main entry point, perform SMS scheduling on the loops of the function
1357 that consist of single basic blocks. */
1364 int maxii
, max_asap
;
1365 partial_schedule_ptr ps
;
1366 basic_block bb
= NULL
;
1368 basic_block condition_bb
= NULL
;
1370 gcov_type trip_count
= 0;
1372 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1373 | LOOPS_HAVE_RECORDED_EXITS
);
1374 if (number_of_loops (cfun
) <= 1)
1376 loop_optimizer_finalize ();
1377 return; /* There are no loops to schedule. */
1380 /* Initialize issue_rate. */
1381 if (targetm
.sched
.issue_rate
)
1383 int temp
= reload_completed
;
1385 reload_completed
= 1;
1386 issue_rate
= targetm
.sched
.issue_rate ();
1387 reload_completed
= temp
;
1392 /* Initialize the scheduler. */
1393 setup_sched_infos ();
1394 haifa_sched_init ();
1396 /* Allocate memory to hold the DDG array one entry for each loop.
1397 We use loop->num as index into this array. */
1398 g_arr
= XCNEWVEC (ddg_ptr
, number_of_loops (cfun
));
1402 fprintf (dump_file
, "\n\nSMS analysis phase\n");
1403 fprintf (dump_file
, "===================\n\n");
1406 /* Build DDGs for all the relevant loops and hold them in G_ARR
1407 indexed by the loop index. */
1408 FOR_EACH_LOOP (loop
, 0)
1410 rtx_insn
*head
, *tail
;
1413 /* For debugging. */
1414 if (dbg_cnt (sms_sched_loop
) == false)
1417 fprintf (dump_file
, "SMS reached max limit... \n");
1424 rtx_insn
*insn
= BB_END (loop
->header
);
1426 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1427 dump_insn_location (insn
);
1428 fprintf (dump_file
, "\n");
1431 if (! loop_canon_p (loop
))
1434 if (! loop_single_full_bb_p (loop
))
1437 fprintf (dump_file
, "SMS not loop_single_full_bb_p\n");
1443 get_ebb_head_tail (bb
, bb
, &head
, &tail
);
1444 latch_edge
= loop_latch_edge (loop
);
1445 gcc_assert (single_exit (loop
));
1446 if (single_exit (loop
)->count
)
1447 trip_count
= latch_edge
->count
/ single_exit (loop
)->count
;
1449 /* Perform SMS only on loops that their average count is above threshold. */
1451 if ( latch_edge
->count
1452 && (latch_edge
->count
< single_exit (loop
)->count
* SMS_LOOP_AVERAGE_COUNT_THRESHOLD
))
1456 dump_insn_location (tail
);
1457 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1458 if (profile_info
&& flag_branch_probabilities
)
1460 fprintf (dump_file
, "SMS loop-count ");
1461 fprintf (dump_file
, "%"PRId64
,
1462 (int64_t) bb
->count
);
1463 fprintf (dump_file
, "\n");
1464 fprintf (dump_file
, "SMS trip-count ");
1465 fprintf (dump_file
, "%"PRId64
,
1466 (int64_t) trip_count
);
1467 fprintf (dump_file
, "\n");
1468 fprintf (dump_file
, "SMS profile-sum-max ");
1469 fprintf (dump_file
, "%"PRId64
,
1470 (int64_t) profile_info
->sum_max
);
1471 fprintf (dump_file
, "\n");
1477 /* Make sure this is a doloop. */
1478 if ( !(count_reg
= doloop_register_get (head
, tail
)))
1481 fprintf (dump_file
, "SMS doloop_register_get failed\n");
1485 /* Don't handle BBs with calls or barriers
1486 or !single_set with the exception of instructions that include
1487 count_reg---these instructions are part of the control part
1488 that do-loop recognizes.
1489 ??? Should handle insns defining subregs. */
1490 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1496 || (NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1497 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
1498 && !reg_mentioned_p (count_reg
, insn
))
1499 || (INSN_P (insn
) && (set
= single_set (insn
))
1500 && GET_CODE (SET_DEST (set
)) == SUBREG
))
1504 if (insn
!= NEXT_INSN (tail
))
1509 fprintf (dump_file
, "SMS loop-with-call\n");
1510 else if (BARRIER_P (insn
))
1511 fprintf (dump_file
, "SMS loop-with-barrier\n");
1512 else if ((NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1513 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
1514 fprintf (dump_file
, "SMS loop-with-not-single-set\n");
1516 fprintf (dump_file
, "SMS loop with subreg in lhs\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;
1555 if (! (g
= g_arr
[loop
->num
]))
1560 rtx_insn
*insn
= BB_END (loop
->header
);
1562 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1563 dump_insn_location (insn
);
1564 fprintf (dump_file
, "\n");
1566 print_ddg (dump_file
, g
);
1569 get_ebb_head_tail (loop
->header
, loop
->header
, &head
, &tail
);
1571 latch_edge
= loop_latch_edge (loop
);
1572 gcc_assert (single_exit (loop
));
1573 if (single_exit (loop
)->count
)
1574 trip_count
= latch_edge
->count
/ single_exit (loop
)->count
;
1578 dump_insn_location (tail
);
1579 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1580 if (profile_info
&& flag_branch_probabilities
)
1582 fprintf (dump_file
, "SMS loop-count ");
1583 fprintf (dump_file
, "%"PRId64
,
1584 (int64_t) bb
->count
);
1585 fprintf (dump_file
, "\n");
1586 fprintf (dump_file
, "SMS profile-sum-max ");
1587 fprintf (dump_file
, "%"PRId64
,
1588 (int64_t) profile_info
->sum_max
);
1589 fprintf (dump_file
, "\n");
1591 fprintf (dump_file
, "SMS doloop\n");
1592 fprintf (dump_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1593 fprintf (dump_file
, "SMS num-loads %d\n", g
->num_loads
);
1594 fprintf (dump_file
, "SMS num-stores %d\n", g
->num_stores
);
1598 /* In case of th loop have doloop register it gets special
1601 if ((count_reg
= doloop_register_get (head
, tail
)))
1603 basic_block pre_header
;
1605 pre_header
= loop_preheader_edge (loop
)->src
;
1606 count_init
= const_iteration_count (count_reg
, pre_header
,
1609 gcc_assert (count_reg
);
1611 if (dump_file
&& count_init
)
1613 fprintf (dump_file
, "SMS const-doloop ");
1614 fprintf (dump_file
, "%"PRId64
,
1616 fprintf (dump_file
, "\n");
1619 node_order
= XNEWVEC (int, g
->num_nodes
);
1621 mii
= 1; /* Need to pass some estimate of mii. */
1622 rec_mii
= sms_order_nodes (g
, mii
, node_order
, &max_asap
);
1623 mii
= MAX (res_MII (g
), rec_mii
);
1624 maxii
= MAX (max_asap
, MAXII_FACTOR
* mii
);
1627 fprintf (dump_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1628 rec_mii
, mii
, maxii
);
1632 set_node_sched_params (g
);
1636 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
);
1640 /* Try to achieve optimized SC by normalizing the partial
1641 schedule (having the cycles start from cycle zero).
1642 The branch location must be placed in row ii-1 in the
1643 final scheduling. If failed, shift all instructions to
1644 position the branch in row ii-1. */
1645 opt_sc_p
= optimize_sc (ps
, g
);
1647 stage_count
= calculate_stage_count (ps
, 0);
1650 /* Bring the branch to cycle ii-1. */
1651 int amount
= (SCHED_TIME (g
->closing_branch
->cuid
)
1655 fprintf (dump_file
, "SMS schedule branch at cycle ii-1\n");
1657 stage_count
= calculate_stage_count (ps
, amount
);
1660 gcc_assert (stage_count
>= 1);
1663 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
1664 1 means that there is no interleaving between iterations thus
1665 we let the scheduling passes do the job in this case. */
1666 if (stage_count
< PARAM_VALUE (PARAM_SMS_MIN_SC
)
1667 || (count_init
&& (loop_count
<= stage_count
))
1668 || (flag_branch_probabilities
&& (trip_count
<= stage_count
)))
1672 fprintf (dump_file
, "SMS failed... \n");
1673 fprintf (dump_file
, "SMS sched-failed (stage-count=%d,"
1674 " loop-count=", stage_count
);
1675 fprintf (dump_file
, "%"PRId64
, loop_count
);
1676 fprintf (dump_file
, ", trip-count=");
1677 fprintf (dump_file
, "%"PRId64
, trip_count
);
1678 fprintf (dump_file
, ")\n");
1685 /* Rotate the partial schedule to have the branch in row ii-1. */
1686 int amount
= SCHED_TIME (g
->closing_branch
->cuid
) - (ps
->ii
- 1);
1688 reset_sched_times (ps
, amount
);
1689 rotate_partial_schedule (ps
, amount
);
1692 set_columns_for_ps (ps
);
1694 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1695 if (!schedule_reg_moves (ps
))
1698 free_partial_schedule (ps
);
1702 /* Moves that handle incoming values might have been added
1703 to a new first stage. Bump the stage count if so.
1705 ??? Perhaps we could consider rotating the schedule here
1707 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1709 reset_sched_times (ps
, 0);
1713 /* The stage count should now be correct without rotation. */
1714 gcc_checking_assert (stage_count
== calculate_stage_count (ps
, 0));
1715 PS_STAGE_COUNT (ps
) = stage_count
;
1721 dump_insn_location (tail
);
1722 fprintf (dump_file
, " SMS succeeded %d %d (with ii, sc)\n",
1723 ps
->ii
, stage_count
);
1724 print_partial_schedule (ps
, dump_file
);
1727 /* case the BCT count is not known , Do loop-versioning */
1728 if (count_reg
&& ! count_init
)
1730 rtx comp_rtx
= gen_rtx_GT (VOIDmode
, count_reg
,
1731 gen_int_mode (stage_count
,
1732 GET_MODE (count_reg
)));
1733 unsigned prob
= (PROB_SMS_ENOUGH_ITERATIONS
1734 * REG_BR_PROB_BASE
) / 100;
1736 loop_version (loop
, comp_rtx
, &condition_bb
,
1737 prob
, prob
, REG_BR_PROB_BASE
- prob
,
1741 /* Set new iteration count of loop kernel. */
1742 if (count_reg
&& count_init
)
1743 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
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
, count_init
);
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 limit on the number of cycles that resource conflicts can span. ??? Should
1854 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1855 set to 0 to save compile time. */
1856 #define DFA_HISTORY SMS_DFA_HISTORY
1858 /* A threshold for the number of repeated unsuccessful attempts to insert
1859 an empty row, before we flush the partial schedule and start over. */
1860 #define MAX_SPLIT_NUM 10
1861 /* Given the partial schedule PS, this function calculates and returns the
1862 cycles in which we can schedule the node with the given index I.
1863 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1864 noticed that there are several cases in which we fail to SMS the loop
1865 because the sched window of a node is empty due to tight data-deps. In
1866 such cases we want to unschedule some of the predecessors/successors
1867 until we get non-empty scheduling window. It returns -1 if the
1868 scheduling window is empty and zero otherwise. */
1871 get_sched_window (partial_schedule_ptr ps
, ddg_node_ptr u_node
,
1872 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
,
1875 int start
, step
, end
;
1876 int early_start
, late_start
;
1878 sbitmap psp
= sbitmap_alloc (ps
->g
->num_nodes
);
1879 sbitmap pss
= sbitmap_alloc (ps
->g
->num_nodes
);
1880 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1881 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1887 /* 1. compute sched window for u (start, end, step). */
1890 psp_not_empty
= bitmap_and (psp
, u_node_preds
, sched_nodes
);
1891 pss_not_empty
= bitmap_and (pss
, u_node_succs
, sched_nodes
);
1893 /* We first compute a forward range (start <= end), then decide whether
1895 early_start
= INT_MIN
;
1896 late_start
= INT_MAX
;
1904 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1906 fprintf (dump_file
, "\nAnalyzing dependencies for node %d (INSN %d)"
1907 "; ii = %d\n\n", u_node
->cuid
, INSN_UID (u_node
->insn
), ii
);
1908 fprintf (dump_file
, "%11s %11s %11s %11s %5s\n",
1909 "start", "early start", "late start", "end", "time");
1910 fprintf (dump_file
, "=========== =========== =========== ==========="
1913 /* Calculate early_start and limit end. Both bounds are inclusive. */
1915 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1917 int v
= e
->src
->cuid
;
1919 if (bitmap_bit_p (sched_nodes
, v
))
1921 int p_st
= SCHED_TIME (v
);
1922 int earliest
= p_st
+ e
->latency
- (e
->distance
* ii
);
1923 int latest
= (e
->data_type
== MEM_DEP
? p_st
+ ii
- 1 : INT_MAX
);
1927 fprintf (dump_file
, "%11s %11d %11s %11d %5d",
1928 "", earliest
, "", latest
, p_st
);
1929 print_ddg_edge (dump_file
, e
);
1930 fprintf (dump_file
, "\n");
1933 early_start
= MAX (early_start
, earliest
);
1934 end
= MIN (end
, latest
);
1936 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1941 /* Calculate late_start and limit start. Both bounds are inclusive. */
1943 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1945 int v
= e
->dest
->cuid
;
1947 if (bitmap_bit_p (sched_nodes
, v
))
1949 int s_st
= SCHED_TIME (v
);
1950 int earliest
= (e
->data_type
== MEM_DEP
? s_st
- ii
+ 1 : INT_MIN
);
1951 int latest
= s_st
- e
->latency
+ (e
->distance
* ii
);
1955 fprintf (dump_file
, "%11d %11s %11d %11s %5d",
1956 earliest
, "", latest
, "", s_st
);
1957 print_ddg_edge (dump_file
, e
);
1958 fprintf (dump_file
, "\n");
1961 start
= MAX (start
, earliest
);
1962 late_start
= MIN (late_start
, latest
);
1964 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1969 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1971 fprintf (dump_file
, "----------- ----------- ----------- -----------"
1973 fprintf (dump_file
, "%11d %11d %11d %11d %5s %s\n",
1974 start
, early_start
, late_start
, end
, "",
1975 "(max, max, min, min)");
1978 /* Get a target scheduling window no bigger than ii. */
1979 if (early_start
== INT_MIN
&& late_start
== INT_MAX
)
1980 early_start
= NODE_ASAP (u_node
);
1981 else if (early_start
== INT_MIN
)
1982 early_start
= late_start
- (ii
- 1);
1983 late_start
= MIN (late_start
, early_start
+ (ii
- 1));
1985 /* Apply memory dependence limits. */
1986 start
= MAX (start
, early_start
);
1987 end
= MIN (end
, late_start
);
1989 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1990 fprintf (dump_file
, "%11s %11d %11d %11s %5s final window\n",
1991 "", start
, end
, "", "");
1993 /* If there are at least as many successors as predecessors, schedule the
1994 node close to its successors. */
1995 if (pss_not_empty
&& count_succs
>= count_preds
)
2003 /* Now that we've finalized the window, make END an exclusive rather
2004 than an inclusive bound. */
2013 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
2016 fprintf (dump_file
, "\nEmpty window: start=%d, end=%d, step=%d\n",
2024 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
2025 node currently been scheduled. At the end of the calculation
2026 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
2027 U_NODE which are (1) already scheduled in the first/last row of
2028 U_NODE's scheduling window, (2) whose dependence inequality with U
2029 becomes an equality when U is scheduled in this same row, and (3)
2030 whose dependence latency is zero.
2032 The first and last rows are calculated using the following parameters:
2033 START/END rows - The cycles that begins/ends the traversal on the window;
2034 searching for an empty cycle to schedule U_NODE.
2035 STEP - The direction in which we traverse the window.
2036 II - The initiation interval. */
2039 calculate_must_precede_follow (ddg_node_ptr u_node
, int start
, int end
,
2040 int step
, int ii
, sbitmap sched_nodes
,
2041 sbitmap must_precede
, sbitmap must_follow
)
2044 int first_cycle_in_window
, last_cycle_in_window
;
2046 gcc_assert (must_precede
&& must_follow
);
2048 /* Consider the following scheduling window:
2049 {first_cycle_in_window, first_cycle_in_window+1, ...,
2050 last_cycle_in_window}. If step is 1 then the following will be
2051 the order we traverse the window: {start=first_cycle_in_window,
2052 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
2053 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
2054 end=first_cycle_in_window-1} if step is -1. */
2055 first_cycle_in_window
= (step
== 1) ? start
: end
- step
;
2056 last_cycle_in_window
= (step
== 1) ? end
- step
: start
;
2058 bitmap_clear (must_precede
);
2059 bitmap_clear (must_follow
);
2062 fprintf (dump_file
, "\nmust_precede: ");
2064 /* Instead of checking if:
2065 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
2066 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
2067 first_cycle_in_window)
2069 we use the fact that latency is non-negative:
2070 SCHED_TIME (e->src) - (e->distance * ii) <=
2071 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
2072 first_cycle_in_window
2074 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
2075 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2076 if (bitmap_bit_p (sched_nodes
, e
->src
->cuid
)
2077 && ((SCHED_TIME (e
->src
->cuid
) - (e
->distance
* ii
)) ==
2078 first_cycle_in_window
))
2081 fprintf (dump_file
, "%d ", e
->src
->cuid
);
2083 bitmap_set_bit (must_precede
, e
->src
->cuid
);
2087 fprintf (dump_file
, "\nmust_follow: ");
2089 /* Instead of checking if:
2090 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
2091 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
2092 last_cycle_in_window)
2094 we use the fact that latency is non-negative:
2095 SCHED_TIME (e->dest) + (e->distance * ii) >=
2096 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
2097 last_cycle_in_window
2099 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
2100 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2101 if (bitmap_bit_p (sched_nodes
, e
->dest
->cuid
)
2102 && ((SCHED_TIME (e
->dest
->cuid
) + (e
->distance
* ii
)) ==
2103 last_cycle_in_window
))
2106 fprintf (dump_file
, "%d ", e
->dest
->cuid
);
2108 bitmap_set_bit (must_follow
, e
->dest
->cuid
);
2112 fprintf (dump_file
, "\n");
2115 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
2116 parameters to decide if that's possible:
2117 PS - The partial schedule.
2118 U - The serial number of U_NODE.
2119 NUM_SPLITS - The number of row splits made so far.
2120 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
2121 the first row of the scheduling window)
2122 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
2123 last row of the scheduling window) */
2126 try_scheduling_node_in_cycle (partial_schedule_ptr ps
,
2127 int u
, int cycle
, sbitmap sched_nodes
,
2128 int *num_splits
, sbitmap must_precede
,
2129 sbitmap must_follow
)
2134 verify_partial_schedule (ps
, sched_nodes
);
2135 psi
= ps_add_node_check_conflicts (ps
, u
, cycle
, must_precede
, must_follow
);
2138 SCHED_TIME (u
) = cycle
;
2139 bitmap_set_bit (sched_nodes
, u
);
2143 fprintf (dump_file
, "Scheduled w/o split in %d\n", cycle
);
2150 /* This function implements the scheduling algorithm for SMS according to the
2152 static partial_schedule_ptr
2153 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
)
2156 int i
, c
, success
, num_splits
= 0;
2157 int flush_and_start_over
= true;
2158 int num_nodes
= g
->num_nodes
;
2159 int start
, end
, step
; /* Place together into one struct? */
2160 sbitmap sched_nodes
= sbitmap_alloc (num_nodes
);
2161 sbitmap must_precede
= sbitmap_alloc (num_nodes
);
2162 sbitmap must_follow
= sbitmap_alloc (num_nodes
);
2163 sbitmap tobe_scheduled
= sbitmap_alloc (num_nodes
);
2165 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
, DFA_HISTORY
);
2167 bitmap_ones (tobe_scheduled
);
2168 bitmap_clear (sched_nodes
);
2170 while (flush_and_start_over
&& (ii
< maxii
))
2174 fprintf (dump_file
, "Starting with ii=%d\n", ii
);
2175 flush_and_start_over
= false;
2176 bitmap_clear (sched_nodes
);
2178 for (i
= 0; i
< num_nodes
; i
++)
2180 int u
= nodes_order
[i
];
2181 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
2182 rtx insn
= u_node
->insn
;
2184 if (!NONDEBUG_INSN_P (insn
))
2186 bitmap_clear_bit (tobe_scheduled
, u
);
2190 if (bitmap_bit_p (sched_nodes
, u
))
2193 /* Try to get non-empty scheduling window. */
2195 if (get_sched_window (ps
, u_node
, sched_nodes
, ii
, &start
,
2199 fprintf (dump_file
, "\nTrying to schedule node %d "
2200 "INSN = %d in (%d .. %d) step %d\n", u
, (INSN_UID
2201 (g
->nodes
[u
].insn
)), start
, end
, step
);
2203 gcc_assert ((step
> 0 && start
< end
)
2204 || (step
< 0 && start
> end
));
2206 calculate_must_precede_follow (u_node
, start
, end
, step
, ii
,
2207 sched_nodes
, must_precede
,
2210 for (c
= start
; c
!= end
; c
+= step
)
2212 sbitmap tmp_precede
, tmp_follow
;
2214 set_must_precede_follow (&tmp_follow
, must_follow
,
2215 &tmp_precede
, must_precede
,
2216 c
, start
, end
, step
);
2218 try_scheduling_node_in_cycle (ps
, u
, c
,
2220 &num_splits
, tmp_precede
,
2226 verify_partial_schedule (ps
, sched_nodes
);
2235 if (num_splits
>= MAX_SPLIT_NUM
)
2238 flush_and_start_over
= true;
2239 verify_partial_schedule (ps
, sched_nodes
);
2240 reset_partial_schedule (ps
, ii
);
2241 verify_partial_schedule (ps
, sched_nodes
);
2246 /* The scheduling window is exclusive of 'end'
2247 whereas compute_split_window() expects an inclusive,
2250 split_row
= compute_split_row (sched_nodes
, start
, end
- 1,
2253 split_row
= compute_split_row (sched_nodes
, end
+ 1, start
,
2256 ps_insert_empty_row (ps
, split_row
, sched_nodes
);
2257 i
--; /* Go back and retry node i. */
2260 fprintf (dump_file
, "num_splits=%d\n", num_splits
);
2263 /* ??? If (success), check register pressure estimates. */
2264 } /* Continue with next node. */
2265 } /* While flush_and_start_over. */
2268 free_partial_schedule (ps
);
2272 gcc_assert (bitmap_equal_p (tobe_scheduled
, sched_nodes
));
2274 sbitmap_free (sched_nodes
);
2275 sbitmap_free (must_precede
);
2276 sbitmap_free (must_follow
);
2277 sbitmap_free (tobe_scheduled
);
2282 /* This function inserts a new empty row into PS at the position
2283 according to SPLITROW, keeping all already scheduled instructions
2284 intact and updating their SCHED_TIME and cycle accordingly. */
2286 ps_insert_empty_row (partial_schedule_ptr ps
, int split_row
,
2287 sbitmap sched_nodes
)
2289 ps_insn_ptr crr_insn
;
2290 ps_insn_ptr
*rows_new
;
2292 int new_ii
= ii
+ 1;
2294 int *rows_length_new
;
2296 verify_partial_schedule (ps
, sched_nodes
);
2298 /* We normalize sched_time and rotate ps to have only non-negative sched
2299 times, for simplicity of updating cycles after inserting new row. */
2300 split_row
-= ps
->min_cycle
;
2301 split_row
= SMODULO (split_row
, ii
);
2303 fprintf (dump_file
, "split_row=%d\n", split_row
);
2305 reset_sched_times (ps
, PS_MIN_CYCLE (ps
));
2306 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
2308 rows_new
= (ps_insn_ptr
*) xcalloc (new_ii
, sizeof (ps_insn_ptr
));
2309 rows_length_new
= (int *) xcalloc (new_ii
, sizeof (int));
2310 for (row
= 0; row
< split_row
; row
++)
2312 rows_new
[row
] = ps
->rows
[row
];
2313 rows_length_new
[row
] = ps
->rows_length
[row
];
2314 ps
->rows
[row
] = NULL
;
2315 for (crr_insn
= rows_new
[row
];
2316 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2318 int u
= crr_insn
->id
;
2319 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
);
2321 SCHED_TIME (u
) = new_time
;
2322 crr_insn
->cycle
= new_time
;
2323 SCHED_ROW (u
) = new_time
% new_ii
;
2324 SCHED_STAGE (u
) = new_time
/ new_ii
;
2329 rows_new
[split_row
] = NULL
;
2331 for (row
= split_row
; row
< ii
; row
++)
2333 rows_new
[row
+ 1] = ps
->rows
[row
];
2334 rows_length_new
[row
+ 1] = ps
->rows_length
[row
];
2335 ps
->rows
[row
] = NULL
;
2336 for (crr_insn
= rows_new
[row
+ 1];
2337 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2339 int u
= crr_insn
->id
;
2340 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
) + 1;
2342 SCHED_TIME (u
) = new_time
;
2343 crr_insn
->cycle
= new_time
;
2344 SCHED_ROW (u
) = new_time
% new_ii
;
2345 SCHED_STAGE (u
) = new_time
/ new_ii
;
2350 ps
->min_cycle
= ps
->min_cycle
+ ps
->min_cycle
/ ii
2351 + (SMODULO (ps
->min_cycle
, ii
) >= split_row
? 1 : 0);
2352 ps
->max_cycle
= ps
->max_cycle
+ ps
->max_cycle
/ ii
2353 + (SMODULO (ps
->max_cycle
, ii
) >= split_row
? 1 : 0);
2355 ps
->rows
= rows_new
;
2356 free (ps
->rows_length
);
2357 ps
->rows_length
= rows_length_new
;
2359 gcc_assert (ps
->min_cycle
>= 0);
2361 verify_partial_schedule (ps
, sched_nodes
);
2364 fprintf (dump_file
, "min_cycle=%d, max_cycle=%d\n", ps
->min_cycle
,
2368 /* Given U_NODE which is the node that failed to be scheduled; LOW and
2369 UP which are the boundaries of it's scheduling window; compute using
2370 SCHED_NODES and II a row in the partial schedule that can be split
2371 which will separate a critical predecessor from a critical successor
2372 thereby expanding the window, and return it. */
2374 compute_split_row (sbitmap sched_nodes
, int low
, int up
, int ii
,
2375 ddg_node_ptr u_node
)
2378 int lower
= INT_MIN
, upper
= INT_MAX
;
2383 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2385 int v
= e
->src
->cuid
;
2387 if (bitmap_bit_p (sched_nodes
, v
)
2388 && (low
== SCHED_TIME (v
) + e
->latency
- (e
->distance
* ii
)))
2389 if (SCHED_TIME (v
) > lower
)
2392 lower
= SCHED_TIME (v
);
2398 crit_cycle
= SCHED_TIME (crit_pred
) + 1;
2399 return SMODULO (crit_cycle
, ii
);
2402 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2404 int v
= e
->dest
->cuid
;
2406 if (bitmap_bit_p (sched_nodes
, v
)
2407 && (up
== SCHED_TIME (v
) - e
->latency
+ (e
->distance
* ii
)))
2408 if (SCHED_TIME (v
) < upper
)
2411 upper
= SCHED_TIME (v
);
2417 crit_cycle
= SCHED_TIME (crit_succ
);
2418 return SMODULO (crit_cycle
, ii
);
2422 fprintf (dump_file
, "Both crit_pred and crit_succ are NULL\n");
2424 return SMODULO ((low
+ up
+ 1) / 2, ii
);
2428 verify_partial_schedule (partial_schedule_ptr ps
, sbitmap sched_nodes
)
2431 ps_insn_ptr crr_insn
;
2433 for (row
= 0; row
< ps
->ii
; row
++)
2437 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2439 int u
= crr_insn
->id
;
2442 gcc_assert (bitmap_bit_p (sched_nodes
, u
));
2443 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2444 popcount (sched_nodes) == number of insns in ps. */
2445 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
2446 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
2449 gcc_assert (ps
->rows_length
[row
] == length
);
2454 /* This page implements the algorithm for ordering the nodes of a DDG
2455 for modulo scheduling, activated through the
2456 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2458 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2459 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
2460 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
2461 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2462 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
2463 #define DEPTH(x) (ASAP ((x)))
2465 typedef struct node_order_params
* nopa
;
2467 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
2468 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
2469 static nopa
calculate_order_params (ddg_ptr
, int, int *);
2470 static int find_max_asap (ddg_ptr
, sbitmap
);
2471 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
2472 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
2474 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
2476 struct node_order_params
2483 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2485 check_nodes_order (int *node_order
, int num_nodes
)
2488 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2493 fprintf (dump_file
, "SMS final nodes order: \n");
2495 for (i
= 0; i
< num_nodes
; i
++)
2497 int u
= node_order
[i
];
2500 fprintf (dump_file
, "%d ", u
);
2501 gcc_assert (u
< num_nodes
&& u
>= 0 && !bitmap_bit_p (tmp
, u
));
2503 bitmap_set_bit (tmp
, u
);
2507 fprintf (dump_file
, "\n");
2512 /* Order the nodes of G for scheduling and pass the result in
2513 NODE_ORDER. Also set aux.count of each node to ASAP.
2514 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2516 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
, int *pmax_asap
)
2520 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
2522 nopa nops
= calculate_order_params (g
, mii
, pmax_asap
);
2525 print_sccs (dump_file
, sccs
, g
);
2527 order_nodes_of_sccs (sccs
, node_order
);
2529 if (sccs
->num_sccs
> 0)
2530 /* First SCC has the largest recurrence_length. */
2531 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
2533 /* Save ASAP before destroying node_order_params. */
2534 for (i
= 0; i
< g
->num_nodes
; i
++)
2536 ddg_node_ptr v
= &g
->nodes
[i
];
2537 v
->aux
.count
= ASAP (v
);
2541 free_ddg_all_sccs (sccs
);
2542 check_nodes_order (node_order
, g
->num_nodes
);
2548 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
2551 ddg_ptr g
= all_sccs
->ddg
;
2552 int num_nodes
= g
->num_nodes
;
2553 sbitmap prev_sccs
= sbitmap_alloc (num_nodes
);
2554 sbitmap on_path
= sbitmap_alloc (num_nodes
);
2555 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2556 sbitmap ones
= sbitmap_alloc (num_nodes
);
2558 bitmap_clear (prev_sccs
);
2561 /* Perform the node ordering starting from the SCC with the highest recMII.
2562 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2563 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
2565 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
2567 /* Add nodes on paths from previous SCCs to the current SCC. */
2568 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
2569 bitmap_ior (tmp
, scc
->nodes
, on_path
);
2571 /* Add nodes on paths from the current SCC to previous SCCs. */
2572 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
2573 bitmap_ior (tmp
, tmp
, on_path
);
2575 /* Remove nodes of previous SCCs from current extended SCC. */
2576 bitmap_and_compl (tmp
, tmp
, prev_sccs
);
2578 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2579 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2582 /* Handle the remaining nodes that do not belong to any scc. Each call
2583 to order_nodes_in_scc handles a single connected component. */
2584 while (pos
< g
->num_nodes
)
2586 bitmap_and_compl (tmp
, ones
, prev_sccs
);
2587 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2589 sbitmap_free (prev_sccs
);
2590 sbitmap_free (on_path
);
2592 sbitmap_free (ones
);
2595 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2596 static struct node_order_params
*
2597 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
, int *pmax_asap
)
2601 int num_nodes
= g
->num_nodes
;
2603 /* Allocate a place to hold ordering params for each node in the DDG. */
2604 nopa node_order_params_arr
;
2606 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2607 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
2608 sizeof (struct node_order_params
));
2610 /* Set the aux pointer of each node to point to its order_params structure. */
2611 for (u
= 0; u
< num_nodes
; u
++)
2612 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
2614 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2615 calculate ASAP, ALAP, mobility, distance, and height for each node
2616 in the dependence (direct acyclic) graph. */
2618 /* We assume that the nodes in the array are in topological order. */
2621 for (u
= 0; u
< num_nodes
; u
++)
2623 ddg_node_ptr u_node
= &g
->nodes
[u
];
2626 for (e
= u_node
->in
; e
; e
= e
->next_in
)
2627 if (e
->distance
== 0)
2628 ASAP (u_node
) = MAX (ASAP (u_node
),
2629 ASAP (e
->src
) + e
->latency
);
2630 max_asap
= MAX (max_asap
, ASAP (u_node
));
2633 for (u
= num_nodes
- 1; u
> -1; u
--)
2635 ddg_node_ptr u_node
= &g
->nodes
[u
];
2637 ALAP (u_node
) = max_asap
;
2638 HEIGHT (u_node
) = 0;
2639 for (e
= u_node
->out
; e
; e
= e
->next_out
)
2640 if (e
->distance
== 0)
2642 ALAP (u_node
) = MIN (ALAP (u_node
),
2643 ALAP (e
->dest
) - e
->latency
);
2644 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
2645 HEIGHT (e
->dest
) + e
->latency
);
2650 fprintf (dump_file
, "\nOrder params\n");
2651 for (u
= 0; u
< num_nodes
; u
++)
2653 ddg_node_ptr u_node
= &g
->nodes
[u
];
2655 fprintf (dump_file
, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u
,
2656 ASAP (u_node
), ALAP (u_node
), HEIGHT (u_node
));
2660 *pmax_asap
= max_asap
;
2661 return node_order_params_arr
;
2665 find_max_asap (ddg_ptr g
, sbitmap nodes
)
2670 sbitmap_iterator sbi
;
2672 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2674 ddg_node_ptr u_node
= &g
->nodes
[u
];
2676 if (max_asap
< ASAP (u_node
))
2678 max_asap
= ASAP (u_node
);
2686 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
2690 int min_mob
= INT_MAX
;
2692 sbitmap_iterator sbi
;
2694 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2696 ddg_node_ptr u_node
= &g
->nodes
[u
];
2698 if (max_hv
< HEIGHT (u_node
))
2700 max_hv
= HEIGHT (u_node
);
2701 min_mob
= MOB (u_node
);
2704 else if ((max_hv
== HEIGHT (u_node
))
2705 && (min_mob
> MOB (u_node
)))
2707 min_mob
= MOB (u_node
);
2715 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
2719 int min_mob
= INT_MAX
;
2721 sbitmap_iterator sbi
;
2723 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2725 ddg_node_ptr u_node
= &g
->nodes
[u
];
2727 if (max_dv
< DEPTH (u_node
))
2729 max_dv
= DEPTH (u_node
);
2730 min_mob
= MOB (u_node
);
2733 else if ((max_dv
== DEPTH (u_node
))
2734 && (min_mob
> MOB (u_node
)))
2736 min_mob
= MOB (u_node
);
2743 /* Places the nodes of SCC into the NODE_ORDER array starting
2744 at position POS, according to the SMS ordering algorithm.
2745 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2746 the NODE_ORDER array, starting from position zero. */
2748 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
2749 int * node_order
, int pos
)
2751 enum sms_direction dir
;
2752 int num_nodes
= g
->num_nodes
;
2753 sbitmap workset
= sbitmap_alloc (num_nodes
);
2754 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2755 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
2756 sbitmap predecessors
= sbitmap_alloc (num_nodes
);
2757 sbitmap successors
= sbitmap_alloc (num_nodes
);
2759 bitmap_clear (predecessors
);
2760 find_predecessors (predecessors
, g
, nodes_ordered
);
2762 bitmap_clear (successors
);
2763 find_successors (successors
, g
, nodes_ordered
);
2766 if (bitmap_and (tmp
, predecessors
, scc
))
2768 bitmap_copy (workset
, tmp
);
2771 else if (bitmap_and (tmp
, successors
, scc
))
2773 bitmap_copy (workset
, tmp
);
2780 bitmap_clear (workset
);
2781 if ((u
= find_max_asap (g
, scc
)) >= 0)
2782 bitmap_set_bit (workset
, u
);
2786 bitmap_clear (zero_bitmap
);
2787 while (!bitmap_equal_p (workset
, zero_bitmap
))
2790 ddg_node_ptr v_node
;
2791 sbitmap v_node_preds
;
2792 sbitmap v_node_succs
;
2796 while (!bitmap_equal_p (workset
, zero_bitmap
))
2798 v
= find_max_hv_min_mob (g
, workset
);
2799 v_node
= &g
->nodes
[v
];
2800 node_order
[pos
++] = v
;
2801 v_node_succs
= NODE_SUCCESSORS (v_node
);
2802 bitmap_and (tmp
, v_node_succs
, scc
);
2804 /* Don't consider the already ordered successors again. */
2805 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2806 bitmap_ior (workset
, workset
, tmp
);
2807 bitmap_clear_bit (workset
, v
);
2808 bitmap_set_bit (nodes_ordered
, v
);
2811 bitmap_clear (predecessors
);
2812 find_predecessors (predecessors
, g
, nodes_ordered
);
2813 bitmap_and (workset
, predecessors
, scc
);
2817 while (!bitmap_equal_p (workset
, zero_bitmap
))
2819 v
= find_max_dv_min_mob (g
, workset
);
2820 v_node
= &g
->nodes
[v
];
2821 node_order
[pos
++] = v
;
2822 v_node_preds
= NODE_PREDECESSORS (v_node
);
2823 bitmap_and (tmp
, v_node_preds
, scc
);
2825 /* Don't consider the already ordered predecessors again. */
2826 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2827 bitmap_ior (workset
, workset
, tmp
);
2828 bitmap_clear_bit (workset
, v
);
2829 bitmap_set_bit (nodes_ordered
, v
);
2832 bitmap_clear (successors
);
2833 find_successors (successors
, g
, nodes_ordered
);
2834 bitmap_and (workset
, successors
, scc
);
2838 sbitmap_free (workset
);
2839 sbitmap_free (zero_bitmap
);
2840 sbitmap_free (predecessors
);
2841 sbitmap_free (successors
);
2846 /* This page contains functions for manipulating partial-schedules during
2847 modulo scheduling. */
2849 /* Create a partial schedule and allocate a memory to hold II rows. */
2851 static partial_schedule_ptr
2852 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2854 partial_schedule_ptr ps
= XNEW (struct partial_schedule
);
2855 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2856 ps
->rows_length
= (int *) xcalloc (ii
, sizeof (int));
2857 ps
->reg_moves
.create (0);
2859 ps
->history
= history
;
2860 ps
->min_cycle
= INT_MAX
;
2861 ps
->max_cycle
= INT_MIN
;
2867 /* Free the PS_INSNs in rows array of the given partial schedule.
2868 ??? Consider caching the PS_INSN's. */
2870 free_ps_insns (partial_schedule_ptr ps
)
2874 for (i
= 0; i
< ps
->ii
; i
++)
2878 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2881 ps
->rows
[i
] = ps_insn
;
2887 /* Free all the memory allocated to the partial schedule. */
2890 free_partial_schedule (partial_schedule_ptr ps
)
2892 ps_reg_move_info
*move
;
2898 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
2899 sbitmap_free (move
->uses
);
2900 ps
->reg_moves
.release ();
2904 free (ps
->rows_length
);
2908 /* Clear the rows array with its PS_INSNs, and create a new one with
2912 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2917 if (new_ii
== ps
->ii
)
2919 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2920 * sizeof (ps_insn_ptr
));
2921 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2922 ps
->rows_length
= (int *) xrealloc (ps
->rows_length
, new_ii
* sizeof (int));
2923 memset (ps
->rows_length
, 0, new_ii
* sizeof (int));
2925 ps
->min_cycle
= INT_MAX
;
2926 ps
->max_cycle
= INT_MIN
;
2929 /* Prints the partial schedule as an ii rows array, for each rows
2930 print the ids of the insns in it. */
2932 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2936 for (i
= 0; i
< ps
->ii
; i
++)
2938 ps_insn_ptr ps_i
= ps
->rows
[i
];
2940 fprintf (dump
, "\n[ROW %d ]: ", i
);
2943 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_i
->id
);
2946 fprintf (dump
, "%d (branch), ", INSN_UID (insn
));
2948 fprintf (dump
, "%d, ", INSN_UID (insn
));
2950 ps_i
= ps_i
->next_in_row
;
2955 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2957 create_ps_insn (int id
, int cycle
)
2959 ps_insn_ptr ps_i
= XNEW (struct ps_insn
);
2962 ps_i
->next_in_row
= NULL
;
2963 ps_i
->prev_in_row
= NULL
;
2964 ps_i
->cycle
= cycle
;
2970 /* Removes the given PS_INSN from the partial schedule. */
2972 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2976 gcc_assert (ps
&& ps_i
);
2978 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2979 if (! ps_i
->prev_in_row
)
2981 gcc_assert (ps_i
== ps
->rows
[row
]);
2982 ps
->rows
[row
] = ps_i
->next_in_row
;
2984 ps
->rows
[row
]->prev_in_row
= NULL
;
2988 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
2989 if (ps_i
->next_in_row
)
2990 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
2993 ps
->rows_length
[row
] -= 1;
2998 /* Unlike what literature describes for modulo scheduling (which focuses
2999 on VLIW machines) the order of the instructions inside a cycle is
3000 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
3001 where the current instruction should go relative to the already
3002 scheduled instructions in the given cycle. Go over these
3003 instructions and find the first possible column to put it in. */
3005 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
3006 sbitmap must_precede
, sbitmap must_follow
)
3008 ps_insn_ptr next_ps_i
;
3009 ps_insn_ptr first_must_follow
= NULL
;
3010 ps_insn_ptr last_must_precede
= NULL
;
3011 ps_insn_ptr last_in_row
= NULL
;
3017 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3019 /* Find the first must follow and the last must precede
3020 and insert the node immediately after the must precede
3021 but make sure that it there is no must follow after it. */
3022 for (next_ps_i
= ps
->rows
[row
];
3024 next_ps_i
= next_ps_i
->next_in_row
)
3027 && bitmap_bit_p (must_follow
, next_ps_i
->id
)
3028 && ! first_must_follow
)
3029 first_must_follow
= next_ps_i
;
3030 if (must_precede
&& bitmap_bit_p (must_precede
, next_ps_i
->id
))
3032 /* If we have already met a node that must follow, then
3033 there is no possible column. */
3034 if (first_must_follow
)
3037 last_must_precede
= next_ps_i
;
3039 /* The closing branch must be the last in the row. */
3041 && bitmap_bit_p (must_precede
, next_ps_i
->id
)
3042 && JUMP_P (ps_rtl_insn (ps
, next_ps_i
->id
)))
3045 last_in_row
= next_ps_i
;
3048 /* The closing branch is scheduled as well. Make sure there is no
3049 dependent instruction after it as the branch should be the last
3050 instruction in the row. */
3051 if (JUMP_P (ps_rtl_insn (ps
, ps_i
->id
)))
3053 if (first_must_follow
)
3057 /* Make the branch the last in the row. New instructions
3058 will be inserted at the beginning of the row or after the
3059 last must_precede instruction thus the branch is guaranteed
3060 to remain the last instruction in the row. */
3061 last_in_row
->next_in_row
= ps_i
;
3062 ps_i
->prev_in_row
= last_in_row
;
3063 ps_i
->next_in_row
= NULL
;
3066 ps
->rows
[row
] = ps_i
;
3070 /* Now insert the node after INSERT_AFTER_PSI. */
3072 if (! last_must_precede
)
3074 ps_i
->next_in_row
= ps
->rows
[row
];
3075 ps_i
->prev_in_row
= NULL
;
3076 if (ps_i
->next_in_row
)
3077 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3078 ps
->rows
[row
] = ps_i
;
3082 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
3083 last_must_precede
->next_in_row
= ps_i
;
3084 ps_i
->prev_in_row
= last_must_precede
;
3085 if (ps_i
->next_in_row
)
3086 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3092 /* Advances the PS_INSN one column in its current row; returns false
3093 in failure and true in success. Bit N is set in MUST_FOLLOW if
3094 the node with cuid N must be come after the node pointed to by
3095 PS_I when scheduled in the same cycle. */
3097 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
3098 sbitmap must_follow
)
3100 ps_insn_ptr prev
, next
;
3106 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3108 if (! ps_i
->next_in_row
)
3111 /* Check if next_in_row is dependent on ps_i, both having same sched
3112 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
3113 if (must_follow
&& bitmap_bit_p (must_follow
, ps_i
->next_in_row
->id
))
3116 /* Advance PS_I over its next_in_row in the doubly linked list. */
3117 prev
= ps_i
->prev_in_row
;
3118 next
= ps_i
->next_in_row
;
3120 if (ps_i
== ps
->rows
[row
])
3121 ps
->rows
[row
] = next
;
3123 ps_i
->next_in_row
= next
->next_in_row
;
3125 if (next
->next_in_row
)
3126 next
->next_in_row
->prev_in_row
= ps_i
;
3128 next
->next_in_row
= ps_i
;
3129 ps_i
->prev_in_row
= next
;
3131 next
->prev_in_row
= prev
;
3133 prev
->next_in_row
= next
;
3138 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
3139 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
3140 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
3141 before/after (respectively) the node pointed to by PS_I when scheduled
3142 in the same cycle. */
3144 add_node_to_ps (partial_schedule_ptr ps
, int id
, int cycle
,
3145 sbitmap must_precede
, sbitmap must_follow
)
3148 int row
= SMODULO (cycle
, ps
->ii
);
3150 if (ps
->rows_length
[row
] >= issue_rate
)
3153 ps_i
= create_ps_insn (id
, cycle
);
3155 /* Finds and inserts PS_I according to MUST_FOLLOW and
3157 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
3163 ps
->rows_length
[row
] += 1;
3167 /* Advance time one cycle. Assumes DFA is being used. */
3169 advance_one_cycle (void)
3171 if (targetm
.sched
.dfa_pre_cycle_insn
)
3172 state_transition (curr_state
,
3173 targetm
.sched
.dfa_pre_cycle_insn ());
3175 state_transition (curr_state
, NULL
);
3177 if (targetm
.sched
.dfa_post_cycle_insn
)
3178 state_transition (curr_state
,
3179 targetm
.sched
.dfa_post_cycle_insn ());
3184 /* Checks if PS has resource conflicts according to DFA, starting from
3185 FROM cycle to TO cycle; returns true if there are conflicts and false
3186 if there are no conflicts. Assumes DFA is being used. */
3188 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
3192 state_reset (curr_state
);
3194 for (cycle
= from
; cycle
<= to
; cycle
++)
3196 ps_insn_ptr crr_insn
;
3197 /* Holds the remaining issue slots in the current row. */
3198 int can_issue_more
= issue_rate
;
3200 /* Walk through the DFA for the current row. */
3201 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
3203 crr_insn
= crr_insn
->next_in_row
)
3205 rtx_insn
*insn
= ps_rtl_insn (ps
, crr_insn
->id
);
3207 if (!NONDEBUG_INSN_P (insn
))
3210 /* Check if there is room for the current insn. */
3211 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
3214 /* Update the DFA state and return with failure if the DFA found
3215 resource conflicts. */
3216 if (state_transition (curr_state
, insn
) >= 0)
3219 if (targetm
.sched
.variable_issue
)
3221 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
3222 insn
, can_issue_more
);
3223 /* A naked CLOBBER or USE generates no instruction, so don't
3224 let them consume issue slots. */
3225 else if (GET_CODE (PATTERN (insn
)) != USE
3226 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3230 /* Advance the DFA to the next cycle. */
3231 advance_one_cycle ();
3236 /* Checks if the given node causes resource conflicts when added to PS at
3237 cycle C. If not the node is added to PS and returned; otherwise zero
3238 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
3239 cuid N must be come before/after (respectively) the node pointed to by
3240 PS_I when scheduled in the same cycle. */
3242 ps_add_node_check_conflicts (partial_schedule_ptr ps
, int n
,
3243 int c
, sbitmap must_precede
,
3244 sbitmap must_follow
)
3246 int has_conflicts
= 0;
3249 /* First add the node to the PS, if this succeeds check for
3250 conflicts, trying different issue slots in the same row. */
3251 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
3252 return NULL
; /* Failed to insert the node at the given cycle. */
3254 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3256 && ps_has_conflicts (ps
,
3260 /* Try different issue slots to find one that the given node can be
3261 scheduled in without conflicts. */
3262 while (has_conflicts
)
3264 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
3266 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3268 && ps_has_conflicts (ps
,
3275 remove_node_from_ps (ps
, ps_i
);
3279 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
3280 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
3284 /* Calculate the stage count of the partial schedule PS. The calculation
3285 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3287 calculate_stage_count (partial_schedule_ptr ps
, int rotation_amount
)
3289 int new_min_cycle
= PS_MIN_CYCLE (ps
) - rotation_amount
;
3290 int new_max_cycle
= PS_MAX_CYCLE (ps
) - rotation_amount
;
3291 int stage_count
= CALC_STAGE_COUNT (-1, new_min_cycle
, ps
->ii
);
3293 /* The calculation of stage count is done adding the number of stages
3294 before cycle zero and after cycle zero. */
3295 stage_count
+= CALC_STAGE_COUNT (new_max_cycle
, 0, ps
->ii
);
3300 /* Rotate the rows of PS such that insns scheduled at time
3301 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3303 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
3305 int i
, row
, backward_rotates
;
3306 int last_row
= ps
->ii
- 1;
3308 if (start_cycle
== 0)
3311 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
3313 /* Revisit later and optimize this into a single loop. */
3314 for (i
= 0; i
< backward_rotates
; i
++)
3316 ps_insn_ptr first_row
= ps
->rows
[0];
3317 int first_row_length
= ps
->rows_length
[0];
3319 for (row
= 0; row
< last_row
; row
++)
3321 ps
->rows
[row
] = ps
->rows
[row
+ 1];
3322 ps
->rows_length
[row
] = ps
->rows_length
[row
+ 1];
3325 ps
->rows
[last_row
] = first_row
;
3326 ps
->rows_length
[last_row
] = first_row_length
;
3329 ps
->max_cycle
-= start_cycle
;
3330 ps
->min_cycle
-= start_cycle
;
3333 #endif /* INSN_SCHEDULING */
3335 /* Run instruction scheduler. */
3336 /* Perform SMS module scheduling. */
3340 const pass_data pass_data_sms
=
3342 RTL_PASS
, /* type */
3344 OPTGROUP_NONE
, /* optinfo_flags */
3346 0, /* properties_required */
3347 0, /* properties_provided */
3348 0, /* properties_destroyed */
3349 0, /* todo_flags_start */
3350 TODO_df_finish
, /* todo_flags_finish */
3353 class pass_sms
: public rtl_opt_pass
3356 pass_sms (gcc::context
*ctxt
)
3357 : rtl_opt_pass (pass_data_sms
, ctxt
)
3360 /* opt_pass methods: */
3361 virtual bool gate (function
*)
3363 return (optimize
> 0 && flag_modulo_sched
);
3366 virtual unsigned int execute (function
*);
3368 }; // class pass_sms
3371 pass_sms::execute (function
*fun ATTRIBUTE_UNUSED
)
3373 #ifdef INSN_SCHEDULING
3376 /* Collect loop information to be used in SMS. */
3377 cfg_layout_initialize (0);
3380 /* Update the life information, because we add pseudos. */
3381 max_regno
= max_reg_num ();
3383 /* Finalize layout changes. */
3384 FOR_EACH_BB_FN (bb
, fun
)
3385 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3386 bb
->aux
= bb
->next_bb
;
3387 free_dominance_info (CDI_DOMINATORS
);
3388 cfg_layout_finalize ();
3389 #endif /* INSN_SCHEDULING */
3396 make_pass_sms (gcc::context
*ctxt
)
3398 return new pass_sms (ctxt
);