OSDN Git Service

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