Daily bump.
[official-gcc.git] / gcc / sched-rgn.c
bloba09fc5d1066ac17a5cd2215d3f4552c51abc5dbe
1 /* Instruction scheduling pass.
2 Copyright (C) 1992-2017 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 "target.h"
51 #include "rtl.h"
52 #include "df.h"
53 #include "memmodel.h"
54 #include "tm_p.h"
55 #include "insn-config.h"
56 #include "emit-rtl.h"
57 #include "recog.h"
58 #include "profile.h"
59 #include "insn-attr.h"
60 #include "except.h"
61 #include "params.h"
62 #include "cfganal.h"
63 #include "sched-int.h"
64 #include "sel-sched.h"
65 #include "tree-pass.h"
66 #include "dbgcnt.h"
67 #include "pretty-print.h"
68 #include "print-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 struct bblst
145 basic_block *first_member;
146 int nr_members;
149 struct candidate
151 char is_valid;
152 char is_speculative;
153 int src_prob;
154 bblst split_bbs;
155 bblst update_bbs;
158 static candidate *candidate_table;
159 #define IS_VALID(src) (candidate_table[src].is_valid)
160 #define IS_SPECULATIVE(src) (candidate_table[src].is_speculative)
161 #define IS_SPECULATIVE_INSN(INSN) \
162 (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
163 #define SRC_PROB(src) ( candidate_table[src].src_prob )
165 /* The bb being currently scheduled. */
166 int target_bb;
168 /* List of edges. */
169 struct edgelst
171 edge *first_member;
172 int nr_members;
175 static edge *edgelst_table;
176 static int edgelst_last;
178 static void extract_edgelst (sbitmap, edgelst *);
180 /* Target info functions. */
181 static void split_edges (int, int, edgelst *);
182 static void compute_trg_info (int);
183 void debug_candidate (int);
184 void debug_candidates (int);
186 /* Dominators array: dom[i] contains the sbitmap of dominators of
187 bb i in the region. */
188 static sbitmap *dom;
190 /* bb 0 is the only region entry. */
191 #define IS_RGN_ENTRY(bb) (!bb)
193 /* Is bb_src dominated by bb_trg. */
194 #define IS_DOMINATED(bb_src, bb_trg) \
195 ( bitmap_bit_p (dom[bb_src], bb_trg) )
197 /* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
198 the probability of bb i relative to the region entry. */
199 static int *prob;
201 /* Bit-set of edges, where bit i stands for edge i. */
202 typedef sbitmap edgeset;
204 /* Number of edges in the region. */
205 static int rgn_nr_edges;
207 /* Array of size rgn_nr_edges. */
208 static edge *rgn_edges;
210 /* Mapping from each edge in the graph to its number in the rgn. */
211 #define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
212 #define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
214 /* The split edges of a source bb is different for each target
215 bb. In order to compute this efficiently, the 'potential-split edges'
216 are computed for each bb prior to scheduling a region. This is actually
217 the split edges of each bb relative to the region entry.
219 pot_split[bb] is the set of potential split edges of bb. */
220 static edgeset *pot_split;
222 /* For every bb, a set of its ancestor edges. */
223 static edgeset *ancestor_edges;
225 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
227 /* Speculative scheduling functions. */
228 static int check_live_1 (int, rtx);
229 static void update_live_1 (int, rtx);
230 static int is_pfree (rtx, int, int);
231 static int find_conditional_protection (rtx_insn *, int);
232 static int is_conditionally_protected (rtx, int, int);
233 static int is_prisky (rtx, int, int);
234 static int is_exception_free (rtx_insn *, int, int);
236 static bool sets_likely_spilled (rtx);
237 static void sets_likely_spilled_1 (rtx, const_rtx, void *);
238 static void add_branch_dependences (rtx_insn *, rtx_insn *);
239 static void compute_block_dependences (int);
241 static void schedule_region (int);
242 static void concat_insn_mem_list (rtx_insn_list *, rtx_expr_list *,
243 rtx_insn_list **, rtx_expr_list **);
244 static void propagate_deps (int, struct deps_desc *);
245 static void free_pending_lists (void);
247 /* Functions for construction of the control flow graph. */
249 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
251 We decide not to build the control flow graph if there is possibly more
252 than one entry to the function, if computed branches exist, if we
253 have nonlocal gotos, or if we have an unreachable loop. */
255 static int
256 is_cfg_nonregular (void)
258 basic_block b;
259 rtx_insn *insn;
261 /* If we have a label that could be the target of a nonlocal goto, then
262 the cfg is not well structured. */
263 if (nonlocal_goto_handler_labels)
264 return 1;
266 /* If we have any forced labels, then the cfg is not well structured. */
267 if (forced_labels)
268 return 1;
270 /* If we have exception handlers, then we consider the cfg not well
271 structured. ?!? We should be able to handle this now that we
272 compute an accurate cfg for EH. */
273 if (current_function_has_exception_handlers ())
274 return 1;
276 /* If we have insns which refer to labels as non-jumped-to operands,
277 then we consider the cfg not well structured. */
278 FOR_EACH_BB_FN (b, cfun)
279 FOR_BB_INSNS (b, insn)
281 rtx note, set, dest;
282 rtx_insn *next;
284 /* If this function has a computed jump, then we consider the cfg
285 not well structured. */
286 if (JUMP_P (insn) && computed_jump_p (insn))
287 return 1;
289 if (!INSN_P (insn))
290 continue;
292 note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX);
293 if (note == NULL_RTX)
294 continue;
296 /* For that label not to be seen as a referred-to label, this
297 must be a single-set which is feeding a jump *only*. This
298 could be a conditional jump with the label split off for
299 machine-specific reasons or a casesi/tablejump. */
300 next = next_nonnote_insn (insn);
301 if (next == NULL_RTX
302 || !JUMP_P (next)
303 || (JUMP_LABEL (next) != XEXP (note, 0)
304 && find_reg_note (next, REG_LABEL_TARGET,
305 XEXP (note, 0)) == NULL_RTX)
306 || BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (next))
307 return 1;
309 set = single_set (insn);
310 if (set == NULL_RTX)
311 return 1;
313 dest = SET_DEST (set);
314 if (!REG_P (dest) || !dead_or_set_p (next, dest))
315 return 1;
318 /* Unreachable loops with more than one basic block are detected
319 during the DFS traversal in find_rgns.
321 Unreachable loops with a single block are detected here. This
322 test is redundant with the one in find_rgns, but it's much
323 cheaper to go ahead and catch the trivial case here. */
324 FOR_EACH_BB_FN (b, cfun)
326 if (EDGE_COUNT (b->preds) == 0
327 || (single_pred_p (b)
328 && single_pred (b) == b))
329 return 1;
332 /* All the tests passed. Consider the cfg well structured. */
333 return 0;
336 /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */
338 static void
339 extract_edgelst (sbitmap set, edgelst *el)
341 unsigned int i = 0;
342 sbitmap_iterator sbi;
344 /* edgelst table space is reused in each call to extract_edgelst. */
345 edgelst_last = 0;
347 el->first_member = &edgelst_table[edgelst_last];
348 el->nr_members = 0;
350 /* Iterate over each word in the bitset. */
351 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, sbi)
353 edgelst_table[edgelst_last++] = rgn_edges[i];
354 el->nr_members++;
358 /* Functions for the construction of regions. */
360 /* Print the regions, for debugging purposes. Callable from debugger. */
362 DEBUG_FUNCTION void
363 debug_regions (void)
365 int rgn, bb;
367 fprintf (sched_dump, "\n;; ------------ REGIONS ----------\n\n");
368 for (rgn = 0; rgn < nr_regions; rgn++)
370 fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
371 rgn_table[rgn].rgn_nr_blocks);
372 fprintf (sched_dump, ";;\tbb/block: ");
374 /* We don't have ebb_head initialized yet, so we can't use
375 BB_TO_BLOCK (). */
376 current_blocks = RGN_BLOCKS (rgn);
378 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
379 fprintf (sched_dump, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
381 fprintf (sched_dump, "\n\n");
385 /* Print the region's basic blocks. */
387 DEBUG_FUNCTION void
388 debug_region (int rgn)
390 int bb;
392 fprintf (stderr, "\n;; ------------ REGION %d ----------\n\n", rgn);
393 fprintf (stderr, ";;\trgn %d nr_blocks %d:\n", rgn,
394 rgn_table[rgn].rgn_nr_blocks);
395 fprintf (stderr, ";;\tbb/block: ");
397 /* We don't have ebb_head initialized yet, so we can't use
398 BB_TO_BLOCK (). */
399 current_blocks = RGN_BLOCKS (rgn);
401 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
402 fprintf (stderr, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
404 fprintf (stderr, "\n\n");
406 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
408 dump_bb (stderr,
409 BASIC_BLOCK_FOR_FN (cfun, rgn_bb_table[current_blocks + bb]),
410 0, TDF_SLIM | TDF_BLOCKS);
411 fprintf (stderr, "\n");
414 fprintf (stderr, "\n");
418 /* True when a bb with index BB_INDEX contained in region RGN. */
419 static bool
420 bb_in_region_p (int bb_index, int rgn)
422 int i;
424 for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
425 if (rgn_bb_table[current_blocks + i] == bb_index)
426 return true;
428 return false;
431 /* Dump region RGN to file F using dot syntax. */
432 void
433 dump_region_dot (FILE *f, int rgn)
435 int i;
437 fprintf (f, "digraph Region_%d {\n", rgn);
439 /* We don't have ebb_head initialized yet, so we can't use
440 BB_TO_BLOCK (). */
441 current_blocks = RGN_BLOCKS (rgn);
443 for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
445 edge e;
446 edge_iterator ei;
447 int src_bb_num = rgn_bb_table[current_blocks + i];
448 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, src_bb_num);
450 FOR_EACH_EDGE (e, ei, bb->succs)
451 if (bb_in_region_p (e->dest->index, rgn))
452 fprintf (f, "\t%d -> %d\n", src_bb_num, e->dest->index);
454 fprintf (f, "}\n");
457 /* The same, but first open a file specified by FNAME. */
458 void
459 dump_region_dot_file (const char *fname, int rgn)
461 FILE *f = fopen (fname, "wt");
462 dump_region_dot (f, rgn);
463 fclose (f);
466 /* Build a single block region for each basic block in the function.
467 This allows for using the same code for interblock and basic block
468 scheduling. */
470 static void
471 find_single_block_region (bool ebbs_p)
473 basic_block bb, ebb_start;
474 int i = 0;
476 nr_regions = 0;
478 if (ebbs_p) {
479 int probability_cutoff;
480 if (profile_info && flag_branch_probabilities)
481 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
482 else
483 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
484 probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
486 FOR_EACH_BB_FN (ebb_start, cfun)
488 RGN_NR_BLOCKS (nr_regions) = 0;
489 RGN_BLOCKS (nr_regions) = i;
490 RGN_DONT_CALC_DEPS (nr_regions) = 0;
491 RGN_HAS_REAL_EBB (nr_regions) = 0;
493 for (bb = ebb_start; ; bb = bb->next_bb)
495 edge e;
497 rgn_bb_table[i] = bb->index;
498 RGN_NR_BLOCKS (nr_regions)++;
499 CONTAINING_RGN (bb->index) = nr_regions;
500 BLOCK_TO_BB (bb->index) = i - RGN_BLOCKS (nr_regions);
501 i++;
503 if (bb->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
504 || LABEL_P (BB_HEAD (bb->next_bb)))
505 break;
507 e = find_fallthru_edge (bb->succs);
508 if (! e)
509 break;
510 if (e->probability <= probability_cutoff)
511 break;
514 ebb_start = bb;
515 nr_regions++;
518 else
519 FOR_EACH_BB_FN (bb, cfun)
521 rgn_bb_table[nr_regions] = bb->index;
522 RGN_NR_BLOCKS (nr_regions) = 1;
523 RGN_BLOCKS (nr_regions) = nr_regions;
524 RGN_DONT_CALC_DEPS (nr_regions) = 0;
525 RGN_HAS_REAL_EBB (nr_regions) = 0;
527 CONTAINING_RGN (bb->index) = nr_regions;
528 BLOCK_TO_BB (bb->index) = 0;
529 nr_regions++;
533 /* Estimate number of the insns in the BB. */
534 static int
535 rgn_estimate_number_of_insns (basic_block bb)
537 int count;
539 count = INSN_LUID (BB_END (bb)) - INSN_LUID (BB_HEAD (bb));
541 if (MAY_HAVE_DEBUG_INSNS)
543 rtx_insn *insn;
545 FOR_BB_INSNS (bb, insn)
546 if (DEBUG_INSN_P (insn))
547 count--;
550 return count;
553 /* Update number of blocks and the estimate for number of insns
554 in the region. Return true if the region is "too large" for interblock
555 scheduling (compile time considerations). */
557 static bool
558 too_large (int block, int *num_bbs, int *num_insns)
560 (*num_bbs)++;
561 (*num_insns) += (common_sched_info->estimate_number_of_insns
562 (BASIC_BLOCK_FOR_FN (cfun, block)));
564 return ((*num_bbs > PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS))
565 || (*num_insns > PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS)));
568 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
569 is still an inner loop. Put in max_hdr[blk] the header of the most inner
570 loop containing blk. */
571 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
573 if (max_hdr[blk] == -1) \
574 max_hdr[blk] = hdr; \
575 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
576 bitmap_clear_bit (inner, hdr); \
577 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
579 bitmap_clear_bit (inner,max_hdr[blk]); \
580 max_hdr[blk] = hdr; \
584 /* Find regions for interblock scheduling.
586 A region for scheduling can be:
588 * A loop-free procedure, or
590 * A reducible inner loop, or
592 * A basic block not contained in any other region.
594 ?!? In theory we could build other regions based on extended basic
595 blocks or reverse extended basic blocks. Is it worth the trouble?
597 Loop blocks that form a region are put into the region's block list
598 in topological order.
600 This procedure stores its results into the following global (ick) variables
602 * rgn_nr
603 * rgn_table
604 * rgn_bb_table
605 * block_to_bb
606 * containing region
608 We use dominator relationships to avoid making regions out of non-reducible
609 loops.
611 This procedure needs to be converted to work on pred/succ lists instead
612 of edge tables. That would simplify it somewhat. */
614 static void
615 haifa_find_rgns (void)
617 int *max_hdr, *dfs_nr, *degree;
618 char no_loops = 1;
619 int node, child, loop_head, i, head, tail;
620 int count = 0, sp, idx = 0;
621 edge_iterator current_edge;
622 edge_iterator *stack;
623 int num_bbs, num_insns, unreachable;
624 int too_large_failure;
625 basic_block bb;
627 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
628 and a mapping from block to its loop header (if the block is contained
629 in a loop, else -1).
631 Store results in HEADER, INNER, and MAX_HDR respectively, these will
632 be used as inputs to the second traversal.
634 STACK, SP and DFS_NR are only used during the first traversal. */
636 /* Allocate and initialize variables for the first traversal. */
637 max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
638 dfs_nr = XCNEWVEC (int, last_basic_block_for_fn (cfun));
639 stack = XNEWVEC (edge_iterator, n_edges_for_fn (cfun));
641 /* Note if a block is a natural inner loop header. */
642 auto_sbitmap inner (last_basic_block_for_fn (cfun));
643 bitmap_ones (inner);
645 /* Note if a block is a natural loop header. */
646 auto_sbitmap header (last_basic_block_for_fn (cfun));
647 bitmap_clear (header);
649 /* Note if a block is in the block queue. */
650 auto_sbitmap in_queue (last_basic_block_for_fn (cfun));
651 bitmap_clear (in_queue);
653 /* Note if a block is in the block queue. */
654 auto_sbitmap in_stack (last_basic_block_for_fn (cfun));
655 bitmap_clear (in_stack);
657 for (i = 0; i < last_basic_block_for_fn (cfun); i++)
658 max_hdr[i] = -1;
660 #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
661 #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
663 /* DFS traversal to find inner loops in the cfg. */
665 current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))->succs);
666 sp = -1;
668 while (1)
670 if (EDGE_PASSED (current_edge))
672 /* We have reached a leaf node or a node that was already
673 processed. Pop edges off the stack until we find
674 an edge that has not yet been processed. */
675 while (sp >= 0 && EDGE_PASSED (current_edge))
677 /* Pop entry off the stack. */
678 current_edge = stack[sp--];
679 node = ei_edge (current_edge)->src->index;
680 gcc_assert (node != ENTRY_BLOCK);
681 child = ei_edge (current_edge)->dest->index;
682 gcc_assert (child != EXIT_BLOCK);
683 bitmap_clear_bit (in_stack, child);
684 if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
685 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
686 ei_next (&current_edge);
689 /* See if have finished the DFS tree traversal. */
690 if (sp < 0 && EDGE_PASSED (current_edge))
691 break;
693 /* Nope, continue the traversal with the popped node. */
694 continue;
697 /* Process a node. */
698 node = ei_edge (current_edge)->src->index;
699 gcc_assert (node != ENTRY_BLOCK);
700 bitmap_set_bit (in_stack, node);
701 dfs_nr[node] = ++count;
703 /* We don't traverse to the exit block. */
704 child = ei_edge (current_edge)->dest->index;
705 if (child == EXIT_BLOCK)
707 SET_EDGE_PASSED (current_edge);
708 ei_next (&current_edge);
709 continue;
712 /* If the successor is in the stack, then we've found a loop.
713 Mark the loop, if it is not a natural loop, then it will
714 be rejected during the second traversal. */
715 if (bitmap_bit_p (in_stack, child))
717 no_loops = 0;
718 bitmap_set_bit (header, child);
719 UPDATE_LOOP_RELATIONS (node, child);
720 SET_EDGE_PASSED (current_edge);
721 ei_next (&current_edge);
722 continue;
725 /* If the child was already visited, then there is no need to visit
726 it again. Just update the loop relationships and restart
727 with a new edge. */
728 if (dfs_nr[child])
730 if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
731 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
732 SET_EDGE_PASSED (current_edge);
733 ei_next (&current_edge);
734 continue;
737 /* Push an entry on the stack and continue DFS traversal. */
738 stack[++sp] = current_edge;
739 SET_EDGE_PASSED (current_edge);
740 current_edge = ei_start (ei_edge (current_edge)->dest->succs);
743 /* Reset ->aux field used by EDGE_PASSED. */
744 FOR_ALL_BB_FN (bb, cfun)
746 edge_iterator ei;
747 edge e;
748 FOR_EACH_EDGE (e, ei, bb->succs)
749 e->aux = NULL;
753 /* Another check for unreachable blocks. The earlier test in
754 is_cfg_nonregular only finds unreachable blocks that do not
755 form a loop.
757 The DFS traversal will mark every block that is reachable from
758 the entry node by placing a nonzero value in dfs_nr. Thus if
759 dfs_nr is zero for any block, then it must be unreachable. */
760 unreachable = 0;
761 FOR_EACH_BB_FN (bb, cfun)
762 if (dfs_nr[bb->index] == 0)
764 unreachable = 1;
765 break;
768 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
769 to hold degree counts. */
770 degree = dfs_nr;
772 FOR_EACH_BB_FN (bb, cfun)
773 degree[bb->index] = EDGE_COUNT (bb->preds);
775 /* Do not perform region scheduling if there are any unreachable
776 blocks. */
777 if (!unreachable)
779 int *queue, *degree1 = NULL;
780 /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
781 there basic blocks, which are forced to be region heads.
782 This is done to try to assemble few smaller regions
783 from a too_large region. */
784 sbitmap extended_rgn_header = NULL;
785 bool extend_regions_p;
787 if (no_loops)
788 bitmap_set_bit (header, 0);
790 /* Second traversal:find reducible inner loops and topologically sort
791 block of each region. */
793 queue = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
795 extend_regions_p = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS) > 0;
796 if (extend_regions_p)
798 degree1 = XNEWVEC (int, last_basic_block_for_fn (cfun));
799 extended_rgn_header =
800 sbitmap_alloc (last_basic_block_for_fn (cfun));
801 bitmap_clear (extended_rgn_header);
804 /* Find blocks which are inner loop headers. We still have non-reducible
805 loops to consider at this point. */
806 FOR_EACH_BB_FN (bb, cfun)
808 if (bitmap_bit_p (header, bb->index) && bitmap_bit_p (inner, bb->index))
810 edge e;
811 edge_iterator ei;
812 basic_block jbb;
814 /* Now check that the loop is reducible. We do this separate
815 from finding inner loops so that we do not find a reducible
816 loop which contains an inner non-reducible loop.
818 A simple way to find reducible/natural loops is to verify
819 that each block in the loop is dominated by the loop
820 header.
822 If there exists a block that is not dominated by the loop
823 header, then the block is reachable from outside the loop
824 and thus the loop is not a natural loop. */
825 FOR_EACH_BB_FN (jbb, cfun)
827 /* First identify blocks in the loop, except for the loop
828 entry block. */
829 if (bb->index == max_hdr[jbb->index] && bb != jbb)
831 /* Now verify that the block is dominated by the loop
832 header. */
833 if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))
834 break;
838 /* If we exited the loop early, then I is the header of
839 a non-reducible loop and we should quit processing it
840 now. */
841 if (jbb != EXIT_BLOCK_PTR_FOR_FN (cfun))
842 continue;
844 /* I is a header of an inner loop, or block 0 in a subroutine
845 with no loops at all. */
846 head = tail = -1;
847 too_large_failure = 0;
848 loop_head = max_hdr[bb->index];
850 if (extend_regions_p)
851 /* We save degree in case when we meet a too_large region
852 and cancel it. We need a correct degree later when
853 calling extend_rgns. */
854 memcpy (degree1, degree,
855 last_basic_block_for_fn (cfun) * sizeof (int));
857 /* Decrease degree of all I's successors for topological
858 ordering. */
859 FOR_EACH_EDGE (e, ei, bb->succs)
860 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
861 --degree[e->dest->index];
863 /* Estimate # insns, and count # blocks in the region. */
864 num_bbs = 1;
865 num_insns = common_sched_info->estimate_number_of_insns (bb);
867 /* Find all loop latches (blocks with back edges to the loop
868 header) or all the leaf blocks in the cfg has no loops.
870 Place those blocks into the queue. */
871 if (no_loops)
873 FOR_EACH_BB_FN (jbb, cfun)
874 /* Leaf nodes have only a single successor which must
875 be EXIT_BLOCK. */
876 if (single_succ_p (jbb)
877 && single_succ (jbb) == EXIT_BLOCK_PTR_FOR_FN (cfun))
879 queue[++tail] = jbb->index;
880 bitmap_set_bit (in_queue, jbb->index);
882 if (too_large (jbb->index, &num_bbs, &num_insns))
884 too_large_failure = 1;
885 break;
889 else
891 edge e;
893 FOR_EACH_EDGE (e, ei, bb->preds)
895 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
896 continue;
898 node = e->src->index;
900 if (max_hdr[node] == loop_head && node != bb->index)
902 /* This is a loop latch. */
903 queue[++tail] = node;
904 bitmap_set_bit (in_queue, node);
906 if (too_large (node, &num_bbs, &num_insns))
908 too_large_failure = 1;
909 break;
915 /* Now add all the blocks in the loop to the queue.
917 We know the loop is a natural loop; however the algorithm
918 above will not always mark certain blocks as being in the
919 loop. Consider:
920 node children
921 a b,c
923 c a,d
926 The algorithm in the DFS traversal may not mark B & D as part
927 of the loop (i.e. they will not have max_hdr set to A).
929 We know they can not be loop latches (else they would have
930 had max_hdr set since they'd have a backedge to a dominator
931 block). So we don't need them on the initial queue.
933 We know they are part of the loop because they are dominated
934 by the loop header and can be reached by a backwards walk of
935 the edges starting with nodes on the initial queue.
937 It is safe and desirable to include those nodes in the
938 loop/scheduling region. To do so we would need to decrease
939 the degree of a node if it is the target of a backedge
940 within the loop itself as the node is placed in the queue.
942 We do not do this because I'm not sure that the actual
943 scheduling code will properly handle this case. ?!? */
945 while (head < tail && !too_large_failure)
947 edge e;
948 child = queue[++head];
950 FOR_EACH_EDGE (e, ei,
951 BASIC_BLOCK_FOR_FN (cfun, child)->preds)
953 node = e->src->index;
955 /* See discussion above about nodes not marked as in
956 this loop during the initial DFS traversal. */
957 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
958 || max_hdr[node] != loop_head)
960 tail = -1;
961 break;
963 else if (!bitmap_bit_p (in_queue, node) && node != bb->index)
965 queue[++tail] = node;
966 bitmap_set_bit (in_queue, node);
968 if (too_large (node, &num_bbs, &num_insns))
970 too_large_failure = 1;
971 break;
977 if (tail >= 0 && !too_large_failure)
979 /* Place the loop header into list of region blocks. */
980 degree[bb->index] = -1;
981 rgn_bb_table[idx] = bb->index;
982 RGN_NR_BLOCKS (nr_regions) = num_bbs;
983 RGN_BLOCKS (nr_regions) = idx++;
984 RGN_DONT_CALC_DEPS (nr_regions) = 0;
985 RGN_HAS_REAL_EBB (nr_regions) = 0;
986 CONTAINING_RGN (bb->index) = nr_regions;
987 BLOCK_TO_BB (bb->index) = count = 0;
989 /* Remove blocks from queue[] when their in degree
990 becomes zero. Repeat until no blocks are left on the
991 list. This produces a topological list of blocks in
992 the region. */
993 while (tail >= 0)
995 if (head < 0)
996 head = tail;
997 child = queue[head];
998 if (degree[child] == 0)
1000 edge e;
1002 degree[child] = -1;
1003 rgn_bb_table[idx++] = child;
1004 BLOCK_TO_BB (child) = ++count;
1005 CONTAINING_RGN (child) = nr_regions;
1006 queue[head] = queue[tail--];
1008 FOR_EACH_EDGE (e, ei,
1009 BASIC_BLOCK_FOR_FN (cfun,
1010 child)->succs)
1011 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1012 --degree[e->dest->index];
1014 else
1015 --head;
1017 ++nr_regions;
1019 else if (extend_regions_p)
1021 /* Restore DEGREE. */
1022 int *t = degree;
1024 degree = degree1;
1025 degree1 = t;
1027 /* And force successors of BB to be region heads.
1028 This may provide several smaller regions instead
1029 of one too_large region. */
1030 FOR_EACH_EDGE (e, ei, bb->succs)
1031 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1032 bitmap_set_bit (extended_rgn_header, e->dest->index);
1036 free (queue);
1038 if (extend_regions_p)
1040 free (degree1);
1042 bitmap_ior (header, header, extended_rgn_header);
1043 sbitmap_free (extended_rgn_header);
1045 extend_rgns (degree, &idx, header, max_hdr);
1049 /* Any block that did not end up in a region is placed into a region
1050 by itself. */
1051 FOR_EACH_BB_FN (bb, cfun)
1052 if (degree[bb->index] >= 0)
1054 rgn_bb_table[idx] = bb->index;
1055 RGN_NR_BLOCKS (nr_regions) = 1;
1056 RGN_BLOCKS (nr_regions) = idx++;
1057 RGN_DONT_CALC_DEPS (nr_regions) = 0;
1058 RGN_HAS_REAL_EBB (nr_regions) = 0;
1059 CONTAINING_RGN (bb->index) = nr_regions++;
1060 BLOCK_TO_BB (bb->index) = 0;
1063 free (max_hdr);
1064 free (degree);
1065 free (stack);
1069 /* Wrapper function.
1070 If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
1071 regions. Otherwise just call find_rgns_haifa. */
1072 static void
1073 find_rgns (void)
1075 if (sel_sched_p () && flag_sel_sched_pipelining)
1076 sel_find_rgns ();
1077 else
1078 haifa_find_rgns ();
1081 static int gather_region_statistics (int **);
1082 static void print_region_statistics (int *, int, int *, int);
1084 /* Calculate the histogram that shows the number of regions having the
1085 given number of basic blocks, and store it in the RSP array. Return
1086 the size of this array. */
1087 static int
1088 gather_region_statistics (int **rsp)
1090 int i, *a = 0, a_sz = 0;
1092 /* a[i] is the number of regions that have (i + 1) basic blocks. */
1093 for (i = 0; i < nr_regions; i++)
1095 int nr_blocks = RGN_NR_BLOCKS (i);
1097 gcc_assert (nr_blocks >= 1);
1099 if (nr_blocks > a_sz)
1101 a = XRESIZEVEC (int, a, nr_blocks);
1103 a[a_sz++] = 0;
1104 while (a_sz != nr_blocks);
1107 a[nr_blocks - 1]++;
1110 *rsp = a;
1111 return a_sz;
1114 /* Print regions statistics. S1 and S2 denote the data before and after
1115 calling extend_rgns, respectively. */
1116 static void
1117 print_region_statistics (int *s1, int s1_sz, int *s2, int s2_sz)
1119 int i;
1121 /* We iterate until s2_sz because extend_rgns does not decrease
1122 the maximal region size. */
1123 for (i = 1; i < s2_sz; i++)
1125 int n1, n2;
1127 n2 = s2[i];
1129 if (n2 == 0)
1130 continue;
1132 if (i >= s1_sz)
1133 n1 = 0;
1134 else
1135 n1 = s1[i];
1137 fprintf (sched_dump, ";; Region extension statistics: size %d: " \
1138 "was %d + %d more\n", i + 1, n1, n2 - n1);
1142 /* Extend regions.
1143 DEGREE - Array of incoming edge count, considering only
1144 the edges, that don't have their sources in formed regions yet.
1145 IDXP - pointer to the next available index in rgn_bb_table.
1146 HEADER - set of all region heads.
1147 LOOP_HDR - mapping from block to the containing loop
1148 (two blocks can reside within one region if they have
1149 the same loop header). */
1150 void
1151 extend_rgns (int *degree, int *idxp, sbitmap header, int *loop_hdr)
1153 int *order, i, rescan = 0, idx = *idxp, iter = 0, max_iter, *max_hdr;
1154 int nblocks = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
1156 max_iter = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS);
1158 max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
1160 order = XNEWVEC (int, last_basic_block_for_fn (cfun));
1161 post_order_compute (order, false, false);
1163 for (i = nblocks - 1; i >= 0; i--)
1165 int bbn = order[i];
1166 if (degree[bbn] >= 0)
1168 max_hdr[bbn] = bbn;
1169 rescan = 1;
1171 else
1172 /* This block already was processed in find_rgns. */
1173 max_hdr[bbn] = -1;
1176 /* The idea is to topologically walk through CFG in top-down order.
1177 During the traversal, if all the predecessors of a node are
1178 marked to be in the same region (they all have the same max_hdr),
1179 then current node is also marked to be a part of that region.
1180 Otherwise the node starts its own region.
1181 CFG should be traversed until no further changes are made. On each
1182 iteration the set of the region heads is extended (the set of those
1183 blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
1184 set of all basic blocks, thus the algorithm is guaranteed to
1185 terminate. */
1187 while (rescan && iter < max_iter)
1189 rescan = 0;
1191 for (i = nblocks - 1; i >= 0; i--)
1193 edge e;
1194 edge_iterator ei;
1195 int bbn = order[i];
1197 if (max_hdr[bbn] != -1 && !bitmap_bit_p (header, bbn))
1199 int hdr = -1;
1201 FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->preds)
1203 int predn = e->src->index;
1205 if (predn != ENTRY_BLOCK
1206 /* If pred wasn't processed in find_rgns. */
1207 && max_hdr[predn] != -1
1208 /* And pred and bb reside in the same loop.
1209 (Or out of any loop). */
1210 && loop_hdr[bbn] == loop_hdr[predn])
1212 if (hdr == -1)
1213 /* Then bb extends the containing region of pred. */
1214 hdr = max_hdr[predn];
1215 else if (hdr != max_hdr[predn])
1216 /* Too bad, there are at least two predecessors
1217 that reside in different regions. Thus, BB should
1218 begin its own region. */
1220 hdr = bbn;
1221 break;
1224 else
1225 /* BB starts its own region. */
1227 hdr = bbn;
1228 break;
1232 if (hdr == bbn)
1234 /* If BB start its own region,
1235 update set of headers with BB. */
1236 bitmap_set_bit (header, bbn);
1237 rescan = 1;
1239 else
1240 gcc_assert (hdr != -1);
1242 max_hdr[bbn] = hdr;
1246 iter++;
1249 /* Statistics were gathered on the SPEC2000 package of tests with
1250 mainline weekly snapshot gcc-4.1-20051015 on ia64.
1252 Statistics for SPECint:
1253 1 iteration : 1751 cases (38.7%)
1254 2 iterations: 2770 cases (61.3%)
1255 Blocks wrapped in regions by find_rgns without extension: 18295 blocks
1256 Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
1257 (We don't count single block regions here).
1259 Statistics for SPECfp:
1260 1 iteration : 621 cases (35.9%)
1261 2 iterations: 1110 cases (64.1%)
1262 Blocks wrapped in regions by find_rgns without extension: 6476 blocks
1263 Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
1264 (We don't count single block regions here).
1266 By default we do at most 2 iterations.
1267 This can be overridden with max-sched-extend-regions-iters parameter:
1268 0 - disable region extension,
1269 N > 0 - do at most N iterations. */
1271 if (sched_verbose && iter != 0)
1272 fprintf (sched_dump, ";; Region extension iterations: %d%s\n", iter,
1273 rescan ? "... failed" : "");
1275 if (!rescan && iter != 0)
1277 int *s1 = NULL, s1_sz = 0;
1279 /* Save the old statistics for later printout. */
1280 if (sched_verbose >= 6)
1281 s1_sz = gather_region_statistics (&s1);
1283 /* We have succeeded. Now assemble the regions. */
1284 for (i = nblocks - 1; i >= 0; i--)
1286 int bbn = order[i];
1288 if (max_hdr[bbn] == bbn)
1289 /* BBN is a region head. */
1291 edge e;
1292 edge_iterator ei;
1293 int num_bbs = 0, j, num_insns = 0, large;
1295 large = too_large (bbn, &num_bbs, &num_insns);
1297 degree[bbn] = -1;
1298 rgn_bb_table[idx] = bbn;
1299 RGN_BLOCKS (nr_regions) = idx++;
1300 RGN_DONT_CALC_DEPS (nr_regions) = 0;
1301 RGN_HAS_REAL_EBB (nr_regions) = 0;
1302 CONTAINING_RGN (bbn) = nr_regions;
1303 BLOCK_TO_BB (bbn) = 0;
1305 FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->succs)
1306 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1307 degree[e->dest->index]--;
1309 if (!large)
1310 /* Here we check whether the region is too_large. */
1311 for (j = i - 1; j >= 0; j--)
1313 int succn = order[j];
1314 if (max_hdr[succn] == bbn)
1316 if ((large = too_large (succn, &num_bbs, &num_insns)))
1317 break;
1321 if (large)
1322 /* If the region is too_large, then wrap every block of
1323 the region into single block region.
1324 Here we wrap region head only. Other blocks are
1325 processed in the below cycle. */
1327 RGN_NR_BLOCKS (nr_regions) = 1;
1328 nr_regions++;
1331 num_bbs = 1;
1333 for (j = i - 1; j >= 0; j--)
1335 int succn = order[j];
1337 if (max_hdr[succn] == bbn)
1338 /* This cycle iterates over all basic blocks, that
1339 are supposed to be in the region with head BBN,
1340 and wraps them into that region (or in single
1341 block region). */
1343 gcc_assert (degree[succn] == 0);
1345 degree[succn] = -1;
1346 rgn_bb_table[idx] = succn;
1347 BLOCK_TO_BB (succn) = large ? 0 : num_bbs++;
1348 CONTAINING_RGN (succn) = nr_regions;
1350 if (large)
1351 /* Wrap SUCCN into single block region. */
1353 RGN_BLOCKS (nr_regions) = idx;
1354 RGN_NR_BLOCKS (nr_regions) = 1;
1355 RGN_DONT_CALC_DEPS (nr_regions) = 0;
1356 RGN_HAS_REAL_EBB (nr_regions) = 0;
1357 nr_regions++;
1360 idx++;
1362 FOR_EACH_EDGE (e, ei,
1363 BASIC_BLOCK_FOR_FN (cfun, succn)->succs)
1364 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1365 degree[e->dest->index]--;
1369 if (!large)
1371 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1372 nr_regions++;
1377 if (sched_verbose >= 6)
1379 int *s2, s2_sz;
1381 /* Get the new statistics and print the comparison with the
1382 one before calling this function. */
1383 s2_sz = gather_region_statistics (&s2);
1384 print_region_statistics (s1, s1_sz, s2, s2_sz);
1385 free (s1);
1386 free (s2);
1390 free (order);
1391 free (max_hdr);
1393 *idxp = idx;
1396 /* Functions for regions scheduling information. */
1398 /* Compute dominators, probability, and potential-split-edges of bb.
1399 Assume that these values were already computed for bb's predecessors. */
1401 static void
1402 compute_dom_prob_ps (int bb)
1404 edge_iterator in_ei;
1405 edge in_edge;
1407 /* We shouldn't have any real ebbs yet. */
1408 gcc_assert (ebb_head [bb] == bb + current_blocks);
1410 if (IS_RGN_ENTRY (bb))
1412 bitmap_set_bit (dom[bb], 0);
1413 prob[bb] = REG_BR_PROB_BASE;
1414 return;
1417 prob[bb] = 0;
1419 /* Initialize dom[bb] to '111..1'. */
1420 bitmap_ones (dom[bb]);
1422 FOR_EACH_EDGE (in_edge, in_ei,
1423 BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb))->preds)
1425 int pred_bb;
1426 edge out_edge;
1427 edge_iterator out_ei;
1429 if (in_edge->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1430 continue;
1432 pred_bb = BLOCK_TO_BB (in_edge->src->index);
1433 bitmap_and (dom[bb], dom[bb], dom[pred_bb]);
1434 bitmap_ior (ancestor_edges[bb],
1435 ancestor_edges[bb], ancestor_edges[pred_bb]);
1437 bitmap_set_bit (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
1439 bitmap_ior (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
1441 FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
1442 bitmap_set_bit (pot_split[bb], EDGE_TO_BIT (out_edge));
1444 prob[bb] += combine_probabilities (prob[pred_bb], in_edge->probability);
1445 // The rounding divide in combine_probabilities can result in an extra
1446 // probability increment propagating along 50-50 edges. Eventually when
1447 // the edges re-merge, the accumulated probability can go slightly above
1448 // REG_BR_PROB_BASE.
1449 if (prob[bb] > REG_BR_PROB_BASE)
1450 prob[bb] = REG_BR_PROB_BASE;
1453 bitmap_set_bit (dom[bb], bb);
1454 bitmap_and_compl (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
1456 if (sched_verbose >= 2)
1457 fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
1458 (100 * prob[bb]) / REG_BR_PROB_BASE);
1461 /* Functions for target info. */
1463 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1464 Note that bb_trg dominates bb_src. */
1466 static void
1467 split_edges (int bb_src, int bb_trg, edgelst *bl)
1469 auto_sbitmap src (SBITMAP_SIZE (pot_split[bb_src]));
1470 bitmap_copy (src, pot_split[bb_src]);
1472 bitmap_and_compl (src, src, pot_split[bb_trg]);
1473 extract_edgelst (src, bl);
1476 /* Find the valid candidate-source-blocks for the target block TRG, compute
1477 their probability, and check if they are speculative or not.
1478 For speculative sources, compute their update-blocks and split-blocks. */
1480 static void
1481 compute_trg_info (int trg)
1483 candidate *sp;
1484 edgelst el = { NULL, 0 };
1485 int i, j, k, update_idx;
1486 basic_block block;
1487 edge_iterator ei;
1488 edge e;
1490 candidate_table = XNEWVEC (candidate, current_nr_blocks);
1492 bblst_last = 0;
1493 /* bblst_table holds split blocks and update blocks for each block after
1494 the current one in the region. split blocks and update blocks are
1495 the TO blocks of region edges, so there can be at most rgn_nr_edges
1496 of them. */
1497 bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
1498 bblst_table = XNEWVEC (basic_block, bblst_size);
1500 edgelst_last = 0;
1501 edgelst_table = XNEWVEC (edge, rgn_nr_edges);
1503 /* Define some of the fields for the target bb as well. */
1504 sp = candidate_table + trg;
1505 sp->is_valid = 1;
1506 sp->is_speculative = 0;
1507 sp->src_prob = REG_BR_PROB_BASE;
1509 auto_sbitmap visited (last_basic_block_for_fn (cfun));
1511 for (i = trg + 1; i < current_nr_blocks; i++)
1513 sp = candidate_table + i;
1515 sp->is_valid = IS_DOMINATED (i, trg);
1516 if (sp->is_valid)
1518 int tf = prob[trg], cf = prob[i];
1520 /* In CFGs with low probability edges TF can possibly be zero. */
1521 sp->src_prob = (tf ? GCOV_COMPUTE_SCALE (cf, tf) : 0);
1522 sp->is_valid = (sp->src_prob >= min_spec_prob);
1525 if (sp->is_valid)
1527 split_edges (i, trg, &el);
1528 sp->is_speculative = (el.nr_members) ? 1 : 0;
1529 if (sp->is_speculative && !flag_schedule_speculative)
1530 sp->is_valid = 0;
1533 if (sp->is_valid)
1535 /* Compute split blocks and store them in bblst_table.
1536 The TO block of every split edge is a split block. */
1537 sp->split_bbs.first_member = &bblst_table[bblst_last];
1538 sp->split_bbs.nr_members = el.nr_members;
1539 for (j = 0; j < el.nr_members; bblst_last++, j++)
1540 bblst_table[bblst_last] = el.first_member[j]->dest;
1541 sp->update_bbs.first_member = &bblst_table[bblst_last];
1543 /* Compute update blocks and store them in bblst_table.
1544 For every split edge, look at the FROM block, and check
1545 all out edges. For each out edge that is not a split edge,
1546 add the TO block to the update block list. This list can end
1547 up with a lot of duplicates. We need to weed them out to avoid
1548 overrunning the end of the bblst_table. */
1550 update_idx = 0;
1551 bitmap_clear (visited);
1552 for (j = 0; j < el.nr_members; j++)
1554 block = el.first_member[j]->src;
1555 FOR_EACH_EDGE (e, ei, block->succs)
1557 if (!bitmap_bit_p (visited, e->dest->index))
1559 for (k = 0; k < el.nr_members; k++)
1560 if (e == el.first_member[k])
1561 break;
1563 if (k >= el.nr_members)
1565 bblst_table[bblst_last++] = e->dest;
1566 bitmap_set_bit (visited, e->dest->index);
1567 update_idx++;
1572 sp->update_bbs.nr_members = update_idx;
1574 /* Make sure we didn't overrun the end of bblst_table. */
1575 gcc_assert (bblst_last <= bblst_size);
1577 else
1579 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1581 sp->is_speculative = 0;
1582 sp->src_prob = 0;
1587 /* Free the computed target info. */
1588 static void
1589 free_trg_info (void)
1591 free (candidate_table);
1592 free (bblst_table);
1593 free (edgelst_table);
1596 /* Print candidates info, for debugging purposes. Callable from debugger. */
1598 DEBUG_FUNCTION void
1599 debug_candidate (int i)
1601 if (!candidate_table[i].is_valid)
1602 return;
1604 if (candidate_table[i].is_speculative)
1606 int j;
1607 fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1609 fprintf (sched_dump, "split path: ");
1610 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1612 int b = candidate_table[i].split_bbs.first_member[j]->index;
1614 fprintf (sched_dump, " %d ", b);
1616 fprintf (sched_dump, "\n");
1618 fprintf (sched_dump, "update path: ");
1619 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
1621 int b = candidate_table[i].update_bbs.first_member[j]->index;
1623 fprintf (sched_dump, " %d ", b);
1625 fprintf (sched_dump, "\n");
1627 else
1629 fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
1633 /* Print candidates info, for debugging purposes. Callable from debugger. */
1635 DEBUG_FUNCTION void
1636 debug_candidates (int trg)
1638 int i;
1640 fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
1641 BB_TO_BLOCK (trg), trg);
1642 for (i = trg + 1; i < current_nr_blocks; i++)
1643 debug_candidate (i);
1646 /* Functions for speculative scheduling. */
1648 static bitmap_head not_in_df;
1650 /* Return 0 if x is a set of a register alive in the beginning of one
1651 of the split-blocks of src, otherwise return 1. */
1653 static int
1654 check_live_1 (int src, rtx x)
1656 int i;
1657 int regno;
1658 rtx reg = SET_DEST (x);
1660 if (reg == 0)
1661 return 1;
1663 while (GET_CODE (reg) == SUBREG
1664 || GET_CODE (reg) == ZERO_EXTRACT
1665 || GET_CODE (reg) == STRICT_LOW_PART)
1666 reg = XEXP (reg, 0);
1668 if (GET_CODE (reg) == PARALLEL)
1670 int i;
1672 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1673 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1674 if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
1675 return 1;
1677 return 0;
1680 if (!REG_P (reg))
1681 return 1;
1683 regno = REGNO (reg);
1685 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1687 /* Global registers are assumed live. */
1688 return 0;
1690 else
1692 if (regno < FIRST_PSEUDO_REGISTER)
1694 /* Check for hard registers. */
1695 int j = REG_NREGS (reg);
1696 while (--j >= 0)
1698 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1700 basic_block b = candidate_table[src].split_bbs.first_member[i];
1701 int t = bitmap_bit_p (&not_in_df, b->index);
1703 /* We can have split blocks, that were recently generated.
1704 Such blocks are always outside current region. */
1705 gcc_assert (!t || (CONTAINING_RGN (b->index)
1706 != CONTAINING_RGN (BB_TO_BLOCK (src))));
1708 if (t || REGNO_REG_SET_P (df_get_live_in (b), regno + j))
1709 return 0;
1713 else
1715 /* Check for pseudo registers. */
1716 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1718 basic_block b = candidate_table[src].split_bbs.first_member[i];
1719 int t = bitmap_bit_p (&not_in_df, b->index);
1721 gcc_assert (!t || (CONTAINING_RGN (b->index)
1722 != CONTAINING_RGN (BB_TO_BLOCK (src))));
1724 if (t || REGNO_REG_SET_P (df_get_live_in (b), regno))
1725 return 0;
1730 return 1;
1733 /* If x is a set of a register R, mark that R is alive in the beginning
1734 of every update-block of src. */
1736 static void
1737 update_live_1 (int src, rtx x)
1739 int i;
1740 int regno;
1741 rtx reg = SET_DEST (x);
1743 if (reg == 0)
1744 return;
1746 while (GET_CODE (reg) == SUBREG
1747 || GET_CODE (reg) == ZERO_EXTRACT
1748 || GET_CODE (reg) == STRICT_LOW_PART)
1749 reg = XEXP (reg, 0);
1751 if (GET_CODE (reg) == PARALLEL)
1753 int i;
1755 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1756 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1757 update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
1759 return;
1762 if (!REG_P (reg))
1763 return;
1765 /* Global registers are always live, so the code below does not apply
1766 to them. */
1768 regno = REGNO (reg);
1770 if (! HARD_REGISTER_NUM_P (regno)
1771 || !global_regs[regno])
1773 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1775 basic_block b = candidate_table[src].update_bbs.first_member[i];
1776 bitmap_set_range (df_get_live_in (b), regno, REG_NREGS (reg));
1781 /* Return 1 if insn can be speculatively moved from block src to trg,
1782 otherwise return 0. Called before first insertion of insn to
1783 ready-list or before the scheduling. */
1785 static int
1786 check_live (rtx_insn *insn, int src)
1788 /* Find the registers set by instruction. */
1789 if (GET_CODE (PATTERN (insn)) == SET
1790 || GET_CODE (PATTERN (insn)) == CLOBBER)
1791 return check_live_1 (src, PATTERN (insn));
1792 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1794 int j;
1795 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1796 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1797 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1798 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
1799 return 0;
1801 return 1;
1804 return 1;
1807 /* Update the live registers info after insn was moved speculatively from
1808 block src to trg. */
1810 static void
1811 update_live (rtx_insn *insn, int src)
1813 /* Find the registers set by instruction. */
1814 if (GET_CODE (PATTERN (insn)) == SET
1815 || GET_CODE (PATTERN (insn)) == CLOBBER)
1816 update_live_1 (src, PATTERN (insn));
1817 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1819 int j;
1820 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1821 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1822 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1823 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
1827 /* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1828 #define IS_REACHABLE(bb_from, bb_to) \
1829 (bb_from == bb_to \
1830 || IS_RGN_ENTRY (bb_from) \
1831 || (bitmap_bit_p (ancestor_edges[bb_to], \
1832 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK_FOR_FN (cfun, \
1833 BB_TO_BLOCK (bb_from)))))))
1835 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1837 static void
1838 set_spec_fed (rtx load_insn)
1840 sd_iterator_def sd_it;
1841 dep_t dep;
1843 FOR_EACH_DEP (load_insn, SD_LIST_FORW, sd_it, dep)
1844 if (DEP_TYPE (dep) == REG_DEP_TRUE)
1845 FED_BY_SPEC_LOAD (DEP_CON (dep)) = 1;
1848 /* On the path from the insn to load_insn_bb, find a conditional
1849 branch depending on insn, that guards the speculative load. */
1851 static int
1852 find_conditional_protection (rtx_insn *insn, int load_insn_bb)
1854 sd_iterator_def sd_it;
1855 dep_t dep;
1857 /* Iterate through DEF-USE forward dependences. */
1858 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
1860 rtx_insn *next = DEP_CON (dep);
1862 if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
1863 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
1864 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
1865 && load_insn_bb != INSN_BB (next)
1866 && DEP_TYPE (dep) == REG_DEP_TRUE
1867 && (JUMP_P (next)
1868 || find_conditional_protection (next, load_insn_bb)))
1869 return 1;
1871 return 0;
1872 } /* find_conditional_protection */
1874 /* Returns 1 if the same insn1 that participates in the computation
1875 of load_insn's address is feeding a conditional branch that is
1876 guarding on load_insn. This is true if we find two DEF-USE
1877 chains:
1878 insn1 -> ... -> conditional-branch
1879 insn1 -> ... -> load_insn,
1880 and if a flow path exists:
1881 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1882 and if insn1 is on the path
1883 region-entry -> ... -> bb_trg -> ... load_insn.
1885 Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
1886 Locate the branch by following INSN_FORW_DEPS from insn1. */
1888 static int
1889 is_conditionally_protected (rtx load_insn, int bb_src, int bb_trg)
1891 sd_iterator_def sd_it;
1892 dep_t dep;
1894 FOR_EACH_DEP (load_insn, SD_LIST_BACK, sd_it, dep)
1896 rtx_insn *insn1 = DEP_PRO (dep);
1898 /* Must be a DEF-USE dependence upon non-branch. */
1899 if (DEP_TYPE (dep) != REG_DEP_TRUE
1900 || JUMP_P (insn1))
1901 continue;
1903 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1904 if (INSN_BB (insn1) == bb_src
1905 || (CONTAINING_RGN (BLOCK_NUM (insn1))
1906 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
1907 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
1908 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
1909 continue;
1911 /* Now search for the conditional-branch. */
1912 if (find_conditional_protection (insn1, bb_src))
1913 return 1;
1915 /* Recursive step: search another insn1, "above" current insn1. */
1916 return is_conditionally_protected (insn1, bb_src, bb_trg);
1919 /* The chain does not exist. */
1920 return 0;
1921 } /* is_conditionally_protected */
1923 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1924 load_insn can move speculatively from bb_src to bb_trg. All the
1925 following must hold:
1927 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1928 (2) load_insn and load1 have a def-use dependence upon
1929 the same insn 'insn1'.
1930 (3) either load2 is in bb_trg, or:
1931 - there's only one split-block, and
1932 - load1 is on the escape path, and
1934 From all these we can conclude that the two loads access memory
1935 addresses that differ at most by a constant, and hence if moving
1936 load_insn would cause an exception, it would have been caused by
1937 load2 anyhow. */
1939 static int
1940 is_pfree (rtx load_insn, int bb_src, int bb_trg)
1942 sd_iterator_def back_sd_it;
1943 dep_t back_dep;
1944 candidate *candp = candidate_table + bb_src;
1946 if (candp->split_bbs.nr_members != 1)
1947 /* Must have exactly one escape block. */
1948 return 0;
1950 FOR_EACH_DEP (load_insn, SD_LIST_BACK, back_sd_it, back_dep)
1952 rtx_insn *insn1 = DEP_PRO (back_dep);
1954 if (DEP_TYPE (back_dep) == REG_DEP_TRUE)
1955 /* Found a DEF-USE dependence (insn1, load_insn). */
1957 sd_iterator_def fore_sd_it;
1958 dep_t fore_dep;
1960 FOR_EACH_DEP (insn1, SD_LIST_FORW, fore_sd_it, fore_dep)
1962 rtx_insn *insn2 = DEP_CON (fore_dep);
1964 if (DEP_TYPE (fore_dep) == REG_DEP_TRUE)
1966 /* Found a DEF-USE dependence (insn1, insn2). */
1967 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
1968 /* insn2 not guaranteed to be a 1 base reg load. */
1969 continue;
1971 if (INSN_BB (insn2) == bb_trg)
1972 /* insn2 is the similar load, in the target block. */
1973 return 1;
1975 if (*(candp->split_bbs.first_member) == BLOCK_FOR_INSN (insn2))
1976 /* insn2 is a similar load, in a split-block. */
1977 return 1;
1983 /* Couldn't find a similar load. */
1984 return 0;
1985 } /* is_pfree */
1987 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1988 a load moved speculatively, or if load_insn is protected by
1989 a compare on load_insn's address). */
1991 static int
1992 is_prisky (rtx load_insn, int bb_src, int bb_trg)
1994 if (FED_BY_SPEC_LOAD (load_insn))
1995 return 1;
1997 if (sd_lists_empty_p (load_insn, SD_LIST_BACK))
1998 /* Dependence may 'hide' out of the region. */
1999 return 1;
2001 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2002 return 1;
2004 return 0;
2007 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2008 Return 1 if insn is exception-free (and the motion is valid)
2009 and 0 otherwise. */
2011 static int
2012 is_exception_free (rtx_insn *insn, int bb_src, int bb_trg)
2014 int insn_class = haifa_classify_insn (insn);
2016 /* Handle non-load insns. */
2017 switch (insn_class)
2019 case TRAP_FREE:
2020 return 1;
2021 case TRAP_RISKY:
2022 return 0;
2023 default:;
2026 /* Handle loads. */
2027 if (!flag_schedule_speculative_load)
2028 return 0;
2029 IS_LOAD_INSN (insn) = 1;
2030 switch (insn_class)
2032 case IFREE:
2033 return (1);
2034 case IRISKY:
2035 return 0;
2036 case PFREE_CANDIDATE:
2037 if (is_pfree (insn, bb_src, bb_trg))
2038 return 1;
2039 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2040 /* FALLTHRU */
2041 case PRISKY_CANDIDATE:
2042 if (!flag_schedule_speculative_load_dangerous
2043 || is_prisky (insn, bb_src, bb_trg))
2044 return 0;
2045 break;
2046 default:;
2049 return flag_schedule_speculative_load_dangerous;
2052 /* The number of insns from the current block scheduled so far. */
2053 static int sched_target_n_insns;
2054 /* The number of insns from the current block to be scheduled in total. */
2055 static int target_n_insns;
2056 /* The number of insns from the entire region scheduled so far. */
2057 static int sched_n_insns;
2059 /* Implementations of the sched_info functions for region scheduling. */
2060 static void init_ready_list (void);
2061 static int can_schedule_ready_p (rtx_insn *);
2062 static void begin_schedule_ready (rtx_insn *);
2063 static ds_t new_ready (rtx_insn *, ds_t);
2064 static int schedule_more_p (void);
2065 static const char *rgn_print_insn (const rtx_insn *, int);
2066 static int rgn_rank (rtx_insn *, rtx_insn *);
2067 static void compute_jump_reg_dependencies (rtx, regset);
2069 /* Functions for speculative scheduling. */
2070 static void rgn_add_remove_insn (rtx_insn *, int);
2071 static void rgn_add_block (basic_block, basic_block);
2072 static void rgn_fix_recovery_cfg (int, int, int);
2073 static basic_block advance_target_bb (basic_block, rtx_insn *);
2075 /* Return nonzero if there are more insns that should be scheduled. */
2077 static int
2078 schedule_more_p (void)
2080 return sched_target_n_insns < target_n_insns;
2083 /* Add all insns that are initially ready to the ready list READY. Called
2084 once before scheduling a set of insns. */
2086 static void
2087 init_ready_list (void)
2089 rtx_insn *prev_head = current_sched_info->prev_head;
2090 rtx_insn *next_tail = current_sched_info->next_tail;
2091 int bb_src;
2092 rtx_insn *insn;
2094 target_n_insns = 0;
2095 sched_target_n_insns = 0;
2096 sched_n_insns = 0;
2098 /* Print debugging information. */
2099 if (sched_verbose >= 5)
2100 debug_rgn_dependencies (target_bb);
2102 /* Prepare current target block info. */
2103 if (current_nr_blocks > 1)
2104 compute_trg_info (target_bb);
2106 /* Initialize ready list with all 'ready' insns in target block.
2107 Count number of insns in the target block being scheduled. */
2108 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
2110 gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
2111 TODO_SPEC (insn) = HARD_DEP;
2112 try_ready (insn);
2113 target_n_insns++;
2115 gcc_assert (!(TODO_SPEC (insn) & BEGIN_CONTROL));
2118 /* Add to ready list all 'ready' insns in valid source blocks.
2119 For speculative insns, check-live, exception-free, and
2120 issue-delay. */
2121 for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
2122 if (IS_VALID (bb_src))
2124 rtx_insn *src_head;
2125 rtx_insn *src_next_tail;
2126 rtx_insn *tail, *head;
2128 get_ebb_head_tail (EBB_FIRST_BB (bb_src), EBB_LAST_BB (bb_src),
2129 &head, &tail);
2130 src_next_tail = NEXT_INSN (tail);
2131 src_head = head;
2133 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
2134 if (INSN_P (insn))
2136 gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
2137 TODO_SPEC (insn) = HARD_DEP;
2138 try_ready (insn);
2143 /* Called after taking INSN from the ready list. Returns nonzero if this
2144 insn can be scheduled, nonzero if we should silently discard it. */
2146 static int
2147 can_schedule_ready_p (rtx_insn *insn)
2149 /* An interblock motion? */
2150 if (INSN_BB (insn) != target_bb && IS_SPECULATIVE_INSN (insn))
2152 /* Cannot schedule this insn unless all operands are live. */
2153 if (!check_live (insn, INSN_BB (insn)))
2154 return 0;
2156 /* Should not move expensive instructions speculatively. */
2157 if (GET_CODE (PATTERN (insn)) != CLOBBER
2158 && !targetm.sched.can_speculate_insn (insn))
2159 return 0;
2162 return 1;
2165 /* Updates counter and other information. Split from can_schedule_ready_p ()
2166 because when we schedule insn speculatively then insn passed to
2167 can_schedule_ready_p () differs from the one passed to
2168 begin_schedule_ready (). */
2169 static void
2170 begin_schedule_ready (rtx_insn *insn)
2172 /* An interblock motion? */
2173 if (INSN_BB (insn) != target_bb)
2175 if (IS_SPECULATIVE_INSN (insn))
2177 gcc_assert (check_live (insn, INSN_BB (insn)));
2179 update_live (insn, INSN_BB (insn));
2181 /* For speculative load, mark insns fed by it. */
2182 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
2183 set_spec_fed (insn);
2185 nr_spec++;
2187 nr_inter++;
2189 else
2191 /* In block motion. */
2192 sched_target_n_insns++;
2194 sched_n_insns++;
2197 /* Called after INSN has all its hard dependencies resolved and the speculation
2198 of type TS is enough to overcome them all.
2199 Return nonzero if it should be moved to the ready list or the queue, or zero
2200 if we should silently discard it. */
2201 static ds_t
2202 new_ready (rtx_insn *next, ds_t ts)
2204 if (INSN_BB (next) != target_bb)
2206 int not_ex_free = 0;
2208 /* For speculative insns, before inserting to ready/queue,
2209 check live, exception-free, and issue-delay. */
2210 if (!IS_VALID (INSN_BB (next))
2211 || CANT_MOVE (next)
2212 || (IS_SPECULATIVE_INSN (next)
2213 && ((recog_memoized (next) >= 0
2214 && min_insn_conflict_delay (curr_state, next, next)
2215 > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY))
2216 || IS_SPECULATION_CHECK_P (next)
2217 || !check_live (next, INSN_BB (next))
2218 || (not_ex_free = !is_exception_free (next, INSN_BB (next),
2219 target_bb)))))
2221 if (not_ex_free
2222 /* We are here because is_exception_free () == false.
2223 But we possibly can handle that with control speculation. */
2224 && sched_deps_info->generate_spec_deps
2225 && spec_info->mask & BEGIN_CONTROL)
2227 ds_t new_ds;
2229 /* Add control speculation to NEXT's dependency type. */
2230 new_ds = set_dep_weak (ts, BEGIN_CONTROL, MAX_DEP_WEAK);
2232 /* Check if NEXT can be speculated with new dependency type. */
2233 if (sched_insn_is_legitimate_for_speculation_p (next, new_ds))
2234 /* Here we got new control-speculative instruction. */
2235 ts = new_ds;
2236 else
2237 /* NEXT isn't ready yet. */
2238 ts = DEP_POSTPONED;
2240 else
2241 /* NEXT isn't ready yet. */
2242 ts = DEP_POSTPONED;
2246 return ts;
2249 /* Return a string that contains the insn uid and optionally anything else
2250 necessary to identify this insn in an output. It's valid to use a
2251 static buffer for this. The ALIGNED parameter should cause the string
2252 to be formatted so that multiple output lines will line up nicely. */
2254 static const char *
2255 rgn_print_insn (const rtx_insn *insn, int aligned)
2257 static char tmp[80];
2259 if (aligned)
2260 sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
2261 else
2263 if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
2264 sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
2265 else
2266 sprintf (tmp, "%d", INSN_UID (insn));
2268 return tmp;
2271 /* Compare priority of two insns. Return a positive number if the second
2272 insn is to be preferred for scheduling, and a negative one if the first
2273 is to be preferred. Zero if they are equally good. */
2275 static int
2276 rgn_rank (rtx_insn *insn1, rtx_insn *insn2)
2278 /* Some comparison make sense in interblock scheduling only. */
2279 if (INSN_BB (insn1) != INSN_BB (insn2))
2281 int spec_val, prob_val;
2283 /* Prefer an inblock motion on an interblock motion. */
2284 if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
2285 return 1;
2286 if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
2287 return -1;
2289 /* Prefer a useful motion on a speculative one. */
2290 spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
2291 if (spec_val)
2292 return spec_val;
2294 /* Prefer a more probable (speculative) insn. */
2295 prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
2296 if (prob_val)
2297 return prob_val;
2299 return 0;
2302 /* NEXT is an instruction that depends on INSN (a backward dependence);
2303 return nonzero if we should include this dependence in priority
2304 calculations. */
2307 contributes_to_priority (rtx_insn *next, rtx_insn *insn)
2309 /* NEXT and INSN reside in one ebb. */
2310 return BLOCK_TO_BB (BLOCK_NUM (next)) == BLOCK_TO_BB (BLOCK_NUM (insn));
2313 /* INSN is a JUMP_INSN. Store the set of registers that must be
2314 considered as used by this jump in USED. */
2316 static void
2317 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
2318 regset used ATTRIBUTE_UNUSED)
2320 /* Nothing to do here, since we postprocess jumps in
2321 add_branch_dependences. */
2324 /* This variable holds common_sched_info hooks and data relevant to
2325 the interblock scheduler. */
2326 static struct common_sched_info_def rgn_common_sched_info;
2329 /* This holds data for the dependence analysis relevant to
2330 the interblock scheduler. */
2331 static struct sched_deps_info_def rgn_sched_deps_info;
2333 /* This holds constant data used for initializing the above structure
2334 for the Haifa scheduler. */
2335 static const struct sched_deps_info_def rgn_const_sched_deps_info =
2337 compute_jump_reg_dependencies,
2338 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
2339 0, 0, 0
2342 /* Same as above, but for the selective scheduler. */
2343 static const struct sched_deps_info_def rgn_const_sel_sched_deps_info =
2345 compute_jump_reg_dependencies,
2346 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
2347 0, 0, 0
2350 /* Return true if scheduling INSN will trigger finish of scheduling
2351 current block. */
2352 static bool
2353 rgn_insn_finishes_block_p (rtx_insn *insn)
2355 if (INSN_BB (insn) == target_bb
2356 && sched_target_n_insns + 1 == target_n_insns)
2357 /* INSN is the last not-scheduled instruction in the current block. */
2358 return true;
2360 return false;
2363 /* Used in schedule_insns to initialize current_sched_info for scheduling
2364 regions (or single basic blocks). */
2366 static const struct haifa_sched_info rgn_const_sched_info =
2368 init_ready_list,
2369 can_schedule_ready_p,
2370 schedule_more_p,
2371 new_ready,
2372 rgn_rank,
2373 rgn_print_insn,
2374 contributes_to_priority,
2375 rgn_insn_finishes_block_p,
2377 NULL, NULL,
2378 NULL, NULL,
2379 0, 0,
2381 rgn_add_remove_insn,
2382 begin_schedule_ready,
2383 NULL,
2384 advance_target_bb,
2385 NULL, NULL,
2386 SCHED_RGN
2389 /* This variable holds the data and hooks needed to the Haifa scheduler backend
2390 for the interblock scheduler frontend. */
2391 static struct haifa_sched_info rgn_sched_info;
2393 /* Returns maximum priority that an insn was assigned to. */
2396 get_rgn_sched_max_insns_priority (void)
2398 return rgn_sched_info.sched_max_insns_priority;
2401 /* Determine if PAT sets a TARGET_CLASS_LIKELY_SPILLED_P register. */
2403 static bool
2404 sets_likely_spilled (rtx pat)
2406 bool ret = false;
2407 note_stores (pat, sets_likely_spilled_1, &ret);
2408 return ret;
2411 static void
2412 sets_likely_spilled_1 (rtx x, const_rtx pat, void *data)
2414 bool *ret = (bool *) data;
2416 if (GET_CODE (pat) == SET
2417 && REG_P (x)
2418 && HARD_REGISTER_P (x)
2419 && targetm.class_likely_spilled_p (REGNO_REG_CLASS (REGNO (x))))
2420 *ret = true;
2423 /* A bitmap to note insns that participate in any dependency. Used in
2424 add_branch_dependences. */
2425 static sbitmap insn_referenced;
2427 /* Add dependences so that branches are scheduled to run last in their
2428 block. */
2429 static void
2430 add_branch_dependences (rtx_insn *head, rtx_insn *tail)
2432 rtx_insn *insn, *last;
2434 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2435 that can throw exceptions, force them to remain in order at the end of
2436 the block by adding dependencies and giving the last a high priority.
2437 There may be notes present, and prev_head may also be a note.
2439 Branches must obviously remain at the end. Calls should remain at the
2440 end since moving them results in worse register allocation. Uses remain
2441 at the end to ensure proper register allocation.
2443 cc0 setters remain at the end because they can't be moved away from
2444 their cc0 user.
2446 Predecessors of SCHED_GROUP_P instructions at the end remain at the end.
2448 COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
2450 Insns setting TARGET_CLASS_LIKELY_SPILLED_P registers (usually return
2451 values) are not moved before reload because we can wind up with register
2452 allocation failures. */
2454 while (tail != head && DEBUG_INSN_P (tail))
2455 tail = PREV_INSN (tail);
2457 insn = tail;
2458 last = 0;
2459 while (CALL_P (insn)
2460 || JUMP_P (insn) || JUMP_TABLE_DATA_P (insn)
2461 || (NONJUMP_INSN_P (insn)
2462 && (GET_CODE (PATTERN (insn)) == USE
2463 || GET_CODE (PATTERN (insn)) == CLOBBER
2464 || can_throw_internal (insn)
2465 || (HAVE_cc0 && sets_cc0_p (PATTERN (insn)))
2466 || (!reload_completed
2467 && sets_likely_spilled (PATTERN (insn)))))
2468 || NOTE_P (insn)
2469 || (last != 0 && SCHED_GROUP_P (last)))
2471 if (!NOTE_P (insn))
2473 if (last != 0
2474 && sd_find_dep_between (insn, last, false) == NULL)
2476 if (! sched_insns_conditions_mutex_p (last, insn))
2477 add_dependence (last, insn, REG_DEP_ANTI);
2478 bitmap_set_bit (insn_referenced, INSN_LUID (insn));
2481 CANT_MOVE (insn) = 1;
2483 last = insn;
2486 /* Don't overrun the bounds of the basic block. */
2487 if (insn == head)
2488 break;
2491 insn = PREV_INSN (insn);
2492 while (insn != head && DEBUG_INSN_P (insn));
2495 /* Make sure these insns are scheduled last in their block. */
2496 insn = last;
2497 if (insn != 0)
2498 while (insn != head)
2500 insn = prev_nonnote_insn (insn);
2502 if (bitmap_bit_p (insn_referenced, INSN_LUID (insn))
2503 || DEBUG_INSN_P (insn))
2504 continue;
2506 if (! sched_insns_conditions_mutex_p (last, insn))
2507 add_dependence (last, insn, REG_DEP_ANTI);
2510 if (!targetm.have_conditional_execution ())
2511 return;
2513 /* Finally, if the block ends in a jump, and we are doing intra-block
2514 scheduling, make sure that the branch depends on any COND_EXEC insns
2515 inside the block to avoid moving the COND_EXECs past the branch insn.
2517 We only have to do this after reload, because (1) before reload there
2518 are no COND_EXEC insns, and (2) the region scheduler is an intra-block
2519 scheduler after reload.
2521 FIXME: We could in some cases move COND_EXEC insns past the branch if
2522 this scheduler would be a little smarter. Consider this code:
2524 T = [addr]
2525 C ? addr += 4
2526 !C ? X += 12
2527 C ? T += 1
2528 C ? jump foo
2530 On a target with a one cycle stall on a memory access the optimal
2531 sequence would be:
2533 T = [addr]
2534 C ? addr += 4
2535 C ? T += 1
2536 C ? jump foo
2537 !C ? X += 12
2539 We don't want to put the 'X += 12' before the branch because it just
2540 wastes a cycle of execution time when the branch is taken.
2542 Note that in the example "!C" will always be true. That is another
2543 possible improvement for handling COND_EXECs in this scheduler: it
2544 could remove always-true predicates. */
2546 if (!reload_completed || ! (JUMP_P (tail) || JUMP_TABLE_DATA_P (tail)))
2547 return;
2549 insn = tail;
2550 while (insn != head)
2552 insn = PREV_INSN (insn);
2554 /* Note that we want to add this dependency even when
2555 sched_insns_conditions_mutex_p returns true. The whole point
2556 is that we _want_ this dependency, even if these insns really
2557 are independent. */
2558 if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC)
2559 add_dependence (tail, insn, REG_DEP_ANTI);
2563 /* Data structures for the computation of data dependences in a regions. We
2564 keep one `deps' structure for every basic block. Before analyzing the
2565 data dependences for a bb, its variables are initialized as a function of
2566 the variables of its predecessors. When the analysis for a bb completes,
2567 we save the contents to the corresponding bb_deps[bb] variable. */
2569 static struct deps_desc *bb_deps;
2571 static void
2572 concat_insn_mem_list (rtx_insn_list *copy_insns,
2573 rtx_expr_list *copy_mems,
2574 rtx_insn_list **old_insns_p,
2575 rtx_expr_list **old_mems_p)
2577 rtx_insn_list *new_insns = *old_insns_p;
2578 rtx_expr_list *new_mems = *old_mems_p;
2580 while (copy_insns)
2582 new_insns = alloc_INSN_LIST (copy_insns->insn (), new_insns);
2583 new_mems = alloc_EXPR_LIST (VOIDmode, copy_mems->element (), new_mems);
2584 copy_insns = copy_insns->next ();
2585 copy_mems = copy_mems->next ();
2588 *old_insns_p = new_insns;
2589 *old_mems_p = new_mems;
2592 /* Join PRED_DEPS to the SUCC_DEPS. */
2593 void
2594 deps_join (struct deps_desc *succ_deps, struct deps_desc *pred_deps)
2596 unsigned reg;
2597 reg_set_iterator rsi;
2599 /* The reg_last lists are inherited by successor. */
2600 EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi)
2602 struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
2603 struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
2605 succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
2606 succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
2607 succ_rl->implicit_sets
2608 = concat_INSN_LIST (pred_rl->implicit_sets, succ_rl->implicit_sets);
2609 succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
2610 succ_rl->clobbers);
2611 succ_rl->uses_length += pred_rl->uses_length;
2612 succ_rl->clobbers_length += pred_rl->clobbers_length;
2614 IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
2616 /* Mem read/write lists are inherited by successor. */
2617 concat_insn_mem_list (pred_deps->pending_read_insns,
2618 pred_deps->pending_read_mems,
2619 &succ_deps->pending_read_insns,
2620 &succ_deps->pending_read_mems);
2621 concat_insn_mem_list (pred_deps->pending_write_insns,
2622 pred_deps->pending_write_mems,
2623 &succ_deps->pending_write_insns,
2624 &succ_deps->pending_write_mems);
2626 succ_deps->pending_jump_insns
2627 = concat_INSN_LIST (pred_deps->pending_jump_insns,
2628 succ_deps->pending_jump_insns);
2629 succ_deps->last_pending_memory_flush
2630 = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
2631 succ_deps->last_pending_memory_flush);
2633 succ_deps->pending_read_list_length += pred_deps->pending_read_list_length;
2634 succ_deps->pending_write_list_length += pred_deps->pending_write_list_length;
2635 succ_deps->pending_flush_length += pred_deps->pending_flush_length;
2637 /* last_function_call is inherited by successor. */
2638 succ_deps->last_function_call
2639 = concat_INSN_LIST (pred_deps->last_function_call,
2640 succ_deps->last_function_call);
2642 /* last_function_call_may_noreturn is inherited by successor. */
2643 succ_deps->last_function_call_may_noreturn
2644 = concat_INSN_LIST (pred_deps->last_function_call_may_noreturn,
2645 succ_deps->last_function_call_may_noreturn);
2647 /* sched_before_next_call is inherited by successor. */
2648 succ_deps->sched_before_next_call
2649 = concat_INSN_LIST (pred_deps->sched_before_next_call,
2650 succ_deps->sched_before_next_call);
2653 /* After computing the dependencies for block BB, propagate the dependencies
2654 found in TMP_DEPS to the successors of the block. */
2655 static void
2656 propagate_deps (int bb, struct deps_desc *pred_deps)
2658 basic_block block = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb));
2659 edge_iterator ei;
2660 edge e;
2662 /* bb's structures are inherited by its successors. */
2663 FOR_EACH_EDGE (e, ei, block->succs)
2665 /* Only bbs "below" bb, in the same region, are interesting. */
2666 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2667 || CONTAINING_RGN (block->index) != CONTAINING_RGN (e->dest->index)
2668 || BLOCK_TO_BB (e->dest->index) <= bb)
2669 continue;
2671 deps_join (bb_deps + BLOCK_TO_BB (e->dest->index), pred_deps);
2674 /* These lists should point to the right place, for correct
2675 freeing later. */
2676 bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
2677 bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
2678 bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
2679 bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
2680 bb_deps[bb].pending_jump_insns = pred_deps->pending_jump_insns;
2682 /* Can't allow these to be freed twice. */
2683 pred_deps->pending_read_insns = 0;
2684 pred_deps->pending_read_mems = 0;
2685 pred_deps->pending_write_insns = 0;
2686 pred_deps->pending_write_mems = 0;
2687 pred_deps->pending_jump_insns = 0;
2690 /* Compute dependences inside bb. In a multiple blocks region:
2691 (1) a bb is analyzed after its predecessors, and (2) the lists in
2692 effect at the end of bb (after analyzing for bb) are inherited by
2693 bb's successors.
2695 Specifically for reg-reg data dependences, the block insns are
2696 scanned by sched_analyze () top-to-bottom. Three lists are
2697 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2698 reg_last[].implicit_sets for implicit hard register DEFs, and
2699 reg_last[].uses for register USEs.
2701 When analysis is completed for bb, we update for its successors:
2702 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2703 ; - IMPLICIT_DEFS[succ] = Union (IMPLICIT_DEFS [succ], IMPLICIT_DEFS [bb])
2704 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2706 The mechanism for computing mem-mem data dependence is very
2707 similar, and the result is interblock dependences in the region. */
2709 static void
2710 compute_block_dependences (int bb)
2712 rtx_insn *head, *tail;
2713 struct deps_desc tmp_deps;
2715 tmp_deps = bb_deps[bb];
2717 /* Do the analysis for this block. */
2718 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2719 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2721 sched_analyze (&tmp_deps, head, tail);
2723 /* Selective scheduling handles control dependencies by itself. */
2724 if (!sel_sched_p ())
2725 add_branch_dependences (head, tail);
2727 if (current_nr_blocks > 1)
2728 propagate_deps (bb, &tmp_deps);
2730 /* Free up the INSN_LISTs. */
2731 free_deps (&tmp_deps);
2733 if (targetm.sched.dependencies_evaluation_hook)
2734 targetm.sched.dependencies_evaluation_hook (head, tail);
2737 /* Free dependencies of instructions inside BB. */
2738 static void
2739 free_block_dependencies (int bb)
2741 rtx_insn *head;
2742 rtx_insn *tail;
2744 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2746 if (no_real_insns_p (head, tail))
2747 return;
2749 sched_free_deps (head, tail, true);
2752 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2753 them to the unused_*_list variables, so that they can be reused. */
2755 static void
2756 free_pending_lists (void)
2758 int bb;
2760 for (bb = 0; bb < current_nr_blocks; bb++)
2762 free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
2763 free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
2764 free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
2765 free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
2766 free_INSN_LIST_list (&bb_deps[bb].pending_jump_insns);
2770 /* Print dependences for debugging starting from FROM_BB.
2771 Callable from debugger. */
2772 /* Print dependences for debugging starting from FROM_BB.
2773 Callable from debugger. */
2774 DEBUG_FUNCTION void
2775 debug_rgn_dependencies (int from_bb)
2777 int bb;
2779 fprintf (sched_dump,
2780 ";; --------------- forward dependences: ------------ \n");
2782 for (bb = from_bb; bb < current_nr_blocks; bb++)
2784 rtx_insn *head, *tail;
2786 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2787 fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
2788 BB_TO_BLOCK (bb), bb);
2790 debug_dependencies (head, tail);
2794 /* Print dependencies information for instructions between HEAD and TAIL.
2795 ??? This function would probably fit best in haifa-sched.c. */
2796 void debug_dependencies (rtx_insn *head, rtx_insn *tail)
2798 rtx_insn *insn;
2799 rtx_insn *next_tail = NEXT_INSN (tail);
2801 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2802 "insn", "code", "bb", "dep", "prio", "cost",
2803 "reservation");
2804 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2805 "----", "----", "--", "---", "----", "----",
2806 "-----------");
2808 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2810 if (! INSN_P (insn))
2812 int n;
2813 fprintf (sched_dump, ";; %6d ", INSN_UID (insn));
2814 if (NOTE_P (insn))
2816 n = NOTE_KIND (insn);
2817 fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
2819 else
2820 fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
2821 continue;
2824 fprintf (sched_dump,
2825 ";; %s%5d%6d%6d%6d%6d%6d ",
2826 (SCHED_GROUP_P (insn) ? "+" : " "),
2827 INSN_UID (insn),
2828 INSN_CODE (insn),
2829 BLOCK_NUM (insn),
2830 sched_emulate_haifa_p ? -1 : sd_lists_size (insn, SD_LIST_BACK),
2831 (sel_sched_p () ? (sched_emulate_haifa_p ? -1
2832 : INSN_PRIORITY (insn))
2833 : INSN_PRIORITY (insn)),
2834 (sel_sched_p () ? (sched_emulate_haifa_p ? -1
2835 : insn_cost (insn))
2836 : insn_cost (insn)));
2838 if (recog_memoized (insn) < 0)
2839 fprintf (sched_dump, "nothing");
2840 else
2841 print_reservation (sched_dump, insn);
2843 fprintf (sched_dump, "\t: ");
2845 sd_iterator_def sd_it;
2846 dep_t dep;
2848 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
2849 fprintf (sched_dump, "%d%s%s ", INSN_UID (DEP_CON (dep)),
2850 DEP_NONREG (dep) ? "n" : "",
2851 DEP_MULTIPLE (dep) ? "m" : "");
2853 fprintf (sched_dump, "\n");
2856 fprintf (sched_dump, "\n");
2859 /* Dump dependency graph for the current region to a file using dot syntax. */
2861 void
2862 dump_rgn_dependencies_dot (FILE *file)
2864 rtx_insn *head, *tail, *con, *pro;
2865 sd_iterator_def sd_it;
2866 dep_t dep;
2867 int bb;
2868 pretty_printer pp;
2870 pp.buffer->stream = file;
2871 pp_printf (&pp, "digraph SchedDG {\n");
2873 for (bb = 0; bb < current_nr_blocks; ++bb)
2875 /* Begin subgraph (basic block). */
2876 pp_printf (&pp, "subgraph cluster_block_%d {\n", bb);
2877 pp_printf (&pp, "\t" "color=blue;" "\n");
2878 pp_printf (&pp, "\t" "style=bold;" "\n");
2879 pp_printf (&pp, "\t" "label=\"BB #%d\";\n", BB_TO_BLOCK (bb));
2881 /* Setup head and tail (no support for EBBs). */
2882 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2883 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2884 tail = NEXT_INSN (tail);
2886 /* Dump all insns. */
2887 for (con = head; con != tail; con = NEXT_INSN (con))
2889 if (!INSN_P (con))
2890 continue;
2892 /* Pretty print the insn. */
2893 pp_printf (&pp, "\t%d [label=\"{", INSN_UID (con));
2894 pp_write_text_to_stream (&pp);
2895 print_insn (&pp, con, /*verbose=*/false);
2896 pp_write_text_as_dot_label_to_stream (&pp, /*for_record=*/true);
2897 pp_write_text_to_stream (&pp);
2899 /* Dump instruction attributes. */
2900 pp_printf (&pp, "|{ uid:%d | luid:%d | prio:%d }}\",shape=record]\n",
2901 INSN_UID (con), INSN_LUID (con), INSN_PRIORITY (con));
2903 /* Dump all deps. */
2904 FOR_EACH_DEP (con, SD_LIST_BACK, sd_it, dep)
2906 int weight = 0;
2907 const char *color;
2908 pro = DEP_PRO (dep);
2910 switch (DEP_TYPE (dep))
2912 case REG_DEP_TRUE:
2913 color = "black";
2914 weight = 1;
2915 break;
2916 case REG_DEP_OUTPUT:
2917 case REG_DEP_ANTI:
2918 color = "orange";
2919 break;
2920 case REG_DEP_CONTROL:
2921 color = "blue";
2922 break;
2923 default:
2924 gcc_unreachable ();
2927 pp_printf (&pp, "\t%d -> %d [color=%s",
2928 INSN_UID (pro), INSN_UID (con), color);
2929 if (int cost = dep_cost (dep))
2930 pp_printf (&pp, ",label=%d", cost);
2931 pp_printf (&pp, ",weight=%d", weight);
2932 pp_printf (&pp, "];\n");
2935 pp_printf (&pp, "}\n");
2938 pp_printf (&pp, "}\n");
2939 pp_flush (&pp);
2942 /* Dump dependency graph for the current region to a file using dot syntax. */
2944 DEBUG_FUNCTION void
2945 dump_rgn_dependencies_dot (const char *fname)
2947 FILE *fp;
2949 fp = fopen (fname, "w");
2950 if (!fp)
2952 perror ("fopen");
2953 return;
2956 dump_rgn_dependencies_dot (fp);
2957 fclose (fp);
2961 /* Returns true if all the basic blocks of the current region have
2962 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
2963 bool
2964 sched_is_disabled_for_current_region_p (void)
2966 int bb;
2968 for (bb = 0; bb < current_nr_blocks; bb++)
2969 if (!(BASIC_BLOCK_FOR_FN (cfun,
2970 BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE))
2971 return false;
2973 return true;
2976 /* Free all region dependencies saved in INSN_BACK_DEPS and
2977 INSN_RESOLVED_BACK_DEPS. The Haifa scheduler does this on the fly
2978 when scheduling, so this function is supposed to be called from
2979 the selective scheduling only. */
2980 void
2981 free_rgn_deps (void)
2983 int bb;
2985 for (bb = 0; bb < current_nr_blocks; bb++)
2987 rtx_insn *head, *tail;
2989 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2990 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2992 sched_free_deps (head, tail, false);
2996 static int rgn_n_insns;
2998 /* Compute insn priority for a current region. */
2999 void
3000 compute_priorities (void)
3002 int bb;
3004 current_sched_info->sched_max_insns_priority = 0;
3005 for (bb = 0; bb < current_nr_blocks; bb++)
3007 rtx_insn *head, *tail;
3009 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
3010 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
3012 if (no_real_insns_p (head, tail))
3013 continue;
3015 rgn_n_insns += set_priorities (head, tail);
3017 current_sched_info->sched_max_insns_priority++;
3020 /* (Re-)initialize the arrays of DFA states at the end of each basic block.
3022 SAVED_LAST_BASIC_BLOCK is the previous length of the arrays. It must be
3023 zero for the first call to this function, to allocate the arrays for the
3024 first time.
3026 This function is called once during initialization of the scheduler, and
3027 called again to resize the arrays if new basic blocks have been created,
3028 for example for speculation recovery code. */
3030 static void
3031 realloc_bb_state_array (int saved_last_basic_block)
3033 char *old_bb_state_array = bb_state_array;
3034 size_t lbb = (size_t) last_basic_block_for_fn (cfun);
3035 size_t slbb = (size_t) saved_last_basic_block;
3037 /* Nothing to do if nothing changed since the last time this was called. */
3038 if (saved_last_basic_block == last_basic_block_for_fn (cfun))
3039 return;
3041 /* The selective scheduler doesn't use the state arrays. */
3042 if (sel_sched_p ())
3044 gcc_assert (bb_state_array == NULL && bb_state == NULL);
3045 return;
3048 gcc_checking_assert (saved_last_basic_block == 0
3049 || (bb_state_array != NULL && bb_state != NULL));
3051 bb_state_array = XRESIZEVEC (char, bb_state_array, lbb * dfa_state_size);
3052 bb_state = XRESIZEVEC (state_t, bb_state, lbb);
3054 /* If BB_STATE_ARRAY has moved, fixup all the state pointers array.
3055 Otherwise only fixup the newly allocated ones. For the state
3056 array itself, only initialize the new entries. */
3057 bool bb_state_array_moved = (bb_state_array != old_bb_state_array);
3058 for (size_t i = bb_state_array_moved ? 0 : slbb; i < lbb; i++)
3059 bb_state[i] = (state_t) (bb_state_array + i * dfa_state_size);
3060 for (size_t i = slbb; i < lbb; i++)
3061 state_reset (bb_state[i]);
3064 /* Free the arrays of DFA states at the end of each basic block. */
3066 static void
3067 free_bb_state_array (void)
3069 free (bb_state_array);
3070 free (bb_state);
3071 bb_state_array = NULL;
3072 bb_state = NULL;
3075 /* Schedule a region. A region is either an inner loop, a loop-free
3076 subroutine, or a single basic block. Each bb in the region is
3077 scheduled after its flow predecessors. */
3079 static void
3080 schedule_region (int rgn)
3082 int bb;
3083 int sched_rgn_n_insns = 0;
3085 rgn_n_insns = 0;
3087 /* Do not support register pressure sensitive scheduling for the new regions
3088 as we don't update the liveness info for them. */
3089 if (sched_pressure != SCHED_PRESSURE_NONE
3090 && rgn >= nr_regions_initial)
3092 free_global_sched_pressure_data ();
3093 sched_pressure = SCHED_PRESSURE_NONE;
3096 rgn_setup_region (rgn);
3098 /* Don't schedule region that is marked by
3099 NOTE_DISABLE_SCHED_OF_BLOCK. */
3100 if (sched_is_disabled_for_current_region_p ())
3101 return;
3103 sched_rgn_compute_dependencies (rgn);
3105 sched_rgn_local_init (rgn);
3107 /* Set priorities. */
3108 compute_priorities ();
3110 sched_extend_ready_list (rgn_n_insns);
3112 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
3114 sched_init_region_reg_pressure_info ();
3115 for (bb = 0; bb < current_nr_blocks; bb++)
3117 basic_block first_bb, last_bb;
3118 rtx_insn *head, *tail;
3120 first_bb = EBB_FIRST_BB (bb);
3121 last_bb = EBB_LAST_BB (bb);
3123 get_ebb_head_tail (first_bb, last_bb, &head, &tail);
3125 if (no_real_insns_p (head, tail))
3127 gcc_assert (first_bb == last_bb);
3128 continue;
3130 sched_setup_bb_reg_pressure_info (first_bb, PREV_INSN (head));
3134 /* Now we can schedule all blocks. */
3135 for (bb = 0; bb < current_nr_blocks; bb++)
3137 basic_block first_bb, last_bb, curr_bb;
3138 rtx_insn *head, *tail;
3140 first_bb = EBB_FIRST_BB (bb);
3141 last_bb = EBB_LAST_BB (bb);
3143 get_ebb_head_tail (first_bb, last_bb, &head, &tail);
3145 if (no_real_insns_p (head, tail))
3147 gcc_assert (first_bb == last_bb);
3148 continue;
3151 current_sched_info->prev_head = PREV_INSN (head);
3152 current_sched_info->next_tail = NEXT_INSN (tail);
3154 remove_notes (head, tail);
3156 unlink_bb_notes (first_bb, last_bb);
3158 target_bb = bb;
3160 gcc_assert (flag_schedule_interblock || current_nr_blocks == 1);
3161 current_sched_info->queue_must_finish_empty = current_nr_blocks == 1;
3163 curr_bb = first_bb;
3164 if (dbg_cnt (sched_block))
3166 edge f;
3167 int saved_last_basic_block = last_basic_block_for_fn (cfun);
3169 schedule_block (&curr_bb, bb_state[first_bb->index]);
3170 gcc_assert (EBB_FIRST_BB (bb) == first_bb);
3171 sched_rgn_n_insns += sched_n_insns;
3172 realloc_bb_state_array (saved_last_basic_block);
3173 f = find_fallthru_edge (last_bb->succs);
3174 if (f && f->probability * 100 / REG_BR_PROB_BASE >=
3175 PARAM_VALUE (PARAM_SCHED_STATE_EDGE_PROB_CUTOFF))
3177 memcpy (bb_state[f->dest->index], curr_state,
3178 dfa_state_size);
3179 if (sched_verbose >= 5)
3180 fprintf (sched_dump, "saving state for edge %d->%d\n",
3181 f->src->index, f->dest->index);
3184 else
3186 sched_rgn_n_insns += rgn_n_insns;
3189 /* Clean up. */
3190 if (current_nr_blocks > 1)
3191 free_trg_info ();
3194 /* Sanity check: verify that all region insns were scheduled. */
3195 gcc_assert (sched_rgn_n_insns == rgn_n_insns);
3197 sched_finish_ready_list ();
3199 /* Done with this region. */
3200 sched_rgn_local_finish ();
3202 /* Free dependencies. */
3203 for (bb = 0; bb < current_nr_blocks; ++bb)
3204 free_block_dependencies (bb);
3206 gcc_assert (haifa_recovery_bb_ever_added_p
3207 || deps_pools_are_empty_p ());
3210 /* Initialize data structures for region scheduling. */
3212 void
3213 sched_rgn_init (bool single_blocks_p)
3215 min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE)
3216 / 100);
3218 nr_inter = 0;
3219 nr_spec = 0;
3221 extend_regions ();
3223 CONTAINING_RGN (ENTRY_BLOCK) = -1;
3224 CONTAINING_RGN (EXIT_BLOCK) = -1;
3226 realloc_bb_state_array (0);
3228 /* Compute regions for scheduling. */
3229 if (single_blocks_p
3230 || n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS + 1
3231 || !flag_schedule_interblock
3232 || is_cfg_nonregular ())
3234 find_single_block_region (sel_sched_p ());
3236 else
3238 /* Compute the dominators and post dominators. */
3239 if (!sel_sched_p ())
3240 calculate_dominance_info (CDI_DOMINATORS);
3242 /* Find regions. */
3243 find_rgns ();
3245 if (sched_verbose >= 3)
3246 debug_regions ();
3248 /* For now. This will move as more and more of haifa is converted
3249 to using the cfg code. */
3250 if (!sel_sched_p ())
3251 free_dominance_info (CDI_DOMINATORS);
3254 gcc_assert (0 < nr_regions && nr_regions <= n_basic_blocks_for_fn (cfun));
3256 RGN_BLOCKS (nr_regions) = (RGN_BLOCKS (nr_regions - 1) +
3257 RGN_NR_BLOCKS (nr_regions - 1));
3258 nr_regions_initial = nr_regions;
3261 /* Free data structures for region scheduling. */
3262 void
3263 sched_rgn_finish (void)
3265 free_bb_state_array ();
3267 /* Reposition the prologue and epilogue notes in case we moved the
3268 prologue/epilogue insns. */
3269 if (reload_completed)
3270 reposition_prologue_and_epilogue_notes ();
3272 if (sched_verbose)
3274 if (reload_completed == 0
3275 && flag_schedule_interblock)
3277 fprintf (sched_dump,
3278 "\n;; Procedure interblock/speculative motions == %d/%d \n",
3279 nr_inter, nr_spec);
3281 else
3282 gcc_assert (nr_inter <= 0);
3283 fprintf (sched_dump, "\n\n");
3286 nr_regions = 0;
3288 free (rgn_table);
3289 rgn_table = NULL;
3291 free (rgn_bb_table);
3292 rgn_bb_table = NULL;
3294 free (block_to_bb);
3295 block_to_bb = NULL;
3297 free (containing_rgn);
3298 containing_rgn = NULL;
3300 free (ebb_head);
3301 ebb_head = NULL;
3304 /* Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
3305 point to the region RGN. */
3306 void
3307 rgn_setup_region (int rgn)
3309 int bb;
3311 /* Set variables for the current region. */
3312 current_nr_blocks = RGN_NR_BLOCKS (rgn);
3313 current_blocks = RGN_BLOCKS (rgn);
3315 /* EBB_HEAD is a region-scope structure. But we realloc it for
3316 each region to save time/memory/something else.
3317 See comments in add_block1, for what reasons we allocate +1 element. */
3318 ebb_head = XRESIZEVEC (int, ebb_head, current_nr_blocks + 1);
3319 for (bb = 0; bb <= current_nr_blocks; bb++)
3320 ebb_head[bb] = current_blocks + bb;
3323 /* Compute instruction dependencies in region RGN. */
3324 void
3325 sched_rgn_compute_dependencies (int rgn)
3327 if (!RGN_DONT_CALC_DEPS (rgn))
3329 int bb;
3331 if (sel_sched_p ())
3332 sched_emulate_haifa_p = 1;
3334 init_deps_global ();
3336 /* Initializations for region data dependence analysis. */
3337 bb_deps = XNEWVEC (struct deps_desc, current_nr_blocks);
3338 for (bb = 0; bb < current_nr_blocks; bb++)
3339 init_deps (bb_deps + bb, false);
3341 /* Initialize bitmap used in add_branch_dependences. */
3342 insn_referenced = sbitmap_alloc (sched_max_luid);
3343 bitmap_clear (insn_referenced);
3345 /* Compute backward dependencies. */
3346 for (bb = 0; bb < current_nr_blocks; bb++)
3347 compute_block_dependences (bb);
3349 sbitmap_free (insn_referenced);
3350 free_pending_lists ();
3351 finish_deps_global ();
3352 free (bb_deps);
3354 /* We don't want to recalculate this twice. */
3355 RGN_DONT_CALC_DEPS (rgn) = 1;
3357 if (sel_sched_p ())
3358 sched_emulate_haifa_p = 0;
3360 else
3361 /* (This is a recovery block. It is always a single block region.)
3362 OR (We use selective scheduling.) */
3363 gcc_assert (current_nr_blocks == 1 || sel_sched_p ());
3366 /* Init region data structures. Returns true if this region should
3367 not be scheduled. */
3368 void
3369 sched_rgn_local_init (int rgn)
3371 int bb;
3373 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
3374 if (current_nr_blocks > 1)
3376 basic_block block;
3377 edge e;
3378 edge_iterator ei;
3380 prob = XNEWVEC (int, current_nr_blocks);
3382 dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
3383 bitmap_vector_clear (dom, current_nr_blocks);
3385 /* Use ->aux to implement EDGE_TO_BIT mapping. */
3386 rgn_nr_edges = 0;
3387 FOR_EACH_BB_FN (block, cfun)
3389 if (CONTAINING_RGN (block->index) != rgn)
3390 continue;
3391 FOR_EACH_EDGE (e, ei, block->succs)
3392 SET_EDGE_TO_BIT (e, rgn_nr_edges++);
3395 rgn_edges = XNEWVEC (edge, rgn_nr_edges);
3396 rgn_nr_edges = 0;
3397 FOR_EACH_BB_FN (block, cfun)
3399 if (CONTAINING_RGN (block->index) != rgn)
3400 continue;
3401 FOR_EACH_EDGE (e, ei, block->succs)
3402 rgn_edges[rgn_nr_edges++] = e;
3405 /* Split edges. */
3406 pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
3407 bitmap_vector_clear (pot_split, current_nr_blocks);
3408 ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
3409 bitmap_vector_clear (ancestor_edges, current_nr_blocks);
3411 /* Compute probabilities, dominators, split_edges. */
3412 for (bb = 0; bb < current_nr_blocks; bb++)
3413 compute_dom_prob_ps (bb);
3415 /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
3416 /* We don't need them anymore. But we want to avoid duplication of
3417 aux fields in the newly created edges. */
3418 FOR_EACH_BB_FN (block, cfun)
3420 if (CONTAINING_RGN (block->index) != rgn)
3421 continue;
3422 FOR_EACH_EDGE (e, ei, block->succs)
3423 e->aux = NULL;
3428 /* Free data computed for the finished region. */
3429 void
3430 sched_rgn_local_free (void)
3432 free (prob);
3433 sbitmap_vector_free (dom);
3434 sbitmap_vector_free (pot_split);
3435 sbitmap_vector_free (ancestor_edges);
3436 free (rgn_edges);
3439 /* Free data computed for the finished region. */
3440 void
3441 sched_rgn_local_finish (void)
3443 if (current_nr_blocks > 1 && !sel_sched_p ())
3445 sched_rgn_local_free ();
3449 /* Setup scheduler infos. */
3450 void
3451 rgn_setup_common_sched_info (void)
3453 memcpy (&rgn_common_sched_info, &haifa_common_sched_info,
3454 sizeof (rgn_common_sched_info));
3456 rgn_common_sched_info.fix_recovery_cfg = rgn_fix_recovery_cfg;
3457 rgn_common_sched_info.add_block = rgn_add_block;
3458 rgn_common_sched_info.estimate_number_of_insns
3459 = rgn_estimate_number_of_insns;
3460 rgn_common_sched_info.sched_pass_id = SCHED_RGN_PASS;
3462 common_sched_info = &rgn_common_sched_info;
3465 /* Setup all *_sched_info structures (for the Haifa frontend
3466 and for the dependence analysis) in the interblock scheduler. */
3467 void
3468 rgn_setup_sched_infos (void)
3470 if (!sel_sched_p ())
3471 memcpy (&rgn_sched_deps_info, &rgn_const_sched_deps_info,
3472 sizeof (rgn_sched_deps_info));
3473 else
3474 memcpy (&rgn_sched_deps_info, &rgn_const_sel_sched_deps_info,
3475 sizeof (rgn_sched_deps_info));
3477 sched_deps_info = &rgn_sched_deps_info;
3479 memcpy (&rgn_sched_info, &rgn_const_sched_info, sizeof (rgn_sched_info));
3480 current_sched_info = &rgn_sched_info;
3483 /* The one entry point in this file. */
3484 void
3485 schedule_insns (void)
3487 int rgn;
3489 /* Taking care of this degenerate case makes the rest of
3490 this code simpler. */
3491 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
3492 return;
3494 rgn_setup_common_sched_info ();
3495 rgn_setup_sched_infos ();
3497 haifa_sched_init ();
3498 sched_rgn_init (reload_completed);
3500 bitmap_initialize (&not_in_df, 0);
3501 bitmap_clear (&not_in_df);
3503 /* Schedule every region in the subroutine. */
3504 for (rgn = 0; rgn < nr_regions; rgn++)
3505 if (dbg_cnt (sched_region))
3506 schedule_region (rgn);
3508 /* Clean up. */
3509 sched_rgn_finish ();
3510 bitmap_clear (&not_in_df);
3512 haifa_sched_finish ();
3515 /* INSN has been added to/removed from current region. */
3516 static void
3517 rgn_add_remove_insn (rtx_insn *insn, int remove_p)
3519 if (!remove_p)
3520 rgn_n_insns++;
3521 else
3522 rgn_n_insns--;
3524 if (INSN_BB (insn) == target_bb)
3526 if (!remove_p)
3527 target_n_insns++;
3528 else
3529 target_n_insns--;
3533 /* Extend internal data structures. */
3534 void
3535 extend_regions (void)
3537 rgn_table = XRESIZEVEC (region, rgn_table, n_basic_blocks_for_fn (cfun));
3538 rgn_bb_table = XRESIZEVEC (int, rgn_bb_table,
3539 n_basic_blocks_for_fn (cfun));
3540 block_to_bb = XRESIZEVEC (int, block_to_bb,
3541 last_basic_block_for_fn (cfun));
3542 containing_rgn = XRESIZEVEC (int, containing_rgn,
3543 last_basic_block_for_fn (cfun));
3546 void
3547 rgn_make_new_region_out_of_new_block (basic_block bb)
3549 int i;
3551 i = RGN_BLOCKS (nr_regions);
3552 /* I - first free position in rgn_bb_table. */
3554 rgn_bb_table[i] = bb->index;
3555 RGN_NR_BLOCKS (nr_regions) = 1;
3556 RGN_HAS_REAL_EBB (nr_regions) = 0;
3557 RGN_DONT_CALC_DEPS (nr_regions) = 0;
3558 CONTAINING_RGN (bb->index) = nr_regions;
3559 BLOCK_TO_BB (bb->index) = 0;
3561 nr_regions++;
3563 RGN_BLOCKS (nr_regions) = i + 1;
3566 /* BB was added to ebb after AFTER. */
3567 static void
3568 rgn_add_block (basic_block bb, basic_block after)
3570 extend_regions ();
3571 bitmap_set_bit (&not_in_df, bb->index);
3573 if (after == 0 || after == EXIT_BLOCK_PTR_FOR_FN (cfun))
3575 rgn_make_new_region_out_of_new_block (bb);
3576 RGN_DONT_CALC_DEPS (nr_regions - 1) = (after
3577 == EXIT_BLOCK_PTR_FOR_FN (cfun));
3579 else
3581 int i, pos;
3583 /* We need to fix rgn_table, block_to_bb, containing_rgn
3584 and ebb_head. */
3586 BLOCK_TO_BB (bb->index) = BLOCK_TO_BB (after->index);
3588 /* We extend ebb_head to one more position to
3589 easily find the last position of the last ebb in
3590 the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
3591 is _always_ valid for access. */
3593 i = BLOCK_TO_BB (after->index) + 1;
3594 pos = ebb_head[i] - 1;
3595 /* Now POS is the index of the last block in the region. */
3597 /* Find index of basic block AFTER. */
3598 for (; rgn_bb_table[pos] != after->index; pos--)
3601 pos++;
3602 gcc_assert (pos > ebb_head[i - 1]);
3604 /* i - ebb right after "AFTER". */
3605 /* ebb_head[i] - VALID. */
3607 /* Source position: ebb_head[i]
3608 Destination position: ebb_head[i] + 1
3609 Last position:
3610 RGN_BLOCKS (nr_regions) - 1
3611 Number of elements to copy: (last_position) - (source_position) + 1
3614 memmove (rgn_bb_table + pos + 1,
3615 rgn_bb_table + pos,
3616 ((RGN_BLOCKS (nr_regions) - 1) - (pos) + 1)
3617 * sizeof (*rgn_bb_table));
3619 rgn_bb_table[pos] = bb->index;
3621 for (; i <= current_nr_blocks; i++)
3622 ebb_head [i]++;
3624 i = CONTAINING_RGN (after->index);
3625 CONTAINING_RGN (bb->index) = i;
3627 RGN_HAS_REAL_EBB (i) = 1;
3629 for (++i; i <= nr_regions; i++)
3630 RGN_BLOCKS (i)++;
3634 /* Fix internal data after interblock movement of jump instruction.
3635 For parameter meaning please refer to
3636 sched-int.h: struct sched_info: fix_recovery_cfg. */
3637 static void
3638 rgn_fix_recovery_cfg (int bbi, int check_bbi, int check_bb_nexti)
3640 int old_pos, new_pos, i;
3642 BLOCK_TO_BB (check_bb_nexti) = BLOCK_TO_BB (bbi);
3644 for (old_pos = ebb_head[BLOCK_TO_BB (check_bbi) + 1] - 1;
3645 rgn_bb_table[old_pos] != check_bb_nexti;
3646 old_pos--)
3648 gcc_assert (old_pos > ebb_head[BLOCK_TO_BB (check_bbi)]);
3650 for (new_pos = ebb_head[BLOCK_TO_BB (bbi) + 1] - 1;
3651 rgn_bb_table[new_pos] != bbi;
3652 new_pos--)
3654 new_pos++;
3655 gcc_assert (new_pos > ebb_head[BLOCK_TO_BB (bbi)]);
3657 gcc_assert (new_pos < old_pos);
3659 memmove (rgn_bb_table + new_pos + 1,
3660 rgn_bb_table + new_pos,
3661 (old_pos - new_pos) * sizeof (*rgn_bb_table));
3663 rgn_bb_table[new_pos] = check_bb_nexti;
3665 for (i = BLOCK_TO_BB (bbi) + 1; i <= BLOCK_TO_BB (check_bbi); i++)
3666 ebb_head[i]++;
3669 /* Return next block in ebb chain. For parameter meaning please refer to
3670 sched-int.h: struct sched_info: advance_target_bb. */
3671 static basic_block
3672 advance_target_bb (basic_block bb, rtx_insn *insn)
3674 if (insn)
3675 return 0;
3677 gcc_assert (BLOCK_TO_BB (bb->index) == target_bb
3678 && BLOCK_TO_BB (bb->next_bb->index) == target_bb);
3679 return bb->next_bb;
3682 #endif
3684 /* Run instruction scheduler. */
3685 static unsigned int
3686 rest_of_handle_live_range_shrinkage (void)
3688 #ifdef INSN_SCHEDULING
3689 int saved;
3691 initialize_live_range_shrinkage ();
3692 saved = flag_schedule_interblock;
3693 flag_schedule_interblock = false;
3694 schedule_insns ();
3695 flag_schedule_interblock = saved;
3696 finish_live_range_shrinkage ();
3697 #endif
3698 return 0;
3701 /* Run instruction scheduler. */
3702 static unsigned int
3703 rest_of_handle_sched (void)
3705 #ifdef INSN_SCHEDULING
3706 if (flag_selective_scheduling
3707 && ! maybe_skip_selective_scheduling ())
3708 run_selective_scheduling ();
3709 else
3710 schedule_insns ();
3711 #endif
3712 return 0;
3715 /* Run second scheduling pass after reload. */
3716 static unsigned int
3717 rest_of_handle_sched2 (void)
3719 #ifdef INSN_SCHEDULING
3720 if (flag_selective_scheduling2
3721 && ! maybe_skip_selective_scheduling ())
3722 run_selective_scheduling ();
3723 else
3725 /* Do control and data sched analysis again,
3726 and write some more of the results to dump file. */
3727 if (flag_sched2_use_superblocks)
3728 schedule_ebbs ();
3729 else
3730 schedule_insns ();
3732 #endif
3733 return 0;
3736 static unsigned int
3737 rest_of_handle_sched_fusion (void)
3739 #ifdef INSN_SCHEDULING
3740 sched_fusion = true;
3741 schedule_insns ();
3742 sched_fusion = false;
3743 #endif
3744 return 0;
3747 namespace {
3749 const pass_data pass_data_live_range_shrinkage =
3751 RTL_PASS, /* type */
3752 "lr_shrinkage", /* name */
3753 OPTGROUP_NONE, /* optinfo_flags */
3754 TV_LIVE_RANGE_SHRINKAGE, /* tv_id */
3755 0, /* properties_required */
3756 0, /* properties_provided */
3757 0, /* properties_destroyed */
3758 0, /* todo_flags_start */
3759 TODO_df_finish, /* todo_flags_finish */
3762 class pass_live_range_shrinkage : public rtl_opt_pass
3764 public:
3765 pass_live_range_shrinkage(gcc::context *ctxt)
3766 : rtl_opt_pass(pass_data_live_range_shrinkage, ctxt)
3769 /* opt_pass methods: */
3770 virtual bool gate (function *)
3772 #ifdef INSN_SCHEDULING
3773 return flag_live_range_shrinkage;
3774 #else
3775 return 0;
3776 #endif
3779 virtual unsigned int execute (function *)
3781 return rest_of_handle_live_range_shrinkage ();
3784 }; // class pass_live_range_shrinkage
3786 } // anon namespace
3788 rtl_opt_pass *
3789 make_pass_live_range_shrinkage (gcc::context *ctxt)
3791 return new pass_live_range_shrinkage (ctxt);
3794 namespace {
3796 const pass_data pass_data_sched =
3798 RTL_PASS, /* type */
3799 "sched1", /* name */
3800 OPTGROUP_NONE, /* optinfo_flags */
3801 TV_SCHED, /* tv_id */
3802 0, /* properties_required */
3803 0, /* properties_provided */
3804 0, /* properties_destroyed */
3805 0, /* todo_flags_start */
3806 TODO_df_finish, /* todo_flags_finish */
3809 class pass_sched : public rtl_opt_pass
3811 public:
3812 pass_sched (gcc::context *ctxt)
3813 : rtl_opt_pass (pass_data_sched, ctxt)
3816 /* opt_pass methods: */
3817 virtual bool gate (function *);
3818 virtual unsigned int execute (function *) { return rest_of_handle_sched (); }
3820 }; // class pass_sched
3822 bool
3823 pass_sched::gate (function *)
3825 #ifdef INSN_SCHEDULING
3826 return optimize > 0 && flag_schedule_insns && dbg_cnt (sched_func);
3827 #else
3828 return 0;
3829 #endif
3832 } // anon namespace
3834 rtl_opt_pass *
3835 make_pass_sched (gcc::context *ctxt)
3837 return new pass_sched (ctxt);
3840 namespace {
3842 const pass_data pass_data_sched2 =
3844 RTL_PASS, /* type */
3845 "sched2", /* name */
3846 OPTGROUP_NONE, /* optinfo_flags */
3847 TV_SCHED2, /* tv_id */
3848 0, /* properties_required */
3849 0, /* properties_provided */
3850 0, /* properties_destroyed */
3851 0, /* todo_flags_start */
3852 TODO_df_finish, /* todo_flags_finish */
3855 class pass_sched2 : public rtl_opt_pass
3857 public:
3858 pass_sched2 (gcc::context *ctxt)
3859 : rtl_opt_pass (pass_data_sched2, ctxt)
3862 /* opt_pass methods: */
3863 virtual bool gate (function *);
3864 virtual unsigned int execute (function *)
3866 return rest_of_handle_sched2 ();
3869 }; // class pass_sched2
3871 bool
3872 pass_sched2::gate (function *)
3874 #ifdef INSN_SCHEDULING
3875 return optimize > 0 && flag_schedule_insns_after_reload
3876 && !targetm.delay_sched2 && dbg_cnt (sched2_func);
3877 #else
3878 return 0;
3879 #endif
3882 } // anon namespace
3884 rtl_opt_pass *
3885 make_pass_sched2 (gcc::context *ctxt)
3887 return new pass_sched2 (ctxt);
3890 namespace {
3892 const pass_data pass_data_sched_fusion =
3894 RTL_PASS, /* type */
3895 "sched_fusion", /* name */
3896 OPTGROUP_NONE, /* optinfo_flags */
3897 TV_SCHED_FUSION, /* tv_id */
3898 0, /* properties_required */
3899 0, /* properties_provided */
3900 0, /* properties_destroyed */
3901 0, /* todo_flags_start */
3902 TODO_df_finish, /* todo_flags_finish */
3905 class pass_sched_fusion : public rtl_opt_pass
3907 public:
3908 pass_sched_fusion (gcc::context *ctxt)
3909 : rtl_opt_pass (pass_data_sched_fusion, ctxt)
3912 /* opt_pass methods: */
3913 virtual bool gate (function *);
3914 virtual unsigned int execute (function *)
3916 return rest_of_handle_sched_fusion ();
3919 }; // class pass_sched2
3921 bool
3922 pass_sched_fusion::gate (function *)
3924 #ifdef INSN_SCHEDULING
3925 /* Scheduling fusion relies on peephole2 to do real fusion work,
3926 so only enable it if peephole2 is in effect. */
3927 return (optimize > 0 && flag_peephole2
3928 && flag_schedule_fusion && targetm.sched.fusion_priority != NULL);
3929 #else
3930 return 0;
3931 #endif
3934 } // anon namespace
3936 rtl_opt_pass *
3937 make_pass_sched_fusion (gcc::context *ctxt)
3939 return new pass_sched_fusion (ctxt);