1 /* Instruction scheduling pass.
2 Copyright (C) 1992-2016 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
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
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This pass implements list scheduling within basic blocks. It is
23 run twice: (1) after flow analysis, but before register allocation,
24 and (2) after register allocation.
26 The first run performs interblock scheduling, moving insns between
27 different blocks in the same "region", and the second runs only
28 basic block scheduling.
30 Interblock motions performed are useful motions and speculative
31 motions, including speculative loads. Motions requiring code
32 duplication are not supported. The identification of motion type
33 and the check for validity of speculative motions requires
34 construction and analysis of the function's control flow graph.
36 The main entry point for this pass is schedule_insns(), called for
37 each function. The work of the scheduler is organized in three
38 levels: (1) function level: insns are subject to splitting,
39 control-flow-graph is constructed, regions are computed (after
40 reload, each region is of one block), (2) region level: control
41 flow graph attributes required for interblock scheduling are
42 computed (dominators, reachability, etc.), data dependences and
43 priorities are computed, and (3) block level: insns in the block
44 are actually scheduled. */
48 #include "coretypes.h"
54 #include "insn-config.h"
58 #include "insn-attr.h"
62 #include "sched-int.h"
63 #include "sel-sched.h"
64 #include "tree-pass.h"
66 #include "pretty-print.h"
67 #include "print-rtl.h"
69 #ifdef INSN_SCHEDULING
71 /* Some accessor macros for h_i_d members only used within this file. */
72 #define FED_BY_SPEC_LOAD(INSN) (HID (INSN)->fed_by_spec_load)
73 #define IS_LOAD_INSN(INSN) (HID (insn)->is_load_insn)
75 /* nr_inter/spec counts interblock/speculative motion for the function. */
76 static int nr_inter
, nr_spec
;
78 static int is_cfg_nonregular (void);
80 /* Number of regions in the procedure. */
83 /* Same as above before adding any new regions. */
84 static int nr_regions_initial
= 0;
86 /* Table of region descriptions. */
87 region
*rgn_table
= NULL
;
89 /* Array of lists of regions' blocks. */
90 int *rgn_bb_table
= NULL
;
92 /* Topological order of blocks in the region (if b2 is reachable from
93 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
94 always referred to by either block or b, while its topological
95 order name (in the region) is referred to by bb. */
96 int *block_to_bb
= NULL
;
98 /* The number of the region containing a block. */
99 int *containing_rgn
= NULL
;
101 /* ebb_head [i] - is index in rgn_bb_table of the head basic block of i'th ebb.
102 Currently we can get a ebb only through splitting of currently
103 scheduling block, therefore, we don't need ebb_head array for every region,
104 hence, its sufficient to hold it for current one only. */
105 int *ebb_head
= NULL
;
107 /* The minimum probability of reaching a source block so that it will be
108 considered for speculative scheduling. */
109 static int min_spec_prob
;
111 static void find_single_block_region (bool);
112 static void find_rgns (void);
113 static bool too_large (int, int *, int *);
115 /* Blocks of the current region being scheduled. */
116 int current_nr_blocks
;
119 /* A speculative motion requires checking live information on the path
120 from 'source' to 'target'. The split blocks are those to be checked.
121 After a speculative motion, live information should be modified in
124 Lists of split and update blocks for each candidate of the current
125 target are in array bblst_table. */
126 static basic_block
*bblst_table
;
127 static int bblst_size
, bblst_last
;
129 /* Arrays that hold the DFA state at the end of a basic block, to re-use
130 as the initial state at the start of successor blocks. The BB_STATE
131 array holds the actual DFA state, and BB_STATE_ARRAY[I] is a pointer
132 into BB_STATE for basic block I. FIXME: This should be a vec. */
133 static char *bb_state_array
= NULL
;
134 static state_t
*bb_state
= NULL
;
136 /* Target info declarations.
138 The block currently being scheduled is referred to as the "target" block,
139 while other blocks in the region from which insns can be moved to the
140 target are called "source" blocks. The candidate structure holds info
141 about such sources: are they valid? Speculative? Etc. */
144 basic_block
*first_member
;
157 static candidate
*candidate_table
;
158 #define IS_VALID(src) (candidate_table[src].is_valid)
159 #define IS_SPECULATIVE(src) (candidate_table[src].is_speculative)
160 #define IS_SPECULATIVE_INSN(INSN) \
161 (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
162 #define SRC_PROB(src) ( candidate_table[src].src_prob )
164 /* The bb being currently scheduled. */
174 static edge
*edgelst_table
;
175 static int edgelst_last
;
177 static void extract_edgelst (sbitmap
, edgelst
*);
179 /* Target info functions. */
180 static void split_edges (int, int, edgelst
*);
181 static void compute_trg_info (int);
182 void debug_candidate (int);
183 void debug_candidates (int);
185 /* Dominators array: dom[i] contains the sbitmap of dominators of
186 bb i in the region. */
189 /* bb 0 is the only region entry. */
190 #define IS_RGN_ENTRY(bb) (!bb)
192 /* Is bb_src dominated by bb_trg. */
193 #define IS_DOMINATED(bb_src, bb_trg) \
194 ( bitmap_bit_p (dom[bb_src], bb_trg) )
196 /* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
197 the probability of bb i relative to the region entry. */
200 /* Bit-set of edges, where bit i stands for edge i. */
201 typedef sbitmap edgeset
;
203 /* Number of edges in the region. */
204 static int rgn_nr_edges
;
206 /* Array of size rgn_nr_edges. */
207 static edge
*rgn_edges
;
209 /* Mapping from each edge in the graph to its number in the rgn. */
210 #define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
211 #define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
213 /* The split edges of a source bb is different for each target
214 bb. In order to compute this efficiently, the 'potential-split edges'
215 are computed for each bb prior to scheduling a region. This is actually
216 the split edges of each bb relative to the region entry.
218 pot_split[bb] is the set of potential split edges of bb. */
219 static edgeset
*pot_split
;
221 /* For every bb, a set of its ancestor edges. */
222 static edgeset
*ancestor_edges
;
224 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
226 /* Speculative scheduling functions. */
227 static int check_live_1 (int, rtx
);
228 static void update_live_1 (int, rtx
);
229 static int is_pfree (rtx
, int, int);
230 static int find_conditional_protection (rtx_insn
*, int);
231 static int is_conditionally_protected (rtx
, int, int);
232 static int is_prisky (rtx
, int, int);
233 static int is_exception_free (rtx_insn
*, int, int);
235 static bool sets_likely_spilled (rtx
);
236 static void sets_likely_spilled_1 (rtx
, const_rtx
, void *);
237 static void add_branch_dependences (rtx_insn
*, rtx_insn
*);
238 static void compute_block_dependences (int);
240 static void schedule_region (int);
241 static void concat_insn_mem_list (rtx_insn_list
*, rtx_expr_list
*,
242 rtx_insn_list
**, rtx_expr_list
**);
243 static void propagate_deps (int, struct deps_desc
*);
244 static void free_pending_lists (void);
246 /* Functions for construction of the control flow graph. */
248 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
250 We decide not to build the control flow graph if there is possibly more
251 than one entry to the function, if computed branches exist, if we
252 have nonlocal gotos, or if we have an unreachable loop. */
255 is_cfg_nonregular (void)
260 /* If we have a label that could be the target of a nonlocal goto, then
261 the cfg is not well structured. */
262 if (nonlocal_goto_handler_labels
)
265 /* If we have any forced labels, then the cfg is not well structured. */
269 /* If we have exception handlers, then we consider the cfg not well
270 structured. ?!? We should be able to handle this now that we
271 compute an accurate cfg for EH. */
272 if (current_function_has_exception_handlers ())
275 /* If we have insns which refer to labels as non-jumped-to operands,
276 then we consider the cfg not well structured. */
277 FOR_EACH_BB_FN (b
, cfun
)
278 FOR_BB_INSNS (b
, insn
)
283 /* If this function has a computed jump, then we consider the cfg
284 not well structured. */
285 if (JUMP_P (insn
) && computed_jump_p (insn
))
291 note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
);
292 if (note
== NULL_RTX
)
295 /* For that label not to be seen as a referred-to label, this
296 must be a single-set which is feeding a jump *only*. This
297 could be a conditional jump with the label split off for
298 machine-specific reasons or a casesi/tablejump. */
299 next
= next_nonnote_insn (insn
);
302 || (JUMP_LABEL (next
) != XEXP (note
, 0)
303 && find_reg_note (next
, REG_LABEL_TARGET
,
304 XEXP (note
, 0)) == NULL_RTX
)
305 || BLOCK_FOR_INSN (insn
) != BLOCK_FOR_INSN (next
))
308 set
= single_set (insn
);
312 dest
= SET_DEST (set
);
313 if (!REG_P (dest
) || !dead_or_set_p (next
, dest
))
317 /* Unreachable loops with more than one basic block are detected
318 during the DFS traversal in find_rgns.
320 Unreachable loops with a single block are detected here. This
321 test is redundant with the one in find_rgns, but it's much
322 cheaper to go ahead and catch the trivial case here. */
323 FOR_EACH_BB_FN (b
, cfun
)
325 if (EDGE_COUNT (b
->preds
) == 0
326 || (single_pred_p (b
)
327 && single_pred (b
) == b
))
331 /* All the tests passed. Consider the cfg well structured. */
335 /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */
338 extract_edgelst (sbitmap set
, edgelst
*el
)
341 sbitmap_iterator sbi
;
343 /* edgelst table space is reused in each call to extract_edgelst. */
346 el
->first_member
= &edgelst_table
[edgelst_last
];
349 /* Iterate over each word in the bitset. */
350 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, sbi
)
352 edgelst_table
[edgelst_last
++] = rgn_edges
[i
];
357 /* Functions for the construction of regions. */
359 /* Print the regions, for debugging purposes. Callable from debugger. */
366 fprintf (sched_dump
, "\n;; ------------ REGIONS ----------\n\n");
367 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
369 fprintf (sched_dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
370 rgn_table
[rgn
].rgn_nr_blocks
);
371 fprintf (sched_dump
, ";;\tbb/block: ");
373 /* We don't have ebb_head initialized yet, so we can't use
375 current_blocks
= RGN_BLOCKS (rgn
);
377 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
378 fprintf (sched_dump
, " %d/%d ", bb
, rgn_bb_table
[current_blocks
+ bb
]);
380 fprintf (sched_dump
, "\n\n");
384 /* Print the region's basic blocks. */
387 debug_region (int rgn
)
391 fprintf (stderr
, "\n;; ------------ REGION %d ----------\n\n", rgn
);
392 fprintf (stderr
, ";;\trgn %d nr_blocks %d:\n", rgn
,
393 rgn_table
[rgn
].rgn_nr_blocks
);
394 fprintf (stderr
, ";;\tbb/block: ");
396 /* We don't have ebb_head initialized yet, so we can't use
398 current_blocks
= RGN_BLOCKS (rgn
);
400 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
401 fprintf (stderr
, " %d/%d ", bb
, rgn_bb_table
[current_blocks
+ bb
]);
403 fprintf (stderr
, "\n\n");
405 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
408 BASIC_BLOCK_FOR_FN (cfun
, rgn_bb_table
[current_blocks
+ bb
]),
409 0, TDF_SLIM
| TDF_BLOCKS
);
410 fprintf (stderr
, "\n");
413 fprintf (stderr
, "\n");
417 /* True when a bb with index BB_INDEX contained in region RGN. */
419 bb_in_region_p (int bb_index
, int rgn
)
423 for (i
= 0; i
< rgn_table
[rgn
].rgn_nr_blocks
; i
++)
424 if (rgn_bb_table
[current_blocks
+ i
] == bb_index
)
430 /* Dump region RGN to file F using dot syntax. */
432 dump_region_dot (FILE *f
, int rgn
)
436 fprintf (f
, "digraph Region_%d {\n", rgn
);
438 /* We don't have ebb_head initialized yet, so we can't use
440 current_blocks
= RGN_BLOCKS (rgn
);
442 for (i
= 0; i
< rgn_table
[rgn
].rgn_nr_blocks
; i
++)
446 int src_bb_num
= rgn_bb_table
[current_blocks
+ i
];
447 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, src_bb_num
);
449 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
450 if (bb_in_region_p (e
->dest
->index
, rgn
))
451 fprintf (f
, "\t%d -> %d\n", src_bb_num
, e
->dest
->index
);
456 /* The same, but first open a file specified by FNAME. */
458 dump_region_dot_file (const char *fname
, int rgn
)
460 FILE *f
= fopen (fname
, "wt");
461 dump_region_dot (f
, rgn
);
465 /* Build a single block region for each basic block in the function.
466 This allows for using the same code for interblock and basic block
470 find_single_block_region (bool ebbs_p
)
472 basic_block bb
, ebb_start
;
478 int probability_cutoff
;
479 if (profile_info
&& flag_branch_probabilities
)
480 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK
);
482 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY
);
483 probability_cutoff
= REG_BR_PROB_BASE
/ 100 * probability_cutoff
;
485 FOR_EACH_BB_FN (ebb_start
, cfun
)
487 RGN_NR_BLOCKS (nr_regions
) = 0;
488 RGN_BLOCKS (nr_regions
) = i
;
489 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
490 RGN_HAS_REAL_EBB (nr_regions
) = 0;
492 for (bb
= ebb_start
; ; bb
= bb
->next_bb
)
496 rgn_bb_table
[i
] = bb
->index
;
497 RGN_NR_BLOCKS (nr_regions
)++;
498 CONTAINING_RGN (bb
->index
) = nr_regions
;
499 BLOCK_TO_BB (bb
->index
) = i
- RGN_BLOCKS (nr_regions
);
502 if (bb
->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
503 || LABEL_P (BB_HEAD (bb
->next_bb
)))
506 e
= find_fallthru_edge (bb
->succs
);
509 if (e
->probability
<= probability_cutoff
)
518 FOR_EACH_BB_FN (bb
, cfun
)
520 rgn_bb_table
[nr_regions
] = bb
->index
;
521 RGN_NR_BLOCKS (nr_regions
) = 1;
522 RGN_BLOCKS (nr_regions
) = nr_regions
;
523 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
524 RGN_HAS_REAL_EBB (nr_regions
) = 0;
526 CONTAINING_RGN (bb
->index
) = nr_regions
;
527 BLOCK_TO_BB (bb
->index
) = 0;
532 /* Estimate number of the insns in the BB. */
534 rgn_estimate_number_of_insns (basic_block bb
)
538 count
= INSN_LUID (BB_END (bb
)) - INSN_LUID (BB_HEAD (bb
));
540 if (MAY_HAVE_DEBUG_INSNS
)
544 FOR_BB_INSNS (bb
, insn
)
545 if (DEBUG_INSN_P (insn
))
552 /* Update number of blocks and the estimate for number of insns
553 in the region. Return true if the region is "too large" for interblock
554 scheduling (compile time considerations). */
557 too_large (int block
, int *num_bbs
, int *num_insns
)
560 (*num_insns
) += (common_sched_info
->estimate_number_of_insns
561 (BASIC_BLOCK_FOR_FN (cfun
, block
)));
563 return ((*num_bbs
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS
))
564 || (*num_insns
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS
)));
567 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
568 is still an inner loop. Put in max_hdr[blk] the header of the most inner
569 loop containing blk. */
570 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
572 if (max_hdr[blk] == -1) \
573 max_hdr[blk] = hdr; \
574 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
575 bitmap_clear_bit (inner, hdr); \
576 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
578 bitmap_clear_bit (inner,max_hdr[blk]); \
579 max_hdr[blk] = hdr; \
583 /* Find regions for interblock scheduling.
585 A region for scheduling can be:
587 * A loop-free procedure, or
589 * A reducible inner loop, or
591 * A basic block not contained in any other region.
593 ?!? In theory we could build other regions based on extended basic
594 blocks or reverse extended basic blocks. Is it worth the trouble?
596 Loop blocks that form a region are put into the region's block list
597 in topological order.
599 This procedure stores its results into the following global (ick) variables
607 We use dominator relationships to avoid making regions out of non-reducible
610 This procedure needs to be converted to work on pred/succ lists instead
611 of edge tables. That would simplify it somewhat. */
614 haifa_find_rgns (void)
616 int *max_hdr
, *dfs_nr
, *degree
;
618 int node
, child
, loop_head
, i
, head
, tail
;
619 int count
= 0, sp
, idx
= 0;
620 edge_iterator current_edge
;
621 edge_iterator
*stack
;
622 int num_bbs
, num_insns
, unreachable
;
623 int too_large_failure
;
626 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
627 and a mapping from block to its loop header (if the block is contained
630 Store results in HEADER, INNER, and MAX_HDR respectively, these will
631 be used as inputs to the second traversal.
633 STACK, SP and DFS_NR are only used during the first traversal. */
635 /* Allocate and initialize variables for the first traversal. */
636 max_hdr
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
637 dfs_nr
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
638 stack
= XNEWVEC (edge_iterator
, n_edges_for_fn (cfun
));
640 /* Note if a block is a natural inner loop header. */
641 auto_sbitmap
inner (last_basic_block_for_fn (cfun
));
644 /* Note if a block is a natural loop header. */
645 auto_sbitmap
header (last_basic_block_for_fn (cfun
));
646 bitmap_clear (header
);
648 /* Note if a block is in the block queue. */
649 auto_sbitmap
in_queue (last_basic_block_for_fn (cfun
));
650 bitmap_clear (in_queue
);
652 /* Note if a block is in the block queue. */
653 auto_sbitmap
in_stack (last_basic_block_for_fn (cfun
));
654 bitmap_clear (in_stack
);
656 for (i
= 0; i
< last_basic_block_for_fn (cfun
); i
++)
659 #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
660 #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
662 /* DFS traversal to find inner loops in the cfg. */
664 current_edge
= ei_start (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->succs
);
669 if (EDGE_PASSED (current_edge
))
671 /* We have reached a leaf node or a node that was already
672 processed. Pop edges off the stack until we find
673 an edge that has not yet been processed. */
674 while (sp
>= 0 && EDGE_PASSED (current_edge
))
676 /* Pop entry off the stack. */
677 current_edge
= stack
[sp
--];
678 node
= ei_edge (current_edge
)->src
->index
;
679 gcc_assert (node
!= ENTRY_BLOCK
);
680 child
= ei_edge (current_edge
)->dest
->index
;
681 gcc_assert (child
!= EXIT_BLOCK
);
682 bitmap_clear_bit (in_stack
, child
);
683 if (max_hdr
[child
] >= 0 && bitmap_bit_p (in_stack
, max_hdr
[child
]))
684 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
685 ei_next (¤t_edge
);
688 /* See if have finished the DFS tree traversal. */
689 if (sp
< 0 && EDGE_PASSED (current_edge
))
692 /* Nope, continue the traversal with the popped node. */
696 /* Process a node. */
697 node
= ei_edge (current_edge
)->src
->index
;
698 gcc_assert (node
!= ENTRY_BLOCK
);
699 bitmap_set_bit (in_stack
, node
);
700 dfs_nr
[node
] = ++count
;
702 /* We don't traverse to the exit block. */
703 child
= ei_edge (current_edge
)->dest
->index
;
704 if (child
== EXIT_BLOCK
)
706 SET_EDGE_PASSED (current_edge
);
707 ei_next (¤t_edge
);
711 /* If the successor is in the stack, then we've found a loop.
712 Mark the loop, if it is not a natural loop, then it will
713 be rejected during the second traversal. */
714 if (bitmap_bit_p (in_stack
, child
))
717 bitmap_set_bit (header
, child
);
718 UPDATE_LOOP_RELATIONS (node
, child
);
719 SET_EDGE_PASSED (current_edge
);
720 ei_next (¤t_edge
);
724 /* If the child was already visited, then there is no need to visit
725 it again. Just update the loop relationships and restart
729 if (max_hdr
[child
] >= 0 && bitmap_bit_p (in_stack
, max_hdr
[child
]))
730 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
731 SET_EDGE_PASSED (current_edge
);
732 ei_next (¤t_edge
);
736 /* Push an entry on the stack and continue DFS traversal. */
737 stack
[++sp
] = current_edge
;
738 SET_EDGE_PASSED (current_edge
);
739 current_edge
= ei_start (ei_edge (current_edge
)->dest
->succs
);
742 /* Reset ->aux field used by EDGE_PASSED. */
743 FOR_ALL_BB_FN (bb
, cfun
)
747 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
752 /* Another check for unreachable blocks. The earlier test in
753 is_cfg_nonregular only finds unreachable blocks that do not
756 The DFS traversal will mark every block that is reachable from
757 the entry node by placing a nonzero value in dfs_nr. Thus if
758 dfs_nr is zero for any block, then it must be unreachable. */
760 FOR_EACH_BB_FN (bb
, cfun
)
761 if (dfs_nr
[bb
->index
] == 0)
767 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
768 to hold degree counts. */
771 FOR_EACH_BB_FN (bb
, cfun
)
772 degree
[bb
->index
] = EDGE_COUNT (bb
->preds
);
774 /* Do not perform region scheduling if there are any unreachable
778 int *queue
, *degree1
= NULL
;
779 /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
780 there basic blocks, which are forced to be region heads.
781 This is done to try to assemble few smaller regions
782 from a too_large region. */
783 sbitmap extended_rgn_header
= NULL
;
784 bool extend_regions_p
;
787 bitmap_set_bit (header
, 0);
789 /* Second traversal:find reducible inner loops and topologically sort
790 block of each region. */
792 queue
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
794 extend_regions_p
= PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS
) > 0;
795 if (extend_regions_p
)
797 degree1
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
798 extended_rgn_header
=
799 sbitmap_alloc (last_basic_block_for_fn (cfun
));
800 bitmap_clear (extended_rgn_header
);
803 /* Find blocks which are inner loop headers. We still have non-reducible
804 loops to consider at this point. */
805 FOR_EACH_BB_FN (bb
, cfun
)
807 if (bitmap_bit_p (header
, bb
->index
) && bitmap_bit_p (inner
, bb
->index
))
813 /* Now check that the loop is reducible. We do this separate
814 from finding inner loops so that we do not find a reducible
815 loop which contains an inner non-reducible loop.
817 A simple way to find reducible/natural loops is to verify
818 that each block in the loop is dominated by the loop
821 If there exists a block that is not dominated by the loop
822 header, then the block is reachable from outside the loop
823 and thus the loop is not a natural loop. */
824 FOR_EACH_BB_FN (jbb
, cfun
)
826 /* First identify blocks in the loop, except for the loop
828 if (bb
->index
== max_hdr
[jbb
->index
] && bb
!= jbb
)
830 /* Now verify that the block is dominated by the loop
832 if (!dominated_by_p (CDI_DOMINATORS
, jbb
, bb
))
837 /* If we exited the loop early, then I is the header of
838 a non-reducible loop and we should quit processing it
840 if (jbb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
843 /* I is a header of an inner loop, or block 0 in a subroutine
844 with no loops at all. */
846 too_large_failure
= 0;
847 loop_head
= max_hdr
[bb
->index
];
849 if (extend_regions_p
)
850 /* We save degree in case when we meet a too_large region
851 and cancel it. We need a correct degree later when
852 calling extend_rgns. */
853 memcpy (degree1
, degree
,
854 last_basic_block_for_fn (cfun
) * sizeof (int));
856 /* Decrease degree of all I's successors for topological
858 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
859 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
860 --degree
[e
->dest
->index
];
862 /* Estimate # insns, and count # blocks in the region. */
864 num_insns
= common_sched_info
->estimate_number_of_insns (bb
);
866 /* Find all loop latches (blocks with back edges to the loop
867 header) or all the leaf blocks in the cfg has no loops.
869 Place those blocks into the queue. */
872 FOR_EACH_BB_FN (jbb
, cfun
)
873 /* Leaf nodes have only a single successor which must
875 if (single_succ_p (jbb
)
876 && single_succ (jbb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
878 queue
[++tail
] = jbb
->index
;
879 bitmap_set_bit (in_queue
, jbb
->index
);
881 if (too_large (jbb
->index
, &num_bbs
, &num_insns
))
883 too_large_failure
= 1;
892 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
894 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
897 node
= e
->src
->index
;
899 if (max_hdr
[node
] == loop_head
&& node
!= bb
->index
)
901 /* This is a loop latch. */
902 queue
[++tail
] = node
;
903 bitmap_set_bit (in_queue
, node
);
905 if (too_large (node
, &num_bbs
, &num_insns
))
907 too_large_failure
= 1;
914 /* Now add all the blocks in the loop to the queue.
916 We know the loop is a natural loop; however the algorithm
917 above will not always mark certain blocks as being in the
925 The algorithm in the DFS traversal may not mark B & D as part
926 of the loop (i.e. they will not have max_hdr set to A).
928 We know they can not be loop latches (else they would have
929 had max_hdr set since they'd have a backedge to a dominator
930 block). So we don't need them on the initial queue.
932 We know they are part of the loop because they are dominated
933 by the loop header and can be reached by a backwards walk of
934 the edges starting with nodes on the initial queue.
936 It is safe and desirable to include those nodes in the
937 loop/scheduling region. To do so we would need to decrease
938 the degree of a node if it is the target of a backedge
939 within the loop itself as the node is placed in the queue.
941 We do not do this because I'm not sure that the actual
942 scheduling code will properly handle this case. ?!? */
944 while (head
< tail
&& !too_large_failure
)
947 child
= queue
[++head
];
949 FOR_EACH_EDGE (e
, ei
,
950 BASIC_BLOCK_FOR_FN (cfun
, child
)->preds
)
952 node
= e
->src
->index
;
954 /* See discussion above about nodes not marked as in
955 this loop during the initial DFS traversal. */
956 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
957 || max_hdr
[node
] != loop_head
)
962 else if (!bitmap_bit_p (in_queue
, node
) && node
!= bb
->index
)
964 queue
[++tail
] = node
;
965 bitmap_set_bit (in_queue
, node
);
967 if (too_large (node
, &num_bbs
, &num_insns
))
969 too_large_failure
= 1;
976 if (tail
>= 0 && !too_large_failure
)
978 /* Place the loop header into list of region blocks. */
979 degree
[bb
->index
] = -1;
980 rgn_bb_table
[idx
] = bb
->index
;
981 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
982 RGN_BLOCKS (nr_regions
) = idx
++;
983 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
984 RGN_HAS_REAL_EBB (nr_regions
) = 0;
985 CONTAINING_RGN (bb
->index
) = nr_regions
;
986 BLOCK_TO_BB (bb
->index
) = count
= 0;
988 /* Remove blocks from queue[] when their in degree
989 becomes zero. Repeat until no blocks are left on the
990 list. This produces a topological list of blocks in
997 if (degree
[child
] == 0)
1002 rgn_bb_table
[idx
++] = child
;
1003 BLOCK_TO_BB (child
) = ++count
;
1004 CONTAINING_RGN (child
) = nr_regions
;
1005 queue
[head
] = queue
[tail
--];
1007 FOR_EACH_EDGE (e
, ei
,
1008 BASIC_BLOCK_FOR_FN (cfun
,
1010 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1011 --degree
[e
->dest
->index
];
1018 else if (extend_regions_p
)
1020 /* Restore DEGREE. */
1026 /* And force successors of BB to be region heads.
1027 This may provide several smaller regions instead
1028 of one too_large region. */
1029 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1030 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1031 bitmap_set_bit (extended_rgn_header
, e
->dest
->index
);
1037 if (extend_regions_p
)
1041 bitmap_ior (header
, header
, extended_rgn_header
);
1042 sbitmap_free (extended_rgn_header
);
1044 extend_rgns (degree
, &idx
, header
, max_hdr
);
1048 /* Any block that did not end up in a region is placed into a region
1050 FOR_EACH_BB_FN (bb
, cfun
)
1051 if (degree
[bb
->index
] >= 0)
1053 rgn_bb_table
[idx
] = bb
->index
;
1054 RGN_NR_BLOCKS (nr_regions
) = 1;
1055 RGN_BLOCKS (nr_regions
) = idx
++;
1056 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1057 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1058 CONTAINING_RGN (bb
->index
) = nr_regions
++;
1059 BLOCK_TO_BB (bb
->index
) = 0;
1068 /* Wrapper function.
1069 If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
1070 regions. Otherwise just call find_rgns_haifa. */
1074 if (sel_sched_p () && flag_sel_sched_pipelining
)
1080 static int gather_region_statistics (int **);
1081 static void print_region_statistics (int *, int, int *, int);
1083 /* Calculate the histogram that shows the number of regions having the
1084 given number of basic blocks, and store it in the RSP array. Return
1085 the size of this array. */
1087 gather_region_statistics (int **rsp
)
1089 int i
, *a
= 0, a_sz
= 0;
1091 /* a[i] is the number of regions that have (i + 1) basic blocks. */
1092 for (i
= 0; i
< nr_regions
; i
++)
1094 int nr_blocks
= RGN_NR_BLOCKS (i
);
1096 gcc_assert (nr_blocks
>= 1);
1098 if (nr_blocks
> a_sz
)
1100 a
= XRESIZEVEC (int, a
, nr_blocks
);
1103 while (a_sz
!= nr_blocks
);
1113 /* Print regions statistics. S1 and S2 denote the data before and after
1114 calling extend_rgns, respectively. */
1116 print_region_statistics (int *s1
, int s1_sz
, int *s2
, int s2_sz
)
1120 /* We iterate until s2_sz because extend_rgns does not decrease
1121 the maximal region size. */
1122 for (i
= 1; i
< s2_sz
; i
++)
1136 fprintf (sched_dump
, ";; Region extension statistics: size %d: " \
1137 "was %d + %d more\n", i
+ 1, n1
, n2
- n1
);
1142 DEGREE - Array of incoming edge count, considering only
1143 the edges, that don't have their sources in formed regions yet.
1144 IDXP - pointer to the next available index in rgn_bb_table.
1145 HEADER - set of all region heads.
1146 LOOP_HDR - mapping from block to the containing loop
1147 (two blocks can reside within one region if they have
1148 the same loop header). */
1150 extend_rgns (int *degree
, int *idxp
, sbitmap header
, int *loop_hdr
)
1152 int *order
, i
, rescan
= 0, idx
= *idxp
, iter
= 0, max_iter
, *max_hdr
;
1153 int nblocks
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
1155 max_iter
= PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS
);
1157 max_hdr
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1159 order
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1160 post_order_compute (order
, false, false);
1162 for (i
= nblocks
- 1; i
>= 0; i
--)
1165 if (degree
[bbn
] >= 0)
1171 /* This block already was processed in find_rgns. */
1175 /* The idea is to topologically walk through CFG in top-down order.
1176 During the traversal, if all the predecessors of a node are
1177 marked to be in the same region (they all have the same max_hdr),
1178 then current node is also marked to be a part of that region.
1179 Otherwise the node starts its own region.
1180 CFG should be traversed until no further changes are made. On each
1181 iteration the set of the region heads is extended (the set of those
1182 blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
1183 set of all basic blocks, thus the algorithm is guaranteed to
1186 while (rescan
&& iter
< max_iter
)
1190 for (i
= nblocks
- 1; i
>= 0; i
--)
1196 if (max_hdr
[bbn
] != -1 && !bitmap_bit_p (header
, bbn
))
1200 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK_FOR_FN (cfun
, bbn
)->preds
)
1202 int predn
= e
->src
->index
;
1204 if (predn
!= ENTRY_BLOCK
1205 /* If pred wasn't processed in find_rgns. */
1206 && max_hdr
[predn
] != -1
1207 /* And pred and bb reside in the same loop.
1208 (Or out of any loop). */
1209 && loop_hdr
[bbn
] == loop_hdr
[predn
])
1212 /* Then bb extends the containing region of pred. */
1213 hdr
= max_hdr
[predn
];
1214 else if (hdr
!= max_hdr
[predn
])
1215 /* Too bad, there are at least two predecessors
1216 that reside in different regions. Thus, BB should
1217 begin its own region. */
1224 /* BB starts its own region. */
1233 /* If BB start its own region,
1234 update set of headers with BB. */
1235 bitmap_set_bit (header
, bbn
);
1239 gcc_assert (hdr
!= -1);
1248 /* Statistics were gathered on the SPEC2000 package of tests with
1249 mainline weekly snapshot gcc-4.1-20051015 on ia64.
1251 Statistics for SPECint:
1252 1 iteration : 1751 cases (38.7%)
1253 2 iterations: 2770 cases (61.3%)
1254 Blocks wrapped in regions by find_rgns without extension: 18295 blocks
1255 Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
1256 (We don't count single block regions here).
1258 Statistics for SPECfp:
1259 1 iteration : 621 cases (35.9%)
1260 2 iterations: 1110 cases (64.1%)
1261 Blocks wrapped in regions by find_rgns without extension: 6476 blocks
1262 Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
1263 (We don't count single block regions here).
1265 By default we do at most 2 iterations.
1266 This can be overridden with max-sched-extend-regions-iters parameter:
1267 0 - disable region extension,
1268 N > 0 - do at most N iterations. */
1270 if (sched_verbose
&& iter
!= 0)
1271 fprintf (sched_dump
, ";; Region extension iterations: %d%s\n", iter
,
1272 rescan
? "... failed" : "");
1274 if (!rescan
&& iter
!= 0)
1276 int *s1
= NULL
, s1_sz
= 0;
1278 /* Save the old statistics for later printout. */
1279 if (sched_verbose
>= 6)
1280 s1_sz
= gather_region_statistics (&s1
);
1282 /* We have succeeded. Now assemble the regions. */
1283 for (i
= nblocks
- 1; i
>= 0; i
--)
1287 if (max_hdr
[bbn
] == bbn
)
1288 /* BBN is a region head. */
1292 int num_bbs
= 0, j
, num_insns
= 0, large
;
1294 large
= too_large (bbn
, &num_bbs
, &num_insns
);
1297 rgn_bb_table
[idx
] = bbn
;
1298 RGN_BLOCKS (nr_regions
) = idx
++;
1299 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1300 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1301 CONTAINING_RGN (bbn
) = nr_regions
;
1302 BLOCK_TO_BB (bbn
) = 0;
1304 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK_FOR_FN (cfun
, bbn
)->succs
)
1305 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1306 degree
[e
->dest
->index
]--;
1309 /* Here we check whether the region is too_large. */
1310 for (j
= i
- 1; j
>= 0; j
--)
1312 int succn
= order
[j
];
1313 if (max_hdr
[succn
] == bbn
)
1315 if ((large
= too_large (succn
, &num_bbs
, &num_insns
)))
1321 /* If the region is too_large, then wrap every block of
1322 the region into single block region.
1323 Here we wrap region head only. Other blocks are
1324 processed in the below cycle. */
1326 RGN_NR_BLOCKS (nr_regions
) = 1;
1332 for (j
= i
- 1; j
>= 0; j
--)
1334 int succn
= order
[j
];
1336 if (max_hdr
[succn
] == bbn
)
1337 /* This cycle iterates over all basic blocks, that
1338 are supposed to be in the region with head BBN,
1339 and wraps them into that region (or in single
1342 gcc_assert (degree
[succn
] == 0);
1345 rgn_bb_table
[idx
] = succn
;
1346 BLOCK_TO_BB (succn
) = large
? 0 : num_bbs
++;
1347 CONTAINING_RGN (succn
) = nr_regions
;
1350 /* Wrap SUCCN into single block region. */
1352 RGN_BLOCKS (nr_regions
) = idx
;
1353 RGN_NR_BLOCKS (nr_regions
) = 1;
1354 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1355 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1361 FOR_EACH_EDGE (e
, ei
,
1362 BASIC_BLOCK_FOR_FN (cfun
, succn
)->succs
)
1363 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1364 degree
[e
->dest
->index
]--;
1370 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1376 if (sched_verbose
>= 6)
1380 /* Get the new statistics and print the comparison with the
1381 one before calling this function. */
1382 s2_sz
= gather_region_statistics (&s2
);
1383 print_region_statistics (s1
, s1_sz
, s2
, s2_sz
);
1395 /* Functions for regions scheduling information. */
1397 /* Compute dominators, probability, and potential-split-edges of bb.
1398 Assume that these values were already computed for bb's predecessors. */
1401 compute_dom_prob_ps (int bb
)
1403 edge_iterator in_ei
;
1406 /* We shouldn't have any real ebbs yet. */
1407 gcc_assert (ebb_head
[bb
] == bb
+ current_blocks
);
1409 if (IS_RGN_ENTRY (bb
))
1411 bitmap_set_bit (dom
[bb
], 0);
1412 prob
[bb
] = REG_BR_PROB_BASE
;
1418 /* Initialize dom[bb] to '111..1'. */
1419 bitmap_ones (dom
[bb
]);
1421 FOR_EACH_EDGE (in_edge
, in_ei
,
1422 BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (bb
))->preds
)
1426 edge_iterator out_ei
;
1428 if (in_edge
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1431 pred_bb
= BLOCK_TO_BB (in_edge
->src
->index
);
1432 bitmap_and (dom
[bb
], dom
[bb
], dom
[pred_bb
]);
1433 bitmap_ior (ancestor_edges
[bb
],
1434 ancestor_edges
[bb
], ancestor_edges
[pred_bb
]);
1436 bitmap_set_bit (ancestor_edges
[bb
], EDGE_TO_BIT (in_edge
));
1438 bitmap_ior (pot_split
[bb
], pot_split
[bb
], pot_split
[pred_bb
]);
1440 FOR_EACH_EDGE (out_edge
, out_ei
, in_edge
->src
->succs
)
1441 bitmap_set_bit (pot_split
[bb
], EDGE_TO_BIT (out_edge
));
1443 prob
[bb
] += combine_probabilities (prob
[pred_bb
], in_edge
->probability
);
1444 // The rounding divide in combine_probabilities can result in an extra
1445 // probability increment propagating along 50-50 edges. Eventually when
1446 // the edges re-merge, the accumulated probability can go slightly above
1447 // REG_BR_PROB_BASE.
1448 if (prob
[bb
] > REG_BR_PROB_BASE
)
1449 prob
[bb
] = REG_BR_PROB_BASE
;
1452 bitmap_set_bit (dom
[bb
], bb
);
1453 bitmap_and_compl (pot_split
[bb
], pot_split
[bb
], ancestor_edges
[bb
]);
1455 if (sched_verbose
>= 2)
1456 fprintf (sched_dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
),
1457 (100 * prob
[bb
]) / REG_BR_PROB_BASE
);
1460 /* Functions for target info. */
1462 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1463 Note that bb_trg dominates bb_src. */
1466 split_edges (int bb_src
, int bb_trg
, edgelst
*bl
)
1468 auto_sbitmap
src (SBITMAP_SIZE (pot_split
[bb_src
]));
1469 bitmap_copy (src
, pot_split
[bb_src
]);
1471 bitmap_and_compl (src
, src
, pot_split
[bb_trg
]);
1472 extract_edgelst (src
, bl
);
1475 /* Find the valid candidate-source-blocks for the target block TRG, compute
1476 their probability, and check if they are speculative or not.
1477 For speculative sources, compute their update-blocks and split-blocks. */
1480 compute_trg_info (int trg
)
1483 edgelst el
= { NULL
, 0 };
1484 int i
, j
, k
, update_idx
;
1489 candidate_table
= XNEWVEC (candidate
, current_nr_blocks
);
1492 /* bblst_table holds split blocks and update blocks for each block after
1493 the current one in the region. split blocks and update blocks are
1494 the TO blocks of region edges, so there can be at most rgn_nr_edges
1496 bblst_size
= (current_nr_blocks
- target_bb
) * rgn_nr_edges
;
1497 bblst_table
= XNEWVEC (basic_block
, bblst_size
);
1500 edgelst_table
= XNEWVEC (edge
, rgn_nr_edges
);
1502 /* Define some of the fields for the target bb as well. */
1503 sp
= candidate_table
+ trg
;
1505 sp
->is_speculative
= 0;
1506 sp
->src_prob
= REG_BR_PROB_BASE
;
1508 auto_sbitmap
visited (last_basic_block_for_fn (cfun
));
1510 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1512 sp
= candidate_table
+ i
;
1514 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1517 int tf
= prob
[trg
], cf
= prob
[i
];
1519 /* In CFGs with low probability edges TF can possibly be zero. */
1520 sp
->src_prob
= (tf
? GCOV_COMPUTE_SCALE (cf
, tf
) : 0);
1521 sp
->is_valid
= (sp
->src_prob
>= min_spec_prob
);
1526 split_edges (i
, trg
, &el
);
1527 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1528 if (sp
->is_speculative
&& !flag_schedule_speculative
)
1534 /* Compute split blocks and store them in bblst_table.
1535 The TO block of every split edge is a split block. */
1536 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
1537 sp
->split_bbs
.nr_members
= el
.nr_members
;
1538 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
1539 bblst_table
[bblst_last
] = el
.first_member
[j
]->dest
;
1540 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
1542 /* Compute update blocks and store them in bblst_table.
1543 For every split edge, look at the FROM block, and check
1544 all out edges. For each out edge that is not a split edge,
1545 add the TO block to the update block list. This list can end
1546 up with a lot of duplicates. We need to weed them out to avoid
1547 overrunning the end of the bblst_table. */
1550 bitmap_clear (visited
);
1551 for (j
= 0; j
< el
.nr_members
; j
++)
1553 block
= el
.first_member
[j
]->src
;
1554 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1556 if (!bitmap_bit_p (visited
, e
->dest
->index
))
1558 for (k
= 0; k
< el
.nr_members
; k
++)
1559 if (e
== el
.first_member
[k
])
1562 if (k
>= el
.nr_members
)
1564 bblst_table
[bblst_last
++] = e
->dest
;
1565 bitmap_set_bit (visited
, e
->dest
->index
);
1571 sp
->update_bbs
.nr_members
= update_idx
;
1573 /* Make sure we didn't overrun the end of bblst_table. */
1574 gcc_assert (bblst_last
<= bblst_size
);
1578 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
1580 sp
->is_speculative
= 0;
1586 /* Free the computed target info. */
1588 free_trg_info (void)
1590 free (candidate_table
);
1592 free (edgelst_table
);
1595 /* Print candidates info, for debugging purposes. Callable from debugger. */
1598 debug_candidate (int i
)
1600 if (!candidate_table
[i
].is_valid
)
1603 if (candidate_table
[i
].is_speculative
)
1606 fprintf (sched_dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
1608 fprintf (sched_dump
, "split path: ");
1609 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
1611 int b
= candidate_table
[i
].split_bbs
.first_member
[j
]->index
;
1613 fprintf (sched_dump
, " %d ", b
);
1615 fprintf (sched_dump
, "\n");
1617 fprintf (sched_dump
, "update path: ");
1618 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
1620 int b
= candidate_table
[i
].update_bbs
.first_member
[j
]->index
;
1622 fprintf (sched_dump
, " %d ", b
);
1624 fprintf (sched_dump
, "\n");
1628 fprintf (sched_dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
1632 /* Print candidates info, for debugging purposes. Callable from debugger. */
1635 debug_candidates (int trg
)
1639 fprintf (sched_dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
1640 BB_TO_BLOCK (trg
), trg
);
1641 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1642 debug_candidate (i
);
1645 /* Functions for speculative scheduling. */
1647 static bitmap_head not_in_df
;
1649 /* Return 0 if x is a set of a register alive in the beginning of one
1650 of the split-blocks of src, otherwise return 1. */
1653 check_live_1 (int src
, rtx x
)
1657 rtx reg
= SET_DEST (x
);
1662 while (GET_CODE (reg
) == SUBREG
1663 || GET_CODE (reg
) == ZERO_EXTRACT
1664 || GET_CODE (reg
) == STRICT_LOW_PART
)
1665 reg
= XEXP (reg
, 0);
1667 if (GET_CODE (reg
) == PARALLEL
)
1671 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1672 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1673 if (check_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0)))
1682 regno
= REGNO (reg
);
1684 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
1686 /* Global registers are assumed live. */
1691 if (regno
< FIRST_PSEUDO_REGISTER
)
1693 /* Check for hard registers. */
1694 int j
= REG_NREGS (reg
);
1697 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1699 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1700 int t
= bitmap_bit_p (¬_in_df
, b
->index
);
1702 /* We can have split blocks, that were recently generated.
1703 Such blocks are always outside current region. */
1704 gcc_assert (!t
|| (CONTAINING_RGN (b
->index
)
1705 != CONTAINING_RGN (BB_TO_BLOCK (src
))));
1707 if (t
|| REGNO_REG_SET_P (df_get_live_in (b
), regno
+ j
))
1714 /* Check for pseudo registers. */
1715 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1717 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1718 int t
= bitmap_bit_p (¬_in_df
, b
->index
);
1720 gcc_assert (!t
|| (CONTAINING_RGN (b
->index
)
1721 != CONTAINING_RGN (BB_TO_BLOCK (src
))));
1723 if (t
|| REGNO_REG_SET_P (df_get_live_in (b
), regno
))
1732 /* If x is a set of a register R, mark that R is alive in the beginning
1733 of every update-block of src. */
1736 update_live_1 (int src
, rtx x
)
1740 rtx reg
= SET_DEST (x
);
1745 while (GET_CODE (reg
) == SUBREG
1746 || GET_CODE (reg
) == ZERO_EXTRACT
1747 || GET_CODE (reg
) == STRICT_LOW_PART
)
1748 reg
= XEXP (reg
, 0);
1750 if (GET_CODE (reg
) == PARALLEL
)
1754 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1755 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1756 update_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0));
1764 /* Global registers are always live, so the code below does not apply
1767 regno
= REGNO (reg
);
1769 if (! HARD_REGISTER_NUM_P (regno
)
1770 || !global_regs
[regno
])
1772 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
1774 basic_block b
= candidate_table
[src
].update_bbs
.first_member
[i
];
1775 bitmap_set_range (df_get_live_in (b
), regno
, REG_NREGS (reg
));
1780 /* Return 1 if insn can be speculatively moved from block src to trg,
1781 otherwise return 0. Called before first insertion of insn to
1782 ready-list or before the scheduling. */
1785 check_live (rtx_insn
*insn
, int src
)
1787 /* Find the registers set by instruction. */
1788 if (GET_CODE (PATTERN (insn
)) == SET
1789 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1790 return check_live_1 (src
, PATTERN (insn
));
1791 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1794 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1795 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1796 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1797 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
1806 /* Update the live registers info after insn was moved speculatively from
1807 block src to trg. */
1810 update_live (rtx_insn
*insn
, int src
)
1812 /* Find the registers set by instruction. */
1813 if (GET_CODE (PATTERN (insn
)) == SET
1814 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1815 update_live_1 (src
, PATTERN (insn
));
1816 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1819 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1820 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1821 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1822 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
1826 /* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1827 #define IS_REACHABLE(bb_from, bb_to) \
1829 || IS_RGN_ENTRY (bb_from) \
1830 || (bitmap_bit_p (ancestor_edges[bb_to], \
1831 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK_FOR_FN (cfun, \
1832 BB_TO_BLOCK (bb_from)))))))
1834 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1837 set_spec_fed (rtx load_insn
)
1839 sd_iterator_def sd_it
;
1842 FOR_EACH_DEP (load_insn
, SD_LIST_FORW
, sd_it
, dep
)
1843 if (DEP_TYPE (dep
) == REG_DEP_TRUE
)
1844 FED_BY_SPEC_LOAD (DEP_CON (dep
)) = 1;
1847 /* On the path from the insn to load_insn_bb, find a conditional
1848 branch depending on insn, that guards the speculative load. */
1851 find_conditional_protection (rtx_insn
*insn
, int load_insn_bb
)
1853 sd_iterator_def sd_it
;
1856 /* Iterate through DEF-USE forward dependences. */
1857 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
1859 rtx_insn
*next
= DEP_CON (dep
);
1861 if ((CONTAINING_RGN (BLOCK_NUM (next
)) ==
1862 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
1863 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
1864 && load_insn_bb
!= INSN_BB (next
)
1865 && DEP_TYPE (dep
) == REG_DEP_TRUE
1867 || find_conditional_protection (next
, load_insn_bb
)))
1871 } /* find_conditional_protection */
1873 /* Returns 1 if the same insn1 that participates in the computation
1874 of load_insn's address is feeding a conditional branch that is
1875 guarding on load_insn. This is true if we find two DEF-USE
1877 insn1 -> ... -> conditional-branch
1878 insn1 -> ... -> load_insn,
1879 and if a flow path exists:
1880 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1881 and if insn1 is on the path
1882 region-entry -> ... -> bb_trg -> ... load_insn.
1884 Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
1885 Locate the branch by following INSN_FORW_DEPS from insn1. */
1888 is_conditionally_protected (rtx load_insn
, int bb_src
, int bb_trg
)
1890 sd_iterator_def sd_it
;
1893 FOR_EACH_DEP (load_insn
, SD_LIST_BACK
, sd_it
, dep
)
1895 rtx_insn
*insn1
= DEP_PRO (dep
);
1897 /* Must be a DEF-USE dependence upon non-branch. */
1898 if (DEP_TYPE (dep
) != REG_DEP_TRUE
1902 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1903 if (INSN_BB (insn1
) == bb_src
1904 || (CONTAINING_RGN (BLOCK_NUM (insn1
))
1905 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
1906 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
1907 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
1910 /* Now search for the conditional-branch. */
1911 if (find_conditional_protection (insn1
, bb_src
))
1914 /* Recursive step: search another insn1, "above" current insn1. */
1915 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
1918 /* The chain does not exist. */
1920 } /* is_conditionally_protected */
1922 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1923 load_insn can move speculatively from bb_src to bb_trg. All the
1924 following must hold:
1926 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1927 (2) load_insn and load1 have a def-use dependence upon
1928 the same insn 'insn1'.
1929 (3) either load2 is in bb_trg, or:
1930 - there's only one split-block, and
1931 - load1 is on the escape path, and
1933 From all these we can conclude that the two loads access memory
1934 addresses that differ at most by a constant, and hence if moving
1935 load_insn would cause an exception, it would have been caused by
1939 is_pfree (rtx load_insn
, int bb_src
, int bb_trg
)
1941 sd_iterator_def back_sd_it
;
1943 candidate
*candp
= candidate_table
+ bb_src
;
1945 if (candp
->split_bbs
.nr_members
!= 1)
1946 /* Must have exactly one escape block. */
1949 FOR_EACH_DEP (load_insn
, SD_LIST_BACK
, back_sd_it
, back_dep
)
1951 rtx_insn
*insn1
= DEP_PRO (back_dep
);
1953 if (DEP_TYPE (back_dep
) == REG_DEP_TRUE
)
1954 /* Found a DEF-USE dependence (insn1, load_insn). */
1956 sd_iterator_def fore_sd_it
;
1959 FOR_EACH_DEP (insn1
, SD_LIST_FORW
, fore_sd_it
, fore_dep
)
1961 rtx_insn
*insn2
= DEP_CON (fore_dep
);
1963 if (DEP_TYPE (fore_dep
) == REG_DEP_TRUE
)
1965 /* Found a DEF-USE dependence (insn1, insn2). */
1966 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
1967 /* insn2 not guaranteed to be a 1 base reg load. */
1970 if (INSN_BB (insn2
) == bb_trg
)
1971 /* insn2 is the similar load, in the target block. */
1974 if (*(candp
->split_bbs
.first_member
) == BLOCK_FOR_INSN (insn2
))
1975 /* insn2 is a similar load, in a split-block. */
1982 /* Couldn't find a similar load. */
1986 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1987 a load moved speculatively, or if load_insn is protected by
1988 a compare on load_insn's address). */
1991 is_prisky (rtx load_insn
, int bb_src
, int bb_trg
)
1993 if (FED_BY_SPEC_LOAD (load_insn
))
1996 if (sd_lists_empty_p (load_insn
, SD_LIST_BACK
))
1997 /* Dependence may 'hide' out of the region. */
2000 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2006 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2007 Return 1 if insn is exception-free (and the motion is valid)
2011 is_exception_free (rtx_insn
*insn
, int bb_src
, int bb_trg
)
2013 int insn_class
= haifa_classify_insn (insn
);
2015 /* Handle non-load insns. */
2026 if (!flag_schedule_speculative_load
)
2028 IS_LOAD_INSN (insn
) = 1;
2035 case PFREE_CANDIDATE
:
2036 if (is_pfree (insn
, bb_src
, bb_trg
))
2038 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2039 case PRISKY_CANDIDATE
:
2040 if (!flag_schedule_speculative_load_dangerous
2041 || is_prisky (insn
, bb_src
, bb_trg
))
2047 return flag_schedule_speculative_load_dangerous
;
2050 /* The number of insns from the current block scheduled so far. */
2051 static int sched_target_n_insns
;
2052 /* The number of insns from the current block to be scheduled in total. */
2053 static int target_n_insns
;
2054 /* The number of insns from the entire region scheduled so far. */
2055 static int sched_n_insns
;
2057 /* Implementations of the sched_info functions for region scheduling. */
2058 static void init_ready_list (void);
2059 static int can_schedule_ready_p (rtx_insn
*);
2060 static void begin_schedule_ready (rtx_insn
*);
2061 static ds_t
new_ready (rtx_insn
*, ds_t
);
2062 static int schedule_more_p (void);
2063 static const char *rgn_print_insn (const rtx_insn
*, int);
2064 static int rgn_rank (rtx_insn
*, rtx_insn
*);
2065 static void compute_jump_reg_dependencies (rtx
, regset
);
2067 /* Functions for speculative scheduling. */
2068 static void rgn_add_remove_insn (rtx_insn
*, int);
2069 static void rgn_add_block (basic_block
, basic_block
);
2070 static void rgn_fix_recovery_cfg (int, int, int);
2071 static basic_block
advance_target_bb (basic_block
, rtx_insn
*);
2073 /* Return nonzero if there are more insns that should be scheduled. */
2076 schedule_more_p (void)
2078 return sched_target_n_insns
< target_n_insns
;
2081 /* Add all insns that are initially ready to the ready list READY. Called
2082 once before scheduling a set of insns. */
2085 init_ready_list (void)
2087 rtx_insn
*prev_head
= current_sched_info
->prev_head
;
2088 rtx_insn
*next_tail
= current_sched_info
->next_tail
;
2093 sched_target_n_insns
= 0;
2096 /* Print debugging information. */
2097 if (sched_verbose
>= 5)
2098 debug_rgn_dependencies (target_bb
);
2100 /* Prepare current target block info. */
2101 if (current_nr_blocks
> 1)
2102 compute_trg_info (target_bb
);
2104 /* Initialize ready list with all 'ready' insns in target block.
2105 Count number of insns in the target block being scheduled. */
2106 for (insn
= NEXT_INSN (prev_head
); insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2108 gcc_assert (TODO_SPEC (insn
) == HARD_DEP
|| TODO_SPEC (insn
) == DEP_POSTPONED
);
2109 TODO_SPEC (insn
) = HARD_DEP
;
2113 gcc_assert (!(TODO_SPEC (insn
) & BEGIN_CONTROL
));
2116 /* Add to ready list all 'ready' insns in valid source blocks.
2117 For speculative insns, check-live, exception-free, and
2119 for (bb_src
= target_bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
2120 if (IS_VALID (bb_src
))
2123 rtx_insn
*src_next_tail
;
2124 rtx_insn
*tail
, *head
;
2126 get_ebb_head_tail (EBB_FIRST_BB (bb_src
), EBB_LAST_BB (bb_src
),
2128 src_next_tail
= NEXT_INSN (tail
);
2131 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
2134 gcc_assert (TODO_SPEC (insn
) == HARD_DEP
|| TODO_SPEC (insn
) == DEP_POSTPONED
);
2135 TODO_SPEC (insn
) = HARD_DEP
;
2141 /* Called after taking INSN from the ready list. Returns nonzero if this
2142 insn can be scheduled, nonzero if we should silently discard it. */
2145 can_schedule_ready_p (rtx_insn
*insn
)
2147 /* An interblock motion? */
2148 if (INSN_BB (insn
) != target_bb
2149 && IS_SPECULATIVE_INSN (insn
)
2150 && !check_live (insn
, INSN_BB (insn
)))
2156 /* Updates counter and other information. Split from can_schedule_ready_p ()
2157 because when we schedule insn speculatively then insn passed to
2158 can_schedule_ready_p () differs from the one passed to
2159 begin_schedule_ready (). */
2161 begin_schedule_ready (rtx_insn
*insn
)
2163 /* An interblock motion? */
2164 if (INSN_BB (insn
) != target_bb
)
2166 if (IS_SPECULATIVE_INSN (insn
))
2168 gcc_assert (check_live (insn
, INSN_BB (insn
)));
2170 update_live (insn
, INSN_BB (insn
));
2172 /* For speculative load, mark insns fed by it. */
2173 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
2174 set_spec_fed (insn
);
2182 /* In block motion. */
2183 sched_target_n_insns
++;
2188 /* Called after INSN has all its hard dependencies resolved and the speculation
2189 of type TS is enough to overcome them all.
2190 Return nonzero if it should be moved to the ready list or the queue, or zero
2191 if we should silently discard it. */
2193 new_ready (rtx_insn
*next
, ds_t ts
)
2195 if (INSN_BB (next
) != target_bb
)
2197 int not_ex_free
= 0;
2199 /* For speculative insns, before inserting to ready/queue,
2200 check live, exception-free, and issue-delay. */
2201 if (!IS_VALID (INSN_BB (next
))
2203 || (IS_SPECULATIVE_INSN (next
)
2204 && ((recog_memoized (next
) >= 0
2205 && min_insn_conflict_delay (curr_state
, next
, next
)
2206 > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY
))
2207 || IS_SPECULATION_CHECK_P (next
)
2208 || !check_live (next
, INSN_BB (next
))
2209 || (not_ex_free
= !is_exception_free (next
, INSN_BB (next
),
2213 /* We are here because is_exception_free () == false.
2214 But we possibly can handle that with control speculation. */
2215 && sched_deps_info
->generate_spec_deps
2216 && spec_info
->mask
& BEGIN_CONTROL
)
2220 /* Add control speculation to NEXT's dependency type. */
2221 new_ds
= set_dep_weak (ts
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
2223 /* Check if NEXT can be speculated with new dependency type. */
2224 if (sched_insn_is_legitimate_for_speculation_p (next
, new_ds
))
2225 /* Here we got new control-speculative instruction. */
2228 /* NEXT isn't ready yet. */
2232 /* NEXT isn't ready yet. */
2240 /* Return a string that contains the insn uid and optionally anything else
2241 necessary to identify this insn in an output. It's valid to use a
2242 static buffer for this. The ALIGNED parameter should cause the string
2243 to be formatted so that multiple output lines will line up nicely. */
2246 rgn_print_insn (const rtx_insn
*insn
, int aligned
)
2248 static char tmp
[80];
2251 sprintf (tmp
, "b%3d: i%4d", INSN_BB (insn
), INSN_UID (insn
));
2254 if (current_nr_blocks
> 1 && INSN_BB (insn
) != target_bb
)
2255 sprintf (tmp
, "%d/b%d", INSN_UID (insn
), INSN_BB (insn
));
2257 sprintf (tmp
, "%d", INSN_UID (insn
));
2262 /* Compare priority of two insns. Return a positive number if the second
2263 insn is to be preferred for scheduling, and a negative one if the first
2264 is to be preferred. Zero if they are equally good. */
2267 rgn_rank (rtx_insn
*insn1
, rtx_insn
*insn2
)
2269 /* Some comparison make sense in interblock scheduling only. */
2270 if (INSN_BB (insn1
) != INSN_BB (insn2
))
2272 int spec_val
, prob_val
;
2274 /* Prefer an inblock motion on an interblock motion. */
2275 if ((INSN_BB (insn2
) == target_bb
) && (INSN_BB (insn1
) != target_bb
))
2277 if ((INSN_BB (insn1
) == target_bb
) && (INSN_BB (insn2
) != target_bb
))
2280 /* Prefer a useful motion on a speculative one. */
2281 spec_val
= IS_SPECULATIVE_INSN (insn1
) - IS_SPECULATIVE_INSN (insn2
);
2285 /* Prefer a more probable (speculative) insn. */
2286 prob_val
= INSN_PROBABILITY (insn2
) - INSN_PROBABILITY (insn1
);
2293 /* NEXT is an instruction that depends on INSN (a backward dependence);
2294 return nonzero if we should include this dependence in priority
2298 contributes_to_priority (rtx_insn
*next
, rtx_insn
*insn
)
2300 /* NEXT and INSN reside in one ebb. */
2301 return BLOCK_TO_BB (BLOCK_NUM (next
)) == BLOCK_TO_BB (BLOCK_NUM (insn
));
2304 /* INSN is a JUMP_INSN. Store the set of registers that must be
2305 considered as used by this jump in USED. */
2308 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
2309 regset used ATTRIBUTE_UNUSED
)
2311 /* Nothing to do here, since we postprocess jumps in
2312 add_branch_dependences. */
2315 /* This variable holds common_sched_info hooks and data relevant to
2316 the interblock scheduler. */
2317 static struct common_sched_info_def rgn_common_sched_info
;
2320 /* This holds data for the dependence analysis relevant to
2321 the interblock scheduler. */
2322 static struct sched_deps_info_def rgn_sched_deps_info
;
2324 /* This holds constant data used for initializing the above structure
2325 for the Haifa scheduler. */
2326 static const struct sched_deps_info_def rgn_const_sched_deps_info
=
2328 compute_jump_reg_dependencies
,
2329 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
2333 /* Same as above, but for the selective scheduler. */
2334 static const struct sched_deps_info_def rgn_const_sel_sched_deps_info
=
2336 compute_jump_reg_dependencies
,
2337 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
2341 /* Return true if scheduling INSN will trigger finish of scheduling
2344 rgn_insn_finishes_block_p (rtx_insn
*insn
)
2346 if (INSN_BB (insn
) == target_bb
2347 && sched_target_n_insns
+ 1 == target_n_insns
)
2348 /* INSN is the last not-scheduled instruction in the current block. */
2354 /* Used in schedule_insns to initialize current_sched_info for scheduling
2355 regions (or single basic blocks). */
2357 static const struct haifa_sched_info rgn_const_sched_info
=
2360 can_schedule_ready_p
,
2365 contributes_to_priority
,
2366 rgn_insn_finishes_block_p
,
2372 rgn_add_remove_insn
,
2373 begin_schedule_ready
,
2380 /* This variable holds the data and hooks needed to the Haifa scheduler backend
2381 for the interblock scheduler frontend. */
2382 static struct haifa_sched_info rgn_sched_info
;
2384 /* Returns maximum priority that an insn was assigned to. */
2387 get_rgn_sched_max_insns_priority (void)
2389 return rgn_sched_info
.sched_max_insns_priority
;
2392 /* Determine if PAT sets a TARGET_CLASS_LIKELY_SPILLED_P register. */
2395 sets_likely_spilled (rtx pat
)
2398 note_stores (pat
, sets_likely_spilled_1
, &ret
);
2403 sets_likely_spilled_1 (rtx x
, const_rtx pat
, void *data
)
2405 bool *ret
= (bool *) data
;
2407 if (GET_CODE (pat
) == SET
2409 && HARD_REGISTER_P (x
)
2410 && targetm
.class_likely_spilled_p (REGNO_REG_CLASS (REGNO (x
))))
2414 /* A bitmap to note insns that participate in any dependency. Used in
2415 add_branch_dependences. */
2416 static sbitmap insn_referenced
;
2418 /* Add dependences so that branches are scheduled to run last in their
2421 add_branch_dependences (rtx_insn
*head
, rtx_insn
*tail
)
2423 rtx_insn
*insn
, *last
;
2425 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2426 that can throw exceptions, force them to remain in order at the end of
2427 the block by adding dependencies and giving the last a high priority.
2428 There may be notes present, and prev_head may also be a note.
2430 Branches must obviously remain at the end. Calls should remain at the
2431 end since moving them results in worse register allocation. Uses remain
2432 at the end to ensure proper register allocation.
2434 cc0 setters remain at the end because they can't be moved away from
2437 Predecessors of SCHED_GROUP_P instructions at the end remain at the end.
2439 COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
2441 Insns setting TARGET_CLASS_LIKELY_SPILLED_P registers (usually return
2442 values) are not moved before reload because we can wind up with register
2443 allocation failures. */
2445 while (tail
!= head
&& DEBUG_INSN_P (tail
))
2446 tail
= PREV_INSN (tail
);
2450 while (CALL_P (insn
)
2451 || JUMP_P (insn
) || JUMP_TABLE_DATA_P (insn
)
2452 || (NONJUMP_INSN_P (insn
)
2453 && (GET_CODE (PATTERN (insn
)) == USE
2454 || GET_CODE (PATTERN (insn
)) == CLOBBER
2455 || can_throw_internal (insn
)
2456 || (HAVE_cc0
&& sets_cc0_p (PATTERN (insn
)))
2457 || (!reload_completed
2458 && sets_likely_spilled (PATTERN (insn
)))))
2460 || (last
!= 0 && SCHED_GROUP_P (last
)))
2465 && sd_find_dep_between (insn
, last
, false) == NULL
)
2467 if (! sched_insns_conditions_mutex_p (last
, insn
))
2468 add_dependence (last
, insn
, REG_DEP_ANTI
);
2469 bitmap_set_bit (insn_referenced
, INSN_LUID (insn
));
2472 CANT_MOVE (insn
) = 1;
2477 /* Don't overrun the bounds of the basic block. */
2482 insn
= PREV_INSN (insn
);
2483 while (insn
!= head
&& DEBUG_INSN_P (insn
));
2486 /* Make sure these insns are scheduled last in their block. */
2489 while (insn
!= head
)
2491 insn
= prev_nonnote_insn (insn
);
2493 if (bitmap_bit_p (insn_referenced
, INSN_LUID (insn
))
2494 || DEBUG_INSN_P (insn
))
2497 if (! sched_insns_conditions_mutex_p (last
, insn
))
2498 add_dependence (last
, insn
, REG_DEP_ANTI
);
2501 if (!targetm
.have_conditional_execution ())
2504 /* Finally, if the block ends in a jump, and we are doing intra-block
2505 scheduling, make sure that the branch depends on any COND_EXEC insns
2506 inside the block to avoid moving the COND_EXECs past the branch insn.
2508 We only have to do this after reload, because (1) before reload there
2509 are no COND_EXEC insns, and (2) the region scheduler is an intra-block
2510 scheduler after reload.
2512 FIXME: We could in some cases move COND_EXEC insns past the branch if
2513 this scheduler would be a little smarter. Consider this code:
2521 On a target with a one cycle stall on a memory access the optimal
2530 We don't want to put the 'X += 12' before the branch because it just
2531 wastes a cycle of execution time when the branch is taken.
2533 Note that in the example "!C" will always be true. That is another
2534 possible improvement for handling COND_EXECs in this scheduler: it
2535 could remove always-true predicates. */
2537 if (!reload_completed
|| ! (JUMP_P (tail
) || JUMP_TABLE_DATA_P (tail
)))
2541 while (insn
!= head
)
2543 insn
= PREV_INSN (insn
);
2545 /* Note that we want to add this dependency even when
2546 sched_insns_conditions_mutex_p returns true. The whole point
2547 is that we _want_ this dependency, even if these insns really
2549 if (INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == COND_EXEC
)
2550 add_dependence (tail
, insn
, REG_DEP_ANTI
);
2554 /* Data structures for the computation of data dependences in a regions. We
2555 keep one `deps' structure for every basic block. Before analyzing the
2556 data dependences for a bb, its variables are initialized as a function of
2557 the variables of its predecessors. When the analysis for a bb completes,
2558 we save the contents to the corresponding bb_deps[bb] variable. */
2560 static struct deps_desc
*bb_deps
;
2563 concat_insn_mem_list (rtx_insn_list
*copy_insns
,
2564 rtx_expr_list
*copy_mems
,
2565 rtx_insn_list
**old_insns_p
,
2566 rtx_expr_list
**old_mems_p
)
2568 rtx_insn_list
*new_insns
= *old_insns_p
;
2569 rtx_expr_list
*new_mems
= *old_mems_p
;
2573 new_insns
= alloc_INSN_LIST (copy_insns
->insn (), new_insns
);
2574 new_mems
= alloc_EXPR_LIST (VOIDmode
, copy_mems
->element (), new_mems
);
2575 copy_insns
= copy_insns
->next ();
2576 copy_mems
= copy_mems
->next ();
2579 *old_insns_p
= new_insns
;
2580 *old_mems_p
= new_mems
;
2583 /* Join PRED_DEPS to the SUCC_DEPS. */
2585 deps_join (struct deps_desc
*succ_deps
, struct deps_desc
*pred_deps
)
2588 reg_set_iterator rsi
;
2590 /* The reg_last lists are inherited by successor. */
2591 EXECUTE_IF_SET_IN_REG_SET (&pred_deps
->reg_last_in_use
, 0, reg
, rsi
)
2593 struct deps_reg
*pred_rl
= &pred_deps
->reg_last
[reg
];
2594 struct deps_reg
*succ_rl
= &succ_deps
->reg_last
[reg
];
2596 succ_rl
->uses
= concat_INSN_LIST (pred_rl
->uses
, succ_rl
->uses
);
2597 succ_rl
->sets
= concat_INSN_LIST (pred_rl
->sets
, succ_rl
->sets
);
2598 succ_rl
->implicit_sets
2599 = concat_INSN_LIST (pred_rl
->implicit_sets
, succ_rl
->implicit_sets
);
2600 succ_rl
->clobbers
= concat_INSN_LIST (pred_rl
->clobbers
,
2602 succ_rl
->uses_length
+= pred_rl
->uses_length
;
2603 succ_rl
->clobbers_length
+= pred_rl
->clobbers_length
;
2605 IOR_REG_SET (&succ_deps
->reg_last_in_use
, &pred_deps
->reg_last_in_use
);
2607 /* Mem read/write lists are inherited by successor. */
2608 concat_insn_mem_list (pred_deps
->pending_read_insns
,
2609 pred_deps
->pending_read_mems
,
2610 &succ_deps
->pending_read_insns
,
2611 &succ_deps
->pending_read_mems
);
2612 concat_insn_mem_list (pred_deps
->pending_write_insns
,
2613 pred_deps
->pending_write_mems
,
2614 &succ_deps
->pending_write_insns
,
2615 &succ_deps
->pending_write_mems
);
2617 succ_deps
->pending_jump_insns
2618 = concat_INSN_LIST (pred_deps
->pending_jump_insns
,
2619 succ_deps
->pending_jump_insns
);
2620 succ_deps
->last_pending_memory_flush
2621 = concat_INSN_LIST (pred_deps
->last_pending_memory_flush
,
2622 succ_deps
->last_pending_memory_flush
);
2624 succ_deps
->pending_read_list_length
+= pred_deps
->pending_read_list_length
;
2625 succ_deps
->pending_write_list_length
+= pred_deps
->pending_write_list_length
;
2626 succ_deps
->pending_flush_length
+= pred_deps
->pending_flush_length
;
2628 /* last_function_call is inherited by successor. */
2629 succ_deps
->last_function_call
2630 = concat_INSN_LIST (pred_deps
->last_function_call
,
2631 succ_deps
->last_function_call
);
2633 /* last_function_call_may_noreturn is inherited by successor. */
2634 succ_deps
->last_function_call_may_noreturn
2635 = concat_INSN_LIST (pred_deps
->last_function_call_may_noreturn
,
2636 succ_deps
->last_function_call_may_noreturn
);
2638 /* sched_before_next_call is inherited by successor. */
2639 succ_deps
->sched_before_next_call
2640 = concat_INSN_LIST (pred_deps
->sched_before_next_call
,
2641 succ_deps
->sched_before_next_call
);
2644 /* After computing the dependencies for block BB, propagate the dependencies
2645 found in TMP_DEPS to the successors of the block. */
2647 propagate_deps (int bb
, struct deps_desc
*pred_deps
)
2649 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (bb
));
2653 /* bb's structures are inherited by its successors. */
2654 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2656 /* Only bbs "below" bb, in the same region, are interesting. */
2657 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2658 || CONTAINING_RGN (block
->index
) != CONTAINING_RGN (e
->dest
->index
)
2659 || BLOCK_TO_BB (e
->dest
->index
) <= bb
)
2662 deps_join (bb_deps
+ BLOCK_TO_BB (e
->dest
->index
), pred_deps
);
2665 /* These lists should point to the right place, for correct
2667 bb_deps
[bb
].pending_read_insns
= pred_deps
->pending_read_insns
;
2668 bb_deps
[bb
].pending_read_mems
= pred_deps
->pending_read_mems
;
2669 bb_deps
[bb
].pending_write_insns
= pred_deps
->pending_write_insns
;
2670 bb_deps
[bb
].pending_write_mems
= pred_deps
->pending_write_mems
;
2671 bb_deps
[bb
].pending_jump_insns
= pred_deps
->pending_jump_insns
;
2673 /* Can't allow these to be freed twice. */
2674 pred_deps
->pending_read_insns
= 0;
2675 pred_deps
->pending_read_mems
= 0;
2676 pred_deps
->pending_write_insns
= 0;
2677 pred_deps
->pending_write_mems
= 0;
2678 pred_deps
->pending_jump_insns
= 0;
2681 /* Compute dependences inside bb. In a multiple blocks region:
2682 (1) a bb is analyzed after its predecessors, and (2) the lists in
2683 effect at the end of bb (after analyzing for bb) are inherited by
2686 Specifically for reg-reg data dependences, the block insns are
2687 scanned by sched_analyze () top-to-bottom. Three lists are
2688 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2689 reg_last[].implicit_sets for implicit hard register DEFs, and
2690 reg_last[].uses for register USEs.
2692 When analysis is completed for bb, we update for its successors:
2693 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2694 ; - IMPLICIT_DEFS[succ] = Union (IMPLICIT_DEFS [succ], IMPLICIT_DEFS [bb])
2695 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2697 The mechanism for computing mem-mem data dependence is very
2698 similar, and the result is interblock dependences in the region. */
2701 compute_block_dependences (int bb
)
2703 rtx_insn
*head
, *tail
;
2704 struct deps_desc tmp_deps
;
2706 tmp_deps
= bb_deps
[bb
];
2708 /* Do the analysis for this block. */
2709 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2710 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2712 sched_analyze (&tmp_deps
, head
, tail
);
2714 /* Selective scheduling handles control dependencies by itself. */
2715 if (!sel_sched_p ())
2716 add_branch_dependences (head
, tail
);
2718 if (current_nr_blocks
> 1)
2719 propagate_deps (bb
, &tmp_deps
);
2721 /* Free up the INSN_LISTs. */
2722 free_deps (&tmp_deps
);
2724 if (targetm
.sched
.dependencies_evaluation_hook
)
2725 targetm
.sched
.dependencies_evaluation_hook (head
, tail
);
2728 /* Free dependencies of instructions inside BB. */
2730 free_block_dependencies (int bb
)
2735 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2737 if (no_real_insns_p (head
, tail
))
2740 sched_free_deps (head
, tail
, true);
2743 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2744 them to the unused_*_list variables, so that they can be reused. */
2747 free_pending_lists (void)
2751 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2753 free_INSN_LIST_list (&bb_deps
[bb
].pending_read_insns
);
2754 free_INSN_LIST_list (&bb_deps
[bb
].pending_write_insns
);
2755 free_EXPR_LIST_list (&bb_deps
[bb
].pending_read_mems
);
2756 free_EXPR_LIST_list (&bb_deps
[bb
].pending_write_mems
);
2757 free_INSN_LIST_list (&bb_deps
[bb
].pending_jump_insns
);
2761 /* Print dependences for debugging starting from FROM_BB.
2762 Callable from debugger. */
2763 /* Print dependences for debugging starting from FROM_BB.
2764 Callable from debugger. */
2766 debug_rgn_dependencies (int from_bb
)
2770 fprintf (sched_dump
,
2771 ";; --------------- forward dependences: ------------ \n");
2773 for (bb
= from_bb
; bb
< current_nr_blocks
; bb
++)
2775 rtx_insn
*head
, *tail
;
2777 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2778 fprintf (sched_dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
2779 BB_TO_BLOCK (bb
), bb
);
2781 debug_dependencies (head
, tail
);
2785 /* Print dependencies information for instructions between HEAD and TAIL.
2786 ??? This function would probably fit best in haifa-sched.c. */
2787 void debug_dependencies (rtx_insn
*head
, rtx_insn
*tail
)
2790 rtx_insn
*next_tail
= NEXT_INSN (tail
);
2792 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2793 "insn", "code", "bb", "dep", "prio", "cost",
2795 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2796 "----", "----", "--", "---", "----", "----",
2799 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2801 if (! INSN_P (insn
))
2804 fprintf (sched_dump
, ";; %6d ", INSN_UID (insn
));
2807 n
= NOTE_KIND (insn
);
2808 fprintf (sched_dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
2811 fprintf (sched_dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
2815 fprintf (sched_dump
,
2816 ";; %s%5d%6d%6d%6d%6d%6d ",
2817 (SCHED_GROUP_P (insn
) ? "+" : " "),
2821 sched_emulate_haifa_p
? -1 : sd_lists_size (insn
, SD_LIST_BACK
),
2822 (sel_sched_p () ? (sched_emulate_haifa_p
? -1
2823 : INSN_PRIORITY (insn
))
2824 : INSN_PRIORITY (insn
)),
2825 (sel_sched_p () ? (sched_emulate_haifa_p
? -1
2827 : insn_cost (insn
)));
2829 if (recog_memoized (insn
) < 0)
2830 fprintf (sched_dump
, "nothing");
2832 print_reservation (sched_dump
, insn
);
2834 fprintf (sched_dump
, "\t: ");
2836 sd_iterator_def sd_it
;
2839 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
2840 fprintf (sched_dump
, "%d%s%s ", INSN_UID (DEP_CON (dep
)),
2841 DEP_NONREG (dep
) ? "n" : "",
2842 DEP_MULTIPLE (dep
) ? "m" : "");
2844 fprintf (sched_dump
, "\n");
2847 fprintf (sched_dump
, "\n");
2850 /* Dump dependency graph for the current region to a file using dot syntax. */
2853 dump_rgn_dependencies_dot (FILE *file
)
2855 rtx_insn
*head
, *tail
, *con
, *pro
;
2856 sd_iterator_def sd_it
;
2861 pp
.buffer
->stream
= file
;
2862 pp_printf (&pp
, "digraph SchedDG {\n");
2864 for (bb
= 0; bb
< current_nr_blocks
; ++bb
)
2866 /* Begin subgraph (basic block). */
2867 pp_printf (&pp
, "subgraph cluster_block_%d {\n", bb
);
2868 pp_printf (&pp
, "\t" "color=blue;" "\n");
2869 pp_printf (&pp
, "\t" "style=bold;" "\n");
2870 pp_printf (&pp
, "\t" "label=\"BB #%d\";\n", BB_TO_BLOCK (bb
));
2872 /* Setup head and tail (no support for EBBs). */
2873 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2874 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2875 tail
= NEXT_INSN (tail
);
2877 /* Dump all insns. */
2878 for (con
= head
; con
!= tail
; con
= NEXT_INSN (con
))
2883 /* Pretty print the insn. */
2884 pp_printf (&pp
, "\t%d [label=\"{", INSN_UID (con
));
2885 pp_write_text_to_stream (&pp
);
2886 print_insn (&pp
, con
, /*verbose=*/false);
2887 pp_write_text_as_dot_label_to_stream (&pp
, /*for_record=*/true);
2888 pp_write_text_to_stream (&pp
);
2890 /* Dump instruction attributes. */
2891 pp_printf (&pp
, "|{ uid:%d | luid:%d | prio:%d }}\",shape=record]\n",
2892 INSN_UID (con
), INSN_LUID (con
), INSN_PRIORITY (con
));
2894 /* Dump all deps. */
2895 FOR_EACH_DEP (con
, SD_LIST_BACK
, sd_it
, dep
)
2899 pro
= DEP_PRO (dep
);
2901 switch (DEP_TYPE (dep
))
2907 case REG_DEP_OUTPUT
:
2911 case REG_DEP_CONTROL
:
2918 pp_printf (&pp
, "\t%d -> %d [color=%s",
2919 INSN_UID (pro
), INSN_UID (con
), color
);
2920 if (int cost
= dep_cost (dep
))
2921 pp_printf (&pp
, ",label=%d", cost
);
2922 pp_printf (&pp
, ",weight=%d", weight
);
2923 pp_printf (&pp
, "];\n");
2926 pp_printf (&pp
, "}\n");
2929 pp_printf (&pp
, "}\n");
2933 /* Dump dependency graph for the current region to a file using dot syntax. */
2936 dump_rgn_dependencies_dot (const char *fname
)
2940 fp
= fopen (fname
, "w");
2947 dump_rgn_dependencies_dot (fp
);
2952 /* Returns true if all the basic blocks of the current region have
2953 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
2955 sched_is_disabled_for_current_region_p (void)
2959 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2960 if (!(BASIC_BLOCK_FOR_FN (cfun
,
2961 BB_TO_BLOCK (bb
))->flags
& BB_DISABLE_SCHEDULE
))
2967 /* Free all region dependencies saved in INSN_BACK_DEPS and
2968 INSN_RESOLVED_BACK_DEPS. The Haifa scheduler does this on the fly
2969 when scheduling, so this function is supposed to be called from
2970 the selective scheduling only. */
2972 free_rgn_deps (void)
2976 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2978 rtx_insn
*head
, *tail
;
2980 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2981 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2983 sched_free_deps (head
, tail
, false);
2987 static int rgn_n_insns
;
2989 /* Compute insn priority for a current region. */
2991 compute_priorities (void)
2995 current_sched_info
->sched_max_insns_priority
= 0;
2996 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2998 rtx_insn
*head
, *tail
;
3000 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
3001 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
3003 if (no_real_insns_p (head
, tail
))
3006 rgn_n_insns
+= set_priorities (head
, tail
);
3008 current_sched_info
->sched_max_insns_priority
++;
3011 /* (Re-)initialize the arrays of DFA states at the end of each basic block.
3013 SAVED_LAST_BASIC_BLOCK is the previous length of the arrays. It must be
3014 zero for the first call to this function, to allocate the arrays for the
3017 This function is called once during initialization of the scheduler, and
3018 called again to resize the arrays if new basic blocks have been created,
3019 for example for speculation recovery code. */
3022 realloc_bb_state_array (int saved_last_basic_block
)
3024 char *old_bb_state_array
= bb_state_array
;
3025 size_t lbb
= (size_t) last_basic_block_for_fn (cfun
);
3026 size_t slbb
= (size_t) saved_last_basic_block
;
3028 /* Nothing to do if nothing changed since the last time this was called. */
3029 if (saved_last_basic_block
== last_basic_block_for_fn (cfun
))
3032 /* The selective scheduler doesn't use the state arrays. */
3035 gcc_assert (bb_state_array
== NULL
&& bb_state
== NULL
);
3039 gcc_checking_assert (saved_last_basic_block
== 0
3040 || (bb_state_array
!= NULL
&& bb_state
!= NULL
));
3042 bb_state_array
= XRESIZEVEC (char, bb_state_array
, lbb
* dfa_state_size
);
3043 bb_state
= XRESIZEVEC (state_t
, bb_state
, lbb
);
3045 /* If BB_STATE_ARRAY has moved, fixup all the state pointers array.
3046 Otherwise only fixup the newly allocated ones. For the state
3047 array itself, only initialize the new entries. */
3048 bool bb_state_array_moved
= (bb_state_array
!= old_bb_state_array
);
3049 for (size_t i
= bb_state_array_moved
? 0 : slbb
; i
< lbb
; i
++)
3050 bb_state
[i
] = (state_t
) (bb_state_array
+ i
* dfa_state_size
);
3051 for (size_t i
= slbb
; i
< lbb
; i
++)
3052 state_reset (bb_state
[i
]);
3055 /* Free the arrays of DFA states at the end of each basic block. */
3058 free_bb_state_array (void)
3060 free (bb_state_array
);
3062 bb_state_array
= NULL
;
3066 /* Schedule a region. A region is either an inner loop, a loop-free
3067 subroutine, or a single basic block. Each bb in the region is
3068 scheduled after its flow predecessors. */
3071 schedule_region (int rgn
)
3074 int sched_rgn_n_insns
= 0;
3078 /* Do not support register pressure sensitive scheduling for the new regions
3079 as we don't update the liveness info for them. */
3080 if (sched_pressure
!= SCHED_PRESSURE_NONE
3081 && rgn
>= nr_regions_initial
)
3083 free_global_sched_pressure_data ();
3084 sched_pressure
= SCHED_PRESSURE_NONE
;
3087 rgn_setup_region (rgn
);
3089 /* Don't schedule region that is marked by
3090 NOTE_DISABLE_SCHED_OF_BLOCK. */
3091 if (sched_is_disabled_for_current_region_p ())
3094 sched_rgn_compute_dependencies (rgn
);
3096 sched_rgn_local_init (rgn
);
3098 /* Set priorities. */
3099 compute_priorities ();
3101 sched_extend_ready_list (rgn_n_insns
);
3103 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
3105 sched_init_region_reg_pressure_info ();
3106 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3108 basic_block first_bb
, last_bb
;
3109 rtx_insn
*head
, *tail
;
3111 first_bb
= EBB_FIRST_BB (bb
);
3112 last_bb
= EBB_LAST_BB (bb
);
3114 get_ebb_head_tail (first_bb
, last_bb
, &head
, &tail
);
3116 if (no_real_insns_p (head
, tail
))
3118 gcc_assert (first_bb
== last_bb
);
3121 sched_setup_bb_reg_pressure_info (first_bb
, PREV_INSN (head
));
3125 /* Now we can schedule all blocks. */
3126 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3128 basic_block first_bb
, last_bb
, curr_bb
;
3129 rtx_insn
*head
, *tail
;
3131 first_bb
= EBB_FIRST_BB (bb
);
3132 last_bb
= EBB_LAST_BB (bb
);
3134 get_ebb_head_tail (first_bb
, last_bb
, &head
, &tail
);
3136 if (no_real_insns_p (head
, tail
))
3138 gcc_assert (first_bb
== last_bb
);
3142 current_sched_info
->prev_head
= PREV_INSN (head
);
3143 current_sched_info
->next_tail
= NEXT_INSN (tail
);
3145 remove_notes (head
, tail
);
3147 unlink_bb_notes (first_bb
, last_bb
);
3151 gcc_assert (flag_schedule_interblock
|| current_nr_blocks
== 1);
3152 current_sched_info
->queue_must_finish_empty
= current_nr_blocks
== 1;
3155 if (dbg_cnt (sched_block
))
3158 int saved_last_basic_block
= last_basic_block_for_fn (cfun
);
3160 schedule_block (&curr_bb
, bb_state
[first_bb
->index
]);
3161 gcc_assert (EBB_FIRST_BB (bb
) == first_bb
);
3162 sched_rgn_n_insns
+= sched_n_insns
;
3163 realloc_bb_state_array (saved_last_basic_block
);
3164 f
= find_fallthru_edge (last_bb
->succs
);
3165 if (f
&& f
->probability
* 100 / REG_BR_PROB_BASE
>=
3166 PARAM_VALUE (PARAM_SCHED_STATE_EDGE_PROB_CUTOFF
))
3168 memcpy (bb_state
[f
->dest
->index
], curr_state
,
3170 if (sched_verbose
>= 5)
3171 fprintf (sched_dump
, "saving state for edge %d->%d\n",
3172 f
->src
->index
, f
->dest
->index
);
3177 sched_rgn_n_insns
+= rgn_n_insns
;
3181 if (current_nr_blocks
> 1)
3185 /* Sanity check: verify that all region insns were scheduled. */
3186 gcc_assert (sched_rgn_n_insns
== rgn_n_insns
);
3188 sched_finish_ready_list ();
3190 /* Done with this region. */
3191 sched_rgn_local_finish ();
3193 /* Free dependencies. */
3194 for (bb
= 0; bb
< current_nr_blocks
; ++bb
)
3195 free_block_dependencies (bb
);
3197 gcc_assert (haifa_recovery_bb_ever_added_p
3198 || deps_pools_are_empty_p ());
3201 /* Initialize data structures for region scheduling. */
3204 sched_rgn_init (bool single_blocks_p
)
3206 min_spec_prob
= ((PARAM_VALUE (PARAM_MIN_SPEC_PROB
) * REG_BR_PROB_BASE
)
3214 CONTAINING_RGN (ENTRY_BLOCK
) = -1;
3215 CONTAINING_RGN (EXIT_BLOCK
) = -1;
3217 realloc_bb_state_array (0);
3219 /* Compute regions for scheduling. */
3221 || n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
+ 1
3222 || !flag_schedule_interblock
3223 || is_cfg_nonregular ())
3225 find_single_block_region (sel_sched_p ());
3229 /* Compute the dominators and post dominators. */
3230 if (!sel_sched_p ())
3231 calculate_dominance_info (CDI_DOMINATORS
);
3236 if (sched_verbose
>= 3)
3239 /* For now. This will move as more and more of haifa is converted
3240 to using the cfg code. */
3241 if (!sel_sched_p ())
3242 free_dominance_info (CDI_DOMINATORS
);
3245 gcc_assert (0 < nr_regions
&& nr_regions
<= n_basic_blocks_for_fn (cfun
));
3247 RGN_BLOCKS (nr_regions
) = (RGN_BLOCKS (nr_regions
- 1) +
3248 RGN_NR_BLOCKS (nr_regions
- 1));
3249 nr_regions_initial
= nr_regions
;
3252 /* Free data structures for region scheduling. */
3254 sched_rgn_finish (void)
3256 free_bb_state_array ();
3258 /* Reposition the prologue and epilogue notes in case we moved the
3259 prologue/epilogue insns. */
3260 if (reload_completed
)
3261 reposition_prologue_and_epilogue_notes ();
3265 if (reload_completed
== 0
3266 && flag_schedule_interblock
)
3268 fprintf (sched_dump
,
3269 "\n;; Procedure interblock/speculative motions == %d/%d \n",
3273 gcc_assert (nr_inter
<= 0);
3274 fprintf (sched_dump
, "\n\n");
3282 free (rgn_bb_table
);
3283 rgn_bb_table
= NULL
;
3288 free (containing_rgn
);
3289 containing_rgn
= NULL
;
3295 /* Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
3296 point to the region RGN. */
3298 rgn_setup_region (int rgn
)
3302 /* Set variables for the current region. */
3303 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
3304 current_blocks
= RGN_BLOCKS (rgn
);
3306 /* EBB_HEAD is a region-scope structure. But we realloc it for
3307 each region to save time/memory/something else.
3308 See comments in add_block1, for what reasons we allocate +1 element. */
3309 ebb_head
= XRESIZEVEC (int, ebb_head
, current_nr_blocks
+ 1);
3310 for (bb
= 0; bb
<= current_nr_blocks
; bb
++)
3311 ebb_head
[bb
] = current_blocks
+ bb
;
3314 /* Compute instruction dependencies in region RGN. */
3316 sched_rgn_compute_dependencies (int rgn
)
3318 if (!RGN_DONT_CALC_DEPS (rgn
))
3323 sched_emulate_haifa_p
= 1;
3325 init_deps_global ();
3327 /* Initializations for region data dependence analysis. */
3328 bb_deps
= XNEWVEC (struct deps_desc
, current_nr_blocks
);
3329 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3330 init_deps (bb_deps
+ bb
, false);
3332 /* Initialize bitmap used in add_branch_dependences. */
3333 insn_referenced
= sbitmap_alloc (sched_max_luid
);
3334 bitmap_clear (insn_referenced
);
3336 /* Compute backward dependencies. */
3337 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3338 compute_block_dependences (bb
);
3340 sbitmap_free (insn_referenced
);
3341 free_pending_lists ();
3342 finish_deps_global ();
3345 /* We don't want to recalculate this twice. */
3346 RGN_DONT_CALC_DEPS (rgn
) = 1;
3349 sched_emulate_haifa_p
= 0;
3352 /* (This is a recovery block. It is always a single block region.)
3353 OR (We use selective scheduling.) */
3354 gcc_assert (current_nr_blocks
== 1 || sel_sched_p ());
3357 /* Init region data structures. Returns true if this region should
3358 not be scheduled. */
3360 sched_rgn_local_init (int rgn
)
3364 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
3365 if (current_nr_blocks
> 1)
3371 prob
= XNEWVEC (int, current_nr_blocks
);
3373 dom
= sbitmap_vector_alloc (current_nr_blocks
, current_nr_blocks
);
3374 bitmap_vector_clear (dom
, current_nr_blocks
);
3376 /* Use ->aux to implement EDGE_TO_BIT mapping. */
3378 FOR_EACH_BB_FN (block
, cfun
)
3380 if (CONTAINING_RGN (block
->index
) != rgn
)
3382 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3383 SET_EDGE_TO_BIT (e
, rgn_nr_edges
++);
3386 rgn_edges
= XNEWVEC (edge
, rgn_nr_edges
);
3388 FOR_EACH_BB_FN (block
, cfun
)
3390 if (CONTAINING_RGN (block
->index
) != rgn
)
3392 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3393 rgn_edges
[rgn_nr_edges
++] = e
;
3397 pot_split
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
3398 bitmap_vector_clear (pot_split
, current_nr_blocks
);
3399 ancestor_edges
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
3400 bitmap_vector_clear (ancestor_edges
, current_nr_blocks
);
3402 /* Compute probabilities, dominators, split_edges. */
3403 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3404 compute_dom_prob_ps (bb
);
3406 /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
3407 /* We don't need them anymore. But we want to avoid duplication of
3408 aux fields in the newly created edges. */
3409 FOR_EACH_BB_FN (block
, cfun
)
3411 if (CONTAINING_RGN (block
->index
) != rgn
)
3413 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3419 /* Free data computed for the finished region. */
3421 sched_rgn_local_free (void)
3424 sbitmap_vector_free (dom
);
3425 sbitmap_vector_free (pot_split
);
3426 sbitmap_vector_free (ancestor_edges
);
3430 /* Free data computed for the finished region. */
3432 sched_rgn_local_finish (void)
3434 if (current_nr_blocks
> 1 && !sel_sched_p ())
3436 sched_rgn_local_free ();
3440 /* Setup scheduler infos. */
3442 rgn_setup_common_sched_info (void)
3444 memcpy (&rgn_common_sched_info
, &haifa_common_sched_info
,
3445 sizeof (rgn_common_sched_info
));
3447 rgn_common_sched_info
.fix_recovery_cfg
= rgn_fix_recovery_cfg
;
3448 rgn_common_sched_info
.add_block
= rgn_add_block
;
3449 rgn_common_sched_info
.estimate_number_of_insns
3450 = rgn_estimate_number_of_insns
;
3451 rgn_common_sched_info
.sched_pass_id
= SCHED_RGN_PASS
;
3453 common_sched_info
= &rgn_common_sched_info
;
3456 /* Setup all *_sched_info structures (for the Haifa frontend
3457 and for the dependence analysis) in the interblock scheduler. */
3459 rgn_setup_sched_infos (void)
3461 if (!sel_sched_p ())
3462 memcpy (&rgn_sched_deps_info
, &rgn_const_sched_deps_info
,
3463 sizeof (rgn_sched_deps_info
));
3465 memcpy (&rgn_sched_deps_info
, &rgn_const_sel_sched_deps_info
,
3466 sizeof (rgn_sched_deps_info
));
3468 sched_deps_info
= &rgn_sched_deps_info
;
3470 memcpy (&rgn_sched_info
, &rgn_const_sched_info
, sizeof (rgn_sched_info
));
3471 current_sched_info
= &rgn_sched_info
;
3474 /* The one entry point in this file. */
3476 schedule_insns (void)
3480 /* Taking care of this degenerate case makes the rest of
3481 this code simpler. */
3482 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
3485 rgn_setup_common_sched_info ();
3486 rgn_setup_sched_infos ();
3488 haifa_sched_init ();
3489 sched_rgn_init (reload_completed
);
3491 bitmap_initialize (¬_in_df
, 0);
3492 bitmap_clear (¬_in_df
);
3494 /* Schedule every region in the subroutine. */
3495 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
3496 if (dbg_cnt (sched_region
))
3497 schedule_region (rgn
);
3500 sched_rgn_finish ();
3501 bitmap_clear (¬_in_df
);
3503 haifa_sched_finish ();
3506 /* INSN has been added to/removed from current region. */
3508 rgn_add_remove_insn (rtx_insn
*insn
, int remove_p
)
3515 if (INSN_BB (insn
) == target_bb
)
3524 /* Extend internal data structures. */
3526 extend_regions (void)
3528 rgn_table
= XRESIZEVEC (region
, rgn_table
, n_basic_blocks_for_fn (cfun
));
3529 rgn_bb_table
= XRESIZEVEC (int, rgn_bb_table
,
3530 n_basic_blocks_for_fn (cfun
));
3531 block_to_bb
= XRESIZEVEC (int, block_to_bb
,
3532 last_basic_block_for_fn (cfun
));
3533 containing_rgn
= XRESIZEVEC (int, containing_rgn
,
3534 last_basic_block_for_fn (cfun
));
3538 rgn_make_new_region_out_of_new_block (basic_block bb
)
3542 i
= RGN_BLOCKS (nr_regions
);
3543 /* I - first free position in rgn_bb_table. */
3545 rgn_bb_table
[i
] = bb
->index
;
3546 RGN_NR_BLOCKS (nr_regions
) = 1;
3547 RGN_HAS_REAL_EBB (nr_regions
) = 0;
3548 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
3549 CONTAINING_RGN (bb
->index
) = nr_regions
;
3550 BLOCK_TO_BB (bb
->index
) = 0;
3554 RGN_BLOCKS (nr_regions
) = i
+ 1;
3557 /* BB was added to ebb after AFTER. */
3559 rgn_add_block (basic_block bb
, basic_block after
)
3562 bitmap_set_bit (¬_in_df
, bb
->index
);
3564 if (after
== 0 || after
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3566 rgn_make_new_region_out_of_new_block (bb
);
3567 RGN_DONT_CALC_DEPS (nr_regions
- 1) = (after
3568 == EXIT_BLOCK_PTR_FOR_FN (cfun
));
3574 /* We need to fix rgn_table, block_to_bb, containing_rgn
3577 BLOCK_TO_BB (bb
->index
) = BLOCK_TO_BB (after
->index
);
3579 /* We extend ebb_head to one more position to
3580 easily find the last position of the last ebb in
3581 the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
3582 is _always_ valid for access. */
3584 i
= BLOCK_TO_BB (after
->index
) + 1;
3585 pos
= ebb_head
[i
] - 1;
3586 /* Now POS is the index of the last block in the region. */
3588 /* Find index of basic block AFTER. */
3589 for (; rgn_bb_table
[pos
] != after
->index
; pos
--)
3593 gcc_assert (pos
> ebb_head
[i
- 1]);
3595 /* i - ebb right after "AFTER". */
3596 /* ebb_head[i] - VALID. */
3598 /* Source position: ebb_head[i]
3599 Destination position: ebb_head[i] + 1
3601 RGN_BLOCKS (nr_regions) - 1
3602 Number of elements to copy: (last_position) - (source_position) + 1
3605 memmove (rgn_bb_table
+ pos
+ 1,
3607 ((RGN_BLOCKS (nr_regions
) - 1) - (pos
) + 1)
3608 * sizeof (*rgn_bb_table
));
3610 rgn_bb_table
[pos
] = bb
->index
;
3612 for (; i
<= current_nr_blocks
; i
++)
3615 i
= CONTAINING_RGN (after
->index
);
3616 CONTAINING_RGN (bb
->index
) = i
;
3618 RGN_HAS_REAL_EBB (i
) = 1;
3620 for (++i
; i
<= nr_regions
; i
++)
3625 /* Fix internal data after interblock movement of jump instruction.
3626 For parameter meaning please refer to
3627 sched-int.h: struct sched_info: fix_recovery_cfg. */
3629 rgn_fix_recovery_cfg (int bbi
, int check_bbi
, int check_bb_nexti
)
3631 int old_pos
, new_pos
, i
;
3633 BLOCK_TO_BB (check_bb_nexti
) = BLOCK_TO_BB (bbi
);
3635 for (old_pos
= ebb_head
[BLOCK_TO_BB (check_bbi
) + 1] - 1;
3636 rgn_bb_table
[old_pos
] != check_bb_nexti
;
3639 gcc_assert (old_pos
> ebb_head
[BLOCK_TO_BB (check_bbi
)]);
3641 for (new_pos
= ebb_head
[BLOCK_TO_BB (bbi
) + 1] - 1;
3642 rgn_bb_table
[new_pos
] != bbi
;
3646 gcc_assert (new_pos
> ebb_head
[BLOCK_TO_BB (bbi
)]);
3648 gcc_assert (new_pos
< old_pos
);
3650 memmove (rgn_bb_table
+ new_pos
+ 1,
3651 rgn_bb_table
+ new_pos
,
3652 (old_pos
- new_pos
) * sizeof (*rgn_bb_table
));
3654 rgn_bb_table
[new_pos
] = check_bb_nexti
;
3656 for (i
= BLOCK_TO_BB (bbi
) + 1; i
<= BLOCK_TO_BB (check_bbi
); i
++)
3660 /* Return next block in ebb chain. For parameter meaning please refer to
3661 sched-int.h: struct sched_info: advance_target_bb. */
3663 advance_target_bb (basic_block bb
, rtx_insn
*insn
)
3668 gcc_assert (BLOCK_TO_BB (bb
->index
) == target_bb
3669 && BLOCK_TO_BB (bb
->next_bb
->index
) == target_bb
);
3675 /* Run instruction scheduler. */
3677 rest_of_handle_live_range_shrinkage (void)
3679 #ifdef INSN_SCHEDULING
3682 initialize_live_range_shrinkage ();
3683 saved
= flag_schedule_interblock
;
3684 flag_schedule_interblock
= false;
3686 flag_schedule_interblock
= saved
;
3687 finish_live_range_shrinkage ();
3692 /* Run instruction scheduler. */
3694 rest_of_handle_sched (void)
3696 #ifdef INSN_SCHEDULING
3697 if (flag_selective_scheduling
3698 && ! maybe_skip_selective_scheduling ())
3699 run_selective_scheduling ();
3706 /* Run second scheduling pass after reload. */
3708 rest_of_handle_sched2 (void)
3710 #ifdef INSN_SCHEDULING
3711 if (flag_selective_scheduling2
3712 && ! maybe_skip_selective_scheduling ())
3713 run_selective_scheduling ();
3716 /* Do control and data sched analysis again,
3717 and write some more of the results to dump file. */
3718 if (flag_sched2_use_superblocks
)
3728 rest_of_handle_sched_fusion (void)
3730 #ifdef INSN_SCHEDULING
3731 sched_fusion
= true;
3733 sched_fusion
= false;
3740 const pass_data pass_data_live_range_shrinkage
=
3742 RTL_PASS
, /* type */
3743 "lr_shrinkage", /* name */
3744 OPTGROUP_NONE
, /* optinfo_flags */
3745 TV_LIVE_RANGE_SHRINKAGE
, /* tv_id */
3746 0, /* properties_required */
3747 0, /* properties_provided */
3748 0, /* properties_destroyed */
3749 0, /* todo_flags_start */
3750 TODO_df_finish
, /* todo_flags_finish */
3753 class pass_live_range_shrinkage
: public rtl_opt_pass
3756 pass_live_range_shrinkage(gcc::context
*ctxt
)
3757 : rtl_opt_pass(pass_data_live_range_shrinkage
, ctxt
)
3760 /* opt_pass methods: */
3761 virtual bool gate (function
*)
3763 #ifdef INSN_SCHEDULING
3764 return flag_live_range_shrinkage
;
3770 virtual unsigned int execute (function
*)
3772 return rest_of_handle_live_range_shrinkage ();
3775 }; // class pass_live_range_shrinkage
3780 make_pass_live_range_shrinkage (gcc::context
*ctxt
)
3782 return new pass_live_range_shrinkage (ctxt
);
3787 const pass_data pass_data_sched
=
3789 RTL_PASS
, /* type */
3790 "sched1", /* name */
3791 OPTGROUP_NONE
, /* optinfo_flags */
3792 TV_SCHED
, /* tv_id */
3793 0, /* properties_required */
3794 0, /* properties_provided */
3795 0, /* properties_destroyed */
3796 0, /* todo_flags_start */
3797 TODO_df_finish
, /* todo_flags_finish */
3800 class pass_sched
: public rtl_opt_pass
3803 pass_sched (gcc::context
*ctxt
)
3804 : rtl_opt_pass (pass_data_sched
, ctxt
)
3807 /* opt_pass methods: */
3808 virtual bool gate (function
*);
3809 virtual unsigned int execute (function
*) { return rest_of_handle_sched (); }
3811 }; // class pass_sched
3814 pass_sched::gate (function
*)
3816 #ifdef INSN_SCHEDULING
3817 return optimize
> 0 && flag_schedule_insns
&& dbg_cnt (sched_func
);
3826 make_pass_sched (gcc::context
*ctxt
)
3828 return new pass_sched (ctxt
);
3833 const pass_data pass_data_sched2
=
3835 RTL_PASS
, /* type */
3836 "sched2", /* name */
3837 OPTGROUP_NONE
, /* optinfo_flags */
3838 TV_SCHED2
, /* tv_id */
3839 0, /* properties_required */
3840 0, /* properties_provided */
3841 0, /* properties_destroyed */
3842 0, /* todo_flags_start */
3843 TODO_df_finish
, /* todo_flags_finish */
3846 class pass_sched2
: public rtl_opt_pass
3849 pass_sched2 (gcc::context
*ctxt
)
3850 : rtl_opt_pass (pass_data_sched2
, ctxt
)
3853 /* opt_pass methods: */
3854 virtual bool gate (function
*);
3855 virtual unsigned int execute (function
*)
3857 return rest_of_handle_sched2 ();
3860 }; // class pass_sched2
3863 pass_sched2::gate (function
*)
3865 #ifdef INSN_SCHEDULING
3866 return optimize
> 0 && flag_schedule_insns_after_reload
3867 && !targetm
.delay_sched2
&& dbg_cnt (sched2_func
);
3876 make_pass_sched2 (gcc::context
*ctxt
)
3878 return new pass_sched2 (ctxt
);
3883 const pass_data pass_data_sched_fusion
=
3885 RTL_PASS
, /* type */
3886 "sched_fusion", /* name */
3887 OPTGROUP_NONE
, /* optinfo_flags */
3888 TV_SCHED_FUSION
, /* tv_id */
3889 0, /* properties_required */
3890 0, /* properties_provided */
3891 0, /* properties_destroyed */
3892 0, /* todo_flags_start */
3893 TODO_df_finish
, /* todo_flags_finish */
3896 class pass_sched_fusion
: public rtl_opt_pass
3899 pass_sched_fusion (gcc::context
*ctxt
)
3900 : rtl_opt_pass (pass_data_sched_fusion
, ctxt
)
3903 /* opt_pass methods: */
3904 virtual bool gate (function
*);
3905 virtual unsigned int execute (function
*)
3907 return rest_of_handle_sched_fusion ();
3910 }; // class pass_sched2
3913 pass_sched_fusion::gate (function
*)
3915 #ifdef INSN_SCHEDULING
3916 /* Scheduling fusion relies on peephole2 to do real fusion work,
3917 so only enable it if peephole2 is in effect. */
3918 return (optimize
> 0 && flag_peephole2
3919 && flag_schedule_fusion
&& targetm
.sched
.fusion_priority
!= NULL
);
3928 make_pass_sched_fusion (gcc::context
*ctxt
)
3930 return new pass_sched_fusion (ctxt
);