1 /* Instruction scheduling pass.
2 Copyright (C) 1992-2014 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"
50 #include "diagnostic-core.h"
53 #include "hard-reg-set.h"
57 #include "insn-config.h"
58 #include "insn-attr.h"
62 #include "sched-int.h"
63 #include "sel-sched.h"
65 #include "tree-pass.h"
68 #ifdef INSN_SCHEDULING
70 /* Some accessor macros for h_i_d members only used within this file. */
71 #define FED_BY_SPEC_LOAD(INSN) (HID (INSN)->fed_by_spec_load)
72 #define IS_LOAD_INSN(INSN) (HID (insn)->is_load_insn)
74 /* nr_inter/spec counts interblock/speculative motion for the function. */
75 static int nr_inter
, nr_spec
;
77 static int is_cfg_nonregular (void);
79 /* Number of regions in the procedure. */
82 /* Same as above before adding any new regions. */
83 static int nr_regions_initial
= 0;
85 /* Table of region descriptions. */
86 region
*rgn_table
= NULL
;
88 /* Array of lists of regions' blocks. */
89 int *rgn_bb_table
= NULL
;
91 /* Topological order of blocks in the region (if b2 is reachable from
92 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
93 always referred to by either block or b, while its topological
94 order name (in the region) is referred to by bb. */
95 int *block_to_bb
= NULL
;
97 /* The number of the region containing a block. */
98 int *containing_rgn
= NULL
;
100 /* ebb_head [i] - is index in rgn_bb_table of the head basic block of i'th ebb.
101 Currently we can get a ebb only through splitting of currently
102 scheduling block, therefore, we don't need ebb_head array for every region,
103 hence, its sufficient to hold it for current one only. */
104 int *ebb_head
= NULL
;
106 /* The minimum probability of reaching a source block so that it will be
107 considered for speculative scheduling. */
108 static int min_spec_prob
;
110 static void find_single_block_region (bool);
111 static void find_rgns (void);
112 static bool too_large (int, int *, int *);
114 /* Blocks of the current region being scheduled. */
115 int current_nr_blocks
;
118 /* A speculative motion requires checking live information on the path
119 from 'source' to 'target'. The split blocks are those to be checked.
120 After a speculative motion, live information should be modified in
123 Lists of split and update blocks for each candidate of the current
124 target are in array bblst_table. */
125 static basic_block
*bblst_table
;
126 static int bblst_size
, bblst_last
;
128 /* Arrays that hold the DFA state at the end of a basic block, to re-use
129 as the initial state at the start of successor blocks. The BB_STATE
130 array holds the actual DFA state, and BB_STATE_ARRAY[I] is a pointer
131 into BB_STATE for basic block I. FIXME: This should be a vec. */
132 static char *bb_state_array
= NULL
;
133 static state_t
*bb_state
= NULL
;
135 /* Target info declarations.
137 The block currently being scheduled is referred to as the "target" block,
138 while other blocks in the region from which insns can be moved to the
139 target are called "source" blocks. The candidate structure holds info
140 about such sources: are they valid? Speculative? Etc. */
143 basic_block
*first_member
;
158 static candidate
*candidate_table
;
159 #define IS_VALID(src) (candidate_table[src].is_valid)
160 #define IS_SPECULATIVE(src) (candidate_table[src].is_speculative)
161 #define IS_SPECULATIVE_INSN(INSN) \
162 (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
163 #define SRC_PROB(src) ( candidate_table[src].src_prob )
165 /* The bb being currently scheduled. */
176 static edge
*edgelst_table
;
177 static int edgelst_last
;
179 static void extract_edgelst (sbitmap
, edgelst
*);
181 /* Target info functions. */
182 static void split_edges (int, int, edgelst
*);
183 static void compute_trg_info (int);
184 void debug_candidate (int);
185 void debug_candidates (int);
187 /* Dominators array: dom[i] contains the sbitmap of dominators of
188 bb i in the region. */
191 /* bb 0 is the only region entry. */
192 #define IS_RGN_ENTRY(bb) (!bb)
194 /* Is bb_src dominated by bb_trg. */
195 #define IS_DOMINATED(bb_src, bb_trg) \
196 ( bitmap_bit_p (dom[bb_src], bb_trg) )
198 /* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
199 the probability of bb i relative to the region entry. */
202 /* Bit-set of edges, where bit i stands for edge i. */
203 typedef sbitmap edgeset
;
205 /* Number of edges in the region. */
206 static int rgn_nr_edges
;
208 /* Array of size rgn_nr_edges. */
209 static edge
*rgn_edges
;
211 /* Mapping from each edge in the graph to its number in the rgn. */
212 #define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
213 #define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
215 /* The split edges of a source bb is different for each target
216 bb. In order to compute this efficiently, the 'potential-split edges'
217 are computed for each bb prior to scheduling a region. This is actually
218 the split edges of each bb relative to the region entry.
220 pot_split[bb] is the set of potential split edges of bb. */
221 static edgeset
*pot_split
;
223 /* For every bb, a set of its ancestor edges. */
224 static edgeset
*ancestor_edges
;
226 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
228 /* Speculative scheduling functions. */
229 static int check_live_1 (int, rtx
);
230 static void update_live_1 (int, rtx
);
231 static int is_pfree (rtx
, int, int);
232 static int find_conditional_protection (rtx
, int);
233 static int is_conditionally_protected (rtx
, int, int);
234 static int is_prisky (rtx
, int, int);
235 static int is_exception_free (rtx
, int, int);
237 static bool sets_likely_spilled (rtx
);
238 static void sets_likely_spilled_1 (rtx
, const_rtx
, void *);
239 static void add_branch_dependences (rtx
, rtx
);
240 static void compute_block_dependences (int);
242 static void schedule_region (int);
243 static void concat_insn_mem_list (rtx
, rtx
, rtx
*, rtx
*);
244 static void propagate_deps (int, struct deps_desc
*);
245 static void free_pending_lists (void);
247 /* Functions for construction of the control flow graph. */
249 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
251 We decide not to build the control flow graph if there is possibly more
252 than one entry to the function, if computed branches exist, if we
253 have nonlocal gotos, or if we have an unreachable loop. */
256 is_cfg_nonregular (void)
261 /* If we have a label that could be the target of a nonlocal goto, then
262 the cfg is not well structured. */
263 if (nonlocal_goto_handler_labels
)
266 /* If we have any forced labels, then the cfg is not well structured. */
270 /* If we have exception handlers, then we consider the cfg not well
271 structured. ?!? We should be able to handle this now that we
272 compute an accurate cfg for EH. */
273 if (current_function_has_exception_handlers ())
276 /* If we have insns which refer to labels as non-jumped-to operands,
277 then we consider the cfg not well structured. */
278 FOR_EACH_BB_FN (b
, cfun
)
279 FOR_BB_INSNS (b
, insn
)
281 rtx note
, next
, set
, dest
;
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 /* Note if a block is a natural loop header. */
629 /* Note if a block is a natural inner loop header. */
632 /* Note if a block is in the block queue. */
635 /* Note if a block is in the block queue. */
638 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
639 and a mapping from block to its loop header (if the block is contained
642 Store results in HEADER, INNER, and MAX_HDR respectively, these will
643 be used as inputs to the second traversal.
645 STACK, SP and DFS_NR are only used during the first traversal. */
647 /* Allocate and initialize variables for the first traversal. */
648 max_hdr
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
649 dfs_nr
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
650 stack
= XNEWVEC (edge_iterator
, n_edges_for_fn (cfun
));
652 inner
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
655 header
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
656 bitmap_clear (header
);
658 in_queue
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
659 bitmap_clear (in_queue
);
661 in_stack
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
662 bitmap_clear (in_stack
);
664 for (i
= 0; i
< last_basic_block_for_fn (cfun
); i
++)
667 #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
668 #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
670 /* DFS traversal to find inner loops in the cfg. */
672 current_edge
= ei_start (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->succs
);
677 if (EDGE_PASSED (current_edge
))
679 /* We have reached a leaf node or a node that was already
680 processed. Pop edges off the stack until we find
681 an edge that has not yet been processed. */
682 while (sp
>= 0 && EDGE_PASSED (current_edge
))
684 /* Pop entry off the stack. */
685 current_edge
= stack
[sp
--];
686 node
= ei_edge (current_edge
)->src
->index
;
687 gcc_assert (node
!= ENTRY_BLOCK
);
688 child
= ei_edge (current_edge
)->dest
->index
;
689 gcc_assert (child
!= EXIT_BLOCK
);
690 bitmap_clear_bit (in_stack
, child
);
691 if (max_hdr
[child
] >= 0 && bitmap_bit_p (in_stack
, max_hdr
[child
]))
692 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
693 ei_next (¤t_edge
);
696 /* See if have finished the DFS tree traversal. */
697 if (sp
< 0 && EDGE_PASSED (current_edge
))
700 /* Nope, continue the traversal with the popped node. */
704 /* Process a node. */
705 node
= ei_edge (current_edge
)->src
->index
;
706 gcc_assert (node
!= ENTRY_BLOCK
);
707 bitmap_set_bit (in_stack
, node
);
708 dfs_nr
[node
] = ++count
;
710 /* We don't traverse to the exit block. */
711 child
= ei_edge (current_edge
)->dest
->index
;
712 if (child
== EXIT_BLOCK
)
714 SET_EDGE_PASSED (current_edge
);
715 ei_next (¤t_edge
);
719 /* If the successor is in the stack, then we've found a loop.
720 Mark the loop, if it is not a natural loop, then it will
721 be rejected during the second traversal. */
722 if (bitmap_bit_p (in_stack
, child
))
725 bitmap_set_bit (header
, child
);
726 UPDATE_LOOP_RELATIONS (node
, child
);
727 SET_EDGE_PASSED (current_edge
);
728 ei_next (¤t_edge
);
732 /* If the child was already visited, then there is no need to visit
733 it again. Just update the loop relationships and restart
737 if (max_hdr
[child
] >= 0 && bitmap_bit_p (in_stack
, max_hdr
[child
]))
738 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
739 SET_EDGE_PASSED (current_edge
);
740 ei_next (¤t_edge
);
744 /* Push an entry on the stack and continue DFS traversal. */
745 stack
[++sp
] = current_edge
;
746 SET_EDGE_PASSED (current_edge
);
747 current_edge
= ei_start (ei_edge (current_edge
)->dest
->succs
);
750 /* Reset ->aux field used by EDGE_PASSED. */
751 FOR_ALL_BB_FN (bb
, cfun
)
755 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
760 /* Another check for unreachable blocks. The earlier test in
761 is_cfg_nonregular only finds unreachable blocks that do not
764 The DFS traversal will mark every block that is reachable from
765 the entry node by placing a nonzero value in dfs_nr. Thus if
766 dfs_nr is zero for any block, then it must be unreachable. */
768 FOR_EACH_BB_FN (bb
, cfun
)
769 if (dfs_nr
[bb
->index
] == 0)
775 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
776 to hold degree counts. */
779 FOR_EACH_BB_FN (bb
, cfun
)
780 degree
[bb
->index
] = EDGE_COUNT (bb
->preds
);
782 /* Do not perform region scheduling if there are any unreachable
786 int *queue
, *degree1
= NULL
;
787 /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
788 there basic blocks, which are forced to be region heads.
789 This is done to try to assemble few smaller regions
790 from a too_large region. */
791 sbitmap extended_rgn_header
= NULL
;
792 bool extend_regions_p
;
795 bitmap_set_bit (header
, 0);
797 /* Second traversal:find reducible inner loops and topologically sort
798 block of each region. */
800 queue
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
802 extend_regions_p
= PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS
) > 0;
803 if (extend_regions_p
)
805 degree1
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
806 extended_rgn_header
=
807 sbitmap_alloc (last_basic_block_for_fn (cfun
));
808 bitmap_clear (extended_rgn_header
);
811 /* Find blocks which are inner loop headers. We still have non-reducible
812 loops to consider at this point. */
813 FOR_EACH_BB_FN (bb
, cfun
)
815 if (bitmap_bit_p (header
, bb
->index
) && bitmap_bit_p (inner
, bb
->index
))
821 /* Now check that the loop is reducible. We do this separate
822 from finding inner loops so that we do not find a reducible
823 loop which contains an inner non-reducible loop.
825 A simple way to find reducible/natural loops is to verify
826 that each block in the loop is dominated by the loop
829 If there exists a block that is not dominated by the loop
830 header, then the block is reachable from outside the loop
831 and thus the loop is not a natural loop. */
832 FOR_EACH_BB_FN (jbb
, cfun
)
834 /* First identify blocks in the loop, except for the loop
836 if (bb
->index
== max_hdr
[jbb
->index
] && bb
!= jbb
)
838 /* Now verify that the block is dominated by the loop
840 if (!dominated_by_p (CDI_DOMINATORS
, jbb
, bb
))
845 /* If we exited the loop early, then I is the header of
846 a non-reducible loop and we should quit processing it
848 if (jbb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
851 /* I is a header of an inner loop, or block 0 in a subroutine
852 with no loops at all. */
854 too_large_failure
= 0;
855 loop_head
= max_hdr
[bb
->index
];
857 if (extend_regions_p
)
858 /* We save degree in case when we meet a too_large region
859 and cancel it. We need a correct degree later when
860 calling extend_rgns. */
861 memcpy (degree1
, degree
,
862 last_basic_block_for_fn (cfun
) * sizeof (int));
864 /* Decrease degree of all I's successors for topological
866 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
867 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
868 --degree
[e
->dest
->index
];
870 /* Estimate # insns, and count # blocks in the region. */
872 num_insns
= common_sched_info
->estimate_number_of_insns (bb
);
874 /* Find all loop latches (blocks with back edges to the loop
875 header) or all the leaf blocks in the cfg has no loops.
877 Place those blocks into the queue. */
880 FOR_EACH_BB_FN (jbb
, cfun
)
881 /* Leaf nodes have only a single successor which must
883 if (single_succ_p (jbb
)
884 && single_succ (jbb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
886 queue
[++tail
] = jbb
->index
;
887 bitmap_set_bit (in_queue
, jbb
->index
);
889 if (too_large (jbb
->index
, &num_bbs
, &num_insns
))
891 too_large_failure
= 1;
900 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
902 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
905 node
= e
->src
->index
;
907 if (max_hdr
[node
] == loop_head
&& node
!= bb
->index
)
909 /* This is a loop latch. */
910 queue
[++tail
] = node
;
911 bitmap_set_bit (in_queue
, node
);
913 if (too_large (node
, &num_bbs
, &num_insns
))
915 too_large_failure
= 1;
922 /* Now add all the blocks in the loop to the queue.
924 We know the loop is a natural loop; however the algorithm
925 above will not always mark certain blocks as being in the
933 The algorithm in the DFS traversal may not mark B & D as part
934 of the loop (i.e. they will not have max_hdr set to A).
936 We know they can not be loop latches (else they would have
937 had max_hdr set since they'd have a backedge to a dominator
938 block). So we don't need them on the initial queue.
940 We know they are part of the loop because they are dominated
941 by the loop header and can be reached by a backwards walk of
942 the edges starting with nodes on the initial queue.
944 It is safe and desirable to include those nodes in the
945 loop/scheduling region. To do so we would need to decrease
946 the degree of a node if it is the target of a backedge
947 within the loop itself as the node is placed in the queue.
949 We do not do this because I'm not sure that the actual
950 scheduling code will properly handle this case. ?!? */
952 while (head
< tail
&& !too_large_failure
)
955 child
= queue
[++head
];
957 FOR_EACH_EDGE (e
, ei
,
958 BASIC_BLOCK_FOR_FN (cfun
, child
)->preds
)
960 node
= e
->src
->index
;
962 /* See discussion above about nodes not marked as in
963 this loop during the initial DFS traversal. */
964 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
965 || max_hdr
[node
] != loop_head
)
970 else if (!bitmap_bit_p (in_queue
, node
) && node
!= bb
->index
)
972 queue
[++tail
] = node
;
973 bitmap_set_bit (in_queue
, node
);
975 if (too_large (node
, &num_bbs
, &num_insns
))
977 too_large_failure
= 1;
984 if (tail
>= 0 && !too_large_failure
)
986 /* Place the loop header into list of region blocks. */
987 degree
[bb
->index
] = -1;
988 rgn_bb_table
[idx
] = bb
->index
;
989 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
990 RGN_BLOCKS (nr_regions
) = idx
++;
991 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
992 RGN_HAS_REAL_EBB (nr_regions
) = 0;
993 CONTAINING_RGN (bb
->index
) = nr_regions
;
994 BLOCK_TO_BB (bb
->index
) = count
= 0;
996 /* Remove blocks from queue[] when their in degree
997 becomes zero. Repeat until no blocks are left on the
998 list. This produces a topological list of blocks in
1004 child
= queue
[head
];
1005 if (degree
[child
] == 0)
1010 rgn_bb_table
[idx
++] = child
;
1011 BLOCK_TO_BB (child
) = ++count
;
1012 CONTAINING_RGN (child
) = nr_regions
;
1013 queue
[head
] = queue
[tail
--];
1015 FOR_EACH_EDGE (e
, ei
,
1016 BASIC_BLOCK_FOR_FN (cfun
,
1018 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1019 --degree
[e
->dest
->index
];
1026 else if (extend_regions_p
)
1028 /* Restore DEGREE. */
1034 /* And force successors of BB to be region heads.
1035 This may provide several smaller regions instead
1036 of one too_large region. */
1037 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1038 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1039 bitmap_set_bit (extended_rgn_header
, e
->dest
->index
);
1045 if (extend_regions_p
)
1049 bitmap_ior (header
, header
, extended_rgn_header
);
1050 sbitmap_free (extended_rgn_header
);
1052 extend_rgns (degree
, &idx
, header
, max_hdr
);
1056 /* Any block that did not end up in a region is placed into a region
1058 FOR_EACH_BB_FN (bb
, cfun
)
1059 if (degree
[bb
->index
] >= 0)
1061 rgn_bb_table
[idx
] = bb
->index
;
1062 RGN_NR_BLOCKS (nr_regions
) = 1;
1063 RGN_BLOCKS (nr_regions
) = idx
++;
1064 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1065 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1066 CONTAINING_RGN (bb
->index
) = nr_regions
++;
1067 BLOCK_TO_BB (bb
->index
) = 0;
1070 nr_regions_initial
= nr_regions
;
1074 sbitmap_free (header
);
1075 sbitmap_free (inner
);
1076 sbitmap_free (in_queue
);
1077 sbitmap_free (in_stack
);
1081 /* Wrapper function.
1082 If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
1083 regions. Otherwise just call find_rgns_haifa. */
1087 if (sel_sched_p () && flag_sel_sched_pipelining
)
1093 static int gather_region_statistics (int **);
1094 static void print_region_statistics (int *, int, int *, int);
1096 /* Calculate the histogram that shows the number of regions having the
1097 given number of basic blocks, and store it in the RSP array. Return
1098 the size of this array. */
1100 gather_region_statistics (int **rsp
)
1102 int i
, *a
= 0, a_sz
= 0;
1104 /* a[i] is the number of regions that have (i + 1) basic blocks. */
1105 for (i
= 0; i
< nr_regions
; i
++)
1107 int nr_blocks
= RGN_NR_BLOCKS (i
);
1109 gcc_assert (nr_blocks
>= 1);
1111 if (nr_blocks
> a_sz
)
1113 a
= XRESIZEVEC (int, a
, nr_blocks
);
1116 while (a_sz
!= nr_blocks
);
1126 /* Print regions statistics. S1 and S2 denote the data before and after
1127 calling extend_rgns, respectively. */
1129 print_region_statistics (int *s1
, int s1_sz
, int *s2
, int s2_sz
)
1133 /* We iterate until s2_sz because extend_rgns does not decrease
1134 the maximal region size. */
1135 for (i
= 1; i
< s2_sz
; i
++)
1149 fprintf (sched_dump
, ";; Region extension statistics: size %d: " \
1150 "was %d + %d more\n", i
+ 1, n1
, n2
- n1
);
1155 DEGREE - Array of incoming edge count, considering only
1156 the edges, that don't have their sources in formed regions yet.
1157 IDXP - pointer to the next available index in rgn_bb_table.
1158 HEADER - set of all region heads.
1159 LOOP_HDR - mapping from block to the containing loop
1160 (two blocks can reside within one region if they have
1161 the same loop header). */
1163 extend_rgns (int *degree
, int *idxp
, sbitmap header
, int *loop_hdr
)
1165 int *order
, i
, rescan
= 0, idx
= *idxp
, iter
= 0, max_iter
, *max_hdr
;
1166 int nblocks
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
1168 max_iter
= PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS
);
1170 max_hdr
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1172 order
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1173 post_order_compute (order
, false, false);
1175 for (i
= nblocks
- 1; i
>= 0; i
--)
1178 if (degree
[bbn
] >= 0)
1184 /* This block already was processed in find_rgns. */
1188 /* The idea is to topologically walk through CFG in top-down order.
1189 During the traversal, if all the predecessors of a node are
1190 marked to be in the same region (they all have the same max_hdr),
1191 then current node is also marked to be a part of that region.
1192 Otherwise the node starts its own region.
1193 CFG should be traversed until no further changes are made. On each
1194 iteration the set of the region heads is extended (the set of those
1195 blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
1196 set of all basic blocks, thus the algorithm is guaranteed to
1199 while (rescan
&& iter
< max_iter
)
1203 for (i
= nblocks
- 1; i
>= 0; i
--)
1209 if (max_hdr
[bbn
] != -1 && !bitmap_bit_p (header
, bbn
))
1213 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK_FOR_FN (cfun
, bbn
)->preds
)
1215 int predn
= e
->src
->index
;
1217 if (predn
!= ENTRY_BLOCK
1218 /* If pred wasn't processed in find_rgns. */
1219 && max_hdr
[predn
] != -1
1220 /* And pred and bb reside in the same loop.
1221 (Or out of any loop). */
1222 && loop_hdr
[bbn
] == loop_hdr
[predn
])
1225 /* Then bb extends the containing region of pred. */
1226 hdr
= max_hdr
[predn
];
1227 else if (hdr
!= max_hdr
[predn
])
1228 /* Too bad, there are at least two predecessors
1229 that reside in different regions. Thus, BB should
1230 begin its own region. */
1237 /* BB starts its own region. */
1246 /* If BB start its own region,
1247 update set of headers with BB. */
1248 bitmap_set_bit (header
, bbn
);
1252 gcc_assert (hdr
!= -1);
1261 /* Statistics were gathered on the SPEC2000 package of tests with
1262 mainline weekly snapshot gcc-4.1-20051015 on ia64.
1264 Statistics for SPECint:
1265 1 iteration : 1751 cases (38.7%)
1266 2 iterations: 2770 cases (61.3%)
1267 Blocks wrapped in regions by find_rgns without extension: 18295 blocks
1268 Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
1269 (We don't count single block regions here).
1271 Statistics for SPECfp:
1272 1 iteration : 621 cases (35.9%)
1273 2 iterations: 1110 cases (64.1%)
1274 Blocks wrapped in regions by find_rgns without extension: 6476 blocks
1275 Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
1276 (We don't count single block regions here).
1278 By default we do at most 2 iterations.
1279 This can be overridden with max-sched-extend-regions-iters parameter:
1280 0 - disable region extension,
1281 N > 0 - do at most N iterations. */
1283 if (sched_verbose
&& iter
!= 0)
1284 fprintf (sched_dump
, ";; Region extension iterations: %d%s\n", iter
,
1285 rescan
? "... failed" : "");
1287 if (!rescan
&& iter
!= 0)
1289 int *s1
= NULL
, s1_sz
= 0;
1291 /* Save the old statistics for later printout. */
1292 if (sched_verbose
>= 6)
1293 s1_sz
= gather_region_statistics (&s1
);
1295 /* We have succeeded. Now assemble the regions. */
1296 for (i
= nblocks
- 1; i
>= 0; i
--)
1300 if (max_hdr
[bbn
] == bbn
)
1301 /* BBN is a region head. */
1305 int num_bbs
= 0, j
, num_insns
= 0, large
;
1307 large
= too_large (bbn
, &num_bbs
, &num_insns
);
1310 rgn_bb_table
[idx
] = bbn
;
1311 RGN_BLOCKS (nr_regions
) = idx
++;
1312 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1313 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1314 CONTAINING_RGN (bbn
) = nr_regions
;
1315 BLOCK_TO_BB (bbn
) = 0;
1317 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK_FOR_FN (cfun
, bbn
)->succs
)
1318 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1319 degree
[e
->dest
->index
]--;
1322 /* Here we check whether the region is too_large. */
1323 for (j
= i
- 1; j
>= 0; j
--)
1325 int succn
= order
[j
];
1326 if (max_hdr
[succn
] == bbn
)
1328 if ((large
= too_large (succn
, &num_bbs
, &num_insns
)))
1334 /* If the region is too_large, then wrap every block of
1335 the region into single block region.
1336 Here we wrap region head only. Other blocks are
1337 processed in the below cycle. */
1339 RGN_NR_BLOCKS (nr_regions
) = 1;
1345 for (j
= i
- 1; j
>= 0; j
--)
1347 int succn
= order
[j
];
1349 if (max_hdr
[succn
] == bbn
)
1350 /* This cycle iterates over all basic blocks, that
1351 are supposed to be in the region with head BBN,
1352 and wraps them into that region (or in single
1355 gcc_assert (degree
[succn
] == 0);
1358 rgn_bb_table
[idx
] = succn
;
1359 BLOCK_TO_BB (succn
) = large
? 0 : num_bbs
++;
1360 CONTAINING_RGN (succn
) = nr_regions
;
1363 /* Wrap SUCCN into single block region. */
1365 RGN_BLOCKS (nr_regions
) = idx
;
1366 RGN_NR_BLOCKS (nr_regions
) = 1;
1367 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1368 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1374 FOR_EACH_EDGE (e
, ei
,
1375 BASIC_BLOCK_FOR_FN (cfun
, succn
)->succs
)
1376 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1377 degree
[e
->dest
->index
]--;
1383 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1389 if (sched_verbose
>= 6)
1393 /* Get the new statistics and print the comparison with the
1394 one before calling this function. */
1395 s2_sz
= gather_region_statistics (&s2
);
1396 print_region_statistics (s1
, s1_sz
, s2
, s2_sz
);
1408 /* Functions for regions scheduling information. */
1410 /* Compute dominators, probability, and potential-split-edges of bb.
1411 Assume that these values were already computed for bb's predecessors. */
1414 compute_dom_prob_ps (int bb
)
1416 edge_iterator in_ei
;
1419 /* We shouldn't have any real ebbs yet. */
1420 gcc_assert (ebb_head
[bb
] == bb
+ current_blocks
);
1422 if (IS_RGN_ENTRY (bb
))
1424 bitmap_set_bit (dom
[bb
], 0);
1425 prob
[bb
] = REG_BR_PROB_BASE
;
1431 /* Initialize dom[bb] to '111..1'. */
1432 bitmap_ones (dom
[bb
]);
1434 FOR_EACH_EDGE (in_edge
, in_ei
,
1435 BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (bb
))->preds
)
1439 edge_iterator out_ei
;
1441 if (in_edge
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1444 pred_bb
= BLOCK_TO_BB (in_edge
->src
->index
);
1445 bitmap_and (dom
[bb
], dom
[bb
], dom
[pred_bb
]);
1446 bitmap_ior (ancestor_edges
[bb
],
1447 ancestor_edges
[bb
], ancestor_edges
[pred_bb
]);
1449 bitmap_set_bit (ancestor_edges
[bb
], EDGE_TO_BIT (in_edge
));
1451 bitmap_ior (pot_split
[bb
], pot_split
[bb
], pot_split
[pred_bb
]);
1453 FOR_EACH_EDGE (out_edge
, out_ei
, in_edge
->src
->succs
)
1454 bitmap_set_bit (pot_split
[bb
], EDGE_TO_BIT (out_edge
));
1456 prob
[bb
] += combine_probabilities (prob
[pred_bb
], in_edge
->probability
);
1457 // The rounding divide in combine_probabilities can result in an extra
1458 // probability increment propagating along 50-50 edges. Eventually when
1459 // the edges re-merge, the accumulated probability can go slightly above
1460 // REG_BR_PROB_BASE.
1461 if (prob
[bb
] > REG_BR_PROB_BASE
)
1462 prob
[bb
] = REG_BR_PROB_BASE
;
1465 bitmap_set_bit (dom
[bb
], bb
);
1466 bitmap_and_compl (pot_split
[bb
], pot_split
[bb
], ancestor_edges
[bb
]);
1468 if (sched_verbose
>= 2)
1469 fprintf (sched_dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
),
1470 (100 * prob
[bb
]) / REG_BR_PROB_BASE
);
1473 /* Functions for target info. */
1475 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1476 Note that bb_trg dominates bb_src. */
1479 split_edges (int bb_src
, int bb_trg
, edgelst
*bl
)
1481 sbitmap src
= sbitmap_alloc (SBITMAP_SIZE (pot_split
[bb_src
]));
1482 bitmap_copy (src
, pot_split
[bb_src
]);
1484 bitmap_and_compl (src
, src
, pot_split
[bb_trg
]);
1485 extract_edgelst (src
, bl
);
1489 /* Find the valid candidate-source-blocks for the target block TRG, compute
1490 their probability, and check if they are speculative or not.
1491 For speculative sources, compute their update-blocks and split-blocks. */
1494 compute_trg_info (int trg
)
1497 edgelst el
= { NULL
, 0 };
1498 int i
, j
, k
, update_idx
;
1504 candidate_table
= XNEWVEC (candidate
, current_nr_blocks
);
1507 /* bblst_table holds split blocks and update blocks for each block after
1508 the current one in the region. split blocks and update blocks are
1509 the TO blocks of region edges, so there can be at most rgn_nr_edges
1511 bblst_size
= (current_nr_blocks
- target_bb
) * rgn_nr_edges
;
1512 bblst_table
= XNEWVEC (basic_block
, bblst_size
);
1515 edgelst_table
= XNEWVEC (edge
, rgn_nr_edges
);
1517 /* Define some of the fields for the target bb as well. */
1518 sp
= candidate_table
+ trg
;
1520 sp
->is_speculative
= 0;
1521 sp
->src_prob
= REG_BR_PROB_BASE
;
1523 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1525 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1527 sp
= candidate_table
+ i
;
1529 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1532 int tf
= prob
[trg
], cf
= prob
[i
];
1534 /* In CFGs with low probability edges TF can possibly be zero. */
1535 sp
->src_prob
= (tf
? GCOV_COMPUTE_SCALE (cf
, tf
) : 0);
1536 sp
->is_valid
= (sp
->src_prob
>= min_spec_prob
);
1541 split_edges (i
, trg
, &el
);
1542 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1543 if (sp
->is_speculative
&& !flag_schedule_speculative
)
1549 /* Compute split blocks and store them in bblst_table.
1550 The TO block of every split edge is a split block. */
1551 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
1552 sp
->split_bbs
.nr_members
= el
.nr_members
;
1553 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
1554 bblst_table
[bblst_last
] = el
.first_member
[j
]->dest
;
1555 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
1557 /* Compute update blocks and store them in bblst_table.
1558 For every split edge, look at the FROM block, and check
1559 all out edges. For each out edge that is not a split edge,
1560 add the TO block to the update block list. This list can end
1561 up with a lot of duplicates. We need to weed them out to avoid
1562 overrunning the end of the bblst_table. */
1565 bitmap_clear (visited
);
1566 for (j
= 0; j
< el
.nr_members
; j
++)
1568 block
= el
.first_member
[j
]->src
;
1569 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1571 if (!bitmap_bit_p (visited
, e
->dest
->index
))
1573 for (k
= 0; k
< el
.nr_members
; k
++)
1574 if (e
== el
.first_member
[k
])
1577 if (k
>= el
.nr_members
)
1579 bblst_table
[bblst_last
++] = e
->dest
;
1580 bitmap_set_bit (visited
, e
->dest
->index
);
1586 sp
->update_bbs
.nr_members
= update_idx
;
1588 /* Make sure we didn't overrun the end of bblst_table. */
1589 gcc_assert (bblst_last
<= bblst_size
);
1593 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
1595 sp
->is_speculative
= 0;
1600 sbitmap_free (visited
);
1603 /* Free the computed target info. */
1605 free_trg_info (void)
1607 free (candidate_table
);
1609 free (edgelst_table
);
1612 /* Print candidates info, for debugging purposes. Callable from debugger. */
1615 debug_candidate (int i
)
1617 if (!candidate_table
[i
].is_valid
)
1620 if (candidate_table
[i
].is_speculative
)
1623 fprintf (sched_dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
1625 fprintf (sched_dump
, "split path: ");
1626 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
1628 int b
= candidate_table
[i
].split_bbs
.first_member
[j
]->index
;
1630 fprintf (sched_dump
, " %d ", b
);
1632 fprintf (sched_dump
, "\n");
1634 fprintf (sched_dump
, "update path: ");
1635 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
1637 int b
= candidate_table
[i
].update_bbs
.first_member
[j
]->index
;
1639 fprintf (sched_dump
, " %d ", b
);
1641 fprintf (sched_dump
, "\n");
1645 fprintf (sched_dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
1649 /* Print candidates info, for debugging purposes. Callable from debugger. */
1652 debug_candidates (int trg
)
1656 fprintf (sched_dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
1657 BB_TO_BLOCK (trg
), trg
);
1658 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1659 debug_candidate (i
);
1662 /* Functions for speculative scheduling. */
1664 static bitmap_head not_in_df
;
1666 /* Return 0 if x is a set of a register alive in the beginning of one
1667 of the split-blocks of src, otherwise return 1. */
1670 check_live_1 (int src
, rtx x
)
1674 rtx reg
= SET_DEST (x
);
1679 while (GET_CODE (reg
) == SUBREG
1680 || GET_CODE (reg
) == ZERO_EXTRACT
1681 || GET_CODE (reg
) == STRICT_LOW_PART
)
1682 reg
= XEXP (reg
, 0);
1684 if (GET_CODE (reg
) == PARALLEL
)
1688 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1689 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1690 if (check_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0)))
1699 regno
= REGNO (reg
);
1701 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
1703 /* Global registers are assumed live. */
1708 if (regno
< FIRST_PSEUDO_REGISTER
)
1710 /* Check for hard registers. */
1711 int j
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1714 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1716 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1717 int t
= bitmap_bit_p (¬_in_df
, b
->index
);
1719 /* We can have split blocks, that were recently generated.
1720 Such blocks are always outside current region. */
1721 gcc_assert (!t
|| (CONTAINING_RGN (b
->index
)
1722 != CONTAINING_RGN (BB_TO_BLOCK (src
))));
1724 if (t
|| REGNO_REG_SET_P (df_get_live_in (b
), regno
+ j
))
1731 /* Check for pseudo registers. */
1732 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1734 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1735 int t
= bitmap_bit_p (¬_in_df
, b
->index
);
1737 gcc_assert (!t
|| (CONTAINING_RGN (b
->index
)
1738 != CONTAINING_RGN (BB_TO_BLOCK (src
))));
1740 if (t
|| REGNO_REG_SET_P (df_get_live_in (b
), regno
))
1749 /* If x is a set of a register R, mark that R is alive in the beginning
1750 of every update-block of src. */
1753 update_live_1 (int src
, rtx x
)
1757 rtx reg
= SET_DEST (x
);
1762 while (GET_CODE (reg
) == SUBREG
1763 || GET_CODE (reg
) == ZERO_EXTRACT
1764 || GET_CODE (reg
) == STRICT_LOW_PART
)
1765 reg
= XEXP (reg
, 0);
1767 if (GET_CODE (reg
) == PARALLEL
)
1771 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1772 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1773 update_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0));
1781 /* Global registers are always live, so the code below does not apply
1784 regno
= REGNO (reg
);
1786 if (! HARD_REGISTER_NUM_P (regno
)
1787 || !global_regs
[regno
])
1789 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
1791 basic_block b
= candidate_table
[src
].update_bbs
.first_member
[i
];
1793 if (HARD_REGISTER_NUM_P (regno
))
1794 bitmap_set_range (df_get_live_in (b
), regno
,
1795 hard_regno_nregs
[regno
][GET_MODE (reg
)]);
1797 bitmap_set_bit (df_get_live_in (b
), regno
);
1802 /* Return 1 if insn can be speculatively moved from block src to trg,
1803 otherwise return 0. Called before first insertion of insn to
1804 ready-list or before the scheduling. */
1807 check_live (rtx insn
, int src
)
1809 /* Find the registers set by instruction. */
1810 if (GET_CODE (PATTERN (insn
)) == SET
1811 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1812 return check_live_1 (src
, PATTERN (insn
));
1813 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1816 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1817 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1818 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1819 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
1828 /* Update the live registers info after insn was moved speculatively from
1829 block src to trg. */
1832 update_live (rtx insn
, int src
)
1834 /* Find the registers set by instruction. */
1835 if (GET_CODE (PATTERN (insn
)) == SET
1836 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1837 update_live_1 (src
, PATTERN (insn
));
1838 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1841 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1842 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1843 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1844 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
1848 /* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1849 #define IS_REACHABLE(bb_from, bb_to) \
1851 || IS_RGN_ENTRY (bb_from) \
1852 || (bitmap_bit_p (ancestor_edges[bb_to], \
1853 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK_FOR_FN (cfun, \
1854 BB_TO_BLOCK (bb_from)))))))
1856 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1859 set_spec_fed (rtx load_insn
)
1861 sd_iterator_def sd_it
;
1864 FOR_EACH_DEP (load_insn
, SD_LIST_FORW
, sd_it
, dep
)
1865 if (DEP_TYPE (dep
) == REG_DEP_TRUE
)
1866 FED_BY_SPEC_LOAD (DEP_CON (dep
)) = 1;
1869 /* On the path from the insn to load_insn_bb, find a conditional
1870 branch depending on insn, that guards the speculative load. */
1873 find_conditional_protection (rtx insn
, int load_insn_bb
)
1875 sd_iterator_def sd_it
;
1878 /* Iterate through DEF-USE forward dependences. */
1879 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
1881 rtx next
= DEP_CON (dep
);
1883 if ((CONTAINING_RGN (BLOCK_NUM (next
)) ==
1884 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
1885 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
1886 && load_insn_bb
!= INSN_BB (next
)
1887 && DEP_TYPE (dep
) == REG_DEP_TRUE
1889 || find_conditional_protection (next
, load_insn_bb
)))
1893 } /* find_conditional_protection */
1895 /* Returns 1 if the same insn1 that participates in the computation
1896 of load_insn's address is feeding a conditional branch that is
1897 guarding on load_insn. This is true if we find two DEF-USE
1899 insn1 -> ... -> conditional-branch
1900 insn1 -> ... -> load_insn,
1901 and if a flow path exists:
1902 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1903 and if insn1 is on the path
1904 region-entry -> ... -> bb_trg -> ... load_insn.
1906 Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
1907 Locate the branch by following INSN_FORW_DEPS from insn1. */
1910 is_conditionally_protected (rtx load_insn
, int bb_src
, int bb_trg
)
1912 sd_iterator_def sd_it
;
1915 FOR_EACH_DEP (load_insn
, SD_LIST_BACK
, sd_it
, dep
)
1917 rtx insn1
= DEP_PRO (dep
);
1919 /* Must be a DEF-USE dependence upon non-branch. */
1920 if (DEP_TYPE (dep
) != REG_DEP_TRUE
1924 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1925 if (INSN_BB (insn1
) == bb_src
1926 || (CONTAINING_RGN (BLOCK_NUM (insn1
))
1927 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
1928 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
1929 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
1932 /* Now search for the conditional-branch. */
1933 if (find_conditional_protection (insn1
, bb_src
))
1936 /* Recursive step: search another insn1, "above" current insn1. */
1937 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
1940 /* The chain does not exist. */
1942 } /* is_conditionally_protected */
1944 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1945 load_insn can move speculatively from bb_src to bb_trg. All the
1946 following must hold:
1948 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1949 (2) load_insn and load1 have a def-use dependence upon
1950 the same insn 'insn1'.
1951 (3) either load2 is in bb_trg, or:
1952 - there's only one split-block, and
1953 - load1 is on the escape path, and
1955 From all these we can conclude that the two loads access memory
1956 addresses that differ at most by a constant, and hence if moving
1957 load_insn would cause an exception, it would have been caused by
1961 is_pfree (rtx load_insn
, int bb_src
, int bb_trg
)
1963 sd_iterator_def back_sd_it
;
1965 candidate
*candp
= candidate_table
+ bb_src
;
1967 if (candp
->split_bbs
.nr_members
!= 1)
1968 /* Must have exactly one escape block. */
1971 FOR_EACH_DEP (load_insn
, SD_LIST_BACK
, back_sd_it
, back_dep
)
1973 rtx insn1
= DEP_PRO (back_dep
);
1975 if (DEP_TYPE (back_dep
) == REG_DEP_TRUE
)
1976 /* Found a DEF-USE dependence (insn1, load_insn). */
1978 sd_iterator_def fore_sd_it
;
1981 FOR_EACH_DEP (insn1
, SD_LIST_FORW
, fore_sd_it
, fore_dep
)
1983 rtx insn2
= DEP_CON (fore_dep
);
1985 if (DEP_TYPE (fore_dep
) == REG_DEP_TRUE
)
1987 /* Found a DEF-USE dependence (insn1, insn2). */
1988 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
1989 /* insn2 not guaranteed to be a 1 base reg load. */
1992 if (INSN_BB (insn2
) == bb_trg
)
1993 /* insn2 is the similar load, in the target block. */
1996 if (*(candp
->split_bbs
.first_member
) == BLOCK_FOR_INSN (insn2
))
1997 /* insn2 is a similar load, in a split-block. */
2004 /* Couldn't find a similar load. */
2008 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2009 a load moved speculatively, or if load_insn is protected by
2010 a compare on load_insn's address). */
2013 is_prisky (rtx load_insn
, int bb_src
, int bb_trg
)
2015 if (FED_BY_SPEC_LOAD (load_insn
))
2018 if (sd_lists_empty_p (load_insn
, SD_LIST_BACK
))
2019 /* Dependence may 'hide' out of the region. */
2022 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2028 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2029 Return 1 if insn is exception-free (and the motion is valid)
2033 is_exception_free (rtx insn
, int bb_src
, int bb_trg
)
2035 int insn_class
= haifa_classify_insn (insn
);
2037 /* Handle non-load insns. */
2048 if (!flag_schedule_speculative_load
)
2050 IS_LOAD_INSN (insn
) = 1;
2057 case PFREE_CANDIDATE
:
2058 if (is_pfree (insn
, bb_src
, bb_trg
))
2060 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2061 case PRISKY_CANDIDATE
:
2062 if (!flag_schedule_speculative_load_dangerous
2063 || is_prisky (insn
, bb_src
, bb_trg
))
2069 return flag_schedule_speculative_load_dangerous
;
2072 /* The number of insns from the current block scheduled so far. */
2073 static int sched_target_n_insns
;
2074 /* The number of insns from the current block to be scheduled in total. */
2075 static int target_n_insns
;
2076 /* The number of insns from the entire region scheduled so far. */
2077 static int sched_n_insns
;
2079 /* Implementations of the sched_info functions for region scheduling. */
2080 static void init_ready_list (void);
2081 static int can_schedule_ready_p (rtx
);
2082 static void begin_schedule_ready (rtx
);
2083 static ds_t
new_ready (rtx
, ds_t
);
2084 static int schedule_more_p (void);
2085 static const char *rgn_print_insn (const_rtx
, int);
2086 static int rgn_rank (rtx
, rtx
);
2087 static void compute_jump_reg_dependencies (rtx
, regset
);
2089 /* Functions for speculative scheduling. */
2090 static void rgn_add_remove_insn (rtx
, int);
2091 static void rgn_add_block (basic_block
, basic_block
);
2092 static void rgn_fix_recovery_cfg (int, int, int);
2093 static basic_block
advance_target_bb (basic_block
, rtx
);
2095 /* Return nonzero if there are more insns that should be scheduled. */
2098 schedule_more_p (void)
2100 return sched_target_n_insns
< target_n_insns
;
2103 /* Add all insns that are initially ready to the ready list READY. Called
2104 once before scheduling a set of insns. */
2107 init_ready_list (void)
2109 rtx prev_head
= current_sched_info
->prev_head
;
2110 rtx next_tail
= current_sched_info
->next_tail
;
2115 sched_target_n_insns
= 0;
2118 /* Print debugging information. */
2119 if (sched_verbose
>= 5)
2120 debug_rgn_dependencies (target_bb
);
2122 /* Prepare current target block info. */
2123 if (current_nr_blocks
> 1)
2124 compute_trg_info (target_bb
);
2126 /* Initialize ready list with all 'ready' insns in target block.
2127 Count number of insns in the target block being scheduled. */
2128 for (insn
= NEXT_INSN (prev_head
); insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2130 gcc_assert (TODO_SPEC (insn
) == HARD_DEP
|| TODO_SPEC (insn
) == DEP_POSTPONED
);
2131 TODO_SPEC (insn
) = HARD_DEP
;
2135 gcc_assert (!(TODO_SPEC (insn
) & BEGIN_CONTROL
));
2138 /* Add to ready list all 'ready' insns in valid source blocks.
2139 For speculative insns, check-live, exception-free, and
2141 for (bb_src
= target_bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
2142 if (IS_VALID (bb_src
))
2148 get_ebb_head_tail (EBB_FIRST_BB (bb_src
), EBB_LAST_BB (bb_src
),
2150 src_next_tail
= NEXT_INSN (tail
);
2153 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
2156 gcc_assert (TODO_SPEC (insn
) == HARD_DEP
|| TODO_SPEC (insn
) == DEP_POSTPONED
);
2157 TODO_SPEC (insn
) = HARD_DEP
;
2163 /* Called after taking INSN from the ready list. Returns nonzero if this
2164 insn can be scheduled, nonzero if we should silently discard it. */
2167 can_schedule_ready_p (rtx insn
)
2169 /* An interblock motion? */
2170 if (INSN_BB (insn
) != target_bb
2171 && IS_SPECULATIVE_INSN (insn
)
2172 && !check_live (insn
, INSN_BB (insn
)))
2178 /* Updates counter and other information. Split from can_schedule_ready_p ()
2179 because when we schedule insn speculatively then insn passed to
2180 can_schedule_ready_p () differs from the one passed to
2181 begin_schedule_ready (). */
2183 begin_schedule_ready (rtx insn
)
2185 /* An interblock motion? */
2186 if (INSN_BB (insn
) != target_bb
)
2188 if (IS_SPECULATIVE_INSN (insn
))
2190 gcc_assert (check_live (insn
, INSN_BB (insn
)));
2192 update_live (insn
, INSN_BB (insn
));
2194 /* For speculative load, mark insns fed by it. */
2195 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
2196 set_spec_fed (insn
);
2204 /* In block motion. */
2205 sched_target_n_insns
++;
2210 /* Called after INSN has all its hard dependencies resolved and the speculation
2211 of type TS is enough to overcome them all.
2212 Return nonzero if it should be moved to the ready list or the queue, or zero
2213 if we should silently discard it. */
2215 new_ready (rtx next
, ds_t ts
)
2217 if (INSN_BB (next
) != target_bb
)
2219 int not_ex_free
= 0;
2221 /* For speculative insns, before inserting to ready/queue,
2222 check live, exception-free, and issue-delay. */
2223 if (!IS_VALID (INSN_BB (next
))
2225 || (IS_SPECULATIVE_INSN (next
)
2226 && ((recog_memoized (next
) >= 0
2227 && min_insn_conflict_delay (curr_state
, next
, next
)
2228 > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY
))
2229 || IS_SPECULATION_CHECK_P (next
)
2230 || !check_live (next
, INSN_BB (next
))
2231 || (not_ex_free
= !is_exception_free (next
, INSN_BB (next
),
2235 /* We are here because is_exception_free () == false.
2236 But we possibly can handle that with control speculation. */
2237 && sched_deps_info
->generate_spec_deps
2238 && spec_info
->mask
& BEGIN_CONTROL
)
2242 /* Add control speculation to NEXT's dependency type. */
2243 new_ds
= set_dep_weak (ts
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
2245 /* Check if NEXT can be speculated with new dependency type. */
2246 if (sched_insn_is_legitimate_for_speculation_p (next
, new_ds
))
2247 /* Here we got new control-speculative instruction. */
2250 /* NEXT isn't ready yet. */
2254 /* NEXT isn't ready yet. */
2262 /* Return a string that contains the insn uid and optionally anything else
2263 necessary to identify this insn in an output. It's valid to use a
2264 static buffer for this. The ALIGNED parameter should cause the string
2265 to be formatted so that multiple output lines will line up nicely. */
2268 rgn_print_insn (const_rtx insn
, int aligned
)
2270 static char tmp
[80];
2273 sprintf (tmp
, "b%3d: i%4d", INSN_BB (insn
), INSN_UID (insn
));
2276 if (current_nr_blocks
> 1 && INSN_BB (insn
) != target_bb
)
2277 sprintf (tmp
, "%d/b%d", INSN_UID (insn
), INSN_BB (insn
));
2279 sprintf (tmp
, "%d", INSN_UID (insn
));
2284 /* Compare priority of two insns. Return a positive number if the second
2285 insn is to be preferred for scheduling, and a negative one if the first
2286 is to be preferred. Zero if they are equally good. */
2289 rgn_rank (rtx insn1
, rtx insn2
)
2291 /* Some comparison make sense in interblock scheduling only. */
2292 if (INSN_BB (insn1
) != INSN_BB (insn2
))
2294 int spec_val
, prob_val
;
2296 /* Prefer an inblock motion on an interblock motion. */
2297 if ((INSN_BB (insn2
) == target_bb
) && (INSN_BB (insn1
) != target_bb
))
2299 if ((INSN_BB (insn1
) == target_bb
) && (INSN_BB (insn2
) != target_bb
))
2302 /* Prefer a useful motion on a speculative one. */
2303 spec_val
= IS_SPECULATIVE_INSN (insn1
) - IS_SPECULATIVE_INSN (insn2
);
2307 /* Prefer a more probable (speculative) insn. */
2308 prob_val
= INSN_PROBABILITY (insn2
) - INSN_PROBABILITY (insn1
);
2315 /* NEXT is an instruction that depends on INSN (a backward dependence);
2316 return nonzero if we should include this dependence in priority
2320 contributes_to_priority (rtx next
, rtx insn
)
2322 /* NEXT and INSN reside in one ebb. */
2323 return BLOCK_TO_BB (BLOCK_NUM (next
)) == BLOCK_TO_BB (BLOCK_NUM (insn
));
2326 /* INSN is a JUMP_INSN. Store the set of registers that must be
2327 considered as used by this jump in USED. */
2330 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
2331 regset used ATTRIBUTE_UNUSED
)
2333 /* Nothing to do here, since we postprocess jumps in
2334 add_branch_dependences. */
2337 /* This variable holds common_sched_info hooks and data relevant to
2338 the interblock scheduler. */
2339 static struct common_sched_info_def rgn_common_sched_info
;
2342 /* This holds data for the dependence analysis relevant to
2343 the interblock scheduler. */
2344 static struct sched_deps_info_def rgn_sched_deps_info
;
2346 /* This holds constant data used for initializing the above structure
2347 for the Haifa scheduler. */
2348 static const struct sched_deps_info_def rgn_const_sched_deps_info
=
2350 compute_jump_reg_dependencies
,
2351 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
2355 /* Same as above, but for the selective scheduler. */
2356 static const struct sched_deps_info_def rgn_const_sel_sched_deps_info
=
2358 compute_jump_reg_dependencies
,
2359 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
2363 /* Return true if scheduling INSN will trigger finish of scheduling
2366 rgn_insn_finishes_block_p (rtx insn
)
2368 if (INSN_BB (insn
) == target_bb
2369 && sched_target_n_insns
+ 1 == target_n_insns
)
2370 /* INSN is the last not-scheduled instruction in the current block. */
2376 /* Used in schedule_insns to initialize current_sched_info for scheduling
2377 regions (or single basic blocks). */
2379 static const struct haifa_sched_info rgn_const_sched_info
=
2382 can_schedule_ready_p
,
2387 contributes_to_priority
,
2388 rgn_insn_finishes_block_p
,
2394 rgn_add_remove_insn
,
2395 begin_schedule_ready
,
2402 /* This variable holds the data and hooks needed to the Haifa scheduler backend
2403 for the interblock scheduler frontend. */
2404 static struct haifa_sched_info rgn_sched_info
;
2406 /* Returns maximum priority that an insn was assigned to. */
2409 get_rgn_sched_max_insns_priority (void)
2411 return rgn_sched_info
.sched_max_insns_priority
;
2414 /* Determine if PAT sets a TARGET_CLASS_LIKELY_SPILLED_P register. */
2417 sets_likely_spilled (rtx pat
)
2420 note_stores (pat
, sets_likely_spilled_1
, &ret
);
2425 sets_likely_spilled_1 (rtx x
, const_rtx pat
, void *data
)
2427 bool *ret
= (bool *) data
;
2429 if (GET_CODE (pat
) == SET
2431 && HARD_REGISTER_P (x
)
2432 && targetm
.class_likely_spilled_p (REGNO_REG_CLASS (REGNO (x
))))
2436 /* A bitmap to note insns that participate in any dependency. Used in
2437 add_branch_dependences. */
2438 static sbitmap insn_referenced
;
2440 /* Add dependences so that branches are scheduled to run last in their
2443 add_branch_dependences (rtx head
, rtx tail
)
2447 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2448 that can throw exceptions, force them to remain in order at the end of
2449 the block by adding dependencies and giving the last a high priority.
2450 There may be notes present, and prev_head may also be a note.
2452 Branches must obviously remain at the end. Calls should remain at the
2453 end since moving them results in worse register allocation. Uses remain
2454 at the end to ensure proper register allocation.
2456 cc0 setters remain at the end because they can't be moved away from
2459 Predecessors of SCHED_GROUP_P instructions at the end remain at the end.
2461 COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
2463 Insns setting TARGET_CLASS_LIKELY_SPILLED_P registers (usually return
2464 values) are not moved before reload because we can wind up with register
2465 allocation failures. */
2467 while (tail
!= head
&& DEBUG_INSN_P (tail
))
2468 tail
= PREV_INSN (tail
);
2472 while (CALL_P (insn
)
2473 || JUMP_P (insn
) || JUMP_TABLE_DATA_P (insn
)
2474 || (NONJUMP_INSN_P (insn
)
2475 && (GET_CODE (PATTERN (insn
)) == USE
2476 || GET_CODE (PATTERN (insn
)) == CLOBBER
2477 || can_throw_internal (insn
)
2479 || sets_cc0_p (PATTERN (insn
))
2481 || (!reload_completed
2482 && sets_likely_spilled (PATTERN (insn
)))))
2484 || (last
!= 0 && SCHED_GROUP_P (last
)))
2489 && sd_find_dep_between (insn
, last
, false) == NULL
)
2491 if (! sched_insns_conditions_mutex_p (last
, insn
))
2492 add_dependence (last
, insn
, REG_DEP_ANTI
);
2493 bitmap_set_bit (insn_referenced
, INSN_LUID (insn
));
2496 CANT_MOVE (insn
) = 1;
2501 /* Don't overrun the bounds of the basic block. */
2506 insn
= PREV_INSN (insn
);
2507 while (insn
!= head
&& DEBUG_INSN_P (insn
));
2510 /* Make sure these insns are scheduled last in their block. */
2513 while (insn
!= head
)
2515 insn
= prev_nonnote_insn (insn
);
2517 if (bitmap_bit_p (insn_referenced
, INSN_LUID (insn
))
2518 || DEBUG_INSN_P (insn
))
2521 if (! sched_insns_conditions_mutex_p (last
, insn
))
2522 add_dependence (last
, insn
, REG_DEP_ANTI
);
2525 if (!targetm
.have_conditional_execution ())
2528 /* Finally, if the block ends in a jump, and we are doing intra-block
2529 scheduling, make sure that the branch depends on any COND_EXEC insns
2530 inside the block to avoid moving the COND_EXECs past the branch insn.
2532 We only have to do this after reload, because (1) before reload there
2533 are no COND_EXEC insns, and (2) the region scheduler is an intra-block
2534 scheduler after reload.
2536 FIXME: We could in some cases move COND_EXEC insns past the branch if
2537 this scheduler would be a little smarter. Consider this code:
2545 On a target with a one cycle stall on a memory access the optimal
2554 We don't want to put the 'X += 12' before the branch because it just
2555 wastes a cycle of execution time when the branch is taken.
2557 Note that in the example "!C" will always be true. That is another
2558 possible improvement for handling COND_EXECs in this scheduler: it
2559 could remove always-true predicates. */
2561 if (!reload_completed
|| ! (JUMP_P (tail
) || JUMP_TABLE_DATA_P (tail
)))
2565 while (insn
!= head
)
2567 insn
= PREV_INSN (insn
);
2569 /* Note that we want to add this dependency even when
2570 sched_insns_conditions_mutex_p returns true. The whole point
2571 is that we _want_ this dependency, even if these insns really
2573 if (INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == COND_EXEC
)
2574 add_dependence (tail
, insn
, REG_DEP_ANTI
);
2578 /* Data structures for the computation of data dependences in a regions. We
2579 keep one `deps' structure for every basic block. Before analyzing the
2580 data dependences for a bb, its variables are initialized as a function of
2581 the variables of its predecessors. When the analysis for a bb completes,
2582 we save the contents to the corresponding bb_deps[bb] variable. */
2584 static struct deps_desc
*bb_deps
;
2587 concat_insn_mem_list (rtx copy_insns
, rtx copy_mems
, rtx
*old_insns_p
,
2590 rtx new_insns
= *old_insns_p
;
2591 rtx new_mems
= *old_mems_p
;
2595 new_insns
= alloc_INSN_LIST (XEXP (copy_insns
, 0), new_insns
);
2596 new_mems
= alloc_EXPR_LIST (VOIDmode
, XEXP (copy_mems
, 0), new_mems
);
2597 copy_insns
= XEXP (copy_insns
, 1);
2598 copy_mems
= XEXP (copy_mems
, 1);
2601 *old_insns_p
= new_insns
;
2602 *old_mems_p
= new_mems
;
2605 /* Join PRED_DEPS to the SUCC_DEPS. */
2607 deps_join (struct deps_desc
*succ_deps
, struct deps_desc
*pred_deps
)
2610 reg_set_iterator rsi
;
2612 /* The reg_last lists are inherited by successor. */
2613 EXECUTE_IF_SET_IN_REG_SET (&pred_deps
->reg_last_in_use
, 0, reg
, rsi
)
2615 struct deps_reg
*pred_rl
= &pred_deps
->reg_last
[reg
];
2616 struct deps_reg
*succ_rl
= &succ_deps
->reg_last
[reg
];
2618 succ_rl
->uses
= concat_INSN_LIST (pred_rl
->uses
, succ_rl
->uses
);
2619 succ_rl
->sets
= concat_INSN_LIST (pred_rl
->sets
, succ_rl
->sets
);
2620 succ_rl
->implicit_sets
2621 = concat_INSN_LIST (pred_rl
->implicit_sets
, succ_rl
->implicit_sets
);
2622 succ_rl
->clobbers
= concat_INSN_LIST (pred_rl
->clobbers
,
2624 succ_rl
->uses_length
+= pred_rl
->uses_length
;
2625 succ_rl
->clobbers_length
+= pred_rl
->clobbers_length
;
2627 IOR_REG_SET (&succ_deps
->reg_last_in_use
, &pred_deps
->reg_last_in_use
);
2629 /* Mem read/write lists are inherited by successor. */
2630 concat_insn_mem_list (pred_deps
->pending_read_insns
,
2631 pred_deps
->pending_read_mems
,
2632 &succ_deps
->pending_read_insns
,
2633 &succ_deps
->pending_read_mems
);
2634 concat_insn_mem_list (pred_deps
->pending_write_insns
,
2635 pred_deps
->pending_write_mems
,
2636 &succ_deps
->pending_write_insns
,
2637 &succ_deps
->pending_write_mems
);
2639 succ_deps
->pending_jump_insns
2640 = concat_INSN_LIST (pred_deps
->pending_jump_insns
,
2641 succ_deps
->pending_jump_insns
);
2642 succ_deps
->last_pending_memory_flush
2643 = concat_INSN_LIST (pred_deps
->last_pending_memory_flush
,
2644 succ_deps
->last_pending_memory_flush
);
2646 succ_deps
->pending_read_list_length
+= pred_deps
->pending_read_list_length
;
2647 succ_deps
->pending_write_list_length
+= pred_deps
->pending_write_list_length
;
2648 succ_deps
->pending_flush_length
+= pred_deps
->pending_flush_length
;
2650 /* last_function_call is inherited by successor. */
2651 succ_deps
->last_function_call
2652 = concat_INSN_LIST (pred_deps
->last_function_call
,
2653 succ_deps
->last_function_call
);
2655 /* last_function_call_may_noreturn is inherited by successor. */
2656 succ_deps
->last_function_call_may_noreturn
2657 = concat_INSN_LIST (pred_deps
->last_function_call_may_noreturn
,
2658 succ_deps
->last_function_call_may_noreturn
);
2660 /* sched_before_next_call is inherited by successor. */
2661 succ_deps
->sched_before_next_call
2662 = concat_INSN_LIST (pred_deps
->sched_before_next_call
,
2663 succ_deps
->sched_before_next_call
);
2666 /* After computing the dependencies for block BB, propagate the dependencies
2667 found in TMP_DEPS to the successors of the block. */
2669 propagate_deps (int bb
, struct deps_desc
*pred_deps
)
2671 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (bb
));
2675 /* bb's structures are inherited by its successors. */
2676 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2678 /* Only bbs "below" bb, in the same region, are interesting. */
2679 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2680 || CONTAINING_RGN (block
->index
) != CONTAINING_RGN (e
->dest
->index
)
2681 || BLOCK_TO_BB (e
->dest
->index
) <= bb
)
2684 deps_join (bb_deps
+ BLOCK_TO_BB (e
->dest
->index
), pred_deps
);
2687 /* These lists should point to the right place, for correct
2689 bb_deps
[bb
].pending_read_insns
= pred_deps
->pending_read_insns
;
2690 bb_deps
[bb
].pending_read_mems
= pred_deps
->pending_read_mems
;
2691 bb_deps
[bb
].pending_write_insns
= pred_deps
->pending_write_insns
;
2692 bb_deps
[bb
].pending_write_mems
= pred_deps
->pending_write_mems
;
2693 bb_deps
[bb
].pending_jump_insns
= pred_deps
->pending_jump_insns
;
2695 /* Can't allow these to be freed twice. */
2696 pred_deps
->pending_read_insns
= 0;
2697 pred_deps
->pending_read_mems
= 0;
2698 pred_deps
->pending_write_insns
= 0;
2699 pred_deps
->pending_write_mems
= 0;
2700 pred_deps
->pending_jump_insns
= 0;
2703 /* Compute dependences inside bb. In a multiple blocks region:
2704 (1) a bb is analyzed after its predecessors, and (2) the lists in
2705 effect at the end of bb (after analyzing for bb) are inherited by
2708 Specifically for reg-reg data dependences, the block insns are
2709 scanned by sched_analyze () top-to-bottom. Three lists are
2710 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2711 reg_last[].implicit_sets for implicit hard register DEFs, and
2712 reg_last[].uses for register USEs.
2714 When analysis is completed for bb, we update for its successors:
2715 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2716 ; - IMPLICIT_DEFS[succ] = Union (IMPLICIT_DEFS [succ], IMPLICIT_DEFS [bb])
2717 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2719 The mechanism for computing mem-mem data dependence is very
2720 similar, and the result is interblock dependences in the region. */
2723 compute_block_dependences (int bb
)
2726 struct deps_desc tmp_deps
;
2728 tmp_deps
= bb_deps
[bb
];
2730 /* Do the analysis for this block. */
2731 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2732 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2734 sched_analyze (&tmp_deps
, head
, tail
);
2736 /* Selective scheduling handles control dependencies by itself. */
2737 if (!sel_sched_p ())
2738 add_branch_dependences (head
, tail
);
2740 if (current_nr_blocks
> 1)
2741 propagate_deps (bb
, &tmp_deps
);
2743 /* Free up the INSN_LISTs. */
2744 free_deps (&tmp_deps
);
2746 if (targetm
.sched
.dependencies_evaluation_hook
)
2747 targetm
.sched
.dependencies_evaluation_hook (head
, tail
);
2750 /* Free dependencies of instructions inside BB. */
2752 free_block_dependencies (int bb
)
2757 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2759 if (no_real_insns_p (head
, tail
))
2762 sched_free_deps (head
, tail
, true);
2765 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2766 them to the unused_*_list variables, so that they can be reused. */
2769 free_pending_lists (void)
2773 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2775 free_INSN_LIST_list (&bb_deps
[bb
].pending_read_insns
);
2776 free_INSN_LIST_list (&bb_deps
[bb
].pending_write_insns
);
2777 free_EXPR_LIST_list (&bb_deps
[bb
].pending_read_mems
);
2778 free_EXPR_LIST_list (&bb_deps
[bb
].pending_write_mems
);
2779 free_INSN_LIST_list (&bb_deps
[bb
].pending_jump_insns
);
2783 /* Print dependences for debugging starting from FROM_BB.
2784 Callable from debugger. */
2785 /* Print dependences for debugging starting from FROM_BB.
2786 Callable from debugger. */
2788 debug_rgn_dependencies (int from_bb
)
2792 fprintf (sched_dump
,
2793 ";; --------------- forward dependences: ------------ \n");
2795 for (bb
= from_bb
; bb
< current_nr_blocks
; bb
++)
2799 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2800 fprintf (sched_dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
2801 BB_TO_BLOCK (bb
), bb
);
2803 debug_dependencies (head
, tail
);
2807 /* Print dependencies information for instructions between HEAD and TAIL.
2808 ??? This function would probably fit best in haifa-sched.c. */
2809 void debug_dependencies (rtx head
, rtx tail
)
2812 rtx next_tail
= NEXT_INSN (tail
);
2814 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2815 "insn", "code", "bb", "dep", "prio", "cost",
2817 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2818 "----", "----", "--", "---", "----", "----",
2821 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2823 if (! INSN_P (insn
))
2826 fprintf (sched_dump
, ";; %6d ", INSN_UID (insn
));
2829 n
= NOTE_KIND (insn
);
2830 fprintf (sched_dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
2833 fprintf (sched_dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
2837 fprintf (sched_dump
,
2838 ";; %s%5d%6d%6d%6d%6d%6d ",
2839 (SCHED_GROUP_P (insn
) ? "+" : " "),
2843 sched_emulate_haifa_p
? -1 : sd_lists_size (insn
, SD_LIST_BACK
),
2844 (sel_sched_p () ? (sched_emulate_haifa_p
? -1
2845 : INSN_PRIORITY (insn
))
2846 : INSN_PRIORITY (insn
)),
2847 (sel_sched_p () ? (sched_emulate_haifa_p
? -1
2849 : insn_cost (insn
)));
2851 if (recog_memoized (insn
) < 0)
2852 fprintf (sched_dump
, "nothing");
2854 print_reservation (sched_dump
, insn
);
2856 fprintf (sched_dump
, "\t: ");
2858 sd_iterator_def sd_it
;
2861 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
2862 fprintf (sched_dump
, "%d%s%s ", INSN_UID (DEP_CON (dep
)),
2863 DEP_NONREG (dep
) ? "n" : "",
2864 DEP_MULTIPLE (dep
) ? "m" : "");
2866 fprintf (sched_dump
, "\n");
2869 fprintf (sched_dump
, "\n");
2872 /* Returns true if all the basic blocks of the current region have
2873 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
2875 sched_is_disabled_for_current_region_p (void)
2879 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2880 if (!(BASIC_BLOCK_FOR_FN (cfun
,
2881 BB_TO_BLOCK (bb
))->flags
& BB_DISABLE_SCHEDULE
))
2887 /* Free all region dependencies saved in INSN_BACK_DEPS and
2888 INSN_RESOLVED_BACK_DEPS. The Haifa scheduler does this on the fly
2889 when scheduling, so this function is supposed to be called from
2890 the selective scheduling only. */
2892 free_rgn_deps (void)
2896 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2900 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2901 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2903 sched_free_deps (head
, tail
, false);
2907 static int rgn_n_insns
;
2909 /* Compute insn priority for a current region. */
2911 compute_priorities (void)
2915 current_sched_info
->sched_max_insns_priority
= 0;
2916 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2920 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2921 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2923 if (no_real_insns_p (head
, tail
))
2926 rgn_n_insns
+= set_priorities (head
, tail
);
2928 current_sched_info
->sched_max_insns_priority
++;
2931 /* (Re-)initialize the arrays of DFA states at the end of each basic block.
2933 SAVED_LAST_BASIC_BLOCK is the previous length of the arrays. It must be
2934 zero for the first call to this function, to allocate the arrays for the
2937 This function is called once during initialization of the scheduler, and
2938 called again to resize the arrays if new basic blocks have been created,
2939 for example for speculation recovery code. */
2942 realloc_bb_state_array (int saved_last_basic_block
)
2944 char *old_bb_state_array
= bb_state_array
;
2945 size_t lbb
= (size_t) last_basic_block_for_fn (cfun
);
2946 size_t slbb
= (size_t) saved_last_basic_block
;
2948 /* Nothing to do if nothing changed since the last time this was called. */
2949 if (saved_last_basic_block
== last_basic_block_for_fn (cfun
))
2952 /* The selective scheduler doesn't use the state arrays. */
2955 gcc_assert (bb_state_array
== NULL
&& bb_state
== NULL
);
2959 gcc_checking_assert (saved_last_basic_block
== 0
2960 || (bb_state_array
!= NULL
&& bb_state
!= NULL
));
2962 bb_state_array
= XRESIZEVEC (char, bb_state_array
, lbb
* dfa_state_size
);
2963 bb_state
= XRESIZEVEC (state_t
, bb_state
, lbb
);
2965 /* If BB_STATE_ARRAY has moved, fixup all the state pointers array.
2966 Otherwise only fixup the newly allocated ones. For the state
2967 array itself, only initialize the new entries. */
2968 bool bb_state_array_moved
= (bb_state_array
!= old_bb_state_array
);
2969 for (size_t i
= bb_state_array_moved
? 0 : slbb
; i
< lbb
; i
++)
2970 bb_state
[i
] = (state_t
) (bb_state_array
+ i
* dfa_state_size
);
2971 for (size_t i
= slbb
; i
< lbb
; i
++)
2972 state_reset (bb_state
[i
]);
2975 /* Free the arrays of DFA states at the end of each basic block. */
2978 free_bb_state_array (void)
2980 free (bb_state_array
);
2982 bb_state_array
= NULL
;
2986 /* Schedule a region. A region is either an inner loop, a loop-free
2987 subroutine, or a single basic block. Each bb in the region is
2988 scheduled after its flow predecessors. */
2991 schedule_region (int rgn
)
2994 int sched_rgn_n_insns
= 0;
2998 /* Do not support register pressure sensitive scheduling for the new regions
2999 as we don't update the liveness info for them. */
3000 if (rgn
>= nr_regions_initial
)
3002 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
3003 free_global_sched_pressure_data ();
3004 sched_pressure
= SCHED_PRESSURE_NONE
;
3007 rgn_setup_region (rgn
);
3009 /* Don't schedule region that is marked by
3010 NOTE_DISABLE_SCHED_OF_BLOCK. */
3011 if (sched_is_disabled_for_current_region_p ())
3014 sched_rgn_compute_dependencies (rgn
);
3016 sched_rgn_local_init (rgn
);
3018 /* Set priorities. */
3019 compute_priorities ();
3021 sched_extend_ready_list (rgn_n_insns
);
3023 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
3025 sched_init_region_reg_pressure_info ();
3026 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3028 basic_block first_bb
, last_bb
;
3031 first_bb
= EBB_FIRST_BB (bb
);
3032 last_bb
= EBB_LAST_BB (bb
);
3034 get_ebb_head_tail (first_bb
, last_bb
, &head
, &tail
);
3036 if (no_real_insns_p (head
, tail
))
3038 gcc_assert (first_bb
== last_bb
);
3041 sched_setup_bb_reg_pressure_info (first_bb
, PREV_INSN (head
));
3045 /* Now we can schedule all blocks. */
3046 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3048 basic_block first_bb
, last_bb
, curr_bb
;
3051 first_bb
= EBB_FIRST_BB (bb
);
3052 last_bb
= EBB_LAST_BB (bb
);
3054 get_ebb_head_tail (first_bb
, last_bb
, &head
, &tail
);
3056 if (no_real_insns_p (head
, tail
))
3058 gcc_assert (first_bb
== last_bb
);
3062 current_sched_info
->prev_head
= PREV_INSN (head
);
3063 current_sched_info
->next_tail
= NEXT_INSN (tail
);
3065 remove_notes (head
, tail
);
3067 unlink_bb_notes (first_bb
, last_bb
);
3071 gcc_assert (flag_schedule_interblock
|| current_nr_blocks
== 1);
3072 current_sched_info
->queue_must_finish_empty
= current_nr_blocks
== 1;
3075 if (dbg_cnt (sched_block
))
3078 int saved_last_basic_block
= last_basic_block_for_fn (cfun
);
3080 schedule_block (&curr_bb
, bb_state
[first_bb
->index
]);
3081 gcc_assert (EBB_FIRST_BB (bb
) == first_bb
);
3082 sched_rgn_n_insns
+= sched_n_insns
;
3083 realloc_bb_state_array (saved_last_basic_block
);
3084 f
= find_fallthru_edge (last_bb
->succs
);
3085 if (f
&& f
->probability
* 100 / REG_BR_PROB_BASE
>=
3086 PARAM_VALUE (PARAM_SCHED_STATE_EDGE_PROB_CUTOFF
))
3088 memcpy (bb_state
[f
->dest
->index
], curr_state
,
3090 if (sched_verbose
>= 5)
3091 fprintf (sched_dump
, "saving state for edge %d->%d\n",
3092 f
->src
->index
, f
->dest
->index
);
3097 sched_rgn_n_insns
+= rgn_n_insns
;
3101 if (current_nr_blocks
> 1)
3105 /* Sanity check: verify that all region insns were scheduled. */
3106 gcc_assert (sched_rgn_n_insns
== rgn_n_insns
);
3108 sched_finish_ready_list ();
3110 /* Done with this region. */
3111 sched_rgn_local_finish ();
3113 /* Free dependencies. */
3114 for (bb
= 0; bb
< current_nr_blocks
; ++bb
)
3115 free_block_dependencies (bb
);
3117 gcc_assert (haifa_recovery_bb_ever_added_p
3118 || deps_pools_are_empty_p ());
3121 /* Initialize data structures for region scheduling. */
3124 sched_rgn_init (bool single_blocks_p
)
3126 min_spec_prob
= ((PARAM_VALUE (PARAM_MIN_SPEC_PROB
) * REG_BR_PROB_BASE
)
3134 CONTAINING_RGN (ENTRY_BLOCK
) = -1;
3135 CONTAINING_RGN (EXIT_BLOCK
) = -1;
3137 realloc_bb_state_array (0);
3139 /* Compute regions for scheduling. */
3141 || n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
+ 1
3142 || !flag_schedule_interblock
3143 || is_cfg_nonregular ())
3145 find_single_block_region (sel_sched_p ());
3149 /* Compute the dominators and post dominators. */
3150 if (!sel_sched_p ())
3151 calculate_dominance_info (CDI_DOMINATORS
);
3156 if (sched_verbose
>= 3)
3159 /* For now. This will move as more and more of haifa is converted
3160 to using the cfg code. */
3161 if (!sel_sched_p ())
3162 free_dominance_info (CDI_DOMINATORS
);
3165 gcc_assert (0 < nr_regions
&& nr_regions
<= n_basic_blocks_for_fn (cfun
));
3167 RGN_BLOCKS (nr_regions
) = (RGN_BLOCKS (nr_regions
- 1) +
3168 RGN_NR_BLOCKS (nr_regions
- 1));
3171 /* Free data structures for region scheduling. */
3173 sched_rgn_finish (void)
3175 free_bb_state_array ();
3177 /* Reposition the prologue and epilogue notes in case we moved the
3178 prologue/epilogue insns. */
3179 if (reload_completed
)
3180 reposition_prologue_and_epilogue_notes ();
3184 if (reload_completed
== 0
3185 && flag_schedule_interblock
)
3187 fprintf (sched_dump
,
3188 "\n;; Procedure interblock/speculative motions == %d/%d \n",
3192 gcc_assert (nr_inter
<= 0);
3193 fprintf (sched_dump
, "\n\n");
3201 free (rgn_bb_table
);
3202 rgn_bb_table
= NULL
;
3207 free (containing_rgn
);
3208 containing_rgn
= NULL
;
3214 /* Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
3215 point to the region RGN. */
3217 rgn_setup_region (int rgn
)
3221 /* Set variables for the current region. */
3222 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
3223 current_blocks
= RGN_BLOCKS (rgn
);
3225 /* EBB_HEAD is a region-scope structure. But we realloc it for
3226 each region to save time/memory/something else.
3227 See comments in add_block1, for what reasons we allocate +1 element. */
3228 ebb_head
= XRESIZEVEC (int, ebb_head
, current_nr_blocks
+ 1);
3229 for (bb
= 0; bb
<= current_nr_blocks
; bb
++)
3230 ebb_head
[bb
] = current_blocks
+ bb
;
3233 /* Compute instruction dependencies in region RGN. */
3235 sched_rgn_compute_dependencies (int rgn
)
3237 if (!RGN_DONT_CALC_DEPS (rgn
))
3242 sched_emulate_haifa_p
= 1;
3244 init_deps_global ();
3246 /* Initializations for region data dependence analysis. */
3247 bb_deps
= XNEWVEC (struct deps_desc
, current_nr_blocks
);
3248 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3249 init_deps (bb_deps
+ bb
, false);
3251 /* Initialize bitmap used in add_branch_dependences. */
3252 insn_referenced
= sbitmap_alloc (sched_max_luid
);
3253 bitmap_clear (insn_referenced
);
3255 /* Compute backward dependencies. */
3256 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3257 compute_block_dependences (bb
);
3259 sbitmap_free (insn_referenced
);
3260 free_pending_lists ();
3261 finish_deps_global ();
3264 /* We don't want to recalculate this twice. */
3265 RGN_DONT_CALC_DEPS (rgn
) = 1;
3268 sched_emulate_haifa_p
= 0;
3271 /* (This is a recovery block. It is always a single block region.)
3272 OR (We use selective scheduling.) */
3273 gcc_assert (current_nr_blocks
== 1 || sel_sched_p ());
3276 /* Init region data structures. Returns true if this region should
3277 not be scheduled. */
3279 sched_rgn_local_init (int rgn
)
3283 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
3284 if (current_nr_blocks
> 1)
3290 prob
= XNEWVEC (int, current_nr_blocks
);
3292 dom
= sbitmap_vector_alloc (current_nr_blocks
, current_nr_blocks
);
3293 bitmap_vector_clear (dom
, current_nr_blocks
);
3295 /* Use ->aux to implement EDGE_TO_BIT mapping. */
3297 FOR_EACH_BB_FN (block
, cfun
)
3299 if (CONTAINING_RGN (block
->index
) != rgn
)
3301 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3302 SET_EDGE_TO_BIT (e
, rgn_nr_edges
++);
3305 rgn_edges
= XNEWVEC (edge
, rgn_nr_edges
);
3307 FOR_EACH_BB_FN (block
, cfun
)
3309 if (CONTAINING_RGN (block
->index
) != rgn
)
3311 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3312 rgn_edges
[rgn_nr_edges
++] = e
;
3316 pot_split
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
3317 bitmap_vector_clear (pot_split
, current_nr_blocks
);
3318 ancestor_edges
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
3319 bitmap_vector_clear (ancestor_edges
, current_nr_blocks
);
3321 /* Compute probabilities, dominators, split_edges. */
3322 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3323 compute_dom_prob_ps (bb
);
3325 /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
3326 /* We don't need them anymore. But we want to avoid duplication of
3327 aux fields in the newly created edges. */
3328 FOR_EACH_BB_FN (block
, cfun
)
3330 if (CONTAINING_RGN (block
->index
) != rgn
)
3332 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3338 /* Free data computed for the finished region. */
3340 sched_rgn_local_free (void)
3343 sbitmap_vector_free (dom
);
3344 sbitmap_vector_free (pot_split
);
3345 sbitmap_vector_free (ancestor_edges
);
3349 /* Free data computed for the finished region. */
3351 sched_rgn_local_finish (void)
3353 if (current_nr_blocks
> 1 && !sel_sched_p ())
3355 sched_rgn_local_free ();
3359 /* Setup scheduler infos. */
3361 rgn_setup_common_sched_info (void)
3363 memcpy (&rgn_common_sched_info
, &haifa_common_sched_info
,
3364 sizeof (rgn_common_sched_info
));
3366 rgn_common_sched_info
.fix_recovery_cfg
= rgn_fix_recovery_cfg
;
3367 rgn_common_sched_info
.add_block
= rgn_add_block
;
3368 rgn_common_sched_info
.estimate_number_of_insns
3369 = rgn_estimate_number_of_insns
;
3370 rgn_common_sched_info
.sched_pass_id
= SCHED_RGN_PASS
;
3372 common_sched_info
= &rgn_common_sched_info
;
3375 /* Setup all *_sched_info structures (for the Haifa frontend
3376 and for the dependence analysis) in the interblock scheduler. */
3378 rgn_setup_sched_infos (void)
3380 if (!sel_sched_p ())
3381 memcpy (&rgn_sched_deps_info
, &rgn_const_sched_deps_info
,
3382 sizeof (rgn_sched_deps_info
));
3384 memcpy (&rgn_sched_deps_info
, &rgn_const_sel_sched_deps_info
,
3385 sizeof (rgn_sched_deps_info
));
3387 sched_deps_info
= &rgn_sched_deps_info
;
3389 memcpy (&rgn_sched_info
, &rgn_const_sched_info
, sizeof (rgn_sched_info
));
3390 current_sched_info
= &rgn_sched_info
;
3393 /* The one entry point in this file. */
3395 schedule_insns (void)
3399 /* Taking care of this degenerate case makes the rest of
3400 this code simpler. */
3401 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
3404 rgn_setup_common_sched_info ();
3405 rgn_setup_sched_infos ();
3407 haifa_sched_init ();
3408 sched_rgn_init (reload_completed
);
3410 bitmap_initialize (¬_in_df
, 0);
3411 bitmap_clear (¬_in_df
);
3413 /* Schedule every region in the subroutine. */
3414 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
3415 if (dbg_cnt (sched_region
))
3416 schedule_region (rgn
);
3419 sched_rgn_finish ();
3420 bitmap_clear (¬_in_df
);
3422 haifa_sched_finish ();
3425 /* INSN has been added to/removed from current region. */
3427 rgn_add_remove_insn (rtx insn
, int remove_p
)
3434 if (INSN_BB (insn
) == target_bb
)
3443 /* Extend internal data structures. */
3445 extend_regions (void)
3447 rgn_table
= XRESIZEVEC (region
, rgn_table
, n_basic_blocks_for_fn (cfun
));
3448 rgn_bb_table
= XRESIZEVEC (int, rgn_bb_table
,
3449 n_basic_blocks_for_fn (cfun
));
3450 block_to_bb
= XRESIZEVEC (int, block_to_bb
,
3451 last_basic_block_for_fn (cfun
));
3452 containing_rgn
= XRESIZEVEC (int, containing_rgn
,
3453 last_basic_block_for_fn (cfun
));
3457 rgn_make_new_region_out_of_new_block (basic_block bb
)
3461 i
= RGN_BLOCKS (nr_regions
);
3462 /* I - first free position in rgn_bb_table. */
3464 rgn_bb_table
[i
] = bb
->index
;
3465 RGN_NR_BLOCKS (nr_regions
) = 1;
3466 RGN_HAS_REAL_EBB (nr_regions
) = 0;
3467 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
3468 CONTAINING_RGN (bb
->index
) = nr_regions
;
3469 BLOCK_TO_BB (bb
->index
) = 0;
3473 RGN_BLOCKS (nr_regions
) = i
+ 1;
3476 /* BB was added to ebb after AFTER. */
3478 rgn_add_block (basic_block bb
, basic_block after
)
3481 bitmap_set_bit (¬_in_df
, bb
->index
);
3483 if (after
== 0 || after
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3485 rgn_make_new_region_out_of_new_block (bb
);
3486 RGN_DONT_CALC_DEPS (nr_regions
- 1) = (after
3487 == EXIT_BLOCK_PTR_FOR_FN (cfun
));
3493 /* We need to fix rgn_table, block_to_bb, containing_rgn
3496 BLOCK_TO_BB (bb
->index
) = BLOCK_TO_BB (after
->index
);
3498 /* We extend ebb_head to one more position to
3499 easily find the last position of the last ebb in
3500 the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
3501 is _always_ valid for access. */
3503 i
= BLOCK_TO_BB (after
->index
) + 1;
3504 pos
= ebb_head
[i
] - 1;
3505 /* Now POS is the index of the last block in the region. */
3507 /* Find index of basic block AFTER. */
3508 for (; rgn_bb_table
[pos
] != after
->index
; pos
--)
3512 gcc_assert (pos
> ebb_head
[i
- 1]);
3514 /* i - ebb right after "AFTER". */
3515 /* ebb_head[i] - VALID. */
3517 /* Source position: ebb_head[i]
3518 Destination position: ebb_head[i] + 1
3520 RGN_BLOCKS (nr_regions) - 1
3521 Number of elements to copy: (last_position) - (source_position) + 1
3524 memmove (rgn_bb_table
+ pos
+ 1,
3526 ((RGN_BLOCKS (nr_regions
) - 1) - (pos
) + 1)
3527 * sizeof (*rgn_bb_table
));
3529 rgn_bb_table
[pos
] = bb
->index
;
3531 for (; i
<= current_nr_blocks
; i
++)
3534 i
= CONTAINING_RGN (after
->index
);
3535 CONTAINING_RGN (bb
->index
) = i
;
3537 RGN_HAS_REAL_EBB (i
) = 1;
3539 for (++i
; i
<= nr_regions
; i
++)
3544 /* Fix internal data after interblock movement of jump instruction.
3545 For parameter meaning please refer to
3546 sched-int.h: struct sched_info: fix_recovery_cfg. */
3548 rgn_fix_recovery_cfg (int bbi
, int check_bbi
, int check_bb_nexti
)
3550 int old_pos
, new_pos
, i
;
3552 BLOCK_TO_BB (check_bb_nexti
) = BLOCK_TO_BB (bbi
);
3554 for (old_pos
= ebb_head
[BLOCK_TO_BB (check_bbi
) + 1] - 1;
3555 rgn_bb_table
[old_pos
] != check_bb_nexti
;
3558 gcc_assert (old_pos
> ebb_head
[BLOCK_TO_BB (check_bbi
)]);
3560 for (new_pos
= ebb_head
[BLOCK_TO_BB (bbi
) + 1] - 1;
3561 rgn_bb_table
[new_pos
] != bbi
;
3565 gcc_assert (new_pos
> ebb_head
[BLOCK_TO_BB (bbi
)]);
3567 gcc_assert (new_pos
< old_pos
);
3569 memmove (rgn_bb_table
+ new_pos
+ 1,
3570 rgn_bb_table
+ new_pos
,
3571 (old_pos
- new_pos
) * sizeof (*rgn_bb_table
));
3573 rgn_bb_table
[new_pos
] = check_bb_nexti
;
3575 for (i
= BLOCK_TO_BB (bbi
) + 1; i
<= BLOCK_TO_BB (check_bbi
); i
++)
3579 /* Return next block in ebb chain. For parameter meaning please refer to
3580 sched-int.h: struct sched_info: advance_target_bb. */
3582 advance_target_bb (basic_block bb
, rtx insn
)
3587 gcc_assert (BLOCK_TO_BB (bb
->index
) == target_bb
3588 && BLOCK_TO_BB (bb
->next_bb
->index
) == target_bb
);
3595 gate_handle_live_range_shrinkage (void)
3597 #ifdef INSN_SCHEDULING
3598 return flag_live_range_shrinkage
;
3604 /* Run instruction scheduler. */
3606 rest_of_handle_live_range_shrinkage (void)
3608 #ifdef INSN_SCHEDULING
3611 initialize_live_range_shrinkage ();
3612 saved
= flag_schedule_interblock
;
3613 flag_schedule_interblock
= false;
3615 flag_schedule_interblock
= saved
;
3616 finish_live_range_shrinkage ();
3622 gate_handle_sched (void)
3624 #ifdef INSN_SCHEDULING
3625 return optimize
> 0 && flag_schedule_insns
&& dbg_cnt (sched_func
);
3631 /* Run instruction scheduler. */
3633 rest_of_handle_sched (void)
3635 #ifdef INSN_SCHEDULING
3636 if (flag_selective_scheduling
3637 && ! maybe_skip_selective_scheduling ())
3638 run_selective_scheduling ();
3646 gate_handle_sched2 (void)
3648 #ifdef INSN_SCHEDULING
3649 return optimize
> 0 && flag_schedule_insns_after_reload
3650 && !targetm
.delay_sched2
&& dbg_cnt (sched2_func
);
3656 /* Run second scheduling pass after reload. */
3658 rest_of_handle_sched2 (void)
3660 #ifdef INSN_SCHEDULING
3661 if (flag_selective_scheduling2
3662 && ! maybe_skip_selective_scheduling ())
3663 run_selective_scheduling ();
3666 /* Do control and data sched analysis again,
3667 and write some more of the results to dump file. */
3668 if (flag_sched2_use_superblocks
)
3679 const pass_data pass_data_live_range_shrinkage
=
3681 RTL_PASS
, /* type */
3682 "lr_shrinkage", /* name */
3683 OPTGROUP_NONE
, /* optinfo_flags */
3684 true, /* has_gate */
3685 true, /* has_execute */
3686 TV_LIVE_RANGE_SHRINKAGE
, /* tv_id */
3687 0, /* properties_required */
3688 0, /* properties_provided */
3689 0, /* properties_destroyed */
3690 0, /* todo_flags_start */
3691 ( TODO_df_finish
| TODO_verify_rtl_sharing
3692 | TODO_verify_flow
), /* todo_flags_finish */
3695 class pass_live_range_shrinkage
: public rtl_opt_pass
3698 pass_live_range_shrinkage(gcc::context
*ctxt
)
3699 : rtl_opt_pass(pass_data_live_range_shrinkage
, ctxt
)
3702 /* opt_pass methods: */
3703 bool gate () { return gate_handle_live_range_shrinkage (); }
3704 unsigned int execute () { return rest_of_handle_live_range_shrinkage (); }
3706 }; // class pass_live_range_shrinkage
3711 make_pass_live_range_shrinkage (gcc::context
*ctxt
)
3713 return new pass_live_range_shrinkage (ctxt
);
3718 const pass_data pass_data_sched
=
3720 RTL_PASS
, /* type */
3721 "sched1", /* name */
3722 OPTGROUP_NONE
, /* optinfo_flags */
3723 true, /* has_gate */
3724 true, /* has_execute */
3725 TV_SCHED
, /* tv_id */
3726 0, /* properties_required */
3727 0, /* properties_provided */
3728 0, /* properties_destroyed */
3729 0, /* todo_flags_start */
3730 ( TODO_df_finish
| TODO_verify_rtl_sharing
3731 | TODO_verify_flow
), /* todo_flags_finish */
3734 class pass_sched
: public rtl_opt_pass
3737 pass_sched (gcc::context
*ctxt
)
3738 : rtl_opt_pass (pass_data_sched
, ctxt
)
3741 /* opt_pass methods: */
3742 bool gate () { return gate_handle_sched (); }
3743 unsigned int execute () { return rest_of_handle_sched (); }
3745 }; // class pass_sched
3750 make_pass_sched (gcc::context
*ctxt
)
3752 return new pass_sched (ctxt
);
3757 const pass_data pass_data_sched2
=
3759 RTL_PASS
, /* type */
3760 "sched2", /* name */
3761 OPTGROUP_NONE
, /* optinfo_flags */
3762 true, /* has_gate */
3763 true, /* has_execute */
3764 TV_SCHED2
, /* tv_id */
3765 0, /* properties_required */
3766 0, /* properties_provided */
3767 0, /* properties_destroyed */
3768 0, /* todo_flags_start */
3769 ( TODO_df_finish
| TODO_verify_rtl_sharing
3770 | TODO_verify_flow
), /* todo_flags_finish */
3773 class pass_sched2
: public rtl_opt_pass
3776 pass_sched2 (gcc::context
*ctxt
)
3777 : rtl_opt_pass (pass_data_sched2
, ctxt
)
3780 /* opt_pass methods: */
3781 bool gate () { return gate_handle_sched2 (); }
3782 unsigned int execute () { return rest_of_handle_sched2 (); }
3784 }; // class pass_sched2
3789 make_pass_sched2 (gcc::context
*ctxt
)
3791 return new pass_sched2 (ctxt
);