1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004 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"
56 #include "basic-block.h"
60 #include "insn-config.h"
61 #include "insn-attr.h"
65 #include "cfglayout.h"
67 #include "sched-int.h"
70 /* Define when we want to do count REG_DEAD notes before and after scheduling
71 for sanity checking. We can't do that when conditional execution is used,
72 as REG_DEAD exist only for unconditional deaths. */
74 #if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING)
75 #define CHECK_DEAD_NOTES 1
77 #define CHECK_DEAD_NOTES 0
81 #ifdef INSN_SCHEDULING
82 /* Some accessor macros for h_i_d members only used within this file. */
83 #define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count)
84 #define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load)
85 #define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn)
87 /* nr_inter/spec counts interblock/speculative motion for the function. */
88 static int nr_inter, nr_spec;
90 /* Control flow graph edges are kept in circular lists. */
99 static haifa_edge *edge_table;
101 #define NEXT_IN(edge) (edge_table[edge].next_in)
102 #define NEXT_OUT(edge) (edge_table[edge].next_out)
103 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
104 #define TO_BLOCK(edge) (edge_table[edge].to_block)
106 /* Number of edges in the control flow graph. (In fact, larger than
107 that by 1, since edge 0 is unused.) */
110 /* Circular list of incoming/outgoing edges of a block. */
111 static int *in_edges;
112 static int *out_edges;
114 #define IN_EDGES(block) (in_edges[block])
115 #define OUT_EDGES(block) (out_edges[block])
117 static int is_cfg_nonregular (void);
118 static int build_control_flow (struct edge_list *);
119 static void new_edge (int, int);
120 static bool sched_is_disabled_for_current_region_p (void);
122 /* A region is the main entity for interblock scheduling: insns
123 are allowed to move between blocks in the same region, along
124 control flow graph edges, in the 'up' direction. */
127 int rgn_nr_blocks; /* Number of blocks in region. */
128 int rgn_blocks; /* cblocks in the region (actually index in rgn_bb_table). */
132 /* Number of regions in the procedure. */
133 static int nr_regions;
135 /* Table of region descriptions. */
136 static region *rgn_table;
138 /* Array of lists of regions' blocks. */
139 static int *rgn_bb_table;
141 /* Topological order of blocks in the region (if b2 is reachable from
142 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
143 always referred to by either block or b, while its topological
144 order name (in the region) is referred to by bb. */
145 static int *block_to_bb;
147 /* The number of the region containing a block. */
148 static int *containing_rgn;
150 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
151 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
152 #define BLOCK_TO_BB(block) (block_to_bb[block])
153 #define CONTAINING_RGN(block) (containing_rgn[block])
155 void debug_regions (void);
156 static void find_single_block_region (void);
157 static void find_rgns (struct edge_list *);
158 static bool too_large (int, int *, int *);
160 extern void debug_live (int, int);
162 /* Blocks of the current region being scheduled. */
163 static int current_nr_blocks;
164 static int current_blocks;
166 /* The mapping from bb to block. */
167 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
171 int *first_member; /* Pointer to the list start in bitlst_table. */
172 int nr_members; /* The number of members of the bit list. */
176 static int bitlst_table_last;
177 static int *bitlst_table;
179 static void extract_bitlst (sbitmap, bitlst *);
181 /* Target info declarations.
183 The block currently being scheduled is referred to as the "target" block,
184 while other blocks in the region from which insns can be moved to the
185 target are called "source" blocks. The candidate structure holds info
186 about such sources: are they valid? Speculative? Etc. */
187 typedef bitlst bblst;
198 static candidate *candidate_table;
200 /* A speculative motion requires checking live information on the path
201 from 'source' to 'target'. The split blocks are those to be checked.
202 After a speculative motion, live information should be modified in
205 Lists of split and update blocks for each candidate of the current
206 target are in array bblst_table. */
207 static int *bblst_table, bblst_size, bblst_last;
209 #define IS_VALID(src) ( candidate_table[src].is_valid )
210 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
211 #define SRC_PROB(src) ( candidate_table[src].src_prob )
213 /* The bb being currently scheduled. */
214 static int target_bb;
217 typedef bitlst edgelst;
219 /* Target info functions. */
220 static void split_edges (int, int, edgelst *);
221 static void compute_trg_info (int);
222 void debug_candidate (int);
223 void debug_candidates (int);
225 /* Dominators array: dom[i] contains the sbitmap of dominators of
226 bb i in the region. */
229 /* bb 0 is the only region entry. */
230 #define IS_RGN_ENTRY(bb) (!bb)
232 /* Is bb_src dominated by bb_trg. */
233 #define IS_DOMINATED(bb_src, bb_trg) \
234 ( TEST_BIT (dom[bb_src], bb_trg) )
236 /* Probability: Prob[i] is a float in [0, 1] which is the probability
237 of bb i relative to the region entry. */
240 /* The probability of bb_src, relative to bb_trg. Note, that while the
241 'prob[bb]' is a float in [0, 1], this macro returns an integer
243 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
246 /* Bit-set of edges, where bit i stands for edge i. */
247 typedef sbitmap edgeset;
249 /* Number of edges in the region. */
250 static int rgn_nr_edges;
252 /* Array of size rgn_nr_edges. */
253 static int *rgn_edges;
256 /* Mapping from each edge in the graph to its number in the rgn. */
257 static int *edge_to_bit;
258 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
260 /* The split edges of a source bb is different for each target
261 bb. In order to compute this efficiently, the 'potential-split edges'
262 are computed for each bb prior to scheduling a region. This is actually
263 the split edges of each bb relative to the region entry.
265 pot_split[bb] is the set of potential split edges of bb. */
266 static edgeset *pot_split;
268 /* For every bb, a set of its ancestor edges. */
269 static edgeset *ancestor_edges;
271 static void compute_dom_prob_ps (int);
273 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
274 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
275 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
277 /* Parameters affecting the decision of rank_for_schedule().
278 ??? Nope. But MIN_PROBABILITY is used in compute_trg_info. */
279 #define MIN_PROBABILITY 40
281 /* Speculative scheduling functions. */
282 static int check_live_1 (int, rtx);
283 static void update_live_1 (int, rtx);
284 static int check_live (rtx, int);
285 static void update_live (rtx, int);
286 static void set_spec_fed (rtx);
287 static int is_pfree (rtx, int, int);
288 static int find_conditional_protection (rtx, int);
289 static int is_conditionally_protected (rtx, int, int);
290 static int is_prisky (rtx, int, int);
291 static int is_exception_free (rtx, int, int);
293 static bool sets_likely_spilled (rtx);
294 static void sets_likely_spilled_1 (rtx, rtx, void *);
295 static void add_branch_dependences (rtx, rtx);
296 static void compute_block_backward_dependences (int);
297 void debug_dependencies (void);
299 static void init_regions (void);
300 static void schedule_region (int);
301 static rtx concat_INSN_LIST (rtx, rtx);
302 static void concat_insn_mem_list (rtx, rtx, rtx *, rtx *);
303 static void propagate_deps (int, struct deps *);
304 static void free_pending_lists (void);
306 /* Functions for construction of the control flow graph. */
308 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
310 We decide not to build the control flow graph if there is possibly more
311 than one entry to the function, if computed branches exist, of if we
312 have nonlocal gotos. */
315 is_cfg_nonregular (void)
321 /* If we have a label that could be the target of a nonlocal goto, then
322 the cfg is not well structured. */
323 if (nonlocal_goto_handler_labels)
326 /* If we have any forced labels, then the cfg is not well structured. */
330 /* If this function has a computed jump, then we consider the cfg
331 not well structured. */
332 if (current_function_has_computed_jump)
335 /* If we have exception handlers, then we consider the cfg not well
336 structured. ?!? We should be able to handle this now that flow.c
337 computes an accurate cfg for EH. */
338 if (current_function_has_exception_handlers ())
341 /* If we have non-jumping insns which refer to labels, then we consider
342 the cfg not well structured. */
343 /* Check for labels referred to other thn by jumps. */
345 for (insn = BB_HEAD (b); ; insn = NEXT_INSN (insn))
347 code = GET_CODE (insn);
348 if (INSN_P (insn) && code != JUMP_INSN)
350 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
353 && ! (JUMP_P (NEXT_INSN (insn))
354 && find_reg_note (NEXT_INSN (insn), REG_LABEL,
359 if (insn == BB_END (b))
363 /* All the tests passed. Consider the cfg well structured. */
367 /* Build the control flow graph and set nr_edges.
369 Instead of trying to build a cfg ourselves, we rely on flow to
370 do it for us. Stamp out useless code (and bug) duplication.
372 Return nonzero if an irregularity in the cfg is found which would
373 prevent cross block scheduling. */
376 build_control_flow (struct edge_list *edge_list)
378 int i, unreachable, num_edges;
381 /* This already accounts for entry/exit edges. */
382 num_edges = NUM_EDGES (edge_list);
384 /* Unreachable loops with more than one basic block are detected
385 during the DFS traversal in find_rgns.
387 Unreachable loops with a single block are detected here. This
388 test is redundant with the one in find_rgns, but it's much
389 cheaper to go ahead and catch the trivial case here. */
393 if (EDGE_COUNT (b->preds) == 0
394 || (EDGE_PRED (b, 0)->src == b
395 && EDGE_COUNT (b->preds) == 1))
399 /* ??? We can kill these soon. */
400 in_edges = xcalloc (last_basic_block, sizeof (int));
401 out_edges = xcalloc (last_basic_block, sizeof (int));
402 edge_table = xcalloc (num_edges, sizeof (haifa_edge));
405 for (i = 0; i < num_edges; i++)
407 edge e = INDEX_EDGE (edge_list, i);
409 if (e->dest != EXIT_BLOCK_PTR
410 && e->src != ENTRY_BLOCK_PTR)
411 new_edge (e->src->index, e->dest->index);
414 /* Increment by 1, since edge 0 is unused. */
420 /* Record an edge in the control flow graph from SOURCE to TARGET.
422 In theory, this is redundant with the s_succs computed above, but
423 we have not converted all of haifa to use information from the
427 new_edge (int source, int target)
430 int curr_edge, fst_edge;
432 /* Check for duplicates. */
433 fst_edge = curr_edge = OUT_EDGES (source);
436 if (FROM_BLOCK (curr_edge) == source
437 && TO_BLOCK (curr_edge) == target)
442 curr_edge = NEXT_OUT (curr_edge);
444 if (fst_edge == curr_edge)
450 FROM_BLOCK (e) = source;
451 TO_BLOCK (e) = target;
453 if (OUT_EDGES (source))
455 next_edge = NEXT_OUT (OUT_EDGES (source));
456 NEXT_OUT (OUT_EDGES (source)) = e;
457 NEXT_OUT (e) = next_edge;
461 OUT_EDGES (source) = e;
465 if (IN_EDGES (target))
467 next_edge = NEXT_IN (IN_EDGES (target));
468 NEXT_IN (IN_EDGES (target)) = e;
469 NEXT_IN (e) = next_edge;
473 IN_EDGES (target) = e;
478 /* Translate a bit-set SET to a list BL of the bit-set members. */
481 extract_bitlst (sbitmap set, bitlst *bl)
485 /* bblst table space is reused in each call to extract_bitlst. */
486 bitlst_table_last = 0;
488 bl->first_member = &bitlst_table[bitlst_table_last];
491 /* Iterate over each word in the bitset. */
492 EXECUTE_IF_SET_IN_SBITMAP (set, 0, i,
494 bitlst_table[bitlst_table_last++] = i;
500 /* Functions for the construction of regions. */
502 /* Print the regions, for debugging purposes. Callable from debugger. */
509 fprintf (sched_dump, "\n;; ------------ REGIONS ----------\n\n");
510 for (rgn = 0; rgn < nr_regions; rgn++)
512 fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
513 rgn_table[rgn].rgn_nr_blocks);
514 fprintf (sched_dump, ";;\tbb/block: ");
516 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
518 current_blocks = RGN_BLOCKS (rgn);
520 gcc_assert (bb == BLOCK_TO_BB (BB_TO_BLOCK (bb)));
521 fprintf (sched_dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
524 fprintf (sched_dump, "\n\n");
528 /* Build a single block region for each basic block in the function.
529 This allows for using the same code for interblock and basic block
533 find_single_block_region (void)
541 rgn_bb_table[nr_regions] = bb->index;
542 RGN_NR_BLOCKS (nr_regions) = 1;
543 RGN_BLOCKS (nr_regions) = nr_regions;
544 CONTAINING_RGN (bb->index) = nr_regions;
545 BLOCK_TO_BB (bb->index) = 0;
550 /* Update number of blocks and the estimate for number of insns
551 in the region. Return true if the region is "too large" for interblock
552 scheduling (compile time considerations). */
555 too_large (int block, int *num_bbs, int *num_insns)
558 (*num_insns) += (INSN_LUID (BB_END (BASIC_BLOCK (block)))
559 - INSN_LUID (BB_HEAD (BASIC_BLOCK (block))));
561 return ((*num_bbs > PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS))
562 || (*num_insns > PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS)));
565 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
566 is still an inner loop. Put in max_hdr[blk] the header of the most inner
567 loop containing blk. */
568 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
570 if (max_hdr[blk] == -1) \
571 max_hdr[blk] = hdr; \
572 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
573 RESET_BIT (inner, hdr); \
574 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
576 RESET_BIT (inner,max_hdr[blk]); \
577 max_hdr[blk] = hdr; \
581 /* Find regions for interblock scheduling.
583 A region for scheduling can be:
585 * A loop-free procedure, or
587 * A reducible inner loop, or
589 * A basic block not contained in any other region.
591 ?!? In theory we could build other regions based on extended basic
592 blocks or reverse extended basic blocks. Is it worth the trouble?
594 Loop blocks that form a region are put into the region's block list
595 in topological order.
597 This procedure stores its results into the following global (ick) variables
605 We use dominator relationships to avoid making regions out of non-reducible
608 This procedure needs to be converted to work on pred/succ lists instead
609 of edge tables. That would simplify it somewhat. */
612 find_rgns (struct edge_list *edge_list)
614 int *max_hdr, *dfs_nr, *stack, *degree;
616 int node, child, loop_head, i, head, tail;
617 int count = 0, sp, idx = 0;
618 int current_edge = out_edges[EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest->index];
619 int num_bbs, num_insns, unreachable;
620 int too_large_failure;
623 /* Note if an edge has been passed. */
626 /* Note if a block is a natural loop header. */
629 /* Note if a block is a natural inner loop header. */
632 /* Note if a block is in the block queue. */
635 /* Note if a block is in the block queue. */
638 int num_edges = NUM_EDGES (edge_list);
640 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
641 and a mapping from block to its loop header (if the block is contained
644 Store results in HEADER, INNER, and MAX_HDR respectively, these will
645 be used as inputs to the second traversal.
647 STACK, SP and DFS_NR are only used during the first traversal. */
649 /* Allocate and initialize variables for the first traversal. */
650 max_hdr = xmalloc (last_basic_block * sizeof (int));
651 dfs_nr = xcalloc (last_basic_block, sizeof (int));
652 stack = xmalloc (nr_edges * sizeof (int));
654 inner = sbitmap_alloc (last_basic_block);
655 sbitmap_ones (inner);
657 header = sbitmap_alloc (last_basic_block);
658 sbitmap_zero (header);
660 passed = sbitmap_alloc (nr_edges);
661 sbitmap_zero (passed);
663 in_queue = sbitmap_alloc (last_basic_block);
664 sbitmap_zero (in_queue);
666 in_stack = sbitmap_alloc (last_basic_block);
667 sbitmap_zero (in_stack);
669 for (i = 0; i < last_basic_block; i++)
672 /* DFS traversal to find inner loops in the cfg. */
677 if (current_edge == 0 || TEST_BIT (passed, current_edge))
679 /* We have reached a leaf node or a node that was already
680 processed. Pop edges off the stack until we find
681 an edge that has not yet been processed. */
683 && (current_edge == 0 || TEST_BIT (passed, current_edge)))
685 /* Pop entry off the stack. */
686 current_edge = stack[sp--];
687 node = FROM_BLOCK (current_edge);
688 child = TO_BLOCK (current_edge);
689 RESET_BIT (in_stack, child);
690 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
691 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
692 current_edge = NEXT_OUT (current_edge);
695 /* See if have finished the DFS tree traversal. */
696 if (sp < 0 && TEST_BIT (passed, current_edge))
699 /* Nope, continue the traversal with the popped node. */
703 /* Process a node. */
704 node = FROM_BLOCK (current_edge);
705 child = TO_BLOCK (current_edge);
706 SET_BIT (in_stack, node);
707 dfs_nr[node] = ++count;
709 /* If the successor is in the stack, then we've found a loop.
710 Mark the loop, if it is not a natural loop, then it will
711 be rejected during the second traversal. */
712 if (TEST_BIT (in_stack, child))
715 SET_BIT (header, child);
716 UPDATE_LOOP_RELATIONS (node, child);
717 SET_BIT (passed, current_edge);
718 current_edge = NEXT_OUT (current_edge);
722 /* If the child was already visited, then there is no need to visit
723 it again. Just update the loop relationships and restart
727 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
728 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
729 SET_BIT (passed, current_edge);
730 current_edge = NEXT_OUT (current_edge);
734 /* Push an entry on the stack and continue DFS traversal. */
735 stack[++sp] = current_edge;
736 SET_BIT (passed, current_edge);
737 current_edge = OUT_EDGES (child);
739 /* This is temporary until haifa is converted to use rth's new
740 cfg routines which have true entry/exit blocks and the
741 appropriate edges from/to those blocks.
743 Generally we update dfs_nr for a node when we process its
744 out edge. However, if the node has no out edge then we will
745 not set dfs_nr for that node. This can confuse the scheduler
746 into thinking that we have unreachable blocks, which in turn
747 disables cross block scheduling.
749 So, if we have a node with no out edges, go ahead and mark it
751 if (current_edge == 0)
752 dfs_nr[child] = ++count;
755 /* Another check for unreachable blocks. The earlier test in
756 is_cfg_nonregular only finds unreachable blocks that do not
759 The DFS traversal will mark every block that is reachable from
760 the entry node by placing a nonzero value in dfs_nr. Thus if
761 dfs_nr is zero for any block, then it must be unreachable. */
764 if (dfs_nr[bb->index] == 0)
770 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
771 to hold degree counts. */
775 degree[bb->index] = 0;
776 for (i = 0; i < num_edges; i++)
778 edge e = INDEX_EDGE (edge_list, i);
780 if (e->dest != EXIT_BLOCK_PTR)
781 degree[e->dest->index]++;
784 /* Do not perform region scheduling if there are any unreachable
793 /* Second traversal:find reducible inner loops and topologically sort
794 block of each region. */
796 queue = xmalloc (n_basic_blocks * sizeof (int));
798 /* Find blocks which are inner loop headers. We still have non-reducible
799 loops to consider at this point. */
802 if (TEST_BIT (header, bb->index) && TEST_BIT (inner, bb->index))
808 /* Now check that the loop is reducible. We do this separate
809 from finding inner loops so that we do not find a reducible
810 loop which contains an inner non-reducible loop.
812 A simple way to find reducible/natural loops is to verify
813 that each block in the loop is dominated by the loop
816 If there exists a block that is not dominated by the loop
817 header, then the block is reachable from outside the loop
818 and thus the loop is not a natural loop. */
821 /* First identify blocks in the loop, except for the loop
823 if (bb->index == max_hdr[jbb->index] && bb != jbb)
825 /* Now verify that the block is dominated by the loop
827 if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))
832 /* If we exited the loop early, then I is the header of
833 a non-reducible loop and we should quit processing it
835 if (jbb != EXIT_BLOCK_PTR)
838 /* I is a header of an inner loop, or block 0 in a subroutine
839 with no loops at all. */
841 too_large_failure = 0;
842 loop_head = max_hdr[bb->index];
844 /* Decrease degree of all I's successors for topological
846 FOR_EACH_EDGE (e, ei, bb->succs)
847 if (e->dest != EXIT_BLOCK_PTR)
848 --degree[e->dest->index];
850 /* Estimate # insns, and count # blocks in the region. */
852 num_insns = (INSN_LUID (BB_END (bb))
853 - INSN_LUID (BB_HEAD (bb)));
855 /* Find all loop latches (blocks with back edges to the loop
856 header) or all the leaf blocks in the cfg has no loops.
858 Place those blocks into the queue. */
862 /* Leaf nodes have only a single successor which must
864 if (EDGE_COUNT (jbb->succs) == 1
865 && EDGE_SUCC (jbb, 0)->dest == EXIT_BLOCK_PTR)
867 queue[++tail] = jbb->index;
868 SET_BIT (in_queue, jbb->index);
870 if (too_large (jbb->index, &num_bbs, &num_insns))
872 too_large_failure = 1;
881 FOR_EACH_EDGE (e, ei, bb->preds)
883 if (e->src == ENTRY_BLOCK_PTR)
886 node = e->src->index;
888 if (max_hdr[node] == loop_head && node != bb->index)
890 /* This is a loop latch. */
891 queue[++tail] = node;
892 SET_BIT (in_queue, node);
894 if (too_large (node, &num_bbs, &num_insns))
896 too_large_failure = 1;
903 /* Now add all the blocks in the loop to the queue.
905 We know the loop is a natural loop; however the algorithm
906 above will not always mark certain blocks as being in the
914 The algorithm in the DFS traversal may not mark B & D as part
915 of the loop (i.e. they will not have max_hdr set to A).
917 We know they can not be loop latches (else they would have
918 had max_hdr set since they'd have a backedge to a dominator
919 block). So we don't need them on the initial queue.
921 We know they are part of the loop because they are dominated
922 by the loop header and can be reached by a backwards walk of
923 the edges starting with nodes on the initial queue.
925 It is safe and desirable to include those nodes in the
926 loop/scheduling region. To do so we would need to decrease
927 the degree of a node if it is the target of a backedge
928 within the loop itself as the node is placed in the queue.
930 We do not do this because I'm not sure that the actual
931 scheduling code will properly handle this case. ?!? */
933 while (head < tail && !too_large_failure)
936 child = queue[++head];
938 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->preds)
940 node = e->src->index;
942 /* See discussion above about nodes not marked as in
943 this loop during the initial DFS traversal. */
944 if (e->src == ENTRY_BLOCK_PTR
945 || max_hdr[node] != loop_head)
950 else if (!TEST_BIT (in_queue, node) && node != bb->index)
952 queue[++tail] = node;
953 SET_BIT (in_queue, node);
955 if (too_large (node, &num_bbs, &num_insns))
957 too_large_failure = 1;
964 if (tail >= 0 && !too_large_failure)
966 /* Place the loop header into list of region blocks. */
967 degree[bb->index] = -1;
968 rgn_bb_table[idx] = bb->index;
969 RGN_NR_BLOCKS (nr_regions) = num_bbs;
970 RGN_BLOCKS (nr_regions) = idx++;
971 CONTAINING_RGN (bb->index) = nr_regions;
972 BLOCK_TO_BB (bb->index) = count = 0;
974 /* Remove blocks from queue[] when their in degree
975 becomes zero. Repeat until no blocks are left on the
976 list. This produces a topological list of blocks in
983 if (degree[child] == 0)
988 rgn_bb_table[idx++] = child;
989 BLOCK_TO_BB (child) = ++count;
990 CONTAINING_RGN (child) = nr_regions;
991 queue[head] = queue[tail--];
993 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->succs)
994 if (e->dest != EXIT_BLOCK_PTR)
995 --degree[e->dest->index];
1007 /* Any block that did not end up in a region is placed into a region
1010 if (degree[bb->index] >= 0)
1012 rgn_bb_table[idx] = bb->index;
1013 RGN_NR_BLOCKS (nr_regions) = 1;
1014 RGN_BLOCKS (nr_regions) = idx++;
1015 CONTAINING_RGN (bb->index) = nr_regions++;
1016 BLOCK_TO_BB (bb->index) = 0;
1022 sbitmap_free (passed);
1023 sbitmap_free (header);
1024 sbitmap_free (inner);
1025 sbitmap_free (in_queue);
1026 sbitmap_free (in_stack);
1029 /* Functions for regions scheduling information. */
1031 /* Compute dominators, probability, and potential-split-edges of bb.
1032 Assume that these values were already computed for bb's predecessors. */
1035 compute_dom_prob_ps (int bb)
1037 int nxt_in_edge, fst_in_edge, pred;
1038 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1041 if (IS_RGN_ENTRY (bb))
1043 SET_BIT (dom[bb], 0);
1048 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1050 /* Initialize dom[bb] to '111..1'. */
1051 sbitmap_ones (dom[bb]);
1055 pred = FROM_BLOCK (nxt_in_edge);
1056 sbitmap_a_and_b (dom[bb], dom[bb], dom[BLOCK_TO_BB (pred)]);
1057 sbitmap_a_or_b (ancestor_edges[bb], ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)]);
1059 SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge));
1062 nr_rgn_out_edges = 0;
1063 fst_out_edge = OUT_EDGES (pred);
1064 nxt_out_edge = NEXT_OUT (fst_out_edge);
1066 sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[BLOCK_TO_BB (pred)]);
1068 SET_BIT (pot_split[bb], EDGE_TO_BIT (fst_out_edge));
1070 /* The successor doesn't belong in the region? */
1071 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1072 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1075 while (fst_out_edge != nxt_out_edge)
1078 /* The successor doesn't belong in the region? */
1079 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1080 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1082 SET_BIT (pot_split[bb], EDGE_TO_BIT (nxt_out_edge));
1083 nxt_out_edge = NEXT_OUT (nxt_out_edge);
1087 /* Now nr_rgn_out_edges is the number of region-exit edges from
1088 pred, and nr_out_edges will be the number of pred out edges
1089 not leaving the region. */
1090 nr_out_edges -= nr_rgn_out_edges;
1091 if (nr_rgn_out_edges > 0)
1092 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1094 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1095 nxt_in_edge = NEXT_IN (nxt_in_edge);
1097 while (fst_in_edge != nxt_in_edge);
1099 SET_BIT (dom[bb], bb);
1100 sbitmap_difference (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
1102 if (sched_verbose >= 2)
1103 fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
1104 (int) (100.0 * prob[bb]));
1107 /* Functions for target info. */
1109 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1110 Note that bb_trg dominates bb_src. */
1113 split_edges (int bb_src, int bb_trg, edgelst *bl)
1115 sbitmap src = sbitmap_alloc (pot_split[bb_src]->n_bits);
1116 sbitmap_copy (src, pot_split[bb_src]);
1118 sbitmap_difference (src, src, pot_split[bb_trg]);
1119 extract_bitlst (src, bl);
1123 /* Find the valid candidate-source-blocks for the target block TRG, compute
1124 their probability, and check if they are speculative or not.
1125 For speculative sources, compute their update-blocks and split-blocks. */
1128 compute_trg_info (int trg)
1132 int check_block, update_idx;
1133 int i, j, k, fst_edge, nxt_edge;
1135 /* Define some of the fields for the target bb as well. */
1136 sp = candidate_table + trg;
1138 sp->is_speculative = 0;
1141 for (i = trg + 1; i < current_nr_blocks; i++)
1143 sp = candidate_table + i;
1145 sp->is_valid = IS_DOMINATED (i, trg);
1148 sp->src_prob = GET_SRC_PROB (i, trg);
1149 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
1154 split_edges (i, trg, &el);
1155 sp->is_speculative = (el.nr_members) ? 1 : 0;
1156 if (sp->is_speculative && !flag_schedule_speculative)
1162 char *update_blocks;
1164 /* Compute split blocks and store them in bblst_table.
1165 The TO block of every split edge is a split block. */
1166 sp->split_bbs.first_member = &bblst_table[bblst_last];
1167 sp->split_bbs.nr_members = el.nr_members;
1168 for (j = 0; j < el.nr_members; bblst_last++, j++)
1169 bblst_table[bblst_last] =
1170 TO_BLOCK (rgn_edges[el.first_member[j]]);
1171 sp->update_bbs.first_member = &bblst_table[bblst_last];
1173 /* Compute update blocks and store them in bblst_table.
1174 For every split edge, look at the FROM block, and check
1175 all out edges. For each out edge that is not a split edge,
1176 add the TO block to the update block list. This list can end
1177 up with a lot of duplicates. We need to weed them out to avoid
1178 overrunning the end of the bblst_table. */
1179 update_blocks = alloca (last_basic_block);
1180 memset (update_blocks, 0, last_basic_block);
1183 for (j = 0; j < el.nr_members; j++)
1185 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
1186 fst_edge = nxt_edge = OUT_EDGES (check_block);
1189 if (! update_blocks[TO_BLOCK (nxt_edge)])
1191 for (k = 0; k < el.nr_members; k++)
1192 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
1195 if (k >= el.nr_members)
1197 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
1198 update_blocks[TO_BLOCK (nxt_edge)] = 1;
1203 nxt_edge = NEXT_OUT (nxt_edge);
1205 while (fst_edge != nxt_edge);
1207 sp->update_bbs.nr_members = update_idx;
1209 /* Make sure we didn't overrun the end of bblst_table. */
1210 gcc_assert (bblst_last <= bblst_size);
1214 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1216 sp->is_speculative = 0;
1222 /* Print candidates info, for debugging purposes. Callable from debugger. */
1225 debug_candidate (int i)
1227 if (!candidate_table[i].is_valid)
1230 if (candidate_table[i].is_speculative)
1233 fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1235 fprintf (sched_dump, "split path: ");
1236 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1238 int b = candidate_table[i].split_bbs.first_member[j];
1240 fprintf (sched_dump, " %d ", b);
1242 fprintf (sched_dump, "\n");
1244 fprintf (sched_dump, "update path: ");
1245 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
1247 int b = candidate_table[i].update_bbs.first_member[j];
1249 fprintf (sched_dump, " %d ", b);
1251 fprintf (sched_dump, "\n");
1255 fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
1259 /* Print candidates info, for debugging purposes. Callable from debugger. */
1262 debug_candidates (int trg)
1266 fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
1267 BB_TO_BLOCK (trg), trg);
1268 for (i = trg + 1; i < current_nr_blocks; i++)
1269 debug_candidate (i);
1272 /* Functions for speculative scheduling. */
1274 /* Return 0 if x is a set of a register alive in the beginning of one
1275 of the split-blocks of src, otherwise return 1. */
1278 check_live_1 (int src, rtx x)
1282 rtx reg = SET_DEST (x);
1287 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
1288 || GET_CODE (reg) == SIGN_EXTRACT
1289 || GET_CODE (reg) == STRICT_LOW_PART)
1290 reg = XEXP (reg, 0);
1292 if (GET_CODE (reg) == PARALLEL)
1296 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1297 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1298 if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
1307 regno = REGNO (reg);
1309 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1311 /* Global registers are assumed live. */
1316 if (regno < FIRST_PSEUDO_REGISTER)
1318 /* Check for hard registers. */
1319 int j = hard_regno_nregs[regno][GET_MODE (reg)];
1322 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1324 int b = candidate_table[src].split_bbs.first_member[i];
1326 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
1336 /* Check for pseudo registers. */
1337 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1339 int b = candidate_table[src].split_bbs.first_member[i];
1341 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
1352 /* If x is a set of a register R, mark that R is alive in the beginning
1353 of every update-block of src. */
1356 update_live_1 (int src, rtx x)
1360 rtx reg = SET_DEST (x);
1365 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
1366 || GET_CODE (reg) == SIGN_EXTRACT
1367 || GET_CODE (reg) == STRICT_LOW_PART)
1368 reg = XEXP (reg, 0);
1370 if (GET_CODE (reg) == PARALLEL)
1374 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1375 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1376 update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
1384 /* Global registers are always live, so the code below does not apply
1387 regno = REGNO (reg);
1389 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
1391 if (regno < FIRST_PSEUDO_REGISTER)
1393 int j = hard_regno_nregs[regno][GET_MODE (reg)];
1396 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1398 int b = candidate_table[src].update_bbs.first_member[i];
1400 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
1407 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1409 int b = candidate_table[src].update_bbs.first_member[i];
1411 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
1417 /* Return 1 if insn can be speculatively moved from block src to trg,
1418 otherwise return 0. Called before first insertion of insn to
1419 ready-list or before the scheduling. */
1422 check_live (rtx insn, int src)
1424 /* Find the registers set by instruction. */
1425 if (GET_CODE (PATTERN (insn)) == SET
1426 || GET_CODE (PATTERN (insn)) == CLOBBER)
1427 return check_live_1 (src, PATTERN (insn));
1428 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1431 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1432 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1433 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1434 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
1443 /* Update the live registers info after insn was moved speculatively from
1444 block src to trg. */
1447 update_live (rtx insn, int src)
1449 /* Find the registers set by instruction. */
1450 if (GET_CODE (PATTERN (insn)) == SET
1451 || GET_CODE (PATTERN (insn)) == CLOBBER)
1452 update_live_1 (src, PATTERN (insn));
1453 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1456 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1457 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1458 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1459 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
1463 /* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1464 #define IS_REACHABLE(bb_from, bb_to) \
1466 || IS_RGN_ENTRY (bb_from) \
1467 || (TEST_BIT (ancestor_edges[bb_to], \
1468 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))))))
1470 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1473 set_spec_fed (rtx load_insn)
1477 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
1478 if (GET_MODE (link) == VOIDmode)
1479 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
1480 } /* set_spec_fed */
1482 /* On the path from the insn to load_insn_bb, find a conditional
1483 branch depending on insn, that guards the speculative load. */
1486 find_conditional_protection (rtx insn, int load_insn_bb)
1490 /* Iterate through DEF-USE forward dependences. */
1491 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
1493 rtx next = XEXP (link, 0);
1494 if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
1495 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
1496 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
1497 && load_insn_bb != INSN_BB (next)
1498 && GET_MODE (link) == VOIDmode
1500 || find_conditional_protection (next, load_insn_bb)))
1504 } /* find_conditional_protection */
1506 /* Returns 1 if the same insn1 that participates in the computation
1507 of load_insn's address is feeding a conditional branch that is
1508 guarding on load_insn. This is true if we find a the two DEF-USE
1510 insn1 -> ... -> conditional-branch
1511 insn1 -> ... -> load_insn,
1512 and if a flow path exist:
1513 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1514 and if insn1 is on the path
1515 region-entry -> ... -> bb_trg -> ... load_insn.
1517 Locate insn1 by climbing on LOG_LINKS from load_insn.
1518 Locate the branch by following INSN_DEPEND from insn1. */
1521 is_conditionally_protected (rtx load_insn, int bb_src, int bb_trg)
1525 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
1527 rtx insn1 = XEXP (link, 0);
1529 /* Must be a DEF-USE dependence upon non-branch. */
1530 if (GET_MODE (link) != VOIDmode
1534 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1535 if (INSN_BB (insn1) == bb_src
1536 || (CONTAINING_RGN (BLOCK_NUM (insn1))
1537 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
1538 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
1539 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
1542 /* Now search for the conditional-branch. */
1543 if (find_conditional_protection (insn1, bb_src))
1546 /* Recursive step: search another insn1, "above" current insn1. */
1547 return is_conditionally_protected (insn1, bb_src, bb_trg);
1550 /* The chain does not exist. */
1552 } /* is_conditionally_protected */
1554 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1555 load_insn can move speculatively from bb_src to bb_trg. All the
1556 following must hold:
1558 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1559 (2) load_insn and load1 have a def-use dependence upon
1560 the same insn 'insn1'.
1561 (3) either load2 is in bb_trg, or:
1562 - there's only one split-block, and
1563 - load1 is on the escape path, and
1565 From all these we can conclude that the two loads access memory
1566 addresses that differ at most by a constant, and hence if moving
1567 load_insn would cause an exception, it would have been caused by
1571 is_pfree (rtx load_insn, int bb_src, int bb_trg)
1574 candidate *candp = candidate_table + bb_src;
1576 if (candp->split_bbs.nr_members != 1)
1577 /* Must have exactly one escape block. */
1580 for (back_link = LOG_LINKS (load_insn);
1581 back_link; back_link = XEXP (back_link, 1))
1583 rtx insn1 = XEXP (back_link, 0);
1585 if (GET_MODE (back_link) == VOIDmode)
1587 /* Found a DEF-USE dependence (insn1, load_insn). */
1590 for (fore_link = INSN_DEPEND (insn1);
1591 fore_link; fore_link = XEXP (fore_link, 1))
1593 rtx insn2 = XEXP (fore_link, 0);
1594 if (GET_MODE (fore_link) == VOIDmode)
1596 /* Found a DEF-USE dependence (insn1, insn2). */
1597 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
1598 /* insn2 not guaranteed to be a 1 base reg load. */
1601 if (INSN_BB (insn2) == bb_trg)
1602 /* insn2 is the similar load, in the target block. */
1605 if (*(candp->split_bbs.first_member) == BLOCK_NUM (insn2))
1606 /* insn2 is a similar load, in a split-block. */
1613 /* Couldn't find a similar load. */
1617 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1618 a load moved speculatively, or if load_insn is protected by
1619 a compare on load_insn's address). */
1622 is_prisky (rtx load_insn, int bb_src, int bb_trg)
1624 if (FED_BY_SPEC_LOAD (load_insn))
1627 if (LOG_LINKS (load_insn) == NULL)
1628 /* Dependence may 'hide' out of the region. */
1631 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
1637 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
1638 Return 1 if insn is exception-free (and the motion is valid)
1642 is_exception_free (rtx insn, int bb_src, int bb_trg)
1644 int insn_class = haifa_classify_insn (insn);
1646 /* Handle non-load insns. */
1657 if (!flag_schedule_speculative_load)
1659 IS_LOAD_INSN (insn) = 1;
1666 case PFREE_CANDIDATE:
1667 if (is_pfree (insn, bb_src, bb_trg))
1669 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
1670 case PRISKY_CANDIDATE:
1671 if (!flag_schedule_speculative_load_dangerous
1672 || is_prisky (insn, bb_src, bb_trg))
1678 return flag_schedule_speculative_load_dangerous;
1681 /* The number of insns from the current block scheduled so far. */
1682 static int sched_target_n_insns;
1683 /* The number of insns from the current block to be scheduled in total. */
1684 static int target_n_insns;
1685 /* The number of insns from the entire region scheduled so far. */
1686 static int sched_n_insns;
1687 /* Nonzero if the last scheduled insn was a jump. */
1688 static int last_was_jump;
1690 /* Implementations of the sched_info functions for region scheduling. */
1691 static void init_ready_list (struct ready_list *);
1692 static int can_schedule_ready_p (rtx);
1693 static int new_ready (rtx);
1694 static int schedule_more_p (void);
1695 static const char *rgn_print_insn (rtx, int);
1696 static int rgn_rank (rtx, rtx);
1697 static int contributes_to_priority (rtx, rtx);
1698 static void compute_jump_reg_dependencies (rtx, regset, regset, regset);
1700 /* Return nonzero if there are more insns that should be scheduled. */
1703 schedule_more_p (void)
1705 return ! last_was_jump && sched_target_n_insns < target_n_insns;
1708 /* Add all insns that are initially ready to the ready list READY. Called
1709 once before scheduling a set of insns. */
1712 init_ready_list (struct ready_list *ready)
1714 rtx prev_head = current_sched_info->prev_head;
1715 rtx next_tail = current_sched_info->next_tail;
1720 sched_target_n_insns = 0;
1724 /* Print debugging information. */
1725 if (sched_verbose >= 5)
1726 debug_dependencies ();
1728 /* Prepare current target block info. */
1729 if (current_nr_blocks > 1)
1731 candidate_table = xmalloc (current_nr_blocks * sizeof (candidate));
1734 /* bblst_table holds split blocks and update blocks for each block after
1735 the current one in the region. split blocks and update blocks are
1736 the TO blocks of region edges, so there can be at most rgn_nr_edges
1738 bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
1739 bblst_table = xmalloc (bblst_size * sizeof (int));
1741 bitlst_table_last = 0;
1742 bitlst_table = xmalloc (rgn_nr_edges * sizeof (int));
1744 compute_trg_info (target_bb);
1747 /* Initialize ready list with all 'ready' insns in target block.
1748 Count number of insns in the target block being scheduled. */
1749 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
1751 if (INSN_DEP_COUNT (insn) == 0)
1753 ready_add (ready, insn);
1755 if (targetm.sched.adjust_priority)
1756 INSN_PRIORITY (insn) =
1757 targetm.sched.adjust_priority (insn, INSN_PRIORITY (insn));
1762 /* Add to ready list all 'ready' insns in valid source blocks.
1763 For speculative insns, check-live, exception-free, and
1765 for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
1766 if (IS_VALID (bb_src))
1772 get_block_head_tail (BB_TO_BLOCK (bb_src), &head, &tail);
1773 src_next_tail = NEXT_INSN (tail);
1776 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
1778 if (! INSN_P (insn))
1781 if (!CANT_MOVE (insn)
1782 && (!IS_SPECULATIVE_INSN (insn)
1783 || ((recog_memoized (insn) < 0
1784 || min_insn_conflict_delay (curr_state,
1786 && check_live (insn, bb_src)
1787 && is_exception_free (insn, bb_src, target_bb))))
1788 if (INSN_DEP_COUNT (insn) == 0)
1790 ready_add (ready, insn);
1792 if (targetm.sched.adjust_priority)
1793 INSN_PRIORITY (insn) =
1794 targetm.sched.adjust_priority (insn, INSN_PRIORITY (insn));
1800 /* Called after taking INSN from the ready list. Returns nonzero if this
1801 insn can be scheduled, nonzero if we should silently discard it. */
1804 can_schedule_ready_p (rtx insn)
1809 /* An interblock motion? */
1810 if (INSN_BB (insn) != target_bb)
1814 if (IS_SPECULATIVE_INSN (insn))
1816 if (!check_live (insn, INSN_BB (insn)))
1818 update_live (insn, INSN_BB (insn));
1820 /* For speculative load, mark insns fed by it. */
1821 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
1822 set_spec_fed (insn);
1828 /* Update source block boundaries. */
1829 b1 = BLOCK_FOR_INSN (insn);
1830 if (insn == BB_HEAD (b1) && insn == BB_END (b1))
1832 /* We moved all the insns in the basic block.
1833 Emit a note after the last insn and update the
1834 begin/end boundaries to point to the note. */
1835 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
1836 BB_HEAD (b1) = note;
1839 else if (insn == BB_END (b1))
1841 /* We took insns from the end of the basic block,
1842 so update the end of block boundary so that it
1843 points to the first insn we did not move. */
1844 BB_END (b1) = PREV_INSN (insn);
1846 else if (insn == BB_HEAD (b1))
1848 /* We took insns from the start of the basic block,
1849 so update the start of block boundary so that
1850 it points to the first insn we did not move. */
1851 BB_HEAD (b1) = NEXT_INSN (insn);
1856 /* In block motion. */
1857 sched_target_n_insns++;
1864 /* Called after INSN has all its dependencies resolved. Return nonzero
1865 if it should be moved to the ready list or the queue, or zero if we
1866 should silently discard it. */
1868 new_ready (rtx next)
1870 /* For speculative insns, before inserting to ready/queue,
1871 check live, exception-free, and issue-delay. */
1872 if (INSN_BB (next) != target_bb
1873 && (!IS_VALID (INSN_BB (next))
1875 || (IS_SPECULATIVE_INSN (next)
1876 && ((recog_memoized (next) >= 0
1877 && min_insn_conflict_delay (curr_state, next, next) > 3)
1878 || !check_live (next, INSN_BB (next))
1879 || !is_exception_free (next, INSN_BB (next), target_bb)))))
1884 /* Return a string that contains the insn uid and optionally anything else
1885 necessary to identify this insn in an output. It's valid to use a
1886 static buffer for this. The ALIGNED parameter should cause the string
1887 to be formatted so that multiple output lines will line up nicely. */
1890 rgn_print_insn (rtx insn, int aligned)
1892 static char tmp[80];
1895 sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
1898 if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
1899 sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
1901 sprintf (tmp, "%d", INSN_UID (insn));
1906 /* Compare priority of two insns. Return a positive number if the second
1907 insn is to be preferred for scheduling, and a negative one if the first
1908 is to be preferred. Zero if they are equally good. */
1911 rgn_rank (rtx insn1, rtx insn2)
1913 /* Some comparison make sense in interblock scheduling only. */
1914 if (INSN_BB (insn1) != INSN_BB (insn2))
1916 int spec_val, prob_val;
1918 /* Prefer an inblock motion on an interblock motion. */
1919 if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
1921 if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
1924 /* Prefer a useful motion on a speculative one. */
1925 spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
1929 /* Prefer a more probable (speculative) insn. */
1930 prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
1937 /* NEXT is an instruction that depends on INSN (a backward dependence);
1938 return nonzero if we should include this dependence in priority
1942 contributes_to_priority (rtx next, rtx insn)
1944 return BLOCK_NUM (next) == BLOCK_NUM (insn);
1947 /* INSN is a JUMP_INSN, COND_SET is the set of registers that are
1948 conditionally set before INSN. Store the set of registers that
1949 must be considered as used by this jump in USED and that of
1950 registers that must be considered as set in SET. */
1953 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
1954 regset cond_exec ATTRIBUTE_UNUSED,
1955 regset used ATTRIBUTE_UNUSED,
1956 regset set ATTRIBUTE_UNUSED)
1958 /* Nothing to do here, since we postprocess jumps in
1959 add_branch_dependences. */
1962 /* Used in schedule_insns to initialize current_sched_info for scheduling
1963 regions (or single basic blocks). */
1965 static struct sched_info region_sched_info =
1968 can_schedule_ready_p,
1973 contributes_to_priority,
1974 compute_jump_reg_dependencies,
1981 /* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register. */
1984 sets_likely_spilled (rtx pat)
1987 note_stores (pat, sets_likely_spilled_1, &ret);
1992 sets_likely_spilled_1 (rtx x, rtx pat, void *data)
1994 bool *ret = (bool *) data;
1996 if (GET_CODE (pat) == SET
1998 && REGNO (x) < FIRST_PSEUDO_REGISTER
1999 && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x))))
2003 /* Add dependences so that branches are scheduled to run last in their
2007 add_branch_dependences (rtx head, rtx tail)
2011 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2012 that can throw exceptions, force them to remain in order at the end of
2013 the block by adding dependencies and giving the last a high priority.
2014 There may be notes present, and prev_head may also be a note.
2016 Branches must obviously remain at the end. Calls should remain at the
2017 end since moving them results in worse register allocation. Uses remain
2018 at the end to ensure proper register allocation.
2020 cc0 setters remain at the end because they can't be moved away from
2023 Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values)
2024 are not moved before reload because we can wind up with register
2025 allocation failures. */
2029 while (CALL_P (insn)
2031 || (NONJUMP_INSN_P (insn)
2032 && (GET_CODE (PATTERN (insn)) == USE
2033 || GET_CODE (PATTERN (insn)) == CLOBBER
2034 || can_throw_internal (insn)
2036 || sets_cc0_p (PATTERN (insn))
2038 || (!reload_completed
2039 && sets_likely_spilled (PATTERN (insn)))))
2044 if (last != 0 && !find_insn_list (insn, LOG_LINKS (last)))
2046 add_dependence (last, insn, REG_DEP_ANTI);
2047 INSN_REF_COUNT (insn)++;
2050 CANT_MOVE (insn) = 1;
2055 /* Don't overrun the bounds of the basic block. */
2059 insn = PREV_INSN (insn);
2062 /* Make sure these insns are scheduled last in their block. */
2065 while (insn != head)
2067 insn = prev_nonnote_insn (insn);
2069 if (INSN_REF_COUNT (insn) != 0)
2072 add_dependence (last, insn, REG_DEP_ANTI);
2073 INSN_REF_COUNT (insn) = 1;
2077 /* Data structures for the computation of data dependences in a regions. We
2078 keep one `deps' structure for every basic block. Before analyzing the
2079 data dependences for a bb, its variables are initialized as a function of
2080 the variables of its predecessors. When the analysis for a bb completes,
2081 we save the contents to the corresponding bb_deps[bb] variable. */
2083 static struct deps *bb_deps;
2085 /* Duplicate the INSN_LIST elements of COPY and prepend them to OLD. */
2088 concat_INSN_LIST (rtx copy, rtx old)
2091 for (; copy ; copy = XEXP (copy, 1))
2092 new = alloc_INSN_LIST (XEXP (copy, 0), new);
2097 concat_insn_mem_list (rtx copy_insns, rtx copy_mems, rtx *old_insns_p,
2100 rtx new_insns = *old_insns_p;
2101 rtx new_mems = *old_mems_p;
2105 new_insns = alloc_INSN_LIST (XEXP (copy_insns, 0), new_insns);
2106 new_mems = alloc_EXPR_LIST (VOIDmode, XEXP (copy_mems, 0), new_mems);
2107 copy_insns = XEXP (copy_insns, 1);
2108 copy_mems = XEXP (copy_mems, 1);
2111 *old_insns_p = new_insns;
2112 *old_mems_p = new_mems;
2115 /* After computing the dependencies for block BB, propagate the dependencies
2116 found in TMP_DEPS to the successors of the block. */
2118 propagate_deps (int bb, struct deps *pred_deps)
2120 int b = BB_TO_BLOCK (bb);
2123 /* bb's structures are inherited by its successors. */
2124 first_edge = e = OUT_EDGES (b);
2128 int b_succ = TO_BLOCK (e);
2129 int bb_succ = BLOCK_TO_BB (b_succ);
2130 struct deps *succ_deps = bb_deps + bb_succ;
2133 /* Only bbs "below" bb, in the same region, are interesting. */
2134 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
2141 /* The reg_last lists are inherited by bb_succ. */
2142 EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg,
2144 struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
2145 struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
2147 succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
2148 succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
2149 succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
2151 succ_rl->uses_length += pred_rl->uses_length;
2152 succ_rl->clobbers_length += pred_rl->clobbers_length;
2154 IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
2156 /* Mem read/write lists are inherited by bb_succ. */
2157 concat_insn_mem_list (pred_deps->pending_read_insns,
2158 pred_deps->pending_read_mems,
2159 &succ_deps->pending_read_insns,
2160 &succ_deps->pending_read_mems);
2161 concat_insn_mem_list (pred_deps->pending_write_insns,
2162 pred_deps->pending_write_mems,
2163 &succ_deps->pending_write_insns,
2164 &succ_deps->pending_write_mems);
2166 succ_deps->last_pending_memory_flush
2167 = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
2168 succ_deps->last_pending_memory_flush);
2170 succ_deps->pending_lists_length += pred_deps->pending_lists_length;
2171 succ_deps->pending_flush_length += pred_deps->pending_flush_length;
2173 /* last_function_call is inherited by bb_succ. */
2174 succ_deps->last_function_call
2175 = concat_INSN_LIST (pred_deps->last_function_call,
2176 succ_deps->last_function_call);
2178 /* sched_before_next_call is inherited by bb_succ. */
2179 succ_deps->sched_before_next_call
2180 = concat_INSN_LIST (pred_deps->sched_before_next_call,
2181 succ_deps->sched_before_next_call);
2185 while (e != first_edge);
2187 /* These lists should point to the right place, for correct
2189 bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
2190 bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
2191 bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
2192 bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
2194 /* Can't allow these to be freed twice. */
2195 pred_deps->pending_read_insns = 0;
2196 pred_deps->pending_read_mems = 0;
2197 pred_deps->pending_write_insns = 0;
2198 pred_deps->pending_write_mems = 0;
2201 /* Compute backward dependences inside bb. In a multiple blocks region:
2202 (1) a bb is analyzed after its predecessors, and (2) the lists in
2203 effect at the end of bb (after analyzing for bb) are inherited by
2206 Specifically for reg-reg data dependences, the block insns are
2207 scanned by sched_analyze () top-to-bottom. Two lists are
2208 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2209 and reg_last[].uses for register USEs.
2211 When analysis is completed for bb, we update for its successors:
2212 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2213 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2215 The mechanism for computing mem-mem data dependence is very
2216 similar, and the result is interblock dependences in the region. */
2219 compute_block_backward_dependences (int bb)
2222 struct deps tmp_deps;
2224 tmp_deps = bb_deps[bb];
2226 /* Do the analysis for this block. */
2227 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2228 sched_analyze (&tmp_deps, head, tail);
2229 add_branch_dependences (head, tail);
2231 if (current_nr_blocks > 1)
2232 propagate_deps (bb, &tmp_deps);
2234 /* Free up the INSN_LISTs. */
2235 free_deps (&tmp_deps);
2238 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2239 them to the unused_*_list variables, so that they can be reused. */
2242 free_pending_lists (void)
2246 for (bb = 0; bb < current_nr_blocks; bb++)
2248 free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
2249 free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
2250 free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
2251 free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
2255 /* Print dependences for debugging, callable from debugger. */
2258 debug_dependencies (void)
2262 fprintf (sched_dump, ";; --------------- forward dependences: ------------ \n");
2263 for (bb = 0; bb < current_nr_blocks; bb++)
2269 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2270 next_tail = NEXT_INSN (tail);
2271 fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
2272 BB_TO_BLOCK (bb), bb);
2274 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2275 "insn", "code", "bb", "dep", "prio", "cost",
2277 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2278 "----", "----", "--", "---", "----", "----",
2281 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2285 if (! INSN_P (insn))
2288 fprintf (sched_dump, ";; %6d ", INSN_UID (insn));
2291 n = NOTE_LINE_NUMBER (insn);
2293 fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
2296 expanded_location xloc;
2297 NOTE_EXPANDED_LOCATION (xloc, insn);
2298 fprintf (sched_dump, "line %d, file %s\n",
2299 xloc.line, xloc.file);
2303 fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
2307 fprintf (sched_dump,
2308 ";; %s%5d%6d%6d%6d%6d%6d ",
2309 (SCHED_GROUP_P (insn) ? "+" : " "),
2313 INSN_DEP_COUNT (insn),
2314 INSN_PRIORITY (insn),
2315 insn_cost (insn, 0, 0));
2317 if (recog_memoized (insn) < 0)
2318 fprintf (sched_dump, "nothing");
2320 print_reservation (sched_dump, insn);
2322 fprintf (sched_dump, "\t: ");
2323 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2324 fprintf (sched_dump, "%d ", INSN_UID (XEXP (link, 0)));
2325 fprintf (sched_dump, "\n");
2328 fprintf (sched_dump, "\n");
2331 /* Returns true if all the basic blocks of the current region have
2332 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */
2334 sched_is_disabled_for_current_region_p (void)
2338 for (bb = 0; bb < current_nr_blocks; bb++)
2339 if (!(BASIC_BLOCK (BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE))
2345 /* Schedule a region. A region is either an inner loop, a loop-free
2346 subroutine, or a single basic block. Each bb in the region is
2347 scheduled after its flow predecessors. */
2350 schedule_region (int rgn)
2353 int rgn_n_insns = 0;
2354 int sched_rgn_n_insns = 0;
2356 /* Set variables for the current region. */
2357 current_nr_blocks = RGN_NR_BLOCKS (rgn);
2358 current_blocks = RGN_BLOCKS (rgn);
2360 /* Don't schedule region that is marked by
2361 NOTE_DISABLE_SCHED_OF_BLOCK. */
2362 if (sched_is_disabled_for_current_region_p ())
2365 init_deps_global ();
2367 /* Initializations for region data dependence analysis. */
2368 bb_deps = xmalloc (sizeof (struct deps) * current_nr_blocks);
2369 for (bb = 0; bb < current_nr_blocks; bb++)
2370 init_deps (bb_deps + bb);
2372 /* Compute LOG_LINKS. */
2373 for (bb = 0; bb < current_nr_blocks; bb++)
2374 compute_block_backward_dependences (bb);
2376 /* Compute INSN_DEPEND. */
2377 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
2380 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2382 compute_forward_dependences (head, tail);
2384 if (targetm.sched.dependencies_evaluation_hook)
2385 targetm.sched.dependencies_evaluation_hook (head, tail);
2389 /* Set priorities. */
2390 for (bb = 0; bb < current_nr_blocks; bb++)
2393 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2395 rgn_n_insns += set_priorities (head, tail);
2398 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
2399 if (current_nr_blocks > 1)
2403 prob = xmalloc ((current_nr_blocks) * sizeof (float));
2405 dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
2406 sbitmap_vector_zero (dom, current_nr_blocks);
2409 edge_to_bit = xmalloc (nr_edges * sizeof (int));
2410 for (i = 1; i < nr_edges; i++)
2411 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
2412 EDGE_TO_BIT (i) = rgn_nr_edges++;
2413 rgn_edges = xmalloc (rgn_nr_edges * sizeof (int));
2416 for (i = 1; i < nr_edges; i++)
2417 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
2418 rgn_edges[rgn_nr_edges++] = i;
2421 pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2422 sbitmap_vector_zero (pot_split, current_nr_blocks);
2423 ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2424 sbitmap_vector_zero (ancestor_edges, current_nr_blocks);
2426 /* Compute probabilities, dominators, split_edges. */
2427 for (bb = 0; bb < current_nr_blocks; bb++)
2428 compute_dom_prob_ps (bb);
2431 /* Now we can schedule all blocks. */
2432 for (bb = 0; bb < current_nr_blocks; bb++)
2435 int b = BB_TO_BLOCK (bb);
2437 get_block_head_tail (b, &head, &tail);
2439 if (no_real_insns_p (head, tail))
2442 current_sched_info->prev_head = PREV_INSN (head);
2443 current_sched_info->next_tail = NEXT_INSN (tail);
2445 if (write_symbols != NO_DEBUG)
2447 save_line_notes (b, head, tail);
2448 rm_line_notes (head, tail);
2451 /* rm_other_notes only removes notes which are _inside_ the
2452 block---that is, it won't remove notes before the first real insn
2453 or after the last real insn of the block. So if the first insn
2454 has a REG_SAVE_NOTE which would otherwise be emitted before the
2455 insn, it is redundant with the note before the start of the
2456 block, and so we have to take it out. */
2461 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
2462 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
2464 remove_note (head, note);
2465 note = XEXP (note, 1);
2466 remove_note (head, note);
2470 /* Remove remaining note insns from the block, save them in
2471 note_list. These notes are restored at the end of
2472 schedule_block (). */
2473 rm_other_notes (head, tail);
2477 current_sched_info->queue_must_finish_empty
2478 = current_nr_blocks > 1 && !flag_schedule_interblock;
2480 schedule_block (b, rgn_n_insns);
2481 sched_rgn_n_insns += sched_n_insns;
2483 /* Update target block boundaries. */
2484 if (head == BB_HEAD (BASIC_BLOCK (b)))
2485 BB_HEAD (BASIC_BLOCK (b)) = current_sched_info->head;
2486 if (tail == BB_END (BASIC_BLOCK (b)))
2487 BB_END (BASIC_BLOCK (b)) = current_sched_info->tail;
2490 if (current_nr_blocks > 1)
2492 free (candidate_table);
2494 free (bitlst_table);
2498 /* Sanity check: verify that all region insns were scheduled. */
2499 gcc_assert (sched_rgn_n_insns == rgn_n_insns);
2501 /* Restore line notes. */
2502 if (write_symbols != NO_DEBUG)
2504 for (bb = 0; bb < current_nr_blocks; bb++)
2507 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2508 restore_line_notes (head, tail);
2512 /* Done with this region. */
2513 free_pending_lists ();
2515 finish_deps_global ();
2519 if (current_nr_blocks > 1)
2522 sbitmap_vector_free (dom);
2523 sbitmap_vector_free (pot_split);
2524 sbitmap_vector_free (ancestor_edges);
2530 /* Indexed by region, holds the number of death notes found in that region.
2531 Used for consistency checks. */
2532 static int *deaths_in_region;
2534 /* Initialize data structures for region scheduling. */
2543 rgn_table = xmalloc ((n_basic_blocks) * sizeof (region));
2544 rgn_bb_table = xmalloc ((n_basic_blocks) * sizeof (int));
2545 block_to_bb = xmalloc ((last_basic_block) * sizeof (int));
2546 containing_rgn = xmalloc ((last_basic_block) * sizeof (int));
2548 /* Compute regions for scheduling. */
2549 if (reload_completed
2550 || n_basic_blocks == 1
2551 || !flag_schedule_interblock)
2553 find_single_block_region ();
2557 /* Verify that a 'good' control flow graph can be built. */
2558 if (is_cfg_nonregular ())
2560 find_single_block_region ();
2564 struct edge_list *edge_list;
2566 /* The scheduler runs after estimate_probabilities; therefore, we
2567 can't blindly call back into find_basic_blocks since doing so
2568 could invalidate the branch probability info. We could,
2569 however, call cleanup_cfg. */
2570 edge_list = create_edge_list ();
2572 /* Compute the dominators and post dominators. */
2573 calculate_dominance_info (CDI_DOMINATORS);
2575 /* build_control_flow will return nonzero if it detects unreachable
2576 blocks or any other irregularity with the cfg which prevents
2577 cross block scheduling. */
2578 if (build_control_flow (edge_list) != 0)
2579 find_single_block_region ();
2581 find_rgns (edge_list);
2583 if (sched_verbose >= 3)
2586 /* We are done with flow's edge list. */
2587 free_edge_list (edge_list);
2589 /* For now. This will move as more and more of haifa is converted
2590 to using the cfg code in flow.c. */
2591 free_dominance_info (CDI_DOMINATORS);
2596 if (CHECK_DEAD_NOTES)
2598 blocks = sbitmap_alloc (last_basic_block);
2599 deaths_in_region = xmalloc (sizeof (int) * nr_regions);
2600 /* Remove all death notes from the subroutine. */
2601 for (rgn = 0; rgn < nr_regions; rgn++)
2605 sbitmap_zero (blocks);
2606 for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
2607 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]);
2609 deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1);
2611 sbitmap_free (blocks);
2614 count_or_remove_death_notes (NULL, 1);
2617 /* The one entry point in this file. DUMP_FILE is the dump file for
2621 schedule_insns (FILE *dump_file)
2623 sbitmap large_region_blocks, blocks;
2625 int any_large_regions;
2628 /* Taking care of this degenerate case makes the rest of
2629 this code simpler. */
2630 if (n_basic_blocks == 0)
2636 sched_init (dump_file);
2640 current_sched_info = ®ion_sched_info;
2642 /* Schedule every region in the subroutine. */
2643 for (rgn = 0; rgn < nr_regions; rgn++)
2644 schedule_region (rgn);
2646 /* Update life analysis for the subroutine. Do single block regions
2647 first so that we can verify that live_at_start didn't change. Then
2648 do all other blocks. */
2649 /* ??? There is an outside possibility that update_life_info, or more
2650 to the point propagate_block, could get called with nonzero flags
2651 more than once for one basic block. This would be kinda bad if it
2652 were to happen, since REG_INFO would be accumulated twice for the
2653 block, and we'd have twice the REG_DEAD notes.
2655 I'm fairly certain that this _shouldn't_ happen, since I don't think
2656 that live_at_start should change at region heads. Not sure what the
2657 best way to test for this kind of thing... */
2659 allocate_reg_life_data ();
2660 compute_bb_for_insn ();
2662 any_large_regions = 0;
2663 large_region_blocks = sbitmap_alloc (last_basic_block);
2664 sbitmap_zero (large_region_blocks);
2666 SET_BIT (large_region_blocks, bb->index);
2668 blocks = sbitmap_alloc (last_basic_block);
2669 sbitmap_zero (blocks);
2671 /* Update life information. For regions consisting of multiple blocks
2672 we've possibly done interblock scheduling that affects global liveness.
2673 For regions consisting of single blocks we need to do only local
2675 for (rgn = 0; rgn < nr_regions; rgn++)
2676 if (RGN_NR_BLOCKS (rgn) > 1)
2677 any_large_regions = 1;
2680 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2681 RESET_BIT (large_region_blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2684 /* Don't update reg info after reload, since that affects
2685 regs_ever_live, which should not change after reload. */
2686 update_life_info (blocks, UPDATE_LIFE_LOCAL,
2687 (reload_completed ? PROP_DEATH_NOTES
2688 : PROP_DEATH_NOTES | PROP_REG_INFO));
2689 if (any_large_regions)
2691 update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL,
2692 PROP_DEATH_NOTES | PROP_REG_INFO);
2695 if (CHECK_DEAD_NOTES)
2697 /* Verify the counts of basic block notes in single the basic block
2699 for (rgn = 0; rgn < nr_regions; rgn++)
2700 if (RGN_NR_BLOCKS (rgn) == 1)
2702 sbitmap_zero (blocks);
2703 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2705 gcc_assert (deaths_in_region[rgn]
2706 == count_or_remove_death_notes (blocks, 0));
2708 free (deaths_in_region);
2711 /* Reposition the prologue and epilogue notes in case we moved the
2712 prologue/epilogue insns. */
2713 if (reload_completed)
2714 reposition_prologue_and_epilogue_notes (get_insns ());
2716 /* Delete redundant line notes. */
2717 if (write_symbols != NO_DEBUG)
2718 rm_redundant_line_notes ();
2722 if (reload_completed == 0 && flag_schedule_interblock)
2724 fprintf (sched_dump,
2725 "\n;; Procedure interblock/speculative motions == %d/%d \n",
2729 gcc_assert (nr_inter <= 0);
2730 fprintf (sched_dump, "\n\n");
2735 free (rgn_bb_table);
2737 free (containing_rgn);
2758 sbitmap_free (blocks);
2759 sbitmap_free (large_region_blocks);