1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010, 2011
4 Free Software Foundation, Inc.
5 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6 and currently maintained by, Jim Wilson (wilson@cygnus.com)
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 /* This pass implements list scheduling within basic blocks. It is
25 run twice: (1) after flow analysis, but before register allocation,
26 and (2) after register allocation.
28 The first run performs interblock scheduling, moving insns between
29 different blocks in the same "region", and the second runs only
30 basic block scheduling.
32 Interblock motions performed are useful motions and speculative
33 motions, including speculative loads. Motions requiring code
34 duplication are not supported. The identification of motion type
35 and the check for validity of speculative motions requires
36 construction and analysis of the function's control flow graph.
38 The main entry point for this pass is schedule_insns(), called for
39 each function. The work of the scheduler is organized in three
40 levels: (1) function level: insns are subject to splitting,
41 control-flow-graph is constructed, regions are computed (after
42 reload, each region is of one block), (2) region level: control
43 flow graph attributes required for interblock scheduling are
44 computed (dominators, reachability, etc.), data dependences and
45 priorities are computed, and (3) block level: insns in the block
46 are actually scheduled. */
50 #include "coretypes.h"
52 #include "diagnostic-core.h"
55 #include "hard-reg-set.h"
59 #include "insn-config.h"
60 #include "insn-attr.h"
64 #include "sched-int.h"
65 #include "sel-sched.h"
67 #include "tree-pass.h"
70 #ifdef INSN_SCHEDULING
72 /* Some accessor macros for h_i_d members only used within this file. */
73 #define FED_BY_SPEC_LOAD(INSN) (HID (INSN)->fed_by_spec_load)
74 #define IS_LOAD_INSN(INSN) (HID (insn)->is_load_insn)
76 /* nr_inter/spec counts interblock/speculative motion for the function. */
77 static int nr_inter
, nr_spec
;
79 static int is_cfg_nonregular (void);
81 /* Number of regions in the procedure. */
84 /* Table of region descriptions. */
85 region
*rgn_table
= NULL
;
87 /* Array of lists of regions' blocks. */
88 int *rgn_bb_table
= NULL
;
90 /* Topological order of blocks in the region (if b2 is reachable from
91 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
92 always referred to by either block or b, while its topological
93 order name (in the region) is referred to by bb. */
94 int *block_to_bb
= NULL
;
96 /* The number of the region containing a block. */
97 int *containing_rgn
= NULL
;
99 /* ebb_head [i] - is index in rgn_bb_table of the head basic block of i'th ebb.
100 Currently we can get a ebb only through splitting of currently
101 scheduling block, therefore, we don't need ebb_head array for every region,
102 hence, its sufficient to hold it for current one only. */
103 int *ebb_head
= NULL
;
105 /* The minimum probability of reaching a source block so that it will be
106 considered for speculative scheduling. */
107 static int min_spec_prob
;
109 static void find_single_block_region (bool);
110 static void find_rgns (void);
111 static bool too_large (int, int *, int *);
113 /* Blocks of the current region being scheduled. */
114 int current_nr_blocks
;
117 /* A speculative motion requires checking live information on the path
118 from 'source' to 'target'. The split blocks are those to be checked.
119 After a speculative motion, live information should be modified in
122 Lists of split and update blocks for each candidate of the current
123 target are in array bblst_table. */
124 static basic_block
*bblst_table
;
125 static int bblst_size
, bblst_last
;
127 /* Target info declarations.
129 The block currently being scheduled is referred to as the "target" block,
130 while other blocks in the region from which insns can be moved to the
131 target are called "source" blocks. The candidate structure holds info
132 about such sources: are they valid? Speculative? Etc. */
135 basic_block
*first_member
;
150 static candidate
*candidate_table
;
151 #define IS_VALID(src) (candidate_table[src].is_valid)
152 #define IS_SPECULATIVE(src) (candidate_table[src].is_speculative)
153 #define IS_SPECULATIVE_INSN(INSN) \
154 (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
155 #define SRC_PROB(src) ( candidate_table[src].src_prob )
157 /* The bb being currently scheduled. */
168 static edge
*edgelst_table
;
169 static int edgelst_last
;
171 static void extract_edgelst (sbitmap
, edgelst
*);
173 /* Target info functions. */
174 static void split_edges (int, int, edgelst
*);
175 static void compute_trg_info (int);
176 void debug_candidate (int);
177 void debug_candidates (int);
179 /* Dominators array: dom[i] contains the sbitmap of dominators of
180 bb i in the region. */
183 /* bb 0 is the only region entry. */
184 #define IS_RGN_ENTRY(bb) (!bb)
186 /* Is bb_src dominated by bb_trg. */
187 #define IS_DOMINATED(bb_src, bb_trg) \
188 ( TEST_BIT (dom[bb_src], bb_trg) )
190 /* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
191 the probability of bb i relative to the region entry. */
194 /* Bit-set of edges, where bit i stands for edge i. */
195 typedef sbitmap edgeset
;
197 /* Number of edges in the region. */
198 static int rgn_nr_edges
;
200 /* Array of size rgn_nr_edges. */
201 static edge
*rgn_edges
;
203 /* Mapping from each edge in the graph to its number in the rgn. */
204 #define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
205 #define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
207 /* The split edges of a source bb is different for each target
208 bb. In order to compute this efficiently, the 'potential-split edges'
209 are computed for each bb prior to scheduling a region. This is actually
210 the split edges of each bb relative to the region entry.
212 pot_split[bb] is the set of potential split edges of bb. */
213 static edgeset
*pot_split
;
215 /* For every bb, a set of its ancestor edges. */
216 static edgeset
*ancestor_edges
;
218 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
220 /* Speculative scheduling functions. */
221 static int check_live_1 (int, rtx
);
222 static void update_live_1 (int, rtx
);
223 static int is_pfree (rtx
, int, int);
224 static int find_conditional_protection (rtx
, int);
225 static int is_conditionally_protected (rtx
, int, int);
226 static int is_prisky (rtx
, int, int);
227 static int is_exception_free (rtx
, int, int);
229 static bool sets_likely_spilled (rtx
);
230 static void sets_likely_spilled_1 (rtx
, const_rtx
, void *);
231 static void add_branch_dependences (rtx
, rtx
);
232 static void compute_block_dependences (int);
234 static void schedule_region (int);
235 static void concat_insn_mem_list (rtx
, rtx
, rtx
*, rtx
*);
236 static void propagate_deps (int, struct deps_desc
*);
237 static void free_pending_lists (void);
239 /* Functions for construction of the control flow graph. */
241 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
243 We decide not to build the control flow graph if there is possibly more
244 than one entry to the function, if computed branches exist, if we
245 have nonlocal gotos, or if we have an unreachable loop. */
248 is_cfg_nonregular (void)
253 /* If we have a label that could be the target of a nonlocal goto, then
254 the cfg is not well structured. */
255 if (nonlocal_goto_handler_labels
)
258 /* If we have any forced labels, then the cfg is not well structured. */
262 /* If we have exception handlers, then we consider the cfg not well
263 structured. ?!? We should be able to handle this now that we
264 compute an accurate cfg for EH. */
265 if (current_function_has_exception_handlers ())
268 /* If we have insns which refer to labels as non-jumped-to operands,
269 then we consider the cfg not well structured. */
271 FOR_BB_INSNS (b
, insn
)
273 rtx note
, next
, set
, dest
;
275 /* If this function has a computed jump, then we consider the cfg
276 not well structured. */
277 if (JUMP_P (insn
) && computed_jump_p (insn
))
283 note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
);
284 if (note
== NULL_RTX
)
287 /* For that label not to be seen as a referred-to label, this
288 must be a single-set which is feeding a jump *only*. This
289 could be a conditional jump with the label split off for
290 machine-specific reasons or a casesi/tablejump. */
291 next
= next_nonnote_insn (insn
);
294 || (JUMP_LABEL (next
) != XEXP (note
, 0)
295 && find_reg_note (next
, REG_LABEL_TARGET
,
296 XEXP (note
, 0)) == NULL_RTX
)
297 || BLOCK_FOR_INSN (insn
) != BLOCK_FOR_INSN (next
))
300 set
= single_set (insn
);
304 dest
= SET_DEST (set
);
305 if (!REG_P (dest
) || !dead_or_set_p (next
, dest
))
309 /* Unreachable loops with more than one basic block are detected
310 during the DFS traversal in find_rgns.
312 Unreachable loops with a single block are detected here. This
313 test is redundant with the one in find_rgns, but it's much
314 cheaper to go ahead and catch the trivial case here. */
317 if (EDGE_COUNT (b
->preds
) == 0
318 || (single_pred_p (b
)
319 && single_pred (b
) == b
))
323 /* All the tests passed. Consider the cfg well structured. */
327 /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */
330 extract_edgelst (sbitmap set
, edgelst
*el
)
333 sbitmap_iterator sbi
;
335 /* edgelst table space is reused in each call to extract_edgelst. */
338 el
->first_member
= &edgelst_table
[edgelst_last
];
341 /* Iterate over each word in the bitset. */
342 EXECUTE_IF_SET_IN_SBITMAP (set
, 0, i
, sbi
)
344 edgelst_table
[edgelst_last
++] = rgn_edges
[i
];
349 /* Functions for the construction of regions. */
351 /* Print the regions, for debugging purposes. Callable from debugger. */
358 fprintf (sched_dump
, "\n;; ------------ REGIONS ----------\n\n");
359 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
361 fprintf (sched_dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
362 rgn_table
[rgn
].rgn_nr_blocks
);
363 fprintf (sched_dump
, ";;\tbb/block: ");
365 /* We don't have ebb_head initialized yet, so we can't use
367 current_blocks
= RGN_BLOCKS (rgn
);
369 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
370 fprintf (sched_dump
, " %d/%d ", bb
, rgn_bb_table
[current_blocks
+ bb
]);
372 fprintf (sched_dump
, "\n\n");
376 /* Print the region's basic blocks. */
379 debug_region (int rgn
)
383 fprintf (stderr
, "\n;; ------------ REGION %d ----------\n\n", rgn
);
384 fprintf (stderr
, ";;\trgn %d nr_blocks %d:\n", rgn
,
385 rgn_table
[rgn
].rgn_nr_blocks
);
386 fprintf (stderr
, ";;\tbb/block: ");
388 /* We don't have ebb_head initialized yet, so we can't use
390 current_blocks
= RGN_BLOCKS (rgn
);
392 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
393 fprintf (stderr
, " %d/%d ", bb
, rgn_bb_table
[current_blocks
+ bb
]);
395 fprintf (stderr
, "\n\n");
397 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
399 dump_bb (stderr
, BASIC_BLOCK (rgn_bb_table
[current_blocks
+ bb
]),
401 fprintf (stderr
, "\n");
404 fprintf (stderr
, "\n");
408 /* True when a bb with index BB_INDEX contained in region RGN. */
410 bb_in_region_p (int bb_index
, int rgn
)
414 for (i
= 0; i
< rgn_table
[rgn
].rgn_nr_blocks
; i
++)
415 if (rgn_bb_table
[current_blocks
+ i
] == bb_index
)
421 /* Dump region RGN to file F using dot syntax. */
423 dump_region_dot (FILE *f
, int rgn
)
427 fprintf (f
, "digraph Region_%d {\n", rgn
);
429 /* We don't have ebb_head initialized yet, so we can't use
431 current_blocks
= RGN_BLOCKS (rgn
);
433 for (i
= 0; i
< rgn_table
[rgn
].rgn_nr_blocks
; i
++)
437 int src_bb_num
= rgn_bb_table
[current_blocks
+ i
];
438 basic_block bb
= BASIC_BLOCK (src_bb_num
);
440 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
441 if (bb_in_region_p (e
->dest
->index
, rgn
))
442 fprintf (f
, "\t%d -> %d\n", src_bb_num
, e
->dest
->index
);
447 /* The same, but first open a file specified by FNAME. */
449 dump_region_dot_file (const char *fname
, int rgn
)
451 FILE *f
= fopen (fname
, "wt");
452 dump_region_dot (f
, rgn
);
456 /* Build a single block region for each basic block in the function.
457 This allows for using the same code for interblock and basic block
461 find_single_block_region (bool ebbs_p
)
463 basic_block bb
, ebb_start
;
469 int probability_cutoff
;
470 if (profile_info
&& flag_branch_probabilities
)
471 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK
);
473 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY
);
474 probability_cutoff
= REG_BR_PROB_BASE
/ 100 * probability_cutoff
;
476 FOR_EACH_BB (ebb_start
)
478 RGN_NR_BLOCKS (nr_regions
) = 0;
479 RGN_BLOCKS (nr_regions
) = i
;
480 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
481 RGN_HAS_REAL_EBB (nr_regions
) = 0;
483 for (bb
= ebb_start
; ; bb
= bb
->next_bb
)
487 rgn_bb_table
[i
] = bb
->index
;
488 RGN_NR_BLOCKS (nr_regions
)++;
489 CONTAINING_RGN (bb
->index
) = nr_regions
;
490 BLOCK_TO_BB (bb
->index
) = i
- RGN_BLOCKS (nr_regions
);
493 if (bb
->next_bb
== EXIT_BLOCK_PTR
494 || LABEL_P (BB_HEAD (bb
->next_bb
)))
497 e
= find_fallthru_edge (bb
->succs
);
500 if (e
->probability
<= probability_cutoff
)
511 rgn_bb_table
[nr_regions
] = bb
->index
;
512 RGN_NR_BLOCKS (nr_regions
) = 1;
513 RGN_BLOCKS (nr_regions
) = nr_regions
;
514 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
515 RGN_HAS_REAL_EBB (nr_regions
) = 0;
517 CONTAINING_RGN (bb
->index
) = nr_regions
;
518 BLOCK_TO_BB (bb
->index
) = 0;
523 /* Estimate number of the insns in the BB. */
525 rgn_estimate_number_of_insns (basic_block bb
)
529 count
= INSN_LUID (BB_END (bb
)) - INSN_LUID (BB_HEAD (bb
));
531 if (MAY_HAVE_DEBUG_INSNS
)
535 FOR_BB_INSNS (bb
, insn
)
536 if (DEBUG_INSN_P (insn
))
543 /* Update number of blocks and the estimate for number of insns
544 in the region. Return true if the region is "too large" for interblock
545 scheduling (compile time considerations). */
548 too_large (int block
, int *num_bbs
, int *num_insns
)
551 (*num_insns
) += (common_sched_info
->estimate_number_of_insns
552 (BASIC_BLOCK (block
)));
554 return ((*num_bbs
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS
))
555 || (*num_insns
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS
)));
558 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
559 is still an inner loop. Put in max_hdr[blk] the header of the most inner
560 loop containing blk. */
561 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
563 if (max_hdr[blk] == -1) \
564 max_hdr[blk] = hdr; \
565 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
566 RESET_BIT (inner, hdr); \
567 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
569 RESET_BIT (inner,max_hdr[blk]); \
570 max_hdr[blk] = hdr; \
574 /* Find regions for interblock scheduling.
576 A region for scheduling can be:
578 * A loop-free procedure, or
580 * A reducible inner loop, or
582 * A basic block not contained in any other region.
584 ?!? In theory we could build other regions based on extended basic
585 blocks or reverse extended basic blocks. Is it worth the trouble?
587 Loop blocks that form a region are put into the region's block list
588 in topological order.
590 This procedure stores its results into the following global (ick) variables
598 We use dominator relationships to avoid making regions out of non-reducible
601 This procedure needs to be converted to work on pred/succ lists instead
602 of edge tables. That would simplify it somewhat. */
605 haifa_find_rgns (void)
607 int *max_hdr
, *dfs_nr
, *degree
;
609 int node
, child
, loop_head
, i
, head
, tail
;
610 int count
= 0, sp
, idx
= 0;
611 edge_iterator current_edge
;
612 edge_iterator
*stack
;
613 int num_bbs
, num_insns
, unreachable
;
614 int too_large_failure
;
617 /* Note if a block is a natural loop header. */
620 /* Note if a block is a natural inner loop header. */
623 /* Note if a block is in the block queue. */
626 /* Note if a block is in the block queue. */
629 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
630 and a mapping from block to its loop header (if the block is contained
633 Store results in HEADER, INNER, and MAX_HDR respectively, these will
634 be used as inputs to the second traversal.
636 STACK, SP and DFS_NR are only used during the first traversal. */
638 /* Allocate and initialize variables for the first traversal. */
639 max_hdr
= XNEWVEC (int, last_basic_block
);
640 dfs_nr
= XCNEWVEC (int, last_basic_block
);
641 stack
= XNEWVEC (edge_iterator
, n_edges
);
643 inner
= sbitmap_alloc (last_basic_block
);
644 sbitmap_ones (inner
);
646 header
= sbitmap_alloc (last_basic_block
);
647 sbitmap_zero (header
);
649 in_queue
= sbitmap_alloc (last_basic_block
);
650 sbitmap_zero (in_queue
);
652 in_stack
= sbitmap_alloc (last_basic_block
);
653 sbitmap_zero (in_stack
);
655 for (i
= 0; i
< last_basic_block
; i
++)
658 #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
659 #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
661 /* DFS traversal to find inner loops in the cfg. */
663 current_edge
= ei_start (single_succ (ENTRY_BLOCK_PTR
)->succs
);
668 if (EDGE_PASSED (current_edge
))
670 /* We have reached a leaf node or a node that was already
671 processed. Pop edges off the stack until we find
672 an edge that has not yet been processed. */
673 while (sp
>= 0 && EDGE_PASSED (current_edge
))
675 /* Pop entry off the stack. */
676 current_edge
= stack
[sp
--];
677 node
= ei_edge (current_edge
)->src
->index
;
678 gcc_assert (node
!= ENTRY_BLOCK
);
679 child
= ei_edge (current_edge
)->dest
->index
;
680 gcc_assert (child
!= EXIT_BLOCK
);
681 RESET_BIT (in_stack
, child
);
682 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
683 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
684 ei_next (¤t_edge
);
687 /* See if have finished the DFS tree traversal. */
688 if (sp
< 0 && EDGE_PASSED (current_edge
))
691 /* Nope, continue the traversal with the popped node. */
695 /* Process a node. */
696 node
= ei_edge (current_edge
)->src
->index
;
697 gcc_assert (node
!= ENTRY_BLOCK
);
698 SET_BIT (in_stack
, node
);
699 dfs_nr
[node
] = ++count
;
701 /* We don't traverse to the exit block. */
702 child
= ei_edge (current_edge
)->dest
->index
;
703 if (child
== EXIT_BLOCK
)
705 SET_EDGE_PASSED (current_edge
);
706 ei_next (¤t_edge
);
710 /* If the successor is in the stack, then we've found a loop.
711 Mark the loop, if it is not a natural loop, then it will
712 be rejected during the second traversal. */
713 if (TEST_BIT (in_stack
, child
))
716 SET_BIT (header
, child
);
717 UPDATE_LOOP_RELATIONS (node
, child
);
718 SET_EDGE_PASSED (current_edge
);
719 ei_next (¤t_edge
);
723 /* If the child was already visited, then there is no need to visit
724 it again. Just update the loop relationships and restart
728 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
729 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
730 SET_EDGE_PASSED (current_edge
);
731 ei_next (¤t_edge
);
735 /* Push an entry on the stack and continue DFS traversal. */
736 stack
[++sp
] = current_edge
;
737 SET_EDGE_PASSED (current_edge
);
738 current_edge
= ei_start (ei_edge (current_edge
)->dest
->succs
);
741 /* Reset ->aux field used by EDGE_PASSED. */
746 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
751 /* Another check for unreachable blocks. The earlier test in
752 is_cfg_nonregular only finds unreachable blocks that do not
755 The DFS traversal will mark every block that is reachable from
756 the entry node by placing a nonzero value in dfs_nr. Thus if
757 dfs_nr is zero for any block, then it must be unreachable. */
760 if (dfs_nr
[bb
->index
] == 0)
766 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
767 to hold degree counts. */
771 degree
[bb
->index
] = EDGE_COUNT (bb
->preds
);
773 /* Do not perform region scheduling if there are any unreachable
777 int *queue
, *degree1
= NULL
;
778 /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
779 there basic blocks, which are forced to be region heads.
780 This is done to try to assemble few smaller regions
781 from a too_large region. */
782 sbitmap extended_rgn_header
= NULL
;
783 bool extend_regions_p
;
788 /* Second traversal:find reducible inner loops and topologically sort
789 block of each region. */
791 queue
= XNEWVEC (int, n_basic_blocks
);
793 extend_regions_p
= PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS
) > 0;
794 if (extend_regions_p
)
796 degree1
= XNEWVEC (int, last_basic_block
);
797 extended_rgn_header
= sbitmap_alloc (last_basic_block
);
798 sbitmap_zero (extended_rgn_header
);
801 /* Find blocks which are inner loop headers. We still have non-reducible
802 loops to consider at this point. */
805 if (TEST_BIT (header
, bb
->index
) && TEST_BIT (inner
, bb
->index
))
811 /* Now check that the loop is reducible. We do this separate
812 from finding inner loops so that we do not find a reducible
813 loop which contains an inner non-reducible loop.
815 A simple way to find reducible/natural loops is to verify
816 that each block in the loop is dominated by the loop
819 If there exists a block that is not dominated by the loop
820 header, then the block is reachable from outside the loop
821 and thus the loop is not a natural loop. */
824 /* First identify blocks in the loop, except for the loop
826 if (bb
->index
== max_hdr
[jbb
->index
] && bb
!= jbb
)
828 /* Now verify that the block is dominated by the loop
830 if (!dominated_by_p (CDI_DOMINATORS
, jbb
, bb
))
835 /* If we exited the loop early, then I is the header of
836 a non-reducible loop and we should quit processing it
838 if (jbb
!= EXIT_BLOCK_PTR
)
841 /* I is a header of an inner loop, or block 0 in a subroutine
842 with no loops at all. */
844 too_large_failure
= 0;
845 loop_head
= max_hdr
[bb
->index
];
847 if (extend_regions_p
)
848 /* We save degree in case when we meet a too_large region
849 and cancel it. We need a correct degree later when
850 calling extend_rgns. */
851 memcpy (degree1
, degree
, last_basic_block
* sizeof (int));
853 /* Decrease degree of all I's successors for topological
855 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
856 if (e
->dest
!= EXIT_BLOCK_PTR
)
857 --degree
[e
->dest
->index
];
859 /* Estimate # insns, and count # blocks in the region. */
861 num_insns
= common_sched_info
->estimate_number_of_insns (bb
);
863 /* Find all loop latches (blocks with back edges to the loop
864 header) or all the leaf blocks in the cfg has no loops.
866 Place those blocks into the queue. */
870 /* Leaf nodes have only a single successor which must
872 if (single_succ_p (jbb
)
873 && single_succ (jbb
) == EXIT_BLOCK_PTR
)
875 queue
[++tail
] = jbb
->index
;
876 SET_BIT (in_queue
, jbb
->index
);
878 if (too_large (jbb
->index
, &num_bbs
, &num_insns
))
880 too_large_failure
= 1;
889 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
891 if (e
->src
== ENTRY_BLOCK_PTR
)
894 node
= e
->src
->index
;
896 if (max_hdr
[node
] == loop_head
&& node
!= bb
->index
)
898 /* This is a loop latch. */
899 queue
[++tail
] = node
;
900 SET_BIT (in_queue
, node
);
902 if (too_large (node
, &num_bbs
, &num_insns
))
904 too_large_failure
= 1;
911 /* Now add all the blocks in the loop to the queue.
913 We know the loop is a natural loop; however the algorithm
914 above will not always mark certain blocks as being in the
922 The algorithm in the DFS traversal may not mark B & D as part
923 of the loop (i.e. they will not have max_hdr set to A).
925 We know they can not be loop latches (else they would have
926 had max_hdr set since they'd have a backedge to a dominator
927 block). So we don't need them on the initial queue.
929 We know they are part of the loop because they are dominated
930 by the loop header and can be reached by a backwards walk of
931 the edges starting with nodes on the initial queue.
933 It is safe and desirable to include those nodes in the
934 loop/scheduling region. To do so we would need to decrease
935 the degree of a node if it is the target of a backedge
936 within the loop itself as the node is placed in the queue.
938 We do not do this because I'm not sure that the actual
939 scheduling code will properly handle this case. ?!? */
941 while (head
< tail
&& !too_large_failure
)
944 child
= queue
[++head
];
946 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (child
)->preds
)
948 node
= e
->src
->index
;
950 /* See discussion above about nodes not marked as in
951 this loop during the initial DFS traversal. */
952 if (e
->src
== ENTRY_BLOCK_PTR
953 || max_hdr
[node
] != loop_head
)
958 else if (!TEST_BIT (in_queue
, node
) && node
!= bb
->index
)
960 queue
[++tail
] = node
;
961 SET_BIT (in_queue
, node
);
963 if (too_large (node
, &num_bbs
, &num_insns
))
965 too_large_failure
= 1;
972 if (tail
>= 0 && !too_large_failure
)
974 /* Place the loop header into list of region blocks. */
975 degree
[bb
->index
] = -1;
976 rgn_bb_table
[idx
] = bb
->index
;
977 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
978 RGN_BLOCKS (nr_regions
) = idx
++;
979 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
980 RGN_HAS_REAL_EBB (nr_regions
) = 0;
981 CONTAINING_RGN (bb
->index
) = nr_regions
;
982 BLOCK_TO_BB (bb
->index
) = count
= 0;
984 /* Remove blocks from queue[] when their in degree
985 becomes zero. Repeat until no blocks are left on the
986 list. This produces a topological list of blocks in
993 if (degree
[child
] == 0)
998 rgn_bb_table
[idx
++] = child
;
999 BLOCK_TO_BB (child
) = ++count
;
1000 CONTAINING_RGN (child
) = nr_regions
;
1001 queue
[head
] = queue
[tail
--];
1003 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (child
)->succs
)
1004 if (e
->dest
!= EXIT_BLOCK_PTR
)
1005 --degree
[e
->dest
->index
];
1012 else if (extend_regions_p
)
1014 /* Restore DEGREE. */
1020 /* And force successors of BB to be region heads.
1021 This may provide several smaller regions instead
1022 of one too_large region. */
1023 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1024 if (e
->dest
!= EXIT_BLOCK_PTR
)
1025 SET_BIT (extended_rgn_header
, e
->dest
->index
);
1031 if (extend_regions_p
)
1035 sbitmap_a_or_b (header
, header
, extended_rgn_header
);
1036 sbitmap_free (extended_rgn_header
);
1038 extend_rgns (degree
, &idx
, header
, max_hdr
);
1042 /* Any block that did not end up in a region is placed into a region
1045 if (degree
[bb
->index
] >= 0)
1047 rgn_bb_table
[idx
] = bb
->index
;
1048 RGN_NR_BLOCKS (nr_regions
) = 1;
1049 RGN_BLOCKS (nr_regions
) = idx
++;
1050 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1051 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1052 CONTAINING_RGN (bb
->index
) = nr_regions
++;
1053 BLOCK_TO_BB (bb
->index
) = 0;
1059 sbitmap_free (header
);
1060 sbitmap_free (inner
);
1061 sbitmap_free (in_queue
);
1062 sbitmap_free (in_stack
);
1066 /* Wrapper function.
1067 If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
1068 regions. Otherwise just call find_rgns_haifa. */
1072 if (sel_sched_p () && flag_sel_sched_pipelining
)
1078 static int gather_region_statistics (int **);
1079 static void print_region_statistics (int *, int, int *, int);
1081 /* Calculate the histogram that shows the number of regions having the
1082 given number of basic blocks, and store it in the RSP array. Return
1083 the size of this array. */
1085 gather_region_statistics (int **rsp
)
1087 int i
, *a
= 0, a_sz
= 0;
1089 /* a[i] is the number of regions that have (i + 1) basic blocks. */
1090 for (i
= 0; i
< nr_regions
; i
++)
1092 int nr_blocks
= RGN_NR_BLOCKS (i
);
1094 gcc_assert (nr_blocks
>= 1);
1096 if (nr_blocks
> a_sz
)
1098 a
= XRESIZEVEC (int, a
, nr_blocks
);
1101 while (a_sz
!= nr_blocks
);
1111 /* Print regions statistics. S1 and S2 denote the data before and after
1112 calling extend_rgns, respectively. */
1114 print_region_statistics (int *s1
, int s1_sz
, int *s2
, int s2_sz
)
1118 /* We iterate until s2_sz because extend_rgns does not decrease
1119 the maximal region size. */
1120 for (i
= 1; i
< s2_sz
; i
++)
1134 fprintf (sched_dump
, ";; Region extension statistics: size %d: " \
1135 "was %d + %d more\n", i
+ 1, n1
, n2
- n1
);
1140 DEGREE - Array of incoming edge count, considering only
1141 the edges, that don't have their sources in formed regions yet.
1142 IDXP - pointer to the next available index in rgn_bb_table.
1143 HEADER - set of all region heads.
1144 LOOP_HDR - mapping from block to the containing loop
1145 (two blocks can reside within one region if they have
1146 the same loop header). */
1148 extend_rgns (int *degree
, int *idxp
, sbitmap header
, int *loop_hdr
)
1150 int *order
, i
, rescan
= 0, idx
= *idxp
, iter
= 0, max_iter
, *max_hdr
;
1151 int nblocks
= n_basic_blocks
- NUM_FIXED_BLOCKS
;
1153 max_iter
= PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS
);
1155 max_hdr
= XNEWVEC (int, last_basic_block
);
1157 order
= XNEWVEC (int, last_basic_block
);
1158 post_order_compute (order
, false, false);
1160 for (i
= nblocks
- 1; i
>= 0; i
--)
1163 if (degree
[bbn
] >= 0)
1169 /* This block already was processed in find_rgns. */
1173 /* The idea is to topologically walk through CFG in top-down order.
1174 During the traversal, if all the predecessors of a node are
1175 marked to be in the same region (they all have the same max_hdr),
1176 then current node is also marked to be a part of that region.
1177 Otherwise the node starts its own region.
1178 CFG should be traversed until no further changes are made. On each
1179 iteration the set of the region heads is extended (the set of those
1180 blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
1181 set of all basic blocks, thus the algorithm is guaranteed to
1184 while (rescan
&& iter
< max_iter
)
1188 for (i
= nblocks
- 1; i
>= 0; i
--)
1194 if (max_hdr
[bbn
] != -1 && !TEST_BIT (header
, bbn
))
1198 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (bbn
)->preds
)
1200 int predn
= e
->src
->index
;
1202 if (predn
!= ENTRY_BLOCK
1203 /* If pred wasn't processed in find_rgns. */
1204 && max_hdr
[predn
] != -1
1205 /* And pred and bb reside in the same loop.
1206 (Or out of any loop). */
1207 && loop_hdr
[bbn
] == loop_hdr
[predn
])
1210 /* Then bb extends the containing region of pred. */
1211 hdr
= max_hdr
[predn
];
1212 else if (hdr
!= max_hdr
[predn
])
1213 /* Too bad, there are at least two predecessors
1214 that reside in different regions. Thus, BB should
1215 begin its own region. */
1222 /* BB starts its own region. */
1231 /* If BB start its own region,
1232 update set of headers with BB. */
1233 SET_BIT (header
, bbn
);
1237 gcc_assert (hdr
!= -1);
1246 /* Statistics were gathered on the SPEC2000 package of tests with
1247 mainline weekly snapshot gcc-4.1-20051015 on ia64.
1249 Statistics for SPECint:
1250 1 iteration : 1751 cases (38.7%)
1251 2 iterations: 2770 cases (61.3%)
1252 Blocks wrapped in regions by find_rgns without extension: 18295 blocks
1253 Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
1254 (We don't count single block regions here).
1256 Statistics for SPECfp:
1257 1 iteration : 621 cases (35.9%)
1258 2 iterations: 1110 cases (64.1%)
1259 Blocks wrapped in regions by find_rgns without extension: 6476 blocks
1260 Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
1261 (We don't count single block regions here).
1263 By default we do at most 2 iterations.
1264 This can be overridden with max-sched-extend-regions-iters parameter:
1265 0 - disable region extension,
1266 N > 0 - do at most N iterations. */
1268 if (sched_verbose
&& iter
!= 0)
1269 fprintf (sched_dump
, ";; Region extension iterations: %d%s\n", iter
,
1270 rescan
? "... failed" : "");
1272 if (!rescan
&& iter
!= 0)
1274 int *s1
= NULL
, s1_sz
= 0;
1276 /* Save the old statistics for later printout. */
1277 if (sched_verbose
>= 6)
1278 s1_sz
= gather_region_statistics (&s1
);
1280 /* We have succeeded. Now assemble the regions. */
1281 for (i
= nblocks
- 1; i
>= 0; i
--)
1285 if (max_hdr
[bbn
] == bbn
)
1286 /* BBN is a region head. */
1290 int num_bbs
= 0, j
, num_insns
= 0, large
;
1292 large
= too_large (bbn
, &num_bbs
, &num_insns
);
1295 rgn_bb_table
[idx
] = bbn
;
1296 RGN_BLOCKS (nr_regions
) = idx
++;
1297 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1298 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1299 CONTAINING_RGN (bbn
) = nr_regions
;
1300 BLOCK_TO_BB (bbn
) = 0;
1302 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (bbn
)->succs
)
1303 if (e
->dest
!= EXIT_BLOCK_PTR
)
1304 degree
[e
->dest
->index
]--;
1307 /* Here we check whether the region is too_large. */
1308 for (j
= i
- 1; j
>= 0; j
--)
1310 int succn
= order
[j
];
1311 if (max_hdr
[succn
] == bbn
)
1313 if ((large
= too_large (succn
, &num_bbs
, &num_insns
)))
1319 /* If the region is too_large, then wrap every block of
1320 the region into single block region.
1321 Here we wrap region head only. Other blocks are
1322 processed in the below cycle. */
1324 RGN_NR_BLOCKS (nr_regions
) = 1;
1330 for (j
= i
- 1; j
>= 0; j
--)
1332 int succn
= order
[j
];
1334 if (max_hdr
[succn
] == bbn
)
1335 /* This cycle iterates over all basic blocks, that
1336 are supposed to be in the region with head BBN,
1337 and wraps them into that region (or in single
1340 gcc_assert (degree
[succn
] == 0);
1343 rgn_bb_table
[idx
] = succn
;
1344 BLOCK_TO_BB (succn
) = large
? 0 : num_bbs
++;
1345 CONTAINING_RGN (succn
) = nr_regions
;
1348 /* Wrap SUCCN into single block region. */
1350 RGN_BLOCKS (nr_regions
) = idx
;
1351 RGN_NR_BLOCKS (nr_regions
) = 1;
1352 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1353 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1359 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (succn
)->succs
)
1360 if (e
->dest
!= EXIT_BLOCK_PTR
)
1361 degree
[e
->dest
->index
]--;
1367 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1373 if (sched_verbose
>= 6)
1377 /* Get the new statistics and print the comparison with the
1378 one before calling this function. */
1379 s2_sz
= gather_region_statistics (&s2
);
1380 print_region_statistics (s1
, s1_sz
, s2
, s2_sz
);
1392 /* Functions for regions scheduling information. */
1394 /* Compute dominators, probability, and potential-split-edges of bb.
1395 Assume that these values were already computed for bb's predecessors. */
1398 compute_dom_prob_ps (int bb
)
1400 edge_iterator in_ei
;
1403 /* We shouldn't have any real ebbs yet. */
1404 gcc_assert (ebb_head
[bb
] == bb
+ current_blocks
);
1406 if (IS_RGN_ENTRY (bb
))
1408 SET_BIT (dom
[bb
], 0);
1409 prob
[bb
] = REG_BR_PROB_BASE
;
1415 /* Initialize dom[bb] to '111..1'. */
1416 sbitmap_ones (dom
[bb
]);
1418 FOR_EACH_EDGE (in_edge
, in_ei
, BASIC_BLOCK (BB_TO_BLOCK (bb
))->preds
)
1422 edge_iterator out_ei
;
1424 if (in_edge
->src
== ENTRY_BLOCK_PTR
)
1427 pred_bb
= BLOCK_TO_BB (in_edge
->src
->index
);
1428 sbitmap_a_and_b (dom
[bb
], dom
[bb
], dom
[pred_bb
]);
1429 sbitmap_a_or_b (ancestor_edges
[bb
],
1430 ancestor_edges
[bb
], ancestor_edges
[pred_bb
]);
1432 SET_BIT (ancestor_edges
[bb
], EDGE_TO_BIT (in_edge
));
1434 sbitmap_a_or_b (pot_split
[bb
], pot_split
[bb
], pot_split
[pred_bb
]);
1436 FOR_EACH_EDGE (out_edge
, out_ei
, in_edge
->src
->succs
)
1437 SET_BIT (pot_split
[bb
], EDGE_TO_BIT (out_edge
));
1439 prob
[bb
] += ((prob
[pred_bb
] * in_edge
->probability
) / REG_BR_PROB_BASE
);
1442 SET_BIT (dom
[bb
], bb
);
1443 sbitmap_difference (pot_split
[bb
], pot_split
[bb
], ancestor_edges
[bb
]);
1445 if (sched_verbose
>= 2)
1446 fprintf (sched_dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
),
1447 (100 * prob
[bb
]) / REG_BR_PROB_BASE
);
1450 /* Functions for target info. */
1452 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1453 Note that bb_trg dominates bb_src. */
1456 split_edges (int bb_src
, int bb_trg
, edgelst
*bl
)
1458 sbitmap src
= sbitmap_alloc (pot_split
[bb_src
]->n_bits
);
1459 sbitmap_copy (src
, pot_split
[bb_src
]);
1461 sbitmap_difference (src
, src
, pot_split
[bb_trg
]);
1462 extract_edgelst (src
, bl
);
1466 /* Find the valid candidate-source-blocks for the target block TRG, compute
1467 their probability, and check if they are speculative or not.
1468 For speculative sources, compute their update-blocks and split-blocks. */
1471 compute_trg_info (int trg
)
1474 edgelst el
= { NULL
, 0 };
1475 int i
, j
, k
, update_idx
;
1481 candidate_table
= XNEWVEC (candidate
, current_nr_blocks
);
1484 /* bblst_table holds split blocks and update blocks for each block after
1485 the current one in the region. split blocks and update blocks are
1486 the TO blocks of region edges, so there can be at most rgn_nr_edges
1488 bblst_size
= (current_nr_blocks
- target_bb
) * rgn_nr_edges
;
1489 bblst_table
= XNEWVEC (basic_block
, bblst_size
);
1492 edgelst_table
= XNEWVEC (edge
, rgn_nr_edges
);
1494 /* Define some of the fields for the target bb as well. */
1495 sp
= candidate_table
+ trg
;
1497 sp
->is_speculative
= 0;
1498 sp
->src_prob
= REG_BR_PROB_BASE
;
1500 visited
= sbitmap_alloc (last_basic_block
);
1502 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1504 sp
= candidate_table
+ i
;
1506 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1509 int tf
= prob
[trg
], cf
= prob
[i
];
1511 /* In CFGs with low probability edges TF can possibly be zero. */
1512 sp
->src_prob
= (tf
? ((cf
* REG_BR_PROB_BASE
) / tf
) : 0);
1513 sp
->is_valid
= (sp
->src_prob
>= min_spec_prob
);
1518 split_edges (i
, trg
, &el
);
1519 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1520 if (sp
->is_speculative
&& !flag_schedule_speculative
)
1526 /* Compute split blocks and store them in bblst_table.
1527 The TO block of every split edge is a split block. */
1528 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
1529 sp
->split_bbs
.nr_members
= el
.nr_members
;
1530 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
1531 bblst_table
[bblst_last
] = el
.first_member
[j
]->dest
;
1532 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
1534 /* Compute update blocks and store them in bblst_table.
1535 For every split edge, look at the FROM block, and check
1536 all out edges. For each out edge that is not a split edge,
1537 add the TO block to the update block list. This list can end
1538 up with a lot of duplicates. We need to weed them out to avoid
1539 overrunning the end of the bblst_table. */
1542 sbitmap_zero (visited
);
1543 for (j
= 0; j
< el
.nr_members
; j
++)
1545 block
= el
.first_member
[j
]->src
;
1546 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1548 if (!TEST_BIT (visited
, e
->dest
->index
))
1550 for (k
= 0; k
< el
.nr_members
; k
++)
1551 if (e
== el
.first_member
[k
])
1554 if (k
>= el
.nr_members
)
1556 bblst_table
[bblst_last
++] = e
->dest
;
1557 SET_BIT (visited
, e
->dest
->index
);
1563 sp
->update_bbs
.nr_members
= update_idx
;
1565 /* Make sure we didn't overrun the end of bblst_table. */
1566 gcc_assert (bblst_last
<= bblst_size
);
1570 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
1572 sp
->is_speculative
= 0;
1577 sbitmap_free (visited
);
1580 /* Free the computed target info. */
1582 free_trg_info (void)
1584 free (candidate_table
);
1586 free (edgelst_table
);
1589 /* Print candidates info, for debugging purposes. Callable from debugger. */
1592 debug_candidate (int i
)
1594 if (!candidate_table
[i
].is_valid
)
1597 if (candidate_table
[i
].is_speculative
)
1600 fprintf (sched_dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
1602 fprintf (sched_dump
, "split path: ");
1603 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
1605 int b
= candidate_table
[i
].split_bbs
.first_member
[j
]->index
;
1607 fprintf (sched_dump
, " %d ", b
);
1609 fprintf (sched_dump
, "\n");
1611 fprintf (sched_dump
, "update path: ");
1612 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
1614 int b
= candidate_table
[i
].update_bbs
.first_member
[j
]->index
;
1616 fprintf (sched_dump
, " %d ", b
);
1618 fprintf (sched_dump
, "\n");
1622 fprintf (sched_dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
1626 /* Print candidates info, for debugging purposes. Callable from debugger. */
1629 debug_candidates (int trg
)
1633 fprintf (sched_dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
1634 BB_TO_BLOCK (trg
), trg
);
1635 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1636 debug_candidate (i
);
1639 /* Functions for speculative scheduling. */
1641 static bitmap_head not_in_df
;
1643 /* Return 0 if x is a set of a register alive in the beginning of one
1644 of the split-blocks of src, otherwise return 1. */
1647 check_live_1 (int src
, rtx x
)
1651 rtx reg
= SET_DEST (x
);
1656 while (GET_CODE (reg
) == SUBREG
1657 || GET_CODE (reg
) == ZERO_EXTRACT
1658 || GET_CODE (reg
) == STRICT_LOW_PART
)
1659 reg
= XEXP (reg
, 0);
1661 if (GET_CODE (reg
) == PARALLEL
)
1665 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1666 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1667 if (check_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0)))
1676 regno
= REGNO (reg
);
1678 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
1680 /* Global registers are assumed live. */
1685 if (regno
< FIRST_PSEUDO_REGISTER
)
1687 /* Check for hard registers. */
1688 int j
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1691 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1693 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1694 int t
= bitmap_bit_p (¬_in_df
, b
->index
);
1696 /* We can have split blocks, that were recently generated.
1697 Such blocks are always outside current region. */
1698 gcc_assert (!t
|| (CONTAINING_RGN (b
->index
)
1699 != CONTAINING_RGN (BB_TO_BLOCK (src
))));
1701 if (t
|| REGNO_REG_SET_P (df_get_live_in (b
), regno
+ j
))
1708 /* Check for pseudo registers. */
1709 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1711 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1712 int t
= bitmap_bit_p (¬_in_df
, b
->index
);
1714 gcc_assert (!t
|| (CONTAINING_RGN (b
->index
)
1715 != CONTAINING_RGN (BB_TO_BLOCK (src
))));
1717 if (t
|| REGNO_REG_SET_P (df_get_live_in (b
), regno
))
1726 /* If x is a set of a register R, mark that R is alive in the beginning
1727 of every update-block of src. */
1730 update_live_1 (int src
, rtx x
)
1734 rtx reg
= SET_DEST (x
);
1739 while (GET_CODE (reg
) == SUBREG
1740 || GET_CODE (reg
) == ZERO_EXTRACT
1741 || GET_CODE (reg
) == STRICT_LOW_PART
)
1742 reg
= XEXP (reg
, 0);
1744 if (GET_CODE (reg
) == PARALLEL
)
1748 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1749 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1750 update_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0));
1758 /* Global registers are always live, so the code below does not apply
1761 regno
= REGNO (reg
);
1763 if (! HARD_REGISTER_NUM_P (regno
)
1764 || !global_regs
[regno
])
1766 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
1768 basic_block b
= candidate_table
[src
].update_bbs
.first_member
[i
];
1770 if (HARD_REGISTER_NUM_P (regno
))
1771 bitmap_set_range (df_get_live_in (b
), regno
,
1772 hard_regno_nregs
[regno
][GET_MODE (reg
)]);
1774 bitmap_set_bit (df_get_live_in (b
), regno
);
1779 /* Return 1 if insn can be speculatively moved from block src to trg,
1780 otherwise return 0. Called before first insertion of insn to
1781 ready-list or before the scheduling. */
1784 check_live (rtx insn
, int src
)
1786 /* Find the registers set by instruction. */
1787 if (GET_CODE (PATTERN (insn
)) == SET
1788 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1789 return check_live_1 (src
, PATTERN (insn
));
1790 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1793 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1794 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1795 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1796 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
1805 /* Update the live registers info after insn was moved speculatively from
1806 block src to trg. */
1809 update_live (rtx insn
, int src
)
1811 /* Find the registers set by instruction. */
1812 if (GET_CODE (PATTERN (insn
)) == SET
1813 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1814 update_live_1 (src
, PATTERN (insn
));
1815 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1818 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1819 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1820 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1821 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
1825 /* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1826 #define IS_REACHABLE(bb_from, bb_to) \
1828 || IS_RGN_ENTRY (bb_from) \
1829 || (TEST_BIT (ancestor_edges[bb_to], \
1830 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK (BB_TO_BLOCK (bb_from)))))))
1832 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1835 set_spec_fed (rtx load_insn
)
1837 sd_iterator_def sd_it
;
1840 FOR_EACH_DEP (load_insn
, SD_LIST_FORW
, sd_it
, dep
)
1841 if (DEP_TYPE (dep
) == REG_DEP_TRUE
)
1842 FED_BY_SPEC_LOAD (DEP_CON (dep
)) = 1;
1845 /* On the path from the insn to load_insn_bb, find a conditional
1846 branch depending on insn, that guards the speculative load. */
1849 find_conditional_protection (rtx insn
, int load_insn_bb
)
1851 sd_iterator_def sd_it
;
1854 /* Iterate through DEF-USE forward dependences. */
1855 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
1857 rtx next
= DEP_CON (dep
);
1859 if ((CONTAINING_RGN (BLOCK_NUM (next
)) ==
1860 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
1861 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
1862 && load_insn_bb
!= INSN_BB (next
)
1863 && DEP_TYPE (dep
) == REG_DEP_TRUE
1865 || find_conditional_protection (next
, load_insn_bb
)))
1869 } /* find_conditional_protection */
1871 /* Returns 1 if the same insn1 that participates in the computation
1872 of load_insn's address is feeding a conditional branch that is
1873 guarding on load_insn. This is true if we find two DEF-USE
1875 insn1 -> ... -> conditional-branch
1876 insn1 -> ... -> load_insn,
1877 and if a flow path exists:
1878 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1879 and if insn1 is on the path
1880 region-entry -> ... -> bb_trg -> ... load_insn.
1882 Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
1883 Locate the branch by following INSN_FORW_DEPS from insn1. */
1886 is_conditionally_protected (rtx load_insn
, int bb_src
, int bb_trg
)
1888 sd_iterator_def sd_it
;
1891 FOR_EACH_DEP (load_insn
, SD_LIST_BACK
, sd_it
, dep
)
1893 rtx insn1
= DEP_PRO (dep
);
1895 /* Must be a DEF-USE dependence upon non-branch. */
1896 if (DEP_TYPE (dep
) != REG_DEP_TRUE
1900 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1901 if (INSN_BB (insn1
) == bb_src
1902 || (CONTAINING_RGN (BLOCK_NUM (insn1
))
1903 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
1904 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
1905 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
1908 /* Now search for the conditional-branch. */
1909 if (find_conditional_protection (insn1
, bb_src
))
1912 /* Recursive step: search another insn1, "above" current insn1. */
1913 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
1916 /* The chain does not exist. */
1918 } /* is_conditionally_protected */
1920 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1921 load_insn can move speculatively from bb_src to bb_trg. All the
1922 following must hold:
1924 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1925 (2) load_insn and load1 have a def-use dependence upon
1926 the same insn 'insn1'.
1927 (3) either load2 is in bb_trg, or:
1928 - there's only one split-block, and
1929 - load1 is on the escape path, and
1931 From all these we can conclude that the two loads access memory
1932 addresses that differ at most by a constant, and hence if moving
1933 load_insn would cause an exception, it would have been caused by
1937 is_pfree (rtx load_insn
, int bb_src
, int bb_trg
)
1939 sd_iterator_def back_sd_it
;
1941 candidate
*candp
= candidate_table
+ bb_src
;
1943 if (candp
->split_bbs
.nr_members
!= 1)
1944 /* Must have exactly one escape block. */
1947 FOR_EACH_DEP (load_insn
, SD_LIST_BACK
, back_sd_it
, back_dep
)
1949 rtx insn1
= DEP_PRO (back_dep
);
1951 if (DEP_TYPE (back_dep
) == REG_DEP_TRUE
)
1952 /* Found a DEF-USE dependence (insn1, load_insn). */
1954 sd_iterator_def fore_sd_it
;
1957 FOR_EACH_DEP (insn1
, SD_LIST_FORW
, fore_sd_it
, fore_dep
)
1959 rtx insn2
= DEP_CON (fore_dep
);
1961 if (DEP_TYPE (fore_dep
) == REG_DEP_TRUE
)
1963 /* Found a DEF-USE dependence (insn1, insn2). */
1964 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
1965 /* insn2 not guaranteed to be a 1 base reg load. */
1968 if (INSN_BB (insn2
) == bb_trg
)
1969 /* insn2 is the similar load, in the target block. */
1972 if (*(candp
->split_bbs
.first_member
) == BLOCK_FOR_INSN (insn2
))
1973 /* insn2 is a similar load, in a split-block. */
1980 /* Couldn't find a similar load. */
1984 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1985 a load moved speculatively, or if load_insn is protected by
1986 a compare on load_insn's address). */
1989 is_prisky (rtx load_insn
, int bb_src
, int bb_trg
)
1991 if (FED_BY_SPEC_LOAD (load_insn
))
1994 if (sd_lists_empty_p (load_insn
, SD_LIST_BACK
))
1995 /* Dependence may 'hide' out of the region. */
1998 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2004 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2005 Return 1 if insn is exception-free (and the motion is valid)
2009 is_exception_free (rtx insn
, int bb_src
, int bb_trg
)
2011 int insn_class
= haifa_classify_insn (insn
);
2013 /* Handle non-load insns. */
2024 if (!flag_schedule_speculative_load
)
2026 IS_LOAD_INSN (insn
) = 1;
2033 case PFREE_CANDIDATE
:
2034 if (is_pfree (insn
, bb_src
, bb_trg
))
2036 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2037 case PRISKY_CANDIDATE
:
2038 if (!flag_schedule_speculative_load_dangerous
2039 || is_prisky (insn
, bb_src
, bb_trg
))
2045 return flag_schedule_speculative_load_dangerous
;
2048 /* The number of insns from the current block scheduled so far. */
2049 static int sched_target_n_insns
;
2050 /* The number of insns from the current block to be scheduled in total. */
2051 static int target_n_insns
;
2052 /* The number of insns from the entire region scheduled so far. */
2053 static int sched_n_insns
;
2055 /* Implementations of the sched_info functions for region scheduling. */
2056 static void init_ready_list (void);
2057 static int can_schedule_ready_p (rtx
);
2058 static void begin_schedule_ready (rtx
);
2059 static ds_t
new_ready (rtx
, ds_t
);
2060 static int schedule_more_p (void);
2061 static const char *rgn_print_insn (const_rtx
, int);
2062 static int rgn_rank (rtx
, rtx
);
2063 static void compute_jump_reg_dependencies (rtx
, regset
);
2065 /* Functions for speculative scheduling. */
2066 static void rgn_add_remove_insn (rtx
, int);
2067 static void rgn_add_block (basic_block
, basic_block
);
2068 static void rgn_fix_recovery_cfg (int, int, int);
2069 static basic_block
advance_target_bb (basic_block
, rtx
);
2071 /* Return nonzero if there are more insns that should be scheduled. */
2074 schedule_more_p (void)
2076 return sched_target_n_insns
< target_n_insns
;
2079 /* Add all insns that are initially ready to the ready list READY. Called
2080 once before scheduling a set of insns. */
2083 init_ready_list (void)
2085 rtx prev_head
= current_sched_info
->prev_head
;
2086 rtx next_tail
= current_sched_info
->next_tail
;
2091 sched_target_n_insns
= 0;
2094 /* Print debugging information. */
2095 if (sched_verbose
>= 5)
2096 debug_rgn_dependencies (target_bb
);
2098 /* Prepare current target block info. */
2099 if (current_nr_blocks
> 1)
2100 compute_trg_info (target_bb
);
2102 /* Initialize ready list with all 'ready' insns in target block.
2103 Count number of insns in the target block being scheduled. */
2104 for (insn
= NEXT_INSN (prev_head
); insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2109 gcc_assert (!(TODO_SPEC (insn
) & BEGIN_CONTROL
));
2112 /* Add to ready list all 'ready' insns in valid source blocks.
2113 For speculative insns, check-live, exception-free, and
2115 for (bb_src
= target_bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
2116 if (IS_VALID (bb_src
))
2122 get_ebb_head_tail (EBB_FIRST_BB (bb_src
), EBB_LAST_BB (bb_src
),
2124 src_next_tail
= NEXT_INSN (tail
);
2127 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
2133 /* Called after taking INSN from the ready list. Returns nonzero if this
2134 insn can be scheduled, nonzero if we should silently discard it. */
2137 can_schedule_ready_p (rtx insn
)
2139 /* An interblock motion? */
2140 if (INSN_BB (insn
) != target_bb
2141 && IS_SPECULATIVE_INSN (insn
)
2142 && !check_live (insn
, INSN_BB (insn
)))
2148 /* Updates counter and other information. Split from can_schedule_ready_p ()
2149 because when we schedule insn speculatively then insn passed to
2150 can_schedule_ready_p () differs from the one passed to
2151 begin_schedule_ready (). */
2153 begin_schedule_ready (rtx insn
)
2155 /* An interblock motion? */
2156 if (INSN_BB (insn
) != target_bb
)
2158 if (IS_SPECULATIVE_INSN (insn
))
2160 gcc_assert (check_live (insn
, INSN_BB (insn
)));
2162 update_live (insn
, INSN_BB (insn
));
2164 /* For speculative load, mark insns fed by it. */
2165 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
2166 set_spec_fed (insn
);
2174 /* In block motion. */
2175 sched_target_n_insns
++;
2180 /* Called after INSN has all its hard dependencies resolved and the speculation
2181 of type TS is enough to overcome them all.
2182 Return nonzero if it should be moved to the ready list or the queue, or zero
2183 if we should silently discard it. */
2185 new_ready (rtx next
, ds_t ts
)
2187 if (INSN_BB (next
) != target_bb
)
2189 int not_ex_free
= 0;
2191 /* For speculative insns, before inserting to ready/queue,
2192 check live, exception-free, and issue-delay. */
2193 if (!IS_VALID (INSN_BB (next
))
2195 || (IS_SPECULATIVE_INSN (next
)
2196 && ((recog_memoized (next
) >= 0
2197 && min_insn_conflict_delay (curr_state
, next
, next
)
2198 > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY
))
2199 || IS_SPECULATION_CHECK_P (next
)
2200 || !check_live (next
, INSN_BB (next
))
2201 || (not_ex_free
= !is_exception_free (next
, INSN_BB (next
),
2205 /* We are here because is_exception_free () == false.
2206 But we possibly can handle that with control speculation. */
2207 && sched_deps_info
->generate_spec_deps
2208 && spec_info
->mask
& BEGIN_CONTROL
)
2212 /* Add control speculation to NEXT's dependency type. */
2213 new_ds
= set_dep_weak (ts
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
2215 /* Check if NEXT can be speculated with new dependency type. */
2216 if (sched_insn_is_legitimate_for_speculation_p (next
, new_ds
))
2217 /* Here we got new control-speculative instruction. */
2220 /* NEXT isn't ready yet. */
2221 ts
= (ts
& ~SPECULATIVE
) | HARD_DEP
;
2224 /* NEXT isn't ready yet. */
2225 ts
= (ts
& ~SPECULATIVE
) | HARD_DEP
;
2232 /* Return a string that contains the insn uid and optionally anything else
2233 necessary to identify this insn in an output. It's valid to use a
2234 static buffer for this. The ALIGNED parameter should cause the string
2235 to be formatted so that multiple output lines will line up nicely. */
2238 rgn_print_insn (const_rtx insn
, int aligned
)
2240 static char tmp
[80];
2243 sprintf (tmp
, "b%3d: i%4d", INSN_BB (insn
), INSN_UID (insn
));
2246 if (current_nr_blocks
> 1 && INSN_BB (insn
) != target_bb
)
2247 sprintf (tmp
, "%d/b%d", INSN_UID (insn
), INSN_BB (insn
));
2249 sprintf (tmp
, "%d", INSN_UID (insn
));
2254 /* Compare priority of two insns. Return a positive number if the second
2255 insn is to be preferred for scheduling, and a negative one if the first
2256 is to be preferred. Zero if they are equally good. */
2259 rgn_rank (rtx insn1
, rtx insn2
)
2261 /* Some comparison make sense in interblock scheduling only. */
2262 if (INSN_BB (insn1
) != INSN_BB (insn2
))
2264 int spec_val
, prob_val
;
2266 /* Prefer an inblock motion on an interblock motion. */
2267 if ((INSN_BB (insn2
) == target_bb
) && (INSN_BB (insn1
) != target_bb
))
2269 if ((INSN_BB (insn1
) == target_bb
) && (INSN_BB (insn2
) != target_bb
))
2272 /* Prefer a useful motion on a speculative one. */
2273 spec_val
= IS_SPECULATIVE_INSN (insn1
) - IS_SPECULATIVE_INSN (insn2
);
2277 /* Prefer a more probable (speculative) insn. */
2278 prob_val
= INSN_PROBABILITY (insn2
) - INSN_PROBABILITY (insn1
);
2285 /* NEXT is an instruction that depends on INSN (a backward dependence);
2286 return nonzero if we should include this dependence in priority
2290 contributes_to_priority (rtx next
, rtx insn
)
2292 /* NEXT and INSN reside in one ebb. */
2293 return BLOCK_TO_BB (BLOCK_NUM (next
)) == BLOCK_TO_BB (BLOCK_NUM (insn
));
2296 /* INSN is a JUMP_INSN. Store the set of registers that must be
2297 considered as used by this jump in USED. */
2300 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
2301 regset used ATTRIBUTE_UNUSED
)
2303 /* Nothing to do here, since we postprocess jumps in
2304 add_branch_dependences. */
2307 /* This variable holds common_sched_info hooks and data relevant to
2308 the interblock scheduler. */
2309 static struct common_sched_info_def rgn_common_sched_info
;
2312 /* This holds data for the dependence analysis relevant to
2313 the interblock scheduler. */
2314 static struct sched_deps_info_def rgn_sched_deps_info
;
2316 /* This holds constant data used for initializing the above structure
2317 for the Haifa scheduler. */
2318 static const struct sched_deps_info_def rgn_const_sched_deps_info
=
2320 compute_jump_reg_dependencies
,
2321 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
2325 /* Same as above, but for the selective scheduler. */
2326 static const struct sched_deps_info_def rgn_const_sel_sched_deps_info
=
2328 compute_jump_reg_dependencies
,
2329 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
2333 /* Return true if scheduling INSN will trigger finish of scheduling
2336 rgn_insn_finishes_block_p (rtx insn
)
2338 if (INSN_BB (insn
) == target_bb
2339 && sched_target_n_insns
+ 1 == target_n_insns
)
2340 /* INSN is the last not-scheduled instruction in the current block. */
2346 /* Used in schedule_insns to initialize current_sched_info for scheduling
2347 regions (or single basic blocks). */
2349 static const struct haifa_sched_info rgn_const_sched_info
=
2352 can_schedule_ready_p
,
2357 contributes_to_priority
,
2358 rgn_insn_finishes_block_p
,
2364 rgn_add_remove_insn
,
2365 begin_schedule_ready
,
2372 /* This variable holds the data and hooks needed to the Haifa scheduler backend
2373 for the interblock scheduler frontend. */
2374 static struct haifa_sched_info rgn_sched_info
;
2376 /* Returns maximum priority that an insn was assigned to. */
2379 get_rgn_sched_max_insns_priority (void)
2381 return rgn_sched_info
.sched_max_insns_priority
;
2384 /* Determine if PAT sets a TARGET_CLASS_LIKELY_SPILLED_P register. */
2387 sets_likely_spilled (rtx pat
)
2390 note_stores (pat
, sets_likely_spilled_1
, &ret
);
2395 sets_likely_spilled_1 (rtx x
, const_rtx pat
, void *data
)
2397 bool *ret
= (bool *) data
;
2399 if (GET_CODE (pat
) == SET
2401 && HARD_REGISTER_P (x
)
2402 && targetm
.class_likely_spilled_p (REGNO_REG_CLASS (REGNO (x
))))
2406 /* A bitmap to note insns that participate in any dependency. Used in
2407 add_branch_dependences. */
2408 static sbitmap insn_referenced
;
2410 /* Add dependences so that branches are scheduled to run last in their
2413 add_branch_dependences (rtx head
, rtx tail
)
2417 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2418 that can throw exceptions, force them to remain in order at the end of
2419 the block by adding dependencies and giving the last a high priority.
2420 There may be notes present, and prev_head may also be a note.
2422 Branches must obviously remain at the end. Calls should remain at the
2423 end since moving them results in worse register allocation. Uses remain
2424 at the end to ensure proper register allocation.
2426 cc0 setters remain at the end because they can't be moved away from
2429 COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
2431 Insns setting TARGET_CLASS_LIKELY_SPILLED_P registers (usually return
2432 values) are not moved before reload because we can wind up with register
2433 allocation failures. */
2435 while (tail
!= head
&& DEBUG_INSN_P (tail
))
2436 tail
= PREV_INSN (tail
);
2440 while (CALL_P (insn
)
2442 || (NONJUMP_INSN_P (insn
)
2443 && (GET_CODE (PATTERN (insn
)) == USE
2444 || GET_CODE (PATTERN (insn
)) == CLOBBER
2445 || can_throw_internal (insn
)
2447 || sets_cc0_p (PATTERN (insn
))
2449 || (!reload_completed
2450 && sets_likely_spilled (PATTERN (insn
)))))
2456 && sd_find_dep_between (insn
, last
, false) == NULL
)
2458 if (! sched_insns_conditions_mutex_p (last
, insn
))
2459 add_dependence (last
, insn
, REG_DEP_ANTI
);
2460 SET_BIT (insn_referenced
, INSN_LUID (insn
));
2463 CANT_MOVE (insn
) = 1;
2468 /* Don't overrun the bounds of the basic block. */
2473 insn
= PREV_INSN (insn
);
2474 while (insn
!= head
&& DEBUG_INSN_P (insn
));
2477 /* Make sure these insns are scheduled last in their block. */
2480 while (insn
!= head
)
2482 insn
= prev_nonnote_insn (insn
);
2484 if (TEST_BIT (insn_referenced
, INSN_LUID (insn
))
2485 || DEBUG_INSN_P (insn
))
2488 if (! sched_insns_conditions_mutex_p (last
, insn
))
2489 add_dependence (last
, insn
, REG_DEP_ANTI
);
2492 if (!targetm
.have_conditional_execution ())
2495 /* Finally, if the block ends in a jump, and we are doing intra-block
2496 scheduling, make sure that the branch depends on any COND_EXEC insns
2497 inside the block to avoid moving the COND_EXECs past the branch insn.
2499 We only have to do this after reload, because (1) before reload there
2500 are no COND_EXEC insns, and (2) the region scheduler is an intra-block
2501 scheduler after reload.
2503 FIXME: We could in some cases move COND_EXEC insns past the branch if
2504 this scheduler would be a little smarter. Consider this code:
2512 On a target with a one cycle stall on a memory access the optimal
2521 We don't want to put the 'X += 12' before the branch because it just
2522 wastes a cycle of execution time when the branch is taken.
2524 Note that in the example "!C" will always be true. That is another
2525 possible improvement for handling COND_EXECs in this scheduler: it
2526 could remove always-true predicates. */
2528 if (!reload_completed
|| ! JUMP_P (tail
))
2532 while (insn
!= head
)
2534 insn
= PREV_INSN (insn
);
2536 /* Note that we want to add this dependency even when
2537 sched_insns_conditions_mutex_p returns true. The whole point
2538 is that we _want_ this dependency, even if these insns really
2540 if (INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == COND_EXEC
)
2541 add_dependence (tail
, insn
, REG_DEP_ANTI
);
2545 /* Data structures for the computation of data dependences in a regions. We
2546 keep one `deps' structure for every basic block. Before analyzing the
2547 data dependences for a bb, its variables are initialized as a function of
2548 the variables of its predecessors. When the analysis for a bb completes,
2549 we save the contents to the corresponding bb_deps[bb] variable. */
2551 static struct deps_desc
*bb_deps
;
2554 concat_insn_mem_list (rtx copy_insns
, rtx copy_mems
, rtx
*old_insns_p
,
2557 rtx new_insns
= *old_insns_p
;
2558 rtx new_mems
= *old_mems_p
;
2562 new_insns
= alloc_INSN_LIST (XEXP (copy_insns
, 0), new_insns
);
2563 new_mems
= alloc_EXPR_LIST (VOIDmode
, XEXP (copy_mems
, 0), new_mems
);
2564 copy_insns
= XEXP (copy_insns
, 1);
2565 copy_mems
= XEXP (copy_mems
, 1);
2568 *old_insns_p
= new_insns
;
2569 *old_mems_p
= new_mems
;
2572 /* Join PRED_DEPS to the SUCC_DEPS. */
2574 deps_join (struct deps_desc
*succ_deps
, struct deps_desc
*pred_deps
)
2577 reg_set_iterator rsi
;
2579 /* The reg_last lists are inherited by successor. */
2580 EXECUTE_IF_SET_IN_REG_SET (&pred_deps
->reg_last_in_use
, 0, reg
, rsi
)
2582 struct deps_reg
*pred_rl
= &pred_deps
->reg_last
[reg
];
2583 struct deps_reg
*succ_rl
= &succ_deps
->reg_last
[reg
];
2585 succ_rl
->uses
= concat_INSN_LIST (pred_rl
->uses
, succ_rl
->uses
);
2586 succ_rl
->sets
= concat_INSN_LIST (pred_rl
->sets
, succ_rl
->sets
);
2587 succ_rl
->implicit_sets
2588 = concat_INSN_LIST (pred_rl
->implicit_sets
, succ_rl
->implicit_sets
);
2589 succ_rl
->clobbers
= concat_INSN_LIST (pred_rl
->clobbers
,
2591 succ_rl
->uses_length
+= pred_rl
->uses_length
;
2592 succ_rl
->clobbers_length
+= pred_rl
->clobbers_length
;
2594 IOR_REG_SET (&succ_deps
->reg_last_in_use
, &pred_deps
->reg_last_in_use
);
2596 /* Mem read/write lists are inherited by successor. */
2597 concat_insn_mem_list (pred_deps
->pending_read_insns
,
2598 pred_deps
->pending_read_mems
,
2599 &succ_deps
->pending_read_insns
,
2600 &succ_deps
->pending_read_mems
);
2601 concat_insn_mem_list (pred_deps
->pending_write_insns
,
2602 pred_deps
->pending_write_mems
,
2603 &succ_deps
->pending_write_insns
,
2604 &succ_deps
->pending_write_mems
);
2606 succ_deps
->pending_jump_insns
2607 = concat_INSN_LIST (pred_deps
->pending_jump_insns
,
2608 succ_deps
->pending_jump_insns
);
2609 succ_deps
->last_pending_memory_flush
2610 = concat_INSN_LIST (pred_deps
->last_pending_memory_flush
,
2611 succ_deps
->last_pending_memory_flush
);
2613 succ_deps
->pending_read_list_length
+= pred_deps
->pending_read_list_length
;
2614 succ_deps
->pending_write_list_length
+= pred_deps
->pending_write_list_length
;
2615 succ_deps
->pending_flush_length
+= pred_deps
->pending_flush_length
;
2617 /* last_function_call is inherited by successor. */
2618 succ_deps
->last_function_call
2619 = concat_INSN_LIST (pred_deps
->last_function_call
,
2620 succ_deps
->last_function_call
);
2622 /* last_function_call_may_noreturn is inherited by successor. */
2623 succ_deps
->last_function_call_may_noreturn
2624 = concat_INSN_LIST (pred_deps
->last_function_call_may_noreturn
,
2625 succ_deps
->last_function_call_may_noreturn
);
2627 /* sched_before_next_call is inherited by successor. */
2628 succ_deps
->sched_before_next_call
2629 = concat_INSN_LIST (pred_deps
->sched_before_next_call
,
2630 succ_deps
->sched_before_next_call
);
2633 /* After computing the dependencies for block BB, propagate the dependencies
2634 found in TMP_DEPS to the successors of the block. */
2636 propagate_deps (int bb
, struct deps_desc
*pred_deps
)
2638 basic_block block
= BASIC_BLOCK (BB_TO_BLOCK (bb
));
2642 /* bb's structures are inherited by its successors. */
2643 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2645 /* Only bbs "below" bb, in the same region, are interesting. */
2646 if (e
->dest
== EXIT_BLOCK_PTR
2647 || CONTAINING_RGN (block
->index
) != CONTAINING_RGN (e
->dest
->index
)
2648 || BLOCK_TO_BB (e
->dest
->index
) <= bb
)
2651 deps_join (bb_deps
+ BLOCK_TO_BB (e
->dest
->index
), pred_deps
);
2654 /* These lists should point to the right place, for correct
2656 bb_deps
[bb
].pending_read_insns
= pred_deps
->pending_read_insns
;
2657 bb_deps
[bb
].pending_read_mems
= pred_deps
->pending_read_mems
;
2658 bb_deps
[bb
].pending_write_insns
= pred_deps
->pending_write_insns
;
2659 bb_deps
[bb
].pending_write_mems
= pred_deps
->pending_write_mems
;
2660 bb_deps
[bb
].pending_jump_insns
= pred_deps
->pending_jump_insns
;
2662 /* Can't allow these to be freed twice. */
2663 pred_deps
->pending_read_insns
= 0;
2664 pred_deps
->pending_read_mems
= 0;
2665 pred_deps
->pending_write_insns
= 0;
2666 pred_deps
->pending_write_mems
= 0;
2667 pred_deps
->pending_jump_insns
= 0;
2670 /* Compute dependences inside bb. In a multiple blocks region:
2671 (1) a bb is analyzed after its predecessors, and (2) the lists in
2672 effect at the end of bb (after analyzing for bb) are inherited by
2675 Specifically for reg-reg data dependences, the block insns are
2676 scanned by sched_analyze () top-to-bottom. Three lists are
2677 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2678 reg_last[].implicit_sets for implicit hard register DEFs, and
2679 reg_last[].uses for register USEs.
2681 When analysis is completed for bb, we update for its successors:
2682 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2683 ; - IMPLICIT_DEFS[succ] = Union (IMPLICIT_DEFS [succ], IMPLICIT_DEFS [bb])
2684 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2686 The mechanism for computing mem-mem data dependence is very
2687 similar, and the result is interblock dependences in the region. */
2690 compute_block_dependences (int bb
)
2693 struct deps_desc tmp_deps
;
2695 tmp_deps
= bb_deps
[bb
];
2697 /* Do the analysis for this block. */
2698 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2699 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2701 sched_analyze (&tmp_deps
, head
, tail
);
2703 /* Selective scheduling handles control dependencies by itself. */
2704 if (!sel_sched_p ())
2705 add_branch_dependences (head
, tail
);
2707 if (current_nr_blocks
> 1)
2708 propagate_deps (bb
, &tmp_deps
);
2710 /* Free up the INSN_LISTs. */
2711 free_deps (&tmp_deps
);
2713 if (targetm
.sched
.dependencies_evaluation_hook
)
2714 targetm
.sched
.dependencies_evaluation_hook (head
, tail
);
2717 /* Free dependencies of instructions inside BB. */
2719 free_block_dependencies (int bb
)
2724 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2726 if (no_real_insns_p (head
, tail
))
2729 sched_free_deps (head
, tail
, true);
2732 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2733 them to the unused_*_list variables, so that they can be reused. */
2736 free_pending_lists (void)
2740 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2742 free_INSN_LIST_list (&bb_deps
[bb
].pending_read_insns
);
2743 free_INSN_LIST_list (&bb_deps
[bb
].pending_write_insns
);
2744 free_EXPR_LIST_list (&bb_deps
[bb
].pending_read_mems
);
2745 free_EXPR_LIST_list (&bb_deps
[bb
].pending_write_mems
);
2746 free_INSN_LIST_list (&bb_deps
[bb
].pending_jump_insns
);
2750 /* Print dependences for debugging starting from FROM_BB.
2751 Callable from debugger. */
2752 /* Print dependences for debugging starting from FROM_BB.
2753 Callable from debugger. */
2755 debug_rgn_dependencies (int from_bb
)
2759 fprintf (sched_dump
,
2760 ";; --------------- forward dependences: ------------ \n");
2762 for (bb
= from_bb
; bb
< current_nr_blocks
; bb
++)
2766 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2767 fprintf (sched_dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
2768 BB_TO_BLOCK (bb
), bb
);
2770 debug_dependencies (head
, tail
);
2774 /* Print dependencies information for instructions between HEAD and TAIL.
2775 ??? This function would probably fit best in haifa-sched.c. */
2776 void debug_dependencies (rtx head
, rtx tail
)
2779 rtx next_tail
= NEXT_INSN (tail
);
2781 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2782 "insn", "code", "bb", "dep", "prio", "cost",
2784 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2785 "----", "----", "--", "---", "----", "----",
2788 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2790 if (! INSN_P (insn
))
2793 fprintf (sched_dump
, ";; %6d ", INSN_UID (insn
));
2796 n
= NOTE_KIND (insn
);
2797 fprintf (sched_dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
2800 fprintf (sched_dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
2804 fprintf (sched_dump
,
2805 ";; %s%5d%6d%6d%6d%6d%6d ",
2806 (SCHED_GROUP_P (insn
) ? "+" : " "),
2810 sched_emulate_haifa_p
? -1 : sd_lists_size (insn
, SD_LIST_BACK
),
2811 (sel_sched_p () ? (sched_emulate_haifa_p
? -1
2812 : INSN_PRIORITY (insn
))
2813 : INSN_PRIORITY (insn
)),
2814 (sel_sched_p () ? (sched_emulate_haifa_p
? -1
2816 : insn_cost (insn
)));
2818 if (recog_memoized (insn
) < 0)
2819 fprintf (sched_dump
, "nothing");
2821 print_reservation (sched_dump
, insn
);
2823 fprintf (sched_dump
, "\t: ");
2825 sd_iterator_def sd_it
;
2828 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
2829 fprintf (sched_dump
, "%d ", INSN_UID (DEP_CON (dep
)));
2831 fprintf (sched_dump
, "\n");
2834 fprintf (sched_dump
, "\n");
2837 /* Returns true if all the basic blocks of the current region have
2838 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
2840 sched_is_disabled_for_current_region_p (void)
2844 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2845 if (!(BASIC_BLOCK (BB_TO_BLOCK (bb
))->flags
& BB_DISABLE_SCHEDULE
))
2851 /* Free all region dependencies saved in INSN_BACK_DEPS and
2852 INSN_RESOLVED_BACK_DEPS. The Haifa scheduler does this on the fly
2853 when scheduling, so this function is supposed to be called from
2854 the selective scheduling only. */
2856 free_rgn_deps (void)
2860 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2864 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2865 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2867 sched_free_deps (head
, tail
, false);
2871 static int rgn_n_insns
;
2873 /* Compute insn priority for a current region. */
2875 compute_priorities (void)
2879 current_sched_info
->sched_max_insns_priority
= 0;
2880 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2884 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2885 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2887 if (no_real_insns_p (head
, tail
))
2890 rgn_n_insns
+= set_priorities (head
, tail
);
2892 current_sched_info
->sched_max_insns_priority
++;
2895 /* Schedule a region. A region is either an inner loop, a loop-free
2896 subroutine, or a single basic block. Each bb in the region is
2897 scheduled after its flow predecessors. */
2900 schedule_region (int rgn
)
2903 int sched_rgn_n_insns
= 0;
2907 rgn_setup_region (rgn
);
2909 /* Don't schedule region that is marked by
2910 NOTE_DISABLE_SCHED_OF_BLOCK. */
2911 if (sched_is_disabled_for_current_region_p ())
2914 sched_rgn_compute_dependencies (rgn
);
2916 sched_rgn_local_init (rgn
);
2918 /* Set priorities. */
2919 compute_priorities ();
2921 sched_extend_ready_list (rgn_n_insns
);
2923 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
2925 sched_init_region_reg_pressure_info ();
2926 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2928 basic_block first_bb
, last_bb
;
2931 first_bb
= EBB_FIRST_BB (bb
);
2932 last_bb
= EBB_LAST_BB (bb
);
2934 get_ebb_head_tail (first_bb
, last_bb
, &head
, &tail
);
2936 if (no_real_insns_p (head
, tail
))
2938 gcc_assert (first_bb
== last_bb
);
2941 sched_setup_bb_reg_pressure_info (first_bb
, PREV_INSN (head
));
2945 /* Now we can schedule all blocks. */
2946 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2948 basic_block first_bb
, last_bb
, curr_bb
;
2951 first_bb
= EBB_FIRST_BB (bb
);
2952 last_bb
= EBB_LAST_BB (bb
);
2954 get_ebb_head_tail (first_bb
, last_bb
, &head
, &tail
);
2956 if (no_real_insns_p (head
, tail
))
2958 gcc_assert (first_bb
== last_bb
);
2962 current_sched_info
->prev_head
= PREV_INSN (head
);
2963 current_sched_info
->next_tail
= NEXT_INSN (tail
);
2965 remove_notes (head
, tail
);
2967 unlink_bb_notes (first_bb
, last_bb
);
2971 gcc_assert (flag_schedule_interblock
|| current_nr_blocks
== 1);
2972 current_sched_info
->queue_must_finish_empty
= current_nr_blocks
== 1;
2975 if (dbg_cnt (sched_block
))
2977 schedule_block (&curr_bb
);
2978 gcc_assert (EBB_FIRST_BB (bb
) == first_bb
);
2979 sched_rgn_n_insns
+= sched_n_insns
;
2983 sched_rgn_n_insns
+= rgn_n_insns
;
2987 if (current_nr_blocks
> 1)
2991 /* Sanity check: verify that all region insns were scheduled. */
2992 gcc_assert (sched_rgn_n_insns
== rgn_n_insns
);
2994 sched_finish_ready_list ();
2996 /* Done with this region. */
2997 sched_rgn_local_finish ();
2999 /* Free dependencies. */
3000 for (bb
= 0; bb
< current_nr_blocks
; ++bb
)
3001 free_block_dependencies (bb
);
3003 gcc_assert (haifa_recovery_bb_ever_added_p
3004 || deps_pools_are_empty_p ());
3007 /* Initialize data structures for region scheduling. */
3010 sched_rgn_init (bool single_blocks_p
)
3012 min_spec_prob
= ((PARAM_VALUE (PARAM_MIN_SPEC_PROB
) * REG_BR_PROB_BASE
)
3020 CONTAINING_RGN (ENTRY_BLOCK
) = -1;
3021 CONTAINING_RGN (EXIT_BLOCK
) = -1;
3023 /* Compute regions for scheduling. */
3025 || n_basic_blocks
== NUM_FIXED_BLOCKS
+ 1
3026 || !flag_schedule_interblock
3027 || is_cfg_nonregular ())
3029 find_single_block_region (sel_sched_p ());
3033 /* Compute the dominators and post dominators. */
3034 if (!sel_sched_p ())
3035 calculate_dominance_info (CDI_DOMINATORS
);
3040 if (sched_verbose
>= 3)
3043 /* For now. This will move as more and more of haifa is converted
3044 to using the cfg code. */
3045 if (!sel_sched_p ())
3046 free_dominance_info (CDI_DOMINATORS
);
3049 gcc_assert (0 < nr_regions
&& nr_regions
<= n_basic_blocks
);
3051 RGN_BLOCKS (nr_regions
) = (RGN_BLOCKS (nr_regions
- 1) +
3052 RGN_NR_BLOCKS (nr_regions
- 1));
3055 /* Free data structures for region scheduling. */
3057 sched_rgn_finish (void)
3059 /* Reposition the prologue and epilogue notes in case we moved the
3060 prologue/epilogue insns. */
3061 if (reload_completed
)
3062 reposition_prologue_and_epilogue_notes ();
3066 if (reload_completed
== 0
3067 && flag_schedule_interblock
)
3069 fprintf (sched_dump
,
3070 "\n;; Procedure interblock/speculative motions == %d/%d \n",
3074 gcc_assert (nr_inter
<= 0);
3075 fprintf (sched_dump
, "\n\n");
3083 free (rgn_bb_table
);
3084 rgn_bb_table
= NULL
;
3089 free (containing_rgn
);
3090 containing_rgn
= NULL
;
3096 /* Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
3097 point to the region RGN. */
3099 rgn_setup_region (int rgn
)
3103 /* Set variables for the current region. */
3104 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
3105 current_blocks
= RGN_BLOCKS (rgn
);
3107 /* EBB_HEAD is a region-scope structure. But we realloc it for
3108 each region to save time/memory/something else.
3109 See comments in add_block1, for what reasons we allocate +1 element. */
3110 ebb_head
= XRESIZEVEC (int, ebb_head
, current_nr_blocks
+ 1);
3111 for (bb
= 0; bb
<= current_nr_blocks
; bb
++)
3112 ebb_head
[bb
] = current_blocks
+ bb
;
3115 /* Compute instruction dependencies in region RGN. */
3117 sched_rgn_compute_dependencies (int rgn
)
3119 if (!RGN_DONT_CALC_DEPS (rgn
))
3124 sched_emulate_haifa_p
= 1;
3126 init_deps_global ();
3128 /* Initializations for region data dependence analysis. */
3129 bb_deps
= XNEWVEC (struct deps_desc
, current_nr_blocks
);
3130 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3131 init_deps (bb_deps
+ bb
, false);
3133 /* Initialize bitmap used in add_branch_dependences. */
3134 insn_referenced
= sbitmap_alloc (sched_max_luid
);
3135 sbitmap_zero (insn_referenced
);
3137 /* Compute backward dependencies. */
3138 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3139 compute_block_dependences (bb
);
3141 sbitmap_free (insn_referenced
);
3142 free_pending_lists ();
3143 finish_deps_global ();
3146 /* We don't want to recalculate this twice. */
3147 RGN_DONT_CALC_DEPS (rgn
) = 1;
3150 sched_emulate_haifa_p
= 0;
3153 /* (This is a recovery block. It is always a single block region.)
3154 OR (We use selective scheduling.) */
3155 gcc_assert (current_nr_blocks
== 1 || sel_sched_p ());
3158 /* Init region data structures. Returns true if this region should
3159 not be scheduled. */
3161 sched_rgn_local_init (int rgn
)
3165 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
3166 if (current_nr_blocks
> 1)
3172 prob
= XNEWVEC (int, current_nr_blocks
);
3174 dom
= sbitmap_vector_alloc (current_nr_blocks
, current_nr_blocks
);
3175 sbitmap_vector_zero (dom
, current_nr_blocks
);
3177 /* Use ->aux to implement EDGE_TO_BIT mapping. */
3181 if (CONTAINING_RGN (block
->index
) != rgn
)
3183 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3184 SET_EDGE_TO_BIT (e
, rgn_nr_edges
++);
3187 rgn_edges
= XNEWVEC (edge
, rgn_nr_edges
);
3191 if (CONTAINING_RGN (block
->index
) != rgn
)
3193 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3194 rgn_edges
[rgn_nr_edges
++] = e
;
3198 pot_split
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
3199 sbitmap_vector_zero (pot_split
, current_nr_blocks
);
3200 ancestor_edges
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
3201 sbitmap_vector_zero (ancestor_edges
, current_nr_blocks
);
3203 /* Compute probabilities, dominators, split_edges. */
3204 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3205 compute_dom_prob_ps (bb
);
3207 /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
3208 /* We don't need them anymore. But we want to avoid duplication of
3209 aux fields in the newly created edges. */
3212 if (CONTAINING_RGN (block
->index
) != rgn
)
3214 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3220 /* Free data computed for the finished region. */
3222 sched_rgn_local_free (void)
3225 sbitmap_vector_free (dom
);
3226 sbitmap_vector_free (pot_split
);
3227 sbitmap_vector_free (ancestor_edges
);
3231 /* Free data computed for the finished region. */
3233 sched_rgn_local_finish (void)
3235 if (current_nr_blocks
> 1 && !sel_sched_p ())
3237 sched_rgn_local_free ();
3241 /* Setup scheduler infos. */
3243 rgn_setup_common_sched_info (void)
3245 memcpy (&rgn_common_sched_info
, &haifa_common_sched_info
,
3246 sizeof (rgn_common_sched_info
));
3248 rgn_common_sched_info
.fix_recovery_cfg
= rgn_fix_recovery_cfg
;
3249 rgn_common_sched_info
.add_block
= rgn_add_block
;
3250 rgn_common_sched_info
.estimate_number_of_insns
3251 = rgn_estimate_number_of_insns
;
3252 rgn_common_sched_info
.sched_pass_id
= SCHED_RGN_PASS
;
3254 common_sched_info
= &rgn_common_sched_info
;
3257 /* Setup all *_sched_info structures (for the Haifa frontend
3258 and for the dependence analysis) in the interblock scheduler. */
3260 rgn_setup_sched_infos (void)
3262 if (!sel_sched_p ())
3263 memcpy (&rgn_sched_deps_info
, &rgn_const_sched_deps_info
,
3264 sizeof (rgn_sched_deps_info
));
3266 memcpy (&rgn_sched_deps_info
, &rgn_const_sel_sched_deps_info
,
3267 sizeof (rgn_sched_deps_info
));
3269 sched_deps_info
= &rgn_sched_deps_info
;
3271 memcpy (&rgn_sched_info
, &rgn_const_sched_info
, sizeof (rgn_sched_info
));
3272 current_sched_info
= &rgn_sched_info
;
3275 /* The one entry point in this file. */
3277 schedule_insns (void)
3281 /* Taking care of this degenerate case makes the rest of
3282 this code simpler. */
3283 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
3286 rgn_setup_common_sched_info ();
3287 rgn_setup_sched_infos ();
3289 haifa_sched_init ();
3290 sched_rgn_init (reload_completed
);
3292 bitmap_initialize (¬_in_df
, 0);
3293 bitmap_clear (¬_in_df
);
3295 /* Schedule every region in the subroutine. */
3296 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
3297 if (dbg_cnt (sched_region
))
3298 schedule_region (rgn
);
3301 sched_rgn_finish ();
3302 bitmap_clear (¬_in_df
);
3304 haifa_sched_finish ();
3307 /* INSN has been added to/removed from current region. */
3309 rgn_add_remove_insn (rtx insn
, int remove_p
)
3316 if (INSN_BB (insn
) == target_bb
)
3325 /* Extend internal data structures. */
3327 extend_regions (void)
3329 rgn_table
= XRESIZEVEC (region
, rgn_table
, n_basic_blocks
);
3330 rgn_bb_table
= XRESIZEVEC (int, rgn_bb_table
, n_basic_blocks
);
3331 block_to_bb
= XRESIZEVEC (int, block_to_bb
, last_basic_block
);
3332 containing_rgn
= XRESIZEVEC (int, containing_rgn
, last_basic_block
);
3336 rgn_make_new_region_out_of_new_block (basic_block bb
)
3340 i
= RGN_BLOCKS (nr_regions
);
3341 /* I - first free position in rgn_bb_table. */
3343 rgn_bb_table
[i
] = bb
->index
;
3344 RGN_NR_BLOCKS (nr_regions
) = 1;
3345 RGN_HAS_REAL_EBB (nr_regions
) = 0;
3346 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
3347 CONTAINING_RGN (bb
->index
) = nr_regions
;
3348 BLOCK_TO_BB (bb
->index
) = 0;
3352 RGN_BLOCKS (nr_regions
) = i
+ 1;
3355 /* BB was added to ebb after AFTER. */
3357 rgn_add_block (basic_block bb
, basic_block after
)
3360 bitmap_set_bit (¬_in_df
, bb
->index
);
3362 if (after
== 0 || after
== EXIT_BLOCK_PTR
)
3364 rgn_make_new_region_out_of_new_block (bb
);
3365 RGN_DONT_CALC_DEPS (nr_regions
- 1) = (after
== EXIT_BLOCK_PTR
);
3371 /* We need to fix rgn_table, block_to_bb, containing_rgn
3374 BLOCK_TO_BB (bb
->index
) = BLOCK_TO_BB (after
->index
);
3376 /* We extend ebb_head to one more position to
3377 easily find the last position of the last ebb in
3378 the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
3379 is _always_ valid for access. */
3381 i
= BLOCK_TO_BB (after
->index
) + 1;
3382 pos
= ebb_head
[i
] - 1;
3383 /* Now POS is the index of the last block in the region. */
3385 /* Find index of basic block AFTER. */
3386 for (; rgn_bb_table
[pos
] != after
->index
; pos
--)
3390 gcc_assert (pos
> ebb_head
[i
- 1]);
3392 /* i - ebb right after "AFTER". */
3393 /* ebb_head[i] - VALID. */
3395 /* Source position: ebb_head[i]
3396 Destination position: ebb_head[i] + 1
3398 RGN_BLOCKS (nr_regions) - 1
3399 Number of elements to copy: (last_position) - (source_position) + 1
3402 memmove (rgn_bb_table
+ pos
+ 1,
3404 ((RGN_BLOCKS (nr_regions
) - 1) - (pos
) + 1)
3405 * sizeof (*rgn_bb_table
));
3407 rgn_bb_table
[pos
] = bb
->index
;
3409 for (; i
<= current_nr_blocks
; i
++)
3412 i
= CONTAINING_RGN (after
->index
);
3413 CONTAINING_RGN (bb
->index
) = i
;
3415 RGN_HAS_REAL_EBB (i
) = 1;
3417 for (++i
; i
<= nr_regions
; i
++)
3422 /* Fix internal data after interblock movement of jump instruction.
3423 For parameter meaning please refer to
3424 sched-int.h: struct sched_info: fix_recovery_cfg. */
3426 rgn_fix_recovery_cfg (int bbi
, int check_bbi
, int check_bb_nexti
)
3428 int old_pos
, new_pos
, i
;
3430 BLOCK_TO_BB (check_bb_nexti
) = BLOCK_TO_BB (bbi
);
3432 for (old_pos
= ebb_head
[BLOCK_TO_BB (check_bbi
) + 1] - 1;
3433 rgn_bb_table
[old_pos
] != check_bb_nexti
;
3436 gcc_assert (old_pos
> ebb_head
[BLOCK_TO_BB (check_bbi
)]);
3438 for (new_pos
= ebb_head
[BLOCK_TO_BB (bbi
) + 1] - 1;
3439 rgn_bb_table
[new_pos
] != bbi
;
3443 gcc_assert (new_pos
> ebb_head
[BLOCK_TO_BB (bbi
)]);
3445 gcc_assert (new_pos
< old_pos
);
3447 memmove (rgn_bb_table
+ new_pos
+ 1,
3448 rgn_bb_table
+ new_pos
,
3449 (old_pos
- new_pos
) * sizeof (*rgn_bb_table
));
3451 rgn_bb_table
[new_pos
] = check_bb_nexti
;
3453 for (i
= BLOCK_TO_BB (bbi
) + 1; i
<= BLOCK_TO_BB (check_bbi
); i
++)
3457 /* Return next block in ebb chain. For parameter meaning please refer to
3458 sched-int.h: struct sched_info: advance_target_bb. */
3460 advance_target_bb (basic_block bb
, rtx insn
)
3465 gcc_assert (BLOCK_TO_BB (bb
->index
) == target_bb
3466 && BLOCK_TO_BB (bb
->next_bb
->index
) == target_bb
);
3473 gate_handle_sched (void)
3475 #ifdef INSN_SCHEDULING
3476 return flag_schedule_insns
&& dbg_cnt (sched_func
);
3482 /* Run instruction scheduler. */
3484 rest_of_handle_sched (void)
3486 #ifdef INSN_SCHEDULING
3487 if (flag_selective_scheduling
3488 && ! maybe_skip_selective_scheduling ())
3489 run_selective_scheduling ();
3497 gate_handle_sched2 (void)
3499 #ifdef INSN_SCHEDULING
3500 return optimize
> 0 && flag_schedule_insns_after_reload
3501 && !targetm
.delay_sched2
&& dbg_cnt (sched2_func
);
3507 /* Run second scheduling pass after reload. */
3509 rest_of_handle_sched2 (void)
3511 #ifdef INSN_SCHEDULING
3512 if (flag_selective_scheduling2
3513 && ! maybe_skip_selective_scheduling ())
3514 run_selective_scheduling ();
3517 /* Do control and data sched analysis again,
3518 and write some more of the results to dump file. */
3519 if (flag_sched2_use_superblocks
)
3528 struct rtl_opt_pass pass_sched
=
3532 "sched1", /* name */
3533 gate_handle_sched
, /* gate */
3534 rest_of_handle_sched
, /* execute */
3537 0, /* static_pass_number */
3538 TV_SCHED
, /* tv_id */
3539 0, /* properties_required */
3540 0, /* properties_provided */
3541 0, /* properties_destroyed */
3542 0, /* todo_flags_start */
3543 TODO_df_finish
| TODO_verify_rtl_sharing
|
3545 TODO_ggc_collect
/* todo_flags_finish */
3549 struct rtl_opt_pass pass_sched2
=
3553 "sched2", /* name */
3554 gate_handle_sched2
, /* gate */
3555 rest_of_handle_sched2
, /* execute */
3558 0, /* static_pass_number */
3559 TV_SCHED2
, /* tv_id */
3560 0, /* properties_required */
3561 0, /* properties_provided */
3562 0, /* properties_destroyed */
3563 0, /* todo_flags_start */
3564 TODO_df_finish
| TODO_verify_rtl_sharing
|
3566 TODO_ggc_collect
/* todo_flags_finish */