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