1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002 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. */
53 #include "hard-reg-set.h"
54 #include "basic-block.h"
58 #include "insn-config.h"
59 #include "insn-attr.h"
63 #include "cfglayout.h"
64 #include "sched-int.h"
67 /* Define when we want to do count REG_DEAD notes before and after scheduling
68 for sanity checking. We can't do that when conditional execution is used,
69 as REG_DEAD exist only for unconditional deaths. */
71 #if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING)
72 #define CHECK_DEAD_NOTES 1
74 #define CHECK_DEAD_NOTES 0
78 #ifdef INSN_SCHEDULING
79 /* Some accessor macros for h_i_d members only used within this file. */
80 #define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count)
81 #define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load)
82 #define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn)
84 #define MAX_RGN_BLOCKS 10
85 #define MAX_RGN_INSNS 100
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 PARAMS ((void));
118 static int build_control_flow PARAMS ((struct edge_list *));
119 static void new_edge PARAMS ((int, int));
121 /* A region is the main entity for interblock scheduling: insns
122 are allowed to move between blocks in the same region, along
123 control flow graph edges, in the 'up' direction. */
126 int rgn_nr_blocks; /* Number of blocks in region. */
127 int rgn_blocks; /* cblocks in the region (actually index in rgn_bb_table). */
131 /* Number of regions in the procedure. */
132 static int nr_regions;
134 /* Table of region descriptions. */
135 static region *rgn_table;
137 /* Array of lists of regions' blocks. */
138 static int *rgn_bb_table;
140 /* Topological order of blocks in the region (if b2 is reachable from
141 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
142 always referred to by either block or b, while its topological
143 order name (in the region) is refered to by bb. */
144 static int *block_to_bb;
146 /* The number of the region containing a block. */
147 static int *containing_rgn;
149 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
150 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
151 #define BLOCK_TO_BB(block) (block_to_bb[block])
152 #define CONTAINING_RGN(block) (containing_rgn[block])
154 void debug_regions PARAMS ((void));
155 static void find_single_block_region PARAMS ((void));
156 static void find_rgns PARAMS ((struct edge_list *, sbitmap *));
157 static int too_large PARAMS ((int, int *, int *));
159 extern void debug_live PARAMS ((int, int));
161 /* Blocks of the current region being scheduled. */
162 static int current_nr_blocks;
163 static int current_blocks;
165 /* The mapping from bb to block. */
166 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
170 int *first_member; /* Pointer to the list start in bitlst_table. */
171 int nr_members; /* The number of members of the bit list. */
175 static int bitlst_table_last;
176 static int bitlst_table_size;
177 static int *bitlst_table;
179 static void extract_bitlst PARAMS ((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 PARAMS ((int, int, edgelst *));
221 static void compute_trg_info PARAMS ((int));
222 void debug_candidate PARAMS ((int));
223 void debug_candidates PARAMS ((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 PARAMS ((int));
273 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
274 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
275 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
276 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
278 /* Parameters affecting the decision of rank_for_schedule().
279 ??? Nope. But MIN_PROBABILITY is used in copmute_trg_info. */
280 #define MIN_DIFF_PRIORITY 2
281 #define MIN_PROBABILITY 40
282 #define MIN_PROB_DIFF 10
284 /* Speculative scheduling functions. */
285 static int check_live_1 PARAMS ((int, rtx));
286 static void update_live_1 PARAMS ((int, rtx));
287 static int check_live PARAMS ((rtx, int));
288 static void update_live PARAMS ((rtx, int));
289 static void set_spec_fed PARAMS ((rtx));
290 static int is_pfree PARAMS ((rtx, int, int));
291 static int find_conditional_protection PARAMS ((rtx, int));
292 static int is_conditionally_protected PARAMS ((rtx, int, int));
293 static int may_trap_exp PARAMS ((rtx, int));
294 static int haifa_classify_insn PARAMS ((rtx));
295 static int is_prisky PARAMS ((rtx, int, int));
296 static int is_exception_free PARAMS ((rtx, int, int));
298 static bool sets_likely_spilled PARAMS ((rtx));
299 static void sets_likely_spilled_1 PARAMS ((rtx, rtx, void *));
300 static void add_branch_dependences PARAMS ((rtx, rtx));
301 static void compute_block_backward_dependences PARAMS ((int));
302 void debug_dependencies PARAMS ((void));
304 static void init_regions PARAMS ((void));
305 static void schedule_region PARAMS ((int));
306 static rtx concat_INSN_LIST PARAMS ((rtx, rtx));
307 static void concat_insn_mem_list PARAMS ((rtx, rtx, rtx *, rtx *));
308 static void propagate_deps PARAMS ((int, struct deps *));
309 static void free_pending_lists PARAMS ((void));
311 /* Functions for construction of the control flow graph. */
313 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
315 We decide not to build the control flow graph if there is possibly more
316 than one entry to the function, if computed branches exist, of if we
317 have nonlocal gotos. */
326 /* If we have a label that could be the target of a nonlocal goto, then
327 the cfg is not well structured. */
328 if (nonlocal_goto_handler_labels)
331 /* If we have any forced labels, then the cfg is not well structured. */
335 /* If this function has a computed jump, then we consider the cfg
336 not well structured. */
337 if (current_function_has_computed_jump)
340 /* If we have exception handlers, then we consider the cfg not well
341 structured. ?!? We should be able to handle this now that flow.c
342 computes an accurate cfg for EH. */
343 if (current_function_has_exception_handlers ())
346 /* If we have non-jumping insns which refer to labels, then we consider
347 the cfg not well structured. */
348 /* Check for labels referred to other thn by jumps. */
349 for (b = 0; b < n_basic_blocks; b++)
350 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
352 code = GET_CODE (insn);
353 if (GET_RTX_CLASS (code) == 'i' && code != JUMP_INSN)
355 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
358 && ! (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
359 && find_reg_note (NEXT_INSN (insn), REG_LABEL,
364 if (insn == BLOCK_END (b))
368 /* All the tests passed. Consider the cfg well structured. */
372 /* Build the control flow graph and set nr_edges.
374 Instead of trying to build a cfg ourselves, we rely on flow to
375 do it for us. Stamp out useless code (and bug) duplication.
377 Return nonzero if an irregularity in the cfg is found which would
378 prevent cross block scheduling. */
381 build_control_flow (edge_list)
382 struct edge_list *edge_list;
384 int i, unreachable, num_edges;
386 /* This already accounts for entry/exit edges. */
387 num_edges = NUM_EDGES (edge_list);
389 /* Unreachable loops with more than one basic block are detected
390 during the DFS traversal in find_rgns.
392 Unreachable loops with a single block are detected here. This
393 test is redundant with the one in find_rgns, but it's much
394 cheaper to go ahead and catch the trivial case here. */
396 for (i = 0; i < n_basic_blocks; i++)
398 basic_block b = BASIC_BLOCK (i);
401 || (b->pred->src == b
402 && b->pred->pred_next == NULL))
406 /* ??? We can kill these soon. */
407 in_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
408 out_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
409 edge_table = (haifa_edge *) xcalloc (num_edges, sizeof (haifa_edge));
412 for (i = 0; i < num_edges; i++)
414 edge e = INDEX_EDGE (edge_list, i);
416 if (e->dest != EXIT_BLOCK_PTR
417 && e->src != ENTRY_BLOCK_PTR)
418 new_edge (e->src->index, e->dest->index);
421 /* Increment by 1, since edge 0 is unused. */
427 /* Record an edge in the control flow graph from SOURCE to TARGET.
429 In theory, this is redundant with the s_succs computed above, but
430 we have not converted all of haifa to use information from the
434 new_edge (source, target)
438 int curr_edge, fst_edge;
440 /* Check for duplicates. */
441 fst_edge = curr_edge = OUT_EDGES (source);
444 if (FROM_BLOCK (curr_edge) == source
445 && TO_BLOCK (curr_edge) == target)
450 curr_edge = NEXT_OUT (curr_edge);
452 if (fst_edge == curr_edge)
458 FROM_BLOCK (e) = source;
459 TO_BLOCK (e) = target;
461 if (OUT_EDGES (source))
463 next_edge = NEXT_OUT (OUT_EDGES (source));
464 NEXT_OUT (OUT_EDGES (source)) = e;
465 NEXT_OUT (e) = next_edge;
469 OUT_EDGES (source) = e;
473 if (IN_EDGES (target))
475 next_edge = NEXT_IN (IN_EDGES (target));
476 NEXT_IN (IN_EDGES (target)) = e;
477 NEXT_IN (e) = next_edge;
481 IN_EDGES (target) = e;
486 /* Translate a bit-set SET to a list BL of the bit-set members. */
489 extract_bitlst (set, bl)
495 /* bblst table space is reused in each call to extract_bitlst. */
496 bitlst_table_last = 0;
498 bl->first_member = &bitlst_table[bitlst_table_last];
501 /* Iterate over each word in the bitset. */
502 EXECUTE_IF_SET_IN_SBITMAP (set, 0, i,
504 bitlst_table[bitlst_table_last++] = i;
510 /* Functions for the construction of regions. */
512 /* Print the regions, for debugging purposes. Callable from debugger. */
519 fprintf (sched_dump, "\n;; ------------ REGIONS ----------\n\n");
520 for (rgn = 0; rgn < nr_regions; rgn++)
522 fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
523 rgn_table[rgn].rgn_nr_blocks);
524 fprintf (sched_dump, ";;\tbb/block: ");
526 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
528 current_blocks = RGN_BLOCKS (rgn);
530 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
533 fprintf (sched_dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
536 fprintf (sched_dump, "\n\n");
540 /* Build a single block region for each basic block in the function.
541 This allows for using the same code for interblock and basic block
545 find_single_block_region ()
549 for (i = 0; i < n_basic_blocks; i++)
552 RGN_NR_BLOCKS (i) = 1;
554 CONTAINING_RGN (i) = i;
557 nr_regions = n_basic_blocks;
560 /* Update number of blocks and the estimate for number of insns
561 in the region. Return 1 if the region is "too large" for interblock
562 scheduling (compile time considerations), otherwise return 0. */
565 too_large (block, num_bbs, num_insns)
566 int block, *num_bbs, *num_insns;
569 (*num_insns) += (INSN_LUID (BLOCK_END (block)) -
570 INSN_LUID (BLOCK_HEAD (block)));
571 if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
577 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
578 is still an inner loop. Put in max_hdr[blk] the header of the most inner
579 loop containing blk. */
580 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
582 if (max_hdr[blk] == -1) \
583 max_hdr[blk] = hdr; \
584 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
585 RESET_BIT (inner, hdr); \
586 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
588 RESET_BIT (inner,max_hdr[blk]); \
589 max_hdr[blk] = hdr; \
593 /* Find regions for interblock scheduling.
595 A region for scheduling can be:
597 * A loop-free procedure, or
599 * A reducible inner loop, or
601 * A basic block not contained in any other region.
603 ?!? In theory we could build other regions based on extended basic
604 blocks or reverse extended basic blocks. Is it worth the trouble?
606 Loop blocks that form a region are put into the region's block list
607 in topological order.
609 This procedure stores its results into the following global (ick) variables
617 We use dominator relationships to avoid making regions out of non-reducible
620 This procedure needs to be converted to work on pred/succ lists instead
621 of edge tables. That would simplify it somewhat. */
624 find_rgns (edge_list, dom)
625 struct edge_list *edge_list;
628 int *max_hdr, *dfs_nr, *stack, *degree;
630 int node, child, loop_head, i, head, tail;
631 int count = 0, sp, idx = 0, current_edge = out_edges[0];
632 int num_bbs, num_insns, unreachable;
633 int too_large_failure;
635 /* Note if an edge has been passed. */
638 /* Note if a block is a natural loop header. */
641 /* Note if a block is an natural inner loop header. */
644 /* Note if a block is in the block queue. */
647 /* Note if a block is in the block queue. */
650 int num_edges = NUM_EDGES (edge_list);
652 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
653 and a mapping from block to its loop header (if the block is contained
656 Store results in HEADER, INNER, and MAX_HDR respectively, these will
657 be used as inputs to the second traversal.
659 STACK, SP and DFS_NR are only used during the first traversal. */
661 /* Allocate and initialize variables for the first traversal. */
662 max_hdr = (int *) xmalloc (n_basic_blocks * sizeof (int));
663 dfs_nr = (int *) xcalloc (n_basic_blocks, sizeof (int));
664 stack = (int *) xmalloc (nr_edges * sizeof (int));
666 inner = sbitmap_alloc (n_basic_blocks);
667 sbitmap_ones (inner);
669 header = sbitmap_alloc (n_basic_blocks);
670 sbitmap_zero (header);
672 passed = sbitmap_alloc (nr_edges);
673 sbitmap_zero (passed);
675 in_queue = sbitmap_alloc (n_basic_blocks);
676 sbitmap_zero (in_queue);
678 in_stack = sbitmap_alloc (n_basic_blocks);
679 sbitmap_zero (in_stack);
681 for (i = 0; i < n_basic_blocks; i++)
684 /* DFS traversal to find inner loops in the cfg. */
689 if (current_edge == 0 || TEST_BIT (passed, current_edge))
691 /* We have reached a leaf node or a node that was already
692 processed. Pop edges off the stack until we find
693 an edge that has not yet been processed. */
695 && (current_edge == 0 || TEST_BIT (passed, current_edge)))
697 /* Pop entry off the stack. */
698 current_edge = stack[sp--];
699 node = FROM_BLOCK (current_edge);
700 child = TO_BLOCK (current_edge);
701 RESET_BIT (in_stack, child);
702 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
703 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
704 current_edge = NEXT_OUT (current_edge);
707 /* See if have finished the DFS tree traversal. */
708 if (sp < 0 && TEST_BIT (passed, current_edge))
711 /* Nope, continue the traversal with the popped node. */
715 /* Process a node. */
716 node = FROM_BLOCK (current_edge);
717 child = TO_BLOCK (current_edge);
718 SET_BIT (in_stack, node);
719 dfs_nr[node] = ++count;
721 /* If the successor is in the stack, then we've found a loop.
722 Mark the loop, if it is not a natural loop, then it will
723 be rejected during the second traversal. */
724 if (TEST_BIT (in_stack, child))
727 SET_BIT (header, child);
728 UPDATE_LOOP_RELATIONS (node, child);
729 SET_BIT (passed, current_edge);
730 current_edge = NEXT_OUT (current_edge);
734 /* If the child was already visited, then there is no need to visit
735 it again. Just update the loop relationships and restart
739 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
740 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
741 SET_BIT (passed, current_edge);
742 current_edge = NEXT_OUT (current_edge);
746 /* Push an entry on the stack and continue DFS traversal. */
747 stack[++sp] = current_edge;
748 SET_BIT (passed, current_edge);
749 current_edge = OUT_EDGES (child);
751 /* This is temporary until haifa is converted to use rth's new
752 cfg routines which have true entry/exit blocks and the
753 appropriate edges from/to those blocks.
755 Generally we update dfs_nr for a node when we process its
756 out edge. However, if the node has no out edge then we will
757 not set dfs_nr for that node. This can confuse the scheduler
758 into thinking that we have unreachable blocks, which in turn
759 disables cross block scheduling.
761 So, if we have a node with no out edges, go ahead and mark it
763 if (current_edge == 0)
764 dfs_nr[child] = ++count;
767 /* Another check for unreachable blocks. The earlier test in
768 is_cfg_nonregular only finds unreachable blocks that do not
771 The DFS traversal will mark every block that is reachable from
772 the entry node by placing a nonzero value in dfs_nr. Thus if
773 dfs_nr is zero for any block, then it must be unreachable. */
775 for (i = 0; i < n_basic_blocks; i++)
782 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
783 to hold degree counts. */
786 for (i = 0; i < n_basic_blocks; i++)
788 for (i = 0; i < num_edges; i++)
790 edge e = INDEX_EDGE (edge_list, i);
792 if (e->dest != EXIT_BLOCK_PTR)
793 degree[e->dest->index]++;
796 /* Do not perform region scheduling if there are any unreachable
805 /* Second travsersal:find reducible inner loops and topologically sort
806 block of each region. */
808 queue = (int *) xmalloc (n_basic_blocks * sizeof (int));
810 /* Find blocks which are inner loop headers. We still have non-reducible
811 loops to consider at this point. */
812 for (i = 0; i < n_basic_blocks; i++)
814 if (TEST_BIT (header, i) && TEST_BIT (inner, i))
819 /* Now check that the loop is reducible. We do this separate
820 from finding inner loops so that we do not find a reducible
821 loop which contains an inner non-reducible loop.
823 A simple way to find reducible/natural loops is to verify
824 that each block in the loop is dominated by the loop
827 If there exists a block that is not dominated by the loop
828 header, then the block is reachable from outside the loop
829 and thus the loop is not a natural loop. */
830 for (j = 0; j < n_basic_blocks; j++)
832 /* First identify blocks in the loop, except for the loop
834 if (i == max_hdr[j] && i != j)
836 /* Now verify that the block is dominated by the loop
838 if (!TEST_BIT (dom[j], i))
843 /* If we exited the loop early, then I is the header of
844 a non-reducible loop and we should quit processing it
846 if (j != n_basic_blocks)
849 /* I is a header of an inner loop, or block 0 in a subroutine
850 with no loops at all. */
852 too_large_failure = 0;
853 loop_head = max_hdr[i];
855 /* Decrease degree of all I's successors for topological
857 for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
858 if (e->dest != EXIT_BLOCK_PTR)
859 --degree[e->dest->index];
861 /* Estimate # insns, and count # blocks in the region. */
863 num_insns = (INSN_LUID (BLOCK_END (i))
864 - INSN_LUID (BLOCK_HEAD (i)));
866 /* Find all loop latches (blocks with back edges to the loop
867 header) or all the leaf blocks in the cfg has no loops.
869 Place those blocks into the queue. */
872 for (j = 0; j < n_basic_blocks; j++)
873 /* Leaf nodes have only a single successor which must
875 if (BASIC_BLOCK (j)->succ
876 && BASIC_BLOCK (j)->succ->dest == EXIT_BLOCK_PTR
877 && BASIC_BLOCK (j)->succ->succ_next == NULL)
880 SET_BIT (in_queue, j);
882 if (too_large (j, &num_bbs, &num_insns))
884 too_large_failure = 1;
893 for (e = BASIC_BLOCK (i)->pred; e; e = e->pred_next)
895 if (e->src == ENTRY_BLOCK_PTR)
898 node = e->src->index;
900 if (max_hdr[node] == loop_head && node != i)
902 /* This is a loop latch. */
903 queue[++tail] = node;
904 SET_BIT (in_queue, node);
906 if (too_large (node, &num_bbs, &num_insns))
908 too_large_failure = 1;
915 /* Now add all the blocks in the loop to the queue.
917 We know the loop is a natural loop; however the algorithm
918 above will not always mark certain blocks as being in the
926 The algorithm in the DFS traversal may not mark B & D as part
927 of the loop (ie they will not have max_hdr set to A).
929 We know they can not be loop latches (else they would have
930 had max_hdr set since they'd have a backedge to a dominator
931 block). So we don't need them on the initial queue.
933 We know they are part of the loop because they are dominated
934 by the loop header and can be reached by a backwards walk of
935 the edges starting with nodes on the initial queue.
937 It is safe and desirable to include those nodes in the
938 loop/scheduling region. To do so we would need to decrease
939 the degree of a node if it is the target of a backedge
940 within the loop itself as the node is placed in the queue.
942 We do not do this because I'm not sure that the actual
943 scheduling code will properly handle this case. ?!? */
945 while (head < tail && !too_large_failure)
948 child = queue[++head];
950 for (e = BASIC_BLOCK (child)->pred; e; e = e->pred_next)
952 node = e->src->index;
954 /* See discussion above about nodes not marked as in
955 this loop during the initial DFS traversal. */
956 if (e->src == ENTRY_BLOCK_PTR
957 || max_hdr[node] != loop_head)
962 else if (!TEST_BIT (in_queue, node) && node != i)
964 queue[++tail] = node;
965 SET_BIT (in_queue, node);
967 if (too_large (node, &num_bbs, &num_insns))
969 too_large_failure = 1;
976 if (tail >= 0 && !too_large_failure)
978 /* Place the loop header into list of region blocks. */
980 rgn_bb_table[idx] = i;
981 RGN_NR_BLOCKS (nr_regions) = num_bbs;
982 RGN_BLOCKS (nr_regions) = idx++;
983 CONTAINING_RGN (i) = nr_regions;
984 BLOCK_TO_BB (i) = count = 0;
986 /* Remove blocks from queue[] when their in degree
987 becomes zero. Repeat until no blocks are left on the
988 list. This produces a topological list of blocks in
995 if (degree[child] == 0)
1000 rgn_bb_table[idx++] = child;
1001 BLOCK_TO_BB (child) = ++count;
1002 CONTAINING_RGN (child) = nr_regions;
1003 queue[head] = queue[tail--];
1005 for (e = BASIC_BLOCK (child)->succ;
1008 if (e->dest != EXIT_BLOCK_PTR)
1009 --degree[e->dest->index];
1021 /* Any block that did not end up in a region is placed into a region
1023 for (i = 0; i < n_basic_blocks; i++)
1026 rgn_bb_table[idx] = i;
1027 RGN_NR_BLOCKS (nr_regions) = 1;
1028 RGN_BLOCKS (nr_regions) = idx++;
1029 CONTAINING_RGN (i) = nr_regions++;
1030 BLOCK_TO_BB (i) = 0;
1036 sbitmap_free (passed);
1037 sbitmap_free (header);
1038 sbitmap_free (inner);
1039 sbitmap_free (in_queue);
1040 sbitmap_free (in_stack);
1043 /* Functions for regions scheduling information. */
1045 /* Compute dominators, probability, and potential-split-edges of bb.
1046 Assume that these values were already computed for bb's predecessors. */
1049 compute_dom_prob_ps (bb)
1052 int nxt_in_edge, fst_in_edge, pred;
1053 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1056 if (IS_RGN_ENTRY (bb))
1058 SET_BIT (dom[bb], 0);
1063 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1065 /* Initialize dom[bb] to '111..1'. */
1066 sbitmap_ones (dom[bb]);
1070 pred = FROM_BLOCK (nxt_in_edge);
1071 sbitmap_a_and_b (dom[bb], dom[bb], dom[BLOCK_TO_BB (pred)]);
1072 sbitmap_a_or_b (ancestor_edges[bb], ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)]);
1074 SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge));
1077 nr_rgn_out_edges = 0;
1078 fst_out_edge = OUT_EDGES (pred);
1079 nxt_out_edge = NEXT_OUT (fst_out_edge);
1081 sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[BLOCK_TO_BB (pred)]);
1083 SET_BIT (pot_split[bb], EDGE_TO_BIT (fst_out_edge));
1085 /* The successor doesn't belong in the region? */
1086 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1087 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1090 while (fst_out_edge != nxt_out_edge)
1093 /* The successor doesn't belong in the region? */
1094 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1095 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1097 SET_BIT (pot_split[bb], EDGE_TO_BIT (nxt_out_edge));
1098 nxt_out_edge = NEXT_OUT (nxt_out_edge);
1102 /* Now nr_rgn_out_edges is the number of region-exit edges from
1103 pred, and nr_out_edges will be the number of pred out edges
1104 not leaving the region. */
1105 nr_out_edges -= nr_rgn_out_edges;
1106 if (nr_rgn_out_edges > 0)
1107 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1109 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1110 nxt_in_edge = NEXT_IN (nxt_in_edge);
1112 while (fst_in_edge != nxt_in_edge);
1114 SET_BIT (dom[bb], bb);
1115 sbitmap_difference (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
1117 if (sched_verbose >= 2)
1118 fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
1119 (int) (100.0 * prob[bb]));
1122 /* Functions for target info. */
1124 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1125 Note that bb_trg dominates bb_src. */
1128 split_edges (bb_src, bb_trg, bl)
1133 sbitmap src = (edgeset) sbitmap_alloc (pot_split[bb_src]->n_bits);
1134 sbitmap_copy (src, pot_split[bb_src]);
1136 sbitmap_difference (src, src, pot_split[bb_trg]);
1137 extract_bitlst (src, bl);
1141 /* Find the valid candidate-source-blocks for the target block TRG, compute
1142 their probability, and check if they are speculative or not.
1143 For speculative sources, compute their update-blocks and split-blocks. */
1146 compute_trg_info (trg)
1151 int check_block, update_idx;
1152 int i, j, k, fst_edge, nxt_edge;
1154 /* Define some of the fields for the target bb as well. */
1155 sp = candidate_table + trg;
1157 sp->is_speculative = 0;
1160 for (i = trg + 1; i < current_nr_blocks; i++)
1162 sp = candidate_table + i;
1164 sp->is_valid = IS_DOMINATED (i, trg);
1167 sp->src_prob = GET_SRC_PROB (i, trg);
1168 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
1173 split_edges (i, trg, &el);
1174 sp->is_speculative = (el.nr_members) ? 1 : 0;
1175 if (sp->is_speculative && !flag_schedule_speculative)
1181 char *update_blocks;
1183 /* Compute split blocks and store them in bblst_table.
1184 The TO block of every split edge is a split block. */
1185 sp->split_bbs.first_member = &bblst_table[bblst_last];
1186 sp->split_bbs.nr_members = el.nr_members;
1187 for (j = 0; j < el.nr_members; bblst_last++, j++)
1188 bblst_table[bblst_last] =
1189 TO_BLOCK (rgn_edges[el.first_member[j]]);
1190 sp->update_bbs.first_member = &bblst_table[bblst_last];
1192 /* Compute update blocks and store them in bblst_table.
1193 For every split edge, look at the FROM block, and check
1194 all out edges. For each out edge that is not a split edge,
1195 add the TO block to the update block list. This list can end
1196 up with a lot of duplicates. We need to weed them out to avoid
1197 overrunning the end of the bblst_table. */
1198 update_blocks = (char *) alloca (n_basic_blocks);
1199 memset (update_blocks, 0, n_basic_blocks);
1202 for (j = 0; j < el.nr_members; j++)
1204 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
1205 fst_edge = nxt_edge = OUT_EDGES (check_block);
1208 if (! update_blocks[TO_BLOCK (nxt_edge)])
1210 for (k = 0; k < el.nr_members; k++)
1211 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
1214 if (k >= el.nr_members)
1216 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
1217 update_blocks[TO_BLOCK (nxt_edge)] = 1;
1222 nxt_edge = NEXT_OUT (nxt_edge);
1224 while (fst_edge != nxt_edge);
1226 sp->update_bbs.nr_members = update_idx;
1228 /* Make sure we didn't overrun the end of bblst_table. */
1229 if (bblst_last > bblst_size)
1234 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1236 sp->is_speculative = 0;
1242 /* Print candidates info, for debugging purposes. Callable from debugger. */
1248 if (!candidate_table[i].is_valid)
1251 if (candidate_table[i].is_speculative)
1254 fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1256 fprintf (sched_dump, "split path: ");
1257 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1259 int b = candidate_table[i].split_bbs.first_member[j];
1261 fprintf (sched_dump, " %d ", b);
1263 fprintf (sched_dump, "\n");
1265 fprintf (sched_dump, "update path: ");
1266 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
1268 int b = candidate_table[i].update_bbs.first_member[j];
1270 fprintf (sched_dump, " %d ", b);
1272 fprintf (sched_dump, "\n");
1276 fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
1280 /* Print candidates info, for debugging purposes. Callable from debugger. */
1283 debug_candidates (trg)
1288 fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
1289 BB_TO_BLOCK (trg), trg);
1290 for (i = trg + 1; i < current_nr_blocks; i++)
1291 debug_candidate (i);
1294 /* Functions for speculative scheduing. */
1296 /* Return 0 if x is a set of a register alive in the beginning of one
1297 of the split-blocks of src, otherwise return 1. */
1300 check_live_1 (src, x)
1306 rtx reg = SET_DEST (x);
1311 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
1312 || GET_CODE (reg) == SIGN_EXTRACT
1313 || GET_CODE (reg) == STRICT_LOW_PART)
1314 reg = XEXP (reg, 0);
1316 if (GET_CODE (reg) == PARALLEL)
1320 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1321 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1322 if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
1328 if (GET_CODE (reg) != REG)
1331 regno = REGNO (reg);
1333 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1335 /* Global registers are assumed live. */
1340 if (regno < FIRST_PSEUDO_REGISTER)
1342 /* Check for hard registers. */
1343 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1346 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1348 int b = candidate_table[src].split_bbs.first_member[i];
1350 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
1360 /* Check for psuedo registers. */
1361 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1363 int b = candidate_table[src].split_bbs.first_member[i];
1365 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
1376 /* If x is a set of a register R, mark that R is alive in the beginning
1377 of every update-block of src. */
1380 update_live_1 (src, x)
1386 rtx reg = SET_DEST (x);
1391 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
1392 || GET_CODE (reg) == SIGN_EXTRACT
1393 || GET_CODE (reg) == STRICT_LOW_PART)
1394 reg = XEXP (reg, 0);
1396 if (GET_CODE (reg) == PARALLEL)
1400 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1401 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1402 update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
1407 if (GET_CODE (reg) != REG)
1410 /* Global registers are always live, so the code below does not apply
1413 regno = REGNO (reg);
1415 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
1417 if (regno < FIRST_PSEUDO_REGISTER)
1419 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1422 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1424 int b = candidate_table[src].update_bbs.first_member[i];
1426 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
1433 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1435 int b = candidate_table[src].update_bbs.first_member[i];
1437 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
1443 /* Return 1 if insn can be speculatively moved from block src to trg,
1444 otherwise return 0. Called before first insertion of insn to
1445 ready-list or before the scheduling. */
1448 check_live (insn, src)
1452 /* Find the registers set by instruction. */
1453 if (GET_CODE (PATTERN (insn)) == SET
1454 || GET_CODE (PATTERN (insn)) == CLOBBER)
1455 return check_live_1 (src, PATTERN (insn));
1456 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1459 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1460 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1461 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1462 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
1471 /* Update the live registers info after insn was moved speculatively from
1472 block src to trg. */
1475 update_live (insn, src)
1479 /* Find the registers set by instruction. */
1480 if (GET_CODE (PATTERN (insn)) == SET
1481 || GET_CODE (PATTERN (insn)) == CLOBBER)
1482 update_live_1 (src, PATTERN (insn));
1483 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1486 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1487 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1488 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1489 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
1493 /* Exception Free Loads:
1495 We define five classes of speculative loads: IFREE, IRISKY,
1496 PFREE, PRISKY, and MFREE.
1498 IFREE loads are loads that are proved to be exception-free, just
1499 by examining the load insn. Examples for such loads are loads
1500 from TOC and loads of global data.
1502 IRISKY loads are loads that are proved to be exception-risky,
1503 just by examining the load insn. Examples for such loads are
1504 volatile loads and loads from shared memory.
1506 PFREE loads are loads for which we can prove, by examining other
1507 insns, that they are exception-free. Currently, this class consists
1508 of loads for which we are able to find a "similar load", either in
1509 the target block, or, if only one split-block exists, in that split
1510 block. Load2 is similar to load1 if both have same single base
1511 register. We identify only part of the similar loads, by finding
1512 an insn upon which both load1 and load2 have a DEF-USE dependence.
1514 PRISKY loads are loads for which we can prove, by examining other
1515 insns, that they are exception-risky. Currently we have two proofs for
1516 such loads. The first proof detects loads that are probably guarded by a
1517 test on the memory address. This proof is based on the
1518 backward and forward data dependence information for the region.
1519 Let load-insn be the examined load.
1520 Load-insn is PRISKY iff ALL the following hold:
1522 - insn1 is not in the same block as load-insn
1523 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
1524 - test-insn is either a compare or a branch, not in the same block
1526 - load-insn is reachable from test-insn
1527 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
1529 This proof might fail when the compare and the load are fed
1530 by an insn not in the region. To solve this, we will add to this
1531 group all loads that have no input DEF-USE dependence.
1533 The second proof detects loads that are directly or indirectly
1534 fed by a speculative load. This proof is affected by the
1535 scheduling process. We will use the flag fed_by_spec_load.
1536 Initially, all insns have this flag reset. After a speculative
1537 motion of an insn, if insn is either a load, or marked as
1538 fed_by_spec_load, we will also mark as fed_by_spec_load every
1539 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
1540 load which is fed_by_spec_load is also PRISKY.
1542 MFREE (maybe-free) loads are all the remaining loads. They may be
1543 exception-free, but we cannot prove it.
1545 Now, all loads in IFREE and PFREE classes are considered
1546 exception-free, while all loads in IRISKY and PRISKY classes are
1547 considered exception-risky. As for loads in the MFREE class,
1548 these are considered either exception-free or exception-risky,
1549 depending on whether we are pessimistic or optimistic. We have
1550 to take the pessimistic approach to assure the safety of
1551 speculative scheduling, but we can take the optimistic approach
1552 by invoking the -fsched_spec_load_dangerous option. */
1554 enum INSN_TRAP_CLASS
1556 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
1557 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
1560 #define WORST_CLASS(class1, class2) \
1561 ((class1 > class2) ? class1 : class2)
1563 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
1564 #define IS_REACHABLE(bb_from, bb_to) \
1566 || IS_RGN_ENTRY (bb_from) \
1567 || (TEST_BIT (ancestor_edges[bb_to], \
1568 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))))))
1570 /* Non-zero iff the address is comprised from at most 1 register. */
1571 #define CONST_BASED_ADDRESS_P(x) \
1572 (GET_CODE (x) == REG \
1573 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
1574 || (GET_CODE (x) == LO_SUM)) \
1575 && (CONSTANT_P (XEXP (x, 0)) \
1576 || CONSTANT_P (XEXP (x, 1)))))
1578 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1581 set_spec_fed (load_insn)
1586 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
1587 if (GET_MODE (link) == VOIDmode)
1588 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
1589 } /* set_spec_fed */
1591 /* On the path from the insn to load_insn_bb, find a conditional
1592 branch depending on insn, that guards the speculative load. */
1595 find_conditional_protection (insn, load_insn_bb)
1601 /* Iterate through DEF-USE forward dependences. */
1602 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
1604 rtx next = XEXP (link, 0);
1605 if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
1606 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
1607 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
1608 && load_insn_bb != INSN_BB (next)
1609 && GET_MODE (link) == VOIDmode
1610 && (GET_CODE (next) == JUMP_INSN
1611 || find_conditional_protection (next, load_insn_bb)))
1615 } /* find_conditional_protection */
1617 /* Returns 1 if the same insn1 that participates in the computation
1618 of load_insn's address is feeding a conditional branch that is
1619 guarding on load_insn. This is true if we find a the two DEF-USE
1621 insn1 -> ... -> conditional-branch
1622 insn1 -> ... -> load_insn,
1623 and if a flow path exist:
1624 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1625 and if insn1 is on the path
1626 region-entry -> ... -> bb_trg -> ... load_insn.
1628 Locate insn1 by climbing on LOG_LINKS from load_insn.
1629 Locate the branch by following INSN_DEPEND from insn1. */
1632 is_conditionally_protected (load_insn, bb_src, bb_trg)
1638 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
1640 rtx insn1 = XEXP (link, 0);
1642 /* Must be a DEF-USE dependence upon non-branch. */
1643 if (GET_MODE (link) != VOIDmode
1644 || GET_CODE (insn1) == JUMP_INSN)
1647 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1648 if (INSN_BB (insn1) == bb_src
1649 || (CONTAINING_RGN (BLOCK_NUM (insn1))
1650 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
1651 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
1652 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
1655 /* Now search for the conditional-branch. */
1656 if (find_conditional_protection (insn1, bb_src))
1659 /* Recursive step: search another insn1, "above" current insn1. */
1660 return is_conditionally_protected (insn1, bb_src, bb_trg);
1663 /* The chain does not exist. */
1665 } /* is_conditionally_protected */
1667 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1668 load_insn can move speculatively from bb_src to bb_trg. All the
1669 following must hold:
1671 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1672 (2) load_insn and load1 have a def-use dependence upon
1673 the same insn 'insn1'.
1674 (3) either load2 is in bb_trg, or:
1675 - there's only one split-block, and
1676 - load1 is on the escape path, and
1678 From all these we can conclude that the two loads access memory
1679 addresses that differ at most by a constant, and hence if moving
1680 load_insn would cause an exception, it would have been caused by
1684 is_pfree (load_insn, bb_src, bb_trg)
1689 candidate *candp = candidate_table + bb_src;
1691 if (candp->split_bbs.nr_members != 1)
1692 /* Must have exactly one escape block. */
1695 for (back_link = LOG_LINKS (load_insn);
1696 back_link; back_link = XEXP (back_link, 1))
1698 rtx insn1 = XEXP (back_link, 0);
1700 if (GET_MODE (back_link) == VOIDmode)
1702 /* Found a DEF-USE dependence (insn1, load_insn). */
1705 for (fore_link = INSN_DEPEND (insn1);
1706 fore_link; fore_link = XEXP (fore_link, 1))
1708 rtx insn2 = XEXP (fore_link, 0);
1709 if (GET_MODE (fore_link) == VOIDmode)
1711 /* Found a DEF-USE dependence (insn1, insn2). */
1712 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
1713 /* insn2 not guaranteed to be a 1 base reg load. */
1716 if (INSN_BB (insn2) == bb_trg)
1717 /* insn2 is the similar load, in the target block. */
1720 if (*(candp->split_bbs.first_member) == BLOCK_NUM (insn2))
1721 /* insn2 is a similar load, in a split-block. */
1728 /* Couldn't find a similar load. */
1732 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
1733 as found by analyzing insn's expression. */
1736 may_trap_exp (x, is_store)
1744 code = GET_CODE (x);
1747 if (code == MEM && may_trap_p (x))
1754 /* The insn uses memory: a volatile load. */
1755 if (MEM_VOLATILE_P (x))
1757 /* An exception-free load. */
1758 if (!may_trap_p (x))
1760 /* A load with 1 base register, to be further checked. */
1761 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
1762 return PFREE_CANDIDATE;
1763 /* No info on the load, to be further checked. */
1764 return PRISKY_CANDIDATE;
1769 int i, insn_class = TRAP_FREE;
1771 /* Neither store nor load, check if it may cause a trap. */
1774 /* Recursive step: walk the insn... */
1775 fmt = GET_RTX_FORMAT (code);
1776 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1780 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
1781 insn_class = WORST_CLASS (insn_class, tmp_class);
1783 else if (fmt[i] == 'E')
1786 for (j = 0; j < XVECLEN (x, i); j++)
1788 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
1789 insn_class = WORST_CLASS (insn_class, tmp_class);
1790 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
1794 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
1801 /* Classifies insn for the purpose of verifying that it can be
1802 moved speculatively, by examining it's patterns, returning:
1803 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
1804 TRAP_FREE: non-load insn.
1805 IFREE: load from a globaly safe location.
1806 IRISKY: volatile load.
1807 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
1808 being either PFREE or PRISKY. */
1811 haifa_classify_insn (insn)
1814 rtx pat = PATTERN (insn);
1815 int tmp_class = TRAP_FREE;
1816 int insn_class = TRAP_FREE;
1819 if (GET_CODE (pat) == PARALLEL)
1821 int i, len = XVECLEN (pat, 0);
1823 for (i = len - 1; i >= 0; i--)
1825 code = GET_CODE (XVECEXP (pat, 0, i));
1829 /* Test if it is a 'store'. */
1830 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
1833 /* Test if it is a store. */
1834 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
1835 if (tmp_class == TRAP_RISKY)
1837 /* Test if it is a load. */
1839 = WORST_CLASS (tmp_class,
1840 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)),
1845 tmp_class = TRAP_RISKY;
1850 insn_class = WORST_CLASS (insn_class, tmp_class);
1851 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
1857 code = GET_CODE (pat);
1861 /* Test if it is a 'store'. */
1862 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
1865 /* Test if it is a store. */
1866 tmp_class = may_trap_exp (SET_DEST (pat), 1);
1867 if (tmp_class == TRAP_RISKY)
1869 /* Test if it is a load. */
1871 WORST_CLASS (tmp_class,
1872 may_trap_exp (SET_SRC (pat), 0));
1876 tmp_class = TRAP_RISKY;
1880 insn_class = tmp_class;
1886 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1887 a load moved speculatively, or if load_insn is protected by
1888 a compare on load_insn's address). */
1891 is_prisky (load_insn, bb_src, bb_trg)
1895 if (FED_BY_SPEC_LOAD (load_insn))
1898 if (LOG_LINKS (load_insn) == NULL)
1899 /* Dependence may 'hide' out of the region. */
1902 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
1908 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
1909 Return 1 if insn is exception-free (and the motion is valid)
1913 is_exception_free (insn, bb_src, bb_trg)
1917 int insn_class = haifa_classify_insn (insn);
1919 /* Handle non-load insns. */
1930 if (!flag_schedule_speculative_load)
1932 IS_LOAD_INSN (insn) = 1;
1939 case PFREE_CANDIDATE:
1940 if (is_pfree (insn, bb_src, bb_trg))
1942 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
1943 case PRISKY_CANDIDATE:
1944 if (!flag_schedule_speculative_load_dangerous
1945 || is_prisky (insn, bb_src, bb_trg))
1951 return flag_schedule_speculative_load_dangerous;
1954 /* The number of insns from the current block scheduled so far. */
1955 static int sched_target_n_insns;
1956 /* The number of insns from the current block to be scheduled in total. */
1957 static int target_n_insns;
1958 /* The number of insns from the entire region scheduled so far. */
1959 static int sched_n_insns;
1960 /* Nonzero if the last scheduled insn was a jump. */
1961 static int last_was_jump;
1963 /* Implementations of the sched_info functions for region scheduling. */
1964 static void init_ready_list PARAMS ((struct ready_list *));
1965 static int can_schedule_ready_p PARAMS ((rtx));
1966 static int new_ready PARAMS ((rtx));
1967 static int schedule_more_p PARAMS ((void));
1968 static const char *rgn_print_insn PARAMS ((rtx, int));
1969 static int rgn_rank PARAMS ((rtx, rtx));
1970 static int contributes_to_priority PARAMS ((rtx, rtx));
1971 static void compute_jump_reg_dependencies PARAMS ((rtx, regset));
1973 /* Return nonzero if there are more insns that should be scheduled. */
1978 return ! last_was_jump && sched_target_n_insns < target_n_insns;
1981 /* Add all insns that are initially ready to the ready list READY. Called
1982 once before scheduling a set of insns. */
1985 init_ready_list (ready)
1986 struct ready_list *ready;
1988 rtx prev_head = current_sched_info->prev_head;
1989 rtx next_tail = current_sched_info->next_tail;
1994 sched_target_n_insns = 0;
1998 /* Print debugging information. */
1999 if (sched_verbose >= 5)
2000 debug_dependencies ();
2002 /* Prepare current target block info. */
2003 if (current_nr_blocks > 1)
2005 candidate_table = (candidate *) xmalloc (current_nr_blocks
2006 * sizeof (candidate));
2009 /* bblst_table holds split blocks and update blocks for each block after
2010 the current one in the region. split blocks and update blocks are
2011 the TO blocks of region edges, so there can be at most rgn_nr_edges
2013 bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
2014 bblst_table = (int *) xmalloc (bblst_size * sizeof (int));
2016 bitlst_table_last = 0;
2017 bitlst_table_size = rgn_nr_edges;
2018 bitlst_table = (int *) xmalloc (rgn_nr_edges * sizeof (int));
2020 compute_trg_info (target_bb);
2023 /* Initialize ready list with all 'ready' insns in target block.
2024 Count number of insns in the target block being scheduled. */
2025 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
2029 if (! INSN_P (insn))
2031 next = NEXT_INSN (insn);
2033 if (INSN_DEP_COUNT (insn) == 0
2034 && (SCHED_GROUP_P (next) == 0 || ! INSN_P (next)))
2035 ready_add (ready, insn);
2036 if (!(SCHED_GROUP_P (insn)))
2040 /* Add to ready list all 'ready' insns in valid source blocks.
2041 For speculative insns, check-live, exception-free, and
2043 for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
2044 if (IS_VALID (bb_src))
2050 get_block_head_tail (BB_TO_BLOCK (bb_src), &head, &tail);
2051 src_next_tail = NEXT_INSN (tail);
2054 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
2056 if (! INSN_P (insn))
2059 if (!CANT_MOVE (insn)
2060 && (!IS_SPECULATIVE_INSN (insn)
2061 || ((((!targetm.sched.use_dfa_pipeline_interface
2062 || !(*targetm.sched.use_dfa_pipeline_interface) ())
2063 && insn_issue_delay (insn) <= 3)
2064 || (targetm.sched.use_dfa_pipeline_interface
2065 && (*targetm.sched.use_dfa_pipeline_interface) ()
2066 && (recog_memoized (insn) < 0
2067 || min_insn_conflict_delay (curr_state,
2069 && check_live (insn, bb_src)
2070 && is_exception_free (insn, bb_src, target_bb))))
2074 /* Note that we haven't squirreled away the notes for
2075 blocks other than the current. So if this is a
2076 speculative insn, NEXT might otherwise be a note. */
2077 next = next_nonnote_insn (insn);
2078 if (INSN_DEP_COUNT (insn) == 0
2080 || SCHED_GROUP_P (next) == 0
2081 || ! INSN_P (next)))
2082 ready_add (ready, insn);
2088 /* Called after taking INSN from the ready list. Returns nonzero if this
2089 insn can be scheduled, nonzero if we should silently discard it. */
2092 can_schedule_ready_p (insn)
2095 if (GET_CODE (insn) == JUMP_INSN)
2098 /* An interblock motion? */
2099 if (INSN_BB (insn) != target_bb)
2104 if (IS_SPECULATIVE_INSN (insn))
2106 if (!check_live (insn, INSN_BB (insn)))
2108 update_live (insn, INSN_BB (insn));
2110 /* For speculative load, mark insns fed by it. */
2111 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
2112 set_spec_fed (insn);
2118 /* Find the beginning of the scheduling group. */
2119 /* ??? Ought to update basic block here, but later bits of
2120 schedule_block assumes the original insn block is
2124 while (SCHED_GROUP_P (temp))
2125 temp = PREV_INSN (temp);
2127 /* Update source block boundaries. */
2128 b1 = BLOCK_FOR_INSN (temp);
2129 if (temp == b1->head && insn == b1->end)
2131 /* We moved all the insns in the basic block.
2132 Emit a note after the last insn and update the
2133 begin/end boundaries to point to the note. */
2134 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
2138 else if (insn == b1->end)
2140 /* We took insns from the end of the basic block,
2141 so update the end of block boundary so that it
2142 points to the first insn we did not move. */
2143 b1->end = PREV_INSN (temp);
2145 else if (temp == b1->head)
2147 /* We took insns from the start of the basic block,
2148 so update the start of block boundary so that
2149 it points to the first insn we did not move. */
2150 b1->head = NEXT_INSN (insn);
2155 /* In block motion. */
2156 sched_target_n_insns++;
2163 /* Called after INSN has all its dependencies resolved. Return nonzero
2164 if it should be moved to the ready list or the queue, or zero if we
2165 should silently discard it. */
2170 /* For speculative insns, before inserting to ready/queue,
2171 check live, exception-free, and issue-delay. */
2172 if (INSN_BB (next) != target_bb
2173 && (!IS_VALID (INSN_BB (next))
2175 || (IS_SPECULATIVE_INSN (next)
2177 || (targetm.sched.use_dfa_pipeline_interface
2178 && (*targetm.sched.use_dfa_pipeline_interface) ()
2179 && recog_memoized (next) >= 0
2180 && min_insn_conflict_delay (curr_state, next,
2182 || ((!targetm.sched.use_dfa_pipeline_interface
2183 || !(*targetm.sched.use_dfa_pipeline_interface) ())
2184 && insn_issue_delay (next) > 3)
2185 || !check_live (next, INSN_BB (next))
2186 || !is_exception_free (next, INSN_BB (next), target_bb)))))
2191 /* Return a string that contains the insn uid and optionally anything else
2192 necessary to identify this insn in an output. It's valid to use a
2193 static buffer for this. The ALIGNED parameter should cause the string
2194 to be formatted so that multiple output lines will line up nicely. */
2197 rgn_print_insn (insn, aligned)
2201 static char tmp[80];
2204 sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
2207 if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
2208 sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
2210 sprintf (tmp, "%d", INSN_UID (insn));
2215 /* Compare priority of two insns. Return a positive number if the second
2216 insn is to be preferred for scheduling, and a negative one if the first
2217 is to be preferred. Zero if they are equally good. */
2220 rgn_rank (insn1, insn2)
2223 /* Some comparison make sense in interblock scheduling only. */
2224 if (INSN_BB (insn1) != INSN_BB (insn2))
2226 int spec_val, prob_val;
2228 /* Prefer an inblock motion on an interblock motion. */
2229 if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
2231 if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
2234 /* Prefer a useful motion on a speculative one. */
2235 spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
2239 /* Prefer a more probable (speculative) insn. */
2240 prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
2247 /* NEXT is an instruction that depends on INSN (a backward dependence);
2248 return nonzero if we should include this dependence in priority
2252 contributes_to_priority (next, insn)
2255 return BLOCK_NUM (next) == BLOCK_NUM (insn);
2258 /* INSN is a JUMP_INSN. Store the set of registers that must be considered
2259 to be set by this jump in SET. */
2262 compute_jump_reg_dependencies (insn, set)
2263 rtx insn ATTRIBUTE_UNUSED;
2264 regset set ATTRIBUTE_UNUSED;
2266 /* Nothing to do here, since we postprocess jumps in
2267 add_branch_dependences. */
2270 /* Used in schedule_insns to initialize current_sched_info for scheduling
2271 regions (or single basic blocks). */
2273 static struct sched_info region_sched_info =
2276 can_schedule_ready_p,
2281 contributes_to_priority,
2282 compute_jump_reg_dependencies,
2289 /* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register. */
2292 sets_likely_spilled (pat)
2296 note_stores (pat, sets_likely_spilled_1, &ret);
2301 sets_likely_spilled_1 (x, pat, data)
2305 bool *ret = (bool *) data;
2307 if (GET_CODE (pat) == SET
2309 && REGNO (x) < FIRST_PSEUDO_REGISTER
2310 && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x))))
2314 /* Add dependences so that branches are scheduled to run last in their
2318 add_branch_dependences (head, tail)
2323 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2324 that can throw exceptions, force them to remain in order at the end of
2325 the block by adding dependencies and giving the last a high priority.
2326 There may be notes present, and prev_head may also be a note.
2328 Branches must obviously remain at the end. Calls should remain at the
2329 end since moving them results in worse register allocation. Uses remain
2330 at the end to ensure proper register allocation.
2332 cc0 setters remaim at the end because they can't be moved away from
2335 Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values)
2336 are not moved before reload because we can wind up with register
2337 allocation failures. */
2341 while (GET_CODE (insn) == CALL_INSN
2342 || GET_CODE (insn) == JUMP_INSN
2343 || (GET_CODE (insn) == INSN
2344 && (GET_CODE (PATTERN (insn)) == USE
2345 || GET_CODE (PATTERN (insn)) == CLOBBER
2346 || can_throw_internal (insn)
2348 || sets_cc0_p (PATTERN (insn))
2350 || (!reload_completed
2351 && sets_likely_spilled (PATTERN (insn)))))
2352 || GET_CODE (insn) == NOTE)
2354 if (GET_CODE (insn) != NOTE)
2356 if (last != 0 && !find_insn_list (insn, LOG_LINKS (last)))
2358 add_dependence (last, insn, REG_DEP_ANTI);
2359 INSN_REF_COUNT (insn)++;
2362 CANT_MOVE (insn) = 1;
2365 /* Skip over insns that are part of a group.
2366 Make each insn explicitly depend on the previous insn.
2367 This ensures that only the group header will ever enter
2368 the ready queue (and, when scheduled, will automatically
2369 schedule the SCHED_GROUP_P block). */
2370 while (SCHED_GROUP_P (insn))
2372 rtx temp = prev_nonnote_insn (insn);
2373 add_dependence (insn, temp, REG_DEP_ANTI);
2378 /* Don't overrun the bounds of the basic block. */
2382 insn = PREV_INSN (insn);
2385 /* Make sure these insns are scheduled last in their block. */
2388 while (insn != head)
2390 insn = prev_nonnote_insn (insn);
2392 if (INSN_REF_COUNT (insn) != 0)
2395 add_dependence (last, insn, REG_DEP_ANTI);
2396 INSN_REF_COUNT (insn) = 1;
2398 /* Skip over insns that are part of a group. */
2399 while (SCHED_GROUP_P (insn))
2400 insn = prev_nonnote_insn (insn);
2404 /* Data structures for the computation of data dependences in a regions. We
2405 keep one `deps' structure for every basic block. Before analyzing the
2406 data dependences for a bb, its variables are initialized as a function of
2407 the variables of its predecessors. When the analysis for a bb completes,
2408 we save the contents to the corresponding bb_deps[bb] variable. */
2410 static struct deps *bb_deps;
2412 /* Duplicate the INSN_LIST elements of COPY and prepend them to OLD. */
2415 concat_INSN_LIST (copy, old)
2419 for (; copy ; copy = XEXP (copy, 1))
2420 new = alloc_INSN_LIST (XEXP (copy, 0), new);
2425 concat_insn_mem_list (copy_insns, copy_mems, old_insns_p, old_mems_p)
2426 rtx copy_insns, copy_mems;
2427 rtx *old_insns_p, *old_mems_p;
2429 rtx new_insns = *old_insns_p;
2430 rtx new_mems = *old_mems_p;
2434 new_insns = alloc_INSN_LIST (XEXP (copy_insns, 0), new_insns);
2435 new_mems = alloc_EXPR_LIST (VOIDmode, XEXP (copy_mems, 0), new_mems);
2436 copy_insns = XEXP (copy_insns, 1);
2437 copy_mems = XEXP (copy_mems, 1);
2440 *old_insns_p = new_insns;
2441 *old_mems_p = new_mems;
2444 /* After computing the dependencies for block BB, propagate the dependencies
2445 found in TMP_DEPS to the successors of the block. */
2447 propagate_deps (bb, pred_deps)
2449 struct deps *pred_deps;
2451 int b = BB_TO_BLOCK (bb);
2454 /* bb's structures are inherited by its successors. */
2455 first_edge = e = OUT_EDGES (b);
2459 int b_succ = TO_BLOCK (e);
2460 int bb_succ = BLOCK_TO_BB (b_succ);
2461 struct deps *succ_deps = bb_deps + bb_succ;
2464 /* Only bbs "below" bb, in the same region, are interesting. */
2465 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
2472 /* The reg_last lists are inherited by bb_succ. */
2473 EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg,
2475 struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
2476 struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
2478 succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
2479 succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
2480 succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
2482 succ_rl->uses_length += pred_rl->uses_length;
2483 succ_rl->clobbers_length += pred_rl->clobbers_length;
2485 IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
2487 /* Mem read/write lists are inherited by bb_succ. */
2488 concat_insn_mem_list (pred_deps->pending_read_insns,
2489 pred_deps->pending_read_mems,
2490 &succ_deps->pending_read_insns,
2491 &succ_deps->pending_read_mems);
2492 concat_insn_mem_list (pred_deps->pending_write_insns,
2493 pred_deps->pending_write_mems,
2494 &succ_deps->pending_write_insns,
2495 &succ_deps->pending_write_mems);
2497 succ_deps->last_pending_memory_flush
2498 = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
2499 succ_deps->last_pending_memory_flush);
2501 succ_deps->pending_lists_length += pred_deps->pending_lists_length;
2502 succ_deps->pending_flush_length += pred_deps->pending_flush_length;
2504 /* last_function_call is inherited by bb_succ. */
2505 succ_deps->last_function_call
2506 = concat_INSN_LIST (pred_deps->last_function_call,
2507 succ_deps->last_function_call);
2509 /* sched_before_next_call is inherited by bb_succ. */
2510 succ_deps->sched_before_next_call
2511 = concat_INSN_LIST (pred_deps->sched_before_next_call,
2512 succ_deps->sched_before_next_call);
2516 while (e != first_edge);
2518 /* These lists should point to the right place, for correct
2520 bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
2521 bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
2522 bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
2523 bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
2525 /* Can't allow these to be freed twice. */
2526 pred_deps->pending_read_insns = 0;
2527 pred_deps->pending_read_mems = 0;
2528 pred_deps->pending_write_insns = 0;
2529 pred_deps->pending_write_mems = 0;
2532 /* Compute backward dependences inside bb. In a multiple blocks region:
2533 (1) a bb is analyzed after its predecessors, and (2) the lists in
2534 effect at the end of bb (after analyzing for bb) are inherited by
2537 Specifically for reg-reg data dependences, the block insns are
2538 scanned by sched_analyze () top-to-bottom. Two lists are
2539 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2540 and reg_last[].uses for register USEs.
2542 When analysis is completed for bb, we update for its successors:
2543 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2544 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2546 The mechanism for computing mem-mem data dependence is very
2547 similar, and the result is interblock dependences in the region. */
2550 compute_block_backward_dependences (bb)
2554 struct deps tmp_deps;
2556 tmp_deps = bb_deps[bb];
2558 /* Do the analysis for this block. */
2559 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2560 sched_analyze (&tmp_deps, head, tail);
2561 add_branch_dependences (head, tail);
2563 if (current_nr_blocks > 1)
2564 propagate_deps (bb, &tmp_deps);
2566 /* Free up the INSN_LISTs. */
2567 free_deps (&tmp_deps);
2570 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2571 them to the unused_*_list variables, so that they can be reused. */
2574 free_pending_lists ()
2578 for (bb = 0; bb < current_nr_blocks; bb++)
2580 free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
2581 free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
2582 free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
2583 free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
2587 /* Print dependences for debugging, callable from debugger. */
2590 debug_dependencies ()
2594 fprintf (sched_dump, ";; --------------- forward dependences: ------------ \n");
2595 for (bb = 0; bb < current_nr_blocks; bb++)
2603 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2604 next_tail = NEXT_INSN (tail);
2605 fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
2606 BB_TO_BLOCK (bb), bb);
2608 if (targetm.sched.use_dfa_pipeline_interface
2609 && (*targetm.sched.use_dfa_pipeline_interface) ())
2611 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2612 "insn", "code", "bb", "dep", "prio", "cost",
2614 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2615 "----", "----", "--", "---", "----", "----",
2620 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
2621 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
2622 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
2623 "----", "----", "--", "---", "----", "----", "--------", "-----");
2626 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2630 if (! INSN_P (insn))
2633 fprintf (sched_dump, ";; %6d ", INSN_UID (insn));
2634 if (GET_CODE (insn) == NOTE)
2636 n = NOTE_LINE_NUMBER (insn);
2638 fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
2640 fprintf (sched_dump, "line %d, file %s\n", n,
2641 NOTE_SOURCE_FILE (insn));
2644 fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
2648 if (targetm.sched.use_dfa_pipeline_interface
2649 && (*targetm.sched.use_dfa_pipeline_interface) ())
2651 fprintf (sched_dump,
2652 ";; %s%5d%6d%6d%6d%6d%6d ",
2653 (SCHED_GROUP_P (insn) ? "+" : " "),
2657 INSN_DEP_COUNT (insn),
2658 INSN_PRIORITY (insn),
2659 insn_cost (insn, 0, 0));
2661 if (recog_memoized (insn) < 0)
2662 fprintf (sched_dump, "nothing");
2664 print_reservation (sched_dump, insn);
2668 int unit = insn_unit (insn);
2671 || function_units[unit].blockage_range_function == 0
2673 : function_units[unit].blockage_range_function (insn));
2674 fprintf (sched_dump,
2675 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
2676 (SCHED_GROUP_P (insn) ? "+" : " "),
2680 INSN_DEP_COUNT (insn),
2681 INSN_PRIORITY (insn),
2682 insn_cost (insn, 0, 0),
2683 (int) MIN_BLOCKAGE_COST (range),
2684 (int) MAX_BLOCKAGE_COST (range));
2685 insn_print_units (insn);
2688 fprintf (sched_dump, "\t: ");
2689 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2690 fprintf (sched_dump, "%d ", INSN_UID (XEXP (link, 0)));
2691 fprintf (sched_dump, "\n");
2695 fprintf (sched_dump, "\n");
2698 /* Schedule a region. A region is either an inner loop, a loop-free
2699 subroutine, or a single basic block. Each bb in the region is
2700 scheduled after its flow predecessors. */
2703 schedule_region (rgn)
2707 int rgn_n_insns = 0;
2708 int sched_rgn_n_insns = 0;
2710 /* Set variables for the current region. */
2711 current_nr_blocks = RGN_NR_BLOCKS (rgn);
2712 current_blocks = RGN_BLOCKS (rgn);
2714 init_deps_global ();
2716 /* Initializations for region data dependence analyisis. */
2717 bb_deps = (struct deps *) xmalloc (sizeof (struct deps) * current_nr_blocks);
2718 for (bb = 0; bb < current_nr_blocks; bb++)
2719 init_deps (bb_deps + bb);
2721 /* Compute LOG_LINKS. */
2722 for (bb = 0; bb < current_nr_blocks; bb++)
2723 compute_block_backward_dependences (bb);
2725 /* Compute INSN_DEPEND. */
2726 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
2729 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2731 compute_forward_dependences (head, tail);
2734 /* Set priorities. */
2735 for (bb = 0; bb < current_nr_blocks; bb++)
2738 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2740 rgn_n_insns += set_priorities (head, tail);
2743 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
2744 if (current_nr_blocks > 1)
2748 prob = (float *) xmalloc ((current_nr_blocks) * sizeof (float));
2750 dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
2751 sbitmap_vector_zero (dom, current_nr_blocks);
2754 edge_to_bit = (int *) xmalloc (nr_edges * sizeof (int));
2755 for (i = 1; i < nr_edges; i++)
2756 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
2757 EDGE_TO_BIT (i) = rgn_nr_edges++;
2758 rgn_edges = (int *) xmalloc (rgn_nr_edges * sizeof (int));
2761 for (i = 1; i < nr_edges; i++)
2762 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
2763 rgn_edges[rgn_nr_edges++] = i;
2766 pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2767 sbitmap_vector_zero (pot_split, current_nr_blocks);
2768 ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2769 sbitmap_vector_zero (ancestor_edges, current_nr_blocks);
2771 /* Compute probabilities, dominators, split_edges. */
2772 for (bb = 0; bb < current_nr_blocks; bb++)
2773 compute_dom_prob_ps (bb);
2776 /* Now we can schedule all blocks. */
2777 for (bb = 0; bb < current_nr_blocks; bb++)
2780 int b = BB_TO_BLOCK (bb);
2782 get_block_head_tail (b, &head, &tail);
2784 if (no_real_insns_p (head, tail))
2787 current_sched_info->prev_head = PREV_INSN (head);
2788 current_sched_info->next_tail = NEXT_INSN (tail);
2790 if (write_symbols != NO_DEBUG)
2792 save_line_notes (b, head, tail);
2793 rm_line_notes (head, tail);
2796 /* rm_other_notes only removes notes which are _inside_ the
2797 block---that is, it won't remove notes before the first real insn
2798 or after the last real insn of the block. So if the first insn
2799 has a REG_SAVE_NOTE which would otherwise be emitted before the
2800 insn, it is redundant with the note before the start of the
2801 block, and so we have to take it out. */
2806 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
2807 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
2809 remove_note (head, note);
2810 note = XEXP (note, 1);
2811 remove_note (head, note);
2815 /* Remove remaining note insns from the block, save them in
2816 note_list. These notes are restored at the end of
2817 schedule_block (). */
2818 rm_other_notes (head, tail);
2822 current_sched_info->queue_must_finish_empty
2823 = current_nr_blocks > 1 && !flag_schedule_interblock;
2825 schedule_block (b, rgn_n_insns);
2826 sched_rgn_n_insns += sched_n_insns;
2828 /* Update target block boundaries. */
2829 if (head == BLOCK_HEAD (b))
2830 BLOCK_HEAD (b) = current_sched_info->head;
2831 if (tail == BLOCK_END (b))
2832 BLOCK_END (b) = current_sched_info->tail;
2835 if (current_nr_blocks > 1)
2837 free (candidate_table);
2839 free (bitlst_table);
2843 /* Sanity check: verify that all region insns were scheduled. */
2844 if (sched_rgn_n_insns != rgn_n_insns)
2847 /* Restore line notes. */
2848 if (write_symbols != NO_DEBUG)
2850 for (bb = 0; bb < current_nr_blocks; bb++)
2853 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2854 restore_line_notes (head, tail);
2858 /* Done with this region. */
2859 free_pending_lists ();
2861 finish_deps_global ();
2865 if (current_nr_blocks > 1)
2868 sbitmap_vector_free (dom);
2869 sbitmap_vector_free (pot_split);
2870 sbitmap_vector_free (ancestor_edges);
2876 /* Indexed by region, holds the number of death notes found in that region.
2877 Used for consistency checks. */
2878 static int *deaths_in_region;
2880 /* Initialize data structures for region scheduling. */
2889 rgn_table = (region *) xmalloc ((n_basic_blocks) * sizeof (region));
2890 rgn_bb_table = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
2891 block_to_bb = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
2892 containing_rgn = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
2894 /* Compute regions for scheduling. */
2895 if (reload_completed
2896 || n_basic_blocks == 1
2897 || !flag_schedule_interblock)
2899 find_single_block_region ();
2903 /* Verify that a 'good' control flow graph can be built. */
2904 if (is_cfg_nonregular ())
2906 find_single_block_region ();
2911 struct edge_list *edge_list;
2913 dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
2915 /* The scheduler runs after flow; therefore, we can't blindly call
2916 back into find_basic_blocks since doing so could invalidate the
2917 info in global_live_at_start.
2919 Consider a block consisting entirely of dead stores; after life
2920 analysis it would be a block of NOTE_INSN_DELETED notes. If
2921 we call find_basic_blocks again, then the block would be removed
2922 entirely and invalidate our the register live information.
2924 We could (should?) recompute register live information. Doing
2925 so may even be beneficial. */
2926 edge_list = create_edge_list ();
2928 /* Compute the dominators and post dominators. */
2929 calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
2931 /* build_control_flow will return nonzero if it detects unreachable
2932 blocks or any other irregularity with the cfg which prevents
2933 cross block scheduling. */
2934 if (build_control_flow (edge_list) != 0)
2935 find_single_block_region ();
2937 find_rgns (edge_list, dom);
2939 if (sched_verbose >= 3)
2942 /* We are done with flow's edge list. */
2943 free_edge_list (edge_list);
2945 /* For now. This will move as more and more of haifa is converted
2946 to using the cfg code in flow.c. */
2952 if (CHECK_DEAD_NOTES)
2954 blocks = sbitmap_alloc (n_basic_blocks);
2955 deaths_in_region = (int *) xmalloc (sizeof (int) * nr_regions);
2956 /* Remove all death notes from the subroutine. */
2957 for (rgn = 0; rgn < nr_regions; rgn++)
2961 sbitmap_zero (blocks);
2962 for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
2963 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]);
2965 deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1);
2967 sbitmap_free (blocks);
2970 count_or_remove_death_notes (NULL, 1);
2973 /* The one entry point in this file. DUMP_FILE is the dump file for
2977 schedule_insns (dump_file)
2980 sbitmap large_region_blocks, blocks;
2982 int any_large_regions;
2984 /* Taking care of this degenerate case makes the rest of
2985 this code simpler. */
2986 if (n_basic_blocks == 0)
2989 scope_to_insns_initialize ();
2994 sched_init (dump_file);
2998 current_sched_info = ®ion_sched_info;
3000 /* Schedule every region in the subroutine. */
3001 for (rgn = 0; rgn < nr_regions; rgn++)
3002 schedule_region (rgn);
3004 /* Update life analysis for the subroutine. Do single block regions
3005 first so that we can verify that live_at_start didn't change. Then
3006 do all other blocks. */
3007 /* ??? There is an outside possibility that update_life_info, or more
3008 to the point propagate_block, could get called with non-zero flags
3009 more than once for one basic block. This would be kinda bad if it
3010 were to happen, since REG_INFO would be accumulated twice for the
3011 block, and we'd have twice the REG_DEAD notes.
3013 I'm fairly certain that this _shouldn't_ happen, since I don't think
3014 that live_at_start should change at region heads. Not sure what the
3015 best way to test for this kind of thing... */
3017 allocate_reg_life_data ();
3018 compute_bb_for_insn (get_max_uid ());
3020 any_large_regions = 0;
3021 large_region_blocks = sbitmap_alloc (n_basic_blocks);
3022 sbitmap_ones (large_region_blocks);
3024 blocks = sbitmap_alloc (n_basic_blocks);
3025 sbitmap_zero (blocks);
3027 /* Update life information. For regions consisting of multiple blocks
3028 we've possibly done interblock scheduling that affects global liveness.
3029 For regions consisting of single blocks we need to do only local
3031 for (rgn = 0; rgn < nr_regions; rgn++)
3032 if (RGN_NR_BLOCKS (rgn) > 1)
3033 any_large_regions = 1;
3036 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
3037 RESET_BIT (large_region_blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
3040 /* Don't update reg info after reload, since that affects
3041 regs_ever_live, which should not change after reload. */
3042 update_life_info (blocks, UPDATE_LIFE_LOCAL,
3043 (reload_completed ? PROP_DEATH_NOTES
3044 : PROP_DEATH_NOTES | PROP_REG_INFO));
3045 if (any_large_regions)
3047 update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL,
3048 PROP_DEATH_NOTES | PROP_REG_INFO);
3051 if (CHECK_DEAD_NOTES)
3053 /* Verify the counts of basic block notes in single the basic block
3055 for (rgn = 0; rgn < nr_regions; rgn++)
3056 if (RGN_NR_BLOCKS (rgn) == 1)
3058 sbitmap_zero (blocks);
3059 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
3061 if (deaths_in_region[rgn]
3062 != count_or_remove_death_notes (blocks, 0))
3065 free (deaths_in_region);
3068 /* Reposition the prologue and epilogue notes in case we moved the
3069 prologue/epilogue insns. */
3070 if (reload_completed)
3071 reposition_prologue_and_epilogue_notes (get_insns ());
3073 /* Delete redundant line notes. */
3074 if (write_symbols != NO_DEBUG)
3075 rm_redundant_line_notes ();
3077 scope_to_insns_finalize ();
3081 if (reload_completed == 0 && flag_schedule_interblock)
3083 fprintf (sched_dump,
3084 "\n;; Procedure interblock/speculative motions == %d/%d \n",
3092 fprintf (sched_dump, "\n\n");
3097 free (rgn_bb_table);
3099 free (containing_rgn);
3120 sbitmap_free (blocks);
3121 sbitmap_free (large_region_blocks);