1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 93-98, 1999 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. */
162 #include "basic-block.h"
164 #include "function.h"
165 #include "hard-reg-set.h"
167 #include "insn-config.h"
168 #include "insn-attr.h"
173 extern char *reg_known_equiv_p;
174 extern rtx *reg_known_value;
176 #ifdef INSN_SCHEDULING
178 /* target_units bitmask has 1 for each unit in the cpu. It should be
179 possible to compute this variable from the machine description.
180 But currently it is computed by examining the insn list. Since
181 this is only needed for visualization, it seems an acceptable
182 solution. (For understanding the mapping of bits to units, see
183 definition of function_units[] in "insn-attrtab.c".) */
185 static int target_units = 0;
187 /* issue_rate is the number of insns that can be scheduled in the same
188 machine cycle. It can be defined in the config/mach/mach.h file,
189 otherwise we set it to 1. */
191 static int issue_rate;
197 /* sched-verbose controls the amount of debugging output the
198 scheduler prints. It is controlled by -fsched-verbose-N:
199 N>0 and no -DSR : the output is directed to stderr.
200 N>=10 will direct the printouts to stderr (regardless of -dSR).
202 N=2: bb's probabilities, detailed ready list info, unit/insn info.
203 N=3: rtl at abort point, control-flow, regions info.
204 N=5: dependences info. */
206 #define MAX_RGN_BLOCKS 10
207 #define MAX_RGN_INSNS 100
209 static int sched_verbose_param = 0;
210 static int sched_verbose = 0;
212 /* nr_inter/spec counts interblock/speculative motion for the function. */
213 static int nr_inter, nr_spec;
216 /* Debugging file. All printouts are sent to dump, which is always set,
217 either to stderr, or to the dump listing file (-dRS). */
218 static FILE *dump = 0;
220 /* fix_sched_param() is called from toplev.c upon detection
221 of the -fsched-***-N options. */
224 fix_sched_param (param, val)
225 const char *param, *val;
227 if (!strcmp (param, "verbose"))
228 sched_verbose_param = atoi (val);
230 warning ("fix_sched_param: unknown param: %s", param);
234 /* Arrays set up by scheduling for the same respective purposes as
235 similar-named arrays set up by flow analysis. We work with these
236 arrays during the scheduling pass so we can compare values against
239 Values of these arrays are copied at the end of this pass into the
240 arrays set up by flow analysis. */
241 static int *sched_reg_n_calls_crossed;
242 static int *sched_reg_live_length;
243 static int *sched_reg_basic_block;
245 /* We need to know the current block number during the post scheduling
246 update of live register information so that we can also update
247 REG_BASIC_BLOCK if a register changes blocks. */
248 static int current_block_num;
250 /* Element N is the next insn that sets (hard or pseudo) register
251 N within the current basic block; or zero, if there is no
252 such insn. Needed for new registers which may be introduced
253 by splitting insns. */
254 static rtx *reg_last_uses;
255 static rtx *reg_last_sets;
256 static rtx *reg_last_clobbers;
257 static regset reg_pending_sets;
258 static regset reg_pending_clobbers;
259 static int reg_pending_sets_all;
261 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
262 static int *insn_luid;
263 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
265 /* Vector indexed by INSN_UID giving each instruction a priority. */
266 static int *insn_priority;
267 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
269 static short *insn_costs;
270 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
272 /* Vector indexed by INSN_UID giving an encoding of the function units
274 static short *insn_units;
275 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
277 /* Vector indexed by INSN_UID giving each instruction a
278 register-weight. This weight is an estimation of the insn
279 contribution to registers pressure. */
280 static int *insn_reg_weight;
281 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
283 /* Vector indexed by INSN_UID giving list of insns which
284 depend upon INSN. Unlike LOG_LINKS, it represents forward dependences. */
285 static rtx *insn_depend;
286 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
288 /* Vector indexed by INSN_UID. Initialized to the number of incoming
289 edges in forward dependence graph (= number of LOG_LINKS). As
290 scheduling procedes, dependence counts are decreased. An
291 instruction moves to the ready list when its counter is zero. */
292 static int *insn_dep_count;
293 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
295 /* Vector indexed by INSN_UID giving an encoding of the blockage range
296 function. The unit and the range are encoded. */
297 static unsigned int *insn_blockage;
298 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
300 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
301 #define ENCODE_BLOCKAGE(U, R) \
302 (((U) << BLOCKAGE_BITS \
303 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
304 | MAX_BLOCKAGE_COST (R))
305 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
306 #define BLOCKAGE_RANGE(B) \
307 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
308 | ((B) & BLOCKAGE_MASK))
310 /* Encodings of the `<name>_unit_blockage_range' function. */
311 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
312 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
314 #define DONE_PRIORITY -1
315 #define MAX_PRIORITY 0x7fffffff
316 #define TAIL_PRIORITY 0x7ffffffe
317 #define LAUNCH_PRIORITY 0x7f000001
318 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
319 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
321 /* Vector indexed by INSN_UID giving number of insns referring to this
323 static int *insn_ref_count;
324 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
326 /* Vector indexed by INSN_UID giving line-number note in effect for each
327 insn. For line-number notes, this indicates whether the note may be
329 static rtx *line_note;
330 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
332 /* Vector indexed by basic block number giving the starting line-number
333 for each basic block. */
334 static rtx *line_note_head;
336 /* List of important notes we must keep around. This is a pointer to the
337 last element in the list. */
338 static rtx note_list;
340 /* Regsets telling whether a given register is live or dead before the last
341 scheduled insn. Must scan the instructions once before scheduling to
342 determine what registers are live or dead at the end of the block. */
343 static regset bb_live_regs;
345 /* Regset telling whether a given register is live after the insn currently
346 being scheduled. Before processing an insn, this is equal to bb_live_regs
347 above. This is used so that we can find registers that are newly born/dead
348 after processing an insn. */
349 static regset old_live_regs;
351 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
352 during the initial scan and reused later. If there are not exactly as
353 many REG_DEAD notes in the post scheduled code as there were in the
354 prescheduled code then we trigger an abort because this indicates a bug. */
355 static rtx dead_notes;
359 /* An instruction is ready to be scheduled when all insns preceding it
360 have already been scheduled. It is important to ensure that all
361 insns which use its result will not be executed until its result
362 has been computed. An insn is maintained in one of four structures:
364 (P) the "Pending" set of insns which cannot be scheduled until
365 their dependencies have been satisfied.
366 (Q) the "Queued" set of insns that can be scheduled when sufficient
368 (R) the "Ready" list of unscheduled, uncommitted insns.
369 (S) the "Scheduled" list of insns.
371 Initially, all insns are either "Pending" or "Ready" depending on
372 whether their dependencies are satisfied.
374 Insns move from the "Ready" list to the "Scheduled" list as they
375 are committed to the schedule. As this occurs, the insns in the
376 "Pending" list have their dependencies satisfied and move to either
377 the "Ready" list or the "Queued" set depending on whether
378 sufficient time has passed to make them ready. As time passes,
379 insns move from the "Queued" set to the "Ready" list. Insns may
380 move from the "Ready" list to the "Queued" set if they are blocked
381 due to a function unit conflict.
383 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
384 insns, i.e., those that are ready, queued, and pending.
385 The "Queued" set (Q) is implemented by the variable `insn_queue'.
386 The "Ready" list (R) is implemented by the variables `ready' and
388 The "Scheduled" list (S) is the new insn chain built by this pass.
390 The transition (R->S) is implemented in the scheduling loop in
391 `schedule_block' when the best insn to schedule is chosen.
392 The transition (R->Q) is implemented in `queue_insn' when an
393 insn is found to have a function unit conflict with the already
395 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
396 insns move from the ready list to the scheduled list.
397 The transition (Q->R) is implemented in 'queue_to_insn' as time
398 passes or stalls are introduced. */
400 /* Implement a circular buffer to delay instructions until sufficient
401 time has passed. INSN_QUEUE_SIZE is a power of two larger than
402 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
403 longest time an isnsn may be queued. */
404 static rtx insn_queue[INSN_QUEUE_SIZE];
405 static int q_ptr = 0;
406 static int q_size = 0;
407 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
408 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
410 /* Vector indexed by INSN_UID giving the minimum clock tick at which
411 the insn becomes ready. This is used to note timing constraints for
412 insns in the pending list. */
413 static int *insn_tick;
414 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
416 /* Data structure for keeping track of register information
417 during that register's life. */
426 /* Forward declarations. */
427 static void add_dependence PROTO ((rtx, rtx, enum reg_note));
428 static void remove_dependence PROTO ((rtx, rtx));
429 static rtx find_insn_list PROTO ((rtx, rtx));
430 static int insn_unit PROTO ((rtx));
431 static unsigned int blockage_range PROTO ((int, rtx));
432 static void clear_units PROTO ((void));
433 static int actual_hazard_this_instance PROTO ((int, int, rtx, int, int));
434 static void schedule_unit PROTO ((int, rtx, int));
435 static int actual_hazard PROTO ((int, rtx, int, int));
436 static int potential_hazard PROTO ((int, rtx, int));
437 static int insn_cost PROTO ((rtx, rtx, rtx));
438 static int priority PROTO ((rtx));
439 static void free_pending_lists PROTO ((void));
440 static void add_insn_mem_dependence PROTO ((rtx *, rtx *, rtx, rtx));
441 static void flush_pending_lists PROTO ((rtx, int));
442 static void sched_analyze_1 PROTO ((rtx, rtx));
443 static void sched_analyze_2 PROTO ((rtx, rtx));
444 static void sched_analyze_insn PROTO ((rtx, rtx, rtx));
445 static void sched_analyze PROTO ((rtx, rtx));
446 static void sched_note_set PROTO ((rtx, int));
447 static int rank_for_schedule PROTO ((const PTR, const PTR));
448 static void swap_sort PROTO ((rtx *, int));
449 static void queue_insn PROTO ((rtx, int));
450 static int schedule_insn PROTO ((rtx, rtx *, int, int));
451 static void create_reg_dead_note PROTO ((rtx, rtx));
452 static void attach_deaths PROTO ((rtx, rtx, int));
453 static void attach_deaths_insn PROTO ((rtx));
454 static int new_sometimes_live PROTO ((struct sometimes *, int, int));
455 static void finish_sometimes_live PROTO ((struct sometimes *, int));
456 static int schedule_block PROTO ((int, int));
457 static char *safe_concat PROTO ((char *, char *, const char *));
458 static int insn_issue_delay PROTO ((rtx));
459 static int birthing_insn_p PROTO ((rtx));
460 static void adjust_priority PROTO ((rtx));
462 /* Mapping of insns to their original block prior to scheduling. */
463 static int *insn_orig_block;
464 #define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
466 /* Some insns (e.g. call) are not allowed to move across blocks. */
467 static char *cant_move;
468 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
470 /* Control flow graph edges are kept in circular lists. */
479 static haifa_edge *edge_table;
481 #define NEXT_IN(edge) (edge_table[edge].next_in)
482 #define NEXT_OUT(edge) (edge_table[edge].next_out)
483 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
484 #define TO_BLOCK(edge) (edge_table[edge].to_block)
486 /* Number of edges in the control flow graph. (In fact, larger than
487 that by 1, since edge 0 is unused.) */
490 /* Circular list of incoming/outgoing edges of a block. */
491 static int *in_edges;
492 static int *out_edges;
494 #define IN_EDGES(block) (in_edges[block])
495 #define OUT_EDGES(block) (out_edges[block])
499 static int is_cfg_nonregular PROTO ((void));
500 static int build_control_flow PROTO ((int_list_ptr *, int_list_ptr *,
502 static void new_edge PROTO ((int, int));
505 /* A region is the main entity for interblock scheduling: insns
506 are allowed to move between blocks in the same region, along
507 control flow graph edges, in the 'up' direction. */
510 int rgn_nr_blocks; /* Number of blocks in region. */
511 int rgn_blocks; /* cblocks in the region (actually index in rgn_bb_table). */
515 /* Number of regions in the procedure. */
516 static int nr_regions;
518 /* Table of region descriptions. */
519 static region *rgn_table;
521 /* Array of lists of regions' blocks. */
522 static int *rgn_bb_table;
524 /* Topological order of blocks in the region (if b2 is reachable from
525 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
526 always referred to by either block or b, while its topological
527 order name (in the region) is refered to by bb. */
528 static int *block_to_bb;
530 /* The number of the region containing a block. */
531 static int *containing_rgn;
533 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
534 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
535 #define BLOCK_TO_BB(block) (block_to_bb[block])
536 #define CONTAINING_RGN(block) (containing_rgn[block])
538 void debug_regions PROTO ((void));
539 static void find_single_block_region PROTO ((void));
540 static void find_rgns PROTO ((int_list_ptr *, int_list_ptr *,
541 int *, int *, sbitmap *));
542 static int too_large PROTO ((int, int *, int *));
544 extern void debug_live PROTO ((int, int));
546 /* Blocks of the current region being scheduled. */
547 static int current_nr_blocks;
548 static int current_blocks;
550 /* The mapping from bb to block. */
551 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
554 /* Bit vectors and bitset operations are needed for computations on
555 the control flow graph. */
557 typedef unsigned HOST_WIDE_INT *bitset;
560 int *first_member; /* Pointer to the list start in bitlst_table. */
561 int nr_members; /* The number of members of the bit list. */
565 static int bitlst_table_last;
566 static int bitlst_table_size;
567 static int *bitlst_table;
569 static char bitset_member PROTO ((bitset, int, int));
570 static void extract_bitlst PROTO ((bitset, int, bitlst *));
572 /* Target info declarations.
574 The block currently being scheduled is referred to as the "target" block,
575 while other blocks in the region from which insns can be moved to the
576 target are called "source" blocks. The candidate structure holds info
577 about such sources: are they valid? Speculative? Etc. */
578 typedef bitlst bblst;
589 static candidate *candidate_table;
591 /* A speculative motion requires checking live information on the path
592 from 'source' to 'target'. The split blocks are those to be checked.
593 After a speculative motion, live information should be modified in
596 Lists of split and update blocks for each candidate of the current
597 target are in array bblst_table. */
598 static int *bblst_table, bblst_size, bblst_last;
600 #define IS_VALID(src) ( candidate_table[src].is_valid )
601 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
602 #define SRC_PROB(src) ( candidate_table[src].src_prob )
604 /* The bb being currently scheduled. */
605 static int target_bb;
608 typedef bitlst edgelst;
610 /* Target info functions. */
611 static void split_edges PROTO ((int, int, edgelst *));
612 static void compute_trg_info PROTO ((int));
613 void debug_candidate PROTO ((int));
614 void debug_candidates PROTO ((int));
617 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
618 typedef bitset bbset;
620 /* Number of words of the bbset. */
621 static int bbset_size;
623 /* Dominators array: dom[i] contains the bbset of dominators of
624 bb i in the region. */
627 /* bb 0 is the only region entry. */
628 #define IS_RGN_ENTRY(bb) (!bb)
630 /* Is bb_src dominated by bb_trg. */
631 #define IS_DOMINATED(bb_src, bb_trg) \
632 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
634 /* Probability: Prob[i] is a float in [0, 1] which is the probability
635 of bb i relative to the region entry. */
638 /* The probability of bb_src, relative to bb_trg. Note, that while the
639 'prob[bb]' is a float in [0, 1], this macro returns an integer
641 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
644 /* Bit-set of edges, where bit i stands for edge i. */
645 typedef bitset edgeset;
647 /* Number of edges in the region. */
648 static int rgn_nr_edges;
650 /* Array of size rgn_nr_edges. */
651 static int *rgn_edges;
653 /* Number of words in an edgeset. */
654 static int edgeset_size;
656 /* Mapping from each edge in the graph to its number in the rgn. */
657 static int *edge_to_bit;
658 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
660 /* The split edges of a source bb is different for each target
661 bb. In order to compute this efficiently, the 'potential-split edges'
662 are computed for each bb prior to scheduling a region. This is actually
663 the split edges of each bb relative to the region entry.
665 pot_split[bb] is the set of potential split edges of bb. */
666 static edgeset *pot_split;
668 /* For every bb, a set of its ancestor edges. */
669 static edgeset *ancestor_edges;
671 static void compute_dom_prob_ps PROTO ((int));
673 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
674 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
675 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
676 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
678 /* Parameters affecting the decision of rank_for_schedule(). */
679 #define MIN_DIFF_PRIORITY 2
680 #define MIN_PROBABILITY 40
681 #define MIN_PROB_DIFF 10
683 /* Speculative scheduling functions. */
684 static int check_live_1 PROTO ((int, rtx));
685 static void update_live_1 PROTO ((int, rtx));
686 static int check_live PROTO ((rtx, int));
687 static void update_live PROTO ((rtx, int));
688 static void set_spec_fed PROTO ((rtx));
689 static int is_pfree PROTO ((rtx, int, int));
690 static int find_conditional_protection PROTO ((rtx, int));
691 static int is_conditionally_protected PROTO ((rtx, int, int));
692 static int may_trap_exp PROTO ((rtx, int));
693 static int haifa_classify_insn PROTO ((rtx));
694 static int is_prisky PROTO ((rtx, int, int));
695 static int is_exception_free PROTO ((rtx, int, int));
697 static char find_insn_mem_list PROTO ((rtx, rtx, rtx, rtx));
698 static void compute_block_forward_dependences PROTO ((int));
699 static void init_rgn_data_dependences PROTO ((int));
700 static void add_branch_dependences PROTO ((rtx, rtx));
701 static void compute_block_backward_dependences PROTO ((int));
702 void debug_dependencies PROTO ((void));
704 /* Notes handling mechanism:
705 =========================
706 Generally, NOTES are saved before scheduling and restored after scheduling.
707 The scheduler distinguishes between three types of notes:
709 (1) LINE_NUMBER notes, generated and used for debugging. Here,
710 before scheduling a region, a pointer to the LINE_NUMBER note is
711 added to the insn following it (in save_line_notes()), and the note
712 is removed (in rm_line_notes() and unlink_line_notes()). After
713 scheduling the region, this pointer is used for regeneration of
714 the LINE_NUMBER note (in restore_line_notes()).
716 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
717 Before scheduling a region, a pointer to the note is added to the insn
718 that follows or precedes it. (This happens as part of the data dependence
719 computation). After scheduling an insn, the pointer contained in it is
720 used for regenerating the corresponding note (in reemit_notes).
722 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
723 these notes are put in a list (in rm_other_notes() and
724 unlink_other_notes ()). After scheduling the block, these notes are
725 inserted at the beginning of the block (in schedule_block()). */
727 static rtx unlink_other_notes PROTO ((rtx, rtx));
728 static rtx unlink_line_notes PROTO ((rtx, rtx));
729 static void rm_line_notes PROTO ((int));
730 static void save_line_notes PROTO ((int));
731 static void restore_line_notes PROTO ((int));
732 static void rm_redundant_line_notes PROTO ((void));
733 static void rm_other_notes PROTO ((rtx, rtx));
734 static rtx reemit_notes PROTO ((rtx, rtx));
736 static void get_block_head_tail PROTO ((int, rtx *, rtx *));
738 static void find_pre_sched_live PROTO ((int));
739 static void find_post_sched_live PROTO ((int));
740 static void update_reg_usage PROTO ((void));
741 static int queue_to_ready PROTO ((rtx [], int));
743 static void debug_ready_list PROTO ((rtx[], int));
744 static void init_target_units PROTO ((void));
745 static void insn_print_units PROTO ((rtx));
746 static int get_visual_tbl_length PROTO ((void));
747 static void init_block_visualization PROTO ((void));
748 static void print_block_visualization PROTO ((int, const char *));
749 static void visualize_scheduled_insns PROTO ((int, int));
750 static void visualize_no_unit PROTO ((rtx));
751 static void visualize_stall_cycles PROTO ((int, int));
752 static void print_exp PROTO ((char *, rtx, int));
753 static void print_value PROTO ((char *, rtx, int));
754 static void print_pattern PROTO ((char *, rtx, int));
755 static void print_insn PROTO ((char *, rtx, int));
756 void debug_reg_vector PROTO ((regset));
758 static rtx move_insn1 PROTO ((rtx, rtx));
759 static rtx move_insn PROTO ((rtx, rtx));
760 static rtx group_leader PROTO ((rtx));
761 static int set_priorities PROTO ((int));
762 static void init_rtx_vector PROTO ((rtx **, rtx *, int, int));
763 static void schedule_region PROTO ((int));
765 #endif /* INSN_SCHEDULING */
767 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
769 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
770 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
771 of dependence that this link represents. */
774 add_dependence (insn, elem, dep_type)
777 enum reg_note dep_type;
781 /* Don't depend an insn on itself. */
785 /* We can get a dependency on deleted insns due to optimizations in
786 the register allocation and reloading or due to splitting. Any
787 such dependency is useless and can be ignored. */
788 if (GET_CODE (elem) == NOTE)
791 /* If elem is part of a sequence that must be scheduled together, then
792 make the dependence point to the last insn of the sequence.
793 When HAVE_cc0, it is possible for NOTEs to exist between users and
794 setters of the condition codes, so we must skip past notes here.
795 Otherwise, NOTEs are impossible here. */
797 next = NEXT_INSN (elem);
800 while (next && GET_CODE (next) == NOTE)
801 next = NEXT_INSN (next);
804 if (next && SCHED_GROUP_P (next)
805 && GET_CODE (next) != CODE_LABEL)
807 /* Notes will never intervene here though, so don't bother checking
809 /* We must reject CODE_LABELs, so that we don't get confused by one
810 that has LABEL_PRESERVE_P set, which is represented by the same
811 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
813 while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
814 && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
815 next = NEXT_INSN (next);
817 /* Again, don't depend an insn on itself. */
821 /* Make the dependence to NEXT, the last insn of the group, instead
822 of the original ELEM. */
826 #ifdef INSN_SCHEDULING
827 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
828 No need for interblock dependences with calls, since
829 calls are not moved between blocks. Note: the edge where
830 elem is a CALL is still required. */
831 if (GET_CODE (insn) == CALL_INSN
832 && (INSN_BB (elem) != INSN_BB (insn)))
837 /* Check that we don't already have this dependence. */
838 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
839 if (XEXP (link, 0) == elem)
841 /* If this is a more restrictive type of dependence than the existing
842 one, then change the existing dependence to this type. */
843 if ((int) dep_type < (int) REG_NOTE_KIND (link))
844 PUT_REG_NOTE_KIND (link, dep_type);
847 /* Might want to check one level of transitivity to save conses. */
849 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
850 LOG_LINKS (insn) = link;
852 /* Insn dependency, not data dependency. */
853 PUT_REG_NOTE_KIND (link, dep_type);
856 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
857 of INSN. Abort if not found. */
860 remove_dependence (insn, elem)
864 rtx prev, link, next;
867 for (prev = 0, link = LOG_LINKS (insn); link; link = next)
869 next = XEXP (link, 1);
870 if (XEXP (link, 0) == elem)
873 XEXP (prev, 1) = next;
875 LOG_LINKS (insn) = next;
876 free_INSN_LIST_node (link);
889 #ifndef INSN_SCHEDULING
891 schedule_insns (dump_file)
901 #define HAIFA_INLINE __inline
904 /* Computation of memory dependencies. */
906 /* The *_insns and *_mems are paired lists. Each pending memory operation
907 will have a pointer to the MEM rtx on one list and a pointer to the
908 containing insn on the other list in the same place in the list. */
910 /* We can't use add_dependence like the old code did, because a single insn
911 may have multiple memory accesses, and hence needs to be on the list
912 once for each memory access. Add_dependence won't let you add an insn
913 to a list more than once. */
915 /* An INSN_LIST containing all insns with pending read operations. */
916 static rtx pending_read_insns;
918 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
919 static rtx pending_read_mems;
921 /* An INSN_LIST containing all insns with pending write operations. */
922 static rtx pending_write_insns;
924 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
925 static rtx pending_write_mems;
927 /* Indicates the combined length of the two pending lists. We must prevent
928 these lists from ever growing too large since the number of dependencies
929 produced is at least O(N*N), and execution time is at least O(4*N*N), as
930 a function of the length of these pending lists. */
932 static int pending_lists_length;
934 /* The last insn upon which all memory references must depend.
935 This is an insn which flushed the pending lists, creating a dependency
936 between it and all previously pending memory references. This creates
937 a barrier (or a checkpoint) which no memory reference is allowed to cross.
939 This includes all non constant CALL_INSNs. When we do interprocedural
940 alias analysis, this restriction can be relaxed.
941 This may also be an INSN that writes memory if the pending lists grow
944 static rtx last_pending_memory_flush;
946 /* The last function call we have seen. All hard regs, and, of course,
947 the last function call, must depend on this. */
949 static rtx last_function_call;
951 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
952 that does not already cross a call. We create dependencies between each
953 of those insn and the next call insn, to ensure that they won't cross a call
954 after scheduling is done. */
956 static rtx sched_before_next_call;
958 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
959 so that insns independent of the last scheduled insn will be preferred
960 over dependent instructions. */
962 static rtx last_scheduled_insn;
964 /* Data structures for the computation of data dependences in a regions. We
965 keep one copy of each of the declared above variables for each bb in the
966 region. Before analyzing the data dependences for a bb, its variables
967 are initialized as a function of the variables of its predecessors. When
968 the analysis for a bb completes, we save the contents of each variable X
969 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
970 copied to bb_pending_read_insns[bb]. Another change is that few
971 variables are now a list of insns rather than a single insn:
972 last_pending_memory_flash, last_function_call, reg_last_sets. The
973 manipulation of these variables was changed appropriately. */
975 static rtx **bb_reg_last_uses;
976 static rtx **bb_reg_last_sets;
977 static rtx **bb_reg_last_clobbers;
979 static rtx *bb_pending_read_insns;
980 static rtx *bb_pending_read_mems;
981 static rtx *bb_pending_write_insns;
982 static rtx *bb_pending_write_mems;
983 static int *bb_pending_lists_length;
985 static rtx *bb_last_pending_memory_flush;
986 static rtx *bb_last_function_call;
987 static rtx *bb_sched_before_next_call;
989 /* Functions for construction of the control flow graph. */
991 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
993 We decide not to build the control flow graph if there is possibly more
994 than one entry to the function, if computed branches exist, of if we
995 have nonlocal gotos. */
1004 /* If we have a label that could be the target of a nonlocal goto, then
1005 the cfg is not well structured. */
1006 if (nonlocal_goto_handler_labels)
1009 /* If we have any forced labels, then the cfg is not well structured. */
1013 /* If this function has a computed jump, then we consider the cfg
1014 not well structured. */
1015 if (current_function_has_computed_jump)
1018 /* If we have exception handlers, then we consider the cfg not well
1019 structured. ?!? We should be able to handle this now that flow.c
1020 computes an accurate cfg for EH. */
1021 if (exception_handler_labels)
1024 /* If we have non-jumping insns which refer to labels, then we consider
1025 the cfg not well structured. */
1026 /* Check for labels referred to other thn by jumps. */
1027 for (b = 0; b < n_basic_blocks; b++)
1028 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
1030 code = GET_CODE (insn);
1031 if (GET_RTX_CLASS (code) == 'i')
1035 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1036 if (REG_NOTE_KIND (note) == REG_LABEL)
1040 if (insn == BLOCK_END (b))
1044 /* All the tests passed. Consider the cfg well structured. */
1048 /* Build the control flow graph and set nr_edges.
1050 Instead of trying to build a cfg ourselves, we rely on flow to
1051 do it for us. Stamp out useless code (and bug) duplication.
1053 Return nonzero if an irregularity in the cfg is found which would
1054 prevent cross block scheduling. */
1057 build_control_flow (s_preds, s_succs, num_preds, num_succs)
1058 int_list_ptr *s_preds;
1059 int_list_ptr *s_succs;
1067 /* Count the number of edges in the cfg. */
1070 for (i = 0; i < n_basic_blocks; i++)
1072 nr_edges += num_succs[i];
1074 /* Unreachable loops with more than one basic block are detected
1075 during the DFS traversal in find_rgns.
1077 Unreachable loops with a single block are detected here. This
1078 test is redundant with the one in find_rgns, but it's much
1079 cheaper to go ahead and catch the trivial case here. */
1080 if (num_preds[i] == 0
1081 || (num_preds[i] == 1 && INT_LIST_VAL (s_preds[i]) == i))
1085 /* Account for entry/exit edges. */
1088 in_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
1089 out_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
1090 edge_table = (haifa_edge *) xcalloc (nr_edges, sizeof (haifa_edge));
1093 for (i = 0; i < n_basic_blocks; i++)
1094 for (succ = s_succs[i]; succ; succ = succ->next)
1096 if (INT_LIST_VAL (succ) != EXIT_BLOCK)
1097 new_edge (i, INT_LIST_VAL (succ));
1100 /* Increment by 1, since edge 0 is unused. */
1107 /* Record an edge in the control flow graph from SOURCE to TARGET.
1109 In theory, this is redundant with the s_succs computed above, but
1110 we have not converted all of haifa to use information from the
1114 new_edge (source, target)
1118 int curr_edge, fst_edge;
1120 /* Check for duplicates. */
1121 fst_edge = curr_edge = OUT_EDGES (source);
1124 if (FROM_BLOCK (curr_edge) == source
1125 && TO_BLOCK (curr_edge) == target)
1130 curr_edge = NEXT_OUT (curr_edge);
1132 if (fst_edge == curr_edge)
1138 FROM_BLOCK (e) = source;
1139 TO_BLOCK (e) = target;
1141 if (OUT_EDGES (source))
1143 next_edge = NEXT_OUT (OUT_EDGES (source));
1144 NEXT_OUT (OUT_EDGES (source)) = e;
1145 NEXT_OUT (e) = next_edge;
1149 OUT_EDGES (source) = e;
1153 if (IN_EDGES (target))
1155 next_edge = NEXT_IN (IN_EDGES (target));
1156 NEXT_IN (IN_EDGES (target)) = e;
1157 NEXT_IN (e) = next_edge;
1161 IN_EDGES (target) = e;
1167 /* BITSET macros for operations on the control flow graph. */
1169 /* Compute bitwise union of two bitsets. */
1170 #define BITSET_UNION(set1, set2, len) \
1171 do { register bitset tp = set1, sp = set2; \
1173 for (i = 0; i < len; i++) \
1174 *(tp++) |= *(sp++); } while (0)
1176 /* Compute bitwise intersection of two bitsets. */
1177 #define BITSET_INTER(set1, set2, len) \
1178 do { register bitset tp = set1, sp = set2; \
1180 for (i = 0; i < len; i++) \
1181 *(tp++) &= *(sp++); } while (0)
1183 /* Compute bitwise difference of two bitsets. */
1184 #define BITSET_DIFFER(set1, set2, len) \
1185 do { register bitset tp = set1, sp = set2; \
1187 for (i = 0; i < len; i++) \
1188 *(tp++) &= ~*(sp++); } while (0)
1190 /* Inverts every bit of bitset 'set'. */
1191 #define BITSET_INVERT(set, len) \
1192 do { register bitset tmpset = set; \
1194 for (i = 0; i < len; i++, tmpset++) \
1195 *tmpset = ~*tmpset; } while (0)
1197 /* Turn on the index'th bit in bitset set. */
1198 #define BITSET_ADD(set, index, len) \
1200 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1203 set[index/HOST_BITS_PER_WIDE_INT] |= \
1204 1 << (index % HOST_BITS_PER_WIDE_INT); \
1207 /* Turn off the index'th bit in set. */
1208 #define BITSET_REMOVE(set, index, len) \
1210 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1213 set[index/HOST_BITS_PER_WIDE_INT] &= \
1214 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1218 /* Check if the index'th bit in bitset set is on. */
1221 bitset_member (set, index, len)
1225 if (index >= HOST_BITS_PER_WIDE_INT * len)
1227 return (set[index / HOST_BITS_PER_WIDE_INT] &
1228 1 << (index % HOST_BITS_PER_WIDE_INT)) ? 1 : 0;
1232 /* Translate a bit-set SET to a list BL of the bit-set members. */
1235 extract_bitlst (set, len, bl)
1241 unsigned HOST_WIDE_INT word;
1243 /* bblst table space is reused in each call to extract_bitlst. */
1244 bitlst_table_last = 0;
1246 bl->first_member = &bitlst_table[bitlst_table_last];
1249 for (i = 0; i < len; i++)
1252 offset = i * HOST_BITS_PER_WIDE_INT;
1253 for (j = 0; word; j++)
1257 bitlst_table[bitlst_table_last++] = offset;
1268 /* Functions for the construction of regions. */
1270 /* Print the regions, for debugging purposes. Callable from debugger. */
1277 fprintf (dump, "\n;; ------------ REGIONS ----------\n\n");
1278 for (rgn = 0; rgn < nr_regions; rgn++)
1280 fprintf (dump, ";;\trgn %d nr_blocks %d:\n", rgn,
1281 rgn_table[rgn].rgn_nr_blocks);
1282 fprintf (dump, ";;\tbb/block: ");
1284 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
1286 current_blocks = RGN_BLOCKS (rgn);
1288 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
1291 fprintf (dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
1294 fprintf (dump, "\n\n");
1299 /* Build a single block region for each basic block in the function.
1300 This allows for using the same code for interblock and basic block
1304 find_single_block_region ()
1308 for (i = 0; i < n_basic_blocks; i++)
1310 rgn_bb_table[i] = i;
1311 RGN_NR_BLOCKS (i) = 1;
1313 CONTAINING_RGN (i) = i;
1314 BLOCK_TO_BB (i) = 0;
1316 nr_regions = n_basic_blocks;
1320 /* Update number of blocks and the estimate for number of insns
1321 in the region. Return 1 if the region is "too large" for interblock
1322 scheduling (compile time considerations), otherwise return 0. */
1325 too_large (block, num_bbs, num_insns)
1326 int block, *num_bbs, *num_insns;
1329 (*num_insns) += (INSN_LUID (BLOCK_END (block)) -
1330 INSN_LUID (BLOCK_HEAD (block)));
1331 if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
1338 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1339 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1340 loop containing blk. */
1341 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1343 if (max_hdr[blk] == -1) \
1344 max_hdr[blk] = hdr; \
1345 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1346 RESET_BIT (inner, hdr); \
1347 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1349 RESET_BIT (inner,max_hdr[blk]); \
1350 max_hdr[blk] = hdr; \
1355 /* Find regions for interblock scheduling.
1357 A region for scheduling can be:
1359 * A loop-free procedure, or
1361 * A reducible inner loop, or
1363 * A basic block not contained in any other region.
1366 ?!? In theory we could build other regions based on extended basic
1367 blocks or reverse extended basic blocks. Is it worth the trouble?
1369 Loop blocks that form a region are put into the region's block list
1370 in topological order.
1372 This procedure stores its results into the following global (ick) variables
1381 We use dominator relationships to avoid making regions out of non-reducible
1384 This procedure needs to be converted to work on pred/succ lists instead
1385 of edge tables. That would simplify it somewhat. */
1388 find_rgns (s_preds, s_succs, num_preds, num_succs, dom)
1389 int_list_ptr *s_preds;
1390 int_list_ptr *s_succs;
1395 int *max_hdr, *dfs_nr, *stack, *queue, *degree;
1397 int node, child, loop_head, i, head, tail;
1398 int count = 0, sp, idx = 0, current_edge = out_edges[0];
1399 int num_bbs, num_insns, unreachable;
1400 int too_large_failure;
1402 /* Note if an edge has been passed. */
1405 /* Note if a block is a natural loop header. */
1408 /* Note if a block is an natural inner loop header. */
1411 /* Note if a block is in the block queue. */
1414 /* Note if a block is in the block queue. */
1417 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1418 and a mapping from block to its loop header (if the block is contained
1419 in a loop, else -1).
1421 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1422 be used as inputs to the second traversal.
1424 STACK, SP and DFS_NR are only used during the first traversal. */
1426 /* Allocate and initialize variables for the first traversal. */
1427 max_hdr = (int *) alloca (n_basic_blocks * sizeof (int));
1428 dfs_nr = (int *) alloca (n_basic_blocks * sizeof (int));
1429 bzero ((char *) dfs_nr, n_basic_blocks * sizeof (int));
1430 stack = (int *) alloca (nr_edges * sizeof (int));
1432 inner = sbitmap_alloc (n_basic_blocks);
1433 sbitmap_ones (inner);
1435 header = sbitmap_alloc (n_basic_blocks);
1436 sbitmap_zero (header);
1438 passed = sbitmap_alloc (nr_edges);
1439 sbitmap_zero (passed);
1441 in_queue = sbitmap_alloc (n_basic_blocks);
1442 sbitmap_zero (in_queue);
1444 in_stack = sbitmap_alloc (n_basic_blocks);
1445 sbitmap_zero (in_stack);
1447 for (i = 0; i < n_basic_blocks; i++)
1450 /* DFS traversal to find inner loops in the cfg. */
1455 if (current_edge == 0 || TEST_BIT (passed, current_edge))
1457 /* We have reached a leaf node or a node that was already
1458 processed. Pop edges off the stack until we find
1459 an edge that has not yet been processed. */
1461 && (current_edge == 0 || TEST_BIT (passed, current_edge)))
1463 /* Pop entry off the stack. */
1464 current_edge = stack[sp--];
1465 node = FROM_BLOCK (current_edge);
1466 child = TO_BLOCK (current_edge);
1467 RESET_BIT (in_stack, child);
1468 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1469 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1470 current_edge = NEXT_OUT (current_edge);
1473 /* See if have finished the DFS tree traversal. */
1474 if (sp < 0 && TEST_BIT (passed, current_edge))
1477 /* Nope, continue the traversal with the popped node. */
1481 /* Process a node. */
1482 node = FROM_BLOCK (current_edge);
1483 child = TO_BLOCK (current_edge);
1484 SET_BIT (in_stack, node);
1485 dfs_nr[node] = ++count;
1487 /* If the successor is in the stack, then we've found a loop.
1488 Mark the loop, if it is not a natural loop, then it will
1489 be rejected during the second traversal. */
1490 if (TEST_BIT (in_stack, child))
1493 SET_BIT (header, child);
1494 UPDATE_LOOP_RELATIONS (node, child);
1495 SET_BIT (passed, current_edge);
1496 current_edge = NEXT_OUT (current_edge);
1500 /* If the child was already visited, then there is no need to visit
1501 it again. Just update the loop relationships and restart
1505 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1506 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1507 SET_BIT (passed, current_edge);
1508 current_edge = NEXT_OUT (current_edge);
1512 /* Push an entry on the stack and continue DFS traversal. */
1513 stack[++sp] = current_edge;
1514 SET_BIT (passed, current_edge);
1515 current_edge = OUT_EDGES (child);
1517 /* This is temporary until haifa is converted to use rth's new
1518 cfg routines which have true entry/exit blocks and the
1519 appropriate edges from/to those blocks.
1521 Generally we update dfs_nr for a node when we process its
1522 out edge. However, if the node has no out edge then we will
1523 not set dfs_nr for that node. This can confuse the scheduler
1524 into thinking that we have unreachable blocks, which in turn
1525 disables cross block scheduling.
1527 So, if we have a node with no out edges, go ahead and mark it
1528 as reachable now. */
1529 if (current_edge == 0)
1530 dfs_nr[child] = ++count;
1533 /* Another check for unreachable blocks. The earlier test in
1534 is_cfg_nonregular only finds unreachable blocks that do not
1537 The DFS traversal will mark every block that is reachable from
1538 the entry node by placing a nonzero value in dfs_nr. Thus if
1539 dfs_nr is zero for any block, then it must be unreachable. */
1541 for (i = 0; i < n_basic_blocks; i++)
1548 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1549 to hold degree counts. */
1552 /* Compute the in-degree of every block in the graph. */
1553 for (i = 0; i < n_basic_blocks; i++)
1554 degree[i] = num_preds[i];
1556 /* Do not perform region scheduling if there are any unreachable
1561 SET_BIT (header, 0);
1563 /* Second travsersal:find reducible inner loops and topologically sort
1564 block of each region. */
1566 queue = (int *) alloca (n_basic_blocks * sizeof (int));
1568 /* Find blocks which are inner loop headers. We still have non-reducible
1569 loops to consider at this point. */
1570 for (i = 0; i < n_basic_blocks; i++)
1572 if (TEST_BIT (header, i) && TEST_BIT (inner, i))
1577 /* Now check that the loop is reducible. We do this separate
1578 from finding inner loops so that we do not find a reducible
1579 loop which contains an inner non-reducible loop.
1581 A simple way to find reducible/natural loops is to verify
1582 that each block in the loop is dominated by the loop
1585 If there exists a block that is not dominated by the loop
1586 header, then the block is reachable from outside the loop
1587 and thus the loop is not a natural loop. */
1588 for (j = 0; j < n_basic_blocks; j++)
1590 /* First identify blocks in the loop, except for the loop
1592 if (i == max_hdr[j] && i != j)
1594 /* Now verify that the block is dominated by the loop
1596 if (!TEST_BIT (dom[j], i))
1601 /* If we exited the loop early, then I is the header of
1602 a non-reducible loop and we should quit processing it
1604 if (j != n_basic_blocks)
1607 /* I is a header of an inner loop, or block 0 in a subroutine
1608 with no loops at all. */
1610 too_large_failure = 0;
1611 loop_head = max_hdr[i];
1613 /* Decrease degree of all I's successors for topological
1615 for (ps = s_succs[i]; ps; ps = ps->next)
1616 if (INT_LIST_VAL (ps) != EXIT_BLOCK
1617 && INT_LIST_VAL (ps) != ENTRY_BLOCK)
1618 --degree[INT_LIST_VAL(ps)];
1620 /* Estimate # insns, and count # blocks in the region. */
1622 num_insns = (INSN_LUID (BLOCK_END (i))
1623 - INSN_LUID (BLOCK_HEAD (i)));
1626 /* Find all loop latches (blocks with back edges to the loop
1627 header) or all the leaf blocks in the cfg has no loops.
1629 Place those blocks into the queue. */
1632 for (j = 0; j < n_basic_blocks; j++)
1633 /* Leaf nodes have only a single successor which must
1635 if (num_succs[j] == 1
1636 && INT_LIST_VAL (s_succs[j]) == EXIT_BLOCK)
1639 SET_BIT (in_queue, j);
1641 if (too_large (j, &num_bbs, &num_insns))
1643 too_large_failure = 1;
1652 for (ps = s_preds[i]; ps; ps = ps->next)
1654 node = INT_LIST_VAL (ps);
1656 if (node == ENTRY_BLOCK || node == EXIT_BLOCK)
1659 if (max_hdr[node] == loop_head && node != i)
1661 /* This is a loop latch. */
1662 queue[++tail] = node;
1663 SET_BIT (in_queue, node);
1665 if (too_large (node, &num_bbs, &num_insns))
1667 too_large_failure = 1;
1675 /* Now add all the blocks in the loop to the queue.
1677 We know the loop is a natural loop; however the algorithm
1678 above will not always mark certain blocks as being in the
1687 The algorithm in the DFS traversal may not mark B & D as part
1688 of the loop (ie they will not have max_hdr set to A).
1690 We know they can not be loop latches (else they would have
1691 had max_hdr set since they'd have a backedge to a dominator
1692 block). So we don't need them on the initial queue.
1694 We know they are part of the loop because they are dominated
1695 by the loop header and can be reached by a backwards walk of
1696 the edges starting with nodes on the initial queue.
1698 It is safe and desirable to include those nodes in the
1699 loop/scheduling region. To do so we would need to decrease
1700 the degree of a node if it is the target of a backedge
1701 within the loop itself as the node is placed in the queue.
1703 We do not do this because I'm not sure that the actual
1704 scheduling code will properly handle this case. ?!? */
1706 while (head < tail && !too_large_failure)
1709 child = queue[++head];
1711 for (ps = s_preds[child]; ps; ps = ps->next)
1713 node = INT_LIST_VAL (ps);
1715 /* See discussion above about nodes not marked as in
1716 this loop during the initial DFS traversal. */
1717 if (node == ENTRY_BLOCK || node == EXIT_BLOCK
1718 || max_hdr[node] != loop_head)
1723 else if (!TEST_BIT (in_queue, node) && node != i)
1725 queue[++tail] = node;
1726 SET_BIT (in_queue, node);
1728 if (too_large (node, &num_bbs, &num_insns))
1730 too_large_failure = 1;
1737 if (tail >= 0 && !too_large_failure)
1739 /* Place the loop header into list of region blocks. */
1741 rgn_bb_table[idx] = i;
1742 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1743 RGN_BLOCKS (nr_regions) = idx++;
1744 CONTAINING_RGN (i) = nr_regions;
1745 BLOCK_TO_BB (i) = count = 0;
1747 /* Remove blocks from queue[] when their in degree
1748 becomes zero. Repeat until no blocks are left on the
1749 list. This produces a topological list of blocks in
1757 child = queue[head];
1758 if (degree[child] == 0)
1761 rgn_bb_table[idx++] = child;
1762 BLOCK_TO_BB (child) = ++count;
1763 CONTAINING_RGN (child) = nr_regions;
1764 queue[head] = queue[tail--];
1766 for (ps = s_succs[child]; ps; ps = ps->next)
1767 if (INT_LIST_VAL (ps) != ENTRY_BLOCK
1768 && INT_LIST_VAL (ps) != EXIT_BLOCK)
1769 --degree[INT_LIST_VAL (ps)];
1780 /* Any block that did not end up in a region is placed into a region
1782 for (i = 0; i < n_basic_blocks; i++)
1785 rgn_bb_table[idx] = i;
1786 RGN_NR_BLOCKS (nr_regions) = 1;
1787 RGN_BLOCKS (nr_regions) = idx++;
1788 CONTAINING_RGN (i) = nr_regions++;
1789 BLOCK_TO_BB (i) = 0;
1800 /* Functions for regions scheduling information. */
1802 /* Compute dominators, probability, and potential-split-edges of bb.
1803 Assume that these values were already computed for bb's predecessors. */
1806 compute_dom_prob_ps (bb)
1809 int nxt_in_edge, fst_in_edge, pred;
1810 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1813 if (IS_RGN_ENTRY (bb))
1815 BITSET_ADD (dom[bb], 0, bbset_size);
1820 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1822 /* Intialize dom[bb] to '111..1'. */
1823 BITSET_INVERT (dom[bb], bbset_size);
1827 pred = FROM_BLOCK (nxt_in_edge);
1828 BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
1830 BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
1833 BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
1836 nr_rgn_out_edges = 0;
1837 fst_out_edge = OUT_EDGES (pred);
1838 nxt_out_edge = NEXT_OUT (fst_out_edge);
1839 BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
1842 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
1844 /* The successor doesn't belong in the region? */
1845 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1846 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1849 while (fst_out_edge != nxt_out_edge)
1852 /* The successor doesn't belong in the region? */
1853 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1854 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1856 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
1857 nxt_out_edge = NEXT_OUT (nxt_out_edge);
1861 /* Now nr_rgn_out_edges is the number of region-exit edges from
1862 pred, and nr_out_edges will be the number of pred out edges
1863 not leaving the region. */
1864 nr_out_edges -= nr_rgn_out_edges;
1865 if (nr_rgn_out_edges > 0)
1866 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1868 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1869 nxt_in_edge = NEXT_IN (nxt_in_edge);
1871 while (fst_in_edge != nxt_in_edge);
1873 BITSET_ADD (dom[bb], bb, bbset_size);
1874 BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
1876 if (sched_verbose >= 2)
1877 fprintf (dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb), (int) (100.0 * prob[bb]));
1878 } /* compute_dom_prob_ps */
1880 /* Functions for target info. */
1882 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1883 Note that bb_trg dominates bb_src. */
1886 split_edges (bb_src, bb_trg, bl)
1891 int es = edgeset_size;
1892 edgeset src = (edgeset) alloca (es * sizeof (HOST_WIDE_INT));
1895 src[es] = (pot_split[bb_src])[es];
1896 BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
1897 extract_bitlst (src, edgeset_size, bl);
1901 /* Find the valid candidate-source-blocks for the target block TRG, compute
1902 their probability, and check if they are speculative or not.
1903 For speculative sources, compute their update-blocks and split-blocks. */
1906 compute_trg_info (trg)
1909 register candidate *sp;
1911 int check_block, update_idx;
1912 int i, j, k, fst_edge, nxt_edge;
1914 /* Define some of the fields for the target bb as well. */
1915 sp = candidate_table + trg;
1917 sp->is_speculative = 0;
1920 for (i = trg + 1; i < current_nr_blocks; i++)
1922 sp = candidate_table + i;
1924 sp->is_valid = IS_DOMINATED (i, trg);
1927 sp->src_prob = GET_SRC_PROB (i, trg);
1928 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
1933 split_edges (i, trg, &el);
1934 sp->is_speculative = (el.nr_members) ? 1 : 0;
1935 if (sp->is_speculative && !flag_schedule_speculative)
1941 sp->split_bbs.first_member = &bblst_table[bblst_last];
1942 sp->split_bbs.nr_members = el.nr_members;
1943 for (j = 0; j < el.nr_members; bblst_last++, j++)
1944 bblst_table[bblst_last] =
1945 TO_BLOCK (rgn_edges[el.first_member[j]]);
1946 sp->update_bbs.first_member = &bblst_table[bblst_last];
1948 for (j = 0; j < el.nr_members; j++)
1950 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
1951 fst_edge = nxt_edge = OUT_EDGES (check_block);
1954 for (k = 0; k < el.nr_members; k++)
1955 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
1958 if (k >= el.nr_members)
1960 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
1964 nxt_edge = NEXT_OUT (nxt_edge);
1966 while (fst_edge != nxt_edge);
1968 sp->update_bbs.nr_members = update_idx;
1973 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1975 sp->is_speculative = 0;
1979 } /* compute_trg_info */
1982 /* Print candidates info, for debugging purposes. Callable from debugger. */
1988 if (!candidate_table[i].is_valid)
1991 if (candidate_table[i].is_speculative)
1994 fprintf (dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1996 fprintf (dump, "split path: ");
1997 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1999 int b = candidate_table[i].split_bbs.first_member[j];
2001 fprintf (dump, " %d ", b);
2003 fprintf (dump, "\n");
2005 fprintf (dump, "update path: ");
2006 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
2008 int b = candidate_table[i].update_bbs.first_member[j];
2010 fprintf (dump, " %d ", b);
2012 fprintf (dump, "\n");
2016 fprintf (dump, " src %d equivalent\n", BB_TO_BLOCK (i));
2021 /* Print candidates info, for debugging purposes. Callable from debugger. */
2024 debug_candidates (trg)
2029 fprintf (dump, "----------- candidate table: target: b=%d bb=%d ---\n",
2030 BB_TO_BLOCK (trg), trg);
2031 for (i = trg + 1; i < current_nr_blocks; i++)
2032 debug_candidate (i);
2036 /* Functions for speculative scheduing. */
2038 /* Return 0 if x is a set of a register alive in the beginning of one
2039 of the split-blocks of src, otherwise return 1. */
2042 check_live_1 (src, x)
2048 register rtx reg = SET_DEST (x);
2053 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2054 || GET_CODE (reg) == SIGN_EXTRACT
2055 || GET_CODE (reg) == STRICT_LOW_PART)
2056 reg = XEXP (reg, 0);
2058 if (GET_CODE (reg) == PARALLEL
2059 && GET_MODE (reg) == BLKmode)
2062 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2063 if (check_live_1 (src, XVECEXP (reg, 0, i)))
2068 if (GET_CODE (reg) != REG)
2071 regno = REGNO (reg);
2073 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2075 /* Global registers are assumed live. */
2080 if (regno < FIRST_PSEUDO_REGISTER)
2082 /* Check for hard registers. */
2083 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2086 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2088 int b = candidate_table[src].split_bbs.first_member[i];
2090 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
2100 /* Check for psuedo registers. */
2101 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2103 int b = candidate_table[src].split_bbs.first_member[i];
2105 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
2117 /* If x is a set of a register R, mark that R is alive in the beginning
2118 of every update-block of src. */
2121 update_live_1 (src, x)
2127 register rtx reg = SET_DEST (x);
2132 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2133 || GET_CODE (reg) == SIGN_EXTRACT
2134 || GET_CODE (reg) == STRICT_LOW_PART)
2135 reg = XEXP (reg, 0);
2137 if (GET_CODE (reg) == PARALLEL
2138 && GET_MODE (reg) == BLKmode)
2141 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2142 update_live_1 (src, XVECEXP (reg, 0, i));
2146 if (GET_CODE (reg) != REG)
2149 /* Global registers are always live, so the code below does not apply
2152 regno = REGNO (reg);
2154 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
2156 if (regno < FIRST_PSEUDO_REGISTER)
2158 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2161 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2163 int b = candidate_table[src].update_bbs.first_member[i];
2165 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
2172 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2174 int b = candidate_table[src].update_bbs.first_member[i];
2176 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
2183 /* Return 1 if insn can be speculatively moved from block src to trg,
2184 otherwise return 0. Called before first insertion of insn to
2185 ready-list or before the scheduling. */
2188 check_live (insn, src)
2192 /* Find the registers set by instruction. */
2193 if (GET_CODE (PATTERN (insn)) == SET
2194 || GET_CODE (PATTERN (insn)) == CLOBBER)
2195 return check_live_1 (src, PATTERN (insn));
2196 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2199 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2200 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2201 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2202 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
2212 /* Update the live registers info after insn was moved speculatively from
2213 block src to trg. */
2216 update_live (insn, src)
2220 /* Find the registers set by instruction. */
2221 if (GET_CODE (PATTERN (insn)) == SET
2222 || GET_CODE (PATTERN (insn)) == CLOBBER)
2223 update_live_1 (src, PATTERN (insn));
2224 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2227 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2228 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2229 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2230 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
2234 /* Exception Free Loads:
2236 We define five classes of speculative loads: IFREE, IRISKY,
2237 PFREE, PRISKY, and MFREE.
2239 IFREE loads are loads that are proved to be exception-free, just
2240 by examining the load insn. Examples for such loads are loads
2241 from TOC and loads of global data.
2243 IRISKY loads are loads that are proved to be exception-risky,
2244 just by examining the load insn. Examples for such loads are
2245 volatile loads and loads from shared memory.
2247 PFREE loads are loads for which we can prove, by examining other
2248 insns, that they are exception-free. Currently, this class consists
2249 of loads for which we are able to find a "similar load", either in
2250 the target block, or, if only one split-block exists, in that split
2251 block. Load2 is similar to load1 if both have same single base
2252 register. We identify only part of the similar loads, by finding
2253 an insn upon which both load1 and load2 have a DEF-USE dependence.
2255 PRISKY loads are loads for which we can prove, by examining other
2256 insns, that they are exception-risky. Currently we have two proofs for
2257 such loads. The first proof detects loads that are probably guarded by a
2258 test on the memory address. This proof is based on the
2259 backward and forward data dependence information for the region.
2260 Let load-insn be the examined load.
2261 Load-insn is PRISKY iff ALL the following hold:
2263 - insn1 is not in the same block as load-insn
2264 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2265 - test-insn is either a compare or a branch, not in the same block
2267 - load-insn is reachable from test-insn
2268 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2270 This proof might fail when the compare and the load are fed
2271 by an insn not in the region. To solve this, we will add to this
2272 group all loads that have no input DEF-USE dependence.
2274 The second proof detects loads that are directly or indirectly
2275 fed by a speculative load. This proof is affected by the
2276 scheduling process. We will use the flag fed_by_spec_load.
2277 Initially, all insns have this flag reset. After a speculative
2278 motion of an insn, if insn is either a load, or marked as
2279 fed_by_spec_load, we will also mark as fed_by_spec_load every
2280 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2281 load which is fed_by_spec_load is also PRISKY.
2283 MFREE (maybe-free) loads are all the remaining loads. They may be
2284 exception-free, but we cannot prove it.
2286 Now, all loads in IFREE and PFREE classes are considered
2287 exception-free, while all loads in IRISKY and PRISKY classes are
2288 considered exception-risky. As for loads in the MFREE class,
2289 these are considered either exception-free or exception-risky,
2290 depending on whether we are pessimistic or optimistic. We have
2291 to take the pessimistic approach to assure the safety of
2292 speculative scheduling, but we can take the optimistic approach
2293 by invoking the -fsched_spec_load_dangerous option. */
2295 enum INSN_TRAP_CLASS
2297 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
2298 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
2301 #define WORST_CLASS(class1, class2) \
2302 ((class1 > class2) ? class1 : class2)
2304 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between
2305 some speculatively moved load insn and this one. */
2306 char *fed_by_spec_load;
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))), \
2316 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2317 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2319 /* Non-zero iff the address is comprised from at most 1 register. */
2320 #define CONST_BASED_ADDRESS_P(x) \
2321 (GET_CODE (x) == REG \
2322 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2323 || (GET_CODE (x) == LO_SUM)) \
2324 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2325 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2327 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2330 set_spec_fed (load_insn)
2335 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
2336 if (GET_MODE (link) == VOIDmode)
2337 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
2338 } /* set_spec_fed */
2340 /* On the path from the insn to load_insn_bb, find a conditional
2341 branch depending on insn, that guards the speculative load. */
2344 find_conditional_protection (insn, load_insn_bb)
2350 /* Iterate through DEF-USE forward dependences. */
2351 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2353 rtx next = XEXP (link, 0);
2354 if ((CONTAINING_RGN (INSN_BLOCK (next)) ==
2355 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
2356 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
2357 && load_insn_bb != INSN_BB (next)
2358 && GET_MODE (link) == VOIDmode
2359 && (GET_CODE (next) == JUMP_INSN
2360 || find_conditional_protection (next, load_insn_bb)))
2364 } /* find_conditional_protection */
2366 /* Returns 1 if the same insn1 that participates in the computation
2367 of load_insn's address is feeding a conditional branch that is
2368 guarding on load_insn. This is true if we find a the two DEF-USE
2370 insn1 -> ... -> conditional-branch
2371 insn1 -> ... -> load_insn,
2372 and if a flow path exist:
2373 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2374 and if insn1 is on the path
2375 region-entry -> ... -> bb_trg -> ... load_insn.
2377 Locate insn1 by climbing on LOG_LINKS from load_insn.
2378 Locate the branch by following INSN_DEPEND from insn1. */
2381 is_conditionally_protected (load_insn, bb_src, bb_trg)
2387 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
2389 rtx insn1 = XEXP (link, 0);
2391 /* Must be a DEF-USE dependence upon non-branch. */
2392 if (GET_MODE (link) != VOIDmode
2393 || GET_CODE (insn1) == JUMP_INSN)
2396 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
2397 if (INSN_BB (insn1) == bb_src
2398 || (CONTAINING_RGN (INSN_BLOCK (insn1))
2399 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
2400 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
2401 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
2404 /* Now search for the conditional-branch. */
2405 if (find_conditional_protection (insn1, bb_src))
2408 /* Recursive step: search another insn1, "above" current insn1. */
2409 return is_conditionally_protected (insn1, bb_src, bb_trg);
2412 /* The chain does not exist. */
2414 } /* is_conditionally_protected */
2416 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2417 load_insn can move speculatively from bb_src to bb_trg. All the
2418 following must hold:
2420 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2421 (2) load_insn and load1 have a def-use dependence upon
2422 the same insn 'insn1'.
2423 (3) either load2 is in bb_trg, or:
2424 - there's only one split-block, and
2425 - load1 is on the escape path, and
2427 From all these we can conclude that the two loads access memory
2428 addresses that differ at most by a constant, and hence if moving
2429 load_insn would cause an exception, it would have been caused by
2433 is_pfree (load_insn, bb_src, bb_trg)
2438 register candidate *candp = candidate_table + bb_src;
2440 if (candp->split_bbs.nr_members != 1)
2441 /* Must have exactly one escape block. */
2444 for (back_link = LOG_LINKS (load_insn);
2445 back_link; back_link = XEXP (back_link, 1))
2447 rtx insn1 = XEXP (back_link, 0);
2449 if (GET_MODE (back_link) == VOIDmode)
2451 /* Found a DEF-USE dependence (insn1, load_insn). */
2454 for (fore_link = INSN_DEPEND (insn1);
2455 fore_link; fore_link = XEXP (fore_link, 1))
2457 rtx insn2 = XEXP (fore_link, 0);
2458 if (GET_MODE (fore_link) == VOIDmode)
2460 /* Found a DEF-USE dependence (insn1, insn2). */
2461 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
2462 /* insn2 not guaranteed to be a 1 base reg load. */
2465 if (INSN_BB (insn2) == bb_trg)
2466 /* insn2 is the similar load, in the target block. */
2469 if (*(candp->split_bbs.first_member) == INSN_BLOCK (insn2))
2470 /* insn2 is a similar load, in a split-block. */
2477 /* Couldn't find a similar load. */
2481 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2482 as found by analyzing insn's expression. */
2485 may_trap_exp (x, is_store)
2493 code = GET_CODE (x);
2503 /* The insn uses memory: a volatile load. */
2504 if (MEM_VOLATILE_P (x))
2506 /* An exception-free load. */
2507 if (!may_trap_p (x))
2509 /* A load with 1 base register, to be further checked. */
2510 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
2511 return PFREE_CANDIDATE;
2512 /* No info on the load, to be further checked. */
2513 return PRISKY_CANDIDATE;
2518 int i, insn_class = TRAP_FREE;
2520 /* Neither store nor load, check if it may cause a trap. */
2523 /* Recursive step: walk the insn... */
2524 fmt = GET_RTX_FORMAT (code);
2525 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2529 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
2530 insn_class = WORST_CLASS (insn_class, tmp_class);
2532 else if (fmt[i] == 'E')
2535 for (j = 0; j < XVECLEN (x, i); j++)
2537 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
2538 insn_class = WORST_CLASS (insn_class, tmp_class);
2539 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2543 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2548 } /* may_trap_exp */
2551 /* Classifies insn for the purpose of verifying that it can be
2552 moved speculatively, by examining it's patterns, returning:
2553 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2554 TRAP_FREE: non-load insn.
2555 IFREE: load from a globaly safe location.
2556 IRISKY: volatile load.
2557 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2558 being either PFREE or PRISKY. */
2561 haifa_classify_insn (insn)
2564 rtx pat = PATTERN (insn);
2565 int tmp_class = TRAP_FREE;
2566 int insn_class = TRAP_FREE;
2569 if (GET_CODE (pat) == PARALLEL)
2571 int i, len = XVECLEN (pat, 0);
2573 for (i = len - 1; i >= 0; i--)
2575 code = GET_CODE (XVECEXP (pat, 0, i));
2579 /* Test if it is a 'store'. */
2580 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
2583 /* Test if it is a store. */
2584 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
2585 if (tmp_class == TRAP_RISKY)
2587 /* Test if it is a load. */
2589 WORST_CLASS (tmp_class,
2590 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 0));
2593 tmp_class = TRAP_RISKY;
2597 insn_class = WORST_CLASS (insn_class, tmp_class);
2598 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2604 code = GET_CODE (pat);
2608 /* Test if it is a 'store'. */
2609 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
2612 /* Test if it is a store. */
2613 tmp_class = may_trap_exp (SET_DEST (pat), 1);
2614 if (tmp_class == TRAP_RISKY)
2616 /* Test if it is a load. */
2618 WORST_CLASS (tmp_class,
2619 may_trap_exp (SET_SRC (pat), 0));
2622 tmp_class = TRAP_RISKY;
2626 insn_class = tmp_class;
2631 } /* haifa_classify_insn */
2633 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2634 a load moved speculatively, or if load_insn is protected by
2635 a compare on load_insn's address). */
2638 is_prisky (load_insn, bb_src, bb_trg)
2642 if (FED_BY_SPEC_LOAD (load_insn))
2645 if (LOG_LINKS (load_insn) == NULL)
2646 /* Dependence may 'hide' out of the region. */
2649 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2655 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2656 Return 1 if insn is exception-free (and the motion is valid)
2660 is_exception_free (insn, bb_src, bb_trg)
2664 int insn_class = haifa_classify_insn (insn);
2666 /* Handle non-load insns. */
2677 if (!flag_schedule_speculative_load)
2679 IS_LOAD_INSN (insn) = 1;
2686 case PFREE_CANDIDATE:
2687 if (is_pfree (insn, bb_src, bb_trg))
2689 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2690 case PRISKY_CANDIDATE:
2691 if (!flag_schedule_speculative_load_dangerous
2692 || is_prisky (insn, bb_src, bb_trg))
2698 return flag_schedule_speculative_load_dangerous;
2699 } /* is_exception_free */
2702 /* Process an insn's memory dependencies. There are four kinds of
2705 (0) read dependence: read follows read
2706 (1) true dependence: read follows write
2707 (2) anti dependence: write follows read
2708 (3) output dependence: write follows write
2710 We are careful to build only dependencies which actually exist, and
2711 use transitivity to avoid building too many links. */
2713 /* Return the INSN_LIST containing INSN in LIST, or NULL
2714 if LIST does not contain INSN. */
2716 HAIFA_INLINE static rtx
2717 find_insn_list (insn, list)
2723 if (XEXP (list, 0) == insn)
2725 list = XEXP (list, 1);
2731 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0
2734 HAIFA_INLINE static char
2735 find_insn_mem_list (insn, x, list, list1)
2741 if (XEXP (list, 0) == insn
2742 && XEXP (list1, 0) == x)
2744 list = XEXP (list, 1);
2745 list1 = XEXP (list1, 1);
2751 /* Compute the function units used by INSN. This caches the value
2752 returned by function_units_used. A function unit is encoded as the
2753 unit number if the value is non-negative and the compliment of a
2754 mask if the value is negative. A function unit index is the
2755 non-negative encoding. */
2757 HAIFA_INLINE static int
2761 register int unit = INSN_UNIT (insn);
2765 recog_memoized (insn);
2767 /* A USE insn, or something else we don't need to understand.
2768 We can't pass these directly to function_units_used because it will
2769 trigger a fatal error for unrecognizable insns. */
2770 if (INSN_CODE (insn) < 0)
2774 unit = function_units_used (insn);
2775 /* Increment non-negative values so we can cache zero. */
2779 /* We only cache 16 bits of the result, so if the value is out of
2780 range, don't cache it. */
2781 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
2783 || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
2784 INSN_UNIT (insn) = unit;
2786 return (unit > 0 ? unit - 1 : unit);
2789 /* Compute the blockage range for executing INSN on UNIT. This caches
2790 the value returned by the blockage_range_function for the unit.
2791 These values are encoded in an int where the upper half gives the
2792 minimum value and the lower half gives the maximum value. */
2794 HAIFA_INLINE static unsigned int
2795 blockage_range (unit, insn)
2799 unsigned int blockage = INSN_BLOCKAGE (insn);
2802 if ((int) UNIT_BLOCKED (blockage) != unit + 1)
2804 range = function_units[unit].blockage_range_function (insn);
2805 /* We only cache the blockage range for one unit and then only if
2807 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
2808 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
2811 range = BLOCKAGE_RANGE (blockage);
2816 /* A vector indexed by function unit instance giving the last insn to use
2817 the unit. The value of the function unit instance index for unit U
2818 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2819 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2821 /* A vector indexed by function unit instance giving the minimum time when
2822 the unit will unblock based on the maximum blockage cost. */
2823 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2825 /* A vector indexed by function unit number giving the number of insns
2826 that remain to use the unit. */
2827 static int unit_n_insns[FUNCTION_UNITS_SIZE];
2829 /* Reset the function unit state to the null state. */
2834 bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
2835 bzero ((char *) unit_tick, sizeof (unit_tick));
2836 bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
2839 /* Return the issue-delay of an insn. */
2841 HAIFA_INLINE static int
2842 insn_issue_delay (insn)
2846 int unit = insn_unit (insn);
2848 /* Efficiency note: in fact, we are working 'hard' to compute a
2849 value that was available in md file, and is not available in
2850 function_units[] structure. It would be nice to have this
2851 value there, too. */
2854 if (function_units[unit].blockage_range_function &&
2855 function_units[unit].blockage_function)
2856 delay = function_units[unit].blockage_function (insn, insn);
2859 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2860 if ((unit & 1) != 0 && function_units[i].blockage_range_function
2861 && function_units[i].blockage_function)
2862 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
2867 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2868 instance INSTANCE at time CLOCK if the previous actual hazard cost
2871 HAIFA_INLINE static int
2872 actual_hazard_this_instance (unit, instance, insn, clock, cost)
2873 int unit, instance, clock, cost;
2876 int tick = unit_tick[instance]; /* Issue time of the last issued insn. */
2878 if (tick - clock > cost)
2880 /* The scheduler is operating forward, so unit's last insn is the
2881 executing insn and INSN is the candidate insn. We want a
2882 more exact measure of the blockage if we execute INSN at CLOCK
2883 given when we committed the execution of the unit's last insn.
2885 The blockage value is given by either the unit's max blockage
2886 constant, blockage range function, or blockage function. Use
2887 the most exact form for the given unit. */
2889 if (function_units[unit].blockage_range_function)
2891 if (function_units[unit].blockage_function)
2892 tick += (function_units[unit].blockage_function
2893 (unit_last_insn[instance], insn)
2894 - function_units[unit].max_blockage);
2896 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
2897 - function_units[unit].max_blockage);
2899 if (tick - clock > cost)
2900 cost = tick - clock;
2905 /* Record INSN as having begun execution on the units encoded by UNIT at
2908 HAIFA_INLINE static void
2909 schedule_unit (unit, insn, clock)
2917 int instance = unit;
2918 #if MAX_MULTIPLICITY > 1
2919 /* Find the first free instance of the function unit and use that
2920 one. We assume that one is free. */
2921 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2923 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
2925 instance += FUNCTION_UNITS_SIZE;
2928 unit_last_insn[instance] = insn;
2929 unit_tick[instance] = (clock + function_units[unit].max_blockage);
2932 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2933 if ((unit & 1) != 0)
2934 schedule_unit (i, insn, clock);
2937 /* Return the actual hazard cost of executing INSN on the units encoded by
2938 UNIT at time CLOCK if the previous actual hazard cost was COST. */
2940 HAIFA_INLINE static int
2941 actual_hazard (unit, insn, clock, cost)
2942 int unit, clock, cost;
2949 /* Find the instance of the function unit with the minimum hazard. */
2950 int instance = unit;
2951 int best_cost = actual_hazard_this_instance (unit, instance, insn,
2953 #if MAX_MULTIPLICITY > 1
2956 if (best_cost > cost)
2958 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2960 instance += FUNCTION_UNITS_SIZE;
2961 this_cost = actual_hazard_this_instance (unit, instance, insn,
2963 if (this_cost < best_cost)
2965 best_cost = this_cost;
2966 if (this_cost <= cost)
2972 cost = MAX (cost, best_cost);
2975 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2976 if ((unit & 1) != 0)
2977 cost = actual_hazard (i, insn, clock, cost);
2982 /* Return the potential hazard cost of executing an instruction on the
2983 units encoded by UNIT if the previous potential hazard cost was COST.
2984 An insn with a large blockage time is chosen in preference to one
2985 with a smaller time; an insn that uses a unit that is more likely
2986 to be used is chosen in preference to one with a unit that is less
2987 used. We are trying to minimize a subsequent actual hazard. */
2989 HAIFA_INLINE static int
2990 potential_hazard (unit, insn, cost)
2995 unsigned int minb, maxb;
2999 minb = maxb = function_units[unit].max_blockage;
3002 if (function_units[unit].blockage_range_function)
3004 maxb = minb = blockage_range (unit, insn);
3005 maxb = MAX_BLOCKAGE_COST (maxb);
3006 minb = MIN_BLOCKAGE_COST (minb);
3011 /* Make the number of instructions left dominate. Make the
3012 minimum delay dominate the maximum delay. If all these
3013 are the same, use the unit number to add an arbitrary
3014 ordering. Other terms can be added. */
3015 ncost = minb * 0x40 + maxb;
3016 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
3023 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3024 if ((unit & 1) != 0)
3025 cost = potential_hazard (i, insn, cost);
3030 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3031 This is the number of cycles between instruction issue and
3032 instruction results. */
3034 HAIFA_INLINE static int
3035 insn_cost (insn, link, used)
3036 rtx insn, link, used;
3038 register int cost = INSN_COST (insn);
3042 recog_memoized (insn);
3044 /* A USE insn, or something else we don't need to understand.
3045 We can't pass these directly to result_ready_cost because it will
3046 trigger a fatal error for unrecognizable insns. */
3047 if (INSN_CODE (insn) < 0)
3049 INSN_COST (insn) = 1;
3054 cost = result_ready_cost (insn);
3059 INSN_COST (insn) = cost;
3063 /* In this case estimate cost without caring how insn is used. */
3064 if (link == 0 && used == 0)
3067 /* A USE insn should never require the value used to be computed. This
3068 allows the computation of a function's result and parameter values to
3069 overlap the return and call. */
3070 recog_memoized (used);
3071 if (INSN_CODE (used) < 0)
3072 LINK_COST_FREE (link) = 1;
3074 /* If some dependencies vary the cost, compute the adjustment. Most
3075 commonly, the adjustment is complete: either the cost is ignored
3076 (in the case of an output- or anti-dependence), or the cost is
3077 unchanged. These values are cached in the link as LINK_COST_FREE
3078 and LINK_COST_ZERO. */
3080 if (LINK_COST_FREE (link))
3083 else if (!LINK_COST_ZERO (link))
3087 ADJUST_COST (used, link, insn, ncost);
3090 LINK_COST_FREE (link) = 1;
3094 LINK_COST_ZERO (link) = 1;
3101 /* Compute the priority number for INSN. */
3110 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
3113 if ((this_priority = INSN_PRIORITY (insn)) == 0)
3115 if (INSN_DEPEND (insn) == 0)
3116 this_priority = insn_cost (insn, 0, 0);
3118 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
3123 if (RTX_INTEGRATED_P (link))
3126 next = XEXP (link, 0);
3128 /* Critical path is meaningful in block boundaries only. */
3129 if (INSN_BLOCK (next) != INSN_BLOCK (insn))
3132 next_priority = insn_cost (insn, link, next) + priority (next);
3133 if (next_priority > this_priority)
3134 this_priority = next_priority;
3136 INSN_PRIORITY (insn) = this_priority;
3138 return this_priority;
3142 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3143 them to the unused_*_list variables, so that they can be reused. */
3146 free_pending_lists ()
3148 if (current_nr_blocks <= 1)
3150 free_INSN_LIST_list (&pending_read_insns);
3151 free_INSN_LIST_list (&pending_write_insns);
3152 free_EXPR_LIST_list (&pending_read_mems);
3153 free_EXPR_LIST_list (&pending_write_mems);
3157 /* Interblock scheduling. */
3160 for (bb = 0; bb < current_nr_blocks; bb++)
3162 free_INSN_LIST_list (&bb_pending_read_insns[bb]);
3163 free_INSN_LIST_list (&bb_pending_write_insns[bb]);
3164 free_EXPR_LIST_list (&bb_pending_read_mems[bb]);
3165 free_EXPR_LIST_list (&bb_pending_write_mems[bb]);
3170 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3171 The MEM is a memory reference contained within INSN, which we are saving
3172 so that we can do memory aliasing on it. */
3175 add_insn_mem_dependence (insn_list, mem_list, insn, mem)
3176 rtx *insn_list, *mem_list, insn, mem;
3180 link = alloc_INSN_LIST (insn, *insn_list);
3183 link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
3186 pending_lists_length++;
3190 /* Make a dependency between every memory reference on the pending lists
3191 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3195 flush_pending_lists (insn, only_write)
3202 while (pending_read_insns && ! only_write)
3204 add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
3206 link = pending_read_insns;
3207 pending_read_insns = XEXP (pending_read_insns, 1);
3208 free_INSN_LIST_node (link);
3210 link = pending_read_mems;
3211 pending_read_mems = XEXP (pending_read_mems, 1);
3212 free_EXPR_LIST_node (link);
3214 while (pending_write_insns)
3216 add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
3218 link = pending_write_insns;
3219 pending_write_insns = XEXP (pending_write_insns, 1);
3220 free_INSN_LIST_node (link);
3222 link = pending_write_mems;
3223 pending_write_mems = XEXP (pending_write_mems, 1);
3224 free_EXPR_LIST_node (link);
3226 pending_lists_length = 0;
3228 /* last_pending_memory_flush is now a list of insns. */
3229 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3230 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3232 free_INSN_LIST_list (&last_pending_memory_flush);
3233 last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
3236 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
3237 rtx, X, creating all dependencies generated by the write to the
3238 destination of X, and reads of everything mentioned. */
3241 sched_analyze_1 (x, insn)
3246 register rtx dest = XEXP (x, 0);
3247 enum rtx_code code = GET_CODE (x);
3252 if (GET_CODE (dest) == PARALLEL
3253 && GET_MODE (dest) == BLKmode)
3256 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
3257 sched_analyze_1 (XVECEXP (dest, 0, i), insn);
3258 if (GET_CODE (x) == SET)
3259 sched_analyze_2 (SET_SRC (x), insn);
3263 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3264 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3266 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3268 /* The second and third arguments are values read by this insn. */
3269 sched_analyze_2 (XEXP (dest, 1), insn);
3270 sched_analyze_2 (XEXP (dest, 2), insn);
3272 dest = XEXP (dest, 0);
3275 if (GET_CODE (dest) == REG)
3279 regno = REGNO (dest);
3281 /* A hard reg in a wide mode may really be multiple registers.
3282 If so, mark all of them just like the first. */
3283 if (regno < FIRST_PSEUDO_REGISTER)
3285 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
3290 for (u = reg_last_uses[regno + i]; u; u = XEXP (u, 1))
3291 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3293 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3294 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3296 /* Clobbers need not be ordered with respect to one
3297 another, but sets must be ordered with respect to a
3301 free_INSN_LIST_list (®_last_uses[regno + i]);
3302 for (u = reg_last_clobbers[regno + i]; u; u = XEXP (u, 1))
3303 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3304 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
3307 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
3309 /* Function calls clobber all call_used regs. */
3310 if (global_regs[regno + i]
3311 || (code == SET && call_used_regs[regno + i]))
3312 for (u = last_function_call; u; u = XEXP (u, 1))
3313 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3320 for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
3321 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3323 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3324 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3328 free_INSN_LIST_list (®_last_uses[regno]);
3329 for (u = reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3330 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3331 SET_REGNO_REG_SET (reg_pending_sets, regno);
3334 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
3336 /* Pseudos that are REG_EQUIV to something may be replaced
3337 by that during reloading. We need only add dependencies for
3338 the address in the REG_EQUIV note. */
3339 if (!reload_completed
3340 && reg_known_equiv_p[regno]
3341 && GET_CODE (reg_known_value[regno]) == MEM)
3342 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3344 /* Don't let it cross a call after scheduling if it doesn't
3345 already cross one. */
3347 if (REG_N_CALLS_CROSSED (regno) == 0)
3348 for (u = last_function_call; u; u = XEXP (u, 1))
3349 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3352 else if (GET_CODE (dest) == MEM)
3354 /* Writing memory. */
3356 if (pending_lists_length > 32)
3358 /* Flush all pending reads and writes to prevent the pending lists
3359 from getting any larger. Insn scheduling runs too slowly when
3360 these lists get long. The number 32 was chosen because it
3361 seems like a reasonable number. When compiling GCC with itself,
3362 this flush occurs 8 times for sparc, and 10 times for m88k using
3364 flush_pending_lists (insn, 0);
3369 rtx pending, pending_mem;
3371 pending = pending_read_insns;
3372 pending_mem = pending_read_mems;
3375 if (anti_dependence (XEXP (pending_mem, 0), dest))
3376 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3378 pending = XEXP (pending, 1);
3379 pending_mem = XEXP (pending_mem, 1);
3382 pending = pending_write_insns;
3383 pending_mem = pending_write_mems;
3386 if (output_dependence (XEXP (pending_mem, 0), dest))
3387 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
3389 pending = XEXP (pending, 1);
3390 pending_mem = XEXP (pending_mem, 1);
3393 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3394 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3396 add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
3399 sched_analyze_2 (XEXP (dest, 0), insn);
3402 /* Analyze reads. */
3403 if (GET_CODE (x) == SET)
3404 sched_analyze_2 (SET_SRC (x), insn);
3407 /* Analyze the uses of memory and registers in rtx X in INSN. */
3410 sched_analyze_2 (x, insn)
3416 register enum rtx_code code;
3417 register const char *fmt;
3422 code = GET_CODE (x);
3431 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3432 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3433 this does not mean that this insn is using cc0. */
3441 /* User of CC0 depends on immediately preceding insn. */
3442 SCHED_GROUP_P (insn) = 1;
3444 /* There may be a note before this insn now, but all notes will
3445 be removed before we actually try to schedule the insns, so
3446 it won't cause a problem later. We must avoid it here though. */
3447 prev = prev_nonnote_insn (insn);
3449 /* Make a copy of all dependencies on the immediately previous insn,
3450 and add to this insn. This is so that all the dependencies will
3451 apply to the group. Remove an explicit dependence on this insn
3452 as SCHED_GROUP_P now represents it. */
3454 if (find_insn_list (prev, LOG_LINKS (insn)))
3455 remove_dependence (insn, prev);
3457 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
3458 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3467 int regno = REGNO (x);
3468 if (regno < FIRST_PSEUDO_REGISTER)
3472 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
3475 reg_last_uses[regno + i]
3476 = alloc_INSN_LIST (insn, reg_last_uses[regno + i]);
3478 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3479 add_dependence (insn, XEXP (u, 0), 0);
3481 /* ??? This should never happen. */
3482 for (u = reg_last_clobbers[regno + i]; u; u = XEXP (u, 1))
3483 add_dependence (insn, XEXP (u, 0), 0);
3485 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3486 /* Function calls clobber all call_used regs. */
3487 for (u = last_function_call; u; u = XEXP (u, 1))
3488 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3493 reg_last_uses[regno] = alloc_INSN_LIST (insn,
3494 reg_last_uses[regno]);
3496 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3497 add_dependence (insn, XEXP (u, 0), 0);
3499 /* ??? This should never happen. */
3500 for (u = reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3501 add_dependence (insn, XEXP (u, 0), 0);
3503 /* Pseudos that are REG_EQUIV to something may be replaced
3504 by that during reloading. We need only add dependencies for
3505 the address in the REG_EQUIV note. */
3506 if (!reload_completed
3507 && reg_known_equiv_p[regno]
3508 && GET_CODE (reg_known_value[regno]) == MEM)
3509 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3511 /* If the register does not already cross any calls, then add this
3512 insn to the sched_before_next_call list so that it will still
3513 not cross calls after scheduling. */
3514 if (REG_N_CALLS_CROSSED (regno) == 0)
3515 add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
3522 /* Reading memory. */
3524 rtx pending, pending_mem;
3526 pending = pending_read_insns;
3527 pending_mem = pending_read_mems;
3530 if (read_dependence (XEXP (pending_mem, 0), x))
3531 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3533 pending = XEXP (pending, 1);
3534 pending_mem = XEXP (pending_mem, 1);
3537 pending = pending_write_insns;
3538 pending_mem = pending_write_mems;
3541 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
3543 add_dependence (insn, XEXP (pending, 0), 0);
3545 pending = XEXP (pending, 1);
3546 pending_mem = XEXP (pending_mem, 1);
3549 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3550 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3552 /* Always add these dependencies to pending_reads, since
3553 this insn may be followed by a write. */
3554 add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
3557 /* Take advantage of tail recursion here. */
3558 sched_analyze_2 (XEXP (x, 0), insn);
3562 /* Force pending stores to memory in case a trap handler needs them. */
3564 flush_pending_lists (insn, 1);
3569 case UNSPEC_VOLATILE:
3573 /* Traditional and volatile asm instructions must be considered to use
3574 and clobber all hard registers, all pseudo-registers and all of
3575 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3577 Consider for instance a volatile asm that changes the fpu rounding
3578 mode. An insn should not be moved across this even if it only uses
3579 pseudo-regs because it might give an incorrectly rounded result. */
3580 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
3582 int max_reg = max_reg_num ();
3583 for (i = 0; i < max_reg; i++)
3585 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3586 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3587 free_INSN_LIST_list (®_last_uses[i]);
3589 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3590 add_dependence (insn, XEXP (u, 0), 0);
3592 for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
3593 add_dependence (insn, XEXP (u, 0), 0);
3595 reg_pending_sets_all = 1;
3597 flush_pending_lists (insn, 0);
3600 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3601 We can not just fall through here since then we would be confused
3602 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3603 traditional asms unlike their normal usage. */
3605 if (code == ASM_OPERANDS)
3607 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3608 sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
3618 /* These both read and modify the result. We must handle them as writes
3619 to get proper dependencies for following instructions. We must handle
3620 them as reads to get proper dependencies from this to previous
3621 instructions. Thus we need to pass them to both sched_analyze_1
3622 and sched_analyze_2. We must call sched_analyze_2 first in order
3623 to get the proper antecedent for the read. */
3624 sched_analyze_2 (XEXP (x, 0), insn);
3625 sched_analyze_1 (x, insn);
3632 /* Other cases: walk the insn. */
3633 fmt = GET_RTX_FORMAT (code);
3634 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3637 sched_analyze_2 (XEXP (x, i), insn);
3638 else if (fmt[i] == 'E')
3639 for (j = 0; j < XVECLEN (x, i); j++)
3640 sched_analyze_2 (XVECEXP (x, i, j), insn);
3644 /* Analyze an INSN with pattern X to find all dependencies. */
3647 sched_analyze_insn (x, insn, loop_notes)
3651 register RTX_CODE code = GET_CODE (x);
3653 int maxreg = max_reg_num ();
3656 if (code == SET || code == CLOBBER)
3657 sched_analyze_1 (x, insn);
3658 else if (code == PARALLEL)
3661 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3663 code = GET_CODE (XVECEXP (x, 0, i));
3664 if (code == SET || code == CLOBBER)
3665 sched_analyze_1 (XVECEXP (x, 0, i), insn);
3667 sched_analyze_2 (XVECEXP (x, 0, i), insn);
3671 sched_analyze_2 (x, insn);
3673 /* Mark registers CLOBBERED or used by called function. */
3674 if (GET_CODE (insn) == CALL_INSN)
3675 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3677 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3678 sched_analyze_1 (XEXP (link, 0), insn);
3680 sched_analyze_2 (XEXP (link, 0), insn);
3683 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3684 block, then we must be sure that no instructions are scheduled across it.
3685 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3686 become incorrect. */
3690 int max_reg = max_reg_num ();
3691 int schedule_barrier_found = 0;
3694 /* Update loop_notes with any notes from this insn. Also determine
3695 if any of the notes on the list correspond to instruction scheduling
3696 barriers (loop, eh & setjmp notes, but not range notes. */
3698 while (XEXP (link, 1))
3700 if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
3701 || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
3702 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
3703 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END
3704 || INTVAL (XEXP (link, 0)) == NOTE_INSN_SETJMP)
3705 schedule_barrier_found = 1;
3707 link = XEXP (link, 1);
3709 XEXP (link, 1) = REG_NOTES (insn);
3710 REG_NOTES (insn) = loop_notes;
3712 /* Add dependencies if a scheduling barrier was found. */
3713 if (schedule_barrier_found)
3715 for (i = 0; i < max_reg; i++)
3718 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3719 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3720 free_INSN_LIST_list (®_last_uses[i]);
3722 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3723 add_dependence (insn, XEXP (u, 0), 0);
3725 for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
3726 add_dependence (insn, XEXP (u, 0), 0);
3728 reg_pending_sets_all = 1;
3730 flush_pending_lists (insn, 0);
3735 /* Accumulate clobbers until the next set so that it will be output dependent
3736 on all of them. At the next set we can clear the clobber list, since
3737 subsequent sets will be output dependent on it. */
3738 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
3740 free_INSN_LIST_list (®_last_sets[i]);
3741 free_INSN_LIST_list (®_last_clobbers[i]);
3743 = alloc_INSN_LIST (insn, NULL_RTX);
3745 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
3747 reg_last_clobbers[i]
3748 = alloc_INSN_LIST (insn,
3749 reg_last_clobbers[i]);
3751 CLEAR_REG_SET (reg_pending_sets);
3752 CLEAR_REG_SET (reg_pending_clobbers);
3754 if (reg_pending_sets_all)
3756 for (i = 0; i < maxreg; i++)
3758 free_INSN_LIST_list (®_last_sets[i]);
3759 reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3762 reg_pending_sets_all = 0;
3765 /* Handle function calls and function returns created by the epilogue
3767 if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
3772 /* When scheduling instructions, we make sure calls don't lose their
3773 accompanying USE insns by depending them one on another in order.
3775 Also, we must do the same thing for returns created by the epilogue
3776 threading code. Note this code works only in this special case,
3777 because other passes make no guarantee that they will never emit
3778 an instruction between a USE and a RETURN. There is such a guarantee
3779 for USE instructions immediately before a call. */
3781 prev_dep_insn = insn;
3782 dep_insn = PREV_INSN (insn);
3783 while (GET_CODE (dep_insn) == INSN
3784 && GET_CODE (PATTERN (dep_insn)) == USE
3785 && GET_CODE (XEXP (PATTERN (dep_insn), 0)) == REG)
3787 SCHED_GROUP_P (prev_dep_insn) = 1;
3789 /* Make a copy of all dependencies on dep_insn, and add to insn.
3790 This is so that all of the dependencies will apply to the
3793 for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
3794 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3796 prev_dep_insn = dep_insn;
3797 dep_insn = PREV_INSN (dep_insn);
3802 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3803 for every dependency. */
3806 sched_analyze (head, tail)
3813 for (insn = head;; insn = NEXT_INSN (insn))
3815 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
3817 /* Clear out the stale LOG_LINKS from flow. */
3818 free_INSN_LIST_list (&LOG_LINKS (insn));
3820 /* Make each JUMP_INSN a scheduling barrier for memory
3822 if (GET_CODE (insn) == JUMP_INSN)
3823 last_pending_memory_flush
3824 = alloc_INSN_LIST (insn, last_pending_memory_flush);
3825 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3828 else if (GET_CODE (insn) == CALL_INSN)
3833 CANT_MOVE (insn) = 1;
3835 /* Clear out the stale LOG_LINKS from flow. */
3836 free_INSN_LIST_list (&LOG_LINKS (insn));
3838 /* Any instruction using a hard register which may get clobbered
3839 by a call needs to be marked as dependent on this call.
3840 This prevents a use of a hard return reg from being moved
3841 past a void call (i.e. it does not explicitly set the hard
3844 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3845 all registers, not just hard registers, may be clobbered by this
3848 /* Insn, being a CALL_INSN, magically depends on
3849 `last_function_call' already. */
3851 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
3852 && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
3854 int max_reg = max_reg_num ();
3855 for (i = 0; i < max_reg; i++)
3857 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3858 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3859 free_INSN_LIST_list (®_last_uses[i]);
3861 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3862 add_dependence (insn, XEXP (u, 0), 0);
3864 for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
3865 add_dependence (insn, XEXP (u, 0), 0);
3867 reg_pending_sets_all = 1;
3869 /* Add a pair of fake REG_NOTEs which we will later
3870 convert back into a NOTE_INSN_SETJMP note. See
3871 reemit_notes for why we use a pair of NOTEs. */
3872 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3875 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3876 GEN_INT (NOTE_INSN_SETJMP),
3881 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3882 if (call_used_regs[i] || global_regs[i])
3884 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3885 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3887 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3888 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3890 SET_REGNO_REG_SET (reg_pending_clobbers, i);
3894 /* For each insn which shouldn't cross a call, add a dependence
3895 between that insn and this call insn. */
3896 x = LOG_LINKS (sched_before_next_call);
3899 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
3902 free_INSN_LIST_list (&LOG_LINKS (sched_before_next_call));
3904 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3907 /* In the absence of interprocedural alias analysis, we must flush
3908 all pending reads and writes, and start new dependencies starting
3909 from here. But only flush writes for constant calls (which may
3910 be passed a pointer to something we haven't written yet). */
3911 flush_pending_lists (insn, CONST_CALL_P (insn));
3913 /* Depend this function call (actually, the user of this
3914 function call) on all hard register clobberage. */
3916 /* last_function_call is now a list of insns. */
3917 free_INSN_LIST_list(&last_function_call);
3918 last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3921 /* See comments on reemit_notes as to why we do this.
3922 ??? Actually, the reemit_notes just say what is done, not why. */
3924 else if (GET_CODE (insn) == NOTE
3925 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_START
3926 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END))
3928 loop_notes = alloc_EXPR_LIST (REG_DEAD, NOTE_RANGE_INFO (insn),
3930 loop_notes = alloc_EXPR_LIST (REG_DEAD,
3931 GEN_INT (NOTE_LINE_NUMBER (insn)),
3934 else if (GET_CODE (insn) == NOTE
3935 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
3936 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
3937 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
3938 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
3939 || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
3940 && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
3944 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
3945 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
3946 region = GEN_INT (NOTE_EH_HANDLER (insn));
3948 region = GEN_INT (0);
3950 loop_notes = alloc_EXPR_LIST (REG_DEAD,
3953 loop_notes = alloc_EXPR_LIST (REG_DEAD,
3954 GEN_INT (NOTE_LINE_NUMBER (insn)),
3956 CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
3965 /* Called when we see a set of a register. If death is true, then we are
3966 scanning backwards. Mark that register as unborn. If nobody says
3967 otherwise, that is how things will remain. If death is false, then we
3968 are scanning forwards. Mark that register as being born. */
3971 sched_note_set (x, death)
3976 register rtx reg = SET_DEST (x);
3982 if (GET_CODE (reg) == PARALLEL
3983 && GET_MODE (reg) == BLKmode)
3986 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
3987 sched_note_set (XVECEXP (reg, 0, i), death);
3991 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
3992 || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
3994 /* Must treat modification of just one hardware register of a multi-reg
3995 value or just a byte field of a register exactly the same way that
3996 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
3997 does not kill the entire register. */
3998 if (GET_CODE (reg) != SUBREG
3999 || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
4002 reg = SUBREG_REG (reg);
4005 if (GET_CODE (reg) != REG)
4008 /* Global registers are always live, so the code below does not apply
4011 regno = REGNO (reg);
4012 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
4016 /* If we only set part of the register, then this set does not
4021 /* Try killing this register. */
4022 if (regno < FIRST_PSEUDO_REGISTER)
4024 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
4027 CLEAR_REGNO_REG_SET (bb_live_regs, regno + j);
4032 /* Recompute REG_BASIC_BLOCK as we update all the other
4033 dataflow information. */
4034 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
4035 sched_reg_basic_block[regno] = current_block_num;
4036 else if (sched_reg_basic_block[regno] != current_block_num)
4037 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
4039 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
4044 /* Make the register live again. */
4045 if (regno < FIRST_PSEUDO_REGISTER)
4047 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
4050 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4055 SET_REGNO_REG_SET (bb_live_regs, regno);
4061 /* Macros and functions for keeping the priority queue sorted, and
4062 dealing with queueing and dequeueing of instructions. */
4064 #define SCHED_SORT(READY, N_READY) \
4065 do { if ((N_READY) == 2) \
4066 swap_sort (READY, N_READY); \
4067 else if ((N_READY) > 2) \
4068 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4071 /* Returns a positive value if x is preferred; returns a negative value if
4072 y is preferred. Should never return 0, since that will make the sort
4076 rank_for_schedule (x, y)
4080 rtx tmp = *(rtx *)y;
4081 rtx tmp2 = *(rtx *)x;
4083 int tmp_class, tmp2_class, depend_count1, depend_count2;
4084 int val, priority_val, spec_val, prob_val, weight_val;
4087 /* Prefer insn with higher priority. */
4088 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
4090 return priority_val;
4092 /* Prefer an insn with smaller contribution to registers-pressure. */
4093 if (!reload_completed &&
4094 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
4095 return (weight_val);
4097 /* Some comparison make sense in interblock scheduling only. */
4098 if (INSN_BB (tmp) != INSN_BB (tmp2))
4100 /* Prefer an inblock motion on an interblock motion. */
4101 if ((INSN_BB (tmp2) == target_bb) && (INSN_BB (tmp) != target_bb))
4103 if ((INSN_BB (tmp) == target_bb) && (INSN_BB (tmp2) != target_bb))
4106 /* Prefer a useful motion on a speculative one. */
4107 if ((spec_val = IS_SPECULATIVE_INSN (tmp) - IS_SPECULATIVE_INSN (tmp2)))
4110 /* Prefer a more probable (speculative) insn. */
4111 prob_val = INSN_PROBABILITY (tmp2) - INSN_PROBABILITY (tmp);
4116 /* Compare insns based on their relation to the last-scheduled-insn. */
4117 if (last_scheduled_insn)
4119 /* Classify the instructions into three classes:
4120 1) Data dependent on last schedule insn.
4121 2) Anti/Output dependent on last scheduled insn.
4122 3) Independent of last scheduled insn, or has latency of one.
4123 Choose the insn from the highest numbered class if different. */
4124 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
4125 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
4127 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4132 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
4133 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
4135 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4140 if ((val = tmp2_class - tmp_class))
4144 /* Prefer the insn which has more later insns that depend on it.
4145 This gives the scheduler more freedom when scheduling later
4146 instructions at the expense of added register pressure. */
4148 for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
4152 for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
4155 val = depend_count2 - depend_count1;
4159 /* If insns are equally good, sort by INSN_LUID (original insn order),
4160 so that we make the sort stable. This minimizes instruction movement,
4161 thus minimizing sched's effect on debugging and cross-jumping. */
4162 return INSN_LUID (tmp) - INSN_LUID (tmp2);
4165 /* Resort the array A in which only element at index N may be out of order. */
4167 HAIFA_INLINE static void
4172 rtx insn = a[n - 1];
4175 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
4183 static int max_priority;
4185 /* Add INSN to the insn queue so that it can be executed at least
4186 N_CYCLES after the currently executing insn. Preserve insns
4187 chain for debugging purposes. */
4189 HAIFA_INLINE static void
4190 queue_insn (insn, n_cycles)
4194 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
4195 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
4196 insn_queue[next_q] = link;
4199 if (sched_verbose >= 2)
4201 fprintf (dump, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn));
4203 if (INSN_BB (insn) != target_bb)
4204 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
4206 fprintf (dump, "queued for %d cycles.\n", n_cycles);
4211 /* Return nonzero if PAT is the pattern of an insn which makes a
4214 HAIFA_INLINE static int
4215 birthing_insn_p (pat)
4220 if (reload_completed == 1)
4223 if (GET_CODE (pat) == SET
4224 && (GET_CODE (SET_DEST (pat)) == REG
4225 || (GET_CODE (SET_DEST (pat)) == PARALLEL
4226 && GET_MODE (SET_DEST (pat)) == BLKmode)))
4228 rtx dest = SET_DEST (pat);
4231 /* It would be more accurate to use refers_to_regno_p or
4232 reg_mentioned_p to determine when the dest is not live before this
4234 if (GET_CODE (dest) == REG)
4237 if (REGNO_REG_SET_P (bb_live_regs, i))
4238 return (REG_N_SETS (i) == 1);
4242 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
4244 int regno = REGNO (SET_DEST (XVECEXP (dest, 0, i)));
4245 if (REGNO_REG_SET_P (bb_live_regs, regno))
4246 return (REG_N_SETS (regno) == 1);
4251 if (GET_CODE (pat) == PARALLEL)
4253 for (j = 0; j < XVECLEN (pat, 0); j++)
4254 if (birthing_insn_p (XVECEXP (pat, 0, j)))
4260 /* PREV is an insn that is ready to execute. Adjust its priority if that
4261 will help shorten register lifetimes. */
4263 HAIFA_INLINE static void
4264 adjust_priority (prev)
4267 /* Trying to shorten register lives after reload has completed
4268 is useless and wrong. It gives inaccurate schedules. */
4269 if (reload_completed == 0)
4274 /* ??? This code has no effect, because REG_DEAD notes are removed
4275 before we ever get here. */
4276 for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
4277 if (REG_NOTE_KIND (note) == REG_DEAD)
4280 /* Defer scheduling insns which kill registers, since that
4281 shortens register lives. Prefer scheduling insns which
4282 make registers live for the same reason. */
4286 INSN_PRIORITY (prev) >>= 3;
4289 INSN_PRIORITY (prev) >>= 2;
4293 INSN_PRIORITY (prev) >>= 1;
4296 if (birthing_insn_p (PATTERN (prev)))
4298 int max = max_priority;
4300 if (max > INSN_PRIORITY (prev))
4301 INSN_PRIORITY (prev) = max;
4307 /* That said, a target might have it's own reasons for adjusting
4308 priority after reload. */
4309 #ifdef ADJUST_PRIORITY
4310 ADJUST_PRIORITY (prev);
4314 /* Clock at which the previous instruction was issued. */
4315 static int last_clock_var;
4317 /* INSN is the "currently executing insn". Launch each insn which was
4318 waiting on INSN. READY is a vector of insns which are ready to fire.
4319 N_READY is the number of elements in READY. CLOCK is the current
4323 schedule_insn (insn, ready, n_ready, clock)
4332 unit = insn_unit (insn);
4334 if (sched_verbose >= 2)
4336 fprintf (dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
4338 insn_print_units (insn);
4339 fprintf (dump, "\n");
4342 if (sched_verbose && unit == -1)
4343 visualize_no_unit (insn);
4345 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
4346 schedule_unit (unit, insn, clock);
4348 if (INSN_DEPEND (insn) == 0)
4351 /* This is used by the function adjust_priority above. */
4353 max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
4355 max_priority = INSN_PRIORITY (insn);
4357 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
4359 rtx next = XEXP (link, 0);
4360 int cost = insn_cost (insn, link, next);
4362 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
4364 if ((INSN_DEP_COUNT (next) -= 1) == 0)
4366 int effective_cost = INSN_TICK (next) - clock;
4368 /* For speculative insns, before inserting to ready/queue,
4369 check live, exception-free, and issue-delay. */
4370 if (INSN_BB (next) != target_bb
4371 && (!IS_VALID (INSN_BB (next))
4373 || (IS_SPECULATIVE_INSN (next)
4374 && (insn_issue_delay (next) > 3
4375 || !check_live (next, INSN_BB (next))
4376 || !is_exception_free (next, INSN_BB (next), target_bb)))))
4379 if (sched_verbose >= 2)
4381 fprintf (dump, ";;\t\tdependences resolved: insn %d ",
4384 if (current_nr_blocks > 1 && INSN_BB (next) != target_bb)
4385 fprintf (dump, "/b%d ", INSN_BLOCK (next));
4387 if (effective_cost < 1)
4388 fprintf (dump, "into ready\n");
4390 fprintf (dump, "into queue with cost=%d\n", effective_cost);
4393 /* Adjust the priority of NEXT and either put it on the ready
4394 list or queue it. */
4395 adjust_priority (next);
4396 if (effective_cost < 1)
4397 ready[n_ready++] = next;
4399 queue_insn (next, effective_cost);
4403 /* Annotate the instruction with issue information -- TImode
4404 indicates that the instruction is expected not to be able
4405 to issue on the same cycle as the previous insn. A machine
4406 may use this information to decide how the instruction should
4408 if (reload_completed && issue_rate > 1)
4410 PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
4411 last_clock_var = clock;
4418 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4422 create_reg_dead_note (reg, insn)
4427 /* The number of registers killed after scheduling must be the same as the
4428 number of registers killed before scheduling. The number of REG_DEAD
4429 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4430 might become one DImode hard register REG_DEAD note, but the number of
4431 registers killed will be conserved.
4433 We carefully remove REG_DEAD notes from the dead_notes list, so that
4434 there will be none left at the end. If we run out early, then there
4435 is a bug somewhere in flow, combine and/or sched. */
4437 if (dead_notes == 0)
4439 if (current_nr_blocks <= 1)
4442 link = alloc_EXPR_LIST (REG_DEAD, NULL_RTX, NULL_RTX);
4446 /* Number of regs killed by REG. */
4447 int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
4448 : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
4449 /* Number of regs killed by REG_DEAD notes taken off the list. */
4453 reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4454 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4455 GET_MODE (XEXP (link, 0))));
4456 while (reg_note_regs < regs_killed)
4458 link = XEXP (link, 1);
4460 /* LINK might be zero if we killed more registers after scheduling
4461 than before, and the last hard register we kill is actually
4464 This is normal for interblock scheduling, so deal with it in
4465 that case, else abort. */
4466 if (link == NULL_RTX && current_nr_blocks <= 1)
4468 else if (link == NULL_RTX)
4469 link = alloc_EXPR_LIST (REG_DEAD, gen_rtx_REG (word_mode, 0),
4472 reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4473 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4474 GET_MODE (XEXP (link, 0))));
4476 dead_notes = XEXP (link, 1);
4478 /* If we took too many regs kills off, put the extra ones back. */
4479 while (reg_note_regs > regs_killed)
4481 rtx temp_reg, temp_link;
4483 temp_reg = gen_rtx_REG (word_mode, 0);
4484 temp_link = alloc_EXPR_LIST (REG_DEAD, temp_reg, dead_notes);
4485 dead_notes = temp_link;
4490 XEXP (link, 0) = reg;
4491 XEXP (link, 1) = REG_NOTES (insn);
4492 REG_NOTES (insn) = link;
4495 /* Subroutine on attach_deaths_insn--handles the recursive search
4496 through INSN. If SET_P is true, then x is being modified by the insn. */
4499 attach_deaths (x, insn, set_p)
4506 register enum rtx_code code;
4507 register const char *fmt;
4512 code = GET_CODE (x);
4524 /* Get rid of the easy cases first. */
4529 /* If the register dies in this insn, queue that note, and mark
4530 this register as needing to die. */
4531 /* This code is very similar to mark_used_1 (if set_p is false)
4532 and mark_set_1 (if set_p is true) in flow.c. */
4542 all_needed = some_needed = REGNO_REG_SET_P (old_live_regs, regno);
4543 if (regno < FIRST_PSEUDO_REGISTER)
4547 n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4550 int needed = (REGNO_REG_SET_P (old_live_regs, regno + n));
4551 some_needed |= needed;
4552 all_needed &= needed;
4556 /* If it wasn't live before we started, then add a REG_DEAD note.
4557 We must check the previous lifetime info not the current info,
4558 because we may have to execute this code several times, e.g.
4559 once for a clobber (which doesn't add a note) and later
4560 for a use (which does add a note).
4562 Always make the register live. We must do this even if it was
4563 live before, because this may be an insn which sets and uses
4564 the same register, in which case the register has already been
4565 killed, so we must make it live again.
4567 Global registers are always live, and should never have a REG_DEAD
4568 note added for them, so none of the code below applies to them. */
4570 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
4572 /* Never add REG_DEAD notes for STACK_POINTER_REGNUM
4573 since it's always considered to be live. Similarly
4574 for FRAME_POINTER_REGNUM if a frame pointer is needed
4575 and for ARG_POINTER_REGNUM if it is fixed. */
4576 if (! (regno == FRAME_POINTER_REGNUM
4577 && (! reload_completed || frame_pointer_needed))
4578 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4579 && ! (regno == HARD_FRAME_POINTER_REGNUM
4580 && (! reload_completed || frame_pointer_needed))
4582 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4583 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
4585 && regno != STACK_POINTER_REGNUM)
4587 if (! all_needed && ! dead_or_set_p (insn, x))
4589 /* Check for the case where the register dying partially
4590 overlaps the register set by this insn. */
4591 if (regno < FIRST_PSEUDO_REGISTER
4592 && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
4594 int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4596 some_needed |= dead_or_set_regno_p (insn, regno + n);
4599 /* If none of the words in X is needed, make a REG_DEAD
4600 note. Otherwise, we must make partial REG_DEAD
4603 create_reg_dead_note (x, insn);
4608 /* Don't make a REG_DEAD note for a part of a
4609 register that is set in the insn. */
4610 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
4612 if (! REGNO_REG_SET_P (old_live_regs, regno+i)
4613 && ! dead_or_set_regno_p (insn, regno + i))
4614 create_reg_dead_note (gen_rtx_REG (reg_raw_mode[regno + i],
4621 if (regno < FIRST_PSEUDO_REGISTER)
4623 int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
4626 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4631 /* Recompute REG_BASIC_BLOCK as we update all the other
4632 dataflow information. */
4633 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
4634 sched_reg_basic_block[regno] = current_block_num;
4635 else if (sched_reg_basic_block[regno] != current_block_num)
4636 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
4638 SET_REGNO_REG_SET (bb_live_regs, regno);
4645 /* Handle tail-recursive case. */
4646 attach_deaths (XEXP (x, 0), insn, 0);
4650 attach_deaths (SUBREG_REG (x), insn,
4651 set_p && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4653 || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4654 == GET_MODE_SIZE (GET_MODE ((x))))));
4657 case STRICT_LOW_PART:
4658 attach_deaths (XEXP (x, 0), insn, 0);
4663 attach_deaths (XEXP (x, 0), insn, 0);
4664 attach_deaths (XEXP (x, 1), insn, 0);
4665 attach_deaths (XEXP (x, 2), insn, 0);
4670 && GET_MODE (x) == BLKmode)
4672 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4673 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
4679 /* Other cases: walk the insn. */
4680 fmt = GET_RTX_FORMAT (code);
4681 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4684 attach_deaths (XEXP (x, i), insn, 0);
4685 else if (fmt[i] == 'E')
4686 for (j = 0; j < XVECLEN (x, i); j++)
4687 attach_deaths (XVECEXP (x, i, j), insn, 0);
4692 /* After INSN has executed, add register death notes for each register
4693 that is dead after INSN. */
4696 attach_deaths_insn (insn)
4699 rtx x = PATTERN (insn);
4700 register RTX_CODE code = GET_CODE (x);
4705 attach_deaths (SET_SRC (x), insn, 0);
4707 /* A register might die here even if it is the destination, e.g.
4708 it is the target of a volatile read and is otherwise unused.
4709 Hence we must always call attach_deaths for the SET_DEST. */
4710 attach_deaths (SET_DEST (x), insn, 1);
4712 else if (code == PARALLEL)
4715 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4717 code = GET_CODE (XVECEXP (x, 0, i));
4720 attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
4722 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
4724 /* Flow does not add REG_DEAD notes to registers that die in
4725 clobbers, so we can't either. */
4726 else if (code != CLOBBER)
4727 attach_deaths (XVECEXP (x, 0, i), insn, 0);
4730 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4731 MEM being clobbered, just like flow. */
4732 else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == MEM)
4733 attach_deaths (XEXP (XEXP (x, 0), 0), insn, 0);
4734 /* Otherwise don't add a death note to things being clobbered. */
4735 else if (code != CLOBBER)
4736 attach_deaths (x, insn, 0);
4738 /* Make death notes for things used in the called function. */
4739 if (GET_CODE (insn) == CALL_INSN)
4740 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
4741 attach_deaths (XEXP (XEXP (link, 0), 0), insn,
4742 GET_CODE (XEXP (link, 0)) == CLOBBER);
4745 /* Functions for handling of notes. */
4747 /* Delete notes beginning with INSN and put them in the chain
4748 of notes ended by NOTE_LIST.
4749 Returns the insn following the notes. */
4752 unlink_other_notes (insn, tail)
4755 rtx prev = PREV_INSN (insn);
4757 while (insn != tail && GET_CODE (insn) == NOTE)
4759 rtx next = NEXT_INSN (insn);
4760 /* Delete the note from its current position. */
4762 NEXT_INSN (prev) = next;
4764 PREV_INSN (next) = prev;
4766 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4767 immediately after the call they follow. We use a fake
4768 (REG_DEAD (const_int -1)) note to remember them.
4769 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4770 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
4771 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
4772 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
4773 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_START
4774 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
4775 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
4776 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
4778 /* Insert the note at the end of the notes list. */
4779 PREV_INSN (insn) = note_list;
4781 NEXT_INSN (note_list) = insn;
4790 /* Delete line notes beginning with INSN. Record line-number notes so
4791 they can be reused. Returns the insn following the notes. */
4794 unlink_line_notes (insn, tail)
4797 rtx prev = PREV_INSN (insn);
4799 while (insn != tail && GET_CODE (insn) == NOTE)
4801 rtx next = NEXT_INSN (insn);
4803 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
4805 /* Delete the note from its current position. */
4807 NEXT_INSN (prev) = next;
4809 PREV_INSN (next) = prev;
4811 /* Record line-number notes so they can be reused. */
4812 LINE_NOTE (insn) = insn;
4822 /* Return the head and tail pointers of BB. */
4824 HAIFA_INLINE static void
4825 get_block_head_tail (bb, headp, tailp)
4835 b = BB_TO_BLOCK (bb);
4837 /* HEAD and TAIL delimit the basic block being scheduled. */
4838 head = BLOCK_HEAD (b);
4839 tail = BLOCK_END (b);
4841 /* Don't include any notes or labels at the beginning of the
4842 basic block, or notes at the ends of basic blocks. */
4843 while (head != tail)
4845 if (GET_CODE (head) == NOTE)
4846 head = NEXT_INSN (head);
4847 else if (GET_CODE (tail) == NOTE)
4848 tail = PREV_INSN (tail);
4849 else if (GET_CODE (head) == CODE_LABEL)
4850 head = NEXT_INSN (head);
4859 /* Delete line notes from bb. Save them so they can be later restored
4860 (in restore_line_notes ()). */
4871 get_block_head_tail (bb, &head, &tail);
4874 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4877 next_tail = NEXT_INSN (tail);
4878 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4882 /* Farm out notes, and maybe save them in NOTE_LIST.
4883 This is needed to keep the debugger from
4884 getting completely deranged. */
4885 if (GET_CODE (insn) == NOTE)
4888 insn = unlink_line_notes (insn, next_tail);
4894 if (insn == next_tail)
4900 /* Save line number notes for each insn in bb. */
4903 save_line_notes (bb)
4909 /* We must use the true line number for the first insn in the block
4910 that was computed and saved at the start of this pass. We can't
4911 use the current line number, because scheduling of the previous
4912 block may have changed the current line number. */
4914 rtx line = line_note_head[BB_TO_BLOCK (bb)];
4917 get_block_head_tail (bb, &head, &tail);
4918 next_tail = NEXT_INSN (tail);
4920 for (insn = BLOCK_HEAD (BB_TO_BLOCK (bb));
4922 insn = NEXT_INSN (insn))
4923 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4926 LINE_NOTE (insn) = line;
4930 /* After bb was scheduled, insert line notes into the insns list. */
4933 restore_line_notes (bb)
4936 rtx line, note, prev, new;
4937 int added_notes = 0;
4939 rtx head, next_tail, insn;
4941 b = BB_TO_BLOCK (bb);
4943 head = BLOCK_HEAD (b);
4944 next_tail = NEXT_INSN (BLOCK_END (b));
4946 /* Determine the current line-number. We want to know the current
4947 line number of the first insn of the block here, in case it is
4948 different from the true line number that was saved earlier. If
4949 different, then we need a line number note before the first insn
4950 of this block. If it happens to be the same, then we don't want to
4951 emit another line number note here. */
4952 for (line = head; line; line = PREV_INSN (line))
4953 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4956 /* Walk the insns keeping track of the current line-number and inserting
4957 the line-number notes as needed. */
4958 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4959 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4961 /* This used to emit line number notes before every non-deleted note.
4962 However, this confuses a debugger, because line notes not separated
4963 by real instructions all end up at the same address. I can find no
4964 use for line number notes before other notes, so none are emitted. */
4965 else if (GET_CODE (insn) != NOTE
4966 && (note = LINE_NOTE (insn)) != 0
4969 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
4970 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
4973 prev = PREV_INSN (insn);
4974 if (LINE_NOTE (note))
4976 /* Re-use the original line-number note. */
4977 LINE_NOTE (note) = 0;
4978 PREV_INSN (note) = prev;
4979 NEXT_INSN (prev) = note;
4980 PREV_INSN (insn) = note;
4981 NEXT_INSN (note) = insn;
4986 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
4987 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
4988 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
4991 if (sched_verbose && added_notes)
4992 fprintf (dump, ";; added %d line-number notes\n", added_notes);
4995 /* After scheduling the function, delete redundant line notes from the
4999 rm_redundant_line_notes ()
5002 rtx insn = get_insns ();
5003 int active_insn = 0;
5006 /* Walk the insns deleting redundant line-number notes. Many of these
5007 are already present. The remainder tend to occur at basic
5008 block boundaries. */
5009 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
5010 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
5012 /* If there are no active insns following, INSN is redundant. */
5013 if (active_insn == 0)
5016 NOTE_SOURCE_FILE (insn) = 0;
5017 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
5019 /* If the line number is unchanged, LINE is redundant. */
5021 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
5022 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
5025 NOTE_SOURCE_FILE (line) = 0;
5026 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
5033 else if (!((GET_CODE (insn) == NOTE
5034 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
5035 || (GET_CODE (insn) == INSN
5036 && (GET_CODE (PATTERN (insn)) == USE
5037 || GET_CODE (PATTERN (insn)) == CLOBBER))))
5040 if (sched_verbose && notes)
5041 fprintf (dump, ";; deleted %d line-number notes\n", notes);
5044 /* Delete notes between head and tail and put them in the chain
5045 of notes ended by NOTE_LIST. */
5048 rm_other_notes (head, tail)
5056 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
5059 next_tail = NEXT_INSN (tail);
5060 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5064 /* Farm out notes, and maybe save them in NOTE_LIST.
5065 This is needed to keep the debugger from
5066 getting completely deranged. */
5067 if (GET_CODE (insn) == NOTE)
5071 insn = unlink_other_notes (insn, next_tail);
5077 if (insn == next_tail)
5083 /* Constructor for `sometimes' data structure. */
5086 new_sometimes_live (regs_sometimes_live, regno, sometimes_max)
5087 struct sometimes *regs_sometimes_live;
5091 register struct sometimes *p;
5093 /* There should never be a register greater than max_regno here. If there
5094 is, it means that a define_split has created a new pseudo reg. This
5095 is not allowed, since there will not be flow info available for any
5096 new register, so catch the error here. */
5097 if (regno >= max_regno)
5100 p = ®s_sometimes_live[sometimes_max];
5103 p->calls_crossed = 0;
5105 return sometimes_max;
5108 /* Count lengths of all regs we are currently tracking,
5109 and find new registers no longer live. */
5112 finish_sometimes_live (regs_sometimes_live, sometimes_max)
5113 struct sometimes *regs_sometimes_live;
5118 for (i = 0; i < sometimes_max; i++)
5120 register struct sometimes *p = ®s_sometimes_live[i];
5121 int regno = p->regno;
5123 sched_reg_live_length[regno] += p->live_length;
5124 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5128 /* Functions for computation of registers live/usage info. */
5130 /* It is assumed that prior to scheduling BASIC_BLOCK (b)->global_live_at_start
5131 contains the registers that are alive at the entry to b.
5133 Two passes follow: The first pass is performed before the scheduling
5134 of a region. It scans each block of the region forward, computing
5135 the set of registers alive at the end of the basic block and
5136 discard REG_DEAD notes (done by find_pre_sched_live ()).
5138 The second path is invoked after scheduling all region blocks.
5139 It scans each block of the region backward, a block being traversed
5140 only after its succesors in the region. When the set of registers
5141 live at the end of a basic block may be changed by the scheduling
5142 (this may happen for multiple blocks region), it is computed as
5143 the union of the registers live at the start of its succesors.
5144 The last-use information is updated by inserting REG_DEAD notes.
5145 (done by find_post_sched_live ()) */
5147 /* Scan all the insns to be scheduled, removing register death notes.
5148 Register death notes end up in DEAD_NOTES.
5149 Recreate the register life information for the end of this basic
5153 find_pre_sched_live (bb)
5156 rtx insn, next_tail, head, tail;
5157 int b = BB_TO_BLOCK (bb);
5159 get_block_head_tail (bb, &head, &tail);
5160 COPY_REG_SET (bb_live_regs, BASIC_BLOCK (b)->global_live_at_start);
5161 next_tail = NEXT_INSN (tail);
5163 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5165 rtx prev, next, link;
5168 /* Handle register life information. */
5169 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
5171 /* See if the register gets born here. */
5172 /* We must check for registers being born before we check for
5173 registers dying. It is possible for a register to be born and
5174 die in the same insn, e.g. reading from a volatile memory
5175 location into an otherwise unused register. Such a register
5176 must be marked as dead after this insn. */
5177 if (GET_CODE (PATTERN (insn)) == SET
5178 || GET_CODE (PATTERN (insn)) == CLOBBER)
5180 sched_note_set (PATTERN (insn), 0);
5184 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5187 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5188 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5189 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5191 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5195 /* ??? This code is obsolete and should be deleted. It
5196 is harmless though, so we will leave it in for now. */
5197 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5198 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
5199 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5202 /* Each call cobbers (makes live) all call-clobbered regs
5203 that are not global or fixed. Note that the function-value
5204 reg is a call_clobbered reg. */
5205 if (GET_CODE (insn) == CALL_INSN)
5208 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
5209 if (call_used_regs[j] && !global_regs[j]
5212 SET_REGNO_REG_SET (bb_live_regs, j);
5216 /* Need to know what registers this insn kills. */
5217 for (prev = 0, link = REG_NOTES (insn); link; link = next)
5219 next = XEXP (link, 1);
5220 if ((REG_NOTE_KIND (link) == REG_DEAD
5221 || REG_NOTE_KIND (link) == REG_UNUSED)
5222 /* Verify that the REG_NOTE has a valid value. */
5223 && GET_CODE (XEXP (link, 0)) == REG)
5225 register int regno = REGNO (XEXP (link, 0));
5229 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5231 if (REG_NOTE_KIND (link) == REG_DEAD)
5234 XEXP (prev, 1) = next;
5236 REG_NOTES (insn) = next;
5237 XEXP (link, 1) = dead_notes;
5243 if (regno < FIRST_PSEUDO_REGISTER)
5245 int j = HARD_REGNO_NREGS (regno,
5246 GET_MODE (XEXP (link, 0)));
5249 CLEAR_REGNO_REG_SET (bb_live_regs, regno+j);
5254 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
5262 INSN_REG_WEIGHT (insn) = reg_weight;
5266 /* Update register life and usage information for block bb
5267 after scheduling. Put register dead notes back in the code. */
5270 find_post_sched_live (bb)
5277 rtx head, tail, prev_head, next_tail;
5279 register struct sometimes *regs_sometimes_live;
5281 b = BB_TO_BLOCK (bb);
5283 /* Compute live regs at the end of bb as a function of its successors. */
5284 if (current_nr_blocks > 1)
5289 first_edge = e = OUT_EDGES (b);
5290 CLEAR_REG_SET (bb_live_regs);
5297 b_succ = TO_BLOCK (e);
5298 IOR_REG_SET (bb_live_regs,
5299 BASIC_BLOCK (b_succ)->global_live_at_start);
5302 while (e != first_edge);
5305 get_block_head_tail (bb, &head, &tail);
5306 next_tail = NEXT_INSN (tail);
5307 prev_head = PREV_INSN (head);
5309 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, i,
5311 sched_reg_basic_block[i] = REG_BLOCK_GLOBAL;
5314 /* If the block is empty, same regs are alive at its end and its start.
5315 since this is not guaranteed after interblock scheduling, make sure they
5316 are truly identical. */
5317 if (NEXT_INSN (prev_head) == tail
5318 && (GET_RTX_CLASS (GET_CODE (tail)) != 'i'))
5320 if (current_nr_blocks > 1)
5321 COPY_REG_SET (BASIC_BLOCK (b)->global_live_at_start, bb_live_regs);
5326 b = BB_TO_BLOCK (bb);
5327 current_block_num = b;
5329 /* Keep track of register lives. */
5330 old_live_regs = ALLOCA_REG_SET ();
5332 = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
5335 /* Initiate "sometimes" data, starting with registers live at end. */
5337 COPY_REG_SET (old_live_regs, bb_live_regs);
5338 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, 0, j,
5341 = new_sometimes_live (regs_sometimes_live,
5345 /* Scan insns back, computing regs live info. */
5346 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
5348 /* First we kill registers set by this insn, and then we
5349 make registers used by this insn live. This is the opposite
5350 order used above because we are traversing the instructions
5353 /* Strictly speaking, we should scan REG_UNUSED notes and make
5354 every register mentioned there live, however, we will just
5355 kill them again immediately below, so there doesn't seem to
5356 be any reason why we bother to do this. */
5358 /* See if this is the last notice we must take of a register. */
5359 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5362 if (GET_CODE (PATTERN (insn)) == SET
5363 || GET_CODE (PATTERN (insn)) == CLOBBER)
5364 sched_note_set (PATTERN (insn), 1);
5365 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5367 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5368 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5369 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5370 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 1);
5373 /* This code keeps life analysis information up to date. */
5374 if (GET_CODE (insn) == CALL_INSN)
5376 register struct sometimes *p;
5378 /* A call kills all call used registers that are not
5379 global or fixed, except for those mentioned in the call
5380 pattern which will be made live again later. */
5381 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5382 if (call_used_regs[i] && ! global_regs[i]
5385 CLEAR_REGNO_REG_SET (bb_live_regs, i);
5388 /* Regs live at the time of a call instruction must not
5389 go in a register clobbered by calls. Record this for
5390 all regs now live. Note that insns which are born or
5391 die in a call do not cross a call, so this must be done
5392 after the killings (above) and before the births
5394 p = regs_sometimes_live;
5395 for (i = 0; i < sometimes_max; i++, p++)
5396 if (REGNO_REG_SET_P (bb_live_regs, p->regno))
5397 p->calls_crossed += 1;
5400 /* Make every register used live, and add REG_DEAD notes for
5401 registers which were not live before we started. */
5402 attach_deaths_insn (insn);
5404 /* Find registers now made live by that instruction. */
5405 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs, old_live_regs, 0, j,
5408 = new_sometimes_live (regs_sometimes_live,
5411 IOR_REG_SET (old_live_regs, bb_live_regs);
5413 /* Count lengths of all regs we are worrying about now,
5414 and handle registers no longer live. */
5416 for (i = 0; i < sometimes_max; i++)
5418 register struct sometimes *p = ®s_sometimes_live[i];
5419 int regno = p->regno;
5421 p->live_length += 1;
5423 if (!REGNO_REG_SET_P (bb_live_regs, regno))
5425 /* This is the end of one of this register's lifetime
5426 segments. Save the lifetime info collected so far,
5427 and clear its bit in the old_live_regs entry. */
5428 sched_reg_live_length[regno] += p->live_length;
5429 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5430 CLEAR_REGNO_REG_SET (old_live_regs, p->regno);
5432 /* Delete the reg_sometimes_live entry for this reg by
5433 copying the last entry over top of it. */
5434 *p = regs_sometimes_live[--sometimes_max];
5435 /* ...and decrement i so that this newly copied entry
5436 will be processed. */
5442 finish_sometimes_live (regs_sometimes_live, sometimes_max);
5444 /* In interblock scheduling, global_live_at_start may have changed. */
5445 if (current_nr_blocks > 1)
5446 COPY_REG_SET (BASIC_BLOCK (b)->global_live_at_start, bb_live_regs);
5449 FREE_REG_SET (old_live_regs);
5450 } /* find_post_sched_live */
5452 /* After scheduling the subroutine, restore information about uses of
5460 if (n_basic_blocks > 0)
5461 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, regno,
5463 sched_reg_basic_block[regno]
5467 for (regno = 0; regno < max_regno; regno++)
5468 if (sched_reg_live_length[regno])
5472 if (REG_LIVE_LENGTH (regno) > sched_reg_live_length[regno])
5474 ";; register %d life shortened from %d to %d\n",
5475 regno, REG_LIVE_LENGTH (regno),
5476 sched_reg_live_length[regno]);
5477 /* Negative values are special; don't overwrite the current
5478 reg_live_length value if it is negative. */
5479 else if (REG_LIVE_LENGTH (regno) < sched_reg_live_length[regno]
5480 && REG_LIVE_LENGTH (regno) >= 0)
5482 ";; register %d life extended from %d to %d\n",
5483 regno, REG_LIVE_LENGTH (regno),
5484 sched_reg_live_length[regno]);
5486 if (!REG_N_CALLS_CROSSED (regno)
5487 && sched_reg_n_calls_crossed[regno])
5489 ";; register %d now crosses calls\n", regno);
5490 else if (REG_N_CALLS_CROSSED (regno)
5491 && !sched_reg_n_calls_crossed[regno]
5492 && REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5494 ";; register %d no longer crosses calls\n", regno);
5496 if (REG_BASIC_BLOCK (regno) != sched_reg_basic_block[regno]
5497 && sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5498 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5500 ";; register %d changed basic block from %d to %d\n",
5501 regno, REG_BASIC_BLOCK(regno),
5502 sched_reg_basic_block[regno]);
5505 /* Negative values are special; don't overwrite the current
5506 reg_live_length value if it is negative. */
5507 if (REG_LIVE_LENGTH (regno) >= 0)
5508 REG_LIVE_LENGTH (regno) = sched_reg_live_length[regno];
5510 if (sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5511 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5512 REG_BASIC_BLOCK(regno) = sched_reg_basic_block[regno];
5514 /* We can't change the value of reg_n_calls_crossed to zero for
5515 pseudos which are live in more than one block.
5517 This is because combine might have made an optimization which
5518 invalidated global_live_at_start and reg_n_calls_crossed,
5519 but it does not update them. If we update reg_n_calls_crossed
5520 here, the two variables are now inconsistent, and this might
5521 confuse the caller-save code into saving a register that doesn't
5522 need to be saved. This is only a problem when we zero calls
5523 crossed for a pseudo live in multiple basic blocks.
5525 Alternatively, we could try to correctly update basic block live
5526 at start here in sched, but that seems complicated.
5528 Note: it is possible that a global register became local,
5529 as result of interblock motion, but will remain marked as a
5531 if (sched_reg_n_calls_crossed[regno]
5532 || REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5533 REG_N_CALLS_CROSSED (regno) = sched_reg_n_calls_crossed[regno];
5538 /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
5539 static int clock_var;
5541 /* Move insns that became ready to fire from queue to ready list. */
5544 queue_to_ready (ready, n_ready)
5551 q_ptr = NEXT_Q (q_ptr);
5553 /* Add all pending insns that can be scheduled without stalls to the
5555 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
5558 insn = XEXP (link, 0);
5561 if (sched_verbose >= 2)
5562 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5564 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5565 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5567 ready[n_ready++] = insn;
5568 if (sched_verbose >= 2)
5569 fprintf (dump, "moving to ready without stalls\n");
5571 insn_queue[q_ptr] = 0;
5573 /* If there are no ready insns, stall until one is ready and add all
5574 of the pending insns at that point to the ready list. */
5577 register int stalls;
5579 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
5581 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
5583 for (; link; link = XEXP (link, 1))
5585 insn = XEXP (link, 0);
5588 if (sched_verbose >= 2)
5589 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5591 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5592 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5594 ready[n_ready++] = insn;
5595 if (sched_verbose >= 2)
5596 fprintf (dump, "moving to ready with %d stalls\n", stalls);
5598 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
5605 if (sched_verbose && stalls)
5606 visualize_stall_cycles (BB_TO_BLOCK (target_bb), stalls);
5607 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
5608 clock_var += stalls;
5613 /* Print the ready list for debugging purposes. Callable from debugger. */
5616 debug_ready_list (ready, n_ready)
5622 for (i = 0; i < n_ready; i++)
5624 fprintf (dump, " %d", INSN_UID (ready[i]));
5625 if (current_nr_blocks > 1 && INSN_BB (ready[i]) != target_bb)
5626 fprintf (dump, "/b%d", INSN_BLOCK (ready[i]));
5628 fprintf (dump, "\n");
5631 /* Print names of units on which insn can/should execute, for debugging. */
5634 insn_print_units (insn)
5638 int unit = insn_unit (insn);
5641 fprintf (dump, "none");
5643 fprintf (dump, "%s", function_units[unit].name);
5646 fprintf (dump, "[");
5647 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
5650 fprintf (dump, "%s", function_units[i].name);
5652 fprintf (dump, " ");
5654 fprintf (dump, "]");
5658 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5659 of a basic block. If more lines are needed, table is splitted to two.
5660 n_visual_lines is the number of lines printed so far for a block.
5661 visual_tbl contains the block visualization info.
5662 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5663 #define MAX_VISUAL_LINES 100
5668 rtx vis_no_unit[10];
5670 /* Finds units that are in use in this fuction. Required only
5671 for visualization. */
5674 init_target_units ()
5679 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
5681 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5684 unit = insn_unit (insn);
5687 target_units |= ~unit;
5689 target_units |= (1 << unit);
5693 /* Return the length of the visualization table. */
5696 get_visual_tbl_length ()
5702 /* Compute length of one field in line. */
5703 s = (char *) alloca (INSN_LEN + 6);
5704 sprintf (s, " %33s", "uname");
5707 /* Compute length of one line. */
5710 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5711 if (function_units[unit].bitmask & target_units)
5712 for (i = 0; i < function_units[unit].multiplicity; i++)
5715 n += strlen ("\n") + 2;
5717 /* Compute length of visualization string. */
5718 return (MAX_VISUAL_LINES * n);
5721 /* Init block visualization debugging info. */
5724 init_block_visualization ()
5726 strcpy (visual_tbl, "");
5734 safe_concat (buf, cur, str)
5739 char *end = buf + BUF_LEN - 2; /* Leave room for null. */
5748 while (cur < end && (c = *str++) != '\0')
5755 /* This recognizes rtx, I classified as expressions. These are always
5756 represent some action on values or results of other expression, that
5757 may be stored in objects representing values. */
5760 print_exp (buf, x, verbose)
5768 const char *fun = (char *)0;
5773 for (i = 0; i < 4; i++)
5779 switch (GET_CODE (x))
5782 op[0] = XEXP (x, 0);
5783 if (GET_CODE (XEXP (x, 1)) == CONST_INT
5784 && INTVAL (XEXP (x, 1)) < 0)
5787 op[1] = GEN_INT (-INTVAL (XEXP (x, 1)));
5792 op[1] = XEXP (x, 1);
5796 op[0] = XEXP (x, 0);
5798 op[1] = XEXP (x, 1);
5802 op[0] = XEXP (x, 0);
5804 op[1] = XEXP (x, 1);
5808 op[0] = XEXP (x, 0);
5809 op[1] = XEXP (x, 1);
5813 op[0] = XEXP (x, 0);
5816 op[0] = XEXP (x, 0);
5818 op[1] = XEXP (x, 1);
5821 op[0] = XEXP (x, 0);
5823 op[1] = XEXP (x, 1);
5827 op[0] = XEXP (x, 0);
5828 op[1] = XEXP (x, 1);
5831 op[0] = XEXP (x, 0);
5833 op[1] = XEXP (x, 1);
5837 op[0] = XEXP (x, 0);
5838 op[1] = XEXP (x, 1);
5842 op[0] = XEXP (x, 0);
5843 op[1] = XEXP (x, 1);
5847 op[0] = XEXP (x, 0);
5848 op[1] = XEXP (x, 1);
5852 op[0] = XEXP (x, 0);
5853 op[1] = XEXP (x, 1);
5857 op[0] = XEXP (x, 0);
5858 op[1] = XEXP (x, 1);
5862 op[0] = XEXP (x, 0);
5865 op[0] = XEXP (x, 0);
5867 op[1] = XEXP (x, 1);
5870 op[0] = XEXP (x, 0);
5872 op[1] = XEXP (x, 1);
5875 op[0] = XEXP (x, 0);
5877 op[1] = XEXP (x, 1);
5880 op[0] = XEXP (x, 0);
5882 op[1] = XEXP (x, 1);
5885 op[0] = XEXP (x, 0);
5887 op[1] = XEXP (x, 1);
5890 op[0] = XEXP (x, 0);
5892 op[1] = XEXP (x, 1);
5895 op[0] = XEXP (x, 0);
5897 op[1] = XEXP (x, 1);
5900 op[0] = XEXP (x, 0);
5902 op[1] = XEXP (x, 1);
5906 op[0] = XEXP (x, 0);
5910 op[0] = XEXP (x, 0);
5914 op[0] = XEXP (x, 0);
5917 op[0] = XEXP (x, 0);
5919 op[1] = XEXP (x, 1);
5922 op[0] = XEXP (x, 0);
5924 op[1] = XEXP (x, 1);
5927 op[0] = XEXP (x, 0);
5929 op[1] = XEXP (x, 1);
5933 op[0] = XEXP (x, 0);
5934 op[1] = XEXP (x, 1);
5937 op[0] = XEXP (x, 0);
5939 op[1] = XEXP (x, 1);
5943 op[0] = XEXP (x, 0);
5944 op[1] = XEXP (x, 1);
5947 op[0] = XEXP (x, 0);
5949 op[1] = XEXP (x, 1);
5953 op[0] = XEXP (x, 0);
5954 op[1] = XEXP (x, 1);
5957 op[0] = XEXP (x, 0);
5959 op[1] = XEXP (x, 1);
5963 op[0] = XEXP (x, 0);
5964 op[1] = XEXP (x, 1);
5967 fun = (verbose) ? "sign_extract" : "sxt";
5968 op[0] = XEXP (x, 0);
5969 op[1] = XEXP (x, 1);
5970 op[2] = XEXP (x, 2);
5973 fun = (verbose) ? "zero_extract" : "zxt";
5974 op[0] = XEXP (x, 0);
5975 op[1] = XEXP (x, 1);
5976 op[2] = XEXP (x, 2);
5979 fun = (verbose) ? "sign_extend" : "sxn";
5980 op[0] = XEXP (x, 0);
5983 fun = (verbose) ? "zero_extend" : "zxn";
5984 op[0] = XEXP (x, 0);
5987 fun = (verbose) ? "float_extend" : "fxn";
5988 op[0] = XEXP (x, 0);
5991 fun = (verbose) ? "trunc" : "trn";
5992 op[0] = XEXP (x, 0);
5994 case FLOAT_TRUNCATE:
5995 fun = (verbose) ? "float_trunc" : "ftr";
5996 op[0] = XEXP (x, 0);
5999 fun = (verbose) ? "float" : "flt";
6000 op[0] = XEXP (x, 0);
6002 case UNSIGNED_FLOAT:
6003 fun = (verbose) ? "uns_float" : "ufl";
6004 op[0] = XEXP (x, 0);
6008 op[0] = XEXP (x, 0);
6011 fun = (verbose) ? "uns_fix" : "ufx";
6012 op[0] = XEXP (x, 0);
6016 op[0] = XEXP (x, 0);
6020 op[0] = XEXP (x, 0);
6023 op[0] = XEXP (x, 0);
6027 op[0] = XEXP (x, 0);
6032 op[0] = XEXP (x, 0);
6036 op[1] = XEXP (x, 1);
6041 op[0] = XEXP (x, 0);
6043 op[1] = XEXP (x, 1);
6045 op[2] = XEXP (x, 2);
6050 op[0] = TRAP_CONDITION (x);
6053 case UNSPEC_VOLATILE:
6055 cur = safe_concat (buf, cur, "unspec");
6056 if (GET_CODE (x) == UNSPEC_VOLATILE)
6057 cur = safe_concat (buf, cur, "/v");
6058 cur = safe_concat (buf, cur, "[");
6060 for (i = 0; i < XVECLEN (x, 0); i++)
6062 print_pattern (tmp, XVECEXP (x, 0, i), verbose);
6063 cur = safe_concat (buf, cur, sep);
6064 cur = safe_concat (buf, cur, tmp);
6067 cur = safe_concat (buf, cur, "] ");
6068 sprintf (tmp, "%d", XINT (x, 1));
6069 cur = safe_concat (buf, cur, tmp);
6073 /* If (verbose) debug_rtx (x); */
6074 st[0] = GET_RTX_NAME (GET_CODE (x));
6078 /* Print this as a function? */
6081 cur = safe_concat (buf, cur, fun);
6082 cur = safe_concat (buf, cur, "(");
6085 for (i = 0; i < 4; i++)
6088 cur = safe_concat (buf, cur, st[i]);
6093 cur = safe_concat (buf, cur, ",");
6095 print_value (tmp, op[i], verbose);
6096 cur = safe_concat (buf, cur, tmp);
6101 cur = safe_concat (buf, cur, ")");
6104 /* Prints rtxes, I customly classified as values. They're constants,
6105 registers, labels, symbols and memory accesses. */
6108 print_value (buf, x, verbose)
6116 switch (GET_CODE (x))
6119 sprintf (t, HOST_WIDE_INT_PRINT_HEX, INTVAL (x));
6120 cur = safe_concat (buf, cur, t);
6123 sprintf (t, "<0x%lx,0x%lx>", (long)XWINT (x, 2), (long)XWINT (x, 3));
6124 cur = safe_concat (buf, cur, t);
6127 cur = safe_concat (buf, cur, "\"");
6128 cur = safe_concat (buf, cur, XSTR (x, 0));
6129 cur = safe_concat (buf, cur, "\"");
6132 cur = safe_concat (buf, cur, "`");
6133 cur = safe_concat (buf, cur, XSTR (x, 0));
6134 cur = safe_concat (buf, cur, "'");
6137 sprintf (t, "L%d", INSN_UID (XEXP (x, 0)));
6138 cur = safe_concat (buf, cur, t);
6141 print_value (t, XEXP (x, 0), verbose);
6142 cur = safe_concat (buf, cur, "const(");
6143 cur = safe_concat (buf, cur, t);
6144 cur = safe_concat (buf, cur, ")");
6147 print_value (t, XEXP (x, 0), verbose);
6148 cur = safe_concat (buf, cur, "high(");
6149 cur = safe_concat (buf, cur, t);
6150 cur = safe_concat (buf, cur, ")");
6153 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
6155 int c = reg_names[ REGNO (x) ][0];
6156 if (c >= '0' && c <= '9')
6157 cur = safe_concat (buf, cur, "%");
6159 cur = safe_concat (buf, cur, reg_names[ REGNO (x) ]);
6163 sprintf (t, "r%d", REGNO (x));
6164 cur = safe_concat (buf, cur, t);
6168 print_value (t, SUBREG_REG (x), verbose);
6169 cur = safe_concat (buf, cur, t);
6170 sprintf (t, "#%d", SUBREG_WORD (x));
6171 cur = safe_concat (buf, cur, t);
6174 cur = safe_concat (buf, cur, "scratch");
6177 cur = safe_concat (buf, cur, "cc0");
6180 cur = safe_concat (buf, cur, "pc");
6183 print_value (t, XEXP (x, 0), verbose);
6184 cur = safe_concat (buf, cur, "[");
6185 cur = safe_concat (buf, cur, t);
6186 cur = safe_concat (buf, cur, "]");
6189 print_exp (t, x, verbose);
6190 cur = safe_concat (buf, cur, t);
6195 /* The next step in insn detalization, its pattern recognition. */
6198 print_pattern (buf, x, verbose)
6203 char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
6205 switch (GET_CODE (x))
6208 print_value (t1, SET_DEST (x), verbose);
6209 print_value (t2, SET_SRC (x), verbose);
6210 sprintf (buf, "%s=%s", t1, t2);
6213 sprintf (buf, "return");
6216 print_exp (buf, x, verbose);
6219 print_value (t1, XEXP (x, 0), verbose);
6220 sprintf (buf, "clobber %s", t1);
6223 print_value (t1, XEXP (x, 0), verbose);
6224 sprintf (buf, "use %s", t1);
6231 for (i = 0; i < XVECLEN (x, 0); i++)
6233 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6234 sprintf (t3, "%s%s;", t1, t2);
6237 sprintf (buf, "%s}", t1);
6244 sprintf (t1, "%%{");
6245 for (i = 0; i < XVECLEN (x, 0); i++)
6247 print_insn (t2, XVECEXP (x, 0, i), verbose);
6248 sprintf (t3, "%s%s;", t1, t2);
6251 sprintf (buf, "%s%%}", t1);
6255 sprintf (buf, "asm {%s}", XSTR (x, 0));
6260 print_value (buf, XEXP (x, 0), verbose);
6263 print_value (t1, TRAP_CONDITION (x), verbose);
6264 sprintf (buf, "trap_if %s", t1);
6270 sprintf (t1, "unspec{");
6271 for (i = 0; i < XVECLEN (x, 0); i++)
6273 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6274 sprintf (t3, "%s%s;", t1, t2);
6277 sprintf (buf, "%s}", t1);
6280 case UNSPEC_VOLATILE:
6284 sprintf (t1, "unspec/v{");
6285 for (i = 0; i < XVECLEN (x, 0); i++)
6287 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6288 sprintf (t3, "%s%s;", t1, t2);
6291 sprintf (buf, "%s}", t1);
6295 print_value (buf, x, verbose);
6297 } /* print_pattern */
6299 /* This is the main function in rtl visualization mechanism. It
6300 accepts an rtx and tries to recognize it as an insn, then prints it
6301 properly in human readable form, resembling assembler mnemonics.
6302 For every insn it prints its UID and BB the insn belongs too.
6303 (Probably the last "option" should be extended somehow, since it
6304 depends now on sched.c inner variables ...) */
6307 print_insn (buf, x, verbose)
6315 switch (GET_CODE (x))
6318 print_pattern (t, PATTERN (x), verbose);
6320 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (x),
6323 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6326 print_pattern (t, PATTERN (x), verbose);
6328 sprintf (buf, "b%d: i% 4d: jump %s", INSN_BB (x),
6331 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6335 if (GET_CODE (x) == PARALLEL)
6337 x = XVECEXP (x, 0, 0);
6338 print_pattern (t, x, verbose);
6341 strcpy (t, "call <...>");
6343 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (insn),
6344 INSN_UID (insn), t);
6346 sprintf (buf, "%-4d %s", INSN_UID (insn), t);
6349 sprintf (buf, "L%d:", INSN_UID (x));
6352 sprintf (buf, "i% 4d: barrier", INSN_UID (x));
6355 if (NOTE_LINE_NUMBER (x) > 0)
6356 sprintf (buf, "%4d note \"%s\" %d", INSN_UID (x),
6357 NOTE_SOURCE_FILE (x), NOTE_LINE_NUMBER (x));
6359 sprintf (buf, "%4d %s", INSN_UID (x),
6360 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x)));
6365 sprintf (buf, "Not an INSN at all\n");
6369 sprintf (buf, "i%-4d <What?>", INSN_UID (x));
6373 /* Print visualization debugging info. */
6376 print_block_visualization (b, s)
6383 fprintf (dump, "\n;; ==================== scheduling visualization for block %d %s \n", b, s);
6385 /* Print names of units. */
6386 fprintf (dump, ";; %-8s", "clock");
6387 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6388 if (function_units[unit].bitmask & target_units)
6389 for (i = 0; i < function_units[unit].multiplicity; i++)
6390 fprintf (dump, " %-33s", function_units[unit].name);
6391 fprintf (dump, " %-8s\n", "no-unit");
6393 fprintf (dump, ";; %-8s", "=====");
6394 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6395 if (function_units[unit].bitmask & target_units)
6396 for (i = 0; i < function_units[unit].multiplicity; i++)
6397 fprintf (dump, " %-33s", "==============================");
6398 fprintf (dump, " %-8s\n", "=======");
6400 /* Print insns in each cycle. */
6401 fprintf (dump, "%s\n", visual_tbl);
6404 /* Print insns in the 'no_unit' column of visualization. */
6407 visualize_no_unit (insn)
6410 vis_no_unit[n_vis_no_unit] = insn;
6414 /* Print insns scheduled in clock, for visualization. */
6417 visualize_scheduled_insns (b, clock)
6422 /* If no more room, split table into two. */
6423 if (n_visual_lines >= MAX_VISUAL_LINES)
6425 print_block_visualization (b, "(incomplete)");
6426 init_block_visualization ();
6431 sprintf (visual_tbl + strlen (visual_tbl), ";; %-8d", clock);
6432 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6433 if (function_units[unit].bitmask & target_units)
6434 for (i = 0; i < function_units[unit].multiplicity; i++)
6436 int instance = unit + i * FUNCTION_UNITS_SIZE;
6437 rtx insn = unit_last_insn[instance];
6439 /* Print insns that still keep the unit busy. */
6441 actual_hazard_this_instance (unit, instance, insn, clock, 0))
6444 print_insn (str, insn, 0);
6445 str[INSN_LEN] = '\0';
6446 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", str);
6449 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", "------------------------------");
6452 /* Print insns that are not assigned to any unit. */
6453 for (i = 0; i < n_vis_no_unit; i++)
6454 sprintf (visual_tbl + strlen (visual_tbl), " %-8d",
6455 INSN_UID (vis_no_unit[i]));
6458 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6461 /* Print stalled cycles. */
6464 visualize_stall_cycles (b, stalls)
6469 /* If no more room, split table into two. */
6470 if (n_visual_lines >= MAX_VISUAL_LINES)
6472 print_block_visualization (b, "(incomplete)");
6473 init_block_visualization ();
6478 sprintf (visual_tbl + strlen (visual_tbl), ";; ");
6479 for (i = 0; i < stalls; i++)
6480 sprintf (visual_tbl + strlen (visual_tbl), ".");
6481 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6484 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
6487 move_insn1 (insn, last)
6490 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
6491 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
6493 NEXT_INSN (insn) = NEXT_INSN (last);
6494 PREV_INSN (NEXT_INSN (last)) = insn;
6496 NEXT_INSN (last) = insn;
6497 PREV_INSN (insn) = last;
6502 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
6503 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
6504 NOTEs. The REG_DEAD note following first one is contains the saved
6505 value for NOTE_BLOCK_NUMBER which is useful for
6506 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
6507 output by the instruction scheduler. Return the new value of LAST. */
6510 reemit_notes (insn, last)
6517 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
6519 if (REG_NOTE_KIND (note) == REG_DEAD
6520 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6522 int note_type = INTVAL (XEXP (note, 0));
6523 if (note_type == NOTE_INSN_SETJMP)
6525 retval = emit_note_after (NOTE_INSN_SETJMP, insn);
6526 CONST_CALL_P (retval) = CONST_CALL_P (note);
6527 remove_note (insn, note);
6528 note = XEXP (note, 1);
6530 else if (note_type == NOTE_INSN_RANGE_START
6531 || note_type == NOTE_INSN_RANGE_END)
6533 last = emit_note_before (note_type, last);
6534 remove_note (insn, note);
6535 note = XEXP (note, 1);
6536 NOTE_RANGE_INFO (last) = XEXP (note, 0);
6540 last = emit_note_before (note_type, last);
6541 remove_note (insn, note);
6542 note = XEXP (note, 1);
6543 if (note_type == NOTE_INSN_EH_REGION_BEG
6544 || note_type == NOTE_INSN_EH_REGION_END)
6545 NOTE_EH_HANDLER (last) = INTVAL (XEXP (note, 0));
6547 remove_note (insn, note);
6553 /* Move INSN, and all insns which should be issued before it,
6554 due to SCHED_GROUP_P flag. Reemit notes if needed.
6556 Return the last insn emitted by the scheduler, which is the
6557 return value from the first call to reemit_notes. */
6560 move_insn (insn, last)
6565 /* If INSN has SCHED_GROUP_P set, then issue it and any other
6566 insns with SCHED_GROUP_P set first. */
6567 while (SCHED_GROUP_P (insn))
6569 rtx prev = PREV_INSN (insn);
6571 /* Move a SCHED_GROUP_P insn. */
6572 move_insn1 (insn, last);
6573 /* If this is the first call to reemit_notes, then record
6574 its return value. */
6575 if (retval == NULL_RTX)
6576 retval = reemit_notes (insn, insn);
6578 reemit_notes (insn, insn);
6582 /* Now move the first non SCHED_GROUP_P insn. */
6583 move_insn1 (insn, last);
6585 /* If this is the first call to reemit_notes, then record
6586 its return value. */
6587 if (retval == NULL_RTX)
6588 retval = reemit_notes (insn, insn);
6590 reemit_notes (insn, insn);
6595 /* Return an insn which represents a SCHED_GROUP, which is
6596 the last insn in the group. */
6607 insn = next_nonnote_insn (insn);
6609 while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
6614 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
6615 possibly bringing insns from subsequent blocks in the same region.
6616 Return number of insns scheduled. */
6619 schedule_block (bb, rgn_n_insns)
6623 /* Local variables. */
6629 /* Flow block of this bb. */
6630 int b = BB_TO_BLOCK (bb);
6632 /* target_n_insns == number of insns in b before scheduling starts.
6633 sched_target_n_insns == how many of b's insns were scheduled.
6634 sched_n_insns == how many insns were scheduled in b. */
6635 int target_n_insns = 0;
6636 int sched_target_n_insns = 0;
6637 int sched_n_insns = 0;
6639 #define NEED_NOTHING 0
6644 /* Head/tail info for this block. */
6651 /* We used to have code to avoid getting parameters moved from hard
6652 argument registers into pseudos.
6654 However, it was removed when it proved to be of marginal benefit
6655 and caused problems because schedule_block and compute_forward_dependences
6656 had different notions of what the "head" insn was. */
6657 get_block_head_tail (bb, &head, &tail);
6659 /* Interblock scheduling could have moved the original head insn from this
6660 block into a proceeding block. This may also cause schedule_block and
6661 compute_forward_dependences to have different notions of what the
6664 If the interblock movement happened to make this block start with
6665 some notes (LOOP, EH or SETJMP) before the first real insn, then
6666 HEAD will have various special notes attached to it which must be
6667 removed so that we don't end up with extra copies of the notes. */
6668 if (GET_RTX_CLASS (GET_CODE (head)) == 'i')
6672 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
6673 if (REG_NOTE_KIND (note) == REG_DEAD
6674 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6675 remove_note (head, note);
6678 next_tail = NEXT_INSN (tail);
6679 prev_head = PREV_INSN (head);
6681 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6682 to schedule this block. */
6684 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6685 return (sched_n_insns);
6690 fprintf (dump, ";; ======================================================\n");
6692 ";; -- basic block %d from %d to %d -- %s reload\n",
6693 b, INSN_UID (BLOCK_HEAD (b)), INSN_UID (BLOCK_END (b)),
6694 (reload_completed ? "after" : "before"));
6695 fprintf (dump, ";; ======================================================\n");
6696 fprintf (dump, "\n");
6698 visual_tbl = (char *) alloca (get_visual_tbl_length ());
6699 init_block_visualization ();
6702 /* Remove remaining note insns from the block, save them in
6703 note_list. These notes are restored at the end of
6704 schedule_block (). */
6706 rm_other_notes (head, tail);
6710 /* Prepare current target block info. */
6711 if (current_nr_blocks > 1)
6713 candidate_table = (candidate *) alloca (current_nr_blocks
6714 * sizeof (candidate));
6717 /* ??? It is not clear why bblst_size is computed this way. The original
6718 number was clearly too small as it resulted in compiler failures.
6719 Multiplying by the original number by 2 (to account for update_bbs
6720 members) seems to be a reasonable solution. */
6721 /* ??? Or perhaps there is a bug somewhere else in this file? */
6722 bblst_size = (current_nr_blocks - bb) * rgn_nr_edges * 2;
6723 bblst_table = (int *) alloca (bblst_size * sizeof (int));
6725 bitlst_table_last = 0;
6726 bitlst_table_size = rgn_nr_edges;
6727 bitlst_table = (int *) alloca (rgn_nr_edges * sizeof (int));
6729 compute_trg_info (bb);
6734 /* Allocate the ready list. */
6735 ready = (rtx *) alloca ((rgn_n_insns + 1) * sizeof (rtx));
6737 /* Print debugging information. */
6738 if (sched_verbose >= 5)
6739 debug_dependencies ();
6742 /* Initialize ready list with all 'ready' insns in target block.
6743 Count number of insns in the target block being scheduled. */
6745 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6749 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6751 next = NEXT_INSN (insn);
6753 if (INSN_DEP_COUNT (insn) == 0
6754 && (SCHED_GROUP_P (next) == 0 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6755 ready[n_ready++] = insn;
6756 if (!(SCHED_GROUP_P (insn)))
6760 /* Add to ready list all 'ready' insns in valid source blocks.
6761 For speculative insns, check-live, exception-free, and
6763 for (bb_src = bb + 1; bb_src < current_nr_blocks; bb_src++)
6764 if (IS_VALID (bb_src))
6770 get_block_head_tail (bb_src, &head, &tail);
6771 src_next_tail = NEXT_INSN (tail);
6775 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6778 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
6780 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6783 if (!CANT_MOVE (insn)
6784 && (!IS_SPECULATIVE_INSN (insn)
6785 || (insn_issue_delay (insn) <= 3
6786 && check_live (insn, bb_src)
6787 && is_exception_free (insn, bb_src, target_bb))))
6792 /* Note that we havn't squirrled away the notes for
6793 blocks other than the current. So if this is a
6794 speculative insn, NEXT might otherwise be a note. */
6795 next = next_nonnote_insn (insn);
6796 if (INSN_DEP_COUNT (insn) == 0
6797 && (SCHED_GROUP_P (next) == 0
6798 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6799 ready[n_ready++] = insn;
6804 #ifdef MD_SCHED_INIT
6805 MD_SCHED_INIT (dump, sched_verbose);
6808 /* No insns scheduled in this block yet. */
6809 last_scheduled_insn = 0;
6811 /* Q_SIZE is the total number of insns in the queue. */
6815 bzero ((char *) insn_queue, sizeof (insn_queue));
6817 /* Start just before the beginning of time. */
6820 /* We start inserting insns after PREV_HEAD. */
6823 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6824 new_needs = (NEXT_INSN (prev_head) == BLOCK_HEAD (b)
6825 ? NEED_HEAD : NEED_NOTHING);
6826 if (PREV_INSN (next_tail) == BLOCK_END (b))
6827 new_needs |= NEED_TAIL;
6829 /* Loop until all the insns in BB are scheduled. */
6830 while (sched_target_n_insns < target_n_insns)
6836 /* Add to the ready list all pending insns that can be issued now.
6837 If there are no ready insns, increment clock until one
6838 is ready and add all pending insns at that point to the ready
6840 n_ready = queue_to_ready (ready, n_ready);
6845 if (sched_verbose >= 2)
6847 fprintf (dump, ";;\t\tReady list after queue_to_ready: ");
6848 debug_ready_list (ready, n_ready);
6851 /* Sort the ready list based on priority. */
6852 SCHED_SORT (ready, n_ready);
6854 /* Allow the target to reorder the list, typically for
6855 better instruction bundling. */
6856 #ifdef MD_SCHED_REORDER
6857 MD_SCHED_REORDER (dump, sched_verbose, ready, n_ready, clock_var,
6860 can_issue_more = issue_rate;
6865 fprintf (dump, "\n;;\tReady list (t =%3d): ", clock_var);
6866 debug_ready_list (ready, n_ready);
6869 /* Issue insns from ready list. */
6870 while (n_ready != 0 && can_issue_more)
6872 /* Select and remove the insn from the ready list. */
6873 rtx insn = ready[--n_ready];
6874 int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
6878 queue_insn (insn, cost);
6882 /* An interblock motion? */
6883 if (INSN_BB (insn) != target_bb)
6887 if (IS_SPECULATIVE_INSN (insn))
6889 if (!check_live (insn, INSN_BB (insn)))
6891 update_live (insn, INSN_BB (insn));
6893 /* For speculative load, mark insns fed by it. */
6894 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
6895 set_spec_fed (insn);
6902 while (SCHED_GROUP_P (temp))
6903 temp = PREV_INSN (temp);
6905 /* Update source block boundaries. */
6906 b1 = INSN_BLOCK (temp);
6907 if (temp == BLOCK_HEAD (b1)
6908 && insn == BLOCK_END (b1))
6910 /* We moved all the insns in the basic block.
6911 Emit a note after the last insn and update the
6912 begin/end boundaries to point to the note. */
6913 emit_note_after (NOTE_INSN_DELETED, insn);
6914 BLOCK_END (b1) = NEXT_INSN (insn);
6915 BLOCK_HEAD (b1) = NEXT_INSN (insn);
6917 else if (insn == BLOCK_END (b1))
6919 /* We took insns from the end of the basic block,
6920 so update the end of block boundary so that it
6921 points to the first insn we did not move. */
6922 BLOCK_END (b1) = PREV_INSN (temp);
6924 else if (temp == BLOCK_HEAD (b1))
6926 /* We took insns from the start of the basic block,
6927 so update the start of block boundary so that
6928 it points to the first insn we did not move. */
6929 BLOCK_HEAD (b1) = NEXT_INSN (insn);
6934 /* In block motion. */
6935 sched_target_n_insns++;
6938 last_scheduled_insn = insn;
6939 last = move_insn (insn, last);
6942 #ifdef MD_SCHED_VARIABLE_ISSUE
6943 MD_SCHED_VARIABLE_ISSUE (dump, sched_verbose, insn,
6949 n_ready = schedule_insn (insn, ready, n_ready, clock_var);
6951 /* Close this block after scheduling its jump. */
6952 if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
6958 visualize_scheduled_insns (b, clock_var);
6964 fprintf (dump, ";;\tReady list (final): ");
6965 debug_ready_list (ready, n_ready);
6966 print_block_visualization (b, "");
6969 /* Sanity check -- queue must be empty now. Meaningless if region has
6971 if (current_nr_blocks > 1)
6972 if (!flag_schedule_interblock && q_size != 0)
6975 /* Update head/tail boundaries. */
6976 head = NEXT_INSN (prev_head);
6979 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6980 previously found among the insns. Insert them at the beginning
6984 rtx note_head = note_list;
6986 while (PREV_INSN (note_head))
6988 note_head = PREV_INSN (note_head);
6991 PREV_INSN (note_head) = PREV_INSN (head);
6992 NEXT_INSN (PREV_INSN (head)) = note_head;
6993 PREV_INSN (head) = note_list;
6994 NEXT_INSN (note_list) = head;
6998 /* Update target block boundaries. */
6999 if (new_needs & NEED_HEAD)
7000 BLOCK_HEAD (b) = head;
7002 if (new_needs & NEED_TAIL)
7003 BLOCK_END (b) = tail;
7008 fprintf (dump, ";; total time = %d\n;; new basic block head = %d\n",
7009 clock_var, INSN_UID (BLOCK_HEAD (b)));
7010 fprintf (dump, ";; new basic block end = %d\n\n",
7011 INSN_UID (BLOCK_END (b)));
7014 return (sched_n_insns);
7015 } /* schedule_block () */
7018 /* Print the bit-set of registers, S, callable from debugger. */
7021 debug_reg_vector (s)
7026 EXECUTE_IF_SET_IN_REG_SET (s, 0, regno,
7028 fprintf (dump, " %d", regno);
7031 fprintf (dump, "\n");
7034 /* Use the backward dependences from LOG_LINKS to build
7035 forward dependences in INSN_DEPEND. */
7038 compute_block_forward_dependences (bb)
7044 enum reg_note dep_type;
7046 get_block_head_tail (bb, &head, &tail);
7047 next_tail = NEXT_INSN (tail);
7048 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
7050 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7053 insn = group_leader (insn);
7055 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
7057 rtx x = group_leader (XEXP (link, 0));
7060 if (x != XEXP (link, 0))
7063 /* Ignore dependences upon deleted insn. */
7064 if (GET_CODE (x) == NOTE || INSN_DELETED_P (x))
7066 if (find_insn_list (insn, INSN_DEPEND (x)))
7069 new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
7071 dep_type = REG_NOTE_KIND (link);
7072 PUT_REG_NOTE_KIND (new_link, dep_type);
7074 INSN_DEPEND (x) = new_link;
7075 INSN_DEP_COUNT (insn) += 1;
7080 /* Initialize variables for region data dependence analysis.
7081 n_bbs is the number of region blocks. */
7083 __inline static void
7084 init_rgn_data_dependences (n_bbs)
7089 /* Variables for which one copy exists for each block. */
7090 bzero ((char *) bb_pending_read_insns, n_bbs * sizeof (rtx));
7091 bzero ((char *) bb_pending_read_mems, n_bbs * sizeof (rtx));
7092 bzero ((char *) bb_pending_write_insns, n_bbs * sizeof (rtx));
7093 bzero ((char *) bb_pending_write_mems, n_bbs * sizeof (rtx));
7094 bzero ((char *) bb_pending_lists_length, n_bbs * sizeof (rtx));
7095 bzero ((char *) bb_last_pending_memory_flush, n_bbs * sizeof (rtx));
7096 bzero ((char *) bb_last_function_call, n_bbs * sizeof (rtx));
7097 bzero ((char *) bb_sched_before_next_call, n_bbs * sizeof (rtx));
7099 /* Create an insn here so that we can hang dependencies off of it later. */
7100 for (bb = 0; bb < n_bbs; bb++)
7102 bb_sched_before_next_call[bb] =
7103 gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
7104 NULL_RTX, 0, NULL_RTX, NULL_RTX);
7105 LOG_LINKS (bb_sched_before_next_call[bb]) = 0;
7109 /* Add dependences so that branches are scheduled to run last in their
7113 add_branch_dependences (head, tail)
7119 /* For all branches, calls, uses, and cc0 setters, force them to remain
7120 in order at the end of the block by adding dependencies and giving
7121 the last a high priority. There may be notes present, and prev_head
7124 Branches must obviously remain at the end. Calls should remain at the
7125 end since moving them results in worse register allocation. Uses remain
7126 at the end to ensure proper register allocation. cc0 setters remaim
7127 at the end because they can't be moved away from their cc0 user. */
7130 while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
7131 || (GET_CODE (insn) == INSN
7132 && (GET_CODE (PATTERN (insn)) == USE
7134 || sets_cc0_p (PATTERN (insn))
7137 || GET_CODE (insn) == NOTE)
7139 if (GET_CODE (insn) != NOTE)
7142 && !find_insn_list (insn, LOG_LINKS (last)))
7144 add_dependence (last, insn, REG_DEP_ANTI);
7145 INSN_REF_COUNT (insn)++;
7148 CANT_MOVE (insn) = 1;
7151 /* Skip over insns that are part of a group.
7152 Make each insn explicitly depend on the previous insn.
7153 This ensures that only the group header will ever enter
7154 the ready queue (and, when scheduled, will automatically
7155 schedule the SCHED_GROUP_P block). */
7156 while (SCHED_GROUP_P (insn))
7158 rtx temp = prev_nonnote_insn (insn);
7159 add_dependence (insn, temp, REG_DEP_ANTI);
7164 /* Don't overrun the bounds of the basic block. */
7168 insn = PREV_INSN (insn);
7171 /* Make sure these insns are scheduled last in their block. */
7174 while (insn != head)
7176 insn = prev_nonnote_insn (insn);
7178 if (INSN_REF_COUNT (insn) != 0)
7181 add_dependence (last, insn, REG_DEP_ANTI);
7182 INSN_REF_COUNT (insn) = 1;
7184 /* Skip over insns that are part of a group. */
7185 while (SCHED_GROUP_P (insn))
7186 insn = prev_nonnote_insn (insn);
7190 /* Compute backward dependences inside bb. In a multiple blocks region:
7191 (1) a bb is analyzed after its predecessors, and (2) the lists in
7192 effect at the end of bb (after analyzing for bb) are inherited by
7195 Specifically for reg-reg data dependences, the block insns are
7196 scanned by sched_analyze () top-to-bottom. Two lists are
7197 maintained by sched_analyze (): reg_last_sets[] for register DEFs,
7198 and reg_last_uses[] for register USEs.
7200 When analysis is completed for bb, we update for its successors:
7201 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7202 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7204 The mechanism for computing mem-mem data dependence is very
7205 similar, and the result is interblock dependences in the region. */
7208 compute_block_backward_dependences (bb)
7214 int max_reg = max_reg_num ();
7216 b = BB_TO_BLOCK (bb);
7218 if (current_nr_blocks == 1)
7220 reg_last_uses = (rtx *) alloca (max_reg * sizeof (rtx));
7221 reg_last_sets = (rtx *) alloca (max_reg * sizeof (rtx));
7222 reg_last_clobbers = (rtx *) alloca (max_reg * sizeof (rtx));
7224 bzero ((char *) reg_last_uses, max_reg * sizeof (rtx));
7225 bzero ((char *) reg_last_sets, max_reg * sizeof (rtx));
7226 bzero ((char *) reg_last_clobbers, max_reg * sizeof (rtx));
7228 pending_read_insns = 0;
7229 pending_read_mems = 0;
7230 pending_write_insns = 0;
7231 pending_write_mems = 0;
7232 pending_lists_length = 0;
7233 last_function_call = 0;
7234 last_pending_memory_flush = 0;
7235 sched_before_next_call
7236 = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
7237 NULL_RTX, 0, NULL_RTX, NULL_RTX);
7238 LOG_LINKS (sched_before_next_call) = 0;
7242 reg_last_uses = bb_reg_last_uses[bb];
7243 reg_last_sets = bb_reg_last_sets[bb];
7244 reg_last_clobbers = bb_reg_last_clobbers[bb];
7246 pending_read_insns = bb_pending_read_insns[bb];
7247 pending_read_mems = bb_pending_read_mems[bb];
7248 pending_write_insns = bb_pending_write_insns[bb];
7249 pending_write_mems = bb_pending_write_mems[bb];
7250 pending_lists_length = bb_pending_lists_length[bb];
7251 last_function_call = bb_last_function_call[bb];
7252 last_pending_memory_flush = bb_last_pending_memory_flush[bb];
7254 sched_before_next_call = bb_sched_before_next_call[bb];
7257 /* Do the analysis for this block. */
7258 get_block_head_tail (bb, &head, &tail);
7259 sched_analyze (head, tail);
7260 add_branch_dependences (head, tail);
7262 if (current_nr_blocks > 1)
7265 int b_succ, bb_succ;
7267 rtx link_insn, link_mem;
7270 /* These lists should point to the right place, for correct
7272 bb_pending_read_insns[bb] = pending_read_insns;
7273 bb_pending_read_mems[bb] = pending_read_mems;
7274 bb_pending_write_insns[bb] = pending_write_insns;
7275 bb_pending_write_mems[bb] = pending_write_mems;
7277 /* bb's structures are inherited by it's successors. */
7278 first_edge = e = OUT_EDGES (b);
7282 b_succ = TO_BLOCK (e);
7283 bb_succ = BLOCK_TO_BB (b_succ);
7285 /* Only bbs "below" bb, in the same region, are interesting. */
7286 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
7293 for (reg = 0; reg < max_reg; reg++)
7296 /* reg-last-uses lists are inherited by bb_succ. */
7297 for (u = reg_last_uses[reg]; u; u = XEXP (u, 1))
7299 if (find_insn_list (XEXP (u, 0),
7300 (bb_reg_last_uses[bb_succ])[reg]))
7303 (bb_reg_last_uses[bb_succ])[reg]
7304 = alloc_INSN_LIST (XEXP (u, 0),
7305 (bb_reg_last_uses[bb_succ])[reg]);
7308 /* reg-last-defs lists are inherited by bb_succ. */
7309 for (u = reg_last_sets[reg]; u; u = XEXP (u, 1))
7311 if (find_insn_list (XEXP (u, 0),
7312 (bb_reg_last_sets[bb_succ])[reg]))
7315 (bb_reg_last_sets[bb_succ])[reg]
7316 = alloc_INSN_LIST (XEXP (u, 0),
7317 (bb_reg_last_sets[bb_succ])[reg]);
7320 for (u = reg_last_clobbers[reg]; u; u = XEXP (u, 1))
7322 if (find_insn_list (XEXP (u, 0),
7323 (bb_reg_last_clobbers[bb_succ])[reg]))
7326 (bb_reg_last_clobbers[bb_succ])[reg]
7327 = alloc_INSN_LIST (XEXP (u, 0),
7328 (bb_reg_last_clobbers[bb_succ])[reg]);
7332 /* Mem read/write lists are inherited by bb_succ. */
7333 link_insn = pending_read_insns;
7334 link_mem = pending_read_mems;
7337 if (!(find_insn_mem_list (XEXP (link_insn, 0),
7339 bb_pending_read_insns[bb_succ],
7340 bb_pending_read_mems[bb_succ])))
7341 add_insn_mem_dependence (&bb_pending_read_insns[bb_succ],
7342 &bb_pending_read_mems[bb_succ],
7343 XEXP (link_insn, 0), XEXP (link_mem, 0));
7344 link_insn = XEXP (link_insn, 1);
7345 link_mem = XEXP (link_mem, 1);
7348 link_insn = pending_write_insns;
7349 link_mem = pending_write_mems;
7352 if (!(find_insn_mem_list (XEXP (link_insn, 0),
7354 bb_pending_write_insns[bb_succ],
7355 bb_pending_write_mems[bb_succ])))
7356 add_insn_mem_dependence (&bb_pending_write_insns[bb_succ],
7357 &bb_pending_write_mems[bb_succ],
7358 XEXP (link_insn, 0), XEXP (link_mem, 0));
7360 link_insn = XEXP (link_insn, 1);
7361 link_mem = XEXP (link_mem, 1);
7364 /* last_function_call is inherited by bb_succ. */
7365 for (u = last_function_call; u; u = XEXP (u, 1))
7367 if (find_insn_list (XEXP (u, 0),
7368 bb_last_function_call[bb_succ]))
7371 bb_last_function_call[bb_succ]
7372 = alloc_INSN_LIST (XEXP (u, 0),
7373 bb_last_function_call[bb_succ]);
7376 /* last_pending_memory_flush is inherited by bb_succ. */
7377 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
7379 if (find_insn_list (XEXP (u, 0),
7380 bb_last_pending_memory_flush[bb_succ]))
7383 bb_last_pending_memory_flush[bb_succ]
7384 = alloc_INSN_LIST (XEXP (u, 0),
7385 bb_last_pending_memory_flush[bb_succ]);
7388 /* sched_before_next_call is inherited by bb_succ. */
7389 x = LOG_LINKS (sched_before_next_call);
7390 for (; x; x = XEXP (x, 1))
7391 add_dependence (bb_sched_before_next_call[bb_succ],
7392 XEXP (x, 0), REG_DEP_ANTI);
7396 while (e != first_edge);
7399 /* Free up the INSN_LISTs.
7401 Note this loop is executed max_reg * nr_regions times. It's first
7402 implementation accounted for over 90% of the calls to free_INSN_LIST_list.
7403 The list was empty for the vast majority of those calls. On the PA, not
7404 calling free_INSN_LIST_list in those cases improves -O2 compile times by
7406 for (b = 0; b < max_reg; ++b)
7408 if (reg_last_clobbers[b])
7409 free_INSN_LIST_list (®_last_clobbers[b]);
7410 if (reg_last_sets[b])
7411 free_INSN_LIST_list (®_last_sets[b]);
7412 if (reg_last_uses[b])
7413 free_INSN_LIST_list (®_last_uses[b]);
7416 /* Assert that we won't need bb_reg_last_* for this block anymore. */
7417 if (current_nr_blocks > 1)
7419 bb_reg_last_uses[bb] = (rtx *) NULL_RTX;
7420 bb_reg_last_sets[bb] = (rtx *) NULL_RTX;
7421 bb_reg_last_clobbers[bb] = (rtx *) NULL_RTX;
7425 /* Print dependences for debugging, callable from debugger. */
7428 debug_dependencies ()
7432 fprintf (dump, ";; --------------- forward dependences: ------------ \n");
7433 for (bb = 0; bb < current_nr_blocks; bb++)
7441 get_block_head_tail (bb, &head, &tail);
7442 next_tail = NEXT_INSN (tail);
7443 fprintf (dump, "\n;; --- Region Dependences --- b %d bb %d \n",
7444 BB_TO_BLOCK (bb), bb);
7446 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7447 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7448 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7449 "----", "----", "--", "---", "----", "----", "--------", "-----");
7450 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
7455 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7458 fprintf (dump, ";; %6d ", INSN_UID (insn));
7459 if (GET_CODE (insn) == NOTE)
7461 n = NOTE_LINE_NUMBER (insn);
7463 fprintf (dump, "%s\n", GET_NOTE_INSN_NAME (n));
7465 fprintf (dump, "line %d, file %s\n", n,
7466 NOTE_SOURCE_FILE (insn));
7469 fprintf (dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
7473 unit = insn_unit (insn);
7475 || function_units[unit].blockage_range_function == 0) ? 0 :
7476 function_units[unit].blockage_range_function (insn);
7478 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7479 (SCHED_GROUP_P (insn) ? "+" : " "),
7483 INSN_DEP_COUNT (insn),
7484 INSN_PRIORITY (insn),
7485 insn_cost (insn, 0, 0),
7486 (int) MIN_BLOCKAGE_COST (range),
7487 (int) MAX_BLOCKAGE_COST (range));
7488 insn_print_units (insn);
7489 fprintf (dump, "\t: ");
7490 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
7491 fprintf (dump, "%d ", INSN_UID (XEXP (link, 0)));
7492 fprintf (dump, "\n");
7496 fprintf (dump, "\n");
7499 /* Set_priorities: compute priority of each insn in the block. */
7512 get_block_head_tail (bb, &head, &tail);
7513 prev_head = PREV_INSN (head);
7516 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
7520 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
7523 if (GET_CODE (insn) == NOTE)
7526 if (!(SCHED_GROUP_P (insn)))
7528 (void) priority (insn);
7534 /* Make each element of VECTOR point at an rtx-vector,
7535 taking the space for all those rtx-vectors from SPACE.
7536 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7537 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7538 (this is the same as init_regset_vector () in flow.c) */
7541 init_rtx_vector (vector, space, nelts, bytes_per_elt)
7548 register rtx *p = space;
7550 for (i = 0; i < nelts; i++)
7553 p += bytes_per_elt / sizeof (*p);
7557 /* Schedule a region. A region is either an inner loop, a loop-free
7558 subroutine, or a single basic block. Each bb in the region is
7559 scheduled after its flow predecessors. */
7562 schedule_region (rgn)
7566 int rgn_n_insns = 0;
7567 int sched_rgn_n_insns = 0;
7569 /* Set variables for the current region. */
7570 current_nr_blocks = RGN_NR_BLOCKS (rgn);
7571 current_blocks = RGN_BLOCKS (rgn);
7573 reg_pending_sets = ALLOCA_REG_SET ();
7574 reg_pending_clobbers = ALLOCA_REG_SET ();
7575 reg_pending_sets_all = 0;
7577 /* Initializations for region data dependence analyisis. */
7578 if (current_nr_blocks > 1)
7581 int maxreg = max_reg_num ();
7583 bb_reg_last_uses = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7584 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7585 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7586 init_rtx_vector (bb_reg_last_uses, space, current_nr_blocks,
7587 maxreg * sizeof (rtx *));
7589 bb_reg_last_sets = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7590 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7591 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7592 init_rtx_vector (bb_reg_last_sets, space, current_nr_blocks,
7593 maxreg * sizeof (rtx *));
7595 bb_reg_last_clobbers =
7596 (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7597 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7598 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7599 init_rtx_vector (bb_reg_last_clobbers, space, current_nr_blocks,
7600 maxreg * sizeof (rtx *));
7602 bb_pending_read_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7603 bb_pending_read_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7604 bb_pending_write_insns =
7605 (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7606 bb_pending_write_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7607 bb_pending_lists_length =
7608 (int *) alloca (current_nr_blocks * sizeof (int));
7609 bb_last_pending_memory_flush =
7610 (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7611 bb_last_function_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7612 bb_sched_before_next_call =
7613 (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7615 init_rgn_data_dependences (current_nr_blocks);
7618 /* Compute LOG_LINKS. */
7619 for (bb = 0; bb < current_nr_blocks; bb++)
7620 compute_block_backward_dependences (bb);
7622 /* Compute INSN_DEPEND. */
7623 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7624 compute_block_forward_dependences (bb);
7626 /* Delete line notes, compute live-regs at block end, and set priorities. */
7628 for (bb = 0; bb < current_nr_blocks; bb++)
7630 if (reload_completed == 0)
7631 find_pre_sched_live (bb);
7633 if (write_symbols != NO_DEBUG)
7635 save_line_notes (bb);
7639 rgn_n_insns += set_priorities (bb);
7642 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
7643 if (current_nr_blocks > 1)
7647 prob = (float *) alloca ((current_nr_blocks) * sizeof (float));
7649 bbset_size = current_nr_blocks / HOST_BITS_PER_WIDE_INT + 1;
7650 dom = (bbset *) alloca (current_nr_blocks * sizeof (bbset));
7651 for (i = 0; i < current_nr_blocks; i++)
7653 dom[i] = (bbset) alloca (bbset_size * sizeof (HOST_WIDE_INT));
7654 bzero ((char *) dom[i], bbset_size * sizeof (HOST_WIDE_INT));
7659 edge_to_bit = (int *) alloca (nr_edges * sizeof (int));
7660 for (i = 1; i < nr_edges; i++)
7661 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
7662 EDGE_TO_BIT (i) = rgn_nr_edges++;
7663 rgn_edges = (int *) alloca (rgn_nr_edges * sizeof (int));
7666 for (i = 1; i < nr_edges; i++)
7667 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
7668 rgn_edges[rgn_nr_edges++] = i;
7671 edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
7672 pot_split = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7673 ancestor_edges = (edgeset *) alloca (current_nr_blocks
7674 * sizeof (edgeset));
7675 for (i = 0; i < current_nr_blocks; i++)
7678 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7679 bzero ((char *) pot_split[i],
7680 edgeset_size * sizeof (HOST_WIDE_INT));
7682 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7683 bzero ((char *) ancestor_edges[i],
7684 edgeset_size * sizeof (HOST_WIDE_INT));
7687 /* Compute probabilities, dominators, split_edges. */
7688 for (bb = 0; bb < current_nr_blocks; bb++)
7689 compute_dom_prob_ps (bb);
7692 /* Now we can schedule all blocks. */
7693 for (bb = 0; bb < current_nr_blocks; bb++)
7695 sched_rgn_n_insns += schedule_block (bb, rgn_n_insns);
7702 /* Sanity check: verify that all region insns were scheduled. */
7703 if (sched_rgn_n_insns != rgn_n_insns)
7706 /* Update register life and usage information. */
7707 if (reload_completed == 0)
7709 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7710 find_post_sched_live (bb);
7712 if (current_nr_blocks <= 1)
7713 /* Sanity check. There should be no REG_DEAD notes leftover
7714 at the end. In practice, this can occur as the result of
7715 bugs in flow, combine.c, and/or sched.c. The values of the
7716 REG_DEAD notes remaining are meaningless, because
7717 dead_notes is just used as a free list. */
7718 if (dead_notes != 0)
7722 /* Restore line notes. */
7723 if (write_symbols != NO_DEBUG)
7725 for (bb = 0; bb < current_nr_blocks; bb++)
7726 restore_line_notes (bb);
7729 /* Done with this region. */
7730 free_pending_lists ();
7732 FREE_REG_SET (reg_pending_sets);
7733 FREE_REG_SET (reg_pending_clobbers);
7736 /* The one entry point in this file. DUMP_FILE is the dump file for
7740 schedule_insns (dump_file)
7751 /* Disable speculative loads in their presence if cc0 defined. */
7753 flag_schedule_speculative_load = 0;
7756 /* Taking care of this degenerate case makes the rest of
7757 this code simpler. */
7758 if (n_basic_blocks == 0)
7761 /* Set dump and sched_verbose for the desired debugging output. If no
7762 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
7763 For -fsched-verbose-N, N>=10, print everything to stderr. */
7764 sched_verbose = sched_verbose_param;
7765 if (sched_verbose_param == 0 && dump_file)
7767 dump = ((sched_verbose_param >= 10 || !dump_file) ? stderr : dump_file);
7772 /* Initialize issue_rate. */
7773 issue_rate = ISSUE_RATE;
7775 /* Do the splitting first for all blocks. */
7776 for (b = 0; b < n_basic_blocks; b++)
7777 split_block_insns (b, 1);
7779 max_uid = (get_max_uid () + 1);
7781 cant_move = xcalloc (max_uid, sizeof (char));
7782 fed_by_spec_load = xcalloc (max_uid, sizeof (char));
7783 is_load_insn = xcalloc (max_uid, sizeof (char));
7785 insn_orig_block = (int *) xmalloc (max_uid * sizeof (int));
7786 insn_luid = (int *) xmalloc (max_uid * sizeof (int));
7789 for (b = 0; b < n_basic_blocks; b++)
7790 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
7792 INSN_BLOCK (insn) = b;
7793 INSN_LUID (insn) = luid++;
7795 if (insn == BLOCK_END (b))
7799 /* After reload, remove inter-blocks dependences computed before reload. */
7800 if (reload_completed)
7805 for (b = 0; b < n_basic_blocks; b++)
7806 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
7810 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
7813 link = LOG_LINKS (insn);
7816 rtx x = XEXP (link, 0);
7818 if (INSN_BLOCK (x) != b)
7820 remove_dependence (insn, x);
7821 link = prev ? XEXP (prev, 1) : LOG_LINKS (insn);
7824 prev = link, link = XEXP (prev, 1);
7828 if (insn == BLOCK_END (b))
7834 rgn_table = (region *) alloca ((n_basic_blocks) * sizeof (region));
7835 rgn_bb_table = (int *) alloca ((n_basic_blocks) * sizeof (int));
7836 block_to_bb = (int *) alloca ((n_basic_blocks) * sizeof (int));
7837 containing_rgn = (int *) alloca ((n_basic_blocks) * sizeof (int));
7839 /* Compute regions for scheduling. */
7840 if (reload_completed
7841 || n_basic_blocks == 1
7842 || !flag_schedule_interblock)
7844 find_single_block_region ();
7848 /* Verify that a 'good' control flow graph can be built. */
7849 if (is_cfg_nonregular ())
7851 find_single_block_region ();
7855 int_list_ptr *s_preds, *s_succs;
7856 int *num_preds, *num_succs;
7857 sbitmap *dom, *pdom;
7859 s_preds = (int_list_ptr *) alloca (n_basic_blocks
7860 * sizeof (int_list_ptr));
7861 s_succs = (int_list_ptr *) alloca (n_basic_blocks
7862 * sizeof (int_list_ptr));
7863 num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
7864 num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
7865 dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
7866 pdom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
7868 /* The scheduler runs after flow; therefore, we can't blindly call
7869 back into find_basic_blocks since doing so could invalidate the
7870 info in global_live_at_start.
7872 Consider a block consisting entirely of dead stores; after life
7873 analysis it would be a block of NOTE_INSN_DELETED notes. If
7874 we call find_basic_blocks again, then the block would be removed
7875 entirely and invalidate our the register live information.
7877 We could (should?) recompute register live information. Doing
7878 so may even be beneficial. */
7880 compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
7882 /* Compute the dominators and post dominators. We don't
7883 currently use post dominators, but we should for
7884 speculative motion analysis. */
7885 compute_dominators (dom, pdom, s_preds, s_succs);
7887 /* build_control_flow will return nonzero if it detects unreachable
7888 blocks or any other irregularity with the cfg which prevents
7889 cross block scheduling. */
7890 if (build_control_flow (s_preds, s_succs, num_preds, num_succs) != 0)
7891 find_single_block_region ();
7893 find_rgns (s_preds, s_succs, num_preds, num_succs, dom);
7895 if (sched_verbose >= 3)
7898 /* For now. This will move as more and more of haifa is converted
7899 to using the cfg code in flow.c. */
7906 /* Allocate data for this pass. See comments, above,
7907 for what these vectors do.
7909 We use xmalloc instead of alloca, because max_uid can be very large
7910 when there is a lot of function inlining. If we used alloca, we could
7911 exceed stack limits on some hosts for some inputs. */
7912 insn_priority = (int *) xcalloc (max_uid, sizeof (int));
7913 insn_reg_weight = (int *) xcalloc (max_uid, sizeof (int));
7914 insn_tick = (int *) xcalloc (max_uid, sizeof (int));
7915 insn_costs = (short *) xcalloc (max_uid, sizeof (short));
7916 insn_units = (short *) xcalloc (max_uid, sizeof (short));
7917 insn_blockage = (unsigned int *) xcalloc (max_uid, sizeof (unsigned int));
7918 insn_ref_count = (int *) xcalloc (max_uid, sizeof (int));
7920 /* Allocate for forward dependencies. */
7921 insn_dep_count = (int *) xcalloc (max_uid, sizeof (int));
7922 insn_depend = (rtx *) xcalloc (max_uid, sizeof (rtx));
7924 if (reload_completed == 0)
7928 sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
7929 sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
7930 sched_reg_basic_block = (int *) alloca (max_regno * sizeof (int));
7931 bb_live_regs = ALLOCA_REG_SET ();
7932 bzero ((char *) sched_reg_n_calls_crossed, max_regno * sizeof (int));
7933 bzero ((char *) sched_reg_live_length, max_regno * sizeof (int));
7935 for (i = 0; i < max_regno; i++)
7936 sched_reg_basic_block[i] = REG_BLOCK_UNKNOWN;
7940 sched_reg_n_calls_crossed = 0;
7941 sched_reg_live_length = 0;
7944 init_alias_analysis ();
7946 if (write_symbols != NO_DEBUG)
7950 line_note = (rtx *) xcalloc (max_uid, sizeof (rtx));
7951 line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
7952 bzero ((char *) line_note_head, n_basic_blocks * sizeof (rtx));
7954 /* Save-line-note-head:
7955 Determine the line-number at the start of each basic block.
7956 This must be computed and saved now, because after a basic block's
7957 predecessor has been scheduled, it is impossible to accurately
7958 determine the correct line number for the first insn of the block. */
7960 for (b = 0; b < n_basic_blocks; b++)
7961 for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line))
7962 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
7964 line_note_head[b] = line;
7969 /* Find units used in this fuction, for visualization. */
7971 init_target_units ();
7973 /* ??? Add a NOTE after the last insn of the last basic block. It is not
7974 known why this is done. */
7976 insn = BLOCK_END (n_basic_blocks - 1);
7977 if (NEXT_INSN (insn) == 0
7978 || (GET_CODE (insn) != NOTE
7979 && GET_CODE (insn) != CODE_LABEL
7980 /* Don't emit a NOTE if it would end up between an unconditional
7981 jump and a BARRIER. */
7982 && !(GET_CODE (insn) == JUMP_INSN
7983 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
7984 emit_note_after (NOTE_INSN_DELETED, BLOCK_END (n_basic_blocks - 1));
7986 /* Schedule every region in the subroutine. */
7987 for (rgn = 0; rgn < nr_regions; rgn++)
7989 schedule_region (rgn);
7996 /* Reposition the prologue and epilogue notes in case we moved the
7997 prologue/epilogue insns. */
7998 if (reload_completed)
7999 reposition_prologue_and_epilogue_notes (get_insns ());
8001 /* Delete redundant line notes. */
8002 if (write_symbols != NO_DEBUG)
8003 rm_redundant_line_notes ();
8005 /* Update information about uses of registers in the subroutine. */
8006 if (reload_completed == 0)
8007 update_reg_usage ();
8011 if (reload_completed == 0 && flag_schedule_interblock)
8013 fprintf (dump, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8021 fprintf (dump, "\n\n");
8025 free (fed_by_spec_load);
8026 free (is_load_insn);
8027 free (insn_orig_block);
8030 free (insn_priority);
8031 free (insn_reg_weight);
8035 free (insn_blockage);
8036 free (insn_ref_count);
8038 free (insn_dep_count);
8041 if (write_symbols != NO_DEBUG)
8045 FREE_REG_SET (bb_live_regs);
8064 #endif /* INSN_SCHEDULING */