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"
174 extern char *reg_known_equiv_p;
175 extern rtx *reg_known_value;
177 #ifdef INSN_SCHEDULING
179 /* target_units bitmask has 1 for each unit in the cpu. It should be
180 possible to compute this variable from the machine description.
181 But currently it is computed by examining the insn list. Since
182 this is only needed for visualization, it seems an acceptable
183 solution. (For understanding the mapping of bits to units, see
184 definition of function_units[] in "insn-attrtab.c".) */
186 static int target_units = 0;
188 /* issue_rate is the number of insns that can be scheduled in the same
189 machine cycle. It can be defined in the config/mach/mach.h file,
190 otherwise we set it to 1. */
192 static int issue_rate;
198 /* sched-verbose controls the amount of debugging output the
199 scheduler prints. It is controlled by -fsched-verbose=N:
200 N>0 and no -DSR : the output is directed to stderr.
201 N>=10 will direct the printouts to stderr (regardless of -dSR).
203 N=2: bb's probabilities, detailed ready list info, unit/insn info.
204 N=3: rtl at abort point, control-flow, regions info.
205 N=5: dependences info. */
207 #define MAX_RGN_BLOCKS 10
208 #define MAX_RGN_INSNS 100
210 static int sched_verbose_param = 0;
211 static int sched_verbose = 0;
213 /* nr_inter/spec counts interblock/speculative motion for the function. */
214 static int nr_inter, nr_spec;
216 /* Debugging file. All printouts are sent to dump, which is always set,
217 either to stderr, or to the dump listing file (-dRS). */
218 static FILE *dump = 0;
220 /* fix_sched_param() is called from toplev.c upon detection
221 of the -fsched-verbose=N option. */
224 fix_sched_param (param, val)
225 const char *param, *val;
227 if (!strcmp (param, "verbose"))
228 sched_verbose_param = atoi (val);
230 warning ("fix_sched_param: unknown param: %s", param);
233 /* Describe state of dependencies used during sched_analyze phase. */
236 /* The *_insns and *_mems are paired lists. Each pending memory operation
237 will have a pointer to the MEM rtx on one list and a pointer to the
238 containing insn on the other list in the same place in the list. */
240 /* We can't use add_dependence like the old code did, because a single insn
241 may have multiple memory accesses, and hence needs to be on the list
242 once for each memory access. Add_dependence won't let you add an insn
243 to a list more than once. */
245 /* An INSN_LIST containing all insns with pending read operations. */
246 rtx pending_read_insns;
248 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
249 rtx pending_read_mems;
251 /* An INSN_LIST containing all insns with pending write operations. */
252 rtx pending_write_insns;
254 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
255 rtx pending_write_mems;
257 /* Indicates the combined length of the two pending lists. We must prevent
258 these lists from ever growing too large since the number of dependencies
259 produced is at least O(N*N), and execution time is at least O(4*N*N), as
260 a function of the length of these pending lists. */
261 int pending_lists_length;
263 /* The last insn upon which all memory references must depend.
264 This is an insn which flushed the pending lists, creating a dependency
265 between it and all previously pending memory references. This creates
266 a barrier (or a checkpoint) which no memory reference is allowed to cross.
268 This includes all non constant CALL_INSNs. When we do interprocedural
269 alias analysis, this restriction can be relaxed.
270 This may also be an INSN that writes memory if the pending lists grow
272 rtx last_pending_memory_flush;
274 /* The last function call we have seen. All hard regs, and, of course,
275 the last function call, must depend on this. */
276 rtx last_function_call;
278 /* Used to keep post-call psuedo/hard reg movements together with
280 int in_post_call_group_p;
282 /* The LOG_LINKS field of this is a list of insns which use a pseudo
283 register that does not already cross a call. We create
284 dependencies between each of those insn and the next call insn,
285 to ensure that they won't cross a call after scheduling is done. */
286 rtx sched_before_next_call;
288 /* Element N is the next insn that sets (hard or pseudo) register
289 N within the current basic block; or zero, if there is no
290 such insn. Needed for new registers which may be introduced
291 by splitting insns. */
294 rtx *reg_last_clobbers;
297 static regset reg_pending_sets;
298 static regset reg_pending_clobbers;
299 static int reg_pending_sets_all;
301 /* To speed up the test for duplicate dependency links we keep a
302 record of dependencies created by add_dependence when the average
303 number of instructions in a basic block is very large.
305 Studies have shown that there is typically around 5 instructions between
306 branches for typical C code. So we can make a guess that the average
307 basic block is approximately 5 instructions long; we will choose 100X
308 the average size as a very large basic block.
310 Each insn has associated bitmaps for its dependencies. Each bitmap
311 has enough entries to represent a dependency on any other insn in
312 the insn chain. All bitmap for true dependencies cache is
313 allocated then the rest two ones are also allocated. */
314 static sbitmap *true_dependency_cache;
315 static sbitmap *anti_dependency_cache;
316 static sbitmap *output_dependency_cache;
318 /* To speed up checking consistency of formed forward insn
319 dependencies we use the following cache. Another possible solution
320 could be switching off checking duplication of insns in forward
322 #ifdef ENABLE_CHECKING
323 static sbitmap *forward_dependency_cache;
326 /* Indexed by INSN_UID, the collection of all data associated with
327 a single instruction. */
329 struct haifa_insn_data
331 /* A list of insns which depend on the instruction. Unlike LOG_LINKS,
332 it represents forward dependancies. */
335 /* The line number note in effect for each insn. For line number
336 notes, this indicates whether the note may be reused. */
339 /* Logical uid gives the original ordering of the insns. */
342 /* A priority for each insn. */
345 /* The number of incoming edges in the forward dependency graph.
346 As scheduling proceds, counts are decreased. An insn moves to
347 the ready queue when its counter reaches zero. */
350 /* An encoding of the blockage range function. Both unit and range
352 unsigned int blockage;
354 /* Number of instructions referring to this insn. */
357 /* The minimum clock tick at which the insn becomes ready. This is
358 used to note timing constraints for the insns in the pending list. */
363 /* An encoding of the function units used. */
366 /* This weight is an estimation of the insn's contribution to
367 register pressure. */
370 /* Some insns (e.g. call) are not allowed to move across blocks. */
371 unsigned int cant_move : 1;
373 /* Set if there's DEF-USE dependance between some speculatively
374 moved load insn and this one. */
375 unsigned int fed_by_spec_load : 1;
376 unsigned int is_load_insn : 1;
379 static struct haifa_insn_data *h_i_d;
381 #define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend)
382 #define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid)
383 #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority)
384 #define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count)
385 #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost)
386 #define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units)
387 #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight)
389 #define INSN_BLOCKAGE(INSN) (h_i_d[INSN_UID (INSN)].blockage)
391 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
392 #define ENCODE_BLOCKAGE(U, R) \
393 (((U) << BLOCKAGE_BITS \
394 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
395 | MAX_BLOCKAGE_COST (R))
396 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
397 #define BLOCKAGE_RANGE(B) \
398 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
399 | ((B) & BLOCKAGE_MASK))
401 /* Encodings of the `<name>_unit_blockage_range' function. */
402 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
403 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
405 #define DONE_PRIORITY -1
406 #define MAX_PRIORITY 0x7fffffff
407 #define TAIL_PRIORITY 0x7ffffffe
408 #define LAUNCH_PRIORITY 0x7f000001
409 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
410 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
412 #define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count)
413 #define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note)
414 #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
415 #define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move)
416 #define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load)
417 #define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn)
419 /* Vector indexed by basic block number giving the starting line-number
420 for each basic block. */
421 static rtx *line_note_head;
423 /* List of important notes we must keep around. This is a pointer to the
424 last element in the list. */
425 static rtx note_list;
429 /* An instruction is ready to be scheduled when all insns preceding it
430 have already been scheduled. It is important to ensure that all
431 insns which use its result will not be executed until its result
432 has been computed. An insn is maintained in one of four structures:
434 (P) the "Pending" set of insns which cannot be scheduled until
435 their dependencies have been satisfied.
436 (Q) the "Queued" set of insns that can be scheduled when sufficient
438 (R) the "Ready" list of unscheduled, uncommitted insns.
439 (S) the "Scheduled" list of insns.
441 Initially, all insns are either "Pending" or "Ready" depending on
442 whether their dependencies are satisfied.
444 Insns move from the "Ready" list to the "Scheduled" list as they
445 are committed to the schedule. As this occurs, the insns in the
446 "Pending" list have their dependencies satisfied and move to either
447 the "Ready" list or the "Queued" set depending on whether
448 sufficient time has passed to make them ready. As time passes,
449 insns move from the "Queued" set to the "Ready" list. Insns may
450 move from the "Ready" list to the "Queued" set if they are blocked
451 due to a function unit conflict.
453 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
454 insns, i.e., those that are ready, queued, and pending.
455 The "Queued" set (Q) is implemented by the variable `insn_queue'.
456 The "Ready" list (R) is implemented by the variables `ready' and
458 The "Scheduled" list (S) is the new insn chain built by this pass.
460 The transition (R->S) is implemented in the scheduling loop in
461 `schedule_block' when the best insn to schedule is chosen.
462 The transition (R->Q) is implemented in `queue_insn' when an
463 insn is found to have a function unit conflict with the already
465 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
466 insns move from the ready list to the scheduled list.
467 The transition (Q->R) is implemented in 'queue_to_insn' as time
468 passes or stalls are introduced. */
470 /* Implement a circular buffer to delay instructions until sufficient
471 time has passed. INSN_QUEUE_SIZE is a power of two larger than
472 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
473 longest time an isnsn may be queued. */
474 static rtx insn_queue[INSN_QUEUE_SIZE];
475 static int q_ptr = 0;
476 static int q_size = 0;
477 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
478 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
480 /* Describe the ready list of the scheduler.
481 VEC holds space enough for all insns in the current region. VECLEN
482 says how many exactly.
483 FIRST is the index of the element with the highest priority; i.e. the
484 last one in the ready list, since elements are ordered by ascending
486 N_READY determines how many insns are on the ready list. */
496 /* Forward declarations. */
497 static void add_dependence PARAMS ((rtx, rtx, enum reg_note));
498 static void remove_dependence PARAMS ((rtx, rtx));
499 static rtx find_insn_list PARAMS ((rtx, rtx));
500 static void set_sched_group_p PARAMS ((rtx));
501 static int insn_unit PARAMS ((rtx));
502 static unsigned int blockage_range PARAMS ((int, rtx));
503 static void clear_units PARAMS ((void));
504 static int actual_hazard_this_instance PARAMS ((int, int, rtx, int, int));
505 static void schedule_unit PARAMS ((int, rtx, int));
506 static int actual_hazard PARAMS ((int, rtx, int, int));
507 static int potential_hazard PARAMS ((int, rtx, int));
508 static int insn_cost PARAMS ((rtx, rtx, rtx));
509 static int priority PARAMS ((rtx));
510 static void free_pending_lists PARAMS ((void));
511 static void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx,
513 static void flush_pending_lists PARAMS ((struct deps *, rtx, int));
514 static void sched_analyze_1 PARAMS ((struct deps *, rtx, rtx));
515 static void sched_analyze_2 PARAMS ((struct deps *, rtx, rtx));
516 static void sched_analyze_insn PARAMS ((struct deps *, rtx, rtx, rtx));
517 static void sched_analyze PARAMS ((struct deps *, rtx, rtx));
518 static int rank_for_schedule PARAMS ((const PTR, const PTR));
519 static void swap_sort PARAMS ((rtx *, int));
520 static void queue_insn PARAMS ((rtx, int));
521 static void schedule_insn PARAMS ((rtx, struct ready_list *, int));
522 static void find_insn_reg_weight PARAMS ((int));
523 static int schedule_block PARAMS ((int, int));
524 static char *safe_concat PARAMS ((char *, char *, const char *));
525 static int insn_issue_delay PARAMS ((rtx));
526 static void adjust_priority PARAMS ((rtx));
528 /* Control flow graph edges are kept in circular lists. */
537 static haifa_edge *edge_table;
539 #define NEXT_IN(edge) (edge_table[edge].next_in)
540 #define NEXT_OUT(edge) (edge_table[edge].next_out)
541 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
542 #define TO_BLOCK(edge) (edge_table[edge].to_block)
544 /* Number of edges in the control flow graph. (In fact, larger than
545 that by 1, since edge 0 is unused.) */
548 /* Circular list of incoming/outgoing edges of a block. */
549 static int *in_edges;
550 static int *out_edges;
552 #define IN_EDGES(block) (in_edges[block])
553 #define OUT_EDGES(block) (out_edges[block])
555 static int is_cfg_nonregular PARAMS ((void));
556 static int build_control_flow PARAMS ((struct edge_list *));
557 static void new_edge PARAMS ((int, int));
559 /* A region is the main entity for interblock scheduling: insns
560 are allowed to move between blocks in the same region, along
561 control flow graph edges, in the 'up' direction. */
564 int rgn_nr_blocks; /* Number of blocks in region. */
565 int rgn_blocks; /* cblocks in the region (actually index in rgn_bb_table). */
569 /* Number of regions in the procedure. */
570 static int nr_regions;
572 /* Table of region descriptions. */
573 static region *rgn_table;
575 /* Array of lists of regions' blocks. */
576 static int *rgn_bb_table;
578 /* Topological order of blocks in the region (if b2 is reachable from
579 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
580 always referred to by either block or b, while its topological
581 order name (in the region) is refered to by bb. */
582 static int *block_to_bb;
584 /* The number of the region containing a block. */
585 static int *containing_rgn;
587 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
588 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
589 #define BLOCK_TO_BB(block) (block_to_bb[block])
590 #define CONTAINING_RGN(block) (containing_rgn[block])
592 void debug_regions PARAMS ((void));
593 static void find_single_block_region PARAMS ((void));
594 static void find_rgns PARAMS ((struct edge_list *, sbitmap *));
595 static int too_large PARAMS ((int, int *, int *));
597 extern void debug_live PARAMS ((int, int));
599 /* Blocks of the current region being scheduled. */
600 static int current_nr_blocks;
601 static int current_blocks;
603 /* The mapping from bb to block. */
604 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
606 /* Bit vectors and bitset operations are needed for computations on
607 the control flow graph. */
609 typedef unsigned HOST_WIDE_INT *bitset;
612 int *first_member; /* Pointer to the list start in bitlst_table. */
613 int nr_members; /* The number of members of the bit list. */
617 static int bitlst_table_last;
618 static int bitlst_table_size;
619 static int *bitlst_table;
621 static char bitset_member PARAMS ((bitset, int, int));
622 static void extract_bitlst PARAMS ((bitset, int, int, bitlst *));
624 /* Target info declarations.
626 The block currently being scheduled is referred to as the "target" block,
627 while other blocks in the region from which insns can be moved to the
628 target are called "source" blocks. The candidate structure holds info
629 about such sources: are they valid? Speculative? Etc. */
630 typedef bitlst bblst;
641 static candidate *candidate_table;
643 /* A speculative motion requires checking live information on the path
644 from 'source' to 'target'. The split blocks are those to be checked.
645 After a speculative motion, live information should be modified in
648 Lists of split and update blocks for each candidate of the current
649 target are in array bblst_table. */
650 static int *bblst_table, bblst_size, bblst_last;
652 #define IS_VALID(src) ( candidate_table[src].is_valid )
653 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
654 #define SRC_PROB(src) ( candidate_table[src].src_prob )
656 /* The bb being currently scheduled. */
657 static int target_bb;
660 typedef bitlst edgelst;
662 /* Target info functions. */
663 static void split_edges PARAMS ((int, int, edgelst *));
664 static void compute_trg_info PARAMS ((int));
665 void debug_candidate PARAMS ((int));
666 void debug_candidates PARAMS ((int));
668 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
669 typedef bitset bbset;
671 /* Number of words of the bbset. */
672 static int bbset_size;
674 /* Dominators array: dom[i] contains the bbset of dominators of
675 bb i in the region. */
678 /* bb 0 is the only region entry. */
679 #define IS_RGN_ENTRY(bb) (!bb)
681 /* Is bb_src dominated by bb_trg. */
682 #define IS_DOMINATED(bb_src, bb_trg) \
683 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
685 /* Probability: Prob[i] is a float in [0, 1] which is the probability
686 of bb i relative to the region entry. */
689 /* The probability of bb_src, relative to bb_trg. Note, that while the
690 'prob[bb]' is a float in [0, 1], this macro returns an integer
692 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
695 /* Bit-set of edges, where bit i stands for edge i. */
696 typedef bitset edgeset;
698 /* Number of edges in the region. */
699 static int rgn_nr_edges;
701 /* Array of size rgn_nr_edges. */
702 static int *rgn_edges;
704 /* Number of words in an edgeset. */
705 static int edgeset_size;
707 /* Number of bits in an edgeset. */
708 static int edgeset_bitsize;
710 /* Mapping from each edge in the graph to its number in the rgn. */
711 static int *edge_to_bit;
712 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
714 /* The split edges of a source bb is different for each target
715 bb. In order to compute this efficiently, the 'potential-split edges'
716 are computed for each bb prior to scheduling a region. This is actually
717 the split edges of each bb relative to the region entry.
719 pot_split[bb] is the set of potential split edges of bb. */
720 static edgeset *pot_split;
722 /* For every bb, a set of its ancestor edges. */
723 static edgeset *ancestor_edges;
725 static void compute_dom_prob_ps PARAMS ((int));
727 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
728 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
729 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
730 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
732 /* Parameters affecting the decision of rank_for_schedule(). */
733 #define MIN_DIFF_PRIORITY 2
734 #define MIN_PROBABILITY 40
735 #define MIN_PROB_DIFF 10
737 /* Speculative scheduling functions. */
738 static int check_live_1 PARAMS ((int, rtx));
739 static void update_live_1 PARAMS ((int, rtx));
740 static int check_live PARAMS ((rtx, int));
741 static void update_live PARAMS ((rtx, int));
742 static void set_spec_fed PARAMS ((rtx));
743 static int is_pfree PARAMS ((rtx, int, int));
744 static int find_conditional_protection PARAMS ((rtx, int));
745 static int is_conditionally_protected PARAMS ((rtx, int, int));
746 static int may_trap_exp PARAMS ((rtx, int));
747 static int haifa_classify_insn PARAMS ((rtx));
748 static int is_prisky PARAMS ((rtx, int, int));
749 static int is_exception_free PARAMS ((rtx, int, int));
751 static char find_insn_mem_list PARAMS ((rtx, rtx, rtx, rtx));
752 static void compute_block_forward_dependences PARAMS ((int));
753 static void add_branch_dependences PARAMS ((rtx, rtx));
754 static void compute_block_backward_dependences PARAMS ((int));
755 void debug_dependencies PARAMS ((void));
757 /* Notes handling mechanism:
758 =========================
759 Generally, NOTES are saved before scheduling and restored after scheduling.
760 The scheduler distinguishes between three types of notes:
762 (1) LINE_NUMBER notes, generated and used for debugging. Here,
763 before scheduling a region, a pointer to the LINE_NUMBER note is
764 added to the insn following it (in save_line_notes()), and the note
765 is removed (in rm_line_notes() and unlink_line_notes()). After
766 scheduling the region, this pointer is used for regeneration of
767 the LINE_NUMBER note (in restore_line_notes()).
769 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
770 Before scheduling a region, a pointer to the note is added to the insn
771 that follows or precedes it. (This happens as part of the data dependence
772 computation). After scheduling an insn, the pointer contained in it is
773 used for regenerating the corresponding note (in reemit_notes).
775 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
776 these notes are put in a list (in rm_other_notes() and
777 unlink_other_notes ()). After scheduling the block, these notes are
778 inserted at the beginning of the block (in schedule_block()). */
780 static rtx unlink_other_notes PARAMS ((rtx, rtx));
781 static rtx unlink_line_notes PARAMS ((rtx, rtx));
782 static void rm_line_notes PARAMS ((int));
783 static void save_line_notes PARAMS ((int));
784 static void restore_line_notes PARAMS ((int));
785 static void rm_redundant_line_notes PARAMS ((void));
786 static void rm_other_notes PARAMS ((rtx, rtx));
787 static rtx reemit_notes PARAMS ((rtx, rtx));
789 static void get_block_head_tail PARAMS ((int, rtx *, rtx *));
790 static void get_bb_head_tail PARAMS ((int, rtx *, rtx *));
792 static void ready_add PARAMS ((struct ready_list *, rtx));
793 static rtx *ready_lastpos PARAMS ((struct ready_list *));
794 static void ready_sort PARAMS ((struct ready_list *));
795 static rtx ready_remove_first PARAMS ((struct ready_list *));
797 static void queue_to_ready PARAMS ((struct ready_list *));
799 static void debug_ready_list PARAMS ((struct ready_list *));
800 static void init_target_units PARAMS ((void));
801 static void insn_print_units PARAMS ((rtx));
802 static int get_visual_tbl_length PARAMS ((void));
803 static void init_block_visualization PARAMS ((void));
804 static void print_block_visualization PARAMS ((int, const char *));
805 static void visualize_scheduled_insns PARAMS ((int, int));
806 static void visualize_no_unit PARAMS ((rtx));
807 static void visualize_stall_cycles PARAMS ((int, int));
808 static void print_exp PARAMS ((char *, rtx, int));
809 static void print_value PARAMS ((char *, rtx, int));
810 static void print_pattern PARAMS ((char *, rtx, int));
811 static void print_insn PARAMS ((char *, rtx, int));
812 void debug_reg_vector PARAMS ((regset));
814 static rtx move_insn1 PARAMS ((rtx, rtx));
815 static rtx move_insn PARAMS ((rtx, rtx));
816 static rtx group_leader PARAMS ((rtx));
817 static int set_priorities PARAMS ((int));
818 static void init_deps PARAMS ((struct deps *));
819 static void schedule_region PARAMS ((int));
820 static void propagate_deps PARAMS ((int, struct deps *, int));
822 #endif /* INSN_SCHEDULING */
824 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
826 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
827 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
828 of dependence that this link represents. */
831 add_dependence (insn, elem, dep_type)
834 enum reg_note dep_type;
838 enum reg_note present_dep_type;
840 /* Don't depend an insn on itself. */
844 /* We can get a dependency on deleted insns due to optimizations in
845 the register allocation and reloading or due to splitting. Any
846 such dependency is useless and can be ignored. */
847 if (GET_CODE (elem) == NOTE)
850 /* If elem is part of a sequence that must be scheduled together, then
851 make the dependence point to the last insn of the sequence.
852 When HAVE_cc0, it is possible for NOTEs to exist between users and
853 setters of the condition codes, so we must skip past notes here.
854 Otherwise, NOTEs are impossible here. */
855 next = next_nonnote_insn (elem);
856 if (next && SCHED_GROUP_P (next)
857 && GET_CODE (next) != CODE_LABEL)
859 /* Notes will never intervene here though, so don't bother checking
862 /* We must reject CODE_LABELs, so that we don't get confused by one
863 that has LABEL_PRESERVE_P set, which is represented by the same
864 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
868 while ((nnext = next_nonnote_insn (next)) != NULL
869 && SCHED_GROUP_P (nnext)
870 && GET_CODE (nnext) != CODE_LABEL)
873 /* Again, don't depend an insn on itself. */
877 /* Make the dependence to NEXT, the last insn of the group, instead
878 of the original ELEM. */
883 #ifdef INSN_SCHEDULING
884 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
885 No need for interblock dependences with calls, since
886 calls are not moved between blocks. Note: the edge where
887 elem is a CALL is still required. */
888 if (GET_CODE (insn) == CALL_INSN
889 && (INSN_BB (elem) != INSN_BB (insn)))
892 /* If we already have a dependency for ELEM, then we do not need to
893 do anything. Avoiding the list walk below can cut compile times
894 dramatically for some code. */
895 if (true_dependency_cache != NULL)
897 if (anti_dependency_cache == NULL || output_dependency_cache == NULL)
899 if (TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)))
900 present_dep_type = 0;
901 else if (TEST_BIT (anti_dependency_cache[INSN_LUID (insn)],
903 present_dep_type = REG_DEP_ANTI;
904 else if (TEST_BIT (output_dependency_cache[INSN_LUID (insn)],
906 present_dep_type = REG_DEP_OUTPUT;
909 if (present_p && (int) dep_type >= (int) present_dep_type)
914 /* Check that we don't already have this dependence. */
916 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
917 if (XEXP (link, 0) == elem)
919 #ifdef INSN_SCHEDULING
920 /* Clear corresponding cache entry because type of the link
922 if (true_dependency_cache != NULL)
924 if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
925 RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
927 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT
928 && output_dependency_cache)
929 RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
936 /* If this is a more restrictive type of dependence than the existing
937 one, then change the existing dependence to this type. */
938 if ((int) dep_type < (int) REG_NOTE_KIND (link))
939 PUT_REG_NOTE_KIND (link, dep_type);
941 #ifdef INSN_SCHEDULING
942 /* If we are adding a dependency to INSN's LOG_LINKs, then
943 note that in the bitmap caches of dependency information. */
944 if (true_dependency_cache != NULL)
946 if ((int)REG_NOTE_KIND (link) == 0)
947 SET_BIT (true_dependency_cache[INSN_LUID (insn)],
949 else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
950 SET_BIT (anti_dependency_cache[INSN_LUID (insn)],
952 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
953 SET_BIT (output_dependency_cache[INSN_LUID (insn)],
959 /* Might want to check one level of transitivity to save conses. */
961 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
962 LOG_LINKS (insn) = link;
964 /* Insn dependency, not data dependency. */
965 PUT_REG_NOTE_KIND (link, dep_type);
967 #ifdef INSN_SCHEDULING
968 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
969 in the bitmap caches of dependency information. */
970 if (true_dependency_cache != NULL)
972 if ((int)dep_type == 0)
973 SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
974 else if (dep_type == REG_DEP_ANTI)
975 SET_BIT (anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
976 else if (dep_type == REG_DEP_OUTPUT)
977 SET_BIT (output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
982 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
983 of INSN. Abort if not found. */
986 remove_dependence (insn, elem)
990 rtx prev, link, next;
993 for (prev = 0, link = LOG_LINKS (insn); link; link = next)
995 next = XEXP (link, 1);
996 if (XEXP (link, 0) == elem)
999 XEXP (prev, 1) = next;
1001 LOG_LINKS (insn) = next;
1003 #ifdef INSN_SCHEDULING
1004 /* If we are removing a dependency from the LOG_LINKS list,
1005 make sure to remove it from the cache too. */
1006 if (true_dependency_cache != NULL)
1008 if (REG_NOTE_KIND (link) == 0)
1009 RESET_BIT (true_dependency_cache[INSN_LUID (insn)],
1011 else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
1012 RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
1014 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
1015 RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
1020 free_INSN_LIST_node (link);
1033 /* Return the INSN_LIST containing INSN in LIST, or NULL
1034 if LIST does not contain INSN. */
1037 find_insn_list (insn, list)
1043 if (XEXP (list, 0) == insn)
1045 list = XEXP (list, 1);
1050 /* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
1051 goes along with that. */
1054 set_sched_group_p (insn)
1059 SCHED_GROUP_P (insn) = 1;
1061 /* There may be a note before this insn now, but all notes will
1062 be removed before we actually try to schedule the insns, so
1063 it won't cause a problem later. We must avoid it here though. */
1064 prev = prev_nonnote_insn (insn);
1066 /* Make a copy of all dependencies on the immediately previous insn,
1067 and add to this insn. This is so that all the dependencies will
1068 apply to the group. Remove an explicit dependence on this insn
1069 as SCHED_GROUP_P now represents it. */
1071 if (find_insn_list (prev, LOG_LINKS (insn)))
1072 remove_dependence (insn, prev);
1074 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
1075 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
1078 #ifndef INSN_SCHEDULING
1080 schedule_insns (dump_file)
1081 FILE *dump_file ATTRIBUTE_UNUSED;
1089 #ifndef HAIFA_INLINE
1090 #define HAIFA_INLINE __inline
1093 /* Computation of memory dependencies. */
1095 /* Data structures for the computation of data dependences in a regions. We
1096 keep one mem_deps structure for every basic block. Before analyzing the
1097 data dependences for a bb, its variables are initialized as a function of
1098 the variables of its predecessors. When the analysis for a bb completes,
1099 we save the contents to the corresponding bb_mem_deps[bb] variable. */
1101 static struct deps *bb_deps;
1103 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1104 so that insns independent of the last scheduled insn will be preferred
1105 over dependent instructions. */
1107 static rtx last_scheduled_insn;
1109 /* Functions for construction of the control flow graph. */
1111 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1113 We decide not to build the control flow graph if there is possibly more
1114 than one entry to the function, if computed branches exist, of if we
1115 have nonlocal gotos. */
1118 is_cfg_nonregular ()
1124 /* If we have a label that could be the target of a nonlocal goto, then
1125 the cfg is not well structured. */
1126 if (nonlocal_goto_handler_labels)
1129 /* If we have any forced labels, then the cfg is not well structured. */
1133 /* If this function has a computed jump, then we consider the cfg
1134 not well structured. */
1135 if (current_function_has_computed_jump)
1138 /* If we have exception handlers, then we consider the cfg not well
1139 structured. ?!? We should be able to handle this now that flow.c
1140 computes an accurate cfg for EH. */
1141 if (exception_handler_labels)
1144 /* If we have non-jumping insns which refer to labels, then we consider
1145 the cfg not well structured. */
1146 /* Check for labels referred to other thn by jumps. */
1147 for (b = 0; b < n_basic_blocks; b++)
1148 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
1150 code = GET_CODE (insn);
1151 if (GET_RTX_CLASS (code) == 'i')
1155 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1156 if (REG_NOTE_KIND (note) == REG_LABEL)
1160 if (insn == BLOCK_END (b))
1164 /* All the tests passed. Consider the cfg well structured. */
1168 /* Build the control flow graph and set nr_edges.
1170 Instead of trying to build a cfg ourselves, we rely on flow to
1171 do it for us. Stamp out useless code (and bug) duplication.
1173 Return nonzero if an irregularity in the cfg is found which would
1174 prevent cross block scheduling. */
1177 build_control_flow (edge_list)
1178 struct edge_list *edge_list;
1180 int i, unreachable, num_edges;
1182 /* This already accounts for entry/exit edges. */
1183 num_edges = NUM_EDGES (edge_list);
1185 /* Unreachable loops with more than one basic block are detected
1186 during the DFS traversal in find_rgns.
1188 Unreachable loops with a single block are detected here. This
1189 test is redundant with the one in find_rgns, but it's much
1190 cheaper to go ahead and catch the trivial case here. */
1192 for (i = 0; i < n_basic_blocks; i++)
1194 basic_block b = BASIC_BLOCK (i);
1197 || (b->pred->src == b
1198 && b->pred->pred_next == NULL))
1202 /* ??? We can kill these soon. */
1203 in_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
1204 out_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
1205 edge_table = (haifa_edge *) xcalloc (num_edges, sizeof (haifa_edge));
1208 for (i = 0; i < num_edges; i++)
1210 edge e = INDEX_EDGE (edge_list, i);
1212 if (e->dest != EXIT_BLOCK_PTR
1213 && e->src != ENTRY_BLOCK_PTR)
1214 new_edge (e->src->index, e->dest->index);
1217 /* Increment by 1, since edge 0 is unused. */
1223 /* Record an edge in the control flow graph from SOURCE to TARGET.
1225 In theory, this is redundant with the s_succs computed above, but
1226 we have not converted all of haifa to use information from the
1230 new_edge (source, target)
1234 int curr_edge, fst_edge;
1236 /* Check for duplicates. */
1237 fst_edge = curr_edge = OUT_EDGES (source);
1240 if (FROM_BLOCK (curr_edge) == source
1241 && TO_BLOCK (curr_edge) == target)
1246 curr_edge = NEXT_OUT (curr_edge);
1248 if (fst_edge == curr_edge)
1254 FROM_BLOCK (e) = source;
1255 TO_BLOCK (e) = target;
1257 if (OUT_EDGES (source))
1259 next_edge = NEXT_OUT (OUT_EDGES (source));
1260 NEXT_OUT (OUT_EDGES (source)) = e;
1261 NEXT_OUT (e) = next_edge;
1265 OUT_EDGES (source) = e;
1269 if (IN_EDGES (target))
1271 next_edge = NEXT_IN (IN_EDGES (target));
1272 NEXT_IN (IN_EDGES (target)) = e;
1273 NEXT_IN (e) = next_edge;
1277 IN_EDGES (target) = e;
1282 /* BITSET macros for operations on the control flow graph. */
1284 /* Compute bitwise union of two bitsets. */
1285 #define BITSET_UNION(set1, set2, len) \
1286 do { register bitset tp = set1, sp = set2; \
1288 for (i = 0; i < len; i++) \
1289 *(tp++) |= *(sp++); } while (0)
1291 /* Compute bitwise intersection of two bitsets. */
1292 #define BITSET_INTER(set1, set2, len) \
1293 do { register bitset tp = set1, sp = set2; \
1295 for (i = 0; i < len; i++) \
1296 *(tp++) &= *(sp++); } while (0)
1298 /* Compute bitwise difference of two bitsets. */
1299 #define BITSET_DIFFER(set1, set2, len) \
1300 do { register bitset tp = set1, sp = set2; \
1302 for (i = 0; i < len; i++) \
1303 *(tp++) &= ~*(sp++); } while (0)
1305 /* Inverts every bit of bitset 'set'. */
1306 #define BITSET_INVERT(set, len) \
1307 do { register bitset tmpset = set; \
1309 for (i = 0; i < len; i++, tmpset++) \
1310 *tmpset = ~*tmpset; } while (0)
1312 /* Turn on the index'th bit in bitset set. */
1313 #define BITSET_ADD(set, index, len) \
1315 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1318 set[index/HOST_BITS_PER_WIDE_INT] |= \
1319 1 << (index % HOST_BITS_PER_WIDE_INT); \
1322 /* Turn off the index'th bit in set. */
1323 #define BITSET_REMOVE(set, index, len) \
1325 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1328 set[index/HOST_BITS_PER_WIDE_INT] &= \
1329 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1332 /* Check if the index'th bit in bitset set is on. */
1335 bitset_member (set, index, len)
1339 if (index >= HOST_BITS_PER_WIDE_INT * len)
1341 return (set[index / HOST_BITS_PER_WIDE_INT] &
1342 1 << (index % HOST_BITS_PER_WIDE_INT)) ? 1 : 0;
1345 /* Translate a bit-set SET to a list BL of the bit-set members. */
1348 extract_bitlst (set, len, bitlen, bl)
1355 unsigned HOST_WIDE_INT word;
1357 /* bblst table space is reused in each call to extract_bitlst. */
1358 bitlst_table_last = 0;
1360 bl->first_member = &bitlst_table[bitlst_table_last];
1363 /* Iterate over each word in the bitset. */
1364 for (i = 0; i < len; i++)
1367 offset = i * HOST_BITS_PER_WIDE_INT;
1369 /* Iterate over each bit in the word, but do not
1370 go beyond the end of the defined bits. */
1371 for (j = 0; offset < bitlen && word; j++)
1375 bitlst_table[bitlst_table_last++] = offset;
1385 /* Functions for the construction of regions. */
1387 /* Print the regions, for debugging purposes. Callable from debugger. */
1394 fprintf (dump, "\n;; ------------ REGIONS ----------\n\n");
1395 for (rgn = 0; rgn < nr_regions; rgn++)
1397 fprintf (dump, ";;\trgn %d nr_blocks %d:\n", rgn,
1398 rgn_table[rgn].rgn_nr_blocks);
1399 fprintf (dump, ";;\tbb/block: ");
1401 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
1403 current_blocks = RGN_BLOCKS (rgn);
1405 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
1408 fprintf (dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
1411 fprintf (dump, "\n\n");
1415 /* Build a single block region for each basic block in the function.
1416 This allows for using the same code for interblock and basic block
1420 find_single_block_region ()
1424 for (i = 0; i < n_basic_blocks; i++)
1426 rgn_bb_table[i] = i;
1427 RGN_NR_BLOCKS (i) = 1;
1429 CONTAINING_RGN (i) = i;
1430 BLOCK_TO_BB (i) = 0;
1432 nr_regions = n_basic_blocks;
1435 /* Update number of blocks and the estimate for number of insns
1436 in the region. Return 1 if the region is "too large" for interblock
1437 scheduling (compile time considerations), otherwise return 0. */
1440 too_large (block, num_bbs, num_insns)
1441 int block, *num_bbs, *num_insns;
1444 (*num_insns) += (INSN_LUID (BLOCK_END (block)) -
1445 INSN_LUID (BLOCK_HEAD (block)));
1446 if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
1452 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1453 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1454 loop containing blk. */
1455 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1457 if (max_hdr[blk] == -1) \
1458 max_hdr[blk] = hdr; \
1459 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1460 RESET_BIT (inner, hdr); \
1461 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1463 RESET_BIT (inner,max_hdr[blk]); \
1464 max_hdr[blk] = hdr; \
1468 /* Find regions for interblock scheduling.
1470 A region for scheduling can be:
1472 * A loop-free procedure, or
1474 * A reducible inner loop, or
1476 * A basic block not contained in any other region.
1478 ?!? In theory we could build other regions based on extended basic
1479 blocks or reverse extended basic blocks. Is it worth the trouble?
1481 Loop blocks that form a region are put into the region's block list
1482 in topological order.
1484 This procedure stores its results into the following global (ick) variables
1492 We use dominator relationships to avoid making regions out of non-reducible
1495 This procedure needs to be converted to work on pred/succ lists instead
1496 of edge tables. That would simplify it somewhat. */
1499 find_rgns (edge_list, dom)
1500 struct edge_list *edge_list;
1503 int *max_hdr, *dfs_nr, *stack, *degree;
1505 int node, child, loop_head, i, head, tail;
1506 int count = 0, sp, idx = 0, current_edge = out_edges[0];
1507 int num_bbs, num_insns, unreachable;
1508 int too_large_failure;
1510 /* Note if an edge has been passed. */
1513 /* Note if a block is a natural loop header. */
1516 /* Note if a block is an natural inner loop header. */
1519 /* Note if a block is in the block queue. */
1522 /* Note if a block is in the block queue. */
1525 int num_edges = NUM_EDGES (edge_list);
1527 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1528 and a mapping from block to its loop header (if the block is contained
1529 in a loop, else -1).
1531 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1532 be used as inputs to the second traversal.
1534 STACK, SP and DFS_NR are only used during the first traversal. */
1536 /* Allocate and initialize variables for the first traversal. */
1537 max_hdr = (int *) xmalloc (n_basic_blocks * sizeof (int));
1538 dfs_nr = (int *) xcalloc (n_basic_blocks, sizeof (int));
1539 stack = (int *) xmalloc (nr_edges * sizeof (int));
1541 inner = sbitmap_alloc (n_basic_blocks);
1542 sbitmap_ones (inner);
1544 header = sbitmap_alloc (n_basic_blocks);
1545 sbitmap_zero (header);
1547 passed = sbitmap_alloc (nr_edges);
1548 sbitmap_zero (passed);
1550 in_queue = sbitmap_alloc (n_basic_blocks);
1551 sbitmap_zero (in_queue);
1553 in_stack = sbitmap_alloc (n_basic_blocks);
1554 sbitmap_zero (in_stack);
1556 for (i = 0; i < n_basic_blocks; i++)
1559 /* DFS traversal to find inner loops in the cfg. */
1564 if (current_edge == 0 || TEST_BIT (passed, current_edge))
1566 /* We have reached a leaf node or a node that was already
1567 processed. Pop edges off the stack until we find
1568 an edge that has not yet been processed. */
1570 && (current_edge == 0 || TEST_BIT (passed, current_edge)))
1572 /* Pop entry off the stack. */
1573 current_edge = stack[sp--];
1574 node = FROM_BLOCK (current_edge);
1575 child = TO_BLOCK (current_edge);
1576 RESET_BIT (in_stack, child);
1577 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1578 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1579 current_edge = NEXT_OUT (current_edge);
1582 /* See if have finished the DFS tree traversal. */
1583 if (sp < 0 && TEST_BIT (passed, current_edge))
1586 /* Nope, continue the traversal with the popped node. */
1590 /* Process a node. */
1591 node = FROM_BLOCK (current_edge);
1592 child = TO_BLOCK (current_edge);
1593 SET_BIT (in_stack, node);
1594 dfs_nr[node] = ++count;
1596 /* If the successor is in the stack, then we've found a loop.
1597 Mark the loop, if it is not a natural loop, then it will
1598 be rejected during the second traversal. */
1599 if (TEST_BIT (in_stack, child))
1602 SET_BIT (header, child);
1603 UPDATE_LOOP_RELATIONS (node, child);
1604 SET_BIT (passed, current_edge);
1605 current_edge = NEXT_OUT (current_edge);
1609 /* If the child was already visited, then there is no need to visit
1610 it again. Just update the loop relationships and restart
1614 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1615 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1616 SET_BIT (passed, current_edge);
1617 current_edge = NEXT_OUT (current_edge);
1621 /* Push an entry on the stack and continue DFS traversal. */
1622 stack[++sp] = current_edge;
1623 SET_BIT (passed, current_edge);
1624 current_edge = OUT_EDGES (child);
1626 /* This is temporary until haifa is converted to use rth's new
1627 cfg routines which have true entry/exit blocks and the
1628 appropriate edges from/to those blocks.
1630 Generally we update dfs_nr for a node when we process its
1631 out edge. However, if the node has no out edge then we will
1632 not set dfs_nr for that node. This can confuse the scheduler
1633 into thinking that we have unreachable blocks, which in turn
1634 disables cross block scheduling.
1636 So, if we have a node with no out edges, go ahead and mark it
1637 as reachable now. */
1638 if (current_edge == 0)
1639 dfs_nr[child] = ++count;
1642 /* Another check for unreachable blocks. The earlier test in
1643 is_cfg_nonregular only finds unreachable blocks that do not
1646 The DFS traversal will mark every block that is reachable from
1647 the entry node by placing a nonzero value in dfs_nr. Thus if
1648 dfs_nr is zero for any block, then it must be unreachable. */
1650 for (i = 0; i < n_basic_blocks; i++)
1657 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1658 to hold degree counts. */
1661 for (i = 0; i < n_basic_blocks; i++)
1663 for (i = 0; i < num_edges; i++)
1665 edge e = INDEX_EDGE (edge_list, i);
1667 if (e->dest != EXIT_BLOCK_PTR)
1668 degree[e->dest->index]++;
1671 /* Do not perform region scheduling if there are any unreachable
1678 SET_BIT (header, 0);
1680 /* Second travsersal:find reducible inner loops and topologically sort
1681 block of each region. */
1683 queue = (int *) xmalloc (n_basic_blocks * sizeof (int));
1685 /* Find blocks which are inner loop headers. We still have non-reducible
1686 loops to consider at this point. */
1687 for (i = 0; i < n_basic_blocks; i++)
1689 if (TEST_BIT (header, i) && TEST_BIT (inner, i))
1694 /* Now check that the loop is reducible. We do this separate
1695 from finding inner loops so that we do not find a reducible
1696 loop which contains an inner non-reducible loop.
1698 A simple way to find reducible/natural loops is to verify
1699 that each block in the loop is dominated by the loop
1702 If there exists a block that is not dominated by the loop
1703 header, then the block is reachable from outside the loop
1704 and thus the loop is not a natural loop. */
1705 for (j = 0; j < n_basic_blocks; j++)
1707 /* First identify blocks in the loop, except for the loop
1709 if (i == max_hdr[j] && i != j)
1711 /* Now verify that the block is dominated by the loop
1713 if (!TEST_BIT (dom[j], i))
1718 /* If we exited the loop early, then I is the header of
1719 a non-reducible loop and we should quit processing it
1721 if (j != n_basic_blocks)
1724 /* I is a header of an inner loop, or block 0 in a subroutine
1725 with no loops at all. */
1727 too_large_failure = 0;
1728 loop_head = max_hdr[i];
1730 /* Decrease degree of all I's successors for topological
1732 for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
1733 if (e->dest != EXIT_BLOCK_PTR)
1734 --degree[e->dest->index];
1736 /* Estimate # insns, and count # blocks in the region. */
1738 num_insns = (INSN_LUID (BLOCK_END (i))
1739 - INSN_LUID (BLOCK_HEAD (i)));
1741 /* Find all loop latches (blocks with back edges to the loop
1742 header) or all the leaf blocks in the cfg has no loops.
1744 Place those blocks into the queue. */
1747 for (j = 0; j < n_basic_blocks; j++)
1748 /* Leaf nodes have only a single successor which must
1750 if (BASIC_BLOCK (j)->succ
1751 && BASIC_BLOCK (j)->succ->dest == EXIT_BLOCK_PTR
1752 && BASIC_BLOCK (j)->succ->succ_next == NULL)
1755 SET_BIT (in_queue, j);
1757 if (too_large (j, &num_bbs, &num_insns))
1759 too_large_failure = 1;
1768 for (e = BASIC_BLOCK (i)->pred; e; e = e->pred_next)
1770 if (e->src == ENTRY_BLOCK_PTR)
1773 node = e->src->index;
1775 if (max_hdr[node] == loop_head && node != i)
1777 /* This is a loop latch. */
1778 queue[++tail] = node;
1779 SET_BIT (in_queue, node);
1781 if (too_large (node, &num_bbs, &num_insns))
1783 too_large_failure = 1;
1790 /* Now add all the blocks in the loop to the queue.
1792 We know the loop is a natural loop; however the algorithm
1793 above will not always mark certain blocks as being in the
1801 The algorithm in the DFS traversal may not mark B & D as part
1802 of the loop (ie they will not have max_hdr set to A).
1804 We know they can not be loop latches (else they would have
1805 had max_hdr set since they'd have a backedge to a dominator
1806 block). So we don't need them on the initial queue.
1808 We know they are part of the loop because they are dominated
1809 by the loop header and can be reached by a backwards walk of
1810 the edges starting with nodes on the initial queue.
1812 It is safe and desirable to include those nodes in the
1813 loop/scheduling region. To do so we would need to decrease
1814 the degree of a node if it is the target of a backedge
1815 within the loop itself as the node is placed in the queue.
1817 We do not do this because I'm not sure that the actual
1818 scheduling code will properly handle this case. ?!? */
1820 while (head < tail && !too_large_failure)
1823 child = queue[++head];
1825 for (e = BASIC_BLOCK (child)->pred; e; e = e->pred_next)
1827 node = e->src->index;
1829 /* See discussion above about nodes not marked as in
1830 this loop during the initial DFS traversal. */
1831 if (e->src == ENTRY_BLOCK_PTR
1832 || max_hdr[node] != loop_head)
1837 else if (!TEST_BIT (in_queue, node) && node != i)
1839 queue[++tail] = node;
1840 SET_BIT (in_queue, node);
1842 if (too_large (node, &num_bbs, &num_insns))
1844 too_large_failure = 1;
1851 if (tail >= 0 && !too_large_failure)
1853 /* Place the loop header into list of region blocks. */
1855 rgn_bb_table[idx] = i;
1856 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1857 RGN_BLOCKS (nr_regions) = idx++;
1858 CONTAINING_RGN (i) = nr_regions;
1859 BLOCK_TO_BB (i) = count = 0;
1861 /* Remove blocks from queue[] when their in degree
1862 becomes zero. Repeat until no blocks are left on the
1863 list. This produces a topological list of blocks in
1869 child = queue[head];
1870 if (degree[child] == 0)
1875 rgn_bb_table[idx++] = child;
1876 BLOCK_TO_BB (child) = ++count;
1877 CONTAINING_RGN (child) = nr_regions;
1878 queue[head] = queue[tail--];
1880 for (e = BASIC_BLOCK (child)->succ;
1883 if (e->dest != EXIT_BLOCK_PTR)
1884 --degree[e->dest->index];
1896 /* Any block that did not end up in a region is placed into a region
1898 for (i = 0; i < n_basic_blocks; i++)
1901 rgn_bb_table[idx] = i;
1902 RGN_NR_BLOCKS (nr_regions) = 1;
1903 RGN_BLOCKS (nr_regions) = idx++;
1904 CONTAINING_RGN (i) = nr_regions++;
1905 BLOCK_TO_BB (i) = 0;
1918 /* Functions for regions scheduling information. */
1920 /* Compute dominators, probability, and potential-split-edges of bb.
1921 Assume that these values were already computed for bb's predecessors. */
1924 compute_dom_prob_ps (bb)
1927 int nxt_in_edge, fst_in_edge, pred;
1928 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1931 if (IS_RGN_ENTRY (bb))
1933 BITSET_ADD (dom[bb], 0, bbset_size);
1938 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1940 /* Intialize dom[bb] to '111..1'. */
1941 BITSET_INVERT (dom[bb], bbset_size);
1945 pred = FROM_BLOCK (nxt_in_edge);
1946 BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
1948 BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
1951 BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
1954 nr_rgn_out_edges = 0;
1955 fst_out_edge = OUT_EDGES (pred);
1956 nxt_out_edge = NEXT_OUT (fst_out_edge);
1957 BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
1960 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
1962 /* The successor doesn't belong in the region? */
1963 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1964 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1967 while (fst_out_edge != nxt_out_edge)
1970 /* The successor doesn't belong in the region? */
1971 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1972 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1974 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
1975 nxt_out_edge = NEXT_OUT (nxt_out_edge);
1979 /* Now nr_rgn_out_edges is the number of region-exit edges from
1980 pred, and nr_out_edges will be the number of pred out edges
1981 not leaving the region. */
1982 nr_out_edges -= nr_rgn_out_edges;
1983 if (nr_rgn_out_edges > 0)
1984 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1986 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1987 nxt_in_edge = NEXT_IN (nxt_in_edge);
1989 while (fst_in_edge != nxt_in_edge);
1991 BITSET_ADD (dom[bb], bb, bbset_size);
1992 BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
1994 if (sched_verbose >= 2)
1995 fprintf (dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
1996 (int) (100.0 * prob[bb]));
1999 /* Functions for target info. */
2001 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
2002 Note that bb_trg dominates bb_src. */
2005 split_edges (bb_src, bb_trg, bl)
2010 int es = edgeset_size;
2011 edgeset src = (edgeset) xcalloc (es, sizeof (HOST_WIDE_INT));
2014 src[es] = (pot_split[bb_src])[es];
2015 BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
2016 extract_bitlst (src, edgeset_size, edgeset_bitsize, bl);
2020 /* Find the valid candidate-source-blocks for the target block TRG, compute
2021 their probability, and check if they are speculative or not.
2022 For speculative sources, compute their update-blocks and split-blocks. */
2025 compute_trg_info (trg)
2028 register candidate *sp;
2030 int check_block, update_idx;
2031 int i, j, k, fst_edge, nxt_edge;
2033 /* Define some of the fields for the target bb as well. */
2034 sp = candidate_table + trg;
2036 sp->is_speculative = 0;
2039 for (i = trg + 1; i < current_nr_blocks; i++)
2041 sp = candidate_table + i;
2043 sp->is_valid = IS_DOMINATED (i, trg);
2046 sp->src_prob = GET_SRC_PROB (i, trg);
2047 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
2052 split_edges (i, trg, &el);
2053 sp->is_speculative = (el.nr_members) ? 1 : 0;
2054 if (sp->is_speculative && !flag_schedule_speculative)
2060 char *update_blocks;
2062 /* Compute split blocks and store them in bblst_table.
2063 The TO block of every split edge is a split block. */
2064 sp->split_bbs.first_member = &bblst_table[bblst_last];
2065 sp->split_bbs.nr_members = el.nr_members;
2066 for (j = 0; j < el.nr_members; bblst_last++, j++)
2067 bblst_table[bblst_last] =
2068 TO_BLOCK (rgn_edges[el.first_member[j]]);
2069 sp->update_bbs.first_member = &bblst_table[bblst_last];
2071 /* Compute update blocks and store them in bblst_table.
2072 For every split edge, look at the FROM block, and check
2073 all out edges. For each out edge that is not a split edge,
2074 add the TO block to the update block list. This list can end
2075 up with a lot of duplicates. We need to weed them out to avoid
2076 overrunning the end of the bblst_table. */
2077 update_blocks = (char *) alloca (n_basic_blocks);
2078 memset (update_blocks, 0, n_basic_blocks);
2081 for (j = 0; j < el.nr_members; j++)
2083 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
2084 fst_edge = nxt_edge = OUT_EDGES (check_block);
2087 if (! update_blocks[TO_BLOCK (nxt_edge)])
2089 for (k = 0; k < el.nr_members; k++)
2090 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
2093 if (k >= el.nr_members)
2095 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
2096 update_blocks[TO_BLOCK (nxt_edge)] = 1;
2101 nxt_edge = NEXT_OUT (nxt_edge);
2103 while (fst_edge != nxt_edge);
2105 sp->update_bbs.nr_members = update_idx;
2107 /* Make sure we didn't overrun the end of bblst_table. */
2108 if (bblst_last > bblst_size)
2113 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
2115 sp->is_speculative = 0;
2121 /* Print candidates info, for debugging purposes. Callable from debugger. */
2127 if (!candidate_table[i].is_valid)
2130 if (candidate_table[i].is_speculative)
2133 fprintf (dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
2135 fprintf (dump, "split path: ");
2136 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
2138 int b = candidate_table[i].split_bbs.first_member[j];
2140 fprintf (dump, " %d ", b);
2142 fprintf (dump, "\n");
2144 fprintf (dump, "update path: ");
2145 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
2147 int b = candidate_table[i].update_bbs.first_member[j];
2149 fprintf (dump, " %d ", b);
2151 fprintf (dump, "\n");
2155 fprintf (dump, " src %d equivalent\n", BB_TO_BLOCK (i));
2159 /* Print candidates info, for debugging purposes. Callable from debugger. */
2162 debug_candidates (trg)
2167 fprintf (dump, "----------- candidate table: target: b=%d bb=%d ---\n",
2168 BB_TO_BLOCK (trg), trg);
2169 for (i = trg + 1; i < current_nr_blocks; i++)
2170 debug_candidate (i);
2173 /* Functions for speculative scheduing. */
2175 /* Return 0 if x is a set of a register alive in the beginning of one
2176 of the split-blocks of src, otherwise return 1. */
2179 check_live_1 (src, x)
2185 register rtx reg = SET_DEST (x);
2190 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2191 || GET_CODE (reg) == SIGN_EXTRACT
2192 || GET_CODE (reg) == STRICT_LOW_PART)
2193 reg = XEXP (reg, 0);
2195 if (GET_CODE (reg) == PARALLEL
2196 && GET_MODE (reg) == BLKmode)
2199 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2200 if (check_live_1 (src, XVECEXP (reg, 0, i)))
2205 if (GET_CODE (reg) != REG)
2208 regno = REGNO (reg);
2210 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2212 /* Global registers are assumed live. */
2217 if (regno < FIRST_PSEUDO_REGISTER)
2219 /* Check for hard registers. */
2220 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2223 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2225 int b = candidate_table[src].split_bbs.first_member[i];
2227 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
2237 /* Check for psuedo registers. */
2238 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2240 int b = candidate_table[src].split_bbs.first_member[i];
2242 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
2253 /* If x is a set of a register R, mark that R is alive in the beginning
2254 of every update-block of src. */
2257 update_live_1 (src, x)
2263 register rtx reg = SET_DEST (x);
2268 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2269 || GET_CODE (reg) == SIGN_EXTRACT
2270 || GET_CODE (reg) == STRICT_LOW_PART)
2271 reg = XEXP (reg, 0);
2273 if (GET_CODE (reg) == PARALLEL
2274 && GET_MODE (reg) == BLKmode)
2277 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2278 update_live_1 (src, XVECEXP (reg, 0, i));
2282 if (GET_CODE (reg) != REG)
2285 /* Global registers are always live, so the code below does not apply
2288 regno = REGNO (reg);
2290 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
2292 if (regno < FIRST_PSEUDO_REGISTER)
2294 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2297 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2299 int b = candidate_table[src].update_bbs.first_member[i];
2301 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
2308 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2310 int b = candidate_table[src].update_bbs.first_member[i];
2312 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
2318 /* Return 1 if insn can be speculatively moved from block src to trg,
2319 otherwise return 0. Called before first insertion of insn to
2320 ready-list or before the scheduling. */
2323 check_live (insn, src)
2327 /* Find the registers set by instruction. */
2328 if (GET_CODE (PATTERN (insn)) == SET
2329 || GET_CODE (PATTERN (insn)) == CLOBBER)
2330 return check_live_1 (src, PATTERN (insn));
2331 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2334 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2335 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2336 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2337 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
2346 /* Update the live registers info after insn was moved speculatively from
2347 block src to trg. */
2350 update_live (insn, src)
2354 /* Find the registers set by instruction. */
2355 if (GET_CODE (PATTERN (insn)) == SET
2356 || GET_CODE (PATTERN (insn)) == CLOBBER)
2357 update_live_1 (src, PATTERN (insn));
2358 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2361 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2362 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2363 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2364 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
2368 /* Exception Free Loads:
2370 We define five classes of speculative loads: IFREE, IRISKY,
2371 PFREE, PRISKY, and MFREE.
2373 IFREE loads are loads that are proved to be exception-free, just
2374 by examining the load insn. Examples for such loads are loads
2375 from TOC and loads of global data.
2377 IRISKY loads are loads that are proved to be exception-risky,
2378 just by examining the load insn. Examples for such loads are
2379 volatile loads and loads from shared memory.
2381 PFREE loads are loads for which we can prove, by examining other
2382 insns, that they are exception-free. Currently, this class consists
2383 of loads for which we are able to find a "similar load", either in
2384 the target block, or, if only one split-block exists, in that split
2385 block. Load2 is similar to load1 if both have same single base
2386 register. We identify only part of the similar loads, by finding
2387 an insn upon which both load1 and load2 have a DEF-USE dependence.
2389 PRISKY loads are loads for which we can prove, by examining other
2390 insns, that they are exception-risky. Currently we have two proofs for
2391 such loads. The first proof detects loads that are probably guarded by a
2392 test on the memory address. This proof is based on the
2393 backward and forward data dependence information for the region.
2394 Let load-insn be the examined load.
2395 Load-insn is PRISKY iff ALL the following hold:
2397 - insn1 is not in the same block as load-insn
2398 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2399 - test-insn is either a compare or a branch, not in the same block
2401 - load-insn is reachable from test-insn
2402 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2404 This proof might fail when the compare and the load are fed
2405 by an insn not in the region. To solve this, we will add to this
2406 group all loads that have no input DEF-USE dependence.
2408 The second proof detects loads that are directly or indirectly
2409 fed by a speculative load. This proof is affected by the
2410 scheduling process. We will use the flag fed_by_spec_load.
2411 Initially, all insns have this flag reset. After a speculative
2412 motion of an insn, if insn is either a load, or marked as
2413 fed_by_spec_load, we will also mark as fed_by_spec_load every
2414 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2415 load which is fed_by_spec_load is also PRISKY.
2417 MFREE (maybe-free) loads are all the remaining loads. They may be
2418 exception-free, but we cannot prove it.
2420 Now, all loads in IFREE and PFREE classes are considered
2421 exception-free, while all loads in IRISKY and PRISKY classes are
2422 considered exception-risky. As for loads in the MFREE class,
2423 these are considered either exception-free or exception-risky,
2424 depending on whether we are pessimistic or optimistic. We have
2425 to take the pessimistic approach to assure the safety of
2426 speculative scheduling, but we can take the optimistic approach
2427 by invoking the -fsched_spec_load_dangerous option. */
2429 enum INSN_TRAP_CLASS
2431 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
2432 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
2435 #define WORST_CLASS(class1, class2) \
2436 ((class1 > class2) ? class1 : class2)
2438 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2439 #define IS_REACHABLE(bb_from, bb_to) \
2441 || IS_RGN_ENTRY (bb_from) \
2442 || (bitset_member (ancestor_edges[bb_to], \
2443 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2446 /* Non-zero iff the address is comprised from at most 1 register. */
2447 #define CONST_BASED_ADDRESS_P(x) \
2448 (GET_CODE (x) == REG \
2449 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2450 || (GET_CODE (x) == LO_SUM)) \
2451 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2452 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2454 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2457 set_spec_fed (load_insn)
2462 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
2463 if (GET_MODE (link) == VOIDmode)
2464 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
2465 } /* set_spec_fed */
2467 /* On the path from the insn to load_insn_bb, find a conditional
2468 branch depending on insn, that guards the speculative load. */
2471 find_conditional_protection (insn, load_insn_bb)
2477 /* Iterate through DEF-USE forward dependences. */
2478 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2480 rtx next = XEXP (link, 0);
2481 if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
2482 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
2483 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
2484 && load_insn_bb != INSN_BB (next)
2485 && GET_MODE (link) == VOIDmode
2486 && (GET_CODE (next) == JUMP_INSN
2487 || find_conditional_protection (next, load_insn_bb)))
2491 } /* find_conditional_protection */
2493 /* Returns 1 if the same insn1 that participates in the computation
2494 of load_insn's address is feeding a conditional branch that is
2495 guarding on load_insn. This is true if we find a the two DEF-USE
2497 insn1 -> ... -> conditional-branch
2498 insn1 -> ... -> load_insn,
2499 and if a flow path exist:
2500 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2501 and if insn1 is on the path
2502 region-entry -> ... -> bb_trg -> ... load_insn.
2504 Locate insn1 by climbing on LOG_LINKS from load_insn.
2505 Locate the branch by following INSN_DEPEND from insn1. */
2508 is_conditionally_protected (load_insn, bb_src, bb_trg)
2514 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
2516 rtx insn1 = XEXP (link, 0);
2518 /* Must be a DEF-USE dependence upon non-branch. */
2519 if (GET_MODE (link) != VOIDmode
2520 || GET_CODE (insn1) == JUMP_INSN)
2523 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
2524 if (INSN_BB (insn1) == bb_src
2525 || (CONTAINING_RGN (BLOCK_NUM (insn1))
2526 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
2527 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
2528 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
2531 /* Now search for the conditional-branch. */
2532 if (find_conditional_protection (insn1, bb_src))
2535 /* Recursive step: search another insn1, "above" current insn1. */
2536 return is_conditionally_protected (insn1, bb_src, bb_trg);
2539 /* The chain does not exist. */
2541 } /* is_conditionally_protected */
2543 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2544 load_insn can move speculatively from bb_src to bb_trg. All the
2545 following must hold:
2547 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2548 (2) load_insn and load1 have a def-use dependence upon
2549 the same insn 'insn1'.
2550 (3) either load2 is in bb_trg, or:
2551 - there's only one split-block, and
2552 - load1 is on the escape path, and
2554 From all these we can conclude that the two loads access memory
2555 addresses that differ at most by a constant, and hence if moving
2556 load_insn would cause an exception, it would have been caused by
2560 is_pfree (load_insn, bb_src, bb_trg)
2565 register candidate *candp = candidate_table + bb_src;
2567 if (candp->split_bbs.nr_members != 1)
2568 /* Must have exactly one escape block. */
2571 for (back_link = LOG_LINKS (load_insn);
2572 back_link; back_link = XEXP (back_link, 1))
2574 rtx insn1 = XEXP (back_link, 0);
2576 if (GET_MODE (back_link) == VOIDmode)
2578 /* Found a DEF-USE dependence (insn1, load_insn). */
2581 for (fore_link = INSN_DEPEND (insn1);
2582 fore_link; fore_link = XEXP (fore_link, 1))
2584 rtx insn2 = XEXP (fore_link, 0);
2585 if (GET_MODE (fore_link) == VOIDmode)
2587 /* Found a DEF-USE dependence (insn1, insn2). */
2588 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
2589 /* insn2 not guaranteed to be a 1 base reg load. */
2592 if (INSN_BB (insn2) == bb_trg)
2593 /* insn2 is the similar load, in the target block. */
2596 if (*(candp->split_bbs.first_member) == BLOCK_NUM (insn2))
2597 /* insn2 is a similar load, in a split-block. */
2604 /* Couldn't find a similar load. */
2608 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2609 as found by analyzing insn's expression. */
2612 may_trap_exp (x, is_store)
2620 code = GET_CODE (x);
2630 /* The insn uses memory: a volatile load. */
2631 if (MEM_VOLATILE_P (x))
2633 /* An exception-free load. */
2634 if (!may_trap_p (x))
2636 /* A load with 1 base register, to be further checked. */
2637 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
2638 return PFREE_CANDIDATE;
2639 /* No info on the load, to be further checked. */
2640 return PRISKY_CANDIDATE;
2645 int i, insn_class = TRAP_FREE;
2647 /* Neither store nor load, check if it may cause a trap. */
2650 /* Recursive step: walk the insn... */
2651 fmt = GET_RTX_FORMAT (code);
2652 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2656 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
2657 insn_class = WORST_CLASS (insn_class, tmp_class);
2659 else if (fmt[i] == 'E')
2662 for (j = 0; j < XVECLEN (x, i); j++)
2664 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
2665 insn_class = WORST_CLASS (insn_class, tmp_class);
2666 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2670 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2677 /* Classifies insn for the purpose of verifying that it can be
2678 moved speculatively, by examining it's patterns, returning:
2679 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2680 TRAP_FREE: non-load insn.
2681 IFREE: load from a globaly safe location.
2682 IRISKY: volatile load.
2683 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2684 being either PFREE or PRISKY. */
2687 haifa_classify_insn (insn)
2690 rtx pat = PATTERN (insn);
2691 int tmp_class = TRAP_FREE;
2692 int insn_class = TRAP_FREE;
2695 if (GET_CODE (pat) == PARALLEL)
2697 int i, len = XVECLEN (pat, 0);
2699 for (i = len - 1; i >= 0; i--)
2701 code = GET_CODE (XVECEXP (pat, 0, i));
2705 /* Test if it is a 'store'. */
2706 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
2709 /* Test if it is a store. */
2710 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
2711 if (tmp_class == TRAP_RISKY)
2713 /* Test if it is a load. */
2715 WORST_CLASS (tmp_class,
2716 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 0));
2720 tmp_class = TRAP_RISKY;
2724 insn_class = WORST_CLASS (insn_class, tmp_class);
2725 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2731 code = GET_CODE (pat);
2735 /* Test if it is a 'store'. */
2736 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
2739 /* Test if it is a store. */
2740 tmp_class = may_trap_exp (SET_DEST (pat), 1);
2741 if (tmp_class == TRAP_RISKY)
2743 /* Test if it is a load. */
2745 WORST_CLASS (tmp_class,
2746 may_trap_exp (SET_SRC (pat), 0));
2750 tmp_class = TRAP_RISKY;
2754 insn_class = tmp_class;
2760 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2761 a load moved speculatively, or if load_insn is protected by
2762 a compare on load_insn's address). */
2765 is_prisky (load_insn, bb_src, bb_trg)
2769 if (FED_BY_SPEC_LOAD (load_insn))
2772 if (LOG_LINKS (load_insn) == NULL)
2773 /* Dependence may 'hide' out of the region. */
2776 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2782 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2783 Return 1 if insn is exception-free (and the motion is valid)
2787 is_exception_free (insn, bb_src, bb_trg)
2791 int insn_class = haifa_classify_insn (insn);
2793 /* Handle non-load insns. */
2804 if (!flag_schedule_speculative_load)
2806 IS_LOAD_INSN (insn) = 1;
2813 case PFREE_CANDIDATE:
2814 if (is_pfree (insn, bb_src, bb_trg))
2816 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2817 case PRISKY_CANDIDATE:
2818 if (!flag_schedule_speculative_load_dangerous
2819 || is_prisky (insn, bb_src, bb_trg))
2825 return flag_schedule_speculative_load_dangerous;
2828 /* Process an insn's memory dependencies. There are four kinds of
2831 (0) read dependence: read follows read
2832 (1) true dependence: read follows write
2833 (2) anti dependence: write follows read
2834 (3) output dependence: write follows write
2836 We are careful to build only dependencies which actually exist, and
2837 use transitivity to avoid building too many links. */
2839 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0
2842 HAIFA_INLINE static char
2843 find_insn_mem_list (insn, x, list, list1)
2849 if (XEXP (list, 0) == insn
2850 && XEXP (list1, 0) == x)
2852 list = XEXP (list, 1);
2853 list1 = XEXP (list1, 1);
2858 /* Compute the function units used by INSN. This caches the value
2859 returned by function_units_used. A function unit is encoded as the
2860 unit number if the value is non-negative and the compliment of a
2861 mask if the value is negative. A function unit index is the
2862 non-negative encoding. */
2864 HAIFA_INLINE static int
2868 register int unit = INSN_UNIT (insn);
2872 recog_memoized (insn);
2874 /* A USE insn, or something else we don't need to understand.
2875 We can't pass these directly to function_units_used because it will
2876 trigger a fatal error for unrecognizable insns. */
2877 if (INSN_CODE (insn) < 0)
2881 unit = function_units_used (insn);
2882 /* Increment non-negative values so we can cache zero. */
2886 /* We only cache 16 bits of the result, so if the value is out of
2887 range, don't cache it. */
2888 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
2890 || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
2891 INSN_UNIT (insn) = unit;
2893 return (unit > 0 ? unit - 1 : unit);
2896 /* Compute the blockage range for executing INSN on UNIT. This caches
2897 the value returned by the blockage_range_function for the unit.
2898 These values are encoded in an int where the upper half gives the
2899 minimum value and the lower half gives the maximum value. */
2901 HAIFA_INLINE static unsigned int
2902 blockage_range (unit, insn)
2906 unsigned int blockage = INSN_BLOCKAGE (insn);
2909 if ((int) UNIT_BLOCKED (blockage) != unit + 1)
2911 range = function_units[unit].blockage_range_function (insn);
2912 /* We only cache the blockage range for one unit and then only if
2914 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
2915 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
2918 range = BLOCKAGE_RANGE (blockage);
2923 /* A vector indexed by function unit instance giving the last insn to use
2924 the unit. The value of the function unit instance index for unit U
2925 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2926 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2928 /* A vector indexed by function unit instance giving the minimum time when
2929 the unit will unblock based on the maximum blockage cost. */
2930 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2932 /* A vector indexed by function unit number giving the number of insns
2933 that remain to use the unit. */
2934 static int unit_n_insns[FUNCTION_UNITS_SIZE];
2936 /* Reset the function unit state to the null state. */
2941 memset ((char *) unit_last_insn, 0, sizeof (unit_last_insn));
2942 memset ((char *) unit_tick, 0, sizeof (unit_tick));
2943 memset ((char *) unit_n_insns, 0, sizeof (unit_n_insns));
2946 /* Return the issue-delay of an insn. */
2948 HAIFA_INLINE static int
2949 insn_issue_delay (insn)
2953 int unit = insn_unit (insn);
2955 /* Efficiency note: in fact, we are working 'hard' to compute a
2956 value that was available in md file, and is not available in
2957 function_units[] structure. It would be nice to have this
2958 value there, too. */
2961 if (function_units[unit].blockage_range_function &&
2962 function_units[unit].blockage_function)
2963 delay = function_units[unit].blockage_function (insn, insn);
2966 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2967 if ((unit & 1) != 0 && function_units[i].blockage_range_function
2968 && function_units[i].blockage_function)
2969 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
2974 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2975 instance INSTANCE at time CLOCK if the previous actual hazard cost
2978 HAIFA_INLINE static int
2979 actual_hazard_this_instance (unit, instance, insn, clock, cost)
2980 int unit, instance, clock, cost;
2983 int tick = unit_tick[instance]; /* Issue time of the last issued insn. */
2985 if (tick - clock > cost)
2987 /* The scheduler is operating forward, so unit's last insn is the
2988 executing insn and INSN is the candidate insn. We want a
2989 more exact measure of the blockage if we execute INSN at CLOCK
2990 given when we committed the execution of the unit's last insn.
2992 The blockage value is given by either the unit's max blockage
2993 constant, blockage range function, or blockage function. Use
2994 the most exact form for the given unit. */
2996 if (function_units[unit].blockage_range_function)
2998 if (function_units[unit].blockage_function)
2999 tick += (function_units[unit].blockage_function
3000 (unit_last_insn[instance], insn)
3001 - function_units[unit].max_blockage);
3003 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
3004 - function_units[unit].max_blockage);
3006 if (tick - clock > cost)
3007 cost = tick - clock;
3012 /* Record INSN as having begun execution on the units encoded by UNIT at
3015 HAIFA_INLINE static void
3016 schedule_unit (unit, insn, clock)
3024 int instance = unit;
3025 #if MAX_MULTIPLICITY > 1
3026 /* Find the first free instance of the function unit and use that
3027 one. We assume that one is free. */
3028 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
3030 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
3032 instance += FUNCTION_UNITS_SIZE;
3035 unit_last_insn[instance] = insn;
3036 unit_tick[instance] = (clock + function_units[unit].max_blockage);
3039 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3040 if ((unit & 1) != 0)
3041 schedule_unit (i, insn, clock);
3044 /* Return the actual hazard cost of executing INSN on the units encoded by
3045 UNIT at time CLOCK if the previous actual hazard cost was COST. */
3047 HAIFA_INLINE static int
3048 actual_hazard (unit, insn, clock, cost)
3049 int unit, clock, cost;
3056 /* Find the instance of the function unit with the minimum hazard. */
3057 int instance = unit;
3058 int best_cost = actual_hazard_this_instance (unit, instance, insn,
3060 #if MAX_MULTIPLICITY > 1
3063 if (best_cost > cost)
3065 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
3067 instance += FUNCTION_UNITS_SIZE;
3068 this_cost = actual_hazard_this_instance (unit, instance, insn,
3070 if (this_cost < best_cost)
3072 best_cost = this_cost;
3073 if (this_cost <= cost)
3079 cost = MAX (cost, best_cost);
3082 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3083 if ((unit & 1) != 0)
3084 cost = actual_hazard (i, insn, clock, cost);
3089 /* Return the potential hazard cost of executing an instruction on the
3090 units encoded by UNIT if the previous potential hazard cost was COST.
3091 An insn with a large blockage time is chosen in preference to one
3092 with a smaller time; an insn that uses a unit that is more likely
3093 to be used is chosen in preference to one with a unit that is less
3094 used. We are trying to minimize a subsequent actual hazard. */
3096 HAIFA_INLINE static int
3097 potential_hazard (unit, insn, cost)
3102 unsigned int minb, maxb;
3106 minb = maxb = function_units[unit].max_blockage;
3109 if (function_units[unit].blockage_range_function)
3111 maxb = minb = blockage_range (unit, insn);
3112 maxb = MAX_BLOCKAGE_COST (maxb);
3113 minb = MIN_BLOCKAGE_COST (minb);
3118 /* Make the number of instructions left dominate. Make the
3119 minimum delay dominate the maximum delay. If all these
3120 are the same, use the unit number to add an arbitrary
3121 ordering. Other terms can be added. */
3122 ncost = minb * 0x40 + maxb;
3123 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
3130 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3131 if ((unit & 1) != 0)
3132 cost = potential_hazard (i, insn, cost);
3137 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3138 This is the number of cycles between instruction issue and
3139 instruction results. */
3141 HAIFA_INLINE static int
3142 insn_cost (insn, link, used)
3143 rtx insn, link, used;
3145 register int cost = INSN_COST (insn);
3149 recog_memoized (insn);
3151 /* A USE insn, or something else we don't need to understand.
3152 We can't pass these directly to result_ready_cost because it will
3153 trigger a fatal error for unrecognizable insns. */
3154 if (INSN_CODE (insn) < 0)
3156 INSN_COST (insn) = 1;
3161 cost = result_ready_cost (insn);
3166 INSN_COST (insn) = cost;
3170 /* In this case estimate cost without caring how insn is used. */
3171 if (link == 0 && used == 0)
3174 /* A USE insn should never require the value used to be computed. This
3175 allows the computation of a function's result and parameter values to
3176 overlap the return and call. */
3177 recog_memoized (used);
3178 if (INSN_CODE (used) < 0)
3179 LINK_COST_FREE (link) = 1;
3181 /* If some dependencies vary the cost, compute the adjustment. Most
3182 commonly, the adjustment is complete: either the cost is ignored
3183 (in the case of an output- or anti-dependence), or the cost is
3184 unchanged. These values are cached in the link as LINK_COST_FREE
3185 and LINK_COST_ZERO. */
3187 if (LINK_COST_FREE (link))
3190 else if (!LINK_COST_ZERO (link))
3194 ADJUST_COST (used, link, insn, ncost);
3197 LINK_COST_FREE (link) = 1;
3201 LINK_COST_ZERO (link) = 1;
3208 /* Compute the priority number for INSN. */
3217 if (! INSN_P (insn))
3220 if ((this_priority = INSN_PRIORITY (insn)) == 0)
3222 if (INSN_DEPEND (insn) == 0)
3223 this_priority = insn_cost (insn, 0, 0);
3225 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
3230 if (RTX_INTEGRATED_P (link))
3233 next = XEXP (link, 0);
3235 /* Critical path is meaningful in block boundaries only. */
3236 if (BLOCK_NUM (next) != BLOCK_NUM (insn))
3239 next_priority = insn_cost (insn, link, next) + priority (next);
3240 if (next_priority > this_priority)
3241 this_priority = next_priority;
3243 INSN_PRIORITY (insn) = this_priority;
3245 return this_priority;
3248 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3249 them to the unused_*_list variables, so that they can be reused. */
3252 free_pending_lists ()
3256 for (bb = 0; bb < current_nr_blocks; bb++)
3258 free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
3259 free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
3260 free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
3261 free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
3265 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3266 The MEM is a memory reference contained within INSN, which we are saving
3267 so that we can do memory aliasing on it. */
3270 add_insn_mem_dependence (deps, insn_list, mem_list, insn, mem)
3272 rtx *insn_list, *mem_list, insn, mem;
3276 link = alloc_INSN_LIST (insn, *insn_list);
3279 link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
3282 deps->pending_lists_length++;
3285 /* Make a dependency between every memory reference on the pending lists
3286 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3290 flush_pending_lists (deps, insn, only_write)
3298 while (deps->pending_read_insns && ! only_write)
3300 add_dependence (insn, XEXP (deps->pending_read_insns, 0),
3303 link = deps->pending_read_insns;
3304 deps->pending_read_insns = XEXP (deps->pending_read_insns, 1);
3305 free_INSN_LIST_node (link);
3307 link = deps->pending_read_mems;
3308 deps->pending_read_mems = XEXP (deps->pending_read_mems, 1);
3309 free_EXPR_LIST_node (link);
3311 while (deps->pending_write_insns)
3313 add_dependence (insn, XEXP (deps->pending_write_insns, 0),
3316 link = deps->pending_write_insns;
3317 deps->pending_write_insns = XEXP (deps->pending_write_insns, 1);
3318 free_INSN_LIST_node (link);
3320 link = deps->pending_write_mems;
3321 deps->pending_write_mems = XEXP (deps->pending_write_mems, 1);
3322 free_EXPR_LIST_node (link);
3324 deps->pending_lists_length = 0;
3326 /* last_pending_memory_flush is now a list of insns. */
3327 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
3328 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3330 free_INSN_LIST_list (&deps->last_pending_memory_flush);
3331 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
3334 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
3335 rtx, X, creating all dependencies generated by the write to the
3336 destination of X, and reads of everything mentioned. */
3339 sched_analyze_1 (deps, x, insn)
3345 register rtx dest = XEXP (x, 0);
3346 enum rtx_code code = GET_CODE (x);
3351 if (GET_CODE (dest) == PARALLEL
3352 && GET_MODE (dest) == BLKmode)
3355 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
3356 sched_analyze_1 (deps, XVECEXP (dest, 0, i), insn);
3357 if (GET_CODE (x) == SET)
3358 sched_analyze_2 (deps, SET_SRC (x), insn);
3362 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3363 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3365 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3367 /* The second and third arguments are values read by this insn. */
3368 sched_analyze_2 (deps, XEXP (dest, 1), insn);
3369 sched_analyze_2 (deps, XEXP (dest, 2), insn);
3371 dest = XEXP (dest, 0);
3374 if (GET_CODE (dest) == REG)
3378 regno = REGNO (dest);
3380 /* A hard reg in a wide mode may really be multiple registers.
3381 If so, mark all of them just like the first. */
3382 if (regno < FIRST_PSEUDO_REGISTER)
3384 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
3390 for (u = deps->reg_last_uses[r]; u; u = XEXP (u, 1))
3391 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3393 for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
3394 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3396 /* Clobbers need not be ordered with respect to one
3397 another, but sets must be ordered with respect to a
3401 free_INSN_LIST_list (&deps->reg_last_uses[r]);
3402 for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
3403 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3404 SET_REGNO_REG_SET (reg_pending_sets, r);
3407 SET_REGNO_REG_SET (reg_pending_clobbers, r);
3409 /* Function calls clobber all call_used regs. */
3410 if (global_regs[r] || (code == SET && call_used_regs[r]))
3411 for (u = deps->last_function_call; u; u = XEXP (u, 1))
3412 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3419 for (u = deps->reg_last_uses[regno]; u; u = XEXP (u, 1))
3420 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3422 for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
3423 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3427 free_INSN_LIST_list (&deps->reg_last_uses[regno]);
3428 for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3429 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3430 SET_REGNO_REG_SET (reg_pending_sets, regno);
3433 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
3435 /* Pseudos that are REG_EQUIV to something may be replaced
3436 by that during reloading. We need only add dependencies for
3437 the address in the REG_EQUIV note. */
3438 if (!reload_completed
3439 && reg_known_equiv_p[regno]
3440 && GET_CODE (reg_known_value[regno]) == MEM)
3441 sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
3443 /* Don't let it cross a call after scheduling if it doesn't
3444 already cross one. */
3446 if (REG_N_CALLS_CROSSED (regno) == 0)
3447 for (u = deps->last_function_call; u; u = XEXP (u, 1))
3448 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3451 else if (GET_CODE (dest) == MEM)
3453 /* Writing memory. */
3455 if (deps->pending_lists_length > 32)
3457 /* Flush all pending reads and writes to prevent the pending lists
3458 from getting any larger. Insn scheduling runs too slowly when
3459 these lists get long. The number 32 was chosen because it
3460 seems like a reasonable number. When compiling GCC with itself,
3461 this flush occurs 8 times for sparc, and 10 times for m88k using
3463 flush_pending_lists (deps, insn, 0);
3468 rtx pending, pending_mem;
3470 pending = deps->pending_read_insns;
3471 pending_mem = deps->pending_read_mems;
3474 if (anti_dependence (XEXP (pending_mem, 0), dest))
3475 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3477 pending = XEXP (pending, 1);
3478 pending_mem = XEXP (pending_mem, 1);
3481 pending = deps->pending_write_insns;
3482 pending_mem = deps->pending_write_mems;
3485 if (output_dependence (XEXP (pending_mem, 0), dest))
3486 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
3488 pending = XEXP (pending, 1);
3489 pending_mem = XEXP (pending_mem, 1);
3492 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
3493 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3495 add_insn_mem_dependence (deps, &deps->pending_write_insns,
3496 &deps->pending_write_mems, insn, dest);
3498 sched_analyze_2 (deps, XEXP (dest, 0), insn);
3501 /* Analyze reads. */
3502 if (GET_CODE (x) == SET)
3503 sched_analyze_2 (deps, SET_SRC (x), insn);
3506 /* Analyze the uses of memory and registers in rtx X in INSN. */
3509 sched_analyze_2 (deps, x, insn)
3516 register enum rtx_code code;
3517 register const char *fmt;
3522 code = GET_CODE (x);
3531 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3532 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3533 this does not mean that this insn is using cc0. */
3538 /* User of CC0 depends on immediately preceding insn. */
3539 set_sched_group_p (insn);
3546 int regno = REGNO (x);
3547 if (regno < FIRST_PSEUDO_REGISTER)
3551 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
3555 deps->reg_last_uses[r]
3556 = alloc_INSN_LIST (insn, deps->reg_last_uses[r]);
3558 for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
3559 add_dependence (insn, XEXP (u, 0), 0);
3561 /* ??? This should never happen. */
3562 for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
3563 add_dependence (insn, XEXP (u, 0), 0);
3565 if (call_used_regs[r] || global_regs[r])
3566 /* Function calls clobber all call_used regs. */
3567 for (u = deps->last_function_call; u; u = XEXP (u, 1))
3568 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3573 deps->reg_last_uses[regno]
3574 = alloc_INSN_LIST (insn, deps->reg_last_uses[regno]);
3576 for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
3577 add_dependence (insn, XEXP (u, 0), 0);
3579 /* ??? This should never happen. */
3580 for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3581 add_dependence (insn, XEXP (u, 0), 0);
3583 /* Pseudos that are REG_EQUIV to something may be replaced
3584 by that during reloading. We need only add dependencies for
3585 the address in the REG_EQUIV note. */
3586 if (!reload_completed
3587 && reg_known_equiv_p[regno]
3588 && GET_CODE (reg_known_value[regno]) == MEM)
3589 sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
3591 /* If the register does not already cross any calls, then add this
3592 insn to the sched_before_next_call list so that it will still
3593 not cross calls after scheduling. */
3594 if (REG_N_CALLS_CROSSED (regno) == 0)
3595 add_dependence (deps->sched_before_next_call, insn,
3603 /* Reading memory. */
3605 rtx pending, pending_mem;
3607 pending = deps->pending_read_insns;
3608 pending_mem = deps->pending_read_mems;
3611 if (read_dependence (XEXP (pending_mem, 0), x))
3612 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3614 pending = XEXP (pending, 1);
3615 pending_mem = XEXP (pending_mem, 1);
3618 pending = deps->pending_write_insns;
3619 pending_mem = deps->pending_write_mems;
3622 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
3624 add_dependence (insn, XEXP (pending, 0), 0);
3626 pending = XEXP (pending, 1);
3627 pending_mem = XEXP (pending_mem, 1);
3630 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
3631 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3633 /* Always add these dependencies to pending_reads, since
3634 this insn may be followed by a write. */
3635 add_insn_mem_dependence (deps, &deps->pending_read_insns,
3636 &deps->pending_read_mems, insn, x);
3638 /* Take advantage of tail recursion here. */
3639 sched_analyze_2 (deps, XEXP (x, 0), insn);
3643 /* Force pending stores to memory in case a trap handler needs them. */
3645 flush_pending_lists (deps, insn, 1);
3650 case UNSPEC_VOLATILE:
3654 /* Traditional and volatile asm instructions must be considered to use
3655 and clobber all hard registers, all pseudo-registers and all of
3656 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3658 Consider for instance a volatile asm that changes the fpu rounding
3659 mode. An insn should not be moved across this even if it only uses
3660 pseudo-regs because it might give an incorrectly rounded result. */
3661 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
3663 int max_reg = max_reg_num ();
3664 for (i = 0; i < max_reg; i++)
3666 for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
3667 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3668 free_INSN_LIST_list (&deps->reg_last_uses[i]);
3670 for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
3671 add_dependence (insn, XEXP (u, 0), 0);
3673 for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
3674 add_dependence (insn, XEXP (u, 0), 0);
3676 reg_pending_sets_all = 1;
3678 flush_pending_lists (deps, insn, 0);
3681 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3682 We can not just fall through here since then we would be confused
3683 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3684 traditional asms unlike their normal usage. */
3686 if (code == ASM_OPERANDS)
3688 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3689 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
3699 /* These both read and modify the result. We must handle them as writes
3700 to get proper dependencies for following instructions. We must handle
3701 them as reads to get proper dependencies from this to previous
3702 instructions. Thus we need to pass them to both sched_analyze_1
3703 and sched_analyze_2. We must call sched_analyze_2 first in order
3704 to get the proper antecedent for the read. */
3705 sched_analyze_2 (deps, XEXP (x, 0), insn);
3706 sched_analyze_1 (deps, x, insn);
3711 /* op0 = op0 + op1 */
3712 sched_analyze_2 (deps, XEXP (x, 0), insn);
3713 sched_analyze_2 (deps, XEXP (x, 1), insn);
3714 sched_analyze_1 (deps, x, insn);
3721 /* Other cases: walk the insn. */
3722 fmt = GET_RTX_FORMAT (code);
3723 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3726 sched_analyze_2 (deps, XEXP (x, i), insn);
3727 else if (fmt[i] == 'E')
3728 for (j = 0; j < XVECLEN (x, i); j++)
3729 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
3733 /* Analyze an INSN with pattern X to find all dependencies. */
3736 sched_analyze_insn (deps, x, insn, loop_notes)
3741 register RTX_CODE code = GET_CODE (x);
3743 int maxreg = max_reg_num ();
3746 if (code == COND_EXEC)
3748 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
3750 /* ??? Should be recording conditions so we reduce the number of
3751 false dependancies. */
3752 x = COND_EXEC_CODE (x);
3753 code = GET_CODE (x);
3755 if (code == SET || code == CLOBBER)
3756 sched_analyze_1 (deps, x, insn);
3757 else if (code == PARALLEL)
3760 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3762 rtx sub = XVECEXP (x, 0, i);
3763 code = GET_CODE (sub);
3765 if (code == COND_EXEC)
3767 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
3768 sub = COND_EXEC_CODE (sub);
3769 code = GET_CODE (sub);
3771 if (code == SET || code == CLOBBER)
3772 sched_analyze_1 (deps, sub, insn);
3774 sched_analyze_2 (deps, sub, insn);
3778 sched_analyze_2 (deps, x, insn);
3780 /* Mark registers CLOBBERED or used by called function. */
3781 if (GET_CODE (insn) == CALL_INSN)
3782 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3784 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3785 sched_analyze_1 (deps, XEXP (link, 0), insn);
3787 sched_analyze_2 (deps, XEXP (link, 0), insn);
3790 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3791 block, then we must be sure that no instructions are scheduled across it.
3792 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3793 become incorrect. */
3797 int max_reg = max_reg_num ();
3798 int schedule_barrier_found = 0;
3801 /* Update loop_notes with any notes from this insn. Also determine
3802 if any of the notes on the list correspond to instruction scheduling
3803 barriers (loop, eh & setjmp notes, but not range notes. */
3805 while (XEXP (link, 1))
3807 if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
3808 || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
3809 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
3810 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END
3811 || INTVAL (XEXP (link, 0)) == NOTE_INSN_SETJMP)
3812 schedule_barrier_found = 1;
3814 link = XEXP (link, 1);
3816 XEXP (link, 1) = REG_NOTES (insn);
3817 REG_NOTES (insn) = loop_notes;
3819 /* Add dependencies if a scheduling barrier was found. */
3820 if (schedule_barrier_found)
3822 for (i = 0; i < max_reg; i++)
3825 for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
3826 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3827 free_INSN_LIST_list (&deps->reg_last_uses[i]);
3829 for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
3830 add_dependence (insn, XEXP (u, 0), 0);
3832 for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
3833 add_dependence (insn, XEXP (u, 0), 0);
3835 reg_pending_sets_all = 1;
3837 flush_pending_lists (deps, insn, 0);
3842 /* Accumulate clobbers until the next set so that it will be output dependent
3843 on all of them. At the next set we can clear the clobber list, since
3844 subsequent sets will be output dependent on it. */
3845 EXECUTE_IF_SET_IN_REG_SET
3846 (reg_pending_sets, 0, i,
3848 free_INSN_LIST_list (&deps->reg_last_sets[i]);
3849 free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
3850 deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3852 EXECUTE_IF_SET_IN_REG_SET
3853 (reg_pending_clobbers, 0, i,
3855 deps->reg_last_clobbers[i]
3856 = alloc_INSN_LIST (insn, deps->reg_last_clobbers[i]);
3858 CLEAR_REG_SET (reg_pending_sets);
3859 CLEAR_REG_SET (reg_pending_clobbers);
3861 if (reg_pending_sets_all)
3863 for (i = 0; i < maxreg; i++)
3865 free_INSN_LIST_list (&deps->reg_last_sets[i]);
3866 free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
3867 deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3870 reg_pending_sets_all = 0;
3873 /* If a post-call group is still open, see if it should remain so.
3874 This insn must be a simple move of a hard reg to a pseudo or
3877 We must avoid moving these insns for correctness on
3878 SMALL_REGISTER_CLASS machines, and for special registers like
3879 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3880 hard regs for all targets. */
3882 if (deps->in_post_call_group_p)
3884 rtx tmp, set = single_set (insn);
3885 int src_regno, dest_regno;
3888 goto end_call_group;
3890 tmp = SET_DEST (set);
3891 if (GET_CODE (tmp) == SUBREG)
3892 tmp = SUBREG_REG (tmp);
3893 if (GET_CODE (tmp) == REG)
3894 dest_regno = REGNO (tmp);
3896 goto end_call_group;
3898 tmp = SET_SRC (set);
3899 if (GET_CODE (tmp) == SUBREG)
3900 tmp = SUBREG_REG (tmp);
3901 if (GET_CODE (tmp) == REG)
3902 src_regno = REGNO (tmp);
3904 goto end_call_group;
3906 if (src_regno < FIRST_PSEUDO_REGISTER
3907 || dest_regno < FIRST_PSEUDO_REGISTER)
3909 set_sched_group_p (insn);
3910 CANT_MOVE (insn) = 1;
3915 deps->in_post_call_group_p = 0;
3920 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3921 for every dependency. */
3924 sched_analyze (deps, head, tail)
3932 for (insn = head;; insn = NEXT_INSN (insn))
3934 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
3936 /* Clear out the stale LOG_LINKS from flow. */
3937 free_INSN_LIST_list (&LOG_LINKS (insn));
3939 /* Clear out stale SCHED_GROUP_P. */
3940 SCHED_GROUP_P (insn) = 0;
3942 /* Make each JUMP_INSN a scheduling barrier for memory
3944 if (GET_CODE (insn) == JUMP_INSN)
3945 deps->last_pending_memory_flush
3946 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
3947 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
3950 else if (GET_CODE (insn) == CALL_INSN)
3955 /* Clear out stale SCHED_GROUP_P. */
3956 SCHED_GROUP_P (insn) = 0;
3958 CANT_MOVE (insn) = 1;
3960 /* Clear out the stale LOG_LINKS from flow. */
3961 free_INSN_LIST_list (&LOG_LINKS (insn));
3963 /* Any instruction using a hard register which may get clobbered
3964 by a call needs to be marked as dependent on this call.
3965 This prevents a use of a hard return reg from being moved
3966 past a void call (i.e. it does not explicitly set the hard
3969 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3970 all registers, not just hard registers, may be clobbered by this
3973 /* Insn, being a CALL_INSN, magically depends on
3974 `last_function_call' already. */
3976 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
3977 && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
3979 int max_reg = max_reg_num ();
3980 for (i = 0; i < max_reg; i++)
3982 for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
3983 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3984 free_INSN_LIST_list (&deps->reg_last_uses[i]);
3986 for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
3987 add_dependence (insn, XEXP (u, 0), 0);
3989 for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
3990 add_dependence (insn, XEXP (u, 0), 0);
3992 reg_pending_sets_all = 1;
3994 /* Add a pair of REG_SAVE_NOTEs which we will later
3995 convert back into a NOTE_INSN_SETJMP note. See
3996 reemit_notes for why we use a pair of NOTEs. */
3997 REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE,
4000 REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE,
4001 GEN_INT (NOTE_INSN_SETJMP),
4006 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4007 if (call_used_regs[i] || global_regs[i])
4009 for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
4010 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
4012 for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
4013 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
4015 SET_REGNO_REG_SET (reg_pending_clobbers, i);
4019 /* For each insn which shouldn't cross a call, add a dependence
4020 between that insn and this call insn. */
4021 x = LOG_LINKS (deps->sched_before_next_call);
4024 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
4027 free_INSN_LIST_list (&LOG_LINKS (deps->sched_before_next_call));
4029 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
4032 /* In the absence of interprocedural alias analysis, we must flush
4033 all pending reads and writes, and start new dependencies starting
4034 from here. But only flush writes for constant calls (which may
4035 be passed a pointer to something we haven't written yet). */
4036 flush_pending_lists (deps, insn, CONST_CALL_P (insn));
4038 /* Depend this function call (actually, the user of this
4039 function call) on all hard register clobberage. */
4041 /* last_function_call is now a list of insns. */
4042 free_INSN_LIST_list (&deps->last_function_call);
4043 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
4045 /* Before reload, begin a post-call group, so as to keep the
4046 lifetimes of hard registers correct. */
4047 if (! reload_completed)
4048 deps->in_post_call_group_p = 1;
4051 /* See comments on reemit_notes as to why we do this.
4052 ??? Actually, the reemit_notes just say what is done, not why. */
4054 else if (GET_CODE (insn) == NOTE
4055 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_BEG
4056 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END))
4058 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn),
4060 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
4061 GEN_INT (NOTE_LINE_NUMBER (insn)),
4064 else if (GET_CODE (insn) == NOTE
4065 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
4066 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
4067 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
4068 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
4069 || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
4070 && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
4074 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
4075 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
4076 rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
4078 rtx_region = GEN_INT (0);
4080 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
4083 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
4084 GEN_INT (NOTE_LINE_NUMBER (insn)),
4086 CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
4095 /* Macros and functions for keeping the priority queue sorted, and
4096 dealing with queueing and dequeueing of instructions. */
4098 #define SCHED_SORT(READY, N_READY) \
4099 do { if ((N_READY) == 2) \
4100 swap_sort (READY, N_READY); \
4101 else if ((N_READY) > 2) \
4102 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4105 /* Returns a positive value if x is preferred; returns a negative value if
4106 y is preferred. Should never return 0, since that will make the sort
4110 rank_for_schedule (x, y)
4114 rtx tmp = *(const rtx *) y;
4115 rtx tmp2 = *(const rtx *) x;
4117 int tmp_class, tmp2_class, depend_count1, depend_count2;
4118 int val, priority_val, spec_val, prob_val, weight_val;
4120 /* Prefer insn with higher priority. */
4121 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
4123 return priority_val;
4125 /* Prefer an insn with smaller contribution to registers-pressure. */
4126 if (!reload_completed &&
4127 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
4128 return (weight_val);
4130 /* Some comparison make sense in interblock scheduling only. */
4131 if (INSN_BB (tmp) != INSN_BB (tmp2))
4133 /* Prefer an inblock motion on an interblock motion. */
4134 if ((INSN_BB (tmp2) == target_bb) && (INSN_BB (tmp) != target_bb))
4136 if ((INSN_BB (tmp) == target_bb) && (INSN_BB (tmp2) != target_bb))
4139 /* Prefer a useful motion on a speculative one. */
4140 if ((spec_val = IS_SPECULATIVE_INSN (tmp) - IS_SPECULATIVE_INSN (tmp2)))
4143 /* Prefer a more probable (speculative) insn. */
4144 prob_val = INSN_PROBABILITY (tmp2) - INSN_PROBABILITY (tmp);
4149 /* Compare insns based on their relation to the last-scheduled-insn. */
4150 if (last_scheduled_insn)
4152 /* Classify the instructions into three classes:
4153 1) Data dependent on last schedule insn.
4154 2) Anti/Output dependent on last scheduled insn.
4155 3) Independent of last scheduled insn, or has latency of one.
4156 Choose the insn from the highest numbered class if different. */
4157 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
4158 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
4160 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4165 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
4166 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
4168 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4173 if ((val = tmp2_class - tmp_class))
4177 /* Prefer the insn which has more later insns that depend on it.
4178 This gives the scheduler more freedom when scheduling later
4179 instructions at the expense of added register pressure. */
4181 for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
4185 for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
4188 val = depend_count2 - depend_count1;
4192 /* If insns are equally good, sort by INSN_LUID (original insn order),
4193 so that we make the sort stable. This minimizes instruction movement,
4194 thus minimizing sched's effect on debugging and cross-jumping. */
4195 return INSN_LUID (tmp) - INSN_LUID (tmp2);
4198 /* Resort the array A in which only element at index N may be out of order. */
4200 HAIFA_INLINE static void
4205 rtx insn = a[n - 1];
4208 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
4216 /* Add INSN to the insn queue so that it can be executed at least
4217 N_CYCLES after the currently executing insn. Preserve insns
4218 chain for debugging purposes. */
4220 HAIFA_INLINE static void
4221 queue_insn (insn, n_cycles)
4225 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
4226 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
4227 insn_queue[next_q] = link;
4230 if (sched_verbose >= 2)
4232 fprintf (dump, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn));
4234 if (INSN_BB (insn) != target_bb)
4235 fprintf (dump, "(b%d) ", BLOCK_NUM (insn));
4237 fprintf (dump, "queued for %d cycles.\n", n_cycles);
4241 /* Return a pointer to the bottom of the ready list, i.e. the insn
4242 with the lowest priority. */
4244 HAIFA_INLINE static rtx *
4245 ready_lastpos (ready)
4246 struct ready_list *ready;
4248 if (ready->n_ready == 0)
4250 return ready->vec + ready->first - ready->n_ready + 1;
4253 /* Add an element INSN to the ready list so that it ends up with the lowest
4256 HAIFA_INLINE static void
4257 ready_add (ready, insn)
4258 struct ready_list *ready;
4261 if (ready->first == ready->n_ready)
4263 memmove (ready->vec + ready->veclen - ready->n_ready,
4264 ready_lastpos (ready),
4265 ready->n_ready * sizeof (rtx));
4266 ready->first = ready->veclen - 1;
4268 ready->vec[ready->first - ready->n_ready] = insn;
4272 /* Remove the element with the highest priority from the ready list and
4275 HAIFA_INLINE static rtx
4276 ready_remove_first (ready)
4277 struct ready_list *ready;
4280 if (ready->n_ready == 0)
4282 t = ready->vec[ready->first--];
4284 /* If the queue becomes empty, reset it. */
4285 if (ready->n_ready == 0)
4286 ready->first = ready->veclen - 1;
4290 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
4293 HAIFA_INLINE static void
4295 struct ready_list *ready;
4297 rtx *first = ready_lastpos (ready);
4298 SCHED_SORT (first, ready->n_ready);
4301 /* PREV is an insn that is ready to execute. Adjust its priority if that
4302 will help shorten or lengthen register lifetimes as appropriate. Also
4303 provide a hook for the target to tweek itself. */
4305 HAIFA_INLINE static void
4306 adjust_priority (prev)
4307 rtx prev ATTRIBUTE_UNUSED;
4309 /* ??? There used to be code here to try and estimate how an insn
4310 affected register lifetimes, but it did it by looking at REG_DEAD
4311 notes, which we removed in schedule_region. Nor did it try to
4312 take into account register pressure or anything useful like that.
4314 Revisit when we have a machine model to work with and not before. */
4316 #ifdef ADJUST_PRIORITY
4317 ADJUST_PRIORITY (prev);
4321 /* Clock at which the previous instruction was issued. */
4322 static int last_clock_var;
4324 /* INSN is the "currently executing insn". Launch each insn which was
4325 waiting on INSN. READY is the ready list which contains the insns
4326 that are ready to fire. CLOCK is the current cycle.
4330 schedule_insn (insn, ready, clock)
4332 struct ready_list *ready;
4338 unit = insn_unit (insn);
4340 if (sched_verbose >= 2)
4342 fprintf (dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
4344 insn_print_units (insn);
4345 fprintf (dump, "\n");
4348 if (sched_verbose && unit == -1)
4349 visualize_no_unit (insn);
4351 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
4352 schedule_unit (unit, insn, clock);
4354 if (INSN_DEPEND (insn) == 0)
4357 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
4359 rtx next = XEXP (link, 0);
4360 int cost = insn_cost (insn, link, next);
4362 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
4364 if ((INSN_DEP_COUNT (next) -= 1) == 0)
4366 int effective_cost = INSN_TICK (next) - clock;
4368 /* For speculative insns, before inserting to ready/queue,
4369 check live, exception-free, and issue-delay. */
4370 if (INSN_BB (next) != target_bb
4371 && (!IS_VALID (INSN_BB (next))
4373 || (IS_SPECULATIVE_INSN (next)
4374 && (insn_issue_delay (next) > 3
4375 || !check_live (next, INSN_BB (next))
4376 || !is_exception_free (next, INSN_BB (next), target_bb)))))
4379 if (sched_verbose >= 2)
4381 fprintf (dump, ";;\t\tdependences resolved: insn %d ",
4384 if (current_nr_blocks > 1 && INSN_BB (next) != target_bb)
4385 fprintf (dump, "/b%d ", BLOCK_NUM (next));
4387 if (effective_cost < 1)
4388 fprintf (dump, "into ready\n");
4390 fprintf (dump, "into queue with cost=%d\n", effective_cost);
4393 /* Adjust the priority of NEXT and either put it on the ready
4394 list or queue it. */
4395 adjust_priority (next);
4396 if (effective_cost < 1)
4397 ready_add (ready, next);
4399 queue_insn (next, effective_cost);
4403 /* Annotate the instruction with issue information -- TImode
4404 indicates that the instruction is expected not to be able
4405 to issue on the same cycle as the previous insn. A machine
4406 may use this information to decide how the instruction should
4408 if (reload_completed && issue_rate > 1)
4410 PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
4411 last_clock_var = clock;
4415 /* Functions for handling of notes. */
4417 /* Delete notes beginning with INSN and put them in the chain
4418 of notes ended by NOTE_LIST.
4419 Returns the insn following the notes. */
4422 unlink_other_notes (insn, tail)
4425 rtx prev = PREV_INSN (insn);
4427 while (insn != tail && GET_CODE (insn) == NOTE)
4429 rtx next = NEXT_INSN (insn);
4430 /* Delete the note from its current position. */
4432 NEXT_INSN (prev) = next;
4434 PREV_INSN (next) = prev;
4436 /* See sched_analyze to see how these are handled. */
4437 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
4438 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
4439 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
4440 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_BEG
4441 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
4442 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
4443 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
4445 /* Insert the note at the end of the notes list. */
4446 PREV_INSN (insn) = note_list;
4448 NEXT_INSN (note_list) = insn;
4457 /* Delete line notes beginning with INSN. Record line-number notes so
4458 they can be reused. Returns the insn following the notes. */
4461 unlink_line_notes (insn, tail)
4464 rtx prev = PREV_INSN (insn);
4466 while (insn != tail && GET_CODE (insn) == NOTE)
4468 rtx next = NEXT_INSN (insn);
4470 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
4472 /* Delete the note from its current position. */
4474 NEXT_INSN (prev) = next;
4476 PREV_INSN (next) = prev;
4478 /* Record line-number notes so they can be reused. */
4479 LINE_NOTE (insn) = insn;
4489 /* Return the head and tail pointers of BB. */
4491 HAIFA_INLINE static void
4492 get_block_head_tail (b, headp, tailp)
4501 /* HEAD and TAIL delimit the basic block being scheduled. */
4502 head = BLOCK_HEAD (b);
4503 tail = BLOCK_END (b);
4505 /* Don't include any notes or labels at the beginning of the
4506 basic block, or notes at the ends of basic blocks. */
4507 while (head != tail)
4509 if (GET_CODE (head) == NOTE)
4510 head = NEXT_INSN (head);
4511 else if (GET_CODE (tail) == NOTE)
4512 tail = PREV_INSN (tail);
4513 else if (GET_CODE (head) == CODE_LABEL)
4514 head = NEXT_INSN (head);
4523 HAIFA_INLINE static void
4524 get_bb_head_tail (bb, headp, tailp)
4529 get_block_head_tail (BB_TO_BLOCK (bb), headp, tailp);
4532 /* Delete line notes from bb. Save them so they can be later restored
4533 (in restore_line_notes ()). */
4544 get_bb_head_tail (bb, &head, &tail);
4546 if (head == tail && (! INSN_P (head)))
4549 next_tail = NEXT_INSN (tail);
4550 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4554 /* Farm out notes, and maybe save them in NOTE_LIST.
4555 This is needed to keep the debugger from
4556 getting completely deranged. */
4557 if (GET_CODE (insn) == NOTE)
4560 insn = unlink_line_notes (insn, next_tail);
4566 if (insn == next_tail)
4572 /* Save line number notes for each insn in bb. */
4575 save_line_notes (bb)
4581 /* We must use the true line number for the first insn in the block
4582 that was computed and saved at the start of this pass. We can't
4583 use the current line number, because scheduling of the previous
4584 block may have changed the current line number. */
4586 rtx line = line_note_head[BB_TO_BLOCK (bb)];
4589 get_bb_head_tail (bb, &head, &tail);
4590 next_tail = NEXT_INSN (tail);
4592 for (insn = BLOCK_HEAD (BB_TO_BLOCK (bb));
4594 insn = NEXT_INSN (insn))
4595 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4598 LINE_NOTE (insn) = line;
4601 /* After bb was scheduled, insert line notes into the insns list. */
4604 restore_line_notes (bb)
4607 rtx line, note, prev, new;
4608 int added_notes = 0;
4610 rtx head, next_tail, insn;
4612 b = BB_TO_BLOCK (bb);
4614 head = BLOCK_HEAD (b);
4615 next_tail = NEXT_INSN (BLOCK_END (b));
4617 /* Determine the current line-number. We want to know the current
4618 line number of the first insn of the block here, in case it is
4619 different from the true line number that was saved earlier. If
4620 different, then we need a line number note before the first insn
4621 of this block. If it happens to be the same, then we don't want to
4622 emit another line number note here. */
4623 for (line = head; line; line = PREV_INSN (line))
4624 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4627 /* Walk the insns keeping track of the current line-number and inserting
4628 the line-number notes as needed. */
4629 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4630 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4632 /* This used to emit line number notes before every non-deleted note.
4633 However, this confuses a debugger, because line notes not separated
4634 by real instructions all end up at the same address. I can find no
4635 use for line number notes before other notes, so none are emitted. */
4636 else if (GET_CODE (insn) != NOTE
4637 && (note = LINE_NOTE (insn)) != 0
4640 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
4641 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
4644 prev = PREV_INSN (insn);
4645 if (LINE_NOTE (note))
4647 /* Re-use the original line-number note. */
4648 LINE_NOTE (note) = 0;
4649 PREV_INSN (note) = prev;
4650 NEXT_INSN (prev) = note;
4651 PREV_INSN (insn) = note;
4652 NEXT_INSN (note) = insn;
4657 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
4658 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
4659 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
4662 if (sched_verbose && added_notes)
4663 fprintf (dump, ";; added %d line-number notes\n", added_notes);
4666 /* After scheduling the function, delete redundant line notes from the
4670 rm_redundant_line_notes ()
4673 rtx insn = get_insns ();
4674 int active_insn = 0;
4677 /* Walk the insns deleting redundant line-number notes. Many of these
4678 are already present. The remainder tend to occur at basic
4679 block boundaries. */
4680 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4681 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4683 /* If there are no active insns following, INSN is redundant. */
4684 if (active_insn == 0)
4687 NOTE_SOURCE_FILE (insn) = 0;
4688 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4690 /* If the line number is unchanged, LINE is redundant. */
4692 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
4693 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
4696 NOTE_SOURCE_FILE (line) = 0;
4697 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
4704 else if (!((GET_CODE (insn) == NOTE
4705 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
4706 || (GET_CODE (insn) == INSN
4707 && (GET_CODE (PATTERN (insn)) == USE
4708 || GET_CODE (PATTERN (insn)) == CLOBBER))))
4711 if (sched_verbose && notes)
4712 fprintf (dump, ";; deleted %d line-number notes\n", notes);
4715 /* Delete notes between head and tail and put them in the chain
4716 of notes ended by NOTE_LIST. */
4719 rm_other_notes (head, tail)
4726 if (head == tail && (! INSN_P (head)))
4729 next_tail = NEXT_INSN (tail);
4730 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4734 /* Farm out notes, and maybe save them in NOTE_LIST.
4735 This is needed to keep the debugger from
4736 getting completely deranged. */
4737 if (GET_CODE (insn) == NOTE)
4741 insn = unlink_other_notes (insn, next_tail);
4747 if (insn == next_tail)
4753 /* Functions for computation of registers live/usage info. */
4755 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
4758 find_insn_reg_weight (b)
4761 rtx insn, next_tail, head, tail;
4763 get_block_head_tail (b, &head, &tail);
4764 next_tail = NEXT_INSN (tail);
4766 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4771 /* Handle register life information. */
4772 if (! INSN_P (insn))
4775 /* Increment weight for each register born here. */
4777 if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
4778 && register_operand (SET_DEST (x), VOIDmode))
4780 else if (GET_CODE (x) == PARALLEL)
4783 for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
4785 x = XVECEXP (PATTERN (insn), 0, j);
4786 if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
4787 && register_operand (SET_DEST (x), VOIDmode))
4792 /* Decrement weight for each register that dies here. */
4793 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
4795 if (REG_NOTE_KIND (x) == REG_DEAD
4796 || REG_NOTE_KIND (x) == REG_UNUSED)
4800 INSN_REG_WEIGHT (insn) = reg_weight;
4804 /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
4805 static int clock_var;
4807 /* Move insns that became ready to fire from queue to ready list. */
4810 queue_to_ready (ready)
4811 struct ready_list *ready;
4816 q_ptr = NEXT_Q (q_ptr);
4818 /* Add all pending insns that can be scheduled without stalls to the
4820 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
4822 insn = XEXP (link, 0);
4825 if (sched_verbose >= 2)
4826 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
4828 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
4829 fprintf (dump, "(b%d) ", BLOCK_NUM (insn));
4831 ready_add (ready, insn);
4832 if (sched_verbose >= 2)
4833 fprintf (dump, "moving to ready without stalls\n");
4835 insn_queue[q_ptr] = 0;
4837 /* If there are no ready insns, stall until one is ready and add all
4838 of the pending insns at that point to the ready list. */
4839 if (ready->n_ready == 0)
4841 register int stalls;
4843 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
4845 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
4847 for (; link; link = XEXP (link, 1))
4849 insn = XEXP (link, 0);
4852 if (sched_verbose >= 2)
4853 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ",
4856 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
4857 fprintf (dump, "(b%d) ", BLOCK_NUM (insn));
4859 ready_add (ready, insn);
4860 if (sched_verbose >= 2)
4861 fprintf (dump, "moving to ready with %d stalls\n", stalls);
4863 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
4870 if (sched_verbose && stalls)
4871 visualize_stall_cycles (BB_TO_BLOCK (target_bb), stalls);
4872 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
4873 clock_var += stalls;
4877 /* Print the ready list for debugging purposes. Callable from debugger. */
4880 debug_ready_list (ready)
4881 struct ready_list *ready;
4886 if (ready->n_ready == 0)
4889 p = ready_lastpos (ready);
4890 for (i = 0; i < ready->n_ready; i++)
4892 fprintf (dump, " %d", INSN_UID (p[i]));
4893 if (current_nr_blocks > 1 && INSN_BB (p[i]) != target_bb)
4894 fprintf (dump, "/b%d", BLOCK_NUM (p[i]));
4896 fprintf (dump, "\n");
4899 /* Print names of units on which insn can/should execute, for debugging. */
4902 insn_print_units (insn)
4906 int unit = insn_unit (insn);
4909 fprintf (dump, "none");
4911 fprintf (dump, "%s", function_units[unit].name);
4914 fprintf (dump, "[");
4915 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
4918 fprintf (dump, "%s", function_units[i].name);
4920 fprintf (dump, " ");
4922 fprintf (dump, "]");
4926 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
4927 of a basic block. If more lines are needed, table is splitted to two.
4928 n_visual_lines is the number of lines printed so far for a block.
4929 visual_tbl contains the block visualization info.
4930 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
4931 #define MAX_VISUAL_LINES 100
4936 rtx vis_no_unit[10];
4938 /* Finds units that are in use in this fuction. Required only
4939 for visualization. */
4942 init_target_units ()
4947 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4949 if (! INSN_P (insn))
4952 unit = insn_unit (insn);
4955 target_units |= ~unit;
4957 target_units |= (1 << unit);
4961 /* Return the length of the visualization table. */
4964 get_visual_tbl_length ()
4970 /* Compute length of one field in line. */
4971 s = (char *) alloca (INSN_LEN + 6);
4972 sprintf (s, " %33s", "uname");
4975 /* Compute length of one line. */
4978 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
4979 if (function_units[unit].bitmask & target_units)
4980 for (i = 0; i < function_units[unit].multiplicity; i++)
4983 n += strlen ("\n") + 2;
4985 /* Compute length of visualization string. */
4986 return (MAX_VISUAL_LINES * n);
4989 /* Init block visualization debugging info. */
4992 init_block_visualization ()
4994 strcpy (visual_tbl, "");
4999 #define BUF_LEN 2048
5002 safe_concat (buf, cur, str)
5007 char *end = buf + BUF_LEN - 2; /* Leave room for null. */
5016 while (cur < end && (c = *str++) != '\0')
5023 /* This recognizes rtx, I classified as expressions. These are always
5024 represent some action on values or results of other expression, that
5025 may be stored in objects representing values. */
5028 print_exp (buf, x, verbose)
5036 const char *fun = (char *) 0;
5041 for (i = 0; i < 4; i++)
5047 switch (GET_CODE (x))
5050 op[0] = XEXP (x, 0);
5051 if (GET_CODE (XEXP (x, 1)) == CONST_INT
5052 && INTVAL (XEXP (x, 1)) < 0)
5055 op[1] = GEN_INT (-INTVAL (XEXP (x, 1)));
5060 op[1] = XEXP (x, 1);
5064 op[0] = XEXP (x, 0);
5066 op[1] = XEXP (x, 1);
5070 op[0] = XEXP (x, 0);
5072 op[1] = XEXP (x, 1);
5076 op[0] = XEXP (x, 0);
5077 op[1] = XEXP (x, 1);
5081 op[0] = XEXP (x, 0);
5084 op[0] = XEXP (x, 0);
5086 op[1] = XEXP (x, 1);
5089 op[0] = XEXP (x, 0);
5091 op[1] = XEXP (x, 1);
5095 op[0] = XEXP (x, 0);
5096 op[1] = XEXP (x, 1);
5099 op[0] = XEXP (x, 0);
5101 op[1] = XEXP (x, 1);
5105 op[0] = XEXP (x, 0);
5106 op[1] = XEXP (x, 1);
5110 op[0] = XEXP (x, 0);
5111 op[1] = XEXP (x, 1);
5115 op[0] = XEXP (x, 0);
5116 op[1] = XEXP (x, 1);
5120 op[0] = XEXP (x, 0);
5121 op[1] = XEXP (x, 1);
5125 op[0] = XEXP (x, 0);
5126 op[1] = XEXP (x, 1);
5130 op[0] = XEXP (x, 0);
5133 op[0] = XEXP (x, 0);
5135 op[1] = XEXP (x, 1);
5138 op[0] = XEXP (x, 0);
5140 op[1] = XEXP (x, 1);
5143 op[0] = XEXP (x, 0);
5145 op[1] = XEXP (x, 1);
5148 op[0] = XEXP (x, 0);
5150 op[1] = XEXP (x, 1);
5153 op[0] = XEXP (x, 0);
5155 op[1] = XEXP (x, 1);
5158 op[0] = XEXP (x, 0);
5160 op[1] = XEXP (x, 1);
5163 op[0] = XEXP (x, 0);
5165 op[1] = XEXP (x, 1);
5168 op[0] = XEXP (x, 0);
5170 op[1] = XEXP (x, 1);
5174 op[0] = XEXP (x, 0);
5178 op[0] = XEXP (x, 0);
5182 op[0] = XEXP (x, 0);
5185 op[0] = XEXP (x, 0);
5187 op[1] = XEXP (x, 1);
5190 op[0] = XEXP (x, 0);
5192 op[1] = XEXP (x, 1);
5195 op[0] = XEXP (x, 0);
5197 op[1] = XEXP (x, 1);
5201 op[0] = XEXP (x, 0);
5202 op[1] = XEXP (x, 1);
5205 op[0] = XEXP (x, 0);
5207 op[1] = XEXP (x, 1);
5211 op[0] = XEXP (x, 0);
5212 op[1] = XEXP (x, 1);
5215 op[0] = XEXP (x, 0);
5217 op[1] = XEXP (x, 1);
5221 op[0] = XEXP (x, 0);
5222 op[1] = XEXP (x, 1);
5225 op[0] = XEXP (x, 0);
5227 op[1] = XEXP (x, 1);
5231 op[0] = XEXP (x, 0);
5232 op[1] = XEXP (x, 1);
5235 fun = (verbose) ? "sign_extract" : "sxt";
5236 op[0] = XEXP (x, 0);
5237 op[1] = XEXP (x, 1);
5238 op[2] = XEXP (x, 2);
5241 fun = (verbose) ? "zero_extract" : "zxt";
5242 op[0] = XEXP (x, 0);
5243 op[1] = XEXP (x, 1);
5244 op[2] = XEXP (x, 2);
5247 fun = (verbose) ? "sign_extend" : "sxn";
5248 op[0] = XEXP (x, 0);
5251 fun = (verbose) ? "zero_extend" : "zxn";
5252 op[0] = XEXP (x, 0);
5255 fun = (verbose) ? "float_extend" : "fxn";
5256 op[0] = XEXP (x, 0);
5259 fun = (verbose) ? "trunc" : "trn";
5260 op[0] = XEXP (x, 0);
5262 case FLOAT_TRUNCATE:
5263 fun = (verbose) ? "float_trunc" : "ftr";
5264 op[0] = XEXP (x, 0);
5267 fun = (verbose) ? "float" : "flt";
5268 op[0] = XEXP (x, 0);
5270 case UNSIGNED_FLOAT:
5271 fun = (verbose) ? "uns_float" : "ufl";
5272 op[0] = XEXP (x, 0);
5276 op[0] = XEXP (x, 0);
5279 fun = (verbose) ? "uns_fix" : "ufx";
5280 op[0] = XEXP (x, 0);
5284 op[0] = XEXP (x, 0);
5288 op[0] = XEXP (x, 0);
5291 op[0] = XEXP (x, 0);
5295 op[0] = XEXP (x, 0);
5300 op[0] = XEXP (x, 0);
5304 op[1] = XEXP (x, 1);
5309 op[0] = XEXP (x, 0);
5311 op[1] = XEXP (x, 1);
5313 op[2] = XEXP (x, 2);
5318 op[0] = TRAP_CONDITION (x);
5321 case UNSPEC_VOLATILE:
5323 cur = safe_concat (buf, cur, "unspec");
5324 if (GET_CODE (x) == UNSPEC_VOLATILE)
5325 cur = safe_concat (buf, cur, "/v");
5326 cur = safe_concat (buf, cur, "[");
5328 for (i = 0; i < XVECLEN (x, 0); i++)
5330 print_pattern (tmp, XVECEXP (x, 0, i), verbose);
5331 cur = safe_concat (buf, cur, sep);
5332 cur = safe_concat (buf, cur, tmp);
5335 cur = safe_concat (buf, cur, "] ");
5336 sprintf (tmp, "%d", XINT (x, 1));
5337 cur = safe_concat (buf, cur, tmp);
5341 /* If (verbose) debug_rtx (x); */
5342 st[0] = GET_RTX_NAME (GET_CODE (x));
5346 /* Print this as a function? */
5349 cur = safe_concat (buf, cur, fun);
5350 cur = safe_concat (buf, cur, "(");
5353 for (i = 0; i < 4; i++)
5356 cur = safe_concat (buf, cur, st[i]);
5361 cur = safe_concat (buf, cur, ",");
5363 print_value (tmp, op[i], verbose);
5364 cur = safe_concat (buf, cur, tmp);
5369 cur = safe_concat (buf, cur, ")");
5372 /* Prints rtxes, I customly classified as values. They're constants,
5373 registers, labels, symbols and memory accesses. */
5376 print_value (buf, x, verbose)
5384 switch (GET_CODE (x))
5387 sprintf (t, HOST_WIDE_INT_PRINT_HEX, INTVAL (x));
5388 cur = safe_concat (buf, cur, t);
5391 sprintf (t, "<0x%lx,0x%lx>", (long) XWINT (x, 2), (long) XWINT (x, 3));
5392 cur = safe_concat (buf, cur, t);
5395 cur = safe_concat (buf, cur, "\"");
5396 cur = safe_concat (buf, cur, XSTR (x, 0));
5397 cur = safe_concat (buf, cur, "\"");
5400 cur = safe_concat (buf, cur, "`");
5401 cur = safe_concat (buf, cur, XSTR (x, 0));
5402 cur = safe_concat (buf, cur, "'");
5405 sprintf (t, "L%d", INSN_UID (XEXP (x, 0)));
5406 cur = safe_concat (buf, cur, t);
5409 print_value (t, XEXP (x, 0), verbose);
5410 cur = safe_concat (buf, cur, "const(");
5411 cur = safe_concat (buf, cur, t);
5412 cur = safe_concat (buf, cur, ")");
5415 print_value (t, XEXP (x, 0), verbose);
5416 cur = safe_concat (buf, cur, "high(");
5417 cur = safe_concat (buf, cur, t);
5418 cur = safe_concat (buf, cur, ")");
5421 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
5423 int c = reg_names[REGNO (x)][0];
5424 if (c >= '0' && c <= '9')
5425 cur = safe_concat (buf, cur, "%");
5427 cur = safe_concat (buf, cur, reg_names[REGNO (x)]);
5431 sprintf (t, "r%d", REGNO (x));
5432 cur = safe_concat (buf, cur, t);
5436 print_value (t, SUBREG_REG (x), verbose);
5437 cur = safe_concat (buf, cur, t);
5438 sprintf (t, "#%d", SUBREG_WORD (x));
5439 cur = safe_concat (buf, cur, t);
5442 cur = safe_concat (buf, cur, "scratch");
5445 cur = safe_concat (buf, cur, "cc0");
5448 cur = safe_concat (buf, cur, "pc");
5451 print_value (t, XEXP (x, 0), verbose);
5452 cur = safe_concat (buf, cur, "[");
5453 cur = safe_concat (buf, cur, t);
5454 cur = safe_concat (buf, cur, "]");
5457 print_exp (t, x, verbose);
5458 cur = safe_concat (buf, cur, t);
5463 /* The next step in insn detalization, its pattern recognition. */
5466 print_pattern (buf, x, verbose)
5471 char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
5473 switch (GET_CODE (x))
5476 print_value (t1, SET_DEST (x), verbose);
5477 print_value (t2, SET_SRC (x), verbose);
5478 sprintf (buf, "%s=%s", t1, t2);
5481 sprintf (buf, "return");
5484 print_exp (buf, x, verbose);
5487 print_value (t1, XEXP (x, 0), verbose);
5488 sprintf (buf, "clobber %s", t1);
5491 print_value (t1, XEXP (x, 0), verbose);
5492 sprintf (buf, "use %s", t1);
5495 print_value (t1, COND_EXEC_CODE (x), verbose);
5496 print_value (t2, COND_EXEC_TEST (x), verbose);
5497 sprintf (buf, "cond_exec %s %s", t1, t2);
5504 for (i = 0; i < XVECLEN (x, 0); i++)
5506 print_pattern (t2, XVECEXP (x, 0, i), verbose);
5507 sprintf (t3, "%s%s;", t1, t2);
5510 sprintf (buf, "%s}", t1);
5517 sprintf (t1, "%%{");
5518 for (i = 0; i < XVECLEN (x, 0); i++)
5520 print_insn (t2, XVECEXP (x, 0, i), verbose);
5521 sprintf (t3, "%s%s;", t1, t2);
5524 sprintf (buf, "%s%%}", t1);
5528 sprintf (buf, "asm {%s}", XSTR (x, 0));
5533 print_value (buf, XEXP (x, 0), verbose);
5536 print_value (t1, TRAP_CONDITION (x), verbose);
5537 sprintf (buf, "trap_if %s", t1);
5543 sprintf (t1, "unspec{");
5544 for (i = 0; i < XVECLEN (x, 0); i++)
5546 print_pattern (t2, XVECEXP (x, 0, i), verbose);
5547 sprintf (t3, "%s%s;", t1, t2);
5550 sprintf (buf, "%s}", t1);
5553 case UNSPEC_VOLATILE:
5557 sprintf (t1, "unspec/v{");
5558 for (i = 0; i < XVECLEN (x, 0); i++)
5560 print_pattern (t2, XVECEXP (x, 0, i), verbose);
5561 sprintf (t3, "%s%s;", t1, t2);
5564 sprintf (buf, "%s}", t1);
5568 print_value (buf, x, verbose);
5570 } /* print_pattern */
5572 /* This is the main function in rtl visualization mechanism. It
5573 accepts an rtx and tries to recognize it as an insn, then prints it
5574 properly in human readable form, resembling assembler mnemonics.
5575 For every insn it prints its UID and BB the insn belongs too.
5576 (Probably the last "option" should be extended somehow, since it
5577 depends now on sched.c inner variables ...) */
5580 print_insn (buf, x, verbose)
5588 switch (GET_CODE (x))
5591 print_pattern (t, PATTERN (x), verbose);
5593 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (x),
5596 sprintf (buf, "%-4d %s", INSN_UID (x), t);
5599 print_pattern (t, PATTERN (x), verbose);
5601 sprintf (buf, "b%d: i% 4d: jump %s", INSN_BB (x),
5604 sprintf (buf, "%-4d %s", INSN_UID (x), t);
5608 if (GET_CODE (x) == PARALLEL)
5610 x = XVECEXP (x, 0, 0);
5611 print_pattern (t, x, verbose);
5614 strcpy (t, "call <...>");
5616 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (insn),
5617 INSN_UID (insn), t);
5619 sprintf (buf, "%-4d %s", INSN_UID (insn), t);
5622 sprintf (buf, "L%d:", INSN_UID (x));
5625 sprintf (buf, "i% 4d: barrier", INSN_UID (x));
5628 if (NOTE_LINE_NUMBER (x) > 0)
5629 sprintf (buf, "%4d note \"%s\" %d", INSN_UID (x),
5630 NOTE_SOURCE_FILE (x), NOTE_LINE_NUMBER (x));
5632 sprintf (buf, "%4d %s", INSN_UID (x),
5633 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x)));
5638 sprintf (buf, "Not an INSN at all\n");
5642 sprintf (buf, "i%-4d <What?>", INSN_UID (x));
5646 /* Print visualization debugging info. */
5649 print_block_visualization (b, s)
5656 fprintf (dump, "\n;; ==================== scheduling visualization for block %d %s \n", b, s);
5658 /* Print names of units. */
5659 fprintf (dump, ";; %-8s", "clock");
5660 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5661 if (function_units[unit].bitmask & target_units)
5662 for (i = 0; i < function_units[unit].multiplicity; i++)
5663 fprintf (dump, " %-33s", function_units[unit].name);
5664 fprintf (dump, " %-8s\n", "no-unit");
5666 fprintf (dump, ";; %-8s", "=====");
5667 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5668 if (function_units[unit].bitmask & target_units)
5669 for (i = 0; i < function_units[unit].multiplicity; i++)
5670 fprintf (dump, " %-33s", "==============================");
5671 fprintf (dump, " %-8s\n", "=======");
5673 /* Print insns in each cycle. */
5674 fprintf (dump, "%s\n", visual_tbl);
5677 /* Print insns in the 'no_unit' column of visualization. */
5680 visualize_no_unit (insn)
5683 vis_no_unit[n_vis_no_unit] = insn;
5687 /* Print insns scheduled in clock, for visualization. */
5690 visualize_scheduled_insns (b, clock)
5695 /* If no more room, split table into two. */
5696 if (n_visual_lines >= MAX_VISUAL_LINES)
5698 print_block_visualization (b, "(incomplete)");
5699 init_block_visualization ();
5704 sprintf (visual_tbl + strlen (visual_tbl), ";; %-8d", clock);
5705 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5706 if (function_units[unit].bitmask & target_units)
5707 for (i = 0; i < function_units[unit].multiplicity; i++)
5709 int instance = unit + i * FUNCTION_UNITS_SIZE;
5710 rtx insn = unit_last_insn[instance];
5712 /* Print insns that still keep the unit busy. */
5714 actual_hazard_this_instance (unit, instance, insn, clock, 0))
5717 print_insn (str, insn, 0);
5718 str[INSN_LEN] = '\0';
5719 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", str);
5722 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", "------------------------------");
5725 /* Print insns that are not assigned to any unit. */
5726 for (i = 0; i < n_vis_no_unit; i++)
5727 sprintf (visual_tbl + strlen (visual_tbl), " %-8d",
5728 INSN_UID (vis_no_unit[i]));
5731 sprintf (visual_tbl + strlen (visual_tbl), "\n");
5734 /* Print stalled cycles. */
5737 visualize_stall_cycles (b, stalls)
5742 /* If no more room, split table into two. */
5743 if (n_visual_lines >= MAX_VISUAL_LINES)
5745 print_block_visualization (b, "(incomplete)");
5746 init_block_visualization ();
5751 sprintf (visual_tbl + strlen (visual_tbl), ";; ");
5752 for (i = 0; i < stalls; i++)
5753 sprintf (visual_tbl + strlen (visual_tbl), ".");
5754 sprintf (visual_tbl + strlen (visual_tbl), "\n");
5757 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
5760 move_insn1 (insn, last)
5763 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
5764 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
5766 NEXT_INSN (insn) = NEXT_INSN (last);
5767 PREV_INSN (NEXT_INSN (last)) = insn;
5769 NEXT_INSN (last) = insn;
5770 PREV_INSN (insn) = last;
5775 /* Search INSN for REG_SAVE_NOTE note pairs for NOTE_INSN_SETJMP,
5776 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
5777 NOTEs. The REG_SAVE_NOTE note following first one is contains the
5778 saved value for NOTE_BLOCK_NUMBER which is useful for
5779 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
5780 output by the instruction scheduler. Return the new value of LAST. */
5783 reemit_notes (insn, last)
5790 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
5792 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
5794 enum insn_note note_type = INTVAL (XEXP (note, 0));
5796 if (note_type == NOTE_INSN_SETJMP)
5798 retval = emit_note_after (NOTE_INSN_SETJMP, insn);
5799 CONST_CALL_P (retval) = CONST_CALL_P (note);
5800 remove_note (insn, note);
5801 note = XEXP (note, 1);
5803 else if (note_type == NOTE_INSN_RANGE_BEG
5804 || note_type == NOTE_INSN_RANGE_END)
5806 last = emit_note_before (note_type, last);
5807 remove_note (insn, note);
5808 note = XEXP (note, 1);
5809 NOTE_RANGE_INFO (last) = XEXP (note, 0);
5813 last = emit_note_before (note_type, last);
5814 remove_note (insn, note);
5815 note = XEXP (note, 1);
5816 if (note_type == NOTE_INSN_EH_REGION_BEG
5817 || note_type == NOTE_INSN_EH_REGION_END)
5818 NOTE_EH_HANDLER (last) = INTVAL (XEXP (note, 0));
5820 remove_note (insn, note);
5826 /* Move INSN, and all insns which should be issued before it,
5827 due to SCHED_GROUP_P flag. Reemit notes if needed.
5829 Return the last insn emitted by the scheduler, which is the
5830 return value from the first call to reemit_notes. */
5833 move_insn (insn, last)
5838 /* If INSN has SCHED_GROUP_P set, then issue it and any other
5839 insns with SCHED_GROUP_P set first. */
5840 while (SCHED_GROUP_P (insn))
5842 rtx prev = PREV_INSN (insn);
5844 /* Move a SCHED_GROUP_P insn. */
5845 move_insn1 (insn, last);
5846 /* If this is the first call to reemit_notes, then record
5847 its return value. */
5848 if (retval == NULL_RTX)
5849 retval = reemit_notes (insn, insn);
5851 reemit_notes (insn, insn);
5855 /* Now move the first non SCHED_GROUP_P insn. */
5856 move_insn1 (insn, last);
5858 /* If this is the first call to reemit_notes, then record
5859 its return value. */
5860 if (retval == NULL_RTX)
5861 retval = reemit_notes (insn, insn);
5863 reemit_notes (insn, insn);
5868 /* Return an insn which represents a SCHED_GROUP, which is
5869 the last insn in the group. */
5880 insn = next_nonnote_insn (insn);
5882 while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
5887 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
5888 possibly bringing insns from subsequent blocks in the same region.
5889 Return number of insns scheduled. */
5892 schedule_block (bb, rgn_n_insns)
5896 /* Local variables. */
5898 struct ready_list ready;
5901 /* Flow block of this bb. */
5902 int b = BB_TO_BLOCK (bb);
5904 /* target_n_insns == number of insns in b before scheduling starts.
5905 sched_target_n_insns == how many of b's insns were scheduled.
5906 sched_n_insns == how many insns were scheduled in b. */
5907 int target_n_insns = 0;
5908 int sched_target_n_insns = 0;
5909 int sched_n_insns = 0;
5911 #define NEED_NOTHING 0
5916 /* Head/tail info for this block. */
5923 /* We used to have code to avoid getting parameters moved from hard
5924 argument registers into pseudos.
5926 However, it was removed when it proved to be of marginal benefit
5927 and caused problems because schedule_block and compute_forward_dependences
5928 had different notions of what the "head" insn was. */
5929 get_bb_head_tail (bb, &head, &tail);
5931 /* rm_other_notes only removes notes which are _inside_ the
5932 block---that is, it won't remove notes before the first real insn
5933 or after the last real insn of the block. So if the first insn
5934 has a REG_SAVE_NOTE which would otherwise be emitted before the
5935 insn, it is redundant with the note before the start of the
5936 block, and so we have to take it out.
5938 FIXME: Probably the same thing should be done with REG_SAVE_NOTEs
5939 referencing NOTE_INSN_SETJMP at the end of the block. */
5944 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
5945 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
5947 if (INTVAL (XEXP (note, 0)) != NOTE_INSN_SETJMP)
5949 remove_note (head, note);
5950 note = XEXP (note, 1);
5951 remove_note (head, note);
5954 note = XEXP (note, 1);
5958 next_tail = NEXT_INSN (tail);
5959 prev_head = PREV_INSN (head);
5961 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
5962 to schedule this block. */
5963 if (head == tail && (! INSN_P (head)))
5964 return (sched_n_insns);
5969 fprintf (dump, ";; ======================================================\n");
5971 ";; -- basic block %d from %d to %d -- %s reload\n",
5972 b, INSN_UID (BLOCK_HEAD (b)), INSN_UID (BLOCK_END (b)),
5973 (reload_completed ? "after" : "before"));
5974 fprintf (dump, ";; ======================================================\n");
5975 fprintf (dump, "\n");
5977 visual_tbl = (char *) alloca (get_visual_tbl_length ());
5978 init_block_visualization ();
5981 /* Remove remaining note insns from the block, save them in
5982 note_list. These notes are restored at the end of
5983 schedule_block (). */
5985 rm_other_notes (head, tail);
5989 /* Prepare current target block info. */
5990 if (current_nr_blocks > 1)
5992 candidate_table = (candidate *) xmalloc (current_nr_blocks
5993 * sizeof (candidate));
5996 /* bblst_table holds split blocks and update blocks for each block after
5997 the current one in the region. split blocks and update blocks are
5998 the TO blocks of region edges, so there can be at most rgn_nr_edges
6000 bblst_size = (current_nr_blocks - bb) * rgn_nr_edges;
6001 bblst_table = (int *) xmalloc (bblst_size * sizeof (int));
6003 bitlst_table_last = 0;
6004 bitlst_table_size = rgn_nr_edges;
6005 bitlst_table = (int *) xmalloc (rgn_nr_edges * sizeof (int));
6007 compute_trg_info (bb);
6012 /* Allocate the ready list. */
6013 ready.veclen = rgn_n_insns + 1 + ISSUE_RATE;
6014 ready.first = ready.veclen - 1;
6015 ready.vec = (rtx *) xmalloc (ready.veclen * sizeof (rtx));
6018 /* Print debugging information. */
6019 if (sched_verbose >= 5)
6020 debug_dependencies ();
6022 /* Initialize ready list with all 'ready' insns in target block.
6023 Count number of insns in the target block being scheduled. */
6024 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6028 if (! INSN_P (insn))
6030 next = NEXT_INSN (insn);
6032 if (INSN_DEP_COUNT (insn) == 0
6033 && (SCHED_GROUP_P (next) == 0 || ! INSN_P (next)))
6034 ready_add (&ready, insn);
6035 if (!(SCHED_GROUP_P (insn)))
6039 /* Add to ready list all 'ready' insns in valid source blocks.
6040 For speculative insns, check-live, exception-free, and
6042 for (bb_src = bb + 1; bb_src < current_nr_blocks; bb_src++)
6043 if (IS_VALID (bb_src))
6049 get_bb_head_tail (bb_src, &head, &tail);
6050 src_next_tail = NEXT_INSN (tail);
6053 if (head == tail && (! INSN_P (head)))
6056 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
6058 if (! INSN_P (insn))
6061 if (!CANT_MOVE (insn)
6062 && (!IS_SPECULATIVE_INSN (insn)
6063 || (insn_issue_delay (insn) <= 3
6064 && check_live (insn, bb_src)
6065 && is_exception_free (insn, bb_src, target_bb))))
6069 /* Note that we havn't squirrled away the notes for
6070 blocks other than the current. So if this is a
6071 speculative insn, NEXT might otherwise be a note. */
6072 next = next_nonnote_insn (insn);
6073 if (INSN_DEP_COUNT (insn) == 0
6075 || SCHED_GROUP_P (next) == 0
6076 || ! INSN_P (next)))
6077 ready_add (&ready, insn);
6082 #ifdef MD_SCHED_INIT
6083 MD_SCHED_INIT (dump, sched_verbose);
6086 /* No insns scheduled in this block yet. */
6087 last_scheduled_insn = 0;
6089 /* Q_SIZE is the total number of insns in the queue. */
6093 memset ((char *) insn_queue, 0, sizeof (insn_queue));
6095 /* Start just before the beginning of time. */
6098 /* We start inserting insns after PREV_HEAD. */
6101 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6102 new_needs = (NEXT_INSN (prev_head) == BLOCK_HEAD (b)
6103 ? NEED_HEAD : NEED_NOTHING);
6104 if (PREV_INSN (next_tail) == BLOCK_END (b))
6105 new_needs |= NEED_TAIL;
6107 /* Loop until all the insns in BB are scheduled. */
6108 while (sched_target_n_insns < target_n_insns)
6112 /* Add to the ready list all pending insns that can be issued now.
6113 If there are no ready insns, increment clock until one
6114 is ready and add all pending insns at that point to the ready
6116 queue_to_ready (&ready);
6118 if (ready.n_ready == 0)
6121 if (sched_verbose >= 2)
6123 fprintf (dump, ";;\t\tReady list after queue_to_ready: ");
6124 debug_ready_list (&ready);
6127 /* Sort the ready list based on priority. */
6128 ready_sort (&ready);
6130 /* Allow the target to reorder the list, typically for
6131 better instruction bundling. */
6132 #ifdef MD_SCHED_REORDER
6133 MD_SCHED_REORDER (dump, sched_verbose, ready_lastpos (&ready),
6134 ready.n_ready, clock_var, can_issue_more);
6136 can_issue_more = issue_rate;
6141 fprintf (dump, "\n;;\tReady list (t =%3d): ", clock_var);
6142 debug_ready_list (&ready);
6145 /* Issue insns from ready list. */
6146 while (ready.n_ready != 0 && can_issue_more)
6148 /* Select and remove the insn from the ready list. */
6149 rtx insn = ready_remove_first (&ready);
6150 int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
6154 queue_insn (insn, cost);
6158 /* An interblock motion? */
6159 if (INSN_BB (insn) != target_bb)
6164 if (IS_SPECULATIVE_INSN (insn))
6166 if (!check_live (insn, INSN_BB (insn)))
6168 update_live (insn, INSN_BB (insn));
6170 /* For speculative load, mark insns fed by it. */
6171 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
6172 set_spec_fed (insn);
6178 /* Find the beginning of the scheduling group. */
6179 /* ??? Ought to update basic block here, but later bits of
6180 schedule_block assumes the original insn block is
6184 while (SCHED_GROUP_P (temp))
6185 temp = PREV_INSN (temp);
6187 /* Update source block boundaries. */
6188 b1 = BLOCK_FOR_INSN (temp);
6189 if (temp == b1->head && insn == b1->end)
6191 /* We moved all the insns in the basic block.
6192 Emit a note after the last insn and update the
6193 begin/end boundaries to point to the note. */
6194 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
6198 else if (insn == b1->end)
6200 /* We took insns from the end of the basic block,
6201 so update the end of block boundary so that it
6202 points to the first insn we did not move. */
6203 b1->end = PREV_INSN (temp);
6205 else if (temp == b1->head)
6207 /* We took insns from the start of the basic block,
6208 so update the start of block boundary so that
6209 it points to the first insn we did not move. */
6210 b1->head = NEXT_INSN (insn);
6215 /* In block motion. */
6216 sched_target_n_insns++;
6219 last_scheduled_insn = insn;
6220 last = move_insn (insn, last);
6223 #ifdef MD_SCHED_VARIABLE_ISSUE
6224 MD_SCHED_VARIABLE_ISSUE (dump, sched_verbose, insn,
6230 schedule_insn (insn, &ready, clock_var);
6232 /* Close this block after scheduling its jump. */
6233 if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
6239 visualize_scheduled_insns (b, clock_var);
6245 fprintf (dump, ";;\tReady list (final): ");
6246 debug_ready_list (&ready);
6247 print_block_visualization (b, "");
6250 /* Sanity check -- queue must be empty now. Meaningless if region has
6252 if (current_nr_blocks > 1)
6253 if (!flag_schedule_interblock && q_size != 0)
6256 /* Update head/tail boundaries. */
6257 head = NEXT_INSN (prev_head);
6260 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6261 previously found among the insns. Insert them at the beginning
6265 rtx note_head = note_list;
6267 while (PREV_INSN (note_head))
6269 note_head = PREV_INSN (note_head);
6272 PREV_INSN (note_head) = PREV_INSN (head);
6273 NEXT_INSN (PREV_INSN (head)) = note_head;
6274 PREV_INSN (head) = note_list;
6275 NEXT_INSN (note_list) = head;
6279 /* Update target block boundaries. */
6280 if (new_needs & NEED_HEAD)
6281 BLOCK_HEAD (b) = head;
6283 if (new_needs & NEED_TAIL)
6284 BLOCK_END (b) = tail;
6289 fprintf (dump, ";; total time = %d\n;; new basic block head = %d\n",
6290 clock_var, INSN_UID (BLOCK_HEAD (b)));
6291 fprintf (dump, ";; new basic block end = %d\n\n",
6292 INSN_UID (BLOCK_END (b)));
6296 if (current_nr_blocks > 1)
6298 free (candidate_table);
6300 free (bitlst_table);
6304 return (sched_n_insns);
6307 /* Print the bit-set of registers, S, callable from debugger. */
6310 debug_reg_vector (s)
6315 EXECUTE_IF_SET_IN_REG_SET (s, 0, regno,
6317 fprintf (dump, " %d", regno);
6320 fprintf (dump, "\n");
6323 /* Use the backward dependences from LOG_LINKS to build
6324 forward dependences in INSN_DEPEND. */
6327 compute_block_forward_dependences (bb)
6333 enum reg_note dep_type;
6335 get_bb_head_tail (bb, &head, &tail);
6336 next_tail = NEXT_INSN (tail);
6337 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6339 if (! INSN_P (insn))
6342 insn = group_leader (insn);
6344 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
6346 rtx x = group_leader (XEXP (link, 0));
6349 if (x != XEXP (link, 0))
6352 #ifdef ENABLE_CHECKING
6353 /* If add_dependence is working properly there should never
6354 be notes, deleted insns or duplicates in the backward
6355 links. Thus we need not check for them here.
6357 However, if we have enabled checking we might as well go
6358 ahead and verify that add_dependence worked properly. */
6359 if (GET_CODE (x) == NOTE
6360 || INSN_DELETED_P (x)
6361 || (forward_dependency_cache != NULL
6362 && TEST_BIT (forward_dependency_cache[INSN_LUID (x)],
6364 || (forward_dependency_cache == NULL
6365 && find_insn_list (insn, INSN_DEPEND (x))))
6367 if (forward_dependency_cache != NULL)
6368 SET_BIT (forward_dependency_cache[INSN_LUID (x)],
6372 new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
6374 dep_type = REG_NOTE_KIND (link);
6375 PUT_REG_NOTE_KIND (new_link, dep_type);
6377 INSN_DEPEND (x) = new_link;
6378 INSN_DEP_COUNT (insn) += 1;
6383 /* Initialize variables for region data dependence analysis.
6384 n_bbs is the number of region blocks. */
6390 int maxreg = max_reg_num ();
6391 deps->reg_last_uses = (rtx *) xcalloc (maxreg, sizeof (rtx));
6392 deps->reg_last_sets = (rtx *) xcalloc (maxreg, sizeof (rtx));
6393 deps->reg_last_clobbers = (rtx *) xcalloc (maxreg, sizeof (rtx));
6395 deps->pending_read_insns = 0;
6396 deps->pending_read_mems = 0;
6397 deps->pending_write_insns = 0;
6398 deps->pending_write_mems = 0;
6399 deps->pending_lists_length = 0;
6400 deps->last_pending_memory_flush = 0;
6401 deps->last_function_call = 0;
6402 deps->in_post_call_group_p = 0;
6404 deps->sched_before_next_call
6405 = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
6406 NULL_RTX, 0, NULL_RTX, NULL_RTX);
6407 LOG_LINKS (deps->sched_before_next_call) = 0;
6410 /* Add dependences so that branches are scheduled to run last in their
6414 add_branch_dependences (head, tail)
6419 /* For all branches, calls, uses, clobbers, and cc0 setters, force them
6420 to remain in order at the end of the block by adding dependencies and
6421 giving the last a high priority. There may be notes present, and
6422 prev_head may also be a note.
6424 Branches must obviously remain at the end. Calls should remain at the
6425 end since moving them results in worse register allocation. Uses remain
6426 at the end to ensure proper register allocation. cc0 setters remaim
6427 at the end because they can't be moved away from their cc0 user. */
6430 while (GET_CODE (insn) == CALL_INSN
6431 || GET_CODE (insn) == JUMP_INSN
6432 || (GET_CODE (insn) == INSN
6433 && (GET_CODE (PATTERN (insn)) == USE
6434 || GET_CODE (PATTERN (insn)) == CLOBBER
6436 || sets_cc0_p (PATTERN (insn))
6439 || GET_CODE (insn) == NOTE)
6441 if (GET_CODE (insn) != NOTE)
6444 && !find_insn_list (insn, LOG_LINKS (last)))
6446 add_dependence (last, insn, REG_DEP_ANTI);
6447 INSN_REF_COUNT (insn)++;
6450 CANT_MOVE (insn) = 1;
6453 /* Skip over insns that are part of a group.
6454 Make each insn explicitly depend on the previous insn.
6455 This ensures that only the group header will ever enter
6456 the ready queue (and, when scheduled, will automatically
6457 schedule the SCHED_GROUP_P block). */
6458 while (SCHED_GROUP_P (insn))
6460 rtx temp = prev_nonnote_insn (insn);
6461 add_dependence (insn, temp, REG_DEP_ANTI);
6466 /* Don't overrun the bounds of the basic block. */
6470 insn = PREV_INSN (insn);
6473 /* Make sure these insns are scheduled last in their block. */
6476 while (insn != head)
6478 insn = prev_nonnote_insn (insn);
6480 if (INSN_REF_COUNT (insn) != 0)
6483 add_dependence (last, insn, REG_DEP_ANTI);
6484 INSN_REF_COUNT (insn) = 1;
6486 /* Skip over insns that are part of a group. */
6487 while (SCHED_GROUP_P (insn))
6488 insn = prev_nonnote_insn (insn);
6492 /* After computing the dependencies for block BB, propagate the dependencies
6493 found in TMP_DEPS to the successors of the block. MAX_REG is the number
6496 propagate_deps (bb, tmp_deps, max_reg)
6498 struct deps *tmp_deps;
6501 int b = BB_TO_BLOCK (bb);
6504 rtx link_insn, link_mem;
6507 /* These lists should point to the right place, for correct
6509 bb_deps[bb].pending_read_insns = tmp_deps->pending_read_insns;
6510 bb_deps[bb].pending_read_mems = tmp_deps->pending_read_mems;
6511 bb_deps[bb].pending_write_insns = tmp_deps->pending_write_insns;
6512 bb_deps[bb].pending_write_mems = tmp_deps->pending_write_mems;
6514 /* bb's structures are inherited by its successors. */
6515 first_edge = e = OUT_EDGES (b);
6522 int b_succ = TO_BLOCK (e);
6523 int bb_succ = BLOCK_TO_BB (b_succ);
6524 struct deps *succ_deps = bb_deps + bb_succ;
6526 /* Only bbs "below" bb, in the same region, are interesting. */
6527 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
6534 for (reg = 0; reg < max_reg; reg++)
6536 /* reg-last-uses lists are inherited by bb_succ. */
6537 for (u = tmp_deps->reg_last_uses[reg]; u; u = XEXP (u, 1))
6539 if (find_insn_list (XEXP (u, 0),
6540 succ_deps->reg_last_uses[reg]))
6543 succ_deps->reg_last_uses[reg]
6544 = alloc_INSN_LIST (XEXP (u, 0),
6545 succ_deps->reg_last_uses[reg]);
6548 /* reg-last-defs lists are inherited by bb_succ. */
6549 for (u = tmp_deps->reg_last_sets[reg]; u; u = XEXP (u, 1))
6551 if (find_insn_list (XEXP (u, 0),
6552 succ_deps->reg_last_sets[reg]))
6555 succ_deps->reg_last_sets[reg]
6556 = alloc_INSN_LIST (XEXP (u, 0),
6557 succ_deps->reg_last_sets[reg]);
6560 for (u = tmp_deps->reg_last_clobbers[reg]; u; u = XEXP (u, 1))
6562 if (find_insn_list (XEXP (u, 0),
6563 succ_deps->reg_last_clobbers[reg]))
6566 succ_deps->reg_last_clobbers[reg]
6567 = alloc_INSN_LIST (XEXP (u, 0),
6568 succ_deps->reg_last_clobbers[reg]);
6572 /* Mem read/write lists are inherited by bb_succ. */
6573 link_insn = tmp_deps->pending_read_insns;
6574 link_mem = tmp_deps->pending_read_mems;
6577 if (!(find_insn_mem_list (XEXP (link_insn, 0),
6579 succ_deps->pending_read_insns,
6580 succ_deps->pending_read_mems)))
6581 add_insn_mem_dependence (succ_deps, &succ_deps->pending_read_insns,
6582 &succ_deps->pending_read_mems,
6583 XEXP (link_insn, 0), XEXP (link_mem, 0));
6584 link_insn = XEXP (link_insn, 1);
6585 link_mem = XEXP (link_mem, 1);
6588 link_insn = tmp_deps->pending_write_insns;
6589 link_mem = tmp_deps->pending_write_mems;
6592 if (!(find_insn_mem_list (XEXP (link_insn, 0),
6594 succ_deps->pending_write_insns,
6595 succ_deps->pending_write_mems)))
6596 add_insn_mem_dependence (succ_deps,
6597 &succ_deps->pending_write_insns,
6598 &succ_deps->pending_write_mems,
6599 XEXP (link_insn, 0), XEXP (link_mem, 0));
6601 link_insn = XEXP (link_insn, 1);
6602 link_mem = XEXP (link_mem, 1);
6605 /* last_function_call is inherited by bb_succ. */
6606 for (u = tmp_deps->last_function_call; u; u = XEXP (u, 1))
6608 if (find_insn_list (XEXP (u, 0),
6609 succ_deps->last_function_call))
6612 succ_deps->last_function_call
6613 = alloc_INSN_LIST (XEXP (u, 0),
6614 succ_deps->last_function_call);
6617 /* last_pending_memory_flush is inherited by bb_succ. */
6618 for (u = tmp_deps->last_pending_memory_flush; u; u = XEXP (u, 1))
6620 if (find_insn_list (XEXP (u, 0),
6621 succ_deps->last_pending_memory_flush))
6624 succ_deps->last_pending_memory_flush
6625 = alloc_INSN_LIST (XEXP (u, 0),
6626 succ_deps->last_pending_memory_flush);
6629 /* sched_before_next_call is inherited by bb_succ. */
6630 x = LOG_LINKS (tmp_deps->sched_before_next_call);
6631 for (; x; x = XEXP (x, 1))
6632 add_dependence (succ_deps->sched_before_next_call,
6633 XEXP (x, 0), REG_DEP_ANTI);
6637 while (e != first_edge);
6640 /* Compute backward dependences inside bb. In a multiple blocks region:
6641 (1) a bb is analyzed after its predecessors, and (2) the lists in
6642 effect at the end of bb (after analyzing for bb) are inherited by
6645 Specifically for reg-reg data dependences, the block insns are
6646 scanned by sched_analyze () top-to-bottom. Two lists are
6647 maintained by sched_analyze (): reg_last_sets[] for register DEFs,
6648 and reg_last_uses[] for register USEs.
6650 When analysis is completed for bb, we update for its successors:
6651 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
6652 ; - USES[succ] = Union (USES [succ], DEFS [bb])
6654 The mechanism for computing mem-mem data dependence is very
6655 similar, and the result is interblock dependences in the region. */
6658 compute_block_backward_dependences (bb)
6663 int max_reg = max_reg_num ();
6664 struct deps tmp_deps;
6666 tmp_deps = bb_deps[bb];
6668 /* Do the analysis for this block. */
6669 get_bb_head_tail (bb, &head, &tail);
6670 sched_analyze (&tmp_deps, head, tail);
6671 add_branch_dependences (head, tail);
6673 if (current_nr_blocks > 1)
6674 propagate_deps (bb, &tmp_deps, max_reg);
6676 /* Free up the INSN_LISTs.
6678 Note this loop is executed max_reg * nr_regions times. It's first
6679 implementation accounted for over 90% of the calls to free_INSN_LIST_list.
6680 The list was empty for the vast majority of those calls. On the PA, not
6681 calling free_INSN_LIST_list in those cases improves -O2 compile times by
6683 for (i = 0; i < max_reg; ++i)
6685 if (tmp_deps.reg_last_clobbers[i])
6686 free_INSN_LIST_list (&tmp_deps.reg_last_clobbers[i]);
6687 if (tmp_deps.reg_last_sets[i])
6688 free_INSN_LIST_list (&tmp_deps.reg_last_sets[i]);
6689 if (tmp_deps.reg_last_uses[i])
6690 free_INSN_LIST_list (&tmp_deps.reg_last_uses[i]);
6693 /* Assert that we won't need bb_reg_last_* for this block anymore. */
6694 free (bb_deps[bb].reg_last_uses);
6695 free (bb_deps[bb].reg_last_sets);
6696 free (bb_deps[bb].reg_last_clobbers);
6697 bb_deps[bb].reg_last_uses = 0;
6698 bb_deps[bb].reg_last_sets = 0;
6699 bb_deps[bb].reg_last_clobbers = 0;
6702 /* Print dependences for debugging, callable from debugger. */
6705 debug_dependencies ()
6709 fprintf (dump, ";; --------------- forward dependences: ------------ \n");
6710 for (bb = 0; bb < current_nr_blocks; bb++)
6718 get_bb_head_tail (bb, &head, &tail);
6719 next_tail = NEXT_INSN (tail);
6720 fprintf (dump, "\n;; --- Region Dependences --- b %d bb %d \n",
6721 BB_TO_BLOCK (bb), bb);
6723 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
6724 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
6725 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
6726 "----", "----", "--", "---", "----", "----", "--------", "-----");
6727 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6732 if (! INSN_P (insn))
6735 fprintf (dump, ";; %6d ", INSN_UID (insn));
6736 if (GET_CODE (insn) == NOTE)
6738 n = NOTE_LINE_NUMBER (insn);
6740 fprintf (dump, "%s\n", GET_NOTE_INSN_NAME (n));
6742 fprintf (dump, "line %d, file %s\n", n,
6743 NOTE_SOURCE_FILE (insn));
6746 fprintf (dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
6750 unit = insn_unit (insn);
6752 || function_units[unit].blockage_range_function == 0) ? 0 :
6753 function_units[unit].blockage_range_function (insn);
6755 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
6756 (SCHED_GROUP_P (insn) ? "+" : " "),
6760 INSN_DEP_COUNT (insn),
6761 INSN_PRIORITY (insn),
6762 insn_cost (insn, 0, 0),
6763 (int) MIN_BLOCKAGE_COST (range),
6764 (int) MAX_BLOCKAGE_COST (range));
6765 insn_print_units (insn);
6766 fprintf (dump, "\t: ");
6767 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
6768 fprintf (dump, "%d ", INSN_UID (XEXP (link, 0)));
6769 fprintf (dump, "\n");
6773 fprintf (dump, "\n");
6776 /* Set_priorities: compute priority of each insn in the block. */
6789 get_bb_head_tail (bb, &head, &tail);
6790 prev_head = PREV_INSN (head);
6792 if (head == tail && (! INSN_P (head)))
6796 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
6799 if (GET_CODE (insn) == NOTE)
6802 if (!(SCHED_GROUP_P (insn)))
6804 (void) priority (insn);
6810 /* Schedule a region. A region is either an inner loop, a loop-free
6811 subroutine, or a single basic block. Each bb in the region is
6812 scheduled after its flow predecessors. */
6815 schedule_region (rgn)
6819 int rgn_n_insns = 0;
6820 int sched_rgn_n_insns = 0;
6821 regset_head reg_pending_sets_head;
6822 regset_head reg_pending_clobbers_head;
6824 /* Set variables for the current region. */
6825 current_nr_blocks = RGN_NR_BLOCKS (rgn);
6826 current_blocks = RGN_BLOCKS (rgn);
6828 reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head);
6829 reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head);
6830 reg_pending_sets_all = 0;
6832 /* Initializations for region data dependence analyisis. */
6833 bb_deps = (struct deps *) xmalloc (sizeof (struct deps) * current_nr_blocks);
6834 for (bb = 0; bb < current_nr_blocks; bb++)
6835 init_deps (bb_deps + bb);
6837 /* Compute LOG_LINKS. */
6838 for (bb = 0; bb < current_nr_blocks; bb++)
6839 compute_block_backward_dependences (bb);
6841 /* Compute INSN_DEPEND. */
6842 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
6843 compute_block_forward_dependences (bb);
6845 /* Delete line notes and set priorities. */
6846 for (bb = 0; bb < current_nr_blocks; bb++)
6848 if (write_symbols != NO_DEBUG)
6850 save_line_notes (bb);
6854 rgn_n_insns += set_priorities (bb);
6857 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
6858 if (current_nr_blocks > 1)
6862 prob = (float *) xmalloc ((current_nr_blocks) * sizeof (float));
6864 bbset_size = current_nr_blocks / HOST_BITS_PER_WIDE_INT + 1;
6865 dom = (bbset *) xmalloc (current_nr_blocks * sizeof (bbset));
6866 for (i = 0; i < current_nr_blocks; i++)
6867 dom[i] = (bbset) xcalloc (bbset_size, sizeof (HOST_WIDE_INT));
6871 edge_to_bit = (int *) xmalloc (nr_edges * sizeof (int));
6872 for (i = 1; i < nr_edges; i++)
6873 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
6874 EDGE_TO_BIT (i) = rgn_nr_edges++;
6875 rgn_edges = (int *) xmalloc (rgn_nr_edges * sizeof (int));
6878 for (i = 1; i < nr_edges; i++)
6879 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
6880 rgn_edges[rgn_nr_edges++] = i;
6883 edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
6884 edgeset_bitsize = rgn_nr_edges;
6885 pot_split = (edgeset *) xmalloc (current_nr_blocks * sizeof (edgeset));
6887 = (edgeset *) xmalloc (current_nr_blocks * sizeof (edgeset));
6888 for (i = 0; i < current_nr_blocks; i++)
6891 (edgeset) xcalloc (edgeset_size, sizeof (HOST_WIDE_INT));
6893 (edgeset) xcalloc (edgeset_size, sizeof (HOST_WIDE_INT));
6896 /* Compute probabilities, dominators, split_edges. */
6897 for (bb = 0; bb < current_nr_blocks; bb++)
6898 compute_dom_prob_ps (bb);
6901 /* Now we can schedule all blocks. */
6902 for (bb = 0; bb < current_nr_blocks; bb++)
6903 sched_rgn_n_insns += schedule_block (bb, rgn_n_insns);
6905 /* Sanity check: verify that all region insns were scheduled. */
6906 if (sched_rgn_n_insns != rgn_n_insns)
6909 /* Restore line notes. */
6910 if (write_symbols != NO_DEBUG)
6912 for (bb = 0; bb < current_nr_blocks; bb++)
6913 restore_line_notes (bb);
6916 /* Done with this region. */
6917 free_pending_lists ();
6919 FREE_REG_SET (reg_pending_sets);
6920 FREE_REG_SET (reg_pending_clobbers);
6924 if (current_nr_blocks > 1)
6929 for (i = 0; i < current_nr_blocks; ++i)
6932 free (pot_split[i]);
6933 free (ancestor_edges[i]);
6939 free (ancestor_edges);
6943 /* The one entry point in this file. DUMP_FILE is the dump file for
6947 schedule_insns (dump_file)
6950 int *deaths_in_region;
6951 sbitmap blocks, large_region_blocks;
6957 int any_large_regions;
6959 /* Disable speculative loads in their presence if cc0 defined. */
6961 flag_schedule_speculative_load = 0;
6964 /* Taking care of this degenerate case makes the rest of
6965 this code simpler. */
6966 if (n_basic_blocks == 0)
6969 /* Set dump and sched_verbose for the desired debugging output. If no
6970 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
6971 For -fsched-verbose=N, N>=10, print everything to stderr. */
6972 sched_verbose = sched_verbose_param;
6973 if (sched_verbose_param == 0 && dump_file)
6975 dump = ((sched_verbose_param >= 10 || !dump_file) ? stderr : dump_file);
6980 /* Initialize issue_rate. */
6981 issue_rate = ISSUE_RATE;
6983 split_all_insns (1);
6985 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
6986 pseudos which do not cross calls. */
6987 max_uid = get_max_uid () + 1;
6989 h_i_d = (struct haifa_insn_data *) xcalloc (max_uid, sizeof (*h_i_d));
6993 for (b = 0; b < n_basic_blocks; b++)
6994 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
6996 INSN_LUID (insn) = luid;
6998 /* Increment the next luid, unless this is a note. We don't
6999 really need separate IDs for notes and we don't want to
7000 schedule differently depending on whether or not there are
7001 line-number notes, i.e., depending on whether or not we're
7002 generating debugging information. */
7003 if (GET_CODE (insn) != NOTE)
7006 if (insn == BLOCK_END (b))
7010 /* ?!? We could save some memory by computing a per-region luid mapping
7011 which could reduce both the number of vectors in the cache and the size
7012 of each vector. Instead we just avoid the cache entirely unless the
7013 average number of instructions in a basic block is very high. See
7014 the comment before the declaration of true_dependency_cache for
7015 what we consider "very high". */
7016 if (luid / n_basic_blocks > 100 * 5)
7018 true_dependency_cache = sbitmap_vector_alloc (luid, luid);
7019 sbitmap_vector_zero (true_dependency_cache, luid);
7020 anti_dependency_cache = sbitmap_vector_alloc (luid, luid);
7021 sbitmap_vector_zero (anti_dependency_cache, luid);
7022 output_dependency_cache = sbitmap_vector_alloc (luid, luid);
7023 sbitmap_vector_zero (output_dependency_cache, luid);
7024 #ifdef ENABLE_CHECKING
7025 forward_dependency_cache = sbitmap_vector_alloc (luid, luid);
7026 sbitmap_vector_zero (forward_dependency_cache, luid);
7031 rgn_table = (region *) xmalloc ((n_basic_blocks) * sizeof (region));
7032 rgn_bb_table = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
7033 block_to_bb = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
7034 containing_rgn = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
7036 blocks = sbitmap_alloc (n_basic_blocks);
7037 large_region_blocks = sbitmap_alloc (n_basic_blocks);
7039 compute_bb_for_insn (max_uid);
7041 /* Compute regions for scheduling. */
7042 if (reload_completed
7043 || n_basic_blocks == 1
7044 || !flag_schedule_interblock)
7046 find_single_block_region ();
7050 /* Verify that a 'good' control flow graph can be built. */
7051 if (is_cfg_nonregular ())
7053 find_single_block_region ();
7058 struct edge_list *edge_list;
7060 dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
7062 /* The scheduler runs after flow; therefore, we can't blindly call
7063 back into find_basic_blocks since doing so could invalidate the
7064 info in global_live_at_start.
7066 Consider a block consisting entirely of dead stores; after life
7067 analysis it would be a block of NOTE_INSN_DELETED notes. If
7068 we call find_basic_blocks again, then the block would be removed
7069 entirely and invalidate our the register live information.
7071 We could (should?) recompute register live information. Doing
7072 so may even be beneficial. */
7073 edge_list = create_edge_list ();
7075 /* Compute the dominators and post dominators. */
7076 calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
7078 /* build_control_flow will return nonzero if it detects unreachable
7079 blocks or any other irregularity with the cfg which prevents
7080 cross block scheduling. */
7081 if (build_control_flow (edge_list) != 0)
7082 find_single_block_region ();
7084 find_rgns (edge_list, dom);
7086 if (sched_verbose >= 3)
7089 /* We are done with flow's edge list. */
7090 free_edge_list (edge_list);
7092 /* For now. This will move as more and more of haifa is converted
7093 to using the cfg code in flow.c. */
7098 deaths_in_region = (int *) xmalloc (sizeof (int) * nr_regions);
7100 init_alias_analysis ();
7102 if (write_symbols != NO_DEBUG)
7106 line_note_head = (rtx *) xcalloc (n_basic_blocks, sizeof (rtx));
7108 /* Save-line-note-head:
7109 Determine the line-number at the start of each basic block.
7110 This must be computed and saved now, because after a basic block's
7111 predecessor has been scheduled, it is impossible to accurately
7112 determine the correct line number for the first insn of the block. */
7114 for (b = 0; b < n_basic_blocks; b++)
7115 for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line))
7116 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
7118 line_note_head[b] = line;
7123 /* Find units used in this fuction, for visualization. */
7125 init_target_units ();
7127 /* ??? Add a NOTE after the last insn of the last basic block. It is not
7128 known why this is done. */
7130 insn = BLOCK_END (n_basic_blocks - 1);
7131 if (NEXT_INSN (insn) == 0
7132 || (GET_CODE (insn) != NOTE
7133 && GET_CODE (insn) != CODE_LABEL
7134 /* Don't emit a NOTE if it would end up between an unconditional
7135 jump and a BARRIER. */
7136 && !(GET_CODE (insn) == JUMP_INSN
7137 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
7138 emit_note_after (NOTE_INSN_DELETED, BLOCK_END (n_basic_blocks - 1));
7140 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
7141 removing death notes. */
7142 for (b = n_basic_blocks - 1; b >= 0; b--)
7143 find_insn_reg_weight (b);
7145 /* Remove all death notes from the subroutine. */
7146 for (rgn = 0; rgn < nr_regions; rgn++)
7148 sbitmap_zero (blocks);
7149 for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
7150 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]);
7152 deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1);
7155 /* Schedule every region in the subroutine. */
7156 for (rgn = 0; rgn < nr_regions; rgn++)
7157 schedule_region (rgn);
7159 /* Update life analysis for the subroutine. Do single block regions
7160 first so that we can verify that live_at_start didn't change. Then
7161 do all other blocks. */
7162 /* ??? There is an outside possibility that update_life_info, or more
7163 to the point propagate_block, could get called with non-zero flags
7164 more than once for one basic block. This would be kinda bad if it
7165 were to happen, since REG_INFO would be accumulated twice for the
7166 block, and we'd have twice the REG_DEAD notes.
7168 I'm fairly certain that this _shouldn't_ happen, since I don't think
7169 that live_at_start should change at region heads. Not sure what the
7170 best way to test for this kind of thing... */
7172 allocate_reg_life_data ();
7173 compute_bb_for_insn (max_uid);
7175 any_large_regions = 0;
7176 sbitmap_ones (large_region_blocks);
7178 for (rgn = 0; rgn < nr_regions; rgn++)
7179 if (RGN_NR_BLOCKS (rgn) > 1)
7180 any_large_regions = 1;
7183 sbitmap_zero (blocks);
7184 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
7185 RESET_BIT (large_region_blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
7187 /* Don't update reg info after reload, since that affects
7188 regs_ever_live, which should not change after reload. */
7189 update_life_info (blocks, UPDATE_LIFE_LOCAL,
7190 (reload_completed ? PROP_DEATH_NOTES
7191 : PROP_DEATH_NOTES | PROP_REG_INFO));
7193 #ifndef HAVE_conditional_execution
7194 /* ??? REG_DEAD notes only exist for unconditional deaths. We need
7195 a count of the conditional plus unconditional deaths for this to
7197 /* In the single block case, the count of registers that died should
7198 not have changed during the schedule. */
7199 if (count_or_remove_death_notes (blocks, 0) != deaths_in_region[rgn])
7204 if (any_large_regions)
7206 update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL,
7207 PROP_DEATH_NOTES | PROP_REG_INFO);
7210 /* Reposition the prologue and epilogue notes in case we moved the
7211 prologue/epilogue insns. */
7212 if (reload_completed)
7213 reposition_prologue_and_epilogue_notes (get_insns ());
7215 /* Delete redundant line notes. */
7216 if (write_symbols != NO_DEBUG)
7217 rm_redundant_line_notes ();
7221 if (reload_completed == 0 && flag_schedule_interblock)
7224 "\n;; Procedure interblock/speculative motions == %d/%d \n",
7232 fprintf (dump, "\n\n");
7236 end_alias_analysis ();
7238 if (true_dependency_cache)
7240 free (true_dependency_cache);
7241 true_dependency_cache = NULL;
7242 free (anti_dependency_cache);
7243 anti_dependency_cache = NULL;
7244 free (output_dependency_cache);
7245 output_dependency_cache = NULL;
7246 #ifdef ENABLE_CHECKING
7247 free (forward_dependency_cache);
7248 forward_dependency_cache = NULL;
7252 free (rgn_bb_table);
7254 free (containing_rgn);
7258 if (write_symbols != NO_DEBUG)
7259 free (line_note_head);
7278 sbitmap_free (blocks);
7279 sbitmap_free (large_region_blocks);
7281 free (deaths_in_region);
7284 #endif /* INSN_SCHEDULING */