Use MODE_BASE_REG_CLASS in legitimize macros.
[official-gcc.git] / gcc / sched-rgn.c
blob892c03fb27663ddc1addd702b21493f0e134b84e
1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001 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
12 version.
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
17 for more details.
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
22 02111-1307, USA. */
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. */
48 #include "config.h"
49 #include "system.h"
50 #include "toplev.h"
51 #include "rtl.h"
52 #include "tm_p.h"
53 #include "hard-reg-set.h"
54 #include "basic-block.h"
55 #include "regs.h"
56 #include "function.h"
57 #include "flags.h"
58 #include "insn-config.h"
59 #include "insn-attr.h"
60 #include "except.h"
61 #include "toplev.h"
62 #include "recog.h"
63 #include "cfglayout.h"
64 #include "sched-int.h"
66 /* Define when we want to do count REG_DEAD notes before and after scheduling
67 for sanity checking. We can't do that when conditional execution is used,
68 as REG_DEAD exist only for unconditional deaths. */
70 #if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING)
71 #define CHECK_DEAD_NOTES 1
72 #else
73 #define CHECK_DEAD_NOTES 0
74 #endif
77 #ifdef INSN_SCHEDULING
78 /* Some accessor macros for h_i_d members only used within this file. */
79 #define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count)
80 #define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load)
81 #define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn)
83 #define MAX_RGN_BLOCKS 10
84 #define MAX_RGN_INSNS 100
86 /* nr_inter/spec counts interblock/speculative motion for the function. */
87 static int nr_inter, nr_spec;
89 /* Control flow graph edges are kept in circular lists. */
90 typedef struct
92 int from_block;
93 int to_block;
94 int next_in;
95 int next_out;
97 haifa_edge;
98 static haifa_edge *edge_table;
100 #define NEXT_IN(edge) (edge_table[edge].next_in)
101 #define NEXT_OUT(edge) (edge_table[edge].next_out)
102 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
103 #define TO_BLOCK(edge) (edge_table[edge].to_block)
105 /* Number of edges in the control flow graph. (In fact, larger than
106 that by 1, since edge 0 is unused.) */
107 static int nr_edges;
109 /* Circular list of incoming/outgoing edges of a block. */
110 static int *in_edges;
111 static int *out_edges;
113 #define IN_EDGES(block) (in_edges[block])
114 #define OUT_EDGES(block) (out_edges[block])
116 static int is_cfg_nonregular PARAMS ((void));
117 static int build_control_flow PARAMS ((struct edge_list *));
118 static void new_edge PARAMS ((int, int));
120 /* A region is the main entity for interblock scheduling: insns
121 are allowed to move between blocks in the same region, along
122 control flow graph edges, in the 'up' direction. */
123 typedef struct
125 int rgn_nr_blocks; /* Number of blocks in region. */
126 int rgn_blocks; /* cblocks in the region (actually index in rgn_bb_table). */
128 region;
130 /* Number of regions in the procedure. */
131 static int nr_regions;
133 /* Table of region descriptions. */
134 static region *rgn_table;
136 /* Array of lists of regions' blocks. */
137 static int *rgn_bb_table;
139 /* Topological order of blocks in the region (if b2 is reachable from
140 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
141 always referred to by either block or b, while its topological
142 order name (in the region) is refered to by bb. */
143 static int *block_to_bb;
145 /* The number of the region containing a block. */
146 static int *containing_rgn;
148 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
149 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
150 #define BLOCK_TO_BB(block) (block_to_bb[block])
151 #define CONTAINING_RGN(block) (containing_rgn[block])
153 void debug_regions PARAMS ((void));
154 static void find_single_block_region PARAMS ((void));
155 static void find_rgns PARAMS ((struct edge_list *, sbitmap *));
156 static int too_large PARAMS ((int, int *, int *));
158 extern void debug_live PARAMS ((int, int));
160 /* Blocks of the current region being scheduled. */
161 static int current_nr_blocks;
162 static int current_blocks;
164 /* The mapping from bb to block. */
165 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
167 typedef struct
169 int *first_member; /* Pointer to the list start in bitlst_table. */
170 int nr_members; /* The number of members of the bit list. */
172 bitlst;
174 static int bitlst_table_last;
175 static int bitlst_table_size;
176 static int *bitlst_table;
178 static void extract_bitlst PARAMS ((sbitmap, bitlst *));
180 /* Target info declarations.
182 The block currently being scheduled is referred to as the "target" block,
183 while other blocks in the region from which insns can be moved to the
184 target are called "source" blocks. The candidate structure holds info
185 about such sources: are they valid? Speculative? Etc. */
186 typedef bitlst bblst;
187 typedef struct
189 char is_valid;
190 char is_speculative;
191 int src_prob;
192 bblst split_bbs;
193 bblst update_bbs;
195 candidate;
197 static candidate *candidate_table;
199 /* A speculative motion requires checking live information on the path
200 from 'source' to 'target'. The split blocks are those to be checked.
201 After a speculative motion, live information should be modified in
202 the 'update' blocks.
204 Lists of split and update blocks for each candidate of the current
205 target are in array bblst_table. */
206 static int *bblst_table, bblst_size, bblst_last;
208 #define IS_VALID(src) ( candidate_table[src].is_valid )
209 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
210 #define SRC_PROB(src) ( candidate_table[src].src_prob )
212 /* The bb being currently scheduled. */
213 static int target_bb;
215 /* List of edges. */
216 typedef bitlst edgelst;
218 /* Target info functions. */
219 static void split_edges PARAMS ((int, int, edgelst *));
220 static void compute_trg_info PARAMS ((int));
221 void debug_candidate PARAMS ((int));
222 void debug_candidates PARAMS ((int));
224 /* Dominators array: dom[i] contains the sbitmap of dominators of
225 bb i in the region. */
226 static sbitmap *dom;
228 /* bb 0 is the only region entry. */
229 #define IS_RGN_ENTRY(bb) (!bb)
231 /* Is bb_src dominated by bb_trg. */
232 #define IS_DOMINATED(bb_src, bb_trg) \
233 ( TEST_BIT (dom[bb_src], bb_trg) )
235 /* Probability: Prob[i] is a float in [0, 1] which is the probability
236 of bb i relative to the region entry. */
237 static float *prob;
239 /* The probability of bb_src, relative to bb_trg. Note, that while the
240 'prob[bb]' is a float in [0, 1], this macro returns an integer
241 in [0, 100]. */
242 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
243 prob[bb_trg])))
245 /* Bit-set of edges, where bit i stands for edge i. */
246 typedef sbitmap edgeset;
248 /* Number of edges in the region. */
249 static int rgn_nr_edges;
251 /* Array of size rgn_nr_edges. */
252 static int *rgn_edges;
255 /* Mapping from each edge in the graph to its number in the rgn. */
256 static int *edge_to_bit;
257 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
259 /* The split edges of a source bb is different for each target
260 bb. In order to compute this efficiently, the 'potential-split edges'
261 are computed for each bb prior to scheduling a region. This is actually
262 the split edges of each bb relative to the region entry.
264 pot_split[bb] is the set of potential split edges of bb. */
265 static edgeset *pot_split;
267 /* For every bb, a set of its ancestor edges. */
268 static edgeset *ancestor_edges;
270 static void compute_dom_prob_ps PARAMS ((int));
272 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
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 copmute_trg_info. */
279 #define MIN_DIFF_PRIORITY 2
280 #define MIN_PROBABILITY 40
281 #define MIN_PROB_DIFF 10
283 /* Speculative scheduling functions. */
284 static int check_live_1 PARAMS ((int, rtx));
285 static void update_live_1 PARAMS ((int, rtx));
286 static int check_live PARAMS ((rtx, int));
287 static void update_live PARAMS ((rtx, int));
288 static void set_spec_fed PARAMS ((rtx));
289 static int is_pfree PARAMS ((rtx, int, int));
290 static int find_conditional_protection PARAMS ((rtx, int));
291 static int is_conditionally_protected PARAMS ((rtx, int, int));
292 static int may_trap_exp PARAMS ((rtx, int));
293 static int haifa_classify_insn PARAMS ((rtx));
294 static int is_prisky PARAMS ((rtx, int, int));
295 static int is_exception_free PARAMS ((rtx, int, int));
297 static void add_branch_dependences PARAMS ((rtx, rtx));
298 static void compute_block_backward_dependences PARAMS ((int));
299 void debug_dependencies PARAMS ((void));
301 static void init_regions PARAMS ((void));
302 static void schedule_region PARAMS ((int));
303 static void propagate_deps PARAMS ((int, struct deps *));
304 static void free_pending_lists PARAMS ((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. */
314 static int
315 is_cfg_nonregular ()
317 int b;
318 rtx insn;
319 RTX_CODE code;
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)
324 return 1;
326 /* If we have any forced labels, then the cfg is not well structured. */
327 if (forced_labels)
328 return 1;
330 /* If this function has a computed jump, then we consider the cfg
331 not well structured. */
332 if (current_function_has_computed_jump)
333 return 1;
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 (exception_handler_labels)
339 return 1;
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. */
344 for (b = 0; b < n_basic_blocks; b++)
345 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
347 code = GET_CODE (insn);
348 if (GET_RTX_CLASS (code) == 'i' && code != JUMP_INSN)
350 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
352 if (note
353 && ! (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
354 && find_reg_note (NEXT_INSN (insn), REG_LABEL,
355 XEXP (note, 0))))
356 return 1;
359 if (insn == BLOCK_END (b))
360 break;
363 /* All the tests passed. Consider the cfg well structured. */
364 return 0;
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. */
375 static int
376 build_control_flow (edge_list)
377 struct edge_list *edge_list;
379 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. */
390 unreachable = 0;
391 for (i = 0; i < n_basic_blocks; i++)
393 basic_block b = BASIC_BLOCK (i);
395 if (b->pred == NULL
396 || (b->pred->src == b
397 && b->pred->pred_next == NULL))
398 unreachable = 1;
401 /* ??? We can kill these soon. */
402 in_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
403 out_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
404 edge_table = (haifa_edge *) xcalloc (num_edges, sizeof (haifa_edge));
406 nr_edges = 0;
407 for (i = 0; i < num_edges; i++)
409 edge e = INDEX_EDGE (edge_list, i);
411 if (e->dest != EXIT_BLOCK_PTR
412 && e->src != ENTRY_BLOCK_PTR)
413 new_edge (e->src->index, e->dest->index);
416 /* Increment by 1, since edge 0 is unused. */
417 nr_edges++;
419 return unreachable;
422 /* Record an edge in the control flow graph from SOURCE to TARGET.
424 In theory, this is redundant with the s_succs computed above, but
425 we have not converted all of haifa to use information from the
426 integer lists. */
428 static void
429 new_edge (source, target)
430 int source, target;
432 int e, next_edge;
433 int curr_edge, fst_edge;
435 /* Check for duplicates. */
436 fst_edge = curr_edge = OUT_EDGES (source);
437 while (curr_edge)
439 if (FROM_BLOCK (curr_edge) == source
440 && TO_BLOCK (curr_edge) == target)
442 return;
445 curr_edge = NEXT_OUT (curr_edge);
447 if (fst_edge == curr_edge)
448 break;
451 e = ++nr_edges;
453 FROM_BLOCK (e) = source;
454 TO_BLOCK (e) = target;
456 if (OUT_EDGES (source))
458 next_edge = NEXT_OUT (OUT_EDGES (source));
459 NEXT_OUT (OUT_EDGES (source)) = e;
460 NEXT_OUT (e) = next_edge;
462 else
464 OUT_EDGES (source) = e;
465 NEXT_OUT (e) = e;
468 if (IN_EDGES (target))
470 next_edge = NEXT_IN (IN_EDGES (target));
471 NEXT_IN (IN_EDGES (target)) = e;
472 NEXT_IN (e) = next_edge;
474 else
476 IN_EDGES (target) = e;
477 NEXT_IN (e) = e;
481 /* Translate a bit-set SET to a list BL of the bit-set members. */
483 static void
484 extract_bitlst (set, bl)
485 sbitmap set;
486 bitlst *bl;
488 int i;
490 /* bblst table space is reused in each call to extract_bitlst. */
491 bitlst_table_last = 0;
493 bl->first_member = &bitlst_table[bitlst_table_last];
494 bl->nr_members = 0;
496 /* Iterate over each word in the bitset. */
497 EXECUTE_IF_SET_IN_SBITMAP (set, 0, i,
499 bitlst_table[bitlst_table_last++] = i;
500 (bl->nr_members)++;
505 /* Functions for the construction of regions. */
507 /* Print the regions, for debugging purposes. Callable from debugger. */
509 void
510 debug_regions ()
512 int rgn, bb;
514 fprintf (sched_dump, "\n;; ------------ REGIONS ----------\n\n");
515 for (rgn = 0; rgn < nr_regions; rgn++)
517 fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
518 rgn_table[rgn].rgn_nr_blocks);
519 fprintf (sched_dump, ";;\tbb/block: ");
521 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
523 current_blocks = RGN_BLOCKS (rgn);
525 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
526 abort ();
528 fprintf (sched_dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
531 fprintf (sched_dump, "\n\n");
535 /* Build a single block region for each basic block in the function.
536 This allows for using the same code for interblock and basic block
537 scheduling. */
539 static void
540 find_single_block_region ()
542 int i;
544 for (i = 0; i < n_basic_blocks; i++)
546 rgn_bb_table[i] = i;
547 RGN_NR_BLOCKS (i) = 1;
548 RGN_BLOCKS (i) = i;
549 CONTAINING_RGN (i) = i;
550 BLOCK_TO_BB (i) = 0;
552 nr_regions = n_basic_blocks;
555 /* Update number of blocks and the estimate for number of insns
556 in the region. Return 1 if the region is "too large" for interblock
557 scheduling (compile time considerations), otherwise return 0. */
559 static int
560 too_large (block, num_bbs, num_insns)
561 int block, *num_bbs, *num_insns;
563 (*num_bbs)++;
564 (*num_insns) += (INSN_LUID (BLOCK_END (block)) -
565 INSN_LUID (BLOCK_HEAD (block)));
566 if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
567 return 1;
568 else
569 return 0;
572 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
573 is still an inner loop. Put in max_hdr[blk] the header of the most inner
574 loop containing blk. */
575 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
577 if (max_hdr[blk] == -1) \
578 max_hdr[blk] = hdr; \
579 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
580 RESET_BIT (inner, hdr); \
581 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
583 RESET_BIT (inner,max_hdr[blk]); \
584 max_hdr[blk] = hdr; \
588 /* Find regions for interblock scheduling.
590 A region for scheduling can be:
592 * A loop-free procedure, or
594 * A reducible inner loop, or
596 * A basic block not contained in any other region.
598 ?!? In theory we could build other regions based on extended basic
599 blocks or reverse extended basic blocks. Is it worth the trouble?
601 Loop blocks that form a region are put into the region's block list
602 in topological order.
604 This procedure stores its results into the following global (ick) variables
606 * rgn_nr
607 * rgn_table
608 * rgn_bb_table
609 * block_to_bb
610 * containing region
612 We use dominator relationships to avoid making regions out of non-reducible
613 loops.
615 This procedure needs to be converted to work on pred/succ lists instead
616 of edge tables. That would simplify it somewhat. */
618 static void
619 find_rgns (edge_list, dom)
620 struct edge_list *edge_list;
621 sbitmap *dom;
623 int *max_hdr, *dfs_nr, *stack, *degree;
624 char no_loops = 1;
625 int node, child, loop_head, i, head, tail;
626 int count = 0, sp, idx = 0, current_edge = out_edges[0];
627 int num_bbs, num_insns, unreachable;
628 int too_large_failure;
630 /* Note if an edge has been passed. */
631 sbitmap passed;
633 /* Note if a block is a natural loop header. */
634 sbitmap header;
636 /* Note if a block is an natural inner loop header. */
637 sbitmap inner;
639 /* Note if a block is in the block queue. */
640 sbitmap in_queue;
642 /* Note if a block is in the block queue. */
643 sbitmap in_stack;
645 int num_edges = NUM_EDGES (edge_list);
647 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
648 and a mapping from block to its loop header (if the block is contained
649 in a loop, else -1).
651 Store results in HEADER, INNER, and MAX_HDR respectively, these will
652 be used as inputs to the second traversal.
654 STACK, SP and DFS_NR are only used during the first traversal. */
656 /* Allocate and initialize variables for the first traversal. */
657 max_hdr = (int *) xmalloc (n_basic_blocks * sizeof (int));
658 dfs_nr = (int *) xcalloc (n_basic_blocks, sizeof (int));
659 stack = (int *) xmalloc (nr_edges * sizeof (int));
661 inner = sbitmap_alloc (n_basic_blocks);
662 sbitmap_ones (inner);
664 header = sbitmap_alloc (n_basic_blocks);
665 sbitmap_zero (header);
667 passed = sbitmap_alloc (nr_edges);
668 sbitmap_zero (passed);
670 in_queue = sbitmap_alloc (n_basic_blocks);
671 sbitmap_zero (in_queue);
673 in_stack = sbitmap_alloc (n_basic_blocks);
674 sbitmap_zero (in_stack);
676 for (i = 0; i < n_basic_blocks; i++)
677 max_hdr[i] = -1;
679 /* DFS traversal to find inner loops in the cfg. */
681 sp = -1;
682 while (1)
684 if (current_edge == 0 || TEST_BIT (passed, current_edge))
686 /* We have reached a leaf node or a node that was already
687 processed. Pop edges off the stack until we find
688 an edge that has not yet been processed. */
689 while (sp >= 0
690 && (current_edge == 0 || TEST_BIT (passed, current_edge)))
692 /* Pop entry off the stack. */
693 current_edge = stack[sp--];
694 node = FROM_BLOCK (current_edge);
695 child = TO_BLOCK (current_edge);
696 RESET_BIT (in_stack, child);
697 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
698 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
699 current_edge = NEXT_OUT (current_edge);
702 /* See if have finished the DFS tree traversal. */
703 if (sp < 0 && TEST_BIT (passed, current_edge))
704 break;
706 /* Nope, continue the traversal with the popped node. */
707 continue;
710 /* Process a node. */
711 node = FROM_BLOCK (current_edge);
712 child = TO_BLOCK (current_edge);
713 SET_BIT (in_stack, node);
714 dfs_nr[node] = ++count;
716 /* If the successor is in the stack, then we've found a loop.
717 Mark the loop, if it is not a natural loop, then it will
718 be rejected during the second traversal. */
719 if (TEST_BIT (in_stack, child))
721 no_loops = 0;
722 SET_BIT (header, child);
723 UPDATE_LOOP_RELATIONS (node, child);
724 SET_BIT (passed, current_edge);
725 current_edge = NEXT_OUT (current_edge);
726 continue;
729 /* If the child was already visited, then there is no need to visit
730 it again. Just update the loop relationships and restart
731 with a new edge. */
732 if (dfs_nr[child])
734 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
735 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
736 SET_BIT (passed, current_edge);
737 current_edge = NEXT_OUT (current_edge);
738 continue;
741 /* Push an entry on the stack and continue DFS traversal. */
742 stack[++sp] = current_edge;
743 SET_BIT (passed, current_edge);
744 current_edge = OUT_EDGES (child);
746 /* This is temporary until haifa is converted to use rth's new
747 cfg routines which have true entry/exit blocks and the
748 appropriate edges from/to those blocks.
750 Generally we update dfs_nr for a node when we process its
751 out edge. However, if the node has no out edge then we will
752 not set dfs_nr for that node. This can confuse the scheduler
753 into thinking that we have unreachable blocks, which in turn
754 disables cross block scheduling.
756 So, if we have a node with no out edges, go ahead and mark it
757 as reachable now. */
758 if (current_edge == 0)
759 dfs_nr[child] = ++count;
762 /* Another check for unreachable blocks. The earlier test in
763 is_cfg_nonregular only finds unreachable blocks that do not
764 form a loop.
766 The DFS traversal will mark every block that is reachable from
767 the entry node by placing a nonzero value in dfs_nr. Thus if
768 dfs_nr is zero for any block, then it must be unreachable. */
769 unreachable = 0;
770 for (i = 0; i < n_basic_blocks; i++)
771 if (dfs_nr[i] == 0)
773 unreachable = 1;
774 break;
777 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
778 to hold degree counts. */
779 degree = dfs_nr;
781 for (i = 0; i < n_basic_blocks; i++)
782 degree[i] = 0;
783 for (i = 0; i < num_edges; i++)
785 edge e = INDEX_EDGE (edge_list, i);
787 if (e->dest != EXIT_BLOCK_PTR)
788 degree[e->dest->index]++;
791 /* Do not perform region scheduling if there are any unreachable
792 blocks. */
793 if (!unreachable)
795 int *queue;
797 if (no_loops)
798 SET_BIT (header, 0);
800 /* Second travsersal:find reducible inner loops and topologically sort
801 block of each region. */
803 queue = (int *) xmalloc (n_basic_blocks * sizeof (int));
805 /* Find blocks which are inner loop headers. We still have non-reducible
806 loops to consider at this point. */
807 for (i = 0; i < n_basic_blocks; i++)
809 if (TEST_BIT (header, i) && TEST_BIT (inner, i))
811 edge e;
812 int j;
814 /* Now check that the loop is reducible. We do this separate
815 from finding inner loops so that we do not find a reducible
816 loop which contains an inner non-reducible loop.
818 A simple way to find reducible/natural loops is to verify
819 that each block in the loop is dominated by the loop
820 header.
822 If there exists a block that is not dominated by the loop
823 header, then the block is reachable from outside the loop
824 and thus the loop is not a natural loop. */
825 for (j = 0; j < n_basic_blocks; j++)
827 /* First identify blocks in the loop, except for the loop
828 entry block. */
829 if (i == max_hdr[j] && i != j)
831 /* Now verify that the block is dominated by the loop
832 header. */
833 if (!TEST_BIT (dom[j], i))
834 break;
838 /* If we exited the loop early, then I is the header of
839 a non-reducible loop and we should quit processing it
840 now. */
841 if (j != n_basic_blocks)
842 continue;
844 /* I is a header of an inner loop, or block 0 in a subroutine
845 with no loops at all. */
846 head = tail = -1;
847 too_large_failure = 0;
848 loop_head = max_hdr[i];
850 /* Decrease degree of all I's successors for topological
851 ordering. */
852 for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
853 if (e->dest != EXIT_BLOCK_PTR)
854 --degree[e->dest->index];
856 /* Estimate # insns, and count # blocks in the region. */
857 num_bbs = 1;
858 num_insns = (INSN_LUID (BLOCK_END (i))
859 - INSN_LUID (BLOCK_HEAD (i)));
861 /* Find all loop latches (blocks with back edges to the loop
862 header) or all the leaf blocks in the cfg has no loops.
864 Place those blocks into the queue. */
865 if (no_loops)
867 for (j = 0; j < n_basic_blocks; j++)
868 /* Leaf nodes have only a single successor which must
869 be EXIT_BLOCK. */
870 if (BASIC_BLOCK (j)->succ
871 && BASIC_BLOCK (j)->succ->dest == EXIT_BLOCK_PTR
872 && BASIC_BLOCK (j)->succ->succ_next == NULL)
874 queue[++tail] = j;
875 SET_BIT (in_queue, j);
877 if (too_large (j, &num_bbs, &num_insns))
879 too_large_failure = 1;
880 break;
884 else
886 edge e;
888 for (e = BASIC_BLOCK (i)->pred; e; e = e->pred_next)
890 if (e->src == ENTRY_BLOCK_PTR)
891 continue;
893 node = e->src->index;
895 if (max_hdr[node] == loop_head && node != i)
897 /* This is a loop latch. */
898 queue[++tail] = node;
899 SET_BIT (in_queue, node);
901 if (too_large (node, &num_bbs, &num_insns))
903 too_large_failure = 1;
904 break;
910 /* Now add all the blocks in the loop to the queue.
912 We know the loop is a natural loop; however the algorithm
913 above will not always mark certain blocks as being in the
914 loop. Consider:
915 node children
916 a b,c
918 c a,d
921 The algorithm in the DFS traversal may not mark B & D as part
922 of the loop (ie they will not have max_hdr set to A).
924 We know they can not be loop latches (else they would have
925 had max_hdr set since they'd have a backedge to a dominator
926 block). So we don't need them on the initial queue.
928 We know they are part of the loop because they are dominated
929 by the loop header and can be reached by a backwards walk of
930 the edges starting with nodes on the initial queue.
932 It is safe and desirable to include those nodes in the
933 loop/scheduling region. To do so we would need to decrease
934 the degree of a node if it is the target of a backedge
935 within the loop itself as the node is placed in the queue.
937 We do not do this because I'm not sure that the actual
938 scheduling code will properly handle this case. ?!? */
940 while (head < tail && !too_large_failure)
942 edge e;
943 child = queue[++head];
945 for (e = BASIC_BLOCK (child)->pred; e; e = e->pred_next)
947 node = e->src->index;
949 /* See discussion above about nodes not marked as in
950 this loop during the initial DFS traversal. */
951 if (e->src == ENTRY_BLOCK_PTR
952 || max_hdr[node] != loop_head)
954 tail = -1;
955 break;
957 else if (!TEST_BIT (in_queue, node) && node != i)
959 queue[++tail] = node;
960 SET_BIT (in_queue, node);
962 if (too_large (node, &num_bbs, &num_insns))
964 too_large_failure = 1;
965 break;
971 if (tail >= 0 && !too_large_failure)
973 /* Place the loop header into list of region blocks. */
974 degree[i] = -1;
975 rgn_bb_table[idx] = i;
976 RGN_NR_BLOCKS (nr_regions) = num_bbs;
977 RGN_BLOCKS (nr_regions) = idx++;
978 CONTAINING_RGN (i) = nr_regions;
979 BLOCK_TO_BB (i) = count = 0;
981 /* Remove blocks from queue[] when their in degree
982 becomes zero. Repeat until no blocks are left on the
983 list. This produces a topological list of blocks in
984 the region. */
985 while (tail >= 0)
987 if (head < 0)
988 head = tail;
989 child = queue[head];
990 if (degree[child] == 0)
992 edge e;
994 degree[child] = -1;
995 rgn_bb_table[idx++] = child;
996 BLOCK_TO_BB (child) = ++count;
997 CONTAINING_RGN (child) = nr_regions;
998 queue[head] = queue[tail--];
1000 for (e = BASIC_BLOCK (child)->succ;
1002 e = e->succ_next)
1003 if (e->dest != EXIT_BLOCK_PTR)
1004 --degree[e->dest->index];
1006 else
1007 --head;
1009 ++nr_regions;
1013 free (queue);
1016 /* Any block that did not end up in a region is placed into a region
1017 by itself. */
1018 for (i = 0; i < n_basic_blocks; i++)
1019 if (degree[i] >= 0)
1021 rgn_bb_table[idx] = i;
1022 RGN_NR_BLOCKS (nr_regions) = 1;
1023 RGN_BLOCKS (nr_regions) = idx++;
1024 CONTAINING_RGN (i) = nr_regions++;
1025 BLOCK_TO_BB (i) = 0;
1028 free (max_hdr);
1029 free (dfs_nr);
1030 free (stack);
1031 free (passed);
1032 free (header);
1033 free (inner);
1034 free (in_queue);
1035 free (in_stack);
1038 /* Functions for regions scheduling information. */
1040 /* Compute dominators, probability, and potential-split-edges of bb.
1041 Assume that these values were already computed for bb's predecessors. */
1043 static void
1044 compute_dom_prob_ps (bb)
1045 int bb;
1047 int nxt_in_edge, fst_in_edge, pred;
1048 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1050 prob[bb] = 0.0;
1051 if (IS_RGN_ENTRY (bb))
1053 SET_BIT (dom[bb], 0);
1054 prob[bb] = 1.0;
1055 return;
1058 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1060 /* Initialize dom[bb] to '111..1'. */
1061 sbitmap_ones (dom[bb]);
1065 pred = FROM_BLOCK (nxt_in_edge);
1066 sbitmap_a_and_b (dom[bb], dom[bb], dom[BLOCK_TO_BB (pred)]);
1067 sbitmap_a_or_b (ancestor_edges[bb], ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)]);
1069 SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge));
1071 nr_out_edges = 1;
1072 nr_rgn_out_edges = 0;
1073 fst_out_edge = OUT_EDGES (pred);
1074 nxt_out_edge = NEXT_OUT (fst_out_edge);
1076 sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[BLOCK_TO_BB (pred)]);
1078 SET_BIT (pot_split[bb], EDGE_TO_BIT (fst_out_edge));
1080 /* The successor doesn't belong in the region? */
1081 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1082 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1083 ++nr_rgn_out_edges;
1085 while (fst_out_edge != nxt_out_edge)
1087 ++nr_out_edges;
1088 /* The successor doesn't belong in the region? */
1089 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1090 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1091 ++nr_rgn_out_edges;
1092 SET_BIT (pot_split[bb], EDGE_TO_BIT (nxt_out_edge));
1093 nxt_out_edge = NEXT_OUT (nxt_out_edge);
1097 /* Now nr_rgn_out_edges is the number of region-exit edges from
1098 pred, and nr_out_edges will be the number of pred out edges
1099 not leaving the region. */
1100 nr_out_edges -= nr_rgn_out_edges;
1101 if (nr_rgn_out_edges > 0)
1102 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1103 else
1104 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1105 nxt_in_edge = NEXT_IN (nxt_in_edge);
1107 while (fst_in_edge != nxt_in_edge);
1109 SET_BIT (dom[bb], bb);
1110 sbitmap_difference (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
1112 if (sched_verbose >= 2)
1113 fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
1114 (int) (100.0 * prob[bb]));
1117 /* Functions for target info. */
1119 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1120 Note that bb_trg dominates bb_src. */
1122 static void
1123 split_edges (bb_src, bb_trg, bl)
1124 int bb_src;
1125 int bb_trg;
1126 edgelst *bl;
1128 sbitmap src = (edgeset) sbitmap_alloc (pot_split[bb_src]->n_bits);
1129 sbitmap_copy (src, pot_split[bb_src]);
1131 sbitmap_difference (src, src, pot_split[bb_trg]);
1132 extract_bitlst (src, bl);
1133 sbitmap_free (src);
1136 /* Find the valid candidate-source-blocks for the target block TRG, compute
1137 their probability, and check if they are speculative or not.
1138 For speculative sources, compute their update-blocks and split-blocks. */
1140 static void
1141 compute_trg_info (trg)
1142 int trg;
1144 candidate *sp;
1145 edgelst el;
1146 int check_block, update_idx;
1147 int i, j, k, fst_edge, nxt_edge;
1149 /* Define some of the fields for the target bb as well. */
1150 sp = candidate_table + trg;
1151 sp->is_valid = 1;
1152 sp->is_speculative = 0;
1153 sp->src_prob = 100;
1155 for (i = trg + 1; i < current_nr_blocks; i++)
1157 sp = candidate_table + i;
1159 sp->is_valid = IS_DOMINATED (i, trg);
1160 if (sp->is_valid)
1162 sp->src_prob = GET_SRC_PROB (i, trg);
1163 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
1166 if (sp->is_valid)
1168 split_edges (i, trg, &el);
1169 sp->is_speculative = (el.nr_members) ? 1 : 0;
1170 if (sp->is_speculative && !flag_schedule_speculative)
1171 sp->is_valid = 0;
1174 if (sp->is_valid)
1176 char *update_blocks;
1178 /* Compute split blocks and store them in bblst_table.
1179 The TO block of every split edge is a split block. */
1180 sp->split_bbs.first_member = &bblst_table[bblst_last];
1181 sp->split_bbs.nr_members = el.nr_members;
1182 for (j = 0; j < el.nr_members; bblst_last++, j++)
1183 bblst_table[bblst_last] =
1184 TO_BLOCK (rgn_edges[el.first_member[j]]);
1185 sp->update_bbs.first_member = &bblst_table[bblst_last];
1187 /* Compute update blocks and store them in bblst_table.
1188 For every split edge, look at the FROM block, and check
1189 all out edges. For each out edge that is not a split edge,
1190 add the TO block to the update block list. This list can end
1191 up with a lot of duplicates. We need to weed them out to avoid
1192 overrunning the end of the bblst_table. */
1193 update_blocks = (char *) alloca (n_basic_blocks);
1194 memset (update_blocks, 0, n_basic_blocks);
1196 update_idx = 0;
1197 for (j = 0; j < el.nr_members; j++)
1199 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
1200 fst_edge = nxt_edge = OUT_EDGES (check_block);
1203 if (! update_blocks[TO_BLOCK (nxt_edge)])
1205 for (k = 0; k < el.nr_members; k++)
1206 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
1207 break;
1209 if (k >= el.nr_members)
1211 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
1212 update_blocks[TO_BLOCK (nxt_edge)] = 1;
1213 update_idx++;
1217 nxt_edge = NEXT_OUT (nxt_edge);
1219 while (fst_edge != nxt_edge);
1221 sp->update_bbs.nr_members = update_idx;
1223 /* Make sure we didn't overrun the end of bblst_table. */
1224 if (bblst_last > bblst_size)
1225 abort ();
1227 else
1229 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1231 sp->is_speculative = 0;
1232 sp->src_prob = 0;
1237 /* Print candidates info, for debugging purposes. Callable from debugger. */
1239 void
1240 debug_candidate (i)
1241 int i;
1243 if (!candidate_table[i].is_valid)
1244 return;
1246 if (candidate_table[i].is_speculative)
1248 int j;
1249 fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1251 fprintf (sched_dump, "split path: ");
1252 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1254 int b = candidate_table[i].split_bbs.first_member[j];
1256 fprintf (sched_dump, " %d ", b);
1258 fprintf (sched_dump, "\n");
1260 fprintf (sched_dump, "update path: ");
1261 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
1263 int b = candidate_table[i].update_bbs.first_member[j];
1265 fprintf (sched_dump, " %d ", b);
1267 fprintf (sched_dump, "\n");
1269 else
1271 fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
1275 /* Print candidates info, for debugging purposes. Callable from debugger. */
1277 void
1278 debug_candidates (trg)
1279 int trg;
1281 int i;
1283 fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
1284 BB_TO_BLOCK (trg), trg);
1285 for (i = trg + 1; i < current_nr_blocks; i++)
1286 debug_candidate (i);
1289 /* Functions for speculative scheduing. */
1291 /* Return 0 if x is a set of a register alive in the beginning of one
1292 of the split-blocks of src, otherwise return 1. */
1294 static int
1295 check_live_1 (src, x)
1296 int src;
1297 rtx x;
1299 int i;
1300 int regno;
1301 rtx reg = SET_DEST (x);
1303 if (reg == 0)
1304 return 1;
1306 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
1307 || GET_CODE (reg) == SIGN_EXTRACT
1308 || GET_CODE (reg) == STRICT_LOW_PART)
1309 reg = XEXP (reg, 0);
1311 if (GET_CODE (reg) == PARALLEL)
1313 int i;
1315 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1316 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1317 if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
1318 return 1;
1320 return 0;
1323 if (GET_CODE (reg) != REG)
1324 return 1;
1326 regno = REGNO (reg);
1328 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1330 /* Global registers are assumed live. */
1331 return 0;
1333 else
1335 if (regno < FIRST_PSEUDO_REGISTER)
1337 /* Check for hard registers. */
1338 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1339 while (--j >= 0)
1341 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1343 int b = candidate_table[src].split_bbs.first_member[i];
1345 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
1346 regno + j))
1348 return 0;
1353 else
1355 /* Check for psuedo registers. */
1356 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1358 int b = candidate_table[src].split_bbs.first_member[i];
1360 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
1362 return 0;
1368 return 1;
1371 /* If x is a set of a register R, mark that R is alive in the beginning
1372 of every update-block of src. */
1374 static void
1375 update_live_1 (src, x)
1376 int src;
1377 rtx x;
1379 int i;
1380 int regno;
1381 rtx reg = SET_DEST (x);
1383 if (reg == 0)
1384 return;
1386 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
1387 || GET_CODE (reg) == SIGN_EXTRACT
1388 || GET_CODE (reg) == STRICT_LOW_PART)
1389 reg = XEXP (reg, 0);
1391 if (GET_CODE (reg) == PARALLEL)
1393 int i;
1395 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1396 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1397 update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
1399 return;
1402 if (GET_CODE (reg) != REG)
1403 return;
1405 /* Global registers are always live, so the code below does not apply
1406 to them. */
1408 regno = REGNO (reg);
1410 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
1412 if (regno < FIRST_PSEUDO_REGISTER)
1414 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1415 while (--j >= 0)
1417 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1419 int b = candidate_table[src].update_bbs.first_member[i];
1421 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
1422 regno + j);
1426 else
1428 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1430 int b = candidate_table[src].update_bbs.first_member[i];
1432 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
1438 /* Return 1 if insn can be speculatively moved from block src to trg,
1439 otherwise return 0. Called before first insertion of insn to
1440 ready-list or before the scheduling. */
1442 static int
1443 check_live (insn, src)
1444 rtx insn;
1445 int src;
1447 /* Find the registers set by instruction. */
1448 if (GET_CODE (PATTERN (insn)) == SET
1449 || GET_CODE (PATTERN (insn)) == CLOBBER)
1450 return check_live_1 (src, PATTERN (insn));
1451 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1453 int j;
1454 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1455 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1456 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1457 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
1458 return 0;
1460 return 1;
1463 return 1;
1466 /* Update the live registers info after insn was moved speculatively from
1467 block src to trg. */
1469 static void
1470 update_live (insn, src)
1471 rtx insn;
1472 int src;
1474 /* Find the registers set by instruction. */
1475 if (GET_CODE (PATTERN (insn)) == SET
1476 || GET_CODE (PATTERN (insn)) == CLOBBER)
1477 update_live_1 (src, PATTERN (insn));
1478 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1480 int j;
1481 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1482 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1483 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1484 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
1488 /* Exception Free Loads:
1490 We define five classes of speculative loads: IFREE, IRISKY,
1491 PFREE, PRISKY, and MFREE.
1493 IFREE loads are loads that are proved to be exception-free, just
1494 by examining the load insn. Examples for such loads are loads
1495 from TOC and loads of global data.
1497 IRISKY loads are loads that are proved to be exception-risky,
1498 just by examining the load insn. Examples for such loads are
1499 volatile loads and loads from shared memory.
1501 PFREE loads are loads for which we can prove, by examining other
1502 insns, that they are exception-free. Currently, this class consists
1503 of loads for which we are able to find a "similar load", either in
1504 the target block, or, if only one split-block exists, in that split
1505 block. Load2 is similar to load1 if both have same single base
1506 register. We identify only part of the similar loads, by finding
1507 an insn upon which both load1 and load2 have a DEF-USE dependence.
1509 PRISKY loads are loads for which we can prove, by examining other
1510 insns, that they are exception-risky. Currently we have two proofs for
1511 such loads. The first proof detects loads that are probably guarded by a
1512 test on the memory address. This proof is based on the
1513 backward and forward data dependence information for the region.
1514 Let load-insn be the examined load.
1515 Load-insn is PRISKY iff ALL the following hold:
1517 - insn1 is not in the same block as load-insn
1518 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
1519 - test-insn is either a compare or a branch, not in the same block
1520 as load-insn
1521 - load-insn is reachable from test-insn
1522 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
1524 This proof might fail when the compare and the load are fed
1525 by an insn not in the region. To solve this, we will add to this
1526 group all loads that have no input DEF-USE dependence.
1528 The second proof detects loads that are directly or indirectly
1529 fed by a speculative load. This proof is affected by the
1530 scheduling process. We will use the flag fed_by_spec_load.
1531 Initially, all insns have this flag reset. After a speculative
1532 motion of an insn, if insn is either a load, or marked as
1533 fed_by_spec_load, we will also mark as fed_by_spec_load every
1534 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
1535 load which is fed_by_spec_load is also PRISKY.
1537 MFREE (maybe-free) loads are all the remaining loads. They may be
1538 exception-free, but we cannot prove it.
1540 Now, all loads in IFREE and PFREE classes are considered
1541 exception-free, while all loads in IRISKY and PRISKY classes are
1542 considered exception-risky. As for loads in the MFREE class,
1543 these are considered either exception-free or exception-risky,
1544 depending on whether we are pessimistic or optimistic. We have
1545 to take the pessimistic approach to assure the safety of
1546 speculative scheduling, but we can take the optimistic approach
1547 by invoking the -fsched_spec_load_dangerous option. */
1549 enum INSN_TRAP_CLASS
1551 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
1552 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
1555 #define WORST_CLASS(class1, class2) \
1556 ((class1 > class2) ? class1 : class2)
1558 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
1559 #define IS_REACHABLE(bb_from, bb_to) \
1560 (bb_from == bb_to \
1561 || IS_RGN_ENTRY (bb_from) \
1562 || (TEST_BIT (ancestor_edges[bb_to], \
1563 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))))))
1565 /* Non-zero iff the address is comprised from at most 1 register. */
1566 #define CONST_BASED_ADDRESS_P(x) \
1567 (GET_CODE (x) == REG \
1568 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
1569 || (GET_CODE (x) == LO_SUM)) \
1570 && (CONSTANT_P (XEXP (x, 0)) \
1571 || CONSTANT_P (XEXP (x, 1)))))
1573 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1575 static void
1576 set_spec_fed (load_insn)
1577 rtx load_insn;
1579 rtx link;
1581 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
1582 if (GET_MODE (link) == VOIDmode)
1583 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
1584 } /* set_spec_fed */
1586 /* On the path from the insn to load_insn_bb, find a conditional
1587 branch depending on insn, that guards the speculative load. */
1589 static int
1590 find_conditional_protection (insn, load_insn_bb)
1591 rtx insn;
1592 int load_insn_bb;
1594 rtx link;
1596 /* Iterate through DEF-USE forward dependences. */
1597 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
1599 rtx next = XEXP (link, 0);
1600 if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
1601 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
1602 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
1603 && load_insn_bb != INSN_BB (next)
1604 && GET_MODE (link) == VOIDmode
1605 && (GET_CODE (next) == JUMP_INSN
1606 || find_conditional_protection (next, load_insn_bb)))
1607 return 1;
1609 return 0;
1610 } /* find_conditional_protection */
1612 /* Returns 1 if the same insn1 that participates in the computation
1613 of load_insn's address is feeding a conditional branch that is
1614 guarding on load_insn. This is true if we find a the two DEF-USE
1615 chains:
1616 insn1 -> ... -> conditional-branch
1617 insn1 -> ... -> load_insn,
1618 and if a flow path exist:
1619 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1620 and if insn1 is on the path
1621 region-entry -> ... -> bb_trg -> ... load_insn.
1623 Locate insn1 by climbing on LOG_LINKS from load_insn.
1624 Locate the branch by following INSN_DEPEND from insn1. */
1626 static int
1627 is_conditionally_protected (load_insn, bb_src, bb_trg)
1628 rtx load_insn;
1629 int bb_src, bb_trg;
1631 rtx link;
1633 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
1635 rtx insn1 = XEXP (link, 0);
1637 /* Must be a DEF-USE dependence upon non-branch. */
1638 if (GET_MODE (link) != VOIDmode
1639 || GET_CODE (insn1) == JUMP_INSN)
1640 continue;
1642 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1643 if (INSN_BB (insn1) == bb_src
1644 || (CONTAINING_RGN (BLOCK_NUM (insn1))
1645 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
1646 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
1647 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
1648 continue;
1650 /* Now search for the conditional-branch. */
1651 if (find_conditional_protection (insn1, bb_src))
1652 return 1;
1654 /* Recursive step: search another insn1, "above" current insn1. */
1655 return is_conditionally_protected (insn1, bb_src, bb_trg);
1658 /* The chain does not exist. */
1659 return 0;
1660 } /* is_conditionally_protected */
1662 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1663 load_insn can move speculatively from bb_src to bb_trg. All the
1664 following must hold:
1666 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1667 (2) load_insn and load1 have a def-use dependence upon
1668 the same insn 'insn1'.
1669 (3) either load2 is in bb_trg, or:
1670 - there's only one split-block, and
1671 - load1 is on the escape path, and
1673 From all these we can conclude that the two loads access memory
1674 addresses that differ at most by a constant, and hence if moving
1675 load_insn would cause an exception, it would have been caused by
1676 load2 anyhow. */
1678 static int
1679 is_pfree (load_insn, bb_src, bb_trg)
1680 rtx load_insn;
1681 int bb_src, bb_trg;
1683 rtx back_link;
1684 candidate *candp = candidate_table + bb_src;
1686 if (candp->split_bbs.nr_members != 1)
1687 /* Must have exactly one escape block. */
1688 return 0;
1690 for (back_link = LOG_LINKS (load_insn);
1691 back_link; back_link = XEXP (back_link, 1))
1693 rtx insn1 = XEXP (back_link, 0);
1695 if (GET_MODE (back_link) == VOIDmode)
1697 /* Found a DEF-USE dependence (insn1, load_insn). */
1698 rtx fore_link;
1700 for (fore_link = INSN_DEPEND (insn1);
1701 fore_link; fore_link = XEXP (fore_link, 1))
1703 rtx insn2 = XEXP (fore_link, 0);
1704 if (GET_MODE (fore_link) == VOIDmode)
1706 /* Found a DEF-USE dependence (insn1, insn2). */
1707 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
1708 /* insn2 not guaranteed to be a 1 base reg load. */
1709 continue;
1711 if (INSN_BB (insn2) == bb_trg)
1712 /* insn2 is the similar load, in the target block. */
1713 return 1;
1715 if (*(candp->split_bbs.first_member) == BLOCK_NUM (insn2))
1716 /* insn2 is a similar load, in a split-block. */
1717 return 1;
1723 /* Couldn't find a similar load. */
1724 return 0;
1725 } /* is_pfree */
1727 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
1728 as found by analyzing insn's expression. */
1730 static int
1731 may_trap_exp (x, is_store)
1732 rtx x;
1733 int is_store;
1735 enum rtx_code code;
1737 if (x == 0)
1738 return TRAP_FREE;
1739 code = GET_CODE (x);
1740 if (is_store)
1742 if (code == MEM && may_trap_p (x))
1743 return TRAP_RISKY;
1744 else
1745 return TRAP_FREE;
1747 if (code == MEM)
1749 /* The insn uses memory: a volatile load. */
1750 if (MEM_VOLATILE_P (x))
1751 return IRISKY;
1752 /* An exception-free load. */
1753 if (!may_trap_p (x))
1754 return IFREE;
1755 /* A load with 1 base register, to be further checked. */
1756 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
1757 return PFREE_CANDIDATE;
1758 /* No info on the load, to be further checked. */
1759 return PRISKY_CANDIDATE;
1761 else
1763 const char *fmt;
1764 int i, insn_class = TRAP_FREE;
1766 /* Neither store nor load, check if it may cause a trap. */
1767 if (may_trap_p (x))
1768 return TRAP_RISKY;
1769 /* Recursive step: walk the insn... */
1770 fmt = GET_RTX_FORMAT (code);
1771 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1773 if (fmt[i] == 'e')
1775 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
1776 insn_class = WORST_CLASS (insn_class, tmp_class);
1778 else if (fmt[i] == 'E')
1780 int j;
1781 for (j = 0; j < XVECLEN (x, i); j++)
1783 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
1784 insn_class = WORST_CLASS (insn_class, tmp_class);
1785 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
1786 break;
1789 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
1790 break;
1792 return insn_class;
1796 /* Classifies insn for the purpose of verifying that it can be
1797 moved speculatively, by examining it's patterns, returning:
1798 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
1799 TRAP_FREE: non-load insn.
1800 IFREE: load from a globaly safe location.
1801 IRISKY: volatile load.
1802 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
1803 being either PFREE or PRISKY. */
1805 static int
1806 haifa_classify_insn (insn)
1807 rtx insn;
1809 rtx pat = PATTERN (insn);
1810 int tmp_class = TRAP_FREE;
1811 int insn_class = TRAP_FREE;
1812 enum rtx_code code;
1814 if (GET_CODE (pat) == PARALLEL)
1816 int i, len = XVECLEN (pat, 0);
1818 for (i = len - 1; i >= 0; i--)
1820 code = GET_CODE (XVECEXP (pat, 0, i));
1821 switch (code)
1823 case CLOBBER:
1824 /* Test if it is a 'store'. */
1825 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
1826 break;
1827 case SET:
1828 /* Test if it is a store. */
1829 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
1830 if (tmp_class == TRAP_RISKY)
1831 break;
1832 /* Test if it is a load. */
1833 tmp_class
1834 = WORST_CLASS (tmp_class,
1835 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)),
1836 0));
1837 break;
1838 case COND_EXEC:
1839 case TRAP_IF:
1840 tmp_class = TRAP_RISKY;
1841 break;
1842 default:
1845 insn_class = WORST_CLASS (insn_class, tmp_class);
1846 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
1847 break;
1850 else
1852 code = GET_CODE (pat);
1853 switch (code)
1855 case CLOBBER:
1856 /* Test if it is a 'store'. */
1857 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
1858 break;
1859 case SET:
1860 /* Test if it is a store. */
1861 tmp_class = may_trap_exp (SET_DEST (pat), 1);
1862 if (tmp_class == TRAP_RISKY)
1863 break;
1864 /* Test if it is a load. */
1865 tmp_class =
1866 WORST_CLASS (tmp_class,
1867 may_trap_exp (SET_SRC (pat), 0));
1868 break;
1869 case COND_EXEC:
1870 case TRAP_IF:
1871 tmp_class = TRAP_RISKY;
1872 break;
1873 default:;
1875 insn_class = tmp_class;
1878 return insn_class;
1881 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1882 a load moved speculatively, or if load_insn is protected by
1883 a compare on load_insn's address). */
1885 static int
1886 is_prisky (load_insn, bb_src, bb_trg)
1887 rtx load_insn;
1888 int bb_src, bb_trg;
1890 if (FED_BY_SPEC_LOAD (load_insn))
1891 return 1;
1893 if (LOG_LINKS (load_insn) == NULL)
1894 /* Dependence may 'hide' out of the region. */
1895 return 1;
1897 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
1898 return 1;
1900 return 0;
1903 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
1904 Return 1 if insn is exception-free (and the motion is valid)
1905 and 0 otherwise. */
1907 static int
1908 is_exception_free (insn, bb_src, bb_trg)
1909 rtx insn;
1910 int bb_src, bb_trg;
1912 int insn_class = haifa_classify_insn (insn);
1914 /* Handle non-load insns. */
1915 switch (insn_class)
1917 case TRAP_FREE:
1918 return 1;
1919 case TRAP_RISKY:
1920 return 0;
1921 default:;
1924 /* Handle loads. */
1925 if (!flag_schedule_speculative_load)
1926 return 0;
1927 IS_LOAD_INSN (insn) = 1;
1928 switch (insn_class)
1930 case IFREE:
1931 return (1);
1932 case IRISKY:
1933 return 0;
1934 case PFREE_CANDIDATE:
1935 if (is_pfree (insn, bb_src, bb_trg))
1936 return 1;
1937 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
1938 case PRISKY_CANDIDATE:
1939 if (!flag_schedule_speculative_load_dangerous
1940 || is_prisky (insn, bb_src, bb_trg))
1941 return 0;
1942 break;
1943 default:;
1946 return flag_schedule_speculative_load_dangerous;
1949 /* The number of insns from the current block scheduled so far. */
1950 static int sched_target_n_insns;
1951 /* The number of insns from the current block to be scheduled in total. */
1952 static int target_n_insns;
1953 /* The number of insns from the entire region scheduled so far. */
1954 static int sched_n_insns;
1955 /* Nonzero if the last scheduled insn was a jump. */
1956 static int last_was_jump;
1958 /* Implementations of the sched_info functions for region scheduling. */
1959 static void init_ready_list PARAMS ((struct ready_list *));
1960 static int can_schedule_ready_p PARAMS ((rtx));
1961 static int new_ready PARAMS ((rtx));
1962 static int schedule_more_p PARAMS ((void));
1963 static const char *rgn_print_insn PARAMS ((rtx, int));
1964 static int rgn_rank PARAMS ((rtx, rtx));
1965 static int contributes_to_priority PARAMS ((rtx, rtx));
1966 static void compute_jump_reg_dependencies PARAMS ((rtx, regset));
1968 /* Return nonzero if there are more insns that should be scheduled. */
1970 static int
1971 schedule_more_p ()
1973 return ! last_was_jump && sched_target_n_insns < target_n_insns;
1976 /* Add all insns that are initially ready to the ready list READY. Called
1977 once before scheduling a set of insns. */
1979 static void
1980 init_ready_list (ready)
1981 struct ready_list *ready;
1983 rtx prev_head = current_sched_info->prev_head;
1984 rtx next_tail = current_sched_info->next_tail;
1985 int bb_src;
1986 rtx insn;
1988 target_n_insns = 0;
1989 sched_target_n_insns = 0;
1990 sched_n_insns = 0;
1991 last_was_jump = 0;
1993 /* Print debugging information. */
1994 if (sched_verbose >= 5)
1995 debug_dependencies ();
1997 /* Prepare current target block info. */
1998 if (current_nr_blocks > 1)
2000 candidate_table = (candidate *) xmalloc (current_nr_blocks
2001 * sizeof (candidate));
2003 bblst_last = 0;
2004 /* bblst_table holds split blocks and update blocks for each block after
2005 the current one in the region. split blocks and update blocks are
2006 the TO blocks of region edges, so there can be at most rgn_nr_edges
2007 of them. */
2008 bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
2009 bblst_table = (int *) xmalloc (bblst_size * sizeof (int));
2011 bitlst_table_last = 0;
2012 bitlst_table_size = rgn_nr_edges;
2013 bitlst_table = (int *) xmalloc (rgn_nr_edges * sizeof (int));
2015 compute_trg_info (target_bb);
2018 /* Initialize ready list with all 'ready' insns in target block.
2019 Count number of insns in the target block being scheduled. */
2020 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
2022 rtx next;
2024 if (! INSN_P (insn))
2025 continue;
2026 next = NEXT_INSN (insn);
2028 if (INSN_DEP_COUNT (insn) == 0
2029 && (SCHED_GROUP_P (next) == 0 || ! INSN_P (next)))
2030 ready_add (ready, insn);
2031 if (!(SCHED_GROUP_P (insn)))
2032 target_n_insns++;
2035 /* Add to ready list all 'ready' insns in valid source blocks.
2036 For speculative insns, check-live, exception-free, and
2037 issue-delay. */
2038 for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
2039 if (IS_VALID (bb_src))
2041 rtx src_head;
2042 rtx src_next_tail;
2043 rtx tail, head;
2045 get_block_head_tail (BB_TO_BLOCK (bb_src), &head, &tail);
2046 src_next_tail = NEXT_INSN (tail);
2047 src_head = head;
2049 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
2051 if (! INSN_P (insn))
2052 continue;
2054 if (!CANT_MOVE (insn)
2055 && (!IS_SPECULATIVE_INSN (insn)
2056 || (insn_issue_delay (insn) <= 3
2057 && check_live (insn, bb_src)
2058 && is_exception_free (insn, bb_src, target_bb))))
2060 rtx next;
2062 /* Note that we haven't squirreled away the notes for
2063 blocks other than the current. So if this is a
2064 speculative insn, NEXT might otherwise be a note. */
2065 next = next_nonnote_insn (insn);
2066 if (INSN_DEP_COUNT (insn) == 0
2067 && (! next
2068 || SCHED_GROUP_P (next) == 0
2069 || ! INSN_P (next)))
2070 ready_add (ready, insn);
2076 /* Called after taking INSN from the ready list. Returns nonzero if this
2077 insn can be scheduled, nonzero if we should silently discard it. */
2079 static int
2080 can_schedule_ready_p (insn)
2081 rtx insn;
2083 if (GET_CODE (insn) == JUMP_INSN)
2084 last_was_jump = 1;
2086 /* An interblock motion? */
2087 if (INSN_BB (insn) != target_bb)
2089 rtx temp;
2090 basic_block b1;
2092 if (IS_SPECULATIVE_INSN (insn))
2094 if (!check_live (insn, INSN_BB (insn)))
2095 return 0;
2096 update_live (insn, INSN_BB (insn));
2098 /* For speculative load, mark insns fed by it. */
2099 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
2100 set_spec_fed (insn);
2102 nr_spec++;
2104 nr_inter++;
2106 /* Find the beginning of the scheduling group. */
2107 /* ??? Ought to update basic block here, but later bits of
2108 schedule_block assumes the original insn block is
2109 still intact. */
2111 temp = insn;
2112 while (SCHED_GROUP_P (temp))
2113 temp = PREV_INSN (temp);
2115 /* Update source block boundaries. */
2116 b1 = BLOCK_FOR_INSN (temp);
2117 if (temp == b1->head && insn == b1->end)
2119 /* We moved all the insns in the basic block.
2120 Emit a note after the last insn and update the
2121 begin/end boundaries to point to the note. */
2122 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
2123 b1->head = note;
2124 b1->end = note;
2126 else if (insn == b1->end)
2128 /* We took insns from the end of the basic block,
2129 so update the end of block boundary so that it
2130 points to the first insn we did not move. */
2131 b1->end = PREV_INSN (temp);
2133 else if (temp == b1->head)
2135 /* We took insns from the start of the basic block,
2136 so update the start of block boundary so that
2137 it points to the first insn we did not move. */
2138 b1->head = NEXT_INSN (insn);
2141 else
2143 /* In block motion. */
2144 sched_target_n_insns++;
2146 sched_n_insns++;
2148 return 1;
2151 /* Called after INSN has all its dependencies resolved. Return nonzero
2152 if it should be moved to the ready list or the queue, or zero if we
2153 should silently discard it. */
2154 static int
2155 new_ready (next)
2156 rtx next;
2158 /* For speculative insns, before inserting to ready/queue,
2159 check live, exception-free, and issue-delay. */
2160 if (INSN_BB (next) != target_bb
2161 && (!IS_VALID (INSN_BB (next))
2162 || CANT_MOVE (next)
2163 || (IS_SPECULATIVE_INSN (next)
2164 && (insn_issue_delay (next) > 3
2165 || !check_live (next, INSN_BB (next))
2166 || !is_exception_free (next, INSN_BB (next), target_bb)))))
2167 return 0;
2168 return 1;
2171 /* Return a string that contains the insn uid and optionally anything else
2172 necessary to identify this insn in an output. It's valid to use a
2173 static buffer for this. The ALIGNED parameter should cause the string
2174 to be formatted so that multiple output lines will line up nicely. */
2176 static const char *
2177 rgn_print_insn (insn, aligned)
2178 rtx insn;
2179 int aligned;
2181 static char tmp[80];
2183 if (aligned)
2184 sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
2185 else
2187 if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
2188 sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
2189 else
2190 sprintf (tmp, "%d", INSN_UID (insn));
2192 return tmp;
2195 /* Compare priority of two insns. Return a positive number if the second
2196 insn is to be preferred for scheduling, and a negative one if the first
2197 is to be preferred. Zero if they are equally good. */
2199 static int
2200 rgn_rank (insn1, insn2)
2201 rtx insn1, insn2;
2203 /* Some comparison make sense in interblock scheduling only. */
2204 if (INSN_BB (insn1) != INSN_BB (insn2))
2206 int spec_val, prob_val;
2208 /* Prefer an inblock motion on an interblock motion. */
2209 if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
2210 return 1;
2211 if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
2212 return -1;
2214 /* Prefer a useful motion on a speculative one. */
2215 spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
2216 if (spec_val)
2217 return spec_val;
2219 /* Prefer a more probable (speculative) insn. */
2220 prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
2221 if (prob_val)
2222 return prob_val;
2224 return 0;
2227 /* NEXT is an instruction that depends on INSN (a backward dependence);
2228 return nonzero if we should include this dependence in priority
2229 calculations. */
2231 static int
2232 contributes_to_priority (next, insn)
2233 rtx next, insn;
2235 return BLOCK_NUM (next) == BLOCK_NUM (insn);
2238 /* INSN is a JUMP_INSN. Store the set of registers that must be considered
2239 to be set by this jump in SET. */
2241 static void
2242 compute_jump_reg_dependencies (insn, set)
2243 rtx insn ATTRIBUTE_UNUSED;
2244 regset set ATTRIBUTE_UNUSED;
2246 /* Nothing to do here, since we postprocess jumps in
2247 add_branch_dependences. */
2250 /* Used in schedule_insns to initialize current_sched_info for scheduling
2251 regions (or single basic blocks). */
2253 static struct sched_info region_sched_info =
2255 init_ready_list,
2256 can_schedule_ready_p,
2257 schedule_more_p,
2258 new_ready,
2259 rgn_rank,
2260 rgn_print_insn,
2261 contributes_to_priority,
2262 compute_jump_reg_dependencies,
2264 NULL, NULL,
2265 NULL, NULL,
2266 0, 0
2269 /* Add dependences so that branches are scheduled to run last in their
2270 block. */
2272 static void
2273 add_branch_dependences (head, tail)
2274 rtx head, tail;
2276 rtx insn, last;
2278 /* For all branches, calls, uses, clobbers, and cc0 setters, force them
2279 to remain in order at the end of the block by adding dependencies and
2280 giving the last a high priority. There may be notes present, and
2281 prev_head may also be a note.
2283 Branches must obviously remain at the end. Calls should remain at the
2284 end since moving them results in worse register allocation. Uses remain
2285 at the end to ensure proper register allocation. cc0 setters remaim
2286 at the end because they can't be moved away from their cc0 user. */
2287 insn = tail;
2288 last = 0;
2289 while (GET_CODE (insn) == CALL_INSN
2290 || GET_CODE (insn) == JUMP_INSN
2291 || (GET_CODE (insn) == INSN
2292 && (GET_CODE (PATTERN (insn)) == USE
2293 || GET_CODE (PATTERN (insn)) == CLOBBER
2294 #ifdef HAVE_cc0
2295 || sets_cc0_p (PATTERN (insn))
2296 #endif
2298 || GET_CODE (insn) == NOTE)
2300 if (GET_CODE (insn) != NOTE)
2302 if (last != 0
2303 && !find_insn_list (insn, LOG_LINKS (last)))
2305 add_dependence (last, insn, REG_DEP_ANTI);
2306 INSN_REF_COUNT (insn)++;
2309 CANT_MOVE (insn) = 1;
2311 last = insn;
2312 /* Skip over insns that are part of a group.
2313 Make each insn explicitly depend on the previous insn.
2314 This ensures that only the group header will ever enter
2315 the ready queue (and, when scheduled, will automatically
2316 schedule the SCHED_GROUP_P block). */
2317 while (SCHED_GROUP_P (insn))
2319 rtx temp = prev_nonnote_insn (insn);
2320 add_dependence (insn, temp, REG_DEP_ANTI);
2321 insn = temp;
2325 /* Don't overrun the bounds of the basic block. */
2326 if (insn == head)
2327 break;
2329 insn = PREV_INSN (insn);
2332 /* Make sure these insns are scheduled last in their block. */
2333 insn = last;
2334 if (insn != 0)
2335 while (insn != head)
2337 insn = prev_nonnote_insn (insn);
2339 if (INSN_REF_COUNT (insn) != 0)
2340 continue;
2342 add_dependence (last, insn, REG_DEP_ANTI);
2343 INSN_REF_COUNT (insn) = 1;
2345 /* Skip over insns that are part of a group. */
2346 while (SCHED_GROUP_P (insn))
2347 insn = prev_nonnote_insn (insn);
2351 /* Data structures for the computation of data dependences in a regions. We
2352 keep one `deps' structure for every basic block. Before analyzing the
2353 data dependences for a bb, its variables are initialized as a function of
2354 the variables of its predecessors. When the analysis for a bb completes,
2355 we save the contents to the corresponding bb_deps[bb] variable. */
2357 static struct deps *bb_deps;
2359 /* After computing the dependencies for block BB, propagate the dependencies
2360 found in TMP_DEPS to the successors of the block. */
2361 static void
2362 propagate_deps (bb, tmp_deps)
2363 int bb;
2364 struct deps *tmp_deps;
2366 int b = BB_TO_BLOCK (bb);
2367 int e, first_edge;
2368 int reg;
2369 rtx link_insn, link_mem;
2370 rtx u;
2372 /* These lists should point to the right place, for correct
2373 freeing later. */
2374 bb_deps[bb].pending_read_insns = tmp_deps->pending_read_insns;
2375 bb_deps[bb].pending_read_mems = tmp_deps->pending_read_mems;
2376 bb_deps[bb].pending_write_insns = tmp_deps->pending_write_insns;
2377 bb_deps[bb].pending_write_mems = tmp_deps->pending_write_mems;
2379 /* bb's structures are inherited by its successors. */
2380 first_edge = e = OUT_EDGES (b);
2381 if (e <= 0)
2382 return;
2386 rtx x;
2387 int b_succ = TO_BLOCK (e);
2388 int bb_succ = BLOCK_TO_BB (b_succ);
2389 struct deps *succ_deps = bb_deps + bb_succ;
2391 /* Only bbs "below" bb, in the same region, are interesting. */
2392 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
2393 || bb_succ <= bb)
2395 e = NEXT_OUT (e);
2396 continue;
2399 /* The reg_last lists are inherited by bb_succ. */
2400 EXECUTE_IF_SET_IN_REG_SET (&tmp_deps->reg_last_in_use, 0, reg,
2402 struct deps_reg *tmp_deps_reg = &tmp_deps->reg_last[reg];
2403 struct deps_reg *succ_deps_reg = &succ_deps->reg_last[reg];
2405 for (u = tmp_deps_reg->uses; u; u = XEXP (u, 1))
2406 if (! find_insn_list (XEXP (u, 0), succ_deps_reg->uses))
2407 succ_deps_reg->uses
2408 = alloc_INSN_LIST (XEXP (u, 0), succ_deps_reg->uses);
2410 for (u = tmp_deps_reg->sets; u; u = XEXP (u, 1))
2411 if (! find_insn_list (XEXP (u, 0), succ_deps_reg->sets))
2412 succ_deps_reg->sets
2413 = alloc_INSN_LIST (XEXP (u, 0), succ_deps_reg->sets);
2415 for (u = tmp_deps_reg->clobbers; u; u = XEXP (u, 1))
2416 if (! find_insn_list (XEXP (u, 0), succ_deps_reg->clobbers))
2417 succ_deps_reg->clobbers
2418 = alloc_INSN_LIST (XEXP (u, 0), succ_deps_reg->clobbers);
2420 IOR_REG_SET (&succ_deps->reg_last_in_use, &tmp_deps->reg_last_in_use);
2422 /* Mem read/write lists are inherited by bb_succ. */
2423 link_insn = tmp_deps->pending_read_insns;
2424 link_mem = tmp_deps->pending_read_mems;
2425 while (link_insn)
2427 if (!(find_insn_mem_list (XEXP (link_insn, 0),
2428 XEXP (link_mem, 0),
2429 succ_deps->pending_read_insns,
2430 succ_deps->pending_read_mems)))
2431 add_insn_mem_dependence (succ_deps, &succ_deps->pending_read_insns,
2432 &succ_deps->pending_read_mems,
2433 XEXP (link_insn, 0), XEXP (link_mem, 0));
2434 link_insn = XEXP (link_insn, 1);
2435 link_mem = XEXP (link_mem, 1);
2438 link_insn = tmp_deps->pending_write_insns;
2439 link_mem = tmp_deps->pending_write_mems;
2440 while (link_insn)
2442 if (!(find_insn_mem_list (XEXP (link_insn, 0),
2443 XEXP (link_mem, 0),
2444 succ_deps->pending_write_insns,
2445 succ_deps->pending_write_mems)))
2446 add_insn_mem_dependence (succ_deps,
2447 &succ_deps->pending_write_insns,
2448 &succ_deps->pending_write_mems,
2449 XEXP (link_insn, 0), XEXP (link_mem, 0));
2451 link_insn = XEXP (link_insn, 1);
2452 link_mem = XEXP (link_mem, 1);
2455 /* last_function_call is inherited by bb_succ. */
2456 for (u = tmp_deps->last_function_call; u; u = XEXP (u, 1))
2457 if (! find_insn_list (XEXP (u, 0), succ_deps->last_function_call))
2458 succ_deps->last_function_call
2459 = alloc_INSN_LIST (XEXP (u, 0), succ_deps->last_function_call);
2461 /* last_pending_memory_flush is inherited by bb_succ. */
2462 for (u = tmp_deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2463 if (! find_insn_list (XEXP (u, 0),
2464 succ_deps->last_pending_memory_flush))
2465 succ_deps->last_pending_memory_flush
2466 = alloc_INSN_LIST (XEXP (u, 0),
2467 succ_deps->last_pending_memory_flush);
2469 /* sched_before_next_call is inherited by bb_succ. */
2470 x = LOG_LINKS (tmp_deps->sched_before_next_call);
2471 for (; x; x = XEXP (x, 1))
2472 add_dependence (succ_deps->sched_before_next_call,
2473 XEXP (x, 0), REG_DEP_ANTI);
2475 e = NEXT_OUT (e);
2477 while (e != first_edge);
2480 /* Compute backward dependences inside bb. In a multiple blocks region:
2481 (1) a bb is analyzed after its predecessors, and (2) the lists in
2482 effect at the end of bb (after analyzing for bb) are inherited by
2483 bb's successrs.
2485 Specifically for reg-reg data dependences, the block insns are
2486 scanned by sched_analyze () top-to-bottom. Two lists are
2487 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2488 and reg_last[].uses for register USEs.
2490 When analysis is completed for bb, we update for its successors:
2491 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2492 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2494 The mechanism for computing mem-mem data dependence is very
2495 similar, and the result is interblock dependences in the region. */
2497 static void
2498 compute_block_backward_dependences (bb)
2499 int bb;
2501 rtx head, tail;
2502 struct deps tmp_deps;
2504 tmp_deps = bb_deps[bb];
2506 /* Do the analysis for this block. */
2507 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2508 sched_analyze (&tmp_deps, head, tail);
2509 add_branch_dependences (head, tail);
2511 if (current_nr_blocks > 1)
2512 propagate_deps (bb, &tmp_deps);
2514 /* Free up the INSN_LISTs. */
2515 free_deps (&tmp_deps);
2518 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2519 them to the unused_*_list variables, so that they can be reused. */
2521 static void
2522 free_pending_lists ()
2524 int bb;
2526 for (bb = 0; bb < current_nr_blocks; bb++)
2528 free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
2529 free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
2530 free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
2531 free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
2535 /* Print dependences for debugging, callable from debugger. */
2537 void
2538 debug_dependencies ()
2540 int bb;
2542 fprintf (sched_dump, ";; --------------- forward dependences: ------------ \n");
2543 for (bb = 0; bb < current_nr_blocks; bb++)
2545 if (1)
2547 rtx head, tail;
2548 rtx next_tail;
2549 rtx insn;
2551 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2552 next_tail = NEXT_INSN (tail);
2553 fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
2554 BB_TO_BLOCK (bb), bb);
2556 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
2557 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
2558 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
2559 "----", "----", "--", "---", "----", "----", "--------", "-----");
2560 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2562 rtx link;
2563 int unit, range;
2565 if (! INSN_P (insn))
2567 int n;
2568 fprintf (sched_dump, ";; %6d ", INSN_UID (insn));
2569 if (GET_CODE (insn) == NOTE)
2571 n = NOTE_LINE_NUMBER (insn);
2572 if (n < 0)
2573 fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
2574 else
2575 fprintf (sched_dump, "line %d, file %s\n", n,
2576 NOTE_SOURCE_FILE (insn));
2578 else
2579 fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
2580 continue;
2583 unit = insn_unit (insn);
2584 range = (unit < 0
2585 || function_units[unit].blockage_range_function == 0) ? 0 :
2586 function_units[unit].blockage_range_function (insn);
2587 fprintf (sched_dump,
2588 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
2589 (SCHED_GROUP_P (insn) ? "+" : " "),
2590 INSN_UID (insn),
2591 INSN_CODE (insn),
2592 INSN_BB (insn),
2593 INSN_DEP_COUNT (insn),
2594 INSN_PRIORITY (insn),
2595 insn_cost (insn, 0, 0),
2596 (int) MIN_BLOCKAGE_COST (range),
2597 (int) MAX_BLOCKAGE_COST (range));
2598 insn_print_units (insn);
2599 fprintf (sched_dump, "\t: ");
2600 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2601 fprintf (sched_dump, "%d ", INSN_UID (XEXP (link, 0)));
2602 fprintf (sched_dump, "\n");
2606 fprintf (sched_dump, "\n");
2609 /* Schedule a region. A region is either an inner loop, a loop-free
2610 subroutine, or a single basic block. Each bb in the region is
2611 scheduled after its flow predecessors. */
2613 static void
2614 schedule_region (rgn)
2615 int rgn;
2617 int bb;
2618 int rgn_n_insns = 0;
2619 int sched_rgn_n_insns = 0;
2621 /* Set variables for the current region. */
2622 current_nr_blocks = RGN_NR_BLOCKS (rgn);
2623 current_blocks = RGN_BLOCKS (rgn);
2625 init_deps_global ();
2627 /* Initializations for region data dependence analyisis. */
2628 bb_deps = (struct deps *) xmalloc (sizeof (struct deps) * current_nr_blocks);
2629 for (bb = 0; bb < current_nr_blocks; bb++)
2630 init_deps (bb_deps + bb);
2632 /* Compute LOG_LINKS. */
2633 for (bb = 0; bb < current_nr_blocks; bb++)
2634 compute_block_backward_dependences (bb);
2636 /* Compute INSN_DEPEND. */
2637 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
2639 rtx head, tail;
2640 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2642 compute_forward_dependences (head, tail);
2645 /* Set priorities. */
2646 for (bb = 0; bb < current_nr_blocks; bb++)
2648 rtx head, tail;
2649 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2651 rgn_n_insns += set_priorities (head, tail);
2654 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
2655 if (current_nr_blocks > 1)
2657 int i;
2659 prob = (float *) xmalloc ((current_nr_blocks) * sizeof (float));
2661 dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
2662 sbitmap_vector_zero (dom, current_nr_blocks);
2663 /* Edge to bit. */
2664 rgn_nr_edges = 0;
2665 edge_to_bit = (int *) xmalloc (nr_edges * sizeof (int));
2666 for (i = 1; i < nr_edges; i++)
2667 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
2668 EDGE_TO_BIT (i) = rgn_nr_edges++;
2669 rgn_edges = (int *) xmalloc (rgn_nr_edges * sizeof (int));
2671 rgn_nr_edges = 0;
2672 for (i = 1; i < nr_edges; i++)
2673 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
2674 rgn_edges[rgn_nr_edges++] = i;
2676 /* Split edges. */
2677 pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2678 sbitmap_vector_zero (pot_split, current_nr_blocks);
2679 ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2680 sbitmap_vector_zero (ancestor_edges, current_nr_blocks);
2682 /* Compute probabilities, dominators, split_edges. */
2683 for (bb = 0; bb < current_nr_blocks; bb++)
2684 compute_dom_prob_ps (bb);
2687 /* Now we can schedule all blocks. */
2688 for (bb = 0; bb < current_nr_blocks; bb++)
2690 rtx head, tail;
2691 int b = BB_TO_BLOCK (bb);
2693 get_block_head_tail (b, &head, &tail);
2695 if (no_real_insns_p (head, tail))
2696 continue;
2698 current_sched_info->prev_head = PREV_INSN (head);
2699 current_sched_info->next_tail = NEXT_INSN (tail);
2701 if (write_symbols != NO_DEBUG)
2703 save_line_notes (b, head, tail);
2704 rm_line_notes (head, tail);
2707 /* rm_other_notes only removes notes which are _inside_ the
2708 block---that is, it won't remove notes before the first real insn
2709 or after the last real insn of the block. So if the first insn
2710 has a REG_SAVE_NOTE which would otherwise be emitted before the
2711 insn, it is redundant with the note before the start of the
2712 block, and so we have to take it out. */
2713 if (INSN_P (head))
2715 rtx note;
2717 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
2718 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
2720 remove_note (head, note);
2721 note = XEXP (note, 1);
2722 remove_note (head, note);
2726 /* Remove remaining note insns from the block, save them in
2727 note_list. These notes are restored at the end of
2728 schedule_block (). */
2729 rm_other_notes (head, tail);
2731 target_bb = bb;
2733 current_sched_info->queue_must_finish_empty
2734 = current_nr_blocks > 1 && !flag_schedule_interblock;
2736 schedule_block (b, rgn_n_insns);
2737 sched_rgn_n_insns += sched_n_insns;
2739 /* Update target block boundaries. */
2740 if (head == BLOCK_HEAD (b))
2741 BLOCK_HEAD (b) = current_sched_info->head;
2742 if (tail == BLOCK_END (b))
2743 BLOCK_END (b) = current_sched_info->tail;
2745 /* Clean up. */
2746 if (current_nr_blocks > 1)
2748 free (candidate_table);
2749 free (bblst_table);
2750 free (bitlst_table);
2754 /* Sanity check: verify that all region insns were scheduled. */
2755 if (sched_rgn_n_insns != rgn_n_insns)
2756 abort ();
2758 /* Restore line notes. */
2759 if (write_symbols != NO_DEBUG)
2761 for (bb = 0; bb < current_nr_blocks; bb++)
2763 rtx head, tail;
2764 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2765 restore_line_notes (head, tail);
2769 /* Done with this region. */
2770 free_pending_lists ();
2772 finish_deps_global ();
2774 free (bb_deps);
2776 if (current_nr_blocks > 1)
2778 free (prob);
2779 sbitmap_vector_free (dom);
2780 sbitmap_vector_free (pot_split);
2781 sbitmap_vector_free (ancestor_edges);
2782 free (edge_to_bit);
2783 free (rgn_edges);
2787 /* Indexed by region, holds the number of death notes found in that region.
2788 Used for consistency checks. */
2789 static int *deaths_in_region;
2791 /* Initialize data structures for region scheduling. */
2793 static void
2794 init_regions ()
2796 sbitmap blocks;
2797 int rgn;
2799 nr_regions = 0;
2800 rgn_table = (region *) xmalloc ((n_basic_blocks) * sizeof (region));
2801 rgn_bb_table = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
2802 block_to_bb = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
2803 containing_rgn = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
2805 /* Compute regions for scheduling. */
2806 if (reload_completed
2807 || n_basic_blocks == 1
2808 || !flag_schedule_interblock)
2810 find_single_block_region ();
2812 else
2814 /* Verify that a 'good' control flow graph can be built. */
2815 if (is_cfg_nonregular ())
2817 find_single_block_region ();
2819 else
2821 sbitmap *dom;
2822 struct edge_list *edge_list;
2824 dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
2826 /* The scheduler runs after flow; therefore, we can't blindly call
2827 back into find_basic_blocks since doing so could invalidate the
2828 info in global_live_at_start.
2830 Consider a block consisting entirely of dead stores; after life
2831 analysis it would be a block of NOTE_INSN_DELETED notes. If
2832 we call find_basic_blocks again, then the block would be removed
2833 entirely and invalidate our the register live information.
2835 We could (should?) recompute register live information. Doing
2836 so may even be beneficial. */
2837 edge_list = create_edge_list ();
2839 /* Compute the dominators and post dominators. */
2840 calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
2842 /* build_control_flow will return nonzero if it detects unreachable
2843 blocks or any other irregularity with the cfg which prevents
2844 cross block scheduling. */
2845 if (build_control_flow (edge_list) != 0)
2846 find_single_block_region ();
2847 else
2848 find_rgns (edge_list, dom);
2850 if (sched_verbose >= 3)
2851 debug_regions ();
2853 /* We are done with flow's edge list. */
2854 free_edge_list (edge_list);
2856 /* For now. This will move as more and more of haifa is converted
2857 to using the cfg code in flow.c. */
2858 free (dom);
2863 if (CHECK_DEAD_NOTES)
2865 blocks = sbitmap_alloc (n_basic_blocks);
2866 deaths_in_region = (int *) xmalloc (sizeof (int) * nr_regions);
2867 /* Remove all death notes from the subroutine. */
2868 for (rgn = 0; rgn < nr_regions; rgn++)
2870 int b;
2872 sbitmap_zero (blocks);
2873 for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
2874 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]);
2876 deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1);
2878 sbitmap_free (blocks);
2880 else
2881 count_or_remove_death_notes (NULL, 1);
2884 /* The one entry point in this file. DUMP_FILE is the dump file for
2885 this pass. */
2887 void
2888 schedule_insns (dump_file)
2889 FILE *dump_file;
2891 sbitmap large_region_blocks, blocks;
2892 int rgn;
2893 int any_large_regions;
2895 /* Taking care of this degenerate case makes the rest of
2896 this code simpler. */
2897 if (n_basic_blocks == 0)
2898 return;
2900 scope_to_insns_initialize ();
2902 nr_inter = 0;
2903 nr_spec = 0;
2905 sched_init (dump_file);
2907 init_regions ();
2909 current_sched_info = &region_sched_info;
2911 /* Schedule every region in the subroutine. */
2912 for (rgn = 0; rgn < nr_regions; rgn++)
2913 schedule_region (rgn);
2915 /* Update life analysis for the subroutine. Do single block regions
2916 first so that we can verify that live_at_start didn't change. Then
2917 do all other blocks. */
2918 /* ??? There is an outside possibility that update_life_info, or more
2919 to the point propagate_block, could get called with non-zero flags
2920 more than once for one basic block. This would be kinda bad if it
2921 were to happen, since REG_INFO would be accumulated twice for the
2922 block, and we'd have twice the REG_DEAD notes.
2924 I'm fairly certain that this _shouldn't_ happen, since I don't think
2925 that live_at_start should change at region heads. Not sure what the
2926 best way to test for this kind of thing... */
2928 allocate_reg_life_data ();
2929 compute_bb_for_insn (get_max_uid ());
2931 any_large_regions = 0;
2932 large_region_blocks = sbitmap_alloc (n_basic_blocks);
2933 sbitmap_ones (large_region_blocks);
2935 blocks = sbitmap_alloc (n_basic_blocks);
2936 sbitmap_zero (blocks);
2938 /* Update life information. For regions consisting of multiple blocks
2939 we've possibly done interblock scheduling that affects global liveness.
2940 For regions consisting of single blocks we need to do only local
2941 liveness. */
2942 for (rgn = 0; rgn < nr_regions; rgn++)
2943 if (RGN_NR_BLOCKS (rgn) > 1)
2944 any_large_regions = 1;
2945 else
2947 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2948 RESET_BIT (large_region_blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2951 /* Don't update reg info after reload, since that affects
2952 regs_ever_live, which should not change after reload. */
2953 update_life_info (blocks, UPDATE_LIFE_LOCAL,
2954 (reload_completed ? PROP_DEATH_NOTES
2955 : PROP_DEATH_NOTES | PROP_REG_INFO));
2956 if (any_large_regions)
2958 update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL,
2959 PROP_DEATH_NOTES | PROP_REG_INFO);
2962 if (CHECK_DEAD_NOTES)
2964 /* Verify the counts of basic block notes in single the basic block
2965 regions. */
2966 for (rgn = 0; rgn < nr_regions; rgn++)
2967 if (RGN_NR_BLOCKS (rgn) == 1)
2969 sbitmap_zero (blocks);
2970 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2972 if (deaths_in_region[rgn]
2973 != count_or_remove_death_notes (blocks, 0))
2974 abort ();
2976 free (deaths_in_region);
2979 /* Reposition the prologue and epilogue notes in case we moved the
2980 prologue/epilogue insns. */
2981 if (reload_completed)
2982 reposition_prologue_and_epilogue_notes (get_insns ());
2984 /* Delete redundant line notes. */
2985 if (write_symbols != NO_DEBUG)
2986 rm_redundant_line_notes ();
2988 scope_to_insns_finalize ();
2990 if (sched_verbose)
2992 if (reload_completed == 0 && flag_schedule_interblock)
2994 fprintf (sched_dump,
2995 "\n;; Procedure interblock/speculative motions == %d/%d \n",
2996 nr_inter, nr_spec);
2998 else
3000 if (nr_inter > 0)
3001 abort ();
3003 fprintf (sched_dump, "\n\n");
3006 /* Clean up. */
3007 free (rgn_table);
3008 free (rgn_bb_table);
3009 free (block_to_bb);
3010 free (containing_rgn);
3012 sched_finish ();
3014 if (edge_table)
3016 free (edge_table);
3017 edge_table = NULL;
3020 if (in_edges)
3022 free (in_edges);
3023 in_edges = NULL;
3025 if (out_edges)
3027 free (out_edges);
3028 out_edges = NULL;
3031 sbitmap_free (blocks);
3032 sbitmap_free (large_region_blocks);
3034 #endif