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"
169 extern char *reg_known_equiv_p;
170 extern rtx *reg_known_value;
172 #ifdef INSN_SCHEDULING
174 /* target_units bitmask has 1 for each unit in the cpu. It should be
175 possible to compute this variable from the machine description.
176 But currently it is computed by examinning the insn list. Since
177 this is only needed for visualization, it seems an acceptable
178 solution. (For understanding the mapping of bits to units, see
179 definition of function_units[] in "insn-attrtab.c") */
181 static int target_units = 0;
183 /* issue_rate is the number of insns that can be scheduled in the same
184 machine cycle. It can be defined in the config/mach/mach.h file,
185 otherwise we set it to 1. */
187 static int issue_rate;
193 /* sched-verbose controls the amount of debugging output the
194 scheduler prints. It is controlled by -fsched-verbose-N:
195 N>0 and no -DSR : the output is directed to stderr.
196 N>=10 will direct the printouts to stderr (regardless of -dSR).
198 N=2: bb's probabilities, detailed ready list info, unit/insn info.
199 N=3: rtl at abort point, control-flow, regions info.
200 N=5: dependences info. */
202 #define MAX_RGN_BLOCKS 10
203 #define MAX_RGN_INSNS 100
205 static int sched_verbose_param = 0;
206 static int sched_verbose = 0;
208 /* nr_inter/spec counts interblock/speculative motion for the function */
209 static int nr_inter, nr_spec;
212 /* debugging file. all printouts are sent to dump, which is always set,
213 either to stderr, or to the dump listing file (-dRS). */
214 static FILE *dump = 0;
216 /* fix_sched_param() is called from toplev.c upon detection
217 of the -fsched-***-N options. */
220 fix_sched_param (param, val)
223 if (!strcmp (param, "verbose"))
224 sched_verbose_param = atoi (val);
226 warning ("fix_sched_param: unknown param: %s", param);
230 /* Arrays set up by scheduling for the same respective purposes as
231 similar-named arrays set up by flow analysis. We work with these
232 arrays during the scheduling pass so we can compare values against
235 Values of these arrays are copied at the end of this pass into the
236 arrays set up by flow analysis. */
237 static int *sched_reg_n_calls_crossed;
238 static int *sched_reg_live_length;
239 static int *sched_reg_basic_block;
241 /* We need to know the current block number during the post scheduling
242 update of live register information so that we can also update
243 REG_BASIC_BLOCK if a register changes blocks. */
244 static int current_block_num;
246 /* Element N is the next insn that sets (hard or pseudo) register
247 N within the current basic block; or zero, if there is no
248 such insn. Needed for new registers which may be introduced
249 by splitting insns. */
250 static rtx *reg_last_uses;
251 static rtx *reg_last_sets;
252 static regset reg_pending_sets;
253 static int reg_pending_sets_all;
255 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
256 static int *insn_luid;
257 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
259 /* Vector indexed by INSN_UID giving each instruction a priority. */
260 static int *insn_priority;
261 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
263 static short *insn_costs;
264 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
266 /* Vector indexed by INSN_UID giving an encoding of the function units
268 static short *insn_units;
269 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
271 /* Vector indexed by INSN_UID giving each instruction a register-weight.
272 This weight is an estimation of the insn contribution to registers pressure. */
273 static int *insn_reg_weight;
274 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
276 /* Vector indexed by INSN_UID giving list of insns which
277 depend upon INSN. Unlike LOG_LINKS, it represents forward dependences. */
278 static rtx *insn_depend;
279 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
281 /* Vector indexed by INSN_UID. Initialized to the number of incoming
282 edges in forward dependence graph (= number of LOG_LINKS). As
283 scheduling procedes, dependence counts are decreased. An
284 instruction moves to the ready list when its counter is zero. */
285 static int *insn_dep_count;
286 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
288 /* Vector indexed by INSN_UID giving an encoding of the blockage range
289 function. The unit and the range are encoded. */
290 static unsigned int *insn_blockage;
291 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
293 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
294 #define ENCODE_BLOCKAGE(U, R) \
295 ((((U) << UNIT_BITS) << BLOCKAGE_BITS \
296 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
297 | MAX_BLOCKAGE_COST (R))
298 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
299 #define BLOCKAGE_RANGE(B) \
300 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
301 | ((B) & BLOCKAGE_MASK))
303 /* Encodings of the `<name>_unit_blockage_range' function. */
304 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
305 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
307 #define DONE_PRIORITY -1
308 #define MAX_PRIORITY 0x7fffffff
309 #define TAIL_PRIORITY 0x7ffffffe
310 #define LAUNCH_PRIORITY 0x7f000001
311 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
312 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
314 /* Vector indexed by INSN_UID giving number of insns referring to this insn. */
315 static int *insn_ref_count;
316 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
318 /* Vector indexed by INSN_UID giving line-number note in effect for each
319 insn. For line-number notes, this indicates whether the note may be
321 static rtx *line_note;
322 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
324 /* Vector indexed by basic block number giving the starting line-number
325 for each basic block. */
326 static rtx *line_note_head;
328 /* List of important notes we must keep around. This is a pointer to the
329 last element in the list. */
330 static rtx note_list;
332 /* Regsets telling whether a given register is live or dead before the last
333 scheduled insn. Must scan the instructions once before scheduling to
334 determine what registers are live or dead at the end of the block. */
335 static regset bb_live_regs;
337 /* Regset telling whether a given register is live after the insn currently
338 being scheduled. Before processing an insn, this is equal to bb_live_regs
339 above. This is used so that we can find registers that are newly born/dead
340 after processing an insn. */
341 static regset old_live_regs;
343 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
344 during the initial scan and reused later. If there are not exactly as
345 many REG_DEAD notes in the post scheduled code as there were in the
346 prescheduled code then we trigger an abort because this indicates a bug. */
347 static rtx dead_notes;
351 /* An instruction is ready to be scheduled when all insns preceding it
352 have already been scheduled. It is important to ensure that all
353 insns which use its result will not be executed until its result
354 has been computed. An insn is maintained in one of four structures:
356 (P) the "Pending" set of insns which cannot be scheduled until
357 their dependencies have been satisfied.
358 (Q) the "Queued" set of insns that can be scheduled when sufficient
360 (R) the "Ready" list of unscheduled, uncommitted insns.
361 (S) the "Scheduled" list of insns.
363 Initially, all insns are either "Pending" or "Ready" depending on
364 whether their dependencies are satisfied.
366 Insns move from the "Ready" list to the "Scheduled" list as they
367 are committed to the schedule. As this occurs, the insns in the
368 "Pending" list have their dependencies satisfied and move to either
369 the "Ready" list or the "Queued" set depending on whether
370 sufficient time has passed to make them ready. As time passes,
371 insns move from the "Queued" set to the "Ready" list. Insns may
372 move from the "Ready" list to the "Queued" set if they are blocked
373 due to a function unit conflict.
375 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
376 insns, i.e., those that are ready, queued, and pending.
377 The "Queued" set (Q) is implemented by the variable `insn_queue'.
378 The "Ready" list (R) is implemented by the variables `ready' and
380 The "Scheduled" list (S) is the new insn chain built by this pass.
382 The transition (R->S) is implemented in the scheduling loop in
383 `schedule_block' when the best insn to schedule is chosen.
384 The transition (R->Q) is implemented in `queue_insn' when an
385 insn is found to have a function unit conflict with the already
387 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
388 insns move from the ready list to the scheduled list.
389 The transition (Q->R) is implemented in 'queue_to_insn' as time
390 passes or stalls are introduced. */
392 /* Implement a circular buffer to delay instructions until sufficient
393 time has passed. INSN_QUEUE_SIZE is a power of two larger than
394 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
395 longest time an isnsn may be queued. */
396 static rtx insn_queue[INSN_QUEUE_SIZE];
397 static int q_ptr = 0;
398 static int q_size = 0;
399 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
400 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
402 /* Vector indexed by INSN_UID giving the minimum clock tick at which
403 the insn becomes ready. This is used to note timing constraints for
404 insns in the pending list. */
405 static int *insn_tick;
406 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
408 /* Data structure for keeping track of register information
409 during that register's life. */
418 /* Forward declarations. */
419 static void add_dependence PROTO ((rtx, rtx, enum reg_note));
420 static void remove_dependence PROTO ((rtx, rtx));
421 static rtx find_insn_list PROTO ((rtx, rtx));
422 static int insn_unit PROTO ((rtx));
423 static unsigned int blockage_range PROTO ((int, rtx));
424 static void clear_units PROTO ((void));
425 static int actual_hazard_this_instance PROTO ((int, int, rtx, int, int));
426 static void schedule_unit PROTO ((int, rtx, int));
427 static int actual_hazard PROTO ((int, rtx, int, int));
428 static int potential_hazard PROTO ((int, rtx, int));
429 static int insn_cost PROTO ((rtx, rtx, rtx));
430 static int priority PROTO ((rtx));
431 static void free_pending_lists PROTO ((void));
432 static void add_insn_mem_dependence PROTO ((rtx *, rtx *, rtx, rtx));
433 static void flush_pending_lists PROTO ((rtx, int));
434 static void sched_analyze_1 PROTO ((rtx, rtx));
435 static void sched_analyze_2 PROTO ((rtx, rtx));
436 static void sched_analyze_insn PROTO ((rtx, rtx, rtx));
437 static void sched_analyze PROTO ((rtx, rtx));
438 static void sched_note_set PROTO ((rtx, int));
439 static int rank_for_schedule PROTO ((const GENERIC_PTR, const GENERIC_PTR));
440 static void swap_sort PROTO ((rtx *, int));
441 static void queue_insn PROTO ((rtx, int));
442 static int schedule_insn PROTO ((rtx, rtx *, int, int));
443 static void create_reg_dead_note PROTO ((rtx, rtx));
444 static void attach_deaths PROTO ((rtx, rtx, int));
445 static void attach_deaths_insn PROTO ((rtx));
446 static int new_sometimes_live PROTO ((struct sometimes *, int, int));
447 static void finish_sometimes_live PROTO ((struct sometimes *, int));
448 static int schedule_block PROTO ((int, int));
449 static rtx regno_use_in PROTO ((int, rtx));
450 static void split_hard_reg_notes PROTO ((rtx, rtx, rtx));
451 static void new_insn_dead_notes PROTO ((rtx, rtx, rtx, rtx));
452 static void update_n_sets PROTO ((rtx, int));
453 static void update_flow_info PROTO ((rtx, rtx, rtx, rtx));
454 static char *safe_concat PROTO ((char *, char *, char *));
456 /* Main entry point of this file. */
457 void schedule_insns PROTO ((FILE *));
459 /* Mapping of insns to their original block prior to scheduling. */
460 static int *insn_orig_block;
461 #define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
463 /* Some insns (e.g. call) are not allowed to move across blocks. */
464 static char *cant_move;
465 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
467 /* Control flow graph edges are kept in circular lists. */
476 static edge *edge_table;
478 #define NEXT_IN(edge) (edge_table[edge].next_in)
479 #define NEXT_OUT(edge) (edge_table[edge].next_out)
480 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
481 #define TO_BLOCK(edge) (edge_table[edge].to_block)
483 /* Number of edges in the control flow graph. (in fact larger than
484 that by 1, since edge 0 is unused.) */
487 /* Circular list of incoming/outgoing edges of a block */
488 static int *in_edges;
489 static int *out_edges;
491 #define IN_EDGES(block) (in_edges[block])
492 #define OUT_EDGES(block) (out_edges[block])
494 /* List of labels which cannot be deleted, needed for control
495 flow graph construction. */
496 extern rtx forced_labels;
499 static int is_cfg_nonregular PROTO ((void));
500 static int build_control_flow PROTO ((int_list_ptr *, int_list_ptr *,
502 static void new_edge PROTO ((int, int));
505 /* A region is the main entity for interblock scheduling: insns
506 are allowed to move between blocks in the same region, along
507 control flow graph edges, in the 'up' direction. */
510 int rgn_nr_blocks; /* number of blocks in region */
511 int rgn_blocks; /* blocks in the region (actually index in rgn_bb_table) */
515 /* Number of regions in the procedure */
516 static int nr_regions;
518 /* Table of region descriptions */
519 static region *rgn_table;
521 /* Array of lists of regions' blocks */
522 static int *rgn_bb_table;
524 /* Topological order of blocks in the region (if b2 is reachable from
525 b1, block_to_bb[b2] > block_to_bb[b1]).
526 Note: A basic block is always referred to by either block or b,
527 while its topological order name (in the region) is refered to by
530 static int *block_to_bb;
532 /* The number of the region containing a block. */
533 static int *containing_rgn;
535 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
536 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
537 #define BLOCK_TO_BB(block) (block_to_bb[block])
538 #define CONTAINING_RGN(block) (containing_rgn[block])
540 void debug_regions PROTO ((void));
541 static void find_single_block_region PROTO ((void));
542 static void find_rgns PROTO ((int_list_ptr *, int_list_ptr *,
543 int *, int *, sbitmap *));
544 static int too_large PROTO ((int, int *, int *));
546 extern void debug_live PROTO ((int, int));
548 /* Blocks of the current region being scheduled. */
549 static int current_nr_blocks;
550 static int current_blocks;
552 /* The mapping from bb to block */
553 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
556 /* Bit vectors and bitset operations are needed for computations on
557 the control flow graph. */
559 typedef unsigned HOST_WIDE_INT *bitset;
562 int *first_member; /* pointer to the list start in bitlst_table. */
563 int nr_members; /* the number of members of the bit list. */
567 static int bitlst_table_last;
568 static int bitlst_table_size;
569 static int *bitlst_table;
571 static char bitset_member PROTO ((bitset, int, int));
572 static void extract_bitlst PROTO ((bitset, int, bitlst *));
574 /* target info declarations.
576 The block currently being scheduled is referred to as the "target" block,
577 while other blocks in the region from which insns can be moved to the
578 target are called "source" blocks. The candidate structure holds info
579 about such sources: are they valid? Speculative? Etc. */
580 typedef bitlst bblst;
591 static candidate *candidate_table;
593 /* A speculative motion requires checking live information on the path
594 from 'source' to 'target'. The split blocks are those to be checked.
595 After a speculative motion, live information should be modified in
598 Lists of split and update blocks for each candidate of the current
599 target are in array bblst_table */
600 static int *bblst_table, bblst_size, bblst_last;
602 #define IS_VALID(src) ( candidate_table[src].is_valid )
603 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
604 #define SRC_PROB(src) ( candidate_table[src].src_prob )
606 /* The bb being currently scheduled. */
607 static int target_bb;
610 typedef bitlst edgelst;
612 /* target info functions */
613 static void split_edges PROTO ((int, int, edgelst *));
614 static void compute_trg_info PROTO ((int));
615 void debug_candidate PROTO ((int));
616 void debug_candidates PROTO ((int));
619 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
620 typedef bitset bbset;
622 /* Number of words of the bbset. */
623 static int bbset_size;
625 /* Dominators array: dom[i] contains the bbset of dominators of
626 bb i in the region. */
629 /* bb 0 is the only region entry */
630 #define IS_RGN_ENTRY(bb) (!bb)
632 /* Is bb_src dominated by bb_trg. */
633 #define IS_DOMINATED(bb_src, bb_trg) \
634 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
636 /* Probability: Prob[i] is a float in [0, 1] which is the probability
637 of bb i relative to the region entry. */
640 /* The probability of bb_src, relative to bb_trg. Note, that while the
641 'prob[bb]' is a float in [0, 1], this macro returns an integer
643 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
646 /* Bit-set of edges, where bit i stands for edge i. */
647 typedef bitset edgeset;
649 /* Number of edges in the region. */
650 static int rgn_nr_edges;
652 /* Array of size rgn_nr_edges. */
653 static int *rgn_edges;
655 /* Number of words in an edgeset. */
656 static int edgeset_size;
658 /* Mapping from each edge in the graph to its number in the rgn. */
659 static int *edge_to_bit;
660 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
662 /* The split edges of a source bb is different for each target
663 bb. In order to compute this efficiently, the 'potential-split edges'
664 are computed for each bb prior to scheduling a region. This is actually
665 the split edges of each bb relative to the region entry.
667 pot_split[bb] is the set of potential split edges of bb. */
668 static edgeset *pot_split;
670 /* For every bb, a set of its ancestor edges. */
671 static edgeset *ancestor_edges;
673 static void compute_dom_prob_ps PROTO ((int));
675 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
676 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
677 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
678 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
680 /* parameters affecting the decision of rank_for_schedule() */
681 #define MIN_DIFF_PRIORITY 2
682 #define MIN_PROBABILITY 40
683 #define MIN_PROB_DIFF 10
685 /* speculative scheduling functions */
686 static int check_live_1 PROTO ((int, rtx));
687 static void update_live_1 PROTO ((int, rtx));
688 static int check_live PROTO ((rtx, int));
689 static void update_live PROTO ((rtx, int));
690 static void set_spec_fed PROTO ((rtx));
691 static int is_pfree PROTO ((rtx, int, int));
692 static int find_conditional_protection PROTO ((rtx, int));
693 static int is_conditionally_protected PROTO ((rtx, int, int));
694 static int may_trap_exp PROTO ((rtx, int));
695 static int haifa_classify_insn PROTO ((rtx));
696 static int is_prisky PROTO ((rtx, int, int));
697 static int is_exception_free PROTO ((rtx, int, int));
699 static char find_insn_mem_list PROTO ((rtx, rtx, rtx, rtx));
700 static void compute_block_forward_dependences PROTO ((int));
701 static void init_rgn_data_dependences PROTO ((int));
702 static void add_branch_dependences PROTO ((rtx, rtx));
703 static void compute_block_backward_dependences PROTO ((int));
704 void debug_dependencies PROTO ((void));
706 /* Notes handling mechanism:
707 =========================
708 Generally, NOTES are saved before scheduling and restored after scheduling.
709 The scheduler distinguishes between three types of notes:
711 (1) LINE_NUMBER notes, generated and used for debugging. Here,
712 before scheduling a region, a pointer to the LINE_NUMBER note is
713 added to the insn following it (in save_line_notes()), and the note
714 is removed (in rm_line_notes() and unlink_line_notes()). After
715 scheduling the region, this pointer is used for regeneration of
716 the LINE_NUMBER note (in restore_line_notes()).
718 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
719 Before scheduling a region, a pointer to the note is added to the insn
720 that follows or precedes it. (This happens as part of the data dependence
721 computation). After scheduling an insn, the pointer contained in it is
722 used for regenerating the corresponding note (in reemit_notes).
724 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
725 these notes are put in a list (in rm_other_notes() and
726 unlink_other_notes ()). After scheduling the block, these notes are
727 inserted at the beginning of the block (in schedule_block()). */
729 static rtx unlink_other_notes PROTO ((rtx, rtx));
730 static rtx unlink_line_notes PROTO ((rtx, rtx));
731 static void rm_line_notes PROTO ((int));
732 static void save_line_notes PROTO ((int));
733 static void restore_line_notes PROTO ((int));
734 static void rm_redundant_line_notes PROTO ((void));
735 static void rm_other_notes PROTO ((rtx, rtx));
736 static rtx reemit_notes PROTO ((rtx, rtx));
738 static void get_block_head_tail PROTO ((int, rtx *, rtx *));
740 static void find_pre_sched_live PROTO ((int));
741 static void find_post_sched_live PROTO ((int));
742 static void update_reg_usage PROTO ((void));
743 static int queue_to_ready PROTO ((rtx [], int));
745 void debug_ready_list PROTO ((rtx[], int));
746 static void init_target_units PROTO (());
747 static void insn_print_units PROTO ((rtx));
748 static int get_visual_tbl_length PROTO (());
749 static void init_block_visualization PROTO (());
750 static void print_block_visualization PROTO ((int, char *));
751 static void visualize_scheduled_insns PROTO ((int, int));
752 static void visualize_no_unit PROTO ((rtx));
753 static void visualize_stall_cycles PROTO ((int, int));
754 static void print_exp PROTO ((char *, rtx, int));
755 static void print_value PROTO ((char *, rtx, int));
756 static void print_pattern PROTO ((char *, rtx, int));
757 static void print_insn PROTO ((char *, rtx, int));
758 void debug_reg_vector PROTO ((regset));
760 static rtx move_insn1 PROTO ((rtx, rtx));
761 static rtx move_insn PROTO ((rtx, rtx));
762 static rtx group_leader PROTO ((rtx));
763 static int set_priorities PROTO ((int));
764 static void init_rtx_vector PROTO ((rtx **, rtx *, int, int));
765 static void schedule_region PROTO ((int));
766 static void split_block_insns PROTO ((int));
768 #endif /* INSN_SCHEDULING */
770 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
772 /* Helper functions for instruction scheduling. */
774 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
775 static rtx unused_insn_list;
777 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
778 static rtx unused_expr_list;
780 static void free_list PROTO ((rtx *, rtx *));
781 static rtx alloc_INSN_LIST PROTO ((rtx, rtx));
782 static rtx alloc_EXPR_LIST PROTO ((int, rtx, rtx));
785 free_list (listp, unused_listp)
786 rtx *listp, *unused_listp;
788 register rtx link, prev_link;
794 link = XEXP (prev_link, 1);
799 link = XEXP (link, 1);
802 XEXP (prev_link, 1) = *unused_listp;
803 *unused_listp = *listp;
808 alloc_INSN_LIST (val, next)
813 if (unused_insn_list)
815 r = unused_insn_list;
816 unused_insn_list = XEXP (r, 1);
819 PUT_REG_NOTE_KIND (r, VOIDmode);
822 r = gen_rtx_INSN_LIST (VOIDmode, val, next);
828 alloc_EXPR_LIST (kind, val, next)
834 if (unused_insn_list)
836 r = unused_insn_list;
837 unused_insn_list = XEXP (r, 1);
840 PUT_REG_NOTE_KIND (r, kind);
843 r = gen_rtx_EXPR_LIST (kind, val, next);
848 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
849 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
850 of dependence that this link represents. */
853 add_dependence (insn, elem, dep_type)
856 enum reg_note dep_type;
860 /* Don't depend an insn on itself. */
864 /* If elem is part of a sequence that must be scheduled together, then
865 make the dependence point to the last insn of the sequence.
866 When HAVE_cc0, it is possible for NOTEs to exist between users and
867 setters of the condition codes, so we must skip past notes here.
868 Otherwise, NOTEs are impossible here. */
870 next = NEXT_INSN (elem);
873 while (next && GET_CODE (next) == NOTE)
874 next = NEXT_INSN (next);
877 if (next && SCHED_GROUP_P (next)
878 && GET_CODE (next) != CODE_LABEL)
880 /* Notes will never intervene here though, so don't bother checking
882 /* We must reject CODE_LABELs, so that we don't get confused by one
883 that has LABEL_PRESERVE_P set, which is represented by the same
884 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
886 while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
887 && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
888 next = NEXT_INSN (next);
890 /* Again, don't depend an insn on itself. */
894 /* Make the dependence to NEXT, the last insn of the group, instead
895 of the original ELEM. */
899 #ifdef INSN_SCHEDULING
900 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
901 No need for interblock dependences with calls, since
902 calls are not moved between blocks. Note: the edge where
903 elem is a CALL is still required. */
904 if (GET_CODE (insn) == CALL_INSN
905 && (INSN_BB (elem) != INSN_BB (insn)))
910 /* Check that we don't already have this dependence. */
911 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
912 if (XEXP (link, 0) == elem)
914 /* If this is a more restrictive type of dependence than the existing
915 one, then change the existing dependence to this type. */
916 if ((int) dep_type < (int) REG_NOTE_KIND (link))
917 PUT_REG_NOTE_KIND (link, dep_type);
920 /* Might want to check one level of transitivity to save conses. */
922 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
923 LOG_LINKS (insn) = link;
925 /* Insn dependency, not data dependency. */
926 PUT_REG_NOTE_KIND (link, dep_type);
929 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
930 of INSN. Abort if not found. */
933 remove_dependence (insn, elem)
937 rtx prev, link, next;
940 for (prev = 0, link = LOG_LINKS (insn); link; link = next)
942 next = XEXP (link, 1);
943 if (XEXP (link, 0) == elem)
946 XEXP (prev, 1) = next;
948 LOG_LINKS (insn) = next;
950 XEXP (link, 1) = unused_insn_list;
951 unused_insn_list = link;
964 #ifndef INSN_SCHEDULING
966 schedule_insns (dump_file)
976 #define HAIFA_INLINE __inline
979 /* Computation of memory dependencies. */
981 /* The *_insns and *_mems are paired lists. Each pending memory operation
982 will have a pointer to the MEM rtx on one list and a pointer to the
983 containing insn on the other list in the same place in the list. */
985 /* We can't use add_dependence like the old code did, because a single insn
986 may have multiple memory accesses, and hence needs to be on the list
987 once for each memory access. Add_dependence won't let you add an insn
988 to a list more than once. */
990 /* An INSN_LIST containing all insns with pending read operations. */
991 static rtx pending_read_insns;
993 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
994 static rtx pending_read_mems;
996 /* An INSN_LIST containing all insns with pending write operations. */
997 static rtx pending_write_insns;
999 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
1000 static rtx pending_write_mems;
1002 /* Indicates the combined length of the two pending lists. We must prevent
1003 these lists from ever growing too large since the number of dependencies
1004 produced is at least O(N*N), and execution time is at least O(4*N*N), as
1005 a function of the length of these pending lists. */
1007 static int pending_lists_length;
1009 /* The last insn upon which all memory references must depend.
1010 This is an insn which flushed the pending lists, creating a dependency
1011 between it and all previously pending memory references. This creates
1012 a barrier (or a checkpoint) which no memory reference is allowed to cross.
1014 This includes all non constant CALL_INSNs. When we do interprocedural
1015 alias analysis, this restriction can be relaxed.
1016 This may also be an INSN that writes memory if the pending lists grow
1019 static rtx last_pending_memory_flush;
1021 /* The last function call we have seen. All hard regs, and, of course,
1022 the last function call, must depend on this. */
1024 static rtx last_function_call;
1026 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
1027 that does not already cross a call. We create dependencies between each
1028 of those insn and the next call insn, to ensure that they won't cross a call
1029 after scheduling is done. */
1031 static rtx sched_before_next_call;
1033 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1034 so that insns independent of the last scheduled insn will be preferred
1035 over dependent instructions. */
1037 static rtx last_scheduled_insn;
1039 /* Data structures for the computation of data dependences in a regions. We
1040 keep one copy of each of the declared above variables for each bb in the
1041 region. Before analyzing the data dependences for a bb, its variables
1042 are initialized as a function of the variables of its predecessors. When
1043 the analysis for a bb completes, we save the contents of each variable X
1044 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
1045 copied to bb_pending_read_insns[bb]. Another change is that few
1046 variables are now a list of insns rather than a single insn:
1047 last_pending_memory_flash, last_function_call, reg_last_sets. The
1048 manipulation of these variables was changed appropriately. */
1050 static rtx **bb_reg_last_uses;
1051 static rtx **bb_reg_last_sets;
1053 static rtx *bb_pending_read_insns;
1054 static rtx *bb_pending_read_mems;
1055 static rtx *bb_pending_write_insns;
1056 static rtx *bb_pending_write_mems;
1057 static int *bb_pending_lists_length;
1059 static rtx *bb_last_pending_memory_flush;
1060 static rtx *bb_last_function_call;
1061 static rtx *bb_sched_before_next_call;
1063 /* functions for construction of the control flow graph. */
1065 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1067 We decide not to build the control flow graph if there is possibly more
1068 than one entry to the function, if computed branches exist, of if we
1069 have nonlocal gotos. */
1072 is_cfg_nonregular ()
1078 /* If we have a label that could be the target of a nonlocal goto, then
1079 the cfg is not well structured. */
1080 if (nonlocal_label_rtx_list () != NULL)
1083 /* If we have any forced labels, then the cfg is not well structured. */
1087 /* If this function has a computed jump, then we consider the cfg
1088 not well structured. */
1089 if (current_function_has_computed_jump)
1092 /* If we have exception handlers, then we consider the cfg not well
1093 structured. ?!? We should be able to handle this now that flow.c
1094 computes an accurate cfg for EH. */
1095 if (exception_handler_labels)
1098 /* If we have non-jumping insns which refer to labels, then we consider
1099 the cfg not well structured. */
1100 /* check for labels referred to other thn by jumps */
1101 for (b = 0; b < n_basic_blocks; b++)
1102 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
1104 code = GET_CODE (insn);
1105 if (GET_RTX_CLASS (code) == 'i')
1109 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1110 if (REG_NOTE_KIND (note) == REG_LABEL)
1114 if (insn == basic_block_end[b])
1118 /* All the tests passed. Consider the cfg well structured. */
1122 /* Build the control flow graph and set nr_edges.
1124 Instead of trying to build a cfg ourselves, we rely on flow to
1125 do it for us. Stamp out useless code (and bug) duplication.
1127 Return nonzero if an irregularity in the cfg is found which would
1128 prevent cross block scheduling. */
1131 build_control_flow (s_preds, s_succs, num_preds, num_succs)
1132 int_list_ptr *s_preds;
1133 int_list_ptr *s_succs;
1141 /* Count the number of edges in the cfg. */
1144 for (i = 0; i < n_basic_blocks; i++)
1146 nr_edges += num_succs[i];
1148 /* Unreachable loops with more than one basic block are detected
1149 during the DFS traversal in find_rgns.
1151 Unreachable loops with a single block are detected here. This
1152 test is redundant with the one in find_rgns, but it's much
1153 cheaper to go ahead and catch the trivial case here. */
1154 if (num_preds[i] == 0
1155 || (num_preds[i] == 1 && INT_LIST_VAL (s_preds[i]) == i))
1159 /* Account for entry/exit edges. */
1162 in_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
1163 out_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
1164 bzero ((char *) in_edges, n_basic_blocks * sizeof (int));
1165 bzero ((char *) out_edges, n_basic_blocks * sizeof (int));
1167 edge_table = (edge *) xmalloc ((nr_edges) * sizeof (edge));
1168 bzero ((char *) edge_table, ((nr_edges) * sizeof (edge)));
1171 for (i = 0; i < n_basic_blocks; i++)
1172 for (succ = s_succs[i]; succ; succ = succ->next)
1174 if (INT_LIST_VAL (succ) != EXIT_BLOCK)
1175 new_edge (i, INT_LIST_VAL (succ));
1178 /* increment by 1, since edge 0 is unused. */
1185 /* Record an edge in the control flow graph from SOURCE to TARGET.
1187 In theory, this is redundant with the s_succs computed above, but
1188 we have not converted all of haifa to use information from the
1192 new_edge (source, target)
1196 int curr_edge, fst_edge;
1198 /* check for duplicates */
1199 fst_edge = curr_edge = OUT_EDGES (source);
1202 if (FROM_BLOCK (curr_edge) == source
1203 && TO_BLOCK (curr_edge) == target)
1208 curr_edge = NEXT_OUT (curr_edge);
1210 if (fst_edge == curr_edge)
1216 FROM_BLOCK (e) = source;
1217 TO_BLOCK (e) = target;
1219 if (OUT_EDGES (source))
1221 next_edge = NEXT_OUT (OUT_EDGES (source));
1222 NEXT_OUT (OUT_EDGES (source)) = e;
1223 NEXT_OUT (e) = next_edge;
1227 OUT_EDGES (source) = e;
1231 if (IN_EDGES (target))
1233 next_edge = NEXT_IN (IN_EDGES (target));
1234 NEXT_IN (IN_EDGES (target)) = e;
1235 NEXT_IN (e) = next_edge;
1239 IN_EDGES (target) = e;
1245 /* BITSET macros for operations on the control flow graph. */
1247 /* Compute bitwise union of two bitsets. */
1248 #define BITSET_UNION(set1, set2, len) \
1249 do { register bitset tp = set1, sp = set2; \
1251 for (i = 0; i < len; i++) \
1252 *(tp++) |= *(sp++); } while (0)
1254 /* Compute bitwise intersection of two bitsets. */
1255 #define BITSET_INTER(set1, set2, len) \
1256 do { register bitset tp = set1, sp = set2; \
1258 for (i = 0; i < len; i++) \
1259 *(tp++) &= *(sp++); } while (0)
1261 /* Compute bitwise difference of two bitsets. */
1262 #define BITSET_DIFFER(set1, set2, len) \
1263 do { register bitset tp = set1, sp = set2; \
1265 for (i = 0; i < len; i++) \
1266 *(tp++) &= ~*(sp++); } while (0)
1268 /* Inverts every bit of bitset 'set' */
1269 #define BITSET_INVERT(set, len) \
1270 do { register bitset tmpset = set; \
1272 for (i = 0; i < len; i++, tmpset++) \
1273 *tmpset = ~*tmpset; } while (0)
1275 /* Turn on the index'th bit in bitset set. */
1276 #define BITSET_ADD(set, index, len) \
1278 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1281 set[index/HOST_BITS_PER_WIDE_INT] |= \
1282 1 << (index % HOST_BITS_PER_WIDE_INT); \
1285 /* Turn off the index'th bit in set. */
1286 #define BITSET_REMOVE(set, index, len) \
1288 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1291 set[index/HOST_BITS_PER_WIDE_INT] &= \
1292 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1296 /* Check if the index'th bit in bitset set is on. */
1299 bitset_member (set, index, len)
1303 if (index >= HOST_BITS_PER_WIDE_INT * len)
1305 return (set[index / HOST_BITS_PER_WIDE_INT] &
1306 1 << (index % HOST_BITS_PER_WIDE_INT)) ? 1 : 0;
1310 /* Translate a bit-set SET to a list BL of the bit-set members. */
1313 extract_bitlst (set, len, bl)
1319 unsigned HOST_WIDE_INT word;
1321 /* bblst table space is reused in each call to extract_bitlst */
1322 bitlst_table_last = 0;
1324 bl->first_member = &bitlst_table[bitlst_table_last];
1327 for (i = 0; i < len; i++)
1330 offset = i * HOST_BITS_PER_WIDE_INT;
1331 for (j = 0; word; j++)
1335 bitlst_table[bitlst_table_last++] = offset;
1346 /* functions for the construction of regions */
1348 /* Print the regions, for debugging purposes. Callable from debugger. */
1355 fprintf (dump, "\n;; ------------ REGIONS ----------\n\n");
1356 for (rgn = 0; rgn < nr_regions; rgn++)
1358 fprintf (dump, ";;\trgn %d nr_blocks %d:\n", rgn,
1359 rgn_table[rgn].rgn_nr_blocks);
1360 fprintf (dump, ";;\tbb/block: ");
1362 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
1364 current_blocks = RGN_BLOCKS (rgn);
1366 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
1369 fprintf (dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
1372 fprintf (dump, "\n\n");
1377 /* Build a single block region for each basic block in the function.
1378 This allows for using the same code for interblock and basic block
1382 find_single_block_region ()
1386 for (i = 0; i < n_basic_blocks; i++)
1388 rgn_bb_table[i] = i;
1389 RGN_NR_BLOCKS (i) = 1;
1391 CONTAINING_RGN (i) = i;
1392 BLOCK_TO_BB (i) = 0;
1394 nr_regions = n_basic_blocks;
1398 /* Update number of blocks and the estimate for number of insns
1399 in the region. Return 1 if the region is "too large" for interblock
1400 scheduling (compile time considerations), otherwise return 0. */
1403 too_large (block, num_bbs, num_insns)
1404 int block, *num_bbs, *num_insns;
1407 (*num_insns) += (INSN_LUID (basic_block_end[block]) -
1408 INSN_LUID (basic_block_head[block]));
1409 if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
1416 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1417 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1418 loop containing blk. */
1419 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1421 if (max_hdr[blk] == -1) \
1422 max_hdr[blk] = hdr; \
1423 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1424 RESET_BIT (inner, hdr); \
1425 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1427 RESET_BIT (inner,max_hdr[blk]); \
1428 max_hdr[blk] = hdr; \
1433 /* Find regions for interblock scheduling.
1435 A region for scheduling can be:
1437 * A loop-free procedure, or
1439 * A reducible inner loop, or
1441 * A basic block not contained in any other region.
1444 ?!? In theory we could build other regions based on extended basic
1445 blocks or reverse extended basic blocks. Is it worth the trouble?
1447 Loop blocks that form a region are put into the region's block list
1448 in topological order.
1450 This procedure stores its results into the following global (ick) variables
1459 We use dominator relationships to avoid making regions out of non-reducible
1462 This procedure needs to be converted to work on pred/succ lists instead
1463 of edge tables. That would simplify it somewhat. */
1466 find_rgns (s_preds, s_succs, num_preds, num_succs, dom)
1467 int_list_ptr *s_preds;
1468 int_list_ptr *s_succs;
1473 int *max_hdr, *dfs_nr, *stack, *queue, *degree;
1475 int node, child, loop_head, i, head, tail;
1476 int count = 0, sp, idx = 0, current_edge = out_edges[0];
1477 int num_bbs, num_insns, unreachable;
1478 int too_large_failure;
1480 /* Note if an edge has been passed. */
1483 /* Note if a block is a natural loop header. */
1486 /* Note if a block is an natural inner loop header. */
1489 /* Note if a block is in the block queue. */
1492 /* Note if a block is in the block queue. */
1495 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1496 and a mapping from block to its loop header (if the block is contained
1497 in a loop, else -1).
1499 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1500 be used as inputs to the second traversal.
1502 STACK, SP and DFS_NR are only used during the first traversal. */
1504 /* Allocate and initialize variables for the first traversal. */
1505 max_hdr = (int *) alloca (n_basic_blocks * sizeof (int));
1506 dfs_nr = (int *) alloca (n_basic_blocks * sizeof (int));
1507 bzero ((char *) dfs_nr, n_basic_blocks * sizeof (int));
1508 stack = (int *) alloca (nr_edges * sizeof (int));
1510 inner = sbitmap_alloc (n_basic_blocks);
1511 sbitmap_ones (inner);
1513 header = sbitmap_alloc (n_basic_blocks);
1514 sbitmap_zero (header);
1516 passed = sbitmap_alloc (nr_edges);
1517 sbitmap_zero (passed);
1519 in_queue = sbitmap_alloc (n_basic_blocks);
1520 sbitmap_zero (in_queue);
1522 in_stack = sbitmap_alloc (n_basic_blocks);
1523 sbitmap_zero (in_stack);
1525 for (i = 0; i < n_basic_blocks; i++)
1528 /* DFS traversal to find inner loops in the cfg. */
1533 if (current_edge == 0 || TEST_BIT (passed, current_edge))
1535 /* We have reached a leaf node or a node that was already
1536 processed. Pop edges off the stack until we find
1537 an edge that has not yet been processed. */
1539 && (current_edge == 0 || TEST_BIT (passed, current_edge)))
1541 /* Pop entry off the stack. */
1542 current_edge = stack[sp--];
1543 node = FROM_BLOCK (current_edge);
1544 child = TO_BLOCK (current_edge);
1545 RESET_BIT (in_stack, child);
1546 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1547 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1548 current_edge = NEXT_OUT (current_edge);
1551 /* See if have finished the DFS tree traversal. */
1552 if (sp < 0 && TEST_BIT (passed, current_edge))
1555 /* Nope, continue the traversal with the popped node. */
1559 /* Process a node. */
1560 node = FROM_BLOCK (current_edge);
1561 child = TO_BLOCK (current_edge);
1562 SET_BIT (in_stack, node);
1563 dfs_nr[node] = ++count;
1565 /* If the successor is in the stack, then we've found a loop.
1566 Mark the loop, if it is not a natural loop, then it will
1567 be rejected during the second traversal. */
1568 if (TEST_BIT (in_stack, child))
1571 SET_BIT (header, child);
1572 UPDATE_LOOP_RELATIONS (node, child);
1573 SET_BIT (passed, current_edge);
1574 current_edge = NEXT_OUT (current_edge);
1578 /* If the child was already visited, then there is no need to visit
1579 it again. Just update the loop relationships and restart
1583 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1584 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1585 SET_BIT (passed, current_edge);
1586 current_edge = NEXT_OUT (current_edge);
1590 /* Push an entry on the stack and continue DFS traversal. */
1591 stack[++sp] = current_edge;
1592 SET_BIT (passed, current_edge);
1593 current_edge = OUT_EDGES (child);
1596 /* Another check for unreachable blocks. The earlier test in
1597 is_cfg_nonregular only finds unreachable blocks that do not
1600 The DFS traversal will mark every block that is reachable from
1601 the entry node by placing a nonzero value in dfs_nr. Thus if
1602 dfs_nr is zero for any block, then it must be unreachable. */
1604 for (i = 0; i < n_basic_blocks; i++)
1611 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1612 to hold degree counts. */
1615 /* Compute the in-degree of every block in the graph */
1616 for (i = 0; i < n_basic_blocks; i++)
1617 degree[i] = num_preds[i];
1619 /* Do not perform region scheduling if there are any unreachable
1624 SET_BIT (header, 0);
1626 /* Second travsersal:find reducible inner loops and topologically sort
1627 block of each region. */
1629 queue = (int *) alloca (n_basic_blocks * sizeof (int));
1631 /* Find blocks which are inner loop headers. We still have non-reducible
1632 loops to consider at this point. */
1633 for (i = 0; i < n_basic_blocks; i++)
1635 if (TEST_BIT (header, i) && TEST_BIT (inner, i))
1640 /* Now check that the loop is reducible. We do this separate
1641 from finding inner loops so that we do not find a reducible
1642 loop which contains an inner non-reducible loop.
1644 A simple way to find reducible/natrual loops is to verify
1645 that each block in the loop is dominated by the loop
1648 If there exists a block that is not dominated by the loop
1649 header, then the block is reachable from outside the loop
1650 and thus the loop is not a natural loop. */
1651 for (j = 0; j < n_basic_blocks; j++)
1653 /* First identify blocks in the loop, except for the loop
1655 if (i == max_hdr[j] && i != j)
1657 /* Now verify that the block is dominated by the loop
1659 if (!TEST_BIT (dom[j], i))
1664 /* If we exited the loop early, then I is the header of a non
1665 reducible loop and we should quit processing it now. */
1666 if (j != n_basic_blocks)
1669 /* I is a header of an inner loop, or block 0 in a subroutine
1670 with no loops at all. */
1672 too_large_failure = 0;
1673 loop_head = max_hdr[i];
1675 /* Decrease degree of all I's successors for topological
1677 for (ps = s_succs[i]; ps; ps = ps->next)
1678 if (INT_LIST_VAL (ps) != EXIT_BLOCK
1679 && INT_LIST_VAL (ps) != ENTRY_BLOCK)
1680 --degree[INT_LIST_VAL(ps)];
1682 /* Estimate # insns, and count # blocks in the region. */
1684 num_insns = (INSN_LUID (basic_block_end[i])
1685 - INSN_LUID (basic_block_head[i]));
1688 /* Find all loop latches (blocks which back edges to the loop
1689 header) or all the leaf blocks in the cfg has no loops.
1691 Place those blocks into the queue. */
1694 for (j = 0; j < n_basic_blocks; j++)
1695 /* Leaf nodes have only a single successor which must
1697 if (num_succs[j] == 1
1698 && INT_LIST_VAL (s_succs[j]) == EXIT_BLOCK)
1701 SET_BIT (in_queue, j);
1703 if (too_large (j, &num_bbs, &num_insns))
1705 too_large_failure = 1;
1714 for (ps = s_preds[i]; ps; ps = ps->next)
1716 node = INT_LIST_VAL (ps);
1718 if (node == ENTRY_BLOCK || node == EXIT_BLOCK)
1721 if (max_hdr[node] == loop_head && node != i)
1723 /* This is a loop latch. */
1724 queue[++tail] = node;
1725 SET_BIT (in_queue, node);
1727 if (too_large (node, &num_bbs, &num_insns))
1729 too_large_failure = 1;
1737 /* Now add all the blocks in the loop to the queue.
1739 We know the loop is a natural loop; however the algorithm
1740 above will not always mark certain blocks as being in the
1749 The algorithm in the DFS traversal may not mark B & D as part
1750 of the loop (ie they will not have max_hdr set to A).
1752 We know they can not be loop latches (else they would have
1753 had max_hdr set since they'd have a backedge to a dominator
1754 block). So we don't need them on the initial queue.
1756 We know they are part of the loop because they are dominated
1757 by the loop header and can be reached by a backwards walk of
1758 the edges starting with nodes on the initial queue.
1760 It is safe and desirable to include those nodes in the
1761 loop/scheduling region. To do so we would need to decrease
1762 the degree of a node if it is the target of a backedge
1763 within the loop itself as the node is placed in the queue.
1765 We do not do this because I'm not sure that the actual
1766 scheduling code will properly handle this case. ?!? */
1768 while (head < tail && !too_large_failure)
1771 child = queue[++head];
1773 for (ps = s_preds[child]; ps; ps = ps->next)
1775 node = INT_LIST_VAL (ps);
1777 /* See discussion above about nodes not marked as in
1778 this loop during the initial DFS traversal. */
1779 if (node == ENTRY_BLOCK || node == EXIT_BLOCK
1780 || max_hdr[node] != loop_head)
1785 else if (!TEST_BIT (in_queue, node) && node != i)
1787 queue[++tail] = node;
1788 SET_BIT (in_queue, node);
1790 if (too_large (node, &num_bbs, &num_insns))
1792 too_large_failure = 1;
1799 if (tail >= 0 && !too_large_failure)
1801 /* Place the loop header into list of region blocks. */
1803 rgn_bb_table[idx] = i;
1804 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1805 RGN_BLOCKS (nr_regions) = idx++;
1806 CONTAINING_RGN (i) = nr_regions;
1807 BLOCK_TO_BB (i) = count = 0;
1809 /* Remove blocks from queue[] when their in degree becomes
1810 zero. Repeat until no blocks are left on the list. This
1811 produces a topological list of blocks in the region. */
1818 child = queue[head];
1819 if (degree[child] == 0)
1822 rgn_bb_table[idx++] = child;
1823 BLOCK_TO_BB (child) = ++count;
1824 CONTAINING_RGN (child) = nr_regions;
1825 queue[head] = queue[tail--];
1827 for (ps = s_succs[child]; ps; ps = ps->next)
1828 if (INT_LIST_VAL (ps) != ENTRY_BLOCK
1829 && INT_LIST_VAL (ps) != EXIT_BLOCK)
1830 --degree[INT_LIST_VAL (ps)];
1841 /* Any block that did not end up in a region is placed into a region
1843 for (i = 0; i < n_basic_blocks; i++)
1846 rgn_bb_table[idx] = i;
1847 RGN_NR_BLOCKS (nr_regions) = 1;
1848 RGN_BLOCKS (nr_regions) = idx++;
1849 CONTAINING_RGN (i) = nr_regions++;
1850 BLOCK_TO_BB (i) = 0;
1861 /* functions for regions scheduling information */
1863 /* Compute dominators, probability, and potential-split-edges of bb.
1864 Assume that these values were already computed for bb's predecessors. */
1867 compute_dom_prob_ps (bb)
1870 int nxt_in_edge, fst_in_edge, pred;
1871 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1874 if (IS_RGN_ENTRY (bb))
1876 BITSET_ADD (dom[bb], 0, bbset_size);
1881 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1883 /* intialize dom[bb] to '111..1' */
1884 BITSET_INVERT (dom[bb], bbset_size);
1888 pred = FROM_BLOCK (nxt_in_edge);
1889 BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
1891 BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
1894 BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
1897 nr_rgn_out_edges = 0;
1898 fst_out_edge = OUT_EDGES (pred);
1899 nxt_out_edge = NEXT_OUT (fst_out_edge);
1900 BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
1903 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
1905 /* the successor doesn't belong the region? */
1906 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1907 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1910 while (fst_out_edge != nxt_out_edge)
1913 /* the successor doesn't belong the region? */
1914 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1915 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1917 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
1918 nxt_out_edge = NEXT_OUT (nxt_out_edge);
1922 /* now nr_rgn_out_edges is the number of region-exit edges from pred,
1923 and nr_out_edges will be the number of pred out edges not leaving
1925 nr_out_edges -= nr_rgn_out_edges;
1926 if (nr_rgn_out_edges > 0)
1927 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1929 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1930 nxt_in_edge = NEXT_IN (nxt_in_edge);
1932 while (fst_in_edge != nxt_in_edge);
1934 BITSET_ADD (dom[bb], bb, bbset_size);
1935 BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
1937 if (sched_verbose >= 2)
1938 fprintf (dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb), (int) (100.0 * prob[bb]));
1939 } /* compute_dom_prob_ps */
1941 /* functions for target info */
1943 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1944 Note that bb_trg dominates bb_src. */
1947 split_edges (bb_src, bb_trg, bl)
1952 int es = edgeset_size;
1953 edgeset src = (edgeset) alloca (es * sizeof (HOST_WIDE_INT));
1956 src[es] = (pot_split[bb_src])[es];
1957 BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
1958 extract_bitlst (src, edgeset_size, bl);
1962 /* Find the valid candidate-source-blocks for the target block TRG, compute
1963 their probability, and check if they are speculative or not.
1964 For speculative sources, compute their update-blocks and split-blocks. */
1967 compute_trg_info (trg)
1970 register candidate *sp;
1972 int check_block, update_idx;
1973 int i, j, k, fst_edge, nxt_edge;
1975 /* define some of the fields for the target bb as well */
1976 sp = candidate_table + trg;
1978 sp->is_speculative = 0;
1981 for (i = trg + 1; i < current_nr_blocks; i++)
1983 sp = candidate_table + i;
1985 sp->is_valid = IS_DOMINATED (i, trg);
1988 sp->src_prob = GET_SRC_PROB (i, trg);
1989 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
1994 split_edges (i, trg, &el);
1995 sp->is_speculative = (el.nr_members) ? 1 : 0;
1996 if (sp->is_speculative && !flag_schedule_speculative)
2002 sp->split_bbs.first_member = &bblst_table[bblst_last];
2003 sp->split_bbs.nr_members = el.nr_members;
2004 for (j = 0; j < el.nr_members; bblst_last++, j++)
2005 bblst_table[bblst_last] =
2006 TO_BLOCK (rgn_edges[el.first_member[j]]);
2007 sp->update_bbs.first_member = &bblst_table[bblst_last];
2009 for (j = 0; j < el.nr_members; j++)
2011 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
2012 fst_edge = nxt_edge = OUT_EDGES (check_block);
2015 for (k = 0; k < el.nr_members; k++)
2016 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
2019 if (k >= el.nr_members)
2021 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
2025 nxt_edge = NEXT_OUT (nxt_edge);
2027 while (fst_edge != nxt_edge);
2029 sp->update_bbs.nr_members = update_idx;
2034 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
2036 sp->is_speculative = 0;
2040 } /* compute_trg_info */
2043 /* Print candidates info, for debugging purposes. Callable from debugger. */
2049 if (!candidate_table[i].is_valid)
2052 if (candidate_table[i].is_speculative)
2055 fprintf (dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
2057 fprintf (dump, "split path: ");
2058 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
2060 int b = candidate_table[i].split_bbs.first_member[j];
2062 fprintf (dump, " %d ", b);
2064 fprintf (dump, "\n");
2066 fprintf (dump, "update path: ");
2067 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
2069 int b = candidate_table[i].update_bbs.first_member[j];
2071 fprintf (dump, " %d ", b);
2073 fprintf (dump, "\n");
2077 fprintf (dump, " src %d equivalent\n", BB_TO_BLOCK (i));
2082 /* Print candidates info, for debugging purposes. Callable from debugger. */
2085 debug_candidates (trg)
2090 fprintf (dump, "----------- candidate table: target: b=%d bb=%d ---\n",
2091 BB_TO_BLOCK (trg), trg);
2092 for (i = trg + 1; i < current_nr_blocks; i++)
2093 debug_candidate (i);
2097 /* functions for speculative scheduing */
2099 /* Return 0 if x is a set of a register alive in the beginning of one
2100 of the split-blocks of src, otherwise return 1. */
2103 check_live_1 (src, x)
2109 register rtx reg = SET_DEST (x);
2114 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2115 || GET_CODE (reg) == SIGN_EXTRACT
2116 || GET_CODE (reg) == STRICT_LOW_PART)
2117 reg = XEXP (reg, 0);
2119 if (GET_CODE (reg) != REG)
2122 regno = REGNO (reg);
2124 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2126 /* Global registers are assumed live */
2131 if (regno < FIRST_PSEUDO_REGISTER)
2133 /* check for hard registers */
2134 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2137 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2139 int b = candidate_table[src].split_bbs.first_member[i];
2141 if (REGNO_REG_SET_P (basic_block_live_at_start[b], regno + j))
2150 /* check for psuedo registers */
2151 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2153 int b = candidate_table[src].split_bbs.first_member[i];
2155 if (REGNO_REG_SET_P (basic_block_live_at_start[b], regno))
2167 /* If x is a set of a register R, mark that R is alive in the beginning
2168 of every update-block of src. */
2171 update_live_1 (src, x)
2177 register rtx reg = SET_DEST (x);
2182 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2183 || GET_CODE (reg) == SIGN_EXTRACT
2184 || GET_CODE (reg) == STRICT_LOW_PART)
2185 reg = XEXP (reg, 0);
2187 if (GET_CODE (reg) != REG)
2190 /* Global registers are always live, so the code below does not apply
2193 regno = REGNO (reg);
2195 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
2197 if (regno < FIRST_PSEUDO_REGISTER)
2199 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2202 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2204 int b = candidate_table[src].update_bbs.first_member[i];
2206 SET_REGNO_REG_SET (basic_block_live_at_start[b], regno + j);
2212 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2214 int b = candidate_table[src].update_bbs.first_member[i];
2216 SET_REGNO_REG_SET (basic_block_live_at_start[b], regno);
2223 /* Return 1 if insn can be speculatively moved from block src to trg,
2224 otherwise return 0. Called before first insertion of insn to
2225 ready-list or before the scheduling. */
2228 check_live (insn, src)
2232 /* find the registers set by instruction */
2233 if (GET_CODE (PATTERN (insn)) == SET
2234 || GET_CODE (PATTERN (insn)) == CLOBBER)
2235 return check_live_1 (src, PATTERN (insn));
2236 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2239 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2240 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2241 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2242 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
2252 /* Update the live registers info after insn was moved speculatively from
2253 block src to trg. */
2256 update_live (insn, src)
2260 /* find the registers set by instruction */
2261 if (GET_CODE (PATTERN (insn)) == SET
2262 || GET_CODE (PATTERN (insn)) == CLOBBER)
2263 update_live_1 (src, PATTERN (insn));
2264 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2267 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2268 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2269 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2270 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
2274 /* Exception Free Loads:
2276 We define five classes of speculative loads: IFREE, IRISKY,
2277 PFREE, PRISKY, and MFREE.
2279 IFREE loads are loads that are proved to be exception-free, just
2280 by examining the load insn. Examples for such loads are loads
2281 from TOC and loads of global data.
2283 IRISKY loads are loads that are proved to be exception-risky,
2284 just by examining the load insn. Examples for such loads are
2285 volatile loads and loads from shared memory.
2287 PFREE loads are loads for which we can prove, by examining other
2288 insns, that they are exception-free. Currently, this class consists
2289 of loads for which we are able to find a "similar load", either in
2290 the target block, or, if only one split-block exists, in that split
2291 block. Load2 is similar to load1 if both have same single base
2292 register. We identify only part of the similar loads, by finding
2293 an insn upon which both load1 and load2 have a DEF-USE dependence.
2295 PRISKY loads are loads for which we can prove, by examining other
2296 insns, that they are exception-risky. Currently we have two proofs for
2297 such loads. The first proof detects loads that are probably guarded by a
2298 test on the memory address. This proof is based on the
2299 backward and forward data dependence information for the region.
2300 Let load-insn be the examined load.
2301 Load-insn is PRISKY iff ALL the following hold:
2303 - insn1 is not in the same block as load-insn
2304 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2305 - test-insn is either a compare or a branch, not in the same block as load-insn
2306 - load-insn is reachable from test-insn
2307 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2309 This proof might fail when the compare and the load are fed
2310 by an insn not in the region. To solve this, we will add to this
2311 group all loads that have no input DEF-USE dependence.
2313 The second proof detects loads that are directly or indirectly
2314 fed by a speculative load. This proof is affected by the
2315 scheduling process. We will use the flag fed_by_spec_load.
2316 Initially, all insns have this flag reset. After a speculative
2317 motion of an insn, if insn is either a load, or marked as
2318 fed_by_spec_load, we will also mark as fed_by_spec_load every
2319 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2320 load which is fed_by_spec_load is also PRISKY.
2322 MFREE (maybe-free) loads are all the remaining loads. They may be
2323 exception-free, but we cannot prove it.
2325 Now, all loads in IFREE and PFREE classes are considered
2326 exception-free, while all loads in IRISKY and PRISKY classes are
2327 considered exception-risky. As for loads in the MFREE class,
2328 these are considered either exception-free or exception-risky,
2329 depending on whether we are pessimistic or optimistic. We have
2330 to take the pessimistic approach to assure the safety of
2331 speculative scheduling, but we can take the optimistic approach
2332 by invoking the -fsched_spec_load_dangerous option. */
2334 enum INSN_TRAP_CLASS
2336 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
2337 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
2340 #define WORST_CLASS(class1, class2) \
2341 ((class1 > class2) ? class1 : class2)
2343 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between */
2344 /* some speculatively moved load insn and this one. */
2345 char *fed_by_spec_load;
2348 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2349 #define IS_REACHABLE(bb_from, bb_to) \
2351 || IS_RGN_ENTRY (bb_from) \
2352 || (bitset_member (ancestor_edges[bb_to], \
2353 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2355 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2356 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2358 /* Non-zero iff the address is comprised from at most 1 register */
2359 #define CONST_BASED_ADDRESS_P(x) \
2360 (GET_CODE (x) == REG \
2361 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2362 || (GET_CODE (x) == LO_SUM)) \
2363 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2364 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2366 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2369 set_spec_fed (load_insn)
2374 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
2375 if (GET_MODE (link) == VOIDmode)
2376 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
2377 } /* set_spec_fed */
2379 /* On the path from the insn to load_insn_bb, find a conditional branch */
2380 /* depending on insn, that guards the speculative load. */
2383 find_conditional_protection (insn, load_insn_bb)
2389 /* iterate through DEF-USE forward dependences */
2390 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2392 rtx next = XEXP (link, 0);
2393 if ((CONTAINING_RGN (INSN_BLOCK (next)) ==
2394 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
2395 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
2396 && load_insn_bb != INSN_BB (next)
2397 && GET_MODE (link) == VOIDmode
2398 && (GET_CODE (next) == JUMP_INSN
2399 || find_conditional_protection (next, load_insn_bb)))
2403 } /* find_conditional_protection */
2405 /* Returns 1 if the same insn1 that participates in the computation
2406 of load_insn's address is feeding a conditional branch that is
2407 guarding on load_insn. This is true if we find a the two DEF-USE
2409 insn1 -> ... -> conditional-branch
2410 insn1 -> ... -> load_insn,
2411 and if a flow path exist:
2412 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2413 and if insn1 is on the path
2414 region-entry -> ... -> bb_trg -> ... load_insn.
2416 Locate insn1 by climbing on LOG_LINKS from load_insn.
2417 Locate the branch by following INSN_DEPEND from insn1. */
2420 is_conditionally_protected (load_insn, bb_src, bb_trg)
2426 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
2428 rtx insn1 = XEXP (link, 0);
2430 /* must be a DEF-USE dependence upon non-branch */
2431 if (GET_MODE (link) != VOIDmode
2432 || GET_CODE (insn1) == JUMP_INSN)
2435 /* must exist a path: region-entry -> ... -> bb_trg -> ... load_insn */
2436 if (INSN_BB (insn1) == bb_src
2437 || (CONTAINING_RGN (INSN_BLOCK (insn1))
2438 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
2439 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
2440 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
2443 /* now search for the conditional-branch */
2444 if (find_conditional_protection (insn1, bb_src))
2447 /* recursive step: search another insn1, "above" current insn1. */
2448 return is_conditionally_protected (insn1, bb_src, bb_trg);
2451 /* the chain does not exsist */
2453 } /* is_conditionally_protected */
2455 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2456 load_insn can move speculatively from bb_src to bb_trg. All the
2457 following must hold:
2459 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2460 (2) load_insn and load1 have a def-use dependence upon
2461 the same insn 'insn1'.
2462 (3) either load2 is in bb_trg, or:
2463 - there's only one split-block, and
2464 - load1 is on the escape path, and
2466 From all these we can conclude that the two loads access memory
2467 addresses that differ at most by a constant, and hence if moving
2468 load_insn would cause an exception, it would have been caused by
2472 is_pfree (load_insn, bb_src, bb_trg)
2477 register candidate *candp = candidate_table + bb_src;
2479 if (candp->split_bbs.nr_members != 1)
2480 /* must have exactly one escape block */
2483 for (back_link = LOG_LINKS (load_insn);
2484 back_link; back_link = XEXP (back_link, 1))
2486 rtx insn1 = XEXP (back_link, 0);
2488 if (GET_MODE (back_link) == VOIDmode)
2490 /* found a DEF-USE dependence (insn1, load_insn) */
2493 for (fore_link = INSN_DEPEND (insn1);
2494 fore_link; fore_link = XEXP (fore_link, 1))
2496 rtx insn2 = XEXP (fore_link, 0);
2497 if (GET_MODE (fore_link) == VOIDmode)
2499 /* found a DEF-USE dependence (insn1, insn2) */
2500 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
2501 /* insn2 not guaranteed to be a 1 base reg load */
2504 if (INSN_BB (insn2) == bb_trg)
2505 /* insn2 is the similar load, in the target block */
2508 if (*(candp->split_bbs.first_member) == INSN_BLOCK (insn2))
2509 /* insn2 is a similar load, in a split-block */
2516 /* couldn't find a similar load */
2520 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2521 as found by analyzing insn's expression. */
2524 may_trap_exp (x, is_store)
2532 code = GET_CODE (x);
2542 /* The insn uses memory */
2543 /* a volatile load */
2544 if (MEM_VOLATILE_P (x))
2546 /* an exception-free load */
2547 if (!may_trap_p (x))
2549 /* a load with 1 base register, to be further checked */
2550 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
2551 return PFREE_CANDIDATE;
2552 /* no info on the load, to be further checked */
2553 return PRISKY_CANDIDATE;
2558 int i, insn_class = TRAP_FREE;
2560 /* neither store nor load, check if it may cause a trap */
2563 /* recursive step: walk the insn... */
2564 fmt = GET_RTX_FORMAT (code);
2565 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2569 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
2570 insn_class = WORST_CLASS (insn_class, tmp_class);
2572 else if (fmt[i] == 'E')
2575 for (j = 0; j < XVECLEN (x, i); j++)
2577 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
2578 insn_class = WORST_CLASS (insn_class, tmp_class);
2579 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2583 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2588 } /* may_trap_exp */
2591 /* Classifies insn for the purpose of verifying that it can be
2592 moved speculatively, by examining it's patterns, returning:
2593 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2594 TRAP_FREE: non-load insn.
2595 IFREE: load from a globaly safe location.
2596 IRISKY: volatile load.
2597 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2598 being either PFREE or PRISKY. */
2601 haifa_classify_insn (insn)
2604 rtx pat = PATTERN (insn);
2605 int tmp_class = TRAP_FREE;
2606 int insn_class = TRAP_FREE;
2609 if (GET_CODE (pat) == PARALLEL)
2611 int i, len = XVECLEN (pat, 0);
2613 for (i = len - 1; i >= 0; i--)
2615 code = GET_CODE (XVECEXP (pat, 0, i));
2619 /* test if it is a 'store' */
2620 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
2623 /* test if it is a store */
2624 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
2625 if (tmp_class == TRAP_RISKY)
2627 /* test if it is a load */
2629 WORST_CLASS (tmp_class,
2630 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 0));
2633 insn_class = WORST_CLASS (insn_class, tmp_class);
2634 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2640 code = GET_CODE (pat);
2644 /* test if it is a 'store' */
2645 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
2648 /* test if it is a store */
2649 tmp_class = may_trap_exp (SET_DEST (pat), 1);
2650 if (tmp_class == TRAP_RISKY)
2652 /* test if it is a load */
2654 WORST_CLASS (tmp_class,
2655 may_trap_exp (SET_SRC (pat), 0));
2658 insn_class = tmp_class;
2663 } /* haifa_classify_insn */
2665 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2666 a load moved speculatively, or if load_insn is protected by
2667 a compare on load_insn's address). */
2670 is_prisky (load_insn, bb_src, bb_trg)
2674 if (FED_BY_SPEC_LOAD (load_insn))
2677 if (LOG_LINKS (load_insn) == NULL)
2678 /* dependence may 'hide' out of the region. */
2681 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2687 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2688 Return 1 if insn is exception-free (and the motion is valid)
2692 is_exception_free (insn, bb_src, bb_trg)
2696 int insn_class = haifa_classify_insn (insn);
2698 /* handle non-load insns */
2709 if (!flag_schedule_speculative_load)
2711 IS_LOAD_INSN (insn) = 1;
2718 case PFREE_CANDIDATE:
2719 if (is_pfree (insn, bb_src, bb_trg))
2721 /* don't 'break' here: PFREE-candidate is also PRISKY-candidate */
2722 case PRISKY_CANDIDATE:
2723 if (!flag_schedule_speculative_load_dangerous
2724 || is_prisky (insn, bb_src, bb_trg))
2730 return flag_schedule_speculative_load_dangerous;
2731 } /* is_exception_free */
2734 /* Process an insn's memory dependencies. There are four kinds of
2737 (0) read dependence: read follows read
2738 (1) true dependence: read follows write
2739 (2) anti dependence: write follows read
2740 (3) output dependence: write follows write
2742 We are careful to build only dependencies which actually exist, and
2743 use transitivity to avoid building too many links. */
2745 /* Return the INSN_LIST containing INSN in LIST, or NULL
2746 if LIST does not contain INSN. */
2748 HAIFA_INLINE static rtx
2749 find_insn_list (insn, list)
2755 if (XEXP (list, 0) == insn)
2757 list = XEXP (list, 1);
2763 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 otherwise. */
2765 HAIFA_INLINE static char
2766 find_insn_mem_list (insn, x, list, list1)
2772 if (XEXP (list, 0) == insn
2773 && XEXP (list1, 0) == x)
2775 list = XEXP (list, 1);
2776 list1 = XEXP (list1, 1);
2782 /* Compute the function units used by INSN. This caches the value
2783 returned by function_units_used. A function unit is encoded as the
2784 unit number if the value is non-negative and the compliment of a
2785 mask if the value is negative. A function unit index is the
2786 non-negative encoding. */
2788 HAIFA_INLINE static int
2792 register int unit = INSN_UNIT (insn);
2796 recog_memoized (insn);
2798 /* A USE insn, or something else we don't need to understand.
2799 We can't pass these directly to function_units_used because it will
2800 trigger a fatal error for unrecognizable insns. */
2801 if (INSN_CODE (insn) < 0)
2805 unit = function_units_used (insn);
2806 /* Increment non-negative values so we can cache zero. */
2810 /* We only cache 16 bits of the result, so if the value is out of
2811 range, don't cache it. */
2812 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
2814 || (~unit & ((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
2815 INSN_UNIT (insn) = unit;
2817 return (unit > 0 ? unit - 1 : unit);
2820 /* Compute the blockage range for executing INSN on UNIT. This caches
2821 the value returned by the blockage_range_function for the unit.
2822 These values are encoded in an int where the upper half gives the
2823 minimum value and the lower half gives the maximum value. */
2825 HAIFA_INLINE static unsigned int
2826 blockage_range (unit, insn)
2830 unsigned int blockage = INSN_BLOCKAGE (insn);
2833 if (UNIT_BLOCKED (blockage) != unit + 1)
2835 range = function_units[unit].blockage_range_function (insn);
2836 /* We only cache the blockage range for one unit and then only if
2838 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
2839 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
2842 range = BLOCKAGE_RANGE (blockage);
2847 /* A vector indexed by function unit instance giving the last insn to use
2848 the unit. The value of the function unit instance index for unit U
2849 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2850 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2852 /* A vector indexed by function unit instance giving the minimum time when
2853 the unit will unblock based on the maximum blockage cost. */
2854 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2856 /* A vector indexed by function unit number giving the number of insns
2857 that remain to use the unit. */
2858 static int unit_n_insns[FUNCTION_UNITS_SIZE];
2860 /* Reset the function unit state to the null state. */
2865 bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
2866 bzero ((char *) unit_tick, sizeof (unit_tick));
2867 bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
2870 /* Return the issue-delay of an insn */
2872 HAIFA_INLINE static int
2873 insn_issue_delay (insn)
2877 int unit = insn_unit (insn);
2879 /* efficiency note: in fact, we are working 'hard' to compute a
2880 value that was available in md file, and is not available in
2881 function_units[] structure. It would be nice to have this
2882 value there, too. */
2885 if (function_units[unit].blockage_range_function &&
2886 function_units[unit].blockage_function)
2887 delay = function_units[unit].blockage_function (insn, insn);
2890 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2891 if ((unit & 1) != 0 && function_units[i].blockage_range_function
2892 && function_units[i].blockage_function)
2893 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
2898 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2899 instance INSTANCE at time CLOCK if the previous actual hazard cost
2902 HAIFA_INLINE static int
2903 actual_hazard_this_instance (unit, instance, insn, clock, cost)
2904 int unit, instance, clock, cost;
2907 int tick = unit_tick[instance]; /* issue time of the last issued insn */
2909 if (tick - clock > cost)
2911 /* The scheduler is operating forward, so unit's last insn is the
2912 executing insn and INSN is the candidate insn. We want a
2913 more exact measure of the blockage if we execute INSN at CLOCK
2914 given when we committed the execution of the unit's last insn.
2916 The blockage value is given by either the unit's max blockage
2917 constant, blockage range function, or blockage function. Use
2918 the most exact form for the given unit. */
2920 if (function_units[unit].blockage_range_function)
2922 if (function_units[unit].blockage_function)
2923 tick += (function_units[unit].blockage_function
2924 (unit_last_insn[instance], insn)
2925 - function_units[unit].max_blockage);
2927 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
2928 - function_units[unit].max_blockage);
2930 if (tick - clock > cost)
2931 cost = tick - clock;
2936 /* Record INSN as having begun execution on the units encoded by UNIT at
2939 HAIFA_INLINE static void
2940 schedule_unit (unit, insn, clock)
2948 int instance = unit;
2949 #if MAX_MULTIPLICITY > 1
2950 /* Find the first free instance of the function unit and use that
2951 one. We assume that one is free. */
2952 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2954 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
2956 instance += FUNCTION_UNITS_SIZE;
2959 unit_last_insn[instance] = insn;
2960 unit_tick[instance] = (clock + function_units[unit].max_blockage);
2963 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2964 if ((unit & 1) != 0)
2965 schedule_unit (i, insn, clock);
2968 /* Return the actual hazard cost of executing INSN on the units encoded by
2969 UNIT at time CLOCK if the previous actual hazard cost was COST. */
2971 HAIFA_INLINE static int
2972 actual_hazard (unit, insn, clock, cost)
2973 int unit, clock, cost;
2980 /* Find the instance of the function unit with the minimum hazard. */
2981 int instance = unit;
2982 int best_cost = actual_hazard_this_instance (unit, instance, insn,
2986 #if MAX_MULTIPLICITY > 1
2987 if (best_cost > cost)
2989 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2991 instance += FUNCTION_UNITS_SIZE;
2992 this_cost = actual_hazard_this_instance (unit, instance, insn,
2994 if (this_cost < best_cost)
2996 best_cost = this_cost;
2997 if (this_cost <= cost)
3003 cost = MAX (cost, best_cost);
3006 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3007 if ((unit & 1) != 0)
3008 cost = actual_hazard (i, insn, clock, cost);
3013 /* Return the potential hazard cost of executing an instruction on the
3014 units encoded by UNIT if the previous potential hazard cost was COST.
3015 An insn with a large blockage time is chosen in preference to one
3016 with a smaller time; an insn that uses a unit that is more likely
3017 to be used is chosen in preference to one with a unit that is less
3018 used. We are trying to minimize a subsequent actual hazard. */
3020 HAIFA_INLINE static int
3021 potential_hazard (unit, insn, cost)
3026 unsigned int minb, maxb;
3030 minb = maxb = function_units[unit].max_blockage;
3033 if (function_units[unit].blockage_range_function)
3035 maxb = minb = blockage_range (unit, insn);
3036 maxb = MAX_BLOCKAGE_COST (maxb);
3037 minb = MIN_BLOCKAGE_COST (minb);
3042 /* Make the number of instructions left dominate. Make the
3043 minimum delay dominate the maximum delay. If all these
3044 are the same, use the unit number to add an arbitrary
3045 ordering. Other terms can be added. */
3046 ncost = minb * 0x40 + maxb;
3047 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
3054 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3055 if ((unit & 1) != 0)
3056 cost = potential_hazard (i, insn, cost);
3061 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3062 This is the number of cycles between instruction issue and
3063 instruction results. */
3065 HAIFA_INLINE static int
3066 insn_cost (insn, link, used)
3067 rtx insn, link, used;
3069 register int cost = INSN_COST (insn);
3073 recog_memoized (insn);
3075 /* A USE insn, or something else we don't need to understand.
3076 We can't pass these directly to result_ready_cost because it will
3077 trigger a fatal error for unrecognizable insns. */
3078 if (INSN_CODE (insn) < 0)
3080 INSN_COST (insn) = 1;
3085 cost = result_ready_cost (insn);
3090 INSN_COST (insn) = cost;
3094 /* in this case estimate cost without caring how insn is used. */
3095 if (link == 0 && used == 0)
3098 /* A USE insn should never require the value used to be computed. This
3099 allows the computation of a function's result and parameter values to
3100 overlap the return and call. */
3101 recog_memoized (used);
3102 if (INSN_CODE (used) < 0)
3103 LINK_COST_FREE (link) = 1;
3105 /* If some dependencies vary the cost, compute the adjustment. Most
3106 commonly, the adjustment is complete: either the cost is ignored
3107 (in the case of an output- or anti-dependence), or the cost is
3108 unchanged. These values are cached in the link as LINK_COST_FREE
3109 and LINK_COST_ZERO. */
3111 if (LINK_COST_FREE (link))
3114 else if (!LINK_COST_ZERO (link))
3118 ADJUST_COST (used, link, insn, ncost);
3120 LINK_COST_FREE (link) = ncost = 1;
3122 LINK_COST_ZERO (link) = 1;
3129 /* Compute the priority number for INSN. */
3138 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
3141 if ((this_priority = INSN_PRIORITY (insn)) == 0)
3143 if (INSN_DEPEND (insn) == 0)
3144 this_priority = insn_cost (insn, 0, 0);
3146 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
3151 if (RTX_INTEGRATED_P (link))
3154 next = XEXP (link, 0);
3156 /* critical path is meaningful in block boundaries only */
3157 if (INSN_BLOCK (next) != INSN_BLOCK (insn))
3160 next_priority = insn_cost (insn, link, next) + priority (next);
3161 if (next_priority > this_priority)
3162 this_priority = next_priority;
3164 INSN_PRIORITY (insn) = this_priority;
3166 return this_priority;
3170 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3171 them to the unused_*_list variables, so that they can be reused. */
3174 free_pending_lists ()
3176 if (current_nr_blocks <= 1)
3178 free_list (&pending_read_insns, &unused_insn_list);
3179 free_list (&pending_write_insns, &unused_insn_list);
3180 free_list (&pending_read_mems, &unused_expr_list);
3181 free_list (&pending_write_mems, &unused_expr_list);
3185 /* interblock scheduling */
3188 for (bb = 0; bb < current_nr_blocks; bb++)
3190 free_list (&bb_pending_read_insns[bb], &unused_insn_list);
3191 free_list (&bb_pending_write_insns[bb], &unused_insn_list);
3192 free_list (&bb_pending_read_mems[bb], &unused_expr_list);
3193 free_list (&bb_pending_write_mems[bb], &unused_expr_list);
3198 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3199 The MEM is a memory reference contained within INSN, which we are saving
3200 so that we can do memory aliasing on it. */
3203 add_insn_mem_dependence (insn_list, mem_list, insn, mem)
3204 rtx *insn_list, *mem_list, insn, mem;
3208 link = alloc_INSN_LIST (insn, *insn_list);
3211 link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
3214 pending_lists_length++;
3218 /* Make a dependency between every memory reference on the pending lists
3219 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3223 flush_pending_lists (insn, only_write)
3230 while (pending_read_insns && ! only_write)
3232 add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
3234 link = pending_read_insns;
3235 pending_read_insns = XEXP (pending_read_insns, 1);
3236 XEXP (link, 1) = unused_insn_list;
3237 unused_insn_list = link;
3239 link = pending_read_mems;
3240 pending_read_mems = XEXP (pending_read_mems, 1);
3241 XEXP (link, 1) = unused_expr_list;
3242 unused_expr_list = link;
3244 while (pending_write_insns)
3246 add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
3248 link = pending_write_insns;
3249 pending_write_insns = XEXP (pending_write_insns, 1);
3250 XEXP (link, 1) = unused_insn_list;
3251 unused_insn_list = link;
3253 link = pending_write_mems;
3254 pending_write_mems = XEXP (pending_write_mems, 1);
3255 XEXP (link, 1) = unused_expr_list;
3256 unused_expr_list = link;
3258 pending_lists_length = 0;
3260 /* last_pending_memory_flush is now a list of insns */
3261 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3262 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3264 free_list (&last_pending_memory_flush, &unused_insn_list);
3265 last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
3268 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
3269 by the write to the destination of X, and reads of everything mentioned. */
3272 sched_analyze_1 (x, insn)
3277 register rtx dest = SET_DEST (x);
3282 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3283 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3285 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3287 /* The second and third arguments are values read by this insn. */
3288 sched_analyze_2 (XEXP (dest, 1), insn);
3289 sched_analyze_2 (XEXP (dest, 2), insn);
3291 dest = SUBREG_REG (dest);
3294 if (GET_CODE (dest) == REG)
3298 regno = REGNO (dest);
3300 /* A hard reg in a wide mode may really be multiple registers.
3301 If so, mark all of them just like the first. */
3302 if (regno < FIRST_PSEUDO_REGISTER)
3304 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
3309 for (u = reg_last_uses[regno + i]; u; u = XEXP (u, 1))
3310 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3311 reg_last_uses[regno + i] = 0;
3313 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3314 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3316 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
3318 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3319 /* Function calls clobber all call_used regs. */
3320 for (u = last_function_call; u; u = XEXP (u, 1))
3321 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3328 for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
3329 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3330 reg_last_uses[regno] = 0;
3332 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3333 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3335 SET_REGNO_REG_SET (reg_pending_sets, regno);
3337 /* Pseudos that are REG_EQUIV to something may be replaced
3338 by that during reloading. We need only add dependencies for
3339 the address in the REG_EQUIV note. */
3340 if (!reload_completed
3341 && reg_known_equiv_p[regno]
3342 && GET_CODE (reg_known_value[regno]) == MEM)
3343 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3345 /* Don't let it cross a call after scheduling if it doesn't
3346 already cross one. */
3348 if (REG_N_CALLS_CROSSED (regno) == 0)
3349 for (u = last_function_call; u; u = XEXP (u, 1))
3350 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3353 else if (GET_CODE (dest) == MEM)
3355 /* Writing memory. */
3357 if (pending_lists_length > 32)
3359 /* Flush all pending reads and writes to prevent the pending lists
3360 from getting any larger. Insn scheduling runs too slowly when
3361 these lists get long. The number 32 was chosen because it
3362 seems like a reasonable number. When compiling GCC with itself,
3363 this flush occurs 8 times for sparc, and 10 times for m88k using
3365 flush_pending_lists (insn, 0);
3370 rtx pending, pending_mem;
3372 pending = pending_read_insns;
3373 pending_mem = pending_read_mems;
3376 /* If a dependency already exists, don't create a new one. */
3377 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3378 if (anti_dependence (XEXP (pending_mem, 0), dest))
3379 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3381 pending = XEXP (pending, 1);
3382 pending_mem = XEXP (pending_mem, 1);
3385 pending = pending_write_insns;
3386 pending_mem = pending_write_mems;
3389 /* If a dependency already exists, don't create a new one. */
3390 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3391 if (output_dependence (XEXP (pending_mem, 0), dest))
3392 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
3394 pending = XEXP (pending, 1);
3395 pending_mem = XEXP (pending_mem, 1);
3398 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3399 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3401 add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
3404 sched_analyze_2 (XEXP (dest, 0), insn);
3407 /* Analyze reads. */
3408 if (GET_CODE (x) == SET)
3409 sched_analyze_2 (SET_SRC (x), insn);
3412 /* Analyze the uses of memory and registers in rtx X in INSN. */
3415 sched_analyze_2 (x, insn)
3421 register enum rtx_code code;
3427 code = GET_CODE (x);
3436 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3437 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3438 this does not mean that this insn is using cc0. */
3446 /* User of CC0 depends on immediately preceding insn. */
3447 SCHED_GROUP_P (insn) = 1;
3449 /* There may be a note before this insn now, but all notes will
3450 be removed before we actually try to schedule the insns, so
3451 it won't cause a problem later. We must avoid it here though. */
3452 prev = prev_nonnote_insn (insn);
3454 /* Make a copy of all dependencies on the immediately previous insn,
3455 and add to this insn. This is so that all the dependencies will
3456 apply to the group. Remove an explicit dependence on this insn
3457 as SCHED_GROUP_P now represents it. */
3459 if (find_insn_list (prev, LOG_LINKS (insn)))
3460 remove_dependence (insn, prev);
3462 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
3463 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3472 int regno = REGNO (x);
3473 if (regno < FIRST_PSEUDO_REGISTER)
3477 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
3480 reg_last_uses[regno + i]
3481 = alloc_INSN_LIST (insn, reg_last_uses[regno + i]);
3483 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3484 add_dependence (insn, XEXP (u, 0), 0);
3486 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3487 /* Function calls clobber all call_used regs. */
3488 for (u = last_function_call; u; u = XEXP (u, 1))
3489 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3494 reg_last_uses[regno] = alloc_INSN_LIST (insn, reg_last_uses[regno]);
3496 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3497 add_dependence (insn, XEXP (u, 0), 0);
3499 /* Pseudos that are REG_EQUIV to something may be replaced
3500 by that during reloading. We need only add dependencies for
3501 the address in the REG_EQUIV note. */
3502 if (!reload_completed
3503 && reg_known_equiv_p[regno]
3504 && GET_CODE (reg_known_value[regno]) == MEM)
3505 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3507 /* If the register does not already cross any calls, then add this
3508 insn to the sched_before_next_call list so that it will still
3509 not cross calls after scheduling. */
3510 if (REG_N_CALLS_CROSSED (regno) == 0)
3511 add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
3518 /* Reading memory. */
3520 rtx pending, pending_mem;
3522 pending = pending_read_insns;
3523 pending_mem = pending_read_mems;
3526 /* If a dependency already exists, don't create a new one. */
3527 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3528 if (read_dependence (XEXP (pending_mem, 0), x))
3529 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3531 pending = XEXP (pending, 1);
3532 pending_mem = XEXP (pending_mem, 1);
3535 pending = pending_write_insns;
3536 pending_mem = pending_write_mems;
3539 /* If a dependency already exists, don't create a new one. */
3540 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3541 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
3543 add_dependence (insn, XEXP (pending, 0), 0);
3545 pending = XEXP (pending, 1);
3546 pending_mem = XEXP (pending_mem, 1);
3549 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3550 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3552 /* Always add these dependencies to pending_reads, since
3553 this insn may be followed by a write. */
3554 add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
3557 /* Take advantage of tail recursion here. */
3558 sched_analyze_2 (XEXP (x, 0), insn);
3564 case UNSPEC_VOLATILE:
3569 /* Traditional and volatile asm instructions must be considered to use
3570 and clobber all hard registers, all pseudo-registers and all of
3571 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3573 Consider for instance a volatile asm that changes the fpu rounding
3574 mode. An insn should not be moved across this even if it only uses
3575 pseudo-regs because it might give an incorrectly rounded result. */
3576 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
3578 int max_reg = max_reg_num ();
3579 for (i = 0; i < max_reg; i++)
3581 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3582 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3583 reg_last_uses[i] = 0;
3585 /* reg_last_sets[r] is now a list of insns */
3586 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3587 add_dependence (insn, XEXP (u, 0), 0);
3589 reg_pending_sets_all = 1;
3591 flush_pending_lists (insn, 0);
3594 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3595 We can not just fall through here since then we would be confused
3596 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3597 traditional asms unlike their normal usage. */
3599 if (code == ASM_OPERANDS)
3601 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3602 sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
3612 /* These both read and modify the result. We must handle them as writes
3613 to get proper dependencies for following instructions. We must handle
3614 them as reads to get proper dependencies from this to previous
3615 instructions. Thus we need to pass them to both sched_analyze_1
3616 and sched_analyze_2. We must call sched_analyze_2 first in order
3617 to get the proper antecedent for the read. */
3618 sched_analyze_2 (XEXP (x, 0), insn);
3619 sched_analyze_1 (x, insn);
3626 /* Other cases: walk the insn. */
3627 fmt = GET_RTX_FORMAT (code);
3628 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3631 sched_analyze_2 (XEXP (x, i), insn);
3632 else if (fmt[i] == 'E')
3633 for (j = 0; j < XVECLEN (x, i); j++)
3634 sched_analyze_2 (XVECEXP (x, i, j), insn);
3638 /* Analyze an INSN with pattern X to find all dependencies. */
3641 sched_analyze_insn (x, insn, loop_notes)
3645 register RTX_CODE code = GET_CODE (x);
3647 int maxreg = max_reg_num ();
3650 if (code == SET || code == CLOBBER)
3651 sched_analyze_1 (x, insn);
3652 else if (code == PARALLEL)
3655 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3657 code = GET_CODE (XVECEXP (x, 0, i));
3658 if (code == SET || code == CLOBBER)
3659 sched_analyze_1 (XVECEXP (x, 0, i), insn);
3661 sched_analyze_2 (XVECEXP (x, 0, i), insn);
3665 sched_analyze_2 (x, insn);
3667 /* Mark registers CLOBBERED or used by called function. */
3668 if (GET_CODE (insn) == CALL_INSN)
3669 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3671 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3672 sched_analyze_1 (XEXP (link, 0), insn);
3674 sched_analyze_2 (XEXP (link, 0), insn);
3677 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic block, then
3678 we must be sure that no instructions are scheduled across it.
3679 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3680 become incorrect. */
3684 int max_reg = max_reg_num ();
3687 for (i = 0; i < max_reg; i++)
3690 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3691 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3692 reg_last_uses[i] = 0;
3694 /* reg_last_sets[r] is now a list of insns */
3695 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3696 add_dependence (insn, XEXP (u, 0), 0);
3698 reg_pending_sets_all = 1;
3700 flush_pending_lists (insn, 0);
3703 while (XEXP (link, 1))
3704 link = XEXP (link, 1);
3705 XEXP (link, 1) = REG_NOTES (insn);
3706 REG_NOTES (insn) = loop_notes;
3709 /* After reload, it is possible for an instruction to have a REG_DEAD note
3710 for a register that actually dies a few instructions earlier. For
3711 example, this can happen with SECONDARY_MEMORY_NEEDED reloads.
3712 In this case, we must consider the insn to use the register mentioned
3713 in the REG_DEAD note. Otherwise, we may accidentally move this insn
3714 after another insn that sets the register, thus getting obviously invalid
3715 rtl. This confuses reorg which believes that REG_DEAD notes are still
3718 ??? We would get better code if we fixed reload to put the REG_DEAD
3719 notes in the right places, but that may not be worth the effort. */
3721 if (reload_completed)
3725 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3726 if (REG_NOTE_KIND (note) == REG_DEAD)
3727 sched_analyze_2 (XEXP (note, 0), insn);
3730 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
3732 /* reg_last_sets[r] is now a list of insns */
3733 free_list (®_last_sets[i], &unused_insn_list);
3735 = alloc_INSN_LIST (insn, NULL_RTX);
3737 CLEAR_REG_SET (reg_pending_sets);
3739 if (reg_pending_sets_all)
3741 for (i = 0; i < maxreg; i++)
3743 /* reg_last_sets[r] is now a list of insns */
3744 free_list (®_last_sets[i], &unused_insn_list);
3745 reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3748 reg_pending_sets_all = 0;
3751 /* Handle function calls and function returns created by the epilogue
3753 if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
3758 /* When scheduling instructions, we make sure calls don't lose their
3759 accompanying USE insns by depending them one on another in order.
3761 Also, we must do the same thing for returns created by the epilogue
3762 threading code. Note this code works only in this special case,
3763 because other passes make no guarantee that they will never emit
3764 an instruction between a USE and a RETURN. There is such a guarantee
3765 for USE instructions immediately before a call. */
3767 prev_dep_insn = insn;
3768 dep_insn = PREV_INSN (insn);
3769 while (GET_CODE (dep_insn) == INSN
3770 && GET_CODE (PATTERN (dep_insn)) == USE
3771 && GET_CODE (XEXP (PATTERN (dep_insn), 0)) == REG)
3773 SCHED_GROUP_P (prev_dep_insn) = 1;
3775 /* Make a copy of all dependencies on dep_insn, and add to insn.
3776 This is so that all of the dependencies will apply to the
3779 for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
3780 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3782 prev_dep_insn = dep_insn;
3783 dep_insn = PREV_INSN (dep_insn);
3788 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3789 for every dependency. */
3792 sched_analyze (head, tail)
3799 for (insn = head;; insn = NEXT_INSN (insn))
3801 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
3803 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3806 else if (GET_CODE (insn) == CALL_INSN)
3811 CANT_MOVE (insn) = 1;
3813 /* Any instruction using a hard register which may get clobbered
3814 by a call needs to be marked as dependent on this call.
3815 This prevents a use of a hard return reg from being moved
3816 past a void call (i.e. it does not explicitly set the hard
3819 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3820 all registers, not just hard registers, may be clobbered by this
3823 /* Insn, being a CALL_INSN, magically depends on
3824 `last_function_call' already. */
3826 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
3827 && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
3829 int max_reg = max_reg_num ();
3830 for (i = 0; i < max_reg; i++)
3832 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3833 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3835 reg_last_uses[i] = 0;
3837 /* reg_last_sets[r] is now a list of insns */
3838 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3839 add_dependence (insn, XEXP (u, 0), 0);
3841 reg_pending_sets_all = 1;
3843 /* Add a pair of fake REG_NOTE which we will later
3844 convert back into a NOTE_INSN_SETJMP note. See
3845 reemit_notes for why we use a pair of NOTEs. */
3846 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3849 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3850 GEN_INT (NOTE_INSN_SETJMP),
3855 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3856 if (call_used_regs[i] || global_regs[i])
3858 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3859 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3860 reg_last_uses[i] = 0;
3862 /* reg_last_sets[r] is now a list of insns */
3863 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3864 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3866 SET_REGNO_REG_SET (reg_pending_sets, i);
3870 /* For each insn which shouldn't cross a call, add a dependence
3871 between that insn and this call insn. */
3872 x = LOG_LINKS (sched_before_next_call);
3875 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
3878 LOG_LINKS (sched_before_next_call) = 0;
3880 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3883 /* In the absence of interprocedural alias analysis, we must flush
3884 all pending reads and writes, and start new dependencies starting
3885 from here. But only flush writes for constant calls (which may
3886 be passed a pointer to something we haven't written yet). */
3887 flush_pending_lists (insn, CONST_CALL_P (insn));
3889 /* Depend this function call (actually, the user of this
3890 function call) on all hard register clobberage. */
3892 /* last_function_call is now a list of insns */
3893 free_list(&last_function_call, &unused_insn_list);
3894 last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3897 /* See comments on reemit_notes as to why we do this. */
3898 else if (GET_CODE (insn) == NOTE
3899 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
3900 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
3901 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
3902 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
3903 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_START
3904 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END
3905 || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
3906 && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
3908 loop_notes = alloc_EXPR_LIST (REG_DEAD,
3909 GEN_INT (NOTE_BLOCK_NUMBER (insn)),
3911 loop_notes = alloc_EXPR_LIST (REG_DEAD,
3912 GEN_INT (NOTE_LINE_NUMBER (insn)),
3914 CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
3923 /* Called when we see a set of a register. If death is true, then we are
3924 scanning backwards. Mark that register as unborn. If nobody says
3925 otherwise, that is how things will remain. If death is false, then we
3926 are scanning forwards. Mark that register as being born. */
3929 sched_note_set (x, death)
3934 register rtx reg = SET_DEST (x);
3940 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
3941 || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
3943 /* Must treat modification of just one hardware register of a multi-reg
3944 value or just a byte field of a register exactly the same way that
3945 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
3946 does not kill the entire register. */
3947 if (GET_CODE (reg) != SUBREG
3948 || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
3951 reg = SUBREG_REG (reg);
3954 if (GET_CODE (reg) != REG)
3957 /* Global registers are always live, so the code below does not apply
3960 regno = REGNO (reg);
3961 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
3965 /* If we only set part of the register, then this set does not
3970 /* Try killing this register. */
3971 if (regno < FIRST_PSEUDO_REGISTER)
3973 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
3976 CLEAR_REGNO_REG_SET (bb_live_regs, regno + j);
3981 /* Recompute REG_BASIC_BLOCK as we update all the other
3982 dataflow information. */
3983 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
3984 sched_reg_basic_block[regno] = current_block_num;
3985 else if (sched_reg_basic_block[regno] != current_block_num)
3986 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
3988 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
3993 /* Make the register live again. */
3994 if (regno < FIRST_PSEUDO_REGISTER)
3996 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
3999 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4004 SET_REGNO_REG_SET (bb_live_regs, regno);
4010 /* Macros and functions for keeping the priority queue sorted, and
4011 dealing with queueing and dequeueing of instructions. */
4013 #define SCHED_SORT(READY, N_READY) \
4014 do { if ((N_READY) == 2) \
4015 swap_sort (READY, N_READY); \
4016 else if ((N_READY) > 2) \
4017 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4020 /* Returns a positive value if x is preferred; returns a negative value if
4021 y is preferred. Should never return 0, since that will make the sort
4025 rank_for_schedule (x, y)
4026 const GENERIC_PTR x;
4027 const GENERIC_PTR y;
4029 rtx tmp = *(rtx *)y;
4030 rtx tmp2 = *(rtx *)x;
4032 int tmp_class, tmp2_class;
4033 int val, priority_val, spec_val, prob_val, weight_val;
4036 /* prefer insn with higher priority */
4037 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
4039 return priority_val;
4041 /* prefer an insn with smaller contribution to registers-pressure */
4042 if (!reload_completed &&
4043 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
4044 return (weight_val);
4046 /* some comparison make sense in interblock scheduling only */
4047 if (INSN_BB (tmp) != INSN_BB (tmp2))
4049 /* prefer an inblock motion on an interblock motion */
4050 if ((INSN_BB (tmp2) == target_bb) && (INSN_BB (tmp) != target_bb))
4052 if ((INSN_BB (tmp) == target_bb) && (INSN_BB (tmp2) != target_bb))
4055 /* prefer a useful motion on a speculative one */
4056 if ((spec_val = IS_SPECULATIVE_INSN (tmp) - IS_SPECULATIVE_INSN (tmp2)))
4059 /* prefer a more probable (speculative) insn */
4060 prob_val = INSN_PROBABILITY (tmp2) - INSN_PROBABILITY (tmp);
4065 /* compare insns based on their relation to the last-scheduled-insn */
4066 if (last_scheduled_insn)
4068 /* Classify the instructions into three classes:
4069 1) Data dependent on last schedule insn.
4070 2) Anti/Output dependent on last scheduled insn.
4071 3) Independent of last scheduled insn, or has latency of one.
4072 Choose the insn from the highest numbered class if different. */
4073 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
4074 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
4076 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4081 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
4082 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
4084 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4089 if ((val = tmp2_class - tmp_class))
4093 /* If insns are equally good, sort by INSN_LUID (original insn order),
4094 so that we make the sort stable. This minimizes instruction movement,
4095 thus minimizing sched's effect on debugging and cross-jumping. */
4096 return INSN_LUID (tmp) - INSN_LUID (tmp2);
4099 /* Resort the array A in which only element at index N may be out of order. */
4101 HAIFA_INLINE static void
4106 rtx insn = a[n - 1];
4109 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
4117 static int max_priority;
4119 /* Add INSN to the insn queue so that it can be executed at least
4120 N_CYCLES after the currently executing insn. Preserve insns
4121 chain for debugging purposes. */
4123 HAIFA_INLINE static void
4124 queue_insn (insn, n_cycles)
4128 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
4129 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
4130 insn_queue[next_q] = link;
4133 if (sched_verbose >= 2)
4135 fprintf (dump, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn));
4137 if (INSN_BB (insn) != target_bb)
4138 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
4140 fprintf (dump, "queued for %d cycles.\n", n_cycles);
4145 /* Return nonzero if PAT is the pattern of an insn which makes a
4148 HAIFA_INLINE static int
4149 birthing_insn_p (pat)
4154 if (reload_completed == 1)
4157 if (GET_CODE (pat) == SET
4158 && GET_CODE (SET_DEST (pat)) == REG)
4160 rtx dest = SET_DEST (pat);
4161 int i = REGNO (dest);
4163 /* It would be more accurate to use refers_to_regno_p or
4164 reg_mentioned_p to determine when the dest is not live before this
4167 if (REGNO_REG_SET_P (bb_live_regs, i))
4168 return (REG_N_SETS (i) == 1);
4172 if (GET_CODE (pat) == PARALLEL)
4174 for (j = 0; j < XVECLEN (pat, 0); j++)
4175 if (birthing_insn_p (XVECEXP (pat, 0, j)))
4181 /* PREV is an insn that is ready to execute. Adjust its priority if that
4182 will help shorten register lifetimes. */
4184 HAIFA_INLINE static void
4185 adjust_priority (prev)
4188 /* Trying to shorten register lives after reload has completed
4189 is useless and wrong. It gives inaccurate schedules. */
4190 if (reload_completed == 0)
4195 /* ??? This code has no effect, because REG_DEAD notes are removed
4196 before we ever get here. */
4197 for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
4198 if (REG_NOTE_KIND (note) == REG_DEAD)
4201 /* Defer scheduling insns which kill registers, since that
4202 shortens register lives. Prefer scheduling insns which
4203 make registers live for the same reason. */
4207 INSN_PRIORITY (prev) >>= 3;
4210 INSN_PRIORITY (prev) >>= 2;
4214 INSN_PRIORITY (prev) >>= 1;
4217 if (birthing_insn_p (PATTERN (prev)))
4219 int max = max_priority;
4221 if (max > INSN_PRIORITY (prev))
4222 INSN_PRIORITY (prev) = max;
4226 #ifdef ADJUST_PRIORITY
4227 ADJUST_PRIORITY (prev);
4232 /* INSN is the "currently executing insn". Launch each insn which was
4233 waiting on INSN. READY is a vector of insns which are ready to fire.
4234 N_READY is the number of elements in READY. CLOCK is the current
4238 schedule_insn (insn, ready, n_ready, clock)
4247 unit = insn_unit (insn);
4249 if (sched_verbose >= 2)
4251 fprintf (dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ", INSN_UID (insn));
4252 insn_print_units (insn);
4253 fprintf (dump, "\n");
4256 if (sched_verbose && unit == -1)
4257 visualize_no_unit (insn);
4259 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
4260 schedule_unit (unit, insn, clock);
4262 if (INSN_DEPEND (insn) == 0)
4265 /* This is used by the function adjust_priority above. */
4267 max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
4269 max_priority = INSN_PRIORITY (insn);
4271 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
4273 rtx next = XEXP (link, 0);
4274 int cost = insn_cost (insn, link, next);
4276 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
4278 if ((INSN_DEP_COUNT (next) -= 1) == 0)
4280 int effective_cost = INSN_TICK (next) - clock;
4282 /* For speculative insns, before inserting to ready/queue,
4283 check live, exception-free, and issue-delay */
4284 if (INSN_BB (next) != target_bb
4285 && (!IS_VALID (INSN_BB (next))
4287 || (IS_SPECULATIVE_INSN (next)
4288 && (insn_issue_delay (next) > 3
4289 || !check_live (next, INSN_BB (next))
4290 || !is_exception_free (next, INSN_BB (next), target_bb)))))
4293 if (sched_verbose >= 2)
4295 fprintf (dump, ";;\t\tdependences resolved: insn %d ", INSN_UID (next));
4297 if (current_nr_blocks > 1 && INSN_BB (next) != target_bb)
4298 fprintf (dump, "/b%d ", INSN_BLOCK (next));
4300 if (effective_cost <= 1)
4301 fprintf (dump, "into ready\n");
4303 fprintf (dump, "into queue with cost=%d\n", effective_cost);
4306 /* Adjust the priority of NEXT and either put it on the ready
4307 list or queue it. */
4308 adjust_priority (next);
4309 if (effective_cost <= 1)
4310 ready[n_ready++] = next;
4312 queue_insn (next, effective_cost);
4320 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4324 create_reg_dead_note (reg, insn)
4329 /* The number of registers killed after scheduling must be the same as the
4330 number of registers killed before scheduling. The number of REG_DEAD
4331 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4332 might become one DImode hard register REG_DEAD note, but the number of
4333 registers killed will be conserved.
4335 We carefully remove REG_DEAD notes from the dead_notes list, so that
4336 there will be none left at the end. If we run out early, then there
4337 is a bug somewhere in flow, combine and/or sched. */
4339 if (dead_notes == 0)
4341 if (current_nr_blocks <= 1)
4344 link = alloc_EXPR_LIST (REG_DEAD, NULL_RTX, NULL_RTX);
4348 /* Number of regs killed by REG. */
4349 int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
4350 : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
4351 /* Number of regs killed by REG_DEAD notes taken off the list. */
4355 reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4356 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4357 GET_MODE (XEXP (link, 0))));
4358 while (reg_note_regs < regs_killed)
4360 link = XEXP (link, 1);
4362 /* LINK might be zero if we killed more registers after scheduling
4363 than before, and the last hard register we kill is actually
4366 This is normal for interblock scheduling, so deal with it in
4367 that case, else abort. */
4368 if (link == NULL_RTX && current_nr_blocks <= 1)
4370 else if (link == NULL_RTX)
4371 link = alloc_EXPR_LIST (REG_DEAD, gen_rtx_REG (word_mode, 0),
4374 reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4375 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4376 GET_MODE (XEXP (link, 0))));
4378 dead_notes = XEXP (link, 1);
4380 /* If we took too many regs kills off, put the extra ones back. */
4381 while (reg_note_regs > regs_killed)
4383 rtx temp_reg, temp_link;
4385 temp_reg = gen_rtx_REG (word_mode, 0);
4386 temp_link = alloc_EXPR_LIST (REG_DEAD, temp_reg, dead_notes);
4387 dead_notes = temp_link;
4392 XEXP (link, 0) = reg;
4393 XEXP (link, 1) = REG_NOTES (insn);
4394 REG_NOTES (insn) = link;
4397 /* Subroutine on attach_deaths_insn--handles the recursive search
4398 through INSN. If SET_P is true, then x is being modified by the insn. */
4401 attach_deaths (x, insn, set_p)
4408 register enum rtx_code code;
4414 code = GET_CODE (x);
4426 /* Get rid of the easy cases first. */
4431 /* If the register dies in this insn, queue that note, and mark
4432 this register as needing to die. */
4433 /* This code is very similar to mark_used_1 (if set_p is false)
4434 and mark_set_1 (if set_p is true) in flow.c. */
4444 all_needed = some_needed = REGNO_REG_SET_P (old_live_regs, regno);
4445 if (regno < FIRST_PSEUDO_REGISTER)
4449 n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4452 int needed = (REGNO_REG_SET_P (old_live_regs, regno + n));
4453 some_needed |= needed;
4454 all_needed &= needed;
4458 /* If it wasn't live before we started, then add a REG_DEAD note.
4459 We must check the previous lifetime info not the current info,
4460 because we may have to execute this code several times, e.g.
4461 once for a clobber (which doesn't add a note) and later
4462 for a use (which does add a note).
4464 Always make the register live. We must do this even if it was
4465 live before, because this may be an insn which sets and uses
4466 the same register, in which case the register has already been
4467 killed, so we must make it live again.
4469 Global registers are always live, and should never have a REG_DEAD
4470 note added for them, so none of the code below applies to them. */
4472 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
4474 /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
4475 STACK_POINTER_REGNUM, since these are always considered to be
4476 live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
4477 if (regno != FRAME_POINTER_REGNUM
4478 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4479 && ! (regno == HARD_FRAME_POINTER_REGNUM)
4481 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4482 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
4484 && regno != STACK_POINTER_REGNUM)
4486 if (! all_needed && ! dead_or_set_p (insn, x))
4488 /* Check for the case where the register dying partially
4489 overlaps the register set by this insn. */
4490 if (regno < FIRST_PSEUDO_REGISTER
4491 && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
4493 int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4495 some_needed |= dead_or_set_regno_p (insn, regno + n);
4498 /* If none of the words in X is needed, make a REG_DEAD
4499 note. Otherwise, we must make partial REG_DEAD
4502 create_reg_dead_note (x, insn);
4507 /* Don't make a REG_DEAD note for a part of a
4508 register that is set in the insn. */
4509 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
4511 if (! REGNO_REG_SET_P (old_live_regs, regno+i)
4512 && ! dead_or_set_regno_p (insn, regno + i))
4513 create_reg_dead_note (gen_rtx_REG (reg_raw_mode[regno + i],
4520 if (regno < FIRST_PSEUDO_REGISTER)
4522 int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
4525 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4530 /* Recompute REG_BASIC_BLOCK as we update all the other
4531 dataflow information. */
4532 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
4533 sched_reg_basic_block[regno] = current_block_num;
4534 else if (sched_reg_basic_block[regno] != current_block_num)
4535 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
4537 SET_REGNO_REG_SET (bb_live_regs, regno);
4544 /* Handle tail-recursive case. */
4545 attach_deaths (XEXP (x, 0), insn, 0);
4549 attach_deaths (SUBREG_REG (x), insn,
4550 set_p && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4552 || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4553 == GET_MODE_SIZE (GET_MODE ((x))))));
4556 case STRICT_LOW_PART:
4557 attach_deaths (XEXP (x, 0), insn, 0);
4562 attach_deaths (XEXP (x, 0), insn, 0);
4563 attach_deaths (XEXP (x, 1), insn, 0);
4564 attach_deaths (XEXP (x, 2), insn, 0);
4568 /* Other cases: walk the insn. */
4569 fmt = GET_RTX_FORMAT (code);
4570 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4573 attach_deaths (XEXP (x, i), insn, 0);
4574 else if (fmt[i] == 'E')
4575 for (j = 0; j < XVECLEN (x, i); j++)
4576 attach_deaths (XVECEXP (x, i, j), insn, 0);
4581 /* After INSN has executed, add register death notes for each register
4582 that is dead after INSN. */
4585 attach_deaths_insn (insn)
4588 rtx x = PATTERN (insn);
4589 register RTX_CODE code = GET_CODE (x);
4594 attach_deaths (SET_SRC (x), insn, 0);
4596 /* A register might die here even if it is the destination, e.g.
4597 it is the target of a volatile read and is otherwise unused.
4598 Hence we must always call attach_deaths for the SET_DEST. */
4599 attach_deaths (SET_DEST (x), insn, 1);
4601 else if (code == PARALLEL)
4604 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4606 code = GET_CODE (XVECEXP (x, 0, i));
4609 attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
4611 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
4613 /* Flow does not add REG_DEAD notes to registers that die in
4614 clobbers, so we can't either. */
4615 else if (code != CLOBBER)
4616 attach_deaths (XVECEXP (x, 0, i), insn, 0);
4619 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4620 MEM being clobbered, just like flow. */
4621 else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == MEM)
4622 attach_deaths (XEXP (XEXP (x, 0), 0), insn, 0);
4623 /* Otherwise don't add a death note to things being clobbered. */
4624 else if (code != CLOBBER)
4625 attach_deaths (x, insn, 0);
4627 /* Make death notes for things used in the called function. */
4628 if (GET_CODE (insn) == CALL_INSN)
4629 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
4630 attach_deaths (XEXP (XEXP (link, 0), 0), insn,
4631 GET_CODE (XEXP (link, 0)) == CLOBBER);
4634 /* functions for handlnig of notes */
4636 /* Delete notes beginning with INSN and put them in the chain
4637 of notes ended by NOTE_LIST.
4638 Returns the insn following the notes. */
4641 unlink_other_notes (insn, tail)
4644 rtx prev = PREV_INSN (insn);
4646 while (insn != tail && GET_CODE (insn) == NOTE)
4648 rtx next = NEXT_INSN (insn);
4649 /* Delete the note from its current position. */
4651 NEXT_INSN (prev) = next;
4653 PREV_INSN (next) = prev;
4655 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4656 immediately after the call they follow. We use a fake
4657 (REG_DEAD (const_int -1)) note to remember them.
4658 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4659 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
4660 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
4661 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
4662 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_START
4663 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
4664 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
4665 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
4667 /* Insert the note at the end of the notes list. */
4668 PREV_INSN (insn) = note_list;
4670 NEXT_INSN (note_list) = insn;
4679 /* Delete line notes beginning with INSN. Record line-number notes so
4680 they can be reused. Returns the insn following the notes. */
4683 unlink_line_notes (insn, tail)
4686 rtx prev = PREV_INSN (insn);
4688 while (insn != tail && GET_CODE (insn) == NOTE)
4690 rtx next = NEXT_INSN (insn);
4692 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
4694 /* Delete the note from its current position. */
4696 NEXT_INSN (prev) = next;
4698 PREV_INSN (next) = prev;
4700 /* Record line-number notes so they can be reused. */
4701 LINE_NOTE (insn) = insn;
4711 /* Return the head and tail pointers of BB. */
4713 HAIFA_INLINE static void
4714 get_block_head_tail (bb, headp, tailp)
4724 b = BB_TO_BLOCK (bb);
4726 /* HEAD and TAIL delimit the basic block being scheduled. */
4727 head = basic_block_head[b];
4728 tail = basic_block_end[b];
4730 /* Don't include any notes or labels at the beginning of the
4731 basic block, or notes at the ends of basic blocks. */
4732 while (head != tail)
4734 if (GET_CODE (head) == NOTE)
4735 head = NEXT_INSN (head);
4736 else if (GET_CODE (tail) == NOTE)
4737 tail = PREV_INSN (tail);
4738 else if (GET_CODE (head) == CODE_LABEL)
4739 head = NEXT_INSN (head);
4748 /* Delete line notes from bb. Save them so they can be later restored
4749 (in restore_line_notes ()). */
4760 get_block_head_tail (bb, &head, &tail);
4763 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4766 next_tail = NEXT_INSN (tail);
4767 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4771 /* Farm out notes, and maybe save them in NOTE_LIST.
4772 This is needed to keep the debugger from
4773 getting completely deranged. */
4774 if (GET_CODE (insn) == NOTE)
4777 insn = unlink_line_notes (insn, next_tail);
4783 if (insn == next_tail)
4789 /* Save line number notes for each insn in bb. */
4792 save_line_notes (bb)
4798 /* We must use the true line number for the first insn in the block
4799 that was computed and saved at the start of this pass. We can't
4800 use the current line number, because scheduling of the previous
4801 block may have changed the current line number. */
4803 rtx line = line_note_head[BB_TO_BLOCK (bb)];
4806 get_block_head_tail (bb, &head, &tail);
4807 next_tail = NEXT_INSN (tail);
4809 for (insn = basic_block_head[BB_TO_BLOCK (bb)];
4811 insn = NEXT_INSN (insn))
4812 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4815 LINE_NOTE (insn) = line;
4819 /* After bb was scheduled, insert line notes into the insns list. */
4822 restore_line_notes (bb)
4825 rtx line, note, prev, new;
4826 int added_notes = 0;
4828 rtx head, next_tail, insn;
4830 b = BB_TO_BLOCK (bb);
4832 head = basic_block_head[b];
4833 next_tail = NEXT_INSN (basic_block_end[b]);
4835 /* Determine the current line-number. We want to know the current
4836 line number of the first insn of the block here, in case it is
4837 different from the true line number that was saved earlier. If
4838 different, then we need a line number note before the first insn
4839 of this block. If it happens to be the same, then we don't want to
4840 emit another line number note here. */
4841 for (line = head; line; line = PREV_INSN (line))
4842 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4845 /* Walk the insns keeping track of the current line-number and inserting
4846 the line-number notes as needed. */
4847 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4848 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4850 /* This used to emit line number notes before every non-deleted note.
4851 However, this confuses a debugger, because line notes not separated
4852 by real instructions all end up at the same address. I can find no
4853 use for line number notes before other notes, so none are emitted. */
4854 else if (GET_CODE (insn) != NOTE
4855 && (note = LINE_NOTE (insn)) != 0
4858 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
4859 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
4862 prev = PREV_INSN (insn);
4863 if (LINE_NOTE (note))
4865 /* Re-use the original line-number note. */
4866 LINE_NOTE (note) = 0;
4867 PREV_INSN (note) = prev;
4868 NEXT_INSN (prev) = note;
4869 PREV_INSN (insn) = note;
4870 NEXT_INSN (note) = insn;
4875 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
4876 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
4877 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
4880 if (sched_verbose && added_notes)
4881 fprintf (dump, ";; added %d line-number notes\n", added_notes);
4884 /* After scheduling the function, delete redundant line notes from the
4888 rm_redundant_line_notes ()
4891 rtx insn = get_insns ();
4892 int active_insn = 0;
4895 /* Walk the insns deleting redundant line-number notes. Many of these
4896 are already present. The remainder tend to occur at basic
4897 block boundaries. */
4898 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4899 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4901 /* If there are no active insns following, INSN is redundant. */
4902 if (active_insn == 0)
4905 NOTE_SOURCE_FILE (insn) = 0;
4906 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4908 /* If the line number is unchanged, LINE is redundant. */
4910 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
4911 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
4914 NOTE_SOURCE_FILE (line) = 0;
4915 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
4922 else if (!((GET_CODE (insn) == NOTE
4923 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
4924 || (GET_CODE (insn) == INSN
4925 && (GET_CODE (PATTERN (insn)) == USE
4926 || GET_CODE (PATTERN (insn)) == CLOBBER))))
4929 if (sched_verbose && notes)
4930 fprintf (dump, ";; deleted %d line-number notes\n", notes);
4933 /* Delete notes between head and tail and put them in the chain
4934 of notes ended by NOTE_LIST. */
4937 rm_other_notes (head, tail)
4945 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4948 next_tail = NEXT_INSN (tail);
4949 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4953 /* Farm out notes, and maybe save them in NOTE_LIST.
4954 This is needed to keep the debugger from
4955 getting completely deranged. */
4956 if (GET_CODE (insn) == NOTE)
4960 insn = unlink_other_notes (insn, next_tail);
4966 if (insn == next_tail)
4972 /* Constructor for `sometimes' data structure. */
4975 new_sometimes_live (regs_sometimes_live, regno, sometimes_max)
4976 struct sometimes *regs_sometimes_live;
4980 register struct sometimes *p;
4982 /* There should never be a register greater than max_regno here. If there
4983 is, it means that a define_split has created a new pseudo reg. This
4984 is not allowed, since there will not be flow info available for any
4985 new register, so catch the error here. */
4986 if (regno >= max_regno)
4989 p = ®s_sometimes_live[sometimes_max];
4992 p->calls_crossed = 0;
4994 return sometimes_max;
4997 /* Count lengths of all regs we are currently tracking,
4998 and find new registers no longer live. */
5001 finish_sometimes_live (regs_sometimes_live, sometimes_max)
5002 struct sometimes *regs_sometimes_live;
5007 for (i = 0; i < sometimes_max; i++)
5009 register struct sometimes *p = ®s_sometimes_live[i];
5010 int regno = p->regno;
5012 sched_reg_live_length[regno] += p->live_length;
5013 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5017 /* functions for computation of registers live/usage info */
5019 /* It is assumed that prior to scheduling basic_block_live_at_start (b)
5020 contains the registers that are alive at the entry to b.
5022 Two passes follow: The first pass is performed before the scheduling
5023 of a region. It scans each block of the region forward, computing
5024 the set of registers alive at the end of the basic block and
5025 discard REG_DEAD notes (done by find_pre_sched_live ()).
5027 The second path is invoked after scheduling all region blocks.
5028 It scans each block of the region backward, a block being traversed
5029 only after its succesors in the region. When the set of registers
5030 live at the end of a basic block may be changed by the scheduling
5031 (this may happen for multiple blocks region), it is computed as
5032 the union of the registers live at the start of its succesors.
5033 The last-use information is updated by inserting REG_DEAD notes.
5034 (done by find_post_sched_live ()) */
5036 /* Scan all the insns to be scheduled, removing register death notes.
5037 Register death notes end up in DEAD_NOTES.
5038 Recreate the register life information for the end of this basic
5042 find_pre_sched_live (bb)
5045 rtx insn, next_tail, head, tail;
5046 int b = BB_TO_BLOCK (bb);
5048 get_block_head_tail (bb, &head, &tail);
5049 COPY_REG_SET (bb_live_regs, basic_block_live_at_start[b]);
5050 next_tail = NEXT_INSN (tail);
5052 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5054 rtx prev, next, link;
5057 /* Handle register life information. */
5058 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
5060 /* See if the register gets born here. */
5061 /* We must check for registers being born before we check for
5062 registers dying. It is possible for a register to be born and
5063 die in the same insn, e.g. reading from a volatile memory
5064 location into an otherwise unused register. Such a register
5065 must be marked as dead after this insn. */
5066 if (GET_CODE (PATTERN (insn)) == SET
5067 || GET_CODE (PATTERN (insn)) == CLOBBER)
5069 sched_note_set (PATTERN (insn), 0);
5073 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5076 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5077 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5078 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5080 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5084 /* ??? This code is obsolete and should be deleted. It
5085 is harmless though, so we will leave it in for now. */
5086 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5087 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
5088 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5091 /* Each call cobbers (makes live) all call-clobbered regs
5092 that are not global or fixed. Note that the function-value
5093 reg is a call_clobbered reg. */
5094 if (GET_CODE (insn) == CALL_INSN)
5097 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
5098 if (call_used_regs[j] && !global_regs[j]
5101 SET_REGNO_REG_SET (bb_live_regs, j);
5105 /* Need to know what registers this insn kills. */
5106 for (prev = 0, link = REG_NOTES (insn); link; link = next)
5108 next = XEXP (link, 1);
5109 if ((REG_NOTE_KIND (link) == REG_DEAD
5110 || REG_NOTE_KIND (link) == REG_UNUSED)
5111 /* Verify that the REG_NOTE has a valid value. */
5112 && GET_CODE (XEXP (link, 0)) == REG)
5114 register int regno = REGNO (XEXP (link, 0));
5118 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5120 if (REG_NOTE_KIND (link) == REG_DEAD)
5123 XEXP (prev, 1) = next;
5125 REG_NOTES (insn) = next;
5126 XEXP (link, 1) = dead_notes;
5132 if (regno < FIRST_PSEUDO_REGISTER)
5134 int j = HARD_REGNO_NREGS (regno,
5135 GET_MODE (XEXP (link, 0)));
5138 CLEAR_REGNO_REG_SET (bb_live_regs, regno+j);
5143 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
5151 INSN_REG_WEIGHT (insn) = reg_weight;
5155 /* Update register life and usage information for block bb
5156 after scheduling. Put register dead notes back in the code. */
5159 find_post_sched_live (bb)
5166 rtx head, tail, prev_head, next_tail;
5168 register struct sometimes *regs_sometimes_live;
5170 b = BB_TO_BLOCK (bb);
5172 /* compute live regs at the end of bb as a function of its successors. */
5173 if (current_nr_blocks > 1)
5178 first_edge = e = OUT_EDGES (b);
5179 CLEAR_REG_SET (bb_live_regs);
5186 b_succ = TO_BLOCK (e);
5187 IOR_REG_SET (bb_live_regs, basic_block_live_at_start[b_succ]);
5190 while (e != first_edge);
5193 get_block_head_tail (bb, &head, &tail);
5194 next_tail = NEXT_INSN (tail);
5195 prev_head = PREV_INSN (head);
5197 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, i,
5199 sched_reg_basic_block[i] = REG_BLOCK_GLOBAL;
5202 /* if the block is empty, same regs are alive at its end and its start.
5203 since this is not guaranteed after interblock scheduling, make sure they
5204 are truly identical. */
5205 if (NEXT_INSN (prev_head) == tail
5206 && (GET_RTX_CLASS (GET_CODE (tail)) != 'i'))
5208 if (current_nr_blocks > 1)
5209 COPY_REG_SET (basic_block_live_at_start[b], bb_live_regs);
5214 b = BB_TO_BLOCK (bb);
5215 current_block_num = b;
5217 /* Keep track of register lives. */
5218 old_live_regs = ALLOCA_REG_SET ();
5220 = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
5223 /* initiate "sometimes" data, starting with registers live at end */
5225 COPY_REG_SET (old_live_regs, bb_live_regs);
5226 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, 0, j,
5229 = new_sometimes_live (regs_sometimes_live,
5233 /* scan insns back, computing regs live info */
5234 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
5236 /* First we kill registers set by this insn, and then we
5237 make registers used by this insn live. This is the opposite
5238 order used above because we are traversing the instructions
5241 /* Strictly speaking, we should scan REG_UNUSED notes and make
5242 every register mentioned there live, however, we will just
5243 kill them again immediately below, so there doesn't seem to
5244 be any reason why we bother to do this. */
5246 /* See if this is the last notice we must take of a register. */
5247 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5250 if (GET_CODE (PATTERN (insn)) == SET
5251 || GET_CODE (PATTERN (insn)) == CLOBBER)
5252 sched_note_set (PATTERN (insn), 1);
5253 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5255 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5256 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5257 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5258 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 1);
5261 /* This code keeps life analysis information up to date. */
5262 if (GET_CODE (insn) == CALL_INSN)
5264 register struct sometimes *p;
5266 /* A call kills all call used registers that are not
5267 global or fixed, except for those mentioned in the call
5268 pattern which will be made live again later. */
5269 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5270 if (call_used_regs[i] && ! global_regs[i]
5273 CLEAR_REGNO_REG_SET (bb_live_regs, i);
5276 /* Regs live at the time of a call instruction must not
5277 go in a register clobbered by calls. Record this for
5278 all regs now live. Note that insns which are born or
5279 die in a call do not cross a call, so this must be done
5280 after the killings (above) and before the births
5282 p = regs_sometimes_live;
5283 for (i = 0; i < sometimes_max; i++, p++)
5284 if (REGNO_REG_SET_P (bb_live_regs, p->regno))
5285 p->calls_crossed += 1;
5288 /* Make every register used live, and add REG_DEAD notes for
5289 registers which were not live before we started. */
5290 attach_deaths_insn (insn);
5292 /* Find registers now made live by that instruction. */
5293 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs, old_live_regs, 0, j,
5296 = new_sometimes_live (regs_sometimes_live,
5299 IOR_REG_SET (old_live_regs, bb_live_regs);
5301 /* Count lengths of all regs we are worrying about now,
5302 and handle registers no longer live. */
5304 for (i = 0; i < sometimes_max; i++)
5306 register struct sometimes *p = ®s_sometimes_live[i];
5307 int regno = p->regno;
5309 p->live_length += 1;
5311 if (!REGNO_REG_SET_P (bb_live_regs, regno))
5313 /* This is the end of one of this register's lifetime
5314 segments. Save the lifetime info collected so far,
5315 and clear its bit in the old_live_regs entry. */
5316 sched_reg_live_length[regno] += p->live_length;
5317 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5318 CLEAR_REGNO_REG_SET (old_live_regs, p->regno);
5320 /* Delete the reg_sometimes_live entry for this reg by
5321 copying the last entry over top of it. */
5322 *p = regs_sometimes_live[--sometimes_max];
5323 /* ...and decrement i so that this newly copied entry
5324 will be processed. */
5330 finish_sometimes_live (regs_sometimes_live, sometimes_max);
5332 /* In interblock scheduling, basic_block_live_at_start may have changed. */
5333 if (current_nr_blocks > 1)
5334 COPY_REG_SET (basic_block_live_at_start[b], bb_live_regs);
5337 FREE_REG_SET (old_live_regs);
5338 } /* find_post_sched_live */
5340 /* After scheduling the subroutine, restore information about uses of
5348 if (n_basic_blocks > 0)
5349 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, regno,
5351 sched_reg_basic_block[regno]
5355 for (regno = 0; regno < max_regno; regno++)
5356 if (sched_reg_live_length[regno])
5360 if (REG_LIVE_LENGTH (regno) > sched_reg_live_length[regno])
5362 ";; register %d life shortened from %d to %d\n",
5363 regno, REG_LIVE_LENGTH (regno),
5364 sched_reg_live_length[regno]);
5365 /* Negative values are special; don't overwrite the current
5366 reg_live_length value if it is negative. */
5367 else if (REG_LIVE_LENGTH (regno) < sched_reg_live_length[regno]
5368 && REG_LIVE_LENGTH (regno) >= 0)
5370 ";; register %d life extended from %d to %d\n",
5371 regno, REG_LIVE_LENGTH (regno),
5372 sched_reg_live_length[regno]);
5374 if (!REG_N_CALLS_CROSSED (regno)
5375 && sched_reg_n_calls_crossed[regno])
5377 ";; register %d now crosses calls\n", regno);
5378 else if (REG_N_CALLS_CROSSED (regno)
5379 && !sched_reg_n_calls_crossed[regno]
5380 && REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5382 ";; register %d no longer crosses calls\n", regno);
5384 if (REG_BASIC_BLOCK (regno) != sched_reg_basic_block[regno]
5385 && sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5386 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5388 ";; register %d changed basic block from %d to %d\n",
5389 regno, REG_BASIC_BLOCK(regno),
5390 sched_reg_basic_block[regno]);
5393 /* Negative values are special; don't overwrite the current
5394 reg_live_length value if it is negative. */
5395 if (REG_LIVE_LENGTH (regno) >= 0)
5396 REG_LIVE_LENGTH (regno) = sched_reg_live_length[regno];
5398 if (sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5399 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5400 REG_BASIC_BLOCK(regno) = sched_reg_basic_block[regno];
5402 /* We can't change the value of reg_n_calls_crossed to zero for
5403 pseudos which are live in more than one block.
5405 This is because combine might have made an optimization which
5406 invalidated basic_block_live_at_start and reg_n_calls_crossed,
5407 but it does not update them. If we update reg_n_calls_crossed
5408 here, the two variables are now inconsistent, and this might
5409 confuse the caller-save code into saving a register that doesn't
5410 need to be saved. This is only a problem when we zero calls
5411 crossed for a pseudo live in multiple basic blocks.
5413 Alternatively, we could try to correctly update basic block live
5414 at start here in sched, but that seems complicated.
5416 Note: it is possible that a global register became local, as result
5417 of interblock motion, but will remain marked as a global register. */
5418 if (sched_reg_n_calls_crossed[regno]
5419 || REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5420 REG_N_CALLS_CROSSED (regno) = sched_reg_n_calls_crossed[regno];
5425 /* Scheduling clock, modified in schedule_block() and queue_to_ready () */
5426 static int clock_var;
5428 /* Move insns that became ready to fire from queue to ready list. */
5431 queue_to_ready (ready, n_ready)
5438 q_ptr = NEXT_Q (q_ptr);
5440 /* Add all pending insns that can be scheduled without stalls to the
5442 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
5445 insn = XEXP (link, 0);
5448 if (sched_verbose >= 2)
5449 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5451 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5452 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5454 ready[n_ready++] = insn;
5455 if (sched_verbose >= 2)
5456 fprintf (dump, "moving to ready without stalls\n");
5458 insn_queue[q_ptr] = 0;
5460 /* If there are no ready insns, stall until one is ready and add all
5461 of the pending insns at that point to the ready list. */
5464 register int stalls;
5466 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
5468 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
5470 for (; link; link = XEXP (link, 1))
5472 insn = XEXP (link, 0);
5475 if (sched_verbose >= 2)
5476 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5478 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5479 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5481 ready[n_ready++] = insn;
5482 if (sched_verbose >= 2)
5483 fprintf (dump, "moving to ready with %d stalls\n", stalls);
5485 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
5492 if (sched_verbose && stalls)
5493 visualize_stall_cycles (BB_TO_BLOCK (target_bb), stalls);
5494 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
5495 clock_var += stalls;
5500 /* Print the ready list for debugging purposes. Callable from debugger. */
5503 debug_ready_list (ready, n_ready)
5509 for (i = 0; i < n_ready; i++)
5511 fprintf (dump, " %d", INSN_UID (ready[i]));
5512 if (current_nr_blocks > 1 && INSN_BB (ready[i]) != target_bb)
5513 fprintf (dump, "/b%d", INSN_BLOCK (ready[i]));
5515 fprintf (dump, "\n");
5518 /* Print names of units on which insn can/should execute, for debugging. */
5521 insn_print_units (insn)
5525 int unit = insn_unit (insn);
5528 fprintf (dump, "none");
5530 fprintf (dump, "%s", function_units[unit].name);
5533 fprintf (dump, "[");
5534 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
5537 fprintf (dump, "%s", function_units[i].name);
5539 fprintf (dump, " ");
5541 fprintf (dump, "]");
5545 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5546 of a basic block. If more lines are needed, table is splitted to two.
5547 n_visual_lines is the number of lines printed so far for a block.
5548 visual_tbl contains the block visualization info.
5549 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5550 #define MAX_VISUAL_LINES 100
5555 rtx vis_no_unit[10];
5557 /* Finds units that are in use in this fuction. Required only
5558 for visualization. */
5561 init_target_units ()
5566 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
5568 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5571 unit = insn_unit (insn);
5574 target_units |= ~unit;
5576 target_units |= (1 << unit);
5580 /* Return the length of the visualization table */
5583 get_visual_tbl_length ()
5589 /* compute length of one field in line */
5590 s = (char *) alloca (INSN_LEN + 5);
5591 sprintf (s, " %33s", "uname");
5594 /* compute length of one line */
5597 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5598 if (function_units[unit].bitmask & target_units)
5599 for (i = 0; i < function_units[unit].multiplicity; i++)
5602 n += strlen ("\n") + 2;
5604 /* compute length of visualization string */
5605 return (MAX_VISUAL_LINES * n);
5608 /* Init block visualization debugging info */
5611 init_block_visualization ()
5613 strcpy (visual_tbl, "");
5621 safe_concat (buf, cur, str)
5626 char *end = buf + BUF_LEN - 2; /* leave room for null */
5635 while (cur < end && (c = *str++) != '\0')
5642 /* This recognizes rtx, I classified as expressions. These are always */
5643 /* represent some action on values or results of other expression, */
5644 /* that may be stored in objects representing values. */
5647 print_exp (buf, x, verbose)
5655 char *fun = (char *)0;
5660 for (i = 0; i < 4; i++)
5666 switch (GET_CODE (x))
5669 op[0] = XEXP (x, 0);
5671 op[1] = XEXP (x, 1);
5674 op[0] = XEXP (x, 0);
5676 op[1] = XEXP (x, 1);
5680 op[0] = XEXP (x, 0);
5682 op[1] = XEXP (x, 1);
5686 op[0] = XEXP (x, 0);
5687 op[1] = XEXP (x, 1);
5691 op[0] = XEXP (x, 0);
5694 op[0] = XEXP (x, 0);
5696 op[1] = XEXP (x, 1);
5699 op[0] = XEXP (x, 0);
5701 op[1] = XEXP (x, 1);
5705 op[0] = XEXP (x, 0);
5706 op[1] = XEXP (x, 1);
5709 op[0] = XEXP (x, 0);
5711 op[1] = XEXP (x, 1);
5715 op[0] = XEXP (x, 0);
5716 op[1] = XEXP (x, 1);
5720 op[0] = XEXP (x, 0);
5721 op[1] = XEXP (x, 1);
5725 op[0] = XEXP (x, 0);
5726 op[1] = XEXP (x, 1);
5730 op[0] = XEXP (x, 0);
5731 op[1] = XEXP (x, 1);
5735 op[0] = XEXP (x, 0);
5736 op[1] = XEXP (x, 1);
5740 op[0] = XEXP (x, 0);
5743 op[0] = XEXP (x, 0);
5745 op[1] = XEXP (x, 1);
5748 op[0] = XEXP (x, 0);
5750 op[1] = XEXP (x, 1);
5753 op[0] = XEXP (x, 0);
5755 op[1] = XEXP (x, 1);
5758 op[0] = XEXP (x, 0);
5760 op[1] = XEXP (x, 1);
5763 op[0] = XEXP (x, 0);
5765 op[1] = XEXP (x, 1);
5768 op[0] = XEXP (x, 0);
5770 op[1] = XEXP (x, 1);
5773 op[0] = XEXP (x, 0);
5775 op[1] = XEXP (x, 1);
5778 op[0] = XEXP (x, 0);
5780 op[1] = XEXP (x, 1);
5784 op[0] = XEXP (x, 0);
5788 op[0] = XEXP (x, 0);
5792 op[0] = XEXP (x, 0);
5795 op[0] = XEXP (x, 0);
5797 op[1] = XEXP (x, 1);
5800 op[0] = XEXP (x, 0);
5802 op[1] = XEXP (x, 1);
5805 op[0] = XEXP (x, 0);
5807 op[1] = XEXP (x, 1);
5811 op[0] = XEXP (x, 0);
5812 op[1] = XEXP (x, 1);
5815 op[0] = XEXP (x, 0);
5817 op[1] = XEXP (x, 1);
5821 op[0] = XEXP (x, 0);
5822 op[1] = XEXP (x, 1);
5825 op[0] = XEXP (x, 0);
5827 op[1] = XEXP (x, 1);
5831 op[0] = XEXP (x, 0);
5832 op[1] = XEXP (x, 1);
5835 op[0] = XEXP (x, 0);
5837 op[1] = XEXP (x, 1);
5841 op[0] = XEXP (x, 0);
5842 op[1] = XEXP (x, 1);
5845 fun = (verbose) ? "sign_extract" : "sxt";
5846 op[0] = XEXP (x, 0);
5847 op[1] = XEXP (x, 1);
5848 op[2] = XEXP (x, 2);
5851 fun = (verbose) ? "zero_extract" : "zxt";
5852 op[0] = XEXP (x, 0);
5853 op[1] = XEXP (x, 1);
5854 op[2] = XEXP (x, 2);
5857 fun = (verbose) ? "sign_extend" : "sxn";
5858 op[0] = XEXP (x, 0);
5861 fun = (verbose) ? "zero_extend" : "zxn";
5862 op[0] = XEXP (x, 0);
5865 fun = (verbose) ? "float_extend" : "fxn";
5866 op[0] = XEXP (x, 0);
5869 fun = (verbose) ? "trunc" : "trn";
5870 op[0] = XEXP (x, 0);
5872 case FLOAT_TRUNCATE:
5873 fun = (verbose) ? "float_trunc" : "ftr";
5874 op[0] = XEXP (x, 0);
5877 fun = (verbose) ? "float" : "flt";
5878 op[0] = XEXP (x, 0);
5880 case UNSIGNED_FLOAT:
5881 fun = (verbose) ? "uns_float" : "ufl";
5882 op[0] = XEXP (x, 0);
5886 op[0] = XEXP (x, 0);
5889 fun = (verbose) ? "uns_fix" : "ufx";
5890 op[0] = XEXP (x, 0);
5894 op[0] = XEXP (x, 0);
5898 op[0] = XEXP (x, 0);
5901 op[0] = XEXP (x, 0);
5905 op[0] = XEXP (x, 0);
5910 op[0] = XEXP (x, 0);
5914 op[1] = XEXP (x, 1);
5919 op[0] = XEXP (x, 0);
5921 op[1] = XEXP (x, 1);
5923 op[2] = XEXP (x, 2);
5928 op[0] = TRAP_CONDITION (x);
5931 case UNSPEC_VOLATILE:
5933 cur = safe_concat (buf, cur, "unspec");
5934 if (GET_CODE (x) == UNSPEC_VOLATILE)
5935 cur = safe_concat (buf, cur, "/v");
5936 cur = safe_concat (buf, cur, "[");
5938 for (i = 0; i < XVECLEN (x, 0); i++)
5940 print_pattern (tmp, XVECEXP (x, 0, i), verbose);
5941 cur = safe_concat (buf, cur, sep);
5942 cur = safe_concat (buf, cur, tmp);
5945 cur = safe_concat (buf, cur, "] ");
5946 sprintf (tmp, "%d", XINT (x, 1));
5947 cur = safe_concat (buf, cur, tmp);
5951 /* if (verbose) debug_rtx (x); */
5952 st[0] = GET_RTX_NAME (GET_CODE (x));
5956 /* Print this as a function? */
5959 cur = safe_concat (buf, cur, fun);
5960 cur = safe_concat (buf, cur, "(");
5963 for (i = 0; i < 4; i++)
5966 cur = safe_concat (buf, cur, st[i]);
5971 cur = safe_concat (buf, cur, ",");
5973 print_value (tmp, op[i], verbose);
5974 cur = safe_concat (buf, cur, tmp);
5979 cur = safe_concat (buf, cur, ")");
5982 /* Prints rtxes, i customly classified as values. They're constants, */
5983 /* registers, labels, symbols and memory accesses. */
5986 print_value (buf, x, verbose)
5994 switch (GET_CODE (x))
5997 sprintf (t, "0x%lx", (long)INTVAL (x));
5998 cur = safe_concat (buf, cur, t);
6001 sprintf (t, "<0x%lx,0x%lx>", (long)XWINT (x, 2), (long)XWINT (x, 3));
6002 cur = safe_concat (buf, cur, t);
6005 cur = safe_concat (buf, cur, "\"");
6006 cur = safe_concat (buf, cur, XSTR (x, 0));
6007 cur = safe_concat (buf, cur, "\"");
6010 cur = safe_concat (buf, cur, "`");
6011 cur = safe_concat (buf, cur, XSTR (x, 0));
6012 cur = safe_concat (buf, cur, "'");
6015 sprintf (t, "L%d", INSN_UID (XEXP (x, 0)));
6016 cur = safe_concat (buf, cur, t);
6019 print_value (t, XEXP (x, 0), verbose);
6020 cur = safe_concat (buf, cur, "const(");
6021 cur = safe_concat (buf, cur, t);
6022 cur = safe_concat (buf, cur, ")");
6025 print_value (t, XEXP (x, 0), verbose);
6026 cur = safe_concat (buf, cur, "high(");
6027 cur = safe_concat (buf, cur, t);
6028 cur = safe_concat (buf, cur, ")");
6031 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
6033 int c = reg_names[ REGNO (x) ][0];
6034 if (c >= '0' && c <= '9')
6035 cur = safe_concat (buf, cur, "%");
6037 cur = safe_concat (buf, cur, reg_names[ REGNO (x) ]);
6041 sprintf (t, "r%d", REGNO (x));
6042 cur = safe_concat (buf, cur, t);
6046 print_value (t, SUBREG_REG (x), verbose);
6047 cur = safe_concat (buf, cur, t);
6048 sprintf (t, "#%d", SUBREG_WORD (x));
6049 cur = safe_concat (buf, cur, t);
6052 cur = safe_concat (buf, cur, "scratch");
6055 cur = safe_concat (buf, cur, "cc0");
6058 cur = safe_concat (buf, cur, "pc");
6061 print_value (t, XEXP (x, 0), verbose);
6062 cur = safe_concat (buf, cur, "[");
6063 cur = safe_concat (buf, cur, t);
6064 cur = safe_concat (buf, cur, "]");
6067 print_exp (t, x, verbose);
6068 cur = safe_concat (buf, cur, t);
6073 /* The next step in insn detalization, its pattern recognition */
6076 print_pattern (buf, x, verbose)
6081 char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
6083 switch (GET_CODE (x))
6086 print_value (t1, SET_DEST (x), verbose);
6087 print_value (t2, SET_SRC (x), verbose);
6088 sprintf (buf, "%s=%s", t1, t2);
6091 sprintf (buf, "return");
6094 print_exp (buf, x, verbose);
6097 print_value (t1, XEXP (x, 0), verbose);
6098 sprintf (buf, "clobber %s", t1);
6101 print_value (t1, XEXP (x, 0), verbose);
6102 sprintf (buf, "use %s", t1);
6109 for (i = 0; i < XVECLEN (x, 0); i++)
6111 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6112 sprintf (t3, "%s%s;", t1, t2);
6115 sprintf (buf, "%s}", t1);
6122 sprintf (t1, "%%{");
6123 for (i = 0; i < XVECLEN (x, 0); i++)
6125 print_insn (t2, XVECEXP (x, 0, i), verbose);
6126 sprintf (t3, "%s%s;", t1, t2);
6129 sprintf (buf, "%s%%}", t1);
6133 sprintf (buf, "asm {%s}", XSTR (x, 0));
6138 print_value (buf, XEXP (x, 0), verbose);
6141 print_value (t1, TRAP_CONDITION (x), verbose);
6142 sprintf (buf, "trap_if %s", t1);
6148 sprintf (t1, "unspec{");
6149 for (i = 0; i < XVECLEN (x, 0); i++)
6151 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6152 sprintf (t3, "%s%s;", t1, t2);
6155 sprintf (buf, "%s}", t1);
6158 case UNSPEC_VOLATILE:
6162 sprintf (t1, "unspec/v{");
6163 for (i = 0; i < XVECLEN (x, 0); i++)
6165 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6166 sprintf (t3, "%s%s;", t1, t2);
6169 sprintf (buf, "%s}", t1);
6173 print_value (buf, x, verbose);
6175 } /* print_pattern */
6177 /* This is the main function in rtl visualization mechanism. It
6178 accepts an rtx and tries to recognize it as an insn, then prints it
6179 properly in human readable form, resembling assembler mnemonics. */
6180 /* For every insn it prints its UID and BB the insn belongs */
6181 /* too. (probably the last "option" should be extended somehow, since */
6182 /* it depends now on sched.c inner variables ...) */
6185 print_insn (buf, x, verbose)
6193 switch (GET_CODE (x))
6196 print_pattern (t, PATTERN (x), verbose);
6198 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (x),
6201 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6204 print_pattern (t, PATTERN (x), verbose);
6206 sprintf (buf, "b%d: i% 4d: jump %s", INSN_BB (x),
6209 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6213 if (GET_CODE (x) == PARALLEL)
6215 x = XVECEXP (x, 0, 0);
6216 print_pattern (t, x, verbose);
6219 strcpy (t, "call <...>");
6221 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (insn),
6222 INSN_UID (insn), t);
6224 sprintf (buf, "%-4d %s", INSN_UID (insn), t);
6227 sprintf (buf, "L%d:", INSN_UID (x));
6230 sprintf (buf, "i% 4d: barrier", INSN_UID (x));
6233 if (NOTE_LINE_NUMBER (x) > 0)
6234 sprintf (buf, "%4d note \"%s\" %d", INSN_UID (x),
6235 NOTE_SOURCE_FILE (x), NOTE_LINE_NUMBER (x));
6237 sprintf (buf, "%4d %s", INSN_UID (x),
6238 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x)));
6243 sprintf (buf, "Not an INSN at all\n");
6247 sprintf (buf, "i%-4d <What?>", INSN_UID (x));
6252 print_insn_chain (rtx_first)
6255 register rtx tmp_rtx;
6258 strcpy (str, "(nil)\n");
6260 switch (GET_CODE (rtx_first))
6268 for (tmp_rtx = rtx_first; tmp_rtx != NULL;
6269 tmp_rtx = NEXT_INSN (tmp_rtx))
6271 print_insn (str, tmp_rtx, 0);
6272 printf ("%s\n", str);
6276 print_insn (str, rtx_first, 0);
6277 printf ("%s\n", str);
6279 } /* print_insn_chain */
6281 /* Print visualization debugging info */
6284 print_block_visualization (b, s)
6291 fprintf (dump, "\n;; ==================== scheduling visualization for block %d %s \n", b, s);
6293 /* Print names of units */
6294 fprintf (dump, ";; %-8s", "clock");
6295 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6296 if (function_units[unit].bitmask & target_units)
6297 for (i = 0; i < function_units[unit].multiplicity; i++)
6298 fprintf (dump, " %-33s", function_units[unit].name);
6299 fprintf (dump, " %-8s\n", "no-unit");
6301 fprintf (dump, ";; %-8s", "=====");
6302 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6303 if (function_units[unit].bitmask & target_units)
6304 for (i = 0; i < function_units[unit].multiplicity; i++)
6305 fprintf (dump, " %-33s", "==============================");
6306 fprintf (dump, " %-8s\n", "=======");
6308 /* Print insns in each cycle */
6309 fprintf (dump, "%s\n", visual_tbl);
6312 /* Print insns in the 'no_unit' column of visualization */
6315 visualize_no_unit (insn)
6318 vis_no_unit[n_vis_no_unit] = insn;
6322 /* Print insns scheduled in clock, for visualization. */
6325 visualize_scheduled_insns (b, clock)
6330 /* if no more room, split table into two */
6331 if (n_visual_lines >= MAX_VISUAL_LINES)
6333 print_block_visualization (b, "(incomplete)");
6334 init_block_visualization ();
6339 sprintf (visual_tbl + strlen (visual_tbl), ";; %-8d", clock);
6340 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6341 if (function_units[unit].bitmask & target_units)
6342 for (i = 0; i < function_units[unit].multiplicity; i++)
6344 int instance = unit + i * FUNCTION_UNITS_SIZE;
6345 rtx insn = unit_last_insn[instance];
6347 /* print insns that still keep the unit busy */
6349 actual_hazard_this_instance (unit, instance, insn, clock, 0))
6352 print_insn (str, insn, 0);
6353 str[INSN_LEN] = '\0';
6354 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", str);
6357 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", "------------------------------");
6360 /* print insns that are not assigned to any unit */
6361 for (i = 0; i < n_vis_no_unit; i++)
6362 sprintf (visual_tbl + strlen (visual_tbl), " %-8d",
6363 INSN_UID (vis_no_unit[i]));
6366 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6369 /* Print stalled cycles */
6372 visualize_stall_cycles (b, stalls)
6377 /* if no more room, split table into two */
6378 if (n_visual_lines >= MAX_VISUAL_LINES)
6380 print_block_visualization (b, "(incomplete)");
6381 init_block_visualization ();
6386 sprintf (visual_tbl + strlen (visual_tbl), ";; ");
6387 for (i = 0; i < stalls; i++)
6388 sprintf (visual_tbl + strlen (visual_tbl), ".");
6389 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6392 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn */
6395 move_insn1 (insn, last)
6398 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
6399 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
6401 NEXT_INSN (insn) = NEXT_INSN (last);
6402 PREV_INSN (NEXT_INSN (last)) = insn;
6404 NEXT_INSN (last) = insn;
6405 PREV_INSN (insn) = last;
6410 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
6411 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
6412 NOTEs. The REG_DEAD note following first one is contains the saved
6413 value for NOTE_BLOCK_NUMBER which is useful for
6414 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
6415 output by the instruction scheduler. Return the new value of LAST. */
6418 reemit_notes (insn, last)
6425 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
6427 if (REG_NOTE_KIND (note) == REG_DEAD
6428 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6430 if (INTVAL (XEXP (note, 0)) == NOTE_INSN_SETJMP)
6432 retval = emit_note_after (INTVAL (XEXP (note, 0)), insn);
6433 CONST_CALL_P (retval) = CONST_CALL_P (note);
6434 remove_note (insn, note);
6435 note = XEXP (note, 1);
6439 last = emit_note_before (INTVAL (XEXP (note, 0)), last);
6440 remove_note (insn, note);
6441 note = XEXP (note, 1);
6442 NOTE_BLOCK_NUMBER (last) = INTVAL (XEXP (note, 0));
6444 remove_note (insn, note);
6450 /* Move INSN, and all insns which should be issued before it,
6451 due to SCHED_GROUP_P flag. Reemit notes if needed.
6453 Return the last insn emitted by the scheduler, which is the
6454 return value from the first call to reemit_notes. */
6457 move_insn (insn, last)
6462 /* If INSN has SCHED_GROUP_P set, then issue it and any other
6463 insns with SCHED_GROUP_P set first. */
6464 while (SCHED_GROUP_P (insn))
6466 rtx prev = PREV_INSN (insn);
6468 /* Move a SCHED_GROUP_P insn. */
6469 move_insn1 (insn, last);
6470 /* If this is the first call to reemit_notes, then record
6471 its return value. */
6472 if (retval == NULL_RTX)
6473 retval = reemit_notes (insn, insn);
6475 reemit_notes (insn, insn);
6479 /* Now move the first non SCHED_GROUP_P insn. */
6480 move_insn1 (insn, last);
6482 /* If this is the first call to reemit_notes, then record
6483 its return value. */
6484 if (retval == NULL_RTX)
6485 retval = reemit_notes (insn, insn);
6487 reemit_notes (insn, insn);
6492 /* Return an insn which represents a SCHED_GROUP, which is
6493 the last insn in the group. */
6504 insn = next_nonnote_insn (insn);
6506 while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
6511 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
6512 possibly bringing insns from subsequent blocks in the same region.
6513 Return number of insns scheduled. */
6516 schedule_block (bb, rgn_n_insns)
6520 /* Local variables. */
6527 /* flow block of this bb */
6528 int b = BB_TO_BLOCK (bb);
6530 /* target_n_insns == number of insns in b before scheduling starts.
6531 sched_target_n_insns == how many of b's insns were scheduled.
6532 sched_n_insns == how many insns were scheduled in b */
6533 int target_n_insns = 0;
6534 int sched_target_n_insns = 0;
6535 int sched_n_insns = 0;
6537 #define NEED_NOTHING 0
6542 /* head/tail info for this block */
6549 /* We used to have code to avoid getting parameters moved from hard
6550 argument registers into pseudos.
6552 However, it was removed when it proved to be of marginal benefit
6553 and caused problems because schedule_block and compute_forward_dependences
6554 had different notions of what the "head" insn was. */
6555 get_block_head_tail (bb, &head, &tail);
6557 /* Interblock scheduling could have moved the original head insn from this
6558 block into a proceeding block. This may also cause schedule_block and
6559 compute_forward_dependences to have different notions of what the
6562 If the interblock movement happened to make this block start with
6563 some notes (LOOP, EH or SETJMP) before the first real insn, then
6564 HEAD will have various special notes attached to it which must be
6565 removed so that we don't end up with extra copies of the notes. */
6566 if (GET_RTX_CLASS (GET_CODE (head)) == 'i')
6570 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
6571 if (REG_NOTE_KIND (note) == REG_DEAD
6572 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6573 remove_note (head, note);
6576 next_tail = NEXT_INSN (tail);
6577 prev_head = PREV_INSN (head);
6579 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6580 to schedule this block. */
6582 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6583 return (sched_n_insns);
6588 fprintf (dump, ";; ======================================================\n");
6590 ";; -- basic block %d from %d to %d -- %s reload\n",
6591 b, INSN_UID (basic_block_head[b]),
6592 INSN_UID (basic_block_end[b]),
6593 (reload_completed ? "after" : "before"));
6594 fprintf (dump, ";; ======================================================\n");
6595 fprintf (dump, "\n");
6597 visual_tbl = (char *) alloca (get_visual_tbl_length ());
6598 init_block_visualization ();
6601 /* remove remaining note insns from the block, save them in
6602 note_list. These notes are restored at the end of
6603 schedule_block (). */
6605 rm_other_notes (head, tail);
6609 /* prepare current target block info */
6610 if (current_nr_blocks > 1)
6612 candidate_table = (candidate *) alloca (current_nr_blocks * sizeof (candidate));
6615 /* ??? It is not clear why bblst_size is computed this way. The original
6616 number was clearly too small as it resulted in compiler failures.
6617 Multiplying by the original number by 2 (to account for update_bbs
6618 members) seems to be a reasonable solution. */
6619 /* ??? Or perhaps there is a bug somewhere else in this file? */
6620 bblst_size = (current_nr_blocks - bb) * rgn_nr_edges * 2;
6621 bblst_table = (int *) alloca (bblst_size * sizeof (int));
6623 bitlst_table_last = 0;
6624 bitlst_table_size = rgn_nr_edges;
6625 bitlst_table = (int *) alloca (rgn_nr_edges * sizeof (int));
6627 compute_trg_info (bb);
6632 /* Allocate the ready list */
6633 ready = (rtx *) alloca ((rgn_n_insns + 1) * sizeof (rtx));
6635 /* Print debugging information. */
6636 if (sched_verbose >= 5)
6637 debug_dependencies ();
6640 /* Initialize ready list with all 'ready' insns in target block.
6641 Count number of insns in the target block being scheduled. */
6643 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6647 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6649 next = NEXT_INSN (insn);
6651 if (INSN_DEP_COUNT (insn) == 0
6652 && (SCHED_GROUP_P (next) == 0 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6653 ready[n_ready++] = insn;
6654 if (!(SCHED_GROUP_P (insn)))
6658 /* Add to ready list all 'ready' insns in valid source blocks.
6659 For speculative insns, check-live, exception-free, and
6661 for (bb_src = bb + 1; bb_src < current_nr_blocks; bb_src++)
6662 if (IS_VALID (bb_src))
6668 get_block_head_tail (bb_src, &head, &tail);
6669 src_next_tail = NEXT_INSN (tail);
6673 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6676 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
6678 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6681 if (!CANT_MOVE (insn)
6682 && (!IS_SPECULATIVE_INSN (insn)
6683 || (insn_issue_delay (insn) <= 3
6684 && check_live (insn, bb_src)
6685 && is_exception_free (insn, bb_src, target_bb))))
6690 next = NEXT_INSN (insn);
6691 if (INSN_DEP_COUNT (insn) == 0
6692 && (SCHED_GROUP_P (next) == 0
6693 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6694 ready[n_ready++] = insn;
6699 /* no insns scheduled in this block yet */
6700 last_scheduled_insn = 0;
6702 /* Sort the ready list */
6703 SCHED_SORT (ready, n_ready);
6705 if (sched_verbose >= 2)
6707 fprintf (dump, ";;\t\tReady list initially: ");
6708 debug_ready_list (ready, n_ready);
6711 /* Q_SIZE is the total number of insns in the queue. */
6715 bzero ((char *) insn_queue, sizeof (insn_queue));
6717 /* We start inserting insns after PREV_HEAD. */
6720 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6721 new_needs = (NEXT_INSN (prev_head) == basic_block_head[b]
6722 ? NEED_HEAD : NEED_NOTHING);
6723 if (PREV_INSN (next_tail) == basic_block_end[b])
6724 new_needs |= NEED_TAIL;
6726 /* loop until all the insns in BB are scheduled. */
6727 while (sched_target_n_insns < target_n_insns)
6733 /* Add to the ready list all pending insns that can be issued now.
6734 If there are no ready insns, increment clock until one
6735 is ready and add all pending insns at that point to the ready
6737 n_ready = queue_to_ready (ready, n_ready);
6742 if (sched_verbose >= 2)
6744 fprintf (dump, ";;\t\tReady list after queue_to_ready: ");
6745 debug_ready_list (ready, n_ready);
6748 /* Sort the ready list. */
6749 SCHED_SORT (ready, n_ready);
6753 fprintf (dump, "\n;;\tReady list (t =%3d): ", clock_var);
6754 debug_ready_list (ready, n_ready);
6757 /* Issue insns from ready list.
6758 It is important to count down from n_ready, because n_ready may change
6759 as insns are issued. */
6760 can_issue_more = issue_rate;
6761 for (i = n_ready - 1; i >= 0 && can_issue_more; i--)
6763 rtx insn = ready[i];
6764 int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
6768 queue_insn (insn, cost);
6769 ready[i] = ready[--n_ready]; /* remove insn from ready list */
6773 /* an interblock motion? */
6774 if (INSN_BB (insn) != target_bb)
6778 if (IS_SPECULATIVE_INSN (insn))
6781 if (!check_live (insn, INSN_BB (insn)))
6783 /* speculative motion, live check failed, remove
6784 insn from ready list */
6785 ready[i] = ready[--n_ready];
6788 update_live (insn, INSN_BB (insn));
6790 /* for speculative load, mark insns fed by it. */
6791 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
6792 set_spec_fed (insn);
6799 while (SCHED_GROUP_P (temp))
6800 temp = PREV_INSN (temp);
6802 /* Update source block boundaries. */
6803 b1 = INSN_BLOCK (temp);
6804 if (temp == basic_block_head[b1]
6805 && insn == basic_block_end[b1])
6807 /* We moved all the insns in the basic block.
6808 Emit a note after the last insn and update the
6809 begin/end boundaries to point to the note. */
6810 emit_note_after (NOTE_INSN_DELETED, insn);
6811 basic_block_end[b1] = NEXT_INSN (insn);
6812 basic_block_head[b1] = NEXT_INSN (insn);
6814 else if (insn == basic_block_end[b1])
6816 /* We took insns from the end of the basic block,
6817 so update the end of block boundary so that it
6818 points to the first insn we did not move. */
6819 basic_block_end[b1] = PREV_INSN (temp);
6821 else if (temp == basic_block_head[b1])
6823 /* We took insns from the start of the basic block,
6824 so update the start of block boundary so that
6825 it points to the first insn we did not move. */
6826 basic_block_head[b1] = NEXT_INSN (insn);
6831 /* in block motion */
6832 sched_target_n_insns++;
6835 last_scheduled_insn = insn;
6836 last = move_insn (insn, last);
6841 n_ready = schedule_insn (insn, ready, n_ready, clock_var);
6843 /* remove insn from ready list */
6844 ready[i] = ready[--n_ready];
6846 /* close this block after scheduling its jump */
6847 if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
6855 visualize_scheduled_insns (b, clock_var);
6862 fprintf (dump, ";;\tReady list (final): ");
6863 debug_ready_list (ready, n_ready);
6864 print_block_visualization (b, "");
6867 /* Sanity check -- queue must be empty now. Meaningless if region has
6869 if (current_nr_blocks > 1)
6870 if (!flag_schedule_interblock && q_size != 0)
6873 /* update head/tail boundaries. */
6874 head = NEXT_INSN (prev_head);
6877 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6878 previously found among the insns. Insert them at the beginning
6882 rtx note_head = note_list;
6884 while (PREV_INSN (note_head))
6886 note_head = PREV_INSN (note_head);
6889 PREV_INSN (note_head) = PREV_INSN (head);
6890 NEXT_INSN (PREV_INSN (head)) = note_head;
6891 PREV_INSN (head) = note_list;
6892 NEXT_INSN (note_list) = head;
6896 /* update target block boundaries. */
6897 if (new_needs & NEED_HEAD)
6898 basic_block_head[b] = head;
6900 if (new_needs & NEED_TAIL)
6901 basic_block_end[b] = tail;
6906 fprintf (dump, ";; total time = %d\n;; new basic block head = %d\n",
6907 clock_var, INSN_UID (basic_block_head[b]));
6908 fprintf (dump, ";; new basic block end = %d\n\n",
6909 INSN_UID (basic_block_end[b]));
6912 return (sched_n_insns);
6913 } /* schedule_block () */
6916 /* print the bit-set of registers, S. callable from debugger */
6919 debug_reg_vector (s)
6924 EXECUTE_IF_SET_IN_REG_SET (s, 0, regno,
6926 fprintf (dump, " %d", regno);
6929 fprintf (dump, "\n");
6932 /* Use the backward dependences from LOG_LINKS to build
6933 forward dependences in INSN_DEPEND. */
6936 compute_block_forward_dependences (bb)
6942 enum reg_note dep_type;
6944 get_block_head_tail (bb, &head, &tail);
6945 next_tail = NEXT_INSN (tail);
6946 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6948 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6951 insn = group_leader (insn);
6953 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
6955 rtx x = group_leader (XEXP (link, 0));
6958 if (x != XEXP (link, 0))
6961 /* Ignore dependences upon deleted insn */
6962 if (GET_CODE (x) == NOTE || INSN_DELETED_P (x))
6964 if (find_insn_list (insn, INSN_DEPEND (x)))
6967 new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
6969 dep_type = REG_NOTE_KIND (link);
6970 PUT_REG_NOTE_KIND (new_link, dep_type);
6972 INSN_DEPEND (x) = new_link;
6973 INSN_DEP_COUNT (insn) += 1;
6978 /* Initialize variables for region data dependence analysis.
6979 n_bbs is the number of region blocks */
6981 __inline static void
6982 init_rgn_data_dependences (n_bbs)
6987 /* variables for which one copy exists for each block */
6988 bzero ((char *) bb_pending_read_insns, n_bbs * sizeof (rtx));
6989 bzero ((char *) bb_pending_read_mems, n_bbs * sizeof (rtx));
6990 bzero ((char *) bb_pending_write_insns, n_bbs * sizeof (rtx));
6991 bzero ((char *) bb_pending_write_mems, n_bbs * sizeof (rtx));
6992 bzero ((char *) bb_pending_lists_length, n_bbs * sizeof (rtx));
6993 bzero ((char *) bb_last_pending_memory_flush, n_bbs * sizeof (rtx));
6994 bzero ((char *) bb_last_function_call, n_bbs * sizeof (rtx));
6995 bzero ((char *) bb_sched_before_next_call, n_bbs * sizeof (rtx));
6997 /* Create an insn here so that we can hang dependencies off of it later. */
6998 for (bb = 0; bb < n_bbs; bb++)
7000 bb_sched_before_next_call[bb] =
7001 gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
7002 NULL_RTX, 0, NULL_RTX, NULL_RTX);
7003 LOG_LINKS (bb_sched_before_next_call[bb]) = 0;
7007 /* Add dependences so that branches are scheduled to run last in their block */
7010 add_branch_dependences (head, tail)
7016 /* For all branches, calls, uses, and cc0 setters, force them to remain
7017 in order at the end of the block by adding dependencies and giving
7018 the last a high priority. There may be notes present, and prev_head
7021 Branches must obviously remain at the end. Calls should remain at the
7022 end since moving them results in worse register allocation. Uses remain
7023 at the end to ensure proper register allocation. cc0 setters remaim
7024 at the end because they can't be moved away from their cc0 user. */
7027 while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
7028 || (GET_CODE (insn) == INSN
7029 && (GET_CODE (PATTERN (insn)) == USE
7031 || sets_cc0_p (PATTERN (insn))
7034 || GET_CODE (insn) == NOTE)
7036 if (GET_CODE (insn) != NOTE)
7039 && !find_insn_list (insn, LOG_LINKS (last)))
7041 add_dependence (last, insn, REG_DEP_ANTI);
7042 INSN_REF_COUNT (insn)++;
7045 CANT_MOVE (insn) = 1;
7048 /* Skip over insns that are part of a group.
7049 Make each insn explicitly depend on the previous insn.
7050 This ensures that only the group header will ever enter
7051 the ready queue (and, when scheduled, will automatically
7052 schedule the SCHED_GROUP_P block). */
7053 while (SCHED_GROUP_P (insn))
7055 rtx temp = prev_nonnote_insn (insn);
7056 add_dependence (insn, temp, REG_DEP_ANTI);
7061 /* Don't overrun the bounds of the basic block. */
7065 insn = PREV_INSN (insn);
7068 /* make sure these insns are scheduled last in their block */
7071 while (insn != head)
7073 insn = prev_nonnote_insn (insn);
7075 if (INSN_REF_COUNT (insn) != 0)
7078 if (!find_insn_list (last, LOG_LINKS (insn)))
7079 add_dependence (last, insn, REG_DEP_ANTI);
7080 INSN_REF_COUNT (insn) = 1;
7082 /* Skip over insns that are part of a group. */
7083 while (SCHED_GROUP_P (insn))
7084 insn = prev_nonnote_insn (insn);
7088 /* Compute bacward dependences inside BB. In a multiple blocks region:
7089 (1) a bb is analyzed after its predecessors, and (2) the lists in
7090 effect at the end of bb (after analyzing for bb) are inherited by
7093 Specifically for reg-reg data dependences, the block insns are
7094 scanned by sched_analyze () top-to-bottom. Two lists are
7095 naintained by sched_analyze (): reg_last_defs[] for register DEFs,
7096 and reg_last_uses[] for register USEs.
7098 When analysis is completed for bb, we update for its successors:
7099 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7100 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7102 The mechanism for computing mem-mem data dependence is very
7103 similar, and the result is interblock dependences in the region. */
7106 compute_block_backward_dependences (bb)
7112 int max_reg = max_reg_num ();
7114 b = BB_TO_BLOCK (bb);
7116 if (current_nr_blocks == 1)
7118 reg_last_uses = (rtx *) alloca (max_reg * sizeof (rtx));
7119 reg_last_sets = (rtx *) alloca (max_reg * sizeof (rtx));
7121 bzero ((char *) reg_last_uses, max_reg * sizeof (rtx));
7122 bzero ((char *) reg_last_sets, max_reg * sizeof (rtx));
7124 pending_read_insns = 0;
7125 pending_read_mems = 0;
7126 pending_write_insns = 0;
7127 pending_write_mems = 0;
7128 pending_lists_length = 0;
7129 last_function_call = 0;
7130 last_pending_memory_flush = 0;
7131 sched_before_next_call
7132 = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
7133 NULL_RTX, 0, NULL_RTX, NULL_RTX);
7134 LOG_LINKS (sched_before_next_call) = 0;
7138 reg_last_uses = bb_reg_last_uses[bb];
7139 reg_last_sets = bb_reg_last_sets[bb];
7141 pending_read_insns = bb_pending_read_insns[bb];
7142 pending_read_mems = bb_pending_read_mems[bb];
7143 pending_write_insns = bb_pending_write_insns[bb];
7144 pending_write_mems = bb_pending_write_mems[bb];
7145 pending_lists_length = bb_pending_lists_length[bb];
7146 last_function_call = bb_last_function_call[bb];
7147 last_pending_memory_flush = bb_last_pending_memory_flush[bb];
7149 sched_before_next_call = bb_sched_before_next_call[bb];
7152 /* do the analysis for this block */
7153 get_block_head_tail (bb, &head, &tail);
7154 sched_analyze (head, tail);
7155 add_branch_dependences (head, tail);
7157 if (current_nr_blocks > 1)
7160 int b_succ, bb_succ;
7162 rtx link_insn, link_mem;
7165 /* these lists should point to the right place, for correct freeing later. */
7166 bb_pending_read_insns[bb] = pending_read_insns;
7167 bb_pending_read_mems[bb] = pending_read_mems;
7168 bb_pending_write_insns[bb] = pending_write_insns;
7169 bb_pending_write_mems[bb] = pending_write_mems;
7171 /* bb's structures are inherited by it's successors */
7172 first_edge = e = OUT_EDGES (b);
7176 b_succ = TO_BLOCK (e);
7177 bb_succ = BLOCK_TO_BB (b_succ);
7179 /* only bbs "below" bb, in the same region, are interesting */
7180 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
7187 for (reg = 0; reg < max_reg; reg++)
7190 /* reg-last-uses lists are inherited by bb_succ */
7191 for (u = reg_last_uses[reg]; u; u = XEXP (u, 1))
7193 if (find_insn_list (XEXP (u, 0), (bb_reg_last_uses[bb_succ])[reg]))
7196 (bb_reg_last_uses[bb_succ])[reg]
7197 = alloc_INSN_LIST (XEXP (u, 0),
7198 (bb_reg_last_uses[bb_succ])[reg]);
7201 /* reg-last-defs lists are inherited by bb_succ */
7202 for (u = reg_last_sets[reg]; u; u = XEXP (u, 1))
7204 if (find_insn_list (XEXP (u, 0), (bb_reg_last_sets[bb_succ])[reg]))
7207 (bb_reg_last_sets[bb_succ])[reg]
7208 = alloc_INSN_LIST (XEXP (u, 0),
7209 (bb_reg_last_sets[bb_succ])[reg]);
7213 /* mem read/write lists are inherited by bb_succ */
7214 link_insn = pending_read_insns;
7215 link_mem = pending_read_mems;
7218 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7219 bb_pending_read_insns[bb_succ],
7220 bb_pending_read_mems[bb_succ])))
7221 add_insn_mem_dependence (&bb_pending_read_insns[bb_succ],
7222 &bb_pending_read_mems[bb_succ],
7223 XEXP (link_insn, 0), XEXP (link_mem, 0));
7224 link_insn = XEXP (link_insn, 1);
7225 link_mem = XEXP (link_mem, 1);
7228 link_insn = pending_write_insns;
7229 link_mem = pending_write_mems;
7232 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7233 bb_pending_write_insns[bb_succ],
7234 bb_pending_write_mems[bb_succ])))
7235 add_insn_mem_dependence (&bb_pending_write_insns[bb_succ],
7236 &bb_pending_write_mems[bb_succ],
7237 XEXP (link_insn, 0), XEXP (link_mem, 0));
7239 link_insn = XEXP (link_insn, 1);
7240 link_mem = XEXP (link_mem, 1);
7243 /* last_function_call is inherited by bb_succ */
7244 for (u = last_function_call; u; u = XEXP (u, 1))
7246 if (find_insn_list (XEXP (u, 0), bb_last_function_call[bb_succ]))
7249 bb_last_function_call[bb_succ]
7250 = alloc_INSN_LIST (XEXP (u, 0),
7251 bb_last_function_call[bb_succ]);
7254 /* last_pending_memory_flush is inherited by bb_succ */
7255 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
7257 if (find_insn_list (XEXP (u, 0), bb_last_pending_memory_flush[bb_succ]))
7260 bb_last_pending_memory_flush[bb_succ]
7261 = alloc_INSN_LIST (XEXP (u, 0),
7262 bb_last_pending_memory_flush[bb_succ]);
7265 /* sched_before_next_call is inherited by bb_succ */
7266 x = LOG_LINKS (sched_before_next_call);
7267 for (; x; x = XEXP (x, 1))
7268 add_dependence (bb_sched_before_next_call[bb_succ],
7269 XEXP (x, 0), REG_DEP_ANTI);
7273 while (e != first_edge);
7276 /* Free up the INSN_LISTs
7278 Note this loop is executed max_reg * nr_regions times. It's first
7279 implementation accounted for over 90% of the calls to free_list.
7280 The list was empty for the vast majority of those calls. On the PA,
7281 not calling free_list in those cases improves -O2 compile times by
7283 for (b = 0; b < max_reg; ++b)
7285 if (reg_last_sets[b])
7286 free_list (®_last_sets[b], &unused_insn_list);
7287 if (reg_last_uses[b])
7288 free_list (®_last_uses[b], &unused_insn_list);
7291 /* Assert that we won't need bb_reg_last_* for this block anymore. */
7292 if (current_nr_blocks > 1)
7294 bb_reg_last_uses[bb] = (rtx *) NULL_RTX;
7295 bb_reg_last_sets[bb] = (rtx *) NULL_RTX;
7299 /* Print dependences for debugging, callable from debugger */
7302 debug_dependencies ()
7306 fprintf (dump, ";; --------------- forward dependences: ------------ \n");
7307 for (bb = 0; bb < current_nr_blocks; bb++)
7315 get_block_head_tail (bb, &head, &tail);
7316 next_tail = NEXT_INSN (tail);
7317 fprintf (dump, "\n;; --- Region Dependences --- b %d bb %d \n",
7318 BB_TO_BLOCK (bb), bb);
7320 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7321 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7322 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7323 "----", "----", "--", "---", "----", "----", "--------", "-----");
7324 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
7329 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7332 fprintf (dump, ";; %6d ", INSN_UID (insn));
7333 if (GET_CODE (insn) == NOTE)
7335 n = NOTE_LINE_NUMBER (insn);
7337 fprintf (dump, "%s\n", GET_NOTE_INSN_NAME (n));
7339 fprintf (dump, "line %d, file %s\n", n,
7340 NOTE_SOURCE_FILE (insn));
7343 fprintf (dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
7347 unit = insn_unit (insn);
7349 || function_units[unit].blockage_range_function == 0) ? 0 :
7350 function_units[unit].blockage_range_function (insn);
7352 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7353 (SCHED_GROUP_P (insn) ? "+" : " "),
7357 INSN_DEP_COUNT (insn),
7358 INSN_PRIORITY (insn),
7359 insn_cost (insn, 0, 0),
7360 (int) MIN_BLOCKAGE_COST (range),
7361 (int) MAX_BLOCKAGE_COST (range));
7362 insn_print_units (insn);
7363 fprintf (dump, "\t: ");
7364 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
7365 fprintf (dump, "%d ", INSN_UID (XEXP (link, 0)));
7366 fprintf (dump, "\n");
7370 fprintf (dump, "\n");
7373 /* Set_priorities: compute priority of each insn in the block */
7386 get_block_head_tail (bb, &head, &tail);
7387 prev_head = PREV_INSN (head);
7390 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
7394 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
7397 if (GET_CODE (insn) == NOTE)
7400 if (!(SCHED_GROUP_P (insn)))
7402 (void) priority (insn);
7408 /* Make each element of VECTOR point at an rtx-vector,
7409 taking the space for all those rtx-vectors from SPACE.
7410 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7411 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7412 (this is the same as init_regset_vector () in flow.c) */
7415 init_rtx_vector (vector, space, nelts, bytes_per_elt)
7422 register rtx *p = space;
7424 for (i = 0; i < nelts; i++)
7427 p += bytes_per_elt / sizeof (*p);
7431 /* Schedule a region. A region is either an inner loop, a loop-free
7432 subroutine, or a single basic block. Each bb in the region is
7433 scheduled after its flow predecessors. */
7436 schedule_region (rgn)
7440 int rgn_n_insns = 0;
7441 int sched_rgn_n_insns = 0;
7443 /* set variables for the current region */
7444 current_nr_blocks = RGN_NR_BLOCKS (rgn);
7445 current_blocks = RGN_BLOCKS (rgn);
7447 reg_pending_sets = ALLOCA_REG_SET ();
7448 reg_pending_sets_all = 0;
7450 /* initializations for region data dependence analyisis */
7451 if (current_nr_blocks > 1)
7454 int maxreg = max_reg_num ();
7456 bb_reg_last_uses = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7457 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7458 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7459 init_rtx_vector (bb_reg_last_uses, space, current_nr_blocks, maxreg * sizeof (rtx *));
7461 bb_reg_last_sets = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7462 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7463 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7464 init_rtx_vector (bb_reg_last_sets, space, current_nr_blocks, maxreg * sizeof (rtx *));
7466 bb_pending_read_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7467 bb_pending_read_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7468 bb_pending_write_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7469 bb_pending_write_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7470 bb_pending_lists_length = (int *) alloca (current_nr_blocks * sizeof (int));
7471 bb_last_pending_memory_flush = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7472 bb_last_function_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7473 bb_sched_before_next_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7475 init_rgn_data_dependences (current_nr_blocks);
7478 /* compute LOG_LINKS */
7479 for (bb = 0; bb < current_nr_blocks; bb++)
7480 compute_block_backward_dependences (bb);
7482 /* compute INSN_DEPEND */
7483 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7484 compute_block_forward_dependences (bb);
7486 /* Delete line notes, compute live-regs at block end, and set priorities. */
7488 for (bb = 0; bb < current_nr_blocks; bb++)
7490 if (reload_completed == 0)
7491 find_pre_sched_live (bb);
7493 if (write_symbols != NO_DEBUG)
7495 save_line_notes (bb);
7499 rgn_n_insns += set_priorities (bb);
7502 /* compute interblock info: probabilities, split-edges, dominators, etc. */
7503 if (current_nr_blocks > 1)
7507 prob = (float *) alloca ((current_nr_blocks) * sizeof (float));
7509 bbset_size = current_nr_blocks / HOST_BITS_PER_WIDE_INT + 1;
7510 dom = (bbset *) alloca (current_nr_blocks * sizeof (bbset));
7511 for (i = 0; i < current_nr_blocks; i++)
7513 dom[i] = (bbset) alloca (bbset_size * sizeof (HOST_WIDE_INT));
7514 bzero ((char *) dom[i], bbset_size * sizeof (HOST_WIDE_INT));
7519 edge_to_bit = (int *) alloca (nr_edges * sizeof (int));
7520 for (i = 1; i < nr_edges; i++)
7521 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
7522 EDGE_TO_BIT (i) = rgn_nr_edges++;
7523 rgn_edges = (int *) alloca (rgn_nr_edges * sizeof (int));
7526 for (i = 1; i < nr_edges; i++)
7527 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
7528 rgn_edges[rgn_nr_edges++] = i;
7531 edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
7532 pot_split = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7533 ancestor_edges = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7534 for (i = 0; i < current_nr_blocks; i++)
7537 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7538 bzero ((char *) pot_split[i],
7539 edgeset_size * sizeof (HOST_WIDE_INT));
7541 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7542 bzero ((char *) ancestor_edges[i],
7543 edgeset_size * sizeof (HOST_WIDE_INT));
7546 /* compute probabilities, dominators, split_edges */
7547 for (bb = 0; bb < current_nr_blocks; bb++)
7548 compute_dom_prob_ps (bb);
7551 /* now we can schedule all blocks */
7552 for (bb = 0; bb < current_nr_blocks; bb++)
7554 sched_rgn_n_insns += schedule_block (bb, rgn_n_insns);
7561 /* sanity check: verify that all region insns were scheduled */
7562 if (sched_rgn_n_insns != rgn_n_insns)
7565 /* update register life and usage information */
7566 if (reload_completed == 0)
7568 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7569 find_post_sched_live (bb);
7571 if (current_nr_blocks <= 1)
7572 /* Sanity check. There should be no REG_DEAD notes leftover at the end.
7573 In practice, this can occur as the result of bugs in flow, combine.c,
7574 and/or sched.c. The values of the REG_DEAD notes remaining are
7575 meaningless, because dead_notes is just used as a free list. */
7576 if (dead_notes != 0)
7580 /* restore line notes. */
7581 if (write_symbols != NO_DEBUG)
7583 for (bb = 0; bb < current_nr_blocks; bb++)
7584 restore_line_notes (bb);
7587 /* Done with this region */
7588 free_pending_lists ();
7590 FREE_REG_SET (reg_pending_sets);
7593 /* Subroutine of split_hard_reg_notes. Searches X for any reference to
7594 REGNO, returning the rtx of the reference found if any. Otherwise,
7598 regno_use_in (regno, x)
7606 if (GET_CODE (x) == REG && REGNO (x) == regno)
7609 fmt = GET_RTX_FORMAT (GET_CODE (x));
7610 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
7614 if ((tem = regno_use_in (regno, XEXP (x, i))))
7617 else if (fmt[i] == 'E')
7618 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
7619 if ((tem = regno_use_in (regno, XVECEXP (x, i, j))))
7626 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
7627 needed for the hard register mentioned in the note. This can happen
7628 if the reference to the hard register in the original insn was split into
7629 several smaller hard register references in the split insns. */
7632 split_hard_reg_notes (note, first, last)
7633 rtx note, first, last;
7635 rtx reg, temp, link;
7636 int n_regs, i, new_reg;
7639 /* Assume that this is a REG_DEAD note. */
7640 if (REG_NOTE_KIND (note) != REG_DEAD)
7643 reg = XEXP (note, 0);
7645 n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
7647 for (i = 0; i < n_regs; i++)
7649 new_reg = REGNO (reg) + i;
7651 /* Check for references to new_reg in the split insns. */
7652 for (insn = last;; insn = PREV_INSN (insn))
7654 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7655 && (temp = regno_use_in (new_reg, PATTERN (insn))))
7657 /* Create a new reg dead note ere. */
7658 link = alloc_EXPR_LIST (REG_DEAD, temp, REG_NOTES (insn));
7659 REG_NOTES (insn) = link;
7661 /* If killed multiple registers here, then add in the excess. */
7662 i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
7666 /* It isn't mentioned anywhere, so no new reg note is needed for
7674 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
7675 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
7678 new_insn_dead_notes (pat, insn, last, orig_insn)
7679 rtx pat, insn, last, orig_insn;
7683 /* PAT is either a CLOBBER or a SET here. */
7684 dest = XEXP (pat, 0);
7686 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
7687 || GET_CODE (dest) == STRICT_LOW_PART
7688 || GET_CODE (dest) == SIGN_EXTRACT)
7689 dest = XEXP (dest, 0);
7691 if (GET_CODE (dest) == REG)
7693 /* If the original insn already used this register, we may not add new
7694 notes for it. One example for a split that needs this test is
7695 when a multi-word memory access with register-indirect addressing
7696 is split into multiple memory accesses with auto-increment and
7697 one adjusting add instruction for the address register. */
7698 if (reg_referenced_p (dest, PATTERN (orig_insn)))
7700 for (tem = last; tem != insn; tem = PREV_INSN (tem))
7702 if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
7703 && reg_overlap_mentioned_p (dest, PATTERN (tem))
7704 && (set = single_set (tem)))
7706 rtx tem_dest = SET_DEST (set);
7708 while (GET_CODE (tem_dest) == ZERO_EXTRACT
7709 || GET_CODE (tem_dest) == SUBREG
7710 || GET_CODE (tem_dest) == STRICT_LOW_PART
7711 || GET_CODE (tem_dest) == SIGN_EXTRACT)
7712 tem_dest = XEXP (tem_dest, 0);
7714 if (!rtx_equal_p (tem_dest, dest))
7716 /* Use the same scheme as combine.c, don't put both REG_DEAD
7717 and REG_UNUSED notes on the same insn. */
7718 if (!find_regno_note (tem, REG_UNUSED, REGNO (dest))
7719 && !find_regno_note (tem, REG_DEAD, REGNO (dest)))
7721 rtx note = alloc_EXPR_LIST (REG_DEAD, dest,
7723 REG_NOTES (tem) = note;
7725 /* The reg only dies in one insn, the last one that uses
7729 else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
7730 /* We found an instruction that both uses the register,
7731 and sets it, so no new REG_NOTE is needed for this set. */
7735 /* If this is a set, it must die somewhere, unless it is the dest of
7736 the original insn, and hence is live after the original insn. Abort
7737 if it isn't supposed to be live after the original insn.
7739 If this is a clobber, then just add a REG_UNUSED note. */
7742 int live_after_orig_insn = 0;
7743 rtx pattern = PATTERN (orig_insn);
7746 if (GET_CODE (pat) == CLOBBER)
7748 rtx note = alloc_EXPR_LIST (REG_UNUSED, dest, REG_NOTES (insn));
7749 REG_NOTES (insn) = note;
7753 /* The original insn could have multiple sets, so search the
7754 insn for all sets. */
7755 if (GET_CODE (pattern) == SET)
7757 if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
7758 live_after_orig_insn = 1;
7760 else if (GET_CODE (pattern) == PARALLEL)
7762 for (i = 0; i < XVECLEN (pattern, 0); i++)
7763 if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
7764 && reg_overlap_mentioned_p (dest,
7765 SET_DEST (XVECEXP (pattern,
7767 live_after_orig_insn = 1;
7770 if (!live_after_orig_insn)
7776 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
7777 registers modified by X. INC is -1 if the containing insn is being deleted,
7778 and is 1 if the containing insn is a newly generated insn. */
7781 update_n_sets (x, inc)
7785 rtx dest = SET_DEST (x);
7787 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
7788 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
7789 dest = SUBREG_REG (dest);
7791 if (GET_CODE (dest) == REG)
7793 int regno = REGNO (dest);
7795 if (regno < FIRST_PSEUDO_REGISTER)
7798 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
7800 for (i = regno; i < endregno; i++)
7801 REG_N_SETS (i) += inc;
7804 REG_N_SETS (regno) += inc;
7808 /* Updates all flow-analysis related quantities (including REG_NOTES) for
7809 the insns from FIRST to LAST inclusive that were created by splitting
7810 ORIG_INSN. NOTES are the original REG_NOTES. */
7813 update_flow_info (notes, first, last, orig_insn)
7820 rtx orig_dest, temp;
7823 /* Get and save the destination set by the original insn. */
7825 orig_dest = single_set (orig_insn);
7827 orig_dest = SET_DEST (orig_dest);
7829 /* Move REG_NOTES from the original insn to where they now belong. */
7831 for (note = notes; note; note = next)
7833 next = XEXP (note, 1);
7834 switch (REG_NOTE_KIND (note))
7838 /* Move these notes from the original insn to the last new insn where
7839 the register is now set. */
7841 for (insn = last;; insn = PREV_INSN (insn))
7843 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7844 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
7846 /* If this note refers to a multiple word hard register, it
7847 may have been split into several smaller hard register
7848 references, so handle it specially. */
7849 temp = XEXP (note, 0);
7850 if (REG_NOTE_KIND (note) == REG_DEAD
7851 && GET_CODE (temp) == REG
7852 && REGNO (temp) < FIRST_PSEUDO_REGISTER
7853 && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
7854 split_hard_reg_notes (note, first, last);
7857 XEXP (note, 1) = REG_NOTES (insn);
7858 REG_NOTES (insn) = note;
7861 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
7863 /* ??? This won't handle multiple word registers correctly,
7864 but should be good enough for now. */
7865 if (REG_NOTE_KIND (note) == REG_UNUSED
7866 && GET_CODE (XEXP (note, 0)) != SCRATCH
7867 && !dead_or_set_p (insn, XEXP (note, 0)))
7868 PUT_REG_NOTE_KIND (note, REG_DEAD);
7870 /* The reg only dies in one insn, the last one that uses
7874 /* It must die somewhere, fail it we couldn't find where it died.
7876 If this is a REG_UNUSED note, then it must be a temporary
7877 register that was not needed by this instantiation of the
7878 pattern, so we can safely ignore it. */
7881 /* After reload, REG_DEAD notes come sometimes an
7882 instruction after the register actually dies. */
7883 if (reload_completed && REG_NOTE_KIND (note) == REG_DEAD)
7885 XEXP (note, 1) = REG_NOTES (insn);
7886 REG_NOTES (insn) = note;
7890 if (REG_NOTE_KIND (note) != REG_UNUSED)
7899 /* If the insn that set the register to 0 was deleted, this
7900 note cannot be relied on any longer. The destination might
7901 even have been moved to memory.
7902 This was observed for SH4 with execute/920501-6.c compilation,
7903 -O2 -fomit-frame-pointer -finline-functions . */
7904 if (GET_CODE (XEXP (note, 0)) == NOTE
7905 || INSN_DELETED_P (XEXP (note, 0)))
7907 /* This note applies to the dest of the original insn. Find the
7908 first new insn that now has the same dest, and move the note
7914 for (insn = first;; insn = NEXT_INSN (insn))
7916 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7917 && (temp = single_set (insn))
7918 && rtx_equal_p (SET_DEST (temp), orig_dest))
7920 XEXP (note, 1) = REG_NOTES (insn);
7921 REG_NOTES (insn) = note;
7922 /* The reg is only zero before one insn, the first that
7926 /* If this note refers to a multiple word hard
7927 register, it may have been split into several smaller
7928 hard register references. We could split the notes,
7929 but simply dropping them is good enough. */
7930 if (GET_CODE (orig_dest) == REG
7931 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
7932 && HARD_REGNO_NREGS (REGNO (orig_dest),
7933 GET_MODE (orig_dest)) > 1)
7935 /* It must be set somewhere, fail if we couldn't find where it
7944 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
7945 set is meaningless. Just drop the note. */
7949 case REG_NO_CONFLICT:
7950 /* These notes apply to the dest of the original insn. Find the last
7951 new insn that now has the same dest, and move the note there. */
7956 for (insn = last;; insn = PREV_INSN (insn))
7958 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7959 && (temp = single_set (insn))
7960 && rtx_equal_p (SET_DEST (temp), orig_dest))
7962 XEXP (note, 1) = REG_NOTES (insn);
7963 REG_NOTES (insn) = note;
7964 /* Only put this note on one of the new insns. */
7968 /* The original dest must still be set someplace. Abort if we
7969 couldn't find it. */
7972 /* However, if this note refers to a multiple word hard
7973 register, it may have been split into several smaller
7974 hard register references. We could split the notes,
7975 but simply dropping them is good enough. */
7976 if (GET_CODE (orig_dest) == REG
7977 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
7978 && HARD_REGNO_NREGS (REGNO (orig_dest),
7979 GET_MODE (orig_dest)) > 1)
7981 /* Likewise for multi-word memory references. */
7982 if (GET_CODE (orig_dest) == MEM
7983 && SIZE_FOR_MODE (orig_dest) > MOVE_MAX)
7991 /* Move a REG_LIBCALL note to the first insn created, and update
7992 the corresponding REG_RETVAL note. */
7993 XEXP (note, 1) = REG_NOTES (first);
7994 REG_NOTES (first) = note;
7996 insn = XEXP (note, 0);
7997 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
7999 XEXP (note, 0) = first;
8002 case REG_EXEC_COUNT:
8003 /* Move a REG_EXEC_COUNT note to the first insn created. */
8004 XEXP (note, 1) = REG_NOTES (first);
8005 REG_NOTES (first) = note;
8009 /* Move a REG_RETVAL note to the last insn created, and update
8010 the corresponding REG_LIBCALL note. */
8011 XEXP (note, 1) = REG_NOTES (last);
8012 REG_NOTES (last) = note;
8014 insn = XEXP (note, 0);
8015 note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
8017 XEXP (note, 0) = last;
8022 /* This should be moved to whichever instruction is a JUMP_INSN. */
8024 for (insn = last;; insn = PREV_INSN (insn))
8026 if (GET_CODE (insn) == JUMP_INSN)
8028 XEXP (note, 1) = REG_NOTES (insn);
8029 REG_NOTES (insn) = note;
8030 /* Only put this note on one of the new insns. */
8033 /* Fail if we couldn't find a JUMP_INSN. */
8040 /* reload sometimes leaves obsolete REG_INC notes around. */
8041 if (reload_completed)
8043 /* This should be moved to whichever instruction now has the
8044 increment operation. */
8048 /* Should be moved to the new insn(s) which use the label. */
8049 for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
8050 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8051 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
8053 REG_NOTES (insn) = alloc_EXPR_LIST (REG_LABEL,
8061 /* These two notes will never appear until after reorg, so we don't
8062 have to handle them here. */
8068 /* Each new insn created, except the last, has a new set. If the destination
8069 is a register, then this reg is now live across several insns, whereas
8070 previously the dest reg was born and died within the same insn. To
8071 reflect this, we now need a REG_DEAD note on the insn where this
8074 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
8076 for (insn = first; insn != last; insn = NEXT_INSN (insn))
8081 pat = PATTERN (insn);
8082 if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
8083 new_insn_dead_notes (pat, insn, last, orig_insn);
8084 else if (GET_CODE (pat) == PARALLEL)
8086 for (i = 0; i < XVECLEN (pat, 0); i++)
8087 if (GET_CODE (XVECEXP (pat, 0, i)) == SET
8088 || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
8089 new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
8093 /* If any insn, except the last, uses the register set by the last insn,
8094 then we need a new REG_DEAD note on that insn. In this case, there
8095 would not have been a REG_DEAD note for this register in the original
8096 insn because it was used and set within one insn. */
8098 set = single_set (last);
8101 rtx dest = SET_DEST (set);
8103 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
8104 || GET_CODE (dest) == STRICT_LOW_PART
8105 || GET_CODE (dest) == SIGN_EXTRACT)
8106 dest = XEXP (dest, 0);
8108 if (GET_CODE (dest) == REG
8109 /* Global registers are always live, so the code below does not
8111 && (REGNO (dest) >= FIRST_PSEUDO_REGISTER
8112 || ! global_regs[REGNO (dest)]))
8114 rtx stop_insn = PREV_INSN (first);
8116 /* If the last insn uses the register that it is setting, then
8117 we don't want to put a REG_DEAD note there. Search backwards
8118 to find the first insn that sets but does not use DEST. */
8121 if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
8123 for (insn = PREV_INSN (insn); insn != first;
8124 insn = PREV_INSN (insn))
8126 if ((set = single_set (insn))
8127 && reg_mentioned_p (dest, SET_DEST (set))
8128 && ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
8133 /* Now find the first insn that uses but does not set DEST. */
8135 for (insn = PREV_INSN (insn); insn != stop_insn;
8136 insn = PREV_INSN (insn))
8138 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8139 && reg_mentioned_p (dest, PATTERN (insn))
8140 && (set = single_set (insn)))
8142 rtx insn_dest = SET_DEST (set);
8144 while (GET_CODE (insn_dest) == ZERO_EXTRACT
8145 || GET_CODE (insn_dest) == SUBREG
8146 || GET_CODE (insn_dest) == STRICT_LOW_PART
8147 || GET_CODE (insn_dest) == SIGN_EXTRACT)
8148 insn_dest = XEXP (insn_dest, 0);
8150 if (insn_dest != dest)
8152 note = alloc_EXPR_LIST (REG_DEAD, dest, REG_NOTES (insn));
8153 REG_NOTES (insn) = note;
8154 /* The reg only dies in one insn, the last one
8163 /* If the original dest is modifying a multiple register target, and the
8164 original instruction was split such that the original dest is now set
8165 by two or more SUBREG sets, then the split insns no longer kill the
8166 destination of the original insn.
8168 In this case, if there exists an instruction in the same basic block,
8169 before the split insn, which uses the original dest, and this use is
8170 killed by the original insn, then we must remove the REG_DEAD note on
8171 this insn, because it is now superfluous.
8173 This does not apply when a hard register gets split, because the code
8174 knows how to handle overlapping hard registers properly. */
8175 if (orig_dest && GET_CODE (orig_dest) == REG)
8177 int found_orig_dest = 0;
8178 int found_split_dest = 0;
8180 for (insn = first;; insn = NEXT_INSN (insn))
8185 /* I'm not sure if this can happen, but let's be safe. */
8186 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
8189 pat = PATTERN (insn);
8190 i = GET_CODE (pat) == PARALLEL ? XVECLEN (pat, 0) : 0;
8195 if (GET_CODE (set) == SET)
8197 if (GET_CODE (SET_DEST (set)) == REG
8198 && REGNO (SET_DEST (set)) == REGNO (orig_dest))
8200 found_orig_dest = 1;
8203 else if (GET_CODE (SET_DEST (set)) == SUBREG
8204 && SUBREG_REG (SET_DEST (set)) == orig_dest)
8206 found_split_dest = 1;
8212 set = XVECEXP (pat, 0, i);
8219 if (found_split_dest)
8221 /* Search backwards from FIRST, looking for the first insn that uses
8222 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
8223 If we find an insn, and it has a REG_DEAD note, then delete the
8226 for (insn = first; insn; insn = PREV_INSN (insn))
8228 if (GET_CODE (insn) == CODE_LABEL
8229 || GET_CODE (insn) == JUMP_INSN)
8231 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8232 && reg_mentioned_p (orig_dest, insn))
8234 note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
8236 remove_note (insn, note);
8240 else if (!found_orig_dest)
8242 /* This should never happen. */
8247 /* Update reg_n_sets. This is necessary to prevent local alloc from
8248 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
8249 a reg from set once to set multiple times. */
8252 rtx x = PATTERN (orig_insn);
8253 RTX_CODE code = GET_CODE (x);
8255 if (code == SET || code == CLOBBER)
8256 update_n_sets (x, -1);
8257 else if (code == PARALLEL)
8260 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8262 code = GET_CODE (XVECEXP (x, 0, i));
8263 if (code == SET || code == CLOBBER)
8264 update_n_sets (XVECEXP (x, 0, i), -1);
8268 for (insn = first;; insn = NEXT_INSN (insn))
8271 code = GET_CODE (x);
8273 if (code == SET || code == CLOBBER)
8274 update_n_sets (x, 1);
8275 else if (code == PARALLEL)
8278 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8280 code = GET_CODE (XVECEXP (x, 0, i));
8281 if (code == SET || code == CLOBBER)
8282 update_n_sets (XVECEXP (x, 0, i), 1);
8292 /* Do the splitting of insns in the block b. */
8295 split_block_insns (b)
8300 for (insn = basic_block_head[b];; insn = next)
8302 rtx set, last, first, notes;
8304 /* Can't use `next_real_insn' because that
8305 might go across CODE_LABELS and short-out basic blocks. */
8306 next = NEXT_INSN (insn);
8307 if (GET_CODE (insn) != INSN)
8309 if (insn == basic_block_end[b])
8315 /* Don't split no-op move insns. These should silently disappear
8316 later in final. Splitting such insns would break the code
8317 that handles REG_NO_CONFLICT blocks. */
8318 set = single_set (insn);
8319 if (set && rtx_equal_p (SET_SRC (set), SET_DEST (set)))
8321 if (insn == basic_block_end[b])
8324 /* Nops get in the way while scheduling, so delete them now if
8325 register allocation has already been done. It is too risky
8326 to try to do this before register allocation, and there are
8327 unlikely to be very many nops then anyways. */
8328 if (reload_completed)
8330 PUT_CODE (insn, NOTE);
8331 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
8332 NOTE_SOURCE_FILE (insn) = 0;
8338 /* Split insns here to get max fine-grain parallelism. */
8339 first = PREV_INSN (insn);
8340 notes = REG_NOTES (insn);
8341 last = try_split (PATTERN (insn), insn, 1);
8344 /* try_split returns the NOTE that INSN became. */
8345 first = NEXT_INSN (first);
8346 update_flow_info (notes, first, last, insn);
8348 PUT_CODE (insn, NOTE);
8349 NOTE_SOURCE_FILE (insn) = 0;
8350 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
8351 if (insn == basic_block_head[b])
8352 basic_block_head[b] = first;
8353 if (insn == basic_block_end[b])
8355 basic_block_end[b] = last;
8360 if (insn == basic_block_end[b])
8365 /* The one entry point in this file. DUMP_FILE is the dump file for
8369 schedule_insns (dump_file)
8380 /* disable speculative loads in their presence if cc0 defined */
8382 flag_schedule_speculative_load = 0;
8385 /* Taking care of this degenerate case makes the rest of
8386 this code simpler. */
8387 if (n_basic_blocks == 0)
8390 /* set dump and sched_verbose for the desired debugging output. If no
8391 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
8392 For -fsched-verbose-N, N>=10, print everything to stderr. */
8393 sched_verbose = sched_verbose_param;
8394 if (sched_verbose_param == 0 && dump_file)
8396 dump = ((sched_verbose_param >= 10 || !dump_file) ? stderr : dump_file);
8401 /* Initialize the unused_*_lists. We can't use the ones left over from
8402 the previous function, because gcc has freed that memory. We can use
8403 the ones left over from the first sched pass in the second pass however,
8404 so only clear them on the first sched pass. The first pass is before
8405 reload if flag_schedule_insns is set, otherwise it is afterwards. */
8407 if (reload_completed == 0 || !flag_schedule_insns)
8409 unused_insn_list = 0;
8410 unused_expr_list = 0;
8413 /* initialize issue_rate */
8414 issue_rate = ISSUE_RATE;
8416 /* do the splitting first for all blocks */
8417 for (b = 0; b < n_basic_blocks; b++)
8418 split_block_insns (b);
8420 max_uid = (get_max_uid () + 1);
8422 cant_move = (char *) alloca (max_uid * sizeof (char));
8423 bzero ((char *) cant_move, max_uid * sizeof (char));
8425 fed_by_spec_load = (char *) alloca (max_uid * sizeof (char));
8426 bzero ((char *) fed_by_spec_load, max_uid * sizeof (char));
8428 is_load_insn = (char *) alloca (max_uid * sizeof (char));
8429 bzero ((char *) is_load_insn, max_uid * sizeof (char));
8431 insn_orig_block = (int *) alloca (max_uid * sizeof (int));
8432 insn_luid = (int *) alloca (max_uid * sizeof (int));
8435 for (b = 0; b < n_basic_blocks; b++)
8436 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
8438 INSN_BLOCK (insn) = b;
8439 INSN_LUID (insn) = luid++;
8441 if (insn == basic_block_end[b])
8445 /* after reload, remove inter-blocks dependences computed before reload. */
8446 if (reload_completed)
8451 for (b = 0; b < n_basic_blocks; b++)
8452 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
8456 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
8459 link = LOG_LINKS (insn);
8462 rtx x = XEXP (link, 0);
8464 if (INSN_BLOCK (x) != b)
8466 remove_dependence (insn, x);
8467 link = prev ? XEXP (prev, 1) : LOG_LINKS (insn);
8470 prev = link, link = XEXP (prev, 1);
8474 if (insn == basic_block_end[b])
8480 rgn_table = (region *) alloca ((n_basic_blocks) * sizeof (region));
8481 rgn_bb_table = (int *) alloca ((n_basic_blocks) * sizeof (int));
8482 block_to_bb = (int *) alloca ((n_basic_blocks) * sizeof (int));
8483 containing_rgn = (int *) alloca ((n_basic_blocks) * sizeof (int));
8485 /* compute regions for scheduling */
8486 if (reload_completed
8487 || n_basic_blocks == 1
8488 || !flag_schedule_interblock)
8490 find_single_block_region ();
8494 /* verify that a 'good' control flow graph can be built */
8495 if (is_cfg_nonregular ())
8497 find_single_block_region ();
8501 int_list_ptr *s_preds, *s_succs;
8502 int *num_preds, *num_succs;
8503 sbitmap *dom, *pdom;
8505 s_preds = (int_list_ptr *) alloca (n_basic_blocks
8506 * sizeof (int_list_ptr));
8507 s_succs = (int_list_ptr *) alloca (n_basic_blocks
8508 * sizeof (int_list_ptr));
8509 num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
8510 num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
8511 dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
8512 pdom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
8514 /* The scheduler runs after flow; therefore, we can't blindly call
8515 back into find_basic_blocks since doing so could invalidate the
8516 info in basic_block_live_at_start.
8518 Consider a block consisting entirely of dead stores; after life
8519 analysis it would be a block of NOTE_INSN_DELETED notes. If
8520 we call find_basic_blocks again, then the block would be removed
8521 entirely and invalidate our the register live information.
8523 We could (should?) recompute register live information. Doing
8524 so may even be beneficial. */
8526 compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
8528 /* Compute the dominators and post dominators. We don't currently use
8529 post dominators, but we should for speculative motion analysis. */
8530 compute_dominators (dom, pdom, s_preds, s_succs);
8532 /* build_control_flow will return nonzero if it detects unreachable
8533 blocks or any other irregularity with the cfg which prevents
8534 cross block scheduling. */
8535 if (build_control_flow (s_preds, s_succs, num_preds, num_succs) != 0)
8536 find_single_block_region ();
8538 find_rgns (s_preds, s_succs, num_preds, num_succs, dom);
8540 if (sched_verbose >= 3)
8543 /* For now. This will move as more and more of haifa is converted
8544 to using the cfg code in flow.c */
8551 /* Allocate data for this pass. See comments, above,
8552 for what these vectors do. */
8553 insn_priority = (int *) alloca (max_uid * sizeof (int));
8554 insn_reg_weight = (int *) alloca (max_uid * sizeof (int));
8555 insn_tick = (int *) alloca (max_uid * sizeof (int));
8556 insn_costs = (short *) alloca (max_uid * sizeof (short));
8557 insn_units = (short *) alloca (max_uid * sizeof (short));
8558 insn_blockage = (unsigned int *) alloca (max_uid * sizeof (unsigned int));
8559 insn_ref_count = (int *) alloca (max_uid * sizeof (int));
8561 /* Allocate for forward dependencies */
8562 insn_dep_count = (int *) alloca (max_uid * sizeof (int));
8563 insn_depend = (rtx *) alloca (max_uid * sizeof (rtx));
8565 if (reload_completed == 0)
8569 sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
8570 sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
8571 sched_reg_basic_block = (int *) alloca (max_regno * sizeof (int));
8572 bb_live_regs = ALLOCA_REG_SET ();
8573 bzero ((char *) sched_reg_n_calls_crossed, max_regno * sizeof (int));
8574 bzero ((char *) sched_reg_live_length, max_regno * sizeof (int));
8576 for (i = 0; i < max_regno; i++)
8577 sched_reg_basic_block[i] = REG_BLOCK_UNKNOWN;
8581 sched_reg_n_calls_crossed = 0;
8582 sched_reg_live_length = 0;
8585 init_alias_analysis ();
8587 if (write_symbols != NO_DEBUG)
8591 line_note = (rtx *) alloca (max_uid * sizeof (rtx));
8592 bzero ((char *) line_note, max_uid * sizeof (rtx));
8593 line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
8594 bzero ((char *) line_note_head, n_basic_blocks * sizeof (rtx));
8596 /* Save-line-note-head:
8597 Determine the line-number at the start of each basic block.
8598 This must be computed and saved now, because after a basic block's
8599 predecessor has been scheduled, it is impossible to accurately
8600 determine the correct line number for the first insn of the block. */
8602 for (b = 0; b < n_basic_blocks; b++)
8603 for (line = basic_block_head[b]; line; line = PREV_INSN (line))
8604 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
8606 line_note_head[b] = line;
8611 bzero ((char *) insn_priority, max_uid * sizeof (int));
8612 bzero ((char *) insn_reg_weight, max_uid * sizeof (int));
8613 bzero ((char *) insn_tick, max_uid * sizeof (int));
8614 bzero ((char *) insn_costs, max_uid * sizeof (short));
8615 bzero ((char *) insn_units, max_uid * sizeof (short));
8616 bzero ((char *) insn_blockage, max_uid * sizeof (unsigned int));
8617 bzero ((char *) insn_ref_count, max_uid * sizeof (int));
8619 /* Initialize for forward dependencies */
8620 bzero ((char *) insn_depend, max_uid * sizeof (rtx));
8621 bzero ((char *) insn_dep_count, max_uid * sizeof (int));
8623 /* Find units used in this fuction, for visualization */
8625 init_target_units ();
8627 /* ??? Add a NOTE after the last insn of the last basic block. It is not
8628 known why this is done. */
8630 insn = basic_block_end[n_basic_blocks - 1];
8631 if (NEXT_INSN (insn) == 0
8632 || (GET_CODE (insn) != NOTE
8633 && GET_CODE (insn) != CODE_LABEL
8634 /* Don't emit a NOTE if it would end up between an unconditional
8635 jump and a BARRIER. */
8636 && !(GET_CODE (insn) == JUMP_INSN
8637 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
8638 emit_note_after (NOTE_INSN_DELETED, basic_block_end[n_basic_blocks - 1]);
8640 /* Schedule every region in the subroutine */
8641 for (rgn = 0; rgn < nr_regions; rgn++)
8643 schedule_region (rgn);
8650 /* Reposition the prologue and epilogue notes in case we moved the
8651 prologue/epilogue insns. */
8652 if (reload_completed)
8653 reposition_prologue_and_epilogue_notes (get_insns ());
8655 /* delete redundant line notes. */
8656 if (write_symbols != NO_DEBUG)
8657 rm_redundant_line_notes ();
8659 /* Update information about uses of registers in the subroutine. */
8660 if (reload_completed == 0)
8661 update_reg_usage ();
8665 if (reload_completed == 0 && flag_schedule_interblock)
8667 fprintf (dump, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8675 fprintf (dump, "\n\n");
8679 FREE_REG_SET (bb_live_regs);
8698 #endif /* INSN_SCHEDULING */