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
7This file is part of GCC.
8
9GCC is free software; you can redistribute it and/or modify it under
10the terms of the GNU General Public License as published by the Free
11Software Foundation; either version 2, or (at your option) any later
12version.
13
14GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15WARRANTY; without even the implied warranty of MERCHANTABILITY or
16FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17for more details.
18
19You should have received a copy of the GNU General Public License
20along with GCC; see the file COPYING.  If not, write to the Free
21Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
2202110-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
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.  */
89static int nr_inter, nr_spec;
90
91static int is_cfg_nonregular (void);
92static 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.  */
97typedef struct
98{
99  int rgn_nr_blocks;		/* Number of blocks in region.  */
100  int rgn_blocks;		/* cblocks in the region (actually index in rgn_bb_table).  */
101}
102region;
103
104/* Number of regions in the procedure.  */
105static int nr_regions;
106
107/* Table of region descriptions.  */
108static region *rgn_table;
109
110/* Array of lists of regions' blocks.  */
111static int *rgn_bb_table;
112
113/* Topological order of blocks in the region (if b2 is reachable from
114   b1, block_to_bb[b2] > block_to_bb[b1]).  Note: A basic block is
115   always referred to by either block or b, while its topological
116   order name (in the region) is referred to by bb.  */
117static int *block_to_bb;
118
119/* The number of the region containing a block.  */
120static int *containing_rgn;
121
122#define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
123#define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
124#define BLOCK_TO_BB(block) (block_to_bb[block])
125#define CONTAINING_RGN(block) (containing_rgn[block])
126
127void debug_regions (void);
128static void find_single_block_region (void);
129static void find_rgns (void);
130static bool too_large (int, int *, int *);
131
132extern void debug_live (int, int);
133
134/* Blocks of the current region being scheduled.  */
135static int current_nr_blocks;
136static int current_blocks;
137
138/* The mapping from bb to block.  */
139#define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
140
141/* Target info declarations.
142
143   The block currently being scheduled is referred to as the "target" block,
144   while other blocks in the region from which insns can be moved to the
145   target are called "source" blocks.  The candidate structure holds info
146   about such sources: are they valid?  Speculative?  Etc.  */
147typedef struct
148{
149  basic_block *first_member;
150  int nr_members;
151}
152bblst;
153
154typedef struct
155{
156  char is_valid;
157  char is_speculative;
158  int src_prob;
159  bblst split_bbs;
160  bblst update_bbs;
161}
162candidate;
163
164static candidate *candidate_table;
165
166/* A speculative motion requires checking live information on the path
167   from 'source' to 'target'.  The split blocks are those to be checked.
168   After a speculative motion, live information should be modified in
169   the 'update' blocks.
170
171   Lists of split and update blocks for each candidate of the current
172   target are in array bblst_table.  */
173static basic_block *bblst_table;
174static int bblst_size, bblst_last;
175
176#define IS_VALID(src) ( candidate_table[src].is_valid )
177#define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
178#define SRC_PROB(src) ( candidate_table[src].src_prob )
179
180/* The bb being currently scheduled.  */
181static int target_bb;
182
183/* List of edges.  */
184typedef struct
185{
186  edge *first_member;
187  int nr_members;
188}
189edgelst;
190
191static edge *edgelst_table;
192static int edgelst_last;
193
194static void extract_edgelst (sbitmap, edgelst *);
195
196
197/* Target info functions.  */
198static void split_edges (int, int, edgelst *);
199static void compute_trg_info (int);
200void debug_candidate (int);
201void debug_candidates (int);
202
203/* Dominators array: dom[i] contains the sbitmap of dominators of
204   bb i in the region.  */
205static sbitmap *dom;
206
207/* bb 0 is the only region entry.  */
208#define IS_RGN_ENTRY(bb) (!bb)
209
210/* Is bb_src dominated by bb_trg.  */
211#define IS_DOMINATED(bb_src, bb_trg)                                 \
212( TEST_BIT (dom[bb_src], bb_trg) )
213
214/* Probability: Prob[i] is a float in [0, 1] which is the probability
215   of bb i relative to the region entry.  */
216static float *prob;
217
218/* The probability of bb_src, relative to bb_trg.  Note, that while the
219   'prob[bb]' is a float in [0, 1], this macro returns an integer
220   in [0, 100].  */
221#define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
222						      prob[bb_trg])))
223
224/* Bit-set of edges, where bit i stands for edge i.  */
225typedef sbitmap edgeset;
226
227/* Number of edges in the region.  */
228static int rgn_nr_edges;
229
230/* Array of size rgn_nr_edges.  */
231static edge *rgn_edges;
232
233/* Mapping from each edge in the graph to its number in the rgn.  */
234#define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
235#define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
236
237/* The split edges of a source bb is different for each target
238   bb.  In order to compute this efficiently, the 'potential-split edges'
239   are computed for each bb prior to scheduling a region.  This is actually
240   the split edges of each bb relative to the region entry.
241
242   pot_split[bb] is the set of potential split edges of bb.  */
243static edgeset *pot_split;
244
245/* For every bb, a set of its ancestor edges.  */
246static edgeset *ancestor_edges;
247
248static void compute_dom_prob_ps (int);
249
250#define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
251#define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
252#define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
253
254/* Speculative scheduling functions.  */
255static int check_live_1 (int, rtx);
256static void update_live_1 (int, rtx);
257static int check_live (rtx, int);
258static void update_live (rtx, int);
259static void set_spec_fed (rtx);
260static int is_pfree (rtx, int, int);
261static int find_conditional_protection (rtx, int);
262static int is_conditionally_protected (rtx, int, int);
263static int is_prisky (rtx, int, int);
264static int is_exception_free (rtx, int, int);
265
266static bool sets_likely_spilled (rtx);
267static void sets_likely_spilled_1 (rtx, rtx, void *);
268static void add_branch_dependences (rtx, rtx);
269static void compute_block_backward_dependences (int);
270void debug_dependencies (void);
271
272static void init_regions (void);
273static void schedule_region (int);
274static rtx concat_INSN_LIST (rtx, rtx);
275static void concat_insn_mem_list (rtx, rtx, rtx *, rtx *);
276static void propagate_deps (int, struct deps *);
277static void free_pending_lists (void);
278
279/* Functions for construction of the control flow graph.  */
280
281/* Return 1 if control flow graph should not be constructed, 0 otherwise.
282
283   We decide not to build the control flow graph if there is possibly more
284   than one entry to the function, if computed branches exist, if we
285   have nonlocal gotos, or if we have an unreachable loop.  */
286
287static int
288is_cfg_nonregular (void)
289{
290  basic_block b;
291  rtx insn;
292
293  /* If we have a label that could be the target of a nonlocal goto, then
294     the cfg is not well structured.  */
295  if (nonlocal_goto_handler_labels)
296    return 1;
297
298  /* If we have any forced labels, then the cfg is not well structured.  */
299  if (forced_labels)
300    return 1;
301
302  /* If we have exception handlers, then we consider the cfg not well
303     structured.  ?!?  We should be able to handle this now that flow.c
304     computes an accurate cfg for EH.  */
305  if (current_function_has_exception_handlers ())
306    return 1;
307
308  /* If we have non-jumping insns which refer to labels, then we consider
309     the cfg not well structured.  */
310  FOR_EACH_BB (b)
311    FOR_BB_INSNS (b, insn)
312      {
313	/* Check for labels referred by non-jump insns.  */
314	if (NONJUMP_INSN_P (insn) || CALL_P (insn))
315	  {
316	    rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
317	    if (note
318		&& ! (JUMP_P (NEXT_INSN (insn))
319		      && find_reg_note (NEXT_INSN (insn), REG_LABEL,
320					XEXP (note, 0))))
321	      return 1;
322	  }
323	/* If this function has a computed jump, then we consider the cfg
324	   not well structured.  */
325	else if (JUMP_P (insn) && computed_jump_p (insn))
326	  return 1;
327      }
328
329  /* Unreachable loops with more than one basic block are detected
330     during the DFS traversal in find_rgns.
331
332     Unreachable loops with a single block are detected here.  This
333     test is redundant with the one in find_rgns, but it's much
334     cheaper to go ahead and catch the trivial case here.  */
335  FOR_EACH_BB (b)
336    {
337      if (EDGE_COUNT (b->preds) == 0
338	  || (single_pred_p (b)
339	      && single_pred (b) == b))
340	return 1;
341    }
342
343  /* All the tests passed.  Consider the cfg well structured.  */
344  return 0;
345}
346
347/* Extract list of edges from a bitmap containing EDGE_TO_BIT bits.  */
348
349static void
350extract_edgelst (sbitmap set, edgelst *el)
351{
352  unsigned int i = 0;
353  sbitmap_iterator sbi;
354
355  /* edgelst table space is reused in each call to extract_edgelst.  */
356  edgelst_last = 0;
357
358  el->first_member = &edgelst_table[edgelst_last];
359  el->nr_members = 0;
360
361  /* Iterate over each word in the bitset.  */
362  EXECUTE_IF_SET_IN_SBITMAP (set, 0, i, sbi)
363    {
364      edgelst_table[edgelst_last++] = rgn_edges[i];
365      el->nr_members++;
366    }
367}
368
369/* Functions for the construction of regions.  */
370
371/* Print the regions, for debugging purposes.  Callable from debugger.  */
372
373void
374debug_regions (void)
375{
376  int rgn, bb;
377
378  fprintf (sched_dump, "\n;;   ------------ REGIONS ----------\n\n");
379  for (rgn = 0; rgn < nr_regions; rgn++)
380    {
381      fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
382	       rgn_table[rgn].rgn_nr_blocks);
383      fprintf (sched_dump, ";;\tbb/block: ");
384
385      for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
386	{
387	  current_blocks = RGN_BLOCKS (rgn);
388
389	  gcc_assert (bb == BLOCK_TO_BB (BB_TO_BLOCK (bb)));
390	  fprintf (sched_dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
391	}
392
393      fprintf (sched_dump, "\n\n");
394    }
395}
396
397/* Build a single block region for each basic block in the function.
398   This allows for using the same code for interblock and basic block
399   scheduling.  */
400
401static void
402find_single_block_region (void)
403{
404  basic_block bb;
405
406  nr_regions = 0;
407
408  FOR_EACH_BB (bb)
409    {
410      rgn_bb_table[nr_regions] = bb->index;
411      RGN_NR_BLOCKS (nr_regions) = 1;
412      RGN_BLOCKS (nr_regions) = nr_regions;
413      CONTAINING_RGN (bb->index) = nr_regions;
414      BLOCK_TO_BB (bb->index) = 0;
415      nr_regions++;
416    }
417}
418
419/* Update number of blocks and the estimate for number of insns
420   in the region.  Return true if the region is "too large" for interblock
421   scheduling (compile time considerations).  */
422
423static bool
424too_large (int block, int *num_bbs, int *num_insns)
425{
426  (*num_bbs)++;
427  (*num_insns) += (INSN_LUID (BB_END (BASIC_BLOCK (block)))
428		   - INSN_LUID (BB_HEAD (BASIC_BLOCK (block))));
429
430  return ((*num_bbs > PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS))
431	  || (*num_insns > PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS)));
432}
433
434/* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
435   is still an inner loop.  Put in max_hdr[blk] the header of the most inner
436   loop containing blk.  */
437#define UPDATE_LOOP_RELATIONS(blk, hdr)		\
438{						\
439  if (max_hdr[blk] == -1)			\
440    max_hdr[blk] = hdr;				\
441  else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr])	\
442    RESET_BIT (inner, hdr);			\
443  else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr])	\
444    {						\
445      RESET_BIT (inner,max_hdr[blk]);		\
446      max_hdr[blk] = hdr;			\
447    }						\
448}
449
450/* Find regions for interblock scheduling.
451
452   A region for scheduling can be:
453
454     * A loop-free procedure, or
455
456     * A reducible inner loop, or
457
458     * A basic block not contained in any other region.
459
460   ?!? In theory we could build other regions based on extended basic
461   blocks or reverse extended basic blocks.  Is it worth the trouble?
462
463   Loop blocks that form a region are put into the region's block list
464   in topological order.
465
466   This procedure stores its results into the following global (ick) variables
467
468     * rgn_nr
469     * rgn_table
470     * rgn_bb_table
471     * block_to_bb
472     * containing region
473
474   We use dominator relationships to avoid making regions out of non-reducible
475   loops.
476
477   This procedure needs to be converted to work on pred/succ lists instead
478   of edge tables.  That would simplify it somewhat.  */
479
480static void
481find_rgns (void)
482{
483  int *max_hdr, *dfs_nr, *degree;
484  char no_loops = 1;
485  int node, child, loop_head, i, head, tail;
486  int count = 0, sp, idx = 0;
487  edge_iterator current_edge;
488  edge_iterator *stack;
489  int num_bbs, num_insns, unreachable;
490  int too_large_failure;
491  basic_block bb;
492
493  /* Note if a block is a natural loop header.  */
494  sbitmap header;
495
496  /* Note if a block is a natural inner loop header.  */
497  sbitmap inner;
498
499  /* Note if a block is in the block queue.  */
500  sbitmap in_queue;
501
502  /* Note if a block is in the block queue.  */
503  sbitmap in_stack;
504
505  /* Perform a DFS traversal of the cfg.  Identify loop headers, inner loops
506     and a mapping from block to its loop header (if the block is contained
507     in a loop, else -1).
508
509     Store results in HEADER, INNER, and MAX_HDR respectively, these will
510     be used as inputs to the second traversal.
511
512     STACK, SP and DFS_NR are only used during the first traversal.  */
513
514  /* Allocate and initialize variables for the first traversal.  */
515  max_hdr = xmalloc (last_basic_block * sizeof (int));
516  dfs_nr = xcalloc (last_basic_block, sizeof (int));
517  stack = xmalloc (n_edges * sizeof (edge_iterator));
518
519  inner = sbitmap_alloc (last_basic_block);
520  sbitmap_ones (inner);
521
522  header = sbitmap_alloc (last_basic_block);
523  sbitmap_zero (header);
524
525  in_queue = sbitmap_alloc (last_basic_block);
526  sbitmap_zero (in_queue);
527
528  in_stack = sbitmap_alloc (last_basic_block);
529  sbitmap_zero (in_stack);
530
531  for (i = 0; i < last_basic_block; i++)
532    max_hdr[i] = -1;
533
534  #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
535  #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
536
537  /* DFS traversal to find inner loops in the cfg.  */
538
539  current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR)->succs);
540  sp = -1;
541
542  while (1)
543    {
544      if (EDGE_PASSED (current_edge))
545	{
546	  /* We have reached a leaf node or a node that was already
547	     processed.  Pop edges off the stack until we find
548	     an edge that has not yet been processed.  */
549	  while (sp >= 0 && EDGE_PASSED (current_edge))
550	    {
551	      /* Pop entry off the stack.  */
552	      current_edge = stack[sp--];
553	      node = ei_edge (current_edge)->src->index;
554	      gcc_assert (node != ENTRY_BLOCK);
555	      child = ei_edge (current_edge)->dest->index;
556	      gcc_assert (child != EXIT_BLOCK);
557	      RESET_BIT (in_stack, child);
558	      if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
559		UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
560	      ei_next (&current_edge);
561	    }
562
563	  /* See if have finished the DFS tree traversal.  */
564	  if (sp < 0 && EDGE_PASSED (current_edge))
565	    break;
566
567	  /* Nope, continue the traversal with the popped node.  */
568	  continue;
569	}
570
571      /* Process a node.  */
572      node = ei_edge (current_edge)->src->index;
573      gcc_assert (node != ENTRY_BLOCK);
574      SET_BIT (in_stack, node);
575      dfs_nr[node] = ++count;
576
577      /* We don't traverse to the exit block.  */
578      child = ei_edge (current_edge)->dest->index;
579      if (child == EXIT_BLOCK)
580	{
581	  SET_EDGE_PASSED (current_edge);
582	  ei_next (&current_edge);
583	  continue;
584	}
585
586      /* If the successor is in the stack, then we've found a loop.
587	 Mark the loop, if it is not a natural loop, then it will
588	 be rejected during the second traversal.  */
589      if (TEST_BIT (in_stack, child))
590	{
591	  no_loops = 0;
592	  SET_BIT (header, child);
593	  UPDATE_LOOP_RELATIONS (node, child);
594	  SET_EDGE_PASSED (current_edge);
595	  ei_next (&current_edge);
596	  continue;
597	}
598
599      /* If the child was already visited, then there is no need to visit
600	 it again.  Just update the loop relationships and restart
601	 with a new edge.  */
602      if (dfs_nr[child])
603	{
604	  if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
605	    UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
606	  SET_EDGE_PASSED (current_edge);
607	  ei_next (&current_edge);
608	  continue;
609	}
610
611      /* Push an entry on the stack and continue DFS traversal.  */
612      stack[++sp] = current_edge;
613      SET_EDGE_PASSED (current_edge);
614      current_edge = ei_start (ei_edge (current_edge)->dest->succs);
615    }
616
617  /* Reset ->aux field used by EDGE_PASSED.  */
618  FOR_ALL_BB (bb)
619    {
620      edge_iterator ei;
621      edge e;
622      FOR_EACH_EDGE (e, ei, bb->succs)
623	e->aux = NULL;
624    }
625
626
627  /* Another check for unreachable blocks.  The earlier test in
628     is_cfg_nonregular only finds unreachable blocks that do not
629     form a loop.
630
631     The DFS traversal will mark every block that is reachable from
632     the entry node by placing a nonzero value in dfs_nr.  Thus if
633     dfs_nr is zero for any block, then it must be unreachable.  */
634  unreachable = 0;
635  FOR_EACH_BB (bb)
636    if (dfs_nr[bb->index] == 0)
637      {
638	unreachable = 1;
639	break;
640      }
641
642  /* Gross.  To avoid wasting memory, the second pass uses the dfs_nr array
643     to hold degree counts.  */
644  degree = dfs_nr;
645
646  FOR_EACH_BB (bb)
647    degree[bb->index] = EDGE_COUNT (bb->preds);
648
649  /* Do not perform region scheduling if there are any unreachable
650     blocks.  */
651  if (!unreachable)
652    {
653      int *queue;
654
655      if (no_loops)
656	SET_BIT (header, 0);
657
658      /* Second traversal:find reducible inner loops and topologically sort
659	 block of each region.  */
660
661      queue = xmalloc (n_basic_blocks * sizeof (int));
662
663      /* Find blocks which are inner loop headers.  We still have non-reducible
664	 loops to consider at this point.  */
665      FOR_EACH_BB (bb)
666	{
667	  if (TEST_BIT (header, bb->index) && TEST_BIT (inner, bb->index))
668	    {
669	      edge e;
670	      edge_iterator ei;
671	      basic_block jbb;
672
673	      /* Now check that the loop is reducible.  We do this separate
674		 from finding inner loops so that we do not find a reducible
675		 loop which contains an inner non-reducible loop.
676
677		 A simple way to find reducible/natural loops is to verify
678		 that each block in the loop is dominated by the loop
679		 header.
680
681		 If there exists a block that is not dominated by the loop
682		 header, then the block is reachable from outside the loop
683		 and thus the loop is not a natural loop.  */
684	      FOR_EACH_BB (jbb)
685		{
686		  /* First identify blocks in the loop, except for the loop
687		     entry block.  */
688		  if (bb->index == max_hdr[jbb->index] && bb != jbb)
689		    {
690		      /* Now verify that the block is dominated by the loop
691			 header.  */
692		      if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))
693			break;
694		    }
695		}
696
697	      /* If we exited the loop early, then I is the header of
698		 a non-reducible loop and we should quit processing it
699		 now.  */
700	      if (jbb != EXIT_BLOCK_PTR)
701		continue;
702
703	      /* I is a header of an inner loop, or block 0 in a subroutine
704		 with no loops at all.  */
705	      head = tail = -1;
706	      too_large_failure = 0;
707	      loop_head = max_hdr[bb->index];
708
709	      /* Decrease degree of all I's successors for topological
710		 ordering.  */
711	      FOR_EACH_EDGE (e, ei, bb->succs)
712		if (e->dest != EXIT_BLOCK_PTR)
713		  --degree[e->dest->index];
714
715	      /* Estimate # insns, and count # blocks in the region.  */
716	      num_bbs = 1;
717	      num_insns = (INSN_LUID (BB_END (bb))
718			   - INSN_LUID (BB_HEAD (bb)));
719
720	      /* Find all loop latches (blocks with back edges to the loop
721		 header) or all the leaf blocks in the cfg has no loops.
722
723		 Place those blocks into the queue.  */
724	      if (no_loops)
725		{
726		  FOR_EACH_BB (jbb)
727		    /* Leaf nodes have only a single successor which must
728		       be EXIT_BLOCK.  */
729		    if (single_succ_p (jbb)
730			&& single_succ (jbb) == EXIT_BLOCK_PTR)
731		      {
732			queue[++tail] = jbb->index;
733			SET_BIT (in_queue, jbb->index);
734
735			if (too_large (jbb->index, &num_bbs, &num_insns))
736			  {
737			    too_large_failure = 1;
738			    break;
739			  }
740		      }
741		}
742	      else
743		{
744		  edge e;
745
746		  FOR_EACH_EDGE (e, ei, bb->preds)
747		    {
748		      if (e->src == ENTRY_BLOCK_PTR)
749			continue;
750
751		      node = e->src->index;
752
753		      if (max_hdr[node] == loop_head && node != bb->index)
754			{
755			  /* This is a loop latch.  */
756			  queue[++tail] = node;
757			  SET_BIT (in_queue, node);
758
759			  if (too_large (node, &num_bbs, &num_insns))
760			    {
761			      too_large_failure = 1;
762			      break;
763			    }
764			}
765		    }
766		}
767
768	      /* Now add all the blocks in the loop to the queue.
769
770	     We know the loop is a natural loop; however the algorithm
771	     above will not always mark certain blocks as being in the
772	     loop.  Consider:
773		node   children
774		 a	  b,c
775		 b	  c
776		 c	  a,d
777		 d	  b
778
779	     The algorithm in the DFS traversal may not mark B & D as part
780	     of the loop (i.e. they will not have max_hdr set to A).
781
782	     We know they can not be loop latches (else they would have
783	     had max_hdr set since they'd have a backedge to a dominator
784	     block).  So we don't need them on the initial queue.
785
786	     We know they are part of the loop because they are dominated
787	     by the loop header and can be reached by a backwards walk of
788	     the edges starting with nodes on the initial queue.
789
790	     It is safe and desirable to include those nodes in the
791	     loop/scheduling region.  To do so we would need to decrease
792	     the degree of a node if it is the target of a backedge
793	     within the loop itself as the node is placed in the queue.
794
795	     We do not do this because I'm not sure that the actual
796	     scheduling code will properly handle this case. ?!? */
797
798	      while (head < tail && !too_large_failure)
799		{
800		  edge e;
801		  child = queue[++head];
802
803		  FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->preds)
804		    {
805		      node = e->src->index;
806
807		      /* See discussion above about nodes not marked as in
808			 this loop during the initial DFS traversal.  */
809		      if (e->src == ENTRY_BLOCK_PTR
810			  || max_hdr[node] != loop_head)
811			{
812			  tail = -1;
813			  break;
814			}
815		      else if (!TEST_BIT (in_queue, node) && node != bb->index)
816			{
817			  queue[++tail] = node;
818			  SET_BIT (in_queue, node);
819
820			  if (too_large (node, &num_bbs, &num_insns))
821			    {
822			      too_large_failure = 1;
823			      break;
824			    }
825			}
826		    }
827		}
828
829	      if (tail >= 0 && !too_large_failure)
830		{
831		  /* Place the loop header into list of region blocks.  */
832		  degree[bb->index] = -1;
833		  rgn_bb_table[idx] = bb->index;
834		  RGN_NR_BLOCKS (nr_regions) = num_bbs;
835		  RGN_BLOCKS (nr_regions) = idx++;
836		  CONTAINING_RGN (bb->index) = nr_regions;
837		  BLOCK_TO_BB (bb->index) = count = 0;
838
839		  /* Remove blocks from queue[] when their in degree
840		     becomes zero.  Repeat until no blocks are left on the
841		     list.  This produces a topological list of blocks in
842		     the region.  */
843		  while (tail >= 0)
844		    {
845		      if (head < 0)
846			head = tail;
847		      child = queue[head];
848		      if (degree[child] == 0)
849			{
850			  edge e;
851
852			  degree[child] = -1;
853			  rgn_bb_table[idx++] = child;
854			  BLOCK_TO_BB (child) = ++count;
855			  CONTAINING_RGN (child) = nr_regions;
856			  queue[head] = queue[tail--];
857
858			  FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->succs)
859			    if (e->dest != EXIT_BLOCK_PTR)
860			      --degree[e->dest->index];
861			}
862		      else
863			--head;
864		    }
865		  ++nr_regions;
866		}
867	    }
868	}
869      free (queue);
870    }
871
872  /* Any block that did not end up in a region is placed into a region
873     by itself.  */
874  FOR_EACH_BB (bb)
875    if (degree[bb->index] >= 0)
876      {
877	rgn_bb_table[idx] = bb->index;
878	RGN_NR_BLOCKS (nr_regions) = 1;
879	RGN_BLOCKS (nr_regions) = idx++;
880	CONTAINING_RGN (bb->index) = nr_regions++;
881	BLOCK_TO_BB (bb->index) = 0;
882      }
883
884  free (max_hdr);
885  free (dfs_nr);
886  free (stack);
887  sbitmap_free (header);
888  sbitmap_free (inner);
889  sbitmap_free (in_queue);
890  sbitmap_free (in_stack);
891}
892
893/* Functions for regions scheduling information.  */
894
895/* Compute dominators, probability, and potential-split-edges of bb.
896   Assume that these values were already computed for bb's predecessors.  */
897
898static void
899compute_dom_prob_ps (int bb)
900{
901  int pred_bb;
902  int nr_out_edges, nr_rgn_out_edges;
903  edge_iterator in_ei, out_ei;
904  edge in_edge, out_edge;
905
906  prob[bb] = 0.0;
907  if (IS_RGN_ENTRY (bb))
908    {
909      SET_BIT (dom[bb], 0);
910      prob[bb] = 1.0;
911      return;
912    }
913
914  /* Initialize dom[bb] to '111..1'.  */
915  sbitmap_ones (dom[bb]);
916
917  FOR_EACH_EDGE (in_edge, in_ei, BASIC_BLOCK (BB_TO_BLOCK (bb))->preds)
918    {
919      if (in_edge->src == ENTRY_BLOCK_PTR)
920	continue;
921
922      pred_bb = BLOCK_TO_BB (in_edge->src->index);
923      sbitmap_a_and_b (dom[bb], dom[bb], dom[pred_bb]);
924      sbitmap_a_or_b (ancestor_edges[bb],
925		      ancestor_edges[bb], ancestor_edges[pred_bb]);
926
927      SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
928
929      sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
930
931      nr_out_edges = 0;
932      nr_rgn_out_edges = 0;
933
934      FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
935	{
936	  ++nr_out_edges;
937
938	  /* The successor doesn't belong in the region?  */
939	  if (out_edge->dest != EXIT_BLOCK_PTR
940	      && CONTAINING_RGN (out_edge->dest->index)
941		 != CONTAINING_RGN (BB_TO_BLOCK (bb)))
942	    ++nr_rgn_out_edges;
943
944	  SET_BIT (pot_split[bb], EDGE_TO_BIT (out_edge));
945	}
946
947      /* Now nr_rgn_out_edges is the number of region-exit edges from
948         pred, and nr_out_edges will be the number of pred out edges
949         not leaving the region.  */
950      nr_out_edges -= nr_rgn_out_edges;
951      if (nr_rgn_out_edges > 0)
952	prob[bb] += 0.9 * prob[pred_bb] / nr_out_edges;
953      else
954	prob[bb] += prob[pred_bb] / nr_out_edges;
955    }
956
957  SET_BIT (dom[bb], bb);
958  sbitmap_difference (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
959
960  if (sched_verbose >= 2)
961    fprintf (sched_dump, ";;  bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
962	     (int) (100.0 * prob[bb]));
963}
964
965/* Functions for target info.  */
966
967/* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
968   Note that bb_trg dominates bb_src.  */
969
970static void
971split_edges (int bb_src, int bb_trg, edgelst *bl)
972{
973  sbitmap src = sbitmap_alloc (pot_split[bb_src]->n_bits);
974  sbitmap_copy (src, pot_split[bb_src]);
975
976  sbitmap_difference (src, src, pot_split[bb_trg]);
977  extract_edgelst (src, bl);
978  sbitmap_free (src);
979}
980
981/* Find the valid candidate-source-blocks for the target block TRG, compute
982   their probability, and check if they are speculative or not.
983   For speculative sources, compute their update-blocks and split-blocks.  */
984
985static void
986compute_trg_info (int trg)
987{
988  candidate *sp;
989  edgelst el;
990  int i, j, k, update_idx;
991  basic_block block;
992  sbitmap visited;
993  edge_iterator ei;
994  edge e;
995
996  /* Define some of the fields for the target bb as well.  */
997  sp = candidate_table + trg;
998  sp->is_valid = 1;
999  sp->is_speculative = 0;
1000  sp->src_prob = 100;
1001
1002  visited = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
1003
1004  for (i = trg + 1; i < current_nr_blocks; i++)
1005    {
1006      sp = candidate_table + i;
1007
1008      sp->is_valid = IS_DOMINATED (i, trg);
1009      if (sp->is_valid)
1010	{
1011	  sp->src_prob = GET_SRC_PROB (i, trg);
1012	  sp->is_valid = (sp->src_prob >= PARAM_VALUE (PARAM_MIN_SPEC_PROB));
1013	}
1014
1015      if (sp->is_valid)
1016	{
1017	  split_edges (i, trg, &el);
1018	  sp->is_speculative = (el.nr_members) ? 1 : 0;
1019	  if (sp->is_speculative && !flag_schedule_speculative)
1020	    sp->is_valid = 0;
1021	}
1022
1023      if (sp->is_valid)
1024	{
1025	  /* Compute split blocks and store them in bblst_table.
1026	     The TO block of every split edge is a split block.  */
1027	  sp->split_bbs.first_member = &bblst_table[bblst_last];
1028	  sp->split_bbs.nr_members = el.nr_members;
1029	  for (j = 0; j < el.nr_members; bblst_last++, j++)
1030	    bblst_table[bblst_last] = el.first_member[j]->dest;
1031	  sp->update_bbs.first_member = &bblst_table[bblst_last];
1032
1033	  /* Compute update blocks and store them in bblst_table.
1034	     For every split edge, look at the FROM block, and check
1035	     all out edges.  For each out edge that is not a split edge,
1036	     add the TO block to the update block list.  This list can end
1037	     up with a lot of duplicates.  We need to weed them out to avoid
1038	     overrunning the end of the bblst_table.  */
1039
1040	  update_idx = 0;
1041	  sbitmap_zero (visited);
1042	  for (j = 0; j < el.nr_members; j++)
1043	    {
1044	      block = el.first_member[j]->src;
1045	      FOR_EACH_EDGE (e, ei, block->succs)
1046		{
1047		  if (!TEST_BIT (visited,
1048				 e->dest->index - (INVALID_BLOCK + 1)))
1049		    {
1050		      for (k = 0; k < el.nr_members; k++)
1051			if (e == el.first_member[k])
1052			  break;
1053
1054		      if (k >= el.nr_members)
1055			{
1056			  bblst_table[bblst_last++] = e->dest;
1057			  SET_BIT (visited,
1058				   e->dest->index - (INVALID_BLOCK + 1));
1059			  update_idx++;
1060			}
1061		    }
1062		}
1063	    }
1064	  sp->update_bbs.nr_members = update_idx;
1065
1066	  /* Make sure we didn't overrun the end of bblst_table.  */
1067	  gcc_assert (bblst_last <= bblst_size);
1068	}
1069      else
1070	{
1071	  sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1072
1073	  sp->is_speculative = 0;
1074	  sp->src_prob = 0;
1075	}
1076    }
1077
1078  sbitmap_free (visited);
1079}
1080
1081/* Print candidates info, for debugging purposes.  Callable from debugger.  */
1082
1083void
1084debug_candidate (int i)
1085{
1086  if (!candidate_table[i].is_valid)
1087    return;
1088
1089  if (candidate_table[i].is_speculative)
1090    {
1091      int j;
1092      fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1093
1094      fprintf (sched_dump, "split path: ");
1095      for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1096	{
1097	  int b = candidate_table[i].split_bbs.first_member[j]->index;
1098
1099	  fprintf (sched_dump, " %d ", b);
1100	}
1101      fprintf (sched_dump, "\n");
1102
1103      fprintf (sched_dump, "update path: ");
1104      for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
1105	{
1106	  int b = candidate_table[i].update_bbs.first_member[j]->index;
1107
1108	  fprintf (sched_dump, " %d ", b);
1109	}
1110      fprintf (sched_dump, "\n");
1111    }
1112  else
1113    {
1114      fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
1115    }
1116}
1117
1118/* Print candidates info, for debugging purposes.  Callable from debugger.  */
1119
1120void
1121debug_candidates (int trg)
1122{
1123  int i;
1124
1125  fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
1126	   BB_TO_BLOCK (trg), trg);
1127  for (i = trg + 1; i < current_nr_blocks; i++)
1128    debug_candidate (i);
1129}
1130
1131/* Functions for speculative scheduling.  */
1132
1133/* Return 0 if x is a set of a register alive in the beginning of one
1134   of the split-blocks of src, otherwise return 1.  */
1135
1136static int
1137check_live_1 (int src, rtx x)
1138{
1139  int i;
1140  int regno;
1141  rtx reg = SET_DEST (x);
1142
1143  if (reg == 0)
1144    return 1;
1145
1146  while (GET_CODE (reg) == SUBREG
1147	 || GET_CODE (reg) == ZERO_EXTRACT
1148	 || GET_CODE (reg) == STRICT_LOW_PART)
1149    reg = XEXP (reg, 0);
1150
1151  if (GET_CODE (reg) == PARALLEL)
1152    {
1153      int i;
1154
1155      for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1156	if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1157	  if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
1158	    return 1;
1159
1160      return 0;
1161    }
1162
1163  if (!REG_P (reg))
1164    return 1;
1165
1166  regno = REGNO (reg);
1167
1168  if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1169    {
1170      /* Global registers are assumed live.  */
1171      return 0;
1172    }
1173  else
1174    {
1175      if (regno < FIRST_PSEUDO_REGISTER)
1176	{
1177	  /* Check for hard registers.  */
1178	  int j = hard_regno_nregs[regno][GET_MODE (reg)];
1179	  while (--j >= 0)
1180	    {
1181	      for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1182		{
1183		  basic_block b = candidate_table[src].split_bbs.first_member[i];
1184
1185		  if (REGNO_REG_SET_P (b->il.rtl->global_live_at_start,
1186				       regno + j))
1187		    {
1188		      return 0;
1189		    }
1190		}
1191	    }
1192	}
1193      else
1194	{
1195	  /* Check for pseudo registers.  */
1196	  for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1197	    {
1198	      basic_block b = candidate_table[src].split_bbs.first_member[i];
1199
1200	      if (REGNO_REG_SET_P (b->il.rtl->global_live_at_start, regno))
1201		{
1202		  return 0;
1203		}
1204	    }
1205	}
1206    }
1207
1208  return 1;
1209}
1210
1211/* If x is a set of a register R, mark that R is alive in the beginning
1212   of every update-block of src.  */
1213
1214static void
1215update_live_1 (int src, rtx x)
1216{
1217  int i;
1218  int regno;
1219  rtx reg = SET_DEST (x);
1220
1221  if (reg == 0)
1222    return;
1223
1224  while (GET_CODE (reg) == SUBREG
1225	 || GET_CODE (reg) == ZERO_EXTRACT
1226	 || GET_CODE (reg) == STRICT_LOW_PART)
1227    reg = XEXP (reg, 0);
1228
1229  if (GET_CODE (reg) == PARALLEL)
1230    {
1231      int i;
1232
1233      for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1234	if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1235	  update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
1236
1237      return;
1238    }
1239
1240  if (!REG_P (reg))
1241    return;
1242
1243  /* Global registers are always live, so the code below does not apply
1244     to them.  */
1245
1246  regno = REGNO (reg);
1247
1248  if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
1249    {
1250      if (regno < FIRST_PSEUDO_REGISTER)
1251	{
1252	  int j = hard_regno_nregs[regno][GET_MODE (reg)];
1253	  while (--j >= 0)
1254	    {
1255	      for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1256		{
1257		  basic_block b = candidate_table[src].update_bbs.first_member[i];
1258
1259		  SET_REGNO_REG_SET (b->il.rtl->global_live_at_start,
1260				     regno + j);
1261		}
1262	    }
1263	}
1264      else
1265	{
1266	  for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1267	    {
1268	      basic_block b = candidate_table[src].update_bbs.first_member[i];
1269
1270	      SET_REGNO_REG_SET (b->il.rtl->global_live_at_start, regno);
1271	    }
1272	}
1273    }
1274}
1275
1276/* Return 1 if insn can be speculatively moved from block src to trg,
1277   otherwise return 0.  Called before first insertion of insn to
1278   ready-list or before the scheduling.  */
1279
1280static int
1281check_live (rtx insn, int src)
1282{
1283  /* Find the registers set by instruction.  */
1284  if (GET_CODE (PATTERN (insn)) == SET
1285      || GET_CODE (PATTERN (insn)) == CLOBBER)
1286    return check_live_1 (src, PATTERN (insn));
1287  else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1288    {
1289      int j;
1290      for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1291	if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1292	     || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1293	    && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
1294	  return 0;
1295
1296      return 1;
1297    }
1298
1299  return 1;
1300}
1301
1302/* Update the live registers info after insn was moved speculatively from
1303   block src to trg.  */
1304
1305static void
1306update_live (rtx insn, int src)
1307{
1308  /* Find the registers set by instruction.  */
1309  if (GET_CODE (PATTERN (insn)) == SET
1310      || GET_CODE (PATTERN (insn)) == CLOBBER)
1311    update_live_1 (src, PATTERN (insn));
1312  else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1313    {
1314      int j;
1315      for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1316	if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1317	    || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1318	  update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
1319    }
1320}
1321
1322/* Nonzero if block bb_to is equal to, or reachable from block bb_from.  */
1323#define IS_REACHABLE(bb_from, bb_to)					\
1324  (bb_from == bb_to							\
1325   || IS_RGN_ENTRY (bb_from)						\
1326   || (TEST_BIT (ancestor_edges[bb_to],					\
1327	 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK (BB_TO_BLOCK (bb_from)))))))
1328
1329/* Turns on the fed_by_spec_load flag for insns fed by load_insn.  */
1330
1331static void
1332set_spec_fed (rtx load_insn)
1333{
1334  rtx link;
1335
1336  for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
1337    if (GET_MODE (link) == VOIDmode)
1338      FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
1339}				/* set_spec_fed */
1340
1341/* On the path from the insn to load_insn_bb, find a conditional
1342branch depending on insn, that guards the speculative load.  */
1343
1344static int
1345find_conditional_protection (rtx insn, int load_insn_bb)
1346{
1347  rtx link;
1348
1349  /* Iterate through DEF-USE forward dependences.  */
1350  for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
1351    {
1352      rtx next = XEXP (link, 0);
1353      if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
1354	   CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
1355	  && IS_REACHABLE (INSN_BB (next), load_insn_bb)
1356	  && load_insn_bb != INSN_BB (next)
1357	  && GET_MODE (link) == VOIDmode
1358	  && (JUMP_P (next)
1359	      || find_conditional_protection (next, load_insn_bb)))
1360	return 1;
1361    }
1362  return 0;
1363}				/* find_conditional_protection */
1364
1365/* Returns 1 if the same insn1 that participates in the computation
1366   of load_insn's address is feeding a conditional branch that is
1367   guarding on load_insn. This is true if we find a the two DEF-USE
1368   chains:
1369   insn1 -> ... -> conditional-branch
1370   insn1 -> ... -> load_insn,
1371   and if a flow path exist:
1372   insn1 -> ... -> conditional-branch -> ... -> load_insn,
1373   and if insn1 is on the path
1374   region-entry -> ... -> bb_trg -> ... load_insn.
1375
1376   Locate insn1 by climbing on LOG_LINKS from load_insn.
1377   Locate the branch by following INSN_DEPEND from insn1.  */
1378
1379static int
1380is_conditionally_protected (rtx load_insn, int bb_src, int bb_trg)
1381{
1382  rtx link;
1383
1384  for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
1385    {
1386      rtx insn1 = XEXP (link, 0);
1387
1388      /* Must be a DEF-USE dependence upon non-branch.  */
1389      if (GET_MODE (link) != VOIDmode
1390	  || JUMP_P (insn1))
1391	continue;
1392
1393      /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn.  */
1394      if (INSN_BB (insn1) == bb_src
1395	  || (CONTAINING_RGN (BLOCK_NUM (insn1))
1396	      != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
1397	  || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
1398	      && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
1399	continue;
1400
1401      /* Now search for the conditional-branch.  */
1402      if (find_conditional_protection (insn1, bb_src))
1403	return 1;
1404
1405      /* Recursive step: search another insn1, "above" current insn1.  */
1406      return is_conditionally_protected (insn1, bb_src, bb_trg);
1407    }
1408
1409  /* The chain does not exist.  */
1410  return 0;
1411}				/* is_conditionally_protected */
1412
1413/* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1414   load_insn can move speculatively from bb_src to bb_trg.  All the
1415   following must hold:
1416
1417   (1) both loads have 1 base register (PFREE_CANDIDATEs).
1418   (2) load_insn and load1 have a def-use dependence upon
1419   the same insn 'insn1'.
1420   (3) either load2 is in bb_trg, or:
1421   - there's only one split-block, and
1422   - load1 is on the escape path, and
1423
1424   From all these we can conclude that the two loads access memory
1425   addresses that differ at most by a constant, and hence if moving
1426   load_insn would cause an exception, it would have been caused by
1427   load2 anyhow.  */
1428
1429static int
1430is_pfree (rtx load_insn, int bb_src, int bb_trg)
1431{
1432  rtx back_link;
1433  candidate *candp = candidate_table + bb_src;
1434
1435  if (candp->split_bbs.nr_members != 1)
1436    /* Must have exactly one escape block.  */
1437    return 0;
1438
1439  for (back_link = LOG_LINKS (load_insn);
1440       back_link; back_link = XEXP (back_link, 1))
1441    {
1442      rtx insn1 = XEXP (back_link, 0);
1443
1444      if (GET_MODE (back_link) == VOIDmode)
1445	{
1446	  /* Found a DEF-USE dependence (insn1, load_insn).  */
1447	  rtx fore_link;
1448
1449	  for (fore_link = INSN_DEPEND (insn1);
1450	       fore_link; fore_link = XEXP (fore_link, 1))
1451	    {
1452	      rtx insn2 = XEXP (fore_link, 0);
1453	      if (GET_MODE (fore_link) == VOIDmode)
1454		{
1455		  /* Found a DEF-USE dependence (insn1, insn2).  */
1456		  if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
1457		    /* insn2 not guaranteed to be a 1 base reg load.  */
1458		    continue;
1459
1460		  if (INSN_BB (insn2) == bb_trg)
1461		    /* insn2 is the similar load, in the target block.  */
1462		    return 1;
1463
1464		  if (*(candp->split_bbs.first_member) == BLOCK_FOR_INSN (insn2))
1465		    /* insn2 is a similar load, in a split-block.  */
1466		    return 1;
1467		}
1468	    }
1469	}
1470    }
1471
1472  /* Couldn't find a similar load.  */
1473  return 0;
1474}				/* is_pfree */
1475
1476/* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1477   a load moved speculatively, or if load_insn is protected by
1478   a compare on load_insn's address).  */
1479
1480static int
1481is_prisky (rtx load_insn, int bb_src, int bb_trg)
1482{
1483  if (FED_BY_SPEC_LOAD (load_insn))
1484    return 1;
1485
1486  if (LOG_LINKS (load_insn) == NULL)
1487    /* Dependence may 'hide' out of the region.  */
1488    return 1;
1489
1490  if (is_conditionally_protected (load_insn, bb_src, bb_trg))
1491    return 1;
1492
1493  return 0;
1494}
1495
1496/* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
1497   Return 1 if insn is exception-free (and the motion is valid)
1498   and 0 otherwise.  */
1499
1500static int
1501is_exception_free (rtx insn, int bb_src, int bb_trg)
1502{
1503  int insn_class = haifa_classify_insn (insn);
1504
1505  /* Handle non-load insns.  */
1506  switch (insn_class)
1507    {
1508    case TRAP_FREE:
1509      return 1;
1510    case TRAP_RISKY:
1511      return 0;
1512    default:;
1513    }
1514
1515  /* Handle loads.  */
1516  if (!flag_schedule_speculative_load)
1517    return 0;
1518  IS_LOAD_INSN (insn) = 1;
1519  switch (insn_class)
1520    {
1521    case IFREE:
1522      return (1);
1523    case IRISKY:
1524      return 0;
1525    case PFREE_CANDIDATE:
1526      if (is_pfree (insn, bb_src, bb_trg))
1527	return 1;
1528      /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate.  */
1529    case PRISKY_CANDIDATE:
1530      if (!flag_schedule_speculative_load_dangerous
1531	  || is_prisky (insn, bb_src, bb_trg))
1532	return 0;
1533      break;
1534    default:;
1535    }
1536
1537  return flag_schedule_speculative_load_dangerous;
1538}
1539
1540/* The number of insns from the current block scheduled so far.  */
1541static int sched_target_n_insns;
1542/* The number of insns from the current block to be scheduled in total.  */
1543static int target_n_insns;
1544/* The number of insns from the entire region scheduled so far.  */
1545static int sched_n_insns;
1546/* Nonzero if the last scheduled insn was a jump.  */
1547static int last_was_jump;
1548
1549/* Implementations of the sched_info functions for region scheduling.  */
1550static void init_ready_list (struct ready_list *);
1551static int can_schedule_ready_p (rtx);
1552static int new_ready (rtx);
1553static int schedule_more_p (void);
1554static const char *rgn_print_insn (rtx, int);
1555static int rgn_rank (rtx, rtx);
1556static int contributes_to_priority (rtx, rtx);
1557static void compute_jump_reg_dependencies (rtx, regset, regset, regset);
1558
1559/* Return nonzero if there are more insns that should be scheduled.  */
1560
1561static int
1562schedule_more_p (void)
1563{
1564  return ! last_was_jump && sched_target_n_insns < target_n_insns;
1565}
1566
1567/* Add all insns that are initially ready to the ready list READY.  Called
1568   once before scheduling a set of insns.  */
1569
1570static void
1571init_ready_list (struct ready_list *ready)
1572{
1573  rtx prev_head = current_sched_info->prev_head;
1574  rtx next_tail = current_sched_info->next_tail;
1575  int bb_src;
1576  rtx insn;
1577
1578  target_n_insns = 0;
1579  sched_target_n_insns = 0;
1580  sched_n_insns = 0;
1581  last_was_jump = 0;
1582
1583  /* Print debugging information.  */
1584  if (sched_verbose >= 5)
1585    debug_dependencies ();
1586
1587  /* Prepare current target block info.  */
1588  if (current_nr_blocks > 1)
1589    {
1590      candidate_table = xmalloc (current_nr_blocks * sizeof (candidate));
1591
1592      bblst_last = 0;
1593      /* bblst_table holds split blocks and update blocks for each block after
1594	 the current one in the region.  split blocks and update blocks are
1595	 the TO blocks of region edges, so there can be at most rgn_nr_edges
1596	 of them.  */
1597      bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
1598      bblst_table = xmalloc (bblst_size * sizeof (basic_block));
1599
1600      edgelst_last = 0;
1601      edgelst_table = xmalloc (rgn_nr_edges * sizeof (edge));
1602
1603      compute_trg_info (target_bb);
1604    }
1605
1606  /* Initialize ready list with all 'ready' insns in target block.
1607     Count number of insns in the target block being scheduled.  */
1608  for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
1609    {
1610      if (INSN_DEP_COUNT (insn) == 0)
1611	{
1612	  ready_add (ready, insn);
1613
1614	  if (targetm.sched.adjust_priority)
1615	    INSN_PRIORITY (insn) =
1616	      targetm.sched.adjust_priority (insn, INSN_PRIORITY (insn));
1617	}
1618      target_n_insns++;
1619    }
1620
1621  /* Add to ready list all 'ready' insns in valid source blocks.
1622     For speculative insns, check-live, exception-free, and
1623     issue-delay.  */
1624  for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
1625    if (IS_VALID (bb_src))
1626      {
1627	rtx src_head;
1628	rtx src_next_tail;
1629	rtx tail, head;
1630
1631	get_block_head_tail (BB_TO_BLOCK (bb_src), &head, &tail);
1632	src_next_tail = NEXT_INSN (tail);
1633	src_head = head;
1634
1635	for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
1636	  {
1637	    if (! INSN_P (insn))
1638	      continue;
1639
1640	    if (!CANT_MOVE (insn)
1641		&& (!IS_SPECULATIVE_INSN (insn)
1642		    || ((recog_memoized (insn) < 0
1643			 || min_insn_conflict_delay (curr_state,
1644						     insn, insn) <= 3)
1645			&& check_live (insn, bb_src)
1646			&& is_exception_free (insn, bb_src, target_bb))))
1647	      if (INSN_DEP_COUNT (insn) == 0)
1648		{
1649		  ready_add (ready, insn);
1650
1651		  if (targetm.sched.adjust_priority)
1652		    INSN_PRIORITY (insn) =
1653		      targetm.sched.adjust_priority (insn, INSN_PRIORITY (insn));
1654		}
1655	  }
1656      }
1657}
1658
1659/* Called after taking INSN from the ready list.  Returns nonzero if this
1660   insn can be scheduled, nonzero if we should silently discard it.  */
1661
1662static int
1663can_schedule_ready_p (rtx insn)
1664{
1665  if (JUMP_P (insn))
1666    last_was_jump = 1;
1667
1668  /* An interblock motion?  */
1669  if (INSN_BB (insn) != target_bb)
1670    {
1671      basic_block b1;
1672
1673      if (IS_SPECULATIVE_INSN (insn))
1674	{
1675	  if (!check_live (insn, INSN_BB (insn)))
1676	    return 0;
1677	  update_live (insn, INSN_BB (insn));
1678
1679	  /* For speculative load, mark insns fed by it.  */
1680	  if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
1681	    set_spec_fed (insn);
1682
1683	  nr_spec++;
1684	}
1685      nr_inter++;
1686
1687      /* Update source block boundaries.  */
1688      b1 = BLOCK_FOR_INSN (insn);
1689      if (insn == BB_HEAD (b1) && insn == BB_END (b1))
1690	{
1691	  /* We moved all the insns in the basic block.
1692	     Emit a note after the last insn and update the
1693	     begin/end boundaries to point to the note.  */
1694	  rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
1695	  BB_HEAD (b1) = note;
1696	  BB_END (b1) = note;
1697	}
1698      else if (insn == BB_END (b1))
1699	{
1700	  /* We took insns from the end of the basic block,
1701	     so update the end of block boundary so that it
1702	     points to the first insn we did not move.  */
1703	  BB_END (b1) = PREV_INSN (insn);
1704	}
1705      else if (insn == BB_HEAD (b1))
1706	{
1707	  /* We took insns from the start of the basic block,
1708	     so update the start of block boundary so that
1709	     it points to the first insn we did not move.  */
1710	  BB_HEAD (b1) = NEXT_INSN (insn);
1711	}
1712    }
1713  else
1714    {
1715      /* In block motion.  */
1716      sched_target_n_insns++;
1717    }
1718  sched_n_insns++;
1719
1720  return 1;
1721}
1722
1723/* Called after INSN has all its dependencies resolved.  Return nonzero
1724   if it should be moved to the ready list or the queue, or zero if we
1725   should silently discard it.  */
1726static int
1727new_ready (rtx next)
1728{
1729  /* For speculative insns, before inserting to ready/queue,
1730     check live, exception-free, and issue-delay.  */
1731  if (INSN_BB (next) != target_bb
1732      && (!IS_VALID (INSN_BB (next))
1733	  || CANT_MOVE (next)
1734	  || (IS_SPECULATIVE_INSN (next)
1735	      && ((recog_memoized (next) >= 0
1736		   && min_insn_conflict_delay (curr_state, next, next) > 3)
1737		  || !check_live (next, INSN_BB (next))
1738		  || !is_exception_free (next, INSN_BB (next), target_bb)))))
1739    return 0;
1740  return 1;
1741}
1742
1743/* Return a string that contains the insn uid and optionally anything else
1744   necessary to identify this insn in an output.  It's valid to use a
1745   static buffer for this.  The ALIGNED parameter should cause the string
1746   to be formatted so that multiple output lines will line up nicely.  */
1747
1748static const char *
1749rgn_print_insn (rtx insn, int aligned)
1750{
1751  static char tmp[80];
1752
1753  if (aligned)
1754    sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
1755  else
1756    {
1757      if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
1758	sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
1759      else
1760	sprintf (tmp, "%d", INSN_UID (insn));
1761    }
1762  return tmp;
1763}
1764
1765/* Compare priority of two insns.  Return a positive number if the second
1766   insn is to be preferred for scheduling, and a negative one if the first
1767   is to be preferred.  Zero if they are equally good.  */
1768
1769static int
1770rgn_rank (rtx insn1, rtx insn2)
1771{
1772  /* Some comparison make sense in interblock scheduling only.  */
1773  if (INSN_BB (insn1) != INSN_BB (insn2))
1774    {
1775      int spec_val, prob_val;
1776
1777      /* Prefer an inblock motion on an interblock motion.  */
1778      if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
1779	return 1;
1780      if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
1781	return -1;
1782
1783      /* Prefer a useful motion on a speculative one.  */
1784      spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
1785      if (spec_val)
1786	return spec_val;
1787
1788      /* Prefer a more probable (speculative) insn.  */
1789      prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
1790      if (prob_val)
1791	return prob_val;
1792    }
1793  return 0;
1794}
1795
1796/* NEXT is an instruction that depends on INSN (a backward dependence);
1797   return nonzero if we should include this dependence in priority
1798   calculations.  */
1799
1800static int
1801contributes_to_priority (rtx next, rtx insn)
1802{
1803  return BLOCK_NUM (next) == BLOCK_NUM (insn);
1804}
1805
1806/* INSN is a JUMP_INSN, COND_SET is the set of registers that are
1807   conditionally set before INSN.  Store the set of registers that
1808   must be considered as used by this jump in USED and that of
1809   registers that must be considered as set in SET.  */
1810
1811static void
1812compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
1813			       regset cond_exec ATTRIBUTE_UNUSED,
1814			       regset used ATTRIBUTE_UNUSED,
1815			       regset set ATTRIBUTE_UNUSED)
1816{
1817  /* Nothing to do here, since we postprocess jumps in
1818     add_branch_dependences.  */
1819}
1820
1821/* Used in schedule_insns to initialize current_sched_info for scheduling
1822   regions (or single basic blocks).  */
1823
1824static struct sched_info region_sched_info =
1825{
1826  init_ready_list,
1827  can_schedule_ready_p,
1828  schedule_more_p,
1829  new_ready,
1830  rgn_rank,
1831  rgn_print_insn,
1832  contributes_to_priority,
1833  compute_jump_reg_dependencies,
1834
1835  NULL, NULL,
1836  NULL, NULL,
1837  0, 0, 0
1838};
1839
1840/* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register.  */
1841
1842static bool
1843sets_likely_spilled (rtx pat)
1844{
1845  bool ret = false;
1846  note_stores (pat, sets_likely_spilled_1, &ret);
1847  return ret;
1848}
1849
1850static void
1851sets_likely_spilled_1 (rtx x, rtx pat, void *data)
1852{
1853  bool *ret = (bool *) data;
1854
1855  if (GET_CODE (pat) == SET
1856      && REG_P (x)
1857      && REGNO (x) < FIRST_PSEUDO_REGISTER
1858      && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x))))
1859    *ret = true;
1860}
1861
1862/* Add dependences so that branches are scheduled to run last in their
1863   block.  */
1864
1865static void
1866add_branch_dependences (rtx head, rtx tail)
1867{
1868  rtx insn, last;
1869
1870  /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
1871     that can throw exceptions, force them to remain in order at the end of
1872     the block by adding dependencies and giving the last a high priority.
1873     There may be notes present, and prev_head may also be a note.
1874
1875     Branches must obviously remain at the end.  Calls should remain at the
1876     end since moving them results in worse register allocation.  Uses remain
1877     at the end to ensure proper register allocation.
1878
1879     cc0 setters remain at the end because they can't be moved away from
1880     their cc0 user.
1881
1882     COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
1883
1884     Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values)
1885     are not moved before reload because we can wind up with register
1886     allocation failures.  */
1887
1888  insn = tail;
1889  last = 0;
1890  while (CALL_P (insn)
1891	 || JUMP_P (insn)
1892	 || (NONJUMP_INSN_P (insn)
1893	     && (GET_CODE (PATTERN (insn)) == USE
1894		 || GET_CODE (PATTERN (insn)) == CLOBBER
1895		 || can_throw_internal (insn)
1896#ifdef HAVE_cc0
1897		 || sets_cc0_p (PATTERN (insn))
1898#endif
1899		 || (!reload_completed
1900		     && sets_likely_spilled (PATTERN (insn)))))
1901	 || NOTE_P (insn))
1902    {
1903      if (!NOTE_P (insn))
1904	{
1905	  if (last != 0 && !find_insn_list (insn, LOG_LINKS (last)))
1906	    {
1907	      if (! sched_insns_conditions_mutex_p (last, insn))
1908		add_dependence (last, insn, REG_DEP_ANTI);
1909	      INSN_REF_COUNT (insn)++;
1910	    }
1911
1912	  CANT_MOVE (insn) = 1;
1913
1914	  last = insn;
1915	}
1916
1917      /* Don't overrun the bounds of the basic block.  */
1918      if (insn == head)
1919	break;
1920
1921      insn = PREV_INSN (insn);
1922    }
1923
1924  /* Make sure these insns are scheduled last in their block.  */
1925  insn = last;
1926  if (insn != 0)
1927    while (insn != head)
1928      {
1929	insn = prev_nonnote_insn (insn);
1930
1931	if (INSN_REF_COUNT (insn) != 0)
1932	  continue;
1933
1934	if (! sched_insns_conditions_mutex_p (last, insn))
1935	  add_dependence (last, insn, REG_DEP_ANTI);
1936	INSN_REF_COUNT (insn) = 1;
1937      }
1938
1939#ifdef HAVE_conditional_execution
1940  /* Finally, if the block ends in a jump, and we are doing intra-block
1941     scheduling, make sure that the branch depends on any COND_EXEC insns
1942     inside the block to avoid moving the COND_EXECs past the branch insn.
1943
1944     We only have to do this after reload, because (1) before reload there
1945     are no COND_EXEC insns, and (2) the region scheduler is an intra-block
1946     scheduler after reload.
1947
1948     FIXME: We could in some cases move COND_EXEC insns past the branch if
1949     this scheduler would be a little smarter.  Consider this code:
1950
1951		T = [addr]
1952	C  ?	addr += 4
1953	!C ?	X += 12
1954	C  ?	T += 1
1955	C  ?	jump foo
1956
1957     On a target with a one cycle stall on a memory access the optimal
1958     sequence would be:
1959
1960		T = [addr]
1961	C  ?	addr += 4
1962	C  ?	T += 1
1963	C  ?	jump foo
1964	!C ?	X += 12
1965
1966     We don't want to put the 'X += 12' before the branch because it just
1967     wastes a cycle of execution time when the branch is taken.
1968
1969     Note that in the example "!C" will always be true.  That is another
1970     possible improvement for handling COND_EXECs in this scheduler: it
1971     could remove always-true predicates.  */
1972
1973  if (!reload_completed || ! JUMP_P (tail))
1974    return;
1975
1976  insn = tail;
1977  while (insn != head)
1978    {
1979      insn = PREV_INSN (insn);
1980
1981      /* Note that we want to add this dependency even when
1982	 sched_insns_conditions_mutex_p returns true.  The whole point
1983	 is that we _want_ this dependency, even if these insns really
1984	 are independent.  */
1985      if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC)
1986	add_dependence (tail, insn, REG_DEP_ANTI);
1987    }
1988#endif
1989}
1990
1991/* Data structures for the computation of data dependences in a regions.  We
1992   keep one `deps' structure for every basic block.  Before analyzing the
1993   data dependences for a bb, its variables are initialized as a function of
1994   the variables of its predecessors.  When the analysis for a bb completes,
1995   we save the contents to the corresponding bb_deps[bb] variable.  */
1996
1997static struct deps *bb_deps;
1998
1999/* Duplicate the INSN_LIST elements of COPY and prepend them to OLD.  */
2000
2001static rtx
2002concat_INSN_LIST (rtx copy, rtx old)
2003{
2004  rtx new = old;
2005  for (; copy ; copy = XEXP (copy, 1))
2006    new = alloc_INSN_LIST (XEXP (copy, 0), new);
2007  return new;
2008}
2009
2010static void
2011concat_insn_mem_list (rtx copy_insns, rtx copy_mems, rtx *old_insns_p,
2012		      rtx *old_mems_p)
2013{
2014  rtx new_insns = *old_insns_p;
2015  rtx new_mems = *old_mems_p;
2016
2017  while (copy_insns)
2018    {
2019      new_insns = alloc_INSN_LIST (XEXP (copy_insns, 0), new_insns);
2020      new_mems = alloc_EXPR_LIST (VOIDmode, XEXP (copy_mems, 0), new_mems);
2021      copy_insns = XEXP (copy_insns, 1);
2022      copy_mems = XEXP (copy_mems, 1);
2023    }
2024
2025  *old_insns_p = new_insns;
2026  *old_mems_p = new_mems;
2027}
2028
2029/* After computing the dependencies for block BB, propagate the dependencies
2030   found in TMP_DEPS to the successors of the block.  */
2031static void
2032propagate_deps (int bb, struct deps *pred_deps)
2033{
2034  basic_block block = BASIC_BLOCK (BB_TO_BLOCK (bb));
2035  edge_iterator ei;
2036  edge e;
2037
2038  /* bb's structures are inherited by its successors.  */
2039  FOR_EACH_EDGE (e, ei, block->succs)
2040    {
2041      struct deps *succ_deps;
2042      unsigned reg;
2043      reg_set_iterator rsi;
2044
2045      /* Only bbs "below" bb, in the same region, are interesting.  */
2046      if (e->dest == EXIT_BLOCK_PTR
2047	  || CONTAINING_RGN (block->index) != CONTAINING_RGN (e->dest->index)
2048	  || BLOCK_TO_BB (e->dest->index) <= bb)
2049	continue;
2050
2051      succ_deps = bb_deps + BLOCK_TO_BB (e->dest->index);
2052
2053      /* The reg_last lists are inherited by successor.  */
2054      EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi)
2055	{
2056	  struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
2057	  struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
2058
2059	  succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
2060	  succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
2061	  succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
2062						succ_rl->clobbers);
2063	  succ_rl->uses_length += pred_rl->uses_length;
2064	  succ_rl->clobbers_length += pred_rl->clobbers_length;
2065	}
2066      IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
2067
2068      /* Mem read/write lists are inherited by successor.  */
2069      concat_insn_mem_list (pred_deps->pending_read_insns,
2070			    pred_deps->pending_read_mems,
2071			    &succ_deps->pending_read_insns,
2072			    &succ_deps->pending_read_mems);
2073      concat_insn_mem_list (pred_deps->pending_write_insns,
2074			    pred_deps->pending_write_mems,
2075			    &succ_deps->pending_write_insns,
2076			    &succ_deps->pending_write_mems);
2077
2078      succ_deps->last_pending_memory_flush
2079	= concat_INSN_LIST (pred_deps->last_pending_memory_flush,
2080			    succ_deps->last_pending_memory_flush);
2081
2082      succ_deps->pending_lists_length += pred_deps->pending_lists_length;
2083      succ_deps->pending_flush_length += pred_deps->pending_flush_length;
2084
2085      /* last_function_call is inherited by successor.  */
2086      succ_deps->last_function_call
2087	= concat_INSN_LIST (pred_deps->last_function_call,
2088			      succ_deps->last_function_call);
2089
2090      /* sched_before_next_call is inherited by successor.  */
2091      succ_deps->sched_before_next_call
2092	= concat_INSN_LIST (pred_deps->sched_before_next_call,
2093			    succ_deps->sched_before_next_call);
2094    }
2095
2096  /* These lists should point to the right place, for correct
2097     freeing later.  */
2098  bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
2099  bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
2100  bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
2101  bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
2102
2103  /* Can't allow these to be freed twice.  */
2104  pred_deps->pending_read_insns = 0;
2105  pred_deps->pending_read_mems = 0;
2106  pred_deps->pending_write_insns = 0;
2107  pred_deps->pending_write_mems = 0;
2108}
2109
2110/* Compute backward dependences inside bb.  In a multiple blocks region:
2111   (1) a bb is analyzed after its predecessors, and (2) the lists in
2112   effect at the end of bb (after analyzing for bb) are inherited by
2113   bb's successors.
2114
2115   Specifically for reg-reg data dependences, the block insns are
2116   scanned by sched_analyze () top-to-bottom.  Two lists are
2117   maintained by sched_analyze (): reg_last[].sets for register DEFs,
2118   and reg_last[].uses for register USEs.
2119
2120   When analysis is completed for bb, we update for its successors:
2121   ;  - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2122   ;  - USES[succ] = Union (USES [succ], DEFS [bb])
2123
2124   The mechanism for computing mem-mem data dependence is very
2125   similar, and the result is interblock dependences in the region.  */
2126
2127static void
2128compute_block_backward_dependences (int bb)
2129{
2130  rtx head, tail;
2131  struct deps tmp_deps;
2132
2133  tmp_deps = bb_deps[bb];
2134
2135  /* Do the analysis for this block.  */
2136  get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2137  sched_analyze (&tmp_deps, head, tail);
2138  add_branch_dependences (head, tail);
2139
2140  if (current_nr_blocks > 1)
2141    propagate_deps (bb, &tmp_deps);
2142
2143  /* Free up the INSN_LISTs.  */
2144  free_deps (&tmp_deps);
2145}
2146
2147/* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2148   them to the unused_*_list variables, so that they can be reused.  */
2149
2150static void
2151free_pending_lists (void)
2152{
2153  int bb;
2154
2155  for (bb = 0; bb < current_nr_blocks; bb++)
2156    {
2157      free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
2158      free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
2159      free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
2160      free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
2161    }
2162}
2163
2164/* Print dependences for debugging, callable from debugger.  */
2165
2166void
2167debug_dependencies (void)
2168{
2169  int bb;
2170
2171  fprintf (sched_dump, ";;   --------------- forward dependences: ------------ \n");
2172  for (bb = 0; bb < current_nr_blocks; bb++)
2173    {
2174      rtx head, tail;
2175      rtx next_tail;
2176      rtx insn;
2177
2178      get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2179      next_tail = NEXT_INSN (tail);
2180      fprintf (sched_dump, "\n;;   --- Region Dependences --- b %d bb %d \n",
2181	       BB_TO_BLOCK (bb), bb);
2182
2183      fprintf (sched_dump, ";;   %7s%6s%6s%6s%6s%6s%14s\n",
2184	       "insn", "code", "bb", "dep", "prio", "cost",
2185	       "reservation");
2186      fprintf (sched_dump, ";;   %7s%6s%6s%6s%6s%6s%14s\n",
2187	       "----", "----", "--", "---", "----", "----",
2188	       "-----------");
2189
2190      for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2191	{
2192	  rtx link;
2193
2194	  if (! INSN_P (insn))
2195	    {
2196	      int n;
2197	      fprintf (sched_dump, ";;   %6d ", INSN_UID (insn));
2198	      if (NOTE_P (insn))
2199		{
2200		  n = NOTE_LINE_NUMBER (insn);
2201		  if (n < 0)
2202		    fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
2203		  else
2204		    {
2205		      expanded_location xloc;
2206		      NOTE_EXPANDED_LOCATION (xloc, insn);
2207		      fprintf (sched_dump, "line %d, file %s\n",
2208			       xloc.line, xloc.file);
2209		    }
2210		}
2211	      else
2212		fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
2213	      continue;
2214	    }
2215
2216	  fprintf (sched_dump,
2217		   ";;   %s%5d%6d%6d%6d%6d%6d   ",
2218		   (SCHED_GROUP_P (insn) ? "+" : " "),
2219		   INSN_UID (insn),
2220		   INSN_CODE (insn),
2221		   INSN_BB (insn),
2222		   INSN_DEP_COUNT (insn),
2223		   INSN_PRIORITY (insn),
2224		   insn_cost (insn, 0, 0));
2225
2226	  if (recog_memoized (insn) < 0)
2227	    fprintf (sched_dump, "nothing");
2228	  else
2229	    print_reservation (sched_dump, insn);
2230
2231	  fprintf (sched_dump, "\t: ");
2232	  for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2233	    fprintf (sched_dump, "%d ", INSN_UID (XEXP (link, 0)));
2234	  fprintf (sched_dump, "\n");
2235	}
2236    }
2237  fprintf (sched_dump, "\n");
2238}
2239
2240/* Returns true if all the basic blocks of the current region have
2241   NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region.  */
2242static bool
2243sched_is_disabled_for_current_region_p (void)
2244{
2245  int bb;
2246
2247  for (bb = 0; bb < current_nr_blocks; bb++)
2248    if (!(BASIC_BLOCK (BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE))
2249      return false;
2250
2251  return true;
2252}
2253
2254/* Schedule a region.  A region is either an inner loop, a loop-free
2255   subroutine, or a single basic block.  Each bb in the region is
2256   scheduled after its flow predecessors.  */
2257
2258static void
2259schedule_region (int rgn)
2260{
2261  basic_block block;
2262  edge_iterator ei;
2263  edge e;
2264  int bb;
2265  int rgn_n_insns = 0;
2266  int sched_rgn_n_insns = 0;
2267
2268  /* Set variables for the current region.  */
2269  current_nr_blocks = RGN_NR_BLOCKS (rgn);
2270  current_blocks = RGN_BLOCKS (rgn);
2271
2272  /* Don't schedule region that is marked by
2273     NOTE_DISABLE_SCHED_OF_BLOCK.  */
2274  if (sched_is_disabled_for_current_region_p ())
2275    return;
2276
2277  init_deps_global ();
2278
2279  /* Initializations for region data dependence analysis.  */
2280  bb_deps = xmalloc (sizeof (struct deps) * current_nr_blocks);
2281  for (bb = 0; bb < current_nr_blocks; bb++)
2282    init_deps (bb_deps + bb);
2283
2284  /* Compute LOG_LINKS.  */
2285  for (bb = 0; bb < current_nr_blocks; bb++)
2286    compute_block_backward_dependences (bb);
2287
2288  /* Compute INSN_DEPEND.  */
2289  for (bb = current_nr_blocks - 1; bb >= 0; bb--)
2290    {
2291      rtx head, tail;
2292      get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2293
2294      compute_forward_dependences (head, tail);
2295
2296      if (targetm.sched.dependencies_evaluation_hook)
2297	targetm.sched.dependencies_evaluation_hook (head, tail);
2298
2299    }
2300
2301  /* Set priorities.  */
2302  for (bb = 0; bb < current_nr_blocks; bb++)
2303    {
2304      rtx head, tail;
2305      get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2306
2307      rgn_n_insns += set_priorities (head, tail);
2308    }
2309
2310  /* Compute interblock info: probabilities, split-edges, dominators, etc.  */
2311  if (current_nr_blocks > 1)
2312    {
2313      prob = xmalloc ((current_nr_blocks) * sizeof (float));
2314
2315      dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
2316      sbitmap_vector_zero (dom, current_nr_blocks);
2317
2318      /* Use ->aux to implement EDGE_TO_BIT mapping.  */
2319      rgn_nr_edges = 0;
2320      FOR_EACH_BB (block)
2321	{
2322	  if (CONTAINING_RGN (block->index) != rgn)
2323	    continue;
2324	  FOR_EACH_EDGE (e, ei, block->succs)
2325	    SET_EDGE_TO_BIT (e, rgn_nr_edges++);
2326	}
2327
2328      rgn_edges = xmalloc (rgn_nr_edges * sizeof (edge));
2329      rgn_nr_edges = 0;
2330      FOR_EACH_BB (block)
2331	{
2332	  if (CONTAINING_RGN (block->index) != rgn)
2333	    continue;
2334	  FOR_EACH_EDGE (e, ei, block->succs)
2335	    rgn_edges[rgn_nr_edges++] = e;
2336	}
2337
2338      /* Split edges.  */
2339      pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2340      sbitmap_vector_zero (pot_split, current_nr_blocks);
2341      ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2342      sbitmap_vector_zero (ancestor_edges, current_nr_blocks);
2343
2344      /* Compute probabilities, dominators, split_edges.  */
2345      for (bb = 0; bb < current_nr_blocks; bb++)
2346	compute_dom_prob_ps (bb);
2347    }
2348
2349  /* Now we can schedule all blocks.  */
2350  for (bb = 0; bb < current_nr_blocks; bb++)
2351    {
2352      rtx head, tail;
2353      int b = BB_TO_BLOCK (bb);
2354
2355      get_block_head_tail (b, &head, &tail);
2356
2357      if (no_real_insns_p (head, tail))
2358	continue;
2359
2360      current_sched_info->prev_head = PREV_INSN (head);
2361      current_sched_info->next_tail = NEXT_INSN (tail);
2362
2363      if (write_symbols != NO_DEBUG)
2364	{
2365	  save_line_notes (b, head, tail);
2366	  rm_line_notes (head, tail);
2367	}
2368
2369      /* rm_other_notes only removes notes which are _inside_ the
2370	 block---that is, it won't remove notes before the first real insn
2371	 or after the last real insn of the block.  So if the first insn
2372	 has a REG_SAVE_NOTE which would otherwise be emitted before the
2373	 insn, it is redundant with the note before the start of the
2374	 block, and so we have to take it out.  */
2375      if (INSN_P (head))
2376	{
2377	  rtx note;
2378
2379	  for (note = REG_NOTES (head); note; note = XEXP (note, 1))
2380	    if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
2381	      remove_note (head, note);
2382	}
2383
2384      /* Remove remaining note insns from the block, save them in
2385	 note_list.  These notes are restored at the end of
2386	 schedule_block ().  */
2387      rm_other_notes (head, tail);
2388
2389      target_bb = bb;
2390
2391      current_sched_info->queue_must_finish_empty
2392	= current_nr_blocks > 1 && !flag_schedule_interblock;
2393
2394      schedule_block (b, rgn_n_insns);
2395      sched_rgn_n_insns += sched_n_insns;
2396
2397      /* Update target block boundaries.  */
2398      if (head == BB_HEAD (BASIC_BLOCK (b)))
2399	BB_HEAD (BASIC_BLOCK (b)) = current_sched_info->head;
2400      if (tail == BB_END (BASIC_BLOCK (b)))
2401	BB_END (BASIC_BLOCK (b)) = current_sched_info->tail;
2402
2403      /* Clean up.  */
2404      if (current_nr_blocks > 1)
2405	{
2406	  free (candidate_table);
2407	  free (bblst_table);
2408	  free (edgelst_table);
2409	}
2410    }
2411
2412  /* Sanity check: verify that all region insns were scheduled.  */
2413  gcc_assert (sched_rgn_n_insns == rgn_n_insns);
2414
2415  /* Restore line notes.  */
2416  if (write_symbols != NO_DEBUG)
2417    {
2418      for (bb = 0; bb < current_nr_blocks; bb++)
2419	{
2420	  rtx head, tail;
2421	  get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2422	  restore_line_notes (head, tail);
2423	}
2424    }
2425
2426  /* Done with this region.  */
2427  free_pending_lists ();
2428
2429  finish_deps_global ();
2430
2431  free (bb_deps);
2432
2433  if (current_nr_blocks > 1)
2434    {
2435      /* Cleanup ->aux used for EDGE_TO_BIT mapping.  */
2436      FOR_EACH_BB (block)
2437	{
2438	  if (CONTAINING_RGN (block->index) != rgn)
2439	    continue;
2440	  FOR_EACH_EDGE (e, ei, block->succs)
2441	    e->aux = NULL;
2442	}
2443
2444      free (prob);
2445      sbitmap_vector_free (dom);
2446      sbitmap_vector_free (pot_split);
2447      sbitmap_vector_free (ancestor_edges);
2448      free (rgn_edges);
2449    }
2450}
2451
2452/* Indexed by region, holds the number of death notes found in that region.
2453   Used for consistency checks.  */
2454static int *deaths_in_region;
2455
2456/* Initialize data structures for region scheduling.  */
2457
2458static void
2459init_regions (void)
2460{
2461  sbitmap blocks;
2462  int rgn;
2463
2464  nr_regions = 0;
2465  rgn_table = xmalloc ((n_basic_blocks) * sizeof (region));
2466  rgn_bb_table = xmalloc ((n_basic_blocks) * sizeof (int));
2467  block_to_bb = xmalloc ((last_basic_block) * sizeof (int));
2468  containing_rgn = xmalloc ((last_basic_block) * sizeof (int));
2469
2470  /* Compute regions for scheduling.  */
2471  if (reload_completed
2472      || n_basic_blocks == 1
2473      || !flag_schedule_interblock
2474      || is_cfg_nonregular ())
2475    {
2476      find_single_block_region ();
2477    }
2478  else
2479    {
2480      /* Compute the dominators and post dominators.  */
2481      calculate_dominance_info (CDI_DOMINATORS);
2482
2483      /* Find regions.  */
2484      find_rgns ();
2485
2486      if (sched_verbose >= 3)
2487	debug_regions ();
2488
2489      /* For now.  This will move as more and more of haifa is converted
2490	 to using the cfg code in flow.c.  */
2491      free_dominance_info (CDI_DOMINATORS);
2492    }
2493
2494
2495  if (CHECK_DEAD_NOTES)
2496    {
2497      blocks = sbitmap_alloc (last_basic_block);
2498      deaths_in_region = xmalloc (sizeof (int) * nr_regions);
2499      /* Remove all death notes from the subroutine.  */
2500      for (rgn = 0; rgn < nr_regions; rgn++)
2501	{
2502	  int b;
2503
2504	  sbitmap_zero (blocks);
2505	  for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
2506	    SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]);
2507
2508	  deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1);
2509	}
2510      sbitmap_free (blocks);
2511    }
2512  else
2513    count_or_remove_death_notes (NULL, 1);
2514}
2515
2516/* The one entry point in this file.  DUMP_FILE is the dump file for
2517   this pass.  */
2518
2519void
2520schedule_insns (FILE *dump_file)
2521{
2522  sbitmap large_region_blocks, blocks;
2523  int rgn;
2524  int any_large_regions;
2525  basic_block bb;
2526
2527  /* Taking care of this degenerate case makes the rest of
2528     this code simpler.  */
2529  if (n_basic_blocks == 0)
2530    return;
2531
2532  nr_inter = 0;
2533  nr_spec = 0;
2534
2535  sched_init (dump_file);
2536
2537  init_regions ();
2538
2539  current_sched_info = &region_sched_info;
2540
2541  /* Schedule every region in the subroutine.  */
2542  for (rgn = 0; rgn < nr_regions; rgn++)
2543    schedule_region (rgn);
2544
2545  /* Update life analysis for the subroutine.  Do single block regions
2546     first so that we can verify that live_at_start didn't change.  Then
2547     do all other blocks.  */
2548  /* ??? There is an outside possibility that update_life_info, or more
2549     to the point propagate_block, could get called with nonzero flags
2550     more than once for one basic block.  This would be kinda bad if it
2551     were to happen, since REG_INFO would be accumulated twice for the
2552     block, and we'd have twice the REG_DEAD notes.
2553
2554     I'm fairly certain that this _shouldn't_ happen, since I don't think
2555     that live_at_start should change at region heads.  Not sure what the
2556     best way to test for this kind of thing...  */
2557
2558  allocate_reg_life_data ();
2559  compute_bb_for_insn ();
2560
2561  any_large_regions = 0;
2562  large_region_blocks = sbitmap_alloc (last_basic_block);
2563  sbitmap_zero (large_region_blocks);
2564  FOR_EACH_BB (bb)
2565    SET_BIT (large_region_blocks, bb->index);
2566
2567  blocks = sbitmap_alloc (last_basic_block);
2568  sbitmap_zero (blocks);
2569
2570  /* Update life information.  For regions consisting of multiple blocks
2571     we've possibly done interblock scheduling that affects global liveness.
2572     For regions consisting of single blocks we need to do only local
2573     liveness.  */
2574  for (rgn = 0; rgn < nr_regions; rgn++)
2575    if (RGN_NR_BLOCKS (rgn) > 1)
2576      any_large_regions = 1;
2577    else
2578      {
2579	SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2580	RESET_BIT (large_region_blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2581      }
2582
2583  /* Don't update reg info after reload, since that affects
2584     regs_ever_live, which should not change after reload.  */
2585  update_life_info (blocks, UPDATE_LIFE_LOCAL,
2586		    (reload_completed ? PROP_DEATH_NOTES
2587		     : PROP_DEATH_NOTES | PROP_REG_INFO));
2588  if (any_large_regions)
2589    {
2590      update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL,
2591			PROP_DEATH_NOTES | PROP_REG_INFO);
2592    }
2593
2594  if (CHECK_DEAD_NOTES)
2595    {
2596      /* Verify the counts of basic block notes in single the basic block
2597         regions.  */
2598      for (rgn = 0; rgn < nr_regions; rgn++)
2599	if (RGN_NR_BLOCKS (rgn) == 1)
2600	  {
2601	    sbitmap_zero (blocks);
2602	    SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2603
2604	    gcc_assert (deaths_in_region[rgn]
2605			== count_or_remove_death_notes (blocks, 0));
2606	  }
2607      free (deaths_in_region);
2608    }
2609
2610  /* Reposition the prologue and epilogue notes in case we moved the
2611     prologue/epilogue insns.  */
2612  if (reload_completed)
2613    reposition_prologue_and_epilogue_notes (get_insns ());
2614
2615  /* Delete redundant line notes.  */
2616  if (write_symbols != NO_DEBUG)
2617    rm_redundant_line_notes ();
2618
2619  if (sched_verbose)
2620    {
2621      if (reload_completed == 0 && flag_schedule_interblock)
2622	{
2623	  fprintf (sched_dump,
2624		   "\n;; Procedure interblock/speculative motions == %d/%d \n",
2625		   nr_inter, nr_spec);
2626	}
2627      else
2628	gcc_assert (nr_inter <= 0);
2629      fprintf (sched_dump, "\n\n");
2630    }
2631
2632  /* Clean up.  */
2633  free (rgn_table);
2634  free (rgn_bb_table);
2635  free (block_to_bb);
2636  free (containing_rgn);
2637
2638  sched_finish ();
2639
2640  sbitmap_free (blocks);
2641  sbitmap_free (large_region_blocks);
2642}
2643#endif
2644
2645static bool
2646gate_handle_sched (void)
2647{
2648#ifdef INSN_SCHEDULING
2649  return flag_schedule_insns;
2650#else
2651  return 0;
2652#endif
2653}
2654
2655/* Run instruction scheduler.  */
2656static void
2657rest_of_handle_sched (void)
2658{
2659#ifdef INSN_SCHEDULING
2660  /* Do control and data sched analysis,
2661     and write some of the results to dump file.  */
2662
2663  schedule_insns (dump_file);
2664#endif
2665}
2666
2667static bool
2668gate_handle_sched2 (void)
2669{
2670#ifdef INSN_SCHEDULING
2671  return optimize > 0 && flag_schedule_insns_after_reload;
2672#else
2673  return 0;
2674#endif
2675}
2676
2677/* Run second scheduling pass after reload.  */
2678static void
2679rest_of_handle_sched2 (void)
2680{
2681#ifdef INSN_SCHEDULING
2682  /* Do control and data sched analysis again,
2683     and write some more of the results to dump file.  */
2684
2685  split_all_insns (1);
2686
2687  if (flag_sched2_use_superblocks || flag_sched2_use_traces)
2688    {
2689      schedule_ebbs (dump_file);
2690      /* No liveness updating code yet, but it should be easy to do.
2691         reg-stack recomputes the liveness when needed for now.  */
2692      count_or_remove_death_notes (NULL, 1);
2693      cleanup_cfg (CLEANUP_EXPENSIVE);
2694    }
2695  else
2696    schedule_insns (dump_file);
2697#endif
2698}
2699
2700struct tree_opt_pass pass_sched =
2701{
2702  "sched1",                             /* name */
2703  gate_handle_sched,                    /* gate */
2704  rest_of_handle_sched,                 /* execute */
2705  NULL,                                 /* sub */
2706  NULL,                                 /* next */
2707  0,                                    /* static_pass_number */
2708  TV_SCHED,                             /* tv_id */
2709  0,                                    /* properties_required */
2710  0,                                    /* properties_provided */
2711  0,                                    /* properties_destroyed */
2712  0,                                    /* todo_flags_start */
2713  TODO_dump_func |
2714  TODO_ggc_collect,                     /* todo_flags_finish */
2715  'S'                                   /* letter */
2716};
2717
2718struct tree_opt_pass pass_sched2 =
2719{
2720  "sched2",                             /* name */
2721  gate_handle_sched2,                   /* gate */
2722  rest_of_handle_sched2,                /* execute */
2723  NULL,                                 /* sub */
2724  NULL,                                 /* next */
2725  0,                                    /* static_pass_number */
2726  TV_SCHED2,                            /* tv_id */
2727  0,                                    /* properties_required */
2728  0,                                    /* properties_provided */
2729  0,                                    /* properties_destroyed */
2730  0,                                    /* todo_flags_start */
2731  TODO_dump_func |
2732  TODO_ggc_collect,                     /* todo_flags_finish */
2733  'R'                                   /* letter */
2734};
2735
2736