1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000 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 GNU CC.
9 GNU CC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 2, or (at your option) any
14 GNU CC is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GNU CC; see the file COPYING. If not, write to the Free
21 the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 /* Instruction scheduling pass.
26 This pass implements list scheduling within basic blocks. It is
27 run twice: (1) after flow analysis, but before register allocation,
28 and (2) after register allocation.
30 The first run performs interblock scheduling, moving insns between
31 different blocks in the same "region", and the second runs only
32 basic block scheduling.
34 Interblock motions performed are useful motions and speculative
35 motions, including speculative loads. Motions requiring code
36 duplication are not supported. The identification of motion type
37 and the check for validity of speculative motions requires
38 construction and analysis of the function's control flow graph.
39 The scheduler works as follows:
41 We compute insn priorities based on data dependencies. Flow
42 analysis only creates a fraction of the data-dependencies we must
43 observe: namely, only those dependencies which the combiner can be
44 expected to use. For this pass, we must therefore create the
45 remaining dependencies we need to observe: register dependencies,
46 memory dependencies, dependencies to keep function calls in order,
47 and the dependence between a conditional branch and the setting of
48 condition codes are all dealt with here.
50 The scheduler first traverses the data flow graph, starting with
51 the last instruction, and proceeding to the first, assigning values
52 to insn_priority as it goes. This sorts the instructions
53 topologically by data dependence.
55 Once priorities have been established, we order the insns using
56 list scheduling. This works as follows: starting with a list of
57 all the ready insns, and sorted according to priority number, we
58 schedule the insn from the end of the list by placing its
59 predecessors in the list according to their priority order. We
60 consider this insn scheduled by setting the pointer to the "end" of
61 the list to point to the previous insn. When an insn has no
62 predecessors, we either queue it until sufficient time has elapsed
63 or add it to the ready list. As the instructions are scheduled or
64 when stalls are introduced, the queue advances and dumps insns into
65 the ready list. When all insns down to the lowest priority have
66 been scheduled, the critical path of the basic block has been made
67 as short as possible. The remaining insns are then scheduled in
70 Function unit conflicts are resolved during forward list scheduling
71 by tracking the time when each insn is committed to the schedule
72 and from that, the time the function units it uses must be free.
73 As insns on the ready list are considered for scheduling, those
74 that would result in a blockage of the already committed insns are
75 queued until no blockage will result.
77 The following list shows the order in which we want to break ties
78 among insns in the ready list:
80 1. choose insn with the longest path to end of bb, ties
82 2. choose insn with least contribution to register pressure,
84 3. prefer in-block upon interblock motion, ties broken by
85 4. prefer useful upon speculative motion, ties broken by
86 5. choose insn with largest control flow probability, ties
88 6. choose insn with the least dependences upon the previously
89 scheduled insn, or finally
90 7 choose the insn which has the most insns dependent on it.
91 8. choose insn with lowest UID.
93 Memory references complicate matters. Only if we can be certain
94 that memory references are not part of the data dependency graph
95 (via true, anti, or output dependence), can we move operations past
96 memory references. To first approximation, reads can be done
97 independently, while writes introduce dependencies. Better
98 approximations will yield fewer dependencies.
100 Before reload, an extended analysis of interblock data dependences
101 is required for interblock scheduling. This is performed in
102 compute_block_backward_dependences ().
104 Dependencies set up by memory references are treated in exactly the
105 same way as other dependencies, by using LOG_LINKS backward
106 dependences. LOG_LINKS are translated into INSN_DEPEND forward
107 dependences for the purpose of forward list scheduling.
109 Having optimized the critical path, we may have also unduly
110 extended the lifetimes of some registers. If an operation requires
111 that constants be loaded into registers, it is certainly desirable
112 to load those constants as early as necessary, but no earlier.
113 I.e., it will not do to load up a bunch of registers at the
114 beginning of a basic block only to use them at the end, if they
115 could be loaded later, since this may result in excessive register
118 Note that since branches are never in basic blocks, but only end
119 basic blocks, this pass will not move branches. But that is ok,
120 since we can use GNU's delayed branch scheduling pass to take care
123 Also note that no further optimizations based on algebraic
124 identities are performed, so this pass would be a good one to
125 perform instruction splitting, such as breaking up a multiply
126 instruction into shifts and adds where that is profitable.
128 Given the memory aliasing analysis that this pass should perform,
129 it should be possible to remove redundant stores to memory, and to
130 load values from registers instead of hitting memory.
132 Before reload, speculative insns are moved only if a 'proof' exists
133 that no exception will be caused by this, and if no live registers
134 exist that inhibit the motion (live registers constraints are not
135 represented by data dependence edges).
137 This pass must update information that subsequent passes expect to
138 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
139 reg_n_calls_crossed, and reg_live_length. Also, BLOCK_HEAD,
142 The information in the line number notes is carefully retained by
143 this pass. Notes that refer to the starting and ending of
144 exception regions are also carefully retained by this pass. All
145 other NOTE insns are grouped in their same relative order at the
146 beginning of basic blocks and regions that have been scheduled.
148 The main entry point for this pass is schedule_insns(), called for
149 each function. The work of the scheduler is organized in three
150 levels: (1) function level: insns are subject to splitting,
151 control-flow-graph is constructed, regions are computed (after
152 reload, each region is of one block), (2) region level: control
153 flow graph attributes required for interblock scheduling are
154 computed (dominators, reachability, etc.), data dependences and
155 priorities are computed, and (3) block level: insns in the block
156 are actually scheduled. */
163 #include "hard-reg-set.h"
164 #include "basic-block.h"
166 #include "function.h"
168 #include "insn-config.h"
169 #include "insn-attr.h"
173 #include "sched-int.h"
175 extern char *reg_known_equiv_p;
176 extern rtx *reg_known_value;
178 #ifdef INSN_SCHEDULING
180 /* issue_rate is the number of insns that can be scheduled in the same
181 machine cycle. It can be defined in the config/mach/mach.h file,
182 otherwise we set it to 1. */
184 static int issue_rate;
190 /* sched-verbose controls the amount of debugging output the
191 scheduler prints. It is controlled by -fsched-verbose=N:
192 N>0 and no -DSR : the output is directed to stderr.
193 N>=10 will direct the printouts to stderr (regardless of -dSR).
195 N=2: bb's probabilities, detailed ready list info, unit/insn info.
196 N=3: rtl at abort point, control-flow, regions info.
197 N=5: dependences info. */
199 #define MAX_RGN_BLOCKS 10
200 #define MAX_RGN_INSNS 100
202 static int sched_verbose_param = 0;
203 static int sched_verbose = 0;
205 /* nr_inter/spec counts interblock/speculative motion for the function. */
206 static int nr_inter, nr_spec;
208 /* Debugging file. All printouts are sent to dump, which is always set,
209 either to stderr, or to the dump listing file (-dRS). */
210 FILE *sched_dump = 0;
212 /* Highest uid before scheduling. */
213 static int old_max_uid;
215 /* fix_sched_param() is called from toplev.c upon detection
216 of the -fsched-verbose=N option. */
219 fix_sched_param (param, val)
220 const char *param, *val;
222 if (!strcmp (param, "verbose"))
223 sched_verbose_param = atoi (val);
225 warning ("fix_sched_param: unknown param: %s", param);
228 /* Describe state of dependencies used during sched_analyze phase. */
231 /* The *_insns and *_mems are paired lists. Each pending memory operation
232 will have a pointer to the MEM rtx on one list and a pointer to the
233 containing insn on the other list in the same place in the list. */
235 /* We can't use add_dependence like the old code did, because a single insn
236 may have multiple memory accesses, and hence needs to be on the list
237 once for each memory access. Add_dependence won't let you add an insn
238 to a list more than once. */
240 /* An INSN_LIST containing all insns with pending read operations. */
241 rtx pending_read_insns;
243 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
244 rtx pending_read_mems;
246 /* An INSN_LIST containing all insns with pending write operations. */
247 rtx pending_write_insns;
249 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
250 rtx pending_write_mems;
252 /* Indicates the combined length of the two pending lists. We must prevent
253 these lists from ever growing too large since the number of dependencies
254 produced is at least O(N*N), and execution time is at least O(4*N*N), as
255 a function of the length of these pending lists. */
256 int pending_lists_length;
258 /* The last insn upon which all memory references must depend.
259 This is an insn which flushed the pending lists, creating a dependency
260 between it and all previously pending memory references. This creates
261 a barrier (or a checkpoint) which no memory reference is allowed to cross.
263 This includes all non constant CALL_INSNs. When we do interprocedural
264 alias analysis, this restriction can be relaxed.
265 This may also be an INSN that writes memory if the pending lists grow
267 rtx last_pending_memory_flush;
269 /* The last function call we have seen. All hard regs, and, of course,
270 the last function call, must depend on this. */
271 rtx last_function_call;
273 /* Used to keep post-call psuedo/hard reg movements together with
275 int in_post_call_group_p;
277 /* The LOG_LINKS field of this is a list of insns which use a pseudo
278 register that does not already cross a call. We create
279 dependencies between each of those insn and the next call insn,
280 to ensure that they won't cross a call after scheduling is done. */
281 rtx sched_before_next_call;
283 /* Element N is the next insn that sets (hard or pseudo) register
284 N within the current basic block; or zero, if there is no
285 such insn. Needed for new registers which may be introduced
286 by splitting insns. */
289 rtx *reg_last_clobbers;
292 static regset reg_pending_sets;
293 static regset reg_pending_clobbers;
294 static int reg_pending_sets_all;
296 /* To speed up the test for duplicate dependency links we keep a
297 record of dependencies created by add_dependence when the average
298 number of instructions in a basic block is very large.
300 Studies have shown that there is typically around 5 instructions between
301 branches for typical C code. So we can make a guess that the average
302 basic block is approximately 5 instructions long; we will choose 100X
303 the average size as a very large basic block.
305 Each insn has associated bitmaps for its dependencies. Each bitmap
306 has enough entries to represent a dependency on any other insn in
307 the insn chain. All bitmap for true dependencies cache is
308 allocated then the rest two ones are also allocated. */
309 static sbitmap *true_dependency_cache;
310 static sbitmap *anti_dependency_cache;
311 static sbitmap *output_dependency_cache;
313 /* To speed up checking consistency of formed forward insn
314 dependencies we use the following cache. Another possible solution
315 could be switching off checking duplication of insns in forward
317 #ifdef ENABLE_CHECKING
318 static sbitmap *forward_dependency_cache;
321 /* Indexed by INSN_UID, the collection of all data associated with
322 a single instruction. */
324 struct haifa_insn_data
326 /* A list of insns which depend on the instruction. Unlike LOG_LINKS,
327 it represents forward dependancies. */
330 /* The line number note in effect for each insn. For line number
331 notes, this indicates whether the note may be reused. */
334 /* Logical uid gives the original ordering of the insns. */
337 /* A priority for each insn. */
340 /* The number of incoming edges in the forward dependency graph.
341 As scheduling proceds, counts are decreased. An insn moves to
342 the ready queue when its counter reaches zero. */
345 /* An encoding of the blockage range function. Both unit and range
347 unsigned int blockage;
349 /* Number of instructions referring to this insn. */
352 /* The minimum clock tick at which the insn becomes ready. This is
353 used to note timing constraints for the insns in the pending list. */
358 /* An encoding of the function units used. */
361 /* This weight is an estimation of the insn's contribution to
362 register pressure. */
365 /* Some insns (e.g. call) are not allowed to move across blocks. */
366 unsigned int cant_move : 1;
368 /* Set if there's DEF-USE dependance between some speculatively
369 moved load insn and this one. */
370 unsigned int fed_by_spec_load : 1;
371 unsigned int is_load_insn : 1;
374 static struct haifa_insn_data *h_i_d;
376 #define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend)
377 #define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid)
378 #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority)
379 #define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count)
380 #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost)
381 #define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units)
382 #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight)
384 #define INSN_BLOCKAGE(INSN) (h_i_d[INSN_UID (INSN)].blockage)
386 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
387 #define ENCODE_BLOCKAGE(U, R) \
388 (((U) << BLOCKAGE_BITS \
389 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
390 | MAX_BLOCKAGE_COST (R))
391 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
392 #define BLOCKAGE_RANGE(B) \
393 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
394 | ((B) & BLOCKAGE_MASK))
396 /* Encodings of the `<name>_unit_blockage_range' function. */
397 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
398 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
400 #define DONE_PRIORITY -1
401 #define MAX_PRIORITY 0x7fffffff
402 #define TAIL_PRIORITY 0x7ffffffe
403 #define LAUNCH_PRIORITY 0x7f000001
404 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
405 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
407 #define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count)
408 #define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note)
409 #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
410 #define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move)
411 #define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load)
412 #define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn)
414 /* Vector indexed by basic block number giving the starting line-number
415 for each basic block. */
416 static rtx *line_note_head;
418 /* List of important notes we must keep around. This is a pointer to the
419 last element in the list. */
420 static rtx note_list;
424 /* An instruction is ready to be scheduled when all insns preceding it
425 have already been scheduled. It is important to ensure that all
426 insns which use its result will not be executed until its result
427 has been computed. An insn is maintained in one of four structures:
429 (P) the "Pending" set of insns which cannot be scheduled until
430 their dependencies have been satisfied.
431 (Q) the "Queued" set of insns that can be scheduled when sufficient
433 (R) the "Ready" list of unscheduled, uncommitted insns.
434 (S) the "Scheduled" list of insns.
436 Initially, all insns are either "Pending" or "Ready" depending on
437 whether their dependencies are satisfied.
439 Insns move from the "Ready" list to the "Scheduled" list as they
440 are committed to the schedule. As this occurs, the insns in the
441 "Pending" list have their dependencies satisfied and move to either
442 the "Ready" list or the "Queued" set depending on whether
443 sufficient time has passed to make them ready. As time passes,
444 insns move from the "Queued" set to the "Ready" list. Insns may
445 move from the "Ready" list to the "Queued" set if they are blocked
446 due to a function unit conflict.
448 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
449 insns, i.e., those that are ready, queued, and pending.
450 The "Queued" set (Q) is implemented by the variable `insn_queue'.
451 The "Ready" list (R) is implemented by the variables `ready' and
453 The "Scheduled" list (S) is the new insn chain built by this pass.
455 The transition (R->S) is implemented in the scheduling loop in
456 `schedule_block' when the best insn to schedule is chosen.
457 The transition (R->Q) is implemented in `queue_insn' when an
458 insn is found to have a function unit conflict with the already
460 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
461 insns move from the ready list to the scheduled list.
462 The transition (Q->R) is implemented in 'queue_to_insn' as time
463 passes or stalls are introduced. */
465 /* Implement a circular buffer to delay instructions until sufficient
466 time has passed. INSN_QUEUE_SIZE is a power of two larger than
467 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
468 longest time an isnsn may be queued. */
469 static rtx insn_queue[INSN_QUEUE_SIZE];
470 static int q_ptr = 0;
471 static int q_size = 0;
472 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
473 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
475 /* Describe the ready list of the scheduler.
476 VEC holds space enough for all insns in the current region. VECLEN
477 says how many exactly.
478 FIRST is the index of the element with the highest priority; i.e. the
479 last one in the ready list, since elements are ordered by ascending
481 N_READY determines how many insns are on the ready list. */
491 /* Forward declarations. */
492 static void add_dependence PARAMS ((rtx, rtx, enum reg_note));
493 static void remove_dependence PARAMS ((rtx, rtx));
494 static rtx find_insn_list PARAMS ((rtx, rtx));
495 static void set_sched_group_p PARAMS ((rtx));
496 static unsigned int blockage_range PARAMS ((int, rtx));
497 static void clear_units PARAMS ((void));
498 static void schedule_unit PARAMS ((int, rtx, int));
499 static int actual_hazard PARAMS ((int, rtx, int, int));
500 static int potential_hazard PARAMS ((int, rtx, int));
501 static int insn_cost PARAMS ((rtx, rtx, rtx));
502 static int priority PARAMS ((rtx));
503 static void free_pending_lists PARAMS ((void));
504 static void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx,
506 static void flush_pending_lists PARAMS ((struct deps *, rtx, int));
507 static void sched_analyze_1 PARAMS ((struct deps *, rtx, rtx));
508 static void sched_analyze_2 PARAMS ((struct deps *, rtx, rtx));
509 static void sched_analyze_insn PARAMS ((struct deps *, rtx, rtx, rtx));
510 static void sched_analyze PARAMS ((struct deps *, rtx, rtx));
511 static int rank_for_schedule PARAMS ((const PTR, const PTR));
512 static void swap_sort PARAMS ((rtx *, int));
513 static void queue_insn PARAMS ((rtx, int));
514 static void schedule_insn PARAMS ((rtx, struct ready_list *, int));
515 static void find_insn_reg_weight PARAMS ((int));
516 static void schedule_block PARAMS ((int, int));
517 static int insn_issue_delay PARAMS ((rtx));
518 static void adjust_priority PARAMS ((rtx));
520 /* Control flow graph edges are kept in circular lists. */
529 static haifa_edge *edge_table;
531 #define NEXT_IN(edge) (edge_table[edge].next_in)
532 #define NEXT_OUT(edge) (edge_table[edge].next_out)
533 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
534 #define TO_BLOCK(edge) (edge_table[edge].to_block)
536 /* Number of edges in the control flow graph. (In fact, larger than
537 that by 1, since edge 0 is unused.) */
540 /* Circular list of incoming/outgoing edges of a block. */
541 static int *in_edges;
542 static int *out_edges;
544 #define IN_EDGES(block) (in_edges[block])
545 #define OUT_EDGES(block) (out_edges[block])
547 static int is_cfg_nonregular PARAMS ((void));
548 static int build_control_flow PARAMS ((struct edge_list *));
549 static void new_edge PARAMS ((int, int));
551 /* A region is the main entity for interblock scheduling: insns
552 are allowed to move between blocks in the same region, along
553 control flow graph edges, in the 'up' direction. */
556 int rgn_nr_blocks; /* Number of blocks in region. */
557 int rgn_blocks; /* cblocks in the region (actually index in rgn_bb_table). */
561 /* Number of regions in the procedure. */
562 static int nr_regions;
564 /* Table of region descriptions. */
565 static region *rgn_table;
567 /* Array of lists of regions' blocks. */
568 static int *rgn_bb_table;
570 /* Topological order of blocks in the region (if b2 is reachable from
571 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
572 always referred to by either block or b, while its topological
573 order name (in the region) is refered to by bb. */
574 static int *block_to_bb;
576 /* The number of the region containing a block. */
577 static int *containing_rgn;
579 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
580 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
581 #define BLOCK_TO_BB(block) (block_to_bb[block])
582 #define CONTAINING_RGN(block) (containing_rgn[block])
584 void debug_regions PARAMS ((void));
585 static void find_single_block_region PARAMS ((void));
586 static void find_rgns PARAMS ((struct edge_list *, sbitmap *));
587 static int too_large PARAMS ((int, int *, int *));
589 extern void debug_live PARAMS ((int, int));
591 /* Blocks of the current region being scheduled. */
592 static int current_nr_blocks;
593 static int current_blocks;
595 /* The mapping from bb to block. */
596 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
598 /* Bit vectors and bitset operations are needed for computations on
599 the control flow graph. */
601 typedef unsigned HOST_WIDE_INT *bitset;
604 int *first_member; /* Pointer to the list start in bitlst_table. */
605 int nr_members; /* The number of members of the bit list. */
609 static int bitlst_table_last;
610 static int bitlst_table_size;
611 static int *bitlst_table;
613 static char bitset_member PARAMS ((bitset, int, int));
614 static void extract_bitlst PARAMS ((bitset, int, int, bitlst *));
616 /* Target info declarations.
618 The block currently being scheduled is referred to as the "target" block,
619 while other blocks in the region from which insns can be moved to the
620 target are called "source" blocks. The candidate structure holds info
621 about such sources: are they valid? Speculative? Etc. */
622 typedef bitlst bblst;
633 static candidate *candidate_table;
635 /* A speculative motion requires checking live information on the path
636 from 'source' to 'target'. The split blocks are those to be checked.
637 After a speculative motion, live information should be modified in
640 Lists of split and update blocks for each candidate of the current
641 target are in array bblst_table. */
642 static int *bblst_table, bblst_size, bblst_last;
644 #define IS_VALID(src) ( candidate_table[src].is_valid )
645 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
646 #define SRC_PROB(src) ( candidate_table[src].src_prob )
648 /* The bb being currently scheduled. */
649 static int target_bb;
652 typedef bitlst edgelst;
654 /* Target info functions. */
655 static void split_edges PARAMS ((int, int, edgelst *));
656 static void compute_trg_info PARAMS ((int));
657 void debug_candidate PARAMS ((int));
658 void debug_candidates PARAMS ((int));
660 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
661 typedef bitset bbset;
663 /* Number of words of the bbset. */
664 static int bbset_size;
666 /* Dominators array: dom[i] contains the bbset of dominators of
667 bb i in the region. */
670 /* bb 0 is the only region entry. */
671 #define IS_RGN_ENTRY(bb) (!bb)
673 /* Is bb_src dominated by bb_trg. */
674 #define IS_DOMINATED(bb_src, bb_trg) \
675 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
677 /* Probability: Prob[i] is a float in [0, 1] which is the probability
678 of bb i relative to the region entry. */
681 /* The probability of bb_src, relative to bb_trg. Note, that while the
682 'prob[bb]' is a float in [0, 1], this macro returns an integer
684 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
687 /* Bit-set of edges, where bit i stands for edge i. */
688 typedef bitset edgeset;
690 /* Number of edges in the region. */
691 static int rgn_nr_edges;
693 /* Array of size rgn_nr_edges. */
694 static int *rgn_edges;
696 /* Number of words in an edgeset. */
697 static int edgeset_size;
699 /* Number of bits in an edgeset. */
700 static int edgeset_bitsize;
702 /* Mapping from each edge in the graph to its number in the rgn. */
703 static int *edge_to_bit;
704 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
706 /* The split edges of a source bb is different for each target
707 bb. In order to compute this efficiently, the 'potential-split edges'
708 are computed for each bb prior to scheduling a region. This is actually
709 the split edges of each bb relative to the region entry.
711 pot_split[bb] is the set of potential split edges of bb. */
712 static edgeset *pot_split;
714 /* For every bb, a set of its ancestor edges. */
715 static edgeset *ancestor_edges;
717 static void compute_dom_prob_ps PARAMS ((int));
719 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
720 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
721 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
722 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
724 /* Parameters affecting the decision of rank_for_schedule(). */
725 #define MIN_DIFF_PRIORITY 2
726 #define MIN_PROBABILITY 40
727 #define MIN_PROB_DIFF 10
729 /* Speculative scheduling functions. */
730 static int check_live_1 PARAMS ((int, rtx));
731 static void update_live_1 PARAMS ((int, rtx));
732 static int check_live PARAMS ((rtx, int));
733 static void update_live PARAMS ((rtx, int));
734 static void set_spec_fed PARAMS ((rtx));
735 static int is_pfree PARAMS ((rtx, int, int));
736 static int find_conditional_protection PARAMS ((rtx, int));
737 static int is_conditionally_protected PARAMS ((rtx, int, int));
738 static int may_trap_exp PARAMS ((rtx, int));
739 static int haifa_classify_insn PARAMS ((rtx));
740 static int is_prisky PARAMS ((rtx, int, int));
741 static int is_exception_free PARAMS ((rtx, int, int));
743 static char find_insn_mem_list PARAMS ((rtx, rtx, rtx, rtx));
744 static void compute_forward_dependences PARAMS ((rtx, rtx));
745 static void add_branch_dependences PARAMS ((rtx, rtx));
746 static void compute_block_backward_dependences PARAMS ((int));
747 void debug_dependencies PARAMS ((void));
749 /* Notes handling mechanism:
750 =========================
751 Generally, NOTES are saved before scheduling and restored after scheduling.
752 The scheduler distinguishes between three types of notes:
754 (1) LINE_NUMBER notes, generated and used for debugging. Here,
755 before scheduling a region, a pointer to the LINE_NUMBER note is
756 added to the insn following it (in save_line_notes()), and the note
757 is removed (in rm_line_notes() and unlink_line_notes()). After
758 scheduling the region, this pointer is used for regeneration of
759 the LINE_NUMBER note (in restore_line_notes()).
761 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
762 Before scheduling a region, a pointer to the note is added to the insn
763 that follows or precedes it. (This happens as part of the data dependence
764 computation). After scheduling an insn, the pointer contained in it is
765 used for regenerating the corresponding note (in reemit_notes).
767 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
768 these notes are put in a list (in rm_other_notes() and
769 unlink_other_notes ()). After scheduling the block, these notes are
770 inserted at the beginning of the block (in schedule_block()). */
772 static rtx unlink_other_notes PARAMS ((rtx, rtx));
773 static rtx unlink_line_notes PARAMS ((rtx, rtx));
774 static void rm_line_notes PARAMS ((int));
775 static void save_line_notes PARAMS ((int));
776 static void restore_line_notes PARAMS ((int));
777 static void rm_redundant_line_notes PARAMS ((void));
778 static void rm_other_notes PARAMS ((rtx, rtx));
779 static rtx reemit_notes PARAMS ((rtx, rtx));
781 static int no_real_insns_p PARAMS ((rtx, rtx));
782 static void get_block_head_tail PARAMS ((int, rtx *, rtx *));
783 static void get_bb_head_tail PARAMS ((int, rtx *, rtx *));
785 static void ready_add PARAMS ((struct ready_list *, rtx));
786 static rtx *ready_lastpos PARAMS ((struct ready_list *));
787 static void ready_sort PARAMS ((struct ready_list *));
788 static rtx ready_remove_first PARAMS ((struct ready_list *));
790 static void queue_to_ready PARAMS ((struct ready_list *));
792 static void debug_ready_list PARAMS ((struct ready_list *));
793 void debug_reg_vector PARAMS ((regset));
795 static rtx move_insn1 PARAMS ((rtx, rtx));
796 static rtx move_insn PARAMS ((rtx, rtx));
797 static rtx group_leader PARAMS ((rtx));
798 static int set_priorities PARAMS ((int));
799 static void init_deps PARAMS ((struct deps *));
800 static void free_deps PARAMS ((struct deps *));
801 static void init_dependency_caches PARAMS ((int));
802 static void free_dependency_caches PARAMS ((void));
803 static void init_regions PARAMS ((void));
804 static void sched_init PARAMS ((FILE *));
805 static void schedule_region PARAMS ((int));
806 static void propagate_deps PARAMS ((int, struct deps *, int));
808 #endif /* INSN_SCHEDULING */
810 /* Point to state used for the current scheduling pass. */
811 struct sched_info *current_sched_info;
813 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
815 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
816 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
817 of dependence that this link represents. */
820 add_dependence (insn, elem, dep_type)
823 enum reg_note dep_type;
827 enum reg_note present_dep_type;
829 /* Don't depend an insn on itself. */
833 /* We can get a dependency on deleted insns due to optimizations in
834 the register allocation and reloading or due to splitting. Any
835 such dependency is useless and can be ignored. */
836 if (GET_CODE (elem) == NOTE)
839 /* If elem is part of a sequence that must be scheduled together, then
840 make the dependence point to the last insn of the sequence.
841 When HAVE_cc0, it is possible for NOTEs to exist between users and
842 setters of the condition codes, so we must skip past notes here.
843 Otherwise, NOTEs are impossible here. */
844 next = next_nonnote_insn (elem);
845 if (next && SCHED_GROUP_P (next)
846 && GET_CODE (next) != CODE_LABEL)
848 /* Notes will never intervene here though, so don't bother checking
851 /* We must reject CODE_LABELs, so that we don't get confused by one
852 that has LABEL_PRESERVE_P set, which is represented by the same
853 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
857 while ((nnext = next_nonnote_insn (next)) != NULL
858 && SCHED_GROUP_P (nnext)
859 && GET_CODE (nnext) != CODE_LABEL)
862 /* Again, don't depend an insn on itself. */
866 /* Make the dependence to NEXT, the last insn of the group, instead
867 of the original ELEM. */
872 #ifdef INSN_SCHEDULING
873 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
874 No need for interblock dependences with calls, since
875 calls are not moved between blocks. Note: the edge where
876 elem is a CALL is still required. */
877 if (GET_CODE (insn) == CALL_INSN
878 && (INSN_BB (elem) != INSN_BB (insn)))
881 /* If we already have a dependency for ELEM, then we do not need to
882 do anything. Avoiding the list walk below can cut compile times
883 dramatically for some code. */
884 if (true_dependency_cache != NULL)
886 if (anti_dependency_cache == NULL || output_dependency_cache == NULL)
888 if (TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)))
889 present_dep_type = 0;
890 else if (TEST_BIT (anti_dependency_cache[INSN_LUID (insn)],
892 present_dep_type = REG_DEP_ANTI;
893 else if (TEST_BIT (output_dependency_cache[INSN_LUID (insn)],
895 present_dep_type = REG_DEP_OUTPUT;
898 if (present_p && (int) dep_type >= (int) present_dep_type)
903 /* Check that we don't already have this dependence. */
905 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
906 if (XEXP (link, 0) == elem)
908 #ifdef INSN_SCHEDULING
909 /* Clear corresponding cache entry because type of the link
911 if (true_dependency_cache != NULL)
913 if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
914 RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
916 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT
917 && output_dependency_cache)
918 RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
925 /* If this is a more restrictive type of dependence than the existing
926 one, then change the existing dependence to this type. */
927 if ((int) dep_type < (int) REG_NOTE_KIND (link))
928 PUT_REG_NOTE_KIND (link, dep_type);
930 #ifdef INSN_SCHEDULING
931 /* If we are adding a dependency to INSN's LOG_LINKs, then
932 note that in the bitmap caches of dependency information. */
933 if (true_dependency_cache != NULL)
935 if ((int)REG_NOTE_KIND (link) == 0)
936 SET_BIT (true_dependency_cache[INSN_LUID (insn)],
938 else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
939 SET_BIT (anti_dependency_cache[INSN_LUID (insn)],
941 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
942 SET_BIT (output_dependency_cache[INSN_LUID (insn)],
948 /* Might want to check one level of transitivity to save conses. */
950 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
951 LOG_LINKS (insn) = link;
953 /* Insn dependency, not data dependency. */
954 PUT_REG_NOTE_KIND (link, dep_type);
956 #ifdef INSN_SCHEDULING
957 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
958 in the bitmap caches of dependency information. */
959 if (true_dependency_cache != NULL)
961 if ((int)dep_type == 0)
962 SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
963 else if (dep_type == REG_DEP_ANTI)
964 SET_BIT (anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
965 else if (dep_type == REG_DEP_OUTPUT)
966 SET_BIT (output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
971 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
972 of INSN. Abort if not found. */
975 remove_dependence (insn, elem)
979 rtx prev, link, next;
982 for (prev = 0, link = LOG_LINKS (insn); link; link = next)
984 next = XEXP (link, 1);
985 if (XEXP (link, 0) == elem)
988 XEXP (prev, 1) = next;
990 LOG_LINKS (insn) = next;
992 #ifdef INSN_SCHEDULING
993 /* If we are removing a dependency from the LOG_LINKS list,
994 make sure to remove it from the cache too. */
995 if (true_dependency_cache != NULL)
997 if (REG_NOTE_KIND (link) == 0)
998 RESET_BIT (true_dependency_cache[INSN_LUID (insn)],
1000 else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
1001 RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
1003 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
1004 RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
1009 free_INSN_LIST_node (link);
1022 /* Return the INSN_LIST containing INSN in LIST, or NULL
1023 if LIST does not contain INSN. */
1026 find_insn_list (insn, list)
1032 if (XEXP (list, 0) == insn)
1034 list = XEXP (list, 1);
1039 /* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
1040 goes along with that. */
1043 set_sched_group_p (insn)
1048 SCHED_GROUP_P (insn) = 1;
1050 /* There may be a note before this insn now, but all notes will
1051 be removed before we actually try to schedule the insns, so
1052 it won't cause a problem later. We must avoid it here though. */
1053 prev = prev_nonnote_insn (insn);
1055 /* Make a copy of all dependencies on the immediately previous insn,
1056 and add to this insn. This is so that all the dependencies will
1057 apply to the group. Remove an explicit dependence on this insn
1058 as SCHED_GROUP_P now represents it. */
1060 if (find_insn_list (prev, LOG_LINKS (insn)))
1061 remove_dependence (insn, prev);
1063 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
1064 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
1067 /* If it is profitable to use them, initialize caches for tracking
1068 dependency informatino. LUID is the number of insns to be scheduled,
1069 it is used in the estimate of profitability. */
1071 init_dependency_caches (luid)
1074 /* ?!? We could save some memory by computing a per-region luid mapping
1075 which could reduce both the number of vectors in the cache and the size
1076 of each vector. Instead we just avoid the cache entirely unless the
1077 average number of instructions in a basic block is very high. See
1078 the comment before the declaration of true_dependency_cache for
1079 what we consider "very high". */
1080 if (luid / n_basic_blocks > 100 * 5)
1082 true_dependency_cache = sbitmap_vector_alloc (luid, luid);
1083 sbitmap_vector_zero (true_dependency_cache, luid);
1084 anti_dependency_cache = sbitmap_vector_alloc (luid, luid);
1085 sbitmap_vector_zero (anti_dependency_cache, luid);
1086 output_dependency_cache = sbitmap_vector_alloc (luid, luid);
1087 sbitmap_vector_zero (output_dependency_cache, luid);
1088 #ifdef ENABLE_CHECKING
1089 forward_dependency_cache = sbitmap_vector_alloc (luid, luid);
1090 sbitmap_vector_zero (forward_dependency_cache, luid);
1095 /* Free the caches allocated in init_dependency_caches. */
1097 free_dependency_caches ()
1099 if (true_dependency_cache)
1101 free (true_dependency_cache);
1102 true_dependency_cache = NULL;
1103 free (anti_dependency_cache);
1104 anti_dependency_cache = NULL;
1105 free (output_dependency_cache);
1106 output_dependency_cache = NULL;
1107 #ifdef ENABLE_CHECKING
1108 free (forward_dependency_cache);
1109 forward_dependency_cache = NULL;
1114 #ifndef INSN_SCHEDULING
1116 schedule_insns (dump_file)
1117 FILE *dump_file ATTRIBUTE_UNUSED;
1122 /* Computation of memory dependencies. */
1124 /* Data structures for the computation of data dependences in a regions. We
1125 keep one mem_deps structure for every basic block. Before analyzing the
1126 data dependences for a bb, its variables are initialized as a function of
1127 the variables of its predecessors. When the analysis for a bb completes,
1128 we save the contents to the corresponding bb_mem_deps[bb] variable. */
1130 static struct deps *bb_deps;
1132 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1133 so that insns independent of the last scheduled insn will be preferred
1134 over dependent instructions. */
1136 static rtx last_scheduled_insn;
1138 /* Functions for construction of the control flow graph. */
1140 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1142 We decide not to build the control flow graph if there is possibly more
1143 than one entry to the function, if computed branches exist, of if we
1144 have nonlocal gotos. */
1147 is_cfg_nonregular ()
1153 /* If we have a label that could be the target of a nonlocal goto, then
1154 the cfg is not well structured. */
1155 if (nonlocal_goto_handler_labels)
1158 /* If we have any forced labels, then the cfg is not well structured. */
1162 /* If this function has a computed jump, then we consider the cfg
1163 not well structured. */
1164 if (current_function_has_computed_jump)
1167 /* If we have exception handlers, then we consider the cfg not well
1168 structured. ?!? We should be able to handle this now that flow.c
1169 computes an accurate cfg for EH. */
1170 if (exception_handler_labels)
1173 /* If we have non-jumping insns which refer to labels, then we consider
1174 the cfg not well structured. */
1175 /* Check for labels referred to other thn by jumps. */
1176 for (b = 0; b < n_basic_blocks; b++)
1177 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
1179 code = GET_CODE (insn);
1180 if (GET_RTX_CLASS (code) == 'i')
1184 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1185 if (REG_NOTE_KIND (note) == REG_LABEL)
1189 if (insn == BLOCK_END (b))
1193 /* All the tests passed. Consider the cfg well structured. */
1197 /* Build the control flow graph and set nr_edges.
1199 Instead of trying to build a cfg ourselves, we rely on flow to
1200 do it for us. Stamp out useless code (and bug) duplication.
1202 Return nonzero if an irregularity in the cfg is found which would
1203 prevent cross block scheduling. */
1206 build_control_flow (edge_list)
1207 struct edge_list *edge_list;
1209 int i, unreachable, num_edges;
1211 /* This already accounts for entry/exit edges. */
1212 num_edges = NUM_EDGES (edge_list);
1214 /* Unreachable loops with more than one basic block are detected
1215 during the DFS traversal in find_rgns.
1217 Unreachable loops with a single block are detected here. This
1218 test is redundant with the one in find_rgns, but it's much
1219 cheaper to go ahead and catch the trivial case here. */
1221 for (i = 0; i < n_basic_blocks; i++)
1223 basic_block b = BASIC_BLOCK (i);
1226 || (b->pred->src == b
1227 && b->pred->pred_next == NULL))
1231 /* ??? We can kill these soon. */
1232 in_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
1233 out_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
1234 edge_table = (haifa_edge *) xcalloc (num_edges, sizeof (haifa_edge));
1237 for (i = 0; i < num_edges; i++)
1239 edge e = INDEX_EDGE (edge_list, i);
1241 if (e->dest != EXIT_BLOCK_PTR
1242 && e->src != ENTRY_BLOCK_PTR)
1243 new_edge (e->src->index, e->dest->index);
1246 /* Increment by 1, since edge 0 is unused. */
1252 /* Record an edge in the control flow graph from SOURCE to TARGET.
1254 In theory, this is redundant with the s_succs computed above, but
1255 we have not converted all of haifa to use information from the
1259 new_edge (source, target)
1263 int curr_edge, fst_edge;
1265 /* Check for duplicates. */
1266 fst_edge = curr_edge = OUT_EDGES (source);
1269 if (FROM_BLOCK (curr_edge) == source
1270 && TO_BLOCK (curr_edge) == target)
1275 curr_edge = NEXT_OUT (curr_edge);
1277 if (fst_edge == curr_edge)
1283 FROM_BLOCK (e) = source;
1284 TO_BLOCK (e) = target;
1286 if (OUT_EDGES (source))
1288 next_edge = NEXT_OUT (OUT_EDGES (source));
1289 NEXT_OUT (OUT_EDGES (source)) = e;
1290 NEXT_OUT (e) = next_edge;
1294 OUT_EDGES (source) = e;
1298 if (IN_EDGES (target))
1300 next_edge = NEXT_IN (IN_EDGES (target));
1301 NEXT_IN (IN_EDGES (target)) = e;
1302 NEXT_IN (e) = next_edge;
1306 IN_EDGES (target) = e;
1311 /* BITSET macros for operations on the control flow graph. */
1313 /* Compute bitwise union of two bitsets. */
1314 #define BITSET_UNION(set1, set2, len) \
1315 do { register bitset tp = set1, sp = set2; \
1317 for (i = 0; i < len; i++) \
1318 *(tp++) |= *(sp++); } while (0)
1320 /* Compute bitwise intersection of two bitsets. */
1321 #define BITSET_INTER(set1, set2, len) \
1322 do { register bitset tp = set1, sp = set2; \
1324 for (i = 0; i < len; i++) \
1325 *(tp++) &= *(sp++); } while (0)
1327 /* Compute bitwise difference of two bitsets. */
1328 #define BITSET_DIFFER(set1, set2, len) \
1329 do { register bitset tp = set1, sp = set2; \
1331 for (i = 0; i < len; i++) \
1332 *(tp++) &= ~*(sp++); } while (0)
1334 /* Inverts every bit of bitset 'set'. */
1335 #define BITSET_INVERT(set, len) \
1336 do { register bitset tmpset = set; \
1338 for (i = 0; i < len; i++, tmpset++) \
1339 *tmpset = ~*tmpset; } while (0)
1341 /* Turn on the index'th bit in bitset set. */
1342 #define BITSET_ADD(set, index, len) \
1344 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1347 set[index/HOST_BITS_PER_WIDE_INT] |= \
1348 1 << (index % HOST_BITS_PER_WIDE_INT); \
1351 /* Turn off the index'th bit in set. */
1352 #define BITSET_REMOVE(set, index, len) \
1354 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1357 set[index/HOST_BITS_PER_WIDE_INT] &= \
1358 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1361 /* Check if the index'th bit in bitset set is on. */
1364 bitset_member (set, index, len)
1368 if (index >= HOST_BITS_PER_WIDE_INT * len)
1370 return (set[index / HOST_BITS_PER_WIDE_INT] &
1371 1 << (index % HOST_BITS_PER_WIDE_INT)) ? 1 : 0;
1374 /* Translate a bit-set SET to a list BL of the bit-set members. */
1377 extract_bitlst (set, len, bitlen, bl)
1384 unsigned HOST_WIDE_INT word;
1386 /* bblst table space is reused in each call to extract_bitlst. */
1387 bitlst_table_last = 0;
1389 bl->first_member = &bitlst_table[bitlst_table_last];
1392 /* Iterate over each word in the bitset. */
1393 for (i = 0; i < len; i++)
1396 offset = i * HOST_BITS_PER_WIDE_INT;
1398 /* Iterate over each bit in the word, but do not
1399 go beyond the end of the defined bits. */
1400 for (j = 0; offset < bitlen && word; j++)
1404 bitlst_table[bitlst_table_last++] = offset;
1414 /* Functions for the construction of regions. */
1416 /* Print the regions, for debugging purposes. Callable from debugger. */
1423 fprintf (sched_dump, "\n;; ------------ REGIONS ----------\n\n");
1424 for (rgn = 0; rgn < nr_regions; rgn++)
1426 fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
1427 rgn_table[rgn].rgn_nr_blocks);
1428 fprintf (sched_dump, ";;\tbb/block: ");
1430 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
1432 current_blocks = RGN_BLOCKS (rgn);
1434 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
1437 fprintf (sched_dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
1440 fprintf (sched_dump, "\n\n");
1444 /* Build a single block region for each basic block in the function.
1445 This allows for using the same code for interblock and basic block
1449 find_single_block_region ()
1453 for (i = 0; i < n_basic_blocks; i++)
1455 rgn_bb_table[i] = i;
1456 RGN_NR_BLOCKS (i) = 1;
1458 CONTAINING_RGN (i) = i;
1459 BLOCK_TO_BB (i) = 0;
1461 nr_regions = n_basic_blocks;
1464 /* Update number of blocks and the estimate for number of insns
1465 in the region. Return 1 if the region is "too large" for interblock
1466 scheduling (compile time considerations), otherwise return 0. */
1469 too_large (block, num_bbs, num_insns)
1470 int block, *num_bbs, *num_insns;
1473 (*num_insns) += (INSN_LUID (BLOCK_END (block)) -
1474 INSN_LUID (BLOCK_HEAD (block)));
1475 if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
1481 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1482 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1483 loop containing blk. */
1484 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1486 if (max_hdr[blk] == -1) \
1487 max_hdr[blk] = hdr; \
1488 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1489 RESET_BIT (inner, hdr); \
1490 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1492 RESET_BIT (inner,max_hdr[blk]); \
1493 max_hdr[blk] = hdr; \
1497 /* Find regions for interblock scheduling.
1499 A region for scheduling can be:
1501 * A loop-free procedure, or
1503 * A reducible inner loop, or
1505 * A basic block not contained in any other region.
1507 ?!? In theory we could build other regions based on extended basic
1508 blocks or reverse extended basic blocks. Is it worth the trouble?
1510 Loop blocks that form a region are put into the region's block list
1511 in topological order.
1513 This procedure stores its results into the following global (ick) variables
1521 We use dominator relationships to avoid making regions out of non-reducible
1524 This procedure needs to be converted to work on pred/succ lists instead
1525 of edge tables. That would simplify it somewhat. */
1528 find_rgns (edge_list, dom)
1529 struct edge_list *edge_list;
1532 int *max_hdr, *dfs_nr, *stack, *degree;
1534 int node, child, loop_head, i, head, tail;
1535 int count = 0, sp, idx = 0, current_edge = out_edges[0];
1536 int num_bbs, num_insns, unreachable;
1537 int too_large_failure;
1539 /* Note if an edge has been passed. */
1542 /* Note if a block is a natural loop header. */
1545 /* Note if a block is an natural inner loop header. */
1548 /* Note if a block is in the block queue. */
1551 /* Note if a block is in the block queue. */
1554 int num_edges = NUM_EDGES (edge_list);
1556 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1557 and a mapping from block to its loop header (if the block is contained
1558 in a loop, else -1).
1560 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1561 be used as inputs to the second traversal.
1563 STACK, SP and DFS_NR are only used during the first traversal. */
1565 /* Allocate and initialize variables for the first traversal. */
1566 max_hdr = (int *) xmalloc (n_basic_blocks * sizeof (int));
1567 dfs_nr = (int *) xcalloc (n_basic_blocks, sizeof (int));
1568 stack = (int *) xmalloc (nr_edges * sizeof (int));
1570 inner = sbitmap_alloc (n_basic_blocks);
1571 sbitmap_ones (inner);
1573 header = sbitmap_alloc (n_basic_blocks);
1574 sbitmap_zero (header);
1576 passed = sbitmap_alloc (nr_edges);
1577 sbitmap_zero (passed);
1579 in_queue = sbitmap_alloc (n_basic_blocks);
1580 sbitmap_zero (in_queue);
1582 in_stack = sbitmap_alloc (n_basic_blocks);
1583 sbitmap_zero (in_stack);
1585 for (i = 0; i < n_basic_blocks; i++)
1588 /* DFS traversal to find inner loops in the cfg. */
1593 if (current_edge == 0 || TEST_BIT (passed, current_edge))
1595 /* We have reached a leaf node or a node that was already
1596 processed. Pop edges off the stack until we find
1597 an edge that has not yet been processed. */
1599 && (current_edge == 0 || TEST_BIT (passed, current_edge)))
1601 /* Pop entry off the stack. */
1602 current_edge = stack[sp--];
1603 node = FROM_BLOCK (current_edge);
1604 child = TO_BLOCK (current_edge);
1605 RESET_BIT (in_stack, child);
1606 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1607 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1608 current_edge = NEXT_OUT (current_edge);
1611 /* See if have finished the DFS tree traversal. */
1612 if (sp < 0 && TEST_BIT (passed, current_edge))
1615 /* Nope, continue the traversal with the popped node. */
1619 /* Process a node. */
1620 node = FROM_BLOCK (current_edge);
1621 child = TO_BLOCK (current_edge);
1622 SET_BIT (in_stack, node);
1623 dfs_nr[node] = ++count;
1625 /* If the successor is in the stack, then we've found a loop.
1626 Mark the loop, if it is not a natural loop, then it will
1627 be rejected during the second traversal. */
1628 if (TEST_BIT (in_stack, child))
1631 SET_BIT (header, child);
1632 UPDATE_LOOP_RELATIONS (node, child);
1633 SET_BIT (passed, current_edge);
1634 current_edge = NEXT_OUT (current_edge);
1638 /* If the child was already visited, then there is no need to visit
1639 it again. Just update the loop relationships and restart
1643 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1644 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1645 SET_BIT (passed, current_edge);
1646 current_edge = NEXT_OUT (current_edge);
1650 /* Push an entry on the stack and continue DFS traversal. */
1651 stack[++sp] = current_edge;
1652 SET_BIT (passed, current_edge);
1653 current_edge = OUT_EDGES (child);
1655 /* This is temporary until haifa is converted to use rth's new
1656 cfg routines which have true entry/exit blocks and the
1657 appropriate edges from/to those blocks.
1659 Generally we update dfs_nr for a node when we process its
1660 out edge. However, if the node has no out edge then we will
1661 not set dfs_nr for that node. This can confuse the scheduler
1662 into thinking that we have unreachable blocks, which in turn
1663 disables cross block scheduling.
1665 So, if we have a node with no out edges, go ahead and mark it
1666 as reachable now. */
1667 if (current_edge == 0)
1668 dfs_nr[child] = ++count;
1671 /* Another check for unreachable blocks. The earlier test in
1672 is_cfg_nonregular only finds unreachable blocks that do not
1675 The DFS traversal will mark every block that is reachable from
1676 the entry node by placing a nonzero value in dfs_nr. Thus if
1677 dfs_nr is zero for any block, then it must be unreachable. */
1679 for (i = 0; i < n_basic_blocks; i++)
1686 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1687 to hold degree counts. */
1690 for (i = 0; i < n_basic_blocks; i++)
1692 for (i = 0; i < num_edges; i++)
1694 edge e = INDEX_EDGE (edge_list, i);
1696 if (e->dest != EXIT_BLOCK_PTR)
1697 degree[e->dest->index]++;
1700 /* Do not perform region scheduling if there are any unreachable
1707 SET_BIT (header, 0);
1709 /* Second travsersal:find reducible inner loops and topologically sort
1710 block of each region. */
1712 queue = (int *) xmalloc (n_basic_blocks * sizeof (int));
1714 /* Find blocks which are inner loop headers. We still have non-reducible
1715 loops to consider at this point. */
1716 for (i = 0; i < n_basic_blocks; i++)
1718 if (TEST_BIT (header, i) && TEST_BIT (inner, i))
1723 /* Now check that the loop is reducible. We do this separate
1724 from finding inner loops so that we do not find a reducible
1725 loop which contains an inner non-reducible loop.
1727 A simple way to find reducible/natural loops is to verify
1728 that each block in the loop is dominated by the loop
1731 If there exists a block that is not dominated by the loop
1732 header, then the block is reachable from outside the loop
1733 and thus the loop is not a natural loop. */
1734 for (j = 0; j < n_basic_blocks; j++)
1736 /* First identify blocks in the loop, except for the loop
1738 if (i == max_hdr[j] && i != j)
1740 /* Now verify that the block is dominated by the loop
1742 if (!TEST_BIT (dom[j], i))
1747 /* If we exited the loop early, then I is the header of
1748 a non-reducible loop and we should quit processing it
1750 if (j != n_basic_blocks)
1753 /* I is a header of an inner loop, or block 0 in a subroutine
1754 with no loops at all. */
1756 too_large_failure = 0;
1757 loop_head = max_hdr[i];
1759 /* Decrease degree of all I's successors for topological
1761 for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
1762 if (e->dest != EXIT_BLOCK_PTR)
1763 --degree[e->dest->index];
1765 /* Estimate # insns, and count # blocks in the region. */
1767 num_insns = (INSN_LUID (BLOCK_END (i))
1768 - INSN_LUID (BLOCK_HEAD (i)));
1770 /* Find all loop latches (blocks with back edges to the loop
1771 header) or all the leaf blocks in the cfg has no loops.
1773 Place those blocks into the queue. */
1776 for (j = 0; j < n_basic_blocks; j++)
1777 /* Leaf nodes have only a single successor which must
1779 if (BASIC_BLOCK (j)->succ
1780 && BASIC_BLOCK (j)->succ->dest == EXIT_BLOCK_PTR
1781 && BASIC_BLOCK (j)->succ->succ_next == NULL)
1784 SET_BIT (in_queue, j);
1786 if (too_large (j, &num_bbs, &num_insns))
1788 too_large_failure = 1;
1797 for (e = BASIC_BLOCK (i)->pred; e; e = e->pred_next)
1799 if (e->src == ENTRY_BLOCK_PTR)
1802 node = e->src->index;
1804 if (max_hdr[node] == loop_head && node != i)
1806 /* This is a loop latch. */
1807 queue[++tail] = node;
1808 SET_BIT (in_queue, node);
1810 if (too_large (node, &num_bbs, &num_insns))
1812 too_large_failure = 1;
1819 /* Now add all the blocks in the loop to the queue.
1821 We know the loop is a natural loop; however the algorithm
1822 above will not always mark certain blocks as being in the
1830 The algorithm in the DFS traversal may not mark B & D as part
1831 of the loop (ie they will not have max_hdr set to A).
1833 We know they can not be loop latches (else they would have
1834 had max_hdr set since they'd have a backedge to a dominator
1835 block). So we don't need them on the initial queue.
1837 We know they are part of the loop because they are dominated
1838 by the loop header and can be reached by a backwards walk of
1839 the edges starting with nodes on the initial queue.
1841 It is safe and desirable to include those nodes in the
1842 loop/scheduling region. To do so we would need to decrease
1843 the degree of a node if it is the target of a backedge
1844 within the loop itself as the node is placed in the queue.
1846 We do not do this because I'm not sure that the actual
1847 scheduling code will properly handle this case. ?!? */
1849 while (head < tail && !too_large_failure)
1852 child = queue[++head];
1854 for (e = BASIC_BLOCK (child)->pred; e; e = e->pred_next)
1856 node = e->src->index;
1858 /* See discussion above about nodes not marked as in
1859 this loop during the initial DFS traversal. */
1860 if (e->src == ENTRY_BLOCK_PTR
1861 || max_hdr[node] != loop_head)
1866 else if (!TEST_BIT (in_queue, node) && node != i)
1868 queue[++tail] = node;
1869 SET_BIT (in_queue, node);
1871 if (too_large (node, &num_bbs, &num_insns))
1873 too_large_failure = 1;
1880 if (tail >= 0 && !too_large_failure)
1882 /* Place the loop header into list of region blocks. */
1884 rgn_bb_table[idx] = i;
1885 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1886 RGN_BLOCKS (nr_regions) = idx++;
1887 CONTAINING_RGN (i) = nr_regions;
1888 BLOCK_TO_BB (i) = count = 0;
1890 /* Remove blocks from queue[] when their in degree
1891 becomes zero. Repeat until no blocks are left on the
1892 list. This produces a topological list of blocks in
1898 child = queue[head];
1899 if (degree[child] == 0)
1904 rgn_bb_table[idx++] = child;
1905 BLOCK_TO_BB (child) = ++count;
1906 CONTAINING_RGN (child) = nr_regions;
1907 queue[head] = queue[tail--];
1909 for (e = BASIC_BLOCK (child)->succ;
1912 if (e->dest != EXIT_BLOCK_PTR)
1913 --degree[e->dest->index];
1925 /* Any block that did not end up in a region is placed into a region
1927 for (i = 0; i < n_basic_blocks; i++)
1930 rgn_bb_table[idx] = i;
1931 RGN_NR_BLOCKS (nr_regions) = 1;
1932 RGN_BLOCKS (nr_regions) = idx++;
1933 CONTAINING_RGN (i) = nr_regions++;
1934 BLOCK_TO_BB (i) = 0;
1947 /* Functions for regions scheduling information. */
1949 /* Compute dominators, probability, and potential-split-edges of bb.
1950 Assume that these values were already computed for bb's predecessors. */
1953 compute_dom_prob_ps (bb)
1956 int nxt_in_edge, fst_in_edge, pred;
1957 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1960 if (IS_RGN_ENTRY (bb))
1962 BITSET_ADD (dom[bb], 0, bbset_size);
1967 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1969 /* Intialize dom[bb] to '111..1'. */
1970 BITSET_INVERT (dom[bb], bbset_size);
1974 pred = FROM_BLOCK (nxt_in_edge);
1975 BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
1977 BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
1980 BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
1983 nr_rgn_out_edges = 0;
1984 fst_out_edge = OUT_EDGES (pred);
1985 nxt_out_edge = NEXT_OUT (fst_out_edge);
1986 BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
1989 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
1991 /* The successor doesn't belong in the region? */
1992 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1993 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1996 while (fst_out_edge != nxt_out_edge)
1999 /* The successor doesn't belong in the region? */
2000 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
2001 CONTAINING_RGN (BB_TO_BLOCK (bb)))
2003 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
2004 nxt_out_edge = NEXT_OUT (nxt_out_edge);
2008 /* Now nr_rgn_out_edges is the number of region-exit edges from
2009 pred, and nr_out_edges will be the number of pred out edges
2010 not leaving the region. */
2011 nr_out_edges -= nr_rgn_out_edges;
2012 if (nr_rgn_out_edges > 0)
2013 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
2015 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
2016 nxt_in_edge = NEXT_IN (nxt_in_edge);
2018 while (fst_in_edge != nxt_in_edge);
2020 BITSET_ADD (dom[bb], bb, bbset_size);
2021 BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
2023 if (sched_verbose >= 2)
2024 fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
2025 (int) (100.0 * prob[bb]));
2028 /* Functions for target info. */
2030 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
2031 Note that bb_trg dominates bb_src. */
2034 split_edges (bb_src, bb_trg, bl)
2039 int es = edgeset_size;
2040 edgeset src = (edgeset) xcalloc (es, sizeof (HOST_WIDE_INT));
2043 src[es] = (pot_split[bb_src])[es];
2044 BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
2045 extract_bitlst (src, edgeset_size, edgeset_bitsize, bl);
2049 /* Find the valid candidate-source-blocks for the target block TRG, compute
2050 their probability, and check if they are speculative or not.
2051 For speculative sources, compute their update-blocks and split-blocks. */
2054 compute_trg_info (trg)
2057 register candidate *sp;
2059 int check_block, update_idx;
2060 int i, j, k, fst_edge, nxt_edge;
2062 /* Define some of the fields for the target bb as well. */
2063 sp = candidate_table + trg;
2065 sp->is_speculative = 0;
2068 for (i = trg + 1; i < current_nr_blocks; i++)
2070 sp = candidate_table + i;
2072 sp->is_valid = IS_DOMINATED (i, trg);
2075 sp->src_prob = GET_SRC_PROB (i, trg);
2076 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
2081 split_edges (i, trg, &el);
2082 sp->is_speculative = (el.nr_members) ? 1 : 0;
2083 if (sp->is_speculative && !flag_schedule_speculative)
2089 char *update_blocks;
2091 /* Compute split blocks and store them in bblst_table.
2092 The TO block of every split edge is a split block. */
2093 sp->split_bbs.first_member = &bblst_table[bblst_last];
2094 sp->split_bbs.nr_members = el.nr_members;
2095 for (j = 0; j < el.nr_members; bblst_last++, j++)
2096 bblst_table[bblst_last] =
2097 TO_BLOCK (rgn_edges[el.first_member[j]]);
2098 sp->update_bbs.first_member = &bblst_table[bblst_last];
2100 /* Compute update blocks and store them in bblst_table.
2101 For every split edge, look at the FROM block, and check
2102 all out edges. For each out edge that is not a split edge,
2103 add the TO block to the update block list. This list can end
2104 up with a lot of duplicates. We need to weed them out to avoid
2105 overrunning the end of the bblst_table. */
2106 update_blocks = (char *) alloca (n_basic_blocks);
2107 memset (update_blocks, 0, n_basic_blocks);
2110 for (j = 0; j < el.nr_members; j++)
2112 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
2113 fst_edge = nxt_edge = OUT_EDGES (check_block);
2116 if (! update_blocks[TO_BLOCK (nxt_edge)])
2118 for (k = 0; k < el.nr_members; k++)
2119 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
2122 if (k >= el.nr_members)
2124 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
2125 update_blocks[TO_BLOCK (nxt_edge)] = 1;
2130 nxt_edge = NEXT_OUT (nxt_edge);
2132 while (fst_edge != nxt_edge);
2134 sp->update_bbs.nr_members = update_idx;
2136 /* Make sure we didn't overrun the end of bblst_table. */
2137 if (bblst_last > bblst_size)
2142 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
2144 sp->is_speculative = 0;
2150 /* Print candidates info, for debugging purposes. Callable from debugger. */
2156 if (!candidate_table[i].is_valid)
2159 if (candidate_table[i].is_speculative)
2162 fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
2164 fprintf (sched_dump, "split path: ");
2165 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
2167 int b = candidate_table[i].split_bbs.first_member[j];
2169 fprintf (sched_dump, " %d ", b);
2171 fprintf (sched_dump, "\n");
2173 fprintf (sched_dump, "update path: ");
2174 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
2176 int b = candidate_table[i].update_bbs.first_member[j];
2178 fprintf (sched_dump, " %d ", b);
2180 fprintf (sched_dump, "\n");
2184 fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
2188 /* Print candidates info, for debugging purposes. Callable from debugger. */
2191 debug_candidates (trg)
2196 fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
2197 BB_TO_BLOCK (trg), trg);
2198 for (i = trg + 1; i < current_nr_blocks; i++)
2199 debug_candidate (i);
2202 /* Functions for speculative scheduing. */
2204 /* Return 0 if x is a set of a register alive in the beginning of one
2205 of the split-blocks of src, otherwise return 1. */
2208 check_live_1 (src, x)
2214 register rtx reg = SET_DEST (x);
2219 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2220 || GET_CODE (reg) == SIGN_EXTRACT
2221 || GET_CODE (reg) == STRICT_LOW_PART)
2222 reg = XEXP (reg, 0);
2224 if (GET_CODE (reg) == PARALLEL
2225 && GET_MODE (reg) == BLKmode)
2228 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2229 if (check_live_1 (src, XVECEXP (reg, 0, i)))
2234 if (GET_CODE (reg) != REG)
2237 regno = REGNO (reg);
2239 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2241 /* Global registers are assumed live. */
2246 if (regno < FIRST_PSEUDO_REGISTER)
2248 /* Check for hard registers. */
2249 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2252 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2254 int b = candidate_table[src].split_bbs.first_member[i];
2256 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
2266 /* Check for psuedo registers. */
2267 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2269 int b = candidate_table[src].split_bbs.first_member[i];
2271 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
2282 /* If x is a set of a register R, mark that R is alive in the beginning
2283 of every update-block of src. */
2286 update_live_1 (src, x)
2292 register rtx reg = SET_DEST (x);
2297 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2298 || GET_CODE (reg) == SIGN_EXTRACT
2299 || GET_CODE (reg) == STRICT_LOW_PART)
2300 reg = XEXP (reg, 0);
2302 if (GET_CODE (reg) == PARALLEL
2303 && GET_MODE (reg) == BLKmode)
2306 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2307 update_live_1 (src, XVECEXP (reg, 0, i));
2311 if (GET_CODE (reg) != REG)
2314 /* Global registers are always live, so the code below does not apply
2317 regno = REGNO (reg);
2319 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
2321 if (regno < FIRST_PSEUDO_REGISTER)
2323 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2326 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2328 int b = candidate_table[src].update_bbs.first_member[i];
2330 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
2337 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2339 int b = candidate_table[src].update_bbs.first_member[i];
2341 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
2347 /* Return 1 if insn can be speculatively moved from block src to trg,
2348 otherwise return 0. Called before first insertion of insn to
2349 ready-list or before the scheduling. */
2352 check_live (insn, src)
2356 /* Find the registers set by instruction. */
2357 if (GET_CODE (PATTERN (insn)) == SET
2358 || GET_CODE (PATTERN (insn)) == CLOBBER)
2359 return check_live_1 (src, PATTERN (insn));
2360 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2363 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2364 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2365 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2366 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
2375 /* Update the live registers info after insn was moved speculatively from
2376 block src to trg. */
2379 update_live (insn, src)
2383 /* Find the registers set by instruction. */
2384 if (GET_CODE (PATTERN (insn)) == SET
2385 || GET_CODE (PATTERN (insn)) == CLOBBER)
2386 update_live_1 (src, PATTERN (insn));
2387 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2390 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2391 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2392 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2393 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
2397 /* Exception Free Loads:
2399 We define five classes of speculative loads: IFREE, IRISKY,
2400 PFREE, PRISKY, and MFREE.
2402 IFREE loads are loads that are proved to be exception-free, just
2403 by examining the load insn. Examples for such loads are loads
2404 from TOC and loads of global data.
2406 IRISKY loads are loads that are proved to be exception-risky,
2407 just by examining the load insn. Examples for such loads are
2408 volatile loads and loads from shared memory.
2410 PFREE loads are loads for which we can prove, by examining other
2411 insns, that they are exception-free. Currently, this class consists
2412 of loads for which we are able to find a "similar load", either in
2413 the target block, or, if only one split-block exists, in that split
2414 block. Load2 is similar to load1 if both have same single base
2415 register. We identify only part of the similar loads, by finding
2416 an insn upon which both load1 and load2 have a DEF-USE dependence.
2418 PRISKY loads are loads for which we can prove, by examining other
2419 insns, that they are exception-risky. Currently we have two proofs for
2420 such loads. The first proof detects loads that are probably guarded by a
2421 test on the memory address. This proof is based on the
2422 backward and forward data dependence information for the region.
2423 Let load-insn be the examined load.
2424 Load-insn is PRISKY iff ALL the following hold:
2426 - insn1 is not in the same block as load-insn
2427 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2428 - test-insn is either a compare or a branch, not in the same block
2430 - load-insn is reachable from test-insn
2431 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2433 This proof might fail when the compare and the load are fed
2434 by an insn not in the region. To solve this, we will add to this
2435 group all loads that have no input DEF-USE dependence.
2437 The second proof detects loads that are directly or indirectly
2438 fed by a speculative load. This proof is affected by the
2439 scheduling process. We will use the flag fed_by_spec_load.
2440 Initially, all insns have this flag reset. After a speculative
2441 motion of an insn, if insn is either a load, or marked as
2442 fed_by_spec_load, we will also mark as fed_by_spec_load every
2443 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2444 load which is fed_by_spec_load is also PRISKY.
2446 MFREE (maybe-free) loads are all the remaining loads. They may be
2447 exception-free, but we cannot prove it.
2449 Now, all loads in IFREE and PFREE classes are considered
2450 exception-free, while all loads in IRISKY and PRISKY classes are
2451 considered exception-risky. As for loads in the MFREE class,
2452 these are considered either exception-free or exception-risky,
2453 depending on whether we are pessimistic or optimistic. We have
2454 to take the pessimistic approach to assure the safety of
2455 speculative scheduling, but we can take the optimistic approach
2456 by invoking the -fsched_spec_load_dangerous option. */
2458 enum INSN_TRAP_CLASS
2460 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
2461 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
2464 #define WORST_CLASS(class1, class2) \
2465 ((class1 > class2) ? class1 : class2)
2467 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2468 #define IS_REACHABLE(bb_from, bb_to) \
2470 || IS_RGN_ENTRY (bb_from) \
2471 || (bitset_member (ancestor_edges[bb_to], \
2472 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2475 /* Non-zero iff the address is comprised from at most 1 register. */
2476 #define CONST_BASED_ADDRESS_P(x) \
2477 (GET_CODE (x) == REG \
2478 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2479 || (GET_CODE (x) == LO_SUM)) \
2480 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2481 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2483 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2486 set_spec_fed (load_insn)
2491 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
2492 if (GET_MODE (link) == VOIDmode)
2493 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
2494 } /* set_spec_fed */
2496 /* On the path from the insn to load_insn_bb, find a conditional
2497 branch depending on insn, that guards the speculative load. */
2500 find_conditional_protection (insn, load_insn_bb)
2506 /* Iterate through DEF-USE forward dependences. */
2507 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2509 rtx next = XEXP (link, 0);
2510 if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
2511 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
2512 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
2513 && load_insn_bb != INSN_BB (next)
2514 && GET_MODE (link) == VOIDmode
2515 && (GET_CODE (next) == JUMP_INSN
2516 || find_conditional_protection (next, load_insn_bb)))
2520 } /* find_conditional_protection */
2522 /* Returns 1 if the same insn1 that participates in the computation
2523 of load_insn's address is feeding a conditional branch that is
2524 guarding on load_insn. This is true if we find a the two DEF-USE
2526 insn1 -> ... -> conditional-branch
2527 insn1 -> ... -> load_insn,
2528 and if a flow path exist:
2529 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2530 and if insn1 is on the path
2531 region-entry -> ... -> bb_trg -> ... load_insn.
2533 Locate insn1 by climbing on LOG_LINKS from load_insn.
2534 Locate the branch by following INSN_DEPEND from insn1. */
2537 is_conditionally_protected (load_insn, bb_src, bb_trg)
2543 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
2545 rtx insn1 = XEXP (link, 0);
2547 /* Must be a DEF-USE dependence upon non-branch. */
2548 if (GET_MODE (link) != VOIDmode
2549 || GET_CODE (insn1) == JUMP_INSN)
2552 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
2553 if (INSN_BB (insn1) == bb_src
2554 || (CONTAINING_RGN (BLOCK_NUM (insn1))
2555 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
2556 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
2557 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
2560 /* Now search for the conditional-branch. */
2561 if (find_conditional_protection (insn1, bb_src))
2564 /* Recursive step: search another insn1, "above" current insn1. */
2565 return is_conditionally_protected (insn1, bb_src, bb_trg);
2568 /* The chain does not exist. */
2570 } /* is_conditionally_protected */
2572 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2573 load_insn can move speculatively from bb_src to bb_trg. All the
2574 following must hold:
2576 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2577 (2) load_insn and load1 have a def-use dependence upon
2578 the same insn 'insn1'.
2579 (3) either load2 is in bb_trg, or:
2580 - there's only one split-block, and
2581 - load1 is on the escape path, and
2583 From all these we can conclude that the two loads access memory
2584 addresses that differ at most by a constant, and hence if moving
2585 load_insn would cause an exception, it would have been caused by
2589 is_pfree (load_insn, bb_src, bb_trg)
2594 register candidate *candp = candidate_table + bb_src;
2596 if (candp->split_bbs.nr_members != 1)
2597 /* Must have exactly one escape block. */
2600 for (back_link = LOG_LINKS (load_insn);
2601 back_link; back_link = XEXP (back_link, 1))
2603 rtx insn1 = XEXP (back_link, 0);
2605 if (GET_MODE (back_link) == VOIDmode)
2607 /* Found a DEF-USE dependence (insn1, load_insn). */
2610 for (fore_link = INSN_DEPEND (insn1);
2611 fore_link; fore_link = XEXP (fore_link, 1))
2613 rtx insn2 = XEXP (fore_link, 0);
2614 if (GET_MODE (fore_link) == VOIDmode)
2616 /* Found a DEF-USE dependence (insn1, insn2). */
2617 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
2618 /* insn2 not guaranteed to be a 1 base reg load. */
2621 if (INSN_BB (insn2) == bb_trg)
2622 /* insn2 is the similar load, in the target block. */
2625 if (*(candp->split_bbs.first_member) == BLOCK_NUM (insn2))
2626 /* insn2 is a similar load, in a split-block. */
2633 /* Couldn't find a similar load. */
2637 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2638 as found by analyzing insn's expression. */
2641 may_trap_exp (x, is_store)
2649 code = GET_CODE (x);
2659 /* The insn uses memory: a volatile load. */
2660 if (MEM_VOLATILE_P (x))
2662 /* An exception-free load. */
2663 if (!may_trap_p (x))
2665 /* A load with 1 base register, to be further checked. */
2666 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
2667 return PFREE_CANDIDATE;
2668 /* No info on the load, to be further checked. */
2669 return PRISKY_CANDIDATE;
2674 int i, insn_class = TRAP_FREE;
2676 /* Neither store nor load, check if it may cause a trap. */
2679 /* Recursive step: walk the insn... */
2680 fmt = GET_RTX_FORMAT (code);
2681 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2685 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
2686 insn_class = WORST_CLASS (insn_class, tmp_class);
2688 else if (fmt[i] == 'E')
2691 for (j = 0; j < XVECLEN (x, i); j++)
2693 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
2694 insn_class = WORST_CLASS (insn_class, tmp_class);
2695 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2699 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2706 /* Classifies insn for the purpose of verifying that it can be
2707 moved speculatively, by examining it's patterns, returning:
2708 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2709 TRAP_FREE: non-load insn.
2710 IFREE: load from a globaly safe location.
2711 IRISKY: volatile load.
2712 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2713 being either PFREE or PRISKY. */
2716 haifa_classify_insn (insn)
2719 rtx pat = PATTERN (insn);
2720 int tmp_class = TRAP_FREE;
2721 int insn_class = TRAP_FREE;
2724 if (GET_CODE (pat) == PARALLEL)
2726 int i, len = XVECLEN (pat, 0);
2728 for (i = len - 1; i >= 0; i--)
2730 code = GET_CODE (XVECEXP (pat, 0, i));
2734 /* Test if it is a 'store'. */
2735 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
2738 /* Test if it is a store. */
2739 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
2740 if (tmp_class == TRAP_RISKY)
2742 /* Test if it is a load. */
2744 WORST_CLASS (tmp_class,
2745 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 0));
2749 tmp_class = TRAP_RISKY;
2753 insn_class = WORST_CLASS (insn_class, tmp_class);
2754 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2760 code = GET_CODE (pat);
2764 /* Test if it is a 'store'. */
2765 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
2768 /* Test if it is a store. */
2769 tmp_class = may_trap_exp (SET_DEST (pat), 1);
2770 if (tmp_class == TRAP_RISKY)
2772 /* Test if it is a load. */
2774 WORST_CLASS (tmp_class,
2775 may_trap_exp (SET_SRC (pat), 0));
2779 tmp_class = TRAP_RISKY;
2783 insn_class = tmp_class;
2789 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2790 a load moved speculatively, or if load_insn is protected by
2791 a compare on load_insn's address). */
2794 is_prisky (load_insn, bb_src, bb_trg)
2798 if (FED_BY_SPEC_LOAD (load_insn))
2801 if (LOG_LINKS (load_insn) == NULL)
2802 /* Dependence may 'hide' out of the region. */
2805 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2811 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2812 Return 1 if insn is exception-free (and the motion is valid)
2816 is_exception_free (insn, bb_src, bb_trg)
2820 int insn_class = haifa_classify_insn (insn);
2822 /* Handle non-load insns. */
2833 if (!flag_schedule_speculative_load)
2835 IS_LOAD_INSN (insn) = 1;
2842 case PFREE_CANDIDATE:
2843 if (is_pfree (insn, bb_src, bb_trg))
2845 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2846 case PRISKY_CANDIDATE:
2847 if (!flag_schedule_speculative_load_dangerous
2848 || is_prisky (insn, bb_src, bb_trg))
2854 return flag_schedule_speculative_load_dangerous;
2857 /* Process an insn's memory dependencies. There are four kinds of
2860 (0) read dependence: read follows read
2861 (1) true dependence: read follows write
2862 (2) anti dependence: write follows read
2863 (3) output dependence: write follows write
2865 We are careful to build only dependencies which actually exist, and
2866 use transitivity to avoid building too many links. */
2868 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0
2871 HAIFA_INLINE static char
2872 find_insn_mem_list (insn, x, list, list1)
2878 if (XEXP (list, 0) == insn
2879 && XEXP (list1, 0) == x)
2881 list = XEXP (list, 1);
2882 list1 = XEXP (list1, 1);
2887 /* Compute the function units used by INSN. This caches the value
2888 returned by function_units_used. A function unit is encoded as the
2889 unit number if the value is non-negative and the compliment of a
2890 mask if the value is negative. A function unit index is the
2891 non-negative encoding. */
2897 register int unit = INSN_UNIT (insn);
2901 recog_memoized (insn);
2903 /* A USE insn, or something else we don't need to understand.
2904 We can't pass these directly to function_units_used because it will
2905 trigger a fatal error for unrecognizable insns. */
2906 if (INSN_CODE (insn) < 0)
2910 unit = function_units_used (insn);
2911 /* Increment non-negative values so we can cache zero. */
2915 /* We only cache 16 bits of the result, so if the value is out of
2916 range, don't cache it. */
2917 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
2919 || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
2920 INSN_UNIT (insn) = unit;
2922 return (unit > 0 ? unit - 1 : unit);
2925 /* Compute the blockage range for executing INSN on UNIT. This caches
2926 the value returned by the blockage_range_function for the unit.
2927 These values are encoded in an int where the upper half gives the
2928 minimum value and the lower half gives the maximum value. */
2930 HAIFA_INLINE static unsigned int
2931 blockage_range (unit, insn)
2935 unsigned int blockage = INSN_BLOCKAGE (insn);
2938 if ((int) UNIT_BLOCKED (blockage) != unit + 1)
2940 range = function_units[unit].blockage_range_function (insn);
2941 /* We only cache the blockage range for one unit and then only if
2943 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
2944 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
2947 range = BLOCKAGE_RANGE (blockage);
2952 /* A vector indexed by function unit instance giving the last insn to use
2953 the unit. The value of the function unit instance index for unit U
2954 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2955 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2957 /* A vector indexed by function unit instance giving the minimum time when
2958 the unit will unblock based on the maximum blockage cost. */
2959 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2961 /* A vector indexed by function unit number giving the number of insns
2962 that remain to use the unit. */
2963 static int unit_n_insns[FUNCTION_UNITS_SIZE];
2965 /* Access the unit_last_insn array. Used by the visualization code. */
2968 get_unit_last_insn (instance)
2971 return unit_last_insn[instance];
2974 /* Reset the function unit state to the null state. */
2979 memset ((char *) unit_last_insn, 0, sizeof (unit_last_insn));
2980 memset ((char *) unit_tick, 0, sizeof (unit_tick));
2981 memset ((char *) unit_n_insns, 0, sizeof (unit_n_insns));
2984 /* Return the issue-delay of an insn. */
2986 HAIFA_INLINE static int
2987 insn_issue_delay (insn)
2991 int unit = insn_unit (insn);
2993 /* Efficiency note: in fact, we are working 'hard' to compute a
2994 value that was available in md file, and is not available in
2995 function_units[] structure. It would be nice to have this
2996 value there, too. */
2999 if (function_units[unit].blockage_range_function &&
3000 function_units[unit].blockage_function)
3001 delay = function_units[unit].blockage_function (insn, insn);
3004 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3005 if ((unit & 1) != 0 && function_units[i].blockage_range_function
3006 && function_units[i].blockage_function)
3007 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
3012 /* Return the actual hazard cost of executing INSN on the unit UNIT,
3013 instance INSTANCE at time CLOCK if the previous actual hazard cost
3017 actual_hazard_this_instance (unit, instance, insn, clock, cost)
3018 int unit, instance, clock, cost;
3021 int tick = unit_tick[instance]; /* Issue time of the last issued insn. */
3023 if (tick - clock > cost)
3025 /* The scheduler is operating forward, so unit's last insn is the
3026 executing insn and INSN is the candidate insn. We want a
3027 more exact measure of the blockage if we execute INSN at CLOCK
3028 given when we committed the execution of the unit's last insn.
3030 The blockage value is given by either the unit's max blockage
3031 constant, blockage range function, or blockage function. Use
3032 the most exact form for the given unit. */
3034 if (function_units[unit].blockage_range_function)
3036 if (function_units[unit].blockage_function)
3037 tick += (function_units[unit].blockage_function
3038 (unit_last_insn[instance], insn)
3039 - function_units[unit].max_blockage);
3041 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
3042 - function_units[unit].max_blockage);
3044 if (tick - clock > cost)
3045 cost = tick - clock;
3050 /* Record INSN as having begun execution on the units encoded by UNIT at
3053 HAIFA_INLINE static void
3054 schedule_unit (unit, insn, clock)
3062 int instance = unit;
3063 #if MAX_MULTIPLICITY > 1
3064 /* Find the first free instance of the function unit and use that
3065 one. We assume that one is free. */
3066 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
3068 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
3070 instance += FUNCTION_UNITS_SIZE;
3073 unit_last_insn[instance] = insn;
3074 unit_tick[instance] = (clock + function_units[unit].max_blockage);
3077 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3078 if ((unit & 1) != 0)
3079 schedule_unit (i, insn, clock);
3082 /* Return the actual hazard cost of executing INSN on the units encoded by
3083 UNIT at time CLOCK if the previous actual hazard cost was COST. */
3085 HAIFA_INLINE static int
3086 actual_hazard (unit, insn, clock, cost)
3087 int unit, clock, cost;
3094 /* Find the instance of the function unit with the minimum hazard. */
3095 int instance = unit;
3096 int best_cost = actual_hazard_this_instance (unit, instance, insn,
3098 #if MAX_MULTIPLICITY > 1
3101 if (best_cost > cost)
3103 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
3105 instance += FUNCTION_UNITS_SIZE;
3106 this_cost = actual_hazard_this_instance (unit, instance, insn,
3108 if (this_cost < best_cost)
3110 best_cost = this_cost;
3111 if (this_cost <= cost)
3117 cost = MAX (cost, best_cost);
3120 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3121 if ((unit & 1) != 0)
3122 cost = actual_hazard (i, insn, clock, cost);
3127 /* Return the potential hazard cost of executing an instruction on the
3128 units encoded by UNIT if the previous potential hazard cost was COST.
3129 An insn with a large blockage time is chosen in preference to one
3130 with a smaller time; an insn that uses a unit that is more likely
3131 to be used is chosen in preference to one with a unit that is less
3132 used. We are trying to minimize a subsequent actual hazard. */
3134 HAIFA_INLINE static int
3135 potential_hazard (unit, insn, cost)
3140 unsigned int minb, maxb;
3144 minb = maxb = function_units[unit].max_blockage;
3147 if (function_units[unit].blockage_range_function)
3149 maxb = minb = blockage_range (unit, insn);
3150 maxb = MAX_BLOCKAGE_COST (maxb);
3151 minb = MIN_BLOCKAGE_COST (minb);
3156 /* Make the number of instructions left dominate. Make the
3157 minimum delay dominate the maximum delay. If all these
3158 are the same, use the unit number to add an arbitrary
3159 ordering. Other terms can be added. */
3160 ncost = minb * 0x40 + maxb;
3161 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
3168 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3169 if ((unit & 1) != 0)
3170 cost = potential_hazard (i, insn, cost);
3175 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3176 This is the number of cycles between instruction issue and
3177 instruction results. */
3179 HAIFA_INLINE static int
3180 insn_cost (insn, link, used)
3181 rtx insn, link, used;
3183 register int cost = INSN_COST (insn);
3187 recog_memoized (insn);
3189 /* A USE insn, or something else we don't need to understand.
3190 We can't pass these directly to result_ready_cost because it will
3191 trigger a fatal error for unrecognizable insns. */
3192 if (INSN_CODE (insn) < 0)
3194 INSN_COST (insn) = 1;
3199 cost = result_ready_cost (insn);
3204 INSN_COST (insn) = cost;
3208 /* In this case estimate cost without caring how insn is used. */
3209 if (link == 0 && used == 0)
3212 /* A USE insn should never require the value used to be computed. This
3213 allows the computation of a function's result and parameter values to
3214 overlap the return and call. */
3215 recog_memoized (used);
3216 if (INSN_CODE (used) < 0)
3217 LINK_COST_FREE (link) = 1;
3219 /* If some dependencies vary the cost, compute the adjustment. Most
3220 commonly, the adjustment is complete: either the cost is ignored
3221 (in the case of an output- or anti-dependence), or the cost is
3222 unchanged. These values are cached in the link as LINK_COST_FREE
3223 and LINK_COST_ZERO. */
3225 if (LINK_COST_FREE (link))
3228 else if (!LINK_COST_ZERO (link))
3232 ADJUST_COST (used, link, insn, ncost);
3235 LINK_COST_FREE (link) = 1;
3239 LINK_COST_ZERO (link) = 1;
3246 /* Compute the priority number for INSN. */
3255 if (! INSN_P (insn))
3258 if ((this_priority = INSN_PRIORITY (insn)) == 0)
3260 if (INSN_DEPEND (insn) == 0)
3261 this_priority = insn_cost (insn, 0, 0);
3263 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
3268 if (RTX_INTEGRATED_P (link))
3271 next = XEXP (link, 0);
3273 /* Critical path is meaningful in block boundaries only. */
3274 if (BLOCK_NUM (next) != BLOCK_NUM (insn))
3277 next_priority = insn_cost (insn, link, next) + priority (next);
3278 if (next_priority > this_priority)
3279 this_priority = next_priority;
3281 INSN_PRIORITY (insn) = this_priority;
3283 return this_priority;
3286 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3287 them to the unused_*_list variables, so that they can be reused. */
3290 free_pending_lists ()
3294 for (bb = 0; bb < current_nr_blocks; bb++)
3296 free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
3297 free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
3298 free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
3299 free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
3303 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3304 The MEM is a memory reference contained within INSN, which we are saving
3305 so that we can do memory aliasing on it. */
3308 add_insn_mem_dependence (deps, insn_list, mem_list, insn, mem)
3310 rtx *insn_list, *mem_list, insn, mem;
3314 link = alloc_INSN_LIST (insn, *insn_list);
3317 link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
3320 deps->pending_lists_length++;
3323 /* Make a dependency between every memory reference on the pending lists
3324 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3328 flush_pending_lists (deps, insn, only_write)
3336 while (deps->pending_read_insns && ! only_write)
3338 add_dependence (insn, XEXP (deps->pending_read_insns, 0),
3341 link = deps->pending_read_insns;
3342 deps->pending_read_insns = XEXP (deps->pending_read_insns, 1);
3343 free_INSN_LIST_node (link);
3345 link = deps->pending_read_mems;
3346 deps->pending_read_mems = XEXP (deps->pending_read_mems, 1);
3347 free_EXPR_LIST_node (link);
3349 while (deps->pending_write_insns)
3351 add_dependence (insn, XEXP (deps->pending_write_insns, 0),
3354 link = deps->pending_write_insns;
3355 deps->pending_write_insns = XEXP (deps->pending_write_insns, 1);
3356 free_INSN_LIST_node (link);
3358 link = deps->pending_write_mems;
3359 deps->pending_write_mems = XEXP (deps->pending_write_mems, 1);
3360 free_EXPR_LIST_node (link);
3362 deps->pending_lists_length = 0;
3364 /* last_pending_memory_flush is now a list of insns. */
3365 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
3366 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3368 free_INSN_LIST_list (&deps->last_pending_memory_flush);
3369 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
3372 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
3373 rtx, X, creating all dependencies generated by the write to the
3374 destination of X, and reads of everything mentioned. */
3377 sched_analyze_1 (deps, x, insn)
3383 register rtx dest = XEXP (x, 0);
3384 enum rtx_code code = GET_CODE (x);
3389 if (GET_CODE (dest) == PARALLEL
3390 && GET_MODE (dest) == BLKmode)
3393 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
3394 sched_analyze_1 (deps, XVECEXP (dest, 0, i), insn);
3395 if (GET_CODE (x) == SET)
3396 sched_analyze_2 (deps, SET_SRC (x), insn);
3400 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3401 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3403 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3405 /* The second and third arguments are values read by this insn. */
3406 sched_analyze_2 (deps, XEXP (dest, 1), insn);
3407 sched_analyze_2 (deps, XEXP (dest, 2), insn);
3409 dest = XEXP (dest, 0);
3412 if (GET_CODE (dest) == REG)
3416 regno = REGNO (dest);
3418 /* A hard reg in a wide mode may really be multiple registers.
3419 If so, mark all of them just like the first. */
3420 if (regno < FIRST_PSEUDO_REGISTER)
3422 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
3428 for (u = deps->reg_last_uses[r]; u; u = XEXP (u, 1))
3429 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3431 for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
3432 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3434 /* Clobbers need not be ordered with respect to one
3435 another, but sets must be ordered with respect to a
3439 free_INSN_LIST_list (&deps->reg_last_uses[r]);
3440 for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
3441 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3442 SET_REGNO_REG_SET (reg_pending_sets, r);
3445 SET_REGNO_REG_SET (reg_pending_clobbers, r);
3447 /* Function calls clobber all call_used regs. */
3448 if (global_regs[r] || (code == SET && call_used_regs[r]))
3449 for (u = deps->last_function_call; u; u = XEXP (u, 1))
3450 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3457 for (u = deps->reg_last_uses[regno]; u; u = XEXP (u, 1))
3458 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3460 for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
3461 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3465 free_INSN_LIST_list (&deps->reg_last_uses[regno]);
3466 for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3467 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3468 SET_REGNO_REG_SET (reg_pending_sets, regno);
3471 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
3473 /* Pseudos that are REG_EQUIV to something may be replaced
3474 by that during reloading. We need only add dependencies for
3475 the address in the REG_EQUIV note. */
3476 if (!reload_completed
3477 && reg_known_equiv_p[regno]
3478 && GET_CODE (reg_known_value[regno]) == MEM)
3479 sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
3481 /* Don't let it cross a call after scheduling if it doesn't
3482 already cross one. */
3484 if (REG_N_CALLS_CROSSED (regno) == 0)
3485 for (u = deps->last_function_call; u; u = XEXP (u, 1))
3486 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3489 else if (GET_CODE (dest) == MEM)
3491 /* Writing memory. */
3493 if (deps->pending_lists_length > 32)
3495 /* Flush all pending reads and writes to prevent the pending lists
3496 from getting any larger. Insn scheduling runs too slowly when
3497 these lists get long. The number 32 was chosen because it
3498 seems like a reasonable number. When compiling GCC with itself,
3499 this flush occurs 8 times for sparc, and 10 times for m88k using
3501 flush_pending_lists (deps, insn, 0);
3506 rtx pending, pending_mem;
3508 pending = deps->pending_read_insns;
3509 pending_mem = deps->pending_read_mems;
3512 if (anti_dependence (XEXP (pending_mem, 0), dest))
3513 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3515 pending = XEXP (pending, 1);
3516 pending_mem = XEXP (pending_mem, 1);
3519 pending = deps->pending_write_insns;
3520 pending_mem = deps->pending_write_mems;
3523 if (output_dependence (XEXP (pending_mem, 0), dest))
3524 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
3526 pending = XEXP (pending, 1);
3527 pending_mem = XEXP (pending_mem, 1);
3530 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
3531 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3533 add_insn_mem_dependence (deps, &deps->pending_write_insns,
3534 &deps->pending_write_mems, insn, dest);
3536 sched_analyze_2 (deps, XEXP (dest, 0), insn);
3539 /* Analyze reads. */
3540 if (GET_CODE (x) == SET)
3541 sched_analyze_2 (deps, SET_SRC (x), insn);
3544 /* Analyze the uses of memory and registers in rtx X in INSN. */
3547 sched_analyze_2 (deps, x, insn)
3554 register enum rtx_code code;
3555 register const char *fmt;
3560 code = GET_CODE (x);
3569 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3570 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3571 this does not mean that this insn is using cc0. */
3576 /* User of CC0 depends on immediately preceding insn. */
3577 set_sched_group_p (insn);
3584 int regno = REGNO (x);
3585 if (regno < FIRST_PSEUDO_REGISTER)
3589 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
3593 deps->reg_last_uses[r]
3594 = alloc_INSN_LIST (insn, deps->reg_last_uses[r]);
3596 for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
3597 add_dependence (insn, XEXP (u, 0), 0);
3599 /* ??? This should never happen. */
3600 for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
3601 add_dependence (insn, XEXP (u, 0), 0);
3603 if (call_used_regs[r] || global_regs[r])
3604 /* Function calls clobber all call_used regs. */
3605 for (u = deps->last_function_call; u; u = XEXP (u, 1))
3606 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3611 deps->reg_last_uses[regno]
3612 = alloc_INSN_LIST (insn, deps->reg_last_uses[regno]);
3614 for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
3615 add_dependence (insn, XEXP (u, 0), 0);
3617 /* ??? This should never happen. */
3618 for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3619 add_dependence (insn, XEXP (u, 0), 0);
3621 /* Pseudos that are REG_EQUIV to something may be replaced
3622 by that during reloading. We need only add dependencies for
3623 the address in the REG_EQUIV note. */
3624 if (!reload_completed
3625 && reg_known_equiv_p[regno]
3626 && GET_CODE (reg_known_value[regno]) == MEM)
3627 sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
3629 /* If the register does not already cross any calls, then add this
3630 insn to the sched_before_next_call list so that it will still
3631 not cross calls after scheduling. */
3632 if (REG_N_CALLS_CROSSED (regno) == 0)
3633 add_dependence (deps->sched_before_next_call, insn,
3641 /* Reading memory. */
3643 rtx pending, pending_mem;
3645 pending = deps->pending_read_insns;
3646 pending_mem = deps->pending_read_mems;
3649 if (read_dependence (XEXP (pending_mem, 0), x))
3650 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3652 pending = XEXP (pending, 1);
3653 pending_mem = XEXP (pending_mem, 1);
3656 pending = deps->pending_write_insns;
3657 pending_mem = deps->pending_write_mems;
3660 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
3662 add_dependence (insn, XEXP (pending, 0), 0);
3664 pending = XEXP (pending, 1);
3665 pending_mem = XEXP (pending_mem, 1);
3668 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
3669 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3671 /* Always add these dependencies to pending_reads, since
3672 this insn may be followed by a write. */
3673 add_insn_mem_dependence (deps, &deps->pending_read_insns,
3674 &deps->pending_read_mems, insn, x);
3676 /* Take advantage of tail recursion here. */
3677 sched_analyze_2 (deps, XEXP (x, 0), insn);
3681 /* Force pending stores to memory in case a trap handler needs them. */
3683 flush_pending_lists (deps, insn, 1);
3688 case UNSPEC_VOLATILE:
3692 /* Traditional and volatile asm instructions must be considered to use
3693 and clobber all hard registers, all pseudo-registers and all of
3694 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3696 Consider for instance a volatile asm that changes the fpu rounding
3697 mode. An insn should not be moved across this even if it only uses
3698 pseudo-regs because it might give an incorrectly rounded result. */
3699 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
3701 int max_reg = max_reg_num ();
3702 for (i = 0; i < max_reg; i++)
3704 for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
3705 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3706 free_INSN_LIST_list (&deps->reg_last_uses[i]);
3708 for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
3709 add_dependence (insn, XEXP (u, 0), 0);
3711 for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
3712 add_dependence (insn, XEXP (u, 0), 0);
3714 reg_pending_sets_all = 1;
3716 flush_pending_lists (deps, insn, 0);
3719 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3720 We can not just fall through here since then we would be confused
3721 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3722 traditional asms unlike their normal usage. */
3724 if (code == ASM_OPERANDS)
3726 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3727 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
3737 /* These both read and modify the result. We must handle them as writes
3738 to get proper dependencies for following instructions. We must handle
3739 them as reads to get proper dependencies from this to previous
3740 instructions. Thus we need to pass them to both sched_analyze_1
3741 and sched_analyze_2. We must call sched_analyze_2 first in order
3742 to get the proper antecedent for the read. */
3743 sched_analyze_2 (deps, XEXP (x, 0), insn);
3744 sched_analyze_1 (deps, x, insn);
3749 /* op0 = op0 + op1 */
3750 sched_analyze_2 (deps, XEXP (x, 0), insn);
3751 sched_analyze_2 (deps, XEXP (x, 1), insn);
3752 sched_analyze_1 (deps, x, insn);
3759 /* Other cases: walk the insn. */
3760 fmt = GET_RTX_FORMAT (code);
3761 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3764 sched_analyze_2 (deps, XEXP (x, i), insn);
3765 else if (fmt[i] == 'E')
3766 for (j = 0; j < XVECLEN (x, i); j++)
3767 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
3771 /* Analyze an INSN with pattern X to find all dependencies. */
3774 sched_analyze_insn (deps, x, insn, loop_notes)
3779 register RTX_CODE code = GET_CODE (x);
3781 int maxreg = max_reg_num ();
3784 if (code == COND_EXEC)
3786 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
3788 /* ??? Should be recording conditions so we reduce the number of
3789 false dependancies. */
3790 x = COND_EXEC_CODE (x);
3791 code = GET_CODE (x);
3793 if (code == SET || code == CLOBBER)
3794 sched_analyze_1 (deps, x, insn);
3795 else if (code == PARALLEL)
3798 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3800 rtx sub = XVECEXP (x, 0, i);
3801 code = GET_CODE (sub);
3803 if (code == COND_EXEC)
3805 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
3806 sub = COND_EXEC_CODE (sub);
3807 code = GET_CODE (sub);
3809 if (code == SET || code == CLOBBER)
3810 sched_analyze_1 (deps, sub, insn);
3812 sched_analyze_2 (deps, sub, insn);
3816 sched_analyze_2 (deps, x, insn);
3818 /* Mark registers CLOBBERED or used by called function. */
3819 if (GET_CODE (insn) == CALL_INSN)
3820 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3822 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3823 sched_analyze_1 (deps, XEXP (link, 0), insn);
3825 sched_analyze_2 (deps, XEXP (link, 0), insn);
3828 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3829 block, then we must be sure that no instructions are scheduled across it.
3830 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3831 become incorrect. */
3835 int max_reg = max_reg_num ();
3836 int schedule_barrier_found = 0;
3839 /* Update loop_notes with any notes from this insn. Also determine
3840 if any of the notes on the list correspond to instruction scheduling
3841 barriers (loop, eh & setjmp notes, but not range notes. */
3843 while (XEXP (link, 1))
3845 if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
3846 || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
3847 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
3848 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END
3849 || INTVAL (XEXP (link, 0)) == NOTE_INSN_SETJMP)
3850 schedule_barrier_found = 1;
3852 link = XEXP (link, 1);
3854 XEXP (link, 1) = REG_NOTES (insn);
3855 REG_NOTES (insn) = loop_notes;
3857 /* Add dependencies if a scheduling barrier was found. */
3858 if (schedule_barrier_found)
3860 for (i = 0; i < max_reg; i++)
3863 for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
3864 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3865 free_INSN_LIST_list (&deps->reg_last_uses[i]);
3867 for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
3868 add_dependence (insn, XEXP (u, 0), 0);
3870 for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
3871 add_dependence (insn, XEXP (u, 0), 0);
3873 reg_pending_sets_all = 1;
3875 flush_pending_lists (deps, insn, 0);
3880 /* Accumulate clobbers until the next set so that it will be output dependent
3881 on all of them. At the next set we can clear the clobber list, since
3882 subsequent sets will be output dependent on it. */
3883 EXECUTE_IF_SET_IN_REG_SET
3884 (reg_pending_sets, 0, i,
3886 free_INSN_LIST_list (&deps->reg_last_sets[i]);
3887 free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
3888 deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3890 EXECUTE_IF_SET_IN_REG_SET
3891 (reg_pending_clobbers, 0, i,
3893 deps->reg_last_clobbers[i]
3894 = alloc_INSN_LIST (insn, deps->reg_last_clobbers[i]);
3896 CLEAR_REG_SET (reg_pending_sets);
3897 CLEAR_REG_SET (reg_pending_clobbers);
3899 if (reg_pending_sets_all)
3901 for (i = 0; i < maxreg; i++)
3903 free_INSN_LIST_list (&deps->reg_last_sets[i]);
3904 free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
3905 deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3908 reg_pending_sets_all = 0;
3911 /* If a post-call group is still open, see if it should remain so.
3912 This insn must be a simple move of a hard reg to a pseudo or
3915 We must avoid moving these insns for correctness on
3916 SMALL_REGISTER_CLASS machines, and for special registers like
3917 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3918 hard regs for all targets. */
3920 if (deps->in_post_call_group_p)
3922 rtx tmp, set = single_set (insn);
3923 int src_regno, dest_regno;
3926 goto end_call_group;
3928 tmp = SET_DEST (set);
3929 if (GET_CODE (tmp) == SUBREG)
3930 tmp = SUBREG_REG (tmp);
3931 if (GET_CODE (tmp) == REG)
3932 dest_regno = REGNO (tmp);
3934 goto end_call_group;
3936 tmp = SET_SRC (set);
3937 if (GET_CODE (tmp) == SUBREG)
3938 tmp = SUBREG_REG (tmp);
3939 if (GET_CODE (tmp) == REG)
3940 src_regno = REGNO (tmp);
3942 goto end_call_group;
3944 if (src_regno < FIRST_PSEUDO_REGISTER
3945 || dest_regno < FIRST_PSEUDO_REGISTER)
3947 set_sched_group_p (insn);
3948 CANT_MOVE (insn) = 1;
3953 deps->in_post_call_group_p = 0;
3958 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3959 for every dependency. */
3962 sched_analyze (deps, head, tail)
3970 for (insn = head;; insn = NEXT_INSN (insn))
3972 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
3974 /* Clear out the stale LOG_LINKS from flow. */
3975 free_INSN_LIST_list (&LOG_LINKS (insn));
3977 /* Clear out stale SCHED_GROUP_P. */
3978 SCHED_GROUP_P (insn) = 0;
3980 /* Make each JUMP_INSN a scheduling barrier for memory
3982 if (GET_CODE (insn) == JUMP_INSN)
3983 deps->last_pending_memory_flush
3984 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
3985 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
3988 else if (GET_CODE (insn) == CALL_INSN)
3993 /* Clear out stale SCHED_GROUP_P. */
3994 SCHED_GROUP_P (insn) = 0;
3996 CANT_MOVE (insn) = 1;
3998 /* Clear out the stale LOG_LINKS from flow. */
3999 free_INSN_LIST_list (&LOG_LINKS (insn));
4001 /* Any instruction using a hard register which may get clobbered
4002 by a call needs to be marked as dependent on this call.
4003 This prevents a use of a hard return reg from being moved
4004 past a void call (i.e. it does not explicitly set the hard
4007 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
4008 all registers, not just hard registers, may be clobbered by this
4011 /* Insn, being a CALL_INSN, magically depends on
4012 `last_function_call' already. */
4014 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
4015 && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
4017 int max_reg = max_reg_num ();
4018 for (i = 0; i < max_reg; i++)
4020 for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
4021 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
4022 free_INSN_LIST_list (&deps->reg_last_uses[i]);
4024 for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
4025 add_dependence (insn, XEXP (u, 0), 0);
4027 for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
4028 add_dependence (insn, XEXP (u, 0), 0);
4030 reg_pending_sets_all = 1;
4032 /* Add a pair of REG_SAVE_NOTEs which we will later
4033 convert back into a NOTE_INSN_SETJMP note. See
4034 reemit_notes for why we use a pair of NOTEs. */
4035 REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE,
4038 REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE,
4039 GEN_INT (NOTE_INSN_SETJMP),
4044 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4045 if (call_used_regs[i] || global_regs[i])
4047 for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
4048 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
4050 for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
4051 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
4053 SET_REGNO_REG_SET (reg_pending_clobbers, i);
4057 /* For each insn which shouldn't cross a call, add a dependence
4058 between that insn and this call insn. */
4059 x = LOG_LINKS (deps->sched_before_next_call);
4062 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
4065 free_INSN_LIST_list (&LOG_LINKS (deps->sched_before_next_call));
4067 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
4070 /* In the absence of interprocedural alias analysis, we must flush
4071 all pending reads and writes, and start new dependencies starting
4072 from here. But only flush writes for constant calls (which may
4073 be passed a pointer to something we haven't written yet). */
4074 flush_pending_lists (deps, insn, CONST_CALL_P (insn));
4076 /* Depend this function call (actually, the user of this
4077 function call) on all hard register clobberage. */
4079 /* last_function_call is now a list of insns. */
4080 free_INSN_LIST_list (&deps->last_function_call);
4081 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
4083 /* Before reload, begin a post-call group, so as to keep the
4084 lifetimes of hard registers correct. */
4085 if (! reload_completed)
4086 deps->in_post_call_group_p = 1;
4089 /* See comments on reemit_notes as to why we do this.
4090 ??? Actually, the reemit_notes just say what is done, not why. */
4092 else if (GET_CODE (insn) == NOTE
4093 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_BEG
4094 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END))
4096 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn),
4098 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
4099 GEN_INT (NOTE_LINE_NUMBER (insn)),
4102 else if (GET_CODE (insn) == NOTE
4103 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
4104 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
4105 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
4106 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
4107 || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
4108 && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
4112 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
4113 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
4114 rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
4116 rtx_region = GEN_INT (0);
4118 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
4121 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
4122 GEN_INT (NOTE_LINE_NUMBER (insn)),
4124 CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
4133 /* Macros and functions for keeping the priority queue sorted, and
4134 dealing with queueing and dequeueing of instructions. */
4136 #define SCHED_SORT(READY, N_READY) \
4137 do { if ((N_READY) == 2) \
4138 swap_sort (READY, N_READY); \
4139 else if ((N_READY) > 2) \
4140 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4143 /* Returns a positive value if x is preferred; returns a negative value if
4144 y is preferred. Should never return 0, since that will make the sort
4148 rank_for_schedule (x, y)
4152 rtx tmp = *(const rtx *) y;
4153 rtx tmp2 = *(const rtx *) x;
4155 int tmp_class, tmp2_class, depend_count1, depend_count2;
4156 int val, priority_val, weight_val, info_val;
4158 /* Prefer insn with higher priority. */
4159 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
4161 return priority_val;
4163 /* Prefer an insn with smaller contribution to registers-pressure. */
4164 if (!reload_completed &&
4165 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
4166 return (weight_val);
4168 info_val = (*current_sched_info->rank) (tmp, tmp2);
4172 /* Compare insns based on their relation to the last-scheduled-insn. */
4173 if (last_scheduled_insn)
4175 /* Classify the instructions into three classes:
4176 1) Data dependent on last schedule insn.
4177 2) Anti/Output dependent on last scheduled insn.
4178 3) Independent of last scheduled insn, or has latency of one.
4179 Choose the insn from the highest numbered class if different. */
4180 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
4181 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
4183 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4188 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
4189 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
4191 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4196 if ((val = tmp2_class - tmp_class))
4200 /* Prefer the insn which has more later insns that depend on it.
4201 This gives the scheduler more freedom when scheduling later
4202 instructions at the expense of added register pressure. */
4204 for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
4208 for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
4211 val = depend_count2 - depend_count1;
4215 /* If insns are equally good, sort by INSN_LUID (original insn order),
4216 so that we make the sort stable. This minimizes instruction movement,
4217 thus minimizing sched's effect on debugging and cross-jumping. */
4218 return INSN_LUID (tmp) - INSN_LUID (tmp2);
4221 /* Resort the array A in which only element at index N may be out of order. */
4223 HAIFA_INLINE static void
4228 rtx insn = a[n - 1];
4231 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
4239 /* Add INSN to the insn queue so that it can be executed at least
4240 N_CYCLES after the currently executing insn. Preserve insns
4241 chain for debugging purposes. */
4243 HAIFA_INLINE static void
4244 queue_insn (insn, n_cycles)
4248 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
4249 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
4250 insn_queue[next_q] = link;
4253 if (sched_verbose >= 2)
4255 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
4256 (*current_sched_info->print_insn) (insn, 0));
4258 fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
4262 /* Return a pointer to the bottom of the ready list, i.e. the insn
4263 with the lowest priority. */
4265 HAIFA_INLINE static rtx *
4266 ready_lastpos (ready)
4267 struct ready_list *ready;
4269 if (ready->n_ready == 0)
4271 return ready->vec + ready->first - ready->n_ready + 1;
4274 /* Add an element INSN to the ready list so that it ends up with the lowest
4277 HAIFA_INLINE static void
4278 ready_add (ready, insn)
4279 struct ready_list *ready;
4282 if (ready->first == ready->n_ready)
4284 memmove (ready->vec + ready->veclen - ready->n_ready,
4285 ready_lastpos (ready),
4286 ready->n_ready * sizeof (rtx));
4287 ready->first = ready->veclen - 1;
4289 ready->vec[ready->first - ready->n_ready] = insn;
4293 /* Remove the element with the highest priority from the ready list and
4296 HAIFA_INLINE static rtx
4297 ready_remove_first (ready)
4298 struct ready_list *ready;
4301 if (ready->n_ready == 0)
4303 t = ready->vec[ready->first--];
4305 /* If the queue becomes empty, reset it. */
4306 if (ready->n_ready == 0)
4307 ready->first = ready->veclen - 1;
4311 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
4314 HAIFA_INLINE static void
4316 struct ready_list *ready;
4318 rtx *first = ready_lastpos (ready);
4319 SCHED_SORT (first, ready->n_ready);
4322 /* PREV is an insn that is ready to execute. Adjust its priority if that
4323 will help shorten or lengthen register lifetimes as appropriate. Also
4324 provide a hook for the target to tweek itself. */
4326 HAIFA_INLINE static void
4327 adjust_priority (prev)
4328 rtx prev ATTRIBUTE_UNUSED;
4330 /* ??? There used to be code here to try and estimate how an insn
4331 affected register lifetimes, but it did it by looking at REG_DEAD
4332 notes, which we removed in schedule_region. Nor did it try to
4333 take into account register pressure or anything useful like that.
4335 Revisit when we have a machine model to work with and not before. */
4337 #ifdef ADJUST_PRIORITY
4338 ADJUST_PRIORITY (prev);
4342 /* Clock at which the previous instruction was issued. */
4343 static int last_clock_var;
4345 /* INSN is the "currently executing insn". Launch each insn which was
4346 waiting on INSN. READY is the ready list which contains the insns
4347 that are ready to fire. CLOCK is the current cycle.
4351 schedule_insn (insn, ready, clock)
4353 struct ready_list *ready;
4359 unit = insn_unit (insn);
4361 if (sched_verbose >= 2)
4363 fprintf (sched_dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
4365 insn_print_units (insn);
4366 fprintf (sched_dump, "\n");
4369 if (sched_verbose && unit == -1)
4370 visualize_no_unit (insn);
4372 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
4373 schedule_unit (unit, insn, clock);
4375 if (INSN_DEPEND (insn) == 0)
4378 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
4380 rtx next = XEXP (link, 0);
4381 int cost = insn_cost (insn, link, next);
4383 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
4385 if ((INSN_DEP_COUNT (next) -= 1) == 0)
4387 int effective_cost = INSN_TICK (next) - clock;
4389 if (! (*current_sched_info->new_ready) (next))
4392 if (sched_verbose >= 2)
4394 fprintf (sched_dump, ";;\t\tdependences resolved: insn %s ",
4395 (*current_sched_info->print_insn) (next, 0));
4397 if (effective_cost < 1)
4398 fprintf (sched_dump, "into ready\n");
4400 fprintf (sched_dump, "into queue with cost=%d\n", effective_cost);
4403 /* Adjust the priority of NEXT and either put it on the ready
4404 list or queue it. */
4405 adjust_priority (next);
4406 if (effective_cost < 1)
4407 ready_add (ready, next);
4409 queue_insn (next, effective_cost);
4413 /* Annotate the instruction with issue information -- TImode
4414 indicates that the instruction is expected not to be able
4415 to issue on the same cycle as the previous insn. A machine
4416 may use this information to decide how the instruction should
4418 if (reload_completed && issue_rate > 1)
4420 PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
4421 last_clock_var = clock;
4425 /* Functions for handling of notes. */
4427 /* Delete notes beginning with INSN and put them in the chain
4428 of notes ended by NOTE_LIST.
4429 Returns the insn following the notes. */
4432 unlink_other_notes (insn, tail)
4435 rtx prev = PREV_INSN (insn);
4437 while (insn != tail && GET_CODE (insn) == NOTE)
4439 rtx next = NEXT_INSN (insn);
4440 /* Delete the note from its current position. */
4442 NEXT_INSN (prev) = next;
4444 PREV_INSN (next) = prev;
4446 /* See sched_analyze to see how these are handled. */
4447 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
4448 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
4449 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
4450 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_BEG
4451 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
4452 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
4453 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
4455 /* Insert the note at the end of the notes list. */
4456 PREV_INSN (insn) = note_list;
4458 NEXT_INSN (note_list) = insn;
4467 /* Delete line notes beginning with INSN. Record line-number notes so
4468 they can be reused. Returns the insn following the notes. */
4471 unlink_line_notes (insn, tail)
4474 rtx prev = PREV_INSN (insn);
4476 while (insn != tail && GET_CODE (insn) == NOTE)
4478 rtx next = NEXT_INSN (insn);
4480 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
4482 /* Delete the note from its current position. */
4484 NEXT_INSN (prev) = next;
4486 PREV_INSN (next) = prev;
4488 /* Record line-number notes so they can be reused. */
4489 LINE_NOTE (insn) = insn;
4499 /* Return the head and tail pointers of BB. */
4501 HAIFA_INLINE static void
4502 get_block_head_tail (b, headp, tailp)
4507 /* HEAD and TAIL delimit the basic block being scheduled. */
4508 rtx head = BLOCK_HEAD (b);
4509 rtx tail = BLOCK_END (b);
4511 /* Don't include any notes or labels at the beginning of the
4512 basic block, or notes at the ends of basic blocks. */
4513 while (head != tail)
4515 if (GET_CODE (head) == NOTE)
4516 head = NEXT_INSN (head);
4517 else if (GET_CODE (tail) == NOTE)
4518 tail = PREV_INSN (tail);
4519 else if (GET_CODE (head) == CODE_LABEL)
4520 head = NEXT_INSN (head);
4529 HAIFA_INLINE static void
4530 get_bb_head_tail (bb, headp, tailp)
4535 get_block_head_tail (BB_TO_BLOCK (bb), headp, tailp);
4538 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
4541 no_real_insns_p (head, tail)
4544 while (head != NEXT_INSN (tail))
4546 if (GET_CODE (head) != NOTE && GET_CODE (head) != CODE_LABEL)
4548 head = NEXT_INSN (head);
4553 /* Delete line notes from bb. Save them so they can be later restored
4554 (in restore_line_notes ()). */
4565 get_bb_head_tail (bb, &head, &tail);
4567 if (head == tail && (! INSN_P (head)))
4570 next_tail = NEXT_INSN (tail);
4571 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4575 /* Farm out notes, and maybe save them in NOTE_LIST.
4576 This is needed to keep the debugger from
4577 getting completely deranged. */
4578 if (GET_CODE (insn) == NOTE)
4581 insn = unlink_line_notes (insn, next_tail);
4587 if (insn == next_tail)
4593 /* Save line number notes for each insn in bb. */
4596 save_line_notes (bb)
4602 /* We must use the true line number for the first insn in the block
4603 that was computed and saved at the start of this pass. We can't
4604 use the current line number, because scheduling of the previous
4605 block may have changed the current line number. */
4607 rtx line = line_note_head[BB_TO_BLOCK (bb)];
4610 get_bb_head_tail (bb, &head, &tail);
4611 next_tail = NEXT_INSN (tail);
4613 for (insn = BLOCK_HEAD (BB_TO_BLOCK (bb));
4615 insn = NEXT_INSN (insn))
4616 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4619 LINE_NOTE (insn) = line;
4622 /* After bb was scheduled, insert line notes into the insns list. */
4625 restore_line_notes (bb)
4628 rtx line, note, prev, new;
4629 int added_notes = 0;
4631 rtx head, next_tail, insn;
4633 b = BB_TO_BLOCK (bb);
4635 head = BLOCK_HEAD (b);
4636 next_tail = NEXT_INSN (BLOCK_END (b));
4638 /* Determine the current line-number. We want to know the current
4639 line number of the first insn of the block here, in case it is
4640 different from the true line number that was saved earlier. If
4641 different, then we need a line number note before the first insn
4642 of this block. If it happens to be the same, then we don't want to
4643 emit another line number note here. */
4644 for (line = head; line; line = PREV_INSN (line))
4645 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4648 /* Walk the insns keeping track of the current line-number and inserting
4649 the line-number notes as needed. */
4650 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4651 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4653 /* This used to emit line number notes before every non-deleted note.
4654 However, this confuses a debugger, because line notes not separated
4655 by real instructions all end up at the same address. I can find no
4656 use for line number notes before other notes, so none are emitted. */
4657 else if (GET_CODE (insn) != NOTE
4658 && (note = LINE_NOTE (insn)) != 0
4661 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
4662 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
4665 prev = PREV_INSN (insn);
4666 if (LINE_NOTE (note))
4668 /* Re-use the original line-number note. */
4669 LINE_NOTE (note) = 0;
4670 PREV_INSN (note) = prev;
4671 NEXT_INSN (prev) = note;
4672 PREV_INSN (insn) = note;
4673 NEXT_INSN (note) = insn;
4678 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
4679 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
4680 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
4683 if (sched_verbose && added_notes)
4684 fprintf (sched_dump, ";; added %d line-number notes\n", added_notes);
4687 /* After scheduling the function, delete redundant line notes from the
4691 rm_redundant_line_notes ()
4694 rtx insn = get_insns ();
4695 int active_insn = 0;
4698 /* Walk the insns deleting redundant line-number notes. Many of these
4699 are already present. The remainder tend to occur at basic
4700 block boundaries. */
4701 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4702 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4704 /* If there are no active insns following, INSN is redundant. */
4705 if (active_insn == 0)
4708 NOTE_SOURCE_FILE (insn) = 0;
4709 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4711 /* If the line number is unchanged, LINE is redundant. */
4713 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
4714 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
4717 NOTE_SOURCE_FILE (line) = 0;
4718 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
4725 else if (!((GET_CODE (insn) == NOTE
4726 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
4727 || (GET_CODE (insn) == INSN
4728 && (GET_CODE (PATTERN (insn)) == USE
4729 || GET_CODE (PATTERN (insn)) == CLOBBER))))
4732 if (sched_verbose && notes)
4733 fprintf (sched_dump, ";; deleted %d line-number notes\n", notes);
4736 /* Delete notes between head and tail and put them in the chain
4737 of notes ended by NOTE_LIST. */
4740 rm_other_notes (head, tail)
4747 if (head == tail && (! INSN_P (head)))
4750 next_tail = NEXT_INSN (tail);
4751 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4755 /* Farm out notes, and maybe save them in NOTE_LIST.
4756 This is needed to keep the debugger from
4757 getting completely deranged. */
4758 if (GET_CODE (insn) == NOTE)
4762 insn = unlink_other_notes (insn, next_tail);
4768 if (insn == next_tail)
4774 /* Functions for computation of registers live/usage info. */
4776 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
4779 find_insn_reg_weight (b)
4782 rtx insn, next_tail, head, tail;
4784 get_block_head_tail (b, &head, &tail);
4785 next_tail = NEXT_INSN (tail);
4787 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4792 /* Handle register life information. */
4793 if (! INSN_P (insn))
4796 /* Increment weight for each register born here. */
4798 if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
4799 && register_operand (SET_DEST (x), VOIDmode))
4801 else if (GET_CODE (x) == PARALLEL)
4804 for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
4806 x = XVECEXP (PATTERN (insn), 0, j);
4807 if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
4808 && register_operand (SET_DEST (x), VOIDmode))
4813 /* Decrement weight for each register that dies here. */
4814 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
4816 if (REG_NOTE_KIND (x) == REG_DEAD
4817 || REG_NOTE_KIND (x) == REG_UNUSED)
4821 INSN_REG_WEIGHT (insn) = reg_weight;
4825 /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
4826 static int clock_var;
4828 /* Move insns that became ready to fire from queue to ready list. */
4831 queue_to_ready (ready)
4832 struct ready_list *ready;
4837 q_ptr = NEXT_Q (q_ptr);
4839 /* Add all pending insns that can be scheduled without stalls to the
4841 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
4843 insn = XEXP (link, 0);
4846 if (sched_verbose >= 2)
4847 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
4848 (*current_sched_info->print_insn) (insn, 0));
4850 ready_add (ready, insn);
4851 if (sched_verbose >= 2)
4852 fprintf (sched_dump, "moving to ready without stalls\n");
4854 insn_queue[q_ptr] = 0;
4856 /* If there are no ready insns, stall until one is ready and add all
4857 of the pending insns at that point to the ready list. */
4858 if (ready->n_ready == 0)
4860 register int stalls;
4862 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
4864 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
4866 for (; link; link = XEXP (link, 1))
4868 insn = XEXP (link, 0);
4871 if (sched_verbose >= 2)
4872 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
4873 (*current_sched_info->print_insn) (insn, 0));
4875 ready_add (ready, insn);
4876 if (sched_verbose >= 2)
4877 fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
4879 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
4886 if (sched_verbose && stalls)
4887 visualize_stall_cycles (stalls);
4888 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
4889 clock_var += stalls;
4893 /* Print the ready list for debugging purposes. Callable from debugger. */
4896 debug_ready_list (ready)
4897 struct ready_list *ready;
4902 if (ready->n_ready == 0)
4905 p = ready_lastpos (ready);
4906 for (i = 0; i < ready->n_ready; i++)
4907 fprintf (sched_dump, " %s", (*current_sched_info->print_insn) (p[i], 0));
4908 fprintf (sched_dump, "\n");
4911 /* The number of insns from the current block scheduled so far. */
4912 static int sched_target_n_insns;
4913 /* The number of insns from the current block to be scheduled in total. */
4914 static int target_n_insns;
4915 /* The number of insns from the entire region scheduled so far. */
4916 static int sched_n_insns;
4918 /* Implementations of the sched_info functions for region scheduling. */
4919 static void init_ready_list PARAMS ((struct ready_list *));
4920 static int can_schedule_ready_p PARAMS ((rtx));
4921 static int new_ready PARAMS ((rtx));
4922 static int schedule_more_p PARAMS ((void));
4923 static const char *rgn_print_insn PARAMS ((rtx, int));
4924 static int rgn_rank PARAMS ((rtx, rtx));
4926 /* Return nonzero if there are more insns that should be scheduled. */
4931 return sched_target_n_insns < target_n_insns;
4934 /* Add all insns that are initially ready to the ready list READY. Called
4935 once before scheduling a set of insns. */
4938 init_ready_list (ready)
4939 struct ready_list *ready;
4941 rtx prev_head = current_sched_info->prev_head;
4942 rtx next_tail = current_sched_info->next_tail;
4947 sched_target_n_insns = 0;
4950 /* Print debugging information. */
4951 if (sched_verbose >= 5)
4952 debug_dependencies ();
4954 /* Prepare current target block info. */
4955 if (current_nr_blocks > 1)
4957 candidate_table = (candidate *) xmalloc (current_nr_blocks
4958 * sizeof (candidate));
4961 /* bblst_table holds split blocks and update blocks for each block after
4962 the current one in the region. split blocks and update blocks are
4963 the TO blocks of region edges, so there can be at most rgn_nr_edges
4965 bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
4966 bblst_table = (int *) xmalloc (bblst_size * sizeof (int));
4968 bitlst_table_last = 0;
4969 bitlst_table_size = rgn_nr_edges;
4970 bitlst_table = (int *) xmalloc (rgn_nr_edges * sizeof (int));
4972 compute_trg_info (target_bb);
4975 /* Initialize ready list with all 'ready' insns in target block.
4976 Count number of insns in the target block being scheduled. */
4977 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
4981 if (! INSN_P (insn))
4983 next = NEXT_INSN (insn);
4985 if (INSN_DEP_COUNT (insn) == 0
4986 && (SCHED_GROUP_P (next) == 0 || ! INSN_P (next)))
4987 ready_add (ready, insn);
4988 if (!(SCHED_GROUP_P (insn)))
4992 /* Add to ready list all 'ready' insns in valid source blocks.
4993 For speculative insns, check-live, exception-free, and
4995 for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
4996 if (IS_VALID (bb_src))
5002 get_bb_head_tail (bb_src, &head, &tail);
5003 src_next_tail = NEXT_INSN (tail);
5006 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
5008 if (! INSN_P (insn))
5011 if (!CANT_MOVE (insn)
5012 && (!IS_SPECULATIVE_INSN (insn)
5013 || (insn_issue_delay (insn) <= 3
5014 && check_live (insn, bb_src)
5015 && is_exception_free (insn, bb_src, target_bb))))
5019 /* Note that we havn't squirrled away the notes for
5020 blocks other than the current. So if this is a
5021 speculative insn, NEXT might otherwise be a note. */
5022 next = next_nonnote_insn (insn);
5023 if (INSN_DEP_COUNT (insn) == 0
5025 || SCHED_GROUP_P (next) == 0
5026 || ! INSN_P (next)))
5027 ready_add (ready, insn);
5033 /* Called after taking INSN from the ready list. Returns nonzero if this
5034 insn can be scheduled, nonzero if we should silently discard it. */
5037 can_schedule_ready_p (insn)
5040 /* An interblock motion? */
5041 if (INSN_BB (insn) != target_bb)
5046 if (IS_SPECULATIVE_INSN (insn))
5048 if (!check_live (insn, INSN_BB (insn)))
5050 update_live (insn, INSN_BB (insn));
5052 /* For speculative load, mark insns fed by it. */
5053 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
5054 set_spec_fed (insn);
5060 /* Find the beginning of the scheduling group. */
5061 /* ??? Ought to update basic block here, but later bits of
5062 schedule_block assumes the original insn block is
5066 while (SCHED_GROUP_P (temp))
5067 temp = PREV_INSN (temp);
5069 /* Update source block boundaries. */
5070 b1 = BLOCK_FOR_INSN (temp);
5071 if (temp == b1->head && insn == b1->end)
5073 /* We moved all the insns in the basic block.
5074 Emit a note after the last insn and update the
5075 begin/end boundaries to point to the note. */
5076 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
5080 else if (insn == b1->end)
5082 /* We took insns from the end of the basic block,
5083 so update the end of block boundary so that it
5084 points to the first insn we did not move. */
5085 b1->end = PREV_INSN (temp);
5087 else if (temp == b1->head)
5089 /* We took insns from the start of the basic block,
5090 so update the start of block boundary so that
5091 it points to the first insn we did not move. */
5092 b1->head = NEXT_INSN (insn);
5097 /* In block motion. */
5098 sched_target_n_insns++;
5105 /* Called after INSN has all its dependencies resolved. Return nonzero
5106 if it should be moved to the ready list or the queue, or zero if we
5107 should silently discard it. */
5112 /* For speculative insns, before inserting to ready/queue,
5113 check live, exception-free, and issue-delay. */
5114 if (INSN_BB (next) != target_bb
5115 && (!IS_VALID (INSN_BB (next))
5117 || (IS_SPECULATIVE_INSN (next)
5118 && (insn_issue_delay (next) > 3
5119 || !check_live (next, INSN_BB (next))
5120 || !is_exception_free (next, INSN_BB (next), target_bb)))))
5125 /* Return a string that contains the insn uid and optionally anything else
5126 necessary to identify this insn in an output. It's valid to use a
5127 static buffer for this. The ALIGNED parameter should cause the string
5128 to be formatted so that multiple output lines will line up nicely. */
5131 rgn_print_insn (insn, aligned)
5135 static char tmp[80];
5138 sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
5141 sprintf (tmp, "%d", INSN_UID (insn));
5142 if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
5143 sprintf (tmp, "/b%d ", INSN_BB (insn));
5148 /* Compare priority of two insns. Return a positive number if the second
5149 insn is to be preferred for scheduling, and a negative one if the first
5150 is to be preferred. Zero if they are equally good. */
5153 rgn_rank (insn1, insn2)
5156 /* Some comparison make sense in interblock scheduling only. */
5157 if (INSN_BB (insn1) != INSN_BB (insn2))
5159 int spec_val, prob_val;
5161 /* Prefer an inblock motion on an interblock motion. */
5162 if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
5164 if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
5167 /* Prefer a useful motion on a speculative one. */
5168 spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
5172 /* Prefer a more probable (speculative) insn. */
5173 prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
5180 /* Used in schedule_insns to initialize current_sched_info for scheduling
5181 regions (or single basic blocks). */
5183 static struct sched_info region_sched_info =
5186 can_schedule_ready_p,
5197 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
5200 move_insn1 (insn, last)
5203 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
5204 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
5206 NEXT_INSN (insn) = NEXT_INSN (last);
5207 PREV_INSN (NEXT_INSN (last)) = insn;
5209 NEXT_INSN (last) = insn;
5210 PREV_INSN (insn) = last;
5215 /* Search INSN for REG_SAVE_NOTE note pairs for NOTE_INSN_SETJMP,
5216 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
5217 NOTEs. The REG_SAVE_NOTE note following first one is contains the
5218 saved value for NOTE_BLOCK_NUMBER which is useful for
5219 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
5220 output by the instruction scheduler. Return the new value of LAST. */
5223 reemit_notes (insn, last)
5230 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
5232 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
5234 enum insn_note note_type = INTVAL (XEXP (note, 0));
5236 if (note_type == NOTE_INSN_SETJMP)
5238 retval = emit_note_after (NOTE_INSN_SETJMP, insn);
5239 CONST_CALL_P (retval) = CONST_CALL_P (note);
5240 remove_note (insn, note);
5241 note = XEXP (note, 1);
5243 else if (note_type == NOTE_INSN_RANGE_BEG
5244 || note_type == NOTE_INSN_RANGE_END)
5246 last = emit_note_before (note_type, last);
5247 remove_note (insn, note);
5248 note = XEXP (note, 1);
5249 NOTE_RANGE_INFO (last) = XEXP (note, 0);
5253 last = emit_note_before (note_type, last);
5254 remove_note (insn, note);
5255 note = XEXP (note, 1);
5256 if (note_type == NOTE_INSN_EH_REGION_BEG
5257 || note_type == NOTE_INSN_EH_REGION_END)
5258 NOTE_EH_HANDLER (last) = INTVAL (XEXP (note, 0));
5260 remove_note (insn, note);
5266 /* Move INSN, and all insns which should be issued before it,
5267 due to SCHED_GROUP_P flag. Reemit notes if needed.
5269 Return the last insn emitted by the scheduler, which is the
5270 return value from the first call to reemit_notes. */
5273 move_insn (insn, last)
5278 /* If INSN has SCHED_GROUP_P set, then issue it and any other
5279 insns with SCHED_GROUP_P set first. */
5280 while (SCHED_GROUP_P (insn))
5282 rtx prev = PREV_INSN (insn);
5284 /* Move a SCHED_GROUP_P insn. */
5285 move_insn1 (insn, last);
5286 /* If this is the first call to reemit_notes, then record
5287 its return value. */
5288 if (retval == NULL_RTX)
5289 retval = reemit_notes (insn, insn);
5291 reemit_notes (insn, insn);
5295 /* Now move the first non SCHED_GROUP_P insn. */
5296 move_insn1 (insn, last);
5298 /* If this is the first call to reemit_notes, then record
5299 its return value. */
5300 if (retval == NULL_RTX)
5301 retval = reemit_notes (insn, insn);
5303 reemit_notes (insn, insn);
5308 /* Return an insn which represents a SCHED_GROUP, which is
5309 the last insn in the group. */
5320 insn = next_nonnote_insn (insn);
5322 while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
5327 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
5328 possibly bringing insns from subsequent blocks in the same region. */
5331 schedule_block (bb, rgn_n_insns)
5336 struct ready_list ready;
5339 /* Flow block of this bb. */
5340 int b = BB_TO_BLOCK (bb);
5342 /* Head/tail info for this block. */
5343 rtx prev_head = current_sched_info->prev_head;
5344 rtx next_tail = current_sched_info->next_tail;
5345 rtx head = NEXT_INSN (prev_head);
5346 rtx tail = PREV_INSN (next_tail);
5348 /* We used to have code to avoid getting parameters moved from hard
5349 argument registers into pseudos.
5351 However, it was removed when it proved to be of marginal benefit
5352 and caused problems because schedule_block and compute_forward_dependences
5353 had different notions of what the "head" insn was. */
5355 if (head == tail && (! INSN_P (head)))
5361 fprintf (sched_dump, ";; ======================================================\n");
5362 fprintf (sched_dump,
5363 ";; -- basic block %d from %d to %d -- %s reload\n",
5364 b, INSN_UID (BLOCK_HEAD (b)), INSN_UID (BLOCK_END (b)),
5365 (reload_completed ? "after" : "before"));
5366 fprintf (sched_dump, ";; ======================================================\n");
5367 fprintf (sched_dump, "\n");
5370 init_block_visualization ();
5375 /* Allocate the ready list. */
5376 ready.veclen = rgn_n_insns + 1 + ISSUE_RATE;
5377 ready.first = ready.veclen - 1;
5378 ready.vec = (rtx *) xmalloc (ready.veclen * sizeof (rtx));
5381 (*current_sched_info->init_ready_list) (&ready);
5383 #ifdef MD_SCHED_INIT
5384 MD_SCHED_INIT (sched_dump, sched_verbose);
5387 /* No insns scheduled in this block yet. */
5388 last_scheduled_insn = 0;
5390 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
5395 memset ((char *) insn_queue, 0, sizeof (insn_queue));
5397 /* Start just before the beginning of time. */
5400 /* We start inserting insns after PREV_HEAD. */
5403 /* Loop until all the insns in BB are scheduled. */
5404 while ((*current_sched_info->schedule_more_p) ())
5408 /* Add to the ready list all pending insns that can be issued now.
5409 If there are no ready insns, increment clock until one
5410 is ready and add all pending insns at that point to the ready
5412 queue_to_ready (&ready);
5414 if (ready.n_ready == 0)
5417 if (sched_verbose >= 2)
5419 fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
5420 debug_ready_list (&ready);
5423 /* Sort the ready list based on priority. */
5424 ready_sort (&ready);
5426 /* Allow the target to reorder the list, typically for
5427 better instruction bundling. */
5428 #ifdef MD_SCHED_REORDER
5429 MD_SCHED_REORDER (sched_dump, sched_verbose, ready_lastpos (&ready),
5430 ready.n_ready, clock_var, can_issue_more);
5432 can_issue_more = issue_rate;
5437 fprintf (sched_dump, "\n;;\tReady list (t =%3d): ", clock_var);
5438 debug_ready_list (&ready);
5441 /* Issue insns from ready list. */
5442 while (ready.n_ready != 0 && can_issue_more)
5444 /* Select and remove the insn from the ready list. */
5445 rtx insn = ready_remove_first (&ready);
5446 int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
5450 queue_insn (insn, cost);
5454 if (! (*current_sched_info->can_schedule_ready_p) (insn))
5457 last_scheduled_insn = insn;
5458 last = move_insn (insn, last);
5460 #ifdef MD_SCHED_VARIABLE_ISSUE
5461 MD_SCHED_VARIABLE_ISSUE (sched_dump, sched_verbose, insn,
5467 schedule_insn (insn, &ready, clock_var);
5470 /* Close this block after scheduling its jump. */
5471 if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
5477 visualize_scheduled_insns (clock_var);
5483 fprintf (sched_dump, ";;\tReady list (final): ");
5484 debug_ready_list (&ready);
5485 print_block_visualization ("");
5488 /* Sanity check -- queue must be empty now. Meaningless if region has
5490 if (current_sched_info->queue_must_finish_empty && q_size != 0)
5493 /* Update head/tail boundaries. */
5494 head = NEXT_INSN (prev_head);
5497 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
5498 previously found among the insns. Insert them at the beginning
5502 rtx note_head = note_list;
5504 while (PREV_INSN (note_head))
5506 note_head = PREV_INSN (note_head);
5509 PREV_INSN (note_head) = PREV_INSN (head);
5510 NEXT_INSN (PREV_INSN (head)) = note_head;
5511 PREV_INSN (head) = note_list;
5512 NEXT_INSN (note_list) = head;
5519 fprintf (sched_dump, ";; total time = %d\n;; new head = %d\n",
5520 clock_var, INSN_UID (head));
5521 fprintf (sched_dump, ";; new tail = %d\n\n",
5526 current_sched_info->head = head;
5527 current_sched_info->tail = tail;
5532 /* Print the bit-set of registers, S, callable from debugger. */
5535 debug_reg_vector (s)
5540 EXECUTE_IF_SET_IN_REG_SET (s, 0, regno,
5542 fprintf (sched_dump, " %d", regno);
5545 fprintf (sched_dump, "\n");
5548 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
5549 dependences from LOG_LINKS to build forward dependences in
5553 compute_forward_dependences (head, tail)
5558 enum reg_note dep_type;
5560 next_tail = NEXT_INSN (tail);
5561 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5563 if (! INSN_P (insn))
5566 insn = group_leader (insn);
5568 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
5570 rtx x = group_leader (XEXP (link, 0));
5573 if (x != XEXP (link, 0))
5576 #ifdef ENABLE_CHECKING
5577 /* If add_dependence is working properly there should never
5578 be notes, deleted insns or duplicates in the backward
5579 links. Thus we need not check for them here.
5581 However, if we have enabled checking we might as well go
5582 ahead and verify that add_dependence worked properly. */
5583 if (GET_CODE (x) == NOTE
5584 || INSN_DELETED_P (x)
5585 || (forward_dependency_cache != NULL
5586 && TEST_BIT (forward_dependency_cache[INSN_LUID (x)],
5588 || (forward_dependency_cache == NULL
5589 && find_insn_list (insn, INSN_DEPEND (x))))
5591 if (forward_dependency_cache != NULL)
5592 SET_BIT (forward_dependency_cache[INSN_LUID (x)],
5596 new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
5598 dep_type = REG_NOTE_KIND (link);
5599 PUT_REG_NOTE_KIND (new_link, dep_type);
5601 INSN_DEPEND (x) = new_link;
5602 INSN_DEP_COUNT (insn) += 1;
5607 /* Initialize variables for region data dependence analysis.
5608 n_bbs is the number of region blocks. */
5614 int maxreg = max_reg_num ();
5615 deps->reg_last_uses = (rtx *) xcalloc (maxreg, sizeof (rtx));
5616 deps->reg_last_sets = (rtx *) xcalloc (maxreg, sizeof (rtx));
5617 deps->reg_last_clobbers = (rtx *) xcalloc (maxreg, sizeof (rtx));
5619 deps->pending_read_insns = 0;
5620 deps->pending_read_mems = 0;
5621 deps->pending_write_insns = 0;
5622 deps->pending_write_mems = 0;
5623 deps->pending_lists_length = 0;
5624 deps->last_pending_memory_flush = 0;
5625 deps->last_function_call = 0;
5626 deps->in_post_call_group_p = 0;
5628 deps->sched_before_next_call
5629 = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
5630 NULL_RTX, 0, NULL_RTX, NULL_RTX);
5631 LOG_LINKS (deps->sched_before_next_call) = 0;
5634 /* Free insn lists found in DEPS. */
5640 int max_reg = max_reg_num ();
5643 /* Note this loop is executed max_reg * nr_regions times. It's first
5644 implementation accounted for over 90% of the calls to free_INSN_LIST_list.
5645 The list was empty for the vast majority of those calls. On the PA, not
5646 calling free_INSN_LIST_list in those cases improves -O2 compile times by
5648 for (i = 0; i < max_reg; ++i)
5650 if (deps->reg_last_clobbers[i])
5651 free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
5652 if (deps->reg_last_sets[i])
5653 free_INSN_LIST_list (&deps->reg_last_sets[i]);
5654 if (deps->reg_last_uses[i])
5655 free_INSN_LIST_list (&deps->reg_last_uses[i]);
5659 /* Add dependences so that branches are scheduled to run last in their
5663 add_branch_dependences (head, tail)
5668 /* For all branches, calls, uses, clobbers, and cc0 setters, force them
5669 to remain in order at the end of the block by adding dependencies and
5670 giving the last a high priority. There may be notes present, and
5671 prev_head may also be a note.
5673 Branches must obviously remain at the end. Calls should remain at the
5674 end since moving them results in worse register allocation. Uses remain
5675 at the end to ensure proper register allocation. cc0 setters remaim
5676 at the end because they can't be moved away from their cc0 user. */
5679 while (GET_CODE (insn) == CALL_INSN
5680 || GET_CODE (insn) == JUMP_INSN
5681 || (GET_CODE (insn) == INSN
5682 && (GET_CODE (PATTERN (insn)) == USE
5683 || GET_CODE (PATTERN (insn)) == CLOBBER
5685 || sets_cc0_p (PATTERN (insn))
5688 || GET_CODE (insn) == NOTE)
5690 if (GET_CODE (insn) != NOTE)
5693 && !find_insn_list (insn, LOG_LINKS (last)))
5695 add_dependence (last, insn, REG_DEP_ANTI);
5696 INSN_REF_COUNT (insn)++;
5699 CANT_MOVE (insn) = 1;
5702 /* Skip over insns that are part of a group.
5703 Make each insn explicitly depend on the previous insn.
5704 This ensures that only the group header will ever enter
5705 the ready queue (and, when scheduled, will automatically
5706 schedule the SCHED_GROUP_P block). */
5707 while (SCHED_GROUP_P (insn))
5709 rtx temp = prev_nonnote_insn (insn);
5710 add_dependence (insn, temp, REG_DEP_ANTI);
5715 /* Don't overrun the bounds of the basic block. */
5719 insn = PREV_INSN (insn);
5722 /* Make sure these insns are scheduled last in their block. */
5725 while (insn != head)
5727 insn = prev_nonnote_insn (insn);
5729 if (INSN_REF_COUNT (insn) != 0)
5732 add_dependence (last, insn, REG_DEP_ANTI);
5733 INSN_REF_COUNT (insn) = 1;
5735 /* Skip over insns that are part of a group. */
5736 while (SCHED_GROUP_P (insn))
5737 insn = prev_nonnote_insn (insn);
5741 /* After computing the dependencies for block BB, propagate the dependencies
5742 found in TMP_DEPS to the successors of the block. MAX_REG is the number
5745 propagate_deps (bb, tmp_deps, max_reg)
5747 struct deps *tmp_deps;
5750 int b = BB_TO_BLOCK (bb);
5753 rtx link_insn, link_mem;
5756 /* These lists should point to the right place, for correct
5758 bb_deps[bb].pending_read_insns = tmp_deps->pending_read_insns;
5759 bb_deps[bb].pending_read_mems = tmp_deps->pending_read_mems;
5760 bb_deps[bb].pending_write_insns = tmp_deps->pending_write_insns;
5761 bb_deps[bb].pending_write_mems = tmp_deps->pending_write_mems;
5763 /* bb's structures are inherited by its successors. */
5764 first_edge = e = OUT_EDGES (b);
5771 int b_succ = TO_BLOCK (e);
5772 int bb_succ = BLOCK_TO_BB (b_succ);
5773 struct deps *succ_deps = bb_deps + bb_succ;
5775 /* Only bbs "below" bb, in the same region, are interesting. */
5776 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
5783 for (reg = 0; reg < max_reg; reg++)
5785 /* reg-last-uses lists are inherited by bb_succ. */
5786 for (u = tmp_deps->reg_last_uses[reg]; u; u = XEXP (u, 1))
5788 if (find_insn_list (XEXP (u, 0),
5789 succ_deps->reg_last_uses[reg]))
5792 succ_deps->reg_last_uses[reg]
5793 = alloc_INSN_LIST (XEXP (u, 0),
5794 succ_deps->reg_last_uses[reg]);
5797 /* reg-last-defs lists are inherited by bb_succ. */
5798 for (u = tmp_deps->reg_last_sets[reg]; u; u = XEXP (u, 1))
5800 if (find_insn_list (XEXP (u, 0),
5801 succ_deps->reg_last_sets[reg]))
5804 succ_deps->reg_last_sets[reg]
5805 = alloc_INSN_LIST (XEXP (u, 0),
5806 succ_deps->reg_last_sets[reg]);
5809 for (u = tmp_deps->reg_last_clobbers[reg]; u; u = XEXP (u, 1))
5811 if (find_insn_list (XEXP (u, 0),
5812 succ_deps->reg_last_clobbers[reg]))
5815 succ_deps->reg_last_clobbers[reg]
5816 = alloc_INSN_LIST (XEXP (u, 0),
5817 succ_deps->reg_last_clobbers[reg]);
5821 /* Mem read/write lists are inherited by bb_succ. */
5822 link_insn = tmp_deps->pending_read_insns;
5823 link_mem = tmp_deps->pending_read_mems;
5826 if (!(find_insn_mem_list (XEXP (link_insn, 0),
5828 succ_deps->pending_read_insns,
5829 succ_deps->pending_read_mems)))
5830 add_insn_mem_dependence (succ_deps, &succ_deps->pending_read_insns,
5831 &succ_deps->pending_read_mems,
5832 XEXP (link_insn, 0), XEXP (link_mem, 0));
5833 link_insn = XEXP (link_insn, 1);
5834 link_mem = XEXP (link_mem, 1);
5837 link_insn = tmp_deps->pending_write_insns;
5838 link_mem = tmp_deps->pending_write_mems;
5841 if (!(find_insn_mem_list (XEXP (link_insn, 0),
5843 succ_deps->pending_write_insns,
5844 succ_deps->pending_write_mems)))
5845 add_insn_mem_dependence (succ_deps,
5846 &succ_deps->pending_write_insns,
5847 &succ_deps->pending_write_mems,
5848 XEXP (link_insn, 0), XEXP (link_mem, 0));
5850 link_insn = XEXP (link_insn, 1);
5851 link_mem = XEXP (link_mem, 1);
5854 /* last_function_call is inherited by bb_succ. */
5855 for (u = tmp_deps->last_function_call; u; u = XEXP (u, 1))
5857 if (find_insn_list (XEXP (u, 0),
5858 succ_deps->last_function_call))
5861 succ_deps->last_function_call
5862 = alloc_INSN_LIST (XEXP (u, 0),
5863 succ_deps->last_function_call);
5866 /* last_pending_memory_flush is inherited by bb_succ. */
5867 for (u = tmp_deps->last_pending_memory_flush; u; u = XEXP (u, 1))
5869 if (find_insn_list (XEXP (u, 0),
5870 succ_deps->last_pending_memory_flush))
5873 succ_deps->last_pending_memory_flush
5874 = alloc_INSN_LIST (XEXP (u, 0),
5875 succ_deps->last_pending_memory_flush);
5878 /* sched_before_next_call is inherited by bb_succ. */
5879 x = LOG_LINKS (tmp_deps->sched_before_next_call);
5880 for (; x; x = XEXP (x, 1))
5881 add_dependence (succ_deps->sched_before_next_call,
5882 XEXP (x, 0), REG_DEP_ANTI);
5886 while (e != first_edge);
5889 /* Compute backward dependences inside bb. In a multiple blocks region:
5890 (1) a bb is analyzed after its predecessors, and (2) the lists in
5891 effect at the end of bb (after analyzing for bb) are inherited by
5894 Specifically for reg-reg data dependences, the block insns are
5895 scanned by sched_analyze () top-to-bottom. Two lists are
5896 maintained by sched_analyze (): reg_last_sets[] for register DEFs,
5897 and reg_last_uses[] for register USEs.
5899 When analysis is completed for bb, we update for its successors:
5900 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
5901 ; - USES[succ] = Union (USES [succ], DEFS [bb])
5903 The mechanism for computing mem-mem data dependence is very
5904 similar, and the result is interblock dependences in the region. */
5907 compute_block_backward_dependences (bb)
5911 int max_reg = max_reg_num ();
5912 struct deps tmp_deps;
5914 tmp_deps = bb_deps[bb];
5916 /* Do the analysis for this block. */
5917 get_bb_head_tail (bb, &head, &tail);
5918 sched_analyze (&tmp_deps, head, tail);
5919 add_branch_dependences (head, tail);
5921 if (current_nr_blocks > 1)
5922 propagate_deps (bb, &tmp_deps, max_reg);
5924 /* Free up the INSN_LISTs. */
5925 free_deps (&tmp_deps);
5927 /* Assert that we won't need bb_reg_last_* for this block anymore. */
5928 free (bb_deps[bb].reg_last_uses);
5929 free (bb_deps[bb].reg_last_sets);
5930 free (bb_deps[bb].reg_last_clobbers);
5931 bb_deps[bb].reg_last_uses = 0;
5932 bb_deps[bb].reg_last_sets = 0;
5933 bb_deps[bb].reg_last_clobbers = 0;
5936 /* Print dependences for debugging, callable from debugger. */
5939 debug_dependencies ()
5943 fprintf (sched_dump, ";; --------------- forward dependences: ------------ \n");
5944 for (bb = 0; bb < current_nr_blocks; bb++)
5952 get_bb_head_tail (bb, &head, &tail);
5953 next_tail = NEXT_INSN (tail);
5954 fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
5955 BB_TO_BLOCK (bb), bb);
5957 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
5958 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
5959 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
5960 "----", "----", "--", "---", "----", "----", "--------", "-----");
5961 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5966 if (! INSN_P (insn))
5969 fprintf (sched_dump, ";; %6d ", INSN_UID (insn));
5970 if (GET_CODE (insn) == NOTE)
5972 n = NOTE_LINE_NUMBER (insn);
5974 fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
5976 fprintf (sched_dump, "line %d, file %s\n", n,
5977 NOTE_SOURCE_FILE (insn));
5980 fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
5984 unit = insn_unit (insn);
5986 || function_units[unit].blockage_range_function == 0) ? 0 :
5987 function_units[unit].blockage_range_function (insn);
5988 fprintf (sched_dump,
5989 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
5990 (SCHED_GROUP_P (insn) ? "+" : " "),
5994 INSN_DEP_COUNT (insn),
5995 INSN_PRIORITY (insn),
5996 insn_cost (insn, 0, 0),
5997 (int) MIN_BLOCKAGE_COST (range),
5998 (int) MAX_BLOCKAGE_COST (range));
5999 insn_print_units (insn);
6000 fprintf (sched_dump, "\t: ");
6001 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
6002 fprintf (sched_dump, "%d ", INSN_UID (XEXP (link, 0)));
6003 fprintf (sched_dump, "\n");
6007 fprintf (sched_dump, "\n");
6010 /* Set_priorities: compute priority of each insn in the block. */
6023 get_bb_head_tail (bb, &head, &tail);
6024 prev_head = PREV_INSN (head);
6026 if (head == tail && (! INSN_P (head)))
6030 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
6032 if (GET_CODE (insn) == NOTE)
6035 if (!(SCHED_GROUP_P (insn)))
6037 (void) priority (insn);
6043 /* Schedule a region. A region is either an inner loop, a loop-free
6044 subroutine, or a single basic block. Each bb in the region is
6045 scheduled after its flow predecessors. */
6048 schedule_region (rgn)
6052 int rgn_n_insns = 0;
6053 int sched_rgn_n_insns = 0;
6054 regset_head reg_pending_sets_head;
6055 regset_head reg_pending_clobbers_head;
6057 /* Set variables for the current region. */
6058 current_nr_blocks = RGN_NR_BLOCKS (rgn);
6059 current_blocks = RGN_BLOCKS (rgn);
6061 reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head);
6062 reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head);
6063 reg_pending_sets_all = 0;
6065 /* Initializations for region data dependence analyisis. */
6066 bb_deps = (struct deps *) xmalloc (sizeof (struct deps) * current_nr_blocks);
6067 for (bb = 0; bb < current_nr_blocks; bb++)
6068 init_deps (bb_deps + bb);
6070 /* Compute LOG_LINKS. */
6071 for (bb = 0; bb < current_nr_blocks; bb++)
6072 compute_block_backward_dependences (bb);
6074 /* Compute INSN_DEPEND. */
6075 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
6078 get_bb_head_tail (bb, &head, &tail);
6080 compute_forward_dependences (head, tail);
6083 /* Set priorities. */
6084 for (bb = 0; bb < current_nr_blocks; bb++)
6085 rgn_n_insns += set_priorities (bb);
6087 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
6088 if (current_nr_blocks > 1)
6092 prob = (float *) xmalloc ((current_nr_blocks) * sizeof (float));
6094 bbset_size = current_nr_blocks / HOST_BITS_PER_WIDE_INT + 1;
6095 dom = (bbset *) xmalloc (current_nr_blocks * sizeof (bbset));
6096 for (i = 0; i < current_nr_blocks; i++)
6097 dom[i] = (bbset) xcalloc (bbset_size, sizeof (HOST_WIDE_INT));
6101 edge_to_bit = (int *) xmalloc (nr_edges * sizeof (int));
6102 for (i = 1; i < nr_edges; i++)
6103 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
6104 EDGE_TO_BIT (i) = rgn_nr_edges++;
6105 rgn_edges = (int *) xmalloc (rgn_nr_edges * sizeof (int));
6108 for (i = 1; i < nr_edges; i++)
6109 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
6110 rgn_edges[rgn_nr_edges++] = i;
6113 edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
6114 edgeset_bitsize = rgn_nr_edges;
6115 pot_split = (edgeset *) xmalloc (current_nr_blocks * sizeof (edgeset));
6117 = (edgeset *) xmalloc (current_nr_blocks * sizeof (edgeset));
6118 for (i = 0; i < current_nr_blocks; i++)
6121 (edgeset) xcalloc (edgeset_size, sizeof (HOST_WIDE_INT));
6123 (edgeset) xcalloc (edgeset_size, sizeof (HOST_WIDE_INT));
6126 /* Compute probabilities, dominators, split_edges. */
6127 for (bb = 0; bb < current_nr_blocks; bb++)
6128 compute_dom_prob_ps (bb);
6131 /* Now we can schedule all blocks. */
6132 for (bb = 0; bb < current_nr_blocks; bb++)
6135 int b = BB_TO_BLOCK (bb);
6137 get_block_head_tail (b, &head, &tail);
6139 if (no_real_insns_p (head, tail))
6142 current_sched_info->prev_head = PREV_INSN (head);
6143 current_sched_info->next_tail = NEXT_INSN (tail);
6145 if (write_symbols != NO_DEBUG)
6147 save_line_notes (bb);
6151 /* rm_other_notes only removes notes which are _inside_ the
6152 block---that is, it won't remove notes before the first real insn
6153 or after the last real insn of the block. So if the first insn
6154 has a REG_SAVE_NOTE which would otherwise be emitted before the
6155 insn, it is redundant with the note before the start of the
6156 block, and so we have to take it out.
6158 FIXME: Probably the same thing should be done with REG_SAVE_NOTEs
6159 referencing NOTE_INSN_SETJMP at the end of the block. */
6164 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
6165 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
6167 if (INTVAL (XEXP (note, 0)) != NOTE_INSN_SETJMP)
6169 remove_note (head, note);
6170 note = XEXP (note, 1);
6171 remove_note (head, note);
6174 note = XEXP (note, 1);
6178 /* Remove remaining note insns from the block, save them in
6179 note_list. These notes are restored at the end of
6180 schedule_block (). */
6182 rm_other_notes (head, tail);
6186 current_sched_info->queue_must_finish_empty
6187 = current_nr_blocks > 1 && !flag_schedule_interblock;
6189 schedule_block (bb, rgn_n_insns);
6190 sched_rgn_n_insns += sched_n_insns;
6192 /* Update target block boundaries. */
6193 if (head == BLOCK_HEAD (b))
6194 BLOCK_HEAD (b) = current_sched_info->head;
6195 if (tail == BLOCK_END (b))
6196 BLOCK_END (b) = current_sched_info->tail;
6199 if (current_nr_blocks > 1)
6201 free (candidate_table);
6203 free (bitlst_table);
6207 /* Sanity check: verify that all region insns were scheduled. */
6208 if (sched_rgn_n_insns != rgn_n_insns)
6211 /* Restore line notes. */
6212 if (write_symbols != NO_DEBUG)
6214 for (bb = 0; bb < current_nr_blocks; bb++)
6215 restore_line_notes (bb);
6218 /* Done with this region. */
6219 free_pending_lists ();
6221 FREE_REG_SET (reg_pending_sets);
6222 FREE_REG_SET (reg_pending_clobbers);
6226 if (current_nr_blocks > 1)
6231 for (i = 0; i < current_nr_blocks; ++i)
6234 free (pot_split[i]);
6235 free (ancestor_edges[i]);
6241 free (ancestor_edges);
6245 /* Initialize some global state for the scheduler. DUMP_FILE is to be used
6246 for debugging output. */
6249 sched_init (dump_file)
6255 /* Disable speculative loads in their presence if cc0 defined. */
6257 flag_schedule_speculative_load = 0;
6260 /* Set dump and sched_verbose for the desired debugging output. If no
6261 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
6262 For -fsched-verbose=N, N>=10, print everything to stderr. */
6263 sched_verbose = sched_verbose_param;
6264 if (sched_verbose_param == 0 && dump_file)
6266 sched_dump = ((sched_verbose_param >= 10 || !dump_file)
6267 ? stderr : dump_file);
6269 /* Initialize issue_rate. */
6270 issue_rate = ISSUE_RATE;
6272 split_all_insns (1);
6274 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
6275 pseudos which do not cross calls. */
6276 old_max_uid = get_max_uid () + 1;
6278 h_i_d = (struct haifa_insn_data *) xcalloc (old_max_uid, sizeof (*h_i_d));
6282 for (b = 0; b < n_basic_blocks; b++)
6283 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
6285 INSN_LUID (insn) = luid;
6287 /* Increment the next luid, unless this is a note. We don't
6288 really need separate IDs for notes and we don't want to
6289 schedule differently depending on whether or not there are
6290 line-number notes, i.e., depending on whether or not we're
6291 generating debugging information. */
6292 if (GET_CODE (insn) != NOTE)
6295 if (insn == BLOCK_END (b))
6299 init_dependency_caches (luid);
6301 compute_bb_for_insn (old_max_uid);
6303 init_alias_analysis ();
6305 if (write_symbols != NO_DEBUG)
6309 line_note_head = (rtx *) xcalloc (n_basic_blocks, sizeof (rtx));
6311 /* Save-line-note-head:
6312 Determine the line-number at the start of each basic block.
6313 This must be computed and saved now, because after a basic block's
6314 predecessor has been scheduled, it is impossible to accurately
6315 determine the correct line number for the first insn of the block. */
6317 for (b = 0; b < n_basic_blocks; b++)
6318 for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line))
6319 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
6321 line_note_head[b] = line;
6326 /* Find units used in this fuction, for visualization. */
6328 init_target_units ();
6330 /* ??? Add a NOTE after the last insn of the last basic block. It is not
6331 known why this is done. */
6333 insn = BLOCK_END (n_basic_blocks - 1);
6334 if (NEXT_INSN (insn) == 0
6335 || (GET_CODE (insn) != NOTE
6336 && GET_CODE (insn) != CODE_LABEL
6337 /* Don't emit a NOTE if it would end up between an unconditional
6338 jump and a BARRIER. */
6339 && !(GET_CODE (insn) == JUMP_INSN
6340 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
6341 emit_note_after (NOTE_INSN_DELETED, BLOCK_END (n_basic_blocks - 1));
6343 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
6344 removing death notes. */
6345 for (b = n_basic_blocks - 1; b >= 0; b--)
6346 find_insn_reg_weight (b);
6349 /* Indexed by region, holds the number of death notes found in that region.
6350 Used for consistency checks. */
6351 static int *deaths_in_region;
6353 /* Initialize data structures for region scheduling. */
6362 rgn_table = (region *) xmalloc ((n_basic_blocks) * sizeof (region));
6363 rgn_bb_table = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
6364 block_to_bb = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
6365 containing_rgn = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
6367 blocks = sbitmap_alloc (n_basic_blocks);
6369 /* Compute regions for scheduling. */
6370 if (reload_completed
6371 || n_basic_blocks == 1
6372 || !flag_schedule_interblock)
6374 find_single_block_region ();
6378 /* Verify that a 'good' control flow graph can be built. */
6379 if (is_cfg_nonregular ())
6381 find_single_block_region ();
6386 struct edge_list *edge_list;
6388 dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
6390 /* The scheduler runs after flow; therefore, we can't blindly call
6391 back into find_basic_blocks since doing so could invalidate the
6392 info in global_live_at_start.
6394 Consider a block consisting entirely of dead stores; after life
6395 analysis it would be a block of NOTE_INSN_DELETED notes. If
6396 we call find_basic_blocks again, then the block would be removed
6397 entirely and invalidate our the register live information.
6399 We could (should?) recompute register live information. Doing
6400 so may even be beneficial. */
6401 edge_list = create_edge_list ();
6403 /* Compute the dominators and post dominators. */
6404 calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
6406 /* build_control_flow will return nonzero if it detects unreachable
6407 blocks or any other irregularity with the cfg which prevents
6408 cross block scheduling. */
6409 if (build_control_flow (edge_list) != 0)
6410 find_single_block_region ();
6412 find_rgns (edge_list, dom);
6414 if (sched_verbose >= 3)
6417 /* We are done with flow's edge list. */
6418 free_edge_list (edge_list);
6420 /* For now. This will move as more and more of haifa is converted
6421 to using the cfg code in flow.c. */
6426 deaths_in_region = (int *) xmalloc (sizeof (int) * nr_regions);
6428 /* Remove all death notes from the subroutine. */
6429 for (rgn = 0; rgn < nr_regions; rgn++)
6433 sbitmap_zero (blocks);
6434 for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
6435 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]);
6437 deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1);
6440 sbitmap_free (blocks);
6443 /* The one entry point in this file. DUMP_FILE is the dump file for
6447 schedule_insns (dump_file)
6450 sbitmap large_region_blocks, blocks;
6452 int any_large_regions;
6454 /* Taking care of this degenerate case makes the rest of
6455 this code simpler. */
6456 if (n_basic_blocks == 0)
6462 sched_init (dump_file);
6466 current_sched_info = ®ion_sched_info;
6468 /* Schedule every region in the subroutine. */
6469 for (rgn = 0; rgn < nr_regions; rgn++)
6470 schedule_region (rgn);
6472 /* Update life analysis for the subroutine. Do single block regions
6473 first so that we can verify that live_at_start didn't change. Then
6474 do all other blocks. */
6475 /* ??? There is an outside possibility that update_life_info, or more
6476 to the point propagate_block, could get called with non-zero flags
6477 more than once for one basic block. This would be kinda bad if it
6478 were to happen, since REG_INFO would be accumulated twice for the
6479 block, and we'd have twice the REG_DEAD notes.
6481 I'm fairly certain that this _shouldn't_ happen, since I don't think
6482 that live_at_start should change at region heads. Not sure what the
6483 best way to test for this kind of thing... */
6485 allocate_reg_life_data ();
6486 compute_bb_for_insn (old_max_uid);
6488 any_large_regions = 0;
6489 large_region_blocks = sbitmap_alloc (n_basic_blocks);
6490 sbitmap_ones (large_region_blocks);
6492 blocks = sbitmap_alloc (n_basic_blocks);
6494 for (rgn = 0; rgn < nr_regions; rgn++)
6495 if (RGN_NR_BLOCKS (rgn) > 1)
6496 any_large_regions = 1;
6499 sbitmap_zero (blocks);
6500 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
6501 RESET_BIT (large_region_blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
6503 /* Don't update reg info after reload, since that affects
6504 regs_ever_live, which should not change after reload. */
6505 update_life_info (blocks, UPDATE_LIFE_LOCAL,
6506 (reload_completed ? PROP_DEATH_NOTES
6507 : PROP_DEATH_NOTES | PROP_REG_INFO));
6509 #ifndef HAVE_conditional_execution
6510 /* ??? REG_DEAD notes only exist for unconditional deaths. We need
6511 a count of the conditional plus unconditional deaths for this to
6513 /* In the single block case, the count of registers that died should
6514 not have changed during the schedule. */
6515 if (count_or_remove_death_notes (blocks, 0) != deaths_in_region[rgn])
6520 if (any_large_regions)
6522 update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL,
6523 PROP_DEATH_NOTES | PROP_REG_INFO);
6526 /* Reposition the prologue and epilogue notes in case we moved the
6527 prologue/epilogue insns. */
6528 if (reload_completed)
6529 reposition_prologue_and_epilogue_notes (get_insns ());
6531 /* Delete redundant line notes. */
6532 if (write_symbols != NO_DEBUG)
6533 rm_redundant_line_notes ();
6537 if (reload_completed == 0 && flag_schedule_interblock)
6539 fprintf (sched_dump,
6540 "\n;; Procedure interblock/speculative motions == %d/%d \n",
6548 fprintf (sched_dump, "\n\n");
6552 end_alias_analysis ();
6554 free_dependency_caches ();
6556 free (rgn_bb_table);
6558 free (containing_rgn);
6562 if (write_symbols != NO_DEBUG)
6563 free (line_note_head);
6582 sbitmap_free (blocks);
6583 sbitmap_free (large_region_blocks);
6585 free (deaths_in_region);
6588 #endif /* INSN_SCHEDULING */