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"
36 #include "insn-attr.h"
38 #include "sched-int.h"
43 #include "tree-pass.h"
45 #include "loop-unroll.h"
47 #ifdef INSN_SCHEDULING
49 /* This file contains the implementation of the Swing Modulo Scheduler,
50 described in the following references:
51 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
52 Lifetime--sensitive modulo scheduling in a production environment.
53 IEEE Trans. on Comps., 50(3), March 2001
54 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
55 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
56 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
58 The basic structure is:
59 1. Build a data-dependence graph (DDG) for each loop.
60 2. Use the DDG to order the insns of a loop (not in topological order
61 necessarily, but rather) trying to place each insn after all its
62 predecessors _or_ after all its successors.
63 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
64 4. Use the ordering to perform list-scheduling of the loop:
65 1. Set II = MII. We will try to schedule the loop within II cycles.
66 2. Try to schedule the insns one by one according to the ordering.
67 For each insn compute an interval of cycles by considering already-
68 scheduled preds and succs (and associated latencies); try to place
69 the insn in the cycles of this window checking for potential
70 resource conflicts (using the DFA interface).
71 Note: this is different from the cycle-scheduling of schedule_insns;
72 here the insns are not scheduled monotonically top-down (nor bottom-
74 3. If failed in scheduling all insns - bump II++ and try again, unless
75 II reaches an upper bound MaxII, in which case report failure.
76 5. If we succeeded in scheduling the loop within II cycles, we now
77 generate prolog and epilog, decrease the counter of the loop, and
78 perform modulo variable expansion for live ranges that span more than
79 II cycles (i.e. use register copies to prevent a def from overwriting
80 itself before reaching the use).
82 SMS works with countable loops (1) whose control part can be easily
83 decoupled from the rest of the loop and (2) whose loop count can
84 be easily adjusted. This is because we peel a constant number of
85 iterations into a prologue and epilogue for which we want to avoid
86 emitting the control part, and a kernel which is to iterate that
87 constant number of iterations less than the original loop. So the
88 control part should be a set of insns clearly identified and having
89 its own iv, not otherwise used in the loop (at-least for now), which
90 initializes a register before the loop to the number of iterations.
91 Currently SMS relies on the do-loop pattern to recognize such loops,
92 where (1) the control part comprises of all insns defining and/or
93 using a certain 'count' register and (2) the loop count can be
94 adjusted by modifying this register prior to the loop.
95 TODO: Rely on cfgloop analysis instead. */
97 /* This page defines partial-schedule structures and functions for
100 typedef struct partial_schedule
*partial_schedule_ptr
;
101 typedef struct ps_insn
*ps_insn_ptr
;
103 /* The minimum (absolute) cycle that a node of ps was scheduled in. */
104 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
106 /* The maximum (absolute) cycle that a node of ps was scheduled in. */
107 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
109 /* Perform signed modulo, always returning a non-negative value. */
110 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
112 /* The number of different iterations the nodes in ps span, assuming
113 the stage boundaries are placed efficiently. */
114 #define CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \
116 /* The stage count of ps. */
117 #define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count)
119 /* A single instruction in the partial schedule. */
122 /* Identifies the instruction to be scheduled. Values smaller than
123 the ddg's num_nodes refer directly to ddg nodes. A value of
124 X - num_nodes refers to register move X. */
127 /* The (absolute) cycle in which the PS instruction is scheduled.
128 Same as SCHED_TIME (node). */
131 /* The next/prev PS_INSN in the same row. */
132 ps_insn_ptr next_in_row
,
137 /* Information about a register move that has been added to a partial
139 struct ps_reg_move_info
141 /* The source of the move is defined by the ps_insn with id DEF.
142 The destination is used by the ps_insns with the ids in USES. */
146 /* The original form of USES' instructions used OLD_REG, but they
147 should now use NEW_REG. */
151 /* The number of consecutive stages that the move occupies. */
152 int num_consecutive_stages
;
154 /* An instruction that sets NEW_REG to the correct value. The first
155 move associated with DEF will have an rhs of OLD_REG; later moves
156 use the result of the previous move. */
160 /* Holds the partial schedule as an array of II rows. Each entry of the
161 array points to a linked list of PS_INSNs, which represents the
162 instructions that are scheduled for that row. */
163 struct partial_schedule
165 int ii
; /* Number of rows in the partial schedule. */
166 int history
; /* Threshold for conflict checking using DFA. */
168 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
171 /* All the moves added for this partial schedule. Index X has
172 a ps_insn id of X + g->num_nodes. */
173 vec
<ps_reg_move_info
> reg_moves
;
175 /* rows_length[i] holds the number of instructions in the row.
176 It is used only (as an optimization) to back off quickly from
177 trying to schedule a node in a full row; that is, to avoid running
178 through futile DFA state transitions. */
181 /* The earliest absolute cycle of an insn in the partial schedule. */
184 /* The latest absolute cycle of an insn in the partial schedule. */
187 ddg_ptr g
; /* The DDG of the insns in the partial schedule. */
189 int stage_count
; /* The stage count of the partial schedule. */
193 static partial_schedule_ptr
create_partial_schedule (int ii
, ddg_ptr
, int history
);
194 static void free_partial_schedule (partial_schedule_ptr
);
195 static void reset_partial_schedule (partial_schedule_ptr
, int new_ii
);
196 void print_partial_schedule (partial_schedule_ptr
, FILE *);
197 static void verify_partial_schedule (partial_schedule_ptr
, sbitmap
);
198 static ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr
,
199 int, int, sbitmap
, sbitmap
);
200 static void rotate_partial_schedule (partial_schedule_ptr
, int);
201 void set_row_column_for_ps (partial_schedule_ptr
);
202 static void ps_insert_empty_row (partial_schedule_ptr
, int, sbitmap
);
203 static int compute_split_row (sbitmap
, int, int, int, ddg_node_ptr
);
206 /* This page defines constants and structures for the modulo scheduling
209 static int sms_order_nodes (ddg_ptr
, int, int *, int *);
210 static void set_node_sched_params (ddg_ptr
);
211 static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr
, int, int, int *);
212 static void permute_partial_schedule (partial_schedule_ptr
, rtx_insn
*);
213 static void generate_prolog_epilog (partial_schedule_ptr
, struct loop
*,
215 static int calculate_stage_count (partial_schedule_ptr
, int);
216 static void calculate_must_precede_follow (ddg_node_ptr
, int, int,
217 int, int, sbitmap
, sbitmap
, sbitmap
);
218 static int get_sched_window (partial_schedule_ptr
, ddg_node_ptr
,
219 sbitmap
, int, int *, int *, int *);
220 static bool try_scheduling_node_in_cycle (partial_schedule_ptr
, int, int,
221 sbitmap
, int *, sbitmap
, sbitmap
);
222 static void remove_node_from_ps (partial_schedule_ptr
, ps_insn_ptr
);
224 #define NODE_ASAP(node) ((node)->aux.count)
226 #define SCHED_PARAMS(x) (&node_sched_param_vec[x])
227 #define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
228 #define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
229 #define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
230 #define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
232 /* The scheduling parameters held for each node. */
233 typedef struct node_sched_params
235 int time
; /* The absolute scheduling cycle. */
237 int row
; /* Holds time % ii. */
238 int stage
; /* Holds time / ii. */
240 /* The column of a node inside the ps. If nodes u, v are on the same row,
241 u will precede v if column (u) < column (v). */
243 } *node_sched_params_ptr
;
245 /* The following three functions are copied from the current scheduler
246 code in order to use sched_analyze() for computing the dependencies.
247 They are used when initializing the sched_info structure. */
249 sms_print_insn (const rtx_insn
*insn
, int aligned ATTRIBUTE_UNUSED
)
253 sprintf (tmp
, "i%4d", INSN_UID (insn
));
258 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
259 regset used ATTRIBUTE_UNUSED
)
263 static struct common_sched_info_def sms_common_sched_info
;
265 static struct sched_deps_info_def sms_sched_deps_info
=
267 compute_jump_reg_dependencies
,
268 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
273 static struct haifa_sched_info sms_sched_info
=
282 NULL
, /* insn_finishes_block_p */
287 NULL
, NULL
, NULL
, NULL
,
292 /* Partial schedule instruction ID in PS is a register move. Return
293 information about it. */
294 static struct ps_reg_move_info
*
295 ps_reg_move (partial_schedule_ptr ps
, int id
)
297 gcc_checking_assert (id
>= ps
->g
->num_nodes
);
298 return &ps
->reg_moves
[id
- ps
->g
->num_nodes
];
301 /* Return the rtl instruction that is being scheduled by partial schedule
302 instruction ID, which belongs to schedule PS. */
304 ps_rtl_insn (partial_schedule_ptr ps
, int id
)
306 if (id
< ps
->g
->num_nodes
)
307 return ps
->g
->nodes
[id
].insn
;
309 return ps_reg_move (ps
, id
)->insn
;
312 /* Partial schedule instruction ID, which belongs to PS, occurred in
313 the original (unscheduled) loop. Return the first instruction
314 in the loop that was associated with ps_rtl_insn (PS, ID).
315 If the instruction had some notes before it, this is the first
318 ps_first_note (partial_schedule_ptr ps
, int id
)
320 gcc_assert (id
< ps
->g
->num_nodes
);
321 return ps
->g
->nodes
[id
].first_note
;
324 /* Return the number of consecutive stages that are occupied by
325 partial schedule instruction ID in PS. */
327 ps_num_consecutive_stages (partial_schedule_ptr ps
, int id
)
329 if (id
< ps
->g
->num_nodes
)
332 return ps_reg_move (ps
, id
)->num_consecutive_stages
;
335 /* Given HEAD and TAIL which are the first and last insns in a loop;
336 return the register which controls the loop. Return zero if it has
337 more than one occurrence in the loop besides the control part or the
338 do-loop pattern is not of the form we expect. */
340 doloop_register_get (rtx_insn
*head
, rtx_insn
*tail
)
343 rtx_insn
*insn
, *first_insn_not_to_check
;
348 if (!targetm
.code_for_doloop_end
)
351 /* TODO: Free SMS's dependence on doloop_condition_get. */
352 condition
= doloop_condition_get (tail
);
356 if (REG_P (XEXP (condition
, 0)))
357 reg
= XEXP (condition
, 0);
358 else if (GET_CODE (XEXP (condition
, 0)) == PLUS
359 && REG_P (XEXP (XEXP (condition
, 0), 0)))
360 reg
= XEXP (XEXP (condition
, 0), 0);
364 /* Check that the COUNT_REG has no other occurrences in the loop
365 until the decrement. We assume the control part consists of
366 either a single (parallel) branch-on-count or a (non-parallel)
367 branch immediately preceded by a single (decrement) insn. */
368 first_insn_not_to_check
= (GET_CODE (PATTERN (tail
)) == PARALLEL
? tail
369 : prev_nondebug_insn (tail
));
371 for (insn
= head
; insn
!= first_insn_not_to_check
; insn
= NEXT_INSN (insn
))
372 if (!DEBUG_INSN_P (insn
) && reg_mentioned_p (reg
, insn
))
376 fprintf (dump_file
, "SMS count_reg found ");
377 print_rtl_single (dump_file
, reg
);
378 fprintf (dump_file
, " outside control in insn:\n");
379 print_rtl_single (dump_file
, insn
);
388 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
389 that the number of iterations is a compile-time constant. If so,
390 return the rtx_insn that sets COUNT_REG to a constant, and set COUNT to
391 this constant. Otherwise return 0. */
393 const_iteration_count (rtx count_reg
, basic_block pre_header
,
397 rtx_insn
*head
, *tail
;
402 get_ebb_head_tail (pre_header
, pre_header
, &head
, &tail
);
404 for (insn
= tail
; insn
!= PREV_INSN (head
); insn
= PREV_INSN (insn
))
405 if (NONDEBUG_INSN_P (insn
) && single_set (insn
) &&
406 rtx_equal_p (count_reg
, SET_DEST (single_set (insn
))))
408 rtx pat
= single_set (insn
);
410 if (CONST_INT_P (SET_SRC (pat
)))
412 *count
= INTVAL (SET_SRC (pat
));
422 /* A very simple resource-based lower bound on the initiation interval.
423 ??? Improve the accuracy of this bound by considering the
424 utilization of various units. */
428 if (targetm
.sched
.sms_res_mii
)
429 return targetm
.sched
.sms_res_mii (g
);
431 return ((g
->num_nodes
- g
->num_debug
) / issue_rate
);
435 /* A vector that contains the sched data for each ps_insn. */
436 static vec
<node_sched_params
> node_sched_param_vec
;
438 /* Allocate sched_params for each node and initialize it. */
440 set_node_sched_params (ddg_ptr g
)
442 node_sched_param_vec
.truncate (0);
443 node_sched_param_vec
.safe_grow_cleared (g
->num_nodes
);
446 /* Make sure that node_sched_param_vec has an entry for every move in PS. */
448 extend_node_sched_params (partial_schedule_ptr ps
)
450 node_sched_param_vec
.safe_grow_cleared (ps
->g
->num_nodes
451 + ps
->reg_moves
.length ());
454 /* Update the sched_params (time, row and stage) for node U using the II,
455 the CYCLE of U and MIN_CYCLE.
456 We're not simply taking the following
457 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
458 because the stages may not be aligned on cycle 0. */
460 update_node_sched_params (int u
, int ii
, int cycle
, int min_cycle
)
462 int sc_until_cycle_zero
;
465 SCHED_TIME (u
) = cycle
;
466 SCHED_ROW (u
) = SMODULO (cycle
, ii
);
468 /* The calculation of stage count is done adding the number
469 of stages before cycle zero and after cycle zero. */
470 sc_until_cycle_zero
= CALC_STAGE_COUNT (-1, min_cycle
, ii
);
472 if (SCHED_TIME (u
) < 0)
474 stage
= CALC_STAGE_COUNT (-1, SCHED_TIME (u
), ii
);
475 SCHED_STAGE (u
) = sc_until_cycle_zero
- stage
;
479 stage
= CALC_STAGE_COUNT (SCHED_TIME (u
), 0, ii
);
480 SCHED_STAGE (u
) = sc_until_cycle_zero
+ stage
- 1;
485 print_node_sched_params (FILE *file
, int num_nodes
, partial_schedule_ptr ps
)
491 for (i
= 0; i
< num_nodes
; i
++)
493 node_sched_params_ptr nsp
= SCHED_PARAMS (i
);
495 fprintf (file
, "Node = %d; INSN = %d\n", i
,
496 INSN_UID (ps_rtl_insn (ps
, i
)));
497 fprintf (file
, " asap = %d:\n", NODE_ASAP (&ps
->g
->nodes
[i
]));
498 fprintf (file
, " time = %d:\n", nsp
->time
);
499 fprintf (file
, " stage = %d:\n", nsp
->stage
);
503 /* Set SCHED_COLUMN for each instruction in row ROW of PS. */
505 set_columns_for_row (partial_schedule_ptr ps
, int row
)
507 ps_insn_ptr cur_insn
;
511 for (cur_insn
= ps
->rows
[row
]; cur_insn
; cur_insn
= cur_insn
->next_in_row
)
512 SCHED_COLUMN (cur_insn
->id
) = column
++;
515 /* Set SCHED_COLUMN for each instruction in PS. */
517 set_columns_for_ps (partial_schedule_ptr ps
)
521 for (row
= 0; row
< ps
->ii
; row
++)
522 set_columns_for_row (ps
, row
);
525 /* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
526 Its single predecessor has already been scheduled, as has its
527 ddg node successors. (The move may have also another move as its
528 successor, in which case that successor will be scheduled later.)
530 The move is part of a chain that satisfies register dependencies
531 between a producing ddg node and various consuming ddg nodes.
532 If some of these dependencies have a distance of 1 (meaning that
533 the use is upward-exposed) then DISTANCE1_USES is nonnull and
534 contains the set of uses with distance-1 dependencies.
535 DISTANCE1_USES is null otherwise.
537 MUST_FOLLOW is a scratch bitmap that is big enough to hold
538 all current ps_insn ids.
540 Return true on success. */
542 schedule_reg_move (partial_schedule_ptr ps
, int i_reg_move
,
543 sbitmap distance1_uses
, sbitmap must_follow
)
546 int this_time
, this_distance
, this_start
, this_end
, this_latency
;
547 int start
, end
, c
, ii
;
548 sbitmap_iterator sbi
;
549 ps_reg_move_info
*move
;
553 move
= ps_reg_move (ps
, i_reg_move
);
557 fprintf (dump_file
, "Scheduling register move INSN %d; ii = %d"
558 ", min cycle = %d\n\n", INSN_UID (move
->insn
), ii
,
560 print_rtl_single (dump_file
, move
->insn
);
561 fprintf (dump_file
, "\n%11s %11s %5s\n", "start", "end", "time");
562 fprintf (dump_file
, "=========== =========== =====\n");
568 /* For dependencies of distance 1 between a producer ddg node A
569 and consumer ddg node B, we have a chain of dependencies:
571 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
573 where Mi is the ith move. For dependencies of distance 0 between
574 a producer ddg node A and consumer ddg node C, we have a chain of
577 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
579 where Mi' occupies the same position as Mi but occurs a stage later.
580 We can only schedule each move once, so if we have both types of
581 chain, we model the second as:
583 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
585 First handle the dependencies between the previously-scheduled
586 predecessor and the move. */
587 this_insn
= ps_rtl_insn (ps
, move
->def
);
588 this_latency
= insn_latency (this_insn
, move
->insn
);
589 this_distance
= distance1_uses
&& move
->def
< ps
->g
->num_nodes
? 1 : 0;
590 this_time
= SCHED_TIME (move
->def
) - this_distance
* ii
;
591 this_start
= this_time
+ this_latency
;
592 this_end
= this_time
+ ii
;
594 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
595 this_start
, this_end
, SCHED_TIME (move
->def
),
596 INSN_UID (this_insn
), this_latency
, this_distance
,
597 INSN_UID (move
->insn
));
599 if (start
< this_start
)
604 /* Handle the dependencies between the move and previously-scheduled
606 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, u
, sbi
)
608 this_insn
= ps_rtl_insn (ps
, u
);
609 this_latency
= insn_latency (move
->insn
, this_insn
);
610 if (distance1_uses
&& !bitmap_bit_p (distance1_uses
, u
))
614 this_time
= SCHED_TIME (u
) + this_distance
* ii
;
615 this_start
= this_time
- ii
;
616 this_end
= this_time
- this_latency
;
618 fprintf (dump_file
, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
619 this_start
, this_end
, SCHED_TIME (u
), INSN_UID (move
->insn
),
620 this_latency
, this_distance
, INSN_UID (this_insn
));
622 if (start
< this_start
)
630 fprintf (dump_file
, "----------- ----------- -----\n");
631 fprintf (dump_file
, "%11d %11d %5s %s\n", start
, end
, "", "(max, min)");
634 bitmap_clear (must_follow
);
635 bitmap_set_bit (must_follow
, move
->def
);
637 start
= MAX (start
, end
- (ii
- 1));
638 for (c
= end
; c
>= start
; c
--)
640 psi
= ps_add_node_check_conflicts (ps
, i_reg_move
, c
,
641 move
->uses
, must_follow
);
644 update_node_sched_params (i_reg_move
, ii
, c
, PS_MIN_CYCLE (ps
));
646 fprintf (dump_file
, "\nScheduled register move INSN %d at"
647 " time %d, row %d\n\n", INSN_UID (move
->insn
), c
,
648 SCHED_ROW (i_reg_move
));
654 fprintf (dump_file
, "\nNo available slot\n\n");
660 Breaking intra-loop register anti-dependences:
661 Each intra-loop register anti-dependence implies a cross-iteration true
662 dependence of distance 1. Therefore, we can remove such false dependencies
663 and figure out if the partial schedule broke them by checking if (for a
664 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
665 if so generate a register move. The number of such moves is equal to:
666 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
667 nreg_moves = ----------------------------------- + 1 - { dependence.
671 schedule_reg_moves (partial_schedule_ptr ps
)
677 for (i
= 0; i
< g
->num_nodes
; i
++)
679 ddg_node_ptr u
= &g
->nodes
[i
];
681 int nreg_moves
= 0, i_reg_move
;
682 rtx prev_reg
, old_reg
;
686 sbitmap distance1_uses
;
687 rtx set
= single_set (u
->insn
);
689 /* Skip instructions that do not set a register. */
690 if ((set
&& !REG_P (SET_DEST (set
))))
693 /* Compute the number of reg_moves needed for u, by looking at life
694 ranges started at u (excluding self-loops). */
695 distances
[0] = distances
[1] = false;
696 for (e
= u
->out
; e
; e
= e
->next_out
)
697 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
699 int nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
700 - SCHED_TIME (e
->src
->cuid
)) / ii
;
702 if (e
->distance
== 1)
703 nreg_moves4e
= (SCHED_TIME (e
->dest
->cuid
)
704 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
706 /* If dest precedes src in the schedule of the kernel, then dest
707 will read before src writes and we can save one reg_copy. */
708 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
709 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
712 if (nreg_moves4e
>= 1)
714 /* !single_set instructions are not supported yet and
715 thus we do not except to encounter them in the loop
716 except from the doloop part. For the latter case
717 we assume no regmoves are generated as the doloop
718 instructions are tied to the branch with an edge. */
720 /* If the instruction contains auto-inc register then
721 validate that the regmov is being generated for the
722 target regsiter rather then the inc'ed register. */
723 gcc_assert (!autoinc_var_is_used_p (u
->insn
, e
->dest
->insn
));
728 gcc_assert (e
->distance
< 2);
729 distances
[e
->distance
] = true;
731 nreg_moves
= MAX (nreg_moves
, nreg_moves4e
);
737 /* Create NREG_MOVES register moves. */
738 first_move
= ps
->reg_moves
.length ();
739 ps
->reg_moves
.safe_grow_cleared (first_move
+ nreg_moves
);
740 extend_node_sched_params (ps
);
742 /* Record the moves associated with this node. */
743 first_move
+= ps
->g
->num_nodes
;
745 /* Generate each move. */
746 old_reg
= prev_reg
= SET_DEST (single_set (u
->insn
));
747 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
749 ps_reg_move_info
*move
= ps_reg_move (ps
, first_move
+ i_reg_move
);
751 move
->def
= i_reg_move
> 0 ? first_move
+ i_reg_move
- 1 : i
;
752 move
->uses
= sbitmap_alloc (first_move
+ nreg_moves
);
753 move
->old_reg
= old_reg
;
754 move
->new_reg
= gen_reg_rtx (GET_MODE (prev_reg
));
755 move
->num_consecutive_stages
= distances
[0] && distances
[1] ? 2 : 1;
756 move
->insn
= gen_move_insn (move
->new_reg
, copy_rtx (prev_reg
));
757 bitmap_clear (move
->uses
);
759 prev_reg
= move
->new_reg
;
762 distance1_uses
= distances
[1] ? sbitmap_alloc (g
->num_nodes
) : NULL
;
765 bitmap_clear (distance1_uses
);
767 /* Every use of the register defined by node may require a different
768 copy of this register, depending on the time the use is scheduled.
769 Record which uses require which move results. */
770 for (e
= u
->out
; e
; e
= e
->next_out
)
771 if (e
->type
== TRUE_DEP
&& e
->dest
!= e
->src
)
773 int dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
774 - SCHED_TIME (e
->src
->cuid
)) / ii
;
776 if (e
->distance
== 1)
777 dest_copy
= (SCHED_TIME (e
->dest
->cuid
)
778 - SCHED_TIME (e
->src
->cuid
) + ii
) / ii
;
780 if (SCHED_ROW (e
->dest
->cuid
) == SCHED_ROW (e
->src
->cuid
)
781 && SCHED_COLUMN (e
->dest
->cuid
) < SCHED_COLUMN (e
->src
->cuid
))
786 ps_reg_move_info
*move
;
788 move
= ps_reg_move (ps
, first_move
+ dest_copy
- 1);
789 bitmap_set_bit (move
->uses
, e
->dest
->cuid
);
790 if (e
->distance
== 1)
791 bitmap_set_bit (distance1_uses
, e
->dest
->cuid
);
795 must_follow
= sbitmap_alloc (first_move
+ nreg_moves
);
796 for (i_reg_move
= 0; i_reg_move
< nreg_moves
; i_reg_move
++)
797 if (!schedule_reg_move (ps
, first_move
+ i_reg_move
,
798 distance1_uses
, must_follow
))
800 sbitmap_free (must_follow
);
802 sbitmap_free (distance1_uses
);
803 if (i_reg_move
< nreg_moves
)
809 /* Emit the moves associatied with PS. Apply the substitutions
810 associated with them. */
812 apply_reg_moves (partial_schedule_ptr ps
)
814 ps_reg_move_info
*move
;
817 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
820 sbitmap_iterator sbi
;
822 EXECUTE_IF_SET_IN_BITMAP (move
->uses
, 0, i_use
, sbi
)
824 replace_rtx (ps
->g
->nodes
[i_use
].insn
, move
->old_reg
, move
->new_reg
);
825 df_insn_rescan (ps
->g
->nodes
[i_use
].insn
);
830 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
831 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
832 will move to cycle zero. */
834 reset_sched_times (partial_schedule_ptr ps
, int amount
)
838 ps_insn_ptr crr_insn
;
840 for (row
= 0; row
< ii
; row
++)
841 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
843 int u
= crr_insn
->id
;
844 int normalized_time
= SCHED_TIME (u
) - amount
;
845 int new_min_cycle
= PS_MIN_CYCLE (ps
) - amount
;
849 /* Print the scheduling times after the rotation. */
850 rtx_insn
*insn
= ps_rtl_insn (ps
, u
);
852 fprintf (dump_file
, "crr_insn->node=%d (insn id %d), "
853 "crr_insn->cycle=%d, min_cycle=%d", u
,
854 INSN_UID (insn
), normalized_time
, new_min_cycle
);
856 fprintf (dump_file
, " (branch)");
857 fprintf (dump_file
, "\n");
860 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
861 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
863 crr_insn
->cycle
= normalized_time
;
864 update_node_sched_params (u
, ii
, normalized_time
, new_min_cycle
);
868 /* Permute the insns according to their order in PS, from row 0 to
869 row ii-1, and position them right before LAST. This schedules
870 the insns of the loop kernel. */
872 permute_partial_schedule (partial_schedule_ptr ps
, rtx_insn
*last
)
878 for (row
= 0; row
< ii
; row
++)
879 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
881 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_ij
->id
);
883 if (PREV_INSN (last
) != insn
)
885 if (ps_ij
->id
< ps
->g
->num_nodes
)
886 reorder_insns_nobb (ps_first_note (ps
, ps_ij
->id
), insn
,
889 add_insn_before (insn
, last
, NULL
);
894 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
895 respectively only if cycle C falls on the border of the scheduling
896 window boundaries marked by START and END cycles. STEP is the
897 direction of the window. */
899 set_must_precede_follow (sbitmap
*tmp_follow
, sbitmap must_follow
,
900 sbitmap
*tmp_precede
, sbitmap must_precede
, int c
,
901 int start
, int end
, int step
)
909 *tmp_precede
= must_precede
;
910 else /* step == -1. */
911 *tmp_follow
= must_follow
;
916 *tmp_follow
= must_follow
;
917 else /* step == -1. */
918 *tmp_precede
= must_precede
;
923 /* Return True if the branch can be moved to row ii-1 while
924 normalizing the partial schedule PS to start from cycle zero and thus
925 optimize the SC. Otherwise return False. */
927 optimize_sc (partial_schedule_ptr ps
, ddg_ptr g
)
929 int amount
= PS_MIN_CYCLE (ps
);
930 sbitmap sched_nodes
= sbitmap_alloc (g
->num_nodes
);
931 int start
, end
, step
;
934 int stage_count
, stage_count_curr
;
936 /* Compare the SC after normalization and SC after bringing the branch
937 to row ii-1. If they are equal just bail out. */
938 stage_count
= calculate_stage_count (ps
, amount
);
940 calculate_stage_count (ps
, SCHED_TIME (g
->closing_branch
->cuid
) - (ii
- 1));
942 if (stage_count
== stage_count_curr
)
945 fprintf (dump_file
, "SMS SC already optimized.\n");
953 fprintf (dump_file
, "SMS Trying to optimize branch location\n");
954 fprintf (dump_file
, "SMS partial schedule before trial:\n");
955 print_partial_schedule (ps
, dump_file
);
958 /* First, normalize the partial scheduling. */
959 reset_sched_times (ps
, amount
);
960 rotate_partial_schedule (ps
, amount
);
964 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
966 print_partial_schedule (ps
, dump_file
);
969 if (SMODULO (SCHED_TIME (g
->closing_branch
->cuid
), ii
) == ii
- 1)
975 bitmap_ones (sched_nodes
);
977 /* Calculate the new placement of the branch. It should be in row
978 ii-1 and fall into it's scheduling window. */
979 if (get_sched_window (ps
, g
->closing_branch
, sched_nodes
, ii
, &start
,
983 ps_insn_ptr next_ps_i
;
984 int branch_cycle
= SCHED_TIME (g
->closing_branch
->cuid
);
985 int row
= SMODULO (branch_cycle
, ps
->ii
);
987 sbitmap must_precede
, must_follow
, tmp_precede
, tmp_follow
;
991 fprintf (dump_file
, "\nTrying to schedule node %d "
992 "INSN = %d in (%d .. %d) step %d\n",
993 g
->closing_branch
->cuid
,
994 (INSN_UID (g
->closing_branch
->insn
)), start
, end
, step
);
996 gcc_assert ((step
> 0 && start
< end
) || (step
< 0 && start
> end
));
999 c
= start
+ ii
- SMODULO (start
, ii
) - 1;
1000 gcc_assert (c
>= start
);
1006 "SMS failed to schedule branch at cycle: %d\n", c
);
1012 c
= start
- SMODULO (start
, ii
) - 1;
1013 gcc_assert (c
<= start
);
1019 "SMS failed to schedule branch at cycle: %d\n", c
);
1025 must_precede
= sbitmap_alloc (g
->num_nodes
);
1026 must_follow
= sbitmap_alloc (g
->num_nodes
);
1028 /* Try to schedule the branch is it's new cycle. */
1029 calculate_must_precede_follow (g
->closing_branch
, start
, end
,
1030 step
, ii
, sched_nodes
,
1031 must_precede
, must_follow
);
1033 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1034 must_precede
, c
, start
, end
, step
);
1036 /* Find the element in the partial schedule related to the closing
1037 branch so we can remove it from it's current cycle. */
1038 for (next_ps_i
= ps
->rows
[row
];
1039 next_ps_i
; next_ps_i
= next_ps_i
->next_in_row
)
1040 if (next_ps_i
->id
== g
->closing_branch
->cuid
)
1043 remove_node_from_ps (ps
, next_ps_i
);
1045 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
, c
,
1046 sched_nodes
, &num_splits
,
1047 tmp_precede
, tmp_follow
);
1048 gcc_assert (num_splits
== 0);
1053 "SMS failed to schedule branch at cycle: %d, "
1054 "bringing it back to cycle %d\n", c
, branch_cycle
);
1056 /* The branch was failed to be placed in row ii - 1.
1057 Put it back in it's original place in the partial
1059 set_must_precede_follow (&tmp_follow
, must_follow
, &tmp_precede
,
1060 must_precede
, branch_cycle
, start
, end
,
1063 try_scheduling_node_in_cycle (ps
, g
->closing_branch
->cuid
,
1064 branch_cycle
, sched_nodes
,
1065 &num_splits
, tmp_precede
,
1067 gcc_assert (success
&& (num_splits
== 0));
1072 /* The branch is placed in row ii - 1. */
1075 "SMS success in moving branch to cycle %d\n", c
);
1077 update_node_sched_params (g
->closing_branch
->cuid
, ii
, c
,
1082 free (must_precede
);
1092 duplicate_insns_of_cycles (partial_schedule_ptr ps
, int from_stage
,
1093 int to_stage
, rtx count_reg
)
1098 for (row
= 0; row
< ps
->ii
; row
++)
1099 for (ps_ij
= ps
->rows
[row
]; ps_ij
; ps_ij
= ps_ij
->next_in_row
)
1102 int first_u
, last_u
;
1105 /* Do not duplicate any insn which refers to count_reg as it
1106 belongs to the control part.
1107 The closing branch is scheduled as well and thus should
1109 TODO: This should be done by analyzing the control part of
1111 u_insn
= ps_rtl_insn (ps
, u
);
1112 if (reg_mentioned_p (count_reg
, u_insn
)
1116 first_u
= SCHED_STAGE (u
);
1117 last_u
= first_u
+ ps_num_consecutive_stages (ps
, u
) - 1;
1118 if (from_stage
<= last_u
&& to_stage
>= first_u
)
1120 if (u
< ps
->g
->num_nodes
)
1121 duplicate_insn_chain (ps_first_note (ps
, u
), u_insn
);
1123 emit_insn (copy_rtx (PATTERN (u_insn
)));
1129 /* Generate the instructions (including reg_moves) for prolog & epilog. */
1131 generate_prolog_epilog (partial_schedule_ptr ps
, struct loop
*loop
,
1132 rtx count_reg
, rtx count_init
)
1135 int last_stage
= PS_STAGE_COUNT (ps
) - 1;
1138 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1143 /* Generate instructions at the beginning of the prolog to
1144 adjust the loop count by STAGE_COUNT. If loop count is constant
1145 (count_init), this constant is adjusted by STAGE_COUNT in
1146 generate_prolog_epilog function. */
1147 rtx sub_reg
= NULL_RTX
;
1149 sub_reg
= expand_simple_binop (GET_MODE (count_reg
), MINUS
, count_reg
,
1150 gen_int_mode (last_stage
,
1151 GET_MODE (count_reg
)),
1152 count_reg
, 1, OPTAB_DIRECT
);
1153 gcc_assert (REG_P (sub_reg
));
1154 if (REGNO (sub_reg
) != REGNO (count_reg
))
1155 emit_move_insn (count_reg
, sub_reg
);
1158 for (i
= 0; i
< last_stage
; i
++)
1159 duplicate_insns_of_cycles (ps
, 0, i
, count_reg
);
1161 /* Put the prolog on the entry edge. */
1162 e
= loop_preheader_edge (loop
);
1163 split_edge_and_insert (e
, get_insns ());
1164 if (!flag_resched_modulo_sched
)
1165 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1169 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1172 for (i
= 0; i
< last_stage
; i
++)
1173 duplicate_insns_of_cycles (ps
, i
+ 1, last_stage
, count_reg
);
1175 /* Put the epilogue on the exit edge. */
1176 gcc_assert (single_exit (loop
));
1177 e
= single_exit (loop
);
1178 split_edge_and_insert (e
, get_insns ());
1179 if (!flag_resched_modulo_sched
)
1180 e
->dest
->flags
|= BB_DISABLE_SCHEDULE
;
1185 /* Mark LOOP as software pipelined so the later
1186 scheduling passes don't touch it. */
1188 mark_loop_unsched (struct loop
*loop
)
1191 basic_block
*bbs
= get_loop_body (loop
);
1193 for (i
= 0; i
< loop
->num_nodes
; i
++)
1194 bbs
[i
]->flags
|= BB_DISABLE_SCHEDULE
;
1199 /* Return true if all the BBs of the loop are empty except the
1202 loop_single_full_bb_p (struct loop
*loop
)
1205 basic_block
*bbs
= get_loop_body (loop
);
1207 for (i
= 0; i
< loop
->num_nodes
; i
++)
1209 rtx_insn
*head
, *tail
;
1210 bool empty_bb
= true;
1212 if (bbs
[i
] == loop
->header
)
1215 /* Make sure that basic blocks other than the header
1216 have only notes labels or jumps. */
1217 get_ebb_head_tail (bbs
[i
], bbs
[i
], &head
, &tail
);
1218 for (; head
!= NEXT_INSN (tail
); head
= NEXT_INSN (head
))
1220 if (NOTE_P (head
) || LABEL_P (head
)
1221 || (INSN_P (head
) && (DEBUG_INSN_P (head
) || JUMP_P (head
))))
1237 /* Dump file:line from INSN's location info to dump_file. */
1240 dump_insn_location (rtx_insn
*insn
)
1242 if (dump_file
&& INSN_HAS_LOCATION (insn
))
1244 expanded_location xloc
= insn_location (insn
);
1245 fprintf (dump_file
, " %s:%i", xloc
.file
, xloc
.line
);
1249 /* A simple loop from SMS point of view; it is a loop that is composed of
1250 either a single basic block or two BBs - a header and a latch. */
1251 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1252 && (EDGE_COUNT (loop->latch->preds) == 1) \
1253 && (EDGE_COUNT (loop->latch->succs) == 1))
1255 /* Return true if the loop is in its canonical form and false if not.
1256 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1258 loop_canon_p (struct loop
*loop
)
1261 if (loop
->inner
|| !loop_outer (loop
))
1264 fprintf (dump_file
, "SMS loop inner or !loop_outer\n");
1268 if (!single_exit (loop
))
1272 rtx_insn
*insn
= BB_END (loop
->header
);
1274 fprintf (dump_file
, "SMS loop many exits");
1275 dump_insn_location (insn
);
1276 fprintf (dump_file
, "\n");
1281 if (! SIMPLE_SMS_LOOP_P (loop
) && ! loop_single_full_bb_p (loop
))
1285 rtx_insn
*insn
= BB_END (loop
->header
);
1287 fprintf (dump_file
, "SMS loop many BBs.");
1288 dump_insn_location (insn
);
1289 fprintf (dump_file
, "\n");
1297 /* If there are more than one entry for the loop,
1298 make it one by splitting the first entry edge and
1299 redirecting the others to the new BB. */
1301 canon_loop (struct loop
*loop
)
1306 /* Avoid annoying special cases of edges going to exit
1308 FOR_EACH_EDGE (e
, i
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
1309 if ((e
->flags
& EDGE_FALLTHRU
) && (EDGE_COUNT (e
->src
->succs
) > 1))
1312 if (loop
->latch
== loop
->header
1313 || EDGE_COUNT (loop
->latch
->succs
) > 1)
1315 FOR_EACH_EDGE (e
, i
, loop
->header
->preds
)
1316 if (e
->src
== loop
->latch
)
1324 setup_sched_infos (void)
1326 memcpy (&sms_common_sched_info
, &haifa_common_sched_info
,
1327 sizeof (sms_common_sched_info
));
1328 sms_common_sched_info
.sched_pass_id
= SCHED_SMS_PASS
;
1329 common_sched_info
= &sms_common_sched_info
;
1331 sched_deps_info
= &sms_sched_deps_info
;
1332 current_sched_info
= &sms_sched_info
;
1335 /* Probability in % that the sms-ed loop rolls enough so that optimized
1336 version may be entered. Just a guess. */
1337 #define PROB_SMS_ENOUGH_ITERATIONS 80
1339 /* Used to calculate the upper bound of ii. */
1340 #define MAXII_FACTOR 2
1342 /* Main entry point, perform SMS scheduling on the loops of the function
1343 that consist of single basic blocks. */
1350 int maxii
, max_asap
;
1351 partial_schedule_ptr ps
;
1352 basic_block bb
= NULL
;
1354 basic_block condition_bb
= NULL
;
1356 gcov_type trip_count
= 0;
1358 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1359 | LOOPS_HAVE_RECORDED_EXITS
);
1360 if (number_of_loops (cfun
) <= 1)
1362 loop_optimizer_finalize ();
1363 return; /* There are no loops to schedule. */
1366 /* Initialize issue_rate. */
1367 if (targetm
.sched
.issue_rate
)
1369 int temp
= reload_completed
;
1371 reload_completed
= 1;
1372 issue_rate
= targetm
.sched
.issue_rate ();
1373 reload_completed
= temp
;
1378 /* Initialize the scheduler. */
1379 setup_sched_infos ();
1380 haifa_sched_init ();
1382 /* Allocate memory to hold the DDG array one entry for each loop.
1383 We use loop->num as index into this array. */
1384 g_arr
= XCNEWVEC (ddg_ptr
, number_of_loops (cfun
));
1388 fprintf (dump_file
, "\n\nSMS analysis phase\n");
1389 fprintf (dump_file
, "===================\n\n");
1392 /* Build DDGs for all the relevant loops and hold them in G_ARR
1393 indexed by the loop index. */
1394 FOR_EACH_LOOP (loop
, 0)
1396 rtx_insn
*head
, *tail
;
1399 /* For debugging. */
1400 if (dbg_cnt (sms_sched_loop
) == false)
1403 fprintf (dump_file
, "SMS reached max limit... \n");
1410 rtx_insn
*insn
= BB_END (loop
->header
);
1412 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1413 dump_insn_location (insn
);
1414 fprintf (dump_file
, "\n");
1417 if (! loop_canon_p (loop
))
1420 if (! loop_single_full_bb_p (loop
))
1423 fprintf (dump_file
, "SMS not loop_single_full_bb_p\n");
1429 get_ebb_head_tail (bb
, bb
, &head
, &tail
);
1430 latch_edge
= loop_latch_edge (loop
);
1431 gcc_assert (single_exit (loop
));
1432 if (single_exit (loop
)->count
)
1433 trip_count
= latch_edge
->count
/ single_exit (loop
)->count
;
1435 /* Perform SMS only on loops that their average count is above threshold. */
1437 if ( latch_edge
->count
1438 && (latch_edge
->count
< single_exit (loop
)->count
* SMS_LOOP_AVERAGE_COUNT_THRESHOLD
))
1442 dump_insn_location (tail
);
1443 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1444 if (profile_info
&& flag_branch_probabilities
)
1446 fprintf (dump_file
, "SMS loop-count ");
1447 fprintf (dump_file
, "%" PRId64
,
1448 (int64_t) bb
->count
);
1449 fprintf (dump_file
, "\n");
1450 fprintf (dump_file
, "SMS trip-count ");
1451 fprintf (dump_file
, "%" PRId64
,
1452 (int64_t) trip_count
);
1453 fprintf (dump_file
, "\n");
1454 fprintf (dump_file
, "SMS profile-sum-max ");
1455 fprintf (dump_file
, "%" PRId64
,
1456 (int64_t) profile_info
->sum_max
);
1457 fprintf (dump_file
, "\n");
1463 /* Make sure this is a doloop. */
1464 if ( !(count_reg
= doloop_register_get (head
, tail
)))
1467 fprintf (dump_file
, "SMS doloop_register_get failed\n");
1471 /* Don't handle BBs with calls or barriers
1472 or !single_set with the exception of instructions that include
1473 count_reg---these instructions are part of the control part
1474 that do-loop recognizes.
1475 ??? Should handle insns defining subregs. */
1476 for (insn
= head
; insn
!= NEXT_INSN (tail
); insn
= NEXT_INSN (insn
))
1482 || (NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1483 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
1484 && !reg_mentioned_p (count_reg
, insn
))
1485 || (INSN_P (insn
) && (set
= single_set (insn
))
1486 && GET_CODE (SET_DEST (set
)) == SUBREG
))
1490 if (insn
!= NEXT_INSN (tail
))
1495 fprintf (dump_file
, "SMS loop-with-call\n");
1496 else if (BARRIER_P (insn
))
1497 fprintf (dump_file
, "SMS loop-with-barrier\n");
1498 else if ((NONDEBUG_INSN_P (insn
) && !JUMP_P (insn
)
1499 && !single_set (insn
) && GET_CODE (PATTERN (insn
)) != USE
))
1500 fprintf (dump_file
, "SMS loop-with-not-single-set\n");
1502 fprintf (dump_file
, "SMS loop with subreg in lhs\n");
1503 print_rtl_single (dump_file
, insn
);
1509 /* Always schedule the closing branch with the rest of the
1510 instructions. The branch is rotated to be in row ii-1 at the
1511 end of the scheduling procedure to make sure it's the last
1512 instruction in the iteration. */
1513 if (! (g
= create_ddg (bb
, 1)))
1516 fprintf (dump_file
, "SMS create_ddg failed\n");
1520 g_arr
[loop
->num
] = g
;
1522 fprintf (dump_file
, "...OK\n");
1527 fprintf (dump_file
, "\nSMS transformation phase\n");
1528 fprintf (dump_file
, "=========================\n\n");
1531 /* We don't want to perform SMS on new loops - created by versioning. */
1532 FOR_EACH_LOOP (loop
, 0)
1534 rtx_insn
*head
, *tail
;
1536 rtx_insn
*count_init
;
1537 int mii
, rec_mii
, stage_count
, min_cycle
;
1538 int64_t loop_count
= 0;
1541 if (! (g
= g_arr
[loop
->num
]))
1546 rtx_insn
*insn
= BB_END (loop
->header
);
1548 fprintf (dump_file
, "SMS loop num: %d", loop
->num
);
1549 dump_insn_location (insn
);
1550 fprintf (dump_file
, "\n");
1552 print_ddg (dump_file
, g
);
1555 get_ebb_head_tail (loop
->header
, loop
->header
, &head
, &tail
);
1557 latch_edge
= loop_latch_edge (loop
);
1558 gcc_assert (single_exit (loop
));
1559 if (single_exit (loop
)->count
)
1560 trip_count
= latch_edge
->count
/ single_exit (loop
)->count
;
1564 dump_insn_location (tail
);
1565 fprintf (dump_file
, "\nSMS single-bb-loop\n");
1566 if (profile_info
&& flag_branch_probabilities
)
1568 fprintf (dump_file
, "SMS loop-count ");
1569 fprintf (dump_file
, "%" PRId64
,
1570 (int64_t) bb
->count
);
1571 fprintf (dump_file
, "\n");
1572 fprintf (dump_file
, "SMS profile-sum-max ");
1573 fprintf (dump_file
, "%" PRId64
,
1574 (int64_t) profile_info
->sum_max
);
1575 fprintf (dump_file
, "\n");
1577 fprintf (dump_file
, "SMS doloop\n");
1578 fprintf (dump_file
, "SMS built-ddg %d\n", g
->num_nodes
);
1579 fprintf (dump_file
, "SMS num-loads %d\n", g
->num_loads
);
1580 fprintf (dump_file
, "SMS num-stores %d\n", g
->num_stores
);
1584 /* In case of th loop have doloop register it gets special
1587 if ((count_reg
= doloop_register_get (head
, tail
)))
1589 basic_block pre_header
;
1591 pre_header
= loop_preheader_edge (loop
)->src
;
1592 count_init
= const_iteration_count (count_reg
, pre_header
,
1595 gcc_assert (count_reg
);
1597 if (dump_file
&& count_init
)
1599 fprintf (dump_file
, "SMS const-doloop ");
1600 fprintf (dump_file
, "%" PRId64
,
1602 fprintf (dump_file
, "\n");
1605 node_order
= XNEWVEC (int, g
->num_nodes
);
1607 mii
= 1; /* Need to pass some estimate of mii. */
1608 rec_mii
= sms_order_nodes (g
, mii
, node_order
, &max_asap
);
1609 mii
= MAX (res_MII (g
), rec_mii
);
1610 maxii
= MAX (max_asap
, MAXII_FACTOR
* mii
);
1613 fprintf (dump_file
, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1614 rec_mii
, mii
, maxii
);
1618 set_node_sched_params (g
);
1622 ps
= sms_schedule_by_order (g
, mii
, maxii
, node_order
);
1626 /* Try to achieve optimized SC by normalizing the partial
1627 schedule (having the cycles start from cycle zero).
1628 The branch location must be placed in row ii-1 in the
1629 final scheduling. If failed, shift all instructions to
1630 position the branch in row ii-1. */
1631 opt_sc_p
= optimize_sc (ps
, g
);
1633 stage_count
= calculate_stage_count (ps
, 0);
1636 /* Bring the branch to cycle ii-1. */
1637 int amount
= (SCHED_TIME (g
->closing_branch
->cuid
)
1641 fprintf (dump_file
, "SMS schedule branch at cycle ii-1\n");
1643 stage_count
= calculate_stage_count (ps
, amount
);
1646 gcc_assert (stage_count
>= 1);
1649 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
1650 1 means that there is no interleaving between iterations thus
1651 we let the scheduling passes do the job in this case. */
1652 if (stage_count
< PARAM_VALUE (PARAM_SMS_MIN_SC
)
1653 || (count_init
&& (loop_count
<= stage_count
))
1654 || (flag_branch_probabilities
&& (trip_count
<= stage_count
)))
1658 fprintf (dump_file
, "SMS failed... \n");
1659 fprintf (dump_file
, "SMS sched-failed (stage-count=%d,"
1660 " loop-count=", stage_count
);
1661 fprintf (dump_file
, "%" PRId64
, loop_count
);
1662 fprintf (dump_file
, ", trip-count=");
1663 fprintf (dump_file
, "%" PRId64
, trip_count
);
1664 fprintf (dump_file
, ")\n");
1671 /* Rotate the partial schedule to have the branch in row ii-1. */
1672 int amount
= SCHED_TIME (g
->closing_branch
->cuid
) - (ps
->ii
- 1);
1674 reset_sched_times (ps
, amount
);
1675 rotate_partial_schedule (ps
, amount
);
1678 set_columns_for_ps (ps
);
1680 min_cycle
= PS_MIN_CYCLE (ps
) - SMODULO (PS_MIN_CYCLE (ps
), ps
->ii
);
1681 if (!schedule_reg_moves (ps
))
1684 free_partial_schedule (ps
);
1688 /* Moves that handle incoming values might have been added
1689 to a new first stage. Bump the stage count if so.
1691 ??? Perhaps we could consider rotating the schedule here
1693 if (PS_MIN_CYCLE (ps
) < min_cycle
)
1695 reset_sched_times (ps
, 0);
1699 /* The stage count should now be correct without rotation. */
1700 gcc_checking_assert (stage_count
== calculate_stage_count (ps
, 0));
1701 PS_STAGE_COUNT (ps
) = stage_count
;
1707 dump_insn_location (tail
);
1708 fprintf (dump_file
, " SMS succeeded %d %d (with ii, sc)\n",
1709 ps
->ii
, stage_count
);
1710 print_partial_schedule (ps
, dump_file
);
1713 /* case the BCT count is not known , Do loop-versioning */
1714 if (count_reg
&& ! count_init
)
1716 rtx comp_rtx
= gen_rtx_GT (VOIDmode
, count_reg
,
1717 gen_int_mode (stage_count
,
1718 GET_MODE (count_reg
)));
1719 unsigned prob
= (PROB_SMS_ENOUGH_ITERATIONS
1720 * REG_BR_PROB_BASE
) / 100;
1722 loop_version (loop
, comp_rtx
, &condition_bb
,
1723 prob
, prob
, REG_BR_PROB_BASE
- prob
,
1727 /* Set new iteration count of loop kernel. */
1728 if (count_reg
&& count_init
)
1729 SET_SRC (single_set (count_init
)) = GEN_INT (loop_count
1732 /* Now apply the scheduled kernel to the RTL of the loop. */
1733 permute_partial_schedule (ps
, g
->closing_branch
->first_note
);
1735 /* Mark this loop as software pipelined so the later
1736 scheduling passes don't touch it. */
1737 if (! flag_resched_modulo_sched
)
1738 mark_loop_unsched (loop
);
1740 /* The life-info is not valid any more. */
1741 df_set_bb_dirty (g
->bb
);
1743 apply_reg_moves (ps
);
1745 print_node_sched_params (dump_file
, g
->num_nodes
, ps
);
1746 /* Generate prolog and epilog. */
1747 generate_prolog_epilog (ps
, loop
, count_reg
, count_init
);
1751 free_partial_schedule (ps
);
1752 node_sched_param_vec
.release ();
1759 /* Release scheduler data, needed until now because of DFA. */
1760 haifa_sched_finish ();
1761 loop_optimizer_finalize ();
1764 /* The SMS scheduling algorithm itself
1765 -----------------------------------
1766 Input: 'O' an ordered list of insns of a loop.
1767 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1769 'Q' is the empty Set
1770 'PS' is the partial schedule; it holds the currently scheduled nodes with
1772 'PSP' previously scheduled predecessors.
1773 'PSS' previously scheduled successors.
1774 't(u)' the cycle where u is scheduled.
1775 'l(u)' is the latency of u.
1776 'd(v,u)' is the dependence distance from v to u.
1777 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1778 the node ordering phase.
1779 'check_hardware_resources_conflicts(u, PS, c)'
1780 run a trace around cycle/slot through DFA model
1781 to check resource conflicts involving instruction u
1782 at cycle c given the partial schedule PS.
1783 'add_to_partial_schedule_at_time(u, PS, c)'
1784 Add the node/instruction u to the partial schedule
1786 'calculate_register_pressure(PS)'
1787 Given a schedule of instructions, calculate the register
1788 pressure it implies. One implementation could be the
1789 maximum number of overlapping live ranges.
1790 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1791 registers available in the hardware.
1795 3. for each node u in O in pre-computed order
1796 4. if (PSP(u) != Q && PSS(u) == Q) then
1797 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1798 6. start = Early_start; end = Early_start + II - 1; step = 1
1799 11. else if (PSP(u) == Q && PSS(u) != Q) then
1800 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1801 13. start = Late_start; end = Late_start - II + 1; step = -1
1802 14. else if (PSP(u) != Q && PSS(u) != Q) then
1803 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1804 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1805 17. start = Early_start;
1806 18. end = min(Early_start + II - 1 , Late_start);
1808 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1809 21. start = ASAP(u); end = start + II - 1; step = 1
1813 24. for (c = start ; c != end ; c += step)
1814 25. if check_hardware_resources_conflicts(u, PS, c) then
1815 26. add_to_partial_schedule_at_time(u, PS, c)
1820 31. if (success == false) then
1822 33. if (II > maxII) then
1823 34. finish - failed to schedule
1828 39. if (calculate_register_pressure(PS) > maxRP) then
1831 42. compute epilogue & prologue
1832 43. finish - succeeded to schedule
1834 ??? The algorithm restricts the scheduling window to II cycles.
1835 In rare cases, it may be better to allow windows of II+1 cycles.
1836 The window would then start and end on the same row, but with
1837 different "must precede" and "must follow" requirements. */
1839 /* A limit on the number of cycles that resource conflicts can span. ??? Should
1840 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1841 set to 0 to save compile time. */
1842 #define DFA_HISTORY SMS_DFA_HISTORY
1844 /* A threshold for the number of repeated unsuccessful attempts to insert
1845 an empty row, before we flush the partial schedule and start over. */
1846 #define MAX_SPLIT_NUM 10
1847 /* Given the partial schedule PS, this function calculates and returns the
1848 cycles in which we can schedule the node with the given index I.
1849 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1850 noticed that there are several cases in which we fail to SMS the loop
1851 because the sched window of a node is empty due to tight data-deps. In
1852 such cases we want to unschedule some of the predecessors/successors
1853 until we get non-empty scheduling window. It returns -1 if the
1854 scheduling window is empty and zero otherwise. */
1857 get_sched_window (partial_schedule_ptr ps
, ddg_node_ptr u_node
,
1858 sbitmap sched_nodes
, int ii
, int *start_p
, int *step_p
,
1861 int start
, step
, end
;
1862 int early_start
, late_start
;
1864 sbitmap psp
= sbitmap_alloc (ps
->g
->num_nodes
);
1865 sbitmap pss
= sbitmap_alloc (ps
->g
->num_nodes
);
1866 sbitmap u_node_preds
= NODE_PREDECESSORS (u_node
);
1867 sbitmap u_node_succs
= NODE_SUCCESSORS (u_node
);
1873 /* 1. compute sched window for u (start, end, step). */
1876 psp_not_empty
= bitmap_and (psp
, u_node_preds
, sched_nodes
);
1877 pss_not_empty
= bitmap_and (pss
, u_node_succs
, sched_nodes
);
1879 /* We first compute a forward range (start <= end), then decide whether
1881 early_start
= INT_MIN
;
1882 late_start
= INT_MAX
;
1890 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1892 fprintf (dump_file
, "\nAnalyzing dependencies for node %d (INSN %d)"
1893 "; ii = %d\n\n", u_node
->cuid
, INSN_UID (u_node
->insn
), ii
);
1894 fprintf (dump_file
, "%11s %11s %11s %11s %5s\n",
1895 "start", "early start", "late start", "end", "time");
1896 fprintf (dump_file
, "=========== =========== =========== ==========="
1899 /* Calculate early_start and limit end. Both bounds are inclusive. */
1901 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
1903 int v
= e
->src
->cuid
;
1905 if (bitmap_bit_p (sched_nodes
, v
))
1907 int p_st
= SCHED_TIME (v
);
1908 int earliest
= p_st
+ e
->latency
- (e
->distance
* ii
);
1909 int latest
= (e
->data_type
== MEM_DEP
? p_st
+ ii
- 1 : INT_MAX
);
1913 fprintf (dump_file
, "%11s %11d %11s %11d %5d",
1914 "", earliest
, "", latest
, p_st
);
1915 print_ddg_edge (dump_file
, e
);
1916 fprintf (dump_file
, "\n");
1919 early_start
= MAX (early_start
, earliest
);
1920 end
= MIN (end
, latest
);
1922 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1927 /* Calculate late_start and limit start. Both bounds are inclusive. */
1929 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
1931 int v
= e
->dest
->cuid
;
1933 if (bitmap_bit_p (sched_nodes
, v
))
1935 int s_st
= SCHED_TIME (v
);
1936 int earliest
= (e
->data_type
== MEM_DEP
? s_st
- ii
+ 1 : INT_MIN
);
1937 int latest
= s_st
- e
->latency
+ (e
->distance
* ii
);
1941 fprintf (dump_file
, "%11d %11s %11d %11s %5d",
1942 earliest
, "", latest
, "", s_st
);
1943 print_ddg_edge (dump_file
, e
);
1944 fprintf (dump_file
, "\n");
1947 start
= MAX (start
, earliest
);
1948 late_start
= MIN (late_start
, latest
);
1950 if (e
->type
== TRUE_DEP
&& e
->data_type
== REG_DEP
)
1955 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1957 fprintf (dump_file
, "----------- ----------- ----------- -----------"
1959 fprintf (dump_file
, "%11d %11d %11d %11d %5s %s\n",
1960 start
, early_start
, late_start
, end
, "",
1961 "(max, max, min, min)");
1964 /* Get a target scheduling window no bigger than ii. */
1965 if (early_start
== INT_MIN
&& late_start
== INT_MAX
)
1966 early_start
= NODE_ASAP (u_node
);
1967 else if (early_start
== INT_MIN
)
1968 early_start
= late_start
- (ii
- 1);
1969 late_start
= MIN (late_start
, early_start
+ (ii
- 1));
1971 /* Apply memory dependence limits. */
1972 start
= MAX (start
, early_start
);
1973 end
= MIN (end
, late_start
);
1975 if (dump_file
&& (psp_not_empty
|| pss_not_empty
))
1976 fprintf (dump_file
, "%11s %11d %11d %11s %5s final window\n",
1977 "", start
, end
, "", "");
1979 /* If there are at least as many successors as predecessors, schedule the
1980 node close to its successors. */
1981 if (pss_not_empty
&& count_succs
>= count_preds
)
1983 std::swap (start
, end
);
1987 /* Now that we've finalized the window, make END an exclusive rather
1988 than an inclusive bound. */
1997 if ((start
>= end
&& step
== 1) || (start
<= end
&& step
== -1))
2000 fprintf (dump_file
, "\nEmpty window: start=%d, end=%d, step=%d\n",
2008 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
2009 node currently been scheduled. At the end of the calculation
2010 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
2011 U_NODE which are (1) already scheduled in the first/last row of
2012 U_NODE's scheduling window, (2) whose dependence inequality with U
2013 becomes an equality when U is scheduled in this same row, and (3)
2014 whose dependence latency is zero.
2016 The first and last rows are calculated using the following parameters:
2017 START/END rows - The cycles that begins/ends the traversal on the window;
2018 searching for an empty cycle to schedule U_NODE.
2019 STEP - The direction in which we traverse the window.
2020 II - The initiation interval. */
2023 calculate_must_precede_follow (ddg_node_ptr u_node
, int start
, int end
,
2024 int step
, int ii
, sbitmap sched_nodes
,
2025 sbitmap must_precede
, sbitmap must_follow
)
2028 int first_cycle_in_window
, last_cycle_in_window
;
2030 gcc_assert (must_precede
&& must_follow
);
2032 /* Consider the following scheduling window:
2033 {first_cycle_in_window, first_cycle_in_window+1, ...,
2034 last_cycle_in_window}. If step is 1 then the following will be
2035 the order we traverse the window: {start=first_cycle_in_window,
2036 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
2037 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
2038 end=first_cycle_in_window-1} if step is -1. */
2039 first_cycle_in_window
= (step
== 1) ? start
: end
- step
;
2040 last_cycle_in_window
= (step
== 1) ? end
- step
: start
;
2042 bitmap_clear (must_precede
);
2043 bitmap_clear (must_follow
);
2046 fprintf (dump_file
, "\nmust_precede: ");
2048 /* Instead of checking if:
2049 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
2050 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
2051 first_cycle_in_window)
2053 we use the fact that latency is non-negative:
2054 SCHED_TIME (e->src) - (e->distance * ii) <=
2055 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
2056 first_cycle_in_window
2058 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
2059 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2060 if (bitmap_bit_p (sched_nodes
, e
->src
->cuid
)
2061 && ((SCHED_TIME (e
->src
->cuid
) - (e
->distance
* ii
)) ==
2062 first_cycle_in_window
))
2065 fprintf (dump_file
, "%d ", e
->src
->cuid
);
2067 bitmap_set_bit (must_precede
, e
->src
->cuid
);
2071 fprintf (dump_file
, "\nmust_follow: ");
2073 /* Instead of checking if:
2074 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
2075 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
2076 last_cycle_in_window)
2078 we use the fact that latency is non-negative:
2079 SCHED_TIME (e->dest) + (e->distance * ii) >=
2080 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
2081 last_cycle_in_window
2083 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
2084 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2085 if (bitmap_bit_p (sched_nodes
, e
->dest
->cuid
)
2086 && ((SCHED_TIME (e
->dest
->cuid
) + (e
->distance
* ii
)) ==
2087 last_cycle_in_window
))
2090 fprintf (dump_file
, "%d ", e
->dest
->cuid
);
2092 bitmap_set_bit (must_follow
, e
->dest
->cuid
);
2096 fprintf (dump_file
, "\n");
2099 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
2100 parameters to decide if that's possible:
2101 PS - The partial schedule.
2102 U - The serial number of U_NODE.
2103 NUM_SPLITS - The number of row splits made so far.
2104 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
2105 the first row of the scheduling window)
2106 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
2107 last row of the scheduling window) */
2110 try_scheduling_node_in_cycle (partial_schedule_ptr ps
,
2111 int u
, int cycle
, sbitmap sched_nodes
,
2112 int *num_splits
, sbitmap must_precede
,
2113 sbitmap must_follow
)
2118 verify_partial_schedule (ps
, sched_nodes
);
2119 psi
= ps_add_node_check_conflicts (ps
, u
, cycle
, must_precede
, must_follow
);
2122 SCHED_TIME (u
) = cycle
;
2123 bitmap_set_bit (sched_nodes
, u
);
2127 fprintf (dump_file
, "Scheduled w/o split in %d\n", cycle
);
2134 /* This function implements the scheduling algorithm for SMS according to the
2136 static partial_schedule_ptr
2137 sms_schedule_by_order (ddg_ptr g
, int mii
, int maxii
, int *nodes_order
)
2140 int i
, c
, success
, num_splits
= 0;
2141 int flush_and_start_over
= true;
2142 int num_nodes
= g
->num_nodes
;
2143 int start
, end
, step
; /* Place together into one struct? */
2144 sbitmap sched_nodes
= sbitmap_alloc (num_nodes
);
2145 sbitmap must_precede
= sbitmap_alloc (num_nodes
);
2146 sbitmap must_follow
= sbitmap_alloc (num_nodes
);
2147 sbitmap tobe_scheduled
= sbitmap_alloc (num_nodes
);
2149 partial_schedule_ptr ps
= create_partial_schedule (ii
, g
, DFA_HISTORY
);
2151 bitmap_ones (tobe_scheduled
);
2152 bitmap_clear (sched_nodes
);
2154 while (flush_and_start_over
&& (ii
< maxii
))
2158 fprintf (dump_file
, "Starting with ii=%d\n", ii
);
2159 flush_and_start_over
= false;
2160 bitmap_clear (sched_nodes
);
2162 for (i
= 0; i
< num_nodes
; i
++)
2164 int u
= nodes_order
[i
];
2165 ddg_node_ptr u_node
= &ps
->g
->nodes
[u
];
2166 rtx_insn
*insn
= u_node
->insn
;
2168 if (!NONDEBUG_INSN_P (insn
))
2170 bitmap_clear_bit (tobe_scheduled
, u
);
2174 if (bitmap_bit_p (sched_nodes
, u
))
2177 /* Try to get non-empty scheduling window. */
2179 if (get_sched_window (ps
, u_node
, sched_nodes
, ii
, &start
,
2183 fprintf (dump_file
, "\nTrying to schedule node %d "
2184 "INSN = %d in (%d .. %d) step %d\n", u
, (INSN_UID
2185 (g
->nodes
[u
].insn
)), start
, end
, step
);
2187 gcc_assert ((step
> 0 && start
< end
)
2188 || (step
< 0 && start
> end
));
2190 calculate_must_precede_follow (u_node
, start
, end
, step
, ii
,
2191 sched_nodes
, must_precede
,
2194 for (c
= start
; c
!= end
; c
+= step
)
2196 sbitmap tmp_precede
, tmp_follow
;
2198 set_must_precede_follow (&tmp_follow
, must_follow
,
2199 &tmp_precede
, must_precede
,
2200 c
, start
, end
, step
);
2202 try_scheduling_node_in_cycle (ps
, u
, c
,
2204 &num_splits
, tmp_precede
,
2210 verify_partial_schedule (ps
, sched_nodes
);
2219 if (num_splits
>= MAX_SPLIT_NUM
)
2222 flush_and_start_over
= true;
2223 verify_partial_schedule (ps
, sched_nodes
);
2224 reset_partial_schedule (ps
, ii
);
2225 verify_partial_schedule (ps
, sched_nodes
);
2230 /* The scheduling window is exclusive of 'end'
2231 whereas compute_split_window() expects an inclusive,
2234 split_row
= compute_split_row (sched_nodes
, start
, end
- 1,
2237 split_row
= compute_split_row (sched_nodes
, end
+ 1, start
,
2240 ps_insert_empty_row (ps
, split_row
, sched_nodes
);
2241 i
--; /* Go back and retry node i. */
2244 fprintf (dump_file
, "num_splits=%d\n", num_splits
);
2247 /* ??? If (success), check register pressure estimates. */
2248 } /* Continue with next node. */
2249 } /* While flush_and_start_over. */
2252 free_partial_schedule (ps
);
2256 gcc_assert (bitmap_equal_p (tobe_scheduled
, sched_nodes
));
2258 sbitmap_free (sched_nodes
);
2259 sbitmap_free (must_precede
);
2260 sbitmap_free (must_follow
);
2261 sbitmap_free (tobe_scheduled
);
2266 /* This function inserts a new empty row into PS at the position
2267 according to SPLITROW, keeping all already scheduled instructions
2268 intact and updating their SCHED_TIME and cycle accordingly. */
2270 ps_insert_empty_row (partial_schedule_ptr ps
, int split_row
,
2271 sbitmap sched_nodes
)
2273 ps_insn_ptr crr_insn
;
2274 ps_insn_ptr
*rows_new
;
2276 int new_ii
= ii
+ 1;
2278 int *rows_length_new
;
2280 verify_partial_schedule (ps
, sched_nodes
);
2282 /* We normalize sched_time and rotate ps to have only non-negative sched
2283 times, for simplicity of updating cycles after inserting new row. */
2284 split_row
-= ps
->min_cycle
;
2285 split_row
= SMODULO (split_row
, ii
);
2287 fprintf (dump_file
, "split_row=%d\n", split_row
);
2289 reset_sched_times (ps
, PS_MIN_CYCLE (ps
));
2290 rotate_partial_schedule (ps
, PS_MIN_CYCLE (ps
));
2292 rows_new
= (ps_insn_ptr
*) xcalloc (new_ii
, sizeof (ps_insn_ptr
));
2293 rows_length_new
= (int *) xcalloc (new_ii
, sizeof (int));
2294 for (row
= 0; row
< split_row
; row
++)
2296 rows_new
[row
] = ps
->rows
[row
];
2297 rows_length_new
[row
] = ps
->rows_length
[row
];
2298 ps
->rows
[row
] = NULL
;
2299 for (crr_insn
= rows_new
[row
];
2300 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2302 int u
= crr_insn
->id
;
2303 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
);
2305 SCHED_TIME (u
) = new_time
;
2306 crr_insn
->cycle
= new_time
;
2307 SCHED_ROW (u
) = new_time
% new_ii
;
2308 SCHED_STAGE (u
) = new_time
/ new_ii
;
2313 rows_new
[split_row
] = NULL
;
2315 for (row
= split_row
; row
< ii
; row
++)
2317 rows_new
[row
+ 1] = ps
->rows
[row
];
2318 rows_length_new
[row
+ 1] = ps
->rows_length
[row
];
2319 ps
->rows
[row
] = NULL
;
2320 for (crr_insn
= rows_new
[row
+ 1];
2321 crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2323 int u
= crr_insn
->id
;
2324 int new_time
= SCHED_TIME (u
) + (SCHED_TIME (u
) / ii
) + 1;
2326 SCHED_TIME (u
) = new_time
;
2327 crr_insn
->cycle
= new_time
;
2328 SCHED_ROW (u
) = new_time
% new_ii
;
2329 SCHED_STAGE (u
) = new_time
/ new_ii
;
2334 ps
->min_cycle
= ps
->min_cycle
+ ps
->min_cycle
/ ii
2335 + (SMODULO (ps
->min_cycle
, ii
) >= split_row
? 1 : 0);
2336 ps
->max_cycle
= ps
->max_cycle
+ ps
->max_cycle
/ ii
2337 + (SMODULO (ps
->max_cycle
, ii
) >= split_row
? 1 : 0);
2339 ps
->rows
= rows_new
;
2340 free (ps
->rows_length
);
2341 ps
->rows_length
= rows_length_new
;
2343 gcc_assert (ps
->min_cycle
>= 0);
2345 verify_partial_schedule (ps
, sched_nodes
);
2348 fprintf (dump_file
, "min_cycle=%d, max_cycle=%d\n", ps
->min_cycle
,
2352 /* Given U_NODE which is the node that failed to be scheduled; LOW and
2353 UP which are the boundaries of it's scheduling window; compute using
2354 SCHED_NODES and II a row in the partial schedule that can be split
2355 which will separate a critical predecessor from a critical successor
2356 thereby expanding the window, and return it. */
2358 compute_split_row (sbitmap sched_nodes
, int low
, int up
, int ii
,
2359 ddg_node_ptr u_node
)
2362 int lower
= INT_MIN
, upper
= INT_MAX
;
2367 for (e
= u_node
->in
; e
!= 0; e
= e
->next_in
)
2369 int v
= e
->src
->cuid
;
2371 if (bitmap_bit_p (sched_nodes
, v
)
2372 && (low
== SCHED_TIME (v
) + e
->latency
- (e
->distance
* ii
)))
2373 if (SCHED_TIME (v
) > lower
)
2376 lower
= SCHED_TIME (v
);
2382 crit_cycle
= SCHED_TIME (crit_pred
) + 1;
2383 return SMODULO (crit_cycle
, ii
);
2386 for (e
= u_node
->out
; e
!= 0; e
= e
->next_out
)
2388 int v
= e
->dest
->cuid
;
2390 if (bitmap_bit_p (sched_nodes
, v
)
2391 && (up
== SCHED_TIME (v
) - e
->latency
+ (e
->distance
* ii
)))
2392 if (SCHED_TIME (v
) < upper
)
2395 upper
= SCHED_TIME (v
);
2401 crit_cycle
= SCHED_TIME (crit_succ
);
2402 return SMODULO (crit_cycle
, ii
);
2406 fprintf (dump_file
, "Both crit_pred and crit_succ are NULL\n");
2408 return SMODULO ((low
+ up
+ 1) / 2, ii
);
2412 verify_partial_schedule (partial_schedule_ptr ps
, sbitmap sched_nodes
)
2415 ps_insn_ptr crr_insn
;
2417 for (row
= 0; row
< ps
->ii
; row
++)
2421 for (crr_insn
= ps
->rows
[row
]; crr_insn
; crr_insn
= crr_insn
->next_in_row
)
2423 int u
= crr_insn
->id
;
2426 gcc_assert (bitmap_bit_p (sched_nodes
, u
));
2427 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2428 popcount (sched_nodes) == number of insns in ps. */
2429 gcc_assert (SCHED_TIME (u
) >= ps
->min_cycle
);
2430 gcc_assert (SCHED_TIME (u
) <= ps
->max_cycle
);
2433 gcc_assert (ps
->rows_length
[row
] == length
);
2438 /* This page implements the algorithm for ordering the nodes of a DDG
2439 for modulo scheduling, activated through the
2440 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2442 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2443 #define ASAP(x) (ORDER_PARAMS ((x))->asap)
2444 #define ALAP(x) (ORDER_PARAMS ((x))->alap)
2445 #define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2446 #define MOB(x) (ALAP ((x)) - ASAP ((x)))
2447 #define DEPTH(x) (ASAP ((x)))
2449 typedef struct node_order_params
* nopa
;
2451 static void order_nodes_of_sccs (ddg_all_sccs_ptr
, int * result
);
2452 static int order_nodes_in_scc (ddg_ptr
, sbitmap
, sbitmap
, int*, int);
2453 static nopa
calculate_order_params (ddg_ptr
, int, int *);
2454 static int find_max_asap (ddg_ptr
, sbitmap
);
2455 static int find_max_hv_min_mob (ddg_ptr
, sbitmap
);
2456 static int find_max_dv_min_mob (ddg_ptr
, sbitmap
);
2458 enum sms_direction
{BOTTOMUP
, TOPDOWN
};
2460 struct node_order_params
2467 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2469 check_nodes_order (int *node_order
, int num_nodes
)
2472 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2477 fprintf (dump_file
, "SMS final nodes order: \n");
2479 for (i
= 0; i
< num_nodes
; i
++)
2481 int u
= node_order
[i
];
2484 fprintf (dump_file
, "%d ", u
);
2485 gcc_assert (u
< num_nodes
&& u
>= 0 && !bitmap_bit_p (tmp
, u
));
2487 bitmap_set_bit (tmp
, u
);
2491 fprintf (dump_file
, "\n");
2496 /* Order the nodes of G for scheduling and pass the result in
2497 NODE_ORDER. Also set aux.count of each node to ASAP.
2498 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2500 sms_order_nodes (ddg_ptr g
, int mii
, int * node_order
, int *pmax_asap
)
2504 ddg_all_sccs_ptr sccs
= create_ddg_all_sccs (g
);
2506 nopa nops
= calculate_order_params (g
, mii
, pmax_asap
);
2509 print_sccs (dump_file
, sccs
, g
);
2511 order_nodes_of_sccs (sccs
, node_order
);
2513 if (sccs
->num_sccs
> 0)
2514 /* First SCC has the largest recurrence_length. */
2515 rec_mii
= sccs
->sccs
[0]->recurrence_length
;
2517 /* Save ASAP before destroying node_order_params. */
2518 for (i
= 0; i
< g
->num_nodes
; i
++)
2520 ddg_node_ptr v
= &g
->nodes
[i
];
2521 v
->aux
.count
= ASAP (v
);
2525 free_ddg_all_sccs (sccs
);
2526 check_nodes_order (node_order
, g
->num_nodes
);
2532 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs
, int * node_order
)
2535 ddg_ptr g
= all_sccs
->ddg
;
2536 int num_nodes
= g
->num_nodes
;
2537 sbitmap prev_sccs
= sbitmap_alloc (num_nodes
);
2538 sbitmap on_path
= sbitmap_alloc (num_nodes
);
2539 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2540 sbitmap ones
= sbitmap_alloc (num_nodes
);
2542 bitmap_clear (prev_sccs
);
2545 /* Perform the node ordering starting from the SCC with the highest recMII.
2546 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2547 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
2549 ddg_scc_ptr scc
= all_sccs
->sccs
[i
];
2551 /* Add nodes on paths from previous SCCs to the current SCC. */
2552 find_nodes_on_paths (on_path
, g
, prev_sccs
, scc
->nodes
);
2553 bitmap_ior (tmp
, scc
->nodes
, on_path
);
2555 /* Add nodes on paths from the current SCC to previous SCCs. */
2556 find_nodes_on_paths (on_path
, g
, scc
->nodes
, prev_sccs
);
2557 bitmap_ior (tmp
, tmp
, on_path
);
2559 /* Remove nodes of previous SCCs from current extended SCC. */
2560 bitmap_and_compl (tmp
, tmp
, prev_sccs
);
2562 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2563 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2566 /* Handle the remaining nodes that do not belong to any scc. Each call
2567 to order_nodes_in_scc handles a single connected component. */
2568 while (pos
< g
->num_nodes
)
2570 bitmap_and_compl (tmp
, ones
, prev_sccs
);
2571 pos
= order_nodes_in_scc (g
, prev_sccs
, tmp
, node_order
, pos
);
2573 sbitmap_free (prev_sccs
);
2574 sbitmap_free (on_path
);
2576 sbitmap_free (ones
);
2579 /* MII is needed if we consider backarcs (that do not close recursive cycles). */
2580 static struct node_order_params
*
2581 calculate_order_params (ddg_ptr g
, int mii ATTRIBUTE_UNUSED
, int *pmax_asap
)
2585 int num_nodes
= g
->num_nodes
;
2587 /* Allocate a place to hold ordering params for each node in the DDG. */
2588 nopa node_order_params_arr
;
2590 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2591 node_order_params_arr
= (nopa
) xcalloc (num_nodes
,
2592 sizeof (struct node_order_params
));
2594 /* Set the aux pointer of each node to point to its order_params structure. */
2595 for (u
= 0; u
< num_nodes
; u
++)
2596 g
->nodes
[u
].aux
.info
= &node_order_params_arr
[u
];
2598 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2599 calculate ASAP, ALAP, mobility, distance, and height for each node
2600 in the dependence (direct acyclic) graph. */
2602 /* We assume that the nodes in the array are in topological order. */
2605 for (u
= 0; u
< num_nodes
; u
++)
2607 ddg_node_ptr u_node
= &g
->nodes
[u
];
2610 for (e
= u_node
->in
; e
; e
= e
->next_in
)
2611 if (e
->distance
== 0)
2612 ASAP (u_node
) = MAX (ASAP (u_node
),
2613 ASAP (e
->src
) + e
->latency
);
2614 max_asap
= MAX (max_asap
, ASAP (u_node
));
2617 for (u
= num_nodes
- 1; u
> -1; u
--)
2619 ddg_node_ptr u_node
= &g
->nodes
[u
];
2621 ALAP (u_node
) = max_asap
;
2622 HEIGHT (u_node
) = 0;
2623 for (e
= u_node
->out
; e
; e
= e
->next_out
)
2624 if (e
->distance
== 0)
2626 ALAP (u_node
) = MIN (ALAP (u_node
),
2627 ALAP (e
->dest
) - e
->latency
);
2628 HEIGHT (u_node
) = MAX (HEIGHT (u_node
),
2629 HEIGHT (e
->dest
) + e
->latency
);
2634 fprintf (dump_file
, "\nOrder params\n");
2635 for (u
= 0; u
< num_nodes
; u
++)
2637 ddg_node_ptr u_node
= &g
->nodes
[u
];
2639 fprintf (dump_file
, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u
,
2640 ASAP (u_node
), ALAP (u_node
), HEIGHT (u_node
));
2644 *pmax_asap
= max_asap
;
2645 return node_order_params_arr
;
2649 find_max_asap (ddg_ptr g
, sbitmap nodes
)
2654 sbitmap_iterator sbi
;
2656 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2658 ddg_node_ptr u_node
= &g
->nodes
[u
];
2660 if (max_asap
< ASAP (u_node
))
2662 max_asap
= ASAP (u_node
);
2670 find_max_hv_min_mob (ddg_ptr g
, sbitmap nodes
)
2674 int min_mob
= INT_MAX
;
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_hv
< HEIGHT (u_node
))
2684 max_hv
= HEIGHT (u_node
);
2685 min_mob
= MOB (u_node
);
2688 else if ((max_hv
== HEIGHT (u_node
))
2689 && (min_mob
> MOB (u_node
)))
2691 min_mob
= MOB (u_node
);
2699 find_max_dv_min_mob (ddg_ptr g
, sbitmap nodes
)
2703 int min_mob
= INT_MAX
;
2705 sbitmap_iterator sbi
;
2707 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
2709 ddg_node_ptr u_node
= &g
->nodes
[u
];
2711 if (max_dv
< DEPTH (u_node
))
2713 max_dv
= DEPTH (u_node
);
2714 min_mob
= MOB (u_node
);
2717 else if ((max_dv
== DEPTH (u_node
))
2718 && (min_mob
> MOB (u_node
)))
2720 min_mob
= MOB (u_node
);
2727 /* Places the nodes of SCC into the NODE_ORDER array starting
2728 at position POS, according to the SMS ordering algorithm.
2729 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2730 the NODE_ORDER array, starting from position zero. */
2732 order_nodes_in_scc (ddg_ptr g
, sbitmap nodes_ordered
, sbitmap scc
,
2733 int * node_order
, int pos
)
2735 enum sms_direction dir
;
2736 int num_nodes
= g
->num_nodes
;
2737 sbitmap workset
= sbitmap_alloc (num_nodes
);
2738 sbitmap tmp
= sbitmap_alloc (num_nodes
);
2739 sbitmap zero_bitmap
= sbitmap_alloc (num_nodes
);
2740 sbitmap predecessors
= sbitmap_alloc (num_nodes
);
2741 sbitmap successors
= sbitmap_alloc (num_nodes
);
2743 bitmap_clear (predecessors
);
2744 find_predecessors (predecessors
, g
, nodes_ordered
);
2746 bitmap_clear (successors
);
2747 find_successors (successors
, g
, nodes_ordered
);
2750 if (bitmap_and (tmp
, predecessors
, scc
))
2752 bitmap_copy (workset
, tmp
);
2755 else if (bitmap_and (tmp
, successors
, scc
))
2757 bitmap_copy (workset
, tmp
);
2764 bitmap_clear (workset
);
2765 if ((u
= find_max_asap (g
, scc
)) >= 0)
2766 bitmap_set_bit (workset
, u
);
2770 bitmap_clear (zero_bitmap
);
2771 while (!bitmap_equal_p (workset
, zero_bitmap
))
2774 ddg_node_ptr v_node
;
2775 sbitmap v_node_preds
;
2776 sbitmap v_node_succs
;
2780 while (!bitmap_equal_p (workset
, zero_bitmap
))
2782 v
= find_max_hv_min_mob (g
, workset
);
2783 v_node
= &g
->nodes
[v
];
2784 node_order
[pos
++] = v
;
2785 v_node_succs
= NODE_SUCCESSORS (v_node
);
2786 bitmap_and (tmp
, v_node_succs
, scc
);
2788 /* Don't consider the already ordered successors again. */
2789 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2790 bitmap_ior (workset
, workset
, tmp
);
2791 bitmap_clear_bit (workset
, v
);
2792 bitmap_set_bit (nodes_ordered
, v
);
2795 bitmap_clear (predecessors
);
2796 find_predecessors (predecessors
, g
, nodes_ordered
);
2797 bitmap_and (workset
, predecessors
, scc
);
2801 while (!bitmap_equal_p (workset
, zero_bitmap
))
2803 v
= find_max_dv_min_mob (g
, workset
);
2804 v_node
= &g
->nodes
[v
];
2805 node_order
[pos
++] = v
;
2806 v_node_preds
= NODE_PREDECESSORS (v_node
);
2807 bitmap_and (tmp
, v_node_preds
, scc
);
2809 /* Don't consider the already ordered predecessors again. */
2810 bitmap_and_compl (tmp
, tmp
, nodes_ordered
);
2811 bitmap_ior (workset
, workset
, tmp
);
2812 bitmap_clear_bit (workset
, v
);
2813 bitmap_set_bit (nodes_ordered
, v
);
2816 bitmap_clear (successors
);
2817 find_successors (successors
, g
, nodes_ordered
);
2818 bitmap_and (workset
, successors
, scc
);
2822 sbitmap_free (workset
);
2823 sbitmap_free (zero_bitmap
);
2824 sbitmap_free (predecessors
);
2825 sbitmap_free (successors
);
2830 /* This page contains functions for manipulating partial-schedules during
2831 modulo scheduling. */
2833 /* Create a partial schedule and allocate a memory to hold II rows. */
2835 static partial_schedule_ptr
2836 create_partial_schedule (int ii
, ddg_ptr g
, int history
)
2838 partial_schedule_ptr ps
= XNEW (struct partial_schedule
);
2839 ps
->rows
= (ps_insn_ptr
*) xcalloc (ii
, sizeof (ps_insn_ptr
));
2840 ps
->rows_length
= (int *) xcalloc (ii
, sizeof (int));
2841 ps
->reg_moves
.create (0);
2843 ps
->history
= history
;
2844 ps
->min_cycle
= INT_MAX
;
2845 ps
->max_cycle
= INT_MIN
;
2851 /* Free the PS_INSNs in rows array of the given partial schedule.
2852 ??? Consider caching the PS_INSN's. */
2854 free_ps_insns (partial_schedule_ptr ps
)
2858 for (i
= 0; i
< ps
->ii
; i
++)
2862 ps_insn_ptr ps_insn
= ps
->rows
[i
]->next_in_row
;
2865 ps
->rows
[i
] = ps_insn
;
2871 /* Free all the memory allocated to the partial schedule. */
2874 free_partial_schedule (partial_schedule_ptr ps
)
2876 ps_reg_move_info
*move
;
2882 FOR_EACH_VEC_ELT (ps
->reg_moves
, i
, move
)
2883 sbitmap_free (move
->uses
);
2884 ps
->reg_moves
.release ();
2888 free (ps
->rows_length
);
2892 /* Clear the rows array with its PS_INSNs, and create a new one with
2896 reset_partial_schedule (partial_schedule_ptr ps
, int new_ii
)
2901 if (new_ii
== ps
->ii
)
2903 ps
->rows
= (ps_insn_ptr
*) xrealloc (ps
->rows
, new_ii
2904 * sizeof (ps_insn_ptr
));
2905 memset (ps
->rows
, 0, new_ii
* sizeof (ps_insn_ptr
));
2906 ps
->rows_length
= (int *) xrealloc (ps
->rows_length
, new_ii
* sizeof (int));
2907 memset (ps
->rows_length
, 0, new_ii
* sizeof (int));
2909 ps
->min_cycle
= INT_MAX
;
2910 ps
->max_cycle
= INT_MIN
;
2913 /* Prints the partial schedule as an ii rows array, for each rows
2914 print the ids of the insns in it. */
2916 print_partial_schedule (partial_schedule_ptr ps
, FILE *dump
)
2920 for (i
= 0; i
< ps
->ii
; i
++)
2922 ps_insn_ptr ps_i
= ps
->rows
[i
];
2924 fprintf (dump
, "\n[ROW %d ]: ", i
);
2927 rtx_insn
*insn
= ps_rtl_insn (ps
, ps_i
->id
);
2930 fprintf (dump
, "%d (branch), ", INSN_UID (insn
));
2932 fprintf (dump
, "%d, ", INSN_UID (insn
));
2934 ps_i
= ps_i
->next_in_row
;
2939 /* Creates an object of PS_INSN and initializes it to the given parameters. */
2941 create_ps_insn (int id
, int cycle
)
2943 ps_insn_ptr ps_i
= XNEW (struct ps_insn
);
2946 ps_i
->next_in_row
= NULL
;
2947 ps_i
->prev_in_row
= NULL
;
2948 ps_i
->cycle
= cycle
;
2954 /* Removes the given PS_INSN from the partial schedule. */
2956 remove_node_from_ps (partial_schedule_ptr ps
, ps_insn_ptr ps_i
)
2960 gcc_assert (ps
&& ps_i
);
2962 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
2963 if (! ps_i
->prev_in_row
)
2965 gcc_assert (ps_i
== ps
->rows
[row
]);
2966 ps
->rows
[row
] = ps_i
->next_in_row
;
2968 ps
->rows
[row
]->prev_in_row
= NULL
;
2972 ps_i
->prev_in_row
->next_in_row
= ps_i
->next_in_row
;
2973 if (ps_i
->next_in_row
)
2974 ps_i
->next_in_row
->prev_in_row
= ps_i
->prev_in_row
;
2977 ps
->rows_length
[row
] -= 1;
2982 /* Unlike what literature describes for modulo scheduling (which focuses
2983 on VLIW machines) the order of the instructions inside a cycle is
2984 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2985 where the current instruction should go relative to the already
2986 scheduled instructions in the given cycle. Go over these
2987 instructions and find the first possible column to put it in. */
2989 ps_insn_find_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
2990 sbitmap must_precede
, sbitmap must_follow
)
2992 ps_insn_ptr next_ps_i
;
2993 ps_insn_ptr first_must_follow
= NULL
;
2994 ps_insn_ptr last_must_precede
= NULL
;
2995 ps_insn_ptr last_in_row
= NULL
;
3001 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3003 /* Find the first must follow and the last must precede
3004 and insert the node immediately after the must precede
3005 but make sure that it there is no must follow after it. */
3006 for (next_ps_i
= ps
->rows
[row
];
3008 next_ps_i
= next_ps_i
->next_in_row
)
3011 && bitmap_bit_p (must_follow
, next_ps_i
->id
)
3012 && ! first_must_follow
)
3013 first_must_follow
= next_ps_i
;
3014 if (must_precede
&& bitmap_bit_p (must_precede
, next_ps_i
->id
))
3016 /* If we have already met a node that must follow, then
3017 there is no possible column. */
3018 if (first_must_follow
)
3021 last_must_precede
= next_ps_i
;
3023 /* The closing branch must be the last in the row. */
3025 && bitmap_bit_p (must_precede
, next_ps_i
->id
)
3026 && JUMP_P (ps_rtl_insn (ps
, next_ps_i
->id
)))
3029 last_in_row
= next_ps_i
;
3032 /* The closing branch is scheduled as well. Make sure there is no
3033 dependent instruction after it as the branch should be the last
3034 instruction in the row. */
3035 if (JUMP_P (ps_rtl_insn (ps
, ps_i
->id
)))
3037 if (first_must_follow
)
3041 /* Make the branch the last in the row. New instructions
3042 will be inserted at the beginning of the row or after the
3043 last must_precede instruction thus the branch is guaranteed
3044 to remain the last instruction in the row. */
3045 last_in_row
->next_in_row
= ps_i
;
3046 ps_i
->prev_in_row
= last_in_row
;
3047 ps_i
->next_in_row
= NULL
;
3050 ps
->rows
[row
] = ps_i
;
3054 /* Now insert the node after INSERT_AFTER_PSI. */
3056 if (! last_must_precede
)
3058 ps_i
->next_in_row
= ps
->rows
[row
];
3059 ps_i
->prev_in_row
= NULL
;
3060 if (ps_i
->next_in_row
)
3061 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3062 ps
->rows
[row
] = ps_i
;
3066 ps_i
->next_in_row
= last_must_precede
->next_in_row
;
3067 last_must_precede
->next_in_row
= ps_i
;
3068 ps_i
->prev_in_row
= last_must_precede
;
3069 if (ps_i
->next_in_row
)
3070 ps_i
->next_in_row
->prev_in_row
= ps_i
;
3076 /* Advances the PS_INSN one column in its current row; returns false
3077 in failure and true in success. Bit N is set in MUST_FOLLOW if
3078 the node with cuid N must be come after the node pointed to by
3079 PS_I when scheduled in the same cycle. */
3081 ps_insn_advance_column (partial_schedule_ptr ps
, ps_insn_ptr ps_i
,
3082 sbitmap must_follow
)
3084 ps_insn_ptr prev
, next
;
3090 row
= SMODULO (ps_i
->cycle
, ps
->ii
);
3092 if (! ps_i
->next_in_row
)
3095 /* Check if next_in_row is dependent on ps_i, both having same sched
3096 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
3097 if (must_follow
&& bitmap_bit_p (must_follow
, ps_i
->next_in_row
->id
))
3100 /* Advance PS_I over its next_in_row in the doubly linked list. */
3101 prev
= ps_i
->prev_in_row
;
3102 next
= ps_i
->next_in_row
;
3104 if (ps_i
== ps
->rows
[row
])
3105 ps
->rows
[row
] = next
;
3107 ps_i
->next_in_row
= next
->next_in_row
;
3109 if (next
->next_in_row
)
3110 next
->next_in_row
->prev_in_row
= ps_i
;
3112 next
->next_in_row
= ps_i
;
3113 ps_i
->prev_in_row
= next
;
3115 next
->prev_in_row
= prev
;
3117 prev
->next_in_row
= next
;
3122 /* Inserts a DDG_NODE to the given partial schedule at the given cycle.
3123 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
3124 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
3125 before/after (respectively) the node pointed to by PS_I when scheduled
3126 in the same cycle. */
3128 add_node_to_ps (partial_schedule_ptr ps
, int id
, int cycle
,
3129 sbitmap must_precede
, sbitmap must_follow
)
3132 int row
= SMODULO (cycle
, ps
->ii
);
3134 if (ps
->rows_length
[row
] >= issue_rate
)
3137 ps_i
= create_ps_insn (id
, cycle
);
3139 /* Finds and inserts PS_I according to MUST_FOLLOW and
3141 if (! ps_insn_find_column (ps
, ps_i
, must_precede
, must_follow
))
3147 ps
->rows_length
[row
] += 1;
3151 /* Advance time one cycle. Assumes DFA is being used. */
3153 advance_one_cycle (void)
3155 if (targetm
.sched
.dfa_pre_cycle_insn
)
3156 state_transition (curr_state
,
3157 targetm
.sched
.dfa_pre_cycle_insn ());
3159 state_transition (curr_state
, NULL
);
3161 if (targetm
.sched
.dfa_post_cycle_insn
)
3162 state_transition (curr_state
,
3163 targetm
.sched
.dfa_post_cycle_insn ());
3168 /* Checks if PS has resource conflicts according to DFA, starting from
3169 FROM cycle to TO cycle; returns true if there are conflicts and false
3170 if there are no conflicts. Assumes DFA is being used. */
3172 ps_has_conflicts (partial_schedule_ptr ps
, int from
, int to
)
3176 state_reset (curr_state
);
3178 for (cycle
= from
; cycle
<= to
; cycle
++)
3180 ps_insn_ptr crr_insn
;
3181 /* Holds the remaining issue slots in the current row. */
3182 int can_issue_more
= issue_rate
;
3184 /* Walk through the DFA for the current row. */
3185 for (crr_insn
= ps
->rows
[SMODULO (cycle
, ps
->ii
)];
3187 crr_insn
= crr_insn
->next_in_row
)
3189 rtx_insn
*insn
= ps_rtl_insn (ps
, crr_insn
->id
);
3191 if (!NONDEBUG_INSN_P (insn
))
3194 /* Check if there is room for the current insn. */
3195 if (!can_issue_more
|| state_dead_lock_p (curr_state
))
3198 /* Update the DFA state and return with failure if the DFA found
3199 resource conflicts. */
3200 if (state_transition (curr_state
, insn
) >= 0)
3203 if (targetm
.sched
.variable_issue
)
3205 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
3206 insn
, can_issue_more
);
3207 /* A naked CLOBBER or USE generates no instruction, so don't
3208 let them consume issue slots. */
3209 else if (GET_CODE (PATTERN (insn
)) != USE
3210 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3214 /* Advance the DFA to the next cycle. */
3215 advance_one_cycle ();
3220 /* Checks if the given node causes resource conflicts when added to PS at
3221 cycle C. If not the node is added to PS and returned; otherwise zero
3222 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
3223 cuid N must be come before/after (respectively) the node pointed to by
3224 PS_I when scheduled in the same cycle. */
3226 ps_add_node_check_conflicts (partial_schedule_ptr ps
, int n
,
3227 int c
, sbitmap must_precede
,
3228 sbitmap must_follow
)
3230 int has_conflicts
= 0;
3233 /* First add the node to the PS, if this succeeds check for
3234 conflicts, trying different issue slots in the same row. */
3235 if (! (ps_i
= add_node_to_ps (ps
, n
, c
, must_precede
, must_follow
)))
3236 return NULL
; /* Failed to insert the node at the given cycle. */
3238 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3240 && ps_has_conflicts (ps
,
3244 /* Try different issue slots to find one that the given node can be
3245 scheduled in without conflicts. */
3246 while (has_conflicts
)
3248 if (! ps_insn_advance_column (ps
, ps_i
, must_follow
))
3250 has_conflicts
= ps_has_conflicts (ps
, c
, c
)
3252 && ps_has_conflicts (ps
,
3259 remove_node_from_ps (ps
, ps_i
);
3263 ps
->min_cycle
= MIN (ps
->min_cycle
, c
);
3264 ps
->max_cycle
= MAX (ps
->max_cycle
, c
);
3268 /* Calculate the stage count of the partial schedule PS. The calculation
3269 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3271 calculate_stage_count (partial_schedule_ptr ps
, int rotation_amount
)
3273 int new_min_cycle
= PS_MIN_CYCLE (ps
) - rotation_amount
;
3274 int new_max_cycle
= PS_MAX_CYCLE (ps
) - rotation_amount
;
3275 int stage_count
= CALC_STAGE_COUNT (-1, new_min_cycle
, ps
->ii
);
3277 /* The calculation of stage count is done adding the number of stages
3278 before cycle zero and after cycle zero. */
3279 stage_count
+= CALC_STAGE_COUNT (new_max_cycle
, 0, ps
->ii
);
3284 /* Rotate the rows of PS such that insns scheduled at time
3285 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3287 rotate_partial_schedule (partial_schedule_ptr ps
, int start_cycle
)
3289 int i
, row
, backward_rotates
;
3290 int last_row
= ps
->ii
- 1;
3292 if (start_cycle
== 0)
3295 backward_rotates
= SMODULO (start_cycle
, ps
->ii
);
3297 /* Revisit later and optimize this into a single loop. */
3298 for (i
= 0; i
< backward_rotates
; i
++)
3300 ps_insn_ptr first_row
= ps
->rows
[0];
3301 int first_row_length
= ps
->rows_length
[0];
3303 for (row
= 0; row
< last_row
; row
++)
3305 ps
->rows
[row
] = ps
->rows
[row
+ 1];
3306 ps
->rows_length
[row
] = ps
->rows_length
[row
+ 1];
3309 ps
->rows
[last_row
] = first_row
;
3310 ps
->rows_length
[last_row
] = first_row_length
;
3313 ps
->max_cycle
-= start_cycle
;
3314 ps
->min_cycle
-= start_cycle
;
3317 #endif /* INSN_SCHEDULING */
3319 /* Run instruction scheduler. */
3320 /* Perform SMS module scheduling. */
3324 const pass_data pass_data_sms
=
3326 RTL_PASS
, /* type */
3328 OPTGROUP_NONE
, /* optinfo_flags */
3330 0, /* properties_required */
3331 0, /* properties_provided */
3332 0, /* properties_destroyed */
3333 0, /* todo_flags_start */
3334 TODO_df_finish
, /* todo_flags_finish */
3337 class pass_sms
: public rtl_opt_pass
3340 pass_sms (gcc::context
*ctxt
)
3341 : rtl_opt_pass (pass_data_sms
, ctxt
)
3344 /* opt_pass methods: */
3345 virtual bool gate (function
*)
3347 return (optimize
> 0 && flag_modulo_sched
);
3350 virtual unsigned int execute (function
*);
3352 }; // class pass_sms
3355 pass_sms::execute (function
*fun ATTRIBUTE_UNUSED
)
3357 #ifdef INSN_SCHEDULING
3360 /* Collect loop information to be used in SMS. */
3361 cfg_layout_initialize (0);
3364 /* Update the life information, because we add pseudos. */
3365 max_regno
= max_reg_num ();
3367 /* Finalize layout changes. */
3368 FOR_EACH_BB_FN (bb
, fun
)
3369 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3370 bb
->aux
= bb
->next_bb
;
3371 free_dominance_info (CDI_DOMINATORS
);
3372 cfg_layout_finalize ();
3373 #endif /* INSN_SCHEDULING */
3380 make_pass_sms (gcc::context
*ctxt
)
3382 return new pass_sms (ctxt
);