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
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"
55 #include "hard-reg-set.h"
59 #include "insn-config.h"
60 #include "insn-attr.h"
64 #include "cfglayout.h"
66 #include "sched-int.h"
67 #include "sel-sched.h"
70 #include "tree-pass.h"
73 #ifdef INSN_SCHEDULING
75 /* Some accessor macros for h_i_d members only used within this file. */
76 #define FED_BY_SPEC_LOAD(INSN) (HID (INSN)->fed_by_spec_load)
77 #define IS_LOAD_INSN(INSN) (HID (insn)->is_load_insn)
79 /* nr_inter/spec counts interblock/speculative motion for the function. */
80 static int nr_inter
, nr_spec
;
82 static int is_cfg_nonregular (void);
84 /* Number of regions in the procedure. */
87 /* Table of region descriptions. */
88 region
*rgn_table
= NULL
;
90 /* Array of lists of regions' blocks. */
91 int *rgn_bb_table
= NULL
;
93 /* Topological order of blocks in the region (if b2 is reachable from
94 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
95 always referred to by either block or b, while its topological
96 order name (in the region) is referred to by bb. */
97 int *block_to_bb
= NULL
;
99 /* The number of the region containing a block. */
100 int *containing_rgn
= NULL
;
102 /* ebb_head [i] - is index in rgn_bb_table of the head basic block of i'th ebb.
103 Currently we can get a ebb only through splitting of currently
104 scheduling block, therefore, we don't need ebb_head array for every region,
105 hence, its sufficient to hold it for current one only. */
106 int *ebb_head
= NULL
;
108 /* The minimum probability of reaching a source block so that it will be
109 considered for speculative scheduling. */
110 static int min_spec_prob
;
112 static void find_single_block_region (bool);
113 static void find_rgns (void);
114 static bool too_large (int, int *, int *);
116 /* Blocks of the current region being scheduled. */
117 int current_nr_blocks
;
120 /* A speculative motion requires checking live information on the path
121 from 'source' to 'target'. The split blocks are those to be checked.
122 After a speculative motion, live information should be modified in
125 Lists of split and update blocks for each candidate of the current
126 target are in array bblst_table. */
127 static basic_block
*bblst_table
;
128 static int bblst_size
, bblst_last
;
130 /* Target info declarations.
132 The block currently being scheduled is referred to as the "target" block,
133 while other blocks in the region from which insns can be moved to the
134 target are called "source" blocks. The candidate structure holds info
135 about such sources: are they valid? Speculative? Etc. */
138 basic_block
*first_member
;
153 static candidate
*candidate_table
;
154 #define IS_VALID(src) (candidate_table[src].is_valid)
155 #define IS_SPECULATIVE(src) (candidate_table[src].is_speculative)
156 #define IS_SPECULATIVE_INSN(INSN) \
157 (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
158 #define SRC_PROB(src) ( candidate_table[src].src_prob )
160 /* The bb being currently scheduled. */
171 static edge
*edgelst_table
;
172 static int edgelst_last
;
174 static void extract_edgelst (sbitmap
, edgelst
*);
176 /* Target info functions. */
177 static void split_edges (int, int, edgelst
*);
178 static void compute_trg_info (int);
179 void debug_candidate (int);
180 void debug_candidates (int);
182 /* Dominators array: dom[i] contains the sbitmap of dominators of
183 bb i in the region. */
186 /* bb 0 is the only region entry. */
187 #define IS_RGN_ENTRY(bb) (!bb)
189 /* Is bb_src dominated by bb_trg. */
190 #define IS_DOMINATED(bb_src, bb_trg) \
191 ( TEST_BIT (dom[bb_src], bb_trg) )
193 /* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
194 the probability of bb i relative to the region entry. */
197 /* Bit-set of edges, where bit i stands for edge i. */
198 typedef sbitmap edgeset
;
200 /* Number of edges in the region. */
201 static int rgn_nr_edges
;
203 /* Array of size rgn_nr_edges. */
204 static edge
*rgn_edges
;
206 /* Mapping from each edge in the graph to its number in the rgn. */
207 #define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
208 #define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
210 /* The split edges of a source bb is different for each target
211 bb. In order to compute this efficiently, the 'potential-split edges'
212 are computed for each bb prior to scheduling a region. This is actually
213 the split edges of each bb relative to the region entry.
215 pot_split[bb] is the set of potential split edges of bb. */
216 static edgeset
*pot_split
;
218 /* For every bb, a set of its ancestor edges. */
219 static edgeset
*ancestor_edges
;
221 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
223 /* Speculative scheduling functions. */
224 static int check_live_1 (int, rtx
);
225 static void update_live_1 (int, rtx
);
226 static int is_pfree (rtx
, int, int);
227 static int find_conditional_protection (rtx
, int);
228 static int is_conditionally_protected (rtx
, int, int);
229 static int is_prisky (rtx
, int, int);
230 static int is_exception_free (rtx
, int, int);
232 static bool sets_likely_spilled (rtx
);
233 static void sets_likely_spilled_1 (rtx
, const_rtx
, void *);
234 static void add_branch_dependences (rtx
, rtx
);
235 static void compute_block_dependences (int);
237 static void schedule_region (int);
238 static rtx
concat_INSN_LIST (rtx
, rtx
);
239 static void concat_insn_mem_list (rtx
, rtx
, rtx
*, rtx
*);
240 static void propagate_deps (int, struct deps
*);
241 static void free_pending_lists (void);
243 /* Functions for construction of the control flow graph. */
245 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
247 We decide not to build the control flow graph if there is possibly more
248 than one entry to the function, if computed branches exist, if we
249 have nonlocal gotos, or if we have an unreachable loop. */
252 is_cfg_nonregular (void)
257 /* If we have a label that could be the target of a nonlocal goto, then
258 the cfg is not well structured. */
259 if (nonlocal_goto_handler_labels
)
262 /* If we have any forced labels, then the cfg is not well structured. */
266 /* If we have exception handlers, then we consider the cfg not well
267 structured. ?!? We should be able to handle this now that we
268 compute an accurate cfg for EH. */
269 if (current_function_has_exception_handlers ())
272 /* If we have insns which refer to labels as non-jumped-to operands,
273 then we consider the cfg not well structured. */
275 FOR_BB_INSNS (b
, insn
)
277 rtx note
, next
, set
, dest
;
279 /* If this function has a computed jump, then we consider the cfg
280 not well structured. */
281 if (JUMP_P (insn
) && computed_jump_p (insn
))
287 note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
);
288 if (note
== NULL_RTX
)
291 /* For that label not to be seen as a referred-to label, this
292 must be a single-set which is feeding a jump *only*. This
293 could be a conditional jump with the label split off for
294 machine-specific reasons or a casesi/tablejump. */
295 next
= next_nonnote_insn (insn
);
298 || (JUMP_LABEL (next
) != XEXP (note
, 0)
299 && find_reg_note (next
, REG_LABEL_TARGET
,
300 XEXP (note
, 0)) == NULL_RTX
)
301 || BLOCK_FOR_INSN (insn
) != BLOCK_FOR_INSN (next
))
304 set
= single_set (insn
);
308 dest
= SET_DEST (set
);
309 if (!REG_P (dest
) || !dead_or_set_p (next
, dest
))
313 /* Unreachable loops with more than one basic block are detected
314 during the DFS traversal in find_rgns.
316 Unreachable loops with a single block are detected here. This
317 test is redundant with the one in find_rgns, but it's much
318 cheaper to go ahead and catch the trivial case here. */
321 if (EDGE_COUNT (b
->preds
) == 0
322 || (single_pred_p (b
)
323 && single_pred (b
) == b
))
327 /* All the tests passed. Consider the cfg well structured. */
331 /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */
334 extract_edgelst (sbitmap set
, edgelst
*el
)
337 sbitmap_iterator sbi
;
339 /* edgelst table space is reused in each call to extract_edgelst. */
342 el
->first_member
= &edgelst_table
[edgelst_last
];
345 /* Iterate over each word in the bitset. */
346 EXECUTE_IF_SET_IN_SBITMAP (set
, 0, i
, sbi
)
348 edgelst_table
[edgelst_last
++] = rgn_edges
[i
];
353 /* Functions for the construction of regions. */
355 /* Print the regions, for debugging purposes. Callable from debugger. */
362 fprintf (sched_dump
, "\n;; ------------ REGIONS ----------\n\n");
363 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
365 fprintf (sched_dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
366 rgn_table
[rgn
].rgn_nr_blocks
);
367 fprintf (sched_dump
, ";;\tbb/block: ");
369 /* We don't have ebb_head initialized yet, so we can't use
371 current_blocks
= RGN_BLOCKS (rgn
);
373 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
374 fprintf (sched_dump
, " %d/%d ", bb
, rgn_bb_table
[current_blocks
+ bb
]);
376 fprintf (sched_dump
, "\n\n");
380 /* Print the region's basic blocks. */
383 debug_region (int rgn
)
387 fprintf (stderr
, "\n;; ------------ REGION %d ----------\n\n", rgn
);
388 fprintf (stderr
, ";;\trgn %d nr_blocks %d:\n", rgn
,
389 rgn_table
[rgn
].rgn_nr_blocks
);
390 fprintf (stderr
, ";;\tbb/block: ");
392 /* We don't have ebb_head initialized yet, so we can't use
394 current_blocks
= RGN_BLOCKS (rgn
);
396 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
397 fprintf (stderr
, " %d/%d ", bb
, rgn_bb_table
[current_blocks
+ bb
]);
399 fprintf (stderr
, "\n\n");
401 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
403 debug_bb_n_slim (rgn_bb_table
[current_blocks
+ bb
]);
404 fprintf (stderr
, "\n");
407 fprintf (stderr
, "\n");
411 /* True when a bb with index BB_INDEX contained in region RGN. */
413 bb_in_region_p (int bb_index
, int rgn
)
417 for (i
= 0; i
< rgn_table
[rgn
].rgn_nr_blocks
; i
++)
418 if (rgn_bb_table
[current_blocks
+ i
] == bb_index
)
424 /* Dump region RGN to file F using dot syntax. */
426 dump_region_dot (FILE *f
, int rgn
)
430 fprintf (f
, "digraph Region_%d {\n", rgn
);
432 /* We don't have ebb_head initialized yet, so we can't use
434 current_blocks
= RGN_BLOCKS (rgn
);
436 for (i
= 0; i
< rgn_table
[rgn
].rgn_nr_blocks
; i
++)
440 int src_bb_num
= rgn_bb_table
[current_blocks
+ i
];
441 struct basic_block_def
*bb
= BASIC_BLOCK (src_bb_num
);
443 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
444 if (bb_in_region_p (e
->dest
->index
, rgn
))
445 fprintf (f
, "\t%d -> %d\n", src_bb_num
, e
->dest
->index
);
450 /* The same, but first open a file specified by FNAME. */
452 dump_region_dot_file (const char *fname
, int rgn
)
454 FILE *f
= fopen (fname
, "wt");
455 dump_region_dot (f
, rgn
);
459 /* Build a single block region for each basic block in the function.
460 This allows for using the same code for interblock and basic block
464 find_single_block_region (bool ebbs_p
)
466 basic_block bb
, ebb_start
;
472 int probability_cutoff
;
473 if (profile_info
&& flag_branch_probabilities
)
474 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK
);
476 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY
);
477 probability_cutoff
= REG_BR_PROB_BASE
/ 100 * probability_cutoff
;
479 FOR_EACH_BB (ebb_start
)
481 RGN_NR_BLOCKS (nr_regions
) = 0;
482 RGN_BLOCKS (nr_regions
) = i
;
483 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
484 RGN_HAS_REAL_EBB (nr_regions
) = 0;
486 for (bb
= ebb_start
; ; bb
= bb
->next_bb
)
491 rgn_bb_table
[i
] = bb
->index
;
492 RGN_NR_BLOCKS (nr_regions
)++;
493 CONTAINING_RGN (bb
->index
) = nr_regions
;
494 BLOCK_TO_BB (bb
->index
) = i
- RGN_BLOCKS (nr_regions
);
497 if (bb
->next_bb
== EXIT_BLOCK_PTR
498 || LABEL_P (BB_HEAD (bb
->next_bb
)))
501 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
502 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
506 if (e
->probability
<= probability_cutoff
)
517 rgn_bb_table
[nr_regions
] = bb
->index
;
518 RGN_NR_BLOCKS (nr_regions
) = 1;
519 RGN_BLOCKS (nr_regions
) = nr_regions
;
520 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
521 RGN_HAS_REAL_EBB (nr_regions
) = 0;
523 CONTAINING_RGN (bb
->index
) = nr_regions
;
524 BLOCK_TO_BB (bb
->index
) = 0;
529 /* Estimate number of the insns in the BB. */
531 rgn_estimate_number_of_insns (basic_block bb
)
533 return INSN_LUID (BB_END (bb
)) - INSN_LUID (BB_HEAD (bb
));
536 /* Update number of blocks and the estimate for number of insns
537 in the region. Return true if the region is "too large" for interblock
538 scheduling (compile time considerations). */
541 too_large (int block
, int *num_bbs
, int *num_insns
)
544 (*num_insns
) += (common_sched_info
->estimate_number_of_insns
545 (BASIC_BLOCK (block
)));
547 return ((*num_bbs
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS
))
548 || (*num_insns
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS
)));
551 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
552 is still an inner loop. Put in max_hdr[blk] the header of the most inner
553 loop containing blk. */
554 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
556 if (max_hdr[blk] == -1) \
557 max_hdr[blk] = hdr; \
558 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
559 RESET_BIT (inner, hdr); \
560 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
562 RESET_BIT (inner,max_hdr[blk]); \
563 max_hdr[blk] = hdr; \
567 /* Find regions for interblock scheduling.
569 A region for scheduling can be:
571 * A loop-free procedure, or
573 * A reducible inner loop, or
575 * A basic block not contained in any other region.
577 ?!? In theory we could build other regions based on extended basic
578 blocks or reverse extended basic blocks. Is it worth the trouble?
580 Loop blocks that form a region are put into the region's block list
581 in topological order.
583 This procedure stores its results into the following global (ick) variables
591 We use dominator relationships to avoid making regions out of non-reducible
594 This procedure needs to be converted to work on pred/succ lists instead
595 of edge tables. That would simplify it somewhat. */
598 haifa_find_rgns (void)
600 int *max_hdr
, *dfs_nr
, *degree
;
602 int node
, child
, loop_head
, i
, head
, tail
;
603 int count
= 0, sp
, idx
= 0;
604 edge_iterator current_edge
;
605 edge_iterator
*stack
;
606 int num_bbs
, num_insns
, unreachable
;
607 int too_large_failure
;
610 /* Note if a block is a natural loop header. */
613 /* Note if a block is a natural inner loop header. */
616 /* Note if a block is in the block queue. */
619 /* Note if a block is in the block queue. */
622 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
623 and a mapping from block to its loop header (if the block is contained
626 Store results in HEADER, INNER, and MAX_HDR respectively, these will
627 be used as inputs to the second traversal.
629 STACK, SP and DFS_NR are only used during the first traversal. */
631 /* Allocate and initialize variables for the first traversal. */
632 max_hdr
= XNEWVEC (int, last_basic_block
);
633 dfs_nr
= XCNEWVEC (int, last_basic_block
);
634 stack
= XNEWVEC (edge_iterator
, n_edges
);
636 inner
= sbitmap_alloc (last_basic_block
);
637 sbitmap_ones (inner
);
639 header
= sbitmap_alloc (last_basic_block
);
640 sbitmap_zero (header
);
642 in_queue
= sbitmap_alloc (last_basic_block
);
643 sbitmap_zero (in_queue
);
645 in_stack
= sbitmap_alloc (last_basic_block
);
646 sbitmap_zero (in_stack
);
648 for (i
= 0; i
< last_basic_block
; i
++)
651 #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
652 #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
654 /* DFS traversal to find inner loops in the cfg. */
656 current_edge
= ei_start (single_succ (ENTRY_BLOCK_PTR
)->succs
);
661 if (EDGE_PASSED (current_edge
))
663 /* We have reached a leaf node or a node that was already
664 processed. Pop edges off the stack until we find
665 an edge that has not yet been processed. */
666 while (sp
>= 0 && EDGE_PASSED (current_edge
))
668 /* Pop entry off the stack. */
669 current_edge
= stack
[sp
--];
670 node
= ei_edge (current_edge
)->src
->index
;
671 gcc_assert (node
!= ENTRY_BLOCK
);
672 child
= ei_edge (current_edge
)->dest
->index
;
673 gcc_assert (child
!= EXIT_BLOCK
);
674 RESET_BIT (in_stack
, child
);
675 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
676 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
677 ei_next (¤t_edge
);
680 /* See if have finished the DFS tree traversal. */
681 if (sp
< 0 && EDGE_PASSED (current_edge
))
684 /* Nope, continue the traversal with the popped node. */
688 /* Process a node. */
689 node
= ei_edge (current_edge
)->src
->index
;
690 gcc_assert (node
!= ENTRY_BLOCK
);
691 SET_BIT (in_stack
, node
);
692 dfs_nr
[node
] = ++count
;
694 /* We don't traverse to the exit block. */
695 child
= ei_edge (current_edge
)->dest
->index
;
696 if (child
== EXIT_BLOCK
)
698 SET_EDGE_PASSED (current_edge
);
699 ei_next (¤t_edge
);
703 /* If the successor is in the stack, then we've found a loop.
704 Mark the loop, if it is not a natural loop, then it will
705 be rejected during the second traversal. */
706 if (TEST_BIT (in_stack
, child
))
709 SET_BIT (header
, child
);
710 UPDATE_LOOP_RELATIONS (node
, child
);
711 SET_EDGE_PASSED (current_edge
);
712 ei_next (¤t_edge
);
716 /* If the child was already visited, then there is no need to visit
717 it again. Just update the loop relationships and restart
721 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
722 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
723 SET_EDGE_PASSED (current_edge
);
724 ei_next (¤t_edge
);
728 /* Push an entry on the stack and continue DFS traversal. */
729 stack
[++sp
] = current_edge
;
730 SET_EDGE_PASSED (current_edge
);
731 current_edge
= ei_start (ei_edge (current_edge
)->dest
->succs
);
734 /* Reset ->aux field used by EDGE_PASSED. */
739 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
744 /* Another check for unreachable blocks. The earlier test in
745 is_cfg_nonregular only finds unreachable blocks that do not
748 The DFS traversal will mark every block that is reachable from
749 the entry node by placing a nonzero value in dfs_nr. Thus if
750 dfs_nr is zero for any block, then it must be unreachable. */
753 if (dfs_nr
[bb
->index
] == 0)
759 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
760 to hold degree counts. */
764 degree
[bb
->index
] = EDGE_COUNT (bb
->preds
);
766 /* Do not perform region scheduling if there are any unreachable
770 int *queue
, *degree1
= NULL
;
771 /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
772 there basic blocks, which are forced to be region heads.
773 This is done to try to assemble few smaller regions
774 from a too_large region. */
775 sbitmap extended_rgn_header
= NULL
;
776 bool extend_regions_p
;
781 /* Second traversal:find reducible inner loops and topologically sort
782 block of each region. */
784 queue
= XNEWVEC (int, n_basic_blocks
);
786 extend_regions_p
= PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS
) > 0;
787 if (extend_regions_p
)
789 degree1
= XNEWVEC (int, last_basic_block
);
790 extended_rgn_header
= sbitmap_alloc (last_basic_block
);
791 sbitmap_zero (extended_rgn_header
);
794 /* Find blocks which are inner loop headers. We still have non-reducible
795 loops to consider at this point. */
798 if (TEST_BIT (header
, bb
->index
) && TEST_BIT (inner
, bb
->index
))
804 /* Now check that the loop is reducible. We do this separate
805 from finding inner loops so that we do not find a reducible
806 loop which contains an inner non-reducible loop.
808 A simple way to find reducible/natural loops is to verify
809 that each block in the loop is dominated by the loop
812 If there exists a block that is not dominated by the loop
813 header, then the block is reachable from outside the loop
814 and thus the loop is not a natural loop. */
817 /* First identify blocks in the loop, except for the loop
819 if (bb
->index
== max_hdr
[jbb
->index
] && bb
!= jbb
)
821 /* Now verify that the block is dominated by the loop
823 if (!dominated_by_p (CDI_DOMINATORS
, jbb
, bb
))
828 /* If we exited the loop early, then I is the header of
829 a non-reducible loop and we should quit processing it
831 if (jbb
!= EXIT_BLOCK_PTR
)
834 /* I is a header of an inner loop, or block 0 in a subroutine
835 with no loops at all. */
837 too_large_failure
= 0;
838 loop_head
= max_hdr
[bb
->index
];
840 if (extend_regions_p
)
841 /* We save degree in case when we meet a too_large region
842 and cancel it. We need a correct degree later when
843 calling extend_rgns. */
844 memcpy (degree1
, degree
, last_basic_block
* sizeof (int));
846 /* Decrease degree of all I's successors for topological
848 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
849 if (e
->dest
!= EXIT_BLOCK_PTR
)
850 --degree
[e
->dest
->index
];
852 /* Estimate # insns, and count # blocks in the region. */
854 num_insns
= common_sched_info
->estimate_number_of_insns (bb
);
856 /* Find all loop latches (blocks with back edges to the loop
857 header) or all the leaf blocks in the cfg has no loops.
859 Place those blocks into the queue. */
863 /* Leaf nodes have only a single successor which must
865 if (single_succ_p (jbb
)
866 && single_succ (jbb
) == EXIT_BLOCK_PTR
)
868 queue
[++tail
] = jbb
->index
;
869 SET_BIT (in_queue
, jbb
->index
);
871 if (too_large (jbb
->index
, &num_bbs
, &num_insns
))
873 too_large_failure
= 1;
882 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
884 if (e
->src
== ENTRY_BLOCK_PTR
)
887 node
= e
->src
->index
;
889 if (max_hdr
[node
] == loop_head
&& node
!= bb
->index
)
891 /* This is a loop latch. */
892 queue
[++tail
] = node
;
893 SET_BIT (in_queue
, node
);
895 if (too_large (node
, &num_bbs
, &num_insns
))
897 too_large_failure
= 1;
904 /* Now add all the blocks in the loop to the queue.
906 We know the loop is a natural loop; however the algorithm
907 above will not always mark certain blocks as being in the
915 The algorithm in the DFS traversal may not mark B & D as part
916 of the loop (i.e. they will not have max_hdr set to A).
918 We know they can not be loop latches (else they would have
919 had max_hdr set since they'd have a backedge to a dominator
920 block). So we don't need them on the initial queue.
922 We know they are part of the loop because they are dominated
923 by the loop header and can be reached by a backwards walk of
924 the edges starting with nodes on the initial queue.
926 It is safe and desirable to include those nodes in the
927 loop/scheduling region. To do so we would need to decrease
928 the degree of a node if it is the target of a backedge
929 within the loop itself as the node is placed in the queue.
931 We do not do this because I'm not sure that the actual
932 scheduling code will properly handle this case. ?!? */
934 while (head
< tail
&& !too_large_failure
)
937 child
= queue
[++head
];
939 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (child
)->preds
)
941 node
= e
->src
->index
;
943 /* See discussion above about nodes not marked as in
944 this loop during the initial DFS traversal. */
945 if (e
->src
== ENTRY_BLOCK_PTR
946 || max_hdr
[node
] != loop_head
)
951 else if (!TEST_BIT (in_queue
, node
) && node
!= bb
->index
)
953 queue
[++tail
] = node
;
954 SET_BIT (in_queue
, node
);
956 if (too_large (node
, &num_bbs
, &num_insns
))
958 too_large_failure
= 1;
965 if (tail
>= 0 && !too_large_failure
)
967 /* Place the loop header into list of region blocks. */
968 degree
[bb
->index
] = -1;
969 rgn_bb_table
[idx
] = bb
->index
;
970 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
971 RGN_BLOCKS (nr_regions
) = idx
++;
972 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
973 RGN_HAS_REAL_EBB (nr_regions
) = 0;
974 CONTAINING_RGN (bb
->index
) = nr_regions
;
975 BLOCK_TO_BB (bb
->index
) = count
= 0;
977 /* Remove blocks from queue[] when their in degree
978 becomes zero. Repeat until no blocks are left on the
979 list. This produces a topological list of blocks in
986 if (degree
[child
] == 0)
991 rgn_bb_table
[idx
++] = child
;
992 BLOCK_TO_BB (child
) = ++count
;
993 CONTAINING_RGN (child
) = nr_regions
;
994 queue
[head
] = queue
[tail
--];
996 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (child
)->succs
)
997 if (e
->dest
!= EXIT_BLOCK_PTR
)
998 --degree
[e
->dest
->index
];
1005 else if (extend_regions_p
)
1007 /* Restore DEGREE. */
1013 /* And force successors of BB to be region heads.
1014 This may provide several smaller regions instead
1015 of one too_large region. */
1016 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1017 if (e
->dest
!= EXIT_BLOCK_PTR
)
1018 SET_BIT (extended_rgn_header
, e
->dest
->index
);
1024 if (extend_regions_p
)
1028 sbitmap_a_or_b (header
, header
, extended_rgn_header
);
1029 sbitmap_free (extended_rgn_header
);
1031 extend_rgns (degree
, &idx
, header
, max_hdr
);
1035 /* Any block that did not end up in a region is placed into a region
1038 if (degree
[bb
->index
] >= 0)
1040 rgn_bb_table
[idx
] = bb
->index
;
1041 RGN_NR_BLOCKS (nr_regions
) = 1;
1042 RGN_BLOCKS (nr_regions
) = idx
++;
1043 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1044 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1045 CONTAINING_RGN (bb
->index
) = nr_regions
++;
1046 BLOCK_TO_BB (bb
->index
) = 0;
1052 sbitmap_free (header
);
1053 sbitmap_free (inner
);
1054 sbitmap_free (in_queue
);
1055 sbitmap_free (in_stack
);
1059 /* Wrapper function.
1060 If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
1061 regions. Otherwise just call find_rgns_haifa. */
1065 if (sel_sched_p () && flag_sel_sched_pipelining
)
1071 static int gather_region_statistics (int **);
1072 static void print_region_statistics (int *, int, int *, int);
1074 /* Calculate the histogram that shows the number of regions having the
1075 given number of basic blocks, and store it in the RSP array. Return
1076 the size of this array. */
1078 gather_region_statistics (int **rsp
)
1080 int i
, *a
= 0, a_sz
= 0;
1082 /* a[i] is the number of regions that have (i + 1) basic blocks. */
1083 for (i
= 0; i
< nr_regions
; i
++)
1085 int nr_blocks
= RGN_NR_BLOCKS (i
);
1087 gcc_assert (nr_blocks
>= 1);
1089 if (nr_blocks
> a_sz
)
1091 a
= XRESIZEVEC (int, a
, nr_blocks
);
1094 while (a_sz
!= nr_blocks
);
1104 /* Print regions statistics. S1 and S2 denote the data before and after
1105 calling extend_rgns, respectively. */
1107 print_region_statistics (int *s1
, int s1_sz
, int *s2
, int s2_sz
)
1111 /* We iterate until s2_sz because extend_rgns does not decrease
1112 the maximal region size. */
1113 for (i
= 1; i
< s2_sz
; i
++)
1127 fprintf (sched_dump
, ";; Region extension statistics: size %d: " \
1128 "was %d + %d more\n", i
+ 1, n1
, n2
- n1
);
1133 DEGREE - Array of incoming edge count, considering only
1134 the edges, that don't have their sources in formed regions yet.
1135 IDXP - pointer to the next available index in rgn_bb_table.
1136 HEADER - set of all region heads.
1137 LOOP_HDR - mapping from block to the containing loop
1138 (two blocks can reside within one region if they have
1139 the same loop header). */
1141 extend_rgns (int *degree
, int *idxp
, sbitmap header
, int *loop_hdr
)
1143 int *order
, i
, rescan
= 0, idx
= *idxp
, iter
= 0, max_iter
, *max_hdr
;
1144 int nblocks
= n_basic_blocks
- NUM_FIXED_BLOCKS
;
1146 max_iter
= PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS
);
1148 max_hdr
= XNEWVEC (int, last_basic_block
);
1150 order
= XNEWVEC (int, last_basic_block
);
1151 post_order_compute (order
, false, false);
1153 for (i
= nblocks
- 1; i
>= 0; i
--)
1156 if (degree
[bbn
] >= 0)
1162 /* This block already was processed in find_rgns. */
1166 /* The idea is to topologically walk through CFG in top-down order.
1167 During the traversal, if all the predecessors of a node are
1168 marked to be in the same region (they all have the same max_hdr),
1169 then current node is also marked to be a part of that region.
1170 Otherwise the node starts its own region.
1171 CFG should be traversed until no further changes are made. On each
1172 iteration the set of the region heads is extended (the set of those
1173 blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
1174 set of all basic blocks, thus the algorithm is guaranteed to
1177 while (rescan
&& iter
< max_iter
)
1181 for (i
= nblocks
- 1; i
>= 0; i
--)
1187 if (max_hdr
[bbn
] != -1 && !TEST_BIT (header
, bbn
))
1191 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (bbn
)->preds
)
1193 int predn
= e
->src
->index
;
1195 if (predn
!= ENTRY_BLOCK
1196 /* If pred wasn't processed in find_rgns. */
1197 && max_hdr
[predn
] != -1
1198 /* And pred and bb reside in the same loop.
1199 (Or out of any loop). */
1200 && loop_hdr
[bbn
] == loop_hdr
[predn
])
1203 /* Then bb extends the containing region of pred. */
1204 hdr
= max_hdr
[predn
];
1205 else if (hdr
!= max_hdr
[predn
])
1206 /* Too bad, there are at least two predecessors
1207 that reside in different regions. Thus, BB should
1208 begin its own region. */
1215 /* BB starts its own region. */
1224 /* If BB start its own region,
1225 update set of headers with BB. */
1226 SET_BIT (header
, bbn
);
1230 gcc_assert (hdr
!= -1);
1239 /* Statistics were gathered on the SPEC2000 package of tests with
1240 mainline weekly snapshot gcc-4.1-20051015 on ia64.
1242 Statistics for SPECint:
1243 1 iteration : 1751 cases (38.7%)
1244 2 iterations: 2770 cases (61.3%)
1245 Blocks wrapped in regions by find_rgns without extension: 18295 blocks
1246 Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
1247 (We don't count single block regions here).
1249 Statistics for SPECfp:
1250 1 iteration : 621 cases (35.9%)
1251 2 iterations: 1110 cases (64.1%)
1252 Blocks wrapped in regions by find_rgns without extension: 6476 blocks
1253 Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
1254 (We don't count single block regions here).
1256 By default we do at most 2 iterations.
1257 This can be overridden with max-sched-extend-regions-iters parameter:
1258 0 - disable region extension,
1259 N > 0 - do at most N iterations. */
1261 if (sched_verbose
&& iter
!= 0)
1262 fprintf (sched_dump
, ";; Region extension iterations: %d%s\n", iter
,
1263 rescan
? "... failed" : "");
1265 if (!rescan
&& iter
!= 0)
1267 int *s1
= NULL
, s1_sz
= 0;
1269 /* Save the old statistics for later printout. */
1270 if (sched_verbose
>= 6)
1271 s1_sz
= gather_region_statistics (&s1
);
1273 /* We have succeeded. Now assemble the regions. */
1274 for (i
= nblocks
- 1; i
>= 0; i
--)
1278 if (max_hdr
[bbn
] == bbn
)
1279 /* BBN is a region head. */
1283 int num_bbs
= 0, j
, num_insns
= 0, large
;
1285 large
= too_large (bbn
, &num_bbs
, &num_insns
);
1288 rgn_bb_table
[idx
] = bbn
;
1289 RGN_BLOCKS (nr_regions
) = idx
++;
1290 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1291 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1292 CONTAINING_RGN (bbn
) = nr_regions
;
1293 BLOCK_TO_BB (bbn
) = 0;
1295 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (bbn
)->succs
)
1296 if (e
->dest
!= EXIT_BLOCK_PTR
)
1297 degree
[e
->dest
->index
]--;
1300 /* Here we check whether the region is too_large. */
1301 for (j
= i
- 1; j
>= 0; j
--)
1303 int succn
= order
[j
];
1304 if (max_hdr
[succn
] == bbn
)
1306 if ((large
= too_large (succn
, &num_bbs
, &num_insns
)))
1312 /* If the region is too_large, then wrap every block of
1313 the region into single block region.
1314 Here we wrap region head only. Other blocks are
1315 processed in the below cycle. */
1317 RGN_NR_BLOCKS (nr_regions
) = 1;
1323 for (j
= i
- 1; j
>= 0; j
--)
1325 int succn
= order
[j
];
1327 if (max_hdr
[succn
] == bbn
)
1328 /* This cycle iterates over all basic blocks, that
1329 are supposed to be in the region with head BBN,
1330 and wraps them into that region (or in single
1333 gcc_assert (degree
[succn
] == 0);
1336 rgn_bb_table
[idx
] = succn
;
1337 BLOCK_TO_BB (succn
) = large
? 0 : num_bbs
++;
1338 CONTAINING_RGN (succn
) = nr_regions
;
1341 /* Wrap SUCCN into single block region. */
1343 RGN_BLOCKS (nr_regions
) = idx
;
1344 RGN_NR_BLOCKS (nr_regions
) = 1;
1345 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1346 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1352 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (succn
)->succs
)
1353 if (e
->dest
!= EXIT_BLOCK_PTR
)
1354 degree
[e
->dest
->index
]--;
1360 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1366 if (sched_verbose
>= 6)
1370 /* Get the new statistics and print the comparison with the
1371 one before calling this function. */
1372 s2_sz
= gather_region_statistics (&s2
);
1373 print_region_statistics (s1
, s1_sz
, s2
, s2_sz
);
1385 /* Functions for regions scheduling information. */
1387 /* Compute dominators, probability, and potential-split-edges of bb.
1388 Assume that these values were already computed for bb's predecessors. */
1391 compute_dom_prob_ps (int bb
)
1393 edge_iterator in_ei
;
1396 /* We shouldn't have any real ebbs yet. */
1397 gcc_assert (ebb_head
[bb
] == bb
+ current_blocks
);
1399 if (IS_RGN_ENTRY (bb
))
1401 SET_BIT (dom
[bb
], 0);
1402 prob
[bb
] = REG_BR_PROB_BASE
;
1408 /* Initialize dom[bb] to '111..1'. */
1409 sbitmap_ones (dom
[bb
]);
1411 FOR_EACH_EDGE (in_edge
, in_ei
, BASIC_BLOCK (BB_TO_BLOCK (bb
))->preds
)
1415 edge_iterator out_ei
;
1417 if (in_edge
->src
== ENTRY_BLOCK_PTR
)
1420 pred_bb
= BLOCK_TO_BB (in_edge
->src
->index
);
1421 sbitmap_a_and_b (dom
[bb
], dom
[bb
], dom
[pred_bb
]);
1422 sbitmap_a_or_b (ancestor_edges
[bb
],
1423 ancestor_edges
[bb
], ancestor_edges
[pred_bb
]);
1425 SET_BIT (ancestor_edges
[bb
], EDGE_TO_BIT (in_edge
));
1427 sbitmap_a_or_b (pot_split
[bb
], pot_split
[bb
], pot_split
[pred_bb
]);
1429 FOR_EACH_EDGE (out_edge
, out_ei
, in_edge
->src
->succs
)
1430 SET_BIT (pot_split
[bb
], EDGE_TO_BIT (out_edge
));
1432 prob
[bb
] += ((prob
[pred_bb
] * in_edge
->probability
) / REG_BR_PROB_BASE
);
1435 SET_BIT (dom
[bb
], bb
);
1436 sbitmap_difference (pot_split
[bb
], pot_split
[bb
], ancestor_edges
[bb
]);
1438 if (sched_verbose
>= 2)
1439 fprintf (sched_dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
),
1440 (100 * prob
[bb
]) / REG_BR_PROB_BASE
);
1443 /* Functions for target info. */
1445 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1446 Note that bb_trg dominates bb_src. */
1449 split_edges (int bb_src
, int bb_trg
, edgelst
*bl
)
1451 sbitmap src
= sbitmap_alloc (pot_split
[bb_src
]->n_bits
);
1452 sbitmap_copy (src
, pot_split
[bb_src
]);
1454 sbitmap_difference (src
, src
, pot_split
[bb_trg
]);
1455 extract_edgelst (src
, bl
);
1459 /* Find the valid candidate-source-blocks for the target block TRG, compute
1460 their probability, and check if they are speculative or not.
1461 For speculative sources, compute their update-blocks and split-blocks. */
1464 compute_trg_info (int trg
)
1467 edgelst el
= { NULL
, 0 };
1468 int i
, j
, k
, update_idx
;
1474 candidate_table
= XNEWVEC (candidate
, current_nr_blocks
);
1477 /* bblst_table holds split blocks and update blocks for each block after
1478 the current one in the region. split blocks and update blocks are
1479 the TO blocks of region edges, so there can be at most rgn_nr_edges
1481 bblst_size
= (current_nr_blocks
- target_bb
) * rgn_nr_edges
;
1482 bblst_table
= XNEWVEC (basic_block
, bblst_size
);
1485 edgelst_table
= XNEWVEC (edge
, rgn_nr_edges
);
1487 /* Define some of the fields for the target bb as well. */
1488 sp
= candidate_table
+ trg
;
1490 sp
->is_speculative
= 0;
1491 sp
->src_prob
= REG_BR_PROB_BASE
;
1493 visited
= sbitmap_alloc (last_basic_block
);
1495 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1497 sp
= candidate_table
+ i
;
1499 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1502 int tf
= prob
[trg
], cf
= prob
[i
];
1504 /* In CFGs with low probability edges TF can possibly be zero. */
1505 sp
->src_prob
= (tf
? ((cf
* REG_BR_PROB_BASE
) / tf
) : 0);
1506 sp
->is_valid
= (sp
->src_prob
>= min_spec_prob
);
1511 split_edges (i
, trg
, &el
);
1512 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1513 if (sp
->is_speculative
&& !flag_schedule_speculative
)
1519 /* Compute split blocks and store them in bblst_table.
1520 The TO block of every split edge is a split block. */
1521 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
1522 sp
->split_bbs
.nr_members
= el
.nr_members
;
1523 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
1524 bblst_table
[bblst_last
] = el
.first_member
[j
]->dest
;
1525 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
1527 /* Compute update blocks and store them in bblst_table.
1528 For every split edge, look at the FROM block, and check
1529 all out edges. For each out edge that is not a split edge,
1530 add the TO block to the update block list. This list can end
1531 up with a lot of duplicates. We need to weed them out to avoid
1532 overrunning the end of the bblst_table. */
1535 sbitmap_zero (visited
);
1536 for (j
= 0; j
< el
.nr_members
; j
++)
1538 block
= el
.first_member
[j
]->src
;
1539 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1541 if (!TEST_BIT (visited
, e
->dest
->index
))
1543 for (k
= 0; k
< el
.nr_members
; k
++)
1544 if (e
== el
.first_member
[k
])
1547 if (k
>= el
.nr_members
)
1549 bblst_table
[bblst_last
++] = e
->dest
;
1550 SET_BIT (visited
, e
->dest
->index
);
1556 sp
->update_bbs
.nr_members
= update_idx
;
1558 /* Make sure we didn't overrun the end of bblst_table. */
1559 gcc_assert (bblst_last
<= bblst_size
);
1563 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
1565 sp
->is_speculative
= 0;
1570 sbitmap_free (visited
);
1573 /* Free the computed target info. */
1575 free_trg_info (void)
1577 free (candidate_table
);
1579 free (edgelst_table
);
1582 /* Print candidates info, for debugging purposes. Callable from debugger. */
1585 debug_candidate (int i
)
1587 if (!candidate_table
[i
].is_valid
)
1590 if (candidate_table
[i
].is_speculative
)
1593 fprintf (sched_dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
1595 fprintf (sched_dump
, "split path: ");
1596 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
1598 int b
= candidate_table
[i
].split_bbs
.first_member
[j
]->index
;
1600 fprintf (sched_dump
, " %d ", b
);
1602 fprintf (sched_dump
, "\n");
1604 fprintf (sched_dump
, "update path: ");
1605 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
1607 int b
= candidate_table
[i
].update_bbs
.first_member
[j
]->index
;
1609 fprintf (sched_dump
, " %d ", b
);
1611 fprintf (sched_dump
, "\n");
1615 fprintf (sched_dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
1619 /* Print candidates info, for debugging purposes. Callable from debugger. */
1622 debug_candidates (int trg
)
1626 fprintf (sched_dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
1627 BB_TO_BLOCK (trg
), trg
);
1628 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1629 debug_candidate (i
);
1632 /* Functions for speculative scheduling. */
1634 static bitmap_head not_in_df
;
1636 /* Return 0 if x is a set of a register alive in the beginning of one
1637 of the split-blocks of src, otherwise return 1. */
1640 check_live_1 (int src
, rtx x
)
1644 rtx reg
= SET_DEST (x
);
1649 while (GET_CODE (reg
) == SUBREG
1650 || GET_CODE (reg
) == ZERO_EXTRACT
1651 || GET_CODE (reg
) == STRICT_LOW_PART
)
1652 reg
= XEXP (reg
, 0);
1654 if (GET_CODE (reg
) == PARALLEL
)
1658 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1659 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1660 if (check_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0)))
1669 regno
= REGNO (reg
);
1671 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
1673 /* Global registers are assumed live. */
1678 if (regno
< FIRST_PSEUDO_REGISTER
)
1680 /* Check for hard registers. */
1681 int j
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1684 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1686 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1687 int t
= bitmap_bit_p (¬_in_df
, b
->index
);
1689 /* We can have split blocks, that were recently generated.
1690 Such blocks are always outside current region. */
1691 gcc_assert (!t
|| (CONTAINING_RGN (b
->index
)
1692 != CONTAINING_RGN (BB_TO_BLOCK (src
))));
1694 if (t
|| REGNO_REG_SET_P (df_get_live_in (b
), regno
+ j
))
1701 /* Check for pseudo registers. */
1702 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1704 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1705 int t
= bitmap_bit_p (¬_in_df
, b
->index
);
1707 gcc_assert (!t
|| (CONTAINING_RGN (b
->index
)
1708 != CONTAINING_RGN (BB_TO_BLOCK (src
))));
1710 if (t
|| REGNO_REG_SET_P (df_get_live_in (b
), regno
))
1719 /* If x is a set of a register R, mark that R is alive in the beginning
1720 of every update-block of src. */
1723 update_live_1 (int src
, rtx x
)
1727 rtx reg
= SET_DEST (x
);
1732 while (GET_CODE (reg
) == SUBREG
1733 || GET_CODE (reg
) == ZERO_EXTRACT
1734 || GET_CODE (reg
) == STRICT_LOW_PART
)
1735 reg
= XEXP (reg
, 0);
1737 if (GET_CODE (reg
) == PARALLEL
)
1741 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1742 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1743 update_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0));
1751 /* Global registers are always live, so the code below does not apply
1754 regno
= REGNO (reg
);
1756 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
1758 if (regno
< FIRST_PSEUDO_REGISTER
)
1760 int j
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1763 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
1765 basic_block b
= candidate_table
[src
].update_bbs
.first_member
[i
];
1767 SET_REGNO_REG_SET (df_get_live_in (b
), regno
+ j
);
1773 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
1775 basic_block b
= candidate_table
[src
].update_bbs
.first_member
[i
];
1777 SET_REGNO_REG_SET (df_get_live_in (b
), regno
);
1783 /* Return 1 if insn can be speculatively moved from block src to trg,
1784 otherwise return 0. Called before first insertion of insn to
1785 ready-list or before the scheduling. */
1788 check_live (rtx insn
, int src
)
1790 /* Find the registers set by instruction. */
1791 if (GET_CODE (PATTERN (insn
)) == SET
1792 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1793 return check_live_1 (src
, PATTERN (insn
));
1794 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1797 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1798 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1799 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1800 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
1809 /* Update the live registers info after insn was moved speculatively from
1810 block src to trg. */
1813 update_live (rtx insn
, int src
)
1815 /* Find the registers set by instruction. */
1816 if (GET_CODE (PATTERN (insn
)) == SET
1817 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1818 update_live_1 (src
, PATTERN (insn
));
1819 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1822 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1823 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1824 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1825 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
1829 /* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1830 #define IS_REACHABLE(bb_from, bb_to) \
1832 || IS_RGN_ENTRY (bb_from) \
1833 || (TEST_BIT (ancestor_edges[bb_to], \
1834 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK (BB_TO_BLOCK (bb_from)))))))
1836 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1839 set_spec_fed (rtx load_insn
)
1841 sd_iterator_def sd_it
;
1844 FOR_EACH_DEP (load_insn
, SD_LIST_FORW
, sd_it
, dep
)
1845 if (DEP_TYPE (dep
) == REG_DEP_TRUE
)
1846 FED_BY_SPEC_LOAD (DEP_CON (dep
)) = 1;
1849 /* On the path from the insn to load_insn_bb, find a conditional
1850 branch depending on insn, that guards the speculative load. */
1853 find_conditional_protection (rtx insn
, int load_insn_bb
)
1855 sd_iterator_def sd_it
;
1858 /* Iterate through DEF-USE forward dependences. */
1859 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
1861 rtx next
= DEP_CON (dep
);
1863 if ((CONTAINING_RGN (BLOCK_NUM (next
)) ==
1864 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
1865 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
1866 && load_insn_bb
!= INSN_BB (next
)
1867 && DEP_TYPE (dep
) == REG_DEP_TRUE
1869 || find_conditional_protection (next
, load_insn_bb
)))
1873 } /* find_conditional_protection */
1875 /* Returns 1 if the same insn1 that participates in the computation
1876 of load_insn's address is feeding a conditional branch that is
1877 guarding on load_insn. This is true if we find two DEF-USE
1879 insn1 -> ... -> conditional-branch
1880 insn1 -> ... -> load_insn,
1881 and if a flow path exists:
1882 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1883 and if insn1 is on the path
1884 region-entry -> ... -> bb_trg -> ... load_insn.
1886 Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
1887 Locate the branch by following INSN_FORW_DEPS from insn1. */
1890 is_conditionally_protected (rtx load_insn
, int bb_src
, int bb_trg
)
1892 sd_iterator_def sd_it
;
1895 FOR_EACH_DEP (load_insn
, SD_LIST_BACK
, sd_it
, dep
)
1897 rtx insn1
= DEP_PRO (dep
);
1899 /* Must be a DEF-USE dependence upon non-branch. */
1900 if (DEP_TYPE (dep
) != REG_DEP_TRUE
1904 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1905 if (INSN_BB (insn1
) == bb_src
1906 || (CONTAINING_RGN (BLOCK_NUM (insn1
))
1907 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
1908 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
1909 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
1912 /* Now search for the conditional-branch. */
1913 if (find_conditional_protection (insn1
, bb_src
))
1916 /* Recursive step: search another insn1, "above" current insn1. */
1917 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
1920 /* The chain does not exist. */
1922 } /* is_conditionally_protected */
1924 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1925 load_insn can move speculatively from bb_src to bb_trg. All the
1926 following must hold:
1928 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1929 (2) load_insn and load1 have a def-use dependence upon
1930 the same insn 'insn1'.
1931 (3) either load2 is in bb_trg, or:
1932 - there's only one split-block, and
1933 - load1 is on the escape path, and
1935 From all these we can conclude that the two loads access memory
1936 addresses that differ at most by a constant, and hence if moving
1937 load_insn would cause an exception, it would have been caused by
1941 is_pfree (rtx load_insn
, int bb_src
, int bb_trg
)
1943 sd_iterator_def back_sd_it
;
1945 candidate
*candp
= candidate_table
+ bb_src
;
1947 if (candp
->split_bbs
.nr_members
!= 1)
1948 /* Must have exactly one escape block. */
1951 FOR_EACH_DEP (load_insn
, SD_LIST_BACK
, back_sd_it
, back_dep
)
1953 rtx insn1
= DEP_PRO (back_dep
);
1955 if (DEP_TYPE (back_dep
) == REG_DEP_TRUE
)
1956 /* Found a DEF-USE dependence (insn1, load_insn). */
1958 sd_iterator_def fore_sd_it
;
1961 FOR_EACH_DEP (insn1
, SD_LIST_FORW
, fore_sd_it
, fore_dep
)
1963 rtx insn2
= DEP_CON (fore_dep
);
1965 if (DEP_TYPE (fore_dep
) == REG_DEP_TRUE
)
1967 /* Found a DEF-USE dependence (insn1, insn2). */
1968 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
1969 /* insn2 not guaranteed to be a 1 base reg load. */
1972 if (INSN_BB (insn2
) == bb_trg
)
1973 /* insn2 is the similar load, in the target block. */
1976 if (*(candp
->split_bbs
.first_member
) == BLOCK_FOR_INSN (insn2
))
1977 /* insn2 is a similar load, in a split-block. */
1984 /* Couldn't find a similar load. */
1988 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1989 a load moved speculatively, or if load_insn is protected by
1990 a compare on load_insn's address). */
1993 is_prisky (rtx load_insn
, int bb_src
, int bb_trg
)
1995 if (FED_BY_SPEC_LOAD (load_insn
))
1998 if (sd_lists_empty_p (load_insn
, SD_LIST_BACK
))
1999 /* Dependence may 'hide' out of the region. */
2002 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2008 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2009 Return 1 if insn is exception-free (and the motion is valid)
2013 is_exception_free (rtx insn
, int bb_src
, int bb_trg
)
2015 int insn_class
= haifa_classify_insn (insn
);
2017 /* Handle non-load insns. */
2028 if (!flag_schedule_speculative_load
)
2030 IS_LOAD_INSN (insn
) = 1;
2037 case PFREE_CANDIDATE
:
2038 if (is_pfree (insn
, bb_src
, bb_trg
))
2040 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2041 case PRISKY_CANDIDATE
:
2042 if (!flag_schedule_speculative_load_dangerous
2043 || is_prisky (insn
, bb_src
, bb_trg
))
2049 return flag_schedule_speculative_load_dangerous
;
2052 /* The number of insns from the current block scheduled so far. */
2053 static int sched_target_n_insns
;
2054 /* The number of insns from the current block to be scheduled in total. */
2055 static int target_n_insns
;
2056 /* The number of insns from the entire region scheduled so far. */
2057 static int sched_n_insns
;
2059 /* Implementations of the sched_info functions for region scheduling. */
2060 static void init_ready_list (void);
2061 static int can_schedule_ready_p (rtx
);
2062 static void begin_schedule_ready (rtx
, rtx
);
2063 static ds_t
new_ready (rtx
, ds_t
);
2064 static int schedule_more_p (void);
2065 static const char *rgn_print_insn (const_rtx
, int);
2066 static int rgn_rank (rtx
, rtx
);
2067 static void compute_jump_reg_dependencies (rtx
, regset
, regset
, regset
);
2069 /* Functions for speculative scheduling. */
2070 static void rgn_add_remove_insn (rtx
, int);
2071 static void rgn_add_block (basic_block
, basic_block
);
2072 static void rgn_fix_recovery_cfg (int, int, int);
2073 static basic_block
advance_target_bb (basic_block
, rtx
);
2075 /* Return nonzero if there are more insns that should be scheduled. */
2078 schedule_more_p (void)
2080 return sched_target_n_insns
< target_n_insns
;
2083 /* Add all insns that are initially ready to the ready list READY. Called
2084 once before scheduling a set of insns. */
2087 init_ready_list (void)
2089 rtx prev_head
= current_sched_info
->prev_head
;
2090 rtx next_tail
= current_sched_info
->next_tail
;
2095 sched_target_n_insns
= 0;
2098 /* Print debugging information. */
2099 if (sched_verbose
>= 5)
2100 debug_rgn_dependencies (target_bb
);
2102 /* Prepare current target block info. */
2103 if (current_nr_blocks
> 1)
2104 compute_trg_info (target_bb
);
2106 /* Initialize ready list with all 'ready' insns in target block.
2107 Count number of insns in the target block being scheduled. */
2108 for (insn
= NEXT_INSN (prev_head
); insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2113 gcc_assert (!(TODO_SPEC (insn
) & BEGIN_CONTROL
));
2116 /* Add to ready list all 'ready' insns in valid source blocks.
2117 For speculative insns, check-live, exception-free, and
2119 for (bb_src
= target_bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
2120 if (IS_VALID (bb_src
))
2126 get_ebb_head_tail (EBB_FIRST_BB (bb_src
), EBB_LAST_BB (bb_src
),
2128 src_next_tail
= NEXT_INSN (tail
);
2131 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
2137 /* Called after taking INSN from the ready list. Returns nonzero if this
2138 insn can be scheduled, nonzero if we should silently discard it. */
2141 can_schedule_ready_p (rtx insn
)
2143 /* An interblock motion? */
2144 if (INSN_BB (insn
) != target_bb
2145 && IS_SPECULATIVE_INSN (insn
)
2146 && !check_live (insn
, INSN_BB (insn
)))
2152 /* Updates counter and other information. Split from can_schedule_ready_p ()
2153 because when we schedule insn speculatively then insn passed to
2154 can_schedule_ready_p () differs from the one passed to
2155 begin_schedule_ready (). */
2157 begin_schedule_ready (rtx insn
, rtx last ATTRIBUTE_UNUSED
)
2159 /* An interblock motion? */
2160 if (INSN_BB (insn
) != target_bb
)
2162 if (IS_SPECULATIVE_INSN (insn
))
2164 gcc_assert (check_live (insn
, INSN_BB (insn
)));
2166 update_live (insn
, INSN_BB (insn
));
2168 /* For speculative load, mark insns fed by it. */
2169 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
2170 set_spec_fed (insn
);
2178 /* In block motion. */
2179 sched_target_n_insns
++;
2184 /* Called after INSN has all its hard dependencies resolved and the speculation
2185 of type TS is enough to overcome them all.
2186 Return nonzero if it should be moved to the ready list or the queue, or zero
2187 if we should silently discard it. */
2189 new_ready (rtx next
, ds_t ts
)
2191 if (INSN_BB (next
) != target_bb
)
2193 int not_ex_free
= 0;
2195 /* For speculative insns, before inserting to ready/queue,
2196 check live, exception-free, and issue-delay. */
2197 if (!IS_VALID (INSN_BB (next
))
2199 || (IS_SPECULATIVE_INSN (next
)
2200 && ((recog_memoized (next
) >= 0
2201 && min_insn_conflict_delay (curr_state
, next
, next
)
2202 > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY
))
2203 || IS_SPECULATION_CHECK_P (next
)
2204 || !check_live (next
, INSN_BB (next
))
2205 || (not_ex_free
= !is_exception_free (next
, INSN_BB (next
),
2209 /* We are here because is_exception_free () == false.
2210 But we possibly can handle that with control speculation. */
2211 && sched_deps_info
->generate_spec_deps
2212 && spec_info
->mask
& BEGIN_CONTROL
)
2216 /* Add control speculation to NEXT's dependency type. */
2217 new_ds
= set_dep_weak (ts
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
2219 /* Check if NEXT can be speculated with new dependency type. */
2220 if (sched_insn_is_legitimate_for_speculation_p (next
, new_ds
))
2221 /* Here we got new control-speculative instruction. */
2224 /* NEXT isn't ready yet. */
2225 ts
= (ts
& ~SPECULATIVE
) | HARD_DEP
;
2228 /* NEXT isn't ready yet. */
2229 ts
= (ts
& ~SPECULATIVE
) | HARD_DEP
;
2236 /* Return a string that contains the insn uid and optionally anything else
2237 necessary to identify this insn in an output. It's valid to use a
2238 static buffer for this. The ALIGNED parameter should cause the string
2239 to be formatted so that multiple output lines will line up nicely. */
2242 rgn_print_insn (const_rtx insn
, int aligned
)
2244 static char tmp
[80];
2247 sprintf (tmp
, "b%3d: i%4d", INSN_BB (insn
), INSN_UID (insn
));
2250 if (current_nr_blocks
> 1 && INSN_BB (insn
) != target_bb
)
2251 sprintf (tmp
, "%d/b%d", INSN_UID (insn
), INSN_BB (insn
));
2253 sprintf (tmp
, "%d", INSN_UID (insn
));
2258 /* Compare priority of two insns. Return a positive number if the second
2259 insn is to be preferred for scheduling, and a negative one if the first
2260 is to be preferred. Zero if they are equally good. */
2263 rgn_rank (rtx insn1
, rtx insn2
)
2265 /* Some comparison make sense in interblock scheduling only. */
2266 if (INSN_BB (insn1
) != INSN_BB (insn2
))
2268 int spec_val
, prob_val
;
2270 /* Prefer an inblock motion on an interblock motion. */
2271 if ((INSN_BB (insn2
) == target_bb
) && (INSN_BB (insn1
) != target_bb
))
2273 if ((INSN_BB (insn1
) == target_bb
) && (INSN_BB (insn2
) != target_bb
))
2276 /* Prefer a useful motion on a speculative one. */
2277 spec_val
= IS_SPECULATIVE_INSN (insn1
) - IS_SPECULATIVE_INSN (insn2
);
2281 /* Prefer a more probable (speculative) insn. */
2282 prob_val
= INSN_PROBABILITY (insn2
) - INSN_PROBABILITY (insn1
);
2289 /* NEXT is an instruction that depends on INSN (a backward dependence);
2290 return nonzero if we should include this dependence in priority
2294 contributes_to_priority (rtx next
, rtx insn
)
2296 /* NEXT and INSN reside in one ebb. */
2297 return BLOCK_TO_BB (BLOCK_NUM (next
)) == BLOCK_TO_BB (BLOCK_NUM (insn
));
2300 /* INSN is a JUMP_INSN, COND_SET is the set of registers that are
2301 conditionally set before INSN. Store the set of registers that
2302 must be considered as used by this jump in USED and that of
2303 registers that must be considered as set in SET. */
2306 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
2307 regset cond_exec ATTRIBUTE_UNUSED
,
2308 regset used ATTRIBUTE_UNUSED
,
2309 regset set ATTRIBUTE_UNUSED
)
2311 /* Nothing to do here, since we postprocess jumps in
2312 add_branch_dependences. */
2315 /* This variable holds common_sched_info hooks and data relevant to
2316 the interblock scheduler. */
2317 static struct common_sched_info_def rgn_common_sched_info
;
2320 /* This holds data for the dependence analysis relevant to
2321 the interblock scheduler. */
2322 static struct sched_deps_info_def rgn_sched_deps_info
;
2324 /* This holds constant data used for initializing the above structure
2325 for the Haifa scheduler. */
2326 static const struct sched_deps_info_def rgn_const_sched_deps_info
=
2328 compute_jump_reg_dependencies
,
2329 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
2333 /* Same as above, but for the selective scheduler. */
2334 static const struct sched_deps_info_def rgn_const_sel_sched_deps_info
=
2336 compute_jump_reg_dependencies
,
2337 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
2341 /* Return true if scheduling INSN will trigger finish of scheduling
2344 rgn_insn_finishes_block_p (rtx insn
)
2346 if (INSN_BB (insn
) == target_bb
2347 && sched_target_n_insns
+ 1 == target_n_insns
)
2348 /* INSN is the last not-scheduled instruction in the current block. */
2354 /* Used in schedule_insns to initialize current_sched_info for scheduling
2355 regions (or single basic blocks). */
2357 static const struct haifa_sched_info rgn_const_sched_info
=
2360 can_schedule_ready_p
,
2365 contributes_to_priority
,
2366 rgn_insn_finishes_block_p
,
2372 rgn_add_remove_insn
,
2373 begin_schedule_ready
,
2378 /* This variable holds the data and hooks needed to the Haifa scheduler backend
2379 for the interblock scheduler frontend. */
2380 static struct haifa_sched_info rgn_sched_info
;
2382 /* Returns maximum priority that an insn was assigned to. */
2385 get_rgn_sched_max_insns_priority (void)
2387 return rgn_sched_info
.sched_max_insns_priority
;
2390 /* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register. */
2393 sets_likely_spilled (rtx pat
)
2396 note_stores (pat
, sets_likely_spilled_1
, &ret
);
2401 sets_likely_spilled_1 (rtx x
, const_rtx pat
, void *data
)
2403 bool *ret
= (bool *) data
;
2405 if (GET_CODE (pat
) == SET
2407 && REGNO (x
) < FIRST_PSEUDO_REGISTER
2408 && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x
))))
2412 /* A bitmap to note insns that participate in any dependency. Used in
2413 add_branch_dependences. */
2414 static sbitmap insn_referenced
;
2416 /* Add dependences so that branches are scheduled to run last in their
2419 add_branch_dependences (rtx head
, rtx tail
)
2423 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2424 that can throw exceptions, force them to remain in order at the end of
2425 the block by adding dependencies and giving the last a high priority.
2426 There may be notes present, and prev_head may also be a note.
2428 Branches must obviously remain at the end. Calls should remain at the
2429 end since moving them results in worse register allocation. Uses remain
2430 at the end to ensure proper register allocation.
2432 cc0 setters remain at the end because they can't be moved away from
2435 COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
2437 Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values)
2438 are not moved before reload because we can wind up with register
2439 allocation failures. */
2443 while (CALL_P (insn
)
2445 || (NONJUMP_INSN_P (insn
)
2446 && (GET_CODE (PATTERN (insn
)) == USE
2447 || GET_CODE (PATTERN (insn
)) == CLOBBER
2448 || can_throw_internal (insn
)
2450 || sets_cc0_p (PATTERN (insn
))
2452 || (!reload_completed
2453 && sets_likely_spilled (PATTERN (insn
)))))
2459 && sd_find_dep_between (insn
, last
, false) == NULL
)
2461 if (! sched_insns_conditions_mutex_p (last
, insn
))
2462 add_dependence (last
, insn
, REG_DEP_ANTI
);
2463 SET_BIT (insn_referenced
, INSN_LUID (insn
));
2466 CANT_MOVE (insn
) = 1;
2471 /* Don't overrun the bounds of the basic block. */
2475 insn
= PREV_INSN (insn
);
2478 /* Make sure these insns are scheduled last in their block. */
2481 while (insn
!= head
)
2483 insn
= prev_nonnote_insn (insn
);
2485 if (TEST_BIT (insn_referenced
, INSN_LUID (insn
)))
2488 if (! sched_insns_conditions_mutex_p (last
, insn
))
2489 add_dependence (last
, insn
, REG_DEP_ANTI
);
2492 #ifdef HAVE_conditional_execution
2493 /* Finally, if the block ends in a jump, and we are doing intra-block
2494 scheduling, make sure that the branch depends on any COND_EXEC insns
2495 inside the block to avoid moving the COND_EXECs past the branch insn.
2497 We only have to do this after reload, because (1) before reload there
2498 are no COND_EXEC insns, and (2) the region scheduler is an intra-block
2499 scheduler after reload.
2501 FIXME: We could in some cases move COND_EXEC insns past the branch if
2502 this scheduler would be a little smarter. Consider this code:
2510 On a target with a one cycle stall on a memory access the optimal
2519 We don't want to put the 'X += 12' before the branch because it just
2520 wastes a cycle of execution time when the branch is taken.
2522 Note that in the example "!C" will always be true. That is another
2523 possible improvement for handling COND_EXECs in this scheduler: it
2524 could remove always-true predicates. */
2526 if (!reload_completed
|| ! JUMP_P (tail
))
2530 while (insn
!= head
)
2532 insn
= PREV_INSN (insn
);
2534 /* Note that we want to add this dependency even when
2535 sched_insns_conditions_mutex_p returns true. The whole point
2536 is that we _want_ this dependency, even if these insns really
2538 if (INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == COND_EXEC
)
2539 add_dependence (tail
, insn
, REG_DEP_ANTI
);
2544 /* Data structures for the computation of data dependences in a regions. We
2545 keep one `deps' structure for every basic block. Before analyzing the
2546 data dependences for a bb, its variables are initialized as a function of
2547 the variables of its predecessors. When the analysis for a bb completes,
2548 we save the contents to the corresponding bb_deps[bb] variable. */
2550 static struct deps
*bb_deps
;
2552 /* Duplicate the INSN_LIST elements of COPY and prepend them to OLD. */
2555 concat_INSN_LIST (rtx copy
, rtx old
)
2558 for (; copy
; copy
= XEXP (copy
, 1))
2559 new_rtx
= alloc_INSN_LIST (XEXP (copy
, 0), new_rtx
);
2564 concat_insn_mem_list (rtx copy_insns
, rtx copy_mems
, rtx
*old_insns_p
,
2567 rtx new_insns
= *old_insns_p
;
2568 rtx new_mems
= *old_mems_p
;
2572 new_insns
= alloc_INSN_LIST (XEXP (copy_insns
, 0), new_insns
);
2573 new_mems
= alloc_EXPR_LIST (VOIDmode
, XEXP (copy_mems
, 0), new_mems
);
2574 copy_insns
= XEXP (copy_insns
, 1);
2575 copy_mems
= XEXP (copy_mems
, 1);
2578 *old_insns_p
= new_insns
;
2579 *old_mems_p
= new_mems
;
2582 /* Join PRED_DEPS to the SUCC_DEPS. */
2584 deps_join (struct deps
*succ_deps
, struct deps
*pred_deps
)
2587 reg_set_iterator rsi
;
2589 /* The reg_last lists are inherited by successor. */
2590 EXECUTE_IF_SET_IN_REG_SET (&pred_deps
->reg_last_in_use
, 0, reg
, rsi
)
2592 struct deps_reg
*pred_rl
= &pred_deps
->reg_last
[reg
];
2593 struct deps_reg
*succ_rl
= &succ_deps
->reg_last
[reg
];
2595 succ_rl
->uses
= concat_INSN_LIST (pred_rl
->uses
, succ_rl
->uses
);
2596 succ_rl
->sets
= concat_INSN_LIST (pred_rl
->sets
, succ_rl
->sets
);
2597 succ_rl
->clobbers
= concat_INSN_LIST (pred_rl
->clobbers
,
2599 succ_rl
->uses_length
+= pred_rl
->uses_length
;
2600 succ_rl
->clobbers_length
+= pred_rl
->clobbers_length
;
2602 IOR_REG_SET (&succ_deps
->reg_last_in_use
, &pred_deps
->reg_last_in_use
);
2604 /* Mem read/write lists are inherited by successor. */
2605 concat_insn_mem_list (pred_deps
->pending_read_insns
,
2606 pred_deps
->pending_read_mems
,
2607 &succ_deps
->pending_read_insns
,
2608 &succ_deps
->pending_read_mems
);
2609 concat_insn_mem_list (pred_deps
->pending_write_insns
,
2610 pred_deps
->pending_write_mems
,
2611 &succ_deps
->pending_write_insns
,
2612 &succ_deps
->pending_write_mems
);
2614 succ_deps
->last_pending_memory_flush
2615 = concat_INSN_LIST (pred_deps
->last_pending_memory_flush
,
2616 succ_deps
->last_pending_memory_flush
);
2618 succ_deps
->pending_read_list_length
+= pred_deps
->pending_read_list_length
;
2619 succ_deps
->pending_write_list_length
+= pred_deps
->pending_write_list_length
;
2620 succ_deps
->pending_flush_length
+= pred_deps
->pending_flush_length
;
2622 /* last_function_call is inherited by successor. */
2623 succ_deps
->last_function_call
2624 = concat_INSN_LIST (pred_deps
->last_function_call
,
2625 succ_deps
->last_function_call
);
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
*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
;
2661 /* Can't allow these to be freed twice. */
2662 pred_deps
->pending_read_insns
= 0;
2663 pred_deps
->pending_read_mems
= 0;
2664 pred_deps
->pending_write_insns
= 0;
2665 pred_deps
->pending_write_mems
= 0;
2668 /* Compute dependences inside bb. In a multiple blocks region:
2669 (1) a bb is analyzed after its predecessors, and (2) the lists in
2670 effect at the end of bb (after analyzing for bb) are inherited by
2673 Specifically for reg-reg data dependences, the block insns are
2674 scanned by sched_analyze () top-to-bottom. Two lists are
2675 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2676 and reg_last[].uses for register USEs.
2678 When analysis is completed for bb, we update for its successors:
2679 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2680 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2682 The mechanism for computing mem-mem data dependence is very
2683 similar, and the result is interblock dependences in the region. */
2686 compute_block_dependences (int bb
)
2689 struct deps tmp_deps
;
2691 tmp_deps
= bb_deps
[bb
];
2693 /* Do the analysis for this block. */
2694 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2695 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2697 sched_analyze (&tmp_deps
, head
, tail
);
2699 /* Selective scheduling handles control dependencies by itself. */
2700 if (!sel_sched_p ())
2701 add_branch_dependences (head
, tail
);
2703 if (current_nr_blocks
> 1)
2704 propagate_deps (bb
, &tmp_deps
);
2706 /* Free up the INSN_LISTs. */
2707 free_deps (&tmp_deps
);
2709 if (targetm
.sched
.dependencies_evaluation_hook
)
2710 targetm
.sched
.dependencies_evaluation_hook (head
, tail
);
2713 /* Free dependencies of instructions inside BB. */
2715 free_block_dependencies (int bb
)
2720 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2722 sched_free_deps (head
, tail
, true);
2725 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2726 them to the unused_*_list variables, so that they can be reused. */
2729 free_pending_lists (void)
2733 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2735 free_INSN_LIST_list (&bb_deps
[bb
].pending_read_insns
);
2736 free_INSN_LIST_list (&bb_deps
[bb
].pending_write_insns
);
2737 free_EXPR_LIST_list (&bb_deps
[bb
].pending_read_mems
);
2738 free_EXPR_LIST_list (&bb_deps
[bb
].pending_write_mems
);
2742 /* Print dependences for debugging starting from FROM_BB.
2743 Callable from debugger. */
2744 /* Print dependences for debugging starting from FROM_BB.
2745 Callable from debugger. */
2747 debug_rgn_dependencies (int from_bb
)
2751 fprintf (sched_dump
,
2752 ";; --------------- forward dependences: ------------ \n");
2754 for (bb
= from_bb
; bb
< current_nr_blocks
; bb
++)
2758 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2759 fprintf (sched_dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
2760 BB_TO_BLOCK (bb
), bb
);
2762 debug_dependencies (head
, tail
);
2766 /* Print dependencies information for instructions between HEAD and TAIL.
2767 ??? This function would probably fit best in haifa-sched.c. */
2768 void debug_dependencies (rtx head
, rtx tail
)
2771 rtx next_tail
= NEXT_INSN (tail
);
2773 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2774 "insn", "code", "bb", "dep", "prio", "cost",
2776 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2777 "----", "----", "--", "---", "----", "----",
2780 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2782 if (! INSN_P (insn
))
2785 fprintf (sched_dump
, ";; %6d ", INSN_UID (insn
));
2788 n
= NOTE_KIND (insn
);
2789 fprintf (sched_dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
2792 fprintf (sched_dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
2796 fprintf (sched_dump
,
2797 ";; %s%5d%6d%6d%6d%6d%6d ",
2798 (SCHED_GROUP_P (insn
) ? "+" : " "),
2802 sched_emulate_haifa_p
? -1 : sd_lists_size (insn
, SD_LIST_BACK
),
2803 (sel_sched_p () ? (sched_emulate_haifa_p
? -1
2804 : INSN_PRIORITY (insn
))
2805 : INSN_PRIORITY (insn
)),
2806 (sel_sched_p () ? (sched_emulate_haifa_p
? -1
2808 : insn_cost (insn
)));
2810 if (recog_memoized (insn
) < 0)
2811 fprintf (sched_dump
, "nothing");
2813 print_reservation (sched_dump
, insn
);
2815 fprintf (sched_dump
, "\t: ");
2817 sd_iterator_def sd_it
;
2820 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
2821 fprintf (sched_dump
, "%d ", INSN_UID (DEP_CON (dep
)));
2823 fprintf (sched_dump
, "\n");
2826 fprintf (sched_dump
, "\n");
2829 /* Returns true if all the basic blocks of the current region have
2830 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
2832 sched_is_disabled_for_current_region_p (void)
2836 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2837 if (!(BASIC_BLOCK (BB_TO_BLOCK (bb
))->flags
& BB_DISABLE_SCHEDULE
))
2843 /* Free all region dependencies saved in INSN_BACK_DEPS and
2844 INSN_RESOLVED_BACK_DEPS. The Haifa scheduler does this on the fly
2845 when scheduling, so this function is supposed to be called from
2846 the selective scheduling only. */
2848 free_rgn_deps (void)
2852 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2856 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2857 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2859 sched_free_deps (head
, tail
, false);
2863 static int rgn_n_insns
;
2865 /* Compute insn priority for a current region. */
2867 compute_priorities (void)
2871 current_sched_info
->sched_max_insns_priority
= 0;
2872 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2876 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2877 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2879 rgn_n_insns
+= set_priorities (head
, tail
);
2881 current_sched_info
->sched_max_insns_priority
++;
2884 /* Schedule a region. A region is either an inner loop, a loop-free
2885 subroutine, or a single basic block. Each bb in the region is
2886 scheduled after its flow predecessors. */
2889 schedule_region (int rgn
)
2892 int sched_rgn_n_insns
= 0;
2896 rgn_setup_region (rgn
);
2898 /* Don't schedule region that is marked by
2899 NOTE_DISABLE_SCHED_OF_BLOCK. */
2900 if (sched_is_disabled_for_current_region_p ())
2903 sched_rgn_compute_dependencies (rgn
);
2905 sched_rgn_local_init (rgn
);
2907 /* Set priorities. */
2908 compute_priorities ();
2910 sched_extend_ready_list (rgn_n_insns
);
2912 /* Now we can schedule all blocks. */
2913 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2915 basic_block first_bb
, last_bb
, curr_bb
;
2918 first_bb
= EBB_FIRST_BB (bb
);
2919 last_bb
= EBB_LAST_BB (bb
);
2921 get_ebb_head_tail (first_bb
, last_bb
, &head
, &tail
);
2923 if (no_real_insns_p (head
, tail
))
2925 gcc_assert (first_bb
== last_bb
);
2929 current_sched_info
->prev_head
= PREV_INSN (head
);
2930 current_sched_info
->next_tail
= NEXT_INSN (tail
);
2932 remove_notes (head
, tail
);
2934 unlink_bb_notes (first_bb
, last_bb
);
2938 gcc_assert (flag_schedule_interblock
|| current_nr_blocks
== 1);
2939 current_sched_info
->queue_must_finish_empty
= current_nr_blocks
== 1;
2942 if (dbg_cnt (sched_block
))
2944 schedule_block (&curr_bb
);
2945 gcc_assert (EBB_FIRST_BB (bb
) == first_bb
);
2946 sched_rgn_n_insns
+= sched_n_insns
;
2950 sched_rgn_n_insns
+= rgn_n_insns
;
2954 if (current_nr_blocks
> 1)
2958 /* Sanity check: verify that all region insns were scheduled. */
2959 gcc_assert (sched_rgn_n_insns
== rgn_n_insns
);
2961 sched_finish_ready_list ();
2963 /* Done with this region. */
2964 sched_rgn_local_finish ();
2966 /* Free dependencies. */
2967 for (bb
= 0; bb
< current_nr_blocks
; ++bb
)
2968 free_block_dependencies (bb
);
2970 gcc_assert (haifa_recovery_bb_ever_added_p
2971 || deps_pools_are_empty_p ());
2974 /* Initialize data structures for region scheduling. */
2977 sched_rgn_init (bool single_blocks_p
)
2979 min_spec_prob
= ((PARAM_VALUE (PARAM_MIN_SPEC_PROB
) * REG_BR_PROB_BASE
)
2987 CONTAINING_RGN (ENTRY_BLOCK
) = -1;
2988 CONTAINING_RGN (EXIT_BLOCK
) = -1;
2990 /* Compute regions for scheduling. */
2992 || n_basic_blocks
== NUM_FIXED_BLOCKS
+ 1
2993 || !flag_schedule_interblock
2994 || is_cfg_nonregular ())
2996 find_single_block_region (sel_sched_p ());
3000 /* Compute the dominators and post dominators. */
3001 if (!sel_sched_p ())
3002 calculate_dominance_info (CDI_DOMINATORS
);
3007 if (sched_verbose
>= 3)
3010 /* For now. This will move as more and more of haifa is converted
3011 to using the cfg code. */
3012 if (!sel_sched_p ())
3013 free_dominance_info (CDI_DOMINATORS
);
3016 gcc_assert (0 < nr_regions
&& nr_regions
<= n_basic_blocks
);
3018 RGN_BLOCKS (nr_regions
) = (RGN_BLOCKS (nr_regions
- 1) +
3019 RGN_NR_BLOCKS (nr_regions
- 1));
3022 /* Free data structures for region scheduling. */
3024 sched_rgn_finish (void)
3026 /* Reposition the prologue and epilogue notes in case we moved the
3027 prologue/epilogue insns. */
3028 if (reload_completed
)
3029 reposition_prologue_and_epilogue_notes ();
3033 if (reload_completed
== 0
3034 && flag_schedule_interblock
)
3036 fprintf (sched_dump
,
3037 "\n;; Procedure interblock/speculative motions == %d/%d \n",
3041 gcc_assert (nr_inter
<= 0);
3042 fprintf (sched_dump
, "\n\n");
3050 free (rgn_bb_table
);
3051 rgn_bb_table
= NULL
;
3056 free (containing_rgn
);
3057 containing_rgn
= NULL
;
3063 /* Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
3064 point to the region RGN. */
3066 rgn_setup_region (int rgn
)
3070 /* Set variables for the current region. */
3071 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
3072 current_blocks
= RGN_BLOCKS (rgn
);
3074 /* EBB_HEAD is a region-scope structure. But we realloc it for
3075 each region to save time/memory/something else.
3076 See comments in add_block1, for what reasons we allocate +1 element. */
3077 ebb_head
= XRESIZEVEC (int, ebb_head
, current_nr_blocks
+ 1);
3078 for (bb
= 0; bb
<= current_nr_blocks
; bb
++)
3079 ebb_head
[bb
] = current_blocks
+ bb
;
3082 /* Compute instruction dependencies in region RGN. */
3084 sched_rgn_compute_dependencies (int rgn
)
3086 if (!RGN_DONT_CALC_DEPS (rgn
))
3091 sched_emulate_haifa_p
= 1;
3093 init_deps_global ();
3095 /* Initializations for region data dependence analysis. */
3096 bb_deps
= XNEWVEC (struct deps
, current_nr_blocks
);
3097 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3098 init_deps (bb_deps
+ bb
);
3100 /* Initialize bitmap used in add_branch_dependences. */
3101 insn_referenced
= sbitmap_alloc (sched_max_luid
);
3102 sbitmap_zero (insn_referenced
);
3104 /* Compute backward dependencies. */
3105 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3106 compute_block_dependences (bb
);
3108 sbitmap_free (insn_referenced
);
3109 free_pending_lists ();
3110 finish_deps_global ();
3113 /* We don't want to recalculate this twice. */
3114 RGN_DONT_CALC_DEPS (rgn
) = 1;
3117 sched_emulate_haifa_p
= 0;
3120 /* (This is a recovery block. It is always a single block region.)
3121 OR (We use selective scheduling.) */
3122 gcc_assert (current_nr_blocks
== 1 || sel_sched_p ());
3125 /* Init region data structures. Returns true if this region should
3126 not be scheduled. */
3128 sched_rgn_local_init (int rgn
)
3132 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
3133 if (current_nr_blocks
> 1)
3139 prob
= XNEWVEC (int, current_nr_blocks
);
3141 dom
= sbitmap_vector_alloc (current_nr_blocks
, current_nr_blocks
);
3142 sbitmap_vector_zero (dom
, current_nr_blocks
);
3144 /* Use ->aux to implement EDGE_TO_BIT mapping. */
3148 if (CONTAINING_RGN (block
->index
) != rgn
)
3150 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3151 SET_EDGE_TO_BIT (e
, rgn_nr_edges
++);
3154 rgn_edges
= XNEWVEC (edge
, rgn_nr_edges
);
3158 if (CONTAINING_RGN (block
->index
) != rgn
)
3160 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3161 rgn_edges
[rgn_nr_edges
++] = e
;
3165 pot_split
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
3166 sbitmap_vector_zero (pot_split
, current_nr_blocks
);
3167 ancestor_edges
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
3168 sbitmap_vector_zero (ancestor_edges
, current_nr_blocks
);
3170 /* Compute probabilities, dominators, split_edges. */
3171 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3172 compute_dom_prob_ps (bb
);
3174 /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
3175 /* We don't need them anymore. But we want to avoid duplication of
3176 aux fields in the newly created edges. */
3179 if (CONTAINING_RGN (block
->index
) != rgn
)
3181 FOR_EACH_EDGE (e
, ei
, block
->succs
)
3187 /* Free data computed for the finished region. */
3189 sched_rgn_local_free (void)
3192 sbitmap_vector_free (dom
);
3193 sbitmap_vector_free (pot_split
);
3194 sbitmap_vector_free (ancestor_edges
);
3198 /* Free data computed for the finished region. */
3200 sched_rgn_local_finish (void)
3202 if (current_nr_blocks
> 1 && !sel_sched_p ())
3204 sched_rgn_local_free ();
3208 /* Setup scheduler infos. */
3210 rgn_setup_common_sched_info (void)
3212 memcpy (&rgn_common_sched_info
, &haifa_common_sched_info
,
3213 sizeof (rgn_common_sched_info
));
3215 rgn_common_sched_info
.fix_recovery_cfg
= rgn_fix_recovery_cfg
;
3216 rgn_common_sched_info
.add_block
= rgn_add_block
;
3217 rgn_common_sched_info
.estimate_number_of_insns
3218 = rgn_estimate_number_of_insns
;
3219 rgn_common_sched_info
.sched_pass_id
= SCHED_RGN_PASS
;
3221 common_sched_info
= &rgn_common_sched_info
;
3224 /* Setup all *_sched_info structures (for the Haifa frontend
3225 and for the dependence analysis) in the interblock scheduler. */
3227 rgn_setup_sched_infos (void)
3229 if (!sel_sched_p ())
3230 memcpy (&rgn_sched_deps_info
, &rgn_const_sched_deps_info
,
3231 sizeof (rgn_sched_deps_info
));
3233 memcpy (&rgn_sched_deps_info
, &rgn_const_sel_sched_deps_info
,
3234 sizeof (rgn_sched_deps_info
));
3236 sched_deps_info
= &rgn_sched_deps_info
;
3238 memcpy (&rgn_sched_info
, &rgn_const_sched_info
, sizeof (rgn_sched_info
));
3239 current_sched_info
= &rgn_sched_info
;
3242 /* The one entry point in this file. */
3244 schedule_insns (void)
3248 /* Taking care of this degenerate case makes the rest of
3249 this code simpler. */
3250 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
3253 rgn_setup_common_sched_info ();
3254 rgn_setup_sched_infos ();
3256 haifa_sched_init ();
3257 sched_rgn_init (reload_completed
);
3259 bitmap_initialize (¬_in_df
, 0);
3260 bitmap_clear (¬_in_df
);
3262 /* Schedule every region in the subroutine. */
3263 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
3264 if (dbg_cnt (sched_region
))
3265 schedule_region (rgn
);
3268 sched_rgn_finish ();
3269 bitmap_clear (¬_in_df
);
3271 haifa_sched_finish ();
3274 /* INSN has been added to/removed from current region. */
3276 rgn_add_remove_insn (rtx insn
, int remove_p
)
3283 if (INSN_BB (insn
) == target_bb
)
3292 /* Extend internal data structures. */
3294 extend_regions (void)
3296 rgn_table
= XRESIZEVEC (region
, rgn_table
, n_basic_blocks
);
3297 rgn_bb_table
= XRESIZEVEC (int, rgn_bb_table
, n_basic_blocks
);
3298 block_to_bb
= XRESIZEVEC (int, block_to_bb
, last_basic_block
);
3299 containing_rgn
= XRESIZEVEC (int, containing_rgn
, last_basic_block
);
3303 rgn_make_new_region_out_of_new_block (basic_block bb
)
3307 i
= RGN_BLOCKS (nr_regions
);
3308 /* I - first free position in rgn_bb_table. */
3310 rgn_bb_table
[i
] = bb
->index
;
3311 RGN_NR_BLOCKS (nr_regions
) = 1;
3312 RGN_HAS_REAL_EBB (nr_regions
) = 0;
3313 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
3314 CONTAINING_RGN (bb
->index
) = nr_regions
;
3315 BLOCK_TO_BB (bb
->index
) = 0;
3319 RGN_BLOCKS (nr_regions
) = i
+ 1;
3322 /* BB was added to ebb after AFTER. */
3324 rgn_add_block (basic_block bb
, basic_block after
)
3327 bitmap_set_bit (¬_in_df
, bb
->index
);
3329 if (after
== 0 || after
== EXIT_BLOCK_PTR
)
3331 rgn_make_new_region_out_of_new_block (bb
);
3332 RGN_DONT_CALC_DEPS (nr_regions
- 1) = (after
== EXIT_BLOCK_PTR
);
3338 /* We need to fix rgn_table, block_to_bb, containing_rgn
3341 BLOCK_TO_BB (bb
->index
) = BLOCK_TO_BB (after
->index
);
3343 /* We extend ebb_head to one more position to
3344 easily find the last position of the last ebb in
3345 the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
3346 is _always_ valid for access. */
3348 i
= BLOCK_TO_BB (after
->index
) + 1;
3349 pos
= ebb_head
[i
] - 1;
3350 /* Now POS is the index of the last block in the region. */
3352 /* Find index of basic block AFTER. */
3353 for (; rgn_bb_table
[pos
] != after
->index
; pos
--);
3356 gcc_assert (pos
> ebb_head
[i
- 1]);
3358 /* i - ebb right after "AFTER". */
3359 /* ebb_head[i] - VALID. */
3361 /* Source position: ebb_head[i]
3362 Destination position: ebb_head[i] + 1
3364 RGN_BLOCKS (nr_regions) - 1
3365 Number of elements to copy: (last_position) - (source_position) + 1
3368 memmove (rgn_bb_table
+ pos
+ 1,
3370 ((RGN_BLOCKS (nr_regions
) - 1) - (pos
) + 1)
3371 * sizeof (*rgn_bb_table
));
3373 rgn_bb_table
[pos
] = bb
->index
;
3375 for (; i
<= current_nr_blocks
; i
++)
3378 i
= CONTAINING_RGN (after
->index
);
3379 CONTAINING_RGN (bb
->index
) = i
;
3381 RGN_HAS_REAL_EBB (i
) = 1;
3383 for (++i
; i
<= nr_regions
; i
++)
3388 /* Fix internal data after interblock movement of jump instruction.
3389 For parameter meaning please refer to
3390 sched-int.h: struct sched_info: fix_recovery_cfg. */
3392 rgn_fix_recovery_cfg (int bbi
, int check_bbi
, int check_bb_nexti
)
3394 int old_pos
, new_pos
, i
;
3396 BLOCK_TO_BB (check_bb_nexti
) = BLOCK_TO_BB (bbi
);
3398 for (old_pos
= ebb_head
[BLOCK_TO_BB (check_bbi
) + 1] - 1;
3399 rgn_bb_table
[old_pos
] != check_bb_nexti
;
3401 gcc_assert (old_pos
> ebb_head
[BLOCK_TO_BB (check_bbi
)]);
3403 for (new_pos
= ebb_head
[BLOCK_TO_BB (bbi
) + 1] - 1;
3404 rgn_bb_table
[new_pos
] != bbi
;
3407 gcc_assert (new_pos
> ebb_head
[BLOCK_TO_BB (bbi
)]);
3409 gcc_assert (new_pos
< old_pos
);
3411 memmove (rgn_bb_table
+ new_pos
+ 1,
3412 rgn_bb_table
+ new_pos
,
3413 (old_pos
- new_pos
) * sizeof (*rgn_bb_table
));
3415 rgn_bb_table
[new_pos
] = check_bb_nexti
;
3417 for (i
= BLOCK_TO_BB (bbi
) + 1; i
<= BLOCK_TO_BB (check_bbi
); i
++)
3421 /* Return next block in ebb chain. For parameter meaning please refer to
3422 sched-int.h: struct sched_info: advance_target_bb. */
3424 advance_target_bb (basic_block bb
, rtx insn
)
3429 gcc_assert (BLOCK_TO_BB (bb
->index
) == target_bb
3430 && BLOCK_TO_BB (bb
->next_bb
->index
) == target_bb
);
3437 gate_handle_sched (void)
3439 #ifdef INSN_SCHEDULING
3440 return flag_schedule_insns
&& dbg_cnt (sched_func
);
3446 /* Run instruction scheduler. */
3448 rest_of_handle_sched (void)
3450 #ifdef INSN_SCHEDULING
3451 if (flag_selective_scheduling
3452 && ! maybe_skip_selective_scheduling ())
3453 run_selective_scheduling ();
3461 gate_handle_sched2 (void)
3463 #ifdef INSN_SCHEDULING
3464 return optimize
> 0 && flag_schedule_insns_after_reload
3465 && dbg_cnt (sched2_func
);
3471 /* Run second scheduling pass after reload. */
3473 rest_of_handle_sched2 (void)
3475 #ifdef INSN_SCHEDULING
3476 if (flag_selective_scheduling2
3477 && ! maybe_skip_selective_scheduling ())
3478 run_selective_scheduling ();
3481 /* Do control and data sched analysis again,
3482 and write some more of the results to dump file. */
3483 if (flag_sched2_use_superblocks
|| flag_sched2_use_traces
)
3492 struct rtl_opt_pass pass_sched
=
3496 "sched1", /* name */
3497 gate_handle_sched
, /* gate */
3498 rest_of_handle_sched
, /* execute */
3501 0, /* static_pass_number */
3502 TV_SCHED
, /* tv_id */
3503 0, /* properties_required */
3504 0, /* properties_provided */
3505 0, /* properties_destroyed */
3506 0, /* todo_flags_start */
3507 TODO_df_finish
| TODO_verify_rtl_sharing
|
3510 TODO_ggc_collect
/* todo_flags_finish */
3514 struct rtl_opt_pass pass_sched2
=
3518 "sched2", /* name */
3519 gate_handle_sched2
, /* gate */
3520 rest_of_handle_sched2
, /* execute */
3523 0, /* static_pass_number */
3524 TV_SCHED2
, /* tv_id */
3525 0, /* properties_required */
3526 0, /* properties_provided */
3527 0, /* properties_destroyed */
3528 0, /* todo_flags_start */
3529 TODO_df_finish
| TODO_verify_rtl_sharing
|
3532 TODO_ggc_collect
/* todo_flags_finish */