Line data Source code
1 : /* Instruction scheduling pass.
2 : Copyright (C) 1992-2026 Free Software Foundation, Inc.
3 : Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 : and currently maintained by, Jim Wilson (wilson@cygnus.com)
5 :
6 : This file is part of GCC.
7 :
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.
12 :
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.
17 :
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/>. */
21 :
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.
25 :
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.
29 :
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.
35 :
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. */
45 :
46 : #include "config.h"
47 : #include "system.h"
48 : #include "coretypes.h"
49 : #include "backend.h"
50 : #include "target.h"
51 : #include "rtl.h"
52 : #include "df.h"
53 : #include "memmodel.h"
54 : #include "tm_p.h"
55 : #include "insn-config.h"
56 : #include "emit-rtl.h"
57 : #include "recog.h"
58 : #include "profile.h"
59 : #include "insn-attr.h"
60 : #include "except.h"
61 : #include "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"
68 :
69 : /* Disable warnings about quoting issues in the pp_xxx calls below
70 : that (intentionally) don't follow GCC diagnostic conventions. */
71 : #if __GNUC__ >= 10
72 : # pragma GCC diagnostic push
73 : # pragma GCC diagnostic ignored "-Wformat-diag"
74 : #endif
75 :
76 : #ifdef INSN_SCHEDULING
77 :
78 : /* Some accessor macros for h_i_d members only used within this file. */
79 : #define FED_BY_SPEC_LOAD(INSN) (HID (INSN)->fed_by_spec_load)
80 : #define IS_LOAD_INSN(INSN) (HID (insn)->is_load_insn)
81 :
82 : /* nr_inter/spec counts interblock/speculative motion for the function. */
83 : static int nr_inter, nr_spec;
84 :
85 : static bool is_cfg_nonregular (void);
86 :
87 : /* Number of regions in the procedure. */
88 : int nr_regions = 0;
89 :
90 : /* Same as above before adding any new regions. */
91 : static int nr_regions_initial = 0;
92 :
93 : /* Table of region descriptions. */
94 : region *rgn_table = NULL;
95 :
96 : /* Array of lists of regions' blocks. */
97 : int *rgn_bb_table = NULL;
98 :
99 : /* Topological order of blocks in the region (if b2 is reachable from
100 : b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
101 : always referred to by either block or b, while its topological
102 : order name (in the region) is referred to by bb. */
103 : int *block_to_bb = NULL;
104 :
105 : /* The number of the region containing a block. */
106 : int *containing_rgn = NULL;
107 :
108 : /* ebb_head [i] - is index in rgn_bb_table of the head basic block of i'th ebb.
109 : Currently we can get a ebb only through splitting of currently
110 : scheduling block, therefore, we don't need ebb_head array for every region,
111 : hence, its sufficient to hold it for current one only. */
112 : int *ebb_head = NULL;
113 :
114 : /* The minimum probability of reaching a source block so that it will be
115 : considered for speculative scheduling. */
116 : static int min_spec_prob;
117 :
118 : static void find_single_block_region (bool);
119 : static void find_rgns (void);
120 : static bool too_large (int, int *, int *);
121 :
122 : /* Blocks of the current region being scheduled. */
123 : int current_nr_blocks;
124 : int current_blocks;
125 :
126 : /* A speculative motion requires checking live information on the path
127 : from 'source' to 'target'. The split blocks are those to be checked.
128 : After a speculative motion, live information should be modified in
129 : the 'update' blocks.
130 :
131 : Lists of split and update blocks for each candidate of the current
132 : target are in array bblst_table. */
133 : static basic_block *bblst_table;
134 : static int bblst_size, bblst_last;
135 :
136 : /* Arrays that hold the DFA state at the end of a basic block, to re-use
137 : as the initial state at the start of successor blocks. The BB_STATE
138 : array holds the actual DFA state, and BB_STATE_ARRAY[I] is a pointer
139 : into BB_STATE for basic block I. FIXME: This should be a vec. */
140 : static char *bb_state_array = NULL;
141 : static state_t *bb_state = NULL;
142 :
143 : /* Target info declarations.
144 :
145 : The block currently being scheduled is referred to as the "target" block,
146 : while other blocks in the region from which insns can be moved to the
147 : target are called "source" blocks. The candidate structure holds info
148 : about such sources: are they valid? Speculative? Etc. */
149 : struct bblst
150 : {
151 : basic_block *first_member;
152 : int nr_members;
153 : };
154 :
155 : struct candidate
156 : {
157 : char is_valid;
158 : char is_speculative;
159 : int src_prob;
160 : bblst split_bbs;
161 : bblst update_bbs;
162 : };
163 :
164 : static candidate *candidate_table;
165 : #define IS_VALID(src) (candidate_table[src].is_valid)
166 : #define IS_SPECULATIVE(src) (candidate_table[src].is_speculative)
167 : #define IS_SPECULATIVE_INSN(INSN) \
168 : (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
169 : #define SRC_PROB(src) ( candidate_table[src].src_prob )
170 :
171 : /* The bb being currently scheduled. */
172 : int target_bb;
173 :
174 : /* List of edges. */
175 : struct edgelst
176 : {
177 : edge *first_member;
178 : int nr_members;
179 : };
180 :
181 : static edge *edgelst_table;
182 : static int edgelst_last;
183 :
184 : static void extract_edgelst (sbitmap, edgelst *);
185 :
186 : /* Target info functions. */
187 : static void split_edges (int, int, edgelst *);
188 : static void compute_trg_info (int);
189 : void debug_candidate (int);
190 : void debug_candidates (int);
191 :
192 : /* Dominators array: dom[i] contains the sbitmap of dominators of
193 : bb i in the region. */
194 : static sbitmap *dom;
195 :
196 : /* bb 0 is the only region entry. */
197 : #define IS_RGN_ENTRY(bb) (!bb)
198 :
199 : /* Is bb_src dominated by bb_trg. */
200 : #define IS_DOMINATED(bb_src, bb_trg) \
201 : ( bitmap_bit_p (dom[bb_src], bb_trg) )
202 :
203 : /* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
204 : the probability of bb i relative to the region entry. */
205 : static int *prob;
206 :
207 : /* Bit-set of edges, where bit i stands for edge i. */
208 : typedef sbitmap edgeset;
209 :
210 : /* Number of edges in the region. */
211 : static int rgn_nr_edges;
212 :
213 : /* Array of size rgn_nr_edges. */
214 : static edge *rgn_edges;
215 :
216 : /* Mapping from each edge in the graph to its number in the rgn. */
217 : #define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
218 : #define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
219 :
220 : /* The split edges of a source bb is different for each target
221 : bb. In order to compute this efficiently, the 'potential-split edges'
222 : are computed for each bb prior to scheduling a region. This is actually
223 : the split edges of each bb relative to the region entry.
224 :
225 : pot_split[bb] is the set of potential split edges of bb. */
226 : static edgeset *pot_split;
227 :
228 : /* For every bb, a set of its ancestor edges. */
229 : static edgeset *ancestor_edges;
230 :
231 : #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
232 :
233 : /* Speculative scheduling functions. */
234 : static bool check_live_1 (int, rtx);
235 : static void update_live_1 (int, rtx);
236 : static bool is_pfree (rtx_insn *, int, int);
237 : static bool find_conditional_protection (rtx_insn *, int);
238 : static bool is_conditionally_protected (rtx_insn *, int, int);
239 : static bool is_prisky (rtx_insn *, int, int);
240 : static bool is_exception_free (rtx_insn *, int, int);
241 :
242 : static bool sets_likely_spilled (rtx);
243 : static void sets_likely_spilled_1 (rtx, const_rtx, void *);
244 : static void add_branch_dependences (rtx_insn *, rtx_insn *);
245 : static void compute_block_dependences (int);
246 :
247 : static void schedule_region (int);
248 : static void concat_insn_mem_list (rtx_insn_list *, rtx_expr_list *,
249 : rtx_insn_list **, rtx_expr_list **);
250 : static void propagate_deps (int, class deps_desc *);
251 : static void free_pending_lists (void);
252 :
253 : /* Functions for construction of the control flow graph. */
254 :
255 : /* Return true if control flow graph should not be constructed,
256 : false otherwise.
257 :
258 : We decide not to build the control flow graph if there is possibly more
259 : than one entry to the function, if computed branches exist, if we
260 : have nonlocal gotos, or if we have an unreachable loop. */
261 :
262 : static bool
263 186 : is_cfg_nonregular (void)
264 : {
265 186 : basic_block b;
266 186 : rtx_insn *insn;
267 :
268 : /* If we have a label that could be the target of a nonlocal goto, then
269 : the cfg is not well structured. */
270 186 : if (nonlocal_goto_handler_labels)
271 : return true;
272 :
273 : /* If we have any forced labels, then the cfg is not well structured. */
274 186 : if (forced_labels)
275 : return true;
276 :
277 : /* If we have exception handlers, then we consider the cfg not well
278 : structured. ?!? We should be able to handle this now that we
279 : compute an accurate cfg for EH. */
280 186 : if (current_function_has_exception_handlers ())
281 : return true;
282 :
283 : /* If we have insns which refer to labels as non-jumped-to operands,
284 : then we consider the cfg not well structured. */
285 1927 : FOR_EACH_BB_FN (b, cfun)
286 14995 : FOR_BB_INSNS (b, insn)
287 : {
288 13248 : rtx note, set, dest;
289 13248 : rtx_insn *next;
290 :
291 : /* If this function has a computed jump, then we consider the cfg
292 : not well structured. */
293 13248 : if (JUMP_P (insn) && computed_jump_p (insn))
294 : return true;
295 :
296 : /* A shared table's successors cannot be redirected independently
297 : to create loop preheaders or scheduling bookkeeping blocks. */
298 13248 : if (shared_tablejump_p (insn, NULL, NULL))
299 : return true;
300 :
301 13248 : if (!INSN_P (insn))
302 3780 : continue;
303 :
304 9468 : note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX);
305 9468 : if (note == NULL_RTX)
306 9458 : continue;
307 :
308 : /* For that label not to be seen as a referred-to label, this
309 : must be a single-set which is feeding a jump *only*. This
310 : could be a conditional jump with the label split off for
311 : machine-specific reasons or a casesi/tablejump. */
312 10 : next = next_nonnote_insn (insn);
313 10 : if (next == NULL_RTX
314 10 : || !JUMP_P (next)
315 0 : || (JUMP_LABEL (next) != XEXP (note, 0)
316 0 : && find_reg_note (next, REG_LABEL_TARGET,
317 : XEXP (note, 0)) == NULL_RTX)
318 10 : || BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (next))
319 : return true;
320 :
321 0 : set = single_set (insn);
322 0 : if (set == NULL_RTX)
323 : return true;
324 :
325 0 : dest = SET_DEST (set);
326 0 : if (!REG_P (dest) || !dead_or_set_p (next, dest))
327 : return true;
328 : }
329 :
330 : /* Unreachable loops with more than one basic block are detected
331 : during the DFS traversal in find_rgns.
332 :
333 : Unreachable loops with a single block are detected here. This
334 : test is redundant with the one in find_rgns, but it's much
335 : cheaper to go ahead and catch the trivial case here. */
336 1894 : FOR_EACH_BB_FN (b, cfun)
337 : {
338 1724 : if (EDGE_COUNT (b->preds) == 0
339 2886 : || (single_pred_p (b)
340 1162 : && single_pred (b) == b))
341 : return true;
342 : }
343 :
344 : /* All the tests passed. Consider the cfg well structured. */
345 : return false;
346 : }
347 :
348 : /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */
349 :
350 : static void
351 51 : extract_edgelst (sbitmap set, edgelst *el)
352 : {
353 51 : unsigned int i = 0;
354 51 : sbitmap_iterator sbi;
355 :
356 : /* edgelst table space is reused in each call to extract_edgelst. */
357 51 : edgelst_last = 0;
358 :
359 51 : el->first_member = &edgelst_table[edgelst_last];
360 51 : el->nr_members = 0;
361 :
362 : /* Iterate over each word in the bitset. */
363 174 : EXECUTE_IF_SET_IN_BITMAP (set, 0, i, sbi)
364 : {
365 72 : edgelst_table[edgelst_last++] = rgn_edges[i];
366 72 : el->nr_members++;
367 : }
368 51 : }
369 :
370 : /* Functions for the construction of regions. */
371 :
372 : /* Print the regions, for debugging purposes. Callable from debugger. */
373 :
374 : DEBUG_FUNCTION void
375 0 : debug_regions (void)
376 : {
377 0 : int rgn, bb;
378 :
379 0 : fprintf (sched_dump, "\n;; ------------ REGIONS ----------\n\n");
380 0 : for (rgn = 0; rgn < nr_regions; rgn++)
381 : {
382 0 : fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
383 0 : rgn_table[rgn].rgn_nr_blocks);
384 0 : fprintf (sched_dump, ";;\tbb/block: ");
385 :
386 : /* We don't have ebb_head initialized yet, so we can't use
387 : BB_TO_BLOCK (). */
388 0 : current_blocks = RGN_BLOCKS (rgn);
389 :
390 0 : for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
391 0 : fprintf (sched_dump, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
392 :
393 0 : fprintf (sched_dump, "\n\n");
394 : }
395 0 : }
396 :
397 : /* Print the region's basic blocks. */
398 :
399 : DEBUG_FUNCTION void
400 0 : debug_region (int rgn)
401 : {
402 0 : int bb;
403 :
404 0 : fprintf (stderr, "\n;; ------------ REGION %d ----------\n\n", rgn);
405 0 : fprintf (stderr, ";;\trgn %d nr_blocks %d:\n", rgn,
406 0 : rgn_table[rgn].rgn_nr_blocks);
407 0 : fprintf (stderr, ";;\tbb/block: ");
408 :
409 : /* We don't have ebb_head initialized yet, so we can't use
410 : BB_TO_BLOCK (). */
411 0 : current_blocks = RGN_BLOCKS (rgn);
412 :
413 0 : for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
414 0 : fprintf (stderr, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
415 :
416 0 : fprintf (stderr, "\n\n");
417 :
418 0 : for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
419 : {
420 0 : dump_bb (stderr,
421 0 : BASIC_BLOCK_FOR_FN (cfun, rgn_bb_table[current_blocks + bb]),
422 : 0, TDF_SLIM | TDF_BLOCKS);
423 0 : fprintf (stderr, "\n");
424 : }
425 :
426 0 : fprintf (stderr, "\n");
427 :
428 0 : }
429 :
430 : /* True when a bb with index BB_INDEX contained in region RGN. */
431 : static bool
432 0 : bb_in_region_p (int bb_index, int rgn)
433 : {
434 0 : int i;
435 :
436 0 : for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
437 0 : if (rgn_bb_table[current_blocks + i] == bb_index)
438 : return true;
439 :
440 : return false;
441 : }
442 :
443 : /* Dump region RGN to file F using dot syntax. */
444 : void
445 0 : dump_region_dot (FILE *f, int rgn)
446 : {
447 0 : int i;
448 :
449 0 : fprintf (f, "digraph Region_%d {\n", rgn);
450 :
451 : /* We don't have ebb_head initialized yet, so we can't use
452 : BB_TO_BLOCK (). */
453 0 : current_blocks = RGN_BLOCKS (rgn);
454 :
455 0 : for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
456 : {
457 0 : edge e;
458 0 : edge_iterator ei;
459 0 : int src_bb_num = rgn_bb_table[current_blocks + i];
460 0 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, src_bb_num);
461 :
462 0 : FOR_EACH_EDGE (e, ei, bb->succs)
463 0 : if (bb_in_region_p (e->dest->index, rgn))
464 0 : fprintf (f, "\t%d -> %d\n", src_bb_num, e->dest->index);
465 : }
466 0 : fprintf (f, "}\n");
467 0 : }
468 :
469 : /* The same, but first open a file specified by FNAME. */
470 : void
471 0 : dump_region_dot_file (const char *fname, int rgn)
472 : {
473 0 : FILE *f = fopen (fname, "wt");
474 0 : dump_region_dot (f, rgn);
475 0 : fclose (f);
476 0 : }
477 :
478 : /* Build a single block region for each basic block in the function.
479 : This allows for using the same code for interblock and basic block
480 : scheduling. */
481 :
482 : static void
483 982738 : find_single_block_region (bool ebbs_p)
484 : {
485 982738 : basic_block bb, ebb_start;
486 982738 : int i = 0;
487 :
488 982738 : nr_regions = 0;
489 :
490 982738 : if (ebbs_p) {
491 52 : int probability_cutoff;
492 52 : if (profile_info && profile_status_for_fn (cfun) == PROFILE_READ)
493 5 : probability_cutoff = param_tracer_min_branch_probability_feedback;
494 : else
495 47 : probability_cutoff = param_tracer_min_branch_probability;
496 52 : probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
497 :
498 177 : FOR_EACH_BB_FN (ebb_start, cfun)
499 : {
500 125 : RGN_NR_BLOCKS (nr_regions) = 0;
501 125 : RGN_BLOCKS (nr_regions) = i;
502 125 : RGN_DONT_CALC_DEPS (nr_regions) = 0;
503 125 : RGN_HAS_REAL_EBB (nr_regions) = 0;
504 :
505 125 : for (bb = ebb_start; ; bb = bb->next_bb)
506 : {
507 135 : edge e;
508 :
509 135 : rgn_bb_table[i] = bb->index;
510 135 : RGN_NR_BLOCKS (nr_regions)++;
511 135 : CONTAINING_RGN (bb->index) = nr_regions;
512 135 : BLOCK_TO_BB (bb->index) = i - RGN_BLOCKS (nr_regions);
513 135 : i++;
514 :
515 135 : if (bb->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
516 83 : || LABEL_P (BB_HEAD (bb->next_bb)))
517 : break;
518 :
519 15 : e = find_fallthru_edge (bb->succs);
520 15 : if (! e)
521 : break;
522 15 : if (e->probability.initialized_p ()
523 15 : && e->probability.to_reg_br_prob_base () <= probability_cutoff)
524 : break;
525 10 : }
526 :
527 125 : ebb_start = bb;
528 125 : nr_regions++;
529 : }
530 : }
531 : else
532 11498607 : FOR_EACH_BB_FN (bb, cfun)
533 : {
534 10515921 : rgn_bb_table[nr_regions] = bb->index;
535 10515921 : RGN_NR_BLOCKS (nr_regions) = 1;
536 10515921 : RGN_BLOCKS (nr_regions) = nr_regions;
537 10515921 : RGN_DONT_CALC_DEPS (nr_regions) = 0;
538 10515921 : RGN_HAS_REAL_EBB (nr_regions) = 0;
539 :
540 10515921 : CONTAINING_RGN (bb->index) = nr_regions;
541 10515921 : BLOCK_TO_BB (bb->index) = 0;
542 10515921 : nr_regions++;
543 : }
544 982738 : }
545 :
546 : /* Estimate number of the insns in the BB. */
547 : static int
548 108 : rgn_estimate_number_of_insns (basic_block bb)
549 : {
550 108 : int count;
551 :
552 108 : count = INSN_LUID (BB_END (bb)) - INSN_LUID (BB_HEAD (bb));
553 :
554 108 : if (MAY_HAVE_DEBUG_INSNS)
555 : {
556 : rtx_insn *insn;
557 :
558 955 : FOR_BB_INSNS (bb, insn)
559 931 : if (DEBUG_INSN_P (insn))
560 539 : count--;
561 : }
562 :
563 108 : return count;
564 : }
565 :
566 : /* Update number of blocks and the estimate for number of insns
567 : in the region. Return true if the region is "too large" for interblock
568 : scheduling (compile time considerations). */
569 :
570 : static bool
571 117 : too_large (int block, int *num_bbs, int *num_insns)
572 : {
573 117 : (*num_bbs)++;
574 234 : (*num_insns) += (common_sched_info->estimate_number_of_insns
575 117 : (BASIC_BLOCK_FOR_FN (cfun, block)));
576 :
577 117 : return ((*num_bbs > param_max_sched_region_blocks)
578 117 : || (*num_insns > param_max_sched_region_insns));
579 : }
580 :
581 : /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
582 : is still an inner loop. Put in max_hdr[blk] the header of the most inner
583 : loop containing blk. */
584 : #define UPDATE_LOOP_RELATIONS(blk, hdr) \
585 : { \
586 : if (max_hdr[blk] == -1) \
587 : max_hdr[blk] = hdr; \
588 : else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
589 : bitmap_clear_bit (inner, hdr); \
590 : else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
591 : { \
592 : bitmap_clear_bit (inner,max_hdr[blk]); \
593 : max_hdr[blk] = hdr; \
594 : } \
595 : }
596 :
597 : /* Find regions for interblock scheduling.
598 :
599 : A region for scheduling can be:
600 :
601 : * A loop-free procedure, or
602 :
603 : * A reducible inner loop, or
604 :
605 : * A basic block not contained in any other region.
606 :
607 : ?!? In theory we could build other regions based on extended basic
608 : blocks or reverse extended basic blocks. Is it worth the trouble?
609 :
610 : Loop blocks that form a region are put into the region's block list
611 : in topological order.
612 :
613 : This procedure stores its results into the following global (ick) variables
614 :
615 : * rgn_nr
616 : * rgn_table
617 : * rgn_bb_table
618 : * block_to_bb
619 : * containing region
620 :
621 : We use dominator relationships to avoid making regions out of non-reducible
622 : loops.
623 :
624 : This procedure needs to be converted to work on pred/succ lists instead
625 : of edge tables. That would simplify it somewhat. */
626 :
627 : static void
628 127 : haifa_find_rgns (void)
629 : {
630 127 : int *max_hdr, *dfs_nr, *degree;
631 127 : char no_loops = 1;
632 127 : int node, child, loop_head, i, head, tail;
633 127 : int count = 0, sp, idx = 0;
634 127 : edge_iterator current_edge;
635 127 : edge_iterator *stack;
636 127 : int num_bbs, num_insns;
637 127 : bool unreachable;
638 127 : bool too_large_failure;
639 127 : basic_block bb;
640 :
641 : /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
642 : and a mapping from block to its loop header (if the block is contained
643 : in a loop, else -1).
644 :
645 : Store results in HEADER, INNER, and MAX_HDR respectively, these will
646 : be used as inputs to the second traversal.
647 :
648 : STACK, SP and DFS_NR are only used during the first traversal. */
649 :
650 : /* Allocate and initialize variables for the first traversal. */
651 127 : max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
652 127 : dfs_nr = XCNEWVEC (int, last_basic_block_for_fn (cfun));
653 127 : stack = XNEWVEC (edge_iterator, n_edges_for_fn (cfun));
654 :
655 : /* Note if a block is a natural inner loop header. */
656 127 : auto_sbitmap inner (last_basic_block_for_fn (cfun));
657 127 : bitmap_ones (inner);
658 :
659 : /* Note if a block is a natural loop header. */
660 127 : auto_sbitmap header (last_basic_block_for_fn (cfun));
661 127 : bitmap_clear (header);
662 :
663 : /* Note if a block is in the block queue. */
664 127 : auto_sbitmap in_queue (last_basic_block_for_fn (cfun));
665 127 : bitmap_clear (in_queue);
666 :
667 : /* Note if a block is in the block queue. */
668 127 : auto_sbitmap in_stack (last_basic_block_for_fn (cfun));
669 127 : bitmap_clear (in_stack);
670 :
671 1764 : for (i = 0; i < last_basic_block_for_fn (cfun); i++)
672 1510 : max_hdr[i] = -1;
673 :
674 : #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
675 : #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
676 :
677 : /* DFS traversal to find inner loops in the cfg. */
678 :
679 127 : current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))->succs);
680 127 : sp = -1;
681 :
682 2416 : while (1)
683 : {
684 2416 : if (EDGE_PASSED (current_edge))
685 : {
686 : /* We have reached a leaf node or a node that was already
687 : processed. Pop edges off the stack until we find
688 : an edge that has not yet been processed. */
689 1710 : while (sp >= 0 && EDGE_PASSED (current_edge))
690 : {
691 : /* Pop entry off the stack. */
692 1147 : current_edge = stack[sp--];
693 1147 : node = ei_edge (current_edge)->src->index;
694 1147 : gcc_assert (node != ENTRY_BLOCK);
695 1147 : child = ei_edge (current_edge)->dest->index;
696 1147 : gcc_assert (child != EXIT_BLOCK);
697 1147 : bitmap_clear_bit (in_stack, child);
698 1147 : if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
699 208 : UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
700 1147 : ei_next (¤t_edge);
701 : }
702 :
703 : /* See if have finished the DFS tree traversal. */
704 563 : if (sp < 0 && EDGE_PASSED (current_edge))
705 : break;
706 :
707 : /* Nope, continue the traversal with the popped node. */
708 436 : continue;
709 : }
710 :
711 : /* Process a node. */
712 1853 : node = ei_edge (current_edge)->src->index;
713 1853 : gcc_assert (node != ENTRY_BLOCK);
714 1853 : bitmap_set_bit (in_stack, node);
715 1853 : dfs_nr[node] = ++count;
716 :
717 : /* We don't traverse to the exit block. */
718 1853 : child = ei_edge (current_edge)->dest->index;
719 1853 : if (child == EXIT_BLOCK)
720 : {
721 125 : SET_EDGE_PASSED (current_edge);
722 125 : ei_next (¤t_edge);
723 125 : continue;
724 : }
725 :
726 : /* If the successor is in the stack, then we've found a loop.
727 : Mark the loop, if it is not a natural loop, then it will
728 : be rejected during the second traversal. */
729 1728 : if (bitmap_bit_p (in_stack, child))
730 : {
731 140 : no_loops = 0;
732 140 : bitmap_set_bit (header, child);
733 140 : UPDATE_LOOP_RELATIONS (node, child);
734 140 : SET_EDGE_PASSED (current_edge);
735 140 : ei_next (¤t_edge);
736 140 : continue;
737 : }
738 :
739 : /* If the child was already visited, then there is no need to visit
740 : it again. Just update the loop relationships and restart
741 : with a new edge. */
742 1588 : if (dfs_nr[child])
743 : {
744 441 : if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
745 42 : UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
746 441 : SET_EDGE_PASSED (current_edge);
747 441 : ei_next (¤t_edge);
748 441 : continue;
749 : }
750 :
751 : /* Push an entry on the stack and continue DFS traversal. */
752 1147 : stack[++sp] = current_edge;
753 1147 : SET_EDGE_PASSED (current_edge);
754 1147 : current_edge = ei_start (ei_edge (current_edge)->dest->succs);
755 : }
756 :
757 : /* Reset ->aux field used by EDGE_PASSED. */
758 1636 : FOR_ALL_BB_FN (bb, cfun)
759 : {
760 1509 : edge_iterator ei;
761 1509 : edge e;
762 3489 : FOR_EACH_EDGE (e, ei, bb->succs)
763 1980 : e->aux = NULL;
764 : }
765 :
766 :
767 : /* Another check for unreachable blocks. The earlier test in
768 : is_cfg_nonregular only finds unreachable blocks that do not
769 : form a loop.
770 :
771 : The DFS traversal will mark every block that is reachable from
772 : the entry node by placing a nonzero value in dfs_nr. Thus if
773 : dfs_nr is zero for any block, then it must be unreachable. */
774 127 : unreachable = false;
775 1309 : FOR_EACH_BB_FN (bb, cfun)
776 1216 : if (dfs_nr[bb->index] == 0)
777 : {
778 : unreachable = true;
779 : break;
780 : }
781 :
782 : /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
783 : to hold degree counts. */
784 127 : degree = dfs_nr;
785 :
786 1382 : FOR_EACH_BB_FN (bb, cfun)
787 2510 : degree[bb->index] = EDGE_COUNT (bb->preds);
788 :
789 : /* Do not perform region scheduling if there are any unreachable
790 : blocks. */
791 127 : if (!unreachable)
792 : {
793 93 : int *queue, *degree1 = NULL;
794 : /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
795 : there basic blocks, which are forced to be region heads.
796 : This is done to try to assemble few smaller regions
797 : from a too_large region. */
798 93 : sbitmap extended_rgn_header = NULL;
799 93 : bool extend_regions_p;
800 :
801 93 : if (no_loops)
802 22 : bitmap_set_bit (header, 0);
803 :
804 : /* Second traversal:find reducible inner loops and topologically sort
805 : block of each region. */
806 :
807 93 : queue = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
808 :
809 93 : extend_regions_p = param_max_sched_extend_regions_iters > 0;
810 93 : if (extend_regions_p)
811 : {
812 2 : degree1 = XNEWVEC (int, last_basic_block_for_fn (cfun));
813 2 : extended_rgn_header =
814 2 : sbitmap_alloc (last_basic_block_for_fn (cfun));
815 2 : bitmap_clear (extended_rgn_header);
816 : }
817 :
818 : /* Find blocks which are inner loop headers. We still have non-reducible
819 : loops to consider at this point. */
820 1193 : FOR_EACH_BB_FN (bb, cfun)
821 : {
822 1100 : if (bitmap_bit_p (header, bb->index) && bitmap_bit_p (inner, bb->index))
823 : {
824 95 : edge e;
825 95 : edge_iterator ei;
826 95 : basic_block jbb;
827 :
828 : /* Now check that the loop is reducible. We do this separate
829 : from finding inner loops so that we do not find a reducible
830 : loop which contains an inner non-reducible loop.
831 :
832 : A simple way to find reducible/natural loops is to verify
833 : that each block in the loop is dominated by the loop
834 : header.
835 :
836 : If there exists a block that is not dominated by the loop
837 : header, then the block is reachable from outside the loop
838 : and thus the loop is not a natural loop. */
839 1650 : FOR_EACH_BB_FN (jbb, cfun)
840 : {
841 : /* First identify blocks in the loop, except for the loop
842 : entry block. */
843 1562 : if (bb->index == max_hdr[jbb->index] && bb != jbb)
844 : {
845 : /* Now verify that the block is dominated by the loop
846 : header. */
847 104 : if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))
848 : break;
849 : }
850 : }
851 :
852 : /* If we exited the loop early, then I is the header of
853 : a non-reducible loop and we should quit processing it
854 : now. */
855 95 : if (jbb != EXIT_BLOCK_PTR_FOR_FN (cfun))
856 7 : continue;
857 :
858 : /* I is a header of an inner loop, or block 0 in a subroutine
859 : with no loops at all. */
860 88 : head = tail = -1;
861 88 : too_large_failure = false;
862 88 : loop_head = max_hdr[bb->index];
863 :
864 88 : if (extend_regions_p)
865 : /* We save degree in case when we meet a too_large region
866 : and cancel it. We need a correct degree later when
867 : calling extend_rgns. */
868 1 : memcpy (degree1, degree,
869 1 : last_basic_block_for_fn (cfun) * sizeof (int));
870 :
871 : /* Decrease degree of all I's successors for topological
872 : ordering. */
873 244 : FOR_EACH_EDGE (e, ei, bb->succs)
874 156 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
875 155 : --degree[e->dest->index];
876 :
877 : /* Estimate # insns, and count # blocks in the region. */
878 88 : num_bbs = 1;
879 88 : num_insns = common_sched_info->estimate_number_of_insns (bb);
880 :
881 : /* Find all loop latches (blocks with back edges to the loop
882 : header) or all the leaf blocks in the cfg has no loops.
883 :
884 : Place those blocks into the queue. */
885 88 : if (no_loops)
886 : {
887 0 : FOR_EACH_BB_FN (jbb, cfun)
888 : /* Leaf nodes have only a single successor which must
889 : be EXIT_BLOCK. */
890 0 : if (single_succ_p (jbb)
891 0 : && single_succ (jbb) == EXIT_BLOCK_PTR_FOR_FN (cfun))
892 : {
893 0 : queue[++tail] = jbb->index;
894 0 : bitmap_set_bit (in_queue, jbb->index);
895 :
896 0 : if (too_large (jbb->index, &num_bbs, &num_insns))
897 : {
898 88 : too_large_failure = true;
899 : break;
900 : }
901 : }
902 : }
903 : else
904 : {
905 88 : edge e;
906 :
907 290 : FOR_EACH_EDGE (e, ei, bb->preds)
908 : {
909 203 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
910 0 : continue;
911 :
912 203 : node = e->src->index;
913 :
914 203 : if (max_hdr[node] == loop_head && node != bb->index)
915 : {
916 : /* This is a loop latch. */
917 43 : queue[++tail] = node;
918 43 : bitmap_set_bit (in_queue, node);
919 :
920 43 : if (too_large (node, &num_bbs, &num_insns))
921 : {
922 : too_large_failure = true;
923 : break;
924 : }
925 : }
926 : }
927 : }
928 :
929 : /* Now add all the blocks in the loop to the queue.
930 :
931 : We know the loop is a natural loop; however the algorithm
932 : above will not always mark certain blocks as being in the
933 : loop. Consider:
934 : node children
935 : a b,c
936 : b c
937 : c a,d
938 : d b
939 :
940 : The algorithm in the DFS traversal may not mark B & D as part
941 : of the loop (i.e. they will not have max_hdr set to A).
942 :
943 : We know they cannot be loop latches (else they would have
944 : had max_hdr set since they'd have a backedge to a dominator
945 : block). So we don't need them on the initial queue.
946 :
947 : We know they are part of the loop because they are dominated
948 : by the loop header and can be reached by a backwards walk of
949 : the edges starting with nodes on the initial queue.
950 :
951 : It is safe and desirable to include those nodes in the
952 : loop/scheduling region. To do so we would need to decrease
953 : the degree of a node if it is the target of a backedge
954 : within the loop itself as the node is placed in the queue.
955 :
956 : We do not do this because I'm not sure that the actual
957 : scheduling code will properly handle this case. ?!? */
958 :
959 182 : while (head < tail && !too_large_failure)
960 : {
961 94 : edge e;
962 94 : child = queue[++head];
963 :
964 207 : FOR_EACH_EDGE (e, ei,
965 : BASIC_BLOCK_FOR_FN (cfun, child)->preds)
966 : {
967 113 : node = e->src->index;
968 :
969 : /* See discussion above about nodes not marked as in
970 : this loop during the initial DFS traversal. */
971 113 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
972 113 : || max_hdr[node] != loop_head)
973 : {
974 : tail = -1;
975 : break;
976 : }
977 113 : else if (!bitmap_bit_p (in_queue, node) && node != bb->index)
978 : {
979 52 : queue[++tail] = node;
980 52 : bitmap_set_bit (in_queue, node);
981 :
982 52 : if (too_large (node, &num_bbs, &num_insns))
983 : {
984 : too_large_failure = true;
985 : break;
986 : }
987 : }
988 : }
989 : }
990 :
991 88 : if (tail >= 0 && !too_large_failure)
992 : {
993 : /* Place the loop header into list of region blocks. */
994 41 : degree[bb->index] = -1;
995 41 : rgn_bb_table[idx] = bb->index;
996 41 : RGN_NR_BLOCKS (nr_regions) = num_bbs;
997 41 : RGN_BLOCKS (nr_regions) = idx++;
998 41 : RGN_DONT_CALC_DEPS (nr_regions) = 0;
999 41 : RGN_HAS_REAL_EBB (nr_regions) = 0;
1000 41 : CONTAINING_RGN (bb->index) = nr_regions;
1001 41 : BLOCK_TO_BB (bb->index) = count = 0;
1002 :
1003 : /* Remove blocks from queue[] when their in degree
1004 : becomes zero. Repeat until no blocks are left on the
1005 : list. This produces a topological list of blocks in
1006 : the region. */
1007 188 : while (tail >= 0)
1008 : {
1009 147 : if (head < 0)
1010 0 : head = tail;
1011 147 : child = queue[head];
1012 147 : if (degree[child] == 0)
1013 : {
1014 94 : edge e;
1015 :
1016 94 : degree[child] = -1;
1017 94 : rgn_bb_table[idx++] = child;
1018 94 : BLOCK_TO_BB (child) = ++count;
1019 94 : CONTAINING_RGN (child) = nr_regions;
1020 94 : queue[head] = queue[tail--];
1021 :
1022 252 : FOR_EACH_EDGE (e, ei,
1023 : BASIC_BLOCK_FOR_FN (cfun,
1024 : child)->succs)
1025 158 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1026 158 : --degree[e->dest->index];
1027 : }
1028 : else
1029 53 : --head;
1030 : }
1031 41 : ++nr_regions;
1032 : }
1033 47 : else if (extend_regions_p)
1034 : {
1035 : /* Restore DEGREE. */
1036 0 : int *t = degree;
1037 :
1038 0 : degree = degree1;
1039 0 : degree1 = t;
1040 :
1041 : /* And force successors of BB to be region heads.
1042 : This may provide several smaller regions instead
1043 : of one too_large region. */
1044 0 : FOR_EACH_EDGE (e, ei, bb->succs)
1045 0 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1046 0 : bitmap_set_bit (extended_rgn_header, e->dest->index);
1047 : }
1048 : }
1049 : }
1050 93 : free (queue);
1051 :
1052 93 : if (extend_regions_p)
1053 : {
1054 2 : free (degree1);
1055 :
1056 2 : bitmap_ior (header, header, extended_rgn_header);
1057 2 : sbitmap_free (extended_rgn_header);
1058 :
1059 2 : extend_rgns (degree, &idx, header, max_hdr);
1060 : }
1061 : }
1062 :
1063 : /* Any block that did not end up in a region is placed into a region
1064 : by itself. */
1065 1382 : FOR_EACH_BB_FN (bb, cfun)
1066 1255 : if (degree[bb->index] >= 0)
1067 : {
1068 1098 : rgn_bb_table[idx] = bb->index;
1069 1098 : RGN_NR_BLOCKS (nr_regions) = 1;
1070 1098 : RGN_BLOCKS (nr_regions) = idx++;
1071 1098 : RGN_DONT_CALC_DEPS (nr_regions) = 0;
1072 1098 : RGN_HAS_REAL_EBB (nr_regions) = 0;
1073 1098 : CONTAINING_RGN (bb->index) = nr_regions++;
1074 1098 : BLOCK_TO_BB (bb->index) = 0;
1075 : }
1076 :
1077 127 : free (max_hdr);
1078 127 : free (degree);
1079 127 : free (stack);
1080 127 : }
1081 :
1082 :
1083 : /* Wrapper function.
1084 : If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
1085 : regions. Otherwise just call find_rgns_haifa. */
1086 : static void
1087 170 : find_rgns (void)
1088 : {
1089 170 : if (sel_sched_p () && flag_sel_sched_pipelining)
1090 43 : sel_find_rgns ();
1091 : else
1092 127 : haifa_find_rgns ();
1093 170 : }
1094 :
1095 : static int gather_region_statistics (int **);
1096 : static void print_region_statistics (int *, int, int *, int);
1097 :
1098 : /* Calculate the histogram that shows the number of regions having the
1099 : given number of basic blocks, and store it in the RSP array. Return
1100 : the size of this array. */
1101 : static int
1102 0 : gather_region_statistics (int **rsp)
1103 : {
1104 0 : int i, *a = 0, a_sz = 0;
1105 :
1106 : /* a[i] is the number of regions that have (i + 1) basic blocks. */
1107 0 : for (i = 0; i < nr_regions; i++)
1108 : {
1109 0 : int nr_blocks = RGN_NR_BLOCKS (i);
1110 :
1111 0 : gcc_assert (nr_blocks >= 1);
1112 :
1113 0 : if (nr_blocks > a_sz)
1114 : {
1115 0 : a = XRESIZEVEC (int, a, nr_blocks);
1116 0 : do
1117 0 : a[a_sz++] = 0;
1118 0 : while (a_sz != nr_blocks);
1119 : }
1120 :
1121 0 : a[nr_blocks - 1]++;
1122 : }
1123 :
1124 0 : *rsp = a;
1125 0 : return a_sz;
1126 : }
1127 :
1128 : /* Print regions statistics. S1 and S2 denote the data before and after
1129 : calling extend_rgns, respectively. */
1130 : static void
1131 0 : print_region_statistics (int *s1, int s1_sz, int *s2, int s2_sz)
1132 : {
1133 0 : int i;
1134 :
1135 : /* We iterate until s2_sz because extend_rgns does not decrease
1136 : the maximal region size. */
1137 0 : for (i = 1; i < s2_sz; i++)
1138 : {
1139 0 : int n1, n2;
1140 :
1141 0 : n2 = s2[i];
1142 :
1143 0 : if (n2 == 0)
1144 0 : continue;
1145 :
1146 0 : if (i >= s1_sz)
1147 : n1 = 0;
1148 : else
1149 0 : n1 = s1[i];
1150 :
1151 0 : fprintf (sched_dump, ";; Region extension statistics: size %d: " \
1152 : "was %d + %d more\n", i + 1, n1, n2 - n1);
1153 : }
1154 0 : }
1155 :
1156 : /* Extend regions.
1157 : DEGREE - Array of incoming edge count, considering only
1158 : the edges, that don't have their sources in formed regions yet.
1159 : IDXP - pointer to the next available index in rgn_bb_table.
1160 : HEADER - set of all region heads.
1161 : LOOP_HDR - mapping from block to the containing loop
1162 : (two blocks can reside within one region if they have
1163 : the same loop header). */
1164 : void
1165 45 : extend_rgns (int *degree, int *idxp, sbitmap header, int *loop_hdr)
1166 : {
1167 45 : int *order, i, idx = *idxp, iter = 0, max_iter, *max_hdr;
1168 45 : int nblocks = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
1169 45 : bool rescan = false;
1170 :
1171 45 : max_iter = param_max_sched_extend_regions_iters;
1172 :
1173 45 : max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
1174 :
1175 45 : order = XNEWVEC (int, last_basic_block_for_fn (cfun));
1176 45 : post_order_compute (order, false, false);
1177 :
1178 578 : for (i = nblocks - 1; i >= 0; i--)
1179 : {
1180 533 : int bbn = order[i];
1181 533 : if (degree[bbn] >= 0)
1182 : {
1183 254 : max_hdr[bbn] = bbn;
1184 254 : rescan = true;
1185 : }
1186 : else
1187 : /* This block already was processed in find_rgns. */
1188 279 : max_hdr[bbn] = -1;
1189 : }
1190 :
1191 : /* The idea is to topologically walk through CFG in top-down order.
1192 : During the traversal, if all the predecessors of a node are
1193 : marked to be in the same region (they all have the same max_hdr),
1194 : then current node is also marked to be a part of that region.
1195 : Otherwise the node starts its own region.
1196 : CFG should be traversed until no further changes are made. On each
1197 : iteration the set of the region heads is extended (the set of those
1198 : blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
1199 : set of all basic blocks, thus the algorithm is guaranteed to
1200 : terminate. */
1201 :
1202 49 : while (rescan && iter < max_iter)
1203 : {
1204 : rescan = false;
1205 :
1206 52 : for (i = nblocks - 1; i >= 0; i--)
1207 : {
1208 48 : edge e;
1209 48 : edge_iterator ei;
1210 48 : int bbn = order[i];
1211 :
1212 48 : if (max_hdr[bbn] != -1 && !bitmap_bit_p (header, bbn))
1213 : {
1214 41 : int hdr = -1;
1215 :
1216 91 : FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->preds)
1217 : {
1218 53 : int predn = e->src->index;
1219 :
1220 53 : if (predn != ENTRY_BLOCK
1221 : /* If pred wasn't processed in find_rgns. */
1222 51 : && max_hdr[predn] != -1
1223 : /* And pred and bb reside in the same loop.
1224 : (Or out of any loop). */
1225 50 : && loop_hdr[bbn] == loop_hdr[predn])
1226 : {
1227 50 : if (hdr == -1)
1228 : /* Then bb extends the containing region of pred. */
1229 : hdr = max_hdr[predn];
1230 12 : else if (hdr != max_hdr[predn])
1231 : /* Too bad, there are at least two predecessors
1232 : that reside in different regions. Thus, BB should
1233 : begin its own region. */
1234 : {
1235 : hdr = bbn;
1236 : break;
1237 : }
1238 : }
1239 : else
1240 : /* BB starts its own region. */
1241 : {
1242 : hdr = bbn;
1243 : break;
1244 : }
1245 : }
1246 :
1247 41 : if (hdr == bbn)
1248 : {
1249 : /* If BB start its own region,
1250 : update set of headers with BB. */
1251 3 : bitmap_set_bit (header, bbn);
1252 3 : rescan = true;
1253 : }
1254 : else
1255 38 : gcc_assert (hdr != -1);
1256 :
1257 41 : max_hdr[bbn] = hdr;
1258 : }
1259 : }
1260 :
1261 4 : iter++;
1262 : }
1263 :
1264 : /* Statistics were gathered on the SPEC2000 package of tests with
1265 : mainline weekly snapshot gcc-4.1-20051015 on ia64.
1266 :
1267 : Statistics for SPECint:
1268 : 1 iteration : 1751 cases (38.7%)
1269 : 2 iterations: 2770 cases (61.3%)
1270 : Blocks wrapped in regions by find_rgns without extension: 18295 blocks
1271 : Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
1272 : (We don't count single block regions here).
1273 :
1274 : Statistics for SPECfp:
1275 : 1 iteration : 621 cases (35.9%)
1276 : 2 iterations: 1110 cases (64.1%)
1277 : Blocks wrapped in regions by find_rgns without extension: 6476 blocks
1278 : Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
1279 : (We don't count single block regions here).
1280 :
1281 : By default we do at most 2 iterations.
1282 : This can be overridden with max-sched-extend-regions-iters parameter:
1283 : 0 - disable region extension,
1284 : N > 0 - do at most N iterations. */
1285 :
1286 45 : if (sched_verbose && iter != 0)
1287 0 : fprintf (sched_dump, ";; Region extension iterations: %d%s\n", iter,
1288 : rescan ? "... failed" : "");
1289 :
1290 45 : if (!rescan && iter != 0)
1291 : {
1292 2 : int *s1 = NULL, s1_sz = 0;
1293 :
1294 : /* Save the old statistics for later printout. */
1295 2 : if (sched_verbose >= 6)
1296 0 : s1_sz = gather_region_statistics (&s1);
1297 :
1298 : /* We have succeeded. Now assemble the regions. */
1299 26 : for (i = nblocks - 1; i >= 0; i--)
1300 : {
1301 24 : int bbn = order[i];
1302 :
1303 24 : if (max_hdr[bbn] == bbn)
1304 : /* BBN is a region head. */
1305 : {
1306 3 : edge e;
1307 3 : edge_iterator ei;
1308 3 : int num_bbs = 0, j, num_insns = 0, large;
1309 :
1310 3 : large = too_large (bbn, &num_bbs, &num_insns);
1311 :
1312 3 : degree[bbn] = -1;
1313 3 : rgn_bb_table[idx] = bbn;
1314 3 : RGN_BLOCKS (nr_regions) = idx++;
1315 3 : RGN_DONT_CALC_DEPS (nr_regions) = 0;
1316 3 : RGN_HAS_REAL_EBB (nr_regions) = 0;
1317 3 : CONTAINING_RGN (bbn) = nr_regions;
1318 3 : BLOCK_TO_BB (bbn) = 0;
1319 :
1320 8 : FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->succs)
1321 5 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1322 4 : degree[e->dest->index]--;
1323 :
1324 3 : if (!large)
1325 : /* Here we check whether the region is too_large. */
1326 22 : for (j = i - 1; j >= 0; j--)
1327 : {
1328 20 : int succn = order[j];
1329 20 : if (max_hdr[succn] == bbn)
1330 : {
1331 19 : if ((large = too_large (succn, &num_bbs, &num_insns)))
1332 : break;
1333 : }
1334 : }
1335 :
1336 3 : if (large)
1337 : /* If the region is too_large, then wrap every block of
1338 : the region into single block region.
1339 : Here we wrap region head only. Other blocks are
1340 : processed in the below cycle. */
1341 : {
1342 1 : RGN_NR_BLOCKS (nr_regions) = 1;
1343 1 : nr_regions++;
1344 : }
1345 :
1346 3 : num_bbs = 1;
1347 :
1348 26 : for (j = i - 1; j >= 0; j--)
1349 : {
1350 23 : int succn = order[j];
1351 :
1352 23 : if (max_hdr[succn] == bbn)
1353 : /* This cycle iterates over all basic blocks, that
1354 : are supposed to be in the region with head BBN,
1355 : and wraps them into that region (or in single
1356 : block region). */
1357 : {
1358 19 : gcc_assert (degree[succn] == 0);
1359 :
1360 19 : degree[succn] = -1;
1361 19 : rgn_bb_table[idx] = succn;
1362 19 : BLOCK_TO_BB (succn) = large ? 0 : num_bbs++;
1363 19 : CONTAINING_RGN (succn) = nr_regions;
1364 :
1365 19 : if (large)
1366 : /* Wrap SUCCN into single block region. */
1367 : {
1368 15 : RGN_BLOCKS (nr_regions) = idx;
1369 15 : RGN_NR_BLOCKS (nr_regions) = 1;
1370 15 : RGN_DONT_CALC_DEPS (nr_regions) = 0;
1371 15 : RGN_HAS_REAL_EBB (nr_regions) = 0;
1372 15 : nr_regions++;
1373 : }
1374 :
1375 19 : idx++;
1376 :
1377 45 : FOR_EACH_EDGE (e, ei,
1378 : BASIC_BLOCK_FOR_FN (cfun, succn)->succs)
1379 26 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1380 25 : degree[e->dest->index]--;
1381 : }
1382 : }
1383 :
1384 3 : if (!large)
1385 : {
1386 2 : RGN_NR_BLOCKS (nr_regions) = num_bbs;
1387 2 : nr_regions++;
1388 : }
1389 : }
1390 : }
1391 :
1392 2 : if (sched_verbose >= 6)
1393 : {
1394 0 : int *s2, s2_sz;
1395 :
1396 : /* Get the new statistics and print the comparison with the
1397 : one before calling this function. */
1398 0 : s2_sz = gather_region_statistics (&s2);
1399 0 : print_region_statistics (s1, s1_sz, s2, s2_sz);
1400 0 : free (s1);
1401 0 : free (s2);
1402 : }
1403 : }
1404 :
1405 45 : free (order);
1406 45 : free (max_hdr);
1407 :
1408 45 : *idxp = idx;
1409 45 : }
1410 :
1411 : /* Functions for regions scheduling information. */
1412 :
1413 : /* Compute dominators, probability, and potential-split-edges of bb.
1414 : Assume that these values were already computed for bb's predecessors. */
1415 :
1416 : static void
1417 72 : compute_dom_prob_ps (int bb)
1418 : {
1419 72 : edge_iterator in_ei;
1420 72 : edge in_edge;
1421 :
1422 : /* We shouldn't have any real ebbs yet. */
1423 72 : gcc_assert (ebb_head [bb] == bb + current_blocks);
1424 :
1425 72 : if (IS_RGN_ENTRY (bb))
1426 : {
1427 26 : bitmap_set_bit (dom[bb], 0);
1428 26 : prob[bb] = REG_BR_PROB_BASE;
1429 26 : return;
1430 : }
1431 :
1432 46 : prob[bb] = 0;
1433 :
1434 : /* Initialize dom[bb] to '111..1'. */
1435 46 : bitmap_ones (dom[bb]);
1436 :
1437 93 : FOR_EACH_EDGE (in_edge, in_ei,
1438 : BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb))->preds)
1439 : {
1440 47 : int pred_bb;
1441 47 : edge out_edge;
1442 47 : edge_iterator out_ei;
1443 :
1444 47 : if (in_edge->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1445 0 : continue;
1446 :
1447 47 : pred_bb = BLOCK_TO_BB (in_edge->src->index);
1448 47 : bitmap_and (dom[bb], dom[bb], dom[pred_bb]);
1449 47 : bitmap_ior (ancestor_edges[bb],
1450 47 : ancestor_edges[bb], ancestor_edges[pred_bb]);
1451 :
1452 47 : bitmap_set_bit (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
1453 :
1454 47 : bitmap_ior (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
1455 :
1456 139 : FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
1457 92 : bitmap_set_bit (pot_split[bb], EDGE_TO_BIT (out_edge));
1458 :
1459 94 : prob[bb] += combine_probabilities
1460 94 : (prob[pred_bb],
1461 47 : in_edge->probability.initialized_p ()
1462 47 : ? in_edge->probability.to_reg_br_prob_base ()
1463 : : 0);
1464 : // The rounding divide in combine_probabilities can result in an extra
1465 : // probability increment propagating along 50-50 edges. Eventually when
1466 : // the edges re-merge, the accumulated probability can go slightly above
1467 : // REG_BR_PROB_BASE.
1468 47 : if (prob[bb] > REG_BR_PROB_BASE)
1469 0 : prob[bb] = REG_BR_PROB_BASE;
1470 : }
1471 :
1472 46 : bitmap_set_bit (dom[bb], bb);
1473 46 : bitmap_and_compl (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
1474 :
1475 46 : if (sched_verbose >= 2)
1476 0 : fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
1477 0 : (100 * prob[bb]) / REG_BR_PROB_BASE);
1478 : }
1479 :
1480 : /* Functions for target info. */
1481 :
1482 : /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1483 : Note that bb_trg dominates bb_src. */
1484 :
1485 : static void
1486 51 : split_edges (int bb_src, int bb_trg, edgelst *bl)
1487 : {
1488 51 : auto_sbitmap src (SBITMAP_SIZE (pot_split[bb_src]));
1489 51 : bitmap_copy (src, pot_split[bb_src]);
1490 :
1491 51 : bitmap_and_compl (src, src, pot_split[bb_trg]);
1492 51 : extract_edgelst (src, bl);
1493 51 : }
1494 :
1495 : /* Find the valid candidate-source-blocks for the target block TRG, compute
1496 : their probability, and check if they are speculative or not.
1497 : For speculative sources, compute their update-blocks and split-blocks. */
1498 :
1499 : static void
1500 72 : compute_trg_info (int trg)
1501 : {
1502 72 : candidate *sp;
1503 72 : edgelst el = { NULL, 0 };
1504 72 : int i, j, k, update_idx;
1505 72 : basic_block block;
1506 72 : edge_iterator ei;
1507 72 : edge e;
1508 :
1509 72 : candidate_table = XNEWVEC (candidate, current_nr_blocks);
1510 :
1511 72 : bblst_last = 0;
1512 : /* bblst_table holds split blocks and update blocks for each block after
1513 : the current one in the region. split blocks and update blocks are
1514 : the TO blocks of region edges, so there can be at most rgn_nr_edges
1515 : of them. */
1516 72 : bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
1517 72 : bblst_table = XNEWVEC (basic_block, bblst_size);
1518 :
1519 72 : edgelst_last = 0;
1520 72 : edgelst_table = XNEWVEC (edge, rgn_nr_edges);
1521 :
1522 : /* Define some of the fields for the target bb as well. */
1523 72 : sp = candidate_table + trg;
1524 72 : sp->is_valid = 1;
1525 72 : sp->is_speculative = 0;
1526 72 : sp->src_prob = REG_BR_PROB_BASE;
1527 :
1528 72 : auto_sbitmap visited (last_basic_block_for_fn (cfun));
1529 :
1530 154 : for (i = trg + 1; i < current_nr_blocks; i++)
1531 : {
1532 82 : sp = candidate_table + i;
1533 :
1534 82 : sp->is_valid = IS_DOMINATED (i, trg);
1535 82 : if (sp->is_valid)
1536 : {
1537 74 : int tf = prob[trg], cf = prob[i];
1538 :
1539 : /* In CFGs with low probability edges TF can possibly be zero. */
1540 74 : sp->src_prob = (tf ?
1541 74 : profile_count::from_gcov_type (cf)
1542 : .probability_in
1543 74 : (profile_count::from_gcov_type (tf))
1544 74 : .to_reg_br_prob_base ()
1545 : : 0);
1546 74 : sp->is_valid = (sp->src_prob >= min_spec_prob);
1547 : }
1548 :
1549 82 : if (sp->is_valid)
1550 : {
1551 51 : split_edges (i, trg, &el);
1552 51 : sp->is_speculative = (el.nr_members) ? 1 : 0;
1553 51 : if (sp->is_speculative && !flag_schedule_speculative)
1554 0 : sp->is_valid = 0;
1555 : }
1556 :
1557 82 : if (sp->is_valid)
1558 : {
1559 : /* Compute split blocks and store them in bblst_table.
1560 : The TO block of every split edge is a split block. */
1561 51 : sp->split_bbs.first_member = &bblst_table[bblst_last];
1562 51 : sp->split_bbs.nr_members = el.nr_members;
1563 123 : for (j = 0; j < el.nr_members; bblst_last++, j++)
1564 72 : bblst_table[bblst_last] = el.first_member[j]->dest;
1565 51 : sp->update_bbs.first_member = &bblst_table[bblst_last];
1566 :
1567 : /* Compute update blocks and store them in bblst_table.
1568 : For every split edge, look at the FROM block, and check
1569 : all out edges. For each out edge that is not a split edge,
1570 : add the TO block to the update block list. This list can end
1571 : up with a lot of duplicates. We need to weed them out to avoid
1572 : overrunning the end of the bblst_table. */
1573 :
1574 51 : update_idx = 0;
1575 51 : bitmap_clear (visited);
1576 174 : for (j = 0; j < el.nr_members; j++)
1577 : {
1578 72 : block = el.first_member[j]->src;
1579 216 : FOR_EACH_EDGE (e, ei, block->succs)
1580 : {
1581 144 : if (!bitmap_bit_p (visited, e->dest->index))
1582 : {
1583 285 : for (k = 0; k < el.nr_members; k++)
1584 213 : if (e == el.first_member[k])
1585 : break;
1586 :
1587 144 : if (k >= el.nr_members)
1588 : {
1589 72 : bblst_table[bblst_last++] = e->dest;
1590 72 : bitmap_set_bit (visited, e->dest->index);
1591 72 : update_idx++;
1592 : }
1593 : }
1594 : }
1595 : }
1596 51 : sp->update_bbs.nr_members = update_idx;
1597 :
1598 : /* Make sure we didn't overrun the end of bblst_table. */
1599 51 : gcc_assert (bblst_last <= bblst_size);
1600 : }
1601 : else
1602 : {
1603 31 : sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1604 :
1605 31 : sp->is_speculative = 0;
1606 31 : sp->src_prob = 0;
1607 : }
1608 : }
1609 72 : }
1610 :
1611 : /* Free the computed target info. */
1612 : static void
1613 72 : free_trg_info (void)
1614 : {
1615 72 : free (candidate_table);
1616 72 : free (bblst_table);
1617 72 : free (edgelst_table);
1618 72 : }
1619 :
1620 : /* Print candidates info, for debugging purposes. Callable from debugger. */
1621 :
1622 : DEBUG_FUNCTION void
1623 0 : debug_candidate (int i)
1624 : {
1625 0 : if (!candidate_table[i].is_valid)
1626 : return;
1627 :
1628 0 : if (candidate_table[i].is_speculative)
1629 : {
1630 0 : int j;
1631 0 : fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1632 :
1633 0 : fprintf (sched_dump, "split path: ");
1634 0 : for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1635 : {
1636 0 : int b = candidate_table[i].split_bbs.first_member[j]->index;
1637 :
1638 0 : fprintf (sched_dump, " %d ", b);
1639 : }
1640 0 : fprintf (sched_dump, "\n");
1641 :
1642 0 : fprintf (sched_dump, "update path: ");
1643 0 : for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
1644 : {
1645 0 : int b = candidate_table[i].update_bbs.first_member[j]->index;
1646 :
1647 0 : fprintf (sched_dump, " %d ", b);
1648 : }
1649 0 : fprintf (sched_dump, "\n");
1650 : }
1651 : else
1652 : {
1653 0 : fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
1654 : }
1655 : }
1656 :
1657 : /* Print candidates info, for debugging purposes. Callable from debugger. */
1658 :
1659 : DEBUG_FUNCTION void
1660 0 : debug_candidates (int trg)
1661 : {
1662 0 : int i;
1663 :
1664 0 : fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
1665 0 : BB_TO_BLOCK (trg), trg);
1666 0 : for (i = trg + 1; i < current_nr_blocks; i++)
1667 0 : debug_candidate (i);
1668 0 : }
1669 :
1670 : /* Functions for speculative scheduling. */
1671 :
1672 : static bitmap_head not_in_df;
1673 :
1674 : /* Return false if x is a set of a register alive in the beginning of one
1675 : of the split-blocks of src, otherwise return true. */
1676 :
1677 : static bool
1678 19 : check_live_1 (int src, rtx x)
1679 : {
1680 19 : int i;
1681 19 : int regno;
1682 19 : rtx reg = SET_DEST (x);
1683 :
1684 19 : if (reg == 0)
1685 : return true;
1686 :
1687 19 : while (GET_CODE (reg) == SUBREG
1688 19 : || GET_CODE (reg) == ZERO_EXTRACT
1689 38 : || GET_CODE (reg) == STRICT_LOW_PART)
1690 0 : reg = XEXP (reg, 0);
1691 :
1692 19 : if (GET_CODE (reg) == PARALLEL)
1693 : {
1694 0 : int i;
1695 :
1696 0 : for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1697 0 : if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1698 0 : if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
1699 : return true;
1700 :
1701 : return false;
1702 : }
1703 :
1704 19 : if (!REG_P (reg))
1705 : return true;
1706 :
1707 16 : regno = REGNO (reg);
1708 :
1709 16 : if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1710 : {
1711 : /* Global registers are assumed live. */
1712 : return false;
1713 : }
1714 : else
1715 : {
1716 16 : if (regno < FIRST_PSEUDO_REGISTER)
1717 : {
1718 : /* Check for hard registers. */
1719 12 : int j = REG_NREGS (reg);
1720 24 : while (--j >= 0)
1721 : {
1722 24 : for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1723 : {
1724 12 : basic_block b = candidate_table[src].split_bbs.first_member[i];
1725 12 : int t = bitmap_bit_p (¬_in_df, b->index);
1726 :
1727 : /* We can have split blocks, that were recently generated.
1728 : Such blocks are always outside current region. */
1729 12 : gcc_assert (!t || (CONTAINING_RGN (b->index)
1730 : != CONTAINING_RGN (BB_TO_BLOCK (src))));
1731 :
1732 12 : if (t || REGNO_REG_SET_P (df_get_live_in (b), regno + j))
1733 : return false;
1734 : }
1735 : }
1736 : }
1737 : else
1738 : {
1739 : /* Check for pseudo registers. */
1740 8 : for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1741 : {
1742 5 : basic_block b = candidate_table[src].split_bbs.first_member[i];
1743 5 : int t = bitmap_bit_p (¬_in_df, b->index);
1744 :
1745 5 : gcc_assert (!t || (CONTAINING_RGN (b->index)
1746 : != CONTAINING_RGN (BB_TO_BLOCK (src))));
1747 :
1748 5 : if (t || REGNO_REG_SET_P (df_get_live_in (b), regno))
1749 : return false;
1750 : }
1751 : }
1752 : }
1753 :
1754 : return true;
1755 : }
1756 :
1757 : /* If x is a set of a register R, mark that R is alive in the beginning
1758 : of every update-block of src. */
1759 :
1760 : static void
1761 0 : update_live_1 (int src, rtx x)
1762 : {
1763 0 : int i;
1764 0 : int regno;
1765 0 : rtx reg = SET_DEST (x);
1766 :
1767 0 : if (reg == 0)
1768 : return;
1769 :
1770 0 : while (GET_CODE (reg) == SUBREG
1771 0 : || GET_CODE (reg) == ZERO_EXTRACT
1772 0 : || GET_CODE (reg) == STRICT_LOW_PART)
1773 0 : reg = XEXP (reg, 0);
1774 :
1775 0 : if (GET_CODE (reg) == PARALLEL)
1776 : {
1777 0 : int i;
1778 :
1779 0 : for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1780 0 : if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1781 0 : update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
1782 :
1783 : return;
1784 : }
1785 :
1786 0 : if (!REG_P (reg))
1787 : return;
1788 :
1789 : /* Global registers are always live, so the code below does not apply
1790 : to them. */
1791 :
1792 0 : regno = REGNO (reg);
1793 :
1794 0 : if (! HARD_REGISTER_NUM_P (regno)
1795 0 : || !global_regs[regno])
1796 : {
1797 0 : for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1798 : {
1799 0 : basic_block b = candidate_table[src].update_bbs.first_member[i];
1800 0 : bitmap_set_range (df_get_live_in (b), regno, REG_NREGS (reg));
1801 : }
1802 : }
1803 : }
1804 :
1805 : /* Return true if insn can be speculatively moved from block src to trg,
1806 : otherwise return false. Called before first insertion of insn to
1807 : ready-list or before the scheduling. */
1808 :
1809 : static bool
1810 35 : check_live (rtx_insn *insn, int src)
1811 : {
1812 : /* Find the registers set by instruction. */
1813 35 : if (GET_CODE (PATTERN (insn)) == SET
1814 35 : || GET_CODE (PATTERN (insn)) == CLOBBER)
1815 19 : return check_live_1 (src, PATTERN (insn));
1816 16 : else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1817 : {
1818 0 : int j;
1819 0 : for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1820 0 : if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1821 0 : || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1822 0 : && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
1823 : return false;
1824 :
1825 : return true;
1826 : }
1827 :
1828 : return true;
1829 : }
1830 :
1831 : /* Update the live registers info after insn was moved speculatively from
1832 : block src to trg. */
1833 :
1834 : static void
1835 8 : update_live (rtx_insn *insn, int src)
1836 : {
1837 : /* Find the registers set by instruction. */
1838 8 : if (GET_CODE (PATTERN (insn)) == SET
1839 8 : || GET_CODE (PATTERN (insn)) == CLOBBER)
1840 0 : update_live_1 (src, PATTERN (insn));
1841 8 : else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1842 : {
1843 0 : int j;
1844 0 : for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1845 0 : if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1846 0 : || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1847 0 : update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
1848 : }
1849 8 : }
1850 :
1851 : /* True if block bb_to is equal to, or reachable from block bb_from. */
1852 : #define IS_REACHABLE(bb_from, bb_to) \
1853 : (bb_from == bb_to \
1854 : || IS_RGN_ENTRY (bb_from) \
1855 : || (bitmap_bit_p \
1856 : (ancestor_edges[bb_to], \
1857 : EDGE_TO_BIT (single_pred_edge \
1858 : (BASIC_BLOCK_FOR_FN (cfun, \
1859 : BB_TO_BLOCK (bb_from)))))))
1860 :
1861 : /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1862 :
1863 : static void
1864 0 : set_spec_fed (rtx_insn *load_insn)
1865 : {
1866 0 : sd_iterator_def sd_it;
1867 0 : dep_t dep;
1868 :
1869 0 : FOR_EACH_DEP (load_insn, SD_LIST_FORW, sd_it, dep)
1870 0 : if (DEP_TYPE (dep) == REG_DEP_TRUE)
1871 0 : FED_BY_SPEC_LOAD (DEP_CON (dep)) = 1;
1872 0 : }
1873 :
1874 : /* On the path from the insn to load_insn_bb, find a conditional
1875 : branch depending on insn, that guards the speculative load. */
1876 :
1877 : static bool
1878 0 : find_conditional_protection (rtx_insn *insn, int load_insn_bb)
1879 : {
1880 0 : sd_iterator_def sd_it;
1881 0 : dep_t dep;
1882 :
1883 : /* Iterate through DEF-USE forward dependences. */
1884 0 : FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
1885 : {
1886 0 : rtx_insn *next = DEP_CON (dep);
1887 :
1888 0 : if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
1889 0 : CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
1890 0 : && IS_REACHABLE (INSN_BB (next), load_insn_bb)
1891 0 : && load_insn_bb != INSN_BB (next)
1892 0 : && DEP_TYPE (dep) == REG_DEP_TRUE
1893 0 : && (JUMP_P (next)
1894 0 : || find_conditional_protection (next, load_insn_bb)))
1895 : return true;
1896 : }
1897 : return false;
1898 : } /* find_conditional_protection */
1899 :
1900 : /* Returns true if the same insn1 that participates in the computation
1901 : of load_insn's address is feeding a conditional branch that is
1902 : guarding on load_insn. This is true if we find two DEF-USE
1903 : chains:
1904 : insn1 -> ... -> conditional-branch
1905 : insn1 -> ... -> load_insn,
1906 : and if a flow path exists:
1907 : insn1 -> ... -> conditional-branch -> ... -> load_insn,
1908 : and if insn1 is on the path
1909 : region-entry -> ... -> bb_trg -> ... load_insn.
1910 :
1911 : Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
1912 : Locate the branch by following INSN_FORW_DEPS from insn1. */
1913 :
1914 : static bool
1915 0 : is_conditionally_protected (rtx_insn *load_insn, int bb_src, int bb_trg)
1916 : {
1917 0 : sd_iterator_def sd_it;
1918 0 : dep_t dep;
1919 :
1920 0 : FOR_EACH_DEP (load_insn, SD_LIST_BACK, sd_it, dep)
1921 : {
1922 0 : rtx_insn *insn1 = DEP_PRO (dep);
1923 :
1924 : /* Must be a DEF-USE dependence upon non-branch. */
1925 0 : if (DEP_TYPE (dep) != REG_DEP_TRUE
1926 0 : || JUMP_P (insn1))
1927 0 : continue;
1928 :
1929 : /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1930 0 : if (INSN_BB (insn1) == bb_src
1931 0 : || (CONTAINING_RGN (BLOCK_NUM (insn1))
1932 0 : != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
1933 0 : || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
1934 0 : && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
1935 0 : continue;
1936 :
1937 : /* Now search for the conditional-branch. */
1938 0 : if (find_conditional_protection (insn1, bb_src))
1939 : return true;
1940 :
1941 : /* Recursive step: search another insn1, "above" current insn1. */
1942 0 : return is_conditionally_protected (insn1, bb_src, bb_trg);
1943 : }
1944 :
1945 : /* The chain does not exist. */
1946 : return false;
1947 : } /* is_conditionally_protected */
1948 :
1949 : /* Returns true if a clue for "similar load" 'insn2' is found, and hence
1950 : load_insn can move speculatively from bb_src to bb_trg. All the
1951 : following must hold:
1952 :
1953 : (1) both loads have 1 base register (PFREE_CANDIDATEs).
1954 : (2) load_insn and load1 have a def-use dependence upon
1955 : the same insn 'insn1'.
1956 : (3) either load2 is in bb_trg, or:
1957 : - there's only one split-block, and
1958 : - load1 is on the escape path, and
1959 :
1960 : From all these we can conclude that the two loads access memory
1961 : addresses that differ at most by a constant, and hence if moving
1962 : load_insn would cause an exception, it would have been caused by
1963 : load2 anyhow. */
1964 :
1965 : static bool
1966 0 : is_pfree (rtx_insn *load_insn, int bb_src, int bb_trg)
1967 : {
1968 0 : sd_iterator_def back_sd_it;
1969 0 : dep_t back_dep;
1970 0 : candidate *candp = candidate_table + bb_src;
1971 :
1972 0 : if (candp->split_bbs.nr_members != 1)
1973 : /* Must have exactly one escape block. */
1974 : return false;
1975 :
1976 0 : FOR_EACH_DEP (load_insn, SD_LIST_BACK, back_sd_it, back_dep)
1977 : {
1978 0 : rtx_insn *insn1 = DEP_PRO (back_dep);
1979 :
1980 0 : if (DEP_TYPE (back_dep) == REG_DEP_TRUE)
1981 : /* Found a DEF-USE dependence (insn1, load_insn). */
1982 : {
1983 0 : sd_iterator_def fore_sd_it;
1984 0 : dep_t fore_dep;
1985 :
1986 0 : FOR_EACH_DEP (insn1, SD_LIST_FORW, fore_sd_it, fore_dep)
1987 : {
1988 0 : rtx_insn *insn2 = DEP_CON (fore_dep);
1989 :
1990 0 : if (DEP_TYPE (fore_dep) == REG_DEP_TRUE)
1991 : {
1992 : /* Found a DEF-USE dependence (insn1, insn2). */
1993 0 : if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
1994 : /* insn2 not guaranteed to be a 1 base reg load. */
1995 0 : continue;
1996 :
1997 0 : if (INSN_BB (insn2) == bb_trg)
1998 : /* insn2 is the similar load, in the target block. */
1999 0 : return true;
2000 :
2001 0 : if (*(candp->split_bbs.first_member) == BLOCK_FOR_INSN (insn2))
2002 : /* insn2 is a similar load, in a split-block. */
2003 : return true;
2004 : }
2005 : }
2006 : }
2007 : }
2008 :
2009 : /* Couldn't find a similar load. */
2010 : return false;
2011 : } /* is_pfree */
2012 :
2013 : /* Return true if load_insn is prisky (i.e. if load_insn is fed by
2014 : a load moved speculatively, or if load_insn is protected by
2015 : a compare on load_insn's address). */
2016 :
2017 : static bool
2018 0 : is_prisky (rtx_insn *load_insn, int bb_src, int bb_trg)
2019 : {
2020 0 : if (FED_BY_SPEC_LOAD (load_insn))
2021 : return true;
2022 :
2023 0 : if (sd_lists_empty_p (load_insn, SD_LIST_BACK))
2024 : /* Dependence may 'hide' out of the region. */
2025 : return true;
2026 :
2027 0 : if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2028 : return true;
2029 :
2030 : return false;
2031 : }
2032 :
2033 : /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2034 : Return true if insn is exception-free (and the motion is valid)
2035 : and false otherwise. */
2036 :
2037 : static bool
2038 26 : is_exception_free (rtx_insn *insn, int bb_src, int bb_trg)
2039 : {
2040 26 : int insn_class = haifa_classify_insn (insn);
2041 :
2042 : /* Handle non-load insns. */
2043 26 : switch (insn_class)
2044 : {
2045 : case TRAP_FREE:
2046 : return true;
2047 : case TRAP_RISKY:
2048 : return false;
2049 3 : default:;
2050 : }
2051 :
2052 : /* Handle loads. */
2053 3 : if (!flag_schedule_speculative_load)
2054 : return false;
2055 0 : IS_LOAD_INSN (insn) = 1;
2056 0 : switch (insn_class)
2057 : {
2058 : case IFREE:
2059 : return true;
2060 : case IRISKY:
2061 : return false;
2062 0 : case PFREE_CANDIDATE:
2063 0 : if (is_pfree (insn, bb_src, bb_trg))
2064 : return true;
2065 : /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2066 : /* FALLTHRU */
2067 0 : case PRISKY_CANDIDATE:
2068 0 : if (!flag_schedule_speculative_load_dangerous
2069 0 : || is_prisky (insn, bb_src, bb_trg))
2070 : return false;
2071 : break;
2072 0 : default:;
2073 : }
2074 :
2075 0 : return flag_schedule_speculative_load_dangerous;
2076 : }
2077 :
2078 : /* The number of insns from the current block scheduled so far. */
2079 : static int sched_target_n_insns;
2080 : /* The number of insns from the current block to be scheduled in total. */
2081 : static int target_n_insns;
2082 : /* The number of insns from the entire region scheduled so far. */
2083 : static int sched_n_insns;
2084 :
2085 : /* Implementations of the sched_info functions for region scheduling. */
2086 : static void init_ready_list (void);
2087 : static bool can_schedule_ready_p (rtx_insn *);
2088 : static void begin_schedule_ready (rtx_insn *);
2089 : static ds_t new_ready (rtx_insn *, ds_t);
2090 : static bool schedule_more_p (void);
2091 : static const char *rgn_print_insn (const rtx_insn *, int);
2092 : static int rgn_rank (rtx_insn *, rtx_insn *);
2093 : static void compute_jump_reg_dependencies (rtx_insn *, regset);
2094 :
2095 : /* Functions for speculative scheduling. */
2096 : static void rgn_add_remove_insn (rtx_insn *, int);
2097 : static void rgn_add_block (basic_block, basic_block);
2098 : static void rgn_fix_recovery_cfg (int, int, int);
2099 : static basic_block advance_target_bb (basic_block, rtx_insn *);
2100 :
2101 : /* Return true if there are more insns that should be scheduled. */
2102 :
2103 : static bool
2104 114575395 : schedule_more_p (void)
2105 : {
2106 114575395 : return sched_target_n_insns < target_n_insns;
2107 : }
2108 :
2109 : /* Add all insns that are initially ready to the ready list READY. Called
2110 : once before scheduling a set of insns. */
2111 :
2112 : static void
2113 10497928 : init_ready_list (void)
2114 : {
2115 10497928 : rtx_insn *prev_head = current_sched_info->prev_head;
2116 10497928 : rtx_insn *next_tail = current_sched_info->next_tail;
2117 10497928 : int bb_src;
2118 10497928 : rtx_insn *insn;
2119 :
2120 10497928 : target_n_insns = 0;
2121 10497928 : sched_target_n_insns = 0;
2122 10497928 : sched_n_insns = 0;
2123 :
2124 : /* Print debugging information. */
2125 10497928 : if (sched_verbose >= 5)
2126 0 : debug_rgn_dependencies (target_bb);
2127 :
2128 : /* Prepare current target block info. */
2129 10497928 : if (current_nr_blocks > 1)
2130 72 : compute_trg_info (target_bb);
2131 :
2132 : /* Initialize ready list with all 'ready' insns in target block.
2133 : Count number of insns in the target block being scheduled. */
2134 134620577 : for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
2135 : {
2136 113624721 : gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
2137 113624721 : TODO_SPEC (insn) = HARD_DEP;
2138 113624721 : try_ready (insn);
2139 113624721 : target_n_insns++;
2140 :
2141 113624721 : gcc_assert (!(TODO_SPEC (insn) & BEGIN_CONTROL));
2142 : }
2143 :
2144 : /* Add to ready list all 'ready' insns in valid source blocks.
2145 : For speculative insns, check-live, exception-free, and
2146 : issue-delay. */
2147 10498010 : for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
2148 82 : if (IS_VALID (bb_src))
2149 : {
2150 51 : rtx_insn *src_head;
2151 51 : rtx_insn *src_next_tail;
2152 51 : rtx_insn *tail, *head;
2153 :
2154 51 : get_ebb_head_tail (EBB_FIRST_BB (bb_src), EBB_LAST_BB (bb_src),
2155 : &head, &tail);
2156 51 : src_next_tail = NEXT_INSN (tail);
2157 51 : src_head = head;
2158 :
2159 712 : for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
2160 661 : if (INSN_P (insn))
2161 : {
2162 637 : gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
2163 637 : TODO_SPEC (insn) = HARD_DEP;
2164 637 : try_ready (insn);
2165 : }
2166 : }
2167 10497928 : }
2168 :
2169 : /* Called after taking INSN from the ready list. Returns true if this
2170 : insn can be scheduled, nonzero if we should silently discard it. */
2171 :
2172 : static bool
2173 61628620 : can_schedule_ready_p (rtx_insn *insn)
2174 : {
2175 : /* An interblock motion? */
2176 61628620 : if (INSN_BB (insn) != target_bb && IS_SPECULATIVE_INSN (insn))
2177 : {
2178 : /* Cannot schedule this insn unless all operands are live. */
2179 0 : if (!check_live (insn, INSN_BB (insn)))
2180 : return false;
2181 :
2182 : /* Should not move expensive instructions speculatively. */
2183 0 : if (GET_CODE (PATTERN (insn)) != CLOBBER
2184 0 : && !targetm.sched.can_speculate_insn (insn))
2185 : return false;
2186 : }
2187 :
2188 : return true;
2189 : }
2190 :
2191 : /* Updates counter and other information. Split from can_schedule_ready_p ()
2192 : because when we schedule insn speculatively then insn passed to
2193 : can_schedule_ready_p () differs from the one passed to
2194 : begin_schedule_ready (). */
2195 : static void
2196 113624729 : begin_schedule_ready (rtx_insn *insn)
2197 : {
2198 : /* An interblock motion? */
2199 113624729 : if (INSN_BB (insn) != target_bb)
2200 : {
2201 8 : if (IS_SPECULATIVE_INSN (insn))
2202 : {
2203 8 : gcc_assert (check_live (insn, INSN_BB (insn)));
2204 :
2205 8 : update_live (insn, INSN_BB (insn));
2206 :
2207 : /* For speculative load, mark insns fed by it. */
2208 8 : if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
2209 0 : set_spec_fed (insn);
2210 :
2211 8 : nr_spec++;
2212 : }
2213 8 : nr_inter++;
2214 : }
2215 : else
2216 : {
2217 : /* In block motion. */
2218 113624721 : sched_target_n_insns++;
2219 : }
2220 113624729 : sched_n_insns++;
2221 113624729 : }
2222 :
2223 : /* Called after INSN has all its hard dependencies resolved and the speculation
2224 : of type TS is enough to overcome them all.
2225 : Return nonzero if it should be moved to the ready list or the queue, or zero
2226 : if we should silently discard it. */
2227 : static ds_t
2228 113624777 : new_ready (rtx_insn *next, ds_t ts)
2229 : {
2230 113624777 : if (INSN_BB (next) != target_bb)
2231 : {
2232 56 : int not_ex_free = 0;
2233 :
2234 : /* For speculative insns, before inserting to ready/queue,
2235 : check live, exception-free, and issue-delay. */
2236 56 : if (!IS_VALID (INSN_BB (next))
2237 40 : || CANT_MOVE (next)
2238 110 : || (IS_SPECULATIVE_INSN (next)
2239 27 : && ((recog_memoized (next) >= 0
2240 19 : && min_insn_conflict_delay (curr_state, next, next)
2241 19 : > param_max_sched_insn_conflict_delay)
2242 27 : || IS_SPECULATION_CHECK_P (next)
2243 27 : || !check_live (next, INSN_BB (next))
2244 26 : || (not_ex_free = !is_exception_free (next, INSN_BB (next),
2245 : target_bb)))))
2246 : {
2247 36 : if (not_ex_free
2248 : /* We are here because is_exception_free () == false.
2249 : But we possibly can handle that with control speculation. */
2250 6 : && sched_deps_info->generate_spec_deps
2251 0 : && spec_info->mask & BEGIN_CONTROL)
2252 : {
2253 0 : ds_t new_ds;
2254 :
2255 : /* Add control speculation to NEXT's dependency type. */
2256 0 : new_ds = set_dep_weak (ts, BEGIN_CONTROL, MAX_DEP_WEAK);
2257 :
2258 : /* Check if NEXT can be speculated with new dependency type. */
2259 0 : if (sched_insn_is_legitimate_for_speculation_p (next, new_ds))
2260 : /* Here we got new control-speculative instruction. */
2261 : ts = new_ds;
2262 : else
2263 : /* NEXT isn't ready yet. */
2264 36 : ts = DEP_POSTPONED;
2265 : }
2266 : else
2267 : /* NEXT isn't ready yet. */
2268 : ts = DEP_POSTPONED;
2269 : }
2270 : }
2271 :
2272 113624777 : return ts;
2273 : }
2274 :
2275 : /* Return a string that contains the insn uid and optionally anything else
2276 : necessary to identify this insn in an output. It's valid to use a
2277 : static buffer for this. The ALIGNED parameter should cause the string
2278 : to be formatted so that multiple output lines will line up nicely. */
2279 :
2280 : static const char *
2281 987 : rgn_print_insn (const rtx_insn *insn, int aligned)
2282 : {
2283 987 : static char tmp[80];
2284 :
2285 987 : if (aligned)
2286 987 : sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
2287 : else
2288 : {
2289 0 : if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
2290 0 : sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
2291 : else
2292 0 : sprintf (tmp, "%d", INSN_UID (insn));
2293 : }
2294 987 : return tmp;
2295 : }
2296 :
2297 : /* Compare priority of two insns. Return a positive number if the second
2298 : insn is to be preferred for scheduling, and a negative one if the first
2299 : is to be preferred. Zero if they are equally good. */
2300 :
2301 : static int
2302 252224813 : rgn_rank (rtx_insn *insn1, rtx_insn *insn2)
2303 : {
2304 : /* Some comparison make sense in interblock scheduling only. */
2305 252224813 : if (INSN_BB (insn1) != INSN_BB (insn2))
2306 : {
2307 0 : int spec_val, prob_val;
2308 :
2309 : /* Prefer an inblock motion on an interblock motion. */
2310 0 : if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
2311 : return 1;
2312 0 : if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
2313 : return -1;
2314 :
2315 : /* Prefer a useful motion on a speculative one. */
2316 0 : spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
2317 0 : if (spec_val)
2318 : return spec_val;
2319 :
2320 : /* Prefer a more probable (speculative) insn. */
2321 0 : prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
2322 0 : if (prob_val)
2323 : return prob_val;
2324 : }
2325 : return 0;
2326 : }
2327 :
2328 : /* NEXT is an instruction that depends on INSN (a backward dependence);
2329 : return true if we should include this dependence in priority
2330 : calculations. */
2331 :
2332 : bool
2333 147146164 : contributes_to_priority (rtx_insn *next, rtx_insn *insn)
2334 : {
2335 : /* NEXT and INSN reside in one ebb. */
2336 147146164 : return BLOCK_TO_BB (BLOCK_NUM (next)) == BLOCK_TO_BB (BLOCK_NUM (insn));
2337 : }
2338 :
2339 : /* INSN is a JUMP_INSN. Store the set of registers that must be
2340 : considered as used by this jump in USED. */
2341 :
2342 : static void
2343 4891438 : compute_jump_reg_dependencies (rtx_insn *insn ATTRIBUTE_UNUSED,
2344 : regset used ATTRIBUTE_UNUSED)
2345 : {
2346 : /* Nothing to do here, since we postprocess jumps in
2347 : add_branch_dependences. */
2348 4891438 : }
2349 :
2350 : /* This variable holds common_sched_info hooks and data relevant to
2351 : the interblock scheduler. */
2352 : static struct common_sched_info_def rgn_common_sched_info;
2353 :
2354 :
2355 : /* This holds data for the dependence analysis relevant to
2356 : the interblock scheduler. */
2357 : static struct sched_deps_info_def rgn_sched_deps_info;
2358 :
2359 : /* This holds constant data used for initializing the above structure
2360 : for the Haifa scheduler. */
2361 : static const struct sched_deps_info_def rgn_const_sched_deps_info =
2362 : {
2363 : compute_jump_reg_dependencies,
2364 : NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
2365 : 0, 0, 0
2366 : };
2367 :
2368 : /* Same as above, but for the selective scheduler. */
2369 : static const struct sched_deps_info_def rgn_const_sel_sched_deps_info =
2370 : {
2371 : compute_jump_reg_dependencies,
2372 : NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
2373 : 0, 0, 0
2374 : };
2375 :
2376 : /* Return true if scheduling INSN will trigger finish of scheduling
2377 : current block. */
2378 : static bool
2379 115386557 : rgn_insn_finishes_block_p (rtx_insn *insn)
2380 : {
2381 115386557 : if (INSN_BB (insn) == target_bb
2382 115386557 : && sched_target_n_insns + 1 == target_n_insns)
2383 : /* INSN is the last not-scheduled instruction in the current block. */
2384 5975716 : return true;
2385 :
2386 : return false;
2387 : }
2388 :
2389 : /* Used in schedule_insns to initialize current_sched_info for scheduling
2390 : regions (or single basic blocks). */
2391 :
2392 : static const struct haifa_sched_info rgn_const_sched_info =
2393 : {
2394 : init_ready_list,
2395 : can_schedule_ready_p,
2396 : schedule_more_p,
2397 : new_ready,
2398 : rgn_rank,
2399 : rgn_print_insn,
2400 : contributes_to_priority,
2401 : rgn_insn_finishes_block_p,
2402 :
2403 : NULL, NULL,
2404 : NULL, NULL,
2405 : 0, 0,
2406 :
2407 : rgn_add_remove_insn,
2408 : begin_schedule_ready,
2409 : NULL,
2410 : advance_target_bb,
2411 : NULL, NULL,
2412 : SCHED_RGN
2413 : };
2414 :
2415 : /* This variable holds the data and hooks needed to the Haifa scheduler backend
2416 : for the interblock scheduler frontend. */
2417 : static struct haifa_sched_info rgn_sched_info;
2418 :
2419 : /* Returns maximum priority that an insn was assigned to. */
2420 :
2421 : int
2422 849 : get_rgn_sched_max_insns_priority (void)
2423 : {
2424 849 : return rgn_sched_info.sched_max_insns_priority;
2425 : }
2426 :
2427 : /* Determine if PAT sets a TARGET_CLASS_LIKELY_SPILLED_P register. */
2428 :
2429 : static bool
2430 1757 : sets_likely_spilled (rtx pat)
2431 : {
2432 1757 : bool ret = false;
2433 0 : note_pattern_stores (pat, sets_likely_spilled_1, &ret);
2434 1757 : return ret;
2435 : }
2436 :
2437 : static void
2438 2090 : sets_likely_spilled_1 (rtx x, const_rtx pat, void *data)
2439 : {
2440 2090 : bool *ret = (bool *) data;
2441 :
2442 2090 : if (GET_CODE (pat) == SET
2443 1862 : && REG_P (x)
2444 1711 : && HARD_REGISTER_P (x)
2445 3114 : && targetm.class_likely_spilled_p (REGNO_REG_CLASS (REGNO (x))))
2446 342 : *ret = true;
2447 2090 : }
2448 :
2449 : /* A bitmap to note insns that participate in any dependency. Used in
2450 : add_branch_dependences. */
2451 : static sbitmap insn_referenced;
2452 :
2453 : /* Add dependences so that branches are scheduled to run last in their
2454 : block. */
2455 : static void
2456 10517854 : add_branch_dependences (rtx_insn *head, rtx_insn *tail)
2457 : {
2458 10517854 : rtx_insn *insn, *last;
2459 :
2460 : /* For all branches, calls, uses, clobbers, and instructions
2461 : that can throw exceptions, force them to remain in order at the end of
2462 : the block by adding dependencies and giving the last a high priority.
2463 : There may be notes present, and prev_head may also be a note.
2464 :
2465 : Branches must obviously remain at the end. Calls should remain at the
2466 : end since moving them results in worse register allocation. Uses remain
2467 : at the end to ensure proper register allocation.
2468 :
2469 : Predecessors of SCHED_GROUP_P instructions at the end remain at the end.
2470 :
2471 : COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
2472 :
2473 : Insns setting TARGET_CLASS_LIKELY_SPILLED_P registers (usually return
2474 : values) are not moved before reload because we can wind up with register
2475 : allocation failures. */
2476 :
2477 12186989 : while (tail != head && DEBUG_INSN_P (tail))
2478 1669135 : tail = PREV_INSN (tail);
2479 :
2480 : insn = tail;
2481 : last = 0;
2482 24472688 : while (CALL_P (insn)
2483 24472688 : || JUMP_P (insn) || JUMP_TABLE_DATA_P (insn)
2484 14785679 : || (NONJUMP_INSN_P (insn)
2485 13129824 : && (GET_CODE (PATTERN (insn)) == USE
2486 12838235 : || GET_CODE (PATTERN (insn)) == CLOBBER
2487 12835927 : || can_throw_internal (insn)
2488 12728548 : || (!reload_completed
2489 1757 : && sets_likely_spilled (PATTERN (insn)))))
2490 14384061 : || NOTE_P (insn)
2491 37639488 : || (last != 0 && SCHED_GROUP_P (last)))
2492 : {
2493 15515838 : if (!NOTE_P (insn))
2494 : {
2495 14298577 : if (last != 0
2496 14298577 : && sd_find_dep_between (insn, last, false) == NULL)
2497 : {
2498 20085 : if (! sched_insns_conditions_mutex_p (last, insn))
2499 20085 : add_dependence (last, insn, REG_DEP_ANTI);
2500 20085 : bitmap_set_bit (insn_referenced, INSN_LUID (insn));
2501 : }
2502 :
2503 14298577 : CANT_MOVE (insn) = 1;
2504 :
2505 14298577 : last = insn;
2506 : }
2507 :
2508 : /* Don't overrun the bounds of the basic block. */
2509 15515838 : if (insn == head)
2510 : break;
2511 :
2512 22685899 : do
2513 22685899 : insn = PREV_INSN (insn);
2514 22685899 : while (insn != head && DEBUG_INSN_P (insn));
2515 : }
2516 :
2517 : /* Selective scheduling handles control dependencies by itself, and
2518 : CANT_MOVE flags ensure that other insns will be kept in place. */
2519 10517854 : if (sel_sched_p ())
2520 : return;
2521 :
2522 : /* Make sure these insns are scheduled last in their block. */
2523 10516849 : insn = last;
2524 10516849 : if (insn != 0)
2525 95490245 : while (insn != head)
2526 : {
2527 86320873 : insn = prev_nonnote_insn (insn);
2528 :
2529 86320873 : if (bitmap_bit_p (insn_referenced, INSN_LUID (insn))
2530 86320873 : || DEBUG_INSN_P (insn))
2531 45256277 : continue;
2532 :
2533 41064596 : if (! sched_insns_conditions_mutex_p (last, insn))
2534 41064596 : add_dependence (last, insn, REG_DEP_ANTI);
2535 : }
2536 :
2537 10516849 : if (!targetm.have_conditional_execution ())
2538 : return;
2539 :
2540 : /* Finally, if the block ends in a jump, and we are doing intra-block
2541 : scheduling, make sure that the branch depends on any COND_EXEC insns
2542 : inside the block to avoid moving the COND_EXECs past the branch insn.
2543 :
2544 : We only have to do this after reload, because (1) before reload there
2545 : are no COND_EXEC insns, and (2) the region scheduler is an intra-block
2546 : scheduler after reload.
2547 :
2548 : FIXME: We could in some cases move COND_EXEC insns past the branch if
2549 : this scheduler would be a little smarter. Consider this code:
2550 :
2551 : T = [addr]
2552 : C ? addr += 4
2553 : !C ? X += 12
2554 : C ? T += 1
2555 : C ? jump foo
2556 :
2557 : On a target with a one cycle stall on a memory access the optimal
2558 : sequence would be:
2559 :
2560 : T = [addr]
2561 : C ? addr += 4
2562 : C ? T += 1
2563 : C ? jump foo
2564 : !C ? X += 12
2565 :
2566 : We don't want to put the 'X += 12' before the branch because it just
2567 : wastes a cycle of execution time when the branch is taken.
2568 :
2569 : Note that in the example "!C" will always be true. That is another
2570 : possible improvement for handling COND_EXECs in this scheduler: it
2571 : could remove always-true predicates. */
2572 :
2573 0 : if (!reload_completed || ! (JUMP_P (tail) || JUMP_TABLE_DATA_P (tail)))
2574 : return;
2575 :
2576 : insn = tail;
2577 0 : while (insn != head)
2578 : {
2579 0 : insn = PREV_INSN (insn);
2580 :
2581 : /* Note that we want to add this dependency even when
2582 : sched_insns_conditions_mutex_p returns true. The whole point
2583 : is that we _want_ this dependency, even if these insns really
2584 : are independent. */
2585 0 : if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC)
2586 0 : add_dependence (tail, insn, REG_DEP_ANTI);
2587 : }
2588 : }
2589 :
2590 : /* Data structures for the computation of data dependences in a regions. We
2591 : keep one `deps' structure for every basic block. Before analyzing the
2592 : data dependences for a bb, its variables are initialized as a function of
2593 : the variables of its predecessors. When the analysis for a bb completes,
2594 : we save the contents to the corresponding bb_deps[bb] variable. */
2595 :
2596 : static class deps_desc *bb_deps;
2597 :
2598 : static void
2599 1142 : concat_insn_mem_list (rtx_insn_list *copy_insns,
2600 : rtx_expr_list *copy_mems,
2601 : rtx_insn_list **old_insns_p,
2602 : rtx_expr_list **old_mems_p)
2603 : {
2604 1142 : rtx_insn_list *new_insns = *old_insns_p;
2605 1142 : rtx_expr_list *new_mems = *old_mems_p;
2606 :
2607 2116 : while (copy_insns)
2608 : {
2609 974 : new_insns = alloc_INSN_LIST (copy_insns->insn (), new_insns);
2610 974 : new_mems = alloc_EXPR_LIST (VOIDmode, copy_mems->element (), new_mems);
2611 974 : copy_insns = copy_insns->next ();
2612 974 : copy_mems = copy_mems->next ();
2613 : }
2614 :
2615 1142 : *old_insns_p = new_insns;
2616 1142 : *old_mems_p = new_mems;
2617 1142 : }
2618 :
2619 : /* Join PRED_DEPS to the SUCC_DEPS. */
2620 : void
2621 571 : deps_join (class deps_desc *succ_deps, class deps_desc *pred_deps)
2622 : {
2623 571 : unsigned reg;
2624 571 : reg_set_iterator rsi;
2625 :
2626 : /* Registers that PRED has not materialised carry PRED's pending barriers as
2627 : their sets list, so fold those into the ones SUCC has materialised before
2628 : the main loop, and into SUCC's own pending list afterwards. */
2629 571 : if (pred_deps->pending_barriers)
2630 43 : EXECUTE_IF_AND_COMPL_IN_REG_SET (&succ_deps->reg_last_in_use,
2631 : &pred_deps->reg_last_in_use,
2632 : 0, reg, rsi)
2633 : {
2634 4 : struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
2635 4 : succ_rl->sets = concat_INSN_LIST (pred_deps->pending_barriers,
2636 : succ_rl->sets);
2637 : }
2638 :
2639 : /* The reg_last lists are inherited by successor. */
2640 20730 : EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi)
2641 : {
2642 20159 : struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
2643 20159 : struct deps_reg *succ_rl = deps_reg_last (succ_deps, reg);
2644 :
2645 20159 : succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
2646 20159 : succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
2647 20159 : succ_rl->implicit_sets
2648 20159 : = concat_INSN_LIST (pred_rl->implicit_sets, succ_rl->implicit_sets);
2649 20159 : succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
2650 : succ_rl->clobbers);
2651 20159 : succ_rl->uses_length += pred_rl->uses_length;
2652 20159 : succ_rl->clobbers_length += pred_rl->clobbers_length;
2653 : }
2654 571 : IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
2655 :
2656 : /* Registers neither side has materialised keep both pending lists. */
2657 571 : succ_deps->pending_barriers
2658 571 : = concat_INSN_LIST (pred_deps->pending_barriers,
2659 : succ_deps->pending_barriers);
2660 :
2661 : /* Mem read/write lists are inherited by successor. */
2662 571 : concat_insn_mem_list (pred_deps->pending_read_insns,
2663 : pred_deps->pending_read_mems,
2664 : &succ_deps->pending_read_insns,
2665 : &succ_deps->pending_read_mems);
2666 571 : concat_insn_mem_list (pred_deps->pending_write_insns,
2667 : pred_deps->pending_write_mems,
2668 : &succ_deps->pending_write_insns,
2669 : &succ_deps->pending_write_mems);
2670 :
2671 571 : succ_deps->pending_jump_insns
2672 571 : = concat_INSN_LIST (pred_deps->pending_jump_insns,
2673 : succ_deps->pending_jump_insns);
2674 571 : succ_deps->last_pending_memory_flush
2675 571 : = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
2676 : succ_deps->last_pending_memory_flush);
2677 :
2678 571 : succ_deps->pending_read_list_length += pred_deps->pending_read_list_length;
2679 571 : succ_deps->pending_write_list_length += pred_deps->pending_write_list_length;
2680 571 : succ_deps->pending_flush_length += pred_deps->pending_flush_length;
2681 :
2682 : /* last_function_call is inherited by successor. */
2683 571 : succ_deps->last_function_call
2684 571 : = concat_INSN_LIST (pred_deps->last_function_call,
2685 : succ_deps->last_function_call);
2686 :
2687 : /* last_function_call_may_noreturn is inherited by successor. */
2688 571 : succ_deps->last_function_call_may_noreturn
2689 571 : = concat_INSN_LIST (pred_deps->last_function_call_may_noreturn,
2690 : succ_deps->last_function_call_may_noreturn);
2691 :
2692 : /* sched_before_next_call is inherited by successor. */
2693 571 : succ_deps->sched_before_next_call
2694 571 : = concat_INSN_LIST (pred_deps->sched_before_next_call,
2695 : succ_deps->sched_before_next_call);
2696 571 : }
2697 :
2698 : /* After computing the dependencies for block BB, propagate the dependencies
2699 : found in TMP_DEPS to the successors of the block. */
2700 : static void
2701 444 : propagate_deps (int bb, class deps_desc *pred_deps)
2702 : {
2703 444 : basic_block block = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb));
2704 444 : edge_iterator ei;
2705 444 : edge e;
2706 :
2707 : /* bb's structures are inherited by its successors. */
2708 1200 : FOR_EACH_EDGE (e, ei, block->succs)
2709 : {
2710 : /* Only bbs "below" bb, in the same region, are interesting. */
2711 756 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2712 754 : || CONTAINING_RGN (block->index) != CONTAINING_RGN (e->dest->index)
2713 499 : || BLOCK_TO_BB (e->dest->index) <= bb)
2714 355 : continue;
2715 :
2716 401 : deps_join (bb_deps + BLOCK_TO_BB (e->dest->index), pred_deps);
2717 : }
2718 :
2719 : /* These lists should point to the right place, for correct
2720 : freeing later. */
2721 444 : bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
2722 444 : bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
2723 444 : bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
2724 444 : bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
2725 444 : bb_deps[bb].pending_jump_insns = pred_deps->pending_jump_insns;
2726 :
2727 : /* Can't allow these to be freed twice. */
2728 444 : pred_deps->pending_read_insns = 0;
2729 444 : pred_deps->pending_read_mems = 0;
2730 444 : pred_deps->pending_write_insns = 0;
2731 444 : pred_deps->pending_write_mems = 0;
2732 444 : pred_deps->pending_jump_insns = 0;
2733 444 : }
2734 :
2735 : /* Compute dependences inside bb. In a multiple blocks region:
2736 : (1) a bb is analyzed after its predecessors, and (2) the lists in
2737 : effect at the end of bb (after analyzing for bb) are inherited by
2738 : bb's successors.
2739 :
2740 : Specifically for reg-reg data dependences, the block insns are
2741 : scanned by sched_analyze () top-to-bottom. Three lists are
2742 : maintained by sched_analyze (): reg_last[].sets for register DEFs,
2743 : reg_last[].implicit_sets for implicit hard register DEFs, and
2744 : reg_last[].uses for register USEs.
2745 :
2746 : When analysis is completed for bb, we update for its successors:
2747 : ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2748 : ; - IMPLICIT_DEFS[succ] = Union (IMPLICIT_DEFS [succ], IMPLICIT_DEFS [bb])
2749 : ; - USES[succ] = Union (USES [succ], DEFS [bb])
2750 :
2751 : The mechanism for computing mem-mem data dependence is very
2752 : similar, and the result is interblock dependences in the region. */
2753 :
2754 : static void
2755 10517854 : compute_block_dependences (int bb)
2756 : {
2757 10517854 : rtx_insn *head, *tail;
2758 10517854 : class deps_desc tmp_deps;
2759 :
2760 10517854 : tmp_deps = bb_deps[bb];
2761 :
2762 : /* Do the analysis for this block. */
2763 10517854 : gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2764 10517854 : get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2765 :
2766 10517854 : sched_analyze (&tmp_deps, head, tail);
2767 :
2768 10517854 : add_branch_dependences (head, tail);
2769 :
2770 10517854 : if (current_nr_blocks > 1)
2771 444 : propagate_deps (bb, &tmp_deps);
2772 :
2773 : /* Free up the INSN_LISTs. */
2774 10517854 : free_deps (&tmp_deps);
2775 :
2776 10517854 : if (targetm.sched.dependencies_evaluation_hook)
2777 10517854 : targetm.sched.dependencies_evaluation_hook (head, tail);
2778 10517854 : }
2779 :
2780 : /* Free dependencies of instructions inside BB. */
2781 : static void
2782 10516849 : free_block_dependencies (int bb)
2783 : {
2784 10516849 : rtx_insn *head;
2785 10516849 : rtx_insn *tail;
2786 :
2787 10516849 : get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2788 :
2789 10516849 : if (no_real_insns_p (head, tail))
2790 : return;
2791 :
2792 10497928 : sched_free_deps (head, tail, true);
2793 : }
2794 :
2795 : /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2796 : them to the unused_*_list variables, so that they can be reused. */
2797 :
2798 : static void
2799 10517518 : free_pending_lists (void)
2800 : {
2801 10517518 : int bb;
2802 :
2803 21035372 : for (bb = 0; bb < current_nr_blocks; bb++)
2804 : {
2805 10517854 : free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
2806 10517854 : free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
2807 10517854 : free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
2808 10517854 : free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
2809 10517854 : free_INSN_LIST_list (&bb_deps[bb].pending_jump_insns);
2810 : }
2811 10517518 : }
2812 :
2813 : /* Print dependences for debugging starting from FROM_BB.
2814 : Callable from debugger. */
2815 : /* Print dependences for debugging starting from FROM_BB.
2816 : Callable from debugger. */
2817 : DEBUG_FUNCTION void
2818 0 : debug_rgn_dependencies (int from_bb)
2819 : {
2820 0 : int bb;
2821 :
2822 0 : fprintf (sched_dump,
2823 : ";; --------------- forward dependences: ------------ \n");
2824 :
2825 0 : for (bb = from_bb; bb < current_nr_blocks; bb++)
2826 : {
2827 0 : rtx_insn *head, *tail;
2828 :
2829 0 : get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2830 0 : fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
2831 0 : BB_TO_BLOCK (bb), bb);
2832 :
2833 0 : debug_dependencies (head, tail);
2834 : }
2835 0 : }
2836 :
2837 : /* Print dependencies information for instructions between HEAD and TAIL.
2838 : ??? This function would probably fit best in haifa-sched.cc. */
2839 0 : void debug_dependencies (rtx_insn *head, rtx_insn *tail)
2840 : {
2841 0 : rtx_insn *insn;
2842 0 : rtx_insn *next_tail = NEXT_INSN (tail);
2843 :
2844 0 : fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2845 : "insn", "code", "bb", "dep", "prio", "cost",
2846 : "reservation");
2847 0 : fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2848 : "----", "----", "--", "---", "----", "----",
2849 : "-----------");
2850 :
2851 0 : for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2852 : {
2853 0 : if (! INSN_P (insn))
2854 : {
2855 0 : int n;
2856 0 : fprintf (sched_dump, ";; %6d ", INSN_UID (insn));
2857 0 : if (NOTE_P (insn))
2858 : {
2859 0 : n = NOTE_KIND (insn);
2860 0 : fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
2861 : }
2862 : else
2863 0 : fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
2864 0 : continue;
2865 0 : }
2866 :
2867 0 : fprintf (sched_dump,
2868 : ";; %s%5d%6d%6d%6d%6d%6d ",
2869 0 : (SCHED_GROUP_P (insn) ? "+" : " "),
2870 0 : INSN_UID (insn),
2871 : INSN_CODE (insn),
2872 0 : BLOCK_NUM (insn),
2873 0 : sched_emulate_haifa_p ? -1 : sd_lists_size (insn, SD_LIST_BACK),
2874 0 : (sel_sched_p () ? (sched_emulate_haifa_p ? -1
2875 0 : : INSN_PRIORITY (insn))
2876 0 : : INSN_PRIORITY (insn)),
2877 0 : (sel_sched_p () ? (sched_emulate_haifa_p ? -1
2878 0 : : insn_sched_cost (insn))
2879 0 : : insn_sched_cost (insn)));
2880 :
2881 0 : if (recog_memoized (insn) < 0)
2882 0 : fprintf (sched_dump, "nothing");
2883 : else
2884 0 : print_reservation (sched_dump, insn);
2885 :
2886 0 : fprintf (sched_dump, "\t: FW:");
2887 0 : {
2888 0 : sd_iterator_def sd_it;
2889 0 : dep_t dep;
2890 :
2891 0 : FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
2892 0 : fprintf (sched_dump, " %d%s%s%s", INSN_UID (DEP_CON (dep)),
2893 0 : DEP_TYPE (dep) == REG_DEP_TRUE ? "t" : "",
2894 0 : DEP_NONREG (dep) ? "n" : "",
2895 0 : DEP_MULTIPLE (dep) ? "m" : "");
2896 0 : if (sched_verbose >= 5)
2897 : {
2898 0 : fprintf (sched_dump, "\n;;\t\t\t\t\t\t: BK:");
2899 0 : FOR_EACH_DEP (insn, SD_LIST_HARD_BACK, sd_it, dep)
2900 0 : fprintf (sched_dump, " %d%s%s%s", INSN_UID (DEP_PRO (dep)),
2901 0 : DEP_TYPE (dep) == REG_DEP_TRUE ? "t" : "",
2902 0 : DEP_NONREG (dep) ? "n" : "",
2903 0 : DEP_MULTIPLE (dep) ? "m" : "");
2904 : }
2905 : }
2906 0 : fprintf (sched_dump, "\n");
2907 : }
2908 :
2909 0 : fprintf (sched_dump, "\n");
2910 0 : }
2911 :
2912 : /* Dump dependency graph for the current region to a file using dot syntax. */
2913 :
2914 : void
2915 0 : dump_rgn_dependencies_dot (FILE *file)
2916 : {
2917 0 : rtx_insn *head, *tail, *con, *pro;
2918 0 : sd_iterator_def sd_it;
2919 0 : dep_t dep;
2920 0 : int bb;
2921 0 : pretty_printer pp;
2922 :
2923 0 : pp.set_output_stream (file);
2924 0 : pp_printf (&pp, "digraph SchedDG {\n");
2925 :
2926 0 : for (bb = 0; bb < current_nr_blocks; ++bb)
2927 : {
2928 : /* Begin subgraph (basic block). */
2929 0 : pp_printf (&pp, "subgraph cluster_block_%d {\n", bb);
2930 0 : pp_printf (&pp, "\t" "color=blue;" "\n");
2931 0 : pp_printf (&pp, "\t" "style=bold;" "\n");
2932 0 : pp_printf (&pp, "\t" "label=\"BB #%d\";\n", BB_TO_BLOCK (bb));
2933 :
2934 : /* Setup head and tail (no support for EBBs). */
2935 0 : gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
2936 0 : get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
2937 0 : tail = NEXT_INSN (tail);
2938 :
2939 : /* Dump all insns. */
2940 0 : for (con = head; con != tail; con = NEXT_INSN (con))
2941 : {
2942 0 : if (!INSN_P (con))
2943 0 : continue;
2944 :
2945 : /* Pretty print the insn. */
2946 0 : pp_printf (&pp, "\t%d [label=\"{", INSN_UID (con));
2947 0 : pp_write_text_to_stream (&pp);
2948 0 : print_insn (&pp, con, /*verbose=*/false);
2949 0 : pp_write_text_as_dot_label_to_stream (&pp, /*for_record=*/true);
2950 0 : pp_write_text_to_stream (&pp);
2951 :
2952 : /* Dump instruction attributes. */
2953 0 : pp_printf (&pp, "|{ uid:%d | luid:%d | prio:%d }}\",shape=record]\n",
2954 0 : INSN_UID (con), INSN_LUID (con), INSN_PRIORITY (con));
2955 :
2956 : /* Dump all deps. */
2957 0 : FOR_EACH_DEP (con, SD_LIST_BACK, sd_it, dep)
2958 : {
2959 0 : int weight = 0;
2960 0 : const char *color;
2961 0 : pro = DEP_PRO (dep);
2962 :
2963 0 : switch (DEP_TYPE (dep))
2964 : {
2965 : case REG_DEP_TRUE:
2966 : color = "black";
2967 : weight = 1;
2968 : break;
2969 0 : case REG_DEP_OUTPUT:
2970 0 : case REG_DEP_ANTI:
2971 0 : color = "orange";
2972 0 : break;
2973 0 : case REG_DEP_CONTROL:
2974 0 : color = "blue";
2975 0 : break;
2976 0 : default:
2977 0 : gcc_unreachable ();
2978 : }
2979 :
2980 0 : pp_printf (&pp, "\t%d -> %d [color=%s",
2981 0 : INSN_UID (pro), INSN_UID (con), color);
2982 0 : if (int cost = dep_cost (dep))
2983 0 : pp_printf (&pp, ",label=%d", cost);
2984 0 : pp_printf (&pp, ",weight=%d", weight);
2985 0 : pp_printf (&pp, "];\n");
2986 : }
2987 : }
2988 0 : pp_printf (&pp, "}\n");
2989 : }
2990 :
2991 0 : pp_printf (&pp, "}\n");
2992 0 : pp_flush (&pp);
2993 0 : }
2994 :
2995 : /* Dump dependency graph for the current region to a file using dot syntax. */
2996 :
2997 : DEBUG_FUNCTION void
2998 0 : dump_rgn_dependencies_dot (const char *fname)
2999 : {
3000 0 : FILE *fp;
3001 :
3002 0 : fp = fopen (fname, "w");
3003 0 : if (!fp)
3004 : {
3005 0 : perror ("fopen");
3006 0 : return;
3007 : }
3008 :
3009 0 : dump_rgn_dependencies_dot (fp);
3010 0 : fclose (fp);
3011 : }
3012 :
3013 :
3014 : /* Returns true if all the basic blocks of the current region have
3015 : NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
3016 : bool
3017 10517518 : sched_is_disabled_for_current_region_p (void)
3018 : {
3019 10517518 : int bb;
3020 :
3021 10517518 : for (bb = 0; bb < current_nr_blocks; bb++)
3022 10517518 : if (!(BASIC_BLOCK_FOR_FN (cfun,
3023 10517518 : BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE))
3024 : return false;
3025 :
3026 : return true;
3027 : }
3028 :
3029 : /* Free all region dependencies saved in INSN_BACK_DEPS and
3030 : INSN_RESOLVED_BACK_DEPS. The Haifa scheduler does this on the fly
3031 : when scheduling, so this function is supposed to be called from
3032 : the selective scheduling only. */
3033 : void
3034 715 : free_rgn_deps (void)
3035 : {
3036 715 : int bb;
3037 :
3038 1720 : for (bb = 0; bb < current_nr_blocks; bb++)
3039 : {
3040 1005 : rtx_insn *head, *tail;
3041 :
3042 1005 : gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
3043 1005 : get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
3044 :
3045 1005 : sched_free_deps (head, tail, false);
3046 : }
3047 715 : }
3048 :
3049 : static int rgn_n_insns;
3050 :
3051 : /* Compute insn priority for a current region. */
3052 : void
3053 10517518 : compute_priorities (void)
3054 : {
3055 10517518 : int bb;
3056 :
3057 10517518 : current_sched_info->sched_max_insns_priority = 0;
3058 21035372 : for (bb = 0; bb < current_nr_blocks; bb++)
3059 : {
3060 10517854 : rtx_insn *head, *tail;
3061 :
3062 10517854 : gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
3063 10517854 : get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
3064 :
3065 10517854 : if (no_real_insns_p (head, tail))
3066 18953 : continue;
3067 :
3068 10498901 : rgn_n_insns += set_priorities (head, tail);
3069 : }
3070 10517518 : current_sched_info->sched_max_insns_priority++;
3071 10517518 : }
3072 :
3073 : /* (Re-)initialize the arrays of DFA states at the end of each basic block.
3074 :
3075 : SAVED_LAST_BASIC_BLOCK is the previous length of the arrays. It must be
3076 : zero for the first call to this function, to allocate the arrays for the
3077 : first time.
3078 :
3079 : This function is called once during initialization of the scheduler, and
3080 : called again to resize the arrays if new basic blocks have been created,
3081 : for example for speculation recovery code. */
3082 :
3083 : static void
3084 11480836 : realloc_bb_state_array (int saved_last_basic_block)
3085 : {
3086 11480836 : char *old_bb_state_array = bb_state_array;
3087 11480836 : size_t lbb = (size_t) last_basic_block_for_fn (cfun);
3088 11480836 : size_t slbb = (size_t) saved_last_basic_block;
3089 :
3090 : /* Nothing to do if nothing changed since the last time this was called. */
3091 11480836 : if (saved_last_basic_block == last_basic_block_for_fn (cfun))
3092 : return;
3093 :
3094 : /* The selective scheduler doesn't use the state arrays. */
3095 982908 : if (sel_sched_p ())
3096 : {
3097 134 : gcc_assert (bb_state_array == NULL && bb_state == NULL);
3098 : return;
3099 : }
3100 :
3101 982774 : gcc_checking_assert (saved_last_basic_block == 0
3102 : || (bb_state_array != NULL && bb_state != NULL));
3103 :
3104 982774 : bb_state_array = XRESIZEVEC (char, bb_state_array, lbb * dfa_state_size);
3105 982774 : bb_state = XRESIZEVEC (state_t, bb_state, lbb);
3106 :
3107 : /* If BB_STATE_ARRAY has moved, fixup all the state pointers array.
3108 : Otherwise only fixup the newly allocated ones. For the state
3109 : array itself, only initialize the new entries. */
3110 982774 : bool bb_state_array_moved = (bb_state_array != old_bb_state_array);
3111 13465214 : for (size_t i = bb_state_array_moved ? 0 : slbb; i < lbb; i++)
3112 12482440 : bb_state[i] = (state_t) (bb_state_array + i * dfa_state_size);
3113 13465214 : for (size_t i = slbb; i < lbb; i++)
3114 12482440 : state_reset (bb_state[i]);
3115 : }
3116 :
3117 : /* Free the arrays of DFA states at the end of each basic block. */
3118 :
3119 : static void
3120 982908 : free_bb_state_array (void)
3121 : {
3122 982908 : free (bb_state_array);
3123 982908 : free (bb_state);
3124 982908 : bb_state_array = NULL;
3125 982908 : bb_state = NULL;
3126 982908 : }
3127 :
3128 : /* If LAST_BB falls through to another block B, record that B should
3129 : start with DFA start STATE. */
3130 :
3131 : static void
3132 10516849 : save_state_for_fallthru_edge (basic_block last_bb, state_t state)
3133 : {
3134 10516849 : edge f = find_fallthru_edge (last_bb->succs);
3135 10516849 : if (f
3136 10516849 : && (!f->probability.initialized_p ()
3137 6976612 : || (f->probability.to_reg_br_prob_base () * 100
3138 : / REG_BR_PROB_BASE
3139 6976612 : >= param_sched_state_edge_prob_cutoff)))
3140 : {
3141 6590556 : memcpy (bb_state[f->dest->index], state,
3142 : dfa_state_size);
3143 6590556 : if (sched_verbose >= 5)
3144 0 : fprintf (sched_dump, "saving state for edge %d->%d\n",
3145 0 : f->src->index, f->dest->index);
3146 : }
3147 10516849 : }
3148 :
3149 : /* Schedule a region. A region is either an inner loop, a loop-free
3150 : subroutine, or a single basic block. Each bb in the region is
3151 : scheduled after its flow predecessors. */
3152 :
3153 : static void
3154 10516803 : schedule_region (int rgn)
3155 : {
3156 10516803 : int bb;
3157 10516803 : int sched_rgn_n_insns = 0;
3158 :
3159 10516803 : rgn_n_insns = 0;
3160 :
3161 : /* Do not support register pressure sensitive scheduling for the new regions
3162 : as we don't update the liveness info for them. */
3163 10516803 : if (sched_pressure != SCHED_PRESSURE_NONE
3164 679 : && rgn >= nr_regions_initial)
3165 : {
3166 0 : free_global_sched_pressure_data ();
3167 0 : sched_pressure = SCHED_PRESSURE_NONE;
3168 : }
3169 :
3170 10516803 : rgn_setup_region (rgn);
3171 :
3172 : /* Don't schedule region that is marked by
3173 : NOTE_DISABLE_SCHED_OF_BLOCK. */
3174 10516803 : if (sched_is_disabled_for_current_region_p ())
3175 : return;
3176 :
3177 10516803 : sched_rgn_compute_dependencies (rgn);
3178 :
3179 10516803 : sched_rgn_local_init (rgn);
3180 :
3181 : /* Set priorities. */
3182 10516803 : compute_priorities ();
3183 :
3184 10516803 : sched_extend_ready_list (rgn_n_insns);
3185 :
3186 10516803 : if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
3187 : {
3188 679 : sched_init_region_reg_pressure_info ();
3189 2073 : for (bb = 0; bb < current_nr_blocks; bb++)
3190 : {
3191 715 : basic_block first_bb, last_bb;
3192 715 : rtx_insn *head, *tail;
3193 :
3194 715 : first_bb = EBB_FIRST_BB (bb);
3195 715 : last_bb = EBB_LAST_BB (bb);
3196 :
3197 715 : get_ebb_head_tail (first_bb, last_bb, &head, &tail);
3198 :
3199 715 : if (no_real_insns_p (head, tail))
3200 : {
3201 9 : gcc_assert (first_bb == last_bb);
3202 9 : continue;
3203 : }
3204 706 : sched_setup_bb_reg_pressure_info (first_bb, PREV_INSN (head));
3205 : }
3206 : }
3207 :
3208 : /* Now we can schedule all blocks. */
3209 21033652 : for (bb = 0; bb < current_nr_blocks; bb++)
3210 : {
3211 10516849 : basic_block first_bb, last_bb, curr_bb;
3212 10516849 : rtx_insn *head, *tail;
3213 :
3214 10516849 : first_bb = EBB_FIRST_BB (bb);
3215 10516849 : last_bb = EBB_LAST_BB (bb);
3216 :
3217 10516849 : get_ebb_head_tail (first_bb, last_bb, &head, &tail);
3218 :
3219 10516849 : if (no_real_insns_p (head, tail))
3220 : {
3221 18921 : gcc_assert (first_bb == last_bb);
3222 18921 : save_state_for_fallthru_edge (last_bb, bb_state[first_bb->index]);
3223 18921 : continue;
3224 : }
3225 :
3226 10497928 : current_sched_info->prev_head = PREV_INSN (head);
3227 10497928 : current_sched_info->next_tail = NEXT_INSN (tail);
3228 :
3229 10497928 : remove_notes (head, tail);
3230 :
3231 10497928 : unlink_bb_notes (first_bb, last_bb);
3232 :
3233 10497928 : target_bb = bb;
3234 :
3235 10497928 : gcc_assert (flag_schedule_interblock || current_nr_blocks == 1);
3236 10497928 : current_sched_info->queue_must_finish_empty = current_nr_blocks == 1;
3237 :
3238 10497928 : curr_bb = first_bb;
3239 10497928 : int saved_last_basic_block = last_basic_block_for_fn (cfun);
3240 :
3241 10497928 : schedule_block (&curr_bb, bb_state[first_bb->index]);
3242 10497928 : gcc_assert (EBB_FIRST_BB (bb) == first_bb);
3243 10497928 : sched_rgn_n_insns += sched_n_insns;
3244 10497928 : realloc_bb_state_array (saved_last_basic_block);
3245 10497928 : save_state_for_fallthru_edge (last_bb, curr_state);
3246 :
3247 : /* Clean up. */
3248 10497928 : if (current_nr_blocks > 1)
3249 72 : free_trg_info ();
3250 : }
3251 :
3252 : /* Sanity check: verify that all region insns were scheduled. */
3253 10516803 : gcc_assert (sched_rgn_n_insns == rgn_n_insns);
3254 :
3255 10516803 : sched_finish_ready_list ();
3256 :
3257 : /* Done with this region. */
3258 10516803 : sched_rgn_local_finish ();
3259 :
3260 : /* Free dependencies. */
3261 31550455 : for (bb = 0; bb < current_nr_blocks; ++bb)
3262 10516849 : free_block_dependencies (bb);
3263 :
3264 10516803 : gcc_assert (haifa_recovery_bb_ever_added_p
3265 : || deps_pools_are_empty_p ());
3266 : }
3267 :
3268 : /* Initialize data structures for region scheduling. */
3269 :
3270 : void
3271 982908 : sched_rgn_init (bool single_blocks_p)
3272 : {
3273 982908 : min_spec_prob = ((param_min_spec_prob * REG_BR_PROB_BASE)
3274 : / 100);
3275 :
3276 982908 : nr_inter = 0;
3277 982908 : nr_spec = 0;
3278 :
3279 982908 : extend_regions ();
3280 :
3281 982908 : CONTAINING_RGN (ENTRY_BLOCK) = -1;
3282 982908 : CONTAINING_RGN (EXIT_BLOCK) = -1;
3283 :
3284 982908 : realloc_bb_state_array (0);
3285 :
3286 : /* Compute regions for scheduling. */
3287 982908 : if (single_blocks_p
3288 321 : || n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS + 1
3289 199 : || !flag_schedule_interblock
3290 983094 : || is_cfg_nonregular ())
3291 : {
3292 982738 : find_single_block_region (sel_sched_p ());
3293 : }
3294 : else
3295 : {
3296 : /* Compute the dominators and post dominators. */
3297 170 : if (!sel_sched_p ())
3298 88 : calculate_dominance_info (CDI_DOMINATORS);
3299 :
3300 : /* Find regions. */
3301 170 : find_rgns ();
3302 :
3303 170 : if (sched_verbose >= 3)
3304 0 : debug_regions ();
3305 :
3306 : /* For now. This will move as more and more of haifa is converted
3307 : to using the cfg code. */
3308 170 : if (!sel_sched_p ())
3309 88 : free_dominance_info (CDI_DOMINATORS);
3310 : }
3311 :
3312 982908 : gcc_assert (nr_regions > 0 && nr_regions <= n_basic_blocks_for_fn (cfun));
3313 :
3314 982908 : RGN_BLOCKS (nr_regions) = (RGN_BLOCKS (nr_regions - 1)
3315 982908 : + RGN_NR_BLOCKS (nr_regions - 1));
3316 982908 : nr_regions_initial = nr_regions;
3317 982908 : }
3318 :
3319 : /* Free data structures for region scheduling. */
3320 : void
3321 982908 : sched_rgn_finish (void)
3322 : {
3323 982908 : free_bb_state_array ();
3324 :
3325 : /* Reposition the prologue and epilogue notes in case we moved the
3326 : prologue/epilogue insns. */
3327 982908 : if (reload_completed)
3328 982674 : reposition_prologue_and_epilogue_notes ();
3329 :
3330 982908 : if (sched_verbose)
3331 : {
3332 24 : if (reload_completed == 0
3333 0 : && flag_schedule_interblock)
3334 : {
3335 0 : fprintf (sched_dump,
3336 : "\n;; Procedure interblock/speculative motions == %d/%d \n",
3337 : nr_inter, nr_spec);
3338 : }
3339 : else
3340 24 : gcc_assert (nr_inter <= 0);
3341 24 : fprintf (sched_dump, "\n\n");
3342 : }
3343 :
3344 982908 : nr_regions = 0;
3345 :
3346 982908 : free (rgn_table);
3347 982908 : rgn_table = NULL;
3348 :
3349 982908 : free (rgn_bb_table);
3350 982908 : rgn_bb_table = NULL;
3351 :
3352 982908 : free (block_to_bb);
3353 982908 : block_to_bb = NULL;
3354 :
3355 982908 : free (containing_rgn);
3356 982908 : containing_rgn = NULL;
3357 :
3358 982908 : free (ebb_head);
3359 982908 : ebb_head = NULL;
3360 982908 : }
3361 :
3362 : /* Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
3363 : point to the region RGN. */
3364 : void
3365 10517723 : rgn_setup_region (int rgn)
3366 : {
3367 10517723 : int bb;
3368 :
3369 : /* Set variables for the current region. */
3370 10517723 : current_nr_blocks = RGN_NR_BLOCKS (rgn);
3371 10517723 : current_blocks = RGN_BLOCKS (rgn);
3372 :
3373 : /* EBB_HEAD is a region-scope structure. But we realloc it for
3374 : each region to save time/memory/something else.
3375 : See comments in add_block1, for what reasons we allocate +1 element. */
3376 10517723 : ebb_head = XRESIZEVEC (int, ebb_head, current_nr_blocks + 1);
3377 31555327 : for (bb = 0; bb <= current_nr_blocks; bb++)
3378 21037604 : ebb_head[bb] = current_blocks + bb;
3379 10517723 : }
3380 :
3381 : /* Compute instruction dependencies in region RGN. */
3382 : void
3383 10517518 : sched_rgn_compute_dependencies (int rgn)
3384 : {
3385 10517518 : if (!RGN_DONT_CALC_DEPS (rgn))
3386 : {
3387 10517518 : int bb;
3388 :
3389 10517518 : if (sel_sched_p ())
3390 715 : sched_emulate_haifa_p = 1;
3391 :
3392 10517518 : init_deps_global ();
3393 :
3394 : /* Initializations for region data dependence analysis. */
3395 10517518 : bb_deps = XNEWVEC (class deps_desc, current_nr_blocks);
3396 21035372 : for (bb = 0; bb < current_nr_blocks; bb++)
3397 10517854 : init_deps (bb_deps + bb, false);
3398 :
3399 : /* Initialize bitmap used in add_branch_dependences. */
3400 10517518 : insn_referenced = sbitmap_alloc (sched_max_luid);
3401 10517518 : bitmap_clear (insn_referenced);
3402 :
3403 : /* Compute backward dependencies. */
3404 31552890 : for (bb = 0; bb < current_nr_blocks; bb++)
3405 10517854 : compute_block_dependences (bb);
3406 :
3407 10517518 : sbitmap_free (insn_referenced);
3408 10517518 : free_pending_lists ();
3409 10517518 : finish_deps_global ();
3410 10517518 : free (bb_deps);
3411 :
3412 : /* We don't want to recalculate this twice. */
3413 10517518 : RGN_DONT_CALC_DEPS (rgn) = 1;
3414 :
3415 10517518 : if (sel_sched_p ())
3416 715 : sched_emulate_haifa_p = 0;
3417 : }
3418 : else
3419 : /* (This is a recovery block. It is always a single block region.)
3420 : OR (We use selective scheduling.) */
3421 0 : gcc_assert (current_nr_blocks == 1 || sel_sched_p ());
3422 10517518 : }
3423 :
3424 : /* Init region data structures. Returns true if this region should
3425 : not be scheduled. */
3426 : void
3427 10516803 : sched_rgn_local_init (int rgn)
3428 : {
3429 10516803 : int bb;
3430 :
3431 : /* Compute interblock info: probabilities, split-edges, dominators, etc. */
3432 10516803 : if (current_nr_blocks > 1)
3433 : {
3434 26 : basic_block block;
3435 26 : edge e;
3436 26 : edge_iterator ei;
3437 :
3438 26 : prob = XNEWVEC (int, current_nr_blocks);
3439 :
3440 26 : dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
3441 26 : bitmap_vector_clear (dom, current_nr_blocks);
3442 :
3443 : /* Use ->aux to implement EDGE_TO_BIT mapping. */
3444 26 : rgn_nr_edges = 0;
3445 1029 : FOR_EACH_BB_FN (block, cfun)
3446 : {
3447 1003 : if (CONTAINING_RGN (block->index) != rgn)
3448 931 : continue;
3449 213 : FOR_EACH_EDGE (e, ei, block->succs)
3450 141 : SET_EDGE_TO_BIT (e, rgn_nr_edges++);
3451 : }
3452 :
3453 26 : rgn_edges = XNEWVEC (edge, rgn_nr_edges);
3454 26 : rgn_nr_edges = 0;
3455 1029 : FOR_EACH_BB_FN (block, cfun)
3456 : {
3457 1003 : if (CONTAINING_RGN (block->index) != rgn)
3458 931 : continue;
3459 213 : FOR_EACH_EDGE (e, ei, block->succs)
3460 141 : rgn_edges[rgn_nr_edges++] = e;
3461 : }
3462 :
3463 : /* Split edges. */
3464 26 : pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
3465 26 : bitmap_vector_clear (pot_split, current_nr_blocks);
3466 26 : ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
3467 26 : bitmap_vector_clear (ancestor_edges, current_nr_blocks);
3468 :
3469 : /* Compute probabilities, dominators, split_edges. */
3470 124 : for (bb = 0; bb < current_nr_blocks; bb++)
3471 72 : compute_dom_prob_ps (bb);
3472 :
3473 : /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
3474 : /* We don't need them anymore. But we want to avoid duplication of
3475 : aux fields in the newly created edges. */
3476 1029 : FOR_EACH_BB_FN (block, cfun)
3477 : {
3478 1003 : if (CONTAINING_RGN (block->index) != rgn)
3479 931 : continue;
3480 213 : FOR_EACH_EDGE (e, ei, block->succs)
3481 141 : e->aux = NULL;
3482 : }
3483 : }
3484 10516803 : }
3485 :
3486 : /* Free data computed for the finished region. */
3487 : void
3488 26 : sched_rgn_local_free (void)
3489 : {
3490 26 : free (prob);
3491 26 : sbitmap_vector_free (dom);
3492 26 : sbitmap_vector_free (pot_split);
3493 26 : sbitmap_vector_free (ancestor_edges);
3494 26 : free (rgn_edges);
3495 26 : }
3496 :
3497 : /* Free data computed for the finished region. */
3498 : void
3499 10516803 : sched_rgn_local_finish (void)
3500 : {
3501 10516803 : if (current_nr_blocks > 1 && !sel_sched_p ())
3502 : {
3503 26 : sched_rgn_local_free ();
3504 : }
3505 10516803 : }
3506 :
3507 : /* Setup scheduler infos. */
3508 : void
3509 983623 : rgn_setup_common_sched_info (void)
3510 : {
3511 983623 : memcpy (&rgn_common_sched_info, &haifa_common_sched_info,
3512 : sizeof (rgn_common_sched_info));
3513 :
3514 983623 : rgn_common_sched_info.fix_recovery_cfg = rgn_fix_recovery_cfg;
3515 983623 : rgn_common_sched_info.add_block = rgn_add_block;
3516 983623 : rgn_common_sched_info.estimate_number_of_insns
3517 983623 : = rgn_estimate_number_of_insns;
3518 983623 : rgn_common_sched_info.sched_pass_id = SCHED_RGN_PASS;
3519 :
3520 983623 : common_sched_info = &rgn_common_sched_info;
3521 983623 : }
3522 :
3523 : /* Setup all *_sched_info structures (for the Haifa frontend
3524 : and for the dependence analysis) in the interblock scheduler. */
3525 : void
3526 983489 : rgn_setup_sched_infos (void)
3527 : {
3528 983489 : if (!sel_sched_p ())
3529 982774 : memcpy (&rgn_sched_deps_info, &rgn_const_sched_deps_info,
3530 : sizeof (rgn_sched_deps_info));
3531 : else
3532 715 : memcpy (&rgn_sched_deps_info, &rgn_const_sel_sched_deps_info,
3533 : sizeof (rgn_sched_deps_info));
3534 :
3535 983489 : sched_deps_info = &rgn_sched_deps_info;
3536 :
3537 983489 : memcpy (&rgn_sched_info, &rgn_const_sched_info, sizeof (rgn_sched_info));
3538 983489 : current_sched_info = &rgn_sched_info;
3539 983489 : }
3540 :
3541 : /* The one entry point in this file. */
3542 : void
3543 982774 : schedule_insns (void)
3544 : {
3545 982774 : int rgn;
3546 :
3547 : /* Taking care of this degenerate case makes the rest of
3548 : this code simpler. */
3549 982774 : if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
3550 : return;
3551 :
3552 982774 : rgn_setup_common_sched_info ();
3553 982774 : rgn_setup_sched_infos ();
3554 :
3555 982774 : haifa_sched_init ();
3556 982774 : sched_rgn_init (reload_completed);
3557 :
3558 982774 : bitmap_initialize (¬_in_df, &bitmap_default_obstack);
3559 :
3560 : /* Schedule every region in the subroutine. */
3561 11499577 : for (rgn = 0; rgn < nr_regions; rgn++)
3562 10516803 : if (dbg_cnt (sched_region))
3563 10516803 : schedule_region (rgn);
3564 :
3565 : /* Clean up. */
3566 982774 : sched_rgn_finish ();
3567 982774 : bitmap_release (¬_in_df);
3568 :
3569 982774 : haifa_sched_finish ();
3570 : }
3571 :
3572 : /* INSN has been added to/removed from current region. */
3573 : static void
3574 0 : rgn_add_remove_insn (rtx_insn *insn, int remove_p)
3575 : {
3576 0 : if (!remove_p)
3577 0 : rgn_n_insns++;
3578 : else
3579 0 : rgn_n_insns--;
3580 :
3581 0 : if (INSN_BB (insn) == target_bb)
3582 : {
3583 0 : if (!remove_p)
3584 0 : target_n_insns++;
3585 : else
3586 0 : target_n_insns--;
3587 : }
3588 0 : }
3589 :
3590 : /* Extend internal data structures. */
3591 : void
3592 983026 : extend_regions (void)
3593 : {
3594 983026 : rgn_table = XRESIZEVEC (region, rgn_table, n_basic_blocks_for_fn (cfun));
3595 983026 : rgn_bb_table = XRESIZEVEC (int, rgn_bb_table,
3596 : n_basic_blocks_for_fn (cfun));
3597 983026 : block_to_bb = XRESIZEVEC (int, block_to_bb,
3598 : last_basic_block_for_fn (cfun));
3599 983026 : containing_rgn = XRESIZEVEC (int, containing_rgn,
3600 : last_basic_block_for_fn (cfun));
3601 983026 : }
3602 :
3603 : void
3604 0 : rgn_make_new_region_out_of_new_block (basic_block bb)
3605 : {
3606 0 : int i;
3607 :
3608 0 : i = RGN_BLOCKS (nr_regions);
3609 : /* I - first free position in rgn_bb_table. */
3610 :
3611 0 : rgn_bb_table[i] = bb->index;
3612 0 : RGN_NR_BLOCKS (nr_regions) = 1;
3613 0 : RGN_HAS_REAL_EBB (nr_regions) = 0;
3614 0 : RGN_DONT_CALC_DEPS (nr_regions) = 0;
3615 0 : CONTAINING_RGN (bb->index) = nr_regions;
3616 0 : BLOCK_TO_BB (bb->index) = 0;
3617 :
3618 0 : nr_regions++;
3619 :
3620 0 : RGN_BLOCKS (nr_regions) = i + 1;
3621 0 : }
3622 :
3623 : /* BB was added to ebb after AFTER. */
3624 : static void
3625 0 : rgn_add_block (basic_block bb, basic_block after)
3626 : {
3627 0 : extend_regions ();
3628 0 : bitmap_set_bit (¬_in_df, bb->index);
3629 :
3630 0 : if (after == 0 || after == EXIT_BLOCK_PTR_FOR_FN (cfun))
3631 : {
3632 0 : rgn_make_new_region_out_of_new_block (bb);
3633 0 : RGN_DONT_CALC_DEPS (nr_regions - 1) = (after
3634 0 : == EXIT_BLOCK_PTR_FOR_FN (cfun));
3635 : }
3636 : else
3637 : {
3638 0 : int i, pos;
3639 :
3640 : /* We need to fix rgn_table, block_to_bb, containing_rgn
3641 : and ebb_head. */
3642 :
3643 0 : BLOCK_TO_BB (bb->index) = BLOCK_TO_BB (after->index);
3644 :
3645 : /* We extend ebb_head to one more position to
3646 : easily find the last position of the last ebb in
3647 : the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
3648 : is _always_ valid for access. */
3649 :
3650 0 : i = BLOCK_TO_BB (after->index) + 1;
3651 0 : pos = ebb_head[i] - 1;
3652 : /* Now POS is the index of the last block in the region. */
3653 :
3654 : /* Find index of basic block AFTER. */
3655 0 : for (; rgn_bb_table[pos] != after->index; pos--)
3656 : ;
3657 :
3658 0 : pos++;
3659 0 : gcc_assert (pos > ebb_head[i - 1]);
3660 :
3661 : /* i - ebb right after "AFTER". */
3662 : /* ebb_head[i] - VALID. */
3663 :
3664 : /* Source position: ebb_head[i]
3665 : Destination position: ebb_head[i] + 1
3666 : Last position:
3667 : RGN_BLOCKS (nr_regions) - 1
3668 : Number of elements to copy: (last_position) - (source_position) + 1
3669 : */
3670 :
3671 0 : memmove (rgn_bb_table + pos + 1,
3672 0 : rgn_bb_table + pos,
3673 0 : ((RGN_BLOCKS (nr_regions) - 1) - (pos) + 1)
3674 : * sizeof (*rgn_bb_table));
3675 :
3676 0 : rgn_bb_table[pos] = bb->index;
3677 :
3678 0 : for (; i <= current_nr_blocks; i++)
3679 0 : ebb_head [i]++;
3680 :
3681 0 : i = CONTAINING_RGN (after->index);
3682 0 : CONTAINING_RGN (bb->index) = i;
3683 :
3684 0 : RGN_HAS_REAL_EBB (i) = 1;
3685 :
3686 0 : for (++i; i <= nr_regions; i++)
3687 0 : RGN_BLOCKS (i)++;
3688 : }
3689 0 : }
3690 :
3691 : /* Fix internal data after interblock movement of jump instruction.
3692 : For parameter meaning please refer to
3693 : sched-int.h: struct sched_info: fix_recovery_cfg. */
3694 : static void
3695 0 : rgn_fix_recovery_cfg (int bbi, int check_bbi, int check_bb_nexti)
3696 : {
3697 0 : int old_pos, new_pos, i;
3698 :
3699 0 : BLOCK_TO_BB (check_bb_nexti) = BLOCK_TO_BB (bbi);
3700 :
3701 0 : for (old_pos = ebb_head[BLOCK_TO_BB (check_bbi) + 1] - 1;
3702 0 : rgn_bb_table[old_pos] != check_bb_nexti;
3703 : old_pos--)
3704 : ;
3705 0 : gcc_assert (old_pos > ebb_head[BLOCK_TO_BB (check_bbi)]);
3706 :
3707 0 : for (new_pos = ebb_head[BLOCK_TO_BB (bbi) + 1] - 1;
3708 0 : rgn_bb_table[new_pos] != bbi;
3709 : new_pos--)
3710 : ;
3711 0 : new_pos++;
3712 0 : gcc_assert (new_pos > ebb_head[BLOCK_TO_BB (bbi)]);
3713 :
3714 0 : gcc_assert (new_pos < old_pos);
3715 :
3716 0 : memmove (rgn_bb_table + new_pos + 1,
3717 0 : rgn_bb_table + new_pos,
3718 0 : (old_pos - new_pos) * sizeof (*rgn_bb_table));
3719 :
3720 0 : rgn_bb_table[new_pos] = check_bb_nexti;
3721 :
3722 0 : for (i = BLOCK_TO_BB (bbi) + 1; i <= BLOCK_TO_BB (check_bbi); i++)
3723 0 : ebb_head[i]++;
3724 0 : }
3725 :
3726 : /* Return next block in ebb chain. For parameter meaning please refer to
3727 : sched-int.h: struct sched_info: advance_target_bb. */
3728 : static basic_block
3729 113624729 : advance_target_bb (basic_block bb, rtx_insn *insn)
3730 : {
3731 113624729 : if (insn)
3732 : return 0;
3733 :
3734 0 : gcc_assert (BLOCK_TO_BB (bb->index) == target_bb
3735 : && BLOCK_TO_BB (bb->next_bb->index) == target_bb);
3736 : return bb->next_bb;
3737 : }
3738 :
3739 : #endif
3740 :
3741 : /* Run instruction scheduler. */
3742 : static unsigned int
3743 35 : rest_of_handle_live_range_shrinkage (void)
3744 : {
3745 : #ifdef INSN_SCHEDULING
3746 35 : int saved;
3747 :
3748 35 : initialize_live_range_shrinkage ();
3749 35 : saved = flag_schedule_interblock;
3750 35 : flag_schedule_interblock = false;
3751 35 : schedule_insns ();
3752 35 : flag_schedule_interblock = saved;
3753 35 : finish_live_range_shrinkage ();
3754 : #endif
3755 35 : return 0;
3756 : }
3757 :
3758 : /* Run instruction scheduler. */
3759 : static unsigned int
3760 199 : rest_of_handle_sched (void)
3761 : {
3762 : #ifdef INSN_SCHEDULING
3763 199 : if (flag_selective_scheduling
3764 199 : && ! maybe_skip_selective_scheduling ())
3765 47 : run_selective_scheduling ();
3766 : else
3767 152 : schedule_insns ();
3768 : #endif
3769 199 : return 0;
3770 : }
3771 :
3772 : /* Run second scheduling pass after reload. */
3773 : static unsigned int
3774 982732 : rest_of_handle_sched2 (void)
3775 : {
3776 : #ifdef INSN_SCHEDULING
3777 982732 : if (flag_selective_scheduling2
3778 982732 : && ! maybe_skip_selective_scheduling ())
3779 87 : run_selective_scheduling ();
3780 : else
3781 : {
3782 : /* Do control and data sched analysis again,
3783 : and write some more of the results to dump file. */
3784 982645 : if (flag_sched2_use_superblocks)
3785 58 : schedule_ebbs ();
3786 : else
3787 982587 : schedule_insns ();
3788 : }
3789 : #endif
3790 982732 : return 0;
3791 : }
3792 :
3793 : static unsigned int
3794 0 : rest_of_handle_sched_fusion (void)
3795 : {
3796 : #ifdef INSN_SCHEDULING
3797 0 : sched_fusion = true;
3798 0 : schedule_insns ();
3799 0 : sched_fusion = false;
3800 : #endif
3801 0 : return 0;
3802 : }
3803 :
3804 : namespace {
3805 :
3806 : const pass_data pass_data_live_range_shrinkage =
3807 : {
3808 : RTL_PASS, /* type */
3809 : "lr_shrinkage", /* name */
3810 : OPTGROUP_NONE, /* optinfo_flags */
3811 : TV_LIVE_RANGE_SHRINKAGE, /* tv_id */
3812 : 0, /* properties_required */
3813 : 0, /* properties_provided */
3814 : 0, /* properties_destroyed */
3815 : 0, /* todo_flags_start */
3816 : TODO_df_finish, /* todo_flags_finish */
3817 : };
3818 :
3819 : class pass_live_range_shrinkage : public rtl_opt_pass
3820 : {
3821 : public:
3822 297180 : pass_live_range_shrinkage(gcc::context *ctxt)
3823 594360 : : rtl_opt_pass(pass_data_live_range_shrinkage, ctxt)
3824 : {}
3825 :
3826 : /* opt_pass methods: */
3827 1517135 : bool gate (function *) final override
3828 : {
3829 : #ifdef INSN_SCHEDULING
3830 1517135 : return flag_live_range_shrinkage;
3831 : #else
3832 : return 0;
3833 : #endif
3834 : }
3835 :
3836 35 : unsigned int execute (function *) final override
3837 : {
3838 35 : return rest_of_handle_live_range_shrinkage ();
3839 : }
3840 :
3841 : }; // class pass_live_range_shrinkage
3842 :
3843 : } // anon namespace
3844 :
3845 : rtl_opt_pass *
3846 297180 : make_pass_live_range_shrinkage (gcc::context *ctxt)
3847 : {
3848 297180 : return new pass_live_range_shrinkage (ctxt);
3849 : }
3850 :
3851 : namespace {
3852 :
3853 : const pass_data pass_data_sched =
3854 : {
3855 : RTL_PASS, /* type */
3856 : "sched1", /* name */
3857 : OPTGROUP_NONE, /* optinfo_flags */
3858 : TV_SCHED, /* tv_id */
3859 : 0, /* properties_required */
3860 : 0, /* properties_provided */
3861 : 0, /* properties_destroyed */
3862 : 0, /* todo_flags_start */
3863 : TODO_df_finish, /* todo_flags_finish */
3864 : };
3865 :
3866 : class pass_sched : public rtl_opt_pass
3867 : {
3868 : public:
3869 297180 : pass_sched (gcc::context *ctxt)
3870 594360 : : rtl_opt_pass (pass_data_sched, ctxt)
3871 : {}
3872 :
3873 : /* opt_pass methods: */
3874 : bool gate (function *) final override;
3875 199 : unsigned int execute (function *) final override
3876 : {
3877 199 : return rest_of_handle_sched ();
3878 : }
3879 :
3880 : }; // class pass_sched
3881 :
3882 : bool
3883 1517135 : pass_sched::gate (function *)
3884 : {
3885 : #ifdef INSN_SCHEDULING
3886 1517135 : return optimize > 0 && flag_schedule_insns && dbg_cnt (sched_func);
3887 : #else
3888 : return 0;
3889 : #endif
3890 : }
3891 :
3892 : } // anon namespace
3893 :
3894 : rtl_opt_pass *
3895 297180 : make_pass_sched (gcc::context *ctxt)
3896 : {
3897 297180 : return new pass_sched (ctxt);
3898 : }
3899 :
3900 : namespace {
3901 :
3902 : const pass_data pass_data_sched2 =
3903 : {
3904 : RTL_PASS, /* type */
3905 : "sched2", /* name */
3906 : OPTGROUP_NONE, /* optinfo_flags */
3907 : TV_SCHED2, /* tv_id */
3908 : 0, /* properties_required */
3909 : 0, /* properties_provided */
3910 : 0, /* properties_destroyed */
3911 : 0, /* todo_flags_start */
3912 : TODO_df_finish, /* todo_flags_finish */
3913 : };
3914 :
3915 : class pass_sched2 : public rtl_opt_pass
3916 : {
3917 : public:
3918 297180 : pass_sched2 (gcc::context *ctxt)
3919 594360 : : rtl_opt_pass (pass_data_sched2, ctxt)
3920 : {}
3921 :
3922 : /* opt_pass methods: */
3923 : bool gate (function *) final override;
3924 982732 : unsigned int execute (function *) final override
3925 : {
3926 982732 : return rest_of_handle_sched2 ();
3927 : }
3928 :
3929 : }; // class pass_sched2
3930 :
3931 : bool
3932 1517135 : pass_sched2::gate (function *)
3933 : {
3934 : #ifdef INSN_SCHEDULING
3935 1064964 : return optimize > 0 && flag_schedule_insns_after_reload
3936 2499868 : && !targetm.delay_sched2 && dbg_cnt (sched2_func);
3937 : #else
3938 : return 0;
3939 : #endif
3940 : }
3941 :
3942 : } // anon namespace
3943 :
3944 : rtl_opt_pass *
3945 297180 : make_pass_sched2 (gcc::context *ctxt)
3946 : {
3947 297180 : return new pass_sched2 (ctxt);
3948 : }
3949 :
3950 : namespace {
3951 :
3952 : const pass_data pass_data_sched_fusion =
3953 : {
3954 : RTL_PASS, /* type */
3955 : "sched_fusion", /* name */
3956 : OPTGROUP_NONE, /* optinfo_flags */
3957 : TV_SCHED_FUSION, /* tv_id */
3958 : 0, /* properties_required */
3959 : 0, /* properties_provided */
3960 : 0, /* properties_destroyed */
3961 : 0, /* todo_flags_start */
3962 : TODO_df_finish, /* todo_flags_finish */
3963 : };
3964 :
3965 : class pass_sched_fusion : public rtl_opt_pass
3966 : {
3967 : public:
3968 297180 : pass_sched_fusion (gcc::context *ctxt)
3969 594360 : : rtl_opt_pass (pass_data_sched_fusion, ctxt)
3970 : {}
3971 :
3972 : /* opt_pass methods: */
3973 : bool gate (function *) final override;
3974 0 : unsigned int execute (function *) final override
3975 : {
3976 0 : return rest_of_handle_sched_fusion ();
3977 : }
3978 :
3979 : }; // class pass_sched2
3980 :
3981 : bool
3982 1517135 : pass_sched_fusion::gate (function *)
3983 : {
3984 : #ifdef INSN_SCHEDULING
3985 : /* Scheduling fusion relies on peephole2 to do real fusion work,
3986 : so only enable it if peephole2 is in effect. */
3987 1064964 : return (optimize > 0 && flag_peephole2
3988 2499875 : && flag_schedule_fusion && targetm.sched.fusion_priority != NULL);
3989 : #else
3990 : return 0;
3991 : #endif
3992 : }
3993 :
3994 : } // anon namespace
3995 :
3996 : rtl_opt_pass *
3997 297180 : make_pass_sched_fusion (gcc::context *ctxt)
3998 : {
3999 297180 : return new pass_sched_fusion (ctxt);
4000 : }
4001 :
4002 : #if __GNUC__ >= 10
4003 : # pragma GCC diagnostic pop
4004 : #endif
|