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, 59 Temple Place - Suite 330, 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 /* Define when we want to do count REG_DEAD notes before and after scheduling
70 for sanity checking. We can't do that when conditional execution is used,
71 as REG_DEAD exist only for unconditional deaths. */
73 #if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING)
74 #define CHECK_DEAD_NOTES 1
76 #define CHECK_DEAD_NOTES 0
80 #ifdef INSN_SCHEDULING
81 /* Some accessor macros for h_i_d members only used within this file. */
82 #define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count)
83 #define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load)
84 #define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn)
86 /* nr_inter/spec counts interblock/speculative motion for the function. */
87 static int nr_inter
, nr_spec
;
89 static int is_cfg_nonregular (void);
90 static bool sched_is_disabled_for_current_region_p (void);
92 /* A region is the main entity for interblock scheduling: insns
93 are allowed to move between blocks in the same region, along
94 control flow graph edges, in the 'up' direction. */
97 int rgn_nr_blocks
; /* Number of blocks in region. */
98 int rgn_blocks
; /* cblocks in the region (actually index in rgn_bb_table). */
102 /* Number of regions in the procedure. */
103 static int nr_regions
;
105 /* Table of region descriptions. */
106 static region
*rgn_table
;
108 /* Array of lists of regions' blocks. */
109 static int *rgn_bb_table
;
111 /* Topological order of blocks in the region (if b2 is reachable from
112 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
113 always referred to by either block or b, while its topological
114 order name (in the region) is referred to by bb. */
115 static int *block_to_bb
;
117 /* The number of the region containing a block. */
118 static int *containing_rgn
;
120 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
121 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
122 #define BLOCK_TO_BB(block) (block_to_bb[block])
123 #define CONTAINING_RGN(block) (containing_rgn[block])
125 void debug_regions (void);
126 static void find_single_block_region (void);
127 static void find_rgns (void);
128 static bool too_large (int, int *, int *);
130 extern void debug_live (int, int);
132 /* Blocks of the current region being scheduled. */
133 static int current_nr_blocks
;
134 static int current_blocks
;
136 /* The mapping from bb to block. */
137 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
139 /* Target info declarations.
141 The block currently being scheduled is referred to as the "target" block,
142 while other blocks in the region from which insns can be moved to the
143 target are called "source" blocks. The candidate structure holds info
144 about such sources: are they valid? Speculative? Etc. */
147 basic_block
*first_member
;
162 static candidate
*candidate_table
;
164 /* A speculative motion requires checking live information on the path
165 from 'source' to 'target'. The split blocks are those to be checked.
166 After a speculative motion, live information should be modified in
169 Lists of split and update blocks for each candidate of the current
170 target are in array bblst_table. */
171 static basic_block
*bblst_table
;
172 static int bblst_size
, bblst_last
;
174 #define IS_VALID(src) ( candidate_table[src].is_valid )
175 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
176 #define SRC_PROB(src) ( candidate_table[src].src_prob )
178 /* The bb being currently scheduled. */
179 static int target_bb
;
189 static edge
*edgelst_table
;
190 static int edgelst_last
;
192 static void extract_edgelst (sbitmap
, edgelst
*);
195 /* Target info functions. */
196 static void split_edges (int, int, edgelst
*);
197 static void compute_trg_info (int);
198 void debug_candidate (int);
199 void debug_candidates (int);
201 /* Dominators array: dom[i] contains the sbitmap of dominators of
202 bb i in the region. */
205 /* bb 0 is the only region entry. */
206 #define IS_RGN_ENTRY(bb) (!bb)
208 /* Is bb_src dominated by bb_trg. */
209 #define IS_DOMINATED(bb_src, bb_trg) \
210 ( TEST_BIT (dom[bb_src], bb_trg) )
212 /* Probability: Prob[i] is a float in [0, 1] which is the probability
213 of bb i relative to the region entry. */
216 /* The probability of bb_src, relative to bb_trg. Note, that while the
217 'prob[bb]' is a float in [0, 1], this macro returns an integer
219 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
222 /* Bit-set of edges, where bit i stands for edge i. */
223 typedef sbitmap edgeset
;
225 /* Number of edges in the region. */
226 static int rgn_nr_edges
;
228 /* Array of size rgn_nr_edges. */
229 static edge
*rgn_edges
;
231 /* Mapping from each edge in the graph to its number in the rgn. */
232 #define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
233 #define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
235 /* The split edges of a source bb is different for each target
236 bb. In order to compute this efficiently, the 'potential-split edges'
237 are computed for each bb prior to scheduling a region. This is actually
238 the split edges of each bb relative to the region entry.
240 pot_split[bb] is the set of potential split edges of bb. */
241 static edgeset
*pot_split
;
243 /* For every bb, a set of its ancestor edges. */
244 static edgeset
*ancestor_edges
;
246 static void compute_dom_prob_ps (int);
248 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
249 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
250 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
252 /* Parameters affecting the decision of rank_for_schedule().
253 ??? Nope. But MIN_PROBABILITY is used in compute_trg_info. */
254 #define MIN_PROBABILITY 40
256 /* Speculative scheduling functions. */
257 static int check_live_1 (int, rtx
);
258 static void update_live_1 (int, rtx
);
259 static int check_live (rtx
, int);
260 static void update_live (rtx
, int);
261 static void set_spec_fed (rtx
);
262 static int is_pfree (rtx
, int, int);
263 static int find_conditional_protection (rtx
, int);
264 static int is_conditionally_protected (rtx
, int, int);
265 static int is_prisky (rtx
, int, int);
266 static int is_exception_free (rtx
, int, int);
268 static bool sets_likely_spilled (rtx
);
269 static void sets_likely_spilled_1 (rtx
, rtx
, void *);
270 static void add_branch_dependences (rtx
, rtx
);
271 static void compute_block_backward_dependences (int);
272 void debug_dependencies (void);
274 static void init_regions (void);
275 static void schedule_region (int);
276 static rtx
concat_INSN_LIST (rtx
, rtx
);
277 static void concat_insn_mem_list (rtx
, rtx
, rtx
*, rtx
*);
278 static void propagate_deps (int, struct deps
*);
279 static void free_pending_lists (void);
281 /* Functions for construction of the control flow graph. */
283 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
285 We decide not to build the control flow graph if there is possibly more
286 than one entry to the function, if computed branches exist, if we
287 have nonlocal gotos, or if we have an unreachable loop. */
290 is_cfg_nonregular (void)
296 /* If we have a label that could be the target of a nonlocal goto, then
297 the cfg is not well structured. */
298 if (nonlocal_goto_handler_labels
)
301 /* If we have any forced labels, then the cfg is not well structured. */
305 /* If this function has a computed jump, then we consider the cfg
306 not well structured. */
307 if (current_function_has_computed_jump
)
310 /* If we have exception handlers, then we consider the cfg not well
311 structured. ?!? We should be able to handle this now that flow.c
312 computes an accurate cfg for EH. */
313 if (current_function_has_exception_handlers ())
316 /* If we have non-jumping insns which refer to labels, then we consider
317 the cfg not well structured. */
318 /* Check for labels referred to other thn by jumps. */
320 for (insn
= BB_HEAD (b
); ; insn
= NEXT_INSN (insn
))
322 code
= GET_CODE (insn
);
323 if (INSN_P (insn
) && code
!= JUMP_INSN
)
325 rtx note
= find_reg_note (insn
, REG_LABEL
, NULL_RTX
);
328 && ! (JUMP_P (NEXT_INSN (insn
))
329 && find_reg_note (NEXT_INSN (insn
), REG_LABEL
,
334 if (insn
== BB_END (b
))
338 /* Unreachable loops with more than one basic block are detected
339 during the DFS traversal in find_rgns.
341 Unreachable loops with a single block are detected here. This
342 test is redundant with the one in find_rgns, but it's much
343 cheaper to go ahead and catch the trivial case here. */
346 if (EDGE_COUNT (b
->preds
) == 0
347 || (EDGE_PRED (b
, 0)->src
== b
348 && EDGE_COUNT (b
->preds
) == 1))
352 /* All the tests passed. Consider the cfg well structured. */
356 /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */
359 extract_edgelst (sbitmap set
, edgelst
*el
)
363 /* edgelst table space is reused in each call to extract_edgelst. */
366 el
->first_member
= &edgelst_table
[edgelst_last
];
369 /* Iterate over each word in the bitset. */
370 EXECUTE_IF_SET_IN_SBITMAP (set
, 0, i
,
372 edgelst_table
[edgelst_last
++] = rgn_edges
[i
];
377 /* Functions for the construction of regions. */
379 /* Print the regions, for debugging purposes. Callable from debugger. */
386 fprintf (sched_dump
, "\n;; ------------ REGIONS ----------\n\n");
387 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
389 fprintf (sched_dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
390 rgn_table
[rgn
].rgn_nr_blocks
);
391 fprintf (sched_dump
, ";;\tbb/block: ");
393 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
395 current_blocks
= RGN_BLOCKS (rgn
);
397 gcc_assert (bb
== BLOCK_TO_BB (BB_TO_BLOCK (bb
)));
398 fprintf (sched_dump
, " %d/%d ", bb
, BB_TO_BLOCK (bb
));
401 fprintf (sched_dump
, "\n\n");
405 /* Build a single block region for each basic block in the function.
406 This allows for using the same code for interblock and basic block
410 find_single_block_region (void)
418 rgn_bb_table
[nr_regions
] = bb
->index
;
419 RGN_NR_BLOCKS (nr_regions
) = 1;
420 RGN_BLOCKS (nr_regions
) = nr_regions
;
421 CONTAINING_RGN (bb
->index
) = nr_regions
;
422 BLOCK_TO_BB (bb
->index
) = 0;
427 /* Update number of blocks and the estimate for number of insns
428 in the region. Return true if the region is "too large" for interblock
429 scheduling (compile time considerations). */
432 too_large (int block
, int *num_bbs
, int *num_insns
)
435 (*num_insns
) += (INSN_LUID (BB_END (BASIC_BLOCK (block
)))
436 - INSN_LUID (BB_HEAD (BASIC_BLOCK (block
))));
438 return ((*num_bbs
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS
))
439 || (*num_insns
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS
)));
442 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
443 is still an inner loop. Put in max_hdr[blk] the header of the most inner
444 loop containing blk. */
445 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
447 if (max_hdr[blk] == -1) \
448 max_hdr[blk] = hdr; \
449 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
450 RESET_BIT (inner, hdr); \
451 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
453 RESET_BIT (inner,max_hdr[blk]); \
454 max_hdr[blk] = hdr; \
458 /* Find regions for interblock scheduling.
460 A region for scheduling can be:
462 * A loop-free procedure, or
464 * A reducible inner loop, or
466 * A basic block not contained in any other region.
468 ?!? In theory we could build other regions based on extended basic
469 blocks or reverse extended basic blocks. Is it worth the trouble?
471 Loop blocks that form a region are put into the region's block list
472 in topological order.
474 This procedure stores its results into the following global (ick) variables
482 We use dominator relationships to avoid making regions out of non-reducible
485 This procedure needs to be converted to work on pred/succ lists instead
486 of edge tables. That would simplify it somewhat. */
491 int *max_hdr
, *dfs_nr
, *degree
;
493 int node
, child
, loop_head
, i
, head
, tail
;
494 int count
= 0, sp
, idx
= 0;
495 edge_iterator current_edge
;
496 edge_iterator
*stack
;
497 int num_bbs
, num_insns
, unreachable
;
498 int too_large_failure
;
501 /* Note if a block is a natural loop header. */
504 /* Note if a block is a natural inner loop header. */
507 /* Note if a block is in the block queue. */
510 /* Note if a block is in the block queue. */
513 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
514 and a mapping from block to its loop header (if the block is contained
517 Store results in HEADER, INNER, and MAX_HDR respectively, these will
518 be used as inputs to the second traversal.
520 STACK, SP and DFS_NR are only used during the first traversal. */
522 /* Allocate and initialize variables for the first traversal. */
523 max_hdr
= xmalloc (last_basic_block
* sizeof (int));
524 dfs_nr
= xcalloc (last_basic_block
, sizeof (int));
525 stack
= xmalloc (n_edges
* sizeof (edge_iterator
));
527 inner
= sbitmap_alloc (last_basic_block
);
528 sbitmap_ones (inner
);
530 header
= sbitmap_alloc (last_basic_block
);
531 sbitmap_zero (header
);
533 in_queue
= sbitmap_alloc (last_basic_block
);
534 sbitmap_zero (in_queue
);
536 in_stack
= sbitmap_alloc (last_basic_block
);
537 sbitmap_zero (in_stack
);
539 for (i
= 0; i
< last_basic_block
; i
++)
542 #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
543 #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
545 /* DFS traversal to find inner loops in the cfg. */
547 current_edge
= ei_start (EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->dest
->succs
);
552 if (EDGE_PASSED (current_edge
))
554 /* We have reached a leaf node or a node that was already
555 processed. Pop edges off the stack until we find
556 an edge that has not yet been processed. */
557 while (sp
>= 0 && EDGE_PASSED (current_edge
))
559 /* Pop entry off the stack. */
560 current_edge
= stack
[sp
--];
561 node
= ei_edge (current_edge
)->src
->index
;
562 gcc_assert (node
!= ENTRY_BLOCK
);
563 child
= ei_edge (current_edge
)->dest
->index
;
564 gcc_assert (child
!= EXIT_BLOCK
);
565 RESET_BIT (in_stack
, child
);
566 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
567 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
568 ei_next (¤t_edge
);
571 /* See if have finished the DFS tree traversal. */
572 if (sp
< 0 && EDGE_PASSED (current_edge
))
575 /* Nope, continue the traversal with the popped node. */
579 /* Process a node. */
580 node
= ei_edge (current_edge
)->src
->index
;
581 gcc_assert (node
!= ENTRY_BLOCK
);
582 SET_BIT (in_stack
, node
);
583 dfs_nr
[node
] = ++count
;
585 /* We don't traverse to the exit block. */
586 child
= ei_edge (current_edge
)->dest
->index
;
587 if (child
== EXIT_BLOCK
)
589 SET_EDGE_PASSED (current_edge
);
590 ei_next (¤t_edge
);
594 /* If the successor is in the stack, then we've found a loop.
595 Mark the loop, if it is not a natural loop, then it will
596 be rejected during the second traversal. */
597 if (TEST_BIT (in_stack
, child
))
600 SET_BIT (header
, child
);
601 UPDATE_LOOP_RELATIONS (node
, child
);
602 SET_EDGE_PASSED (current_edge
);
603 ei_next (¤t_edge
);
607 /* If the child was already visited, then there is no need to visit
608 it again. Just update the loop relationships and restart
612 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
613 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
614 SET_EDGE_PASSED (current_edge
);
615 ei_next (¤t_edge
);
619 /* Push an entry on the stack and continue DFS traversal. */
620 stack
[++sp
] = current_edge
;
621 SET_EDGE_PASSED (current_edge
);
622 current_edge
= ei_start (ei_edge (current_edge
)->dest
->succs
);
625 /* Reset ->aux field used by EDGE_PASSED. */
630 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
635 /* Another check for unreachable blocks. The earlier test in
636 is_cfg_nonregular only finds unreachable blocks that do not
639 The DFS traversal will mark every block that is reachable from
640 the entry node by placing a nonzero value in dfs_nr. Thus if
641 dfs_nr is zero for any block, then it must be unreachable. */
644 if (dfs_nr
[bb
->index
] == 0)
650 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
651 to hold degree counts. */
655 degree
[bb
->index
] = EDGE_COUNT (bb
->preds
);
657 /* Do not perform region scheduling if there are any unreachable
666 /* Second traversal:find reducible inner loops and topologically sort
667 block of each region. */
669 queue
= xmalloc (n_basic_blocks
* sizeof (int));
671 /* Find blocks which are inner loop headers. We still have non-reducible
672 loops to consider at this point. */
675 if (TEST_BIT (header
, bb
->index
) && TEST_BIT (inner
, bb
->index
))
681 /* Now check that the loop is reducible. We do this separate
682 from finding inner loops so that we do not find a reducible
683 loop which contains an inner non-reducible loop.
685 A simple way to find reducible/natural loops is to verify
686 that each block in the loop is dominated by the loop
689 If there exists a block that is not dominated by the loop
690 header, then the block is reachable from outside the loop
691 and thus the loop is not a natural loop. */
694 /* First identify blocks in the loop, except for the loop
696 if (bb
->index
== max_hdr
[jbb
->index
] && bb
!= jbb
)
698 /* Now verify that the block is dominated by the loop
700 if (!dominated_by_p (CDI_DOMINATORS
, jbb
, bb
))
705 /* If we exited the loop early, then I is the header of
706 a non-reducible loop and we should quit processing it
708 if (jbb
!= EXIT_BLOCK_PTR
)
711 /* I is a header of an inner loop, or block 0 in a subroutine
712 with no loops at all. */
714 too_large_failure
= 0;
715 loop_head
= max_hdr
[bb
->index
];
717 /* Decrease degree of all I's successors for topological
719 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
720 if (e
->dest
!= EXIT_BLOCK_PTR
)
721 --degree
[e
->dest
->index
];
723 /* Estimate # insns, and count # blocks in the region. */
725 num_insns
= (INSN_LUID (BB_END (bb
))
726 - INSN_LUID (BB_HEAD (bb
)));
728 /* Find all loop latches (blocks with back edges to the loop
729 header) or all the leaf blocks in the cfg has no loops.
731 Place those blocks into the queue. */
735 /* Leaf nodes have only a single successor which must
737 if (EDGE_COUNT (jbb
->succs
) == 1
738 && EDGE_SUCC (jbb
, 0)->dest
== EXIT_BLOCK_PTR
)
740 queue
[++tail
] = jbb
->index
;
741 SET_BIT (in_queue
, jbb
->index
);
743 if (too_large (jbb
->index
, &num_bbs
, &num_insns
))
745 too_large_failure
= 1;
754 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
756 if (e
->src
== ENTRY_BLOCK_PTR
)
759 node
= e
->src
->index
;
761 if (max_hdr
[node
] == loop_head
&& node
!= bb
->index
)
763 /* This is a loop latch. */
764 queue
[++tail
] = node
;
765 SET_BIT (in_queue
, node
);
767 if (too_large (node
, &num_bbs
, &num_insns
))
769 too_large_failure
= 1;
776 /* Now add all the blocks in the loop to the queue.
778 We know the loop is a natural loop; however the algorithm
779 above will not always mark certain blocks as being in the
787 The algorithm in the DFS traversal may not mark B & D as part
788 of the loop (i.e. they will not have max_hdr set to A).
790 We know they can not be loop latches (else they would have
791 had max_hdr set since they'd have a backedge to a dominator
792 block). So we don't need them on the initial queue.
794 We know they are part of the loop because they are dominated
795 by the loop header and can be reached by a backwards walk of
796 the edges starting with nodes on the initial queue.
798 It is safe and desirable to include those nodes in the
799 loop/scheduling region. To do so we would need to decrease
800 the degree of a node if it is the target of a backedge
801 within the loop itself as the node is placed in the queue.
803 We do not do this because I'm not sure that the actual
804 scheduling code will properly handle this case. ?!? */
806 while (head
< tail
&& !too_large_failure
)
809 child
= queue
[++head
];
811 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (child
)->preds
)
813 node
= e
->src
->index
;
815 /* See discussion above about nodes not marked as in
816 this loop during the initial DFS traversal. */
817 if (e
->src
== ENTRY_BLOCK_PTR
818 || max_hdr
[node
] != loop_head
)
823 else if (!TEST_BIT (in_queue
, node
) && node
!= bb
->index
)
825 queue
[++tail
] = node
;
826 SET_BIT (in_queue
, node
);
828 if (too_large (node
, &num_bbs
, &num_insns
))
830 too_large_failure
= 1;
837 if (tail
>= 0 && !too_large_failure
)
839 /* Place the loop header into list of region blocks. */
840 degree
[bb
->index
] = -1;
841 rgn_bb_table
[idx
] = bb
->index
;
842 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
843 RGN_BLOCKS (nr_regions
) = idx
++;
844 CONTAINING_RGN (bb
->index
) = nr_regions
;
845 BLOCK_TO_BB (bb
->index
) = count
= 0;
847 /* Remove blocks from queue[] when their in degree
848 becomes zero. Repeat until no blocks are left on the
849 list. This produces a topological list of blocks in
856 if (degree
[child
] == 0)
861 rgn_bb_table
[idx
++] = child
;
862 BLOCK_TO_BB (child
) = ++count
;
863 CONTAINING_RGN (child
) = nr_regions
;
864 queue
[head
] = queue
[tail
--];
866 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (child
)->succs
)
867 if (e
->dest
!= EXIT_BLOCK_PTR
)
868 --degree
[e
->dest
->index
];
880 /* Any block that did not end up in a region is placed into a region
883 if (degree
[bb
->index
] >= 0)
885 rgn_bb_table
[idx
] = bb
->index
;
886 RGN_NR_BLOCKS (nr_regions
) = 1;
887 RGN_BLOCKS (nr_regions
) = idx
++;
888 CONTAINING_RGN (bb
->index
) = nr_regions
++;
889 BLOCK_TO_BB (bb
->index
) = 0;
895 sbitmap_free (header
);
896 sbitmap_free (inner
);
897 sbitmap_free (in_queue
);
898 sbitmap_free (in_stack
);
901 /* Functions for regions scheduling information. */
903 /* Compute dominators, probability, and potential-split-edges of bb.
904 Assume that these values were already computed for bb's predecessors. */
907 compute_dom_prob_ps (int bb
)
910 int nr_out_edges
, nr_rgn_out_edges
;
911 edge_iterator in_ei
, out_ei
;
912 edge in_edge
, out_edge
;
915 if (IS_RGN_ENTRY (bb
))
917 SET_BIT (dom
[bb
], 0);
922 /* Initialize dom[bb] to '111..1'. */
923 sbitmap_ones (dom
[bb
]);
925 FOR_EACH_EDGE (in_edge
, in_ei
, BASIC_BLOCK (BB_TO_BLOCK (bb
))->preds
)
927 if (in_edge
->src
== ENTRY_BLOCK_PTR
)
930 pred_bb
= BLOCK_TO_BB (in_edge
->src
->index
);
931 sbitmap_a_and_b (dom
[bb
], dom
[bb
], dom
[pred_bb
]);
932 sbitmap_a_or_b (ancestor_edges
[bb
],
933 ancestor_edges
[bb
], ancestor_edges
[pred_bb
]);
935 SET_BIT (ancestor_edges
[bb
], EDGE_TO_BIT (in_edge
));
937 sbitmap_a_or_b (pot_split
[bb
], pot_split
[bb
], pot_split
[pred_bb
]);
940 nr_rgn_out_edges
= 0;
942 FOR_EACH_EDGE (out_edge
, out_ei
, in_edge
->src
->succs
)
946 /* The successor doesn't belong in the region? */
947 if (out_edge
->dest
!= EXIT_BLOCK_PTR
948 && CONTAINING_RGN (out_edge
->dest
->index
)
949 != CONTAINING_RGN (BB_TO_BLOCK (bb
)))
952 SET_BIT (pot_split
[bb
], EDGE_TO_BIT (out_edge
));
955 /* Now nr_rgn_out_edges is the number of region-exit edges from
956 pred, and nr_out_edges will be the number of pred out edges
957 not leaving the region. */
958 nr_out_edges
-= nr_rgn_out_edges
;
959 if (nr_rgn_out_edges
> 0)
960 prob
[bb
] += 0.9 * prob
[pred_bb
] / nr_out_edges
;
962 prob
[bb
] += prob
[pred_bb
] / nr_out_edges
;
965 SET_BIT (dom
[bb
], bb
);
966 sbitmap_difference (pot_split
[bb
], pot_split
[bb
], ancestor_edges
[bb
]);
968 if (sched_verbose
>= 2)
969 fprintf (sched_dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
),
970 (int) (100.0 * prob
[bb
]));
973 /* Functions for target info. */
975 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
976 Note that bb_trg dominates bb_src. */
979 split_edges (int bb_src
, int bb_trg
, edgelst
*bl
)
981 sbitmap src
= sbitmap_alloc (pot_split
[bb_src
]->n_bits
);
982 sbitmap_copy (src
, pot_split
[bb_src
]);
984 sbitmap_difference (src
, src
, pot_split
[bb_trg
]);
985 extract_edgelst (src
, bl
);
989 /* Find the valid candidate-source-blocks for the target block TRG, compute
990 their probability, and check if they are speculative or not.
991 For speculative sources, compute their update-blocks and split-blocks. */
994 compute_trg_info (int trg
)
998 int i
, j
, k
, update_idx
;
1004 /* Define some of the fields for the target bb as well. */
1005 sp
= candidate_table
+ trg
;
1007 sp
->is_speculative
= 0;
1010 visited
= sbitmap_alloc (last_basic_block
- (INVALID_BLOCK
+ 1));
1012 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1014 sp
= candidate_table
+ i
;
1016 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1019 sp
->src_prob
= GET_SRC_PROB (i
, trg
);
1020 sp
->is_valid
= (sp
->src_prob
>= MIN_PROBABILITY
);
1025 split_edges (i
, trg
, &el
);
1026 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1027 if (sp
->is_speculative
&& !flag_schedule_speculative
)
1033 /* Compute split blocks and store them in bblst_table.
1034 The TO block of every split edge is a split block. */
1035 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
1036 sp
->split_bbs
.nr_members
= el
.nr_members
;
1037 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
1038 bblst_table
[bblst_last
] = el
.first_member
[j
]->dest
;
1039 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
1041 /* Compute update blocks and store them in bblst_table.
1042 For every split edge, look at the FROM block, and check
1043 all out edges. For each out edge that is not a split edge,
1044 add the TO block to the update block list. This list can end
1045 up with a lot of duplicates. We need to weed them out to avoid
1046 overrunning the end of the bblst_table. */
1049 sbitmap_zero (visited
);
1050 for (j
= 0; j
< el
.nr_members
; j
++)
1052 block
= el
.first_member
[j
]->src
;
1053 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1055 if (!TEST_BIT (visited
,
1056 e
->dest
->index
- (INVALID_BLOCK
+ 1)))
1058 for (k
= 0; k
< el
.nr_members
; k
++)
1059 if (e
== el
.first_member
[k
])
1062 if (k
>= el
.nr_members
)
1064 bblst_table
[bblst_last
++] = e
->dest
;
1066 e
->dest
->index
- (INVALID_BLOCK
+ 1));
1072 sp
->update_bbs
.nr_members
= update_idx
;
1074 /* Make sure we didn't overrun the end of bblst_table. */
1075 gcc_assert (bblst_last
<= bblst_size
);
1079 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
1081 sp
->is_speculative
= 0;
1086 sbitmap_free (visited
);
1089 /* Print candidates info, for debugging purposes. Callable from debugger. */
1092 debug_candidate (int i
)
1094 if (!candidate_table
[i
].is_valid
)
1097 if (candidate_table
[i
].is_speculative
)
1100 fprintf (sched_dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
1102 fprintf (sched_dump
, "split path: ");
1103 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
1105 int b
= candidate_table
[i
].split_bbs
.first_member
[j
]->index
;
1107 fprintf (sched_dump
, " %d ", b
);
1109 fprintf (sched_dump
, "\n");
1111 fprintf (sched_dump
, "update path: ");
1112 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
1114 int b
= candidate_table
[i
].update_bbs
.first_member
[j
]->index
;
1116 fprintf (sched_dump
, " %d ", b
);
1118 fprintf (sched_dump
, "\n");
1122 fprintf (sched_dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
1126 /* Print candidates info, for debugging purposes. Callable from debugger. */
1129 debug_candidates (int trg
)
1133 fprintf (sched_dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
1134 BB_TO_BLOCK (trg
), trg
);
1135 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1136 debug_candidate (i
);
1139 /* Functions for speculative scheduling. */
1141 /* Return 0 if x is a set of a register alive in the beginning of one
1142 of the split-blocks of src, otherwise return 1. */
1145 check_live_1 (int src
, rtx x
)
1149 rtx reg
= SET_DEST (x
);
1154 while (GET_CODE (reg
) == SUBREG
1155 || GET_CODE (reg
) == ZERO_EXTRACT
1156 || GET_CODE (reg
) == STRICT_LOW_PART
)
1157 reg
= XEXP (reg
, 0);
1159 if (GET_CODE (reg
) == PARALLEL
)
1163 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1164 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1165 if (check_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0)))
1174 regno
= REGNO (reg
);
1176 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
1178 /* Global registers are assumed live. */
1183 if (regno
< FIRST_PSEUDO_REGISTER
)
1185 /* Check for hard registers. */
1186 int j
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1189 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1191 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1193 if (REGNO_REG_SET_P (b
->global_live_at_start
, regno
+ j
))
1202 /* Check for pseudo registers. */
1203 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1205 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1207 if (REGNO_REG_SET_P (b
->global_live_at_start
, regno
))
1218 /* If x is a set of a register R, mark that R is alive in the beginning
1219 of every update-block of src. */
1222 update_live_1 (int src
, rtx x
)
1226 rtx reg
= SET_DEST (x
);
1231 while (GET_CODE (reg
) == SUBREG
1232 || GET_CODE (reg
) == ZERO_EXTRACT
1233 || GET_CODE (reg
) == STRICT_LOW_PART
)
1234 reg
= XEXP (reg
, 0);
1236 if (GET_CODE (reg
) == PARALLEL
)
1240 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1241 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1242 update_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0));
1250 /* Global registers are always live, so the code below does not apply
1253 regno
= REGNO (reg
);
1255 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
1257 if (regno
< FIRST_PSEUDO_REGISTER
)
1259 int j
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1262 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
1264 basic_block b
= candidate_table
[src
].update_bbs
.first_member
[i
];
1266 SET_REGNO_REG_SET (b
->global_live_at_start
, regno
+ j
);
1272 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
1274 basic_block b
= candidate_table
[src
].update_bbs
.first_member
[i
];
1276 SET_REGNO_REG_SET (b
->global_live_at_start
, regno
);
1282 /* Return 1 if insn can be speculatively moved from block src to trg,
1283 otherwise return 0. Called before first insertion of insn to
1284 ready-list or before the scheduling. */
1287 check_live (rtx insn
, int src
)
1289 /* Find the registers set by instruction. */
1290 if (GET_CODE (PATTERN (insn
)) == SET
1291 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1292 return check_live_1 (src
, PATTERN (insn
));
1293 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1296 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1297 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1298 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1299 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
1308 /* Update the live registers info after insn was moved speculatively from
1309 block src to trg. */
1312 update_live (rtx insn
, int src
)
1314 /* Find the registers set by instruction. */
1315 if (GET_CODE (PATTERN (insn
)) == SET
1316 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1317 update_live_1 (src
, PATTERN (insn
));
1318 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1321 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1322 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1323 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1324 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
1328 /* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1329 #define IS_REACHABLE(bb_from, bb_to) \
1331 || IS_RGN_ENTRY (bb_from) \
1332 || (TEST_BIT (ancestor_edges[bb_to], \
1333 EDGE_TO_BIT (EDGE_PRED (BASIC_BLOCK (BB_TO_BLOCK (bb_from)), 0)))))
1335 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1338 set_spec_fed (rtx load_insn
)
1342 for (link
= INSN_DEPEND (load_insn
); link
; link
= XEXP (link
, 1))
1343 if (GET_MODE (link
) == VOIDmode
)
1344 FED_BY_SPEC_LOAD (XEXP (link
, 0)) = 1;
1345 } /* set_spec_fed */
1347 /* On the path from the insn to load_insn_bb, find a conditional
1348 branch depending on insn, that guards the speculative load. */
1351 find_conditional_protection (rtx insn
, int load_insn_bb
)
1355 /* Iterate through DEF-USE forward dependences. */
1356 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
1358 rtx next
= XEXP (link
, 0);
1359 if ((CONTAINING_RGN (BLOCK_NUM (next
)) ==
1360 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
1361 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
1362 && load_insn_bb
!= INSN_BB (next
)
1363 && GET_MODE (link
) == VOIDmode
1365 || find_conditional_protection (next
, load_insn_bb
)))
1369 } /* find_conditional_protection */
1371 /* Returns 1 if the same insn1 that participates in the computation
1372 of load_insn's address is feeding a conditional branch that is
1373 guarding on load_insn. This is true if we find a the two DEF-USE
1375 insn1 -> ... -> conditional-branch
1376 insn1 -> ... -> load_insn,
1377 and if a flow path exist:
1378 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1379 and if insn1 is on the path
1380 region-entry -> ... -> bb_trg -> ... load_insn.
1382 Locate insn1 by climbing on LOG_LINKS from load_insn.
1383 Locate the branch by following INSN_DEPEND from insn1. */
1386 is_conditionally_protected (rtx load_insn
, int bb_src
, int bb_trg
)
1390 for (link
= LOG_LINKS (load_insn
); link
; link
= XEXP (link
, 1))
1392 rtx insn1
= XEXP (link
, 0);
1394 /* Must be a DEF-USE dependence upon non-branch. */
1395 if (GET_MODE (link
) != VOIDmode
1399 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1400 if (INSN_BB (insn1
) == bb_src
1401 || (CONTAINING_RGN (BLOCK_NUM (insn1
))
1402 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
1403 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
1404 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
1407 /* Now search for the conditional-branch. */
1408 if (find_conditional_protection (insn1
, bb_src
))
1411 /* Recursive step: search another insn1, "above" current insn1. */
1412 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
1415 /* The chain does not exist. */
1417 } /* is_conditionally_protected */
1419 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1420 load_insn can move speculatively from bb_src to bb_trg. All the
1421 following must hold:
1423 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1424 (2) load_insn and load1 have a def-use dependence upon
1425 the same insn 'insn1'.
1426 (3) either load2 is in bb_trg, or:
1427 - there's only one split-block, and
1428 - load1 is on the escape path, and
1430 From all these we can conclude that the two loads access memory
1431 addresses that differ at most by a constant, and hence if moving
1432 load_insn would cause an exception, it would have been caused by
1436 is_pfree (rtx load_insn
, int bb_src
, int bb_trg
)
1439 candidate
*candp
= candidate_table
+ bb_src
;
1441 if (candp
->split_bbs
.nr_members
!= 1)
1442 /* Must have exactly one escape block. */
1445 for (back_link
= LOG_LINKS (load_insn
);
1446 back_link
; back_link
= XEXP (back_link
, 1))
1448 rtx insn1
= XEXP (back_link
, 0);
1450 if (GET_MODE (back_link
) == VOIDmode
)
1452 /* Found a DEF-USE dependence (insn1, load_insn). */
1455 for (fore_link
= INSN_DEPEND (insn1
);
1456 fore_link
; fore_link
= XEXP (fore_link
, 1))
1458 rtx insn2
= XEXP (fore_link
, 0);
1459 if (GET_MODE (fore_link
) == VOIDmode
)
1461 /* Found a DEF-USE dependence (insn1, insn2). */
1462 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
1463 /* insn2 not guaranteed to be a 1 base reg load. */
1466 if (INSN_BB (insn2
) == bb_trg
)
1467 /* insn2 is the similar load, in the target block. */
1470 if (*(candp
->split_bbs
.first_member
) == BLOCK_FOR_INSN (insn2
))
1471 /* insn2 is a similar load, in a split-block. */
1478 /* Couldn't find a similar load. */
1482 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1483 a load moved speculatively, or if load_insn is protected by
1484 a compare on load_insn's address). */
1487 is_prisky (rtx load_insn
, int bb_src
, int bb_trg
)
1489 if (FED_BY_SPEC_LOAD (load_insn
))
1492 if (LOG_LINKS (load_insn
) == NULL
)
1493 /* Dependence may 'hide' out of the region. */
1496 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
1502 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
1503 Return 1 if insn is exception-free (and the motion is valid)
1507 is_exception_free (rtx insn
, int bb_src
, int bb_trg
)
1509 int insn_class
= haifa_classify_insn (insn
);
1511 /* Handle non-load insns. */
1522 if (!flag_schedule_speculative_load
)
1524 IS_LOAD_INSN (insn
) = 1;
1531 case PFREE_CANDIDATE
:
1532 if (is_pfree (insn
, bb_src
, bb_trg
))
1534 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
1535 case PRISKY_CANDIDATE
:
1536 if (!flag_schedule_speculative_load_dangerous
1537 || is_prisky (insn
, bb_src
, bb_trg
))
1543 return flag_schedule_speculative_load_dangerous
;
1546 /* The number of insns from the current block scheduled so far. */
1547 static int sched_target_n_insns
;
1548 /* The number of insns from the current block to be scheduled in total. */
1549 static int target_n_insns
;
1550 /* The number of insns from the entire region scheduled so far. */
1551 static int sched_n_insns
;
1552 /* Nonzero if the last scheduled insn was a jump. */
1553 static int last_was_jump
;
1555 /* Implementations of the sched_info functions for region scheduling. */
1556 static void init_ready_list (struct ready_list
*);
1557 static int can_schedule_ready_p (rtx
);
1558 static int new_ready (rtx
);
1559 static int schedule_more_p (void);
1560 static const char *rgn_print_insn (rtx
, int);
1561 static int rgn_rank (rtx
, rtx
);
1562 static int contributes_to_priority (rtx
, rtx
);
1563 static void compute_jump_reg_dependencies (rtx
, regset
, regset
, regset
);
1565 /* Return nonzero if there are more insns that should be scheduled. */
1568 schedule_more_p (void)
1570 return ! last_was_jump
&& sched_target_n_insns
< target_n_insns
;
1573 /* Add all insns that are initially ready to the ready list READY. Called
1574 once before scheduling a set of insns. */
1577 init_ready_list (struct ready_list
*ready
)
1579 rtx prev_head
= current_sched_info
->prev_head
;
1580 rtx next_tail
= current_sched_info
->next_tail
;
1585 sched_target_n_insns
= 0;
1589 /* Print debugging information. */
1590 if (sched_verbose
>= 5)
1591 debug_dependencies ();
1593 /* Prepare current target block info. */
1594 if (current_nr_blocks
> 1)
1596 candidate_table
= xmalloc (current_nr_blocks
* sizeof (candidate
));
1599 /* bblst_table holds split blocks and update blocks for each block after
1600 the current one in the region. split blocks and update blocks are
1601 the TO blocks of region edges, so there can be at most rgn_nr_edges
1603 bblst_size
= (current_nr_blocks
- target_bb
) * rgn_nr_edges
;
1604 bblst_table
= xmalloc (bblst_size
* sizeof (basic_block
));
1607 edgelst_table
= xmalloc (rgn_nr_edges
* sizeof (edge
));
1609 compute_trg_info (target_bb
);
1612 /* Initialize ready list with all 'ready' insns in target block.
1613 Count number of insns in the target block being scheduled. */
1614 for (insn
= NEXT_INSN (prev_head
); insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1616 if (INSN_DEP_COUNT (insn
) == 0)
1618 ready_add (ready
, insn
);
1620 if (targetm
.sched
.adjust_priority
)
1621 INSN_PRIORITY (insn
) =
1622 targetm
.sched
.adjust_priority (insn
, INSN_PRIORITY (insn
));
1627 /* Add to ready list all 'ready' insns in valid source blocks.
1628 For speculative insns, check-live, exception-free, and
1630 for (bb_src
= target_bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
1631 if (IS_VALID (bb_src
))
1637 get_block_head_tail (BB_TO_BLOCK (bb_src
), &head
, &tail
);
1638 src_next_tail
= NEXT_INSN (tail
);
1641 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
1643 if (! INSN_P (insn
))
1646 if (!CANT_MOVE (insn
)
1647 && (!IS_SPECULATIVE_INSN (insn
)
1648 || ((recog_memoized (insn
) < 0
1649 || min_insn_conflict_delay (curr_state
,
1651 && check_live (insn
, bb_src
)
1652 && is_exception_free (insn
, bb_src
, target_bb
))))
1653 if (INSN_DEP_COUNT (insn
) == 0)
1655 ready_add (ready
, insn
);
1657 if (targetm
.sched
.adjust_priority
)
1658 INSN_PRIORITY (insn
) =
1659 targetm
.sched
.adjust_priority (insn
, INSN_PRIORITY (insn
));
1665 /* Called after taking INSN from the ready list. Returns nonzero if this
1666 insn can be scheduled, nonzero if we should silently discard it. */
1669 can_schedule_ready_p (rtx insn
)
1674 /* An interblock motion? */
1675 if (INSN_BB (insn
) != target_bb
)
1679 if (IS_SPECULATIVE_INSN (insn
))
1681 if (!check_live (insn
, INSN_BB (insn
)))
1683 update_live (insn
, INSN_BB (insn
));
1685 /* For speculative load, mark insns fed by it. */
1686 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
1687 set_spec_fed (insn
);
1693 /* Update source block boundaries. */
1694 b1
= BLOCK_FOR_INSN (insn
);
1695 if (insn
== BB_HEAD (b1
) && insn
== BB_END (b1
))
1697 /* We moved all the insns in the basic block.
1698 Emit a note after the last insn and update the
1699 begin/end boundaries to point to the note. */
1700 rtx note
= emit_note_after (NOTE_INSN_DELETED
, insn
);
1701 BB_HEAD (b1
) = note
;
1704 else if (insn
== BB_END (b1
))
1706 /* We took insns from the end of the basic block,
1707 so update the end of block boundary so that it
1708 points to the first insn we did not move. */
1709 BB_END (b1
) = PREV_INSN (insn
);
1711 else if (insn
== BB_HEAD (b1
))
1713 /* We took insns from the start of the basic block,
1714 so update the start of block boundary so that
1715 it points to the first insn we did not move. */
1716 BB_HEAD (b1
) = NEXT_INSN (insn
);
1721 /* In block motion. */
1722 sched_target_n_insns
++;
1729 /* Called after INSN has all its dependencies resolved. Return nonzero
1730 if it should be moved to the ready list or the queue, or zero if we
1731 should silently discard it. */
1733 new_ready (rtx next
)
1735 /* For speculative insns, before inserting to ready/queue,
1736 check live, exception-free, and issue-delay. */
1737 if (INSN_BB (next
) != target_bb
1738 && (!IS_VALID (INSN_BB (next
))
1740 || (IS_SPECULATIVE_INSN (next
)
1741 && ((recog_memoized (next
) >= 0
1742 && min_insn_conflict_delay (curr_state
, next
, next
) > 3)
1743 || !check_live (next
, INSN_BB (next
))
1744 || !is_exception_free (next
, INSN_BB (next
), target_bb
)))))
1749 /* Return a string that contains the insn uid and optionally anything else
1750 necessary to identify this insn in an output. It's valid to use a
1751 static buffer for this. The ALIGNED parameter should cause the string
1752 to be formatted so that multiple output lines will line up nicely. */
1755 rgn_print_insn (rtx insn
, int aligned
)
1757 static char tmp
[80];
1760 sprintf (tmp
, "b%3d: i%4d", INSN_BB (insn
), INSN_UID (insn
));
1763 if (current_nr_blocks
> 1 && INSN_BB (insn
) != target_bb
)
1764 sprintf (tmp
, "%d/b%d", INSN_UID (insn
), INSN_BB (insn
));
1766 sprintf (tmp
, "%d", INSN_UID (insn
));
1771 /* Compare priority of two insns. Return a positive number if the second
1772 insn is to be preferred for scheduling, and a negative one if the first
1773 is to be preferred. Zero if they are equally good. */
1776 rgn_rank (rtx insn1
, rtx insn2
)
1778 /* Some comparison make sense in interblock scheduling only. */
1779 if (INSN_BB (insn1
) != INSN_BB (insn2
))
1781 int spec_val
, prob_val
;
1783 /* Prefer an inblock motion on an interblock motion. */
1784 if ((INSN_BB (insn2
) == target_bb
) && (INSN_BB (insn1
) != target_bb
))
1786 if ((INSN_BB (insn1
) == target_bb
) && (INSN_BB (insn2
) != target_bb
))
1789 /* Prefer a useful motion on a speculative one. */
1790 spec_val
= IS_SPECULATIVE_INSN (insn1
) - IS_SPECULATIVE_INSN (insn2
);
1794 /* Prefer a more probable (speculative) insn. */
1795 prob_val
= INSN_PROBABILITY (insn2
) - INSN_PROBABILITY (insn1
);
1802 /* NEXT is an instruction that depends on INSN (a backward dependence);
1803 return nonzero if we should include this dependence in priority
1807 contributes_to_priority (rtx next
, rtx insn
)
1809 return BLOCK_NUM (next
) == BLOCK_NUM (insn
);
1812 /* INSN is a JUMP_INSN, COND_SET is the set of registers that are
1813 conditionally set before INSN. Store the set of registers that
1814 must be considered as used by this jump in USED and that of
1815 registers that must be considered as set in SET. */
1818 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
1819 regset cond_exec ATTRIBUTE_UNUSED
,
1820 regset used ATTRIBUTE_UNUSED
,
1821 regset set ATTRIBUTE_UNUSED
)
1823 /* Nothing to do here, since we postprocess jumps in
1824 add_branch_dependences. */
1827 /* Used in schedule_insns to initialize current_sched_info for scheduling
1828 regions (or single basic blocks). */
1830 static struct sched_info region_sched_info
=
1833 can_schedule_ready_p
,
1838 contributes_to_priority
,
1839 compute_jump_reg_dependencies
,
1846 /* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register. */
1849 sets_likely_spilled (rtx pat
)
1852 note_stores (pat
, sets_likely_spilled_1
, &ret
);
1857 sets_likely_spilled_1 (rtx x
, rtx pat
, void *data
)
1859 bool *ret
= (bool *) data
;
1861 if (GET_CODE (pat
) == SET
1863 && REGNO (x
) < FIRST_PSEUDO_REGISTER
1864 && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x
))))
1868 /* Add dependences so that branches are scheduled to run last in their
1872 add_branch_dependences (rtx head
, rtx tail
)
1876 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
1877 that can throw exceptions, force them to remain in order at the end of
1878 the block by adding dependencies and giving the last a high priority.
1879 There may be notes present, and prev_head may also be a note.
1881 Branches must obviously remain at the end. Calls should remain at the
1882 end since moving them results in worse register allocation. Uses remain
1883 at the end to ensure proper register allocation.
1885 cc0 setters remain at the end because they can't be moved away from
1888 Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values)
1889 are not moved before reload because we can wind up with register
1890 allocation failures. */
1894 while (CALL_P (insn
)
1896 || (NONJUMP_INSN_P (insn
)
1897 && (GET_CODE (PATTERN (insn
)) == USE
1898 || GET_CODE (PATTERN (insn
)) == CLOBBER
1899 || can_throw_internal (insn
)
1901 || sets_cc0_p (PATTERN (insn
))
1903 || (!reload_completed
1904 && sets_likely_spilled (PATTERN (insn
)))))
1909 if (last
!= 0 && !find_insn_list (insn
, LOG_LINKS (last
)))
1911 add_dependence (last
, insn
, REG_DEP_ANTI
);
1912 INSN_REF_COUNT (insn
)++;
1915 CANT_MOVE (insn
) = 1;
1920 /* Don't overrun the bounds of the basic block. */
1924 insn
= PREV_INSN (insn
);
1927 /* Make sure these insns are scheduled last in their block. */
1930 while (insn
!= head
)
1932 insn
= prev_nonnote_insn (insn
);
1934 if (INSN_REF_COUNT (insn
) != 0)
1937 add_dependence (last
, insn
, REG_DEP_ANTI
);
1938 INSN_REF_COUNT (insn
) = 1;
1942 /* Data structures for the computation of data dependences in a regions. We
1943 keep one `deps' structure for every basic block. Before analyzing the
1944 data dependences for a bb, its variables are initialized as a function of
1945 the variables of its predecessors. When the analysis for a bb completes,
1946 we save the contents to the corresponding bb_deps[bb] variable. */
1948 static struct deps
*bb_deps
;
1950 /* Duplicate the INSN_LIST elements of COPY and prepend them to OLD. */
1953 concat_INSN_LIST (rtx copy
, rtx old
)
1956 for (; copy
; copy
= XEXP (copy
, 1))
1957 new = alloc_INSN_LIST (XEXP (copy
, 0), new);
1962 concat_insn_mem_list (rtx copy_insns
, rtx copy_mems
, rtx
*old_insns_p
,
1965 rtx new_insns
= *old_insns_p
;
1966 rtx new_mems
= *old_mems_p
;
1970 new_insns
= alloc_INSN_LIST (XEXP (copy_insns
, 0), new_insns
);
1971 new_mems
= alloc_EXPR_LIST (VOIDmode
, XEXP (copy_mems
, 0), new_mems
);
1972 copy_insns
= XEXP (copy_insns
, 1);
1973 copy_mems
= XEXP (copy_mems
, 1);
1976 *old_insns_p
= new_insns
;
1977 *old_mems_p
= new_mems
;
1980 /* After computing the dependencies for block BB, propagate the dependencies
1981 found in TMP_DEPS to the successors of the block. */
1983 propagate_deps (int bb
, struct deps
*pred_deps
)
1985 basic_block block
= BASIC_BLOCK (BB_TO_BLOCK (bb
));
1989 /* bb's structures are inherited by its successors. */
1990 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1992 struct deps
*succ_deps
;
1994 reg_set_iterator rsi
;
1996 /* Only bbs "below" bb, in the same region, are interesting. */
1997 if (e
->dest
== EXIT_BLOCK_PTR
1998 || CONTAINING_RGN (block
->index
) != CONTAINING_RGN (e
->dest
->index
)
1999 || BLOCK_TO_BB (e
->dest
->index
) <= bb
)
2002 succ_deps
= bb_deps
+ BLOCK_TO_BB (e
->dest
->index
);
2004 /* The reg_last lists are inherited by successor. */
2005 EXECUTE_IF_SET_IN_REG_SET (&pred_deps
->reg_last_in_use
, 0, reg
, rsi
)
2007 struct deps_reg
*pred_rl
= &pred_deps
->reg_last
[reg
];
2008 struct deps_reg
*succ_rl
= &succ_deps
->reg_last
[reg
];
2010 succ_rl
->uses
= concat_INSN_LIST (pred_rl
->uses
, succ_rl
->uses
);
2011 succ_rl
->sets
= concat_INSN_LIST (pred_rl
->sets
, succ_rl
->sets
);
2012 succ_rl
->clobbers
= concat_INSN_LIST (pred_rl
->clobbers
,
2014 succ_rl
->uses_length
+= pred_rl
->uses_length
;
2015 succ_rl
->clobbers_length
+= pred_rl
->clobbers_length
;
2017 IOR_REG_SET (&succ_deps
->reg_last_in_use
, &pred_deps
->reg_last_in_use
);
2019 /* Mem read/write lists are inherited by successor. */
2020 concat_insn_mem_list (pred_deps
->pending_read_insns
,
2021 pred_deps
->pending_read_mems
,
2022 &succ_deps
->pending_read_insns
,
2023 &succ_deps
->pending_read_mems
);
2024 concat_insn_mem_list (pred_deps
->pending_write_insns
,
2025 pred_deps
->pending_write_mems
,
2026 &succ_deps
->pending_write_insns
,
2027 &succ_deps
->pending_write_mems
);
2029 succ_deps
->last_pending_memory_flush
2030 = concat_INSN_LIST (pred_deps
->last_pending_memory_flush
,
2031 succ_deps
->last_pending_memory_flush
);
2033 succ_deps
->pending_lists_length
+= pred_deps
->pending_lists_length
;
2034 succ_deps
->pending_flush_length
+= pred_deps
->pending_flush_length
;
2036 /* last_function_call is inherited by successor. */
2037 succ_deps
->last_function_call
2038 = concat_INSN_LIST (pred_deps
->last_function_call
,
2039 succ_deps
->last_function_call
);
2041 /* sched_before_next_call is inherited by successor. */
2042 succ_deps
->sched_before_next_call
2043 = concat_INSN_LIST (pred_deps
->sched_before_next_call
,
2044 succ_deps
->sched_before_next_call
);
2047 /* These lists should point to the right place, for correct
2049 bb_deps
[bb
].pending_read_insns
= pred_deps
->pending_read_insns
;
2050 bb_deps
[bb
].pending_read_mems
= pred_deps
->pending_read_mems
;
2051 bb_deps
[bb
].pending_write_insns
= pred_deps
->pending_write_insns
;
2052 bb_deps
[bb
].pending_write_mems
= pred_deps
->pending_write_mems
;
2054 /* Can't allow these to be freed twice. */
2055 pred_deps
->pending_read_insns
= 0;
2056 pred_deps
->pending_read_mems
= 0;
2057 pred_deps
->pending_write_insns
= 0;
2058 pred_deps
->pending_write_mems
= 0;
2061 /* Compute backward dependences inside bb. In a multiple blocks region:
2062 (1) a bb is analyzed after its predecessors, and (2) the lists in
2063 effect at the end of bb (after analyzing for bb) are inherited by
2066 Specifically for reg-reg data dependences, the block insns are
2067 scanned by sched_analyze () top-to-bottom. Two lists are
2068 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2069 and reg_last[].uses for register USEs.
2071 When analysis is completed for bb, we update for its successors:
2072 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2073 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2075 The mechanism for computing mem-mem data dependence is very
2076 similar, and the result is interblock dependences in the region. */
2079 compute_block_backward_dependences (int bb
)
2082 struct deps tmp_deps
;
2084 tmp_deps
= bb_deps
[bb
];
2086 /* Do the analysis for this block. */
2087 get_block_head_tail (BB_TO_BLOCK (bb
), &head
, &tail
);
2088 sched_analyze (&tmp_deps
, head
, tail
);
2089 add_branch_dependences (head
, tail
);
2091 if (current_nr_blocks
> 1)
2092 propagate_deps (bb
, &tmp_deps
);
2094 /* Free up the INSN_LISTs. */
2095 free_deps (&tmp_deps
);
2098 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2099 them to the unused_*_list variables, so that they can be reused. */
2102 free_pending_lists (void)
2106 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2108 free_INSN_LIST_list (&bb_deps
[bb
].pending_read_insns
);
2109 free_INSN_LIST_list (&bb_deps
[bb
].pending_write_insns
);
2110 free_EXPR_LIST_list (&bb_deps
[bb
].pending_read_mems
);
2111 free_EXPR_LIST_list (&bb_deps
[bb
].pending_write_mems
);
2115 /* Print dependences for debugging, callable from debugger. */
2118 debug_dependencies (void)
2122 fprintf (sched_dump
, ";; --------------- forward dependences: ------------ \n");
2123 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2129 get_block_head_tail (BB_TO_BLOCK (bb
), &head
, &tail
);
2130 next_tail
= NEXT_INSN (tail
);
2131 fprintf (sched_dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
2132 BB_TO_BLOCK (bb
), bb
);
2134 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2135 "insn", "code", "bb", "dep", "prio", "cost",
2137 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2138 "----", "----", "--", "---", "----", "----",
2141 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2145 if (! INSN_P (insn
))
2148 fprintf (sched_dump
, ";; %6d ", INSN_UID (insn
));
2151 n
= NOTE_LINE_NUMBER (insn
);
2153 fprintf (sched_dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
2156 expanded_location xloc
;
2157 NOTE_EXPANDED_LOCATION (xloc
, insn
);
2158 fprintf (sched_dump
, "line %d, file %s\n",
2159 xloc
.line
, xloc
.file
);
2163 fprintf (sched_dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
2167 fprintf (sched_dump
,
2168 ";; %s%5d%6d%6d%6d%6d%6d ",
2169 (SCHED_GROUP_P (insn
) ? "+" : " "),
2173 INSN_DEP_COUNT (insn
),
2174 INSN_PRIORITY (insn
),
2175 insn_cost (insn
, 0, 0));
2177 if (recog_memoized (insn
) < 0)
2178 fprintf (sched_dump
, "nothing");
2180 print_reservation (sched_dump
, insn
);
2182 fprintf (sched_dump
, "\t: ");
2183 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
2184 fprintf (sched_dump
, "%d ", INSN_UID (XEXP (link
, 0)));
2185 fprintf (sched_dump
, "\n");
2188 fprintf (sched_dump
, "\n");
2191 /* Returns true if all the basic blocks of the current region have
2192 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
2194 sched_is_disabled_for_current_region_p (void)
2198 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2199 if (!(BASIC_BLOCK (BB_TO_BLOCK (bb
))->flags
& BB_DISABLE_SCHEDULE
))
2205 /* Schedule a region. A region is either an inner loop, a loop-free
2206 subroutine, or a single basic block. Each bb in the region is
2207 scheduled after its flow predecessors. */
2210 schedule_region (int rgn
)
2216 int rgn_n_insns
= 0;
2217 int sched_rgn_n_insns
= 0;
2219 /* Set variables for the current region. */
2220 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
2221 current_blocks
= RGN_BLOCKS (rgn
);
2223 /* Don't schedule region that is marked by
2224 NOTE_DISABLE_SCHED_OF_BLOCK. */
2225 if (sched_is_disabled_for_current_region_p ())
2228 init_deps_global ();
2230 /* Initializations for region data dependence analysis. */
2231 bb_deps
= xmalloc (sizeof (struct deps
) * current_nr_blocks
);
2232 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2233 init_deps (bb_deps
+ bb
);
2235 /* Compute LOG_LINKS. */
2236 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2237 compute_block_backward_dependences (bb
);
2239 /* Compute INSN_DEPEND. */
2240 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
2243 get_block_head_tail (BB_TO_BLOCK (bb
), &head
, &tail
);
2245 compute_forward_dependences (head
, tail
);
2247 if (targetm
.sched
.dependencies_evaluation_hook
)
2248 targetm
.sched
.dependencies_evaluation_hook (head
, tail
);
2252 /* Set priorities. */
2253 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2256 get_block_head_tail (BB_TO_BLOCK (bb
), &head
, &tail
);
2258 rgn_n_insns
+= set_priorities (head
, tail
);
2261 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
2262 if (current_nr_blocks
> 1)
2264 prob
= xmalloc ((current_nr_blocks
) * sizeof (float));
2266 dom
= sbitmap_vector_alloc (current_nr_blocks
, current_nr_blocks
);
2267 sbitmap_vector_zero (dom
, current_nr_blocks
);
2269 /* Use ->aux to implement EDGE_TO_BIT mapping. */
2273 if (CONTAINING_RGN (block
->index
) != rgn
)
2275 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2276 SET_EDGE_TO_BIT (e
, rgn_nr_edges
++);
2279 rgn_edges
= xmalloc (rgn_nr_edges
* sizeof (edge
));
2283 if (CONTAINING_RGN (block
->index
) != rgn
)
2285 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2286 rgn_edges
[rgn_nr_edges
++] = e
;
2290 pot_split
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
2291 sbitmap_vector_zero (pot_split
, current_nr_blocks
);
2292 ancestor_edges
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
2293 sbitmap_vector_zero (ancestor_edges
, current_nr_blocks
);
2295 /* Compute probabilities, dominators, split_edges. */
2296 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2297 compute_dom_prob_ps (bb
);
2300 /* Now we can schedule all blocks. */
2301 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2304 int b
= BB_TO_BLOCK (bb
);
2306 get_block_head_tail (b
, &head
, &tail
);
2308 if (no_real_insns_p (head
, tail
))
2311 current_sched_info
->prev_head
= PREV_INSN (head
);
2312 current_sched_info
->next_tail
= NEXT_INSN (tail
);
2314 if (write_symbols
!= NO_DEBUG
)
2316 save_line_notes (b
, head
, tail
);
2317 rm_line_notes (head
, tail
);
2320 /* rm_other_notes only removes notes which are _inside_ the
2321 block---that is, it won't remove notes before the first real insn
2322 or after the last real insn of the block. So if the first insn
2323 has a REG_SAVE_NOTE which would otherwise be emitted before the
2324 insn, it is redundant with the note before the start of the
2325 block, and so we have to take it out. */
2330 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
2331 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
2332 remove_note (head
, note
);
2335 /* Remove remaining note insns from the block, save them in
2336 note_list. These notes are restored at the end of
2337 schedule_block (). */
2338 rm_other_notes (head
, tail
);
2342 current_sched_info
->queue_must_finish_empty
2343 = current_nr_blocks
> 1 && !flag_schedule_interblock
;
2345 schedule_block (b
, rgn_n_insns
);
2346 sched_rgn_n_insns
+= sched_n_insns
;
2348 /* Update target block boundaries. */
2349 if (head
== BB_HEAD (BASIC_BLOCK (b
)))
2350 BB_HEAD (BASIC_BLOCK (b
)) = current_sched_info
->head
;
2351 if (tail
== BB_END (BASIC_BLOCK (b
)))
2352 BB_END (BASIC_BLOCK (b
)) = current_sched_info
->tail
;
2355 if (current_nr_blocks
> 1)
2357 free (candidate_table
);
2359 free (edgelst_table
);
2363 /* Sanity check: verify that all region insns were scheduled. */
2364 gcc_assert (sched_rgn_n_insns
== rgn_n_insns
);
2366 /* Restore line notes. */
2367 if (write_symbols
!= NO_DEBUG
)
2369 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2372 get_block_head_tail (BB_TO_BLOCK (bb
), &head
, &tail
);
2373 restore_line_notes (head
, tail
);
2377 /* Done with this region. */
2378 free_pending_lists ();
2380 finish_deps_global ();
2384 if (current_nr_blocks
> 1)
2386 /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
2389 if (CONTAINING_RGN (block
->index
) != rgn
)
2391 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2396 sbitmap_vector_free (dom
);
2397 sbitmap_vector_free (pot_split
);
2398 sbitmap_vector_free (ancestor_edges
);
2403 /* Indexed by region, holds the number of death notes found in that region.
2404 Used for consistency checks. */
2405 static int *deaths_in_region
;
2407 /* Initialize data structures for region scheduling. */
2416 rgn_table
= xmalloc ((n_basic_blocks
) * sizeof (region
));
2417 rgn_bb_table
= xmalloc ((n_basic_blocks
) * sizeof (int));
2418 block_to_bb
= xmalloc ((last_basic_block
) * sizeof (int));
2419 containing_rgn
= xmalloc ((last_basic_block
) * sizeof (int));
2421 /* Compute regions for scheduling. */
2422 if (reload_completed
2423 || n_basic_blocks
== 1
2424 || !flag_schedule_interblock
2425 || is_cfg_nonregular ())
2427 find_single_block_region ();
2431 /* Compute the dominators and post dominators. */
2432 calculate_dominance_info (CDI_DOMINATORS
);
2437 if (sched_verbose
>= 3)
2440 /* For now. This will move as more and more of haifa is converted
2441 to using the cfg code in flow.c. */
2442 free_dominance_info (CDI_DOMINATORS
);
2446 if (CHECK_DEAD_NOTES
)
2448 blocks
= sbitmap_alloc (last_basic_block
);
2449 deaths_in_region
= xmalloc (sizeof (int) * nr_regions
);
2450 /* Remove all death notes from the subroutine. */
2451 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
2455 sbitmap_zero (blocks
);
2456 for (b
= RGN_NR_BLOCKS (rgn
) - 1; b
>= 0; --b
)
2457 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
) + b
]);
2459 deaths_in_region
[rgn
] = count_or_remove_death_notes (blocks
, 1);
2461 sbitmap_free (blocks
);
2464 count_or_remove_death_notes (NULL
, 1);
2467 /* The one entry point in this file. DUMP_FILE is the dump file for
2471 schedule_insns (FILE *dump_file
)
2473 sbitmap large_region_blocks
, blocks
;
2475 int any_large_regions
;
2478 /* Taking care of this degenerate case makes the rest of
2479 this code simpler. */
2480 if (n_basic_blocks
== 0)
2486 sched_init (dump_file
);
2490 current_sched_info
= ®ion_sched_info
;
2492 /* Schedule every region in the subroutine. */
2493 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
2494 schedule_region (rgn
);
2496 /* Update life analysis for the subroutine. Do single block regions
2497 first so that we can verify that live_at_start didn't change. Then
2498 do all other blocks. */
2499 /* ??? There is an outside possibility that update_life_info, or more
2500 to the point propagate_block, could get called with nonzero flags
2501 more than once for one basic block. This would be kinda bad if it
2502 were to happen, since REG_INFO would be accumulated twice for the
2503 block, and we'd have twice the REG_DEAD notes.
2505 I'm fairly certain that this _shouldn't_ happen, since I don't think
2506 that live_at_start should change at region heads. Not sure what the
2507 best way to test for this kind of thing... */
2509 allocate_reg_life_data ();
2510 compute_bb_for_insn ();
2512 any_large_regions
= 0;
2513 large_region_blocks
= sbitmap_alloc (last_basic_block
);
2514 sbitmap_zero (large_region_blocks
);
2516 SET_BIT (large_region_blocks
, bb
->index
);
2518 blocks
= sbitmap_alloc (last_basic_block
);
2519 sbitmap_zero (blocks
);
2521 /* Update life information. For regions consisting of multiple blocks
2522 we've possibly done interblock scheduling that affects global liveness.
2523 For regions consisting of single blocks we need to do only local
2525 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
2526 if (RGN_NR_BLOCKS (rgn
) > 1)
2527 any_large_regions
= 1;
2530 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
2531 RESET_BIT (large_region_blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
2534 /* Don't update reg info after reload, since that affects
2535 regs_ever_live, which should not change after reload. */
2536 update_life_info (blocks
, UPDATE_LIFE_LOCAL
,
2537 (reload_completed
? PROP_DEATH_NOTES
2538 : PROP_DEATH_NOTES
| PROP_REG_INFO
));
2539 if (any_large_regions
)
2541 update_life_info (large_region_blocks
, UPDATE_LIFE_GLOBAL
,
2542 PROP_DEATH_NOTES
| PROP_REG_INFO
);
2545 if (CHECK_DEAD_NOTES
)
2547 /* Verify the counts of basic block notes in single the basic block
2549 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
2550 if (RGN_NR_BLOCKS (rgn
) == 1)
2552 sbitmap_zero (blocks
);
2553 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
2555 gcc_assert (deaths_in_region
[rgn
]
2556 == count_or_remove_death_notes (blocks
, 0));
2558 free (deaths_in_region
);
2561 /* Reposition the prologue and epilogue notes in case we moved the
2562 prologue/epilogue insns. */
2563 if (reload_completed
)
2564 reposition_prologue_and_epilogue_notes (get_insns ());
2566 /* Delete redundant line notes. */
2567 if (write_symbols
!= NO_DEBUG
)
2568 rm_redundant_line_notes ();
2572 if (reload_completed
== 0 && flag_schedule_interblock
)
2574 fprintf (sched_dump
,
2575 "\n;; Procedure interblock/speculative motions == %d/%d \n",
2579 gcc_assert (nr_inter
<= 0);
2580 fprintf (sched_dump
, "\n\n");
2585 free (rgn_bb_table
);
2587 free (containing_rgn
);
2591 sbitmap_free (blocks
);
2592 sbitmap_free (large_region_blocks
);