1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 93-97, 1998 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to the Free
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
24 /* Instruction scheduling pass.
26 This pass implements list scheduling within basic blocks. It is
27 run twice: (1) after flow analysis, but before register allocation,
28 and (2) after register allocation.
30 The first run performs interblock scheduling, moving insns between
31 different blocks in the same "region", and the second runs only
32 basic block scheduling.
34 Interblock motions performed are useful motions and speculative
35 motions, including speculative loads. Motions requiring code
36 duplication are not supported. The identification of motion type
37 and the check for validity of speculative motions requires
38 construction and analysis of the function's control flow graph.
39 The scheduler works as follows:
41 We compute insn priorities based on data dependencies. Flow
42 analysis only creates a fraction of the data-dependencies we must
43 observe: namely, only those dependencies which the combiner can be
44 expected to use. For this pass, we must therefore create the
45 remaining dependencies we need to observe: register dependencies,
46 memory dependencies, dependencies to keep function calls in order,
47 and the dependence between a conditional branch and the setting of
48 condition codes are all dealt with here.
50 The scheduler first traverses the data flow graph, starting with
51 the last instruction, and proceeding to the first, assigning values
52 to insn_priority as it goes. This sorts the instructions
53 topologically by data dependence.
55 Once priorities have been established, we order the insns using
56 list scheduling. This works as follows: starting with a list of
57 all the ready insns, and sorted according to priority number, we
58 schedule the insn from the end of the list by placing its
59 predecessors in the list according to their priority order. We
60 consider this insn scheduled by setting the pointer to the "end" of
61 the list to point to the previous insn. When an insn has no
62 predecessors, we either queue it until sufficient time has elapsed
63 or add it to the ready list. As the instructions are scheduled or
64 when stalls are introduced, the queue advances and dumps insns into
65 the ready list. When all insns down to the lowest priority have
66 been scheduled, the critical path of the basic block has been made
67 as short as possible. The remaining insns are then scheduled in
70 Function unit conflicts are resolved during forward list scheduling
71 by tracking the time when each insn is committed to the schedule
72 and from that, the time the function units it uses must be free.
73 As insns on the ready list are considered for scheduling, those
74 that would result in a blockage of the already committed insns are
75 queued until no blockage will result.
77 The following list shows the order in which we want to break ties
78 among insns in the ready list:
80 1. choose insn with the longest path to end of bb, ties
82 2. choose insn with least contribution to register pressure,
84 3. prefer in-block upon interblock motion, ties broken by
85 4. prefer useful upon speculative motion, ties broken by
86 5. choose insn with largest control flow probability, ties
88 6. choose insn with the least dependences upon the previously
89 scheduled insn, or finally
90 7. choose insn with lowest UID.
92 Memory references complicate matters. Only if we can be certain
93 that memory references are not part of the data dependency graph
94 (via true, anti, or output dependence), can we move operations past
95 memory references. To first approximation, reads can be done
96 independently, while writes introduce dependencies. Better
97 approximations will yield fewer dependencies.
99 Before reload, an extended analysis of interblock data dependences
100 is required for interblock scheduling. This is performed in
101 compute_block_backward_dependences ().
103 Dependencies set up by memory references are treated in exactly the
104 same way as other dependencies, by using LOG_LINKS backward
105 dependences. LOG_LINKS are translated into INSN_DEPEND forward
106 dependences for the purpose of forward list scheduling.
108 Having optimized the critical path, we may have also unduly
109 extended the lifetimes of some registers. If an operation requires
110 that constants be loaded into registers, it is certainly desirable
111 to load those constants as early as necessary, but no earlier.
112 I.e., it will not do to load up a bunch of registers at the
113 beginning of a basic block only to use them at the end, if they
114 could be loaded later, since this may result in excessive register
117 Note that since branches are never in basic blocks, but only end
118 basic blocks, this pass will not move branches. But that is ok,
119 since we can use GNU's delayed branch scheduling pass to take care
122 Also note that no further optimizations based on algebraic
123 identities are performed, so this pass would be a good one to
124 perform instruction splitting, such as breaking up a multiply
125 instruction into shifts and adds where that is profitable.
127 Given the memory aliasing analysis that this pass should perform,
128 it should be possible to remove redundant stores to memory, and to
129 load values from registers instead of hitting memory.
131 Before reload, speculative insns are moved only if a 'proof' exists
132 that no exception will be caused by this, and if no live registers
133 exist that inhibit the motion (live registers constraints are not
134 represented by data dependence edges).
136 This pass must update information that subsequent passes expect to
137 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
138 reg_n_calls_crossed, and reg_live_length. Also, basic_block_head,
141 The information in the line number notes is carefully retained by
142 this pass. Notes that refer to the starting and ending of
143 exception regions are also carefully retained by this pass. All
144 other NOTE insns are grouped in their same relative order at the
145 beginning of basic blocks and regions that have been scheduled.
147 The main entry point for this pass is schedule_insns(), called for
148 each function. The work of the scheduler is organized in three
149 levels: (1) function level: insns are subject to splitting,
150 control-flow-graph is constructed, regions are computed (after
151 reload, each region is of one block), (2) region level: control
152 flow graph attributes required for interblock scheduling are
153 computed (dominators, reachability, etc.), data dependences and
154 priorities are computed, and (3) block level: insns in the block
155 are actually scheduled. */
160 #include "basic-block.h"
162 #include "hard-reg-set.h"
164 #include "insn-config.h"
165 #include "insn-attr.h"
168 extern char *reg_known_equiv_p;
169 extern rtx *reg_known_value;
171 #ifdef INSN_SCHEDULING
173 /* target_units bitmask has 1 for each unit in the cpu. It should be
174 possible to compute this variable from the machine description.
175 But currently it is computed by examinning the insn list. Since
176 this is only needed for visualization, it seems an acceptable
177 solution. (For understanding the mapping of bits to units, see
178 definition of function_units[] in "insn-attrtab.c") */
180 static int target_units = 0;
182 /* issue_rate is the number of insns that can be scheduled in the same
183 machine cycle. It can be defined in the config/mach/mach.h file,
184 otherwise we set it to 1. */
186 static int issue_rate;
192 /* sched-verbose controls the amount of debugging output the
193 scheduler prints. It is controlled by -fsched-verbose-N:
194 N>0 and no -DSR : the output is directed to stderr.
195 N>=10 will direct the printouts to stderr (regardless of -dSR).
197 N=2: bb's probabilities, detailed ready list info, unit/insn info.
198 N=3: rtl at abort point, control-flow, regions info.
199 N=5: dependences info. */
201 #define MAX_RGN_BLOCKS 10
202 #define MAX_RGN_INSNS 100
204 static int sched_verbose_param = 0;
205 static int sched_verbose = 0;
207 /* nr_inter/spec counts interblock/speculative motion for the function */
208 static int nr_inter, nr_spec;
211 /* debugging file. all printouts are sent to dump, which is always set,
212 either to stderr, or to the dump listing file (-dRS). */
213 static FILE *dump = 0;
215 /* fix_sched_param() is called from toplev.c upon detection
216 of the -fsched-***-N options. */
219 fix_sched_param (param, val)
222 if (!strcmp (param, "verbose"))
223 sched_verbose_param = atoi (val);
225 warning ("fix_sched_param: unknown param: %s", param);
229 /* Arrays set up by scheduling for the same respective purposes as
230 similar-named arrays set up by flow analysis. We work with these
231 arrays during the scheduling pass so we can compare values against
234 Values of these arrays are copied at the end of this pass into the
235 arrays set up by flow analysis. */
236 static int *sched_reg_n_calls_crossed;
237 static int *sched_reg_live_length;
238 static int *sched_reg_basic_block;
240 /* We need to know the current block number during the post scheduling
241 update of live register information so that we can also update
242 REG_BASIC_BLOCK if a register changes blocks. */
243 static int current_block_num;
245 /* Element N is the next insn that sets (hard or pseudo) register
246 N within the current basic block; or zero, if there is no
247 such insn. Needed for new registers which may be introduced
248 by splitting insns. */
249 static rtx *reg_last_uses;
250 static rtx *reg_last_sets;
251 static regset reg_pending_sets;
252 static int reg_pending_sets_all;
254 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
255 static int *insn_luid;
256 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
258 /* Vector indexed by INSN_UID giving each instruction a priority. */
259 static int *insn_priority;
260 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
262 static short *insn_costs;
263 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
265 /* Vector indexed by INSN_UID giving an encoding of the function units
267 static short *insn_units;
268 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
270 /* Vector indexed by INSN_UID giving each instruction a register-weight.
271 This weight is an estimation of the insn contribution to registers pressure. */
272 static int *insn_reg_weight;
273 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
275 /* Vector indexed by INSN_UID giving list of insns which
276 depend upon INSN. Unlike LOG_LINKS, it represents forward dependences. */
277 static rtx *insn_depend;
278 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
280 /* Vector indexed by INSN_UID. Initialized to the number of incoming
281 edges in forward dependence graph (= number of LOG_LINKS). As
282 scheduling procedes, dependence counts are decreased. An
283 instruction moves to the ready list when its counter is zero. */
284 static int *insn_dep_count;
285 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
287 /* Vector indexed by INSN_UID giving an encoding of the blockage range
288 function. The unit and the range are encoded. */
289 static unsigned int *insn_blockage;
290 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
292 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
293 #define ENCODE_BLOCKAGE(U, R) \
294 ((((U) << UNIT_BITS) << BLOCKAGE_BITS \
295 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
296 | MAX_BLOCKAGE_COST (R))
297 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
298 #define BLOCKAGE_RANGE(B) \
299 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
300 | ((B) & BLOCKAGE_MASK))
302 /* Encodings of the `<name>_unit_blockage_range' function. */
303 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
304 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
306 #define DONE_PRIORITY -1
307 #define MAX_PRIORITY 0x7fffffff
308 #define TAIL_PRIORITY 0x7ffffffe
309 #define LAUNCH_PRIORITY 0x7f000001
310 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
311 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
313 /* Vector indexed by INSN_UID giving number of insns referring to this insn. */
314 static int *insn_ref_count;
315 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
317 /* Vector indexed by INSN_UID giving line-number note in effect for each
318 insn. For line-number notes, this indicates whether the note may be
320 static rtx *line_note;
321 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
323 /* Vector indexed by basic block number giving the starting line-number
324 for each basic block. */
325 static rtx *line_note_head;
327 /* List of important notes we must keep around. This is a pointer to the
328 last element in the list. */
329 static rtx note_list;
331 /* Regsets telling whether a given register is live or dead before the last
332 scheduled insn. Must scan the instructions once before scheduling to
333 determine what registers are live or dead at the end of the block. */
334 static regset bb_live_regs;
336 /* Regset telling whether a given register is live after the insn currently
337 being scheduled. Before processing an insn, this is equal to bb_live_regs
338 above. This is used so that we can find registers that are newly born/dead
339 after processing an insn. */
340 static regset old_live_regs;
342 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
343 during the initial scan and reused later. If there are not exactly as
344 many REG_DEAD notes in the post scheduled code as there were in the
345 prescheduled code then we trigger an abort because this indicates a bug. */
346 static rtx dead_notes;
350 /* An instruction is ready to be scheduled when all insns preceding it
351 have already been scheduled. It is important to ensure that all
352 insns which use its result will not be executed until its result
353 has been computed. An insn is maintained in one of four structures:
355 (P) the "Pending" set of insns which cannot be scheduled until
356 their dependencies have been satisfied.
357 (Q) the "Queued" set of insns that can be scheduled when sufficient
359 (R) the "Ready" list of unscheduled, uncommitted insns.
360 (S) the "Scheduled" list of insns.
362 Initially, all insns are either "Pending" or "Ready" depending on
363 whether their dependencies are satisfied.
365 Insns move from the "Ready" list to the "Scheduled" list as they
366 are committed to the schedule. As this occurs, the insns in the
367 "Pending" list have their dependencies satisfied and move to either
368 the "Ready" list or the "Queued" set depending on whether
369 sufficient time has passed to make them ready. As time passes,
370 insns move from the "Queued" set to the "Ready" list. Insns may
371 move from the "Ready" list to the "Queued" set if they are blocked
372 due to a function unit conflict.
374 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
375 insns, i.e., those that are ready, queued, and pending.
376 The "Queued" set (Q) is implemented by the variable `insn_queue'.
377 The "Ready" list (R) is implemented by the variables `ready' and
379 The "Scheduled" list (S) is the new insn chain built by this pass.
381 The transition (R->S) is implemented in the scheduling loop in
382 `schedule_block' when the best insn to schedule is chosen.
383 The transition (R->Q) is implemented in `queue_insn' when an
384 insn is found to have a function unit conflict with the already
386 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
387 insns move from the ready list to the scheduled list.
388 The transition (Q->R) is implemented in 'queue_to_insn' as time
389 passes or stalls are introduced. */
391 /* Implement a circular buffer to delay instructions until sufficient
392 time has passed. INSN_QUEUE_SIZE is a power of two larger than
393 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
394 longest time an isnsn may be queued. */
395 static rtx insn_queue[INSN_QUEUE_SIZE];
396 static int q_ptr = 0;
397 static int q_size = 0;
398 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
399 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
401 /* Vector indexed by INSN_UID giving the minimum clock tick at which
402 the insn becomes ready. This is used to note timing constraints for
403 insns in the pending list. */
404 static int *insn_tick;
405 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
407 /* Data structure for keeping track of register information
408 during that register's life. */
417 /* Forward declarations. */
418 static void add_dependence PROTO ((rtx, rtx, enum reg_note));
419 static void remove_dependence PROTO ((rtx, rtx));
420 static rtx find_insn_list PROTO ((rtx, rtx));
421 static int insn_unit PROTO ((rtx));
422 static unsigned int blockage_range PROTO ((int, rtx));
423 static void clear_units PROTO ((void));
424 static int actual_hazard_this_instance PROTO ((int, int, rtx, int, int));
425 static void schedule_unit PROTO ((int, rtx, int));
426 static int actual_hazard PROTO ((int, rtx, int, int));
427 static int potential_hazard PROTO ((int, rtx, int));
428 static int insn_cost PROTO ((rtx, rtx, rtx));
429 static int priority PROTO ((rtx));
430 static void free_pending_lists PROTO ((void));
431 static void add_insn_mem_dependence PROTO ((rtx *, rtx *, rtx, rtx));
432 static void flush_pending_lists PROTO ((rtx, int));
433 static void sched_analyze_1 PROTO ((rtx, rtx));
434 static void sched_analyze_2 PROTO ((rtx, rtx));
435 static void sched_analyze_insn PROTO ((rtx, rtx, rtx));
436 static void sched_analyze PROTO ((rtx, rtx));
437 static void sched_note_set PROTO ((rtx, int));
438 static int rank_for_schedule PROTO ((const GENERIC_PTR, const GENERIC_PTR));
439 static void swap_sort PROTO ((rtx *, int));
440 static void queue_insn PROTO ((rtx, int));
441 static int schedule_insn PROTO ((rtx, rtx *, int, int));
442 static void create_reg_dead_note PROTO ((rtx, rtx));
443 static void attach_deaths PROTO ((rtx, rtx, int));
444 static void attach_deaths_insn PROTO ((rtx));
445 static int new_sometimes_live PROTO ((struct sometimes *, int, int));
446 static void finish_sometimes_live PROTO ((struct sometimes *, int));
447 static int schedule_block PROTO ((int, int));
448 static rtx regno_use_in PROTO ((int, rtx));
449 static void split_hard_reg_notes PROTO ((rtx, rtx, rtx));
450 static void new_insn_dead_notes PROTO ((rtx, rtx, rtx, rtx));
451 static void update_n_sets PROTO ((rtx, int));
452 static void update_flow_info PROTO ((rtx, rtx, rtx, rtx));
453 static char *safe_concat PROTO ((char *, char *, char *));
455 /* Main entry point of this file. */
456 void schedule_insns PROTO ((FILE *));
458 /* Mapping of insns to their original block prior to scheduling. */
459 static int *insn_orig_block;
460 #define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
462 /* Some insns (e.g. call) are not allowed to move across blocks. */
463 static char *cant_move;
464 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
466 /* Control flow graph edges are kept in circular lists. */
475 static edge *edge_table;
477 #define NEXT_IN(edge) (edge_table[edge].next_in)
478 #define NEXT_OUT(edge) (edge_table[edge].next_out)
479 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
480 #define TO_BLOCK(edge) (edge_table[edge].to_block)
482 /* Number of edges in the control flow graph. (in fact larger than
483 that by 1, since edge 0 is unused.) */
486 /* Circular list of incoming/outgoing edges of a block */
487 static int *in_edges;
488 static int *out_edges;
490 #define IN_EDGES(block) (in_edges[block])
491 #define OUT_EDGES(block) (out_edges[block])
493 /* List of labels which cannot be deleted, needed for control
494 flow graph construction. */
495 extern rtx forced_labels;
498 static int is_cfg_nonregular PROTO ((void));
499 static int build_control_flow PROTO ((int_list_ptr *, int_list_ptr *,
501 static void new_edge PROTO ((int, int));
504 /* A region is the main entity for interblock scheduling: insns
505 are allowed to move between blocks in the same region, along
506 control flow graph edges, in the 'up' direction. */
509 int rgn_nr_blocks; /* number of blocks in region */
510 int rgn_blocks; /* blocks in the region (actually index in rgn_bb_table) */
514 /* Number of regions in the procedure */
515 static int nr_regions;
517 /* Table of region descriptions */
518 static region *rgn_table;
520 /* Array of lists of regions' blocks */
521 static int *rgn_bb_table;
523 /* Topological order of blocks in the region (if b2 is reachable from
524 b1, block_to_bb[b2] > block_to_bb[b1]).
525 Note: A basic block is always referred to by either block or b,
526 while its topological order name (in the region) is refered to by
529 static int *block_to_bb;
531 /* The number of the region containing a block. */
532 static int *containing_rgn;
534 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
535 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
536 #define BLOCK_TO_BB(block) (block_to_bb[block])
537 #define CONTAINING_RGN(block) (containing_rgn[block])
539 void debug_regions PROTO ((void));
540 static void find_single_block_region PROTO ((void));
541 static void find_rgns PROTO ((int_list_ptr *, int_list_ptr *,
542 int *, int *, sbitmap *));
543 static int too_large PROTO ((int, int *, int *));
545 extern void debug_live PROTO ((int, int));
547 /* Blocks of the current region being scheduled. */
548 static int current_nr_blocks;
549 static int current_blocks;
551 /* The mapping from bb to block */
552 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
555 /* Bit vectors and bitset operations are needed for computations on
556 the control flow graph. */
558 typedef unsigned HOST_WIDE_INT *bitset;
561 int *first_member; /* pointer to the list start in bitlst_table. */
562 int nr_members; /* the number of members of the bit list. */
566 static int bitlst_table_last;
567 static int bitlst_table_size;
568 static int *bitlst_table;
570 static char bitset_member PROTO ((bitset, int, int));
571 static void extract_bitlst PROTO ((bitset, int, bitlst *));
573 /* target info declarations.
575 The block currently being scheduled is referred to as the "target" block,
576 while other blocks in the region from which insns can be moved to the
577 target are called "source" blocks. The candidate structure holds info
578 about such sources: are they valid? Speculative? Etc. */
579 typedef bitlst bblst;
590 static candidate *candidate_table;
592 /* A speculative motion requires checking live information on the path
593 from 'source' to 'target'. The split blocks are those to be checked.
594 After a speculative motion, live information should be modified in
597 Lists of split and update blocks for each candidate of the current
598 target are in array bblst_table */
599 static int *bblst_table, bblst_size, bblst_last;
601 #define IS_VALID(src) ( candidate_table[src].is_valid )
602 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
603 #define SRC_PROB(src) ( candidate_table[src].src_prob )
605 /* The bb being currently scheduled. */
606 static int target_bb;
609 typedef bitlst edgelst;
611 /* target info functions */
612 static void split_edges PROTO ((int, int, edgelst *));
613 static void compute_trg_info PROTO ((int));
614 void debug_candidate PROTO ((int));
615 void debug_candidates PROTO ((int));
618 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
619 typedef bitset bbset;
621 /* Number of words of the bbset. */
622 static int bbset_size;
624 /* Dominators array: dom[i] contains the bbset of dominators of
625 bb i in the region. */
628 /* bb 0 is the only region entry */
629 #define IS_RGN_ENTRY(bb) (!bb)
631 /* Is bb_src dominated by bb_trg. */
632 #define IS_DOMINATED(bb_src, bb_trg) \
633 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
635 /* Probability: Prob[i] is a float in [0, 1] which is the probability
636 of bb i relative to the region entry. */
639 /* The probability of bb_src, relative to bb_trg. Note, that while the
640 'prob[bb]' is a float in [0, 1], this macro returns an integer
642 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
645 /* Bit-set of edges, where bit i stands for edge i. */
646 typedef bitset edgeset;
648 /* Number of edges in the region. */
649 static int rgn_nr_edges;
651 /* Array of size rgn_nr_edges. */
652 static int *rgn_edges;
654 /* Number of words in an edgeset. */
655 static int edgeset_size;
657 /* Mapping from each edge in the graph to its number in the rgn. */
658 static int *edge_to_bit;
659 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
661 /* The split edges of a source bb is different for each target
662 bb. In order to compute this efficiently, the 'potential-split edges'
663 are computed for each bb prior to scheduling a region. This is actually
664 the split edges of each bb relative to the region entry.
666 pot_split[bb] is the set of potential split edges of bb. */
667 static edgeset *pot_split;
669 /* For every bb, a set of its ancestor edges. */
670 static edgeset *ancestor_edges;
672 static void compute_dom_prob_ps PROTO ((int));
674 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
675 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
676 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
677 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
679 /* parameters affecting the decision of rank_for_schedule() */
680 #define MIN_DIFF_PRIORITY 2
681 #define MIN_PROBABILITY 40
682 #define MIN_PROB_DIFF 10
684 /* speculative scheduling functions */
685 static int check_live_1 PROTO ((int, rtx));
686 static void update_live_1 PROTO ((int, rtx));
687 static int check_live PROTO ((rtx, int));
688 static void update_live PROTO ((rtx, int));
689 static void set_spec_fed PROTO ((rtx));
690 static int is_pfree PROTO ((rtx, int, int));
691 static int find_conditional_protection PROTO ((rtx, int));
692 static int is_conditionally_protected PROTO ((rtx, int, int));
693 static int may_trap_exp PROTO ((rtx, int));
694 static int haifa_classify_insn PROTO ((rtx));
695 static int is_prisky PROTO ((rtx, int, int));
696 static int is_exception_free PROTO ((rtx, int, int));
698 static char find_insn_mem_list PROTO ((rtx, rtx, rtx, rtx));
699 static void compute_block_forward_dependences PROTO ((int));
700 static void init_rgn_data_dependences PROTO ((int));
701 static void add_branch_dependences PROTO ((rtx, rtx));
702 static void compute_block_backward_dependences PROTO ((int));
703 void debug_dependencies PROTO ((void));
705 /* Notes handling mechanism:
706 =========================
707 Generally, NOTES are saved before scheduling and restored after scheduling.
708 The scheduler distinguishes between three types of notes:
710 (1) LINE_NUMBER notes, generated and used for debugging. Here,
711 before scheduling a region, a pointer to the LINE_NUMBER note is
712 added to the insn following it (in save_line_notes()), and the note
713 is removed (in rm_line_notes() and unlink_line_notes()). After
714 scheduling the region, this pointer is used for regeneration of
715 the LINE_NUMBER note (in restore_line_notes()).
717 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
718 Before scheduling a region, a pointer to the note is added to the insn
719 that follows or precedes it. (This happens as part of the data dependence
720 computation). After scheduling an insn, the pointer contained in it is
721 used for regenerating the corresponding note (in reemit_notes).
723 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
724 these notes are put in a list (in rm_other_notes() and
725 unlink_other_notes ()). After scheduling the block, these notes are
726 inserted at the beginning of the block (in schedule_block()). */
728 static rtx unlink_other_notes PROTO ((rtx, rtx));
729 static rtx unlink_line_notes PROTO ((rtx, rtx));
730 static void rm_line_notes PROTO ((int));
731 static void save_line_notes PROTO ((int));
732 static void restore_line_notes PROTO ((int));
733 static void rm_redundant_line_notes PROTO ((void));
734 static void rm_other_notes PROTO ((rtx, rtx));
735 static rtx reemit_notes PROTO ((rtx, rtx));
737 static void get_block_head_tail PROTO ((int, rtx *, rtx *));
739 static void find_pre_sched_live PROTO ((int));
740 static void find_post_sched_live PROTO ((int));
741 static void update_reg_usage PROTO ((void));
742 static int queue_to_ready PROTO ((rtx [], int));
744 void debug_ready_list PROTO ((rtx[], int));
745 static void init_target_units PROTO (());
746 static void insn_print_units PROTO ((rtx));
747 static int get_visual_tbl_length PROTO (());
748 static void init_block_visualization PROTO (());
749 static void print_block_visualization PROTO ((int, char *));
750 static void visualize_scheduled_insns PROTO ((int, int));
751 static void visualize_no_unit PROTO ((rtx));
752 static void visualize_stall_cycles PROTO ((int, int));
753 static void print_exp PROTO ((char *, rtx, int));
754 static void print_value PROTO ((char *, rtx, int));
755 static void print_pattern PROTO ((char *, rtx, int));
756 static void print_insn PROTO ((char *, rtx, int));
757 void debug_reg_vector PROTO ((regset));
759 static rtx move_insn1 PROTO ((rtx, rtx));
760 static rtx move_insn PROTO ((rtx, rtx));
761 static rtx group_leader PROTO ((rtx));
762 static int set_priorities PROTO ((int));
763 static void init_rtx_vector PROTO ((rtx **, rtx *, int, int));
764 static void schedule_region PROTO ((int));
765 static void split_block_insns PROTO ((int));
767 #endif /* INSN_SCHEDULING */
769 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
771 /* Helper functions for instruction scheduling. */
773 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
774 static rtx unused_insn_list;
776 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
777 static rtx unused_expr_list;
779 static void free_list PROTO ((rtx *, rtx *));
780 static rtx alloc_INSN_LIST PROTO ((rtx, rtx));
781 static rtx alloc_EXPR_LIST PROTO ((int, rtx, rtx));
784 free_list (listp, unused_listp)
785 rtx *listp, *unused_listp;
787 register rtx link, prev_link;
793 link = XEXP (prev_link, 1);
798 link = XEXP (link, 1);
801 XEXP (prev_link, 1) = *unused_listp;
802 *unused_listp = *listp;
807 alloc_INSN_LIST (val, next)
812 if (unused_insn_list)
814 r = unused_insn_list;
815 unused_insn_list = XEXP (r, 1);
818 PUT_REG_NOTE_KIND (r, VOIDmode);
821 r = gen_rtx_INSN_LIST (VOIDmode, val, next);
827 alloc_EXPR_LIST (kind, val, next)
833 if (unused_insn_list)
835 r = unused_insn_list;
836 unused_insn_list = XEXP (r, 1);
839 PUT_REG_NOTE_KIND (r, kind);
842 r = gen_rtx_EXPR_LIST (kind, val, next);
847 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
848 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
849 of dependence that this link represents. */
852 add_dependence (insn, elem, dep_type)
855 enum reg_note dep_type;
859 /* Don't depend an insn on itself. */
863 /* If elem is part of a sequence that must be scheduled together, then
864 make the dependence point to the last insn of the sequence.
865 When HAVE_cc0, it is possible for NOTEs to exist between users and
866 setters of the condition codes, so we must skip past notes here.
867 Otherwise, NOTEs are impossible here. */
869 next = NEXT_INSN (elem);
872 while (next && GET_CODE (next) == NOTE)
873 next = NEXT_INSN (next);
876 if (next && SCHED_GROUP_P (next)
877 && GET_CODE (next) != CODE_LABEL)
879 /* Notes will never intervene here though, so don't bother checking
881 /* We must reject CODE_LABELs, so that we don't get confused by one
882 that has LABEL_PRESERVE_P set, which is represented by the same
883 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
885 while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
886 && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
887 next = NEXT_INSN (next);
889 /* Again, don't depend an insn on itself. */
893 /* Make the dependence to NEXT, the last insn of the group, instead
894 of the original ELEM. */
898 #ifdef INSN_SCHEDULING
899 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
900 No need for interblock dependences with calls, since
901 calls are not moved between blocks. Note: the edge where
902 elem is a CALL is still required. */
903 if (GET_CODE (insn) == CALL_INSN
904 && (INSN_BB (elem) != INSN_BB (insn)))
909 /* Check that we don't already have this dependence. */
910 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
911 if (XEXP (link, 0) == elem)
913 /* If this is a more restrictive type of dependence than the existing
914 one, then change the existing dependence to this type. */
915 if ((int) dep_type < (int) REG_NOTE_KIND (link))
916 PUT_REG_NOTE_KIND (link, dep_type);
919 /* Might want to check one level of transitivity to save conses. */
921 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
922 LOG_LINKS (insn) = link;
924 /* Insn dependency, not data dependency. */
925 PUT_REG_NOTE_KIND (link, dep_type);
928 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
929 of INSN. Abort if not found. */
932 remove_dependence (insn, elem)
936 rtx prev, link, next;
939 for (prev = 0, link = LOG_LINKS (insn); link; link = next)
941 next = XEXP (link, 1);
942 if (XEXP (link, 0) == elem)
945 XEXP (prev, 1) = next;
947 LOG_LINKS (insn) = next;
949 XEXP (link, 1) = unused_insn_list;
950 unused_insn_list = link;
963 #ifndef INSN_SCHEDULING
965 schedule_insns (dump_file)
975 #define HAIFA_INLINE __inline
978 /* Computation of memory dependencies. */
980 /* The *_insns and *_mems are paired lists. Each pending memory operation
981 will have a pointer to the MEM rtx on one list and a pointer to the
982 containing insn on the other list in the same place in the list. */
984 /* We can't use add_dependence like the old code did, because a single insn
985 may have multiple memory accesses, and hence needs to be on the list
986 once for each memory access. Add_dependence won't let you add an insn
987 to a list more than once. */
989 /* An INSN_LIST containing all insns with pending read operations. */
990 static rtx pending_read_insns;
992 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
993 static rtx pending_read_mems;
995 /* An INSN_LIST containing all insns with pending write operations. */
996 static rtx pending_write_insns;
998 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
999 static rtx pending_write_mems;
1001 /* Indicates the combined length of the two pending lists. We must prevent
1002 these lists from ever growing too large since the number of dependencies
1003 produced is at least O(N*N), and execution time is at least O(4*N*N), as
1004 a function of the length of these pending lists. */
1006 static int pending_lists_length;
1008 /* The last insn upon which all memory references must depend.
1009 This is an insn which flushed the pending lists, creating a dependency
1010 between it and all previously pending memory references. This creates
1011 a barrier (or a checkpoint) which no memory reference is allowed to cross.
1013 This includes all non constant CALL_INSNs. When we do interprocedural
1014 alias analysis, this restriction can be relaxed.
1015 This may also be an INSN that writes memory if the pending lists grow
1018 static rtx last_pending_memory_flush;
1020 /* The last function call we have seen. All hard regs, and, of course,
1021 the last function call, must depend on this. */
1023 static rtx last_function_call;
1025 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
1026 that does not already cross a call. We create dependencies between each
1027 of those insn and the next call insn, to ensure that they won't cross a call
1028 after scheduling is done. */
1030 static rtx sched_before_next_call;
1032 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1033 so that insns independent of the last scheduled insn will be preferred
1034 over dependent instructions. */
1036 static rtx last_scheduled_insn;
1038 /* Data structures for the computation of data dependences in a regions. We
1039 keep one copy of each of the declared above variables for each bb in the
1040 region. Before analyzing the data dependences for a bb, its variables
1041 are initialized as a function of the variables of its predecessors. When
1042 the analysis for a bb completes, we save the contents of each variable X
1043 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
1044 copied to bb_pending_read_insns[bb]. Another change is that few
1045 variables are now a list of insns rather than a single insn:
1046 last_pending_memory_flash, last_function_call, reg_last_sets. The
1047 manipulation of these variables was changed appropriately. */
1049 static rtx **bb_reg_last_uses;
1050 static rtx **bb_reg_last_sets;
1052 static rtx *bb_pending_read_insns;
1053 static rtx *bb_pending_read_mems;
1054 static rtx *bb_pending_write_insns;
1055 static rtx *bb_pending_write_mems;
1056 static int *bb_pending_lists_length;
1058 static rtx *bb_last_pending_memory_flush;
1059 static rtx *bb_last_function_call;
1060 static rtx *bb_sched_before_next_call;
1062 /* functions for construction of the control flow graph. */
1064 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1066 We decide not to build the control flow graph if there is possibly more
1067 than one entry to the function, if computed branches exist, of if we
1068 have nonlocal gotos. */
1071 is_cfg_nonregular ()
1077 /* If we have a label that could be the target of a nonlocal goto, then
1078 the cfg is not well structured. */
1079 if (nonlocal_label_rtx_list () != NULL)
1082 /* If we have any forced labels, then the cfg is not well structured. */
1086 /* If this function has a computed jump, then we consider the cfg
1087 not well structured. */
1088 if (current_function_has_computed_jump)
1091 /* If we have exception handlers, then we consider the cfg not well
1092 structured. ?!? We should be able to handle this now that flow.c
1093 computes an accurate cfg for EH. */
1094 if (exception_handler_labels)
1097 /* If we have non-jumping insns which refer to labels, then we consider
1098 the cfg not well structured. */
1099 /* check for labels referred to other thn by jumps */
1100 for (b = 0; b < n_basic_blocks; b++)
1101 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
1103 code = GET_CODE (insn);
1104 if (GET_RTX_CLASS (code) == 'i')
1108 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1109 if (REG_NOTE_KIND (note) == REG_LABEL)
1113 if (insn == basic_block_end[b])
1117 /* All the tests passed. Consider the cfg well structured. */
1121 /* Build the control flow graph and set nr_edges.
1123 Instead of trying to build a cfg ourselves, we rely on flow to
1124 do it for us. Stamp out useless code (and bug) duplication.
1126 Return nonzero if an irregularity in the cfg is found which would
1127 prevent cross block scheduling. */
1130 build_control_flow (s_preds, s_succs, num_preds, num_succs)
1131 int_list_ptr *s_preds;
1132 int_list_ptr *s_succs;
1140 /* Count the number of edges in the cfg. */
1143 for (i = 0; i < n_basic_blocks; i++)
1145 nr_edges += num_succs[i];
1147 /* Unreachable loops with more than one basic block are detected
1148 during the DFS traversal in find_rgns.
1150 Unreachable loops with a single block are detected here. This
1151 test is redundant with the one in find_rgns, but it's much
1152 cheaper to go ahead and catch the trivial case here. */
1153 if (num_preds[i] == 0
1154 || (num_preds[i] == 1 && INT_LIST_VAL (s_preds[i]) == i))
1158 /* Account for entry/exit edges. */
1161 in_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
1162 out_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
1163 bzero ((char *) in_edges, n_basic_blocks * sizeof (int));
1164 bzero ((char *) out_edges, n_basic_blocks * sizeof (int));
1166 edge_table = (edge *) xmalloc ((nr_edges) * sizeof (edge));
1167 bzero ((char *) edge_table, ((nr_edges) * sizeof (edge)));
1170 for (i = 0; i < n_basic_blocks; i++)
1171 for (succ = s_succs[i]; succ; succ = succ->next)
1173 if (INT_LIST_VAL (succ) != EXIT_BLOCK)
1174 new_edge (i, INT_LIST_VAL (succ));
1177 /* increment by 1, since edge 0 is unused. */
1184 /* Record an edge in the control flow graph from SOURCE to TARGET.
1186 In theory, this is redundant with the s_succs computed above, but
1187 we have not converted all of haifa to use information from the
1191 new_edge (source, target)
1195 int curr_edge, fst_edge;
1197 /* check for duplicates */
1198 fst_edge = curr_edge = OUT_EDGES (source);
1201 if (FROM_BLOCK (curr_edge) == source
1202 && TO_BLOCK (curr_edge) == target)
1207 curr_edge = NEXT_OUT (curr_edge);
1209 if (fst_edge == curr_edge)
1215 FROM_BLOCK (e) = source;
1216 TO_BLOCK (e) = target;
1218 if (OUT_EDGES (source))
1220 next_edge = NEXT_OUT (OUT_EDGES (source));
1221 NEXT_OUT (OUT_EDGES (source)) = e;
1222 NEXT_OUT (e) = next_edge;
1226 OUT_EDGES (source) = e;
1230 if (IN_EDGES (target))
1232 next_edge = NEXT_IN (IN_EDGES (target));
1233 NEXT_IN (IN_EDGES (target)) = e;
1234 NEXT_IN (e) = next_edge;
1238 IN_EDGES (target) = e;
1244 /* BITSET macros for operations on the control flow graph. */
1246 /* Compute bitwise union of two bitsets. */
1247 #define BITSET_UNION(set1, set2, len) \
1248 do { register bitset tp = set1, sp = set2; \
1250 for (i = 0; i < len; i++) \
1251 *(tp++) |= *(sp++); } while (0)
1253 /* Compute bitwise intersection of two bitsets. */
1254 #define BITSET_INTER(set1, set2, len) \
1255 do { register bitset tp = set1, sp = set2; \
1257 for (i = 0; i < len; i++) \
1258 *(tp++) &= *(sp++); } while (0)
1260 /* Compute bitwise difference of two bitsets. */
1261 #define BITSET_DIFFER(set1, set2, len) \
1262 do { register bitset tp = set1, sp = set2; \
1264 for (i = 0; i < len; i++) \
1265 *(tp++) &= ~*(sp++); } while (0)
1267 /* Inverts every bit of bitset 'set' */
1268 #define BITSET_INVERT(set, len) \
1269 do { register bitset tmpset = set; \
1271 for (i = 0; i < len; i++, tmpset++) \
1272 *tmpset = ~*tmpset; } while (0)
1274 /* Turn on the index'th bit in bitset set. */
1275 #define BITSET_ADD(set, index, len) \
1277 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1280 set[index/HOST_BITS_PER_WIDE_INT] |= \
1281 1 << (index % HOST_BITS_PER_WIDE_INT); \
1284 /* Turn off the index'th bit in set. */
1285 #define BITSET_REMOVE(set, index, len) \
1287 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1290 set[index/HOST_BITS_PER_WIDE_INT] &= \
1291 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1295 /* Check if the index'th bit in bitset set is on. */
1298 bitset_member (set, index, len)
1302 if (index >= HOST_BITS_PER_WIDE_INT * len)
1304 return (set[index / HOST_BITS_PER_WIDE_INT] &
1305 1 << (index % HOST_BITS_PER_WIDE_INT)) ? 1 : 0;
1309 /* Translate a bit-set SET to a list BL of the bit-set members. */
1312 extract_bitlst (set, len, bl)
1318 unsigned HOST_WIDE_INT word;
1320 /* bblst table space is reused in each call to extract_bitlst */
1321 bitlst_table_last = 0;
1323 bl->first_member = &bitlst_table[bitlst_table_last];
1326 for (i = 0; i < len; i++)
1329 offset = i * HOST_BITS_PER_WIDE_INT;
1330 for (j = 0; word; j++)
1334 bitlst_table[bitlst_table_last++] = offset;
1345 /* functions for the construction of regions */
1347 /* Print the regions, for debugging purposes. Callable from debugger. */
1354 fprintf (dump, "\n;; ------------ REGIONS ----------\n\n");
1355 for (rgn = 0; rgn < nr_regions; rgn++)
1357 fprintf (dump, ";;\trgn %d nr_blocks %d:\n", rgn,
1358 rgn_table[rgn].rgn_nr_blocks);
1359 fprintf (dump, ";;\tbb/block: ");
1361 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
1363 current_blocks = RGN_BLOCKS (rgn);
1365 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
1368 fprintf (dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
1371 fprintf (dump, "\n\n");
1376 /* Build a single block region for each basic block in the function.
1377 This allows for using the same code for interblock and basic block
1381 find_single_block_region ()
1385 for (i = 0; i < n_basic_blocks; i++)
1387 rgn_bb_table[i] = i;
1388 RGN_NR_BLOCKS (i) = 1;
1390 CONTAINING_RGN (i) = i;
1391 BLOCK_TO_BB (i) = 0;
1393 nr_regions = n_basic_blocks;
1397 /* Update number of blocks and the estimate for number of insns
1398 in the region. Return 1 if the region is "too large" for interblock
1399 scheduling (compile time considerations), otherwise return 0. */
1402 too_large (block, num_bbs, num_insns)
1403 int block, *num_bbs, *num_insns;
1406 (*num_insns) += (INSN_LUID (basic_block_end[block]) -
1407 INSN_LUID (basic_block_head[block]));
1408 if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
1415 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1416 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1417 loop containing blk. */
1418 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1420 if (max_hdr[blk] == -1) \
1421 max_hdr[blk] = hdr; \
1422 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1423 RESET_BIT (inner, hdr); \
1424 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1426 RESET_BIT (inner,max_hdr[blk]); \
1427 max_hdr[blk] = hdr; \
1432 /* Find regions for interblock scheduling.
1434 A region for scheduling can be:
1436 * A loop-free procedure, or
1438 * A reducible inner loop, or
1440 * A basic block not contained in any other region.
1443 ?!? In theory we could build other regions based on extended basic
1444 blocks or reverse extended basic blocks. Is it worth the trouble?
1446 Loop blocks that form a region are put into the region's block list
1447 in topological order.
1449 This procedure stores its results into the following global (ick) variables
1458 We use dominator relationships to avoid making regions out of non-reducible
1461 This procedure needs to be converted to work on pred/succ lists instead
1462 of edge tables. That would simplify it somewhat. */
1465 find_rgns (s_preds, s_succs, num_preds, num_succs, dom)
1466 int_list_ptr *s_preds;
1467 int_list_ptr *s_succs;
1472 int *max_hdr, *dfs_nr, *stack, *queue, *degree;
1474 int node, child, loop_head, i, j, head, tail;
1475 int count = 0, sp, idx = 0, current_edge = out_edges[0];
1476 int num_bbs, num_insns, unreachable;
1477 int too_large_failure;
1479 /* Note if an edge has been passed. */
1482 /* Note if a block is a natural loop header. */
1485 /* Note if a block is an natural inner loop header. */
1488 /* Note if a block is in the block queue. */
1491 /* Note if a block is in the block queue. */
1494 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1495 and a mapping from block to its loop header (if the block is contained
1496 in a loop, else -1).
1498 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1499 be used as inputs to the second traversal.
1501 STACK, SP and DFS_NR are only used during the first traversal. */
1503 /* Allocate and initialize variables for the first traversal. */
1504 max_hdr = (int *) alloca (n_basic_blocks * sizeof (int));
1505 dfs_nr = (int *) alloca (n_basic_blocks * sizeof (int));
1506 bzero ((char *) dfs_nr, n_basic_blocks * sizeof (int));
1507 stack = (int *) alloca (nr_edges * sizeof (int));
1509 inner = sbitmap_alloc (n_basic_blocks);
1510 sbitmap_ones (inner);
1512 header = sbitmap_alloc (n_basic_blocks);
1513 sbitmap_zero (header);
1515 passed = sbitmap_alloc (nr_edges);
1516 sbitmap_zero (passed);
1518 in_queue = sbitmap_alloc (n_basic_blocks);
1519 sbitmap_zero (in_queue);
1521 in_stack = sbitmap_alloc (n_basic_blocks);
1522 sbitmap_zero (in_stack);
1524 for (i = 0; i < n_basic_blocks; i++)
1527 /* DFS traversal to find inner loops in the cfg. */
1532 if (current_edge == 0 || TEST_BIT (passed, current_edge))
1534 /* We have reached a leaf node or a node that was already
1535 processed. Pop edges off the stack until we find
1536 an edge that has not yet been processed. */
1538 && (current_edge == 0 || TEST_BIT (passed, current_edge)))
1540 /* Pop entry off the stack. */
1541 current_edge = stack[sp--];
1542 node = FROM_BLOCK (current_edge);
1543 child = TO_BLOCK (current_edge);
1544 RESET_BIT (in_stack, child);
1545 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1546 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1547 current_edge = NEXT_OUT (current_edge);
1550 /* See if have finished the DFS tree traversal. */
1551 if (sp < 0 && TEST_BIT (passed, current_edge))
1554 /* Nope, continue the traversal with the popped node. */
1558 /* Process a node. */
1559 node = FROM_BLOCK (current_edge);
1560 child = TO_BLOCK (current_edge);
1561 SET_BIT (in_stack, node);
1562 dfs_nr[node] = ++count;
1564 /* If the successor is in the stack, then we've found a loop.
1565 Mark the loop, if it is not a natural loop, then it will
1566 be rejected during the second traversal. */
1567 if (TEST_BIT (in_stack, child))
1570 SET_BIT (header, child);
1571 UPDATE_LOOP_RELATIONS (node, child);
1572 SET_BIT (passed, current_edge);
1573 current_edge = NEXT_OUT (current_edge);
1577 /* If the child was already visited, then there is no need to visit
1578 it again. Just update the loop relationships and restart
1582 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1583 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1584 SET_BIT (passed, current_edge);
1585 current_edge = NEXT_OUT (current_edge);
1589 /* Push an entry on the stack and continue DFS traversal. */
1590 stack[++sp] = current_edge;
1591 SET_BIT (passed, current_edge);
1592 current_edge = OUT_EDGES (child);
1595 /* Another check for unreachable blocks. The earlier test in
1596 is_cfg_nonregular only finds unreachable blocks that do not
1599 The DFS traversal will mark every block that is reachable from
1600 the entry node by placing a nonzero value in dfs_nr. Thus if
1601 dfs_nr is zero for any block, then it must be unreachable. */
1603 for (i = 0; i < n_basic_blocks; i++)
1610 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1611 to hold degree counts. */
1614 /* Compute the in-degree of every block in the graph */
1615 for (i = 0; i < n_basic_blocks; i++)
1616 degree[i] = num_preds[i];
1618 /* Do not perform region scheduling if there are any unreachable
1623 SET_BIT (header, 0);
1625 /* Second travsersal:find reducible inner loops and topologically sort
1626 block of each region. */
1628 queue = (int *) alloca (n_basic_blocks * sizeof (int));
1630 /* Find blocks which are inner loop headers. We still have non-reducible
1631 loops to consider at this point. */
1632 for (i = 0; i < n_basic_blocks; i++)
1634 if (TEST_BIT (header, i) && TEST_BIT (inner, i))
1639 /* Now check that the loop is reducible. We do this separate
1640 from finding inner loops so that we do not find a reducible
1641 loop which contains an inner non-reducible loop.
1643 A simple way to find reducible/natrual loops is to verify
1644 that each block in the loop is dominated by the loop
1647 If there exists a block that is not dominated by the loop
1648 header, then the block is reachable from outside the loop
1649 and thus the loop is not a natural loop. */
1650 for (j = 0; j < n_basic_blocks; j++)
1652 /* First identify blocks in the loop, except for the loop
1654 if (i == max_hdr[j] && i != j)
1656 /* Now verify that the block is dominated by the loop
1658 if (!TEST_BIT (dom[j], i))
1663 /* If we exited the loop early, then I is the header of a non
1664 reducible loop and we should quit processing it now. */
1665 if (j != n_basic_blocks)
1668 /* I is a header of an inner loop, or block 0 in a subroutine
1669 with no loops at all. */
1671 too_large_failure = 0;
1672 loop_head = max_hdr[i];
1674 /* Decrease degree of all I's successors for topological
1676 for (ps = s_succs[i]; ps; ps = ps->next)
1677 if (INT_LIST_VAL (ps) != EXIT_BLOCK
1678 && INT_LIST_VAL (ps) != ENTRY_BLOCK)
1679 --degree[INT_LIST_VAL(ps)];
1681 /* Estimate # insns, and count # blocks in the region. */
1683 num_insns = (INSN_LUID (basic_block_end[i])
1684 - INSN_LUID (basic_block_head[i]));
1687 /* Find all loop latches (blocks which back edges to the loop
1688 header) or all the leaf blocks in the cfg has no loops.
1690 Place those blocks into the queue. */
1693 for (j = 0; j < n_basic_blocks; j++)
1694 /* Leaf nodes have only a single successor which must
1696 if (num_succs[j] == 1
1697 && INT_LIST_VAL (s_succs[j]) == EXIT_BLOCK)
1700 SET_BIT (in_queue, j);
1702 if (too_large (j, &num_bbs, &num_insns))
1704 too_large_failure = 1;
1713 for (ps = s_preds[i]; ps; ps = ps->next)
1715 node = INT_LIST_VAL (ps);
1717 if (node == ENTRY_BLOCK || node == EXIT_BLOCK)
1720 if (max_hdr[node] == loop_head && node != i)
1722 /* This is a loop latch. */
1723 queue[++tail] = node;
1724 SET_BIT (in_queue, node);
1726 if (too_large (node, &num_bbs, &num_insns))
1728 too_large_failure = 1;
1736 /* Now add all the blocks in the loop to the queue.
1738 We know the loop is a natural loop; however the algorithm
1739 above will not always mark certain blocks as being in the
1748 The algorithm in the DFS traversal may not mark B & D as part
1749 of the loop (ie they will not have max_hdr set to A).
1751 We know they can not be loop latches (else they would have
1752 had max_hdr set since they'd have a backedge to a dominator
1753 block). So we don't need them on the initial queue.
1755 We know they are part of the loop because they are dominated
1756 by the loop header and can be reached by a backwards walk of
1757 the edges starting with nodes on the initial queue.
1759 It is safe and desirable to include those nodes in the
1760 loop/scheduling region. To do so we would need to decrease
1761 the degree of a node if it is the target of a backedge
1762 within the loop itself as the node is placed in the queue.
1764 We do not do this because I'm not sure that the actual
1765 scheduling code will properly handle this case. ?!? */
1767 while (head < tail && !too_large_failure)
1770 child = queue[++head];
1772 for (ps = s_preds[child]; ps; ps = ps->next)
1774 node = INT_LIST_VAL (ps);
1776 /* See discussion above about nodes not marked as in
1777 this loop during the initial DFS traversal. */
1778 if (node == ENTRY_BLOCK || node == EXIT_BLOCK
1779 || max_hdr[node] != loop_head)
1784 else if (!TEST_BIT (in_queue, node) && node != i)
1786 queue[++tail] = node;
1787 SET_BIT (in_queue, node);
1789 if (too_large (node, &num_bbs, &num_insns))
1791 too_large_failure = 1;
1798 if (tail >= 0 && !too_large_failure)
1800 /* Place the loop header into list of region blocks. */
1802 rgn_bb_table[idx] = i;
1803 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1804 RGN_BLOCKS (nr_regions) = idx++;
1805 CONTAINING_RGN (i) = nr_regions;
1806 BLOCK_TO_BB (i) = count = 0;
1808 /* Remove blocks from queue[] when their in degree becomes
1809 zero. Repeat until no blocks are left on the list. This
1810 produces a topological list of blocks in the region. */
1817 child = queue[head];
1818 if (degree[child] == 0)
1821 rgn_bb_table[idx++] = child;
1822 BLOCK_TO_BB (child) = ++count;
1823 CONTAINING_RGN (child) = nr_regions;
1824 queue[head] = queue[tail--];
1826 for (ps = s_succs[child]; ps; ps = ps->next)
1827 if (INT_LIST_VAL (ps) != ENTRY_BLOCK
1828 && INT_LIST_VAL (ps) != EXIT_BLOCK)
1829 --degree[INT_LIST_VAL (ps)];
1840 /* Any block that did not end up in a region is placed into a region
1842 for (i = 0; i < n_basic_blocks; i++)
1845 rgn_bb_table[idx] = i;
1846 RGN_NR_BLOCKS (nr_regions) = 1;
1847 RGN_BLOCKS (nr_regions) = idx++;
1848 CONTAINING_RGN (i) = nr_regions++;
1849 BLOCK_TO_BB (i) = 0;
1860 /* functions for regions scheduling information */
1862 /* Compute dominators, probability, and potential-split-edges of bb.
1863 Assume that these values were already computed for bb's predecessors. */
1866 compute_dom_prob_ps (bb)
1869 int nxt_in_edge, fst_in_edge, pred;
1870 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1873 if (IS_RGN_ENTRY (bb))
1875 BITSET_ADD (dom[bb], 0, bbset_size);
1880 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1882 /* intialize dom[bb] to '111..1' */
1883 BITSET_INVERT (dom[bb], bbset_size);
1887 pred = FROM_BLOCK (nxt_in_edge);
1888 BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
1890 BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
1893 BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
1896 nr_rgn_out_edges = 0;
1897 fst_out_edge = OUT_EDGES (pred);
1898 nxt_out_edge = NEXT_OUT (fst_out_edge);
1899 BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
1902 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
1904 /* the successor doesn't belong the region? */
1905 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1906 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1909 while (fst_out_edge != nxt_out_edge)
1912 /* the successor doesn't belong the region? */
1913 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1914 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1916 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
1917 nxt_out_edge = NEXT_OUT (nxt_out_edge);
1921 /* now nr_rgn_out_edges is the number of region-exit edges from pred,
1922 and nr_out_edges will be the number of pred out edges not leaving
1924 nr_out_edges -= nr_rgn_out_edges;
1925 if (nr_rgn_out_edges > 0)
1926 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1928 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1929 nxt_in_edge = NEXT_IN (nxt_in_edge);
1931 while (fst_in_edge != nxt_in_edge);
1933 BITSET_ADD (dom[bb], bb, bbset_size);
1934 BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
1936 if (sched_verbose >= 2)
1937 fprintf (dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb), (int) (100.0 * prob[bb]));
1938 } /* compute_dom_prob_ps */
1940 /* functions for target info */
1942 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1943 Note that bb_trg dominates bb_src. */
1946 split_edges (bb_src, bb_trg, bl)
1951 int es = edgeset_size;
1952 edgeset src = (edgeset) alloca (es * sizeof (HOST_WIDE_INT));
1955 src[es] = (pot_split[bb_src])[es];
1956 BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
1957 extract_bitlst (src, edgeset_size, bl);
1961 /* Find the valid candidate-source-blocks for the target block TRG, compute
1962 their probability, and check if they are speculative or not.
1963 For speculative sources, compute their update-blocks and split-blocks. */
1966 compute_trg_info (trg)
1969 register candidate *sp;
1971 int check_block, update_idx;
1972 int i, j, k, fst_edge, nxt_edge;
1974 /* define some of the fields for the target bb as well */
1975 sp = candidate_table + trg;
1977 sp->is_speculative = 0;
1980 for (i = trg + 1; i < current_nr_blocks; i++)
1982 sp = candidate_table + i;
1984 sp->is_valid = IS_DOMINATED (i, trg);
1987 sp->src_prob = GET_SRC_PROB (i, trg);
1988 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
1993 split_edges (i, trg, &el);
1994 sp->is_speculative = (el.nr_members) ? 1 : 0;
1995 if (sp->is_speculative && !flag_schedule_speculative)
2001 sp->split_bbs.first_member = &bblst_table[bblst_last];
2002 sp->split_bbs.nr_members = el.nr_members;
2003 for (j = 0; j < el.nr_members; bblst_last++, j++)
2004 bblst_table[bblst_last] =
2005 TO_BLOCK (rgn_edges[el.first_member[j]]);
2006 sp->update_bbs.first_member = &bblst_table[bblst_last];
2008 for (j = 0; j < el.nr_members; j++)
2010 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
2011 fst_edge = nxt_edge = OUT_EDGES (check_block);
2014 for (k = 0; k < el.nr_members; k++)
2015 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
2018 if (k >= el.nr_members)
2020 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
2024 nxt_edge = NEXT_OUT (nxt_edge);
2026 while (fst_edge != nxt_edge);
2028 sp->update_bbs.nr_members = update_idx;
2033 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
2035 sp->is_speculative = 0;
2039 } /* compute_trg_info */
2042 /* Print candidates info, for debugging purposes. Callable from debugger. */
2048 if (!candidate_table[i].is_valid)
2051 if (candidate_table[i].is_speculative)
2054 fprintf (dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
2056 fprintf (dump, "split path: ");
2057 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
2059 int b = candidate_table[i].split_bbs.first_member[j];
2061 fprintf (dump, " %d ", b);
2063 fprintf (dump, "\n");
2065 fprintf (dump, "update path: ");
2066 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
2068 int b = candidate_table[i].update_bbs.first_member[j];
2070 fprintf (dump, " %d ", b);
2072 fprintf (dump, "\n");
2076 fprintf (dump, " src %d equivalent\n", BB_TO_BLOCK (i));
2081 /* Print candidates info, for debugging purposes. Callable from debugger. */
2084 debug_candidates (trg)
2089 fprintf (dump, "----------- candidate table: target: b=%d bb=%d ---\n",
2090 BB_TO_BLOCK (trg), trg);
2091 for (i = trg + 1; i < current_nr_blocks; i++)
2092 debug_candidate (i);
2096 /* functions for speculative scheduing */
2098 /* Return 0 if x is a set of a register alive in the beginning of one
2099 of the split-blocks of src, otherwise return 1. */
2102 check_live_1 (src, x)
2108 register rtx reg = SET_DEST (x);
2113 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2114 || GET_CODE (reg) == SIGN_EXTRACT
2115 || GET_CODE (reg) == STRICT_LOW_PART)
2116 reg = XEXP (reg, 0);
2118 if (GET_CODE (reg) != REG)
2121 regno = REGNO (reg);
2123 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2125 /* Global registers are assumed live */
2130 if (regno < FIRST_PSEUDO_REGISTER)
2132 /* check for hard registers */
2133 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2136 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2138 int b = candidate_table[src].split_bbs.first_member[i];
2140 if (REGNO_REG_SET_P (basic_block_live_at_start[b], regno + j))
2149 /* check for psuedo registers */
2150 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2152 int b = candidate_table[src].split_bbs.first_member[i];
2154 if (REGNO_REG_SET_P (basic_block_live_at_start[b], regno))
2166 /* If x is a set of a register R, mark that R is alive in the beginning
2167 of every update-block of src. */
2170 update_live_1 (src, x)
2176 register rtx reg = SET_DEST (x);
2181 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2182 || GET_CODE (reg) == SIGN_EXTRACT
2183 || GET_CODE (reg) == STRICT_LOW_PART)
2184 reg = XEXP (reg, 0);
2186 if (GET_CODE (reg) != REG)
2189 /* Global registers are always live, so the code below does not apply
2192 regno = REGNO (reg);
2194 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
2196 if (regno < FIRST_PSEUDO_REGISTER)
2198 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2201 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2203 int b = candidate_table[src].update_bbs.first_member[i];
2205 SET_REGNO_REG_SET (basic_block_live_at_start[b], regno + j);
2211 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2213 int b = candidate_table[src].update_bbs.first_member[i];
2215 SET_REGNO_REG_SET (basic_block_live_at_start[b], regno);
2222 /* Return 1 if insn can be speculatively moved from block src to trg,
2223 otherwise return 0. Called before first insertion of insn to
2224 ready-list or before the scheduling. */
2227 check_live (insn, src)
2231 /* find the registers set by instruction */
2232 if (GET_CODE (PATTERN (insn)) == SET
2233 || GET_CODE (PATTERN (insn)) == CLOBBER)
2234 return check_live_1 (src, PATTERN (insn));
2235 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2238 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2239 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2240 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2241 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
2251 /* Update the live registers info after insn was moved speculatively from
2252 block src to trg. */
2255 update_live (insn, src)
2259 /* find the registers set by instruction */
2260 if (GET_CODE (PATTERN (insn)) == SET
2261 || GET_CODE (PATTERN (insn)) == CLOBBER)
2262 update_live_1 (src, PATTERN (insn));
2263 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2266 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2267 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2268 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2269 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
2273 /* Exception Free Loads:
2275 We define five classes of speculative loads: IFREE, IRISKY,
2276 PFREE, PRISKY, and MFREE.
2278 IFREE loads are loads that are proved to be exception-free, just
2279 by examining the load insn. Examples for such loads are loads
2280 from TOC and loads of global data.
2282 IRISKY loads are loads that are proved to be exception-risky,
2283 just by examining the load insn. Examples for such loads are
2284 volatile loads and loads from shared memory.
2286 PFREE loads are loads for which we can prove, by examining other
2287 insns, that they are exception-free. Currently, this class consists
2288 of loads for which we are able to find a "similar load", either in
2289 the target block, or, if only one split-block exists, in that split
2290 block. Load2 is similar to load1 if both have same single base
2291 register. We identify only part of the similar loads, by finding
2292 an insn upon which both load1 and load2 have a DEF-USE dependence.
2294 PRISKY loads are loads for which we can prove, by examining other
2295 insns, that they are exception-risky. Currently we have two proofs for
2296 such loads. The first proof detects loads that are probably guarded by a
2297 test on the memory address. This proof is based on the
2298 backward and forward data dependence information for the region.
2299 Let load-insn be the examined load.
2300 Load-insn is PRISKY iff ALL the following hold:
2302 - insn1 is not in the same block as load-insn
2303 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2304 - test-insn is either a compare or a branch, not in the same block as load-insn
2305 - load-insn is reachable from test-insn
2306 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2308 This proof might fail when the compare and the load are fed
2309 by an insn not in the region. To solve this, we will add to this
2310 group all loads that have no input DEF-USE dependence.
2312 The second proof detects loads that are directly or indirectly
2313 fed by a speculative load. This proof is affected by the
2314 scheduling process. We will use the flag fed_by_spec_load.
2315 Initially, all insns have this flag reset. After a speculative
2316 motion of an insn, if insn is either a load, or marked as
2317 fed_by_spec_load, we will also mark as fed_by_spec_load every
2318 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2319 load which is fed_by_spec_load is also PRISKY.
2321 MFREE (maybe-free) loads are all the remaining loads. They may be
2322 exception-free, but we cannot prove it.
2324 Now, all loads in IFREE and PFREE classes are considered
2325 exception-free, while all loads in IRISKY and PRISKY classes are
2326 considered exception-risky. As for loads in the MFREE class,
2327 these are considered either exception-free or exception-risky,
2328 depending on whether we are pessimistic or optimistic. We have
2329 to take the pessimistic approach to assure the safety of
2330 speculative scheduling, but we can take the optimistic approach
2331 by invoking the -fsched_spec_load_dangerous option. */
2333 enum INSN_TRAP_CLASS
2335 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
2336 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
2339 #define WORST_CLASS(class1, class2) \
2340 ((class1 > class2) ? class1 : class2)
2342 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between */
2343 /* some speculatively moved load insn and this one. */
2344 char *fed_by_spec_load;
2347 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2348 #define IS_REACHABLE(bb_from, bb_to) \
2350 || IS_RGN_ENTRY (bb_from) \
2351 || (bitset_member (ancestor_edges[bb_to], \
2352 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2354 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2355 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2357 /* Non-zero iff the address is comprised from at most 1 register */
2358 #define CONST_BASED_ADDRESS_P(x) \
2359 (GET_CODE (x) == REG \
2360 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2361 || (GET_CODE (x) == LO_SUM)) \
2362 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2363 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2365 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2368 set_spec_fed (load_insn)
2373 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
2374 if (GET_MODE (link) == VOIDmode)
2375 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
2376 } /* set_spec_fed */
2378 /* On the path from the insn to load_insn_bb, find a conditional branch */
2379 /* depending on insn, that guards the speculative load. */
2382 find_conditional_protection (insn, load_insn_bb)
2388 /* iterate through DEF-USE forward dependences */
2389 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2391 rtx next = XEXP (link, 0);
2392 if ((CONTAINING_RGN (INSN_BLOCK (next)) ==
2393 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
2394 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
2395 && load_insn_bb != INSN_BB (next)
2396 && GET_MODE (link) == VOIDmode
2397 && (GET_CODE (next) == JUMP_INSN
2398 || find_conditional_protection (next, load_insn_bb)))
2402 } /* find_conditional_protection */
2404 /* Returns 1 if the same insn1 that participates in the computation
2405 of load_insn's address is feeding a conditional branch that is
2406 guarding on load_insn. This is true if we find a the two DEF-USE
2408 insn1 -> ... -> conditional-branch
2409 insn1 -> ... -> load_insn,
2410 and if a flow path exist:
2411 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2412 and if insn1 is on the path
2413 region-entry -> ... -> bb_trg -> ... load_insn.
2415 Locate insn1 by climbing on LOG_LINKS from load_insn.
2416 Locate the branch by following INSN_DEPEND from insn1. */
2419 is_conditionally_protected (load_insn, bb_src, bb_trg)
2425 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
2427 rtx insn1 = XEXP (link, 0);
2429 /* must be a DEF-USE dependence upon non-branch */
2430 if (GET_MODE (link) != VOIDmode
2431 || GET_CODE (insn1) == JUMP_INSN)
2434 /* must exist a path: region-entry -> ... -> bb_trg -> ... load_insn */
2435 if (INSN_BB (insn1) == bb_src
2436 || (CONTAINING_RGN (INSN_BLOCK (insn1))
2437 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
2438 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
2439 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
2442 /* now search for the conditional-branch */
2443 if (find_conditional_protection (insn1, bb_src))
2446 /* recursive step: search another insn1, "above" current insn1. */
2447 return is_conditionally_protected (insn1, bb_src, bb_trg);
2450 /* the chain does not exsist */
2452 } /* is_conditionally_protected */
2454 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2455 load_insn can move speculatively from bb_src to bb_trg. All the
2456 following must hold:
2458 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2459 (2) load_insn and load1 have a def-use dependence upon
2460 the same insn 'insn1'.
2461 (3) either load2 is in bb_trg, or:
2462 - there's only one split-block, and
2463 - load1 is on the escape path, and
2465 From all these we can conclude that the two loads access memory
2466 addresses that differ at most by a constant, and hence if moving
2467 load_insn would cause an exception, it would have been caused by
2471 is_pfree (load_insn, bb_src, bb_trg)
2476 register candidate *candp = candidate_table + bb_src;
2478 if (candp->split_bbs.nr_members != 1)
2479 /* must have exactly one escape block */
2482 for (back_link = LOG_LINKS (load_insn);
2483 back_link; back_link = XEXP (back_link, 1))
2485 rtx insn1 = XEXP (back_link, 0);
2487 if (GET_MODE (back_link) == VOIDmode)
2489 /* found a DEF-USE dependence (insn1, load_insn) */
2492 for (fore_link = INSN_DEPEND (insn1);
2493 fore_link; fore_link = XEXP (fore_link, 1))
2495 rtx insn2 = XEXP (fore_link, 0);
2496 if (GET_MODE (fore_link) == VOIDmode)
2498 /* found a DEF-USE dependence (insn1, insn2) */
2499 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
2500 /* insn2 not guaranteed to be a 1 base reg load */
2503 if (INSN_BB (insn2) == bb_trg)
2504 /* insn2 is the similar load, in the target block */
2507 if (*(candp->split_bbs.first_member) == INSN_BLOCK (insn2))
2508 /* insn2 is a similar load, in a split-block */
2515 /* couldn't find a similar load */
2519 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2520 as found by analyzing insn's expression. */
2523 may_trap_exp (x, is_store)
2531 code = GET_CODE (x);
2541 /* The insn uses memory */
2542 /* a volatile load */
2543 if (MEM_VOLATILE_P (x))
2545 /* an exception-free load */
2546 if (!may_trap_p (x))
2548 /* a load with 1 base register, to be further checked */
2549 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
2550 return PFREE_CANDIDATE;
2551 /* no info on the load, to be further checked */
2552 return PRISKY_CANDIDATE;
2557 int i, insn_class = TRAP_FREE;
2559 /* neither store nor load, check if it may cause a trap */
2562 /* recursive step: walk the insn... */
2563 fmt = GET_RTX_FORMAT (code);
2564 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2568 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
2569 insn_class = WORST_CLASS (insn_class, tmp_class);
2571 else if (fmt[i] == 'E')
2574 for (j = 0; j < XVECLEN (x, i); j++)
2576 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
2577 insn_class = WORST_CLASS (insn_class, tmp_class);
2578 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2582 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2587 } /* may_trap_exp */
2590 /* Classifies insn for the purpose of verifying that it can be
2591 moved speculatively, by examining it's patterns, returning:
2592 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2593 TRAP_FREE: non-load insn.
2594 IFREE: load from a globaly safe location.
2595 IRISKY: volatile load.
2596 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2597 being either PFREE or PRISKY. */
2600 haifa_classify_insn (insn)
2603 rtx pat = PATTERN (insn);
2604 int tmp_class = TRAP_FREE;
2605 int insn_class = TRAP_FREE;
2608 if (GET_CODE (pat) == PARALLEL)
2610 int i, len = XVECLEN (pat, 0);
2612 for (i = len - 1; i >= 0; i--)
2614 code = GET_CODE (XVECEXP (pat, 0, i));
2618 /* test if it is a 'store' */
2619 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
2622 /* test if it is a store */
2623 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
2624 if (tmp_class == TRAP_RISKY)
2626 /* test if it is a load */
2628 WORST_CLASS (tmp_class,
2629 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 0));
2632 insn_class = WORST_CLASS (insn_class, tmp_class);
2633 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2639 code = GET_CODE (pat);
2643 /* test if it is a 'store' */
2644 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
2647 /* test if it is a store */
2648 tmp_class = may_trap_exp (SET_DEST (pat), 1);
2649 if (tmp_class == TRAP_RISKY)
2651 /* test if it is a load */
2653 WORST_CLASS (tmp_class,
2654 may_trap_exp (SET_SRC (pat), 0));
2657 insn_class = tmp_class;
2662 } /* haifa_classify_insn */
2664 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2665 a load moved speculatively, or if load_insn is protected by
2666 a compare on load_insn's address). */
2669 is_prisky (load_insn, bb_src, bb_trg)
2673 if (FED_BY_SPEC_LOAD (load_insn))
2676 if (LOG_LINKS (load_insn) == NULL)
2677 /* dependence may 'hide' out of the region. */
2680 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2686 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2687 Return 1 if insn is exception-free (and the motion is valid)
2691 is_exception_free (insn, bb_src, bb_trg)
2695 int insn_class = haifa_classify_insn (insn);
2697 /* handle non-load insns */
2708 if (!flag_schedule_speculative_load)
2710 IS_LOAD_INSN (insn) = 1;
2717 case PFREE_CANDIDATE:
2718 if (is_pfree (insn, bb_src, bb_trg))
2720 /* don't 'break' here: PFREE-candidate is also PRISKY-candidate */
2721 case PRISKY_CANDIDATE:
2722 if (!flag_schedule_speculative_load_dangerous
2723 || is_prisky (insn, bb_src, bb_trg))
2729 return flag_schedule_speculative_load_dangerous;
2730 } /* is_exception_free */
2733 /* Process an insn's memory dependencies. There are four kinds of
2736 (0) read dependence: read follows read
2737 (1) true dependence: read follows write
2738 (2) anti dependence: write follows read
2739 (3) output dependence: write follows write
2741 We are careful to build only dependencies which actually exist, and
2742 use transitivity to avoid building too many links. */
2744 /* Return the INSN_LIST containing INSN in LIST, or NULL
2745 if LIST does not contain INSN. */
2747 HAIFA_INLINE static rtx
2748 find_insn_list (insn, list)
2754 if (XEXP (list, 0) == insn)
2756 list = XEXP (list, 1);
2762 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 otherwise. */
2764 HAIFA_INLINE static char
2765 find_insn_mem_list (insn, x, list, list1)
2771 if (XEXP (list, 0) == insn
2772 && XEXP (list1, 0) == x)
2774 list = XEXP (list, 1);
2775 list1 = XEXP (list1, 1);
2781 /* Compute the function units used by INSN. This caches the value
2782 returned by function_units_used. A function unit is encoded as the
2783 unit number if the value is non-negative and the compliment of a
2784 mask if the value is negative. A function unit index is the
2785 non-negative encoding. */
2787 HAIFA_INLINE static int
2791 register int unit = INSN_UNIT (insn);
2795 recog_memoized (insn);
2797 /* A USE insn, or something else we don't need to understand.
2798 We can't pass these directly to function_units_used because it will
2799 trigger a fatal error for unrecognizable insns. */
2800 if (INSN_CODE (insn) < 0)
2804 unit = function_units_used (insn);
2805 /* Increment non-negative values so we can cache zero. */
2809 /* We only cache 16 bits of the result, so if the value is out of
2810 range, don't cache it. */
2811 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
2813 || (~unit & ((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
2814 INSN_UNIT (insn) = unit;
2816 return (unit > 0 ? unit - 1 : unit);
2819 /* Compute the blockage range for executing INSN on UNIT. This caches
2820 the value returned by the blockage_range_function for the unit.
2821 These values are encoded in an int where the upper half gives the
2822 minimum value and the lower half gives the maximum value. */
2824 HAIFA_INLINE static unsigned int
2825 blockage_range (unit, insn)
2829 unsigned int blockage = INSN_BLOCKAGE (insn);
2832 if (UNIT_BLOCKED (blockage) != unit + 1)
2834 range = function_units[unit].blockage_range_function (insn);
2835 /* We only cache the blockage range for one unit and then only if
2837 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
2838 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
2841 range = BLOCKAGE_RANGE (blockage);
2846 /* A vector indexed by function unit instance giving the last insn to use
2847 the unit. The value of the function unit instance index for unit U
2848 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2849 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2851 /* A vector indexed by function unit instance giving the minimum time when
2852 the unit will unblock based on the maximum blockage cost. */
2853 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2855 /* A vector indexed by function unit number giving the number of insns
2856 that remain to use the unit. */
2857 static int unit_n_insns[FUNCTION_UNITS_SIZE];
2859 /* Reset the function unit state to the null state. */
2864 bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
2865 bzero ((char *) unit_tick, sizeof (unit_tick));
2866 bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
2869 /* Return the issue-delay of an insn */
2871 HAIFA_INLINE static int
2872 insn_issue_delay (insn)
2876 int unit = insn_unit (insn);
2878 /* efficiency note: in fact, we are working 'hard' to compute a
2879 value that was available in md file, and is not available in
2880 function_units[] structure. It would be nice to have this
2881 value there, too. */
2884 if (function_units[unit].blockage_range_function &&
2885 function_units[unit].blockage_function)
2886 delay = function_units[unit].blockage_function (insn, insn);
2889 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2890 if ((unit & 1) != 0 && function_units[i].blockage_range_function
2891 && function_units[i].blockage_function)
2892 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
2897 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2898 instance INSTANCE at time CLOCK if the previous actual hazard cost
2901 HAIFA_INLINE static int
2902 actual_hazard_this_instance (unit, instance, insn, clock, cost)
2903 int unit, instance, clock, cost;
2906 int tick = unit_tick[instance]; /* issue time of the last issued insn */
2908 if (tick - clock > cost)
2910 /* The scheduler is operating forward, so unit's last insn is the
2911 executing insn and INSN is the candidate insn. We want a
2912 more exact measure of the blockage if we execute INSN at CLOCK
2913 given when we committed the execution of the unit's last insn.
2915 The blockage value is given by either the unit's max blockage
2916 constant, blockage range function, or blockage function. Use
2917 the most exact form for the given unit. */
2919 if (function_units[unit].blockage_range_function)
2921 if (function_units[unit].blockage_function)
2922 tick += (function_units[unit].blockage_function
2923 (unit_last_insn[instance], insn)
2924 - function_units[unit].max_blockage);
2926 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
2927 - function_units[unit].max_blockage);
2929 if (tick - clock > cost)
2930 cost = tick - clock;
2935 /* Record INSN as having begun execution on the units encoded by UNIT at
2938 HAIFA_INLINE static void
2939 schedule_unit (unit, insn, clock)
2947 int instance = unit;
2948 #if MAX_MULTIPLICITY > 1
2949 /* Find the first free instance of the function unit and use that
2950 one. We assume that one is free. */
2951 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2953 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
2955 instance += FUNCTION_UNITS_SIZE;
2958 unit_last_insn[instance] = insn;
2959 unit_tick[instance] = (clock + function_units[unit].max_blockage);
2962 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2963 if ((unit & 1) != 0)
2964 schedule_unit (i, insn, clock);
2967 /* Return the actual hazard cost of executing INSN on the units encoded by
2968 UNIT at time CLOCK if the previous actual hazard cost was COST. */
2970 HAIFA_INLINE static int
2971 actual_hazard (unit, insn, clock, cost)
2972 int unit, clock, cost;
2979 /* Find the instance of the function unit with the minimum hazard. */
2980 int instance = unit;
2981 int best_cost = actual_hazard_this_instance (unit, instance, insn,
2985 #if MAX_MULTIPLICITY > 1
2986 if (best_cost > cost)
2988 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2990 instance += FUNCTION_UNITS_SIZE;
2991 this_cost = actual_hazard_this_instance (unit, instance, insn,
2993 if (this_cost < best_cost)
2995 best_cost = this_cost;
2996 if (this_cost <= cost)
3002 cost = MAX (cost, best_cost);
3005 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3006 if ((unit & 1) != 0)
3007 cost = actual_hazard (i, insn, clock, cost);
3012 /* Return the potential hazard cost of executing an instruction on the
3013 units encoded by UNIT if the previous potential hazard cost was COST.
3014 An insn with a large blockage time is chosen in preference to one
3015 with a smaller time; an insn that uses a unit that is more likely
3016 to be used is chosen in preference to one with a unit that is less
3017 used. We are trying to minimize a subsequent actual hazard. */
3019 HAIFA_INLINE static int
3020 potential_hazard (unit, insn, cost)
3025 unsigned int minb, maxb;
3029 minb = maxb = function_units[unit].max_blockage;
3032 if (function_units[unit].blockage_range_function)
3034 maxb = minb = blockage_range (unit, insn);
3035 maxb = MAX_BLOCKAGE_COST (maxb);
3036 minb = MIN_BLOCKAGE_COST (minb);
3041 /* Make the number of instructions left dominate. Make the
3042 minimum delay dominate the maximum delay. If all these
3043 are the same, use the unit number to add an arbitrary
3044 ordering. Other terms can be added. */
3045 ncost = minb * 0x40 + maxb;
3046 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
3053 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3054 if ((unit & 1) != 0)
3055 cost = potential_hazard (i, insn, cost);
3060 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3061 This is the number of cycles between instruction issue and
3062 instruction results. */
3064 HAIFA_INLINE static int
3065 insn_cost (insn, link, used)
3066 rtx insn, link, used;
3068 register int cost = INSN_COST (insn);
3072 recog_memoized (insn);
3074 /* A USE insn, or something else we don't need to understand.
3075 We can't pass these directly to result_ready_cost because it will
3076 trigger a fatal error for unrecognizable insns. */
3077 if (INSN_CODE (insn) < 0)
3079 INSN_COST (insn) = 1;
3084 cost = result_ready_cost (insn);
3089 INSN_COST (insn) = cost;
3093 /* in this case estimate cost without caring how insn is used. */
3094 if (link == 0 && used == 0)
3097 /* A USE insn should never require the value used to be computed. This
3098 allows the computation of a function's result and parameter values to
3099 overlap the return and call. */
3100 recog_memoized (used);
3101 if (INSN_CODE (used) < 0)
3102 LINK_COST_FREE (link) = 1;
3104 /* If some dependencies vary the cost, compute the adjustment. Most
3105 commonly, the adjustment is complete: either the cost is ignored
3106 (in the case of an output- or anti-dependence), or the cost is
3107 unchanged. These values are cached in the link as LINK_COST_FREE
3108 and LINK_COST_ZERO. */
3110 if (LINK_COST_FREE (link))
3113 else if (!LINK_COST_ZERO (link))
3117 ADJUST_COST (used, link, insn, ncost);
3119 LINK_COST_FREE (link) = ncost = 1;
3121 LINK_COST_ZERO (link) = 1;
3128 /* Compute the priority number for INSN. */
3137 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
3140 if ((this_priority = INSN_PRIORITY (insn)) == 0)
3142 if (INSN_DEPEND (insn) == 0)
3143 this_priority = insn_cost (insn, 0, 0);
3145 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
3150 if (RTX_INTEGRATED_P (link))
3153 next = XEXP (link, 0);
3155 /* critical path is meaningful in block boundaries only */
3156 if (INSN_BLOCK (next) != INSN_BLOCK (insn))
3159 next_priority = insn_cost (insn, link, next) + priority (next);
3160 if (next_priority > this_priority)
3161 this_priority = next_priority;
3163 INSN_PRIORITY (insn) = this_priority;
3165 return this_priority;
3169 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3170 them to the unused_*_list variables, so that they can be reused. */
3173 free_pending_lists ()
3175 if (current_nr_blocks <= 1)
3177 free_list (&pending_read_insns, &unused_insn_list);
3178 free_list (&pending_write_insns, &unused_insn_list);
3179 free_list (&pending_read_mems, &unused_expr_list);
3180 free_list (&pending_write_mems, &unused_expr_list);
3184 /* interblock scheduling */
3187 for (bb = 0; bb < current_nr_blocks; bb++)
3189 free_list (&bb_pending_read_insns[bb], &unused_insn_list);
3190 free_list (&bb_pending_write_insns[bb], &unused_insn_list);
3191 free_list (&bb_pending_read_mems[bb], &unused_expr_list);
3192 free_list (&bb_pending_write_mems[bb], &unused_expr_list);
3197 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3198 The MEM is a memory reference contained within INSN, which we are saving
3199 so that we can do memory aliasing on it. */
3202 add_insn_mem_dependence (insn_list, mem_list, insn, mem)
3203 rtx *insn_list, *mem_list, insn, mem;
3207 link = alloc_INSN_LIST (insn, *insn_list);
3210 link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
3213 pending_lists_length++;
3217 /* Make a dependency between every memory reference on the pending lists
3218 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3222 flush_pending_lists (insn, only_write)
3229 while (pending_read_insns && ! only_write)
3231 add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
3233 link = pending_read_insns;
3234 pending_read_insns = XEXP (pending_read_insns, 1);
3235 XEXP (link, 1) = unused_insn_list;
3236 unused_insn_list = link;
3238 link = pending_read_mems;
3239 pending_read_mems = XEXP (pending_read_mems, 1);
3240 XEXP (link, 1) = unused_expr_list;
3241 unused_expr_list = link;
3243 while (pending_write_insns)
3245 add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
3247 link = pending_write_insns;
3248 pending_write_insns = XEXP (pending_write_insns, 1);
3249 XEXP (link, 1) = unused_insn_list;
3250 unused_insn_list = link;
3252 link = pending_write_mems;
3253 pending_write_mems = XEXP (pending_write_mems, 1);
3254 XEXP (link, 1) = unused_expr_list;
3255 unused_expr_list = link;
3257 pending_lists_length = 0;
3259 /* last_pending_memory_flush is now a list of insns */
3260 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3261 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3263 free_list (&last_pending_memory_flush, &unused_insn_list);
3264 last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
3267 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
3268 by the write to the destination of X, and reads of everything mentioned. */
3271 sched_analyze_1 (x, insn)
3276 register rtx dest = SET_DEST (x);
3281 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3282 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3284 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3286 /* The second and third arguments are values read by this insn. */
3287 sched_analyze_2 (XEXP (dest, 1), insn);
3288 sched_analyze_2 (XEXP (dest, 2), insn);
3290 dest = SUBREG_REG (dest);
3293 if (GET_CODE (dest) == REG)
3297 regno = REGNO (dest);
3299 /* A hard reg in a wide mode may really be multiple registers.
3300 If so, mark all of them just like the first. */
3301 if (regno < FIRST_PSEUDO_REGISTER)
3303 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
3308 for (u = reg_last_uses[regno + i]; u; u = XEXP (u, 1))
3309 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3310 reg_last_uses[regno + i] = 0;
3312 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3313 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3315 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
3317 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3318 /* Function calls clobber all call_used regs. */
3319 for (u = last_function_call; u; u = XEXP (u, 1))
3320 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3327 for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
3328 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3329 reg_last_uses[regno] = 0;
3331 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3332 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3334 SET_REGNO_REG_SET (reg_pending_sets, regno);
3336 /* Pseudos that are REG_EQUIV to something may be replaced
3337 by that during reloading. We need only add dependencies for
3338 the address in the REG_EQUIV note. */
3339 if (!reload_completed
3340 && reg_known_equiv_p[regno]
3341 && GET_CODE (reg_known_value[regno]) == MEM)
3342 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3344 /* Don't let it cross a call after scheduling if it doesn't
3345 already cross one. */
3347 if (REG_N_CALLS_CROSSED (regno) == 0)
3348 for (u = last_function_call; u; u = XEXP (u, 1))
3349 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3352 else if (GET_CODE (dest) == MEM)
3354 /* Writing memory. */
3356 if (pending_lists_length > 32)
3358 /* Flush all pending reads and writes to prevent the pending lists
3359 from getting any larger. Insn scheduling runs too slowly when
3360 these lists get long. The number 32 was chosen because it
3361 seems like a reasonable number. When compiling GCC with itself,
3362 this flush occurs 8 times for sparc, and 10 times for m88k using
3364 flush_pending_lists (insn, 0);
3369 rtx pending, pending_mem;
3371 pending = pending_read_insns;
3372 pending_mem = pending_read_mems;
3375 /* If a dependency already exists, don't create a new one. */
3376 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3377 if (anti_dependence (XEXP (pending_mem, 0), dest))
3378 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3380 pending = XEXP (pending, 1);
3381 pending_mem = XEXP (pending_mem, 1);
3384 pending = pending_write_insns;
3385 pending_mem = pending_write_mems;
3388 /* If a dependency already exists, don't create a new one. */
3389 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3390 if (output_dependence (XEXP (pending_mem, 0), dest))
3391 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
3393 pending = XEXP (pending, 1);
3394 pending_mem = XEXP (pending_mem, 1);
3397 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3398 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3400 add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
3403 sched_analyze_2 (XEXP (dest, 0), insn);
3406 /* Analyze reads. */
3407 if (GET_CODE (x) == SET)
3408 sched_analyze_2 (SET_SRC (x), insn);
3411 /* Analyze the uses of memory and registers in rtx X in INSN. */
3414 sched_analyze_2 (x, insn)
3420 register enum rtx_code code;
3426 code = GET_CODE (x);
3435 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3436 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3437 this does not mean that this insn is using cc0. */
3445 /* User of CC0 depends on immediately preceding insn. */
3446 SCHED_GROUP_P (insn) = 1;
3448 /* There may be a note before this insn now, but all notes will
3449 be removed before we actually try to schedule the insns, so
3450 it won't cause a problem later. We must avoid it here though. */
3451 prev = prev_nonnote_insn (insn);
3453 /* Make a copy of all dependencies on the immediately previous insn,
3454 and add to this insn. This is so that all the dependencies will
3455 apply to the group. Remove an explicit dependence on this insn
3456 as SCHED_GROUP_P now represents it. */
3458 if (find_insn_list (prev, LOG_LINKS (insn)))
3459 remove_dependence (insn, prev);
3461 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
3462 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3471 int regno = REGNO (x);
3472 if (regno < FIRST_PSEUDO_REGISTER)
3476 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
3479 reg_last_uses[regno + i]
3480 = alloc_INSN_LIST (insn, reg_last_uses[regno + i]);
3482 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3483 add_dependence (insn, XEXP (u, 0), 0);
3485 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3486 /* Function calls clobber all call_used regs. */
3487 for (u = last_function_call; u; u = XEXP (u, 1))
3488 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3493 reg_last_uses[regno] = alloc_INSN_LIST (insn, reg_last_uses[regno]);
3495 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3496 add_dependence (insn, XEXP (u, 0), 0);
3498 /* Pseudos that are REG_EQUIV to something may be replaced
3499 by that during reloading. We need only add dependencies for
3500 the address in the REG_EQUIV note. */
3501 if (!reload_completed
3502 && reg_known_equiv_p[regno]
3503 && GET_CODE (reg_known_value[regno]) == MEM)
3504 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3506 /* If the register does not already cross any calls, then add this
3507 insn to the sched_before_next_call list so that it will still
3508 not cross calls after scheduling. */
3509 if (REG_N_CALLS_CROSSED (regno) == 0)
3510 add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
3517 /* Reading memory. */
3519 rtx pending, pending_mem;
3521 pending = pending_read_insns;
3522 pending_mem = pending_read_mems;
3525 /* If a dependency already exists, don't create a new one. */
3526 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3527 if (read_dependence (XEXP (pending_mem, 0), x))
3528 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3530 pending = XEXP (pending, 1);
3531 pending_mem = XEXP (pending_mem, 1);
3534 pending = pending_write_insns;
3535 pending_mem = pending_write_mems;
3538 /* If a dependency already exists, don't create a new one. */
3539 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3540 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
3542 add_dependence (insn, XEXP (pending, 0), 0);
3544 pending = XEXP (pending, 1);
3545 pending_mem = XEXP (pending_mem, 1);
3548 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3549 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3551 /* Always add these dependencies to pending_reads, since
3552 this insn may be followed by a write. */
3553 add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
3556 /* Take advantage of tail recursion here. */
3557 sched_analyze_2 (XEXP (x, 0), insn);
3563 case UNSPEC_VOLATILE:
3568 /* Traditional and volatile asm instructions must be considered to use
3569 and clobber all hard registers, all pseudo-registers and all of
3570 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3572 Consider for instance a volatile asm that changes the fpu rounding
3573 mode. An insn should not be moved across this even if it only uses
3574 pseudo-regs because it might give an incorrectly rounded result. */
3575 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
3577 int max_reg = max_reg_num ();
3578 for (i = 0; i < max_reg; i++)
3580 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3581 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3582 reg_last_uses[i] = 0;
3584 /* reg_last_sets[r] is now a list of insns */
3585 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3586 add_dependence (insn, XEXP (u, 0), 0);
3588 reg_pending_sets_all = 1;
3590 flush_pending_lists (insn, 0);
3593 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3594 We can not just fall through here since then we would be confused
3595 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3596 traditional asms unlike their normal usage. */
3598 if (code == ASM_OPERANDS)
3600 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3601 sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
3611 /* These both read and modify the result. We must handle them as writes
3612 to get proper dependencies for following instructions. We must handle
3613 them as reads to get proper dependencies from this to previous
3614 instructions. Thus we need to pass them to both sched_analyze_1
3615 and sched_analyze_2. We must call sched_analyze_2 first in order
3616 to get the proper antecedent for the read. */
3617 sched_analyze_2 (XEXP (x, 0), insn);
3618 sched_analyze_1 (x, insn);
3625 /* Other cases: walk the insn. */
3626 fmt = GET_RTX_FORMAT (code);
3627 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3630 sched_analyze_2 (XEXP (x, i), insn);
3631 else if (fmt[i] == 'E')
3632 for (j = 0; j < XVECLEN (x, i); j++)
3633 sched_analyze_2 (XVECEXP (x, i, j), insn);
3637 /* Analyze an INSN with pattern X to find all dependencies. */
3640 sched_analyze_insn (x, insn, loop_notes)
3644 register RTX_CODE code = GET_CODE (x);
3646 int maxreg = max_reg_num ();
3649 if (code == SET || code == CLOBBER)
3650 sched_analyze_1 (x, insn);
3651 else if (code == PARALLEL)
3654 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3656 code = GET_CODE (XVECEXP (x, 0, i));
3657 if (code == SET || code == CLOBBER)
3658 sched_analyze_1 (XVECEXP (x, 0, i), insn);
3660 sched_analyze_2 (XVECEXP (x, 0, i), insn);
3664 sched_analyze_2 (x, insn);
3666 /* Mark registers CLOBBERED or used by called function. */
3667 if (GET_CODE (insn) == CALL_INSN)
3668 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3670 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3671 sched_analyze_1 (XEXP (link, 0), insn);
3673 sched_analyze_2 (XEXP (link, 0), insn);
3676 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic block, then
3677 we must be sure that no instructions are scheduled across it.
3678 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3679 become incorrect. */
3683 int max_reg = max_reg_num ();
3686 for (i = 0; i < max_reg; i++)
3689 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3690 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3691 reg_last_uses[i] = 0;
3693 /* reg_last_sets[r] is now a list of insns */
3694 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3695 add_dependence (insn, XEXP (u, 0), 0);
3697 reg_pending_sets_all = 1;
3699 flush_pending_lists (insn, 0);
3702 while (XEXP (link, 1))
3703 link = XEXP (link, 1);
3704 XEXP (link, 1) = REG_NOTES (insn);
3705 REG_NOTES (insn) = loop_notes;
3708 /* After reload, it is possible for an instruction to have a REG_DEAD note
3709 for a register that actually dies a few instructions earlier. For
3710 example, this can happen with SECONDARY_MEMORY_NEEDED reloads.
3711 In this case, we must consider the insn to use the register mentioned
3712 in the REG_DEAD note. Otherwise, we may accidentally move this insn
3713 after another insn that sets the register, thus getting obviously invalid
3714 rtl. This confuses reorg which believes that REG_DEAD notes are still
3717 ??? We would get better code if we fixed reload to put the REG_DEAD
3718 notes in the right places, but that may not be worth the effort. */
3720 if (reload_completed)
3724 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3725 if (REG_NOTE_KIND (note) == REG_DEAD)
3726 sched_analyze_2 (XEXP (note, 0), insn);
3729 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
3731 /* reg_last_sets[r] is now a list of insns */
3732 free_list (®_last_sets[i], &unused_insn_list);
3734 = alloc_INSN_LIST (insn, NULL_RTX);
3736 CLEAR_REG_SET (reg_pending_sets);
3738 if (reg_pending_sets_all)
3740 for (i = 0; i < maxreg; i++)
3742 /* reg_last_sets[r] is now a list of insns */
3743 free_list (®_last_sets[i], &unused_insn_list);
3744 reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3747 reg_pending_sets_all = 0;
3750 /* Handle function calls and function returns created by the epilogue
3752 if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
3757 /* When scheduling instructions, we make sure calls don't lose their
3758 accompanying USE insns by depending them one on another in order.
3760 Also, we must do the same thing for returns created by the epilogue
3761 threading code. Note this code works only in this special case,
3762 because other passes make no guarantee that they will never emit
3763 an instruction between a USE and a RETURN. There is such a guarantee
3764 for USE instructions immediately before a call. */
3766 prev_dep_insn = insn;
3767 dep_insn = PREV_INSN (insn);
3768 while (GET_CODE (dep_insn) == INSN
3769 && GET_CODE (PATTERN (dep_insn)) == USE
3770 && GET_CODE (XEXP (PATTERN (dep_insn), 0)) == REG)
3772 SCHED_GROUP_P (prev_dep_insn) = 1;
3774 /* Make a copy of all dependencies on dep_insn, and add to insn.
3775 This is so that all of the dependencies will apply to the
3778 for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
3779 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3781 prev_dep_insn = dep_insn;
3782 dep_insn = PREV_INSN (dep_insn);
3787 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3788 for every dependency. */
3791 sched_analyze (head, tail)
3798 for (insn = head;; insn = NEXT_INSN (insn))
3800 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
3802 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3805 else if (GET_CODE (insn) == CALL_INSN)
3810 CANT_MOVE (insn) = 1;
3812 /* Any instruction using a hard register which may get clobbered
3813 by a call needs to be marked as dependent on this call.
3814 This prevents a use of a hard return reg from being moved
3815 past a void call (i.e. it does not explicitly set the hard
3818 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3819 all registers, not just hard registers, may be clobbered by this
3822 /* Insn, being a CALL_INSN, magically depends on
3823 `last_function_call' already. */
3825 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
3826 && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
3828 int max_reg = max_reg_num ();
3829 for (i = 0; i < max_reg; i++)
3831 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3832 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3834 reg_last_uses[i] = 0;
3836 /* reg_last_sets[r] is now a list of insns */
3837 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3838 add_dependence (insn, XEXP (u, 0), 0);
3840 reg_pending_sets_all = 1;
3842 /* Add a pair of fake REG_NOTE which we will later
3843 convert back into a NOTE_INSN_SETJMP note. See
3844 reemit_notes for why we use a pair of NOTEs. */
3845 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3848 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3849 GEN_INT (NOTE_INSN_SETJMP),
3854 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3855 if (call_used_regs[i] || global_regs[i])
3857 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3858 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3859 reg_last_uses[i] = 0;
3861 /* reg_last_sets[r] is now a list of insns */
3862 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3863 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3865 SET_REGNO_REG_SET (reg_pending_sets, i);
3869 /* For each insn which shouldn't cross a call, add a dependence
3870 between that insn and this call insn. */
3871 x = LOG_LINKS (sched_before_next_call);
3874 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
3877 LOG_LINKS (sched_before_next_call) = 0;
3879 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3882 /* In the absence of interprocedural alias analysis, we must flush
3883 all pending reads and writes, and start new dependencies starting
3884 from here. But only flush writes for constant calls (which may
3885 be passed a pointer to something we haven't written yet). */
3886 flush_pending_lists (insn, CONST_CALL_P (insn));
3888 /* Depend this function call (actually, the user of this
3889 function call) on all hard register clobberage. */
3891 /* last_function_call is now a list of insns */
3892 free_list(&last_function_call, &unused_insn_list);
3893 last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3896 /* See comments on reemit_notes as to why we do this. */
3897 else if (GET_CODE (insn) == NOTE
3898 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
3899 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
3900 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
3901 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
3902 || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
3903 && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
3905 loop_notes = alloc_EXPR_LIST (REG_DEAD,
3906 GEN_INT (NOTE_BLOCK_NUMBER (insn)),
3908 loop_notes = alloc_EXPR_LIST (REG_DEAD,
3909 GEN_INT (NOTE_LINE_NUMBER (insn)),
3911 CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
3920 /* Called when we see a set of a register. If death is true, then we are
3921 scanning backwards. Mark that register as unborn. If nobody says
3922 otherwise, that is how things will remain. If death is false, then we
3923 are scanning forwards. Mark that register as being born. */
3926 sched_note_set (x, death)
3931 register rtx reg = SET_DEST (x);
3937 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
3938 || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
3940 /* Must treat modification of just one hardware register of a multi-reg
3941 value or just a byte field of a register exactly the same way that
3942 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
3943 does not kill the entire register. */
3944 if (GET_CODE (reg) != SUBREG
3945 || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
3948 reg = SUBREG_REG (reg);
3951 if (GET_CODE (reg) != REG)
3954 /* Global registers are always live, so the code below does not apply
3957 regno = REGNO (reg);
3958 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
3962 /* If we only set part of the register, then this set does not
3967 /* Try killing this register. */
3968 if (regno < FIRST_PSEUDO_REGISTER)
3970 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
3973 CLEAR_REGNO_REG_SET (bb_live_regs, regno + j);
3978 /* Recompute REG_BASIC_BLOCK as we update all the other
3979 dataflow information. */
3980 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
3981 sched_reg_basic_block[regno] = current_block_num;
3982 else if (sched_reg_basic_block[regno] != current_block_num)
3983 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
3985 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
3990 /* Make the register live again. */
3991 if (regno < FIRST_PSEUDO_REGISTER)
3993 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
3996 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4001 SET_REGNO_REG_SET (bb_live_regs, regno);
4007 /* Macros and functions for keeping the priority queue sorted, and
4008 dealing with queueing and dequeueing of instructions. */
4010 #define SCHED_SORT(READY, N_READY) \
4011 do { if ((N_READY) == 2) \
4012 swap_sort (READY, N_READY); \
4013 else if ((N_READY) > 2) \
4014 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4017 /* Returns a positive value if x is preferred; returns a negative value if
4018 y is preferred. Should never return 0, since that will make the sort
4022 rank_for_schedule (x, y)
4023 const GENERIC_PTR x;
4024 const GENERIC_PTR y;
4026 rtx tmp = *(rtx *)y;
4027 rtx tmp2 = *(rtx *)x;
4029 int tmp_class, tmp2_class;
4030 int val, priority_val, spec_val, prob_val, weight_val;
4033 /* prefer insn with higher priority */
4034 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
4036 return priority_val;
4038 /* prefer an insn with smaller contribution to registers-pressure */
4039 if (!reload_completed &&
4040 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
4041 return (weight_val);
4043 /* some comparison make sense in interblock scheduling only */
4044 if (INSN_BB (tmp) != INSN_BB (tmp2))
4046 /* prefer an inblock motion on an interblock motion */
4047 if ((INSN_BB (tmp2) == target_bb) && (INSN_BB (tmp) != target_bb))
4049 if ((INSN_BB (tmp) == target_bb) && (INSN_BB (tmp2) != target_bb))
4052 /* prefer a useful motion on a speculative one */
4053 if ((spec_val = IS_SPECULATIVE_INSN (tmp) - IS_SPECULATIVE_INSN (tmp2)))
4056 /* prefer a more probable (speculative) insn */
4057 prob_val = INSN_PROBABILITY (tmp2) - INSN_PROBABILITY (tmp);
4062 /* compare insns based on their relation to the last-scheduled-insn */
4063 if (last_scheduled_insn)
4065 /* Classify the instructions into three classes:
4066 1) Data dependent on last schedule insn.
4067 2) Anti/Output dependent on last scheduled insn.
4068 3) Independent of last scheduled insn, or has latency of one.
4069 Choose the insn from the highest numbered class if different. */
4070 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
4071 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
4073 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4078 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
4079 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
4081 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4086 if ((val = tmp2_class - tmp_class))
4090 /* If insns are equally good, sort by INSN_LUID (original insn order),
4091 so that we make the sort stable. This minimizes instruction movement,
4092 thus minimizing sched's effect on debugging and cross-jumping. */
4093 return INSN_LUID (tmp) - INSN_LUID (tmp2);
4096 /* Resort the array A in which only element at index N may be out of order. */
4098 HAIFA_INLINE static void
4103 rtx insn = a[n - 1];
4106 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
4114 static int max_priority;
4116 /* Add INSN to the insn queue so that it can be executed at least
4117 N_CYCLES after the currently executing insn. Preserve insns
4118 chain for debugging purposes. */
4120 HAIFA_INLINE static void
4121 queue_insn (insn, n_cycles)
4125 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
4126 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
4127 insn_queue[next_q] = link;
4130 if (sched_verbose >= 2)
4132 fprintf (dump, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn));
4134 if (INSN_BB (insn) != target_bb)
4135 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
4137 fprintf (dump, "queued for %d cycles.\n", n_cycles);
4142 /* Return nonzero if PAT is the pattern of an insn which makes a
4145 HAIFA_INLINE static int
4146 birthing_insn_p (pat)
4151 if (reload_completed == 1)
4154 if (GET_CODE (pat) == SET
4155 && GET_CODE (SET_DEST (pat)) == REG)
4157 rtx dest = SET_DEST (pat);
4158 int i = REGNO (dest);
4160 /* It would be more accurate to use refers_to_regno_p or
4161 reg_mentioned_p to determine when the dest is not live before this
4164 if (REGNO_REG_SET_P (bb_live_regs, i))
4165 return (REG_N_SETS (i) == 1);
4169 if (GET_CODE (pat) == PARALLEL)
4171 for (j = 0; j < XVECLEN (pat, 0); j++)
4172 if (birthing_insn_p (XVECEXP (pat, 0, j)))
4178 /* PREV is an insn that is ready to execute. Adjust its priority if that
4179 will help shorten register lifetimes. */
4181 HAIFA_INLINE static void
4182 adjust_priority (prev)
4185 /* Trying to shorten register lives after reload has completed
4186 is useless and wrong. It gives inaccurate schedules. */
4187 if (reload_completed == 0)
4192 /* ??? This code has no effect, because REG_DEAD notes are removed
4193 before we ever get here. */
4194 for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
4195 if (REG_NOTE_KIND (note) == REG_DEAD)
4198 /* Defer scheduling insns which kill registers, since that
4199 shortens register lives. Prefer scheduling insns which
4200 make registers live for the same reason. */
4204 INSN_PRIORITY (prev) >>= 3;
4207 INSN_PRIORITY (prev) >>= 2;
4211 INSN_PRIORITY (prev) >>= 1;
4214 if (birthing_insn_p (PATTERN (prev)))
4216 int max = max_priority;
4218 if (max > INSN_PRIORITY (prev))
4219 INSN_PRIORITY (prev) = max;
4223 #ifdef ADJUST_PRIORITY
4224 ADJUST_PRIORITY (prev);
4229 /* INSN is the "currently executing insn". Launch each insn which was
4230 waiting on INSN. READY is a vector of insns which are ready to fire.
4231 N_READY is the number of elements in READY. CLOCK is the current
4235 schedule_insn (insn, ready, n_ready, clock)
4244 unit = insn_unit (insn);
4246 if (sched_verbose >= 2)
4248 fprintf (dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ", INSN_UID (insn));
4249 insn_print_units (insn);
4250 fprintf (dump, "\n");
4253 if (sched_verbose && unit == -1)
4254 visualize_no_unit (insn);
4256 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
4257 schedule_unit (unit, insn, clock);
4259 if (INSN_DEPEND (insn) == 0)
4262 /* This is used by the function adjust_priority above. */
4264 max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
4266 max_priority = INSN_PRIORITY (insn);
4268 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
4270 rtx next = XEXP (link, 0);
4271 int cost = insn_cost (insn, link, next);
4273 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
4275 if ((INSN_DEP_COUNT (next) -= 1) == 0)
4277 int effective_cost = INSN_TICK (next) - clock;
4279 /* For speculative insns, before inserting to ready/queue,
4280 check live, exception-free, and issue-delay */
4281 if (INSN_BB (next) != target_bb
4282 && (!IS_VALID (INSN_BB (next))
4284 || (IS_SPECULATIVE_INSN (next)
4285 && (insn_issue_delay (next) > 3
4286 || !check_live (next, INSN_BB (next))
4287 || !is_exception_free (next, INSN_BB (next), target_bb)))))
4290 if (sched_verbose >= 2)
4292 fprintf (dump, ";;\t\tdependences resolved: insn %d ", INSN_UID (next));
4294 if (current_nr_blocks > 1 && INSN_BB (next) != target_bb)
4295 fprintf (dump, "/b%d ", INSN_BLOCK (next));
4297 if (effective_cost <= 1)
4298 fprintf (dump, "into ready\n");
4300 fprintf (dump, "into queue with cost=%d\n", effective_cost);
4303 /* Adjust the priority of NEXT and either put it on the ready
4304 list or queue it. */
4305 adjust_priority (next);
4306 if (effective_cost <= 1)
4307 ready[n_ready++] = next;
4309 queue_insn (next, effective_cost);
4317 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4321 create_reg_dead_note (reg, insn)
4326 /* The number of registers killed after scheduling must be the same as the
4327 number of registers killed before scheduling. The number of REG_DEAD
4328 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4329 might become one DImode hard register REG_DEAD note, but the number of
4330 registers killed will be conserved.
4332 We carefully remove REG_DEAD notes from the dead_notes list, so that
4333 there will be none left at the end. If we run out early, then there
4334 is a bug somewhere in flow, combine and/or sched. */
4336 if (dead_notes == 0)
4338 if (current_nr_blocks <= 1)
4341 link = alloc_EXPR_LIST (REG_DEAD, NULL_RTX, NULL_RTX);
4345 /* Number of regs killed by REG. */
4346 int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
4347 : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
4348 /* Number of regs killed by REG_DEAD notes taken off the list. */
4352 reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4353 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4354 GET_MODE (XEXP (link, 0))));
4355 while (reg_note_regs < regs_killed)
4357 link = XEXP (link, 1);
4359 /* LINK might be zero if we killed more registers after scheduling
4360 than before, and the last hard register we kill is actually
4363 This is normal for interblock scheduling, so deal with it in
4364 that case, else abort. */
4365 if (link == NULL_RTX && current_nr_blocks <= 1)
4367 else if (link == NULL_RTX)
4368 link = alloc_EXPR_LIST (REG_DEAD, gen_rtx_REG (word_mode, 0),
4371 reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4372 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4373 GET_MODE (XEXP (link, 0))));
4375 dead_notes = XEXP (link, 1);
4377 /* If we took too many regs kills off, put the extra ones back. */
4378 while (reg_note_regs > regs_killed)
4380 rtx temp_reg, temp_link;
4382 temp_reg = gen_rtx_REG (word_mode, 0);
4383 temp_link = alloc_EXPR_LIST (REG_DEAD, temp_reg, dead_notes);
4384 dead_notes = temp_link;
4389 XEXP (link, 0) = reg;
4390 XEXP (link, 1) = REG_NOTES (insn);
4391 REG_NOTES (insn) = link;
4394 /* Subroutine on attach_deaths_insn--handles the recursive search
4395 through INSN. If SET_P is true, then x is being modified by the insn. */
4398 attach_deaths (x, insn, set_p)
4405 register enum rtx_code code;
4411 code = GET_CODE (x);
4423 /* Get rid of the easy cases first. */
4428 /* If the register dies in this insn, queue that note, and mark
4429 this register as needing to die. */
4430 /* This code is very similar to mark_used_1 (if set_p is false)
4431 and mark_set_1 (if set_p is true) in flow.c. */
4441 all_needed = some_needed = REGNO_REG_SET_P (old_live_regs, regno);
4442 if (regno < FIRST_PSEUDO_REGISTER)
4446 n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4449 int needed = (REGNO_REG_SET_P (old_live_regs, regno + n));
4450 some_needed |= needed;
4451 all_needed &= needed;
4455 /* If it wasn't live before we started, then add a REG_DEAD note.
4456 We must check the previous lifetime info not the current info,
4457 because we may have to execute this code several times, e.g.
4458 once for a clobber (which doesn't add a note) and later
4459 for a use (which does add a note).
4461 Always make the register live. We must do this even if it was
4462 live before, because this may be an insn which sets and uses
4463 the same register, in which case the register has already been
4464 killed, so we must make it live again.
4466 Global registers are always live, and should never have a REG_DEAD
4467 note added for them, so none of the code below applies to them. */
4469 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
4471 /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
4472 STACK_POINTER_REGNUM, since these are always considered to be
4473 live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
4474 if (regno != FRAME_POINTER_REGNUM
4475 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4476 && ! (regno == HARD_FRAME_POINTER_REGNUM)
4478 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4479 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
4481 && regno != STACK_POINTER_REGNUM)
4483 if (! all_needed && ! dead_or_set_p (insn, x))
4485 /* Check for the case where the register dying partially
4486 overlaps the register set by this insn. */
4487 if (regno < FIRST_PSEUDO_REGISTER
4488 && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
4490 int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4492 some_needed |= dead_or_set_regno_p (insn, regno + n);
4495 /* If none of the words in X is needed, make a REG_DEAD
4496 note. Otherwise, we must make partial REG_DEAD
4499 create_reg_dead_note (x, insn);
4504 /* Don't make a REG_DEAD note for a part of a
4505 register that is set in the insn. */
4506 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
4508 if (! REGNO_REG_SET_P (old_live_regs, regno+i)
4509 && ! dead_or_set_regno_p (insn, regno + i))
4510 create_reg_dead_note (gen_rtx_REG (reg_raw_mode[regno + i],
4517 if (regno < FIRST_PSEUDO_REGISTER)
4519 int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
4522 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4527 /* Recompute REG_BASIC_BLOCK as we update all the other
4528 dataflow information. */
4529 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
4530 sched_reg_basic_block[regno] = current_block_num;
4531 else if (sched_reg_basic_block[regno] != current_block_num)
4532 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
4534 SET_REGNO_REG_SET (bb_live_regs, regno);
4541 /* Handle tail-recursive case. */
4542 attach_deaths (XEXP (x, 0), insn, 0);
4546 attach_deaths (SUBREG_REG (x), insn,
4547 set_p && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4549 || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4550 == GET_MODE_SIZE (GET_MODE ((x))))));
4553 case STRICT_LOW_PART:
4554 attach_deaths (XEXP (x, 0), insn, 0);
4559 attach_deaths (XEXP (x, 0), insn, 0);
4560 attach_deaths (XEXP (x, 1), insn, 0);
4561 attach_deaths (XEXP (x, 2), insn, 0);
4565 /* Other cases: walk the insn. */
4566 fmt = GET_RTX_FORMAT (code);
4567 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4570 attach_deaths (XEXP (x, i), insn, 0);
4571 else if (fmt[i] == 'E')
4572 for (j = 0; j < XVECLEN (x, i); j++)
4573 attach_deaths (XVECEXP (x, i, j), insn, 0);
4578 /* After INSN has executed, add register death notes for each register
4579 that is dead after INSN. */
4582 attach_deaths_insn (insn)
4585 rtx x = PATTERN (insn);
4586 register RTX_CODE code = GET_CODE (x);
4591 attach_deaths (SET_SRC (x), insn, 0);
4593 /* A register might die here even if it is the destination, e.g.
4594 it is the target of a volatile read and is otherwise unused.
4595 Hence we must always call attach_deaths for the SET_DEST. */
4596 attach_deaths (SET_DEST (x), insn, 1);
4598 else if (code == PARALLEL)
4601 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4603 code = GET_CODE (XVECEXP (x, 0, i));
4606 attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
4608 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
4610 /* Flow does not add REG_DEAD notes to registers that die in
4611 clobbers, so we can't either. */
4612 else if (code != CLOBBER)
4613 attach_deaths (XVECEXP (x, 0, i), insn, 0);
4616 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4617 MEM being clobbered, just like flow. */
4618 else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == MEM)
4619 attach_deaths (XEXP (XEXP (x, 0), 0), insn, 0);
4620 /* Otherwise don't add a death note to things being clobbered. */
4621 else if (code != CLOBBER)
4622 attach_deaths (x, insn, 0);
4624 /* Make death notes for things used in the called function. */
4625 if (GET_CODE (insn) == CALL_INSN)
4626 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
4627 attach_deaths (XEXP (XEXP (link, 0), 0), insn,
4628 GET_CODE (XEXP (link, 0)) == CLOBBER);
4631 /* functions for handlnig of notes */
4633 /* Delete notes beginning with INSN and put them in the chain
4634 of notes ended by NOTE_LIST.
4635 Returns the insn following the notes. */
4638 unlink_other_notes (insn, tail)
4641 rtx prev = PREV_INSN (insn);
4643 while (insn != tail && GET_CODE (insn) == NOTE)
4645 rtx next = NEXT_INSN (insn);
4646 /* Delete the note from its current position. */
4648 NEXT_INSN (prev) = next;
4650 PREV_INSN (next) = prev;
4652 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4653 immediately after the call they follow. We use a fake
4654 (REG_DEAD (const_int -1)) note to remember them.
4655 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4656 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
4657 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
4658 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
4659 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
4660 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
4662 /* Insert the note at the end of the notes list. */
4663 PREV_INSN (insn) = note_list;
4665 NEXT_INSN (note_list) = insn;
4674 /* Delete line notes beginning with INSN. Record line-number notes so
4675 they can be reused. Returns the insn following the notes. */
4678 unlink_line_notes (insn, tail)
4681 rtx prev = PREV_INSN (insn);
4683 while (insn != tail && GET_CODE (insn) == NOTE)
4685 rtx next = NEXT_INSN (insn);
4687 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
4689 /* Delete the note from its current position. */
4691 NEXT_INSN (prev) = next;
4693 PREV_INSN (next) = prev;
4695 /* Record line-number notes so they can be reused. */
4696 LINE_NOTE (insn) = insn;
4706 /* Return the head and tail pointers of BB. */
4708 HAIFA_INLINE static void
4709 get_block_head_tail (bb, headp, tailp)
4719 b = BB_TO_BLOCK (bb);
4721 /* HEAD and TAIL delimit the basic block being scheduled. */
4722 head = basic_block_head[b];
4723 tail = basic_block_end[b];
4725 /* Don't include any notes or labels at the beginning of the
4726 basic block, or notes at the ends of basic blocks. */
4727 while (head != tail)
4729 if (GET_CODE (head) == NOTE)
4730 head = NEXT_INSN (head);
4731 else if (GET_CODE (tail) == NOTE)
4732 tail = PREV_INSN (tail);
4733 else if (GET_CODE (head) == CODE_LABEL)
4734 head = NEXT_INSN (head);
4743 /* Delete line notes from bb. Save them so they can be later restored
4744 (in restore_line_notes ()). */
4755 get_block_head_tail (bb, &head, &tail);
4758 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4761 next_tail = NEXT_INSN (tail);
4762 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4766 /* Farm out notes, and maybe save them in NOTE_LIST.
4767 This is needed to keep the debugger from
4768 getting completely deranged. */
4769 if (GET_CODE (insn) == NOTE)
4772 insn = unlink_line_notes (insn, next_tail);
4778 if (insn == next_tail)
4784 /* Save line number notes for each insn in bb. */
4787 save_line_notes (bb)
4793 /* We must use the true line number for the first insn in the block
4794 that was computed and saved at the start of this pass. We can't
4795 use the current line number, because scheduling of the previous
4796 block may have changed the current line number. */
4798 rtx line = line_note_head[BB_TO_BLOCK (bb)];
4801 get_block_head_tail (bb, &head, &tail);
4802 next_tail = NEXT_INSN (tail);
4804 for (insn = basic_block_head[BB_TO_BLOCK (bb)];
4806 insn = NEXT_INSN (insn))
4807 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4810 LINE_NOTE (insn) = line;
4814 /* After bb was scheduled, insert line notes into the insns list. */
4817 restore_line_notes (bb)
4820 rtx line, note, prev, new;
4821 int added_notes = 0;
4823 rtx head, next_tail, insn;
4825 b = BB_TO_BLOCK (bb);
4827 head = basic_block_head[b];
4828 next_tail = NEXT_INSN (basic_block_end[b]);
4830 /* Determine the current line-number. We want to know the current
4831 line number of the first insn of the block here, in case it is
4832 different from the true line number that was saved earlier. If
4833 different, then we need a line number note before the first insn
4834 of this block. If it happens to be the same, then we don't want to
4835 emit another line number note here. */
4836 for (line = head; line; line = PREV_INSN (line))
4837 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4840 /* Walk the insns keeping track of the current line-number and inserting
4841 the line-number notes as needed. */
4842 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4843 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4845 /* This used to emit line number notes before every non-deleted note.
4846 However, this confuses a debugger, because line notes not separated
4847 by real instructions all end up at the same address. I can find no
4848 use for line number notes before other notes, so none are emitted. */
4849 else if (GET_CODE (insn) != NOTE
4850 && (note = LINE_NOTE (insn)) != 0
4853 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
4854 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
4857 prev = PREV_INSN (insn);
4858 if (LINE_NOTE (note))
4860 /* Re-use the original line-number note. */
4861 LINE_NOTE (note) = 0;
4862 PREV_INSN (note) = prev;
4863 NEXT_INSN (prev) = note;
4864 PREV_INSN (insn) = note;
4865 NEXT_INSN (note) = insn;
4870 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
4871 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
4872 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
4875 if (sched_verbose && added_notes)
4876 fprintf (dump, ";; added %d line-number notes\n", added_notes);
4879 /* After scheduling the function, delete redundant line notes from the
4883 rm_redundant_line_notes ()
4886 rtx insn = get_insns ();
4887 int active_insn = 0;
4890 /* Walk the insns deleting redundant line-number notes. Many of these
4891 are already present. The remainder tend to occur at basic
4892 block boundaries. */
4893 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4894 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4896 /* If there are no active insns following, INSN is redundant. */
4897 if (active_insn == 0)
4900 NOTE_SOURCE_FILE (insn) = 0;
4901 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4903 /* If the line number is unchanged, LINE is redundant. */
4905 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
4906 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
4909 NOTE_SOURCE_FILE (line) = 0;
4910 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
4917 else if (!((GET_CODE (insn) == NOTE
4918 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
4919 || (GET_CODE (insn) == INSN
4920 && (GET_CODE (PATTERN (insn)) == USE
4921 || GET_CODE (PATTERN (insn)) == CLOBBER))))
4924 if (sched_verbose && notes)
4925 fprintf (dump, ";; deleted %d line-number notes\n", notes);
4928 /* Delete notes between head and tail and put them in the chain
4929 of notes ended by NOTE_LIST. */
4932 rm_other_notes (head, tail)
4940 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4943 next_tail = NEXT_INSN (tail);
4944 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4948 /* Farm out notes, and maybe save them in NOTE_LIST.
4949 This is needed to keep the debugger from
4950 getting completely deranged. */
4951 if (GET_CODE (insn) == NOTE)
4955 insn = unlink_other_notes (insn, next_tail);
4961 if (insn == next_tail)
4967 /* Constructor for `sometimes' data structure. */
4970 new_sometimes_live (regs_sometimes_live, regno, sometimes_max)
4971 struct sometimes *regs_sometimes_live;
4975 register struct sometimes *p;
4977 /* There should never be a register greater than max_regno here. If there
4978 is, it means that a define_split has created a new pseudo reg. This
4979 is not allowed, since there will not be flow info available for any
4980 new register, so catch the error here. */
4981 if (regno >= max_regno)
4984 p = ®s_sometimes_live[sometimes_max];
4987 p->calls_crossed = 0;
4989 return sometimes_max;
4992 /* Count lengths of all regs we are currently tracking,
4993 and find new registers no longer live. */
4996 finish_sometimes_live (regs_sometimes_live, sometimes_max)
4997 struct sometimes *regs_sometimes_live;
5002 for (i = 0; i < sometimes_max; i++)
5004 register struct sometimes *p = ®s_sometimes_live[i];
5005 int regno = p->regno;
5007 sched_reg_live_length[regno] += p->live_length;
5008 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5012 /* functions for computation of registers live/usage info */
5014 /* It is assumed that prior to scheduling basic_block_live_at_start (b)
5015 contains the registers that are alive at the entry to b.
5017 Two passes follow: The first pass is performed before the scheduling
5018 of a region. It scans each block of the region forward, computing
5019 the set of registers alive at the end of the basic block and
5020 discard REG_DEAD notes (done by find_pre_sched_live ()).
5022 The second path is invoked after scheduling all region blocks.
5023 It scans each block of the region backward, a block being traversed
5024 only after its succesors in the region. When the set of registers
5025 live at the end of a basic block may be changed by the scheduling
5026 (this may happen for multiple blocks region), it is computed as
5027 the union of the registers live at the start of its succesors.
5028 The last-use information is updated by inserting REG_DEAD notes.
5029 (done by find_post_sched_live ()) */
5031 /* Scan all the insns to be scheduled, removing register death notes.
5032 Register death notes end up in DEAD_NOTES.
5033 Recreate the register life information for the end of this basic
5037 find_pre_sched_live (bb)
5040 rtx insn, next_tail, head, tail;
5041 int b = BB_TO_BLOCK (bb);
5043 get_block_head_tail (bb, &head, &tail);
5044 COPY_REG_SET (bb_live_regs, basic_block_live_at_start[b]);
5045 next_tail = NEXT_INSN (tail);
5047 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5049 rtx prev, next, link;
5052 /* Handle register life information. */
5053 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
5055 /* See if the register gets born here. */
5056 /* We must check for registers being born before we check for
5057 registers dying. It is possible for a register to be born and
5058 die in the same insn, e.g. reading from a volatile memory
5059 location into an otherwise unused register. Such a register
5060 must be marked as dead after this insn. */
5061 if (GET_CODE (PATTERN (insn)) == SET
5062 || GET_CODE (PATTERN (insn)) == CLOBBER)
5064 sched_note_set (PATTERN (insn), 0);
5068 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5071 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5072 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5073 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5075 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5079 /* ??? This code is obsolete and should be deleted. It
5080 is harmless though, so we will leave it in for now. */
5081 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5082 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
5083 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5086 /* Each call cobbers (makes live) all call-clobbered regs
5087 that are not global or fixed. Note that the function-value
5088 reg is a call_clobbered reg. */
5089 if (GET_CODE (insn) == CALL_INSN)
5092 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
5093 if (call_used_regs[j] && !global_regs[j]
5096 SET_REGNO_REG_SET (bb_live_regs, j);
5100 /* Need to know what registers this insn kills. */
5101 for (prev = 0, link = REG_NOTES (insn); link; link = next)
5103 next = XEXP (link, 1);
5104 if ((REG_NOTE_KIND (link) == REG_DEAD
5105 || REG_NOTE_KIND (link) == REG_UNUSED)
5106 /* Verify that the REG_NOTE has a valid value. */
5107 && GET_CODE (XEXP (link, 0)) == REG)
5109 register int regno = REGNO (XEXP (link, 0));
5113 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5115 if (REG_NOTE_KIND (link) == REG_DEAD)
5118 XEXP (prev, 1) = next;
5120 REG_NOTES (insn) = next;
5121 XEXP (link, 1) = dead_notes;
5127 if (regno < FIRST_PSEUDO_REGISTER)
5129 int j = HARD_REGNO_NREGS (regno,
5130 GET_MODE (XEXP (link, 0)));
5133 CLEAR_REGNO_REG_SET (bb_live_regs, regno+j);
5138 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
5146 INSN_REG_WEIGHT (insn) = reg_weight;
5150 /* Update register life and usage information for block bb
5151 after scheduling. Put register dead notes back in the code. */
5154 find_post_sched_live (bb)
5161 rtx head, tail, prev_head, next_tail;
5163 register struct sometimes *regs_sometimes_live;
5165 b = BB_TO_BLOCK (bb);
5167 /* compute live regs at the end of bb as a function of its successors. */
5168 if (current_nr_blocks > 1)
5173 first_edge = e = OUT_EDGES (b);
5174 CLEAR_REG_SET (bb_live_regs);
5181 b_succ = TO_BLOCK (e);
5182 IOR_REG_SET (bb_live_regs, basic_block_live_at_start[b_succ]);
5185 while (e != first_edge);
5188 get_block_head_tail (bb, &head, &tail);
5189 next_tail = NEXT_INSN (tail);
5190 prev_head = PREV_INSN (head);
5192 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, i,
5194 sched_reg_basic_block[i] = REG_BLOCK_GLOBAL;
5197 /* if the block is empty, same regs are alive at its end and its start.
5198 since this is not guaranteed after interblock scheduling, make sure they
5199 are truly identical. */
5200 if (NEXT_INSN (prev_head) == tail
5201 && (GET_RTX_CLASS (GET_CODE (tail)) != 'i'))
5203 if (current_nr_blocks > 1)
5204 COPY_REG_SET (basic_block_live_at_start[b], bb_live_regs);
5209 b = BB_TO_BLOCK (bb);
5210 current_block_num = b;
5212 /* Keep track of register lives. */
5213 old_live_regs = ALLOCA_REG_SET ();
5215 = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
5218 /* initiate "sometimes" data, starting with registers live at end */
5220 COPY_REG_SET (old_live_regs, bb_live_regs);
5221 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, 0, j,
5224 = new_sometimes_live (regs_sometimes_live,
5228 /* scan insns back, computing regs live info */
5229 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
5231 /* First we kill registers set by this insn, and then we
5232 make registers used by this insn live. This is the opposite
5233 order used above because we are traversing the instructions
5236 /* Strictly speaking, we should scan REG_UNUSED notes and make
5237 every register mentioned there live, however, we will just
5238 kill them again immediately below, so there doesn't seem to
5239 be any reason why we bother to do this. */
5241 /* See if this is the last notice we must take of a register. */
5242 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5245 if (GET_CODE (PATTERN (insn)) == SET
5246 || GET_CODE (PATTERN (insn)) == CLOBBER)
5247 sched_note_set (PATTERN (insn), 1);
5248 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5250 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5251 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5252 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5253 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 1);
5256 /* This code keeps life analysis information up to date. */
5257 if (GET_CODE (insn) == CALL_INSN)
5259 register struct sometimes *p;
5261 /* A call kills all call used registers that are not
5262 global or fixed, except for those mentioned in the call
5263 pattern which will be made live again later. */
5264 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5265 if (call_used_regs[i] && ! global_regs[i]
5268 CLEAR_REGNO_REG_SET (bb_live_regs, i);
5271 /* Regs live at the time of a call instruction must not
5272 go in a register clobbered by calls. Record this for
5273 all regs now live. Note that insns which are born or
5274 die in a call do not cross a call, so this must be done
5275 after the killings (above) and before the births
5277 p = regs_sometimes_live;
5278 for (i = 0; i < sometimes_max; i++, p++)
5279 if (REGNO_REG_SET_P (bb_live_regs, p->regno))
5280 p->calls_crossed += 1;
5283 /* Make every register used live, and add REG_DEAD notes for
5284 registers which were not live before we started. */
5285 attach_deaths_insn (insn);
5287 /* Find registers now made live by that instruction. */
5288 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs, old_live_regs, 0, j,
5291 = new_sometimes_live (regs_sometimes_live,
5294 IOR_REG_SET (old_live_regs, bb_live_regs);
5296 /* Count lengths of all regs we are worrying about now,
5297 and handle registers no longer live. */
5299 for (i = 0; i < sometimes_max; i++)
5301 register struct sometimes *p = ®s_sometimes_live[i];
5302 int regno = p->regno;
5304 p->live_length += 1;
5306 if (!REGNO_REG_SET_P (bb_live_regs, regno))
5308 /* This is the end of one of this register's lifetime
5309 segments. Save the lifetime info collected so far,
5310 and clear its bit in the old_live_regs entry. */
5311 sched_reg_live_length[regno] += p->live_length;
5312 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5313 CLEAR_REGNO_REG_SET (old_live_regs, p->regno);
5315 /* Delete the reg_sometimes_live entry for this reg by
5316 copying the last entry over top of it. */
5317 *p = regs_sometimes_live[--sometimes_max];
5318 /* ...and decrement i so that this newly copied entry
5319 will be processed. */
5325 finish_sometimes_live (regs_sometimes_live, sometimes_max);
5327 /* In interblock scheduling, basic_block_live_at_start may have changed. */
5328 if (current_nr_blocks > 1)
5329 COPY_REG_SET (basic_block_live_at_start[b], bb_live_regs);
5332 FREE_REG_SET (old_live_regs);
5333 } /* find_post_sched_live */
5335 /* After scheduling the subroutine, restore information about uses of
5343 if (n_basic_blocks > 0)
5344 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, regno,
5346 sched_reg_basic_block[regno]
5350 for (regno = 0; regno < max_regno; regno++)
5351 if (sched_reg_live_length[regno])
5355 if (REG_LIVE_LENGTH (regno) > sched_reg_live_length[regno])
5357 ";; register %d life shortened from %d to %d\n",
5358 regno, REG_LIVE_LENGTH (regno),
5359 sched_reg_live_length[regno]);
5360 /* Negative values are special; don't overwrite the current
5361 reg_live_length value if it is negative. */
5362 else if (REG_LIVE_LENGTH (regno) < sched_reg_live_length[regno]
5363 && REG_LIVE_LENGTH (regno) >= 0)
5365 ";; register %d life extended from %d to %d\n",
5366 regno, REG_LIVE_LENGTH (regno),
5367 sched_reg_live_length[regno]);
5369 if (!REG_N_CALLS_CROSSED (regno)
5370 && sched_reg_n_calls_crossed[regno])
5372 ";; register %d now crosses calls\n", regno);
5373 else if (REG_N_CALLS_CROSSED (regno)
5374 && !sched_reg_n_calls_crossed[regno]
5375 && REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5377 ";; register %d no longer crosses calls\n", regno);
5379 if (REG_BASIC_BLOCK (regno) != sched_reg_basic_block[regno]
5380 && sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5381 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5383 ";; register %d changed basic block from %d to %d\n",
5384 regno, REG_BASIC_BLOCK(regno),
5385 sched_reg_basic_block[regno]);
5388 /* Negative values are special; don't overwrite the current
5389 reg_live_length value if it is negative. */
5390 if (REG_LIVE_LENGTH (regno) >= 0)
5391 REG_LIVE_LENGTH (regno) = sched_reg_live_length[regno];
5393 if (sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5394 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5395 REG_BASIC_BLOCK(regno) = sched_reg_basic_block[regno];
5397 /* We can't change the value of reg_n_calls_crossed to zero for
5398 pseudos which are live in more than one block.
5400 This is because combine might have made an optimization which
5401 invalidated basic_block_live_at_start and reg_n_calls_crossed,
5402 but it does not update them. If we update reg_n_calls_crossed
5403 here, the two variables are now inconsistent, and this might
5404 confuse the caller-save code into saving a register that doesn't
5405 need to be saved. This is only a problem when we zero calls
5406 crossed for a pseudo live in multiple basic blocks.
5408 Alternatively, we could try to correctly update basic block live
5409 at start here in sched, but that seems complicated.
5411 Note: it is possible that a global register became local, as result
5412 of interblock motion, but will remain marked as a global register. */
5413 if (sched_reg_n_calls_crossed[regno]
5414 || REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5415 REG_N_CALLS_CROSSED (regno) = sched_reg_n_calls_crossed[regno];
5420 /* Scheduling clock, modified in schedule_block() and queue_to_ready () */
5421 static int clock_var;
5423 /* Move insns that became ready to fire from queue to ready list. */
5426 queue_to_ready (ready, n_ready)
5433 q_ptr = NEXT_Q (q_ptr);
5435 /* Add all pending insns that can be scheduled without stalls to the
5437 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
5440 insn = XEXP (link, 0);
5443 if (sched_verbose >= 2)
5444 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5446 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5447 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5449 ready[n_ready++] = insn;
5450 if (sched_verbose >= 2)
5451 fprintf (dump, "moving to ready without stalls\n");
5453 insn_queue[q_ptr] = 0;
5455 /* If there are no ready insns, stall until one is ready and add all
5456 of the pending insns at that point to the ready list. */
5459 register int stalls;
5461 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
5463 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
5465 for (; link; link = XEXP (link, 1))
5467 insn = XEXP (link, 0);
5470 if (sched_verbose >= 2)
5471 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5473 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5474 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5476 ready[n_ready++] = insn;
5477 if (sched_verbose >= 2)
5478 fprintf (dump, "moving to ready with %d stalls\n", stalls);
5480 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
5487 if (sched_verbose && stalls)
5488 visualize_stall_cycles (BB_TO_BLOCK (target_bb), stalls);
5489 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
5490 clock_var += stalls;
5495 /* Print the ready list for debugging purposes. Callable from debugger. */
5498 debug_ready_list (ready, n_ready)
5504 for (i = 0; i < n_ready; i++)
5506 fprintf (dump, " %d", INSN_UID (ready[i]));
5507 if (current_nr_blocks > 1 && INSN_BB (ready[i]) != target_bb)
5508 fprintf (dump, "/b%d", INSN_BLOCK (ready[i]));
5510 fprintf (dump, "\n");
5513 /* Print names of units on which insn can/should execute, for debugging. */
5516 insn_print_units (insn)
5520 int unit = insn_unit (insn);
5523 fprintf (dump, "none");
5525 fprintf (dump, "%s", function_units[unit].name);
5528 fprintf (dump, "[");
5529 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
5532 fprintf (dump, "%s", function_units[i].name);
5534 fprintf (dump, " ");
5536 fprintf (dump, "]");
5540 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5541 of a basic block. If more lines are needed, table is splitted to two.
5542 n_visual_lines is the number of lines printed so far for a block.
5543 visual_tbl contains the block visualization info.
5544 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5545 #define MAX_VISUAL_LINES 100
5550 rtx vis_no_unit[10];
5552 /* Finds units that are in use in this fuction. Required only
5553 for visualization. */
5556 init_target_units ()
5561 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
5563 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5566 unit = insn_unit (insn);
5569 target_units |= ~unit;
5571 target_units |= (1 << unit);
5575 /* Return the length of the visualization table */
5578 get_visual_tbl_length ()
5584 /* compute length of one field in line */
5585 s = (char *) alloca (INSN_LEN + 5);
5586 sprintf (s, " %33s", "uname");
5589 /* compute length of one line */
5592 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5593 if (function_units[unit].bitmask & target_units)
5594 for (i = 0; i < function_units[unit].multiplicity; i++)
5597 n += strlen ("\n") + 2;
5599 /* compute length of visualization string */
5600 return (MAX_VISUAL_LINES * n);
5603 /* Init block visualization debugging info */
5606 init_block_visualization ()
5608 strcpy (visual_tbl, "");
5616 safe_concat (buf, cur, str)
5621 char *end = buf + BUF_LEN - 2; /* leave room for null */
5630 while (cur < end && (c = *str++) != '\0')
5637 /* This recognizes rtx, I classified as expressions. These are always */
5638 /* represent some action on values or results of other expression, */
5639 /* that may be stored in objects representing values. */
5642 print_exp (buf, x, verbose)
5650 char *fun = (char *)0;
5655 for (i = 0; i < 4; i++)
5661 switch (GET_CODE (x))
5664 op[0] = XEXP (x, 0);
5666 op[1] = XEXP (x, 1);
5669 op[0] = XEXP (x, 0);
5671 op[1] = XEXP (x, 1);
5675 op[0] = XEXP (x, 0);
5677 op[1] = XEXP (x, 1);
5681 op[0] = XEXP (x, 0);
5682 op[1] = XEXP (x, 1);
5686 op[0] = XEXP (x, 0);
5689 op[0] = XEXP (x, 0);
5691 op[1] = XEXP (x, 1);
5694 op[0] = XEXP (x, 0);
5696 op[1] = XEXP (x, 1);
5700 op[0] = XEXP (x, 0);
5701 op[1] = XEXP (x, 1);
5704 op[0] = XEXP (x, 0);
5706 op[1] = XEXP (x, 1);
5710 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);
5738 op[0] = XEXP (x, 0);
5740 op[1] = XEXP (x, 1);
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);
5779 op[0] = XEXP (x, 0);
5783 op[0] = XEXP (x, 0);
5787 op[0] = XEXP (x, 0);
5790 op[0] = XEXP (x, 0);
5792 op[1] = XEXP (x, 1);
5795 op[0] = XEXP (x, 0);
5797 op[1] = XEXP (x, 1);
5800 op[0] = XEXP (x, 0);
5802 op[1] = XEXP (x, 1);
5806 op[0] = XEXP (x, 0);
5807 op[1] = XEXP (x, 1);
5810 op[0] = XEXP (x, 0);
5812 op[1] = XEXP (x, 1);
5816 op[0] = XEXP (x, 0);
5817 op[1] = XEXP (x, 1);
5820 op[0] = XEXP (x, 0);
5822 op[1] = XEXP (x, 1);
5826 op[0] = XEXP (x, 0);
5827 op[1] = XEXP (x, 1);
5830 op[0] = XEXP (x, 0);
5832 op[1] = XEXP (x, 1);
5836 op[0] = XEXP (x, 0);
5837 op[1] = XEXP (x, 1);
5840 fun = (verbose) ? "sign_extract" : "sxt";
5841 op[0] = XEXP (x, 0);
5842 op[1] = XEXP (x, 1);
5843 op[2] = XEXP (x, 2);
5846 fun = (verbose) ? "zero_extract" : "zxt";
5847 op[0] = XEXP (x, 0);
5848 op[1] = XEXP (x, 1);
5849 op[2] = XEXP (x, 2);
5852 fun = (verbose) ? "sign_extend" : "sxn";
5853 op[0] = XEXP (x, 0);
5856 fun = (verbose) ? "zero_extend" : "zxn";
5857 op[0] = XEXP (x, 0);
5860 fun = (verbose) ? "float_extend" : "fxn";
5861 op[0] = XEXP (x, 0);
5864 fun = (verbose) ? "trunc" : "trn";
5865 op[0] = XEXP (x, 0);
5867 case FLOAT_TRUNCATE:
5868 fun = (verbose) ? "float_trunc" : "ftr";
5869 op[0] = XEXP (x, 0);
5872 fun = (verbose) ? "float" : "flt";
5873 op[0] = XEXP (x, 0);
5875 case UNSIGNED_FLOAT:
5876 fun = (verbose) ? "uns_float" : "ufl";
5877 op[0] = XEXP (x, 0);
5881 op[0] = XEXP (x, 0);
5884 fun = (verbose) ? "uns_fix" : "ufx";
5885 op[0] = XEXP (x, 0);
5889 op[0] = XEXP (x, 0);
5893 op[0] = XEXP (x, 0);
5896 op[0] = XEXP (x, 0);
5900 op[0] = XEXP (x, 0);
5905 op[0] = XEXP (x, 0);
5909 op[1] = XEXP (x, 1);
5914 op[0] = XEXP (x, 0);
5916 op[1] = XEXP (x, 1);
5918 op[2] = XEXP (x, 2);
5923 op[0] = TRAP_CONDITION (x);
5926 case UNSPEC_VOLATILE:
5928 cur = safe_concat (buf, cur, "unspec");
5929 if (GET_CODE (x) == UNSPEC_VOLATILE)
5930 cur = safe_concat (buf, cur, "/v");
5931 cur = safe_concat (buf, cur, "[");
5933 for (i = 0; i < XVECLEN (x, 0); i++)
5935 print_pattern (tmp, XVECEXP (x, 0, i), verbose);
5936 cur = safe_concat (buf, cur, sep);
5937 cur = safe_concat (buf, cur, tmp);
5940 cur = safe_concat (buf, cur, "] ");
5941 sprintf (tmp, "%d", XINT (x, 1));
5942 cur = safe_concat (buf, cur, tmp);
5946 /* if (verbose) debug_rtx (x); */
5947 st[0] = GET_RTX_NAME (GET_CODE (x));
5951 /* Print this as a function? */
5954 cur = safe_concat (buf, cur, fun);
5955 cur = safe_concat (buf, cur, "(");
5958 for (i = 0; i < 4; i++)
5961 cur = safe_concat (buf, cur, st[i]);
5966 cur = safe_concat (buf, cur, ",");
5968 print_value (tmp, op[i], verbose);
5969 cur = safe_concat (buf, cur, tmp);
5974 cur = safe_concat (buf, cur, ")");
5977 /* Prints rtxes, i customly classified as values. They're constants, */
5978 /* registers, labels, symbols and memory accesses. */
5981 print_value (buf, x, verbose)
5989 switch (GET_CODE (x))
5992 sprintf (t, "0x%lx", (long)INTVAL (x));
5993 cur = safe_concat (buf, cur, t);
5996 sprintf (t, "<0x%lx,0x%lx>", (long)XWINT (x, 2), (long)XWINT (x, 3));
5997 cur = safe_concat (buf, cur, t);
6000 cur = safe_concat (buf, cur, "\"");
6001 cur = safe_concat (buf, cur, XSTR (x, 0));
6002 cur = safe_concat (buf, cur, "\"");
6005 cur = safe_concat (buf, cur, "`");
6006 cur = safe_concat (buf, cur, XSTR (x, 0));
6007 cur = safe_concat (buf, cur, "'");
6010 sprintf (t, "L%d", INSN_UID (XEXP (x, 0)));
6011 cur = safe_concat (buf, cur, t);
6014 print_value (t, XEXP (x, 0), verbose);
6015 cur = safe_concat (buf, cur, "const(");
6016 cur = safe_concat (buf, cur, t);
6017 cur = safe_concat (buf, cur, ")");
6020 print_value (t, XEXP (x, 0), verbose);
6021 cur = safe_concat (buf, cur, "high(");
6022 cur = safe_concat (buf, cur, t);
6023 cur = safe_concat (buf, cur, ")");
6026 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
6028 int c = reg_names[ REGNO (x) ][0];
6029 if (c >= '0' && c <= '9')
6030 cur = safe_concat (buf, cur, "%");
6032 cur = safe_concat (buf, cur, reg_names[ REGNO (x) ]);
6036 sprintf (t, "r%d", REGNO (x));
6037 cur = safe_concat (buf, cur, t);
6041 print_value (t, SUBREG_REG (x), verbose);
6042 cur = safe_concat (buf, cur, t);
6043 sprintf (t, "#%d", SUBREG_WORD (x));
6044 cur = safe_concat (buf, cur, t);
6047 cur = safe_concat (buf, cur, "scratch");
6050 cur = safe_concat (buf, cur, "cc0");
6053 cur = safe_concat (buf, cur, "pc");
6056 print_value (t, XEXP (x, 0), verbose);
6057 cur = safe_concat (buf, cur, "[");
6058 cur = safe_concat (buf, cur, t);
6059 cur = safe_concat (buf, cur, "]");
6062 print_exp (t, x, verbose);
6063 cur = safe_concat (buf, cur, t);
6068 /* The next step in insn detalization, its pattern recognition */
6071 print_pattern (buf, x, verbose)
6076 char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
6078 switch (GET_CODE (x))
6081 print_value (t1, SET_DEST (x), verbose);
6082 print_value (t2, SET_SRC (x), verbose);
6083 sprintf (buf, "%s=%s", t1, t2);
6086 sprintf (buf, "return");
6089 print_exp (buf, x, verbose);
6092 print_value (t1, XEXP (x, 0), verbose);
6093 sprintf (buf, "clobber %s", t1);
6096 print_value (t1, XEXP (x, 0), verbose);
6097 sprintf (buf, "use %s", t1);
6104 for (i = 0; i < XVECLEN (x, 0); i++)
6106 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6107 sprintf (t3, "%s%s;", t1, t2);
6110 sprintf (buf, "%s}", t1);
6117 sprintf (t1, "%%{");
6118 for (i = 0; i < XVECLEN (x, 0); i++)
6120 print_insn (t2, XVECEXP (x, 0, i), verbose);
6121 sprintf (t3, "%s%s;", t1, t2);
6124 sprintf (buf, "%s%%}", t1);
6128 sprintf (buf, "asm {%s}", XSTR (x, 0));
6133 print_value (buf, XEXP (x, 0), verbose);
6136 print_value (t1, TRAP_CONDITION (x), verbose);
6137 sprintf (buf, "trap_if %s", t1);
6143 sprintf (t1, "unspec{");
6144 for (i = 0; i < XVECLEN (x, 0); i++)
6146 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6147 sprintf (t3, "%s%s;", t1, t2);
6150 sprintf (buf, "%s}", t1);
6153 case UNSPEC_VOLATILE:
6157 sprintf (t1, "unspec/v{");
6158 for (i = 0; i < XVECLEN (x, 0); i++)
6160 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6161 sprintf (t3, "%s%s;", t1, t2);
6164 sprintf (buf, "%s}", t1);
6168 print_value (buf, x, verbose);
6170 } /* print_pattern */
6172 /* This is the main function in rtl visualization mechanism. It
6173 accepts an rtx and tries to recognize it as an insn, then prints it
6174 properly in human readable form, resembling assembler mnemonics. */
6175 /* For every insn it prints its UID and BB the insn belongs */
6176 /* too. (probably the last "option" should be extended somehow, since */
6177 /* it depends now on sched.c inner variables ...) */
6180 print_insn (buf, x, verbose)
6188 switch (GET_CODE (x))
6191 print_pattern (t, PATTERN (x), verbose);
6193 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (x),
6196 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6199 print_pattern (t, PATTERN (x), verbose);
6201 sprintf (buf, "b%d: i% 4d: jump %s", INSN_BB (x),
6204 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6208 if (GET_CODE (x) == PARALLEL)
6210 x = XVECEXP (x, 0, 0);
6211 print_pattern (t, x, verbose);
6214 strcpy (t, "call <...>");
6216 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (insn),
6217 INSN_UID (insn), t);
6219 sprintf (buf, "%-4d %s", INSN_UID (insn), t);
6222 sprintf (buf, "L%d:", INSN_UID (x));
6225 sprintf (buf, "i% 4d: barrier", INSN_UID (x));
6228 if (NOTE_LINE_NUMBER (x) > 0)
6229 sprintf (buf, "%4d note \"%s\" %d", INSN_UID (x),
6230 NOTE_SOURCE_FILE (x), NOTE_LINE_NUMBER (x));
6232 sprintf (buf, "%4d %s", INSN_UID (x),
6233 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x)));
6238 sprintf (buf, "Not an INSN at all\n");
6242 sprintf (buf, "i%-4d <What?>", INSN_UID (x));
6247 print_insn_chain (rtx_first)
6250 register rtx tmp_rtx;
6253 strcpy (str, "(nil)\n");
6255 switch (GET_CODE (rtx_first))
6263 for (tmp_rtx = rtx_first; tmp_rtx != NULL;
6264 tmp_rtx = NEXT_INSN (tmp_rtx))
6266 print_insn (str, tmp_rtx, 0);
6267 printf ("%s\n", str);
6271 print_insn (str, rtx_first, 0);
6272 printf ("%s\n", str);
6274 } /* print_insn_chain */
6276 /* Print visualization debugging info */
6279 print_block_visualization (b, s)
6286 fprintf (dump, "\n;; ==================== scheduling visualization for block %d %s \n", b, s);
6288 /* Print names of units */
6289 fprintf (dump, ";; %-8s", "clock");
6290 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6291 if (function_units[unit].bitmask & target_units)
6292 for (i = 0; i < function_units[unit].multiplicity; i++)
6293 fprintf (dump, " %-33s", function_units[unit].name);
6294 fprintf (dump, " %-8s\n", "no-unit");
6296 fprintf (dump, ";; %-8s", "=====");
6297 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6298 if (function_units[unit].bitmask & target_units)
6299 for (i = 0; i < function_units[unit].multiplicity; i++)
6300 fprintf (dump, " %-33s", "==============================");
6301 fprintf (dump, " %-8s\n", "=======");
6303 /* Print insns in each cycle */
6304 fprintf (dump, "%s\n", visual_tbl);
6307 /* Print insns in the 'no_unit' column of visualization */
6310 visualize_no_unit (insn)
6313 vis_no_unit[n_vis_no_unit] = insn;
6317 /* Print insns scheduled in clock, for visualization. */
6320 visualize_scheduled_insns (b, clock)
6325 /* if no more room, split table into two */
6326 if (n_visual_lines >= MAX_VISUAL_LINES)
6328 print_block_visualization (b, "(incomplete)");
6329 init_block_visualization ();
6334 sprintf (visual_tbl + strlen (visual_tbl), ";; %-8d", clock);
6335 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6336 if (function_units[unit].bitmask & target_units)
6337 for (i = 0; i < function_units[unit].multiplicity; i++)
6339 int instance = unit + i * FUNCTION_UNITS_SIZE;
6340 rtx insn = unit_last_insn[instance];
6342 /* print insns that still keep the unit busy */
6344 actual_hazard_this_instance (unit, instance, insn, clock, 0))
6347 print_insn (str, insn, 0);
6348 str[INSN_LEN] = '\0';
6349 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", str);
6352 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", "------------------------------");
6355 /* print insns that are not assigned to any unit */
6356 for (i = 0; i < n_vis_no_unit; i++)
6357 sprintf (visual_tbl + strlen (visual_tbl), " %-8d",
6358 INSN_UID (vis_no_unit[i]));
6361 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6364 /* Print stalled cycles */
6367 visualize_stall_cycles (b, stalls)
6372 /* if no more room, split table into two */
6373 if (n_visual_lines >= MAX_VISUAL_LINES)
6375 print_block_visualization (b, "(incomplete)");
6376 init_block_visualization ();
6381 sprintf (visual_tbl + strlen (visual_tbl), ";; ");
6382 for (i = 0; i < stalls; i++)
6383 sprintf (visual_tbl + strlen (visual_tbl), ".");
6384 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6387 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn */
6390 move_insn1 (insn, last)
6393 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
6394 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
6396 NEXT_INSN (insn) = NEXT_INSN (last);
6397 PREV_INSN (NEXT_INSN (last)) = insn;
6399 NEXT_INSN (last) = insn;
6400 PREV_INSN (insn) = last;
6405 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
6406 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
6407 NOTEs. The REG_DEAD note following first one is contains the saved
6408 value for NOTE_BLOCK_NUMBER which is useful for
6409 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
6410 output by the instruction scheduler. Return the new value of LAST. */
6413 reemit_notes (insn, last)
6420 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
6422 if (REG_NOTE_KIND (note) == REG_DEAD
6423 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6425 if (INTVAL (XEXP (note, 0)) == NOTE_INSN_SETJMP)
6427 retval = emit_note_after (INTVAL (XEXP (note, 0)), insn);
6428 CONST_CALL_P (retval) = CONST_CALL_P (note);
6429 remove_note (insn, note);
6430 note = XEXP (note, 1);
6434 last = emit_note_before (INTVAL (XEXP (note, 0)), last);
6435 remove_note (insn, note);
6436 note = XEXP (note, 1);
6437 NOTE_BLOCK_NUMBER (last) = INTVAL (XEXP (note, 0));
6439 remove_note (insn, note);
6445 /* Move INSN, and all insns which should be issued before it,
6446 due to SCHED_GROUP_P flag. Reemit notes if needed.
6448 Return the last insn emitted by the scheduler, which is the
6449 return value from the first call to reemit_notes. */
6452 move_insn (insn, last)
6457 /* If INSN has SCHED_GROUP_P set, then issue it and any other
6458 insns with SCHED_GROUP_P set first. */
6459 while (SCHED_GROUP_P (insn))
6461 rtx prev = PREV_INSN (insn);
6463 /* Move a SCHED_GROUP_P insn. */
6464 move_insn1 (insn, last);
6465 /* If this is the first call to reemit_notes, then record
6466 its return value. */
6467 if (retval == NULL_RTX)
6468 retval = reemit_notes (insn, insn);
6470 reemit_notes (insn, insn);
6474 /* Now move the first non SCHED_GROUP_P insn. */
6475 move_insn1 (insn, last);
6477 /* If this is the first call to reemit_notes, then record
6478 its return value. */
6479 if (retval == NULL_RTX)
6480 retval = reemit_notes (insn, insn);
6482 reemit_notes (insn, insn);
6487 /* Return an insn which represents a SCHED_GROUP, which is
6488 the last insn in the group. */
6499 insn = next_nonnote_insn (insn);
6501 while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
6506 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
6507 possibly bringing insns from subsequent blocks in the same region.
6508 Return number of insns scheduled. */
6511 schedule_block (bb, rgn_n_insns)
6515 /* Local variables. */
6522 /* flow block of this bb */
6523 int b = BB_TO_BLOCK (bb);
6525 /* target_n_insns == number of insns in b before scheduling starts.
6526 sched_target_n_insns == how many of b's insns were scheduled.
6527 sched_n_insns == how many insns were scheduled in b */
6528 int target_n_insns = 0;
6529 int sched_target_n_insns = 0;
6530 int sched_n_insns = 0;
6532 #define NEED_NOTHING 0
6537 /* head/tail info for this block */
6544 /* We used to have code to avoid getting parameters moved from hard
6545 argument registers into pseudos.
6547 However, it was removed when it proved to be of marginal benefit
6548 and caused problems because schedule_block and compute_forward_dependences
6549 had different notions of what the "head" insn was. */
6550 get_block_head_tail (bb, &head, &tail);
6552 /* Interblock scheduling could have moved the original head insn from this
6553 block into a proceeding block. This may also cause schedule_block and
6554 compute_forward_dependences to have different notions of what the
6557 If the interblock movement happened to make this block start with
6558 some notes (LOOP, EH or SETJMP) before the first real insn, then
6559 HEAD will have various special notes attached to it which must be
6560 removed so that we don't end up with extra copies of the notes. */
6561 if (GET_RTX_CLASS (GET_CODE (head)) == 'i')
6565 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
6566 if (REG_NOTE_KIND (note) == REG_DEAD
6567 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6568 remove_note (head, note);
6571 next_tail = NEXT_INSN (tail);
6572 prev_head = PREV_INSN (head);
6574 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6575 to schedule this block. */
6577 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6578 return (sched_n_insns);
6583 fprintf (dump, ";; ======================================================\n");
6585 ";; -- basic block %d from %d to %d -- %s reload\n",
6586 b, INSN_UID (basic_block_head[b]),
6587 INSN_UID (basic_block_end[b]),
6588 (reload_completed ? "after" : "before"));
6589 fprintf (dump, ";; ======================================================\n");
6590 fprintf (dump, "\n");
6592 visual_tbl = (char *) alloca (get_visual_tbl_length ());
6593 init_block_visualization ();
6596 /* remove remaining note insns from the block, save them in
6597 note_list. These notes are restored at the end of
6598 schedule_block (). */
6600 rm_other_notes (head, tail);
6604 /* prepare current target block info */
6605 if (current_nr_blocks > 1)
6607 candidate_table = (candidate *) alloca (current_nr_blocks * sizeof (candidate));
6610 /* ??? It is not clear why bblst_size is computed this way. The original
6611 number was clearly too small as it resulted in compiler failures.
6612 Multiplying by the original number by 2 (to account for update_bbs
6613 members) seems to be a reasonable solution. */
6614 /* ??? Or perhaps there is a bug somewhere else in this file? */
6615 bblst_size = (current_nr_blocks - bb) * rgn_nr_edges * 2;
6616 bblst_table = (int *) alloca (bblst_size * sizeof (int));
6618 bitlst_table_last = 0;
6619 bitlst_table_size = rgn_nr_edges;
6620 bitlst_table = (int *) alloca (rgn_nr_edges * sizeof (int));
6622 compute_trg_info (bb);
6627 /* Allocate the ready list */
6628 ready = (rtx *) alloca ((rgn_n_insns + 1) * sizeof (rtx));
6630 /* Print debugging information. */
6631 if (sched_verbose >= 5)
6632 debug_dependencies ();
6635 /* Initialize ready list with all 'ready' insns in target block.
6636 Count number of insns in the target block being scheduled. */
6638 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6642 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6644 next = NEXT_INSN (insn);
6646 if (INSN_DEP_COUNT (insn) == 0
6647 && (SCHED_GROUP_P (next) == 0 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6648 ready[n_ready++] = insn;
6649 if (!(SCHED_GROUP_P (insn)))
6653 /* Add to ready list all 'ready' insns in valid source blocks.
6654 For speculative insns, check-live, exception-free, and
6656 for (bb_src = bb + 1; bb_src < current_nr_blocks; bb_src++)
6657 if (IS_VALID (bb_src))
6663 get_block_head_tail (bb_src, &head, &tail);
6664 src_next_tail = NEXT_INSN (tail);
6668 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6671 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
6673 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6676 if (!CANT_MOVE (insn)
6677 && (!IS_SPECULATIVE_INSN (insn)
6678 || (insn_issue_delay (insn) <= 3
6679 && check_live (insn, bb_src)
6680 && is_exception_free (insn, bb_src, target_bb))))
6685 next = NEXT_INSN (insn);
6686 if (INSN_DEP_COUNT (insn) == 0
6687 && (SCHED_GROUP_P (next) == 0
6688 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6689 ready[n_ready++] = insn;
6694 /* no insns scheduled in this block yet */
6695 last_scheduled_insn = 0;
6697 /* Sort the ready list */
6698 SCHED_SORT (ready, n_ready);
6700 if (sched_verbose >= 2)
6702 fprintf (dump, ";;\t\tReady list initially: ");
6703 debug_ready_list (ready, n_ready);
6706 /* Q_SIZE is the total number of insns in the queue. */
6710 bzero ((char *) insn_queue, sizeof (insn_queue));
6712 /* We start inserting insns after PREV_HEAD. */
6715 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6716 new_needs = (NEXT_INSN (prev_head) == basic_block_head[b]
6717 ? NEED_HEAD : NEED_NOTHING);
6718 if (PREV_INSN (next_tail) == basic_block_end[b])
6719 new_needs |= NEED_TAIL;
6721 /* loop until all the insns in BB are scheduled. */
6722 while (sched_target_n_insns < target_n_insns)
6728 /* Add to the ready list all pending insns that can be issued now.
6729 If there are no ready insns, increment clock until one
6730 is ready and add all pending insns at that point to the ready
6732 n_ready = queue_to_ready (ready, n_ready);
6737 if (sched_verbose >= 2)
6739 fprintf (dump, ";;\t\tReady list after queue_to_ready: ");
6740 debug_ready_list (ready, n_ready);
6743 /* Sort the ready list. */
6744 SCHED_SORT (ready, n_ready);
6748 fprintf (dump, "\n;;\tReady list (t =%3d): ", clock_var);
6749 debug_ready_list (ready, n_ready);
6752 /* Issue insns from ready list.
6753 It is important to count down from n_ready, because n_ready may change
6754 as insns are issued. */
6755 can_issue_more = issue_rate;
6756 for (i = n_ready - 1; i >= 0 && can_issue_more; i--)
6758 rtx insn = ready[i];
6759 int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
6763 queue_insn (insn, cost);
6764 ready[i] = ready[--n_ready]; /* remove insn from ready list */
6768 /* an interblock motion? */
6769 if (INSN_BB (insn) != target_bb)
6773 if (IS_SPECULATIVE_INSN (insn))
6776 if (!check_live (insn, INSN_BB (insn)))
6778 /* speculative motion, live check failed, remove
6779 insn from ready list */
6780 ready[i] = ready[--n_ready];
6783 update_live (insn, INSN_BB (insn));
6785 /* for speculative load, mark insns fed by it. */
6786 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
6787 set_spec_fed (insn);
6794 while (SCHED_GROUP_P (temp))
6795 temp = PREV_INSN (temp);
6797 /* Update source block boundaries. */
6798 b1 = INSN_BLOCK (temp);
6799 if (temp == basic_block_head[b1]
6800 && insn == basic_block_end[b1])
6802 /* We moved all the insns in the basic block.
6803 Emit a note after the last insn and update the
6804 begin/end boundaries to point to the note. */
6805 emit_note_after (NOTE_INSN_DELETED, insn);
6806 basic_block_end[b1] = NEXT_INSN (insn);
6807 basic_block_head[b1] = NEXT_INSN (insn);
6809 else if (insn == basic_block_end[b1])
6811 /* We took insns from the end of the basic block,
6812 so update the end of block boundary so that it
6813 points to the first insn we did not move. */
6814 basic_block_end[b1] = PREV_INSN (temp);
6816 else if (temp == basic_block_head[b1])
6818 /* We took insns from the start of the basic block,
6819 so update the start of block boundary so that
6820 it points to the first insn we did not move. */
6821 basic_block_head[b1] = NEXT_INSN (insn);
6826 /* in block motion */
6827 sched_target_n_insns++;
6830 last_scheduled_insn = insn;
6831 last = move_insn (insn, last);
6836 n_ready = schedule_insn (insn, ready, n_ready, clock_var);
6838 /* remove insn from ready list */
6839 ready[i] = ready[--n_ready];
6841 /* close this block after scheduling its jump */
6842 if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
6850 visualize_scheduled_insns (b, clock_var);
6857 fprintf (dump, ";;\tReady list (final): ");
6858 debug_ready_list (ready, n_ready);
6859 print_block_visualization (b, "");
6862 /* Sanity check -- queue must be empty now. Meaningless if region has
6864 if (current_nr_blocks > 1)
6865 if (!flag_schedule_interblock && q_size != 0)
6868 /* update head/tail boundaries. */
6869 head = NEXT_INSN (prev_head);
6872 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6873 previously found among the insns. Insert them at the beginning
6877 rtx note_head = note_list;
6879 while (PREV_INSN (note_head))
6881 note_head = PREV_INSN (note_head);
6884 PREV_INSN (note_head) = PREV_INSN (head);
6885 NEXT_INSN (PREV_INSN (head)) = note_head;
6886 PREV_INSN (head) = note_list;
6887 NEXT_INSN (note_list) = head;
6891 /* update target block boundaries. */
6892 if (new_needs & NEED_HEAD)
6893 basic_block_head[b] = head;
6895 if (new_needs & NEED_TAIL)
6896 basic_block_end[b] = tail;
6901 fprintf (dump, ";; total time = %d\n;; new basic block head = %d\n",
6902 clock_var, INSN_UID (basic_block_head[b]));
6903 fprintf (dump, ";; new basic block end = %d\n\n",
6904 INSN_UID (basic_block_end[b]));
6907 return (sched_n_insns);
6908 } /* schedule_block () */
6911 /* print the bit-set of registers, S. callable from debugger */
6914 debug_reg_vector (s)
6919 EXECUTE_IF_SET_IN_REG_SET (s, 0, regno,
6921 fprintf (dump, " %d", regno);
6924 fprintf (dump, "\n");
6927 /* Use the backward dependences from LOG_LINKS to build
6928 forward dependences in INSN_DEPEND. */
6931 compute_block_forward_dependences (bb)
6937 enum reg_note dep_type;
6939 get_block_head_tail (bb, &head, &tail);
6940 next_tail = NEXT_INSN (tail);
6941 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6943 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6946 insn = group_leader (insn);
6948 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
6950 rtx x = group_leader (XEXP (link, 0));
6953 if (x != XEXP (link, 0))
6956 /* Ignore dependences upon deleted insn */
6957 if (GET_CODE (x) == NOTE || INSN_DELETED_P (x))
6959 if (find_insn_list (insn, INSN_DEPEND (x)))
6962 new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
6964 dep_type = REG_NOTE_KIND (link);
6965 PUT_REG_NOTE_KIND (new_link, dep_type);
6967 INSN_DEPEND (x) = new_link;
6968 INSN_DEP_COUNT (insn) += 1;
6973 /* Initialize variables for region data dependence analysis.
6974 n_bbs is the number of region blocks */
6976 __inline static void
6977 init_rgn_data_dependences (n_bbs)
6982 /* variables for which one copy exists for each block */
6983 bzero ((char *) bb_pending_read_insns, n_bbs * sizeof (rtx));
6984 bzero ((char *) bb_pending_read_mems, n_bbs * sizeof (rtx));
6985 bzero ((char *) bb_pending_write_insns, n_bbs * sizeof (rtx));
6986 bzero ((char *) bb_pending_write_mems, n_bbs * sizeof (rtx));
6987 bzero ((char *) bb_pending_lists_length, n_bbs * sizeof (rtx));
6988 bzero ((char *) bb_last_pending_memory_flush, n_bbs * sizeof (rtx));
6989 bzero ((char *) bb_last_function_call, n_bbs * sizeof (rtx));
6990 bzero ((char *) bb_sched_before_next_call, n_bbs * sizeof (rtx));
6992 /* Create an insn here so that we can hang dependencies off of it later. */
6993 for (bb = 0; bb < n_bbs; bb++)
6995 bb_sched_before_next_call[bb] =
6996 gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
6997 NULL_RTX, 0, NULL_RTX, NULL_RTX);
6998 LOG_LINKS (bb_sched_before_next_call[bb]) = 0;
7002 /* Add dependences so that branches are scheduled to run last in their block */
7005 add_branch_dependences (head, tail)
7011 /* For all branches, calls, uses, and cc0 setters, force them to remain
7012 in order at the end of the block by adding dependencies and giving
7013 the last a high priority. There may be notes present, and prev_head
7016 Branches must obviously remain at the end. Calls should remain at the
7017 end since moving them results in worse register allocation. Uses remain
7018 at the end to ensure proper register allocation. cc0 setters remaim
7019 at the end because they can't be moved away from their cc0 user. */
7022 while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
7023 || (GET_CODE (insn) == INSN
7024 && (GET_CODE (PATTERN (insn)) == USE
7026 || sets_cc0_p (PATTERN (insn))
7029 || GET_CODE (insn) == NOTE)
7031 if (GET_CODE (insn) != NOTE)
7034 && !find_insn_list (insn, LOG_LINKS (last)))
7036 add_dependence (last, insn, REG_DEP_ANTI);
7037 INSN_REF_COUNT (insn)++;
7040 CANT_MOVE (insn) = 1;
7043 /* Skip over insns that are part of a group.
7044 Make each insn explicitly depend on the previous insn.
7045 This ensures that only the group header will ever enter
7046 the ready queue (and, when scheduled, will automatically
7047 schedule the SCHED_GROUP_P block). */
7048 while (SCHED_GROUP_P (insn))
7050 rtx temp = prev_nonnote_insn (insn);
7051 add_dependence (insn, temp, REG_DEP_ANTI);
7056 /* Don't overrun the bounds of the basic block. */
7060 insn = PREV_INSN (insn);
7063 /* make sure these insns are scheduled last in their block */
7066 while (insn != head)
7068 insn = prev_nonnote_insn (insn);
7070 if (INSN_REF_COUNT (insn) != 0)
7073 if (!find_insn_list (last, LOG_LINKS (insn)))
7074 add_dependence (last, insn, REG_DEP_ANTI);
7075 INSN_REF_COUNT (insn) = 1;
7077 /* Skip over insns that are part of a group. */
7078 while (SCHED_GROUP_P (insn))
7079 insn = prev_nonnote_insn (insn);
7083 /* Compute bacward dependences inside BB. In a multiple blocks region:
7084 (1) a bb is analyzed after its predecessors, and (2) the lists in
7085 effect at the end of bb (after analyzing for bb) are inherited by
7088 Specifically for reg-reg data dependences, the block insns are
7089 scanned by sched_analyze () top-to-bottom. Two lists are
7090 naintained by sched_analyze (): reg_last_defs[] for register DEFs,
7091 and reg_last_uses[] for register USEs.
7093 When analysis is completed for bb, we update for its successors:
7094 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7095 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7097 The mechanism for computing mem-mem data dependence is very
7098 similar, and the result is interblock dependences in the region. */
7101 compute_block_backward_dependences (bb)
7107 int max_reg = max_reg_num ();
7109 b = BB_TO_BLOCK (bb);
7111 if (current_nr_blocks == 1)
7113 reg_last_uses = (rtx *) alloca (max_reg * sizeof (rtx));
7114 reg_last_sets = (rtx *) alloca (max_reg * sizeof (rtx));
7116 bzero ((char *) reg_last_uses, max_reg * sizeof (rtx));
7117 bzero ((char *) reg_last_sets, max_reg * sizeof (rtx));
7119 pending_read_insns = 0;
7120 pending_read_mems = 0;
7121 pending_write_insns = 0;
7122 pending_write_mems = 0;
7123 pending_lists_length = 0;
7124 last_function_call = 0;
7125 last_pending_memory_flush = 0;
7126 sched_before_next_call
7127 = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
7128 NULL_RTX, 0, NULL_RTX, NULL_RTX);
7129 LOG_LINKS (sched_before_next_call) = 0;
7133 reg_last_uses = bb_reg_last_uses[bb];
7134 reg_last_sets = bb_reg_last_sets[bb];
7136 pending_read_insns = bb_pending_read_insns[bb];
7137 pending_read_mems = bb_pending_read_mems[bb];
7138 pending_write_insns = bb_pending_write_insns[bb];
7139 pending_write_mems = bb_pending_write_mems[bb];
7140 pending_lists_length = bb_pending_lists_length[bb];
7141 last_function_call = bb_last_function_call[bb];
7142 last_pending_memory_flush = bb_last_pending_memory_flush[bb];
7144 sched_before_next_call = bb_sched_before_next_call[bb];
7147 /* do the analysis for this block */
7148 get_block_head_tail (bb, &head, &tail);
7149 sched_analyze (head, tail);
7150 add_branch_dependences (head, tail);
7152 if (current_nr_blocks > 1)
7155 int b_succ, bb_succ;
7157 rtx link_insn, link_mem;
7160 /* these lists should point to the right place, for correct freeing later. */
7161 bb_pending_read_insns[bb] = pending_read_insns;
7162 bb_pending_read_mems[bb] = pending_read_mems;
7163 bb_pending_write_insns[bb] = pending_write_insns;
7164 bb_pending_write_mems[bb] = pending_write_mems;
7166 /* bb's structures are inherited by it's successors */
7167 first_edge = e = OUT_EDGES (b);
7171 b_succ = TO_BLOCK (e);
7172 bb_succ = BLOCK_TO_BB (b_succ);
7174 /* only bbs "below" bb, in the same region, are interesting */
7175 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
7182 for (reg = 0; reg < max_reg; reg++)
7185 /* reg-last-uses lists are inherited by bb_succ */
7186 for (u = reg_last_uses[reg]; u; u = XEXP (u, 1))
7188 if (find_insn_list (XEXP (u, 0), (bb_reg_last_uses[bb_succ])[reg]))
7191 (bb_reg_last_uses[bb_succ])[reg]
7192 = alloc_INSN_LIST (XEXP (u, 0),
7193 (bb_reg_last_uses[bb_succ])[reg]);
7196 /* reg-last-defs lists are inherited by bb_succ */
7197 for (u = reg_last_sets[reg]; u; u = XEXP (u, 1))
7199 if (find_insn_list (XEXP (u, 0), (bb_reg_last_sets[bb_succ])[reg]))
7202 (bb_reg_last_sets[bb_succ])[reg]
7203 = alloc_INSN_LIST (XEXP (u, 0),
7204 (bb_reg_last_sets[bb_succ])[reg]);
7208 /* mem read/write lists are inherited by bb_succ */
7209 link_insn = pending_read_insns;
7210 link_mem = pending_read_mems;
7213 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7214 bb_pending_read_insns[bb_succ],
7215 bb_pending_read_mems[bb_succ])))
7216 add_insn_mem_dependence (&bb_pending_read_insns[bb_succ],
7217 &bb_pending_read_mems[bb_succ],
7218 XEXP (link_insn, 0), XEXP (link_mem, 0));
7219 link_insn = XEXP (link_insn, 1);
7220 link_mem = XEXP (link_mem, 1);
7223 link_insn = pending_write_insns;
7224 link_mem = pending_write_mems;
7227 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7228 bb_pending_write_insns[bb_succ],
7229 bb_pending_write_mems[bb_succ])))
7230 add_insn_mem_dependence (&bb_pending_write_insns[bb_succ],
7231 &bb_pending_write_mems[bb_succ],
7232 XEXP (link_insn, 0), XEXP (link_mem, 0));
7234 link_insn = XEXP (link_insn, 1);
7235 link_mem = XEXP (link_mem, 1);
7238 /* last_function_call is inherited by bb_succ */
7239 for (u = last_function_call; u; u = XEXP (u, 1))
7241 if (find_insn_list (XEXP (u, 0), bb_last_function_call[bb_succ]))
7244 bb_last_function_call[bb_succ]
7245 = alloc_INSN_LIST (XEXP (u, 0),
7246 bb_last_function_call[bb_succ]);
7249 /* last_pending_memory_flush is inherited by bb_succ */
7250 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
7252 if (find_insn_list (XEXP (u, 0), bb_last_pending_memory_flush[bb_succ]))
7255 bb_last_pending_memory_flush[bb_succ]
7256 = alloc_INSN_LIST (XEXP (u, 0),
7257 bb_last_pending_memory_flush[bb_succ]);
7260 /* sched_before_next_call is inherited by bb_succ */
7261 x = LOG_LINKS (sched_before_next_call);
7262 for (; x; x = XEXP (x, 1))
7263 add_dependence (bb_sched_before_next_call[bb_succ],
7264 XEXP (x, 0), REG_DEP_ANTI);
7268 while (e != first_edge);
7271 /* Free up the INSN_LISTs
7273 Note this loop is executed max_reg * nr_regions times. It's first
7274 implementation accounted for over 90% of the calls to free_list.
7275 The list was empty for the vast majority of those calls. On the PA,
7276 not calling free_list in those cases improves -O2 compile times by
7278 for (b = 0; b < max_reg; ++b)
7280 if (reg_last_sets[b])
7281 free_list (®_last_sets[b], &unused_insn_list);
7282 if (reg_last_uses[b])
7283 free_list (®_last_uses[b], &unused_insn_list);
7286 /* Assert that we won't need bb_reg_last_* for this block anymore. */
7287 if (current_nr_blocks > 1)
7289 bb_reg_last_uses[bb] = (rtx *) NULL_RTX;
7290 bb_reg_last_sets[bb] = (rtx *) NULL_RTX;
7294 /* Print dependences for debugging, callable from debugger */
7297 debug_dependencies ()
7301 fprintf (dump, ";; --------------- forward dependences: ------------ \n");
7302 for (bb = 0; bb < current_nr_blocks; bb++)
7310 get_block_head_tail (bb, &head, &tail);
7311 next_tail = NEXT_INSN (tail);
7312 fprintf (dump, "\n;; --- Region Dependences --- b %d bb %d \n",
7313 BB_TO_BLOCK (bb), bb);
7315 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7316 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7317 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7318 "----", "----", "--", "---", "----", "----", "--------", "-----");
7319 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
7324 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7327 fprintf (dump, ";; %6d ", INSN_UID (insn));
7328 if (GET_CODE (insn) == NOTE)
7330 n = NOTE_LINE_NUMBER (insn);
7332 fprintf (dump, "%s\n", GET_NOTE_INSN_NAME (n));
7334 fprintf (dump, "line %d, file %s\n", n,
7335 NOTE_SOURCE_FILE (insn));
7338 fprintf (dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
7342 unit = insn_unit (insn);
7344 || function_units[unit].blockage_range_function == 0) ? 0 :
7345 function_units[unit].blockage_range_function (insn);
7347 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7348 (SCHED_GROUP_P (insn) ? "+" : " "),
7352 INSN_DEP_COUNT (insn),
7353 INSN_PRIORITY (insn),
7354 insn_cost (insn, 0, 0),
7355 (int) MIN_BLOCKAGE_COST (range),
7356 (int) MAX_BLOCKAGE_COST (range));
7357 insn_print_units (insn);
7358 fprintf (dump, "\t: ");
7359 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
7360 fprintf (dump, "%d ", INSN_UID (XEXP (link, 0)));
7361 fprintf (dump, "\n");
7365 fprintf (dump, "\n");
7368 /* Set_priorities: compute priority of each insn in the block */
7381 get_block_head_tail (bb, &head, &tail);
7382 prev_head = PREV_INSN (head);
7385 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
7389 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
7392 if (GET_CODE (insn) == NOTE)
7395 if (!(SCHED_GROUP_P (insn)))
7397 (void) priority (insn);
7403 /* Make each element of VECTOR point at an rtx-vector,
7404 taking the space for all those rtx-vectors from SPACE.
7405 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7406 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7407 (this is the same as init_regset_vector () in flow.c) */
7410 init_rtx_vector (vector, space, nelts, bytes_per_elt)
7417 register rtx *p = space;
7419 for (i = 0; i < nelts; i++)
7422 p += bytes_per_elt / sizeof (*p);
7426 /* Schedule a region. A region is either an inner loop, a loop-free
7427 subroutine, or a single basic block. Each bb in the region is
7428 scheduled after its flow predecessors. */
7431 schedule_region (rgn)
7435 int rgn_n_insns = 0;
7436 int sched_rgn_n_insns = 0;
7438 /* set variables for the current region */
7439 current_nr_blocks = RGN_NR_BLOCKS (rgn);
7440 current_blocks = RGN_BLOCKS (rgn);
7442 reg_pending_sets = ALLOCA_REG_SET ();
7443 reg_pending_sets_all = 0;
7445 /* initializations for region data dependence analyisis */
7446 if (current_nr_blocks > 1)
7449 int maxreg = max_reg_num ();
7451 bb_reg_last_uses = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7452 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7453 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7454 init_rtx_vector (bb_reg_last_uses, space, current_nr_blocks, maxreg * sizeof (rtx *));
7456 bb_reg_last_sets = (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_sets, space, current_nr_blocks, maxreg * sizeof (rtx *));
7461 bb_pending_read_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7462 bb_pending_read_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7463 bb_pending_write_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7464 bb_pending_write_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7465 bb_pending_lists_length = (int *) alloca (current_nr_blocks * sizeof (int));
7466 bb_last_pending_memory_flush = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7467 bb_last_function_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7468 bb_sched_before_next_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7470 init_rgn_data_dependences (current_nr_blocks);
7473 /* compute LOG_LINKS */
7474 for (bb = 0; bb < current_nr_blocks; bb++)
7475 compute_block_backward_dependences (bb);
7477 /* compute INSN_DEPEND */
7478 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7479 compute_block_forward_dependences (bb);
7481 /* Delete line notes, compute live-regs at block end, and set priorities. */
7483 for (bb = 0; bb < current_nr_blocks; bb++)
7485 if (reload_completed == 0)
7486 find_pre_sched_live (bb);
7488 if (write_symbols != NO_DEBUG)
7490 save_line_notes (bb);
7494 rgn_n_insns += set_priorities (bb);
7497 /* compute interblock info: probabilities, split-edges, dominators, etc. */
7498 if (current_nr_blocks > 1)
7502 prob = (float *) alloca ((current_nr_blocks) * sizeof (float));
7504 bbset_size = current_nr_blocks / HOST_BITS_PER_WIDE_INT + 1;
7505 dom = (bbset *) alloca (current_nr_blocks * sizeof (bbset));
7506 for (i = 0; i < current_nr_blocks; i++)
7508 dom[i] = (bbset) alloca (bbset_size * sizeof (HOST_WIDE_INT));
7509 bzero ((char *) dom[i], bbset_size * sizeof (HOST_WIDE_INT));
7514 edge_to_bit = (int *) alloca (nr_edges * sizeof (int));
7515 for (i = 1; i < nr_edges; i++)
7516 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
7517 EDGE_TO_BIT (i) = rgn_nr_edges++;
7518 rgn_edges = (int *) alloca (rgn_nr_edges * sizeof (int));
7521 for (i = 1; i < nr_edges; i++)
7522 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
7523 rgn_edges[rgn_nr_edges++] = i;
7526 edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
7527 pot_split = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7528 ancestor_edges = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7529 for (i = 0; i < current_nr_blocks; i++)
7532 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7533 bzero ((char *) pot_split[i],
7534 edgeset_size * sizeof (HOST_WIDE_INT));
7536 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7537 bzero ((char *) ancestor_edges[i],
7538 edgeset_size * sizeof (HOST_WIDE_INT));
7541 /* compute probabilities, dominators, split_edges */
7542 for (bb = 0; bb < current_nr_blocks; bb++)
7543 compute_dom_prob_ps (bb);
7546 /* now we can schedule all blocks */
7547 for (bb = 0; bb < current_nr_blocks; bb++)
7549 sched_rgn_n_insns += schedule_block (bb, rgn_n_insns);
7556 /* sanity check: verify that all region insns were scheduled */
7557 if (sched_rgn_n_insns != rgn_n_insns)
7560 /* update register life and usage information */
7561 if (reload_completed == 0)
7563 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7564 find_post_sched_live (bb);
7566 if (current_nr_blocks <= 1)
7567 /* Sanity check. There should be no REG_DEAD notes leftover at the end.
7568 In practice, this can occur as the result of bugs in flow, combine.c,
7569 and/or sched.c. The values of the REG_DEAD notes remaining are
7570 meaningless, because dead_notes is just used as a free list. */
7571 if (dead_notes != 0)
7575 /* restore line notes. */
7576 if (write_symbols != NO_DEBUG)
7578 for (bb = 0; bb < current_nr_blocks; bb++)
7579 restore_line_notes (bb);
7582 /* Done with this region */
7583 free_pending_lists ();
7585 FREE_REG_SET (reg_pending_sets);
7588 /* Subroutine of split_hard_reg_notes. Searches X for any reference to
7589 REGNO, returning the rtx of the reference found if any. Otherwise,
7593 regno_use_in (regno, x)
7601 if (GET_CODE (x) == REG && REGNO (x) == regno)
7604 fmt = GET_RTX_FORMAT (GET_CODE (x));
7605 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
7609 if ((tem = regno_use_in (regno, XEXP (x, i))))
7612 else if (fmt[i] == 'E')
7613 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
7614 if ((tem = regno_use_in (regno, XVECEXP (x, i, j))))
7621 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
7622 needed for the hard register mentioned in the note. This can happen
7623 if the reference to the hard register in the original insn was split into
7624 several smaller hard register references in the split insns. */
7627 split_hard_reg_notes (note, first, last)
7628 rtx note, first, last;
7630 rtx reg, temp, link;
7631 int n_regs, i, new_reg;
7634 /* Assume that this is a REG_DEAD note. */
7635 if (REG_NOTE_KIND (note) != REG_DEAD)
7638 reg = XEXP (note, 0);
7640 n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
7642 for (i = 0; i < n_regs; i++)
7644 new_reg = REGNO (reg) + i;
7646 /* Check for references to new_reg in the split insns. */
7647 for (insn = last;; insn = PREV_INSN (insn))
7649 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7650 && (temp = regno_use_in (new_reg, PATTERN (insn))))
7652 /* Create a new reg dead note ere. */
7653 link = alloc_EXPR_LIST (REG_DEAD, temp, REG_NOTES (insn));
7654 REG_NOTES (insn) = link;
7656 /* If killed multiple registers here, then add in the excess. */
7657 i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
7661 /* It isn't mentioned anywhere, so no new reg note is needed for
7669 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
7670 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
7673 new_insn_dead_notes (pat, insn, last, orig_insn)
7674 rtx pat, insn, last, orig_insn;
7678 /* PAT is either a CLOBBER or a SET here. */
7679 dest = XEXP (pat, 0);
7681 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
7682 || GET_CODE (dest) == STRICT_LOW_PART
7683 || GET_CODE (dest) == SIGN_EXTRACT)
7684 dest = XEXP (dest, 0);
7686 if (GET_CODE (dest) == REG)
7688 /* If the original insn already used this register, we may not add new
7689 notes for it. One example for a split that needs this test is
7690 when a multi-word memory access with register-indirect addressing
7691 is split into multiple memory accesses with auto-increment and
7692 one adjusting add instruction for the address register. */
7693 if (reg_referenced_p (dest, PATTERN (orig_insn)))
7695 for (tem = last; tem != insn; tem = PREV_INSN (tem))
7697 if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
7698 && reg_overlap_mentioned_p (dest, PATTERN (tem))
7699 && (set = single_set (tem)))
7701 rtx tem_dest = SET_DEST (set);
7703 while (GET_CODE (tem_dest) == ZERO_EXTRACT
7704 || GET_CODE (tem_dest) == SUBREG
7705 || GET_CODE (tem_dest) == STRICT_LOW_PART
7706 || GET_CODE (tem_dest) == SIGN_EXTRACT)
7707 tem_dest = XEXP (tem_dest, 0);
7709 if (!rtx_equal_p (tem_dest, dest))
7711 /* Use the same scheme as combine.c, don't put both REG_DEAD
7712 and REG_UNUSED notes on the same insn. */
7713 if (!find_regno_note (tem, REG_UNUSED, REGNO (dest))
7714 && !find_regno_note (tem, REG_DEAD, REGNO (dest)))
7716 rtx note = alloc_EXPR_LIST (REG_DEAD, dest,
7718 REG_NOTES (tem) = note;
7720 /* The reg only dies in one insn, the last one that uses
7724 else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
7725 /* We found an instruction that both uses the register,
7726 and sets it, so no new REG_NOTE is needed for this set. */
7730 /* If this is a set, it must die somewhere, unless it is the dest of
7731 the original insn, and hence is live after the original insn. Abort
7732 if it isn't supposed to be live after the original insn.
7734 If this is a clobber, then just add a REG_UNUSED note. */
7737 int live_after_orig_insn = 0;
7738 rtx pattern = PATTERN (orig_insn);
7741 if (GET_CODE (pat) == CLOBBER)
7743 rtx note = alloc_EXPR_LIST (REG_UNUSED, dest, REG_NOTES (insn));
7744 REG_NOTES (insn) = note;
7748 /* The original insn could have multiple sets, so search the
7749 insn for all sets. */
7750 if (GET_CODE (pattern) == SET)
7752 if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
7753 live_after_orig_insn = 1;
7755 else if (GET_CODE (pattern) == PARALLEL)
7757 for (i = 0; i < XVECLEN (pattern, 0); i++)
7758 if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
7759 && reg_overlap_mentioned_p (dest,
7760 SET_DEST (XVECEXP (pattern,
7762 live_after_orig_insn = 1;
7765 if (!live_after_orig_insn)
7771 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
7772 registers modified by X. INC is -1 if the containing insn is being deleted,
7773 and is 1 if the containing insn is a newly generated insn. */
7776 update_n_sets (x, inc)
7780 rtx dest = SET_DEST (x);
7782 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
7783 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
7784 dest = SUBREG_REG (dest);
7786 if (GET_CODE (dest) == REG)
7788 int regno = REGNO (dest);
7790 if (regno < FIRST_PSEUDO_REGISTER)
7793 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
7795 for (i = regno; i < endregno; i++)
7796 REG_N_SETS (i) += inc;
7799 REG_N_SETS (regno) += inc;
7803 /* Updates all flow-analysis related quantities (including REG_NOTES) for
7804 the insns from FIRST to LAST inclusive that were created by splitting
7805 ORIG_INSN. NOTES are the original REG_NOTES. */
7808 update_flow_info (notes, first, last, orig_insn)
7815 rtx orig_dest, temp;
7818 /* Get and save the destination set by the original insn. */
7820 orig_dest = single_set (orig_insn);
7822 orig_dest = SET_DEST (orig_dest);
7824 /* Move REG_NOTES from the original insn to where they now belong. */
7826 for (note = notes; note; note = next)
7828 next = XEXP (note, 1);
7829 switch (REG_NOTE_KIND (note))
7833 /* Move these notes from the original insn to the last new insn where
7834 the register is now set. */
7836 for (insn = last;; insn = PREV_INSN (insn))
7838 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7839 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
7841 /* If this note refers to a multiple word hard register, it
7842 may have been split into several smaller hard register
7843 references, so handle it specially. */
7844 temp = XEXP (note, 0);
7845 if (REG_NOTE_KIND (note) == REG_DEAD
7846 && GET_CODE (temp) == REG
7847 && REGNO (temp) < FIRST_PSEUDO_REGISTER
7848 && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
7849 split_hard_reg_notes (note, first, last);
7852 XEXP (note, 1) = REG_NOTES (insn);
7853 REG_NOTES (insn) = note;
7856 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
7858 /* ??? This won't handle multiple word registers correctly,
7859 but should be good enough for now. */
7860 if (REG_NOTE_KIND (note) == REG_UNUSED
7861 && GET_CODE (XEXP (note, 0)) != SCRATCH
7862 && !dead_or_set_p (insn, XEXP (note, 0)))
7863 PUT_REG_NOTE_KIND (note, REG_DEAD);
7865 /* The reg only dies in one insn, the last one that uses
7869 /* It must die somewhere, fail it we couldn't find where it died.
7871 If this is a REG_UNUSED note, then it must be a temporary
7872 register that was not needed by this instantiation of the
7873 pattern, so we can safely ignore it. */
7876 /* After reload, REG_DEAD notes come sometimes an
7877 instruction after the register actually dies. */
7878 if (reload_completed && REG_NOTE_KIND (note) == REG_DEAD)
7880 XEXP (note, 1) = REG_NOTES (insn);
7881 REG_NOTES (insn) = note;
7885 if (REG_NOTE_KIND (note) != REG_UNUSED)
7894 /* If the insn that set the register to 0 was deleted, this
7895 note cannot be relied on any longer. The destination might
7896 even have been moved to memory.
7897 This was observed for SH4 with execute/920501-6.c compilation,
7898 -O2 -fomit-frame-pointer -finline-functions . */
7899 if (GET_CODE (XEXP (note, 0)) == NOTE
7900 || INSN_DELETED_P (XEXP (note, 0)))
7902 /* This note applies to the dest of the original insn. Find the
7903 first new insn that now has the same dest, and move the note
7909 for (insn = first;; insn = NEXT_INSN (insn))
7911 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7912 && (temp = single_set (insn))
7913 && rtx_equal_p (SET_DEST (temp), orig_dest))
7915 XEXP (note, 1) = REG_NOTES (insn);
7916 REG_NOTES (insn) = note;
7917 /* The reg is only zero before one insn, the first that
7921 /* If this note refers to a multiple word hard
7922 register, it may have been split into several smaller
7923 hard register references. We could split the notes,
7924 but simply dropping them is good enough. */
7925 if (GET_CODE (orig_dest) == REG
7926 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
7927 && HARD_REGNO_NREGS (REGNO (orig_dest),
7928 GET_MODE (orig_dest)) > 1)
7930 /* It must be set somewhere, fail if we couldn't find where it
7939 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
7940 set is meaningless. Just drop the note. */
7944 case REG_NO_CONFLICT:
7945 /* These notes apply to the dest of the original insn. Find the last
7946 new insn that now has the same dest, and move the note there. */
7951 for (insn = last;; insn = PREV_INSN (insn))
7953 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7954 && (temp = single_set (insn))
7955 && rtx_equal_p (SET_DEST (temp), orig_dest))
7957 XEXP (note, 1) = REG_NOTES (insn);
7958 REG_NOTES (insn) = note;
7959 /* Only put this note on one of the new insns. */
7963 /* The original dest must still be set someplace. Abort if we
7964 couldn't find it. */
7967 /* However, if this note refers to a multiple word hard
7968 register, it may have been split into several smaller
7969 hard register references. We could split the notes,
7970 but simply dropping them is good enough. */
7971 if (GET_CODE (orig_dest) == REG
7972 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
7973 && HARD_REGNO_NREGS (REGNO (orig_dest),
7974 GET_MODE (orig_dest)) > 1)
7976 /* Likewise for multi-word memory references. */
7977 if (GET_CODE (orig_dest) == MEM
7978 && SIZE_FOR_MODE (orig_dest) > MOVE_MAX)
7986 /* Move a REG_LIBCALL note to the first insn created, and update
7987 the corresponding REG_RETVAL note. */
7988 XEXP (note, 1) = REG_NOTES (first);
7989 REG_NOTES (first) = note;
7991 insn = XEXP (note, 0);
7992 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
7994 XEXP (note, 0) = first;
7997 case REG_EXEC_COUNT:
7998 /* Move a REG_EXEC_COUNT note to the first insn created. */
7999 XEXP (note, 1) = REG_NOTES (first);
8000 REG_NOTES (first) = note;
8004 /* Move a REG_RETVAL note to the last insn created, and update
8005 the corresponding REG_LIBCALL note. */
8006 XEXP (note, 1) = REG_NOTES (last);
8007 REG_NOTES (last) = note;
8009 insn = XEXP (note, 0);
8010 note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
8012 XEXP (note, 0) = last;
8017 /* This should be moved to whichever instruction is a JUMP_INSN. */
8019 for (insn = last;; insn = PREV_INSN (insn))
8021 if (GET_CODE (insn) == JUMP_INSN)
8023 XEXP (note, 1) = REG_NOTES (insn);
8024 REG_NOTES (insn) = note;
8025 /* Only put this note on one of the new insns. */
8028 /* Fail if we couldn't find a JUMP_INSN. */
8035 /* reload sometimes leaves obsolete REG_INC notes around. */
8036 if (reload_completed)
8038 /* This should be moved to whichever instruction now has the
8039 increment operation. */
8043 /* Should be moved to the new insn(s) which use the label. */
8044 for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
8045 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8046 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
8048 REG_NOTES (insn) = alloc_EXPR_LIST (REG_LABEL,
8056 /* These two notes will never appear until after reorg, so we don't
8057 have to handle them here. */
8063 /* Each new insn created, except the last, has a new set. If the destination
8064 is a register, then this reg is now live across several insns, whereas
8065 previously the dest reg was born and died within the same insn. To
8066 reflect this, we now need a REG_DEAD note on the insn where this
8069 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
8071 for (insn = first; insn != last; insn = NEXT_INSN (insn))
8076 pat = PATTERN (insn);
8077 if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
8078 new_insn_dead_notes (pat, insn, last, orig_insn);
8079 else if (GET_CODE (pat) == PARALLEL)
8081 for (i = 0; i < XVECLEN (pat, 0); i++)
8082 if (GET_CODE (XVECEXP (pat, 0, i)) == SET
8083 || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
8084 new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
8088 /* If any insn, except the last, uses the register set by the last insn,
8089 then we need a new REG_DEAD note on that insn. In this case, there
8090 would not have been a REG_DEAD note for this register in the original
8091 insn because it was used and set within one insn. */
8093 set = single_set (last);
8096 rtx dest = SET_DEST (set);
8098 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
8099 || GET_CODE (dest) == STRICT_LOW_PART
8100 || GET_CODE (dest) == SIGN_EXTRACT)
8101 dest = XEXP (dest, 0);
8103 if (GET_CODE (dest) == REG
8104 /* Global registers are always live, so the code below does not
8106 && (REGNO (dest) >= FIRST_PSEUDO_REGISTER
8107 || ! global_regs[REGNO (dest)]))
8109 rtx stop_insn = PREV_INSN (first);
8111 /* If the last insn uses the register that it is setting, then
8112 we don't want to put a REG_DEAD note there. Search backwards
8113 to find the first insn that sets but does not use DEST. */
8116 if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
8118 for (insn = PREV_INSN (insn); insn != first;
8119 insn = PREV_INSN (insn))
8121 if ((set = single_set (insn))
8122 && reg_mentioned_p (dest, SET_DEST (set))
8123 && ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
8128 /* Now find the first insn that uses but does not set DEST. */
8130 for (insn = PREV_INSN (insn); insn != stop_insn;
8131 insn = PREV_INSN (insn))
8133 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8134 && reg_mentioned_p (dest, PATTERN (insn))
8135 && (set = single_set (insn)))
8137 rtx insn_dest = SET_DEST (set);
8139 while (GET_CODE (insn_dest) == ZERO_EXTRACT
8140 || GET_CODE (insn_dest) == SUBREG
8141 || GET_CODE (insn_dest) == STRICT_LOW_PART
8142 || GET_CODE (insn_dest) == SIGN_EXTRACT)
8143 insn_dest = XEXP (insn_dest, 0);
8145 if (insn_dest != dest)
8147 note = alloc_EXPR_LIST (REG_DEAD, dest, REG_NOTES (insn));
8148 REG_NOTES (insn) = note;
8149 /* The reg only dies in one insn, the last one
8158 /* If the original dest is modifying a multiple register target, and the
8159 original instruction was split such that the original dest is now set
8160 by two or more SUBREG sets, then the split insns no longer kill the
8161 destination of the original insn.
8163 In this case, if there exists an instruction in the same basic block,
8164 before the split insn, which uses the original dest, and this use is
8165 killed by the original insn, then we must remove the REG_DEAD note on
8166 this insn, because it is now superfluous.
8168 This does not apply when a hard register gets split, because the code
8169 knows how to handle overlapping hard registers properly. */
8170 if (orig_dest && GET_CODE (orig_dest) == REG)
8172 int found_orig_dest = 0;
8173 int found_split_dest = 0;
8175 for (insn = first;; insn = NEXT_INSN (insn))
8180 /* I'm not sure if this can happen, but let's be safe. */
8181 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
8184 pat = PATTERN (insn);
8185 i = GET_CODE (pat) == PARALLEL ? XVECLEN (pat, 0) : 0;
8190 if (GET_CODE (set) == SET)
8192 if (GET_CODE (SET_DEST (set)) == REG
8193 && REGNO (SET_DEST (set)) == REGNO (orig_dest))
8195 found_orig_dest = 1;
8198 else if (GET_CODE (SET_DEST (set)) == SUBREG
8199 && SUBREG_REG (SET_DEST (set)) == orig_dest)
8201 found_split_dest = 1;
8207 set = XVECEXP (pat, 0, i);
8214 if (found_split_dest)
8216 /* Search backwards from FIRST, looking for the first insn that uses
8217 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
8218 If we find an insn, and it has a REG_DEAD note, then delete the
8221 for (insn = first; insn; insn = PREV_INSN (insn))
8223 if (GET_CODE (insn) == CODE_LABEL
8224 || GET_CODE (insn) == JUMP_INSN)
8226 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8227 && reg_mentioned_p (orig_dest, insn))
8229 note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
8231 remove_note (insn, note);
8235 else if (!found_orig_dest)
8237 /* This should never happen. */
8242 /* Update reg_n_sets. This is necessary to prevent local alloc from
8243 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
8244 a reg from set once to set multiple times. */
8247 rtx x = PATTERN (orig_insn);
8248 RTX_CODE code = GET_CODE (x);
8250 if (code == SET || code == CLOBBER)
8251 update_n_sets (x, -1);
8252 else if (code == PARALLEL)
8255 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8257 code = GET_CODE (XVECEXP (x, 0, i));
8258 if (code == SET || code == CLOBBER)
8259 update_n_sets (XVECEXP (x, 0, i), -1);
8263 for (insn = first;; insn = NEXT_INSN (insn))
8266 code = GET_CODE (x);
8268 if (code == SET || code == CLOBBER)
8269 update_n_sets (x, 1);
8270 else if (code == PARALLEL)
8273 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8275 code = GET_CODE (XVECEXP (x, 0, i));
8276 if (code == SET || code == CLOBBER)
8277 update_n_sets (XVECEXP (x, 0, i), 1);
8287 /* Do the splitting of insns in the block b. */
8290 split_block_insns (b)
8295 for (insn = basic_block_head[b];; insn = next)
8297 rtx set, last, first, notes;
8299 /* Can't use `next_real_insn' because that
8300 might go across CODE_LABELS and short-out basic blocks. */
8301 next = NEXT_INSN (insn);
8302 if (GET_CODE (insn) != INSN)
8304 if (insn == basic_block_end[b])
8310 /* Don't split no-op move insns. These should silently disappear
8311 later in final. Splitting such insns would break the code
8312 that handles REG_NO_CONFLICT blocks. */
8313 set = single_set (insn);
8314 if (set && rtx_equal_p (SET_SRC (set), SET_DEST (set)))
8316 if (insn == basic_block_end[b])
8319 /* Nops get in the way while scheduling, so delete them now if
8320 register allocation has already been done. It is too risky
8321 to try to do this before register allocation, and there are
8322 unlikely to be very many nops then anyways. */
8323 if (reload_completed)
8325 PUT_CODE (insn, NOTE);
8326 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
8327 NOTE_SOURCE_FILE (insn) = 0;
8333 /* Split insns here to get max fine-grain parallelism. */
8334 first = PREV_INSN (insn);
8335 notes = REG_NOTES (insn);
8336 last = try_split (PATTERN (insn), insn, 1);
8339 /* try_split returns the NOTE that INSN became. */
8340 first = NEXT_INSN (first);
8341 update_flow_info (notes, first, last, insn);
8343 PUT_CODE (insn, NOTE);
8344 NOTE_SOURCE_FILE (insn) = 0;
8345 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
8346 if (insn == basic_block_head[b])
8347 basic_block_head[b] = first;
8348 if (insn == basic_block_end[b])
8350 basic_block_end[b] = last;
8355 if (insn == basic_block_end[b])
8360 /* The one entry point in this file. DUMP_FILE is the dump file for
8364 schedule_insns (dump_file)
8375 /* disable speculative loads in their presence if cc0 defined */
8377 flag_schedule_speculative_load = 0;
8380 /* Taking care of this degenerate case makes the rest of
8381 this code simpler. */
8382 if (n_basic_blocks == 0)
8385 /* set dump and sched_verbose for the desired debugging output. If no
8386 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
8387 For -fsched-verbose-N, N>=10, print everything to stderr. */
8388 sched_verbose = sched_verbose_param;
8389 if (sched_verbose_param == 0 && dump_file)
8391 dump = ((sched_verbose_param >= 10 || !dump_file) ? stderr : dump_file);
8396 /* Initialize the unused_*_lists. We can't use the ones left over from
8397 the previous function, because gcc has freed that memory. We can use
8398 the ones left over from the first sched pass in the second pass however,
8399 so only clear them on the first sched pass. The first pass is before
8400 reload if flag_schedule_insns is set, otherwise it is afterwards. */
8402 if (reload_completed == 0 || !flag_schedule_insns)
8404 unused_insn_list = 0;
8405 unused_expr_list = 0;
8408 /* initialize issue_rate */
8409 issue_rate = ISSUE_RATE;
8411 /* do the splitting first for all blocks */
8412 for (b = 0; b < n_basic_blocks; b++)
8413 split_block_insns (b);
8415 max_uid = (get_max_uid () + 1);
8417 cant_move = (char *) alloca (max_uid * sizeof (char));
8418 bzero ((char *) cant_move, max_uid * sizeof (char));
8420 fed_by_spec_load = (char *) alloca (max_uid * sizeof (char));
8421 bzero ((char *) fed_by_spec_load, max_uid * sizeof (char));
8423 is_load_insn = (char *) alloca (max_uid * sizeof (char));
8424 bzero ((char *) is_load_insn, max_uid * sizeof (char));
8426 insn_orig_block = (int *) alloca (max_uid * sizeof (int));
8427 insn_luid = (int *) alloca (max_uid * sizeof (int));
8430 for (b = 0; b < n_basic_blocks; b++)
8431 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
8433 INSN_BLOCK (insn) = b;
8434 INSN_LUID (insn) = luid++;
8436 if (insn == basic_block_end[b])
8440 /* after reload, remove inter-blocks dependences computed before reload. */
8441 if (reload_completed)
8446 for (b = 0; b < n_basic_blocks; b++)
8447 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
8451 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
8454 link = LOG_LINKS (insn);
8457 rtx x = XEXP (link, 0);
8459 if (INSN_BLOCK (x) != b)
8461 remove_dependence (insn, x);
8462 link = prev ? XEXP (prev, 1) : LOG_LINKS (insn);
8465 prev = link, link = XEXP (prev, 1);
8469 if (insn == basic_block_end[b])
8475 rgn_table = (region *) alloca ((n_basic_blocks) * sizeof (region));
8476 rgn_bb_table = (int *) alloca ((n_basic_blocks) * sizeof (int));
8477 block_to_bb = (int *) alloca ((n_basic_blocks) * sizeof (int));
8478 containing_rgn = (int *) alloca ((n_basic_blocks) * sizeof (int));
8480 /* compute regions for scheduling */
8481 if (reload_completed
8482 || n_basic_blocks == 1
8483 || !flag_schedule_interblock)
8485 find_single_block_region ();
8489 /* verify that a 'good' control flow graph can be built */
8490 if (is_cfg_nonregular ())
8492 find_single_block_region ();
8496 int_list_ptr *s_preds, *s_succs;
8497 int *num_preds, *num_succs;
8498 sbitmap *dom, *pdom;
8500 s_preds = (int_list_ptr *) alloca (n_basic_blocks
8501 * sizeof (int_list_ptr));
8502 s_succs = (int_list_ptr *) alloca (n_basic_blocks
8503 * sizeof (int_list_ptr));
8504 num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
8505 num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
8506 dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
8507 pdom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
8509 /* The scheduler runs after flow; therefore, we can't blindly call
8510 back into find_basic_blocks since doing so could invalidate the
8511 info in basic_block_live_at_start.
8513 Consider a block consisting entirely of dead stores; after life
8514 analysis it would be a block of NOTE_INSN_DELETED notes. If
8515 we call find_basic_blocks again, then the block would be removed
8516 entirely and invalidate our the register live information.
8518 We could (should?) recompute register live information. Doing
8519 so may even be beneficial. */
8521 /* CYGNUS LOCAL edge_splitting/law */
8522 compute_preds_succs (s_preds, s_succs, num_preds, num_succs, 0);
8523 /* END CYGNUS LOCAL */
8525 /* Compute the dominators and post dominators. We don't currently use
8526 post dominators, but we should for speculative motion analysis. */
8527 compute_dominators (dom, pdom, s_preds, s_succs);
8529 /* build_control_flow will return nonzero if it detects unreachable
8530 blocks or any other irregularity with the cfg which prevents
8531 cross block scheduling. */
8532 if (build_control_flow (s_preds, s_succs, num_preds, num_succs) != 0)
8533 find_single_block_region ();
8535 find_rgns (s_preds, s_succs, num_preds, num_succs, dom);
8537 if (sched_verbose >= 3)
8540 /* For now. This will move as more and more of haifa is converted
8541 to using the cfg code in flow.c */
8548 /* Allocate data for this pass. See comments, above,
8549 for what these vectors do. */
8550 insn_priority = (int *) alloca (max_uid * sizeof (int));
8551 insn_reg_weight = (int *) alloca (max_uid * sizeof (int));
8552 insn_tick = (int *) alloca (max_uid * sizeof (int));
8553 insn_costs = (short *) alloca (max_uid * sizeof (short));
8554 insn_units = (short *) alloca (max_uid * sizeof (short));
8555 insn_blockage = (unsigned int *) alloca (max_uid * sizeof (unsigned int));
8556 insn_ref_count = (int *) alloca (max_uid * sizeof (int));
8558 /* Allocate for forward dependencies */
8559 insn_dep_count = (int *) alloca (max_uid * sizeof (int));
8560 insn_depend = (rtx *) alloca (max_uid * sizeof (rtx));
8562 if (reload_completed == 0)
8566 sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
8567 sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
8568 sched_reg_basic_block = (int *) alloca (max_regno * sizeof (int));
8569 bb_live_regs = ALLOCA_REG_SET ();
8570 bzero ((char *) sched_reg_n_calls_crossed, max_regno * sizeof (int));
8571 bzero ((char *) sched_reg_live_length, max_regno * sizeof (int));
8573 for (i = 0; i < max_regno; i++)
8574 sched_reg_basic_block[i] = REG_BLOCK_UNKNOWN;
8578 sched_reg_n_calls_crossed = 0;
8579 sched_reg_live_length = 0;
8582 init_alias_analysis ();
8584 if (write_symbols != NO_DEBUG)
8588 line_note = (rtx *) alloca (max_uid * sizeof (rtx));
8589 bzero ((char *) line_note, max_uid * sizeof (rtx));
8590 line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
8591 bzero ((char *) line_note_head, n_basic_blocks * sizeof (rtx));
8593 /* Save-line-note-head:
8594 Determine the line-number at the start of each basic block.
8595 This must be computed and saved now, because after a basic block's
8596 predecessor has been scheduled, it is impossible to accurately
8597 determine the correct line number for the first insn of the block. */
8599 for (b = 0; b < n_basic_blocks; b++)
8600 for (line = basic_block_head[b]; line; line = PREV_INSN (line))
8601 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
8603 line_note_head[b] = line;
8608 bzero ((char *) insn_priority, max_uid * sizeof (int));
8609 bzero ((char *) insn_reg_weight, max_uid * sizeof (int));
8610 bzero ((char *) insn_tick, max_uid * sizeof (int));
8611 bzero ((char *) insn_costs, max_uid * sizeof (short));
8612 bzero ((char *) insn_units, max_uid * sizeof (short));
8613 bzero ((char *) insn_blockage, max_uid * sizeof (unsigned int));
8614 bzero ((char *) insn_ref_count, max_uid * sizeof (int));
8616 /* Initialize for forward dependencies */
8617 bzero ((char *) insn_depend, max_uid * sizeof (rtx));
8618 bzero ((char *) insn_dep_count, max_uid * sizeof (int));
8620 /* Find units used in this fuction, for visualization */
8622 init_target_units ();
8624 /* ??? Add a NOTE after the last insn of the last basic block. It is not
8625 known why this is done. */
8627 insn = basic_block_end[n_basic_blocks - 1];
8628 if (NEXT_INSN (insn) == 0
8629 || (GET_CODE (insn) != NOTE
8630 && GET_CODE (insn) != CODE_LABEL
8631 /* Don't emit a NOTE if it would end up between an unconditional
8632 jump and a BARRIER. */
8633 && !(GET_CODE (insn) == JUMP_INSN
8634 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
8635 emit_note_after (NOTE_INSN_DELETED, basic_block_end[n_basic_blocks - 1]);
8637 /* Schedule every region in the subroutine */
8638 for (rgn = 0; rgn < nr_regions; rgn++)
8640 schedule_region (rgn);
8647 /* Reposition the prologue and epilogue notes in case we moved the
8648 prologue/epilogue insns. */
8649 if (reload_completed)
8650 reposition_prologue_and_epilogue_notes (get_insns ());
8652 /* delete redundant line notes. */
8653 if (write_symbols != NO_DEBUG)
8654 rm_redundant_line_notes ();
8656 /* Update information about uses of registers in the subroutine. */
8657 if (reload_completed == 0)
8658 update_reg_usage ();
8662 if (reload_completed == 0 && flag_schedule_interblock)
8664 fprintf (dump, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8672 fprintf (dump, "\n\n");
8676 FREE_REG_SET (bb_live_regs);
8695 #endif /* INSN_SCHEDULING */