1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004-2013 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"
33 #include "insn-config.h"
34 #include "insn-attr.h"
37 #include "sched-int.h"
44 #include "tree-pass.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 typedef struct ps_reg_move_info ps_reg_move_info
;
163 /* Holds the partial schedule as an array of II rows. Each entry of the
164 array points to a linked list of PS_INSNs, which represents the
165 instructions that are scheduled for that row. */
166 struct partial_schedule
168 int ii
; /* Number of rows in the partial schedule. */
169 int history
; /* Threshold for conflict checking using DFA. */
171 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
174 /* All the moves added for this partial schedule. Index X has
175 a ps_insn id of X + g->num_nodes. */
176 vec
<ps_reg_move_info
> reg_moves
;
178 /* rows_length[i] holds the number of instructions in the row.
179 It is used only (as an optimization) to back off quickly from
180 trying to schedule a node in a full row; that is, to avoid running
181 through futile DFA state transitions. */
184 /* The earliest absolute cycle of an insn in the partial schedule. */
187 /* The latest absolute cycle of an insn in the partial schedule. */
190 ddg_ptr g
; /* The DDG of the insns in the partial schedule. */
192 int stage_count
; /* The stage count of the partial schedule. */
196 static partial_schedule_ptr
create_partial_schedule (int ii
, ddg_ptr
, int history
);
197 static void free_partial_schedule (partial_schedule_ptr
);
198 static void reset_partial_schedule (partial_schedule_ptr
, int new_ii
);
199 void print_partial_schedule (partial_schedule_ptr
, FILE *);
200 static void verify_partial_schedule (partial_schedule_ptr
, sbitmap
);
201 static ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr
,
202 int, int, sbitmap
, sbitmap
);
203 static void rotate_partial_schedule (partial_schedule_ptr
, int);
204 void set_row_column_for_ps (partial_schedule_ptr
);
205 static void ps_insert_empty_row (partial_schedule_ptr
, int, sbitmap
);
206 static int compute_split_row (sbitmap
, int, int, int, ddg_node_ptr
);
209 /* This page defines constants and structures for the modulo scheduling
212 static int sms_order_nodes (ddg_ptr
, int, int *, int *);
213 static void set_node_sched_params (ddg_ptr
);
214 static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr
, int, int, int *);
215 static void permute_partial_schedule (partial_schedule_ptr
, rtx
);
216 static void generate_prolog_epilog (partial_schedule_ptr
, struct loop
*,
218 static int calculate_stage_count (partial_schedule_ptr
, int);
219 static void calculate_must_precede_follow (ddg_node_ptr
, int, int,
220 int, int, sbitmap
, sbitmap
, sbitmap
);
221 static int get_sched_window (partial_schedule_ptr
, ddg_node_ptr
,
222 sbitmap
, int, int *, int *, int *);
223 static bool try_scheduling_node_in_cycle (partial_schedule_ptr
, int, int,
224 sbitmap
, int *, sbitmap
, sbitmap
);
225 static void remove_node_from_ps (partial_schedule_ptr
, ps_insn_ptr
);
227 #define NODE_ASAP(node) ((node)->aux.count)
229 #define SCHED_PARAMS(x) (&node_sched_param_vec[x])
230 #define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
231 #define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
232 #define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
233 #define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
235 /* The scheduling parameters held for each node. */
236 typedef struct node_sched_params
238 int time
; /* The absolute scheduling cycle. */
240 int row
; /* Holds time % ii. */
241 int stage
; /* Holds time / ii. */
243 /* The column of a node inside the ps. If nodes u, v are on the same row,
244 u will precede v if column (u) < column (v). */
246 } *node_sched_params_ptr
;
248 typedef struct node_sched_params node_sched_params
;
250 /* The following three functions are copied from the current scheduler
251 code in order to use sched_analyze() for computing the dependencies.
252 They are used when initializing the sched_info structure. */
254 sms_print_insn (const_rtx insn
, int aligned ATTRIBUTE_UNUSED
)
258 sprintf (tmp
, "i%4d", INSN_UID (insn
));
263 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
264 regset used ATTRIBUTE_UNUSED
)
268 static struct common_sched_info_def sms_common_sched_info
;
270 static struct sched_deps_info_def sms_sched_deps_info
=
272 compute_jump_reg_dependencies
,
273 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
278 static struct haifa_sched_info sms_sched_info
=
287 NULL
, /* insn_finishes_block_p */
292 NULL
, NULL
, NULL
, NULL
,
297 /* Partial schedule instruction ID in PS is a register move. Return
298 information about it. */
299 static struct ps_reg_move_info
*
300 ps_reg_move (partial_schedule_ptr ps
, int id
)
302 gcc_checking_assert (id
>= ps
->g
->num_nodes
);
303 return &ps
->reg_moves
[id
- ps
->g
->num_nodes
];
306 /* Return the rtl instruction that is being scheduled by partial schedule
307 instruction ID, which belongs to schedule PS. */
309 ps_rtl_insn (partial_schedule_ptr ps
, int id
)
311 if (id
< ps
->g
->num_nodes
)
312 return ps
->g
->nodes
[id
].insn
;
314 return ps_reg_move (ps
, id
)->insn
;
317 /* Partial schedule instruction ID, which belongs to PS, occurred in
318 the original (unscheduled) loop. Return the first instruction
319 in the loop that was associated with ps_rtl_insn (PS, ID).
320 If the instruction had some notes before it, this is the first
323 ps_first_note (partial_schedule_ptr ps
, int id
)
325 gcc_assert (id
< ps
->g
->num_nodes
);
326 return ps
->g
->nodes
[id
].first_note
;
329 /* Return the number of consecutive stages that are occupied by
330 partial schedule instruction ID in PS. */
332 ps_num_consecutive_stages (partial_schedule_ptr ps
, int id
)
334 if (id
< ps
->g
->num_nodes
)
337 return ps_reg_move (ps
, id
)->num_consecutive_stages
;
340 /* Given HEAD and TAIL which are the first and last insns in a loop;
341 return the register which controls the loop. Return zero if it has
342 more than one occurrence in the loop besides the control part or the
343 do-loop pattern is not of the form we expect. */
345 doloop_register_get (rtx head ATTRIBUTE_UNUSED
, rtx tail ATTRIBUTE_UNUSED
)
347 #ifdef HAVE_doloop_end
348 rtx reg
, condition
, insn
, first_insn_not_to_check
;
353 /* TODO: Free SMS's dependence on doloop_condition_get. */
354 condition
= doloop_condition_get (tail
);
358 if (REG_P (XEXP (condition
, 0)))
359 reg
= XEXP (condition
, 0);
360 else if (GET_CODE (XEXP (condition
, 0)) == PLUS
361 && REG_P (XEXP (XEXP (condition
, 0), 0)))
362 reg
= XEXP (XEXP (condition
, 0), 0);
366 /* Check that the COUNT_REG has no other occurrences in the loop
367 until the decrement. We assume the control part consists of
368 either a single (parallel) branch-on-count or a (non-parallel)
369 branch immediately preceded by a single (decrement) insn. */
370 first_insn_not_to_check
= (GET_CODE (PATTERN (tail
)) == PARALLEL
? tail
371 : prev_nondebug_insn (tail
));
373 for (insn
= head
; insn
!= first_insn_not_to_check
; insn
= NEXT_INSN (insn
))
374 if (!DEBUG_INSN_P (insn
) && reg_mentioned_p (reg
, insn
))
378 fprintf (dump_file
, "SMS count_reg found ");
379 print_rtl_single (dump_file
, reg
);
380 fprintf (dump_file
, " outside control in insn:\n");
381 print_rtl_single (dump_file
, insn
);
393 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
394 that the number of iterations is a compile-time constant. If so,
395 return the rtx that sets COUNT_REG to a constant, and set COUNT to
396 this constant. Otherwise return 0. */
398 const_iteration_count (rtx count_reg
, basic_block pre_header
,
399 HOST_WIDEST_INT
* count
)
407 get_ebb_head_tail (pre_header
, pre_header
, &head
, &tail
);
409 for (insn
= tail
; insn
!= PREV_INSN (head
); insn
= PREV_INSN (insn
))
410 if (NONDEBUG_INSN_P (insn
) && single_set (insn
) &&
411 rtx_equal_p (count_reg
, SET_DEST (single_set (insn
))))
413 rtx pat
= single_set (insn
);
415 if (CONST_INT_P (SET_SRC (pat
)))
417 *count
= INTVAL (SET_SRC (pat
));
427 /* A very simple resource-based lower bound on the initiation interval.
428 ??? Improve the accuracy of this bound by considering the
429 utilization of various units. */
433 if (targetm
.sched
.sms_res_mii
)
434 return targetm
.sched
.sms_res_mii (g
);
436 return ((g
->num_nodes
- g
->num_debug
) / issue_rate
);
440 /* A vector that contains the sched data for each ps_insn. */
441 static vec
<node_sched_params
> node_sched_param_vec
;
443 /* Allocate sched_params for each node and initialize it. */
445 set_node_sched_params (ddg_ptr g
)
447 node_sched_param_vec
.truncate (0);
448 node_sched_param_vec
.safe_grow_cleared (g
->num_nodes
);
451 /* Make sure that node_sched_param_vec has an entry for every move in PS. */
453 extend_node_sched_params (partial_schedule_ptr ps
)
455 node_sched_param_vec
.safe_grow_cleared (ps
->g
->num_nodes
456 + ps
->reg_moves
.length ());
459 /* Update the sched_params (time, row and stage) for node U using the II,
460 the CYCLE of U and MIN_CYCLE.
461 We're not simply taking the following
462 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
463 because the stages may not be aligned on cycle 0. */
465 update_node_sched_params (int u
, int ii
, int cycle
, int min_cycle
)
467 int sc_until_cycle_zero
;
470 SCHED_TIME (u
) = cycle
;
471 SCHED_ROW (u
) = SMODULO (cycle
, ii
);
473 /* The calculation of stage count is done adding the number
474 of stages before cycle zero and after cycle zero. */
475 sc_until_cycle_zero
= CALC_STAGE_COUNT (-1, min_cycle
, ii
);
477 if (SCHED_TIME (u
) < 0)
479 stage
= CALC_STAGE_COUNT (-1, SCHED_TIME (u
), ii
);
480 SCHED_STAGE (u
) = sc_until_cycle_zero
- stage
;
484 stage
= CALC_STAGE_COUNT (SCHED_TIME (u
), 0, ii
);
485 SCHED_STAGE (u
) = sc_until_cycle_zero
+ stage
- 1;
490 print_node_sched_params (FILE *file
, int num_nodes
, partial_schedule_ptr ps
)
496 for (i
= 0; i
< num_nodes
; i
++)
498 node_sched_params_ptr nsp
= SCHED_PARAMS (i
);
500 fprintf (file
, "Node = %d; INSN = %d\n", i
,
501 INSN_UID (ps_rtl_insn (ps
, i
)));
502 fprintf (file
, " asap = %d:\n", NODE_ASAP (&ps
->g
->nodes
[i
]));
503 fprintf (file
, " time = %d:\n", nsp
->time
);
504 fprintf (file
, " stage = %d:\n", nsp
->stage
);
508 /* Set SCHED_COLUMN for each instruction in row ROW of PS. */
510 set_columns_for_row (partial_schedule_ptr ps
, int row
)
512 ps_insn_ptr cur_insn
;
516 for (cur_insn
= ps
->rows
[row
]; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
517 SCHED_COLUMN (cur_insn
->id
) = column
++;
520 /* Set SCHED_COLUMN for each instruction in PS. */
522 set_columns_for_ps (partial_schedule_ptr ps
)
526 for (row
= 0; row
< ps
->ii
; row
++)
527 set_columns_for_row (ps
, row
);
530 /* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
531 Its single predecessor has already been scheduled, as has its
532 ddg node successors. (The move may have also another move as its
533 successor, in which case that successor will be scheduled later.)
535 The move is part of a chain that satisfies register dependencies
536 between a producing ddg node and various consuming ddg nodes.
537 If some of these dependencies have a distance of 1 (meaning that
538 the use is upward-exposed) then DISTANCE1_USES is nonnull and
539 contains the set of uses with distance-1 dependencies.
540 DISTANCE1_USES is null otherwise.
542 MUST_FOLLOW is a scratch bitmap that is big enough to hold
543 all current ps_insn ids.
545 Return true on success. */
547 schedule_reg_move (partial_schedule_ptr ps
, int i_reg_move
,
548 sbitmap distance1_uses
, sbitmap must_follow
)
551 int this_time
, this_distance
, this_start
, this_end
, this_latency
;
552 int start
, end
, c
, ii
;
553 sbitmap_iterator sbi
;
554 ps_reg_move_info
*move
;
558 move
= ps_reg_move (ps
, i_reg_move
);
562 fprintf (dump_file
, "Scheduling register move INSN %d; ii = %d"
563 ", min cycle = %d\n\n", INSN_UID (move
->insn
), ii
,
565 print_rtl_single (dump_file
, move
->insn
);
566 fprintf (dump_file
, "\n%11s %11s %5s\n", "start", "end", "time");
567 fprintf (dump_file
, "=========== =========== =====\n");
573 /* For dependencies of distance 1 between a producer ddg node A
574 and consumer ddg node B, we have a chain of dependencies:
576 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
578 where Mi is the ith move. For dependencies of distance 0 between
579 a producer ddg node A and consumer ddg node C, we have a chain of
582 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
584 where Mi' occupies the same position as Mi but occurs a stage later.
585 We can only schedule each move once, so if we have both types of
586 chain, we model the second as:
588 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
590 First handle the dependencies between the previously-scheduled
591 predecessor and the move. */
592 this_insn
= ps_rtl_insn (ps
, move
->def
);
593 this_latency
= insn_latency (this_insn
, move
->insn
);
594 this_distance
= distance1_uses
&& move
->def
< ps
->g
->num_nodes
? 1 : 0;
595 this_time
= SCHED_TIME (move
->def
) - this_distance
* ii
;
596 this_start
= this_time
+ this_latency
;
597 this_end
= this_time
+ ii
;
599 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
600 this_start
, this_end
, SCHED_TIME (move
->def
),
601 INSN_UID (this_insn
), this_latency
, this_distance
,
602 INSN_UID (move
->insn
));
604 if (start
< this_start
)
609 /* Handle the dependencies between the move and previously-scheduled
611 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, u
, sbi
)
613 this_insn
= ps_rtl_insn (ps
, u
);
614 this_latency
= insn_latency (move
->insn
, this_insn
);
615 if (distance1_uses
&& !bitmap_bit_p (distance1_uses
, u
))
619 this_time
= SCHED_TIME (u
) + this_distance
* ii
;
620 this_start
= this_time
- ii
;
621 this_end
= this_time
- this_latency
;
623 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
624 this_start
, this_end
, SCHED_TIME (u
), INSN_UID (move
->insn
),
625 this_latency
, this_distance
, INSN_UID (this_insn
));
627 if (start
< this_start
)
635 fprintf (dump_file
, "----------- ----------- -----\n");
636 fprintf (dump_file
, "%11d %11d %5s %s\n", start
, end
, "", "(max, min)");
639 bitmap_clear (must_follow
);
640 bitmap_set_bit (must_follow
, move
->def
);
642 start
= MAX (start
, end
- (ii
- 1));
643 for (c
= end
; c
>= start
; c
--)
645 psi
= ps_add_node_check_conflicts (ps
, i_reg_move
, c
,
646 move
->uses
, must_follow
);
649 update_node_sched_params (i_reg_move
, ii
, c
, PS_MIN_CYCLE (ps
));
651 fprintf (dump_file
, "\nScheduled register move INSN %d at"
652 " time %d, row %d\n\n", INSN_UID (move
->insn
), c
,
653 SCHED_ROW (i_reg_move
));
659 fprintf (dump_file
, "\nNo available slot\n\n");
665 Breaking intra-loop register anti-dependences:
666 Each intra-loop register anti-dependence implies a cross-iteration true
667 dependence of distance 1. Therefore, we can remove such false dependencies
668 and figure out if the partial schedule broke them by checking if (for a
669 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
670 if so generate a register move. The number of such moves is equal to:
671 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
672 nreg_moves = ----------------------------------- + 1 - { dependence.
676 schedule_reg_moves (partial_schedule_ptr ps
)
682 for (i
= 0; i
< g
->num_nodes
; i
++)
684 ddg_node_ptr u
= &g
->nodes
[i
];
686 int nreg_moves
= 0, i_reg_move
;
687 rtx prev_reg
, old_reg
;
691 sbitmap distance1_uses
;
692 rtx set
= single_set (u
->insn
);
694 /* Skip instructions that do not set a register. */
695 if ((set
&& !REG_P (SET_DEST (set
))))
698 /* Compute the number of reg_moves needed for u, by looking at life
699 ranges started at u (excluding self-loops). */
700 distances
[0] = distances
[1] = false;
701 for (e
= u
->out
; e
; e
= e
->next_out
)
702 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
704 int nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
705 - SCHED_TIME (e
->src
->cuid
)) / ii
;
707 if (e
->distance
== 1)
708 nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
709 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
711 /* If dest precedes src in the schedule of the kernel, then dest
712 will read before src writes and we can save one reg_copy. */
713 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
714 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
717 if (nreg_moves4e
>= 1)
719 /* !single_set instructions are not supported yet and
720 thus we do not except to encounter them in the loop
721 except from the doloop part. For the latter case
722 we assume no regmoves are generated as the doloop
723 instructions are tied to the branch with an edge. */
725 /* If the instruction contains auto-inc register then
726 validate that the regmov is being generated for the
727 target regsiter rather then the inc'ed register. */
728 gcc_assert (!autoinc_var_is_used_p (u
->insn
, e
->dest
->insn
));
733 gcc_assert (e
->distance
< 2);
734 distances
[e
->distance
] = true;
736 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
742 /* Create NREG_MOVES register moves. */
743 first_move
= ps
->reg_moves
.length ();
744 ps
->reg_moves
.safe_grow_cleared (first_move
+ nreg_moves
);
745 extend_node_sched_params (ps
);
747 /* Record the moves associated with this node. */
748 first_move
+= ps
->g
->num_nodes
;
750 /* Generate each move. */
751 old_reg
= prev_reg
= SET_DEST (single_set (u
->insn
));
752 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
754 ps_reg_move_info
*move
= ps_reg_move (ps
, first_move
+ i_reg_move
);
756 move
->def
= i_reg_move
> 0 ? first_move
+ i_reg_move
- 1 : i
;
757 move
->uses
= sbitmap_alloc (first_move
+ nreg_moves
);
758 move
->old_reg
= old_reg
;
759 move
->new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
760 move
->num_consecutive_stages
= distances
[0] && distances
[1] ? 2 : 1;
761 move
->insn
= gen_move_insn (move
->new_reg
, copy_rtx (prev_reg
));
762 bitmap_clear (move
->uses
);
764 prev_reg
= move
->new_reg
;
767 distance1_uses
= distances
[1] ? sbitmap_alloc (g
->num_nodes
) : NULL
;
769 /* Every use of the register defined by node may require a different
770 copy of this register, depending on the time the use is scheduled.
771 Record which uses require which move results. */
772 for (e
= u
->out
; e
; e
= e
->next_out
)
773 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
775 int dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
776 - SCHED_TIME (e
->src
->cuid
)) / ii
;
778 if (e
->distance
== 1)
779 dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
780 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
782 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
783 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
788 ps_reg_move_info
*move
;
790 move
= ps_reg_move (ps
, first_move
+ dest_copy
- 1);
791 bitmap_set_bit (move
->uses
, e
->dest
->cuid
);
792 if (e
->distance
== 1)
793 bitmap_set_bit (distance1_uses
, e
->dest
->cuid
);
797 must_follow
= sbitmap_alloc (first_move
+ nreg_moves
);
798 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
799 if (!schedule_reg_move (ps
, first_move
+ i_reg_move
,
800 distance1_uses
, must_follow
))
802 sbitmap_free (must_follow
);
804 sbitmap_free (distance1_uses
);
805 if (i_reg_move
< nreg_moves
)
811 /* Emit the moves associatied with PS. Apply the substitutions
812 associated with them. */
814 apply_reg_moves (partial_schedule_ptr ps
)
816 ps_reg_move_info
*move
;
819 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
822 sbitmap_iterator sbi
;
824 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, i_use
, sbi
)
826 replace_rtx (ps
->g
->nodes
[i_use
].insn
, move
->old_reg
, move
->new_reg
);
827 df_insn_rescan (ps
->g
->nodes
[i_use
].insn
);
832 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
833 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
834 will move to cycle zero. */
836 reset_sched_times (partial_schedule_ptr ps
, int amount
)
840 ps_insn_ptr crr_insn
;
842 for (row
= 0; row
< ii
; row
++)
843 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
845 int u
= crr_insn
->id
;
846 int normalized_time
= SCHED_TIME (u
) - amount
;
847 int new_min_cycle
= PS_MIN_CYCLE (ps
) - amount
;
851 /* Print the scheduling times after the rotation. */
852 rtx insn
= ps_rtl_insn (ps
, u
);
854 fprintf (dump_file
, "crr_insn->node=%d (insn id %d), "
855 "crr_insn->cycle=%d, min_cycle=%d", u
,
856 INSN_UID (insn
), normalized_time
, new_min_cycle
);
858 fprintf (dump_file
, " (branch)");
859 fprintf (dump_file
, "\n");
862 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
863 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
865 crr_insn
->cycle
= normalized_time
;
866 update_node_sched_params (u
, ii
, normalized_time
, new_min_cycle
);
870 /* Permute the insns according to their order in PS, from row 0 to
871 row ii-1, and position them right before LAST. This schedules
872 the insns of the loop kernel. */
874 permute_partial_schedule (partial_schedule_ptr ps
, rtx last
)
880 for (row
= 0; row
< ii
; row
++)
881 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
883 rtx insn
= ps_rtl_insn (ps
, ps_ij
->id
);
885 if (PREV_INSN (last
) != insn
)
887 if (ps_ij
->id
< ps
->g
->num_nodes
)
888 reorder_insns_nobb (ps_first_note (ps
, ps_ij
->id
), insn
,
891 add_insn_before (insn
, last
, NULL
);
896 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
897 respectively only if cycle C falls on the border of the scheduling
898 window boundaries marked by START and END cycles. STEP is the
899 direction of the window. */
901 set_must_precede_follow (sbitmap
*tmp_follow
, sbitmap must_follow
,
902 sbitmap
*tmp_precede
, sbitmap must_precede
, int c
,
903 int start
, int end
, int step
)
911 *tmp_precede
= must_precede
;
912 else /* step == -1. */
913 *tmp_follow
= must_follow
;
918 *tmp_follow
= must_follow
;
919 else /* step == -1. */
920 *tmp_precede
= must_precede
;
925 /* Return True if the branch can be moved to row ii-1 while
926 normalizing the partial schedule PS to start from cycle zero and thus
927 optimize the SC. Otherwise return False. */
929 optimize_sc (partial_schedule_ptr ps
, ddg_ptr g
)
931 int amount
= PS_MIN_CYCLE (ps
);
932 sbitmap sched_nodes
= sbitmap_alloc (g
->num_nodes
);
933 int start
, end
, step
;
936 int stage_count
, stage_count_curr
;
938 /* Compare the SC after normalization and SC after bringing the branch
939 to row ii-1. If they are equal just bail out. */
940 stage_count
= calculate_stage_count (ps
, amount
);
942 calculate_stage_count (ps
, SCHED_TIME (g
->closing_branch
->cuid
) - (ii
- 1));
944 if (stage_count
== stage_count_curr
)
947 fprintf (dump_file
, "SMS SC already optimized.\n");
955 fprintf (dump_file
, "SMS Trying to optimize branch location\n");
956 fprintf (dump_file
, "SMS partial schedule before trial:\n");
957 print_partial_schedule (ps
, dump_file
);
960 /* First, normalize the partial scheduling. */
961 reset_sched_times (ps
, amount
);
962 rotate_partial_schedule (ps
, amount
);
966 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
968 print_partial_schedule (ps
, dump_file
);
971 if (SMODULO (SCHED_TIME (g
->closing_branch
->cuid
), ii
) == ii
- 1)
977 bitmap_ones (sched_nodes
);
979 /* Calculate the new placement of the branch. It should be in row
980 ii-1 and fall into it's scheduling window. */
981 if (get_sched_window (ps
, g
->closing_branch
, sched_nodes
, ii
, &start
,
985 ps_insn_ptr next_ps_i
;
986 int branch_cycle
= SCHED_TIME (g
->closing_branch
->cuid
);
987 int row
= SMODULO (branch_cycle
, ps
->ii
);
989 sbitmap must_precede
, must_follow
, tmp_precede
, tmp_follow
;
993 fprintf (dump_file
, "\nTrying to schedule node %d "
994 "INSN = %d in (%d .. %d) step %d\n",
995 g
->closing_branch
->cuid
,
996 (INSN_UID (g
->closing_branch
->insn
)), start
, end
, step
);
998 gcc_assert ((step
> 0 && start
< end
) || (step
< 0 && start
> end
));
1001 c
= start
+ ii
- SMODULO (start
, ii
) - 1;
1002 gcc_assert (c
>= start
);
1008 "SMS failed to schedule branch at cycle: %d\n", c
);
1014 c
= start
- SMODULO (start
, ii
) - 1;
1015 gcc_assert (c
<= start
);
1021 "SMS failed to schedule branch at cycle: %d\n", c
);
1027 must_precede
= sbitmap_alloc (g
->num_nodes
);
1028 must_follow
= sbitmap_alloc (g
->num_nodes
);
1030 /* Try to schedule the branch is it's new cycle. */
1031 calculate_must_precede_follow (g
->closing_branch
, start
, end
,
1032 step
, ii
, sched_nodes
,
1033 must_precede
, must_follow
);
1035 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1036 must_precede
, c
, start
, end
, step
);
1038 /* Find the element in the partial schedule related to the closing
1039 branch so we can remove it from it's current cycle. */
1040 for (next_ps_i
= ps
->rows
[row
];
1041 next_ps_i
; next_ps_i
= next_ps_i
->next_in_row
)
1042 if (next_ps_i
->id
== g
->closing_branch
->cuid
)
1045 remove_node_from_ps (ps
, next_ps_i
);
1047 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
, c
,
1048 sched_nodes
, &num_splits
,
1049 tmp_precede
, tmp_follow
);
1050 gcc_assert (num_splits
== 0);
1055 "SMS failed to schedule branch at cycle: %d, "
1056 "bringing it back to cycle %d\n", c
, branch_cycle
);
1058 /* The branch was failed to be placed in row ii - 1.
1059 Put it back in it's original place in the partial
1061 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1062 must_precede
, branch_cycle
, start
, end
,
1065 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
,
1066 branch_cycle
, sched_nodes
,
1067 &num_splits
, tmp_precede
,
1069 gcc_assert (success
&& (num_splits
== 0));
1074 /* The branch is placed in row ii - 1. */
1077 "SMS success in moving branch to cycle %d\n", c
);
1079 update_node_sched_params (g
->closing_branch
->cuid
, ii
, c
,
1084 free (must_precede
);
1094 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
1095 int to_stage
, rtx count_reg
)
1100 for (row
= 0; row
< ps
->ii
; row
++)
1101 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
1104 int first_u
, last_u
;
1107 /* Do not duplicate any insn which refers to count_reg as it
1108 belongs to the control part.
1109 The closing branch is scheduled as well and thus should
1111 TODO: This should be done by analyzing the control part of
1113 u_insn
= ps_rtl_insn (ps
, u
);
1114 if (reg_mentioned_p (count_reg
, u_insn
)
1118 first_u
= SCHED_STAGE (u
);
1119 last_u
= first_u
+ ps_num_consecutive_stages (ps
, u
) - 1;
1120 if (from_stage
<= last_u
&& to_stage
>= first_u
)
1122 if (u
< ps
->g
->num_nodes
)
1123 duplicate_insn_chain (ps_first_note (ps
, u
), u_insn
);
1125 emit_insn (copy_rtx (PATTERN (u_insn
)));
1131 /* Generate the instructions (including reg_moves) for prolog & epilog. */
1133 generate_prolog_epilog (partial_schedule_ptr ps
, struct loop
*loop
,
1134 rtx count_reg
, rtx count_init
)
1137 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
1140 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1145 /* Generate instructions at the beginning of the prolog to
1146 adjust the loop count by STAGE_COUNT. If loop count is constant
1147 (count_init), this constant is adjusted by STAGE_COUNT in
1148 generate_prolog_epilog function. */
1149 rtx sub_reg
= NULL_RTX
;
1151 sub_reg
= expand_simple_binop (GET_MODE (count_reg
), MINUS
,
1152 count_reg
, GEN_INT (last_stage
),
1153 count_reg
, 1, OPTAB_DIRECT
);
1154 gcc_assert (REG_P (sub_reg
));
1155 if (REGNO (sub_reg
) != REGNO (count_reg
))
1156 emit_move_insn (count_reg
, sub_reg
);
1159 for (i
= 0; i
< last_stage
; i
++)
1160 duplicate_insns_of_cycles (ps
, 0, i
, count_reg
);
1162 /* Put the prolog on the entry edge. */
1163 e
= loop_preheader_edge (loop
);
1164 split_edge_and_insert (e
, get_insns ());
1165 if (!flag_resched_modulo_sched
)
1166 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1170 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1173 for (i
= 0; i
< last_stage
; i
++)
1174 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, count_reg
);
1176 /* Put the epilogue on the exit edge. */
1177 gcc_assert (single_exit (loop
));
1178 e
= single_exit (loop
);
1179 split_edge_and_insert (e
, get_insns ());
1180 if (!flag_resched_modulo_sched
)
1181 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1186 /* Mark LOOP as software pipelined so the later
1187 scheduling passes don't touch it. */
1189 mark_loop_unsched (struct loop
*loop
)
1192 basic_block
*bbs
= get_loop_body (loop
);
1194 for (i
= 0; i
< loop
->num_nodes
; i
++)
1195 bbs
[i
]->flags
|= BB_DISABLE_SCHEDULE
;
1200 /* Return true if all the BBs of the loop are empty except the
1203 loop_single_full_bb_p (struct loop
*loop
)
1206 basic_block
*bbs
= get_loop_body (loop
);
1208 for (i
= 0; i
< loop
->num_nodes
; i
++)
1211 bool empty_bb
= true;
1213 if (bbs
[i
] == loop
->header
)
1216 /* Make sure that basic blocks other than the header
1217 have only notes labels or jumps. */
1218 get_ebb_head_tail (bbs
[i
], bbs
[i
], &head
, &tail
);
1219 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
1221 if (NOTE_P (head
) || LABEL_P (head
)
1222 || (INSN_P (head
) && (DEBUG_INSN_P (head
) || JUMP_P (head
))))
1238 /* Dump file:line from INSN's location info to dump_file. */
1241 dump_insn_location (rtx insn
)
1243 if (dump_file
&& INSN_LOCATION (insn
))
1245 const char *file
= insn_file (insn
);
1247 fprintf (dump_file
, " %s:%i", file
, insn_line (insn
));
1251 /* A simple loop from SMS point of view; it is a loop that is composed of
1252 either a single basic block or two BBs - a header and a latch. */
1253 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1254 && (EDGE_COUNT (loop->latch->preds) == 1) \
1255 && (EDGE_COUNT (loop->latch->succs) == 1))
1257 /* Return true if the loop is in its canonical form and false if not.
1258 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1260 loop_canon_p (struct loop
*loop
)
1263 if (loop
->inner
|| !loop_outer (loop
))
1266 fprintf (dump_file
, "SMS loop inner or !loop_outer\n");
1270 if (!single_exit (loop
))
1274 rtx insn
= BB_END (loop
->header
);
1276 fprintf (dump_file
, "SMS loop many exits");
1277 dump_insn_location (insn
);
1278 fprintf (dump_file
, "\n");
1283 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
1287 rtx insn
= BB_END (loop
->header
);
1289 fprintf (dump_file
, "SMS loop many BBs.");
1290 dump_insn_location (insn
);
1291 fprintf (dump_file
, "\n");
1299 /* If there are more than one entry for the loop,
1300 make it one by splitting the first entry edge and
1301 redirecting the others to the new BB. */
1303 canon_loop (struct loop
*loop
)
1308 /* Avoid annoying special cases of edges going to exit
1310 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR
->preds
)
1311 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
1314 if (loop
->latch
== loop
->header
1315 || EDGE_COUNT (loop
->latch
->succs
) > 1)
1317 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
1318 if (e
->src
== loop
->latch
)
1326 setup_sched_infos (void)
1328 memcpy (&sms_common_sched_info
, &haifa_common_sched_info
,
1329 sizeof (sms_common_sched_info
));
1330 sms_common_sched_info
.sched_pass_id
= SCHED_SMS_PASS
;
1331 common_sched_info
= &sms_common_sched_info
;
1333 sched_deps_info
= &sms_sched_deps_info
;
1334 current_sched_info
= &sms_sched_info
;
1337 /* Probability in % that the sms-ed loop rolls enough so that optimized
1338 version may be entered. Just a guess. */
1339 #define PROB_SMS_ENOUGH_ITERATIONS 80
1341 /* Used to calculate the upper bound of ii. */
1342 #define MAXII_FACTOR 2
1344 /* Main entry point, perform SMS scheduling on the loops of the function
1345 that consist of single basic blocks. */
1352 int maxii
, max_asap
;
1354 partial_schedule_ptr ps
;
1355 basic_block bb
= NULL
;
1357 basic_block condition_bb
= NULL
;
1359 gcov_type trip_count
= 0;
1361 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1362 | LOOPS_HAVE_RECORDED_EXITS
);
1363 if (number_of_loops () <= 1)
1365 loop_optimizer_finalize ();
1366 return; /* There are no loops to schedule. */
1369 /* Initialize issue_rate. */
1370 if (targetm
.sched
.issue_rate
)
1372 int temp
= reload_completed
;
1374 reload_completed
= 1;
1375 issue_rate
= targetm
.sched
.issue_rate ();
1376 reload_completed
= temp
;
1381 /* Initialize the scheduler. */
1382 setup_sched_infos ();
1383 haifa_sched_init ();
1385 /* Allocate memory to hold the DDG array one entry for each loop.
1386 We use loop->num as index into this array. */
1387 g_arr
= XCNEWVEC (ddg_ptr
, number_of_loops ());
1391 fprintf (dump_file
, "\n\nSMS analysis phase\n");
1392 fprintf (dump_file
, "===================\n\n");
1395 /* Build DDGs for all the relevant loops and hold them in G_ARR
1396 indexed by the loop index. */
1397 FOR_EACH_LOOP (li
, loop
, 0)
1402 /* For debugging. */
1403 if (dbg_cnt (sms_sched_loop
) == false)
1406 fprintf (dump_file
, "SMS reached max limit... \n");
1408 FOR_EACH_LOOP_BREAK (li
);
1413 rtx insn
= BB_END (loop
->header
);
1415 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1416 dump_insn_location (insn
);
1417 fprintf (dump_file
, "\n");
1420 if (! loop_canon_p (loop
))
1423 if (! loop_single_full_bb_p (loop
))
1426 fprintf (dump_file
, "SMS not loop_single_full_bb_p\n");
1432 get_ebb_head_tail (bb
, bb
, &head
, &tail
);
1433 latch_edge
= loop_latch_edge (loop
);
1434 gcc_assert (single_exit (loop
));
1435 if (single_exit (loop
)->count
)
1436 trip_count
= latch_edge
->count
/ single_exit (loop
)->count
;
1438 /* Perform SMS only on loops that their average count is above threshold. */
1440 if ( latch_edge
->count
1441 && (latch_edge
->count
< single_exit (loop
)->count
* SMS_LOOP_AVERAGE_COUNT_THRESHOLD
))
1445 dump_insn_location (tail
);
1446 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1447 if (profile_info
&& flag_branch_probabilities
)
1449 fprintf (dump_file
, "SMS loop-count ");
1450 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1451 (HOST_WIDEST_INT
) bb
->count
);
1452 fprintf (dump_file
, "\n");
1453 fprintf (dump_file
, "SMS trip-count ");
1454 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1455 (HOST_WIDEST_INT
) trip_count
);
1456 fprintf (dump_file
, "\n");
1457 fprintf (dump_file
, "SMS profile-sum-max ");
1458 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1459 (HOST_WIDEST_INT
) profile_info
->sum_max
);
1460 fprintf (dump_file
, "\n");
1466 /* Make sure this is a doloop. */
1467 if ( !(count_reg
= doloop_register_get (head
, tail
)))
1470 fprintf (dump_file
, "SMS doloop_register_get failed\n");
1474 /* Don't handle BBs with calls or barriers
1475 or !single_set with the exception of instructions that include
1476 count_reg---these instructions are part of the control part
1477 that do-loop recognizes.
1478 ??? Should handle insns defining subregs. */
1479 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1485 || (NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1486 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
1487 && !reg_mentioned_p (count_reg
, insn
))
1488 || (INSN_P (insn
) && (set
= single_set (insn
))
1489 && GET_CODE (SET_DEST (set
)) == SUBREG
))
1493 if (insn
!= NEXT_INSN (tail
))
1498 fprintf (dump_file
, "SMS loop-with-call\n");
1499 else if (BARRIER_P (insn
))
1500 fprintf (dump_file
, "SMS loop-with-barrier\n");
1501 else if ((NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1502 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
1503 fprintf (dump_file
, "SMS loop-with-not-single-set\n");
1505 fprintf (dump_file
, "SMS loop with subreg in lhs\n");
1506 print_rtl_single (dump_file
, insn
);
1512 /* Always schedule the closing branch with the rest of the
1513 instructions. The branch is rotated to be in row ii-1 at the
1514 end of the scheduling procedure to make sure it's the last
1515 instruction in the iteration. */
1516 if (! (g
= create_ddg (bb
, 1)))
1519 fprintf (dump_file
, "SMS create_ddg failed\n");
1523 g_arr
[loop
->num
] = g
;
1525 fprintf (dump_file
, "...OK\n");
1530 fprintf (dump_file
, "\nSMS transformation phase\n");
1531 fprintf (dump_file
, "=========================\n\n");
1534 /* We don't want to perform SMS on new loops - created by versioning. */
1535 FOR_EACH_LOOP (li
, loop
, 0)
1538 rtx count_reg
, count_init
;
1539 int mii
, rec_mii
, stage_count
, min_cycle
;
1540 HOST_WIDEST_INT loop_count
= 0;
1543 if (! (g
= g_arr
[loop
->num
]))
1548 rtx insn
= BB_END (loop
->header
);
1550 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1551 dump_insn_location (insn
);
1552 fprintf (dump_file
, "\n");
1554 print_ddg (dump_file
, g
);
1557 get_ebb_head_tail (loop
->header
, loop
->header
, &head
, &tail
);
1559 latch_edge
= loop_latch_edge (loop
);
1560 gcc_assert (single_exit (loop
));
1561 if (single_exit (loop
)->count
)
1562 trip_count
= latch_edge
->count
/ single_exit (loop
)->count
;
1566 dump_insn_location (tail
);
1567 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1568 if (profile_info
&& flag_branch_probabilities
)
1570 fprintf (dump_file
, "SMS loop-count ");
1571 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1572 (HOST_WIDEST_INT
) bb
->count
);
1573 fprintf (dump_file
, "\n");
1574 fprintf (dump_file
, "SMS profile-sum-max ");
1575 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1576 (HOST_WIDEST_INT
) profile_info
->sum_max
);
1577 fprintf (dump_file
, "\n");
1579 fprintf (dump_file
, "SMS doloop\n");
1580 fprintf (dump_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1581 fprintf (dump_file
, "SMS num-loads %d\n", g
->num_loads
);
1582 fprintf (dump_file
, "SMS num-stores %d\n", g
->num_stores
);
1586 /* In case of th loop have doloop register it gets special
1588 count_init
= NULL_RTX
;
1589 if ((count_reg
= doloop_register_get (head
, tail
)))
1591 basic_block pre_header
;
1593 pre_header
= loop_preheader_edge (loop
)->src
;
1594 count_init
= const_iteration_count (count_reg
, pre_header
,
1597 gcc_assert (count_reg
);
1599 if (dump_file
&& count_init
)
1601 fprintf (dump_file
, "SMS const-doloop ");
1602 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1604 fprintf (dump_file
, "\n");
1607 node_order
= XNEWVEC (int, g
->num_nodes
);
1609 mii
= 1; /* Need to pass some estimate of mii. */
1610 rec_mii
= sms_order_nodes (g
, mii
, node_order
, &max_asap
);
1611 mii
= MAX (res_MII (g
), rec_mii
);
1612 maxii
= MAX (max_asap
, MAXII_FACTOR
* mii
);
1615 fprintf (dump_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1616 rec_mii
, mii
, maxii
);
1620 set_node_sched_params (g
);
1624 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
);
1628 /* Try to achieve optimized SC by normalizing the partial
1629 schedule (having the cycles start from cycle zero).
1630 The branch location must be placed in row ii-1 in the
1631 final scheduling. If failed, shift all instructions to
1632 position the branch in row ii-1. */
1633 opt_sc_p
= optimize_sc (ps
, g
);
1635 stage_count
= calculate_stage_count (ps
, 0);
1638 /* Bring the branch to cycle ii-1. */
1639 int amount
= (SCHED_TIME (g
->closing_branch
->cuid
)
1643 fprintf (dump_file
, "SMS schedule branch at cycle ii-1\n");
1645 stage_count
= calculate_stage_count (ps
, amount
);
1648 gcc_assert (stage_count
>= 1);
1651 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
1652 1 means that there is no interleaving between iterations thus
1653 we let the scheduling passes do the job in this case. */
1654 if (stage_count
< PARAM_VALUE (PARAM_SMS_MIN_SC
)
1655 || (count_init
&& (loop_count
<= stage_count
))
1656 || (flag_branch_probabilities
&& (trip_count
<= stage_count
)))
1660 fprintf (dump_file
, "SMS failed... \n");
1661 fprintf (dump_file
, "SMS sched-failed (stage-count=%d,"
1662 " loop-count=", stage_count
);
1663 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, loop_count
);
1664 fprintf (dump_file
, ", trip-count=");
1665 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, trip_count
);
1666 fprintf (dump_file
, ")\n");
1673 /* Rotate the partial schedule to have the branch in row ii-1. */
1674 int amount
= SCHED_TIME (g
->closing_branch
->cuid
) - (ps
->ii
- 1);
1676 reset_sched_times (ps
, amount
);
1677 rotate_partial_schedule (ps
, amount
);
1680 set_columns_for_ps (ps
);
1682 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1683 if (!schedule_reg_moves (ps
))
1686 free_partial_schedule (ps
);
1690 /* Moves that handle incoming values might have been added
1691 to a new first stage. Bump the stage count if so.
1693 ??? Perhaps we could consider rotating the schedule here
1695 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1697 reset_sched_times (ps
, 0);
1701 /* The stage count should now be correct without rotation. */
1702 gcc_checking_assert (stage_count
== calculate_stage_count (ps
, 0));
1703 PS_STAGE_COUNT (ps
) = stage_count
;
1709 dump_insn_location (tail
);
1710 fprintf (dump_file
, " SMS succeeded %d %d (with ii, sc)\n",
1711 ps
->ii
, stage_count
);
1712 print_partial_schedule (ps
, dump_file
);
1715 /* case the BCT count is not known , Do loop-versioning */
1716 if (count_reg
&& ! count_init
)
1718 rtx comp_rtx
= gen_rtx_fmt_ee (GT
, VOIDmode
, count_reg
,
1719 GEN_INT(stage_count
));
1720 unsigned prob
= (PROB_SMS_ENOUGH_ITERATIONS
1721 * REG_BR_PROB_BASE
) / 100;
1723 loop_version (loop
, comp_rtx
, &condition_bb
,
1724 prob
, prob
, REG_BR_PROB_BASE
- prob
,
1728 /* Set new iteration count of loop kernel. */
1729 if (count_reg
&& count_init
)
1730 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1733 /* Now apply the scheduled kernel to the RTL of the loop. */
1734 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1736 /* Mark this loop as software pipelined so the later
1737 scheduling passes don't touch it. */
1738 if (! flag_resched_modulo_sched
)
1739 mark_loop_unsched (loop
);
1741 /* The life-info is not valid any more. */
1742 df_set_bb_dirty (g
->bb
);
1744 apply_reg_moves (ps
);
1746 print_node_sched_params (dump_file
, g
->num_nodes
, ps
);
1747 /* Generate prolog and epilog. */
1748 generate_prolog_epilog (ps
, loop
, count_reg
, count_init
);
1752 free_partial_schedule (ps
);
1753 node_sched_param_vec
.release ();
1760 /* Release scheduler data, needed until now because of DFA. */
1761 haifa_sched_finish ();
1762 loop_optimizer_finalize ();
1765 /* The SMS scheduling algorithm itself
1766 -----------------------------------
1767 Input: 'O' an ordered list of insns of a loop.
1768 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1770 'Q' is the empty Set
1771 'PS' is the partial schedule; it holds the currently scheduled nodes with
1773 'PSP' previously scheduled predecessors.
1774 'PSS' previously scheduled successors.
1775 't(u)' the cycle where u is scheduled.
1776 'l(u)' is the latency of u.
1777 'd(v,u)' is the dependence distance from v to u.
1778 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1779 the node ordering phase.
1780 'check_hardware_resources_conflicts(u, PS, c)'
1781 run a trace around cycle/slot through DFA model
1782 to check resource conflicts involving instruction u
1783 at cycle c given the partial schedule PS.
1784 'add_to_partial_schedule_at_time(u, PS, c)'
1785 Add the node/instruction u to the partial schedule
1787 'calculate_register_pressure(PS)'
1788 Given a schedule of instructions, calculate the register
1789 pressure it implies. One implementation could be the
1790 maximum number of overlapping live ranges.
1791 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1792 registers available in the hardware.
1796 3. for each node u in O in pre-computed order
1797 4. if (PSP(u) != Q && PSS(u) == Q) then
1798 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1799 6. start = Early_start; end = Early_start + II - 1; step = 1
1800 11. else if (PSP(u) == Q && PSS(u) != Q) then
1801 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1802 13. start = Late_start; end = Late_start - II + 1; step = -1
1803 14. else if (PSP(u) != Q && PSS(u) != Q) then
1804 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1805 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1806 17. start = Early_start;
1807 18. end = min(Early_start + II - 1 , Late_start);
1809 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1810 21. start = ASAP(u); end = start + II - 1; step = 1
1814 24. for (c = start ; c != end ; c += step)
1815 25. if check_hardware_resources_conflicts(u, PS, c) then
1816 26. add_to_partial_schedule_at_time(u, PS, c)
1821 31. if (success == false) then
1823 33. if (II > maxII) then
1824 34. finish - failed to schedule
1829 39. if (calculate_register_pressure(PS) > maxRP) then
1832 42. compute epilogue & prologue
1833 43. finish - succeeded to schedule
1835 ??? The algorithm restricts the scheduling window to II cycles.
1836 In rare cases, it may be better to allow windows of II+1 cycles.
1837 The window would then start and end on the same row, but with
1838 different "must precede" and "must follow" requirements. */
1840 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1841 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1842 set to 0 to save compile time. */
1843 #define DFA_HISTORY SMS_DFA_HISTORY
1845 /* A threshold for the number of repeated unsuccessful attempts to insert
1846 an empty row, before we flush the partial schedule and start over. */
1847 #define MAX_SPLIT_NUM 10
1848 /* Given the partial schedule PS, this function calculates and returns the
1849 cycles in which we can schedule the node with the given index I.
1850 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1851 noticed that there are several cases in which we fail to SMS the loop
1852 because the sched window of a node is empty due to tight data-deps. In
1853 such cases we want to unschedule some of the predecessors/successors
1854 until we get non-empty scheduling window. It returns -1 if the
1855 scheduling window is empty and zero otherwise. */
1858 get_sched_window (partial_schedule_ptr ps
, ddg_node_ptr u_node
,
1859 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
,
1862 int start
, step
, end
;
1863 int early_start
, late_start
;
1865 sbitmap psp
= sbitmap_alloc (ps
->g
->num_nodes
);
1866 sbitmap pss
= sbitmap_alloc (ps
->g
->num_nodes
);
1867 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1868 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1874 /* 1. compute sched window for u (start, end, step). */
1877 psp_not_empty
= bitmap_and (psp
, u_node_preds
, sched_nodes
);
1878 pss_not_empty
= bitmap_and (pss
, u_node_succs
, sched_nodes
);
1880 /* We first compute a forward range (start <= end), then decide whether
1882 early_start
= INT_MIN
;
1883 late_start
= INT_MAX
;
1891 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1893 fprintf (dump_file
, "\nAnalyzing dependencies for node %d (INSN %d)"
1894 "; ii = %d\n\n", u_node
->cuid
, INSN_UID (u_node
->insn
), ii
);
1895 fprintf (dump_file
, "%11s %11s %11s %11s %5s\n",
1896 "start", "early start", "late start", "end", "time");
1897 fprintf (dump_file
, "=========== =========== =========== ==========="
1900 /* Calculate early_start and limit end. Both bounds are inclusive. */
1902 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1904 int v
= e
->src
->cuid
;
1906 if (bitmap_bit_p (sched_nodes
, v
))
1908 int p_st
= SCHED_TIME (v
);
1909 int earliest
= p_st
+ e
->latency
- (e
->distance
* ii
);
1910 int latest
= (e
->data_type
== MEM_DEP
? p_st
+ ii
- 1 : INT_MAX
);
1914 fprintf (dump_file
, "%11s %11d %11s %11d %5d",
1915 "", earliest
, "", latest
, p_st
);
1916 print_ddg_edge (dump_file
, e
);
1917 fprintf (dump_file
, "\n");
1920 early_start
= MAX (early_start
, earliest
);
1921 end
= MIN (end
, latest
);
1923 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1928 /* Calculate late_start and limit start. Both bounds are inclusive. */
1930 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1932 int v
= e
->dest
->cuid
;
1934 if (bitmap_bit_p (sched_nodes
, v
))
1936 int s_st
= SCHED_TIME (v
);
1937 int earliest
= (e
->data_type
== MEM_DEP
? s_st
- ii
+ 1 : INT_MIN
);
1938 int latest
= s_st
- e
->latency
+ (e
->distance
* ii
);
1942 fprintf (dump_file
, "%11d %11s %11d %11s %5d",
1943 earliest
, "", latest
, "", s_st
);
1944 print_ddg_edge (dump_file
, e
);
1945 fprintf (dump_file
, "\n");
1948 start
= MAX (start
, earliest
);
1949 late_start
= MIN (late_start
, latest
);
1951 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1956 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1958 fprintf (dump_file
, "----------- ----------- ----------- -----------"
1960 fprintf (dump_file
, "%11d %11d %11d %11d %5s %s\n",
1961 start
, early_start
, late_start
, end
, "",
1962 "(max, max, min, min)");
1965 /* Get a target scheduling window no bigger than ii. */
1966 if (early_start
== INT_MIN
&& late_start
== INT_MAX
)
1967 early_start
= NODE_ASAP (u_node
);
1968 else if (early_start
== INT_MIN
)
1969 early_start
= late_start
- (ii
- 1);
1970 late_start
= MIN (late_start
, early_start
+ (ii
- 1));
1972 /* Apply memory dependence limits. */
1973 start
= MAX (start
, early_start
);
1974 end
= MIN (end
, late_start
);
1976 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1977 fprintf (dump_file
, "%11s %11d %11d %11s %5s final window\n",
1978 "", start
, end
, "", "");
1980 /* If there are at least as many successors as predecessors, schedule the
1981 node close to its successors. */
1982 if (pss_not_empty
&& count_succs
>= count_preds
)
1990 /* Now that we've finalized the window, make END an exclusive rather
1991 than an inclusive bound. */
2000 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
2003 fprintf (dump_file
, "\nEmpty window: start=%d, end=%d, step=%d\n",
2011 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
2012 node currently been scheduled. At the end of the calculation
2013 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
2014 U_NODE which are (1) already scheduled in the first/last row of
2015 U_NODE's scheduling window, (2) whose dependence inequality with U
2016 becomes an equality when U is scheduled in this same row, and (3)
2017 whose dependence latency is zero.
2019 The first and last rows are calculated using the following parameters:
2020 START/END rows - The cycles that begins/ends the traversal on the window;
2021 searching for an empty cycle to schedule U_NODE.
2022 STEP - The direction in which we traverse the window.
2023 II - The initiation interval. */
2026 calculate_must_precede_follow (ddg_node_ptr u_node
, int start
, int end
,
2027 int step
, int ii
, sbitmap sched_nodes
,
2028 sbitmap must_precede
, sbitmap must_follow
)
2031 int first_cycle_in_window
, last_cycle_in_window
;
2033 gcc_assert (must_precede
&& must_follow
);
2035 /* Consider the following scheduling window:
2036 {first_cycle_in_window, first_cycle_in_window+1, ...,
2037 last_cycle_in_window}. If step is 1 then the following will be
2038 the order we traverse the window: {start=first_cycle_in_window,
2039 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
2040 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
2041 end=first_cycle_in_window-1} if step is -1. */
2042 first_cycle_in_window
= (step
== 1) ? start
: end
- step
;
2043 last_cycle_in_window
= (step
== 1) ? end
- step
: start
;
2045 bitmap_clear (must_precede
);
2046 bitmap_clear (must_follow
);
2049 fprintf (dump_file
, "\nmust_precede: ");
2051 /* Instead of checking if:
2052 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
2053 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
2054 first_cycle_in_window)
2056 we use the fact that latency is non-negative:
2057 SCHED_TIME (e->src) - (e->distance * ii) <=
2058 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
2059 first_cycle_in_window
2061 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
2062 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2063 if (bitmap_bit_p (sched_nodes
, e
->src
->cuid
)
2064 && ((SCHED_TIME (e
->src
->cuid
) - (e
->distance
* ii
)) ==
2065 first_cycle_in_window
))
2068 fprintf (dump_file
, "%d ", e
->src
->cuid
);
2070 bitmap_set_bit (must_precede
, e
->src
->cuid
);
2074 fprintf (dump_file
, "\nmust_follow: ");
2076 /* Instead of checking if:
2077 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
2078 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
2079 last_cycle_in_window)
2081 we use the fact that latency is non-negative:
2082 SCHED_TIME (e->dest) + (e->distance * ii) >=
2083 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
2084 last_cycle_in_window
2086 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
2087 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2088 if (bitmap_bit_p (sched_nodes
, e
->dest
->cuid
)
2089 && ((SCHED_TIME (e
->dest
->cuid
) + (e
->distance
* ii
)) ==
2090 last_cycle_in_window
))
2093 fprintf (dump_file
, "%d ", e
->dest
->cuid
);
2095 bitmap_set_bit (must_follow
, e
->dest
->cuid
);
2099 fprintf (dump_file
, "\n");
2102 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
2103 parameters to decide if that's possible:
2104 PS - The partial schedule.
2105 U - The serial number of U_NODE.
2106 NUM_SPLITS - The number of row splits made so far.
2107 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
2108 the first row of the scheduling window)
2109 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
2110 last row of the scheduling window) */
2113 try_scheduling_node_in_cycle (partial_schedule_ptr ps
,
2114 int u
, int cycle
, sbitmap sched_nodes
,
2115 int *num_splits
, sbitmap must_precede
,
2116 sbitmap must_follow
)
2121 verify_partial_schedule (ps
, sched_nodes
);
2122 psi
= ps_add_node_check_conflicts (ps
, u
, cycle
, must_precede
, must_follow
);
2125 SCHED_TIME (u
) = cycle
;
2126 bitmap_set_bit (sched_nodes
, u
);
2130 fprintf (dump_file
, "Scheduled w/o split in %d\n", cycle
);
2137 /* This function implements the scheduling algorithm for SMS according to the
2139 static partial_schedule_ptr
2140 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
)
2143 int i
, c
, success
, num_splits
= 0;
2144 int flush_and_start_over
= true;
2145 int num_nodes
= g
->num_nodes
;
2146 int start
, end
, step
; /* Place together into one struct? */
2147 sbitmap sched_nodes
= sbitmap_alloc (num_nodes
);
2148 sbitmap must_precede
= sbitmap_alloc (num_nodes
);
2149 sbitmap must_follow
= sbitmap_alloc (num_nodes
);
2150 sbitmap tobe_scheduled
= sbitmap_alloc (num_nodes
);
2152 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
, DFA_HISTORY
);
2154 bitmap_ones (tobe_scheduled
);
2155 bitmap_clear (sched_nodes
);
2157 while (flush_and_start_over
&& (ii
< maxii
))
2161 fprintf (dump_file
, "Starting with ii=%d\n", ii
);
2162 flush_and_start_over
= false;
2163 bitmap_clear (sched_nodes
);
2165 for (i
= 0; i
< num_nodes
; i
++)
2167 int u
= nodes_order
[i
];
2168 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
2169 rtx insn
= u_node
->insn
;
2171 if (!NONDEBUG_INSN_P (insn
))
2173 bitmap_clear_bit (tobe_scheduled
, u
);
2177 if (bitmap_bit_p (sched_nodes
, u
))
2180 /* Try to get non-empty scheduling window. */
2182 if (get_sched_window (ps
, u_node
, sched_nodes
, ii
, &start
,
2186 fprintf (dump_file
, "\nTrying to schedule node %d "
2187 "INSN = %d in (%d .. %d) step %d\n", u
, (INSN_UID
2188 (g
->nodes
[u
].insn
)), start
, end
, step
);
2190 gcc_assert ((step
> 0 && start
< end
)
2191 || (step
< 0 && start
> end
));
2193 calculate_must_precede_follow (u_node
, start
, end
, step
, ii
,
2194 sched_nodes
, must_precede
,
2197 for (c
= start
; c
!= end
; c
+= step
)
2199 sbitmap tmp_precede
, tmp_follow
;
2201 set_must_precede_follow (&tmp_follow
, must_follow
,
2202 &tmp_precede
, must_precede
,
2203 c
, start
, end
, step
);
2205 try_scheduling_node_in_cycle (ps
, u
, c
,
2207 &num_splits
, tmp_precede
,
2213 verify_partial_schedule (ps
, sched_nodes
);
2222 if (num_splits
>= MAX_SPLIT_NUM
)
2225 flush_and_start_over
= true;
2226 verify_partial_schedule (ps
, sched_nodes
);
2227 reset_partial_schedule (ps
, ii
);
2228 verify_partial_schedule (ps
, sched_nodes
);
2233 /* The scheduling window is exclusive of 'end'
2234 whereas compute_split_window() expects an inclusive,
2237 split_row
= compute_split_row (sched_nodes
, start
, end
- 1,
2240 split_row
= compute_split_row (sched_nodes
, end
+ 1, start
,
2243 ps_insert_empty_row (ps
, split_row
, sched_nodes
);
2244 i
--; /* Go back and retry node i. */
2247 fprintf (dump_file
, "num_splits=%d\n", num_splits
);
2250 /* ??? If (success), check register pressure estimates. */
2251 } /* Continue with next node. */
2252 } /* While flush_and_start_over. */
2255 free_partial_schedule (ps
);
2259 gcc_assert (bitmap_equal_p (tobe_scheduled
, sched_nodes
));
2261 sbitmap_free (sched_nodes
);
2262 sbitmap_free (must_precede
);
2263 sbitmap_free (must_follow
);
2264 sbitmap_free (tobe_scheduled
);
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 sbitmap tmp
= sbitmap_alloc (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");
2499 /* Order the nodes of G for scheduling and pass the result in
2500 NODE_ORDER. Also set aux.count of each node to ASAP.
2501 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2503 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
, int *pmax_asap
)
2507 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
2509 nopa nops
= calculate_order_params (g
, mii
, pmax_asap
);
2512 print_sccs (dump_file
, sccs
, g
);
2514 order_nodes_of_sccs (sccs
, node_order
);
2516 if (sccs
->num_sccs
> 0)
2517 /* First SCC has the largest recurrence_length. */
2518 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
2520 /* Save ASAP before destroying node_order_params. */
2521 for (i
= 0; i
< g
->num_nodes
; i
++)
2523 ddg_node_ptr v
= &g
->nodes
[i
];
2524 v
->aux
.count
= ASAP (v
);
2528 free_ddg_all_sccs (sccs
);
2529 check_nodes_order (node_order
, g
->num_nodes
);
2535 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
2538 ddg_ptr g
= all_sccs
->ddg
;
2539 int num_nodes
= g
->num_nodes
;
2540 sbitmap prev_sccs
= sbitmap_alloc (num_nodes
);
2541 sbitmap on_path
= sbitmap_alloc (num_nodes
);
2542 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2543 sbitmap ones
= sbitmap_alloc (num_nodes
);
2545 bitmap_clear (prev_sccs
);
2548 /* Perform the node ordering starting from the SCC with the highest recMII.
2549 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2550 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
2552 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
2554 /* Add nodes on paths from previous SCCs to the current SCC. */
2555 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
2556 bitmap_ior (tmp
, scc
->nodes
, on_path
);
2558 /* Add nodes on paths from the current SCC to previous SCCs. */
2559 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
2560 bitmap_ior (tmp
, tmp
, on_path
);
2562 /* Remove nodes of previous SCCs from current extended SCC. */
2563 bitmap_and_compl (tmp
, tmp
, prev_sccs
);
2565 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2566 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2569 /* Handle the remaining nodes that do not belong to any scc. Each call
2570 to order_nodes_in_scc handles a single connected component. */
2571 while (pos
< g
->num_nodes
)
2573 bitmap_and_compl (tmp
, ones
, prev_sccs
);
2574 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2576 sbitmap_free (prev_sccs
);
2577 sbitmap_free (on_path
);
2579 sbitmap_free (ones
);
2582 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2583 static struct node_order_params
*
2584 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
, int *pmax_asap
)
2588 int num_nodes
= g
->num_nodes
;
2590 /* Allocate a place to hold ordering params for each node in the DDG. */
2591 nopa node_order_params_arr
;
2593 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2594 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
2595 sizeof (struct node_order_params
));
2597 /* Set the aux pointer of each node to point to its order_params structure. */
2598 for (u
= 0; u
< num_nodes
; u
++)
2599 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
2601 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2602 calculate ASAP, ALAP, mobility, distance, and height for each node
2603 in the dependence (direct acyclic) graph. */
2605 /* We assume that the nodes in the array are in topological order. */
2608 for (u
= 0; u
< num_nodes
; u
++)
2610 ddg_node_ptr u_node
= &g
->nodes
[u
];
2613 for (e
= u_node
->in
; e
; e
= e
->next_in
)
2614 if (e
->distance
== 0)
2615 ASAP (u_node
) = MAX (ASAP (u_node
),
2616 ASAP (e
->src
) + e
->latency
);
2617 max_asap
= MAX (max_asap
, ASAP (u_node
));
2620 for (u
= num_nodes
- 1; u
> -1; u
--)
2622 ddg_node_ptr u_node
= &g
->nodes
[u
];
2624 ALAP (u_node
) = max_asap
;
2625 HEIGHT (u_node
) = 0;
2626 for (e
= u_node
->out
; e
; e
= e
->next_out
)
2627 if (e
->distance
== 0)
2629 ALAP (u_node
) = MIN (ALAP (u_node
),
2630 ALAP (e
->dest
) - e
->latency
);
2631 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
2632 HEIGHT (e
->dest
) + e
->latency
);
2637 fprintf (dump_file
, "\nOrder params\n");
2638 for (u
= 0; u
< num_nodes
; u
++)
2640 ddg_node_ptr u_node
= &g
->nodes
[u
];
2642 fprintf (dump_file
, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u
,
2643 ASAP (u_node
), ALAP (u_node
), HEIGHT (u_node
));
2647 *pmax_asap
= max_asap
;
2648 return node_order_params_arr
;
2652 find_max_asap (ddg_ptr g
, sbitmap nodes
)
2657 sbitmap_iterator sbi
;
2659 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2661 ddg_node_ptr u_node
= &g
->nodes
[u
];
2663 if (max_asap
< ASAP (u_node
))
2665 max_asap
= ASAP (u_node
);
2673 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
2677 int min_mob
= INT_MAX
;
2679 sbitmap_iterator sbi
;
2681 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2683 ddg_node_ptr u_node
= &g
->nodes
[u
];
2685 if (max_hv
< HEIGHT (u_node
))
2687 max_hv
= HEIGHT (u_node
);
2688 min_mob
= MOB (u_node
);
2691 else if ((max_hv
== HEIGHT (u_node
))
2692 && (min_mob
> MOB (u_node
)))
2694 min_mob
= MOB (u_node
);
2702 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
2706 int min_mob
= INT_MAX
;
2708 sbitmap_iterator sbi
;
2710 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2712 ddg_node_ptr u_node
= &g
->nodes
[u
];
2714 if (max_dv
< DEPTH (u_node
))
2716 max_dv
= DEPTH (u_node
);
2717 min_mob
= MOB (u_node
);
2720 else if ((max_dv
== DEPTH (u_node
))
2721 && (min_mob
> MOB (u_node
)))
2723 min_mob
= MOB (u_node
);
2730 /* Places the nodes of SCC into the NODE_ORDER array starting
2731 at position POS, according to the SMS ordering algorithm.
2732 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2733 the NODE_ORDER array, starting from position zero. */
2735 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
2736 int * node_order
, int pos
)
2738 enum sms_direction dir
;
2739 int num_nodes
= g
->num_nodes
;
2740 sbitmap workset
= sbitmap_alloc (num_nodes
);
2741 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2742 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
2743 sbitmap predecessors
= sbitmap_alloc (num_nodes
);
2744 sbitmap successors
= sbitmap_alloc (num_nodes
);
2746 bitmap_clear (predecessors
);
2747 find_predecessors (predecessors
, g
, nodes_ordered
);
2749 bitmap_clear (successors
);
2750 find_successors (successors
, g
, nodes_ordered
);
2753 if (bitmap_and (tmp
, predecessors
, scc
))
2755 bitmap_copy (workset
, tmp
);
2758 else if (bitmap_and (tmp
, successors
, scc
))
2760 bitmap_copy (workset
, tmp
);
2767 bitmap_clear (workset
);
2768 if ((u
= find_max_asap (g
, scc
)) >= 0)
2769 bitmap_set_bit (workset
, u
);
2773 bitmap_clear (zero_bitmap
);
2774 while (!bitmap_equal_p (workset
, zero_bitmap
))
2777 ddg_node_ptr v_node
;
2778 sbitmap v_node_preds
;
2779 sbitmap v_node_succs
;
2783 while (!bitmap_equal_p (workset
, zero_bitmap
))
2785 v
= find_max_hv_min_mob (g
, workset
);
2786 v_node
= &g
->nodes
[v
];
2787 node_order
[pos
++] = v
;
2788 v_node_succs
= NODE_SUCCESSORS (v_node
);
2789 bitmap_and (tmp
, v_node_succs
, scc
);
2791 /* Don't consider the already ordered successors again. */
2792 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2793 bitmap_ior (workset
, workset
, tmp
);
2794 bitmap_clear_bit (workset
, v
);
2795 bitmap_set_bit (nodes_ordered
, v
);
2798 bitmap_clear (predecessors
);
2799 find_predecessors (predecessors
, g
, nodes_ordered
);
2800 bitmap_and (workset
, predecessors
, scc
);
2804 while (!bitmap_equal_p (workset
, zero_bitmap
))
2806 v
= find_max_dv_min_mob (g
, workset
);
2807 v_node
= &g
->nodes
[v
];
2808 node_order
[pos
++] = v
;
2809 v_node_preds
= NODE_PREDECESSORS (v_node
);
2810 bitmap_and (tmp
, v_node_preds
, scc
);
2812 /* Don't consider the already ordered predecessors again. */
2813 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2814 bitmap_ior (workset
, workset
, tmp
);
2815 bitmap_clear_bit (workset
, v
);
2816 bitmap_set_bit (nodes_ordered
, v
);
2819 bitmap_clear (successors
);
2820 find_successors (successors
, g
, nodes_ordered
);
2821 bitmap_and (workset
, successors
, scc
);
2825 sbitmap_free (workset
);
2826 sbitmap_free (zero_bitmap
);
2827 sbitmap_free (predecessors
);
2828 sbitmap_free (successors
);
2833 /* This page contains functions for manipulating partial-schedules during
2834 modulo scheduling. */
2836 /* Create a partial schedule and allocate a memory to hold II rows. */
2838 static partial_schedule_ptr
2839 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2841 partial_schedule_ptr ps
= XNEW (struct partial_schedule
);
2842 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2843 ps
->rows_length
= (int *) xcalloc (ii
, sizeof (int));
2844 ps
->reg_moves
.create (0);
2846 ps
->history
= history
;
2847 ps
->min_cycle
= INT_MAX
;
2848 ps
->max_cycle
= INT_MIN
;
2854 /* Free the PS_INSNs in rows array of the given partial schedule.
2855 ??? Consider caching the PS_INSN's. */
2857 free_ps_insns (partial_schedule_ptr ps
)
2861 for (i
= 0; i
< ps
->ii
; i
++)
2865 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2868 ps
->rows
[i
] = ps_insn
;
2874 /* Free all the memory allocated to the partial schedule. */
2877 free_partial_schedule (partial_schedule_ptr ps
)
2879 ps_reg_move_info
*move
;
2885 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
2886 sbitmap_free (move
->uses
);
2887 ps
->reg_moves
.release ();
2891 free (ps
->rows_length
);
2895 /* Clear the rows array with its PS_INSNs, and create a new one with
2899 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2904 if (new_ii
== ps
->ii
)
2906 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2907 * sizeof (ps_insn_ptr
));
2908 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2909 ps
->rows_length
= (int *) xrealloc (ps
->rows_length
, new_ii
* sizeof (int));
2910 memset (ps
->rows_length
, 0, new_ii
* sizeof (int));
2912 ps
->min_cycle
= INT_MAX
;
2913 ps
->max_cycle
= INT_MIN
;
2916 /* Prints the partial schedule as an ii rows array, for each rows
2917 print the ids of the insns in it. */
2919 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2923 for (i
= 0; i
< ps
->ii
; i
++)
2925 ps_insn_ptr ps_i
= ps
->rows
[i
];
2927 fprintf (dump
, "\n[ROW %d ]: ", i
);
2930 rtx insn
= ps_rtl_insn (ps
, ps_i
->id
);
2933 fprintf (dump
, "%d (branch), ", INSN_UID (insn
));
2935 fprintf (dump
, "%d, ", INSN_UID (insn
));
2937 ps_i
= ps_i
->next_in_row
;
2942 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2944 create_ps_insn (int id
, int cycle
)
2946 ps_insn_ptr ps_i
= XNEW (struct ps_insn
);
2949 ps_i
->next_in_row
= NULL
;
2950 ps_i
->prev_in_row
= NULL
;
2951 ps_i
->cycle
= cycle
;
2957 /* Removes the given PS_INSN from the partial schedule. */
2959 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2963 gcc_assert (ps
&& ps_i
);
2965 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2966 if (! ps_i
->prev_in_row
)
2968 gcc_assert (ps_i
== ps
->rows
[row
]);
2969 ps
->rows
[row
] = ps_i
->next_in_row
;
2971 ps
->rows
[row
]->prev_in_row
= NULL
;
2975 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
2976 if (ps_i
->next_in_row
)
2977 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
2980 ps
->rows_length
[row
] -= 1;
2985 /* Unlike what literature describes for modulo scheduling (which focuses
2986 on VLIW machines) the order of the instructions inside a cycle is
2987 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2988 where the current instruction should go relative to the already
2989 scheduled instructions in the given cycle. Go over these
2990 instructions and find the first possible column to put it in. */
2992 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2993 sbitmap must_precede
, sbitmap must_follow
)
2995 ps_insn_ptr next_ps_i
;
2996 ps_insn_ptr first_must_follow
= NULL
;
2997 ps_insn_ptr last_must_precede
= NULL
;
2998 ps_insn_ptr last_in_row
= NULL
;
3004 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3006 /* Find the first must follow and the last must precede
3007 and insert the node immediately after the must precede
3008 but make sure that it there is no must follow after it. */
3009 for (next_ps_i
= ps
->rows
[row
];
3011 next_ps_i
= next_ps_i
->next_in_row
)
3014 && bitmap_bit_p (must_follow
, next_ps_i
->id
)
3015 && ! first_must_follow
)
3016 first_must_follow
= next_ps_i
;
3017 if (must_precede
&& bitmap_bit_p (must_precede
, next_ps_i
->id
))
3019 /* If we have already met a node that must follow, then
3020 there is no possible column. */
3021 if (first_must_follow
)
3024 last_must_precede
= next_ps_i
;
3026 /* The closing branch must be the last in the row. */
3028 && bitmap_bit_p (must_precede
, next_ps_i
->id
)
3029 && JUMP_P (ps_rtl_insn (ps
, next_ps_i
->id
)))
3032 last_in_row
= next_ps_i
;
3035 /* The closing branch is scheduled as well. Make sure there is no
3036 dependent instruction after it as the branch should be the last
3037 instruction in the row. */
3038 if (JUMP_P (ps_rtl_insn (ps
, ps_i
->id
)))
3040 if (first_must_follow
)
3044 /* Make the branch the last in the row. New instructions
3045 will be inserted at the beginning of the row or after the
3046 last must_precede instruction thus the branch is guaranteed
3047 to remain the last instruction in the row. */
3048 last_in_row
->next_in_row
= ps_i
;
3049 ps_i
->prev_in_row
= last_in_row
;
3050 ps_i
->next_in_row
= NULL
;
3053 ps
->rows
[row
] = ps_i
;
3057 /* Now insert the node after INSERT_AFTER_PSI. */
3059 if (! last_must_precede
)
3061 ps_i
->next_in_row
= ps
->rows
[row
];
3062 ps_i
->prev_in_row
= NULL
;
3063 if (ps_i
->next_in_row
)
3064 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3065 ps
->rows
[row
] = ps_i
;
3069 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
3070 last_must_precede
->next_in_row
= ps_i
;
3071 ps_i
->prev_in_row
= last_must_precede
;
3072 if (ps_i
->next_in_row
)
3073 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3079 /* Advances the PS_INSN one column in its current row; returns false
3080 in failure and true in success. Bit N is set in MUST_FOLLOW if
3081 the node with cuid N must be come after the node pointed to by
3082 PS_I when scheduled in the same cycle. */
3084 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
3085 sbitmap must_follow
)
3087 ps_insn_ptr prev
, next
;
3093 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3095 if (! ps_i
->next_in_row
)
3098 /* Check if next_in_row is dependent on ps_i, both having same sched
3099 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
3100 if (must_follow
&& bitmap_bit_p (must_follow
, ps_i
->next_in_row
->id
))
3103 /* Advance PS_I over its next_in_row in the doubly linked list. */
3104 prev
= ps_i
->prev_in_row
;
3105 next
= ps_i
->next_in_row
;
3107 if (ps_i
== ps
->rows
[row
])
3108 ps
->rows
[row
] = next
;
3110 ps_i
->next_in_row
= next
->next_in_row
;
3112 if (next
->next_in_row
)
3113 next
->next_in_row
->prev_in_row
= ps_i
;
3115 next
->next_in_row
= ps_i
;
3116 ps_i
->prev_in_row
= next
;
3118 next
->prev_in_row
= prev
;
3120 prev
->next_in_row
= next
;
3125 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
3126 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
3127 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
3128 before/after (respectively) the node pointed to by PS_I when scheduled
3129 in the same cycle. */
3131 add_node_to_ps (partial_schedule_ptr ps
, int id
, int cycle
,
3132 sbitmap must_precede
, sbitmap must_follow
)
3135 int row
= SMODULO (cycle
, ps
->ii
);
3137 if (ps
->rows_length
[row
] >= issue_rate
)
3140 ps_i
= create_ps_insn (id
, cycle
);
3142 /* Finds and inserts PS_I according to MUST_FOLLOW and
3144 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
3150 ps
->rows_length
[row
] += 1;
3154 /* Advance time one cycle. Assumes DFA is being used. */
3156 advance_one_cycle (void)
3158 if (targetm
.sched
.dfa_pre_cycle_insn
)
3159 state_transition (curr_state
,
3160 targetm
.sched
.dfa_pre_cycle_insn ());
3162 state_transition (curr_state
, NULL
);
3164 if (targetm
.sched
.dfa_post_cycle_insn
)
3165 state_transition (curr_state
,
3166 targetm
.sched
.dfa_post_cycle_insn ());
3171 /* Checks if PS has resource conflicts according to DFA, starting from
3172 FROM cycle to TO cycle; returns true if there are conflicts and false
3173 if there are no conflicts. Assumes DFA is being used. */
3175 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
3179 state_reset (curr_state
);
3181 for (cycle
= from
; cycle
<= to
; cycle
++)
3183 ps_insn_ptr crr_insn
;
3184 /* Holds the remaining issue slots in the current row. */
3185 int can_issue_more
= issue_rate
;
3187 /* Walk through the DFA for the current row. */
3188 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
3190 crr_insn
= crr_insn
->next_in_row
)
3192 rtx insn
= ps_rtl_insn (ps
, crr_insn
->id
);
3194 if (!NONDEBUG_INSN_P (insn
))
3197 /* Check if there is room for the current insn. */
3198 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
3201 /* Update the DFA state and return with failure if the DFA found
3202 resource conflicts. */
3203 if (state_transition (curr_state
, insn
) >= 0)
3206 if (targetm
.sched
.variable_issue
)
3208 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
3209 insn
, can_issue_more
);
3210 /* A naked CLOBBER or USE generates no instruction, so don't
3211 let them consume issue slots. */
3212 else if (GET_CODE (PATTERN (insn
)) != USE
3213 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3217 /* Advance the DFA to the next cycle. */
3218 advance_one_cycle ();
3223 /* Checks if the given node causes resource conflicts when added to PS at
3224 cycle C. If not the node is added to PS and returned; otherwise zero
3225 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
3226 cuid N must be come before/after (respectively) the node pointed to by
3227 PS_I when scheduled in the same cycle. */
3229 ps_add_node_check_conflicts (partial_schedule_ptr ps
, int n
,
3230 int c
, sbitmap must_precede
,
3231 sbitmap must_follow
)
3233 int has_conflicts
= 0;
3236 /* First add the node to the PS, if this succeeds check for
3237 conflicts, trying different issue slots in the same row. */
3238 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
3239 return NULL
; /* Failed to insert the node at the given cycle. */
3241 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3243 && ps_has_conflicts (ps
,
3247 /* Try different issue slots to find one that the given node can be
3248 scheduled in without conflicts. */
3249 while (has_conflicts
)
3251 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
3253 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3255 && ps_has_conflicts (ps
,
3262 remove_node_from_ps (ps
, ps_i
);
3266 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
3267 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
3271 /* Calculate the stage count of the partial schedule PS. The calculation
3272 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3274 calculate_stage_count (partial_schedule_ptr ps
, int rotation_amount
)
3276 int new_min_cycle
= PS_MIN_CYCLE (ps
) - rotation_amount
;
3277 int new_max_cycle
= PS_MAX_CYCLE (ps
) - rotation_amount
;
3278 int stage_count
= CALC_STAGE_COUNT (-1, new_min_cycle
, ps
->ii
);
3280 /* The calculation of stage count is done adding the number of stages
3281 before cycle zero and after cycle zero. */
3282 stage_count
+= CALC_STAGE_COUNT (new_max_cycle
, 0, ps
->ii
);
3287 /* Rotate the rows of PS such that insns scheduled at time
3288 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3290 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
3292 int i
, row
, backward_rotates
;
3293 int last_row
= ps
->ii
- 1;
3295 if (start_cycle
== 0)
3298 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
3300 /* Revisit later and optimize this into a single loop. */
3301 for (i
= 0; i
< backward_rotates
; i
++)
3303 ps_insn_ptr first_row
= ps
->rows
[0];
3304 int first_row_length
= ps
->rows_length
[0];
3306 for (row
= 0; row
< last_row
; row
++)
3308 ps
->rows
[row
] = ps
->rows
[row
+ 1];
3309 ps
->rows_length
[row
] = ps
->rows_length
[row
+ 1];
3312 ps
->rows
[last_row
] = first_row
;
3313 ps
->rows_length
[last_row
] = first_row_length
;
3316 ps
->max_cycle
-= start_cycle
;
3317 ps
->min_cycle
-= start_cycle
;
3320 #endif /* INSN_SCHEDULING */
3323 gate_handle_sms (void)
3325 return (optimize
> 0 && flag_modulo_sched
);
3329 /* Run instruction scheduler. */
3330 /* Perform SMS module scheduling. */
3332 rest_of_handle_sms (void)
3334 #ifdef INSN_SCHEDULING
3337 /* Collect loop information to be used in SMS. */
3338 cfg_layout_initialize (0);
3341 /* Update the life information, because we add pseudos. */
3342 max_regno
= max_reg_num ();
3344 /* Finalize layout changes. */
3346 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
3347 bb
->aux
= bb
->next_bb
;
3348 free_dominance_info (CDI_DOMINATORS
);
3349 cfg_layout_finalize ();
3350 #endif /* INSN_SCHEDULING */
3354 struct rtl_opt_pass pass_sms
=
3359 OPTGROUP_NONE
, /* optinfo_flags */
3360 gate_handle_sms
, /* gate */
3361 rest_of_handle_sms
, /* execute */
3364 0, /* static_pass_number */
3366 0, /* properties_required */
3367 0, /* properties_provided */
3368 0, /* properties_destroyed */
3369 0, /* todo_flags_start */
3372 | TODO_verify_rtl_sharing
3373 | TODO_ggc_collect
/* todo_flags_finish */