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 "dominance.h"
47 #include "basic-block.h"
48 #include "sched-int.h"
57 #include "tree-pass.h"
59 #include "loop-unroll.h"
61 #ifdef INSN_SCHEDULING
63 /* This file contains the implementation of the Swing Modulo Scheduler,
64 described in the following references:
65 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
66 Lifetime--sensitive modulo scheduling in a production environment.
67 IEEE Trans. on Comps., 50(3), March 2001
68 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
69 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
70 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
72 The basic structure is:
73 1. Build a data-dependence graph (DDG) for each loop.
74 2. Use the DDG to order the insns of a loop (not in topological order
75 necessarily, but rather) trying to place each insn after all its
76 predecessors _or_ after all its successors.
77 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
78 4. Use the ordering to perform list-scheduling of the loop:
79 1. Set II = MII. We will try to schedule the loop within II cycles.
80 2. Try to schedule the insns one by one according to the ordering.
81 For each insn compute an interval of cycles by considering already-
82 scheduled preds and succs (and associated latencies); try to place
83 the insn in the cycles of this window checking for potential
84 resource conflicts (using the DFA interface).
85 Note: this is different from the cycle-scheduling of schedule_insns;
86 here the insns are not scheduled monotonically top-down (nor bottom-
88 3. If failed in scheduling all insns - bump II++ and try again, unless
89 II reaches an upper bound MaxII, in which case report failure.
90 5. If we succeeded in scheduling the loop within II cycles, we now
91 generate prolog and epilog, decrease the counter of the loop, and
92 perform modulo variable expansion for live ranges that span more than
93 II cycles (i.e. use register copies to prevent a def from overwriting
94 itself before reaching the use).
96 SMS works with countable loops (1) whose control part can be easily
97 decoupled from the rest of the loop and (2) whose loop count can
98 be easily adjusted. This is because we peel a constant number of
99 iterations into a prologue and epilogue for which we want to avoid
100 emitting the control part, and a kernel which is to iterate that
101 constant number of iterations less than the original loop. So the
102 control part should be a set of insns clearly identified and having
103 its own iv, not otherwise used in the loop (at-least for now), which
104 initializes a register before the loop to the number of iterations.
105 Currently SMS relies on the do-loop pattern to recognize such loops,
106 where (1) the control part comprises of all insns defining and/or
107 using a certain 'count' register and (2) the loop count can be
108 adjusted by modifying this register prior to the loop.
109 TODO: Rely on cfgloop analysis instead. */
111 /* This page defines partial-schedule structures and functions for
112 modulo scheduling. */
114 typedef struct partial_schedule
*partial_schedule_ptr
;
115 typedef struct ps_insn
*ps_insn_ptr
;
117 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
118 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
120 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
121 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
123 /* Perform signed modulo, always returning a non-negative value. */
124 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
126 /* The number of different iterations the nodes in ps span, assuming
127 the stage boundaries are placed efficiently. */
128 #define CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \
130 /* The stage count of ps. */
131 #define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count)
133 /* A single instruction in the partial schedule. */
136 /* Identifies the instruction to be scheduled. Values smaller than
137 the ddg's num_nodes refer directly to ddg nodes. A value of
138 X - num_nodes refers to register move X. */
141 /* The (absolute) cycle in which the PS instruction is scheduled.
142 Same as SCHED_TIME (node). */
145 /* The next/prev PS_INSN in the same row. */
146 ps_insn_ptr next_in_row
,
151 /* Information about a register move that has been added to a partial
153 struct ps_reg_move_info
155 /* The source of the move is defined by the ps_insn with id DEF.
156 The destination is used by the ps_insns with the ids in USES. */
160 /* The original form of USES' instructions used OLD_REG, but they
161 should now use NEW_REG. */
165 /* The number of consecutive stages that the move occupies. */
166 int num_consecutive_stages
;
168 /* An instruction that sets NEW_REG to the correct value. The first
169 move associated with DEF will have an rhs of OLD_REG; later moves
170 use the result of the previous move. */
174 typedef struct ps_reg_move_info ps_reg_move_info
;
176 /* Holds the partial schedule as an array of II rows. Each entry of the
177 array points to a linked list of PS_INSNs, which represents the
178 instructions that are scheduled for that row. */
179 struct partial_schedule
181 int ii
; /* Number of rows in the partial schedule. */
182 int history
; /* Threshold for conflict checking using DFA. */
184 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
187 /* All the moves added for this partial schedule. Index X has
188 a ps_insn id of X + g->num_nodes. */
189 vec
<ps_reg_move_info
> reg_moves
;
191 /* rows_length[i] holds the number of instructions in the row.
192 It is used only (as an optimization) to back off quickly from
193 trying to schedule a node in a full row; that is, to avoid running
194 through futile DFA state transitions. */
197 /* The earliest absolute cycle of an insn in the partial schedule. */
200 /* The latest absolute cycle of an insn in the partial schedule. */
203 ddg_ptr g
; /* The DDG of the insns in the partial schedule. */
205 int stage_count
; /* The stage count of the partial schedule. */
209 static partial_schedule_ptr
create_partial_schedule (int ii
, ddg_ptr
, int history
);
210 static void free_partial_schedule (partial_schedule_ptr
);
211 static void reset_partial_schedule (partial_schedule_ptr
, int new_ii
);
212 void print_partial_schedule (partial_schedule_ptr
, FILE *);
213 static void verify_partial_schedule (partial_schedule_ptr
, sbitmap
);
214 static ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr
,
215 int, int, sbitmap
, sbitmap
);
216 static void rotate_partial_schedule (partial_schedule_ptr
, int);
217 void set_row_column_for_ps (partial_schedule_ptr
);
218 static void ps_insert_empty_row (partial_schedule_ptr
, int, sbitmap
);
219 static int compute_split_row (sbitmap
, int, int, int, ddg_node_ptr
);
222 /* This page defines constants and structures for the modulo scheduling
225 static int sms_order_nodes (ddg_ptr
, int, int *, int *);
226 static void set_node_sched_params (ddg_ptr
);
227 static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr
, int, int, int *);
228 static void permute_partial_schedule (partial_schedule_ptr
, rtx_insn
*);
229 static void generate_prolog_epilog (partial_schedule_ptr
, struct loop
*,
231 static int calculate_stage_count (partial_schedule_ptr
, int);
232 static void calculate_must_precede_follow (ddg_node_ptr
, int, int,
233 int, int, sbitmap
, sbitmap
, sbitmap
);
234 static int get_sched_window (partial_schedule_ptr
, ddg_node_ptr
,
235 sbitmap
, int, int *, int *, int *);
236 static bool try_scheduling_node_in_cycle (partial_schedule_ptr
, int, int,
237 sbitmap
, int *, sbitmap
, sbitmap
);
238 static void remove_node_from_ps (partial_schedule_ptr
, ps_insn_ptr
);
240 #define NODE_ASAP(node) ((node)->aux.count)
242 #define SCHED_PARAMS(x) (&node_sched_param_vec[x])
243 #define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
244 #define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
245 #define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
246 #define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
248 /* The scheduling parameters held for each node. */
249 typedef struct node_sched_params
251 int time
; /* The absolute scheduling cycle. */
253 int row
; /* Holds time % ii. */
254 int stage
; /* Holds time / ii. */
256 /* The column of a node inside the ps. If nodes u, v are on the same row,
257 u will precede v if column (u) < column (v). */
259 } *node_sched_params_ptr
;
261 typedef struct node_sched_params node_sched_params
;
263 /* The following three functions are copied from the current scheduler
264 code in order to use sched_analyze() for computing the dependencies.
265 They are used when initializing the sched_info structure. */
267 sms_print_insn (const rtx_insn
*insn
, int aligned ATTRIBUTE_UNUSED
)
271 sprintf (tmp
, "i%4d", INSN_UID (insn
));
276 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
277 regset used ATTRIBUTE_UNUSED
)
281 static struct common_sched_info_def sms_common_sched_info
;
283 static struct sched_deps_info_def sms_sched_deps_info
=
285 compute_jump_reg_dependencies
,
286 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
291 static struct haifa_sched_info sms_sched_info
=
300 NULL
, /* insn_finishes_block_p */
305 NULL
, NULL
, NULL
, NULL
,
310 /* Partial schedule instruction ID in PS is a register move. Return
311 information about it. */
312 static struct ps_reg_move_info
*
313 ps_reg_move (partial_schedule_ptr ps
, int id
)
315 gcc_checking_assert (id
>= ps
->g
->num_nodes
);
316 return &ps
->reg_moves
[id
- ps
->g
->num_nodes
];
319 /* Return the rtl instruction that is being scheduled by partial schedule
320 instruction ID, which belongs to schedule PS. */
322 ps_rtl_insn (partial_schedule_ptr ps
, int id
)
324 if (id
< ps
->g
->num_nodes
)
325 return ps
->g
->nodes
[id
].insn
;
327 return ps_reg_move (ps
, id
)->insn
;
330 /* Partial schedule instruction ID, which belongs to PS, occurred in
331 the original (unscheduled) loop. Return the first instruction
332 in the loop that was associated with ps_rtl_insn (PS, ID).
333 If the instruction had some notes before it, this is the first
336 ps_first_note (partial_schedule_ptr ps
, int id
)
338 gcc_assert (id
< ps
->g
->num_nodes
);
339 return ps
->g
->nodes
[id
].first_note
;
342 /* Return the number of consecutive stages that are occupied by
343 partial schedule instruction ID in PS. */
345 ps_num_consecutive_stages (partial_schedule_ptr ps
, int id
)
347 if (id
< ps
->g
->num_nodes
)
350 return ps_reg_move (ps
, id
)->num_consecutive_stages
;
353 /* Given HEAD and TAIL which are the first and last insns in a loop;
354 return the register which controls the loop. Return zero if it has
355 more than one occurrence in the loop besides the control part or the
356 do-loop pattern is not of the form we expect. */
358 doloop_register_get (rtx_insn
*head ATTRIBUTE_UNUSED
, rtx_insn
*tail ATTRIBUTE_UNUSED
)
360 #ifdef HAVE_doloop_end
362 rtx_insn
*insn
, *first_insn_not_to_check
;
367 /* TODO: Free SMS's dependence on doloop_condition_get. */
368 condition
= doloop_condition_get (tail
);
372 if (REG_P (XEXP (condition
, 0)))
373 reg
= XEXP (condition
, 0);
374 else if (GET_CODE (XEXP (condition
, 0)) == PLUS
375 && REG_P (XEXP (XEXP (condition
, 0), 0)))
376 reg
= XEXP (XEXP (condition
, 0), 0);
380 /* Check that the COUNT_REG has no other occurrences in the loop
381 until the decrement. We assume the control part consists of
382 either a single (parallel) branch-on-count or a (non-parallel)
383 branch immediately preceded by a single (decrement) insn. */
384 first_insn_not_to_check
= (GET_CODE (PATTERN (tail
)) == PARALLEL
? tail
385 : prev_nondebug_insn (tail
));
387 for (insn
= head
; insn
!= first_insn_not_to_check
; insn
= NEXT_INSN (insn
))
388 if (!DEBUG_INSN_P (insn
) && reg_mentioned_p (reg
, insn
))
392 fprintf (dump_file
, "SMS count_reg found ");
393 print_rtl_single (dump_file
, reg
);
394 fprintf (dump_file
, " outside control in insn:\n");
395 print_rtl_single (dump_file
, insn
);
407 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
408 that the number of iterations is a compile-time constant. If so,
409 return the rtx_insn that sets COUNT_REG to a constant, and set COUNT to
410 this constant. Otherwise return 0. */
412 const_iteration_count (rtx count_reg
, basic_block pre_header
,
416 rtx_insn
*head
, *tail
;
421 get_ebb_head_tail (pre_header
, pre_header
, &head
, &tail
);
423 for (insn
= tail
; insn
!= PREV_INSN (head
); insn
= PREV_INSN (insn
))
424 if (NONDEBUG_INSN_P (insn
) && single_set (insn
) &&
425 rtx_equal_p (count_reg
, SET_DEST (single_set (insn
))))
427 rtx pat
= single_set (insn
);
429 if (CONST_INT_P (SET_SRC (pat
)))
431 *count
= INTVAL (SET_SRC (pat
));
441 /* A very simple resource-based lower bound on the initiation interval.
442 ??? Improve the accuracy of this bound by considering the
443 utilization of various units. */
447 if (targetm
.sched
.sms_res_mii
)
448 return targetm
.sched
.sms_res_mii (g
);
450 return ((g
->num_nodes
- g
->num_debug
) / issue_rate
);
454 /* A vector that contains the sched data for each ps_insn. */
455 static vec
<node_sched_params
> node_sched_param_vec
;
457 /* Allocate sched_params for each node and initialize it. */
459 set_node_sched_params (ddg_ptr g
)
461 node_sched_param_vec
.truncate (0);
462 node_sched_param_vec
.safe_grow_cleared (g
->num_nodes
);
465 /* Make sure that node_sched_param_vec has an entry for every move in PS. */
467 extend_node_sched_params (partial_schedule_ptr ps
)
469 node_sched_param_vec
.safe_grow_cleared (ps
->g
->num_nodes
470 + ps
->reg_moves
.length ());
473 /* Update the sched_params (time, row and stage) for node U using the II,
474 the CYCLE of U and MIN_CYCLE.
475 We're not simply taking the following
476 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
477 because the stages may not be aligned on cycle 0. */
479 update_node_sched_params (int u
, int ii
, int cycle
, int min_cycle
)
481 int sc_until_cycle_zero
;
484 SCHED_TIME (u
) = cycle
;
485 SCHED_ROW (u
) = SMODULO (cycle
, ii
);
487 /* The calculation of stage count is done adding the number
488 of stages before cycle zero and after cycle zero. */
489 sc_until_cycle_zero
= CALC_STAGE_COUNT (-1, min_cycle
, ii
);
491 if (SCHED_TIME (u
) < 0)
493 stage
= CALC_STAGE_COUNT (-1, SCHED_TIME (u
), ii
);
494 SCHED_STAGE (u
) = sc_until_cycle_zero
- stage
;
498 stage
= CALC_STAGE_COUNT (SCHED_TIME (u
), 0, ii
);
499 SCHED_STAGE (u
) = sc_until_cycle_zero
+ stage
- 1;
504 print_node_sched_params (FILE *file
, int num_nodes
, partial_schedule_ptr ps
)
510 for (i
= 0; i
< num_nodes
; i
++)
512 node_sched_params_ptr nsp
= SCHED_PARAMS (i
);
514 fprintf (file
, "Node = %d; INSN = %d\n", i
,
515 INSN_UID (ps_rtl_insn (ps
, i
)));
516 fprintf (file
, " asap = %d:\n", NODE_ASAP (&ps
->g
->nodes
[i
]));
517 fprintf (file
, " time = %d:\n", nsp
->time
);
518 fprintf (file
, " stage = %d:\n", nsp
->stage
);
522 /* Set SCHED_COLUMN for each instruction in row ROW of PS. */
524 set_columns_for_row (partial_schedule_ptr ps
, int row
)
526 ps_insn_ptr cur_insn
;
530 for (cur_insn
= ps
->rows
[row
]; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
531 SCHED_COLUMN (cur_insn
->id
) = column
++;
534 /* Set SCHED_COLUMN for each instruction in PS. */
536 set_columns_for_ps (partial_schedule_ptr ps
)
540 for (row
= 0; row
< ps
->ii
; row
++)
541 set_columns_for_row (ps
, row
);
544 /* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
545 Its single predecessor has already been scheduled, as has its
546 ddg node successors. (The move may have also another move as its
547 successor, in which case that successor will be scheduled later.)
549 The move is part of a chain that satisfies register dependencies
550 between a producing ddg node and various consuming ddg nodes.
551 If some of these dependencies have a distance of 1 (meaning that
552 the use is upward-exposed) then DISTANCE1_USES is nonnull and
553 contains the set of uses with distance-1 dependencies.
554 DISTANCE1_USES is null otherwise.
556 MUST_FOLLOW is a scratch bitmap that is big enough to hold
557 all current ps_insn ids.
559 Return true on success. */
561 schedule_reg_move (partial_schedule_ptr ps
, int i_reg_move
,
562 sbitmap distance1_uses
, sbitmap must_follow
)
565 int this_time
, this_distance
, this_start
, this_end
, this_latency
;
566 int start
, end
, c
, ii
;
567 sbitmap_iterator sbi
;
568 ps_reg_move_info
*move
;
572 move
= ps_reg_move (ps
, i_reg_move
);
576 fprintf (dump_file
, "Scheduling register move INSN %d; ii = %d"
577 ", min cycle = %d\n\n", INSN_UID (move
->insn
), ii
,
579 print_rtl_single (dump_file
, move
->insn
);
580 fprintf (dump_file
, "\n%11s %11s %5s\n", "start", "end", "time");
581 fprintf (dump_file
, "=========== =========== =====\n");
587 /* For dependencies of distance 1 between a producer ddg node A
588 and consumer ddg node B, we have a chain of dependencies:
590 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
592 where Mi is the ith move. For dependencies of distance 0 between
593 a producer ddg node A and consumer ddg node C, we have a chain of
596 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
598 where Mi' occupies the same position as Mi but occurs a stage later.
599 We can only schedule each move once, so if we have both types of
600 chain, we model the second as:
602 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
604 First handle the dependencies between the previously-scheduled
605 predecessor and the move. */
606 this_insn
= ps_rtl_insn (ps
, move
->def
);
607 this_latency
= insn_latency (this_insn
, move
->insn
);
608 this_distance
= distance1_uses
&& move
->def
< ps
->g
->num_nodes
? 1 : 0;
609 this_time
= SCHED_TIME (move
->def
) - this_distance
* ii
;
610 this_start
= this_time
+ this_latency
;
611 this_end
= this_time
+ ii
;
613 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
614 this_start
, this_end
, SCHED_TIME (move
->def
),
615 INSN_UID (this_insn
), this_latency
, this_distance
,
616 INSN_UID (move
->insn
));
618 if (start
< this_start
)
623 /* Handle the dependencies between the move and previously-scheduled
625 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, u
, sbi
)
627 this_insn
= ps_rtl_insn (ps
, u
);
628 this_latency
= insn_latency (move
->insn
, this_insn
);
629 if (distance1_uses
&& !bitmap_bit_p (distance1_uses
, u
))
633 this_time
= SCHED_TIME (u
) + this_distance
* ii
;
634 this_start
= this_time
- ii
;
635 this_end
= this_time
- this_latency
;
637 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
638 this_start
, this_end
, SCHED_TIME (u
), INSN_UID (move
->insn
),
639 this_latency
, this_distance
, INSN_UID (this_insn
));
641 if (start
< this_start
)
649 fprintf (dump_file
, "----------- ----------- -----\n");
650 fprintf (dump_file
, "%11d %11d %5s %s\n", start
, end
, "", "(max, min)");
653 bitmap_clear (must_follow
);
654 bitmap_set_bit (must_follow
, move
->def
);
656 start
= MAX (start
, end
- (ii
- 1));
657 for (c
= end
; c
>= start
; c
--)
659 psi
= ps_add_node_check_conflicts (ps
, i_reg_move
, c
,
660 move
->uses
, must_follow
);
663 update_node_sched_params (i_reg_move
, ii
, c
, PS_MIN_CYCLE (ps
));
665 fprintf (dump_file
, "\nScheduled register move INSN %d at"
666 " time %d, row %d\n\n", INSN_UID (move
->insn
), c
,
667 SCHED_ROW (i_reg_move
));
673 fprintf (dump_file
, "\nNo available slot\n\n");
679 Breaking intra-loop register anti-dependences:
680 Each intra-loop register anti-dependence implies a cross-iteration true
681 dependence of distance 1. Therefore, we can remove such false dependencies
682 and figure out if the partial schedule broke them by checking if (for a
683 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
684 if so generate a register move. The number of such moves is equal to:
685 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
686 nreg_moves = ----------------------------------- + 1 - { dependence.
690 schedule_reg_moves (partial_schedule_ptr ps
)
696 for (i
= 0; i
< g
->num_nodes
; i
++)
698 ddg_node_ptr u
= &g
->nodes
[i
];
700 int nreg_moves
= 0, i_reg_move
;
701 rtx prev_reg
, old_reg
;
705 sbitmap distance1_uses
;
706 rtx set
= single_set (u
->insn
);
708 /* Skip instructions that do not set a register. */
709 if ((set
&& !REG_P (SET_DEST (set
))))
712 /* Compute the number of reg_moves needed for u, by looking at life
713 ranges started at u (excluding self-loops). */
714 distances
[0] = distances
[1] = false;
715 for (e
= u
->out
; e
; e
= e
->next_out
)
716 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
718 int nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
719 - SCHED_TIME (e
->src
->cuid
)) / ii
;
721 if (e
->distance
== 1)
722 nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
723 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
725 /* If dest precedes src in the schedule of the kernel, then dest
726 will read before src writes and we can save one reg_copy. */
727 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
728 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
731 if (nreg_moves4e
>= 1)
733 /* !single_set instructions are not supported yet and
734 thus we do not except to encounter them in the loop
735 except from the doloop part. For the latter case
736 we assume no regmoves are generated as the doloop
737 instructions are tied to the branch with an edge. */
739 /* If the instruction contains auto-inc register then
740 validate that the regmov is being generated for the
741 target regsiter rather then the inc'ed register. */
742 gcc_assert (!autoinc_var_is_used_p (u
->insn
, e
->dest
->insn
));
747 gcc_assert (e
->distance
< 2);
748 distances
[e
->distance
] = true;
750 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
756 /* Create NREG_MOVES register moves. */
757 first_move
= ps
->reg_moves
.length ();
758 ps
->reg_moves
.safe_grow_cleared (first_move
+ nreg_moves
);
759 extend_node_sched_params (ps
);
761 /* Record the moves associated with this node. */
762 first_move
+= ps
->g
->num_nodes
;
764 /* Generate each move. */
765 old_reg
= prev_reg
= SET_DEST (single_set (u
->insn
));
766 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
768 ps_reg_move_info
*move
= ps_reg_move (ps
, first_move
+ i_reg_move
);
770 move
->def
= i_reg_move
> 0 ? first_move
+ i_reg_move
- 1 : i
;
771 move
->uses
= sbitmap_alloc (first_move
+ nreg_moves
);
772 move
->old_reg
= old_reg
;
773 move
->new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
774 move
->num_consecutive_stages
= distances
[0] && distances
[1] ? 2 : 1;
775 move
->insn
= as_a
<rtx_insn
*> (gen_move_insn (move
->new_reg
,
776 copy_rtx (prev_reg
)));
777 bitmap_clear (move
->uses
);
779 prev_reg
= move
->new_reg
;
782 distance1_uses
= distances
[1] ? sbitmap_alloc (g
->num_nodes
) : NULL
;
785 bitmap_clear (distance1_uses
);
787 /* Every use of the register defined by node may require a different
788 copy of this register, depending on the time the use is scheduled.
789 Record which uses require which move results. */
790 for (e
= u
->out
; e
; e
= e
->next_out
)
791 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
793 int dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
794 - SCHED_TIME (e
->src
->cuid
)) / ii
;
796 if (e
->distance
== 1)
797 dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
798 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
800 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
801 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
806 ps_reg_move_info
*move
;
808 move
= ps_reg_move (ps
, first_move
+ dest_copy
- 1);
809 bitmap_set_bit (move
->uses
, e
->dest
->cuid
);
810 if (e
->distance
== 1)
811 bitmap_set_bit (distance1_uses
, e
->dest
->cuid
);
815 must_follow
= sbitmap_alloc (first_move
+ nreg_moves
);
816 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
817 if (!schedule_reg_move (ps
, first_move
+ i_reg_move
,
818 distance1_uses
, must_follow
))
820 sbitmap_free (must_follow
);
822 sbitmap_free (distance1_uses
);
823 if (i_reg_move
< nreg_moves
)
829 /* Emit the moves associatied with PS. Apply the substitutions
830 associated with them. */
832 apply_reg_moves (partial_schedule_ptr ps
)
834 ps_reg_move_info
*move
;
837 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
840 sbitmap_iterator sbi
;
842 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, i_use
, sbi
)
844 replace_rtx (ps
->g
->nodes
[i_use
].insn
, move
->old_reg
, move
->new_reg
);
845 df_insn_rescan (ps
->g
->nodes
[i_use
].insn
);
850 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
851 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
852 will move to cycle zero. */
854 reset_sched_times (partial_schedule_ptr ps
, int amount
)
858 ps_insn_ptr crr_insn
;
860 for (row
= 0; row
< ii
; row
++)
861 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
863 int u
= crr_insn
->id
;
864 int normalized_time
= SCHED_TIME (u
) - amount
;
865 int new_min_cycle
= PS_MIN_CYCLE (ps
) - amount
;
869 /* Print the scheduling times after the rotation. */
870 rtx_insn
*insn
= ps_rtl_insn (ps
, u
);
872 fprintf (dump_file
, "crr_insn->node=%d (insn id %d), "
873 "crr_insn->cycle=%d, min_cycle=%d", u
,
874 INSN_UID (insn
), normalized_time
, new_min_cycle
);
876 fprintf (dump_file
, " (branch)");
877 fprintf (dump_file
, "\n");
880 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
881 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
883 crr_insn
->cycle
= normalized_time
;
884 update_node_sched_params (u
, ii
, normalized_time
, new_min_cycle
);
888 /* Permute the insns according to their order in PS, from row 0 to
889 row ii-1, and position them right before LAST. This schedules
890 the insns of the loop kernel. */
892 permute_partial_schedule (partial_schedule_ptr ps
, rtx_insn
*last
)
898 for (row
= 0; row
< ii
; row
++)
899 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
901 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_ij
->id
);
903 if (PREV_INSN (last
) != insn
)
905 if (ps_ij
->id
< ps
->g
->num_nodes
)
906 reorder_insns_nobb (ps_first_note (ps
, ps_ij
->id
), insn
,
909 add_insn_before (insn
, last
, NULL
);
914 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
915 respectively only if cycle C falls on the border of the scheduling
916 window boundaries marked by START and END cycles. STEP is the
917 direction of the window. */
919 set_must_precede_follow (sbitmap
*tmp_follow
, sbitmap must_follow
,
920 sbitmap
*tmp_precede
, sbitmap must_precede
, int c
,
921 int start
, int end
, int step
)
929 *tmp_precede
= must_precede
;
930 else /* step == -1. */
931 *tmp_follow
= must_follow
;
936 *tmp_follow
= must_follow
;
937 else /* step == -1. */
938 *tmp_precede
= must_precede
;
943 /* Return True if the branch can be moved to row ii-1 while
944 normalizing the partial schedule PS to start from cycle zero and thus
945 optimize the SC. Otherwise return False. */
947 optimize_sc (partial_schedule_ptr ps
, ddg_ptr g
)
949 int amount
= PS_MIN_CYCLE (ps
);
950 sbitmap sched_nodes
= sbitmap_alloc (g
->num_nodes
);
951 int start
, end
, step
;
954 int stage_count
, stage_count_curr
;
956 /* Compare the SC after normalization and SC after bringing the branch
957 to row ii-1. If they are equal just bail out. */
958 stage_count
= calculate_stage_count (ps
, amount
);
960 calculate_stage_count (ps
, SCHED_TIME (g
->closing_branch
->cuid
) - (ii
- 1));
962 if (stage_count
== stage_count_curr
)
965 fprintf (dump_file
, "SMS SC already optimized.\n");
973 fprintf (dump_file
, "SMS Trying to optimize branch location\n");
974 fprintf (dump_file
, "SMS partial schedule before trial:\n");
975 print_partial_schedule (ps
, dump_file
);
978 /* First, normalize the partial scheduling. */
979 reset_sched_times (ps
, amount
);
980 rotate_partial_schedule (ps
, amount
);
984 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
986 print_partial_schedule (ps
, dump_file
);
989 if (SMODULO (SCHED_TIME (g
->closing_branch
->cuid
), ii
) == ii
- 1)
995 bitmap_ones (sched_nodes
);
997 /* Calculate the new placement of the branch. It should be in row
998 ii-1 and fall into it's scheduling window. */
999 if (get_sched_window (ps
, g
->closing_branch
, sched_nodes
, ii
, &start
,
1003 ps_insn_ptr next_ps_i
;
1004 int branch_cycle
= SCHED_TIME (g
->closing_branch
->cuid
);
1005 int row
= SMODULO (branch_cycle
, ps
->ii
);
1007 sbitmap must_precede
, must_follow
, tmp_precede
, tmp_follow
;
1011 fprintf (dump_file
, "\nTrying to schedule node %d "
1012 "INSN = %d in (%d .. %d) step %d\n",
1013 g
->closing_branch
->cuid
,
1014 (INSN_UID (g
->closing_branch
->insn
)), start
, end
, step
);
1016 gcc_assert ((step
> 0 && start
< end
) || (step
< 0 && start
> end
));
1019 c
= start
+ ii
- SMODULO (start
, ii
) - 1;
1020 gcc_assert (c
>= start
);
1026 "SMS failed to schedule branch at cycle: %d\n", c
);
1032 c
= start
- SMODULO (start
, ii
) - 1;
1033 gcc_assert (c
<= start
);
1039 "SMS failed to schedule branch at cycle: %d\n", c
);
1045 must_precede
= sbitmap_alloc (g
->num_nodes
);
1046 must_follow
= sbitmap_alloc (g
->num_nodes
);
1048 /* Try to schedule the branch is it's new cycle. */
1049 calculate_must_precede_follow (g
->closing_branch
, start
, end
,
1050 step
, ii
, sched_nodes
,
1051 must_precede
, must_follow
);
1053 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1054 must_precede
, c
, start
, end
, step
);
1056 /* Find the element in the partial schedule related to the closing
1057 branch so we can remove it from it's current cycle. */
1058 for (next_ps_i
= ps
->rows
[row
];
1059 next_ps_i
; next_ps_i
= next_ps_i
->next_in_row
)
1060 if (next_ps_i
->id
== g
->closing_branch
->cuid
)
1063 remove_node_from_ps (ps
, next_ps_i
);
1065 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
, c
,
1066 sched_nodes
, &num_splits
,
1067 tmp_precede
, tmp_follow
);
1068 gcc_assert (num_splits
== 0);
1073 "SMS failed to schedule branch at cycle: %d, "
1074 "bringing it back to cycle %d\n", c
, branch_cycle
);
1076 /* The branch was failed to be placed in row ii - 1.
1077 Put it back in it's original place in the partial
1079 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1080 must_precede
, branch_cycle
, start
, end
,
1083 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
,
1084 branch_cycle
, sched_nodes
,
1085 &num_splits
, tmp_precede
,
1087 gcc_assert (success
&& (num_splits
== 0));
1092 /* The branch is placed in row ii - 1. */
1095 "SMS success in moving branch to cycle %d\n", c
);
1097 update_node_sched_params (g
->closing_branch
->cuid
, ii
, c
,
1102 free (must_precede
);
1112 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
1113 int to_stage
, rtx count_reg
)
1118 for (row
= 0; row
< ps
->ii
; row
++)
1119 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
1122 int first_u
, last_u
;
1125 /* Do not duplicate any insn which refers to count_reg as it
1126 belongs to the control part.
1127 The closing branch is scheduled as well and thus should
1129 TODO: This should be done by analyzing the control part of
1131 u_insn
= ps_rtl_insn (ps
, u
);
1132 if (reg_mentioned_p (count_reg
, u_insn
)
1136 first_u
= SCHED_STAGE (u
);
1137 last_u
= first_u
+ ps_num_consecutive_stages (ps
, u
) - 1;
1138 if (from_stage
<= last_u
&& to_stage
>= first_u
)
1140 if (u
< ps
->g
->num_nodes
)
1141 duplicate_insn_chain (ps_first_note (ps
, u
), u_insn
);
1143 emit_insn (copy_rtx (PATTERN (u_insn
)));
1149 /* Generate the instructions (including reg_moves) for prolog & epilog. */
1151 generate_prolog_epilog (partial_schedule_ptr ps
, struct loop
*loop
,
1152 rtx count_reg
, rtx count_init
)
1155 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
1158 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1163 /* Generate instructions at the beginning of the prolog to
1164 adjust the loop count by STAGE_COUNT. If loop count is constant
1165 (count_init), this constant is adjusted by STAGE_COUNT in
1166 generate_prolog_epilog function. */
1167 rtx sub_reg
= NULL_RTX
;
1169 sub_reg
= expand_simple_binop (GET_MODE (count_reg
), MINUS
, count_reg
,
1170 gen_int_mode (last_stage
,
1171 GET_MODE (count_reg
)),
1172 count_reg
, 1, OPTAB_DIRECT
);
1173 gcc_assert (REG_P (sub_reg
));
1174 if (REGNO (sub_reg
) != REGNO (count_reg
))
1175 emit_move_insn (count_reg
, sub_reg
);
1178 for (i
= 0; i
< last_stage
; i
++)
1179 duplicate_insns_of_cycles (ps
, 0, i
, count_reg
);
1181 /* Put the prolog on the entry edge. */
1182 e
= loop_preheader_edge (loop
);
1183 split_edge_and_insert (e
, get_insns ());
1184 if (!flag_resched_modulo_sched
)
1185 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1189 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1192 for (i
= 0; i
< last_stage
; i
++)
1193 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, count_reg
);
1195 /* Put the epilogue on the exit edge. */
1196 gcc_assert (single_exit (loop
));
1197 e
= single_exit (loop
);
1198 split_edge_and_insert (e
, get_insns ());
1199 if (!flag_resched_modulo_sched
)
1200 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1205 /* Mark LOOP as software pipelined so the later
1206 scheduling passes don't touch it. */
1208 mark_loop_unsched (struct loop
*loop
)
1211 basic_block
*bbs
= get_loop_body (loop
);
1213 for (i
= 0; i
< loop
->num_nodes
; i
++)
1214 bbs
[i
]->flags
|= BB_DISABLE_SCHEDULE
;
1219 /* Return true if all the BBs of the loop are empty except the
1222 loop_single_full_bb_p (struct loop
*loop
)
1225 basic_block
*bbs
= get_loop_body (loop
);
1227 for (i
= 0; i
< loop
->num_nodes
; i
++)
1229 rtx_insn
*head
, *tail
;
1230 bool empty_bb
= true;
1232 if (bbs
[i
] == loop
->header
)
1235 /* Make sure that basic blocks other than the header
1236 have only notes labels or jumps. */
1237 get_ebb_head_tail (bbs
[i
], bbs
[i
], &head
, &tail
);
1238 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
1240 if (NOTE_P (head
) || LABEL_P (head
)
1241 || (INSN_P (head
) && (DEBUG_INSN_P (head
) || JUMP_P (head
))))
1257 /* Dump file:line from INSN's location info to dump_file. */
1260 dump_insn_location (rtx_insn
*insn
)
1262 if (dump_file
&& INSN_HAS_LOCATION (insn
))
1264 expanded_location xloc
= insn_location (insn
);
1265 fprintf (dump_file
, " %s:%i", xloc
.file
, xloc
.line
);
1269 /* A simple loop from SMS point of view; it is a loop that is composed of
1270 either a single basic block or two BBs - a header and a latch. */
1271 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1272 && (EDGE_COUNT (loop->latch->preds) == 1) \
1273 && (EDGE_COUNT (loop->latch->succs) == 1))
1275 /* Return true if the loop is in its canonical form and false if not.
1276 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1278 loop_canon_p (struct loop
*loop
)
1281 if (loop
->inner
|| !loop_outer (loop
))
1284 fprintf (dump_file
, "SMS loop inner or !loop_outer\n");
1288 if (!single_exit (loop
))
1292 rtx_insn
*insn
= BB_END (loop
->header
);
1294 fprintf (dump_file
, "SMS loop many exits");
1295 dump_insn_location (insn
);
1296 fprintf (dump_file
, "\n");
1301 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
1305 rtx_insn
*insn
= BB_END (loop
->header
);
1307 fprintf (dump_file
, "SMS loop many BBs.");
1308 dump_insn_location (insn
);
1309 fprintf (dump_file
, "\n");
1317 /* If there are more than one entry for the loop,
1318 make it one by splitting the first entry edge and
1319 redirecting the others to the new BB. */
1321 canon_loop (struct loop
*loop
)
1326 /* Avoid annoying special cases of edges going to exit
1328 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1329 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
1332 if (loop
->latch
== loop
->header
1333 || EDGE_COUNT (loop
->latch
->succs
) > 1)
1335 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
1336 if (e
->src
== loop
->latch
)
1344 setup_sched_infos (void)
1346 memcpy (&sms_common_sched_info
, &haifa_common_sched_info
,
1347 sizeof (sms_common_sched_info
));
1348 sms_common_sched_info
.sched_pass_id
= SCHED_SMS_PASS
;
1349 common_sched_info
= &sms_common_sched_info
;
1351 sched_deps_info
= &sms_sched_deps_info
;
1352 current_sched_info
= &sms_sched_info
;
1355 /* Probability in % that the sms-ed loop rolls enough so that optimized
1356 version may be entered. Just a guess. */
1357 #define PROB_SMS_ENOUGH_ITERATIONS 80
1359 /* Used to calculate the upper bound of ii. */
1360 #define MAXII_FACTOR 2
1362 /* Main entry point, perform SMS scheduling on the loops of the function
1363 that consist of single basic blocks. */
1370 int maxii
, max_asap
;
1371 partial_schedule_ptr ps
;
1372 basic_block bb
= NULL
;
1374 basic_block condition_bb
= NULL
;
1376 gcov_type trip_count
= 0;
1378 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1379 | LOOPS_HAVE_RECORDED_EXITS
);
1380 if (number_of_loops (cfun
) <= 1)
1382 loop_optimizer_finalize ();
1383 return; /* There are no loops to schedule. */
1386 /* Initialize issue_rate. */
1387 if (targetm
.sched
.issue_rate
)
1389 int temp
= reload_completed
;
1391 reload_completed
= 1;
1392 issue_rate
= targetm
.sched
.issue_rate ();
1393 reload_completed
= temp
;
1398 /* Initialize the scheduler. */
1399 setup_sched_infos ();
1400 haifa_sched_init ();
1402 /* Allocate memory to hold the DDG array one entry for each loop.
1403 We use loop->num as index into this array. */
1404 g_arr
= XCNEWVEC (ddg_ptr
, number_of_loops (cfun
));
1408 fprintf (dump_file
, "\n\nSMS analysis phase\n");
1409 fprintf (dump_file
, "===================\n\n");
1412 /* Build DDGs for all the relevant loops and hold them in G_ARR
1413 indexed by the loop index. */
1414 FOR_EACH_LOOP (loop
, 0)
1416 rtx_insn
*head
, *tail
;
1419 /* For debugging. */
1420 if (dbg_cnt (sms_sched_loop
) == false)
1423 fprintf (dump_file
, "SMS reached max limit... \n");
1430 rtx_insn
*insn
= BB_END (loop
->header
);
1432 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1433 dump_insn_location (insn
);
1434 fprintf (dump_file
, "\n");
1437 if (! loop_canon_p (loop
))
1440 if (! loop_single_full_bb_p (loop
))
1443 fprintf (dump_file
, "SMS not loop_single_full_bb_p\n");
1449 get_ebb_head_tail (bb
, bb
, &head
, &tail
);
1450 latch_edge
= loop_latch_edge (loop
);
1451 gcc_assert (single_exit (loop
));
1452 if (single_exit (loop
)->count
)
1453 trip_count
= latch_edge
->count
/ single_exit (loop
)->count
;
1455 /* Perform SMS only on loops that their average count is above threshold. */
1457 if ( latch_edge
->count
1458 && (latch_edge
->count
< single_exit (loop
)->count
* SMS_LOOP_AVERAGE_COUNT_THRESHOLD
))
1462 dump_insn_location (tail
);
1463 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1464 if (profile_info
&& flag_branch_probabilities
)
1466 fprintf (dump_file
, "SMS loop-count ");
1467 fprintf (dump_file
, "%"PRId64
,
1468 (int64_t) bb
->count
);
1469 fprintf (dump_file
, "\n");
1470 fprintf (dump_file
, "SMS trip-count ");
1471 fprintf (dump_file
, "%"PRId64
,
1472 (int64_t) trip_count
);
1473 fprintf (dump_file
, "\n");
1474 fprintf (dump_file
, "SMS profile-sum-max ");
1475 fprintf (dump_file
, "%"PRId64
,
1476 (int64_t) profile_info
->sum_max
);
1477 fprintf (dump_file
, "\n");
1483 /* Make sure this is a doloop. */
1484 if ( !(count_reg
= doloop_register_get (head
, tail
)))
1487 fprintf (dump_file
, "SMS doloop_register_get failed\n");
1491 /* Don't handle BBs with calls or barriers
1492 or !single_set with the exception of instructions that include
1493 count_reg---these instructions are part of the control part
1494 that do-loop recognizes.
1495 ??? Should handle insns defining subregs. */
1496 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1502 || (NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1503 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
1504 && !reg_mentioned_p (count_reg
, insn
))
1505 || (INSN_P (insn
) && (set
= single_set (insn
))
1506 && GET_CODE (SET_DEST (set
)) == SUBREG
))
1510 if (insn
!= NEXT_INSN (tail
))
1515 fprintf (dump_file
, "SMS loop-with-call\n");
1516 else if (BARRIER_P (insn
))
1517 fprintf (dump_file
, "SMS loop-with-barrier\n");
1518 else if ((NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1519 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
1520 fprintf (dump_file
, "SMS loop-with-not-single-set\n");
1522 fprintf (dump_file
, "SMS loop with subreg in lhs\n");
1523 print_rtl_single (dump_file
, insn
);
1529 /* Always schedule the closing branch with the rest of the
1530 instructions. The branch is rotated to be in row ii-1 at the
1531 end of the scheduling procedure to make sure it's the last
1532 instruction in the iteration. */
1533 if (! (g
= create_ddg (bb
, 1)))
1536 fprintf (dump_file
, "SMS create_ddg failed\n");
1540 g_arr
[loop
->num
] = g
;
1542 fprintf (dump_file
, "...OK\n");
1547 fprintf (dump_file
, "\nSMS transformation phase\n");
1548 fprintf (dump_file
, "=========================\n\n");
1551 /* We don't want to perform SMS on new loops - created by versioning. */
1552 FOR_EACH_LOOP (loop
, 0)
1554 rtx_insn
*head
, *tail
;
1556 rtx_insn
*count_init
;
1557 int mii
, rec_mii
, stage_count
, min_cycle
;
1558 int64_t loop_count
= 0;
1561 if (! (g
= g_arr
[loop
->num
]))
1566 rtx_insn
*insn
= BB_END (loop
->header
);
1568 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1569 dump_insn_location (insn
);
1570 fprintf (dump_file
, "\n");
1572 print_ddg (dump_file
, g
);
1575 get_ebb_head_tail (loop
->header
, loop
->header
, &head
, &tail
);
1577 latch_edge
= loop_latch_edge (loop
);
1578 gcc_assert (single_exit (loop
));
1579 if (single_exit (loop
)->count
)
1580 trip_count
= latch_edge
->count
/ single_exit (loop
)->count
;
1584 dump_insn_location (tail
);
1585 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1586 if (profile_info
&& flag_branch_probabilities
)
1588 fprintf (dump_file
, "SMS loop-count ");
1589 fprintf (dump_file
, "%"PRId64
,
1590 (int64_t) bb
->count
);
1591 fprintf (dump_file
, "\n");
1592 fprintf (dump_file
, "SMS profile-sum-max ");
1593 fprintf (dump_file
, "%"PRId64
,
1594 (int64_t) profile_info
->sum_max
);
1595 fprintf (dump_file
, "\n");
1597 fprintf (dump_file
, "SMS doloop\n");
1598 fprintf (dump_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1599 fprintf (dump_file
, "SMS num-loads %d\n", g
->num_loads
);
1600 fprintf (dump_file
, "SMS num-stores %d\n", g
->num_stores
);
1604 /* In case of th loop have doloop register it gets special
1607 if ((count_reg
= doloop_register_get (head
, tail
)))
1609 basic_block pre_header
;
1611 pre_header
= loop_preheader_edge (loop
)->src
;
1612 count_init
= const_iteration_count (count_reg
, pre_header
,
1615 gcc_assert (count_reg
);
1617 if (dump_file
&& count_init
)
1619 fprintf (dump_file
, "SMS const-doloop ");
1620 fprintf (dump_file
, "%"PRId64
,
1622 fprintf (dump_file
, "\n");
1625 node_order
= XNEWVEC (int, g
->num_nodes
);
1627 mii
= 1; /* Need to pass some estimate of mii. */
1628 rec_mii
= sms_order_nodes (g
, mii
, node_order
, &max_asap
);
1629 mii
= MAX (res_MII (g
), rec_mii
);
1630 maxii
= MAX (max_asap
, MAXII_FACTOR
* mii
);
1633 fprintf (dump_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1634 rec_mii
, mii
, maxii
);
1638 set_node_sched_params (g
);
1642 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
);
1646 /* Try to achieve optimized SC by normalizing the partial
1647 schedule (having the cycles start from cycle zero).
1648 The branch location must be placed in row ii-1 in the
1649 final scheduling. If failed, shift all instructions to
1650 position the branch in row ii-1. */
1651 opt_sc_p
= optimize_sc (ps
, g
);
1653 stage_count
= calculate_stage_count (ps
, 0);
1656 /* Bring the branch to cycle ii-1. */
1657 int amount
= (SCHED_TIME (g
->closing_branch
->cuid
)
1661 fprintf (dump_file
, "SMS schedule branch at cycle ii-1\n");
1663 stage_count
= calculate_stage_count (ps
, amount
);
1666 gcc_assert (stage_count
>= 1);
1669 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
1670 1 means that there is no interleaving between iterations thus
1671 we let the scheduling passes do the job in this case. */
1672 if (stage_count
< PARAM_VALUE (PARAM_SMS_MIN_SC
)
1673 || (count_init
&& (loop_count
<= stage_count
))
1674 || (flag_branch_probabilities
&& (trip_count
<= stage_count
)))
1678 fprintf (dump_file
, "SMS failed... \n");
1679 fprintf (dump_file
, "SMS sched-failed (stage-count=%d,"
1680 " loop-count=", stage_count
);
1681 fprintf (dump_file
, "%"PRId64
, loop_count
);
1682 fprintf (dump_file
, ", trip-count=");
1683 fprintf (dump_file
, "%"PRId64
, trip_count
);
1684 fprintf (dump_file
, ")\n");
1691 /* Rotate the partial schedule to have the branch in row ii-1. */
1692 int amount
= SCHED_TIME (g
->closing_branch
->cuid
) - (ps
->ii
- 1);
1694 reset_sched_times (ps
, amount
);
1695 rotate_partial_schedule (ps
, amount
);
1698 set_columns_for_ps (ps
);
1700 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1701 if (!schedule_reg_moves (ps
))
1704 free_partial_schedule (ps
);
1708 /* Moves that handle incoming values might have been added
1709 to a new first stage. Bump the stage count if so.
1711 ??? Perhaps we could consider rotating the schedule here
1713 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1715 reset_sched_times (ps
, 0);
1719 /* The stage count should now be correct without rotation. */
1720 gcc_checking_assert (stage_count
== calculate_stage_count (ps
, 0));
1721 PS_STAGE_COUNT (ps
) = stage_count
;
1727 dump_insn_location (tail
);
1728 fprintf (dump_file
, " SMS succeeded %d %d (with ii, sc)\n",
1729 ps
->ii
, stage_count
);
1730 print_partial_schedule (ps
, dump_file
);
1733 /* case the BCT count is not known , Do loop-versioning */
1734 if (count_reg
&& ! count_init
)
1736 rtx comp_rtx
= gen_rtx_GT (VOIDmode
, count_reg
,
1737 gen_int_mode (stage_count
,
1738 GET_MODE (count_reg
)));
1739 unsigned prob
= (PROB_SMS_ENOUGH_ITERATIONS
1740 * REG_BR_PROB_BASE
) / 100;
1742 loop_version (loop
, comp_rtx
, &condition_bb
,
1743 prob
, prob
, REG_BR_PROB_BASE
- prob
,
1747 /* Set new iteration count of loop kernel. */
1748 if (count_reg
&& count_init
)
1749 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1752 /* Now apply the scheduled kernel to the RTL of the loop. */
1753 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1755 /* Mark this loop as software pipelined so the later
1756 scheduling passes don't touch it. */
1757 if (! flag_resched_modulo_sched
)
1758 mark_loop_unsched (loop
);
1760 /* The life-info is not valid any more. */
1761 df_set_bb_dirty (g
->bb
);
1763 apply_reg_moves (ps
);
1765 print_node_sched_params (dump_file
, g
->num_nodes
, ps
);
1766 /* Generate prolog and epilog. */
1767 generate_prolog_epilog (ps
, loop
, count_reg
, count_init
);
1771 free_partial_schedule (ps
);
1772 node_sched_param_vec
.release ();
1779 /* Release scheduler data, needed until now because of DFA. */
1780 haifa_sched_finish ();
1781 loop_optimizer_finalize ();
1784 /* The SMS scheduling algorithm itself
1785 -----------------------------------
1786 Input: 'O' an ordered list of insns of a loop.
1787 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1789 'Q' is the empty Set
1790 'PS' is the partial schedule; it holds the currently scheduled nodes with
1792 'PSP' previously scheduled predecessors.
1793 'PSS' previously scheduled successors.
1794 't(u)' the cycle where u is scheduled.
1795 'l(u)' is the latency of u.
1796 'd(v,u)' is the dependence distance from v to u.
1797 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1798 the node ordering phase.
1799 'check_hardware_resources_conflicts(u, PS, c)'
1800 run a trace around cycle/slot through DFA model
1801 to check resource conflicts involving instruction u
1802 at cycle c given the partial schedule PS.
1803 'add_to_partial_schedule_at_time(u, PS, c)'
1804 Add the node/instruction u to the partial schedule
1806 'calculate_register_pressure(PS)'
1807 Given a schedule of instructions, calculate the register
1808 pressure it implies. One implementation could be the
1809 maximum number of overlapping live ranges.
1810 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1811 registers available in the hardware.
1815 3. for each node u in O in pre-computed order
1816 4. if (PSP(u) != Q && PSS(u) == Q) then
1817 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1818 6. start = Early_start; end = Early_start + II - 1; step = 1
1819 11. else if (PSP(u) == Q && PSS(u) != Q) then
1820 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1821 13. start = Late_start; end = Late_start - II + 1; step = -1
1822 14. else if (PSP(u) != Q && PSS(u) != Q) then
1823 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1824 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1825 17. start = Early_start;
1826 18. end = min(Early_start + II - 1 , Late_start);
1828 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1829 21. start = ASAP(u); end = start + II - 1; step = 1
1833 24. for (c = start ; c != end ; c += step)
1834 25. if check_hardware_resources_conflicts(u, PS, c) then
1835 26. add_to_partial_schedule_at_time(u, PS, c)
1840 31. if (success == false) then
1842 33. if (II > maxII) then
1843 34. finish - failed to schedule
1848 39. if (calculate_register_pressure(PS) > maxRP) then
1851 42. compute epilogue & prologue
1852 43. finish - succeeded to schedule
1854 ??? The algorithm restricts the scheduling window to II cycles.
1855 In rare cases, it may be better to allow windows of II+1 cycles.
1856 The window would then start and end on the same row, but with
1857 different "must precede" and "must follow" requirements. */
1859 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1860 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1861 set to 0 to save compile time. */
1862 #define DFA_HISTORY SMS_DFA_HISTORY
1864 /* A threshold for the number of repeated unsuccessful attempts to insert
1865 an empty row, before we flush the partial schedule and start over. */
1866 #define MAX_SPLIT_NUM 10
1867 /* Given the partial schedule PS, this function calculates and returns the
1868 cycles in which we can schedule the node with the given index I.
1869 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1870 noticed that there are several cases in which we fail to SMS the loop
1871 because the sched window of a node is empty due to tight data-deps. In
1872 such cases we want to unschedule some of the predecessors/successors
1873 until we get non-empty scheduling window. It returns -1 if the
1874 scheduling window is empty and zero otherwise. */
1877 get_sched_window (partial_schedule_ptr ps
, ddg_node_ptr u_node
,
1878 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
,
1881 int start
, step
, end
;
1882 int early_start
, late_start
;
1884 sbitmap psp
= sbitmap_alloc (ps
->g
->num_nodes
);
1885 sbitmap pss
= sbitmap_alloc (ps
->g
->num_nodes
);
1886 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1887 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1893 /* 1. compute sched window for u (start, end, step). */
1896 psp_not_empty
= bitmap_and (psp
, u_node_preds
, sched_nodes
);
1897 pss_not_empty
= bitmap_and (pss
, u_node_succs
, sched_nodes
);
1899 /* We first compute a forward range (start <= end), then decide whether
1901 early_start
= INT_MIN
;
1902 late_start
= INT_MAX
;
1910 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1912 fprintf (dump_file
, "\nAnalyzing dependencies for node %d (INSN %d)"
1913 "; ii = %d\n\n", u_node
->cuid
, INSN_UID (u_node
->insn
), ii
);
1914 fprintf (dump_file
, "%11s %11s %11s %11s %5s\n",
1915 "start", "early start", "late start", "end", "time");
1916 fprintf (dump_file
, "=========== =========== =========== ==========="
1919 /* Calculate early_start and limit end. Both bounds are inclusive. */
1921 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1923 int v
= e
->src
->cuid
;
1925 if (bitmap_bit_p (sched_nodes
, v
))
1927 int p_st
= SCHED_TIME (v
);
1928 int earliest
= p_st
+ e
->latency
- (e
->distance
* ii
);
1929 int latest
= (e
->data_type
== MEM_DEP
? p_st
+ ii
- 1 : INT_MAX
);
1933 fprintf (dump_file
, "%11s %11d %11s %11d %5d",
1934 "", earliest
, "", latest
, p_st
);
1935 print_ddg_edge (dump_file
, e
);
1936 fprintf (dump_file
, "\n");
1939 early_start
= MAX (early_start
, earliest
);
1940 end
= MIN (end
, latest
);
1942 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1947 /* Calculate late_start and limit start. Both bounds are inclusive. */
1949 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1951 int v
= e
->dest
->cuid
;
1953 if (bitmap_bit_p (sched_nodes
, v
))
1955 int s_st
= SCHED_TIME (v
);
1956 int earliest
= (e
->data_type
== MEM_DEP
? s_st
- ii
+ 1 : INT_MIN
);
1957 int latest
= s_st
- e
->latency
+ (e
->distance
* ii
);
1961 fprintf (dump_file
, "%11d %11s %11d %11s %5d",
1962 earliest
, "", latest
, "", s_st
);
1963 print_ddg_edge (dump_file
, e
);
1964 fprintf (dump_file
, "\n");
1967 start
= MAX (start
, earliest
);
1968 late_start
= MIN (late_start
, latest
);
1970 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1975 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1977 fprintf (dump_file
, "----------- ----------- ----------- -----------"
1979 fprintf (dump_file
, "%11d %11d %11d %11d %5s %s\n",
1980 start
, early_start
, late_start
, end
, "",
1981 "(max, max, min, min)");
1984 /* Get a target scheduling window no bigger than ii. */
1985 if (early_start
== INT_MIN
&& late_start
== INT_MAX
)
1986 early_start
= NODE_ASAP (u_node
);
1987 else if (early_start
== INT_MIN
)
1988 early_start
= late_start
- (ii
- 1);
1989 late_start
= MIN (late_start
, early_start
+ (ii
- 1));
1991 /* Apply memory dependence limits. */
1992 start
= MAX (start
, early_start
);
1993 end
= MIN (end
, late_start
);
1995 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1996 fprintf (dump_file
, "%11s %11d %11d %11s %5s final window\n",
1997 "", start
, end
, "", "");
1999 /* If there are at least as many successors as predecessors, schedule the
2000 node close to its successors. */
2001 if (pss_not_empty
&& count_succs
>= count_preds
)
2009 /* Now that we've finalized the window, make END an exclusive rather
2010 than an inclusive bound. */
2019 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
2022 fprintf (dump_file
, "\nEmpty window: start=%d, end=%d, step=%d\n",
2030 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
2031 node currently been scheduled. At the end of the calculation
2032 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
2033 U_NODE which are (1) already scheduled in the first/last row of
2034 U_NODE's scheduling window, (2) whose dependence inequality with U
2035 becomes an equality when U is scheduled in this same row, and (3)
2036 whose dependence latency is zero.
2038 The first and last rows are calculated using the following parameters:
2039 START/END rows - The cycles that begins/ends the traversal on the window;
2040 searching for an empty cycle to schedule U_NODE.
2041 STEP - The direction in which we traverse the window.
2042 II - The initiation interval. */
2045 calculate_must_precede_follow (ddg_node_ptr u_node
, int start
, int end
,
2046 int step
, int ii
, sbitmap sched_nodes
,
2047 sbitmap must_precede
, sbitmap must_follow
)
2050 int first_cycle_in_window
, last_cycle_in_window
;
2052 gcc_assert (must_precede
&& must_follow
);
2054 /* Consider the following scheduling window:
2055 {first_cycle_in_window, first_cycle_in_window+1, ...,
2056 last_cycle_in_window}. If step is 1 then the following will be
2057 the order we traverse the window: {start=first_cycle_in_window,
2058 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
2059 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
2060 end=first_cycle_in_window-1} if step is -1. */
2061 first_cycle_in_window
= (step
== 1) ? start
: end
- step
;
2062 last_cycle_in_window
= (step
== 1) ? end
- step
: start
;
2064 bitmap_clear (must_precede
);
2065 bitmap_clear (must_follow
);
2068 fprintf (dump_file
, "\nmust_precede: ");
2070 /* Instead of checking if:
2071 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
2072 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
2073 first_cycle_in_window)
2075 we use the fact that latency is non-negative:
2076 SCHED_TIME (e->src) - (e->distance * ii) <=
2077 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
2078 first_cycle_in_window
2080 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
2081 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2082 if (bitmap_bit_p (sched_nodes
, e
->src
->cuid
)
2083 && ((SCHED_TIME (e
->src
->cuid
) - (e
->distance
* ii
)) ==
2084 first_cycle_in_window
))
2087 fprintf (dump_file
, "%d ", e
->src
->cuid
);
2089 bitmap_set_bit (must_precede
, e
->src
->cuid
);
2093 fprintf (dump_file
, "\nmust_follow: ");
2095 /* Instead of checking if:
2096 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
2097 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
2098 last_cycle_in_window)
2100 we use the fact that latency is non-negative:
2101 SCHED_TIME (e->dest) + (e->distance * ii) >=
2102 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
2103 last_cycle_in_window
2105 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
2106 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2107 if (bitmap_bit_p (sched_nodes
, e
->dest
->cuid
)
2108 && ((SCHED_TIME (e
->dest
->cuid
) + (e
->distance
* ii
)) ==
2109 last_cycle_in_window
))
2112 fprintf (dump_file
, "%d ", e
->dest
->cuid
);
2114 bitmap_set_bit (must_follow
, e
->dest
->cuid
);
2118 fprintf (dump_file
, "\n");
2121 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
2122 parameters to decide if that's possible:
2123 PS - The partial schedule.
2124 U - The serial number of U_NODE.
2125 NUM_SPLITS - The number of row splits made so far.
2126 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
2127 the first row of the scheduling window)
2128 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
2129 last row of the scheduling window) */
2132 try_scheduling_node_in_cycle (partial_schedule_ptr ps
,
2133 int u
, int cycle
, sbitmap sched_nodes
,
2134 int *num_splits
, sbitmap must_precede
,
2135 sbitmap must_follow
)
2140 verify_partial_schedule (ps
, sched_nodes
);
2141 psi
= ps_add_node_check_conflicts (ps
, u
, cycle
, must_precede
, must_follow
);
2144 SCHED_TIME (u
) = cycle
;
2145 bitmap_set_bit (sched_nodes
, u
);
2149 fprintf (dump_file
, "Scheduled w/o split in %d\n", cycle
);
2156 /* This function implements the scheduling algorithm for SMS according to the
2158 static partial_schedule_ptr
2159 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
)
2162 int i
, c
, success
, num_splits
= 0;
2163 int flush_and_start_over
= true;
2164 int num_nodes
= g
->num_nodes
;
2165 int start
, end
, step
; /* Place together into one struct? */
2166 sbitmap sched_nodes
= sbitmap_alloc (num_nodes
);
2167 sbitmap must_precede
= sbitmap_alloc (num_nodes
);
2168 sbitmap must_follow
= sbitmap_alloc (num_nodes
);
2169 sbitmap tobe_scheduled
= sbitmap_alloc (num_nodes
);
2171 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
, DFA_HISTORY
);
2173 bitmap_ones (tobe_scheduled
);
2174 bitmap_clear (sched_nodes
);
2176 while (flush_and_start_over
&& (ii
< maxii
))
2180 fprintf (dump_file
, "Starting with ii=%d\n", ii
);
2181 flush_and_start_over
= false;
2182 bitmap_clear (sched_nodes
);
2184 for (i
= 0; i
< num_nodes
; i
++)
2186 int u
= nodes_order
[i
];
2187 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
2188 rtx insn
= u_node
->insn
;
2190 if (!NONDEBUG_INSN_P (insn
))
2192 bitmap_clear_bit (tobe_scheduled
, u
);
2196 if (bitmap_bit_p (sched_nodes
, u
))
2199 /* Try to get non-empty scheduling window. */
2201 if (get_sched_window (ps
, u_node
, sched_nodes
, ii
, &start
,
2205 fprintf (dump_file
, "\nTrying to schedule node %d "
2206 "INSN = %d in (%d .. %d) step %d\n", u
, (INSN_UID
2207 (g
->nodes
[u
].insn
)), start
, end
, step
);
2209 gcc_assert ((step
> 0 && start
< end
)
2210 || (step
< 0 && start
> end
));
2212 calculate_must_precede_follow (u_node
, start
, end
, step
, ii
,
2213 sched_nodes
, must_precede
,
2216 for (c
= start
; c
!= end
; c
+= step
)
2218 sbitmap tmp_precede
, tmp_follow
;
2220 set_must_precede_follow (&tmp_follow
, must_follow
,
2221 &tmp_precede
, must_precede
,
2222 c
, start
, end
, step
);
2224 try_scheduling_node_in_cycle (ps
, u
, c
,
2226 &num_splits
, tmp_precede
,
2232 verify_partial_schedule (ps
, sched_nodes
);
2241 if (num_splits
>= MAX_SPLIT_NUM
)
2244 flush_and_start_over
= true;
2245 verify_partial_schedule (ps
, sched_nodes
);
2246 reset_partial_schedule (ps
, ii
);
2247 verify_partial_schedule (ps
, sched_nodes
);
2252 /* The scheduling window is exclusive of 'end'
2253 whereas compute_split_window() expects an inclusive,
2256 split_row
= compute_split_row (sched_nodes
, start
, end
- 1,
2259 split_row
= compute_split_row (sched_nodes
, end
+ 1, start
,
2262 ps_insert_empty_row (ps
, split_row
, sched_nodes
);
2263 i
--; /* Go back and retry node i. */
2266 fprintf (dump_file
, "num_splits=%d\n", num_splits
);
2269 /* ??? If (success), check register pressure estimates. */
2270 } /* Continue with next node. */
2271 } /* While flush_and_start_over. */
2274 free_partial_schedule (ps
);
2278 gcc_assert (bitmap_equal_p (tobe_scheduled
, sched_nodes
));
2280 sbitmap_free (sched_nodes
);
2281 sbitmap_free (must_precede
);
2282 sbitmap_free (must_follow
);
2283 sbitmap_free (tobe_scheduled
);
2288 /* This function inserts a new empty row into PS at the position
2289 according to SPLITROW, keeping all already scheduled instructions
2290 intact and updating their SCHED_TIME and cycle accordingly. */
2292 ps_insert_empty_row (partial_schedule_ptr ps
, int split_row
,
2293 sbitmap sched_nodes
)
2295 ps_insn_ptr crr_insn
;
2296 ps_insn_ptr
*rows_new
;
2298 int new_ii
= ii
+ 1;
2300 int *rows_length_new
;
2302 verify_partial_schedule (ps
, sched_nodes
);
2304 /* We normalize sched_time and rotate ps to have only non-negative sched
2305 times, for simplicity of updating cycles after inserting new row. */
2306 split_row
-= ps
->min_cycle
;
2307 split_row
= SMODULO (split_row
, ii
);
2309 fprintf (dump_file
, "split_row=%d\n", split_row
);
2311 reset_sched_times (ps
, PS_MIN_CYCLE (ps
));
2312 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
2314 rows_new
= (ps_insn_ptr
*) xcalloc (new_ii
, sizeof (ps_insn_ptr
));
2315 rows_length_new
= (int *) xcalloc (new_ii
, sizeof (int));
2316 for (row
= 0; row
< split_row
; row
++)
2318 rows_new
[row
] = ps
->rows
[row
];
2319 rows_length_new
[row
] = ps
->rows_length
[row
];
2320 ps
->rows
[row
] = NULL
;
2321 for (crr_insn
= rows_new
[row
];
2322 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2324 int u
= crr_insn
->id
;
2325 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
);
2327 SCHED_TIME (u
) = new_time
;
2328 crr_insn
->cycle
= new_time
;
2329 SCHED_ROW (u
) = new_time
% new_ii
;
2330 SCHED_STAGE (u
) = new_time
/ new_ii
;
2335 rows_new
[split_row
] = NULL
;
2337 for (row
= split_row
; row
< ii
; row
++)
2339 rows_new
[row
+ 1] = ps
->rows
[row
];
2340 rows_length_new
[row
+ 1] = ps
->rows_length
[row
];
2341 ps
->rows
[row
] = NULL
;
2342 for (crr_insn
= rows_new
[row
+ 1];
2343 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2345 int u
= crr_insn
->id
;
2346 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
) + 1;
2348 SCHED_TIME (u
) = new_time
;
2349 crr_insn
->cycle
= new_time
;
2350 SCHED_ROW (u
) = new_time
% new_ii
;
2351 SCHED_STAGE (u
) = new_time
/ new_ii
;
2356 ps
->min_cycle
= ps
->min_cycle
+ ps
->min_cycle
/ ii
2357 + (SMODULO (ps
->min_cycle
, ii
) >= split_row
? 1 : 0);
2358 ps
->max_cycle
= ps
->max_cycle
+ ps
->max_cycle
/ ii
2359 + (SMODULO (ps
->max_cycle
, ii
) >= split_row
? 1 : 0);
2361 ps
->rows
= rows_new
;
2362 free (ps
->rows_length
);
2363 ps
->rows_length
= rows_length_new
;
2365 gcc_assert (ps
->min_cycle
>= 0);
2367 verify_partial_schedule (ps
, sched_nodes
);
2370 fprintf (dump_file
, "min_cycle=%d, max_cycle=%d\n", ps
->min_cycle
,
2374 /* Given U_NODE which is the node that failed to be scheduled; LOW and
2375 UP which are the boundaries of it's scheduling window; compute using
2376 SCHED_NODES and II a row in the partial schedule that can be split
2377 which will separate a critical predecessor from a critical successor
2378 thereby expanding the window, and return it. */
2380 compute_split_row (sbitmap sched_nodes
, int low
, int up
, int ii
,
2381 ddg_node_ptr u_node
)
2384 int lower
= INT_MIN
, upper
= INT_MAX
;
2389 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2391 int v
= e
->src
->cuid
;
2393 if (bitmap_bit_p (sched_nodes
, v
)
2394 && (low
== SCHED_TIME (v
) + e
->latency
- (e
->distance
* ii
)))
2395 if (SCHED_TIME (v
) > lower
)
2398 lower
= SCHED_TIME (v
);
2404 crit_cycle
= SCHED_TIME (crit_pred
) + 1;
2405 return SMODULO (crit_cycle
, ii
);
2408 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2410 int v
= e
->dest
->cuid
;
2412 if (bitmap_bit_p (sched_nodes
, v
)
2413 && (up
== SCHED_TIME (v
) - e
->latency
+ (e
->distance
* ii
)))
2414 if (SCHED_TIME (v
) < upper
)
2417 upper
= SCHED_TIME (v
);
2423 crit_cycle
= SCHED_TIME (crit_succ
);
2424 return SMODULO (crit_cycle
, ii
);
2428 fprintf (dump_file
, "Both crit_pred and crit_succ are NULL\n");
2430 return SMODULO ((low
+ up
+ 1) / 2, ii
);
2434 verify_partial_schedule (partial_schedule_ptr ps
, sbitmap sched_nodes
)
2437 ps_insn_ptr crr_insn
;
2439 for (row
= 0; row
< ps
->ii
; row
++)
2443 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2445 int u
= crr_insn
->id
;
2448 gcc_assert (bitmap_bit_p (sched_nodes
, u
));
2449 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2450 popcount (sched_nodes) == number of insns in ps. */
2451 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
2452 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
2455 gcc_assert (ps
->rows_length
[row
] == length
);
2460 /* This page implements the algorithm for ordering the nodes of a DDG
2461 for modulo scheduling, activated through the
2462 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2464 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2465 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
2466 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
2467 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2468 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
2469 #define DEPTH(x) (ASAP ((x)))
2471 typedef struct node_order_params
* nopa
;
2473 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
2474 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
2475 static nopa
calculate_order_params (ddg_ptr
, int, int *);
2476 static int find_max_asap (ddg_ptr
, sbitmap
);
2477 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
2478 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
2480 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
2482 struct node_order_params
2489 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2491 check_nodes_order (int *node_order
, int num_nodes
)
2494 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2499 fprintf (dump_file
, "SMS final nodes order: \n");
2501 for (i
= 0; i
< num_nodes
; i
++)
2503 int u
= node_order
[i
];
2506 fprintf (dump_file
, "%d ", u
);
2507 gcc_assert (u
< num_nodes
&& u
>= 0 && !bitmap_bit_p (tmp
, u
));
2509 bitmap_set_bit (tmp
, u
);
2513 fprintf (dump_file
, "\n");
2518 /* Order the nodes of G for scheduling and pass the result in
2519 NODE_ORDER. Also set aux.count of each node to ASAP.
2520 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2522 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
, int *pmax_asap
)
2526 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
2528 nopa nops
= calculate_order_params (g
, mii
, pmax_asap
);
2531 print_sccs (dump_file
, sccs
, g
);
2533 order_nodes_of_sccs (sccs
, node_order
);
2535 if (sccs
->num_sccs
> 0)
2536 /* First SCC has the largest recurrence_length. */
2537 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
2539 /* Save ASAP before destroying node_order_params. */
2540 for (i
= 0; i
< g
->num_nodes
; i
++)
2542 ddg_node_ptr v
= &g
->nodes
[i
];
2543 v
->aux
.count
= ASAP (v
);
2547 free_ddg_all_sccs (sccs
);
2548 check_nodes_order (node_order
, g
->num_nodes
);
2554 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
2557 ddg_ptr g
= all_sccs
->ddg
;
2558 int num_nodes
= g
->num_nodes
;
2559 sbitmap prev_sccs
= sbitmap_alloc (num_nodes
);
2560 sbitmap on_path
= sbitmap_alloc (num_nodes
);
2561 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2562 sbitmap ones
= sbitmap_alloc (num_nodes
);
2564 bitmap_clear (prev_sccs
);
2567 /* Perform the node ordering starting from the SCC with the highest recMII.
2568 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2569 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
2571 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
2573 /* Add nodes on paths from previous SCCs to the current SCC. */
2574 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
2575 bitmap_ior (tmp
, scc
->nodes
, on_path
);
2577 /* Add nodes on paths from the current SCC to previous SCCs. */
2578 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
2579 bitmap_ior (tmp
, tmp
, on_path
);
2581 /* Remove nodes of previous SCCs from current extended SCC. */
2582 bitmap_and_compl (tmp
, tmp
, prev_sccs
);
2584 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2585 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2588 /* Handle the remaining nodes that do not belong to any scc. Each call
2589 to order_nodes_in_scc handles a single connected component. */
2590 while (pos
< g
->num_nodes
)
2592 bitmap_and_compl (tmp
, ones
, prev_sccs
);
2593 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2595 sbitmap_free (prev_sccs
);
2596 sbitmap_free (on_path
);
2598 sbitmap_free (ones
);
2601 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2602 static struct node_order_params
*
2603 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
, int *pmax_asap
)
2607 int num_nodes
= g
->num_nodes
;
2609 /* Allocate a place to hold ordering params for each node in the DDG. */
2610 nopa node_order_params_arr
;
2612 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2613 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
2614 sizeof (struct node_order_params
));
2616 /* Set the aux pointer of each node to point to its order_params structure. */
2617 for (u
= 0; u
< num_nodes
; u
++)
2618 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
2620 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2621 calculate ASAP, ALAP, mobility, distance, and height for each node
2622 in the dependence (direct acyclic) graph. */
2624 /* We assume that the nodes in the array are in topological order. */
2627 for (u
= 0; u
< num_nodes
; u
++)
2629 ddg_node_ptr u_node
= &g
->nodes
[u
];
2632 for (e
= u_node
->in
; e
; e
= e
->next_in
)
2633 if (e
->distance
== 0)
2634 ASAP (u_node
) = MAX (ASAP (u_node
),
2635 ASAP (e
->src
) + e
->latency
);
2636 max_asap
= MAX (max_asap
, ASAP (u_node
));
2639 for (u
= num_nodes
- 1; u
> -1; u
--)
2641 ddg_node_ptr u_node
= &g
->nodes
[u
];
2643 ALAP (u_node
) = max_asap
;
2644 HEIGHT (u_node
) = 0;
2645 for (e
= u_node
->out
; e
; e
= e
->next_out
)
2646 if (e
->distance
== 0)
2648 ALAP (u_node
) = MIN (ALAP (u_node
),
2649 ALAP (e
->dest
) - e
->latency
);
2650 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
2651 HEIGHT (e
->dest
) + e
->latency
);
2656 fprintf (dump_file
, "\nOrder params\n");
2657 for (u
= 0; u
< num_nodes
; u
++)
2659 ddg_node_ptr u_node
= &g
->nodes
[u
];
2661 fprintf (dump_file
, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u
,
2662 ASAP (u_node
), ALAP (u_node
), HEIGHT (u_node
));
2666 *pmax_asap
= max_asap
;
2667 return node_order_params_arr
;
2671 find_max_asap (ddg_ptr g
, sbitmap nodes
)
2676 sbitmap_iterator sbi
;
2678 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2680 ddg_node_ptr u_node
= &g
->nodes
[u
];
2682 if (max_asap
< ASAP (u_node
))
2684 max_asap
= ASAP (u_node
);
2692 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
2696 int min_mob
= INT_MAX
;
2698 sbitmap_iterator sbi
;
2700 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2702 ddg_node_ptr u_node
= &g
->nodes
[u
];
2704 if (max_hv
< HEIGHT (u_node
))
2706 max_hv
= HEIGHT (u_node
);
2707 min_mob
= MOB (u_node
);
2710 else if ((max_hv
== HEIGHT (u_node
))
2711 && (min_mob
> MOB (u_node
)))
2713 min_mob
= MOB (u_node
);
2721 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
2725 int min_mob
= INT_MAX
;
2727 sbitmap_iterator sbi
;
2729 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2731 ddg_node_ptr u_node
= &g
->nodes
[u
];
2733 if (max_dv
< DEPTH (u_node
))
2735 max_dv
= DEPTH (u_node
);
2736 min_mob
= MOB (u_node
);
2739 else if ((max_dv
== DEPTH (u_node
))
2740 && (min_mob
> MOB (u_node
)))
2742 min_mob
= MOB (u_node
);
2749 /* Places the nodes of SCC into the NODE_ORDER array starting
2750 at position POS, according to the SMS ordering algorithm.
2751 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2752 the NODE_ORDER array, starting from position zero. */
2754 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
2755 int * node_order
, int pos
)
2757 enum sms_direction dir
;
2758 int num_nodes
= g
->num_nodes
;
2759 sbitmap workset
= sbitmap_alloc (num_nodes
);
2760 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2761 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
2762 sbitmap predecessors
= sbitmap_alloc (num_nodes
);
2763 sbitmap successors
= sbitmap_alloc (num_nodes
);
2765 bitmap_clear (predecessors
);
2766 find_predecessors (predecessors
, g
, nodes_ordered
);
2768 bitmap_clear (successors
);
2769 find_successors (successors
, g
, nodes_ordered
);
2772 if (bitmap_and (tmp
, predecessors
, scc
))
2774 bitmap_copy (workset
, tmp
);
2777 else if (bitmap_and (tmp
, successors
, scc
))
2779 bitmap_copy (workset
, tmp
);
2786 bitmap_clear (workset
);
2787 if ((u
= find_max_asap (g
, scc
)) >= 0)
2788 bitmap_set_bit (workset
, u
);
2792 bitmap_clear (zero_bitmap
);
2793 while (!bitmap_equal_p (workset
, zero_bitmap
))
2796 ddg_node_ptr v_node
;
2797 sbitmap v_node_preds
;
2798 sbitmap v_node_succs
;
2802 while (!bitmap_equal_p (workset
, zero_bitmap
))
2804 v
= find_max_hv_min_mob (g
, workset
);
2805 v_node
= &g
->nodes
[v
];
2806 node_order
[pos
++] = v
;
2807 v_node_succs
= NODE_SUCCESSORS (v_node
);
2808 bitmap_and (tmp
, v_node_succs
, scc
);
2810 /* Don't consider the already ordered successors again. */
2811 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2812 bitmap_ior (workset
, workset
, tmp
);
2813 bitmap_clear_bit (workset
, v
);
2814 bitmap_set_bit (nodes_ordered
, v
);
2817 bitmap_clear (predecessors
);
2818 find_predecessors (predecessors
, g
, nodes_ordered
);
2819 bitmap_and (workset
, predecessors
, scc
);
2823 while (!bitmap_equal_p (workset
, zero_bitmap
))
2825 v
= find_max_dv_min_mob (g
, workset
);
2826 v_node
= &g
->nodes
[v
];
2827 node_order
[pos
++] = v
;
2828 v_node_preds
= NODE_PREDECESSORS (v_node
);
2829 bitmap_and (tmp
, v_node_preds
, scc
);
2831 /* Don't consider the already ordered predecessors again. */
2832 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2833 bitmap_ior (workset
, workset
, tmp
);
2834 bitmap_clear_bit (workset
, v
);
2835 bitmap_set_bit (nodes_ordered
, v
);
2838 bitmap_clear (successors
);
2839 find_successors (successors
, g
, nodes_ordered
);
2840 bitmap_and (workset
, successors
, scc
);
2844 sbitmap_free (workset
);
2845 sbitmap_free (zero_bitmap
);
2846 sbitmap_free (predecessors
);
2847 sbitmap_free (successors
);
2852 /* This page contains functions for manipulating partial-schedules during
2853 modulo scheduling. */
2855 /* Create a partial schedule and allocate a memory to hold II rows. */
2857 static partial_schedule_ptr
2858 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2860 partial_schedule_ptr ps
= XNEW (struct partial_schedule
);
2861 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2862 ps
->rows_length
= (int *) xcalloc (ii
, sizeof (int));
2863 ps
->reg_moves
.create (0);
2865 ps
->history
= history
;
2866 ps
->min_cycle
= INT_MAX
;
2867 ps
->max_cycle
= INT_MIN
;
2873 /* Free the PS_INSNs in rows array of the given partial schedule.
2874 ??? Consider caching the PS_INSN's. */
2876 free_ps_insns (partial_schedule_ptr ps
)
2880 for (i
= 0; i
< ps
->ii
; i
++)
2884 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2887 ps
->rows
[i
] = ps_insn
;
2893 /* Free all the memory allocated to the partial schedule. */
2896 free_partial_schedule (partial_schedule_ptr ps
)
2898 ps_reg_move_info
*move
;
2904 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
2905 sbitmap_free (move
->uses
);
2906 ps
->reg_moves
.release ();
2910 free (ps
->rows_length
);
2914 /* Clear the rows array with its PS_INSNs, and create a new one with
2918 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2923 if (new_ii
== ps
->ii
)
2925 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2926 * sizeof (ps_insn_ptr
));
2927 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2928 ps
->rows_length
= (int *) xrealloc (ps
->rows_length
, new_ii
* sizeof (int));
2929 memset (ps
->rows_length
, 0, new_ii
* sizeof (int));
2931 ps
->min_cycle
= INT_MAX
;
2932 ps
->max_cycle
= INT_MIN
;
2935 /* Prints the partial schedule as an ii rows array, for each rows
2936 print the ids of the insns in it. */
2938 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2942 for (i
= 0; i
< ps
->ii
; i
++)
2944 ps_insn_ptr ps_i
= ps
->rows
[i
];
2946 fprintf (dump
, "\n[ROW %d ]: ", i
);
2949 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_i
->id
);
2952 fprintf (dump
, "%d (branch), ", INSN_UID (insn
));
2954 fprintf (dump
, "%d, ", INSN_UID (insn
));
2956 ps_i
= ps_i
->next_in_row
;
2961 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2963 create_ps_insn (int id
, int cycle
)
2965 ps_insn_ptr ps_i
= XNEW (struct ps_insn
);
2968 ps_i
->next_in_row
= NULL
;
2969 ps_i
->prev_in_row
= NULL
;
2970 ps_i
->cycle
= cycle
;
2976 /* Removes the given PS_INSN from the partial schedule. */
2978 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2982 gcc_assert (ps
&& ps_i
);
2984 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2985 if (! ps_i
->prev_in_row
)
2987 gcc_assert (ps_i
== ps
->rows
[row
]);
2988 ps
->rows
[row
] = ps_i
->next_in_row
;
2990 ps
->rows
[row
]->prev_in_row
= NULL
;
2994 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
2995 if (ps_i
->next_in_row
)
2996 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
2999 ps
->rows_length
[row
] -= 1;
3004 /* Unlike what literature describes for modulo scheduling (which focuses
3005 on VLIW machines) the order of the instructions inside a cycle is
3006 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
3007 where the current instruction should go relative to the already
3008 scheduled instructions in the given cycle. Go over these
3009 instructions and find the first possible column to put it in. */
3011 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
3012 sbitmap must_precede
, sbitmap must_follow
)
3014 ps_insn_ptr next_ps_i
;
3015 ps_insn_ptr first_must_follow
= NULL
;
3016 ps_insn_ptr last_must_precede
= NULL
;
3017 ps_insn_ptr last_in_row
= NULL
;
3023 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3025 /* Find the first must follow and the last must precede
3026 and insert the node immediately after the must precede
3027 but make sure that it there is no must follow after it. */
3028 for (next_ps_i
= ps
->rows
[row
];
3030 next_ps_i
= next_ps_i
->next_in_row
)
3033 && bitmap_bit_p (must_follow
, next_ps_i
->id
)
3034 && ! first_must_follow
)
3035 first_must_follow
= next_ps_i
;
3036 if (must_precede
&& bitmap_bit_p (must_precede
, next_ps_i
->id
))
3038 /* If we have already met a node that must follow, then
3039 there is no possible column. */
3040 if (first_must_follow
)
3043 last_must_precede
= next_ps_i
;
3045 /* The closing branch must be the last in the row. */
3047 && bitmap_bit_p (must_precede
, next_ps_i
->id
)
3048 && JUMP_P (ps_rtl_insn (ps
, next_ps_i
->id
)))
3051 last_in_row
= next_ps_i
;
3054 /* The closing branch is scheduled as well. Make sure there is no
3055 dependent instruction after it as the branch should be the last
3056 instruction in the row. */
3057 if (JUMP_P (ps_rtl_insn (ps
, ps_i
->id
)))
3059 if (first_must_follow
)
3063 /* Make the branch the last in the row. New instructions
3064 will be inserted at the beginning of the row or after the
3065 last must_precede instruction thus the branch is guaranteed
3066 to remain the last instruction in the row. */
3067 last_in_row
->next_in_row
= ps_i
;
3068 ps_i
->prev_in_row
= last_in_row
;
3069 ps_i
->next_in_row
= NULL
;
3072 ps
->rows
[row
] = ps_i
;
3076 /* Now insert the node after INSERT_AFTER_PSI. */
3078 if (! last_must_precede
)
3080 ps_i
->next_in_row
= ps
->rows
[row
];
3081 ps_i
->prev_in_row
= NULL
;
3082 if (ps_i
->next_in_row
)
3083 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3084 ps
->rows
[row
] = ps_i
;
3088 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
3089 last_must_precede
->next_in_row
= ps_i
;
3090 ps_i
->prev_in_row
= last_must_precede
;
3091 if (ps_i
->next_in_row
)
3092 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3098 /* Advances the PS_INSN one column in its current row; returns false
3099 in failure and true in success. Bit N is set in MUST_FOLLOW if
3100 the node with cuid N must be come after the node pointed to by
3101 PS_I when scheduled in the same cycle. */
3103 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
3104 sbitmap must_follow
)
3106 ps_insn_ptr prev
, next
;
3112 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3114 if (! ps_i
->next_in_row
)
3117 /* Check if next_in_row is dependent on ps_i, both having same sched
3118 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
3119 if (must_follow
&& bitmap_bit_p (must_follow
, ps_i
->next_in_row
->id
))
3122 /* Advance PS_I over its next_in_row in the doubly linked list. */
3123 prev
= ps_i
->prev_in_row
;
3124 next
= ps_i
->next_in_row
;
3126 if (ps_i
== ps
->rows
[row
])
3127 ps
->rows
[row
] = next
;
3129 ps_i
->next_in_row
= next
->next_in_row
;
3131 if (next
->next_in_row
)
3132 next
->next_in_row
->prev_in_row
= ps_i
;
3134 next
->next_in_row
= ps_i
;
3135 ps_i
->prev_in_row
= next
;
3137 next
->prev_in_row
= prev
;
3139 prev
->next_in_row
= next
;
3144 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
3145 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
3146 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
3147 before/after (respectively) the node pointed to by PS_I when scheduled
3148 in the same cycle. */
3150 add_node_to_ps (partial_schedule_ptr ps
, int id
, int cycle
,
3151 sbitmap must_precede
, sbitmap must_follow
)
3154 int row
= SMODULO (cycle
, ps
->ii
);
3156 if (ps
->rows_length
[row
] >= issue_rate
)
3159 ps_i
= create_ps_insn (id
, cycle
);
3161 /* Finds and inserts PS_I according to MUST_FOLLOW and
3163 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
3169 ps
->rows_length
[row
] += 1;
3173 /* Advance time one cycle. Assumes DFA is being used. */
3175 advance_one_cycle (void)
3177 if (targetm
.sched
.dfa_pre_cycle_insn
)
3178 state_transition (curr_state
,
3179 targetm
.sched
.dfa_pre_cycle_insn ());
3181 state_transition (curr_state
, NULL
);
3183 if (targetm
.sched
.dfa_post_cycle_insn
)
3184 state_transition (curr_state
,
3185 targetm
.sched
.dfa_post_cycle_insn ());
3190 /* Checks if PS has resource conflicts according to DFA, starting from
3191 FROM cycle to TO cycle; returns true if there are conflicts and false
3192 if there are no conflicts. Assumes DFA is being used. */
3194 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
3198 state_reset (curr_state
);
3200 for (cycle
= from
; cycle
<= to
; cycle
++)
3202 ps_insn_ptr crr_insn
;
3203 /* Holds the remaining issue slots in the current row. */
3204 int can_issue_more
= issue_rate
;
3206 /* Walk through the DFA for the current row. */
3207 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
3209 crr_insn
= crr_insn
->next_in_row
)
3211 rtx_insn
*insn
= ps_rtl_insn (ps
, crr_insn
->id
);
3213 if (!NONDEBUG_INSN_P (insn
))
3216 /* Check if there is room for the current insn. */
3217 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
3220 /* Update the DFA state and return with failure if the DFA found
3221 resource conflicts. */
3222 if (state_transition (curr_state
, insn
) >= 0)
3225 if (targetm
.sched
.variable_issue
)
3227 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
3228 insn
, can_issue_more
);
3229 /* A naked CLOBBER or USE generates no instruction, so don't
3230 let them consume issue slots. */
3231 else if (GET_CODE (PATTERN (insn
)) != USE
3232 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3236 /* Advance the DFA to the next cycle. */
3237 advance_one_cycle ();
3242 /* Checks if the given node causes resource conflicts when added to PS at
3243 cycle C. If not the node is added to PS and returned; otherwise zero
3244 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
3245 cuid N must be come before/after (respectively) the node pointed to by
3246 PS_I when scheduled in the same cycle. */
3248 ps_add_node_check_conflicts (partial_schedule_ptr ps
, int n
,
3249 int c
, sbitmap must_precede
,
3250 sbitmap must_follow
)
3252 int has_conflicts
= 0;
3255 /* First add the node to the PS, if this succeeds check for
3256 conflicts, trying different issue slots in the same row. */
3257 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
3258 return NULL
; /* Failed to insert the node at the given cycle. */
3260 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3262 && ps_has_conflicts (ps
,
3266 /* Try different issue slots to find one that the given node can be
3267 scheduled in without conflicts. */
3268 while (has_conflicts
)
3270 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
3272 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3274 && ps_has_conflicts (ps
,
3281 remove_node_from_ps (ps
, ps_i
);
3285 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
3286 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
3290 /* Calculate the stage count of the partial schedule PS. The calculation
3291 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3293 calculate_stage_count (partial_schedule_ptr ps
, int rotation_amount
)
3295 int new_min_cycle
= PS_MIN_CYCLE (ps
) - rotation_amount
;
3296 int new_max_cycle
= PS_MAX_CYCLE (ps
) - rotation_amount
;
3297 int stage_count
= CALC_STAGE_COUNT (-1, new_min_cycle
, ps
->ii
);
3299 /* The calculation of stage count is done adding the number of stages
3300 before cycle zero and after cycle zero. */
3301 stage_count
+= CALC_STAGE_COUNT (new_max_cycle
, 0, ps
->ii
);
3306 /* Rotate the rows of PS such that insns scheduled at time
3307 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3309 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
3311 int i
, row
, backward_rotates
;
3312 int last_row
= ps
->ii
- 1;
3314 if (start_cycle
== 0)
3317 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
3319 /* Revisit later and optimize this into a single loop. */
3320 for (i
= 0; i
< backward_rotates
; i
++)
3322 ps_insn_ptr first_row
= ps
->rows
[0];
3323 int first_row_length
= ps
->rows_length
[0];
3325 for (row
= 0; row
< last_row
; row
++)
3327 ps
->rows
[row
] = ps
->rows
[row
+ 1];
3328 ps
->rows_length
[row
] = ps
->rows_length
[row
+ 1];
3331 ps
->rows
[last_row
] = first_row
;
3332 ps
->rows_length
[last_row
] = first_row_length
;
3335 ps
->max_cycle
-= start_cycle
;
3336 ps
->min_cycle
-= start_cycle
;
3339 #endif /* INSN_SCHEDULING */
3341 /* Run instruction scheduler. */
3342 /* Perform SMS module scheduling. */
3346 const pass_data pass_data_sms
=
3348 RTL_PASS
, /* type */
3350 OPTGROUP_NONE
, /* optinfo_flags */
3352 0, /* properties_required */
3353 0, /* properties_provided */
3354 0, /* properties_destroyed */
3355 0, /* todo_flags_start */
3356 TODO_df_finish
, /* todo_flags_finish */
3359 class pass_sms
: public rtl_opt_pass
3362 pass_sms (gcc::context
*ctxt
)
3363 : rtl_opt_pass (pass_data_sms
, ctxt
)
3366 /* opt_pass methods: */
3367 virtual bool gate (function
*)
3369 return (optimize
> 0 && flag_modulo_sched
);
3372 virtual unsigned int execute (function
*);
3374 }; // class pass_sms
3377 pass_sms::execute (function
*fun ATTRIBUTE_UNUSED
)
3379 #ifdef INSN_SCHEDULING
3382 /* Collect loop information to be used in SMS. */
3383 cfg_layout_initialize (0);
3386 /* Update the life information, because we add pseudos. */
3387 max_regno
= max_reg_num ();
3389 /* Finalize layout changes. */
3390 FOR_EACH_BB_FN (bb
, fun
)
3391 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3392 bb
->aux
= bb
->next_bb
;
3393 free_dominance_info (CDI_DOMINATORS
);
3394 cfg_layout_finalize ();
3395 #endif /* INSN_SCHEDULING */
3402 make_pass_sms (gcc::context
*ctxt
)
3404 return new pass_sms (ctxt
);