1 /* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004-2015 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"
54 #include "double-int.h"
61 #include "insn-codes.h"
69 #include "tree-pass.h"
71 #include "loop-unroll.h"
73 #ifdef INSN_SCHEDULING
75 /* This file contains the implementation of the Swing Modulo Scheduler,
76 described in the following references:
77 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
78 Lifetime--sensitive modulo scheduling in a production environment.
79 IEEE Trans. on Comps., 50(3), March 2001
80 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
81 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
82 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
84 The basic structure is:
85 1. Build a data-dependence graph (DDG) for each loop.
86 2. Use the DDG to order the insns of a loop (not in topological order
87 necessarily, but rather) trying to place each insn after all its
88 predecessors _or_ after all its successors.
89 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
90 4. Use the ordering to perform list-scheduling of the loop:
91 1. Set II = MII. We will try to schedule the loop within II cycles.
92 2. Try to schedule the insns one by one according to the ordering.
93 For each insn compute an interval of cycles by considering already-
94 scheduled preds and succs (and associated latencies); try to place
95 the insn in the cycles of this window checking for potential
96 resource conflicts (using the DFA interface).
97 Note: this is different from the cycle-scheduling of schedule_insns;
98 here the insns are not scheduled monotonically top-down (nor bottom-
100 3. If failed in scheduling all insns - bump II++ and try again, unless
101 II reaches an upper bound MaxII, in which case report failure.
102 5. If we succeeded in scheduling the loop within II cycles, we now
103 generate prolog and epilog, decrease the counter of the loop, and
104 perform modulo variable expansion for live ranges that span more than
105 II cycles (i.e. use register copies to prevent a def from overwriting
106 itself before reaching the use).
108 SMS works with countable loops (1) whose control part can be easily
109 decoupled from the rest of the loop and (2) whose loop count can
110 be easily adjusted. This is because we peel a constant number of
111 iterations into a prologue and epilogue for which we want to avoid
112 emitting the control part, and a kernel which is to iterate that
113 constant number of iterations less than the original loop. So the
114 control part should be a set of insns clearly identified and having
115 its own iv, not otherwise used in the loop (at-least for now), which
116 initializes a register before the loop to the number of iterations.
117 Currently SMS relies on the do-loop pattern to recognize such loops,
118 where (1) the control part comprises of all insns defining and/or
119 using a certain 'count' register and (2) the loop count can be
120 adjusted by modifying this register prior to the loop.
121 TODO: Rely on cfgloop analysis instead. */
123 /* This page defines partial-schedule structures and functions for
124 modulo scheduling. */
126 typedef struct partial_schedule
*partial_schedule_ptr
;
127 typedef struct ps_insn
*ps_insn_ptr
;
129 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
130 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
132 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
133 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
135 /* Perform signed modulo, always returning a non-negative value. */
136 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
138 /* The number of different iterations the nodes in ps span, assuming
139 the stage boundaries are placed efficiently. */
140 #define CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \
142 /* The stage count of ps. */
143 #define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count)
145 /* A single instruction in the partial schedule. */
148 /* Identifies the instruction to be scheduled. Values smaller than
149 the ddg's num_nodes refer directly to ddg nodes. A value of
150 X - num_nodes refers to register move X. */
153 /* The (absolute) cycle in which the PS instruction is scheduled.
154 Same as SCHED_TIME (node). */
157 /* The next/prev PS_INSN in the same row. */
158 ps_insn_ptr next_in_row
,
163 /* Information about a register move that has been added to a partial
165 struct ps_reg_move_info
167 /* The source of the move is defined by the ps_insn with id DEF.
168 The destination is used by the ps_insns with the ids in USES. */
172 /* The original form of USES' instructions used OLD_REG, but they
173 should now use NEW_REG. */
177 /* The number of consecutive stages that the move occupies. */
178 int num_consecutive_stages
;
180 /* An instruction that sets NEW_REG to the correct value. The first
181 move associated with DEF will have an rhs of OLD_REG; later moves
182 use the result of the previous move. */
186 typedef struct ps_reg_move_info ps_reg_move_info
;
188 /* Holds the partial schedule as an array of II rows. Each entry of the
189 array points to a linked list of PS_INSNs, which represents the
190 instructions that are scheduled for that row. */
191 struct partial_schedule
193 int ii
; /* Number of rows in the partial schedule. */
194 int history
; /* Threshold for conflict checking using DFA. */
196 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
199 /* All the moves added for this partial schedule. Index X has
200 a ps_insn id of X + g->num_nodes. */
201 vec
<ps_reg_move_info
> reg_moves
;
203 /* rows_length[i] holds the number of instructions in the row.
204 It is used only (as an optimization) to back off quickly from
205 trying to schedule a node in a full row; that is, to avoid running
206 through futile DFA state transitions. */
209 /* The earliest absolute cycle of an insn in the partial schedule. */
212 /* The latest absolute cycle of an insn in the partial schedule. */
215 ddg_ptr g
; /* The DDG of the insns in the partial schedule. */
217 int stage_count
; /* The stage count of the partial schedule. */
221 static partial_schedule_ptr
create_partial_schedule (int ii
, ddg_ptr
, int history
);
222 static void free_partial_schedule (partial_schedule_ptr
);
223 static void reset_partial_schedule (partial_schedule_ptr
, int new_ii
);
224 void print_partial_schedule (partial_schedule_ptr
, FILE *);
225 static void verify_partial_schedule (partial_schedule_ptr
, sbitmap
);
226 static ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr
,
227 int, int, sbitmap
, sbitmap
);
228 static void rotate_partial_schedule (partial_schedule_ptr
, int);
229 void set_row_column_for_ps (partial_schedule_ptr
);
230 static void ps_insert_empty_row (partial_schedule_ptr
, int, sbitmap
);
231 static int compute_split_row (sbitmap
, int, int, int, ddg_node_ptr
);
234 /* This page defines constants and structures for the modulo scheduling
237 static int sms_order_nodes (ddg_ptr
, int, int *, int *);
238 static void set_node_sched_params (ddg_ptr
);
239 static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr
, int, int, int *);
240 static void permute_partial_schedule (partial_schedule_ptr
, rtx_insn
*);
241 static void generate_prolog_epilog (partial_schedule_ptr
, struct loop
*,
243 static int calculate_stage_count (partial_schedule_ptr
, int);
244 static void calculate_must_precede_follow (ddg_node_ptr
, int, int,
245 int, int, sbitmap
, sbitmap
, sbitmap
);
246 static int get_sched_window (partial_schedule_ptr
, ddg_node_ptr
,
247 sbitmap
, int, int *, int *, int *);
248 static bool try_scheduling_node_in_cycle (partial_schedule_ptr
, int, int,
249 sbitmap
, int *, sbitmap
, sbitmap
);
250 static void remove_node_from_ps (partial_schedule_ptr
, ps_insn_ptr
);
252 #define NODE_ASAP(node) ((node)->aux.count)
254 #define SCHED_PARAMS(x) (&node_sched_param_vec[x])
255 #define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
256 #define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
257 #define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
258 #define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
260 /* The scheduling parameters held for each node. */
261 typedef struct node_sched_params
263 int time
; /* The absolute scheduling cycle. */
265 int row
; /* Holds time % ii. */
266 int stage
; /* Holds time / ii. */
268 /* The column of a node inside the ps. If nodes u, v are on the same row,
269 u will precede v if column (u) < column (v). */
271 } *node_sched_params_ptr
;
273 typedef struct node_sched_params node_sched_params
;
275 /* The following three functions are copied from the current scheduler
276 code in order to use sched_analyze() for computing the dependencies.
277 They are used when initializing the sched_info structure. */
279 sms_print_insn (const rtx_insn
*insn
, int aligned ATTRIBUTE_UNUSED
)
283 sprintf (tmp
, "i%4d", INSN_UID (insn
));
288 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
289 regset used ATTRIBUTE_UNUSED
)
293 static struct common_sched_info_def sms_common_sched_info
;
295 static struct sched_deps_info_def sms_sched_deps_info
=
297 compute_jump_reg_dependencies
,
298 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
303 static struct haifa_sched_info sms_sched_info
=
312 NULL
, /* insn_finishes_block_p */
317 NULL
, NULL
, NULL
, NULL
,
322 /* Partial schedule instruction ID in PS is a register move. Return
323 information about it. */
324 static struct ps_reg_move_info
*
325 ps_reg_move (partial_schedule_ptr ps
, int id
)
327 gcc_checking_assert (id
>= ps
->g
->num_nodes
);
328 return &ps
->reg_moves
[id
- ps
->g
->num_nodes
];
331 /* Return the rtl instruction that is being scheduled by partial schedule
332 instruction ID, which belongs to schedule PS. */
334 ps_rtl_insn (partial_schedule_ptr ps
, int id
)
336 if (id
< ps
->g
->num_nodes
)
337 return ps
->g
->nodes
[id
].insn
;
339 return ps_reg_move (ps
, id
)->insn
;
342 /* Partial schedule instruction ID, which belongs to PS, occurred in
343 the original (unscheduled) loop. Return the first instruction
344 in the loop that was associated with ps_rtl_insn (PS, ID).
345 If the instruction had some notes before it, this is the first
348 ps_first_note (partial_schedule_ptr ps
, int id
)
350 gcc_assert (id
< ps
->g
->num_nodes
);
351 return ps
->g
->nodes
[id
].first_note
;
354 /* Return the number of consecutive stages that are occupied by
355 partial schedule instruction ID in PS. */
357 ps_num_consecutive_stages (partial_schedule_ptr ps
, int id
)
359 if (id
< ps
->g
->num_nodes
)
362 return ps_reg_move (ps
, id
)->num_consecutive_stages
;
365 /* Given HEAD and TAIL which are the first and last insns in a loop;
366 return the register which controls the loop. Return zero if it has
367 more than one occurrence in the loop besides the control part or the
368 do-loop pattern is not of the form we expect. */
370 doloop_register_get (rtx_insn
*head ATTRIBUTE_UNUSED
, rtx_insn
*tail ATTRIBUTE_UNUSED
)
372 #ifdef HAVE_doloop_end
374 rtx_insn
*insn
, *first_insn_not_to_check
;
379 /* TODO: Free SMS's dependence on doloop_condition_get. */
380 condition
= doloop_condition_get (tail
);
384 if (REG_P (XEXP (condition
, 0)))
385 reg
= XEXP (condition
, 0);
386 else if (GET_CODE (XEXP (condition
, 0)) == PLUS
387 && REG_P (XEXP (XEXP (condition
, 0), 0)))
388 reg
= XEXP (XEXP (condition
, 0), 0);
392 /* Check that the COUNT_REG has no other occurrences in the loop
393 until the decrement. We assume the control part consists of
394 either a single (parallel) branch-on-count or a (non-parallel)
395 branch immediately preceded by a single (decrement) insn. */
396 first_insn_not_to_check
= (GET_CODE (PATTERN (tail
)) == PARALLEL
? tail
397 : prev_nondebug_insn (tail
));
399 for (insn
= head
; insn
!= first_insn_not_to_check
; insn
= NEXT_INSN (insn
))
400 if (!DEBUG_INSN_P (insn
) && reg_mentioned_p (reg
, insn
))
404 fprintf (dump_file
, "SMS count_reg found ");
405 print_rtl_single (dump_file
, reg
);
406 fprintf (dump_file
, " outside control in insn:\n");
407 print_rtl_single (dump_file
, insn
);
419 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
420 that the number of iterations is a compile-time constant. If so,
421 return the rtx_insn that sets COUNT_REG to a constant, and set COUNT to
422 this constant. Otherwise return 0. */
424 const_iteration_count (rtx count_reg
, basic_block pre_header
,
428 rtx_insn
*head
, *tail
;
433 get_ebb_head_tail (pre_header
, pre_header
, &head
, &tail
);
435 for (insn
= tail
; insn
!= PREV_INSN (head
); insn
= PREV_INSN (insn
))
436 if (NONDEBUG_INSN_P (insn
) && single_set (insn
) &&
437 rtx_equal_p (count_reg
, SET_DEST (single_set (insn
))))
439 rtx pat
= single_set (insn
);
441 if (CONST_INT_P (SET_SRC (pat
)))
443 *count
= INTVAL (SET_SRC (pat
));
453 /* A very simple resource-based lower bound on the initiation interval.
454 ??? Improve the accuracy of this bound by considering the
455 utilization of various units. */
459 if (targetm
.sched
.sms_res_mii
)
460 return targetm
.sched
.sms_res_mii (g
);
462 return ((g
->num_nodes
- g
->num_debug
) / issue_rate
);
466 /* A vector that contains the sched data for each ps_insn. */
467 static vec
<node_sched_params
> node_sched_param_vec
;
469 /* Allocate sched_params for each node and initialize it. */
471 set_node_sched_params (ddg_ptr g
)
473 node_sched_param_vec
.truncate (0);
474 node_sched_param_vec
.safe_grow_cleared (g
->num_nodes
);
477 /* Make sure that node_sched_param_vec has an entry for every move in PS. */
479 extend_node_sched_params (partial_schedule_ptr ps
)
481 node_sched_param_vec
.safe_grow_cleared (ps
->g
->num_nodes
482 + ps
->reg_moves
.length ());
485 /* Update the sched_params (time, row and stage) for node U using the II,
486 the CYCLE of U and MIN_CYCLE.
487 We're not simply taking the following
488 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
489 because the stages may not be aligned on cycle 0. */
491 update_node_sched_params (int u
, int ii
, int cycle
, int min_cycle
)
493 int sc_until_cycle_zero
;
496 SCHED_TIME (u
) = cycle
;
497 SCHED_ROW (u
) = SMODULO (cycle
, ii
);
499 /* The calculation of stage count is done adding the number
500 of stages before cycle zero and after cycle zero. */
501 sc_until_cycle_zero
= CALC_STAGE_COUNT (-1, min_cycle
, ii
);
503 if (SCHED_TIME (u
) < 0)
505 stage
= CALC_STAGE_COUNT (-1, SCHED_TIME (u
), ii
);
506 SCHED_STAGE (u
) = sc_until_cycle_zero
- stage
;
510 stage
= CALC_STAGE_COUNT (SCHED_TIME (u
), 0, ii
);
511 SCHED_STAGE (u
) = sc_until_cycle_zero
+ stage
- 1;
516 print_node_sched_params (FILE *file
, int num_nodes
, partial_schedule_ptr ps
)
522 for (i
= 0; i
< num_nodes
; i
++)
524 node_sched_params_ptr nsp
= SCHED_PARAMS (i
);
526 fprintf (file
, "Node = %d; INSN = %d\n", i
,
527 INSN_UID (ps_rtl_insn (ps
, i
)));
528 fprintf (file
, " asap = %d:\n", NODE_ASAP (&ps
->g
->nodes
[i
]));
529 fprintf (file
, " time = %d:\n", nsp
->time
);
530 fprintf (file
, " stage = %d:\n", nsp
->stage
);
534 /* Set SCHED_COLUMN for each instruction in row ROW of PS. */
536 set_columns_for_row (partial_schedule_ptr ps
, int row
)
538 ps_insn_ptr cur_insn
;
542 for (cur_insn
= ps
->rows
[row
]; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
543 SCHED_COLUMN (cur_insn
->id
) = column
++;
546 /* Set SCHED_COLUMN for each instruction in PS. */
548 set_columns_for_ps (partial_schedule_ptr ps
)
552 for (row
= 0; row
< ps
->ii
; row
++)
553 set_columns_for_row (ps
, row
);
556 /* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
557 Its single predecessor has already been scheduled, as has its
558 ddg node successors. (The move may have also another move as its
559 successor, in which case that successor will be scheduled later.)
561 The move is part of a chain that satisfies register dependencies
562 between a producing ddg node and various consuming ddg nodes.
563 If some of these dependencies have a distance of 1 (meaning that
564 the use is upward-exposed) then DISTANCE1_USES is nonnull and
565 contains the set of uses with distance-1 dependencies.
566 DISTANCE1_USES is null otherwise.
568 MUST_FOLLOW is a scratch bitmap that is big enough to hold
569 all current ps_insn ids.
571 Return true on success. */
573 schedule_reg_move (partial_schedule_ptr ps
, int i_reg_move
,
574 sbitmap distance1_uses
, sbitmap must_follow
)
577 int this_time
, this_distance
, this_start
, this_end
, this_latency
;
578 int start
, end
, c
, ii
;
579 sbitmap_iterator sbi
;
580 ps_reg_move_info
*move
;
584 move
= ps_reg_move (ps
, i_reg_move
);
588 fprintf (dump_file
, "Scheduling register move INSN %d; ii = %d"
589 ", min cycle = %d\n\n", INSN_UID (move
->insn
), ii
,
591 print_rtl_single (dump_file
, move
->insn
);
592 fprintf (dump_file
, "\n%11s %11s %5s\n", "start", "end", "time");
593 fprintf (dump_file
, "=========== =========== =====\n");
599 /* For dependencies of distance 1 between a producer ddg node A
600 and consumer ddg node B, we have a chain of dependencies:
602 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
604 where Mi is the ith move. For dependencies of distance 0 between
605 a producer ddg node A and consumer ddg node C, we have a chain of
608 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
610 where Mi' occupies the same position as Mi but occurs a stage later.
611 We can only schedule each move once, so if we have both types of
612 chain, we model the second as:
614 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
616 First handle the dependencies between the previously-scheduled
617 predecessor and the move. */
618 this_insn
= ps_rtl_insn (ps
, move
->def
);
619 this_latency
= insn_latency (this_insn
, move
->insn
);
620 this_distance
= distance1_uses
&& move
->def
< ps
->g
->num_nodes
? 1 : 0;
621 this_time
= SCHED_TIME (move
->def
) - this_distance
* ii
;
622 this_start
= this_time
+ this_latency
;
623 this_end
= this_time
+ ii
;
625 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
626 this_start
, this_end
, SCHED_TIME (move
->def
),
627 INSN_UID (this_insn
), this_latency
, this_distance
,
628 INSN_UID (move
->insn
));
630 if (start
< this_start
)
635 /* Handle the dependencies between the move and previously-scheduled
637 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, u
, sbi
)
639 this_insn
= ps_rtl_insn (ps
, u
);
640 this_latency
= insn_latency (move
->insn
, this_insn
);
641 if (distance1_uses
&& !bitmap_bit_p (distance1_uses
, u
))
645 this_time
= SCHED_TIME (u
) + this_distance
* ii
;
646 this_start
= this_time
- ii
;
647 this_end
= this_time
- this_latency
;
649 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
650 this_start
, this_end
, SCHED_TIME (u
), INSN_UID (move
->insn
),
651 this_latency
, this_distance
, INSN_UID (this_insn
));
653 if (start
< this_start
)
661 fprintf (dump_file
, "----------- ----------- -----\n");
662 fprintf (dump_file
, "%11d %11d %5s %s\n", start
, end
, "", "(max, min)");
665 bitmap_clear (must_follow
);
666 bitmap_set_bit (must_follow
, move
->def
);
668 start
= MAX (start
, end
- (ii
- 1));
669 for (c
= end
; c
>= start
; c
--)
671 psi
= ps_add_node_check_conflicts (ps
, i_reg_move
, c
,
672 move
->uses
, must_follow
);
675 update_node_sched_params (i_reg_move
, ii
, c
, PS_MIN_CYCLE (ps
));
677 fprintf (dump_file
, "\nScheduled register move INSN %d at"
678 " time %d, row %d\n\n", INSN_UID (move
->insn
), c
,
679 SCHED_ROW (i_reg_move
));
685 fprintf (dump_file
, "\nNo available slot\n\n");
691 Breaking intra-loop register anti-dependences:
692 Each intra-loop register anti-dependence implies a cross-iteration true
693 dependence of distance 1. Therefore, we can remove such false dependencies
694 and figure out if the partial schedule broke them by checking if (for a
695 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
696 if so generate a register move. The number of such moves is equal to:
697 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
698 nreg_moves = ----------------------------------- + 1 - { dependence.
702 schedule_reg_moves (partial_schedule_ptr ps
)
708 for (i
= 0; i
< g
->num_nodes
; i
++)
710 ddg_node_ptr u
= &g
->nodes
[i
];
712 int nreg_moves
= 0, i_reg_move
;
713 rtx prev_reg
, old_reg
;
717 sbitmap distance1_uses
;
718 rtx set
= single_set (u
->insn
);
720 /* Skip instructions that do not set a register. */
721 if ((set
&& !REG_P (SET_DEST (set
))))
724 /* Compute the number of reg_moves needed for u, by looking at life
725 ranges started at u (excluding self-loops). */
726 distances
[0] = distances
[1] = false;
727 for (e
= u
->out
; e
; e
= e
->next_out
)
728 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
730 int nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
731 - SCHED_TIME (e
->src
->cuid
)) / ii
;
733 if (e
->distance
== 1)
734 nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
735 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
737 /* If dest precedes src in the schedule of the kernel, then dest
738 will read before src writes and we can save one reg_copy. */
739 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
740 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
743 if (nreg_moves4e
>= 1)
745 /* !single_set instructions are not supported yet and
746 thus we do not except to encounter them in the loop
747 except from the doloop part. For the latter case
748 we assume no regmoves are generated as the doloop
749 instructions are tied to the branch with an edge. */
751 /* If the instruction contains auto-inc register then
752 validate that the regmov is being generated for the
753 target regsiter rather then the inc'ed register. */
754 gcc_assert (!autoinc_var_is_used_p (u
->insn
, e
->dest
->insn
));
759 gcc_assert (e
->distance
< 2);
760 distances
[e
->distance
] = true;
762 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
768 /* Create NREG_MOVES register moves. */
769 first_move
= ps
->reg_moves
.length ();
770 ps
->reg_moves
.safe_grow_cleared (first_move
+ nreg_moves
);
771 extend_node_sched_params (ps
);
773 /* Record the moves associated with this node. */
774 first_move
+= ps
->g
->num_nodes
;
776 /* Generate each move. */
777 old_reg
= prev_reg
= SET_DEST (single_set (u
->insn
));
778 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
780 ps_reg_move_info
*move
= ps_reg_move (ps
, first_move
+ i_reg_move
);
782 move
->def
= i_reg_move
> 0 ? first_move
+ i_reg_move
- 1 : i
;
783 move
->uses
= sbitmap_alloc (first_move
+ nreg_moves
);
784 move
->old_reg
= old_reg
;
785 move
->new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
786 move
->num_consecutive_stages
= distances
[0] && distances
[1] ? 2 : 1;
787 move
->insn
= as_a
<rtx_insn
*> (gen_move_insn (move
->new_reg
,
788 copy_rtx (prev_reg
)));
789 bitmap_clear (move
->uses
);
791 prev_reg
= move
->new_reg
;
794 distance1_uses
= distances
[1] ? sbitmap_alloc (g
->num_nodes
) : NULL
;
797 bitmap_clear (distance1_uses
);
799 /* Every use of the register defined by node may require a different
800 copy of this register, depending on the time the use is scheduled.
801 Record which uses require which move results. */
802 for (e
= u
->out
; e
; e
= e
->next_out
)
803 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
805 int dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
806 - SCHED_TIME (e
->src
->cuid
)) / ii
;
808 if (e
->distance
== 1)
809 dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
810 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
812 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
813 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
818 ps_reg_move_info
*move
;
820 move
= ps_reg_move (ps
, first_move
+ dest_copy
- 1);
821 bitmap_set_bit (move
->uses
, e
->dest
->cuid
);
822 if (e
->distance
== 1)
823 bitmap_set_bit (distance1_uses
, e
->dest
->cuid
);
827 must_follow
= sbitmap_alloc (first_move
+ nreg_moves
);
828 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
829 if (!schedule_reg_move (ps
, first_move
+ i_reg_move
,
830 distance1_uses
, must_follow
))
832 sbitmap_free (must_follow
);
834 sbitmap_free (distance1_uses
);
835 if (i_reg_move
< nreg_moves
)
841 /* Emit the moves associatied with PS. Apply the substitutions
842 associated with them. */
844 apply_reg_moves (partial_schedule_ptr ps
)
846 ps_reg_move_info
*move
;
849 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
852 sbitmap_iterator sbi
;
854 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, i_use
, sbi
)
856 replace_rtx (ps
->g
->nodes
[i_use
].insn
, move
->old_reg
, move
->new_reg
);
857 df_insn_rescan (ps
->g
->nodes
[i_use
].insn
);
862 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
863 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
864 will move to cycle zero. */
866 reset_sched_times (partial_schedule_ptr ps
, int amount
)
870 ps_insn_ptr crr_insn
;
872 for (row
= 0; row
< ii
; row
++)
873 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
875 int u
= crr_insn
->id
;
876 int normalized_time
= SCHED_TIME (u
) - amount
;
877 int new_min_cycle
= PS_MIN_CYCLE (ps
) - amount
;
881 /* Print the scheduling times after the rotation. */
882 rtx_insn
*insn
= ps_rtl_insn (ps
, u
);
884 fprintf (dump_file
, "crr_insn->node=%d (insn id %d), "
885 "crr_insn->cycle=%d, min_cycle=%d", u
,
886 INSN_UID (insn
), normalized_time
, new_min_cycle
);
888 fprintf (dump_file
, " (branch)");
889 fprintf (dump_file
, "\n");
892 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
893 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
895 crr_insn
->cycle
= normalized_time
;
896 update_node_sched_params (u
, ii
, normalized_time
, new_min_cycle
);
900 /* Permute the insns according to their order in PS, from row 0 to
901 row ii-1, and position them right before LAST. This schedules
902 the insns of the loop kernel. */
904 permute_partial_schedule (partial_schedule_ptr ps
, rtx_insn
*last
)
910 for (row
= 0; row
< ii
; row
++)
911 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
913 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_ij
->id
);
915 if (PREV_INSN (last
) != insn
)
917 if (ps_ij
->id
< ps
->g
->num_nodes
)
918 reorder_insns_nobb (ps_first_note (ps
, ps_ij
->id
), insn
,
921 add_insn_before (insn
, last
, NULL
);
926 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
927 respectively only if cycle C falls on the border of the scheduling
928 window boundaries marked by START and END cycles. STEP is the
929 direction of the window. */
931 set_must_precede_follow (sbitmap
*tmp_follow
, sbitmap must_follow
,
932 sbitmap
*tmp_precede
, sbitmap must_precede
, int c
,
933 int start
, int end
, int step
)
941 *tmp_precede
= must_precede
;
942 else /* step == -1. */
943 *tmp_follow
= must_follow
;
948 *tmp_follow
= must_follow
;
949 else /* step == -1. */
950 *tmp_precede
= must_precede
;
955 /* Return True if the branch can be moved to row ii-1 while
956 normalizing the partial schedule PS to start from cycle zero and thus
957 optimize the SC. Otherwise return False. */
959 optimize_sc (partial_schedule_ptr ps
, ddg_ptr g
)
961 int amount
= PS_MIN_CYCLE (ps
);
962 sbitmap sched_nodes
= sbitmap_alloc (g
->num_nodes
);
963 int start
, end
, step
;
966 int stage_count
, stage_count_curr
;
968 /* Compare the SC after normalization and SC after bringing the branch
969 to row ii-1. If they are equal just bail out. */
970 stage_count
= calculate_stage_count (ps
, amount
);
972 calculate_stage_count (ps
, SCHED_TIME (g
->closing_branch
->cuid
) - (ii
- 1));
974 if (stage_count
== stage_count_curr
)
977 fprintf (dump_file
, "SMS SC already optimized.\n");
985 fprintf (dump_file
, "SMS Trying to optimize branch location\n");
986 fprintf (dump_file
, "SMS partial schedule before trial:\n");
987 print_partial_schedule (ps
, dump_file
);
990 /* First, normalize the partial scheduling. */
991 reset_sched_times (ps
, amount
);
992 rotate_partial_schedule (ps
, amount
);
996 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
998 print_partial_schedule (ps
, dump_file
);
1001 if (SMODULO (SCHED_TIME (g
->closing_branch
->cuid
), ii
) == ii
- 1)
1007 bitmap_ones (sched_nodes
);
1009 /* Calculate the new placement of the branch. It should be in row
1010 ii-1 and fall into it's scheduling window. */
1011 if (get_sched_window (ps
, g
->closing_branch
, sched_nodes
, ii
, &start
,
1015 ps_insn_ptr next_ps_i
;
1016 int branch_cycle
= SCHED_TIME (g
->closing_branch
->cuid
);
1017 int row
= SMODULO (branch_cycle
, ps
->ii
);
1019 sbitmap must_precede
, must_follow
, tmp_precede
, tmp_follow
;
1023 fprintf (dump_file
, "\nTrying to schedule node %d "
1024 "INSN = %d in (%d .. %d) step %d\n",
1025 g
->closing_branch
->cuid
,
1026 (INSN_UID (g
->closing_branch
->insn
)), start
, end
, step
);
1028 gcc_assert ((step
> 0 && start
< end
) || (step
< 0 && start
> end
));
1031 c
= start
+ ii
- SMODULO (start
, ii
) - 1;
1032 gcc_assert (c
>= start
);
1038 "SMS failed to schedule branch at cycle: %d\n", c
);
1044 c
= start
- SMODULO (start
, ii
) - 1;
1045 gcc_assert (c
<= start
);
1051 "SMS failed to schedule branch at cycle: %d\n", c
);
1057 must_precede
= sbitmap_alloc (g
->num_nodes
);
1058 must_follow
= sbitmap_alloc (g
->num_nodes
);
1060 /* Try to schedule the branch is it's new cycle. */
1061 calculate_must_precede_follow (g
->closing_branch
, start
, end
,
1062 step
, ii
, sched_nodes
,
1063 must_precede
, must_follow
);
1065 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1066 must_precede
, c
, start
, end
, step
);
1068 /* Find the element in the partial schedule related to the closing
1069 branch so we can remove it from it's current cycle. */
1070 for (next_ps_i
= ps
->rows
[row
];
1071 next_ps_i
; next_ps_i
= next_ps_i
->next_in_row
)
1072 if (next_ps_i
->id
== g
->closing_branch
->cuid
)
1075 remove_node_from_ps (ps
, next_ps_i
);
1077 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
, c
,
1078 sched_nodes
, &num_splits
,
1079 tmp_precede
, tmp_follow
);
1080 gcc_assert (num_splits
== 0);
1085 "SMS failed to schedule branch at cycle: %d, "
1086 "bringing it back to cycle %d\n", c
, branch_cycle
);
1088 /* The branch was failed to be placed in row ii - 1.
1089 Put it back in it's original place in the partial
1091 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1092 must_precede
, branch_cycle
, start
, end
,
1095 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
,
1096 branch_cycle
, sched_nodes
,
1097 &num_splits
, tmp_precede
,
1099 gcc_assert (success
&& (num_splits
== 0));
1104 /* The branch is placed in row ii - 1. */
1107 "SMS success in moving branch to cycle %d\n", c
);
1109 update_node_sched_params (g
->closing_branch
->cuid
, ii
, c
,
1114 free (must_precede
);
1124 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
1125 int to_stage
, rtx count_reg
)
1130 for (row
= 0; row
< ps
->ii
; row
++)
1131 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
1134 int first_u
, last_u
;
1137 /* Do not duplicate any insn which refers to count_reg as it
1138 belongs to the control part.
1139 The closing branch is scheduled as well and thus should
1141 TODO: This should be done by analyzing the control part of
1143 u_insn
= ps_rtl_insn (ps
, u
);
1144 if (reg_mentioned_p (count_reg
, u_insn
)
1148 first_u
= SCHED_STAGE (u
);
1149 last_u
= first_u
+ ps_num_consecutive_stages (ps
, u
) - 1;
1150 if (from_stage
<= last_u
&& to_stage
>= first_u
)
1152 if (u
< ps
->g
->num_nodes
)
1153 duplicate_insn_chain (ps_first_note (ps
, u
), u_insn
);
1155 emit_insn (copy_rtx (PATTERN (u_insn
)));
1161 /* Generate the instructions (including reg_moves) for prolog & epilog. */
1163 generate_prolog_epilog (partial_schedule_ptr ps
, struct loop
*loop
,
1164 rtx count_reg
, rtx count_init
)
1167 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
1170 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1175 /* Generate instructions at the beginning of the prolog to
1176 adjust the loop count by STAGE_COUNT. If loop count is constant
1177 (count_init), this constant is adjusted by STAGE_COUNT in
1178 generate_prolog_epilog function. */
1179 rtx sub_reg
= NULL_RTX
;
1181 sub_reg
= expand_simple_binop (GET_MODE (count_reg
), MINUS
, count_reg
,
1182 gen_int_mode (last_stage
,
1183 GET_MODE (count_reg
)),
1184 count_reg
, 1, OPTAB_DIRECT
);
1185 gcc_assert (REG_P (sub_reg
));
1186 if (REGNO (sub_reg
) != REGNO (count_reg
))
1187 emit_move_insn (count_reg
, sub_reg
);
1190 for (i
= 0; i
< last_stage
; i
++)
1191 duplicate_insns_of_cycles (ps
, 0, i
, count_reg
);
1193 /* Put the prolog on the entry edge. */
1194 e
= loop_preheader_edge (loop
);
1195 split_edge_and_insert (e
, get_insns ());
1196 if (!flag_resched_modulo_sched
)
1197 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1201 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1204 for (i
= 0; i
< last_stage
; i
++)
1205 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, count_reg
);
1207 /* Put the epilogue on the exit edge. */
1208 gcc_assert (single_exit (loop
));
1209 e
= single_exit (loop
);
1210 split_edge_and_insert (e
, get_insns ());
1211 if (!flag_resched_modulo_sched
)
1212 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1217 /* Mark LOOP as software pipelined so the later
1218 scheduling passes don't touch it. */
1220 mark_loop_unsched (struct loop
*loop
)
1223 basic_block
*bbs
= get_loop_body (loop
);
1225 for (i
= 0; i
< loop
->num_nodes
; i
++)
1226 bbs
[i
]->flags
|= BB_DISABLE_SCHEDULE
;
1231 /* Return true if all the BBs of the loop are empty except the
1234 loop_single_full_bb_p (struct loop
*loop
)
1237 basic_block
*bbs
= get_loop_body (loop
);
1239 for (i
= 0; i
< loop
->num_nodes
; i
++)
1241 rtx_insn
*head
, *tail
;
1242 bool empty_bb
= true;
1244 if (bbs
[i
] == loop
->header
)
1247 /* Make sure that basic blocks other than the header
1248 have only notes labels or jumps. */
1249 get_ebb_head_tail (bbs
[i
], bbs
[i
], &head
, &tail
);
1250 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
1252 if (NOTE_P (head
) || LABEL_P (head
)
1253 || (INSN_P (head
) && (DEBUG_INSN_P (head
) || JUMP_P (head
))))
1269 /* Dump file:line from INSN's location info to dump_file. */
1272 dump_insn_location (rtx_insn
*insn
)
1274 if (dump_file
&& INSN_HAS_LOCATION (insn
))
1276 expanded_location xloc
= insn_location (insn
);
1277 fprintf (dump_file
, " %s:%i", xloc
.file
, xloc
.line
);
1281 /* A simple loop from SMS point of view; it is a loop that is composed of
1282 either a single basic block or two BBs - a header and a latch. */
1283 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1284 && (EDGE_COUNT (loop->latch->preds) == 1) \
1285 && (EDGE_COUNT (loop->latch->succs) == 1))
1287 /* Return true if the loop is in its canonical form and false if not.
1288 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1290 loop_canon_p (struct loop
*loop
)
1293 if (loop
->inner
|| !loop_outer (loop
))
1296 fprintf (dump_file
, "SMS loop inner or !loop_outer\n");
1300 if (!single_exit (loop
))
1304 rtx_insn
*insn
= BB_END (loop
->header
);
1306 fprintf (dump_file
, "SMS loop many exits");
1307 dump_insn_location (insn
);
1308 fprintf (dump_file
, "\n");
1313 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
1317 rtx_insn
*insn
= BB_END (loop
->header
);
1319 fprintf (dump_file
, "SMS loop many BBs.");
1320 dump_insn_location (insn
);
1321 fprintf (dump_file
, "\n");
1329 /* If there are more than one entry for the loop,
1330 make it one by splitting the first entry edge and
1331 redirecting the others to the new BB. */
1333 canon_loop (struct loop
*loop
)
1338 /* Avoid annoying special cases of edges going to exit
1340 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1341 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
1344 if (loop
->latch
== loop
->header
1345 || EDGE_COUNT (loop
->latch
->succs
) > 1)
1347 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
1348 if (e
->src
== loop
->latch
)
1356 setup_sched_infos (void)
1358 memcpy (&sms_common_sched_info
, &haifa_common_sched_info
,
1359 sizeof (sms_common_sched_info
));
1360 sms_common_sched_info
.sched_pass_id
= SCHED_SMS_PASS
;
1361 common_sched_info
= &sms_common_sched_info
;
1363 sched_deps_info
= &sms_sched_deps_info
;
1364 current_sched_info
= &sms_sched_info
;
1367 /* Probability in % that the sms-ed loop rolls enough so that optimized
1368 version may be entered. Just a guess. */
1369 #define PROB_SMS_ENOUGH_ITERATIONS 80
1371 /* Used to calculate the upper bound of ii. */
1372 #define MAXII_FACTOR 2
1374 /* Main entry point, perform SMS scheduling on the loops of the function
1375 that consist of single basic blocks. */
1382 int maxii
, max_asap
;
1383 partial_schedule_ptr ps
;
1384 basic_block bb
= NULL
;
1386 basic_block condition_bb
= NULL
;
1388 gcov_type trip_count
= 0;
1390 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1391 | LOOPS_HAVE_RECORDED_EXITS
);
1392 if (number_of_loops (cfun
) <= 1)
1394 loop_optimizer_finalize ();
1395 return; /* There are no loops to schedule. */
1398 /* Initialize issue_rate. */
1399 if (targetm
.sched
.issue_rate
)
1401 int temp
= reload_completed
;
1403 reload_completed
= 1;
1404 issue_rate
= targetm
.sched
.issue_rate ();
1405 reload_completed
= temp
;
1410 /* Initialize the scheduler. */
1411 setup_sched_infos ();
1412 haifa_sched_init ();
1414 /* Allocate memory to hold the DDG array one entry for each loop.
1415 We use loop->num as index into this array. */
1416 g_arr
= XCNEWVEC (ddg_ptr
, number_of_loops (cfun
));
1420 fprintf (dump_file
, "\n\nSMS analysis phase\n");
1421 fprintf (dump_file
, "===================\n\n");
1424 /* Build DDGs for all the relevant loops and hold them in G_ARR
1425 indexed by the loop index. */
1426 FOR_EACH_LOOP (loop
, 0)
1428 rtx_insn
*head
, *tail
;
1431 /* For debugging. */
1432 if (dbg_cnt (sms_sched_loop
) == false)
1435 fprintf (dump_file
, "SMS reached max limit... \n");
1442 rtx_insn
*insn
= BB_END (loop
->header
);
1444 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1445 dump_insn_location (insn
);
1446 fprintf (dump_file
, "\n");
1449 if (! loop_canon_p (loop
))
1452 if (! loop_single_full_bb_p (loop
))
1455 fprintf (dump_file
, "SMS not loop_single_full_bb_p\n");
1461 get_ebb_head_tail (bb
, bb
, &head
, &tail
);
1462 latch_edge
= loop_latch_edge (loop
);
1463 gcc_assert (single_exit (loop
));
1464 if (single_exit (loop
)->count
)
1465 trip_count
= latch_edge
->count
/ single_exit (loop
)->count
;
1467 /* Perform SMS only on loops that their average count is above threshold. */
1469 if ( latch_edge
->count
1470 && (latch_edge
->count
< single_exit (loop
)->count
* SMS_LOOP_AVERAGE_COUNT_THRESHOLD
))
1474 dump_insn_location (tail
);
1475 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1476 if (profile_info
&& flag_branch_probabilities
)
1478 fprintf (dump_file
, "SMS loop-count ");
1479 fprintf (dump_file
, "%"PRId64
,
1480 (int64_t) bb
->count
);
1481 fprintf (dump_file
, "\n");
1482 fprintf (dump_file
, "SMS trip-count ");
1483 fprintf (dump_file
, "%"PRId64
,
1484 (int64_t) trip_count
);
1485 fprintf (dump_file
, "\n");
1486 fprintf (dump_file
, "SMS profile-sum-max ");
1487 fprintf (dump_file
, "%"PRId64
,
1488 (int64_t) profile_info
->sum_max
);
1489 fprintf (dump_file
, "\n");
1495 /* Make sure this is a doloop. */
1496 if ( !(count_reg
= doloop_register_get (head
, tail
)))
1499 fprintf (dump_file
, "SMS doloop_register_get failed\n");
1503 /* Don't handle BBs with calls or barriers
1504 or !single_set with the exception of instructions that include
1505 count_reg---these instructions are part of the control part
1506 that do-loop recognizes.
1507 ??? Should handle insns defining subregs. */
1508 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1514 || (NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1515 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
1516 && !reg_mentioned_p (count_reg
, insn
))
1517 || (INSN_P (insn
) && (set
= single_set (insn
))
1518 && GET_CODE (SET_DEST (set
)) == SUBREG
))
1522 if (insn
!= NEXT_INSN (tail
))
1527 fprintf (dump_file
, "SMS loop-with-call\n");
1528 else if (BARRIER_P (insn
))
1529 fprintf (dump_file
, "SMS loop-with-barrier\n");
1530 else if ((NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1531 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
1532 fprintf (dump_file
, "SMS loop-with-not-single-set\n");
1534 fprintf (dump_file
, "SMS loop with subreg in lhs\n");
1535 print_rtl_single (dump_file
, insn
);
1541 /* Always schedule the closing branch with the rest of the
1542 instructions. The branch is rotated to be in row ii-1 at the
1543 end of the scheduling procedure to make sure it's the last
1544 instruction in the iteration. */
1545 if (! (g
= create_ddg (bb
, 1)))
1548 fprintf (dump_file
, "SMS create_ddg failed\n");
1552 g_arr
[loop
->num
] = g
;
1554 fprintf (dump_file
, "...OK\n");
1559 fprintf (dump_file
, "\nSMS transformation phase\n");
1560 fprintf (dump_file
, "=========================\n\n");
1563 /* We don't want to perform SMS on new loops - created by versioning. */
1564 FOR_EACH_LOOP (loop
, 0)
1566 rtx_insn
*head
, *tail
;
1568 rtx_insn
*count_init
;
1569 int mii
, rec_mii
, stage_count
, min_cycle
;
1570 int64_t loop_count
= 0;
1573 if (! (g
= g_arr
[loop
->num
]))
1578 rtx_insn
*insn
= BB_END (loop
->header
);
1580 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1581 dump_insn_location (insn
);
1582 fprintf (dump_file
, "\n");
1584 print_ddg (dump_file
, g
);
1587 get_ebb_head_tail (loop
->header
, loop
->header
, &head
, &tail
);
1589 latch_edge
= loop_latch_edge (loop
);
1590 gcc_assert (single_exit (loop
));
1591 if (single_exit (loop
)->count
)
1592 trip_count
= latch_edge
->count
/ single_exit (loop
)->count
;
1596 dump_insn_location (tail
);
1597 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1598 if (profile_info
&& flag_branch_probabilities
)
1600 fprintf (dump_file
, "SMS loop-count ");
1601 fprintf (dump_file
, "%"PRId64
,
1602 (int64_t) bb
->count
);
1603 fprintf (dump_file
, "\n");
1604 fprintf (dump_file
, "SMS profile-sum-max ");
1605 fprintf (dump_file
, "%"PRId64
,
1606 (int64_t) profile_info
->sum_max
);
1607 fprintf (dump_file
, "\n");
1609 fprintf (dump_file
, "SMS doloop\n");
1610 fprintf (dump_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1611 fprintf (dump_file
, "SMS num-loads %d\n", g
->num_loads
);
1612 fprintf (dump_file
, "SMS num-stores %d\n", g
->num_stores
);
1616 /* In case of th loop have doloop register it gets special
1619 if ((count_reg
= doloop_register_get (head
, tail
)))
1621 basic_block pre_header
;
1623 pre_header
= loop_preheader_edge (loop
)->src
;
1624 count_init
= const_iteration_count (count_reg
, pre_header
,
1627 gcc_assert (count_reg
);
1629 if (dump_file
&& count_init
)
1631 fprintf (dump_file
, "SMS const-doloop ");
1632 fprintf (dump_file
, "%"PRId64
,
1634 fprintf (dump_file
, "\n");
1637 node_order
= XNEWVEC (int, g
->num_nodes
);
1639 mii
= 1; /* Need to pass some estimate of mii. */
1640 rec_mii
= sms_order_nodes (g
, mii
, node_order
, &max_asap
);
1641 mii
= MAX (res_MII (g
), rec_mii
);
1642 maxii
= MAX (max_asap
, MAXII_FACTOR
* mii
);
1645 fprintf (dump_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1646 rec_mii
, mii
, maxii
);
1650 set_node_sched_params (g
);
1654 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
);
1658 /* Try to achieve optimized SC by normalizing the partial
1659 schedule (having the cycles start from cycle zero).
1660 The branch location must be placed in row ii-1 in the
1661 final scheduling. If failed, shift all instructions to
1662 position the branch in row ii-1. */
1663 opt_sc_p
= optimize_sc (ps
, g
);
1665 stage_count
= calculate_stage_count (ps
, 0);
1668 /* Bring the branch to cycle ii-1. */
1669 int amount
= (SCHED_TIME (g
->closing_branch
->cuid
)
1673 fprintf (dump_file
, "SMS schedule branch at cycle ii-1\n");
1675 stage_count
= calculate_stage_count (ps
, amount
);
1678 gcc_assert (stage_count
>= 1);
1681 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
1682 1 means that there is no interleaving between iterations thus
1683 we let the scheduling passes do the job in this case. */
1684 if (stage_count
< PARAM_VALUE (PARAM_SMS_MIN_SC
)
1685 || (count_init
&& (loop_count
<= stage_count
))
1686 || (flag_branch_probabilities
&& (trip_count
<= stage_count
)))
1690 fprintf (dump_file
, "SMS failed... \n");
1691 fprintf (dump_file
, "SMS sched-failed (stage-count=%d,"
1692 " loop-count=", stage_count
);
1693 fprintf (dump_file
, "%"PRId64
, loop_count
);
1694 fprintf (dump_file
, ", trip-count=");
1695 fprintf (dump_file
, "%"PRId64
, trip_count
);
1696 fprintf (dump_file
, ")\n");
1703 /* Rotate the partial schedule to have the branch in row ii-1. */
1704 int amount
= SCHED_TIME (g
->closing_branch
->cuid
) - (ps
->ii
- 1);
1706 reset_sched_times (ps
, amount
);
1707 rotate_partial_schedule (ps
, amount
);
1710 set_columns_for_ps (ps
);
1712 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1713 if (!schedule_reg_moves (ps
))
1716 free_partial_schedule (ps
);
1720 /* Moves that handle incoming values might have been added
1721 to a new first stage. Bump the stage count if so.
1723 ??? Perhaps we could consider rotating the schedule here
1725 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1727 reset_sched_times (ps
, 0);
1731 /* The stage count should now be correct without rotation. */
1732 gcc_checking_assert (stage_count
== calculate_stage_count (ps
, 0));
1733 PS_STAGE_COUNT (ps
) = stage_count
;
1739 dump_insn_location (tail
);
1740 fprintf (dump_file
, " SMS succeeded %d %d (with ii, sc)\n",
1741 ps
->ii
, stage_count
);
1742 print_partial_schedule (ps
, dump_file
);
1745 /* case the BCT count is not known , Do loop-versioning */
1746 if (count_reg
&& ! count_init
)
1748 rtx comp_rtx
= gen_rtx_GT (VOIDmode
, count_reg
,
1749 gen_int_mode (stage_count
,
1750 GET_MODE (count_reg
)));
1751 unsigned prob
= (PROB_SMS_ENOUGH_ITERATIONS
1752 * REG_BR_PROB_BASE
) / 100;
1754 loop_version (loop
, comp_rtx
, &condition_bb
,
1755 prob
, prob
, REG_BR_PROB_BASE
- prob
,
1759 /* Set new iteration count of loop kernel. */
1760 if (count_reg
&& count_init
)
1761 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1764 /* Now apply the scheduled kernel to the RTL of the loop. */
1765 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1767 /* Mark this loop as software pipelined so the later
1768 scheduling passes don't touch it. */
1769 if (! flag_resched_modulo_sched
)
1770 mark_loop_unsched (loop
);
1772 /* The life-info is not valid any more. */
1773 df_set_bb_dirty (g
->bb
);
1775 apply_reg_moves (ps
);
1777 print_node_sched_params (dump_file
, g
->num_nodes
, ps
);
1778 /* Generate prolog and epilog. */
1779 generate_prolog_epilog (ps
, loop
, count_reg
, count_init
);
1783 free_partial_schedule (ps
);
1784 node_sched_param_vec
.release ();
1791 /* Release scheduler data, needed until now because of DFA. */
1792 haifa_sched_finish ();
1793 loop_optimizer_finalize ();
1796 /* The SMS scheduling algorithm itself
1797 -----------------------------------
1798 Input: 'O' an ordered list of insns of a loop.
1799 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1801 'Q' is the empty Set
1802 'PS' is the partial schedule; it holds the currently scheduled nodes with
1804 'PSP' previously scheduled predecessors.
1805 'PSS' previously scheduled successors.
1806 't(u)' the cycle where u is scheduled.
1807 'l(u)' is the latency of u.
1808 'd(v,u)' is the dependence distance from v to u.
1809 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1810 the node ordering phase.
1811 'check_hardware_resources_conflicts(u, PS, c)'
1812 run a trace around cycle/slot through DFA model
1813 to check resource conflicts involving instruction u
1814 at cycle c given the partial schedule PS.
1815 'add_to_partial_schedule_at_time(u, PS, c)'
1816 Add the node/instruction u to the partial schedule
1818 'calculate_register_pressure(PS)'
1819 Given a schedule of instructions, calculate the register
1820 pressure it implies. One implementation could be the
1821 maximum number of overlapping live ranges.
1822 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1823 registers available in the hardware.
1827 3. for each node u in O in pre-computed order
1828 4. if (PSP(u) != Q && PSS(u) == Q) then
1829 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1830 6. start = Early_start; end = Early_start + II - 1; step = 1
1831 11. else if (PSP(u) == Q && PSS(u) != Q) then
1832 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1833 13. start = Late_start; end = Late_start - II + 1; step = -1
1834 14. else if (PSP(u) != Q && PSS(u) != Q) then
1835 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1836 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1837 17. start = Early_start;
1838 18. end = min(Early_start + II - 1 , Late_start);
1840 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1841 21. start = ASAP(u); end = start + II - 1; step = 1
1845 24. for (c = start ; c != end ; c += step)
1846 25. if check_hardware_resources_conflicts(u, PS, c) then
1847 26. add_to_partial_schedule_at_time(u, PS, c)
1852 31. if (success == false) then
1854 33. if (II > maxII) then
1855 34. finish - failed to schedule
1860 39. if (calculate_register_pressure(PS) > maxRP) then
1863 42. compute epilogue & prologue
1864 43. finish - succeeded to schedule
1866 ??? The algorithm restricts the scheduling window to II cycles.
1867 In rare cases, it may be better to allow windows of II+1 cycles.
1868 The window would then start and end on the same row, but with
1869 different "must precede" and "must follow" requirements. */
1871 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1872 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1873 set to 0 to save compile time. */
1874 #define DFA_HISTORY SMS_DFA_HISTORY
1876 /* A threshold for the number of repeated unsuccessful attempts to insert
1877 an empty row, before we flush the partial schedule and start over. */
1878 #define MAX_SPLIT_NUM 10
1879 /* Given the partial schedule PS, this function calculates and returns the
1880 cycles in which we can schedule the node with the given index I.
1881 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1882 noticed that there are several cases in which we fail to SMS the loop
1883 because the sched window of a node is empty due to tight data-deps. In
1884 such cases we want to unschedule some of the predecessors/successors
1885 until we get non-empty scheduling window. It returns -1 if the
1886 scheduling window is empty and zero otherwise. */
1889 get_sched_window (partial_schedule_ptr ps
, ddg_node_ptr u_node
,
1890 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
,
1893 int start
, step
, end
;
1894 int early_start
, late_start
;
1896 sbitmap psp
= sbitmap_alloc (ps
->g
->num_nodes
);
1897 sbitmap pss
= sbitmap_alloc (ps
->g
->num_nodes
);
1898 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1899 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1905 /* 1. compute sched window for u (start, end, step). */
1908 psp_not_empty
= bitmap_and (psp
, u_node_preds
, sched_nodes
);
1909 pss_not_empty
= bitmap_and (pss
, u_node_succs
, sched_nodes
);
1911 /* We first compute a forward range (start <= end), then decide whether
1913 early_start
= INT_MIN
;
1914 late_start
= INT_MAX
;
1922 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1924 fprintf (dump_file
, "\nAnalyzing dependencies for node %d (INSN %d)"
1925 "; ii = %d\n\n", u_node
->cuid
, INSN_UID (u_node
->insn
), ii
);
1926 fprintf (dump_file
, "%11s %11s %11s %11s %5s\n",
1927 "start", "early start", "late start", "end", "time");
1928 fprintf (dump_file
, "=========== =========== =========== ==========="
1931 /* Calculate early_start and limit end. Both bounds are inclusive. */
1933 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1935 int v
= e
->src
->cuid
;
1937 if (bitmap_bit_p (sched_nodes
, v
))
1939 int p_st
= SCHED_TIME (v
);
1940 int earliest
= p_st
+ e
->latency
- (e
->distance
* ii
);
1941 int latest
= (e
->data_type
== MEM_DEP
? p_st
+ ii
- 1 : INT_MAX
);
1945 fprintf (dump_file
, "%11s %11d %11s %11d %5d",
1946 "", earliest
, "", latest
, p_st
);
1947 print_ddg_edge (dump_file
, e
);
1948 fprintf (dump_file
, "\n");
1951 early_start
= MAX (early_start
, earliest
);
1952 end
= MIN (end
, latest
);
1954 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1959 /* Calculate late_start and limit start. Both bounds are inclusive. */
1961 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1963 int v
= e
->dest
->cuid
;
1965 if (bitmap_bit_p (sched_nodes
, v
))
1967 int s_st
= SCHED_TIME (v
);
1968 int earliest
= (e
->data_type
== MEM_DEP
? s_st
- ii
+ 1 : INT_MIN
);
1969 int latest
= s_st
- e
->latency
+ (e
->distance
* ii
);
1973 fprintf (dump_file
, "%11d %11s %11d %11s %5d",
1974 earliest
, "", latest
, "", s_st
);
1975 print_ddg_edge (dump_file
, e
);
1976 fprintf (dump_file
, "\n");
1979 start
= MAX (start
, earliest
);
1980 late_start
= MIN (late_start
, latest
);
1982 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1987 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1989 fprintf (dump_file
, "----------- ----------- ----------- -----------"
1991 fprintf (dump_file
, "%11d %11d %11d %11d %5s %s\n",
1992 start
, early_start
, late_start
, end
, "",
1993 "(max, max, min, min)");
1996 /* Get a target scheduling window no bigger than ii. */
1997 if (early_start
== INT_MIN
&& late_start
== INT_MAX
)
1998 early_start
= NODE_ASAP (u_node
);
1999 else if (early_start
== INT_MIN
)
2000 early_start
= late_start
- (ii
- 1);
2001 late_start
= MIN (late_start
, early_start
+ (ii
- 1));
2003 /* Apply memory dependence limits. */
2004 start
= MAX (start
, early_start
);
2005 end
= MIN (end
, late_start
);
2007 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
2008 fprintf (dump_file
, "%11s %11d %11d %11s %5s final window\n",
2009 "", start
, end
, "", "");
2011 /* If there are at least as many successors as predecessors, schedule the
2012 node close to its successors. */
2013 if (pss_not_empty
&& count_succs
>= count_preds
)
2021 /* Now that we've finalized the window, make END an exclusive rather
2022 than an inclusive bound. */
2031 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
2034 fprintf (dump_file
, "\nEmpty window: start=%d, end=%d, step=%d\n",
2042 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
2043 node currently been scheduled. At the end of the calculation
2044 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
2045 U_NODE which are (1) already scheduled in the first/last row of
2046 U_NODE's scheduling window, (2) whose dependence inequality with U
2047 becomes an equality when U is scheduled in this same row, and (3)
2048 whose dependence latency is zero.
2050 The first and last rows are calculated using the following parameters:
2051 START/END rows - The cycles that begins/ends the traversal on the window;
2052 searching for an empty cycle to schedule U_NODE.
2053 STEP - The direction in which we traverse the window.
2054 II - The initiation interval. */
2057 calculate_must_precede_follow (ddg_node_ptr u_node
, int start
, int end
,
2058 int step
, int ii
, sbitmap sched_nodes
,
2059 sbitmap must_precede
, sbitmap must_follow
)
2062 int first_cycle_in_window
, last_cycle_in_window
;
2064 gcc_assert (must_precede
&& must_follow
);
2066 /* Consider the following scheduling window:
2067 {first_cycle_in_window, first_cycle_in_window+1, ...,
2068 last_cycle_in_window}. If step is 1 then the following will be
2069 the order we traverse the window: {start=first_cycle_in_window,
2070 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
2071 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
2072 end=first_cycle_in_window-1} if step is -1. */
2073 first_cycle_in_window
= (step
== 1) ? start
: end
- step
;
2074 last_cycle_in_window
= (step
== 1) ? end
- step
: start
;
2076 bitmap_clear (must_precede
);
2077 bitmap_clear (must_follow
);
2080 fprintf (dump_file
, "\nmust_precede: ");
2082 /* Instead of checking if:
2083 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
2084 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
2085 first_cycle_in_window)
2087 we use the fact that latency is non-negative:
2088 SCHED_TIME (e->src) - (e->distance * ii) <=
2089 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
2090 first_cycle_in_window
2092 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
2093 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2094 if (bitmap_bit_p (sched_nodes
, e
->src
->cuid
)
2095 && ((SCHED_TIME (e
->src
->cuid
) - (e
->distance
* ii
)) ==
2096 first_cycle_in_window
))
2099 fprintf (dump_file
, "%d ", e
->src
->cuid
);
2101 bitmap_set_bit (must_precede
, e
->src
->cuid
);
2105 fprintf (dump_file
, "\nmust_follow: ");
2107 /* Instead of checking if:
2108 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
2109 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
2110 last_cycle_in_window)
2112 we use the fact that latency is non-negative:
2113 SCHED_TIME (e->dest) + (e->distance * ii) >=
2114 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
2115 last_cycle_in_window
2117 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
2118 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2119 if (bitmap_bit_p (sched_nodes
, e
->dest
->cuid
)
2120 && ((SCHED_TIME (e
->dest
->cuid
) + (e
->distance
* ii
)) ==
2121 last_cycle_in_window
))
2124 fprintf (dump_file
, "%d ", e
->dest
->cuid
);
2126 bitmap_set_bit (must_follow
, e
->dest
->cuid
);
2130 fprintf (dump_file
, "\n");
2133 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
2134 parameters to decide if that's possible:
2135 PS - The partial schedule.
2136 U - The serial number of U_NODE.
2137 NUM_SPLITS - The number of row splits made so far.
2138 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
2139 the first row of the scheduling window)
2140 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
2141 last row of the scheduling window) */
2144 try_scheduling_node_in_cycle (partial_schedule_ptr ps
,
2145 int u
, int cycle
, sbitmap sched_nodes
,
2146 int *num_splits
, sbitmap must_precede
,
2147 sbitmap must_follow
)
2152 verify_partial_schedule (ps
, sched_nodes
);
2153 psi
= ps_add_node_check_conflicts (ps
, u
, cycle
, must_precede
, must_follow
);
2156 SCHED_TIME (u
) = cycle
;
2157 bitmap_set_bit (sched_nodes
, u
);
2161 fprintf (dump_file
, "Scheduled w/o split in %d\n", cycle
);
2168 /* This function implements the scheduling algorithm for SMS according to the
2170 static partial_schedule_ptr
2171 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
)
2174 int i
, c
, success
, num_splits
= 0;
2175 int flush_and_start_over
= true;
2176 int num_nodes
= g
->num_nodes
;
2177 int start
, end
, step
; /* Place together into one struct? */
2178 sbitmap sched_nodes
= sbitmap_alloc (num_nodes
);
2179 sbitmap must_precede
= sbitmap_alloc (num_nodes
);
2180 sbitmap must_follow
= sbitmap_alloc (num_nodes
);
2181 sbitmap tobe_scheduled
= sbitmap_alloc (num_nodes
);
2183 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
, DFA_HISTORY
);
2185 bitmap_ones (tobe_scheduled
);
2186 bitmap_clear (sched_nodes
);
2188 while (flush_and_start_over
&& (ii
< maxii
))
2192 fprintf (dump_file
, "Starting with ii=%d\n", ii
);
2193 flush_and_start_over
= false;
2194 bitmap_clear (sched_nodes
);
2196 for (i
= 0; i
< num_nodes
; i
++)
2198 int u
= nodes_order
[i
];
2199 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
2200 rtx insn
= u_node
->insn
;
2202 if (!NONDEBUG_INSN_P (insn
))
2204 bitmap_clear_bit (tobe_scheduled
, u
);
2208 if (bitmap_bit_p (sched_nodes
, u
))
2211 /* Try to get non-empty scheduling window. */
2213 if (get_sched_window (ps
, u_node
, sched_nodes
, ii
, &start
,
2217 fprintf (dump_file
, "\nTrying to schedule node %d "
2218 "INSN = %d in (%d .. %d) step %d\n", u
, (INSN_UID
2219 (g
->nodes
[u
].insn
)), start
, end
, step
);
2221 gcc_assert ((step
> 0 && start
< end
)
2222 || (step
< 0 && start
> end
));
2224 calculate_must_precede_follow (u_node
, start
, end
, step
, ii
,
2225 sched_nodes
, must_precede
,
2228 for (c
= start
; c
!= end
; c
+= step
)
2230 sbitmap tmp_precede
, tmp_follow
;
2232 set_must_precede_follow (&tmp_follow
, must_follow
,
2233 &tmp_precede
, must_precede
,
2234 c
, start
, end
, step
);
2236 try_scheduling_node_in_cycle (ps
, u
, c
,
2238 &num_splits
, tmp_precede
,
2244 verify_partial_schedule (ps
, sched_nodes
);
2253 if (num_splits
>= MAX_SPLIT_NUM
)
2256 flush_and_start_over
= true;
2257 verify_partial_schedule (ps
, sched_nodes
);
2258 reset_partial_schedule (ps
, ii
);
2259 verify_partial_schedule (ps
, sched_nodes
);
2264 /* The scheduling window is exclusive of 'end'
2265 whereas compute_split_window() expects an inclusive,
2268 split_row
= compute_split_row (sched_nodes
, start
, end
- 1,
2271 split_row
= compute_split_row (sched_nodes
, end
+ 1, start
,
2274 ps_insert_empty_row (ps
, split_row
, sched_nodes
);
2275 i
--; /* Go back and retry node i. */
2278 fprintf (dump_file
, "num_splits=%d\n", num_splits
);
2281 /* ??? If (success), check register pressure estimates. */
2282 } /* Continue with next node. */
2283 } /* While flush_and_start_over. */
2286 free_partial_schedule (ps
);
2290 gcc_assert (bitmap_equal_p (tobe_scheduled
, sched_nodes
));
2292 sbitmap_free (sched_nodes
);
2293 sbitmap_free (must_precede
);
2294 sbitmap_free (must_follow
);
2295 sbitmap_free (tobe_scheduled
);
2300 /* This function inserts a new empty row into PS at the position
2301 according to SPLITROW, keeping all already scheduled instructions
2302 intact and updating their SCHED_TIME and cycle accordingly. */
2304 ps_insert_empty_row (partial_schedule_ptr ps
, int split_row
,
2305 sbitmap sched_nodes
)
2307 ps_insn_ptr crr_insn
;
2308 ps_insn_ptr
*rows_new
;
2310 int new_ii
= ii
+ 1;
2312 int *rows_length_new
;
2314 verify_partial_schedule (ps
, sched_nodes
);
2316 /* We normalize sched_time and rotate ps to have only non-negative sched
2317 times, for simplicity of updating cycles after inserting new row. */
2318 split_row
-= ps
->min_cycle
;
2319 split_row
= SMODULO (split_row
, ii
);
2321 fprintf (dump_file
, "split_row=%d\n", split_row
);
2323 reset_sched_times (ps
, PS_MIN_CYCLE (ps
));
2324 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
2326 rows_new
= (ps_insn_ptr
*) xcalloc (new_ii
, sizeof (ps_insn_ptr
));
2327 rows_length_new
= (int *) xcalloc (new_ii
, sizeof (int));
2328 for (row
= 0; row
< split_row
; row
++)
2330 rows_new
[row
] = ps
->rows
[row
];
2331 rows_length_new
[row
] = ps
->rows_length
[row
];
2332 ps
->rows
[row
] = NULL
;
2333 for (crr_insn
= rows_new
[row
];
2334 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2336 int u
= crr_insn
->id
;
2337 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
);
2339 SCHED_TIME (u
) = new_time
;
2340 crr_insn
->cycle
= new_time
;
2341 SCHED_ROW (u
) = new_time
% new_ii
;
2342 SCHED_STAGE (u
) = new_time
/ new_ii
;
2347 rows_new
[split_row
] = NULL
;
2349 for (row
= split_row
; row
< ii
; row
++)
2351 rows_new
[row
+ 1] = ps
->rows
[row
];
2352 rows_length_new
[row
+ 1] = ps
->rows_length
[row
];
2353 ps
->rows
[row
] = NULL
;
2354 for (crr_insn
= rows_new
[row
+ 1];
2355 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2357 int u
= crr_insn
->id
;
2358 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
) + 1;
2360 SCHED_TIME (u
) = new_time
;
2361 crr_insn
->cycle
= new_time
;
2362 SCHED_ROW (u
) = new_time
% new_ii
;
2363 SCHED_STAGE (u
) = new_time
/ new_ii
;
2368 ps
->min_cycle
= ps
->min_cycle
+ ps
->min_cycle
/ ii
2369 + (SMODULO (ps
->min_cycle
, ii
) >= split_row
? 1 : 0);
2370 ps
->max_cycle
= ps
->max_cycle
+ ps
->max_cycle
/ ii
2371 + (SMODULO (ps
->max_cycle
, ii
) >= split_row
? 1 : 0);
2373 ps
->rows
= rows_new
;
2374 free (ps
->rows_length
);
2375 ps
->rows_length
= rows_length_new
;
2377 gcc_assert (ps
->min_cycle
>= 0);
2379 verify_partial_schedule (ps
, sched_nodes
);
2382 fprintf (dump_file
, "min_cycle=%d, max_cycle=%d\n", ps
->min_cycle
,
2386 /* Given U_NODE which is the node that failed to be scheduled; LOW and
2387 UP which are the boundaries of it's scheduling window; compute using
2388 SCHED_NODES and II a row in the partial schedule that can be split
2389 which will separate a critical predecessor from a critical successor
2390 thereby expanding the window, and return it. */
2392 compute_split_row (sbitmap sched_nodes
, int low
, int up
, int ii
,
2393 ddg_node_ptr u_node
)
2396 int lower
= INT_MIN
, upper
= INT_MAX
;
2401 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2403 int v
= e
->src
->cuid
;
2405 if (bitmap_bit_p (sched_nodes
, v
)
2406 && (low
== SCHED_TIME (v
) + e
->latency
- (e
->distance
* ii
)))
2407 if (SCHED_TIME (v
) > lower
)
2410 lower
= SCHED_TIME (v
);
2416 crit_cycle
= SCHED_TIME (crit_pred
) + 1;
2417 return SMODULO (crit_cycle
, ii
);
2420 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2422 int v
= e
->dest
->cuid
;
2424 if (bitmap_bit_p (sched_nodes
, v
)
2425 && (up
== SCHED_TIME (v
) - e
->latency
+ (e
->distance
* ii
)))
2426 if (SCHED_TIME (v
) < upper
)
2429 upper
= SCHED_TIME (v
);
2435 crit_cycle
= SCHED_TIME (crit_succ
);
2436 return SMODULO (crit_cycle
, ii
);
2440 fprintf (dump_file
, "Both crit_pred and crit_succ are NULL\n");
2442 return SMODULO ((low
+ up
+ 1) / 2, ii
);
2446 verify_partial_schedule (partial_schedule_ptr ps
, sbitmap sched_nodes
)
2449 ps_insn_ptr crr_insn
;
2451 for (row
= 0; row
< ps
->ii
; row
++)
2455 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2457 int u
= crr_insn
->id
;
2460 gcc_assert (bitmap_bit_p (sched_nodes
, u
));
2461 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2462 popcount (sched_nodes) == number of insns in ps. */
2463 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
2464 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
2467 gcc_assert (ps
->rows_length
[row
] == length
);
2472 /* This page implements the algorithm for ordering the nodes of a DDG
2473 for modulo scheduling, activated through the
2474 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2476 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2477 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
2478 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
2479 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2480 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
2481 #define DEPTH(x) (ASAP ((x)))
2483 typedef struct node_order_params
* nopa
;
2485 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
2486 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
2487 static nopa
calculate_order_params (ddg_ptr
, int, int *);
2488 static int find_max_asap (ddg_ptr
, sbitmap
);
2489 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
2490 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
2492 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
2494 struct node_order_params
2501 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2503 check_nodes_order (int *node_order
, int num_nodes
)
2506 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2511 fprintf (dump_file
, "SMS final nodes order: \n");
2513 for (i
= 0; i
< num_nodes
; i
++)
2515 int u
= node_order
[i
];
2518 fprintf (dump_file
, "%d ", u
);
2519 gcc_assert (u
< num_nodes
&& u
>= 0 && !bitmap_bit_p (tmp
, u
));
2521 bitmap_set_bit (tmp
, u
);
2525 fprintf (dump_file
, "\n");
2530 /* Order the nodes of G for scheduling and pass the result in
2531 NODE_ORDER. Also set aux.count of each node to ASAP.
2532 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2534 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
, int *pmax_asap
)
2538 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
2540 nopa nops
= calculate_order_params (g
, mii
, pmax_asap
);
2543 print_sccs (dump_file
, sccs
, g
);
2545 order_nodes_of_sccs (sccs
, node_order
);
2547 if (sccs
->num_sccs
> 0)
2548 /* First SCC has the largest recurrence_length. */
2549 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
2551 /* Save ASAP before destroying node_order_params. */
2552 for (i
= 0; i
< g
->num_nodes
; i
++)
2554 ddg_node_ptr v
= &g
->nodes
[i
];
2555 v
->aux
.count
= ASAP (v
);
2559 free_ddg_all_sccs (sccs
);
2560 check_nodes_order (node_order
, g
->num_nodes
);
2566 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
2569 ddg_ptr g
= all_sccs
->ddg
;
2570 int num_nodes
= g
->num_nodes
;
2571 sbitmap prev_sccs
= sbitmap_alloc (num_nodes
);
2572 sbitmap on_path
= sbitmap_alloc (num_nodes
);
2573 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2574 sbitmap ones
= sbitmap_alloc (num_nodes
);
2576 bitmap_clear (prev_sccs
);
2579 /* Perform the node ordering starting from the SCC with the highest recMII.
2580 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2581 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
2583 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
2585 /* Add nodes on paths from previous SCCs to the current SCC. */
2586 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
2587 bitmap_ior (tmp
, scc
->nodes
, on_path
);
2589 /* Add nodes on paths from the current SCC to previous SCCs. */
2590 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
2591 bitmap_ior (tmp
, tmp
, on_path
);
2593 /* Remove nodes of previous SCCs from current extended SCC. */
2594 bitmap_and_compl (tmp
, tmp
, prev_sccs
);
2596 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2597 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2600 /* Handle the remaining nodes that do not belong to any scc. Each call
2601 to order_nodes_in_scc handles a single connected component. */
2602 while (pos
< g
->num_nodes
)
2604 bitmap_and_compl (tmp
, ones
, prev_sccs
);
2605 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2607 sbitmap_free (prev_sccs
);
2608 sbitmap_free (on_path
);
2610 sbitmap_free (ones
);
2613 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2614 static struct node_order_params
*
2615 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
, int *pmax_asap
)
2619 int num_nodes
= g
->num_nodes
;
2621 /* Allocate a place to hold ordering params for each node in the DDG. */
2622 nopa node_order_params_arr
;
2624 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2625 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
2626 sizeof (struct node_order_params
));
2628 /* Set the aux pointer of each node to point to its order_params structure. */
2629 for (u
= 0; u
< num_nodes
; u
++)
2630 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
2632 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2633 calculate ASAP, ALAP, mobility, distance, and height for each node
2634 in the dependence (direct acyclic) graph. */
2636 /* We assume that the nodes in the array are in topological order. */
2639 for (u
= 0; u
< num_nodes
; u
++)
2641 ddg_node_ptr u_node
= &g
->nodes
[u
];
2644 for (e
= u_node
->in
; e
; e
= e
->next_in
)
2645 if (e
->distance
== 0)
2646 ASAP (u_node
) = MAX (ASAP (u_node
),
2647 ASAP (e
->src
) + e
->latency
);
2648 max_asap
= MAX (max_asap
, ASAP (u_node
));
2651 for (u
= num_nodes
- 1; u
> -1; u
--)
2653 ddg_node_ptr u_node
= &g
->nodes
[u
];
2655 ALAP (u_node
) = max_asap
;
2656 HEIGHT (u_node
) = 0;
2657 for (e
= u_node
->out
; e
; e
= e
->next_out
)
2658 if (e
->distance
== 0)
2660 ALAP (u_node
) = MIN (ALAP (u_node
),
2661 ALAP (e
->dest
) - e
->latency
);
2662 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
2663 HEIGHT (e
->dest
) + e
->latency
);
2668 fprintf (dump_file
, "\nOrder params\n");
2669 for (u
= 0; u
< num_nodes
; u
++)
2671 ddg_node_ptr u_node
= &g
->nodes
[u
];
2673 fprintf (dump_file
, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u
,
2674 ASAP (u_node
), ALAP (u_node
), HEIGHT (u_node
));
2678 *pmax_asap
= max_asap
;
2679 return node_order_params_arr
;
2683 find_max_asap (ddg_ptr g
, sbitmap nodes
)
2688 sbitmap_iterator sbi
;
2690 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2692 ddg_node_ptr u_node
= &g
->nodes
[u
];
2694 if (max_asap
< ASAP (u_node
))
2696 max_asap
= ASAP (u_node
);
2704 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
2708 int min_mob
= INT_MAX
;
2710 sbitmap_iterator sbi
;
2712 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2714 ddg_node_ptr u_node
= &g
->nodes
[u
];
2716 if (max_hv
< HEIGHT (u_node
))
2718 max_hv
= HEIGHT (u_node
);
2719 min_mob
= MOB (u_node
);
2722 else if ((max_hv
== HEIGHT (u_node
))
2723 && (min_mob
> MOB (u_node
)))
2725 min_mob
= MOB (u_node
);
2733 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
2737 int min_mob
= INT_MAX
;
2739 sbitmap_iterator sbi
;
2741 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2743 ddg_node_ptr u_node
= &g
->nodes
[u
];
2745 if (max_dv
< DEPTH (u_node
))
2747 max_dv
= DEPTH (u_node
);
2748 min_mob
= MOB (u_node
);
2751 else if ((max_dv
== DEPTH (u_node
))
2752 && (min_mob
> MOB (u_node
)))
2754 min_mob
= MOB (u_node
);
2761 /* Places the nodes of SCC into the NODE_ORDER array starting
2762 at position POS, according to the SMS ordering algorithm.
2763 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2764 the NODE_ORDER array, starting from position zero. */
2766 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
2767 int * node_order
, int pos
)
2769 enum sms_direction dir
;
2770 int num_nodes
= g
->num_nodes
;
2771 sbitmap workset
= sbitmap_alloc (num_nodes
);
2772 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2773 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
2774 sbitmap predecessors
= sbitmap_alloc (num_nodes
);
2775 sbitmap successors
= sbitmap_alloc (num_nodes
);
2777 bitmap_clear (predecessors
);
2778 find_predecessors (predecessors
, g
, nodes_ordered
);
2780 bitmap_clear (successors
);
2781 find_successors (successors
, g
, nodes_ordered
);
2784 if (bitmap_and (tmp
, predecessors
, scc
))
2786 bitmap_copy (workset
, tmp
);
2789 else if (bitmap_and (tmp
, successors
, scc
))
2791 bitmap_copy (workset
, tmp
);
2798 bitmap_clear (workset
);
2799 if ((u
= find_max_asap (g
, scc
)) >= 0)
2800 bitmap_set_bit (workset
, u
);
2804 bitmap_clear (zero_bitmap
);
2805 while (!bitmap_equal_p (workset
, zero_bitmap
))
2808 ddg_node_ptr v_node
;
2809 sbitmap v_node_preds
;
2810 sbitmap v_node_succs
;
2814 while (!bitmap_equal_p (workset
, zero_bitmap
))
2816 v
= find_max_hv_min_mob (g
, workset
);
2817 v_node
= &g
->nodes
[v
];
2818 node_order
[pos
++] = v
;
2819 v_node_succs
= NODE_SUCCESSORS (v_node
);
2820 bitmap_and (tmp
, v_node_succs
, scc
);
2822 /* Don't consider the already ordered successors again. */
2823 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2824 bitmap_ior (workset
, workset
, tmp
);
2825 bitmap_clear_bit (workset
, v
);
2826 bitmap_set_bit (nodes_ordered
, v
);
2829 bitmap_clear (predecessors
);
2830 find_predecessors (predecessors
, g
, nodes_ordered
);
2831 bitmap_and (workset
, predecessors
, scc
);
2835 while (!bitmap_equal_p (workset
, zero_bitmap
))
2837 v
= find_max_dv_min_mob (g
, workset
);
2838 v_node
= &g
->nodes
[v
];
2839 node_order
[pos
++] = v
;
2840 v_node_preds
= NODE_PREDECESSORS (v_node
);
2841 bitmap_and (tmp
, v_node_preds
, scc
);
2843 /* Don't consider the already ordered predecessors again. */
2844 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2845 bitmap_ior (workset
, workset
, tmp
);
2846 bitmap_clear_bit (workset
, v
);
2847 bitmap_set_bit (nodes_ordered
, v
);
2850 bitmap_clear (successors
);
2851 find_successors (successors
, g
, nodes_ordered
);
2852 bitmap_and (workset
, successors
, scc
);
2856 sbitmap_free (workset
);
2857 sbitmap_free (zero_bitmap
);
2858 sbitmap_free (predecessors
);
2859 sbitmap_free (successors
);
2864 /* This page contains functions for manipulating partial-schedules during
2865 modulo scheduling. */
2867 /* Create a partial schedule and allocate a memory to hold II rows. */
2869 static partial_schedule_ptr
2870 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2872 partial_schedule_ptr ps
= XNEW (struct partial_schedule
);
2873 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2874 ps
->rows_length
= (int *) xcalloc (ii
, sizeof (int));
2875 ps
->reg_moves
.create (0);
2877 ps
->history
= history
;
2878 ps
->min_cycle
= INT_MAX
;
2879 ps
->max_cycle
= INT_MIN
;
2885 /* Free the PS_INSNs in rows array of the given partial schedule.
2886 ??? Consider caching the PS_INSN's. */
2888 free_ps_insns (partial_schedule_ptr ps
)
2892 for (i
= 0; i
< ps
->ii
; i
++)
2896 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2899 ps
->rows
[i
] = ps_insn
;
2905 /* Free all the memory allocated to the partial schedule. */
2908 free_partial_schedule (partial_schedule_ptr ps
)
2910 ps_reg_move_info
*move
;
2916 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
2917 sbitmap_free (move
->uses
);
2918 ps
->reg_moves
.release ();
2922 free (ps
->rows_length
);
2926 /* Clear the rows array with its PS_INSNs, and create a new one with
2930 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2935 if (new_ii
== ps
->ii
)
2937 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2938 * sizeof (ps_insn_ptr
));
2939 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2940 ps
->rows_length
= (int *) xrealloc (ps
->rows_length
, new_ii
* sizeof (int));
2941 memset (ps
->rows_length
, 0, new_ii
* sizeof (int));
2943 ps
->min_cycle
= INT_MAX
;
2944 ps
->max_cycle
= INT_MIN
;
2947 /* Prints the partial schedule as an ii rows array, for each rows
2948 print the ids of the insns in it. */
2950 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2954 for (i
= 0; i
< ps
->ii
; i
++)
2956 ps_insn_ptr ps_i
= ps
->rows
[i
];
2958 fprintf (dump
, "\n[ROW %d ]: ", i
);
2961 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_i
->id
);
2964 fprintf (dump
, "%d (branch), ", INSN_UID (insn
));
2966 fprintf (dump
, "%d, ", INSN_UID (insn
));
2968 ps_i
= ps_i
->next_in_row
;
2973 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2975 create_ps_insn (int id
, int cycle
)
2977 ps_insn_ptr ps_i
= XNEW (struct ps_insn
);
2980 ps_i
->next_in_row
= NULL
;
2981 ps_i
->prev_in_row
= NULL
;
2982 ps_i
->cycle
= cycle
;
2988 /* Removes the given PS_INSN from the partial schedule. */
2990 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2994 gcc_assert (ps
&& ps_i
);
2996 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2997 if (! ps_i
->prev_in_row
)
2999 gcc_assert (ps_i
== ps
->rows
[row
]);
3000 ps
->rows
[row
] = ps_i
->next_in_row
;
3002 ps
->rows
[row
]->prev_in_row
= NULL
;
3006 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
3007 if (ps_i
->next_in_row
)
3008 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
3011 ps
->rows_length
[row
] -= 1;
3016 /* Unlike what literature describes for modulo scheduling (which focuses
3017 on VLIW machines) the order of the instructions inside a cycle is
3018 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
3019 where the current instruction should go relative to the already
3020 scheduled instructions in the given cycle. Go over these
3021 instructions and find the first possible column to put it in. */
3023 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
3024 sbitmap must_precede
, sbitmap must_follow
)
3026 ps_insn_ptr next_ps_i
;
3027 ps_insn_ptr first_must_follow
= NULL
;
3028 ps_insn_ptr last_must_precede
= NULL
;
3029 ps_insn_ptr last_in_row
= NULL
;
3035 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3037 /* Find the first must follow and the last must precede
3038 and insert the node immediately after the must precede
3039 but make sure that it there is no must follow after it. */
3040 for (next_ps_i
= ps
->rows
[row
];
3042 next_ps_i
= next_ps_i
->next_in_row
)
3045 && bitmap_bit_p (must_follow
, next_ps_i
->id
)
3046 && ! first_must_follow
)
3047 first_must_follow
= next_ps_i
;
3048 if (must_precede
&& bitmap_bit_p (must_precede
, next_ps_i
->id
))
3050 /* If we have already met a node that must follow, then
3051 there is no possible column. */
3052 if (first_must_follow
)
3055 last_must_precede
= next_ps_i
;
3057 /* The closing branch must be the last in the row. */
3059 && bitmap_bit_p (must_precede
, next_ps_i
->id
)
3060 && JUMP_P (ps_rtl_insn (ps
, next_ps_i
->id
)))
3063 last_in_row
= next_ps_i
;
3066 /* The closing branch is scheduled as well. Make sure there is no
3067 dependent instruction after it as the branch should be the last
3068 instruction in the row. */
3069 if (JUMP_P (ps_rtl_insn (ps
, ps_i
->id
)))
3071 if (first_must_follow
)
3075 /* Make the branch the last in the row. New instructions
3076 will be inserted at the beginning of the row or after the
3077 last must_precede instruction thus the branch is guaranteed
3078 to remain the last instruction in the row. */
3079 last_in_row
->next_in_row
= ps_i
;
3080 ps_i
->prev_in_row
= last_in_row
;
3081 ps_i
->next_in_row
= NULL
;
3084 ps
->rows
[row
] = ps_i
;
3088 /* Now insert the node after INSERT_AFTER_PSI. */
3090 if (! last_must_precede
)
3092 ps_i
->next_in_row
= ps
->rows
[row
];
3093 ps_i
->prev_in_row
= NULL
;
3094 if (ps_i
->next_in_row
)
3095 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3096 ps
->rows
[row
] = ps_i
;
3100 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
3101 last_must_precede
->next_in_row
= ps_i
;
3102 ps_i
->prev_in_row
= last_must_precede
;
3103 if (ps_i
->next_in_row
)
3104 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3110 /* Advances the PS_INSN one column in its current row; returns false
3111 in failure and true in success. Bit N is set in MUST_FOLLOW if
3112 the node with cuid N must be come after the node pointed to by
3113 PS_I when scheduled in the same cycle. */
3115 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
3116 sbitmap must_follow
)
3118 ps_insn_ptr prev
, next
;
3124 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3126 if (! ps_i
->next_in_row
)
3129 /* Check if next_in_row is dependent on ps_i, both having same sched
3130 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
3131 if (must_follow
&& bitmap_bit_p (must_follow
, ps_i
->next_in_row
->id
))
3134 /* Advance PS_I over its next_in_row in the doubly linked list. */
3135 prev
= ps_i
->prev_in_row
;
3136 next
= ps_i
->next_in_row
;
3138 if (ps_i
== ps
->rows
[row
])
3139 ps
->rows
[row
] = next
;
3141 ps_i
->next_in_row
= next
->next_in_row
;
3143 if (next
->next_in_row
)
3144 next
->next_in_row
->prev_in_row
= ps_i
;
3146 next
->next_in_row
= ps_i
;
3147 ps_i
->prev_in_row
= next
;
3149 next
->prev_in_row
= prev
;
3151 prev
->next_in_row
= next
;
3156 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
3157 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
3158 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
3159 before/after (respectively) the node pointed to by PS_I when scheduled
3160 in the same cycle. */
3162 add_node_to_ps (partial_schedule_ptr ps
, int id
, int cycle
,
3163 sbitmap must_precede
, sbitmap must_follow
)
3166 int row
= SMODULO (cycle
, ps
->ii
);
3168 if (ps
->rows_length
[row
] >= issue_rate
)
3171 ps_i
= create_ps_insn (id
, cycle
);
3173 /* Finds and inserts PS_I according to MUST_FOLLOW and
3175 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
3181 ps
->rows_length
[row
] += 1;
3185 /* Advance time one cycle. Assumes DFA is being used. */
3187 advance_one_cycle (void)
3189 if (targetm
.sched
.dfa_pre_cycle_insn
)
3190 state_transition (curr_state
,
3191 targetm
.sched
.dfa_pre_cycle_insn ());
3193 state_transition (curr_state
, NULL
);
3195 if (targetm
.sched
.dfa_post_cycle_insn
)
3196 state_transition (curr_state
,
3197 targetm
.sched
.dfa_post_cycle_insn ());
3202 /* Checks if PS has resource conflicts according to DFA, starting from
3203 FROM cycle to TO cycle; returns true if there are conflicts and false
3204 if there are no conflicts. Assumes DFA is being used. */
3206 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
3210 state_reset (curr_state
);
3212 for (cycle
= from
; cycle
<= to
; cycle
++)
3214 ps_insn_ptr crr_insn
;
3215 /* Holds the remaining issue slots in the current row. */
3216 int can_issue_more
= issue_rate
;
3218 /* Walk through the DFA for the current row. */
3219 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
3221 crr_insn
= crr_insn
->next_in_row
)
3223 rtx_insn
*insn
= ps_rtl_insn (ps
, crr_insn
->id
);
3225 if (!NONDEBUG_INSN_P (insn
))
3228 /* Check if there is room for the current insn. */
3229 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
3232 /* Update the DFA state and return with failure if the DFA found
3233 resource conflicts. */
3234 if (state_transition (curr_state
, insn
) >= 0)
3237 if (targetm
.sched
.variable_issue
)
3239 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
3240 insn
, can_issue_more
);
3241 /* A naked CLOBBER or USE generates no instruction, so don't
3242 let them consume issue slots. */
3243 else if (GET_CODE (PATTERN (insn
)) != USE
3244 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3248 /* Advance the DFA to the next cycle. */
3249 advance_one_cycle ();
3254 /* Checks if the given node causes resource conflicts when added to PS at
3255 cycle C. If not the node is added to PS and returned; otherwise zero
3256 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
3257 cuid N must be come before/after (respectively) the node pointed to by
3258 PS_I when scheduled in the same cycle. */
3260 ps_add_node_check_conflicts (partial_schedule_ptr ps
, int n
,
3261 int c
, sbitmap must_precede
,
3262 sbitmap must_follow
)
3264 int has_conflicts
= 0;
3267 /* First add the node to the PS, if this succeeds check for
3268 conflicts, trying different issue slots in the same row. */
3269 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
3270 return NULL
; /* Failed to insert the node at the given cycle. */
3272 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3274 && ps_has_conflicts (ps
,
3278 /* Try different issue slots to find one that the given node can be
3279 scheduled in without conflicts. */
3280 while (has_conflicts
)
3282 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
3284 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3286 && ps_has_conflicts (ps
,
3293 remove_node_from_ps (ps
, ps_i
);
3297 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
3298 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
3302 /* Calculate the stage count of the partial schedule PS. The calculation
3303 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3305 calculate_stage_count (partial_schedule_ptr ps
, int rotation_amount
)
3307 int new_min_cycle
= PS_MIN_CYCLE (ps
) - rotation_amount
;
3308 int new_max_cycle
= PS_MAX_CYCLE (ps
) - rotation_amount
;
3309 int stage_count
= CALC_STAGE_COUNT (-1, new_min_cycle
, ps
->ii
);
3311 /* The calculation of stage count is done adding the number of stages
3312 before cycle zero and after cycle zero. */
3313 stage_count
+= CALC_STAGE_COUNT (new_max_cycle
, 0, ps
->ii
);
3318 /* Rotate the rows of PS such that insns scheduled at time
3319 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3321 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
3323 int i
, row
, backward_rotates
;
3324 int last_row
= ps
->ii
- 1;
3326 if (start_cycle
== 0)
3329 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
3331 /* Revisit later and optimize this into a single loop. */
3332 for (i
= 0; i
< backward_rotates
; i
++)
3334 ps_insn_ptr first_row
= ps
->rows
[0];
3335 int first_row_length
= ps
->rows_length
[0];
3337 for (row
= 0; row
< last_row
; row
++)
3339 ps
->rows
[row
] = ps
->rows
[row
+ 1];
3340 ps
->rows_length
[row
] = ps
->rows_length
[row
+ 1];
3343 ps
->rows
[last_row
] = first_row
;
3344 ps
->rows_length
[last_row
] = first_row_length
;
3347 ps
->max_cycle
-= start_cycle
;
3348 ps
->min_cycle
-= start_cycle
;
3351 #endif /* INSN_SCHEDULING */
3353 /* Run instruction scheduler. */
3354 /* Perform SMS module scheduling. */
3358 const pass_data pass_data_sms
=
3360 RTL_PASS
, /* type */
3362 OPTGROUP_NONE
, /* optinfo_flags */
3364 0, /* properties_required */
3365 0, /* properties_provided */
3366 0, /* properties_destroyed */
3367 0, /* todo_flags_start */
3368 TODO_df_finish
, /* todo_flags_finish */
3371 class pass_sms
: public rtl_opt_pass
3374 pass_sms (gcc::context
*ctxt
)
3375 : rtl_opt_pass (pass_data_sms
, ctxt
)
3378 /* opt_pass methods: */
3379 virtual bool gate (function
*)
3381 return (optimize
> 0 && flag_modulo_sched
);
3384 virtual unsigned int execute (function
*);
3386 }; // class pass_sms
3389 pass_sms::execute (function
*fun ATTRIBUTE_UNUSED
)
3391 #ifdef INSN_SCHEDULING
3394 /* Collect loop information to be used in SMS. */
3395 cfg_layout_initialize (0);
3398 /* Update the life information, because we add pseudos. */
3399 max_regno
= max_reg_num ();
3401 /* Finalize layout changes. */
3402 FOR_EACH_BB_FN (bb
, fun
)
3403 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3404 bb
->aux
= bb
->next_bb
;
3405 free_dominance_info (CDI_DOMINATORS
);
3406 cfg_layout_finalize ();
3407 #endif /* INSN_SCHEDULING */
3414 make_pass_sms (gcc::context
*ctxt
)
3416 return new pass_sms (ctxt
);