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)
295 /* If we have a label that could be the target of a nonlocal goto, then
296 the cfg is not well structured. */
297 if (nonlocal_goto_handler_labels
)
300 /* If we have any forced labels, then the cfg is not well structured. */
304 /* If we have exception handlers, then we consider the cfg not well
305 structured. ?!? We should be able to handle this now that flow.c
306 computes an accurate cfg for EH. */
307 if (current_function_has_exception_handlers ())
310 /* If we have non-jumping insns which refer to labels, then we consider
311 the cfg not well structured. */
313 FOR_BB_INSNS (b
, insn
)
315 /* Check for labels referred by non-jump insns. */
316 if (NONJUMP_INSN_P (insn
) || CALL_P (insn
))
318 rtx note
= find_reg_note (insn
, REG_LABEL
, NULL_RTX
);
320 && ! (JUMP_P (NEXT_INSN (insn
))
321 && find_reg_note (NEXT_INSN (insn
), REG_LABEL
,
325 /* If this function has a computed jump, then we consider the cfg
326 not well structured. */
327 else if (JUMP_P (insn
) && computed_jump_p (insn
))
331 /* Unreachable loops with more than one basic block are detected
332 during the DFS traversal in find_rgns.
334 Unreachable loops with a single block are detected here. This
335 test is redundant with the one in find_rgns, but it's much
336 cheaper to go ahead and catch the trivial case here. */
339 if (EDGE_COUNT (b
->preds
) == 0
340 || (single_pred_p (b
)
341 && single_pred (b
) == b
))
345 /* All the tests passed. Consider the cfg well structured. */
349 /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */
352 extract_edgelst (sbitmap set
, edgelst
*el
)
355 sbitmap_iterator sbi
;
357 /* edgelst table space is reused in each call to extract_edgelst. */
360 el
->first_member
= &edgelst_table
[edgelst_last
];
363 /* Iterate over each word in the bitset. */
364 EXECUTE_IF_SET_IN_SBITMAP (set
, 0, i
, sbi
)
366 edgelst_table
[edgelst_last
++] = rgn_edges
[i
];
371 /* Functions for the construction of regions. */
373 /* Print the regions, for debugging purposes. Callable from debugger. */
380 fprintf (sched_dump
, "\n;; ------------ REGIONS ----------\n\n");
381 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
383 fprintf (sched_dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
384 rgn_table
[rgn
].rgn_nr_blocks
);
385 fprintf (sched_dump
, ";;\tbb/block: ");
387 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
389 current_blocks
= RGN_BLOCKS (rgn
);
391 gcc_assert (bb
== BLOCK_TO_BB (BB_TO_BLOCK (bb
)));
392 fprintf (sched_dump
, " %d/%d ", bb
, BB_TO_BLOCK (bb
));
395 fprintf (sched_dump
, "\n\n");
399 /* Build a single block region for each basic block in the function.
400 This allows for using the same code for interblock and basic block
404 find_single_block_region (void)
412 rgn_bb_table
[nr_regions
] = bb
->index
;
413 RGN_NR_BLOCKS (nr_regions
) = 1;
414 RGN_BLOCKS (nr_regions
) = nr_regions
;
415 CONTAINING_RGN (bb
->index
) = nr_regions
;
416 BLOCK_TO_BB (bb
->index
) = 0;
421 /* Update number of blocks and the estimate for number of insns
422 in the region. Return true if the region is "too large" for interblock
423 scheduling (compile time considerations). */
426 too_large (int block
, int *num_bbs
, int *num_insns
)
429 (*num_insns
) += (INSN_LUID (BB_END (BASIC_BLOCK (block
)))
430 - INSN_LUID (BB_HEAD (BASIC_BLOCK (block
))));
432 return ((*num_bbs
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS
))
433 || (*num_insns
> PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS
)));
436 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
437 is still an inner loop. Put in max_hdr[blk] the header of the most inner
438 loop containing blk. */
439 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
441 if (max_hdr[blk] == -1) \
442 max_hdr[blk] = hdr; \
443 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
444 RESET_BIT (inner, hdr); \
445 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
447 RESET_BIT (inner,max_hdr[blk]); \
448 max_hdr[blk] = hdr; \
452 /* Find regions for interblock scheduling.
454 A region for scheduling can be:
456 * A loop-free procedure, or
458 * A reducible inner loop, or
460 * A basic block not contained in any other region.
462 ?!? In theory we could build other regions based on extended basic
463 blocks or reverse extended basic blocks. Is it worth the trouble?
465 Loop blocks that form a region are put into the region's block list
466 in topological order.
468 This procedure stores its results into the following global (ick) variables
476 We use dominator relationships to avoid making regions out of non-reducible
479 This procedure needs to be converted to work on pred/succ lists instead
480 of edge tables. That would simplify it somewhat. */
485 int *max_hdr
, *dfs_nr
, *degree
;
487 int node
, child
, loop_head
, i
, head
, tail
;
488 int count
= 0, sp
, idx
= 0;
489 edge_iterator current_edge
;
490 edge_iterator
*stack
;
491 int num_bbs
, num_insns
, unreachable
;
492 int too_large_failure
;
495 /* Note if a block is a natural loop header. */
498 /* Note if a block is a natural inner loop header. */
501 /* Note if a block is in the block queue. */
504 /* Note if a block is in the block queue. */
507 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
508 and a mapping from block to its loop header (if the block is contained
511 Store results in HEADER, INNER, and MAX_HDR respectively, these will
512 be used as inputs to the second traversal.
514 STACK, SP and DFS_NR are only used during the first traversal. */
516 /* Allocate and initialize variables for the first traversal. */
517 max_hdr
= xmalloc (last_basic_block
* sizeof (int));
518 dfs_nr
= xcalloc (last_basic_block
, sizeof (int));
519 stack
= xmalloc (n_edges
* sizeof (edge_iterator
));
521 inner
= sbitmap_alloc (last_basic_block
);
522 sbitmap_ones (inner
);
524 header
= sbitmap_alloc (last_basic_block
);
525 sbitmap_zero (header
);
527 in_queue
= sbitmap_alloc (last_basic_block
);
528 sbitmap_zero (in_queue
);
530 in_stack
= sbitmap_alloc (last_basic_block
);
531 sbitmap_zero (in_stack
);
533 for (i
= 0; i
< last_basic_block
; i
++)
536 #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
537 #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
539 /* DFS traversal to find inner loops in the cfg. */
541 current_edge
= ei_start (single_succ (ENTRY_BLOCK_PTR
)->succs
);
546 if (EDGE_PASSED (current_edge
))
548 /* We have reached a leaf node or a node that was already
549 processed. Pop edges off the stack until we find
550 an edge that has not yet been processed. */
551 while (sp
>= 0 && EDGE_PASSED (current_edge
))
553 /* Pop entry off the stack. */
554 current_edge
= stack
[sp
--];
555 node
= ei_edge (current_edge
)->src
->index
;
556 gcc_assert (node
!= ENTRY_BLOCK
);
557 child
= ei_edge (current_edge
)->dest
->index
;
558 gcc_assert (child
!= EXIT_BLOCK
);
559 RESET_BIT (in_stack
, child
);
560 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
561 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
562 ei_next (¤t_edge
);
565 /* See if have finished the DFS tree traversal. */
566 if (sp
< 0 && EDGE_PASSED (current_edge
))
569 /* Nope, continue the traversal with the popped node. */
573 /* Process a node. */
574 node
= ei_edge (current_edge
)->src
->index
;
575 gcc_assert (node
!= ENTRY_BLOCK
);
576 SET_BIT (in_stack
, node
);
577 dfs_nr
[node
] = ++count
;
579 /* We don't traverse to the exit block. */
580 child
= ei_edge (current_edge
)->dest
->index
;
581 if (child
== EXIT_BLOCK
)
583 SET_EDGE_PASSED (current_edge
);
584 ei_next (¤t_edge
);
588 /* If the successor is in the stack, then we've found a loop.
589 Mark the loop, if it is not a natural loop, then it will
590 be rejected during the second traversal. */
591 if (TEST_BIT (in_stack
, child
))
594 SET_BIT (header
, child
);
595 UPDATE_LOOP_RELATIONS (node
, child
);
596 SET_EDGE_PASSED (current_edge
);
597 ei_next (¤t_edge
);
601 /* If the child was already visited, then there is no need to visit
602 it again. Just update the loop relationships and restart
606 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
607 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
608 SET_EDGE_PASSED (current_edge
);
609 ei_next (¤t_edge
);
613 /* Push an entry on the stack and continue DFS traversal. */
614 stack
[++sp
] = current_edge
;
615 SET_EDGE_PASSED (current_edge
);
616 current_edge
= ei_start (ei_edge (current_edge
)->dest
->succs
);
619 /* Reset ->aux field used by EDGE_PASSED. */
624 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
629 /* Another check for unreachable blocks. The earlier test in
630 is_cfg_nonregular only finds unreachable blocks that do not
633 The DFS traversal will mark every block that is reachable from
634 the entry node by placing a nonzero value in dfs_nr. Thus if
635 dfs_nr is zero for any block, then it must be unreachable. */
638 if (dfs_nr
[bb
->index
] == 0)
644 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
645 to hold degree counts. */
649 degree
[bb
->index
] = EDGE_COUNT (bb
->preds
);
651 /* Do not perform region scheduling if there are any unreachable
660 /* Second traversal:find reducible inner loops and topologically sort
661 block of each region. */
663 queue
= xmalloc (n_basic_blocks
* sizeof (int));
665 /* Find blocks which are inner loop headers. We still have non-reducible
666 loops to consider at this point. */
669 if (TEST_BIT (header
, bb
->index
) && TEST_BIT (inner
, bb
->index
))
675 /* Now check that the loop is reducible. We do this separate
676 from finding inner loops so that we do not find a reducible
677 loop which contains an inner non-reducible loop.
679 A simple way to find reducible/natural loops is to verify
680 that each block in the loop is dominated by the loop
683 If there exists a block that is not dominated by the loop
684 header, then the block is reachable from outside the loop
685 and thus the loop is not a natural loop. */
688 /* First identify blocks in the loop, except for the loop
690 if (bb
->index
== max_hdr
[jbb
->index
] && bb
!= jbb
)
692 /* Now verify that the block is dominated by the loop
694 if (!dominated_by_p (CDI_DOMINATORS
, jbb
, bb
))
699 /* If we exited the loop early, then I is the header of
700 a non-reducible loop and we should quit processing it
702 if (jbb
!= EXIT_BLOCK_PTR
)
705 /* I is a header of an inner loop, or block 0 in a subroutine
706 with no loops at all. */
708 too_large_failure
= 0;
709 loop_head
= max_hdr
[bb
->index
];
711 /* Decrease degree of all I's successors for topological
713 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
714 if (e
->dest
!= EXIT_BLOCK_PTR
)
715 --degree
[e
->dest
->index
];
717 /* Estimate # insns, and count # blocks in the region. */
719 num_insns
= (INSN_LUID (BB_END (bb
))
720 - INSN_LUID (BB_HEAD (bb
)));
722 /* Find all loop latches (blocks with back edges to the loop
723 header) or all the leaf blocks in the cfg has no loops.
725 Place those blocks into the queue. */
729 /* Leaf nodes have only a single successor which must
731 if (single_succ_p (jbb
)
732 && single_succ (jbb
) == EXIT_BLOCK_PTR
)
734 queue
[++tail
] = jbb
->index
;
735 SET_BIT (in_queue
, jbb
->index
);
737 if (too_large (jbb
->index
, &num_bbs
, &num_insns
))
739 too_large_failure
= 1;
748 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
750 if (e
->src
== ENTRY_BLOCK_PTR
)
753 node
= e
->src
->index
;
755 if (max_hdr
[node
] == loop_head
&& node
!= bb
->index
)
757 /* This is a loop latch. */
758 queue
[++tail
] = node
;
759 SET_BIT (in_queue
, node
);
761 if (too_large (node
, &num_bbs
, &num_insns
))
763 too_large_failure
= 1;
770 /* Now add all the blocks in the loop to the queue.
772 We know the loop is a natural loop; however the algorithm
773 above will not always mark certain blocks as being in the
781 The algorithm in the DFS traversal may not mark B & D as part
782 of the loop (i.e. they will not have max_hdr set to A).
784 We know they can not be loop latches (else they would have
785 had max_hdr set since they'd have a backedge to a dominator
786 block). So we don't need them on the initial queue.
788 We know they are part of the loop because they are dominated
789 by the loop header and can be reached by a backwards walk of
790 the edges starting with nodes on the initial queue.
792 It is safe and desirable to include those nodes in the
793 loop/scheduling region. To do so we would need to decrease
794 the degree of a node if it is the target of a backedge
795 within the loop itself as the node is placed in the queue.
797 We do not do this because I'm not sure that the actual
798 scheduling code will properly handle this case. ?!? */
800 while (head
< tail
&& !too_large_failure
)
803 child
= queue
[++head
];
805 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (child
)->preds
)
807 node
= e
->src
->index
;
809 /* See discussion above about nodes not marked as in
810 this loop during the initial DFS traversal. */
811 if (e
->src
== ENTRY_BLOCK_PTR
812 || max_hdr
[node
] != loop_head
)
817 else if (!TEST_BIT (in_queue
, node
) && node
!= bb
->index
)
819 queue
[++tail
] = node
;
820 SET_BIT (in_queue
, node
);
822 if (too_large (node
, &num_bbs
, &num_insns
))
824 too_large_failure
= 1;
831 if (tail
>= 0 && !too_large_failure
)
833 /* Place the loop header into list of region blocks. */
834 degree
[bb
->index
] = -1;
835 rgn_bb_table
[idx
] = bb
->index
;
836 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
837 RGN_BLOCKS (nr_regions
) = idx
++;
838 CONTAINING_RGN (bb
->index
) = nr_regions
;
839 BLOCK_TO_BB (bb
->index
) = count
= 0;
841 /* Remove blocks from queue[] when their in degree
842 becomes zero. Repeat until no blocks are left on the
843 list. This produces a topological list of blocks in
850 if (degree
[child
] == 0)
855 rgn_bb_table
[idx
++] = child
;
856 BLOCK_TO_BB (child
) = ++count
;
857 CONTAINING_RGN (child
) = nr_regions
;
858 queue
[head
] = queue
[tail
--];
860 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (child
)->succs
)
861 if (e
->dest
!= EXIT_BLOCK_PTR
)
862 --degree
[e
->dest
->index
];
874 /* Any block that did not end up in a region is placed into a region
877 if (degree
[bb
->index
] >= 0)
879 rgn_bb_table
[idx
] = bb
->index
;
880 RGN_NR_BLOCKS (nr_regions
) = 1;
881 RGN_BLOCKS (nr_regions
) = idx
++;
882 CONTAINING_RGN (bb
->index
) = nr_regions
++;
883 BLOCK_TO_BB (bb
->index
) = 0;
889 sbitmap_free (header
);
890 sbitmap_free (inner
);
891 sbitmap_free (in_queue
);
892 sbitmap_free (in_stack
);
895 /* Functions for regions scheduling information. */
897 /* Compute dominators, probability, and potential-split-edges of bb.
898 Assume that these values were already computed for bb's predecessors. */
901 compute_dom_prob_ps (int bb
)
904 int nr_out_edges
, nr_rgn_out_edges
;
905 edge_iterator in_ei
, out_ei
;
906 edge in_edge
, out_edge
;
909 if (IS_RGN_ENTRY (bb
))
911 SET_BIT (dom
[bb
], 0);
916 /* Initialize dom[bb] to '111..1'. */
917 sbitmap_ones (dom
[bb
]);
919 FOR_EACH_EDGE (in_edge
, in_ei
, BASIC_BLOCK (BB_TO_BLOCK (bb
))->preds
)
921 if (in_edge
->src
== ENTRY_BLOCK_PTR
)
924 pred_bb
= BLOCK_TO_BB (in_edge
->src
->index
);
925 sbitmap_a_and_b (dom
[bb
], dom
[bb
], dom
[pred_bb
]);
926 sbitmap_a_or_b (ancestor_edges
[bb
],
927 ancestor_edges
[bb
], ancestor_edges
[pred_bb
]);
929 SET_BIT (ancestor_edges
[bb
], EDGE_TO_BIT (in_edge
));
931 sbitmap_a_or_b (pot_split
[bb
], pot_split
[bb
], pot_split
[pred_bb
]);
934 nr_rgn_out_edges
= 0;
936 FOR_EACH_EDGE (out_edge
, out_ei
, in_edge
->src
->succs
)
940 /* The successor doesn't belong in the region? */
941 if (out_edge
->dest
!= EXIT_BLOCK_PTR
942 && CONTAINING_RGN (out_edge
->dest
->index
)
943 != CONTAINING_RGN (BB_TO_BLOCK (bb
)))
946 SET_BIT (pot_split
[bb
], EDGE_TO_BIT (out_edge
));
949 /* Now nr_rgn_out_edges is the number of region-exit edges from
950 pred, and nr_out_edges will be the number of pred out edges
951 not leaving the region. */
952 nr_out_edges
-= nr_rgn_out_edges
;
953 if (nr_rgn_out_edges
> 0)
954 prob
[bb
] += 0.9 * prob
[pred_bb
] / nr_out_edges
;
956 prob
[bb
] += prob
[pred_bb
] / nr_out_edges
;
959 SET_BIT (dom
[bb
], bb
);
960 sbitmap_difference (pot_split
[bb
], pot_split
[bb
], ancestor_edges
[bb
]);
962 if (sched_verbose
>= 2)
963 fprintf (sched_dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
),
964 (int) (100.0 * prob
[bb
]));
967 /* Functions for target info. */
969 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
970 Note that bb_trg dominates bb_src. */
973 split_edges (int bb_src
, int bb_trg
, edgelst
*bl
)
975 sbitmap src
= sbitmap_alloc (pot_split
[bb_src
]->n_bits
);
976 sbitmap_copy (src
, pot_split
[bb_src
]);
978 sbitmap_difference (src
, src
, pot_split
[bb_trg
]);
979 extract_edgelst (src
, bl
);
983 /* Find the valid candidate-source-blocks for the target block TRG, compute
984 their probability, and check if they are speculative or not.
985 For speculative sources, compute their update-blocks and split-blocks. */
988 compute_trg_info (int trg
)
992 int i
, j
, k
, update_idx
;
998 /* Define some of the fields for the target bb as well. */
999 sp
= candidate_table
+ trg
;
1001 sp
->is_speculative
= 0;
1004 visited
= sbitmap_alloc (last_basic_block
- (INVALID_BLOCK
+ 1));
1006 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1008 sp
= candidate_table
+ i
;
1010 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1013 sp
->src_prob
= GET_SRC_PROB (i
, trg
);
1014 sp
->is_valid
= (sp
->src_prob
>= MIN_PROBABILITY
);
1019 split_edges (i
, trg
, &el
);
1020 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1021 if (sp
->is_speculative
&& !flag_schedule_speculative
)
1027 /* Compute split blocks and store them in bblst_table.
1028 The TO block of every split edge is a split block. */
1029 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
1030 sp
->split_bbs
.nr_members
= el
.nr_members
;
1031 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
1032 bblst_table
[bblst_last
] = el
.first_member
[j
]->dest
;
1033 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
1035 /* Compute update blocks and store them in bblst_table.
1036 For every split edge, look at the FROM block, and check
1037 all out edges. For each out edge that is not a split edge,
1038 add the TO block to the update block list. This list can end
1039 up with a lot of duplicates. We need to weed them out to avoid
1040 overrunning the end of the bblst_table. */
1043 sbitmap_zero (visited
);
1044 for (j
= 0; j
< el
.nr_members
; j
++)
1046 block
= el
.first_member
[j
]->src
;
1047 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1049 if (!TEST_BIT (visited
,
1050 e
->dest
->index
- (INVALID_BLOCK
+ 1)))
1052 for (k
= 0; k
< el
.nr_members
; k
++)
1053 if (e
== el
.first_member
[k
])
1056 if (k
>= el
.nr_members
)
1058 bblst_table
[bblst_last
++] = e
->dest
;
1060 e
->dest
->index
- (INVALID_BLOCK
+ 1));
1066 sp
->update_bbs
.nr_members
= update_idx
;
1068 /* Make sure we didn't overrun the end of bblst_table. */
1069 gcc_assert (bblst_last
<= bblst_size
);
1073 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
1075 sp
->is_speculative
= 0;
1080 sbitmap_free (visited
);
1083 /* Print candidates info, for debugging purposes. Callable from debugger. */
1086 debug_candidate (int i
)
1088 if (!candidate_table
[i
].is_valid
)
1091 if (candidate_table
[i
].is_speculative
)
1094 fprintf (sched_dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
1096 fprintf (sched_dump
, "split path: ");
1097 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
1099 int b
= candidate_table
[i
].split_bbs
.first_member
[j
]->index
;
1101 fprintf (sched_dump
, " %d ", b
);
1103 fprintf (sched_dump
, "\n");
1105 fprintf (sched_dump
, "update path: ");
1106 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
1108 int b
= candidate_table
[i
].update_bbs
.first_member
[j
]->index
;
1110 fprintf (sched_dump
, " %d ", b
);
1112 fprintf (sched_dump
, "\n");
1116 fprintf (sched_dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
1120 /* Print candidates info, for debugging purposes. Callable from debugger. */
1123 debug_candidates (int trg
)
1127 fprintf (sched_dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
1128 BB_TO_BLOCK (trg
), trg
);
1129 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1130 debug_candidate (i
);
1133 /* Functions for speculative scheduling. */
1135 /* Return 0 if x is a set of a register alive in the beginning of one
1136 of the split-blocks of src, otherwise return 1. */
1139 check_live_1 (int src
, rtx x
)
1143 rtx reg
= SET_DEST (x
);
1148 while (GET_CODE (reg
) == SUBREG
1149 || GET_CODE (reg
) == ZERO_EXTRACT
1150 || GET_CODE (reg
) == STRICT_LOW_PART
)
1151 reg
= XEXP (reg
, 0);
1153 if (GET_CODE (reg
) == PARALLEL
)
1157 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1158 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1159 if (check_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0)))
1168 regno
= REGNO (reg
);
1170 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
1172 /* Global registers are assumed live. */
1177 if (regno
< FIRST_PSEUDO_REGISTER
)
1179 /* Check for hard registers. */
1180 int j
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1183 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1185 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1187 if (REGNO_REG_SET_P (b
->il
.rtl
->global_live_at_start
,
1197 /* Check for pseudo registers. */
1198 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
1200 basic_block b
= candidate_table
[src
].split_bbs
.first_member
[i
];
1202 if (REGNO_REG_SET_P (b
->il
.rtl
->global_live_at_start
, regno
))
1213 /* If x is a set of a register R, mark that R is alive in the beginning
1214 of every update-block of src. */
1217 update_live_1 (int src
, rtx x
)
1221 rtx reg
= SET_DEST (x
);
1226 while (GET_CODE (reg
) == SUBREG
1227 || GET_CODE (reg
) == ZERO_EXTRACT
1228 || GET_CODE (reg
) == STRICT_LOW_PART
)
1229 reg
= XEXP (reg
, 0);
1231 if (GET_CODE (reg
) == PARALLEL
)
1235 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
1236 if (XEXP (XVECEXP (reg
, 0, i
), 0) != 0)
1237 update_live_1 (src
, XEXP (XVECEXP (reg
, 0, i
), 0));
1245 /* Global registers are always live, so the code below does not apply
1248 regno
= REGNO (reg
);
1250 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
1252 if (regno
< FIRST_PSEUDO_REGISTER
)
1254 int j
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
1257 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
1259 basic_block b
= candidate_table
[src
].update_bbs
.first_member
[i
];
1261 SET_REGNO_REG_SET (b
->il
.rtl
->global_live_at_start
,
1268 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
1270 basic_block b
= candidate_table
[src
].update_bbs
.first_member
[i
];
1272 SET_REGNO_REG_SET (b
->il
.rtl
->global_live_at_start
, regno
);
1278 /* Return 1 if insn can be speculatively moved from block src to trg,
1279 otherwise return 0. Called before first insertion of insn to
1280 ready-list or before the scheduling. */
1283 check_live (rtx insn
, int src
)
1285 /* Find the registers set by instruction. */
1286 if (GET_CODE (PATTERN (insn
)) == SET
1287 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1288 return check_live_1 (src
, PATTERN (insn
));
1289 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1292 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1293 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1294 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1295 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
1304 /* Update the live registers info after insn was moved speculatively from
1305 block src to trg. */
1308 update_live (rtx insn
, int src
)
1310 /* Find the registers set by instruction. */
1311 if (GET_CODE (PATTERN (insn
)) == SET
1312 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
1313 update_live_1 (src
, PATTERN (insn
));
1314 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
1317 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
1318 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
1319 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
1320 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
1324 /* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1325 #define IS_REACHABLE(bb_from, bb_to) \
1327 || IS_RGN_ENTRY (bb_from) \
1328 || (TEST_BIT (ancestor_edges[bb_to], \
1329 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK (BB_TO_BLOCK (bb_from)))))))
1331 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1334 set_spec_fed (rtx load_insn
)
1338 for (link
= INSN_DEPEND (load_insn
); link
; link
= XEXP (link
, 1))
1339 if (GET_MODE (link
) == VOIDmode
)
1340 FED_BY_SPEC_LOAD (XEXP (link
, 0)) = 1;
1341 } /* set_spec_fed */
1343 /* On the path from the insn to load_insn_bb, find a conditional
1344 branch depending on insn, that guards the speculative load. */
1347 find_conditional_protection (rtx insn
, int load_insn_bb
)
1351 /* Iterate through DEF-USE forward dependences. */
1352 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
1354 rtx next
= XEXP (link
, 0);
1355 if ((CONTAINING_RGN (BLOCK_NUM (next
)) ==
1356 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
1357 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
1358 && load_insn_bb
!= INSN_BB (next
)
1359 && GET_MODE (link
) == VOIDmode
1361 || find_conditional_protection (next
, load_insn_bb
)))
1365 } /* find_conditional_protection */
1367 /* Returns 1 if the same insn1 that participates in the computation
1368 of load_insn's address is feeding a conditional branch that is
1369 guarding on load_insn. This is true if we find a the two DEF-USE
1371 insn1 -> ... -> conditional-branch
1372 insn1 -> ... -> load_insn,
1373 and if a flow path exist:
1374 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1375 and if insn1 is on the path
1376 region-entry -> ... -> bb_trg -> ... load_insn.
1378 Locate insn1 by climbing on LOG_LINKS from load_insn.
1379 Locate the branch by following INSN_DEPEND from insn1. */
1382 is_conditionally_protected (rtx load_insn
, int bb_src
, int bb_trg
)
1386 for (link
= LOG_LINKS (load_insn
); link
; link
= XEXP (link
, 1))
1388 rtx insn1
= XEXP (link
, 0);
1390 /* Must be a DEF-USE dependence upon non-branch. */
1391 if (GET_MODE (link
) != VOIDmode
1395 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1396 if (INSN_BB (insn1
) == bb_src
1397 || (CONTAINING_RGN (BLOCK_NUM (insn1
))
1398 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
1399 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
1400 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
1403 /* Now search for the conditional-branch. */
1404 if (find_conditional_protection (insn1
, bb_src
))
1407 /* Recursive step: search another insn1, "above" current insn1. */
1408 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
1411 /* The chain does not exist. */
1413 } /* is_conditionally_protected */
1415 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1416 load_insn can move speculatively from bb_src to bb_trg. All the
1417 following must hold:
1419 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1420 (2) load_insn and load1 have a def-use dependence upon
1421 the same insn 'insn1'.
1422 (3) either load2 is in bb_trg, or:
1423 - there's only one split-block, and
1424 - load1 is on the escape path, and
1426 From all these we can conclude that the two loads access memory
1427 addresses that differ at most by a constant, and hence if moving
1428 load_insn would cause an exception, it would have been caused by
1432 is_pfree (rtx load_insn
, int bb_src
, int bb_trg
)
1435 candidate
*candp
= candidate_table
+ bb_src
;
1437 if (candp
->split_bbs
.nr_members
!= 1)
1438 /* Must have exactly one escape block. */
1441 for (back_link
= LOG_LINKS (load_insn
);
1442 back_link
; back_link
= XEXP (back_link
, 1))
1444 rtx insn1
= XEXP (back_link
, 0);
1446 if (GET_MODE (back_link
) == VOIDmode
)
1448 /* Found a DEF-USE dependence (insn1, load_insn). */
1451 for (fore_link
= INSN_DEPEND (insn1
);
1452 fore_link
; fore_link
= XEXP (fore_link
, 1))
1454 rtx insn2
= XEXP (fore_link
, 0);
1455 if (GET_MODE (fore_link
) == VOIDmode
)
1457 /* Found a DEF-USE dependence (insn1, insn2). */
1458 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
1459 /* insn2 not guaranteed to be a 1 base reg load. */
1462 if (INSN_BB (insn2
) == bb_trg
)
1463 /* insn2 is the similar load, in the target block. */
1466 if (*(candp
->split_bbs
.first_member
) == BLOCK_FOR_INSN (insn2
))
1467 /* insn2 is a similar load, in a split-block. */
1474 /* Couldn't find a similar load. */
1478 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1479 a load moved speculatively, or if load_insn is protected by
1480 a compare on load_insn's address). */
1483 is_prisky (rtx load_insn
, int bb_src
, int bb_trg
)
1485 if (FED_BY_SPEC_LOAD (load_insn
))
1488 if (LOG_LINKS (load_insn
) == NULL
)
1489 /* Dependence may 'hide' out of the region. */
1492 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
1498 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
1499 Return 1 if insn is exception-free (and the motion is valid)
1503 is_exception_free (rtx insn
, int bb_src
, int bb_trg
)
1505 int insn_class
= haifa_classify_insn (insn
);
1507 /* Handle non-load insns. */
1518 if (!flag_schedule_speculative_load
)
1520 IS_LOAD_INSN (insn
) = 1;
1527 case PFREE_CANDIDATE
:
1528 if (is_pfree (insn
, bb_src
, bb_trg
))
1530 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
1531 case PRISKY_CANDIDATE
:
1532 if (!flag_schedule_speculative_load_dangerous
1533 || is_prisky (insn
, bb_src
, bb_trg
))
1539 return flag_schedule_speculative_load_dangerous
;
1542 /* The number of insns from the current block scheduled so far. */
1543 static int sched_target_n_insns
;
1544 /* The number of insns from the current block to be scheduled in total. */
1545 static int target_n_insns
;
1546 /* The number of insns from the entire region scheduled so far. */
1547 static int sched_n_insns
;
1548 /* Nonzero if the last scheduled insn was a jump. */
1549 static int last_was_jump
;
1551 /* Implementations of the sched_info functions for region scheduling. */
1552 static void init_ready_list (struct ready_list
*);
1553 static int can_schedule_ready_p (rtx
);
1554 static int new_ready (rtx
);
1555 static int schedule_more_p (void);
1556 static const char *rgn_print_insn (rtx
, int);
1557 static int rgn_rank (rtx
, rtx
);
1558 static int contributes_to_priority (rtx
, rtx
);
1559 static void compute_jump_reg_dependencies (rtx
, regset
, regset
, regset
);
1561 /* Return nonzero if there are more insns that should be scheduled. */
1564 schedule_more_p (void)
1566 return ! last_was_jump
&& sched_target_n_insns
< target_n_insns
;
1569 /* Add all insns that are initially ready to the ready list READY. Called
1570 once before scheduling a set of insns. */
1573 init_ready_list (struct ready_list
*ready
)
1575 rtx prev_head
= current_sched_info
->prev_head
;
1576 rtx next_tail
= current_sched_info
->next_tail
;
1581 sched_target_n_insns
= 0;
1585 /* Print debugging information. */
1586 if (sched_verbose
>= 5)
1587 debug_dependencies ();
1589 /* Prepare current target block info. */
1590 if (current_nr_blocks
> 1)
1592 candidate_table
= xmalloc (current_nr_blocks
* sizeof (candidate
));
1595 /* bblst_table holds split blocks and update blocks for each block after
1596 the current one in the region. split blocks and update blocks are
1597 the TO blocks of region edges, so there can be at most rgn_nr_edges
1599 bblst_size
= (current_nr_blocks
- target_bb
) * rgn_nr_edges
;
1600 bblst_table
= xmalloc (bblst_size
* sizeof (basic_block
));
1603 edgelst_table
= xmalloc (rgn_nr_edges
* sizeof (edge
));
1605 compute_trg_info (target_bb
);
1608 /* Initialize ready list with all 'ready' insns in target block.
1609 Count number of insns in the target block being scheduled. */
1610 for (insn
= NEXT_INSN (prev_head
); insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1612 if (INSN_DEP_COUNT (insn
) == 0)
1614 ready_add (ready
, insn
);
1616 if (targetm
.sched
.adjust_priority
)
1617 INSN_PRIORITY (insn
) =
1618 targetm
.sched
.adjust_priority (insn
, INSN_PRIORITY (insn
));
1623 /* Add to ready list all 'ready' insns in valid source blocks.
1624 For speculative insns, check-live, exception-free, and
1626 for (bb_src
= target_bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
1627 if (IS_VALID (bb_src
))
1633 get_block_head_tail (BB_TO_BLOCK (bb_src
), &head
, &tail
);
1634 src_next_tail
= NEXT_INSN (tail
);
1637 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
1639 if (! INSN_P (insn
))
1642 if (!CANT_MOVE (insn
)
1643 && (!IS_SPECULATIVE_INSN (insn
)
1644 || ((recog_memoized (insn
) < 0
1645 || min_insn_conflict_delay (curr_state
,
1647 && check_live (insn
, bb_src
)
1648 && is_exception_free (insn
, bb_src
, target_bb
))))
1649 if (INSN_DEP_COUNT (insn
) == 0)
1651 ready_add (ready
, insn
);
1653 if (targetm
.sched
.adjust_priority
)
1654 INSN_PRIORITY (insn
) =
1655 targetm
.sched
.adjust_priority (insn
, INSN_PRIORITY (insn
));
1661 /* Called after taking INSN from the ready list. Returns nonzero if this
1662 insn can be scheduled, nonzero if we should silently discard it. */
1665 can_schedule_ready_p (rtx insn
)
1670 /* An interblock motion? */
1671 if (INSN_BB (insn
) != target_bb
)
1675 if (IS_SPECULATIVE_INSN (insn
))
1677 if (!check_live (insn
, INSN_BB (insn
)))
1679 update_live (insn
, INSN_BB (insn
));
1681 /* For speculative load, mark insns fed by it. */
1682 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
1683 set_spec_fed (insn
);
1689 /* Update source block boundaries. */
1690 b1
= BLOCK_FOR_INSN (insn
);
1691 if (insn
== BB_HEAD (b1
) && insn
== BB_END (b1
))
1693 /* We moved all the insns in the basic block.
1694 Emit a note after the last insn and update the
1695 begin/end boundaries to point to the note. */
1696 rtx note
= emit_note_after (NOTE_INSN_DELETED
, insn
);
1697 BB_HEAD (b1
) = note
;
1700 else if (insn
== BB_END (b1
))
1702 /* We took insns from the end of the basic block,
1703 so update the end of block boundary so that it
1704 points to the first insn we did not move. */
1705 BB_END (b1
) = PREV_INSN (insn
);
1707 else if (insn
== BB_HEAD (b1
))
1709 /* We took insns from the start of the basic block,
1710 so update the start of block boundary so that
1711 it points to the first insn we did not move. */
1712 BB_HEAD (b1
) = NEXT_INSN (insn
);
1717 /* In block motion. */
1718 sched_target_n_insns
++;
1725 /* Called after INSN has all its dependencies resolved. Return nonzero
1726 if it should be moved to the ready list or the queue, or zero if we
1727 should silently discard it. */
1729 new_ready (rtx next
)
1731 /* For speculative insns, before inserting to ready/queue,
1732 check live, exception-free, and issue-delay. */
1733 if (INSN_BB (next
) != target_bb
1734 && (!IS_VALID (INSN_BB (next
))
1736 || (IS_SPECULATIVE_INSN (next
)
1737 && ((recog_memoized (next
) >= 0
1738 && min_insn_conflict_delay (curr_state
, next
, next
) > 3)
1739 || !check_live (next
, INSN_BB (next
))
1740 || !is_exception_free (next
, INSN_BB (next
), target_bb
)))))
1745 /* Return a string that contains the insn uid and optionally anything else
1746 necessary to identify this insn in an output. It's valid to use a
1747 static buffer for this. The ALIGNED parameter should cause the string
1748 to be formatted so that multiple output lines will line up nicely. */
1751 rgn_print_insn (rtx insn
, int aligned
)
1753 static char tmp
[80];
1756 sprintf (tmp
, "b%3d: i%4d", INSN_BB (insn
), INSN_UID (insn
));
1759 if (current_nr_blocks
> 1 && INSN_BB (insn
) != target_bb
)
1760 sprintf (tmp
, "%d/b%d", INSN_UID (insn
), INSN_BB (insn
));
1762 sprintf (tmp
, "%d", INSN_UID (insn
));
1767 /* Compare priority of two insns. Return a positive number if the second
1768 insn is to be preferred for scheduling, and a negative one if the first
1769 is to be preferred. Zero if they are equally good. */
1772 rgn_rank (rtx insn1
, rtx insn2
)
1774 /* Some comparison make sense in interblock scheduling only. */
1775 if (INSN_BB (insn1
) != INSN_BB (insn2
))
1777 int spec_val
, prob_val
;
1779 /* Prefer an inblock motion on an interblock motion. */
1780 if ((INSN_BB (insn2
) == target_bb
) && (INSN_BB (insn1
) != target_bb
))
1782 if ((INSN_BB (insn1
) == target_bb
) && (INSN_BB (insn2
) != target_bb
))
1785 /* Prefer a useful motion on a speculative one. */
1786 spec_val
= IS_SPECULATIVE_INSN (insn1
) - IS_SPECULATIVE_INSN (insn2
);
1790 /* Prefer a more probable (speculative) insn. */
1791 prob_val
= INSN_PROBABILITY (insn2
) - INSN_PROBABILITY (insn1
);
1798 /* NEXT is an instruction that depends on INSN (a backward dependence);
1799 return nonzero if we should include this dependence in priority
1803 contributes_to_priority (rtx next
, rtx insn
)
1805 return BLOCK_NUM (next
) == BLOCK_NUM (insn
);
1808 /* INSN is a JUMP_INSN, COND_SET is the set of registers that are
1809 conditionally set before INSN. Store the set of registers that
1810 must be considered as used by this jump in USED and that of
1811 registers that must be considered as set in SET. */
1814 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED
,
1815 regset cond_exec ATTRIBUTE_UNUSED
,
1816 regset used ATTRIBUTE_UNUSED
,
1817 regset set ATTRIBUTE_UNUSED
)
1819 /* Nothing to do here, since we postprocess jumps in
1820 add_branch_dependences. */
1823 /* Used in schedule_insns to initialize current_sched_info for scheduling
1824 regions (or single basic blocks). */
1826 static struct sched_info region_sched_info
=
1829 can_schedule_ready_p
,
1834 contributes_to_priority
,
1835 compute_jump_reg_dependencies
,
1842 /* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register. */
1845 sets_likely_spilled (rtx pat
)
1848 note_stores (pat
, sets_likely_spilled_1
, &ret
);
1853 sets_likely_spilled_1 (rtx x
, rtx pat
, void *data
)
1855 bool *ret
= (bool *) data
;
1857 if (GET_CODE (pat
) == SET
1859 && REGNO (x
) < FIRST_PSEUDO_REGISTER
1860 && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x
))))
1864 /* Add dependences so that branches are scheduled to run last in their
1868 add_branch_dependences (rtx head
, rtx tail
)
1872 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
1873 that can throw exceptions, force them to remain in order at the end of
1874 the block by adding dependencies and giving the last a high priority.
1875 There may be notes present, and prev_head may also be a note.
1877 Branches must obviously remain at the end. Calls should remain at the
1878 end since moving them results in worse register allocation. Uses remain
1879 at the end to ensure proper register allocation.
1881 cc0 setters remain at the end because they can't be moved away from
1884 Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values)
1885 are not moved before reload because we can wind up with register
1886 allocation failures. */
1890 while (CALL_P (insn
)
1892 || (NONJUMP_INSN_P (insn
)
1893 && (GET_CODE (PATTERN (insn
)) == USE
1894 || GET_CODE (PATTERN (insn
)) == CLOBBER
1895 || can_throw_internal (insn
)
1897 || sets_cc0_p (PATTERN (insn
))
1899 || (!reload_completed
1900 && sets_likely_spilled (PATTERN (insn
)))))
1905 if (last
!= 0 && !find_insn_list (insn
, LOG_LINKS (last
)))
1907 add_dependence (last
, insn
, REG_DEP_ANTI
);
1908 INSN_REF_COUNT (insn
)++;
1911 CANT_MOVE (insn
) = 1;
1916 /* Don't overrun the bounds of the basic block. */
1920 insn
= PREV_INSN (insn
);
1923 /* Make sure these insns are scheduled last in their block. */
1926 while (insn
!= head
)
1928 insn
= prev_nonnote_insn (insn
);
1930 if (INSN_REF_COUNT (insn
) != 0)
1933 add_dependence (last
, insn
, REG_DEP_ANTI
);
1934 INSN_REF_COUNT (insn
) = 1;
1938 /* Data structures for the computation of data dependences in a regions. We
1939 keep one `deps' structure for every basic block. Before analyzing the
1940 data dependences for a bb, its variables are initialized as a function of
1941 the variables of its predecessors. When the analysis for a bb completes,
1942 we save the contents to the corresponding bb_deps[bb] variable. */
1944 static struct deps
*bb_deps
;
1946 /* Duplicate the INSN_LIST elements of COPY and prepend them to OLD. */
1949 concat_INSN_LIST (rtx copy
, rtx old
)
1952 for (; copy
; copy
= XEXP (copy
, 1))
1953 new = alloc_INSN_LIST (XEXP (copy
, 0), new);
1958 concat_insn_mem_list (rtx copy_insns
, rtx copy_mems
, rtx
*old_insns_p
,
1961 rtx new_insns
= *old_insns_p
;
1962 rtx new_mems
= *old_mems_p
;
1966 new_insns
= alloc_INSN_LIST (XEXP (copy_insns
, 0), new_insns
);
1967 new_mems
= alloc_EXPR_LIST (VOIDmode
, XEXP (copy_mems
, 0), new_mems
);
1968 copy_insns
= XEXP (copy_insns
, 1);
1969 copy_mems
= XEXP (copy_mems
, 1);
1972 *old_insns_p
= new_insns
;
1973 *old_mems_p
= new_mems
;
1976 /* After computing the dependencies for block BB, propagate the dependencies
1977 found in TMP_DEPS to the successors of the block. */
1979 propagate_deps (int bb
, struct deps
*pred_deps
)
1981 basic_block block
= BASIC_BLOCK (BB_TO_BLOCK (bb
));
1985 /* bb's structures are inherited by its successors. */
1986 FOR_EACH_EDGE (e
, ei
, block
->succs
)
1988 struct deps
*succ_deps
;
1990 reg_set_iterator rsi
;
1992 /* Only bbs "below" bb, in the same region, are interesting. */
1993 if (e
->dest
== EXIT_BLOCK_PTR
1994 || CONTAINING_RGN (block
->index
) != CONTAINING_RGN (e
->dest
->index
)
1995 || BLOCK_TO_BB (e
->dest
->index
) <= bb
)
1998 succ_deps
= bb_deps
+ BLOCK_TO_BB (e
->dest
->index
);
2000 /* The reg_last lists are inherited by successor. */
2001 EXECUTE_IF_SET_IN_REG_SET (&pred_deps
->reg_last_in_use
, 0, reg
, rsi
)
2003 struct deps_reg
*pred_rl
= &pred_deps
->reg_last
[reg
];
2004 struct deps_reg
*succ_rl
= &succ_deps
->reg_last
[reg
];
2006 succ_rl
->uses
= concat_INSN_LIST (pred_rl
->uses
, succ_rl
->uses
);
2007 succ_rl
->sets
= concat_INSN_LIST (pred_rl
->sets
, succ_rl
->sets
);
2008 succ_rl
->clobbers
= concat_INSN_LIST (pred_rl
->clobbers
,
2010 succ_rl
->uses_length
+= pred_rl
->uses_length
;
2011 succ_rl
->clobbers_length
+= pred_rl
->clobbers_length
;
2013 IOR_REG_SET (&succ_deps
->reg_last_in_use
, &pred_deps
->reg_last_in_use
);
2015 /* Mem read/write lists are inherited by successor. */
2016 concat_insn_mem_list (pred_deps
->pending_read_insns
,
2017 pred_deps
->pending_read_mems
,
2018 &succ_deps
->pending_read_insns
,
2019 &succ_deps
->pending_read_mems
);
2020 concat_insn_mem_list (pred_deps
->pending_write_insns
,
2021 pred_deps
->pending_write_mems
,
2022 &succ_deps
->pending_write_insns
,
2023 &succ_deps
->pending_write_mems
);
2025 succ_deps
->last_pending_memory_flush
2026 = concat_INSN_LIST (pred_deps
->last_pending_memory_flush
,
2027 succ_deps
->last_pending_memory_flush
);
2029 succ_deps
->pending_lists_length
+= pred_deps
->pending_lists_length
;
2030 succ_deps
->pending_flush_length
+= pred_deps
->pending_flush_length
;
2032 /* last_function_call is inherited by successor. */
2033 succ_deps
->last_function_call
2034 = concat_INSN_LIST (pred_deps
->last_function_call
,
2035 succ_deps
->last_function_call
);
2037 /* sched_before_next_call is inherited by successor. */
2038 succ_deps
->sched_before_next_call
2039 = concat_INSN_LIST (pred_deps
->sched_before_next_call
,
2040 succ_deps
->sched_before_next_call
);
2043 /* These lists should point to the right place, for correct
2045 bb_deps
[bb
].pending_read_insns
= pred_deps
->pending_read_insns
;
2046 bb_deps
[bb
].pending_read_mems
= pred_deps
->pending_read_mems
;
2047 bb_deps
[bb
].pending_write_insns
= pred_deps
->pending_write_insns
;
2048 bb_deps
[bb
].pending_write_mems
= pred_deps
->pending_write_mems
;
2050 /* Can't allow these to be freed twice. */
2051 pred_deps
->pending_read_insns
= 0;
2052 pred_deps
->pending_read_mems
= 0;
2053 pred_deps
->pending_write_insns
= 0;
2054 pred_deps
->pending_write_mems
= 0;
2057 /* Compute backward dependences inside bb. In a multiple blocks region:
2058 (1) a bb is analyzed after its predecessors, and (2) the lists in
2059 effect at the end of bb (after analyzing for bb) are inherited by
2062 Specifically for reg-reg data dependences, the block insns are
2063 scanned by sched_analyze () top-to-bottom. Two lists are
2064 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2065 and reg_last[].uses for register USEs.
2067 When analysis is completed for bb, we update for its successors:
2068 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2069 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2071 The mechanism for computing mem-mem data dependence is very
2072 similar, and the result is interblock dependences in the region. */
2075 compute_block_backward_dependences (int bb
)
2078 struct deps tmp_deps
;
2080 tmp_deps
= bb_deps
[bb
];
2082 /* Do the analysis for this block. */
2083 get_block_head_tail (BB_TO_BLOCK (bb
), &head
, &tail
);
2084 sched_analyze (&tmp_deps
, head
, tail
);
2085 add_branch_dependences (head
, tail
);
2087 if (current_nr_blocks
> 1)
2088 propagate_deps (bb
, &tmp_deps
);
2090 /* Free up the INSN_LISTs. */
2091 free_deps (&tmp_deps
);
2094 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2095 them to the unused_*_list variables, so that they can be reused. */
2098 free_pending_lists (void)
2102 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2104 free_INSN_LIST_list (&bb_deps
[bb
].pending_read_insns
);
2105 free_INSN_LIST_list (&bb_deps
[bb
].pending_write_insns
);
2106 free_EXPR_LIST_list (&bb_deps
[bb
].pending_read_mems
);
2107 free_EXPR_LIST_list (&bb_deps
[bb
].pending_write_mems
);
2111 /* Print dependences for debugging, callable from debugger. */
2114 debug_dependencies (void)
2118 fprintf (sched_dump
, ";; --------------- forward dependences: ------------ \n");
2119 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2125 get_block_head_tail (BB_TO_BLOCK (bb
), &head
, &tail
);
2126 next_tail
= NEXT_INSN (tail
);
2127 fprintf (sched_dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
2128 BB_TO_BLOCK (bb
), bb
);
2130 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2131 "insn", "code", "bb", "dep", "prio", "cost",
2133 fprintf (sched_dump
, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2134 "----", "----", "--", "---", "----", "----",
2137 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2141 if (! INSN_P (insn
))
2144 fprintf (sched_dump
, ";; %6d ", INSN_UID (insn
));
2147 n
= NOTE_LINE_NUMBER (insn
);
2149 fprintf (sched_dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
2152 expanded_location xloc
;
2153 NOTE_EXPANDED_LOCATION (xloc
, insn
);
2154 fprintf (sched_dump
, "line %d, file %s\n",
2155 xloc
.line
, xloc
.file
);
2159 fprintf (sched_dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
2163 fprintf (sched_dump
,
2164 ";; %s%5d%6d%6d%6d%6d%6d ",
2165 (SCHED_GROUP_P (insn
) ? "+" : " "),
2169 INSN_DEP_COUNT (insn
),
2170 INSN_PRIORITY (insn
),
2171 insn_cost (insn
, 0, 0));
2173 if (recog_memoized (insn
) < 0)
2174 fprintf (sched_dump
, "nothing");
2176 print_reservation (sched_dump
, insn
);
2178 fprintf (sched_dump
, "\t: ");
2179 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
2180 fprintf (sched_dump
, "%d ", INSN_UID (XEXP (link
, 0)));
2181 fprintf (sched_dump
, "\n");
2184 fprintf (sched_dump
, "\n");
2187 /* Returns true if all the basic blocks of the current region have
2188 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
2190 sched_is_disabled_for_current_region_p (void)
2194 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2195 if (!(BASIC_BLOCK (BB_TO_BLOCK (bb
))->flags
& BB_DISABLE_SCHEDULE
))
2201 /* Schedule a region. A region is either an inner loop, a loop-free
2202 subroutine, or a single basic block. Each bb in the region is
2203 scheduled after its flow predecessors. */
2206 schedule_region (int rgn
)
2212 int rgn_n_insns
= 0;
2213 int sched_rgn_n_insns
= 0;
2215 /* Set variables for the current region. */
2216 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
2217 current_blocks
= RGN_BLOCKS (rgn
);
2219 /* Don't schedule region that is marked by
2220 NOTE_DISABLE_SCHED_OF_BLOCK. */
2221 if (sched_is_disabled_for_current_region_p ())
2224 init_deps_global ();
2226 /* Initializations for region data dependence analysis. */
2227 bb_deps
= xmalloc (sizeof (struct deps
) * current_nr_blocks
);
2228 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2229 init_deps (bb_deps
+ bb
);
2231 /* Compute LOG_LINKS. */
2232 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2233 compute_block_backward_dependences (bb
);
2235 /* Compute INSN_DEPEND. */
2236 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
2239 get_block_head_tail (BB_TO_BLOCK (bb
), &head
, &tail
);
2241 compute_forward_dependences (head
, tail
);
2243 if (targetm
.sched
.dependencies_evaluation_hook
)
2244 targetm
.sched
.dependencies_evaluation_hook (head
, tail
);
2248 /* Set priorities. */
2249 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2252 get_block_head_tail (BB_TO_BLOCK (bb
), &head
, &tail
);
2254 rgn_n_insns
+= set_priorities (head
, tail
);
2257 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
2258 if (current_nr_blocks
> 1)
2260 prob
= xmalloc ((current_nr_blocks
) * sizeof (float));
2262 dom
= sbitmap_vector_alloc (current_nr_blocks
, current_nr_blocks
);
2263 sbitmap_vector_zero (dom
, current_nr_blocks
);
2265 /* Use ->aux to implement EDGE_TO_BIT mapping. */
2269 if (CONTAINING_RGN (block
->index
) != rgn
)
2271 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2272 SET_EDGE_TO_BIT (e
, rgn_nr_edges
++);
2275 rgn_edges
= xmalloc (rgn_nr_edges
* sizeof (edge
));
2279 if (CONTAINING_RGN (block
->index
) != rgn
)
2281 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2282 rgn_edges
[rgn_nr_edges
++] = e
;
2286 pot_split
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
2287 sbitmap_vector_zero (pot_split
, current_nr_blocks
);
2288 ancestor_edges
= sbitmap_vector_alloc (current_nr_blocks
, rgn_nr_edges
);
2289 sbitmap_vector_zero (ancestor_edges
, current_nr_blocks
);
2291 /* Compute probabilities, dominators, split_edges. */
2292 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2293 compute_dom_prob_ps (bb
);
2296 /* Now we can schedule all blocks. */
2297 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2300 int b
= BB_TO_BLOCK (bb
);
2302 get_block_head_tail (b
, &head
, &tail
);
2304 if (no_real_insns_p (head
, tail
))
2307 current_sched_info
->prev_head
= PREV_INSN (head
);
2308 current_sched_info
->next_tail
= NEXT_INSN (tail
);
2310 if (write_symbols
!= NO_DEBUG
)
2312 save_line_notes (b
, head
, tail
);
2313 rm_line_notes (head
, tail
);
2316 /* rm_other_notes only removes notes which are _inside_ the
2317 block---that is, it won't remove notes before the first real insn
2318 or after the last real insn of the block. So if the first insn
2319 has a REG_SAVE_NOTE which would otherwise be emitted before the
2320 insn, it is redundant with the note before the start of the
2321 block, and so we have to take it out. */
2326 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
2327 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
2328 remove_note (head
, note
);
2331 /* Remove remaining note insns from the block, save them in
2332 note_list. These notes are restored at the end of
2333 schedule_block (). */
2334 rm_other_notes (head
, tail
);
2338 current_sched_info
->queue_must_finish_empty
2339 = current_nr_blocks
> 1 && !flag_schedule_interblock
;
2341 schedule_block (b
, rgn_n_insns
);
2342 sched_rgn_n_insns
+= sched_n_insns
;
2344 /* Update target block boundaries. */
2345 if (head
== BB_HEAD (BASIC_BLOCK (b
)))
2346 BB_HEAD (BASIC_BLOCK (b
)) = current_sched_info
->head
;
2347 if (tail
== BB_END (BASIC_BLOCK (b
)))
2348 BB_END (BASIC_BLOCK (b
)) = current_sched_info
->tail
;
2351 if (current_nr_blocks
> 1)
2353 free (candidate_table
);
2355 free (edgelst_table
);
2359 /* Sanity check: verify that all region insns were scheduled. */
2360 gcc_assert (sched_rgn_n_insns
== rgn_n_insns
);
2362 /* Restore line notes. */
2363 if (write_symbols
!= NO_DEBUG
)
2365 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
2368 get_block_head_tail (BB_TO_BLOCK (bb
), &head
, &tail
);
2369 restore_line_notes (head
, tail
);
2373 /* Done with this region. */
2374 free_pending_lists ();
2376 finish_deps_global ();
2380 if (current_nr_blocks
> 1)
2382 /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
2385 if (CONTAINING_RGN (block
->index
) != rgn
)
2387 FOR_EACH_EDGE (e
, ei
, block
->succs
)
2392 sbitmap_vector_free (dom
);
2393 sbitmap_vector_free (pot_split
);
2394 sbitmap_vector_free (ancestor_edges
);
2399 /* Indexed by region, holds the number of death notes found in that region.
2400 Used for consistency checks. */
2401 static int *deaths_in_region
;
2403 /* Initialize data structures for region scheduling. */
2412 rgn_table
= xmalloc ((n_basic_blocks
) * sizeof (region
));
2413 rgn_bb_table
= xmalloc ((n_basic_blocks
) * sizeof (int));
2414 block_to_bb
= xmalloc ((last_basic_block
) * sizeof (int));
2415 containing_rgn
= xmalloc ((last_basic_block
) * sizeof (int));
2417 /* Compute regions for scheduling. */
2418 if (reload_completed
2419 || n_basic_blocks
== 1
2420 || !flag_schedule_interblock
2421 || is_cfg_nonregular ())
2423 find_single_block_region ();
2427 /* Compute the dominators and post dominators. */
2428 calculate_dominance_info (CDI_DOMINATORS
);
2433 if (sched_verbose
>= 3)
2436 /* For now. This will move as more and more of haifa is converted
2437 to using the cfg code in flow.c. */
2438 free_dominance_info (CDI_DOMINATORS
);
2442 if (CHECK_DEAD_NOTES
)
2444 blocks
= sbitmap_alloc (last_basic_block
);
2445 deaths_in_region
= xmalloc (sizeof (int) * nr_regions
);
2446 /* Remove all death notes from the subroutine. */
2447 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
2451 sbitmap_zero (blocks
);
2452 for (b
= RGN_NR_BLOCKS (rgn
) - 1; b
>= 0; --b
)
2453 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
) + b
]);
2455 deaths_in_region
[rgn
] = count_or_remove_death_notes (blocks
, 1);
2457 sbitmap_free (blocks
);
2460 count_or_remove_death_notes (NULL
, 1);
2463 /* The one entry point in this file. DUMP_FILE is the dump file for
2467 schedule_insns (FILE *dump_file
)
2469 sbitmap large_region_blocks
, blocks
;
2471 int any_large_regions
;
2474 /* Taking care of this degenerate case makes the rest of
2475 this code simpler. */
2476 if (n_basic_blocks
== 0)
2482 sched_init (dump_file
);
2486 current_sched_info
= ®ion_sched_info
;
2488 /* Schedule every region in the subroutine. */
2489 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
2490 schedule_region (rgn
);
2492 /* Update life analysis for the subroutine. Do single block regions
2493 first so that we can verify that live_at_start didn't change. Then
2494 do all other blocks. */
2495 /* ??? There is an outside possibility that update_life_info, or more
2496 to the point propagate_block, could get called with nonzero flags
2497 more than once for one basic block. This would be kinda bad if it
2498 were to happen, since REG_INFO would be accumulated twice for the
2499 block, and we'd have twice the REG_DEAD notes.
2501 I'm fairly certain that this _shouldn't_ happen, since I don't think
2502 that live_at_start should change at region heads. Not sure what the
2503 best way to test for this kind of thing... */
2505 allocate_reg_life_data ();
2506 compute_bb_for_insn ();
2508 any_large_regions
= 0;
2509 large_region_blocks
= sbitmap_alloc (last_basic_block
);
2510 sbitmap_zero (large_region_blocks
);
2512 SET_BIT (large_region_blocks
, bb
->index
);
2514 blocks
= sbitmap_alloc (last_basic_block
);
2515 sbitmap_zero (blocks
);
2517 /* Update life information. For regions consisting of multiple blocks
2518 we've possibly done interblock scheduling that affects global liveness.
2519 For regions consisting of single blocks we need to do only local
2521 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
2522 if (RGN_NR_BLOCKS (rgn
) > 1)
2523 any_large_regions
= 1;
2526 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
2527 RESET_BIT (large_region_blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
2530 /* Don't update reg info after reload, since that affects
2531 regs_ever_live, which should not change after reload. */
2532 update_life_info (blocks
, UPDATE_LIFE_LOCAL
,
2533 (reload_completed
? PROP_DEATH_NOTES
2534 : PROP_DEATH_NOTES
| PROP_REG_INFO
));
2535 if (any_large_regions
)
2537 update_life_info (large_region_blocks
, UPDATE_LIFE_GLOBAL
,
2538 PROP_DEATH_NOTES
| PROP_REG_INFO
);
2541 if (CHECK_DEAD_NOTES
)
2543 /* Verify the counts of basic block notes in single the basic block
2545 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
2546 if (RGN_NR_BLOCKS (rgn
) == 1)
2548 sbitmap_zero (blocks
);
2549 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
2551 gcc_assert (deaths_in_region
[rgn
]
2552 == count_or_remove_death_notes (blocks
, 0));
2554 free (deaths_in_region
);
2557 /* Reposition the prologue and epilogue notes in case we moved the
2558 prologue/epilogue insns. */
2559 if (reload_completed
)
2560 reposition_prologue_and_epilogue_notes (get_insns ());
2562 /* Delete redundant line notes. */
2563 if (write_symbols
!= NO_DEBUG
)
2564 rm_redundant_line_notes ();
2568 if (reload_completed
== 0 && flag_schedule_interblock
)
2570 fprintf (sched_dump
,
2571 "\n;; Procedure interblock/speculative motions == %d/%d \n",
2575 gcc_assert (nr_inter
<= 0);
2576 fprintf (sched_dump
, "\n\n");
2581 free (rgn_bb_table
);
2583 free (containing_rgn
);
2587 sbitmap_free (blocks
);
2588 sbitmap_free (large_region_blocks
);