1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5 and currently maintained by, Jim Wilson (wilson@cygnus.com)
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING. If not, write to the Free
21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
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"
69 #include "tree-pass.h"
71 /* Define when we want to do count REG_DEAD notes before and after scheduling
72 for sanity checking. We can't do that when conditional execution is used,
73 as REG_DEAD exist only for unconditional deaths. */
75 #if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING)
76 #define CHECK_DEAD_NOTES 1
78 #define CHECK_DEAD_NOTES 0
82 #ifdef INSN_SCHEDULING
83 /* Some accessor macros for h_i_d members only used within this file. */
84 #define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count)
85 #define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load)
86 #define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn)
88 /* nr_inter/spec counts interblock/speculative motion for the function. */
89 static int nr_inter
, nr_spec
;
91 static int is_cfg_nonregular (void);
92 static bool sched_is_disabled_for_current_region_p (void);
94 /* A region is the main entity for interblock scheduling: insns
95 are allowed to move between blocks in the same region, along
96 control flow graph edges, in the 'up' direction. */
99 /* Number of extended basic blocks in region. */
101 /* cblocks in the region (actually index in rgn_bb_table). */
103 /* Dependencies for this region are already computed. Basically, indicates,
104 that this is a recovery block. */
105 unsigned int dont_calc_deps
: 1;
106 /* This region has at least one non-trivial ebb. */
107 unsigned int has_real_ebb
: 1;
111 /* Number of regions in the procedure. */
112 static int nr_regions
;
114 /* Table of region descriptions. */
115 static region
*rgn_table
;
117 /* Array of lists of regions' blocks. */
118 static int *rgn_bb_table
;
120 /* Topological order of blocks in the region (if b2 is reachable from
121 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
122 always referred to by either block or b, while its topological
123 order name (in the region) is referred to by bb. */
124 static int *block_to_bb
;
126 /* The number of the region containing a block. */
127 static int *containing_rgn
;
129 /* The minimum probability of reaching a source block so that it will be
130 considered for speculative scheduling. */
131 static int min_spec_prob
;
133 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
134 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
135 #define RGN_DONT_CALC_DEPS(rgn) (rgn_table[rgn].dont_calc_deps)
136 #define RGN_HAS_REAL_EBB(rgn) (rgn_table[rgn].has_real_ebb)
137 #define BLOCK_TO_BB(block) (block_to_bb[block])
138 #define CONTAINING_RGN(block) (containing_rgn[block])
140 void debug_regions (void);
141 static void find_single_block_region (void);
142 static void find_rgns (void);
143 static void extend_rgns (int *, int *, sbitmap
, int *);
144 static bool too_large (int, int *, int *);
146 extern void debug_live (int, int);
148 /* Blocks of the current region being scheduled. */
149 static int current_nr_blocks
;
150 static int current_blocks
;
152 static int rgn_n_insns
;
154 /* The mapping from ebb to block. */
155 /* ebb_head [i] - is index in rgn_bb_table, while
156 EBB_HEAD (i) - is basic block index.
157 BASIC_BLOCK (EBB_HEAD (i)) - head of ebb. */
158 #define BB_TO_BLOCK(ebb) (rgn_bb_table[ebb_head[ebb]])
159 #define EBB_FIRST_BB(ebb) BASIC_BLOCK (BB_TO_BLOCK (ebb))
160 #define EBB_LAST_BB(ebb) BASIC_BLOCK (rgn_bb_table[ebb_head[ebb + 1] - 1])
162 /* Target info declarations.
164 The block currently being scheduled is referred to as the "target" block,
165 while other blocks in the region from which insns can be moved to the
166 target are called "source" blocks. The candidate structure holds info
167 about such sources: are they valid? Speculative? Etc. */
170 basic_block
*first_member
;
185 static candidate
*candidate_table
;
187 /* A speculative motion requires checking live information on the path
188 from 'source' to 'target'. The split blocks are those to be checked.
189 After a speculative motion, live information should be modified in
192 Lists of split and update blocks for each candidate of the current
193 target are in array bblst_table. */
194 static basic_block
*bblst_table
;
195 static int bblst_size
, bblst_last
;
197 #define IS_VALID(src) ( candidate_table[src].is_valid )
198 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
199 #define SRC_PROB(src) ( candidate_table[src].src_prob )
201 /* The bb being currently scheduled. */
202 static int target_bb
;
212 static edge
*edgelst_table
;
213 static int edgelst_last
;
215 static void extract_edgelst (sbitmap
, edgelst
*);
218 /* Target info functions. */
219 static void split_edges (int, int, edgelst
*);
220 static void compute_trg_info (int);
221 void debug_candidate (int);
222 void debug_candidates (int);
224 /* Dominators array: dom[i] contains the sbitmap of dominators of
225 bb i in the region. */
228 /* bb 0 is the only region entry. */
229 #define IS_RGN_ENTRY(bb) (!bb)
231 /* Is bb_src dominated by bb_trg. */
232 #define IS_DOMINATED(bb_src, bb_trg) \
233 ( TEST_BIT (dom[bb_src], bb_trg) )
235 /* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
236 the probability of bb i relative to the region entry. */
239 /* Bit-set of edges, where bit i stands for edge i. */
240 typedef sbitmap edgeset
;
242 /* Number of edges in the region. */
243 static int rgn_nr_edges
;
245 /* Array of size rgn_nr_edges. */
246 static edge
*rgn_edges
;
248 /* Mapping from each edge in the graph to its number in the rgn. */
249 #define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
250 #define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
252 /* The split edges of a source bb is different for each target
253 bb. In order to compute this efficiently, the 'potential-split edges'
254 are computed for each bb prior to scheduling a region. This is actually
255 the split edges of each bb relative to the region entry.
257 pot_split[bb] is the set of potential split edges of bb. */
258 static edgeset
*pot_split
;
260 /* For every bb, a set of its ancestor edges. */
261 static edgeset
*ancestor_edges
;
263 /* Array of EBBs sizes. Currently we can get a ebb only through
264 splitting of currently scheduling block, therefore, we don't need
265 ebb_head array for every region, its sufficient to hold it only
267 static int *ebb_head
;
269 static void compute_dom_prob_ps (int);
271 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
272 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
273 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
275 /* Speculative scheduling functions. */
276 static int check_live_1 (int, rtx
);
277 static void update_live_1 (int, rtx
);
278 static int check_live (rtx
, int);
279 static void update_live (rtx
, int);
280 static void set_spec_fed (rtx
);
281 static int is_pfree (rtx
, int, int);
282 static int find_conditional_protection (rtx
, int);
283 static int is_conditionally_protected (rtx
, int, int);
284 static int is_prisky (rtx
, int, int);
285 static int is_exception_free (rtx
, int, int);
287 static bool sets_likely_spilled (rtx
);
288 static void sets_likely_spilled_1 (rtx
, rtx
, void *);
289 static void add_branch_dependences (rtx
, rtx
);
290 static void compute_block_backward_dependences (int);
291 void debug_dependencies (void);
293 static void init_regions (void);
294 static void schedule_region (int);
295 static rtx
concat_INSN_LIST (rtx
, rtx
);
296 static void concat_insn_mem_list (rtx
, rtx
, rtx
*, rtx
*);
297 static void propagate_deps (int, struct deps
*);
298 static void free_pending_lists (void);
300 /* Functions for construction of the control flow graph. */
302 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
304 We decide not to build the control flow graph if there is possibly more
305 than one entry to the function, if computed branches exist, if we
306 have nonlocal gotos, or if we have an unreachable loop. */
309 is_cfg_nonregular (void)
314 /* If we have a label that could be the target of a nonlocal goto, then
315 the cfg is not well structured. */
316 if (nonlocal_goto_handler_labels
)
319 /* If we have any forced labels, then the cfg is not well structured. */
323 /* If we have exception handlers, then we consider the cfg not well
324 structured. ?!? We should be able to handle this now that flow.c
325 computes an accurate cfg for EH. */
326 if (current_function_has_exception_handlers ())
329 /* If we have non-jumping insns which refer to labels, then we consider
330 the cfg not well structured. */
332 FOR_BB_INSNS (b
, insn
)
334 /* Check for labels referred by non-jump insns. */
335 if (NONJUMP_INSN_P (insn
) || CALL_P (insn
))
337 rtx note
= find_reg_note (insn
, REG_LABEL
, NULL_RTX
);
339 && ! (JUMP_P (NEXT_INSN (insn
))
340 && find_reg_note (NEXT_INSN (insn
), REG_LABEL
,
344 /* If this function has a computed jump, then we consider the cfg
345 not well structured. */
346 else if (JUMP_P (insn
) && computed_jump_p (insn
))
350 /* Unreachable loops with more than one basic block are detected
351 during the DFS traversal in find_rgns.
353 Unreachable loops with a single block are detected here. This
354 test is redundant with the one in find_rgns, but it's much
355 cheaper to go ahead and catch the trivial case here. */
358 if (EDGE_COUNT (b
->preds
) == 0
359 || (single_pred_p (b
)
360 && single_pred (b
) == b
))
364 /* All the tests passed. Consider the cfg well structured. */
368 /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */
371 extract_edgelst (sbitmap set
, edgelst
*el
)
374 sbitmap_iterator sbi
;
376 /* edgelst table space is reused in each call to extract_edgelst. */
379 el
->first_member
= &edgelst_table
[edgelst_last
];
382 /* Iterate over each word in the bitset. */
383 EXECUTE_IF_SET_IN_SBITMAP (set
, 0, i
, sbi
)
385 edgelst_table
[edgelst_last
++] = rgn_edges
[i
];
390 /* Functions for the construction of regions. */
392 /* Print the regions, for debugging purposes. Callable from debugger. */
399 fprintf (sched_dump
, "\n;; ------------ REGIONS ----------\n\n");
400 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
402 fprintf (sched_dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
403 rgn_table
[rgn
].rgn_nr_blocks
);
404 fprintf (sched_dump
, ";;\tbb/block: ");
406 /* We don't have ebb_head initialized yet, so we can't use
408 current_blocks
= RGN_BLOCKS (rgn
);
410 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
411 fprintf (sched_dump
, " %d/%d ", bb
, rgn_bb_table
[current_blocks
+ bb
]);
413 fprintf (sched_dump
, "\n\n");
417 /* Build a single block region for each basic block in the function.
418 This allows for using the same code for interblock and basic block
422 find_single_block_region (void)
430 rgn_bb_table
[nr_regions
] = bb
->index
;
431 RGN_NR_BLOCKS (nr_regions
) = 1;
432 RGN_BLOCKS (nr_regions
) = nr_regions
;
433 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
434 RGN_HAS_REAL_EBB (nr_regions
) = 0;
435 CONTAINING_RGN (bb
->index
) = nr_regions
;
436 BLOCK_TO_BB (bb
->index
) = 0;
441 /* Update number of blocks and the estimate for number of insns
442 in the region. Return true if the region is "too large" for interblock
443 scheduling (compile time considerations). */
446 too_large (int block
, int *num_bbs
, int *num_insns
)
449 (*num_insns
) += (INSN_LUID (BB_END (BASIC_BLOCK (block
)))
450 - INSN_LUID (BB_HEAD (BASIC_BLOCK (block
))));
452 return ((*num_bbs
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS
))
453 || (*num_insns
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS
)));
456 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
457 is still an inner loop. Put in max_hdr[blk] the header of the most inner
458 loop containing blk. */
459 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
461 if (max_hdr[blk] == -1) \
462 max_hdr[blk] = hdr; \
463 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
464 RESET_BIT (inner, hdr); \
465 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
467 RESET_BIT (inner,max_hdr[blk]); \
468 max_hdr[blk] = hdr; \
472 /* Find regions for interblock scheduling.
474 A region for scheduling can be:
476 * A loop-free procedure, or
478 * A reducible inner loop, or
480 * A basic block not contained in any other region.
482 ?!? In theory we could build other regions based on extended basic
483 blocks or reverse extended basic blocks. Is it worth the trouble?
485 Loop blocks that form a region are put into the region's block list
486 in topological order.
488 This procedure stores its results into the following global (ick) variables
496 We use dominator relationships to avoid making regions out of non-reducible
499 This procedure needs to be converted to work on pred/succ lists instead
500 of edge tables. That would simplify it somewhat. */
505 int *max_hdr
, *dfs_nr
, *degree
;
507 int node
, child
, loop_head
, i
, head
, tail
;
508 int count
= 0, sp
, idx
= 0;
509 edge_iterator current_edge
;
510 edge_iterator
*stack
;
511 int num_bbs
, num_insns
, unreachable
;
512 int too_large_failure
;
515 /* Note if a block is a natural loop header. */
518 /* Note if a block is a natural inner loop header. */
521 /* Note if a block is in the block queue. */
524 /* Note if a block is in the block queue. */
527 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
528 and a mapping from block to its loop header (if the block is contained
531 Store results in HEADER, INNER, and MAX_HDR respectively, these will
532 be used as inputs to the second traversal.
534 STACK, SP and DFS_NR are only used during the first traversal. */
536 /* Allocate and initialize variables for the first traversal. */
537 max_hdr
= XNEWVEC (int, last_basic_block
);
538 dfs_nr
= XCNEWVEC (int, last_basic_block
);
539 stack
= XNEWVEC (edge_iterator
, n_edges
);
541 inner
= sbitmap_alloc (last_basic_block
);
542 sbitmap_ones (inner
);
544 header
= sbitmap_alloc (last_basic_block
);
545 sbitmap_zero (header
);
547 in_queue
= sbitmap_alloc (last_basic_block
);
548 sbitmap_zero (in_queue
);
550 in_stack
= sbitmap_alloc (last_basic_block
);
551 sbitmap_zero (in_stack
);
553 for (i
= 0; i
< last_basic_block
; i
++)
556 #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
557 #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
559 /* DFS traversal to find inner loops in the cfg. */
561 current_edge
= ei_start (single_succ (ENTRY_BLOCK_PTR
)->succs
);
566 if (EDGE_PASSED (current_edge
))
568 /* We have reached a leaf node or a node that was already
569 processed. Pop edges off the stack until we find
570 an edge that has not yet been processed. */
571 while (sp
>= 0 && EDGE_PASSED (current_edge
))
573 /* Pop entry off the stack. */
574 current_edge
= stack
[sp
--];
575 node
= ei_edge (current_edge
)->src
->index
;
576 gcc_assert (node
!= ENTRY_BLOCK
);
577 child
= ei_edge (current_edge
)->dest
->index
;
578 gcc_assert (child
!= EXIT_BLOCK
);
579 RESET_BIT (in_stack
, child
);
580 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
581 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
582 ei_next (¤t_edge
);
585 /* See if have finished the DFS tree traversal. */
586 if (sp
< 0 && EDGE_PASSED (current_edge
))
589 /* Nope, continue the traversal with the popped node. */
593 /* Process a node. */
594 node
= ei_edge (current_edge
)->src
->index
;
595 gcc_assert (node
!= ENTRY_BLOCK
);
596 SET_BIT (in_stack
, node
);
597 dfs_nr
[node
] = ++count
;
599 /* We don't traverse to the exit block. */
600 child
= ei_edge (current_edge
)->dest
->index
;
601 if (child
== EXIT_BLOCK
)
603 SET_EDGE_PASSED (current_edge
);
604 ei_next (¤t_edge
);
608 /* If the successor is in the stack, then we've found a loop.
609 Mark the loop, if it is not a natural loop, then it will
610 be rejected during the second traversal. */
611 if (TEST_BIT (in_stack
, child
))
614 SET_BIT (header
, child
);
615 UPDATE_LOOP_RELATIONS (node
, child
);
616 SET_EDGE_PASSED (current_edge
);
617 ei_next (¤t_edge
);
621 /* If the child was already visited, then there is no need to visit
622 it again. Just update the loop relationships and restart
626 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
627 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
628 SET_EDGE_PASSED (current_edge
);
629 ei_next (¤t_edge
);
633 /* Push an entry on the stack and continue DFS traversal. */
634 stack
[++sp
] = current_edge
;
635 SET_EDGE_PASSED (current_edge
);
636 current_edge
= ei_start (ei_edge (current_edge
)->dest
->succs
);
639 /* Reset ->aux field used by EDGE_PASSED. */
644 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
649 /* Another check for unreachable blocks. The earlier test in
650 is_cfg_nonregular only finds unreachable blocks that do not
653 The DFS traversal will mark every block that is reachable from
654 the entry node by placing a nonzero value in dfs_nr. Thus if
655 dfs_nr is zero for any block, then it must be unreachable. */
658 if (dfs_nr
[bb
->index
] == 0)
664 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
665 to hold degree counts. */
669 degree
[bb
->index
] = EDGE_COUNT (bb
->preds
);
671 /* Do not perform region scheduling if there are any unreachable
675 int *queue
, *degree1
= NULL
;
676 /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
677 there basic blocks, which are forced to be region heads.
678 This is done to try to assemble few smaller regions
679 from a too_large region. */
680 sbitmap extended_rgn_header
= NULL
;
681 bool extend_regions_p
;
686 /* Second traversal:find reducible inner loops and topologically sort
687 block of each region. */
689 queue
= XNEWVEC (int, n_basic_blocks
);
691 extend_regions_p
= PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS
) > 0;
692 if (extend_regions_p
)
694 degree1
= xmalloc (last_basic_block
* sizeof (int));
695 extended_rgn_header
= sbitmap_alloc (last_basic_block
);
696 sbitmap_zero (extended_rgn_header
);
699 /* Find blocks which are inner loop headers. We still have non-reducible
700 loops to consider at this point. */
703 if (TEST_BIT (header
, bb
->index
) && TEST_BIT (inner
, bb
->index
))
709 /* Now check that the loop is reducible. We do this separate
710 from finding inner loops so that we do not find a reducible
711 loop which contains an inner non-reducible loop.
713 A simple way to find reducible/natural loops is to verify
714 that each block in the loop is dominated by the loop
717 If there exists a block that is not dominated by the loop
718 header, then the block is reachable from outside the loop
719 and thus the loop is not a natural loop. */
722 /* First identify blocks in the loop, except for the loop
724 if (bb
->index
== max_hdr
[jbb
->index
] && bb
!= jbb
)
726 /* Now verify that the block is dominated by the loop
728 if (!dominated_by_p (CDI_DOMINATORS
, jbb
, bb
))
733 /* If we exited the loop early, then I is the header of
734 a non-reducible loop and we should quit processing it
736 if (jbb
!= EXIT_BLOCK_PTR
)
739 /* I is a header of an inner loop, or block 0 in a subroutine
740 with no loops at all. */
742 too_large_failure
= 0;
743 loop_head
= max_hdr
[bb
->index
];
745 if (extend_regions_p
)
746 /* We save degree in case when we meet a too_large region
747 and cancel it. We need a correct degree later when
748 calling extend_rgns. */
749 memcpy (degree1
, degree
, last_basic_block
* sizeof (int));
751 /* Decrease degree of all I's successors for topological
753 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
754 if (e
->dest
!= EXIT_BLOCK_PTR
)
755 --degree
[e
->dest
->index
];
757 /* Estimate # insns, and count # blocks in the region. */
759 num_insns
= (INSN_LUID (BB_END (bb
))
760 - INSN_LUID (BB_HEAD (bb
)));
762 /* Find all loop latches (blocks with back edges to the loop
763 header) or all the leaf blocks in the cfg has no loops.
765 Place those blocks into the queue. */
769 /* Leaf nodes have only a single successor which must
771 if (single_succ_p (jbb
)
772 && single_succ (jbb
) == EXIT_BLOCK_PTR
)
774 queue
[++tail
] = jbb
->index
;
775 SET_BIT (in_queue
, jbb
->index
);
777 if (too_large (jbb
->index
, &num_bbs
, &num_insns
))
779 too_large_failure
= 1;
788 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
790 if (e
->src
== ENTRY_BLOCK_PTR
)
793 node
= e
->src
->index
;
795 if (max_hdr
[node
] == loop_head
&& node
!= bb
->index
)
797 /* This is a loop latch. */
798 queue
[++tail
] = node
;
799 SET_BIT (in_queue
, node
);
801 if (too_large (node
, &num_bbs
, &num_insns
))
803 too_large_failure
= 1;
810 /* Now add all the blocks in the loop to the queue.
812 We know the loop is a natural loop; however the algorithm
813 above will not always mark certain blocks as being in the
821 The algorithm in the DFS traversal may not mark B & D as part
822 of the loop (i.e. they will not have max_hdr set to A).
824 We know they can not be loop latches (else they would have
825 had max_hdr set since they'd have a backedge to a dominator
826 block). So we don't need them on the initial queue.
828 We know they are part of the loop because they are dominated
829 by the loop header and can be reached by a backwards walk of
830 the edges starting with nodes on the initial queue.
832 It is safe and desirable to include those nodes in the
833 loop/scheduling region. To do so we would need to decrease
834 the degree of a node if it is the target of a backedge
835 within the loop itself as the node is placed in the queue.
837 We do not do this because I'm not sure that the actual
838 scheduling code will properly handle this case. ?!? */
840 while (head
< tail
&& !too_large_failure
)
843 child
= queue
[++head
];
845 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (child
)->preds
)
847 node
= e
->src
->index
;
849 /* See discussion above about nodes not marked as in
850 this loop during the initial DFS traversal. */
851 if (e
->src
== ENTRY_BLOCK_PTR
852 || max_hdr
[node
] != loop_head
)
857 else if (!TEST_BIT (in_queue
, node
) && node
!= bb
->index
)
859 queue
[++tail
] = node
;
860 SET_BIT (in_queue
, node
);
862 if (too_large (node
, &num_bbs
, &num_insns
))
864 too_large_failure
= 1;
871 if (tail
>= 0 && !too_large_failure
)
873 /* Place the loop header into list of region blocks. */
874 degree
[bb
->index
] = -1;
875 rgn_bb_table
[idx
] = bb
->index
;
876 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
877 RGN_BLOCKS (nr_regions
) = idx
++;
878 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
879 RGN_HAS_REAL_EBB (nr_regions
) = 0;
880 CONTAINING_RGN (bb
->index
) = nr_regions
;
881 BLOCK_TO_BB (bb
->index
) = count
= 0;
883 /* Remove blocks from queue[] when their in degree
884 becomes zero. Repeat until no blocks are left on the
885 list. This produces a topological list of blocks in
892 if (degree
[child
] == 0)
897 rgn_bb_table
[idx
++] = child
;
898 BLOCK_TO_BB (child
) = ++count
;
899 CONTAINING_RGN (child
) = nr_regions
;
900 queue
[head
] = queue
[tail
--];
902 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (child
)->succs
)
903 if (e
->dest
!= EXIT_BLOCK_PTR
)
904 --degree
[e
->dest
->index
];
911 else if (extend_regions_p
)
913 /* Restore DEGREE. */
919 /* And force successors of BB to be region heads.
920 This may provide several smaller regions instead
921 of one too_large region. */
922 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
923 if (e
->dest
!= EXIT_BLOCK_PTR
)
924 SET_BIT (extended_rgn_header
, e
->dest
->index
);
930 if (extend_regions_p
)
934 sbitmap_a_or_b (header
, header
, extended_rgn_header
);
935 sbitmap_free (extended_rgn_header
);
937 extend_rgns (degree
, &idx
, header
, max_hdr
);
941 /* Any block that did not end up in a region is placed into a region
944 if (degree
[bb
->index
] >= 0)
946 rgn_bb_table
[idx
] = bb
->index
;
947 RGN_NR_BLOCKS (nr_regions
) = 1;
948 RGN_BLOCKS (nr_regions
) = idx
++;
949 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
950 RGN_HAS_REAL_EBB (nr_regions
) = 0;
951 CONTAINING_RGN (bb
->index
) = nr_regions
++;
952 BLOCK_TO_BB (bb
->index
) = 0;
958 sbitmap_free (header
);
959 sbitmap_free (inner
);
960 sbitmap_free (in_queue
);
961 sbitmap_free (in_stack
);
964 static int gather_region_statistics (int **);
965 static void print_region_statistics (int *, int, int *, int);
967 /* Calculate the histogram that shows the number of regions having the
968 given number of basic blocks, and store it in the RSP array. Return
969 the size of this array. */
971 gather_region_statistics (int **rsp
)
973 int i
, *a
= 0, a_sz
= 0;
975 /* a[i] is the number of regions that have (i + 1) basic blocks. */
976 for (i
= 0; i
< nr_regions
; i
++)
978 int nr_blocks
= RGN_NR_BLOCKS (i
);
980 gcc_assert (nr_blocks
>= 1);
982 if (nr_blocks
> a_sz
)
984 a
= xrealloc (a
, nr_blocks
* sizeof (*a
));
987 while (a_sz
!= nr_blocks
);
997 /* Print regions statistics. S1 and S2 denote the data before and after
998 calling extend_rgns, respectively. */
1000 print_region_statistics (int *s1
, int s1_sz
, int *s2
, int s2_sz
)
1004 /* We iterate until s2_sz because extend_rgns does not decrease
1005 the maximal region size. */
1006 for (i
= 1; i
< s2_sz
; i
++)
1020 fprintf (sched_dump
, ";; Region extension statistics: size %d: " \
1021 "was %d + %d more\n", i
+ 1, n1
, n2
- n1
);
1026 DEGREE - Array of incoming edge count, considering only
1027 the edges, that don't have their sources in formed regions yet.
1028 IDXP - pointer to the next available index in rgn_bb_table.
1029 HEADER - set of all region heads.
1030 LOOP_HDR - mapping from block to the containing loop
1031 (two blocks can reside within one region if they have
1032 the same loop header). */
1034 extend_rgns (int *degree
, int *idxp
, sbitmap header
, int *loop_hdr
)
1036 int *order
, i
, rescan
= 0, idx
= *idxp
, iter
= 0, max_iter
, *max_hdr
;
1037 int nblocks
= n_basic_blocks
- NUM_FIXED_BLOCKS
;
1039 max_iter
= PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS
);
1041 max_hdr
= xmalloc (last_basic_block
* sizeof (*max_hdr
));
1043 order
= xmalloc (last_basic_block
* sizeof (*order
));
1044 post_order_compute (order
, false);
1046 for (i
= nblocks
- 1; i
>= 0; i
--)
1049 if (degree
[bbn
] >= 0)
1055 /* This block already was processed in find_rgns. */
1059 /* The idea is to topologically walk through CFG in top-down order.
1060 During the traversal, if all the predecessors of a node are
1061 marked to be in the same region (they all have the same max_hdr),
1062 then current node is also marked to be a part of that region.
1063 Otherwise the node starts its own region.
1064 CFG should be traversed until no further changes are made. On each
1065 iteration the set of the region heads is extended (the set of those
1066 blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
1067 set of all basic blocks, thus the algorithm is guaranteed to terminate. */
1069 while (rescan
&& iter
< max_iter
)
1073 for (i
= nblocks
- 1; i
>= 0; i
--)
1079 if (max_hdr
[bbn
] != -1 && !TEST_BIT (header
, bbn
))
1083 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (bbn
)->preds
)
1085 int predn
= e
->src
->index
;
1087 if (predn
!= ENTRY_BLOCK
1088 /* If pred wasn't processed in find_rgns. */
1089 && max_hdr
[predn
] != -1
1090 /* And pred and bb reside in the same loop.
1091 (Or out of any loop). */
1092 && loop_hdr
[bbn
] == loop_hdr
[predn
])
1095 /* Then bb extends the containing region of pred. */
1096 hdr
= max_hdr
[predn
];
1097 else if (hdr
!= max_hdr
[predn
])
1098 /* Too bad, there are at least two predecessors
1099 that reside in different regions. Thus, BB should
1100 begin its own region. */
1107 /* BB starts its own region. */
1116 /* If BB start its own region,
1117 update set of headers with BB. */
1118 SET_BIT (header
, bbn
);
1122 gcc_assert (hdr
!= -1);
1131 /* Statistics were gathered on the SPEC2000 package of tests with
1132 mainline weekly snapshot gcc-4.1-20051015 on ia64.
1134 Statistics for SPECint:
1135 1 iteration : 1751 cases (38.7%)
1136 2 iterations: 2770 cases (61.3%)
1137 Blocks wrapped in regions by find_rgns without extension: 18295 blocks
1138 Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
1139 (We don't count single block regions here).
1141 Statistics for SPECfp:
1142 1 iteration : 621 cases (35.9%)
1143 2 iterations: 1110 cases (64.1%)
1144 Blocks wrapped in regions by find_rgns without extension: 6476 blocks
1145 Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
1146 (We don't count single block regions here).
1148 By default we do at most 2 iterations.
1149 This can be overridden with max-sched-extend-regions-iters parameter:
1150 0 - disable region extension,
1151 N > 0 - do at most N iterations. */
1153 if (sched_verbose
&& iter
!= 0)
1154 fprintf (sched_dump
, ";; Region extension iterations: %d%s\n", iter
,
1155 rescan
? "... failed" : "");
1157 if (!rescan
&& iter
!= 0)
1159 int *s1
= NULL
, s1_sz
= 0;
1161 /* Save the old statistics for later printout. */
1162 if (sched_verbose
>= 6)
1163 s1_sz
= gather_region_statistics (&s1
);
1165 /* We have succeeded. Now assemble the regions. */
1166 for (i
= nblocks
- 1; i
>= 0; i
--)
1170 if (max_hdr
[bbn
] == bbn
)
1171 /* BBN is a region head. */
1175 int num_bbs
= 0, j
, num_insns
= 0, large
;
1177 large
= too_large (bbn
, &num_bbs
, &num_insns
);
1180 rgn_bb_table
[idx
] = bbn
;
1181 RGN_BLOCKS (nr_regions
) = idx
++;
1182 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1183 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1184 CONTAINING_RGN (bbn
) = nr_regions
;
1185 BLOCK_TO_BB (bbn
) = 0;
1187 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (bbn
)->succs
)
1188 if (e
->dest
!= EXIT_BLOCK_PTR
)
1189 degree
[e
->dest
->index
]--;
1192 /* Here we check whether the region is too_large. */
1193 for (j
= i
- 1; j
>= 0; j
--)
1195 int succn
= order
[j
];
1196 if (max_hdr
[succn
] == bbn
)
1198 if ((large
= too_large (succn
, &num_bbs
, &num_insns
)))
1204 /* If the region is too_large, then wrap every block of
1205 the region into single block region.
1206 Here we wrap region head only. Other blocks are
1207 processed in the below cycle. */
1209 RGN_NR_BLOCKS (nr_regions
) = 1;
1215 for (j
= i
- 1; j
>= 0; j
--)
1217 int succn
= order
[j
];
1219 if (max_hdr
[succn
] == bbn
)
1220 /* This cycle iterates over all basic blocks, that
1221 are supposed to be in the region with head BBN,
1222 and wraps them into that region (or in single
1225 gcc_assert (degree
[succn
] == 0);
1228 rgn_bb_table
[idx
] = succn
;
1229 BLOCK_TO_BB (succn
) = large
? 0 : num_bbs
++;
1230 CONTAINING_RGN (succn
) = nr_regions
;
1233 /* Wrap SUCCN into single block region. */
1235 RGN_BLOCKS (nr_regions
) = idx
;
1236 RGN_NR_BLOCKS (nr_regions
) = 1;
1237 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
1238 RGN_HAS_REAL_EBB (nr_regions
) = 0;
1244 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (succn
)->succs
)
1245 if (e
->dest
!= EXIT_BLOCK_PTR
)
1246 degree
[e
->dest
->index
]--;
1252 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1258 if (sched_verbose
>= 6)
1262 /* Get the new statistics and print the comparison with the
1263 one before calling this function. */
1264 s2_sz
= gather_region_statistics (&s2
);
1265 print_region_statistics (s1
, s1_sz
, s2
, s2_sz
);
1277 /* Functions for regions scheduling information. */
1279 /* Compute dominators, probability, and potential-split-edges of bb.
1280 Assume that these values were already computed for bb's predecessors. */
1283 compute_dom_prob_ps (int bb
)
1285 edge_iterator in_ei
;
1288 /* We shouldn't have any real ebbs yet. */
1289 gcc_assert (ebb_head
[bb
] == bb
+ current_blocks
);
1291 if (IS_RGN_ENTRY (bb
))
1293 SET_BIT (dom
[bb
], 0);
1294 prob
[bb
] = REG_BR_PROB_BASE
;
1300 /* Initialize dom[bb] to '111..1'. */
1301 sbitmap_ones (dom
[bb
]);
1303 FOR_EACH_EDGE (in_edge
, in_ei
, BASIC_BLOCK (BB_TO_BLOCK (bb
))->preds
)
1307 edge_iterator out_ei
;
1309 if (in_edge
->src
== ENTRY_BLOCK_PTR
)
1312 pred_bb
= BLOCK_TO_BB (in_edge
->src
->index
);
1313 sbitmap_a_and_b (dom
[bb
], dom
[bb
], dom
[pred_bb
]);
1314 sbitmap_a_or_b (ancestor_edges
[bb
],
1315 ancestor_edges
[bb
], ancestor_edges
[pred_bb
]);
1317 SET_BIT (ancestor_edges
[bb
], EDGE_TO_BIT (in_edge
));
1319 sbitmap_a_or_b (pot_split
[bb
], pot_split
[bb
], pot_split
[pred_bb
]);
1321 FOR_EACH_EDGE (out_edge
, out_ei
, in_edge
->src
->succs
)
1322 SET_BIT (pot_split
[bb
], EDGE_TO_BIT (out_edge
));
1324 prob
[bb
] += ((prob
[pred_bb
] * in_edge
->probability
) / REG_BR_PROB_BASE
);
1327 SET_BIT (dom
[bb
], bb
);
1328 sbitmap_difference (pot_split
[bb
], pot_split
[bb
], ancestor_edges
[bb
]);
1330 if (sched_verbose
>= 2)
1331 fprintf (sched_dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
),
1332 (100 * prob
[bb
]) / REG_BR_PROB_BASE
);
1335 /* Functions for target info. */
1337 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1338 Note that bb_trg dominates bb_src. */
1341 split_edges (int bb_src
, int bb_trg
, edgelst
*bl
)
1343 sbitmap src
= sbitmap_alloc (pot_split
[bb_src
]->n_bits
);
1344 sbitmap_copy (src
, pot_split
[bb_src
]);
1346 sbitmap_difference (src
, src
, pot_split
[bb_trg
]);
1347 extract_edgelst (src
, bl
);
1351 /* Find the valid candidate-source-blocks for the target block TRG, compute
1352 their probability, and check if they are speculative or not.
1353 For speculative sources, compute their update-blocks and split-blocks. */
1356 compute_trg_info (int trg
)
1360 int i
, j
, k
, update_idx
;
1366 /* Define some of the fields for the target bb as well. */
1367 sp
= candidate_table
+ trg
;
1369 sp
->is_speculative
= 0;
1370 sp
->src_prob
= REG_BR_PROB_BASE
;
1372 visited
= sbitmap_alloc (last_basic_block
);
1374 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1376 sp
= candidate_table
+ i
;
1378 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1381 int tf
= prob
[trg
], cf
= prob
[i
];
1383 /* In CFGs with low probability edges TF can possibly be zero. */
1384 sp
->src_prob
= (tf
? ((cf
* REG_BR_PROB_BASE
) / tf
) : 0);
1385 sp
->is_valid
= (sp
->src_prob
>= min_spec_prob
);
1390 split_edges (i
, trg
, &el
);
1391 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1392 if (sp
->is_speculative
&& !flag_schedule_speculative
)
1398 /* Compute split blocks and store them in bblst_table.
1399 The TO block of every split edge is a split block. */
1400 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
1401 sp
->split_bbs
.nr_members
= el
.nr_members
;
1402 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
1403 bblst_table
[bblst_last
] = el
.first_member
[j
]->dest
;
1404 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
1406 /* Compute update blocks and store them in bblst_table.
1407 For every split edge, look at the FROM block, and check
1408 all out edges. For each out edge that is not a split edge,
1409 add the TO block to the update block list. This list can end
1410 up with a lot of duplicates. We need to weed them out to avoid
1411 overrunning the end of the bblst_table. */
1414 sbitmap_zero (visited
);
1415 for (j
= 0; j
< el
.nr_members
; j
++)
1417 block
= el
.first_member
[j
]->src
;
1418 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1420 if (!TEST_BIT (visited
, e
->dest
->index
))
1422 for (k
= 0; k
< el
.nr_members
; k
++)
1423 if (e
== el
.first_member
[k
])
1426 if (k
>= el
.nr_members
)
1428 bblst_table
[bblst_last
++] = e
->dest
;
1429 SET_BIT (visited
, e
->dest
->index
);
1435 sp
->update_bbs
.nr_members
= update_idx
;
1437 /* Make sure we didn't overrun the end of bblst_table. */
1438 gcc_assert (bblst_last
<= bblst_size
);
1442 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
1444 sp
->is_speculative
= 0;
1449 sbitmap_free (visited
);
1452 /* Print candidates info, for debugging purposes. Callable from debugger. */
1455 debug_candidate (int i
)
1457 if (!candidate_table
[i
].is_valid
)
1460 if (candidate_table
[i
].is_speculative
)
1463 fprintf (sched_dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
1465 fprintf (sched_dump
, "split path: ");
1466 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
1468 int b
= candidate_table
[i
].split_bbs
.first_member
[j
]->index
;
1470 fprintf (sched_dump
, " %d ", b
);
1472 fprintf (sched_dump
, "\n");
1474 fprintf (sched_dump
, "update path: ");
1475 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
1477 int b
= candidate_table
[i
].update_bbs
.first_member
[j
]->index
;
1479 fprintf (sched_dump
, " %d ", b
);
1481 fprintf (sched_dump
, "\n");
1485 fprintf (sched_dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
1489 /* Print candidates info, for debugging purposes. Callable from debugger. */
1492 debug_candidates (int trg
)
1496 fprintf (sched_dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
1497 BB_TO_BLOCK (trg
), trg
);
1498 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1499 debug_candidate (i
);
1502 /* Functions for speculative scheduling. */
1504 /* Return 0 if x is a set of a register alive in the beginning of one
1505 of the split-blocks of src, otherwise return 1. */
1508 check_live_1 (int src
, rtx x
)
1512 rtx reg
= SET_DEST (x
);
1517 while (GET_CODE (reg
) == SUBREG
1518 || GET_CODE (reg
) == ZERO_EXTRACT
1519 || GET_CODE (reg
) == STRICT_LOW_PART
)
1520 reg
= XEXP (reg
, 0);
1522 if (GET_CODE (reg
) == PARALLEL
)
1526 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1527 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1528 if (check_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0)))
1537 regno
= REGNO (reg
);
1539 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
1541 /* Global registers are assumed live. */
1546 if (regno
< FIRST_PSEUDO_REGISTER
)
1548 /* Check for hard registers. */
1549 int j
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1552 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1554 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1556 /* We can have split blocks, that were recently generated.
1557 such blocks are always outside current region. */
1558 gcc_assert (glat_start
[b
->index
]
1559 || CONTAINING_RGN (b
->index
)
1560 != CONTAINING_RGN (BB_TO_BLOCK (src
)));
1561 if (!glat_start
[b
->index
]
1562 || REGNO_REG_SET_P (glat_start
[b
->index
],
1572 /* Check for pseudo registers. */
1573 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1575 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1577 gcc_assert (glat_start
[b
->index
]
1578 || CONTAINING_RGN (b
->index
)
1579 != CONTAINING_RGN (BB_TO_BLOCK (src
)));
1580 if (!glat_start
[b
->index
]
1581 || REGNO_REG_SET_P (glat_start
[b
->index
], regno
))
1592 /* If x is a set of a register R, mark that R is alive in the beginning
1593 of every update-block of src. */
1596 update_live_1 (int src
, rtx x
)
1600 rtx reg
= SET_DEST (x
);
1605 while (GET_CODE (reg
) == SUBREG
1606 || GET_CODE (reg
) == ZERO_EXTRACT
1607 || GET_CODE (reg
) == STRICT_LOW_PART
)
1608 reg
= XEXP (reg
, 0);
1610 if (GET_CODE (reg
) == PARALLEL
)
1614 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1615 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1616 update_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0));
1624 /* Global registers are always live, so the code below does not apply
1627 regno
= REGNO (reg
);
1629 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
1631 if (regno
< FIRST_PSEUDO_REGISTER
)
1633 int j
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1636 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
1638 basic_block b
= candidate_table
[src
].update_bbs
.first_member
[i
];
1640 SET_REGNO_REG_SET (glat_start
[b
->index
], regno
+ j
);
1646 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
1648 basic_block b
= candidate_table
[src
].update_bbs
.first_member
[i
];
1650 SET_REGNO_REG_SET (glat_start
[b
->index
], regno
);
1656 /* Return 1 if insn can be speculatively moved from block src to trg,
1657 otherwise return 0. Called before first insertion of insn to
1658 ready-list or before the scheduling. */
1661 check_live (rtx insn
, int src
)
1663 /* Find the registers set by instruction. */
1664 if (GET_CODE (PATTERN (insn
)) == SET
1665 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1666 return check_live_1 (src
, PATTERN (insn
));
1667 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1670 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1671 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1672 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1673 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
1682 /* Update the live registers info after insn was moved speculatively from
1683 block src to trg. */
1686 update_live (rtx insn
, int src
)
1688 /* Find the registers set by instruction. */
1689 if (GET_CODE (PATTERN (insn
)) == SET
1690 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1691 update_live_1 (src
, PATTERN (insn
));
1692 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1695 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1696 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1697 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1698 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
1702 /* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1703 #define IS_REACHABLE(bb_from, bb_to) \
1705 || IS_RGN_ENTRY (bb_from) \
1706 || (TEST_BIT (ancestor_edges[bb_to], \
1707 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK (BB_TO_BLOCK (bb_from)))))))
1709 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1712 set_spec_fed (rtx load_insn
)
1716 FOR_EACH_DEP_LINK (link
, INSN_FORW_DEPS (load_insn
))
1717 if (DEP_LINK_KIND (link
) == REG_DEP_TRUE
)
1718 FED_BY_SPEC_LOAD (DEP_LINK_CON (link
)) = 1;
1721 /* On the path from the insn to load_insn_bb, find a conditional
1722 branch depending on insn, that guards the speculative load. */
1725 find_conditional_protection (rtx insn
, int load_insn_bb
)
1729 /* Iterate through DEF-USE forward dependences. */
1730 FOR_EACH_DEP_LINK (link
, INSN_FORW_DEPS (insn
))
1732 rtx next
= DEP_LINK_CON (link
);
1734 if ((CONTAINING_RGN (BLOCK_NUM (next
)) ==
1735 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
1736 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
1737 && load_insn_bb
!= INSN_BB (next
)
1738 && DEP_LINK_KIND (link
) == REG_DEP_TRUE
1740 || find_conditional_protection (next
, load_insn_bb
)))
1744 } /* find_conditional_protection */
1746 /* Returns 1 if the same insn1 that participates in the computation
1747 of load_insn's address is feeding a conditional branch that is
1748 guarding on load_insn. This is true if we find a the two DEF-USE
1750 insn1 -> ... -> conditional-branch
1751 insn1 -> ... -> load_insn,
1752 and if a flow path exist:
1753 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1754 and if insn1 is on the path
1755 region-entry -> ... -> bb_trg -> ... load_insn.
1757 Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
1758 Locate the branch by following INSN_FORW_DEPS from insn1. */
1761 is_conditionally_protected (rtx load_insn
, int bb_src
, int bb_trg
)
1765 FOR_EACH_DEP_LINK (link
, INSN_BACK_DEPS (load_insn
))
1767 rtx insn1
= DEP_LINK_PRO (link
);
1769 /* Must be a DEF-USE dependence upon non-branch. */
1770 if (DEP_LINK_KIND (link
) != REG_DEP_TRUE
1774 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1775 if (INSN_BB (insn1
) == bb_src
1776 || (CONTAINING_RGN (BLOCK_NUM (insn1
))
1777 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
1778 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
1779 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
1782 /* Now search for the conditional-branch. */
1783 if (find_conditional_protection (insn1
, bb_src
))
1786 /* Recursive step: search another insn1, "above" current insn1. */
1787 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
1790 /* The chain does not exist. */
1792 } /* is_conditionally_protected */
1794 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1795 load_insn can move speculatively from bb_src to bb_trg. All the
1796 following must hold:
1798 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1799 (2) load_insn and load1 have a def-use dependence upon
1800 the same insn 'insn1'.
1801 (3) either load2 is in bb_trg, or:
1802 - there's only one split-block, and
1803 - load1 is on the escape path, and
1805 From all these we can conclude that the two loads access memory
1806 addresses that differ at most by a constant, and hence if moving
1807 load_insn would cause an exception, it would have been caused by
1811 is_pfree (rtx load_insn
, int bb_src
, int bb_trg
)
1813 dep_link_t back_link
;
1814 candidate
*candp
= candidate_table
+ bb_src
;
1816 if (candp
->split_bbs
.nr_members
!= 1)
1817 /* Must have exactly one escape block. */
1820 FOR_EACH_DEP_LINK (back_link
, INSN_BACK_DEPS (load_insn
))
1822 rtx insn1
= DEP_LINK_PRO (back_link
);
1824 if (DEP_LINK_KIND (back_link
) == REG_DEP_TRUE
)
1826 /* Found a DEF-USE dependence (insn1, load_insn). */
1827 dep_link_t fore_link
;
1829 FOR_EACH_DEP_LINK (fore_link
, INSN_FORW_DEPS (insn1
))
1831 rtx insn2
= DEP_LINK_CON (fore_link
);
1833 if (DEP_LINK_KIND (fore_link
) == REG_DEP_TRUE
)
1835 /* Found a DEF-USE dependence (insn1, insn2). */
1836 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
1837 /* insn2 not guaranteed to be a 1 base reg load. */
1840 if (INSN_BB (insn2
) == bb_trg
)
1841 /* insn2 is the similar load, in the target block. */
1844 if (*(candp
->split_bbs
.first_member
) == BLOCK_FOR_INSN (insn2
))
1845 /* insn2 is a similar load, in a split-block. */
1852 /* Couldn't find a similar load. */
1856 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1857 a load moved speculatively, or if load_insn is protected by
1858 a compare on load_insn's address). */
1861 is_prisky (rtx load_insn
, int bb_src
, int bb_trg
)
1863 if (FED_BY_SPEC_LOAD (load_insn
))
1866 if (deps_list_empty_p (INSN_BACK_DEPS (load_insn
)))
1867 /* Dependence may 'hide' out of the region. */
1870 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
1876 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
1877 Return 1 if insn is exception-free (and the motion is valid)
1881 is_exception_free (rtx insn
, int bb_src
, int bb_trg
)
1883 int insn_class
= haifa_classify_insn (insn
);
1885 /* Handle non-load insns. */
1896 if (!flag_schedule_speculative_load
)
1898 IS_LOAD_INSN (insn
) = 1;
1905 case PFREE_CANDIDATE
:
1906 if (is_pfree (insn
, bb_src
, bb_trg
))
1908 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
1909 case PRISKY_CANDIDATE
:
1910 if (!flag_schedule_speculative_load_dangerous
1911 || is_prisky (insn
, bb_src
, bb_trg
))
1917 return flag_schedule_speculative_load_dangerous
;
1920 /* The number of insns from the current block scheduled so far. */
1921 static int sched_target_n_insns
;
1922 /* The number of insns from the current block to be scheduled in total. */
1923 static int target_n_insns
;
1924 /* The number of insns from the entire region scheduled so far. */
1925 static int sched_n_insns
;
1927 /* Implementations of the sched_info functions for region scheduling. */
1928 static void init_ready_list (void);
1929 static int can_schedule_ready_p (rtx
);
1930 static void begin_schedule_ready (rtx
, rtx
);
1931 static ds_t
new_ready (rtx
, ds_t
);
1932 static int schedule_more_p (void);
1933 static const char *rgn_print_insn (rtx
, int);
1934 static int rgn_rank (rtx
, rtx
);
1935 static int contributes_to_priority (rtx
, rtx
);
1936 static void compute_jump_reg_dependencies (rtx
, regset
, regset
, regset
);
1938 /* Functions for speculative scheduling. */
1939 static void add_remove_insn (rtx
, int);
1940 static void extend_regions (void);
1941 static void add_block1 (basic_block
, basic_block
);
1942 static void fix_recovery_cfg (int, int, int);
1943 static basic_block
advance_target_bb (basic_block
, rtx
);
1944 static void check_dead_notes1 (int, sbitmap
);
1945 #ifdef ENABLE_CHECKING
1946 static int region_head_or_leaf_p (basic_block
, int);
1949 /* Return nonzero if there are more insns that should be scheduled. */
1952 schedule_more_p (void)
1954 return sched_target_n_insns
< target_n_insns
;
1957 /* Add all insns that are initially ready to the ready list READY. Called
1958 once before scheduling a set of insns. */
1961 init_ready_list (void)
1963 rtx prev_head
= current_sched_info
->prev_head
;
1964 rtx next_tail
= current_sched_info
->next_tail
;
1969 sched_target_n_insns
= 0;
1972 /* Print debugging information. */
1973 if (sched_verbose
>= 5)
1974 debug_dependencies ();
1976 /* Prepare current target block info. */
1977 if (current_nr_blocks
> 1)
1979 candidate_table
= XNEWVEC (candidate
, current_nr_blocks
);
1982 /* bblst_table holds split blocks and update blocks for each block after
1983 the current one in the region. split blocks and update blocks are
1984 the TO blocks of region edges, so there can be at most rgn_nr_edges
1986 bblst_size
= (current_nr_blocks
- target_bb
) * rgn_nr_edges
;
1987 bblst_table
= XNEWVEC (basic_block
, bblst_size
);
1990 edgelst_table
= XNEWVEC (edge
, rgn_nr_edges
);
1992 compute_trg_info (target_bb
);
1995 /* Initialize ready list with all 'ready' insns in target block.
1996 Count number of insns in the target block being scheduled. */
1997 for (insn
= NEXT_INSN (prev_head
); insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2002 gcc_assert (!(TODO_SPEC (insn
) & BEGIN_CONTROL
));
2005 /* Add to ready list all 'ready' insns in valid source blocks.
2006 For speculative insns, check-live, exception-free, and
2008 for (bb_src
= target_bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
2009 if (IS_VALID (bb_src
))
2015 get_ebb_head_tail (EBB_FIRST_BB (bb_src
), EBB_LAST_BB (bb_src
),
2017 src_next_tail
= NEXT_INSN (tail
);
2020 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
2026 /* Called after taking INSN from the ready list. Returns nonzero if this
2027 insn can be scheduled, nonzero if we should silently discard it. */
2030 can_schedule_ready_p (rtx insn
)
2032 /* An interblock motion? */
2033 if (INSN_BB (insn
) != target_bb
2034 && IS_SPECULATIVE_INSN (insn
)
2035 && !check_live (insn
, INSN_BB (insn
)))
2041 /* Updates counter and other information. Split from can_schedule_ready_p ()
2042 because when we schedule insn speculatively then insn passed to
2043 can_schedule_ready_p () differs from the one passed to
2044 begin_schedule_ready (). */
2046 begin_schedule_ready (rtx insn
, rtx last ATTRIBUTE_UNUSED
)
2048 /* An interblock motion? */
2049 if (INSN_BB (insn
) != target_bb
)
2051 if (IS_SPECULATIVE_INSN (insn
))
2053 gcc_assert (check_live (insn
, INSN_BB (insn
)));
2055 update_live (insn
, INSN_BB (insn
));
2057 /* For speculative load, mark insns fed by it. */
2058 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
2059 set_spec_fed (insn
);
2067 /* In block motion. */
2068 sched_target_n_insns
++;
2073 /* Called after INSN has all its hard dependencies resolved and the speculation
2074 of type TS is enough to overcome them all.
2075 Return nonzero if it should be moved to the ready list or the queue, or zero
2076 if we should silently discard it. */
2078 new_ready (rtx next
, ds_t ts
)
2080 if (INSN_BB (next
) != target_bb
)
2082 int not_ex_free
= 0;
2084 /* For speculative insns, before inserting to ready/queue,
2085 check live, exception-free, and issue-delay. */
2086 if (!IS_VALID (INSN_BB (next
))
2088 || (IS_SPECULATIVE_INSN (next
)
2089 && ((recog_memoized (next
) >= 0
2090 && min_insn_conflict_delay (curr_state
, next
, next
)
2091 > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY
))
2092 || IS_SPECULATION_CHECK_P (next
)
2093 || !check_live (next
, INSN_BB (next
))
2094 || (not_ex_free
= !is_exception_free (next
, INSN_BB (next
),
2098 /* We are here because is_exception_free () == false.
2099 But we possibly can handle that with control speculation. */
2100 && current_sched_info
->flags
& DO_SPECULATION
)
2101 /* Here we got new control-speculative instruction. */
2102 ts
= set_dep_weak (ts
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
2104 ts
= (ts
& ~SPECULATIVE
) | HARD_DEP
;
2111 /* Return a string that contains the insn uid and optionally anything else
2112 necessary to identify this insn in an output. It's valid to use a
2113 static buffer for this. The ALIGNED parameter should cause the string
2114 to be formatted so that multiple output lines will line up nicely. */
2117 rgn_print_insn (rtx insn
, int aligned
)
2119 static char tmp
[80];
2122 sprintf (tmp
, "b%3d: i%4d", INSN_BB (insn
), INSN_UID (insn
));
2125 if (current_nr_blocks
> 1 && INSN_BB (insn
) != target_bb
)
2126 sprintf (tmp
, "%d/b%d", INSN_UID (insn
), INSN_BB (insn
));
2128 sprintf (tmp
, "%d", INSN_UID (insn
));
2133 /* Compare priority of two insns. Return a positive number if the second
2134 insn is to be preferred for scheduling, and a negative one if the first
2135 is to be preferred. Zero if they are equally good. */
2138 rgn_rank (rtx insn1
, rtx insn2
)
2140 /* Some comparison make sense in interblock scheduling only. */
2141 if (INSN_BB (insn1
) != INSN_BB (insn2
))
2143 int spec_val
, prob_val
;
2145 /* Prefer an inblock motion on an interblock motion. */
2146 if ((INSN_BB (insn2
) == target_bb
) && (INSN_BB (insn1
) != target_bb
))
2148 if ((INSN_BB (insn1
) == target_bb
) && (INSN_BB (insn2
) != target_bb
))
2151 /* Prefer a useful motion on a speculative one. */
2152 spec_val
= IS_SPECULATIVE_INSN (insn1
) - IS_SPECULATIVE_INSN (insn2
);
2156 /* Prefer a more probable (speculative) insn. */
2157 prob_val
= INSN_PROBABILITY (insn2
) - INSN_PROBABILITY (insn1
);
2164 /* NEXT is an instruction that depends on INSN (a backward dependence);
2165 return nonzero if we should include this dependence in priority
2169 contributes_to_priority (rtx next
, rtx insn
)
2171 /* NEXT and INSN reside in one ebb. */
2172 return BLOCK_TO_BB (BLOCK_NUM (next
)) == BLOCK_TO_BB (BLOCK_NUM (insn
));
2175 /* INSN is a JUMP_INSN, COND_SET is the set of registers that are
2176 conditionally set before INSN. Store the set of registers that
2177 must be considered as used by this jump in USED and that of
2178 registers that must be considered as set in SET. */
2181 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
2182 regset cond_exec ATTRIBUTE_UNUSED
,
2183 regset used ATTRIBUTE_UNUSED
,
2184 regset set ATTRIBUTE_UNUSED
)
2186 /* Nothing to do here, since we postprocess jumps in
2187 add_branch_dependences. */
2190 /* Used in schedule_insns to initialize current_sched_info for scheduling
2191 regions (or single basic blocks). */
2193 static struct sched_info region_sched_info
=
2196 can_schedule_ready_p
,
2201 contributes_to_priority
,
2202 compute_jump_reg_dependencies
,
2209 begin_schedule_ready
,
2213 #ifdef ENABLE_CHECKING
2214 region_head_or_leaf_p
,
2216 SCHED_RGN
| USE_GLAT
2217 #ifdef ENABLE_CHECKING
2222 /* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register. */
2225 sets_likely_spilled (rtx pat
)
2228 note_stores (pat
, sets_likely_spilled_1
, &ret
);
2233 sets_likely_spilled_1 (rtx x
, rtx pat
, void *data
)
2235 bool *ret
= (bool *) data
;
2237 if (GET_CODE (pat
) == SET
2239 && REGNO (x
) < FIRST_PSEUDO_REGISTER
2240 && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x
))))
2244 /* Add dependences so that branches are scheduled to run last in their
2248 add_branch_dependences (rtx head
, rtx tail
)
2252 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2253 that can throw exceptions, force them to remain in order at the end of
2254 the block by adding dependencies and giving the last a high priority.
2255 There may be notes present, and prev_head may also be a note.
2257 Branches must obviously remain at the end. Calls should remain at the
2258 end since moving them results in worse register allocation. Uses remain
2259 at the end to ensure proper register allocation.
2261 cc0 setters remain at the end because they can't be moved away from
2264 COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
2266 Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values)
2267 are not moved before reload because we can wind up with register
2268 allocation failures. */
2272 while (CALL_P (insn
)
2274 || (NONJUMP_INSN_P (insn
)
2275 && (GET_CODE (PATTERN (insn
)) == USE
2276 || GET_CODE (PATTERN (insn
)) == CLOBBER
2277 || can_throw_internal (insn
)
2279 || sets_cc0_p (PATTERN (insn
))
2281 || (!reload_completed
2282 && sets_likely_spilled (PATTERN (insn
)))))
2288 && (find_link_by_pro_in_deps_list (INSN_BACK_DEPS (last
), insn
)
2291 if (! sched_insns_conditions_mutex_p (last
, insn
))
2292 add_dependence (last
, insn
, REG_DEP_ANTI
);
2293 INSN_REF_COUNT (insn
)++;
2296 CANT_MOVE (insn
) = 1;
2301 /* Don't overrun the bounds of the basic block. */
2305 insn
= PREV_INSN (insn
);
2308 /* Make sure these insns are scheduled last in their block. */
2311 while (insn
!= head
)
2313 insn
= prev_nonnote_insn (insn
);
2315 if (INSN_REF_COUNT (insn
) != 0)
2318 if (! sched_insns_conditions_mutex_p (last
, insn
))
2319 add_dependence (last
, insn
, REG_DEP_ANTI
);
2320 INSN_REF_COUNT (insn
) = 1;
2323 #ifdef HAVE_conditional_execution
2324 /* Finally, if the block ends in a jump, and we are doing intra-block
2325 scheduling, make sure that the branch depends on any COND_EXEC insns
2326 inside the block to avoid moving the COND_EXECs past the branch insn.
2328 We only have to do this after reload, because (1) before reload there
2329 are no COND_EXEC insns, and (2) the region scheduler is an intra-block
2330 scheduler after reload.
2332 FIXME: We could in some cases move COND_EXEC insns past the branch if
2333 this scheduler would be a little smarter. Consider this code:
2341 On a target with a one cycle stall on a memory access the optimal
2350 We don't want to put the 'X += 12' before the branch because it just
2351 wastes a cycle of execution time when the branch is taken.
2353 Note that in the example "!C" will always be true. That is another
2354 possible improvement for handling COND_EXECs in this scheduler: it
2355 could remove always-true predicates. */
2357 if (!reload_completed
|| ! JUMP_P (tail
))
2361 while (insn
!= head
)
2363 insn
= PREV_INSN (insn
);
2365 /* Note that we want to add this dependency even when
2366 sched_insns_conditions_mutex_p returns true. The whole point
2367 is that we _want_ this dependency, even if these insns really
2369 if (INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == COND_EXEC
)
2370 add_dependence (tail
, insn
, REG_DEP_ANTI
);
2375 /* Data structures for the computation of data dependences in a regions. We
2376 keep one `deps' structure for every basic block. Before analyzing the
2377 data dependences for a bb, its variables are initialized as a function of
2378 the variables of its predecessors. When the analysis for a bb completes,
2379 we save the contents to the corresponding bb_deps[bb] variable. */
2381 static struct deps
*bb_deps
;
2383 /* Duplicate the INSN_LIST elements of COPY and prepend them to OLD. */
2386 concat_INSN_LIST (rtx copy
, rtx old
)
2389 for (; copy
; copy
= XEXP (copy
, 1))
2390 new = alloc_INSN_LIST (XEXP (copy
, 0), new);
2395 concat_insn_mem_list (rtx copy_insns
, rtx copy_mems
, rtx
*old_insns_p
,
2398 rtx new_insns
= *old_insns_p
;
2399 rtx new_mems
= *old_mems_p
;
2403 new_insns
= alloc_INSN_LIST (XEXP (copy_insns
, 0), new_insns
);
2404 new_mems
= alloc_EXPR_LIST (VOIDmode
, XEXP (copy_mems
, 0), new_mems
);
2405 copy_insns
= XEXP (copy_insns
, 1);
2406 copy_mems
= XEXP (copy_mems
, 1);
2409 *old_insns_p
= new_insns
;
2410 *old_mems_p
= new_mems
;
2413 /* After computing the dependencies for block BB, propagate the dependencies
2414 found in TMP_DEPS to the successors of the block. */
2416 propagate_deps (int bb
, struct deps
*pred_deps
)
2418 basic_block block
= BASIC_BLOCK (BB_TO_BLOCK (bb
));
2422 /* bb's structures are inherited by its successors. */
2423 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2425 struct deps
*succ_deps
;
2427 reg_set_iterator rsi
;
2429 /* Only bbs "below" bb, in the same region, are interesting. */
2430 if (e
->dest
== EXIT_BLOCK_PTR
2431 || CONTAINING_RGN (block
->index
) != CONTAINING_RGN (e
->dest
->index
)
2432 || BLOCK_TO_BB (e
->dest
->index
) <= bb
)
2435 succ_deps
= bb_deps
+ BLOCK_TO_BB (e
->dest
->index
);
2437 /* The reg_last lists are inherited by successor. */
2438 EXECUTE_IF_SET_IN_REG_SET (&pred_deps
->reg_last_in_use
, 0, reg
, rsi
)
2440 struct deps_reg
*pred_rl
= &pred_deps
->reg_last
[reg
];
2441 struct deps_reg
*succ_rl
= &succ_deps
->reg_last
[reg
];
2443 succ_rl
->uses
= concat_INSN_LIST (pred_rl
->uses
, succ_rl
->uses
);
2444 succ_rl
->sets
= concat_INSN_LIST (pred_rl
->sets
, succ_rl
->sets
);
2445 succ_rl
->clobbers
= concat_INSN_LIST (pred_rl
->clobbers
,
2447 succ_rl
->uses_length
+= pred_rl
->uses_length
;
2448 succ_rl
->clobbers_length
+= pred_rl
->clobbers_length
;
2450 IOR_REG_SET (&succ_deps
->reg_last_in_use
, &pred_deps
->reg_last_in_use
);
2452 /* Mem read/write lists are inherited by successor. */
2453 concat_insn_mem_list (pred_deps
->pending_read_insns
,
2454 pred_deps
->pending_read_mems
,
2455 &succ_deps
->pending_read_insns
,
2456 &succ_deps
->pending_read_mems
);
2457 concat_insn_mem_list (pred_deps
->pending_write_insns
,
2458 pred_deps
->pending_write_mems
,
2459 &succ_deps
->pending_write_insns
,
2460 &succ_deps
->pending_write_mems
);
2462 succ_deps
->last_pending_memory_flush
2463 = concat_INSN_LIST (pred_deps
->last_pending_memory_flush
,
2464 succ_deps
->last_pending_memory_flush
);
2466 succ_deps
->pending_read_list_length
2467 += pred_deps
->pending_read_list_length
;
2468 succ_deps
->pending_write_list_length
2469 += pred_deps
->pending_write_list_length
;
2470 succ_deps
->pending_flush_length
+= pred_deps
->pending_flush_length
;
2472 /* last_function_call is inherited by successor. */
2473 succ_deps
->last_function_call
2474 = concat_INSN_LIST (pred_deps
->last_function_call
,
2475 succ_deps
->last_function_call
);
2477 /* sched_before_next_call is inherited by successor. */
2478 succ_deps
->sched_before_next_call
2479 = concat_INSN_LIST (pred_deps
->sched_before_next_call
,
2480 succ_deps
->sched_before_next_call
);
2483 /* These lists should point to the right place, for correct
2485 bb_deps
[bb
].pending_read_insns
= pred_deps
->pending_read_insns
;
2486 bb_deps
[bb
].pending_read_mems
= pred_deps
->pending_read_mems
;
2487 bb_deps
[bb
].pending_write_insns
= pred_deps
->pending_write_insns
;
2488 bb_deps
[bb
].pending_write_mems
= pred_deps
->pending_write_mems
;
2490 /* Can't allow these to be freed twice. */
2491 pred_deps
->pending_read_insns
= 0;
2492 pred_deps
->pending_read_mems
= 0;
2493 pred_deps
->pending_write_insns
= 0;
2494 pred_deps
->pending_write_mems
= 0;
2497 /* Compute backward dependences inside bb. In a multiple blocks region:
2498 (1) a bb is analyzed after its predecessors, and (2) the lists in
2499 effect at the end of bb (after analyzing for bb) are inherited by
2502 Specifically for reg-reg data dependences, the block insns are
2503 scanned by sched_analyze () top-to-bottom. Two lists are
2504 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2505 and reg_last[].uses for register USEs.
2507 When analysis is completed for bb, we update for its successors:
2508 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2509 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2511 The mechanism for computing mem-mem data dependence is very
2512 similar, and the result is interblock dependences in the region. */
2515 compute_block_backward_dependences (int bb
)
2518 struct deps tmp_deps
;
2520 tmp_deps
= bb_deps
[bb
];
2522 /* Do the analysis for this block. */
2523 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2524 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2525 sched_analyze (&tmp_deps
, head
, tail
);
2526 add_branch_dependences (head
, tail
);
2528 if (current_nr_blocks
> 1)
2529 propagate_deps (bb
, &tmp_deps
);
2531 /* Free up the INSN_LISTs. */
2532 free_deps (&tmp_deps
);
2535 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2536 them to the unused_*_list variables, so that they can be reused. */
2539 free_pending_lists (void)
2543 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2545 free_INSN_LIST_list (&bb_deps
[bb
].pending_read_insns
);
2546 free_INSN_LIST_list (&bb_deps
[bb
].pending_write_insns
);
2547 free_EXPR_LIST_list (&bb_deps
[bb
].pending_read_mems
);
2548 free_EXPR_LIST_list (&bb_deps
[bb
].pending_write_mems
);
2552 /* Print dependences for debugging, callable from debugger. */
2555 debug_dependencies (void)
2559 fprintf (sched_dump
, ";; --------------- forward dependences: ------------ \n");
2560 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2566 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2567 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2568 next_tail
= NEXT_INSN (tail
);
2569 fprintf (sched_dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
2570 BB_TO_BLOCK (bb
), bb
);
2572 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2573 "insn", "code", "bb", "dep", "prio", "cost",
2575 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2576 "----", "----", "--", "---", "----", "----",
2579 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2583 if (! INSN_P (insn
))
2586 fprintf (sched_dump
, ";; %6d ", INSN_UID (insn
));
2589 n
= NOTE_LINE_NUMBER (insn
);
2591 fprintf (sched_dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
2594 fprintf (sched_dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
2598 fprintf (sched_dump
,
2599 ";; %s%5d%6d%6d%6d%6d%6d ",
2600 (SCHED_GROUP_P (insn
) ? "+" : " "),
2604 INSN_DEP_COUNT (insn
),
2605 INSN_PRIORITY (insn
),
2608 if (recog_memoized (insn
) < 0)
2609 fprintf (sched_dump
, "nothing");
2611 print_reservation (sched_dump
, insn
);
2613 fprintf (sched_dump
, "\t: ");
2614 FOR_EACH_DEP_LINK (link
, INSN_FORW_DEPS (insn
))
2615 fprintf (sched_dump
, "%d ", INSN_UID (DEP_LINK_CON (link
)));
2616 fprintf (sched_dump
, "\n");
2619 fprintf (sched_dump
, "\n");
2622 /* Returns true if all the basic blocks of the current region have
2623 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
2625 sched_is_disabled_for_current_region_p (void)
2629 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2630 if (!(BASIC_BLOCK (BB_TO_BLOCK (bb
))->flags
& BB_DISABLE_SCHEDULE
))
2636 /* Schedule a region. A region is either an inner loop, a loop-free
2637 subroutine, or a single basic block. Each bb in the region is
2638 scheduled after its flow predecessors. */
2641 schedule_region (int rgn
)
2647 int sched_rgn_n_insns
= 0;
2650 /* Set variables for the current region. */
2651 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
2652 current_blocks
= RGN_BLOCKS (rgn
);
2654 /* See comments in add_block1, for what reasons we allocate +1 element. */
2655 ebb_head
= xrealloc (ebb_head
, (current_nr_blocks
+ 1) * sizeof (*ebb_head
));
2656 for (bb
= 0; bb
<= current_nr_blocks
; bb
++)
2657 ebb_head
[bb
] = current_blocks
+ bb
;
2659 /* Don't schedule region that is marked by
2660 NOTE_DISABLE_SCHED_OF_BLOCK. */
2661 if (sched_is_disabled_for_current_region_p ())
2664 if (!RGN_DONT_CALC_DEPS (rgn
))
2666 init_deps_global ();
2668 /* Initializations for region data dependence analysis. */
2669 bb_deps
= XNEWVEC (struct deps
, current_nr_blocks
);
2670 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2671 init_deps (bb_deps
+ bb
);
2673 /* Compute backward dependencies. */
2674 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2675 compute_block_backward_dependences (bb
);
2677 /* Compute forward dependencies. */
2678 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
2682 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2683 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2685 compute_forward_dependences (head
, tail
);
2687 if (targetm
.sched
.dependencies_evaluation_hook
)
2688 targetm
.sched
.dependencies_evaluation_hook (head
, tail
);
2691 free_pending_lists ();
2693 finish_deps_global ();
2698 /* This is a recovery block. It is always a single block region. */
2699 gcc_assert (current_nr_blocks
== 1);
2701 /* Set priorities. */
2702 current_sched_info
->sched_max_insns_priority
= 0;
2703 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2707 gcc_assert (EBB_FIRST_BB (bb
) == EBB_LAST_BB (bb
));
2708 get_ebb_head_tail (EBB_FIRST_BB (bb
), EBB_LAST_BB (bb
), &head
, &tail
);
2710 rgn_n_insns
+= set_priorities (head
, tail
);
2712 current_sched_info
->sched_max_insns_priority
++;
2714 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
2715 if (current_nr_blocks
> 1)
2717 prob
= XNEWVEC (int, current_nr_blocks
);
2719 dom
= sbitmap_vector_alloc (current_nr_blocks
, current_nr_blocks
);
2720 sbitmap_vector_zero (dom
, current_nr_blocks
);
2722 /* Use ->aux to implement EDGE_TO_BIT mapping. */
2726 if (CONTAINING_RGN (block
->index
) != rgn
)
2728 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2729 SET_EDGE_TO_BIT (e
, rgn_nr_edges
++);
2732 rgn_edges
= XNEWVEC (edge
, rgn_nr_edges
);
2736 if (CONTAINING_RGN (block
->index
) != rgn
)
2738 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2739 rgn_edges
[rgn_nr_edges
++] = e
;
2743 pot_split
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
2744 sbitmap_vector_zero (pot_split
, current_nr_blocks
);
2745 ancestor_edges
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
2746 sbitmap_vector_zero (ancestor_edges
, current_nr_blocks
);
2748 /* Compute probabilities, dominators, split_edges. */
2749 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2750 compute_dom_prob_ps (bb
);
2752 /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
2753 /* We don't need them anymore. But we want to avoid duplication of
2754 aux fields in the newly created edges. */
2757 if (CONTAINING_RGN (block
->index
) != rgn
)
2759 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2764 /* Now we can schedule all blocks. */
2765 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2767 basic_block first_bb
, last_bb
, curr_bb
;
2770 first_bb
= EBB_FIRST_BB (bb
);
2771 last_bb
= EBB_LAST_BB (bb
);
2773 get_ebb_head_tail (first_bb
, last_bb
, &head
, &tail
);
2775 if (no_real_insns_p (head
, tail
))
2777 gcc_assert (first_bb
== last_bb
);
2781 current_sched_info
->prev_head
= PREV_INSN (head
);
2782 current_sched_info
->next_tail
= NEXT_INSN (tail
);
2785 /* rm_other_notes only removes notes which are _inside_ the
2786 block---that is, it won't remove notes before the first real insn
2787 or after the last real insn of the block. So if the first insn
2788 has a REG_SAVE_NOTE which would otherwise be emitted before the
2789 insn, it is redundant with the note before the start of the
2790 block, and so we have to take it out. */
2795 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
2796 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
2797 remove_note (head
, note
);
2800 /* This means that first block in ebb is empty.
2801 It looks to me as an impossible thing. There at least should be
2802 a recovery check, that caused the splitting. */
2805 /* Remove remaining note insns from the block, save them in
2806 note_list. These notes are restored at the end of
2807 schedule_block (). */
2808 rm_other_notes (head
, tail
);
2810 unlink_bb_notes (first_bb
, last_bb
);
2814 gcc_assert (flag_schedule_interblock
|| current_nr_blocks
== 1);
2815 current_sched_info
->queue_must_finish_empty
= current_nr_blocks
== 1;
2818 schedule_block (&curr_bb
, rgn_n_insns
);
2819 gcc_assert (EBB_FIRST_BB (bb
) == first_bb
);
2820 sched_rgn_n_insns
+= sched_n_insns
;
2823 if (current_nr_blocks
> 1)
2825 free (candidate_table
);
2827 free (edgelst_table
);
2831 /* Sanity check: verify that all region insns were scheduled. */
2832 gcc_assert (sched_rgn_n_insns
== rgn_n_insns
);
2835 /* Done with this region. */
2837 if (current_nr_blocks
> 1)
2840 sbitmap_vector_free (dom
);
2841 sbitmap_vector_free (pot_split
);
2842 sbitmap_vector_free (ancestor_edges
);
2847 /* Indexed by region, holds the number of death notes found in that region.
2848 Used for consistency checks. */
2849 static int *deaths_in_region
;
2851 /* Initialize data structures for region scheduling. */
2866 /* Compute regions for scheduling. */
2867 if (reload_completed
2868 || n_basic_blocks
== NUM_FIXED_BLOCKS
+ 1
2869 || !flag_schedule_interblock
2870 || is_cfg_nonregular ())
2872 find_single_block_region ();
2876 /* Compute the dominators and post dominators. */
2877 calculate_dominance_info (CDI_DOMINATORS
);
2882 if (sched_verbose
>= 3)
2885 /* For now. This will move as more and more of haifa is converted
2886 to using the cfg code in flow.c. */
2887 free_dominance_info (CDI_DOMINATORS
);
2889 RGN_BLOCKS (nr_regions
) = RGN_BLOCKS (nr_regions
- 1) +
2890 RGN_NR_BLOCKS (nr_regions
- 1);
2893 if (CHECK_DEAD_NOTES
)
2895 blocks
= sbitmap_alloc (last_basic_block
);
2896 deaths_in_region
= XNEWVEC (int, nr_regions
);
2897 /* Remove all death notes from the subroutine. */
2898 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
2899 check_dead_notes1 (rgn
, blocks
);
2901 sbitmap_free (blocks
);
2904 count_or_remove_death_notes (NULL
, 1);
2907 /* The one entry point in this file. */
2910 schedule_insns (void)
2912 sbitmap large_region_blocks
, blocks
;
2914 int any_large_regions
;
2917 /* Taking care of this degenerate case makes the rest of
2918 this code simpler. */
2919 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
2925 /* We need current_sched_info in init_dependency_caches, which is
2926 invoked via sched_init. */
2927 current_sched_info
= ®ion_sched_info
;
2931 min_spec_prob
= ((PARAM_VALUE (PARAM_MIN_SPEC_PROB
) * REG_BR_PROB_BASE
)
2936 /* EBB_HEAD is a region-scope structure. But we realloc it for
2937 each region to save time/memory/something else. */
2940 /* Schedule every region in the subroutine. */
2941 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
2942 schedule_region (rgn
);
2946 /* Update life analysis for the subroutine. Do single block regions
2947 first so that we can verify that live_at_start didn't change. Then
2948 do all other blocks. */
2949 /* ??? There is an outside possibility that update_life_info, or more
2950 to the point propagate_block, could get called with nonzero flags
2951 more than once for one basic block. This would be kinda bad if it
2952 were to happen, since REG_INFO would be accumulated twice for the
2953 block, and we'd have twice the REG_DEAD notes.
2955 I'm fairly certain that this _shouldn't_ happen, since I don't think
2956 that live_at_start should change at region heads. Not sure what the
2957 best way to test for this kind of thing... */
2959 if (current_sched_info
->flags
& DETACH_LIFE_INFO
)
2960 /* this flag can be set either by the target or by ENABLE_CHECKING. */
2961 attach_life_info ();
2963 allocate_reg_life_data ();
2965 any_large_regions
= 0;
2966 large_region_blocks
= sbitmap_alloc (last_basic_block
);
2967 sbitmap_zero (large_region_blocks
);
2969 SET_BIT (large_region_blocks
, bb
->index
);
2971 blocks
= sbitmap_alloc (last_basic_block
);
2972 sbitmap_zero (blocks
);
2974 /* Update life information. For regions consisting of multiple blocks
2975 we've possibly done interblock scheduling that affects global liveness.
2976 For regions consisting of single blocks we need to do only local
2978 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
2979 if (RGN_NR_BLOCKS (rgn
) > 1
2980 /* Or the only block of this region has been split. */
2981 || RGN_HAS_REAL_EBB (rgn
)
2982 /* New blocks (e.g. recovery blocks) should be processed
2983 as parts of large regions. */
2984 || !glat_start
[rgn_bb_table
[RGN_BLOCKS (rgn
)]])
2985 any_large_regions
= 1;
2988 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
2989 RESET_BIT (large_region_blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
2992 /* Don't update reg info after reload, since that affects
2993 regs_ever_live, which should not change after reload. */
2994 update_life_info (blocks
, UPDATE_LIFE_LOCAL
,
2995 (reload_completed
? PROP_DEATH_NOTES
2996 : (PROP_DEATH_NOTES
| PROP_REG_INFO
)));
2997 if (any_large_regions
)
2999 update_life_info (large_region_blocks
, UPDATE_LIFE_GLOBAL
,
3000 (reload_completed
? PROP_DEATH_NOTES
3001 : (PROP_DEATH_NOTES
| PROP_REG_INFO
)));
3003 #ifdef ENABLE_CHECKING
3004 check_reg_live (true);
3008 if (CHECK_DEAD_NOTES
)
3010 /* Verify the counts of basic block notes in single basic block
3012 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
3013 if (RGN_NR_BLOCKS (rgn
) == 1)
3015 sbitmap_zero (blocks
);
3016 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
3018 gcc_assert (deaths_in_region
[rgn
]
3019 == count_or_remove_death_notes (blocks
, 0));
3021 free (deaths_in_region
);
3024 /* Reposition the prologue and epilogue notes in case we moved the
3025 prologue/epilogue insns. */
3026 if (reload_completed
)
3027 reposition_prologue_and_epilogue_notes (get_insns ());
3031 if (reload_completed
== 0 && flag_schedule_interblock
)
3033 fprintf (sched_dump
,
3034 "\n;; Procedure interblock/speculative motions == %d/%d \n",
3038 gcc_assert (nr_inter
<= 0);
3039 fprintf (sched_dump
, "\n\n");
3044 free (rgn_bb_table
);
3046 free (containing_rgn
);
3050 sbitmap_free (blocks
);
3051 sbitmap_free (large_region_blocks
);
3054 /* INSN has been added to/removed from current region. */
3056 add_remove_insn (rtx insn
, int remove_p
)
3063 if (INSN_BB (insn
) == target_bb
)
3072 /* Extend internal data structures. */
3074 extend_regions (void)
3076 rgn_table
= XRESIZEVEC (region
, rgn_table
, n_basic_blocks
);
3077 rgn_bb_table
= XRESIZEVEC (int, rgn_bb_table
, n_basic_blocks
);
3078 block_to_bb
= XRESIZEVEC (int, block_to_bb
, last_basic_block
);
3079 containing_rgn
= XRESIZEVEC (int, containing_rgn
, last_basic_block
);
3082 /* BB was added to ebb after AFTER. */
3084 add_block1 (basic_block bb
, basic_block after
)
3088 if (after
== 0 || after
== EXIT_BLOCK_PTR
)
3092 i
= RGN_BLOCKS (nr_regions
);
3093 /* I - first free position in rgn_bb_table. */
3095 rgn_bb_table
[i
] = bb
->index
;
3096 RGN_NR_BLOCKS (nr_regions
) = 1;
3097 RGN_DONT_CALC_DEPS (nr_regions
) = after
== EXIT_BLOCK_PTR
;
3098 RGN_HAS_REAL_EBB (nr_regions
) = 0;
3099 CONTAINING_RGN (bb
->index
) = nr_regions
;
3100 BLOCK_TO_BB (bb
->index
) = 0;
3104 RGN_BLOCKS (nr_regions
) = i
+ 1;
3106 if (CHECK_DEAD_NOTES
)
3108 sbitmap blocks
= sbitmap_alloc (last_basic_block
);
3109 deaths_in_region
= xrealloc (deaths_in_region
, nr_regions
*
3110 sizeof (*deaths_in_region
));
3112 check_dead_notes1 (nr_regions
- 1, blocks
);
3114 sbitmap_free (blocks
);
3121 /* We need to fix rgn_table, block_to_bb, containing_rgn
3124 BLOCK_TO_BB (bb
->index
) = BLOCK_TO_BB (after
->index
);
3126 /* We extend ebb_head to one more position to
3127 easily find the last position of the last ebb in
3128 the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
3129 is _always_ valid for access. */
3131 i
= BLOCK_TO_BB (after
->index
) + 1;
3132 pos
= ebb_head
[i
] - 1;
3133 /* Now POS is the index of the last block in the region. */
3135 /* Find index of basic block AFTER. */
3136 for (; rgn_bb_table
[pos
] != after
->index
; pos
--);
3139 gcc_assert (pos
> ebb_head
[i
- 1]);
3141 /* i - ebb right after "AFTER". */
3142 /* ebb_head[i] - VALID. */
3144 /* Source position: ebb_head[i]
3145 Destination position: ebb_head[i] + 1
3147 RGN_BLOCKS (nr_regions) - 1
3148 Number of elements to copy: (last_position) - (source_position) + 1
3151 memmove (rgn_bb_table
+ pos
+ 1,
3153 ((RGN_BLOCKS (nr_regions
) - 1) - (pos
) + 1)
3154 * sizeof (*rgn_bb_table
));
3156 rgn_bb_table
[pos
] = bb
->index
;
3158 for (; i
<= current_nr_blocks
; i
++)
3161 i
= CONTAINING_RGN (after
->index
);
3162 CONTAINING_RGN (bb
->index
) = i
;
3164 RGN_HAS_REAL_EBB (i
) = 1;
3166 for (++i
; i
<= nr_regions
; i
++)
3169 /* We don't need to call check_dead_notes1 () because this new block
3170 is just a split of the old. We don't want to count anything twice. */
3174 /* Fix internal data after interblock movement of jump instruction.
3175 For parameter meaning please refer to
3176 sched-int.h: struct sched_info: fix_recovery_cfg. */
3178 fix_recovery_cfg (int bbi
, int check_bbi
, int check_bb_nexti
)
3180 int old_pos
, new_pos
, i
;
3182 BLOCK_TO_BB (check_bb_nexti
) = BLOCK_TO_BB (bbi
);
3184 for (old_pos
= ebb_head
[BLOCK_TO_BB (check_bbi
) + 1] - 1;
3185 rgn_bb_table
[old_pos
] != check_bb_nexti
;
3187 gcc_assert (old_pos
> ebb_head
[BLOCK_TO_BB (check_bbi
)]);
3189 for (new_pos
= ebb_head
[BLOCK_TO_BB (bbi
) + 1] - 1;
3190 rgn_bb_table
[new_pos
] != bbi
;
3193 gcc_assert (new_pos
> ebb_head
[BLOCK_TO_BB (bbi
)]);
3195 gcc_assert (new_pos
< old_pos
);
3197 memmove (rgn_bb_table
+ new_pos
+ 1,
3198 rgn_bb_table
+ new_pos
,
3199 (old_pos
- new_pos
) * sizeof (*rgn_bb_table
));
3201 rgn_bb_table
[new_pos
] = check_bb_nexti
;
3203 for (i
= BLOCK_TO_BB (bbi
) + 1; i
<= BLOCK_TO_BB (check_bbi
); i
++)
3207 /* Return next block in ebb chain. For parameter meaning please refer to
3208 sched-int.h: struct sched_info: advance_target_bb. */
3210 advance_target_bb (basic_block bb
, rtx insn
)
3215 gcc_assert (BLOCK_TO_BB (bb
->index
) == target_bb
3216 && BLOCK_TO_BB (bb
->next_bb
->index
) == target_bb
);
3220 /* Count and remove death notes in region RGN, which consists of blocks
3221 with indecies in BLOCKS. */
3223 check_dead_notes1 (int rgn
, sbitmap blocks
)
3227 sbitmap_zero (blocks
);
3228 for (b
= RGN_NR_BLOCKS (rgn
) - 1; b
>= 0; --b
)
3229 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
) + b
]);
3231 deaths_in_region
[rgn
] = count_or_remove_death_notes (blocks
, 1);
3234 #ifdef ENABLE_CHECKING
3235 /* Return non zero, if BB is head or leaf (depending of LEAF_P) block in
3236 current region. For more information please refer to
3237 sched-int.h: struct sched_info: region_head_or_leaf_p. */
3239 region_head_or_leaf_p (basic_block bb
, int leaf_p
)
3242 return bb
->index
== rgn_bb_table
[RGN_BLOCKS (CONTAINING_RGN (bb
->index
))];
3249 i
= CONTAINING_RGN (bb
->index
);
3251 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3252 if (e
->dest
!= EXIT_BLOCK_PTR
3253 && CONTAINING_RGN (e
->dest
->index
) == i
3254 /* except self-loop. */
3261 #endif /* ENABLE_CHECKING */
3266 gate_handle_sched (void)
3268 #ifdef INSN_SCHEDULING
3269 return flag_schedule_insns
;
3275 /* Run instruction scheduler. */
3277 rest_of_handle_sched (void)
3279 #ifdef INSN_SCHEDULING
3280 /* Do control and data sched analysis,
3281 and write some of the results to dump file. */
3289 gate_handle_sched2 (void)
3291 #ifdef INSN_SCHEDULING
3292 return optimize
> 0 && flag_schedule_insns_after_reload
;
3298 /* Run second scheduling pass after reload. */
3300 rest_of_handle_sched2 (void)
3302 #ifdef INSN_SCHEDULING
3303 /* Do control and data sched analysis again,
3304 and write some more of the results to dump file. */
3306 split_all_insns (1);
3308 if (flag_sched2_use_superblocks
|| flag_sched2_use_traces
)
3311 /* No liveness updating code yet, but it should be easy to do.
3312 reg-stack recomputes the liveness when needed for now. */
3313 count_or_remove_death_notes (NULL
, 1);
3314 cleanup_cfg (CLEANUP_EXPENSIVE
);
3322 struct tree_opt_pass pass_sched
=
3324 "sched1", /* name */
3325 gate_handle_sched
, /* gate */
3326 rest_of_handle_sched
, /* execute */
3329 0, /* static_pass_number */
3330 TV_SCHED
, /* tv_id */
3331 0, /* properties_required */
3332 0, /* properties_provided */
3333 0, /* properties_destroyed */
3334 0, /* todo_flags_start */
3336 TODO_ggc_collect
, /* todo_flags_finish */
3340 struct tree_opt_pass pass_sched2
=
3342 "sched2", /* name */
3343 gate_handle_sched2
, /* gate */
3344 rest_of_handle_sched2
, /* execute */
3347 0, /* static_pass_number */
3348 TV_SCHED2
, /* tv_id */
3349 0, /* properties_required */
3350 0, /* properties_provided */
3351 0, /* properties_destroyed */
3352 0, /* todo_flags_start */
3354 TODO_ggc_collect
, /* todo_flags_finish */