OSDN Git Service

82f3d125668a1cb6092dde9393ade4c7cdd69c49
[pf3gnuchains/gcc-fork.git] / gcc / sched-rgn.c
1 /* Instruction scheduling pass.
2    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5    and currently maintained by, Jim Wilson (wilson@cygnus.com)
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, or (at your option) any later
12 version.
13
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING.  If not, write to the Free
21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 02110-1301, USA.  */
23
24 /* This pass implements list scheduling within basic blocks.  It is
25    run twice: (1) after flow analysis, but before register allocation,
26    and (2) after register allocation.
27
28    The first run performs interblock scheduling, moving insns between
29    different blocks in the same "region", and the second runs only
30    basic block scheduling.
31
32    Interblock motions performed are useful motions and speculative
33    motions, including speculative loads.  Motions requiring code
34    duplication are not supported.  The identification of motion type
35    and the check for validity of speculative motions requires
36    construction and analysis of the function's control flow graph.
37
38    The main entry point for this pass is schedule_insns(), called for
39    each function.  The work of the scheduler is organized in three
40    levels: (1) function level: insns are subject to splitting,
41    control-flow-graph is constructed, regions are computed (after
42    reload, each region is of one block), (2) region level: control
43    flow graph attributes required for interblock scheduling are
44    computed (dominators, reachability, etc.), data dependences and
45    priorities are computed, and (3) block level: insns in the block
46    are actually scheduled.  */
47 \f
48 #include "config.h"
49 #include "system.h"
50 #include "coretypes.h"
51 #include "tm.h"
52 #include "toplev.h"
53 #include "rtl.h"
54 #include "tm_p.h"
55 #include "hard-reg-set.h"
56 #include "regs.h"
57 #include "function.h"
58 #include "flags.h"
59 #include "insn-config.h"
60 #include "insn-attr.h"
61 #include "except.h"
62 #include "toplev.h"
63 #include "recog.h"
64 #include "cfglayout.h"
65 #include "params.h"
66 #include "sched-int.h"
67 #include "target.h"
68 #include "timevar.h"
69 #include "tree-pass.h"
70
71 /* Define when we want to do count REG_DEAD notes before and after scheduling
72    for sanity checking.  We can't do that when conditional execution is used,
73    as REG_DEAD exist only for unconditional deaths.  */
74
75 #if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING)
76 #define CHECK_DEAD_NOTES 1
77 #else
78 #define CHECK_DEAD_NOTES 0
79 #endif
80
81
82 #ifdef INSN_SCHEDULING
83 /* Some accessor macros for h_i_d members only used within this file.  */
84 #define INSN_REF_COUNT(INSN)    (h_i_d[INSN_UID (INSN)].ref_count)
85 #define FED_BY_SPEC_LOAD(insn)  (h_i_d[INSN_UID (insn)].fed_by_spec_load)
86 #define IS_LOAD_INSN(insn)      (h_i_d[INSN_UID (insn)].is_load_insn)
87
88 /* nr_inter/spec counts interblock/speculative motion for the function.  */
89 static int nr_inter, nr_spec;
90
91 static int is_cfg_nonregular (void);
92 static bool sched_is_disabled_for_current_region_p (void);
93
94 /* A region is the main entity for interblock scheduling: insns
95    are allowed to move between blocks in the same region, along
96    control flow graph edges, in the 'up' direction.  */
97 typedef struct
98 {
99   /* Number of extended basic blocks in region.  */
100   int rgn_nr_blocks;
101   /* cblocks in the region (actually index in rgn_bb_table).  */
102   int rgn_blocks;
103   /* Dependencies for this region are already computed.  Basically, indicates,
104      that this is a recovery block.  */
105   unsigned int dont_calc_deps : 1;
106   /* This region has at least one non-trivial ebb.  */
107   unsigned int has_real_ebb : 1;
108 }
109 region;
110
111 /* Number of regions in the procedure.  */
112 static int nr_regions;
113
114 /* Table of region descriptions.  */
115 static region *rgn_table;
116
117 /* Array of lists of regions' blocks.  */
118 static int *rgn_bb_table;
119
120 /* Topological order of blocks in the region (if b2 is reachable from
121    b1, block_to_bb[b2] > block_to_bb[b1]).  Note: A basic block is
122    always referred to by either block or b, while its topological
123    order name (in the region) is referred to by bb.  */
124 static int *block_to_bb;
125
126 /* The number of the region containing a block.  */
127 static int *containing_rgn;
128
129 /* The minimum probability of reaching a source block so that it will be
130    considered for speculative scheduling.  */
131 static int min_spec_prob;
132
133 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
134 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
135 #define RGN_DONT_CALC_DEPS(rgn) (rgn_table[rgn].dont_calc_deps)
136 #define RGN_HAS_REAL_EBB(rgn) (rgn_table[rgn].has_real_ebb)
137 #define BLOCK_TO_BB(block) (block_to_bb[block])
138 #define CONTAINING_RGN(block) (containing_rgn[block])
139
140 void debug_regions (void);
141 static void find_single_block_region (void);
142 static void find_rgns (void);
143 static void extend_rgns (int *, int *, sbitmap, int *);
144 static bool too_large (int, int *, int *);
145
146 extern void debug_live (int, int);
147
148 /* Blocks of the current region being scheduled.  */
149 static int current_nr_blocks;
150 static int current_blocks;
151
152 static int rgn_n_insns;
153
154 /* The mapping from ebb to block.  */
155 /* ebb_head [i] - is index in rgn_bb_table, while
156    EBB_HEAD (i) - is basic block index.
157    BASIC_BLOCK (EBB_HEAD (i)) - head of ebb.  */
158 #define BB_TO_BLOCK(ebb) (rgn_bb_table[ebb_head[ebb]])
159 #define EBB_FIRST_BB(ebb) BASIC_BLOCK (BB_TO_BLOCK (ebb))
160 #define EBB_LAST_BB(ebb) BASIC_BLOCK (rgn_bb_table[ebb_head[ebb + 1] - 1])
161
162 /* Target info declarations.
163
164    The block currently being scheduled is referred to as the "target" block,
165    while other blocks in the region from which insns can be moved to the
166    target are called "source" blocks.  The candidate structure holds info
167    about such sources: are they valid?  Speculative?  Etc.  */
168 typedef struct
169 {
170   basic_block *first_member;
171   int nr_members;
172 }
173 bblst;
174
175 typedef struct
176 {
177   char is_valid;
178   char is_speculative;
179   int src_prob;
180   bblst split_bbs;
181   bblst update_bbs;
182 }
183 candidate;
184
185 static candidate *candidate_table;
186
187 /* A speculative motion requires checking live information on the path
188    from 'source' to 'target'.  The split blocks are those to be checked.
189    After a speculative motion, live information should be modified in
190    the 'update' blocks.
191
192    Lists of split and update blocks for each candidate of the current
193    target are in array bblst_table.  */
194 static basic_block *bblst_table;
195 static int bblst_size, bblst_last;
196
197 #define IS_VALID(src) ( candidate_table[src].is_valid )
198 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
199 #define SRC_PROB(src) ( candidate_table[src].src_prob )
200
201 /* The bb being currently scheduled.  */
202 static int target_bb;
203
204 /* List of edges.  */
205 typedef struct
206 {
207   edge *first_member;
208   int nr_members;
209 }
210 edgelst;
211
212 static edge *edgelst_table;
213 static int edgelst_last;
214
215 static void extract_edgelst (sbitmap, edgelst *);
216
217
218 /* Target info functions.  */
219 static void split_edges (int, int, edgelst *);
220 static void compute_trg_info (int);
221 void debug_candidate (int);
222 void debug_candidates (int);
223
224 /* Dominators array: dom[i] contains the sbitmap of dominators of
225    bb i in the region.  */
226 static sbitmap *dom;
227
228 /* bb 0 is the only region entry.  */
229 #define IS_RGN_ENTRY(bb) (!bb)
230
231 /* Is bb_src dominated by bb_trg.  */
232 #define IS_DOMINATED(bb_src, bb_trg)                                 \
233 ( TEST_BIT (dom[bb_src], bb_trg) )
234
235 /* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
236    the probability of bb i relative to the region entry.  */
237 static int *prob;
238
239 /* Bit-set of edges, where bit i stands for edge i.  */
240 typedef sbitmap edgeset;
241
242 /* Number of edges in the region.  */
243 static int rgn_nr_edges;
244
245 /* Array of size rgn_nr_edges.  */
246 static edge *rgn_edges;
247
248 /* Mapping from each edge in the graph to its number in the rgn.  */
249 #define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
250 #define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
251
252 /* The split edges of a source bb is different for each target
253    bb.  In order to compute this efficiently, the 'potential-split edges'
254    are computed for each bb prior to scheduling a region.  This is actually
255    the split edges of each bb relative to the region entry.
256
257    pot_split[bb] is the set of potential split edges of bb.  */
258 static edgeset *pot_split;
259
260 /* For every bb, a set of its ancestor edges.  */
261 static edgeset *ancestor_edges;
262
263 /* Array of EBBs sizes.  Currently we can get a ebb only through 
264    splitting of currently scheduling block, therefore, we don't need
265    ebb_head array for every region, its sufficient to hold it only
266    for current one.  */
267 static int *ebb_head;
268
269 static void compute_dom_prob_ps (int);
270
271 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
272 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
273 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
274
275 /* Speculative scheduling functions.  */
276 static int check_live_1 (int, rtx);
277 static void update_live_1 (int, rtx);
278 static int check_live (rtx, int);
279 static void update_live (rtx, int);
280 static void set_spec_fed (rtx);
281 static int is_pfree (rtx, int, int);
282 static int find_conditional_protection (rtx, int);
283 static int is_conditionally_protected (rtx, int, int);
284 static int is_prisky (rtx, int, int);
285 static int is_exception_free (rtx, int, int);
286
287 static bool sets_likely_spilled (rtx);
288 static void sets_likely_spilled_1 (rtx, rtx, void *);
289 static void add_branch_dependences (rtx, rtx);
290 static void compute_block_backward_dependences (int);
291 void debug_dependencies (void);
292
293 static void init_regions (void);
294 static void schedule_region (int);
295 static rtx concat_INSN_LIST (rtx, rtx);
296 static void concat_insn_mem_list (rtx, rtx, rtx *, rtx *);
297 static void propagate_deps (int, struct deps *);
298 static void free_pending_lists (void);
299
300 /* Functions for construction of the control flow graph.  */
301
302 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
303
304    We decide not to build the control flow graph if there is possibly more
305    than one entry to the function, if computed branches exist, if we
306    have nonlocal gotos, or if we have an unreachable loop.  */
307
308 static int
309 is_cfg_nonregular (void)
310 {
311   basic_block b;
312   rtx insn;
313
314   /* If we have a label that could be the target of a nonlocal goto, then
315      the cfg is not well structured.  */
316   if (nonlocal_goto_handler_labels)
317     return 1;
318
319   /* If we have any forced labels, then the cfg is not well structured.  */
320   if (forced_labels)
321     return 1;
322
323   /* If we have exception handlers, then we consider the cfg not well
324      structured.  ?!?  We should be able to handle this now that flow.c
325      computes an accurate cfg for EH.  */
326   if (current_function_has_exception_handlers ())
327     return 1;
328
329   /* If we have non-jumping insns which refer to labels, then we consider
330      the cfg not well structured.  */
331   FOR_EACH_BB (b)
332     FOR_BB_INSNS (b, insn)
333       {
334         /* Check for labels referred by non-jump insns.  */
335         if (NONJUMP_INSN_P (insn) || CALL_P (insn))
336           {
337             rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
338             if (note
339                 && ! (JUMP_P (NEXT_INSN (insn))
340                       && find_reg_note (NEXT_INSN (insn), REG_LABEL,
341                                         XEXP (note, 0))))
342               return 1;
343           }
344         /* If this function has a computed jump, then we consider the cfg
345            not well structured.  */
346         else if (JUMP_P (insn) && computed_jump_p (insn))
347           return 1;
348       }
349
350   /* Unreachable loops with more than one basic block are detected
351      during the DFS traversal in find_rgns.
352
353      Unreachable loops with a single block are detected here.  This
354      test is redundant with the one in find_rgns, but it's much
355      cheaper to go ahead and catch the trivial case here.  */
356   FOR_EACH_BB (b)
357     {
358       if (EDGE_COUNT (b->preds) == 0
359           || (single_pred_p (b)
360               && single_pred (b) == b))
361         return 1;
362     }
363
364   /* All the tests passed.  Consider the cfg well structured.  */
365   return 0;
366 }
367
368 /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits.  */
369
370 static void
371 extract_edgelst (sbitmap set, edgelst *el)
372 {
373   unsigned int i = 0;
374   sbitmap_iterator sbi;
375
376   /* edgelst table space is reused in each call to extract_edgelst.  */
377   edgelst_last = 0;
378
379   el->first_member = &edgelst_table[edgelst_last];
380   el->nr_members = 0;
381
382   /* Iterate over each word in the bitset.  */
383   EXECUTE_IF_SET_IN_SBITMAP (set, 0, i, sbi)
384     {
385       edgelst_table[edgelst_last++] = rgn_edges[i];
386       el->nr_members++;
387     }
388 }
389
390 /* Functions for the construction of regions.  */
391
392 /* Print the regions, for debugging purposes.  Callable from debugger.  */
393
394 void
395 debug_regions (void)
396 {
397   int rgn, bb;
398
399   fprintf (sched_dump, "\n;;   ------------ REGIONS ----------\n\n");
400   for (rgn = 0; rgn < nr_regions; rgn++)
401     {
402       fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
403                rgn_table[rgn].rgn_nr_blocks);
404       fprintf (sched_dump, ";;\tbb/block: ");
405
406       /* We don't have ebb_head initialized yet, so we can't use
407          BB_TO_BLOCK ().  */
408       current_blocks = RGN_BLOCKS (rgn);
409
410       for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
411         fprintf (sched_dump, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
412
413       fprintf (sched_dump, "\n\n");
414     }
415 }
416
417 /* Build a single block region for each basic block in the function.
418    This allows for using the same code for interblock and basic block
419    scheduling.  */
420
421 static void
422 find_single_block_region (void)
423 {
424   basic_block bb;
425
426   nr_regions = 0;
427
428   FOR_EACH_BB (bb)
429     {
430       rgn_bb_table[nr_regions] = bb->index;
431       RGN_NR_BLOCKS (nr_regions) = 1;
432       RGN_BLOCKS (nr_regions) = nr_regions;
433       RGN_DONT_CALC_DEPS (nr_regions) = 0;
434       RGN_HAS_REAL_EBB (nr_regions) = 0;
435       CONTAINING_RGN (bb->index) = nr_regions;
436       BLOCK_TO_BB (bb->index) = 0;
437       nr_regions++;
438     }
439 }
440
441 /* Update number of blocks and the estimate for number of insns
442    in the region.  Return true if the region is "too large" for interblock
443    scheduling (compile time considerations).  */
444
445 static bool
446 too_large (int block, int *num_bbs, int *num_insns)
447 {
448   (*num_bbs)++;
449   (*num_insns) += (INSN_LUID (BB_END (BASIC_BLOCK (block)))
450                    - INSN_LUID (BB_HEAD (BASIC_BLOCK (block))));
451
452   return ((*num_bbs > PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS))
453           || (*num_insns > PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS)));
454 }
455
456 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
457    is still an inner loop.  Put in max_hdr[blk] the header of the most inner
458    loop containing blk.  */
459 #define UPDATE_LOOP_RELATIONS(blk, hdr)         \
460 {                                               \
461   if (max_hdr[blk] == -1)                       \
462     max_hdr[blk] = hdr;                         \
463   else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr])  \
464     RESET_BIT (inner, hdr);                     \
465   else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr])  \
466     {                                           \
467       RESET_BIT (inner,max_hdr[blk]);           \
468       max_hdr[blk] = hdr;                       \
469     }                                           \
470 }
471
472 /* Find regions for interblock scheduling.
473
474    A region for scheduling can be:
475
476      * A loop-free procedure, or
477
478      * A reducible inner loop, or
479
480      * A basic block not contained in any other region.
481
482    ?!? In theory we could build other regions based on extended basic
483    blocks or reverse extended basic blocks.  Is it worth the trouble?
484
485    Loop blocks that form a region are put into the region's block list
486    in topological order.
487
488    This procedure stores its results into the following global (ick) variables
489
490      * rgn_nr
491      * rgn_table
492      * rgn_bb_table
493      * block_to_bb
494      * containing region
495
496    We use dominator relationships to avoid making regions out of non-reducible
497    loops.
498
499    This procedure needs to be converted to work on pred/succ lists instead
500    of edge tables.  That would simplify it somewhat.  */
501
502 static void
503 find_rgns (void)
504 {
505   int *max_hdr, *dfs_nr, *degree;
506   char no_loops = 1;
507   int node, child, loop_head, i, head, tail;
508   int count = 0, sp, idx = 0;
509   edge_iterator current_edge;
510   edge_iterator *stack;
511   int num_bbs, num_insns, unreachable;
512   int too_large_failure;
513   basic_block bb;
514
515   /* Note if a block is a natural loop header.  */
516   sbitmap header;
517
518   /* Note if a block is a natural inner loop header.  */
519   sbitmap inner;
520
521   /* Note if a block is in the block queue.  */
522   sbitmap in_queue;
523
524   /* Note if a block is in the block queue.  */
525   sbitmap in_stack;
526
527   /* Perform a DFS traversal of the cfg.  Identify loop headers, inner loops
528      and a mapping from block to its loop header (if the block is contained
529      in a loop, else -1).
530
531      Store results in HEADER, INNER, and MAX_HDR respectively, these will
532      be used as inputs to the second traversal.
533
534      STACK, SP and DFS_NR are only used during the first traversal.  */
535
536   /* Allocate and initialize variables for the first traversal.  */
537   max_hdr = XNEWVEC (int, last_basic_block);
538   dfs_nr = XCNEWVEC (int, last_basic_block);
539   stack = XNEWVEC (edge_iterator, n_edges);
540
541   inner = sbitmap_alloc (last_basic_block);
542   sbitmap_ones (inner);
543
544   header = sbitmap_alloc (last_basic_block);
545   sbitmap_zero (header);
546
547   in_queue = sbitmap_alloc (last_basic_block);
548   sbitmap_zero (in_queue);
549
550   in_stack = sbitmap_alloc (last_basic_block);
551   sbitmap_zero (in_stack);
552
553   for (i = 0; i < last_basic_block; i++)
554     max_hdr[i] = -1;
555
556   #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
557   #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
558
559   /* DFS traversal to find inner loops in the cfg.  */
560
561   current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR)->succs);
562   sp = -1;
563
564   while (1)
565     {
566       if (EDGE_PASSED (current_edge))
567         {
568           /* We have reached a leaf node or a node that was already
569              processed.  Pop edges off the stack until we find
570              an edge that has not yet been processed.  */
571           while (sp >= 0 && EDGE_PASSED (current_edge))
572             {
573               /* Pop entry off the stack.  */
574               current_edge = stack[sp--];
575               node = ei_edge (current_edge)->src->index;
576               gcc_assert (node != ENTRY_BLOCK);
577               child = ei_edge (current_edge)->dest->index;
578               gcc_assert (child != EXIT_BLOCK);
579               RESET_BIT (in_stack, child);
580               if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
581                 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
582               ei_next (&current_edge);
583             }
584
585           /* See if have finished the DFS tree traversal.  */
586           if (sp < 0 && EDGE_PASSED (current_edge))
587             break;
588
589           /* Nope, continue the traversal with the popped node.  */
590           continue;
591         }
592
593       /* Process a node.  */
594       node = ei_edge (current_edge)->src->index;
595       gcc_assert (node != ENTRY_BLOCK);
596       SET_BIT (in_stack, node);
597       dfs_nr[node] = ++count;
598
599       /* We don't traverse to the exit block.  */
600       child = ei_edge (current_edge)->dest->index;
601       if (child == EXIT_BLOCK)
602         {
603           SET_EDGE_PASSED (current_edge);
604           ei_next (&current_edge);
605           continue;
606         }
607
608       /* If the successor is in the stack, then we've found a loop.
609          Mark the loop, if it is not a natural loop, then it will
610          be rejected during the second traversal.  */
611       if (TEST_BIT (in_stack, child))
612         {
613           no_loops = 0;
614           SET_BIT (header, child);
615           UPDATE_LOOP_RELATIONS (node, child);
616           SET_EDGE_PASSED (current_edge);
617           ei_next (&current_edge);
618           continue;
619         }
620
621       /* If the child was already visited, then there is no need to visit
622          it again.  Just update the loop relationships and restart
623          with a new edge.  */
624       if (dfs_nr[child])
625         {
626           if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
627             UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
628           SET_EDGE_PASSED (current_edge);
629           ei_next (&current_edge);
630           continue;
631         }
632
633       /* Push an entry on the stack and continue DFS traversal.  */
634       stack[++sp] = current_edge;
635       SET_EDGE_PASSED (current_edge);
636       current_edge = ei_start (ei_edge (current_edge)->dest->succs);
637     }
638
639   /* Reset ->aux field used by EDGE_PASSED.  */
640   FOR_ALL_BB (bb)
641     {
642       edge_iterator ei;
643       edge e;
644       FOR_EACH_EDGE (e, ei, bb->succs)
645         e->aux = NULL;
646     }
647
648
649   /* Another check for unreachable blocks.  The earlier test in
650      is_cfg_nonregular only finds unreachable blocks that do not
651      form a loop.
652
653      The DFS traversal will mark every block that is reachable from
654      the entry node by placing a nonzero value in dfs_nr.  Thus if
655      dfs_nr is zero for any block, then it must be unreachable.  */
656   unreachable = 0;
657   FOR_EACH_BB (bb)
658     if (dfs_nr[bb->index] == 0)
659       {
660         unreachable = 1;
661         break;
662       }
663
664   /* Gross.  To avoid wasting memory, the second pass uses the dfs_nr array
665      to hold degree counts.  */
666   degree = dfs_nr;
667
668   FOR_EACH_BB (bb)
669     degree[bb->index] = EDGE_COUNT (bb->preds);
670
671   /* Do not perform region scheduling if there are any unreachable
672      blocks.  */
673   if (!unreachable)
674     {
675       int *queue, *degree1 = NULL;
676       /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
677          there basic blocks, which are forced to be region heads.
678          This is done to try to assemble few smaller regions 
679          from a too_large region.  */
680       sbitmap extended_rgn_header = NULL;
681       bool extend_regions_p;
682
683       if (no_loops)
684         SET_BIT (header, 0);
685
686       /* Second traversal:find reducible inner loops and topologically sort
687          block of each region.  */
688
689       queue = XNEWVEC (int, n_basic_blocks);
690       
691       extend_regions_p = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS) > 0;
692       if (extend_regions_p)
693         {
694           degree1 = xmalloc (last_basic_block * sizeof (int));
695           extended_rgn_header = sbitmap_alloc (last_basic_block);
696           sbitmap_zero (extended_rgn_header);
697         }
698
699       /* Find blocks which are inner loop headers.  We still have non-reducible
700          loops to consider at this point.  */
701       FOR_EACH_BB (bb)
702         {
703           if (TEST_BIT (header, bb->index) && TEST_BIT (inner, bb->index))
704             {
705               edge e;
706               edge_iterator ei;
707               basic_block jbb;
708
709               /* Now check that the loop is reducible.  We do this separate
710                  from finding inner loops so that we do not find a reducible
711                  loop which contains an inner non-reducible loop.
712
713                  A simple way to find reducible/natural loops is to verify
714                  that each block in the loop is dominated by the loop
715                  header.
716
717                  If there exists a block that is not dominated by the loop
718                  header, then the block is reachable from outside the loop
719                  and thus the loop is not a natural loop.  */
720               FOR_EACH_BB (jbb)
721                 {
722                   /* First identify blocks in the loop, except for the loop
723                      entry block.  */
724                   if (bb->index == max_hdr[jbb->index] && bb != jbb)
725                     {
726                       /* Now verify that the block is dominated by the loop
727                          header.  */
728                       if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))
729                         break;
730                     }
731                 }
732
733               /* If we exited the loop early, then I is the header of
734                  a non-reducible loop and we should quit processing it
735                  now.  */
736               if (jbb != EXIT_BLOCK_PTR)
737                 continue;
738
739               /* I is a header of an inner loop, or block 0 in a subroutine
740                  with no loops at all.  */
741               head = tail = -1;
742               too_large_failure = 0;
743               loop_head = max_hdr[bb->index];
744
745               if (extend_regions_p)
746                 /* We save degree in case when we meet a too_large region 
747                    and cancel it.  We need a correct degree later when 
748                    calling extend_rgns.  */
749                 memcpy (degree1, degree, last_basic_block * sizeof (int));
750               
751               /* Decrease degree of all I's successors for topological
752                  ordering.  */
753               FOR_EACH_EDGE (e, ei, bb->succs)
754                 if (e->dest != EXIT_BLOCK_PTR)
755                   --degree[e->dest->index];
756
757               /* Estimate # insns, and count # blocks in the region.  */
758               num_bbs = 1;
759               num_insns = (INSN_LUID (BB_END (bb))
760                            - INSN_LUID (BB_HEAD (bb)));
761
762               /* Find all loop latches (blocks with back edges to the loop
763                  header) or all the leaf blocks in the cfg has no loops.
764
765                  Place those blocks into the queue.  */
766               if (no_loops)
767                 {
768                   FOR_EACH_BB (jbb)
769                     /* Leaf nodes have only a single successor which must
770                        be EXIT_BLOCK.  */
771                     if (single_succ_p (jbb)
772                         && single_succ (jbb) == EXIT_BLOCK_PTR)
773                       {
774                         queue[++tail] = jbb->index;
775                         SET_BIT (in_queue, jbb->index);
776
777                         if (too_large (jbb->index, &num_bbs, &num_insns))
778                           {
779                             too_large_failure = 1;
780                             break;
781                           }
782                       }
783                 }
784               else
785                 {
786                   edge e;
787
788                   FOR_EACH_EDGE (e, ei, bb->preds)
789                     {
790                       if (e->src == ENTRY_BLOCK_PTR)
791                         continue;
792
793                       node = e->src->index;
794
795                       if (max_hdr[node] == loop_head && node != bb->index)
796                         {
797                           /* This is a loop latch.  */
798                           queue[++tail] = node;
799                           SET_BIT (in_queue, node);
800
801                           if (too_large (node, &num_bbs, &num_insns))
802                             {
803                               too_large_failure = 1;
804                               break;
805                             }
806                         }
807                     }
808                 }
809
810               /* Now add all the blocks in the loop to the queue.
811
812              We know the loop is a natural loop; however the algorithm
813              above will not always mark certain blocks as being in the
814              loop.  Consider:
815                 node   children
816                  a        b,c
817                  b        c
818                  c        a,d
819                  d        b
820
821              The algorithm in the DFS traversal may not mark B & D as part
822              of the loop (i.e. they will not have max_hdr set to A).
823
824              We know they can not be loop latches (else they would have
825              had max_hdr set since they'd have a backedge to a dominator
826              block).  So we don't need them on the initial queue.
827
828              We know they are part of the loop because they are dominated
829              by the loop header and can be reached by a backwards walk of
830              the edges starting with nodes on the initial queue.
831
832              It is safe and desirable to include those nodes in the
833              loop/scheduling region.  To do so we would need to decrease
834              the degree of a node if it is the target of a backedge
835              within the loop itself as the node is placed in the queue.
836
837              We do not do this because I'm not sure that the actual
838              scheduling code will properly handle this case. ?!? */
839
840               while (head < tail && !too_large_failure)
841                 {
842                   edge e;
843                   child = queue[++head];
844
845                   FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->preds)
846                     {
847                       node = e->src->index;
848
849                       /* See discussion above about nodes not marked as in
850                          this loop during the initial DFS traversal.  */
851                       if (e->src == ENTRY_BLOCK_PTR
852                           || max_hdr[node] != loop_head)
853                         {
854                           tail = -1;
855                           break;
856                         }
857                       else if (!TEST_BIT (in_queue, node) && node != bb->index)
858                         {
859                           queue[++tail] = node;
860                           SET_BIT (in_queue, node);
861
862                           if (too_large (node, &num_bbs, &num_insns))
863                             {
864                               too_large_failure = 1;
865                               break;
866                             }
867                         }
868                     }
869                 }
870
871               if (tail >= 0 && !too_large_failure)
872                 {
873                   /* Place the loop header into list of region blocks.  */
874                   degree[bb->index] = -1;
875                   rgn_bb_table[idx] = bb->index;
876                   RGN_NR_BLOCKS (nr_regions) = num_bbs;
877                   RGN_BLOCKS (nr_regions) = idx++;
878                   RGN_DONT_CALC_DEPS (nr_regions) = 0;
879                   RGN_HAS_REAL_EBB (nr_regions) = 0;
880                   CONTAINING_RGN (bb->index) = nr_regions;
881                   BLOCK_TO_BB (bb->index) = count = 0;
882
883                   /* Remove blocks from queue[] when their in degree
884                      becomes zero.  Repeat until no blocks are left on the
885                      list.  This produces a topological list of blocks in
886                      the region.  */
887                   while (tail >= 0)
888                     {
889                       if (head < 0)
890                         head = tail;
891                       child = queue[head];
892                       if (degree[child] == 0)
893                         {
894                           edge e;
895
896                           degree[child] = -1;
897                           rgn_bb_table[idx++] = child;
898                           BLOCK_TO_BB (child) = ++count;
899                           CONTAINING_RGN (child) = nr_regions;
900                           queue[head] = queue[tail--];
901
902                           FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->succs)
903                             if (e->dest != EXIT_BLOCK_PTR)
904                               --degree[e->dest->index];
905                         }
906                       else
907                         --head;
908                     }
909                   ++nr_regions;
910                 }
911               else if (extend_regions_p)
912                 {
913                   /* Restore DEGREE.  */
914                   int *t = degree;
915
916                   degree = degree1;
917                   degree1 = t;
918                   
919                   /* And force successors of BB to be region heads.
920                      This may provide several smaller regions instead
921                      of one too_large region.  */
922                   FOR_EACH_EDGE (e, ei, bb->succs)
923                     if (e->dest != EXIT_BLOCK_PTR)
924                       SET_BIT (extended_rgn_header, e->dest->index);
925                 }
926             }
927         }
928       free (queue);
929
930       if (extend_regions_p)
931         {
932           free (degree1);
933           
934           sbitmap_a_or_b (header, header, extended_rgn_header);
935           sbitmap_free (extended_rgn_header);
936  
937           extend_rgns (degree, &idx, header, max_hdr);
938         }
939     }
940
941   /* Any block that did not end up in a region is placed into a region
942      by itself.  */
943   FOR_EACH_BB (bb)
944     if (degree[bb->index] >= 0)
945       {
946         rgn_bb_table[idx] = bb->index;
947         RGN_NR_BLOCKS (nr_regions) = 1;
948         RGN_BLOCKS (nr_regions) = idx++;
949         RGN_DONT_CALC_DEPS (nr_regions) = 0;
950         RGN_HAS_REAL_EBB (nr_regions) = 0;
951         CONTAINING_RGN (bb->index) = nr_regions++;
952         BLOCK_TO_BB (bb->index) = 0;
953       }
954
955   free (max_hdr);
956   free (degree);
957   free (stack);
958   sbitmap_free (header);
959   sbitmap_free (inner);
960   sbitmap_free (in_queue);
961   sbitmap_free (in_stack);
962 }
963
964 static int gather_region_statistics (int **);
965 static void print_region_statistics (int *, int, int *, int);
966
967 /* Calculate the histogram that shows the number of regions having the 
968    given number of basic blocks, and store it in the RSP array.  Return 
969    the size of this array.  */
970 static int
971 gather_region_statistics (int **rsp)
972 {
973   int i, *a = 0, a_sz = 0;
974
975   /* a[i] is the number of regions that have (i + 1) basic blocks.  */
976   for (i = 0; i < nr_regions; i++)
977     {
978       int nr_blocks = RGN_NR_BLOCKS (i);
979
980       gcc_assert (nr_blocks >= 1);
981
982       if (nr_blocks > a_sz)
983         {        
984           a = xrealloc (a, nr_blocks * sizeof (*a));
985           do
986             a[a_sz++] = 0;
987           while (a_sz != nr_blocks);
988         }
989
990       a[nr_blocks - 1]++;
991     }
992
993   *rsp = a;
994   return a_sz;
995 }
996
997 /* Print regions statistics.  S1 and S2 denote the data before and after 
998    calling extend_rgns, respectively.  */
999 static void
1000 print_region_statistics (int *s1, int s1_sz, int *s2, int s2_sz)
1001 {
1002   int i;
1003   
1004   /* We iterate until s2_sz because extend_rgns does not decrease 
1005      the maximal region size.  */
1006   for (i = 1; i < s2_sz; i++)
1007     {
1008       int n1, n2;
1009
1010       n2 = s2[i];
1011
1012       if (n2 == 0)
1013         continue;
1014
1015       if (i >= s1_sz)
1016         n1 = 0;
1017       else
1018         n1 = s1[i];
1019
1020       fprintf (sched_dump, ";; Region extension statistics: size %d: " \
1021                "was %d + %d more\n", i + 1, n1, n2 - n1);
1022     }
1023 }
1024
1025 /* Extend regions.
1026    DEGREE - Array of incoming edge count, considering only
1027    the edges, that don't have their sources in formed regions yet.
1028    IDXP - pointer to the next available index in rgn_bb_table.
1029    HEADER - set of all region heads.
1030    LOOP_HDR - mapping from block to the containing loop
1031    (two blocks can reside within one region if they have
1032    the same loop header).  */
1033 static void
1034 extend_rgns (int *degree, int *idxp, sbitmap header, int *loop_hdr)
1035 {
1036   int *order, i, rescan = 0, idx = *idxp, iter = 0, max_iter, *max_hdr;
1037   int nblocks = n_basic_blocks - NUM_FIXED_BLOCKS;
1038
1039   max_iter = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS);
1040
1041   max_hdr = xmalloc (last_basic_block * sizeof (*max_hdr));
1042
1043   order = xmalloc (last_basic_block * sizeof (*order));
1044   post_order_compute (order, false);
1045
1046   for (i = nblocks - 1; i >= 0; i--)
1047     {
1048       int bbn = order[i];
1049       if (degree[bbn] >= 0)
1050         {
1051           max_hdr[bbn] = bbn;
1052           rescan = 1;
1053         }
1054       else
1055         /* This block already was processed in find_rgns.  */
1056         max_hdr[bbn] = -1;
1057     }
1058   
1059   /* The idea is to topologically walk through CFG in top-down order.
1060      During the traversal, if all the predecessors of a node are
1061      marked to be in the same region (they all have the same max_hdr),
1062      then current node is also marked to be a part of that region. 
1063      Otherwise the node starts its own region.
1064      CFG should be traversed until no further changes are made.  On each 
1065      iteration the set of the region heads is extended (the set of those 
1066      blocks that have max_hdr[bbi] == bbi).  This set is upper bounded by the 
1067      set of all basic blocks, thus the algorithm is guaranteed to terminate.  */
1068
1069   while (rescan && iter < max_iter)
1070     {
1071       rescan = 0;
1072       
1073       for (i = nblocks - 1; i >= 0; i--)
1074         {
1075           edge e;
1076           edge_iterator ei;
1077           int bbn = order[i];
1078         
1079           if (max_hdr[bbn] != -1 && !TEST_BIT (header, bbn))
1080             {
1081               int hdr = -1;
1082
1083               FOR_EACH_EDGE (e, ei, BASIC_BLOCK (bbn)->preds)
1084                 {
1085                   int predn = e->src->index;
1086
1087                   if (predn != ENTRY_BLOCK
1088                       /* If pred wasn't processed in find_rgns.  */
1089                       && max_hdr[predn] != -1
1090                       /* And pred and bb reside in the same loop.
1091                          (Or out of any loop).  */
1092                       && loop_hdr[bbn] == loop_hdr[predn])
1093                     {
1094                       if (hdr == -1)
1095                         /* Then bb extends the containing region of pred.  */
1096                         hdr = max_hdr[predn];
1097                       else if (hdr != max_hdr[predn])
1098                         /* Too bad, there are at least two predecessors
1099                            that reside in different regions.  Thus, BB should
1100                            begin its own region.  */
1101                         {
1102                           hdr = bbn;
1103                           break;
1104                         }                   
1105                     }
1106                   else
1107                     /* BB starts its own region.  */
1108                     {
1109                       hdr = bbn;
1110                       break;
1111                     }           
1112                 }
1113             
1114               if (hdr == bbn)
1115                 {
1116                   /* If BB start its own region,
1117                      update set of headers with BB.  */
1118                   SET_BIT (header, bbn);
1119                   rescan = 1;
1120                 }
1121               else
1122                 gcc_assert (hdr != -1);     
1123
1124               max_hdr[bbn] = hdr;
1125             }
1126         }
1127
1128       iter++;
1129     }
1130   
1131   /* Statistics were gathered on the SPEC2000 package of tests with
1132      mainline weekly snapshot gcc-4.1-20051015 on ia64.
1133      
1134      Statistics for SPECint:
1135      1 iteration : 1751 cases (38.7%)
1136      2 iterations: 2770 cases (61.3%)
1137      Blocks wrapped in regions by find_rgns without extension: 18295 blocks
1138      Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
1139      (We don't count single block regions here).
1140      
1141      Statistics for SPECfp:
1142      1 iteration : 621 cases (35.9%)
1143      2 iterations: 1110 cases (64.1%)
1144      Blocks wrapped in regions by find_rgns without extension: 6476 blocks
1145      Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
1146      (We don't count single block regions here).
1147
1148      By default we do at most 2 iterations.
1149      This can be overridden with max-sched-extend-regions-iters parameter:
1150      0 - disable region extension,
1151      N > 0 - do at most N iterations.  */
1152   
1153   if (sched_verbose && iter != 0)
1154     fprintf (sched_dump, ";; Region extension iterations: %d%s\n", iter,
1155              rescan ? "... failed" : "");
1156     
1157   if (!rescan && iter != 0)
1158     {
1159       int *s1 = NULL, s1_sz = 0;
1160
1161       /* Save the old statistics for later printout.  */
1162       if (sched_verbose >= 6)
1163         s1_sz = gather_region_statistics (&s1);
1164
1165       /* We have succeeded.  Now assemble the regions.  */
1166       for (i = nblocks - 1; i >= 0; i--)
1167         {
1168           int bbn = order[i];
1169
1170           if (max_hdr[bbn] == bbn)
1171             /* BBN is a region head.  */
1172             {
1173               edge e;
1174               edge_iterator ei;
1175               int num_bbs = 0, j, num_insns = 0, large;
1176         
1177               large = too_large (bbn, &num_bbs, &num_insns);
1178
1179               degree[bbn] = -1;
1180               rgn_bb_table[idx] = bbn;
1181               RGN_BLOCKS (nr_regions) = idx++;
1182               RGN_DONT_CALC_DEPS (nr_regions) = 0;
1183               RGN_HAS_REAL_EBB (nr_regions) = 0;
1184               CONTAINING_RGN (bbn) = nr_regions;
1185               BLOCK_TO_BB (bbn) = 0;
1186
1187               FOR_EACH_EDGE (e, ei, BASIC_BLOCK (bbn)->succs)
1188                 if (e->dest != EXIT_BLOCK_PTR)
1189                   degree[e->dest->index]--;
1190
1191               if (!large)
1192                 /* Here we check whether the region is too_large.  */
1193                 for (j = i - 1; j >= 0; j--)
1194                   {
1195                     int succn = order[j];
1196                     if (max_hdr[succn] == bbn)
1197                       {
1198                         if ((large = too_large (succn, &num_bbs, &num_insns)))
1199                           break;
1200                       }
1201                   }
1202
1203               if (large)
1204                 /* If the region is too_large, then wrap every block of
1205                    the region into single block region.
1206                    Here we wrap region head only.  Other blocks are
1207                    processed in the below cycle.  */
1208                 {
1209                   RGN_NR_BLOCKS (nr_regions) = 1;
1210                   nr_regions++;
1211                 }          
1212
1213               num_bbs = 1;
1214
1215               for (j = i - 1; j >= 0; j--)
1216                 {
1217                   int succn = order[j];
1218
1219                   if (max_hdr[succn] == bbn)
1220                     /* This cycle iterates over all basic blocks, that 
1221                        are supposed to be in the region with head BBN,
1222                        and wraps them into that region (or in single
1223                        block region).  */
1224                     {
1225                       gcc_assert (degree[succn] == 0);
1226
1227                       degree[succn] = -1;
1228                       rgn_bb_table[idx] = succn;                 
1229                       BLOCK_TO_BB (succn) = large ? 0 : num_bbs++;
1230                       CONTAINING_RGN (succn) = nr_regions;
1231
1232                       if (large)
1233                         /* Wrap SUCCN into single block region.  */
1234                         {
1235                           RGN_BLOCKS (nr_regions) = idx;
1236                           RGN_NR_BLOCKS (nr_regions) = 1;
1237                           RGN_DONT_CALC_DEPS (nr_regions) = 0;
1238                           RGN_HAS_REAL_EBB (nr_regions) = 0;
1239                           nr_regions++;
1240                         }
1241
1242                       idx++;
1243                                 
1244                       FOR_EACH_EDGE (e, ei, BASIC_BLOCK (succn)->succs)
1245                         if (e->dest != EXIT_BLOCK_PTR)
1246                           degree[e->dest->index]--;
1247                     }
1248                 }
1249
1250               if (!large)
1251                 {
1252                   RGN_NR_BLOCKS (nr_regions) = num_bbs;
1253                   nr_regions++;
1254                 }
1255             }
1256         }
1257
1258       if (sched_verbose >= 6)
1259         {
1260           int *s2, s2_sz;
1261
1262           /* Get the new statistics and print the comparison with the 
1263              one before calling this function.  */
1264           s2_sz = gather_region_statistics (&s2);
1265           print_region_statistics (s1, s1_sz, s2, s2_sz);
1266           free (s1);
1267           free (s2);
1268         }
1269     }
1270   
1271   free (order);
1272   free (max_hdr);
1273
1274   *idxp = idx; 
1275 }
1276
1277 /* Functions for regions scheduling information.  */
1278
1279 /* Compute dominators, probability, and potential-split-edges of bb.
1280    Assume that these values were already computed for bb's predecessors.  */
1281
1282 static void
1283 compute_dom_prob_ps (int bb)
1284 {
1285   edge_iterator in_ei;
1286   edge in_edge;
1287
1288   /* We shouldn't have any real ebbs yet.  */
1289   gcc_assert (ebb_head [bb] == bb + current_blocks);
1290   
1291   if (IS_RGN_ENTRY (bb))
1292     {
1293       SET_BIT (dom[bb], 0);
1294       prob[bb] = REG_BR_PROB_BASE;
1295       return;
1296     }
1297
1298   prob[bb] = 0;
1299
1300   /* Initialize dom[bb] to '111..1'.  */
1301   sbitmap_ones (dom[bb]);
1302
1303   FOR_EACH_EDGE (in_edge, in_ei, BASIC_BLOCK (BB_TO_BLOCK (bb))->preds)
1304     {
1305       int pred_bb;
1306       edge out_edge;
1307       edge_iterator out_ei;
1308
1309       if (in_edge->src == ENTRY_BLOCK_PTR)
1310         continue;
1311
1312       pred_bb = BLOCK_TO_BB (in_edge->src->index);
1313       sbitmap_a_and_b (dom[bb], dom[bb], dom[pred_bb]);
1314       sbitmap_a_or_b (ancestor_edges[bb],
1315                       ancestor_edges[bb], ancestor_edges[pred_bb]);
1316
1317       SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
1318
1319       sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
1320
1321       FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
1322         SET_BIT (pot_split[bb], EDGE_TO_BIT (out_edge));
1323
1324       prob[bb] += ((prob[pred_bb] * in_edge->probability) / REG_BR_PROB_BASE);
1325     }
1326
1327   SET_BIT (dom[bb], bb);
1328   sbitmap_difference (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
1329
1330   if (sched_verbose >= 2)
1331     fprintf (sched_dump, ";;  bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
1332              (100 * prob[bb]) / REG_BR_PROB_BASE);
1333 }
1334
1335 /* Functions for target info.  */
1336
1337 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1338    Note that bb_trg dominates bb_src.  */
1339
1340 static void
1341 split_edges (int bb_src, int bb_trg, edgelst *bl)
1342 {
1343   sbitmap src = sbitmap_alloc (pot_split[bb_src]->n_bits);
1344   sbitmap_copy (src, pot_split[bb_src]);
1345
1346   sbitmap_difference (src, src, pot_split[bb_trg]);
1347   extract_edgelst (src, bl);
1348   sbitmap_free (src);
1349 }
1350
1351 /* Find the valid candidate-source-blocks for the target block TRG, compute
1352    their probability, and check if they are speculative or not.
1353    For speculative sources, compute their update-blocks and split-blocks.  */
1354
1355 static void
1356 compute_trg_info (int trg)
1357 {
1358   candidate *sp;
1359   edgelst el;
1360   int i, j, k, update_idx;
1361   basic_block block;
1362   sbitmap visited;
1363   edge_iterator ei;
1364   edge e;
1365
1366   /* Define some of the fields for the target bb as well.  */
1367   sp = candidate_table + trg;
1368   sp->is_valid = 1;
1369   sp->is_speculative = 0;
1370   sp->src_prob = REG_BR_PROB_BASE;
1371
1372   visited = sbitmap_alloc (last_basic_block);
1373
1374   for (i = trg + 1; i < current_nr_blocks; i++)
1375     {
1376       sp = candidate_table + i;
1377
1378       sp->is_valid = IS_DOMINATED (i, trg);
1379       if (sp->is_valid)
1380         {
1381           int tf = prob[trg], cf = prob[i];
1382
1383           /* In CFGs with low probability edges TF can possibly be zero.  */
1384           sp->src_prob = (tf ? ((cf * REG_BR_PROB_BASE) / tf) : 0);
1385           sp->is_valid = (sp->src_prob >= min_spec_prob);
1386         }
1387
1388       if (sp->is_valid)
1389         {
1390           split_edges (i, trg, &el);
1391           sp->is_speculative = (el.nr_members) ? 1 : 0;
1392           if (sp->is_speculative && !flag_schedule_speculative)
1393             sp->is_valid = 0;
1394         }
1395
1396       if (sp->is_valid)
1397         {
1398           /* Compute split blocks and store them in bblst_table.
1399              The TO block of every split edge is a split block.  */
1400           sp->split_bbs.first_member = &bblst_table[bblst_last];
1401           sp->split_bbs.nr_members = el.nr_members;
1402           for (j = 0; j < el.nr_members; bblst_last++, j++)
1403             bblst_table[bblst_last] = el.first_member[j]->dest;
1404           sp->update_bbs.first_member = &bblst_table[bblst_last];
1405
1406           /* Compute update blocks and store them in bblst_table.
1407              For every split edge, look at the FROM block, and check
1408              all out edges.  For each out edge that is not a split edge,
1409              add the TO block to the update block list.  This list can end
1410              up with a lot of duplicates.  We need to weed them out to avoid
1411              overrunning the end of the bblst_table.  */
1412
1413           update_idx = 0;
1414           sbitmap_zero (visited);
1415           for (j = 0; j < el.nr_members; j++)
1416             {
1417               block = el.first_member[j]->src;
1418               FOR_EACH_EDGE (e, ei, block->succs)
1419                 {
1420                   if (!TEST_BIT (visited, e->dest->index))
1421                     {
1422                       for (k = 0; k < el.nr_members; k++)
1423                         if (e == el.first_member[k])
1424                           break;
1425
1426                       if (k >= el.nr_members)
1427                         {
1428                           bblst_table[bblst_last++] = e->dest;
1429                           SET_BIT (visited, e->dest->index);
1430                           update_idx++;
1431                         }
1432                     }
1433                 }
1434             }
1435           sp->update_bbs.nr_members = update_idx;
1436
1437           /* Make sure we didn't overrun the end of bblst_table.  */
1438           gcc_assert (bblst_last <= bblst_size);
1439         }
1440       else
1441         {
1442           sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1443
1444           sp->is_speculative = 0;
1445           sp->src_prob = 0;
1446         }
1447     }
1448
1449   sbitmap_free (visited);
1450 }
1451
1452 /* Print candidates info, for debugging purposes.  Callable from debugger.  */
1453
1454 void
1455 debug_candidate (int i)
1456 {
1457   if (!candidate_table[i].is_valid)
1458     return;
1459
1460   if (candidate_table[i].is_speculative)
1461     {
1462       int j;
1463       fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1464
1465       fprintf (sched_dump, "split path: ");
1466       for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1467         {
1468           int b = candidate_table[i].split_bbs.first_member[j]->index;
1469
1470           fprintf (sched_dump, " %d ", b);
1471         }
1472       fprintf (sched_dump, "\n");
1473
1474       fprintf (sched_dump, "update path: ");
1475       for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
1476         {
1477           int b = candidate_table[i].update_bbs.first_member[j]->index;
1478
1479           fprintf (sched_dump, " %d ", b);
1480         }
1481       fprintf (sched_dump, "\n");
1482     }
1483   else
1484     {
1485       fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
1486     }
1487 }
1488
1489 /* Print candidates info, for debugging purposes.  Callable from debugger.  */
1490
1491 void
1492 debug_candidates (int trg)
1493 {
1494   int i;
1495
1496   fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
1497            BB_TO_BLOCK (trg), trg);
1498   for (i = trg + 1; i < current_nr_blocks; i++)
1499     debug_candidate (i);
1500 }
1501
1502 /* Functions for speculative scheduling.  */
1503
1504 /* Return 0 if x is a set of a register alive in the beginning of one
1505    of the split-blocks of src, otherwise return 1.  */
1506
1507 static int
1508 check_live_1 (int src, rtx x)
1509 {
1510   int i;
1511   int regno;
1512   rtx reg = SET_DEST (x);
1513
1514   if (reg == 0)
1515     return 1;
1516
1517   while (GET_CODE (reg) == SUBREG
1518          || GET_CODE (reg) == ZERO_EXTRACT
1519          || GET_CODE (reg) == STRICT_LOW_PART)
1520     reg = XEXP (reg, 0);
1521
1522   if (GET_CODE (reg) == PARALLEL)
1523     {
1524       int i;
1525
1526       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1527         if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1528           if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
1529             return 1;
1530
1531       return 0;
1532     }
1533
1534   if (!REG_P (reg))
1535     return 1;
1536
1537   regno = REGNO (reg);
1538
1539   if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1540     {
1541       /* Global registers are assumed live.  */
1542       return 0;
1543     }
1544   else
1545     {
1546       if (regno < FIRST_PSEUDO_REGISTER)
1547         {
1548           /* Check for hard registers.  */
1549           int j = hard_regno_nregs[regno][GET_MODE (reg)];
1550           while (--j >= 0)
1551             {
1552               for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1553                 {
1554                   basic_block b = candidate_table[src].split_bbs.first_member[i];
1555
1556                   /* We can have split blocks, that were recently generated.
1557                      such blocks are always outside current region.  */
1558                   gcc_assert (glat_start[b->index]
1559                               || CONTAINING_RGN (b->index)
1560                               != CONTAINING_RGN (BB_TO_BLOCK (src)));
1561                   if (!glat_start[b->index]
1562                       || REGNO_REG_SET_P (glat_start[b->index],
1563                                           regno + j))
1564                     {
1565                       return 0;
1566                     }
1567                 }
1568             }
1569         }
1570       else
1571         {
1572           /* Check for pseudo registers.  */
1573           for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1574             {
1575               basic_block b = candidate_table[src].split_bbs.first_member[i];
1576
1577               gcc_assert (glat_start[b->index]
1578                           || CONTAINING_RGN (b->index)
1579                           != CONTAINING_RGN (BB_TO_BLOCK (src)));
1580               if (!glat_start[b->index]
1581                   || REGNO_REG_SET_P (glat_start[b->index], regno))
1582                 {
1583                   return 0;
1584                 }
1585             }
1586         }
1587     }
1588
1589   return 1;
1590 }
1591
1592 /* If x is a set of a register R, mark that R is alive in the beginning
1593    of every update-block of src.  */
1594
1595 static void
1596 update_live_1 (int src, rtx x)
1597 {
1598   int i;
1599   int regno;
1600   rtx reg = SET_DEST (x);
1601
1602   if (reg == 0)
1603     return;
1604
1605   while (GET_CODE (reg) == SUBREG
1606          || GET_CODE (reg) == ZERO_EXTRACT
1607          || GET_CODE (reg) == STRICT_LOW_PART)
1608     reg = XEXP (reg, 0);
1609
1610   if (GET_CODE (reg) == PARALLEL)
1611     {
1612       int i;
1613
1614       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1615         if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1616           update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
1617
1618       return;
1619     }
1620
1621   if (!REG_P (reg))
1622     return;
1623
1624   /* Global registers are always live, so the code below does not apply
1625      to them.  */
1626
1627   regno = REGNO (reg);
1628
1629   if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
1630     {
1631       if (regno < FIRST_PSEUDO_REGISTER)
1632         {
1633           int j = hard_regno_nregs[regno][GET_MODE (reg)];
1634           while (--j >= 0)
1635             {
1636               for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1637                 {
1638                   basic_block b = candidate_table[src].update_bbs.first_member[i];
1639
1640                   SET_REGNO_REG_SET (glat_start[b->index], regno + j);
1641                 }
1642             }
1643         }
1644       else
1645         {
1646           for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1647             {
1648               basic_block b = candidate_table[src].update_bbs.first_member[i];
1649
1650               SET_REGNO_REG_SET (glat_start[b->index], regno);
1651             }
1652         }
1653     }
1654 }
1655
1656 /* Return 1 if insn can be speculatively moved from block src to trg,
1657    otherwise return 0.  Called before first insertion of insn to
1658    ready-list or before the scheduling.  */
1659
1660 static int
1661 check_live (rtx insn, int src)
1662 {
1663   /* Find the registers set by instruction.  */
1664   if (GET_CODE (PATTERN (insn)) == SET
1665       || GET_CODE (PATTERN (insn)) == CLOBBER)
1666     return check_live_1 (src, PATTERN (insn));
1667   else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1668     {
1669       int j;
1670       for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1671         if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1672              || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1673             && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
1674           return 0;
1675
1676       return 1;
1677     }
1678
1679   return 1;
1680 }
1681
1682 /* Update the live registers info after insn was moved speculatively from
1683    block src to trg.  */
1684
1685 static void
1686 update_live (rtx insn, int src)
1687 {
1688   /* Find the registers set by instruction.  */
1689   if (GET_CODE (PATTERN (insn)) == SET
1690       || GET_CODE (PATTERN (insn)) == CLOBBER)
1691     update_live_1 (src, PATTERN (insn));
1692   else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1693     {
1694       int j;
1695       for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1696         if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1697             || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1698           update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
1699     }
1700 }
1701
1702 /* Nonzero if block bb_to is equal to, or reachable from block bb_from.  */
1703 #define IS_REACHABLE(bb_from, bb_to)                                    \
1704   (bb_from == bb_to                                                     \
1705    || IS_RGN_ENTRY (bb_from)                                            \
1706    || (TEST_BIT (ancestor_edges[bb_to],                                 \
1707          EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK (BB_TO_BLOCK (bb_from)))))))
1708
1709 /* Turns on the fed_by_spec_load flag for insns fed by load_insn.  */
1710
1711 static void
1712 set_spec_fed (rtx load_insn)
1713 {
1714   dep_link_t link;
1715
1716   FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (load_insn))
1717     if (DEP_LINK_KIND (link) == REG_DEP_TRUE)
1718       FED_BY_SPEC_LOAD (DEP_LINK_CON (link)) = 1;
1719 }
1720
1721 /* On the path from the insn to load_insn_bb, find a conditional
1722 branch depending on insn, that guards the speculative load.  */
1723
1724 static int
1725 find_conditional_protection (rtx insn, int load_insn_bb)
1726 {
1727   dep_link_t link;
1728
1729   /* Iterate through DEF-USE forward dependences.  */
1730   FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (insn))
1731     {
1732       rtx next = DEP_LINK_CON (link);
1733
1734       if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
1735            CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
1736           && IS_REACHABLE (INSN_BB (next), load_insn_bb)
1737           && load_insn_bb != INSN_BB (next)
1738           && DEP_LINK_KIND (link) == REG_DEP_TRUE
1739           && (JUMP_P (next)
1740               || find_conditional_protection (next, load_insn_bb)))
1741         return 1;
1742     }
1743   return 0;
1744 }                               /* find_conditional_protection */
1745
1746 /* Returns 1 if the same insn1 that participates in the computation
1747    of load_insn's address is feeding a conditional branch that is
1748    guarding on load_insn. This is true if we find a the two DEF-USE
1749    chains:
1750    insn1 -> ... -> conditional-branch
1751    insn1 -> ... -> load_insn,
1752    and if a flow path exist:
1753    insn1 -> ... -> conditional-branch -> ... -> load_insn,
1754    and if insn1 is on the path
1755    region-entry -> ... -> bb_trg -> ... load_insn.
1756
1757    Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
1758    Locate the branch by following INSN_FORW_DEPS from insn1.  */
1759
1760 static int
1761 is_conditionally_protected (rtx load_insn, int bb_src, int bb_trg)
1762 {
1763   dep_link_t link;
1764
1765   FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (load_insn))
1766     {
1767       rtx insn1 = DEP_LINK_PRO (link);
1768
1769       /* Must be a DEF-USE dependence upon non-branch.  */
1770       if (DEP_LINK_KIND (link) != REG_DEP_TRUE
1771           || JUMP_P (insn1))
1772         continue;
1773
1774       /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn.  */
1775       if (INSN_BB (insn1) == bb_src
1776           || (CONTAINING_RGN (BLOCK_NUM (insn1))
1777               != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
1778           || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
1779               && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
1780         continue;
1781
1782       /* Now search for the conditional-branch.  */
1783       if (find_conditional_protection (insn1, bb_src))
1784         return 1;
1785
1786       /* Recursive step: search another insn1, "above" current insn1.  */
1787       return is_conditionally_protected (insn1, bb_src, bb_trg);
1788     }
1789
1790   /* The chain does not exist.  */
1791   return 0;
1792 }                               /* is_conditionally_protected */
1793
1794 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1795    load_insn can move speculatively from bb_src to bb_trg.  All the
1796    following must hold:
1797
1798    (1) both loads have 1 base register (PFREE_CANDIDATEs).
1799    (2) load_insn and load1 have a def-use dependence upon
1800    the same insn 'insn1'.
1801    (3) either load2 is in bb_trg, or:
1802    - there's only one split-block, and
1803    - load1 is on the escape path, and
1804
1805    From all these we can conclude that the two loads access memory
1806    addresses that differ at most by a constant, and hence if moving
1807    load_insn would cause an exception, it would have been caused by
1808    load2 anyhow.  */
1809
1810 static int
1811 is_pfree (rtx load_insn, int bb_src, int bb_trg)
1812 {
1813   dep_link_t back_link;
1814   candidate *candp = candidate_table + bb_src;
1815
1816   if (candp->split_bbs.nr_members != 1)
1817     /* Must have exactly one escape block.  */
1818     return 0;
1819
1820   FOR_EACH_DEP_LINK (back_link, INSN_BACK_DEPS (load_insn))
1821     {
1822       rtx insn1 = DEP_LINK_PRO (back_link);
1823
1824       if (DEP_LINK_KIND (back_link) == REG_DEP_TRUE)
1825         {
1826           /* Found a DEF-USE dependence (insn1, load_insn).  */
1827           dep_link_t fore_link;
1828
1829           FOR_EACH_DEP_LINK (fore_link, INSN_FORW_DEPS (insn1))
1830             {
1831               rtx insn2 = DEP_LINK_CON (fore_link);
1832
1833               if (DEP_LINK_KIND (fore_link) == REG_DEP_TRUE)
1834                 {
1835                   /* Found a DEF-USE dependence (insn1, insn2).  */
1836                   if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
1837                     /* insn2 not guaranteed to be a 1 base reg load.  */
1838                     continue;
1839
1840                   if (INSN_BB (insn2) == bb_trg)
1841                     /* insn2 is the similar load, in the target block.  */
1842                     return 1;
1843
1844                   if (*(candp->split_bbs.first_member) == BLOCK_FOR_INSN (insn2))
1845                     /* insn2 is a similar load, in a split-block.  */
1846                     return 1;
1847                 }
1848             }
1849         }
1850     }
1851
1852   /* Couldn't find a similar load.  */
1853   return 0;
1854 }                               /* is_pfree */
1855
1856 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1857    a load moved speculatively, or if load_insn is protected by
1858    a compare on load_insn's address).  */
1859
1860 static int
1861 is_prisky (rtx load_insn, int bb_src, int bb_trg)
1862 {
1863   if (FED_BY_SPEC_LOAD (load_insn))
1864     return 1;
1865
1866   if (deps_list_empty_p (INSN_BACK_DEPS (load_insn)))
1867     /* Dependence may 'hide' out of the region.  */
1868     return 1;
1869
1870   if (is_conditionally_protected (load_insn, bb_src, bb_trg))
1871     return 1;
1872
1873   return 0;
1874 }
1875
1876 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
1877    Return 1 if insn is exception-free (and the motion is valid)
1878    and 0 otherwise.  */
1879
1880 static int
1881 is_exception_free (rtx insn, int bb_src, int bb_trg)
1882 {
1883   int insn_class = haifa_classify_insn (insn);
1884
1885   /* Handle non-load insns.  */
1886   switch (insn_class)
1887     {
1888     case TRAP_FREE:
1889       return 1;
1890     case TRAP_RISKY:
1891       return 0;
1892     default:;
1893     }
1894
1895   /* Handle loads.  */
1896   if (!flag_schedule_speculative_load)
1897     return 0;
1898   IS_LOAD_INSN (insn) = 1;
1899   switch (insn_class)
1900     {
1901     case IFREE:
1902       return (1);
1903     case IRISKY:
1904       return 0;
1905     case PFREE_CANDIDATE:
1906       if (is_pfree (insn, bb_src, bb_trg))
1907         return 1;
1908       /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate.  */
1909     case PRISKY_CANDIDATE:
1910       if (!flag_schedule_speculative_load_dangerous
1911           || is_prisky (insn, bb_src, bb_trg))
1912         return 0;
1913       break;
1914     default:;
1915     }
1916
1917   return flag_schedule_speculative_load_dangerous;
1918 }
1919 \f
1920 /* The number of insns from the current block scheduled so far.  */
1921 static int sched_target_n_insns;
1922 /* The number of insns from the current block to be scheduled in total.  */
1923 static int target_n_insns;
1924 /* The number of insns from the entire region scheduled so far.  */
1925 static int sched_n_insns;
1926
1927 /* Implementations of the sched_info functions for region scheduling.  */
1928 static void init_ready_list (void);
1929 static int can_schedule_ready_p (rtx);
1930 static void begin_schedule_ready (rtx, rtx);
1931 static ds_t new_ready (rtx, ds_t);
1932 static int schedule_more_p (void);
1933 static const char *rgn_print_insn (rtx, int);
1934 static int rgn_rank (rtx, rtx);
1935 static int contributes_to_priority (rtx, rtx);
1936 static void compute_jump_reg_dependencies (rtx, regset, regset, regset);
1937
1938 /* Functions for speculative scheduling.  */
1939 static void add_remove_insn (rtx, int);
1940 static void extend_regions (void);
1941 static void add_block1 (basic_block, basic_block);
1942 static void fix_recovery_cfg (int, int, int);
1943 static basic_block advance_target_bb (basic_block, rtx);
1944 static void check_dead_notes1 (int, sbitmap);
1945 #ifdef ENABLE_CHECKING
1946 static int region_head_or_leaf_p (basic_block, int);
1947 #endif
1948
1949 /* Return nonzero if there are more insns that should be scheduled.  */
1950
1951 static int
1952 schedule_more_p (void)
1953 {
1954   return sched_target_n_insns < target_n_insns;
1955 }
1956
1957 /* Add all insns that are initially ready to the ready list READY.  Called
1958    once before scheduling a set of insns.  */
1959
1960 static void
1961 init_ready_list (void)
1962 {
1963   rtx prev_head = current_sched_info->prev_head;
1964   rtx next_tail = current_sched_info->next_tail;
1965   int bb_src;
1966   rtx insn;
1967
1968   target_n_insns = 0;
1969   sched_target_n_insns = 0;
1970   sched_n_insns = 0;
1971
1972   /* Print debugging information.  */
1973   if (sched_verbose >= 5)
1974     debug_dependencies ();
1975
1976   /* Prepare current target block info.  */
1977   if (current_nr_blocks > 1)
1978     {
1979       candidate_table = XNEWVEC (candidate, current_nr_blocks);
1980
1981       bblst_last = 0;
1982       /* bblst_table holds split blocks and update blocks for each block after
1983          the current one in the region.  split blocks and update blocks are
1984          the TO blocks of region edges, so there can be at most rgn_nr_edges
1985          of them.  */
1986       bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
1987       bblst_table = XNEWVEC (basic_block, bblst_size);
1988
1989       edgelst_last = 0;
1990       edgelst_table = XNEWVEC (edge, rgn_nr_edges);
1991
1992       compute_trg_info (target_bb);
1993     }
1994
1995   /* Initialize ready list with all 'ready' insns in target block.
1996      Count number of insns in the target block being scheduled.  */
1997   for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
1998     {      
1999       try_ready (insn);
2000       target_n_insns++;
2001
2002       gcc_assert (!(TODO_SPEC (insn) & BEGIN_CONTROL));
2003     }
2004
2005   /* Add to ready list all 'ready' insns in valid source blocks.
2006      For speculative insns, check-live, exception-free, and
2007      issue-delay.  */
2008   for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
2009     if (IS_VALID (bb_src))
2010       {
2011         rtx src_head;
2012         rtx src_next_tail;
2013         rtx tail, head;
2014
2015         get_ebb_head_tail (EBB_FIRST_BB (bb_src), EBB_LAST_BB (bb_src),
2016                            &head, &tail);
2017         src_next_tail = NEXT_INSN (tail);
2018         src_head = head;
2019
2020         for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
2021           if (INSN_P (insn))
2022             try_ready (insn);
2023       }
2024 }
2025
2026 /* Called after taking INSN from the ready list.  Returns nonzero if this
2027    insn can be scheduled, nonzero if we should silently discard it.  */
2028
2029 static int
2030 can_schedule_ready_p (rtx insn)
2031 {
2032   /* An interblock motion?  */
2033   if (INSN_BB (insn) != target_bb
2034       && IS_SPECULATIVE_INSN (insn)
2035       && !check_live (insn, INSN_BB (insn)))
2036     return 0;          
2037   else
2038     return 1;
2039 }
2040
2041 /* Updates counter and other information.  Split from can_schedule_ready_p ()
2042    because when we schedule insn speculatively then insn passed to
2043    can_schedule_ready_p () differs from the one passed to
2044    begin_schedule_ready ().  */
2045 static void
2046 begin_schedule_ready (rtx insn, rtx last ATTRIBUTE_UNUSED)
2047 {
2048   /* An interblock motion?  */
2049   if (INSN_BB (insn) != target_bb)
2050     {
2051       if (IS_SPECULATIVE_INSN (insn))
2052         {
2053           gcc_assert (check_live (insn, INSN_BB (insn)));
2054
2055           update_live (insn, INSN_BB (insn));
2056
2057           /* For speculative load, mark insns fed by it.  */
2058           if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
2059             set_spec_fed (insn);
2060
2061           nr_spec++;
2062         }
2063       nr_inter++;
2064     }
2065   else
2066     {
2067       /* In block motion.  */
2068       sched_target_n_insns++;
2069     }
2070   sched_n_insns++;
2071 }
2072
2073 /* Called after INSN has all its hard dependencies resolved and the speculation
2074    of type TS is enough to overcome them all.
2075    Return nonzero if it should be moved to the ready list or the queue, or zero
2076    if we should silently discard it.  */
2077 static ds_t
2078 new_ready (rtx next, ds_t ts)
2079 {
2080   if (INSN_BB (next) != target_bb)
2081     {
2082       int not_ex_free = 0;
2083
2084       /* For speculative insns, before inserting to ready/queue,
2085          check live, exception-free, and issue-delay.  */       
2086       if (!IS_VALID (INSN_BB (next))
2087           || CANT_MOVE (next)
2088           || (IS_SPECULATIVE_INSN (next)
2089               && ((recog_memoized (next) >= 0
2090                    && min_insn_conflict_delay (curr_state, next, next) 
2091                    > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY))
2092                   || IS_SPECULATION_CHECK_P (next)
2093                   || !check_live (next, INSN_BB (next))
2094                   || (not_ex_free = !is_exception_free (next, INSN_BB (next),
2095                                                         target_bb)))))
2096         {
2097           if (not_ex_free
2098               /* We are here because is_exception_free () == false.
2099                  But we possibly can handle that with control speculation.  */
2100               && current_sched_info->flags & DO_SPECULATION)
2101             /* Here we got new control-speculative instruction.  */
2102             ts = set_dep_weak (ts, BEGIN_CONTROL, MAX_DEP_WEAK);
2103           else
2104             ts = (ts & ~SPECULATIVE) | HARD_DEP;
2105         }
2106     }
2107   
2108   return ts;
2109 }
2110
2111 /* Return a string that contains the insn uid and optionally anything else
2112    necessary to identify this insn in an output.  It's valid to use a
2113    static buffer for this.  The ALIGNED parameter should cause the string
2114    to be formatted so that multiple output lines will line up nicely.  */
2115
2116 static const char *
2117 rgn_print_insn (rtx insn, int aligned)
2118 {
2119   static char tmp[80];
2120
2121   if (aligned)
2122     sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
2123   else
2124     {
2125       if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
2126         sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
2127       else
2128         sprintf (tmp, "%d", INSN_UID (insn));
2129     }
2130   return tmp;
2131 }
2132
2133 /* Compare priority of two insns.  Return a positive number if the second
2134    insn is to be preferred for scheduling, and a negative one if the first
2135    is to be preferred.  Zero if they are equally good.  */
2136
2137 static int
2138 rgn_rank (rtx insn1, rtx insn2)
2139 {
2140   /* Some comparison make sense in interblock scheduling only.  */
2141   if (INSN_BB (insn1) != INSN_BB (insn2))
2142     {
2143       int spec_val, prob_val;
2144
2145       /* Prefer an inblock motion on an interblock motion.  */
2146       if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
2147         return 1;
2148       if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
2149         return -1;
2150
2151       /* Prefer a useful motion on a speculative one.  */
2152       spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
2153       if (spec_val)
2154         return spec_val;
2155
2156       /* Prefer a more probable (speculative) insn.  */
2157       prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
2158       if (prob_val)
2159         return prob_val;
2160     }
2161   return 0;
2162 }
2163
2164 /* NEXT is an instruction that depends on INSN (a backward dependence);
2165    return nonzero if we should include this dependence in priority
2166    calculations.  */
2167
2168 static int
2169 contributes_to_priority (rtx next, rtx insn)
2170 {
2171   /* NEXT and INSN reside in one ebb.  */
2172   return BLOCK_TO_BB (BLOCK_NUM (next)) == BLOCK_TO_BB (BLOCK_NUM (insn));
2173 }
2174
2175 /* INSN is a JUMP_INSN, COND_SET is the set of registers that are
2176    conditionally set before INSN.  Store the set of registers that
2177    must be considered as used by this jump in USED and that of
2178    registers that must be considered as set in SET.  */
2179
2180 static void
2181 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
2182                                regset cond_exec ATTRIBUTE_UNUSED,
2183                                regset used ATTRIBUTE_UNUSED,
2184                                regset set ATTRIBUTE_UNUSED)
2185 {
2186   /* Nothing to do here, since we postprocess jumps in
2187      add_branch_dependences.  */
2188 }
2189
2190 /* Used in schedule_insns to initialize current_sched_info for scheduling
2191    regions (or single basic blocks).  */
2192
2193 static struct sched_info region_sched_info =
2194 {
2195   init_ready_list,
2196   can_schedule_ready_p,
2197   schedule_more_p,
2198   new_ready,
2199   rgn_rank,
2200   rgn_print_insn,
2201   contributes_to_priority,
2202   compute_jump_reg_dependencies,
2203
2204   NULL, NULL,
2205   NULL, NULL,
2206   0, 0, 0,
2207
2208   add_remove_insn,
2209   begin_schedule_ready,
2210   add_block1,
2211   advance_target_bb,
2212   fix_recovery_cfg,
2213 #ifdef ENABLE_CHECKING
2214   region_head_or_leaf_p,
2215 #endif
2216   SCHED_RGN | USE_GLAT
2217 #ifdef ENABLE_CHECKING
2218   | DETACH_LIFE_INFO
2219 #endif
2220 };
2221
2222 /* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register.  */
2223
2224 static bool
2225 sets_likely_spilled (rtx pat)
2226 {
2227   bool ret = false;
2228   note_stores (pat, sets_likely_spilled_1, &ret);
2229   return ret;
2230 }
2231
2232 static void
2233 sets_likely_spilled_1 (rtx x, rtx pat, void *data)
2234 {
2235   bool *ret = (bool *) data;
2236
2237   if (GET_CODE (pat) == SET
2238       && REG_P (x)
2239       && REGNO (x) < FIRST_PSEUDO_REGISTER
2240       && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x))))
2241     *ret = true;
2242 }
2243
2244 /* Add dependences so that branches are scheduled to run last in their
2245    block.  */
2246
2247 static void
2248 add_branch_dependences (rtx head, rtx tail)
2249 {
2250   rtx insn, last;
2251
2252   /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2253      that can throw exceptions, force them to remain in order at the end of
2254      the block by adding dependencies and giving the last a high priority.
2255      There may be notes present, and prev_head may also be a note.
2256
2257      Branches must obviously remain at the end.  Calls should remain at the
2258      end since moving them results in worse register allocation.  Uses remain
2259      at the end to ensure proper register allocation.
2260
2261      cc0 setters remain at the end because they can't be moved away from
2262      their cc0 user.
2263
2264      COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
2265
2266      Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values)
2267      are not moved before reload because we can wind up with register
2268      allocation failures.  */
2269
2270   insn = tail;
2271   last = 0;
2272   while (CALL_P (insn)
2273          || JUMP_P (insn)
2274          || (NONJUMP_INSN_P (insn)
2275              && (GET_CODE (PATTERN (insn)) == USE
2276                  || GET_CODE (PATTERN (insn)) == CLOBBER
2277                  || can_throw_internal (insn)
2278 #ifdef HAVE_cc0
2279                  || sets_cc0_p (PATTERN (insn))
2280 #endif
2281                  || (!reload_completed
2282                      && sets_likely_spilled (PATTERN (insn)))))
2283          || NOTE_P (insn))
2284     {
2285       if (!NOTE_P (insn))
2286         {
2287           if (last != 0
2288               && (find_link_by_pro_in_deps_list (INSN_BACK_DEPS (last), insn)
2289                   == NULL))
2290             {
2291               if (! sched_insns_conditions_mutex_p (last, insn))
2292                 add_dependence (last, insn, REG_DEP_ANTI);
2293               INSN_REF_COUNT (insn)++;
2294             }
2295
2296           CANT_MOVE (insn) = 1;
2297
2298           last = insn;
2299         }
2300
2301       /* Don't overrun the bounds of the basic block.  */
2302       if (insn == head)
2303         break;
2304
2305       insn = PREV_INSN (insn);
2306     }
2307
2308   /* Make sure these insns are scheduled last in their block.  */
2309   insn = last;
2310   if (insn != 0)
2311     while (insn != head)
2312       {
2313         insn = prev_nonnote_insn (insn);
2314
2315         if (INSN_REF_COUNT (insn) != 0)
2316           continue;
2317
2318         if (! sched_insns_conditions_mutex_p (last, insn))
2319           add_dependence (last, insn, REG_DEP_ANTI);
2320         INSN_REF_COUNT (insn) = 1;
2321       }
2322
2323 #ifdef HAVE_conditional_execution
2324   /* Finally, if the block ends in a jump, and we are doing intra-block
2325      scheduling, make sure that the branch depends on any COND_EXEC insns
2326      inside the block to avoid moving the COND_EXECs past the branch insn.
2327
2328      We only have to do this after reload, because (1) before reload there
2329      are no COND_EXEC insns, and (2) the region scheduler is an intra-block
2330      scheduler after reload.
2331
2332      FIXME: We could in some cases move COND_EXEC insns past the branch if
2333      this scheduler would be a little smarter.  Consider this code:
2334
2335                 T = [addr]
2336         C  ?    addr += 4
2337         !C ?    X += 12
2338         C  ?    T += 1
2339         C  ?    jump foo
2340
2341      On a target with a one cycle stall on a memory access the optimal
2342      sequence would be:
2343
2344                 T = [addr]
2345         C  ?    addr += 4
2346         C  ?    T += 1
2347         C  ?    jump foo
2348         !C ?    X += 12
2349
2350      We don't want to put the 'X += 12' before the branch because it just
2351      wastes a cycle of execution time when the branch is taken.
2352
2353      Note that in the example "!C" will always be true.  That is another
2354      possible improvement for handling COND_EXECs in this scheduler: it
2355      could remove always-true predicates.  */
2356
2357   if (!reload_completed || ! JUMP_P (tail))
2358     return;
2359
2360   insn = tail;
2361   while (insn != head)
2362     {
2363       insn = PREV_INSN (insn);
2364
2365       /* Note that we want to add this dependency even when
2366          sched_insns_conditions_mutex_p returns true.  The whole point
2367          is that we _want_ this dependency, even if these insns really
2368          are independent.  */
2369       if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC)
2370         add_dependence (tail, insn, REG_DEP_ANTI);
2371     }
2372 #endif
2373 }
2374
2375 /* Data structures for the computation of data dependences in a regions.  We
2376    keep one `deps' structure for every basic block.  Before analyzing the
2377    data dependences for a bb, its variables are initialized as a function of
2378    the variables of its predecessors.  When the analysis for a bb completes,
2379    we save the contents to the corresponding bb_deps[bb] variable.  */
2380
2381 static struct deps *bb_deps;
2382
2383 /* Duplicate the INSN_LIST elements of COPY and prepend them to OLD.  */
2384
2385 static rtx
2386 concat_INSN_LIST (rtx copy, rtx old)
2387 {
2388   rtx new = old;
2389   for (; copy ; copy = XEXP (copy, 1))
2390     new = alloc_INSN_LIST (XEXP (copy, 0), new);
2391   return new;
2392 }
2393
2394 static void
2395 concat_insn_mem_list (rtx copy_insns, rtx copy_mems, rtx *old_insns_p,
2396                       rtx *old_mems_p)
2397 {
2398   rtx new_insns = *old_insns_p;
2399   rtx new_mems = *old_mems_p;
2400
2401   while (copy_insns)
2402     {
2403       new_insns = alloc_INSN_LIST (XEXP (copy_insns, 0), new_insns);
2404       new_mems = alloc_EXPR_LIST (VOIDmode, XEXP (copy_mems, 0), new_mems);
2405       copy_insns = XEXP (copy_insns, 1);
2406       copy_mems = XEXP (copy_mems, 1);
2407     }
2408
2409   *old_insns_p = new_insns;
2410   *old_mems_p = new_mems;
2411 }
2412
2413 /* After computing the dependencies for block BB, propagate the dependencies
2414    found in TMP_DEPS to the successors of the block.  */
2415 static void
2416 propagate_deps (int bb, struct deps *pred_deps)
2417 {
2418   basic_block block = BASIC_BLOCK (BB_TO_BLOCK (bb));
2419   edge_iterator ei;
2420   edge e;
2421
2422   /* bb's structures are inherited by its successors.  */
2423   FOR_EACH_EDGE (e, ei, block->succs)
2424     {
2425       struct deps *succ_deps;
2426       unsigned reg;
2427       reg_set_iterator rsi;
2428
2429       /* Only bbs "below" bb, in the same region, are interesting.  */
2430       if (e->dest == EXIT_BLOCK_PTR
2431           || CONTAINING_RGN (block->index) != CONTAINING_RGN (e->dest->index)
2432           || BLOCK_TO_BB (e->dest->index) <= bb)
2433         continue;
2434
2435       succ_deps = bb_deps + BLOCK_TO_BB (e->dest->index);
2436
2437       /* The reg_last lists are inherited by successor.  */
2438       EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi)
2439         {
2440           struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
2441           struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
2442
2443           succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
2444           succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
2445           succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
2446                                                 succ_rl->clobbers);
2447           succ_rl->uses_length += pred_rl->uses_length;
2448           succ_rl->clobbers_length += pred_rl->clobbers_length;
2449         }
2450       IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
2451
2452       /* Mem read/write lists are inherited by successor.  */
2453       concat_insn_mem_list (pred_deps->pending_read_insns,
2454                             pred_deps->pending_read_mems,
2455                             &succ_deps->pending_read_insns,
2456                             &succ_deps->pending_read_mems);
2457       concat_insn_mem_list (pred_deps->pending_write_insns,
2458                             pred_deps->pending_write_mems,
2459                             &succ_deps->pending_write_insns,
2460                             &succ_deps->pending_write_mems);
2461
2462       succ_deps->last_pending_memory_flush
2463         = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
2464                             succ_deps->last_pending_memory_flush);
2465
2466       succ_deps->pending_lists_length += pred_deps->pending_lists_length;
2467       succ_deps->pending_flush_length += pred_deps->pending_flush_length;
2468
2469       /* last_function_call is inherited by successor.  */
2470       succ_deps->last_function_call
2471         = concat_INSN_LIST (pred_deps->last_function_call,
2472                               succ_deps->last_function_call);
2473
2474       /* sched_before_next_call is inherited by successor.  */
2475       succ_deps->sched_before_next_call
2476         = concat_INSN_LIST (pred_deps->sched_before_next_call,
2477                             succ_deps->sched_before_next_call);
2478     }
2479
2480   /* These lists should point to the right place, for correct
2481      freeing later.  */
2482   bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
2483   bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
2484   bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
2485   bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
2486
2487   /* Can't allow these to be freed twice.  */
2488   pred_deps->pending_read_insns = 0;
2489   pred_deps->pending_read_mems = 0;
2490   pred_deps->pending_write_insns = 0;
2491   pred_deps->pending_write_mems = 0;
2492 }
2493
2494 /* Compute backward dependences inside bb.  In a multiple blocks region:
2495    (1) a bb is analyzed after its predecessors, and (2) the lists in
2496    effect at the end of bb (after analyzing for bb) are inherited by
2497    bb's successors.
2498
2499    Specifically for reg-reg data dependences, the block insns are
2500    scanned by sched_analyze () top-to-bottom.  Two lists are
2501    maintained by sched_analyze (): reg_last[].sets for register DEFs,
2502    and reg_last[].uses for register USEs.
2503
2504    When analysis is completed for bb, we update for its successors:
2505    ;  - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2506    ;  - USES[succ] = Union (USES [succ], DEFS [bb])
2507
2508    The mechanism for computing mem-mem data dependence is very
2509    similar, and the result is interblock dependences in the region.  */
2510
2511 static void
2512 compute_block_backward_dependences (int bb)
2513 {
2514   rtx head, tail;
2515   struct deps tmp_deps;
2516
2517   tmp_deps = bb_deps[bb];
2518
2519   /* Do the analysis for this block.  */
2520   gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2521   get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2522   sched_analyze (&tmp_deps, head, tail);
2523   add_branch_dependences (head, tail);
2524
2525   if (current_nr_blocks > 1)
2526     propagate_deps (bb, &tmp_deps);
2527
2528   /* Free up the INSN_LISTs.  */
2529   free_deps (&tmp_deps);
2530 }
2531
2532 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2533    them to the unused_*_list variables, so that they can be reused.  */
2534
2535 static void
2536 free_pending_lists (void)
2537 {
2538   int bb;
2539
2540   for (bb = 0; bb < current_nr_blocks; bb++)
2541     {
2542       free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
2543       free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
2544       free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
2545       free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
2546     }
2547 }
2548 \f
2549 /* Print dependences for debugging, callable from debugger.  */
2550
2551 void
2552 debug_dependencies (void)
2553 {
2554   int bb;
2555
2556   fprintf (sched_dump, ";;   --------------- forward dependences: ------------ \n");
2557   for (bb = 0; bb < current_nr_blocks; bb++)
2558     {
2559       rtx head, tail;
2560       rtx next_tail;
2561       rtx insn;
2562
2563       gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2564       get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2565       next_tail = NEXT_INSN (tail);
2566       fprintf (sched_dump, "\n;;   --- Region Dependences --- b %d bb %d \n",
2567                BB_TO_BLOCK (bb), bb);
2568
2569       fprintf (sched_dump, ";;   %7s%6s%6s%6s%6s%6s%14s\n",
2570                "insn", "code", "bb", "dep", "prio", "cost",
2571                "reservation");
2572       fprintf (sched_dump, ";;   %7s%6s%6s%6s%6s%6s%14s\n",
2573                "----", "----", "--", "---", "----", "----",
2574                "-----------");
2575
2576       for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2577         {
2578           dep_link_t link;
2579
2580           if (! INSN_P (insn))
2581             {
2582               int n;
2583               fprintf (sched_dump, ";;   %6d ", INSN_UID (insn));
2584               if (NOTE_P (insn))
2585                 {
2586                   n = NOTE_LINE_NUMBER (insn);
2587                   if (n < 0)
2588                     fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
2589                 }
2590               else
2591                 fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
2592               continue;
2593             }
2594
2595           fprintf (sched_dump,
2596                    ";;   %s%5d%6d%6d%6d%6d%6d   ",
2597                    (SCHED_GROUP_P (insn) ? "+" : " "),
2598                    INSN_UID (insn),
2599                    INSN_CODE (insn),
2600                    INSN_BB (insn),
2601                    INSN_DEP_COUNT (insn),
2602                    INSN_PRIORITY (insn),
2603                    insn_cost (insn));
2604
2605           if (recog_memoized (insn) < 0)
2606             fprintf (sched_dump, "nothing");
2607           else
2608             print_reservation (sched_dump, insn);
2609
2610           fprintf (sched_dump, "\t: ");
2611           FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (insn))
2612             fprintf (sched_dump, "%d ", INSN_UID (DEP_LINK_CON (link)));
2613           fprintf (sched_dump, "\n");
2614         }
2615     }
2616   fprintf (sched_dump, "\n");
2617 }
2618 \f
2619 /* Returns true if all the basic blocks of the current region have
2620    NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region.  */
2621 static bool
2622 sched_is_disabled_for_current_region_p (void)
2623 {
2624   int bb;
2625
2626   for (bb = 0; bb < current_nr_blocks; bb++)
2627     if (!(BASIC_BLOCK (BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE))
2628       return false;
2629
2630   return true;
2631 }
2632
2633 /* Schedule a region.  A region is either an inner loop, a loop-free
2634    subroutine, or a single basic block.  Each bb in the region is
2635    scheduled after its flow predecessors.  */
2636
2637 static void
2638 schedule_region (int rgn)
2639 {
2640   basic_block block;
2641   edge_iterator ei;
2642   edge e;
2643   int bb;
2644   int sched_rgn_n_insns = 0;
2645
2646   rgn_n_insns = 0;
2647   /* Set variables for the current region.  */
2648   current_nr_blocks = RGN_NR_BLOCKS (rgn);
2649   current_blocks = RGN_BLOCKS (rgn);
2650   
2651   /* See comments in add_block1, for what reasons we allocate +1 element.  */ 
2652   ebb_head = xrealloc (ebb_head, (current_nr_blocks + 1) * sizeof (*ebb_head));
2653   for (bb = 0; bb <= current_nr_blocks; bb++)
2654     ebb_head[bb] = current_blocks + bb;
2655
2656   /* Don't schedule region that is marked by
2657      NOTE_DISABLE_SCHED_OF_BLOCK.  */
2658   if (sched_is_disabled_for_current_region_p ())
2659     return;
2660
2661   if (!RGN_DONT_CALC_DEPS (rgn))
2662     {
2663       init_deps_global ();
2664
2665       /* Initializations for region data dependence analysis.  */
2666       bb_deps = XNEWVEC (struct deps, current_nr_blocks);
2667       for (bb = 0; bb < current_nr_blocks; bb++)
2668         init_deps (bb_deps + bb);
2669
2670       /* Compute backward dependencies.  */
2671       for (bb = 0; bb < current_nr_blocks; bb++)
2672         compute_block_backward_dependences (bb);
2673
2674       /* Compute forward dependencies.  */
2675       for (bb = current_nr_blocks - 1; bb >= 0; bb--)
2676         {
2677           rtx head, tail;
2678
2679           gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2680           get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2681
2682           compute_forward_dependences (head, tail);
2683
2684           if (targetm.sched.dependencies_evaluation_hook)
2685             targetm.sched.dependencies_evaluation_hook (head, tail);
2686         }
2687
2688       free_pending_lists ();
2689
2690       finish_deps_global ();
2691
2692       free (bb_deps);
2693     }
2694   else
2695     /* This is a recovery block.  It is always a single block region.  */
2696     gcc_assert (current_nr_blocks == 1);
2697       
2698   /* Set priorities.  */
2699   current_sched_info->sched_max_insns_priority = 0;
2700   for (bb = 0; bb < current_nr_blocks; bb++)
2701     {
2702       rtx head, tail;
2703       
2704       gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2705       get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2706
2707       rgn_n_insns += set_priorities (head, tail);
2708     }
2709   current_sched_info->sched_max_insns_priority++;
2710
2711   /* Compute interblock info: probabilities, split-edges, dominators, etc.  */
2712   if (current_nr_blocks > 1)
2713     {
2714       prob = XNEWVEC (int, current_nr_blocks);
2715
2716       dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
2717       sbitmap_vector_zero (dom, current_nr_blocks);
2718
2719       /* Use ->aux to implement EDGE_TO_BIT mapping.  */
2720       rgn_nr_edges = 0;
2721       FOR_EACH_BB (block)
2722         {
2723           if (CONTAINING_RGN (block->index) != rgn)
2724             continue;
2725           FOR_EACH_EDGE (e, ei, block->succs)
2726             SET_EDGE_TO_BIT (e, rgn_nr_edges++);
2727         }
2728
2729       rgn_edges = XNEWVEC (edge, rgn_nr_edges);
2730       rgn_nr_edges = 0;
2731       FOR_EACH_BB (block)
2732         {
2733           if (CONTAINING_RGN (block->index) != rgn)
2734             continue;
2735           FOR_EACH_EDGE (e, ei, block->succs)
2736             rgn_edges[rgn_nr_edges++] = e;
2737         }
2738
2739       /* Split edges.  */
2740       pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2741       sbitmap_vector_zero (pot_split, current_nr_blocks);
2742       ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2743       sbitmap_vector_zero (ancestor_edges, current_nr_blocks);
2744
2745       /* Compute probabilities, dominators, split_edges.  */
2746       for (bb = 0; bb < current_nr_blocks; bb++)
2747         compute_dom_prob_ps (bb);
2748
2749       /* Cleanup ->aux used for EDGE_TO_BIT mapping.  */
2750       /* We don't need them anymore.  But we want to avoid duplication of
2751          aux fields in the newly created edges.  */
2752       FOR_EACH_BB (block)
2753         {
2754           if (CONTAINING_RGN (block->index) != rgn)
2755             continue;
2756           FOR_EACH_EDGE (e, ei, block->succs)
2757             e->aux = NULL;
2758         }
2759     }
2760
2761   /* Now we can schedule all blocks.  */
2762   for (bb = 0; bb < current_nr_blocks; bb++)
2763     {
2764       basic_block first_bb, last_bb, curr_bb;
2765       rtx head, tail;
2766
2767       first_bb = EBB_FIRST_BB (bb);
2768       last_bb = EBB_LAST_BB (bb);
2769
2770       get_ebb_head_tail (first_bb, last_bb, &head, &tail);
2771
2772       if (no_real_insns_p (head, tail))
2773         {
2774           gcc_assert (first_bb == last_bb);
2775           continue;
2776         }
2777
2778       current_sched_info->prev_head = PREV_INSN (head);
2779       current_sched_info->next_tail = NEXT_INSN (tail);
2780
2781
2782       /* rm_other_notes only removes notes which are _inside_ the
2783          block---that is, it won't remove notes before the first real insn
2784          or after the last real insn of the block.  So if the first insn
2785          has a REG_SAVE_NOTE which would otherwise be emitted before the
2786          insn, it is redundant with the note before the start of the
2787          block, and so we have to take it out.  */
2788       if (INSN_P (head))
2789         {
2790           rtx note;
2791
2792           for (note = REG_NOTES (head); note; note = XEXP (note, 1))
2793             if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
2794               remove_note (head, note);
2795         }
2796       else
2797         /* This means that first block in ebb is empty.
2798            It looks to me as an impossible thing.  There at least should be
2799            a recovery check, that caused the splitting.  */
2800         gcc_unreachable ();
2801
2802       /* Remove remaining note insns from the block, save them in
2803          note_list.  These notes are restored at the end of
2804          schedule_block ().  */
2805       rm_other_notes (head, tail);
2806
2807       unlink_bb_notes (first_bb, last_bb);
2808
2809       target_bb = bb;
2810
2811       gcc_assert (flag_schedule_interblock || current_nr_blocks == 1);
2812       current_sched_info->queue_must_finish_empty = current_nr_blocks == 1;
2813
2814       curr_bb = first_bb;
2815       schedule_block (&curr_bb, rgn_n_insns);
2816       gcc_assert (EBB_FIRST_BB (bb) == first_bb);
2817       sched_rgn_n_insns += sched_n_insns;
2818
2819       /* Clean up.  */
2820       if (current_nr_blocks > 1)
2821         {
2822           free (candidate_table);
2823           free (bblst_table);
2824           free (edgelst_table);
2825         }
2826     }
2827
2828   /* Sanity check: verify that all region insns were scheduled.  */
2829   gcc_assert (sched_rgn_n_insns == rgn_n_insns);
2830
2831
2832   /* Done with this region.  */
2833
2834   if (current_nr_blocks > 1)
2835     {
2836       free (prob);
2837       sbitmap_vector_free (dom);
2838       sbitmap_vector_free (pot_split);
2839       sbitmap_vector_free (ancestor_edges);
2840       free (rgn_edges);
2841     }
2842 }
2843
2844 /* Indexed by region, holds the number of death notes found in that region.
2845    Used for consistency checks.  */
2846 static int *deaths_in_region;
2847
2848 /* Initialize data structures for region scheduling.  */
2849
2850 static void
2851 init_regions (void)
2852 {
2853   sbitmap blocks;
2854   int rgn;
2855
2856   nr_regions = 0;
2857   rgn_table = 0;
2858   rgn_bb_table = 0;
2859   block_to_bb = 0;
2860   containing_rgn = 0;
2861   extend_regions ();
2862
2863   /* Compute regions for scheduling.  */
2864   if (reload_completed
2865       || n_basic_blocks == NUM_FIXED_BLOCKS + 1
2866       || !flag_schedule_interblock
2867       || is_cfg_nonregular ())
2868     {
2869       find_single_block_region ();
2870     }
2871   else
2872     {
2873       /* Compute the dominators and post dominators.  */
2874       calculate_dominance_info (CDI_DOMINATORS);
2875
2876       /* Find regions.  */
2877       find_rgns ();
2878
2879       if (sched_verbose >= 3)
2880         debug_regions ();
2881
2882       /* For now.  This will move as more and more of haifa is converted
2883          to using the cfg code in flow.c.  */
2884       free_dominance_info (CDI_DOMINATORS);
2885     }
2886   RGN_BLOCKS (nr_regions) = RGN_BLOCKS (nr_regions - 1) +
2887     RGN_NR_BLOCKS (nr_regions - 1);
2888
2889
2890   if (CHECK_DEAD_NOTES)
2891     {
2892       blocks = sbitmap_alloc (last_basic_block);
2893       deaths_in_region = XNEWVEC (int, nr_regions);
2894       /* Remove all death notes from the subroutine.  */
2895       for (rgn = 0; rgn < nr_regions; rgn++)
2896         check_dead_notes1 (rgn, blocks);
2897
2898       sbitmap_free (blocks);
2899     }
2900   else
2901     count_or_remove_death_notes (NULL, 1);
2902 }
2903
2904 /* The one entry point in this file.  */
2905
2906 void
2907 schedule_insns (void)
2908 {
2909   sbitmap large_region_blocks, blocks;
2910   int rgn;
2911   int any_large_regions;
2912   basic_block bb;
2913
2914   /* Taking care of this degenerate case makes the rest of
2915      this code simpler.  */
2916   if (n_basic_blocks == NUM_FIXED_BLOCKS)
2917     return;
2918
2919   nr_inter = 0;
2920   nr_spec = 0;
2921
2922   /* We need current_sched_info in init_dependency_caches, which is
2923      invoked via sched_init.  */
2924   current_sched_info = &region_sched_info;
2925
2926   sched_init ();
2927
2928   min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE)
2929                     / 100);
2930
2931   init_regions ();
2932
2933   /* EBB_HEAD is a region-scope structure.  But we realloc it for
2934      each region to save time/memory/something else.  */
2935   ebb_head = 0;
2936   
2937   /* Schedule every region in the subroutine.  */
2938   for (rgn = 0; rgn < nr_regions; rgn++)
2939     schedule_region (rgn);
2940   
2941   free(ebb_head);
2942
2943   /* Update life analysis for the subroutine.  Do single block regions
2944      first so that we can verify that live_at_start didn't change.  Then
2945      do all other blocks.  */
2946   /* ??? There is an outside possibility that update_life_info, or more
2947      to the point propagate_block, could get called with nonzero flags
2948      more than once for one basic block.  This would be kinda bad if it
2949      were to happen, since REG_INFO would be accumulated twice for the
2950      block, and we'd have twice the REG_DEAD notes.
2951
2952      I'm fairly certain that this _shouldn't_ happen, since I don't think
2953      that live_at_start should change at region heads.  Not sure what the
2954      best way to test for this kind of thing...  */
2955
2956   if (current_sched_info->flags & DETACH_LIFE_INFO)
2957     /* this flag can be set either by the target or by ENABLE_CHECKING.  */
2958     attach_life_info ();
2959
2960   allocate_reg_life_data ();
2961
2962   any_large_regions = 0;
2963   large_region_blocks = sbitmap_alloc (last_basic_block);
2964   sbitmap_zero (large_region_blocks);
2965   FOR_EACH_BB (bb)
2966     SET_BIT (large_region_blocks, bb->index);
2967
2968   blocks = sbitmap_alloc (last_basic_block);
2969   sbitmap_zero (blocks);
2970
2971   /* Update life information.  For regions consisting of multiple blocks
2972      we've possibly done interblock scheduling that affects global liveness.
2973      For regions consisting of single blocks we need to do only local
2974      liveness.  */
2975   for (rgn = 0; rgn < nr_regions; rgn++)    
2976     if (RGN_NR_BLOCKS (rgn) > 1
2977         /* Or the only block of this region has been split.  */
2978         || RGN_HAS_REAL_EBB (rgn)
2979         /* New blocks (e.g. recovery blocks) should be processed
2980            as parts of large regions.  */
2981         || !glat_start[rgn_bb_table[RGN_BLOCKS (rgn)]])
2982       any_large_regions = 1;
2983     else
2984       {
2985         SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2986         RESET_BIT (large_region_blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2987       }
2988
2989   /* Don't update reg info after reload, since that affects
2990      regs_ever_live, which should not change after reload.  */
2991   update_life_info (blocks, UPDATE_LIFE_LOCAL,
2992                     (reload_completed ? PROP_DEATH_NOTES
2993                      : (PROP_DEATH_NOTES | PROP_REG_INFO)));
2994   if (any_large_regions)
2995     {
2996       update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL,
2997                         (reload_completed ? PROP_DEATH_NOTES
2998                          : (PROP_DEATH_NOTES | PROP_REG_INFO)));
2999
3000 #ifdef ENABLE_CHECKING
3001       check_reg_live (true);
3002 #endif
3003     }
3004
3005   if (CHECK_DEAD_NOTES)
3006     {
3007       /* Verify the counts of basic block notes in single basic block
3008          regions.  */
3009       for (rgn = 0; rgn < nr_regions; rgn++)
3010         if (RGN_NR_BLOCKS (rgn) == 1)
3011           {
3012             sbitmap_zero (blocks);
3013             SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
3014
3015             gcc_assert (deaths_in_region[rgn]
3016                         == count_or_remove_death_notes (blocks, 0));
3017           }
3018       free (deaths_in_region);
3019     }
3020
3021   /* Reposition the prologue and epilogue notes in case we moved the
3022      prologue/epilogue insns.  */
3023   if (reload_completed)
3024     reposition_prologue_and_epilogue_notes (get_insns ());
3025
3026   if (sched_verbose)
3027     {
3028       if (reload_completed == 0 && flag_schedule_interblock)
3029         {
3030           fprintf (sched_dump,
3031                    "\n;; Procedure interblock/speculative motions == %d/%d \n",
3032                    nr_inter, nr_spec);
3033         }
3034       else
3035         gcc_assert (nr_inter <= 0);
3036       fprintf (sched_dump, "\n\n");
3037     }
3038
3039   /* Clean up.  */
3040   free (rgn_table);
3041   free (rgn_bb_table);
3042   free (block_to_bb);
3043   free (containing_rgn);
3044
3045   sched_finish ();
3046
3047   sbitmap_free (blocks);
3048   sbitmap_free (large_region_blocks);
3049 }
3050
3051 /* INSN has been added to/removed from current region.  */
3052 static void
3053 add_remove_insn (rtx insn, int remove_p)
3054 {
3055   if (!remove_p)
3056     rgn_n_insns++;
3057   else
3058     rgn_n_insns--;
3059
3060   if (INSN_BB (insn) == target_bb)
3061     {
3062       if (!remove_p)
3063         target_n_insns++;
3064       else
3065         target_n_insns--;
3066     }
3067 }
3068
3069 /* Extend internal data structures.  */
3070 static void
3071 extend_regions (void)
3072 {
3073   rgn_table = XRESIZEVEC (region, rgn_table, n_basic_blocks);
3074   rgn_bb_table = XRESIZEVEC (int, rgn_bb_table, n_basic_blocks);
3075   block_to_bb = XRESIZEVEC (int, block_to_bb, last_basic_block);
3076   containing_rgn = XRESIZEVEC (int, containing_rgn, last_basic_block);
3077 }
3078
3079 /* BB was added to ebb after AFTER.  */
3080 static void
3081 add_block1 (basic_block bb, basic_block after)
3082 {
3083   extend_regions ();
3084
3085   if (after == 0 || after == EXIT_BLOCK_PTR)
3086     {
3087       int i;
3088       
3089       i = RGN_BLOCKS (nr_regions);
3090       /* I - first free position in rgn_bb_table.  */
3091
3092       rgn_bb_table[i] = bb->index;
3093       RGN_NR_BLOCKS (nr_regions) = 1;
3094       RGN_DONT_CALC_DEPS (nr_regions) = after == EXIT_BLOCK_PTR;
3095       RGN_HAS_REAL_EBB (nr_regions) = 0;
3096       CONTAINING_RGN (bb->index) = nr_regions;
3097       BLOCK_TO_BB (bb->index) = 0;
3098
3099       nr_regions++;
3100       
3101       RGN_BLOCKS (nr_regions) = i + 1;
3102
3103       if (CHECK_DEAD_NOTES)
3104         {
3105           sbitmap blocks = sbitmap_alloc (last_basic_block);
3106           deaths_in_region = xrealloc (deaths_in_region, nr_regions *
3107                                        sizeof (*deaths_in_region));
3108
3109           check_dead_notes1 (nr_regions - 1, blocks);
3110       
3111           sbitmap_free (blocks);
3112         }
3113     }
3114   else
3115     { 
3116       int i, pos;
3117
3118       /* We need to fix rgn_table, block_to_bb, containing_rgn
3119          and ebb_head.  */
3120
3121       BLOCK_TO_BB (bb->index) = BLOCK_TO_BB (after->index);
3122
3123       /* We extend ebb_head to one more position to
3124          easily find the last position of the last ebb in 
3125          the current region.  Thus, ebb_head[BLOCK_TO_BB (after) + 1]
3126          is _always_ valid for access.  */
3127
3128       i = BLOCK_TO_BB (after->index) + 1;
3129       pos = ebb_head[i] - 1;
3130       /* Now POS is the index of the last block in the region.  */
3131
3132       /* Find index of basic block AFTER.  */
3133       for (; rgn_bb_table[pos] != after->index; pos--);
3134
3135       pos++;
3136       gcc_assert (pos > ebb_head[i - 1]);
3137
3138       /* i - ebb right after "AFTER".  */
3139       /* ebb_head[i] - VALID.  */
3140
3141       /* Source position: ebb_head[i]
3142          Destination position: ebb_head[i] + 1
3143          Last position: 
3144            RGN_BLOCKS (nr_regions) - 1
3145          Number of elements to copy: (last_position) - (source_position) + 1
3146        */
3147       
3148       memmove (rgn_bb_table + pos + 1,
3149                rgn_bb_table + pos,
3150                ((RGN_BLOCKS (nr_regions) - 1) - (pos) + 1)
3151                * sizeof (*rgn_bb_table));
3152
3153       rgn_bb_table[pos] = bb->index;
3154       
3155       for (; i <= current_nr_blocks; i++)
3156         ebb_head [i]++;
3157
3158       i = CONTAINING_RGN (after->index);
3159       CONTAINING_RGN (bb->index) = i;
3160       
3161       RGN_HAS_REAL_EBB (i) = 1;
3162
3163       for (++i; i <= nr_regions; i++)
3164         RGN_BLOCKS (i)++;
3165
3166       /* We don't need to call check_dead_notes1 () because this new block
3167          is just a split of the old.  We don't want to count anything twice.  */
3168     }
3169 }
3170
3171 /* Fix internal data after interblock movement of jump instruction.
3172    For parameter meaning please refer to
3173    sched-int.h: struct sched_info: fix_recovery_cfg.  */
3174 static void
3175 fix_recovery_cfg (int bbi, int check_bbi, int check_bb_nexti)
3176 {
3177   int old_pos, new_pos, i;
3178
3179   BLOCK_TO_BB (check_bb_nexti) = BLOCK_TO_BB (bbi);
3180   
3181   for (old_pos = ebb_head[BLOCK_TO_BB (check_bbi) + 1] - 1;
3182        rgn_bb_table[old_pos] != check_bb_nexti;
3183        old_pos--);
3184   gcc_assert (old_pos > ebb_head[BLOCK_TO_BB (check_bbi)]);
3185
3186   for (new_pos = ebb_head[BLOCK_TO_BB (bbi) + 1] - 1;
3187        rgn_bb_table[new_pos] != bbi;
3188        new_pos--);
3189   new_pos++;
3190   gcc_assert (new_pos > ebb_head[BLOCK_TO_BB (bbi)]);
3191   
3192   gcc_assert (new_pos < old_pos);
3193
3194   memmove (rgn_bb_table + new_pos + 1,
3195            rgn_bb_table + new_pos,
3196            (old_pos - new_pos) * sizeof (*rgn_bb_table));
3197
3198   rgn_bb_table[new_pos] = check_bb_nexti;
3199
3200   for (i = BLOCK_TO_BB (bbi) + 1; i <= BLOCK_TO_BB (check_bbi); i++)
3201     ebb_head[i]++;
3202 }
3203
3204 /* Return next block in ebb chain.  For parameter meaning please refer to
3205    sched-int.h: struct sched_info: advance_target_bb.  */
3206 static basic_block
3207 advance_target_bb (basic_block bb, rtx insn)
3208 {
3209   if (insn)
3210     return 0;
3211
3212   gcc_assert (BLOCK_TO_BB (bb->index) == target_bb
3213               && BLOCK_TO_BB (bb->next_bb->index) == target_bb);
3214   return bb->next_bb;
3215 }
3216
3217 /* Count and remove death notes in region RGN, which consists of blocks
3218    with indecies in BLOCKS.  */
3219 static void
3220 check_dead_notes1 (int rgn, sbitmap blocks)
3221 {
3222   int b;
3223
3224   sbitmap_zero (blocks);
3225   for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
3226     SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]);
3227
3228   deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1);
3229 }
3230
3231 #ifdef ENABLE_CHECKING
3232 /* Return non zero, if BB is head or leaf (depending of LEAF_P) block in
3233    current region.  For more information please refer to
3234    sched-int.h: struct sched_info: region_head_or_leaf_p.  */
3235 static int
3236 region_head_or_leaf_p (basic_block bb, int leaf_p)
3237 {
3238   if (!leaf_p)    
3239     return bb->index == rgn_bb_table[RGN_BLOCKS (CONTAINING_RGN (bb->index))];
3240   else
3241     {
3242       int i;
3243       edge e;
3244       edge_iterator ei;
3245       
3246       i = CONTAINING_RGN (bb->index);
3247
3248       FOR_EACH_EDGE (e, ei, bb->succs)
3249         if (e->dest != EXIT_BLOCK_PTR
3250             && CONTAINING_RGN (e->dest->index) == i
3251             /* except self-loop.  */
3252             && e->dest != bb)
3253           return 0;
3254       
3255       return 1;
3256     }
3257 }
3258 #endif /* ENABLE_CHECKING  */
3259
3260 #endif
3261 \f
3262 static bool
3263 gate_handle_sched (void)
3264 {
3265 #ifdef INSN_SCHEDULING
3266   return flag_schedule_insns;
3267 #else
3268   return 0;
3269 #endif
3270 }
3271
3272 /* Run instruction scheduler.  */
3273 static unsigned int
3274 rest_of_handle_sched (void)
3275 {
3276 #ifdef INSN_SCHEDULING
3277   /* Do control and data sched analysis,
3278      and write some of the results to dump file.  */
3279
3280   schedule_insns ();
3281 #endif
3282   return 0;
3283 }
3284
3285 static bool
3286 gate_handle_sched2 (void)
3287 {
3288 #ifdef INSN_SCHEDULING
3289   return optimize > 0 && flag_schedule_insns_after_reload;
3290 #else
3291   return 0;
3292 #endif
3293 }
3294
3295 /* Run second scheduling pass after reload.  */
3296 static unsigned int
3297 rest_of_handle_sched2 (void)
3298 {
3299 #ifdef INSN_SCHEDULING
3300   /* Do control and data sched analysis again,
3301      and write some more of the results to dump file.  */
3302
3303   split_all_insns (1);
3304
3305   if (flag_sched2_use_superblocks || flag_sched2_use_traces)
3306     {
3307       schedule_ebbs ();
3308       /* No liveness updating code yet, but it should be easy to do.
3309          reg-stack recomputes the liveness when needed for now.  */
3310       count_or_remove_death_notes (NULL, 1);
3311       cleanup_cfg (CLEANUP_EXPENSIVE);
3312     }
3313   else
3314     schedule_insns ();
3315 #endif
3316   return 0;
3317 }
3318
3319 struct tree_opt_pass pass_sched =
3320 {
3321   "sched1",                             /* name */
3322   gate_handle_sched,                    /* gate */
3323   rest_of_handle_sched,                 /* execute */
3324   NULL,                                 /* sub */
3325   NULL,                                 /* next */
3326   0,                                    /* static_pass_number */
3327   TV_SCHED,                             /* tv_id */
3328   0,                                    /* properties_required */
3329   0,                                    /* properties_provided */
3330   0,                                    /* properties_destroyed */
3331   0,                                    /* todo_flags_start */
3332   TODO_dump_func |
3333   TODO_ggc_collect,                     /* todo_flags_finish */
3334   'S'                                   /* letter */
3335 };
3336
3337 struct tree_opt_pass pass_sched2 =
3338 {
3339   "sched2",                             /* name */
3340   gate_handle_sched2,                   /* gate */
3341   rest_of_handle_sched2,                /* execute */
3342   NULL,                                 /* sub */
3343   NULL,                                 /* next */
3344   0,                                    /* static_pass_number */
3345   TV_SCHED2,                            /* tv_id */
3346   0,                                    /* properties_required */
3347   0,                                    /* properties_provided */
3348   0,                                    /* properties_destroyed */
3349   0,                                    /* todo_flags_start */
3350   TODO_dump_func |
3351   TODO_ggc_collect,                     /* todo_flags_finish */
3352   'R'                                   /* letter */
3353 };
3354