PR middle-end/66867
[official-gcc.git] / gcc / sched-rgn.c
blobfa662ffb319ba91e06d56fd0380ff38561f4fd5f
1 /* Instruction scheduling pass.
2 Copyright (C) 1992-2016 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 "tm_p.h"
54 #include "insn-config.h"
55 #include "emit-rtl.h"
56 #include "recog.h"
57 #include "profile.h"
58 #include "insn-attr.h"
59 #include "except.h"
60 #include "params.h"
61 #include "cfganal.h"
62 #include "sched-int.h"
63 #include "sel-sched.h"
64 #include "tree-pass.h"
65 #include "dbgcnt.h"
66 #include "pretty-print.h"
67 #include "print-rtl.h"
69 #ifdef INSN_SCHEDULING
71 /* Some accessor macros for h_i_d members only used within this file. */
72 #define FED_BY_SPEC_LOAD(INSN) (HID (INSN)->fed_by_spec_load)
73 #define IS_LOAD_INSN(INSN) (HID (insn)->is_load_insn)
75 /* nr_inter/spec counts interblock/speculative motion for the function. */
76 static int nr_inter, nr_spec;
78 static int is_cfg_nonregular (void);
80 /* Number of regions in the procedure. */
81 int nr_regions = 0;
83 /* Same as above before adding any new regions. */
84 static int nr_regions_initial = 0;
86 /* Table of region descriptions. */
87 region *rgn_table = NULL;
89 /* Array of lists of regions' blocks. */
90 int *rgn_bb_table = NULL;
92 /* Topological order of blocks in the region (if b2 is reachable from
93 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
94 always referred to by either block or b, while its topological
95 order name (in the region) is referred to by bb. */
96 int *block_to_bb = NULL;
98 /* The number of the region containing a block. */
99 int *containing_rgn = NULL;
101 /* ebb_head [i] - is index in rgn_bb_table of the head basic block of i'th ebb.
102 Currently we can get a ebb only through splitting of currently
103 scheduling block, therefore, we don't need ebb_head array for every region,
104 hence, its sufficient to hold it for current one only. */
105 int *ebb_head = NULL;
107 /* The minimum probability of reaching a source block so that it will be
108 considered for speculative scheduling. */
109 static int min_spec_prob;
111 static void find_single_block_region (bool);
112 static void find_rgns (void);
113 static bool too_large (int, int *, int *);
115 /* Blocks of the current region being scheduled. */
116 int current_nr_blocks;
117 int current_blocks;
119 /* A speculative motion requires checking live information on the path
120 from 'source' to 'target'. The split blocks are those to be checked.
121 After a speculative motion, live information should be modified in
122 the 'update' blocks.
124 Lists of split and update blocks for each candidate of the current
125 target are in array bblst_table. */
126 static basic_block *bblst_table;
127 static int bblst_size, bblst_last;
129 /* Arrays that hold the DFA state at the end of a basic block, to re-use
130 as the initial state at the start of successor blocks. The BB_STATE
131 array holds the actual DFA state, and BB_STATE_ARRAY[I] is a pointer
132 into BB_STATE for basic block I. FIXME: This should be a vec. */
133 static char *bb_state_array = NULL;
134 static state_t *bb_state = NULL;
136 /* Target info declarations.
138 The block currently being scheduled is referred to as the "target" block,
139 while other blocks in the region from which insns can be moved to the
140 target are called "source" blocks. The candidate structure holds info
141 about such sources: are they valid? Speculative? Etc. */
142 struct bblst
144 basic_block *first_member;
145 int nr_members;
148 struct candidate
150 char is_valid;
151 char is_speculative;
152 int src_prob;
153 bblst split_bbs;
154 bblst update_bbs;
157 static candidate *candidate_table;
158 #define IS_VALID(src) (candidate_table[src].is_valid)
159 #define IS_SPECULATIVE(src) (candidate_table[src].is_speculative)
160 #define IS_SPECULATIVE_INSN(INSN) \
161 (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
162 #define SRC_PROB(src) ( candidate_table[src].src_prob )
164 /* The bb being currently scheduled. */
165 int target_bb;
167 /* List of edges. */
168 struct edgelst
170 edge *first_member;
171 int nr_members;
174 static edge *edgelst_table;
175 static int edgelst_last;
177 static void extract_edgelst (sbitmap, edgelst *);
179 /* Target info functions. */
180 static void split_edges (int, int, edgelst *);
181 static void compute_trg_info (int);
182 void debug_candidate (int);
183 void debug_candidates (int);
185 /* Dominators array: dom[i] contains the sbitmap of dominators of
186 bb i in the region. */
187 static sbitmap *dom;
189 /* bb 0 is the only region entry. */
190 #define IS_RGN_ENTRY(bb) (!bb)
192 /* Is bb_src dominated by bb_trg. */
193 #define IS_DOMINATED(bb_src, bb_trg) \
194 ( bitmap_bit_p (dom[bb_src], bb_trg) )
196 /* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
197 the probability of bb i relative to the region entry. */
198 static int *prob;
200 /* Bit-set of edges, where bit i stands for edge i. */
201 typedef sbitmap edgeset;
203 /* Number of edges in the region. */
204 static int rgn_nr_edges;
206 /* Array of size rgn_nr_edges. */
207 static edge *rgn_edges;
209 /* Mapping from each edge in the graph to its number in the rgn. */
210 #define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
211 #define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
213 /* The split edges of a source bb is different for each target
214 bb. In order to compute this efficiently, the 'potential-split edges'
215 are computed for each bb prior to scheduling a region. This is actually
216 the split edges of each bb relative to the region entry.
218 pot_split[bb] is the set of potential split edges of bb. */
219 static edgeset *pot_split;
221 /* For every bb, a set of its ancestor edges. */
222 static edgeset *ancestor_edges;
224 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
226 /* Speculative scheduling functions. */
227 static int check_live_1 (int, rtx);
228 static void update_live_1 (int, rtx);
229 static int is_pfree (rtx, int, int);
230 static int find_conditional_protection (rtx_insn *, int);
231 static int is_conditionally_protected (rtx, int, int);
232 static int is_prisky (rtx, int, int);
233 static int is_exception_free (rtx_insn *, int, int);
235 static bool sets_likely_spilled (rtx);
236 static void sets_likely_spilled_1 (rtx, const_rtx, void *);
237 static void add_branch_dependences (rtx_insn *, rtx_insn *);
238 static void compute_block_dependences (int);
240 static void schedule_region (int);
241 static void concat_insn_mem_list (rtx_insn_list *, rtx_expr_list *,
242 rtx_insn_list **, rtx_expr_list **);
243 static void propagate_deps (int, struct deps_desc *);
244 static void free_pending_lists (void);
246 /* Functions for construction of the control flow graph. */
248 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
250 We decide not to build the control flow graph if there is possibly more
251 than one entry to the function, if computed branches exist, if we
252 have nonlocal gotos, or if we have an unreachable loop. */
254 static int
255 is_cfg_nonregular (void)
257 basic_block b;
258 rtx_insn *insn;
260 /* If we have a label that could be the target of a nonlocal goto, then
261 the cfg is not well structured. */
262 if (nonlocal_goto_handler_labels)
263 return 1;
265 /* If we have any forced labels, then the cfg is not well structured. */
266 if (forced_labels)
267 return 1;
269 /* If we have exception handlers, then we consider the cfg not well
270 structured. ?!? We should be able to handle this now that we
271 compute an accurate cfg for EH. */
272 if (current_function_has_exception_handlers ())
273 return 1;
275 /* If we have insns which refer to labels as non-jumped-to operands,
276 then we consider the cfg not well structured. */
277 FOR_EACH_BB_FN (b, cfun)
278 FOR_BB_INSNS (b, insn)
280 rtx note, set, dest;
281 rtx_insn *next;
283 /* If this function has a computed jump, then we consider the cfg
284 not well structured. */
285 if (JUMP_P (insn) && computed_jump_p (insn))
286 return 1;
288 if (!INSN_P (insn))
289 continue;
291 note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX);
292 if (note == NULL_RTX)
293 continue;
295 /* For that label not to be seen as a referred-to label, this
296 must be a single-set which is feeding a jump *only*. This
297 could be a conditional jump with the label split off for
298 machine-specific reasons or a casesi/tablejump. */
299 next = next_nonnote_insn (insn);
300 if (next == NULL_RTX
301 || !JUMP_P (next)
302 || (JUMP_LABEL (next) != XEXP (note, 0)
303 && find_reg_note (next, REG_LABEL_TARGET,
304 XEXP (note, 0)) == NULL_RTX)
305 || BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (next))
306 return 1;
308 set = single_set (insn);
309 if (set == NULL_RTX)
310 return 1;
312 dest = SET_DEST (set);
313 if (!REG_P (dest) || !dead_or_set_p (next, dest))
314 return 1;
317 /* Unreachable loops with more than one basic block are detected
318 during the DFS traversal in find_rgns.
320 Unreachable loops with a single block are detected here. This
321 test is redundant with the one in find_rgns, but it's much
322 cheaper to go ahead and catch the trivial case here. */
323 FOR_EACH_BB_FN (b, cfun)
325 if (EDGE_COUNT (b->preds) == 0
326 || (single_pred_p (b)
327 && single_pred (b) == b))
328 return 1;
331 /* All the tests passed. Consider the cfg well structured. */
332 return 0;
335 /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */
337 static void
338 extract_edgelst (sbitmap set, edgelst *el)
340 unsigned int i = 0;
341 sbitmap_iterator sbi;
343 /* edgelst table space is reused in each call to extract_edgelst. */
344 edgelst_last = 0;
346 el->first_member = &edgelst_table[edgelst_last];
347 el->nr_members = 0;
349 /* Iterate over each word in the bitset. */
350 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, sbi)
352 edgelst_table[edgelst_last++] = rgn_edges[i];
353 el->nr_members++;
357 /* Functions for the construction of regions. */
359 /* Print the regions, for debugging purposes. Callable from debugger. */
361 DEBUG_FUNCTION void
362 debug_regions (void)
364 int rgn, bb;
366 fprintf (sched_dump, "\n;; ------------ REGIONS ----------\n\n");
367 for (rgn = 0; rgn < nr_regions; rgn++)
369 fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
370 rgn_table[rgn].rgn_nr_blocks);
371 fprintf (sched_dump, ";;\tbb/block: ");
373 /* We don't have ebb_head initialized yet, so we can't use
374 BB_TO_BLOCK (). */
375 current_blocks = RGN_BLOCKS (rgn);
377 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
378 fprintf (sched_dump, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
380 fprintf (sched_dump, "\n\n");
384 /* Print the region's basic blocks. */
386 DEBUG_FUNCTION void
387 debug_region (int rgn)
389 int bb;
391 fprintf (stderr, "\n;; ------------ REGION %d ----------\n\n", rgn);
392 fprintf (stderr, ";;\trgn %d nr_blocks %d:\n", rgn,
393 rgn_table[rgn].rgn_nr_blocks);
394 fprintf (stderr, ";;\tbb/block: ");
396 /* We don't have ebb_head initialized yet, so we can't use
397 BB_TO_BLOCK (). */
398 current_blocks = RGN_BLOCKS (rgn);
400 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
401 fprintf (stderr, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
403 fprintf (stderr, "\n\n");
405 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
407 dump_bb (stderr,
408 BASIC_BLOCK_FOR_FN (cfun, rgn_bb_table[current_blocks + bb]),
409 0, TDF_SLIM | TDF_BLOCKS);
410 fprintf (stderr, "\n");
413 fprintf (stderr, "\n");
417 /* True when a bb with index BB_INDEX contained in region RGN. */
418 static bool
419 bb_in_region_p (int bb_index, int rgn)
421 int i;
423 for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
424 if (rgn_bb_table[current_blocks + i] == bb_index)
425 return true;
427 return false;
430 /* Dump region RGN to file F using dot syntax. */
431 void
432 dump_region_dot (FILE *f, int rgn)
434 int i;
436 fprintf (f, "digraph Region_%d {\n", rgn);
438 /* We don't have ebb_head initialized yet, so we can't use
439 BB_TO_BLOCK (). */
440 current_blocks = RGN_BLOCKS (rgn);
442 for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
444 edge e;
445 edge_iterator ei;
446 int src_bb_num = rgn_bb_table[current_blocks + i];
447 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, src_bb_num);
449 FOR_EACH_EDGE (e, ei, bb->succs)
450 if (bb_in_region_p (e->dest->index, rgn))
451 fprintf (f, "\t%d -> %d\n", src_bb_num, e->dest->index);
453 fprintf (f, "}\n");
456 /* The same, but first open a file specified by FNAME. */
457 void
458 dump_region_dot_file (const char *fname, int rgn)
460 FILE *f = fopen (fname, "wt");
461 dump_region_dot (f, rgn);
462 fclose (f);
465 /* Build a single block region for each basic block in the function.
466 This allows for using the same code for interblock and basic block
467 scheduling. */
469 static void
470 find_single_block_region (bool ebbs_p)
472 basic_block bb, ebb_start;
473 int i = 0;
475 nr_regions = 0;
477 if (ebbs_p) {
478 int probability_cutoff;
479 if (profile_info && flag_branch_probabilities)
480 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
481 else
482 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
483 probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
485 FOR_EACH_BB_FN (ebb_start, cfun)
487 RGN_NR_BLOCKS (nr_regions) = 0;
488 RGN_BLOCKS (nr_regions) = i;
489 RGN_DONT_CALC_DEPS (nr_regions) = 0;
490 RGN_HAS_REAL_EBB (nr_regions) = 0;
492 for (bb = ebb_start; ; bb = bb->next_bb)
494 edge e;
496 rgn_bb_table[i] = bb->index;
497 RGN_NR_BLOCKS (nr_regions)++;
498 CONTAINING_RGN (bb->index) = nr_regions;
499 BLOCK_TO_BB (bb->index) = i - RGN_BLOCKS (nr_regions);
500 i++;
502 if (bb->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
503 || LABEL_P (BB_HEAD (bb->next_bb)))
504 break;
506 e = find_fallthru_edge (bb->succs);
507 if (! e)
508 break;
509 if (e->probability <= probability_cutoff)
510 break;
513 ebb_start = bb;
514 nr_regions++;
517 else
518 FOR_EACH_BB_FN (bb, cfun)
520 rgn_bb_table[nr_regions] = bb->index;
521 RGN_NR_BLOCKS (nr_regions) = 1;
522 RGN_BLOCKS (nr_regions) = nr_regions;
523 RGN_DONT_CALC_DEPS (nr_regions) = 0;
524 RGN_HAS_REAL_EBB (nr_regions) = 0;
526 CONTAINING_RGN (bb->index) = nr_regions;
527 BLOCK_TO_BB (bb->index) = 0;
528 nr_regions++;
532 /* Estimate number of the insns in the BB. */
533 static int
534 rgn_estimate_number_of_insns (basic_block bb)
536 int count;
538 count = INSN_LUID (BB_END (bb)) - INSN_LUID (BB_HEAD (bb));
540 if (MAY_HAVE_DEBUG_INSNS)
542 rtx_insn *insn;
544 FOR_BB_INSNS (bb, insn)
545 if (DEBUG_INSN_P (insn))
546 count--;
549 return count;
552 /* Update number of blocks and the estimate for number of insns
553 in the region. Return true if the region is "too large" for interblock
554 scheduling (compile time considerations). */
556 static bool
557 too_large (int block, int *num_bbs, int *num_insns)
559 (*num_bbs)++;
560 (*num_insns) += (common_sched_info->estimate_number_of_insns
561 (BASIC_BLOCK_FOR_FN (cfun, block)));
563 return ((*num_bbs > PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS))
564 || (*num_insns > PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS)));
567 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
568 is still an inner loop. Put in max_hdr[blk] the header of the most inner
569 loop containing blk. */
570 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
572 if (max_hdr[blk] == -1) \
573 max_hdr[blk] = hdr; \
574 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
575 bitmap_clear_bit (inner, hdr); \
576 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
578 bitmap_clear_bit (inner,max_hdr[blk]); \
579 max_hdr[blk] = hdr; \
583 /* Find regions for interblock scheduling.
585 A region for scheduling can be:
587 * A loop-free procedure, or
589 * A reducible inner loop, or
591 * A basic block not contained in any other region.
593 ?!? In theory we could build other regions based on extended basic
594 blocks or reverse extended basic blocks. Is it worth the trouble?
596 Loop blocks that form a region are put into the region's block list
597 in topological order.
599 This procedure stores its results into the following global (ick) variables
601 * rgn_nr
602 * rgn_table
603 * rgn_bb_table
604 * block_to_bb
605 * containing region
607 We use dominator relationships to avoid making regions out of non-reducible
608 loops.
610 This procedure needs to be converted to work on pred/succ lists instead
611 of edge tables. That would simplify it somewhat. */
613 static void
614 haifa_find_rgns (void)
616 int *max_hdr, *dfs_nr, *degree;
617 char no_loops = 1;
618 int node, child, loop_head, i, head, tail;
619 int count = 0, sp, idx = 0;
620 edge_iterator current_edge;
621 edge_iterator *stack;
622 int num_bbs, num_insns, unreachable;
623 int too_large_failure;
624 basic_block bb;
626 /* Note if a block is a natural loop header. */
627 sbitmap header;
629 /* Note if a block is a natural inner loop header. */
630 sbitmap inner;
632 /* Note if a block is in the block queue. */
633 sbitmap in_queue;
635 /* Note if a block is in the block queue. */
636 sbitmap in_stack;
638 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
639 and a mapping from block to its loop header (if the block is contained
640 in a loop, else -1).
642 Store results in HEADER, INNER, and MAX_HDR respectively, these will
643 be used as inputs to the second traversal.
645 STACK, SP and DFS_NR are only used during the first traversal. */
647 /* Allocate and initialize variables for the first traversal. */
648 max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
649 dfs_nr = XCNEWVEC (int, last_basic_block_for_fn (cfun));
650 stack = XNEWVEC (edge_iterator, n_edges_for_fn (cfun));
652 inner = sbitmap_alloc (last_basic_block_for_fn (cfun));
653 bitmap_ones (inner);
655 header = sbitmap_alloc (last_basic_block_for_fn (cfun));
656 bitmap_clear (header);
658 in_queue = sbitmap_alloc (last_basic_block_for_fn (cfun));
659 bitmap_clear (in_queue);
661 in_stack = sbitmap_alloc (last_basic_block_for_fn (cfun));
662 bitmap_clear (in_stack);
664 for (i = 0; i < last_basic_block_for_fn (cfun); i++)
665 max_hdr[i] = -1;
667 #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
668 #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
670 /* DFS traversal to find inner loops in the cfg. */
672 current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))->succs);
673 sp = -1;
675 while (1)
677 if (EDGE_PASSED (current_edge))
679 /* We have reached a leaf node or a node that was already
680 processed. Pop edges off the stack until we find
681 an edge that has not yet been processed. */
682 while (sp >= 0 && EDGE_PASSED (current_edge))
684 /* Pop entry off the stack. */
685 current_edge = stack[sp--];
686 node = ei_edge (current_edge)->src->index;
687 gcc_assert (node != ENTRY_BLOCK);
688 child = ei_edge (current_edge)->dest->index;
689 gcc_assert (child != EXIT_BLOCK);
690 bitmap_clear_bit (in_stack, child);
691 if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
692 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
693 ei_next (&current_edge);
696 /* See if have finished the DFS tree traversal. */
697 if (sp < 0 && EDGE_PASSED (current_edge))
698 break;
700 /* Nope, continue the traversal with the popped node. */
701 continue;
704 /* Process a node. */
705 node = ei_edge (current_edge)->src->index;
706 gcc_assert (node != ENTRY_BLOCK);
707 bitmap_set_bit (in_stack, node);
708 dfs_nr[node] = ++count;
710 /* We don't traverse to the exit block. */
711 child = ei_edge (current_edge)->dest->index;
712 if (child == EXIT_BLOCK)
714 SET_EDGE_PASSED (current_edge);
715 ei_next (&current_edge);
716 continue;
719 /* If the successor is in the stack, then we've found a loop.
720 Mark the loop, if it is not a natural loop, then it will
721 be rejected during the second traversal. */
722 if (bitmap_bit_p (in_stack, child))
724 no_loops = 0;
725 bitmap_set_bit (header, child);
726 UPDATE_LOOP_RELATIONS (node, child);
727 SET_EDGE_PASSED (current_edge);
728 ei_next (&current_edge);
729 continue;
732 /* If the child was already visited, then there is no need to visit
733 it again. Just update the loop relationships and restart
734 with a new edge. */
735 if (dfs_nr[child])
737 if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
738 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
739 SET_EDGE_PASSED (current_edge);
740 ei_next (&current_edge);
741 continue;
744 /* Push an entry on the stack and continue DFS traversal. */
745 stack[++sp] = current_edge;
746 SET_EDGE_PASSED (current_edge);
747 current_edge = ei_start (ei_edge (current_edge)->dest->succs);
750 /* Reset ->aux field used by EDGE_PASSED. */
751 FOR_ALL_BB_FN (bb, cfun)
753 edge_iterator ei;
754 edge e;
755 FOR_EACH_EDGE (e, ei, bb->succs)
756 e->aux = NULL;
760 /* Another check for unreachable blocks. The earlier test in
761 is_cfg_nonregular only finds unreachable blocks that do not
762 form a loop.
764 The DFS traversal will mark every block that is reachable from
765 the entry node by placing a nonzero value in dfs_nr. Thus if
766 dfs_nr is zero for any block, then it must be unreachable. */
767 unreachable = 0;
768 FOR_EACH_BB_FN (bb, cfun)
769 if (dfs_nr[bb->index] == 0)
771 unreachable = 1;
772 break;
775 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
776 to hold degree counts. */
777 degree = dfs_nr;
779 FOR_EACH_BB_FN (bb, cfun)
780 degree[bb->index] = EDGE_COUNT (bb->preds);
782 /* Do not perform region scheduling if there are any unreachable
783 blocks. */
784 if (!unreachable)
786 int *queue, *degree1 = NULL;
787 /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
788 there basic blocks, which are forced to be region heads.
789 This is done to try to assemble few smaller regions
790 from a too_large region. */
791 sbitmap extended_rgn_header = NULL;
792 bool extend_regions_p;
794 if (no_loops)
795 bitmap_set_bit (header, 0);
797 /* Second traversal:find reducible inner loops and topologically sort
798 block of each region. */
800 queue = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
802 extend_regions_p = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS) > 0;
803 if (extend_regions_p)
805 degree1 = XNEWVEC (int, last_basic_block_for_fn (cfun));
806 extended_rgn_header =
807 sbitmap_alloc (last_basic_block_for_fn (cfun));
808 bitmap_clear (extended_rgn_header);
811 /* Find blocks which are inner loop headers. We still have non-reducible
812 loops to consider at this point. */
813 FOR_EACH_BB_FN (bb, cfun)
815 if (bitmap_bit_p (header, bb->index) && bitmap_bit_p (inner, bb->index))
817 edge e;
818 edge_iterator ei;
819 basic_block jbb;
821 /* Now check that the loop is reducible. We do this separate
822 from finding inner loops so that we do not find a reducible
823 loop which contains an inner non-reducible loop.
825 A simple way to find reducible/natural loops is to verify
826 that each block in the loop is dominated by the loop
827 header.
829 If there exists a block that is not dominated by the loop
830 header, then the block is reachable from outside the loop
831 and thus the loop is not a natural loop. */
832 FOR_EACH_BB_FN (jbb, cfun)
834 /* First identify blocks in the loop, except for the loop
835 entry block. */
836 if (bb->index == max_hdr[jbb->index] && bb != jbb)
838 /* Now verify that the block is dominated by the loop
839 header. */
840 if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))
841 break;
845 /* If we exited the loop early, then I is the header of
846 a non-reducible loop and we should quit processing it
847 now. */
848 if (jbb != EXIT_BLOCK_PTR_FOR_FN (cfun))
849 continue;
851 /* I is a header of an inner loop, or block 0 in a subroutine
852 with no loops at all. */
853 head = tail = -1;
854 too_large_failure = 0;
855 loop_head = max_hdr[bb->index];
857 if (extend_regions_p)
858 /* We save degree in case when we meet a too_large region
859 and cancel it. We need a correct degree later when
860 calling extend_rgns. */
861 memcpy (degree1, degree,
862 last_basic_block_for_fn (cfun) * sizeof (int));
864 /* Decrease degree of all I's successors for topological
865 ordering. */
866 FOR_EACH_EDGE (e, ei, bb->succs)
867 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
868 --degree[e->dest->index];
870 /* Estimate # insns, and count # blocks in the region. */
871 num_bbs = 1;
872 num_insns = common_sched_info->estimate_number_of_insns (bb);
874 /* Find all loop latches (blocks with back edges to the loop
875 header) or all the leaf blocks in the cfg has no loops.
877 Place those blocks into the queue. */
878 if (no_loops)
880 FOR_EACH_BB_FN (jbb, cfun)
881 /* Leaf nodes have only a single successor which must
882 be EXIT_BLOCK. */
883 if (single_succ_p (jbb)
884 && single_succ (jbb) == EXIT_BLOCK_PTR_FOR_FN (cfun))
886 queue[++tail] = jbb->index;
887 bitmap_set_bit (in_queue, jbb->index);
889 if (too_large (jbb->index, &num_bbs, &num_insns))
891 too_large_failure = 1;
892 break;
896 else
898 edge e;
900 FOR_EACH_EDGE (e, ei, bb->preds)
902 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
903 continue;
905 node = e->src->index;
907 if (max_hdr[node] == loop_head && node != bb->index)
909 /* This is a loop latch. */
910 queue[++tail] = node;
911 bitmap_set_bit (in_queue, node);
913 if (too_large (node, &num_bbs, &num_insns))
915 too_large_failure = 1;
916 break;
922 /* Now add all the blocks in the loop to the queue.
924 We know the loop is a natural loop; however the algorithm
925 above will not always mark certain blocks as being in the
926 loop. Consider:
927 node children
928 a b,c
930 c a,d
933 The algorithm in the DFS traversal may not mark B & D as part
934 of the loop (i.e. they will not have max_hdr set to A).
936 We know they can not be loop latches (else they would have
937 had max_hdr set since they'd have a backedge to a dominator
938 block). So we don't need them on the initial queue.
940 We know they are part of the loop because they are dominated
941 by the loop header and can be reached by a backwards walk of
942 the edges starting with nodes on the initial queue.
944 It is safe and desirable to include those nodes in the
945 loop/scheduling region. To do so we would need to decrease
946 the degree of a node if it is the target of a backedge
947 within the loop itself as the node is placed in the queue.
949 We do not do this because I'm not sure that the actual
950 scheduling code will properly handle this case. ?!? */
952 while (head < tail && !too_large_failure)
954 edge e;
955 child = queue[++head];
957 FOR_EACH_EDGE (e, ei,
958 BASIC_BLOCK_FOR_FN (cfun, child)->preds)
960 node = e->src->index;
962 /* See discussion above about nodes not marked as in
963 this loop during the initial DFS traversal. */
964 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
965 || max_hdr[node] != loop_head)
967 tail = -1;
968 break;
970 else if (!bitmap_bit_p (in_queue, node) && node != bb->index)
972 queue[++tail] = node;
973 bitmap_set_bit (in_queue, node);
975 if (too_large (node, &num_bbs, &num_insns))
977 too_large_failure = 1;
978 break;
984 if (tail >= 0 && !too_large_failure)
986 /* Place the loop header into list of region blocks. */
987 degree[bb->index] = -1;
988 rgn_bb_table[idx] = bb->index;
989 RGN_NR_BLOCKS (nr_regions) = num_bbs;
990 RGN_BLOCKS (nr_regions) = idx++;
991 RGN_DONT_CALC_DEPS (nr_regions) = 0;
992 RGN_HAS_REAL_EBB (nr_regions) = 0;
993 CONTAINING_RGN (bb->index) = nr_regions;
994 BLOCK_TO_BB (bb->index) = count = 0;
996 /* Remove blocks from queue[] when their in degree
997 becomes zero. Repeat until no blocks are left on the
998 list. This produces a topological list of blocks in
999 the region. */
1000 while (tail >= 0)
1002 if (head < 0)
1003 head = tail;
1004 child = queue[head];
1005 if (degree[child] == 0)
1007 edge e;
1009 degree[child] = -1;
1010 rgn_bb_table[idx++] = child;
1011 BLOCK_TO_BB (child) = ++count;
1012 CONTAINING_RGN (child) = nr_regions;
1013 queue[head] = queue[tail--];
1015 FOR_EACH_EDGE (e, ei,
1016 BASIC_BLOCK_FOR_FN (cfun,
1017 child)->succs)
1018 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1019 --degree[e->dest->index];
1021 else
1022 --head;
1024 ++nr_regions;
1026 else if (extend_regions_p)
1028 /* Restore DEGREE. */
1029 int *t = degree;
1031 degree = degree1;
1032 degree1 = t;
1034 /* And force successors of BB to be region heads.
1035 This may provide several smaller regions instead
1036 of one too_large region. */
1037 FOR_EACH_EDGE (e, ei, bb->succs)
1038 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1039 bitmap_set_bit (extended_rgn_header, e->dest->index);
1043 free (queue);
1045 if (extend_regions_p)
1047 free (degree1);
1049 bitmap_ior (header, header, extended_rgn_header);
1050 sbitmap_free (extended_rgn_header);
1052 extend_rgns (degree, &idx, header, max_hdr);
1056 /* Any block that did not end up in a region is placed into a region
1057 by itself. */
1058 FOR_EACH_BB_FN (bb, cfun)
1059 if (degree[bb->index] >= 0)
1061 rgn_bb_table[idx] = bb->index;
1062 RGN_NR_BLOCKS (nr_regions) = 1;
1063 RGN_BLOCKS (nr_regions) = idx++;
1064 RGN_DONT_CALC_DEPS (nr_regions) = 0;
1065 RGN_HAS_REAL_EBB (nr_regions) = 0;
1066 CONTAINING_RGN (bb->index) = nr_regions++;
1067 BLOCK_TO_BB (bb->index) = 0;
1070 free (max_hdr);
1071 free (degree);
1072 free (stack);
1073 sbitmap_free (header);
1074 sbitmap_free (inner);
1075 sbitmap_free (in_queue);
1076 sbitmap_free (in_stack);
1080 /* Wrapper function.
1081 If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
1082 regions. Otherwise just call find_rgns_haifa. */
1083 static void
1084 find_rgns (void)
1086 if (sel_sched_p () && flag_sel_sched_pipelining)
1087 sel_find_rgns ();
1088 else
1089 haifa_find_rgns ();
1092 static int gather_region_statistics (int **);
1093 static void print_region_statistics (int *, int, int *, int);
1095 /* Calculate the histogram that shows the number of regions having the
1096 given number of basic blocks, and store it in the RSP array. Return
1097 the size of this array. */
1098 static int
1099 gather_region_statistics (int **rsp)
1101 int i, *a = 0, a_sz = 0;
1103 /* a[i] is the number of regions that have (i + 1) basic blocks. */
1104 for (i = 0; i < nr_regions; i++)
1106 int nr_blocks = RGN_NR_BLOCKS (i);
1108 gcc_assert (nr_blocks >= 1);
1110 if (nr_blocks > a_sz)
1112 a = XRESIZEVEC (int, a, nr_blocks);
1114 a[a_sz++] = 0;
1115 while (a_sz != nr_blocks);
1118 a[nr_blocks - 1]++;
1121 *rsp = a;
1122 return a_sz;
1125 /* Print regions statistics. S1 and S2 denote the data before and after
1126 calling extend_rgns, respectively. */
1127 static void
1128 print_region_statistics (int *s1, int s1_sz, int *s2, int s2_sz)
1130 int i;
1132 /* We iterate until s2_sz because extend_rgns does not decrease
1133 the maximal region size. */
1134 for (i = 1; i < s2_sz; i++)
1136 int n1, n2;
1138 n2 = s2[i];
1140 if (n2 == 0)
1141 continue;
1143 if (i >= s1_sz)
1144 n1 = 0;
1145 else
1146 n1 = s1[i];
1148 fprintf (sched_dump, ";; Region extension statistics: size %d: " \
1149 "was %d + %d more\n", i + 1, n1, n2 - n1);
1153 /* Extend regions.
1154 DEGREE - Array of incoming edge count, considering only
1155 the edges, that don't have their sources in formed regions yet.
1156 IDXP - pointer to the next available index in rgn_bb_table.
1157 HEADER - set of all region heads.
1158 LOOP_HDR - mapping from block to the containing loop
1159 (two blocks can reside within one region if they have
1160 the same loop header). */
1161 void
1162 extend_rgns (int *degree, int *idxp, sbitmap header, int *loop_hdr)
1164 int *order, i, rescan = 0, idx = *idxp, iter = 0, max_iter, *max_hdr;
1165 int nblocks = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
1167 max_iter = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS);
1169 max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
1171 order = XNEWVEC (int, last_basic_block_for_fn (cfun));
1172 post_order_compute (order, false, false);
1174 for (i = nblocks - 1; i >= 0; i--)
1176 int bbn = order[i];
1177 if (degree[bbn] >= 0)
1179 max_hdr[bbn] = bbn;
1180 rescan = 1;
1182 else
1183 /* This block already was processed in find_rgns. */
1184 max_hdr[bbn] = -1;
1187 /* The idea is to topologically walk through CFG in top-down order.
1188 During the traversal, if all the predecessors of a node are
1189 marked to be in the same region (they all have the same max_hdr),
1190 then current node is also marked to be a part of that region.
1191 Otherwise the node starts its own region.
1192 CFG should be traversed until no further changes are made. On each
1193 iteration the set of the region heads is extended (the set of those
1194 blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
1195 set of all basic blocks, thus the algorithm is guaranteed to
1196 terminate. */
1198 while (rescan && iter < max_iter)
1200 rescan = 0;
1202 for (i = nblocks - 1; i >= 0; i--)
1204 edge e;
1205 edge_iterator ei;
1206 int bbn = order[i];
1208 if (max_hdr[bbn] != -1 && !bitmap_bit_p (header, bbn))
1210 int hdr = -1;
1212 FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->preds)
1214 int predn = e->src->index;
1216 if (predn != ENTRY_BLOCK
1217 /* If pred wasn't processed in find_rgns. */
1218 && max_hdr[predn] != -1
1219 /* And pred and bb reside in the same loop.
1220 (Or out of any loop). */
1221 && loop_hdr[bbn] == loop_hdr[predn])
1223 if (hdr == -1)
1224 /* Then bb extends the containing region of pred. */
1225 hdr = max_hdr[predn];
1226 else if (hdr != max_hdr[predn])
1227 /* Too bad, there are at least two predecessors
1228 that reside in different regions. Thus, BB should
1229 begin its own region. */
1231 hdr = bbn;
1232 break;
1235 else
1236 /* BB starts its own region. */
1238 hdr = bbn;
1239 break;
1243 if (hdr == bbn)
1245 /* If BB start its own region,
1246 update set of headers with BB. */
1247 bitmap_set_bit (header, bbn);
1248 rescan = 1;
1250 else
1251 gcc_assert (hdr != -1);
1253 max_hdr[bbn] = hdr;
1257 iter++;
1260 /* Statistics were gathered on the SPEC2000 package of tests with
1261 mainline weekly snapshot gcc-4.1-20051015 on ia64.
1263 Statistics for SPECint:
1264 1 iteration : 1751 cases (38.7%)
1265 2 iterations: 2770 cases (61.3%)
1266 Blocks wrapped in regions by find_rgns without extension: 18295 blocks
1267 Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
1268 (We don't count single block regions here).
1270 Statistics for SPECfp:
1271 1 iteration : 621 cases (35.9%)
1272 2 iterations: 1110 cases (64.1%)
1273 Blocks wrapped in regions by find_rgns without extension: 6476 blocks
1274 Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
1275 (We don't count single block regions here).
1277 By default we do at most 2 iterations.
1278 This can be overridden with max-sched-extend-regions-iters parameter:
1279 0 - disable region extension,
1280 N > 0 - do at most N iterations. */
1282 if (sched_verbose && iter != 0)
1283 fprintf (sched_dump, ";; Region extension iterations: %d%s\n", iter,
1284 rescan ? "... failed" : "");
1286 if (!rescan && iter != 0)
1288 int *s1 = NULL, s1_sz = 0;
1290 /* Save the old statistics for later printout. */
1291 if (sched_verbose >= 6)
1292 s1_sz = gather_region_statistics (&s1);
1294 /* We have succeeded. Now assemble the regions. */
1295 for (i = nblocks - 1; i >= 0; i--)
1297 int bbn = order[i];
1299 if (max_hdr[bbn] == bbn)
1300 /* BBN is a region head. */
1302 edge e;
1303 edge_iterator ei;
1304 int num_bbs = 0, j, num_insns = 0, large;
1306 large = too_large (bbn, &num_bbs, &num_insns);
1308 degree[bbn] = -1;
1309 rgn_bb_table[idx] = bbn;
1310 RGN_BLOCKS (nr_regions) = idx++;
1311 RGN_DONT_CALC_DEPS (nr_regions) = 0;
1312 RGN_HAS_REAL_EBB (nr_regions) = 0;
1313 CONTAINING_RGN (bbn) = nr_regions;
1314 BLOCK_TO_BB (bbn) = 0;
1316 FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->succs)
1317 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1318 degree[e->dest->index]--;
1320 if (!large)
1321 /* Here we check whether the region is too_large. */
1322 for (j = i - 1; j >= 0; j--)
1324 int succn = order[j];
1325 if (max_hdr[succn] == bbn)
1327 if ((large = too_large (succn, &num_bbs, &num_insns)))
1328 break;
1332 if (large)
1333 /* If the region is too_large, then wrap every block of
1334 the region into single block region.
1335 Here we wrap region head only. Other blocks are
1336 processed in the below cycle. */
1338 RGN_NR_BLOCKS (nr_regions) = 1;
1339 nr_regions++;
1342 num_bbs = 1;
1344 for (j = i - 1; j >= 0; j--)
1346 int succn = order[j];
1348 if (max_hdr[succn] == bbn)
1349 /* This cycle iterates over all basic blocks, that
1350 are supposed to be in the region with head BBN,
1351 and wraps them into that region (or in single
1352 block region). */
1354 gcc_assert (degree[succn] == 0);
1356 degree[succn] = -1;
1357 rgn_bb_table[idx] = succn;
1358 BLOCK_TO_BB (succn) = large ? 0 : num_bbs++;
1359 CONTAINING_RGN (succn) = nr_regions;
1361 if (large)
1362 /* Wrap SUCCN into single block region. */
1364 RGN_BLOCKS (nr_regions) = idx;
1365 RGN_NR_BLOCKS (nr_regions) = 1;
1366 RGN_DONT_CALC_DEPS (nr_regions) = 0;
1367 RGN_HAS_REAL_EBB (nr_regions) = 0;
1368 nr_regions++;
1371 idx++;
1373 FOR_EACH_EDGE (e, ei,
1374 BASIC_BLOCK_FOR_FN (cfun, succn)->succs)
1375 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1376 degree[e->dest->index]--;
1380 if (!large)
1382 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1383 nr_regions++;
1388 if (sched_verbose >= 6)
1390 int *s2, s2_sz;
1392 /* Get the new statistics and print the comparison with the
1393 one before calling this function. */
1394 s2_sz = gather_region_statistics (&s2);
1395 print_region_statistics (s1, s1_sz, s2, s2_sz);
1396 free (s1);
1397 free (s2);
1401 free (order);
1402 free (max_hdr);
1404 *idxp = idx;
1407 /* Functions for regions scheduling information. */
1409 /* Compute dominators, probability, and potential-split-edges of bb.
1410 Assume that these values were already computed for bb's predecessors. */
1412 static void
1413 compute_dom_prob_ps (int bb)
1415 edge_iterator in_ei;
1416 edge in_edge;
1418 /* We shouldn't have any real ebbs yet. */
1419 gcc_assert (ebb_head [bb] == bb + current_blocks);
1421 if (IS_RGN_ENTRY (bb))
1423 bitmap_set_bit (dom[bb], 0);
1424 prob[bb] = REG_BR_PROB_BASE;
1425 return;
1428 prob[bb] = 0;
1430 /* Initialize dom[bb] to '111..1'. */
1431 bitmap_ones (dom[bb]);
1433 FOR_EACH_EDGE (in_edge, in_ei,
1434 BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb))->preds)
1436 int pred_bb;
1437 edge out_edge;
1438 edge_iterator out_ei;
1440 if (in_edge->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1441 continue;
1443 pred_bb = BLOCK_TO_BB (in_edge->src->index);
1444 bitmap_and (dom[bb], dom[bb], dom[pred_bb]);
1445 bitmap_ior (ancestor_edges[bb],
1446 ancestor_edges[bb], ancestor_edges[pred_bb]);
1448 bitmap_set_bit (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
1450 bitmap_ior (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
1452 FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
1453 bitmap_set_bit (pot_split[bb], EDGE_TO_BIT (out_edge));
1455 prob[bb] += combine_probabilities (prob[pred_bb], in_edge->probability);
1456 // The rounding divide in combine_probabilities can result in an extra
1457 // probability increment propagating along 50-50 edges. Eventually when
1458 // the edges re-merge, the accumulated probability can go slightly above
1459 // REG_BR_PROB_BASE.
1460 if (prob[bb] > REG_BR_PROB_BASE)
1461 prob[bb] = REG_BR_PROB_BASE;
1464 bitmap_set_bit (dom[bb], bb);
1465 bitmap_and_compl (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
1467 if (sched_verbose >= 2)
1468 fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
1469 (100 * prob[bb]) / REG_BR_PROB_BASE);
1472 /* Functions for target info. */
1474 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1475 Note that bb_trg dominates bb_src. */
1477 static void
1478 split_edges (int bb_src, int bb_trg, edgelst *bl)
1480 sbitmap src = sbitmap_alloc (SBITMAP_SIZE (pot_split[bb_src]));
1481 bitmap_copy (src, pot_split[bb_src]);
1483 bitmap_and_compl (src, src, pot_split[bb_trg]);
1484 extract_edgelst (src, bl);
1485 sbitmap_free (src);
1488 /* Find the valid candidate-source-blocks for the target block TRG, compute
1489 their probability, and check if they are speculative or not.
1490 For speculative sources, compute their update-blocks and split-blocks. */
1492 static void
1493 compute_trg_info (int trg)
1495 candidate *sp;
1496 edgelst el = { NULL, 0 };
1497 int i, j, k, update_idx;
1498 basic_block block;
1499 sbitmap visited;
1500 edge_iterator ei;
1501 edge e;
1503 candidate_table = XNEWVEC (candidate, current_nr_blocks);
1505 bblst_last = 0;
1506 /* bblst_table holds split blocks and update blocks for each block after
1507 the current one in the region. split blocks and update blocks are
1508 the TO blocks of region edges, so there can be at most rgn_nr_edges
1509 of them. */
1510 bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
1511 bblst_table = XNEWVEC (basic_block, bblst_size);
1513 edgelst_last = 0;
1514 edgelst_table = XNEWVEC (edge, rgn_nr_edges);
1516 /* Define some of the fields for the target bb as well. */
1517 sp = candidate_table + trg;
1518 sp->is_valid = 1;
1519 sp->is_speculative = 0;
1520 sp->src_prob = REG_BR_PROB_BASE;
1522 visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
1524 for (i = trg + 1; i < current_nr_blocks; i++)
1526 sp = candidate_table + i;
1528 sp->is_valid = IS_DOMINATED (i, trg);
1529 if (sp->is_valid)
1531 int tf = prob[trg], cf = prob[i];
1533 /* In CFGs with low probability edges TF can possibly be zero. */
1534 sp->src_prob = (tf ? GCOV_COMPUTE_SCALE (cf, tf) : 0);
1535 sp->is_valid = (sp->src_prob >= min_spec_prob);
1538 if (sp->is_valid)
1540 split_edges (i, trg, &el);
1541 sp->is_speculative = (el.nr_members) ? 1 : 0;
1542 if (sp->is_speculative && !flag_schedule_speculative)
1543 sp->is_valid = 0;
1546 if (sp->is_valid)
1548 /* Compute split blocks and store them in bblst_table.
1549 The TO block of every split edge is a split block. */
1550 sp->split_bbs.first_member = &bblst_table[bblst_last];
1551 sp->split_bbs.nr_members = el.nr_members;
1552 for (j = 0; j < el.nr_members; bblst_last++, j++)
1553 bblst_table[bblst_last] = el.first_member[j]->dest;
1554 sp->update_bbs.first_member = &bblst_table[bblst_last];
1556 /* Compute update blocks and store them in bblst_table.
1557 For every split edge, look at the FROM block, and check
1558 all out edges. For each out edge that is not a split edge,
1559 add the TO block to the update block list. This list can end
1560 up with a lot of duplicates. We need to weed them out to avoid
1561 overrunning the end of the bblst_table. */
1563 update_idx = 0;
1564 bitmap_clear (visited);
1565 for (j = 0; j < el.nr_members; j++)
1567 block = el.first_member[j]->src;
1568 FOR_EACH_EDGE (e, ei, block->succs)
1570 if (!bitmap_bit_p (visited, e->dest->index))
1572 for (k = 0; k < el.nr_members; k++)
1573 if (e == el.first_member[k])
1574 break;
1576 if (k >= el.nr_members)
1578 bblst_table[bblst_last++] = e->dest;
1579 bitmap_set_bit (visited, e->dest->index);
1580 update_idx++;
1585 sp->update_bbs.nr_members = update_idx;
1587 /* Make sure we didn't overrun the end of bblst_table. */
1588 gcc_assert (bblst_last <= bblst_size);
1590 else
1592 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1594 sp->is_speculative = 0;
1595 sp->src_prob = 0;
1599 sbitmap_free (visited);
1602 /* Free the computed target info. */
1603 static void
1604 free_trg_info (void)
1606 free (candidate_table);
1607 free (bblst_table);
1608 free (edgelst_table);
1611 /* Print candidates info, for debugging purposes. Callable from debugger. */
1613 DEBUG_FUNCTION void
1614 debug_candidate (int i)
1616 if (!candidate_table[i].is_valid)
1617 return;
1619 if (candidate_table[i].is_speculative)
1621 int j;
1622 fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1624 fprintf (sched_dump, "split path: ");
1625 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1627 int b = candidate_table[i].split_bbs.first_member[j]->index;
1629 fprintf (sched_dump, " %d ", b);
1631 fprintf (sched_dump, "\n");
1633 fprintf (sched_dump, "update path: ");
1634 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
1636 int b = candidate_table[i].update_bbs.first_member[j]->index;
1638 fprintf (sched_dump, " %d ", b);
1640 fprintf (sched_dump, "\n");
1642 else
1644 fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
1648 /* Print candidates info, for debugging purposes. Callable from debugger. */
1650 DEBUG_FUNCTION void
1651 debug_candidates (int trg)
1653 int i;
1655 fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
1656 BB_TO_BLOCK (trg), trg);
1657 for (i = trg + 1; i < current_nr_blocks; i++)
1658 debug_candidate (i);
1661 /* Functions for speculative scheduling. */
1663 static bitmap_head not_in_df;
1665 /* Return 0 if x is a set of a register alive in the beginning of one
1666 of the split-blocks of src, otherwise return 1. */
1668 static int
1669 check_live_1 (int src, rtx x)
1671 int i;
1672 int regno;
1673 rtx reg = SET_DEST (x);
1675 if (reg == 0)
1676 return 1;
1678 while (GET_CODE (reg) == SUBREG
1679 || GET_CODE (reg) == ZERO_EXTRACT
1680 || GET_CODE (reg) == STRICT_LOW_PART)
1681 reg = XEXP (reg, 0);
1683 if (GET_CODE (reg) == PARALLEL)
1685 int i;
1687 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1688 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1689 if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
1690 return 1;
1692 return 0;
1695 if (!REG_P (reg))
1696 return 1;
1698 regno = REGNO (reg);
1700 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1702 /* Global registers are assumed live. */
1703 return 0;
1705 else
1707 if (regno < FIRST_PSEUDO_REGISTER)
1709 /* Check for hard registers. */
1710 int j = REG_NREGS (reg);
1711 while (--j >= 0)
1713 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1715 basic_block b = candidate_table[src].split_bbs.first_member[i];
1716 int t = bitmap_bit_p (&not_in_df, b->index);
1718 /* We can have split blocks, that were recently generated.
1719 Such blocks are always outside current region. */
1720 gcc_assert (!t || (CONTAINING_RGN (b->index)
1721 != CONTAINING_RGN (BB_TO_BLOCK (src))));
1723 if (t || REGNO_REG_SET_P (df_get_live_in (b), regno + j))
1724 return 0;
1728 else
1730 /* Check for pseudo registers. */
1731 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1733 basic_block b = candidate_table[src].split_bbs.first_member[i];
1734 int t = bitmap_bit_p (&not_in_df, b->index);
1736 gcc_assert (!t || (CONTAINING_RGN (b->index)
1737 != CONTAINING_RGN (BB_TO_BLOCK (src))));
1739 if (t || REGNO_REG_SET_P (df_get_live_in (b), regno))
1740 return 0;
1745 return 1;
1748 /* If x is a set of a register R, mark that R is alive in the beginning
1749 of every update-block of src. */
1751 static void
1752 update_live_1 (int src, rtx x)
1754 int i;
1755 int regno;
1756 rtx reg = SET_DEST (x);
1758 if (reg == 0)
1759 return;
1761 while (GET_CODE (reg) == SUBREG
1762 || GET_CODE (reg) == ZERO_EXTRACT
1763 || GET_CODE (reg) == STRICT_LOW_PART)
1764 reg = XEXP (reg, 0);
1766 if (GET_CODE (reg) == PARALLEL)
1768 int i;
1770 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1771 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1772 update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
1774 return;
1777 if (!REG_P (reg))
1778 return;
1780 /* Global registers are always live, so the code below does not apply
1781 to them. */
1783 regno = REGNO (reg);
1785 if (! HARD_REGISTER_NUM_P (regno)
1786 || !global_regs[regno])
1788 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1790 basic_block b = candidate_table[src].update_bbs.first_member[i];
1791 bitmap_set_range (df_get_live_in (b), regno, REG_NREGS (reg));
1796 /* Return 1 if insn can be speculatively moved from block src to trg,
1797 otherwise return 0. Called before first insertion of insn to
1798 ready-list or before the scheduling. */
1800 static int
1801 check_live (rtx_insn *insn, int src)
1803 /* Find the registers set by instruction. */
1804 if (GET_CODE (PATTERN (insn)) == SET
1805 || GET_CODE (PATTERN (insn)) == CLOBBER)
1806 return check_live_1 (src, PATTERN (insn));
1807 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1809 int j;
1810 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1811 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1812 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1813 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
1814 return 0;
1816 return 1;
1819 return 1;
1822 /* Update the live registers info after insn was moved speculatively from
1823 block src to trg. */
1825 static void
1826 update_live (rtx_insn *insn, int src)
1828 /* Find the registers set by instruction. */
1829 if (GET_CODE (PATTERN (insn)) == SET
1830 || GET_CODE (PATTERN (insn)) == CLOBBER)
1831 update_live_1 (src, PATTERN (insn));
1832 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1834 int j;
1835 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1836 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1837 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1838 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
1842 /* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1843 #define IS_REACHABLE(bb_from, bb_to) \
1844 (bb_from == bb_to \
1845 || IS_RGN_ENTRY (bb_from) \
1846 || (bitmap_bit_p (ancestor_edges[bb_to], \
1847 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK_FOR_FN (cfun, \
1848 BB_TO_BLOCK (bb_from)))))))
1850 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1852 static void
1853 set_spec_fed (rtx load_insn)
1855 sd_iterator_def sd_it;
1856 dep_t dep;
1858 FOR_EACH_DEP (load_insn, SD_LIST_FORW, sd_it, dep)
1859 if (DEP_TYPE (dep) == REG_DEP_TRUE)
1860 FED_BY_SPEC_LOAD (DEP_CON (dep)) = 1;
1863 /* On the path from the insn to load_insn_bb, find a conditional
1864 branch depending on insn, that guards the speculative load. */
1866 static int
1867 find_conditional_protection (rtx_insn *insn, int load_insn_bb)
1869 sd_iterator_def sd_it;
1870 dep_t dep;
1872 /* Iterate through DEF-USE forward dependences. */
1873 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
1875 rtx_insn *next = DEP_CON (dep);
1877 if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
1878 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
1879 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
1880 && load_insn_bb != INSN_BB (next)
1881 && DEP_TYPE (dep) == REG_DEP_TRUE
1882 && (JUMP_P (next)
1883 || find_conditional_protection (next, load_insn_bb)))
1884 return 1;
1886 return 0;
1887 } /* find_conditional_protection */
1889 /* Returns 1 if the same insn1 that participates in the computation
1890 of load_insn's address is feeding a conditional branch that is
1891 guarding on load_insn. This is true if we find two DEF-USE
1892 chains:
1893 insn1 -> ... -> conditional-branch
1894 insn1 -> ... -> load_insn,
1895 and if a flow path exists:
1896 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1897 and if insn1 is on the path
1898 region-entry -> ... -> bb_trg -> ... load_insn.
1900 Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
1901 Locate the branch by following INSN_FORW_DEPS from insn1. */
1903 static int
1904 is_conditionally_protected (rtx load_insn, int bb_src, int bb_trg)
1906 sd_iterator_def sd_it;
1907 dep_t dep;
1909 FOR_EACH_DEP (load_insn, SD_LIST_BACK, sd_it, dep)
1911 rtx_insn *insn1 = DEP_PRO (dep);
1913 /* Must be a DEF-USE dependence upon non-branch. */
1914 if (DEP_TYPE (dep) != REG_DEP_TRUE
1915 || JUMP_P (insn1))
1916 continue;
1918 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1919 if (INSN_BB (insn1) == bb_src
1920 || (CONTAINING_RGN (BLOCK_NUM (insn1))
1921 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
1922 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
1923 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
1924 continue;
1926 /* Now search for the conditional-branch. */
1927 if (find_conditional_protection (insn1, bb_src))
1928 return 1;
1930 /* Recursive step: search another insn1, "above" current insn1. */
1931 return is_conditionally_protected (insn1, bb_src, bb_trg);
1934 /* The chain does not exist. */
1935 return 0;
1936 } /* is_conditionally_protected */
1938 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1939 load_insn can move speculatively from bb_src to bb_trg. All the
1940 following must hold:
1942 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1943 (2) load_insn and load1 have a def-use dependence upon
1944 the same insn 'insn1'.
1945 (3) either load2 is in bb_trg, or:
1946 - there's only one split-block, and
1947 - load1 is on the escape path, and
1949 From all these we can conclude that the two loads access memory
1950 addresses that differ at most by a constant, and hence if moving
1951 load_insn would cause an exception, it would have been caused by
1952 load2 anyhow. */
1954 static int
1955 is_pfree (rtx load_insn, int bb_src, int bb_trg)
1957 sd_iterator_def back_sd_it;
1958 dep_t back_dep;
1959 candidate *candp = candidate_table + bb_src;
1961 if (candp->split_bbs.nr_members != 1)
1962 /* Must have exactly one escape block. */
1963 return 0;
1965 FOR_EACH_DEP (load_insn, SD_LIST_BACK, back_sd_it, back_dep)
1967 rtx_insn *insn1 = DEP_PRO (back_dep);
1969 if (DEP_TYPE (back_dep) == REG_DEP_TRUE)
1970 /* Found a DEF-USE dependence (insn1, load_insn). */
1972 sd_iterator_def fore_sd_it;
1973 dep_t fore_dep;
1975 FOR_EACH_DEP (insn1, SD_LIST_FORW, fore_sd_it, fore_dep)
1977 rtx_insn *insn2 = DEP_CON (fore_dep);
1979 if (DEP_TYPE (fore_dep) == REG_DEP_TRUE)
1981 /* Found a DEF-USE dependence (insn1, insn2). */
1982 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
1983 /* insn2 not guaranteed to be a 1 base reg load. */
1984 continue;
1986 if (INSN_BB (insn2) == bb_trg)
1987 /* insn2 is the similar load, in the target block. */
1988 return 1;
1990 if (*(candp->split_bbs.first_member) == BLOCK_FOR_INSN (insn2))
1991 /* insn2 is a similar load, in a split-block. */
1992 return 1;
1998 /* Couldn't find a similar load. */
1999 return 0;
2000 } /* is_pfree */
2002 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2003 a load moved speculatively, or if load_insn is protected by
2004 a compare on load_insn's address). */
2006 static int
2007 is_prisky (rtx load_insn, int bb_src, int bb_trg)
2009 if (FED_BY_SPEC_LOAD (load_insn))
2010 return 1;
2012 if (sd_lists_empty_p (load_insn, SD_LIST_BACK))
2013 /* Dependence may 'hide' out of the region. */
2014 return 1;
2016 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2017 return 1;
2019 return 0;
2022 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2023 Return 1 if insn is exception-free (and the motion is valid)
2024 and 0 otherwise. */
2026 static int
2027 is_exception_free (rtx_insn *insn, int bb_src, int bb_trg)
2029 int insn_class = haifa_classify_insn (insn);
2031 /* Handle non-load insns. */
2032 switch (insn_class)
2034 case TRAP_FREE:
2035 return 1;
2036 case TRAP_RISKY:
2037 return 0;
2038 default:;
2041 /* Handle loads. */
2042 if (!flag_schedule_speculative_load)
2043 return 0;
2044 IS_LOAD_INSN (insn) = 1;
2045 switch (insn_class)
2047 case IFREE:
2048 return (1);
2049 case IRISKY:
2050 return 0;
2051 case PFREE_CANDIDATE:
2052 if (is_pfree (insn, bb_src, bb_trg))
2053 return 1;
2054 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2055 case PRISKY_CANDIDATE:
2056 if (!flag_schedule_speculative_load_dangerous
2057 || is_prisky (insn, bb_src, bb_trg))
2058 return 0;
2059 break;
2060 default:;
2063 return flag_schedule_speculative_load_dangerous;
2066 /* The number of insns from the current block scheduled so far. */
2067 static int sched_target_n_insns;
2068 /* The number of insns from the current block to be scheduled in total. */
2069 static int target_n_insns;
2070 /* The number of insns from the entire region scheduled so far. */
2071 static int sched_n_insns;
2073 /* Implementations of the sched_info functions for region scheduling. */
2074 static void init_ready_list (void);
2075 static int can_schedule_ready_p (rtx_insn *);
2076 static void begin_schedule_ready (rtx_insn *);
2077 static ds_t new_ready (rtx_insn *, ds_t);
2078 static int schedule_more_p (void);
2079 static const char *rgn_print_insn (const rtx_insn *, int);
2080 static int rgn_rank (rtx_insn *, rtx_insn *);
2081 static void compute_jump_reg_dependencies (rtx, regset);
2083 /* Functions for speculative scheduling. */
2084 static void rgn_add_remove_insn (rtx_insn *, int);
2085 static void rgn_add_block (basic_block, basic_block);
2086 static void rgn_fix_recovery_cfg (int, int, int);
2087 static basic_block advance_target_bb (basic_block, rtx_insn *);
2089 /* Return nonzero if there are more insns that should be scheduled. */
2091 static int
2092 schedule_more_p (void)
2094 return sched_target_n_insns < target_n_insns;
2097 /* Add all insns that are initially ready to the ready list READY. Called
2098 once before scheduling a set of insns. */
2100 static void
2101 init_ready_list (void)
2103 rtx_insn *prev_head = current_sched_info->prev_head;
2104 rtx_insn *next_tail = current_sched_info->next_tail;
2105 int bb_src;
2106 rtx_insn *insn;
2108 target_n_insns = 0;
2109 sched_target_n_insns = 0;
2110 sched_n_insns = 0;
2112 /* Print debugging information. */
2113 if (sched_verbose >= 5)
2114 debug_rgn_dependencies (target_bb);
2116 /* Prepare current target block info. */
2117 if (current_nr_blocks > 1)
2118 compute_trg_info (target_bb);
2120 /* Initialize ready list with all 'ready' insns in target block.
2121 Count number of insns in the target block being scheduled. */
2122 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
2124 gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
2125 TODO_SPEC (insn) = HARD_DEP;
2126 try_ready (insn);
2127 target_n_insns++;
2129 gcc_assert (!(TODO_SPEC (insn) & BEGIN_CONTROL));
2132 /* Add to ready list all 'ready' insns in valid source blocks.
2133 For speculative insns, check-live, exception-free, and
2134 issue-delay. */
2135 for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
2136 if (IS_VALID (bb_src))
2138 rtx_insn *src_head;
2139 rtx_insn *src_next_tail;
2140 rtx_insn *tail, *head;
2142 get_ebb_head_tail (EBB_FIRST_BB (bb_src), EBB_LAST_BB (bb_src),
2143 &head, &tail);
2144 src_next_tail = NEXT_INSN (tail);
2145 src_head = head;
2147 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
2148 if (INSN_P (insn))
2150 gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
2151 TODO_SPEC (insn) = HARD_DEP;
2152 try_ready (insn);
2157 /* Called after taking INSN from the ready list. Returns nonzero if this
2158 insn can be scheduled, nonzero if we should silently discard it. */
2160 static int
2161 can_schedule_ready_p (rtx_insn *insn)
2163 /* An interblock motion? */
2164 if (INSN_BB (insn) != target_bb
2165 && IS_SPECULATIVE_INSN (insn)
2166 && !check_live (insn, INSN_BB (insn)))
2167 return 0;
2168 else
2169 return 1;
2172 /* Updates counter and other information. Split from can_schedule_ready_p ()
2173 because when we schedule insn speculatively then insn passed to
2174 can_schedule_ready_p () differs from the one passed to
2175 begin_schedule_ready (). */
2176 static void
2177 begin_schedule_ready (rtx_insn *insn)
2179 /* An interblock motion? */
2180 if (INSN_BB (insn) != target_bb)
2182 if (IS_SPECULATIVE_INSN (insn))
2184 gcc_assert (check_live (insn, INSN_BB (insn)));
2186 update_live (insn, INSN_BB (insn));
2188 /* For speculative load, mark insns fed by it. */
2189 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
2190 set_spec_fed (insn);
2192 nr_spec++;
2194 nr_inter++;
2196 else
2198 /* In block motion. */
2199 sched_target_n_insns++;
2201 sched_n_insns++;
2204 /* Called after INSN has all its hard dependencies resolved and the speculation
2205 of type TS is enough to overcome them all.
2206 Return nonzero if it should be moved to the ready list or the queue, or zero
2207 if we should silently discard it. */
2208 static ds_t
2209 new_ready (rtx_insn *next, ds_t ts)
2211 if (INSN_BB (next) != target_bb)
2213 int not_ex_free = 0;
2215 /* For speculative insns, before inserting to ready/queue,
2216 check live, exception-free, and issue-delay. */
2217 if (!IS_VALID (INSN_BB (next))
2218 || CANT_MOVE (next)
2219 || (IS_SPECULATIVE_INSN (next)
2220 && ((recog_memoized (next) >= 0
2221 && min_insn_conflict_delay (curr_state, next, next)
2222 > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY))
2223 || IS_SPECULATION_CHECK_P (next)
2224 || !check_live (next, INSN_BB (next))
2225 || (not_ex_free = !is_exception_free (next, INSN_BB (next),
2226 target_bb)))))
2228 if (not_ex_free
2229 /* We are here because is_exception_free () == false.
2230 But we possibly can handle that with control speculation. */
2231 && sched_deps_info->generate_spec_deps
2232 && spec_info->mask & BEGIN_CONTROL)
2234 ds_t new_ds;
2236 /* Add control speculation to NEXT's dependency type. */
2237 new_ds = set_dep_weak (ts, BEGIN_CONTROL, MAX_DEP_WEAK);
2239 /* Check if NEXT can be speculated with new dependency type. */
2240 if (sched_insn_is_legitimate_for_speculation_p (next, new_ds))
2241 /* Here we got new control-speculative instruction. */
2242 ts = new_ds;
2243 else
2244 /* NEXT isn't ready yet. */
2245 ts = DEP_POSTPONED;
2247 else
2248 /* NEXT isn't ready yet. */
2249 ts = DEP_POSTPONED;
2253 return ts;
2256 /* Return a string that contains the insn uid and optionally anything else
2257 necessary to identify this insn in an output. It's valid to use a
2258 static buffer for this. The ALIGNED parameter should cause the string
2259 to be formatted so that multiple output lines will line up nicely. */
2261 static const char *
2262 rgn_print_insn (const rtx_insn *insn, int aligned)
2264 static char tmp[80];
2266 if (aligned)
2267 sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
2268 else
2270 if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
2271 sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
2272 else
2273 sprintf (tmp, "%d", INSN_UID (insn));
2275 return tmp;
2278 /* Compare priority of two insns. Return a positive number if the second
2279 insn is to be preferred for scheduling, and a negative one if the first
2280 is to be preferred. Zero if they are equally good. */
2282 static int
2283 rgn_rank (rtx_insn *insn1, rtx_insn *insn2)
2285 /* Some comparison make sense in interblock scheduling only. */
2286 if (INSN_BB (insn1) != INSN_BB (insn2))
2288 int spec_val, prob_val;
2290 /* Prefer an inblock motion on an interblock motion. */
2291 if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
2292 return 1;
2293 if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
2294 return -1;
2296 /* Prefer a useful motion on a speculative one. */
2297 spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
2298 if (spec_val)
2299 return spec_val;
2301 /* Prefer a more probable (speculative) insn. */
2302 prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
2303 if (prob_val)
2304 return prob_val;
2306 return 0;
2309 /* NEXT is an instruction that depends on INSN (a backward dependence);
2310 return nonzero if we should include this dependence in priority
2311 calculations. */
2314 contributes_to_priority (rtx_insn *next, rtx_insn *insn)
2316 /* NEXT and INSN reside in one ebb. */
2317 return BLOCK_TO_BB (BLOCK_NUM (next)) == BLOCK_TO_BB (BLOCK_NUM (insn));
2320 /* INSN is a JUMP_INSN. Store the set of registers that must be
2321 considered as used by this jump in USED. */
2323 static void
2324 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
2325 regset used ATTRIBUTE_UNUSED)
2327 /* Nothing to do here, since we postprocess jumps in
2328 add_branch_dependences. */
2331 /* This variable holds common_sched_info hooks and data relevant to
2332 the interblock scheduler. */
2333 static struct common_sched_info_def rgn_common_sched_info;
2336 /* This holds data for the dependence analysis relevant to
2337 the interblock scheduler. */
2338 static struct sched_deps_info_def rgn_sched_deps_info;
2340 /* This holds constant data used for initializing the above structure
2341 for the Haifa scheduler. */
2342 static const struct sched_deps_info_def rgn_const_sched_deps_info =
2344 compute_jump_reg_dependencies,
2345 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
2346 0, 0, 0
2349 /* Same as above, but for the selective scheduler. */
2350 static const struct sched_deps_info_def rgn_const_sel_sched_deps_info =
2352 compute_jump_reg_dependencies,
2353 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
2354 0, 0, 0
2357 /* Return true if scheduling INSN will trigger finish of scheduling
2358 current block. */
2359 static bool
2360 rgn_insn_finishes_block_p (rtx_insn *insn)
2362 if (INSN_BB (insn) == target_bb
2363 && sched_target_n_insns + 1 == target_n_insns)
2364 /* INSN is the last not-scheduled instruction in the current block. */
2365 return true;
2367 return false;
2370 /* Used in schedule_insns to initialize current_sched_info for scheduling
2371 regions (or single basic blocks). */
2373 static const struct haifa_sched_info rgn_const_sched_info =
2375 init_ready_list,
2376 can_schedule_ready_p,
2377 schedule_more_p,
2378 new_ready,
2379 rgn_rank,
2380 rgn_print_insn,
2381 contributes_to_priority,
2382 rgn_insn_finishes_block_p,
2384 NULL, NULL,
2385 NULL, NULL,
2386 0, 0,
2388 rgn_add_remove_insn,
2389 begin_schedule_ready,
2390 NULL,
2391 advance_target_bb,
2392 NULL, NULL,
2393 SCHED_RGN
2396 /* This variable holds the data and hooks needed to the Haifa scheduler backend
2397 for the interblock scheduler frontend. */
2398 static struct haifa_sched_info rgn_sched_info;
2400 /* Returns maximum priority that an insn was assigned to. */
2403 get_rgn_sched_max_insns_priority (void)
2405 return rgn_sched_info.sched_max_insns_priority;
2408 /* Determine if PAT sets a TARGET_CLASS_LIKELY_SPILLED_P register. */
2410 static bool
2411 sets_likely_spilled (rtx pat)
2413 bool ret = false;
2414 note_stores (pat, sets_likely_spilled_1, &ret);
2415 return ret;
2418 static void
2419 sets_likely_spilled_1 (rtx x, const_rtx pat, void *data)
2421 bool *ret = (bool *) data;
2423 if (GET_CODE (pat) == SET
2424 && REG_P (x)
2425 && HARD_REGISTER_P (x)
2426 && targetm.class_likely_spilled_p (REGNO_REG_CLASS (REGNO (x))))
2427 *ret = true;
2430 /* A bitmap to note insns that participate in any dependency. Used in
2431 add_branch_dependences. */
2432 static sbitmap insn_referenced;
2434 /* Add dependences so that branches are scheduled to run last in their
2435 block. */
2436 static void
2437 add_branch_dependences (rtx_insn *head, rtx_insn *tail)
2439 rtx_insn *insn, *last;
2441 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2442 that can throw exceptions, force them to remain in order at the end of
2443 the block by adding dependencies and giving the last a high priority.
2444 There may be notes present, and prev_head may also be a note.
2446 Branches must obviously remain at the end. Calls should remain at the
2447 end since moving them results in worse register allocation. Uses remain
2448 at the end to ensure proper register allocation.
2450 cc0 setters remain at the end because they can't be moved away from
2451 their cc0 user.
2453 Predecessors of SCHED_GROUP_P instructions at the end remain at the end.
2455 COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
2457 Insns setting TARGET_CLASS_LIKELY_SPILLED_P registers (usually return
2458 values) are not moved before reload because we can wind up with register
2459 allocation failures. */
2461 while (tail != head && DEBUG_INSN_P (tail))
2462 tail = PREV_INSN (tail);
2464 insn = tail;
2465 last = 0;
2466 while (CALL_P (insn)
2467 || JUMP_P (insn) || JUMP_TABLE_DATA_P (insn)
2468 || (NONJUMP_INSN_P (insn)
2469 && (GET_CODE (PATTERN (insn)) == USE
2470 || GET_CODE (PATTERN (insn)) == CLOBBER
2471 || can_throw_internal (insn)
2472 || (HAVE_cc0 && sets_cc0_p (PATTERN (insn)))
2473 || (!reload_completed
2474 && sets_likely_spilled (PATTERN (insn)))))
2475 || NOTE_P (insn)
2476 || (last != 0 && SCHED_GROUP_P (last)))
2478 if (!NOTE_P (insn))
2480 if (last != 0
2481 && sd_find_dep_between (insn, last, false) == NULL)
2483 if (! sched_insns_conditions_mutex_p (last, insn))
2484 add_dependence (last, insn, REG_DEP_ANTI);
2485 bitmap_set_bit (insn_referenced, INSN_LUID (insn));
2488 CANT_MOVE (insn) = 1;
2490 last = insn;
2493 /* Don't overrun the bounds of the basic block. */
2494 if (insn == head)
2495 break;
2498 insn = PREV_INSN (insn);
2499 while (insn != head && DEBUG_INSN_P (insn));
2502 /* Make sure these insns are scheduled last in their block. */
2503 insn = last;
2504 if (insn != 0)
2505 while (insn != head)
2507 insn = prev_nonnote_insn (insn);
2509 if (bitmap_bit_p (insn_referenced, INSN_LUID (insn))
2510 || DEBUG_INSN_P (insn))
2511 continue;
2513 if (! sched_insns_conditions_mutex_p (last, insn))
2514 add_dependence (last, insn, REG_DEP_ANTI);
2517 if (!targetm.have_conditional_execution ())
2518 return;
2520 /* Finally, if the block ends in a jump, and we are doing intra-block
2521 scheduling, make sure that the branch depends on any COND_EXEC insns
2522 inside the block to avoid moving the COND_EXECs past the branch insn.
2524 We only have to do this after reload, because (1) before reload there
2525 are no COND_EXEC insns, and (2) the region scheduler is an intra-block
2526 scheduler after reload.
2528 FIXME: We could in some cases move COND_EXEC insns past the branch if
2529 this scheduler would be a little smarter. Consider this code:
2531 T = [addr]
2532 C ? addr += 4
2533 !C ? X += 12
2534 C ? T += 1
2535 C ? jump foo
2537 On a target with a one cycle stall on a memory access the optimal
2538 sequence would be:
2540 T = [addr]
2541 C ? addr += 4
2542 C ? T += 1
2543 C ? jump foo
2544 !C ? X += 12
2546 We don't want to put the 'X += 12' before the branch because it just
2547 wastes a cycle of execution time when the branch is taken.
2549 Note that in the example "!C" will always be true. That is another
2550 possible improvement for handling COND_EXECs in this scheduler: it
2551 could remove always-true predicates. */
2553 if (!reload_completed || ! (JUMP_P (tail) || JUMP_TABLE_DATA_P (tail)))
2554 return;
2556 insn = tail;
2557 while (insn != head)
2559 insn = PREV_INSN (insn);
2561 /* Note that we want to add this dependency even when
2562 sched_insns_conditions_mutex_p returns true. The whole point
2563 is that we _want_ this dependency, even if these insns really
2564 are independent. */
2565 if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC)
2566 add_dependence (tail, insn, REG_DEP_ANTI);
2570 /* Data structures for the computation of data dependences in a regions. We
2571 keep one `deps' structure for every basic block. Before analyzing the
2572 data dependences for a bb, its variables are initialized as a function of
2573 the variables of its predecessors. When the analysis for a bb completes,
2574 we save the contents to the corresponding bb_deps[bb] variable. */
2576 static struct deps_desc *bb_deps;
2578 static void
2579 concat_insn_mem_list (rtx_insn_list *copy_insns,
2580 rtx_expr_list *copy_mems,
2581 rtx_insn_list **old_insns_p,
2582 rtx_expr_list **old_mems_p)
2584 rtx_insn_list *new_insns = *old_insns_p;
2585 rtx_expr_list *new_mems = *old_mems_p;
2587 while (copy_insns)
2589 new_insns = alloc_INSN_LIST (copy_insns->insn (), new_insns);
2590 new_mems = alloc_EXPR_LIST (VOIDmode, copy_mems->element (), new_mems);
2591 copy_insns = copy_insns->next ();
2592 copy_mems = copy_mems->next ();
2595 *old_insns_p = new_insns;
2596 *old_mems_p = new_mems;
2599 /* Join PRED_DEPS to the SUCC_DEPS. */
2600 void
2601 deps_join (struct deps_desc *succ_deps, struct deps_desc *pred_deps)
2603 unsigned reg;
2604 reg_set_iterator rsi;
2606 /* The reg_last lists are inherited by successor. */
2607 EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi)
2609 struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
2610 struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
2612 succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
2613 succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
2614 succ_rl->implicit_sets
2615 = concat_INSN_LIST (pred_rl->implicit_sets, succ_rl->implicit_sets);
2616 succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
2617 succ_rl->clobbers);
2618 succ_rl->uses_length += pred_rl->uses_length;
2619 succ_rl->clobbers_length += pred_rl->clobbers_length;
2621 IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
2623 /* Mem read/write lists are inherited by successor. */
2624 concat_insn_mem_list (pred_deps->pending_read_insns,
2625 pred_deps->pending_read_mems,
2626 &succ_deps->pending_read_insns,
2627 &succ_deps->pending_read_mems);
2628 concat_insn_mem_list (pred_deps->pending_write_insns,
2629 pred_deps->pending_write_mems,
2630 &succ_deps->pending_write_insns,
2631 &succ_deps->pending_write_mems);
2633 succ_deps->pending_jump_insns
2634 = concat_INSN_LIST (pred_deps->pending_jump_insns,
2635 succ_deps->pending_jump_insns);
2636 succ_deps->last_pending_memory_flush
2637 = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
2638 succ_deps->last_pending_memory_flush);
2640 succ_deps->pending_read_list_length += pred_deps->pending_read_list_length;
2641 succ_deps->pending_write_list_length += pred_deps->pending_write_list_length;
2642 succ_deps->pending_flush_length += pred_deps->pending_flush_length;
2644 /* last_function_call is inherited by successor. */
2645 succ_deps->last_function_call
2646 = concat_INSN_LIST (pred_deps->last_function_call,
2647 succ_deps->last_function_call);
2649 /* last_function_call_may_noreturn is inherited by successor. */
2650 succ_deps->last_function_call_may_noreturn
2651 = concat_INSN_LIST (pred_deps->last_function_call_may_noreturn,
2652 succ_deps->last_function_call_may_noreturn);
2654 /* sched_before_next_call is inherited by successor. */
2655 succ_deps->sched_before_next_call
2656 = concat_INSN_LIST (pred_deps->sched_before_next_call,
2657 succ_deps->sched_before_next_call);
2660 /* After computing the dependencies for block BB, propagate the dependencies
2661 found in TMP_DEPS to the successors of the block. */
2662 static void
2663 propagate_deps (int bb, struct deps_desc *pred_deps)
2665 basic_block block = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb));
2666 edge_iterator ei;
2667 edge e;
2669 /* bb's structures are inherited by its successors. */
2670 FOR_EACH_EDGE (e, ei, block->succs)
2672 /* Only bbs "below" bb, in the same region, are interesting. */
2673 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2674 || CONTAINING_RGN (block->index) != CONTAINING_RGN (e->dest->index)
2675 || BLOCK_TO_BB (e->dest->index) <= bb)
2676 continue;
2678 deps_join (bb_deps + BLOCK_TO_BB (e->dest->index), pred_deps);
2681 /* These lists should point to the right place, for correct
2682 freeing later. */
2683 bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
2684 bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
2685 bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
2686 bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
2687 bb_deps[bb].pending_jump_insns = pred_deps->pending_jump_insns;
2689 /* Can't allow these to be freed twice. */
2690 pred_deps->pending_read_insns = 0;
2691 pred_deps->pending_read_mems = 0;
2692 pred_deps->pending_write_insns = 0;
2693 pred_deps->pending_write_mems = 0;
2694 pred_deps->pending_jump_insns = 0;
2697 /* Compute dependences inside bb. In a multiple blocks region:
2698 (1) a bb is analyzed after its predecessors, and (2) the lists in
2699 effect at the end of bb (after analyzing for bb) are inherited by
2700 bb's successors.
2702 Specifically for reg-reg data dependences, the block insns are
2703 scanned by sched_analyze () top-to-bottom. Three lists are
2704 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2705 reg_last[].implicit_sets for implicit hard register DEFs, and
2706 reg_last[].uses for register USEs.
2708 When analysis is completed for bb, we update for its successors:
2709 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2710 ; - IMPLICIT_DEFS[succ] = Union (IMPLICIT_DEFS [succ], IMPLICIT_DEFS [bb])
2711 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2713 The mechanism for computing mem-mem data dependence is very
2714 similar, and the result is interblock dependences in the region. */
2716 static void
2717 compute_block_dependences (int bb)
2719 rtx_insn *head, *tail;
2720 struct deps_desc tmp_deps;
2722 tmp_deps = bb_deps[bb];
2724 /* Do the analysis for this block. */
2725 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2726 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2728 sched_analyze (&tmp_deps, head, tail);
2730 /* Selective scheduling handles control dependencies by itself. */
2731 if (!sel_sched_p ())
2732 add_branch_dependences (head, tail);
2734 if (current_nr_blocks > 1)
2735 propagate_deps (bb, &tmp_deps);
2737 /* Free up the INSN_LISTs. */
2738 free_deps (&tmp_deps);
2740 if (targetm.sched.dependencies_evaluation_hook)
2741 targetm.sched.dependencies_evaluation_hook (head, tail);
2744 /* Free dependencies of instructions inside BB. */
2745 static void
2746 free_block_dependencies (int bb)
2748 rtx_insn *head;
2749 rtx_insn *tail;
2751 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2753 if (no_real_insns_p (head, tail))
2754 return;
2756 sched_free_deps (head, tail, true);
2759 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2760 them to the unused_*_list variables, so that they can be reused. */
2762 static void
2763 free_pending_lists (void)
2765 int bb;
2767 for (bb = 0; bb < current_nr_blocks; bb++)
2769 free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
2770 free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
2771 free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
2772 free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
2773 free_INSN_LIST_list (&bb_deps[bb].pending_jump_insns);
2777 /* Print dependences for debugging starting from FROM_BB.
2778 Callable from debugger. */
2779 /* Print dependences for debugging starting from FROM_BB.
2780 Callable from debugger. */
2781 DEBUG_FUNCTION void
2782 debug_rgn_dependencies (int from_bb)
2784 int bb;
2786 fprintf (sched_dump,
2787 ";; --------------- forward dependences: ------------ \n");
2789 for (bb = from_bb; bb < current_nr_blocks; bb++)
2791 rtx_insn *head, *tail;
2793 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2794 fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
2795 BB_TO_BLOCK (bb), bb);
2797 debug_dependencies (head, tail);
2801 /* Print dependencies information for instructions between HEAD and TAIL.
2802 ??? This function would probably fit best in haifa-sched.c. */
2803 void debug_dependencies (rtx_insn *head, rtx_insn *tail)
2805 rtx_insn *insn;
2806 rtx_insn *next_tail = NEXT_INSN (tail);
2808 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2809 "insn", "code", "bb", "dep", "prio", "cost",
2810 "reservation");
2811 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2812 "----", "----", "--", "---", "----", "----",
2813 "-----------");
2815 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2817 if (! INSN_P (insn))
2819 int n;
2820 fprintf (sched_dump, ";; %6d ", INSN_UID (insn));
2821 if (NOTE_P (insn))
2823 n = NOTE_KIND (insn);
2824 fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
2826 else
2827 fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
2828 continue;
2831 fprintf (sched_dump,
2832 ";; %s%5d%6d%6d%6d%6d%6d ",
2833 (SCHED_GROUP_P (insn) ? "+" : " "),
2834 INSN_UID (insn),
2835 INSN_CODE (insn),
2836 BLOCK_NUM (insn),
2837 sched_emulate_haifa_p ? -1 : sd_lists_size (insn, SD_LIST_BACK),
2838 (sel_sched_p () ? (sched_emulate_haifa_p ? -1
2839 : INSN_PRIORITY (insn))
2840 : INSN_PRIORITY (insn)),
2841 (sel_sched_p () ? (sched_emulate_haifa_p ? -1
2842 : insn_cost (insn))
2843 : insn_cost (insn)));
2845 if (recog_memoized (insn) < 0)
2846 fprintf (sched_dump, "nothing");
2847 else
2848 print_reservation (sched_dump, insn);
2850 fprintf (sched_dump, "\t: ");
2852 sd_iterator_def sd_it;
2853 dep_t dep;
2855 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
2856 fprintf (sched_dump, "%d%s%s ", INSN_UID (DEP_CON (dep)),
2857 DEP_NONREG (dep) ? "n" : "",
2858 DEP_MULTIPLE (dep) ? "m" : "");
2860 fprintf (sched_dump, "\n");
2863 fprintf (sched_dump, "\n");
2866 /* Dump dependency graph for the current region to a file using dot syntax. */
2868 void
2869 dump_rgn_dependencies_dot (FILE *file)
2871 rtx_insn *head, *tail, *con, *pro;
2872 sd_iterator_def sd_it;
2873 dep_t dep;
2874 int bb;
2875 pretty_printer pp;
2877 pp.buffer->stream = file;
2878 pp_printf (&pp, "digraph SchedDG {\n");
2880 for (bb = 0; bb < current_nr_blocks; ++bb)
2882 /* Begin subgraph (basic block). */
2883 pp_printf (&pp, "subgraph cluster_block_%d {\n", bb);
2884 pp_printf (&pp, "\t" "color=blue;" "\n");
2885 pp_printf (&pp, "\t" "style=bold;" "\n");
2886 pp_printf (&pp, "\t" "label=\"BB #%d\";\n", BB_TO_BLOCK (bb));
2888 /* Setup head and tail (no support for EBBs). */
2889 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2890 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2891 tail = NEXT_INSN (tail);
2893 /* Dump all insns. */
2894 for (con = head; con != tail; con = NEXT_INSN (con))
2896 if (!INSN_P (con))
2897 continue;
2899 /* Pretty print the insn. */
2900 pp_printf (&pp, "\t%d [label=\"{", INSN_UID (con));
2901 pp_write_text_to_stream (&pp);
2902 print_insn (&pp, con, /*verbose=*/false);
2903 pp_write_text_as_dot_label_to_stream (&pp, /*for_record=*/true);
2904 pp_write_text_to_stream (&pp);
2906 /* Dump instruction attributes. */
2907 pp_printf (&pp, "|{ uid:%d | luid:%d | prio:%d }}\",shape=record]\n",
2908 INSN_UID (con), INSN_LUID (con), INSN_PRIORITY (con));
2910 /* Dump all deps. */
2911 FOR_EACH_DEP (con, SD_LIST_BACK, sd_it, dep)
2913 int weight = 0;
2914 const char *color;
2915 pro = DEP_PRO (dep);
2917 switch (DEP_TYPE (dep))
2919 case REG_DEP_TRUE:
2920 color = "black";
2921 weight = 1;
2922 break;
2923 case REG_DEP_OUTPUT:
2924 case REG_DEP_ANTI:
2925 color = "orange";
2926 break;
2927 case REG_DEP_CONTROL:
2928 color = "blue";
2929 break;
2930 default:
2931 gcc_unreachable ();
2934 pp_printf (&pp, "\t%d -> %d [color=%s",
2935 INSN_UID (pro), INSN_UID (con), color);
2936 if (int cost = dep_cost (dep))
2937 pp_printf (&pp, ",label=%d", cost);
2938 pp_printf (&pp, ",weight=%d", weight);
2939 pp_printf (&pp, "];\n");
2942 pp_printf (&pp, "}\n");
2945 pp_printf (&pp, "}\n");
2946 pp_flush (&pp);
2949 /* Dump dependency graph for the current region to a file using dot syntax. */
2951 DEBUG_FUNCTION void
2952 dump_rgn_dependencies_dot (const char *fname)
2954 FILE *fp;
2956 fp = fopen (fname, "w");
2957 if (!fp)
2959 perror ("fopen");
2960 return;
2963 dump_rgn_dependencies_dot (fp);
2964 fclose (fp);
2968 /* Returns true if all the basic blocks of the current region have
2969 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
2970 bool
2971 sched_is_disabled_for_current_region_p (void)
2973 int bb;
2975 for (bb = 0; bb < current_nr_blocks; bb++)
2976 if (!(BASIC_BLOCK_FOR_FN (cfun,
2977 BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE))
2978 return false;
2980 return true;
2983 /* Free all region dependencies saved in INSN_BACK_DEPS and
2984 INSN_RESOLVED_BACK_DEPS. The Haifa scheduler does this on the fly
2985 when scheduling, so this function is supposed to be called from
2986 the selective scheduling only. */
2987 void
2988 free_rgn_deps (void)
2990 int bb;
2992 for (bb = 0; bb < current_nr_blocks; bb++)
2994 rtx_insn *head, *tail;
2996 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2997 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2999 sched_free_deps (head, tail, false);
3003 static int rgn_n_insns;
3005 /* Compute insn priority for a current region. */
3006 void
3007 compute_priorities (void)
3009 int bb;
3011 current_sched_info->sched_max_insns_priority = 0;
3012 for (bb = 0; bb < current_nr_blocks; bb++)
3014 rtx_insn *head, *tail;
3016 gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
3017 get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
3019 if (no_real_insns_p (head, tail))
3020 continue;
3022 rgn_n_insns += set_priorities (head, tail);
3024 current_sched_info->sched_max_insns_priority++;
3027 /* (Re-)initialize the arrays of DFA states at the end of each basic block.
3029 SAVED_LAST_BASIC_BLOCK is the previous length of the arrays. It must be
3030 zero for the first call to this function, to allocate the arrays for the
3031 first time.
3033 This function is called once during initialization of the scheduler, and
3034 called again to resize the arrays if new basic blocks have been created,
3035 for example for speculation recovery code. */
3037 static void
3038 realloc_bb_state_array (int saved_last_basic_block)
3040 char *old_bb_state_array = bb_state_array;
3041 size_t lbb = (size_t) last_basic_block_for_fn (cfun);
3042 size_t slbb = (size_t) saved_last_basic_block;
3044 /* Nothing to do if nothing changed since the last time this was called. */
3045 if (saved_last_basic_block == last_basic_block_for_fn (cfun))
3046 return;
3048 /* The selective scheduler doesn't use the state arrays. */
3049 if (sel_sched_p ())
3051 gcc_assert (bb_state_array == NULL && bb_state == NULL);
3052 return;
3055 gcc_checking_assert (saved_last_basic_block == 0
3056 || (bb_state_array != NULL && bb_state != NULL));
3058 bb_state_array = XRESIZEVEC (char, bb_state_array, lbb * dfa_state_size);
3059 bb_state = XRESIZEVEC (state_t, bb_state, lbb);
3061 /* If BB_STATE_ARRAY has moved, fixup all the state pointers array.
3062 Otherwise only fixup the newly allocated ones. For the state
3063 array itself, only initialize the new entries. */
3064 bool bb_state_array_moved = (bb_state_array != old_bb_state_array);
3065 for (size_t i = bb_state_array_moved ? 0 : slbb; i < lbb; i++)
3066 bb_state[i] = (state_t) (bb_state_array + i * dfa_state_size);
3067 for (size_t i = slbb; i < lbb; i++)
3068 state_reset (bb_state[i]);
3071 /* Free the arrays of DFA states at the end of each basic block. */
3073 static void
3074 free_bb_state_array (void)
3076 free (bb_state_array);
3077 free (bb_state);
3078 bb_state_array = NULL;
3079 bb_state = NULL;
3082 /* Schedule a region. A region is either an inner loop, a loop-free
3083 subroutine, or a single basic block. Each bb in the region is
3084 scheduled after its flow predecessors. */
3086 static void
3087 schedule_region (int rgn)
3089 int bb;
3090 int sched_rgn_n_insns = 0;
3092 rgn_n_insns = 0;
3094 /* Do not support register pressure sensitive scheduling for the new regions
3095 as we don't update the liveness info for them. */
3096 if (sched_pressure != SCHED_PRESSURE_NONE
3097 && rgn >= nr_regions_initial)
3099 free_global_sched_pressure_data ();
3100 sched_pressure = SCHED_PRESSURE_NONE;
3103 rgn_setup_region (rgn);
3105 /* Don't schedule region that is marked by
3106 NOTE_DISABLE_SCHED_OF_BLOCK. */
3107 if (sched_is_disabled_for_current_region_p ())
3108 return;
3110 sched_rgn_compute_dependencies (rgn);
3112 sched_rgn_local_init (rgn);
3114 /* Set priorities. */
3115 compute_priorities ();
3117 sched_extend_ready_list (rgn_n_insns);
3119 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
3121 sched_init_region_reg_pressure_info ();
3122 for (bb = 0; bb < current_nr_blocks; bb++)
3124 basic_block first_bb, last_bb;
3125 rtx_insn *head, *tail;
3127 first_bb = EBB_FIRST_BB (bb);
3128 last_bb = EBB_LAST_BB (bb);
3130 get_ebb_head_tail (first_bb, last_bb, &head, &tail);
3132 if (no_real_insns_p (head, tail))
3134 gcc_assert (first_bb == last_bb);
3135 continue;
3137 sched_setup_bb_reg_pressure_info (first_bb, PREV_INSN (head));
3141 /* Now we can schedule all blocks. */
3142 for (bb = 0; bb < current_nr_blocks; bb++)
3144 basic_block first_bb, last_bb, curr_bb;
3145 rtx_insn *head, *tail;
3147 first_bb = EBB_FIRST_BB (bb);
3148 last_bb = EBB_LAST_BB (bb);
3150 get_ebb_head_tail (first_bb, last_bb, &head, &tail);
3152 if (no_real_insns_p (head, tail))
3154 gcc_assert (first_bb == last_bb);
3155 continue;
3158 current_sched_info->prev_head = PREV_INSN (head);
3159 current_sched_info->next_tail = NEXT_INSN (tail);
3161 remove_notes (head, tail);
3163 unlink_bb_notes (first_bb, last_bb);
3165 target_bb = bb;
3167 gcc_assert (flag_schedule_interblock || current_nr_blocks == 1);
3168 current_sched_info->queue_must_finish_empty = current_nr_blocks == 1;
3170 curr_bb = first_bb;
3171 if (dbg_cnt (sched_block))
3173 edge f;
3174 int saved_last_basic_block = last_basic_block_for_fn (cfun);
3176 schedule_block (&curr_bb, bb_state[first_bb->index]);
3177 gcc_assert (EBB_FIRST_BB (bb) == first_bb);
3178 sched_rgn_n_insns += sched_n_insns;
3179 realloc_bb_state_array (saved_last_basic_block);
3180 f = find_fallthru_edge (last_bb->succs);
3181 if (f && f->probability * 100 / REG_BR_PROB_BASE >=
3182 PARAM_VALUE (PARAM_SCHED_STATE_EDGE_PROB_CUTOFF))
3184 memcpy (bb_state[f->dest->index], curr_state,
3185 dfa_state_size);
3186 if (sched_verbose >= 5)
3187 fprintf (sched_dump, "saving state for edge %d->%d\n",
3188 f->src->index, f->dest->index);
3191 else
3193 sched_rgn_n_insns += rgn_n_insns;
3196 /* Clean up. */
3197 if (current_nr_blocks > 1)
3198 free_trg_info ();
3201 /* Sanity check: verify that all region insns were scheduled. */
3202 gcc_assert (sched_rgn_n_insns == rgn_n_insns);
3204 sched_finish_ready_list ();
3206 /* Done with this region. */
3207 sched_rgn_local_finish ();
3209 /* Free dependencies. */
3210 for (bb = 0; bb < current_nr_blocks; ++bb)
3211 free_block_dependencies (bb);
3213 gcc_assert (haifa_recovery_bb_ever_added_p
3214 || deps_pools_are_empty_p ());
3217 /* Initialize data structures for region scheduling. */
3219 void
3220 sched_rgn_init (bool single_blocks_p)
3222 min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE)
3223 / 100);
3225 nr_inter = 0;
3226 nr_spec = 0;
3228 extend_regions ();
3230 CONTAINING_RGN (ENTRY_BLOCK) = -1;
3231 CONTAINING_RGN (EXIT_BLOCK) = -1;
3233 realloc_bb_state_array (0);
3235 /* Compute regions for scheduling. */
3236 if (single_blocks_p
3237 || n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS + 1
3238 || !flag_schedule_interblock
3239 || is_cfg_nonregular ())
3241 find_single_block_region (sel_sched_p ());
3243 else
3245 /* Compute the dominators and post dominators. */
3246 if (!sel_sched_p ())
3247 calculate_dominance_info (CDI_DOMINATORS);
3249 /* Find regions. */
3250 find_rgns ();
3252 if (sched_verbose >= 3)
3253 debug_regions ();
3255 /* For now. This will move as more and more of haifa is converted
3256 to using the cfg code. */
3257 if (!sel_sched_p ())
3258 free_dominance_info (CDI_DOMINATORS);
3261 gcc_assert (0 < nr_regions && nr_regions <= n_basic_blocks_for_fn (cfun));
3263 RGN_BLOCKS (nr_regions) = (RGN_BLOCKS (nr_regions - 1) +
3264 RGN_NR_BLOCKS (nr_regions - 1));
3265 nr_regions_initial = nr_regions;
3268 /* Free data structures for region scheduling. */
3269 void
3270 sched_rgn_finish (void)
3272 free_bb_state_array ();
3274 /* Reposition the prologue and epilogue notes in case we moved the
3275 prologue/epilogue insns. */
3276 if (reload_completed)
3277 reposition_prologue_and_epilogue_notes ();
3279 if (sched_verbose)
3281 if (reload_completed == 0
3282 && flag_schedule_interblock)
3284 fprintf (sched_dump,
3285 "\n;; Procedure interblock/speculative motions == %d/%d \n",
3286 nr_inter, nr_spec);
3288 else
3289 gcc_assert (nr_inter <= 0);
3290 fprintf (sched_dump, "\n\n");
3293 nr_regions = 0;
3295 free (rgn_table);
3296 rgn_table = NULL;
3298 free (rgn_bb_table);
3299 rgn_bb_table = NULL;
3301 free (block_to_bb);
3302 block_to_bb = NULL;
3304 free (containing_rgn);
3305 containing_rgn = NULL;
3307 free (ebb_head);
3308 ebb_head = NULL;
3311 /* Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
3312 point to the region RGN. */
3313 void
3314 rgn_setup_region (int rgn)
3316 int bb;
3318 /* Set variables for the current region. */
3319 current_nr_blocks = RGN_NR_BLOCKS (rgn);
3320 current_blocks = RGN_BLOCKS (rgn);
3322 /* EBB_HEAD is a region-scope structure. But we realloc it for
3323 each region to save time/memory/something else.
3324 See comments in add_block1, for what reasons we allocate +1 element. */
3325 ebb_head = XRESIZEVEC (int, ebb_head, current_nr_blocks + 1);
3326 for (bb = 0; bb <= current_nr_blocks; bb++)
3327 ebb_head[bb] = current_blocks + bb;
3330 /* Compute instruction dependencies in region RGN. */
3331 void
3332 sched_rgn_compute_dependencies (int rgn)
3334 if (!RGN_DONT_CALC_DEPS (rgn))
3336 int bb;
3338 if (sel_sched_p ())
3339 sched_emulate_haifa_p = 1;
3341 init_deps_global ();
3343 /* Initializations for region data dependence analysis. */
3344 bb_deps = XNEWVEC (struct deps_desc, current_nr_blocks);
3345 for (bb = 0; bb < current_nr_blocks; bb++)
3346 init_deps (bb_deps + bb, false);
3348 /* Initialize bitmap used in add_branch_dependences. */
3349 insn_referenced = sbitmap_alloc (sched_max_luid);
3350 bitmap_clear (insn_referenced);
3352 /* Compute backward dependencies. */
3353 for (bb = 0; bb < current_nr_blocks; bb++)
3354 compute_block_dependences (bb);
3356 sbitmap_free (insn_referenced);
3357 free_pending_lists ();
3358 finish_deps_global ();
3359 free (bb_deps);
3361 /* We don't want to recalculate this twice. */
3362 RGN_DONT_CALC_DEPS (rgn) = 1;
3364 if (sel_sched_p ())
3365 sched_emulate_haifa_p = 0;
3367 else
3368 /* (This is a recovery block. It is always a single block region.)
3369 OR (We use selective scheduling.) */
3370 gcc_assert (current_nr_blocks == 1 || sel_sched_p ());
3373 /* Init region data structures. Returns true if this region should
3374 not be scheduled. */
3375 void
3376 sched_rgn_local_init (int rgn)
3378 int bb;
3380 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
3381 if (current_nr_blocks > 1)
3383 basic_block block;
3384 edge e;
3385 edge_iterator ei;
3387 prob = XNEWVEC (int, current_nr_blocks);
3389 dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
3390 bitmap_vector_clear (dom, current_nr_blocks);
3392 /* Use ->aux to implement EDGE_TO_BIT mapping. */
3393 rgn_nr_edges = 0;
3394 FOR_EACH_BB_FN (block, cfun)
3396 if (CONTAINING_RGN (block->index) != rgn)
3397 continue;
3398 FOR_EACH_EDGE (e, ei, block->succs)
3399 SET_EDGE_TO_BIT (e, rgn_nr_edges++);
3402 rgn_edges = XNEWVEC (edge, rgn_nr_edges);
3403 rgn_nr_edges = 0;
3404 FOR_EACH_BB_FN (block, cfun)
3406 if (CONTAINING_RGN (block->index) != rgn)
3407 continue;
3408 FOR_EACH_EDGE (e, ei, block->succs)
3409 rgn_edges[rgn_nr_edges++] = e;
3412 /* Split edges. */
3413 pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
3414 bitmap_vector_clear (pot_split, current_nr_blocks);
3415 ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
3416 bitmap_vector_clear (ancestor_edges, current_nr_blocks);
3418 /* Compute probabilities, dominators, split_edges. */
3419 for (bb = 0; bb < current_nr_blocks; bb++)
3420 compute_dom_prob_ps (bb);
3422 /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
3423 /* We don't need them anymore. But we want to avoid duplication of
3424 aux fields in the newly created edges. */
3425 FOR_EACH_BB_FN (block, cfun)
3427 if (CONTAINING_RGN (block->index) != rgn)
3428 continue;
3429 FOR_EACH_EDGE (e, ei, block->succs)
3430 e->aux = NULL;
3435 /* Free data computed for the finished region. */
3436 void
3437 sched_rgn_local_free (void)
3439 free (prob);
3440 sbitmap_vector_free (dom);
3441 sbitmap_vector_free (pot_split);
3442 sbitmap_vector_free (ancestor_edges);
3443 free (rgn_edges);
3446 /* Free data computed for the finished region. */
3447 void
3448 sched_rgn_local_finish (void)
3450 if (current_nr_blocks > 1 && !sel_sched_p ())
3452 sched_rgn_local_free ();
3456 /* Setup scheduler infos. */
3457 void
3458 rgn_setup_common_sched_info (void)
3460 memcpy (&rgn_common_sched_info, &haifa_common_sched_info,
3461 sizeof (rgn_common_sched_info));
3463 rgn_common_sched_info.fix_recovery_cfg = rgn_fix_recovery_cfg;
3464 rgn_common_sched_info.add_block = rgn_add_block;
3465 rgn_common_sched_info.estimate_number_of_insns
3466 = rgn_estimate_number_of_insns;
3467 rgn_common_sched_info.sched_pass_id = SCHED_RGN_PASS;
3469 common_sched_info = &rgn_common_sched_info;
3472 /* Setup all *_sched_info structures (for the Haifa frontend
3473 and for the dependence analysis) in the interblock scheduler. */
3474 void
3475 rgn_setup_sched_infos (void)
3477 if (!sel_sched_p ())
3478 memcpy (&rgn_sched_deps_info, &rgn_const_sched_deps_info,
3479 sizeof (rgn_sched_deps_info));
3480 else
3481 memcpy (&rgn_sched_deps_info, &rgn_const_sel_sched_deps_info,
3482 sizeof (rgn_sched_deps_info));
3484 sched_deps_info = &rgn_sched_deps_info;
3486 memcpy (&rgn_sched_info, &rgn_const_sched_info, sizeof (rgn_sched_info));
3487 current_sched_info = &rgn_sched_info;
3490 /* The one entry point in this file. */
3491 void
3492 schedule_insns (void)
3494 int rgn;
3496 /* Taking care of this degenerate case makes the rest of
3497 this code simpler. */
3498 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
3499 return;
3501 rgn_setup_common_sched_info ();
3502 rgn_setup_sched_infos ();
3504 haifa_sched_init ();
3505 sched_rgn_init (reload_completed);
3507 bitmap_initialize (&not_in_df, 0);
3508 bitmap_clear (&not_in_df);
3510 /* Schedule every region in the subroutine. */
3511 for (rgn = 0; rgn < nr_regions; rgn++)
3512 if (dbg_cnt (sched_region))
3513 schedule_region (rgn);
3515 /* Clean up. */
3516 sched_rgn_finish ();
3517 bitmap_clear (&not_in_df);
3519 haifa_sched_finish ();
3522 /* INSN has been added to/removed from current region. */
3523 static void
3524 rgn_add_remove_insn (rtx_insn *insn, int remove_p)
3526 if (!remove_p)
3527 rgn_n_insns++;
3528 else
3529 rgn_n_insns--;
3531 if (INSN_BB (insn) == target_bb)
3533 if (!remove_p)
3534 target_n_insns++;
3535 else
3536 target_n_insns--;
3540 /* Extend internal data structures. */
3541 void
3542 extend_regions (void)
3544 rgn_table = XRESIZEVEC (region, rgn_table, n_basic_blocks_for_fn (cfun));
3545 rgn_bb_table = XRESIZEVEC (int, rgn_bb_table,
3546 n_basic_blocks_for_fn (cfun));
3547 block_to_bb = XRESIZEVEC (int, block_to_bb,
3548 last_basic_block_for_fn (cfun));
3549 containing_rgn = XRESIZEVEC (int, containing_rgn,
3550 last_basic_block_for_fn (cfun));
3553 void
3554 rgn_make_new_region_out_of_new_block (basic_block bb)
3556 int i;
3558 i = RGN_BLOCKS (nr_regions);
3559 /* I - first free position in rgn_bb_table. */
3561 rgn_bb_table[i] = bb->index;
3562 RGN_NR_BLOCKS (nr_regions) = 1;
3563 RGN_HAS_REAL_EBB (nr_regions) = 0;
3564 RGN_DONT_CALC_DEPS (nr_regions) = 0;
3565 CONTAINING_RGN (bb->index) = nr_regions;
3566 BLOCK_TO_BB (bb->index) = 0;
3568 nr_regions++;
3570 RGN_BLOCKS (nr_regions) = i + 1;
3573 /* BB was added to ebb after AFTER. */
3574 static void
3575 rgn_add_block (basic_block bb, basic_block after)
3577 extend_regions ();
3578 bitmap_set_bit (&not_in_df, bb->index);
3580 if (after == 0 || after == EXIT_BLOCK_PTR_FOR_FN (cfun))
3582 rgn_make_new_region_out_of_new_block (bb);
3583 RGN_DONT_CALC_DEPS (nr_regions - 1) = (after
3584 == EXIT_BLOCK_PTR_FOR_FN (cfun));
3586 else
3588 int i, pos;
3590 /* We need to fix rgn_table, block_to_bb, containing_rgn
3591 and ebb_head. */
3593 BLOCK_TO_BB (bb->index) = BLOCK_TO_BB (after->index);
3595 /* We extend ebb_head to one more position to
3596 easily find the last position of the last ebb in
3597 the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
3598 is _always_ valid for access. */
3600 i = BLOCK_TO_BB (after->index) + 1;
3601 pos = ebb_head[i] - 1;
3602 /* Now POS is the index of the last block in the region. */
3604 /* Find index of basic block AFTER. */
3605 for (; rgn_bb_table[pos] != after->index; pos--)
3608 pos++;
3609 gcc_assert (pos > ebb_head[i - 1]);
3611 /* i - ebb right after "AFTER". */
3612 /* ebb_head[i] - VALID. */
3614 /* Source position: ebb_head[i]
3615 Destination position: ebb_head[i] + 1
3616 Last position:
3617 RGN_BLOCKS (nr_regions) - 1
3618 Number of elements to copy: (last_position) - (source_position) + 1
3621 memmove (rgn_bb_table + pos + 1,
3622 rgn_bb_table + pos,
3623 ((RGN_BLOCKS (nr_regions) - 1) - (pos) + 1)
3624 * sizeof (*rgn_bb_table));
3626 rgn_bb_table[pos] = bb->index;
3628 for (; i <= current_nr_blocks; i++)
3629 ebb_head [i]++;
3631 i = CONTAINING_RGN (after->index);
3632 CONTAINING_RGN (bb->index) = i;
3634 RGN_HAS_REAL_EBB (i) = 1;
3636 for (++i; i <= nr_regions; i++)
3637 RGN_BLOCKS (i)++;
3641 /* Fix internal data after interblock movement of jump instruction.
3642 For parameter meaning please refer to
3643 sched-int.h: struct sched_info: fix_recovery_cfg. */
3644 static void
3645 rgn_fix_recovery_cfg (int bbi, int check_bbi, int check_bb_nexti)
3647 int old_pos, new_pos, i;
3649 BLOCK_TO_BB (check_bb_nexti) = BLOCK_TO_BB (bbi);
3651 for (old_pos = ebb_head[BLOCK_TO_BB (check_bbi) + 1] - 1;
3652 rgn_bb_table[old_pos] != check_bb_nexti;
3653 old_pos--)
3655 gcc_assert (old_pos > ebb_head[BLOCK_TO_BB (check_bbi)]);
3657 for (new_pos = ebb_head[BLOCK_TO_BB (bbi) + 1] - 1;
3658 rgn_bb_table[new_pos] != bbi;
3659 new_pos--)
3661 new_pos++;
3662 gcc_assert (new_pos > ebb_head[BLOCK_TO_BB (bbi)]);
3664 gcc_assert (new_pos < old_pos);
3666 memmove (rgn_bb_table + new_pos + 1,
3667 rgn_bb_table + new_pos,
3668 (old_pos - new_pos) * sizeof (*rgn_bb_table));
3670 rgn_bb_table[new_pos] = check_bb_nexti;
3672 for (i = BLOCK_TO_BB (bbi) + 1; i <= BLOCK_TO_BB (check_bbi); i++)
3673 ebb_head[i]++;
3676 /* Return next block in ebb chain. For parameter meaning please refer to
3677 sched-int.h: struct sched_info: advance_target_bb. */
3678 static basic_block
3679 advance_target_bb (basic_block bb, rtx_insn *insn)
3681 if (insn)
3682 return 0;
3684 gcc_assert (BLOCK_TO_BB (bb->index) == target_bb
3685 && BLOCK_TO_BB (bb->next_bb->index) == target_bb);
3686 return bb->next_bb;
3689 #endif
3691 /* Run instruction scheduler. */
3692 static unsigned int
3693 rest_of_handle_live_range_shrinkage (void)
3695 #ifdef INSN_SCHEDULING
3696 int saved;
3698 initialize_live_range_shrinkage ();
3699 saved = flag_schedule_interblock;
3700 flag_schedule_interblock = false;
3701 schedule_insns ();
3702 flag_schedule_interblock = saved;
3703 finish_live_range_shrinkage ();
3704 #endif
3705 return 0;
3708 /* Run instruction scheduler. */
3709 static unsigned int
3710 rest_of_handle_sched (void)
3712 #ifdef INSN_SCHEDULING
3713 if (flag_selective_scheduling
3714 && ! maybe_skip_selective_scheduling ())
3715 run_selective_scheduling ();
3716 else
3717 schedule_insns ();
3718 #endif
3719 return 0;
3722 /* Run second scheduling pass after reload. */
3723 static unsigned int
3724 rest_of_handle_sched2 (void)
3726 #ifdef INSN_SCHEDULING
3727 if (flag_selective_scheduling2
3728 && ! maybe_skip_selective_scheduling ())
3729 run_selective_scheduling ();
3730 else
3732 /* Do control and data sched analysis again,
3733 and write some more of the results to dump file. */
3734 if (flag_sched2_use_superblocks)
3735 schedule_ebbs ();
3736 else
3737 schedule_insns ();
3739 #endif
3740 return 0;
3743 static unsigned int
3744 rest_of_handle_sched_fusion (void)
3746 #ifdef INSN_SCHEDULING
3747 sched_fusion = true;
3748 schedule_insns ();
3749 sched_fusion = false;
3750 #endif
3751 return 0;
3754 namespace {
3756 const pass_data pass_data_live_range_shrinkage =
3758 RTL_PASS, /* type */
3759 "lr_shrinkage", /* name */
3760 OPTGROUP_NONE, /* optinfo_flags */
3761 TV_LIVE_RANGE_SHRINKAGE, /* tv_id */
3762 0, /* properties_required */
3763 0, /* properties_provided */
3764 0, /* properties_destroyed */
3765 0, /* todo_flags_start */
3766 TODO_df_finish, /* todo_flags_finish */
3769 class pass_live_range_shrinkage : public rtl_opt_pass
3771 public:
3772 pass_live_range_shrinkage(gcc::context *ctxt)
3773 : rtl_opt_pass(pass_data_live_range_shrinkage, ctxt)
3776 /* opt_pass methods: */
3777 virtual bool gate (function *)
3779 #ifdef INSN_SCHEDULING
3780 return flag_live_range_shrinkage;
3781 #else
3782 return 0;
3783 #endif
3786 virtual unsigned int execute (function *)
3788 return rest_of_handle_live_range_shrinkage ();
3791 }; // class pass_live_range_shrinkage
3793 } // anon namespace
3795 rtl_opt_pass *
3796 make_pass_live_range_shrinkage (gcc::context *ctxt)
3798 return new pass_live_range_shrinkage (ctxt);
3801 namespace {
3803 const pass_data pass_data_sched =
3805 RTL_PASS, /* type */
3806 "sched1", /* name */
3807 OPTGROUP_NONE, /* optinfo_flags */
3808 TV_SCHED, /* tv_id */
3809 0, /* properties_required */
3810 0, /* properties_provided */
3811 0, /* properties_destroyed */
3812 0, /* todo_flags_start */
3813 TODO_df_finish, /* todo_flags_finish */
3816 class pass_sched : public rtl_opt_pass
3818 public:
3819 pass_sched (gcc::context *ctxt)
3820 : rtl_opt_pass (pass_data_sched, ctxt)
3823 /* opt_pass methods: */
3824 virtual bool gate (function *);
3825 virtual unsigned int execute (function *) { return rest_of_handle_sched (); }
3827 }; // class pass_sched
3829 bool
3830 pass_sched::gate (function *)
3832 #ifdef INSN_SCHEDULING
3833 return optimize > 0 && flag_schedule_insns && dbg_cnt (sched_func);
3834 #else
3835 return 0;
3836 #endif
3839 } // anon namespace
3841 rtl_opt_pass *
3842 make_pass_sched (gcc::context *ctxt)
3844 return new pass_sched (ctxt);
3847 namespace {
3849 const pass_data pass_data_sched2 =
3851 RTL_PASS, /* type */
3852 "sched2", /* name */
3853 OPTGROUP_NONE, /* optinfo_flags */
3854 TV_SCHED2, /* tv_id */
3855 0, /* properties_required */
3856 0, /* properties_provided */
3857 0, /* properties_destroyed */
3858 0, /* todo_flags_start */
3859 TODO_df_finish, /* todo_flags_finish */
3862 class pass_sched2 : public rtl_opt_pass
3864 public:
3865 pass_sched2 (gcc::context *ctxt)
3866 : rtl_opt_pass (pass_data_sched2, ctxt)
3869 /* opt_pass methods: */
3870 virtual bool gate (function *);
3871 virtual unsigned int execute (function *)
3873 return rest_of_handle_sched2 ();
3876 }; // class pass_sched2
3878 bool
3879 pass_sched2::gate (function *)
3881 #ifdef INSN_SCHEDULING
3882 return optimize > 0 && flag_schedule_insns_after_reload
3883 && !targetm.delay_sched2 && dbg_cnt (sched2_func);
3884 #else
3885 return 0;
3886 #endif
3889 } // anon namespace
3891 rtl_opt_pass *
3892 make_pass_sched2 (gcc::context *ctxt)
3894 return new pass_sched2 (ctxt);
3897 namespace {
3899 const pass_data pass_data_sched_fusion =
3901 RTL_PASS, /* type */
3902 "sched_fusion", /* name */
3903 OPTGROUP_NONE, /* optinfo_flags */
3904 TV_SCHED_FUSION, /* tv_id */
3905 0, /* properties_required */
3906 0, /* properties_provided */
3907 0, /* properties_destroyed */
3908 0, /* todo_flags_start */
3909 TODO_df_finish, /* todo_flags_finish */
3912 class pass_sched_fusion : public rtl_opt_pass
3914 public:
3915 pass_sched_fusion (gcc::context *ctxt)
3916 : rtl_opt_pass (pass_data_sched_fusion, ctxt)
3919 /* opt_pass methods: */
3920 virtual bool gate (function *);
3921 virtual unsigned int execute (function *)
3923 return rest_of_handle_sched_fusion ();
3926 }; // class pass_sched2
3928 bool
3929 pass_sched_fusion::gate (function *)
3931 #ifdef INSN_SCHEDULING
3932 /* Scheduling fusion relies on peephole2 to do real fusion work,
3933 so only enable it if peephole2 is in effect. */
3934 return (optimize > 0 && flag_peephole2
3935 && flag_schedule_fusion && targetm.sched.fusion_priority != NULL);
3936 #else
3937 return 0;
3938 #endif
3941 } // anon namespace
3943 rtl_opt_pass *
3944 make_pass_sched_fusion (gcc::context *ctxt)
3946 return new pass_sched_fusion (ctxt);