Merge branch 'master' of ssh://crater.dragonflybsd.org/repository/git/dragonfly
[dragonfly.git] / contrib / gcc-3.4 / gcc / sched-rgn.c
CommitLineData
003757ed
MD
1/* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
4 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5 and currently maintained by, Jim Wilson (wilson@cygnus.com)
6
7This file is part of GCC.
8
9GCC is free software; you can redistribute it and/or modify it under
10the terms of the GNU General Public License as published by the Free
11Software Foundation; either version 2, or (at your option) any later
12version.
13
14GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15WARRANTY; without even the implied warranty of MERCHANTABILITY or
16FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17for more details.
18
19You should have received a copy of the GNU General Public License
20along with GCC; see the file COPYING. If not, write to the Free
21Software Foundation, 59 Temple Place - Suite 330, Boston, MA
2202111-1307, USA. */
23
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.
27
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.
31
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.
37
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. */
47\f
48#include "config.h"
49#include "system.h"
50#include "coretypes.h"
51#include "tm.h"
52#include "toplev.h"
53#include "rtl.h"
54#include "tm_p.h"
55#include "hard-reg-set.h"
56#include "basic-block.h"
57#include "regs.h"
58#include "function.h"
59#include "flags.h"
60#include "insn-config.h"
61#include "insn-attr.h"
62#include "except.h"
63#include "toplev.h"
64#include "recog.h"
65#include "cfglayout.h"
66#include "sched-int.h"
67#include "target.h"
68
69/* Define when we want to do count REG_DEAD notes before and after scheduling
70 for sanity checking. We can't do that when conditional execution is used,
71 as REG_DEAD exist only for unconditional deaths. */
72
73#if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING)
74#define CHECK_DEAD_NOTES 1
75#else
76#define CHECK_DEAD_NOTES 0
77#endif
78
79
80#ifdef INSN_SCHEDULING
81/* Some accessor macros for h_i_d members only used within this file. */
82#define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count)
83#define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load)
84#define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn)
85
86#define MAX_RGN_BLOCKS 10
87#define MAX_RGN_INSNS 100
88
89/* nr_inter/spec counts interblock/speculative motion for the function. */
90static int nr_inter, nr_spec;
91
92/* Control flow graph edges are kept in circular lists. */
93typedef struct
94{
95 int from_block;
96 int to_block;
97 int next_in;
98 int next_out;
99}
100haifa_edge;
101static haifa_edge *edge_table;
102
103#define NEXT_IN(edge) (edge_table[edge].next_in)
104#define NEXT_OUT(edge) (edge_table[edge].next_out)
105#define FROM_BLOCK(edge) (edge_table[edge].from_block)
106#define TO_BLOCK(edge) (edge_table[edge].to_block)
107
108/* Number of edges in the control flow graph. (In fact, larger than
109 that by 1, since edge 0 is unused.) */
110static int nr_edges;
111
112/* Circular list of incoming/outgoing edges of a block. */
113static int *in_edges;
114static int *out_edges;
115
116#define IN_EDGES(block) (in_edges[block])
117#define OUT_EDGES(block) (out_edges[block])
118
119static int is_cfg_nonregular (void);
120static int build_control_flow (struct edge_list *);
121static void new_edge (int, int);
122
123/* A region is the main entity for interblock scheduling: insns
124 are allowed to move between blocks in the same region, along
125 control flow graph edges, in the 'up' direction. */
126typedef struct
127{
128 int rgn_nr_blocks; /* Number of blocks in region. */
129 int rgn_blocks; /* cblocks in the region (actually index in rgn_bb_table). */
130}
131region;
132
133/* Number of regions in the procedure. */
134static int nr_regions;
135
136/* Table of region descriptions. */
137static region *rgn_table;
138
139/* Array of lists of regions' blocks. */
140static int *rgn_bb_table;
141
142/* Topological order of blocks in the region (if b2 is reachable from
143 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
144 always referred to by either block or b, while its topological
145 order name (in the region) is referred to by bb. */
146static int *block_to_bb;
147
148/* The number of the region containing a block. */
149static int *containing_rgn;
150
151#define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
152#define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
153#define BLOCK_TO_BB(block) (block_to_bb[block])
154#define CONTAINING_RGN(block) (containing_rgn[block])
155
156void debug_regions (void);
157static void find_single_block_region (void);
158static void find_rgns (struct edge_list *);
159static int too_large (int, int *, int *);
160
161extern void debug_live (int, int);
162
163/* Blocks of the current region being scheduled. */
164static int current_nr_blocks;
165static int current_blocks;
166
167/* The mapping from bb to block. */
168#define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
169
170typedef struct
171{
172 int *first_member; /* Pointer to the list start in bitlst_table. */
173 int nr_members; /* The number of members of the bit list. */
174}
175bitlst;
176
177static int bitlst_table_last;
178static int *bitlst_table;
179
180static void extract_bitlst (sbitmap, bitlst *);
181
182/* Target info declarations.
183
184 The block currently being scheduled is referred to as the "target" block,
185 while other blocks in the region from which insns can be moved to the
186 target are called "source" blocks. The candidate structure holds info
187 about such sources: are they valid? Speculative? Etc. */
188typedef bitlst bblst;
189typedef struct
190{
191 char is_valid;
192 char is_speculative;
193 int src_prob;
194 bblst split_bbs;
195 bblst update_bbs;
196}
197candidate;
198
199static candidate *candidate_table;
200
201/* A speculative motion requires checking live information on the path
202 from 'source' to 'target'. The split blocks are those to be checked.
203 After a speculative motion, live information should be modified in
204 the 'update' blocks.
205
206 Lists of split and update blocks for each candidate of the current
207 target are in array bblst_table. */
208static int *bblst_table, bblst_size, bblst_last;
209
210#define IS_VALID(src) ( candidate_table[src].is_valid )
211#define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
212#define SRC_PROB(src) ( candidate_table[src].src_prob )
213
214/* The bb being currently scheduled. */
215static int target_bb;
216
217/* List of edges. */
218typedef bitlst edgelst;
219
220/* Target info functions. */
221static void split_edges (int, int, edgelst *);
222static void compute_trg_info (int);
223void debug_candidate (int);
224void debug_candidates (int);
225
226/* Dominators array: dom[i] contains the sbitmap of dominators of
227 bb i in the region. */
228static sbitmap *dom;
229
230/* bb 0 is the only region entry. */
231#define IS_RGN_ENTRY(bb) (!bb)
232
233/* Is bb_src dominated by bb_trg. */
234#define IS_DOMINATED(bb_src, bb_trg) \
235( TEST_BIT (dom[bb_src], bb_trg) )
236
237/* Probability: Prob[i] is a float in [0, 1] which is the probability
238 of bb i relative to the region entry. */
239static float *prob;
240
241/* The probability of bb_src, relative to bb_trg. Note, that while the
242 'prob[bb]' is a float in [0, 1], this macro returns an integer
243 in [0, 100]. */
244#define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
245 prob[bb_trg])))
246
247/* Bit-set of edges, where bit i stands for edge i. */
248typedef sbitmap edgeset;
249
250/* Number of edges in the region. */
251static int rgn_nr_edges;
252
253/* Array of size rgn_nr_edges. */
254static int *rgn_edges;
255
256
257/* Mapping from each edge in the graph to its number in the rgn. */
258static int *edge_to_bit;
259#define EDGE_TO_BIT(edge) (edge_to_bit[edge])
260
261/* The split edges of a source bb is different for each target
262 bb. In order to compute this efficiently, the 'potential-split edges'
263 are computed for each bb prior to scheduling a region. This is actually
264 the split edges of each bb relative to the region entry.
265
266 pot_split[bb] is the set of potential split edges of bb. */
267static edgeset *pot_split;
268
269/* For every bb, a set of its ancestor edges. */
270static edgeset *ancestor_edges;
271
272static void compute_dom_prob_ps (int);
273
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)))
277
278/* Parameters affecting the decision of rank_for_schedule().
279 ??? Nope. But MIN_PROBABILITY is used in compute_trg_info. */
280#define MIN_PROBABILITY 40
281
282/* Speculative scheduling functions. */
283static int check_live_1 (int, rtx);
284static void update_live_1 (int, rtx);
285static int check_live (rtx, int);
286static void update_live (rtx, int);
287static void set_spec_fed (rtx);
288static int is_pfree (rtx, int, int);
289static int find_conditional_protection (rtx, int);
290static int is_conditionally_protected (rtx, int, int);
291static int is_prisky (rtx, int, int);
292static int is_exception_free (rtx, int, int);
293
294static bool sets_likely_spilled (rtx);
295static void sets_likely_spilled_1 (rtx, rtx, void *);
296static void add_branch_dependences (rtx, rtx);
297static void compute_block_backward_dependences (int);
298void debug_dependencies (void);
299
300static void init_regions (void);
301static void schedule_region (int);
302static rtx concat_INSN_LIST (rtx, rtx);
303static void concat_insn_mem_list (rtx, rtx, rtx *, rtx *);
304static void propagate_deps (int, struct deps *);
305static void free_pending_lists (void);
306
307/* Functions for construction of the control flow graph. */
308
309/* Return 1 if control flow graph should not be constructed, 0 otherwise.
310
311 We decide not to build the control flow graph if there is possibly more
312 than one entry to the function, if computed branches exist, of if we
313 have nonlocal gotos. */
314
315static int
316is_cfg_nonregular (void)
317{
318 basic_block b;
319 rtx insn;
320 RTX_CODE code;
321
322 /* If we have a label that could be the target of a nonlocal goto, then
323 the cfg is not well structured. */
324 if (nonlocal_goto_handler_labels)
325 return 1;
326
327 /* If we have any forced labels, then the cfg is not well structured. */
328 if (forced_labels)
329 return 1;
330
331 /* If this function has a computed jump, then we consider the cfg
332 not well structured. */
333 if (current_function_has_computed_jump)
334 return 1;
335
336 /* If we have exception handlers, then we consider the cfg not well
337 structured. ?!? We should be able to handle this now that flow.c
338 computes an accurate cfg for EH. */
339 if (current_function_has_exception_handlers ())
340 return 1;
341
342 /* If we have non-jumping insns which refer to labels, then we consider
343 the cfg not well structured. */
344 /* Check for labels referred to other thn by jumps. */
345 FOR_EACH_BB (b)
346 for (insn = BB_HEAD (b); ; insn = NEXT_INSN (insn))
347 {
348 code = GET_CODE (insn);
349 if (GET_RTX_CLASS (code) == 'i' && code != JUMP_INSN)
350 {
351 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
352
353 if (note
354 && ! (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
355 && find_reg_note (NEXT_INSN (insn), REG_LABEL,
356 XEXP (note, 0))))
357 return 1;
358 }
359
360 if (insn == BB_END (b))
361 break;
362 }
363
364 /* All the tests passed. Consider the cfg well structured. */
365 return 0;
366}
367
368/* Build the control flow graph and set nr_edges.
369
370 Instead of trying to build a cfg ourselves, we rely on flow to
371 do it for us. Stamp out useless code (and bug) duplication.
372
373 Return nonzero if an irregularity in the cfg is found which would
374 prevent cross block scheduling. */
375
376static int
377build_control_flow (struct edge_list *edge_list)
378{
379 int i, unreachable, num_edges;
380 basic_block b;
381
382 /* This already accounts for entry/exit edges. */
383 num_edges = NUM_EDGES (edge_list);
384
385 /* Unreachable loops with more than one basic block are detected
386 during the DFS traversal in find_rgns.
387
388 Unreachable loops with a single block are detected here. This
389 test is redundant with the one in find_rgns, but it's much
390 cheaper to go ahead and catch the trivial case here. */
391 unreachable = 0;
392 FOR_EACH_BB (b)
393 {
394 if (b->pred == NULL
395 || (b->pred->src == b
396 && b->pred->pred_next == NULL))
397 unreachable = 1;
398 }
399
400 /* ??? We can kill these soon. */
401 in_edges = xcalloc (last_basic_block, sizeof (int));
402 out_edges = xcalloc (last_basic_block, sizeof (int));
403 edge_table = xcalloc (num_edges, sizeof (haifa_edge));
404
405 nr_edges = 0;
406 for (i = 0; i < num_edges; i++)
407 {
408 edge e = INDEX_EDGE (edge_list, i);
409
410 if (e->dest != EXIT_BLOCK_PTR
411 && e->src != ENTRY_BLOCK_PTR)
412 new_edge (e->src->index, e->dest->index);
413 }
414
415 /* Increment by 1, since edge 0 is unused. */
416 nr_edges++;
417
418 return unreachable;
419}
420
421/* Record an edge in the control flow graph from SOURCE to TARGET.
422
423 In theory, this is redundant with the s_succs computed above, but
424 we have not converted all of haifa to use information from the
425 integer lists. */
426
427static void
428new_edge (int source, int target)
429{
430 int e, next_edge;
431 int curr_edge, fst_edge;
432
433 /* Check for duplicates. */
434 fst_edge = curr_edge = OUT_EDGES (source);
435 while (curr_edge)
436 {
437 if (FROM_BLOCK (curr_edge) == source
438 && TO_BLOCK (curr_edge) == target)
439 {
440 return;
441 }
442
443 curr_edge = NEXT_OUT (curr_edge);
444
445 if (fst_edge == curr_edge)
446 break;
447 }
448
449 e = ++nr_edges;
450
451 FROM_BLOCK (e) = source;
452 TO_BLOCK (e) = target;
453
454 if (OUT_EDGES (source))
455 {
456 next_edge = NEXT_OUT (OUT_EDGES (source));
457 NEXT_OUT (OUT_EDGES (source)) = e;
458 NEXT_OUT (e) = next_edge;
459 }
460 else
461 {
462 OUT_EDGES (source) = e;
463 NEXT_OUT (e) = e;
464 }
465
466 if (IN_EDGES (target))
467 {
468 next_edge = NEXT_IN (IN_EDGES (target));
469 NEXT_IN (IN_EDGES (target)) = e;
470 NEXT_IN (e) = next_edge;
471 }
472 else
473 {
474 IN_EDGES (target) = e;
475 NEXT_IN (e) = e;
476 }
477}
478
479/* Translate a bit-set SET to a list BL of the bit-set members. */
480
481static void
482extract_bitlst (sbitmap set, bitlst *bl)
483{
484 int i;
485
486 /* bblst table space is reused in each call to extract_bitlst. */
487 bitlst_table_last = 0;
488
489 bl->first_member = &bitlst_table[bitlst_table_last];
490 bl->nr_members = 0;
491
492 /* Iterate over each word in the bitset. */
493 EXECUTE_IF_SET_IN_SBITMAP (set, 0, i,
494 {
495 bitlst_table[bitlst_table_last++] = i;
496 (bl->nr_members)++;
497 });
498
499}
500
501/* Functions for the construction of regions. */
502
503/* Print the regions, for debugging purposes. Callable from debugger. */
504
505void
506debug_regions (void)
507{
508 int rgn, bb;
509
510 fprintf (sched_dump, "\n;; ------------ REGIONS ----------\n\n");
511 for (rgn = 0; rgn < nr_regions; rgn++)
512 {
513 fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
514 rgn_table[rgn].rgn_nr_blocks);
515 fprintf (sched_dump, ";;\tbb/block: ");
516
517 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
518 {
519 current_blocks = RGN_BLOCKS (rgn);
520
521 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
522 abort ();
523
524 fprintf (sched_dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
525 }
526
527 fprintf (sched_dump, "\n\n");
528 }
529}
530
531/* Build a single block region for each basic block in the function.
532 This allows for using the same code for interblock and basic block
533 scheduling. */
534
535static void
536find_single_block_region (void)
537{
538 basic_block bb;
539
540 nr_regions = 0;
541
542 FOR_EACH_BB (bb)
543 {
544 rgn_bb_table[nr_regions] = bb->index;
545 RGN_NR_BLOCKS (nr_regions) = 1;
546 RGN_BLOCKS (nr_regions) = nr_regions;
547 CONTAINING_RGN (bb->index) = nr_regions;
548 BLOCK_TO_BB (bb->index) = 0;
549 nr_regions++;
550 }
551}
552
553/* Update number of blocks and the estimate for number of insns
554 in the region. Return 1 if the region is "too large" for interblock
555 scheduling (compile time considerations), otherwise return 0. */
556
557static int
558too_large (int block, int *num_bbs, int *num_insns)
559{
560 (*num_bbs)++;
561 (*num_insns) += (INSN_LUID (BB_END (BASIC_BLOCK (block))) -
562 INSN_LUID (BB_HEAD (BASIC_BLOCK (block))));
563 if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
564 return 1;
565 else
566 return 0;
567}
568
569/* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
570 is still an inner loop. Put in max_hdr[blk] the header of the most inner
571 loop containing blk. */
572#define UPDATE_LOOP_RELATIONS(blk, hdr) \
573{ \
574 if (max_hdr[blk] == -1) \
575 max_hdr[blk] = hdr; \
576 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
577 RESET_BIT (inner, hdr); \
578 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
579 { \
580 RESET_BIT (inner,max_hdr[blk]); \
581 max_hdr[blk] = hdr; \
582 } \
583}
584
585/* Find regions for interblock scheduling.
586
587 A region for scheduling can be:
588
589 * A loop-free procedure, or
590
591 * A reducible inner loop, or
592
593 * A basic block not contained in any other region.
594
595 ?!? In theory we could build other regions based on extended basic
596 blocks or reverse extended basic blocks. Is it worth the trouble?
597
598 Loop blocks that form a region are put into the region's block list
599 in topological order.
600
601 This procedure stores its results into the following global (ick) variables
602
603 * rgn_nr
604 * rgn_table
605 * rgn_bb_table
606 * block_to_bb
607 * containing region
608
609 We use dominator relationships to avoid making regions out of non-reducible
610 loops.
611
612 This procedure needs to be converted to work on pred/succ lists instead
613 of edge tables. That would simplify it somewhat. */
614
615static void
616find_rgns (struct edge_list *edge_list)
617{
618 int *max_hdr, *dfs_nr, *stack, *degree;
619 char no_loops = 1;
620 int node, child, loop_head, i, head, tail;
621 int count = 0, sp, idx = 0;
622 int current_edge = out_edges[ENTRY_BLOCK_PTR->succ->dest->index];
623 int num_bbs, num_insns, unreachable;
624 int too_large_failure;
625 basic_block bb;
626
627 /* Note if an edge has been passed. */
628 sbitmap passed;
629
630 /* Note if a block is a natural loop header. */
631 sbitmap header;
632
633 /* Note if a block is a natural inner loop header. */
634 sbitmap inner;
635
636 /* Note if a block is in the block queue. */
637 sbitmap in_queue;
638
639 /* Note if a block is in the block queue. */
640 sbitmap in_stack;
641
642 int num_edges = NUM_EDGES (edge_list);
643
644 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
645 and a mapping from block to its loop header (if the block is contained
646 in a loop, else -1).
647
648 Store results in HEADER, INNER, and MAX_HDR respectively, these will
649 be used as inputs to the second traversal.
650
651 STACK, SP and DFS_NR are only used during the first traversal. */
652
653 /* Allocate and initialize variables for the first traversal. */
654 max_hdr = xmalloc (last_basic_block * sizeof (int));
655 dfs_nr = xcalloc (last_basic_block, sizeof (int));
656 stack = xmalloc (nr_edges * sizeof (int));
657
658 inner = sbitmap_alloc (last_basic_block);
659 sbitmap_ones (inner);
660
661 header = sbitmap_alloc (last_basic_block);
662 sbitmap_zero (header);
663
664 passed = sbitmap_alloc (nr_edges);
665 sbitmap_zero (passed);
666
667 in_queue = sbitmap_alloc (last_basic_block);
668 sbitmap_zero (in_queue);
669
670 in_stack = sbitmap_alloc (last_basic_block);
671 sbitmap_zero (in_stack);
672
673 for (i = 0; i < last_basic_block; i++)
674 max_hdr[i] = -1;
675
676 /* DFS traversal to find inner loops in the cfg. */
677
678 sp = -1;
679 while (1)
680 {
681 if (current_edge == 0 || TEST_BIT (passed, current_edge))
682 {
683 /* We have reached a leaf node or a node that was already
684 processed. Pop edges off the stack until we find
685 an edge that has not yet been processed. */
686 while (sp >= 0
687 && (current_edge == 0 || TEST_BIT (passed, current_edge)))
688 {
689 /* Pop entry off the stack. */
690 current_edge = stack[sp--];
691 node = FROM_BLOCK (current_edge);
692 child = TO_BLOCK (current_edge);
693 RESET_BIT (in_stack, child);
694 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
695 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
696 current_edge = NEXT_OUT (current_edge);
697 }
698
699 /* See if have finished the DFS tree traversal. */
700 if (sp < 0 && TEST_BIT (passed, current_edge))
701 break;
702
703 /* Nope, continue the traversal with the popped node. */
704 continue;
705 }
706
707 /* Process a node. */
708 node = FROM_BLOCK (current_edge);
709 child = TO_BLOCK (current_edge);
710 SET_BIT (in_stack, node);
711 dfs_nr[node] = ++count;
712
713 /* If the successor is in the stack, then we've found a loop.
714 Mark the loop, if it is not a natural loop, then it will
715 be rejected during the second traversal. */
716 if (TEST_BIT (in_stack, child))
717 {
718 no_loops = 0;
719 SET_BIT (header, child);
720 UPDATE_LOOP_RELATIONS (node, child);
721 SET_BIT (passed, current_edge);
722 current_edge = NEXT_OUT (current_edge);
723 continue;
724 }
725
726 /* If the child was already visited, then there is no need to visit
727 it again. Just update the loop relationships and restart
728 with a new edge. */
729 if (dfs_nr[child])
730 {
731 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
732 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
733 SET_BIT (passed, current_edge);
734 current_edge = NEXT_OUT (current_edge);
735 continue;
736 }
737
738 /* Push an entry on the stack and continue DFS traversal. */
739 stack[++sp] = current_edge;
740 SET_BIT (passed, current_edge);
741 current_edge = OUT_EDGES (child);
742
743 /* This is temporary until haifa is converted to use rth's new
744 cfg routines which have true entry/exit blocks and the
745 appropriate edges from/to those blocks.
746
747 Generally we update dfs_nr for a node when we process its
748 out edge. However, if the node has no out edge then we will
749 not set dfs_nr for that node. This can confuse the scheduler
750 into thinking that we have unreachable blocks, which in turn
751 disables cross block scheduling.
752
753 So, if we have a node with no out edges, go ahead and mark it
754 as reachable now. */
755 if (current_edge == 0)
756 dfs_nr[child] = ++count;
757 }
758
759 /* Another check for unreachable blocks. The earlier test in
760 is_cfg_nonregular only finds unreachable blocks that do not
761 form a loop.
762
763 The DFS traversal will mark every block that is reachable from
764 the entry node by placing a nonzero value in dfs_nr. Thus if
765 dfs_nr is zero for any block, then it must be unreachable. */
766 unreachable = 0;
767 FOR_EACH_BB (bb)
768 if (dfs_nr[bb->index] == 0)
769 {
770 unreachable = 1;
771 break;
772 }
773
774 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
775 to hold degree counts. */
776 degree = dfs_nr;
777
778 FOR_EACH_BB (bb)
779 degree[bb->index] = 0;
780 for (i = 0; i < num_edges; i++)
781 {
782 edge e = INDEX_EDGE (edge_list, i);
783
784 if (e->dest != EXIT_BLOCK_PTR)
785 degree[e->dest->index]++;
786 }
787
788 /* Do not perform region scheduling if there are any unreachable
789 blocks. */
790 if (!unreachable)
791 {
792 int *queue;
793
794 if (no_loops)
795 SET_BIT (header, 0);
796
797 /* Second traversal:find reducible inner loops and topologically sort
798 block of each region. */
799
800 queue = xmalloc (n_basic_blocks * sizeof (int));
801
802 /* Find blocks which are inner loop headers. We still have non-reducible
803 loops to consider at this point. */
804 FOR_EACH_BB (bb)
805 {
806 if (TEST_BIT (header, bb->index) && TEST_BIT (inner, bb->index))
807 {
808 edge e;
809 basic_block jbb;
810
811 /* Now check that the loop is reducible. We do this separate
812 from finding inner loops so that we do not find a reducible
813 loop which contains an inner non-reducible loop.
814
815 A simple way to find reducible/natural loops is to verify
816 that each block in the loop is dominated by the loop
817 header.
818
819 If there exists a block that is not dominated by the loop
820 header, then the block is reachable from outside the loop
821 and thus the loop is not a natural loop. */
822 FOR_EACH_BB (jbb)
823 {
824 /* First identify blocks in the loop, except for the loop
825 entry block. */
826 if (bb->index == max_hdr[jbb->index] && bb != jbb)
827 {
828 /* Now verify that the block is dominated by the loop
829 header. */
830 if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))
831 break;
832 }
833 }
834
835 /* If we exited the loop early, then I is the header of
836 a non-reducible loop and we should quit processing it
837 now. */
838 if (jbb != EXIT_BLOCK_PTR)
839 continue;
840
841 /* I is a header of an inner loop, or block 0 in a subroutine
842 with no loops at all. */
843 head = tail = -1;
844 too_large_failure = 0;
845 loop_head = max_hdr[bb->index];
846
847 /* Decrease degree of all I's successors for topological
848 ordering. */
849 for (e = bb->succ; e; e = e->succ_next)
850 if (e->dest != EXIT_BLOCK_PTR)
851 --degree[e->dest->index];
852
853 /* Estimate # insns, and count # blocks in the region. */
854 num_bbs = 1;
855 num_insns = (INSN_LUID (BB_END (bb))
856 - INSN_LUID (BB_HEAD (bb)));
857
858 /* Find all loop latches (blocks with back edges to the loop
859 header) or all the leaf blocks in the cfg has no loops.
860
861 Place those blocks into the queue. */
862 if (no_loops)
863 {
864 FOR_EACH_BB (jbb)
865 /* Leaf nodes have only a single successor which must
866 be EXIT_BLOCK. */
867 if (jbb->succ
868 && jbb->succ->dest == EXIT_BLOCK_PTR
869 && jbb->succ->succ_next == NULL)
870 {
871 queue[++tail] = jbb->index;
872 SET_BIT (in_queue, jbb->index);
873
874 if (too_large (jbb->index, &num_bbs, &num_insns))
875 {
876 too_large_failure = 1;
877 break;
878 }
879 }
880 }
881 else
882 {
883 edge e;
884
885 for (e = bb->pred; e; e = e->pred_next)
886 {
887 if (e->src == ENTRY_BLOCK_PTR)
888 continue;
889
890 node = e->src->index;
891
892 if (max_hdr[node] == loop_head && node != bb->index)
893 {
894 /* This is a loop latch. */
895 queue[++tail] = node;
896 SET_BIT (in_queue, node);
897
898 if (too_large (node, &num_bbs, &num_insns))
899 {
900 too_large_failure = 1;
901 break;
902 }
903 }
904 }
905 }
906
907 /* Now add all the blocks in the loop to the queue.
908
909 We know the loop is a natural loop; however the algorithm
910 above will not always mark certain blocks as being in the
911 loop. Consider:
912 node children
913 a b,c
914 b c
915 c a,d
916 d b
917
918 The algorithm in the DFS traversal may not mark B & D as part
919 of the loop (ie they will not have max_hdr set to A).
920
921 We know they can not be loop latches (else they would have
922 had max_hdr set since they'd have a backedge to a dominator
923 block). So we don't need them on the initial queue.
924
925 We know they are part of the loop because they are dominated
926 by the loop header and can be reached by a backwards walk of
927 the edges starting with nodes on the initial queue.
928
929 It is safe and desirable to include those nodes in the
930 loop/scheduling region. To do so we would need to decrease
931 the degree of a node if it is the target of a backedge
932 within the loop itself as the node is placed in the queue.
933
934 We do not do this because I'm not sure that the actual
935 scheduling code will properly handle this case. ?!? */
936
937 while (head < tail && !too_large_failure)
938 {
939 edge e;
940 child = queue[++head];
941
942 for (e = BASIC_BLOCK (child)->pred; e; e = e->pred_next)
943 {
944 node = e->src->index;
945
946 /* See discussion above about nodes not marked as in
947 this loop during the initial DFS traversal. */
948 if (e->src == ENTRY_BLOCK_PTR
949 || max_hdr[node] != loop_head)
950 {
951 tail = -1;
952 break;
953 }
954 else if (!TEST_BIT (in_queue, node) && node != bb->index)
955 {
956 queue[++tail] = node;
957 SET_BIT (in_queue, node);
958
959 if (too_large (node, &num_bbs, &num_insns))
960 {
961 too_large_failure = 1;
962 break;
963 }
964 }
965 }
966 }
967
968 if (tail >= 0 && !too_large_failure)
969 {
970 /* Place the loop header into list of region blocks. */
971 degree[bb->index] = -1;
972 rgn_bb_table[idx] = bb->index;
973 RGN_NR_BLOCKS (nr_regions) = num_bbs;
974 RGN_BLOCKS (nr_regions) = idx++;
975 CONTAINING_RGN (bb->index) = nr_regions;
976 BLOCK_TO_BB (bb->index) = count = 0;
977
978 /* Remove blocks from queue[] when their in degree
979 becomes zero. Repeat until no blocks are left on the
980 list. This produces a topological list of blocks in
981 the region. */
982 while (tail >= 0)
983 {
984 if (head < 0)
985 head = tail;
986 child = queue[head];
987 if (degree[child] == 0)
988 {
989 edge e;
990
991 degree[child] = -1;
992 rgn_bb_table[idx++] = child;
993 BLOCK_TO_BB (child) = ++count;
994 CONTAINING_RGN (child) = nr_regions;
995 queue[head] = queue[tail--];
996
997 for (e = BASIC_BLOCK (child)->succ;
998 e;
999 e = e->succ_next)
1000 if (e->dest != EXIT_BLOCK_PTR)
1001 --degree[e->dest->index];
1002 }
1003 else
1004 --head;
1005 }
1006 ++nr_regions;
1007 }
1008 }
1009 }
1010 free (queue);
1011 }
1012
1013 /* Any block that did not end up in a region is placed into a region
1014 by itself. */
1015 FOR_EACH_BB (bb)
1016 if (degree[bb->index] >= 0)
1017 {
1018 rgn_bb_table[idx] = bb->index;
1019 RGN_NR_BLOCKS (nr_regions) = 1;
1020 RGN_BLOCKS (nr_regions) = idx++;
1021 CONTAINING_RGN (bb->index) = nr_regions++;
1022 BLOCK_TO_BB (bb->index) = 0;
1023 }
1024
1025 free (max_hdr);
1026 free (dfs_nr);
1027 free (stack);
1028 sbitmap_free (passed);
1029 sbitmap_free (header);
1030 sbitmap_free (inner);
1031 sbitmap_free (in_queue);
1032 sbitmap_free (in_stack);
1033}
1034
1035/* Functions for regions scheduling information. */
1036
1037/* Compute dominators, probability, and potential-split-edges of bb.
1038 Assume that these values were already computed for bb's predecessors. */
1039
1040static void
1041compute_dom_prob_ps (int bb)
1042{
1043 int nxt_in_edge, fst_in_edge, pred;
1044 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1045
1046 prob[bb] = 0.0;
1047 if (IS_RGN_ENTRY (bb))
1048 {
1049 SET_BIT (dom[bb], 0);
1050 prob[bb] = 1.0;
1051 return;
1052 }
1053
1054 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1055
1056 /* Initialize dom[bb] to '111..1'. */
1057 sbitmap_ones (dom[bb]);
1058
1059 do
1060 {
1061 pred = FROM_BLOCK (nxt_in_edge);
1062 sbitmap_a_and_b (dom[bb], dom[bb], dom[BLOCK_TO_BB (pred)]);
1063 sbitmap_a_or_b (ancestor_edges[bb], ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)]);
1064
1065 SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge));
1066
1067 nr_out_edges = 1;
1068 nr_rgn_out_edges = 0;
1069 fst_out_edge = OUT_EDGES (pred);
1070 nxt_out_edge = NEXT_OUT (fst_out_edge);
1071
1072 sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[BLOCK_TO_BB (pred)]);
1073
1074 SET_BIT (pot_split[bb], EDGE_TO_BIT (fst_out_edge));
1075
1076 /* The successor doesn't belong in the region? */
1077 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1078 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1079 ++nr_rgn_out_edges;
1080
1081 while (fst_out_edge != nxt_out_edge)
1082 {
1083 ++nr_out_edges;
1084 /* The successor doesn't belong in the region? */
1085 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1086 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1087 ++nr_rgn_out_edges;
1088 SET_BIT (pot_split[bb], EDGE_TO_BIT (nxt_out_edge));
1089 nxt_out_edge = NEXT_OUT (nxt_out_edge);
1090
1091 }
1092
1093 /* Now nr_rgn_out_edges is the number of region-exit edges from
1094 pred, and nr_out_edges will be the number of pred out edges
1095 not leaving the region. */
1096 nr_out_edges -= nr_rgn_out_edges;
1097 if (nr_rgn_out_edges > 0)
1098 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1099 else
1100 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1101 nxt_in_edge = NEXT_IN (nxt_in_edge);
1102 }
1103 while (fst_in_edge != nxt_in_edge);
1104
1105 SET_BIT (dom[bb], bb);
1106 sbitmap_difference (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
1107
1108 if (sched_verbose >= 2)
1109 fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
1110 (int) (100.0 * prob[bb]));
1111}
1112
1113/* Functions for target info. */
1114
1115/* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1116 Note that bb_trg dominates bb_src. */
1117
1118static void
1119split_edges (int bb_src, int bb_trg, edgelst *bl)
1120{
1121 sbitmap src = sbitmap_alloc (pot_split[bb_src]->n_bits);
1122 sbitmap_copy (src, pot_split[bb_src]);
1123
1124 sbitmap_difference (src, src, pot_split[bb_trg]);
1125 extract_bitlst (src, bl);
1126 sbitmap_free (src);
1127}
1128
1129/* Find the valid candidate-source-blocks for the target block TRG, compute
1130 their probability, and check if they are speculative or not.
1131 For speculative sources, compute their update-blocks and split-blocks. */
1132
1133static void
1134compute_trg_info (int trg)
1135{
1136 candidate *sp;
1137 edgelst el;
1138 int check_block, update_idx;
1139 int i, j, k, fst_edge, nxt_edge;
1140
1141 /* Define some of the fields for the target bb as well. */
1142 sp = candidate_table + trg;
1143 sp->is_valid = 1;
1144 sp->is_speculative = 0;
1145 sp->src_prob = 100;
1146
1147 for (i = trg + 1; i < current_nr_blocks; i++)
1148 {
1149 sp = candidate_table + i;
1150
1151 sp->is_valid = IS_DOMINATED (i, trg);
1152 if (sp->is_valid)
1153 {
1154 sp->src_prob = GET_SRC_PROB (i, trg);
1155 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
1156 }
1157
1158 if (sp->is_valid)
1159 {
1160 split_edges (i, trg, &el);
1161 sp->is_speculative = (el.nr_members) ? 1 : 0;
1162 if (sp->is_speculative && !flag_schedule_speculative)
1163 sp->is_valid = 0;
1164 }
1165
1166 if (sp->is_valid)
1167 {
1168 char *update_blocks;
1169
1170 /* Compute split blocks and store them in bblst_table.
1171 The TO block of every split edge is a split block. */
1172 sp->split_bbs.first_member = &bblst_table[bblst_last];
1173 sp->split_bbs.nr_members = el.nr_members;
1174 for (j = 0; j < el.nr_members; bblst_last++, j++)
1175 bblst_table[bblst_last] =
1176 TO_BLOCK (rgn_edges[el.first_member[j]]);
1177 sp->update_bbs.first_member = &bblst_table[bblst_last];
1178
1179 /* Compute update blocks and store them in bblst_table.
1180 For every split edge, look at the FROM block, and check
1181 all out edges. For each out edge that is not a split edge,
1182 add the TO block to the update block list. This list can end
1183 up with a lot of duplicates. We need to weed them out to avoid
1184 overrunning the end of the bblst_table. */
1185 update_blocks = alloca (last_basic_block);
1186 memset (update_blocks, 0, last_basic_block);
1187
1188 update_idx = 0;
1189 for (j = 0; j < el.nr_members; j++)
1190 {
1191 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
1192 fst_edge = nxt_edge = OUT_EDGES (check_block);
1193 do
1194 {
1195 if (! update_blocks[TO_BLOCK (nxt_edge)])
1196 {
1197 for (k = 0; k < el.nr_members; k++)
1198 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
1199 break;
1200
1201 if (k >= el.nr_members)
1202 {
1203 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
1204 update_blocks[TO_BLOCK (nxt_edge)] = 1;
1205 update_idx++;
1206 }
1207 }
1208
1209 nxt_edge = NEXT_OUT (nxt_edge);
1210 }
1211 while (fst_edge != nxt_edge);
1212 }
1213 sp->update_bbs.nr_members = update_idx;
1214
1215 /* Make sure we didn't overrun the end of bblst_table. */
1216 if (bblst_last > bblst_size)
1217 abort ();
1218 }
1219 else
1220 {
1221 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1222
1223 sp->is_speculative = 0;
1224 sp->src_prob = 0;
1225 }
1226 }
1227}
1228
1229/* Print candidates info, for debugging purposes. Callable from debugger. */
1230
1231void
1232debug_candidate (int i)
1233{
1234 if (!candidate_table[i].is_valid)
1235 return;
1236
1237 if (candidate_table[i].is_speculative)
1238 {
1239 int j;
1240 fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1241
1242 fprintf (sched_dump, "split path: ");
1243 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1244 {
1245 int b = candidate_table[i].split_bbs.first_member[j];
1246
1247 fprintf (sched_dump, " %d ", b);
1248 }
1249 fprintf (sched_dump, "\n");
1250
1251 fprintf (sched_dump, "update path: ");
1252 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
1253 {
1254 int b = candidate_table[i].update_bbs.first_member[j];
1255
1256 fprintf (sched_dump, " %d ", b);
1257 }
1258 fprintf (sched_dump, "\n");
1259 }
1260 else
1261 {
1262 fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
1263 }
1264}
1265
1266/* Print candidates info, for debugging purposes. Callable from debugger. */
1267
1268void
1269debug_candidates (int trg)
1270{
1271 int i;
1272
1273 fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
1274 BB_TO_BLOCK (trg), trg);
1275 for (i = trg + 1; i < current_nr_blocks; i++)
1276 debug_candidate (i);
1277}
1278
1279/* Functions for speculative scheduling. */
1280
1281/* Return 0 if x is a set of a register alive in the beginning of one
1282 of the split-blocks of src, otherwise return 1. */
1283
1284static int
1285check_live_1 (int src, rtx x)
1286{
1287 int i;
1288 int regno;
1289 rtx reg = SET_DEST (x);
1290
1291 if (reg == 0)
1292 return 1;
1293
1294 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
1295 || GET_CODE (reg) == SIGN_EXTRACT
1296 || GET_CODE (reg) == STRICT_LOW_PART)
1297 reg = XEXP (reg, 0);
1298
1299 if (GET_CODE (reg) == PARALLEL)
1300 {
1301 int i;
1302
1303 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1304 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1305 if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
1306 return 1;
1307
1308 return 0;
1309 }
1310
1311 if (GET_CODE (reg) != REG)
1312 return 1;
1313
1314 regno = REGNO (reg);
1315
1316 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1317 {
1318 /* Global registers are assumed live. */
1319 return 0;
1320 }
1321 else
1322 {
1323 if (regno < FIRST_PSEUDO_REGISTER)
1324 {
1325 /* Check for hard registers. */
1326 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1327 while (--j >= 0)
1328 {
1329 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1330 {
1331 int b = candidate_table[src].split_bbs.first_member[i];
1332
1333 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
1334 regno + j))
1335 {
1336 return 0;
1337 }
1338 }
1339 }
1340 }
1341 else
1342 {
1343 /* Check for pseudo registers. */
1344 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1345 {
1346 int b = candidate_table[src].split_bbs.first_member[i];
1347
1348 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
1349 {
1350 return 0;
1351 }
1352 }
1353 }
1354 }
1355
1356 return 1;
1357}
1358
1359/* If x is a set of a register R, mark that R is alive in the beginning
1360 of every update-block of src. */
1361
1362static void
1363update_live_1 (int src, rtx x)
1364{
1365 int i;
1366 int regno;
1367 rtx reg = SET_DEST (x);
1368
1369 if (reg == 0)
1370 return;
1371
1372 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
1373 || GET_CODE (reg) == SIGN_EXTRACT
1374 || GET_CODE (reg) == STRICT_LOW_PART)
1375 reg = XEXP (reg, 0);
1376
1377 if (GET_CODE (reg) == PARALLEL)
1378 {
1379 int i;
1380
1381 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1382 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1383 update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
1384
1385 return;
1386 }
1387
1388 if (GET_CODE (reg) != REG)
1389 return;
1390
1391 /* Global registers are always live, so the code below does not apply
1392 to them. */
1393
1394 regno = REGNO (reg);
1395
1396 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
1397 {
1398 if (regno < FIRST_PSEUDO_REGISTER)
1399 {
1400 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1401 while (--j >= 0)
1402 {
1403 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1404 {
1405 int b = candidate_table[src].update_bbs.first_member[i];
1406
1407 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
1408 regno + j);
1409 }
1410 }
1411 }
1412 else
1413 {
1414 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1415 {
1416 int b = candidate_table[src].update_bbs.first_member[i];
1417
1418 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
1419 }
1420 }
1421 }
1422}
1423
1424/* Return 1 if insn can be speculatively moved from block src to trg,
1425 otherwise return 0. Called before first insertion of insn to
1426 ready-list or before the scheduling. */
1427
1428static int
1429check_live (rtx insn, int src)
1430{
1431 /* Find the registers set by instruction. */
1432 if (GET_CODE (PATTERN (insn)) == SET
1433 || GET_CODE (PATTERN (insn)) == CLOBBER)
1434 return check_live_1 (src, PATTERN (insn));
1435 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1436 {
1437 int j;
1438 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1439 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1440 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1441 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
1442 return 0;
1443
1444 return 1;
1445 }
1446
1447 return 1;
1448}
1449
1450/* Update the live registers info after insn was moved speculatively from
1451 block src to trg. */
1452
1453static void
1454update_live (rtx insn, int src)
1455{
1456 /* Find the registers set by instruction. */
1457 if (GET_CODE (PATTERN (insn)) == SET
1458 || GET_CODE (PATTERN (insn)) == CLOBBER)
1459 update_live_1 (src, PATTERN (insn));
1460 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1461 {
1462 int j;
1463 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1464 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1465 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1466 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
1467 }
1468}
1469
1470/* Nonzero if block bb_to is equal to, or reachable from block bb_from. */
1471#define IS_REACHABLE(bb_from, bb_to) \
1472 (bb_from == bb_to \
1473 || IS_RGN_ENTRY (bb_from) \
1474 || (TEST_BIT (ancestor_edges[bb_to], \
1475 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))))))
1476
1477/* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
1478
1479static void
1480set_spec_fed (rtx load_insn)
1481{
1482 rtx link;
1483
1484 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
1485 if (GET_MODE (link) == VOIDmode)
1486 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
1487} /* set_spec_fed */
1488
1489/* On the path from the insn to load_insn_bb, find a conditional
1490branch depending on insn, that guards the speculative load. */
1491
1492static int
1493find_conditional_protection (rtx insn, int load_insn_bb)
1494{
1495 rtx link;
1496
1497 /* Iterate through DEF-USE forward dependences. */
1498 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
1499 {
1500 rtx next = XEXP (link, 0);
1501 if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
1502 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
1503 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
1504 && load_insn_bb != INSN_BB (next)
1505 && GET_MODE (link) == VOIDmode
1506 && (GET_CODE (next) == JUMP_INSN
1507 || find_conditional_protection (next, load_insn_bb)))
1508 return 1;
1509 }
1510 return 0;
1511} /* find_conditional_protection */
1512
1513/* Returns 1 if the same insn1 that participates in the computation
1514 of load_insn's address is feeding a conditional branch that is
1515 guarding on load_insn. This is true if we find a the two DEF-USE
1516 chains:
1517 insn1 -> ... -> conditional-branch
1518 insn1 -> ... -> load_insn,
1519 and if a flow path exist:
1520 insn1 -> ... -> conditional-branch -> ... -> load_insn,
1521 and if insn1 is on the path
1522 region-entry -> ... -> bb_trg -> ... load_insn.
1523
1524 Locate insn1 by climbing on LOG_LINKS from load_insn.
1525 Locate the branch by following INSN_DEPEND from insn1. */
1526
1527static int
1528is_conditionally_protected (rtx load_insn, int bb_src, int bb_trg)
1529{
1530 rtx link;
1531
1532 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
1533 {
1534 rtx insn1 = XEXP (link, 0);
1535
1536 /* Must be a DEF-USE dependence upon non-branch. */
1537 if (GET_MODE (link) != VOIDmode
1538 || GET_CODE (insn1) == JUMP_INSN)
1539 continue;
1540
1541 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
1542 if (INSN_BB (insn1) == bb_src
1543 || (CONTAINING_RGN (BLOCK_NUM (insn1))
1544 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
1545 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
1546 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
1547 continue;
1548
1549 /* Now search for the conditional-branch. */
1550 if (find_conditional_protection (insn1, bb_src))
1551 return 1;
1552
1553 /* Recursive step: search another insn1, "above" current insn1. */
1554 return is_conditionally_protected (insn1, bb_src, bb_trg);
1555 }
1556
1557 /* The chain does not exist. */
1558 return 0;
1559} /* is_conditionally_protected */
1560
1561/* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1562 load_insn can move speculatively from bb_src to bb_trg. All the
1563 following must hold:
1564
1565 (1) both loads have 1 base register (PFREE_CANDIDATEs).
1566 (2) load_insn and load1 have a def-use dependence upon
1567 the same insn 'insn1'.
1568 (3) either load2 is in bb_trg, or:
1569 - there's only one split-block, and
1570 - load1 is on the escape path, and
1571
1572 From all these we can conclude that the two loads access memory
1573 addresses that differ at most by a constant, and hence if moving
1574 load_insn would cause an exception, it would have been caused by
1575 load2 anyhow. */
1576
1577static int
1578is_pfree (rtx load_insn, int bb_src, int bb_trg)
1579{
1580 rtx back_link;
1581 candidate *candp = candidate_table + bb_src;
1582
1583 if (candp->split_bbs.nr_members != 1)
1584 /* Must have exactly one escape block. */
1585 return 0;
1586
1587 for (back_link = LOG_LINKS (load_insn);
1588 back_link; back_link = XEXP (back_link, 1))
1589 {
1590 rtx insn1 = XEXP (back_link, 0);
1591
1592 if (GET_MODE (back_link) == VOIDmode)
1593 {
1594 /* Found a DEF-USE dependence (insn1, load_insn). */
1595 rtx fore_link;
1596
1597 for (fore_link = INSN_DEPEND (insn1);
1598 fore_link; fore_link = XEXP (fore_link, 1))
1599 {
1600 rtx insn2 = XEXP (fore_link, 0);
1601 if (GET_MODE (fore_link) == VOIDmode)
1602 {
1603 /* Found a DEF-USE dependence (insn1, insn2). */
1604 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
1605 /* insn2 not guaranteed to be a 1 base reg load. */
1606 continue;
1607
1608 if (INSN_BB (insn2) == bb_trg)
1609 /* insn2 is the similar load, in the target block. */
1610 return 1;
1611
1612 if (*(candp->split_bbs.first_member) == BLOCK_NUM (insn2))
1613 /* insn2 is a similar load, in a split-block. */
1614 return 1;
1615 }
1616 }
1617 }
1618 }
1619
1620 /* Couldn't find a similar load. */
1621 return 0;
1622} /* is_pfree */
1623
1624/* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1625 a load moved speculatively, or if load_insn is protected by
1626 a compare on load_insn's address). */
1627
1628static int
1629is_prisky (rtx load_insn, int bb_src, int bb_trg)
1630{
1631 if (FED_BY_SPEC_LOAD (load_insn))
1632 return 1;
1633
1634 if (LOG_LINKS (load_insn) == NULL)
1635 /* Dependence may 'hide' out of the region. */
1636 return 1;
1637
1638 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
1639 return 1;
1640
1641 return 0;
1642}
1643
1644/* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
1645 Return 1 if insn is exception-free (and the motion is valid)
1646 and 0 otherwise. */
1647
1648static int
1649is_exception_free (rtx insn, int bb_src, int bb_trg)
1650{
1651 int insn_class = haifa_classify_insn (insn);
1652
1653 /* Handle non-load insns. */
1654 switch (insn_class)
1655 {
1656 case TRAP_FREE:
1657 return 1;
1658 case TRAP_RISKY:
1659 return 0;
1660 default:;
1661 }
1662
1663 /* Handle loads. */
1664 if (!flag_schedule_speculative_load)
1665 return 0;
1666 IS_LOAD_INSN (insn) = 1;
1667 switch (insn_class)
1668 {
1669 case IFREE:
1670 return (1);
1671 case IRISKY:
1672 return 0;
1673 case PFREE_CANDIDATE:
1674 if (is_pfree (insn, bb_src, bb_trg))
1675 return 1;
1676 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
1677 case PRISKY_CANDIDATE:
1678 if (!flag_schedule_speculative_load_dangerous
1679 || is_prisky (insn, bb_src, bb_trg))
1680 return 0;
1681 break;
1682 default:;
1683 }
1684
1685 return flag_schedule_speculative_load_dangerous;
1686}
1687\f
1688/* The number of insns from the current block scheduled so far. */
1689static int sched_target_n_insns;
1690/* The number of insns from the current block to be scheduled in total. */
1691static int target_n_insns;
1692/* The number of insns from the entire region scheduled so far. */
1693static int sched_n_insns;
1694/* Nonzero if the last scheduled insn was a jump. */
1695static int last_was_jump;
1696
1697/* Implementations of the sched_info functions for region scheduling. */
1698static void init_ready_list (struct ready_list *);
1699static int can_schedule_ready_p (rtx);
1700static int new_ready (rtx);
1701static int schedule_more_p (void);
1702static const char *rgn_print_insn (rtx, int);
1703static int rgn_rank (rtx, rtx);
1704static int contributes_to_priority (rtx, rtx);
1705static void compute_jump_reg_dependencies (rtx, regset, regset, regset);
1706
1707/* Return nonzero if there are more insns that should be scheduled. */
1708
1709static int
1710schedule_more_p (void)
1711{
1712 return ! last_was_jump && sched_target_n_insns < target_n_insns;
1713}
1714
1715/* Add all insns that are initially ready to the ready list READY. Called
1716 once before scheduling a set of insns. */
1717
1718static void
1719init_ready_list (struct ready_list *ready)
1720{
1721 rtx prev_head = current_sched_info->prev_head;
1722 rtx next_tail = current_sched_info->next_tail;
1723 int bb_src;
1724 rtx insn;
1725
1726 target_n_insns = 0;
1727 sched_target_n_insns = 0;
1728 sched_n_insns = 0;
1729 last_was_jump = 0;
1730
1731 /* Print debugging information. */
1732 if (sched_verbose >= 5)
1733 debug_dependencies ();
1734
1735 /* Prepare current target block info. */
1736 if (current_nr_blocks > 1)
1737 {
1738 candidate_table = xmalloc (current_nr_blocks * sizeof (candidate));
1739
1740 bblst_last = 0;
1741 /* bblst_table holds split blocks and update blocks for each block after
1742 the current one in the region. split blocks and update blocks are
1743 the TO blocks of region edges, so there can be at most rgn_nr_edges
1744 of them. */
1745 bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
1746 bblst_table = xmalloc (bblst_size * sizeof (int));
1747
1748 bitlst_table_last = 0;
1749 bitlst_table = xmalloc (rgn_nr_edges * sizeof (int));
1750
1751 compute_trg_info (target_bb);
1752 }
1753
1754 /* Initialize ready list with all 'ready' insns in target block.
1755 Count number of insns in the target block being scheduled. */
1756 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
1757 {
1758 if (INSN_DEP_COUNT (insn) == 0)
1759 {
1760 ready_add (ready, insn);
1761
1762 if (targetm.sched.adjust_priority)
1763 INSN_PRIORITY (insn) =
1764 (*targetm.sched.adjust_priority) (insn, INSN_PRIORITY (insn));
1765 }
1766 target_n_insns++;
1767 }
1768
1769 /* Add to ready list all 'ready' insns in valid source blocks.
1770 For speculative insns, check-live, exception-free, and
1771 issue-delay. */
1772 for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
1773 if (IS_VALID (bb_src))
1774 {
1775 rtx src_head;
1776 rtx src_next_tail;
1777 rtx tail, head;
1778
1779 get_block_head_tail (BB_TO_BLOCK (bb_src), &head, &tail);
1780 src_next_tail = NEXT_INSN (tail);
1781 src_head = head;
1782
1783 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
1784 {
1785 if (! INSN_P (insn))
1786 continue;
1787
1788 if (!CANT_MOVE (insn)
1789 && (!IS_SPECULATIVE_INSN (insn)
1790 || ((((!targetm.sched.use_dfa_pipeline_interface
1791 || !(*targetm.sched.use_dfa_pipeline_interface) ())
1792 && insn_issue_delay (insn) <= 3)
1793 || (targetm.sched.use_dfa_pipeline_interface
1794 && (*targetm.sched.use_dfa_pipeline_interface) ()
1795 && (recog_memoized (insn) < 0
1796 || min_insn_conflict_delay (curr_state,
1797 insn, insn) <= 3)))
1798 && check_live (insn, bb_src)
1799 && is_exception_free (insn, bb_src, target_bb))))
1800 if (INSN_DEP_COUNT (insn) == 0)
1801 {
1802 ready_add (ready, insn);
1803
1804 if (targetm.sched.adjust_priority)
1805 INSN_PRIORITY (insn) =
1806 (*targetm.sched.adjust_priority) (insn, INSN_PRIORITY (insn));
1807 }
1808 }
1809 }
1810}
1811
1812/* Called after taking INSN from the ready list. Returns nonzero if this
1813 insn can be scheduled, nonzero if we should silently discard it. */
1814
1815static int
1816can_schedule_ready_p (rtx insn)
1817{
1818 if (GET_CODE (insn) == JUMP_INSN)
1819 last_was_jump = 1;
1820
1821 /* An interblock motion? */
1822 if (INSN_BB (insn) != target_bb)
1823 {
1824 basic_block b1;
1825
1826 if (IS_SPECULATIVE_INSN (insn))
1827 {
1828 if (!check_live (insn, INSN_BB (insn)))
1829 return 0;
1830 update_live (insn, INSN_BB (insn));
1831
1832 /* For speculative load, mark insns fed by it. */
1833 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
1834 set_spec_fed (insn);
1835
1836 nr_spec++;
1837 }
1838 nr_inter++;
1839
1840 /* Update source block boundaries. */
1841 b1 = BLOCK_FOR_INSN (insn);
1842 if (insn == BB_HEAD (b1) && insn == BB_END (b1))
1843 {
1844 /* We moved all the insns in the basic block.
1845 Emit a note after the last insn and update the
1846 begin/end boundaries to point to the note. */
1847 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
1848 BB_HEAD (b1) = note;
1849 BB_END (b1) = note;
1850 }
1851 else if (insn == BB_END (b1))
1852 {
1853 /* We took insns from the end of the basic block,
1854 so update the end of block boundary so that it
1855 points to the first insn we did not move. */
1856 BB_END (b1) = PREV_INSN (insn);
1857 }
1858 else if (insn == BB_HEAD (b1))
1859 {
1860 /* We took insns from the start of the basic block,
1861 so update the start of block boundary so that
1862 it points to the first insn we did not move. */
1863 BB_HEAD (b1) = NEXT_INSN (insn);
1864 }
1865 }
1866 else
1867 {
1868 /* In block motion. */
1869 sched_target_n_insns++;
1870 }
1871 sched_n_insns++;
1872
1873 return 1;
1874}
1875
1876/* Called after INSN has all its dependencies resolved. Return nonzero
1877 if it should be moved to the ready list or the queue, or zero if we
1878 should silently discard it. */
1879static int
1880new_ready (rtx next)
1881{
1882 /* For speculative insns, before inserting to ready/queue,
1883 check live, exception-free, and issue-delay. */
1884 if (INSN_BB (next) != target_bb
1885 && (!IS_VALID (INSN_BB (next))
1886 || CANT_MOVE (next)
1887 || (IS_SPECULATIVE_INSN (next)
1888 && (0
1889 || (targetm.sched.use_dfa_pipeline_interface
1890 && (*targetm.sched.use_dfa_pipeline_interface) ()
1891 && recog_memoized (next) >= 0
1892 && min_insn_conflict_delay (curr_state, next,
1893 next) > 3)
1894 || ((!targetm.sched.use_dfa_pipeline_interface
1895 || !(*targetm.sched.use_dfa_pipeline_interface) ())
1896 && insn_issue_delay (next) > 3)
1897 || !check_live (next, INSN_BB (next))
1898 || !is_exception_free (next, INSN_BB (next), target_bb)))))
1899 return 0;
1900 return 1;
1901}
1902
1903/* Return a string that contains the insn uid and optionally anything else
1904 necessary to identify this insn in an output. It's valid to use a
1905 static buffer for this. The ALIGNED parameter should cause the string
1906 to be formatted so that multiple output lines will line up nicely. */
1907
1908static const char *
1909rgn_print_insn (rtx insn, int aligned)
1910{
1911 static char tmp[80];
1912
1913 if (aligned)
1914 sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
1915 else
1916 {
1917 if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
1918 sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
1919 else
1920 sprintf (tmp, "%d", INSN_UID (insn));
1921 }
1922 return tmp;
1923}
1924
1925/* Compare priority of two insns. Return a positive number if the second
1926 insn is to be preferred for scheduling, and a negative one if the first
1927 is to be preferred. Zero if they are equally good. */
1928
1929static int
1930rgn_rank (rtx insn1, rtx insn2)
1931{
1932 /* Some comparison make sense in interblock scheduling only. */
1933 if (INSN_BB (insn1) != INSN_BB (insn2))
1934 {
1935 int spec_val, prob_val;
1936
1937 /* Prefer an inblock motion on an interblock motion. */
1938 if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
1939 return 1;
1940 if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
1941 return -1;
1942
1943 /* Prefer a useful motion on a speculative one. */
1944 spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
1945 if (spec_val)
1946 return spec_val;
1947
1948 /* Prefer a more probable (speculative) insn. */
1949 prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
1950 if (prob_val)
1951 return prob_val;
1952 }
1953 return 0;
1954}
1955
1956/* NEXT is an instruction that depends on INSN (a backward dependence);
1957 return nonzero if we should include this dependence in priority
1958 calculations. */
1959
1960static int
1961contributes_to_priority (rtx next, rtx insn)
1962{
1963 return BLOCK_NUM (next) == BLOCK_NUM (insn);
1964}
1965
1966/* INSN is a JUMP_INSN, COND_SET is the set of registers that are
1967 conditionally set before INSN. Store the set of registers that
1968 must be considered as used by this jump in USED and that of
1969 registers that must be considered as set in SET. */
1970
1971static void
1972compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
1973 regset cond_exec ATTRIBUTE_UNUSED,
1974 regset used ATTRIBUTE_UNUSED,
1975 regset set ATTRIBUTE_UNUSED)
1976{
1977 /* Nothing to do here, since we postprocess jumps in
1978 add_branch_dependences. */
1979}
1980
1981/* Used in schedule_insns to initialize current_sched_info for scheduling
1982 regions (or single basic blocks). */
1983
1984static struct sched_info region_sched_info =
1985{
1986 init_ready_list,
1987 can_schedule_ready_p,
1988 schedule_more_p,
1989 new_ready,
1990 rgn_rank,
1991 rgn_print_insn,
1992 contributes_to_priority,
1993 compute_jump_reg_dependencies,
1994
1995 NULL, NULL,
1996 NULL, NULL,
1997 0, 0, 0
1998};
1999
2000/* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register. */
2001
2002static bool
2003sets_likely_spilled (rtx pat)
2004{
2005 bool ret = false;
2006 note_stores (pat, sets_likely_spilled_1, &ret);
2007 return ret;
2008}
2009
2010static void
2011sets_likely_spilled_1 (rtx x, rtx pat, void *data)
2012{
2013 bool *ret = (bool *) data;
2014
2015 if (GET_CODE (pat) == SET
2016 && REG_P (x)
2017 && REGNO (x) < FIRST_PSEUDO_REGISTER
2018 && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x))))
2019 *ret = true;
2020}
2021
2022/* Add dependences so that branches are scheduled to run last in their
2023 block. */
2024
2025static void
2026add_branch_dependences (rtx head, rtx tail)
2027{
2028 rtx insn, last;
2029
2030 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2031 that can throw exceptions, force them to remain in order at the end of
2032 the block by adding dependencies and giving the last a high priority.
2033 There may be notes present, and prev_head may also be a note.
2034
2035 Branches must obviously remain at the end. Calls should remain at the
2036 end since moving them results in worse register allocation. Uses remain
2037 at the end to ensure proper register allocation.
2038
2039 cc0 setters remain at the end because they can't be moved away from
2040 their cc0 user.
2041
2042 Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values)
2043 are not moved before reload because we can wind up with register
2044 allocation failures. */
2045
2046 insn = tail;
2047 last = 0;
2048 while (GET_CODE (insn) == CALL_INSN
2049 || GET_CODE (insn) == JUMP_INSN
2050 || (GET_CODE (insn) == INSN
2051 && (GET_CODE (PATTERN (insn)) == USE
2052 || GET_CODE (PATTERN (insn)) == CLOBBER
2053 || can_throw_internal (insn)
2054#ifdef HAVE_cc0
2055 || sets_cc0_p (PATTERN (insn))
2056#endif
2057 || (!reload_completed
2058 && sets_likely_spilled (PATTERN (insn)))))
2059 || GET_CODE (insn) == NOTE)
2060 {
2061 if (GET_CODE (insn) != NOTE)
2062 {
2063 if (last != 0 && !find_insn_list (insn, LOG_LINKS (last)))
2064 {
2065 add_dependence (last, insn, REG_DEP_ANTI);
2066 INSN_REF_COUNT (insn)++;
2067 }
2068
2069 CANT_MOVE (insn) = 1;
2070
2071 last = insn;
2072 }
2073
2074 /* Don't overrun the bounds of the basic block. */
2075 if (insn == head)
2076 break;
2077
2078 insn = PREV_INSN (insn);
2079 }
2080
1378ea41
SS
2081#ifdef HAVE_cc0
2082 /* There may be other cc0 setters earlier on in this block.
2083 Look for them and include them in the set not to be disturbed. */
2084 if (insn != head && last != NULL_RTX)
2085 {
2086 rtx earlier_cc0_setter = NULL_RTX;
2087
2088 for (insn = last; insn != NULL_RTX && insn != head;)
2089 {
2090 insn = prev_nonnote_insn (insn);
2091 if (sets_cc0_p (insn))
2092 earlier_cc0_setter = insn;
2093 }
2094
2095 if (earlier_cc0_setter != NULL_RTX)
2096 {
2097 insn = last;
2098 do
2099 {
2100 insn = prev_nonnote_insn (insn);
2101
2102 if (last != 0 && ! find_insn_list (insn, LOG_LINKS (last)))
2103 {
2104 add_dependence (last, insn, REG_DEP_ANTI);
2105 INSN_REF_COUNT (insn)++;
2106 }
2107
2108 CANT_MOVE (insn) = 1;
2109
2110 last = insn;
2111 }
2112 while (insn != earlier_cc0_setter);
2113 }
2114 }
2115#endif
2116
003757ed
MD
2117 /* Make sure these insns are scheduled last in their block. */
2118 insn = last;
2119 if (insn != 0)
2120 while (insn != head)
2121 {
2122 insn = prev_nonnote_insn (insn);
2123
2124 if (INSN_REF_COUNT (insn) != 0)
2125 continue;
2126
2127 add_dependence (last, insn, REG_DEP_ANTI);
2128 INSN_REF_COUNT (insn) = 1;
2129 }
2130}
2131
2132/* Data structures for the computation of data dependences in a regions. We
2133 keep one `deps' structure for every basic block. Before analyzing the
2134 data dependences for a bb, its variables are initialized as a function of
2135 the variables of its predecessors. When the analysis for a bb completes,
2136 we save the contents to the corresponding bb_deps[bb] variable. */
2137
2138static struct deps *bb_deps;
2139
2140/* Duplicate the INSN_LIST elements of COPY and prepend them to OLD. */
2141
2142static rtx
2143concat_INSN_LIST (rtx copy, rtx old)
2144{
2145 rtx new = old;
2146 for (; copy ; copy = XEXP (copy, 1))
2147 new = alloc_INSN_LIST (XEXP (copy, 0), new);
2148 return new;
2149}
2150
2151static void
2152concat_insn_mem_list (rtx copy_insns, rtx copy_mems, rtx *old_insns_p,
2153 rtx *old_mems_p)
2154{
2155 rtx new_insns = *old_insns_p;
2156 rtx new_mems = *old_mems_p;
2157
2158 while (copy_insns)
2159 {
2160 new_insns = alloc_INSN_LIST (XEXP (copy_insns, 0), new_insns);
2161 new_mems = alloc_EXPR_LIST (VOIDmode, XEXP (copy_mems, 0), new_mems);
2162 copy_insns = XEXP (copy_insns, 1);
2163 copy_mems = XEXP (copy_mems, 1);
2164 }
2165
2166 *old_insns_p = new_insns;
2167 *old_mems_p = new_mems;
2168}
2169
2170/* After computing the dependencies for block BB, propagate the dependencies
2171 found in TMP_DEPS to the successors of the block. */
2172static void
2173propagate_deps (int bb, struct deps *pred_deps)
2174{
2175 int b = BB_TO_BLOCK (bb);
2176 int e, first_edge;
2177
2178 /* bb's structures are inherited by its successors. */
2179 first_edge = e = OUT_EDGES (b);
2180 if (e > 0)
2181 do
2182 {
2183 int b_succ = TO_BLOCK (e);
2184 int bb_succ = BLOCK_TO_BB (b_succ);
2185 struct deps *succ_deps = bb_deps + bb_succ;
2186 int reg;
2187
2188 /* Only bbs "below" bb, in the same region, are interesting. */
2189 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
2190 || bb_succ <= bb)
2191 {
2192 e = NEXT_OUT (e);
2193 continue;
2194 }
2195
2196 /* The reg_last lists are inherited by bb_succ. */
2197 EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg,
2198 {
2199 struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
2200 struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
2201
2202 succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
2203 succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
2204 succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
2205 succ_rl->clobbers);
2206 succ_rl->uses_length += pred_rl->uses_length;
2207 succ_rl->clobbers_length += pred_rl->clobbers_length;
2208 });
2209 IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
2210
2211 /* Mem read/write lists are inherited by bb_succ. */
2212 concat_insn_mem_list (pred_deps->pending_read_insns,
2213 pred_deps->pending_read_mems,
2214 &succ_deps->pending_read_insns,
2215 &succ_deps->pending_read_mems);
2216 concat_insn_mem_list (pred_deps->pending_write_insns,
2217 pred_deps->pending_write_mems,
2218 &succ_deps->pending_write_insns,
2219 &succ_deps->pending_write_mems);
2220
2221 succ_deps->last_pending_memory_flush
2222 = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
2223 succ_deps->last_pending_memory_flush);
2224
2225 succ_deps->pending_lists_length += pred_deps->pending_lists_length;
2226 succ_deps->pending_flush_length += pred_deps->pending_flush_length;
2227
2228 /* last_function_call is inherited by bb_succ. */
2229 succ_deps->last_function_call
2230 = concat_INSN_LIST (pred_deps->last_function_call,
2231 succ_deps->last_function_call);
2232
2233 /* sched_before_next_call is inherited by bb_succ. */
2234 succ_deps->sched_before_next_call
2235 = concat_INSN_LIST (pred_deps->sched_before_next_call,
2236 succ_deps->sched_before_next_call);
2237
2238 e = NEXT_OUT (e);
2239 }
2240 while (e != first_edge);
2241
2242 /* These lists should point to the right place, for correct
2243 freeing later. */
2244 bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
2245 bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
2246 bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
2247 bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
2248
2249 /* Can't allow these to be freed twice. */
2250 pred_deps->pending_read_insns = 0;
2251 pred_deps->pending_read_mems = 0;
2252 pred_deps->pending_write_insns = 0;
2253 pred_deps->pending_write_mems = 0;
2254}
2255
2256/* Compute backward dependences inside bb. In a multiple blocks region:
2257 (1) a bb is analyzed after its predecessors, and (2) the lists in
2258 effect at the end of bb (after analyzing for bb) are inherited by
2259 bb's successors.
2260
2261 Specifically for reg-reg data dependences, the block insns are
2262 scanned by sched_analyze () top-to-bottom. Two lists are
2263 maintained by sched_analyze (): reg_last[].sets for register DEFs,
2264 and reg_last[].uses for register USEs.
2265
2266 When analysis is completed for bb, we update for its successors:
2267 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2268 ; - USES[succ] = Union (USES [succ], DEFS [bb])
2269
2270 The mechanism for computing mem-mem data dependence is very
2271 similar, and the result is interblock dependences in the region. */
2272
2273static void
2274compute_block_backward_dependences (int bb)
2275{
2276 rtx head, tail;
2277 struct deps tmp_deps;
2278
2279 tmp_deps = bb_deps[bb];
2280
2281 /* Do the analysis for this block. */
2282 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2283 sched_analyze (&tmp_deps, head, tail);
2284 add_branch_dependences (head, tail);
2285
2286 if (current_nr_blocks > 1)
2287 propagate_deps (bb, &tmp_deps);
2288
2289 /* Free up the INSN_LISTs. */
2290 free_deps (&tmp_deps);
2291}
2292
2293/* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2294 them to the unused_*_list variables, so that they can be reused. */
2295
2296static void
2297free_pending_lists (void)
2298{
2299 int bb;
2300
2301 for (bb = 0; bb < current_nr_blocks; bb++)
2302 {
2303 free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
2304 free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
2305 free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
2306 free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
2307 }
2308}
2309\f
2310/* Print dependences for debugging, callable from debugger. */
2311
2312void
2313debug_dependencies (void)
2314{
2315 int bb;
2316
2317 fprintf (sched_dump, ";; --------------- forward dependences: ------------ \n");
2318 for (bb = 0; bb < current_nr_blocks; bb++)
2319 {
2320 if (1)
2321 {
2322 rtx head, tail;
2323 rtx next_tail;
2324 rtx insn;
2325
2326 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2327 next_tail = NEXT_INSN (tail);
2328 fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
2329 BB_TO_BLOCK (bb), bb);
2330
2331 if (targetm.sched.use_dfa_pipeline_interface
2332 && (*targetm.sched.use_dfa_pipeline_interface) ())
2333 {
2334 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2335 "insn", "code", "bb", "dep", "prio", "cost",
2336 "reservation");
2337 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n",
2338 "----", "----", "--", "---", "----", "----",
2339 "-----------");
2340 }
2341 else
2342 {
2343 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
2344 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
2345 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
2346 "----", "----", "--", "---", "----", "----", "--------", "-----");
2347 }
2348
2349 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2350 {
2351 rtx link;
2352
2353 if (! INSN_P (insn))
2354 {
2355 int n;
2356 fprintf (sched_dump, ";; %6d ", INSN_UID (insn));
2357 if (GET_CODE (insn) == NOTE)
2358 {
2359 n = NOTE_LINE_NUMBER (insn);
2360 if (n < 0)
2361 fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
2362 else
2363 fprintf (sched_dump, "line %d, file %s\n", n,
2364 NOTE_SOURCE_FILE (insn));
2365 }
2366 else
2367 fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
2368 continue;
2369 }
2370
2371 if (targetm.sched.use_dfa_pipeline_interface
2372 && (*targetm.sched.use_dfa_pipeline_interface) ())
2373 {
2374 fprintf (sched_dump,
2375 ";; %s%5d%6d%6d%6d%6d%6d ",
2376 (SCHED_GROUP_P (insn) ? "+" : " "),
2377 INSN_UID (insn),
2378 INSN_CODE (insn),
2379 INSN_BB (insn),
2380 INSN_DEP_COUNT (insn),
2381 INSN_PRIORITY (insn),
2382 insn_cost (insn, 0, 0));
2383
2384 if (recog_memoized (insn) < 0)
2385 fprintf (sched_dump, "nothing");
2386 else
2387 print_reservation (sched_dump, insn);
2388 }
2389 else
2390 {
2391 int unit = insn_unit (insn);
2392 int range
2393 = (unit < 0
2394 || function_units[unit].blockage_range_function == 0
2395 ? 0
2396 : function_units[unit].blockage_range_function (insn));
2397 fprintf (sched_dump,
2398 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
2399 (SCHED_GROUP_P (insn) ? "+" : " "),
2400 INSN_UID (insn),
2401 INSN_CODE (insn),
2402 INSN_BB (insn),
2403 INSN_DEP_COUNT (insn),
2404 INSN_PRIORITY (insn),
2405 insn_cost (insn, 0, 0),
2406 (int) MIN_BLOCKAGE_COST (range),
2407 (int) MAX_BLOCKAGE_COST (range));
2408 insn_print_units (insn);
2409 }
2410
2411 fprintf (sched_dump, "\t: ");
2412 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2413 fprintf (sched_dump, "%d ", INSN_UID (XEXP (link, 0)));
2414 fprintf (sched_dump, "\n");
2415 }
2416 }
2417 }
2418 fprintf (sched_dump, "\n");
2419}
2420\f
2421/* Schedule a region. A region is either an inner loop, a loop-free
2422 subroutine, or a single basic block. Each bb in the region is
2423 scheduled after its flow predecessors. */
2424
2425static void
2426schedule_region (int rgn)
2427{
2428 int bb;
2429 int rgn_n_insns = 0;
2430 int sched_rgn_n_insns = 0;
2431
2432 /* Set variables for the current region. */
2433 current_nr_blocks = RGN_NR_BLOCKS (rgn);
2434 current_blocks = RGN_BLOCKS (rgn);
2435
2436 init_deps_global ();
2437
2438 /* Initializations for region data dependence analysis. */
2439 bb_deps = xmalloc (sizeof (struct deps) * current_nr_blocks);
2440 for (bb = 0; bb < current_nr_blocks; bb++)
2441 init_deps (bb_deps + bb);
2442
2443 /* Compute LOG_LINKS. */
2444 for (bb = 0; bb < current_nr_blocks; bb++)
2445 compute_block_backward_dependences (bb);
2446
2447 /* Compute INSN_DEPEND. */
2448 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
2449 {
2450 rtx head, tail;
2451 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2452
2453 compute_forward_dependences (head, tail);
2454
2455 if (targetm.sched.dependencies_evaluation_hook)
2456 targetm.sched.dependencies_evaluation_hook (head, tail);
2457
2458 }
2459
2460 /* Set priorities. */
2461 for (bb = 0; bb < current_nr_blocks; bb++)
2462 {
2463 rtx head, tail;
2464 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2465
2466 rgn_n_insns += set_priorities (head, tail);
2467 }
2468
2469 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
2470 if (current_nr_blocks > 1)
2471 {
2472 int i;
2473
2474 prob = xmalloc ((current_nr_blocks) * sizeof (float));
2475
2476 dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
2477 sbitmap_vector_zero (dom, current_nr_blocks);
2478 /* Edge to bit. */
2479 rgn_nr_edges = 0;
2480 edge_to_bit = xmalloc (nr_edges * sizeof (int));
2481 for (i = 1; i < nr_edges; i++)
2482 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
2483 EDGE_TO_BIT (i) = rgn_nr_edges++;
2484 rgn_edges = xmalloc (rgn_nr_edges * sizeof (int));
2485
2486 rgn_nr_edges = 0;
2487 for (i = 1; i < nr_edges; i++)
2488 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
2489 rgn_edges[rgn_nr_edges++] = i;
2490
2491 /* Split edges. */
2492 pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2493 sbitmap_vector_zero (pot_split, current_nr_blocks);
2494 ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2495 sbitmap_vector_zero (ancestor_edges, current_nr_blocks);
2496
2497 /* Compute probabilities, dominators, split_edges. */
2498 for (bb = 0; bb < current_nr_blocks; bb++)
2499 compute_dom_prob_ps (bb);
2500 }
2501
2502 /* Now we can schedule all blocks. */
2503 for (bb = 0; bb < current_nr_blocks; bb++)
2504 {
2505 rtx head, tail;
2506 int b = BB_TO_BLOCK (bb);
2507
2508 get_block_head_tail (b, &head, &tail);
2509
2510 if (no_real_insns_p (head, tail))
2511 continue;
2512
2513 current_sched_info->prev_head = PREV_INSN (head);
2514 current_sched_info->next_tail = NEXT_INSN (tail);
2515
2516 if (write_symbols != NO_DEBUG)
2517 {
2518 save_line_notes (b, head, tail);
2519 rm_line_notes (head, tail);
2520 }
2521
2522 /* rm_other_notes only removes notes which are _inside_ the
2523 block---that is, it won't remove notes before the first real insn
2524 or after the last real insn of the block. So if the first insn
2525 has a REG_SAVE_NOTE which would otherwise be emitted before the
2526 insn, it is redundant with the note before the start of the
2527 block, and so we have to take it out. */
2528 if (INSN_P (head))
2529 {
2530 rtx note;
2531
2532 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
2533 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
2534 {
2535 remove_note (head, note);
2536 note = XEXP (note, 1);
2537 remove_note (head, note);
2538 }
2539 }
2540
2541 /* Remove remaining note insns from the block, save them in
2542 note_list. These notes are restored at the end of
2543 schedule_block (). */
2544 rm_other_notes (head, tail);
2545
2546 target_bb = bb;
2547
2548 current_sched_info->queue_must_finish_empty
2549 = current_nr_blocks > 1 && !flag_schedule_interblock;
2550
2551 schedule_block (b, rgn_n_insns);
2552 sched_rgn_n_insns += sched_n_insns;
2553
2554 /* Update target block boundaries. */
2555 if (head == BB_HEAD (BASIC_BLOCK (b)))
2556 BB_HEAD (BASIC_BLOCK (b)) = current_sched_info->head;
2557 if (tail == BB_END (BASIC_BLOCK (b)))
2558 BB_END (BASIC_BLOCK (b)) = current_sched_info->tail;
2559
2560 /* Clean up. */
2561 if (current_nr_blocks > 1)
2562 {
2563 free (candidate_table);
2564 free (bblst_table);
2565 free (bitlst_table);
2566 }
2567 }
2568
2569 /* Sanity check: verify that all region insns were scheduled. */
2570 if (sched_rgn_n_insns != rgn_n_insns)
2571 abort ();
2572
2573 /* Restore line notes. */
2574 if (write_symbols != NO_DEBUG)
2575 {
2576 for (bb = 0; bb < current_nr_blocks; bb++)
2577 {
2578 rtx head, tail;
2579 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2580 restore_line_notes (head, tail);
2581 }
2582 }
2583
2584 /* Done with this region. */
2585 free_pending_lists ();
2586
2587 finish_deps_global ();
2588
2589 free (bb_deps);
2590
2591 if (current_nr_blocks > 1)
2592 {
2593 free (prob);
2594 sbitmap_vector_free (dom);
2595 sbitmap_vector_free (pot_split);
2596 sbitmap_vector_free (ancestor_edges);
2597 free (edge_to_bit);
2598 free (rgn_edges);
2599 }
2600}
2601
2602/* Indexed by region, holds the number of death notes found in that region.
2603 Used for consistency checks. */
2604static int *deaths_in_region;
2605
2606/* Initialize data structures for region scheduling. */
2607
2608static void
2609init_regions (void)
2610{
2611 sbitmap blocks;
2612 int rgn;
2613
2614 nr_regions = 0;
2615 rgn_table = xmalloc ((n_basic_blocks) * sizeof (region));
2616 rgn_bb_table = xmalloc ((n_basic_blocks) * sizeof (int));
2617 block_to_bb = xmalloc ((last_basic_block) * sizeof (int));
2618 containing_rgn = xmalloc ((last_basic_block) * sizeof (int));
2619
2620 /* Compute regions for scheduling. */
2621 if (reload_completed
2622 || n_basic_blocks == 1
2623 || !flag_schedule_interblock)
2624 {
2625 find_single_block_region ();
2626 }
2627 else
2628 {
2629 /* Verify that a 'good' control flow graph can be built. */
2630 if (is_cfg_nonregular ())
2631 {
2632 find_single_block_region ();
2633 }
2634 else
2635 {
2636 struct edge_list *edge_list;
2637
2638 /* The scheduler runs after estimate_probabilities; therefore, we
2639 can't blindly call back into find_basic_blocks since doing so
2640 could invalidate the branch probability info. We could,
2641 however, call cleanup_cfg. */
2642 edge_list = create_edge_list ();
2643
2644 /* Compute the dominators and post dominators. */
2645 calculate_dominance_info (CDI_DOMINATORS);
2646
2647 /* build_control_flow will return nonzero if it detects unreachable
2648 blocks or any other irregularity with the cfg which prevents
2649 cross block scheduling. */
2650 if (build_control_flow (edge_list) != 0)
2651 find_single_block_region ();
2652 else
2653 find_rgns (edge_list);
2654
2655 if (sched_verbose >= 3)
2656 debug_regions ();
2657
2658 /* We are done with flow's edge list. */
2659 free_edge_list (edge_list);
2660
2661 /* For now. This will move as more and more of haifa is converted
2662 to using the cfg code in flow.c. */
2663 free_dominance_info (CDI_DOMINATORS);
2664 }
2665 }
2666
2667
2668 if (CHECK_DEAD_NOTES)
2669 {
2670 blocks = sbitmap_alloc (last_basic_block);
2671 deaths_in_region = xmalloc (sizeof (int) * nr_regions);
2672 /* Remove all death notes from the subroutine. */
2673 for (rgn = 0; rgn < nr_regions; rgn++)
2674 {
2675 int b;
2676
2677 sbitmap_zero (blocks);
2678 for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
2679 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]);
2680
2681 deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1);
2682 }
2683 sbitmap_free (blocks);
2684 }
2685 else
2686 count_or_remove_death_notes (NULL, 1);
2687}
2688
2689/* The one entry point in this file. DUMP_FILE is the dump file for
2690 this pass. */
2691
2692void
2693schedule_insns (FILE *dump_file)
2694{
2695 sbitmap large_region_blocks, blocks;
2696 int rgn;
2697 int any_large_regions;
2698 basic_block bb;
2699
2700 /* Taking care of this degenerate case makes the rest of
2701 this code simpler. */
2702 if (n_basic_blocks == 0)
2703 return;
2704
2705 nr_inter = 0;
2706 nr_spec = 0;
2707
2708 sched_init (dump_file);
2709
2710 init_regions ();
2711
2712 current_sched_info = &region_sched_info;
2713
2714 /* Schedule every region in the subroutine. */
2715 for (rgn = 0; rgn < nr_regions; rgn++)
2716 schedule_region (rgn);
2717
2718 /* Update life analysis for the subroutine. Do single block regions
2719 first so that we can verify that live_at_start didn't change. Then
2720 do all other blocks. */
2721 /* ??? There is an outside possibility that update_life_info, or more
2722 to the point propagate_block, could get called with nonzero flags
2723 more than once for one basic block. This would be kinda bad if it
2724 were to happen, since REG_INFO would be accumulated twice for the
2725 block, and we'd have twice the REG_DEAD notes.
2726
2727 I'm fairly certain that this _shouldn't_ happen, since I don't think
2728 that live_at_start should change at region heads. Not sure what the
2729 best way to test for this kind of thing... */
2730
2731 allocate_reg_life_data ();
2732 compute_bb_for_insn ();
2733
2734 any_large_regions = 0;
2735 large_region_blocks = sbitmap_alloc (last_basic_block);
2736 sbitmap_zero (large_region_blocks);
2737 FOR_EACH_BB (bb)
2738 SET_BIT (large_region_blocks, bb->index);
2739
2740 blocks = sbitmap_alloc (last_basic_block);
2741 sbitmap_zero (blocks);
2742
2743 /* Update life information. For regions consisting of multiple blocks
2744 we've possibly done interblock scheduling that affects global liveness.
2745 For regions consisting of single blocks we need to do only local
2746 liveness. */
2747 for (rgn = 0; rgn < nr_regions; rgn++)
2748 if (RGN_NR_BLOCKS (rgn) > 1)
2749 any_large_regions = 1;
2750 else
2751 {
2752 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2753 RESET_BIT (large_region_blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2754 }
2755
2756 /* Don't update reg info after reload, since that affects
2757 regs_ever_live, which should not change after reload. */
2758 update_life_info (blocks, UPDATE_LIFE_LOCAL,
2759 (reload_completed ? PROP_DEATH_NOTES
2760 : PROP_DEATH_NOTES | PROP_REG_INFO));
2761 if (any_large_regions)
2762 {
2763 update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL,
2764 PROP_DEATH_NOTES | PROP_REG_INFO);
2765 }
2766
2767 if (CHECK_DEAD_NOTES)
2768 {
2769 /* Verify the counts of basic block notes in single the basic block
2770 regions. */
2771 for (rgn = 0; rgn < nr_regions; rgn++)
2772 if (RGN_NR_BLOCKS (rgn) == 1)
2773 {
2774 sbitmap_zero (blocks);
2775 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
2776
2777 if (deaths_in_region[rgn]
2778 != count_or_remove_death_notes (blocks, 0))
2779 abort ();
2780 }
2781 free (deaths_in_region);
2782 }
2783
2784 /* Reposition the prologue and epilogue notes in case we moved the
2785 prologue/epilogue insns. */
2786 if (reload_completed)
2787 reposition_prologue_and_epilogue_notes (get_insns ());
2788
2789 /* Delete redundant line notes. */
2790 if (write_symbols != NO_DEBUG)
2791 rm_redundant_line_notes ();
2792
2793 if (sched_verbose)
2794 {
2795 if (reload_completed == 0 && flag_schedule_interblock)
2796 {
2797 fprintf (sched_dump,
2798 "\n;; Procedure interblock/speculative motions == %d/%d \n",
2799 nr_inter, nr_spec);
2800 }
2801 else
2802 {
2803 if (nr_inter > 0)
2804 abort ();
2805 }
2806 fprintf (sched_dump, "\n\n");
2807 }
2808
2809 /* Clean up. */
2810 free (rgn_table);
2811 free (rgn_bb_table);
2812 free (block_to_bb);
2813 free (containing_rgn);
2814
2815 sched_finish ();
2816
2817 if (edge_table)
2818 {
2819 free (edge_table);
2820 edge_table = NULL;
2821 }
2822
2823 if (in_edges)
2824 {
2825 free (in_edges);
2826 in_edges = NULL;
2827 }
2828 if (out_edges)
2829 {
2830 free (out_edges);
2831 out_edges = NULL;
2832 }
2833
2834 sbitmap_free (blocks);
2835 sbitmap_free (large_region_blocks);
2836}
2837#endif