1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 93-98, 1999, 2000 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to the Free
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
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 "basic-block.h"
165 #include "function.h"
166 #include "hard-reg-set.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;
217 /* Debugging file. All printouts are sent to dump, which is always set,
218 either to stderr, or to the dump listing file (-dRS). */
219 static FILE *dump = 0;
221 /* fix_sched_param() is called from toplev.c upon detection
222 of the -fsched-***-N options. */
225 fix_sched_param (param, val)
226 const char *param, *val;
228 if (!strcmp (param, "verbose"))
229 sched_verbose_param = atoi (val);
231 warning ("fix_sched_param: unknown param: %s", param);
234 /* Describe state of dependencies used during sched_analyze phase. */
237 /* The *_insns and *_mems are paired lists. Each pending memory operation
238 will have a pointer to the MEM rtx on one list and a pointer to the
239 containing insn on the other list in the same place in the list. */
241 /* We can't use add_dependence like the old code did, because a single insn
242 may have multiple memory accesses, and hence needs to be on the list
243 once for each memory access. Add_dependence won't let you add an insn
244 to a list more than once. */
246 /* An INSN_LIST containing all insns with pending read operations. */
247 rtx pending_read_insns;
249 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
250 rtx pending_read_mems;
252 /* An INSN_LIST containing all insns with pending write operations. */
253 rtx pending_write_insns;
255 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
256 rtx pending_write_mems;
258 /* Indicates the combined length of the two pending lists. We must prevent
259 these lists from ever growing too large since the number of dependencies
260 produced is at least O(N*N), and execution time is at least O(4*N*N), as
261 a function of the length of these pending lists. */
262 int pending_lists_length;
264 /* The last insn upon which all memory references must depend.
265 This is an insn which flushed the pending lists, creating a dependency
266 between it and all previously pending memory references. This creates
267 a barrier (or a checkpoint) which no memory reference is allowed to cross.
269 This includes all non constant CALL_INSNs. When we do interprocedural
270 alias analysis, this restriction can be relaxed.
271 This may also be an INSN that writes memory if the pending lists grow
273 rtx last_pending_memory_flush;
275 /* The last function call we have seen. All hard regs, and, of course,
276 the last function call, must depend on this. */
277 rtx last_function_call;
279 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
280 that does not already cross a call. We create dependencies between each
281 of those insn and the next call insn, to ensure that they won't cross a call
282 after scheduling is done. */
283 rtx sched_before_next_call;
285 /* Element N is the next insn that sets (hard or pseudo) register
286 N within the current basic block; or zero, if there is no
287 such insn. Needed for new registers which may be introduced
288 by splitting insns. */
291 rtx *reg_last_clobbers;
294 static regset reg_pending_sets;
295 static regset reg_pending_clobbers;
296 static int reg_pending_sets_all;
298 /* To speed up the test for duplicate dependency links we keep a record
299 of true dependencies created by add_dependence when the average number
300 of instructions in a basic block is very large.
302 Studies have shown that there is typically around 5 instructions between
303 branches for typical C code. So we can make a guess that the average
304 basic block is approximately 5 instructions long; we will choose 100X
305 the average size as a very large basic block.
307 Each insn has an associated bitmap for its dependencies. Each bitmap
308 has enough entries to represent a dependency on any other insn in the
310 static sbitmap *true_dependency_cache;
312 /* Indexed by INSN_UID, the collection of all data associated with
313 a single instruction. */
315 struct haifa_insn_data
317 /* A list of insns which depend on the instruction. Unlike LOG_LINKS,
318 it represents forward dependancies. */
321 /* The line number note in effect for each insn. For line number
322 notes, this indicates whether the note may be reused. */
325 /* Logical uid gives the original ordering of the insns. */
328 /* A priority for each insn. */
331 /* The number of incoming edges in the forward dependency graph.
332 As scheduling proceds, counts are decreased. An insn moves to
333 the ready queue when its counter reaches zero. */
336 /* An encoding of the blockage range function. Both unit and range
338 unsigned int blockage;
340 /* Number of instructions referring to this insn. */
343 /* The minimum clock tick at which the insn becomes ready. This is
344 used to note timing constraints for the insns in the pending list. */
349 /* An encoding of the function units used. */
352 /* This weight is an estimation of the insn's contribution to
353 register pressure. */
356 /* Some insns (e.g. call) are not allowed to move across blocks. */
357 unsigned int cant_move : 1;
359 /* Set if there's DEF-USE dependance between some speculatively
360 moved load insn and this one. */
361 unsigned int fed_by_spec_load : 1;
362 unsigned int is_load_insn : 1;
365 static struct haifa_insn_data *h_i_d;
367 #define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend)
368 #define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid)
369 #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority)
370 #define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count)
371 #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost)
372 #define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units)
373 #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight)
375 #define INSN_BLOCKAGE(INSN) (h_i_d[INSN_UID (INSN)].blockage)
377 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
378 #define ENCODE_BLOCKAGE(U, R) \
379 (((U) << BLOCKAGE_BITS \
380 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
381 | MAX_BLOCKAGE_COST (R))
382 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
383 #define BLOCKAGE_RANGE(B) \
384 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
385 | ((B) & BLOCKAGE_MASK))
387 /* Encodings of the `<name>_unit_blockage_range' function. */
388 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
389 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
391 #define DONE_PRIORITY -1
392 #define MAX_PRIORITY 0x7fffffff
393 #define TAIL_PRIORITY 0x7ffffffe
394 #define LAUNCH_PRIORITY 0x7f000001
395 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
396 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
398 #define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count)
399 #define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note)
400 #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
401 #define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move)
402 #define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load)
403 #define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn)
405 /* Vector indexed by basic block number giving the starting line-number
406 for each basic block. */
407 static rtx *line_note_head;
409 /* List of important notes we must keep around. This is a pointer to the
410 last element in the list. */
411 static rtx note_list;
415 /* An instruction is ready to be scheduled when all insns preceding it
416 have already been scheduled. It is important to ensure that all
417 insns which use its result will not be executed until its result
418 has been computed. An insn is maintained in one of four structures:
420 (P) the "Pending" set of insns which cannot be scheduled until
421 their dependencies have been satisfied.
422 (Q) the "Queued" set of insns that can be scheduled when sufficient
424 (R) the "Ready" list of unscheduled, uncommitted insns.
425 (S) the "Scheduled" list of insns.
427 Initially, all insns are either "Pending" or "Ready" depending on
428 whether their dependencies are satisfied.
430 Insns move from the "Ready" list to the "Scheduled" list as they
431 are committed to the schedule. As this occurs, the insns in the
432 "Pending" list have their dependencies satisfied and move to either
433 the "Ready" list or the "Queued" set depending on whether
434 sufficient time has passed to make them ready. As time passes,
435 insns move from the "Queued" set to the "Ready" list. Insns may
436 move from the "Ready" list to the "Queued" set if they are blocked
437 due to a function unit conflict.
439 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
440 insns, i.e., those that are ready, queued, and pending.
441 The "Queued" set (Q) is implemented by the variable `insn_queue'.
442 The "Ready" list (R) is implemented by the variables `ready' and
444 The "Scheduled" list (S) is the new insn chain built by this pass.
446 The transition (R->S) is implemented in the scheduling loop in
447 `schedule_block' when the best insn to schedule is chosen.
448 The transition (R->Q) is implemented in `queue_insn' when an
449 insn is found to have a function unit conflict with the already
451 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
452 insns move from the ready list to the scheduled list.
453 The transition (Q->R) is implemented in 'queue_to_insn' as time
454 passes or stalls are introduced. */
456 /* Implement a circular buffer to delay instructions until sufficient
457 time has passed. INSN_QUEUE_SIZE is a power of two larger than
458 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
459 longest time an isnsn may be queued. */
460 static rtx insn_queue[INSN_QUEUE_SIZE];
461 static int q_ptr = 0;
462 static int q_size = 0;
463 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
464 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
466 /* Forward declarations. */
467 static void add_dependence PARAMS ((rtx, rtx, enum reg_note));
469 static void remove_dependence PARAMS ((rtx, rtx));
471 static rtx find_insn_list PARAMS ((rtx, rtx));
472 static int insn_unit PARAMS ((rtx));
473 static unsigned int blockage_range PARAMS ((int, rtx));
474 static void clear_units PARAMS ((void));
475 static int actual_hazard_this_instance PARAMS ((int, int, rtx, int, int));
476 static void schedule_unit PARAMS ((int, rtx, int));
477 static int actual_hazard PARAMS ((int, rtx, int, int));
478 static int potential_hazard PARAMS ((int, rtx, int));
479 static int insn_cost PARAMS ((rtx, rtx, rtx));
480 static int priority PARAMS ((rtx));
481 static void free_pending_lists PARAMS ((void));
482 static void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx,
484 static void flush_pending_lists PARAMS ((struct deps *, rtx, int));
485 static void sched_analyze_1 PARAMS ((struct deps *, rtx, rtx));
486 static void sched_analyze_2 PARAMS ((struct deps *, rtx, rtx));
487 static void sched_analyze_insn PARAMS ((struct deps *, rtx, rtx, rtx));
488 static void sched_analyze PARAMS ((struct deps *, rtx, rtx));
489 static int rank_for_schedule PARAMS ((const PTR, const PTR));
490 static void swap_sort PARAMS ((rtx *, int));
491 static void queue_insn PARAMS ((rtx, int));
492 static int schedule_insn PARAMS ((rtx, rtx *, int, int));
493 static void find_insn_reg_weight PARAMS ((int));
494 static int schedule_block PARAMS ((int, int));
495 static char *safe_concat PARAMS ((char *, char *, const char *));
496 static int insn_issue_delay PARAMS ((rtx));
497 static void adjust_priority PARAMS ((rtx));
499 /* Control flow graph edges are kept in circular lists. */
508 static haifa_edge *edge_table;
510 #define NEXT_IN(edge) (edge_table[edge].next_in)
511 #define NEXT_OUT(edge) (edge_table[edge].next_out)
512 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
513 #define TO_BLOCK(edge) (edge_table[edge].to_block)
515 /* Number of edges in the control flow graph. (In fact, larger than
516 that by 1, since edge 0 is unused.) */
519 /* Circular list of incoming/outgoing edges of a block. */
520 static int *in_edges;
521 static int *out_edges;
523 #define IN_EDGES(block) (in_edges[block])
524 #define OUT_EDGES(block) (out_edges[block])
528 static int is_cfg_nonregular PARAMS ((void));
529 static int build_control_flow PARAMS ((struct edge_list *));
530 static void new_edge PARAMS ((int, int));
533 /* A region is the main entity for interblock scheduling: insns
534 are allowed to move between blocks in the same region, along
535 control flow graph edges, in the 'up' direction. */
538 int rgn_nr_blocks; /* Number of blocks in region. */
539 int rgn_blocks; /* cblocks in the region (actually index in rgn_bb_table). */
543 /* Number of regions in the procedure. */
544 static int nr_regions;
546 /* Table of region descriptions. */
547 static region *rgn_table;
549 /* Array of lists of regions' blocks. */
550 static int *rgn_bb_table;
552 /* Topological order of blocks in the region (if b2 is reachable from
553 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
554 always referred to by either block or b, while its topological
555 order name (in the region) is refered to by bb. */
556 static int *block_to_bb;
558 /* The number of the region containing a block. */
559 static int *containing_rgn;
561 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
562 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
563 #define BLOCK_TO_BB(block) (block_to_bb[block])
564 #define CONTAINING_RGN(block) (containing_rgn[block])
566 void debug_regions PARAMS ((void));
567 static void find_single_block_region PARAMS ((void));
568 static void find_rgns PARAMS ((struct edge_list *, sbitmap *));
569 static int too_large PARAMS ((int, int *, int *));
571 extern void debug_live PARAMS ((int, int));
573 /* Blocks of the current region being scheduled. */
574 static int current_nr_blocks;
575 static int current_blocks;
577 /* The mapping from bb to block. */
578 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
581 /* Bit vectors and bitset operations are needed for computations on
582 the control flow graph. */
584 typedef unsigned HOST_WIDE_INT *bitset;
587 int *first_member; /* Pointer to the list start in bitlst_table. */
588 int nr_members; /* The number of members of the bit list. */
592 static int bitlst_table_last;
593 static int bitlst_table_size;
594 static int *bitlst_table;
596 static char bitset_member PARAMS ((bitset, int, int));
597 static void extract_bitlst PARAMS ((bitset, int, int, bitlst *));
599 /* Target info declarations.
601 The block currently being scheduled is referred to as the "target" block,
602 while other blocks in the region from which insns can be moved to the
603 target are called "source" blocks. The candidate structure holds info
604 about such sources: are they valid? Speculative? Etc. */
605 typedef bitlst bblst;
616 static candidate *candidate_table;
618 /* A speculative motion requires checking live information on the path
619 from 'source' to 'target'. The split blocks are those to be checked.
620 After a speculative motion, live information should be modified in
623 Lists of split and update blocks for each candidate of the current
624 target are in array bblst_table. */
625 static int *bblst_table, bblst_size, bblst_last;
627 #define IS_VALID(src) ( candidate_table[src].is_valid )
628 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
629 #define SRC_PROB(src) ( candidate_table[src].src_prob )
631 /* The bb being currently scheduled. */
632 static int target_bb;
635 typedef bitlst edgelst;
637 /* Target info functions. */
638 static void split_edges PARAMS ((int, int, edgelst *));
639 static void compute_trg_info PARAMS ((int));
640 void debug_candidate PARAMS ((int));
641 void debug_candidates PARAMS ((int));
644 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
645 typedef bitset bbset;
647 /* Number of words of the bbset. */
648 static int bbset_size;
650 /* Dominators array: dom[i] contains the bbset of dominators of
651 bb i in the region. */
654 /* bb 0 is the only region entry. */
655 #define IS_RGN_ENTRY(bb) (!bb)
657 /* Is bb_src dominated by bb_trg. */
658 #define IS_DOMINATED(bb_src, bb_trg) \
659 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
661 /* Probability: Prob[i] is a float in [0, 1] which is the probability
662 of bb i relative to the region entry. */
665 /* The probability of bb_src, relative to bb_trg. Note, that while the
666 'prob[bb]' is a float in [0, 1], this macro returns an integer
668 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
671 /* Bit-set of edges, where bit i stands for edge i. */
672 typedef bitset edgeset;
674 /* Number of edges in the region. */
675 static int rgn_nr_edges;
677 /* Array of size rgn_nr_edges. */
678 static int *rgn_edges;
680 /* Number of words in an edgeset. */
681 static int edgeset_size;
683 /* Number of bits in an edgeset. */
684 static int edgeset_bitsize;
686 /* Mapping from each edge in the graph to its number in the rgn. */
687 static int *edge_to_bit;
688 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
690 /* The split edges of a source bb is different for each target
691 bb. In order to compute this efficiently, the 'potential-split edges'
692 are computed for each bb prior to scheduling a region. This is actually
693 the split edges of each bb relative to the region entry.
695 pot_split[bb] is the set of potential split edges of bb. */
696 static edgeset *pot_split;
698 /* For every bb, a set of its ancestor edges. */
699 static edgeset *ancestor_edges;
701 static void compute_dom_prob_ps PARAMS ((int));
703 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
704 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
705 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
706 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
708 /* Parameters affecting the decision of rank_for_schedule(). */
709 #define MIN_DIFF_PRIORITY 2
710 #define MIN_PROBABILITY 40
711 #define MIN_PROB_DIFF 10
713 /* Speculative scheduling functions. */
714 static int check_live_1 PARAMS ((int, rtx));
715 static void update_live_1 PARAMS ((int, rtx));
716 static int check_live PARAMS ((rtx, int));
717 static void update_live PARAMS ((rtx, int));
718 static void set_spec_fed PARAMS ((rtx));
719 static int is_pfree PARAMS ((rtx, int, int));
720 static int find_conditional_protection PARAMS ((rtx, int));
721 static int is_conditionally_protected PARAMS ((rtx, int, int));
722 static int may_trap_exp PARAMS ((rtx, int));
723 static int haifa_classify_insn PARAMS ((rtx));
724 static int is_prisky PARAMS ((rtx, int, int));
725 static int is_exception_free PARAMS ((rtx, int, int));
727 static char find_insn_mem_list PARAMS ((rtx, rtx, rtx, rtx));
728 static void compute_block_forward_dependences PARAMS ((int));
729 static void add_branch_dependences PARAMS ((rtx, rtx));
730 static void compute_block_backward_dependences PARAMS ((int));
731 void debug_dependencies PARAMS ((void));
733 /* Notes handling mechanism:
734 =========================
735 Generally, NOTES are saved before scheduling and restored after scheduling.
736 The scheduler distinguishes between three types of notes:
738 (1) LINE_NUMBER notes, generated and used for debugging. Here,
739 before scheduling a region, a pointer to the LINE_NUMBER note is
740 added to the insn following it (in save_line_notes()), and the note
741 is removed (in rm_line_notes() and unlink_line_notes()). After
742 scheduling the region, this pointer is used for regeneration of
743 the LINE_NUMBER note (in restore_line_notes()).
745 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
746 Before scheduling a region, a pointer to the note is added to the insn
747 that follows or precedes it. (This happens as part of the data dependence
748 computation). After scheduling an insn, the pointer contained in it is
749 used for regenerating the corresponding note (in reemit_notes).
751 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
752 these notes are put in a list (in rm_other_notes() and
753 unlink_other_notes ()). After scheduling the block, these notes are
754 inserted at the beginning of the block (in schedule_block()). */
756 static rtx unlink_other_notes PARAMS ((rtx, rtx));
757 static rtx unlink_line_notes PARAMS ((rtx, rtx));
758 static void rm_line_notes PARAMS ((int));
759 static void save_line_notes PARAMS ((int));
760 static void restore_line_notes PARAMS ((int));
761 static void rm_redundant_line_notes PARAMS ((void));
762 static void rm_other_notes PARAMS ((rtx, rtx));
763 static rtx reemit_notes PARAMS ((rtx, rtx));
765 static void get_block_head_tail PARAMS ((int, rtx *, rtx *));
766 static void get_bb_head_tail PARAMS ((int, rtx *, rtx *));
768 static int queue_to_ready PARAMS ((rtx [], int));
770 static void debug_ready_list PARAMS ((rtx[], int));
771 static void init_target_units PARAMS ((void));
772 static void insn_print_units PARAMS ((rtx));
773 static int get_visual_tbl_length PARAMS ((void));
774 static void init_block_visualization PARAMS ((void));
775 static void print_block_visualization PARAMS ((int, const char *));
776 static void visualize_scheduled_insns PARAMS ((int, int));
777 static void visualize_no_unit PARAMS ((rtx));
778 static void visualize_stall_cycles PARAMS ((int, int));
779 static void print_exp PARAMS ((char *, rtx, int));
780 static void print_value PARAMS ((char *, rtx, int));
781 static void print_pattern PARAMS ((char *, rtx, int));
782 static void print_insn PARAMS ((char *, rtx, int));
783 void debug_reg_vector PARAMS ((regset));
785 static rtx move_insn1 PARAMS ((rtx, rtx));
786 static rtx move_insn PARAMS ((rtx, rtx));
787 static rtx group_leader PARAMS ((rtx));
788 static int set_priorities PARAMS ((int));
789 static void init_deps PARAMS ((struct deps *));
790 static void schedule_region PARAMS ((int));
791 static void propagate_deps PARAMS ((int, struct deps *, int));
793 #endif /* INSN_SCHEDULING */
795 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
797 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
798 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
799 of dependence that this link represents. */
802 add_dependence (insn, elem, dep_type)
805 enum reg_note dep_type;
809 /* Don't depend an insn on itself. */
813 /* We can get a dependency on deleted insns due to optimizations in
814 the register allocation and reloading or due to splitting. Any
815 such dependency is useless and can be ignored. */
816 if (GET_CODE (elem) == NOTE)
819 /* If elem is part of a sequence that must be scheduled together, then
820 make the dependence point to the last insn of the sequence.
821 When HAVE_cc0, it is possible for NOTEs to exist between users and
822 setters of the condition codes, so we must skip past notes here.
823 Otherwise, NOTEs are impossible here. */
825 next = NEXT_INSN (elem);
828 while (next && GET_CODE (next) == NOTE)
829 next = NEXT_INSN (next);
832 if (next && SCHED_GROUP_P (next)
833 && GET_CODE (next) != CODE_LABEL)
835 /* Notes will never intervene here though, so don't bother checking
837 /* We must reject CODE_LABELs, so that we don't get confused by one
838 that has LABEL_PRESERVE_P set, which is represented by the same
839 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
841 while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
842 && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
843 next = NEXT_INSN (next);
845 /* Again, don't depend an insn on itself. */
849 /* Make the dependence to NEXT, the last insn of the group, instead
850 of the original ELEM. */
854 #ifdef INSN_SCHEDULING
855 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
856 No need for interblock dependences with calls, since
857 calls are not moved between blocks. Note: the edge where
858 elem is a CALL is still required. */
859 if (GET_CODE (insn) == CALL_INSN
860 && (INSN_BB (elem) != INSN_BB (insn)))
864 /* If we already have a true dependency for ELEM, then we do not
865 need to do anything. Avoiding the list walk below can cut
866 compile times dramatically for some code. */
867 if (true_dependency_cache
868 && TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)))
872 /* Check that we don't already have this dependence. */
873 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
874 if (XEXP (link, 0) == elem)
876 /* If this is a more restrictive type of dependence than the existing
877 one, then change the existing dependence to this type. */
878 if ((int) dep_type < (int) REG_NOTE_KIND (link))
879 PUT_REG_NOTE_KIND (link, dep_type);
881 #ifdef INSN_SCHEDULING
882 /* If we are adding a true dependency to INSN's LOG_LINKs, then
883 note that in the bitmap cache of true dependency information. */
884 if ((int)dep_type == 0 && true_dependency_cache)
885 SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
889 /* Might want to check one level of transitivity to save conses. */
891 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
892 LOG_LINKS (insn) = link;
894 /* Insn dependency, not data dependency. */
895 PUT_REG_NOTE_KIND (link, dep_type);
897 #ifdef INSN_SCHEDULING
898 /* If we are adding a true dependency to INSN's LOG_LINKs, then
899 note that in the bitmap cache of true dependency information. */
900 if ((int)dep_type == 0 && true_dependency_cache)
901 SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
906 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
907 of INSN. Abort if not found. */
910 remove_dependence (insn, elem)
914 rtx prev, link, next;
917 for (prev = 0, link = LOG_LINKS (insn); link; link = next)
919 next = XEXP (link, 1);
920 if (XEXP (link, 0) == elem)
923 XEXP (prev, 1) = next;
925 LOG_LINKS (insn) = next;
927 #ifdef INSN_SCHEDULING
928 /* If we are removing a true dependency from the LOG_LINKS list,
929 make sure to remove it from the cache too. */
930 if (REG_NOTE_KIND (link) == 0 && true_dependency_cache)
931 RESET_BIT (true_dependency_cache[INSN_LUID (insn)],
935 free_INSN_LIST_node (link);
947 #endif /* HAVE_cc0 */
949 #ifndef INSN_SCHEDULING
951 schedule_insns (dump_file)
952 FILE *dump_file ATTRIBUTE_UNUSED;
961 #define HAIFA_INLINE __inline
964 /* Computation of memory dependencies. */
966 /* Data structures for the computation of data dependences in a regions. We
967 keep one mem_deps structure for every basic block. Before analyzing the
968 data dependences for a bb, its variables are initialized as a function of
969 the variables of its predecessors. When the analysis for a bb completes,
970 we save the contents to the corresponding bb_mem_deps[bb] variable. */
972 static struct deps *bb_deps;
974 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
975 so that insns independent of the last scheduled insn will be preferred
976 over dependent instructions. */
978 static rtx last_scheduled_insn;
980 /* Functions for construction of the control flow graph. */
982 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
984 We decide not to build the control flow graph if there is possibly more
985 than one entry to the function, if computed branches exist, of if we
986 have nonlocal gotos. */
995 /* If we have a label that could be the target of a nonlocal goto, then
996 the cfg is not well structured. */
997 if (nonlocal_goto_handler_labels)
1000 /* If we have any forced labels, then the cfg is not well structured. */
1004 /* If this function has a computed jump, then we consider the cfg
1005 not well structured. */
1006 if (current_function_has_computed_jump)
1009 /* If we have exception handlers, then we consider the cfg not well
1010 structured. ?!? We should be able to handle this now that flow.c
1011 computes an accurate cfg for EH. */
1012 if (exception_handler_labels)
1015 /* If we have non-jumping insns which refer to labels, then we consider
1016 the cfg not well structured. */
1017 /* Check for labels referred to other thn by jumps. */
1018 for (b = 0; b < n_basic_blocks; b++)
1019 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
1021 code = GET_CODE (insn);
1022 if (GET_RTX_CLASS (code) == 'i')
1026 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1027 if (REG_NOTE_KIND (note) == REG_LABEL)
1031 if (insn == BLOCK_END (b))
1035 /* All the tests passed. Consider the cfg well structured. */
1039 /* Build the control flow graph and set nr_edges.
1041 Instead of trying to build a cfg ourselves, we rely on flow to
1042 do it for us. Stamp out useless code (and bug) duplication.
1044 Return nonzero if an irregularity in the cfg is found which would
1045 prevent cross block scheduling. */
1048 build_control_flow (edge_list)
1049 struct edge_list *edge_list;
1051 int i, unreachable, num_edges;
1053 /* This already accounts for entry/exit edges. */
1054 num_edges = NUM_EDGES (edge_list);
1056 /* Unreachable loops with more than one basic block are detected
1057 during the DFS traversal in find_rgns.
1059 Unreachable loops with a single block are detected here. This
1060 test is redundant with the one in find_rgns, but it's much
1061 cheaper to go ahead and catch the trivial case here. */
1063 for (i = 0; i < n_basic_blocks; i++)
1065 basic_block b = BASIC_BLOCK (i);
1068 || (b->pred->src == b
1069 && b->pred->pred_next == NULL))
1073 /* ??? We can kill these soon. */
1074 in_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
1075 out_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
1076 edge_table = (haifa_edge *) xcalloc (num_edges, sizeof (haifa_edge));
1079 for (i = 0; i < num_edges; i++)
1081 edge e = INDEX_EDGE (edge_list, i);
1083 if (e->dest != EXIT_BLOCK_PTR
1084 && e->src != ENTRY_BLOCK_PTR)
1085 new_edge (e->src->index, e->dest->index);
1088 /* Increment by 1, since edge 0 is unused. */
1095 /* Record an edge in the control flow graph from SOURCE to TARGET.
1097 In theory, this is redundant with the s_succs computed above, but
1098 we have not converted all of haifa to use information from the
1102 new_edge (source, target)
1106 int curr_edge, fst_edge;
1108 /* Check for duplicates. */
1109 fst_edge = curr_edge = OUT_EDGES (source);
1112 if (FROM_BLOCK (curr_edge) == source
1113 && TO_BLOCK (curr_edge) == target)
1118 curr_edge = NEXT_OUT (curr_edge);
1120 if (fst_edge == curr_edge)
1126 FROM_BLOCK (e) = source;
1127 TO_BLOCK (e) = target;
1129 if (OUT_EDGES (source))
1131 next_edge = NEXT_OUT (OUT_EDGES (source));
1132 NEXT_OUT (OUT_EDGES (source)) = e;
1133 NEXT_OUT (e) = next_edge;
1137 OUT_EDGES (source) = e;
1141 if (IN_EDGES (target))
1143 next_edge = NEXT_IN (IN_EDGES (target));
1144 NEXT_IN (IN_EDGES (target)) = e;
1145 NEXT_IN (e) = next_edge;
1149 IN_EDGES (target) = e;
1155 /* BITSET macros for operations on the control flow graph. */
1157 /* Compute bitwise union of two bitsets. */
1158 #define BITSET_UNION(set1, set2, len) \
1159 do { register bitset tp = set1, sp = set2; \
1161 for (i = 0; i < len; i++) \
1162 *(tp++) |= *(sp++); } while (0)
1164 /* Compute bitwise intersection of two bitsets. */
1165 #define BITSET_INTER(set1, set2, len) \
1166 do { register bitset tp = set1, sp = set2; \
1168 for (i = 0; i < len; i++) \
1169 *(tp++) &= *(sp++); } while (0)
1171 /* Compute bitwise difference of two bitsets. */
1172 #define BITSET_DIFFER(set1, set2, len) \
1173 do { register bitset tp = set1, sp = set2; \
1175 for (i = 0; i < len; i++) \
1176 *(tp++) &= ~*(sp++); } while (0)
1178 /* Inverts every bit of bitset 'set'. */
1179 #define BITSET_INVERT(set, len) \
1180 do { register bitset tmpset = set; \
1182 for (i = 0; i < len; i++, tmpset++) \
1183 *tmpset = ~*tmpset; } while (0)
1185 /* Turn on the index'th bit in bitset set. */
1186 #define BITSET_ADD(set, index, len) \
1188 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1191 set[index/HOST_BITS_PER_WIDE_INT] |= \
1192 1 << (index % HOST_BITS_PER_WIDE_INT); \
1195 /* Turn off the index'th bit in set. */
1196 #define BITSET_REMOVE(set, index, len) \
1198 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1201 set[index/HOST_BITS_PER_WIDE_INT] &= \
1202 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1206 /* Check if the index'th bit in bitset set is on. */
1209 bitset_member (set, index, len)
1213 if (index >= HOST_BITS_PER_WIDE_INT * len)
1215 return (set[index / HOST_BITS_PER_WIDE_INT] &
1216 1 << (index % HOST_BITS_PER_WIDE_INT)) ? 1 : 0;
1220 /* Translate a bit-set SET to a list BL of the bit-set members. */
1223 extract_bitlst (set, len, bitlen, bl)
1230 unsigned HOST_WIDE_INT word;
1232 /* bblst table space is reused in each call to extract_bitlst. */
1233 bitlst_table_last = 0;
1235 bl->first_member = &bitlst_table[bitlst_table_last];
1238 /* Iterate over each word in the bitset. */
1239 for (i = 0; i < len; i++)
1242 offset = i * HOST_BITS_PER_WIDE_INT;
1244 /* Iterate over each bit in the word, but do not
1245 go beyond the end of the defined bits. */
1246 for (j = 0; offset < bitlen && word; j++)
1250 bitlst_table[bitlst_table_last++] = offset;
1261 /* Functions for the construction of regions. */
1263 /* Print the regions, for debugging purposes. Callable from debugger. */
1270 fprintf (dump, "\n;; ------------ REGIONS ----------\n\n");
1271 for (rgn = 0; rgn < nr_regions; rgn++)
1273 fprintf (dump, ";;\trgn %d nr_blocks %d:\n", rgn,
1274 rgn_table[rgn].rgn_nr_blocks);
1275 fprintf (dump, ";;\tbb/block: ");
1277 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
1279 current_blocks = RGN_BLOCKS (rgn);
1281 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
1284 fprintf (dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
1287 fprintf (dump, "\n\n");
1292 /* Build a single block region for each basic block in the function.
1293 This allows for using the same code for interblock and basic block
1297 find_single_block_region ()
1301 for (i = 0; i < n_basic_blocks; i++)
1303 rgn_bb_table[i] = i;
1304 RGN_NR_BLOCKS (i) = 1;
1306 CONTAINING_RGN (i) = i;
1307 BLOCK_TO_BB (i) = 0;
1309 nr_regions = n_basic_blocks;
1313 /* Update number of blocks and the estimate for number of insns
1314 in the region. Return 1 if the region is "too large" for interblock
1315 scheduling (compile time considerations), otherwise return 0. */
1318 too_large (block, num_bbs, num_insns)
1319 int block, *num_bbs, *num_insns;
1322 (*num_insns) += (INSN_LUID (BLOCK_END (block)) -
1323 INSN_LUID (BLOCK_HEAD (block)));
1324 if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
1331 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1332 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1333 loop containing blk. */
1334 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1336 if (max_hdr[blk] == -1) \
1337 max_hdr[blk] = hdr; \
1338 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1339 RESET_BIT (inner, hdr); \
1340 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1342 RESET_BIT (inner,max_hdr[blk]); \
1343 max_hdr[blk] = hdr; \
1348 /* Find regions for interblock scheduling.
1350 A region for scheduling can be:
1352 * A loop-free procedure, or
1354 * A reducible inner loop, or
1356 * A basic block not contained in any other region.
1359 ?!? In theory we could build other regions based on extended basic
1360 blocks or reverse extended basic blocks. Is it worth the trouble?
1362 Loop blocks that form a region are put into the region's block list
1363 in topological order.
1365 This procedure stores its results into the following global (ick) variables
1374 We use dominator relationships to avoid making regions out of non-reducible
1377 This procedure needs to be converted to work on pred/succ lists instead
1378 of edge tables. That would simplify it somewhat. */
1381 find_rgns (edge_list, dom)
1382 struct edge_list *edge_list;
1385 int *max_hdr, *dfs_nr, *stack, *degree;
1387 int node, child, loop_head, i, head, tail;
1388 int count = 0, sp, idx = 0, current_edge = out_edges[0];
1389 int num_bbs, num_insns, unreachable;
1390 int too_large_failure;
1392 /* Note if an edge has been passed. */
1395 /* Note if a block is a natural loop header. */
1398 /* Note if a block is an natural inner loop header. */
1401 /* Note if a block is in the block queue. */
1404 /* Note if a block is in the block queue. */
1407 int num_edges = NUM_EDGES (edge_list);
1409 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1410 and a mapping from block to its loop header (if the block is contained
1411 in a loop, else -1).
1413 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1414 be used as inputs to the second traversal.
1416 STACK, SP and DFS_NR are only used during the first traversal. */
1418 /* Allocate and initialize variables for the first traversal. */
1419 max_hdr = (int *) xmalloc (n_basic_blocks * sizeof (int));
1420 dfs_nr = (int *) xcalloc (n_basic_blocks, sizeof (int));
1421 stack = (int *) xmalloc (nr_edges * sizeof (int));
1423 inner = sbitmap_alloc (n_basic_blocks);
1424 sbitmap_ones (inner);
1426 header = sbitmap_alloc (n_basic_blocks);
1427 sbitmap_zero (header);
1429 passed = sbitmap_alloc (nr_edges);
1430 sbitmap_zero (passed);
1432 in_queue = sbitmap_alloc (n_basic_blocks);
1433 sbitmap_zero (in_queue);
1435 in_stack = sbitmap_alloc (n_basic_blocks);
1436 sbitmap_zero (in_stack);
1438 for (i = 0; i < n_basic_blocks; i++)
1441 /* DFS traversal to find inner loops in the cfg. */
1446 if (current_edge == 0 || TEST_BIT (passed, current_edge))
1448 /* We have reached a leaf node or a node that was already
1449 processed. Pop edges off the stack until we find
1450 an edge that has not yet been processed. */
1452 && (current_edge == 0 || TEST_BIT (passed, current_edge)))
1454 /* Pop entry off the stack. */
1455 current_edge = stack[sp--];
1456 node = FROM_BLOCK (current_edge);
1457 child = TO_BLOCK (current_edge);
1458 RESET_BIT (in_stack, child);
1459 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1460 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1461 current_edge = NEXT_OUT (current_edge);
1464 /* See if have finished the DFS tree traversal. */
1465 if (sp < 0 && TEST_BIT (passed, current_edge))
1468 /* Nope, continue the traversal with the popped node. */
1472 /* Process a node. */
1473 node = FROM_BLOCK (current_edge);
1474 child = TO_BLOCK (current_edge);
1475 SET_BIT (in_stack, node);
1476 dfs_nr[node] = ++count;
1478 /* If the successor is in the stack, then we've found a loop.
1479 Mark the loop, if it is not a natural loop, then it will
1480 be rejected during the second traversal. */
1481 if (TEST_BIT (in_stack, child))
1484 SET_BIT (header, child);
1485 UPDATE_LOOP_RELATIONS (node, child);
1486 SET_BIT (passed, current_edge);
1487 current_edge = NEXT_OUT (current_edge);
1491 /* If the child was already visited, then there is no need to visit
1492 it again. Just update the loop relationships and restart
1496 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1497 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1498 SET_BIT (passed, current_edge);
1499 current_edge = NEXT_OUT (current_edge);
1503 /* Push an entry on the stack and continue DFS traversal. */
1504 stack[++sp] = current_edge;
1505 SET_BIT (passed, current_edge);
1506 current_edge = OUT_EDGES (child);
1508 /* This is temporary until haifa is converted to use rth's new
1509 cfg routines which have true entry/exit blocks and the
1510 appropriate edges from/to those blocks.
1512 Generally we update dfs_nr for a node when we process its
1513 out edge. However, if the node has no out edge then we will
1514 not set dfs_nr for that node. This can confuse the scheduler
1515 into thinking that we have unreachable blocks, which in turn
1516 disables cross block scheduling.
1518 So, if we have a node with no out edges, go ahead and mark it
1519 as reachable now. */
1520 if (current_edge == 0)
1521 dfs_nr[child] = ++count;
1524 /* Another check for unreachable blocks. The earlier test in
1525 is_cfg_nonregular only finds unreachable blocks that do not
1528 The DFS traversal will mark every block that is reachable from
1529 the entry node by placing a nonzero value in dfs_nr. Thus if
1530 dfs_nr is zero for any block, then it must be unreachable. */
1532 for (i = 0; i < n_basic_blocks; i++)
1539 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1540 to hold degree counts. */
1543 for (i = 0; i < n_basic_blocks; i++)
1545 for (i = 0; i < num_edges; i++)
1547 edge e = INDEX_EDGE (edge_list, i);
1549 if (e->dest != EXIT_BLOCK_PTR)
1550 degree[e->dest->index]++;
1553 /* Do not perform region scheduling if there are any unreachable
1560 SET_BIT (header, 0);
1562 /* Second travsersal:find reducible inner loops and topologically sort
1563 block of each region. */
1565 queue = (int *) xmalloc (n_basic_blocks * sizeof (int));
1567 /* Find blocks which are inner loop headers. We still have non-reducible
1568 loops to consider at this point. */
1569 for (i = 0; i < n_basic_blocks; i++)
1571 if (TEST_BIT (header, i) && TEST_BIT (inner, i))
1576 /* Now check that the loop is reducible. We do this separate
1577 from finding inner loops so that we do not find a reducible
1578 loop which contains an inner non-reducible loop.
1580 A simple way to find reducible/natural loops is to verify
1581 that each block in the loop is dominated by the loop
1584 If there exists a block that is not dominated by the loop
1585 header, then the block is reachable from outside the loop
1586 and thus the loop is not a natural loop. */
1587 for (j = 0; j < n_basic_blocks; j++)
1589 /* First identify blocks in the loop, except for the loop
1591 if (i == max_hdr[j] && i != j)
1593 /* Now verify that the block is dominated by the loop
1595 if (!TEST_BIT (dom[j], i))
1600 /* If we exited the loop early, then I is the header of
1601 a non-reducible loop and we should quit processing it
1603 if (j != n_basic_blocks)
1606 /* I is a header of an inner loop, or block 0 in a subroutine
1607 with no loops at all. */
1609 too_large_failure = 0;
1610 loop_head = max_hdr[i];
1612 /* Decrease degree of all I's successors for topological
1614 for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
1615 if (e->dest != EXIT_BLOCK_PTR)
1616 --degree[e->dest->index];
1618 /* Estimate # insns, and count # blocks in the region. */
1620 num_insns = (INSN_LUID (BLOCK_END (i))
1621 - INSN_LUID (BLOCK_HEAD (i)));
1624 /* Find all loop latches (blocks with back edges to the loop
1625 header) or all the leaf blocks in the cfg has no loops.
1627 Place those blocks into the queue. */
1630 for (j = 0; j < n_basic_blocks; j++)
1631 /* Leaf nodes have only a single successor which must
1633 if (BASIC_BLOCK (j)->succ
1634 && BASIC_BLOCK (j)->succ->dest == EXIT_BLOCK_PTR
1635 && BASIC_BLOCK (j)->succ->succ_next == NULL)
1638 SET_BIT (in_queue, j);
1640 if (too_large (j, &num_bbs, &num_insns))
1642 too_large_failure = 1;
1651 for (e = BASIC_BLOCK (i)->pred; e; e = e->pred_next)
1653 if (e->src == ENTRY_BLOCK_PTR)
1656 node = e->src->index;
1658 if (max_hdr[node] == loop_head && node != i)
1660 /* This is a loop latch. */
1661 queue[++tail] = node;
1662 SET_BIT (in_queue, node);
1664 if (too_large (node, &num_bbs, &num_insns))
1666 too_large_failure = 1;
1674 /* Now add all the blocks in the loop to the queue.
1676 We know the loop is a natural loop; however the algorithm
1677 above will not always mark certain blocks as being in the
1686 The algorithm in the DFS traversal may not mark B & D as part
1687 of the loop (ie they will not have max_hdr set to A).
1689 We know they can not be loop latches (else they would have
1690 had max_hdr set since they'd have a backedge to a dominator
1691 block). So we don't need them on the initial queue.
1693 We know they are part of the loop because they are dominated
1694 by the loop header and can be reached by a backwards walk of
1695 the edges starting with nodes on the initial queue.
1697 It is safe and desirable to include those nodes in the
1698 loop/scheduling region. To do so we would need to decrease
1699 the degree of a node if it is the target of a backedge
1700 within the loop itself as the node is placed in the queue.
1702 We do not do this because I'm not sure that the actual
1703 scheduling code will properly handle this case. ?!? */
1705 while (head < tail && !too_large_failure)
1708 child = queue[++head];
1710 for (e = BASIC_BLOCK (child)->pred; e; e = e->pred_next)
1712 node = e->src->index;
1714 /* See discussion above about nodes not marked as in
1715 this loop during the initial DFS traversal. */
1716 if (e->src == ENTRY_BLOCK_PTR
1717 || max_hdr[node] != loop_head)
1722 else if (!TEST_BIT (in_queue, node) && node != i)
1724 queue[++tail] = node;
1725 SET_BIT (in_queue, node);
1727 if (too_large (node, &num_bbs, &num_insns))
1729 too_large_failure = 1;
1736 if (tail >= 0 && !too_large_failure)
1738 /* Place the loop header into list of region blocks. */
1740 rgn_bb_table[idx] = i;
1741 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1742 RGN_BLOCKS (nr_regions) = idx++;
1743 CONTAINING_RGN (i) = nr_regions;
1744 BLOCK_TO_BB (i) = count = 0;
1746 /* Remove blocks from queue[] when their in degree
1747 becomes zero. Repeat until no blocks are left on the
1748 list. This produces a topological list of blocks in
1754 child = queue[head];
1755 if (degree[child] == 0)
1760 rgn_bb_table[idx++] = child;
1761 BLOCK_TO_BB (child) = ++count;
1762 CONTAINING_RGN (child) = nr_regions;
1763 queue[head] = queue[tail--];
1765 for (e = BASIC_BLOCK (child)->succ;
1768 if (e->dest != EXIT_BLOCK_PTR)
1769 --degree[e->dest->index];
1781 /* Any block that did not end up in a region is placed into a region
1783 for (i = 0; i < n_basic_blocks; i++)
1786 rgn_bb_table[idx] = i;
1787 RGN_NR_BLOCKS (nr_regions) = 1;
1788 RGN_BLOCKS (nr_regions) = idx++;
1789 CONTAINING_RGN (i) = nr_regions++;
1790 BLOCK_TO_BB (i) = 0;
1804 /* Functions for regions scheduling information. */
1806 /* Compute dominators, probability, and potential-split-edges of bb.
1807 Assume that these values were already computed for bb's predecessors. */
1810 compute_dom_prob_ps (bb)
1813 int nxt_in_edge, fst_in_edge, pred;
1814 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1817 if (IS_RGN_ENTRY (bb))
1819 BITSET_ADD (dom[bb], 0, bbset_size);
1824 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1826 /* Intialize dom[bb] to '111..1'. */
1827 BITSET_INVERT (dom[bb], bbset_size);
1831 pred = FROM_BLOCK (nxt_in_edge);
1832 BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
1834 BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
1837 BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
1840 nr_rgn_out_edges = 0;
1841 fst_out_edge = OUT_EDGES (pred);
1842 nxt_out_edge = NEXT_OUT (fst_out_edge);
1843 BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
1846 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
1848 /* The successor doesn't belong in the region? */
1849 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1850 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1853 while (fst_out_edge != nxt_out_edge)
1856 /* The successor doesn't belong in the region? */
1857 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1858 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1860 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
1861 nxt_out_edge = NEXT_OUT (nxt_out_edge);
1865 /* Now nr_rgn_out_edges is the number of region-exit edges from
1866 pred, and nr_out_edges will be the number of pred out edges
1867 not leaving the region. */
1868 nr_out_edges -= nr_rgn_out_edges;
1869 if (nr_rgn_out_edges > 0)
1870 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1872 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1873 nxt_in_edge = NEXT_IN (nxt_in_edge);
1875 while (fst_in_edge != nxt_in_edge);
1877 BITSET_ADD (dom[bb], bb, bbset_size);
1878 BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
1880 if (sched_verbose >= 2)
1881 fprintf (dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb), (int) (100.0 * prob[bb]));
1882 } /* compute_dom_prob_ps */
1884 /* Functions for target info. */
1886 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1887 Note that bb_trg dominates bb_src. */
1890 split_edges (bb_src, bb_trg, bl)
1895 int es = edgeset_size;
1896 edgeset src = (edgeset) xcalloc (es, sizeof (HOST_WIDE_INT));
1899 src[es] = (pot_split[bb_src])[es];
1900 BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
1901 extract_bitlst (src, edgeset_size, edgeset_bitsize, bl);
1906 /* Find the valid candidate-source-blocks for the target block TRG, compute
1907 their probability, and check if they are speculative or not.
1908 For speculative sources, compute their update-blocks and split-blocks. */
1911 compute_trg_info (trg)
1914 register candidate *sp;
1916 int check_block, update_idx;
1917 int i, j, k, fst_edge, nxt_edge;
1919 /* Define some of the fields for the target bb as well. */
1920 sp = candidate_table + trg;
1922 sp->is_speculative = 0;
1925 for (i = trg + 1; i < current_nr_blocks; i++)
1927 sp = candidate_table + i;
1929 sp->is_valid = IS_DOMINATED (i, trg);
1932 sp->src_prob = GET_SRC_PROB (i, trg);
1933 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
1938 split_edges (i, trg, &el);
1939 sp->is_speculative = (el.nr_members) ? 1 : 0;
1940 if (sp->is_speculative && !flag_schedule_speculative)
1946 sp->split_bbs.first_member = &bblst_table[bblst_last];
1947 sp->split_bbs.nr_members = el.nr_members;
1948 for (j = 0; j < el.nr_members; bblst_last++, j++)
1949 bblst_table[bblst_last] =
1950 TO_BLOCK (rgn_edges[el.first_member[j]]);
1951 sp->update_bbs.first_member = &bblst_table[bblst_last];
1953 for (j = 0; j < el.nr_members; j++)
1955 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
1956 fst_edge = nxt_edge = OUT_EDGES (check_block);
1959 for (k = 0; k < el.nr_members; k++)
1960 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
1963 if (k >= el.nr_members)
1965 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
1969 nxt_edge = NEXT_OUT (nxt_edge);
1971 while (fst_edge != nxt_edge);
1973 sp->update_bbs.nr_members = update_idx;
1978 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1980 sp->is_speculative = 0;
1984 } /* compute_trg_info */
1987 /* Print candidates info, for debugging purposes. Callable from debugger. */
1993 if (!candidate_table[i].is_valid)
1996 if (candidate_table[i].is_speculative)
1999 fprintf (dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
2001 fprintf (dump, "split path: ");
2002 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
2004 int b = candidate_table[i].split_bbs.first_member[j];
2006 fprintf (dump, " %d ", b);
2008 fprintf (dump, "\n");
2010 fprintf (dump, "update path: ");
2011 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
2013 int b = candidate_table[i].update_bbs.first_member[j];
2015 fprintf (dump, " %d ", b);
2017 fprintf (dump, "\n");
2021 fprintf (dump, " src %d equivalent\n", BB_TO_BLOCK (i));
2026 /* Print candidates info, for debugging purposes. Callable from debugger. */
2029 debug_candidates (trg)
2034 fprintf (dump, "----------- candidate table: target: b=%d bb=%d ---\n",
2035 BB_TO_BLOCK (trg), trg);
2036 for (i = trg + 1; i < current_nr_blocks; i++)
2037 debug_candidate (i);
2041 /* Functions for speculative scheduing. */
2043 /* Return 0 if x is a set of a register alive in the beginning of one
2044 of the split-blocks of src, otherwise return 1. */
2047 check_live_1 (src, x)
2053 register rtx reg = SET_DEST (x);
2058 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2059 || GET_CODE (reg) == SIGN_EXTRACT
2060 || GET_CODE (reg) == STRICT_LOW_PART)
2061 reg = XEXP (reg, 0);
2063 if (GET_CODE (reg) == PARALLEL
2064 && GET_MODE (reg) == BLKmode)
2067 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2068 if (check_live_1 (src, XVECEXP (reg, 0, i)))
2073 if (GET_CODE (reg) != REG)
2076 regno = REGNO (reg);
2078 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2080 /* Global registers are assumed live. */
2085 if (regno < FIRST_PSEUDO_REGISTER)
2087 /* Check for hard registers. */
2088 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2091 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2093 int b = candidate_table[src].split_bbs.first_member[i];
2095 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
2105 /* Check for psuedo registers. */
2106 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2108 int b = candidate_table[src].split_bbs.first_member[i];
2110 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
2122 /* If x is a set of a register R, mark that R is alive in the beginning
2123 of every update-block of src. */
2126 update_live_1 (src, x)
2132 register rtx reg = SET_DEST (x);
2137 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2138 || GET_CODE (reg) == SIGN_EXTRACT
2139 || GET_CODE (reg) == STRICT_LOW_PART)
2140 reg = XEXP (reg, 0);
2142 if (GET_CODE (reg) == PARALLEL
2143 && GET_MODE (reg) == BLKmode)
2146 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2147 update_live_1 (src, XVECEXP (reg, 0, i));
2151 if (GET_CODE (reg) != REG)
2154 /* Global registers are always live, so the code below does not apply
2157 regno = REGNO (reg);
2159 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
2161 if (regno < FIRST_PSEUDO_REGISTER)
2163 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2166 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2168 int b = candidate_table[src].update_bbs.first_member[i];
2170 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
2177 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2179 int b = candidate_table[src].update_bbs.first_member[i];
2181 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
2188 /* Return 1 if insn can be speculatively moved from block src to trg,
2189 otherwise return 0. Called before first insertion of insn to
2190 ready-list or before the scheduling. */
2193 check_live (insn, src)
2197 /* Find the registers set by instruction. */
2198 if (GET_CODE (PATTERN (insn)) == SET
2199 || GET_CODE (PATTERN (insn)) == CLOBBER)
2200 return check_live_1 (src, PATTERN (insn));
2201 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2204 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2205 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2206 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2207 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
2217 /* Update the live registers info after insn was moved speculatively from
2218 block src to trg. */
2221 update_live (insn, src)
2225 /* Find the registers set by instruction. */
2226 if (GET_CODE (PATTERN (insn)) == SET
2227 || GET_CODE (PATTERN (insn)) == CLOBBER)
2228 update_live_1 (src, PATTERN (insn));
2229 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2232 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2233 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2234 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2235 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
2239 /* Exception Free Loads:
2241 We define five classes of speculative loads: IFREE, IRISKY,
2242 PFREE, PRISKY, and MFREE.
2244 IFREE loads are loads that are proved to be exception-free, just
2245 by examining the load insn. Examples for such loads are loads
2246 from TOC and loads of global data.
2248 IRISKY loads are loads that are proved to be exception-risky,
2249 just by examining the load insn. Examples for such loads are
2250 volatile loads and loads from shared memory.
2252 PFREE loads are loads for which we can prove, by examining other
2253 insns, that they are exception-free. Currently, this class consists
2254 of loads for which we are able to find a "similar load", either in
2255 the target block, or, if only one split-block exists, in that split
2256 block. Load2 is similar to load1 if both have same single base
2257 register. We identify only part of the similar loads, by finding
2258 an insn upon which both load1 and load2 have a DEF-USE dependence.
2260 PRISKY loads are loads for which we can prove, by examining other
2261 insns, that they are exception-risky. Currently we have two proofs for
2262 such loads. The first proof detects loads that are probably guarded by a
2263 test on the memory address. This proof is based on the
2264 backward and forward data dependence information for the region.
2265 Let load-insn be the examined load.
2266 Load-insn is PRISKY iff ALL the following hold:
2268 - insn1 is not in the same block as load-insn
2269 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2270 - test-insn is either a compare or a branch, not in the same block
2272 - load-insn is reachable from test-insn
2273 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2275 This proof might fail when the compare and the load are fed
2276 by an insn not in the region. To solve this, we will add to this
2277 group all loads that have no input DEF-USE dependence.
2279 The second proof detects loads that are directly or indirectly
2280 fed by a speculative load. This proof is affected by the
2281 scheduling process. We will use the flag fed_by_spec_load.
2282 Initially, all insns have this flag reset. After a speculative
2283 motion of an insn, if insn is either a load, or marked as
2284 fed_by_spec_load, we will also mark as fed_by_spec_load every
2285 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2286 load which is fed_by_spec_load is also PRISKY.
2288 MFREE (maybe-free) loads are all the remaining loads. They may be
2289 exception-free, but we cannot prove it.
2291 Now, all loads in IFREE and PFREE classes are considered
2292 exception-free, while all loads in IRISKY and PRISKY classes are
2293 considered exception-risky. As for loads in the MFREE class,
2294 these are considered either exception-free or exception-risky,
2295 depending on whether we are pessimistic or optimistic. We have
2296 to take the pessimistic approach to assure the safety of
2297 speculative scheduling, but we can take the optimistic approach
2298 by invoking the -fsched_spec_load_dangerous option. */
2300 enum INSN_TRAP_CLASS
2302 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
2303 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
2306 #define WORST_CLASS(class1, class2) \
2307 ((class1 > class2) ? class1 : class2)
2309 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2310 #define IS_REACHABLE(bb_from, bb_to) \
2312 || IS_RGN_ENTRY (bb_from) \
2313 || (bitset_member (ancestor_edges[bb_to], \
2314 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2317 /* Non-zero iff the address is comprised from at most 1 register. */
2318 #define CONST_BASED_ADDRESS_P(x) \
2319 (GET_CODE (x) == REG \
2320 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2321 || (GET_CODE (x) == LO_SUM)) \
2322 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2323 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2325 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2328 set_spec_fed (load_insn)
2333 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
2334 if (GET_MODE (link) == VOIDmode)
2335 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
2336 } /* set_spec_fed */
2338 /* On the path from the insn to load_insn_bb, find a conditional
2339 branch depending on insn, that guards the speculative load. */
2342 find_conditional_protection (insn, load_insn_bb)
2348 /* Iterate through DEF-USE forward dependences. */
2349 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2351 rtx next = XEXP (link, 0);
2352 if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
2353 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
2354 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
2355 && load_insn_bb != INSN_BB (next)
2356 && GET_MODE (link) == VOIDmode
2357 && (GET_CODE (next) == JUMP_INSN
2358 || find_conditional_protection (next, load_insn_bb)))
2362 } /* find_conditional_protection */
2364 /* Returns 1 if the same insn1 that participates in the computation
2365 of load_insn's address is feeding a conditional branch that is
2366 guarding on load_insn. This is true if we find a the two DEF-USE
2368 insn1 -> ... -> conditional-branch
2369 insn1 -> ... -> load_insn,
2370 and if a flow path exist:
2371 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2372 and if insn1 is on the path
2373 region-entry -> ... -> bb_trg -> ... load_insn.
2375 Locate insn1 by climbing on LOG_LINKS from load_insn.
2376 Locate the branch by following INSN_DEPEND from insn1. */
2379 is_conditionally_protected (load_insn, bb_src, bb_trg)
2385 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
2387 rtx insn1 = XEXP (link, 0);
2389 /* Must be a DEF-USE dependence upon non-branch. */
2390 if (GET_MODE (link) != VOIDmode
2391 || GET_CODE (insn1) == JUMP_INSN)
2394 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
2395 if (INSN_BB (insn1) == bb_src
2396 || (CONTAINING_RGN (BLOCK_NUM (insn1))
2397 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
2398 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
2399 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
2402 /* Now search for the conditional-branch. */
2403 if (find_conditional_protection (insn1, bb_src))
2406 /* Recursive step: search another insn1, "above" current insn1. */
2407 return is_conditionally_protected (insn1, bb_src, bb_trg);
2410 /* The chain does not exist. */
2412 } /* is_conditionally_protected */
2414 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2415 load_insn can move speculatively from bb_src to bb_trg. All the
2416 following must hold:
2418 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2419 (2) load_insn and load1 have a def-use dependence upon
2420 the same insn 'insn1'.
2421 (3) either load2 is in bb_trg, or:
2422 - there's only one split-block, and
2423 - load1 is on the escape path, and
2425 From all these we can conclude that the two loads access memory
2426 addresses that differ at most by a constant, and hence if moving
2427 load_insn would cause an exception, it would have been caused by
2431 is_pfree (load_insn, bb_src, bb_trg)
2436 register candidate *candp = candidate_table + bb_src;
2438 if (candp->split_bbs.nr_members != 1)
2439 /* Must have exactly one escape block. */
2442 for (back_link = LOG_LINKS (load_insn);
2443 back_link; back_link = XEXP (back_link, 1))
2445 rtx insn1 = XEXP (back_link, 0);
2447 if (GET_MODE (back_link) == VOIDmode)
2449 /* Found a DEF-USE dependence (insn1, load_insn). */
2452 for (fore_link = INSN_DEPEND (insn1);
2453 fore_link; fore_link = XEXP (fore_link, 1))
2455 rtx insn2 = XEXP (fore_link, 0);
2456 if (GET_MODE (fore_link) == VOIDmode)
2458 /* Found a DEF-USE dependence (insn1, insn2). */
2459 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
2460 /* insn2 not guaranteed to be a 1 base reg load. */
2463 if (INSN_BB (insn2) == bb_trg)
2464 /* insn2 is the similar load, in the target block. */
2467 if (*(candp->split_bbs.first_member) == BLOCK_NUM (insn2))
2468 /* insn2 is a similar load, in a split-block. */
2475 /* Couldn't find a similar load. */
2479 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2480 as found by analyzing insn's expression. */
2483 may_trap_exp (x, is_store)
2491 code = GET_CODE (x);
2501 /* The insn uses memory: a volatile load. */
2502 if (MEM_VOLATILE_P (x))
2504 /* An exception-free load. */
2505 if (!may_trap_p (x))
2507 /* A load with 1 base register, to be further checked. */
2508 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
2509 return PFREE_CANDIDATE;
2510 /* No info on the load, to be further checked. */
2511 return PRISKY_CANDIDATE;
2516 int i, insn_class = TRAP_FREE;
2518 /* Neither store nor load, check if it may cause a trap. */
2521 /* Recursive step: walk the insn... */
2522 fmt = GET_RTX_FORMAT (code);
2523 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2527 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
2528 insn_class = WORST_CLASS (insn_class, tmp_class);
2530 else if (fmt[i] == 'E')
2533 for (j = 0; j < XVECLEN (x, i); j++)
2535 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
2536 insn_class = WORST_CLASS (insn_class, tmp_class);
2537 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2541 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2546 } /* may_trap_exp */
2549 /* Classifies insn for the purpose of verifying that it can be
2550 moved speculatively, by examining it's patterns, returning:
2551 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2552 TRAP_FREE: non-load insn.
2553 IFREE: load from a globaly safe location.
2554 IRISKY: volatile load.
2555 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2556 being either PFREE or PRISKY. */
2559 haifa_classify_insn (insn)
2562 rtx pat = PATTERN (insn);
2563 int tmp_class = TRAP_FREE;
2564 int insn_class = TRAP_FREE;
2567 if (GET_CODE (pat) == PARALLEL)
2569 int i, len = XVECLEN (pat, 0);
2571 for (i = len - 1; i >= 0; i--)
2573 code = GET_CODE (XVECEXP (pat, 0, i));
2577 /* Test if it is a 'store'. */
2578 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
2581 /* Test if it is a store. */
2582 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
2583 if (tmp_class == TRAP_RISKY)
2585 /* Test if it is a load. */
2587 WORST_CLASS (tmp_class,
2588 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 0));
2591 tmp_class = TRAP_RISKY;
2595 insn_class = WORST_CLASS (insn_class, tmp_class);
2596 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2602 code = GET_CODE (pat);
2606 /* Test if it is a 'store'. */
2607 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
2610 /* Test if it is a store. */
2611 tmp_class = may_trap_exp (SET_DEST (pat), 1);
2612 if (tmp_class == TRAP_RISKY)
2614 /* Test if it is a load. */
2616 WORST_CLASS (tmp_class,
2617 may_trap_exp (SET_SRC (pat), 0));
2620 tmp_class = TRAP_RISKY;
2624 insn_class = tmp_class;
2629 } /* haifa_classify_insn */
2631 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2632 a load moved speculatively, or if load_insn is protected by
2633 a compare on load_insn's address). */
2636 is_prisky (load_insn, bb_src, bb_trg)
2640 if (FED_BY_SPEC_LOAD (load_insn))
2643 if (LOG_LINKS (load_insn) == NULL)
2644 /* Dependence may 'hide' out of the region. */
2647 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2653 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2654 Return 1 if insn is exception-free (and the motion is valid)
2658 is_exception_free (insn, bb_src, bb_trg)
2662 int insn_class = haifa_classify_insn (insn);
2664 /* Handle non-load insns. */
2675 if (!flag_schedule_speculative_load)
2677 IS_LOAD_INSN (insn) = 1;
2684 case PFREE_CANDIDATE:
2685 if (is_pfree (insn, bb_src, bb_trg))
2687 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2688 case PRISKY_CANDIDATE:
2689 if (!flag_schedule_speculative_load_dangerous
2690 || is_prisky (insn, bb_src, bb_trg))
2696 return flag_schedule_speculative_load_dangerous;
2697 } /* is_exception_free */
2700 /* Process an insn's memory dependencies. There are four kinds of
2703 (0) read dependence: read follows read
2704 (1) true dependence: read follows write
2705 (2) anti dependence: write follows read
2706 (3) output dependence: write follows write
2708 We are careful to build only dependencies which actually exist, and
2709 use transitivity to avoid building too many links. */
2711 /* Return the INSN_LIST containing INSN in LIST, or NULL
2712 if LIST does not contain INSN. */
2714 HAIFA_INLINE static rtx
2715 find_insn_list (insn, list)
2721 if (XEXP (list, 0) == insn)
2723 list = XEXP (list, 1);
2729 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0
2732 HAIFA_INLINE static char
2733 find_insn_mem_list (insn, x, list, list1)
2739 if (XEXP (list, 0) == insn
2740 && XEXP (list1, 0) == x)
2742 list = XEXP (list, 1);
2743 list1 = XEXP (list1, 1);
2749 /* Compute the function units used by INSN. This caches the value
2750 returned by function_units_used. A function unit is encoded as the
2751 unit number if the value is non-negative and the compliment of a
2752 mask if the value is negative. A function unit index is the
2753 non-negative encoding. */
2755 HAIFA_INLINE static int
2759 register int unit = INSN_UNIT (insn);
2763 recog_memoized (insn);
2765 /* A USE insn, or something else we don't need to understand.
2766 We can't pass these directly to function_units_used because it will
2767 trigger a fatal error for unrecognizable insns. */
2768 if (INSN_CODE (insn) < 0)
2772 unit = function_units_used (insn);
2773 /* Increment non-negative values so we can cache zero. */
2777 /* We only cache 16 bits of the result, so if the value is out of
2778 range, don't cache it. */
2779 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
2781 || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
2782 INSN_UNIT (insn) = unit;
2784 return (unit > 0 ? unit - 1 : unit);
2787 /* Compute the blockage range for executing INSN on UNIT. This caches
2788 the value returned by the blockage_range_function for the unit.
2789 These values are encoded in an int where the upper half gives the
2790 minimum value and the lower half gives the maximum value. */
2792 HAIFA_INLINE static unsigned int
2793 blockage_range (unit, insn)
2797 unsigned int blockage = INSN_BLOCKAGE (insn);
2800 if ((int) UNIT_BLOCKED (blockage) != unit + 1)
2802 range = function_units[unit].blockage_range_function (insn);
2803 /* We only cache the blockage range for one unit and then only if
2805 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
2806 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
2809 range = BLOCKAGE_RANGE (blockage);
2814 /* A vector indexed by function unit instance giving the last insn to use
2815 the unit. The value of the function unit instance index for unit U
2816 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2817 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2819 /* A vector indexed by function unit instance giving the minimum time when
2820 the unit will unblock based on the maximum blockage cost. */
2821 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2823 /* A vector indexed by function unit number giving the number of insns
2824 that remain to use the unit. */
2825 static int unit_n_insns[FUNCTION_UNITS_SIZE];
2827 /* Reset the function unit state to the null state. */
2832 bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
2833 bzero ((char *) unit_tick, sizeof (unit_tick));
2834 bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
2837 /* Return the issue-delay of an insn. */
2839 HAIFA_INLINE static int
2840 insn_issue_delay (insn)
2844 int unit = insn_unit (insn);
2846 /* Efficiency note: in fact, we are working 'hard' to compute a
2847 value that was available in md file, and is not available in
2848 function_units[] structure. It would be nice to have this
2849 value there, too. */
2852 if (function_units[unit].blockage_range_function &&
2853 function_units[unit].blockage_function)
2854 delay = function_units[unit].blockage_function (insn, insn);
2857 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2858 if ((unit & 1) != 0 && function_units[i].blockage_range_function
2859 && function_units[i].blockage_function)
2860 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
2865 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2866 instance INSTANCE at time CLOCK if the previous actual hazard cost
2869 HAIFA_INLINE static int
2870 actual_hazard_this_instance (unit, instance, insn, clock, cost)
2871 int unit, instance, clock, cost;
2874 int tick = unit_tick[instance]; /* Issue time of the last issued insn. */
2876 if (tick - clock > cost)
2878 /* The scheduler is operating forward, so unit's last insn is the
2879 executing insn and INSN is the candidate insn. We want a
2880 more exact measure of the blockage if we execute INSN at CLOCK
2881 given when we committed the execution of the unit's last insn.
2883 The blockage value is given by either the unit's max blockage
2884 constant, blockage range function, or blockage function. Use
2885 the most exact form for the given unit. */
2887 if (function_units[unit].blockage_range_function)
2889 if (function_units[unit].blockage_function)
2890 tick += (function_units[unit].blockage_function
2891 (unit_last_insn[instance], insn)
2892 - function_units[unit].max_blockage);
2894 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
2895 - function_units[unit].max_blockage);
2897 if (tick - clock > cost)
2898 cost = tick - clock;
2903 /* Record INSN as having begun execution on the units encoded by UNIT at
2906 HAIFA_INLINE static void
2907 schedule_unit (unit, insn, clock)
2915 int instance = unit;
2916 #if MAX_MULTIPLICITY > 1
2917 /* Find the first free instance of the function unit and use that
2918 one. We assume that one is free. */
2919 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2921 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
2923 instance += FUNCTION_UNITS_SIZE;
2926 unit_last_insn[instance] = insn;
2927 unit_tick[instance] = (clock + function_units[unit].max_blockage);
2930 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2931 if ((unit & 1) != 0)
2932 schedule_unit (i, insn, clock);
2935 /* Return the actual hazard cost of executing INSN on the units encoded by
2936 UNIT at time CLOCK if the previous actual hazard cost was COST. */
2938 HAIFA_INLINE static int
2939 actual_hazard (unit, insn, clock, cost)
2940 int unit, clock, cost;
2947 /* Find the instance of the function unit with the minimum hazard. */
2948 int instance = unit;
2949 int best_cost = actual_hazard_this_instance (unit, instance, insn,
2951 #if MAX_MULTIPLICITY > 1
2954 if (best_cost > cost)
2956 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2958 instance += FUNCTION_UNITS_SIZE;
2959 this_cost = actual_hazard_this_instance (unit, instance, insn,
2961 if (this_cost < best_cost)
2963 best_cost = this_cost;
2964 if (this_cost <= cost)
2970 cost = MAX (cost, best_cost);
2973 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2974 if ((unit & 1) != 0)
2975 cost = actual_hazard (i, insn, clock, cost);
2980 /* Return the potential hazard cost of executing an instruction on the
2981 units encoded by UNIT if the previous potential hazard cost was COST.
2982 An insn with a large blockage time is chosen in preference to one
2983 with a smaller time; an insn that uses a unit that is more likely
2984 to be used is chosen in preference to one with a unit that is less
2985 used. We are trying to minimize a subsequent actual hazard. */
2987 HAIFA_INLINE static int
2988 potential_hazard (unit, insn, cost)
2993 unsigned int minb, maxb;
2997 minb = maxb = function_units[unit].max_blockage;
3000 if (function_units[unit].blockage_range_function)
3002 maxb = minb = blockage_range (unit, insn);
3003 maxb = MAX_BLOCKAGE_COST (maxb);
3004 minb = MIN_BLOCKAGE_COST (minb);
3009 /* Make the number of instructions left dominate. Make the
3010 minimum delay dominate the maximum delay. If all these
3011 are the same, use the unit number to add an arbitrary
3012 ordering. Other terms can be added. */
3013 ncost = minb * 0x40 + maxb;
3014 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
3021 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3022 if ((unit & 1) != 0)
3023 cost = potential_hazard (i, insn, cost);
3028 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3029 This is the number of cycles between instruction issue and
3030 instruction results. */
3032 HAIFA_INLINE static int
3033 insn_cost (insn, link, used)
3034 rtx insn, link, used;
3036 register int cost = INSN_COST (insn);
3040 recog_memoized (insn);
3042 /* A USE insn, or something else we don't need to understand.
3043 We can't pass these directly to result_ready_cost because it will
3044 trigger a fatal error for unrecognizable insns. */
3045 if (INSN_CODE (insn) < 0)
3047 INSN_COST (insn) = 1;
3052 cost = result_ready_cost (insn);
3057 INSN_COST (insn) = cost;
3061 /* In this case estimate cost without caring how insn is used. */
3062 if (link == 0 && used == 0)
3065 /* A USE insn should never require the value used to be computed. This
3066 allows the computation of a function's result and parameter values to
3067 overlap the return and call. */
3068 recog_memoized (used);
3069 if (INSN_CODE (used) < 0)
3070 LINK_COST_FREE (link) = 1;
3072 /* If some dependencies vary the cost, compute the adjustment. Most
3073 commonly, the adjustment is complete: either the cost is ignored
3074 (in the case of an output- or anti-dependence), or the cost is
3075 unchanged. These values are cached in the link as LINK_COST_FREE
3076 and LINK_COST_ZERO. */
3078 if (LINK_COST_FREE (link))
3081 else if (!LINK_COST_ZERO (link))
3085 ADJUST_COST (used, link, insn, ncost);
3088 LINK_COST_FREE (link) = 1;
3092 LINK_COST_ZERO (link) = 1;
3099 /* Compute the priority number for INSN. */
3108 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
3111 if ((this_priority = INSN_PRIORITY (insn)) == 0)
3113 if (INSN_DEPEND (insn) == 0)
3114 this_priority = insn_cost (insn, 0, 0);
3116 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
3121 if (RTX_INTEGRATED_P (link))
3124 next = XEXP (link, 0);
3126 /* Critical path is meaningful in block boundaries only. */
3127 if (BLOCK_NUM (next) != BLOCK_NUM (insn))
3130 next_priority = insn_cost (insn, link, next) + priority (next);
3131 if (next_priority > this_priority)
3132 this_priority = next_priority;
3134 INSN_PRIORITY (insn) = this_priority;
3136 return this_priority;
3140 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3141 them to the unused_*_list variables, so that they can be reused. */
3144 free_pending_lists ()
3148 for (bb = 0; bb < current_nr_blocks; bb++)
3150 free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
3151 free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
3152 free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
3153 free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
3157 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3158 The MEM is a memory reference contained within INSN, which we are saving
3159 so that we can do memory aliasing on it. */
3162 add_insn_mem_dependence (deps, insn_list, mem_list, insn, mem)
3164 rtx *insn_list, *mem_list, insn, mem;
3168 link = alloc_INSN_LIST (insn, *insn_list);
3171 link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
3174 deps->pending_lists_length++;
3177 /* Make a dependency between every memory reference on the pending lists
3178 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3182 flush_pending_lists (deps, insn, only_write)
3190 while (deps->pending_read_insns && ! only_write)
3192 add_dependence (insn, XEXP (deps->pending_read_insns, 0),
3195 link = deps->pending_read_insns;
3196 deps->pending_read_insns = XEXP (deps->pending_read_insns, 1);
3197 free_INSN_LIST_node (link);
3199 link = deps->pending_read_mems;
3200 deps->pending_read_mems = XEXP (deps->pending_read_mems, 1);
3201 free_EXPR_LIST_node (link);
3203 while (deps->pending_write_insns)
3205 add_dependence (insn, XEXP (deps->pending_write_insns, 0),
3208 link = deps->pending_write_insns;
3209 deps->pending_write_insns = XEXP (deps->pending_write_insns, 1);
3210 free_INSN_LIST_node (link);
3212 link = deps->pending_write_mems;
3213 deps->pending_write_mems = XEXP (deps->pending_write_mems, 1);
3214 free_EXPR_LIST_node (link);
3216 deps->pending_lists_length = 0;
3218 /* last_pending_memory_flush is now a list of insns. */
3219 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
3220 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3222 free_INSN_LIST_list (&deps->last_pending_memory_flush);
3223 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
3226 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
3227 rtx, X, creating all dependencies generated by the write to the
3228 destination of X, and reads of everything mentioned. */
3231 sched_analyze_1 (deps, x, insn)
3237 register rtx dest = XEXP (x, 0);
3238 enum rtx_code code = GET_CODE (x);
3243 if (GET_CODE (dest) == PARALLEL
3244 && GET_MODE (dest) == BLKmode)
3247 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
3248 sched_analyze_1 (deps, XVECEXP (dest, 0, i), insn);
3249 if (GET_CODE (x) == SET)
3250 sched_analyze_2 (deps, SET_SRC (x), insn);
3254 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3255 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3257 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3259 /* The second and third arguments are values read by this insn. */
3260 sched_analyze_2 (deps, XEXP (dest, 1), insn);
3261 sched_analyze_2 (deps, XEXP (dest, 2), insn);
3263 dest = XEXP (dest, 0);
3266 if (GET_CODE (dest) == REG)
3270 regno = REGNO (dest);
3272 /* A hard reg in a wide mode may really be multiple registers.
3273 If so, mark all of them just like the first. */
3274 if (regno < FIRST_PSEUDO_REGISTER)
3276 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
3282 for (u = deps->reg_last_uses[r]; u; u = XEXP (u, 1))
3283 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3285 for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
3286 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3288 /* Clobbers need not be ordered with respect to one
3289 another, but sets must be ordered with respect to a
3293 free_INSN_LIST_list (&deps->reg_last_uses[r]);
3294 for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
3295 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3296 SET_REGNO_REG_SET (reg_pending_sets, r);
3299 SET_REGNO_REG_SET (reg_pending_clobbers, r);
3301 /* Function calls clobber all call_used regs. */
3302 if (global_regs[r] || (code == SET && call_used_regs[r]))
3303 for (u = deps->last_function_call; u; u = XEXP (u, 1))
3304 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3311 for (u = deps->reg_last_uses[regno]; u; u = XEXP (u, 1))
3312 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3314 for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
3315 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3319 free_INSN_LIST_list (&deps->reg_last_uses[regno]);
3320 for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3321 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3322 SET_REGNO_REG_SET (reg_pending_sets, regno);
3325 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
3327 /* Pseudos that are REG_EQUIV to something may be replaced
3328 by that during reloading. We need only add dependencies for
3329 the address in the REG_EQUIV note. */
3330 if (!reload_completed
3331 && reg_known_equiv_p[regno]
3332 && GET_CODE (reg_known_value[regno]) == MEM)
3333 sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
3335 /* Don't let it cross a call after scheduling if it doesn't
3336 already cross one. */
3338 if (REG_N_CALLS_CROSSED (regno) == 0)
3339 for (u = deps->last_function_call; u; u = XEXP (u, 1))
3340 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3343 else if (GET_CODE (dest) == MEM)
3345 /* Writing memory. */
3347 if (deps->pending_lists_length > 32)
3349 /* Flush all pending reads and writes to prevent the pending lists
3350 from getting any larger. Insn scheduling runs too slowly when
3351 these lists get long. The number 32 was chosen because it
3352 seems like a reasonable number. When compiling GCC with itself,
3353 this flush occurs 8 times for sparc, and 10 times for m88k using
3355 flush_pending_lists (deps, insn, 0);
3360 rtx pending, pending_mem;
3362 pending = deps->pending_read_insns;
3363 pending_mem = deps->pending_read_mems;
3366 if (anti_dependence (XEXP (pending_mem, 0), dest))
3367 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3369 pending = XEXP (pending, 1);
3370 pending_mem = XEXP (pending_mem, 1);
3373 pending = deps->pending_write_insns;
3374 pending_mem = deps->pending_write_mems;
3377 if (output_dependence (XEXP (pending_mem, 0), dest))
3378 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
3380 pending = XEXP (pending, 1);
3381 pending_mem = XEXP (pending_mem, 1);
3384 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
3385 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3387 add_insn_mem_dependence (deps, &deps->pending_write_insns,
3388 &deps->pending_write_mems, insn, dest);
3390 sched_analyze_2 (deps, XEXP (dest, 0), insn);
3393 /* Analyze reads. */
3394 if (GET_CODE (x) == SET)
3395 sched_analyze_2 (deps, SET_SRC (x), insn);
3398 /* Analyze the uses of memory and registers in rtx X in INSN. */
3401 sched_analyze_2 (deps, x, insn)
3408 register enum rtx_code code;
3409 register const char *fmt;
3414 code = GET_CODE (x);
3423 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3424 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3425 this does not mean that this insn is using cc0. */
3433 /* User of CC0 depends on immediately preceding insn. */
3434 SCHED_GROUP_P (insn) = 1;
3436 /* There may be a note before this insn now, but all notes will
3437 be removed before we actually try to schedule the insns, so
3438 it won't cause a problem later. We must avoid it here though. */
3439 prev = prev_nonnote_insn (insn);
3441 /* Make a copy of all dependencies on the immediately previous insn,
3442 and add to this insn. This is so that all the dependencies will
3443 apply to the group. Remove an explicit dependence on this insn
3444 as SCHED_GROUP_P now represents it. */
3446 if (find_insn_list (prev, LOG_LINKS (insn)))
3447 remove_dependence (insn, prev);
3449 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
3450 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3459 int regno = REGNO (x);
3460 if (regno < FIRST_PSEUDO_REGISTER)
3464 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
3468 deps->reg_last_uses[r]
3469 = alloc_INSN_LIST (insn, deps->reg_last_uses[r]);
3471 for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
3472 add_dependence (insn, XEXP (u, 0), 0);
3474 /* ??? This should never happen. */
3475 for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
3476 add_dependence (insn, XEXP (u, 0), 0);
3478 if (call_used_regs[r] || global_regs[r])
3479 /* Function calls clobber all call_used regs. */
3480 for (u = deps->last_function_call; u; u = XEXP (u, 1))
3481 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3486 deps->reg_last_uses[regno]
3487 = alloc_INSN_LIST (insn, deps->reg_last_uses[regno]);
3489 for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
3490 add_dependence (insn, XEXP (u, 0), 0);
3492 /* ??? This should never happen. */
3493 for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3494 add_dependence (insn, XEXP (u, 0), 0);
3496 /* Pseudos that are REG_EQUIV to something may be replaced
3497 by that during reloading. We need only add dependencies for
3498 the address in the REG_EQUIV note. */
3499 if (!reload_completed
3500 && reg_known_equiv_p[regno]
3501 && GET_CODE (reg_known_value[regno]) == MEM)
3502 sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
3504 /* If the register does not already cross any calls, then add this
3505 insn to the sched_before_next_call list so that it will still
3506 not cross calls after scheduling. */
3507 if (REG_N_CALLS_CROSSED (regno) == 0)
3508 add_dependence (deps->sched_before_next_call, insn,
3516 /* Reading memory. */
3518 rtx pending, pending_mem;
3520 pending = deps->pending_read_insns;
3521 pending_mem = deps->pending_read_mems;
3524 if (read_dependence (XEXP (pending_mem, 0), x))
3525 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3527 pending = XEXP (pending, 1);
3528 pending_mem = XEXP (pending_mem, 1);
3531 pending = deps->pending_write_insns;
3532 pending_mem = deps->pending_write_mems;
3535 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
3537 add_dependence (insn, XEXP (pending, 0), 0);
3539 pending = XEXP (pending, 1);
3540 pending_mem = XEXP (pending_mem, 1);
3543 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
3544 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3546 /* Always add these dependencies to pending_reads, since
3547 this insn may be followed by a write. */
3548 add_insn_mem_dependence (deps, &deps->pending_read_insns,
3549 &deps->pending_read_mems, insn, x);
3551 /* Take advantage of tail recursion here. */
3552 sched_analyze_2 (deps, XEXP (x, 0), insn);
3556 /* Force pending stores to memory in case a trap handler needs them. */
3558 flush_pending_lists (deps, insn, 1);
3563 case UNSPEC_VOLATILE:
3567 /* Traditional and volatile asm instructions must be considered to use
3568 and clobber all hard registers, all pseudo-registers and all of
3569 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3571 Consider for instance a volatile asm that changes the fpu rounding
3572 mode. An insn should not be moved across this even if it only uses
3573 pseudo-regs because it might give an incorrectly rounded result. */
3574 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
3576 int max_reg = max_reg_num ();
3577 for (i = 0; i < max_reg; i++)
3579 for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
3580 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3581 free_INSN_LIST_list (&deps->reg_last_uses[i]);
3583 for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
3584 add_dependence (insn, XEXP (u, 0), 0);
3586 for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
3587 add_dependence (insn, XEXP (u, 0), 0);
3589 reg_pending_sets_all = 1;
3591 flush_pending_lists (deps, insn, 0);
3594 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3595 We can not just fall through here since then we would be confused
3596 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3597 traditional asms unlike their normal usage. */
3599 if (code == ASM_OPERANDS)
3601 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3602 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
3612 /* These both read and modify the result. We must handle them as writes
3613 to get proper dependencies for following instructions. We must handle
3614 them as reads to get proper dependencies from this to previous
3615 instructions. Thus we need to pass them to both sched_analyze_1
3616 and sched_analyze_2. We must call sched_analyze_2 first in order
3617 to get the proper antecedent for the read. */
3618 sched_analyze_2 (deps, XEXP (x, 0), insn);
3619 sched_analyze_1 (deps, x, insn);
3626 /* Other cases: walk the insn. */
3627 fmt = GET_RTX_FORMAT (code);
3628 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3631 sched_analyze_2 (deps, XEXP (x, i), insn);
3632 else if (fmt[i] == 'E')
3633 for (j = 0; j < XVECLEN (x, i); j++)
3634 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
3638 /* Analyze an INSN with pattern X to find all dependencies. */
3641 sched_analyze_insn (deps, x, insn, loop_notes)
3646 register RTX_CODE code = GET_CODE (x);
3648 int maxreg = max_reg_num ();
3651 if (code == SET || code == CLOBBER)
3652 sched_analyze_1 (deps, x, insn);
3653 else if (code == PARALLEL)
3656 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3658 code = GET_CODE (XVECEXP (x, 0, i));
3659 if (code == SET || code == CLOBBER)
3660 sched_analyze_1 (deps, XVECEXP (x, 0, i), insn);
3662 sched_analyze_2 (deps, XVECEXP (x, 0, i), insn);
3666 sched_analyze_2 (deps, x, insn);
3668 /* Mark registers CLOBBERED or used by called function. */
3669 if (GET_CODE (insn) == CALL_INSN)
3670 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3672 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3673 sched_analyze_1 (deps, XEXP (link, 0), insn);
3675 sched_analyze_2 (deps, XEXP (link, 0), insn);
3678 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3679 block, then we must be sure that no instructions are scheduled across it.
3680 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3681 become incorrect. */
3685 int max_reg = max_reg_num ();
3686 int schedule_barrier_found = 0;
3689 /* Update loop_notes with any notes from this insn. Also determine
3690 if any of the notes on the list correspond to instruction scheduling
3691 barriers (loop, eh & setjmp notes, but not range notes. */
3693 while (XEXP (link, 1))
3695 if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
3696 || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
3697 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
3698 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END
3699 || INTVAL (XEXP (link, 0)) == NOTE_INSN_SETJMP)
3700 schedule_barrier_found = 1;
3702 link = XEXP (link, 1);
3704 XEXP (link, 1) = REG_NOTES (insn);
3705 REG_NOTES (insn) = loop_notes;
3707 /* Add dependencies if a scheduling barrier was found. */
3708 if (schedule_barrier_found)
3710 for (i = 0; i < max_reg; i++)
3713 for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
3714 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3715 free_INSN_LIST_list (&deps->reg_last_uses[i]);
3717 for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
3718 add_dependence (insn, XEXP (u, 0), 0);
3720 for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
3721 add_dependence (insn, XEXP (u, 0), 0);
3723 reg_pending_sets_all = 1;
3725 flush_pending_lists (deps, insn, 0);
3730 /* Accumulate clobbers until the next set so that it will be output dependent
3731 on all of them. At the next set we can clear the clobber list, since
3732 subsequent sets will be output dependent on it. */
3733 EXECUTE_IF_SET_IN_REG_SET
3734 (reg_pending_sets, 0, i,
3736 free_INSN_LIST_list (&deps->reg_last_sets[i]);
3737 free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
3738 deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3740 EXECUTE_IF_SET_IN_REG_SET
3741 (reg_pending_clobbers, 0, i,
3743 deps->reg_last_clobbers[i]
3744 = alloc_INSN_LIST (insn, deps->reg_last_clobbers[i]);
3746 CLEAR_REG_SET (reg_pending_sets);
3747 CLEAR_REG_SET (reg_pending_clobbers);
3749 if (reg_pending_sets_all)
3751 for (i = 0; i < maxreg; i++)
3753 free_INSN_LIST_list (&deps->reg_last_sets[i]);
3754 free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
3755 deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3758 reg_pending_sets_all = 0;
3761 /* Handle function calls and function returns created by the epilogue
3763 if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
3768 /* When scheduling instructions, we make sure calls don't lose their
3769 accompanying USE insns by depending them one on another in order.
3771 Also, we must do the same thing for returns created by the epilogue
3772 threading code. Note this code works only in this special case,
3773 because other passes make no guarantee that they will never emit
3774 an instruction between a USE and a RETURN. There is such a guarantee
3775 for USE instructions immediately before a call. */
3777 prev_dep_insn = insn;
3778 dep_insn = PREV_INSN (insn);
3779 while (GET_CODE (dep_insn) == INSN
3780 && GET_CODE (PATTERN (dep_insn)) == USE
3781 && GET_CODE (XEXP (PATTERN (dep_insn), 0)) == REG)
3783 SCHED_GROUP_P (prev_dep_insn) = 1;
3785 /* Make a copy of all dependencies on dep_insn, and add to insn.
3786 This is so that all of the dependencies will apply to the
3789 for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
3790 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3792 prev_dep_insn = dep_insn;
3793 dep_insn = PREV_INSN (dep_insn);
3798 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3799 for every dependency. */
3802 sched_analyze (deps, head, tail)
3810 for (insn = head;; insn = NEXT_INSN (insn))
3812 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
3814 /* Clear out the stale LOG_LINKS from flow. */
3815 free_INSN_LIST_list (&LOG_LINKS (insn));
3817 /* Make each JUMP_INSN a scheduling barrier for memory
3819 if (GET_CODE (insn) == JUMP_INSN)
3820 deps->last_pending_memory_flush
3821 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
3822 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
3825 else if (GET_CODE (insn) == CALL_INSN)
3830 CANT_MOVE (insn) = 1;
3832 /* Clear out the stale LOG_LINKS from flow. */
3833 free_INSN_LIST_list (&LOG_LINKS (insn));
3835 /* Any instruction using a hard register which may get clobbered
3836 by a call needs to be marked as dependent on this call.
3837 This prevents a use of a hard return reg from being moved
3838 past a void call (i.e. it does not explicitly set the hard
3841 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3842 all registers, not just hard registers, may be clobbered by this
3845 /* Insn, being a CALL_INSN, magically depends on
3846 `last_function_call' already. */
3848 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
3849 && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
3851 int max_reg = max_reg_num ();
3852 for (i = 0; i < max_reg; i++)
3854 for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
3855 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3856 free_INSN_LIST_list (&deps->reg_last_uses[i]);
3858 for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
3859 add_dependence (insn, XEXP (u, 0), 0);
3861 for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
3862 add_dependence (insn, XEXP (u, 0), 0);
3864 reg_pending_sets_all = 1;
3866 /* Add a pair of REG_SAVE_NOTEs which we will later
3867 convert back into a NOTE_INSN_SETJMP note. See
3868 reemit_notes for why we use a pair of NOTEs. */
3869 REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE,
3872 REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE,
3873 GEN_INT (NOTE_INSN_SETJMP),
3878 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3879 if (call_used_regs[i] || global_regs[i])
3881 for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
3882 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3884 for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
3885 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3887 SET_REGNO_REG_SET (reg_pending_clobbers, i);
3891 /* For each insn which shouldn't cross a call, add a dependence
3892 between that insn and this call insn. */
3893 x = LOG_LINKS (deps->sched_before_next_call);
3896 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
3899 free_INSN_LIST_list (&LOG_LINKS (deps->sched_before_next_call));
3901 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
3904 /* In the absence of interprocedural alias analysis, we must flush
3905 all pending reads and writes, and start new dependencies starting
3906 from here. But only flush writes for constant calls (which may
3907 be passed a pointer to something we haven't written yet). */
3908 flush_pending_lists (deps, insn, CONST_CALL_P (insn));
3910 /* Depend this function call (actually, the user of this
3911 function call) on all hard register clobberage. */
3913 /* last_function_call is now a list of insns. */
3914 free_INSN_LIST_list (&deps->last_function_call);
3915 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3918 /* See comments on reemit_notes as to why we do this.
3919 ??? Actually, the reemit_notes just say what is done, not why. */
3921 else if (GET_CODE (insn) == NOTE
3922 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_START
3923 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END))
3925 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn),
3927 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
3928 GEN_INT (NOTE_LINE_NUMBER (insn)),
3931 else if (GET_CODE (insn) == NOTE
3932 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
3933 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
3934 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
3935 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
3936 || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
3937 && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
3941 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
3942 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
3943 rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
3945 rtx_region = GEN_INT (0);
3947 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
3950 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
3951 GEN_INT (NOTE_LINE_NUMBER (insn)),
3953 CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
3962 /* Macros and functions for keeping the priority queue sorted, and
3963 dealing with queueing and dequeueing of instructions. */
3965 #define SCHED_SORT(READY, N_READY) \
3966 do { if ((N_READY) == 2) \
3967 swap_sort (READY, N_READY); \
3968 else if ((N_READY) > 2) \
3969 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
3972 /* Returns a positive value if x is preferred; returns a negative value if
3973 y is preferred. Should never return 0, since that will make the sort
3977 rank_for_schedule (x, y)
3981 rtx tmp = *(rtx *)y;
3982 rtx tmp2 = *(rtx *)x;
3984 int tmp_class, tmp2_class, depend_count1, depend_count2;
3985 int val, priority_val, spec_val, prob_val, weight_val;
3988 /* Prefer insn with higher priority. */
3989 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
3991 return priority_val;
3993 /* Prefer an insn with smaller contribution to registers-pressure. */
3994 if (!reload_completed &&
3995 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
3996 return (weight_val);
3998 /* Some comparison make sense in interblock scheduling only. */
3999 if (INSN_BB (tmp) != INSN_BB (tmp2))
4001 /* Prefer an inblock motion on an interblock motion. */
4002 if ((INSN_BB (tmp2) == target_bb) && (INSN_BB (tmp) != target_bb))
4004 if ((INSN_BB (tmp) == target_bb) && (INSN_BB (tmp2) != target_bb))
4007 /* Prefer a useful motion on a speculative one. */
4008 if ((spec_val = IS_SPECULATIVE_INSN (tmp) - IS_SPECULATIVE_INSN (tmp2)))
4011 /* Prefer a more probable (speculative) insn. */
4012 prob_val = INSN_PROBABILITY (tmp2) - INSN_PROBABILITY (tmp);
4017 /* Compare insns based on their relation to the last-scheduled-insn. */
4018 if (last_scheduled_insn)
4020 /* Classify the instructions into three classes:
4021 1) Data dependent on last schedule insn.
4022 2) Anti/Output dependent on last scheduled insn.
4023 3) Independent of last scheduled insn, or has latency of one.
4024 Choose the insn from the highest numbered class if different. */
4025 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
4026 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
4028 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4033 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
4034 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
4036 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4041 if ((val = tmp2_class - tmp_class))
4045 /* Prefer the insn which has more later insns that depend on it.
4046 This gives the scheduler more freedom when scheduling later
4047 instructions at the expense of added register pressure. */
4049 for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
4053 for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
4056 val = depend_count2 - depend_count1;
4060 /* If insns are equally good, sort by INSN_LUID (original insn order),
4061 so that we make the sort stable. This minimizes instruction movement,
4062 thus minimizing sched's effect on debugging and cross-jumping. */
4063 return INSN_LUID (tmp) - INSN_LUID (tmp2);
4066 /* Resort the array A in which only element at index N may be out of order. */
4068 HAIFA_INLINE static void
4073 rtx insn = a[n - 1];
4076 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
4084 static int max_priority;
4086 /* Add INSN to the insn queue so that it can be executed at least
4087 N_CYCLES after the currently executing insn. Preserve insns
4088 chain for debugging purposes. */
4090 HAIFA_INLINE static void
4091 queue_insn (insn, n_cycles)
4095 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
4096 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
4097 insn_queue[next_q] = link;
4100 if (sched_verbose >= 2)
4102 fprintf (dump, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn));
4104 if (INSN_BB (insn) != target_bb)
4105 fprintf (dump, "(b%d) ", BLOCK_NUM (insn));
4107 fprintf (dump, "queued for %d cycles.\n", n_cycles);
4112 /* PREV is an insn that is ready to execute. Adjust its priority if that
4113 will help shorten or lengthen register lifetimes as appropriate. Also
4114 provide a hook for the target to tweek itself. */
4116 HAIFA_INLINE static void
4117 adjust_priority (prev)
4118 rtx prev ATTRIBUTE_UNUSED;
4120 /* ??? There used to be code here to try and estimate how an insn
4121 affected register lifetimes, but it did it by looking at REG_DEAD
4122 notes, which we removed in schedule_region. Nor did it try to
4123 take into account register pressure or anything useful like that.
4125 Revisit when we have a machine model to work with and not before. */
4127 #ifdef ADJUST_PRIORITY
4128 ADJUST_PRIORITY (prev);
4132 /* Clock at which the previous instruction was issued. */
4133 static int last_clock_var;
4135 /* INSN is the "currently executing insn". Launch each insn which was
4136 waiting on INSN. READY is a vector of insns which are ready to fire.
4137 N_READY is the number of elements in READY. CLOCK is the current
4141 schedule_insn (insn, ready, n_ready, clock)
4150 unit = insn_unit (insn);
4152 if (sched_verbose >= 2)
4154 fprintf (dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
4156 insn_print_units (insn);
4157 fprintf (dump, "\n");
4160 if (sched_verbose && unit == -1)
4161 visualize_no_unit (insn);
4163 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
4164 schedule_unit (unit, insn, clock);
4166 if (INSN_DEPEND (insn) == 0)
4169 /* This is used by the function adjust_priority above. */
4171 max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
4173 max_priority = INSN_PRIORITY (insn);
4175 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
4177 rtx next = XEXP (link, 0);
4178 int cost = insn_cost (insn, link, next);
4180 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
4182 if ((INSN_DEP_COUNT (next) -= 1) == 0)
4184 int effective_cost = INSN_TICK (next) - clock;
4186 /* For speculative insns, before inserting to ready/queue,
4187 check live, exception-free, and issue-delay. */
4188 if (INSN_BB (next) != target_bb
4189 && (!IS_VALID (INSN_BB (next))
4191 || (IS_SPECULATIVE_INSN (next)
4192 && (insn_issue_delay (next) > 3
4193 || !check_live (next, INSN_BB (next))
4194 || !is_exception_free (next, INSN_BB (next), target_bb)))))
4197 if (sched_verbose >= 2)
4199 fprintf (dump, ";;\t\tdependences resolved: insn %d ",
4202 if (current_nr_blocks > 1 && INSN_BB (next) != target_bb)
4203 fprintf (dump, "/b%d ", BLOCK_NUM (next));
4205 if (effective_cost < 1)
4206 fprintf (dump, "into ready\n");
4208 fprintf (dump, "into queue with cost=%d\n", effective_cost);
4211 /* Adjust the priority of NEXT and either put it on the ready
4212 list or queue it. */
4213 adjust_priority (next);
4214 if (effective_cost < 1)
4215 ready[n_ready++] = next;
4217 queue_insn (next, effective_cost);
4221 /* Annotate the instruction with issue information -- TImode
4222 indicates that the instruction is expected not to be able
4223 to issue on the same cycle as the previous insn. A machine
4224 may use this information to decide how the instruction should
4226 if (reload_completed && issue_rate > 1)
4228 PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
4229 last_clock_var = clock;
4235 /* Functions for handling of notes. */
4237 /* Delete notes beginning with INSN and put them in the chain
4238 of notes ended by NOTE_LIST.
4239 Returns the insn following the notes. */
4242 unlink_other_notes (insn, tail)
4245 rtx prev = PREV_INSN (insn);
4247 while (insn != tail && GET_CODE (insn) == NOTE)
4249 rtx next = NEXT_INSN (insn);
4250 /* Delete the note from its current position. */
4252 NEXT_INSN (prev) = next;
4254 PREV_INSN (next) = prev;
4256 /* See sched_analyze to see how these are handled. */
4257 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
4258 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
4259 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
4260 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_START
4261 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
4262 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
4263 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
4265 /* Insert the note at the end of the notes list. */
4266 PREV_INSN (insn) = note_list;
4268 NEXT_INSN (note_list) = insn;
4277 /* Delete line notes beginning with INSN. Record line-number notes so
4278 they can be reused. Returns the insn following the notes. */
4281 unlink_line_notes (insn, tail)
4284 rtx prev = PREV_INSN (insn);
4286 while (insn != tail && GET_CODE (insn) == NOTE)
4288 rtx next = NEXT_INSN (insn);
4290 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
4292 /* Delete the note from its current position. */
4294 NEXT_INSN (prev) = next;
4296 PREV_INSN (next) = prev;
4298 /* Record line-number notes so they can be reused. */
4299 LINE_NOTE (insn) = insn;
4309 /* Return the head and tail pointers of BB. */
4311 HAIFA_INLINE static void
4312 get_block_head_tail (b, headp, tailp)
4321 /* HEAD and TAIL delimit the basic block being scheduled. */
4322 head = BLOCK_HEAD (b);
4323 tail = BLOCK_END (b);
4325 /* Don't include any notes or labels at the beginning of the
4326 basic block, or notes at the ends of basic blocks. */
4327 while (head != tail)
4329 if (GET_CODE (head) == NOTE)
4330 head = NEXT_INSN (head);
4331 else if (GET_CODE (tail) == NOTE)
4332 tail = PREV_INSN (tail);
4333 else if (GET_CODE (head) == CODE_LABEL)
4334 head = NEXT_INSN (head);
4343 HAIFA_INLINE static void
4344 get_bb_head_tail (bb, headp, tailp)
4349 get_block_head_tail (BB_TO_BLOCK (bb), headp, tailp);
4352 /* Delete line notes from bb. Save them so they can be later restored
4353 (in restore_line_notes ()). */
4364 get_bb_head_tail (bb, &head, &tail);
4367 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4370 next_tail = NEXT_INSN (tail);
4371 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4375 /* Farm out notes, and maybe save them in NOTE_LIST.
4376 This is needed to keep the debugger from
4377 getting completely deranged. */
4378 if (GET_CODE (insn) == NOTE)
4381 insn = unlink_line_notes (insn, next_tail);
4387 if (insn == next_tail)
4393 /* Save line number notes for each insn in bb. */
4396 save_line_notes (bb)
4402 /* We must use the true line number for the first insn in the block
4403 that was computed and saved at the start of this pass. We can't
4404 use the current line number, because scheduling of the previous
4405 block may have changed the current line number. */
4407 rtx line = line_note_head[BB_TO_BLOCK (bb)];
4410 get_bb_head_tail (bb, &head, &tail);
4411 next_tail = NEXT_INSN (tail);
4413 for (insn = BLOCK_HEAD (BB_TO_BLOCK (bb));
4415 insn = NEXT_INSN (insn))
4416 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4419 LINE_NOTE (insn) = line;
4423 /* After bb was scheduled, insert line notes into the insns list. */
4426 restore_line_notes (bb)
4429 rtx line, note, prev, new;
4430 int added_notes = 0;
4432 rtx head, next_tail, insn;
4434 b = BB_TO_BLOCK (bb);
4436 head = BLOCK_HEAD (b);
4437 next_tail = NEXT_INSN (BLOCK_END (b));
4439 /* Determine the current line-number. We want to know the current
4440 line number of the first insn of the block here, in case it is
4441 different from the true line number that was saved earlier. If
4442 different, then we need a line number note before the first insn
4443 of this block. If it happens to be the same, then we don't want to
4444 emit another line number note here. */
4445 for (line = head; line; line = PREV_INSN (line))
4446 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4449 /* Walk the insns keeping track of the current line-number and inserting
4450 the line-number notes as needed. */
4451 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4452 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4454 /* This used to emit line number notes before every non-deleted note.
4455 However, this confuses a debugger, because line notes not separated
4456 by real instructions all end up at the same address. I can find no
4457 use for line number notes before other notes, so none are emitted. */
4458 else if (GET_CODE (insn) != NOTE
4459 && (note = LINE_NOTE (insn)) != 0
4462 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
4463 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
4466 prev = PREV_INSN (insn);
4467 if (LINE_NOTE (note))
4469 /* Re-use the original line-number note. */
4470 LINE_NOTE (note) = 0;
4471 PREV_INSN (note) = prev;
4472 NEXT_INSN (prev) = note;
4473 PREV_INSN (insn) = note;
4474 NEXT_INSN (note) = insn;
4479 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
4480 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
4481 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
4484 if (sched_verbose && added_notes)
4485 fprintf (dump, ";; added %d line-number notes\n", added_notes);
4488 /* After scheduling the function, delete redundant line notes from the
4492 rm_redundant_line_notes ()
4495 rtx insn = get_insns ();
4496 int active_insn = 0;
4499 /* Walk the insns deleting redundant line-number notes. Many of these
4500 are already present. The remainder tend to occur at basic
4501 block boundaries. */
4502 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4503 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4505 /* If there are no active insns following, INSN is redundant. */
4506 if (active_insn == 0)
4509 NOTE_SOURCE_FILE (insn) = 0;
4510 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4512 /* If the line number is unchanged, LINE is redundant. */
4514 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
4515 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
4518 NOTE_SOURCE_FILE (line) = 0;
4519 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
4526 else if (!((GET_CODE (insn) == NOTE
4527 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
4528 || (GET_CODE (insn) == INSN
4529 && (GET_CODE (PATTERN (insn)) == USE
4530 || GET_CODE (PATTERN (insn)) == CLOBBER))))
4533 if (sched_verbose && notes)
4534 fprintf (dump, ";; deleted %d line-number notes\n", notes);
4537 /* Delete notes between head and tail and put them in the chain
4538 of notes ended by NOTE_LIST. */
4541 rm_other_notes (head, tail)
4549 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4552 next_tail = NEXT_INSN (tail);
4553 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4557 /* Farm out notes, and maybe save them in NOTE_LIST.
4558 This is needed to keep the debugger from
4559 getting completely deranged. */
4560 if (GET_CODE (insn) == NOTE)
4564 insn = unlink_other_notes (insn, next_tail);
4570 if (insn == next_tail)
4576 /* Functions for computation of registers live/usage info. */
4578 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
4581 find_insn_reg_weight (b)
4584 rtx insn, next_tail, head, tail;
4586 get_block_head_tail (b, &head, &tail);
4587 next_tail = NEXT_INSN (tail);
4589 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4594 /* Handle register life information. */
4595 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
4598 /* Increment weight for each register born here. */
4600 if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
4601 && register_operand (SET_DEST (x), VOIDmode))
4603 else if (GET_CODE (x) == PARALLEL)
4606 for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
4608 x = XVECEXP (PATTERN (insn), 0, j);
4609 if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
4610 && register_operand (SET_DEST (x), VOIDmode))
4615 /* Decrement weight for each register that dies here. */
4616 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
4618 if (REG_NOTE_KIND (x) == REG_DEAD
4619 || REG_NOTE_KIND (x) == REG_UNUSED)
4623 INSN_REG_WEIGHT (insn) = reg_weight;
4627 /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
4628 static int clock_var;
4630 /* Move insns that became ready to fire from queue to ready list. */
4633 queue_to_ready (ready, n_ready)
4640 q_ptr = NEXT_Q (q_ptr);
4642 /* Add all pending insns that can be scheduled without stalls to the
4644 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
4647 insn = XEXP (link, 0);
4650 if (sched_verbose >= 2)
4651 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
4653 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
4654 fprintf (dump, "(b%d) ", BLOCK_NUM (insn));
4656 ready[n_ready++] = insn;
4657 if (sched_verbose >= 2)
4658 fprintf (dump, "moving to ready without stalls\n");
4660 insn_queue[q_ptr] = 0;
4662 /* If there are no ready insns, stall until one is ready and add all
4663 of the pending insns at that point to the ready list. */
4666 register int stalls;
4668 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
4670 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
4672 for (; link; link = XEXP (link, 1))
4674 insn = XEXP (link, 0);
4677 if (sched_verbose >= 2)
4678 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
4680 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
4681 fprintf (dump, "(b%d) ", BLOCK_NUM (insn));
4683 ready[n_ready++] = insn;
4684 if (sched_verbose >= 2)
4685 fprintf (dump, "moving to ready with %d stalls\n", stalls);
4687 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
4694 if (sched_verbose && stalls)
4695 visualize_stall_cycles (BB_TO_BLOCK (target_bb), stalls);
4696 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
4697 clock_var += stalls;
4702 /* Print the ready list for debugging purposes. Callable from debugger. */
4705 debug_ready_list (ready, n_ready)
4711 for (i = 0; i < n_ready; i++)
4713 fprintf (dump, " %d", INSN_UID (ready[i]));
4714 if (current_nr_blocks > 1 && INSN_BB (ready[i]) != target_bb)
4715 fprintf (dump, "/b%d", BLOCK_NUM (ready[i]));
4717 fprintf (dump, "\n");
4720 /* Print names of units on which insn can/should execute, for debugging. */
4723 insn_print_units (insn)
4727 int unit = insn_unit (insn);
4730 fprintf (dump, "none");
4732 fprintf (dump, "%s", function_units[unit].name);
4735 fprintf (dump, "[");
4736 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
4739 fprintf (dump, "%s", function_units[i].name);
4741 fprintf (dump, " ");
4743 fprintf (dump, "]");
4747 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
4748 of a basic block. If more lines are needed, table is splitted to two.
4749 n_visual_lines is the number of lines printed so far for a block.
4750 visual_tbl contains the block visualization info.
4751 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
4752 #define MAX_VISUAL_LINES 100
4757 rtx vis_no_unit[10];
4759 /* Finds units that are in use in this fuction. Required only
4760 for visualization. */
4763 init_target_units ()
4768 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4770 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
4773 unit = insn_unit (insn);
4776 target_units |= ~unit;
4778 target_units |= (1 << unit);
4782 /* Return the length of the visualization table. */
4785 get_visual_tbl_length ()
4791 /* Compute length of one field in line. */
4792 s = (char *) alloca (INSN_LEN + 6);
4793 sprintf (s, " %33s", "uname");
4796 /* Compute length of one line. */
4799 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
4800 if (function_units[unit].bitmask & target_units)
4801 for (i = 0; i < function_units[unit].multiplicity; i++)
4804 n += strlen ("\n") + 2;
4806 /* Compute length of visualization string. */
4807 return (MAX_VISUAL_LINES * n);
4810 /* Init block visualization debugging info. */
4813 init_block_visualization ()
4815 strcpy (visual_tbl, "");
4823 safe_concat (buf, cur, str)
4828 char *end = buf + BUF_LEN - 2; /* Leave room for null. */
4837 while (cur < end && (c = *str++) != '\0')
4844 /* This recognizes rtx, I classified as expressions. These are always
4845 represent some action on values or results of other expression, that
4846 may be stored in objects representing values. */
4849 print_exp (buf, x, verbose)
4857 const char *fun = (char *)0;
4862 for (i = 0; i < 4; i++)
4868 switch (GET_CODE (x))
4871 op[0] = XEXP (x, 0);
4872 if (GET_CODE (XEXP (x, 1)) == CONST_INT
4873 && INTVAL (XEXP (x, 1)) < 0)
4876 op[1] = GEN_INT (-INTVAL (XEXP (x, 1)));
4881 op[1] = XEXP (x, 1);
4885 op[0] = XEXP (x, 0);
4887 op[1] = XEXP (x, 1);
4891 op[0] = XEXP (x, 0);
4893 op[1] = XEXP (x, 1);
4897 op[0] = XEXP (x, 0);
4898 op[1] = XEXP (x, 1);
4902 op[0] = XEXP (x, 0);
4905 op[0] = XEXP (x, 0);
4907 op[1] = XEXP (x, 1);
4910 op[0] = XEXP (x, 0);
4912 op[1] = XEXP (x, 1);
4916 op[0] = XEXP (x, 0);
4917 op[1] = XEXP (x, 1);
4920 op[0] = XEXP (x, 0);
4922 op[1] = XEXP (x, 1);
4926 op[0] = XEXP (x, 0);
4927 op[1] = XEXP (x, 1);
4931 op[0] = XEXP (x, 0);
4932 op[1] = XEXP (x, 1);
4936 op[0] = XEXP (x, 0);
4937 op[1] = XEXP (x, 1);
4941 op[0] = XEXP (x, 0);
4942 op[1] = XEXP (x, 1);
4946 op[0] = XEXP (x, 0);
4947 op[1] = XEXP (x, 1);
4951 op[0] = XEXP (x, 0);
4954 op[0] = XEXP (x, 0);
4956 op[1] = XEXP (x, 1);
4959 op[0] = XEXP (x, 0);
4961 op[1] = XEXP (x, 1);
4964 op[0] = XEXP (x, 0);
4966 op[1] = XEXP (x, 1);
4969 op[0] = XEXP (x, 0);
4971 op[1] = XEXP (x, 1);
4974 op[0] = XEXP (x, 0);
4976 op[1] = XEXP (x, 1);
4979 op[0] = XEXP (x, 0);
4981 op[1] = XEXP (x, 1);
4984 op[0] = XEXP (x, 0);
4986 op[1] = XEXP (x, 1);
4989 op[0] = XEXP (x, 0);
4991 op[1] = XEXP (x, 1);
4995 op[0] = XEXP (x, 0);
4999 op[0] = XEXP (x, 0);
5003 op[0] = XEXP (x, 0);
5006 op[0] = XEXP (x, 0);
5008 op[1] = XEXP (x, 1);
5011 op[0] = XEXP (x, 0);
5013 op[1] = XEXP (x, 1);
5016 op[0] = XEXP (x, 0);
5018 op[1] = XEXP (x, 1);
5022 op[0] = XEXP (x, 0);
5023 op[1] = XEXP (x, 1);
5026 op[0] = XEXP (x, 0);
5028 op[1] = XEXP (x, 1);
5032 op[0] = XEXP (x, 0);
5033 op[1] = XEXP (x, 1);
5036 op[0] = XEXP (x, 0);
5038 op[1] = XEXP (x, 1);
5042 op[0] = XEXP (x, 0);
5043 op[1] = XEXP (x, 1);
5046 op[0] = XEXP (x, 0);
5048 op[1] = XEXP (x, 1);
5052 op[0] = XEXP (x, 0);
5053 op[1] = XEXP (x, 1);
5056 fun = (verbose) ? "sign_extract" : "sxt";
5057 op[0] = XEXP (x, 0);
5058 op[1] = XEXP (x, 1);
5059 op[2] = XEXP (x, 2);
5062 fun = (verbose) ? "zero_extract" : "zxt";
5063 op[0] = XEXP (x, 0);
5064 op[1] = XEXP (x, 1);
5065 op[2] = XEXP (x, 2);
5068 fun = (verbose) ? "sign_extend" : "sxn";
5069 op[0] = XEXP (x, 0);
5072 fun = (verbose) ? "zero_extend" : "zxn";
5073 op[0] = XEXP (x, 0);
5076 fun = (verbose) ? "float_extend" : "fxn";
5077 op[0] = XEXP (x, 0);
5080 fun = (verbose) ? "trunc" : "trn";
5081 op[0] = XEXP (x, 0);
5083 case FLOAT_TRUNCATE:
5084 fun = (verbose) ? "float_trunc" : "ftr";
5085 op[0] = XEXP (x, 0);
5088 fun = (verbose) ? "float" : "flt";
5089 op[0] = XEXP (x, 0);
5091 case UNSIGNED_FLOAT:
5092 fun = (verbose) ? "uns_float" : "ufl";
5093 op[0] = XEXP (x, 0);
5097 op[0] = XEXP (x, 0);
5100 fun = (verbose) ? "uns_fix" : "ufx";
5101 op[0] = XEXP (x, 0);
5105 op[0] = XEXP (x, 0);
5109 op[0] = XEXP (x, 0);
5112 op[0] = XEXP (x, 0);
5116 op[0] = XEXP (x, 0);
5121 op[0] = XEXP (x, 0);
5125 op[1] = XEXP (x, 1);
5130 op[0] = XEXP (x, 0);
5132 op[1] = XEXP (x, 1);
5134 op[2] = XEXP (x, 2);
5139 op[0] = TRAP_CONDITION (x);
5142 case UNSPEC_VOLATILE:
5144 cur = safe_concat (buf, cur, "unspec");
5145 if (GET_CODE (x) == UNSPEC_VOLATILE)
5146 cur = safe_concat (buf, cur, "/v");
5147 cur = safe_concat (buf, cur, "[");
5149 for (i = 0; i < XVECLEN (x, 0); i++)
5151 print_pattern (tmp, XVECEXP (x, 0, i), verbose);
5152 cur = safe_concat (buf, cur, sep);
5153 cur = safe_concat (buf, cur, tmp);
5156 cur = safe_concat (buf, cur, "] ");
5157 sprintf (tmp, "%d", XINT (x, 1));
5158 cur = safe_concat (buf, cur, tmp);
5162 /* If (verbose) debug_rtx (x); */
5163 st[0] = GET_RTX_NAME (GET_CODE (x));
5167 /* Print this as a function? */
5170 cur = safe_concat (buf, cur, fun);
5171 cur = safe_concat (buf, cur, "(");
5174 for (i = 0; i < 4; i++)
5177 cur = safe_concat (buf, cur, st[i]);
5182 cur = safe_concat (buf, cur, ",");
5184 print_value (tmp, op[i], verbose);
5185 cur = safe_concat (buf, cur, tmp);
5190 cur = safe_concat (buf, cur, ")");
5193 /* Prints rtxes, I customly classified as values. They're constants,
5194 registers, labels, symbols and memory accesses. */
5197 print_value (buf, x, verbose)
5205 switch (GET_CODE (x))
5208 sprintf (t, HOST_WIDE_INT_PRINT_HEX, INTVAL (x));
5209 cur = safe_concat (buf, cur, t);
5212 sprintf (t, "<0x%lx,0x%lx>", (long)XWINT (x, 2), (long)XWINT (x, 3));
5213 cur = safe_concat (buf, cur, t);
5216 cur = safe_concat (buf, cur, "\"");
5217 cur = safe_concat (buf, cur, XSTR (x, 0));
5218 cur = safe_concat (buf, cur, "\"");
5221 cur = safe_concat (buf, cur, "`");
5222 cur = safe_concat (buf, cur, XSTR (x, 0));
5223 cur = safe_concat (buf, cur, "'");
5226 sprintf (t, "L%d", INSN_UID (XEXP (x, 0)));
5227 cur = safe_concat (buf, cur, t);
5230 print_value (t, XEXP (x, 0), verbose);
5231 cur = safe_concat (buf, cur, "const(");
5232 cur = safe_concat (buf, cur, t);
5233 cur = safe_concat (buf, cur, ")");
5236 print_value (t, XEXP (x, 0), verbose);
5237 cur = safe_concat (buf, cur, "high(");
5238 cur = safe_concat (buf, cur, t);
5239 cur = safe_concat (buf, cur, ")");
5242 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
5244 int c = reg_names[ REGNO (x) ][0];
5245 if (c >= '0' && c <= '9')
5246 cur = safe_concat (buf, cur, "%");
5248 cur = safe_concat (buf, cur, reg_names[ REGNO (x) ]);
5252 sprintf (t, "r%d", REGNO (x));
5253 cur = safe_concat (buf, cur, t);
5257 print_value (t, SUBREG_REG (x), verbose);
5258 cur = safe_concat (buf, cur, t);
5259 sprintf (t, "#%d", SUBREG_WORD (x));
5260 cur = safe_concat (buf, cur, t);
5263 cur = safe_concat (buf, cur, "scratch");
5266 cur = safe_concat (buf, cur, "cc0");
5269 cur = safe_concat (buf, cur, "pc");
5272 print_value (t, XEXP (x, 0), verbose);
5273 cur = safe_concat (buf, cur, "[");
5274 cur = safe_concat (buf, cur, t);
5275 cur = safe_concat (buf, cur, "]");
5278 print_exp (t, x, verbose);
5279 cur = safe_concat (buf, cur, t);
5284 /* The next step in insn detalization, its pattern recognition. */
5287 print_pattern (buf, x, verbose)
5292 char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
5294 switch (GET_CODE (x))
5297 print_value (t1, SET_DEST (x), verbose);
5298 print_value (t2, SET_SRC (x), verbose);
5299 sprintf (buf, "%s=%s", t1, t2);
5302 sprintf (buf, "return");
5305 print_exp (buf, x, verbose);
5308 print_value (t1, XEXP (x, 0), verbose);
5309 sprintf (buf, "clobber %s", t1);
5312 print_value (t1, XEXP (x, 0), verbose);
5313 sprintf (buf, "use %s", t1);
5320 for (i = 0; i < XVECLEN (x, 0); i++)
5322 print_pattern (t2, XVECEXP (x, 0, i), verbose);
5323 sprintf (t3, "%s%s;", t1, t2);
5326 sprintf (buf, "%s}", t1);
5333 sprintf (t1, "%%{");
5334 for (i = 0; i < XVECLEN (x, 0); i++)
5336 print_insn (t2, XVECEXP (x, 0, i), verbose);
5337 sprintf (t3, "%s%s;", t1, t2);
5340 sprintf (buf, "%s%%}", t1);
5344 sprintf (buf, "asm {%s}", XSTR (x, 0));
5349 print_value (buf, XEXP (x, 0), verbose);
5352 print_value (t1, TRAP_CONDITION (x), verbose);
5353 sprintf (buf, "trap_if %s", t1);
5359 sprintf (t1, "unspec{");
5360 for (i = 0; i < XVECLEN (x, 0); i++)
5362 print_pattern (t2, XVECEXP (x, 0, i), verbose);
5363 sprintf (t3, "%s%s;", t1, t2);
5366 sprintf (buf, "%s}", t1);
5369 case UNSPEC_VOLATILE:
5373 sprintf (t1, "unspec/v{");
5374 for (i = 0; i < XVECLEN (x, 0); i++)
5376 print_pattern (t2, XVECEXP (x, 0, i), verbose);
5377 sprintf (t3, "%s%s;", t1, t2);
5380 sprintf (buf, "%s}", t1);
5384 print_value (buf, x, verbose);
5386 } /* print_pattern */
5388 /* This is the main function in rtl visualization mechanism. It
5389 accepts an rtx and tries to recognize it as an insn, then prints it
5390 properly in human readable form, resembling assembler mnemonics.
5391 For every insn it prints its UID and BB the insn belongs too.
5392 (Probably the last "option" should be extended somehow, since it
5393 depends now on sched.c inner variables ...) */
5396 print_insn (buf, x, verbose)
5404 switch (GET_CODE (x))
5407 print_pattern (t, PATTERN (x), verbose);
5409 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (x),
5412 sprintf (buf, "%-4d %s", INSN_UID (x), t);
5415 print_pattern (t, PATTERN (x), verbose);
5417 sprintf (buf, "b%d: i% 4d: jump %s", INSN_BB (x),
5420 sprintf (buf, "%-4d %s", INSN_UID (x), t);
5424 if (GET_CODE (x) == PARALLEL)
5426 x = XVECEXP (x, 0, 0);
5427 print_pattern (t, x, verbose);
5430 strcpy (t, "call <...>");
5432 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (insn),
5433 INSN_UID (insn), t);
5435 sprintf (buf, "%-4d %s", INSN_UID (insn), t);
5438 sprintf (buf, "L%d:", INSN_UID (x));
5441 sprintf (buf, "i% 4d: barrier", INSN_UID (x));
5444 if (NOTE_LINE_NUMBER (x) > 0)
5445 sprintf (buf, "%4d note \"%s\" %d", INSN_UID (x),
5446 NOTE_SOURCE_FILE (x), NOTE_LINE_NUMBER (x));
5448 sprintf (buf, "%4d %s", INSN_UID (x),
5449 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x)));
5454 sprintf (buf, "Not an INSN at all\n");
5458 sprintf (buf, "i%-4d <What?>", INSN_UID (x));
5462 /* Print visualization debugging info. */
5465 print_block_visualization (b, s)
5472 fprintf (dump, "\n;; ==================== scheduling visualization for block %d %s \n", b, s);
5474 /* Print names of units. */
5475 fprintf (dump, ";; %-8s", "clock");
5476 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5477 if (function_units[unit].bitmask & target_units)
5478 for (i = 0; i < function_units[unit].multiplicity; i++)
5479 fprintf (dump, " %-33s", function_units[unit].name);
5480 fprintf (dump, " %-8s\n", "no-unit");
5482 fprintf (dump, ";; %-8s", "=====");
5483 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5484 if (function_units[unit].bitmask & target_units)
5485 for (i = 0; i < function_units[unit].multiplicity; i++)
5486 fprintf (dump, " %-33s", "==============================");
5487 fprintf (dump, " %-8s\n", "=======");
5489 /* Print insns in each cycle. */
5490 fprintf (dump, "%s\n", visual_tbl);
5493 /* Print insns in the 'no_unit' column of visualization. */
5496 visualize_no_unit (insn)
5499 vis_no_unit[n_vis_no_unit] = insn;
5503 /* Print insns scheduled in clock, for visualization. */
5506 visualize_scheduled_insns (b, clock)
5511 /* If no more room, split table into two. */
5512 if (n_visual_lines >= MAX_VISUAL_LINES)
5514 print_block_visualization (b, "(incomplete)");
5515 init_block_visualization ();
5520 sprintf (visual_tbl + strlen (visual_tbl), ";; %-8d", clock);
5521 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5522 if (function_units[unit].bitmask & target_units)
5523 for (i = 0; i < function_units[unit].multiplicity; i++)
5525 int instance = unit + i * FUNCTION_UNITS_SIZE;
5526 rtx insn = unit_last_insn[instance];
5528 /* Print insns that still keep the unit busy. */
5530 actual_hazard_this_instance (unit, instance, insn, clock, 0))
5533 print_insn (str, insn, 0);
5534 str[INSN_LEN] = '\0';
5535 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", str);
5538 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", "------------------------------");
5541 /* Print insns that are not assigned to any unit. */
5542 for (i = 0; i < n_vis_no_unit; i++)
5543 sprintf (visual_tbl + strlen (visual_tbl), " %-8d",
5544 INSN_UID (vis_no_unit[i]));
5547 sprintf (visual_tbl + strlen (visual_tbl), "\n");
5550 /* Print stalled cycles. */
5553 visualize_stall_cycles (b, stalls)
5558 /* If no more room, split table into two. */
5559 if (n_visual_lines >= MAX_VISUAL_LINES)
5561 print_block_visualization (b, "(incomplete)");
5562 init_block_visualization ();
5567 sprintf (visual_tbl + strlen (visual_tbl), ";; ");
5568 for (i = 0; i < stalls; i++)
5569 sprintf (visual_tbl + strlen (visual_tbl), ".");
5570 sprintf (visual_tbl + strlen (visual_tbl), "\n");
5573 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
5576 move_insn1 (insn, last)
5579 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
5580 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
5582 NEXT_INSN (insn) = NEXT_INSN (last);
5583 PREV_INSN (NEXT_INSN (last)) = insn;
5585 NEXT_INSN (last) = insn;
5586 PREV_INSN (insn) = last;
5591 /* Search INSN for REG_SAVE_NOTE note pairs for NOTE_INSN_SETJMP,
5592 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
5593 NOTEs. The REG_SAVE_NOTE note following first one is contains the
5594 saved value for NOTE_BLOCK_NUMBER which is useful for
5595 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
5596 output by the instruction scheduler. Return the new value of LAST. */
5599 reemit_notes (insn, last)
5606 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
5608 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
5610 int note_type = INTVAL (XEXP (note, 0));
5611 if (note_type == NOTE_INSN_SETJMP)
5613 retval = emit_note_after (NOTE_INSN_SETJMP, insn);
5614 CONST_CALL_P (retval) = CONST_CALL_P (note);
5615 remove_note (insn, note);
5616 note = XEXP (note, 1);
5618 else if (note_type == NOTE_INSN_RANGE_START
5619 || note_type == NOTE_INSN_RANGE_END)
5621 last = emit_note_before (note_type, last);
5622 remove_note (insn, note);
5623 note = XEXP (note, 1);
5624 NOTE_RANGE_INFO (last) = XEXP (note, 0);
5628 last = emit_note_before (note_type, last);
5629 remove_note (insn, note);
5630 note = XEXP (note, 1);
5631 if (note_type == NOTE_INSN_EH_REGION_BEG
5632 || note_type == NOTE_INSN_EH_REGION_END)
5633 NOTE_EH_HANDLER (last) = INTVAL (XEXP (note, 0));
5635 remove_note (insn, note);
5641 /* Move INSN, and all insns which should be issued before it,
5642 due to SCHED_GROUP_P flag. Reemit notes if needed.
5644 Return the last insn emitted by the scheduler, which is the
5645 return value from the first call to reemit_notes. */
5648 move_insn (insn, last)
5653 /* If INSN has SCHED_GROUP_P set, then issue it and any other
5654 insns with SCHED_GROUP_P set first. */
5655 while (SCHED_GROUP_P (insn))
5657 rtx prev = PREV_INSN (insn);
5659 /* Move a SCHED_GROUP_P insn. */
5660 move_insn1 (insn, last);
5661 /* If this is the first call to reemit_notes, then record
5662 its return value. */
5663 if (retval == NULL_RTX)
5664 retval = reemit_notes (insn, insn);
5666 reemit_notes (insn, insn);
5670 /* Now move the first non SCHED_GROUP_P insn. */
5671 move_insn1 (insn, last);
5673 /* If this is the first call to reemit_notes, then record
5674 its return value. */
5675 if (retval == NULL_RTX)
5676 retval = reemit_notes (insn, insn);
5678 reemit_notes (insn, insn);
5683 /* Return an insn which represents a SCHED_GROUP, which is
5684 the last insn in the group. */
5695 insn = next_nonnote_insn (insn);
5697 while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
5702 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
5703 possibly bringing insns from subsequent blocks in the same region.
5704 Return number of insns scheduled. */
5707 schedule_block (bb, rgn_n_insns)
5711 /* Local variables. */
5717 /* Flow block of this bb. */
5718 int b = BB_TO_BLOCK (bb);
5720 /* target_n_insns == number of insns in b before scheduling starts.
5721 sched_target_n_insns == how many of b's insns were scheduled.
5722 sched_n_insns == how many insns were scheduled in b. */
5723 int target_n_insns = 0;
5724 int sched_target_n_insns = 0;
5725 int sched_n_insns = 0;
5727 #define NEED_NOTHING 0
5732 /* Head/tail info for this block. */
5739 /* We used to have code to avoid getting parameters moved from hard
5740 argument registers into pseudos.
5742 However, it was removed when it proved to be of marginal benefit
5743 and caused problems because schedule_block and compute_forward_dependences
5744 had different notions of what the "head" insn was. */
5745 get_bb_head_tail (bb, &head, &tail);
5747 /* Interblock scheduling could have moved the original head insn from this
5748 block into a proceeding block. This may also cause schedule_block and
5749 compute_forward_dependences to have different notions of what the
5752 If the interblock movement happened to make this block start with
5753 some notes (LOOP, EH or SETJMP) before the first real insn, then
5754 HEAD will have various special notes attached to it which must be
5755 removed so that we don't end up with extra copies of the notes. */
5756 if (GET_RTX_CLASS (GET_CODE (head)) == 'i')
5760 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
5761 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
5762 remove_note (head, note);
5765 next_tail = NEXT_INSN (tail);
5766 prev_head = PREV_INSN (head);
5768 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
5769 to schedule this block. */
5771 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
5772 return (sched_n_insns);
5777 fprintf (dump, ";; ======================================================\n");
5779 ";; -- basic block %d from %d to %d -- %s reload\n",
5780 b, INSN_UID (BLOCK_HEAD (b)), INSN_UID (BLOCK_END (b)),
5781 (reload_completed ? "after" : "before"));
5782 fprintf (dump, ";; ======================================================\n");
5783 fprintf (dump, "\n");
5785 visual_tbl = (char *) alloca (get_visual_tbl_length ());
5786 init_block_visualization ();
5789 /* Remove remaining note insns from the block, save them in
5790 note_list. These notes are restored at the end of
5791 schedule_block (). */
5793 rm_other_notes (head, tail);
5797 /* Prepare current target block info. */
5798 if (current_nr_blocks > 1)
5800 candidate_table = (candidate *) xmalloc (current_nr_blocks
5801 * sizeof (candidate));
5804 /* ??? It is not clear why bblst_size is computed this way. The original
5805 number was clearly too small as it resulted in compiler failures.
5806 Multiplying by the original number by 2 (to account for update_bbs
5807 members) seems to be a reasonable solution. */
5808 /* ??? Or perhaps there is a bug somewhere else in this file? */
5809 bblst_size = (current_nr_blocks - bb) * rgn_nr_edges * 2;
5810 bblst_table = (int *) xmalloc (bblst_size * sizeof (int));
5812 bitlst_table_last = 0;
5813 bitlst_table_size = rgn_nr_edges;
5814 bitlst_table = (int *) xmalloc (rgn_nr_edges * sizeof (int));
5816 compute_trg_info (bb);
5821 /* Allocate the ready list. */
5822 ready = (rtx *) xmalloc ((rgn_n_insns + 1) * sizeof (rtx));
5824 /* Print debugging information. */
5825 if (sched_verbose >= 5)
5826 debug_dependencies ();
5829 /* Initialize ready list with all 'ready' insns in target block.
5830 Count number of insns in the target block being scheduled. */
5832 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5836 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5838 next = NEXT_INSN (insn);
5840 if (INSN_DEP_COUNT (insn) == 0
5841 && (SCHED_GROUP_P (next) == 0 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
5842 ready[n_ready++] = insn;
5843 if (!(SCHED_GROUP_P (insn)))
5847 /* Add to ready list all 'ready' insns in valid source blocks.
5848 For speculative insns, check-live, exception-free, and
5850 for (bb_src = bb + 1; bb_src < current_nr_blocks; bb_src++)
5851 if (IS_VALID (bb_src))
5857 get_bb_head_tail (bb_src, &head, &tail);
5858 src_next_tail = NEXT_INSN (tail);
5862 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
5865 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
5867 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5870 if (!CANT_MOVE (insn)
5871 && (!IS_SPECULATIVE_INSN (insn)
5872 || (insn_issue_delay (insn) <= 3
5873 && check_live (insn, bb_src)
5874 && is_exception_free (insn, bb_src, target_bb))))
5878 /* Note that we havn't squirrled away the notes for
5879 blocks other than the current. So if this is a
5880 speculative insn, NEXT might otherwise be a note. */
5881 next = next_nonnote_insn (insn);
5882 if (INSN_DEP_COUNT (insn) == 0
5884 || SCHED_GROUP_P (next) == 0
5885 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
5886 ready[n_ready++] = insn;
5891 #ifdef MD_SCHED_INIT
5892 MD_SCHED_INIT (dump, sched_verbose);
5895 /* No insns scheduled in this block yet. */
5896 last_scheduled_insn = 0;
5898 /* Q_SIZE is the total number of insns in the queue. */
5902 bzero ((char *) insn_queue, sizeof (insn_queue));
5904 /* Start just before the beginning of time. */
5907 /* We start inserting insns after PREV_HEAD. */
5910 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
5911 new_needs = (NEXT_INSN (prev_head) == BLOCK_HEAD (b)
5912 ? NEED_HEAD : NEED_NOTHING);
5913 if (PREV_INSN (next_tail) == BLOCK_END (b))
5914 new_needs |= NEED_TAIL;
5916 /* Loop until all the insns in BB are scheduled. */
5917 while (sched_target_n_insns < target_n_insns)
5921 /* Add to the ready list all pending insns that can be issued now.
5922 If there are no ready insns, increment clock until one
5923 is ready and add all pending insns at that point to the ready
5925 n_ready = queue_to_ready (ready, n_ready);
5930 if (sched_verbose >= 2)
5932 fprintf (dump, ";;\t\tReady list after queue_to_ready: ");
5933 debug_ready_list (ready, n_ready);
5936 /* Sort the ready list based on priority. */
5937 SCHED_SORT (ready, n_ready);
5939 /* Allow the target to reorder the list, typically for
5940 better instruction bundling. */
5941 #ifdef MD_SCHED_REORDER
5942 MD_SCHED_REORDER (dump, sched_verbose, ready, n_ready, clock_var,
5945 can_issue_more = issue_rate;
5950 fprintf (dump, "\n;;\tReady list (t =%3d): ", clock_var);
5951 debug_ready_list (ready, n_ready);
5954 /* Issue insns from ready list. */
5955 while (n_ready != 0 && can_issue_more)
5957 /* Select and remove the insn from the ready list. */
5958 rtx insn = ready[--n_ready];
5959 int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
5963 queue_insn (insn, cost);
5967 /* An interblock motion? */
5968 if (INSN_BB (insn) != target_bb)
5973 if (IS_SPECULATIVE_INSN (insn))
5975 if (!check_live (insn, INSN_BB (insn)))
5977 update_live (insn, INSN_BB (insn));
5979 /* For speculative load, mark insns fed by it. */
5980 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
5981 set_spec_fed (insn);
5987 /* Find the beginning of the scheduling group. */
5988 /* ??? Ought to update basic block here, but later bits of
5989 schedule_block assumes the original insn block is
5993 while (SCHED_GROUP_P (temp))
5994 temp = PREV_INSN (temp);
5996 /* Update source block boundaries. */
5997 b1 = BLOCK_FOR_INSN (temp);
5998 if (temp == b1->head && insn == b1->end)
6000 /* We moved all the insns in the basic block.
6001 Emit a note after the last insn and update the
6002 begin/end boundaries to point to the note. */
6003 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
6007 else if (insn == b1->end)
6009 /* We took insns from the end of the basic block,
6010 so update the end of block boundary so that it
6011 points to the first insn we did not move. */
6012 b1->end = PREV_INSN (temp);
6014 else if (temp == b1->head)
6016 /* We took insns from the start of the basic block,
6017 so update the start of block boundary so that
6018 it points to the first insn we did not move. */
6019 b1->head = NEXT_INSN (insn);
6024 /* In block motion. */
6025 sched_target_n_insns++;
6028 last_scheduled_insn = insn;
6029 last = move_insn (insn, last);
6032 #ifdef MD_SCHED_VARIABLE_ISSUE
6033 MD_SCHED_VARIABLE_ISSUE (dump, sched_verbose, insn,
6039 n_ready = schedule_insn (insn, ready, n_ready, clock_var);
6041 /* Close this block after scheduling its jump. */
6042 if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
6048 visualize_scheduled_insns (b, clock_var);
6054 fprintf (dump, ";;\tReady list (final): ");
6055 debug_ready_list (ready, n_ready);
6056 print_block_visualization (b, "");
6059 /* Sanity check -- queue must be empty now. Meaningless if region has
6061 if (current_nr_blocks > 1)
6062 if (!flag_schedule_interblock && q_size != 0)
6065 /* Update head/tail boundaries. */
6066 head = NEXT_INSN (prev_head);
6069 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6070 previously found among the insns. Insert them at the beginning
6074 rtx note_head = note_list;
6076 while (PREV_INSN (note_head))
6078 note_head = PREV_INSN (note_head);
6081 PREV_INSN (note_head) = PREV_INSN (head);
6082 NEXT_INSN (PREV_INSN (head)) = note_head;
6083 PREV_INSN (head) = note_list;
6084 NEXT_INSN (note_list) = head;
6088 /* Update target block boundaries. */
6089 if (new_needs & NEED_HEAD)
6090 BLOCK_HEAD (b) = head;
6092 if (new_needs & NEED_TAIL)
6093 BLOCK_END (b) = tail;
6098 fprintf (dump, ";; total time = %d\n;; new basic block head = %d\n",
6099 clock_var, INSN_UID (BLOCK_HEAD (b)));
6100 fprintf (dump, ";; new basic block end = %d\n\n",
6101 INSN_UID (BLOCK_END (b)));
6105 if (current_nr_blocks > 1)
6107 free (candidate_table);
6109 free (bitlst_table);
6113 return (sched_n_insns);
6114 } /* schedule_block () */
6117 /* Print the bit-set of registers, S, callable from debugger. */
6120 debug_reg_vector (s)
6125 EXECUTE_IF_SET_IN_REG_SET (s, 0, regno,
6127 fprintf (dump, " %d", regno);
6130 fprintf (dump, "\n");
6133 /* Use the backward dependences from LOG_LINKS to build
6134 forward dependences in INSN_DEPEND. */
6137 compute_block_forward_dependences (bb)
6143 enum reg_note dep_type;
6145 get_bb_head_tail (bb, &head, &tail);
6146 next_tail = NEXT_INSN (tail);
6147 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6149 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6152 insn = group_leader (insn);
6154 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
6156 rtx x = group_leader (XEXP (link, 0));
6159 if (x != XEXP (link, 0))
6162 #ifdef ENABLE_CHECKING
6163 /* If add_dependence is working properly there should never
6164 be notes, deleted insns or duplicates in the backward
6165 links. Thus we need not check for them here.
6167 However, if we have enabled checking we might as well go
6168 ahead and verify that add_dependence worked properly. */
6169 if (GET_CODE (x) == NOTE
6170 || INSN_DELETED_P (x)
6171 || find_insn_list (insn, INSN_DEPEND (x)))
6175 new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
6177 dep_type = REG_NOTE_KIND (link);
6178 PUT_REG_NOTE_KIND (new_link, dep_type);
6180 INSN_DEPEND (x) = new_link;
6181 INSN_DEP_COUNT (insn) += 1;
6186 /* Initialize variables for region data dependence analysis.
6187 n_bbs is the number of region blocks. */
6193 int maxreg = max_reg_num ();
6194 deps->reg_last_uses = (rtx *) xcalloc (maxreg, sizeof (rtx));
6195 deps->reg_last_sets = (rtx *) xcalloc (maxreg, sizeof (rtx));
6196 deps->reg_last_clobbers = (rtx *) xcalloc (maxreg, sizeof (rtx));
6198 deps->pending_read_insns = 0;
6199 deps->pending_read_mems = 0;
6200 deps->pending_write_insns = 0;
6201 deps->pending_write_mems = 0;
6202 deps->pending_lists_length = 0;
6203 deps->last_pending_memory_flush = 0;
6204 deps->last_function_call = 0;
6206 deps->sched_before_next_call
6207 = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
6208 NULL_RTX, 0, NULL_RTX, NULL_RTX);
6209 LOG_LINKS (deps->sched_before_next_call) = 0;
6212 /* Add dependences so that branches are scheduled to run last in their
6216 add_branch_dependences (head, tail)
6221 /* For all branches, calls, uses, clobbers, and cc0 setters, force them
6222 to remain in order at the end of the block by adding dependencies and
6223 giving the last a high priority. There may be notes present, and
6224 prev_head may also be a note.
6226 Branches must obviously remain at the end. Calls should remain at the
6227 end since moving them results in worse register allocation. Uses remain
6228 at the end to ensure proper register allocation. cc0 setters remaim
6229 at the end because they can't be moved away from their cc0 user. */
6232 while (GET_CODE (insn) == CALL_INSN
6233 || GET_CODE (insn) == JUMP_INSN
6234 || (GET_CODE (insn) == INSN
6235 && (GET_CODE (PATTERN (insn)) == USE
6236 || GET_CODE (PATTERN (insn)) == CLOBBER
6238 || sets_cc0_p (PATTERN (insn))
6241 || GET_CODE (insn) == NOTE)
6243 if (GET_CODE (insn) != NOTE)
6246 && !find_insn_list (insn, LOG_LINKS (last)))
6248 add_dependence (last, insn, REG_DEP_ANTI);
6249 INSN_REF_COUNT (insn)++;
6252 CANT_MOVE (insn) = 1;
6255 /* Skip over insns that are part of a group.
6256 Make each insn explicitly depend on the previous insn.
6257 This ensures that only the group header will ever enter
6258 the ready queue (and, when scheduled, will automatically
6259 schedule the SCHED_GROUP_P block). */
6260 while (SCHED_GROUP_P (insn))
6262 rtx temp = prev_nonnote_insn (insn);
6263 add_dependence (insn, temp, REG_DEP_ANTI);
6268 /* Don't overrun the bounds of the basic block. */
6272 insn = PREV_INSN (insn);
6275 /* Make sure these insns are scheduled last in their block. */
6278 while (insn != head)
6280 insn = prev_nonnote_insn (insn);
6282 if (INSN_REF_COUNT (insn) != 0)
6285 add_dependence (last, insn, REG_DEP_ANTI);
6286 INSN_REF_COUNT (insn) = 1;
6288 /* Skip over insns that are part of a group. */
6289 while (SCHED_GROUP_P (insn))
6290 insn = prev_nonnote_insn (insn);
6294 /* After computing the dependencies for block BB, propagate the dependencies
6295 found in TMP_DEPS to the successors of the block. MAX_REG is the number
6298 propagate_deps (bb, tmp_deps, max_reg)
6300 struct deps *tmp_deps;
6303 int b = BB_TO_BLOCK (bb);
6306 rtx link_insn, link_mem;
6309 /* These lists should point to the right place, for correct
6311 bb_deps[bb].pending_read_insns = tmp_deps->pending_read_insns;
6312 bb_deps[bb].pending_read_mems = tmp_deps->pending_read_mems;
6313 bb_deps[bb].pending_write_insns = tmp_deps->pending_write_insns;
6314 bb_deps[bb].pending_write_mems = tmp_deps->pending_write_mems;
6316 /* bb's structures are inherited by its successors. */
6317 first_edge = e = OUT_EDGES (b);
6324 int b_succ = TO_BLOCK (e);
6325 int bb_succ = BLOCK_TO_BB (b_succ);
6326 struct deps *succ_deps = bb_deps + bb_succ;
6328 /* Only bbs "below" bb, in the same region, are interesting. */
6329 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
6336 for (reg = 0; reg < max_reg; reg++)
6338 /* reg-last-uses lists are inherited by bb_succ. */
6339 for (u = tmp_deps->reg_last_uses[reg]; u; u = XEXP (u, 1))
6341 if (find_insn_list (XEXP (u, 0),
6342 succ_deps->reg_last_uses[reg]))
6345 succ_deps->reg_last_uses[reg]
6346 = alloc_INSN_LIST (XEXP (u, 0),
6347 succ_deps->reg_last_uses[reg]);
6350 /* reg-last-defs lists are inherited by bb_succ. */
6351 for (u = tmp_deps->reg_last_sets[reg]; u; u = XEXP (u, 1))
6353 if (find_insn_list (XEXP (u, 0),
6354 succ_deps->reg_last_sets[reg]))
6357 succ_deps->reg_last_sets[reg]
6358 = alloc_INSN_LIST (XEXP (u, 0),
6359 succ_deps->reg_last_sets[reg]);
6362 for (u = tmp_deps->reg_last_clobbers[reg]; u; u = XEXP (u, 1))
6364 if (find_insn_list (XEXP (u, 0),
6365 succ_deps->reg_last_clobbers[reg]))
6368 succ_deps->reg_last_clobbers[reg]
6369 = alloc_INSN_LIST (XEXP (u, 0),
6370 succ_deps->reg_last_clobbers[reg]);
6374 /* Mem read/write lists are inherited by bb_succ. */
6375 link_insn = tmp_deps->pending_read_insns;
6376 link_mem = tmp_deps->pending_read_mems;
6379 if (!(find_insn_mem_list (XEXP (link_insn, 0),
6381 succ_deps->pending_read_insns,
6382 succ_deps->pending_read_mems)))
6383 add_insn_mem_dependence (succ_deps, &succ_deps->pending_read_insns,
6384 &succ_deps->pending_read_mems,
6385 XEXP (link_insn, 0), XEXP (link_mem, 0));
6386 link_insn = XEXP (link_insn, 1);
6387 link_mem = XEXP (link_mem, 1);
6390 link_insn = tmp_deps->pending_write_insns;
6391 link_mem = tmp_deps->pending_write_mems;
6394 if (!(find_insn_mem_list (XEXP (link_insn, 0),
6396 succ_deps->pending_write_insns,
6397 succ_deps->pending_write_mems)))
6398 add_insn_mem_dependence (succ_deps,
6399 &succ_deps->pending_write_insns,
6400 &succ_deps->pending_write_mems,
6401 XEXP (link_insn, 0), XEXP (link_mem, 0));
6403 link_insn = XEXP (link_insn, 1);
6404 link_mem = XEXP (link_mem, 1);
6407 /* last_function_call is inherited by bb_succ. */
6408 for (u = tmp_deps->last_function_call; u; u = XEXP (u, 1))
6410 if (find_insn_list (XEXP (u, 0),
6411 succ_deps->last_function_call))
6414 succ_deps->last_function_call
6415 = alloc_INSN_LIST (XEXP (u, 0),
6416 succ_deps->last_function_call);
6419 /* last_pending_memory_flush is inherited by bb_succ. */
6420 for (u = tmp_deps->last_pending_memory_flush; u; u = XEXP (u, 1))
6422 if (find_insn_list (XEXP (u, 0),
6423 succ_deps->last_pending_memory_flush))
6426 succ_deps->last_pending_memory_flush
6427 = alloc_INSN_LIST (XEXP (u, 0),
6428 succ_deps->last_pending_memory_flush);
6431 /* sched_before_next_call is inherited by bb_succ. */
6432 x = LOG_LINKS (tmp_deps->sched_before_next_call);
6433 for (; x; x = XEXP (x, 1))
6434 add_dependence (succ_deps->sched_before_next_call,
6435 XEXP (x, 0), REG_DEP_ANTI);
6439 while (e != first_edge);
6442 /* Compute backward dependences inside bb. In a multiple blocks region:
6443 (1) a bb is analyzed after its predecessors, and (2) the lists in
6444 effect at the end of bb (after analyzing for bb) are inherited by
6447 Specifically for reg-reg data dependences, the block insns are
6448 scanned by sched_analyze () top-to-bottom. Two lists are
6449 maintained by sched_analyze (): reg_last_sets[] for register DEFs,
6450 and reg_last_uses[] for register USEs.
6452 When analysis is completed for bb, we update for its successors:
6453 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
6454 ; - USES[succ] = Union (USES [succ], DEFS [bb])
6456 The mechanism for computing mem-mem data dependence is very
6457 similar, and the result is interblock dependences in the region. */
6460 compute_block_backward_dependences (bb)
6465 int max_reg = max_reg_num ();
6466 struct deps tmp_deps;
6468 tmp_deps = bb_deps[bb];
6470 /* Do the analysis for this block. */
6471 get_bb_head_tail (bb, &head, &tail);
6472 sched_analyze (&tmp_deps, head, tail);
6473 add_branch_dependences (head, tail);
6475 if (current_nr_blocks > 1)
6476 propagate_deps (bb, &tmp_deps, max_reg);
6478 /* Free up the INSN_LISTs.
6480 Note this loop is executed max_reg * nr_regions times. It's first
6481 implementation accounted for over 90% of the calls to free_INSN_LIST_list.
6482 The list was empty for the vast majority of those calls. On the PA, not
6483 calling free_INSN_LIST_list in those cases improves -O2 compile times by
6485 for (i = 0; i < max_reg; ++i)
6487 if (tmp_deps.reg_last_clobbers[i])
6488 free_INSN_LIST_list (&tmp_deps.reg_last_clobbers[i]);
6489 if (tmp_deps.reg_last_sets[i])
6490 free_INSN_LIST_list (&tmp_deps.reg_last_sets[i]);
6491 if (tmp_deps.reg_last_uses[i])
6492 free_INSN_LIST_list (&tmp_deps.reg_last_uses[i]);
6495 /* Assert that we won't need bb_reg_last_* for this block anymore. */
6496 free (bb_deps[bb].reg_last_uses);
6497 free (bb_deps[bb].reg_last_sets);
6498 free (bb_deps[bb].reg_last_clobbers);
6499 bb_deps[bb].reg_last_uses = 0;
6500 bb_deps[bb].reg_last_sets = 0;
6501 bb_deps[bb].reg_last_clobbers = 0;
6504 /* Print dependences for debugging, callable from debugger. */
6507 debug_dependencies ()
6511 fprintf (dump, ";; --------------- forward dependences: ------------ \n");
6512 for (bb = 0; bb < current_nr_blocks; bb++)
6520 get_bb_head_tail (bb, &head, &tail);
6521 next_tail = NEXT_INSN (tail);
6522 fprintf (dump, "\n;; --- Region Dependences --- b %d bb %d \n",
6523 BB_TO_BLOCK (bb), bb);
6525 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
6526 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
6527 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
6528 "----", "----", "--", "---", "----", "----", "--------", "-----");
6529 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6534 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6537 fprintf (dump, ";; %6d ", INSN_UID (insn));
6538 if (GET_CODE (insn) == NOTE)
6540 n = NOTE_LINE_NUMBER (insn);
6542 fprintf (dump, "%s\n", GET_NOTE_INSN_NAME (n));
6544 fprintf (dump, "line %d, file %s\n", n,
6545 NOTE_SOURCE_FILE (insn));
6548 fprintf (dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
6552 unit = insn_unit (insn);
6554 || function_units[unit].blockage_range_function == 0) ? 0 :
6555 function_units[unit].blockage_range_function (insn);
6557 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
6558 (SCHED_GROUP_P (insn) ? "+" : " "),
6562 INSN_DEP_COUNT (insn),
6563 INSN_PRIORITY (insn),
6564 insn_cost (insn, 0, 0),
6565 (int) MIN_BLOCKAGE_COST (range),
6566 (int) MAX_BLOCKAGE_COST (range));
6567 insn_print_units (insn);
6568 fprintf (dump, "\t: ");
6569 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
6570 fprintf (dump, "%d ", INSN_UID (XEXP (link, 0)));
6571 fprintf (dump, "\n");
6575 fprintf (dump, "\n");
6578 /* Set_priorities: compute priority of each insn in the block. */
6591 get_bb_head_tail (bb, &head, &tail);
6592 prev_head = PREV_INSN (head);
6595 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6599 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
6602 if (GET_CODE (insn) == NOTE)
6605 if (!(SCHED_GROUP_P (insn)))
6607 (void) priority (insn);
6613 /* Schedule a region. A region is either an inner loop, a loop-free
6614 subroutine, or a single basic block. Each bb in the region is
6615 scheduled after its flow predecessors. */
6618 schedule_region (rgn)
6622 int rgn_n_insns = 0;
6623 int sched_rgn_n_insns = 0;
6625 /* Set variables for the current region. */
6626 current_nr_blocks = RGN_NR_BLOCKS (rgn);
6627 current_blocks = RGN_BLOCKS (rgn);
6629 reg_pending_sets = ALLOCA_REG_SET ();
6630 reg_pending_clobbers = ALLOCA_REG_SET ();
6631 reg_pending_sets_all = 0;
6633 /* Initializations for region data dependence analyisis. */
6634 bb_deps = (struct deps *) xmalloc (sizeof (struct deps) * current_nr_blocks);
6635 for (bb = 0; bb < current_nr_blocks; bb++)
6636 init_deps (bb_deps + bb);
6638 /* Compute LOG_LINKS. */
6639 for (bb = 0; bb < current_nr_blocks; bb++)
6640 compute_block_backward_dependences (bb);
6642 /* Compute INSN_DEPEND. */
6643 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
6644 compute_block_forward_dependences (bb);
6646 /* Delete line notes and set priorities. */
6647 for (bb = 0; bb < current_nr_blocks; bb++)
6649 if (write_symbols != NO_DEBUG)
6651 save_line_notes (bb);
6655 rgn_n_insns += set_priorities (bb);
6658 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
6659 if (current_nr_blocks > 1)
6663 prob = (float *) xmalloc ((current_nr_blocks) * sizeof (float));
6665 bbset_size = current_nr_blocks / HOST_BITS_PER_WIDE_INT + 1;
6666 dom = (bbset *) xmalloc (current_nr_blocks * sizeof (bbset));
6667 for (i = 0; i < current_nr_blocks; i++)
6668 dom[i] = (bbset) xcalloc (bbset_size, sizeof (HOST_WIDE_INT));
6672 edge_to_bit = (int *) xmalloc (nr_edges * sizeof (int));
6673 for (i = 1; i < nr_edges; i++)
6674 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
6675 EDGE_TO_BIT (i) = rgn_nr_edges++;
6676 rgn_edges = (int *) xmalloc (rgn_nr_edges * sizeof (int));
6679 for (i = 1; i < nr_edges; i++)
6680 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
6681 rgn_edges[rgn_nr_edges++] = i;
6684 edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
6685 edgeset_bitsize = rgn_nr_edges;
6686 pot_split = (edgeset *) xmalloc (current_nr_blocks * sizeof (edgeset));
6688 = (edgeset *) xmalloc (current_nr_blocks * sizeof (edgeset));
6689 for (i = 0; i < current_nr_blocks; i++)
6692 (edgeset) xcalloc (edgeset_size, sizeof (HOST_WIDE_INT));
6694 (edgeset) xcalloc (edgeset_size, sizeof (HOST_WIDE_INT));
6697 /* Compute probabilities, dominators, split_edges. */
6698 for (bb = 0; bb < current_nr_blocks; bb++)
6699 compute_dom_prob_ps (bb);
6702 /* Now we can schedule all blocks. */
6703 for (bb = 0; bb < current_nr_blocks; bb++)
6704 sched_rgn_n_insns += schedule_block (bb, rgn_n_insns);
6706 /* Sanity check: verify that all region insns were scheduled. */
6707 if (sched_rgn_n_insns != rgn_n_insns)
6710 /* Restore line notes. */
6711 if (write_symbols != NO_DEBUG)
6713 for (bb = 0; bb < current_nr_blocks; bb++)
6714 restore_line_notes (bb);
6717 /* Done with this region. */
6718 free_pending_lists ();
6720 FREE_REG_SET (reg_pending_sets);
6721 FREE_REG_SET (reg_pending_clobbers);
6725 if (current_nr_blocks > 1)
6730 for (i = 0; i < current_nr_blocks; ++i)
6733 free (pot_split[i]);
6734 free (ancestor_edges[i]);
6740 free (ancestor_edges);
6744 /* The one entry point in this file. DUMP_FILE is the dump file for
6748 schedule_insns (dump_file)
6751 int *deaths_in_region;
6752 sbitmap blocks, large_region_blocks;
6758 int any_large_regions;
6760 /* Disable speculative loads in their presence if cc0 defined. */
6762 flag_schedule_speculative_load = 0;
6765 /* Taking care of this degenerate case makes the rest of
6766 this code simpler. */
6767 if (n_basic_blocks == 0)
6770 /* Set dump and sched_verbose for the desired debugging output. If no
6771 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
6772 For -fsched-verbose-N, N>=10, print everything to stderr. */
6773 sched_verbose = sched_verbose_param;
6774 if (sched_verbose_param == 0 && dump_file)
6776 dump = ((sched_verbose_param >= 10 || !dump_file) ? stderr : dump_file);
6781 /* Initialize issue_rate. */
6782 issue_rate = ISSUE_RATE;
6784 split_all_insns (1);
6786 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
6787 pseudos which do not cross calls. */
6788 max_uid = get_max_uid () + 1;
6790 h_i_d = (struct haifa_insn_data *) xcalloc (max_uid, sizeof (*h_i_d));
6794 for (b = 0; b < n_basic_blocks; b++)
6795 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
6797 INSN_LUID (insn) = luid;
6799 /* Increment the next luid, unless this is a note. We don't
6800 really need separate IDs for notes and we don't want to
6801 schedule differently depending on whether or not there are
6802 line-number notes, i.e., depending on whether or not we're
6803 generating debugging information. */
6804 if (GET_CODE (insn) != NOTE)
6807 if (insn == BLOCK_END (b))
6811 /* ?!? We could save some memory by computing a per-region luid mapping
6812 which could reduce both the number of vectors in the cache and the size
6813 of each vector. Instead we just avoid the cache entirely unless the
6814 average number of instructions in a basic block is very high. See
6815 the comment before the declaration of true_dependency_cache for
6816 what we consider "very high". */
6817 if (luid / n_basic_blocks > 100 * 5)
6819 true_dependency_cache = sbitmap_vector_alloc (luid, luid);
6820 sbitmap_vector_zero (true_dependency_cache, luid);
6824 rgn_table = (region *) xmalloc ((n_basic_blocks) * sizeof (region));
6825 rgn_bb_table = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
6826 block_to_bb = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
6827 containing_rgn = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
6829 blocks = sbitmap_alloc (n_basic_blocks);
6830 large_region_blocks = sbitmap_alloc (n_basic_blocks);
6832 compute_bb_for_insn (max_uid);
6834 /* Compute regions for scheduling. */
6835 if (reload_completed
6836 || n_basic_blocks == 1
6837 || !flag_schedule_interblock)
6839 find_single_block_region ();
6843 /* Verify that a 'good' control flow graph can be built. */
6844 if (is_cfg_nonregular ())
6846 find_single_block_region ();
6851 struct edge_list *edge_list;
6853 dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
6855 /* The scheduler runs after flow; therefore, we can't blindly call
6856 back into find_basic_blocks since doing so could invalidate the
6857 info in global_live_at_start.
6859 Consider a block consisting entirely of dead stores; after life
6860 analysis it would be a block of NOTE_INSN_DELETED notes. If
6861 we call find_basic_blocks again, then the block would be removed
6862 entirely and invalidate our the register live information.
6864 We could (should?) recompute register live information. Doing
6865 so may even be beneficial. */
6866 edge_list = create_edge_list ();
6868 /* Compute the dominators and post dominators. We don't
6869 currently use post dominators, but we should for
6870 speculative motion analysis. */
6871 compute_flow_dominators (dom, NULL);
6873 /* build_control_flow will return nonzero if it detects unreachable
6874 blocks or any other irregularity with the cfg which prevents
6875 cross block scheduling. */
6876 if (build_control_flow (edge_list) != 0)
6877 find_single_block_region ();
6879 find_rgns (edge_list, dom);
6881 if (sched_verbose >= 3)
6884 /* For now. This will move as more and more of haifa is converted
6885 to using the cfg code in flow.c. */
6890 deaths_in_region = (int *) xmalloc (sizeof(int) * nr_regions);
6892 init_alias_analysis ();
6894 if (write_symbols != NO_DEBUG)
6898 line_note_head = (rtx *) xcalloc (n_basic_blocks, sizeof (rtx));
6900 /* Save-line-note-head:
6901 Determine the line-number at the start of each basic block.
6902 This must be computed and saved now, because after a basic block's
6903 predecessor has been scheduled, it is impossible to accurately
6904 determine the correct line number for the first insn of the block. */
6906 for (b = 0; b < n_basic_blocks; b++)
6907 for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line))
6908 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
6910 line_note_head[b] = line;
6915 /* Find units used in this fuction, for visualization. */
6917 init_target_units ();
6919 /* ??? Add a NOTE after the last insn of the last basic block. It is not
6920 known why this is done. */
6922 insn = BLOCK_END (n_basic_blocks - 1);
6923 if (NEXT_INSN (insn) == 0
6924 || (GET_CODE (insn) != NOTE
6925 && GET_CODE (insn) != CODE_LABEL
6926 /* Don't emit a NOTE if it would end up between an unconditional
6927 jump and a BARRIER. */
6928 && !(GET_CODE (insn) == JUMP_INSN
6929 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
6930 emit_note_after (NOTE_INSN_DELETED, BLOCK_END (n_basic_blocks - 1));
6932 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
6933 removing death notes. */
6934 for (b = n_basic_blocks - 1; b >= 0; b--)
6935 find_insn_reg_weight (b);
6937 /* Remove all death notes from the subroutine. */
6938 for (rgn = 0; rgn < nr_regions; rgn++)
6940 sbitmap_zero (blocks);
6941 for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
6942 SET_BIT (blocks, rgn_bb_table [RGN_BLOCKS (rgn) + b]);
6944 deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1);
6947 /* Schedule every region in the subroutine. */
6948 for (rgn = 0; rgn < nr_regions; rgn++)
6949 schedule_region (rgn);
6951 /* Update life analysis for the subroutine. Do single block regions
6952 first so that we can verify that live_at_start didn't change. Then
6953 do all other blocks. */
6954 /* ??? There is an outside possibility that update_life_info, or more
6955 to the point propagate_block, could get called with non-zero flags
6956 more than once for one basic block. This would be kinda bad if it
6957 were to happen, since REG_INFO would be accumulated twice for the
6958 block, and we'd have twice the REG_DEAD notes.
6960 I'm fairly certain that this _shouldn't_ happen, since I don't think
6961 that live_at_start should change at region heads. Not sure what the
6962 best way to test for this kind of thing... */
6964 allocate_reg_life_data ();
6965 compute_bb_for_insn (max_uid);
6967 any_large_regions = 0;
6968 sbitmap_ones (large_region_blocks);
6970 for (rgn = 0; rgn < nr_regions; rgn++)
6971 if (RGN_NR_BLOCKS (rgn) > 1)
6972 any_large_regions = 1;
6975 sbitmap_zero (blocks);
6976 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
6977 RESET_BIT (large_region_blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
6979 /* Don't update reg info after reload, since that affects
6980 regs_ever_live, which should not change after reload. */
6981 update_life_info (blocks, UPDATE_LIFE_LOCAL,
6982 (reload_completed ? PROP_DEATH_NOTES
6983 : PROP_DEATH_NOTES | PROP_REG_INFO));
6985 /* In the single block case, the count of registers that died should
6986 not have changed during the schedule. */
6987 if (count_or_remove_death_notes (blocks, 0) != deaths_in_region[rgn])
6991 if (any_large_regions)
6993 update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL,
6994 PROP_DEATH_NOTES | PROP_REG_INFO);
6997 /* Reposition the prologue and epilogue notes in case we moved the
6998 prologue/epilogue insns. */
6999 if (reload_completed)
7000 reposition_prologue_and_epilogue_notes (get_insns ());
7002 /* Delete redundant line notes. */
7003 if (write_symbols != NO_DEBUG)
7004 rm_redundant_line_notes ();
7008 if (reload_completed == 0 && flag_schedule_interblock)
7010 fprintf (dump, "\n;; Procedure interblock/speculative motions == %d/%d \n",
7018 fprintf (dump, "\n\n");
7022 end_alias_analysis ();
7024 if (true_dependency_cache)
7026 free (true_dependency_cache);
7027 true_dependency_cache = NULL;
7030 free (rgn_bb_table);
7032 free (containing_rgn);
7036 if (write_symbols != NO_DEBUG)
7037 free (line_note_head);
7056 sbitmap_free (blocks);
7057 sbitmap_free (large_region_blocks);
7059 free (deaths_in_region);
7062 #endif /* INSN_SCHEDULING */