1/* Swing Modulo Scheduling implementation.
2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
3 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "backend.h"
26#include "target.h"
27#include "rtl.h"
28#include "tree.h"
29#include "cfghooks.h"
30#include "df.h"
31#include "memmodel.h"
32#include "optabs.h"
33#include "regs.h"
34#include "emit-rtl.h"
35#include "gcov-io.h"
36#include "profile.h"
37#include "insn-attr.h"
38#include "cfgrtl.h"
39#include "sched-int.h"
40#include "cfgloop.h"
41#include "expr.h"
42#include "params.h"
43#include "ddg.h"
44#include "tree-pass.h"
45#include "dbgcnt.h"
46#include "loop-unroll.h"
47
48#ifdef INSN_SCHEDULING
49
50/* This file contains the implementation of the Swing Modulo Scheduler,
51 described in the following references:
52 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
53 Lifetime--sensitive modulo scheduling in a production environment.
54 IEEE Trans. on Comps., 50(3), March 2001
55 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
56 Swing Modulo Scheduling: A Lifetime Sensitive Approach.
57 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).
58
59 The basic structure is:
60 1. Build a data-dependence graph (DDG) for each loop.
61 2. Use the DDG to order the insns of a loop (not in topological order
62 necessarily, but rather) trying to place each insn after all its
63 predecessors _or_ after all its successors.
64 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
65 4. Use the ordering to perform list-scheduling of the loop:
66 1. Set II = MII. We will try to schedule the loop within II cycles.
67 2. Try to schedule the insns one by one according to the ordering.
68 For each insn compute an interval of cycles by considering already-
69 scheduled preds and succs (and associated latencies); try to place
70 the insn in the cycles of this window checking for potential
71 resource conflicts (using the DFA interface).
72 Note: this is different from the cycle-scheduling of schedule_insns;
73 here the insns are not scheduled monotonically top-down (nor bottom-
74 up).
75 3. If failed in scheduling all insns - bump II++ and try again, unless
76 II reaches an upper bound MaxII, in which case report failure.
77 5. If we succeeded in scheduling the loop within II cycles, we now
78 generate prolog and epilog, decrease the counter of the loop, and
79 perform modulo variable expansion for live ranges that span more than
80 II cycles (i.e. use register copies to prevent a def from overwriting
81 itself before reaching the use).
82
83 SMS works with countable loops (1) whose control part can be easily
84 decoupled from the rest of the loop and (2) whose loop count can
85 be easily adjusted. This is because we peel a constant number of
86 iterations into a prologue and epilogue for which we want to avoid
87 emitting the control part, and a kernel which is to iterate that
88 constant number of iterations less than the original loop. So the
89 control part should be a set of insns clearly identified and having
90 its own iv, not otherwise used in the loop (at-least for now), which
91 initializes a register before the loop to the number of iterations.
92 Currently SMS relies on the do-loop pattern to recognize such loops,
93 where (1) the control part comprises of all insns defining and/or
94 using a certain 'count' register and (2) the loop count can be
95 adjusted by modifying this register prior to the loop.
96 TODO: Rely on cfgloop analysis instead. */
97
98/* This page defines partial-schedule structures and functions for
99 modulo scheduling. */
100
101typedef struct partial_schedule *partial_schedule_ptr;
102typedef struct ps_insn *ps_insn_ptr;
103
104/* The minimum (absolute) cycle that a node of ps was scheduled in. */
105#define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)
106
107/* The maximum (absolute) cycle that a node of ps was scheduled in. */
108#define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)
109
110/* Perform signed modulo, always returning a non-negative value. */
111#define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
112
113/* The number of different iterations the nodes in ps span, assuming
114 the stage boundaries are placed efficiently. */
115#define CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \
116 + 1 + ii - 1) / ii)
117/* The stage count of ps. */
118#define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count)
119
120/* A single instruction in the partial schedule. */
121struct ps_insn
122{
123 /* Identifies the instruction to be scheduled. Values smaller than
124 the ddg's num_nodes refer directly to ddg nodes. A value of
125 X - num_nodes refers to register move X. */
126 int id;
127
128 /* The (absolute) cycle in which the PS instruction is scheduled.
129 Same as SCHED_TIME (node). */
130 int cycle;
131
132 /* The next/prev PS_INSN in the same row. */
133 ps_insn_ptr next_in_row,
134 prev_in_row;
135
136};
137
138/* Information about a register move that has been added to a partial
139 schedule. */
140struct ps_reg_move_info
141{
142 /* The source of the move is defined by the ps_insn with id DEF.
143 The destination is used by the ps_insns with the ids in USES. */
144 int def;
145 sbitmap uses;
146
147 /* The original form of USES' instructions used OLD_REG, but they
148 should now use NEW_REG. */
149 rtx old_reg;
150 rtx new_reg;
151
152 /* The number of consecutive stages that the move occupies. */
153 int num_consecutive_stages;
154
155 /* An instruction that sets NEW_REG to the correct value. The first
156 move associated with DEF will have an rhs of OLD_REG; later moves
157 use the result of the previous move. */
158 rtx_insn *insn;
159};
160
161/* Holds the partial schedule as an array of II rows. Each entry of the
162 array points to a linked list of PS_INSNs, which represents the
163 instructions that are scheduled for that row. */
164struct partial_schedule
165{
166 int ii; /* Number of rows in the partial schedule. */
167 int history; /* Threshold for conflict checking using DFA. */
168
169 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
170 ps_insn_ptr *rows;
171
172 /* All the moves added for this partial schedule. Index X has
173 a ps_insn id of X + g->num_nodes. */
174 vec<ps_reg_move_info> reg_moves;
175
176 /* rows_length[i] holds the number of instructions in the row.
177 It is used only (as an optimization) to back off quickly from
178 trying to schedule a node in a full row; that is, to avoid running
179 through futile DFA state transitions. */
180 int *rows_length;
181
182 /* The earliest absolute cycle of an insn in the partial schedule. */
183 int min_cycle;
184
185 /* The latest absolute cycle of an insn in the partial schedule. */
186 int max_cycle;
187
188 ddg_ptr g; /* The DDG of the insns in the partial schedule. */
189
190 int stage_count; /* The stage count of the partial schedule. */
191};
192
193
194static partial_schedule_ptr create_partial_schedule (int ii, ddg_ptr, int history);
195static void free_partial_schedule (partial_schedule_ptr);
196static void reset_partial_schedule (partial_schedule_ptr, int new_ii);
197void print_partial_schedule (partial_schedule_ptr, FILE *);
198static void verify_partial_schedule (partial_schedule_ptr, sbitmap);
199static ps_insn_ptr ps_add_node_check_conflicts (partial_schedule_ptr,
200 int, int, sbitmap, sbitmap);
201static void rotate_partial_schedule (partial_schedule_ptr, int);
202void set_row_column_for_ps (partial_schedule_ptr);
203static void ps_insert_empty_row (partial_schedule_ptr, int, sbitmap);
204static int compute_split_row (sbitmap, int, int, int, ddg_node_ptr);
205
206
207/* This page defines constants and structures for the modulo scheduling
208 driver. */
209
210static int sms_order_nodes (ddg_ptr, int, int *, int *);
211static void set_node_sched_params (ddg_ptr);
212static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int, int *);
213static void permute_partial_schedule (partial_schedule_ptr, rtx_insn *);
214static void generate_prolog_epilog (partial_schedule_ptr, struct loop *,
215 rtx, rtx);
216static int calculate_stage_count (partial_schedule_ptr, int);
217static void calculate_must_precede_follow (ddg_node_ptr, int, int,
218 int, int, sbitmap, sbitmap, sbitmap);
219static int get_sched_window (partial_schedule_ptr, ddg_node_ptr,
220 sbitmap, int, int *, int *, int *);
221static bool try_scheduling_node_in_cycle (partial_schedule_ptr, int, int,
222 sbitmap, int *, sbitmap, sbitmap);
223static void remove_node_from_ps (partial_schedule_ptr, ps_insn_ptr);
224
225#define NODE_ASAP(node) ((node)->aux.count)
226
227#define SCHED_PARAMS(x) (&node_sched_param_vec[x])
228#define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
229#define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
230#define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
231#define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
232
233/* The scheduling parameters held for each node. */
234typedef struct node_sched_params
235{
236 int time; /* The absolute scheduling cycle. */
237
238 int row; /* Holds time % ii. */
239 int stage; /* Holds time / ii. */
240
241 /* The column of a node inside the ps. If nodes u, v are on the same row,
242 u will precede v if column (u) < column (v). */
243 int column;
244} *node_sched_params_ptr;
245
246/* The following three functions are copied from the current scheduler
247 code in order to use sched_analyze() for computing the dependencies.
248 They are used when initializing the sched_info structure. */
249static const char *
250sms_print_insn (const rtx_insn *insn, int aligned ATTRIBUTE_UNUSED)
251{
252 static char tmp[80];
253
254 sprintf (tmp, "i%4d", INSN_UID (insn));
255 return tmp;
256}
257
258static void
259compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
260 regset used ATTRIBUTE_UNUSED)
261{
262}
263
264static struct common_sched_info_def sms_common_sched_info;
265
266static struct sched_deps_info_def sms_sched_deps_info =
267 {
268 compute_jump_reg_dependencies,
269 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
270 NULL,
271 0, 0, 0
272 };
273
274static struct haifa_sched_info sms_sched_info =
275{
276 NULL,
277 NULL,
278 NULL,
279 NULL,
280 NULL,
281 sms_print_insn,
282 NULL,
283 NULL, /* insn_finishes_block_p */
284 NULL, NULL,
285 NULL, NULL,
286 0, 0,
287
288 NULL, NULL, NULL, NULL,
289 NULL, NULL,
290 0
291};
292
293/* Partial schedule instruction ID in PS is a register move. Return
294 information about it. */
295static struct ps_reg_move_info *
296ps_reg_move (partial_schedule_ptr ps, int id)
297{
298 gcc_checking_assert (id >= ps->g->num_nodes);
299 return &ps->reg_moves[id - ps->g->num_nodes];
300}
301
302/* Return the rtl instruction that is being scheduled by partial schedule
303 instruction ID, which belongs to schedule PS. */
304static rtx_insn *
305ps_rtl_insn (partial_schedule_ptr ps, int id)
306{
307 if (id < ps->g->num_nodes)
308 return ps->g->nodes[id].insn;
309 else
310 return ps_reg_move (ps, id)->insn;
311}
312
313/* Partial schedule instruction ID, which belongs to PS, occurred in
314 the original (unscheduled) loop. Return the first instruction
315 in the loop that was associated with ps_rtl_insn (PS, ID).
316 If the instruction had some notes before it, this is the first
317 of those notes. */
318static rtx_insn *
319ps_first_note (partial_schedule_ptr ps, int id)
320{
321 gcc_assert (id < ps->g->num_nodes);
322 return ps->g->nodes[id].first_note;
323}
324
325/* Return the number of consecutive stages that are occupied by
326 partial schedule instruction ID in PS. */
327static int
328ps_num_consecutive_stages (partial_schedule_ptr ps, int id)
329{
330 if (id < ps->g->num_nodes)
331 return 1;
332 else
333 return ps_reg_move (ps, id)->num_consecutive_stages;
334}
335
336/* Given HEAD and TAIL which are the first and last insns in a loop;
337 return the register which controls the loop. Return zero if it has
338 more than one occurrence in the loop besides the control part or the
339 do-loop pattern is not of the form we expect. */
340static rtx
341doloop_register_get (rtx_insn *head, rtx_insn *tail)
342{
343 rtx reg, condition;
344 rtx_insn *insn, *first_insn_not_to_check;
345
346 if (!JUMP_P (tail))
347 return NULL_RTX;
348
349 if (!targetm.code_for_doloop_end)
350 return NULL_RTX;
351
352 /* TODO: Free SMS's dependence on doloop_condition_get. */
353 condition = doloop_condition_get (tail);
354 if (! condition)
355 return NULL_RTX;
356
357 if (REG_P (XEXP (condition, 0)))
358 reg = XEXP (condition, 0);
359 else if (GET_CODE (XEXP (condition, 0)) == PLUS
360 && REG_P (XEXP (XEXP (condition, 0), 0)))
361 reg = XEXP (XEXP (condition, 0), 0);
362 else
363 gcc_unreachable ();
364
365 /* Check that the COUNT_REG has no other occurrences in the loop
366 until the decrement. We assume the control part consists of
367 either a single (parallel) branch-on-count or a (non-parallel)
368 branch immediately preceded by a single (decrement) insn. */
369 first_insn_not_to_check = (GET_CODE (PATTERN (tail)) == PARALLEL ? tail
370 : prev_nondebug_insn (tail));
371
372 for (insn = head; insn != first_insn_not_to_check; insn = NEXT_INSN (insn))
373 if (!DEBUG_INSN_P (insn) && reg_mentioned_p (reg, insn))
374 {
375 if (dump_file)
376 {
377 fprintf (dump_file, "SMS count_reg found ");
378 print_rtl_single (dump_file, reg);
379 fprintf (dump_file, " outside control in insn:\n");
380 print_rtl_single (dump_file, insn);
381 }
382
383 return NULL_RTX;
384 }
385
386 return reg;
387}
388
389/* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
390 that the number of iterations is a compile-time constant. If so,
391 return the rtx_insn that sets COUNT_REG to a constant, and set COUNT to
392 this constant. Otherwise return 0. */
393static rtx_insn *
394const_iteration_count (rtx count_reg, basic_block pre_header,
395 int64_t * count)
396{
397 rtx_insn *insn;
398 rtx_insn *head, *tail;
399
400 if (! pre_header)
401 return NULL;
402
403 get_ebb_head_tail (pre_header, pre_header, &head, &tail);
404
405 for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn))
406 if (NONDEBUG_INSN_P (insn) && single_set (insn) &&
407 rtx_equal_p (count_reg, SET_DEST (single_set (insn))))
408 {
409 rtx pat = single_set (insn);
410
411 if (CONST_INT_P (SET_SRC (pat)))
412 {
413 *count = INTVAL (SET_SRC (pat));
414 return insn;
415 }
416
417 return NULL;
418 }
419
420 return NULL;
421}
422
423/* A very simple resource-based lower bound on the initiation interval.
424 ??? Improve the accuracy of this bound by considering the
425 utilization of various units. */
426static int
427res_MII (ddg_ptr g)
428{
429 if (targetm.sched.sms_res_mii)
430 return targetm.sched.sms_res_mii (g);
431
432 return ((g->num_nodes - g->num_debug) / issue_rate);
433}
434
435
436/* A vector that contains the sched data for each ps_insn. */
437static vec<node_sched_params> node_sched_param_vec;
438
439/* Allocate sched_params for each node and initialize it. */
440static void
441set_node_sched_params (ddg_ptr g)
442{
443 node_sched_param_vec.truncate (0);
444 node_sched_param_vec.safe_grow_cleared (g->num_nodes);
445}
446
447/* Make sure that node_sched_param_vec has an entry for every move in PS. */
448static void
449extend_node_sched_params (partial_schedule_ptr ps)
450{
451 node_sched_param_vec.safe_grow_cleared (ps->g->num_nodes
452 + ps->reg_moves.length ());
453}
454
455/* Update the sched_params (time, row and stage) for node U using the II,
456 the CYCLE of U and MIN_CYCLE.
457 We're not simply taking the following
458 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
459 because the stages may not be aligned on cycle 0. */
460static void
461update_node_sched_params (int u, int ii, int cycle, int min_cycle)
462{
463 int sc_until_cycle_zero;
464 int stage;
465
466 SCHED_TIME (u) = cycle;
467 SCHED_ROW (u) = SMODULO (cycle, ii);
468
469 /* The calculation of stage count is done adding the number
470 of stages before cycle zero and after cycle zero. */
471 sc_until_cycle_zero = CALC_STAGE_COUNT (-1, min_cycle, ii);
472
473 if (SCHED_TIME (u) < 0)
474 {
475 stage = CALC_STAGE_COUNT (-1, SCHED_TIME (u), ii);
476 SCHED_STAGE (u) = sc_until_cycle_zero - stage;
477 }
478 else
479 {
480 stage = CALC_STAGE_COUNT (SCHED_TIME (u), 0, ii);
481 SCHED_STAGE (u) = sc_until_cycle_zero + stage - 1;
482 }
483}
484
485static void
486print_node_sched_params (FILE *file, int num_nodes, partial_schedule_ptr ps)
487{
488 int i;
489
490 if (! file)
491 return;
492 for (i = 0; i < num_nodes; i++)
493 {
494 node_sched_params_ptr nsp = SCHED_PARAMS (i);
495
496 fprintf (file, "Node = %d; INSN = %d\n", i,
497 INSN_UID (ps_rtl_insn (ps, i)));
498 fprintf (file, " asap = %d:\n", NODE_ASAP (&ps->g->nodes[i]));
499 fprintf (file, " time = %d:\n", nsp->time);
500 fprintf (file, " stage = %d:\n", nsp->stage);
501 }
502}
503
504/* Set SCHED_COLUMN for each instruction in row ROW of PS. */
505static void
506set_columns_for_row (partial_schedule_ptr ps, int row)
507{
508 ps_insn_ptr cur_insn;
509 int column;
510
511 column = 0;
512 for (cur_insn = ps->rows[row]; cur_insn; cur_insn = cur_insn->next_in_row)
513 SCHED_COLUMN (cur_insn->id) = column++;
514}
515
516/* Set SCHED_COLUMN for each instruction in PS. */
517static void
518set_columns_for_ps (partial_schedule_ptr ps)
519{
520 int row;
521
522 for (row = 0; row < ps->ii; row++)
523 set_columns_for_row (ps, row);
524}
525
526/* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
527 Its single predecessor has already been scheduled, as has its
528 ddg node successors. (The move may have also another move as its
529 successor, in which case that successor will be scheduled later.)
530
531 The move is part of a chain that satisfies register dependencies
532 between a producing ddg node and various consuming ddg nodes.
533 If some of these dependencies have a distance of 1 (meaning that
534 the use is upward-exposed) then DISTANCE1_USES is nonnull and
535 contains the set of uses with distance-1 dependencies.
536 DISTANCE1_USES is null otherwise.
537
538 MUST_FOLLOW is a scratch bitmap that is big enough to hold
539 all current ps_insn ids.
540
541 Return true on success. */
542static bool
543schedule_reg_move (partial_schedule_ptr ps, int i_reg_move,
544 sbitmap distance1_uses, sbitmap must_follow)
545{
546 unsigned int u;
547 int this_time, this_distance, this_start, this_end, this_latency;
548 int start, end, c, ii;
549 sbitmap_iterator sbi;
550 ps_reg_move_info *move;
551 rtx_insn *this_insn;
552 ps_insn_ptr psi;
553
554 move = ps_reg_move (ps, i_reg_move);
555 ii = ps->ii;
556 if (dump_file)
557 {
558 fprintf (dump_file, "Scheduling register move INSN %d; ii = %d"
559 ", min cycle = %d\n\n", INSN_UID (move->insn), ii,
560 PS_MIN_CYCLE (ps));
561 print_rtl_single (dump_file, move->insn);
562 fprintf (dump_file, "\n%11s %11s %5s\n", "start", "end", "time");
563 fprintf (dump_file, "=========== =========== =====\n");
564 }
565
566 start = INT_MIN;
567 end = INT_MAX;
568
569 /* For dependencies of distance 1 between a producer ddg node A
570 and consumer ddg node B, we have a chain of dependencies:
571
572 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
573
574 where Mi is the ith move. For dependencies of distance 0 between
575 a producer ddg node A and consumer ddg node C, we have a chain of
576 dependencies:
577
578 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
579
580 where Mi' occupies the same position as Mi but occurs a stage later.
581 We can only schedule each move once, so if we have both types of
582 chain, we model the second as:
583
584 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
585
586 First handle the dependencies between the previously-scheduled
587 predecessor and the move. */
588 this_insn = ps_rtl_insn (ps, move->def);
589 this_latency = insn_latency (this_insn, move->insn);
590 this_distance = distance1_uses && move->def < ps->g->num_nodes ? 1 : 0;
591 this_time = SCHED_TIME (move->def) - this_distance * ii;
592 this_start = this_time + this_latency;
593 this_end = this_time + ii;
594 if (dump_file)
595 fprintf (dump_file, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
596 this_start, this_end, SCHED_TIME (move->def),
597 INSN_UID (this_insn), this_latency, this_distance,
598 INSN_UID (move->insn));
599
600 if (start < this_start)
601 start = this_start;
602 if (end > this_end)
603 end = this_end;
604
605 /* Handle the dependencies between the move and previously-scheduled
606 successors. */
607 EXECUTE_IF_SET_IN_BITMAP (move->uses, 0, u, sbi)
608 {
609 this_insn = ps_rtl_insn (ps, u);
610 this_latency = insn_latency (move->insn, this_insn);
611 if (distance1_uses && !bitmap_bit_p (distance1_uses, u))
612 this_distance = -1;
613 else
614 this_distance = 0;
615 this_time = SCHED_TIME (u) + this_distance * ii;
616 this_start = this_time - ii;
617 this_end = this_time - this_latency;
618 if (dump_file)
619 fprintf (dump_file, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
620 this_start, this_end, SCHED_TIME (u), INSN_UID (move->insn),
621 this_latency, this_distance, INSN_UID (this_insn));
622
623 if (start < this_start)
624 start = this_start;
625 if (end > this_end)
626 end = this_end;
627 }
628
629 if (dump_file)
630 {
631 fprintf (dump_file, "----------- ----------- -----\n");
632 fprintf (dump_file, "%11d %11d %5s %s\n", start, end, "", "(max, min)");
633 }
634
635 bitmap_clear (must_follow);
636 bitmap_set_bit (must_follow, move->def);
637
638 start = MAX (start, end - (ii - 1));
639 for (c = end; c >= start; c--)
640 {
641 psi = ps_add_node_check_conflicts (ps, i_reg_move, c,
642 move->uses, must_follow);
643 if (psi)
644 {
645 update_node_sched_params (i_reg_move, ii, c, PS_MIN_CYCLE (ps));
646 if (dump_file)
647 fprintf (dump_file, "\nScheduled register move INSN %d at"
648 " time %d, row %d\n\n", INSN_UID (move->insn), c,
649 SCHED_ROW (i_reg_move));
650 return true;
651 }
652 }
653
654 if (dump_file)
655 fprintf (dump_file, "\nNo available slot\n\n");
656
657 return false;
658}
659
660/*
661 Breaking intra-loop register anti-dependences:
662 Each intra-loop register anti-dependence implies a cross-iteration true
663 dependence of distance 1. Therefore, we can remove such false dependencies
664 and figure out if the partial schedule broke them by checking if (for a
665 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
666 if so generate a register move. The number of such moves is equal to:
667 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
668 nreg_moves = ----------------------------------- + 1 - { dependence.
669 ii { 1 if not.
670*/
671static bool
672schedule_reg_moves (partial_schedule_ptr ps)
673{
674 ddg_ptr g = ps->g;
675 int ii = ps->ii;
676 int i;
677
678 for (i = 0; i < g->num_nodes; i++)
679 {
680 ddg_node_ptr u = &g->nodes[i];
681 ddg_edge_ptr e;
682 int nreg_moves = 0, i_reg_move;
683 rtx prev_reg, old_reg;
684 int first_move;
685 int distances[2];
686 sbitmap distance1_uses;
687 rtx set = single_set (u->insn);
688
689 /* Skip instructions that do not set a register. */
690 if ((set && !REG_P (SET_DEST (set))))
691 continue;
692
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)
698 {
699 int nreg_moves4e = (SCHED_TIME (e->dest->cuid)
700 - SCHED_TIME (e->src->cuid)) / ii;
701
702 if (e->distance == 1)
703 nreg_moves4e = (SCHED_TIME (e->dest->cuid)
704 - SCHED_TIME (e->src->cuid) + ii) / ii;
705
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))
710 nreg_moves4e--;
711
712 if (nreg_moves4e >= 1)
713 {
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. */
719 gcc_assert (set);
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));
724 }
725
726 if (nreg_moves4e)
727 {
728 gcc_assert (e->distance < 2);
729 distances[e->distance] = true;
730 }
731 nreg_moves = MAX (nreg_moves, nreg_moves4e);
732 }
733
734 if (nreg_moves == 0)
735 continue;
736
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);
741
742 /* Record the moves associated with this node. */
743 first_move += ps->g->num_nodes;
744
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++)
748 {
749 ps_reg_move_info *move = ps_reg_move (ps, first_move + i_reg_move);
750
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);
758
759 prev_reg = move->new_reg;
760 }
761
762 distance1_uses = distances[1] ? sbitmap_alloc (g->num_nodes) : NULL;
763
764 if (distance1_uses)
765 bitmap_clear (distance1_uses);
766
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)
772 {
773 int dest_copy = (SCHED_TIME (e->dest->cuid)
774 - SCHED_TIME (e->src->cuid)) / ii;
775
776 if (e->distance == 1)
777 dest_copy = (SCHED_TIME (e->dest->cuid)
778 - SCHED_TIME (e->src->cuid) + ii) / ii;
779
780 if (SCHED_ROW (e->dest->cuid) == SCHED_ROW (e->src->cuid)
781 && SCHED_COLUMN (e->dest->cuid) < SCHED_COLUMN (e->src->cuid))
782 dest_copy--;
783
784 if (dest_copy)
785 {
786 ps_reg_move_info *move;
787
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);
792 }
793 }
794
795 auto_sbitmap must_follow (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))
799 break;
800 if (distance1_uses)
801 sbitmap_free (distance1_uses);
802 if (i_reg_move < nreg_moves)
803 return false;
804 }
805 return true;
806}
807
808/* Emit the moves associated with PS. Apply the substitutions
809 associated with them. */
810static void
811apply_reg_moves (partial_schedule_ptr ps)
812{
813 ps_reg_move_info *move;
814 int i;
815
816 FOR_EACH_VEC_ELT (ps->reg_moves, i, move)
817 {
818 unsigned int i_use;
819 sbitmap_iterator sbi;
820
821 EXECUTE_IF_SET_IN_BITMAP (move->uses, 0, i_use, sbi)
822 {
823 replace_rtx (ps->g->nodes[i_use].insn, move->old_reg, move->new_reg);
824 df_insn_rescan (ps->g->nodes[i_use].insn);
825 }
826 }
827}
828
829/* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
830 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
831 will move to cycle zero. */
832static void
833reset_sched_times (partial_schedule_ptr ps, int amount)
834{
835 int row;
836 int ii = ps->ii;
837 ps_insn_ptr crr_insn;
838
839 for (row = 0; row < ii; row++)
840 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
841 {
842 int u = crr_insn->id;
843 int normalized_time = SCHED_TIME (u) - amount;
844 int new_min_cycle = PS_MIN_CYCLE (ps) - amount;
845
846 if (dump_file)
847 {
848 /* Print the scheduling times after the rotation. */
849 rtx_insn *insn = ps_rtl_insn (ps, u);
850
851 fprintf (dump_file, "crr_insn->node=%d (insn id %d), "
852 "crr_insn->cycle=%d, min_cycle=%d", u,
853 INSN_UID (insn), normalized_time, new_min_cycle);
854 if (JUMP_P (insn))
855 fprintf (dump_file, " (branch)");
856 fprintf (dump_file, "\n");
857 }
858
859 gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
860 gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
861
862 crr_insn->cycle = normalized_time;
863 update_node_sched_params (u, ii, normalized_time, new_min_cycle);
864 }
865}
866
867/* Permute the insns according to their order in PS, from row 0 to
868 row ii-1, and position them right before LAST. This schedules
869 the insns of the loop kernel. */
870static void
871permute_partial_schedule (partial_schedule_ptr ps, rtx_insn *last)
872{
873 int ii = ps->ii;
874 int row;
875 ps_insn_ptr ps_ij;
876
877 for (row = 0; row < ii ; row++)
878 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
879 {
880 rtx_insn *insn = ps_rtl_insn (ps, ps_ij->id);
881
882 if (PREV_INSN (last) != insn)
883 {
884 if (ps_ij->id < ps->g->num_nodes)
885 reorder_insns_nobb (ps_first_note (ps, ps_ij->id), insn,
886 PREV_INSN (last));
887 else
888 add_insn_before (insn, last, NULL);
889 }
890 }
891}
892
893/* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
894 respectively only if cycle C falls on the border of the scheduling
895 window boundaries marked by START and END cycles. STEP is the
896 direction of the window. */
897static inline void
898set_must_precede_follow (sbitmap *tmp_follow, sbitmap must_follow,
899 sbitmap *tmp_precede, sbitmap must_precede, int c,
900 int start, int end, int step)
901{
902 *tmp_precede = NULL;
903 *tmp_follow = NULL;
904
905 if (c == start)
906 {
907 if (step == 1)
908 *tmp_precede = must_precede;
909 else /* step == -1. */
910 *tmp_follow = must_follow;
911 }
912 if (c == end - step)
913 {
914 if (step == 1)
915 *tmp_follow = must_follow;
916 else /* step == -1. */
917 *tmp_precede = must_precede;
918 }
919
920}
921
922/* Return True if the branch can be moved to row ii-1 while
923 normalizing the partial schedule PS to start from cycle zero and thus
924 optimize the SC. Otherwise return False. */
925static bool
926optimize_sc (partial_schedule_ptr ps, ddg_ptr g)
927{
928 int amount = PS_MIN_CYCLE (ps);
929 int start, end, step;
930 int ii = ps->ii;
931 bool ok = false;
932 int stage_count, stage_count_curr;
933
934 /* Compare the SC after normalization and SC after bringing the branch
935 to row ii-1. If they are equal just bail out. */
936 stage_count = calculate_stage_count (ps, amount);
937 stage_count_curr =
938 calculate_stage_count (ps, SCHED_TIME (g->closing_branch->cuid) - (ii - 1));
939
940 if (stage_count == stage_count_curr)
941 {
942 if (dump_file)
943 fprintf (dump_file, "SMS SC already optimized.\n");
944
945 return false;
946 }
947
948 if (dump_file)
949 {
950 fprintf (dump_file, "SMS Trying to optimize branch location\n");
951 fprintf (dump_file, "SMS partial schedule before trial:\n");
952 print_partial_schedule (ps, dump_file);
953 }
954
955 /* First, normalize the partial scheduling. */
956 reset_sched_times (ps, amount);
957 rotate_partial_schedule (ps, amount);
958 if (dump_file)
959 {
960 fprintf (dump_file,
961 "SMS partial schedule after normalization (ii, %d, SC %d):\n",
962 ii, stage_count);
963 print_partial_schedule (ps, dump_file);
964 }
965
966 if (SMODULO (SCHED_TIME (g->closing_branch->cuid), ii) == ii - 1)
967 return true;
968
969 auto_sbitmap sched_nodes (g->num_nodes);
970 bitmap_ones (sched_nodes);
971
972 /* Calculate the new placement of the branch. It should be in row
973 ii-1 and fall into it's scheduling window. */
974 if (get_sched_window (ps, g->closing_branch, sched_nodes, ii, &start,
975 &step, &end) == 0)
976 {
977 bool success;
978 ps_insn_ptr next_ps_i;
979 int branch_cycle = SCHED_TIME (g->closing_branch->cuid);
980 int row = SMODULO (branch_cycle, ps->ii);
981 int num_splits = 0;
982 sbitmap tmp_precede, tmp_follow;
983 int min_cycle, c;
984
985 if (dump_file)
986 fprintf (dump_file, "\nTrying to schedule node %d "
987 "INSN = %d in (%d .. %d) step %d\n",
988 g->closing_branch->cuid,
989 (INSN_UID (g->closing_branch->insn)), start, end, step);
990
991 gcc_assert ((step > 0 && start < end) || (step < 0 && start > end));
992 if (step == 1)
993 {
994 c = start + ii - SMODULO (start, ii) - 1;
995 gcc_assert (c >= start);
996 if (c >= end)
997 {
998 if (dump_file)
999 fprintf (dump_file,
1000 "SMS failed to schedule branch at cycle: %d\n", c);
1001 return false;
1002 }
1003 }
1004 else
1005 {
1006 c = start - SMODULO (start, ii) - 1;
1007 gcc_assert (c <= start);
1008
1009 if (c <= end)
1010 {
1011 if (dump_file)
1012 fprintf (dump_file,
1013 "SMS failed to schedule branch at cycle: %d\n", c);
1014 return false;
1015 }
1016 }
1017
1018 auto_sbitmap must_precede (g->num_nodes);
1019 auto_sbitmap must_follow (g->num_nodes);
1020
1021 /* Try to schedule the branch is it's new cycle. */
1022 calculate_must_precede_follow (g->closing_branch, start, end,
1023 step, ii, sched_nodes,
1024 must_precede, must_follow);
1025
1026 set_must_precede_follow (&tmp_follow, must_follow, &tmp_precede,
1027 must_precede, c, start, end, step);
1028
1029 /* Find the element in the partial schedule related to the closing
1030 branch so we can remove it from it's current cycle. */
1031 for (next_ps_i = ps->rows[row];
1032 next_ps_i; next_ps_i = next_ps_i->next_in_row)
1033 if (next_ps_i->id == g->closing_branch->cuid)
1034 break;
1035
1036 min_cycle = PS_MIN_CYCLE (ps) - SMODULO (PS_MIN_CYCLE (ps), ps->ii);
1037 remove_node_from_ps (ps, next_ps_i);
1038 success =
1039 try_scheduling_node_in_cycle (ps, g->closing_branch->cuid, c,
1040 sched_nodes, &num_splits,
1041 tmp_precede, tmp_follow);
1042 gcc_assert (num_splits == 0);
1043 if (!success)
1044 {
1045 if (dump_file)
1046 fprintf (dump_file,
1047 "SMS failed to schedule branch at cycle: %d, "
1048 "bringing it back to cycle %d\n", c, branch_cycle);
1049
1050 /* The branch was failed to be placed in row ii - 1.
1051 Put it back in it's original place in the partial
1052 schedualing. */
1053 set_must_precede_follow (&tmp_follow, must_follow, &tmp_precede,
1054 must_precede, branch_cycle, start, end,
1055 step);
1056 success =
1057 try_scheduling_node_in_cycle (ps, g->closing_branch->cuid,
1058 branch_cycle, sched_nodes,
1059 &num_splits, tmp_precede,
1060 tmp_follow);
1061 gcc_assert (success && (num_splits == 0));
1062 ok = false;
1063 }
1064 else
1065 {
1066 /* The branch is placed in row ii - 1. */
1067 if (dump_file)
1068 fprintf (dump_file,
1069 "SMS success in moving branch to cycle %d\n", c);
1070
1071 update_node_sched_params (g->closing_branch->cuid, ii, c,
1072 PS_MIN_CYCLE (ps));
1073 ok = true;
1074 }
1075
1076 /* This might have been added to a new first stage. */
1077 if (PS_MIN_CYCLE (ps) < min_cycle)
1078 reset_sched_times (ps, 0);
1079 }
1080
1081 return ok;
1082}
1083
1084static void
1085duplicate_insns_of_cycles (partial_schedule_ptr ps, int from_stage,
1086 int to_stage, rtx count_reg)
1087{
1088 int row;
1089 ps_insn_ptr ps_ij;
1090
1091 for (row = 0; row < ps->ii; row++)
1092 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
1093 {
1094 int u = ps_ij->id;
1095 int first_u, last_u;
1096 rtx_insn *u_insn;
1097
1098 /* Do not duplicate any insn which refers to count_reg as it
1099 belongs to the control part.
1100 The closing branch is scheduled as well and thus should
1101 be ignored.
1102 TODO: This should be done by analyzing the control part of
1103 the loop. */
1104 u_insn = ps_rtl_insn (ps, u);
1105 if (reg_mentioned_p (count_reg, u_insn)
1106 || JUMP_P (u_insn))
1107 continue;
1108
1109 first_u = SCHED_STAGE (u);
1110 last_u = first_u + ps_num_consecutive_stages (ps, u) - 1;
1111 if (from_stage <= last_u && to_stage >= first_u)
1112 {
1113 if (u < ps->g->num_nodes)
1114 duplicate_insn_chain (ps_first_note (ps, u), u_insn);
1115 else
1116 emit_insn (copy_rtx (PATTERN (u_insn)));
1117 }
1118 }
1119}
1120
1121
1122/* Generate the instructions (including reg_moves) for prolog & epilog. */
1123static void
1124generate_prolog_epilog (partial_schedule_ptr ps, struct loop *loop,
1125 rtx count_reg, rtx count_init)
1126{
1127 int i;
1128 int last_stage = PS_STAGE_COUNT (ps) - 1;
1129 edge e;
1130
1131 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1132 start_sequence ();
1133
1134 if (!count_init)
1135 {
1136 /* Generate instructions at the beginning of the prolog to
1137 adjust the loop count by STAGE_COUNT. If loop count is constant
1138 (count_init), this constant is adjusted by STAGE_COUNT in
1139 generate_prolog_epilog function. */
1140 rtx sub_reg = NULL_RTX;
1141
1142 sub_reg = expand_simple_binop (GET_MODE (count_reg), MINUS, count_reg,
1143 gen_int_mode (last_stage,
1144 GET_MODE (count_reg)),
1145 count_reg, 1, OPTAB_DIRECT);
1146 gcc_assert (REG_P (sub_reg));
1147 if (REGNO (sub_reg) != REGNO (count_reg))
1148 emit_move_insn (count_reg, sub_reg);
1149 }
1150
1151 for (i = 0; i < last_stage; i++)
1152 duplicate_insns_of_cycles (ps, 0, i, count_reg);
1153
1154 /* Put the prolog on the entry edge. */
1155 e = loop_preheader_edge (loop);
1156 split_edge_and_insert (e, get_insns ());
1157 if (!flag_resched_modulo_sched)
1158 e->dest->flags |= BB_DISABLE_SCHEDULE;
1159
1160 end_sequence ();
1161
1162 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1163 start_sequence ();
1164
1165 for (i = 0; i < last_stage; i++)
1166 duplicate_insns_of_cycles (ps, i + 1, last_stage, count_reg);
1167
1168 /* Put the epilogue on the exit edge. */
1169 gcc_assert (single_exit (loop));
1170 e = single_exit (loop);
1171 split_edge_and_insert (e, get_insns ());
1172 if (!flag_resched_modulo_sched)
1173 e->dest->flags |= BB_DISABLE_SCHEDULE;
1174
1175 end_sequence ();
1176}
1177
1178/* Mark LOOP as software pipelined so the later
1179 scheduling passes don't touch it. */
1180static void
1181mark_loop_unsched (struct loop *loop)
1182{
1183 unsigned i;
1184 basic_block *bbs = get_loop_body (loop);
1185
1186 for (i = 0; i < loop->num_nodes; i++)
1187 bbs[i]->flags |= BB_DISABLE_SCHEDULE;
1188
1189 free (bbs);
1190}
1191
1192/* Return true if all the BBs of the loop are empty except the
1193 loop header. */
1194static bool
1195loop_single_full_bb_p (struct loop *loop)
1196{
1197 unsigned i;
1198 basic_block *bbs = get_loop_body (loop);
1199
1200 for (i = 0; i < loop->num_nodes ; i++)
1201 {
1202 rtx_insn *head, *tail;
1203 bool empty_bb = true;
1204
1205 if (bbs[i] == loop->header)
1206 continue;
1207
1208 /* Make sure that basic blocks other than the header
1209 have only notes labels or jumps. */
1210 get_ebb_head_tail (bbs[i], bbs[i], &head, &tail);
1211 for (; head != NEXT_INSN (tail); head = NEXT_INSN (head))
1212 {
1213 if (NOTE_P (head) || LABEL_P (head)
1214 || (INSN_P (head) && (DEBUG_INSN_P (head) || JUMP_P (head))))
1215 continue;
1216 empty_bb = false;
1217 break;
1218 }
1219
1220 if (! empty_bb)
1221 {
1222 free (bbs);
1223 return false;
1224 }
1225 }
1226 free (bbs);
1227 return true;
1228}
1229
1230/* Dump file:line from INSN's location info to dump_file. */
1231
1232static void
1233dump_insn_location (rtx_insn *insn)
1234{
1235 if (dump_file && INSN_HAS_LOCATION (insn))
1236 {
1237 expanded_location xloc = insn_location (insn);
1238 fprintf (dump_file, " %s:%i", xloc.file, xloc.line);
1239 }
1240}
1241
1242/* A simple loop from SMS point of view; it is a loop that is composed of
1243 either a single basic block or two BBs - a header and a latch. */
1244#define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1245 && (EDGE_COUNT (loop->latch->preds) == 1) \
1246 && (EDGE_COUNT (loop->latch->succs) == 1))
1247
1248/* Return true if the loop is in its canonical form and false if not.
1249 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
1250static bool
1251loop_canon_p (struct loop *loop)
1252{
1253
1254 if (loop->inner || !loop_outer (loop))
1255 {
1256 if (dump_file)
1257 fprintf (dump_file, "SMS loop inner or !loop_outer\n");
1258 return false;
1259 }
1260
1261 if (!single_exit (loop))
1262 {
1263 if (dump_file)
1264 {
1265 rtx_insn *insn = BB_END (loop->header);
1266
1267 fprintf (dump_file, "SMS loop many exits");
1268 dump_insn_location (insn);
1269 fprintf (dump_file, "\n");
1270 }
1271 return false;
1272 }
1273
1274 if (! SIMPLE_SMS_LOOP_P (loop) && ! loop_single_full_bb_p (loop))
1275 {
1276 if (dump_file)
1277 {
1278 rtx_insn *insn = BB_END (loop->header);
1279
1280 fprintf (dump_file, "SMS loop many BBs.");
1281 dump_insn_location (insn);
1282 fprintf (dump_file, "\n");
1283 }
1284 return false;
1285 }
1286
1287 return true;
1288}
1289
1290/* If there are more than one entry for the loop,
1291 make it one by splitting the first entry edge and
1292 redirecting the others to the new BB. */
1293static void
1294canon_loop (struct loop *loop)
1295{
1296 edge e;
1297 edge_iterator i;
1298
1299 /* Avoid annoying special cases of edges going to exit
1300 block. */
1301 FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
1302 if ((e->flags & EDGE_FALLTHRU) && (EDGE_COUNT (e->src->succs) > 1))
1303 split_edge (e);
1304
1305 if (loop->latch == loop->header
1306 || EDGE_COUNT (loop->latch->succs) > 1)
1307 {
1308 FOR_EACH_EDGE (e, i, loop->header->preds)
1309 if (e->src == loop->latch)
1310 break;
1311 split_edge (e);
1312 }
1313}
1314
1315/* Setup infos. */
1316static void
1317setup_sched_infos (void)
1318{
1319 memcpy (&sms_common_sched_info, &haifa_common_sched_info,
1320 sizeof (sms_common_sched_info));
1321 sms_common_sched_info.sched_pass_id = SCHED_SMS_PASS;
1322 common_sched_info = &sms_common_sched_info;
1323
1324 sched_deps_info = &sms_sched_deps_info;
1325 current_sched_info = &sms_sched_info;
1326}
1327
1328/* Probability in % that the sms-ed loop rolls enough so that optimized
1329 version may be entered. Just a guess. */
1330#define PROB_SMS_ENOUGH_ITERATIONS 80
1331
1332/* Used to calculate the upper bound of ii. */
1333#define MAXII_FACTOR 2
1334
1335/* Main entry point, perform SMS scheduling on the loops of the function
1336 that consist of single basic blocks. */
1337static void
1338sms_schedule (void)
1339{
1340 rtx_insn *insn;
1341 ddg_ptr *g_arr, g;
1342 int * node_order;
1343 int maxii, max_asap;
1344 partial_schedule_ptr ps;
1345 basic_block bb = NULL;
1346 struct loop *loop;
1347 basic_block condition_bb = NULL;
1348 edge latch_edge;
1349 gcov_type trip_count = 0;
1350
1351 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
1352 | LOOPS_HAVE_RECORDED_EXITS);
1353 if (number_of_loops (cfun) <= 1)
1354 {
1355 loop_optimizer_finalize ();
1356 return; /* There are no loops to schedule. */
1357 }
1358
1359 /* Initialize issue_rate. */
1360 if (targetm.sched.issue_rate)
1361 {
1362 int temp = reload_completed;
1363
1364 reload_completed = 1;
1365 issue_rate = targetm.sched.issue_rate ();
1366 reload_completed = temp;
1367 }
1368 else
1369 issue_rate = 1;
1370
1371 /* Initialize the scheduler. */
1372 setup_sched_infos ();
1373 haifa_sched_init ();
1374
1375 /* Allocate memory to hold the DDG array one entry for each loop.
1376 We use loop->num as index into this array. */
1377 g_arr = XCNEWVEC (ddg_ptr, number_of_loops (cfun));
1378
1379 if (dump_file)
1380 {
1381 fprintf (dump_file, "\n\nSMS analysis phase\n");
1382 fprintf (dump_file, "===================\n\n");
1383 }
1384
1385 /* Build DDGs for all the relevant loops and hold them in G_ARR
1386 indexed by the loop index. */
1387 FOR_EACH_LOOP (loop, 0)
1388 {
1389 rtx_insn *head, *tail;
1390 rtx count_reg;
1391
1392 /* For debugging. */
1393 if (dbg_cnt (sms_sched_loop) == false)
1394 {
1395 if (dump_file)
1396 fprintf (dump_file, "SMS reached max limit... \n");
1397
1398 break;
1399 }
1400
1401 if (dump_file)
1402 {
1403 rtx_insn *insn = BB_END (loop->header);
1404
1405 fprintf (dump_file, "SMS loop num: %d", loop->num);
1406 dump_insn_location (insn);
1407 fprintf (dump_file, "\n");
1408 }
1409
1410 if (! loop_canon_p (loop))
1411 continue;
1412
1413 if (! loop_single_full_bb_p (loop))
1414 {
1415 if (dump_file)
1416 fprintf (dump_file, "SMS not loop_single_full_bb_p\n");
1417 continue;
1418 }
1419
1420 bb = loop->header;
1421
1422 get_ebb_head_tail (bb, bb, &head, &tail);
1423 latch_edge = loop_latch_edge (loop);
1424 gcc_assert (single_exit (loop));
1425 if (single_exit (loop)->count () > profile_count::zero ())
1426 trip_count = latch_edge->count ().to_gcov_type ()
1427 / single_exit (loop)->count ().to_gcov_type ();
1428
1429 /* Perform SMS only on loops that their average count is above threshold. */
1430
1431 if ( latch_edge->count () > profile_count::zero ()
1432 && (latch_edge->count()
1433 < single_exit (loop)->count ().apply_scale
1434 (SMS_LOOP_AVERAGE_COUNT_THRESHOLD, 1)))
1435 {
1436 if (dump_file)
1437 {
1438 dump_insn_location (tail);
1439 fprintf (dump_file, "\nSMS single-bb-loop\n");
1440 if (profile_info && flag_branch_probabilities)
1441 {
1442 fprintf (dump_file, "SMS loop-count ");
1443 fprintf (dump_file, "%" PRId64,
1444 (int64_t) bb->count.to_gcov_type ());
1445 fprintf (dump_file, "\n");
1446 fprintf (dump_file, "SMS trip-count ");
1447 fprintf (dump_file, "%" PRId64,
1448 (int64_t) trip_count);
1449 fprintf (dump_file, "\n");
1450 fprintf (dump_file, "SMS profile-sum-max ");
1451 fprintf (dump_file, "%" PRId64,
1452 (int64_t) profile_info->sum_max);
1453 fprintf (dump_file, "\n");
1454 }
1455 }
1456 continue;
1457 }
1458
1459 /* Make sure this is a doloop. */
1460 if ( !(count_reg = doloop_register_get (head, tail)))
1461 {
1462 if (dump_file)
1463 fprintf (dump_file, "SMS doloop_register_get failed\n");
1464 continue;
1465 }
1466
1467 /* Don't handle BBs with calls or barriers
1468 or !single_set with the exception of instructions that include
1469 count_reg---these instructions are part of the control part
1470 that do-loop recognizes.
1471 ??? Should handle insns defining subregs. */
1472 for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn))
1473 {
1474 rtx set;
1475
1476 if (CALL_P (insn)
1477 || BARRIER_P (insn)
1478 || (NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
1479 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE
1480 && !reg_mentioned_p (count_reg, insn))
1481 || (INSN_P (insn) && (set = single_set (insn))
1482 && GET_CODE (SET_DEST (set)) == SUBREG))
1483 break;
1484 }
1485
1486 if (insn != NEXT_INSN (tail))
1487 {
1488 if (dump_file)
1489 {
1490 if (CALL_P (insn))
1491 fprintf (dump_file, "SMS loop-with-call\n");
1492 else if (BARRIER_P (insn))
1493 fprintf (dump_file, "SMS loop-with-barrier\n");
1494 else if ((NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
1495 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE))
1496 fprintf (dump_file, "SMS loop-with-not-single-set\n");
1497 else
1498 fprintf (dump_file, "SMS loop with subreg in lhs\n");
1499 print_rtl_single (dump_file, insn);
1500 }
1501
1502 continue;
1503 }
1504
1505 /* Always schedule the closing branch with the rest of the
1506 instructions. The branch is rotated to be in row ii-1 at the
1507 end of the scheduling procedure to make sure it's the last
1508 instruction in the iteration. */
1509 if (! (g = create_ddg (bb, 1)))
1510 {
1511 if (dump_file)
1512 fprintf (dump_file, "SMS create_ddg failed\n");
1513 continue;
1514 }
1515
1516 g_arr[loop->num] = g;
1517 if (dump_file)
1518 fprintf (dump_file, "...OK\n");
1519
1520 }
1521 if (dump_file)
1522 {
1523 fprintf (dump_file, "\nSMS transformation phase\n");
1524 fprintf (dump_file, "=========================\n\n");
1525 }
1526
1527 /* We don't want to perform SMS on new loops - created by versioning. */
1528 FOR_EACH_LOOP (loop, 0)
1529 {
1530 rtx_insn *head, *tail;
1531 rtx count_reg;
1532 rtx_insn *count_init;
1533 int mii, rec_mii, stage_count, min_cycle;
1534 int64_t loop_count = 0;
1535 bool opt_sc_p;
1536
1537 if (! (g = g_arr[loop->num]))
1538 continue;
1539
1540 if (dump_file)
1541 {
1542 rtx_insn *insn = BB_END (loop->header);
1543
1544 fprintf (dump_file, "SMS loop num: %d", loop->num);
1545 dump_insn_location (insn);
1546 fprintf (dump_file, "\n");
1547
1548 print_ddg (dump_file, g);
1549 }
1550
1551 get_ebb_head_tail (loop->header, loop->header, &head, &tail);
1552
1553 latch_edge = loop_latch_edge (loop);
1554 gcc_assert (single_exit (loop));
1555 if (single_exit (loop)->count ()> profile_count::zero ())
1556 trip_count = latch_edge->count ().to_gcov_type ()
1557 / single_exit (loop)->count ().to_gcov_type ();
1558
1559 if (dump_file)
1560 {
1561 dump_insn_location (tail);
1562 fprintf (dump_file, "\nSMS single-bb-loop\n");
1563 if (profile_info && flag_branch_probabilities)
1564 {
1565 fprintf (dump_file, "SMS loop-count ");
1566 fprintf (dump_file, "%" PRId64,
1567 (int64_t) bb->count.to_gcov_type ());
1568 fprintf (dump_file, "\n");
1569 fprintf (dump_file, "SMS profile-sum-max ");
1570 fprintf (dump_file, "%" PRId64,
1571 (int64_t) profile_info->sum_max);
1572 fprintf (dump_file, "\n");
1573 }
1574 fprintf (dump_file, "SMS doloop\n");
1575 fprintf (dump_file, "SMS built-ddg %d\n", g->num_nodes);
1576 fprintf (dump_file, "SMS num-loads %d\n", g->num_loads);
1577 fprintf (dump_file, "SMS num-stores %d\n", g->num_stores);
1578 }
1579
1580
1581 /* In case of th loop have doloop register it gets special
1582 handling. */
1583 count_init = NULL;
1584 if ((count_reg = doloop_register_get (head, tail)))
1585 {
1586 basic_block pre_header;
1587
1588 pre_header = loop_preheader_edge (loop)->src;
1589 count_init = const_iteration_count (count_reg, pre_header,
1590 &loop_count);
1591 }
1592 gcc_assert (count_reg);
1593
1594 if (dump_file && count_init)
1595 {
1596 fprintf (dump_file, "SMS const-doloop ");
1597 fprintf (dump_file, "%" PRId64,
1598 loop_count);
1599 fprintf (dump_file, "\n");
1600 }
1601
1602 node_order = XNEWVEC (int, g->num_nodes);
1603
1604 mii = 1; /* Need to pass some estimate of mii. */
1605 rec_mii = sms_order_nodes (g, mii, node_order, &max_asap);
1606 mii = MAX (res_MII (g), rec_mii);
1607 maxii = MAX (max_asap, MAXII_FACTOR * mii);
1608
1609 if (dump_file)
1610 fprintf (dump_file, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
1611 rec_mii, mii, maxii);
1612
1613 for (;;)
1614 {
1615 set_node_sched_params (g);
1616
1617 stage_count = 0;
1618 opt_sc_p = false;
1619 ps = sms_schedule_by_order (g, mii, maxii, node_order);
1620
1621 if (ps)
1622 {
1623 /* Try to achieve optimized SC by normalizing the partial
1624 schedule (having the cycles start from cycle zero).
1625 The branch location must be placed in row ii-1 in the
1626 final scheduling. If failed, shift all instructions to
1627 position the branch in row ii-1. */
1628 opt_sc_p = optimize_sc (ps, g);
1629 if (opt_sc_p)
1630 stage_count = calculate_stage_count (ps, 0);
1631 else
1632 {
1633 /* Bring the branch to cycle ii-1. */
1634 int amount = (SCHED_TIME (g->closing_branch->cuid)
1635 - (ps->ii - 1));
1636
1637 if (dump_file)
1638 fprintf (dump_file, "SMS schedule branch at cycle ii-1\n");
1639
1640 stage_count = calculate_stage_count (ps, amount);
1641 }
1642
1643 gcc_assert (stage_count >= 1);
1644 }
1645
1646 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
1647 1 means that there is no interleaving between iterations thus
1648 we let the scheduling passes do the job in this case. */
1649 if (stage_count < PARAM_VALUE (PARAM_SMS_MIN_SC)
1650 || (count_init && (loop_count <= stage_count))
1651 || (flag_branch_probabilities && (trip_count <= stage_count)))
1652 {
1653 if (dump_file)
1654 {
1655 fprintf (dump_file, "SMS failed... \n");
1656 fprintf (dump_file, "SMS sched-failed (stage-count=%d,"
1657 " loop-count=", stage_count);
1658 fprintf (dump_file, "%" PRId64, loop_count);
1659 fprintf (dump_file, ", trip-count=");
1660 fprintf (dump_file, "%" PRId64, trip_count);
1661 fprintf (dump_file, ")\n");
1662 }
1663 break;
1664 }
1665
1666 if (!opt_sc_p)
1667 {
1668 /* Rotate the partial schedule to have the branch in row ii-1. */
1669 int amount = SCHED_TIME (g->closing_branch->cuid) - (ps->ii - 1);
1670
1671 reset_sched_times (ps, amount);
1672 rotate_partial_schedule (ps, amount);
1673 }
1674
1675 set_columns_for_ps (ps);
1676
1677 min_cycle = PS_MIN_CYCLE (ps) - SMODULO (PS_MIN_CYCLE (ps), ps->ii);
1678 if (!schedule_reg_moves (ps))
1679 {
1680 mii = ps->ii + 1;
1681 free_partial_schedule (ps);
1682 continue;
1683 }
1684
1685 /* Moves that handle incoming values might have been added
1686 to a new first stage. Bump the stage count if so.
1687
1688 ??? Perhaps we could consider rotating the schedule here
1689 instead? */
1690 if (PS_MIN_CYCLE (ps) < min_cycle)
1691 {
1692 reset_sched_times (ps, 0);
1693 stage_count++;
1694 }
1695
1696 /* The stage count should now be correct without rotation. */
1697 gcc_checking_assert (stage_count == calculate_stage_count (ps, 0));
1698 PS_STAGE_COUNT (ps) = stage_count;
1699
1700 canon_loop (loop);
1701
1702 if (dump_file)
1703 {
1704 dump_insn_location (tail);
1705 fprintf (dump_file, " SMS succeeded %d %d (with ii, sc)\n",
1706 ps->ii, stage_count);
1707 print_partial_schedule (ps, dump_file);
1708 }
1709
1710 /* case the BCT count is not known , Do loop-versioning */
1711 if (count_reg && ! count_init)
1712 {
1713 rtx comp_rtx = gen_rtx_GT (VOIDmode, count_reg,
1714 gen_int_mode (stage_count,
1715 GET_MODE (count_reg)));
1716 profile_probability prob = profile_probability::guessed_always ()
1717 .apply_scale (PROB_SMS_ENOUGH_ITERATIONS, 100);
1718
1719 loop_version (loop, comp_rtx, &condition_bb,
1720 prob, prob.invert (),
1721 prob, prob.invert (), true);
1722 }
1723
1724 /* Set new iteration count of loop kernel. */
1725 if (count_reg && count_init)
1726 SET_SRC (single_set (count_init)) = GEN_INT (loop_count
1727 - stage_count + 1);
1728
1729 /* Now apply the scheduled kernel to the RTL of the loop. */
1730 permute_partial_schedule (ps, g->closing_branch->first_note);
1731
1732 /* Mark this loop as software pipelined so the later
1733 scheduling passes don't touch it. */
1734 if (! flag_resched_modulo_sched)
1735 mark_loop_unsched (loop);
1736
1737 /* The life-info is not valid any more. */
1738 df_set_bb_dirty (g->bb);
1739
1740 apply_reg_moves (ps);
1741 if (dump_file)
1742 print_node_sched_params (dump_file, g->num_nodes, ps);
1743 /* Generate prolog and epilog. */
1744 generate_prolog_epilog (ps, loop, count_reg, count_init);
1745 break;
1746 }
1747
1748 free_partial_schedule (ps);
1749 node_sched_param_vec.release ();
1750 free (node_order);
1751 free_ddg (g);
1752 }
1753
1754 free (g_arr);
1755
1756 /* Release scheduler data, needed until now because of DFA. */
1757 haifa_sched_finish ();
1758 loop_optimizer_finalize ();
1759}
1760
1761/* The SMS scheduling algorithm itself
1762 -----------------------------------
1763 Input: 'O' an ordered list of insns of a loop.
1764 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1765
1766 'Q' is the empty Set
1767 'PS' is the partial schedule; it holds the currently scheduled nodes with
1768 their cycle/slot.
1769 'PSP' previously scheduled predecessors.
1770 'PSS' previously scheduled successors.
1771 't(u)' the cycle where u is scheduled.
1772 'l(u)' is the latency of u.
1773 'd(v,u)' is the dependence distance from v to u.
1774 'ASAP(u)' the earliest time at which u could be scheduled as computed in
1775 the node ordering phase.
1776 'check_hardware_resources_conflicts(u, PS, c)'
1777 run a trace around cycle/slot through DFA model
1778 to check resource conflicts involving instruction u
1779 at cycle c given the partial schedule PS.
1780 'add_to_partial_schedule_at_time(u, PS, c)'
1781 Add the node/instruction u to the partial schedule
1782 PS at time c.
1783 'calculate_register_pressure(PS)'
1784 Given a schedule of instructions, calculate the register
1785 pressure it implies. One implementation could be the
1786 maximum number of overlapping live ranges.
1787 'maxRP' The maximum allowed register pressure, it is usually derived from the number
1788 registers available in the hardware.
1789
1790 1. II = MII.
1791 2. PS = empty list
1792 3. for each node u in O in pre-computed order
1793 4. if (PSP(u) != Q && PSS(u) == Q) then
1794 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1795 6. start = Early_start; end = Early_start + II - 1; step = 1
1796 11. else if (PSP(u) == Q && PSS(u) != Q) then
1797 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1798 13. start = Late_start; end = Late_start - II + 1; step = -1
1799 14. else if (PSP(u) != Q && PSS(u) != Q) then
1800 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u).
1801 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u).
1802 17. start = Early_start;
1803 18. end = min(Early_start + II - 1 , Late_start);
1804 19. step = 1
1805 20. else "if (PSP(u) == Q && PSS(u) == Q)"
1806 21. start = ASAP(u); end = start + II - 1; step = 1
1807 22. endif
1808
1809 23. success = false
1810 24. for (c = start ; c != end ; c += step)
1811 25. if check_hardware_resources_conflicts(u, PS, c) then
1812 26. add_to_partial_schedule_at_time(u, PS, c)
1813 27. success = true
1814 28. break
1815 29. endif
1816 30. endfor
1817 31. if (success == false) then
1818 32. II = II + 1
1819 33. if (II > maxII) then
1820 34. finish - failed to schedule
1821 35. endif
1822 36. goto 2.
1823 37. endif
1824 38. endfor
1825 39. if (calculate_register_pressure(PS) > maxRP) then
1826 40. goto 32.
1827 41. endif
1828 42. compute epilogue & prologue
1829 43. finish - succeeded to schedule
1830
1831 ??? The algorithm restricts the scheduling window to II cycles.
1832 In rare cases, it may be better to allow windows of II+1 cycles.
1833 The window would then start and end on the same row, but with
1834 different "must precede" and "must follow" requirements. */
1835
1836/* A limit on the number of cycles that resource conflicts can span. ??? Should
1837 be provided by DFA, and be dependent on the type of insn scheduled. Currently
1838 set to 0 to save compile time. */
1839#define DFA_HISTORY SMS_DFA_HISTORY
1840
1841/* A threshold for the number of repeated unsuccessful attempts to insert
1842 an empty row, before we flush the partial schedule and start over. */
1843#define MAX_SPLIT_NUM 10
1844/* Given the partial schedule PS, this function calculates and returns the
1845 cycles in which we can schedule the node with the given index I.
1846 NOTE: Here we do the backtracking in SMS, in some special cases. We have
1847 noticed that there are several cases in which we fail to SMS the loop
1848 because the sched window of a node is empty due to tight data-deps. In
1849 such cases we want to unschedule some of the predecessors/successors
1850 until we get non-empty scheduling window. It returns -1 if the
1851 scheduling window is empty and zero otherwise. */
1852
1853static int
1854get_sched_window (partial_schedule_ptr ps, ddg_node_ptr u_node,
1855 sbitmap sched_nodes, int ii, int *start_p, int *step_p,
1856 int *end_p)
1857{
1858 int start, step, end;
1859 int early_start, late_start;
1860 ddg_edge_ptr e;
1861 auto_sbitmap psp (ps->g->num_nodes);
1862 auto_sbitmap pss (ps->g->num_nodes);
1863 sbitmap u_node_preds = NODE_PREDECESSORS (u_node);
1864 sbitmap u_node_succs = NODE_SUCCESSORS (u_node);
1865 int psp_not_empty;
1866 int pss_not_empty;
1867 int count_preds;
1868 int count_succs;
1869
1870 /* 1. compute sched window for u (start, end, step). */
1871 bitmap_clear (psp);
1872 bitmap_clear (pss);
1873 psp_not_empty = bitmap_and (psp, u_node_preds, sched_nodes);
1874 pss_not_empty = bitmap_and (pss, u_node_succs, sched_nodes);
1875
1876 /* We first compute a forward range (start <= end), then decide whether
1877 to reverse it. */
1878 early_start = INT_MIN;
1879 late_start = INT_MAX;
1880 start = INT_MIN;
1881 end = INT_MAX;
1882 step = 1;
1883
1884 count_preds = 0;
1885 count_succs = 0;
1886
1887 if (dump_file && (psp_not_empty || pss_not_empty))
1888 {
1889 fprintf (dump_file, "\nAnalyzing dependencies for node %d (INSN %d)"
1890 "; ii = %d\n\n", u_node->cuid, INSN_UID (u_node->insn), ii);
1891 fprintf (dump_file, "%11s %11s %11s %11s %5s\n",
1892 "start", "early start", "late start", "end", "time");
1893 fprintf (dump_file, "=========== =========== =========== ==========="
1894 " =====\n");
1895 }
1896 /* Calculate early_start and limit end. Both bounds are inclusive. */
1897 if (psp_not_empty)
1898 for (e = u_node->in; e != 0; e = e->next_in)
1899 {
1900 int v = e->src->cuid;
1901
1902 if (bitmap_bit_p (sched_nodes, v))
1903 {
1904 int p_st = SCHED_TIME (v);
1905 int earliest = p_st + e->latency - (e->distance * ii);
1906 int latest = (e->data_type == MEM_DEP ? p_st + ii - 1 : INT_MAX);
1907
1908 if (dump_file)
1909 {
1910 fprintf (dump_file, "%11s %11d %11s %11d %5d",
1911 "", earliest, "", latest, p_st);
1912 print_ddg_edge (dump_file, e);
1913 fprintf (dump_file, "\n");
1914 }
1915
1916 early_start = MAX (early_start, earliest);
1917 end = MIN (end, latest);
1918
1919 if (e->type == TRUE_DEP && e->data_type == REG_DEP)
1920 count_preds++;
1921 }
1922 }
1923
1924 /* Calculate late_start and limit start. Both bounds are inclusive. */
1925 if (pss_not_empty)
1926 for (e = u_node->out; e != 0; e = e->next_out)
1927 {
1928 int v = e->dest->cuid;
1929
1930 if (bitmap_bit_p (sched_nodes, v))
1931 {
1932 int s_st = SCHED_TIME (v);
1933 int earliest = (e->data_type == MEM_DEP ? s_st - ii + 1 : INT_MIN);
1934 int latest = s_st - e->latency + (e->distance * ii);
1935
1936 if (dump_file)
1937 {
1938 fprintf (dump_file, "%11d %11s %11d %11s %5d",
1939 earliest, "", latest, "", s_st);
1940 print_ddg_edge (dump_file, e);
1941 fprintf (dump_file, "\n");
1942 }
1943
1944 start = MAX (start, earliest);
1945 late_start = MIN (late_start, latest);
1946
1947 if (e->type == TRUE_DEP && e->data_type == REG_DEP)
1948 count_succs++;
1949 }
1950 }
1951
1952 if (dump_file && (psp_not_empty || pss_not_empty))
1953 {
1954 fprintf (dump_file, "----------- ----------- ----------- -----------"
1955 " -----\n");
1956 fprintf (dump_file, "%11d %11d %11d %11d %5s %s\n",
1957 start, early_start, late_start, end, "",
1958 "(max, max, min, min)");
1959 }
1960
1961 /* Get a target scheduling window no bigger than ii. */
1962 if (early_start == INT_MIN && late_start == INT_MAX)
1963 early_start = NODE_ASAP (u_node);
1964 else if (early_start == INT_MIN)
1965 early_start = late_start - (ii - 1);
1966 late_start = MIN (late_start, early_start + (ii - 1));
1967
1968 /* Apply memory dependence limits. */
1969 start = MAX (start, early_start);
1970 end = MIN (end, late_start);
1971
1972 if (dump_file && (psp_not_empty || pss_not_empty))
1973 fprintf (dump_file, "%11s %11d %11d %11s %5s final window\n",
1974 "", start, end, "", "");
1975
1976 /* If there are at least as many successors as predecessors, schedule the
1977 node close to its successors. */
1978 if (pss_not_empty && count_succs >= count_preds)
1979 {
1980 std::swap (start, end);
1981 step = -1;
1982 }
1983
1984 /* Now that we've finalized the window, make END an exclusive rather
1985 than an inclusive bound. */
1986 end += step;
1987
1988 *start_p = start;
1989 *step_p = step;
1990 *end_p = end;
1991
1992 if ((start >= end && step == 1) || (start <= end && step == -1))
1993 {
1994 if (dump_file)
1995 fprintf (dump_file, "\nEmpty window: start=%d, end=%d, step=%d\n",
1996 start, end, step);
1997 return -1;
1998 }
1999
2000 return 0;
2001}
2002
2003/* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
2004 node currently been scheduled. At the end of the calculation
2005 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
2006 U_NODE which are (1) already scheduled in the first/last row of
2007 U_NODE's scheduling window, (2) whose dependence inequality with U
2008 becomes an equality when U is scheduled in this same row, and (3)
2009 whose dependence latency is zero.
2010
2011 The first and last rows are calculated using the following parameters:
2012 START/END rows - The cycles that begins/ends the traversal on the window;
2013 searching for an empty cycle to schedule U_NODE.
2014 STEP - The direction in which we traverse the window.
2015 II - The initiation interval. */
2016
2017static void
2018calculate_must_precede_follow (ddg_node_ptr u_node, int start, int end,
2019 int step, int ii, sbitmap sched_nodes,
2020 sbitmap must_precede, sbitmap must_follow)
2021{
2022 ddg_edge_ptr e;
2023 int first_cycle_in_window, last_cycle_in_window;
2024
2025 gcc_assert (must_precede && must_follow);
2026
2027 /* Consider the following scheduling window:
2028 {first_cycle_in_window, first_cycle_in_window+1, ...,
2029 last_cycle_in_window}. If step is 1 then the following will be
2030 the order we traverse the window: {start=first_cycle_in_window,
2031 first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
2032 or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
2033 end=first_cycle_in_window-1} if step is -1. */
2034 first_cycle_in_window = (step == 1) ? start : end - step;
2035 last_cycle_in_window = (step == 1) ? end - step : start;
2036
2037 bitmap_clear (must_precede);
2038 bitmap_clear (must_follow);
2039
2040 if (dump_file)
2041 fprintf (dump_file, "\nmust_precede: ");
2042
2043 /* Instead of checking if:
2044 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
2045 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
2046 first_cycle_in_window)
2047 && e->latency == 0
2048 we use the fact that latency is non-negative:
2049 SCHED_TIME (e->src) - (e->distance * ii) <=
2050 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
2051 first_cycle_in_window
2052 and check only if
2053 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
2054 for (e = u_node->in; e != 0; e = e->next_in)
2055 if (bitmap_bit_p (sched_nodes, e->src->cuid)
2056 && ((SCHED_TIME (e->src->cuid) - (e->distance * ii)) ==
2057 first_cycle_in_window))
2058 {
2059 if (dump_file)
2060 fprintf (dump_file, "%d ", e->src->cuid);
2061
2062 bitmap_set_bit (must_precede, e->src->cuid);
2063 }
2064
2065 if (dump_file)
2066 fprintf (dump_file, "\nmust_follow: ");
2067
2068 /* Instead of checking if:
2069 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
2070 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
2071 last_cycle_in_window)
2072 && e->latency == 0
2073 we use the fact that latency is non-negative:
2074 SCHED_TIME (e->dest) + (e->distance * ii) >=
2075 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
2076 last_cycle_in_window
2077 and check only if
2078 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
2079 for (e = u_node->out; e != 0; e = e->next_out)
2080 if (bitmap_bit_p (sched_nodes, e->dest->cuid)
2081 && ((SCHED_TIME (e->dest->cuid) + (e->distance * ii)) ==
2082 last_cycle_in_window))
2083 {
2084 if (dump_file)
2085 fprintf (dump_file, "%d ", e->dest->cuid);
2086
2087 bitmap_set_bit (must_follow, e->dest->cuid);
2088 }
2089
2090 if (dump_file)
2091 fprintf (dump_file, "\n");
2092}
2093
2094/* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
2095 parameters to decide if that's possible:
2096 PS - The partial schedule.
2097 U - The serial number of U_NODE.
2098 NUM_SPLITS - The number of row splits made so far.
2099 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
2100 the first row of the scheduling window)
2101 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
2102 last row of the scheduling window) */
2103
2104static bool
2105try_scheduling_node_in_cycle (partial_schedule_ptr ps,
2106 int u, int cycle, sbitmap sched_nodes,
2107 int *num_splits, sbitmap must_precede,
2108 sbitmap must_follow)
2109{
2110 ps_insn_ptr psi;
2111 bool success = 0;
2112
2113 verify_partial_schedule (ps, sched_nodes);
2114 psi = ps_add_node_check_conflicts (ps, u, cycle, must_precede, must_follow);
2115 if (psi)
2116 {
2117 SCHED_TIME (u) = cycle;
2118 bitmap_set_bit (sched_nodes, u);
2119 success = 1;
2120 *num_splits = 0;
2121 if (dump_file)
2122 fprintf (dump_file, "Scheduled w/o split in %d\n", cycle);
2123
2124 }
2125
2126 return success;
2127}
2128
2129/* This function implements the scheduling algorithm for SMS according to the
2130 above algorithm. */
2131static partial_schedule_ptr
2132sms_schedule_by_order (ddg_ptr g, int mii, int maxii, int *nodes_order)
2133{
2134 int ii = mii;
2135 int i, c, success, num_splits = 0;
2136 int flush_and_start_over = true;
2137 int num_nodes = g->num_nodes;
2138 int start, end, step; /* Place together into one struct? */
2139 auto_sbitmap sched_nodes (num_nodes);
2140 auto_sbitmap must_precede (num_nodes);
2141 auto_sbitmap must_follow (num_nodes);
2142 auto_sbitmap tobe_scheduled (num_nodes);
2143
2144 partial_schedule_ptr ps = create_partial_schedule (ii, g, DFA_HISTORY);
2145
2146 bitmap_ones (tobe_scheduled);
2147 bitmap_clear (sched_nodes);
2148
2149 while (flush_and_start_over && (ii < maxii))
2150 {
2151
2152 if (dump_file)
2153 fprintf (dump_file, "Starting with ii=%d\n", ii);
2154 flush_and_start_over = false;
2155 bitmap_clear (sched_nodes);
2156
2157 for (i = 0; i < num_nodes; i++)
2158 {
2159 int u = nodes_order[i];
2160 ddg_node_ptr u_node = &ps->g->nodes[u];
2161 rtx_insn *insn = u_node->insn;
2162
2163 if (!NONDEBUG_INSN_P (insn))
2164 {
2165 bitmap_clear_bit (tobe_scheduled, u);
2166 continue;
2167 }
2168
2169 if (bitmap_bit_p (sched_nodes, u))
2170 continue;
2171
2172 /* Try to get non-empty scheduling window. */
2173 success = 0;
2174 if (get_sched_window (ps, u_node, sched_nodes, ii, &start,
2175 &step, &end) == 0)
2176 {
2177 if (dump_file)
2178 fprintf (dump_file, "\nTrying to schedule node %d "
2179 "INSN = %d in (%d .. %d) step %d\n", u, (INSN_UID
2180 (g->nodes[u].insn)), start, end, step);
2181
2182 gcc_assert ((step > 0 && start < end)
2183 || (step < 0 && start > end));
2184
2185 calculate_must_precede_follow (u_node, start, end, step, ii,
2186 sched_nodes, must_precede,
2187 must_follow);
2188
2189 for (c = start; c != end; c += step)
2190 {
2191 sbitmap tmp_precede, tmp_follow;
2192
2193 set_must_precede_follow (&tmp_follow, must_follow,
2194 &tmp_precede, must_precede,
2195 c, start, end, step);
2196 success =
2197 try_scheduling_node_in_cycle (ps, u, c,
2198 sched_nodes,
2199 &num_splits, tmp_precede,
2200 tmp_follow);
2201 if (success)
2202 break;
2203 }
2204
2205 verify_partial_schedule (ps, sched_nodes);
2206 }
2207 if (!success)
2208 {
2209 int split_row;
2210
2211 if (ii++ == maxii)
2212 break;
2213
2214 if (num_splits >= MAX_SPLIT_NUM)
2215 {
2216 num_splits = 0;
2217 flush_and_start_over = true;
2218 verify_partial_schedule (ps, sched_nodes);
2219 reset_partial_schedule (ps, ii);
2220 verify_partial_schedule (ps, sched_nodes);
2221 break;
2222 }
2223
2224 num_splits++;
2225 /* The scheduling window is exclusive of 'end'
2226 whereas compute_split_window() expects an inclusive,
2227 ordered range. */
2228 if (step == 1)
2229 split_row = compute_split_row (sched_nodes, start, end - 1,
2230 ps->ii, u_node);
2231 else
2232 split_row = compute_split_row (sched_nodes, end + 1, start,
2233 ps->ii, u_node);
2234
2235 ps_insert_empty_row (ps, split_row, sched_nodes);
2236 i--; /* Go back and retry node i. */
2237
2238 if (dump_file)
2239 fprintf (dump_file, "num_splits=%d\n", num_splits);
2240 }
2241
2242 /* ??? If (success), check register pressure estimates. */
2243 } /* Continue with next node. */
2244 } /* While flush_and_start_over. */
2245 if (ii >= maxii)
2246 {
2247 free_partial_schedule (ps);
2248 ps = NULL;
2249 }
2250 else
2251 gcc_assert (bitmap_equal_p (tobe_scheduled, sched_nodes));
2252
2253 return ps;
2254}
2255
2256/* This function inserts a new empty row into PS at the position
2257 according to SPLITROW, keeping all already scheduled instructions
2258 intact and updating their SCHED_TIME and cycle accordingly. */
2259static void
2260ps_insert_empty_row (partial_schedule_ptr ps, int split_row,
2261 sbitmap sched_nodes)
2262{
2263 ps_insn_ptr crr_insn;
2264 ps_insn_ptr *rows_new;
2265 int ii = ps->ii;
2266 int new_ii = ii + 1;
2267 int row;
2268 int *rows_length_new;
2269
2270 verify_partial_schedule (ps, sched_nodes);
2271
2272 /* We normalize sched_time and rotate ps to have only non-negative sched
2273 times, for simplicity of updating cycles after inserting new row. */
2274 split_row -= ps->min_cycle;
2275 split_row = SMODULO (split_row, ii);
2276 if (dump_file)
2277 fprintf (dump_file, "split_row=%d\n", split_row);
2278
2279 reset_sched_times (ps, PS_MIN_CYCLE (ps));
2280 rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
2281
2282 rows_new = (ps_insn_ptr *) xcalloc (new_ii, sizeof (ps_insn_ptr));
2283 rows_length_new = (int *) xcalloc (new_ii, sizeof (int));
2284 for (row = 0; row < split_row; row++)
2285 {
2286 rows_new[row] = ps->rows[row];
2287 rows_length_new[row] = ps->rows_length[row];
2288 ps->rows[row] = NULL;
2289 for (crr_insn = rows_new[row];
2290 crr_insn; crr_insn = crr_insn->next_in_row)
2291 {
2292 int u = crr_insn->id;
2293 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii);
2294
2295 SCHED_TIME (u) = new_time;
2296 crr_insn->cycle = new_time;
2297 SCHED_ROW (u) = new_time % new_ii;
2298 SCHED_STAGE (u) = new_time / new_ii;
2299 }
2300
2301 }
2302
2303 rows_new[split_row] = NULL;
2304
2305 for (row = split_row; row < ii; row++)
2306 {
2307 rows_new[row + 1] = ps->rows[row];
2308 rows_length_new[row + 1] = ps->rows_length[row];
2309 ps->rows[row] = NULL;
2310 for (crr_insn = rows_new[row + 1];
2311 crr_insn; crr_insn = crr_insn->next_in_row)
2312 {
2313 int u = crr_insn->id;
2314 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii) + 1;
2315
2316 SCHED_TIME (u) = new_time;
2317 crr_insn->cycle = new_time;
2318 SCHED_ROW (u) = new_time % new_ii;
2319 SCHED_STAGE (u) = new_time / new_ii;
2320 }
2321 }
2322
2323 /* Updating ps. */
2324 ps->min_cycle = ps->min_cycle + ps->min_cycle / ii
2325 + (SMODULO (ps->min_cycle, ii) >= split_row ? 1 : 0);
2326 ps->max_cycle = ps->max_cycle + ps->max_cycle / ii
2327 + (SMODULO (ps->max_cycle, ii) >= split_row ? 1 : 0);
2328 free (ps->rows);
2329 ps->rows = rows_new;
2330 free (ps->rows_length);
2331 ps->rows_length = rows_length_new;
2332 ps->ii = new_ii;
2333 gcc_assert (ps->min_cycle >= 0);
2334
2335 verify_partial_schedule (ps, sched_nodes);
2336
2337 if (dump_file)
2338 fprintf (dump_file, "min_cycle=%d, max_cycle=%d\n", ps->min_cycle,
2339 ps->max_cycle);
2340}
2341
2342/* Given U_NODE which is the node that failed to be scheduled; LOW and
2343 UP which are the boundaries of it's scheduling window; compute using
2344 SCHED_NODES and II a row in the partial schedule that can be split
2345 which will separate a critical predecessor from a critical successor
2346 thereby expanding the window, and return it. */
2347static int
2348compute_split_row (sbitmap sched_nodes, int low, int up, int ii,
2349 ddg_node_ptr u_node)
2350{
2351 ddg_edge_ptr e;
2352 int lower = INT_MIN, upper = INT_MAX;
2353 int crit_pred = -1;
2354 int crit_succ = -1;
2355 int crit_cycle;
2356
2357 for (e = u_node->in; e != 0; e = e->next_in)
2358 {
2359 int v = e->src->cuid;
2360
2361 if (bitmap_bit_p (sched_nodes, v)
2362 && (low == SCHED_TIME (v) + e->latency - (e->distance * ii)))
2363 if (SCHED_TIME (v) > lower)
2364 {
2365 crit_pred = v;
2366 lower = SCHED_TIME (v);
2367 }
2368 }
2369
2370 if (crit_pred >= 0)
2371 {
2372 crit_cycle = SCHED_TIME (crit_pred) + 1;
2373 return SMODULO (crit_cycle, ii);
2374 }
2375
2376 for (e = u_node->out; e != 0; e = e->next_out)
2377 {
2378 int v = e->dest->cuid;
2379
2380 if (bitmap_bit_p (sched_nodes, v)
2381 && (up == SCHED_TIME (v) - e->latency + (e->distance * ii)))
2382 if (SCHED_TIME (v) < upper)
2383 {
2384 crit_succ = v;
2385 upper = SCHED_TIME (v);
2386 }
2387 }
2388
2389 if (crit_succ >= 0)
2390 {
2391 crit_cycle = SCHED_TIME (crit_succ);
2392 return SMODULO (crit_cycle, ii);
2393 }
2394
2395 if (dump_file)
2396 fprintf (dump_file, "Both crit_pred and crit_succ are NULL\n");
2397
2398 return SMODULO ((low + up + 1) / 2, ii);
2399}
2400
2401static void
2402verify_partial_schedule (partial_schedule_ptr ps, sbitmap sched_nodes)
2403{
2404 int row;
2405 ps_insn_ptr crr_insn;
2406
2407 for (row = 0; row < ps->ii; row++)
2408 {
2409 int length = 0;
2410
2411 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
2412 {
2413 int u = crr_insn->id;
2414
2415 length++;
2416 gcc_assert (bitmap_bit_p (sched_nodes, u));
2417 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
2418 popcount (sched_nodes) == number of insns in ps. */
2419 gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
2420 gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
2421 }
2422
2423 gcc_assert (ps->rows_length[row] == length);
2424 }
2425}
2426
2427
2428/* This page implements the algorithm for ordering the nodes of a DDG
2429 for modulo scheduling, activated through the
2430 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */
2431
2432#define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
2433#define ASAP(x) (ORDER_PARAMS ((x))->asap)
2434#define ALAP(x) (ORDER_PARAMS ((x))->alap)
2435#define HEIGHT(x) (ORDER_PARAMS ((x))->height)
2436#define MOB(x) (ALAP ((x)) - ASAP ((x)))
2437#define DEPTH(x) (ASAP ((x)))
2438
2439typedef struct node_order_params * nopa;
2440
2441static void order_nodes_of_sccs (ddg_all_sccs_ptr, int * result);
2442static int order_nodes_in_scc (ddg_ptr, sbitmap, sbitmap, int*, int);
2443static nopa calculate_order_params (ddg_ptr, int, int *);
2444static int find_max_asap (ddg_ptr, sbitmap);
2445static int find_max_hv_min_mob (ddg_ptr, sbitmap);
2446static int find_max_dv_min_mob (ddg_ptr, sbitmap);
2447
2448enum sms_direction {BOTTOMUP, TOPDOWN};
2449
2450struct node_order_params
2451{
2452 int asap;
2453 int alap;
2454 int height;
2455};
2456
2457/* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */
2458static void
2459check_nodes_order (int *node_order, int num_nodes)
2460{
2461 int i;
2462 auto_sbitmap tmp (num_nodes);
2463
2464 bitmap_clear (tmp);
2465
2466 if (dump_file)
2467 fprintf (dump_file, "SMS final nodes order: \n");
2468
2469 for (i = 0; i < num_nodes; i++)
2470 {
2471 int u = node_order[i];
2472
2473 if (dump_file)
2474 fprintf (dump_file, "%d ", u);
2475 gcc_assert (u < num_nodes && u >= 0 && !bitmap_bit_p (tmp, u));
2476
2477 bitmap_set_bit (tmp, u);
2478 }
2479
2480 if (dump_file)
2481 fprintf (dump_file, "\n");
2482}
2483
2484/* Order the nodes of G for scheduling and pass the result in
2485 NODE_ORDER. Also set aux.count of each node to ASAP.
2486 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
2487static int
2488sms_order_nodes (ddg_ptr g, int mii, int * node_order, int *pmax_asap)
2489{
2490 int i;
2491 int rec_mii = 0;
2492 ddg_all_sccs_ptr sccs = create_ddg_all_sccs (g);
2493
2494 nopa nops = calculate_order_params (g, mii, pmax_asap);
2495
2496 if (dump_file)
2497 print_sccs (dump_file, sccs, g);
2498
2499 order_nodes_of_sccs (sccs, node_order);
2500
2501 if (sccs->num_sccs > 0)
2502 /* First SCC has the largest recurrence_length. */
2503 rec_mii = sccs->sccs[0]->recurrence_length;
2504
2505 /* Save ASAP before destroying node_order_params. */
2506 for (i = 0; i < g->num_nodes; i++)
2507 {
2508 ddg_node_ptr v = &g->nodes[i];
2509 v->aux.count = ASAP (v);
2510 }
2511
2512 free (nops);
2513 free_ddg_all_sccs (sccs);
2514 check_nodes_order (node_order, g->num_nodes);
2515
2516 return rec_mii;
2517}
2518
2519static void
2520order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs, int * node_order)
2521{
2522 int i, pos = 0;
2523 ddg_ptr g = all_sccs->ddg;
2524 int num_nodes = g->num_nodes;
2525 auto_sbitmap prev_sccs (num_nodes);
2526 auto_sbitmap on_path (num_nodes);
2527 auto_sbitmap tmp (num_nodes);
2528 auto_sbitmap ones (num_nodes);
2529
2530 bitmap_clear (prev_sccs);
2531 bitmap_ones (ones);
2532
2533 /* Perform the node ordering starting from the SCC with the highest recMII.
2534 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
2535 for (i = 0; i < all_sccs->num_sccs; i++)
2536 {
2537 ddg_scc_ptr scc = all_sccs->sccs[i];
2538
2539 /* Add nodes on paths from previous SCCs to the current SCC. */
2540 find_nodes_on_paths (on_path, g, prev_sccs, scc->nodes);
2541 bitmap_ior (tmp, scc->nodes, on_path);
2542
2543 /* Add nodes on paths from the current SCC to previous SCCs. */
2544 find_nodes_on_paths (on_path, g, scc->nodes, prev_sccs);
2545 bitmap_ior (tmp, tmp, on_path);
2546
2547 /* Remove nodes of previous SCCs from current extended SCC. */
2548 bitmap_and_compl (tmp, tmp, prev_sccs);
2549
2550 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
2551 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */
2552 }
2553
2554 /* Handle the remaining nodes that do not belong to any scc. Each call
2555 to order_nodes_in_scc handles a single connected component. */
2556 while (pos < g->num_nodes)
2557 {
2558 bitmap_and_compl (tmp, ones, prev_sccs);
2559 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
2560 }
2561}
2562
2563/* MII is needed if we consider backarcs (that do not close recursive cycles). */
2564static struct node_order_params *
2565calculate_order_params (ddg_ptr g, int mii ATTRIBUTE_UNUSED, int *pmax_asap)
2566{
2567 int u;
2568 int max_asap;
2569 int num_nodes = g->num_nodes;
2570 ddg_edge_ptr e;
2571 /* Allocate a place to hold ordering params for each node in the DDG. */
2572 nopa node_order_params_arr;
2573
2574 /* Initialize of ASAP/ALAP/HEIGHT to zero. */
2575 node_order_params_arr = (nopa) xcalloc (num_nodes,
2576 sizeof (struct node_order_params));
2577
2578 /* Set the aux pointer of each node to point to its order_params structure. */
2579 for (u = 0; u < num_nodes; u++)
2580 g->nodes[u].aux.info = &node_order_params_arr[u];
2581
2582 /* Disregarding a backarc from each recursive cycle to obtain a DAG,
2583 calculate ASAP, ALAP, mobility, distance, and height for each node
2584 in the dependence (direct acyclic) graph. */
2585
2586 /* We assume that the nodes in the array are in topological order. */
2587
2588 max_asap = 0;
2589 for (u = 0; u < num_nodes; u++)
2590 {
2591 ddg_node_ptr u_node = &g->nodes[u];
2592
2593 ASAP (u_node) = 0;
2594 for (e = u_node->in; e; e = e->next_in)
2595 if (e->distance == 0)
2596 ASAP (u_node) = MAX (ASAP (u_node),
2597 ASAP (e->src) + e->latency);
2598 max_asap = MAX (max_asap, ASAP (u_node));
2599 }
2600
2601 for (u = num_nodes - 1; u > -1; u--)
2602 {
2603 ddg_node_ptr u_node = &g->nodes[u];
2604
2605 ALAP (u_node) = max_asap;
2606 HEIGHT (u_node) = 0;
2607 for (e = u_node->out; e; e = e->next_out)
2608 if (e->distance == 0)
2609 {
2610 ALAP (u_node) = MIN (ALAP (u_node),
2611 ALAP (e->dest) - e->latency);
2612 HEIGHT (u_node) = MAX (HEIGHT (u_node),
2613 HEIGHT (e->dest) + e->latency);
2614 }
2615 }
2616 if (dump_file)
2617 {
2618 fprintf (dump_file, "\nOrder params\n");
2619 for (u = 0; u < num_nodes; u++)
2620 {
2621 ddg_node_ptr u_node = &g->nodes[u];
2622
2623 fprintf (dump_file, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u,
2624 ASAP (u_node), ALAP (u_node), HEIGHT (u_node));
2625 }
2626 }
2627
2628 *pmax_asap = max_asap;
2629 return node_order_params_arr;
2630}
2631
2632static int
2633find_max_asap (ddg_ptr g, sbitmap nodes)
2634{
2635 unsigned int u = 0;
2636 int max_asap = -1;
2637 int result = -1;
2638 sbitmap_iterator sbi;
2639
2640 EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi)
2641 {
2642 ddg_node_ptr u_node = &g->nodes[u];
2643
2644 if (max_asap < ASAP (u_node))
2645 {
2646 max_asap = ASAP (u_node);
2647 result = u;
2648 }
2649 }
2650 return result;
2651}
2652
2653static int
2654find_max_hv_min_mob (ddg_ptr g, sbitmap nodes)
2655{
2656 unsigned int u = 0;
2657 int max_hv = -1;
2658 int min_mob = INT_MAX;
2659 int result = -1;
2660 sbitmap_iterator sbi;
2661
2662 EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi)
2663 {
2664 ddg_node_ptr u_node = &g->nodes[u];
2665
2666 if (max_hv < HEIGHT (u_node))
2667 {
2668 max_hv = HEIGHT (u_node);
2669 min_mob = MOB (u_node);
2670 result = u;
2671 }
2672 else if ((max_hv == HEIGHT (u_node))
2673 && (min_mob > MOB (u_node)))
2674 {
2675 min_mob = MOB (u_node);
2676 result = u;
2677 }
2678 }
2679 return result;
2680}
2681
2682static int
2683find_max_dv_min_mob (ddg_ptr g, sbitmap nodes)
2684{
2685 unsigned int u = 0;
2686 int max_dv = -1;
2687 int min_mob = INT_MAX;
2688 int result = -1;
2689 sbitmap_iterator sbi;
2690
2691 EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi)
2692 {
2693 ddg_node_ptr u_node = &g->nodes[u];
2694
2695 if (max_dv < DEPTH (u_node))
2696 {
2697 max_dv = DEPTH (u_node);
2698 min_mob = MOB (u_node);
2699 result = u;
2700 }
2701 else if ((max_dv == DEPTH (u_node))
2702 && (min_mob > MOB (u_node)))
2703 {
2704 min_mob = MOB (u_node);
2705 result = u;
2706 }
2707 }
2708 return result;
2709}
2710
2711/* Places the nodes of SCC into the NODE_ORDER array starting
2712 at position POS, according to the SMS ordering algorithm.
2713 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
2714 the NODE_ORDER array, starting from position zero. */
2715static int
2716order_nodes_in_scc (ddg_ptr g, sbitmap nodes_ordered, sbitmap scc,
2717 int * node_order, int pos)
2718{
2719 enum sms_direction dir;
2720 int num_nodes = g->num_nodes;
2721 auto_sbitmap workset (num_nodes);
2722 auto_sbitmap tmp (num_nodes);
2723 sbitmap zero_bitmap = sbitmap_alloc (num_nodes);
2724 auto_sbitmap predecessors (num_nodes);
2725 auto_sbitmap successors (num_nodes);
2726
2727 bitmap_clear (predecessors);
2728 find_predecessors (predecessors, g, nodes_ordered);
2729
2730 bitmap_clear (successors);
2731 find_successors (successors, g, nodes_ordered);
2732
2733 bitmap_clear (tmp);
2734 if (bitmap_and (tmp, predecessors, scc))
2735 {
2736 bitmap_copy (workset, tmp);
2737 dir = BOTTOMUP;
2738 }
2739 else if (bitmap_and (tmp, successors, scc))
2740 {
2741 bitmap_copy (workset, tmp);
2742 dir = TOPDOWN;
2743 }
2744 else
2745 {
2746 int u;
2747
2748 bitmap_clear (workset);
2749 if ((u = find_max_asap (g, scc)) >= 0)
2750 bitmap_set_bit (workset, u);
2751 dir = BOTTOMUP;
2752 }
2753
2754 bitmap_clear (zero_bitmap);
2755 while (!bitmap_equal_p (workset, zero_bitmap))
2756 {
2757 int v;
2758 ddg_node_ptr v_node;
2759 sbitmap v_node_preds;
2760 sbitmap v_node_succs;
2761
2762 if (dir == TOPDOWN)
2763 {
2764 while (!bitmap_equal_p (workset, zero_bitmap))
2765 {
2766 v = find_max_hv_min_mob (g, workset);
2767 v_node = &g->nodes[v];
2768 node_order[pos++] = v;
2769 v_node_succs = NODE_SUCCESSORS (v_node);
2770 bitmap_and (tmp, v_node_succs, scc);
2771
2772 /* Don't consider the already ordered successors again. */
2773 bitmap_and_compl (tmp, tmp, nodes_ordered);
2774 bitmap_ior (workset, workset, tmp);
2775 bitmap_clear_bit (workset, v);
2776 bitmap_set_bit (nodes_ordered, v);
2777 }
2778 dir = BOTTOMUP;
2779 bitmap_clear (predecessors);
2780 find_predecessors (predecessors, g, nodes_ordered);
2781 bitmap_and (workset, predecessors, scc);
2782 }
2783 else
2784 {
2785 while (!bitmap_equal_p (workset, zero_bitmap))
2786 {
2787 v = find_max_dv_min_mob (g, workset);
2788 v_node = &g->nodes[v];
2789 node_order[pos++] = v;
2790 v_node_preds = NODE_PREDECESSORS (v_node);
2791 bitmap_and (tmp, v_node_preds, scc);
2792
2793 /* Don't consider the already ordered predecessors again. */
2794 bitmap_and_compl (tmp, tmp, nodes_ordered);
2795 bitmap_ior (workset, workset, tmp);
2796 bitmap_clear_bit (workset, v);
2797 bitmap_set_bit (nodes_ordered, v);
2798 }
2799 dir = TOPDOWN;
2800 bitmap_clear (successors);
2801 find_successors (successors, g, nodes_ordered);
2802 bitmap_and (workset, successors, scc);
2803 }
2804 }
2805 sbitmap_free (zero_bitmap);
2806 return pos;
2807}
2808
2809
2810/* This page contains functions for manipulating partial-schedules during
2811 modulo scheduling. */
2812
2813/* Create a partial schedule and allocate a memory to hold II rows. */
2814
2815static partial_schedule_ptr
2816create_partial_schedule (int ii, ddg_ptr g, int history)
2817{
2818 partial_schedule_ptr ps = XNEW (struct partial_schedule);
2819 ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
2820 ps->rows_length = (int *) xcalloc (ii, sizeof (int));
2821 ps->reg_moves.create (0);
2822 ps->ii = ii;
2823 ps->history = history;
2824 ps->min_cycle = INT_MAX;
2825 ps->max_cycle = INT_MIN;
2826 ps->g = g;
2827
2828 return ps;
2829}
2830
2831/* Free the PS_INSNs in rows array of the given partial schedule.
2832 ??? Consider caching the PS_INSN's. */
2833static void
2834free_ps_insns (partial_schedule_ptr ps)
2835{
2836 int i;
2837
2838 for (i = 0; i < ps->ii; i++)
2839 {
2840 while (ps->rows[i])
2841 {
2842 ps_insn_ptr ps_insn = ps->rows[i]->next_in_row;
2843
2844 free (ps->rows[i]);
2845 ps->rows[i] = ps_insn;
2846 }
2847 ps->rows[i] = NULL;
2848 }
2849}
2850
2851/* Free all the memory allocated to the partial schedule. */
2852
2853static void
2854free_partial_schedule (partial_schedule_ptr ps)
2855{
2856 ps_reg_move_info *move;
2857 unsigned int i;
2858
2859 if (!ps)
2860 return;
2861
2862 FOR_EACH_VEC_ELT (ps->reg_moves, i, move)
2863 sbitmap_free (move->uses);
2864 ps->reg_moves.release ();
2865
2866 free_ps_insns (ps);
2867 free (ps->rows);
2868 free (ps->rows_length);
2869 free (ps);
2870}
2871
2872/* Clear the rows array with its PS_INSNs, and create a new one with
2873 NEW_II rows. */
2874
2875static void
2876reset_partial_schedule (partial_schedule_ptr ps, int new_ii)
2877{
2878 if (!ps)
2879 return;
2880 free_ps_insns (ps);
2881 if (new_ii == ps->ii)
2882 return;
2883 ps->rows = (ps_insn_ptr *) xrealloc (ps->rows, new_ii
2884 * sizeof (ps_insn_ptr));
2885 memset (ps->rows, 0, new_ii * sizeof (ps_insn_ptr));
2886 ps->rows_length = (int *) xrealloc (ps->rows_length, new_ii * sizeof (int));
2887 memset (ps->rows_length, 0, new_ii * sizeof (int));
2888 ps->ii = new_ii;
2889 ps->min_cycle = INT_MAX;
2890 ps->max_cycle = INT_MIN;
2891}
2892
2893/* Prints the partial schedule as an ii rows array, for each rows
2894 print the ids of the insns in it. */
2895void
2896print_partial_schedule (partial_schedule_ptr ps, FILE *dump)
2897{
2898 int i;
2899
2900 for (i = 0; i < ps->ii; i++)
2901 {
2902 ps_insn_ptr ps_i = ps->rows[i];
2903
2904 fprintf (dump, "\n[ROW %d ]: ", i);
2905 while (ps_i)
2906 {
2907 rtx_insn *insn = ps_rtl_insn (ps, ps_i->id);
2908
2909 if (JUMP_P (insn))
2910 fprintf (dump, "%d (branch), ", INSN_UID (insn));
2911 else
2912 fprintf (dump, "%d, ", INSN_UID (insn));
2913
2914 ps_i = ps_i->next_in_row;
2915 }
2916 }
2917}
2918
2919/* Creates an object of PS_INSN and initializes it to the given parameters. */
2920static ps_insn_ptr
2921create_ps_insn (int id, int cycle)
2922{
2923 ps_insn_ptr ps_i = XNEW (struct ps_insn);
2924
2925 ps_i->id = id;
2926 ps_i->next_in_row = NULL;
2927 ps_i->prev_in_row = NULL;
2928 ps_i->cycle = cycle;
2929
2930 return ps_i;
2931}
2932
2933
2934/* Removes the given PS_INSN from the partial schedule. */
2935static void
2936remove_node_from_ps (partial_schedule_ptr ps, ps_insn_ptr ps_i)
2937{
2938 int row;
2939
2940 gcc_assert (ps && ps_i);
2941
2942 row = SMODULO (ps_i->cycle, ps->ii);
2943 if (! ps_i->prev_in_row)
2944 {
2945 gcc_assert (ps_i == ps->rows[row]);
2946 ps->rows[row] = ps_i->next_in_row;
2947 if (ps->rows[row])
2948 ps->rows[row]->prev_in_row = NULL;
2949 }
2950 else
2951 {
2952 ps_i->prev_in_row->next_in_row = ps_i->next_in_row;
2953 if (ps_i->next_in_row)
2954 ps_i->next_in_row->prev_in_row = ps_i->prev_in_row;
2955 }
2956
2957 ps->rows_length[row] -= 1;
2958 free (ps_i);
2959 return;
2960}
2961
2962/* Unlike what literature describes for modulo scheduling (which focuses
2963 on VLIW machines) the order of the instructions inside a cycle is
2964 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
2965 where the current instruction should go relative to the already
2966 scheduled instructions in the given cycle. Go over these
2967 instructions and find the first possible column to put it in. */
2968static bool
2969ps_insn_find_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
2970 sbitmap must_precede, sbitmap must_follow)
2971{
2972 ps_insn_ptr next_ps_i;
2973 ps_insn_ptr first_must_follow = NULL;
2974 ps_insn_ptr last_must_precede = NULL;
2975 ps_insn_ptr last_in_row = NULL;
2976 int row;
2977
2978 if (! ps_i)
2979 return false;
2980
2981 row = SMODULO (ps_i->cycle, ps->ii);
2982
2983 /* Find the first must follow and the last must precede
2984 and insert the node immediately after the must precede
2985 but make sure that it there is no must follow after it. */
2986 for (next_ps_i = ps->rows[row];
2987 next_ps_i;
2988 next_ps_i = next_ps_i->next_in_row)
2989 {
2990 if (must_follow
2991 && bitmap_bit_p (must_follow, next_ps_i->id)
2992 && ! first_must_follow)
2993 first_must_follow = next_ps_i;
2994 if (must_precede && bitmap_bit_p (must_precede, next_ps_i->id))
2995 {
2996 /* If we have already met a node that must follow, then
2997 there is no possible column. */
2998 if (first_must_follow)
2999 return false;
3000 else
3001 last_must_precede = next_ps_i;
3002 }
3003 /* The closing branch must be the last in the row. */
3004 if (must_precede
3005 && bitmap_bit_p (must_precede, next_ps_i->id)
3006 && JUMP_P (ps_rtl_insn (ps, next_ps_i->id)))
3007 return false;
3008
3009 last_in_row = next_ps_i;
3010 }
3011
3012 /* The closing branch is scheduled as well. Make sure there is no
3013 dependent instruction after it as the branch should be the last
3014 instruction in the row. */
3015 if (JUMP_P (ps_rtl_insn (ps, ps_i->id)))
3016 {
3017 if (first_must_follow)
3018 return false;
3019 if (last_in_row)
3020 {
3021 /* Make the branch the last in the row. New instructions
3022 will be inserted at the beginning of the row or after the
3023 last must_precede instruction thus the branch is guaranteed
3024 to remain the last instruction in the row. */
3025 last_in_row->next_in_row = ps_i;
3026 ps_i->prev_in_row = last_in_row;
3027 ps_i->next_in_row = NULL;
3028 }
3029 else
3030 ps->rows[row] = ps_i;
3031 return true;
3032 }
3033
3034 /* Now insert the node after INSERT_AFTER_PSI. */
3035
3036 if (! last_must_precede)
3037 {
3038 ps_i->next_in_row = ps->rows[row];
3039 ps_i->prev_in_row = NULL;
3040 if (ps_i->next_in_row)
3041 ps_i->next_in_row->prev_in_row = ps_i;
3042 ps->rows[row] = ps_i;
3043 }
3044 else
3045 {
3046 ps_i->next_in_row = last_must_precede->next_in_row;
3047 last_must_precede->next_in_row = ps_i;
3048 ps_i->prev_in_row = last_must_precede;
3049 if (ps_i->next_in_row)
3050 ps_i->next_in_row->prev_in_row = ps_i;
3051 }
3052
3053 return true;
3054}
3055
3056/* Advances the PS_INSN one column in its current row; returns false
3057 in failure and true in success. Bit N is set in MUST_FOLLOW if
3058 the node with cuid N must be come after the node pointed to by
3059 PS_I when scheduled in the same cycle. */
3060static int
3061ps_insn_advance_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
3062 sbitmap must_follow)
3063{
3064 ps_insn_ptr prev, next;
3065 int row;
3066
3067 if (!ps || !ps_i)
3068 return false;
3069
3070 row = SMODULO (ps_i->cycle, ps->ii);
3071
3072 if (! ps_i->next_in_row)
3073 return false;
3074
3075 /* Check if next_in_row is dependent on ps_i, both having same sched
3076 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
3077 if (must_follow && bitmap_bit_p (must_follow, ps_i->next_in_row->id))
3078 return false;
3079
3080 /* Advance PS_I over its next_in_row in the doubly linked list. */
3081 prev = ps_i->prev_in_row;
3082 next = ps_i->next_in_row;
3083
3084 if (ps_i == ps->rows[row])
3085 ps->rows[row] = next;
3086
3087 ps_i->next_in_row = next->next_in_row;
3088
3089 if (next->next_in_row)
3090 next->next_in_row->prev_in_row = ps_i;
3091
3092 next->next_in_row = ps_i;
3093 ps_i->prev_in_row = next;
3094
3095 next->prev_in_row = prev;
3096 if (prev)
3097 prev->next_in_row = next;
3098
3099 return true;
3100}
3101
3102/* Inserts a DDG_NODE to the given partial schedule at the given cycle.
3103 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
3104 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
3105 before/after (respectively) the node pointed to by PS_I when scheduled
3106 in the same cycle. */
3107static ps_insn_ptr
3108add_node_to_ps (partial_schedule_ptr ps, int id, int cycle,
3109 sbitmap must_precede, sbitmap must_follow)
3110{
3111 ps_insn_ptr ps_i;
3112 int row = SMODULO (cycle, ps->ii);
3113
3114 if (ps->rows_length[row] >= issue_rate)
3115 return NULL;
3116
3117 ps_i = create_ps_insn (id, cycle);
3118
3119 /* Finds and inserts PS_I according to MUST_FOLLOW and
3120 MUST_PRECEDE. */
3121 if (! ps_insn_find_column (ps, ps_i, must_precede, must_follow))
3122 {
3123 free (ps_i);
3124 return NULL;
3125 }
3126
3127 ps->rows_length[row] += 1;
3128 return ps_i;
3129}
3130
3131/* Advance time one cycle. Assumes DFA is being used. */
3132static void
3133advance_one_cycle (void)
3134{
3135 if (targetm.sched.dfa_pre_cycle_insn)
3136 state_transition (curr_state,
3137 targetm.sched.dfa_pre_cycle_insn ());
3138
3139 state_transition (curr_state, NULL);
3140
3141 if (targetm.sched.dfa_post_cycle_insn)
3142 state_transition (curr_state,
3143 targetm.sched.dfa_post_cycle_insn ());
3144}
3145
3146
3147
3148/* Checks if PS has resource conflicts according to DFA, starting from
3149 FROM cycle to TO cycle; returns true if there are conflicts and false
3150 if there are no conflicts. Assumes DFA is being used. */
3151static int
3152ps_has_conflicts (partial_schedule_ptr ps, int from, int to)
3153{
3154 int cycle;
3155
3156 state_reset (curr_state);
3157
3158 for (cycle = from; cycle <= to; cycle++)
3159 {
3160 ps_insn_ptr crr_insn;
3161 /* Holds the remaining issue slots in the current row. */
3162 int can_issue_more = issue_rate;
3163
3164 /* Walk through the DFA for the current row. */
3165 for (crr_insn = ps->rows[SMODULO (cycle, ps->ii)];
3166 crr_insn;
3167 crr_insn = crr_insn->next_in_row)
3168 {
3169 rtx_insn *insn = ps_rtl_insn (ps, crr_insn->id);
3170
3171 if (!NONDEBUG_INSN_P (insn))
3172 continue;
3173
3174 /* Check if there is room for the current insn. */
3175 if (!can_issue_more || state_dead_lock_p (curr_state))
3176 return true;
3177
3178 /* Update the DFA state and return with failure if the DFA found
3179 resource conflicts. */
3180 if (state_transition (curr_state, insn) >= 0)
3181 return true;
3182
3183 if (targetm.sched.variable_issue)
3184 can_issue_more =
3185 targetm.sched.variable_issue (sched_dump, sched_verbose,
3186 insn, can_issue_more);
3187 /* A naked CLOBBER or USE generates no instruction, so don't
3188 let them consume issue slots. */
3189 else if (GET_CODE (PATTERN (insn)) != USE
3190 && GET_CODE (PATTERN (insn)) != CLOBBER)
3191 can_issue_more--;
3192 }
3193
3194 /* Advance the DFA to the next cycle. */
3195 advance_one_cycle ();
3196 }
3197 return false;
3198}
3199
3200/* Checks if the given node causes resource conflicts when added to PS at
3201 cycle C. If not the node is added to PS and returned; otherwise zero
3202 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
3203 cuid N must be come before/after (respectively) the node pointed to by
3204 PS_I when scheduled in the same cycle. */
3205ps_insn_ptr
3206ps_add_node_check_conflicts (partial_schedule_ptr ps, int n,
3207 int c, sbitmap must_precede,
3208 sbitmap must_follow)
3209{
3210 int has_conflicts = 0;
3211 ps_insn_ptr ps_i;
3212
3213 /* First add the node to the PS, if this succeeds check for
3214 conflicts, trying different issue slots in the same row. */
3215 if (! (ps_i = add_node_to_ps (ps, n, c, must_precede, must_follow)))
3216 return NULL; /* Failed to insert the node at the given cycle. */
3217
3218 has_conflicts = ps_has_conflicts (ps, c, c)
3219 || (ps->history > 0
3220 && ps_has_conflicts (ps,
3221 c - ps->history,
3222 c + ps->history));
3223
3224 /* Try different issue slots to find one that the given node can be
3225 scheduled in without conflicts. */
3226 while (has_conflicts)
3227 {
3228 if (! ps_insn_advance_column (ps, ps_i, must_follow))
3229 break;
3230 has_conflicts = ps_has_conflicts (ps, c, c)
3231 || (ps->history > 0
3232 && ps_has_conflicts (ps,
3233 c - ps->history,
3234 c + ps->history));
3235 }
3236
3237 if (has_conflicts)
3238 {
3239 remove_node_from_ps (ps, ps_i);
3240 return NULL;
3241 }
3242
3243 ps->min_cycle = MIN (ps->min_cycle, c);
3244 ps->max_cycle = MAX (ps->max_cycle, c);
3245 return ps_i;
3246}
3247
3248/* Calculate the stage count of the partial schedule PS. The calculation
3249 takes into account the rotation amount passed in ROTATION_AMOUNT. */
3250int
3251calculate_stage_count (partial_schedule_ptr ps, int rotation_amount)
3252{
3253 int new_min_cycle = PS_MIN_CYCLE (ps) - rotation_amount;
3254 int new_max_cycle = PS_MAX_CYCLE (ps) - rotation_amount;
3255 int stage_count = CALC_STAGE_COUNT (-1, new_min_cycle, ps->ii);
3256
3257 /* The calculation of stage count is done adding the number of stages
3258 before cycle zero and after cycle zero. */
3259 stage_count += CALC_STAGE_COUNT (new_max_cycle, 0, ps->ii);
3260
3261 return stage_count;
3262}
3263
3264/* Rotate the rows of PS such that insns scheduled at time
3265 START_CYCLE will appear in row 0. Updates max/min_cycles. */
3266void
3267rotate_partial_schedule (partial_schedule_ptr ps, int start_cycle)
3268{
3269 int i, row, backward_rotates;
3270 int last_row = ps->ii - 1;
3271
3272 if (start_cycle == 0)
3273 return;
3274
3275 backward_rotates = SMODULO (start_cycle, ps->ii);
3276
3277 /* Revisit later and optimize this into a single loop. */
3278 for (i = 0; i < backward_rotates; i++)
3279 {
3280 ps_insn_ptr first_row = ps->rows[0];
3281 int first_row_length = ps->rows_length[0];
3282
3283 for (row = 0; row < last_row; row++)
3284 {
3285 ps->rows[row] = ps->rows[row + 1];
3286 ps->rows_length[row] = ps->rows_length[row + 1];
3287 }
3288
3289 ps->rows[last_row] = first_row;
3290 ps->rows_length[last_row] = first_row_length;
3291 }
3292
3293 ps->max_cycle -= start_cycle;
3294 ps->min_cycle -= start_cycle;
3295}
3296
3297#endif /* INSN_SCHEDULING */
3298
3299/* Run instruction scheduler. */
3300/* Perform SMS module scheduling. */
3301
3302namespace {
3303
3304const pass_data pass_data_sms =
3305{
3306 RTL_PASS, /* type */
3307 "sms", /* name */
3308 OPTGROUP_NONE, /* optinfo_flags */
3309 TV_SMS, /* tv_id */
3310 0, /* properties_required */
3311 0, /* properties_provided */
3312 0, /* properties_destroyed */
3313 0, /* todo_flags_start */
3314 TODO_df_finish, /* todo_flags_finish */
3315};
3316
3317class pass_sms : public rtl_opt_pass
3318{
3319public:
3320 pass_sms (gcc::context *ctxt)
3321 : rtl_opt_pass (pass_data_sms, ctxt)
3322 {}
3323
3324 /* opt_pass methods: */
3325 virtual bool gate (function *)
3326{
3327 return (optimize > 0 && flag_modulo_sched);
3328}
3329
3330 virtual unsigned int execute (function *);
3331
3332}; // class pass_sms
3333
3334unsigned int
3335pass_sms::execute (function *fun ATTRIBUTE_UNUSED)
3336{
3337#ifdef INSN_SCHEDULING
3338 basic_block bb;
3339
3340 /* Collect loop information to be used in SMS. */
3341 cfg_layout_initialize (0);
3342 sms_schedule ();
3343
3344 /* Update the life information, because we add pseudos. */
3345 max_regno = max_reg_num ();
3346
3347 /* Finalize layout changes. */
3348 FOR_EACH_BB_FN (bb, fun)
3349 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3350 bb->aux = bb->next_bb;
3351 free_dominance_info (CDI_DOMINATORS);
3352 cfg_layout_finalize ();
3353#endif /* INSN_SCHEDULING */
3354 return 0;
3355}
3356
3357} // anon namespace
3358
3359rtl_opt_pass *
3360make_pass_sms (gcc::context *ctxt)
3361{
3362 return new pass_sms (ctxt);
3363}
3364