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_insn
*, rtx_insn
*);
240 static void compute_block_dependences (int);
242 static void schedule_region (int);
243 static void concat_insn_mem_list (rtx_insn_list
*, rtx_expr_list
*,
244 rtx_insn_list
**, rtx_expr_list
**);
245 static void propagate_deps (int, struct deps_desc
*);
246 static void free_pending_lists (void);
248 /* Functions for construction of the control flow graph. */
250 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
252 We decide not to build the control flow graph if there is possibly more
253 than one entry to the function, if computed branches exist, if we
254 have nonlocal gotos, or if we have an unreachable loop. */
257 is_cfg_nonregular (void)
262 /* If we have a label that could be the target of a nonlocal goto, then
263 the cfg is not well structured. */
264 if (nonlocal_goto_handler_labels
)
267 /* If we have any forced labels, then the cfg is not well structured. */
271 /* If we have exception handlers, then we consider the cfg not well
272 structured. ?!? We should be able to handle this now that we
273 compute an accurate cfg for EH. */
274 if (current_function_has_exception_handlers ())
277 /* If we have insns which refer to labels as non-jumped-to operands,
278 then we consider the cfg not well structured. */
279 FOR_EACH_BB_FN (b
, cfun
)
280 FOR_BB_INSNS (b
, insn
)
285 /* If this function has a computed jump, then we consider the cfg
286 not well structured. */
287 if (JUMP_P (insn
) && computed_jump_p (insn
))
293 note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
);
294 if (note
== NULL_RTX
)
297 /* For that label not to be seen as a referred-to label, this
298 must be a single-set which is feeding a jump *only*. This
299 could be a conditional jump with the label split off for
300 machine-specific reasons or a casesi/tablejump. */
301 next
= next_nonnote_insn (insn
);
304 || (JUMP_LABEL (next
) != XEXP (note
, 0)
305 && find_reg_note (next
, REG_LABEL_TARGET
,
306 XEXP (note
, 0)) == NULL_RTX
)
307 || BLOCK_FOR_INSN (insn
) != BLOCK_FOR_INSN (next
))
310 set
= single_set (insn
);
314 dest
= SET_DEST (set
);
315 if (!REG_P (dest
) || !dead_or_set_p (next
, dest
))
319 /* Unreachable loops with more than one basic block are detected
320 during the DFS traversal in find_rgns.
322 Unreachable loops with a single block are detected here. This
323 test is redundant with the one in find_rgns, but it's much
324 cheaper to go ahead and catch the trivial case here. */
325 FOR_EACH_BB_FN (b
, cfun
)
327 if (EDGE_COUNT (b
->preds
) == 0
328 || (single_pred_p (b
)
329 && single_pred (b
) == b
))
333 /* All the tests passed. Consider the cfg well structured. */
337 /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */
340 extract_edgelst (sbitmap set
, edgelst
*el
)
343 sbitmap_iterator sbi
;
345 /* edgelst table space is reused in each call to extract_edgelst. */
348 el
->first_member
= &edgelst_table
[edgelst_last
];
351 /* Iterate over each word in the bitset. */
352 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, sbi
)
354 edgelst_table
[edgelst_last
++] = rgn_edges
[i
];
359 /* Functions for the construction of regions. */
361 /* Print the regions, for debugging purposes. Callable from debugger. */
368 fprintf (sched_dump
, "\n;; ------------ REGIONS ----------\n\n");
369 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
371 fprintf (sched_dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
372 rgn_table
[rgn
].rgn_nr_blocks
);
373 fprintf (sched_dump
, ";;\tbb/block: ");
375 /* We don't have ebb_head initialized yet, so we can't use
377 current_blocks
= RGN_BLOCKS (rgn
);
379 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
380 fprintf (sched_dump
, " %d/%d ", bb
, rgn_bb_table
[current_blocks
+ bb
]);
382 fprintf (sched_dump
, "\n\n");
386 /* Print the region's basic blocks. */
389 debug_region (int rgn
)
393 fprintf (stderr
, "\n;; ------------ REGION %d ----------\n\n", rgn
);
394 fprintf (stderr
, ";;\trgn %d nr_blocks %d:\n", rgn
,
395 rgn_table
[rgn
].rgn_nr_blocks
);
396 fprintf (stderr
, ";;\tbb/block: ");
398 /* We don't have ebb_head initialized yet, so we can't use
400 current_blocks
= RGN_BLOCKS (rgn
);
402 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
403 fprintf (stderr
, " %d/%d ", bb
, rgn_bb_table
[current_blocks
+ bb
]);
405 fprintf (stderr
, "\n\n");
407 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
410 BASIC_BLOCK_FOR_FN (cfun
, rgn_bb_table
[current_blocks
+ bb
]),
411 0, TDF_SLIM
| TDF_BLOCKS
);
412 fprintf (stderr
, "\n");
415 fprintf (stderr
, "\n");
419 /* True when a bb with index BB_INDEX contained in region RGN. */
421 bb_in_region_p (int bb_index
, int rgn
)
425 for (i
= 0; i
< rgn_table
[rgn
].rgn_nr_blocks
; i
++)
426 if (rgn_bb_table
[current_blocks
+ i
] == bb_index
)
432 /* Dump region RGN to file F using dot syntax. */
434 dump_region_dot (FILE *f
, int rgn
)
438 fprintf (f
, "digraph Region_%d {\n", rgn
);
440 /* We don't have ebb_head initialized yet, so we can't use
442 current_blocks
= RGN_BLOCKS (rgn
);
444 for (i
= 0; i
< rgn_table
[rgn
].rgn_nr_blocks
; i
++)
448 int src_bb_num
= rgn_bb_table
[current_blocks
+ i
];
449 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, src_bb_num
);
451 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
452 if (bb_in_region_p (e
->dest
->index
, rgn
))
453 fprintf (f
, "\t%d -> %d\n", src_bb_num
, e
->dest
->index
);
458 /* The same, but first open a file specified by FNAME. */
460 dump_region_dot_file (const char *fname
, int rgn
)
462 FILE *f
= fopen (fname
, "wt");
463 dump_region_dot (f
, rgn
);
467 /* Build a single block region for each basic block in the function.
468 This allows for using the same code for interblock and basic block
472 find_single_block_region (bool ebbs_p
)
474 basic_block bb
, ebb_start
;
480 int probability_cutoff
;
481 if (profile_info
&& flag_branch_probabilities
)
482 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK
);
484 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY
);
485 probability_cutoff
= REG_BR_PROB_BASE
/ 100 * probability_cutoff
;
487 FOR_EACH_BB_FN (ebb_start
, cfun
)
489 RGN_NR_BLOCKS (nr_regions
) = 0;
490 RGN_BLOCKS (nr_regions
) = i
;
491 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
492 RGN_HAS_REAL_EBB (nr_regions
) = 0;
494 for (bb
= ebb_start
; ; bb
= bb
->next_bb
)
498 rgn_bb_table
[i
] = bb
->index
;
499 RGN_NR_BLOCKS (nr_regions
)++;
500 CONTAINING_RGN (bb
->index
) = nr_regions
;
501 BLOCK_TO_BB (bb
->index
) = i
- RGN_BLOCKS (nr_regions
);
504 if (bb
->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
505 || LABEL_P (BB_HEAD (bb
->next_bb
)))
508 e
= find_fallthru_edge (bb
->succs
);
511 if (e
->probability
<= probability_cutoff
)
520 FOR_EACH_BB_FN (bb
, cfun
)
522 rgn_bb_table
[nr_regions
] = bb
->index
;
523 RGN_NR_BLOCKS (nr_regions
) = 1;
524 RGN_BLOCKS (nr_regions
) = nr_regions
;
525 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
526 RGN_HAS_REAL_EBB (nr_regions
) = 0;
528 CONTAINING_RGN (bb
->index
) = nr_regions
;
529 BLOCK_TO_BB (bb
->index
) = 0;
534 /* Estimate number of the insns in the BB. */
536 rgn_estimate_number_of_insns (basic_block bb
)
540 count
= INSN_LUID (BB_END (bb
)) - INSN_LUID (BB_HEAD (bb
));
542 if (MAY_HAVE_DEBUG_INSNS
)
546 FOR_BB_INSNS (bb
, insn
)
547 if (DEBUG_INSN_P (insn
))
554 /* Update number of blocks and the estimate for number of insns
555 in the region. Return true if the region is "too large" for interblock
556 scheduling (compile time considerations). */
559 too_large (int block
, int *num_bbs
, int *num_insns
)
562 (*num_insns
) += (common_sched_info
->estimate_number_of_insns
563 (BASIC_BLOCK_FOR_FN (cfun
, block
)));
565 return ((*num_bbs
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS
))
566 || (*num_insns
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS
)));
569 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
570 is still an inner loop. Put in max_hdr[blk] the header of the most inner
571 loop containing blk. */
572 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
574 if (max_hdr[blk] == -1) \
575 max_hdr[blk] = hdr; \
576 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
577 bitmap_clear_bit (inner, hdr); \
578 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
580 bitmap_clear_bit (inner,max_hdr[blk]); \
581 max_hdr[blk] = hdr; \
585 /* Find regions for interblock scheduling.
587 A region for scheduling can be:
589 * A loop-free procedure, or
591 * A reducible inner loop, or
593 * A basic block not contained in any other region.
595 ?!? In theory we could build other regions based on extended basic
596 blocks or reverse extended basic blocks. Is it worth the trouble?
598 Loop blocks that form a region are put into the region's block list
599 in topological order.
601 This procedure stores its results into the following global (ick) variables
609 We use dominator relationships to avoid making regions out of non-reducible
612 This procedure needs to be converted to work on pred/succ lists instead
613 of edge tables. That would simplify it somewhat. */
616 haifa_find_rgns (void)
618 int *max_hdr
, *dfs_nr
, *degree
;
620 int node
, child
, loop_head
, i
, head
, tail
;
621 int count
= 0, sp
, idx
= 0;
622 edge_iterator current_edge
;
623 edge_iterator
*stack
;
624 int num_bbs
, num_insns
, unreachable
;
625 int too_large_failure
;
628 /* Note if a block is a natural loop header. */
631 /* Note if a block is a natural inner loop header. */
634 /* Note if a block is in the block queue. */
637 /* Note if a block is in the block queue. */
640 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
641 and a mapping from block to its loop header (if the block is contained
644 Store results in HEADER, INNER, and MAX_HDR respectively, these will
645 be used as inputs to the second traversal.
647 STACK, SP and DFS_NR are only used during the first traversal. */
649 /* Allocate and initialize variables for the first traversal. */
650 max_hdr
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
651 dfs_nr
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
652 stack
= XNEWVEC (edge_iterator
, n_edges_for_fn (cfun
));
654 inner
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
657 header
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
658 bitmap_clear (header
);
660 in_queue
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
661 bitmap_clear (in_queue
);
663 in_stack
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
664 bitmap_clear (in_stack
);
666 for (i
= 0; i
< last_basic_block_for_fn (cfun
); i
++)
669 #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
670 #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
672 /* DFS traversal to find inner loops in the cfg. */
674 current_edge
= ei_start (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->succs
);
679 if (EDGE_PASSED (current_edge
))
681 /* We have reached a leaf node or a node that was already
682 processed. Pop edges off the stack until we find
683 an edge that has not yet been processed. */
684 while (sp
>= 0 && EDGE_PASSED (current_edge
))
686 /* Pop entry off the stack. */
687 current_edge
= stack
[sp
--];
688 node
= ei_edge (current_edge
)->src
->index
;
689 gcc_assert (node
!= ENTRY_BLOCK
);
690 child
= ei_edge (current_edge
)->dest
->index
;
691 gcc_assert (child
!= EXIT_BLOCK
);
692 bitmap_clear_bit (in_stack
, child
);
693 if (max_hdr
[child
] >= 0 && bitmap_bit_p (in_stack
, max_hdr
[child
]))
694 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
695 ei_next (¤t_edge
);
698 /* See if have finished the DFS tree traversal. */
699 if (sp
< 0 && EDGE_PASSED (current_edge
))
702 /* Nope, continue the traversal with the popped node. */
706 /* Process a node. */
707 node
= ei_edge (current_edge
)->src
->index
;
708 gcc_assert (node
!= ENTRY_BLOCK
);
709 bitmap_set_bit (in_stack
, node
);
710 dfs_nr
[node
] = ++count
;
712 /* We don't traverse to the exit block. */
713 child
= ei_edge (current_edge
)->dest
->index
;
714 if (child
== EXIT_BLOCK
)
716 SET_EDGE_PASSED (current_edge
);
717 ei_next (¤t_edge
);
721 /* If the successor is in the stack, then we've found a loop.
722 Mark the loop, if it is not a natural loop, then it will
723 be rejected during the second traversal. */
724 if (bitmap_bit_p (in_stack
, child
))
727 bitmap_set_bit (header
, child
);
728 UPDATE_LOOP_RELATIONS (node
, child
);
729 SET_EDGE_PASSED (current_edge
);
730 ei_next (¤t_edge
);
734 /* If the child was already visited, then there is no need to visit
735 it again. Just update the loop relationships and restart
739 if (max_hdr
[child
] >= 0 && bitmap_bit_p (in_stack
, max_hdr
[child
]))
740 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
741 SET_EDGE_PASSED (current_edge
);
742 ei_next (¤t_edge
);
746 /* Push an entry on the stack and continue DFS traversal. */
747 stack
[++sp
] = current_edge
;
748 SET_EDGE_PASSED (current_edge
);
749 current_edge
= ei_start (ei_edge (current_edge
)->dest
->succs
);
752 /* Reset ->aux field used by EDGE_PASSED. */
753 FOR_ALL_BB_FN (bb
, cfun
)
757 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
762 /* Another check for unreachable blocks. The earlier test in
763 is_cfg_nonregular only finds unreachable blocks that do not
766 The DFS traversal will mark every block that is reachable from
767 the entry node by placing a nonzero value in dfs_nr. Thus if
768 dfs_nr is zero for any block, then it must be unreachable. */
770 FOR_EACH_BB_FN (bb
, cfun
)
771 if (dfs_nr
[bb
->index
] == 0)
777 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
778 to hold degree counts. */
781 FOR_EACH_BB_FN (bb
, cfun
)
782 degree
[bb
->index
] = EDGE_COUNT (bb
->preds
);
784 /* Do not perform region scheduling if there are any unreachable
788 int *queue
, *degree1
= NULL
;
789 /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
790 there basic blocks, which are forced to be region heads.
791 This is done to try to assemble few smaller regions
792 from a too_large region. */
793 sbitmap extended_rgn_header
= NULL
;
794 bool extend_regions_p
;
797 bitmap_set_bit (header
, 0);
799 /* Second traversal:find reducible inner loops and topologically sort
800 block of each region. */
802 queue
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
804 extend_regions_p
= PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS
) > 0;
805 if (extend_regions_p
)
807 degree1
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
808 extended_rgn_header
=
809 sbitmap_alloc (last_basic_block_for_fn (cfun
));
810 bitmap_clear (extended_rgn_header
);
813 /* Find blocks which are inner loop headers. We still have non-reducible
814 loops to consider at this point. */
815 FOR_EACH_BB_FN (bb
, cfun
)
817 if (bitmap_bit_p (header
, bb
->index
) && bitmap_bit_p (inner
, bb
->index
))
823 /* Now check that the loop is reducible. We do this separate
824 from finding inner loops so that we do not find a reducible
825 loop which contains an inner non-reducible loop.
827 A simple way to find reducible/natural loops is to verify
828 that each block in the loop is dominated by the loop
831 If there exists a block that is not dominated by the loop
832 header, then the block is reachable from outside the loop
833 and thus the loop is not a natural loop. */
834 FOR_EACH_BB_FN (jbb
, cfun
)
836 /* First identify blocks in the loop, except for the loop
838 if (bb
->index
== max_hdr
[jbb
->index
] && bb
!= jbb
)
840 /* Now verify that the block is dominated by the loop
842 if (!dominated_by_p (CDI_DOMINATORS
, jbb
, bb
))
847 /* If we exited the loop early, then I is the header of
848 a non-reducible loop and we should quit processing it
850 if (jbb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
853 /* I is a header of an inner loop, or block 0 in a subroutine
854 with no loops at all. */
856 too_large_failure
= 0;
857 loop_head
= max_hdr
[bb
->index
];
859 if (extend_regions_p
)
860 /* We save degree in case when we meet a too_large region
861 and cancel it. We need a correct degree later when
862 calling extend_rgns. */
863 memcpy (degree1
, degree
,
864 last_basic_block_for_fn (cfun
) * sizeof (int));
866 /* Decrease degree of all I's successors for topological
868 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
869 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
870 --degree
[e
->dest
->index
];
872 /* Estimate # insns, and count # blocks in the region. */
874 num_insns
= common_sched_info
->estimate_number_of_insns (bb
);
876 /* Find all loop latches (blocks with back edges to the loop
877 header) or all the leaf blocks in the cfg has no loops.
879 Place those blocks into the queue. */
882 FOR_EACH_BB_FN (jbb
, cfun
)
883 /* Leaf nodes have only a single successor which must
885 if (single_succ_p (jbb
)
886 && single_succ (jbb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
888 queue
[++tail
] = jbb
->index
;
889 bitmap_set_bit (in_queue
, jbb
->index
);
891 if (too_large (jbb
->index
, &num_bbs
, &num_insns
))
893 too_large_failure
= 1;
902 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
904 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
907 node
= e
->src
->index
;
909 if (max_hdr
[node
] == loop_head
&& node
!= bb
->index
)
911 /* This is a loop latch. */
912 queue
[++tail
] = node
;
913 bitmap_set_bit (in_queue
, node
);
915 if (too_large (node
, &num_bbs
, &num_insns
))
917 too_large_failure
= 1;
924 /* Now add all the blocks in the loop to the queue.
926 We know the loop is a natural loop; however the algorithm
927 above will not always mark certain blocks as being in the
935 The algorithm in the DFS traversal may not mark B & D as part
936 of the loop (i.e. they will not have max_hdr set to A).
938 We know they can not be loop latches (else they would have
939 had max_hdr set since they'd have a backedge to a dominator
940 block). So we don't need them on the initial queue.
942 We know they are part of the loop because they are dominated
943 by the loop header and can be reached by a backwards walk of
944 the edges starting with nodes on the initial queue.
946 It is safe and desirable to include those nodes in the
947 loop/scheduling region. To do so we would need to decrease
948 the degree of a node if it is the target of a backedge
949 within the loop itself as the node is placed in the queue.
951 We do not do this because I'm not sure that the actual
952 scheduling code will properly handle this case. ?!? */
954 while (head
< tail
&& !too_large_failure
)
957 child
= queue
[++head
];
959 FOR_EACH_EDGE (e
, ei
,
960 BASIC_BLOCK_FOR_FN (cfun
, child
)->preds
)
962 node
= e
->src
->index
;
964 /* See discussion above about nodes not marked as in
965 this loop during the initial DFS traversal. */
966 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
967 || max_hdr
[node
] != loop_head
)
972 else if (!bitmap_bit_p (in_queue
, node
) && node
!= bb
->index
)
974 queue
[++tail
] = node
;
975 bitmap_set_bit (in_queue
, node
);
977 if (too_large (node
, &num_bbs
, &num_insns
))
979 too_large_failure
= 1;
986 if (tail
>= 0 && !too_large_failure
)
988 /* Place the loop header into list of region blocks. */
989 degree
[bb
->index
] = -1;
990 rgn_bb_table
[idx
] = bb
->index
;
991 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
992 RGN_BLOCKS (nr_regions
) = idx
++;
993 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
994 RGN_HAS_REAL_EBB (nr_regions
) = 0;
995 CONTAINING_RGN (bb
->index
) = nr_regions
;
996 BLOCK_TO_BB (bb
->index
) = count
= 0;
998 /* Remove blocks from queue[] when their in degree
999 becomes zero. Repeat until no blocks are left on the
1000 list. This produces a topological list of blocks in
1006 child
= queue
[head
];
1007 if (degree
[child
] == 0)
1012 rgn_bb_table
[idx
++] = child
;
1013 BLOCK_TO_BB (child
) = ++count
;
1014 CONTAINING_RGN (child
) = nr_regions
;
1015 queue
[head
] = queue
[tail
--];
1017 FOR_EACH_EDGE (e
, ei
,
1018 BASIC_BLOCK_FOR_FN (cfun
,
1020 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1021 --degree
[e
->dest
->index
];
1028 else if (extend_regions_p
)
1030 /* Restore DEGREE. */
1036 /* And force successors of BB to be region heads.
1037 This may provide several smaller regions instead
1038 of one too_large region. */
1039 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1040 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1041 bitmap_set_bit (extended_rgn_header
, e
->dest
->index
);
1047 if (extend_regions_p
)
1051 bitmap_ior (header
, header
, extended_rgn_header
);
1052 sbitmap_free (extended_rgn_header
);
1054 extend_rgns (degree
, &idx
, header
, max_hdr
);
1058 /* Any block that did not end up in a region is placed into a region
1060 FOR_EACH_BB_FN (bb
, cfun
)
1061 if (degree
[bb
->index
] >= 0)
1063 rgn_bb_table
[idx
] = bb
->index
;
1064 RGN_NR_BLOCKS (nr_regions
) = 1;
1065 RGN_BLOCKS (nr_regions
) = idx
++;
1066 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1067 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1068 CONTAINING_RGN (bb
->index
) = nr_regions
++;
1069 BLOCK_TO_BB (bb
->index
) = 0;
1075 sbitmap_free (header
);
1076 sbitmap_free (inner
);
1077 sbitmap_free (in_queue
);
1078 sbitmap_free (in_stack
);
1082 /* Wrapper function.
1083 If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
1084 regions. Otherwise just call find_rgns_haifa. */
1088 if (sel_sched_p () && flag_sel_sched_pipelining
)
1094 static int gather_region_statistics (int **);
1095 static void print_region_statistics (int *, int, int *, int);
1097 /* Calculate the histogram that shows the number of regions having the
1098 given number of basic blocks, and store it in the RSP array. Return
1099 the size of this array. */
1101 gather_region_statistics (int **rsp
)
1103 int i
, *a
= 0, a_sz
= 0;
1105 /* a[i] is the number of regions that have (i + 1) basic blocks. */
1106 for (i
= 0; i
< nr_regions
; i
++)
1108 int nr_blocks
= RGN_NR_BLOCKS (i
);
1110 gcc_assert (nr_blocks
>= 1);
1112 if (nr_blocks
> a_sz
)
1114 a
= XRESIZEVEC (int, a
, nr_blocks
);
1117 while (a_sz
!= nr_blocks
);
1127 /* Print regions statistics. S1 and S2 denote the data before and after
1128 calling extend_rgns, respectively. */
1130 print_region_statistics (int *s1
, int s1_sz
, int *s2
, int s2_sz
)
1134 /* We iterate until s2_sz because extend_rgns does not decrease
1135 the maximal region size. */
1136 for (i
= 1; i
< s2_sz
; i
++)
1150 fprintf (sched_dump
, ";; Region extension statistics: size %d: " \
1151 "was %d + %d more\n", i
+ 1, n1
, n2
- n1
);
1156 DEGREE - Array of incoming edge count, considering only
1157 the edges, that don't have their sources in formed regions yet.
1158 IDXP - pointer to the next available index in rgn_bb_table.
1159 HEADER - set of all region heads.
1160 LOOP_HDR - mapping from block to the containing loop
1161 (two blocks can reside within one region if they have
1162 the same loop header). */
1164 extend_rgns (int *degree
, int *idxp
, sbitmap header
, int *loop_hdr
)
1166 int *order
, i
, rescan
= 0, idx
= *idxp
, iter
= 0, max_iter
, *max_hdr
;
1167 int nblocks
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
1169 max_iter
= PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS
);
1171 max_hdr
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1173 order
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1174 post_order_compute (order
, false, false);
1176 for (i
= nblocks
- 1; i
>= 0; i
--)
1179 if (degree
[bbn
] >= 0)
1185 /* This block already was processed in find_rgns. */
1189 /* The idea is to topologically walk through CFG in top-down order.
1190 During the traversal, if all the predecessors of a node are
1191 marked to be in the same region (they all have the same max_hdr),
1192 then current node is also marked to be a part of that region.
1193 Otherwise the node starts its own region.
1194 CFG should be traversed until no further changes are made. On each
1195 iteration the set of the region heads is extended (the set of those
1196 blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
1197 set of all basic blocks, thus the algorithm is guaranteed to
1200 while (rescan
&& iter
< max_iter
)
1204 for (i
= nblocks
- 1; i
>= 0; i
--)
1210 if (max_hdr
[bbn
] != -1 && !bitmap_bit_p (header
, bbn
))
1214 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK_FOR_FN (cfun
, bbn
)->preds
)
1216 int predn
= e
->src
->index
;
1218 if (predn
!= ENTRY_BLOCK
1219 /* If pred wasn't processed in find_rgns. */
1220 && max_hdr
[predn
] != -1
1221 /* And pred and bb reside in the same loop.
1222 (Or out of any loop). */
1223 && loop_hdr
[bbn
] == loop_hdr
[predn
])
1226 /* Then bb extends the containing region of pred. */
1227 hdr
= max_hdr
[predn
];
1228 else if (hdr
!= max_hdr
[predn
])
1229 /* Too bad, there are at least two predecessors
1230 that reside in different regions. Thus, BB should
1231 begin its own region. */
1238 /* BB starts its own region. */
1247 /* If BB start its own region,
1248 update set of headers with BB. */
1249 bitmap_set_bit (header
, bbn
);
1253 gcc_assert (hdr
!= -1);
1262 /* Statistics were gathered on the SPEC2000 package of tests with
1263 mainline weekly snapshot gcc-4.1-20051015 on ia64.
1265 Statistics for SPECint:
1266 1 iteration : 1751 cases (38.7%)
1267 2 iterations: 2770 cases (61.3%)
1268 Blocks wrapped in regions by find_rgns without extension: 18295 blocks
1269 Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
1270 (We don't count single block regions here).
1272 Statistics for SPECfp:
1273 1 iteration : 621 cases (35.9%)
1274 2 iterations: 1110 cases (64.1%)
1275 Blocks wrapped in regions by find_rgns without extension: 6476 blocks
1276 Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
1277 (We don't count single block regions here).
1279 By default we do at most 2 iterations.
1280 This can be overridden with max-sched-extend-regions-iters parameter:
1281 0 - disable region extension,
1282 N > 0 - do at most N iterations. */
1284 if (sched_verbose
&& iter
!= 0)
1285 fprintf (sched_dump
, ";; Region extension iterations: %d%s\n", iter
,
1286 rescan
? "... failed" : "");
1288 if (!rescan
&& iter
!= 0)
1290 int *s1
= NULL
, s1_sz
= 0;
1292 /* Save the old statistics for later printout. */
1293 if (sched_verbose
>= 6)
1294 s1_sz
= gather_region_statistics (&s1
);
1296 /* We have succeeded. Now assemble the regions. */
1297 for (i
= nblocks
- 1; i
>= 0; i
--)
1301 if (max_hdr
[bbn
] == bbn
)
1302 /* BBN is a region head. */
1306 int num_bbs
= 0, j
, num_insns
= 0, large
;
1308 large
= too_large (bbn
, &num_bbs
, &num_insns
);
1311 rgn_bb_table
[idx
] = bbn
;
1312 RGN_BLOCKS (nr_regions
) = idx
++;
1313 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1314 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1315 CONTAINING_RGN (bbn
) = nr_regions
;
1316 BLOCK_TO_BB (bbn
) = 0;
1318 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK_FOR_FN (cfun
, bbn
)->succs
)
1319 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1320 degree
[e
->dest
->index
]--;
1323 /* Here we check whether the region is too_large. */
1324 for (j
= i
- 1; j
>= 0; j
--)
1326 int succn
= order
[j
];
1327 if (max_hdr
[succn
] == bbn
)
1329 if ((large
= too_large (succn
, &num_bbs
, &num_insns
)))
1335 /* If the region is too_large, then wrap every block of
1336 the region into single block region.
1337 Here we wrap region head only. Other blocks are
1338 processed in the below cycle. */
1340 RGN_NR_BLOCKS (nr_regions
) = 1;
1346 for (j
= i
- 1; j
>= 0; j
--)
1348 int succn
= order
[j
];
1350 if (max_hdr
[succn
] == bbn
)
1351 /* This cycle iterates over all basic blocks, that
1352 are supposed to be in the region with head BBN,
1353 and wraps them into that region (or in single
1356 gcc_assert (degree
[succn
] == 0);
1359 rgn_bb_table
[idx
] = succn
;
1360 BLOCK_TO_BB (succn
) = large
? 0 : num_bbs
++;
1361 CONTAINING_RGN (succn
) = nr_regions
;
1364 /* Wrap SUCCN into single block region. */
1366 RGN_BLOCKS (nr_regions
) = idx
;
1367 RGN_NR_BLOCKS (nr_regions
) = 1;
1368 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1369 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1375 FOR_EACH_EDGE (e
, ei
,
1376 BASIC_BLOCK_FOR_FN (cfun
, succn
)->succs
)
1377 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1378 degree
[e
->dest
->index
]--;
1384 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1390 if (sched_verbose
>= 6)
1394 /* Get the new statistics and print the comparison with the
1395 one before calling this function. */
1396 s2_sz
= gather_region_statistics (&s2
);
1397 print_region_statistics (s1
, s1_sz
, s2
, s2_sz
);
1409 /* Functions for regions scheduling information. */
1411 /* Compute dominators, probability, and potential-split-edges of bb.
1412 Assume that these values were already computed for bb's predecessors. */
1415 compute_dom_prob_ps (int bb
)
1417 edge_iterator in_ei
;
1420 /* We shouldn't have any real ebbs yet. */
1421 gcc_assert (ebb_head
[bb
] == bb
+ current_blocks
);
1423 if (IS_RGN_ENTRY (bb
))
1425 bitmap_set_bit (dom
[bb
], 0);
1426 prob
[bb
] = REG_BR_PROB_BASE
;
1432 /* Initialize dom[bb] to '111..1'. */
1433 bitmap_ones (dom
[bb
]);
1435 FOR_EACH_EDGE (in_edge
, in_ei
,
1436 BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (bb
))->preds
)
1440 edge_iterator out_ei
;
1442 if (in_edge
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1445 pred_bb
= BLOCK_TO_BB (in_edge
->src
->index
);
1446 bitmap_and (dom
[bb
], dom
[bb
], dom
[pred_bb
]);
1447 bitmap_ior (ancestor_edges
[bb
],
1448 ancestor_edges
[bb
], ancestor_edges
[pred_bb
]);
1450 bitmap_set_bit (ancestor_edges
[bb
], EDGE_TO_BIT (in_edge
));
1452 bitmap_ior (pot_split
[bb
], pot_split
[bb
], pot_split
[pred_bb
]);
1454 FOR_EACH_EDGE (out_edge
, out_ei
, in_edge
->src
->succs
)
1455 bitmap_set_bit (pot_split
[bb
], EDGE_TO_BIT (out_edge
));
1457 prob
[bb
] += combine_probabilities (prob
[pred_bb
], in_edge
->probability
);
1458 // The rounding divide in combine_probabilities can result in an extra
1459 // probability increment propagating along 50-50 edges. Eventually when
1460 // the edges re-merge, the accumulated probability can go slightly above
1461 // REG_BR_PROB_BASE.
1462 if (prob
[bb
] > REG_BR_PROB_BASE
)
1463 prob
[bb
] = REG_BR_PROB_BASE
;
1466 bitmap_set_bit (dom
[bb
], bb
);
1467 bitmap_and_compl (pot_split
[bb
], pot_split
[bb
], ancestor_edges
[bb
]);
1469 if (sched_verbose
>= 2)
1470 fprintf (sched_dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
),
1471 (100 * prob
[bb
]) / REG_BR_PROB_BASE
);
1474 /* Functions for target info. */
1476 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1477 Note that bb_trg dominates bb_src. */
1480 split_edges (int bb_src
, int bb_trg
, edgelst
*bl
)
1482 sbitmap src
= sbitmap_alloc (SBITMAP_SIZE (pot_split
[bb_src
]));
1483 bitmap_copy (src
, pot_split
[bb_src
]);
1485 bitmap_and_compl (src
, src
, pot_split
[bb_trg
]);
1486 extract_edgelst (src
, bl
);
1490 /* Find the valid candidate-source-blocks for the target block TRG, compute
1491 their probability, and check if they are speculative or not.
1492 For speculative sources, compute their update-blocks and split-blocks. */
1495 compute_trg_info (int trg
)
1498 edgelst el
= { NULL
, 0 };
1499 int i
, j
, k
, update_idx
;
1505 candidate_table
= XNEWVEC (candidate
, current_nr_blocks
);
1508 /* bblst_table holds split blocks and update blocks for each block after
1509 the current one in the region. split blocks and update blocks are
1510 the TO blocks of region edges, so there can be at most rgn_nr_edges
1512 bblst_size
= (current_nr_blocks
- target_bb
) * rgn_nr_edges
;
1513 bblst_table
= XNEWVEC (basic_block
, bblst_size
);
1516 edgelst_table
= XNEWVEC (edge
, rgn_nr_edges
);
1518 /* Define some of the fields for the target bb as well. */
1519 sp
= candidate_table
+ trg
;
1521 sp
->is_speculative
= 0;
1522 sp
->src_prob
= REG_BR_PROB_BASE
;
1524 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1526 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1528 sp
= candidate_table
+ i
;
1530 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1533 int tf
= prob
[trg
], cf
= prob
[i
];
1535 /* In CFGs with low probability edges TF can possibly be zero. */
1536 sp
->src_prob
= (tf
? GCOV_COMPUTE_SCALE (cf
, tf
) : 0);
1537 sp
->is_valid
= (sp
->src_prob
>= min_spec_prob
);
1542 split_edges (i
, trg
, &el
);
1543 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1544 if (sp
->is_speculative
&& !flag_schedule_speculative
)
1550 /* Compute split blocks and store them in bblst_table.
1551 The TO block of every split edge is a split block. */
1552 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
1553 sp
->split_bbs
.nr_members
= el
.nr_members
;
1554 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
1555 bblst_table
[bblst_last
] = el
.first_member
[j
]->dest
;
1556 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
1558 /* Compute update blocks and store them in bblst_table.
1559 For every split edge, look at the FROM block, and check
1560 all out edges. For each out edge that is not a split edge,
1561 add the TO block to the update block list. This list can end
1562 up with a lot of duplicates. We need to weed them out to avoid
1563 overrunning the end of the bblst_table. */
1566 bitmap_clear (visited
);
1567 for (j
= 0; j
< el
.nr_members
; j
++)
1569 block
= el
.first_member
[j
]->src
;
1570 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1572 if (!bitmap_bit_p (visited
, e
->dest
->index
))
1574 for (k
= 0; k
< el
.nr_members
; k
++)
1575 if (e
== el
.first_member
[k
])
1578 if (k
>= el
.nr_members
)
1580 bblst_table
[bblst_last
++] = e
->dest
;
1581 bitmap_set_bit (visited
, e
->dest
->index
);
1587 sp
->update_bbs
.nr_members
= update_idx
;
1589 /* Make sure we didn't overrun the end of bblst_table. */
1590 gcc_assert (bblst_last
<= bblst_size
);
1594 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
1596 sp
->is_speculative
= 0;
1601 sbitmap_free (visited
);
1604 /* Free the computed target info. */
1606 free_trg_info (void)
1608 free (candidate_table
);
1610 free (edgelst_table
);
1613 /* Print candidates info, for debugging purposes. Callable from debugger. */
1616 debug_candidate (int i
)
1618 if (!candidate_table
[i
].is_valid
)
1621 if (candidate_table
[i
].is_speculative
)
1624 fprintf (sched_dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
1626 fprintf (sched_dump
, "split path: ");
1627 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
1629 int b
= candidate_table
[i
].split_bbs
.first_member
[j
]->index
;
1631 fprintf (sched_dump
, " %d ", b
);
1633 fprintf (sched_dump
, "\n");
1635 fprintf (sched_dump
, "update path: ");
1636 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
1638 int b
= candidate_table
[i
].update_bbs
.first_member
[j
]->index
;
1640 fprintf (sched_dump
, " %d ", b
);
1642 fprintf (sched_dump
, "\n");
1646 fprintf (sched_dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
1650 /* Print candidates info, for debugging purposes. Callable from debugger. */
1653 debug_candidates (int trg
)
1657 fprintf (sched_dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
1658 BB_TO_BLOCK (trg
), trg
);
1659 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1660 debug_candidate (i
);
1663 /* Functions for speculative scheduling. */
1665 static bitmap_head not_in_df
;
1667 /* Return 0 if x is a set of a register alive in the beginning of one
1668 of the split-blocks of src, otherwise return 1. */
1671 check_live_1 (int src
, rtx x
)
1675 rtx reg
= SET_DEST (x
);
1680 while (GET_CODE (reg
) == SUBREG
1681 || GET_CODE (reg
) == ZERO_EXTRACT
1682 || GET_CODE (reg
) == STRICT_LOW_PART
)
1683 reg
= XEXP (reg
, 0);
1685 if (GET_CODE (reg
) == PARALLEL
)
1689 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1690 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1691 if (check_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0)))
1700 regno
= REGNO (reg
);
1702 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
1704 /* Global registers are assumed live. */
1709 if (regno
< FIRST_PSEUDO_REGISTER
)
1711 /* Check for hard registers. */
1712 int j
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1715 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1717 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1718 int t
= bitmap_bit_p (¬_in_df
, b
->index
);
1720 /* We can have split blocks, that were recently generated.
1721 Such blocks are always outside current region. */
1722 gcc_assert (!t
|| (CONTAINING_RGN (b
->index
)
1723 != CONTAINING_RGN (BB_TO_BLOCK (src
))));
1725 if (t
|| REGNO_REG_SET_P (df_get_live_in (b
), regno
+ j
))
1732 /* Check for pseudo registers. */
1733 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1735 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1736 int t
= bitmap_bit_p (¬_in_df
, b
->index
);
1738 gcc_assert (!t
|| (CONTAINING_RGN (b
->index
)
1739 != CONTAINING_RGN (BB_TO_BLOCK (src
))));
1741 if (t
|| REGNO_REG_SET_P (df_get_live_in (b
), regno
))
1750 /* If x is a set of a register R, mark that R is alive in the beginning
1751 of every update-block of src. */
1754 update_live_1 (int src
, rtx x
)
1758 rtx reg
= SET_DEST (x
);
1763 while (GET_CODE (reg
) == SUBREG
1764 || GET_CODE (reg
) == ZERO_EXTRACT
1765 || GET_CODE (reg
) == STRICT_LOW_PART
)
1766 reg
= XEXP (reg
, 0);
1768 if (GET_CODE (reg
) == PARALLEL
)
1772 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1773 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1774 update_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0));
1782 /* Global registers are always live, so the code below does not apply
1785 regno
= REGNO (reg
);
1787 if (! HARD_REGISTER_NUM_P (regno
)
1788 || !global_regs
[regno
])
1790 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
1792 basic_block b
= candidate_table
[src
].update_bbs
.first_member
[i
];
1794 if (HARD_REGISTER_NUM_P (regno
))
1795 bitmap_set_range (df_get_live_in (b
), regno
,
1796 hard_regno_nregs
[regno
][GET_MODE (reg
)]);
1798 bitmap_set_bit (df_get_live_in (b
), regno
);
1803 /* Return 1 if insn can be speculatively moved from block src to trg,
1804 otherwise return 0. Called before first insertion of insn to
1805 ready-list or before the scheduling. */
1808 check_live (rtx_insn
*insn
, int src
)
1810 /* Find the registers set by instruction. */
1811 if (GET_CODE (PATTERN (insn
)) == SET
1812 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1813 return check_live_1 (src
, PATTERN (insn
));
1814 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1817 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1818 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1819 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1820 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
1829 /* Update the live registers info after insn was moved speculatively from
1830 block src to trg. */
1833 update_live (rtx insn
, int src
)
1835 /* Find the registers set by instruction. */
1836 if (GET_CODE (PATTERN (insn
)) == SET
1837 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1838 update_live_1 (src
, PATTERN (insn
));
1839 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1842 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1843 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1844 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1845 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
1849 /* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1850 #define IS_REACHABLE(bb_from, bb_to) \
1852 || IS_RGN_ENTRY (bb_from) \
1853 || (bitmap_bit_p (ancestor_edges[bb_to], \
1854 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK_FOR_FN (cfun, \
1855 BB_TO_BLOCK (bb_from)))))))
1857 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1860 set_spec_fed (rtx load_insn
)
1862 sd_iterator_def sd_it
;
1865 FOR_EACH_DEP (load_insn
, SD_LIST_FORW
, sd_it
, dep
)
1866 if (DEP_TYPE (dep
) == REG_DEP_TRUE
)
1867 FED_BY_SPEC_LOAD (DEP_CON (dep
)) = 1;
1870 /* On the path from the insn to load_insn_bb, find a conditional
1871 branch depending on insn, that guards the speculative load. */
1874 find_conditional_protection (rtx insn
, int load_insn_bb
)
1876 sd_iterator_def sd_it
;
1879 /* Iterate through DEF-USE forward dependences. */
1880 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
1882 rtx_insn
*next
= DEP_CON (dep
);
1884 if ((CONTAINING_RGN (BLOCK_NUM (next
)) ==
1885 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
1886 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
1887 && load_insn_bb
!= INSN_BB (next
)
1888 && DEP_TYPE (dep
) == REG_DEP_TRUE
1890 || find_conditional_protection (next
, load_insn_bb
)))
1894 } /* find_conditional_protection */
1896 /* Returns 1 if the same insn1 that participates in the computation
1897 of load_insn's address is feeding a conditional branch that is
1898 guarding on load_insn. This is true if we find two DEF-USE
1900 insn1 -> ... -> conditional-branch
1901 insn1 -> ... -> load_insn,
1902 and if a flow path exists:
1903 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1904 and if insn1 is on the path
1905 region-entry -> ... -> bb_trg -> ... load_insn.
1907 Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
1908 Locate the branch by following INSN_FORW_DEPS from insn1. */
1911 is_conditionally_protected (rtx load_insn
, int bb_src
, int bb_trg
)
1913 sd_iterator_def sd_it
;
1916 FOR_EACH_DEP (load_insn
, SD_LIST_BACK
, sd_it
, dep
)
1918 rtx_insn
*insn1
= DEP_PRO (dep
);
1920 /* Must be a DEF-USE dependence upon non-branch. */
1921 if (DEP_TYPE (dep
) != REG_DEP_TRUE
1925 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1926 if (INSN_BB (insn1
) == bb_src
1927 || (CONTAINING_RGN (BLOCK_NUM (insn1
))
1928 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
1929 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
1930 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
1933 /* Now search for the conditional-branch. */
1934 if (find_conditional_protection (insn1
, bb_src
))
1937 /* Recursive step: search another insn1, "above" current insn1. */
1938 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
1941 /* The chain does not exist. */
1943 } /* is_conditionally_protected */
1945 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1946 load_insn can move speculatively from bb_src to bb_trg. All the
1947 following must hold:
1949 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1950 (2) load_insn and load1 have a def-use dependence upon
1951 the same insn 'insn1'.
1952 (3) either load2 is in bb_trg, or:
1953 - there's only one split-block, and
1954 - load1 is on the escape path, and
1956 From all these we can conclude that the two loads access memory
1957 addresses that differ at most by a constant, and hence if moving
1958 load_insn would cause an exception, it would have been caused by
1962 is_pfree (rtx load_insn
, int bb_src
, int bb_trg
)
1964 sd_iterator_def back_sd_it
;
1966 candidate
*candp
= candidate_table
+ bb_src
;
1968 if (candp
->split_bbs
.nr_members
!= 1)
1969 /* Must have exactly one escape block. */
1972 FOR_EACH_DEP (load_insn
, SD_LIST_BACK
, back_sd_it
, back_dep
)
1974 rtx_insn
*insn1
= DEP_PRO (back_dep
);
1976 if (DEP_TYPE (back_dep
) == REG_DEP_TRUE
)
1977 /* Found a DEF-USE dependence (insn1, load_insn). */
1979 sd_iterator_def fore_sd_it
;
1982 FOR_EACH_DEP (insn1
, SD_LIST_FORW
, fore_sd_it
, fore_dep
)
1984 rtx_insn
*insn2
= DEP_CON (fore_dep
);
1986 if (DEP_TYPE (fore_dep
) == REG_DEP_TRUE
)
1988 /* Found a DEF-USE dependence (insn1, insn2). */
1989 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
1990 /* insn2 not guaranteed to be a 1 base reg load. */
1993 if (INSN_BB (insn2
) == bb_trg
)
1994 /* insn2 is the similar load, in the target block. */
1997 if (*(candp
->split_bbs
.first_member
) == BLOCK_FOR_INSN (insn2
))
1998 /* insn2 is a similar load, in a split-block. */
2005 /* Couldn't find a similar load. */
2009 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2010 a load moved speculatively, or if load_insn is protected by
2011 a compare on load_insn's address). */
2014 is_prisky (rtx load_insn
, int bb_src
, int bb_trg
)
2016 if (FED_BY_SPEC_LOAD (load_insn
))
2019 if (sd_lists_empty_p (load_insn
, SD_LIST_BACK
))
2020 /* Dependence may 'hide' out of the region. */
2023 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2029 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2030 Return 1 if insn is exception-free (and the motion is valid)
2034 is_exception_free (rtx insn
, int bb_src
, int bb_trg
)
2036 int insn_class
= haifa_classify_insn (insn
);
2038 /* Handle non-load insns. */
2049 if (!flag_schedule_speculative_load
)
2051 IS_LOAD_INSN (insn
) = 1;
2058 case PFREE_CANDIDATE
:
2059 if (is_pfree (insn
, bb_src
, bb_trg
))
2061 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2062 case PRISKY_CANDIDATE
:
2063 if (!flag_schedule_speculative_load_dangerous
2064 || is_prisky (insn
, bb_src
, bb_trg
))
2070 return flag_schedule_speculative_load_dangerous
;
2073 /* The number of insns from the current block scheduled so far. */
2074 static int sched_target_n_insns
;
2075 /* The number of insns from the current block to be scheduled in total. */
2076 static int target_n_insns
;
2077 /* The number of insns from the entire region scheduled so far. */
2078 static int sched_n_insns
;
2080 /* Implementations of the sched_info functions for region scheduling. */
2081 static void init_ready_list (void);
2082 static int can_schedule_ready_p (rtx_insn
*);
2083 static void begin_schedule_ready (rtx_insn
*);
2084 static ds_t
new_ready (rtx_insn
*, ds_t
);
2085 static int schedule_more_p (void);
2086 static const char *rgn_print_insn (const rtx_insn
*, int);
2087 static int rgn_rank (rtx_insn
*, rtx_insn
*);
2088 static void compute_jump_reg_dependencies (rtx
, regset
);
2090 /* Functions for speculative scheduling. */
2091 static void rgn_add_remove_insn (rtx_insn
*, int);
2092 static void rgn_add_block (basic_block
, basic_block
);
2093 static void rgn_fix_recovery_cfg (int, int, int);
2094 static basic_block
advance_target_bb (basic_block
, rtx_insn
*);
2096 /* Return nonzero if there are more insns that should be scheduled. */
2099 schedule_more_p (void)
2101 return sched_target_n_insns
< target_n_insns
;
2104 /* Add all insns that are initially ready to the ready list READY. Called
2105 once before scheduling a set of insns. */
2108 init_ready_list (void)
2110 rtx_insn
*prev_head
= current_sched_info
->prev_head
;
2111 rtx_insn
*next_tail
= current_sched_info
->next_tail
;
2116 sched_target_n_insns
= 0;
2119 /* Print debugging information. */
2120 if (sched_verbose
>= 5)
2121 debug_rgn_dependencies (target_bb
);
2123 /* Prepare current target block info. */
2124 if (current_nr_blocks
> 1)
2125 compute_trg_info (target_bb
);
2127 /* Initialize ready list with all 'ready' insns in target block.
2128 Count number of insns in the target block being scheduled. */
2129 for (insn
= NEXT_INSN (prev_head
); insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2131 gcc_assert (TODO_SPEC (insn
) == HARD_DEP
|| TODO_SPEC (insn
) == DEP_POSTPONED
);
2132 TODO_SPEC (insn
) = HARD_DEP
;
2136 gcc_assert (!(TODO_SPEC (insn
) & BEGIN_CONTROL
));
2139 /* Add to ready list all 'ready' insns in valid source blocks.
2140 For speculative insns, check-live, exception-free, and
2142 for (bb_src
= target_bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
2143 if (IS_VALID (bb_src
))
2146 rtx_insn
*src_next_tail
;
2147 rtx_insn
*tail
, *head
;
2149 get_ebb_head_tail (EBB_FIRST_BB (bb_src
), EBB_LAST_BB (bb_src
),
2151 src_next_tail
= NEXT_INSN (tail
);
2154 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
2157 gcc_assert (TODO_SPEC (insn
) == HARD_DEP
|| TODO_SPEC (insn
) == DEP_POSTPONED
);
2158 TODO_SPEC (insn
) = HARD_DEP
;
2164 /* Called after taking INSN from the ready list. Returns nonzero if this
2165 insn can be scheduled, nonzero if we should silently discard it. */
2168 can_schedule_ready_p (rtx_insn
*insn
)
2170 /* An interblock motion? */
2171 if (INSN_BB (insn
) != target_bb
2172 && IS_SPECULATIVE_INSN (insn
)
2173 && !check_live (insn
, INSN_BB (insn
)))
2179 /* Updates counter and other information. Split from can_schedule_ready_p ()
2180 because when we schedule insn speculatively then insn passed to
2181 can_schedule_ready_p () differs from the one passed to
2182 begin_schedule_ready (). */
2184 begin_schedule_ready (rtx_insn
*insn
)
2186 /* An interblock motion? */
2187 if (INSN_BB (insn
) != target_bb
)
2189 if (IS_SPECULATIVE_INSN (insn
))
2191 gcc_assert (check_live (insn
, INSN_BB (insn
)));
2193 update_live (insn
, INSN_BB (insn
));
2195 /* For speculative load, mark insns fed by it. */
2196 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
2197 set_spec_fed (insn
);
2205 /* In block motion. */
2206 sched_target_n_insns
++;
2211 /* Called after INSN has all its hard dependencies resolved and the speculation
2212 of type TS is enough to overcome them all.
2213 Return nonzero if it should be moved to the ready list or the queue, or zero
2214 if we should silently discard it. */
2216 new_ready (rtx_insn
*next
, ds_t ts
)
2218 if (INSN_BB (next
) != target_bb
)
2220 int not_ex_free
= 0;
2222 /* For speculative insns, before inserting to ready/queue,
2223 check live, exception-free, and issue-delay. */
2224 if (!IS_VALID (INSN_BB (next
))
2226 || (IS_SPECULATIVE_INSN (next
)
2227 && ((recog_memoized (next
) >= 0
2228 && min_insn_conflict_delay (curr_state
, next
, next
)
2229 > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY
))
2230 || IS_SPECULATION_CHECK_P (next
)
2231 || !check_live (next
, INSN_BB (next
))
2232 || (not_ex_free
= !is_exception_free (next
, INSN_BB (next
),
2236 /* We are here because is_exception_free () == false.
2237 But we possibly can handle that with control speculation. */
2238 && sched_deps_info
->generate_spec_deps
2239 && spec_info
->mask
& BEGIN_CONTROL
)
2243 /* Add control speculation to NEXT's dependency type. */
2244 new_ds
= set_dep_weak (ts
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
2246 /* Check if NEXT can be speculated with new dependency type. */
2247 if (sched_insn_is_legitimate_for_speculation_p (next
, new_ds
))
2248 /* Here we got new control-speculative instruction. */
2251 /* NEXT isn't ready yet. */
2255 /* NEXT isn't ready yet. */
2263 /* Return a string that contains the insn uid and optionally anything else
2264 necessary to identify this insn in an output. It's valid to use a
2265 static buffer for this. The ALIGNED parameter should cause the string
2266 to be formatted so that multiple output lines will line up nicely. */
2269 rgn_print_insn (const rtx_insn
*insn
, int aligned
)
2271 static char tmp
[80];
2274 sprintf (tmp
, "b%3d: i%4d", INSN_BB (insn
), INSN_UID (insn
));
2277 if (current_nr_blocks
> 1 && INSN_BB (insn
) != target_bb
)
2278 sprintf (tmp
, "%d/b%d", INSN_UID (insn
), INSN_BB (insn
));
2280 sprintf (tmp
, "%d", INSN_UID (insn
));
2285 /* Compare priority of two insns. Return a positive number if the second
2286 insn is to be preferred for scheduling, and a negative one if the first
2287 is to be preferred. Zero if they are equally good. */
2290 rgn_rank (rtx_insn
*insn1
, rtx_insn
*insn2
)
2292 /* Some comparison make sense in interblock scheduling only. */
2293 if (INSN_BB (insn1
) != INSN_BB (insn2
))
2295 int spec_val
, prob_val
;
2297 /* Prefer an inblock motion on an interblock motion. */
2298 if ((INSN_BB (insn2
) == target_bb
) && (INSN_BB (insn1
) != target_bb
))
2300 if ((INSN_BB (insn1
) == target_bb
) && (INSN_BB (insn2
) != target_bb
))
2303 /* Prefer a useful motion on a speculative one. */
2304 spec_val
= IS_SPECULATIVE_INSN (insn1
) - IS_SPECULATIVE_INSN (insn2
);
2308 /* Prefer a more probable (speculative) insn. */
2309 prob_val
= INSN_PROBABILITY (insn2
) - INSN_PROBABILITY (insn1
);
2316 /* NEXT is an instruction that depends on INSN (a backward dependence);
2317 return nonzero if we should include this dependence in priority
2321 contributes_to_priority (rtx_insn
*next
, rtx_insn
*insn
)
2323 /* NEXT and INSN reside in one ebb. */
2324 return BLOCK_TO_BB (BLOCK_NUM (next
)) == BLOCK_TO_BB (BLOCK_NUM (insn
));
2327 /* INSN is a JUMP_INSN. Store the set of registers that must be
2328 considered as used by this jump in USED. */
2331 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
2332 regset used ATTRIBUTE_UNUSED
)
2334 /* Nothing to do here, since we postprocess jumps in
2335 add_branch_dependences. */
2338 /* This variable holds common_sched_info hooks and data relevant to
2339 the interblock scheduler. */
2340 static struct common_sched_info_def rgn_common_sched_info
;
2343 /* This holds data for the dependence analysis relevant to
2344 the interblock scheduler. */
2345 static struct sched_deps_info_def rgn_sched_deps_info
;
2347 /* This holds constant data used for initializing the above structure
2348 for the Haifa scheduler. */
2349 static const struct sched_deps_info_def rgn_const_sched_deps_info
=
2351 compute_jump_reg_dependencies
,
2352 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
2356 /* Same as above, but for the selective scheduler. */
2357 static const struct sched_deps_info_def rgn_const_sel_sched_deps_info
=
2359 compute_jump_reg_dependencies
,
2360 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
2364 /* Return true if scheduling INSN will trigger finish of scheduling
2367 rgn_insn_finishes_block_p (rtx_insn
*insn
)
2369 if (INSN_BB (insn
) == target_bb
2370 && sched_target_n_insns
+ 1 == target_n_insns
)
2371 /* INSN is the last not-scheduled instruction in the current block. */
2377 /* Used in schedule_insns to initialize current_sched_info for scheduling
2378 regions (or single basic blocks). */
2380 static const struct haifa_sched_info rgn_const_sched_info
=
2383 can_schedule_ready_p
,
2388 contributes_to_priority
,
2389 rgn_insn_finishes_block_p
,
2395 rgn_add_remove_insn
,
2396 begin_schedule_ready
,
2403 /* This variable holds the data and hooks needed to the Haifa scheduler backend
2404 for the interblock scheduler frontend. */
2405 static struct haifa_sched_info rgn_sched_info
;
2407 /* Returns maximum priority that an insn was assigned to. */
2410 get_rgn_sched_max_insns_priority (void)
2412 return rgn_sched_info
.sched_max_insns_priority
;
2415 /* Determine if PAT sets a TARGET_CLASS_LIKELY_SPILLED_P register. */
2418 sets_likely_spilled (rtx pat
)
2421 note_stores (pat
, sets_likely_spilled_1
, &ret
);
2426 sets_likely_spilled_1 (rtx x
, const_rtx pat
, void *data
)
2428 bool *ret
= (bool *) data
;
2430 if (GET_CODE (pat
) == SET
2432 && HARD_REGISTER_P (x
)
2433 && targetm
.class_likely_spilled_p (REGNO_REG_CLASS (REGNO (x
))))
2437 /* A bitmap to note insns that participate in any dependency. Used in
2438 add_branch_dependences. */
2439 static sbitmap insn_referenced
;
2441 /* Add dependences so that branches are scheduled to run last in their
2444 add_branch_dependences (rtx_insn
*head
, rtx_insn
*tail
)
2446 rtx_insn
*insn
, *last
;
2448 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2449 that can throw exceptions, force them to remain in order at the end of
2450 the block by adding dependencies and giving the last a high priority.
2451 There may be notes present, and prev_head may also be a note.
2453 Branches must obviously remain at the end. Calls should remain at the
2454 end since moving them results in worse register allocation. Uses remain
2455 at the end to ensure proper register allocation.
2457 cc0 setters remain at the end because they can't be moved away from
2460 Predecessors of SCHED_GROUP_P instructions at the end remain at the end.
2462 COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
2464 Insns setting TARGET_CLASS_LIKELY_SPILLED_P registers (usually return
2465 values) are not moved before reload because we can wind up with register
2466 allocation failures. */
2468 while (tail
!= head
&& DEBUG_INSN_P (tail
))
2469 tail
= PREV_INSN (tail
);
2473 while (CALL_P (insn
)
2474 || JUMP_P (insn
) || JUMP_TABLE_DATA_P (insn
)
2475 || (NONJUMP_INSN_P (insn
)
2476 && (GET_CODE (PATTERN (insn
)) == USE
2477 || GET_CODE (PATTERN (insn
)) == CLOBBER
2478 || can_throw_internal (insn
)
2480 || sets_cc0_p (PATTERN (insn
))
2482 || (!reload_completed
2483 && sets_likely_spilled (PATTERN (insn
)))))
2485 || (last
!= 0 && SCHED_GROUP_P (last
)))
2490 && sd_find_dep_between (insn
, last
, false) == NULL
)
2492 if (! sched_insns_conditions_mutex_p (last
, insn
))
2493 add_dependence (last
, insn
, REG_DEP_ANTI
);
2494 bitmap_set_bit (insn_referenced
, INSN_LUID (insn
));
2497 CANT_MOVE (insn
) = 1;
2502 /* Don't overrun the bounds of the basic block. */
2507 insn
= PREV_INSN (insn
);
2508 while (insn
!= head
&& DEBUG_INSN_P (insn
));
2511 /* Make sure these insns are scheduled last in their block. */
2514 while (insn
!= head
)
2516 insn
= prev_nonnote_insn (insn
);
2518 if (bitmap_bit_p (insn_referenced
, INSN_LUID (insn
))
2519 || DEBUG_INSN_P (insn
))
2522 if (! sched_insns_conditions_mutex_p (last
, insn
))
2523 add_dependence (last
, insn
, REG_DEP_ANTI
);
2526 if (!targetm
.have_conditional_execution ())
2529 /* Finally, if the block ends in a jump, and we are doing intra-block
2530 scheduling, make sure that the branch depends on any COND_EXEC insns
2531 inside the block to avoid moving the COND_EXECs past the branch insn.
2533 We only have to do this after reload, because (1) before reload there
2534 are no COND_EXEC insns, and (2) the region scheduler is an intra-block
2535 scheduler after reload.
2537 FIXME: We could in some cases move COND_EXEC insns past the branch if
2538 this scheduler would be a little smarter. Consider this code:
2546 On a target with a one cycle stall on a memory access the optimal
2555 We don't want to put the 'X += 12' before the branch because it just
2556 wastes a cycle of execution time when the branch is taken.
2558 Note that in the example "!C" will always be true. That is another
2559 possible improvement for handling COND_EXECs in this scheduler: it
2560 could remove always-true predicates. */
2562 if (!reload_completed
|| ! (JUMP_P (tail
) || JUMP_TABLE_DATA_P (tail
)))
2566 while (insn
!= head
)
2568 insn
= PREV_INSN (insn
);
2570 /* Note that we want to add this dependency even when
2571 sched_insns_conditions_mutex_p returns true. The whole point
2572 is that we _want_ this dependency, even if these insns really
2574 if (INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == COND_EXEC
)
2575 add_dependence (tail
, insn
, REG_DEP_ANTI
);
2579 /* Data structures for the computation of data dependences in a regions. We
2580 keep one `deps' structure for every basic block. Before analyzing the
2581 data dependences for a bb, its variables are initialized as a function of
2582 the variables of its predecessors. When the analysis for a bb completes,
2583 we save the contents to the corresponding bb_deps[bb] variable. */
2585 static struct deps_desc
*bb_deps
;
2588 concat_insn_mem_list (rtx_insn_list
*copy_insns
,
2589 rtx_expr_list
*copy_mems
,
2590 rtx_insn_list
**old_insns_p
,
2591 rtx_expr_list
**old_mems_p
)
2593 rtx_insn_list
*new_insns
= *old_insns_p
;
2594 rtx_expr_list
*new_mems
= *old_mems_p
;
2598 new_insns
= alloc_INSN_LIST (copy_insns
->insn (), new_insns
);
2599 new_mems
= alloc_EXPR_LIST (VOIDmode
, copy_mems
->element (), new_mems
);
2600 copy_insns
= copy_insns
->next ();
2601 copy_mems
= copy_mems
->next ();
2604 *old_insns_p
= new_insns
;
2605 *old_mems_p
= new_mems
;
2608 /* Join PRED_DEPS to the SUCC_DEPS. */
2610 deps_join (struct deps_desc
*succ_deps
, struct deps_desc
*pred_deps
)
2613 reg_set_iterator rsi
;
2615 /* The reg_last lists are inherited by successor. */
2616 EXECUTE_IF_SET_IN_REG_SET (&pred_deps
->reg_last_in_use
, 0, reg
, rsi
)
2618 struct deps_reg
*pred_rl
= &pred_deps
->reg_last
[reg
];
2619 struct deps_reg
*succ_rl
= &succ_deps
->reg_last
[reg
];
2621 succ_rl
->uses
= concat_INSN_LIST (pred_rl
->uses
, succ_rl
->uses
);
2622 succ_rl
->sets
= concat_INSN_LIST (pred_rl
->sets
, succ_rl
->sets
);
2623 succ_rl
->implicit_sets
2624 = concat_INSN_LIST (pred_rl
->implicit_sets
, succ_rl
->implicit_sets
);
2625 succ_rl
->clobbers
= concat_INSN_LIST (pred_rl
->clobbers
,
2627 succ_rl
->uses_length
+= pred_rl
->uses_length
;
2628 succ_rl
->clobbers_length
+= pred_rl
->clobbers_length
;
2630 IOR_REG_SET (&succ_deps
->reg_last_in_use
, &pred_deps
->reg_last_in_use
);
2632 /* Mem read/write lists are inherited by successor. */
2633 concat_insn_mem_list (pred_deps
->pending_read_insns
,
2634 pred_deps
->pending_read_mems
,
2635 &succ_deps
->pending_read_insns
,
2636 &succ_deps
->pending_read_mems
);
2637 concat_insn_mem_list (pred_deps
->pending_write_insns
,
2638 pred_deps
->pending_write_mems
,
2639 &succ_deps
->pending_write_insns
,
2640 &succ_deps
->pending_write_mems
);
2642 succ_deps
->pending_jump_insns
2643 = concat_INSN_LIST (pred_deps
->pending_jump_insns
,
2644 succ_deps
->pending_jump_insns
);
2645 succ_deps
->last_pending_memory_flush
2646 = concat_INSN_LIST (pred_deps
->last_pending_memory_flush
,
2647 succ_deps
->last_pending_memory_flush
);
2649 succ_deps
->pending_read_list_length
+= pred_deps
->pending_read_list_length
;
2650 succ_deps
->pending_write_list_length
+= pred_deps
->pending_write_list_length
;
2651 succ_deps
->pending_flush_length
+= pred_deps
->pending_flush_length
;
2653 /* last_function_call is inherited by successor. */
2654 succ_deps
->last_function_call
2655 = concat_INSN_LIST (pred_deps
->last_function_call
,
2656 succ_deps
->last_function_call
);
2658 /* last_function_call_may_noreturn is inherited by successor. */
2659 succ_deps
->last_function_call_may_noreturn
2660 = concat_INSN_LIST (pred_deps
->last_function_call_may_noreturn
,
2661 succ_deps
->last_function_call_may_noreturn
);
2663 /* sched_before_next_call is inherited by successor. */
2664 succ_deps
->sched_before_next_call
2665 = concat_INSN_LIST (pred_deps
->sched_before_next_call
,
2666 succ_deps
->sched_before_next_call
);
2669 /* After computing the dependencies for block BB, propagate the dependencies
2670 found in TMP_DEPS to the successors of the block. */
2672 propagate_deps (int bb
, struct deps_desc
*pred_deps
)
2674 basic_block block
= BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (bb
));
2678 /* bb's structures are inherited by its successors. */
2679 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2681 /* Only bbs "below" bb, in the same region, are interesting. */
2682 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2683 || CONTAINING_RGN (block
->index
) != CONTAINING_RGN (e
->dest
->index
)
2684 || BLOCK_TO_BB (e
->dest
->index
) <= bb
)
2687 deps_join (bb_deps
+ BLOCK_TO_BB (e
->dest
->index
), pred_deps
);
2690 /* These lists should point to the right place, for correct
2692 bb_deps
[bb
].pending_read_insns
= pred_deps
->pending_read_insns
;
2693 bb_deps
[bb
].pending_read_mems
= pred_deps
->pending_read_mems
;
2694 bb_deps
[bb
].pending_write_insns
= pred_deps
->pending_write_insns
;
2695 bb_deps
[bb
].pending_write_mems
= pred_deps
->pending_write_mems
;
2696 bb_deps
[bb
].pending_jump_insns
= pred_deps
->pending_jump_insns
;
2698 /* Can't allow these to be freed twice. */
2699 pred_deps
->pending_read_insns
= 0;
2700 pred_deps
->pending_read_mems
= 0;
2701 pred_deps
->pending_write_insns
= 0;
2702 pred_deps
->pending_write_mems
= 0;
2703 pred_deps
->pending_jump_insns
= 0;
2706 /* Compute dependences inside bb. In a multiple blocks region:
2707 (1) a bb is analyzed after its predecessors, and (2) the lists in
2708 effect at the end of bb (after analyzing for bb) are inherited by
2711 Specifically for reg-reg data dependences, the block insns are
2712 scanned by sched_analyze () top-to-bottom. Three lists are
2713 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2714 reg_last[].implicit_sets for implicit hard register DEFs, and
2715 reg_last[].uses for register USEs.
2717 When analysis is completed for bb, we update for its successors:
2718 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2719 ; - IMPLICIT_DEFS[succ] = Union (IMPLICIT_DEFS [succ], IMPLICIT_DEFS [bb])
2720 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2722 The mechanism for computing mem-mem data dependence is very
2723 similar, and the result is interblock dependences in the region. */
2726 compute_block_dependences (int bb
)
2728 rtx_insn
*head
, *tail
;
2729 struct deps_desc tmp_deps
;
2731 tmp_deps
= bb_deps
[bb
];
2733 /* Do the analysis for this block. */
2734 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2735 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2737 sched_analyze (&tmp_deps
, head
, tail
);
2739 /* Selective scheduling handles control dependencies by itself. */
2740 if (!sel_sched_p ())
2741 add_branch_dependences (head
, tail
);
2743 if (current_nr_blocks
> 1)
2744 propagate_deps (bb
, &tmp_deps
);
2746 /* Free up the INSN_LISTs. */
2747 free_deps (&tmp_deps
);
2749 if (targetm
.sched
.dependencies_evaluation_hook
)
2750 targetm
.sched
.dependencies_evaluation_hook (head
, tail
);
2753 /* Free dependencies of instructions inside BB. */
2755 free_block_dependencies (int bb
)
2760 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2762 if (no_real_insns_p (head
, tail
))
2765 sched_free_deps (head
, tail
, true);
2768 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2769 them to the unused_*_list variables, so that they can be reused. */
2772 free_pending_lists (void)
2776 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2778 free_INSN_LIST_list (&bb_deps
[bb
].pending_read_insns
);
2779 free_INSN_LIST_list (&bb_deps
[bb
].pending_write_insns
);
2780 free_EXPR_LIST_list (&bb_deps
[bb
].pending_read_mems
);
2781 free_EXPR_LIST_list (&bb_deps
[bb
].pending_write_mems
);
2782 free_INSN_LIST_list (&bb_deps
[bb
].pending_jump_insns
);
2786 /* Print dependences for debugging starting from FROM_BB.
2787 Callable from debugger. */
2788 /* Print dependences for debugging starting from FROM_BB.
2789 Callable from debugger. */
2791 debug_rgn_dependencies (int from_bb
)
2795 fprintf (sched_dump
,
2796 ";; --------------- forward dependences: ------------ \n");
2798 for (bb
= from_bb
; bb
< current_nr_blocks
; bb
++)
2800 rtx_insn
*head
, *tail
;
2802 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2803 fprintf (sched_dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
2804 BB_TO_BLOCK (bb
), bb
);
2806 debug_dependencies (head
, tail
);
2810 /* Print dependencies information for instructions between HEAD and TAIL.
2811 ??? This function would probably fit best in haifa-sched.c. */
2812 void debug_dependencies (rtx_insn
*head
, rtx_insn
*tail
)
2815 rtx_insn
*next_tail
= NEXT_INSN (tail
);
2817 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2818 "insn", "code", "bb", "dep", "prio", "cost",
2820 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2821 "----", "----", "--", "---", "----", "----",
2824 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2826 if (! INSN_P (insn
))
2829 fprintf (sched_dump
, ";; %6d ", INSN_UID (insn
));
2832 n
= NOTE_KIND (insn
);
2833 fprintf (sched_dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
2836 fprintf (sched_dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
2840 fprintf (sched_dump
,
2841 ";; %s%5d%6d%6d%6d%6d%6d ",
2842 (SCHED_GROUP_P (insn
) ? "+" : " "),
2846 sched_emulate_haifa_p
? -1 : sd_lists_size (insn
, SD_LIST_BACK
),
2847 (sel_sched_p () ? (sched_emulate_haifa_p
? -1
2848 : INSN_PRIORITY (insn
))
2849 : INSN_PRIORITY (insn
)),
2850 (sel_sched_p () ? (sched_emulate_haifa_p
? -1
2852 : insn_cost (insn
)));
2854 if (recog_memoized (insn
) < 0)
2855 fprintf (sched_dump
, "nothing");
2857 print_reservation (sched_dump
, insn
);
2859 fprintf (sched_dump
, "\t: ");
2861 sd_iterator_def sd_it
;
2864 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
2865 fprintf (sched_dump
, "%d%s%s ", INSN_UID (DEP_CON (dep
)),
2866 DEP_NONREG (dep
) ? "n" : "",
2867 DEP_MULTIPLE (dep
) ? "m" : "");
2869 fprintf (sched_dump
, "\n");
2872 fprintf (sched_dump
, "\n");
2875 /* Returns true if all the basic blocks of the current region have
2876 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
2878 sched_is_disabled_for_current_region_p (void)
2882 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2883 if (!(BASIC_BLOCK_FOR_FN (cfun
,
2884 BB_TO_BLOCK (bb
))->flags
& BB_DISABLE_SCHEDULE
))
2890 /* Free all region dependencies saved in INSN_BACK_DEPS and
2891 INSN_RESOLVED_BACK_DEPS. The Haifa scheduler does this on the fly
2892 when scheduling, so this function is supposed to be called from
2893 the selective scheduling only. */
2895 free_rgn_deps (void)
2899 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2901 rtx_insn
*head
, *tail
;
2903 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2904 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2906 sched_free_deps (head
, tail
, false);
2910 static int rgn_n_insns
;
2912 /* Compute insn priority for a current region. */
2914 compute_priorities (void)
2918 current_sched_info
->sched_max_insns_priority
= 0;
2919 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2921 rtx_insn
*head
, *tail
;
2923 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2924 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2926 if (no_real_insns_p (head
, tail
))
2929 rgn_n_insns
+= set_priorities (head
, tail
);
2931 current_sched_info
->sched_max_insns_priority
++;
2934 /* (Re-)initialize the arrays of DFA states at the end of each basic block.
2936 SAVED_LAST_BASIC_BLOCK is the previous length of the arrays. It must be
2937 zero for the first call to this function, to allocate the arrays for the
2940 This function is called once during initialization of the scheduler, and
2941 called again to resize the arrays if new basic blocks have been created,
2942 for example for speculation recovery code. */
2945 realloc_bb_state_array (int saved_last_basic_block
)
2947 char *old_bb_state_array
= bb_state_array
;
2948 size_t lbb
= (size_t) last_basic_block_for_fn (cfun
);
2949 size_t slbb
= (size_t) saved_last_basic_block
;
2951 /* Nothing to do if nothing changed since the last time this was called. */
2952 if (saved_last_basic_block
== last_basic_block_for_fn (cfun
))
2955 /* The selective scheduler doesn't use the state arrays. */
2958 gcc_assert (bb_state_array
== NULL
&& bb_state
== NULL
);
2962 gcc_checking_assert (saved_last_basic_block
== 0
2963 || (bb_state_array
!= NULL
&& bb_state
!= NULL
));
2965 bb_state_array
= XRESIZEVEC (char, bb_state_array
, lbb
* dfa_state_size
);
2966 bb_state
= XRESIZEVEC (state_t
, bb_state
, lbb
);
2968 /* If BB_STATE_ARRAY has moved, fixup all the state pointers array.
2969 Otherwise only fixup the newly allocated ones. For the state
2970 array itself, only initialize the new entries. */
2971 bool bb_state_array_moved
= (bb_state_array
!= old_bb_state_array
);
2972 for (size_t i
= bb_state_array_moved
? 0 : slbb
; i
< lbb
; i
++)
2973 bb_state
[i
] = (state_t
) (bb_state_array
+ i
* dfa_state_size
);
2974 for (size_t i
= slbb
; i
< lbb
; i
++)
2975 state_reset (bb_state
[i
]);
2978 /* Free the arrays of DFA states at the end of each basic block. */
2981 free_bb_state_array (void)
2983 free (bb_state_array
);
2985 bb_state_array
= NULL
;
2989 /* Schedule a region. A region is either an inner loop, a loop-free
2990 subroutine, or a single basic block. Each bb in the region is
2991 scheduled after its flow predecessors. */
2994 schedule_region (int rgn
)
2997 int sched_rgn_n_insns
= 0;
3001 /* Do not support register pressure sensitive scheduling for the new regions
3002 as we don't update the liveness info for them. */
3003 if (sched_pressure
!= SCHED_PRESSURE_NONE
3004 && rgn
>= nr_regions_initial
)
3006 free_global_sched_pressure_data ();
3007 sched_pressure
= SCHED_PRESSURE_NONE
;
3010 rgn_setup_region (rgn
);
3012 /* Don't schedule region that is marked by
3013 NOTE_DISABLE_SCHED_OF_BLOCK. */
3014 if (sched_is_disabled_for_current_region_p ())
3017 sched_rgn_compute_dependencies (rgn
);
3019 sched_rgn_local_init (rgn
);
3021 /* Set priorities. */
3022 compute_priorities ();
3024 sched_extend_ready_list (rgn_n_insns
);
3026 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
3028 sched_init_region_reg_pressure_info ();
3029 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3031 basic_block first_bb
, last_bb
;
3032 rtx_insn
*head
, *tail
;
3034 first_bb
= EBB_FIRST_BB (bb
);
3035 last_bb
= EBB_LAST_BB (bb
);
3037 get_ebb_head_tail (first_bb
, last_bb
, &head
, &tail
);
3039 if (no_real_insns_p (head
, tail
))
3041 gcc_assert (first_bb
== last_bb
);
3044 sched_setup_bb_reg_pressure_info (first_bb
, PREV_INSN (head
));
3048 /* Now we can schedule all blocks. */
3049 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3051 basic_block first_bb
, last_bb
, curr_bb
;
3052 rtx_insn
*head
, *tail
;
3054 first_bb
= EBB_FIRST_BB (bb
);
3055 last_bb
= EBB_LAST_BB (bb
);
3057 get_ebb_head_tail (first_bb
, last_bb
, &head
, &tail
);
3059 if (no_real_insns_p (head
, tail
))
3061 gcc_assert (first_bb
== last_bb
);
3065 current_sched_info
->prev_head
= PREV_INSN (head
);
3066 current_sched_info
->next_tail
= NEXT_INSN (tail
);
3068 remove_notes (head
, tail
);
3070 unlink_bb_notes (first_bb
, last_bb
);
3074 gcc_assert (flag_schedule_interblock
|| current_nr_blocks
== 1);
3075 current_sched_info
->queue_must_finish_empty
= current_nr_blocks
== 1;
3078 if (dbg_cnt (sched_block
))
3081 int saved_last_basic_block
= last_basic_block_for_fn (cfun
);
3083 schedule_block (&curr_bb
, bb_state
[first_bb
->index
]);
3084 gcc_assert (EBB_FIRST_BB (bb
) == first_bb
);
3085 sched_rgn_n_insns
+= sched_n_insns
;
3086 realloc_bb_state_array (saved_last_basic_block
);
3087 f
= find_fallthru_edge (last_bb
->succs
);
3088 if (f
&& f
->probability
* 100 / REG_BR_PROB_BASE
>=
3089 PARAM_VALUE (PARAM_SCHED_STATE_EDGE_PROB_CUTOFF
))
3091 memcpy (bb_state
[f
->dest
->index
], curr_state
,
3093 if (sched_verbose
>= 5)
3094 fprintf (sched_dump
, "saving state for edge %d->%d\n",
3095 f
->src
->index
, f
->dest
->index
);
3100 sched_rgn_n_insns
+= rgn_n_insns
;
3104 if (current_nr_blocks
> 1)
3108 /* Sanity check: verify that all region insns were scheduled. */
3109 gcc_assert (sched_rgn_n_insns
== rgn_n_insns
);
3111 sched_finish_ready_list ();
3113 /* Done with this region. */
3114 sched_rgn_local_finish ();
3116 /* Free dependencies. */
3117 for (bb
= 0; bb
< current_nr_blocks
; ++bb
)
3118 free_block_dependencies (bb
);
3120 gcc_assert (haifa_recovery_bb_ever_added_p
3121 || deps_pools_are_empty_p ());
3124 /* Initialize data structures for region scheduling. */
3127 sched_rgn_init (bool single_blocks_p
)
3129 min_spec_prob
= ((PARAM_VALUE (PARAM_MIN_SPEC_PROB
) * REG_BR_PROB_BASE
)
3137 CONTAINING_RGN (ENTRY_BLOCK
) = -1;
3138 CONTAINING_RGN (EXIT_BLOCK
) = -1;
3140 realloc_bb_state_array (0);
3142 /* Compute regions for scheduling. */
3144 || n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
+ 1
3145 || !flag_schedule_interblock
3146 || is_cfg_nonregular ())
3148 find_single_block_region (sel_sched_p ());
3152 /* Compute the dominators and post dominators. */
3153 if (!sel_sched_p ())
3154 calculate_dominance_info (CDI_DOMINATORS
);
3159 if (sched_verbose
>= 3)
3162 /* For now. This will move as more and more of haifa is converted
3163 to using the cfg code. */
3164 if (!sel_sched_p ())
3165 free_dominance_info (CDI_DOMINATORS
);
3168 gcc_assert (0 < nr_regions
&& nr_regions
<= n_basic_blocks_for_fn (cfun
));
3170 RGN_BLOCKS (nr_regions
) = (RGN_BLOCKS (nr_regions
- 1) +
3171 RGN_NR_BLOCKS (nr_regions
- 1));
3172 nr_regions_initial
= nr_regions
;
3175 /* Free data structures for region scheduling. */
3177 sched_rgn_finish (void)
3179 free_bb_state_array ();
3181 /* Reposition the prologue and epilogue notes in case we moved the
3182 prologue/epilogue insns. */
3183 if (reload_completed
)
3184 reposition_prologue_and_epilogue_notes ();
3188 if (reload_completed
== 0
3189 && flag_schedule_interblock
)
3191 fprintf (sched_dump
,
3192 "\n;; Procedure interblock/speculative motions == %d/%d \n",
3196 gcc_assert (nr_inter
<= 0);
3197 fprintf (sched_dump
, "\n\n");
3205 free (rgn_bb_table
);
3206 rgn_bb_table
= NULL
;
3211 free (containing_rgn
);
3212 containing_rgn
= NULL
;
3218 /* Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
3219 point to the region RGN. */
3221 rgn_setup_region (int rgn
)
3225 /* Set variables for the current region. */
3226 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
3227 current_blocks
= RGN_BLOCKS (rgn
);
3229 /* EBB_HEAD is a region-scope structure. But we realloc it for
3230 each region to save time/memory/something else.
3231 See comments in add_block1, for what reasons we allocate +1 element. */
3232 ebb_head
= XRESIZEVEC (int, ebb_head
, current_nr_blocks
+ 1);
3233 for (bb
= 0; bb
<= current_nr_blocks
; bb
++)
3234 ebb_head
[bb
] = current_blocks
+ bb
;
3237 /* Compute instruction dependencies in region RGN. */
3239 sched_rgn_compute_dependencies (int rgn
)
3241 if (!RGN_DONT_CALC_DEPS (rgn
))
3246 sched_emulate_haifa_p
= 1;
3248 init_deps_global ();
3250 /* Initializations for region data dependence analysis. */
3251 bb_deps
= XNEWVEC (struct deps_desc
, current_nr_blocks
);
3252 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3253 init_deps (bb_deps
+ bb
, false);
3255 /* Initialize bitmap used in add_branch_dependences. */
3256 insn_referenced
= sbitmap_alloc (sched_max_luid
);
3257 bitmap_clear (insn_referenced
);
3259 /* Compute backward dependencies. */
3260 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3261 compute_block_dependences (bb
);
3263 sbitmap_free (insn_referenced
);
3264 free_pending_lists ();
3265 finish_deps_global ();
3268 /* We don't want to recalculate this twice. */
3269 RGN_DONT_CALC_DEPS (rgn
) = 1;
3272 sched_emulate_haifa_p
= 0;
3275 /* (This is a recovery block. It is always a single block region.)
3276 OR (We use selective scheduling.) */
3277 gcc_assert (current_nr_blocks
== 1 || sel_sched_p ());
3280 /* Init region data structures. Returns true if this region should
3281 not be scheduled. */
3283 sched_rgn_local_init (int rgn
)
3287 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
3288 if (current_nr_blocks
> 1)
3294 prob
= XNEWVEC (int, current_nr_blocks
);
3296 dom
= sbitmap_vector_alloc (current_nr_blocks
, current_nr_blocks
);
3297 bitmap_vector_clear (dom
, current_nr_blocks
);
3299 /* Use ->aux to implement EDGE_TO_BIT mapping. */
3301 FOR_EACH_BB_FN (block
, cfun
)
3303 if (CONTAINING_RGN (block
->index
) != rgn
)
3305 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3306 SET_EDGE_TO_BIT (e
, rgn_nr_edges
++);
3309 rgn_edges
= XNEWVEC (edge
, rgn_nr_edges
);
3311 FOR_EACH_BB_FN (block
, cfun
)
3313 if (CONTAINING_RGN (block
->index
) != rgn
)
3315 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3316 rgn_edges
[rgn_nr_edges
++] = e
;
3320 pot_split
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
3321 bitmap_vector_clear (pot_split
, current_nr_blocks
);
3322 ancestor_edges
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
3323 bitmap_vector_clear (ancestor_edges
, current_nr_blocks
);
3325 /* Compute probabilities, dominators, split_edges. */
3326 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3327 compute_dom_prob_ps (bb
);
3329 /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
3330 /* We don't need them anymore. But we want to avoid duplication of
3331 aux fields in the newly created edges. */
3332 FOR_EACH_BB_FN (block
, cfun
)
3334 if (CONTAINING_RGN (block
->index
) != rgn
)
3336 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3342 /* Free data computed for the finished region. */
3344 sched_rgn_local_free (void)
3347 sbitmap_vector_free (dom
);
3348 sbitmap_vector_free (pot_split
);
3349 sbitmap_vector_free (ancestor_edges
);
3353 /* Free data computed for the finished region. */
3355 sched_rgn_local_finish (void)
3357 if (current_nr_blocks
> 1 && !sel_sched_p ())
3359 sched_rgn_local_free ();
3363 /* Setup scheduler infos. */
3365 rgn_setup_common_sched_info (void)
3367 memcpy (&rgn_common_sched_info
, &haifa_common_sched_info
,
3368 sizeof (rgn_common_sched_info
));
3370 rgn_common_sched_info
.fix_recovery_cfg
= rgn_fix_recovery_cfg
;
3371 rgn_common_sched_info
.add_block
= rgn_add_block
;
3372 rgn_common_sched_info
.estimate_number_of_insns
3373 = rgn_estimate_number_of_insns
;
3374 rgn_common_sched_info
.sched_pass_id
= SCHED_RGN_PASS
;
3376 common_sched_info
= &rgn_common_sched_info
;
3379 /* Setup all *_sched_info structures (for the Haifa frontend
3380 and for the dependence analysis) in the interblock scheduler. */
3382 rgn_setup_sched_infos (void)
3384 if (!sel_sched_p ())
3385 memcpy (&rgn_sched_deps_info
, &rgn_const_sched_deps_info
,
3386 sizeof (rgn_sched_deps_info
));
3388 memcpy (&rgn_sched_deps_info
, &rgn_const_sel_sched_deps_info
,
3389 sizeof (rgn_sched_deps_info
));
3391 sched_deps_info
= &rgn_sched_deps_info
;
3393 memcpy (&rgn_sched_info
, &rgn_const_sched_info
, sizeof (rgn_sched_info
));
3394 current_sched_info
= &rgn_sched_info
;
3397 /* The one entry point in this file. */
3399 schedule_insns (void)
3403 /* Taking care of this degenerate case makes the rest of
3404 this code simpler. */
3405 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
3408 rgn_setup_common_sched_info ();
3409 rgn_setup_sched_infos ();
3411 haifa_sched_init ();
3412 sched_rgn_init (reload_completed
);
3414 bitmap_initialize (¬_in_df
, 0);
3415 bitmap_clear (¬_in_df
);
3417 /* Schedule every region in the subroutine. */
3418 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
3419 if (dbg_cnt (sched_region
))
3420 schedule_region (rgn
);
3423 sched_rgn_finish ();
3424 bitmap_clear (¬_in_df
);
3426 haifa_sched_finish ();
3429 /* INSN has been added to/removed from current region. */
3431 rgn_add_remove_insn (rtx_insn
*insn
, int remove_p
)
3438 if (INSN_BB (insn
) == target_bb
)
3447 /* Extend internal data structures. */
3449 extend_regions (void)
3451 rgn_table
= XRESIZEVEC (region
, rgn_table
, n_basic_blocks_for_fn (cfun
));
3452 rgn_bb_table
= XRESIZEVEC (int, rgn_bb_table
,
3453 n_basic_blocks_for_fn (cfun
));
3454 block_to_bb
= XRESIZEVEC (int, block_to_bb
,
3455 last_basic_block_for_fn (cfun
));
3456 containing_rgn
= XRESIZEVEC (int, containing_rgn
,
3457 last_basic_block_for_fn (cfun
));
3461 rgn_make_new_region_out_of_new_block (basic_block bb
)
3465 i
= RGN_BLOCKS (nr_regions
);
3466 /* I - first free position in rgn_bb_table. */
3468 rgn_bb_table
[i
] = bb
->index
;
3469 RGN_NR_BLOCKS (nr_regions
) = 1;
3470 RGN_HAS_REAL_EBB (nr_regions
) = 0;
3471 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
3472 CONTAINING_RGN (bb
->index
) = nr_regions
;
3473 BLOCK_TO_BB (bb
->index
) = 0;
3477 RGN_BLOCKS (nr_regions
) = i
+ 1;
3480 /* BB was added to ebb after AFTER. */
3482 rgn_add_block (basic_block bb
, basic_block after
)
3485 bitmap_set_bit (¬_in_df
, bb
->index
);
3487 if (after
== 0 || after
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3489 rgn_make_new_region_out_of_new_block (bb
);
3490 RGN_DONT_CALC_DEPS (nr_regions
- 1) = (after
3491 == EXIT_BLOCK_PTR_FOR_FN (cfun
));
3497 /* We need to fix rgn_table, block_to_bb, containing_rgn
3500 BLOCK_TO_BB (bb
->index
) = BLOCK_TO_BB (after
->index
);
3502 /* We extend ebb_head to one more position to
3503 easily find the last position of the last ebb in
3504 the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
3505 is _always_ valid for access. */
3507 i
= BLOCK_TO_BB (after
->index
) + 1;
3508 pos
= ebb_head
[i
] - 1;
3509 /* Now POS is the index of the last block in the region. */
3511 /* Find index of basic block AFTER. */
3512 for (; rgn_bb_table
[pos
] != after
->index
; pos
--)
3516 gcc_assert (pos
> ebb_head
[i
- 1]);
3518 /* i - ebb right after "AFTER". */
3519 /* ebb_head[i] - VALID. */
3521 /* Source position: ebb_head[i]
3522 Destination position: ebb_head[i] + 1
3524 RGN_BLOCKS (nr_regions) - 1
3525 Number of elements to copy: (last_position) - (source_position) + 1
3528 memmove (rgn_bb_table
+ pos
+ 1,
3530 ((RGN_BLOCKS (nr_regions
) - 1) - (pos
) + 1)
3531 * sizeof (*rgn_bb_table
));
3533 rgn_bb_table
[pos
] = bb
->index
;
3535 for (; i
<= current_nr_blocks
; i
++)
3538 i
= CONTAINING_RGN (after
->index
);
3539 CONTAINING_RGN (bb
->index
) = i
;
3541 RGN_HAS_REAL_EBB (i
) = 1;
3543 for (++i
; i
<= nr_regions
; i
++)
3548 /* Fix internal data after interblock movement of jump instruction.
3549 For parameter meaning please refer to
3550 sched-int.h: struct sched_info: fix_recovery_cfg. */
3552 rgn_fix_recovery_cfg (int bbi
, int check_bbi
, int check_bb_nexti
)
3554 int old_pos
, new_pos
, i
;
3556 BLOCK_TO_BB (check_bb_nexti
) = BLOCK_TO_BB (bbi
);
3558 for (old_pos
= ebb_head
[BLOCK_TO_BB (check_bbi
) + 1] - 1;
3559 rgn_bb_table
[old_pos
] != check_bb_nexti
;
3562 gcc_assert (old_pos
> ebb_head
[BLOCK_TO_BB (check_bbi
)]);
3564 for (new_pos
= ebb_head
[BLOCK_TO_BB (bbi
) + 1] - 1;
3565 rgn_bb_table
[new_pos
] != bbi
;
3569 gcc_assert (new_pos
> ebb_head
[BLOCK_TO_BB (bbi
)]);
3571 gcc_assert (new_pos
< old_pos
);
3573 memmove (rgn_bb_table
+ new_pos
+ 1,
3574 rgn_bb_table
+ new_pos
,
3575 (old_pos
- new_pos
) * sizeof (*rgn_bb_table
));
3577 rgn_bb_table
[new_pos
] = check_bb_nexti
;
3579 for (i
= BLOCK_TO_BB (bbi
) + 1; i
<= BLOCK_TO_BB (check_bbi
); i
++)
3583 /* Return next block in ebb chain. For parameter meaning please refer to
3584 sched-int.h: struct sched_info: advance_target_bb. */
3586 advance_target_bb (basic_block bb
, rtx_insn
*insn
)
3591 gcc_assert (BLOCK_TO_BB (bb
->index
) == target_bb
3592 && BLOCK_TO_BB (bb
->next_bb
->index
) == target_bb
);
3598 /* Run instruction scheduler. */
3600 rest_of_handle_live_range_shrinkage (void)
3602 #ifdef INSN_SCHEDULING
3605 initialize_live_range_shrinkage ();
3606 saved
= flag_schedule_interblock
;
3607 flag_schedule_interblock
= false;
3609 flag_schedule_interblock
= saved
;
3610 finish_live_range_shrinkage ();
3615 /* Run instruction scheduler. */
3617 rest_of_handle_sched (void)
3619 #ifdef INSN_SCHEDULING
3620 if (flag_selective_scheduling
3621 && ! maybe_skip_selective_scheduling ())
3622 run_selective_scheduling ();
3629 /* Run second scheduling pass after reload. */
3631 rest_of_handle_sched2 (void)
3633 #ifdef INSN_SCHEDULING
3634 if (flag_selective_scheduling2
3635 && ! maybe_skip_selective_scheduling ())
3636 run_selective_scheduling ();
3639 /* Do control and data sched analysis again,
3640 and write some more of the results to dump file. */
3641 if (flag_sched2_use_superblocks
)
3652 const pass_data pass_data_live_range_shrinkage
=
3654 RTL_PASS
, /* type */
3655 "lr_shrinkage", /* name */
3656 OPTGROUP_NONE
, /* optinfo_flags */
3657 TV_LIVE_RANGE_SHRINKAGE
, /* tv_id */
3658 0, /* properties_required */
3659 0, /* properties_provided */
3660 0, /* properties_destroyed */
3661 0, /* todo_flags_start */
3662 TODO_df_finish
, /* todo_flags_finish */
3665 class pass_live_range_shrinkage
: public rtl_opt_pass
3668 pass_live_range_shrinkage(gcc::context
*ctxt
)
3669 : rtl_opt_pass(pass_data_live_range_shrinkage
, ctxt
)
3672 /* opt_pass methods: */
3673 virtual bool gate (function
*)
3675 #ifdef INSN_SCHEDULING
3676 return flag_live_range_shrinkage
;
3682 virtual unsigned int execute (function
*)
3684 return rest_of_handle_live_range_shrinkage ();
3687 }; // class pass_live_range_shrinkage
3692 make_pass_live_range_shrinkage (gcc::context
*ctxt
)
3694 return new pass_live_range_shrinkage (ctxt
);
3699 const pass_data pass_data_sched
=
3701 RTL_PASS
, /* type */
3702 "sched1", /* name */
3703 OPTGROUP_NONE
, /* optinfo_flags */
3704 TV_SCHED
, /* tv_id */
3705 0, /* properties_required */
3706 0, /* properties_provided */
3707 0, /* properties_destroyed */
3708 0, /* todo_flags_start */
3709 TODO_df_finish
, /* todo_flags_finish */
3712 class pass_sched
: public rtl_opt_pass
3715 pass_sched (gcc::context
*ctxt
)
3716 : rtl_opt_pass (pass_data_sched
, ctxt
)
3719 /* opt_pass methods: */
3720 virtual bool gate (function
*);
3721 virtual unsigned int execute (function
*) { return rest_of_handle_sched (); }
3723 }; // class pass_sched
3726 pass_sched::gate (function
*)
3728 #ifdef INSN_SCHEDULING
3729 return optimize
> 0 && flag_schedule_insns
&& dbg_cnt (sched_func
);
3738 make_pass_sched (gcc::context
*ctxt
)
3740 return new pass_sched (ctxt
);
3745 const pass_data pass_data_sched2
=
3747 RTL_PASS
, /* type */
3748 "sched2", /* name */
3749 OPTGROUP_NONE
, /* optinfo_flags */
3750 TV_SCHED2
, /* tv_id */
3751 0, /* properties_required */
3752 0, /* properties_provided */
3753 0, /* properties_destroyed */
3754 0, /* todo_flags_start */
3755 TODO_df_finish
, /* todo_flags_finish */
3758 class pass_sched2
: public rtl_opt_pass
3761 pass_sched2 (gcc::context
*ctxt
)
3762 : rtl_opt_pass (pass_data_sched2
, ctxt
)
3765 /* opt_pass methods: */
3766 virtual bool gate (function
*);
3767 virtual unsigned int execute (function
*)
3769 return rest_of_handle_sched2 ();
3772 }; // class pass_sched2
3775 pass_sched2::gate (function
*)
3777 #ifdef INSN_SCHEDULING
3778 return optimize
> 0 && flag_schedule_insns_after_reload
3779 && !targetm
.delay_sched2
&& dbg_cnt (sched2_func
);
3788 make_pass_sched2 (gcc::context
*ctxt
)
3790 return new pass_sched2 (ctxt
);