gcc/
[official-gcc.git] / gcc / sched-rgn.c
blobccdde706ea7866434c35d36deb0f4915e358d28f
1 /* Instruction scheduling pass.
2 Copyright (C) 1992-2015 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This pass implements list scheduling within basic blocks. It is
23 run twice: (1) after flow analysis, but before register allocation,
24 and (2) after register allocation.
26 The first run performs interblock scheduling, moving insns between
27 different blocks in the same "region", and the second runs only
28 basic block scheduling.
30 Interblock motions performed are useful motions and speculative
31 motions, including speculative loads. Motions requiring code
32 duplication are not supported. The identification of motion type
33 and the check for validity of speculative motions requires
34 construction and analysis of the function's control flow graph.
36 The main entry point for this pass is schedule_insns(), called for
37 each function. The work of the scheduler is organized in three
38 levels: (1) function level: insns are subject to splitting,
39 control-flow-graph is constructed, regions are computed (after
40 reload, each region is of one block), (2) region level: control
41 flow graph attributes required for interblock scheduling are
42 computed (dominators, reachability, etc.), data dependences and
43 priorities are computed, and (3) block level: insns in the block
44 are actually scheduled. */
46 #include "config.h"
47 #include "system.h"
48 #include "coretypes.h"
49 #include "tm.h"
50 #include "diagnostic-core.h"
51 #include "rtl.h"
52 #include "tm_p.h"
53 #include "hard-reg-set.h"
54 #include "regs.h"
55 #include "function.h"
56 #include "profile.h"
57 #include "flags.h"
58 #include "insn-config.h"
59 #include "insn-attr.h"
60 #include "except.h"
61 #include "recog.h"
62 #include "params.h"
63 #include "dominance.h"
64 #include "cfg.h"
65 #include "cfganal.h"
66 #include "predict.h"
67 #include "basic-block.h"
68 #include "sched-int.h"
69 #include "sel-sched.h"
70 #include "target.h"
71 #include "tree-pass.h"
72 #include "dbgcnt.h"
73 #include "emit-rtl.h"
75 #ifdef INSN_SCHEDULING
77 /* Some accessor macros for h_i_d members only used within this file. */
78 #define FED_BY_SPEC_LOAD(INSN) (HID (INSN)->fed_by_spec_load)
79 #define IS_LOAD_INSN(INSN) (HID (insn)->is_load_insn)
81 /* nr_inter/spec counts interblock/speculative motion for the function. */
82 static int nr_inter, nr_spec;
84 static int is_cfg_nonregular (void);
86 /* Number of regions in the procedure. */
87 int nr_regions = 0;
89 /* Same as above before adding any new regions. */
90 static int nr_regions_initial = 0;
92 /* Table of region descriptions. */
93 region *rgn_table = NULL;
95 /* Array of lists of regions' blocks. */
96 int *rgn_bb_table = NULL;
98 /* Topological order of blocks in the region (if b2 is reachable from
99 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
100 always referred to by either block or b, while its topological
101 order name (in the region) is referred to by bb. */
102 int *block_to_bb = NULL;
104 /* The number of the region containing a block. */
105 int *containing_rgn = NULL;
107 /* ebb_head [i] - is index in rgn_bb_table of the head basic block of i'th ebb.
108 Currently we can get a ebb only through splitting of currently
109 scheduling block, therefore, we don't need ebb_head array for every region,
110 hence, its sufficient to hold it for current one only. */
111 int *ebb_head = NULL;
113 /* The minimum probability of reaching a source block so that it will be
114 considered for speculative scheduling. */
115 static int min_spec_prob;
117 static void find_single_block_region (bool);
118 static void find_rgns (void);
119 static bool too_large (int, int *, int *);
121 /* Blocks of the current region being scheduled. */
122 int current_nr_blocks;
123 int current_blocks;
125 /* A speculative motion requires checking live information on the path
126 from 'source' to 'target'. The split blocks are those to be checked.
127 After a speculative motion, live information should be modified in
128 the 'update' blocks.
130 Lists of split and update blocks for each candidate of the current
131 target are in array bblst_table. */
132 static basic_block *bblst_table;
133 static int bblst_size, bblst_last;
135 /* Arrays that hold the DFA state at the end of a basic block, to re-use
136 as the initial state at the start of successor blocks. The BB_STATE
137 array holds the actual DFA state, and BB_STATE_ARRAY[I] is a pointer
138 into BB_STATE for basic block I. FIXME: This should be a vec. */
139 static char *bb_state_array = NULL;
140 static state_t *bb_state = NULL;
142 /* Target info declarations.
144 The block currently being scheduled is referred to as the "target" block,
145 while other blocks in the region from which insns can be moved to the
146 target are called "source" blocks. The candidate structure holds info
147 about such sources: are they valid? Speculative? Etc. */
148 typedef struct
150 basic_block *first_member;
151 int nr_members;
153 bblst;
155 typedef struct
157 char is_valid;
158 char is_speculative;
159 int src_prob;
160 bblst split_bbs;
161 bblst update_bbs;
163 candidate;
165 static candidate *candidate_table;
166 #define IS_VALID(src) (candidate_table[src].is_valid)
167 #define IS_SPECULATIVE(src) (candidate_table[src].is_speculative)
168 #define IS_SPECULATIVE_INSN(INSN) \
169 (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
170 #define SRC_PROB(src) ( candidate_table[src].src_prob )
172 /* The bb being currently scheduled. */
173 int target_bb;
175 /* List of edges. */
176 typedef struct
178 edge *first_member;
179 int nr_members;
181 edgelst;
183 static edge *edgelst_table;
184 static int edgelst_last;
186 static void extract_edgelst (sbitmap, edgelst *);
188 /* Target info functions. */
189 static void split_edges (int, int, edgelst *);
190 static void compute_trg_info (int);
191 void debug_candidate (int);
192 void debug_candidates (int);
194 /* Dominators array: dom[i] contains the sbitmap of dominators of
195 bb i in the region. */
196 static sbitmap *dom;
198 /* bb 0 is the only region entry. */
199 #define IS_RGN_ENTRY(bb) (!bb)
201 /* Is bb_src dominated by bb_trg. */
202 #define IS_DOMINATED(bb_src, bb_trg) \
203 ( bitmap_bit_p (dom[bb_src], bb_trg) )
205 /* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
206 the probability of bb i relative to the region entry. */
207 static int *prob;
209 /* Bit-set of edges, where bit i stands for edge i. */
210 typedef sbitmap edgeset;
212 /* Number of edges in the region. */
213 static int rgn_nr_edges;
215 /* Array of size rgn_nr_edges. */
216 static edge *rgn_edges;
218 /* Mapping from each edge in the graph to its number in the rgn. */
219 #define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
220 #define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
222 /* The split edges of a source bb is different for each target
223 bb. In order to compute this efficiently, the 'potential-split edges'
224 are computed for each bb prior to scheduling a region. This is actually
225 the split edges of each bb relative to the region entry.
227 pot_split[bb] is the set of potential split edges of bb. */
228 static edgeset *pot_split;
230 /* For every bb, a set of its ancestor edges. */
231 static edgeset *ancestor_edges;
233 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
235 /* Speculative scheduling functions. */
236 static int check_live_1 (int, rtx);
237 static void update_live_1 (int, rtx);
238 static int is_pfree (rtx, int, int);
239 static int find_conditional_protection (rtx_insn *, int);
240 static int is_conditionally_protected (rtx, int, int);
241 static int is_prisky (rtx, int, int);
242 static int is_exception_free (rtx_insn *, int, int);
244 static bool sets_likely_spilled (rtx);
245 static void sets_likely_spilled_1 (rtx, const_rtx, void *);
246 static void add_branch_dependences (rtx_insn *, rtx_insn *);
247 static void compute_block_dependences (int);
249 static void schedule_region (int);
250 static void concat_insn_mem_list (rtx_insn_list *, rtx_expr_list *,
251 rtx_insn_list **, rtx_expr_list **);
252 static void propagate_deps (int, struct deps_desc *);
253 static void free_pending_lists (void);
255 /* Functions for construction of the control flow graph. */
257 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
259 We decide not to build the control flow graph if there is possibly more
260 than one entry to the function, if computed branches exist, if we
261 have nonlocal gotos, or if we have an unreachable loop. */
263 static int
264 is_cfg_nonregular (void)
266 basic_block b;
267 rtx_insn *insn;
269 /* If we have a label that could be the target of a nonlocal goto, then
270 the cfg is not well structured. */
271 if (nonlocal_goto_handler_labels)
272 return 1;
274 /* If we have any forced labels, then the cfg is not well structured. */
275 if (forced_labels)
276 return 1;
278 /* If we have exception handlers, then we consider the cfg not well
279 structured. ?!? We should be able to handle this now that we
280 compute an accurate cfg for EH. */
281 if (current_function_has_exception_handlers ())
282 return 1;
284 /* If we have insns which refer to labels as non-jumped-to operands,
285 then we consider the cfg not well structured. */
286 FOR_EACH_BB_FN (b, cfun)
287 FOR_BB_INSNS (b, insn)
289 rtx note, set, dest;
290 rtx_insn *next;
292 /* If this function has a computed jump, then we consider the cfg
293 not well structured. */
294 if (JUMP_P (insn) && computed_jump_p (insn))
295 return 1;
297 if (!INSN_P (insn))
298 continue;
300 note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX);
301 if (note == NULL_RTX)
302 continue;
304 /* For that label not to be seen as a referred-to label, this
305 must be a single-set which is feeding a jump *only*. This
306 could be a conditional jump with the label split off for
307 machine-specific reasons or a casesi/tablejump. */
308 next = next_nonnote_insn (insn);
309 if (next == NULL_RTX
310 || !JUMP_P (next)
311 || (JUMP_LABEL (next) != XEXP (note, 0)
312 && find_reg_note (next, REG_LABEL_TARGET,
313 XEXP (note, 0)) == NULL_RTX)
314 || BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (next))
315 return 1;
317 set = single_set (insn);
318 if (set == NULL_RTX)
319 return 1;
321 dest = SET_DEST (set);
322 if (!REG_P (dest) || !dead_or_set_p (next, dest))
323 return 1;
326 /* Unreachable loops with more than one basic block are detected
327 during the DFS traversal in find_rgns.
329 Unreachable loops with a single block are detected here. This
330 test is redundant with the one in find_rgns, but it's much
331 cheaper to go ahead and catch the trivial case here. */
332 FOR_EACH_BB_FN (b, cfun)
334 if (EDGE_COUNT (b->preds) == 0
335 || (single_pred_p (b)
336 && single_pred (b) == b))
337 return 1;
340 /* All the tests passed. Consider the cfg well structured. */
341 return 0;
344 /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */
346 static void
347 extract_edgelst (sbitmap set, edgelst *el)
349 unsigned int i = 0;
350 sbitmap_iterator sbi;
352 /* edgelst table space is reused in each call to extract_edgelst. */
353 edgelst_last = 0;
355 el->first_member = &edgelst_table[edgelst_last];
356 el->nr_members = 0;
358 /* Iterate over each word in the bitset. */
359 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, sbi)
361 edgelst_table[edgelst_last++] = rgn_edges[i];
362 el->nr_members++;
366 /* Functions for the construction of regions. */
368 /* Print the regions, for debugging purposes. Callable from debugger. */
370 DEBUG_FUNCTION void
371 debug_regions (void)
373 int rgn, bb;
375 fprintf (sched_dump, "\n;; ------------ REGIONS ----------\n\n");
376 for (rgn = 0; rgn < nr_regions; rgn++)
378 fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
379 rgn_table[rgn].rgn_nr_blocks);
380 fprintf (sched_dump, ";;\tbb/block: ");
382 /* We don't have ebb_head initialized yet, so we can't use
383 BB_TO_BLOCK (). */
384 current_blocks = RGN_BLOCKS (rgn);
386 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
387 fprintf (sched_dump, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
389 fprintf (sched_dump, "\n\n");
393 /* Print the region's basic blocks. */
395 DEBUG_FUNCTION void
396 debug_region (int rgn)
398 int bb;
400 fprintf (stderr, "\n;; ------------ REGION %d ----------\n\n", rgn);
401 fprintf (stderr, ";;\trgn %d nr_blocks %d:\n", rgn,
402 rgn_table[rgn].rgn_nr_blocks);
403 fprintf (stderr, ";;\tbb/block: ");
405 /* We don't have ebb_head initialized yet, so we can't use
406 BB_TO_BLOCK (). */
407 current_blocks = RGN_BLOCKS (rgn);
409 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
410 fprintf (stderr, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
412 fprintf (stderr, "\n\n");
414 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
416 dump_bb (stderr,
417 BASIC_BLOCK_FOR_FN (cfun, rgn_bb_table[current_blocks + bb]),
418 0, TDF_SLIM | TDF_BLOCKS);
419 fprintf (stderr, "\n");
422 fprintf (stderr, "\n");
426 /* True when a bb with index BB_INDEX contained in region RGN. */
427 static bool
428 bb_in_region_p (int bb_index, int rgn)
430 int i;
432 for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
433 if (rgn_bb_table[current_blocks + i] == bb_index)
434 return true;
436 return false;
439 /* Dump region RGN to file F using dot syntax. */
440 void
441 dump_region_dot (FILE *f, int rgn)
443 int i;
445 fprintf (f, "digraph Region_%d {\n", rgn);
447 /* We don't have ebb_head initialized yet, so we can't use
448 BB_TO_BLOCK (). */
449 current_blocks = RGN_BLOCKS (rgn);
451 for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
453 edge e;
454 edge_iterator ei;
455 int src_bb_num = rgn_bb_table[current_blocks + i];
456 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, src_bb_num);
458 FOR_EACH_EDGE (e, ei, bb->succs)
459 if (bb_in_region_p (e->dest->index, rgn))
460 fprintf (f, "\t%d -> %d\n", src_bb_num, e->dest->index);
462 fprintf (f, "}\n");
465 /* The same, but first open a file specified by FNAME. */
466 void
467 dump_region_dot_file (const char *fname, int rgn)
469 FILE *f = fopen (fname, "wt");
470 dump_region_dot (f, rgn);
471 fclose (f);
474 /* Build a single block region for each basic block in the function.
475 This allows for using the same code for interblock and basic block
476 scheduling. */
478 static void
479 find_single_block_region (bool ebbs_p)
481 basic_block bb, ebb_start;
482 int i = 0;
484 nr_regions = 0;
486 if (ebbs_p) {
487 int probability_cutoff;
488 if (profile_info && flag_branch_probabilities)
489 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
490 else
491 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
492 probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
494 FOR_EACH_BB_FN (ebb_start, cfun)
496 RGN_NR_BLOCKS (nr_regions) = 0;
497 RGN_BLOCKS (nr_regions) = i;
498 RGN_DONT_CALC_DEPS (nr_regions) = 0;
499 RGN_HAS_REAL_EBB (nr_regions) = 0;
501 for (bb = ebb_start; ; bb = bb->next_bb)
503 edge e;
505 rgn_bb_table[i] = bb->index;
506 RGN_NR_BLOCKS (nr_regions)++;
507 CONTAINING_RGN (bb->index) = nr_regions;
508 BLOCK_TO_BB (bb->index) = i - RGN_BLOCKS (nr_regions);
509 i++;
511 if (bb->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
512 || LABEL_P (BB_HEAD (bb->next_bb)))
513 break;
515 e = find_fallthru_edge (bb->succs);
516 if (! e)
517 break;
518 if (e->probability <= probability_cutoff)
519 break;
522 ebb_start = bb;
523 nr_regions++;
526 else
527 FOR_EACH_BB_FN (bb, cfun)
529 rgn_bb_table[nr_regions] = bb->index;
530 RGN_NR_BLOCKS (nr_regions) = 1;
531 RGN_BLOCKS (nr_regions) = nr_regions;
532 RGN_DONT_CALC_DEPS (nr_regions) = 0;
533 RGN_HAS_REAL_EBB (nr_regions) = 0;
535 CONTAINING_RGN (bb->index) = nr_regions;
536 BLOCK_TO_BB (bb->index) = 0;
537 nr_regions++;
541 /* Estimate number of the insns in the BB. */
542 static int
543 rgn_estimate_number_of_insns (basic_block bb)
545 int count;
547 count = INSN_LUID (BB_END (bb)) - INSN_LUID (BB_HEAD (bb));
549 if (MAY_HAVE_DEBUG_INSNS)
551 rtx_insn *insn;
553 FOR_BB_INSNS (bb, insn)
554 if (DEBUG_INSN_P (insn))
555 count--;
558 return count;
561 /* Update number of blocks and the estimate for number of insns
562 in the region. Return true if the region is "too large" for interblock
563 scheduling (compile time considerations). */
565 static bool
566 too_large (int block, int *num_bbs, int *num_insns)
568 (*num_bbs)++;
569 (*num_insns) += (common_sched_info->estimate_number_of_insns
570 (BASIC_BLOCK_FOR_FN (cfun, block)));
572 return ((*num_bbs > PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS))
573 || (*num_insns > PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS)));
576 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
577 is still an inner loop. Put in max_hdr[blk] the header of the most inner
578 loop containing blk. */
579 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
581 if (max_hdr[blk] == -1) \
582 max_hdr[blk] = hdr; \
583 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
584 bitmap_clear_bit (inner, hdr); \
585 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
587 bitmap_clear_bit (inner,max_hdr[blk]); \
588 max_hdr[blk] = hdr; \
592 /* Find regions for interblock scheduling.
594 A region for scheduling can be:
596 * A loop-free procedure, or
598 * A reducible inner loop, or
600 * A basic block not contained in any other region.
602 ?!? In theory we could build other regions based on extended basic
603 blocks or reverse extended basic blocks. Is it worth the trouble?
605 Loop blocks that form a region are put into the region's block list
606 in topological order.
608 This procedure stores its results into the following global (ick) variables
610 * rgn_nr
611 * rgn_table
612 * rgn_bb_table
613 * block_to_bb
614 * containing region
616 We use dominator relationships to avoid making regions out of non-reducible
617 loops.
619 This procedure needs to be converted to work on pred/succ lists instead
620 of edge tables. That would simplify it somewhat. */
622 static void
623 haifa_find_rgns (void)
625 int *max_hdr, *dfs_nr, *degree;
626 char no_loops = 1;
627 int node, child, loop_head, i, head, tail;
628 int count = 0, sp, idx = 0;
629 edge_iterator current_edge;
630 edge_iterator *stack;
631 int num_bbs, num_insns, unreachable;
632 int too_large_failure;
633 basic_block bb;
635 /* Note if a block is a natural loop header. */
636 sbitmap header;
638 /* Note if a block is a natural inner loop header. */
639 sbitmap inner;
641 /* Note if a block is in the block queue. */
642 sbitmap in_queue;
644 /* Note if a block is in the block queue. */
645 sbitmap in_stack;
647 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
648 and a mapping from block to its loop header (if the block is contained
649 in a loop, else -1).
651 Store results in HEADER, INNER, and MAX_HDR respectively, these will
652 be used as inputs to the second traversal.
654 STACK, SP and DFS_NR are only used during the first traversal. */
656 /* Allocate and initialize variables for the first traversal. */
657 max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
658 dfs_nr = XCNEWVEC (int, last_basic_block_for_fn (cfun));
659 stack = XNEWVEC (edge_iterator, n_edges_for_fn (cfun));
661 inner = sbitmap_alloc (last_basic_block_for_fn (cfun));
662 bitmap_ones (inner);
664 header = sbitmap_alloc (last_basic_block_for_fn (cfun));
665 bitmap_clear (header);
667 in_queue = sbitmap_alloc (last_basic_block_for_fn (cfun));
668 bitmap_clear (in_queue);
670 in_stack = sbitmap_alloc (last_basic_block_for_fn (cfun));
671 bitmap_clear (in_stack);
673 for (i = 0; i < last_basic_block_for_fn (cfun); i++)
674 max_hdr[i] = -1;
676 #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
677 #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
679 /* DFS traversal to find inner loops in the cfg. */
681 current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))->succs);
682 sp = -1;
684 while (1)
686 if (EDGE_PASSED (current_edge))
688 /* We have reached a leaf node or a node that was already
689 processed. Pop edges off the stack until we find
690 an edge that has not yet been processed. */
691 while (sp >= 0 && EDGE_PASSED (current_edge))
693 /* Pop entry off the stack. */
694 current_edge = stack[sp--];
695 node = ei_edge (current_edge)->src->index;
696 gcc_assert (node != ENTRY_BLOCK);
697 child = ei_edge (current_edge)->dest->index;
698 gcc_assert (child != EXIT_BLOCK);
699 bitmap_clear_bit (in_stack, child);
700 if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
701 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
702 ei_next (&current_edge);
705 /* See if have finished the DFS tree traversal. */
706 if (sp < 0 && EDGE_PASSED (current_edge))
707 break;
709 /* Nope, continue the traversal with the popped node. */
710 continue;
713 /* Process a node. */
714 node = ei_edge (current_edge)->src->index;
715 gcc_assert (node != ENTRY_BLOCK);
716 bitmap_set_bit (in_stack, node);
717 dfs_nr[node] = ++count;
719 /* We don't traverse to the exit block. */
720 child = ei_edge (current_edge)->dest->index;
721 if (child == EXIT_BLOCK)
723 SET_EDGE_PASSED (current_edge);
724 ei_next (&current_edge);
725 continue;
728 /* If the successor is in the stack, then we've found a loop.
729 Mark the loop, if it is not a natural loop, then it will
730 be rejected during the second traversal. */
731 if (bitmap_bit_p (in_stack, child))
733 no_loops = 0;
734 bitmap_set_bit (header, child);
735 UPDATE_LOOP_RELATIONS (node, child);
736 SET_EDGE_PASSED (current_edge);
737 ei_next (&current_edge);
738 continue;
741 /* If the child was already visited, then there is no need to visit
742 it again. Just update the loop relationships and restart
743 with a new edge. */
744 if (dfs_nr[child])
746 if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
747 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
748 SET_EDGE_PASSED (current_edge);
749 ei_next (&current_edge);
750 continue;
753 /* Push an entry on the stack and continue DFS traversal. */
754 stack[++sp] = current_edge;
755 SET_EDGE_PASSED (current_edge);
756 current_edge = ei_start (ei_edge (current_edge)->dest->succs);
759 /* Reset ->aux field used by EDGE_PASSED. */
760 FOR_ALL_BB_FN (bb, cfun)
762 edge_iterator ei;
763 edge e;
764 FOR_EACH_EDGE (e, ei, bb->succs)
765 e->aux = NULL;
769 /* Another check for unreachable blocks. The earlier test in
770 is_cfg_nonregular only finds unreachable blocks that do not
771 form a loop.
773 The DFS traversal will mark every block that is reachable from
774 the entry node by placing a nonzero value in dfs_nr. Thus if
775 dfs_nr is zero for any block, then it must be unreachable. */
776 unreachable = 0;
777 FOR_EACH_BB_FN (bb, cfun)
778 if (dfs_nr[bb->index] == 0)
780 unreachable = 1;
781 break;
784 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
785 to hold degree counts. */
786 degree = dfs_nr;
788 FOR_EACH_BB_FN (bb, cfun)
789 degree[bb->index] = EDGE_COUNT (bb->preds);
791 /* Do not perform region scheduling if there are any unreachable
792 blocks. */
793 if (!unreachable)
795 int *queue, *degree1 = NULL;
796 /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
797 there basic blocks, which are forced to be region heads.
798 This is done to try to assemble few smaller regions
799 from a too_large region. */
800 sbitmap extended_rgn_header = NULL;
801 bool extend_regions_p;
803 if (no_loops)
804 bitmap_set_bit (header, 0);
806 /* Second traversal:find reducible inner loops and topologically sort
807 block of each region. */
809 queue = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
811 extend_regions_p = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS) > 0;
812 if (extend_regions_p)
814 degree1 = XNEWVEC (int, last_basic_block_for_fn (cfun));
815 extended_rgn_header =
816 sbitmap_alloc (last_basic_block_for_fn (cfun));
817 bitmap_clear (extended_rgn_header);
820 /* Find blocks which are inner loop headers. We still have non-reducible
821 loops to consider at this point. */
822 FOR_EACH_BB_FN (bb, cfun)
824 if (bitmap_bit_p (header, bb->index) && bitmap_bit_p (inner, bb->index))
826 edge e;
827 edge_iterator ei;
828 basic_block jbb;
830 /* Now check that the loop is reducible. We do this separate
831 from finding inner loops so that we do not find a reducible
832 loop which contains an inner non-reducible loop.
834 A simple way to find reducible/natural loops is to verify
835 that each block in the loop is dominated by the loop
836 header.
838 If there exists a block that is not dominated by the loop
839 header, then the block is reachable from outside the loop
840 and thus the loop is not a natural loop. */
841 FOR_EACH_BB_FN (jbb, cfun)
843 /* First identify blocks in the loop, except for the loop
844 entry block. */
845 if (bb->index == max_hdr[jbb->index] && bb != jbb)
847 /* Now verify that the block is dominated by the loop
848 header. */
849 if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))
850 break;
854 /* If we exited the loop early, then I is the header of
855 a non-reducible loop and we should quit processing it
856 now. */
857 if (jbb != EXIT_BLOCK_PTR_FOR_FN (cfun))
858 continue;
860 /* I is a header of an inner loop, or block 0 in a subroutine
861 with no loops at all. */
862 head = tail = -1;
863 too_large_failure = 0;
864 loop_head = max_hdr[bb->index];
866 if (extend_regions_p)
867 /* We save degree in case when we meet a too_large region
868 and cancel it. We need a correct degree later when
869 calling extend_rgns. */
870 memcpy (degree1, degree,
871 last_basic_block_for_fn (cfun) * sizeof (int));
873 /* Decrease degree of all I's successors for topological
874 ordering. */
875 FOR_EACH_EDGE (e, ei, bb->succs)
876 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
877 --degree[e->dest->index];
879 /* Estimate # insns, and count # blocks in the region. */
880 num_bbs = 1;
881 num_insns = common_sched_info->estimate_number_of_insns (bb);
883 /* Find all loop latches (blocks with back edges to the loop
884 header) or all the leaf blocks in the cfg has no loops.
886 Place those blocks into the queue. */
887 if (no_loops)
889 FOR_EACH_BB_FN (jbb, cfun)
890 /* Leaf nodes have only a single successor which must
891 be EXIT_BLOCK. */
892 if (single_succ_p (jbb)
893 && single_succ (jbb) == EXIT_BLOCK_PTR_FOR_FN (cfun))
895 queue[++tail] = jbb->index;
896 bitmap_set_bit (in_queue, jbb->index);
898 if (too_large (jbb->index, &num_bbs, &num_insns))
900 too_large_failure = 1;
901 break;
905 else
907 edge e;
909 FOR_EACH_EDGE (e, ei, bb->preds)
911 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
912 continue;
914 node = e->src->index;
916 if (max_hdr[node] == loop_head && node != bb->index)
918 /* This is a loop latch. */
919 queue[++tail] = node;
920 bitmap_set_bit (in_queue, node);
922 if (too_large (node, &num_bbs, &num_insns))
924 too_large_failure = 1;
925 break;
931 /* Now add all the blocks in the loop to the queue.
933 We know the loop is a natural loop; however the algorithm
934 above will not always mark certain blocks as being in the
935 loop. Consider:
936 node children
937 a b,c
939 c a,d
942 The algorithm in the DFS traversal may not mark B & D as part
943 of the loop (i.e. they will not have max_hdr set to A).
945 We know they can not be loop latches (else they would have
946 had max_hdr set since they'd have a backedge to a dominator
947 block). So we don't need them on the initial queue.
949 We know they are part of the loop because they are dominated
950 by the loop header and can be reached by a backwards walk of
951 the edges starting with nodes on the initial queue.
953 It is safe and desirable to include those nodes in the
954 loop/scheduling region. To do so we would need to decrease
955 the degree of a node if it is the target of a backedge
956 within the loop itself as the node is placed in the queue.
958 We do not do this because I'm not sure that the actual
959 scheduling code will properly handle this case. ?!? */
961 while (head < tail && !too_large_failure)
963 edge e;
964 child = queue[++head];
966 FOR_EACH_EDGE (e, ei,
967 BASIC_BLOCK_FOR_FN (cfun, child)->preds)
969 node = e->src->index;
971 /* See discussion above about nodes not marked as in
972 this loop during the initial DFS traversal. */
973 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
974 || max_hdr[node] != loop_head)
976 tail = -1;
977 break;
979 else if (!bitmap_bit_p (in_queue, node) && node != bb->index)
981 queue[++tail] = node;
982 bitmap_set_bit (in_queue, node);
984 if (too_large (node, &num_bbs, &num_insns))
986 too_large_failure = 1;
987 break;
993 if (tail >= 0 && !too_large_failure)
995 /* Place the loop header into list of region blocks. */
996 degree[bb->index] = -1;
997 rgn_bb_table[idx] = bb->index;
998 RGN_NR_BLOCKS (nr_regions) = num_bbs;
999 RGN_BLOCKS (nr_regions) = idx++;
1000 RGN_DONT_CALC_DEPS (nr_regions) = 0;
1001 RGN_HAS_REAL_EBB (nr_regions) = 0;
1002 CONTAINING_RGN (bb->index) = nr_regions;
1003 BLOCK_TO_BB (bb->index) = count = 0;
1005 /* Remove blocks from queue[] when their in degree
1006 becomes zero. Repeat until no blocks are left on the
1007 list. This produces a topological list of blocks in
1008 the region. */
1009 while (tail >= 0)
1011 if (head < 0)
1012 head = tail;
1013 child = queue[head];
1014 if (degree[child] == 0)
1016 edge e;
1018 degree[child] = -1;
1019 rgn_bb_table[idx++] = child;
1020 BLOCK_TO_BB (child) = ++count;
1021 CONTAINING_RGN (child) = nr_regions;
1022 queue[head] = queue[tail--];
1024 FOR_EACH_EDGE (e, ei,
1025 BASIC_BLOCK_FOR_FN (cfun,
1026 child)->succs)
1027 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1028 --degree[e->dest->index];
1030 else
1031 --head;
1033 ++nr_regions;
1035 else if (extend_regions_p)
1037 /* Restore DEGREE. */
1038 int *t = degree;
1040 degree = degree1;
1041 degree1 = t;
1043 /* And force successors of BB to be region heads.
1044 This may provide several smaller regions instead
1045 of one too_large region. */
1046 FOR_EACH_EDGE (e, ei, bb->succs)
1047 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1048 bitmap_set_bit (extended_rgn_header, e->dest->index);
1052 free (queue);
1054 if (extend_regions_p)
1056 free (degree1);
1058 bitmap_ior (header, header, extended_rgn_header);
1059 sbitmap_free (extended_rgn_header);
1061 extend_rgns (degree, &idx, header, max_hdr);
1065 /* Any block that did not end up in a region is placed into a region
1066 by itself. */
1067 FOR_EACH_BB_FN (bb, cfun)
1068 if (degree[bb->index] >= 0)
1070 rgn_bb_table[idx] = bb->index;
1071 RGN_NR_BLOCKS (nr_regions) = 1;
1072 RGN_BLOCKS (nr_regions) = idx++;
1073 RGN_DONT_CALC_DEPS (nr_regions) = 0;
1074 RGN_HAS_REAL_EBB (nr_regions) = 0;
1075 CONTAINING_RGN (bb->index) = nr_regions++;
1076 BLOCK_TO_BB (bb->index) = 0;
1079 free (max_hdr);
1080 free (degree);
1081 free (stack);
1082 sbitmap_free (header);
1083 sbitmap_free (inner);
1084 sbitmap_free (in_queue);
1085 sbitmap_free (in_stack);
1089 /* Wrapper function.
1090 If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
1091 regions. Otherwise just call find_rgns_haifa. */
1092 static void
1093 find_rgns (void)
1095 if (sel_sched_p () && flag_sel_sched_pipelining)
1096 sel_find_rgns ();
1097 else
1098 haifa_find_rgns ();
1101 static int gather_region_statistics (int **);
1102 static void print_region_statistics (int *, int, int *, int);
1104 /* Calculate the histogram that shows the number of regions having the
1105 given number of basic blocks, and store it in the RSP array. Return
1106 the size of this array. */
1107 static int
1108 gather_region_statistics (int **rsp)
1110 int i, *a = 0, a_sz = 0;
1112 /* a[i] is the number of regions that have (i + 1) basic blocks. */
1113 for (i = 0; i < nr_regions; i++)
1115 int nr_blocks = RGN_NR_BLOCKS (i);
1117 gcc_assert (nr_blocks >= 1);
1119 if (nr_blocks > a_sz)
1121 a = XRESIZEVEC (int, a, nr_blocks);
1123 a[a_sz++] = 0;
1124 while (a_sz != nr_blocks);
1127 a[nr_blocks - 1]++;
1130 *rsp = a;
1131 return a_sz;
1134 /* Print regions statistics. S1 and S2 denote the data before and after
1135 calling extend_rgns, respectively. */
1136 static void
1137 print_region_statistics (int *s1, int s1_sz, int *s2, int s2_sz)
1139 int i;
1141 /* We iterate until s2_sz because extend_rgns does not decrease
1142 the maximal region size. */
1143 for (i = 1; i < s2_sz; i++)
1145 int n1, n2;
1147 n2 = s2[i];
1149 if (n2 == 0)
1150 continue;
1152 if (i >= s1_sz)
1153 n1 = 0;
1154 else
1155 n1 = s1[i];
1157 fprintf (sched_dump, ";; Region extension statistics: size %d: " \
1158 "was %d + %d more\n", i + 1, n1, n2 - n1);
1162 /* Extend regions.
1163 DEGREE - Array of incoming edge count, considering only
1164 the edges, that don't have their sources in formed regions yet.
1165 IDXP - pointer to the next available index in rgn_bb_table.
1166 HEADER - set of all region heads.
1167 LOOP_HDR - mapping from block to the containing loop
1168 (two blocks can reside within one region if they have
1169 the same loop header). */
1170 void
1171 extend_rgns (int *degree, int *idxp, sbitmap header, int *loop_hdr)
1173 int *order, i, rescan = 0, idx = *idxp, iter = 0, max_iter, *max_hdr;
1174 int nblocks = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
1176 max_iter = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS);
1178 max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
1180 order = XNEWVEC (int, last_basic_block_for_fn (cfun));
1181 post_order_compute (order, false, false);
1183 for (i = nblocks - 1; i >= 0; i--)
1185 int bbn = order[i];
1186 if (degree[bbn] >= 0)
1188 max_hdr[bbn] = bbn;
1189 rescan = 1;
1191 else
1192 /* This block already was processed in find_rgns. */
1193 max_hdr[bbn] = -1;
1196 /* The idea is to topologically walk through CFG in top-down order.
1197 During the traversal, if all the predecessors of a node are
1198 marked to be in the same region (they all have the same max_hdr),
1199 then current node is also marked to be a part of that region.
1200 Otherwise the node starts its own region.
1201 CFG should be traversed until no further changes are made. On each
1202 iteration the set of the region heads is extended (the set of those
1203 blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
1204 set of all basic blocks, thus the algorithm is guaranteed to
1205 terminate. */
1207 while (rescan && iter < max_iter)
1209 rescan = 0;
1211 for (i = nblocks - 1; i >= 0; i--)
1213 edge e;
1214 edge_iterator ei;
1215 int bbn = order[i];
1217 if (max_hdr[bbn] != -1 && !bitmap_bit_p (header, bbn))
1219 int hdr = -1;
1221 FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->preds)
1223 int predn = e->src->index;
1225 if (predn != ENTRY_BLOCK
1226 /* If pred wasn't processed in find_rgns. */
1227 && max_hdr[predn] != -1
1228 /* And pred and bb reside in the same loop.
1229 (Or out of any loop). */
1230 && loop_hdr[bbn] == loop_hdr[predn])
1232 if (hdr == -1)
1233 /* Then bb extends the containing region of pred. */
1234 hdr = max_hdr[predn];
1235 else if (hdr != max_hdr[predn])
1236 /* Too bad, there are at least two predecessors
1237 that reside in different regions. Thus, BB should
1238 begin its own region. */
1240 hdr = bbn;
1241 break;
1244 else
1245 /* BB starts its own region. */
1247 hdr = bbn;
1248 break;
1252 if (hdr == bbn)
1254 /* If BB start its own region,
1255 update set of headers with BB. */
1256 bitmap_set_bit (header, bbn);
1257 rescan = 1;
1259 else
1260 gcc_assert (hdr != -1);
1262 max_hdr[bbn] = hdr;
1266 iter++;
1269 /* Statistics were gathered on the SPEC2000 package of tests with
1270 mainline weekly snapshot gcc-4.1-20051015 on ia64.
1272 Statistics for SPECint:
1273 1 iteration : 1751 cases (38.7%)
1274 2 iterations: 2770 cases (61.3%)
1275 Blocks wrapped in regions by find_rgns without extension: 18295 blocks
1276 Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
1277 (We don't count single block regions here).
1279 Statistics for SPECfp:
1280 1 iteration : 621 cases (35.9%)
1281 2 iterations: 1110 cases (64.1%)
1282 Blocks wrapped in regions by find_rgns without extension: 6476 blocks
1283 Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
1284 (We don't count single block regions here).
1286 By default we do at most 2 iterations.
1287 This can be overridden with max-sched-extend-regions-iters parameter:
1288 0 - disable region extension,
1289 N > 0 - do at most N iterations. */
1291 if (sched_verbose && iter != 0)
1292 fprintf (sched_dump, ";; Region extension iterations: %d%s\n", iter,
1293 rescan ? "... failed" : "");
1295 if (!rescan && iter != 0)
1297 int *s1 = NULL, s1_sz = 0;
1299 /* Save the old statistics for later printout. */
1300 if (sched_verbose >= 6)
1301 s1_sz = gather_region_statistics (&s1);
1303 /* We have succeeded. Now assemble the regions. */
1304 for (i = nblocks - 1; i >= 0; i--)
1306 int bbn = order[i];
1308 if (max_hdr[bbn] == bbn)
1309 /* BBN is a region head. */
1311 edge e;
1312 edge_iterator ei;
1313 int num_bbs = 0, j, num_insns = 0, large;
1315 large = too_large (bbn, &num_bbs, &num_insns);
1317 degree[bbn] = -1;
1318 rgn_bb_table[idx] = bbn;
1319 RGN_BLOCKS (nr_regions) = idx++;
1320 RGN_DONT_CALC_DEPS (nr_regions) = 0;
1321 RGN_HAS_REAL_EBB (nr_regions) = 0;
1322 CONTAINING_RGN (bbn) = nr_regions;
1323 BLOCK_TO_BB (bbn) = 0;
1325 FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->succs)
1326 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1327 degree[e->dest->index]--;
1329 if (!large)
1330 /* Here we check whether the region is too_large. */
1331 for (j = i - 1; j >= 0; j--)
1333 int succn = order[j];
1334 if (max_hdr[succn] == bbn)
1336 if ((large = too_large (succn, &num_bbs, &num_insns)))
1337 break;
1341 if (large)
1342 /* If the region is too_large, then wrap every block of
1343 the region into single block region.
1344 Here we wrap region head only. Other blocks are
1345 processed in the below cycle. */
1347 RGN_NR_BLOCKS (nr_regions) = 1;
1348 nr_regions++;
1351 num_bbs = 1;
1353 for (j = i - 1; j >= 0; j--)
1355 int succn = order[j];
1357 if (max_hdr[succn] == bbn)
1358 /* This cycle iterates over all basic blocks, that
1359 are supposed to be in the region with head BBN,
1360 and wraps them into that region (or in single
1361 block region). */
1363 gcc_assert (degree[succn] == 0);
1365 degree[succn] = -1;
1366 rgn_bb_table[idx] = succn;
1367 BLOCK_TO_BB (succn) = large ? 0 : num_bbs++;
1368 CONTAINING_RGN (succn) = nr_regions;
1370 if (large)
1371 /* Wrap SUCCN into single block region. */
1373 RGN_BLOCKS (nr_regions) = idx;
1374 RGN_NR_BLOCKS (nr_regions) = 1;
1375 RGN_DONT_CALC_DEPS (nr_regions) = 0;
1376 RGN_HAS_REAL_EBB (nr_regions) = 0;
1377 nr_regions++;
1380 idx++;
1382 FOR_EACH_EDGE (e, ei,
1383 BASIC_BLOCK_FOR_FN (cfun, succn)->succs)
1384 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1385 degree[e->dest->index]--;
1389 if (!large)
1391 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1392 nr_regions++;
1397 if (sched_verbose >= 6)
1399 int *s2, s2_sz;
1401 /* Get the new statistics and print the comparison with the
1402 one before calling this function. */
1403 s2_sz = gather_region_statistics (&s2);
1404 print_region_statistics (s1, s1_sz, s2, s2_sz);
1405 free (s1);
1406 free (s2);
1410 free (order);
1411 free (max_hdr);
1413 *idxp = idx;
1416 /* Functions for regions scheduling information. */
1418 /* Compute dominators, probability, and potential-split-edges of bb.
1419 Assume that these values were already computed for bb's predecessors. */
1421 static void
1422 compute_dom_prob_ps (int bb)
1424 edge_iterator in_ei;
1425 edge in_edge;
1427 /* We shouldn't have any real ebbs yet. */
1428 gcc_assert (ebb_head [bb] == bb + current_blocks);
1430 if (IS_RGN_ENTRY (bb))
1432 bitmap_set_bit (dom[bb], 0);
1433 prob[bb] = REG_BR_PROB_BASE;
1434 return;
1437 prob[bb] = 0;
1439 /* Initialize dom[bb] to '111..1'. */
1440 bitmap_ones (dom[bb]);
1442 FOR_EACH_EDGE (in_edge, in_ei,
1443 BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb))->preds)
1445 int pred_bb;
1446 edge out_edge;
1447 edge_iterator out_ei;
1449 if (in_edge->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1450 continue;
1452 pred_bb = BLOCK_TO_BB (in_edge->src->index);
1453 bitmap_and (dom[bb], dom[bb], dom[pred_bb]);
1454 bitmap_ior (ancestor_edges[bb],
1455 ancestor_edges[bb], ancestor_edges[pred_bb]);
1457 bitmap_set_bit (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
1459 bitmap_ior (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
1461 FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
1462 bitmap_set_bit (pot_split[bb], EDGE_TO_BIT (out_edge));
1464 prob[bb] += combine_probabilities (prob[pred_bb], in_edge->probability);
1465 // The rounding divide in combine_probabilities can result in an extra
1466 // probability increment propagating along 50-50 edges. Eventually when
1467 // the edges re-merge, the accumulated probability can go slightly above
1468 // REG_BR_PROB_BASE.
1469 if (prob[bb] > REG_BR_PROB_BASE)
1470 prob[bb] = REG_BR_PROB_BASE;
1473 bitmap_set_bit (dom[bb], bb);
1474 bitmap_and_compl (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
1476 if (sched_verbose >= 2)
1477 fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
1478 (100 * prob[bb]) / REG_BR_PROB_BASE);
1481 /* Functions for target info. */
1483 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1484 Note that bb_trg dominates bb_src. */
1486 static void
1487 split_edges (int bb_src, int bb_trg, edgelst *bl)
1489 sbitmap src = sbitmap_alloc (SBITMAP_SIZE (pot_split[bb_src]));
1490 bitmap_copy (src, pot_split[bb_src]);
1492 bitmap_and_compl (src, src, pot_split[bb_trg]);
1493 extract_edgelst (src, bl);
1494 sbitmap_free (src);
1497 /* Find the valid candidate-source-blocks for the target block TRG, compute
1498 their probability, and check if they are speculative or not.
1499 For speculative sources, compute their update-blocks and split-blocks. */
1501 static void
1502 compute_trg_info (int trg)
1504 candidate *sp;
1505 edgelst el = { NULL, 0 };
1506 int i, j, k, update_idx;
1507 basic_block block;
1508 sbitmap visited;
1509 edge_iterator ei;
1510 edge e;
1512 candidate_table = XNEWVEC (candidate, current_nr_blocks);
1514 bblst_last = 0;
1515 /* bblst_table holds split blocks and update blocks for each block after
1516 the current one in the region. split blocks and update blocks are
1517 the TO blocks of region edges, so there can be at most rgn_nr_edges
1518 of them. */
1519 bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
1520 bblst_table = XNEWVEC (basic_block, bblst_size);
1522 edgelst_last = 0;
1523 edgelst_table = XNEWVEC (edge, rgn_nr_edges);
1525 /* Define some of the fields for the target bb as well. */
1526 sp = candidate_table + trg;
1527 sp->is_valid = 1;
1528 sp->is_speculative = 0;
1529 sp->src_prob = REG_BR_PROB_BASE;
1531 visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
1533 for (i = trg + 1; i < current_nr_blocks; i++)
1535 sp = candidate_table + i;
1537 sp->is_valid = IS_DOMINATED (i, trg);
1538 if (sp->is_valid)
1540 int tf = prob[trg], cf = prob[i];
1542 /* In CFGs with low probability edges TF can possibly be zero. */
1543 sp->src_prob = (tf ? GCOV_COMPUTE_SCALE (cf, tf) : 0);
1544 sp->is_valid = (sp->src_prob >= min_spec_prob);
1547 if (sp->is_valid)
1549 split_edges (i, trg, &el);
1550 sp->is_speculative = (el.nr_members) ? 1 : 0;
1551 if (sp->is_speculative && !flag_schedule_speculative)
1552 sp->is_valid = 0;
1555 if (sp->is_valid)
1557 /* Compute split blocks and store them in bblst_table.
1558 The TO block of every split edge is a split block. */
1559 sp->split_bbs.first_member = &bblst_table[bblst_last];
1560 sp->split_bbs.nr_members = el.nr_members;
1561 for (j = 0; j < el.nr_members; bblst_last++, j++)
1562 bblst_table[bblst_last] = el.first_member[j]->dest;
1563 sp->update_bbs.first_member = &bblst_table[bblst_last];
1565 /* Compute update blocks and store them in bblst_table.
1566 For every split edge, look at the FROM block, and check
1567 all out edges. For each out edge that is not a split edge,
1568 add the TO block to the update block list. This list can end
1569 up with a lot of duplicates. We need to weed them out to avoid
1570 overrunning the end of the bblst_table. */
1572 update_idx = 0;
1573 bitmap_clear (visited);
1574 for (j = 0; j < el.nr_members; j++)
1576 block = el.first_member[j]->src;
1577 FOR_EACH_EDGE (e, ei, block->succs)
1579 if (!bitmap_bit_p (visited, e->dest->index))
1581 for (k = 0; k < el.nr_members; k++)
1582 if (e == el.first_member[k])
1583 break;
1585 if (k >= el.nr_members)
1587 bblst_table[bblst_last++] = e->dest;
1588 bitmap_set_bit (visited, e->dest->index);
1589 update_idx++;
1594 sp->update_bbs.nr_members = update_idx;
1596 /* Make sure we didn't overrun the end of bblst_table. */
1597 gcc_assert (bblst_last <= bblst_size);
1599 else
1601 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1603 sp->is_speculative = 0;
1604 sp->src_prob = 0;
1608 sbitmap_free (visited);
1611 /* Free the computed target info. */
1612 static void
1613 free_trg_info (void)
1615 free (candidate_table);
1616 free (bblst_table);
1617 free (edgelst_table);
1620 /* Print candidates info, for debugging purposes. Callable from debugger. */
1622 DEBUG_FUNCTION void
1623 debug_candidate (int i)
1625 if (!candidate_table[i].is_valid)
1626 return;
1628 if (candidate_table[i].is_speculative)
1630 int j;
1631 fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1633 fprintf (sched_dump, "split path: ");
1634 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1636 int b = candidate_table[i].split_bbs.first_member[j]->index;
1638 fprintf (sched_dump, " %d ", b);
1640 fprintf (sched_dump, "\n");
1642 fprintf (sched_dump, "update path: ");
1643 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
1645 int b = candidate_table[i].update_bbs.first_member[j]->index;
1647 fprintf (sched_dump, " %d ", b);
1649 fprintf (sched_dump, "\n");
1651 else
1653 fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
1657 /* Print candidates info, for debugging purposes. Callable from debugger. */
1659 DEBUG_FUNCTION void
1660 debug_candidates (int trg)
1662 int i;
1664 fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
1665 BB_TO_BLOCK (trg), trg);
1666 for (i = trg + 1; i < current_nr_blocks; i++)
1667 debug_candidate (i);
1670 /* Functions for speculative scheduling. */
1672 static bitmap_head not_in_df;
1674 /* Return 0 if x is a set of a register alive in the beginning of one
1675 of the split-blocks of src, otherwise return 1. */
1677 static int
1678 check_live_1 (int src, rtx x)
1680 int i;
1681 int regno;
1682 rtx reg = SET_DEST (x);
1684 if (reg == 0)
1685 return 1;
1687 while (GET_CODE (reg) == SUBREG
1688 || GET_CODE (reg) == ZERO_EXTRACT
1689 || GET_CODE (reg) == STRICT_LOW_PART)
1690 reg = XEXP (reg, 0);
1692 if (GET_CODE (reg) == PARALLEL)
1694 int i;
1696 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1697 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1698 if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
1699 return 1;
1701 return 0;
1704 if (!REG_P (reg))
1705 return 1;
1707 regno = REGNO (reg);
1709 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1711 /* Global registers are assumed live. */
1712 return 0;
1714 else
1716 if (regno < FIRST_PSEUDO_REGISTER)
1718 /* Check for hard registers. */
1719 int j = REG_NREGS (reg);
1720 while (--j >= 0)
1722 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1724 basic_block b = candidate_table[src].split_bbs.first_member[i];
1725 int t = bitmap_bit_p (&not_in_df, b->index);
1727 /* We can have split blocks, that were recently generated.
1728 Such blocks are always outside current region. */
1729 gcc_assert (!t || (CONTAINING_RGN (b->index)
1730 != CONTAINING_RGN (BB_TO_BLOCK (src))));
1732 if (t || REGNO_REG_SET_P (df_get_live_in (b), regno + j))
1733 return 0;
1737 else
1739 /* Check for pseudo registers. */
1740 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1742 basic_block b = candidate_table[src].split_bbs.first_member[i];
1743 int t = bitmap_bit_p (&not_in_df, b->index);
1745 gcc_assert (!t || (CONTAINING_RGN (b->index)
1746 != CONTAINING_RGN (BB_TO_BLOCK (src))));
1748 if (t || REGNO_REG_SET_P (df_get_live_in (b), regno))
1749 return 0;
1754 return 1;
1757 /* If x is a set of a register R, mark that R is alive in the beginning
1758 of every update-block of src. */
1760 static void
1761 update_live_1 (int src, rtx x)
1763 int i;
1764 int regno;
1765 rtx reg = SET_DEST (x);
1767 if (reg == 0)
1768 return;
1770 while (GET_CODE (reg) == SUBREG
1771 || GET_CODE (reg) == ZERO_EXTRACT
1772 || GET_CODE (reg) == STRICT_LOW_PART)
1773 reg = XEXP (reg, 0);
1775 if (GET_CODE (reg) == PARALLEL)
1777 int i;
1779 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1780 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1781 update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
1783 return;
1786 if (!REG_P (reg))
1787 return;
1789 /* Global registers are always live, so the code below does not apply
1790 to them. */
1792 regno = REGNO (reg);
1794 if (! HARD_REGISTER_NUM_P (regno)
1795 || !global_regs[regno])
1797 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1799 basic_block b = candidate_table[src].update_bbs.first_member[i];
1800 bitmap_set_range (df_get_live_in (b), regno, REG_NREGS (reg));
1805 /* Return 1 if insn can be speculatively moved from block src to trg,
1806 otherwise return 0. Called before first insertion of insn to
1807 ready-list or before the scheduling. */
1809 static int
1810 check_live (rtx_insn *insn, int src)
1812 /* Find the registers set by instruction. */
1813 if (GET_CODE (PATTERN (insn)) == SET
1814 || GET_CODE (PATTERN (insn)) == CLOBBER)
1815 return check_live_1 (src, PATTERN (insn));
1816 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1818 int j;
1819 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1820 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1821 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1822 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
1823 return 0;
1825 return 1;
1828 return 1;
1831 /* Update the live registers info after insn was moved speculatively from
1832 block src to trg. */
1834 static void
1835 update_live (rtx_insn *insn, int src)
1837 /* Find the registers set by instruction. */
1838 if (GET_CODE (PATTERN (insn)) == SET
1839 || GET_CODE (PATTERN (insn)) == CLOBBER)
1840 update_live_1 (src, PATTERN (insn));
1841 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1843 int j;
1844 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1845 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1846 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1847 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
1851 /* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1852 #define IS_REACHABLE(bb_from, bb_to) \
1853 (bb_from == bb_to \
1854 || IS_RGN_ENTRY (bb_from) \
1855 || (bitmap_bit_p (ancestor_edges[bb_to], \
1856 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK_FOR_FN (cfun, \
1857 BB_TO_BLOCK (bb_from)))))))
1859 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1861 static void
1862 set_spec_fed (rtx load_insn)
1864 sd_iterator_def sd_it;
1865 dep_t dep;
1867 FOR_EACH_DEP (load_insn, SD_LIST_FORW, sd_it, dep)
1868 if (DEP_TYPE (dep) == REG_DEP_TRUE)
1869 FED_BY_SPEC_LOAD (DEP_CON (dep)) = 1;
1872 /* On the path from the insn to load_insn_bb, find a conditional
1873 branch depending on insn, that guards the speculative load. */
1875 static int
1876 find_conditional_protection (rtx_insn *insn, int load_insn_bb)
1878 sd_iterator_def sd_it;
1879 dep_t dep;
1881 /* Iterate through DEF-USE forward dependences. */
1882 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
1884 rtx_insn *next = DEP_CON (dep);
1886 if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
1887 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
1888 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
1889 && load_insn_bb != INSN_BB (next)
1890 && DEP_TYPE (dep) == REG_DEP_TRUE
1891 && (JUMP_P (next)
1892 || find_conditional_protection (next, load_insn_bb)))
1893 return 1;
1895 return 0;
1896 } /* find_conditional_protection */
1898 /* Returns 1 if the same insn1 that participates in the computation
1899 of load_insn's address is feeding a conditional branch that is
1900 guarding on load_insn. This is true if we find two DEF-USE
1901 chains:
1902 insn1 -> ... -> conditional-branch
1903 insn1 -> ... -> load_insn,
1904 and if a flow path exists:
1905 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1906 and if insn1 is on the path
1907 region-entry -> ... -> bb_trg -> ... load_insn.
1909 Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
1910 Locate the branch by following INSN_FORW_DEPS from insn1. */
1912 static int
1913 is_conditionally_protected (rtx load_insn, int bb_src, int bb_trg)
1915 sd_iterator_def sd_it;
1916 dep_t dep;
1918 FOR_EACH_DEP (load_insn, SD_LIST_BACK, sd_it, dep)
1920 rtx_insn *insn1 = DEP_PRO (dep);
1922 /* Must be a DEF-USE dependence upon non-branch. */
1923 if (DEP_TYPE (dep) != REG_DEP_TRUE
1924 || JUMP_P (insn1))
1925 continue;
1927 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1928 if (INSN_BB (insn1) == bb_src
1929 || (CONTAINING_RGN (BLOCK_NUM (insn1))
1930 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
1931 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
1932 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
1933 continue;
1935 /* Now search for the conditional-branch. */
1936 if (find_conditional_protection (insn1, bb_src))
1937 return 1;
1939 /* Recursive step: search another insn1, "above" current insn1. */
1940 return is_conditionally_protected (insn1, bb_src, bb_trg);
1943 /* The chain does not exist. */
1944 return 0;
1945 } /* is_conditionally_protected */
1947 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1948 load_insn can move speculatively from bb_src to bb_trg. All the
1949 following must hold:
1951 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1952 (2) load_insn and load1 have a def-use dependence upon
1953 the same insn 'insn1'.
1954 (3) either load2 is in bb_trg, or:
1955 - there's only one split-block, and
1956 - load1 is on the escape path, and
1958 From all these we can conclude that the two loads access memory
1959 addresses that differ at most by a constant, and hence if moving
1960 load_insn would cause an exception, it would have been caused by
1961 load2 anyhow. */
1963 static int
1964 is_pfree (rtx load_insn, int bb_src, int bb_trg)
1966 sd_iterator_def back_sd_it;
1967 dep_t back_dep;
1968 candidate *candp = candidate_table + bb_src;
1970 if (candp->split_bbs.nr_members != 1)
1971 /* Must have exactly one escape block. */
1972 return 0;
1974 FOR_EACH_DEP (load_insn, SD_LIST_BACK, back_sd_it, back_dep)
1976 rtx_insn *insn1 = DEP_PRO (back_dep);
1978 if (DEP_TYPE (back_dep) == REG_DEP_TRUE)
1979 /* Found a DEF-USE dependence (insn1, load_insn). */
1981 sd_iterator_def fore_sd_it;
1982 dep_t fore_dep;
1984 FOR_EACH_DEP (insn1, SD_LIST_FORW, fore_sd_it, fore_dep)
1986 rtx_insn *insn2 = DEP_CON (fore_dep);
1988 if (DEP_TYPE (fore_dep) == REG_DEP_TRUE)
1990 /* Found a DEF-USE dependence (insn1, insn2). */
1991 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
1992 /* insn2 not guaranteed to be a 1 base reg load. */
1993 continue;
1995 if (INSN_BB (insn2) == bb_trg)
1996 /* insn2 is the similar load, in the target block. */
1997 return 1;
1999 if (*(candp->split_bbs.first_member) == BLOCK_FOR_INSN (insn2))
2000 /* insn2 is a similar load, in a split-block. */
2001 return 1;
2007 /* Couldn't find a similar load. */
2008 return 0;
2009 } /* is_pfree */
2011 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2012 a load moved speculatively, or if load_insn is protected by
2013 a compare on load_insn's address). */
2015 static int
2016 is_prisky (rtx load_insn, int bb_src, int bb_trg)
2018 if (FED_BY_SPEC_LOAD (load_insn))
2019 return 1;
2021 if (sd_lists_empty_p (load_insn, SD_LIST_BACK))
2022 /* Dependence may 'hide' out of the region. */
2023 return 1;
2025 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2026 return 1;
2028 return 0;
2031 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2032 Return 1 if insn is exception-free (and the motion is valid)
2033 and 0 otherwise. */
2035 static int
2036 is_exception_free (rtx_insn *insn, int bb_src, int bb_trg)
2038 int insn_class = haifa_classify_insn (insn);
2040 /* Handle non-load insns. */
2041 switch (insn_class)
2043 case TRAP_FREE:
2044 return 1;
2045 case TRAP_RISKY:
2046 return 0;
2047 default:;
2050 /* Handle loads. */
2051 if (!flag_schedule_speculative_load)
2052 return 0;
2053 IS_LOAD_INSN (insn) = 1;
2054 switch (insn_class)
2056 case IFREE:
2057 return (1);
2058 case IRISKY:
2059 return 0;
2060 case PFREE_CANDIDATE:
2061 if (is_pfree (insn, bb_src, bb_trg))
2062 return 1;
2063 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2064 case PRISKY_CANDIDATE:
2065 if (!flag_schedule_speculative_load_dangerous
2066 || is_prisky (insn, bb_src, bb_trg))
2067 return 0;
2068 break;
2069 default:;
2072 return flag_schedule_speculative_load_dangerous;
2075 /* The number of insns from the current block scheduled so far. */
2076 static int sched_target_n_insns;
2077 /* The number of insns from the current block to be scheduled in total. */
2078 static int target_n_insns;
2079 /* The number of insns from the entire region scheduled so far. */
2080 static int sched_n_insns;
2082 /* Implementations of the sched_info functions for region scheduling. */
2083 static void init_ready_list (void);
2084 static int can_schedule_ready_p (rtx_insn *);
2085 static void begin_schedule_ready (rtx_insn *);
2086 static ds_t new_ready (rtx_insn *, ds_t);
2087 static int schedule_more_p (void);
2088 static const char *rgn_print_insn (const rtx_insn *, int);
2089 static int rgn_rank (rtx_insn *, rtx_insn *);
2090 static void compute_jump_reg_dependencies (rtx, regset);
2092 /* Functions for speculative scheduling. */
2093 static void rgn_add_remove_insn (rtx_insn *, int);
2094 static void rgn_add_block (basic_block, basic_block);
2095 static void rgn_fix_recovery_cfg (int, int, int);
2096 static basic_block advance_target_bb (basic_block, rtx_insn *);
2098 /* Return nonzero if there are more insns that should be scheduled. */
2100 static int
2101 schedule_more_p (void)
2103 return sched_target_n_insns < target_n_insns;
2106 /* Add all insns that are initially ready to the ready list READY. Called
2107 once before scheduling a set of insns. */
2109 static void
2110 init_ready_list (void)
2112 rtx_insn *prev_head = current_sched_info->prev_head;
2113 rtx_insn *next_tail = current_sched_info->next_tail;
2114 int bb_src;
2115 rtx_insn *insn;
2117 target_n_insns = 0;
2118 sched_target_n_insns = 0;
2119 sched_n_insns = 0;
2121 /* Print debugging information. */
2122 if (sched_verbose >= 5)
2123 debug_rgn_dependencies (target_bb);
2125 /* Prepare current target block info. */
2126 if (current_nr_blocks > 1)
2127 compute_trg_info (target_bb);
2129 /* Initialize ready list with all 'ready' insns in target block.
2130 Count number of insns in the target block being scheduled. */
2131 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
2133 gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
2134 TODO_SPEC (insn) = HARD_DEP;
2135 try_ready (insn);
2136 target_n_insns++;
2138 gcc_assert (!(TODO_SPEC (insn) & BEGIN_CONTROL));
2141 /* Add to ready list all 'ready' insns in valid source blocks.
2142 For speculative insns, check-live, exception-free, and
2143 issue-delay. */
2144 for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
2145 if (IS_VALID (bb_src))
2147 rtx_insn *src_head;
2148 rtx_insn *src_next_tail;
2149 rtx_insn *tail, *head;
2151 get_ebb_head_tail (EBB_FIRST_BB (bb_src), EBB_LAST_BB (bb_src),
2152 &head, &tail);
2153 src_next_tail = NEXT_INSN (tail);
2154 src_head = head;
2156 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
2157 if (INSN_P (insn))
2159 gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
2160 TODO_SPEC (insn) = HARD_DEP;
2161 try_ready (insn);
2166 /* Called after taking INSN from the ready list. Returns nonzero if this
2167 insn can be scheduled, nonzero if we should silently discard it. */
2169 static int
2170 can_schedule_ready_p (rtx_insn *insn)
2172 /* An interblock motion? */
2173 if (INSN_BB (insn) != target_bb
2174 && IS_SPECULATIVE_INSN (insn)
2175 && !check_live (insn, INSN_BB (insn)))
2176 return 0;
2177 else
2178 return 1;
2181 /* Updates counter and other information. Split from can_schedule_ready_p ()
2182 because when we schedule insn speculatively then insn passed to
2183 can_schedule_ready_p () differs from the one passed to
2184 begin_schedule_ready (). */
2185 static void
2186 begin_schedule_ready (rtx_insn *insn)
2188 /* An interblock motion? */
2189 if (INSN_BB (insn) != target_bb)
2191 if (IS_SPECULATIVE_INSN (insn))
2193 gcc_assert (check_live (insn, INSN_BB (insn)));
2195 update_live (insn, INSN_BB (insn));
2197 /* For speculative load, mark insns fed by it. */
2198 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
2199 set_spec_fed (insn);
2201 nr_spec++;
2203 nr_inter++;
2205 else
2207 /* In block motion. */
2208 sched_target_n_insns++;
2210 sched_n_insns++;
2213 /* Called after INSN has all its hard dependencies resolved and the speculation
2214 of type TS is enough to overcome them all.
2215 Return nonzero if it should be moved to the ready list or the queue, or zero
2216 if we should silently discard it. */
2217 static ds_t
2218 new_ready (rtx_insn *next, ds_t ts)
2220 if (INSN_BB (next) != target_bb)
2222 int not_ex_free = 0;
2224 /* For speculative insns, before inserting to ready/queue,
2225 check live, exception-free, and issue-delay. */
2226 if (!IS_VALID (INSN_BB (next))
2227 || CANT_MOVE (next)
2228 || (IS_SPECULATIVE_INSN (next)
2229 && ((recog_memoized (next) >= 0
2230 && min_insn_conflict_delay (curr_state, next, next)
2231 > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY))
2232 || IS_SPECULATION_CHECK_P (next)
2233 || !check_live (next, INSN_BB (next))
2234 || (not_ex_free = !is_exception_free (next, INSN_BB (next),
2235 target_bb)))))
2237 if (not_ex_free
2238 /* We are here because is_exception_free () == false.
2239 But we possibly can handle that with control speculation. */
2240 && sched_deps_info->generate_spec_deps
2241 && spec_info->mask & BEGIN_CONTROL)
2243 ds_t new_ds;
2245 /* Add control speculation to NEXT's dependency type. */
2246 new_ds = set_dep_weak (ts, BEGIN_CONTROL, MAX_DEP_WEAK);
2248 /* Check if NEXT can be speculated with new dependency type. */
2249 if (sched_insn_is_legitimate_for_speculation_p (next, new_ds))
2250 /* Here we got new control-speculative instruction. */
2251 ts = new_ds;
2252 else
2253 /* NEXT isn't ready yet. */
2254 ts = DEP_POSTPONED;
2256 else
2257 /* NEXT isn't ready yet. */
2258 ts = DEP_POSTPONED;
2262 return ts;
2265 /* Return a string that contains the insn uid and optionally anything else
2266 necessary to identify this insn in an output. It's valid to use a
2267 static buffer for this. The ALIGNED parameter should cause the string
2268 to be formatted so that multiple output lines will line up nicely. */
2270 static const char *
2271 rgn_print_insn (const rtx_insn *insn, int aligned)
2273 static char tmp[80];
2275 if (aligned)
2276 sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
2277 else
2279 if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
2280 sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
2281 else
2282 sprintf (tmp, "%d", INSN_UID (insn));
2284 return tmp;
2287 /* Compare priority of two insns. Return a positive number if the second
2288 insn is to be preferred for scheduling, and a negative one if the first
2289 is to be preferred. Zero if they are equally good. */
2291 static int
2292 rgn_rank (rtx_insn *insn1, rtx_insn *insn2)
2294 /* Some comparison make sense in interblock scheduling only. */
2295 if (INSN_BB (insn1) != INSN_BB (insn2))
2297 int spec_val, prob_val;
2299 /* Prefer an inblock motion on an interblock motion. */
2300 if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
2301 return 1;
2302 if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
2303 return -1;
2305 /* Prefer a useful motion on a speculative one. */
2306 spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
2307 if (spec_val)
2308 return spec_val;
2310 /* Prefer a more probable (speculative) insn. */
2311 prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
2312 if (prob_val)
2313 return prob_val;
2315 return 0;
2318 /* NEXT is an instruction that depends on INSN (a backward dependence);
2319 return nonzero if we should include this dependence in priority
2320 calculations. */
2323 contributes_to_priority (rtx_insn *next, rtx_insn *insn)
2325 /* NEXT and INSN reside in one ebb. */
2326 return BLOCK_TO_BB (BLOCK_NUM (next)) == BLOCK_TO_BB (BLOCK_NUM (insn));
2329 /* INSN is a JUMP_INSN. Store the set of registers that must be
2330 considered as used by this jump in USED. */
2332 static void
2333 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
2334 regset used ATTRIBUTE_UNUSED)
2336 /* Nothing to do here, since we postprocess jumps in
2337 add_branch_dependences. */
2340 /* This variable holds common_sched_info hooks and data relevant to
2341 the interblock scheduler. */
2342 static struct common_sched_info_def rgn_common_sched_info;
2345 /* This holds data for the dependence analysis relevant to
2346 the interblock scheduler. */
2347 static struct sched_deps_info_def rgn_sched_deps_info;
2349 /* This holds constant data used for initializing the above structure
2350 for the Haifa scheduler. */
2351 static const struct sched_deps_info_def rgn_const_sched_deps_info =
2353 compute_jump_reg_dependencies,
2354 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
2355 0, 0, 0
2358 /* Same as above, but for the selective scheduler. */
2359 static const struct sched_deps_info_def rgn_const_sel_sched_deps_info =
2361 compute_jump_reg_dependencies,
2362 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
2363 0, 0, 0
2366 /* Return true if scheduling INSN will trigger finish of scheduling
2367 current block. */
2368 static bool
2369 rgn_insn_finishes_block_p (rtx_insn *insn)
2371 if (INSN_BB (insn) == target_bb
2372 && sched_target_n_insns + 1 == target_n_insns)
2373 /* INSN is the last not-scheduled instruction in the current block. */
2374 return true;
2376 return false;
2379 /* Used in schedule_insns to initialize current_sched_info for scheduling
2380 regions (or single basic blocks). */
2382 static const struct haifa_sched_info rgn_const_sched_info =
2384 init_ready_list,
2385 can_schedule_ready_p,
2386 schedule_more_p,
2387 new_ready,
2388 rgn_rank,
2389 rgn_print_insn,
2390 contributes_to_priority,
2391 rgn_insn_finishes_block_p,
2393 NULL, NULL,
2394 NULL, NULL,
2395 0, 0,
2397 rgn_add_remove_insn,
2398 begin_schedule_ready,
2399 NULL,
2400 advance_target_bb,
2401 NULL, NULL,
2402 SCHED_RGN
2405 /* This variable holds the data and hooks needed to the Haifa scheduler backend
2406 for the interblock scheduler frontend. */
2407 static struct haifa_sched_info rgn_sched_info;
2409 /* Returns maximum priority that an insn was assigned to. */
2412 get_rgn_sched_max_insns_priority (void)
2414 return rgn_sched_info.sched_max_insns_priority;
2417 /* Determine if PAT sets a TARGET_CLASS_LIKELY_SPILLED_P register. */
2419 static bool
2420 sets_likely_spilled (rtx pat)
2422 bool ret = false;
2423 note_stores (pat, sets_likely_spilled_1, &ret);
2424 return ret;
2427 static void
2428 sets_likely_spilled_1 (rtx x, const_rtx pat, void *data)
2430 bool *ret = (bool *) data;
2432 if (GET_CODE (pat) == SET
2433 && REG_P (x)
2434 && HARD_REGISTER_P (x)
2435 && targetm.class_likely_spilled_p (REGNO_REG_CLASS (REGNO (x))))
2436 *ret = true;
2439 /* A bitmap to note insns that participate in any dependency. Used in
2440 add_branch_dependences. */
2441 static sbitmap insn_referenced;
2443 /* Add dependences so that branches are scheduled to run last in their
2444 block. */
2445 static void
2446 add_branch_dependences (rtx_insn *head, rtx_insn *tail)
2448 rtx_insn *insn, *last;
2450 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2451 that can throw exceptions, force them to remain in order at the end of
2452 the block by adding dependencies and giving the last a high priority.
2453 There may be notes present, and prev_head may also be a note.
2455 Branches must obviously remain at the end. Calls should remain at the
2456 end since moving them results in worse register allocation. Uses remain
2457 at the end to ensure proper register allocation.
2459 cc0 setters remain at the end because they can't be moved away from
2460 their cc0 user.
2462 Predecessors of SCHED_GROUP_P instructions at the end remain at the end.
2464 COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
2466 Insns setting TARGET_CLASS_LIKELY_SPILLED_P registers (usually return
2467 values) are not moved before reload because we can wind up with register
2468 allocation failures. */
2470 while (tail != head && DEBUG_INSN_P (tail))
2471 tail = PREV_INSN (tail);
2473 insn = tail;
2474 last = 0;
2475 while (CALL_P (insn)
2476 || JUMP_P (insn) || JUMP_TABLE_DATA_P (insn)
2477 || (NONJUMP_INSN_P (insn)
2478 && (GET_CODE (PATTERN (insn)) == USE
2479 || GET_CODE (PATTERN (insn)) == CLOBBER
2480 || can_throw_internal (insn)
2481 || (HAVE_cc0 && sets_cc0_p (PATTERN (insn)))
2482 || (!reload_completed
2483 && sets_likely_spilled (PATTERN (insn)))))
2484 || NOTE_P (insn)
2485 || (last != 0 && SCHED_GROUP_P (last)))
2487 if (!NOTE_P (insn))
2489 if (last != 0
2490 && sd_find_dep_between (insn, last, false) == NULL)
2492 if (! sched_insns_conditions_mutex_p (last, insn))
2493 add_dependence (last, insn, REG_DEP_ANTI);
2494 bitmap_set_bit (insn_referenced, INSN_LUID (insn));
2497 CANT_MOVE (insn) = 1;
2499 last = insn;
2502 /* Don't overrun the bounds of the basic block. */
2503 if (insn == head)
2504 break;
2507 insn = PREV_INSN (insn);
2508 while (insn != head && DEBUG_INSN_P (insn));
2511 /* Make sure these insns are scheduled last in their block. */
2512 insn = last;
2513 if (insn != 0)
2514 while (insn != head)
2516 insn = prev_nonnote_insn (insn);
2518 if (bitmap_bit_p (insn_referenced, INSN_LUID (insn))
2519 || DEBUG_INSN_P (insn))
2520 continue;
2522 if (! sched_insns_conditions_mutex_p (last, insn))
2523 add_dependence (last, insn, REG_DEP_ANTI);
2526 if (!targetm.have_conditional_execution ())
2527 return;
2529 /* Finally, if the block ends in a jump, and we are doing intra-block
2530 scheduling, make sure that the branch depends on any COND_EXEC insns
2531 inside the block to avoid moving the COND_EXECs past the branch insn.
2533 We only have to do this after reload, because (1) before reload there
2534 are no COND_EXEC insns, and (2) the region scheduler is an intra-block
2535 scheduler after reload.
2537 FIXME: We could in some cases move COND_EXEC insns past the branch if
2538 this scheduler would be a little smarter. Consider this code:
2540 T = [addr]
2541 C ? addr += 4
2542 !C ? X += 12
2543 C ? T += 1
2544 C ? jump foo
2546 On a target with a one cycle stall on a memory access the optimal
2547 sequence would be:
2549 T = [addr]
2550 C ? addr += 4
2551 C ? T += 1
2552 C ? jump foo
2553 !C ? X += 12
2555 We don't want to put the 'X += 12' before the branch because it just
2556 wastes a cycle of execution time when the branch is taken.
2558 Note that in the example "!C" will always be true. That is another
2559 possible improvement for handling COND_EXECs in this scheduler: it
2560 could remove always-true predicates. */
2562 if (!reload_completed || ! (JUMP_P (tail) || JUMP_TABLE_DATA_P (tail)))
2563 return;
2565 insn = tail;
2566 while (insn != head)
2568 insn = PREV_INSN (insn);
2570 /* Note that we want to add this dependency even when
2571 sched_insns_conditions_mutex_p returns true. The whole point
2572 is that we _want_ this dependency, even if these insns really
2573 are independent. */
2574 if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC)
2575 add_dependence (tail, insn, REG_DEP_ANTI);
2579 /* Data structures for the computation of data dependences in a regions. We
2580 keep one `deps' structure for every basic block. Before analyzing the
2581 data dependences for a bb, its variables are initialized as a function of
2582 the variables of its predecessors. When the analysis for a bb completes,
2583 we save the contents to the corresponding bb_deps[bb] variable. */
2585 static struct deps_desc *bb_deps;
2587 static void
2588 concat_insn_mem_list (rtx_insn_list *copy_insns,
2589 rtx_expr_list *copy_mems,
2590 rtx_insn_list **old_insns_p,
2591 rtx_expr_list **old_mems_p)
2593 rtx_insn_list *new_insns = *old_insns_p;
2594 rtx_expr_list *new_mems = *old_mems_p;
2596 while (copy_insns)
2598 new_insns = alloc_INSN_LIST (copy_insns->insn (), new_insns);
2599 new_mems = alloc_EXPR_LIST (VOIDmode, copy_mems->element (), new_mems);
2600 copy_insns = copy_insns->next ();
2601 copy_mems = copy_mems->next ();
2604 *old_insns_p = new_insns;
2605 *old_mems_p = new_mems;
2608 /* Join PRED_DEPS to the SUCC_DEPS. */
2609 void
2610 deps_join (struct deps_desc *succ_deps, struct deps_desc *pred_deps)
2612 unsigned reg;
2613 reg_set_iterator rsi;
2615 /* The reg_last lists are inherited by successor. */
2616 EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi)
2618 struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
2619 struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
2621 succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
2622 succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
2623 succ_rl->implicit_sets
2624 = concat_INSN_LIST (pred_rl->implicit_sets, succ_rl->implicit_sets);
2625 succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
2626 succ_rl->clobbers);
2627 succ_rl->uses_length += pred_rl->uses_length;
2628 succ_rl->clobbers_length += pred_rl->clobbers_length;
2630 IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
2632 /* Mem read/write lists are inherited by successor. */
2633 concat_insn_mem_list (pred_deps->pending_read_insns,
2634 pred_deps->pending_read_mems,
2635 &succ_deps->pending_read_insns,
2636 &succ_deps->pending_read_mems);
2637 concat_insn_mem_list (pred_deps->pending_write_insns,
2638 pred_deps->pending_write_mems,
2639 &succ_deps->pending_write_insns,
2640 &succ_deps->pending_write_mems);
2642 succ_deps->pending_jump_insns
2643 = concat_INSN_LIST (pred_deps->pending_jump_insns,
2644 succ_deps->pending_jump_insns);
2645 succ_deps->last_pending_memory_flush
2646 = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
2647 succ_deps->last_pending_memory_flush);
2649 succ_deps->pending_read_list_length += pred_deps->pending_read_list_length;
2650 succ_deps->pending_write_list_length += pred_deps->pending_write_list_length;
2651 succ_deps->pending_flush_length += pred_deps->pending_flush_length;
2653 /* last_function_call is inherited by successor. */
2654 succ_deps->last_function_call
2655 = concat_INSN_LIST (pred_deps->last_function_call,
2656 succ_deps->last_function_call);
2658 /* last_function_call_may_noreturn is inherited by successor. */
2659 succ_deps->last_function_call_may_noreturn
2660 = concat_INSN_LIST (pred_deps->last_function_call_may_noreturn,
2661 succ_deps->last_function_call_may_noreturn);
2663 /* sched_before_next_call is inherited by successor. */
2664 succ_deps->sched_before_next_call
2665 = concat_INSN_LIST (pred_deps->sched_before_next_call,
2666 succ_deps->sched_before_next_call);
2669 /* After computing the dependencies for block BB, propagate the dependencies
2670 found in TMP_DEPS to the successors of the block. */
2671 static void
2672 propagate_deps (int bb, struct deps_desc *pred_deps)
2674 basic_block block = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb));
2675 edge_iterator ei;
2676 edge e;
2678 /* bb's structures are inherited by its successors. */
2679 FOR_EACH_EDGE (e, ei, block->succs)
2681 /* Only bbs "below" bb, in the same region, are interesting. */
2682 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2683 || CONTAINING_RGN (block->index) != CONTAINING_RGN (e->dest->index)
2684 || BLOCK_TO_BB (e->dest->index) <= bb)
2685 continue;
2687 deps_join (bb_deps + BLOCK_TO_BB (e->dest->index), pred_deps);
2690 /* These lists should point to the right place, for correct
2691 freeing later. */
2692 bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
2693 bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
2694 bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
2695 bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
2696 bb_deps[bb].pending_jump_insns = pred_deps->pending_jump_insns;
2698 /* Can't allow these to be freed twice. */
2699 pred_deps->pending_read_insns = 0;
2700 pred_deps->pending_read_mems = 0;
2701 pred_deps->pending_write_insns = 0;
2702 pred_deps->pending_write_mems = 0;
2703 pred_deps->pending_jump_insns = 0;
2706 /* Compute dependences inside bb. In a multiple blocks region:
2707 (1) a bb is analyzed after its predecessors, and (2) the lists in
2708 effect at the end of bb (after analyzing for bb) are inherited by
2709 bb's successors.
2711 Specifically for reg-reg data dependences, the block insns are
2712 scanned by sched_analyze () top-to-bottom. Three lists are
2713 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2714 reg_last[].implicit_sets for implicit hard register DEFs, and
2715 reg_last[].uses for register USEs.
2717 When analysis is completed for bb, we update for its successors:
2718 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2719 ; - IMPLICIT_DEFS[succ] = Union (IMPLICIT_DEFS [succ], IMPLICIT_DEFS [bb])
2720 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2722 The mechanism for computing mem-mem data dependence is very
2723 similar, and the result is interblock dependences in the region. */
2725 static void
2726 compute_block_dependences (int bb)
2728 rtx_insn *head, *tail;
2729 struct deps_desc tmp_deps;
2731 tmp_deps = bb_deps[bb];
2733 /* Do the analysis for this block. */
2734 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2735 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2737 sched_analyze (&tmp_deps, head, tail);
2739 /* Selective scheduling handles control dependencies by itself. */
2740 if (!sel_sched_p ())
2741 add_branch_dependences (head, tail);
2743 if (current_nr_blocks > 1)
2744 propagate_deps (bb, &tmp_deps);
2746 /* Free up the INSN_LISTs. */
2747 free_deps (&tmp_deps);
2749 if (targetm.sched.dependencies_evaluation_hook)
2750 targetm.sched.dependencies_evaluation_hook (head, tail);
2753 /* Free dependencies of instructions inside BB. */
2754 static void
2755 free_block_dependencies (int bb)
2757 rtx_insn *head;
2758 rtx_insn *tail;
2760 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2762 if (no_real_insns_p (head, tail))
2763 return;
2765 sched_free_deps (head, tail, true);
2768 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2769 them to the unused_*_list variables, so that they can be reused. */
2771 static void
2772 free_pending_lists (void)
2774 int bb;
2776 for (bb = 0; bb < current_nr_blocks; bb++)
2778 free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
2779 free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
2780 free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
2781 free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
2782 free_INSN_LIST_list (&bb_deps[bb].pending_jump_insns);
2786 /* Print dependences for debugging starting from FROM_BB.
2787 Callable from debugger. */
2788 /* Print dependences for debugging starting from FROM_BB.
2789 Callable from debugger. */
2790 DEBUG_FUNCTION void
2791 debug_rgn_dependencies (int from_bb)
2793 int bb;
2795 fprintf (sched_dump,
2796 ";; --------------- forward dependences: ------------ \n");
2798 for (bb = from_bb; bb < current_nr_blocks; bb++)
2800 rtx_insn *head, *tail;
2802 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2803 fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
2804 BB_TO_BLOCK (bb), bb);
2806 debug_dependencies (head, tail);
2810 /* Print dependencies information for instructions between HEAD and TAIL.
2811 ??? This function would probably fit best in haifa-sched.c. */
2812 void debug_dependencies (rtx_insn *head, rtx_insn *tail)
2814 rtx_insn *insn;
2815 rtx_insn *next_tail = NEXT_INSN (tail);
2817 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2818 "insn", "code", "bb", "dep", "prio", "cost",
2819 "reservation");
2820 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2821 "----", "----", "--", "---", "----", "----",
2822 "-----------");
2824 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2826 if (! INSN_P (insn))
2828 int n;
2829 fprintf (sched_dump, ";; %6d ", INSN_UID (insn));
2830 if (NOTE_P (insn))
2832 n = NOTE_KIND (insn);
2833 fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
2835 else
2836 fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
2837 continue;
2840 fprintf (sched_dump,
2841 ";; %s%5d%6d%6d%6d%6d%6d ",
2842 (SCHED_GROUP_P (insn) ? "+" : " "),
2843 INSN_UID (insn),
2844 INSN_CODE (insn),
2845 BLOCK_NUM (insn),
2846 sched_emulate_haifa_p ? -1 : sd_lists_size (insn, SD_LIST_BACK),
2847 (sel_sched_p () ? (sched_emulate_haifa_p ? -1
2848 : INSN_PRIORITY (insn))
2849 : INSN_PRIORITY (insn)),
2850 (sel_sched_p () ? (sched_emulate_haifa_p ? -1
2851 : insn_cost (insn))
2852 : insn_cost (insn)));
2854 if (recog_memoized (insn) < 0)
2855 fprintf (sched_dump, "nothing");
2856 else
2857 print_reservation (sched_dump, insn);
2859 fprintf (sched_dump, "\t: ");
2861 sd_iterator_def sd_it;
2862 dep_t dep;
2864 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
2865 fprintf (sched_dump, "%d%s%s ", INSN_UID (DEP_CON (dep)),
2866 DEP_NONREG (dep) ? "n" : "",
2867 DEP_MULTIPLE (dep) ? "m" : "");
2869 fprintf (sched_dump, "\n");
2872 fprintf (sched_dump, "\n");
2875 /* Returns true if all the basic blocks of the current region have
2876 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
2877 bool
2878 sched_is_disabled_for_current_region_p (void)
2880 int bb;
2882 for (bb = 0; bb < current_nr_blocks; bb++)
2883 if (!(BASIC_BLOCK_FOR_FN (cfun,
2884 BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE))
2885 return false;
2887 return true;
2890 /* Free all region dependencies saved in INSN_BACK_DEPS and
2891 INSN_RESOLVED_BACK_DEPS. The Haifa scheduler does this on the fly
2892 when scheduling, so this function is supposed to be called from
2893 the selective scheduling only. */
2894 void
2895 free_rgn_deps (void)
2897 int bb;
2899 for (bb = 0; bb < current_nr_blocks; bb++)
2901 rtx_insn *head, *tail;
2903 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2904 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2906 sched_free_deps (head, tail, false);
2910 static int rgn_n_insns;
2912 /* Compute insn priority for a current region. */
2913 void
2914 compute_priorities (void)
2916 int bb;
2918 current_sched_info->sched_max_insns_priority = 0;
2919 for (bb = 0; bb < current_nr_blocks; bb++)
2921 rtx_insn *head, *tail;
2923 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2924 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2926 if (no_real_insns_p (head, tail))
2927 continue;
2929 rgn_n_insns += set_priorities (head, tail);
2931 current_sched_info->sched_max_insns_priority++;
2934 /* (Re-)initialize the arrays of DFA states at the end of each basic block.
2936 SAVED_LAST_BASIC_BLOCK is the previous length of the arrays. It must be
2937 zero for the first call to this function, to allocate the arrays for the
2938 first time.
2940 This function is called once during initialization of the scheduler, and
2941 called again to resize the arrays if new basic blocks have been created,
2942 for example for speculation recovery code. */
2944 static void
2945 realloc_bb_state_array (int saved_last_basic_block)
2947 char *old_bb_state_array = bb_state_array;
2948 size_t lbb = (size_t) last_basic_block_for_fn (cfun);
2949 size_t slbb = (size_t) saved_last_basic_block;
2951 /* Nothing to do if nothing changed since the last time this was called. */
2952 if (saved_last_basic_block == last_basic_block_for_fn (cfun))
2953 return;
2955 /* The selective scheduler doesn't use the state arrays. */
2956 if (sel_sched_p ())
2958 gcc_assert (bb_state_array == NULL && bb_state == NULL);
2959 return;
2962 gcc_checking_assert (saved_last_basic_block == 0
2963 || (bb_state_array != NULL && bb_state != NULL));
2965 bb_state_array = XRESIZEVEC (char, bb_state_array, lbb * dfa_state_size);
2966 bb_state = XRESIZEVEC (state_t, bb_state, lbb);
2968 /* If BB_STATE_ARRAY has moved, fixup all the state pointers array.
2969 Otherwise only fixup the newly allocated ones. For the state
2970 array itself, only initialize the new entries. */
2971 bool bb_state_array_moved = (bb_state_array != old_bb_state_array);
2972 for (size_t i = bb_state_array_moved ? 0 : slbb; i < lbb; i++)
2973 bb_state[i] = (state_t) (bb_state_array + i * dfa_state_size);
2974 for (size_t i = slbb; i < lbb; i++)
2975 state_reset (bb_state[i]);
2978 /* Free the arrays of DFA states at the end of each basic block. */
2980 static void
2981 free_bb_state_array (void)
2983 free (bb_state_array);
2984 free (bb_state);
2985 bb_state_array = NULL;
2986 bb_state = NULL;
2989 /* Schedule a region. A region is either an inner loop, a loop-free
2990 subroutine, or a single basic block. Each bb in the region is
2991 scheduled after its flow predecessors. */
2993 static void
2994 schedule_region (int rgn)
2996 int bb;
2997 int sched_rgn_n_insns = 0;
2999 rgn_n_insns = 0;
3001 /* Do not support register pressure sensitive scheduling for the new regions
3002 as we don't update the liveness info for them. */
3003 if (sched_pressure != SCHED_PRESSURE_NONE
3004 && rgn >= nr_regions_initial)
3006 free_global_sched_pressure_data ();
3007 sched_pressure = SCHED_PRESSURE_NONE;
3010 rgn_setup_region (rgn);
3012 /* Don't schedule region that is marked by
3013 NOTE_DISABLE_SCHED_OF_BLOCK. */
3014 if (sched_is_disabled_for_current_region_p ())
3015 return;
3017 sched_rgn_compute_dependencies (rgn);
3019 sched_rgn_local_init (rgn);
3021 /* Set priorities. */
3022 compute_priorities ();
3024 sched_extend_ready_list (rgn_n_insns);
3026 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
3028 sched_init_region_reg_pressure_info ();
3029 for (bb = 0; bb < current_nr_blocks; bb++)
3031 basic_block first_bb, last_bb;
3032 rtx_insn *head, *tail;
3034 first_bb = EBB_FIRST_BB (bb);
3035 last_bb = EBB_LAST_BB (bb);
3037 get_ebb_head_tail (first_bb, last_bb, &head, &tail);
3039 if (no_real_insns_p (head, tail))
3041 gcc_assert (first_bb == last_bb);
3042 continue;
3044 sched_setup_bb_reg_pressure_info (first_bb, PREV_INSN (head));
3048 /* Now we can schedule all blocks. */
3049 for (bb = 0; bb < current_nr_blocks; bb++)
3051 basic_block first_bb, last_bb, curr_bb;
3052 rtx_insn *head, *tail;
3054 first_bb = EBB_FIRST_BB (bb);
3055 last_bb = EBB_LAST_BB (bb);
3057 get_ebb_head_tail (first_bb, last_bb, &head, &tail);
3059 if (no_real_insns_p (head, tail))
3061 gcc_assert (first_bb == last_bb);
3062 continue;
3065 current_sched_info->prev_head = PREV_INSN (head);
3066 current_sched_info->next_tail = NEXT_INSN (tail);
3068 remove_notes (head, tail);
3070 unlink_bb_notes (first_bb, last_bb);
3072 target_bb = bb;
3074 gcc_assert (flag_schedule_interblock || current_nr_blocks == 1);
3075 current_sched_info->queue_must_finish_empty = current_nr_blocks == 1;
3077 curr_bb = first_bb;
3078 if (dbg_cnt (sched_block))
3080 edge f;
3081 int saved_last_basic_block = last_basic_block_for_fn (cfun);
3083 schedule_block (&curr_bb, bb_state[first_bb->index]);
3084 gcc_assert (EBB_FIRST_BB (bb) == first_bb);
3085 sched_rgn_n_insns += sched_n_insns;
3086 realloc_bb_state_array (saved_last_basic_block);
3087 f = find_fallthru_edge (last_bb->succs);
3088 if (f && f->probability * 100 / REG_BR_PROB_BASE >=
3089 PARAM_VALUE (PARAM_SCHED_STATE_EDGE_PROB_CUTOFF))
3091 memcpy (bb_state[f->dest->index], curr_state,
3092 dfa_state_size);
3093 if (sched_verbose >= 5)
3094 fprintf (sched_dump, "saving state for edge %d->%d\n",
3095 f->src->index, f->dest->index);
3098 else
3100 sched_rgn_n_insns += rgn_n_insns;
3103 /* Clean up. */
3104 if (current_nr_blocks > 1)
3105 free_trg_info ();
3108 /* Sanity check: verify that all region insns were scheduled. */
3109 gcc_assert (sched_rgn_n_insns == rgn_n_insns);
3111 sched_finish_ready_list ();
3113 /* Done with this region. */
3114 sched_rgn_local_finish ();
3116 /* Free dependencies. */
3117 for (bb = 0; bb < current_nr_blocks; ++bb)
3118 free_block_dependencies (bb);
3120 gcc_assert (haifa_recovery_bb_ever_added_p
3121 || deps_pools_are_empty_p ());
3124 /* Initialize data structures for region scheduling. */
3126 void
3127 sched_rgn_init (bool single_blocks_p)
3129 min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE)
3130 / 100);
3132 nr_inter = 0;
3133 nr_spec = 0;
3135 extend_regions ();
3137 CONTAINING_RGN (ENTRY_BLOCK) = -1;
3138 CONTAINING_RGN (EXIT_BLOCK) = -1;
3140 realloc_bb_state_array (0);
3142 /* Compute regions for scheduling. */
3143 if (single_blocks_p
3144 || n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS + 1
3145 || !flag_schedule_interblock
3146 || is_cfg_nonregular ())
3148 find_single_block_region (sel_sched_p ());
3150 else
3152 /* Compute the dominators and post dominators. */
3153 if (!sel_sched_p ())
3154 calculate_dominance_info (CDI_DOMINATORS);
3156 /* Find regions. */
3157 find_rgns ();
3159 if (sched_verbose >= 3)
3160 debug_regions ();
3162 /* For now. This will move as more and more of haifa is converted
3163 to using the cfg code. */
3164 if (!sel_sched_p ())
3165 free_dominance_info (CDI_DOMINATORS);
3168 gcc_assert (0 < nr_regions && nr_regions <= n_basic_blocks_for_fn (cfun));
3170 RGN_BLOCKS (nr_regions) = (RGN_BLOCKS (nr_regions - 1) +
3171 RGN_NR_BLOCKS (nr_regions - 1));
3172 nr_regions_initial = nr_regions;
3175 /* Free data structures for region scheduling. */
3176 void
3177 sched_rgn_finish (void)
3179 free_bb_state_array ();
3181 /* Reposition the prologue and epilogue notes in case we moved the
3182 prologue/epilogue insns. */
3183 if (reload_completed)
3184 reposition_prologue_and_epilogue_notes ();
3186 if (sched_verbose)
3188 if (reload_completed == 0
3189 && flag_schedule_interblock)
3191 fprintf (sched_dump,
3192 "\n;; Procedure interblock/speculative motions == %d/%d \n",
3193 nr_inter, nr_spec);
3195 else
3196 gcc_assert (nr_inter <= 0);
3197 fprintf (sched_dump, "\n\n");
3200 nr_regions = 0;
3202 free (rgn_table);
3203 rgn_table = NULL;
3205 free (rgn_bb_table);
3206 rgn_bb_table = NULL;
3208 free (block_to_bb);
3209 block_to_bb = NULL;
3211 free (containing_rgn);
3212 containing_rgn = NULL;
3214 free (ebb_head);
3215 ebb_head = NULL;
3218 /* Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
3219 point to the region RGN. */
3220 void
3221 rgn_setup_region (int rgn)
3223 int bb;
3225 /* Set variables for the current region. */
3226 current_nr_blocks = RGN_NR_BLOCKS (rgn);
3227 current_blocks = RGN_BLOCKS (rgn);
3229 /* EBB_HEAD is a region-scope structure. But we realloc it for
3230 each region to save time/memory/something else.
3231 See comments in add_block1, for what reasons we allocate +1 element. */
3232 ebb_head = XRESIZEVEC (int, ebb_head, current_nr_blocks + 1);
3233 for (bb = 0; bb <= current_nr_blocks; bb++)
3234 ebb_head[bb] = current_blocks + bb;
3237 /* Compute instruction dependencies in region RGN. */
3238 void
3239 sched_rgn_compute_dependencies (int rgn)
3241 if (!RGN_DONT_CALC_DEPS (rgn))
3243 int bb;
3245 if (sel_sched_p ())
3246 sched_emulate_haifa_p = 1;
3248 init_deps_global ();
3250 /* Initializations for region data dependence analysis. */
3251 bb_deps = XNEWVEC (struct deps_desc, current_nr_blocks);
3252 for (bb = 0; bb < current_nr_blocks; bb++)
3253 init_deps (bb_deps + bb, false);
3255 /* Initialize bitmap used in add_branch_dependences. */
3256 insn_referenced = sbitmap_alloc (sched_max_luid);
3257 bitmap_clear (insn_referenced);
3259 /* Compute backward dependencies. */
3260 for (bb = 0; bb < current_nr_blocks; bb++)
3261 compute_block_dependences (bb);
3263 sbitmap_free (insn_referenced);
3264 free_pending_lists ();
3265 finish_deps_global ();
3266 free (bb_deps);
3268 /* We don't want to recalculate this twice. */
3269 RGN_DONT_CALC_DEPS (rgn) = 1;
3271 if (sel_sched_p ())
3272 sched_emulate_haifa_p = 0;
3274 else
3275 /* (This is a recovery block. It is always a single block region.)
3276 OR (We use selective scheduling.) */
3277 gcc_assert (current_nr_blocks == 1 || sel_sched_p ());
3280 /* Init region data structures. Returns true if this region should
3281 not be scheduled. */
3282 void
3283 sched_rgn_local_init (int rgn)
3285 int bb;
3287 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
3288 if (current_nr_blocks > 1)
3290 basic_block block;
3291 edge e;
3292 edge_iterator ei;
3294 prob = XNEWVEC (int, current_nr_blocks);
3296 dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
3297 bitmap_vector_clear (dom, current_nr_blocks);
3299 /* Use ->aux to implement EDGE_TO_BIT mapping. */
3300 rgn_nr_edges = 0;
3301 FOR_EACH_BB_FN (block, cfun)
3303 if (CONTAINING_RGN (block->index) != rgn)
3304 continue;
3305 FOR_EACH_EDGE (e, ei, block->succs)
3306 SET_EDGE_TO_BIT (e, rgn_nr_edges++);
3309 rgn_edges = XNEWVEC (edge, rgn_nr_edges);
3310 rgn_nr_edges = 0;
3311 FOR_EACH_BB_FN (block, cfun)
3313 if (CONTAINING_RGN (block->index) != rgn)
3314 continue;
3315 FOR_EACH_EDGE (e, ei, block->succs)
3316 rgn_edges[rgn_nr_edges++] = e;
3319 /* Split edges. */
3320 pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
3321 bitmap_vector_clear (pot_split, current_nr_blocks);
3322 ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
3323 bitmap_vector_clear (ancestor_edges, current_nr_blocks);
3325 /* Compute probabilities, dominators, split_edges. */
3326 for (bb = 0; bb < current_nr_blocks; bb++)
3327 compute_dom_prob_ps (bb);
3329 /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
3330 /* We don't need them anymore. But we want to avoid duplication of
3331 aux fields in the newly created edges. */
3332 FOR_EACH_BB_FN (block, cfun)
3334 if (CONTAINING_RGN (block->index) != rgn)
3335 continue;
3336 FOR_EACH_EDGE (e, ei, block->succs)
3337 e->aux = NULL;
3342 /* Free data computed for the finished region. */
3343 void
3344 sched_rgn_local_free (void)
3346 free (prob);
3347 sbitmap_vector_free (dom);
3348 sbitmap_vector_free (pot_split);
3349 sbitmap_vector_free (ancestor_edges);
3350 free (rgn_edges);
3353 /* Free data computed for the finished region. */
3354 void
3355 sched_rgn_local_finish (void)
3357 if (current_nr_blocks > 1 && !sel_sched_p ())
3359 sched_rgn_local_free ();
3363 /* Setup scheduler infos. */
3364 void
3365 rgn_setup_common_sched_info (void)
3367 memcpy (&rgn_common_sched_info, &haifa_common_sched_info,
3368 sizeof (rgn_common_sched_info));
3370 rgn_common_sched_info.fix_recovery_cfg = rgn_fix_recovery_cfg;
3371 rgn_common_sched_info.add_block = rgn_add_block;
3372 rgn_common_sched_info.estimate_number_of_insns
3373 = rgn_estimate_number_of_insns;
3374 rgn_common_sched_info.sched_pass_id = SCHED_RGN_PASS;
3376 common_sched_info = &rgn_common_sched_info;
3379 /* Setup all *_sched_info structures (for the Haifa frontend
3380 and for the dependence analysis) in the interblock scheduler. */
3381 void
3382 rgn_setup_sched_infos (void)
3384 if (!sel_sched_p ())
3385 memcpy (&rgn_sched_deps_info, &rgn_const_sched_deps_info,
3386 sizeof (rgn_sched_deps_info));
3387 else
3388 memcpy (&rgn_sched_deps_info, &rgn_const_sel_sched_deps_info,
3389 sizeof (rgn_sched_deps_info));
3391 sched_deps_info = &rgn_sched_deps_info;
3393 memcpy (&rgn_sched_info, &rgn_const_sched_info, sizeof (rgn_sched_info));
3394 current_sched_info = &rgn_sched_info;
3397 /* The one entry point in this file. */
3398 void
3399 schedule_insns (void)
3401 int rgn;
3403 /* Taking care of this degenerate case makes the rest of
3404 this code simpler. */
3405 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
3406 return;
3408 rgn_setup_common_sched_info ();
3409 rgn_setup_sched_infos ();
3411 haifa_sched_init ();
3412 sched_rgn_init (reload_completed);
3414 bitmap_initialize (&not_in_df, 0);
3415 bitmap_clear (&not_in_df);
3417 /* Schedule every region in the subroutine. */
3418 for (rgn = 0; rgn < nr_regions; rgn++)
3419 if (dbg_cnt (sched_region))
3420 schedule_region (rgn);
3422 /* Clean up. */
3423 sched_rgn_finish ();
3424 bitmap_clear (&not_in_df);
3426 haifa_sched_finish ();
3429 /* INSN has been added to/removed from current region. */
3430 static void
3431 rgn_add_remove_insn (rtx_insn *insn, int remove_p)
3433 if (!remove_p)
3434 rgn_n_insns++;
3435 else
3436 rgn_n_insns--;
3438 if (INSN_BB (insn) == target_bb)
3440 if (!remove_p)
3441 target_n_insns++;
3442 else
3443 target_n_insns--;
3447 /* Extend internal data structures. */
3448 void
3449 extend_regions (void)
3451 rgn_table = XRESIZEVEC (region, rgn_table, n_basic_blocks_for_fn (cfun));
3452 rgn_bb_table = XRESIZEVEC (int, rgn_bb_table,
3453 n_basic_blocks_for_fn (cfun));
3454 block_to_bb = XRESIZEVEC (int, block_to_bb,
3455 last_basic_block_for_fn (cfun));
3456 containing_rgn = XRESIZEVEC (int, containing_rgn,
3457 last_basic_block_for_fn (cfun));
3460 void
3461 rgn_make_new_region_out_of_new_block (basic_block bb)
3463 int i;
3465 i = RGN_BLOCKS (nr_regions);
3466 /* I - first free position in rgn_bb_table. */
3468 rgn_bb_table[i] = bb->index;
3469 RGN_NR_BLOCKS (nr_regions) = 1;
3470 RGN_HAS_REAL_EBB (nr_regions) = 0;
3471 RGN_DONT_CALC_DEPS (nr_regions) = 0;
3472 CONTAINING_RGN (bb->index) = nr_regions;
3473 BLOCK_TO_BB (bb->index) = 0;
3475 nr_regions++;
3477 RGN_BLOCKS (nr_regions) = i + 1;
3480 /* BB was added to ebb after AFTER. */
3481 static void
3482 rgn_add_block (basic_block bb, basic_block after)
3484 extend_regions ();
3485 bitmap_set_bit (&not_in_df, bb->index);
3487 if (after == 0 || after == EXIT_BLOCK_PTR_FOR_FN (cfun))
3489 rgn_make_new_region_out_of_new_block (bb);
3490 RGN_DONT_CALC_DEPS (nr_regions - 1) = (after
3491 == EXIT_BLOCK_PTR_FOR_FN (cfun));
3493 else
3495 int i, pos;
3497 /* We need to fix rgn_table, block_to_bb, containing_rgn
3498 and ebb_head. */
3500 BLOCK_TO_BB (bb->index) = BLOCK_TO_BB (after->index);
3502 /* We extend ebb_head to one more position to
3503 easily find the last position of the last ebb in
3504 the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
3505 is _always_ valid for access. */
3507 i = BLOCK_TO_BB (after->index) + 1;
3508 pos = ebb_head[i] - 1;
3509 /* Now POS is the index of the last block in the region. */
3511 /* Find index of basic block AFTER. */
3512 for (; rgn_bb_table[pos] != after->index; pos--)
3515 pos++;
3516 gcc_assert (pos > ebb_head[i - 1]);
3518 /* i - ebb right after "AFTER". */
3519 /* ebb_head[i] - VALID. */
3521 /* Source position: ebb_head[i]
3522 Destination position: ebb_head[i] + 1
3523 Last position:
3524 RGN_BLOCKS (nr_regions) - 1
3525 Number of elements to copy: (last_position) - (source_position) + 1
3528 memmove (rgn_bb_table + pos + 1,
3529 rgn_bb_table + pos,
3530 ((RGN_BLOCKS (nr_regions) - 1) - (pos) + 1)
3531 * sizeof (*rgn_bb_table));
3533 rgn_bb_table[pos] = bb->index;
3535 for (; i <= current_nr_blocks; i++)
3536 ebb_head [i]++;
3538 i = CONTAINING_RGN (after->index);
3539 CONTAINING_RGN (bb->index) = i;
3541 RGN_HAS_REAL_EBB (i) = 1;
3543 for (++i; i <= nr_regions; i++)
3544 RGN_BLOCKS (i)++;
3548 /* Fix internal data after interblock movement of jump instruction.
3549 For parameter meaning please refer to
3550 sched-int.h: struct sched_info: fix_recovery_cfg. */
3551 static void
3552 rgn_fix_recovery_cfg (int bbi, int check_bbi, int check_bb_nexti)
3554 int old_pos, new_pos, i;
3556 BLOCK_TO_BB (check_bb_nexti) = BLOCK_TO_BB (bbi);
3558 for (old_pos = ebb_head[BLOCK_TO_BB (check_bbi) + 1] - 1;
3559 rgn_bb_table[old_pos] != check_bb_nexti;
3560 old_pos--)
3562 gcc_assert (old_pos > ebb_head[BLOCK_TO_BB (check_bbi)]);
3564 for (new_pos = ebb_head[BLOCK_TO_BB (bbi) + 1] - 1;
3565 rgn_bb_table[new_pos] != bbi;
3566 new_pos--)
3568 new_pos++;
3569 gcc_assert (new_pos > ebb_head[BLOCK_TO_BB (bbi)]);
3571 gcc_assert (new_pos < old_pos);
3573 memmove (rgn_bb_table + new_pos + 1,
3574 rgn_bb_table + new_pos,
3575 (old_pos - new_pos) * sizeof (*rgn_bb_table));
3577 rgn_bb_table[new_pos] = check_bb_nexti;
3579 for (i = BLOCK_TO_BB (bbi) + 1; i <= BLOCK_TO_BB (check_bbi); i++)
3580 ebb_head[i]++;
3583 /* Return next block in ebb chain. For parameter meaning please refer to
3584 sched-int.h: struct sched_info: advance_target_bb. */
3585 static basic_block
3586 advance_target_bb (basic_block bb, rtx_insn *insn)
3588 if (insn)
3589 return 0;
3591 gcc_assert (BLOCK_TO_BB (bb->index) == target_bb
3592 && BLOCK_TO_BB (bb->next_bb->index) == target_bb);
3593 return bb->next_bb;
3596 #endif
3598 /* Run instruction scheduler. */
3599 static unsigned int
3600 rest_of_handle_live_range_shrinkage (void)
3602 #ifdef INSN_SCHEDULING
3603 int saved;
3605 initialize_live_range_shrinkage ();
3606 saved = flag_schedule_interblock;
3607 flag_schedule_interblock = false;
3608 schedule_insns ();
3609 flag_schedule_interblock = saved;
3610 finish_live_range_shrinkage ();
3611 #endif
3612 return 0;
3615 /* Run instruction scheduler. */
3616 static unsigned int
3617 rest_of_handle_sched (void)
3619 #ifdef INSN_SCHEDULING
3620 if (flag_selective_scheduling
3621 && ! maybe_skip_selective_scheduling ())
3622 run_selective_scheduling ();
3623 else
3624 schedule_insns ();
3625 #endif
3626 return 0;
3629 /* Run second scheduling pass after reload. */
3630 static unsigned int
3631 rest_of_handle_sched2 (void)
3633 #ifdef INSN_SCHEDULING
3634 if (flag_selective_scheduling2
3635 && ! maybe_skip_selective_scheduling ())
3636 run_selective_scheduling ();
3637 else
3639 /* Do control and data sched analysis again,
3640 and write some more of the results to dump file. */
3641 if (flag_sched2_use_superblocks)
3642 schedule_ebbs ();
3643 else
3644 schedule_insns ();
3646 #endif
3647 return 0;
3650 static unsigned int
3651 rest_of_handle_sched_fusion (void)
3653 #ifdef INSN_SCHEDULING
3654 sched_fusion = true;
3655 schedule_insns ();
3656 sched_fusion = false;
3657 #endif
3658 return 0;
3661 namespace {
3663 const pass_data pass_data_live_range_shrinkage =
3665 RTL_PASS, /* type */
3666 "lr_shrinkage", /* name */
3667 OPTGROUP_NONE, /* optinfo_flags */
3668 TV_LIVE_RANGE_SHRINKAGE, /* tv_id */
3669 0, /* properties_required */
3670 0, /* properties_provided */
3671 0, /* properties_destroyed */
3672 0, /* todo_flags_start */
3673 TODO_df_finish, /* todo_flags_finish */
3676 class pass_live_range_shrinkage : public rtl_opt_pass
3678 public:
3679 pass_live_range_shrinkage(gcc::context *ctxt)
3680 : rtl_opt_pass(pass_data_live_range_shrinkage, ctxt)
3683 /* opt_pass methods: */
3684 virtual bool gate (function *)
3686 #ifdef INSN_SCHEDULING
3687 return flag_live_range_shrinkage;
3688 #else
3689 return 0;
3690 #endif
3693 virtual unsigned int execute (function *)
3695 return rest_of_handle_live_range_shrinkage ();
3698 }; // class pass_live_range_shrinkage
3700 } // anon namespace
3702 rtl_opt_pass *
3703 make_pass_live_range_shrinkage (gcc::context *ctxt)
3705 return new pass_live_range_shrinkage (ctxt);
3708 namespace {
3710 const pass_data pass_data_sched =
3712 RTL_PASS, /* type */
3713 "sched1", /* name */
3714 OPTGROUP_NONE, /* optinfo_flags */
3715 TV_SCHED, /* tv_id */
3716 0, /* properties_required */
3717 0, /* properties_provided */
3718 0, /* properties_destroyed */
3719 0, /* todo_flags_start */
3720 TODO_df_finish, /* todo_flags_finish */
3723 class pass_sched : public rtl_opt_pass
3725 public:
3726 pass_sched (gcc::context *ctxt)
3727 : rtl_opt_pass (pass_data_sched, ctxt)
3730 /* opt_pass methods: */
3731 virtual bool gate (function *);
3732 virtual unsigned int execute (function *) { return rest_of_handle_sched (); }
3734 }; // class pass_sched
3736 bool
3737 pass_sched::gate (function *)
3739 #ifdef INSN_SCHEDULING
3740 return optimize > 0 && flag_schedule_insns && dbg_cnt (sched_func);
3741 #else
3742 return 0;
3743 #endif
3746 } // anon namespace
3748 rtl_opt_pass *
3749 make_pass_sched (gcc::context *ctxt)
3751 return new pass_sched (ctxt);
3754 namespace {
3756 const pass_data pass_data_sched2 =
3758 RTL_PASS, /* type */
3759 "sched2", /* name */
3760 OPTGROUP_NONE, /* optinfo_flags */
3761 TV_SCHED2, /* tv_id */
3762 0, /* properties_required */
3763 0, /* properties_provided */
3764 0, /* properties_destroyed */
3765 0, /* todo_flags_start */
3766 TODO_df_finish, /* todo_flags_finish */
3769 class pass_sched2 : public rtl_opt_pass
3771 public:
3772 pass_sched2 (gcc::context *ctxt)
3773 : rtl_opt_pass (pass_data_sched2, ctxt)
3776 /* opt_pass methods: */
3777 virtual bool gate (function *);
3778 virtual unsigned int execute (function *)
3780 return rest_of_handle_sched2 ();
3783 }; // class pass_sched2
3785 bool
3786 pass_sched2::gate (function *)
3788 #ifdef INSN_SCHEDULING
3789 return optimize > 0 && flag_schedule_insns_after_reload
3790 && !targetm.delay_sched2 && dbg_cnt (sched2_func);
3791 #else
3792 return 0;
3793 #endif
3796 } // anon namespace
3798 rtl_opt_pass *
3799 make_pass_sched2 (gcc::context *ctxt)
3801 return new pass_sched2 (ctxt);
3804 namespace {
3806 const pass_data pass_data_sched_fusion =
3808 RTL_PASS, /* type */
3809 "sched_fusion", /* name */
3810 OPTGROUP_NONE, /* optinfo_flags */
3811 TV_SCHED_FUSION, /* tv_id */
3812 0, /* properties_required */
3813 0, /* properties_provided */
3814 0, /* properties_destroyed */
3815 0, /* todo_flags_start */
3816 TODO_df_finish, /* todo_flags_finish */
3819 class pass_sched_fusion : public rtl_opt_pass
3821 public:
3822 pass_sched_fusion (gcc::context *ctxt)
3823 : rtl_opt_pass (pass_data_sched_fusion, ctxt)
3826 /* opt_pass methods: */
3827 virtual bool gate (function *);
3828 virtual unsigned int execute (function *)
3830 return rest_of_handle_sched_fusion ();
3833 }; // class pass_sched2
3835 bool
3836 pass_sched_fusion::gate (function *)
3838 #ifdef INSN_SCHEDULING
3839 /* Scheduling fusion relies on peephole2 to do real fusion work,
3840 so only enable it if peephole2 is in effect. */
3841 return (optimize > 0 && flag_peephole2
3842 && flag_schedule_fusion && targetm.sched.fusion_priority != NULL);
3843 #else
3844 return 0;
3845 #endif
3848 } // anon namespace
3850 rtl_opt_pass *
3851 make_pass_sched_fusion (gcc::context *ctxt)
3853 return new pass_sched_fusion (ctxt);