* tree-if-conv.c: Fix various typos in comments.
[official-gcc.git] / gcc / sched-rgn.c
blobce2c1724fff113b159f961ca4bf6a3cadbc6e102
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 "backend.h"
50 #include "rtl.h"
51 #include "df.h"
52 #include "diagnostic-core.h"
53 #include "tm_p.h"
54 #include "regs.h"
55 #include "profile.h"
56 #include "flags.h"
57 #include "insn-config.h"
58 #include "insn-attr.h"
59 #include "except.h"
60 #include "recog.h"
61 #include "params.h"
62 #include "cfganal.h"
63 #include "sched-int.h"
64 #include "sel-sched.h"
65 #include "target.h"
66 #include "tree-pass.h"
67 #include "dbgcnt.h"
68 #include "emit-rtl.h"
70 #ifdef INSN_SCHEDULING
72 /* Some accessor macros for h_i_d members only used within this file. */
73 #define FED_BY_SPEC_LOAD(INSN) (HID (INSN)->fed_by_spec_load)
74 #define IS_LOAD_INSN(INSN) (HID (insn)->is_load_insn)
76 /* nr_inter/spec counts interblock/speculative motion for the function. */
77 static int nr_inter, nr_spec;
79 static int is_cfg_nonregular (void);
81 /* Number of regions in the procedure. */
82 int nr_regions = 0;
84 /* Same as above before adding any new regions. */
85 static int nr_regions_initial = 0;
87 /* Table of region descriptions. */
88 region *rgn_table = NULL;
90 /* Array of lists of regions' blocks. */
91 int *rgn_bb_table = NULL;
93 /* Topological order of blocks in the region (if b2 is reachable from
94 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
95 always referred to by either block or b, while its topological
96 order name (in the region) is referred to by bb. */
97 int *block_to_bb = NULL;
99 /* The number of the region containing a block. */
100 int *containing_rgn = NULL;
102 /* ebb_head [i] - is index in rgn_bb_table of the head basic block of i'th ebb.
103 Currently we can get a ebb only through splitting of currently
104 scheduling block, therefore, we don't need ebb_head array for every region,
105 hence, its sufficient to hold it for current one only. */
106 int *ebb_head = NULL;
108 /* The minimum probability of reaching a source block so that it will be
109 considered for speculative scheduling. */
110 static int min_spec_prob;
112 static void find_single_block_region (bool);
113 static void find_rgns (void);
114 static bool too_large (int, int *, int *);
116 /* Blocks of the current region being scheduled. */
117 int current_nr_blocks;
118 int current_blocks;
120 /* A speculative motion requires checking live information on the path
121 from 'source' to 'target'. The split blocks are those to be checked.
122 After a speculative motion, live information should be modified in
123 the 'update' blocks.
125 Lists of split and update blocks for each candidate of the current
126 target are in array bblst_table. */
127 static basic_block *bblst_table;
128 static int bblst_size, bblst_last;
130 /* Arrays that hold the DFA state at the end of a basic block, to re-use
131 as the initial state at the start of successor blocks. The BB_STATE
132 array holds the actual DFA state, and BB_STATE_ARRAY[I] is a pointer
133 into BB_STATE for basic block I. FIXME: This should be a vec. */
134 static char *bb_state_array = NULL;
135 static state_t *bb_state = NULL;
137 /* Target info declarations.
139 The block currently being scheduled is referred to as the "target" block,
140 while other blocks in the region from which insns can be moved to the
141 target are called "source" blocks. The candidate structure holds info
142 about such sources: are they valid? Speculative? Etc. */
143 typedef struct
145 basic_block *first_member;
146 int nr_members;
148 bblst;
150 typedef struct
152 char is_valid;
153 char is_speculative;
154 int src_prob;
155 bblst split_bbs;
156 bblst update_bbs;
158 candidate;
160 static candidate *candidate_table;
161 #define IS_VALID(src) (candidate_table[src].is_valid)
162 #define IS_SPECULATIVE(src) (candidate_table[src].is_speculative)
163 #define IS_SPECULATIVE_INSN(INSN) \
164 (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
165 #define SRC_PROB(src) ( candidate_table[src].src_prob )
167 /* The bb being currently scheduled. */
168 int target_bb;
170 /* List of edges. */
171 typedef struct
173 edge *first_member;
174 int nr_members;
176 edgelst;
178 static edge *edgelst_table;
179 static int edgelst_last;
181 static void extract_edgelst (sbitmap, edgelst *);
183 /* Target info functions. */
184 static void split_edges (int, int, edgelst *);
185 static void compute_trg_info (int);
186 void debug_candidate (int);
187 void debug_candidates (int);
189 /* Dominators array: dom[i] contains the sbitmap of dominators of
190 bb i in the region. */
191 static sbitmap *dom;
193 /* bb 0 is the only region entry. */
194 #define IS_RGN_ENTRY(bb) (!bb)
196 /* Is bb_src dominated by bb_trg. */
197 #define IS_DOMINATED(bb_src, bb_trg) \
198 ( bitmap_bit_p (dom[bb_src], bb_trg) )
200 /* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
201 the probability of bb i relative to the region entry. */
202 static int *prob;
204 /* Bit-set of edges, where bit i stands for edge i. */
205 typedef sbitmap edgeset;
207 /* Number of edges in the region. */
208 static int rgn_nr_edges;
210 /* Array of size rgn_nr_edges. */
211 static edge *rgn_edges;
213 /* Mapping from each edge in the graph to its number in the rgn. */
214 #define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
215 #define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
217 /* The split edges of a source bb is different for each target
218 bb. In order to compute this efficiently, the 'potential-split edges'
219 are computed for each bb prior to scheduling a region. This is actually
220 the split edges of each bb relative to the region entry.
222 pot_split[bb] is the set of potential split edges of bb. */
223 static edgeset *pot_split;
225 /* For every bb, a set of its ancestor edges. */
226 static edgeset *ancestor_edges;
228 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
230 /* Speculative scheduling functions. */
231 static int check_live_1 (int, rtx);
232 static void update_live_1 (int, rtx);
233 static int is_pfree (rtx, int, int);
234 static int find_conditional_protection (rtx_insn *, int);
235 static int is_conditionally_protected (rtx, int, int);
236 static int is_prisky (rtx, int, int);
237 static int is_exception_free (rtx_insn *, int, int);
239 static bool sets_likely_spilled (rtx);
240 static void sets_likely_spilled_1 (rtx, const_rtx, void *);
241 static void add_branch_dependences (rtx_insn *, rtx_insn *);
242 static void compute_block_dependences (int);
244 static void schedule_region (int);
245 static void concat_insn_mem_list (rtx_insn_list *, rtx_expr_list *,
246 rtx_insn_list **, rtx_expr_list **);
247 static void propagate_deps (int, struct deps_desc *);
248 static void free_pending_lists (void);
250 /* Functions for construction of the control flow graph. */
252 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
254 We decide not to build the control flow graph if there is possibly more
255 than one entry to the function, if computed branches exist, if we
256 have nonlocal gotos, or if we have an unreachable loop. */
258 static int
259 is_cfg_nonregular (void)
261 basic_block b;
262 rtx_insn *insn;
264 /* If we have a label that could be the target of a nonlocal goto, then
265 the cfg is not well structured. */
266 if (nonlocal_goto_handler_labels)
267 return 1;
269 /* If we have any forced labels, then the cfg is not well structured. */
270 if (forced_labels)
271 return 1;
273 /* If we have exception handlers, then we consider the cfg not well
274 structured. ?!? We should be able to handle this now that we
275 compute an accurate cfg for EH. */
276 if (current_function_has_exception_handlers ())
277 return 1;
279 /* If we have insns which refer to labels as non-jumped-to operands,
280 then we consider the cfg not well structured. */
281 FOR_EACH_BB_FN (b, cfun)
282 FOR_BB_INSNS (b, insn)
284 rtx note, set, dest;
285 rtx_insn *next;
287 /* If this function has a computed jump, then we consider the cfg
288 not well structured. */
289 if (JUMP_P (insn) && computed_jump_p (insn))
290 return 1;
292 if (!INSN_P (insn))
293 continue;
295 note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX);
296 if (note == NULL_RTX)
297 continue;
299 /* For that label not to be seen as a referred-to label, this
300 must be a single-set which is feeding a jump *only*. This
301 could be a conditional jump with the label split off for
302 machine-specific reasons or a casesi/tablejump. */
303 next = next_nonnote_insn (insn);
304 if (next == NULL_RTX
305 || !JUMP_P (next)
306 || (JUMP_LABEL (next) != XEXP (note, 0)
307 && find_reg_note (next, REG_LABEL_TARGET,
308 XEXP (note, 0)) == NULL_RTX)
309 || BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (next))
310 return 1;
312 set = single_set (insn);
313 if (set == NULL_RTX)
314 return 1;
316 dest = SET_DEST (set);
317 if (!REG_P (dest) || !dead_or_set_p (next, dest))
318 return 1;
321 /* Unreachable loops with more than one basic block are detected
322 during the DFS traversal in find_rgns.
324 Unreachable loops with a single block are detected here. This
325 test is redundant with the one in find_rgns, but it's much
326 cheaper to go ahead and catch the trivial case here. */
327 FOR_EACH_BB_FN (b, cfun)
329 if (EDGE_COUNT (b->preds) == 0
330 || (single_pred_p (b)
331 && single_pred (b) == b))
332 return 1;
335 /* All the tests passed. Consider the cfg well structured. */
336 return 0;
339 /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */
341 static void
342 extract_edgelst (sbitmap set, edgelst *el)
344 unsigned int i = 0;
345 sbitmap_iterator sbi;
347 /* edgelst table space is reused in each call to extract_edgelst. */
348 edgelst_last = 0;
350 el->first_member = &edgelst_table[edgelst_last];
351 el->nr_members = 0;
353 /* Iterate over each word in the bitset. */
354 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, sbi)
356 edgelst_table[edgelst_last++] = rgn_edges[i];
357 el->nr_members++;
361 /* Functions for the construction of regions. */
363 /* Print the regions, for debugging purposes. Callable from debugger. */
365 DEBUG_FUNCTION void
366 debug_regions (void)
368 int rgn, bb;
370 fprintf (sched_dump, "\n;; ------------ REGIONS ----------\n\n");
371 for (rgn = 0; rgn < nr_regions; rgn++)
373 fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
374 rgn_table[rgn].rgn_nr_blocks);
375 fprintf (sched_dump, ";;\tbb/block: ");
377 /* We don't have ebb_head initialized yet, so we can't use
378 BB_TO_BLOCK (). */
379 current_blocks = RGN_BLOCKS (rgn);
381 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
382 fprintf (sched_dump, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
384 fprintf (sched_dump, "\n\n");
388 /* Print the region's basic blocks. */
390 DEBUG_FUNCTION void
391 debug_region (int rgn)
393 int bb;
395 fprintf (stderr, "\n;; ------------ REGION %d ----------\n\n", rgn);
396 fprintf (stderr, ";;\trgn %d nr_blocks %d:\n", rgn,
397 rgn_table[rgn].rgn_nr_blocks);
398 fprintf (stderr, ";;\tbb/block: ");
400 /* We don't have ebb_head initialized yet, so we can't use
401 BB_TO_BLOCK (). */
402 current_blocks = RGN_BLOCKS (rgn);
404 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
405 fprintf (stderr, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
407 fprintf (stderr, "\n\n");
409 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
411 dump_bb (stderr,
412 BASIC_BLOCK_FOR_FN (cfun, rgn_bb_table[current_blocks + bb]),
413 0, TDF_SLIM | TDF_BLOCKS);
414 fprintf (stderr, "\n");
417 fprintf (stderr, "\n");
421 /* True when a bb with index BB_INDEX contained in region RGN. */
422 static bool
423 bb_in_region_p (int bb_index, int rgn)
425 int i;
427 for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
428 if (rgn_bb_table[current_blocks + i] == bb_index)
429 return true;
431 return false;
434 /* Dump region RGN to file F using dot syntax. */
435 void
436 dump_region_dot (FILE *f, int rgn)
438 int i;
440 fprintf (f, "digraph Region_%d {\n", rgn);
442 /* We don't have ebb_head initialized yet, so we can't use
443 BB_TO_BLOCK (). */
444 current_blocks = RGN_BLOCKS (rgn);
446 for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
448 edge e;
449 edge_iterator ei;
450 int src_bb_num = rgn_bb_table[current_blocks + i];
451 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, src_bb_num);
453 FOR_EACH_EDGE (e, ei, bb->succs)
454 if (bb_in_region_p (e->dest->index, rgn))
455 fprintf (f, "\t%d -> %d\n", src_bb_num, e->dest->index);
457 fprintf (f, "}\n");
460 /* The same, but first open a file specified by FNAME. */
461 void
462 dump_region_dot_file (const char *fname, int rgn)
464 FILE *f = fopen (fname, "wt");
465 dump_region_dot (f, rgn);
466 fclose (f);
469 /* Build a single block region for each basic block in the function.
470 This allows for using the same code for interblock and basic block
471 scheduling. */
473 static void
474 find_single_block_region (bool ebbs_p)
476 basic_block bb, ebb_start;
477 int i = 0;
479 nr_regions = 0;
481 if (ebbs_p) {
482 int probability_cutoff;
483 if (profile_info && flag_branch_probabilities)
484 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
485 else
486 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
487 probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
489 FOR_EACH_BB_FN (ebb_start, cfun)
491 RGN_NR_BLOCKS (nr_regions) = 0;
492 RGN_BLOCKS (nr_regions) = i;
493 RGN_DONT_CALC_DEPS (nr_regions) = 0;
494 RGN_HAS_REAL_EBB (nr_regions) = 0;
496 for (bb = ebb_start; ; bb = bb->next_bb)
498 edge e;
500 rgn_bb_table[i] = bb->index;
501 RGN_NR_BLOCKS (nr_regions)++;
502 CONTAINING_RGN (bb->index) = nr_regions;
503 BLOCK_TO_BB (bb->index) = i - RGN_BLOCKS (nr_regions);
504 i++;
506 if (bb->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
507 || LABEL_P (BB_HEAD (bb->next_bb)))
508 break;
510 e = find_fallthru_edge (bb->succs);
511 if (! e)
512 break;
513 if (e->probability <= probability_cutoff)
514 break;
517 ebb_start = bb;
518 nr_regions++;
521 else
522 FOR_EACH_BB_FN (bb, cfun)
524 rgn_bb_table[nr_regions] = bb->index;
525 RGN_NR_BLOCKS (nr_regions) = 1;
526 RGN_BLOCKS (nr_regions) = nr_regions;
527 RGN_DONT_CALC_DEPS (nr_regions) = 0;
528 RGN_HAS_REAL_EBB (nr_regions) = 0;
530 CONTAINING_RGN (bb->index) = nr_regions;
531 BLOCK_TO_BB (bb->index) = 0;
532 nr_regions++;
536 /* Estimate number of the insns in the BB. */
537 static int
538 rgn_estimate_number_of_insns (basic_block bb)
540 int count;
542 count = INSN_LUID (BB_END (bb)) - INSN_LUID (BB_HEAD (bb));
544 if (MAY_HAVE_DEBUG_INSNS)
546 rtx_insn *insn;
548 FOR_BB_INSNS (bb, insn)
549 if (DEBUG_INSN_P (insn))
550 count--;
553 return count;
556 /* Update number of blocks and the estimate for number of insns
557 in the region. Return true if the region is "too large" for interblock
558 scheduling (compile time considerations). */
560 static bool
561 too_large (int block, int *num_bbs, int *num_insns)
563 (*num_bbs)++;
564 (*num_insns) += (common_sched_info->estimate_number_of_insns
565 (BASIC_BLOCK_FOR_FN (cfun, block)));
567 return ((*num_bbs > PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS))
568 || (*num_insns > PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS)));
571 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
572 is still an inner loop. Put in max_hdr[blk] the header of the most inner
573 loop containing blk. */
574 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
576 if (max_hdr[blk] == -1) \
577 max_hdr[blk] = hdr; \
578 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
579 bitmap_clear_bit (inner, hdr); \
580 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
582 bitmap_clear_bit (inner,max_hdr[blk]); \
583 max_hdr[blk] = hdr; \
587 /* Find regions for interblock scheduling.
589 A region for scheduling can be:
591 * A loop-free procedure, or
593 * A reducible inner loop, or
595 * A basic block not contained in any other region.
597 ?!? In theory we could build other regions based on extended basic
598 blocks or reverse extended basic blocks. Is it worth the trouble?
600 Loop blocks that form a region are put into the region's block list
601 in topological order.
603 This procedure stores its results into the following global (ick) variables
605 * rgn_nr
606 * rgn_table
607 * rgn_bb_table
608 * block_to_bb
609 * containing region
611 We use dominator relationships to avoid making regions out of non-reducible
612 loops.
614 This procedure needs to be converted to work on pred/succ lists instead
615 of edge tables. That would simplify it somewhat. */
617 static void
618 haifa_find_rgns (void)
620 int *max_hdr, *dfs_nr, *degree;
621 char no_loops = 1;
622 int node, child, loop_head, i, head, tail;
623 int count = 0, sp, idx = 0;
624 edge_iterator current_edge;
625 edge_iterator *stack;
626 int num_bbs, num_insns, unreachable;
627 int too_large_failure;
628 basic_block bb;
630 /* Note if a block is a natural loop header. */
631 sbitmap header;
633 /* Note if a block is a natural inner loop header. */
634 sbitmap inner;
636 /* Note if a block is in the block queue. */
637 sbitmap in_queue;
639 /* Note if a block is in the block queue. */
640 sbitmap in_stack;
642 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
643 and a mapping from block to its loop header (if the block is contained
644 in a loop, else -1).
646 Store results in HEADER, INNER, and MAX_HDR respectively, these will
647 be used as inputs to the second traversal.
649 STACK, SP and DFS_NR are only used during the first traversal. */
651 /* Allocate and initialize variables for the first traversal. */
652 max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
653 dfs_nr = XCNEWVEC (int, last_basic_block_for_fn (cfun));
654 stack = XNEWVEC (edge_iterator, n_edges_for_fn (cfun));
656 inner = sbitmap_alloc (last_basic_block_for_fn (cfun));
657 bitmap_ones (inner);
659 header = sbitmap_alloc (last_basic_block_for_fn (cfun));
660 bitmap_clear (header);
662 in_queue = sbitmap_alloc (last_basic_block_for_fn (cfun));
663 bitmap_clear (in_queue);
665 in_stack = sbitmap_alloc (last_basic_block_for_fn (cfun));
666 bitmap_clear (in_stack);
668 for (i = 0; i < last_basic_block_for_fn (cfun); i++)
669 max_hdr[i] = -1;
671 #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
672 #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
674 /* DFS traversal to find inner loops in the cfg. */
676 current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))->succs);
677 sp = -1;
679 while (1)
681 if (EDGE_PASSED (current_edge))
683 /* We have reached a leaf node or a node that was already
684 processed. Pop edges off the stack until we find
685 an edge that has not yet been processed. */
686 while (sp >= 0 && EDGE_PASSED (current_edge))
688 /* Pop entry off the stack. */
689 current_edge = stack[sp--];
690 node = ei_edge (current_edge)->src->index;
691 gcc_assert (node != ENTRY_BLOCK);
692 child = ei_edge (current_edge)->dest->index;
693 gcc_assert (child != EXIT_BLOCK);
694 bitmap_clear_bit (in_stack, child);
695 if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
696 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
697 ei_next (&current_edge);
700 /* See if have finished the DFS tree traversal. */
701 if (sp < 0 && EDGE_PASSED (current_edge))
702 break;
704 /* Nope, continue the traversal with the popped node. */
705 continue;
708 /* Process a node. */
709 node = ei_edge (current_edge)->src->index;
710 gcc_assert (node != ENTRY_BLOCK);
711 bitmap_set_bit (in_stack, node);
712 dfs_nr[node] = ++count;
714 /* We don't traverse to the exit block. */
715 child = ei_edge (current_edge)->dest->index;
716 if (child == EXIT_BLOCK)
718 SET_EDGE_PASSED (current_edge);
719 ei_next (&current_edge);
720 continue;
723 /* If the successor is in the stack, then we've found a loop.
724 Mark the loop, if it is not a natural loop, then it will
725 be rejected during the second traversal. */
726 if (bitmap_bit_p (in_stack, child))
728 no_loops = 0;
729 bitmap_set_bit (header, child);
730 UPDATE_LOOP_RELATIONS (node, child);
731 SET_EDGE_PASSED (current_edge);
732 ei_next (&current_edge);
733 continue;
736 /* If the child was already visited, then there is no need to visit
737 it again. Just update the loop relationships and restart
738 with a new edge. */
739 if (dfs_nr[child])
741 if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
742 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
743 SET_EDGE_PASSED (current_edge);
744 ei_next (&current_edge);
745 continue;
748 /* Push an entry on the stack and continue DFS traversal. */
749 stack[++sp] = current_edge;
750 SET_EDGE_PASSED (current_edge);
751 current_edge = ei_start (ei_edge (current_edge)->dest->succs);
754 /* Reset ->aux field used by EDGE_PASSED. */
755 FOR_ALL_BB_FN (bb, cfun)
757 edge_iterator ei;
758 edge e;
759 FOR_EACH_EDGE (e, ei, bb->succs)
760 e->aux = NULL;
764 /* Another check for unreachable blocks. The earlier test in
765 is_cfg_nonregular only finds unreachable blocks that do not
766 form a loop.
768 The DFS traversal will mark every block that is reachable from
769 the entry node by placing a nonzero value in dfs_nr. Thus if
770 dfs_nr is zero for any block, then it must be unreachable. */
771 unreachable = 0;
772 FOR_EACH_BB_FN (bb, cfun)
773 if (dfs_nr[bb->index] == 0)
775 unreachable = 1;
776 break;
779 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
780 to hold degree counts. */
781 degree = dfs_nr;
783 FOR_EACH_BB_FN (bb, cfun)
784 degree[bb->index] = EDGE_COUNT (bb->preds);
786 /* Do not perform region scheduling if there are any unreachable
787 blocks. */
788 if (!unreachable)
790 int *queue, *degree1 = NULL;
791 /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
792 there basic blocks, which are forced to be region heads.
793 This is done to try to assemble few smaller regions
794 from a too_large region. */
795 sbitmap extended_rgn_header = NULL;
796 bool extend_regions_p;
798 if (no_loops)
799 bitmap_set_bit (header, 0);
801 /* Second traversal:find reducible inner loops and topologically sort
802 block of each region. */
804 queue = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
806 extend_regions_p = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS) > 0;
807 if (extend_regions_p)
809 degree1 = XNEWVEC (int, last_basic_block_for_fn (cfun));
810 extended_rgn_header =
811 sbitmap_alloc (last_basic_block_for_fn (cfun));
812 bitmap_clear (extended_rgn_header);
815 /* Find blocks which are inner loop headers. We still have non-reducible
816 loops to consider at this point. */
817 FOR_EACH_BB_FN (bb, cfun)
819 if (bitmap_bit_p (header, bb->index) && bitmap_bit_p (inner, bb->index))
821 edge e;
822 edge_iterator ei;
823 basic_block jbb;
825 /* Now check that the loop is reducible. We do this separate
826 from finding inner loops so that we do not find a reducible
827 loop which contains an inner non-reducible loop.
829 A simple way to find reducible/natural loops is to verify
830 that each block in the loop is dominated by the loop
831 header.
833 If there exists a block that is not dominated by the loop
834 header, then the block is reachable from outside the loop
835 and thus the loop is not a natural loop. */
836 FOR_EACH_BB_FN (jbb, cfun)
838 /* First identify blocks in the loop, except for the loop
839 entry block. */
840 if (bb->index == max_hdr[jbb->index] && bb != jbb)
842 /* Now verify that the block is dominated by the loop
843 header. */
844 if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))
845 break;
849 /* If we exited the loop early, then I is the header of
850 a non-reducible loop and we should quit processing it
851 now. */
852 if (jbb != EXIT_BLOCK_PTR_FOR_FN (cfun))
853 continue;
855 /* I is a header of an inner loop, or block 0 in a subroutine
856 with no loops at all. */
857 head = tail = -1;
858 too_large_failure = 0;
859 loop_head = max_hdr[bb->index];
861 if (extend_regions_p)
862 /* We save degree in case when we meet a too_large region
863 and cancel it. We need a correct degree later when
864 calling extend_rgns. */
865 memcpy (degree1, degree,
866 last_basic_block_for_fn (cfun) * sizeof (int));
868 /* Decrease degree of all I's successors for topological
869 ordering. */
870 FOR_EACH_EDGE (e, ei, bb->succs)
871 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
872 --degree[e->dest->index];
874 /* Estimate # insns, and count # blocks in the region. */
875 num_bbs = 1;
876 num_insns = common_sched_info->estimate_number_of_insns (bb);
878 /* Find all loop latches (blocks with back edges to the loop
879 header) or all the leaf blocks in the cfg has no loops.
881 Place those blocks into the queue. */
882 if (no_loops)
884 FOR_EACH_BB_FN (jbb, cfun)
885 /* Leaf nodes have only a single successor which must
886 be EXIT_BLOCK. */
887 if (single_succ_p (jbb)
888 && single_succ (jbb) == EXIT_BLOCK_PTR_FOR_FN (cfun))
890 queue[++tail] = jbb->index;
891 bitmap_set_bit (in_queue, jbb->index);
893 if (too_large (jbb->index, &num_bbs, &num_insns))
895 too_large_failure = 1;
896 break;
900 else
902 edge e;
904 FOR_EACH_EDGE (e, ei, bb->preds)
906 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
907 continue;
909 node = e->src->index;
911 if (max_hdr[node] == loop_head && node != bb->index)
913 /* This is a loop latch. */
914 queue[++tail] = node;
915 bitmap_set_bit (in_queue, node);
917 if (too_large (node, &num_bbs, &num_insns))
919 too_large_failure = 1;
920 break;
926 /* Now add all the blocks in the loop to the queue.
928 We know the loop is a natural loop; however the algorithm
929 above will not always mark certain blocks as being in the
930 loop. Consider:
931 node children
932 a b,c
934 c a,d
937 The algorithm in the DFS traversal may not mark B & D as part
938 of the loop (i.e. they will not have max_hdr set to A).
940 We know they can not be loop latches (else they would have
941 had max_hdr set since they'd have a backedge to a dominator
942 block). So we don't need them on the initial queue.
944 We know they are part of the loop because they are dominated
945 by the loop header and can be reached by a backwards walk of
946 the edges starting with nodes on the initial queue.
948 It is safe and desirable to include those nodes in the
949 loop/scheduling region. To do so we would need to decrease
950 the degree of a node if it is the target of a backedge
951 within the loop itself as the node is placed in the queue.
953 We do not do this because I'm not sure that the actual
954 scheduling code will properly handle this case. ?!? */
956 while (head < tail && !too_large_failure)
958 edge e;
959 child = queue[++head];
961 FOR_EACH_EDGE (e, ei,
962 BASIC_BLOCK_FOR_FN (cfun, child)->preds)
964 node = e->src->index;
966 /* See discussion above about nodes not marked as in
967 this loop during the initial DFS traversal. */
968 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
969 || max_hdr[node] != loop_head)
971 tail = -1;
972 break;
974 else if (!bitmap_bit_p (in_queue, node) && node != bb->index)
976 queue[++tail] = node;
977 bitmap_set_bit (in_queue, node);
979 if (too_large (node, &num_bbs, &num_insns))
981 too_large_failure = 1;
982 break;
988 if (tail >= 0 && !too_large_failure)
990 /* Place the loop header into list of region blocks. */
991 degree[bb->index] = -1;
992 rgn_bb_table[idx] = bb->index;
993 RGN_NR_BLOCKS (nr_regions) = num_bbs;
994 RGN_BLOCKS (nr_regions) = idx++;
995 RGN_DONT_CALC_DEPS (nr_regions) = 0;
996 RGN_HAS_REAL_EBB (nr_regions) = 0;
997 CONTAINING_RGN (bb->index) = nr_regions;
998 BLOCK_TO_BB (bb->index) = count = 0;
1000 /* Remove blocks from queue[] when their in degree
1001 becomes zero. Repeat until no blocks are left on the
1002 list. This produces a topological list of blocks in
1003 the region. */
1004 while (tail >= 0)
1006 if (head < 0)
1007 head = tail;
1008 child = queue[head];
1009 if (degree[child] == 0)
1011 edge e;
1013 degree[child] = -1;
1014 rgn_bb_table[idx++] = child;
1015 BLOCK_TO_BB (child) = ++count;
1016 CONTAINING_RGN (child) = nr_regions;
1017 queue[head] = queue[tail--];
1019 FOR_EACH_EDGE (e, ei,
1020 BASIC_BLOCK_FOR_FN (cfun,
1021 child)->succs)
1022 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1023 --degree[e->dest->index];
1025 else
1026 --head;
1028 ++nr_regions;
1030 else if (extend_regions_p)
1032 /* Restore DEGREE. */
1033 int *t = degree;
1035 degree = degree1;
1036 degree1 = t;
1038 /* And force successors of BB to be region heads.
1039 This may provide several smaller regions instead
1040 of one too_large region. */
1041 FOR_EACH_EDGE (e, ei, bb->succs)
1042 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1043 bitmap_set_bit (extended_rgn_header, e->dest->index);
1047 free (queue);
1049 if (extend_regions_p)
1051 free (degree1);
1053 bitmap_ior (header, header, extended_rgn_header);
1054 sbitmap_free (extended_rgn_header);
1056 extend_rgns (degree, &idx, header, max_hdr);
1060 /* Any block that did not end up in a region is placed into a region
1061 by itself. */
1062 FOR_EACH_BB_FN (bb, cfun)
1063 if (degree[bb->index] >= 0)
1065 rgn_bb_table[idx] = bb->index;
1066 RGN_NR_BLOCKS (nr_regions) = 1;
1067 RGN_BLOCKS (nr_regions) = idx++;
1068 RGN_DONT_CALC_DEPS (nr_regions) = 0;
1069 RGN_HAS_REAL_EBB (nr_regions) = 0;
1070 CONTAINING_RGN (bb->index) = nr_regions++;
1071 BLOCK_TO_BB (bb->index) = 0;
1074 free (max_hdr);
1075 free (degree);
1076 free (stack);
1077 sbitmap_free (header);
1078 sbitmap_free (inner);
1079 sbitmap_free (in_queue);
1080 sbitmap_free (in_stack);
1084 /* Wrapper function.
1085 If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
1086 regions. Otherwise just call find_rgns_haifa. */
1087 static void
1088 find_rgns (void)
1090 if (sel_sched_p () && flag_sel_sched_pipelining)
1091 sel_find_rgns ();
1092 else
1093 haifa_find_rgns ();
1096 static int gather_region_statistics (int **);
1097 static void print_region_statistics (int *, int, int *, int);
1099 /* Calculate the histogram that shows the number of regions having the
1100 given number of basic blocks, and store it in the RSP array. Return
1101 the size of this array. */
1102 static int
1103 gather_region_statistics (int **rsp)
1105 int i, *a = 0, a_sz = 0;
1107 /* a[i] is the number of regions that have (i + 1) basic blocks. */
1108 for (i = 0; i < nr_regions; i++)
1110 int nr_blocks = RGN_NR_BLOCKS (i);
1112 gcc_assert (nr_blocks >= 1);
1114 if (nr_blocks > a_sz)
1116 a = XRESIZEVEC (int, a, nr_blocks);
1118 a[a_sz++] = 0;
1119 while (a_sz != nr_blocks);
1122 a[nr_blocks - 1]++;
1125 *rsp = a;
1126 return a_sz;
1129 /* Print regions statistics. S1 and S2 denote the data before and after
1130 calling extend_rgns, respectively. */
1131 static void
1132 print_region_statistics (int *s1, int s1_sz, int *s2, int s2_sz)
1134 int i;
1136 /* We iterate until s2_sz because extend_rgns does not decrease
1137 the maximal region size. */
1138 for (i = 1; i < s2_sz; i++)
1140 int n1, n2;
1142 n2 = s2[i];
1144 if (n2 == 0)
1145 continue;
1147 if (i >= s1_sz)
1148 n1 = 0;
1149 else
1150 n1 = s1[i];
1152 fprintf (sched_dump, ";; Region extension statistics: size %d: " \
1153 "was %d + %d more\n", i + 1, n1, n2 - n1);
1157 /* Extend regions.
1158 DEGREE - Array of incoming edge count, considering only
1159 the edges, that don't have their sources in formed regions yet.
1160 IDXP - pointer to the next available index in rgn_bb_table.
1161 HEADER - set of all region heads.
1162 LOOP_HDR - mapping from block to the containing loop
1163 (two blocks can reside within one region if they have
1164 the same loop header). */
1165 void
1166 extend_rgns (int *degree, int *idxp, sbitmap header, int *loop_hdr)
1168 int *order, i, rescan = 0, idx = *idxp, iter = 0, max_iter, *max_hdr;
1169 int nblocks = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
1171 max_iter = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS);
1173 max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
1175 order = XNEWVEC (int, last_basic_block_for_fn (cfun));
1176 post_order_compute (order, false, false);
1178 for (i = nblocks - 1; i >= 0; i--)
1180 int bbn = order[i];
1181 if (degree[bbn] >= 0)
1183 max_hdr[bbn] = bbn;
1184 rescan = 1;
1186 else
1187 /* This block already was processed in find_rgns. */
1188 max_hdr[bbn] = -1;
1191 /* The idea is to topologically walk through CFG in top-down order.
1192 During the traversal, if all the predecessors of a node are
1193 marked to be in the same region (they all have the same max_hdr),
1194 then current node is also marked to be a part of that region.
1195 Otherwise the node starts its own region.
1196 CFG should be traversed until no further changes are made. On each
1197 iteration the set of the region heads is extended (the set of those
1198 blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
1199 set of all basic blocks, thus the algorithm is guaranteed to
1200 terminate. */
1202 while (rescan && iter < max_iter)
1204 rescan = 0;
1206 for (i = nblocks - 1; i >= 0; i--)
1208 edge e;
1209 edge_iterator ei;
1210 int bbn = order[i];
1212 if (max_hdr[bbn] != -1 && !bitmap_bit_p (header, bbn))
1214 int hdr = -1;
1216 FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->preds)
1218 int predn = e->src->index;
1220 if (predn != ENTRY_BLOCK
1221 /* If pred wasn't processed in find_rgns. */
1222 && max_hdr[predn] != -1
1223 /* And pred and bb reside in the same loop.
1224 (Or out of any loop). */
1225 && loop_hdr[bbn] == loop_hdr[predn])
1227 if (hdr == -1)
1228 /* Then bb extends the containing region of pred. */
1229 hdr = max_hdr[predn];
1230 else if (hdr != max_hdr[predn])
1231 /* Too bad, there are at least two predecessors
1232 that reside in different regions. Thus, BB should
1233 begin its own region. */
1235 hdr = bbn;
1236 break;
1239 else
1240 /* BB starts its own region. */
1242 hdr = bbn;
1243 break;
1247 if (hdr == bbn)
1249 /* If BB start its own region,
1250 update set of headers with BB. */
1251 bitmap_set_bit (header, bbn);
1252 rescan = 1;
1254 else
1255 gcc_assert (hdr != -1);
1257 max_hdr[bbn] = hdr;
1261 iter++;
1264 /* Statistics were gathered on the SPEC2000 package of tests with
1265 mainline weekly snapshot gcc-4.1-20051015 on ia64.
1267 Statistics for SPECint:
1268 1 iteration : 1751 cases (38.7%)
1269 2 iterations: 2770 cases (61.3%)
1270 Blocks wrapped in regions by find_rgns without extension: 18295 blocks
1271 Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
1272 (We don't count single block regions here).
1274 Statistics for SPECfp:
1275 1 iteration : 621 cases (35.9%)
1276 2 iterations: 1110 cases (64.1%)
1277 Blocks wrapped in regions by find_rgns without extension: 6476 blocks
1278 Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
1279 (We don't count single block regions here).
1281 By default we do at most 2 iterations.
1282 This can be overridden with max-sched-extend-regions-iters parameter:
1283 0 - disable region extension,
1284 N > 0 - do at most N iterations. */
1286 if (sched_verbose && iter != 0)
1287 fprintf (sched_dump, ";; Region extension iterations: %d%s\n", iter,
1288 rescan ? "... failed" : "");
1290 if (!rescan && iter != 0)
1292 int *s1 = NULL, s1_sz = 0;
1294 /* Save the old statistics for later printout. */
1295 if (sched_verbose >= 6)
1296 s1_sz = gather_region_statistics (&s1);
1298 /* We have succeeded. Now assemble the regions. */
1299 for (i = nblocks - 1; i >= 0; i--)
1301 int bbn = order[i];
1303 if (max_hdr[bbn] == bbn)
1304 /* BBN is a region head. */
1306 edge e;
1307 edge_iterator ei;
1308 int num_bbs = 0, j, num_insns = 0, large;
1310 large = too_large (bbn, &num_bbs, &num_insns);
1312 degree[bbn] = -1;
1313 rgn_bb_table[idx] = bbn;
1314 RGN_BLOCKS (nr_regions) = idx++;
1315 RGN_DONT_CALC_DEPS (nr_regions) = 0;
1316 RGN_HAS_REAL_EBB (nr_regions) = 0;
1317 CONTAINING_RGN (bbn) = nr_regions;
1318 BLOCK_TO_BB (bbn) = 0;
1320 FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->succs)
1321 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1322 degree[e->dest->index]--;
1324 if (!large)
1325 /* Here we check whether the region is too_large. */
1326 for (j = i - 1; j >= 0; j--)
1328 int succn = order[j];
1329 if (max_hdr[succn] == bbn)
1331 if ((large = too_large (succn, &num_bbs, &num_insns)))
1332 break;
1336 if (large)
1337 /* If the region is too_large, then wrap every block of
1338 the region into single block region.
1339 Here we wrap region head only. Other blocks are
1340 processed in the below cycle. */
1342 RGN_NR_BLOCKS (nr_regions) = 1;
1343 nr_regions++;
1346 num_bbs = 1;
1348 for (j = i - 1; j >= 0; j--)
1350 int succn = order[j];
1352 if (max_hdr[succn] == bbn)
1353 /* This cycle iterates over all basic blocks, that
1354 are supposed to be in the region with head BBN,
1355 and wraps them into that region (or in single
1356 block region). */
1358 gcc_assert (degree[succn] == 0);
1360 degree[succn] = -1;
1361 rgn_bb_table[idx] = succn;
1362 BLOCK_TO_BB (succn) = large ? 0 : num_bbs++;
1363 CONTAINING_RGN (succn) = nr_regions;
1365 if (large)
1366 /* Wrap SUCCN into single block region. */
1368 RGN_BLOCKS (nr_regions) = idx;
1369 RGN_NR_BLOCKS (nr_regions) = 1;
1370 RGN_DONT_CALC_DEPS (nr_regions) = 0;
1371 RGN_HAS_REAL_EBB (nr_regions) = 0;
1372 nr_regions++;
1375 idx++;
1377 FOR_EACH_EDGE (e, ei,
1378 BASIC_BLOCK_FOR_FN (cfun, succn)->succs)
1379 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1380 degree[e->dest->index]--;
1384 if (!large)
1386 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1387 nr_regions++;
1392 if (sched_verbose >= 6)
1394 int *s2, s2_sz;
1396 /* Get the new statistics and print the comparison with the
1397 one before calling this function. */
1398 s2_sz = gather_region_statistics (&s2);
1399 print_region_statistics (s1, s1_sz, s2, s2_sz);
1400 free (s1);
1401 free (s2);
1405 free (order);
1406 free (max_hdr);
1408 *idxp = idx;
1411 /* Functions for regions scheduling information. */
1413 /* Compute dominators, probability, and potential-split-edges of bb.
1414 Assume that these values were already computed for bb's predecessors. */
1416 static void
1417 compute_dom_prob_ps (int bb)
1419 edge_iterator in_ei;
1420 edge in_edge;
1422 /* We shouldn't have any real ebbs yet. */
1423 gcc_assert (ebb_head [bb] == bb + current_blocks);
1425 if (IS_RGN_ENTRY (bb))
1427 bitmap_set_bit (dom[bb], 0);
1428 prob[bb] = REG_BR_PROB_BASE;
1429 return;
1432 prob[bb] = 0;
1434 /* Initialize dom[bb] to '111..1'. */
1435 bitmap_ones (dom[bb]);
1437 FOR_EACH_EDGE (in_edge, in_ei,
1438 BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb))->preds)
1440 int pred_bb;
1441 edge out_edge;
1442 edge_iterator out_ei;
1444 if (in_edge->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1445 continue;
1447 pred_bb = BLOCK_TO_BB (in_edge->src->index);
1448 bitmap_and (dom[bb], dom[bb], dom[pred_bb]);
1449 bitmap_ior (ancestor_edges[bb],
1450 ancestor_edges[bb], ancestor_edges[pred_bb]);
1452 bitmap_set_bit (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
1454 bitmap_ior (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
1456 FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
1457 bitmap_set_bit (pot_split[bb], EDGE_TO_BIT (out_edge));
1459 prob[bb] += combine_probabilities (prob[pred_bb], in_edge->probability);
1460 // The rounding divide in combine_probabilities can result in an extra
1461 // probability increment propagating along 50-50 edges. Eventually when
1462 // the edges re-merge, the accumulated probability can go slightly above
1463 // REG_BR_PROB_BASE.
1464 if (prob[bb] > REG_BR_PROB_BASE)
1465 prob[bb] = REG_BR_PROB_BASE;
1468 bitmap_set_bit (dom[bb], bb);
1469 bitmap_and_compl (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
1471 if (sched_verbose >= 2)
1472 fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
1473 (100 * prob[bb]) / REG_BR_PROB_BASE);
1476 /* Functions for target info. */
1478 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1479 Note that bb_trg dominates bb_src. */
1481 static void
1482 split_edges (int bb_src, int bb_trg, edgelst *bl)
1484 sbitmap src = sbitmap_alloc (SBITMAP_SIZE (pot_split[bb_src]));
1485 bitmap_copy (src, pot_split[bb_src]);
1487 bitmap_and_compl (src, src, pot_split[bb_trg]);
1488 extract_edgelst (src, bl);
1489 sbitmap_free (src);
1492 /* Find the valid candidate-source-blocks for the target block TRG, compute
1493 their probability, and check if they are speculative or not.
1494 For speculative sources, compute their update-blocks and split-blocks. */
1496 static void
1497 compute_trg_info (int trg)
1499 candidate *sp;
1500 edgelst el = { NULL, 0 };
1501 int i, j, k, update_idx;
1502 basic_block block;
1503 sbitmap visited;
1504 edge_iterator ei;
1505 edge e;
1507 candidate_table = XNEWVEC (candidate, current_nr_blocks);
1509 bblst_last = 0;
1510 /* bblst_table holds split blocks and update blocks for each block after
1511 the current one in the region. split blocks and update blocks are
1512 the TO blocks of region edges, so there can be at most rgn_nr_edges
1513 of them. */
1514 bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
1515 bblst_table = XNEWVEC (basic_block, bblst_size);
1517 edgelst_last = 0;
1518 edgelst_table = XNEWVEC (edge, rgn_nr_edges);
1520 /* Define some of the fields for the target bb as well. */
1521 sp = candidate_table + trg;
1522 sp->is_valid = 1;
1523 sp->is_speculative = 0;
1524 sp->src_prob = REG_BR_PROB_BASE;
1526 visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
1528 for (i = trg + 1; i < current_nr_blocks; i++)
1530 sp = candidate_table + i;
1532 sp->is_valid = IS_DOMINATED (i, trg);
1533 if (sp->is_valid)
1535 int tf = prob[trg], cf = prob[i];
1537 /* In CFGs with low probability edges TF can possibly be zero. */
1538 sp->src_prob = (tf ? GCOV_COMPUTE_SCALE (cf, tf) : 0);
1539 sp->is_valid = (sp->src_prob >= min_spec_prob);
1542 if (sp->is_valid)
1544 split_edges (i, trg, &el);
1545 sp->is_speculative = (el.nr_members) ? 1 : 0;
1546 if (sp->is_speculative && !flag_schedule_speculative)
1547 sp->is_valid = 0;
1550 if (sp->is_valid)
1552 /* Compute split blocks and store them in bblst_table.
1553 The TO block of every split edge is a split block. */
1554 sp->split_bbs.first_member = &bblst_table[bblst_last];
1555 sp->split_bbs.nr_members = el.nr_members;
1556 for (j = 0; j < el.nr_members; bblst_last++, j++)
1557 bblst_table[bblst_last] = el.first_member[j]->dest;
1558 sp->update_bbs.first_member = &bblst_table[bblst_last];
1560 /* Compute update blocks and store them in bblst_table.
1561 For every split edge, look at the FROM block, and check
1562 all out edges. For each out edge that is not a split edge,
1563 add the TO block to the update block list. This list can end
1564 up with a lot of duplicates. We need to weed them out to avoid
1565 overrunning the end of the bblst_table. */
1567 update_idx = 0;
1568 bitmap_clear (visited);
1569 for (j = 0; j < el.nr_members; j++)
1571 block = el.first_member[j]->src;
1572 FOR_EACH_EDGE (e, ei, block->succs)
1574 if (!bitmap_bit_p (visited, e->dest->index))
1576 for (k = 0; k < el.nr_members; k++)
1577 if (e == el.first_member[k])
1578 break;
1580 if (k >= el.nr_members)
1582 bblst_table[bblst_last++] = e->dest;
1583 bitmap_set_bit (visited, e->dest->index);
1584 update_idx++;
1589 sp->update_bbs.nr_members = update_idx;
1591 /* Make sure we didn't overrun the end of bblst_table. */
1592 gcc_assert (bblst_last <= bblst_size);
1594 else
1596 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1598 sp->is_speculative = 0;
1599 sp->src_prob = 0;
1603 sbitmap_free (visited);
1606 /* Free the computed target info. */
1607 static void
1608 free_trg_info (void)
1610 free (candidate_table);
1611 free (bblst_table);
1612 free (edgelst_table);
1615 /* Print candidates info, for debugging purposes. Callable from debugger. */
1617 DEBUG_FUNCTION void
1618 debug_candidate (int i)
1620 if (!candidate_table[i].is_valid)
1621 return;
1623 if (candidate_table[i].is_speculative)
1625 int j;
1626 fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1628 fprintf (sched_dump, "split path: ");
1629 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1631 int b = candidate_table[i].split_bbs.first_member[j]->index;
1633 fprintf (sched_dump, " %d ", b);
1635 fprintf (sched_dump, "\n");
1637 fprintf (sched_dump, "update path: ");
1638 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
1640 int b = candidate_table[i].update_bbs.first_member[j]->index;
1642 fprintf (sched_dump, " %d ", b);
1644 fprintf (sched_dump, "\n");
1646 else
1648 fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
1652 /* Print candidates info, for debugging purposes. Callable from debugger. */
1654 DEBUG_FUNCTION void
1655 debug_candidates (int trg)
1657 int i;
1659 fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
1660 BB_TO_BLOCK (trg), trg);
1661 for (i = trg + 1; i < current_nr_blocks; i++)
1662 debug_candidate (i);
1665 /* Functions for speculative scheduling. */
1667 static bitmap_head not_in_df;
1669 /* Return 0 if x is a set of a register alive in the beginning of one
1670 of the split-blocks of src, otherwise return 1. */
1672 static int
1673 check_live_1 (int src, rtx x)
1675 int i;
1676 int regno;
1677 rtx reg = SET_DEST (x);
1679 if (reg == 0)
1680 return 1;
1682 while (GET_CODE (reg) == SUBREG
1683 || GET_CODE (reg) == ZERO_EXTRACT
1684 || GET_CODE (reg) == STRICT_LOW_PART)
1685 reg = XEXP (reg, 0);
1687 if (GET_CODE (reg) == PARALLEL)
1689 int i;
1691 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1692 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1693 if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
1694 return 1;
1696 return 0;
1699 if (!REG_P (reg))
1700 return 1;
1702 regno = REGNO (reg);
1704 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1706 /* Global registers are assumed live. */
1707 return 0;
1709 else
1711 if (regno < FIRST_PSEUDO_REGISTER)
1713 /* Check for hard registers. */
1714 int j = REG_NREGS (reg);
1715 while (--j >= 0)
1717 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1719 basic_block b = candidate_table[src].split_bbs.first_member[i];
1720 int t = bitmap_bit_p (&not_in_df, b->index);
1722 /* We can have split blocks, that were recently generated.
1723 Such blocks are always outside current region. */
1724 gcc_assert (!t || (CONTAINING_RGN (b->index)
1725 != CONTAINING_RGN (BB_TO_BLOCK (src))));
1727 if (t || REGNO_REG_SET_P (df_get_live_in (b), regno + j))
1728 return 0;
1732 else
1734 /* Check for pseudo registers. */
1735 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1737 basic_block b = candidate_table[src].split_bbs.first_member[i];
1738 int t = bitmap_bit_p (&not_in_df, b->index);
1740 gcc_assert (!t || (CONTAINING_RGN (b->index)
1741 != CONTAINING_RGN (BB_TO_BLOCK (src))));
1743 if (t || REGNO_REG_SET_P (df_get_live_in (b), regno))
1744 return 0;
1749 return 1;
1752 /* If x is a set of a register R, mark that R is alive in the beginning
1753 of every update-block of src. */
1755 static void
1756 update_live_1 (int src, rtx x)
1758 int i;
1759 int regno;
1760 rtx reg = SET_DEST (x);
1762 if (reg == 0)
1763 return;
1765 while (GET_CODE (reg) == SUBREG
1766 || GET_CODE (reg) == ZERO_EXTRACT
1767 || GET_CODE (reg) == STRICT_LOW_PART)
1768 reg = XEXP (reg, 0);
1770 if (GET_CODE (reg) == PARALLEL)
1772 int i;
1774 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1775 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1776 update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
1778 return;
1781 if (!REG_P (reg))
1782 return;
1784 /* Global registers are always live, so the code below does not apply
1785 to them. */
1787 regno = REGNO (reg);
1789 if (! HARD_REGISTER_NUM_P (regno)
1790 || !global_regs[regno])
1792 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1794 basic_block b = candidate_table[src].update_bbs.first_member[i];
1795 bitmap_set_range (df_get_live_in (b), regno, REG_NREGS (reg));
1800 /* Return 1 if insn can be speculatively moved from block src to trg,
1801 otherwise return 0. Called before first insertion of insn to
1802 ready-list or before the scheduling. */
1804 static int
1805 check_live (rtx_insn *insn, int src)
1807 /* Find the registers set by instruction. */
1808 if (GET_CODE (PATTERN (insn)) == SET
1809 || GET_CODE (PATTERN (insn)) == CLOBBER)
1810 return check_live_1 (src, PATTERN (insn));
1811 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1813 int j;
1814 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1815 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1816 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1817 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
1818 return 0;
1820 return 1;
1823 return 1;
1826 /* Update the live registers info after insn was moved speculatively from
1827 block src to trg. */
1829 static void
1830 update_live (rtx_insn *insn, int src)
1832 /* Find the registers set by instruction. */
1833 if (GET_CODE (PATTERN (insn)) == SET
1834 || GET_CODE (PATTERN (insn)) == CLOBBER)
1835 update_live_1 (src, PATTERN (insn));
1836 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1838 int j;
1839 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1840 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1841 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1842 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
1846 /* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1847 #define IS_REACHABLE(bb_from, bb_to) \
1848 (bb_from == bb_to \
1849 || IS_RGN_ENTRY (bb_from) \
1850 || (bitmap_bit_p (ancestor_edges[bb_to], \
1851 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK_FOR_FN (cfun, \
1852 BB_TO_BLOCK (bb_from)))))))
1854 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1856 static void
1857 set_spec_fed (rtx load_insn)
1859 sd_iterator_def sd_it;
1860 dep_t dep;
1862 FOR_EACH_DEP (load_insn, SD_LIST_FORW, sd_it, dep)
1863 if (DEP_TYPE (dep) == REG_DEP_TRUE)
1864 FED_BY_SPEC_LOAD (DEP_CON (dep)) = 1;
1867 /* On the path from the insn to load_insn_bb, find a conditional
1868 branch depending on insn, that guards the speculative load. */
1870 static int
1871 find_conditional_protection (rtx_insn *insn, int load_insn_bb)
1873 sd_iterator_def sd_it;
1874 dep_t dep;
1876 /* Iterate through DEF-USE forward dependences. */
1877 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
1879 rtx_insn *next = DEP_CON (dep);
1881 if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
1882 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
1883 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
1884 && load_insn_bb != INSN_BB (next)
1885 && DEP_TYPE (dep) == REG_DEP_TRUE
1886 && (JUMP_P (next)
1887 || find_conditional_protection (next, load_insn_bb)))
1888 return 1;
1890 return 0;
1891 } /* find_conditional_protection */
1893 /* Returns 1 if the same insn1 that participates in the computation
1894 of load_insn's address is feeding a conditional branch that is
1895 guarding on load_insn. This is true if we find two DEF-USE
1896 chains:
1897 insn1 -> ... -> conditional-branch
1898 insn1 -> ... -> load_insn,
1899 and if a flow path exists:
1900 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1901 and if insn1 is on the path
1902 region-entry -> ... -> bb_trg -> ... load_insn.
1904 Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
1905 Locate the branch by following INSN_FORW_DEPS from insn1. */
1907 static int
1908 is_conditionally_protected (rtx load_insn, int bb_src, int bb_trg)
1910 sd_iterator_def sd_it;
1911 dep_t dep;
1913 FOR_EACH_DEP (load_insn, SD_LIST_BACK, sd_it, dep)
1915 rtx_insn *insn1 = DEP_PRO (dep);
1917 /* Must be a DEF-USE dependence upon non-branch. */
1918 if (DEP_TYPE (dep) != REG_DEP_TRUE
1919 || JUMP_P (insn1))
1920 continue;
1922 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1923 if (INSN_BB (insn1) == bb_src
1924 || (CONTAINING_RGN (BLOCK_NUM (insn1))
1925 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
1926 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
1927 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
1928 continue;
1930 /* Now search for the conditional-branch. */
1931 if (find_conditional_protection (insn1, bb_src))
1932 return 1;
1934 /* Recursive step: search another insn1, "above" current insn1. */
1935 return is_conditionally_protected (insn1, bb_src, bb_trg);
1938 /* The chain does not exist. */
1939 return 0;
1940 } /* is_conditionally_protected */
1942 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1943 load_insn can move speculatively from bb_src to bb_trg. All the
1944 following must hold:
1946 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1947 (2) load_insn and load1 have a def-use dependence upon
1948 the same insn 'insn1'.
1949 (3) either load2 is in bb_trg, or:
1950 - there's only one split-block, and
1951 - load1 is on the escape path, and
1953 From all these we can conclude that the two loads access memory
1954 addresses that differ at most by a constant, and hence if moving
1955 load_insn would cause an exception, it would have been caused by
1956 load2 anyhow. */
1958 static int
1959 is_pfree (rtx load_insn, int bb_src, int bb_trg)
1961 sd_iterator_def back_sd_it;
1962 dep_t back_dep;
1963 candidate *candp = candidate_table + bb_src;
1965 if (candp->split_bbs.nr_members != 1)
1966 /* Must have exactly one escape block. */
1967 return 0;
1969 FOR_EACH_DEP (load_insn, SD_LIST_BACK, back_sd_it, back_dep)
1971 rtx_insn *insn1 = DEP_PRO (back_dep);
1973 if (DEP_TYPE (back_dep) == REG_DEP_TRUE)
1974 /* Found a DEF-USE dependence (insn1, load_insn). */
1976 sd_iterator_def fore_sd_it;
1977 dep_t fore_dep;
1979 FOR_EACH_DEP (insn1, SD_LIST_FORW, fore_sd_it, fore_dep)
1981 rtx_insn *insn2 = DEP_CON (fore_dep);
1983 if (DEP_TYPE (fore_dep) == REG_DEP_TRUE)
1985 /* Found a DEF-USE dependence (insn1, insn2). */
1986 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
1987 /* insn2 not guaranteed to be a 1 base reg load. */
1988 continue;
1990 if (INSN_BB (insn2) == bb_trg)
1991 /* insn2 is the similar load, in the target block. */
1992 return 1;
1994 if (*(candp->split_bbs.first_member) == BLOCK_FOR_INSN (insn2))
1995 /* insn2 is a similar load, in a split-block. */
1996 return 1;
2002 /* Couldn't find a similar load. */
2003 return 0;
2004 } /* is_pfree */
2006 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2007 a load moved speculatively, or if load_insn is protected by
2008 a compare on load_insn's address). */
2010 static int
2011 is_prisky (rtx load_insn, int bb_src, int bb_trg)
2013 if (FED_BY_SPEC_LOAD (load_insn))
2014 return 1;
2016 if (sd_lists_empty_p (load_insn, SD_LIST_BACK))
2017 /* Dependence may 'hide' out of the region. */
2018 return 1;
2020 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2021 return 1;
2023 return 0;
2026 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2027 Return 1 if insn is exception-free (and the motion is valid)
2028 and 0 otherwise. */
2030 static int
2031 is_exception_free (rtx_insn *insn, int bb_src, int bb_trg)
2033 int insn_class = haifa_classify_insn (insn);
2035 /* Handle non-load insns. */
2036 switch (insn_class)
2038 case TRAP_FREE:
2039 return 1;
2040 case TRAP_RISKY:
2041 return 0;
2042 default:;
2045 /* Handle loads. */
2046 if (!flag_schedule_speculative_load)
2047 return 0;
2048 IS_LOAD_INSN (insn) = 1;
2049 switch (insn_class)
2051 case IFREE:
2052 return (1);
2053 case IRISKY:
2054 return 0;
2055 case PFREE_CANDIDATE:
2056 if (is_pfree (insn, bb_src, bb_trg))
2057 return 1;
2058 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2059 case PRISKY_CANDIDATE:
2060 if (!flag_schedule_speculative_load_dangerous
2061 || is_prisky (insn, bb_src, bb_trg))
2062 return 0;
2063 break;
2064 default:;
2067 return flag_schedule_speculative_load_dangerous;
2070 /* The number of insns from the current block scheduled so far. */
2071 static int sched_target_n_insns;
2072 /* The number of insns from the current block to be scheduled in total. */
2073 static int target_n_insns;
2074 /* The number of insns from the entire region scheduled so far. */
2075 static int sched_n_insns;
2077 /* Implementations of the sched_info functions for region scheduling. */
2078 static void init_ready_list (void);
2079 static int can_schedule_ready_p (rtx_insn *);
2080 static void begin_schedule_ready (rtx_insn *);
2081 static ds_t new_ready (rtx_insn *, ds_t);
2082 static int schedule_more_p (void);
2083 static const char *rgn_print_insn (const rtx_insn *, int);
2084 static int rgn_rank (rtx_insn *, rtx_insn *);
2085 static void compute_jump_reg_dependencies (rtx, regset);
2087 /* Functions for speculative scheduling. */
2088 static void rgn_add_remove_insn (rtx_insn *, int);
2089 static void rgn_add_block (basic_block, basic_block);
2090 static void rgn_fix_recovery_cfg (int, int, int);
2091 static basic_block advance_target_bb (basic_block, rtx_insn *);
2093 /* Return nonzero if there are more insns that should be scheduled. */
2095 static int
2096 schedule_more_p (void)
2098 return sched_target_n_insns < target_n_insns;
2101 /* Add all insns that are initially ready to the ready list READY. Called
2102 once before scheduling a set of insns. */
2104 static void
2105 init_ready_list (void)
2107 rtx_insn *prev_head = current_sched_info->prev_head;
2108 rtx_insn *next_tail = current_sched_info->next_tail;
2109 int bb_src;
2110 rtx_insn *insn;
2112 target_n_insns = 0;
2113 sched_target_n_insns = 0;
2114 sched_n_insns = 0;
2116 /* Print debugging information. */
2117 if (sched_verbose >= 5)
2118 debug_rgn_dependencies (target_bb);
2120 /* Prepare current target block info. */
2121 if (current_nr_blocks > 1)
2122 compute_trg_info (target_bb);
2124 /* Initialize ready list with all 'ready' insns in target block.
2125 Count number of insns in the target block being scheduled. */
2126 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
2128 gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
2129 TODO_SPEC (insn) = HARD_DEP;
2130 try_ready (insn);
2131 target_n_insns++;
2133 gcc_assert (!(TODO_SPEC (insn) & BEGIN_CONTROL));
2136 /* Add to ready list all 'ready' insns in valid source blocks.
2137 For speculative insns, check-live, exception-free, and
2138 issue-delay. */
2139 for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
2140 if (IS_VALID (bb_src))
2142 rtx_insn *src_head;
2143 rtx_insn *src_next_tail;
2144 rtx_insn *tail, *head;
2146 get_ebb_head_tail (EBB_FIRST_BB (bb_src), EBB_LAST_BB (bb_src),
2147 &head, &tail);
2148 src_next_tail = NEXT_INSN (tail);
2149 src_head = head;
2151 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
2152 if (INSN_P (insn))
2154 gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
2155 TODO_SPEC (insn) = HARD_DEP;
2156 try_ready (insn);
2161 /* Called after taking INSN from the ready list. Returns nonzero if this
2162 insn can be scheduled, nonzero if we should silently discard it. */
2164 static int
2165 can_schedule_ready_p (rtx_insn *insn)
2167 /* An interblock motion? */
2168 if (INSN_BB (insn) != target_bb
2169 && IS_SPECULATIVE_INSN (insn)
2170 && !check_live (insn, INSN_BB (insn)))
2171 return 0;
2172 else
2173 return 1;
2176 /* Updates counter and other information. Split from can_schedule_ready_p ()
2177 because when we schedule insn speculatively then insn passed to
2178 can_schedule_ready_p () differs from the one passed to
2179 begin_schedule_ready (). */
2180 static void
2181 begin_schedule_ready (rtx_insn *insn)
2183 /* An interblock motion? */
2184 if (INSN_BB (insn) != target_bb)
2186 if (IS_SPECULATIVE_INSN (insn))
2188 gcc_assert (check_live (insn, INSN_BB (insn)));
2190 update_live (insn, INSN_BB (insn));
2192 /* For speculative load, mark insns fed by it. */
2193 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
2194 set_spec_fed (insn);
2196 nr_spec++;
2198 nr_inter++;
2200 else
2202 /* In block motion. */
2203 sched_target_n_insns++;
2205 sched_n_insns++;
2208 /* Called after INSN has all its hard dependencies resolved and the speculation
2209 of type TS is enough to overcome them all.
2210 Return nonzero if it should be moved to the ready list or the queue, or zero
2211 if we should silently discard it. */
2212 static ds_t
2213 new_ready (rtx_insn *next, ds_t ts)
2215 if (INSN_BB (next) != target_bb)
2217 int not_ex_free = 0;
2219 /* For speculative insns, before inserting to ready/queue,
2220 check live, exception-free, and issue-delay. */
2221 if (!IS_VALID (INSN_BB (next))
2222 || CANT_MOVE (next)
2223 || (IS_SPECULATIVE_INSN (next)
2224 && ((recog_memoized (next) >= 0
2225 && min_insn_conflict_delay (curr_state, next, next)
2226 > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY))
2227 || IS_SPECULATION_CHECK_P (next)
2228 || !check_live (next, INSN_BB (next))
2229 || (not_ex_free = !is_exception_free (next, INSN_BB (next),
2230 target_bb)))))
2232 if (not_ex_free
2233 /* We are here because is_exception_free () == false.
2234 But we possibly can handle that with control speculation. */
2235 && sched_deps_info->generate_spec_deps
2236 && spec_info->mask & BEGIN_CONTROL)
2238 ds_t new_ds;
2240 /* Add control speculation to NEXT's dependency type. */
2241 new_ds = set_dep_weak (ts, BEGIN_CONTROL, MAX_DEP_WEAK);
2243 /* Check if NEXT can be speculated with new dependency type. */
2244 if (sched_insn_is_legitimate_for_speculation_p (next, new_ds))
2245 /* Here we got new control-speculative instruction. */
2246 ts = new_ds;
2247 else
2248 /* NEXT isn't ready yet. */
2249 ts = DEP_POSTPONED;
2251 else
2252 /* NEXT isn't ready yet. */
2253 ts = DEP_POSTPONED;
2257 return ts;
2260 /* Return a string that contains the insn uid and optionally anything else
2261 necessary to identify this insn in an output. It's valid to use a
2262 static buffer for this. The ALIGNED parameter should cause the string
2263 to be formatted so that multiple output lines will line up nicely. */
2265 static const char *
2266 rgn_print_insn (const rtx_insn *insn, int aligned)
2268 static char tmp[80];
2270 if (aligned)
2271 sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
2272 else
2274 if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
2275 sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
2276 else
2277 sprintf (tmp, "%d", INSN_UID (insn));
2279 return tmp;
2282 /* Compare priority of two insns. Return a positive number if the second
2283 insn is to be preferred for scheduling, and a negative one if the first
2284 is to be preferred. Zero if they are equally good. */
2286 static int
2287 rgn_rank (rtx_insn *insn1, rtx_insn *insn2)
2289 /* Some comparison make sense in interblock scheduling only. */
2290 if (INSN_BB (insn1) != INSN_BB (insn2))
2292 int spec_val, prob_val;
2294 /* Prefer an inblock motion on an interblock motion. */
2295 if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
2296 return 1;
2297 if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
2298 return -1;
2300 /* Prefer a useful motion on a speculative one. */
2301 spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
2302 if (spec_val)
2303 return spec_val;
2305 /* Prefer a more probable (speculative) insn. */
2306 prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
2307 if (prob_val)
2308 return prob_val;
2310 return 0;
2313 /* NEXT is an instruction that depends on INSN (a backward dependence);
2314 return nonzero if we should include this dependence in priority
2315 calculations. */
2318 contributes_to_priority (rtx_insn *next, rtx_insn *insn)
2320 /* NEXT and INSN reside in one ebb. */
2321 return BLOCK_TO_BB (BLOCK_NUM (next)) == BLOCK_TO_BB (BLOCK_NUM (insn));
2324 /* INSN is a JUMP_INSN. Store the set of registers that must be
2325 considered as used by this jump in USED. */
2327 static void
2328 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
2329 regset used ATTRIBUTE_UNUSED)
2331 /* Nothing to do here, since we postprocess jumps in
2332 add_branch_dependences. */
2335 /* This variable holds common_sched_info hooks and data relevant to
2336 the interblock scheduler. */
2337 static struct common_sched_info_def rgn_common_sched_info;
2340 /* This holds data for the dependence analysis relevant to
2341 the interblock scheduler. */
2342 static struct sched_deps_info_def rgn_sched_deps_info;
2344 /* This holds constant data used for initializing the above structure
2345 for the Haifa scheduler. */
2346 static const struct sched_deps_info_def rgn_const_sched_deps_info =
2348 compute_jump_reg_dependencies,
2349 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
2350 0, 0, 0
2353 /* Same as above, but for the selective scheduler. */
2354 static const struct sched_deps_info_def rgn_const_sel_sched_deps_info =
2356 compute_jump_reg_dependencies,
2357 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
2358 0, 0, 0
2361 /* Return true if scheduling INSN will trigger finish of scheduling
2362 current block. */
2363 static bool
2364 rgn_insn_finishes_block_p (rtx_insn *insn)
2366 if (INSN_BB (insn) == target_bb
2367 && sched_target_n_insns + 1 == target_n_insns)
2368 /* INSN is the last not-scheduled instruction in the current block. */
2369 return true;
2371 return false;
2374 /* Used in schedule_insns to initialize current_sched_info for scheduling
2375 regions (or single basic blocks). */
2377 static const struct haifa_sched_info rgn_const_sched_info =
2379 init_ready_list,
2380 can_schedule_ready_p,
2381 schedule_more_p,
2382 new_ready,
2383 rgn_rank,
2384 rgn_print_insn,
2385 contributes_to_priority,
2386 rgn_insn_finishes_block_p,
2388 NULL, NULL,
2389 NULL, NULL,
2390 0, 0,
2392 rgn_add_remove_insn,
2393 begin_schedule_ready,
2394 NULL,
2395 advance_target_bb,
2396 NULL, NULL,
2397 SCHED_RGN
2400 /* This variable holds the data and hooks needed to the Haifa scheduler backend
2401 for the interblock scheduler frontend. */
2402 static struct haifa_sched_info rgn_sched_info;
2404 /* Returns maximum priority that an insn was assigned to. */
2407 get_rgn_sched_max_insns_priority (void)
2409 return rgn_sched_info.sched_max_insns_priority;
2412 /* Determine if PAT sets a TARGET_CLASS_LIKELY_SPILLED_P register. */
2414 static bool
2415 sets_likely_spilled (rtx pat)
2417 bool ret = false;
2418 note_stores (pat, sets_likely_spilled_1, &ret);
2419 return ret;
2422 static void
2423 sets_likely_spilled_1 (rtx x, const_rtx pat, void *data)
2425 bool *ret = (bool *) data;
2427 if (GET_CODE (pat) == SET
2428 && REG_P (x)
2429 && HARD_REGISTER_P (x)
2430 && targetm.class_likely_spilled_p (REGNO_REG_CLASS (REGNO (x))))
2431 *ret = true;
2434 /* A bitmap to note insns that participate in any dependency. Used in
2435 add_branch_dependences. */
2436 static sbitmap insn_referenced;
2438 /* Add dependences so that branches are scheduled to run last in their
2439 block. */
2440 static void
2441 add_branch_dependences (rtx_insn *head, rtx_insn *tail)
2443 rtx_insn *insn, *last;
2445 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2446 that can throw exceptions, force them to remain in order at the end of
2447 the block by adding dependencies and giving the last a high priority.
2448 There may be notes present, and prev_head may also be a note.
2450 Branches must obviously remain at the end. Calls should remain at the
2451 end since moving them results in worse register allocation. Uses remain
2452 at the end to ensure proper register allocation.
2454 cc0 setters remain at the end because they can't be moved away from
2455 their cc0 user.
2457 Predecessors of SCHED_GROUP_P instructions at the end remain at the end.
2459 COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
2461 Insns setting TARGET_CLASS_LIKELY_SPILLED_P registers (usually return
2462 values) are not moved before reload because we can wind up with register
2463 allocation failures. */
2465 while (tail != head && DEBUG_INSN_P (tail))
2466 tail = PREV_INSN (tail);
2468 insn = tail;
2469 last = 0;
2470 while (CALL_P (insn)
2471 || JUMP_P (insn) || JUMP_TABLE_DATA_P (insn)
2472 || (NONJUMP_INSN_P (insn)
2473 && (GET_CODE (PATTERN (insn)) == USE
2474 || GET_CODE (PATTERN (insn)) == CLOBBER
2475 || can_throw_internal (insn)
2476 || (HAVE_cc0 && sets_cc0_p (PATTERN (insn)))
2477 || (!reload_completed
2478 && sets_likely_spilled (PATTERN (insn)))))
2479 || NOTE_P (insn)
2480 || (last != 0 && SCHED_GROUP_P (last)))
2482 if (!NOTE_P (insn))
2484 if (last != 0
2485 && sd_find_dep_between (insn, last, false) == NULL)
2487 if (! sched_insns_conditions_mutex_p (last, insn))
2488 add_dependence (last, insn, REG_DEP_ANTI);
2489 bitmap_set_bit (insn_referenced, INSN_LUID (insn));
2492 CANT_MOVE (insn) = 1;
2494 last = insn;
2497 /* Don't overrun the bounds of the basic block. */
2498 if (insn == head)
2499 break;
2502 insn = PREV_INSN (insn);
2503 while (insn != head && DEBUG_INSN_P (insn));
2506 /* Make sure these insns are scheduled last in their block. */
2507 insn = last;
2508 if (insn != 0)
2509 while (insn != head)
2511 insn = prev_nonnote_insn (insn);
2513 if (bitmap_bit_p (insn_referenced, INSN_LUID (insn))
2514 || DEBUG_INSN_P (insn))
2515 continue;
2517 if (! sched_insns_conditions_mutex_p (last, insn))
2518 add_dependence (last, insn, REG_DEP_ANTI);
2521 if (!targetm.have_conditional_execution ())
2522 return;
2524 /* Finally, if the block ends in a jump, and we are doing intra-block
2525 scheduling, make sure that the branch depends on any COND_EXEC insns
2526 inside the block to avoid moving the COND_EXECs past the branch insn.
2528 We only have to do this after reload, because (1) before reload there
2529 are no COND_EXEC insns, and (2) the region scheduler is an intra-block
2530 scheduler after reload.
2532 FIXME: We could in some cases move COND_EXEC insns past the branch if
2533 this scheduler would be a little smarter. Consider this code:
2535 T = [addr]
2536 C ? addr += 4
2537 !C ? X += 12
2538 C ? T += 1
2539 C ? jump foo
2541 On a target with a one cycle stall on a memory access the optimal
2542 sequence would be:
2544 T = [addr]
2545 C ? addr += 4
2546 C ? T += 1
2547 C ? jump foo
2548 !C ? X += 12
2550 We don't want to put the 'X += 12' before the branch because it just
2551 wastes a cycle of execution time when the branch is taken.
2553 Note that in the example "!C" will always be true. That is another
2554 possible improvement for handling COND_EXECs in this scheduler: it
2555 could remove always-true predicates. */
2557 if (!reload_completed || ! (JUMP_P (tail) || JUMP_TABLE_DATA_P (tail)))
2558 return;
2560 insn = tail;
2561 while (insn != head)
2563 insn = PREV_INSN (insn);
2565 /* Note that we want to add this dependency even when
2566 sched_insns_conditions_mutex_p returns true. The whole point
2567 is that we _want_ this dependency, even if these insns really
2568 are independent. */
2569 if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC)
2570 add_dependence (tail, insn, REG_DEP_ANTI);
2574 /* Data structures for the computation of data dependences in a regions. We
2575 keep one `deps' structure for every basic block. Before analyzing the
2576 data dependences for a bb, its variables are initialized as a function of
2577 the variables of its predecessors. When the analysis for a bb completes,
2578 we save the contents to the corresponding bb_deps[bb] variable. */
2580 static struct deps_desc *bb_deps;
2582 static void
2583 concat_insn_mem_list (rtx_insn_list *copy_insns,
2584 rtx_expr_list *copy_mems,
2585 rtx_insn_list **old_insns_p,
2586 rtx_expr_list **old_mems_p)
2588 rtx_insn_list *new_insns = *old_insns_p;
2589 rtx_expr_list *new_mems = *old_mems_p;
2591 while (copy_insns)
2593 new_insns = alloc_INSN_LIST (copy_insns->insn (), new_insns);
2594 new_mems = alloc_EXPR_LIST (VOIDmode, copy_mems->element (), new_mems);
2595 copy_insns = copy_insns->next ();
2596 copy_mems = copy_mems->next ();
2599 *old_insns_p = new_insns;
2600 *old_mems_p = new_mems;
2603 /* Join PRED_DEPS to the SUCC_DEPS. */
2604 void
2605 deps_join (struct deps_desc *succ_deps, struct deps_desc *pred_deps)
2607 unsigned reg;
2608 reg_set_iterator rsi;
2610 /* The reg_last lists are inherited by successor. */
2611 EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi)
2613 struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
2614 struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
2616 succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
2617 succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
2618 succ_rl->implicit_sets
2619 = concat_INSN_LIST (pred_rl->implicit_sets, succ_rl->implicit_sets);
2620 succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
2621 succ_rl->clobbers);
2622 succ_rl->uses_length += pred_rl->uses_length;
2623 succ_rl->clobbers_length += pred_rl->clobbers_length;
2625 IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
2627 /* Mem read/write lists are inherited by successor. */
2628 concat_insn_mem_list (pred_deps->pending_read_insns,
2629 pred_deps->pending_read_mems,
2630 &succ_deps->pending_read_insns,
2631 &succ_deps->pending_read_mems);
2632 concat_insn_mem_list (pred_deps->pending_write_insns,
2633 pred_deps->pending_write_mems,
2634 &succ_deps->pending_write_insns,
2635 &succ_deps->pending_write_mems);
2637 succ_deps->pending_jump_insns
2638 = concat_INSN_LIST (pred_deps->pending_jump_insns,
2639 succ_deps->pending_jump_insns);
2640 succ_deps->last_pending_memory_flush
2641 = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
2642 succ_deps->last_pending_memory_flush);
2644 succ_deps->pending_read_list_length += pred_deps->pending_read_list_length;
2645 succ_deps->pending_write_list_length += pred_deps->pending_write_list_length;
2646 succ_deps->pending_flush_length += pred_deps->pending_flush_length;
2648 /* last_function_call is inherited by successor. */
2649 succ_deps->last_function_call
2650 = concat_INSN_LIST (pred_deps->last_function_call,
2651 succ_deps->last_function_call);
2653 /* last_function_call_may_noreturn is inherited by successor. */
2654 succ_deps->last_function_call_may_noreturn
2655 = concat_INSN_LIST (pred_deps->last_function_call_may_noreturn,
2656 succ_deps->last_function_call_may_noreturn);
2658 /* sched_before_next_call is inherited by successor. */
2659 succ_deps->sched_before_next_call
2660 = concat_INSN_LIST (pred_deps->sched_before_next_call,
2661 succ_deps->sched_before_next_call);
2664 /* After computing the dependencies for block BB, propagate the dependencies
2665 found in TMP_DEPS to the successors of the block. */
2666 static void
2667 propagate_deps (int bb, struct deps_desc *pred_deps)
2669 basic_block block = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb));
2670 edge_iterator ei;
2671 edge e;
2673 /* bb's structures are inherited by its successors. */
2674 FOR_EACH_EDGE (e, ei, block->succs)
2676 /* Only bbs "below" bb, in the same region, are interesting. */
2677 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2678 || CONTAINING_RGN (block->index) != CONTAINING_RGN (e->dest->index)
2679 || BLOCK_TO_BB (e->dest->index) <= bb)
2680 continue;
2682 deps_join (bb_deps + BLOCK_TO_BB (e->dest->index), pred_deps);
2685 /* These lists should point to the right place, for correct
2686 freeing later. */
2687 bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
2688 bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
2689 bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
2690 bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
2691 bb_deps[bb].pending_jump_insns = pred_deps->pending_jump_insns;
2693 /* Can't allow these to be freed twice. */
2694 pred_deps->pending_read_insns = 0;
2695 pred_deps->pending_read_mems = 0;
2696 pred_deps->pending_write_insns = 0;
2697 pred_deps->pending_write_mems = 0;
2698 pred_deps->pending_jump_insns = 0;
2701 /* Compute dependences inside bb. In a multiple blocks region:
2702 (1) a bb is analyzed after its predecessors, and (2) the lists in
2703 effect at the end of bb (after analyzing for bb) are inherited by
2704 bb's successors.
2706 Specifically for reg-reg data dependences, the block insns are
2707 scanned by sched_analyze () top-to-bottom. Three lists are
2708 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2709 reg_last[].implicit_sets for implicit hard register DEFs, and
2710 reg_last[].uses for register USEs.
2712 When analysis is completed for bb, we update for its successors:
2713 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2714 ; - IMPLICIT_DEFS[succ] = Union (IMPLICIT_DEFS [succ], IMPLICIT_DEFS [bb])
2715 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2717 The mechanism for computing mem-mem data dependence is very
2718 similar, and the result is interblock dependences in the region. */
2720 static void
2721 compute_block_dependences (int bb)
2723 rtx_insn *head, *tail;
2724 struct deps_desc tmp_deps;
2726 tmp_deps = bb_deps[bb];
2728 /* Do the analysis for this block. */
2729 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2730 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2732 sched_analyze (&tmp_deps, head, tail);
2734 /* Selective scheduling handles control dependencies by itself. */
2735 if (!sel_sched_p ())
2736 add_branch_dependences (head, tail);
2738 if (current_nr_blocks > 1)
2739 propagate_deps (bb, &tmp_deps);
2741 /* Free up the INSN_LISTs. */
2742 free_deps (&tmp_deps);
2744 if (targetm.sched.dependencies_evaluation_hook)
2745 targetm.sched.dependencies_evaluation_hook (head, tail);
2748 /* Free dependencies of instructions inside BB. */
2749 static void
2750 free_block_dependencies (int bb)
2752 rtx_insn *head;
2753 rtx_insn *tail;
2755 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2757 if (no_real_insns_p (head, tail))
2758 return;
2760 sched_free_deps (head, tail, true);
2763 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2764 them to the unused_*_list variables, so that they can be reused. */
2766 static void
2767 free_pending_lists (void)
2769 int bb;
2771 for (bb = 0; bb < current_nr_blocks; bb++)
2773 free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
2774 free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
2775 free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
2776 free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
2777 free_INSN_LIST_list (&bb_deps[bb].pending_jump_insns);
2781 /* Print dependences for debugging starting from FROM_BB.
2782 Callable from debugger. */
2783 /* Print dependences for debugging starting from FROM_BB.
2784 Callable from debugger. */
2785 DEBUG_FUNCTION void
2786 debug_rgn_dependencies (int from_bb)
2788 int bb;
2790 fprintf (sched_dump,
2791 ";; --------------- forward dependences: ------------ \n");
2793 for (bb = from_bb; bb < current_nr_blocks; bb++)
2795 rtx_insn *head, *tail;
2797 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2798 fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
2799 BB_TO_BLOCK (bb), bb);
2801 debug_dependencies (head, tail);
2805 /* Print dependencies information for instructions between HEAD and TAIL.
2806 ??? This function would probably fit best in haifa-sched.c. */
2807 void debug_dependencies (rtx_insn *head, rtx_insn *tail)
2809 rtx_insn *insn;
2810 rtx_insn *next_tail = NEXT_INSN (tail);
2812 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2813 "insn", "code", "bb", "dep", "prio", "cost",
2814 "reservation");
2815 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2816 "----", "----", "--", "---", "----", "----",
2817 "-----------");
2819 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2821 if (! INSN_P (insn))
2823 int n;
2824 fprintf (sched_dump, ";; %6d ", INSN_UID (insn));
2825 if (NOTE_P (insn))
2827 n = NOTE_KIND (insn);
2828 fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
2830 else
2831 fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
2832 continue;
2835 fprintf (sched_dump,
2836 ";; %s%5d%6d%6d%6d%6d%6d ",
2837 (SCHED_GROUP_P (insn) ? "+" : " "),
2838 INSN_UID (insn),
2839 INSN_CODE (insn),
2840 BLOCK_NUM (insn),
2841 sched_emulate_haifa_p ? -1 : sd_lists_size (insn, SD_LIST_BACK),
2842 (sel_sched_p () ? (sched_emulate_haifa_p ? -1
2843 : INSN_PRIORITY (insn))
2844 : INSN_PRIORITY (insn)),
2845 (sel_sched_p () ? (sched_emulate_haifa_p ? -1
2846 : insn_cost (insn))
2847 : insn_cost (insn)));
2849 if (recog_memoized (insn) < 0)
2850 fprintf (sched_dump, "nothing");
2851 else
2852 print_reservation (sched_dump, insn);
2854 fprintf (sched_dump, "\t: ");
2856 sd_iterator_def sd_it;
2857 dep_t dep;
2859 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
2860 fprintf (sched_dump, "%d%s%s ", INSN_UID (DEP_CON (dep)),
2861 DEP_NONREG (dep) ? "n" : "",
2862 DEP_MULTIPLE (dep) ? "m" : "");
2864 fprintf (sched_dump, "\n");
2867 fprintf (sched_dump, "\n");
2870 /* Returns true if all the basic blocks of the current region have
2871 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
2872 bool
2873 sched_is_disabled_for_current_region_p (void)
2875 int bb;
2877 for (bb = 0; bb < current_nr_blocks; bb++)
2878 if (!(BASIC_BLOCK_FOR_FN (cfun,
2879 BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE))
2880 return false;
2882 return true;
2885 /* Free all region dependencies saved in INSN_BACK_DEPS and
2886 INSN_RESOLVED_BACK_DEPS. The Haifa scheduler does this on the fly
2887 when scheduling, so this function is supposed to be called from
2888 the selective scheduling only. */
2889 void
2890 free_rgn_deps (void)
2892 int bb;
2894 for (bb = 0; bb < current_nr_blocks; bb++)
2896 rtx_insn *head, *tail;
2898 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2899 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2901 sched_free_deps (head, tail, false);
2905 static int rgn_n_insns;
2907 /* Compute insn priority for a current region. */
2908 void
2909 compute_priorities (void)
2911 int bb;
2913 current_sched_info->sched_max_insns_priority = 0;
2914 for (bb = 0; bb < current_nr_blocks; bb++)
2916 rtx_insn *head, *tail;
2918 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2919 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2921 if (no_real_insns_p (head, tail))
2922 continue;
2924 rgn_n_insns += set_priorities (head, tail);
2926 current_sched_info->sched_max_insns_priority++;
2929 /* (Re-)initialize the arrays of DFA states at the end of each basic block.
2931 SAVED_LAST_BASIC_BLOCK is the previous length of the arrays. It must be
2932 zero for the first call to this function, to allocate the arrays for the
2933 first time.
2935 This function is called once during initialization of the scheduler, and
2936 called again to resize the arrays if new basic blocks have been created,
2937 for example for speculation recovery code. */
2939 static void
2940 realloc_bb_state_array (int saved_last_basic_block)
2942 char *old_bb_state_array = bb_state_array;
2943 size_t lbb = (size_t) last_basic_block_for_fn (cfun);
2944 size_t slbb = (size_t) saved_last_basic_block;
2946 /* Nothing to do if nothing changed since the last time this was called. */
2947 if (saved_last_basic_block == last_basic_block_for_fn (cfun))
2948 return;
2950 /* The selective scheduler doesn't use the state arrays. */
2951 if (sel_sched_p ())
2953 gcc_assert (bb_state_array == NULL && bb_state == NULL);
2954 return;
2957 gcc_checking_assert (saved_last_basic_block == 0
2958 || (bb_state_array != NULL && bb_state != NULL));
2960 bb_state_array = XRESIZEVEC (char, bb_state_array, lbb * dfa_state_size);
2961 bb_state = XRESIZEVEC (state_t, bb_state, lbb);
2963 /* If BB_STATE_ARRAY has moved, fixup all the state pointers array.
2964 Otherwise only fixup the newly allocated ones. For the state
2965 array itself, only initialize the new entries. */
2966 bool bb_state_array_moved = (bb_state_array != old_bb_state_array);
2967 for (size_t i = bb_state_array_moved ? 0 : slbb; i < lbb; i++)
2968 bb_state[i] = (state_t) (bb_state_array + i * dfa_state_size);
2969 for (size_t i = slbb; i < lbb; i++)
2970 state_reset (bb_state[i]);
2973 /* Free the arrays of DFA states at the end of each basic block. */
2975 static void
2976 free_bb_state_array (void)
2978 free (bb_state_array);
2979 free (bb_state);
2980 bb_state_array = NULL;
2981 bb_state = NULL;
2984 /* Schedule a region. A region is either an inner loop, a loop-free
2985 subroutine, or a single basic block. Each bb in the region is
2986 scheduled after its flow predecessors. */
2988 static void
2989 schedule_region (int rgn)
2991 int bb;
2992 int sched_rgn_n_insns = 0;
2994 rgn_n_insns = 0;
2996 /* Do not support register pressure sensitive scheduling for the new regions
2997 as we don't update the liveness info for them. */
2998 if (sched_pressure != SCHED_PRESSURE_NONE
2999 && rgn >= nr_regions_initial)
3001 free_global_sched_pressure_data ();
3002 sched_pressure = SCHED_PRESSURE_NONE;
3005 rgn_setup_region (rgn);
3007 /* Don't schedule region that is marked by
3008 NOTE_DISABLE_SCHED_OF_BLOCK. */
3009 if (sched_is_disabled_for_current_region_p ())
3010 return;
3012 sched_rgn_compute_dependencies (rgn);
3014 sched_rgn_local_init (rgn);
3016 /* Set priorities. */
3017 compute_priorities ();
3019 sched_extend_ready_list (rgn_n_insns);
3021 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
3023 sched_init_region_reg_pressure_info ();
3024 for (bb = 0; bb < current_nr_blocks; bb++)
3026 basic_block first_bb, last_bb;
3027 rtx_insn *head, *tail;
3029 first_bb = EBB_FIRST_BB (bb);
3030 last_bb = EBB_LAST_BB (bb);
3032 get_ebb_head_tail (first_bb, last_bb, &head, &tail);
3034 if (no_real_insns_p (head, tail))
3036 gcc_assert (first_bb == last_bb);
3037 continue;
3039 sched_setup_bb_reg_pressure_info (first_bb, PREV_INSN (head));
3043 /* Now we can schedule all blocks. */
3044 for (bb = 0; bb < current_nr_blocks; bb++)
3046 basic_block first_bb, last_bb, curr_bb;
3047 rtx_insn *head, *tail;
3049 first_bb = EBB_FIRST_BB (bb);
3050 last_bb = EBB_LAST_BB (bb);
3052 get_ebb_head_tail (first_bb, last_bb, &head, &tail);
3054 if (no_real_insns_p (head, tail))
3056 gcc_assert (first_bb == last_bb);
3057 continue;
3060 current_sched_info->prev_head = PREV_INSN (head);
3061 current_sched_info->next_tail = NEXT_INSN (tail);
3063 remove_notes (head, tail);
3065 unlink_bb_notes (first_bb, last_bb);
3067 target_bb = bb;
3069 gcc_assert (flag_schedule_interblock || current_nr_blocks == 1);
3070 current_sched_info->queue_must_finish_empty = current_nr_blocks == 1;
3072 curr_bb = first_bb;
3073 if (dbg_cnt (sched_block))
3075 edge f;
3076 int saved_last_basic_block = last_basic_block_for_fn (cfun);
3078 schedule_block (&curr_bb, bb_state[first_bb->index]);
3079 gcc_assert (EBB_FIRST_BB (bb) == first_bb);
3080 sched_rgn_n_insns += sched_n_insns;
3081 realloc_bb_state_array (saved_last_basic_block);
3082 f = find_fallthru_edge (last_bb->succs);
3083 if (f && f->probability * 100 / REG_BR_PROB_BASE >=
3084 PARAM_VALUE (PARAM_SCHED_STATE_EDGE_PROB_CUTOFF))
3086 memcpy (bb_state[f->dest->index], curr_state,
3087 dfa_state_size);
3088 if (sched_verbose >= 5)
3089 fprintf (sched_dump, "saving state for edge %d->%d\n",
3090 f->src->index, f->dest->index);
3093 else
3095 sched_rgn_n_insns += rgn_n_insns;
3098 /* Clean up. */
3099 if (current_nr_blocks > 1)
3100 free_trg_info ();
3103 /* Sanity check: verify that all region insns were scheduled. */
3104 gcc_assert (sched_rgn_n_insns == rgn_n_insns);
3106 sched_finish_ready_list ();
3108 /* Done with this region. */
3109 sched_rgn_local_finish ();
3111 /* Free dependencies. */
3112 for (bb = 0; bb < current_nr_blocks; ++bb)
3113 free_block_dependencies (bb);
3115 gcc_assert (haifa_recovery_bb_ever_added_p
3116 || deps_pools_are_empty_p ());
3119 /* Initialize data structures for region scheduling. */
3121 void
3122 sched_rgn_init (bool single_blocks_p)
3124 min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE)
3125 / 100);
3127 nr_inter = 0;
3128 nr_spec = 0;
3130 extend_regions ();
3132 CONTAINING_RGN (ENTRY_BLOCK) = -1;
3133 CONTAINING_RGN (EXIT_BLOCK) = -1;
3135 realloc_bb_state_array (0);
3137 /* Compute regions for scheduling. */
3138 if (single_blocks_p
3139 || n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS + 1
3140 || !flag_schedule_interblock
3141 || is_cfg_nonregular ())
3143 find_single_block_region (sel_sched_p ());
3145 else
3147 /* Compute the dominators and post dominators. */
3148 if (!sel_sched_p ())
3149 calculate_dominance_info (CDI_DOMINATORS);
3151 /* Find regions. */
3152 find_rgns ();
3154 if (sched_verbose >= 3)
3155 debug_regions ();
3157 /* For now. This will move as more and more of haifa is converted
3158 to using the cfg code. */
3159 if (!sel_sched_p ())
3160 free_dominance_info (CDI_DOMINATORS);
3163 gcc_assert (0 < nr_regions && nr_regions <= n_basic_blocks_for_fn (cfun));
3165 RGN_BLOCKS (nr_regions) = (RGN_BLOCKS (nr_regions - 1) +
3166 RGN_NR_BLOCKS (nr_regions - 1));
3167 nr_regions_initial = nr_regions;
3170 /* Free data structures for region scheduling. */
3171 void
3172 sched_rgn_finish (void)
3174 free_bb_state_array ();
3176 /* Reposition the prologue and epilogue notes in case we moved the
3177 prologue/epilogue insns. */
3178 if (reload_completed)
3179 reposition_prologue_and_epilogue_notes ();
3181 if (sched_verbose)
3183 if (reload_completed == 0
3184 && flag_schedule_interblock)
3186 fprintf (sched_dump,
3187 "\n;; Procedure interblock/speculative motions == %d/%d \n",
3188 nr_inter, nr_spec);
3190 else
3191 gcc_assert (nr_inter <= 0);
3192 fprintf (sched_dump, "\n\n");
3195 nr_regions = 0;
3197 free (rgn_table);
3198 rgn_table = NULL;
3200 free (rgn_bb_table);
3201 rgn_bb_table = NULL;
3203 free (block_to_bb);
3204 block_to_bb = NULL;
3206 free (containing_rgn);
3207 containing_rgn = NULL;
3209 free (ebb_head);
3210 ebb_head = NULL;
3213 /* Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
3214 point to the region RGN. */
3215 void
3216 rgn_setup_region (int rgn)
3218 int bb;
3220 /* Set variables for the current region. */
3221 current_nr_blocks = RGN_NR_BLOCKS (rgn);
3222 current_blocks = RGN_BLOCKS (rgn);
3224 /* EBB_HEAD is a region-scope structure. But we realloc it for
3225 each region to save time/memory/something else.
3226 See comments in add_block1, for what reasons we allocate +1 element. */
3227 ebb_head = XRESIZEVEC (int, ebb_head, current_nr_blocks + 1);
3228 for (bb = 0; bb <= current_nr_blocks; bb++)
3229 ebb_head[bb] = current_blocks + bb;
3232 /* Compute instruction dependencies in region RGN. */
3233 void
3234 sched_rgn_compute_dependencies (int rgn)
3236 if (!RGN_DONT_CALC_DEPS (rgn))
3238 int bb;
3240 if (sel_sched_p ())
3241 sched_emulate_haifa_p = 1;
3243 init_deps_global ();
3245 /* Initializations for region data dependence analysis. */
3246 bb_deps = XNEWVEC (struct deps_desc, current_nr_blocks);
3247 for (bb = 0; bb < current_nr_blocks; bb++)
3248 init_deps (bb_deps + bb, false);
3250 /* Initialize bitmap used in add_branch_dependences. */
3251 insn_referenced = sbitmap_alloc (sched_max_luid);
3252 bitmap_clear (insn_referenced);
3254 /* Compute backward dependencies. */
3255 for (bb = 0; bb < current_nr_blocks; bb++)
3256 compute_block_dependences (bb);
3258 sbitmap_free (insn_referenced);
3259 free_pending_lists ();
3260 finish_deps_global ();
3261 free (bb_deps);
3263 /* We don't want to recalculate this twice. */
3264 RGN_DONT_CALC_DEPS (rgn) = 1;
3266 if (sel_sched_p ())
3267 sched_emulate_haifa_p = 0;
3269 else
3270 /* (This is a recovery block. It is always a single block region.)
3271 OR (We use selective scheduling.) */
3272 gcc_assert (current_nr_blocks == 1 || sel_sched_p ());
3275 /* Init region data structures. Returns true if this region should
3276 not be scheduled. */
3277 void
3278 sched_rgn_local_init (int rgn)
3280 int bb;
3282 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
3283 if (current_nr_blocks > 1)
3285 basic_block block;
3286 edge e;
3287 edge_iterator ei;
3289 prob = XNEWVEC (int, current_nr_blocks);
3291 dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
3292 bitmap_vector_clear (dom, current_nr_blocks);
3294 /* Use ->aux to implement EDGE_TO_BIT mapping. */
3295 rgn_nr_edges = 0;
3296 FOR_EACH_BB_FN (block, cfun)
3298 if (CONTAINING_RGN (block->index) != rgn)
3299 continue;
3300 FOR_EACH_EDGE (e, ei, block->succs)
3301 SET_EDGE_TO_BIT (e, rgn_nr_edges++);
3304 rgn_edges = XNEWVEC (edge, rgn_nr_edges);
3305 rgn_nr_edges = 0;
3306 FOR_EACH_BB_FN (block, cfun)
3308 if (CONTAINING_RGN (block->index) != rgn)
3309 continue;
3310 FOR_EACH_EDGE (e, ei, block->succs)
3311 rgn_edges[rgn_nr_edges++] = e;
3314 /* Split edges. */
3315 pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
3316 bitmap_vector_clear (pot_split, current_nr_blocks);
3317 ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
3318 bitmap_vector_clear (ancestor_edges, current_nr_blocks);
3320 /* Compute probabilities, dominators, split_edges. */
3321 for (bb = 0; bb < current_nr_blocks; bb++)
3322 compute_dom_prob_ps (bb);
3324 /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
3325 /* We don't need them anymore. But we want to avoid duplication of
3326 aux fields in the newly created edges. */
3327 FOR_EACH_BB_FN (block, cfun)
3329 if (CONTAINING_RGN (block->index) != rgn)
3330 continue;
3331 FOR_EACH_EDGE (e, ei, block->succs)
3332 e->aux = NULL;
3337 /* Free data computed for the finished region. */
3338 void
3339 sched_rgn_local_free (void)
3341 free (prob);
3342 sbitmap_vector_free (dom);
3343 sbitmap_vector_free (pot_split);
3344 sbitmap_vector_free (ancestor_edges);
3345 free (rgn_edges);
3348 /* Free data computed for the finished region. */
3349 void
3350 sched_rgn_local_finish (void)
3352 if (current_nr_blocks > 1 && !sel_sched_p ())
3354 sched_rgn_local_free ();
3358 /* Setup scheduler infos. */
3359 void
3360 rgn_setup_common_sched_info (void)
3362 memcpy (&rgn_common_sched_info, &haifa_common_sched_info,
3363 sizeof (rgn_common_sched_info));
3365 rgn_common_sched_info.fix_recovery_cfg = rgn_fix_recovery_cfg;
3366 rgn_common_sched_info.add_block = rgn_add_block;
3367 rgn_common_sched_info.estimate_number_of_insns
3368 = rgn_estimate_number_of_insns;
3369 rgn_common_sched_info.sched_pass_id = SCHED_RGN_PASS;
3371 common_sched_info = &rgn_common_sched_info;
3374 /* Setup all *_sched_info structures (for the Haifa frontend
3375 and for the dependence analysis) in the interblock scheduler. */
3376 void
3377 rgn_setup_sched_infos (void)
3379 if (!sel_sched_p ())
3380 memcpy (&rgn_sched_deps_info, &rgn_const_sched_deps_info,
3381 sizeof (rgn_sched_deps_info));
3382 else
3383 memcpy (&rgn_sched_deps_info, &rgn_const_sel_sched_deps_info,
3384 sizeof (rgn_sched_deps_info));
3386 sched_deps_info = &rgn_sched_deps_info;
3388 memcpy (&rgn_sched_info, &rgn_const_sched_info, sizeof (rgn_sched_info));
3389 current_sched_info = &rgn_sched_info;
3392 /* The one entry point in this file. */
3393 void
3394 schedule_insns (void)
3396 int rgn;
3398 /* Taking care of this degenerate case makes the rest of
3399 this code simpler. */
3400 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
3401 return;
3403 rgn_setup_common_sched_info ();
3404 rgn_setup_sched_infos ();
3406 haifa_sched_init ();
3407 sched_rgn_init (reload_completed);
3409 bitmap_initialize (&not_in_df, 0);
3410 bitmap_clear (&not_in_df);
3412 /* Schedule every region in the subroutine. */
3413 for (rgn = 0; rgn < nr_regions; rgn++)
3414 if (dbg_cnt (sched_region))
3415 schedule_region (rgn);
3417 /* Clean up. */
3418 sched_rgn_finish ();
3419 bitmap_clear (&not_in_df);
3421 haifa_sched_finish ();
3424 /* INSN has been added to/removed from current region. */
3425 static void
3426 rgn_add_remove_insn (rtx_insn *insn, int remove_p)
3428 if (!remove_p)
3429 rgn_n_insns++;
3430 else
3431 rgn_n_insns--;
3433 if (INSN_BB (insn) == target_bb)
3435 if (!remove_p)
3436 target_n_insns++;
3437 else
3438 target_n_insns--;
3442 /* Extend internal data structures. */
3443 void
3444 extend_regions (void)
3446 rgn_table = XRESIZEVEC (region, rgn_table, n_basic_blocks_for_fn (cfun));
3447 rgn_bb_table = XRESIZEVEC (int, rgn_bb_table,
3448 n_basic_blocks_for_fn (cfun));
3449 block_to_bb = XRESIZEVEC (int, block_to_bb,
3450 last_basic_block_for_fn (cfun));
3451 containing_rgn = XRESIZEVEC (int, containing_rgn,
3452 last_basic_block_for_fn (cfun));
3455 void
3456 rgn_make_new_region_out_of_new_block (basic_block bb)
3458 int i;
3460 i = RGN_BLOCKS (nr_regions);
3461 /* I - first free position in rgn_bb_table. */
3463 rgn_bb_table[i] = bb->index;
3464 RGN_NR_BLOCKS (nr_regions) = 1;
3465 RGN_HAS_REAL_EBB (nr_regions) = 0;
3466 RGN_DONT_CALC_DEPS (nr_regions) = 0;
3467 CONTAINING_RGN (bb->index) = nr_regions;
3468 BLOCK_TO_BB (bb->index) = 0;
3470 nr_regions++;
3472 RGN_BLOCKS (nr_regions) = i + 1;
3475 /* BB was added to ebb after AFTER. */
3476 static void
3477 rgn_add_block (basic_block bb, basic_block after)
3479 extend_regions ();
3480 bitmap_set_bit (&not_in_df, bb->index);
3482 if (after == 0 || after == EXIT_BLOCK_PTR_FOR_FN (cfun))
3484 rgn_make_new_region_out_of_new_block (bb);
3485 RGN_DONT_CALC_DEPS (nr_regions - 1) = (after
3486 == EXIT_BLOCK_PTR_FOR_FN (cfun));
3488 else
3490 int i, pos;
3492 /* We need to fix rgn_table, block_to_bb, containing_rgn
3493 and ebb_head. */
3495 BLOCK_TO_BB (bb->index) = BLOCK_TO_BB (after->index);
3497 /* We extend ebb_head to one more position to
3498 easily find the last position of the last ebb in
3499 the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
3500 is _always_ valid for access. */
3502 i = BLOCK_TO_BB (after->index) + 1;
3503 pos = ebb_head[i] - 1;
3504 /* Now POS is the index of the last block in the region. */
3506 /* Find index of basic block AFTER. */
3507 for (; rgn_bb_table[pos] != after->index; pos--)
3510 pos++;
3511 gcc_assert (pos > ebb_head[i - 1]);
3513 /* i - ebb right after "AFTER". */
3514 /* ebb_head[i] - VALID. */
3516 /* Source position: ebb_head[i]
3517 Destination position: ebb_head[i] + 1
3518 Last position:
3519 RGN_BLOCKS (nr_regions) - 1
3520 Number of elements to copy: (last_position) - (source_position) + 1
3523 memmove (rgn_bb_table + pos + 1,
3524 rgn_bb_table + pos,
3525 ((RGN_BLOCKS (nr_regions) - 1) - (pos) + 1)
3526 * sizeof (*rgn_bb_table));
3528 rgn_bb_table[pos] = bb->index;
3530 for (; i <= current_nr_blocks; i++)
3531 ebb_head [i]++;
3533 i = CONTAINING_RGN (after->index);
3534 CONTAINING_RGN (bb->index) = i;
3536 RGN_HAS_REAL_EBB (i) = 1;
3538 for (++i; i <= nr_regions; i++)
3539 RGN_BLOCKS (i)++;
3543 /* Fix internal data after interblock movement of jump instruction.
3544 For parameter meaning please refer to
3545 sched-int.h: struct sched_info: fix_recovery_cfg. */
3546 static void
3547 rgn_fix_recovery_cfg (int bbi, int check_bbi, int check_bb_nexti)
3549 int old_pos, new_pos, i;
3551 BLOCK_TO_BB (check_bb_nexti) = BLOCK_TO_BB (bbi);
3553 for (old_pos = ebb_head[BLOCK_TO_BB (check_bbi) + 1] - 1;
3554 rgn_bb_table[old_pos] != check_bb_nexti;
3555 old_pos--)
3557 gcc_assert (old_pos > ebb_head[BLOCK_TO_BB (check_bbi)]);
3559 for (new_pos = ebb_head[BLOCK_TO_BB (bbi) + 1] - 1;
3560 rgn_bb_table[new_pos] != bbi;
3561 new_pos--)
3563 new_pos++;
3564 gcc_assert (new_pos > ebb_head[BLOCK_TO_BB (bbi)]);
3566 gcc_assert (new_pos < old_pos);
3568 memmove (rgn_bb_table + new_pos + 1,
3569 rgn_bb_table + new_pos,
3570 (old_pos - new_pos) * sizeof (*rgn_bb_table));
3572 rgn_bb_table[new_pos] = check_bb_nexti;
3574 for (i = BLOCK_TO_BB (bbi) + 1; i <= BLOCK_TO_BB (check_bbi); i++)
3575 ebb_head[i]++;
3578 /* Return next block in ebb chain. For parameter meaning please refer to
3579 sched-int.h: struct sched_info: advance_target_bb. */
3580 static basic_block
3581 advance_target_bb (basic_block bb, rtx_insn *insn)
3583 if (insn)
3584 return 0;
3586 gcc_assert (BLOCK_TO_BB (bb->index) == target_bb
3587 && BLOCK_TO_BB (bb->next_bb->index) == target_bb);
3588 return bb->next_bb;
3591 #endif
3593 /* Run instruction scheduler. */
3594 static unsigned int
3595 rest_of_handle_live_range_shrinkage (void)
3597 #ifdef INSN_SCHEDULING
3598 int saved;
3600 initialize_live_range_shrinkage ();
3601 saved = flag_schedule_interblock;
3602 flag_schedule_interblock = false;
3603 schedule_insns ();
3604 flag_schedule_interblock = saved;
3605 finish_live_range_shrinkage ();
3606 #endif
3607 return 0;
3610 /* Run instruction scheduler. */
3611 static unsigned int
3612 rest_of_handle_sched (void)
3614 #ifdef INSN_SCHEDULING
3615 if (flag_selective_scheduling
3616 && ! maybe_skip_selective_scheduling ())
3617 run_selective_scheduling ();
3618 else
3619 schedule_insns ();
3620 #endif
3621 return 0;
3624 /* Run second scheduling pass after reload. */
3625 static unsigned int
3626 rest_of_handle_sched2 (void)
3628 #ifdef INSN_SCHEDULING
3629 if (flag_selective_scheduling2
3630 && ! maybe_skip_selective_scheduling ())
3631 run_selective_scheduling ();
3632 else
3634 /* Do control and data sched analysis again,
3635 and write some more of the results to dump file. */
3636 if (flag_sched2_use_superblocks)
3637 schedule_ebbs ();
3638 else
3639 schedule_insns ();
3641 #endif
3642 return 0;
3645 static unsigned int
3646 rest_of_handle_sched_fusion (void)
3648 #ifdef INSN_SCHEDULING
3649 sched_fusion = true;
3650 schedule_insns ();
3651 sched_fusion = false;
3652 #endif
3653 return 0;
3656 namespace {
3658 const pass_data pass_data_live_range_shrinkage =
3660 RTL_PASS, /* type */
3661 "lr_shrinkage", /* name */
3662 OPTGROUP_NONE, /* optinfo_flags */
3663 TV_LIVE_RANGE_SHRINKAGE, /* tv_id */
3664 0, /* properties_required */
3665 0, /* properties_provided */
3666 0, /* properties_destroyed */
3667 0, /* todo_flags_start */
3668 TODO_df_finish, /* todo_flags_finish */
3671 class pass_live_range_shrinkage : public rtl_opt_pass
3673 public:
3674 pass_live_range_shrinkage(gcc::context *ctxt)
3675 : rtl_opt_pass(pass_data_live_range_shrinkage, ctxt)
3678 /* opt_pass methods: */
3679 virtual bool gate (function *)
3681 #ifdef INSN_SCHEDULING
3682 return flag_live_range_shrinkage;
3683 #else
3684 return 0;
3685 #endif
3688 virtual unsigned int execute (function *)
3690 return rest_of_handle_live_range_shrinkage ();
3693 }; // class pass_live_range_shrinkage
3695 } // anon namespace
3697 rtl_opt_pass *
3698 make_pass_live_range_shrinkage (gcc::context *ctxt)
3700 return new pass_live_range_shrinkage (ctxt);
3703 namespace {
3705 const pass_data pass_data_sched =
3707 RTL_PASS, /* type */
3708 "sched1", /* name */
3709 OPTGROUP_NONE, /* optinfo_flags */
3710 TV_SCHED, /* tv_id */
3711 0, /* properties_required */
3712 0, /* properties_provided */
3713 0, /* properties_destroyed */
3714 0, /* todo_flags_start */
3715 TODO_df_finish, /* todo_flags_finish */
3718 class pass_sched : public rtl_opt_pass
3720 public:
3721 pass_sched (gcc::context *ctxt)
3722 : rtl_opt_pass (pass_data_sched, ctxt)
3725 /* opt_pass methods: */
3726 virtual bool gate (function *);
3727 virtual unsigned int execute (function *) { return rest_of_handle_sched (); }
3729 }; // class pass_sched
3731 bool
3732 pass_sched::gate (function *)
3734 #ifdef INSN_SCHEDULING
3735 return optimize > 0 && flag_schedule_insns && dbg_cnt (sched_func);
3736 #else
3737 return 0;
3738 #endif
3741 } // anon namespace
3743 rtl_opt_pass *
3744 make_pass_sched (gcc::context *ctxt)
3746 return new pass_sched (ctxt);
3749 namespace {
3751 const pass_data pass_data_sched2 =
3753 RTL_PASS, /* type */
3754 "sched2", /* name */
3755 OPTGROUP_NONE, /* optinfo_flags */
3756 TV_SCHED2, /* tv_id */
3757 0, /* properties_required */
3758 0, /* properties_provided */
3759 0, /* properties_destroyed */
3760 0, /* todo_flags_start */
3761 TODO_df_finish, /* todo_flags_finish */
3764 class pass_sched2 : public rtl_opt_pass
3766 public:
3767 pass_sched2 (gcc::context *ctxt)
3768 : rtl_opt_pass (pass_data_sched2, ctxt)
3771 /* opt_pass methods: */
3772 virtual bool gate (function *);
3773 virtual unsigned int execute (function *)
3775 return rest_of_handle_sched2 ();
3778 }; // class pass_sched2
3780 bool
3781 pass_sched2::gate (function *)
3783 #ifdef INSN_SCHEDULING
3784 return optimize > 0 && flag_schedule_insns_after_reload
3785 && !targetm.delay_sched2 && dbg_cnt (sched2_func);
3786 #else
3787 return 0;
3788 #endif
3791 } // anon namespace
3793 rtl_opt_pass *
3794 make_pass_sched2 (gcc::context *ctxt)
3796 return new pass_sched2 (ctxt);
3799 namespace {
3801 const pass_data pass_data_sched_fusion =
3803 RTL_PASS, /* type */
3804 "sched_fusion", /* name */
3805 OPTGROUP_NONE, /* optinfo_flags */
3806 TV_SCHED_FUSION, /* tv_id */
3807 0, /* properties_required */
3808 0, /* properties_provided */
3809 0, /* properties_destroyed */
3810 0, /* todo_flags_start */
3811 TODO_df_finish, /* todo_flags_finish */
3814 class pass_sched_fusion : public rtl_opt_pass
3816 public:
3817 pass_sched_fusion (gcc::context *ctxt)
3818 : rtl_opt_pass (pass_data_sched_fusion, ctxt)
3821 /* opt_pass methods: */
3822 virtual bool gate (function *);
3823 virtual unsigned int execute (function *)
3825 return rest_of_handle_sched_fusion ();
3828 }; // class pass_sched2
3830 bool
3831 pass_sched_fusion::gate (function *)
3833 #ifdef INSN_SCHEDULING
3834 /* Scheduling fusion relies on peephole2 to do real fusion work,
3835 so only enable it if peephole2 is in effect. */
3836 return (optimize > 0 && flag_peephole2
3837 && flag_schedule_fusion && targetm.sched.fusion_priority != NULL);
3838 #else
3839 return 0;
3840 #endif
3843 } // anon namespace
3845 rtl_opt_pass *
3846 make_pass_sched_fusion (gcc::context *ctxt)
3848 return new pass_sched_fusion (ctxt);