1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 93-97, 1998 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 insn with lowest UID.
92 Memory references complicate matters. Only if we can be certain
93 that memory references are not part of the data dependency graph
94 (via true, anti, or output dependence), can we move operations past
95 memory references. To first approximation, reads can be done
96 independently, while writes introduce dependencies. Better
97 approximations will yield fewer dependencies.
99 Before reload, an extended analysis of interblock data dependences
100 is required for interblock scheduling. This is performed in
101 compute_block_backward_dependences ().
103 Dependencies set up by memory references are treated in exactly the
104 same way as other dependencies, by using LOG_LINKS backward
105 dependences. LOG_LINKS are translated into INSN_DEPEND forward
106 dependences for the purpose of forward list scheduling.
108 Having optimized the critical path, we may have also unduly
109 extended the lifetimes of some registers. If an operation requires
110 that constants be loaded into registers, it is certainly desirable
111 to load those constants as early as necessary, but no earlier.
112 I.e., it will not do to load up a bunch of registers at the
113 beginning of a basic block only to use them at the end, if they
114 could be loaded later, since this may result in excessive register
117 Note that since branches are never in basic blocks, but only end
118 basic blocks, this pass will not move branches. But that is ok,
119 since we can use GNU's delayed branch scheduling pass to take care
122 Also note that no further optimizations based on algebraic
123 identities are performed, so this pass would be a good one to
124 perform instruction splitting, such as breaking up a multiply
125 instruction into shifts and adds where that is profitable.
127 Given the memory aliasing analysis that this pass should perform,
128 it should be possible to remove redundant stores to memory, and to
129 load values from registers instead of hitting memory.
131 Before reload, speculative insns are moved only if a 'proof' exists
132 that no exception will be caused by this, and if no live registers
133 exist that inhibit the motion (live registers constraints are not
134 represented by data dependence edges).
136 This pass must update information that subsequent passes expect to
137 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
138 reg_n_calls_crossed, and reg_live_length. Also, basic_block_head,
141 The information in the line number notes is carefully retained by
142 this pass. Notes that refer to the starting and ending of
143 exception regions are also carefully retained by this pass. All
144 other NOTE insns are grouped in their same relative order at the
145 beginning of basic blocks and regions that have been scheduled.
147 The main entry point for this pass is schedule_insns(), called for
148 each function. The work of the scheduler is organized in three
149 levels: (1) function level: insns are subject to splitting,
150 control-flow-graph is constructed, regions are computed (after
151 reload, each region is of one block), (2) region level: control
152 flow graph attributes required for interblock scheduling are
153 computed (dominators, reachability, etc.), data dependences and
154 priorities are computed, and (3) block level: insns in the block
155 are actually scheduled. */
160 #include "basic-block.h"
162 #include "hard-reg-set.h"
164 #include "insn-config.h"
165 #include "insn-attr.h"
168 extern char *reg_known_equiv_p;
169 extern rtx *reg_known_value;
171 #ifdef INSN_SCHEDULING
173 /* target_units bitmask has 1 for each unit in the cpu. It should be
174 possible to compute this variable from the machine description.
175 But currently it is computed by examinning the insn list. Since
176 this is only needed for visualization, it seems an acceptable
177 solution. (For understanding the mapping of bits to units, see
178 definition of function_units[] in "insn-attrtab.c") */
180 static int target_units = 0;
182 /* issue_rate is the number of insns that can be scheduled in the same
183 machine cycle. It can be defined in the config/mach/mach.h file,
184 otherwise we set it to 1. */
186 static int issue_rate;
192 /* sched-verbose controls the amount of debugging output the
193 scheduler prints. It is controlled by -fsched-verbose-N:
194 N>0 and no -DSR : the output is directed to stderr.
195 N>=10 will direct the printouts to stderr (regardless of -dSR).
197 N=2: bb's probabilities, detailed ready list info, unit/insn info.
198 N=3: rtl at abort point, control-flow, regions info.
199 N=5: dependences info. */
201 #define MAX_RGN_BLOCKS 10
202 #define MAX_RGN_INSNS 100
204 static int sched_verbose_param = 0;
205 static int sched_verbose = 0;
207 /* nr_inter/spec counts interblock/speculative motion for the function */
208 static int nr_inter, nr_spec;
211 /* debugging file. all printouts are sent to dump, which is always set,
212 either to stderr, or to the dump listing file (-dRS). */
213 static FILE *dump = 0;
215 /* fix_sched_param() is called from toplev.c upon detection
216 of the -fsched-***-N options. */
219 fix_sched_param (param, val)
222 if (!strcmp (param, "verbose"))
223 sched_verbose_param = atoi (val);
225 warning ("fix_sched_param: unknown param: %s", param);
229 /* Arrays set up by scheduling for the same respective purposes as
230 similar-named arrays set up by flow analysis. We work with these
231 arrays during the scheduling pass so we can compare values against
234 Values of these arrays are copied at the end of this pass into the
235 arrays set up by flow analysis. */
236 static int *sched_reg_n_calls_crossed;
237 static int *sched_reg_live_length;
238 static int *sched_reg_basic_block;
240 /* We need to know the current block number during the post scheduling
241 update of live register information so that we can also update
242 REG_BASIC_BLOCK if a register changes blocks. */
243 static int current_block_num;
245 /* Element N is the next insn that sets (hard or pseudo) register
246 N within the current basic block; or zero, if there is no
247 such insn. Needed for new registers which may be introduced
248 by splitting insns. */
249 static rtx *reg_last_uses;
250 static rtx *reg_last_sets;
251 static regset reg_pending_sets;
252 static int reg_pending_sets_all;
254 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
255 static int *insn_luid;
256 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
258 /* Vector indexed by INSN_UID giving each instruction a priority. */
259 static int *insn_priority;
260 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
262 static short *insn_costs;
263 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
265 /* Vector indexed by INSN_UID giving an encoding of the function units
267 static short *insn_units;
268 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
270 /* Vector indexed by INSN_UID giving each instruction a register-weight.
271 This weight is an estimation of the insn contribution to registers pressure. */
272 static int *insn_reg_weight;
273 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
275 /* Vector indexed by INSN_UID giving list of insns which
276 depend upon INSN. Unlike LOG_LINKS, it represents forward dependences. */
277 static rtx *insn_depend;
278 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
280 /* Vector indexed by INSN_UID. Initialized to the number of incoming
281 edges in forward dependence graph (= number of LOG_LINKS). As
282 scheduling procedes, dependence counts are decreased. An
283 instruction moves to the ready list when its counter is zero. */
284 static int *insn_dep_count;
285 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
287 /* Vector indexed by INSN_UID giving an encoding of the blockage range
288 function. The unit and the range are encoded. */
289 static unsigned int *insn_blockage;
290 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
292 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
293 #define ENCODE_BLOCKAGE(U, R) \
294 ((((U) << UNIT_BITS) << BLOCKAGE_BITS \
295 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
296 | MAX_BLOCKAGE_COST (R))
297 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
298 #define BLOCKAGE_RANGE(B) \
299 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
300 | ((B) & BLOCKAGE_MASK))
302 /* Encodings of the `<name>_unit_blockage_range' function. */
303 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
304 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
306 #define DONE_PRIORITY -1
307 #define MAX_PRIORITY 0x7fffffff
308 #define TAIL_PRIORITY 0x7ffffffe
309 #define LAUNCH_PRIORITY 0x7f000001
310 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
311 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
313 /* Vector indexed by INSN_UID giving number of insns referring to this insn. */
314 static int *insn_ref_count;
315 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
317 /* Vector indexed by INSN_UID giving line-number note in effect for each
318 insn. For line-number notes, this indicates whether the note may be
320 static rtx *line_note;
321 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
323 /* Vector indexed by basic block number giving the starting line-number
324 for each basic block. */
325 static rtx *line_note_head;
327 /* List of important notes we must keep around. This is a pointer to the
328 last element in the list. */
329 static rtx note_list;
331 /* Regsets telling whether a given register is live or dead before the last
332 scheduled insn. Must scan the instructions once before scheduling to
333 determine what registers are live or dead at the end of the block. */
334 static regset bb_live_regs;
336 /* Regset telling whether a given register is live after the insn currently
337 being scheduled. Before processing an insn, this is equal to bb_live_regs
338 above. This is used so that we can find registers that are newly born/dead
339 after processing an insn. */
340 static regset old_live_regs;
342 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
343 during the initial scan and reused later. If there are not exactly as
344 many REG_DEAD notes in the post scheduled code as there were in the
345 prescheduled code then we trigger an abort because this indicates a bug. */
346 static rtx dead_notes;
350 /* An instruction is ready to be scheduled when all insns preceding it
351 have already been scheduled. It is important to ensure that all
352 insns which use its result will not be executed until its result
353 has been computed. An insn is maintained in one of four structures:
355 (P) the "Pending" set of insns which cannot be scheduled until
356 their dependencies have been satisfied.
357 (Q) the "Queued" set of insns that can be scheduled when sufficient
359 (R) the "Ready" list of unscheduled, uncommitted insns.
360 (S) the "Scheduled" list of insns.
362 Initially, all insns are either "Pending" or "Ready" depending on
363 whether their dependencies are satisfied.
365 Insns move from the "Ready" list to the "Scheduled" list as they
366 are committed to the schedule. As this occurs, the insns in the
367 "Pending" list have their dependencies satisfied and move to either
368 the "Ready" list or the "Queued" set depending on whether
369 sufficient time has passed to make them ready. As time passes,
370 insns move from the "Queued" set to the "Ready" list. Insns may
371 move from the "Ready" list to the "Queued" set if they are blocked
372 due to a function unit conflict.
374 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
375 insns, i.e., those that are ready, queued, and pending.
376 The "Queued" set (Q) is implemented by the variable `insn_queue'.
377 The "Ready" list (R) is implemented by the variables `ready' and
379 The "Scheduled" list (S) is the new insn chain built by this pass.
381 The transition (R->S) is implemented in the scheduling loop in
382 `schedule_block' when the best insn to schedule is chosen.
383 The transition (R->Q) is implemented in `queue_insn' when an
384 insn is found to to have a function unit conflict with the already
386 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
387 insns move from the ready list to the scheduled list.
388 The transition (Q->R) is implemented in 'queue_to_insn' as time
389 passes or stalls are introduced. */
391 /* Implement a circular buffer to delay instructions until sufficient
392 time has passed. INSN_QUEUE_SIZE is a power of two larger than
393 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
394 longest time an isnsn may be queued. */
395 static rtx insn_queue[INSN_QUEUE_SIZE];
396 static int q_ptr = 0;
397 static int q_size = 0;
398 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
399 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
401 /* Vector indexed by INSN_UID giving the minimum clock tick at which
402 the insn becomes ready. This is used to note timing constraints for
403 insns in the pending list. */
404 static int *insn_tick;
405 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
407 /* Data structure for keeping track of register information
408 during that register's life. */
417 /* Forward declarations. */
418 static void add_dependence PROTO ((rtx, rtx, enum reg_note));
419 static void remove_dependence PROTO ((rtx, rtx));
420 static rtx find_insn_list PROTO ((rtx, rtx));
421 static int insn_unit PROTO ((rtx));
422 static unsigned int blockage_range PROTO ((int, rtx));
423 static void clear_units PROTO ((void));
424 static int actual_hazard_this_instance PROTO ((int, int, rtx, int, int));
425 static void schedule_unit PROTO ((int, rtx, int));
426 static int actual_hazard PROTO ((int, rtx, int, int));
427 static int potential_hazard PROTO ((int, rtx, int));
428 static int insn_cost PROTO ((rtx, rtx, rtx));
429 static int priority PROTO ((rtx));
430 static void free_pending_lists PROTO ((void));
431 static void add_insn_mem_dependence PROTO ((rtx *, rtx *, rtx, rtx));
432 static void flush_pending_lists PROTO ((rtx, int));
433 static void sched_analyze_1 PROTO ((rtx, rtx));
434 static void sched_analyze_2 PROTO ((rtx, rtx));
435 static void sched_analyze_insn PROTO ((rtx, rtx, rtx));
436 static void sched_analyze PROTO ((rtx, rtx));
437 static void sched_note_set PROTO ((rtx, int));
438 static int rank_for_schedule PROTO ((const GENERIC_PTR, const GENERIC_PTR));
439 static void swap_sort PROTO ((rtx *, int));
440 static void queue_insn PROTO ((rtx, int));
441 static int schedule_insn PROTO ((rtx, rtx *, int, int));
442 static void create_reg_dead_note PROTO ((rtx, rtx));
443 static void attach_deaths PROTO ((rtx, rtx, int));
444 static void attach_deaths_insn PROTO ((rtx));
445 static int new_sometimes_live PROTO ((struct sometimes *, int, int));
446 static void finish_sometimes_live PROTO ((struct sometimes *, int));
447 static int schedule_block PROTO ((int, int));
448 static rtx regno_use_in PROTO ((int, rtx));
449 static void split_hard_reg_notes PROTO ((rtx, rtx, rtx));
450 static void new_insn_dead_notes PROTO ((rtx, rtx, rtx, rtx));
451 static void update_n_sets PROTO ((rtx, int));
452 static void update_flow_info PROTO ((rtx, rtx, rtx, rtx));
453 static char *safe_concat PROTO ((char *, char *, char *));
455 /* Main entry point of this file. */
456 void schedule_insns PROTO ((FILE *));
458 /* Mapping of insns to their original block prior to scheduling. */
459 static int *insn_orig_block;
460 #define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
462 /* Some insns (e.g. call) are not allowed to move across blocks. */
463 static char *cant_move;
464 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
466 /* Control flow graph edges are kept in circular lists. */
475 static edge *edge_table;
477 #define NEXT_IN(edge) (edge_table[edge].next_in)
478 #define NEXT_OUT(edge) (edge_table[edge].next_out)
479 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
480 #define TO_BLOCK(edge) (edge_table[edge].to_block)
482 /* Number of edges in the control flow graph. (in fact larger than
483 that by 1, since edge 0 is unused.) */
486 /* Circular list of incoming/outgoing edges of a block */
487 static int *in_edges;
488 static int *out_edges;
490 #define IN_EDGES(block) (in_edges[block])
491 #define OUT_EDGES(block) (out_edges[block])
493 /* List of labels which cannot be deleted, needed for control
494 flow graph construction. */
495 extern rtx forced_labels;
498 static int is_cfg_nonregular PROTO ((void));
499 static int build_control_flow PROTO ((int_list_ptr *, int_list_ptr *,
501 static void new_edge PROTO ((int, int));
504 /* A region is the main entity for interblock scheduling: insns
505 are allowed to move between blocks in the same region, along
506 control flow graph edges, in the 'up' direction. */
509 int rgn_nr_blocks; /* number of blocks in region */
510 int rgn_blocks; /* blocks in the region (actually index in rgn_bb_table) */
514 /* Number of regions in the procedure */
515 static int nr_regions;
517 /* Table of region descriptions */
518 static region *rgn_table;
520 /* Array of lists of regions' blocks */
521 static int *rgn_bb_table;
523 /* Topological order of blocks in the region (if b2 is reachable from
524 b1, block_to_bb[b2] > block_to_bb[b1]).
525 Note: A basic block is always referred to by either block or b,
526 while its topological order name (in the region) is refered to by
529 static int *block_to_bb;
531 /* The number of the region containing a block. */
532 static int *containing_rgn;
534 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
535 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
536 #define BLOCK_TO_BB(block) (block_to_bb[block])
537 #define CONTAINING_RGN(block) (containing_rgn[block])
539 void debug_regions PROTO ((void));
540 static void find_single_block_region PROTO ((void));
541 static void find_rgns PROTO ((int_list_ptr *, int_list_ptr *,
542 int *, int *, sbitmap *));
543 static int too_large PROTO ((int, int *, int *));
545 extern void debug_live PROTO ((int, int));
547 /* Blocks of the current region being scheduled. */
548 static int current_nr_blocks;
549 static int current_blocks;
551 /* The mapping from bb to block */
552 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
555 /* Bit vectors and bitset operations are needed for computations on
556 the control flow graph. */
558 typedef unsigned HOST_WIDE_INT *bitset;
561 int *first_member; /* pointer to the list start in bitlst_table. */
562 int nr_members; /* the number of members of the bit list. */
566 static int bitlst_table_last;
567 static int bitlst_table_size;
568 static int *bitlst_table;
570 static char bitset_member PROTO ((bitset, int, int));
571 static void extract_bitlst PROTO ((bitset, int, bitlst *));
573 /* target info declarations.
575 The block currently being scheduled is referred to as the "target" block,
576 while other blocks in the region from which insns can be moved to the
577 target are called "source" blocks. The candidate structure holds info
578 about such sources: are they valid? Speculative? Etc. */
579 typedef bitlst bblst;
590 static candidate *candidate_table;
592 /* A speculative motion requires checking live information on the path
593 from 'source' to 'target'. The split blocks are those to be checked.
594 After a speculative motion, live information should be modified in
597 Lists of split and update blocks for each candidate of the current
598 target are in array bblst_table */
599 static int *bblst_table, bblst_size, bblst_last;
601 #define IS_VALID(src) ( candidate_table[src].is_valid )
602 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
603 #define SRC_PROB(src) ( candidate_table[src].src_prob )
605 /* The bb being currently scheduled. */
606 static int target_bb;
609 typedef bitlst edgelst;
611 /* target info functions */
612 static void split_edges PROTO ((int, int, edgelst *));
613 static void compute_trg_info PROTO ((int));
614 void debug_candidate PROTO ((int));
615 void debug_candidates PROTO ((int));
618 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
619 typedef bitset bbset;
621 /* Number of words of the bbset. */
622 static int bbset_size;
624 /* Dominators array: dom[i] contains the bbset of dominators of
625 bb i in the region. */
628 /* bb 0 is the only region entry */
629 #define IS_RGN_ENTRY(bb) (!bb)
631 /* Is bb_src dominated by bb_trg. */
632 #define IS_DOMINATED(bb_src, bb_trg) \
633 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
635 /* Probability: Prob[i] is a float in [0, 1] which is the probability
636 of bb i relative to the region entry. */
639 /* The probability of bb_src, relative to bb_trg. Note, that while the
640 'prob[bb]' is a float in [0, 1], this macro returns an integer
642 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
645 /* Bit-set of edges, where bit i stands for edge i. */
646 typedef bitset edgeset;
648 /* Number of edges in the region. */
649 static int rgn_nr_edges;
651 /* Array of size rgn_nr_edges. */
652 static int *rgn_edges;
654 /* Number of words in an edgeset. */
655 static int edgeset_size;
657 /* Mapping from each edge in the graph to its number in the rgn. */
658 static int *edge_to_bit;
659 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
661 /* The split edges of a source bb is different for each target
662 bb. In order to compute this efficiently, the 'potential-split edges'
663 are computed for each bb prior to scheduling a region. This is actually
664 the split edges of each bb relative to the region entry.
666 pot_split[bb] is the set of potential split edges of bb. */
667 static edgeset *pot_split;
669 /* For every bb, a set of its ancestor edges. */
670 static edgeset *ancestor_edges;
672 static void compute_dom_prob_ps PROTO ((int));
674 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
675 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
676 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
677 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
679 /* parameters affecting the decision of rank_for_schedule() */
680 #define MIN_DIFF_PRIORITY 2
681 #define MIN_PROBABILITY 40
682 #define MIN_PROB_DIFF 10
684 /* speculative scheduling functions */
685 static int check_live_1 PROTO ((int, rtx));
686 static void update_live_1 PROTO ((int, rtx));
687 static int check_live PROTO ((rtx, int));
688 static void update_live PROTO ((rtx, int));
689 static void set_spec_fed PROTO ((rtx));
690 static int is_pfree PROTO ((rtx, int, int));
691 static int find_conditional_protection PROTO ((rtx, int));
692 static int is_conditionally_protected PROTO ((rtx, int, int));
693 static int may_trap_exp PROTO ((rtx, int));
694 static int haifa_classify_insn PROTO ((rtx));
695 static int is_prisky PROTO ((rtx, int, int));
696 static int is_exception_free PROTO ((rtx, int, int));
698 static char find_insn_mem_list PROTO ((rtx, rtx, rtx, rtx));
699 static void compute_block_forward_dependences PROTO ((int));
700 static void init_rgn_data_dependences PROTO ((int));
701 static void add_branch_dependences PROTO ((rtx, rtx));
702 static void compute_block_backward_dependences PROTO ((int));
703 void debug_dependencies PROTO ((void));
705 /* Notes handling mechanism:
706 =========================
707 Generally, NOTES are saved before scheduling and restored after scheduling.
708 The scheduler distinguishes between three types of notes:
710 (1) LINE_NUMBER notes, generated and used for debugging. Here,
711 before scheduling a region, a pointer to the LINE_NUMBER note is
712 added to the insn following it (in save_line_notes()), and the note
713 is removed (in rm_line_notes() and unlink_line_notes()). After
714 scheduling the region, this pointer is used for regeneration of
715 the LINE_NUMBER note (in restore_line_notes()).
717 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
718 Before scheduling a region, a pointer to the note is added to the insn
719 that follows or precedes it. (This happens as part of the data dependence
720 computation). After scheduling an insn, the pointer contained in it is
721 used for regenerating the corresponding note (in reemit_notes).
723 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
724 these notes are put in a list (in rm_other_notes() and
725 unlink_other_notes ()). After scheduling the block, these notes are
726 inserted at the beginning of the block (in schedule_block()). */
728 static rtx unlink_other_notes PROTO ((rtx, rtx));
729 static rtx unlink_line_notes PROTO ((rtx, rtx));
730 static void rm_line_notes PROTO ((int));
731 static void save_line_notes PROTO ((int));
732 static void restore_line_notes PROTO ((int));
733 static void rm_redundant_line_notes PROTO ((void));
734 static void rm_other_notes PROTO ((rtx, rtx));
735 static rtx reemit_notes PROTO ((rtx, rtx));
737 static void get_block_head_tail PROTO ((int, rtx *, rtx *));
739 static void find_pre_sched_live PROTO ((int));
740 static void find_post_sched_live PROTO ((int));
741 static void update_reg_usage PROTO ((void));
742 static int queue_to_ready PROTO ((rtx [], int));
744 void debug_ready_list PROTO ((rtx[], int));
745 static void init_target_units PROTO (());
746 static void insn_print_units PROTO ((rtx));
747 static int get_visual_tbl_length PROTO (());
748 static void init_block_visualization PROTO (());
749 static void print_block_visualization PROTO ((int, char *));
750 static void visualize_scheduled_insns PROTO ((int, int));
751 static void visualize_no_unit PROTO ((rtx));
752 static void visualize_stall_cycles PROTO ((int, int));
753 static void print_exp PROTO ((char *, rtx, int));
754 static void print_value PROTO ((char *, rtx, int));
755 static void print_pattern PROTO ((char *, rtx, int));
756 static void print_insn PROTO ((char *, rtx, int));
757 void debug_reg_vector PROTO ((regset));
759 static rtx move_insn1 PROTO ((rtx, rtx));
760 static rtx move_insn PROTO ((rtx, rtx));
761 static rtx group_leader PROTO ((rtx));
762 static int set_priorities PROTO ((int));
763 static void init_rtx_vector PROTO ((rtx **, rtx *, int, int));
764 static void schedule_region PROTO ((int));
765 static void split_block_insns PROTO ((int));
767 #endif /* INSN_SCHEDULING */
769 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
771 /* Helper functions for instruction scheduling. */
773 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
774 static rtx unused_insn_list;
776 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
777 static rtx unused_expr_list;
779 static void free_list PROTO ((rtx *, rtx *));
780 static rtx alloc_INSN_LIST PROTO ((rtx, rtx));
781 static rtx alloc_EXPR_LIST PROTO ((int, rtx, rtx));
784 free_list (listp, unused_listp)
785 rtx *listp, *unused_listp;
787 register rtx link, prev_link;
793 link = XEXP (prev_link, 1);
798 link = XEXP (link, 1);
801 XEXP (prev_link, 1) = *unused_listp;
802 *unused_listp = *listp;
807 alloc_INSN_LIST (val, next)
812 if (unused_insn_list)
814 r = unused_insn_list;
815 unused_insn_list = XEXP (r, 1);
818 PUT_REG_NOTE_KIND (r, VOIDmode);
821 r = gen_rtx_INSN_LIST (VOIDmode, val, next);
827 alloc_EXPR_LIST (kind, val, next)
833 if (unused_insn_list)
835 r = unused_insn_list;
836 unused_insn_list = XEXP (r, 1);
839 PUT_REG_NOTE_KIND (r, kind);
842 r = gen_rtx_EXPR_LIST (kind, val, next);
847 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
848 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
849 of dependence that this link represents. */
852 add_dependence (insn, elem, dep_type)
855 enum reg_note dep_type;
859 /* Don't depend an insn on itself. */
863 /* If elem is part of a sequence that must be scheduled together, then
864 make the dependence point to the last insn of the sequence.
865 When HAVE_cc0, it is possible for NOTEs to exist between users and
866 setters of the condition codes, so we must skip past notes here.
867 Otherwise, NOTEs are impossible here. */
869 next = NEXT_INSN (elem);
872 while (next && GET_CODE (next) == NOTE)
873 next = NEXT_INSN (next);
876 if (next && SCHED_GROUP_P (next)
877 && GET_CODE (next) != CODE_LABEL)
879 /* Notes will never intervene here though, so don't bother checking
881 /* We must reject CODE_LABELs, so that we don't get confused by one
882 that has LABEL_PRESERVE_P set, which is represented by the same
883 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
885 while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
886 && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
887 next = NEXT_INSN (next);
889 /* Again, don't depend an insn on itself. */
893 /* Make the dependence to NEXT, the last insn of the group, instead
894 of the original ELEM. */
898 #ifdef INSN_SCHEDULING
899 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
900 No need for interblock dependences with calls, since
901 calls are not moved between blocks. Note: the edge where
902 elem is a CALL is still required. */
903 if (GET_CODE (insn) == CALL_INSN
904 && (INSN_BB (elem) != INSN_BB (insn)))
909 /* Check that we don't already have this dependence. */
910 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
911 if (XEXP (link, 0) == elem)
913 /* If this is a more restrictive type of dependence than the existing
914 one, then change the existing dependence to this type. */
915 if ((int) dep_type < (int) REG_NOTE_KIND (link))
916 PUT_REG_NOTE_KIND (link, dep_type);
919 /* Might want to check one level of transitivity to save conses. */
921 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
922 LOG_LINKS (insn) = link;
924 /* Insn dependency, not data dependency. */
925 PUT_REG_NOTE_KIND (link, dep_type);
928 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
929 of INSN. Abort if not found. */
932 remove_dependence (insn, elem)
936 rtx prev, link, next;
939 for (prev = 0, link = LOG_LINKS (insn); link; link = next)
941 next = XEXP (link, 1);
942 if (XEXP (link, 0) == elem)
945 XEXP (prev, 1) = next;
947 LOG_LINKS (insn) = next;
949 XEXP (link, 1) = unused_insn_list;
950 unused_insn_list = link;
963 #ifndef INSN_SCHEDULING
965 schedule_insns (dump_file)
974 /* Computation of memory dependencies. */
976 /* The *_insns and *_mems are paired lists. Each pending memory operation
977 will have a pointer to the MEM rtx on one list and a pointer to the
978 containing insn on the other list in the same place in the list. */
980 /* We can't use add_dependence like the old code did, because a single insn
981 may have multiple memory accesses, and hence needs to be on the list
982 once for each memory access. Add_dependence won't let you add an insn
983 to a list more than once. */
985 /* An INSN_LIST containing all insns with pending read operations. */
986 static rtx pending_read_insns;
988 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
989 static rtx pending_read_mems;
991 /* An INSN_LIST containing all insns with pending write operations. */
992 static rtx pending_write_insns;
994 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
995 static rtx pending_write_mems;
997 /* Indicates the combined length of the two pending lists. We must prevent
998 these lists from ever growing too large since the number of dependencies
999 produced is at least O(N*N), and execution time is at least O(4*N*N), as
1000 a function of the length of these pending lists. */
1002 static int pending_lists_length;
1004 /* The last insn upon which all memory references must depend.
1005 This is an insn which flushed the pending lists, creating a dependency
1006 between it and all previously pending memory references. This creates
1007 a barrier (or a checkpoint) which no memory reference is allowed to cross.
1009 This includes all non constant CALL_INSNs. When we do interprocedural
1010 alias analysis, this restriction can be relaxed.
1011 This may also be an INSN that writes memory if the pending lists grow
1014 static rtx last_pending_memory_flush;
1016 /* The last function call we have seen. All hard regs, and, of course,
1017 the last function call, must depend on this. */
1019 static rtx last_function_call;
1021 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
1022 that does not already cross a call. We create dependencies between each
1023 of those insn and the next call insn, to ensure that they won't cross a call
1024 after scheduling is done. */
1026 static rtx sched_before_next_call;
1028 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1029 so that insns independent of the last scheduled insn will be preferred
1030 over dependent instructions. */
1032 static rtx last_scheduled_insn;
1034 /* Data structures for the computation of data dependences in a regions. We
1035 keep one copy of each of the declared above variables for each bb in the
1036 region. Before analyzing the data dependences for a bb, its variables
1037 are initialized as a function of the variables of its predecessors. When
1038 the analysis for a bb completes, we save the contents of each variable X
1039 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
1040 copied to bb_pending_read_insns[bb]. Another change is that few
1041 variables are now a list of insns rather than a single insn:
1042 last_pending_memory_flash, last_function_call, reg_last_sets. The
1043 manipulation of these variables was changed appropriately. */
1045 static rtx **bb_reg_last_uses;
1046 static rtx **bb_reg_last_sets;
1048 static rtx *bb_pending_read_insns;
1049 static rtx *bb_pending_read_mems;
1050 static rtx *bb_pending_write_insns;
1051 static rtx *bb_pending_write_mems;
1052 static int *bb_pending_lists_length;
1054 static rtx *bb_last_pending_memory_flush;
1055 static rtx *bb_last_function_call;
1056 static rtx *bb_sched_before_next_call;
1058 /* functions for construction of the control flow graph. */
1060 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1062 We decide not to build the control flow graph if there is possibly more
1063 than one entry to the function, if computed branches exist, of if we
1064 have nonlocal gotos. */
1067 is_cfg_nonregular ()
1073 /* If we have a label that could be the target of a nonlocal goto, then
1074 the cfg is not well structured. */
1075 if (nonlocal_label_rtx_list () != NULL)
1078 /* If we have any forced labels, then the cfg is not well structured. */
1082 /* If this function has a computed jump, then we consider the cfg
1083 not well structured. */
1084 if (current_function_has_computed_jump)
1087 /* If we have exception handlers, then we consider the cfg not well
1088 structured. ?!? We should be able to handle this now that flow.c
1089 computes an accurate cfg for EH. */
1090 if (exception_handler_labels)
1093 /* If we have non-jumping insns which refer to labels, then we consider
1094 the cfg not well structured. */
1095 /* check for labels referred to other thn by jumps */
1096 for (b = 0; b < n_basic_blocks; b++)
1097 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
1099 code = GET_CODE (insn);
1100 if (GET_RTX_CLASS (code) == 'i')
1104 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1105 if (REG_NOTE_KIND (note) == REG_LABEL)
1109 if (insn == basic_block_end[b])
1113 /* All the tests passed. Consider the cfg well structured. */
1117 /* Build the control flow graph and set nr_edges.
1119 Instead of trying to build a cfg ourselves, we rely on flow to
1120 do it for us. Stamp out useless code (and bug) duplication.
1122 Return nonzero if an irregularity in the cfg is found which would
1123 prevent cross block scheduling. */
1126 build_control_flow (s_preds, s_succs, num_preds, num_succs)
1127 int_list_ptr *s_preds;
1128 int_list_ptr *s_succs;
1136 /* Count the number of edges in the cfg. */
1139 for (i = 0; i < n_basic_blocks; i++)
1141 nr_edges += num_succs[i];
1143 /* Unreachable loops with more than one basic block are detected
1144 during the DFS traversal in find_rgns.
1146 Unreachable loops with a single block are detected here. This
1147 test is redundant with the one in find_rgns, but it's much
1148 cheaper to go ahead and catch the trivial case here. */
1149 if (num_preds[i] == 0
1150 || (num_preds[i] == 1 && INT_LIST_VAL (s_preds[i]) == i))
1154 /* Account for entry/exit edges. */
1157 in_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
1158 out_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
1159 bzero ((char *) in_edges, n_basic_blocks * sizeof (int));
1160 bzero ((char *) out_edges, n_basic_blocks * sizeof (int));
1162 edge_table = (edge *) xmalloc ((nr_edges) * sizeof (edge));
1163 bzero ((char *) edge_table, ((nr_edges) * sizeof (edge)));
1166 for (i = 0; i < n_basic_blocks; i++)
1167 for (succ = s_succs[i]; succ; succ = succ->next)
1169 if (INT_LIST_VAL (succ) != EXIT_BLOCK)
1170 new_edge (i, INT_LIST_VAL (succ));
1173 /* increment by 1, since edge 0 is unused. */
1180 /* Record an edge in the control flow graph from SOURCE to TARGET.
1182 In theory, this is redundant with the s_succs computed above, but
1183 we have not converted all of haifa to use information from the
1187 new_edge (source, target)
1191 int curr_edge, fst_edge;
1193 /* check for duplicates */
1194 fst_edge = curr_edge = OUT_EDGES (source);
1197 if (FROM_BLOCK (curr_edge) == source
1198 && TO_BLOCK (curr_edge) == target)
1203 curr_edge = NEXT_OUT (curr_edge);
1205 if (fst_edge == curr_edge)
1211 FROM_BLOCK (e) = source;
1212 TO_BLOCK (e) = target;
1214 if (OUT_EDGES (source))
1216 next_edge = NEXT_OUT (OUT_EDGES (source));
1217 NEXT_OUT (OUT_EDGES (source)) = e;
1218 NEXT_OUT (e) = next_edge;
1222 OUT_EDGES (source) = e;
1226 if (IN_EDGES (target))
1228 next_edge = NEXT_IN (IN_EDGES (target));
1229 NEXT_IN (IN_EDGES (target)) = e;
1230 NEXT_IN (e) = next_edge;
1234 IN_EDGES (target) = e;
1240 /* BITSET macros for operations on the control flow graph. */
1242 /* Compute bitwise union of two bitsets. */
1243 #define BITSET_UNION(set1, set2, len) \
1244 do { register bitset tp = set1, sp = set2; \
1246 for (i = 0; i < len; i++) \
1247 *(tp++) |= *(sp++); } while (0)
1249 /* Compute bitwise intersection of two bitsets. */
1250 #define BITSET_INTER(set1, set2, len) \
1251 do { register bitset tp = set1, sp = set2; \
1253 for (i = 0; i < len; i++) \
1254 *(tp++) &= *(sp++); } while (0)
1256 /* Compute bitwise difference of two bitsets. */
1257 #define BITSET_DIFFER(set1, set2, len) \
1258 do { register bitset tp = set1, sp = set2; \
1260 for (i = 0; i < len; i++) \
1261 *(tp++) &= ~*(sp++); } while (0)
1263 /* Inverts every bit of bitset 'set' */
1264 #define BITSET_INVERT(set, len) \
1265 do { register bitset tmpset = set; \
1267 for (i = 0; i < len; i++, tmpset++) \
1268 *tmpset = ~*tmpset; } while (0)
1270 /* Turn on the index'th bit in bitset set. */
1271 #define BITSET_ADD(set, index, len) \
1273 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1276 set[index/HOST_BITS_PER_WIDE_INT] |= \
1277 1 << (index % HOST_BITS_PER_WIDE_INT); \
1280 /* Turn off the index'th bit in set. */
1281 #define BITSET_REMOVE(set, index, len) \
1283 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1286 set[index/HOST_BITS_PER_WIDE_INT] &= \
1287 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1291 /* Check if the index'th bit in bitset set is on. */
1294 bitset_member (set, index, len)
1298 if (index >= HOST_BITS_PER_WIDE_INT * len)
1300 return (set[index / HOST_BITS_PER_WIDE_INT] &
1301 1 << (index % HOST_BITS_PER_WIDE_INT)) ? 1 : 0;
1305 /* Translate a bit-set SET to a list BL of the bit-set members. */
1308 extract_bitlst (set, len, bl)
1314 unsigned HOST_WIDE_INT word;
1316 /* bblst table space is reused in each call to extract_bitlst */
1317 bitlst_table_last = 0;
1319 bl->first_member = &bitlst_table[bitlst_table_last];
1322 for (i = 0; i < len; i++)
1325 offset = i * HOST_BITS_PER_WIDE_INT;
1326 for (j = 0; word; j++)
1330 bitlst_table[bitlst_table_last++] = offset;
1341 /* functions for the construction of regions */
1343 /* Print the regions, for debugging purposes. Callable from debugger. */
1350 fprintf (dump, "\n;; ------------ REGIONS ----------\n\n");
1351 for (rgn = 0; rgn < nr_regions; rgn++)
1353 fprintf (dump, ";;\trgn %d nr_blocks %d:\n", rgn,
1354 rgn_table[rgn].rgn_nr_blocks);
1355 fprintf (dump, ";;\tbb/block: ");
1357 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
1359 current_blocks = RGN_BLOCKS (rgn);
1361 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
1364 fprintf (dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
1367 fprintf (dump, "\n\n");
1372 /* Build a single block region for each basic block in the function.
1373 This allows for using the same code for interblock and basic block
1377 find_single_block_region ()
1381 for (i = 0; i < n_basic_blocks; i++)
1383 rgn_bb_table[i] = i;
1384 RGN_NR_BLOCKS (i) = 1;
1386 CONTAINING_RGN (i) = i;
1387 BLOCK_TO_BB (i) = 0;
1389 nr_regions = n_basic_blocks;
1393 /* Update number of blocks and the estimate for number of insns
1394 in the region. Return 1 if the region is "too large" for interblock
1395 scheduling (compile time considerations), otherwise return 0. */
1398 too_large (block, num_bbs, num_insns)
1399 int block, *num_bbs, *num_insns;
1402 (*num_insns) += (INSN_LUID (basic_block_end[block]) -
1403 INSN_LUID (basic_block_head[block]));
1404 if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
1411 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1412 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1413 loop containing blk. */
1414 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1416 if (max_hdr[blk] == -1) \
1417 max_hdr[blk] = hdr; \
1418 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1419 RESET_BIT (inner, hdr); \
1420 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1422 RESET_BIT (inner,max_hdr[blk]); \
1423 max_hdr[blk] = hdr; \
1428 /* Find regions for interblock scheduling.
1430 A region for scheduling can be:
1432 * A loop-free procedure, or
1434 * A reducible inner loop, or
1436 * A basic block not contained in any other region.
1439 ?!? In theory we could build other regions based on extended basic
1440 blocks or reverse extended basic blocks. Is it worth the trouble?
1442 Loop blocks that form a region are put into the region's block list
1443 in topological order.
1445 This procedure stores its results into the following global (ick) variables
1454 We use dominator relationships to avoid making regions out of non-reducible
1457 This procedure needs to be converted to work on pred/succ lists instead
1458 of edge tables. That would simplify it somewhat. */
1461 find_rgns (s_preds, s_succs, num_preds, num_succs, dom)
1462 int_list_ptr *s_preds;
1463 int_list_ptr *s_succs;
1468 int *max_hdr, *dfs_nr, *stack, *queue, *degree;
1470 int node, child, loop_head, i, j, head, tail;
1471 int count = 0, sp, idx = 0, current_edge = out_edges[0];
1472 int num_bbs, num_insns, unreachable;
1473 int too_large_failure;
1475 /* Note if an edge has been passed. */
1478 /* Note if a block is a natural loop header. */
1481 /* Note if a block is an natural inner loop header. */
1484 /* Note if a block is in the block queue. */
1487 /* Note if a block is in the block queue. */
1490 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1491 and a mapping from block to its loop header (if the block is contained
1492 in a loop, else -1).
1494 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1495 be used as inputs to the second traversal.
1497 STACK, SP and DFS_NR are only used during the first traversal. */
1499 /* Allocate and initialize variables for the first traversal. */
1500 max_hdr = (int *) alloca (n_basic_blocks * sizeof (int));
1501 dfs_nr = (int *) alloca (n_basic_blocks * sizeof (int));
1502 bzero ((char *) dfs_nr, n_basic_blocks * sizeof (int));
1503 stack = (int *) alloca (nr_edges * sizeof (int));
1505 inner = sbitmap_alloc (n_basic_blocks);
1506 sbitmap_ones (inner);
1508 header = sbitmap_alloc (n_basic_blocks);
1509 sbitmap_zero (header);
1511 passed = sbitmap_alloc (nr_edges);
1512 sbitmap_zero (passed);
1514 in_queue = sbitmap_alloc (n_basic_blocks);
1515 sbitmap_zero (in_queue);
1517 in_stack = sbitmap_alloc (n_basic_blocks);
1518 sbitmap_zero (in_stack);
1520 for (i = 0; i < n_basic_blocks; i++)
1523 /* DFS traversal to find inner loops in the cfg. */
1528 if (current_edge == 0 || TEST_BIT (passed, current_edge))
1530 /* We have reached a leaf node or a node that was already
1531 processed. Pop edges off the stack until we find
1532 an edge that has not yet been processed. */
1534 && (current_edge == 0 || TEST_BIT (passed, current_edge)))
1536 /* Pop entry off the stack. */
1537 current_edge = stack[sp--];
1538 node = FROM_BLOCK (current_edge);
1539 child = TO_BLOCK (current_edge);
1540 RESET_BIT (in_stack, child);
1541 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1542 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1543 current_edge = NEXT_OUT (current_edge);
1546 /* See if have finished the DFS tree traversal. */
1547 if (sp < 0 && TEST_BIT (passed, current_edge))
1550 /* Nope, continue the traversal with the popped node. */
1554 /* Process a node. */
1555 node = FROM_BLOCK (current_edge);
1556 child = TO_BLOCK (current_edge);
1557 SET_BIT (in_stack, node);
1558 dfs_nr[node] = ++count;
1560 /* If the successor is in the stack, then we've found a loop.
1561 Mark the loop, if it is not a natural loop, then it will
1562 be rejected during the second traversal. */
1563 if (TEST_BIT (in_stack, child))
1566 SET_BIT (header, child);
1567 UPDATE_LOOP_RELATIONS (node, child);
1568 SET_BIT (passed, current_edge);
1569 current_edge = NEXT_OUT (current_edge);
1573 /* If the child was already visited, then there is no need to visit
1574 it again. Just update the loop relationships and restart
1578 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1579 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1580 SET_BIT (passed, current_edge);
1581 current_edge = NEXT_OUT (current_edge);
1585 /* Push an entry on the stack and continue DFS traversal. */
1586 stack[++sp] = current_edge;
1587 SET_BIT (passed, current_edge);
1588 current_edge = OUT_EDGES (child);
1591 /* Another check for unreachable blocks. The earlier test in
1592 is_cfg_nonregular only finds unreachable blocks that do not
1595 The DFS traversal will mark every block that is reachable from
1596 the entry node by placing a nonzero value in dfs_nr. Thus if
1597 dfs_nr is zero for any block, then it must be unreachable. */
1599 for (i = 0; i < n_basic_blocks; i++)
1606 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1607 to hold degree counts. */
1610 /* Compute the in-degree of every block in the graph */
1611 for (i = 0; i < n_basic_blocks; i++)
1612 degree[i] = num_preds[i];
1614 /* Do not perform region scheduling if there are any unreachable
1619 SET_BIT (header, 0);
1621 /* Second travsersal:find reducible inner loops and topologically sort
1622 block of each region. */
1624 queue = (int *) alloca (n_basic_blocks * sizeof (int));
1626 /* Find blocks which are inner loop headers. We still have non-reducible
1627 loops to consider at this point. */
1628 for (i = 0; i < n_basic_blocks; i++)
1630 if (TEST_BIT (header, i) && TEST_BIT (inner, i))
1635 /* Now check that the loop is reducible. We do this separate
1636 from finding inner loops so that we do not find a reducible
1637 loop which contains an inner non-reducible loop.
1639 A simple way to find reducible/natrual loops is to verify
1640 that each block in the loop is dominated by the loop
1643 If there exists a block that is not dominated by the loop
1644 header, then the block is reachable from outside the loop
1645 and thus the loop is not a natural loop. */
1646 for (j = 0; j < n_basic_blocks; j++)
1648 /* First identify blocks in the loop, except for the loop
1650 if (i == max_hdr[j] && i != j)
1652 /* Now verify that the block is dominated by the loop
1654 if (!TEST_BIT (dom[j], i))
1659 /* If we exited the loop early, then I is the header of a non
1660 reducible loop and we should quit processing it now. */
1661 if (j != n_basic_blocks)
1664 /* I is a header of an inner loop, or block 0 in a subroutine
1665 with no loops at all. */
1667 too_large_failure = 0;
1668 loop_head = max_hdr[i];
1670 /* Decrease degree of all I's successors for topological
1672 for (ps = s_succs[i]; ps; ps = ps->next)
1673 if (INT_LIST_VAL (ps) != EXIT_BLOCK
1674 && INT_LIST_VAL (ps) != ENTRY_BLOCK)
1675 --degree[INT_LIST_VAL(ps)];
1677 /* Estimate # insns, and count # blocks in the region. */
1679 num_insns = (INSN_LUID (basic_block_end[i])
1680 - INSN_LUID (basic_block_head[i]));
1683 /* Find all loop latches (blocks which back edges to the loop
1684 header) or all the leaf blocks in the cfg has no loops.
1686 Place those blocks into the queue. */
1689 for (j = 0; j < n_basic_blocks; j++)
1690 /* Leaf nodes have only a single successor which must
1692 if (num_succs[j] == 1
1693 && INT_LIST_VAL (s_succs[j]) == EXIT_BLOCK)
1696 SET_BIT (in_queue, j);
1698 if (too_large (j, &num_bbs, &num_insns))
1700 too_large_failure = 1;
1709 for (ps = s_preds[i]; ps; ps = ps->next)
1711 node = INT_LIST_VAL (ps);
1713 if (node == ENTRY_BLOCK || node == EXIT_BLOCK)
1716 if (max_hdr[node] == loop_head && node != i)
1718 /* This is a loop latch. */
1719 queue[++tail] = node;
1720 SET_BIT (in_queue, node);
1722 if (too_large (node, &num_bbs, &num_insns))
1724 too_large_failure = 1;
1732 /* Now add all the blocks in the loop to the queue.
1734 We know the loop is a natural loop; however the algorithm
1735 above will not always mark certain blocks as being in the
1744 The algorithm in the DFS traversal may not mark B & D as part
1745 of the loop (ie they will not have max_hdr set to A).
1747 We know they can not be loop latches (else they would have
1748 had max_hdr set since they'd have a backedge to a dominator
1749 block). So we don't need them on the initial queue.
1751 We know they are part of the loop because they are dominated
1752 by the loop header and can be reached by a backwards walk of
1753 the edges starting with nodes on the initial queue.
1755 It is safe and desirable to include those nodes in the
1756 loop/scheduling region. To do so we would need to decrease
1757 the degree of a node if it is the target of a backedge
1758 within the loop itself as the node is placed in the queue.
1760 We do not do this because I'm not sure that the actual
1761 scheduling code will properly handle this case. ?!? */
1763 while (head < tail && !too_large_failure)
1766 child = queue[++head];
1768 for (ps = s_preds[child]; ps; ps = ps->next)
1770 node = INT_LIST_VAL (ps);
1772 /* See discussion above about nodes not marked as in
1773 this loop during the initial DFS traversal. */
1774 if (node == ENTRY_BLOCK || node == EXIT_BLOCK
1775 || max_hdr[node] != loop_head)
1780 else if (!TEST_BIT (in_queue, node) && node != i)
1782 queue[++tail] = node;
1783 SET_BIT (in_queue, node);
1785 if (too_large (node, &num_bbs, &num_insns))
1787 too_large_failure = 1;
1794 if (tail >= 0 && !too_large_failure)
1796 /* Place the loop header into list of region blocks. */
1798 rgn_bb_table[idx] = i;
1799 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1800 RGN_BLOCKS (nr_regions) = idx++;
1801 CONTAINING_RGN (i) = nr_regions;
1802 BLOCK_TO_BB (i) = count = 0;
1804 /* Remove blocks from queue[] when their in degree becomes
1805 zero. Repeat until no blocks are left on the list. This
1806 produces a topological list of blocks in the region. */
1813 child = queue[head];
1814 if (degree[child] == 0)
1817 rgn_bb_table[idx++] = child;
1818 BLOCK_TO_BB (child) = ++count;
1819 CONTAINING_RGN (child) = nr_regions;
1820 queue[head] = queue[tail--];
1822 for (ps = s_succs[child]; ps; ps = ps->next)
1823 if (INT_LIST_VAL (ps) != ENTRY_BLOCK
1824 && INT_LIST_VAL (ps) != EXIT_BLOCK)
1825 --degree[INT_LIST_VAL (ps)];
1836 /* Any block that did not end up in a region is placed into a region
1838 for (i = 0; i < n_basic_blocks; i++)
1841 rgn_bb_table[idx] = i;
1842 RGN_NR_BLOCKS (nr_regions) = 1;
1843 RGN_BLOCKS (nr_regions) = idx++;
1844 CONTAINING_RGN (i) = nr_regions++;
1845 BLOCK_TO_BB (i) = 0;
1856 /* functions for regions scheduling information */
1858 /* Compute dominators, probability, and potential-split-edges of bb.
1859 Assume that these values were already computed for bb's predecessors. */
1862 compute_dom_prob_ps (bb)
1865 int nxt_in_edge, fst_in_edge, pred;
1866 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1869 if (IS_RGN_ENTRY (bb))
1871 BITSET_ADD (dom[bb], 0, bbset_size);
1876 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1878 /* intialize dom[bb] to '111..1' */
1879 BITSET_INVERT (dom[bb], bbset_size);
1883 pred = FROM_BLOCK (nxt_in_edge);
1884 BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
1886 BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
1889 BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
1892 nr_rgn_out_edges = 0;
1893 fst_out_edge = OUT_EDGES (pred);
1894 nxt_out_edge = NEXT_OUT (fst_out_edge);
1895 BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
1898 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
1900 /* the successor doesn't belong the region? */
1901 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1902 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1905 while (fst_out_edge != nxt_out_edge)
1908 /* the successor doesn't belong the region? */
1909 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1910 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1912 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
1913 nxt_out_edge = NEXT_OUT (nxt_out_edge);
1917 /* now nr_rgn_out_edges is the number of region-exit edges from pred,
1918 and nr_out_edges will be the number of pred out edges not leaving
1920 nr_out_edges -= nr_rgn_out_edges;
1921 if (nr_rgn_out_edges > 0)
1922 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1924 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1925 nxt_in_edge = NEXT_IN (nxt_in_edge);
1927 while (fst_in_edge != nxt_in_edge);
1929 BITSET_ADD (dom[bb], bb, bbset_size);
1930 BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
1932 if (sched_verbose >= 2)
1933 fprintf (dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb), (int) (100.0 * prob[bb]));
1934 } /* compute_dom_prob_ps */
1936 /* functions for target info */
1938 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1939 Note that bb_trg dominates bb_src. */
1942 split_edges (bb_src, bb_trg, bl)
1947 int es = edgeset_size;
1948 edgeset src = (edgeset) alloca (es * sizeof (HOST_WIDE_INT));
1951 src[es] = (pot_split[bb_src])[es];
1952 BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
1953 extract_bitlst (src, edgeset_size, bl);
1957 /* Find the valid candidate-source-blocks for the target block TRG, compute
1958 their probability, and check if they are speculative or not.
1959 For speculative sources, compute their update-blocks and split-blocks. */
1962 compute_trg_info (trg)
1965 register candidate *sp;
1967 int check_block, update_idx;
1968 int i, j, k, fst_edge, nxt_edge;
1970 /* define some of the fields for the target bb as well */
1971 sp = candidate_table + trg;
1973 sp->is_speculative = 0;
1976 for (i = trg + 1; i < current_nr_blocks; i++)
1978 sp = candidate_table + i;
1980 sp->is_valid = IS_DOMINATED (i, trg);
1983 sp->src_prob = GET_SRC_PROB (i, trg);
1984 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
1989 split_edges (i, trg, &el);
1990 sp->is_speculative = (el.nr_members) ? 1 : 0;
1991 if (sp->is_speculative && !flag_schedule_speculative)
1997 sp->split_bbs.first_member = &bblst_table[bblst_last];
1998 sp->split_bbs.nr_members = el.nr_members;
1999 for (j = 0; j < el.nr_members; bblst_last++, j++)
2000 bblst_table[bblst_last] =
2001 TO_BLOCK (rgn_edges[el.first_member[j]]);
2002 sp->update_bbs.first_member = &bblst_table[bblst_last];
2004 for (j = 0; j < el.nr_members; j++)
2006 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
2007 fst_edge = nxt_edge = OUT_EDGES (check_block);
2010 for (k = 0; k < el.nr_members; k++)
2011 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
2014 if (k >= el.nr_members)
2016 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
2020 nxt_edge = NEXT_OUT (nxt_edge);
2022 while (fst_edge != nxt_edge);
2024 sp->update_bbs.nr_members = update_idx;
2029 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
2031 sp->is_speculative = 0;
2035 } /* compute_trg_info */
2038 /* Print candidates info, for debugging purposes. Callable from debugger. */
2044 if (!candidate_table[i].is_valid)
2047 if (candidate_table[i].is_speculative)
2050 fprintf (dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
2052 fprintf (dump, "split path: ");
2053 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
2055 int b = candidate_table[i].split_bbs.first_member[j];
2057 fprintf (dump, " %d ", b);
2059 fprintf (dump, "\n");
2061 fprintf (dump, "update path: ");
2062 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
2064 int b = candidate_table[i].update_bbs.first_member[j];
2066 fprintf (dump, " %d ", b);
2068 fprintf (dump, "\n");
2072 fprintf (dump, " src %d equivalent\n", BB_TO_BLOCK (i));
2077 /* Print candidates info, for debugging purposes. Callable from debugger. */
2080 debug_candidates (trg)
2085 fprintf (dump, "----------- candidate table: target: b=%d bb=%d ---\n",
2086 BB_TO_BLOCK (trg), trg);
2087 for (i = trg + 1; i < current_nr_blocks; i++)
2088 debug_candidate (i);
2092 /* functions for speculative scheduing */
2094 /* Return 0 if x is a set of a register alive in the beginning of one
2095 of the split-blocks of src, otherwise return 1. */
2098 check_live_1 (src, x)
2104 register rtx reg = SET_DEST (x);
2109 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2110 || GET_CODE (reg) == SIGN_EXTRACT
2111 || GET_CODE (reg) == STRICT_LOW_PART)
2112 reg = XEXP (reg, 0);
2114 if (GET_CODE (reg) != REG)
2117 regno = REGNO (reg);
2119 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2121 /* Global registers are assumed live */
2126 if (regno < FIRST_PSEUDO_REGISTER)
2128 /* check for hard registers */
2129 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2132 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2134 int b = candidate_table[src].split_bbs.first_member[i];
2136 if (REGNO_REG_SET_P (basic_block_live_at_start[b], regno + j))
2145 /* check for psuedo registers */
2146 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2148 int b = candidate_table[src].split_bbs.first_member[i];
2150 if (REGNO_REG_SET_P (basic_block_live_at_start[b], regno))
2162 /* If x is a set of a register R, mark that R is alive in the beginning
2163 of every update-block of src. */
2166 update_live_1 (src, x)
2172 register rtx reg = SET_DEST (x);
2177 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2178 || GET_CODE (reg) == SIGN_EXTRACT
2179 || GET_CODE (reg) == STRICT_LOW_PART)
2180 reg = XEXP (reg, 0);
2182 if (GET_CODE (reg) != REG)
2185 /* Global registers are always live, so the code below does not apply
2188 regno = REGNO (reg);
2190 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
2192 if (regno < FIRST_PSEUDO_REGISTER)
2194 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2197 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2199 int b = candidate_table[src].update_bbs.first_member[i];
2201 SET_REGNO_REG_SET (basic_block_live_at_start[b], regno + j);
2207 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2209 int b = candidate_table[src].update_bbs.first_member[i];
2211 SET_REGNO_REG_SET (basic_block_live_at_start[b], regno);
2218 /* Return 1 if insn can be speculatively moved from block src to trg,
2219 otherwise return 0. Called before first insertion of insn to
2220 ready-list or before the scheduling. */
2223 check_live (insn, src)
2227 /* find the registers set by instruction */
2228 if (GET_CODE (PATTERN (insn)) == SET
2229 || GET_CODE (PATTERN (insn)) == CLOBBER)
2230 return check_live_1 (src, PATTERN (insn));
2231 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2234 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2235 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2236 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2237 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
2247 /* Update the live registers info after insn was moved speculatively from
2248 block src to trg. */
2251 update_live (insn, src)
2255 /* find the registers set by instruction */
2256 if (GET_CODE (PATTERN (insn)) == SET
2257 || GET_CODE (PATTERN (insn)) == CLOBBER)
2258 update_live_1 (src, PATTERN (insn));
2259 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2262 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2263 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2264 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2265 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
2269 /* Exception Free Loads:
2271 We define five classes of speculative loads: IFREE, IRISKY,
2272 PFREE, PRISKY, and MFREE.
2274 IFREE loads are loads that are proved to be exception-free, just
2275 by examining the load insn. Examples for such loads are loads
2276 from TOC and loads of global data.
2278 IRISKY loads are loads that are proved to be exception-risky,
2279 just by examining the load insn. Examples for such loads are
2280 volatile loads and loads from shared memory.
2282 PFREE loads are loads for which we can prove, by examining other
2283 insns, that they are exception-free. Currently, this class consists
2284 of loads for which we are able to find a "similar load", either in
2285 the target block, or, if only one split-block exists, in that split
2286 block. Load2 is similar to load1 if both have same single base
2287 register. We identify only part of the similar loads, by finding
2288 an insn upon which both load1 and load2 have a DEF-USE dependence.
2290 PRISKY loads are loads for which we can prove, by examining other
2291 insns, that they are exception-risky. Currently we have two proofs for
2292 such loads. The first proof detects loads that are probably guarded by a
2293 test on the memory address. This proof is based on the
2294 backward and forward data dependence information for the region.
2295 Let load-insn be the examined load.
2296 Load-insn is PRISKY iff ALL the following hold:
2298 - insn1 is not in the same block as load-insn
2299 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2300 - test-insn is either a compare or a branch, not in the same block as load-insn
2301 - load-insn is reachable from test-insn
2302 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2304 This proof might fail when the compare and the load are fed
2305 by an insn not in the region. To solve this, we will add to this
2306 group all loads that have no input DEF-USE dependence.
2308 The second proof detects loads that are directly or indirectly
2309 fed by a speculative load. This proof is affected by the
2310 scheduling process. We will use the flag fed_by_spec_load.
2311 Initially, all insns have this flag reset. After a speculative
2312 motion of an insn, if insn is either a load, or marked as
2313 fed_by_spec_load, we will also mark as fed_by_spec_load every
2314 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2315 load which is fed_by_spec_load is also PRISKY.
2317 MFREE (maybe-free) loads are all the remaining loads. They may be
2318 exception-free, but we cannot prove it.
2320 Now, all loads in IFREE and PFREE classes are considered
2321 exception-free, while all loads in IRISKY and PRISKY classes are
2322 considered exception-risky. As for loads in the MFREE class,
2323 these are considered either exception-free or exception-risky,
2324 depending on whether we are pessimistic or optimistic. We have
2325 to take the pessimistic approach to assure the safety of
2326 speculative scheduling, but we can take the optimistic approach
2327 by invoking the -fsched_spec_load_dangerous option. */
2329 enum INSN_TRAP_CLASS
2331 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
2332 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
2335 #define WORST_CLASS(class1, class2) \
2336 ((class1 > class2) ? class1 : class2)
2338 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between */
2339 /* some speculatively moved load insn and this one. */
2340 char *fed_by_spec_load;
2343 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2344 #define IS_REACHABLE(bb_from, bb_to) \
2346 || IS_RGN_ENTRY (bb_from) \
2347 || (bitset_member (ancestor_edges[bb_to], \
2348 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2350 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2351 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2353 /* Non-zero iff the address is comprised from at most 1 register */
2354 #define CONST_BASED_ADDRESS_P(x) \
2355 (GET_CODE (x) == REG \
2356 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2357 || (GET_CODE (x) == LO_SUM)) \
2358 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2359 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2361 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2364 set_spec_fed (load_insn)
2369 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
2370 if (GET_MODE (link) == VOIDmode)
2371 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
2372 } /* set_spec_fed */
2374 /* On the path from the insn to load_insn_bb, find a conditional branch */
2375 /* depending on insn, that guards the speculative load. */
2378 find_conditional_protection (insn, load_insn_bb)
2384 /* iterate through DEF-USE forward dependences */
2385 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2387 rtx next = XEXP (link, 0);
2388 if ((CONTAINING_RGN (INSN_BLOCK (next)) ==
2389 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
2390 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
2391 && load_insn_bb != INSN_BB (next)
2392 && GET_MODE (link) == VOIDmode
2393 && (GET_CODE (next) == JUMP_INSN
2394 || find_conditional_protection (next, load_insn_bb)))
2398 } /* find_conditional_protection */
2400 /* Returns 1 if the same insn1 that participates in the computation
2401 of load_insn's address is feeding a conditional branch that is
2402 guarding on load_insn. This is true if we find a the two DEF-USE
2404 insn1 -> ... -> conditional-branch
2405 insn1 -> ... -> load_insn,
2406 and if a flow path exist:
2407 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2408 and if insn1 is on the path
2409 region-entry -> ... -> bb_trg -> ... load_insn.
2411 Locate insn1 by climbing on LOG_LINKS from load_insn.
2412 Locate the branch by following INSN_DEPEND from insn1. */
2415 is_conditionally_protected (load_insn, bb_src, bb_trg)
2421 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
2423 rtx insn1 = XEXP (link, 0);
2425 /* must be a DEF-USE dependence upon non-branch */
2426 if (GET_MODE (link) != VOIDmode
2427 || GET_CODE (insn1) == JUMP_INSN)
2430 /* must exist a path: region-entry -> ... -> bb_trg -> ... load_insn */
2431 if (INSN_BB (insn1) == bb_src
2432 || (CONTAINING_RGN (INSN_BLOCK (insn1))
2433 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
2434 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
2435 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
2438 /* now search for the conditional-branch */
2439 if (find_conditional_protection (insn1, bb_src))
2442 /* recursive step: search another insn1, "above" current insn1. */
2443 return is_conditionally_protected (insn1, bb_src, bb_trg);
2446 /* the chain does not exsist */
2448 } /* is_conditionally_protected */
2450 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2451 load_insn can move speculatively from bb_src to bb_trg. All the
2452 following must hold:
2454 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2455 (2) load_insn and load1 have a def-use dependence upon
2456 the same insn 'insn1'.
2457 (3) either load2 is in bb_trg, or:
2458 - there's only one split-block, and
2459 - load1 is on the escape path, and
2461 From all these we can conclude that the two loads access memory
2462 addresses that differ at most by a constant, and hence if moving
2463 load_insn would cause an exception, it would have been caused by
2467 is_pfree (load_insn, bb_src, bb_trg)
2472 register candidate *candp = candidate_table + bb_src;
2474 if (candp->split_bbs.nr_members != 1)
2475 /* must have exactly one escape block */
2478 for (back_link = LOG_LINKS (load_insn);
2479 back_link; back_link = XEXP (back_link, 1))
2481 rtx insn1 = XEXP (back_link, 0);
2483 if (GET_MODE (back_link) == VOIDmode)
2485 /* found a DEF-USE dependence (insn1, load_insn) */
2488 for (fore_link = INSN_DEPEND (insn1);
2489 fore_link; fore_link = XEXP (fore_link, 1))
2491 rtx insn2 = XEXP (fore_link, 0);
2492 if (GET_MODE (fore_link) == VOIDmode)
2494 /* found a DEF-USE dependence (insn1, insn2) */
2495 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
2496 /* insn2 not guaranteed to be a 1 base reg load */
2499 if (INSN_BB (insn2) == bb_trg)
2500 /* insn2 is the similar load, in the target block */
2503 if (*(candp->split_bbs.first_member) == INSN_BLOCK (insn2))
2504 /* insn2 is a similar load, in a split-block */
2511 /* couldn't find a similar load */
2515 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2516 as found by analyzing insn's expression. */
2519 may_trap_exp (x, is_store)
2527 code = GET_CODE (x);
2537 /* The insn uses memory */
2538 /* a volatile load */
2539 if (MEM_VOLATILE_P (x))
2541 /* an exception-free load */
2542 if (!may_trap_p (x))
2544 /* a load with 1 base register, to be further checked */
2545 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
2546 return PFREE_CANDIDATE;
2547 /* no info on the load, to be further checked */
2548 return PRISKY_CANDIDATE;
2553 int i, insn_class = TRAP_FREE;
2555 /* neither store nor load, check if it may cause a trap */
2558 /* recursive step: walk the insn... */
2559 fmt = GET_RTX_FORMAT (code);
2560 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2564 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
2565 insn_class = WORST_CLASS (insn_class, tmp_class);
2567 else if (fmt[i] == 'E')
2570 for (j = 0; j < XVECLEN (x, i); j++)
2572 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
2573 insn_class = WORST_CLASS (insn_class, tmp_class);
2574 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2578 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2583 } /* may_trap_exp */
2586 /* Classifies insn for the purpose of verifying that it can be
2587 moved speculatively, by examining it's patterns, returning:
2588 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2589 TRAP_FREE: non-load insn.
2590 IFREE: load from a globaly safe location.
2591 IRISKY: volatile load.
2592 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2593 being either PFREE or PRISKY. */
2596 haifa_classify_insn (insn)
2599 rtx pat = PATTERN (insn);
2600 int tmp_class = TRAP_FREE;
2601 int insn_class = TRAP_FREE;
2604 if (GET_CODE (pat) == PARALLEL)
2606 int i, len = XVECLEN (pat, 0);
2608 for (i = len - 1; i >= 0; i--)
2610 code = GET_CODE (XVECEXP (pat, 0, i));
2614 /* test if it is a 'store' */
2615 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
2618 /* test if it is a store */
2619 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
2620 if (tmp_class == TRAP_RISKY)
2622 /* test if it is a load */
2624 WORST_CLASS (tmp_class,
2625 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 0));
2628 insn_class = WORST_CLASS (insn_class, tmp_class);
2629 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2635 code = GET_CODE (pat);
2639 /* test if it is a 'store' */
2640 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
2643 /* test if it is a store */
2644 tmp_class = may_trap_exp (SET_DEST (pat), 1);
2645 if (tmp_class == TRAP_RISKY)
2647 /* test if it is a load */
2649 WORST_CLASS (tmp_class,
2650 may_trap_exp (SET_SRC (pat), 0));
2653 insn_class = tmp_class;
2658 } /* haifa_classify_insn */
2660 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2661 a load moved speculatively, or if load_insn is protected by
2662 a compare on load_insn's address). */
2665 is_prisky (load_insn, bb_src, bb_trg)
2669 if (FED_BY_SPEC_LOAD (load_insn))
2672 if (LOG_LINKS (load_insn) == NULL)
2673 /* dependence may 'hide' out of the region. */
2676 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2682 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2683 Return 1 if insn is exception-free (and the motion is valid)
2687 is_exception_free (insn, bb_src, bb_trg)
2691 int insn_class = haifa_classify_insn (insn);
2693 /* handle non-load insns */
2704 if (!flag_schedule_speculative_load)
2706 IS_LOAD_INSN (insn) = 1;
2713 case PFREE_CANDIDATE:
2714 if (is_pfree (insn, bb_src, bb_trg))
2716 /* don't 'break' here: PFREE-candidate is also PRISKY-candidate */
2717 case PRISKY_CANDIDATE:
2718 if (!flag_schedule_speculative_load_dangerous
2719 || is_prisky (insn, bb_src, bb_trg))
2725 return flag_schedule_speculative_load_dangerous;
2726 } /* is_exception_free */
2729 /* Process an insn's memory dependencies. There are four kinds of
2732 (0) read dependence: read follows read
2733 (1) true dependence: read follows write
2734 (2) anti dependence: write follows read
2735 (3) output dependence: write follows write
2737 We are careful to build only dependencies which actually exist, and
2738 use transitivity to avoid building too many links. */
2740 /* Return the INSN_LIST containing INSN in LIST, or NULL
2741 if LIST does not contain INSN. */
2744 find_insn_list (insn, list)
2750 if (XEXP (list, 0) == insn)
2752 list = XEXP (list, 1);
2758 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 otherwise. */
2760 __inline static char
2761 find_insn_mem_list (insn, x, list, list1)
2767 if (XEXP (list, 0) == insn
2768 && XEXP (list1, 0) == x)
2770 list = XEXP (list, 1);
2771 list1 = XEXP (list1, 1);
2777 /* Compute the function units used by INSN. This caches the value
2778 returned by function_units_used. A function unit is encoded as the
2779 unit number if the value is non-negative and the compliment of a
2780 mask if the value is negative. A function unit index is the
2781 non-negative encoding. */
2787 register int unit = INSN_UNIT (insn);
2791 recog_memoized (insn);
2793 /* A USE insn, or something else we don't need to understand.
2794 We can't pass these directly to function_units_used because it will
2795 trigger a fatal error for unrecognizable insns. */
2796 if (INSN_CODE (insn) < 0)
2800 unit = function_units_used (insn);
2801 /* Increment non-negative values so we can cache zero. */
2805 /* We only cache 16 bits of the result, so if the value is out of
2806 range, don't cache it. */
2807 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
2809 || (~unit & ((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
2810 INSN_UNIT (insn) = unit;
2812 return (unit > 0 ? unit - 1 : unit);
2815 /* Compute the blockage range for executing INSN on UNIT. This caches
2816 the value returned by the blockage_range_function for the unit.
2817 These values are encoded in an int where the upper half gives the
2818 minimum value and the lower half gives the maximum value. */
2820 __inline static unsigned int
2821 blockage_range (unit, insn)
2825 unsigned int blockage = INSN_BLOCKAGE (insn);
2828 if (UNIT_BLOCKED (blockage) != unit + 1)
2830 range = function_units[unit].blockage_range_function (insn);
2831 /* We only cache the blockage range for one unit and then only if
2833 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
2834 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
2837 range = BLOCKAGE_RANGE (blockage);
2842 /* A vector indexed by function unit instance giving the last insn to use
2843 the unit. The value of the function unit instance index for unit U
2844 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2845 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2847 /* A vector indexed by function unit instance giving the minimum time when
2848 the unit will unblock based on the maximum blockage cost. */
2849 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2851 /* A vector indexed by function unit number giving the number of insns
2852 that remain to use the unit. */
2853 static int unit_n_insns[FUNCTION_UNITS_SIZE];
2855 /* Reset the function unit state to the null state. */
2860 bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
2861 bzero ((char *) unit_tick, sizeof (unit_tick));
2862 bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
2865 /* Return the issue-delay of an insn */
2868 insn_issue_delay (insn)
2872 int unit = insn_unit (insn);
2874 /* efficiency note: in fact, we are working 'hard' to compute a
2875 value that was available in md file, and is not available in
2876 function_units[] structure. It would be nice to have this
2877 value there, too. */
2880 if (function_units[unit].blockage_range_function &&
2881 function_units[unit].blockage_function)
2882 delay = function_units[unit].blockage_function (insn, insn);
2885 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2886 if ((unit & 1) != 0 && function_units[i].blockage_range_function
2887 && function_units[i].blockage_function)
2888 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
2893 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2894 instance INSTANCE at time CLOCK if the previous actual hazard cost
2898 actual_hazard_this_instance (unit, instance, insn, clock, cost)
2899 int unit, instance, clock, cost;
2902 int tick = unit_tick[instance]; /* issue time of the last issued insn */
2904 if (tick - clock > cost)
2906 /* The scheduler is operating forward, so unit's last insn is the
2907 executing insn and INSN is the candidate insn. We want a
2908 more exact measure of the blockage if we execute INSN at CLOCK
2909 given when we committed the execution of the unit's last insn.
2911 The blockage value is given by either the unit's max blockage
2912 constant, blockage range function, or blockage function. Use
2913 the most exact form for the given unit. */
2915 if (function_units[unit].blockage_range_function)
2917 if (function_units[unit].blockage_function)
2918 tick += (function_units[unit].blockage_function
2919 (unit_last_insn[instance], insn)
2920 - function_units[unit].max_blockage);
2922 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
2923 - function_units[unit].max_blockage);
2925 if (tick - clock > cost)
2926 cost = tick - clock;
2931 /* Record INSN as having begun execution on the units encoded by UNIT at
2934 __inline static void
2935 schedule_unit (unit, insn, clock)
2943 int instance = unit;
2944 #if MAX_MULTIPLICITY > 1
2945 /* Find the first free instance of the function unit and use that
2946 one. We assume that one is free. */
2947 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2949 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
2951 instance += FUNCTION_UNITS_SIZE;
2954 unit_last_insn[instance] = insn;
2955 unit_tick[instance] = (clock + function_units[unit].max_blockage);
2958 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2959 if ((unit & 1) != 0)
2960 schedule_unit (i, insn, clock);
2963 /* Return the actual hazard cost of executing INSN on the units encoded by
2964 UNIT at time CLOCK if the previous actual hazard cost was COST. */
2967 actual_hazard (unit, insn, clock, cost)
2968 int unit, clock, cost;
2975 /* Find the instance of the function unit with the minimum hazard. */
2976 int instance = unit;
2977 int best_cost = actual_hazard_this_instance (unit, instance, insn,
2981 #if MAX_MULTIPLICITY > 1
2982 if (best_cost > cost)
2984 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2986 instance += FUNCTION_UNITS_SIZE;
2987 this_cost = actual_hazard_this_instance (unit, instance, insn,
2989 if (this_cost < best_cost)
2991 best_cost = this_cost;
2992 if (this_cost <= cost)
2998 cost = MAX (cost, best_cost);
3001 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3002 if ((unit & 1) != 0)
3003 cost = actual_hazard (i, insn, clock, cost);
3008 /* Return the potential hazard cost of executing an instruction on the
3009 units encoded by UNIT if the previous potential hazard cost was COST.
3010 An insn with a large blockage time is chosen in preference to one
3011 with a smaller time; an insn that uses a unit that is more likely
3012 to be used is chosen in preference to one with a unit that is less
3013 used. We are trying to minimize a subsequent actual hazard. */
3016 potential_hazard (unit, insn, cost)
3021 unsigned int minb, maxb;
3025 minb = maxb = function_units[unit].max_blockage;
3028 if (function_units[unit].blockage_range_function)
3030 maxb = minb = blockage_range (unit, insn);
3031 maxb = MAX_BLOCKAGE_COST (maxb);
3032 minb = MIN_BLOCKAGE_COST (minb);
3037 /* Make the number of instructions left dominate. Make the
3038 minimum delay dominate the maximum delay. If all these
3039 are the same, use the unit number to add an arbitrary
3040 ordering. Other terms can be added. */
3041 ncost = minb * 0x40 + maxb;
3042 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
3049 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3050 if ((unit & 1) != 0)
3051 cost = potential_hazard (i, insn, cost);
3056 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3057 This is the number of cycles between instruction issue and
3058 instruction results. */
3061 insn_cost (insn, link, used)
3062 rtx insn, link, used;
3064 register int cost = INSN_COST (insn);
3068 recog_memoized (insn);
3070 /* A USE insn, or something else we don't need to understand.
3071 We can't pass these directly to result_ready_cost because it will
3072 trigger a fatal error for unrecognizable insns. */
3073 if (INSN_CODE (insn) < 0)
3075 INSN_COST (insn) = 1;
3080 cost = result_ready_cost (insn);
3085 INSN_COST (insn) = cost;
3089 /* in this case estimate cost without caring how insn is used. */
3090 if (link == 0 && used == 0)
3093 /* A USE insn should never require the value used to be computed. This
3094 allows the computation of a function's result and parameter values to
3095 overlap the return and call. */
3096 recog_memoized (used);
3097 if (INSN_CODE (used) < 0)
3098 LINK_COST_FREE (link) = 1;
3100 /* If some dependencies vary the cost, compute the adjustment. Most
3101 commonly, the adjustment is complete: either the cost is ignored
3102 (in the case of an output- or anti-dependence), or the cost is
3103 unchanged. These values are cached in the link as LINK_COST_FREE
3104 and LINK_COST_ZERO. */
3106 if (LINK_COST_FREE (link))
3109 else if (!LINK_COST_ZERO (link))
3113 ADJUST_COST (used, link, insn, ncost);
3115 LINK_COST_FREE (link) = ncost = 1;
3117 LINK_COST_ZERO (link) = 1;
3124 /* Compute the priority number for INSN. */
3133 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
3136 if ((this_priority = INSN_PRIORITY (insn)) == 0)
3138 if (INSN_DEPEND (insn) == 0)
3139 this_priority = insn_cost (insn, 0, 0);
3141 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
3146 if (RTX_INTEGRATED_P (link))
3149 next = XEXP (link, 0);
3151 /* critical path is meaningful in block boundaries only */
3152 if (INSN_BLOCK (next) != INSN_BLOCK (insn))
3155 next_priority = insn_cost (insn, link, next) + priority (next);
3156 if (next_priority > this_priority)
3157 this_priority = next_priority;
3159 INSN_PRIORITY (insn) = this_priority;
3161 return this_priority;
3165 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3166 them to the unused_*_list variables, so that they can be reused. */
3169 free_pending_lists ()
3171 if (current_nr_blocks <= 1)
3173 free_list (&pending_read_insns, &unused_insn_list);
3174 free_list (&pending_write_insns, &unused_insn_list);
3175 free_list (&pending_read_mems, &unused_expr_list);
3176 free_list (&pending_write_mems, &unused_expr_list);
3180 /* interblock scheduling */
3183 for (bb = 0; bb < current_nr_blocks; bb++)
3185 free_list (&bb_pending_read_insns[bb], &unused_insn_list);
3186 free_list (&bb_pending_write_insns[bb], &unused_insn_list);
3187 free_list (&bb_pending_read_mems[bb], &unused_expr_list);
3188 free_list (&bb_pending_write_mems[bb], &unused_expr_list);
3193 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3194 The MEM is a memory reference contained within INSN, which we are saving
3195 so that we can do memory aliasing on it. */
3198 add_insn_mem_dependence (insn_list, mem_list, insn, mem)
3199 rtx *insn_list, *mem_list, insn, mem;
3203 link = alloc_INSN_LIST (insn, *insn_list);
3206 link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
3209 pending_lists_length++;
3213 /* Make a dependency between every memory reference on the pending lists
3214 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3218 flush_pending_lists (insn, only_write)
3225 while (pending_read_insns && ! only_write)
3227 add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
3229 link = pending_read_insns;
3230 pending_read_insns = XEXP (pending_read_insns, 1);
3231 XEXP (link, 1) = unused_insn_list;
3232 unused_insn_list = link;
3234 link = pending_read_mems;
3235 pending_read_mems = XEXP (pending_read_mems, 1);
3236 XEXP (link, 1) = unused_expr_list;
3237 unused_expr_list = link;
3239 while (pending_write_insns)
3241 add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
3243 link = pending_write_insns;
3244 pending_write_insns = XEXP (pending_write_insns, 1);
3245 XEXP (link, 1) = unused_insn_list;
3246 unused_insn_list = link;
3248 link = pending_write_mems;
3249 pending_write_mems = XEXP (pending_write_mems, 1);
3250 XEXP (link, 1) = unused_expr_list;
3251 unused_expr_list = link;
3253 pending_lists_length = 0;
3255 /* last_pending_memory_flush is now a list of insns */
3256 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3257 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3259 free_list (&last_pending_memory_flush, &unused_insn_list);
3260 last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
3263 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
3264 by the write to the destination of X, and reads of everything mentioned. */
3267 sched_analyze_1 (x, insn)
3272 register rtx dest = SET_DEST (x);
3277 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3278 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3280 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3282 /* The second and third arguments are values read by this insn. */
3283 sched_analyze_2 (XEXP (dest, 1), insn);
3284 sched_analyze_2 (XEXP (dest, 2), insn);
3286 dest = SUBREG_REG (dest);
3289 if (GET_CODE (dest) == REG)
3293 regno = REGNO (dest);
3295 /* A hard reg in a wide mode may really be multiple registers.
3296 If so, mark all of them just like the first. */
3297 if (regno < FIRST_PSEUDO_REGISTER)
3299 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
3304 for (u = reg_last_uses[regno + i]; u; u = XEXP (u, 1))
3305 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3306 reg_last_uses[regno + i] = 0;
3308 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3309 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3311 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
3313 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3314 /* Function calls clobber all call_used regs. */
3315 for (u = last_function_call; u; u = XEXP (u, 1))
3316 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3323 for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
3324 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3325 reg_last_uses[regno] = 0;
3327 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3328 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3330 SET_REGNO_REG_SET (reg_pending_sets, regno);
3332 /* Pseudos that are REG_EQUIV to something may be replaced
3333 by that during reloading. We need only add dependencies for
3334 the address in the REG_EQUIV note. */
3335 if (!reload_completed
3336 && reg_known_equiv_p[regno]
3337 && GET_CODE (reg_known_value[regno]) == MEM)
3338 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3340 /* Don't let it cross a call after scheduling if it doesn't
3341 already cross one. */
3343 if (REG_N_CALLS_CROSSED (regno) == 0)
3344 for (u = last_function_call; u; u = XEXP (u, 1))
3345 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3348 else if (GET_CODE (dest) == MEM)
3350 /* Writing memory. */
3352 if (pending_lists_length > 32)
3354 /* Flush all pending reads and writes to prevent the pending lists
3355 from getting any larger. Insn scheduling runs too slowly when
3356 these lists get long. The number 32 was chosen because it
3357 seems like a reasonable number. When compiling GCC with itself,
3358 this flush occurs 8 times for sparc, and 10 times for m88k using
3360 flush_pending_lists (insn, 0);
3365 rtx pending, pending_mem;
3367 pending = pending_read_insns;
3368 pending_mem = pending_read_mems;
3371 /* If a dependency already exists, don't create a new one. */
3372 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3373 if (anti_dependence (XEXP (pending_mem, 0), dest))
3374 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3376 pending = XEXP (pending, 1);
3377 pending_mem = XEXP (pending_mem, 1);
3380 pending = pending_write_insns;
3381 pending_mem = pending_write_mems;
3384 /* If a dependency already exists, don't create a new one. */
3385 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
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;
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 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3482 /* Function calls clobber all call_used regs. */
3483 for (u = last_function_call; u; u = XEXP (u, 1))
3484 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3489 reg_last_uses[regno] = alloc_INSN_LIST (insn, reg_last_uses[regno]);
3491 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3492 add_dependence (insn, XEXP (u, 0), 0);
3494 /* Pseudos that are REG_EQUIV to something may be replaced
3495 by that during reloading. We need only add dependencies for
3496 the address in the REG_EQUIV note. */
3497 if (!reload_completed
3498 && reg_known_equiv_p[regno]
3499 && GET_CODE (reg_known_value[regno]) == MEM)
3500 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3502 /* If the register does not already cross any calls, then add this
3503 insn to the sched_before_next_call list so that it will still
3504 not cross calls after scheduling. */
3505 if (REG_N_CALLS_CROSSED (regno) == 0)
3506 add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
3513 /* Reading memory. */
3515 rtx pending, pending_mem;
3517 pending = pending_read_insns;
3518 pending_mem = pending_read_mems;
3521 /* If a dependency already exists, don't create a new one. */
3522 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3523 if (read_dependence (XEXP (pending_mem, 0), x))
3524 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3526 pending = XEXP (pending, 1);
3527 pending_mem = XEXP (pending_mem, 1);
3530 pending = pending_write_insns;
3531 pending_mem = pending_write_mems;
3534 /* If a dependency already exists, don't create a new one. */
3535 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3536 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
3538 add_dependence (insn, XEXP (pending, 0), 0);
3540 pending = XEXP (pending, 1);
3541 pending_mem = XEXP (pending_mem, 1);
3544 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3545 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3547 /* Always add these dependencies to pending_reads, since
3548 this insn may be followed by a write. */
3549 add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
3552 /* Take advantage of tail recursion here. */
3553 sched_analyze_2 (XEXP (x, 0), insn);
3559 case UNSPEC_VOLATILE:
3564 /* Traditional and volatile asm instructions must be considered to use
3565 and clobber all hard registers, all pseudo-registers and all of
3566 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3568 Consider for instance a volatile asm that changes the fpu rounding
3569 mode. An insn should not be moved across this even if it only uses
3570 pseudo-regs because it might give an incorrectly rounded result. */
3571 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
3573 int max_reg = max_reg_num ();
3574 for (i = 0; i < max_reg; i++)
3576 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3577 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3578 reg_last_uses[i] = 0;
3580 /* reg_last_sets[r] is now a list of insns */
3581 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3582 add_dependence (insn, XEXP (u, 0), 0);
3584 reg_pending_sets_all = 1;
3586 flush_pending_lists (insn, 0);
3589 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3590 We can not just fall through here since then we would be confused
3591 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3592 traditional asms unlike their normal usage. */
3594 if (code == ASM_OPERANDS)
3596 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3597 sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
3607 /* These both read and modify the result. We must handle them as writes
3608 to get proper dependencies for following instructions. We must handle
3609 them as reads to get proper dependencies from this to previous
3610 instructions. Thus we need to pass them to both sched_analyze_1
3611 and sched_analyze_2. We must call sched_analyze_2 first in order
3612 to get the proper antecedent for the read. */
3613 sched_analyze_2 (XEXP (x, 0), insn);
3614 sched_analyze_1 (x, insn);
3621 /* Other cases: walk the insn. */
3622 fmt = GET_RTX_FORMAT (code);
3623 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3626 sched_analyze_2 (XEXP (x, i), insn);
3627 else if (fmt[i] == 'E')
3628 for (j = 0; j < XVECLEN (x, i); j++)
3629 sched_analyze_2 (XVECEXP (x, i, j), insn);
3633 /* Analyze an INSN with pattern X to find all dependencies. */
3636 sched_analyze_insn (x, insn, loop_notes)
3640 register RTX_CODE code = GET_CODE (x);
3642 int maxreg = max_reg_num ();
3645 if (code == SET || code == CLOBBER)
3646 sched_analyze_1 (x, insn);
3647 else if (code == PARALLEL)
3650 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3652 code = GET_CODE (XVECEXP (x, 0, i));
3653 if (code == SET || code == CLOBBER)
3654 sched_analyze_1 (XVECEXP (x, 0, i), insn);
3656 sched_analyze_2 (XVECEXP (x, 0, i), insn);
3660 sched_analyze_2 (x, insn);
3662 /* Mark registers CLOBBERED or used by called function. */
3663 if (GET_CODE (insn) == CALL_INSN)
3664 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3666 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3667 sched_analyze_1 (XEXP (link, 0), insn);
3669 sched_analyze_2 (XEXP (link, 0), insn);
3672 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic block, then
3673 we must be sure that no instructions are scheduled across it.
3674 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3675 become incorrect. */
3679 int max_reg = max_reg_num ();
3682 for (i = 0; i < max_reg; i++)
3685 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3686 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3687 reg_last_uses[i] = 0;
3689 /* reg_last_sets[r] is now a list of insns */
3690 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3691 add_dependence (insn, XEXP (u, 0), 0);
3693 reg_pending_sets_all = 1;
3695 flush_pending_lists (insn, 0);
3698 while (XEXP (link, 1))
3699 link = XEXP (link, 1);
3700 XEXP (link, 1) = REG_NOTES (insn);
3701 REG_NOTES (insn) = loop_notes;
3704 /* After reload, it is possible for an instruction to have a REG_DEAD note
3705 for a register that actually dies a few instructions earlier. For
3706 example, this can happen with SECONDARY_MEMORY_NEEDED reloads.
3707 In this case, we must consider the insn to use the register mentioned
3708 in the REG_DEAD note. Otherwise, we may accidentally move this insn
3709 after another insn that sets the register, thus getting obviously invalid
3710 rtl. This confuses reorg which believes that REG_DEAD notes are still
3713 ??? We would get better code if we fixed reload to put the REG_DEAD
3714 notes in the right places, but that may not be worth the effort. */
3716 if (reload_completed)
3720 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3721 if (REG_NOTE_KIND (note) == REG_DEAD)
3722 sched_analyze_2 (XEXP (note, 0), insn);
3725 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
3727 /* reg_last_sets[r] is now a list of insns */
3728 free_list (®_last_sets[i], &unused_insn_list);
3730 = alloc_INSN_LIST (insn, NULL_RTX);
3732 CLEAR_REG_SET (reg_pending_sets);
3734 if (reg_pending_sets_all)
3736 for (i = 0; i < maxreg; i++)
3738 /* reg_last_sets[r] is now a list of insns */
3739 free_list (®_last_sets[i], &unused_insn_list);
3740 reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3743 reg_pending_sets_all = 0;
3746 /* Handle function calls and function returns created by the epilogue
3748 if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
3753 /* When scheduling instructions, we make sure calls don't lose their
3754 accompanying USE insns by depending them one on another in order.
3756 Also, we must do the same thing for returns created by the epilogue
3757 threading code. Note this code works only in this special case,
3758 because other passes make no guarantee that they will never emit
3759 an instruction between a USE and a RETURN. There is such a guarantee
3760 for USE instructions immediately before a call. */
3762 prev_dep_insn = insn;
3763 dep_insn = PREV_INSN (insn);
3764 while (GET_CODE (dep_insn) == INSN
3765 && GET_CODE (PATTERN (dep_insn)) == USE
3766 && GET_CODE (XEXP (PATTERN (dep_insn), 0)) == REG)
3768 SCHED_GROUP_P (prev_dep_insn) = 1;
3770 /* Make a copy of all dependencies on dep_insn, and add to insn.
3771 This is so that all of the dependencies will apply to the
3774 for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
3775 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3777 prev_dep_insn = dep_insn;
3778 dep_insn = PREV_INSN (dep_insn);
3783 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3784 for every dependency. */
3787 sched_analyze (head, tail)
3794 for (insn = head;; insn = NEXT_INSN (insn))
3796 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
3798 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3801 else if (GET_CODE (insn) == CALL_INSN)
3806 CANT_MOVE (insn) = 1;
3808 /* Any instruction using a hard register which may get clobbered
3809 by a call needs to be marked as dependent on this call.
3810 This prevents a use of a hard return reg from being moved
3811 past a void call (i.e. it does not explicitly set the hard
3814 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3815 all registers, not just hard registers, may be clobbered by this
3818 /* Insn, being a CALL_INSN, magically depends on
3819 `last_function_call' already. */
3821 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
3822 && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
3824 int max_reg = max_reg_num ();
3825 for (i = 0; i < max_reg; i++)
3827 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3828 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3830 reg_last_uses[i] = 0;
3832 /* reg_last_sets[r] is now a list of insns */
3833 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3834 add_dependence (insn, XEXP (u, 0), 0);
3836 reg_pending_sets_all = 1;
3838 /* Add a pair of fake REG_NOTE which we will later
3839 convert back into a NOTE_INSN_SETJMP note. See
3840 reemit_notes for why we use a pair of NOTEs. */
3841 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3844 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3845 GEN_INT (NOTE_INSN_SETJMP),
3850 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3851 if (call_used_regs[i] || global_regs[i])
3853 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3854 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3855 reg_last_uses[i] = 0;
3857 /* reg_last_sets[r] is now a list of insns */
3858 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3859 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3861 SET_REGNO_REG_SET (reg_pending_sets, i);
3865 /* For each insn which shouldn't cross a call, add a dependence
3866 between that insn and this call insn. */
3867 x = LOG_LINKS (sched_before_next_call);
3870 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
3873 LOG_LINKS (sched_before_next_call) = 0;
3875 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3878 /* In the absence of interprocedural alias analysis, we must flush
3879 all pending reads and writes, and start new dependencies starting
3880 from here. But only flush writes for constant calls (which may
3881 be passed a pointer to something we haven't written yet). */
3882 flush_pending_lists (insn, CONST_CALL_P (insn));
3884 /* Depend this function call (actually, the user of this
3885 function call) on all hard register clobberage. */
3887 /* last_function_call is now a list of insns */
3888 free_list(&last_function_call, &unused_insn_list);
3889 last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3892 /* See comments on reemit_notes as to why we do this. */
3893 else if (GET_CODE (insn) == NOTE
3894 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
3895 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
3896 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
3897 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
3898 || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
3899 && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
3901 loop_notes = alloc_EXPR_LIST (REG_DEAD,
3902 GEN_INT (NOTE_BLOCK_NUMBER (insn)),
3904 loop_notes = alloc_EXPR_LIST (REG_DEAD,
3905 GEN_INT (NOTE_LINE_NUMBER (insn)),
3907 CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
3916 /* Called when we see a set of a register. If death is true, then we are
3917 scanning backwards. Mark that register as unborn. If nobody says
3918 otherwise, that is how things will remain. If death is false, then we
3919 are scanning forwards. Mark that register as being born. */
3922 sched_note_set (x, death)
3927 register rtx reg = SET_DEST (x);
3933 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
3934 || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
3936 /* Must treat modification of just one hardware register of a multi-reg
3937 value or just a byte field of a register exactly the same way that
3938 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
3939 does not kill the entire register. */
3940 if (GET_CODE (reg) != SUBREG
3941 || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
3944 reg = SUBREG_REG (reg);
3947 if (GET_CODE (reg) != REG)
3950 /* Global registers are always live, so the code below does not apply
3953 regno = REGNO (reg);
3954 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
3958 /* If we only set part of the register, then this set does not
3963 /* Try killing this register. */
3964 if (regno < FIRST_PSEUDO_REGISTER)
3966 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
3969 CLEAR_REGNO_REG_SET (bb_live_regs, regno + j);
3974 /* Recompute REG_BASIC_BLOCK as we update all the other
3975 dataflow information. */
3976 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
3977 sched_reg_basic_block[regno] = current_block_num;
3978 else if (sched_reg_basic_block[regno] != current_block_num)
3979 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
3981 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
3986 /* Make the register live again. */
3987 if (regno < FIRST_PSEUDO_REGISTER)
3989 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
3992 SET_REGNO_REG_SET (bb_live_regs, regno + j);
3997 SET_REGNO_REG_SET (bb_live_regs, regno);
4003 /* Macros and functions for keeping the priority queue sorted, and
4004 dealing with queueing and dequeueing of instructions. */
4006 #define SCHED_SORT(READY, N_READY) \
4007 do { if ((N_READY) == 2) \
4008 swap_sort (READY, N_READY); \
4009 else if ((N_READY) > 2) \
4010 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4013 /* Returns a positive value if x is preferred; returns a negative value if
4014 y is preferred. Should never return 0, since that will make the sort
4018 rank_for_schedule (x, y)
4019 const GENERIC_PTR x;
4020 const GENERIC_PTR y;
4022 rtx tmp = *(rtx *)y;
4023 rtx tmp2 = *(rtx *)x;
4025 int tmp_class, tmp2_class;
4026 int val, priority_val, spec_val, prob_val, weight_val;
4029 /* prefer insn with higher priority */
4030 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
4032 return priority_val;
4034 /* prefer an insn with smaller contribution to registers-pressure */
4035 if (!reload_completed &&
4036 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
4037 return (weight_val);
4039 /* some comparison make sense in interblock scheduling only */
4040 if (INSN_BB (tmp) != INSN_BB (tmp2))
4042 /* prefer an inblock motion on an interblock motion */
4043 if ((INSN_BB (tmp2) == target_bb) && (INSN_BB (tmp) != target_bb))
4045 if ((INSN_BB (tmp) == target_bb) && (INSN_BB (tmp2) != target_bb))
4048 /* prefer a useful motion on a speculative one */
4049 if ((spec_val = IS_SPECULATIVE_INSN (tmp) - IS_SPECULATIVE_INSN (tmp2)))
4052 /* prefer a more probable (speculative) insn */
4053 prob_val = INSN_PROBABILITY (tmp2) - INSN_PROBABILITY (tmp);
4058 /* compare insns based on their relation to the last-scheduled-insn */
4059 if (last_scheduled_insn)
4061 /* Classify the instructions into three classes:
4062 1) Data dependent on last schedule insn.
4063 2) Anti/Output dependent on last scheduled insn.
4064 3) Independent of last scheduled insn, or has latency of one.
4065 Choose the insn from the highest numbered class if different. */
4066 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
4067 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
4069 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4074 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
4075 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
4077 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4082 if ((val = tmp2_class - tmp_class))
4086 /* If insns are equally good, sort by INSN_LUID (original insn order),
4087 so that we make the sort stable. This minimizes instruction movement,
4088 thus minimizing sched's effect on debugging and cross-jumping. */
4089 return INSN_LUID (tmp) - INSN_LUID (tmp2);
4092 /* Resort the array A in which only element at index N may be out of order. */
4094 __inline static void
4099 rtx insn = a[n - 1];
4102 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
4110 static int max_priority;
4112 /* Add INSN to the insn queue so that it can be executed at least
4113 N_CYCLES after the currently executing insn. Preserve insns
4114 chain for debugging purposes. */
4116 __inline static void
4117 queue_insn (insn, n_cycles)
4121 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
4122 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
4123 insn_queue[next_q] = link;
4126 if (sched_verbose >= 2)
4128 fprintf (dump, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn));
4130 if (INSN_BB (insn) != target_bb)
4131 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
4133 fprintf (dump, "queued for %d cycles.\n", n_cycles);
4138 /* Return nonzero if PAT is the pattern of an insn which makes a
4142 birthing_insn_p (pat)
4147 if (reload_completed == 1)
4150 if (GET_CODE (pat) == SET
4151 && GET_CODE (SET_DEST (pat)) == REG)
4153 rtx dest = SET_DEST (pat);
4154 int i = REGNO (dest);
4156 /* It would be more accurate to use refers_to_regno_p or
4157 reg_mentioned_p to determine when the dest is not live before this
4160 if (REGNO_REG_SET_P (bb_live_regs, i))
4161 return (REG_N_SETS (i) == 1);
4165 if (GET_CODE (pat) == PARALLEL)
4167 for (j = 0; j < XVECLEN (pat, 0); j++)
4168 if (birthing_insn_p (XVECEXP (pat, 0, j)))
4174 /* PREV is an insn that is ready to execute. Adjust its priority if that
4175 will help shorten register lifetimes. */
4177 __inline static void
4178 adjust_priority (prev)
4181 /* Trying to shorten register lives after reload has completed
4182 is useless and wrong. It gives inaccurate schedules. */
4183 if (reload_completed == 0)
4188 /* ??? This code has no effect, because REG_DEAD notes are removed
4189 before we ever get here. */
4190 for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
4191 if (REG_NOTE_KIND (note) == REG_DEAD)
4194 /* Defer scheduling insns which kill registers, since that
4195 shortens register lives. Prefer scheduling insns which
4196 make registers live for the same reason. */
4200 INSN_PRIORITY (prev) >>= 3;
4203 INSN_PRIORITY (prev) >>= 2;
4207 INSN_PRIORITY (prev) >>= 1;
4210 if (birthing_insn_p (PATTERN (prev)))
4212 int max = max_priority;
4214 if (max > INSN_PRIORITY (prev))
4215 INSN_PRIORITY (prev) = max;
4219 #ifdef ADJUST_PRIORITY
4220 ADJUST_PRIORITY (prev);
4225 /* INSN is the "currently executing insn". Launch each insn which was
4226 waiting on INSN. READY is a vector of insns which are ready to fire.
4227 N_READY is the number of elements in READY. CLOCK is the current
4231 schedule_insn (insn, ready, n_ready, clock)
4240 unit = insn_unit (insn);
4242 if (sched_verbose >= 2)
4244 fprintf (dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ", INSN_UID (insn));
4245 insn_print_units (insn);
4246 fprintf (dump, "\n");
4249 if (sched_verbose && unit == -1)
4250 visualize_no_unit (insn);
4252 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
4253 schedule_unit (unit, insn, clock);
4255 if (INSN_DEPEND (insn) == 0)
4258 /* This is used by the function adjust_priority above. */
4260 max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
4262 max_priority = INSN_PRIORITY (insn);
4264 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
4266 rtx next = XEXP (link, 0);
4267 int cost = insn_cost (insn, link, next);
4269 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
4271 if ((INSN_DEP_COUNT (next) -= 1) == 0)
4273 int effective_cost = INSN_TICK (next) - clock;
4275 /* For speculative insns, before inserting to ready/queue,
4276 check live, exception-free, and issue-delay */
4277 if (INSN_BB (next) != target_bb
4278 && (!IS_VALID (INSN_BB (next))
4280 || (IS_SPECULATIVE_INSN (next)
4281 && (insn_issue_delay (next) > 3
4282 || !check_live (next, INSN_BB (next))
4283 || !is_exception_free (next, INSN_BB (next), target_bb)))))
4286 if (sched_verbose >= 2)
4288 fprintf (dump, ";;\t\tdependences resolved: insn %d ", INSN_UID (next));
4290 if (current_nr_blocks > 1 && INSN_BB (next) != target_bb)
4291 fprintf (dump, "/b%d ", INSN_BLOCK (next));
4293 if (effective_cost <= 1)
4294 fprintf (dump, "into ready\n");
4296 fprintf (dump, "into queue with cost=%d\n", effective_cost);
4299 /* Adjust the priority of NEXT and either put it on the ready
4300 list or queue it. */
4301 adjust_priority (next);
4302 if (effective_cost <= 1)
4303 ready[n_ready++] = next;
4305 queue_insn (next, effective_cost);
4313 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4317 create_reg_dead_note (reg, insn)
4322 /* The number of registers killed after scheduling must be the same as the
4323 number of registers killed before scheduling. The number of REG_DEAD
4324 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4325 might become one DImode hard register REG_DEAD note, but the number of
4326 registers killed will be conserved.
4328 We carefully remove REG_DEAD notes from the dead_notes list, so that
4329 there will be none left at the end. If we run out early, then there
4330 is a bug somewhere in flow, combine and/or sched. */
4332 if (dead_notes == 0)
4334 if (current_nr_blocks <= 1)
4337 link = alloc_EXPR_LIST (REG_DEAD, NULL_RTX, NULL_RTX);
4341 /* Number of regs killed by REG. */
4342 int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
4343 : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
4344 /* Number of regs killed by REG_DEAD notes taken off the list. */
4348 reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4349 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4350 GET_MODE (XEXP (link, 0))));
4351 while (reg_note_regs < regs_killed)
4353 link = XEXP (link, 1);
4355 /* LINK might be zero if we killed more registers after scheduling
4356 than before, and the last hard register we kill is actually
4359 This is normal for interblock scheduling, so deal with it in
4360 that case, else abort. */
4361 if (link == NULL_RTX && current_nr_blocks <= 1)
4363 else if (link == NULL_RTX)
4364 link = alloc_EXPR_LIST (REG_DEAD, gen_rtx_REG (word_mode, 0),
4367 reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4368 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4369 GET_MODE (XEXP (link, 0))));
4371 dead_notes = XEXP (link, 1);
4373 /* If we took too many regs kills off, put the extra ones back. */
4374 while (reg_note_regs > regs_killed)
4376 rtx temp_reg, temp_link;
4378 temp_reg = gen_rtx_REG (word_mode, 0);
4379 temp_link = alloc_EXPR_LIST (REG_DEAD, temp_reg, dead_notes);
4380 dead_notes = temp_link;
4385 XEXP (link, 0) = reg;
4386 XEXP (link, 1) = REG_NOTES (insn);
4387 REG_NOTES (insn) = link;
4390 /* Subroutine on attach_deaths_insn--handles the recursive search
4391 through INSN. If SET_P is true, then x is being modified by the insn. */
4394 attach_deaths (x, insn, set_p)
4401 register enum rtx_code code;
4407 code = GET_CODE (x);
4419 /* Get rid of the easy cases first. */
4424 /* If the register dies in this insn, queue that note, and mark
4425 this register as needing to die. */
4426 /* This code is very similar to mark_used_1 (if set_p is false)
4427 and mark_set_1 (if set_p is true) in flow.c. */
4437 all_needed = some_needed = REGNO_REG_SET_P (old_live_regs, regno);
4438 if (regno < FIRST_PSEUDO_REGISTER)
4442 n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4445 int needed = (REGNO_REG_SET_P (old_live_regs, regno + n));
4446 some_needed |= needed;
4447 all_needed &= needed;
4451 /* If it wasn't live before we started, then add a REG_DEAD note.
4452 We must check the previous lifetime info not the current info,
4453 because we may have to execute this code several times, e.g.
4454 once for a clobber (which doesn't add a note) and later
4455 for a use (which does add a note).
4457 Always make the register live. We must do this even if it was
4458 live before, because this may be an insn which sets and uses
4459 the same register, in which case the register has already been
4460 killed, so we must make it live again.
4462 Global registers are always live, and should never have a REG_DEAD
4463 note added for them, so none of the code below applies to them. */
4465 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
4467 /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
4468 STACK_POINTER_REGNUM, since these are always considered to be
4469 live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
4470 if (regno != FRAME_POINTER_REGNUM
4471 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4472 && ! (regno == HARD_FRAME_POINTER_REGNUM)
4474 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4475 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
4477 && regno != STACK_POINTER_REGNUM)
4479 if (! all_needed && ! dead_or_set_p (insn, x))
4481 /* Check for the case where the register dying partially
4482 overlaps the register set by this insn. */
4483 if (regno < FIRST_PSEUDO_REGISTER
4484 && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
4486 int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4488 some_needed |= dead_or_set_regno_p (insn, regno + n);
4491 /* If none of the words in X is needed, make a REG_DEAD
4492 note. Otherwise, we must make partial REG_DEAD
4495 create_reg_dead_note (x, insn);
4500 /* Don't make a REG_DEAD note for a part of a
4501 register that is set in the insn. */
4502 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
4504 if (! REGNO_REG_SET_P (old_live_regs, regno+i)
4505 && ! dead_or_set_regno_p (insn, regno + i))
4506 create_reg_dead_note (gen_rtx_REG (reg_raw_mode[regno + i],
4513 if (regno < FIRST_PSEUDO_REGISTER)
4515 int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
4518 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4523 /* Recompute REG_BASIC_BLOCK as we update all the other
4524 dataflow information. */
4525 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
4526 sched_reg_basic_block[regno] = current_block_num;
4527 else if (sched_reg_basic_block[regno] != current_block_num)
4528 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
4530 SET_REGNO_REG_SET (bb_live_regs, regno);
4537 /* Handle tail-recursive case. */
4538 attach_deaths (XEXP (x, 0), insn, 0);
4542 attach_deaths (SUBREG_REG (x), insn,
4543 set_p && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4545 || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4546 == GET_MODE_SIZE (GET_MODE ((x))))));
4549 case STRICT_LOW_PART:
4550 attach_deaths (XEXP (x, 0), insn, 0);
4555 attach_deaths (XEXP (x, 0), insn, 0);
4556 attach_deaths (XEXP (x, 1), insn, 0);
4557 attach_deaths (XEXP (x, 2), insn, 0);
4561 /* Other cases: walk the insn. */
4562 fmt = GET_RTX_FORMAT (code);
4563 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4566 attach_deaths (XEXP (x, i), insn, 0);
4567 else if (fmt[i] == 'E')
4568 for (j = 0; j < XVECLEN (x, i); j++)
4569 attach_deaths (XVECEXP (x, i, j), insn, 0);
4574 /* After INSN has executed, add register death notes for each register
4575 that is dead after INSN. */
4578 attach_deaths_insn (insn)
4581 rtx x = PATTERN (insn);
4582 register RTX_CODE code = GET_CODE (x);
4587 attach_deaths (SET_SRC (x), insn, 0);
4589 /* A register might die here even if it is the destination, e.g.
4590 it is the target of a volatile read and is otherwise unused.
4591 Hence we must always call attach_deaths for the SET_DEST. */
4592 attach_deaths (SET_DEST (x), insn, 1);
4594 else if (code == PARALLEL)
4597 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4599 code = GET_CODE (XVECEXP (x, 0, i));
4602 attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
4604 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
4606 /* Flow does not add REG_DEAD notes to registers that die in
4607 clobbers, so we can't either. */
4608 else if (code != CLOBBER)
4609 attach_deaths (XVECEXP (x, 0, i), insn, 0);
4612 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4613 MEM being clobbered, just like flow. */
4614 else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == MEM)
4615 attach_deaths (XEXP (XEXP (x, 0), 0), insn, 0);
4616 /* Otherwise don't add a death note to things being clobbered. */
4617 else if (code != CLOBBER)
4618 attach_deaths (x, insn, 0);
4620 /* Make death notes for things used in the called function. */
4621 if (GET_CODE (insn) == CALL_INSN)
4622 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
4623 attach_deaths (XEXP (XEXP (link, 0), 0), insn,
4624 GET_CODE (XEXP (link, 0)) == CLOBBER);
4627 /* functions for handlnig of notes */
4629 /* Delete notes beginning with INSN and put them in the chain
4630 of notes ended by NOTE_LIST.
4631 Returns the insn following the notes. */
4634 unlink_other_notes (insn, tail)
4637 rtx prev = PREV_INSN (insn);
4639 while (insn != tail && GET_CODE (insn) == NOTE)
4641 rtx next = NEXT_INSN (insn);
4642 /* Delete the note from its current position. */
4644 NEXT_INSN (prev) = next;
4646 PREV_INSN (next) = prev;
4648 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4649 immediately after the call they follow. We use a fake
4650 (REG_DEAD (const_int -1)) note to remember them.
4651 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4652 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
4653 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
4654 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
4655 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
4656 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
4658 /* Insert the note at the end of the notes list. */
4659 PREV_INSN (insn) = note_list;
4661 NEXT_INSN (note_list) = insn;
4670 /* Delete line notes beginning with INSN. Record line-number notes so
4671 they can be reused. Returns the insn following the notes. */
4674 unlink_line_notes (insn, tail)
4677 rtx prev = PREV_INSN (insn);
4679 while (insn != tail && GET_CODE (insn) == NOTE)
4681 rtx next = NEXT_INSN (insn);
4683 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
4685 /* Delete the note from its current position. */
4687 NEXT_INSN (prev) = next;
4689 PREV_INSN (next) = prev;
4691 /* Record line-number notes so they can be reused. */
4692 LINE_NOTE (insn) = insn;
4702 /* Return the head and tail pointers of BB. */
4704 __inline static void
4705 get_block_head_tail (bb, headp, tailp)
4715 b = BB_TO_BLOCK (bb);
4717 /* HEAD and TAIL delimit the basic block being scheduled. */
4718 head = basic_block_head[b];
4719 tail = basic_block_end[b];
4721 /* Don't include any notes or labels at the beginning of the
4722 basic block, or notes at the ends of basic blocks. */
4723 while (head != tail)
4725 if (GET_CODE (head) == NOTE)
4726 head = NEXT_INSN (head);
4727 else if (GET_CODE (tail) == NOTE)
4728 tail = PREV_INSN (tail);
4729 else if (GET_CODE (head) == CODE_LABEL)
4730 head = NEXT_INSN (head);
4739 /* Delete line notes from bb. Save them so they can be later restored
4740 (in restore_line_notes ()). */
4751 get_block_head_tail (bb, &head, &tail);
4754 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4757 next_tail = NEXT_INSN (tail);
4758 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4762 /* Farm out notes, and maybe save them in NOTE_LIST.
4763 This is needed to keep the debugger from
4764 getting completely deranged. */
4765 if (GET_CODE (insn) == NOTE)
4768 insn = unlink_line_notes (insn, next_tail);
4774 if (insn == next_tail)
4780 /* Save line number notes for each insn in bb. */
4783 save_line_notes (bb)
4789 /* We must use the true line number for the first insn in the block
4790 that was computed and saved at the start of this pass. We can't
4791 use the current line number, because scheduling of the previous
4792 block may have changed the current line number. */
4794 rtx line = line_note_head[BB_TO_BLOCK (bb)];
4797 get_block_head_tail (bb, &head, &tail);
4798 next_tail = NEXT_INSN (tail);
4800 for (insn = basic_block_head[BB_TO_BLOCK (bb)];
4802 insn = NEXT_INSN (insn))
4803 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4806 LINE_NOTE (insn) = line;
4810 /* After bb was scheduled, insert line notes into the insns list. */
4813 restore_line_notes (bb)
4816 rtx line, note, prev, new;
4817 int added_notes = 0;
4819 rtx head, next_tail, insn;
4821 b = BB_TO_BLOCK (bb);
4823 head = basic_block_head[b];
4824 next_tail = NEXT_INSN (basic_block_end[b]);
4826 /* Determine the current line-number. We want to know the current
4827 line number of the first insn of the block here, in case it is
4828 different from the true line number that was saved earlier. If
4829 different, then we need a line number note before the first insn
4830 of this block. If it happens to be the same, then we don't want to
4831 emit another line number note here. */
4832 for (line = head; line; line = PREV_INSN (line))
4833 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4836 /* Walk the insns keeping track of the current line-number and inserting
4837 the line-number notes as needed. */
4838 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4839 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4841 /* This used to emit line number notes before every non-deleted note.
4842 However, this confuses a debugger, because line notes not separated
4843 by real instructions all end up at the same address. I can find no
4844 use for line number notes before other notes, so none are emitted. */
4845 else if (GET_CODE (insn) != NOTE
4846 && (note = LINE_NOTE (insn)) != 0
4849 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
4850 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
4853 prev = PREV_INSN (insn);
4854 if (LINE_NOTE (note))
4856 /* Re-use the original line-number note. */
4857 LINE_NOTE (note) = 0;
4858 PREV_INSN (note) = prev;
4859 NEXT_INSN (prev) = note;
4860 PREV_INSN (insn) = note;
4861 NEXT_INSN (note) = insn;
4866 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
4867 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
4868 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
4871 if (sched_verbose && added_notes)
4872 fprintf (dump, ";; added %d line-number notes\n", added_notes);
4875 /* After scheduling the function, delete redundant line notes from the
4879 rm_redundant_line_notes ()
4882 rtx insn = get_insns ();
4883 int active_insn = 0;
4886 /* Walk the insns deleting redundant line-number notes. Many of these
4887 are already present. The remainder tend to occur at basic
4888 block boundaries. */
4889 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4890 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4892 /* If there are no active insns following, INSN is redundant. */
4893 if (active_insn == 0)
4896 NOTE_SOURCE_FILE (insn) = 0;
4897 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4899 /* If the line number is unchanged, LINE is redundant. */
4901 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
4902 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
4905 NOTE_SOURCE_FILE (line) = 0;
4906 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
4913 else if (!((GET_CODE (insn) == NOTE
4914 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
4915 || (GET_CODE (insn) == INSN
4916 && (GET_CODE (PATTERN (insn)) == USE
4917 || GET_CODE (PATTERN (insn)) == CLOBBER))))
4920 if (sched_verbose && notes)
4921 fprintf (dump, ";; deleted %d line-number notes\n", notes);
4924 /* Delete notes between head and tail and put them in the chain
4925 of notes ended by NOTE_LIST. */
4928 rm_other_notes (head, tail)
4936 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4939 next_tail = NEXT_INSN (tail);
4940 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4944 /* Farm out notes, and maybe save them in NOTE_LIST.
4945 This is needed to keep the debugger from
4946 getting completely deranged. */
4947 if (GET_CODE (insn) == NOTE)
4951 insn = unlink_other_notes (insn, next_tail);
4957 if (insn == next_tail)
4963 /* Constructor for `sometimes' data structure. */
4966 new_sometimes_live (regs_sometimes_live, regno, sometimes_max)
4967 struct sometimes *regs_sometimes_live;
4971 register struct sometimes *p;
4973 /* There should never be a register greater than max_regno here. If there
4974 is, it means that a define_split has created a new pseudo reg. This
4975 is not allowed, since there will not be flow info available for any
4976 new register, so catch the error here. */
4977 if (regno >= max_regno)
4980 p = ®s_sometimes_live[sometimes_max];
4983 p->calls_crossed = 0;
4985 return sometimes_max;
4988 /* Count lengths of all regs we are currently tracking,
4989 and find new registers no longer live. */
4992 finish_sometimes_live (regs_sometimes_live, sometimes_max)
4993 struct sometimes *regs_sometimes_live;
4998 for (i = 0; i < sometimes_max; i++)
5000 register struct sometimes *p = ®s_sometimes_live[i];
5001 int regno = p->regno;
5003 sched_reg_live_length[regno] += p->live_length;
5004 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5008 /* functions for computation of registers live/usage info */
5010 /* It is assumed that prior to scheduling basic_block_live_at_start (b)
5011 contains the registers that are alive at the entry to b.
5013 Two passes follow: The first pass is performed before the scheduling
5014 of a region. It scans each block of the region forward, computing
5015 the set of registers alive at the end of the basic block and
5016 discard REG_DEAD notes (done by find_pre_sched_live ()).
5018 The second path is invoked after scheduling all region blocks.
5019 It scans each block of the region backward, a block being traversed
5020 only after its succesors in the region. When the set of registers
5021 live at the end of a basic block may be changed by the scheduling
5022 (this may happen for multiple blocks region), it is computed as
5023 the union of the registers live at the start of its succesors.
5024 The last-use information is updated by inserting REG_DEAD notes.
5025 (done by find_post_sched_live ()) */
5027 /* Scan all the insns to be scheduled, removing register death notes.
5028 Register death notes end up in DEAD_NOTES.
5029 Recreate the register life information for the end of this basic
5033 find_pre_sched_live (bb)
5036 rtx insn, next_tail, head, tail;
5037 int b = BB_TO_BLOCK (bb);
5039 get_block_head_tail (bb, &head, &tail);
5040 COPY_REG_SET (bb_live_regs, basic_block_live_at_start[b]);
5041 next_tail = NEXT_INSN (tail);
5043 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5045 rtx prev, next, link;
5048 /* Handle register life information. */
5049 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
5051 /* See if the register gets born here. */
5052 /* We must check for registers being born before we check for
5053 registers dying. It is possible for a register to be born and
5054 die in the same insn, e.g. reading from a volatile memory
5055 location into an otherwise unused register. Such a register
5056 must be marked as dead after this insn. */
5057 if (GET_CODE (PATTERN (insn)) == SET
5058 || GET_CODE (PATTERN (insn)) == CLOBBER)
5060 sched_note_set (PATTERN (insn), 0);
5064 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5067 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5068 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5069 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5071 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5075 /* ??? This code is obsolete and should be deleted. It
5076 is harmless though, so we will leave it in for now. */
5077 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5078 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
5079 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5082 /* Each call cobbers (makes live) all call-clobbered regs
5083 that are not global or fixed. Note that the function-value
5084 reg is a call_clobbered reg. */
5085 if (GET_CODE (insn) == CALL_INSN)
5088 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
5089 if (call_used_regs[j] && !global_regs[j]
5092 SET_REGNO_REG_SET (bb_live_regs, j);
5096 /* Need to know what registers this insn kills. */
5097 for (prev = 0, link = REG_NOTES (insn); link; link = next)
5099 next = XEXP (link, 1);
5100 if ((REG_NOTE_KIND (link) == REG_DEAD
5101 || REG_NOTE_KIND (link) == REG_UNUSED)
5102 /* Verify that the REG_NOTE has a valid value. */
5103 && GET_CODE (XEXP (link, 0)) == REG)
5105 register int regno = REGNO (XEXP (link, 0));
5109 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5111 if (REG_NOTE_KIND (link) == REG_DEAD)
5114 XEXP (prev, 1) = next;
5116 REG_NOTES (insn) = next;
5117 XEXP (link, 1) = dead_notes;
5123 if (regno < FIRST_PSEUDO_REGISTER)
5125 int j = HARD_REGNO_NREGS (regno,
5126 GET_MODE (XEXP (link, 0)));
5129 CLEAR_REGNO_REG_SET (bb_live_regs, regno+j);
5134 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
5142 INSN_REG_WEIGHT (insn) = reg_weight;
5146 /* Update register life and usage information for block bb
5147 after scheduling. Put register dead notes back in the code. */
5150 find_post_sched_live (bb)
5157 rtx head, tail, prev_head, next_tail;
5159 register struct sometimes *regs_sometimes_live;
5161 b = BB_TO_BLOCK (bb);
5163 /* compute live regs at the end of bb as a function of its successors. */
5164 if (current_nr_blocks > 1)
5169 first_edge = e = OUT_EDGES (b);
5170 CLEAR_REG_SET (bb_live_regs);
5177 b_succ = TO_BLOCK (e);
5178 IOR_REG_SET (bb_live_regs, basic_block_live_at_start[b_succ]);
5181 while (e != first_edge);
5184 get_block_head_tail (bb, &head, &tail);
5185 next_tail = NEXT_INSN (tail);
5186 prev_head = PREV_INSN (head);
5188 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, i,
5190 sched_reg_basic_block[i] = REG_BLOCK_GLOBAL;
5193 /* if the block is empty, same regs are alive at its end and its start.
5194 since this is not guaranteed after interblock scheduling, make sure they
5195 are truly identical. */
5196 if (NEXT_INSN (prev_head) == tail
5197 && (GET_RTX_CLASS (GET_CODE (tail)) != 'i'))
5199 if (current_nr_blocks > 1)
5200 COPY_REG_SET (basic_block_live_at_start[b], bb_live_regs);
5205 b = BB_TO_BLOCK (bb);
5206 current_block_num = b;
5208 /* Keep track of register lives. */
5209 old_live_regs = ALLOCA_REG_SET ();
5211 = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
5214 /* initiate "sometimes" data, starting with registers live at end */
5216 COPY_REG_SET (old_live_regs, bb_live_regs);
5217 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, 0, j,
5220 = new_sometimes_live (regs_sometimes_live,
5224 /* scan insns back, computing regs live info */
5225 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
5227 /* First we kill registers set by this insn, and then we
5228 make registers used by this insn live. This is the opposite
5229 order used above because we are traversing the instructions
5232 /* Strictly speaking, we should scan REG_UNUSED notes and make
5233 every register mentioned there live, however, we will just
5234 kill them again immediately below, so there doesn't seem to
5235 be any reason why we bother to do this. */
5237 /* See if this is the last notice we must take of a register. */
5238 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5241 if (GET_CODE (PATTERN (insn)) == SET
5242 || GET_CODE (PATTERN (insn)) == CLOBBER)
5243 sched_note_set (PATTERN (insn), 1);
5244 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5246 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5247 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5248 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5249 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 1);
5252 /* This code keeps life analysis information up to date. */
5253 if (GET_CODE (insn) == CALL_INSN)
5255 register struct sometimes *p;
5257 /* A call kills all call used registers that are not
5258 global or fixed, except for those mentioned in the call
5259 pattern which will be made live again later. */
5260 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5261 if (call_used_regs[i] && ! global_regs[i]
5264 CLEAR_REGNO_REG_SET (bb_live_regs, i);
5267 /* Regs live at the time of a call instruction must not
5268 go in a register clobbered by calls. Record this for
5269 all regs now live. Note that insns which are born or
5270 die in a call do not cross a call, so this must be done
5271 after the killings (above) and before the births
5273 p = regs_sometimes_live;
5274 for (i = 0; i < sometimes_max; i++, p++)
5275 if (REGNO_REG_SET_P (bb_live_regs, p->regno))
5276 p->calls_crossed += 1;
5279 /* Make every register used live, and add REG_DEAD notes for
5280 registers which were not live before we started. */
5281 attach_deaths_insn (insn);
5283 /* Find registers now made live by that instruction. */
5284 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs, old_live_regs, 0, j,
5287 = new_sometimes_live (regs_sometimes_live,
5290 IOR_REG_SET (old_live_regs, bb_live_regs);
5292 /* Count lengths of all regs we are worrying about now,
5293 and handle registers no longer live. */
5295 for (i = 0; i < sometimes_max; i++)
5297 register struct sometimes *p = ®s_sometimes_live[i];
5298 int regno = p->regno;
5300 p->live_length += 1;
5302 if (!REGNO_REG_SET_P (bb_live_regs, regno))
5304 /* This is the end of one of this register's lifetime
5305 segments. Save the lifetime info collected so far,
5306 and clear its bit in the old_live_regs entry. */
5307 sched_reg_live_length[regno] += p->live_length;
5308 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5309 CLEAR_REGNO_REG_SET (old_live_regs, p->regno);
5311 /* Delete the reg_sometimes_live entry for this reg by
5312 copying the last entry over top of it. */
5313 *p = regs_sometimes_live[--sometimes_max];
5314 /* ...and decrement i so that this newly copied entry
5315 will be processed. */
5321 finish_sometimes_live (regs_sometimes_live, sometimes_max);
5323 /* In interblock scheduling, basic_block_live_at_start may have changed. */
5324 if (current_nr_blocks > 1)
5325 COPY_REG_SET (basic_block_live_at_start[b], bb_live_regs);
5328 FREE_REG_SET (old_live_regs);
5329 } /* find_post_sched_live */
5331 /* After scheduling the subroutine, restore information about uses of
5339 if (n_basic_blocks > 0)
5340 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, regno,
5342 sched_reg_basic_block[regno]
5346 for (regno = 0; regno < max_regno; regno++)
5347 if (sched_reg_live_length[regno])
5351 if (REG_LIVE_LENGTH (regno) > sched_reg_live_length[regno])
5353 ";; register %d life shortened from %d to %d\n",
5354 regno, REG_LIVE_LENGTH (regno),
5355 sched_reg_live_length[regno]);
5356 /* Negative values are special; don't overwrite the current
5357 reg_live_length value if it is negative. */
5358 else if (REG_LIVE_LENGTH (regno) < sched_reg_live_length[regno]
5359 && REG_LIVE_LENGTH (regno) >= 0)
5361 ";; register %d life extended from %d to %d\n",
5362 regno, REG_LIVE_LENGTH (regno),
5363 sched_reg_live_length[regno]);
5365 if (!REG_N_CALLS_CROSSED (regno)
5366 && sched_reg_n_calls_crossed[regno])
5368 ";; register %d now crosses calls\n", regno);
5369 else if (REG_N_CALLS_CROSSED (regno)
5370 && !sched_reg_n_calls_crossed[regno]
5371 && REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5373 ";; register %d no longer crosses calls\n", regno);
5375 if (REG_BASIC_BLOCK (regno) != sched_reg_basic_block[regno]
5376 && sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5377 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5379 ";; register %d changed basic block from %d to %d\n",
5380 regno, REG_BASIC_BLOCK(regno),
5381 sched_reg_basic_block[regno]);
5384 /* Negative values are special; don't overwrite the current
5385 reg_live_length value if it is negative. */
5386 if (REG_LIVE_LENGTH (regno) >= 0)
5387 REG_LIVE_LENGTH (regno) = sched_reg_live_length[regno];
5389 if (sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5390 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5391 REG_BASIC_BLOCK(regno) = sched_reg_basic_block[regno];
5393 /* We can't change the value of reg_n_calls_crossed to zero for
5394 pseudos which are live in more than one block.
5396 This is because combine might have made an optimization which
5397 invalidated basic_block_live_at_start and reg_n_calls_crossed,
5398 but it does not update them. If we update reg_n_calls_crossed
5399 here, the two variables are now inconsistent, and this might
5400 confuse the caller-save code into saving a register that doesn't
5401 need to be saved. This is only a problem when we zero calls
5402 crossed for a pseudo live in multiple basic blocks.
5404 Alternatively, we could try to correctly update basic block live
5405 at start here in sched, but that seems complicated.
5407 Note: it is possible that a global register became local, as result
5408 of interblock motion, but will remain marked as a global register. */
5409 if (sched_reg_n_calls_crossed[regno]
5410 || REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5411 REG_N_CALLS_CROSSED (regno) = sched_reg_n_calls_crossed[regno];
5416 /* Scheduling clock, modified in schedule_block() and queue_to_ready () */
5417 static int clock_var;
5419 /* Move insns that became ready to fire from queue to ready list. */
5422 queue_to_ready (ready, n_ready)
5429 q_ptr = NEXT_Q (q_ptr);
5431 /* Add all pending insns that can be scheduled without stalls to the
5433 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
5436 insn = XEXP (link, 0);
5439 if (sched_verbose >= 2)
5440 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5442 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5443 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5445 ready[n_ready++] = insn;
5446 if (sched_verbose >= 2)
5447 fprintf (dump, "moving to ready without stalls\n");
5449 insn_queue[q_ptr] = 0;
5451 /* If there are no ready insns, stall until one is ready and add all
5452 of the pending insns at that point to the ready list. */
5455 register int stalls;
5457 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
5459 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
5461 for (; link; link = XEXP (link, 1))
5463 insn = XEXP (link, 0);
5466 if (sched_verbose >= 2)
5467 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5469 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5470 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5472 ready[n_ready++] = insn;
5473 if (sched_verbose >= 2)
5474 fprintf (dump, "moving to ready with %d stalls\n", stalls);
5476 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
5483 if (sched_verbose && stalls)
5484 visualize_stall_cycles (BB_TO_BLOCK (target_bb), stalls);
5485 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
5486 clock_var += stalls;
5491 /* Print the ready list for debugging purposes. Callable from debugger. */
5494 debug_ready_list (ready, n_ready)
5500 for (i = 0; i < n_ready; i++)
5502 fprintf (dump, " %d", INSN_UID (ready[i]));
5503 if (current_nr_blocks > 1 && INSN_BB (ready[i]) != target_bb)
5504 fprintf (dump, "/b%d", INSN_BLOCK (ready[i]));
5506 fprintf (dump, "\n");
5509 /* Print names of units on which insn can/should execute, for debugging. */
5512 insn_print_units (insn)
5516 int unit = insn_unit (insn);
5519 fprintf (dump, "none");
5521 fprintf (dump, "%s", function_units[unit].name);
5524 fprintf (dump, "[");
5525 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
5528 fprintf (dump, "%s", function_units[i].name);
5530 fprintf (dump, " ");
5532 fprintf (dump, "]");
5536 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5537 of a basic block. If more lines are needed, table is splitted to two.
5538 n_visual_lines is the number of lines printed so far for a block.
5539 visual_tbl contains the block visualization info.
5540 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5541 #define MAX_VISUAL_LINES 100
5546 rtx vis_no_unit[10];
5548 /* Finds units that are in use in this fuction. Required only
5549 for visualization. */
5552 init_target_units ()
5557 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
5559 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5562 unit = insn_unit (insn);
5565 target_units |= ~unit;
5567 target_units |= (1 << unit);
5571 /* Return the length of the visualization table */
5574 get_visual_tbl_length ()
5580 /* compute length of one field in line */
5581 s = (char *) alloca (INSN_LEN + 5);
5582 sprintf (s, " %33s", "uname");
5585 /* compute length of one line */
5588 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5589 if (function_units[unit].bitmask & target_units)
5590 for (i = 0; i < function_units[unit].multiplicity; i++)
5593 n += strlen ("\n") + 2;
5595 /* compute length of visualization string */
5596 return (MAX_VISUAL_LINES * n);
5599 /* Init block visualization debugging info */
5602 init_block_visualization ()
5604 strcpy (visual_tbl, "");
5612 safe_concat (buf, cur, str)
5617 char *end = buf + BUF_LEN - 2; /* leave room for null */
5626 while (cur < end && (c = *str++) != '\0')
5633 /* This recognizes rtx, I classified as expressions. These are always */
5634 /* represent some action on values or results of other expression, */
5635 /* that may be stored in objects representing values. */
5638 print_exp (buf, x, verbose)
5646 char *fun = (char *)0;
5651 for (i = 0; i < 4; i++)
5657 switch (GET_CODE (x))
5660 op[0] = XEXP (x, 0);
5662 op[1] = XEXP (x, 1);
5665 op[0] = XEXP (x, 0);
5667 op[1] = XEXP (x, 1);
5671 op[0] = XEXP (x, 0);
5673 op[1] = XEXP (x, 1);
5677 op[0] = XEXP (x, 0);
5678 op[1] = XEXP (x, 1);
5682 op[0] = XEXP (x, 0);
5685 op[0] = XEXP (x, 0);
5687 op[1] = XEXP (x, 1);
5690 op[0] = XEXP (x, 0);
5692 op[1] = XEXP (x, 1);
5696 op[0] = XEXP (x, 0);
5697 op[1] = XEXP (x, 1);
5700 op[0] = XEXP (x, 0);
5702 op[1] = XEXP (x, 1);
5706 op[0] = XEXP (x, 0);
5707 op[1] = XEXP (x, 1);
5711 op[0] = XEXP (x, 0);
5712 op[1] = XEXP (x, 1);
5716 op[0] = XEXP (x, 0);
5717 op[1] = XEXP (x, 1);
5721 op[0] = XEXP (x, 0);
5722 op[1] = XEXP (x, 1);
5726 op[0] = XEXP (x, 0);
5727 op[1] = XEXP (x, 1);
5731 op[0] = XEXP (x, 0);
5734 op[0] = XEXP (x, 0);
5736 op[1] = XEXP (x, 1);
5739 op[0] = XEXP (x, 0);
5741 op[1] = XEXP (x, 1);
5744 op[0] = XEXP (x, 0);
5746 op[1] = XEXP (x, 1);
5749 op[0] = XEXP (x, 0);
5751 op[1] = XEXP (x, 1);
5754 op[0] = XEXP (x, 0);
5756 op[1] = XEXP (x, 1);
5759 op[0] = XEXP (x, 0);
5761 op[1] = XEXP (x, 1);
5764 op[0] = XEXP (x, 0);
5766 op[1] = XEXP (x, 1);
5769 op[0] = XEXP (x, 0);
5771 op[1] = XEXP (x, 1);
5775 op[0] = XEXP (x, 0);
5779 op[0] = XEXP (x, 0);
5783 op[0] = XEXP (x, 0);
5786 op[0] = XEXP (x, 0);
5788 op[1] = XEXP (x, 1);
5791 op[0] = XEXP (x, 0);
5793 op[1] = XEXP (x, 1);
5796 op[0] = XEXP (x, 0);
5798 op[1] = XEXP (x, 1);
5802 op[0] = XEXP (x, 0);
5803 op[1] = XEXP (x, 1);
5806 op[0] = XEXP (x, 0);
5808 op[1] = XEXP (x, 1);
5812 op[0] = XEXP (x, 0);
5813 op[1] = XEXP (x, 1);
5816 op[0] = XEXP (x, 0);
5818 op[1] = XEXP (x, 1);
5822 op[0] = XEXP (x, 0);
5823 op[1] = XEXP (x, 1);
5826 op[0] = XEXP (x, 0);
5828 op[1] = XEXP (x, 1);
5832 op[0] = XEXP (x, 0);
5833 op[1] = XEXP (x, 1);
5836 fun = (verbose) ? "sign_extract" : "sxt";
5837 op[0] = XEXP (x, 0);
5838 op[1] = XEXP (x, 1);
5839 op[2] = XEXP (x, 2);
5842 fun = (verbose) ? "zero_extract" : "zxt";
5843 op[0] = XEXP (x, 0);
5844 op[1] = XEXP (x, 1);
5845 op[2] = XEXP (x, 2);
5848 fun = (verbose) ? "sign_extend" : "sxn";
5849 op[0] = XEXP (x, 0);
5852 fun = (verbose) ? "zero_extend" : "zxn";
5853 op[0] = XEXP (x, 0);
5856 fun = (verbose) ? "float_extend" : "fxn";
5857 op[0] = XEXP (x, 0);
5860 fun = (verbose) ? "trunc" : "trn";
5861 op[0] = XEXP (x, 0);
5863 case FLOAT_TRUNCATE:
5864 fun = (verbose) ? "float_trunc" : "ftr";
5865 op[0] = XEXP (x, 0);
5868 fun = (verbose) ? "float" : "flt";
5869 op[0] = XEXP (x, 0);
5871 case UNSIGNED_FLOAT:
5872 fun = (verbose) ? "uns_float" : "ufl";
5873 op[0] = XEXP (x, 0);
5877 op[0] = XEXP (x, 0);
5880 fun = (verbose) ? "uns_fix" : "ufx";
5881 op[0] = XEXP (x, 0);
5885 op[0] = XEXP (x, 0);
5889 op[0] = XEXP (x, 0);
5892 op[0] = XEXP (x, 0);
5896 op[0] = XEXP (x, 0);
5901 op[0] = XEXP (x, 0);
5905 op[1] = XEXP (x, 1);
5910 op[0] = XEXP (x, 0);
5912 op[1] = XEXP (x, 1);
5914 op[2] = XEXP (x, 2);
5919 op[0] = TRAP_CONDITION (x);
5922 case UNSPEC_VOLATILE:
5924 cur = safe_concat (buf, cur, "unspec");
5925 if (GET_CODE (x) == UNSPEC_VOLATILE)
5926 cur = safe_concat (buf, cur, "/v");
5927 cur = safe_concat (buf, cur, "[");
5929 for (i = 0; i < XVECLEN (x, 0); i++)
5931 print_pattern (tmp, XVECEXP (x, 0, i), verbose);
5932 cur = safe_concat (buf, cur, sep);
5933 cur = safe_concat (buf, cur, tmp);
5936 cur = safe_concat (buf, cur, "] ");
5937 sprintf (tmp, "%d", XINT (x, 1));
5938 cur = safe_concat (buf, cur, tmp);
5942 /* if (verbose) debug_rtx (x); */
5943 st[0] = GET_RTX_NAME (x);
5947 /* Print this as a function? */
5950 cur = safe_concat (buf, cur, fun);
5951 cur = safe_concat (buf, cur, "(");
5954 for (i = 0; i < 4; i++)
5957 cur = safe_concat (buf, cur, st[i]);
5962 cur = safe_concat (buf, cur, ",");
5964 print_value (tmp, op[i], verbose);
5965 cur = safe_concat (buf, cur, tmp);
5970 cur = safe_concat (buf, cur, ")");
5973 /* Prints rtxes, i customly classified as values. They're constants, */
5974 /* registers, labels, symbols and memory accesses. */
5977 print_value (buf, x, verbose)
5985 switch (GET_CODE (x))
5988 sprintf (t, "0x%lx", (long)INTVAL (x));
5989 cur = safe_concat (buf, cur, t);
5992 sprintf (t, "<0x%lx,0x%lx>", (long)XWINT (x, 2), (long)XWINT (x, 3));
5993 cur = safe_concat (buf, cur, t);
5996 cur = safe_concat (buf, cur, "\"");
5997 cur = safe_concat (buf, cur, XSTR (x, 0));
5998 cur = safe_concat (buf, cur, "\"");
6001 cur = safe_concat (buf, cur, "`");
6002 cur = safe_concat (buf, cur, XSTR (x, 0));
6003 cur = safe_concat (buf, cur, "'");
6006 sprintf (t, "L%d", INSN_UID (XEXP (x, 0)));
6007 cur = safe_concat (buf, cur, t);
6010 print_value (t, XEXP (x, 0), verbose);
6011 cur = safe_concat (buf, cur, "const(");
6012 cur = safe_concat (buf, cur, t);
6013 cur = safe_concat (buf, cur, ")");
6016 print_value (t, XEXP (x, 0), verbose);
6017 cur = safe_concat (buf, cur, "high(");
6018 cur = safe_concat (buf, cur, t);
6019 cur = safe_concat (buf, cur, ")");
6022 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
6024 int c = reg_names[ REGNO (x) ][0];
6025 if (c >= '0' && c <= '9')
6026 cur = safe_concat (buf, cur, "%");
6028 cur = safe_concat (buf, cur, reg_names[ REGNO (x) ]);
6032 sprintf (t, "r%d", REGNO (x));
6033 cur = safe_concat (buf, cur, t);
6037 print_value (t, SUBREG_REG (x), verbose);
6038 cur = safe_concat (buf, cur, t);
6039 sprintf (t, "#%d", SUBREG_WORD (x));
6040 cur = safe_concat (buf, cur, t);
6043 cur = safe_concat (buf, cur, "scratch");
6046 cur = safe_concat (buf, cur, "cc0");
6049 cur = safe_concat (buf, cur, "pc");
6052 print_value (t, XEXP (x, 0), verbose);
6053 cur = safe_concat (buf, cur, "[");
6054 cur = safe_concat (buf, cur, t);
6055 cur = safe_concat (buf, cur, "]");
6058 print_exp (t, x, verbose);
6059 cur = safe_concat (buf, cur, t);
6064 /* The next step in insn detalization, its pattern recognition */
6067 print_pattern (buf, x, verbose)
6072 char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
6074 switch (GET_CODE (x))
6077 print_value (t1, SET_DEST (x), verbose);
6078 print_value (t2, SET_SRC (x), verbose);
6079 sprintf (buf, "%s=%s", t1, t2);
6082 sprintf (buf, "return");
6085 print_exp (buf, x, verbose);
6088 print_value (t1, XEXP (x, 0), verbose);
6089 sprintf (buf, "clobber %s", t1);
6092 print_value (t1, XEXP (x, 0), verbose);
6093 sprintf (buf, "use %s", t1);
6100 for (i = 0; i < XVECLEN (x, 0); i++)
6102 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6103 sprintf (t3, "%s%s;", t1, t2);
6106 sprintf (buf, "%s}", t1);
6113 sprintf (t1, "%%{");
6114 for (i = 0; i < XVECLEN (x, 0); i++)
6116 print_insn (t2, XVECEXP (x, 0, i), verbose);
6117 sprintf (t3, "%s%s;", t1, t2);
6120 sprintf (buf, "%s%%}", t1);
6124 sprintf (buf, "asm {%s}", XSTR (x, 0));
6129 print_value (buf, XEXP (x, 0), verbose);
6132 print_value (t1, TRAP_CONDITION (x), verbose);
6133 sprintf (buf, "trap_if %s", t1);
6139 sprintf (t1, "unspec{");
6140 for (i = 0; i < XVECLEN (x, 0); i++)
6142 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6143 sprintf (t3, "%s%s;", t1, t2);
6146 sprintf (buf, "%s}", t1);
6149 case UNSPEC_VOLATILE:
6153 sprintf (t1, "unspec/v{");
6154 for (i = 0; i < XVECLEN (x, 0); i++)
6156 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6157 sprintf (t3, "%s%s;", t1, t2);
6160 sprintf (buf, "%s}", t1);
6164 print_value (buf, x, verbose);
6166 } /* print_pattern */
6168 /* This is the main function in rtl visualization mechanism. It
6169 accepts an rtx and tries to recognize it as an insn, then prints it
6170 properly in human readable form, resembling assembler mnemonics. */
6171 /* For every insn it prints its UID and BB the insn belongs */
6172 /* too. (probably the last "option" should be extended somehow, since */
6173 /* it depends now on sched.c inner variables ...) */
6176 print_insn (buf, x, verbose)
6184 switch (GET_CODE (x))
6187 print_pattern (t, PATTERN (x), verbose);
6189 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (x),
6192 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6195 print_pattern (t, PATTERN (x), verbose);
6197 sprintf (buf, "b%d: i% 4d: jump %s", INSN_BB (x),
6200 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6204 if (GET_CODE (x) == PARALLEL)
6206 x = XVECEXP (x, 0, 0);
6207 print_pattern (t, x, verbose);
6210 strcpy (t, "call <...>");
6212 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (insn),
6213 INSN_UID (insn), t);
6215 sprintf (buf, "%-4d %s", INSN_UID (insn), t);
6218 sprintf (buf, "L%d:", INSN_UID (x));
6221 sprintf (buf, "i% 4d: barrier", INSN_UID (x));
6224 if (NOTE_LINE_NUMBER (x) > 0)
6225 sprintf (buf, "%4d note \"%s\" %d", INSN_UID (x),
6226 NOTE_SOURCE_FILE (x), NOTE_LINE_NUMBER (x));
6228 sprintf (buf, "%4d %s", INSN_UID (x),
6229 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x)));
6234 sprintf (buf, "Not an INSN at all\n");
6238 sprintf (buf, "i%-4d <What?>", INSN_UID (x));
6243 print_insn_chain (rtx_first)
6246 register rtx tmp_rtx;
6249 strcpy (str, "(nil)\n");
6251 switch (GET_CODE (rtx_first))
6259 for (tmp_rtx = rtx_first; tmp_rtx != NULL;
6260 tmp_rtx = NEXT_INSN (tmp_rtx))
6262 print_insn (str, tmp_rtx, 0);
6263 printf ("%s\n", str);
6267 print_insn (str, rtx_first, 0);
6268 printf ("%s\n", str);
6270 } /* print_insn_chain */
6272 /* Print visualization debugging info */
6275 print_block_visualization (b, s)
6282 fprintf (dump, "\n;; ==================== scheduling visualization for block %d %s \n", b, s);
6284 /* Print names of units */
6285 fprintf (dump, ";; %-8s", "clock");
6286 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6287 if (function_units[unit].bitmask & target_units)
6288 for (i = 0; i < function_units[unit].multiplicity; i++)
6289 fprintf (dump, " %-33s", function_units[unit].name);
6290 fprintf (dump, " %-8s\n", "no-unit");
6292 fprintf (dump, ";; %-8s", "=====");
6293 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6294 if (function_units[unit].bitmask & target_units)
6295 for (i = 0; i < function_units[unit].multiplicity; i++)
6296 fprintf (dump, " %-33s", "==============================");
6297 fprintf (dump, " %-8s\n", "=======");
6299 /* Print insns in each cycle */
6300 fprintf (dump, "%s\n", visual_tbl);
6303 /* Print insns in the 'no_unit' column of visualization */
6306 visualize_no_unit (insn)
6309 vis_no_unit[n_vis_no_unit] = insn;
6313 /* Print insns scheduled in clock, for visualization. */
6316 visualize_scheduled_insns (b, clock)
6321 /* if no more room, split table into two */
6322 if (n_visual_lines >= MAX_VISUAL_LINES)
6324 print_block_visualization (b, "(incomplete)");
6325 init_block_visualization ();
6330 sprintf (visual_tbl + strlen (visual_tbl), ";; %-8d", clock);
6331 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6332 if (function_units[unit].bitmask & target_units)
6333 for (i = 0; i < function_units[unit].multiplicity; i++)
6335 int instance = unit + i * FUNCTION_UNITS_SIZE;
6336 rtx insn = unit_last_insn[instance];
6338 /* print insns that still keep the unit busy */
6340 actual_hazard_this_instance (unit, instance, insn, clock, 0))
6343 print_insn (str, insn, 0);
6344 str[INSN_LEN] = '\0';
6345 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", str);
6348 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", "------------------------------");
6351 /* print insns that are not assigned to any unit */
6352 for (i = 0; i < n_vis_no_unit; i++)
6353 sprintf (visual_tbl + strlen (visual_tbl), " %-8d",
6354 INSN_UID (vis_no_unit[i]));
6357 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6360 /* Print stalled cycles */
6363 visualize_stall_cycles (b, stalls)
6368 /* if no more room, split table into two */
6369 if (n_visual_lines >= MAX_VISUAL_LINES)
6371 print_block_visualization (b, "(incomplete)");
6372 init_block_visualization ();
6377 sprintf (visual_tbl + strlen (visual_tbl), ";; ");
6378 for (i = 0; i < stalls; i++)
6379 sprintf (visual_tbl + strlen (visual_tbl), ".");
6380 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6383 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn */
6386 move_insn1 (insn, last)
6389 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
6390 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
6392 NEXT_INSN (insn) = NEXT_INSN (last);
6393 PREV_INSN (NEXT_INSN (last)) = insn;
6395 NEXT_INSN (last) = insn;
6396 PREV_INSN (insn) = last;
6401 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
6402 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
6403 NOTEs. The REG_DEAD note following first one is contains the saved
6404 value for NOTE_BLOCK_NUMBER which is useful for
6405 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
6406 output by the instruction scheduler. Return the new value of LAST. */
6409 reemit_notes (insn, last)
6416 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
6418 if (REG_NOTE_KIND (note) == REG_DEAD
6419 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6421 if (INTVAL (XEXP (note, 0)) == NOTE_INSN_SETJMP)
6423 retval = emit_note_after (INTVAL (XEXP (note, 0)), insn);
6424 CONST_CALL_P (retval) = CONST_CALL_P (note);
6425 remove_note (insn, note);
6426 note = XEXP (note, 1);
6430 last = emit_note_before (INTVAL (XEXP (note, 0)), last);
6431 remove_note (insn, note);
6432 note = XEXP (note, 1);
6433 NOTE_BLOCK_NUMBER (last) = INTVAL (XEXP (note, 0));
6435 remove_note (insn, note);
6441 /* Move INSN, and all insns which should be issued before it,
6442 due to SCHED_GROUP_P flag. Reemit notes if needed.
6444 Return the last insn emitted by the scheduler, which is the
6445 return value from the first call to reemit_notes. */
6448 move_insn (insn, last)
6453 /* If INSN has SCHED_GROUP_P set, then issue it and any other
6454 insns with SCHED_GROUP_P set first. */
6455 while (SCHED_GROUP_P (insn))
6457 rtx prev = PREV_INSN (insn);
6459 /* Move a SCHED_GROUP_P insn. */
6460 move_insn1 (insn, last);
6461 /* If this is the first call to reemit_notes, then record
6462 its return value. */
6463 if (retval == NULL_RTX)
6464 retval = reemit_notes (insn, insn);
6466 reemit_notes (insn, insn);
6470 /* Now move the first non SCHED_GROUP_P insn. */
6471 move_insn1 (insn, last);
6473 /* If this is the first call to reemit_notes, then record
6474 its return value. */
6475 if (retval == NULL_RTX)
6476 retval = reemit_notes (insn, insn);
6478 reemit_notes (insn, insn);
6483 /* Return an insn which represents a SCHED_GROUP, which is
6484 the last insn in the group. */
6495 insn = next_nonnote_insn (insn);
6497 while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
6502 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
6503 possibly bringing insns from subsequent blocks in the same region.
6504 Return number of insns scheduled. */
6507 schedule_block (bb, rgn_n_insns)
6511 /* Local variables. */
6518 /* flow block of this bb */
6519 int b = BB_TO_BLOCK (bb);
6521 /* target_n_insns == number of insns in b before scheduling starts.
6522 sched_target_n_insns == how many of b's insns were scheduled.
6523 sched_n_insns == how many insns were scheduled in b */
6524 int target_n_insns = 0;
6525 int sched_target_n_insns = 0;
6526 int sched_n_insns = 0;
6528 #define NEED_NOTHING 0
6533 /* head/tail info for this block */
6540 /* We used to have code to avoid getting parameters moved from hard
6541 argument registers into pseudos.
6543 However, it was removed when it proved to be of marginal benefit
6544 and caused problems because schedule_block and compute_forward_dependences
6545 had different notions of what the "head" insn was. */
6546 get_block_head_tail (bb, &head, &tail);
6548 /* Interblock scheduling could have moved the original head insn from this
6549 block into a proceeding block. This may also cause schedule_block and
6550 compute_forward_dependences to have different notions of what the
6553 If the interblock movement happened to make this block start with
6554 some notes (LOOP, EH or SETJMP) before the first real insn, then
6555 HEAD will have various special notes attached to it which must be
6556 removed so that we don't end up with extra copies of the notes. */
6557 if (GET_RTX_CLASS (GET_CODE (head)) == 'i')
6561 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
6562 if (REG_NOTE_KIND (note) == REG_DEAD
6563 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6564 remove_note (head, note);
6567 next_tail = NEXT_INSN (tail);
6568 prev_head = PREV_INSN (head);
6570 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6571 to schedule this block. */
6573 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6574 return (sched_n_insns);
6579 fprintf (dump, ";; ======================================================\n");
6581 ";; -- basic block %d from %d to %d -- %s reload\n",
6582 b, INSN_UID (basic_block_head[b]),
6583 INSN_UID (basic_block_end[b]),
6584 (reload_completed ? "after" : "before"));
6585 fprintf (dump, ";; ======================================================\n");
6586 fprintf (dump, "\n");
6588 visual_tbl = (char *) alloca (get_visual_tbl_length ());
6589 init_block_visualization ();
6592 /* remove remaining note insns from the block, save them in
6593 note_list. These notes are restored at the end of
6594 schedule_block (). */
6596 rm_other_notes (head, tail);
6600 /* prepare current target block info */
6601 if (current_nr_blocks > 1)
6603 candidate_table = (candidate *) alloca (current_nr_blocks * sizeof (candidate));
6606 /* ??? It is not clear why bblst_size is computed this way. The original
6607 number was clearly too small as it resulted in compiler failures.
6608 Multiplying by the original number by 2 (to account for update_bbs
6609 members) seems to be a reasonable solution. */
6610 /* ??? Or perhaps there is a bug somewhere else in this file? */
6611 bblst_size = (current_nr_blocks - bb) * rgn_nr_edges * 2;
6612 bblst_table = (int *) alloca (bblst_size * sizeof (int));
6614 bitlst_table_last = 0;
6615 bitlst_table_size = rgn_nr_edges;
6616 bitlst_table = (int *) alloca (rgn_nr_edges * sizeof (int));
6618 compute_trg_info (bb);
6623 /* Allocate the ready list */
6624 ready = (rtx *) alloca ((rgn_n_insns + 1) * sizeof (rtx));
6626 /* Print debugging information. */
6627 if (sched_verbose >= 5)
6628 debug_dependencies ();
6631 /* Initialize ready list with all 'ready' insns in target block.
6632 Count number of insns in the target block being scheduled. */
6634 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6638 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6640 next = NEXT_INSN (insn);
6642 if (INSN_DEP_COUNT (insn) == 0
6643 && (SCHED_GROUP_P (next) == 0 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6644 ready[n_ready++] = insn;
6645 if (!(SCHED_GROUP_P (insn)))
6649 /* Add to ready list all 'ready' insns in valid source blocks.
6650 For speculative insns, check-live, exception-free, and
6652 for (bb_src = bb + 1; bb_src < current_nr_blocks; bb_src++)
6653 if (IS_VALID (bb_src))
6659 get_block_head_tail (bb_src, &head, &tail);
6660 src_next_tail = NEXT_INSN (tail);
6664 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6667 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
6669 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6672 if (!CANT_MOVE (insn)
6673 && (!IS_SPECULATIVE_INSN (insn)
6674 || (insn_issue_delay (insn) <= 3
6675 && check_live (insn, bb_src)
6676 && is_exception_free (insn, bb_src, target_bb))))
6681 next = NEXT_INSN (insn);
6682 if (INSN_DEP_COUNT (insn) == 0
6683 && (SCHED_GROUP_P (next) == 0
6684 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6685 ready[n_ready++] = insn;
6690 /* no insns scheduled in this block yet */
6691 last_scheduled_insn = 0;
6693 /* Sort the ready list */
6694 SCHED_SORT (ready, n_ready);
6696 if (sched_verbose >= 2)
6698 fprintf (dump, ";;\t\tReady list initially: ");
6699 debug_ready_list (ready, n_ready);
6702 /* Q_SIZE is the total number of insns in the queue. */
6706 bzero ((char *) insn_queue, sizeof (insn_queue));
6708 /* We start inserting insns after PREV_HEAD. */
6711 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6712 new_needs = (NEXT_INSN (prev_head) == basic_block_head[b]
6713 ? NEED_HEAD : NEED_NOTHING);
6714 if (PREV_INSN (next_tail) == basic_block_end[b])
6715 new_needs |= NEED_TAIL;
6717 /* loop until all the insns in BB are scheduled. */
6718 while (sched_target_n_insns < target_n_insns)
6724 /* Add to the ready list all pending insns that can be issued now.
6725 If there are no ready insns, increment clock until one
6726 is ready and add all pending insns at that point to the ready
6728 n_ready = queue_to_ready (ready, n_ready);
6733 if (sched_verbose >= 2)
6735 fprintf (dump, ";;\t\tReady list after queue_to_ready: ");
6736 debug_ready_list (ready, n_ready);
6739 /* Sort the ready list. */
6740 SCHED_SORT (ready, n_ready);
6744 fprintf (dump, ";;\tReady list (t =%3d): ", clock_var);
6745 debug_ready_list (ready, n_ready);
6748 /* Issue insns from ready list.
6749 It is important to count down from n_ready, because n_ready may change
6750 as insns are issued. */
6751 can_issue_more = issue_rate;
6752 for (i = n_ready - 1; i >= 0 && can_issue_more; i--)
6754 rtx insn = ready[i];
6755 int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
6759 queue_insn (insn, cost);
6760 ready[i] = ready[--n_ready]; /* remove insn from ready list */
6764 /* an interblock motion? */
6765 if (INSN_BB (insn) != target_bb)
6769 if (IS_SPECULATIVE_INSN (insn))
6772 if (!check_live (insn, INSN_BB (insn)))
6774 /* speculative motion, live check failed, remove
6775 insn from ready list */
6776 ready[i] = ready[--n_ready];
6779 update_live (insn, INSN_BB (insn));
6781 /* for speculative load, mark insns fed by it. */
6782 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
6783 set_spec_fed (insn);
6790 while (SCHED_GROUP_P (temp))
6791 temp = PREV_INSN (temp);
6793 /* Update source block boundaries. */
6794 b1 = INSN_BLOCK (temp);
6795 if (temp == basic_block_head[b1]
6796 && insn == basic_block_end[b1])
6798 /* We moved all the insns in the basic block.
6799 Emit a note after the last insn and update the
6800 begin/end boundaries to point to the note. */
6801 emit_note_after (NOTE_INSN_DELETED, insn);
6802 basic_block_end[b1] = NEXT_INSN (insn);
6803 basic_block_head[b1] = NEXT_INSN (insn);
6805 else if (insn == basic_block_end[b1])
6807 /* We took insns from the end of the basic block,
6808 so update the end of block boundary so that it
6809 points to the first insn we did not move. */
6810 basic_block_end[b1] = PREV_INSN (temp);
6812 else if (temp == basic_block_head[b1])
6814 /* We took insns from the start of the basic block,
6815 so update the start of block boundary so that
6816 it points to the first insn we did not move. */
6817 basic_block_head[b1] = NEXT_INSN (insn);
6822 /* in block motion */
6823 sched_target_n_insns++;
6826 last_scheduled_insn = insn;
6827 last = move_insn (insn, last);
6832 n_ready = schedule_insn (insn, ready, n_ready, clock_var);
6834 /* remove insn from ready list */
6835 ready[i] = ready[--n_ready];
6837 /* close this block after scheduling its jump */
6838 if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
6846 visualize_scheduled_insns (b, clock_var);
6853 fprintf (dump, ";;\tReady list (final): ");
6854 debug_ready_list (ready, n_ready);
6855 print_block_visualization (b, "");
6858 /* Sanity check -- queue must be empty now. Meaningless if region has
6860 if (current_nr_blocks > 1)
6861 if (!flag_schedule_interblock && q_size != 0)
6864 /* update head/tail boundaries. */
6865 head = NEXT_INSN (prev_head);
6868 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6869 previously found among the insns. Insert them at the beginning
6873 rtx note_head = note_list;
6875 while (PREV_INSN (note_head))
6877 note_head = PREV_INSN (note_head);
6880 PREV_INSN (note_head) = PREV_INSN (head);
6881 NEXT_INSN (PREV_INSN (head)) = note_head;
6882 PREV_INSN (head) = note_list;
6883 NEXT_INSN (note_list) = head;
6887 /* update target block boundaries. */
6888 if (new_needs & NEED_HEAD)
6889 basic_block_head[b] = head;
6891 if (new_needs & NEED_TAIL)
6892 basic_block_end[b] = tail;
6897 fprintf (dump, ";; total time = %d\n;; new basic block head = %d\n",
6898 clock_var, INSN_UID (basic_block_head[b]));
6899 fprintf (dump, ";; new basic block end = %d\n\n",
6900 INSN_UID (basic_block_end[b]));
6903 return (sched_n_insns);
6904 } /* schedule_block () */
6907 /* print the bit-set of registers, S. callable from debugger */
6910 debug_reg_vector (s)
6915 EXECUTE_IF_SET_IN_REG_SET (s, 0, regno,
6917 fprintf (dump, " %d", regno);
6920 fprintf (dump, "\n");
6923 /* Use the backward dependences from LOG_LINKS to build
6924 forward dependences in INSN_DEPEND. */
6927 compute_block_forward_dependences (bb)
6933 enum reg_note dep_type;
6935 get_block_head_tail (bb, &head, &tail);
6936 next_tail = NEXT_INSN (tail);
6937 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6939 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6942 insn = group_leader (insn);
6944 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
6946 rtx x = group_leader (XEXP (link, 0));
6949 if (x != XEXP (link, 0))
6952 /* Ignore dependences upon deleted insn */
6953 if (GET_CODE (x) == NOTE || INSN_DELETED_P (x))
6955 if (find_insn_list (insn, INSN_DEPEND (x)))
6958 new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
6960 dep_type = REG_NOTE_KIND (link);
6961 PUT_REG_NOTE_KIND (new_link, dep_type);
6963 INSN_DEPEND (x) = new_link;
6964 INSN_DEP_COUNT (insn) += 1;
6969 /* Initialize variables for region data dependence analysis.
6970 n_bbs is the number of region blocks */
6972 __inline static void
6973 init_rgn_data_dependences (n_bbs)
6978 /* variables for which one copy exists for each block */
6979 bzero ((char *) bb_pending_read_insns, n_bbs * sizeof (rtx));
6980 bzero ((char *) bb_pending_read_mems, n_bbs * sizeof (rtx));
6981 bzero ((char *) bb_pending_write_insns, n_bbs * sizeof (rtx));
6982 bzero ((char *) bb_pending_write_mems, n_bbs * sizeof (rtx));
6983 bzero ((char *) bb_pending_lists_length, n_bbs * sizeof (rtx));
6984 bzero ((char *) bb_last_pending_memory_flush, n_bbs * sizeof (rtx));
6985 bzero ((char *) bb_last_function_call, n_bbs * sizeof (rtx));
6986 bzero ((char *) bb_sched_before_next_call, n_bbs * sizeof (rtx));
6988 /* Create an insn here so that we can hang dependencies off of it later. */
6989 for (bb = 0; bb < n_bbs; bb++)
6991 bb_sched_before_next_call[bb] =
6992 gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
6993 NULL_RTX, 0, NULL_RTX, NULL_RTX);
6994 LOG_LINKS (bb_sched_before_next_call[bb]) = 0;
6998 /* Add dependences so that branches are scheduled to run last in their block */
7001 add_branch_dependences (head, tail)
7007 /* For all branches, calls, uses, and cc0 setters, force them to remain
7008 in order at the end of the block by adding dependencies and giving
7009 the last a high priority. There may be notes present, and prev_head
7012 Branches must obviously remain at the end. Calls should remain at the
7013 end since moving them results in worse register allocation. Uses remain
7014 at the end to ensure proper register allocation. cc0 setters remaim
7015 at the end because they can't be moved away from their cc0 user. */
7018 while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
7019 || (GET_CODE (insn) == INSN
7020 && (GET_CODE (PATTERN (insn)) == USE
7022 || sets_cc0_p (PATTERN (insn))
7025 || GET_CODE (insn) == NOTE)
7027 if (GET_CODE (insn) != NOTE)
7030 && !find_insn_list (insn, LOG_LINKS (last)))
7032 add_dependence (last, insn, REG_DEP_ANTI);
7033 INSN_REF_COUNT (insn)++;
7036 CANT_MOVE (insn) = 1;
7039 /* Skip over insns that are part of a group.
7040 Make each insn explicitly depend on the previous insn.
7041 This ensures that only the group header will ever enter
7042 the ready queue (and, when scheduled, will automatically
7043 schedule the SCHED_GROUP_P block). */
7044 while (SCHED_GROUP_P (insn))
7046 rtx temp = prev_nonnote_insn (insn);
7047 add_dependence (insn, temp, REG_DEP_ANTI);
7052 /* Don't overrun the bounds of the basic block. */
7056 insn = PREV_INSN (insn);
7059 /* make sure these insns are scheduled last in their block */
7062 while (insn != head)
7064 insn = prev_nonnote_insn (insn);
7066 if (INSN_REF_COUNT (insn) != 0)
7069 if (!find_insn_list (last, LOG_LINKS (insn)))
7070 add_dependence (last, insn, REG_DEP_ANTI);
7071 INSN_REF_COUNT (insn) = 1;
7073 /* Skip over insns that are part of a group. */
7074 while (SCHED_GROUP_P (insn))
7075 insn = prev_nonnote_insn (insn);
7079 /* Compute bacward dependences inside BB. In a multiple blocks region:
7080 (1) a bb is analyzed after its predecessors, and (2) the lists in
7081 effect at the end of bb (after analyzing for bb) are inherited by
7084 Specifically for reg-reg data dependences, the block insns are
7085 scanned by sched_analyze () top-to-bottom. Two lists are
7086 naintained by sched_analyze (): reg_last_defs[] for register DEFs,
7087 and reg_last_uses[] for register USEs.
7089 When analysis is completed for bb, we update for its successors:
7090 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7091 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7093 The mechanism for computing mem-mem data dependence is very
7094 similar, and the result is interblock dependences in the region. */
7097 compute_block_backward_dependences (bb)
7103 int max_reg = max_reg_num ();
7105 b = BB_TO_BLOCK (bb);
7107 if (current_nr_blocks == 1)
7109 reg_last_uses = (rtx *) alloca (max_reg * sizeof (rtx));
7110 reg_last_sets = (rtx *) alloca (max_reg * sizeof (rtx));
7112 bzero ((char *) reg_last_uses, max_reg * sizeof (rtx));
7113 bzero ((char *) reg_last_sets, max_reg * sizeof (rtx));
7115 pending_read_insns = 0;
7116 pending_read_mems = 0;
7117 pending_write_insns = 0;
7118 pending_write_mems = 0;
7119 pending_lists_length = 0;
7120 last_function_call = 0;
7121 last_pending_memory_flush = 0;
7122 sched_before_next_call
7123 = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
7124 NULL_RTX, 0, NULL_RTX, NULL_RTX);
7125 LOG_LINKS (sched_before_next_call) = 0;
7129 reg_last_uses = bb_reg_last_uses[bb];
7130 reg_last_sets = bb_reg_last_sets[bb];
7132 pending_read_insns = bb_pending_read_insns[bb];
7133 pending_read_mems = bb_pending_read_mems[bb];
7134 pending_write_insns = bb_pending_write_insns[bb];
7135 pending_write_mems = bb_pending_write_mems[bb];
7136 pending_lists_length = bb_pending_lists_length[bb];
7137 last_function_call = bb_last_function_call[bb];
7138 last_pending_memory_flush = bb_last_pending_memory_flush[bb];
7140 sched_before_next_call = bb_sched_before_next_call[bb];
7143 /* do the analysis for this block */
7144 get_block_head_tail (bb, &head, &tail);
7145 sched_analyze (head, tail);
7146 add_branch_dependences (head, tail);
7148 if (current_nr_blocks > 1)
7151 int b_succ, bb_succ;
7153 rtx link_insn, link_mem;
7156 /* these lists should point to the right place, for correct freeing later. */
7157 bb_pending_read_insns[bb] = pending_read_insns;
7158 bb_pending_read_mems[bb] = pending_read_mems;
7159 bb_pending_write_insns[bb] = pending_write_insns;
7160 bb_pending_write_mems[bb] = pending_write_mems;
7162 /* bb's structures are inherited by it's successors */
7163 first_edge = e = OUT_EDGES (b);
7167 b_succ = TO_BLOCK (e);
7168 bb_succ = BLOCK_TO_BB (b_succ);
7170 /* only bbs "below" bb, in the same region, are interesting */
7171 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
7178 for (reg = 0; reg < max_reg; reg++)
7181 /* reg-last-uses lists are inherited by bb_succ */
7182 for (u = reg_last_uses[reg]; u; u = XEXP (u, 1))
7184 if (find_insn_list (XEXP (u, 0), (bb_reg_last_uses[bb_succ])[reg]))
7187 (bb_reg_last_uses[bb_succ])[reg]
7188 = alloc_INSN_LIST (XEXP (u, 0),
7189 (bb_reg_last_uses[bb_succ])[reg]);
7192 /* reg-last-defs lists are inherited by bb_succ */
7193 for (u = reg_last_sets[reg]; u; u = XEXP (u, 1))
7195 if (find_insn_list (XEXP (u, 0), (bb_reg_last_sets[bb_succ])[reg]))
7198 (bb_reg_last_sets[bb_succ])[reg]
7199 = alloc_INSN_LIST (XEXP (u, 0),
7200 (bb_reg_last_sets[bb_succ])[reg]);
7204 /* mem read/write lists are inherited by bb_succ */
7205 link_insn = pending_read_insns;
7206 link_mem = pending_read_mems;
7209 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7210 bb_pending_read_insns[bb_succ],
7211 bb_pending_read_mems[bb_succ])))
7212 add_insn_mem_dependence (&bb_pending_read_insns[bb_succ],
7213 &bb_pending_read_mems[bb_succ],
7214 XEXP (link_insn, 0), XEXP (link_mem, 0));
7215 link_insn = XEXP (link_insn, 1);
7216 link_mem = XEXP (link_mem, 1);
7219 link_insn = pending_write_insns;
7220 link_mem = pending_write_mems;
7223 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7224 bb_pending_write_insns[bb_succ],
7225 bb_pending_write_mems[bb_succ])))
7226 add_insn_mem_dependence (&bb_pending_write_insns[bb_succ],
7227 &bb_pending_write_mems[bb_succ],
7228 XEXP (link_insn, 0), XEXP (link_mem, 0));
7230 link_insn = XEXP (link_insn, 1);
7231 link_mem = XEXP (link_mem, 1);
7234 /* last_function_call is inherited by bb_succ */
7235 for (u = last_function_call; u; u = XEXP (u, 1))
7237 if (find_insn_list (XEXP (u, 0), bb_last_function_call[bb_succ]))
7240 bb_last_function_call[bb_succ]
7241 = alloc_INSN_LIST (XEXP (u, 0),
7242 bb_last_function_call[bb_succ]);
7245 /* last_pending_memory_flush is inherited by bb_succ */
7246 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
7248 if (find_insn_list (XEXP (u, 0), bb_last_pending_memory_flush[bb_succ]))
7251 bb_last_pending_memory_flush[bb_succ]
7252 = alloc_INSN_LIST (XEXP (u, 0),
7253 bb_last_pending_memory_flush[bb_succ]);
7256 /* sched_before_next_call is inherited by bb_succ */
7257 x = LOG_LINKS (sched_before_next_call);
7258 for (; x; x = XEXP (x, 1))
7259 add_dependence (bb_sched_before_next_call[bb_succ],
7260 XEXP (x, 0), REG_DEP_ANTI);
7264 while (e != first_edge);
7267 /* Free up the INSN_LISTs
7269 Note this loop is executed max_reg * nr_regions times. It's first
7270 implementation accounted for over 90% of the calls to free_list.
7271 The list was empty for the vast majority of those calls. On the PA,
7272 not calling free_list in those cases improves -O2 compile times by
7274 for (b = 0; b < max_reg; ++b)
7276 if (reg_last_sets[b])
7277 free_list (®_last_sets[b], &unused_insn_list);
7278 if (reg_last_uses[b])
7279 free_list (®_last_uses[b], &unused_insn_list);
7282 /* Assert that we won't need bb_reg_last_* for this block anymore. */
7283 if (current_nr_blocks > 1)
7285 bb_reg_last_uses[bb] = (rtx *) NULL_RTX;
7286 bb_reg_last_sets[bb] = (rtx *) NULL_RTX;
7290 /* Print dependences for debugging, callable from debugger */
7293 debug_dependencies ()
7297 fprintf (dump, ";; --------------- forward dependences: ------------ \n");
7298 for (bb = 0; bb < current_nr_blocks; bb++)
7306 get_block_head_tail (bb, &head, &tail);
7307 next_tail = NEXT_INSN (tail);
7308 fprintf (dump, "\n;; --- Region Dependences --- b %d bb %d \n",
7309 BB_TO_BLOCK (bb), bb);
7311 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7312 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7313 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7314 "----", "----", "--", "---", "----", "----", "--------", "-----");
7315 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
7320 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7323 fprintf (dump, ";; %6d ", INSN_UID (insn));
7324 if (GET_CODE (insn) == NOTE)
7326 n = NOTE_LINE_NUMBER (insn);
7328 fprintf (dump, "%s\n", GET_NOTE_INSN_NAME (n));
7330 fprintf (dump, "line %d, file %s\n", n,
7331 NOTE_SOURCE_FILE (insn));
7334 fprintf (dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
7338 unit = insn_unit (insn);
7340 || function_units[unit].blockage_range_function == 0) ? 0 :
7341 function_units[unit].blockage_range_function (insn);
7343 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7344 (SCHED_GROUP_P (insn) ? "+" : " "),
7348 INSN_DEP_COUNT (insn),
7349 INSN_PRIORITY (insn),
7350 insn_cost (insn, 0, 0),
7351 (int) MIN_BLOCKAGE_COST (range),
7352 (int) MAX_BLOCKAGE_COST (range));
7353 insn_print_units (insn);
7354 fprintf (dump, "\t: ");
7355 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
7356 fprintf (dump, "%d ", INSN_UID (XEXP (link, 0)));
7357 fprintf (dump, "\n");
7361 fprintf (dump, "\n");
7364 /* Set_priorities: compute priority of each insn in the block */
7377 get_block_head_tail (bb, &head, &tail);
7378 prev_head = PREV_INSN (head);
7381 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
7385 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
7388 if (GET_CODE (insn) == NOTE)
7391 if (!(SCHED_GROUP_P (insn)))
7393 (void) priority (insn);
7399 /* Make each element of VECTOR point at an rtx-vector,
7400 taking the space for all those rtx-vectors from SPACE.
7401 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7402 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7403 (this is the same as init_regset_vector () in flow.c) */
7406 init_rtx_vector (vector, space, nelts, bytes_per_elt)
7413 register rtx *p = space;
7415 for (i = 0; i < nelts; i++)
7418 p += bytes_per_elt / sizeof (*p);
7422 /* Schedule a region. A region is either an inner loop, a loop-free
7423 subroutine, or a single basic block. Each bb in the region is
7424 scheduled after its flow predecessors. */
7427 schedule_region (rgn)
7431 int rgn_n_insns = 0;
7432 int sched_rgn_n_insns = 0;
7434 /* set variables for the current region */
7435 current_nr_blocks = RGN_NR_BLOCKS (rgn);
7436 current_blocks = RGN_BLOCKS (rgn);
7438 reg_pending_sets = ALLOCA_REG_SET ();
7439 reg_pending_sets_all = 0;
7441 /* initializations for region data dependence analyisis */
7442 if (current_nr_blocks > 1)
7445 int maxreg = max_reg_num ();
7447 bb_reg_last_uses = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7448 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7449 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7450 init_rtx_vector (bb_reg_last_uses, space, current_nr_blocks, maxreg * sizeof (rtx *));
7452 bb_reg_last_sets = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7453 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7454 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7455 init_rtx_vector (bb_reg_last_sets, space, current_nr_blocks, maxreg * sizeof (rtx *));
7457 bb_pending_read_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7458 bb_pending_read_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7459 bb_pending_write_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7460 bb_pending_write_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7461 bb_pending_lists_length = (int *) alloca (current_nr_blocks * sizeof (int));
7462 bb_last_pending_memory_flush = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7463 bb_last_function_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7464 bb_sched_before_next_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7466 init_rgn_data_dependences (current_nr_blocks);
7469 /* compute LOG_LINKS */
7470 for (bb = 0; bb < current_nr_blocks; bb++)
7471 compute_block_backward_dependences (bb);
7473 /* compute INSN_DEPEND */
7474 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7475 compute_block_forward_dependences (bb);
7477 /* Delete line notes, compute live-regs at block end, and set priorities. */
7479 for (bb = 0; bb < current_nr_blocks; bb++)
7481 if (reload_completed == 0)
7482 find_pre_sched_live (bb);
7484 if (write_symbols != NO_DEBUG)
7486 save_line_notes (bb);
7490 rgn_n_insns += set_priorities (bb);
7493 /* compute interblock info: probabilities, split-edges, dominators, etc. */
7494 if (current_nr_blocks > 1)
7498 prob = (float *) alloca ((current_nr_blocks) * sizeof (float));
7500 bbset_size = current_nr_blocks / HOST_BITS_PER_WIDE_INT + 1;
7501 dom = (bbset *) alloca (current_nr_blocks * sizeof (bbset));
7502 for (i = 0; i < current_nr_blocks; i++)
7504 dom[i] = (bbset) alloca (bbset_size * sizeof (HOST_WIDE_INT));
7505 bzero ((char *) dom[i], bbset_size * sizeof (HOST_WIDE_INT));
7510 edge_to_bit = (int *) alloca (nr_edges * sizeof (int));
7511 for (i = 1; i < nr_edges; i++)
7512 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
7513 EDGE_TO_BIT (i) = rgn_nr_edges++;
7514 rgn_edges = (int *) alloca (rgn_nr_edges * sizeof (int));
7517 for (i = 1; i < nr_edges; i++)
7518 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
7519 rgn_edges[rgn_nr_edges++] = i;
7522 edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
7523 pot_split = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7524 ancestor_edges = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7525 for (i = 0; i < current_nr_blocks; i++)
7528 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7529 bzero ((char *) pot_split[i],
7530 edgeset_size * sizeof (HOST_WIDE_INT));
7532 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7533 bzero ((char *) ancestor_edges[i],
7534 edgeset_size * sizeof (HOST_WIDE_INT));
7537 /* compute probabilities, dominators, split_edges */
7538 for (bb = 0; bb < current_nr_blocks; bb++)
7539 compute_dom_prob_ps (bb);
7542 /* now we can schedule all blocks */
7543 for (bb = 0; bb < current_nr_blocks; bb++)
7545 sched_rgn_n_insns += schedule_block (bb, rgn_n_insns);
7552 /* sanity check: verify that all region insns were scheduled */
7553 if (sched_rgn_n_insns != rgn_n_insns)
7556 /* update register life and usage information */
7557 if (reload_completed == 0)
7559 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7560 find_post_sched_live (bb);
7562 if (current_nr_blocks <= 1)
7563 /* Sanity check. There should be no REG_DEAD notes leftover at the end.
7564 In practice, this can occur as the result of bugs in flow, combine.c,
7565 and/or sched.c. The values of the REG_DEAD notes remaining are
7566 meaningless, because dead_notes is just used as a free list. */
7567 if (dead_notes != 0)
7571 /* restore line notes. */
7572 if (write_symbols != NO_DEBUG)
7574 for (bb = 0; bb < current_nr_blocks; bb++)
7575 restore_line_notes (bb);
7578 /* Done with this region */
7579 free_pending_lists ();
7581 FREE_REG_SET (reg_pending_sets);
7584 /* Subroutine of split_hard_reg_notes. Searches X for any reference to
7585 REGNO, returning the rtx of the reference found if any. Otherwise,
7589 regno_use_in (regno, x)
7597 if (GET_CODE (x) == REG && REGNO (x) == regno)
7600 fmt = GET_RTX_FORMAT (GET_CODE (x));
7601 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
7605 if ((tem = regno_use_in (regno, XEXP (x, i))))
7608 else if (fmt[i] == 'E')
7609 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
7610 if ((tem = regno_use_in (regno, XVECEXP (x, i, j))))
7617 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
7618 needed for the hard register mentioned in the note. This can happen
7619 if the reference to the hard register in the original insn was split into
7620 several smaller hard register references in the split insns. */
7623 split_hard_reg_notes (note, first, last)
7624 rtx note, first, last;
7626 rtx reg, temp, link;
7627 int n_regs, i, new_reg;
7630 /* Assume that this is a REG_DEAD note. */
7631 if (REG_NOTE_KIND (note) != REG_DEAD)
7634 reg = XEXP (note, 0);
7636 n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
7638 for (i = 0; i < n_regs; i++)
7640 new_reg = REGNO (reg) + i;
7642 /* Check for references to new_reg in the split insns. */
7643 for (insn = last;; insn = PREV_INSN (insn))
7645 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7646 && (temp = regno_use_in (new_reg, PATTERN (insn))))
7648 /* Create a new reg dead note ere. */
7649 link = alloc_EXPR_LIST (REG_DEAD, temp, REG_NOTES (insn));
7650 REG_NOTES (insn) = link;
7652 /* If killed multiple registers here, then add in the excess. */
7653 i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
7657 /* It isn't mentioned anywhere, so no new reg note is needed for
7665 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
7666 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
7669 new_insn_dead_notes (pat, insn, last, orig_insn)
7670 rtx pat, insn, last, orig_insn;
7674 /* PAT is either a CLOBBER or a SET here. */
7675 dest = XEXP (pat, 0);
7677 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
7678 || GET_CODE (dest) == STRICT_LOW_PART
7679 || GET_CODE (dest) == SIGN_EXTRACT)
7680 dest = XEXP (dest, 0);
7682 if (GET_CODE (dest) == REG)
7684 /* If the original insn already used this register, we may not add new
7685 notes for it. One example for a split that needs this test is
7686 when a multi-word memory access with register-indirect addressing
7687 is split into multiple memory accesses with auto-increment and
7688 one adjusting add instruction for the address register. */
7689 if (reg_referenced_p (dest, PATTERN (orig_insn)))
7691 for (tem = last; tem != insn; tem = PREV_INSN (tem))
7693 if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
7694 && reg_overlap_mentioned_p (dest, PATTERN (tem))
7695 && (set = single_set (tem)))
7697 rtx tem_dest = SET_DEST (set);
7699 while (GET_CODE (tem_dest) == ZERO_EXTRACT
7700 || GET_CODE (tem_dest) == SUBREG
7701 || GET_CODE (tem_dest) == STRICT_LOW_PART
7702 || GET_CODE (tem_dest) == SIGN_EXTRACT)
7703 tem_dest = XEXP (tem_dest, 0);
7705 if (!rtx_equal_p (tem_dest, dest))
7707 /* Use the same scheme as combine.c, don't put both REG_DEAD
7708 and REG_UNUSED notes on the same insn. */
7709 if (!find_regno_note (tem, REG_UNUSED, REGNO (dest))
7710 && !find_regno_note (tem, REG_DEAD, REGNO (dest)))
7712 rtx note = alloc_EXPR_LIST (REG_DEAD, dest,
7714 REG_NOTES (tem) = note;
7716 /* The reg only dies in one insn, the last one that uses
7720 else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
7721 /* We found an instruction that both uses the register,
7722 and sets it, so no new REG_NOTE is needed for this set. */
7726 /* If this is a set, it must die somewhere, unless it is the dest of
7727 the original insn, and hence is live after the original insn. Abort
7728 if it isn't supposed to be live after the original insn.
7730 If this is a clobber, then just add a REG_UNUSED note. */
7733 int live_after_orig_insn = 0;
7734 rtx pattern = PATTERN (orig_insn);
7737 if (GET_CODE (pat) == CLOBBER)
7739 rtx note = alloc_EXPR_LIST (REG_UNUSED, dest, REG_NOTES (insn));
7740 REG_NOTES (insn) = note;
7744 /* The original insn could have multiple sets, so search the
7745 insn for all sets. */
7746 if (GET_CODE (pattern) == SET)
7748 if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
7749 live_after_orig_insn = 1;
7751 else if (GET_CODE (pattern) == PARALLEL)
7753 for (i = 0; i < XVECLEN (pattern, 0); i++)
7754 if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
7755 && reg_overlap_mentioned_p (dest,
7756 SET_DEST (XVECEXP (pattern,
7758 live_after_orig_insn = 1;
7761 if (!live_after_orig_insn)
7767 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
7768 registers modified by X. INC is -1 if the containing insn is being deleted,
7769 and is 1 if the containing insn is a newly generated insn. */
7772 update_n_sets (x, inc)
7776 rtx dest = SET_DEST (x);
7778 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
7779 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
7780 dest = SUBREG_REG (dest);
7782 if (GET_CODE (dest) == REG)
7784 int regno = REGNO (dest);
7786 if (regno < FIRST_PSEUDO_REGISTER)
7789 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
7791 for (i = regno; i < endregno; i++)
7792 REG_N_SETS (i) += inc;
7795 REG_N_SETS (regno) += inc;
7799 /* Updates all flow-analysis related quantities (including REG_NOTES) for
7800 the insns from FIRST to LAST inclusive that were created by splitting
7801 ORIG_INSN. NOTES are the original REG_NOTES. */
7804 update_flow_info (notes, first, last, orig_insn)
7811 rtx orig_dest, temp;
7814 /* Get and save the destination set by the original insn. */
7816 orig_dest = single_set (orig_insn);
7818 orig_dest = SET_DEST (orig_dest);
7820 /* Move REG_NOTES from the original insn to where they now belong. */
7822 for (note = notes; note; note = next)
7824 next = XEXP (note, 1);
7825 switch (REG_NOTE_KIND (note))
7829 /* Move these notes from the original insn to the last new insn where
7830 the register is now set. */
7832 for (insn = last;; insn = PREV_INSN (insn))
7834 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7835 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
7837 /* If this note refers to a multiple word hard register, it
7838 may have been split into several smaller hard register
7839 references, so handle it specially. */
7840 temp = XEXP (note, 0);
7841 if (REG_NOTE_KIND (note) == REG_DEAD
7842 && GET_CODE (temp) == REG
7843 && REGNO (temp) < FIRST_PSEUDO_REGISTER
7844 && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
7845 split_hard_reg_notes (note, first, last);
7848 XEXP (note, 1) = REG_NOTES (insn);
7849 REG_NOTES (insn) = note;
7852 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
7854 /* ??? This won't handle multiple word registers correctly,
7855 but should be good enough for now. */
7856 if (REG_NOTE_KIND (note) == REG_UNUSED
7857 && GET_CODE (XEXP (note, 0)) != SCRATCH
7858 && !dead_or_set_p (insn, XEXP (note, 0)))
7859 PUT_REG_NOTE_KIND (note, REG_DEAD);
7861 /* The reg only dies in one insn, the last one that uses
7865 /* It must die somewhere, fail it we couldn't find where it died.
7867 If this is a REG_UNUSED note, then it must be a temporary
7868 register that was not needed by this instantiation of the
7869 pattern, so we can safely ignore it. */
7872 /* After reload, REG_DEAD notes come sometimes an
7873 instruction after the register actually dies. */
7874 if (reload_completed && REG_NOTE_KIND (note) == REG_DEAD)
7876 XEXP (note, 1) = REG_NOTES (insn);
7877 REG_NOTES (insn) = note;
7881 if (REG_NOTE_KIND (note) != REG_UNUSED)
7890 /* If the insn that set the register to 0 was deleted, this
7891 note cannot be relied on any longer. The destination might
7892 even have been moved to memory.
7893 This was observed for SH4 with execute/920501-6.c compilation,
7894 -O2 -fomit-frame-pointer -finline-functions . */
7895 if (GET_CODE (XEXP (note, 0)) == NOTE
7896 || INSN_DELETED_P (XEXP (note, 0)))
7898 /* This note applies to the dest of the original insn. Find the
7899 first new insn that now has the same dest, and move the note
7905 for (insn = first;; insn = NEXT_INSN (insn))
7907 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7908 && (temp = single_set (insn))
7909 && rtx_equal_p (SET_DEST (temp), orig_dest))
7911 XEXP (note, 1) = REG_NOTES (insn);
7912 REG_NOTES (insn) = note;
7913 /* The reg is only zero before one insn, the first that
7917 /* If this note refers to a multiple word hard
7918 register, it may have been split into several smaller
7919 hard register references. We could split the notes,
7920 but simply dropping them is good enough. */
7921 if (GET_CODE (orig_dest) == REG
7922 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
7923 && HARD_REGNO_NREGS (REGNO (orig_dest),
7924 GET_MODE (orig_dest)) > 1)
7926 /* It must be set somewhere, fail if we couldn't find where it
7935 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
7936 set is meaningless. Just drop the note. */
7940 case REG_NO_CONFLICT:
7941 /* These notes apply to the dest of the original insn. Find the last
7942 new insn that now has the same dest, and move the note there. */
7947 for (insn = last;; insn = PREV_INSN (insn))
7949 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7950 && (temp = single_set (insn))
7951 && rtx_equal_p (SET_DEST (temp), orig_dest))
7953 XEXP (note, 1) = REG_NOTES (insn);
7954 REG_NOTES (insn) = note;
7955 /* Only put this note on one of the new insns. */
7959 /* The original dest must still be set someplace. Abort if we
7960 couldn't find it. */
7963 /* However, if this note refers to a multiple word hard
7964 register, it may have been split into several smaller
7965 hard register references. We could split the notes,
7966 but simply dropping them is good enough. */
7967 if (GET_CODE (orig_dest) == REG
7968 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
7969 && HARD_REGNO_NREGS (REGNO (orig_dest),
7970 GET_MODE (orig_dest)) > 1)
7972 /* Likewise for multi-word memory references. */
7973 if (GET_CODE (orig_dest) == MEM
7974 && SIZE_FOR_MODE (orig_dest) > MOVE_MAX)
7982 /* Move a REG_LIBCALL note to the first insn created, and update
7983 the corresponding REG_RETVAL note. */
7984 XEXP (note, 1) = REG_NOTES (first);
7985 REG_NOTES (first) = note;
7987 insn = XEXP (note, 0);
7988 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
7990 XEXP (note, 0) = first;
7993 case REG_EXEC_COUNT:
7994 /* Move a REG_EXEC_COUNT note to the first insn created. */
7995 XEXP (note, 1) = REG_NOTES (first);
7996 REG_NOTES (first) = note;
8000 /* Move a REG_RETVAL note to the last insn created, and update
8001 the corresponding REG_LIBCALL note. */
8002 XEXP (note, 1) = REG_NOTES (last);
8003 REG_NOTES (last) = note;
8005 insn = XEXP (note, 0);
8006 note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
8008 XEXP (note, 0) = last;
8013 /* This should be moved to whichever instruction is a JUMP_INSN. */
8015 for (insn = last;; insn = PREV_INSN (insn))
8017 if (GET_CODE (insn) == JUMP_INSN)
8019 XEXP (note, 1) = REG_NOTES (insn);
8020 REG_NOTES (insn) = note;
8021 /* Only put this note on one of the new insns. */
8024 /* Fail if we couldn't find a JUMP_INSN. */
8031 /* reload sometimes leaves obsolete REG_INC notes around. */
8032 if (reload_completed)
8034 /* This should be moved to whichever instruction now has the
8035 increment operation. */
8039 /* Should be moved to the new insn(s) which use the label. */
8040 for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
8041 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8042 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
8044 REG_NOTES (insn) = alloc_EXPR_LIST (REG_LABEL,
8052 /* These two notes will never appear until after reorg, so we don't
8053 have to handle them here. */
8059 /* Each new insn created, except the last, has a new set. If the destination
8060 is a register, then this reg is now live across several insns, whereas
8061 previously the dest reg was born and died within the same insn. To
8062 reflect this, we now need a REG_DEAD note on the insn where this
8065 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
8067 for (insn = first; insn != last; insn = NEXT_INSN (insn))
8072 pat = PATTERN (insn);
8073 if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
8074 new_insn_dead_notes (pat, insn, last, orig_insn);
8075 else if (GET_CODE (pat) == PARALLEL)
8077 for (i = 0; i < XVECLEN (pat, 0); i++)
8078 if (GET_CODE (XVECEXP (pat, 0, i)) == SET
8079 || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
8080 new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
8084 /* If any insn, except the last, uses the register set by the last insn,
8085 then we need a new REG_DEAD note on that insn. In this case, there
8086 would not have been a REG_DEAD note for this register in the original
8087 insn because it was used and set within one insn. */
8089 set = single_set (last);
8092 rtx dest = SET_DEST (set);
8094 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
8095 || GET_CODE (dest) == STRICT_LOW_PART
8096 || GET_CODE (dest) == SIGN_EXTRACT)
8097 dest = XEXP (dest, 0);
8099 if (GET_CODE (dest) == REG
8100 /* Global registers are always live, so the code below does not
8102 && (REGNO (dest) >= FIRST_PSEUDO_REGISTER
8103 || ! global_regs[REGNO (dest)]))
8105 rtx stop_insn = PREV_INSN (first);
8107 /* If the last insn uses the register that it is setting, then
8108 we don't want to put a REG_DEAD note there. Search backwards
8109 to find the first insn that sets but does not use DEST. */
8112 if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
8114 for (insn = PREV_INSN (insn); insn != first;
8115 insn = PREV_INSN (insn))
8117 if ((set = single_set (insn))
8118 && reg_mentioned_p (dest, SET_DEST (set))
8119 && ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
8124 /* Now find the first insn that uses but does not set DEST. */
8126 for (insn = PREV_INSN (insn); insn != stop_insn;
8127 insn = PREV_INSN (insn))
8129 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8130 && reg_mentioned_p (dest, PATTERN (insn))
8131 && (set = single_set (insn)))
8133 rtx insn_dest = SET_DEST (set);
8135 while (GET_CODE (insn_dest) == ZERO_EXTRACT
8136 || GET_CODE (insn_dest) == SUBREG
8137 || GET_CODE (insn_dest) == STRICT_LOW_PART
8138 || GET_CODE (insn_dest) == SIGN_EXTRACT)
8139 insn_dest = XEXP (insn_dest, 0);
8141 if (insn_dest != dest)
8143 note = alloc_EXPR_LIST (REG_DEAD, dest, REG_NOTES (insn));
8144 REG_NOTES (insn) = note;
8145 /* The reg only dies in one insn, the last one
8154 /* If the original dest is modifying a multiple register target, and the
8155 original instruction was split such that the original dest is now set
8156 by two or more SUBREG sets, then the split insns no longer kill the
8157 destination of the original insn.
8159 In this case, if there exists an instruction in the same basic block,
8160 before the split insn, which uses the original dest, and this use is
8161 killed by the original insn, then we must remove the REG_DEAD note on
8162 this insn, because it is now superfluous.
8164 This does not apply when a hard register gets split, because the code
8165 knows how to handle overlapping hard registers properly. */
8166 if (orig_dest && GET_CODE (orig_dest) == REG)
8168 int found_orig_dest = 0;
8169 int found_split_dest = 0;
8171 for (insn = first;; insn = NEXT_INSN (insn))
8176 /* I'm not sure if this can happen, but let's be safe. */
8177 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
8180 pat = PATTERN (insn);
8181 i = GET_CODE (pat) == PARALLEL ? XVECLEN (pat, 0) : 0;
8186 if (GET_CODE (set) == SET)
8188 if (GET_CODE (SET_DEST (set)) == REG
8189 && REGNO (SET_DEST (set)) == REGNO (orig_dest))
8191 found_orig_dest = 1;
8194 else if (GET_CODE (SET_DEST (set)) == SUBREG
8195 && SUBREG_REG (SET_DEST (set)) == orig_dest)
8197 found_split_dest = 1;
8203 set = XVECEXP (pat, 0, i);
8210 if (found_split_dest)
8212 /* Search backwards from FIRST, looking for the first insn that uses
8213 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
8214 If we find an insn, and it has a REG_DEAD note, then delete the
8217 for (insn = first; insn; insn = PREV_INSN (insn))
8219 if (GET_CODE (insn) == CODE_LABEL
8220 || GET_CODE (insn) == JUMP_INSN)
8222 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8223 && reg_mentioned_p (orig_dest, insn))
8225 note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
8227 remove_note (insn, note);
8231 else if (!found_orig_dest)
8233 /* This should never happen. */
8238 /* Update reg_n_sets. This is necessary to prevent local alloc from
8239 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
8240 a reg from set once to set multiple times. */
8243 rtx x = PATTERN (orig_insn);
8244 RTX_CODE code = GET_CODE (x);
8246 if (code == SET || code == CLOBBER)
8247 update_n_sets (x, -1);
8248 else if (code == PARALLEL)
8251 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8253 code = GET_CODE (XVECEXP (x, 0, i));
8254 if (code == SET || code == CLOBBER)
8255 update_n_sets (XVECEXP (x, 0, i), -1);
8259 for (insn = first;; insn = NEXT_INSN (insn))
8262 code = GET_CODE (x);
8264 if (code == SET || code == CLOBBER)
8265 update_n_sets (x, 1);
8266 else if (code == PARALLEL)
8269 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8271 code = GET_CODE (XVECEXP (x, 0, i));
8272 if (code == SET || code == CLOBBER)
8273 update_n_sets (XVECEXP (x, 0, i), 1);
8283 /* Do the splitting of insns in the block b. */
8286 split_block_insns (b)
8291 for (insn = basic_block_head[b];; insn = next)
8293 rtx set, last, first, notes;
8295 /* Can't use `next_real_insn' because that
8296 might go across CODE_LABELS and short-out basic blocks. */
8297 next = NEXT_INSN (insn);
8298 if (GET_CODE (insn) != INSN)
8300 if (insn == basic_block_end[b])
8306 /* Don't split no-op move insns. These should silently disappear
8307 later in final. Splitting such insns would break the code
8308 that handles REG_NO_CONFLICT blocks. */
8309 set = single_set (insn);
8310 if (set && rtx_equal_p (SET_SRC (set), SET_DEST (set)))
8312 if (insn == basic_block_end[b])
8315 /* Nops get in the way while scheduling, so delete them now if
8316 register allocation has already been done. It is too risky
8317 to try to do this before register allocation, and there are
8318 unlikely to be very many nops then anyways. */
8319 if (reload_completed)
8321 PUT_CODE (insn, NOTE);
8322 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
8323 NOTE_SOURCE_FILE (insn) = 0;
8329 /* Split insns here to get max fine-grain parallelism. */
8330 first = PREV_INSN (insn);
8331 notes = REG_NOTES (insn);
8332 last = try_split (PATTERN (insn), insn, 1);
8335 /* try_split returns the NOTE that INSN became. */
8336 first = NEXT_INSN (first);
8337 update_flow_info (notes, first, last, insn);
8339 PUT_CODE (insn, NOTE);
8340 NOTE_SOURCE_FILE (insn) = 0;
8341 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
8342 if (insn == basic_block_head[b])
8343 basic_block_head[b] = first;
8344 if (insn == basic_block_end[b])
8346 basic_block_end[b] = last;
8351 if (insn == basic_block_end[b])
8356 /* The one entry point in this file. DUMP_FILE is the dump file for
8360 schedule_insns (dump_file)
8371 /* disable speculative loads in their presence if cc0 defined */
8373 flag_schedule_speculative_load = 0;
8376 /* Taking care of this degenerate case makes the rest of
8377 this code simpler. */
8378 if (n_basic_blocks == 0)
8381 /* set dump and sched_verbose for the desired debugging output. If no
8382 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
8383 For -fsched-verbose-N, N>=10, print everything to stderr. */
8384 sched_verbose = sched_verbose_param;
8385 if (sched_verbose_param == 0 && dump_file)
8387 dump = ((sched_verbose_param >= 10 || !dump_file) ? stderr : dump_file);
8392 /* Initialize the unused_*_lists. We can't use the ones left over from
8393 the previous function, because gcc has freed that memory. We can use
8394 the ones left over from the first sched pass in the second pass however,
8395 so only clear them on the first sched pass. The first pass is before
8396 reload if flag_schedule_insns is set, otherwise it is afterwards. */
8398 if (reload_completed == 0 || !flag_schedule_insns)
8400 unused_insn_list = 0;
8401 unused_expr_list = 0;
8404 /* initialize issue_rate */
8405 issue_rate = ISSUE_RATE;
8407 /* do the splitting first for all blocks */
8408 for (b = 0; b < n_basic_blocks; b++)
8409 split_block_insns (b);
8411 max_uid = (get_max_uid () + 1);
8413 cant_move = (char *) alloca (max_uid * sizeof (char));
8414 bzero ((char *) cant_move, max_uid * sizeof (char));
8416 fed_by_spec_load = (char *) alloca (max_uid * sizeof (char));
8417 bzero ((char *) fed_by_spec_load, max_uid * sizeof (char));
8419 is_load_insn = (char *) alloca (max_uid * sizeof (char));
8420 bzero ((char *) is_load_insn, max_uid * sizeof (char));
8422 insn_orig_block = (int *) alloca (max_uid * sizeof (int));
8423 insn_luid = (int *) alloca (max_uid * sizeof (int));
8426 for (b = 0; b < n_basic_blocks; b++)
8427 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
8429 INSN_BLOCK (insn) = b;
8430 INSN_LUID (insn) = luid++;
8432 if (insn == basic_block_end[b])
8436 /* after reload, remove inter-blocks dependences computed before reload. */
8437 if (reload_completed)
8442 for (b = 0; b < n_basic_blocks; b++)
8443 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
8447 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
8450 link = LOG_LINKS (insn);
8453 rtx x = XEXP (link, 0);
8455 if (INSN_BLOCK (x) != b)
8457 remove_dependence (insn, x);
8458 link = prev ? XEXP (prev, 1) : LOG_LINKS (insn);
8461 prev = link, link = XEXP (prev, 1);
8465 if (insn == basic_block_end[b])
8471 rgn_table = (region *) alloca ((n_basic_blocks) * sizeof (region));
8472 rgn_bb_table = (int *) alloca ((n_basic_blocks) * sizeof (int));
8473 block_to_bb = (int *) alloca ((n_basic_blocks) * sizeof (int));
8474 containing_rgn = (int *) alloca ((n_basic_blocks) * sizeof (int));
8476 /* compute regions for scheduling */
8477 if (reload_completed
8478 || n_basic_blocks == 1
8479 || !flag_schedule_interblock)
8481 find_single_block_region ();
8485 /* verify that a 'good' control flow graph can be built */
8486 if (is_cfg_nonregular ())
8488 find_single_block_region ();
8492 int_list_ptr *s_preds, *s_succs;
8493 int *num_preds, *num_succs;
8494 sbitmap *dom, *pdom;
8496 s_preds = (int_list_ptr *) alloca (n_basic_blocks
8497 * sizeof (int_list_ptr));
8498 s_succs = (int_list_ptr *) alloca (n_basic_blocks
8499 * sizeof (int_list_ptr));
8500 num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
8501 num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
8502 dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
8503 pdom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
8505 /* The scheduler runs after flow; therefore, we can't blindly call
8506 back into find_basic_blocks since doing so could invalidate the
8507 info in basic_block_live_at_start.
8509 Consider a block consisting entirely of dead stores; after life
8510 analysis it would be a block of NOTE_INSN_DELETED notes. If
8511 we call find_basic_blocks again, then the block would be removed
8512 entirely and invalidate our the register live information.
8514 We could (should?) recompute register live information. Doing
8515 so may even be beneficial. */
8517 compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
8519 /* Compute the dominators and post dominators. We don't currently use
8520 post dominators, but we should for speculative motion analysis. */
8521 compute_dominators (dom, pdom, s_preds, s_succs);
8523 /* build_control_flow will return nonzero if it detects unreachable
8524 blocks or any other irregularity with the cfg which prevents
8525 cross block scheduling. */
8526 if (build_control_flow (s_preds, s_succs, num_preds, num_succs) != 0)
8527 find_single_block_region ();
8529 find_rgns (s_preds, s_succs, num_preds, num_succs, dom);
8531 if (sched_verbose >= 3)
8534 /* For now. This will move as more and more of haifa is converted
8535 to using the cfg code in flow.c */
8542 /* Allocate data for this pass. See comments, above,
8543 for what these vectors do. */
8544 insn_priority = (int *) alloca (max_uid * sizeof (int));
8545 insn_reg_weight = (int *) alloca (max_uid * sizeof (int));
8546 insn_tick = (int *) alloca (max_uid * sizeof (int));
8547 insn_costs = (short *) alloca (max_uid * sizeof (short));
8548 insn_units = (short *) alloca (max_uid * sizeof (short));
8549 insn_blockage = (unsigned int *) alloca (max_uid * sizeof (unsigned int));
8550 insn_ref_count = (int *) alloca (max_uid * sizeof (int));
8552 /* Allocate for forward dependencies */
8553 insn_dep_count = (int *) alloca (max_uid * sizeof (int));
8554 insn_depend = (rtx *) alloca (max_uid * sizeof (rtx));
8556 if (reload_completed == 0)
8560 sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
8561 sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
8562 sched_reg_basic_block = (int *) alloca (max_regno * sizeof (int));
8563 bb_live_regs = ALLOCA_REG_SET ();
8564 bzero ((char *) sched_reg_n_calls_crossed, max_regno * sizeof (int));
8565 bzero ((char *) sched_reg_live_length, max_regno * sizeof (int));
8567 for (i = 0; i < max_regno; i++)
8568 sched_reg_basic_block[i] = REG_BLOCK_UNKNOWN;
8572 sched_reg_n_calls_crossed = 0;
8573 sched_reg_live_length = 0;
8576 init_alias_analysis ();
8578 if (write_symbols != NO_DEBUG)
8582 line_note = (rtx *) alloca (max_uid * sizeof (rtx));
8583 bzero ((char *) line_note, max_uid * sizeof (rtx));
8584 line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
8585 bzero ((char *) line_note_head, n_basic_blocks * sizeof (rtx));
8587 /* Save-line-note-head:
8588 Determine the line-number at the start of each basic block.
8589 This must be computed and saved now, because after a basic block's
8590 predecessor has been scheduled, it is impossible to accurately
8591 determine the correct line number for the first insn of the block. */
8593 for (b = 0; b < n_basic_blocks; b++)
8594 for (line = basic_block_head[b]; line; line = PREV_INSN (line))
8595 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
8597 line_note_head[b] = line;
8602 bzero ((char *) insn_priority, max_uid * sizeof (int));
8603 bzero ((char *) insn_reg_weight, max_uid * sizeof (int));
8604 bzero ((char *) insn_tick, max_uid * sizeof (int));
8605 bzero ((char *) insn_costs, max_uid * sizeof (short));
8606 bzero ((char *) insn_units, max_uid * sizeof (short));
8607 bzero ((char *) insn_blockage, max_uid * sizeof (unsigned int));
8608 bzero ((char *) insn_ref_count, max_uid * sizeof (int));
8610 /* Initialize for forward dependencies */
8611 bzero ((char *) insn_depend, max_uid * sizeof (rtx));
8612 bzero ((char *) insn_dep_count, max_uid * sizeof (int));
8614 /* Find units used in this fuction, for visualization */
8616 init_target_units ();
8618 /* ??? Add a NOTE after the last insn of the last basic block. It is not
8619 known why this is done. */
8621 insn = basic_block_end[n_basic_blocks - 1];
8622 if (NEXT_INSN (insn) == 0
8623 || (GET_CODE (insn) != NOTE
8624 && GET_CODE (insn) != CODE_LABEL
8625 /* Don't emit a NOTE if it would end up between an unconditional
8626 jump and a BARRIER. */
8627 && !(GET_CODE (insn) == JUMP_INSN
8628 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
8629 emit_note_after (NOTE_INSN_DELETED, basic_block_end[n_basic_blocks - 1]);
8631 /* Schedule every region in the subroutine */
8632 for (rgn = 0; rgn < nr_regions; rgn++)
8634 schedule_region (rgn);
8641 /* Reposition the prologue and epilogue notes in case we moved the
8642 prologue/epilogue insns. */
8643 if (reload_completed)
8644 reposition_prologue_and_epilogue_notes (get_insns ());
8646 /* delete redundant line notes. */
8647 if (write_symbols != NO_DEBUG)
8648 rm_redundant_line_notes ();
8650 /* Update information about uses of registers in the subroutine. */
8651 if (reload_completed == 0)
8652 update_reg_usage ();
8656 if (reload_completed == 0 && flag_schedule_interblock)
8658 fprintf (dump, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8666 fprintf (dump, "\n\n");
8670 FREE_REG_SET (bb_live_regs);
8689 #endif /* INSN_SCHEDULING */