1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 93-98, 1999 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to the Free
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
24 /* Instruction scheduling pass.
26 This pass implements list scheduling within basic blocks. It is
27 run twice: (1) after flow analysis, but before register allocation,
28 and (2) after register allocation.
30 The first run performs interblock scheduling, moving insns between
31 different blocks in the same "region", and the second runs only
32 basic block scheduling.
34 Interblock motions performed are useful motions and speculative
35 motions, including speculative loads. Motions requiring code
36 duplication are not supported. The identification of motion type
37 and the check for validity of speculative motions requires
38 construction and analysis of the function's control flow graph.
39 The scheduler works as follows:
41 We compute insn priorities based on data dependencies. Flow
42 analysis only creates a fraction of the data-dependencies we must
43 observe: namely, only those dependencies which the combiner can be
44 expected to use. For this pass, we must therefore create the
45 remaining dependencies we need to observe: register dependencies,
46 memory dependencies, dependencies to keep function calls in order,
47 and the dependence between a conditional branch and the setting of
48 condition codes are all dealt with here.
50 The scheduler first traverses the data flow graph, starting with
51 the last instruction, and proceeding to the first, assigning values
52 to insn_priority as it goes. This sorts the instructions
53 topologically by data dependence.
55 Once priorities have been established, we order the insns using
56 list scheduling. This works as follows: starting with a list of
57 all the ready insns, and sorted according to priority number, we
58 schedule the insn from the end of the list by placing its
59 predecessors in the list according to their priority order. We
60 consider this insn scheduled by setting the pointer to the "end" of
61 the list to point to the previous insn. When an insn has no
62 predecessors, we either queue it until sufficient time has elapsed
63 or add it to the ready list. As the instructions are scheduled or
64 when stalls are introduced, the queue advances and dumps insns into
65 the ready list. When all insns down to the lowest priority have
66 been scheduled, the critical path of the basic block has been made
67 as short as possible. The remaining insns are then scheduled in
70 Function unit conflicts are resolved during forward list scheduling
71 by tracking the time when each insn is committed to the schedule
72 and from that, the time the function units it uses must be free.
73 As insns on the ready list are considered for scheduling, those
74 that would result in a blockage of the already committed insns are
75 queued until no blockage will result.
77 The following list shows the order in which we want to break ties
78 among insns in the ready list:
80 1. choose insn with the longest path to end of bb, ties
82 2. choose insn with least contribution to register pressure,
84 3. prefer in-block upon interblock motion, ties broken by
85 4. prefer useful upon speculative motion, ties broken by
86 5. choose insn with largest control flow probability, ties
88 6. choose insn with the least dependences upon the previously
89 scheduled insn, or finally
90 7 choose the insn which has the most insns dependent on it.
91 8. choose insn with lowest UID.
93 Memory references complicate matters. Only if we can be certain
94 that memory references are not part of the data dependency graph
95 (via true, anti, or output dependence), can we move operations past
96 memory references. To first approximation, reads can be done
97 independently, while writes introduce dependencies. Better
98 approximations will yield fewer dependencies.
100 Before reload, an extended analysis of interblock data dependences
101 is required for interblock scheduling. This is performed in
102 compute_block_backward_dependences ().
104 Dependencies set up by memory references are treated in exactly the
105 same way as other dependencies, by using LOG_LINKS backward
106 dependences. LOG_LINKS are translated into INSN_DEPEND forward
107 dependences for the purpose of forward list scheduling.
109 Having optimized the critical path, we may have also unduly
110 extended the lifetimes of some registers. If an operation requires
111 that constants be loaded into registers, it is certainly desirable
112 to load those constants as early as necessary, but no earlier.
113 I.e., it will not do to load up a bunch of registers at the
114 beginning of a basic block only to use them at the end, if they
115 could be loaded later, since this may result in excessive register
118 Note that since branches are never in basic blocks, but only end
119 basic blocks, this pass will not move branches. But that is ok,
120 since we can use GNU's delayed branch scheduling pass to take care
123 Also note that no further optimizations based on algebraic
124 identities are performed, so this pass would be a good one to
125 perform instruction splitting, such as breaking up a multiply
126 instruction into shifts and adds where that is profitable.
128 Given the memory aliasing analysis that this pass should perform,
129 it should be possible to remove redundant stores to memory, and to
130 load values from registers instead of hitting memory.
132 Before reload, speculative insns are moved only if a 'proof' exists
133 that no exception will be caused by this, and if no live registers
134 exist that inhibit the motion (live registers constraints are not
135 represented by data dependence edges).
137 This pass must update information that subsequent passes expect to
138 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
139 reg_n_calls_crossed, and reg_live_length. Also, BLOCK_HEAD,
142 The information in the line number notes is carefully retained by
143 this pass. Notes that refer to the starting and ending of
144 exception regions are also carefully retained by this pass. All
145 other NOTE insns are grouped in their same relative order at the
146 beginning of basic blocks and regions that have been scheduled.
148 The main entry point for this pass is schedule_insns(), called for
149 each function. The work of the scheduler is organized in three
150 levels: (1) function level: insns are subject to splitting,
151 control-flow-graph is constructed, regions are computed (after
152 reload, each region is of one block), (2) region level: control
153 flow graph attributes required for interblock scheduling are
154 computed (dominators, reachability, etc.), data dependences and
155 priorities are computed, and (3) block level: insns in the block
156 are actually scheduled. */
162 #include "basic-block.h"
164 #include "function.h"
165 #include "hard-reg-set.h"
167 #include "insn-config.h"
168 #include "insn-attr.h"
173 extern char *reg_known_equiv_p;
174 extern rtx *reg_known_value;
176 #ifdef INSN_SCHEDULING
178 /* target_units bitmask has 1 for each unit in the cpu. It should be
179 possible to compute this variable from the machine description.
180 But currently it is computed by examinning the insn list. Since
181 this is only needed for visualization, it seems an acceptable
182 solution. (For understanding the mapping of bits to units, see
183 definition of function_units[] in "insn-attrtab.c") */
185 static int target_units = 0;
187 /* issue_rate is the number of insns that can be scheduled in the same
188 machine cycle. It can be defined in the config/mach/mach.h file,
189 otherwise we set it to 1. */
191 static int issue_rate;
197 /* sched-verbose controls the amount of debugging output the
198 scheduler prints. It is controlled by -fsched-verbose-N:
199 N>0 and no -DSR : the output is directed to stderr.
200 N>=10 will direct the printouts to stderr (regardless of -dSR).
202 N=2: bb's probabilities, detailed ready list info, unit/insn info.
203 N=3: rtl at abort point, control-flow, regions info.
204 N=5: dependences info. */
206 #define MAX_RGN_BLOCKS 10
207 #define MAX_RGN_INSNS 100
209 static int sched_verbose_param = 0;
210 static int sched_verbose = 0;
212 /* nr_inter/spec counts interblock/speculative motion for the function */
213 static int nr_inter, nr_spec;
216 /* debugging file. all printouts are sent to dump, which is always set,
217 either to stderr, or to the dump listing file (-dRS). */
218 static FILE *dump = 0;
220 /* fix_sched_param() is called from toplev.c upon detection
221 of the -fsched-***-N options. */
224 fix_sched_param (param, val)
225 const char *param, *val;
227 if (!strcmp (param, "verbose"))
228 sched_verbose_param = atoi (val);
230 warning ("fix_sched_param: unknown param: %s", param);
234 /* Arrays set up by scheduling for the same respective purposes as
235 similar-named arrays set up by flow analysis. We work with these
236 arrays during the scheduling pass so we can compare values against
239 Values of these arrays are copied at the end of this pass into the
240 arrays set up by flow analysis. */
241 static int *sched_reg_n_calls_crossed;
242 static int *sched_reg_live_length;
243 static int *sched_reg_basic_block;
245 /* We need to know the current block number during the post scheduling
246 update of live register information so that we can also update
247 REG_BASIC_BLOCK if a register changes blocks. */
248 static int current_block_num;
250 /* Element N is the next insn that sets (hard or pseudo) register
251 N within the current basic block; or zero, if there is no
252 such insn. Needed for new registers which may be introduced
253 by splitting insns. */
254 static rtx *reg_last_uses;
255 static rtx *reg_last_sets;
256 static rtx *reg_last_clobbers;
257 static regset reg_pending_sets;
258 static regset reg_pending_clobbers;
259 static int reg_pending_sets_all;
261 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
262 static int *insn_luid;
263 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
265 /* Vector indexed by INSN_UID giving each instruction a priority. */
266 static int *insn_priority;
267 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
269 static short *insn_costs;
270 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
272 /* Vector indexed by INSN_UID giving an encoding of the function units
274 static short *insn_units;
275 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
277 /* Vector indexed by INSN_UID giving each instruction a register-weight.
278 This weight is an estimation of the insn contribution to registers pressure. */
279 static int *insn_reg_weight;
280 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
282 /* Vector indexed by INSN_UID giving list of insns which
283 depend upon INSN. Unlike LOG_LINKS, it represents forward dependences. */
284 static rtx *insn_depend;
285 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
287 /* Vector indexed by INSN_UID. Initialized to the number of incoming
288 edges in forward dependence graph (= number of LOG_LINKS). As
289 scheduling procedes, dependence counts are decreased. An
290 instruction moves to the ready list when its counter is zero. */
291 static int *insn_dep_count;
292 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
294 /* Vector indexed by INSN_UID giving an encoding of the blockage range
295 function. The unit and the range are encoded. */
296 static unsigned int *insn_blockage;
297 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
299 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
300 #define ENCODE_BLOCKAGE(U, R) \
301 (((U) << BLOCKAGE_BITS \
302 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
303 | MAX_BLOCKAGE_COST (R))
304 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
305 #define BLOCKAGE_RANGE(B) \
306 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
307 | ((B) & BLOCKAGE_MASK))
309 /* Encodings of the `<name>_unit_blockage_range' function. */
310 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
311 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
313 #define DONE_PRIORITY -1
314 #define MAX_PRIORITY 0x7fffffff
315 #define TAIL_PRIORITY 0x7ffffffe
316 #define LAUNCH_PRIORITY 0x7f000001
317 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
318 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
320 /* Vector indexed by INSN_UID giving number of insns referring to this insn. */
321 static int *insn_ref_count;
322 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
324 /* Vector indexed by INSN_UID giving line-number note in effect for each
325 insn. For line-number notes, this indicates whether the note may be
327 static rtx *line_note;
328 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
330 /* Vector indexed by basic block number giving the starting line-number
331 for each basic block. */
332 static rtx *line_note_head;
334 /* List of important notes we must keep around. This is a pointer to the
335 last element in the list. */
336 static rtx note_list;
338 /* Regsets telling whether a given register is live or dead before the last
339 scheduled insn. Must scan the instructions once before scheduling to
340 determine what registers are live or dead at the end of the block. */
341 static regset bb_live_regs;
343 /* Regset telling whether a given register is live after the insn currently
344 being scheduled. Before processing an insn, this is equal to bb_live_regs
345 above. This is used so that we can find registers that are newly born/dead
346 after processing an insn. */
347 static regset old_live_regs;
349 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
350 during the initial scan and reused later. If there are not exactly as
351 many REG_DEAD notes in the post scheduled code as there were in the
352 prescheduled code then we trigger an abort because this indicates a bug. */
353 static rtx dead_notes;
357 /* An instruction is ready to be scheduled when all insns preceding it
358 have already been scheduled. It is important to ensure that all
359 insns which use its result will not be executed until its result
360 has been computed. An insn is maintained in one of four structures:
362 (P) the "Pending" set of insns which cannot be scheduled until
363 their dependencies have been satisfied.
364 (Q) the "Queued" set of insns that can be scheduled when sufficient
366 (R) the "Ready" list of unscheduled, uncommitted insns.
367 (S) the "Scheduled" list of insns.
369 Initially, all insns are either "Pending" or "Ready" depending on
370 whether their dependencies are satisfied.
372 Insns move from the "Ready" list to the "Scheduled" list as they
373 are committed to the schedule. As this occurs, the insns in the
374 "Pending" list have their dependencies satisfied and move to either
375 the "Ready" list or the "Queued" set depending on whether
376 sufficient time has passed to make them ready. As time passes,
377 insns move from the "Queued" set to the "Ready" list. Insns may
378 move from the "Ready" list to the "Queued" set if they are blocked
379 due to a function unit conflict.
381 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
382 insns, i.e., those that are ready, queued, and pending.
383 The "Queued" set (Q) is implemented by the variable `insn_queue'.
384 The "Ready" list (R) is implemented by the variables `ready' and
386 The "Scheduled" list (S) is the new insn chain built by this pass.
388 The transition (R->S) is implemented in the scheduling loop in
389 `schedule_block' when the best insn to schedule is chosen.
390 The transition (R->Q) is implemented in `queue_insn' when an
391 insn is found to have a function unit conflict with the already
393 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
394 insns move from the ready list to the scheduled list.
395 The transition (Q->R) is implemented in 'queue_to_insn' as time
396 passes or stalls are introduced. */
398 /* Implement a circular buffer to delay instructions until sufficient
399 time has passed. INSN_QUEUE_SIZE is a power of two larger than
400 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
401 longest time an isnsn may be queued. */
402 static rtx insn_queue[INSN_QUEUE_SIZE];
403 static int q_ptr = 0;
404 static int q_size = 0;
405 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
406 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
408 /* Vector indexed by INSN_UID giving the minimum clock tick at which
409 the insn becomes ready. This is used to note timing constraints for
410 insns in the pending list. */
411 static int *insn_tick;
412 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
414 /* Data structure for keeping track of register information
415 during that register's life. */
424 /* Forward declarations. */
425 static void add_dependence PROTO ((rtx, rtx, enum reg_note));
426 static void remove_dependence PROTO ((rtx, rtx));
427 static rtx find_insn_list PROTO ((rtx, rtx));
428 static int insn_unit PROTO ((rtx));
429 static unsigned int blockage_range PROTO ((int, rtx));
430 static void clear_units PROTO ((void));
431 static int actual_hazard_this_instance PROTO ((int, int, rtx, int, int));
432 static void schedule_unit PROTO ((int, rtx, int));
433 static int actual_hazard PROTO ((int, rtx, int, int));
434 static int potential_hazard PROTO ((int, rtx, int));
435 static int insn_cost PROTO ((rtx, rtx, rtx));
436 static int priority PROTO ((rtx));
437 static void free_pending_lists PROTO ((void));
438 static void add_insn_mem_dependence PROTO ((rtx *, rtx *, rtx, rtx));
439 static void flush_pending_lists PROTO ((rtx, int));
440 static void sched_analyze_1 PROTO ((rtx, rtx));
441 static void sched_analyze_2 PROTO ((rtx, rtx));
442 static void sched_analyze_insn PROTO ((rtx, rtx, rtx));
443 static void sched_analyze PROTO ((rtx, rtx));
444 static void sched_note_set PROTO ((rtx, int));
445 static int rank_for_schedule PROTO ((const GENERIC_PTR, const GENERIC_PTR));
446 static void swap_sort PROTO ((rtx *, int));
447 static void queue_insn PROTO ((rtx, int));
448 static int schedule_insn PROTO ((rtx, rtx *, int, int));
449 static void create_reg_dead_note PROTO ((rtx, rtx));
450 static void attach_deaths PROTO ((rtx, rtx, int));
451 static void attach_deaths_insn PROTO ((rtx));
452 static int new_sometimes_live PROTO ((struct sometimes *, int, int));
453 static void finish_sometimes_live PROTO ((struct sometimes *, int));
454 static int schedule_block PROTO ((int, int));
455 static void split_hard_reg_notes PROTO ((rtx, rtx, rtx));
456 static void new_insn_dead_notes PROTO ((rtx, rtx, rtx, rtx));
457 static void update_n_sets PROTO ((rtx, int));
458 static char *safe_concat PROTO ((char *, char *, const char *));
459 static int insn_issue_delay PROTO ((rtx));
460 static int birthing_insn_p PROTO ((rtx));
461 static void adjust_priority PROTO ((rtx));
463 /* Mapping of insns to their original block prior to scheduling. */
464 static int *insn_orig_block;
465 #define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
467 /* Some insns (e.g. call) are not allowed to move across blocks. */
468 static char *cant_move;
469 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
471 /* Control flow graph edges are kept in circular lists. */
480 static haifa_edge *edge_table;
482 #define NEXT_IN(edge) (edge_table[edge].next_in)
483 #define NEXT_OUT(edge) (edge_table[edge].next_out)
484 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
485 #define TO_BLOCK(edge) (edge_table[edge].to_block)
487 /* Number of edges in the control flow graph. (in fact larger than
488 that by 1, since edge 0 is unused.) */
491 /* Circular list of incoming/outgoing edges of a block */
492 static int *in_edges;
493 static int *out_edges;
495 #define IN_EDGES(block) (in_edges[block])
496 #define OUT_EDGES(block) (out_edges[block])
500 static int is_cfg_nonregular PROTO ((void));
501 static int build_control_flow PROTO ((int_list_ptr *, int_list_ptr *,
503 static void new_edge PROTO ((int, int));
506 /* A region is the main entity for interblock scheduling: insns
507 are allowed to move between blocks in the same region, along
508 control flow graph edges, in the 'up' direction. */
511 int rgn_nr_blocks; /* number of blocks in region */
512 int rgn_blocks; /* blocks in the region (actually index in rgn_bb_table) */
516 /* Number of regions in the procedure */
517 static int nr_regions;
519 /* Table of region descriptions */
520 static region *rgn_table;
522 /* Array of lists of regions' blocks */
523 static int *rgn_bb_table;
525 /* Topological order of blocks in the region (if b2 is reachable from
526 b1, block_to_bb[b2] > block_to_bb[b1]).
527 Note: A basic block is always referred to by either block or b,
528 while its topological order name (in the region) is refered to by
531 static int *block_to_bb;
533 /* The number of the region containing a block. */
534 static int *containing_rgn;
536 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
537 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
538 #define BLOCK_TO_BB(block) (block_to_bb[block])
539 #define CONTAINING_RGN(block) (containing_rgn[block])
541 void debug_regions PROTO ((void));
542 static void find_single_block_region PROTO ((void));
543 static void find_rgns PROTO ((int_list_ptr *, int_list_ptr *,
544 int *, int *, sbitmap *));
545 static int too_large PROTO ((int, int *, int *));
547 extern void debug_live PROTO ((int, int));
549 /* Blocks of the current region being scheduled. */
550 static int current_nr_blocks;
551 static int current_blocks;
553 /* The mapping from bb to block */
554 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
557 /* Bit vectors and bitset operations are needed for computations on
558 the control flow graph. */
560 typedef unsigned HOST_WIDE_INT *bitset;
563 int *first_member; /* pointer to the list start in bitlst_table. */
564 int nr_members; /* the number of members of the bit list. */
568 static int bitlst_table_last;
569 static int bitlst_table_size;
570 static int *bitlst_table;
572 static char bitset_member PROTO ((bitset, int, int));
573 static void extract_bitlst PROTO ((bitset, int, bitlst *));
575 /* target info declarations.
577 The block currently being scheduled is referred to as the "target" block,
578 while other blocks in the region from which insns can be moved to the
579 target are called "source" blocks. The candidate structure holds info
580 about such sources: are they valid? Speculative? Etc. */
581 typedef bitlst bblst;
592 static candidate *candidate_table;
594 /* A speculative motion requires checking live information on the path
595 from 'source' to 'target'. The split blocks are those to be checked.
596 After a speculative motion, live information should be modified in
599 Lists of split and update blocks for each candidate of the current
600 target are in array bblst_table */
601 static int *bblst_table, bblst_size, bblst_last;
603 #define IS_VALID(src) ( candidate_table[src].is_valid )
604 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
605 #define SRC_PROB(src) ( candidate_table[src].src_prob )
607 /* The bb being currently scheduled. */
608 static int target_bb;
611 typedef bitlst edgelst;
613 /* target info functions */
614 static void split_edges PROTO ((int, int, edgelst *));
615 static void compute_trg_info PROTO ((int));
616 void debug_candidate PROTO ((int));
617 void debug_candidates PROTO ((int));
620 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
621 typedef bitset bbset;
623 /* Number of words of the bbset. */
624 static int bbset_size;
626 /* Dominators array: dom[i] contains the bbset of dominators of
627 bb i in the region. */
630 /* bb 0 is the only region entry */
631 #define IS_RGN_ENTRY(bb) (!bb)
633 /* Is bb_src dominated by bb_trg. */
634 #define IS_DOMINATED(bb_src, bb_trg) \
635 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
637 /* Probability: Prob[i] is a float in [0, 1] which is the probability
638 of bb i relative to the region entry. */
641 /* The probability of bb_src, relative to bb_trg. Note, that while the
642 'prob[bb]' is a float in [0, 1], this macro returns an integer
644 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
647 /* Bit-set of edges, where bit i stands for edge i. */
648 typedef bitset edgeset;
650 /* Number of edges in the region. */
651 static int rgn_nr_edges;
653 /* Array of size rgn_nr_edges. */
654 static int *rgn_edges;
656 /* Number of words in an edgeset. */
657 static int edgeset_size;
659 /* Mapping from each edge in the graph to its number in the rgn. */
660 static int *edge_to_bit;
661 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
663 /* The split edges of a source bb is different for each target
664 bb. In order to compute this efficiently, the 'potential-split edges'
665 are computed for each bb prior to scheduling a region. This is actually
666 the split edges of each bb relative to the region entry.
668 pot_split[bb] is the set of potential split edges of bb. */
669 static edgeset *pot_split;
671 /* For every bb, a set of its ancestor edges. */
672 static edgeset *ancestor_edges;
674 static void compute_dom_prob_ps PROTO ((int));
676 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
677 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
678 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
679 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
681 /* parameters affecting the decision of rank_for_schedule() */
682 #define MIN_DIFF_PRIORITY 2
683 #define MIN_PROBABILITY 40
684 #define MIN_PROB_DIFF 10
686 /* speculative scheduling functions */
687 static int check_live_1 PROTO ((int, rtx));
688 static void update_live_1 PROTO ((int, rtx));
689 static int check_live PROTO ((rtx, int));
690 static void update_live PROTO ((rtx, int));
691 static void set_spec_fed PROTO ((rtx));
692 static int is_pfree PROTO ((rtx, int, int));
693 static int find_conditional_protection PROTO ((rtx, int));
694 static int is_conditionally_protected PROTO ((rtx, int, int));
695 static int may_trap_exp PROTO ((rtx, int));
696 static int haifa_classify_insn PROTO ((rtx));
697 static int is_prisky PROTO ((rtx, int, int));
698 static int is_exception_free PROTO ((rtx, int, int));
700 static char find_insn_mem_list PROTO ((rtx, rtx, rtx, rtx));
701 static void compute_block_forward_dependences PROTO ((int));
702 static void init_rgn_data_dependences PROTO ((int));
703 static void add_branch_dependences PROTO ((rtx, rtx));
704 static void compute_block_backward_dependences PROTO ((int));
705 void debug_dependencies PROTO ((void));
707 /* Notes handling mechanism:
708 =========================
709 Generally, NOTES are saved before scheduling and restored after scheduling.
710 The scheduler distinguishes between three types of notes:
712 (1) LINE_NUMBER notes, generated and used for debugging. Here,
713 before scheduling a region, a pointer to the LINE_NUMBER note is
714 added to the insn following it (in save_line_notes()), and the note
715 is removed (in rm_line_notes() and unlink_line_notes()). After
716 scheduling the region, this pointer is used for regeneration of
717 the LINE_NUMBER note (in restore_line_notes()).
719 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
720 Before scheduling a region, a pointer to the note is added to the insn
721 that follows or precedes it. (This happens as part of the data dependence
722 computation). After scheduling an insn, the pointer contained in it is
723 used for regenerating the corresponding note (in reemit_notes).
725 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
726 these notes are put in a list (in rm_other_notes() and
727 unlink_other_notes ()). After scheduling the block, these notes are
728 inserted at the beginning of the block (in schedule_block()). */
730 static rtx unlink_other_notes PROTO ((rtx, rtx));
731 static rtx unlink_line_notes PROTO ((rtx, rtx));
732 static void rm_line_notes PROTO ((int));
733 static void save_line_notes PROTO ((int));
734 static void restore_line_notes PROTO ((int));
735 static void rm_redundant_line_notes PROTO ((void));
736 static void rm_other_notes PROTO ((rtx, rtx));
737 static rtx reemit_notes PROTO ((rtx, rtx));
739 static void get_block_head_tail PROTO ((int, rtx *, rtx *));
741 static void find_pre_sched_live PROTO ((int));
742 static void find_post_sched_live PROTO ((int));
743 static void update_reg_usage PROTO ((void));
744 static int queue_to_ready PROTO ((rtx [], int));
746 static void debug_ready_list PROTO ((rtx[], int));
747 static void init_target_units PROTO ((void));
748 static void insn_print_units PROTO ((rtx));
749 static int get_visual_tbl_length PROTO ((void));
750 static void init_block_visualization PROTO ((void));
751 static void print_block_visualization PROTO ((int, const char *));
752 static void visualize_scheduled_insns PROTO ((int, int));
753 static void visualize_no_unit PROTO ((rtx));
754 static void visualize_stall_cycles PROTO ((int, int));
755 static void print_exp PROTO ((char *, rtx, int));
756 static void print_value PROTO ((char *, rtx, int));
757 static void print_pattern PROTO ((char *, rtx, int));
758 static void print_insn PROTO ((char *, rtx, int));
759 void debug_reg_vector PROTO ((regset));
761 static rtx move_insn1 PROTO ((rtx, rtx));
762 static rtx move_insn PROTO ((rtx, rtx));
763 static rtx group_leader PROTO ((rtx));
764 static int set_priorities PROTO ((int));
765 static void init_rtx_vector PROTO ((rtx **, rtx *, int, int));
766 static void schedule_region PROTO ((int));
768 #endif /* INSN_SCHEDULING */
770 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
772 /* Helper functions for instruction scheduling. */
774 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
775 static rtx unused_insn_list;
777 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
778 static rtx unused_expr_list;
780 static void free_list PROTO ((rtx *, rtx *));
781 static rtx alloc_INSN_LIST PROTO ((rtx, rtx));
782 static rtx alloc_EXPR_LIST PROTO ((int, rtx, rtx));
785 free_list (listp, unused_listp)
786 rtx *listp, *unused_listp;
788 register rtx link, prev_link;
794 link = XEXP (prev_link, 1);
799 link = XEXP (link, 1);
802 XEXP (prev_link, 1) = *unused_listp;
803 *unused_listp = *listp;
808 alloc_INSN_LIST (val, next)
813 if (unused_insn_list)
815 r = unused_insn_list;
816 unused_insn_list = XEXP (r, 1);
819 PUT_REG_NOTE_KIND (r, VOIDmode);
822 r = gen_rtx_INSN_LIST (VOIDmode, val, next);
828 alloc_EXPR_LIST (kind, val, next)
834 if (unused_expr_list)
836 r = unused_expr_list;
837 unused_expr_list = XEXP (r, 1);
840 PUT_REG_NOTE_KIND (r, kind);
843 r = gen_rtx_EXPR_LIST (kind, val, next);
848 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
849 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
850 of dependence that this link represents. */
853 add_dependence (insn, elem, dep_type)
856 enum reg_note dep_type;
860 /* Don't depend an insn on itself. */
864 /* We can get a dependency on deleted insns due to optimizations in
865 the register allocation and reloading or due to splitting. Any
866 such dependency is useless and can be ignored. */
867 if (GET_CODE (elem) == NOTE)
870 /* If elem is part of a sequence that must be scheduled together, then
871 make the dependence point to the last insn of the sequence.
872 When HAVE_cc0, it is possible for NOTEs to exist between users and
873 setters of the condition codes, so we must skip past notes here.
874 Otherwise, NOTEs are impossible here. */
876 next = NEXT_INSN (elem);
879 while (next && GET_CODE (next) == NOTE)
880 next = NEXT_INSN (next);
883 if (next && SCHED_GROUP_P (next)
884 && GET_CODE (next) != CODE_LABEL)
886 /* Notes will never intervene here though, so don't bother checking
888 /* We must reject CODE_LABELs, so that we don't get confused by one
889 that has LABEL_PRESERVE_P set, which is represented by the same
890 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
892 while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
893 && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
894 next = NEXT_INSN (next);
896 /* Again, don't depend an insn on itself. */
900 /* Make the dependence to NEXT, the last insn of the group, instead
901 of the original ELEM. */
905 #ifdef INSN_SCHEDULING
906 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
907 No need for interblock dependences with calls, since
908 calls are not moved between blocks. Note: the edge where
909 elem is a CALL is still required. */
910 if (GET_CODE (insn) == CALL_INSN
911 && (INSN_BB (elem) != INSN_BB (insn)))
916 /* Check that we don't already have this dependence. */
917 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
918 if (XEXP (link, 0) == elem)
920 /* If this is a more restrictive type of dependence than the existing
921 one, then change the existing dependence to this type. */
922 if ((int) dep_type < (int) REG_NOTE_KIND (link))
923 PUT_REG_NOTE_KIND (link, dep_type);
926 /* Might want to check one level of transitivity to save conses. */
928 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
929 LOG_LINKS (insn) = link;
931 /* Insn dependency, not data dependency. */
932 PUT_REG_NOTE_KIND (link, dep_type);
935 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
936 of INSN. Abort if not found. */
939 remove_dependence (insn, elem)
943 rtx prev, link, next;
946 for (prev = 0, link = LOG_LINKS (insn); link; link = next)
948 next = XEXP (link, 1);
949 if (XEXP (link, 0) == elem)
952 XEXP (prev, 1) = next;
954 LOG_LINKS (insn) = next;
956 XEXP (link, 1) = unused_insn_list;
957 unused_insn_list = link;
970 #ifndef INSN_SCHEDULING
972 schedule_insns (dump_file)
982 #define HAIFA_INLINE __inline
985 /* Computation of memory dependencies. */
987 /* The *_insns and *_mems are paired lists. Each pending memory operation
988 will have a pointer to the MEM rtx on one list and a pointer to the
989 containing insn on the other list in the same place in the list. */
991 /* We can't use add_dependence like the old code did, because a single insn
992 may have multiple memory accesses, and hence needs to be on the list
993 once for each memory access. Add_dependence won't let you add an insn
994 to a list more than once. */
996 /* An INSN_LIST containing all insns with pending read operations. */
997 static rtx pending_read_insns;
999 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
1000 static rtx pending_read_mems;
1002 /* An INSN_LIST containing all insns with pending write operations. */
1003 static rtx pending_write_insns;
1005 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
1006 static rtx pending_write_mems;
1008 /* Indicates the combined length of the two pending lists. We must prevent
1009 these lists from ever growing too large since the number of dependencies
1010 produced is at least O(N*N), and execution time is at least O(4*N*N), as
1011 a function of the length of these pending lists. */
1013 static int pending_lists_length;
1015 /* The last insn upon which all memory references must depend.
1016 This is an insn which flushed the pending lists, creating a dependency
1017 between it and all previously pending memory references. This creates
1018 a barrier (or a checkpoint) which no memory reference is allowed to cross.
1020 This includes all non constant CALL_INSNs. When we do interprocedural
1021 alias analysis, this restriction can be relaxed.
1022 This may also be an INSN that writes memory if the pending lists grow
1025 static rtx last_pending_memory_flush;
1027 /* The last function call we have seen. All hard regs, and, of course,
1028 the last function call, must depend on this. */
1030 static rtx last_function_call;
1032 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
1033 that does not already cross a call. We create dependencies between each
1034 of those insn and the next call insn, to ensure that they won't cross a call
1035 after scheduling is done. */
1037 static rtx sched_before_next_call;
1039 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1040 so that insns independent of the last scheduled insn will be preferred
1041 over dependent instructions. */
1043 static rtx last_scheduled_insn;
1045 /* Data structures for the computation of data dependences in a regions. We
1046 keep one copy of each of the declared above variables for each bb in the
1047 region. Before analyzing the data dependences for a bb, its variables
1048 are initialized as a function of the variables of its predecessors. When
1049 the analysis for a bb completes, we save the contents of each variable X
1050 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
1051 copied to bb_pending_read_insns[bb]. Another change is that few
1052 variables are now a list of insns rather than a single insn:
1053 last_pending_memory_flash, last_function_call, reg_last_sets. The
1054 manipulation of these variables was changed appropriately. */
1056 static rtx **bb_reg_last_uses;
1057 static rtx **bb_reg_last_sets;
1058 static rtx **bb_reg_last_clobbers;
1060 static rtx *bb_pending_read_insns;
1061 static rtx *bb_pending_read_mems;
1062 static rtx *bb_pending_write_insns;
1063 static rtx *bb_pending_write_mems;
1064 static int *bb_pending_lists_length;
1066 static rtx *bb_last_pending_memory_flush;
1067 static rtx *bb_last_function_call;
1068 static rtx *bb_sched_before_next_call;
1070 /* functions for construction of the control flow graph. */
1072 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1074 We decide not to build the control flow graph if there is possibly more
1075 than one entry to the function, if computed branches exist, of if we
1076 have nonlocal gotos. */
1079 is_cfg_nonregular ()
1085 /* If we have a label that could be the target of a nonlocal goto, then
1086 the cfg is not well structured. */
1087 if (nonlocal_goto_handler_labels)
1090 /* If we have any forced labels, then the cfg is not well structured. */
1094 /* If this function has a computed jump, then we consider the cfg
1095 not well structured. */
1096 if (current_function_has_computed_jump)
1099 /* If we have exception handlers, then we consider the cfg not well
1100 structured. ?!? We should be able to handle this now that flow.c
1101 computes an accurate cfg for EH. */
1102 if (exception_handler_labels)
1105 /* If we have non-jumping insns which refer to labels, then we consider
1106 the cfg not well structured. */
1107 /* check for labels referred to other thn by jumps */
1108 for (b = 0; b < n_basic_blocks; b++)
1109 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
1111 code = GET_CODE (insn);
1112 if (GET_RTX_CLASS (code) == 'i')
1116 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1117 if (REG_NOTE_KIND (note) == REG_LABEL)
1121 if (insn == BLOCK_END (b))
1125 /* All the tests passed. Consider the cfg well structured. */
1129 /* Build the control flow graph and set nr_edges.
1131 Instead of trying to build a cfg ourselves, we rely on flow to
1132 do it for us. Stamp out useless code (and bug) duplication.
1134 Return nonzero if an irregularity in the cfg is found which would
1135 prevent cross block scheduling. */
1138 build_control_flow (s_preds, s_succs, num_preds, num_succs)
1139 int_list_ptr *s_preds;
1140 int_list_ptr *s_succs;
1148 /* Count the number of edges in the cfg. */
1151 for (i = 0; i < n_basic_blocks; i++)
1153 nr_edges += num_succs[i];
1155 /* Unreachable loops with more than one basic block are detected
1156 during the DFS traversal in find_rgns.
1158 Unreachable loops with a single block are detected here. This
1159 test is redundant with the one in find_rgns, but it's much
1160 cheaper to go ahead and catch the trivial case here. */
1161 if (num_preds[i] == 0
1162 || (num_preds[i] == 1 && INT_LIST_VAL (s_preds[i]) == i))
1166 /* Account for entry/exit edges. */
1169 in_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
1170 out_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
1171 bzero ((char *) in_edges, n_basic_blocks * sizeof (int));
1172 bzero ((char *) out_edges, n_basic_blocks * sizeof (int));
1174 edge_table = (haifa_edge *) xmalloc ((nr_edges) * sizeof (haifa_edge));
1175 bzero ((char *) edge_table, ((nr_edges) * sizeof (haifa_edge)));
1178 for (i = 0; i < n_basic_blocks; i++)
1179 for (succ = s_succs[i]; succ; succ = succ->next)
1181 if (INT_LIST_VAL (succ) != EXIT_BLOCK)
1182 new_edge (i, INT_LIST_VAL (succ));
1185 /* increment by 1, since edge 0 is unused. */
1192 /* Record an edge in the control flow graph from SOURCE to TARGET.
1194 In theory, this is redundant with the s_succs computed above, but
1195 we have not converted all of haifa to use information from the
1199 new_edge (source, target)
1203 int curr_edge, fst_edge;
1205 /* check for duplicates */
1206 fst_edge = curr_edge = OUT_EDGES (source);
1209 if (FROM_BLOCK (curr_edge) == source
1210 && TO_BLOCK (curr_edge) == target)
1215 curr_edge = NEXT_OUT (curr_edge);
1217 if (fst_edge == curr_edge)
1223 FROM_BLOCK (e) = source;
1224 TO_BLOCK (e) = target;
1226 if (OUT_EDGES (source))
1228 next_edge = NEXT_OUT (OUT_EDGES (source));
1229 NEXT_OUT (OUT_EDGES (source)) = e;
1230 NEXT_OUT (e) = next_edge;
1234 OUT_EDGES (source) = e;
1238 if (IN_EDGES (target))
1240 next_edge = NEXT_IN (IN_EDGES (target));
1241 NEXT_IN (IN_EDGES (target)) = e;
1242 NEXT_IN (e) = next_edge;
1246 IN_EDGES (target) = e;
1252 /* BITSET macros for operations on the control flow graph. */
1254 /* Compute bitwise union of two bitsets. */
1255 #define BITSET_UNION(set1, set2, len) \
1256 do { register bitset tp = set1, sp = set2; \
1258 for (i = 0; i < len; i++) \
1259 *(tp++) |= *(sp++); } while (0)
1261 /* Compute bitwise intersection of two bitsets. */
1262 #define BITSET_INTER(set1, set2, len) \
1263 do { register bitset tp = set1, sp = set2; \
1265 for (i = 0; i < len; i++) \
1266 *(tp++) &= *(sp++); } while (0)
1268 /* Compute bitwise difference of two bitsets. */
1269 #define BITSET_DIFFER(set1, set2, len) \
1270 do { register bitset tp = set1, sp = set2; \
1272 for (i = 0; i < len; i++) \
1273 *(tp++) &= ~*(sp++); } while (0)
1275 /* Inverts every bit of bitset 'set' */
1276 #define BITSET_INVERT(set, len) \
1277 do { register bitset tmpset = set; \
1279 for (i = 0; i < len; i++, tmpset++) \
1280 *tmpset = ~*tmpset; } while (0)
1282 /* Turn on the index'th bit in bitset set. */
1283 #define BITSET_ADD(set, index, len) \
1285 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1288 set[index/HOST_BITS_PER_WIDE_INT] |= \
1289 1 << (index % HOST_BITS_PER_WIDE_INT); \
1292 /* Turn off the index'th bit in set. */
1293 #define BITSET_REMOVE(set, index, len) \
1295 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1298 set[index/HOST_BITS_PER_WIDE_INT] &= \
1299 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1303 /* Check if the index'th bit in bitset set is on. */
1306 bitset_member (set, index, len)
1310 if (index >= HOST_BITS_PER_WIDE_INT * len)
1312 return (set[index / HOST_BITS_PER_WIDE_INT] &
1313 1 << (index % HOST_BITS_PER_WIDE_INT)) ? 1 : 0;
1317 /* Translate a bit-set SET to a list BL of the bit-set members. */
1320 extract_bitlst (set, len, bl)
1326 unsigned HOST_WIDE_INT word;
1328 /* bblst table space is reused in each call to extract_bitlst */
1329 bitlst_table_last = 0;
1331 bl->first_member = &bitlst_table[bitlst_table_last];
1334 for (i = 0; i < len; i++)
1337 offset = i * HOST_BITS_PER_WIDE_INT;
1338 for (j = 0; word; j++)
1342 bitlst_table[bitlst_table_last++] = offset;
1353 /* functions for the construction of regions */
1355 /* Print the regions, for debugging purposes. Callable from debugger. */
1362 fprintf (dump, "\n;; ------------ REGIONS ----------\n\n");
1363 for (rgn = 0; rgn < nr_regions; rgn++)
1365 fprintf (dump, ";;\trgn %d nr_blocks %d:\n", rgn,
1366 rgn_table[rgn].rgn_nr_blocks);
1367 fprintf (dump, ";;\tbb/block: ");
1369 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
1371 current_blocks = RGN_BLOCKS (rgn);
1373 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
1376 fprintf (dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
1379 fprintf (dump, "\n\n");
1384 /* Build a single block region for each basic block in the function.
1385 This allows for using the same code for interblock and basic block
1389 find_single_block_region ()
1393 for (i = 0; i < n_basic_blocks; i++)
1395 rgn_bb_table[i] = i;
1396 RGN_NR_BLOCKS (i) = 1;
1398 CONTAINING_RGN (i) = i;
1399 BLOCK_TO_BB (i) = 0;
1401 nr_regions = n_basic_blocks;
1405 /* Update number of blocks and the estimate for number of insns
1406 in the region. Return 1 if the region is "too large" for interblock
1407 scheduling (compile time considerations), otherwise return 0. */
1410 too_large (block, num_bbs, num_insns)
1411 int block, *num_bbs, *num_insns;
1414 (*num_insns) += (INSN_LUID (BLOCK_END (block)) -
1415 INSN_LUID (BLOCK_HEAD (block)));
1416 if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
1423 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1424 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1425 loop containing blk. */
1426 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1428 if (max_hdr[blk] == -1) \
1429 max_hdr[blk] = hdr; \
1430 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1431 RESET_BIT (inner, hdr); \
1432 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1434 RESET_BIT (inner,max_hdr[blk]); \
1435 max_hdr[blk] = hdr; \
1440 /* Find regions for interblock scheduling.
1442 A region for scheduling can be:
1444 * A loop-free procedure, or
1446 * A reducible inner loop, or
1448 * A basic block not contained in any other region.
1451 ?!? In theory we could build other regions based on extended basic
1452 blocks or reverse extended basic blocks. Is it worth the trouble?
1454 Loop blocks that form a region are put into the region's block list
1455 in topological order.
1457 This procedure stores its results into the following global (ick) variables
1466 We use dominator relationships to avoid making regions out of non-reducible
1469 This procedure needs to be converted to work on pred/succ lists instead
1470 of edge tables. That would simplify it somewhat. */
1473 find_rgns (s_preds, s_succs, num_preds, num_succs, dom)
1474 int_list_ptr *s_preds;
1475 int_list_ptr *s_succs;
1480 int *max_hdr, *dfs_nr, *stack, *queue, *degree;
1482 int node, child, loop_head, i, head, tail;
1483 int count = 0, sp, idx = 0, current_edge = out_edges[0];
1484 int num_bbs, num_insns, unreachable;
1485 int too_large_failure;
1487 /* Note if an edge has been passed. */
1490 /* Note if a block is a natural loop header. */
1493 /* Note if a block is an natural inner loop header. */
1496 /* Note if a block is in the block queue. */
1499 /* Note if a block is in the block queue. */
1502 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1503 and a mapping from block to its loop header (if the block is contained
1504 in a loop, else -1).
1506 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1507 be used as inputs to the second traversal.
1509 STACK, SP and DFS_NR are only used during the first traversal. */
1511 /* Allocate and initialize variables for the first traversal. */
1512 max_hdr = (int *) alloca (n_basic_blocks * sizeof (int));
1513 dfs_nr = (int *) alloca (n_basic_blocks * sizeof (int));
1514 bzero ((char *) dfs_nr, n_basic_blocks * sizeof (int));
1515 stack = (int *) alloca (nr_edges * sizeof (int));
1517 inner = sbitmap_alloc (n_basic_blocks);
1518 sbitmap_ones (inner);
1520 header = sbitmap_alloc (n_basic_blocks);
1521 sbitmap_zero (header);
1523 passed = sbitmap_alloc (nr_edges);
1524 sbitmap_zero (passed);
1526 in_queue = sbitmap_alloc (n_basic_blocks);
1527 sbitmap_zero (in_queue);
1529 in_stack = sbitmap_alloc (n_basic_blocks);
1530 sbitmap_zero (in_stack);
1532 for (i = 0; i < n_basic_blocks; i++)
1535 /* DFS traversal to find inner loops in the cfg. */
1540 if (current_edge == 0 || TEST_BIT (passed, current_edge))
1542 /* We have reached a leaf node or a node that was already
1543 processed. Pop edges off the stack until we find
1544 an edge that has not yet been processed. */
1546 && (current_edge == 0 || TEST_BIT (passed, current_edge)))
1548 /* Pop entry off the stack. */
1549 current_edge = stack[sp--];
1550 node = FROM_BLOCK (current_edge);
1551 child = TO_BLOCK (current_edge);
1552 RESET_BIT (in_stack, child);
1553 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1554 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1555 current_edge = NEXT_OUT (current_edge);
1558 /* See if have finished the DFS tree traversal. */
1559 if (sp < 0 && TEST_BIT (passed, current_edge))
1562 /* Nope, continue the traversal with the popped node. */
1566 /* Process a node. */
1567 node = FROM_BLOCK (current_edge);
1568 child = TO_BLOCK (current_edge);
1569 SET_BIT (in_stack, node);
1570 dfs_nr[node] = ++count;
1572 /* If the successor is in the stack, then we've found a loop.
1573 Mark the loop, if it is not a natural loop, then it will
1574 be rejected during the second traversal. */
1575 if (TEST_BIT (in_stack, child))
1578 SET_BIT (header, child);
1579 UPDATE_LOOP_RELATIONS (node, child);
1580 SET_BIT (passed, current_edge);
1581 current_edge = NEXT_OUT (current_edge);
1585 /* If the child was already visited, then there is no need to visit
1586 it again. Just update the loop relationships and restart
1590 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1591 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1592 SET_BIT (passed, current_edge);
1593 current_edge = NEXT_OUT (current_edge);
1597 /* Push an entry on the stack and continue DFS traversal. */
1598 stack[++sp] = current_edge;
1599 SET_BIT (passed, current_edge);
1600 current_edge = OUT_EDGES (child);
1603 /* Another check for unreachable blocks. The earlier test in
1604 is_cfg_nonregular only finds unreachable blocks that do not
1607 The DFS traversal will mark every block that is reachable from
1608 the entry node by placing a nonzero value in dfs_nr. Thus if
1609 dfs_nr is zero for any block, then it must be unreachable. */
1611 for (i = 0; i < n_basic_blocks; i++)
1618 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1619 to hold degree counts. */
1622 /* Compute the in-degree of every block in the graph */
1623 for (i = 0; i < n_basic_blocks; i++)
1624 degree[i] = num_preds[i];
1626 /* Do not perform region scheduling if there are any unreachable
1631 SET_BIT (header, 0);
1633 /* Second travsersal:find reducible inner loops and topologically sort
1634 block of each region. */
1636 queue = (int *) alloca (n_basic_blocks * sizeof (int));
1638 /* Find blocks which are inner loop headers. We still have non-reducible
1639 loops to consider at this point. */
1640 for (i = 0; i < n_basic_blocks; i++)
1642 if (TEST_BIT (header, i) && TEST_BIT (inner, i))
1647 /* Now check that the loop is reducible. We do this separate
1648 from finding inner loops so that we do not find a reducible
1649 loop which contains an inner non-reducible loop.
1651 A simple way to find reducible/natrual loops is to verify
1652 that each block in the loop is dominated by the loop
1655 If there exists a block that is not dominated by the loop
1656 header, then the block is reachable from outside the loop
1657 and thus the loop is not a natural loop. */
1658 for (j = 0; j < n_basic_blocks; j++)
1660 /* First identify blocks in the loop, except for the loop
1662 if (i == max_hdr[j] && i != j)
1664 /* Now verify that the block is dominated by the loop
1666 if (!TEST_BIT (dom[j], i))
1671 /* If we exited the loop early, then I is the header of a non
1672 reducible loop and we should quit processing it now. */
1673 if (j != n_basic_blocks)
1676 /* I is a header of an inner loop, or block 0 in a subroutine
1677 with no loops at all. */
1679 too_large_failure = 0;
1680 loop_head = max_hdr[i];
1682 /* Decrease degree of all I's successors for topological
1684 for (ps = s_succs[i]; ps; ps = ps->next)
1685 if (INT_LIST_VAL (ps) != EXIT_BLOCK
1686 && INT_LIST_VAL (ps) != ENTRY_BLOCK)
1687 --degree[INT_LIST_VAL(ps)];
1689 /* Estimate # insns, and count # blocks in the region. */
1691 num_insns = (INSN_LUID (BLOCK_END (i))
1692 - INSN_LUID (BLOCK_HEAD (i)));
1695 /* Find all loop latches (blocks which back edges to the loop
1696 header) or all the leaf blocks in the cfg has no loops.
1698 Place those blocks into the queue. */
1701 for (j = 0; j < n_basic_blocks; j++)
1702 /* Leaf nodes have only a single successor which must
1704 if (num_succs[j] == 1
1705 && INT_LIST_VAL (s_succs[j]) == EXIT_BLOCK)
1708 SET_BIT (in_queue, j);
1710 if (too_large (j, &num_bbs, &num_insns))
1712 too_large_failure = 1;
1721 for (ps = s_preds[i]; ps; ps = ps->next)
1723 node = INT_LIST_VAL (ps);
1725 if (node == ENTRY_BLOCK || node == EXIT_BLOCK)
1728 if (max_hdr[node] == loop_head && node != i)
1730 /* This is a loop latch. */
1731 queue[++tail] = node;
1732 SET_BIT (in_queue, node);
1734 if (too_large (node, &num_bbs, &num_insns))
1736 too_large_failure = 1;
1744 /* Now add all the blocks in the loop to the queue.
1746 We know the loop is a natural loop; however the algorithm
1747 above will not always mark certain blocks as being in the
1756 The algorithm in the DFS traversal may not mark B & D as part
1757 of the loop (ie they will not have max_hdr set to A).
1759 We know they can not be loop latches (else they would have
1760 had max_hdr set since they'd have a backedge to a dominator
1761 block). So we don't need them on the initial queue.
1763 We know they are part of the loop because they are dominated
1764 by the loop header and can be reached by a backwards walk of
1765 the edges starting with nodes on the initial queue.
1767 It is safe and desirable to include those nodes in the
1768 loop/scheduling region. To do so we would need to decrease
1769 the degree of a node if it is the target of a backedge
1770 within the loop itself as the node is placed in the queue.
1772 We do not do this because I'm not sure that the actual
1773 scheduling code will properly handle this case. ?!? */
1775 while (head < tail && !too_large_failure)
1778 child = queue[++head];
1780 for (ps = s_preds[child]; ps; ps = ps->next)
1782 node = INT_LIST_VAL (ps);
1784 /* See discussion above about nodes not marked as in
1785 this loop during the initial DFS traversal. */
1786 if (node == ENTRY_BLOCK || node == EXIT_BLOCK
1787 || max_hdr[node] != loop_head)
1792 else if (!TEST_BIT (in_queue, node) && node != i)
1794 queue[++tail] = node;
1795 SET_BIT (in_queue, node);
1797 if (too_large (node, &num_bbs, &num_insns))
1799 too_large_failure = 1;
1806 if (tail >= 0 && !too_large_failure)
1808 /* Place the loop header into list of region blocks. */
1810 rgn_bb_table[idx] = i;
1811 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1812 RGN_BLOCKS (nr_regions) = idx++;
1813 CONTAINING_RGN (i) = nr_regions;
1814 BLOCK_TO_BB (i) = count = 0;
1816 /* Remove blocks from queue[] when their in degree becomes
1817 zero. Repeat until no blocks are left on the list. This
1818 produces a topological list of blocks in the region. */
1825 child = queue[head];
1826 if (degree[child] == 0)
1829 rgn_bb_table[idx++] = child;
1830 BLOCK_TO_BB (child) = ++count;
1831 CONTAINING_RGN (child) = nr_regions;
1832 queue[head] = queue[tail--];
1834 for (ps = s_succs[child]; ps; ps = ps->next)
1835 if (INT_LIST_VAL (ps) != ENTRY_BLOCK
1836 && INT_LIST_VAL (ps) != EXIT_BLOCK)
1837 --degree[INT_LIST_VAL (ps)];
1848 /* Any block that did not end up in a region is placed into a region
1850 for (i = 0; i < n_basic_blocks; i++)
1853 rgn_bb_table[idx] = i;
1854 RGN_NR_BLOCKS (nr_regions) = 1;
1855 RGN_BLOCKS (nr_regions) = idx++;
1856 CONTAINING_RGN (i) = nr_regions++;
1857 BLOCK_TO_BB (i) = 0;
1868 /* functions for regions scheduling information */
1870 /* Compute dominators, probability, and potential-split-edges of bb.
1871 Assume that these values were already computed for bb's predecessors. */
1874 compute_dom_prob_ps (bb)
1877 int nxt_in_edge, fst_in_edge, pred;
1878 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1881 if (IS_RGN_ENTRY (bb))
1883 BITSET_ADD (dom[bb], 0, bbset_size);
1888 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1890 /* intialize dom[bb] to '111..1' */
1891 BITSET_INVERT (dom[bb], bbset_size);
1895 pred = FROM_BLOCK (nxt_in_edge);
1896 BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
1898 BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
1901 BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
1904 nr_rgn_out_edges = 0;
1905 fst_out_edge = OUT_EDGES (pred);
1906 nxt_out_edge = NEXT_OUT (fst_out_edge);
1907 BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
1910 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
1912 /* the successor doesn't belong the region? */
1913 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1914 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1917 while (fst_out_edge != nxt_out_edge)
1920 /* the successor doesn't belong the region? */
1921 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1922 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1924 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
1925 nxt_out_edge = NEXT_OUT (nxt_out_edge);
1929 /* now nr_rgn_out_edges is the number of region-exit edges from pred,
1930 and nr_out_edges will be the number of pred out edges not leaving
1932 nr_out_edges -= nr_rgn_out_edges;
1933 if (nr_rgn_out_edges > 0)
1934 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1936 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1937 nxt_in_edge = NEXT_IN (nxt_in_edge);
1939 while (fst_in_edge != nxt_in_edge);
1941 BITSET_ADD (dom[bb], bb, bbset_size);
1942 BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
1944 if (sched_verbose >= 2)
1945 fprintf (dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb), (int) (100.0 * prob[bb]));
1946 } /* compute_dom_prob_ps */
1948 /* functions for target info */
1950 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1951 Note that bb_trg dominates bb_src. */
1954 split_edges (bb_src, bb_trg, bl)
1959 int es = edgeset_size;
1960 edgeset src = (edgeset) alloca (es * sizeof (HOST_WIDE_INT));
1963 src[es] = (pot_split[bb_src])[es];
1964 BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
1965 extract_bitlst (src, edgeset_size, bl);
1969 /* Find the valid candidate-source-blocks for the target block TRG, compute
1970 their probability, and check if they are speculative or not.
1971 For speculative sources, compute their update-blocks and split-blocks. */
1974 compute_trg_info (trg)
1977 register candidate *sp;
1979 int check_block, update_idx;
1980 int i, j, k, fst_edge, nxt_edge;
1982 /* define some of the fields for the target bb as well */
1983 sp = candidate_table + trg;
1985 sp->is_speculative = 0;
1988 for (i = trg + 1; i < current_nr_blocks; i++)
1990 sp = candidate_table + i;
1992 sp->is_valid = IS_DOMINATED (i, trg);
1995 sp->src_prob = GET_SRC_PROB (i, trg);
1996 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
2001 split_edges (i, trg, &el);
2002 sp->is_speculative = (el.nr_members) ? 1 : 0;
2003 if (sp->is_speculative && !flag_schedule_speculative)
2009 sp->split_bbs.first_member = &bblst_table[bblst_last];
2010 sp->split_bbs.nr_members = el.nr_members;
2011 for (j = 0; j < el.nr_members; bblst_last++, j++)
2012 bblst_table[bblst_last] =
2013 TO_BLOCK (rgn_edges[el.first_member[j]]);
2014 sp->update_bbs.first_member = &bblst_table[bblst_last];
2016 for (j = 0; j < el.nr_members; j++)
2018 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
2019 fst_edge = nxt_edge = OUT_EDGES (check_block);
2022 for (k = 0; k < el.nr_members; k++)
2023 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
2026 if (k >= el.nr_members)
2028 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
2032 nxt_edge = NEXT_OUT (nxt_edge);
2034 while (fst_edge != nxt_edge);
2036 sp->update_bbs.nr_members = update_idx;
2041 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
2043 sp->is_speculative = 0;
2047 } /* compute_trg_info */
2050 /* Print candidates info, for debugging purposes. Callable from debugger. */
2056 if (!candidate_table[i].is_valid)
2059 if (candidate_table[i].is_speculative)
2062 fprintf (dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
2064 fprintf (dump, "split path: ");
2065 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
2067 int b = candidate_table[i].split_bbs.first_member[j];
2069 fprintf (dump, " %d ", b);
2071 fprintf (dump, "\n");
2073 fprintf (dump, "update path: ");
2074 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
2076 int b = candidate_table[i].update_bbs.first_member[j];
2078 fprintf (dump, " %d ", b);
2080 fprintf (dump, "\n");
2084 fprintf (dump, " src %d equivalent\n", BB_TO_BLOCK (i));
2089 /* Print candidates info, for debugging purposes. Callable from debugger. */
2092 debug_candidates (trg)
2097 fprintf (dump, "----------- candidate table: target: b=%d bb=%d ---\n",
2098 BB_TO_BLOCK (trg), trg);
2099 for (i = trg + 1; i < current_nr_blocks; i++)
2100 debug_candidate (i);
2104 /* functions for speculative scheduing */
2106 /* Return 0 if x is a set of a register alive in the beginning of one
2107 of the split-blocks of src, otherwise return 1. */
2110 check_live_1 (src, x)
2116 register rtx reg = SET_DEST (x);
2121 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2122 || GET_CODE (reg) == SIGN_EXTRACT
2123 || GET_CODE (reg) == STRICT_LOW_PART)
2124 reg = XEXP (reg, 0);
2126 if (GET_CODE (reg) == PARALLEL
2127 && GET_MODE (reg) == BLKmode)
2130 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2131 if (check_live_1 (src, XVECEXP (reg, 0, i)))
2136 if (GET_CODE (reg) != REG)
2139 regno = REGNO (reg);
2141 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2143 /* Global registers are assumed live */
2148 if (regno < FIRST_PSEUDO_REGISTER)
2150 /* check for hard registers */
2151 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2154 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2156 int b = candidate_table[src].split_bbs.first_member[i];
2158 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
2168 /* check for psuedo registers */
2169 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2171 int b = candidate_table[src].split_bbs.first_member[i];
2173 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
2185 /* If x is a set of a register R, mark that R is alive in the beginning
2186 of every update-block of src. */
2189 update_live_1 (src, x)
2195 register rtx reg = SET_DEST (x);
2200 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2201 || GET_CODE (reg) == SIGN_EXTRACT
2202 || GET_CODE (reg) == STRICT_LOW_PART)
2203 reg = XEXP (reg, 0);
2205 if (GET_CODE (reg) == PARALLEL
2206 && GET_MODE (reg) == BLKmode)
2209 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2210 update_live_1 (src, XVECEXP (reg, 0, i));
2214 if (GET_CODE (reg) != REG)
2217 /* Global registers are always live, so the code below does not apply
2220 regno = REGNO (reg);
2222 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
2224 if (regno < FIRST_PSEUDO_REGISTER)
2226 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2229 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2231 int b = candidate_table[src].update_bbs.first_member[i];
2233 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
2240 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2242 int b = candidate_table[src].update_bbs.first_member[i];
2244 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
2251 /* Return 1 if insn can be speculatively moved from block src to trg,
2252 otherwise return 0. Called before first insertion of insn to
2253 ready-list or before the scheduling. */
2256 check_live (insn, src)
2260 /* find the registers set by instruction */
2261 if (GET_CODE (PATTERN (insn)) == SET
2262 || GET_CODE (PATTERN (insn)) == CLOBBER)
2263 return check_live_1 (src, PATTERN (insn));
2264 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2267 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2268 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2269 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2270 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
2280 /* Update the live registers info after insn was moved speculatively from
2281 block src to trg. */
2284 update_live (insn, src)
2288 /* find the registers set by instruction */
2289 if (GET_CODE (PATTERN (insn)) == SET
2290 || GET_CODE (PATTERN (insn)) == CLOBBER)
2291 update_live_1 (src, PATTERN (insn));
2292 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2295 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2296 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2297 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2298 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
2302 /* Exception Free Loads:
2304 We define five classes of speculative loads: IFREE, IRISKY,
2305 PFREE, PRISKY, and MFREE.
2307 IFREE loads are loads that are proved to be exception-free, just
2308 by examining the load insn. Examples for such loads are loads
2309 from TOC and loads of global data.
2311 IRISKY loads are loads that are proved to be exception-risky,
2312 just by examining the load insn. Examples for such loads are
2313 volatile loads and loads from shared memory.
2315 PFREE loads are loads for which we can prove, by examining other
2316 insns, that they are exception-free. Currently, this class consists
2317 of loads for which we are able to find a "similar load", either in
2318 the target block, or, if only one split-block exists, in that split
2319 block. Load2 is similar to load1 if both have same single base
2320 register. We identify only part of the similar loads, by finding
2321 an insn upon which both load1 and load2 have a DEF-USE dependence.
2323 PRISKY loads are loads for which we can prove, by examining other
2324 insns, that they are exception-risky. Currently we have two proofs for
2325 such loads. The first proof detects loads that are probably guarded by a
2326 test on the memory address. This proof is based on the
2327 backward and forward data dependence information for the region.
2328 Let load-insn be the examined load.
2329 Load-insn is PRISKY iff ALL the following hold:
2331 - insn1 is not in the same block as load-insn
2332 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2333 - test-insn is either a compare or a branch, not in the same block as load-insn
2334 - load-insn is reachable from test-insn
2335 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2337 This proof might fail when the compare and the load are fed
2338 by an insn not in the region. To solve this, we will add to this
2339 group all loads that have no input DEF-USE dependence.
2341 The second proof detects loads that are directly or indirectly
2342 fed by a speculative load. This proof is affected by the
2343 scheduling process. We will use the flag fed_by_spec_load.
2344 Initially, all insns have this flag reset. After a speculative
2345 motion of an insn, if insn is either a load, or marked as
2346 fed_by_spec_load, we will also mark as fed_by_spec_load every
2347 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2348 load which is fed_by_spec_load is also PRISKY.
2350 MFREE (maybe-free) loads are all the remaining loads. They may be
2351 exception-free, but we cannot prove it.
2353 Now, all loads in IFREE and PFREE classes are considered
2354 exception-free, while all loads in IRISKY and PRISKY classes are
2355 considered exception-risky. As for loads in the MFREE class,
2356 these are considered either exception-free or exception-risky,
2357 depending on whether we are pessimistic or optimistic. We have
2358 to take the pessimistic approach to assure the safety of
2359 speculative scheduling, but we can take the optimistic approach
2360 by invoking the -fsched_spec_load_dangerous option. */
2362 enum INSN_TRAP_CLASS
2364 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
2365 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
2368 #define WORST_CLASS(class1, class2) \
2369 ((class1 > class2) ? class1 : class2)
2371 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between */
2372 /* some speculatively moved load insn and this one. */
2373 char *fed_by_spec_load;
2376 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2377 #define IS_REACHABLE(bb_from, bb_to) \
2379 || IS_RGN_ENTRY (bb_from) \
2380 || (bitset_member (ancestor_edges[bb_to], \
2381 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2383 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2384 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2386 /* Non-zero iff the address is comprised from at most 1 register */
2387 #define CONST_BASED_ADDRESS_P(x) \
2388 (GET_CODE (x) == REG \
2389 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2390 || (GET_CODE (x) == LO_SUM)) \
2391 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2392 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2394 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2397 set_spec_fed (load_insn)
2402 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
2403 if (GET_MODE (link) == VOIDmode)
2404 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
2405 } /* set_spec_fed */
2407 /* On the path from the insn to load_insn_bb, find a conditional branch */
2408 /* depending on insn, that guards the speculative load. */
2411 find_conditional_protection (insn, load_insn_bb)
2417 /* iterate through DEF-USE forward dependences */
2418 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2420 rtx next = XEXP (link, 0);
2421 if ((CONTAINING_RGN (INSN_BLOCK (next)) ==
2422 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
2423 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
2424 && load_insn_bb != INSN_BB (next)
2425 && GET_MODE (link) == VOIDmode
2426 && (GET_CODE (next) == JUMP_INSN
2427 || find_conditional_protection (next, load_insn_bb)))
2431 } /* find_conditional_protection */
2433 /* Returns 1 if the same insn1 that participates in the computation
2434 of load_insn's address is feeding a conditional branch that is
2435 guarding on load_insn. This is true if we find a the two DEF-USE
2437 insn1 -> ... -> conditional-branch
2438 insn1 -> ... -> load_insn,
2439 and if a flow path exist:
2440 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2441 and if insn1 is on the path
2442 region-entry -> ... -> bb_trg -> ... load_insn.
2444 Locate insn1 by climbing on LOG_LINKS from load_insn.
2445 Locate the branch by following INSN_DEPEND from insn1. */
2448 is_conditionally_protected (load_insn, bb_src, bb_trg)
2454 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
2456 rtx insn1 = XEXP (link, 0);
2458 /* must be a DEF-USE dependence upon non-branch */
2459 if (GET_MODE (link) != VOIDmode
2460 || GET_CODE (insn1) == JUMP_INSN)
2463 /* must exist a path: region-entry -> ... -> bb_trg -> ... load_insn */
2464 if (INSN_BB (insn1) == bb_src
2465 || (CONTAINING_RGN (INSN_BLOCK (insn1))
2466 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
2467 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
2468 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
2471 /* now search for the conditional-branch */
2472 if (find_conditional_protection (insn1, bb_src))
2475 /* recursive step: search another insn1, "above" current insn1. */
2476 return is_conditionally_protected (insn1, bb_src, bb_trg);
2479 /* the chain does not exsist */
2481 } /* is_conditionally_protected */
2483 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2484 load_insn can move speculatively from bb_src to bb_trg. All the
2485 following must hold:
2487 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2488 (2) load_insn and load1 have a def-use dependence upon
2489 the same insn 'insn1'.
2490 (3) either load2 is in bb_trg, or:
2491 - there's only one split-block, and
2492 - load1 is on the escape path, and
2494 From all these we can conclude that the two loads access memory
2495 addresses that differ at most by a constant, and hence if moving
2496 load_insn would cause an exception, it would have been caused by
2500 is_pfree (load_insn, bb_src, bb_trg)
2505 register candidate *candp = candidate_table + bb_src;
2507 if (candp->split_bbs.nr_members != 1)
2508 /* must have exactly one escape block */
2511 for (back_link = LOG_LINKS (load_insn);
2512 back_link; back_link = XEXP (back_link, 1))
2514 rtx insn1 = XEXP (back_link, 0);
2516 if (GET_MODE (back_link) == VOIDmode)
2518 /* found a DEF-USE dependence (insn1, load_insn) */
2521 for (fore_link = INSN_DEPEND (insn1);
2522 fore_link; fore_link = XEXP (fore_link, 1))
2524 rtx insn2 = XEXP (fore_link, 0);
2525 if (GET_MODE (fore_link) == VOIDmode)
2527 /* found a DEF-USE dependence (insn1, insn2) */
2528 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
2529 /* insn2 not guaranteed to be a 1 base reg load */
2532 if (INSN_BB (insn2) == bb_trg)
2533 /* insn2 is the similar load, in the target block */
2536 if (*(candp->split_bbs.first_member) == INSN_BLOCK (insn2))
2537 /* insn2 is a similar load, in a split-block */
2544 /* couldn't find a similar load */
2548 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2549 as found by analyzing insn's expression. */
2552 may_trap_exp (x, is_store)
2560 code = GET_CODE (x);
2570 /* The insn uses memory */
2571 /* a volatile load */
2572 if (MEM_VOLATILE_P (x))
2574 /* an exception-free load */
2575 if (!may_trap_p (x))
2577 /* a load with 1 base register, to be further checked */
2578 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
2579 return PFREE_CANDIDATE;
2580 /* no info on the load, to be further checked */
2581 return PRISKY_CANDIDATE;
2586 int i, insn_class = TRAP_FREE;
2588 /* neither store nor load, check if it may cause a trap */
2591 /* recursive step: walk the insn... */
2592 fmt = GET_RTX_FORMAT (code);
2593 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2597 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
2598 insn_class = WORST_CLASS (insn_class, tmp_class);
2600 else if (fmt[i] == 'E')
2603 for (j = 0; j < XVECLEN (x, i); j++)
2605 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
2606 insn_class = WORST_CLASS (insn_class, tmp_class);
2607 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2611 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2616 } /* may_trap_exp */
2619 /* Classifies insn for the purpose of verifying that it can be
2620 moved speculatively, by examining it's patterns, returning:
2621 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2622 TRAP_FREE: non-load insn.
2623 IFREE: load from a globaly safe location.
2624 IRISKY: volatile load.
2625 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2626 being either PFREE or PRISKY. */
2629 haifa_classify_insn (insn)
2632 rtx pat = PATTERN (insn);
2633 int tmp_class = TRAP_FREE;
2634 int insn_class = TRAP_FREE;
2637 if (GET_CODE (pat) == PARALLEL)
2639 int i, len = XVECLEN (pat, 0);
2641 for (i = len - 1; i >= 0; i--)
2643 code = GET_CODE (XVECEXP (pat, 0, i));
2647 /* test if it is a 'store' */
2648 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
2651 /* test if it is a store */
2652 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
2653 if (tmp_class == TRAP_RISKY)
2655 /* test if it is a load */
2657 WORST_CLASS (tmp_class,
2658 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 0));
2661 tmp_class = TRAP_RISKY;
2665 insn_class = WORST_CLASS (insn_class, tmp_class);
2666 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2672 code = GET_CODE (pat);
2676 /* test if it is a 'store' */
2677 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
2680 /* test if it is a store */
2681 tmp_class = may_trap_exp (SET_DEST (pat), 1);
2682 if (tmp_class == TRAP_RISKY)
2684 /* test if it is a load */
2686 WORST_CLASS (tmp_class,
2687 may_trap_exp (SET_SRC (pat), 0));
2690 tmp_class = TRAP_RISKY;
2694 insn_class = tmp_class;
2699 } /* haifa_classify_insn */
2701 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2702 a load moved speculatively, or if load_insn is protected by
2703 a compare on load_insn's address). */
2706 is_prisky (load_insn, bb_src, bb_trg)
2710 if (FED_BY_SPEC_LOAD (load_insn))
2713 if (LOG_LINKS (load_insn) == NULL)
2714 /* dependence may 'hide' out of the region. */
2717 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2723 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2724 Return 1 if insn is exception-free (and the motion is valid)
2728 is_exception_free (insn, bb_src, bb_trg)
2732 int insn_class = haifa_classify_insn (insn);
2734 /* handle non-load insns */
2745 if (!flag_schedule_speculative_load)
2747 IS_LOAD_INSN (insn) = 1;
2754 case PFREE_CANDIDATE:
2755 if (is_pfree (insn, bb_src, bb_trg))
2757 /* don't 'break' here: PFREE-candidate is also PRISKY-candidate */
2758 case PRISKY_CANDIDATE:
2759 if (!flag_schedule_speculative_load_dangerous
2760 || is_prisky (insn, bb_src, bb_trg))
2766 return flag_schedule_speculative_load_dangerous;
2767 } /* is_exception_free */
2770 /* Process an insn's memory dependencies. There are four kinds of
2773 (0) read dependence: read follows read
2774 (1) true dependence: read follows write
2775 (2) anti dependence: write follows read
2776 (3) output dependence: write follows write
2778 We are careful to build only dependencies which actually exist, and
2779 use transitivity to avoid building too many links. */
2781 /* Return the INSN_LIST containing INSN in LIST, or NULL
2782 if LIST does not contain INSN. */
2784 HAIFA_INLINE static rtx
2785 find_insn_list (insn, list)
2791 if (XEXP (list, 0) == insn)
2793 list = XEXP (list, 1);
2799 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 otherwise. */
2801 HAIFA_INLINE static char
2802 find_insn_mem_list (insn, x, list, list1)
2808 if (XEXP (list, 0) == insn
2809 && XEXP (list1, 0) == x)
2811 list = XEXP (list, 1);
2812 list1 = XEXP (list1, 1);
2818 /* Compute the function units used by INSN. This caches the value
2819 returned by function_units_used. A function unit is encoded as the
2820 unit number if the value is non-negative and the compliment of a
2821 mask if the value is negative. A function unit index is the
2822 non-negative encoding. */
2824 HAIFA_INLINE static int
2828 register int unit = INSN_UNIT (insn);
2832 recog_memoized (insn);
2834 /* A USE insn, or something else we don't need to understand.
2835 We can't pass these directly to function_units_used because it will
2836 trigger a fatal error for unrecognizable insns. */
2837 if (INSN_CODE (insn) < 0)
2841 unit = function_units_used (insn);
2842 /* Increment non-negative values so we can cache zero. */
2846 /* We only cache 16 bits of the result, so if the value is out of
2847 range, don't cache it. */
2848 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
2850 || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
2851 INSN_UNIT (insn) = unit;
2853 return (unit > 0 ? unit - 1 : unit);
2856 /* Compute the blockage range for executing INSN on UNIT. This caches
2857 the value returned by the blockage_range_function for the unit.
2858 These values are encoded in an int where the upper half gives the
2859 minimum value and the lower half gives the maximum value. */
2861 HAIFA_INLINE static unsigned int
2862 blockage_range (unit, insn)
2866 unsigned int blockage = INSN_BLOCKAGE (insn);
2869 if ((int) UNIT_BLOCKED (blockage) != unit + 1)
2871 range = function_units[unit].blockage_range_function (insn);
2872 /* We only cache the blockage range for one unit and then only if
2874 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
2875 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
2878 range = BLOCKAGE_RANGE (blockage);
2883 /* A vector indexed by function unit instance giving the last insn to use
2884 the unit. The value of the function unit instance index for unit U
2885 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2886 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2888 /* A vector indexed by function unit instance giving the minimum time when
2889 the unit will unblock based on the maximum blockage cost. */
2890 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2892 /* A vector indexed by function unit number giving the number of insns
2893 that remain to use the unit. */
2894 static int unit_n_insns[FUNCTION_UNITS_SIZE];
2896 /* Reset the function unit state to the null state. */
2901 bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
2902 bzero ((char *) unit_tick, sizeof (unit_tick));
2903 bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
2906 /* Return the issue-delay of an insn */
2908 HAIFA_INLINE static int
2909 insn_issue_delay (insn)
2913 int unit = insn_unit (insn);
2915 /* efficiency note: in fact, we are working 'hard' to compute a
2916 value that was available in md file, and is not available in
2917 function_units[] structure. It would be nice to have this
2918 value there, too. */
2921 if (function_units[unit].blockage_range_function &&
2922 function_units[unit].blockage_function)
2923 delay = function_units[unit].blockage_function (insn, insn);
2926 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2927 if ((unit & 1) != 0 && function_units[i].blockage_range_function
2928 && function_units[i].blockage_function)
2929 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
2934 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2935 instance INSTANCE at time CLOCK if the previous actual hazard cost
2938 HAIFA_INLINE static int
2939 actual_hazard_this_instance (unit, instance, insn, clock, cost)
2940 int unit, instance, clock, cost;
2943 int tick = unit_tick[instance]; /* issue time of the last issued insn */
2945 if (tick - clock > cost)
2947 /* The scheduler is operating forward, so unit's last insn is the
2948 executing insn and INSN is the candidate insn. We want a
2949 more exact measure of the blockage if we execute INSN at CLOCK
2950 given when we committed the execution of the unit's last insn.
2952 The blockage value is given by either the unit's max blockage
2953 constant, blockage range function, or blockage function. Use
2954 the most exact form for the given unit. */
2956 if (function_units[unit].blockage_range_function)
2958 if (function_units[unit].blockage_function)
2959 tick += (function_units[unit].blockage_function
2960 (unit_last_insn[instance], insn)
2961 - function_units[unit].max_blockage);
2963 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
2964 - function_units[unit].max_blockage);
2966 if (tick - clock > cost)
2967 cost = tick - clock;
2972 /* Record INSN as having begun execution on the units encoded by UNIT at
2975 HAIFA_INLINE static void
2976 schedule_unit (unit, insn, clock)
2984 int instance = unit;
2985 #if MAX_MULTIPLICITY > 1
2986 /* Find the first free instance of the function unit and use that
2987 one. We assume that one is free. */
2988 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2990 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
2992 instance += FUNCTION_UNITS_SIZE;
2995 unit_last_insn[instance] = insn;
2996 unit_tick[instance] = (clock + function_units[unit].max_blockage);
2999 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3000 if ((unit & 1) != 0)
3001 schedule_unit (i, insn, clock);
3004 /* Return the actual hazard cost of executing INSN on the units encoded by
3005 UNIT at time CLOCK if the previous actual hazard cost was COST. */
3007 HAIFA_INLINE static int
3008 actual_hazard (unit, insn, clock, cost)
3009 int unit, clock, cost;
3016 /* Find the instance of the function unit with the minimum hazard. */
3017 int instance = unit;
3018 int best_cost = actual_hazard_this_instance (unit, instance, insn,
3022 #if MAX_MULTIPLICITY > 1
3023 if (best_cost > cost)
3025 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
3027 instance += FUNCTION_UNITS_SIZE;
3028 this_cost = actual_hazard_this_instance (unit, instance, insn,
3030 if (this_cost < best_cost)
3032 best_cost = this_cost;
3033 if (this_cost <= cost)
3039 cost = MAX (cost, best_cost);
3042 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3043 if ((unit & 1) != 0)
3044 cost = actual_hazard (i, insn, clock, cost);
3049 /* Return the potential hazard cost of executing an instruction on the
3050 units encoded by UNIT if the previous potential hazard cost was COST.
3051 An insn with a large blockage time is chosen in preference to one
3052 with a smaller time; an insn that uses a unit that is more likely
3053 to be used is chosen in preference to one with a unit that is less
3054 used. We are trying to minimize a subsequent actual hazard. */
3056 HAIFA_INLINE static int
3057 potential_hazard (unit, insn, cost)
3062 unsigned int minb, maxb;
3066 minb = maxb = function_units[unit].max_blockage;
3069 if (function_units[unit].blockage_range_function)
3071 maxb = minb = blockage_range (unit, insn);
3072 maxb = MAX_BLOCKAGE_COST (maxb);
3073 minb = MIN_BLOCKAGE_COST (minb);
3078 /* Make the number of instructions left dominate. Make the
3079 minimum delay dominate the maximum delay. If all these
3080 are the same, use the unit number to add an arbitrary
3081 ordering. Other terms can be added. */
3082 ncost = minb * 0x40 + maxb;
3083 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
3090 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3091 if ((unit & 1) != 0)
3092 cost = potential_hazard (i, insn, cost);
3097 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3098 This is the number of cycles between instruction issue and
3099 instruction results. */
3101 HAIFA_INLINE static int
3102 insn_cost (insn, link, used)
3103 rtx insn, link, used;
3105 register int cost = INSN_COST (insn);
3109 recog_memoized (insn);
3111 /* A USE insn, or something else we don't need to understand.
3112 We can't pass these directly to result_ready_cost because it will
3113 trigger a fatal error for unrecognizable insns. */
3114 if (INSN_CODE (insn) < 0)
3116 INSN_COST (insn) = 1;
3121 cost = result_ready_cost (insn);
3126 INSN_COST (insn) = cost;
3130 /* in this case estimate cost without caring how insn is used. */
3131 if (link == 0 && used == 0)
3134 /* A USE insn should never require the value used to be computed. This
3135 allows the computation of a function's result and parameter values to
3136 overlap the return and call. */
3137 recog_memoized (used);
3138 if (INSN_CODE (used) < 0)
3139 LINK_COST_FREE (link) = 1;
3141 /* If some dependencies vary the cost, compute the adjustment. Most
3142 commonly, the adjustment is complete: either the cost is ignored
3143 (in the case of an output- or anti-dependence), or the cost is
3144 unchanged. These values are cached in the link as LINK_COST_FREE
3145 and LINK_COST_ZERO. */
3147 if (LINK_COST_FREE (link))
3150 else if (!LINK_COST_ZERO (link))
3154 ADJUST_COST (used, link, insn, ncost);
3157 LINK_COST_FREE (link) = 1;
3161 LINK_COST_ZERO (link) = 1;
3168 /* Compute the priority number for INSN. */
3177 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
3180 if ((this_priority = INSN_PRIORITY (insn)) == 0)
3182 if (INSN_DEPEND (insn) == 0)
3183 this_priority = insn_cost (insn, 0, 0);
3185 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
3190 if (RTX_INTEGRATED_P (link))
3193 next = XEXP (link, 0);
3195 /* critical path is meaningful in block boundaries only */
3196 if (INSN_BLOCK (next) != INSN_BLOCK (insn))
3199 next_priority = insn_cost (insn, link, next) + priority (next);
3200 if (next_priority > this_priority)
3201 this_priority = next_priority;
3203 INSN_PRIORITY (insn) = this_priority;
3205 return this_priority;
3209 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3210 them to the unused_*_list variables, so that they can be reused. */
3213 free_pending_lists ()
3215 if (current_nr_blocks <= 1)
3217 free_list (&pending_read_insns, &unused_insn_list);
3218 free_list (&pending_write_insns, &unused_insn_list);
3219 free_list (&pending_read_mems, &unused_expr_list);
3220 free_list (&pending_write_mems, &unused_expr_list);
3224 /* interblock scheduling */
3227 for (bb = 0; bb < current_nr_blocks; bb++)
3229 free_list (&bb_pending_read_insns[bb], &unused_insn_list);
3230 free_list (&bb_pending_write_insns[bb], &unused_insn_list);
3231 free_list (&bb_pending_read_mems[bb], &unused_expr_list);
3232 free_list (&bb_pending_write_mems[bb], &unused_expr_list);
3237 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3238 The MEM is a memory reference contained within INSN, which we are saving
3239 so that we can do memory aliasing on it. */
3242 add_insn_mem_dependence (insn_list, mem_list, insn, mem)
3243 rtx *insn_list, *mem_list, insn, mem;
3247 link = alloc_INSN_LIST (insn, *insn_list);
3250 link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
3253 pending_lists_length++;
3257 /* Make a dependency between every memory reference on the pending lists
3258 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3262 flush_pending_lists (insn, only_write)
3269 while (pending_read_insns && ! only_write)
3271 add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
3273 link = pending_read_insns;
3274 pending_read_insns = XEXP (pending_read_insns, 1);
3275 XEXP (link, 1) = unused_insn_list;
3276 unused_insn_list = link;
3278 link = pending_read_mems;
3279 pending_read_mems = XEXP (pending_read_mems, 1);
3280 XEXP (link, 1) = unused_expr_list;
3281 unused_expr_list = link;
3283 while (pending_write_insns)
3285 add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
3287 link = pending_write_insns;
3288 pending_write_insns = XEXP (pending_write_insns, 1);
3289 XEXP (link, 1) = unused_insn_list;
3290 unused_insn_list = link;
3292 link = pending_write_mems;
3293 pending_write_mems = XEXP (pending_write_mems, 1);
3294 XEXP (link, 1) = unused_expr_list;
3295 unused_expr_list = link;
3297 pending_lists_length = 0;
3299 /* last_pending_memory_flush is now a list of insns */
3300 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3301 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3303 free_list (&last_pending_memory_flush, &unused_insn_list);
3304 last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
3307 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
3308 by the write to the destination of X, and reads of everything mentioned. */
3311 sched_analyze_1 (x, insn)
3316 register rtx dest = SET_DEST (x);
3317 enum rtx_code code = GET_CODE (x);
3322 if (GET_CODE (dest) == PARALLEL
3323 && GET_MODE (dest) == BLKmode)
3326 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
3327 sched_analyze_1 (XVECEXP (dest, 0, i), insn);
3328 if (GET_CODE (x) == SET)
3329 sched_analyze_2 (SET_SRC (x), insn);
3333 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3334 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3336 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3338 /* The second and third arguments are values read by this insn. */
3339 sched_analyze_2 (XEXP (dest, 1), insn);
3340 sched_analyze_2 (XEXP (dest, 2), insn);
3342 dest = SUBREG_REG (dest);
3345 if (GET_CODE (dest) == REG)
3349 regno = REGNO (dest);
3351 /* A hard reg in a wide mode may really be multiple registers.
3352 If so, mark all of them just like the first. */
3353 if (regno < FIRST_PSEUDO_REGISTER)
3355 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
3360 for (u = reg_last_uses[regno + i]; u; u = XEXP (u, 1))
3361 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3363 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3364 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3366 /* Clobbers need not be ordered with respect to one another,
3367 but sets must be ordered with respect to a pending clobber. */
3370 free_list (®_last_uses[regno + i], &unused_insn_list);
3371 for (u = reg_last_clobbers[regno + i]; u; u = XEXP (u, 1))
3372 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3373 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
3376 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
3378 /* Function calls clobber all call_used regs. */
3379 if (global_regs[regno + i]
3380 || (code == SET && call_used_regs[regno + i]))
3381 for (u = last_function_call; u; u = XEXP (u, 1))
3382 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3389 for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
3390 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3392 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3393 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3397 free_list (®_last_uses[regno], &unused_insn_list);
3398 for (u = reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3399 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3400 SET_REGNO_REG_SET (reg_pending_sets, regno);
3403 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
3405 /* Pseudos that are REG_EQUIV to something may be replaced
3406 by that during reloading. We need only add dependencies for
3407 the address in the REG_EQUIV note. */
3408 if (!reload_completed
3409 && reg_known_equiv_p[regno]
3410 && GET_CODE (reg_known_value[regno]) == MEM)
3411 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3413 /* Don't let it cross a call after scheduling if it doesn't
3414 already cross one. */
3416 if (REG_N_CALLS_CROSSED (regno) == 0)
3417 for (u = last_function_call; u; u = XEXP (u, 1))
3418 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3421 else if (GET_CODE (dest) == MEM)
3423 /* Writing memory. */
3425 if (pending_lists_length > 32)
3427 /* Flush all pending reads and writes to prevent the pending lists
3428 from getting any larger. Insn scheduling runs too slowly when
3429 these lists get long. The number 32 was chosen because it
3430 seems like a reasonable number. When compiling GCC with itself,
3431 this flush occurs 8 times for sparc, and 10 times for m88k using
3433 flush_pending_lists (insn, 0);
3438 rtx pending, pending_mem;
3440 pending = pending_read_insns;
3441 pending_mem = pending_read_mems;
3444 /* If a dependency already exists, don't create a new one. */
3445 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3446 if (anti_dependence (XEXP (pending_mem, 0), dest))
3447 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3449 pending = XEXP (pending, 1);
3450 pending_mem = XEXP (pending_mem, 1);
3453 pending = pending_write_insns;
3454 pending_mem = pending_write_mems;
3457 /* If a dependency already exists, don't create a new one. */
3458 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3459 if (output_dependence (XEXP (pending_mem, 0), dest))
3460 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
3462 pending = XEXP (pending, 1);
3463 pending_mem = XEXP (pending_mem, 1);
3466 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3467 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3469 add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
3472 sched_analyze_2 (XEXP (dest, 0), insn);
3475 /* Analyze reads. */
3476 if (GET_CODE (x) == SET)
3477 sched_analyze_2 (SET_SRC (x), insn);
3480 /* Analyze the uses of memory and registers in rtx X in INSN. */
3483 sched_analyze_2 (x, insn)
3489 register enum rtx_code code;
3490 register const char *fmt;
3495 code = GET_CODE (x);
3504 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3505 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3506 this does not mean that this insn is using cc0. */
3514 /* User of CC0 depends on immediately preceding insn. */
3515 SCHED_GROUP_P (insn) = 1;
3517 /* There may be a note before this insn now, but all notes will
3518 be removed before we actually try to schedule the insns, so
3519 it won't cause a problem later. We must avoid it here though. */
3520 prev = prev_nonnote_insn (insn);
3522 /* Make a copy of all dependencies on the immediately previous insn,
3523 and add to this insn. This is so that all the dependencies will
3524 apply to the group. Remove an explicit dependence on this insn
3525 as SCHED_GROUP_P now represents it. */
3527 if (find_insn_list (prev, LOG_LINKS (insn)))
3528 remove_dependence (insn, prev);
3530 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
3531 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3540 int regno = REGNO (x);
3541 if (regno < FIRST_PSEUDO_REGISTER)
3545 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
3548 reg_last_uses[regno + i]
3549 = alloc_INSN_LIST (insn, reg_last_uses[regno + i]);
3551 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3552 add_dependence (insn, XEXP (u, 0), 0);
3554 /* ??? This should never happen. */
3555 for (u = reg_last_clobbers[regno + i]; u; u = XEXP (u, 1))
3556 add_dependence (insn, XEXP (u, 0), 0);
3558 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3559 /* Function calls clobber all call_used regs. */
3560 for (u = last_function_call; u; u = XEXP (u, 1))
3561 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3566 reg_last_uses[regno] = alloc_INSN_LIST (insn, reg_last_uses[regno]);
3568 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3569 add_dependence (insn, XEXP (u, 0), 0);
3571 /* ??? This should never happen. */
3572 for (u = reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3573 add_dependence (insn, XEXP (u, 0), 0);
3575 /* Pseudos that are REG_EQUIV to something may be replaced
3576 by that during reloading. We need only add dependencies for
3577 the address in the REG_EQUIV note. */
3578 if (!reload_completed
3579 && reg_known_equiv_p[regno]
3580 && GET_CODE (reg_known_value[regno]) == MEM)
3581 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3583 /* If the register does not already cross any calls, then add this
3584 insn to the sched_before_next_call list so that it will still
3585 not cross calls after scheduling. */
3586 if (REG_N_CALLS_CROSSED (regno) == 0)
3587 add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
3594 /* Reading memory. */
3596 rtx pending, pending_mem;
3598 pending = pending_read_insns;
3599 pending_mem = pending_read_mems;
3602 /* If a dependency already exists, don't create a new one. */
3603 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3604 if (read_dependence (XEXP (pending_mem, 0), x))
3605 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3607 pending = XEXP (pending, 1);
3608 pending_mem = XEXP (pending_mem, 1);
3611 pending = pending_write_insns;
3612 pending_mem = pending_write_mems;
3615 /* If a dependency already exists, don't create a new one. */
3616 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3617 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
3619 add_dependence (insn, XEXP (pending, 0), 0);
3621 pending = XEXP (pending, 1);
3622 pending_mem = XEXP (pending_mem, 1);
3625 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3626 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3628 /* Always add these dependencies to pending_reads, since
3629 this insn may be followed by a write. */
3630 add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
3633 /* Take advantage of tail recursion here. */
3634 sched_analyze_2 (XEXP (x, 0), insn);
3638 /* Force pending stores to memory in case a trap handler needs them. */
3640 flush_pending_lists (insn, 1);
3645 case UNSPEC_VOLATILE:
3649 /* Traditional and volatile asm instructions must be considered to use
3650 and clobber all hard registers, all pseudo-registers and all of
3651 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3653 Consider for instance a volatile asm that changes the fpu rounding
3654 mode. An insn should not be moved across this even if it only uses
3655 pseudo-regs because it might give an incorrectly rounded result. */
3656 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
3658 int max_reg = max_reg_num ();
3659 for (i = 0; i < max_reg; i++)
3661 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3662 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3663 free_list (®_last_uses[i], &unused_insn_list);
3665 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3666 add_dependence (insn, XEXP (u, 0), 0);
3668 for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
3669 add_dependence (insn, XEXP (u, 0), 0);
3671 reg_pending_sets_all = 1;
3673 flush_pending_lists (insn, 0);
3676 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3677 We can not just fall through here since then we would be confused
3678 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3679 traditional asms unlike their normal usage. */
3681 if (code == ASM_OPERANDS)
3683 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3684 sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
3694 /* These both read and modify the result. We must handle them as writes
3695 to get proper dependencies for following instructions. We must handle
3696 them as reads to get proper dependencies from this to previous
3697 instructions. Thus we need to pass them to both sched_analyze_1
3698 and sched_analyze_2. We must call sched_analyze_2 first in order
3699 to get the proper antecedent for the read. */
3700 sched_analyze_2 (XEXP (x, 0), insn);
3701 sched_analyze_1 (x, insn);
3708 /* Other cases: walk the insn. */
3709 fmt = GET_RTX_FORMAT (code);
3710 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3713 sched_analyze_2 (XEXP (x, i), insn);
3714 else if (fmt[i] == 'E')
3715 for (j = 0; j < XVECLEN (x, i); j++)
3716 sched_analyze_2 (XVECEXP (x, i, j), insn);
3720 /* Analyze an INSN with pattern X to find all dependencies. */
3723 sched_analyze_insn (x, insn, loop_notes)
3727 register RTX_CODE code = GET_CODE (x);
3729 int maxreg = max_reg_num ();
3732 if (code == SET || code == CLOBBER)
3733 sched_analyze_1 (x, insn);
3734 else if (code == PARALLEL)
3737 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3739 code = GET_CODE (XVECEXP (x, 0, i));
3740 if (code == SET || code == CLOBBER)
3741 sched_analyze_1 (XVECEXP (x, 0, i), insn);
3743 sched_analyze_2 (XVECEXP (x, 0, i), insn);
3747 sched_analyze_2 (x, insn);
3749 /* Mark registers CLOBBERED or used by called function. */
3750 if (GET_CODE (insn) == CALL_INSN)
3751 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3753 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3754 sched_analyze_1 (XEXP (link, 0), insn);
3756 sched_analyze_2 (XEXP (link, 0), insn);
3759 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3760 block, then we must be sure that no instructions are scheduled across it.
3761 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3762 become incorrect. */
3766 int max_reg = max_reg_num ();
3767 int schedule_barrier_found = 0;
3770 /* Update loop_notes with any notes from this insn. Also determine
3771 if any of the notes on the list correspond to instruction scheduling
3772 barriers (loop, eh & setjmp notes, but not range notes. */
3774 while (XEXP (link, 1))
3776 if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
3777 || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
3778 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
3779 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END
3780 || INTVAL (XEXP (link, 0)) == NOTE_INSN_SETJMP)
3781 schedule_barrier_found = 1;
3783 link = XEXP (link, 1);
3785 XEXP (link, 1) = REG_NOTES (insn);
3786 REG_NOTES (insn) = loop_notes;
3788 /* Add dependencies if a scheduling barrier was found. */
3789 if (schedule_barrier_found)
3791 for (i = 0; i < max_reg; i++)
3794 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3795 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3796 free_list (®_last_uses[i], &unused_insn_list);
3798 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3799 add_dependence (insn, XEXP (u, 0), 0);
3801 for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
3802 add_dependence (insn, XEXP (u, 0), 0);
3804 reg_pending_sets_all = 1;
3806 flush_pending_lists (insn, 0);
3811 /* Accumulate clobbers until the next set so that it will be output dependant
3812 on all of them. At the next set we can clear the clobber list, since
3813 subsequent sets will be output dependant on it. */
3814 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
3816 free_list (®_last_sets[i], &unused_insn_list);
3817 free_list (®_last_clobbers[i],
3820 = alloc_INSN_LIST (insn, NULL_RTX);
3822 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
3824 reg_last_clobbers[i]
3825 = alloc_INSN_LIST (insn, reg_last_clobbers[i]);
3827 CLEAR_REG_SET (reg_pending_sets);
3828 CLEAR_REG_SET (reg_pending_clobbers);
3830 if (reg_pending_sets_all)
3832 for (i = 0; i < maxreg; i++)
3834 free_list (®_last_sets[i], &unused_insn_list);
3835 reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3838 reg_pending_sets_all = 0;
3841 /* Handle function calls and function returns created by the epilogue
3843 if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
3848 /* When scheduling instructions, we make sure calls don't lose their
3849 accompanying USE insns by depending them one on another in order.
3851 Also, we must do the same thing for returns created by the epilogue
3852 threading code. Note this code works only in this special case,
3853 because other passes make no guarantee that they will never emit
3854 an instruction between a USE and a RETURN. There is such a guarantee
3855 for USE instructions immediately before a call. */
3857 prev_dep_insn = insn;
3858 dep_insn = PREV_INSN (insn);
3859 while (GET_CODE (dep_insn) == INSN
3860 && GET_CODE (PATTERN (dep_insn)) == USE
3861 && GET_CODE (XEXP (PATTERN (dep_insn), 0)) == REG)
3863 SCHED_GROUP_P (prev_dep_insn) = 1;
3865 /* Make a copy of all dependencies on dep_insn, and add to insn.
3866 This is so that all of the dependencies will apply to the
3869 for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
3870 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3872 prev_dep_insn = dep_insn;
3873 dep_insn = PREV_INSN (dep_insn);
3878 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3879 for every dependency. */
3882 sched_analyze (head, tail)
3889 for (insn = head;; insn = NEXT_INSN (insn))
3891 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
3893 /* Make each JUMP_INSN a scheduling barrier for memory references. */
3894 if (GET_CODE (insn) == JUMP_INSN)
3895 last_pending_memory_flush
3896 = alloc_INSN_LIST (insn, last_pending_memory_flush);
3897 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3900 else if (GET_CODE (insn) == CALL_INSN)
3905 CANT_MOVE (insn) = 1;
3907 /* Any instruction using a hard register which may get clobbered
3908 by a call needs to be marked as dependent on this call.
3909 This prevents a use of a hard return reg from being moved
3910 past a void call (i.e. it does not explicitly set the hard
3913 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3914 all registers, not just hard registers, may be clobbered by this
3917 /* Insn, being a CALL_INSN, magically depends on
3918 `last_function_call' already. */
3920 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
3921 && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
3923 int max_reg = max_reg_num ();
3924 for (i = 0; i < max_reg; i++)
3926 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3927 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3928 free_list (®_last_uses[i], &unused_insn_list);
3930 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3931 add_dependence (insn, XEXP (u, 0), 0);
3933 for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
3934 add_dependence (insn, XEXP (u, 0), 0);
3936 reg_pending_sets_all = 1;
3938 /* Add a pair of fake REG_NOTE which we will later
3939 convert back into a NOTE_INSN_SETJMP note. See
3940 reemit_notes for why we use a pair of NOTEs. */
3941 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3944 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3945 GEN_INT (NOTE_INSN_SETJMP),
3950 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3951 if (call_used_regs[i] || global_regs[i])
3953 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3954 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3956 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3957 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3959 SET_REGNO_REG_SET (reg_pending_clobbers, i);
3963 /* For each insn which shouldn't cross a call, add a dependence
3964 between that insn and this call insn. */
3965 x = LOG_LINKS (sched_before_next_call);
3968 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
3971 LOG_LINKS (sched_before_next_call) = 0;
3973 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3976 /* In the absence of interprocedural alias analysis, we must flush
3977 all pending reads and writes, and start new dependencies starting
3978 from here. But only flush writes for constant calls (which may
3979 be passed a pointer to something we haven't written yet). */
3980 flush_pending_lists (insn, CONST_CALL_P (insn));
3982 /* Depend this function call (actually, the user of this
3983 function call) on all hard register clobberage. */
3985 /* last_function_call is now a list of insns */
3986 free_list(&last_function_call, &unused_insn_list);
3987 last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3990 /* See comments on reemit_notes as to why we do this. */
3991 /* ??? Actually, the reemit_notes just say what is done, not why. */
3993 else if (GET_CODE (insn) == NOTE
3994 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_START
3995 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END))
3997 loop_notes = alloc_EXPR_LIST (REG_DEAD, NOTE_RANGE_INFO (insn),
3999 loop_notes = alloc_EXPR_LIST (REG_DEAD,
4000 GEN_INT (NOTE_LINE_NUMBER (insn)),
4003 else if (GET_CODE (insn) == NOTE
4004 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
4005 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
4006 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
4007 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
4008 || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
4009 && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
4011 loop_notes = alloc_EXPR_LIST (REG_DEAD,
4012 GEN_INT (NOTE_BLOCK_NUMBER (insn)),
4014 loop_notes = alloc_EXPR_LIST (REG_DEAD,
4015 GEN_INT (NOTE_LINE_NUMBER (insn)),
4017 CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
4026 /* Called when we see a set of a register. If death is true, then we are
4027 scanning backwards. Mark that register as unborn. If nobody says
4028 otherwise, that is how things will remain. If death is false, then we
4029 are scanning forwards. Mark that register as being born. */
4032 sched_note_set (x, death)
4037 register rtx reg = SET_DEST (x);
4043 if (GET_CODE (reg) == PARALLEL
4044 && GET_MODE (reg) == BLKmode)
4047 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
4048 sched_note_set (XVECEXP (reg, 0, i), death);
4052 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
4053 || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
4055 /* Must treat modification of just one hardware register of a multi-reg
4056 value or just a byte field of a register exactly the same way that
4057 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
4058 does not kill the entire register. */
4059 if (GET_CODE (reg) != SUBREG
4060 || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
4063 reg = SUBREG_REG (reg);
4066 if (GET_CODE (reg) != REG)
4069 /* Global registers are always live, so the code below does not apply
4072 regno = REGNO (reg);
4073 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
4077 /* If we only set part of the register, then this set does not
4082 /* Try killing this register. */
4083 if (regno < FIRST_PSEUDO_REGISTER)
4085 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
4088 CLEAR_REGNO_REG_SET (bb_live_regs, regno + j);
4093 /* Recompute REG_BASIC_BLOCK as we update all the other
4094 dataflow information. */
4095 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
4096 sched_reg_basic_block[regno] = current_block_num;
4097 else if (sched_reg_basic_block[regno] != current_block_num)
4098 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
4100 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
4105 /* Make the register live again. */
4106 if (regno < FIRST_PSEUDO_REGISTER)
4108 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
4111 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4116 SET_REGNO_REG_SET (bb_live_regs, regno);
4122 /* Macros and functions for keeping the priority queue sorted, and
4123 dealing with queueing and dequeueing of instructions. */
4125 #define SCHED_SORT(READY, N_READY) \
4126 do { if ((N_READY) == 2) \
4127 swap_sort (READY, N_READY); \
4128 else if ((N_READY) > 2) \
4129 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4132 /* Returns a positive value if x is preferred; returns a negative value if
4133 y is preferred. Should never return 0, since that will make the sort
4137 rank_for_schedule (x, y)
4138 const GENERIC_PTR x;
4139 const GENERIC_PTR y;
4141 rtx tmp = *(rtx *)y;
4142 rtx tmp2 = *(rtx *)x;
4144 int tmp_class, tmp2_class, depend_count1, depend_count2;
4145 int val, priority_val, spec_val, prob_val, weight_val;
4148 /* prefer insn with higher priority */
4149 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
4151 return priority_val;
4153 /* prefer an insn with smaller contribution to registers-pressure */
4154 if (!reload_completed &&
4155 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
4156 return (weight_val);
4158 /* some comparison make sense in interblock scheduling only */
4159 if (INSN_BB (tmp) != INSN_BB (tmp2))
4161 /* prefer an inblock motion on an interblock motion */
4162 if ((INSN_BB (tmp2) == target_bb) && (INSN_BB (tmp) != target_bb))
4164 if ((INSN_BB (tmp) == target_bb) && (INSN_BB (tmp2) != target_bb))
4167 /* prefer a useful motion on a speculative one */
4168 if ((spec_val = IS_SPECULATIVE_INSN (tmp) - IS_SPECULATIVE_INSN (tmp2)))
4171 /* prefer a more probable (speculative) insn */
4172 prob_val = INSN_PROBABILITY (tmp2) - INSN_PROBABILITY (tmp);
4177 /* compare insns based on their relation to the last-scheduled-insn */
4178 if (last_scheduled_insn)
4180 /* Classify the instructions into three classes:
4181 1) Data dependent on last schedule insn.
4182 2) Anti/Output dependent on last scheduled insn.
4183 3) Independent of last scheduled insn, or has latency of one.
4184 Choose the insn from the highest numbered class if different. */
4185 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
4186 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
4188 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4193 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
4194 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
4196 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4201 if ((val = tmp2_class - tmp_class))
4205 /* Prefer the insn which has more later insns that depend on it.
4206 This gives the scheduler more freedom when scheduling later
4207 instructions at the expense of added register pressure. */
4209 for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
4213 for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
4216 val = depend_count2 - depend_count1;
4220 /* If insns are equally good, sort by INSN_LUID (original insn order),
4221 so that we make the sort stable. This minimizes instruction movement,
4222 thus minimizing sched's effect on debugging and cross-jumping. */
4223 return INSN_LUID (tmp) - INSN_LUID (tmp2);
4226 /* Resort the array A in which only element at index N may be out of order. */
4228 HAIFA_INLINE static void
4233 rtx insn = a[n - 1];
4236 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
4244 static int max_priority;
4246 /* Add INSN to the insn queue so that it can be executed at least
4247 N_CYCLES after the currently executing insn. Preserve insns
4248 chain for debugging purposes. */
4250 HAIFA_INLINE static void
4251 queue_insn (insn, n_cycles)
4255 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
4256 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
4257 insn_queue[next_q] = link;
4260 if (sched_verbose >= 2)
4262 fprintf (dump, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn));
4264 if (INSN_BB (insn) != target_bb)
4265 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
4267 fprintf (dump, "queued for %d cycles.\n", n_cycles);
4272 /* Return nonzero if PAT is the pattern of an insn which makes a
4275 HAIFA_INLINE static int
4276 birthing_insn_p (pat)
4281 if (reload_completed == 1)
4284 if (GET_CODE (pat) == SET
4285 && (GET_CODE (SET_DEST (pat)) == REG
4286 || (GET_CODE (SET_DEST (pat)) == PARALLEL
4287 && GET_MODE (SET_DEST (pat)) == BLKmode)))
4289 rtx dest = SET_DEST (pat);
4292 /* It would be more accurate to use refers_to_regno_p or
4293 reg_mentioned_p to determine when the dest is not live before this
4295 if (GET_CODE (dest) == REG)
4298 if (REGNO_REG_SET_P (bb_live_regs, i))
4299 return (REG_N_SETS (i) == 1);
4303 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
4305 int regno = REGNO (SET_DEST (XVECEXP (dest, 0, i)));
4306 if (REGNO_REG_SET_P (bb_live_regs, regno))
4307 return (REG_N_SETS (regno) == 1);
4312 if (GET_CODE (pat) == PARALLEL)
4314 for (j = 0; j < XVECLEN (pat, 0); j++)
4315 if (birthing_insn_p (XVECEXP (pat, 0, j)))
4321 /* PREV is an insn that is ready to execute. Adjust its priority if that
4322 will help shorten register lifetimes. */
4324 HAIFA_INLINE static void
4325 adjust_priority (prev)
4328 /* Trying to shorten register lives after reload has completed
4329 is useless and wrong. It gives inaccurate schedules. */
4330 if (reload_completed == 0)
4335 /* ??? This code has no effect, because REG_DEAD notes are removed
4336 before we ever get here. */
4337 for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
4338 if (REG_NOTE_KIND (note) == REG_DEAD)
4341 /* Defer scheduling insns which kill registers, since that
4342 shortens register lives. Prefer scheduling insns which
4343 make registers live for the same reason. */
4347 INSN_PRIORITY (prev) >>= 3;
4350 INSN_PRIORITY (prev) >>= 2;
4354 INSN_PRIORITY (prev) >>= 1;
4357 if (birthing_insn_p (PATTERN (prev)))
4359 int max = max_priority;
4361 if (max > INSN_PRIORITY (prev))
4362 INSN_PRIORITY (prev) = max;
4368 /* That said, a target might have it's own reasons for adjusting
4369 priority after reload. */
4370 #ifdef ADJUST_PRIORITY
4371 ADJUST_PRIORITY (prev);
4375 /* Clock at which the previous instruction was issued. */
4376 static int last_clock_var;
4378 /* INSN is the "currently executing insn". Launch each insn which was
4379 waiting on INSN. READY is a vector of insns which are ready to fire.
4380 N_READY is the number of elements in READY. CLOCK is the current
4384 schedule_insn (insn, ready, n_ready, clock)
4393 unit = insn_unit (insn);
4395 if (sched_verbose >= 2)
4397 fprintf (dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ", INSN_UID (insn));
4398 insn_print_units (insn);
4399 fprintf (dump, "\n");
4402 if (sched_verbose && unit == -1)
4403 visualize_no_unit (insn);
4405 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
4406 schedule_unit (unit, insn, clock);
4408 if (INSN_DEPEND (insn) == 0)
4411 /* This is used by the function adjust_priority above. */
4413 max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
4415 max_priority = INSN_PRIORITY (insn);
4417 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
4419 rtx next = XEXP (link, 0);
4420 int cost = insn_cost (insn, link, next);
4422 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
4424 if ((INSN_DEP_COUNT (next) -= 1) == 0)
4426 int effective_cost = INSN_TICK (next) - clock;
4428 /* For speculative insns, before inserting to ready/queue,
4429 check live, exception-free, and issue-delay */
4430 if (INSN_BB (next) != target_bb
4431 && (!IS_VALID (INSN_BB (next))
4433 || (IS_SPECULATIVE_INSN (next)
4434 && (insn_issue_delay (next) > 3
4435 || !check_live (next, INSN_BB (next))
4436 || !is_exception_free (next, INSN_BB (next), target_bb)))))
4439 if (sched_verbose >= 2)
4441 fprintf (dump, ";;\t\tdependences resolved: insn %d ", INSN_UID (next));
4443 if (current_nr_blocks > 1 && INSN_BB (next) != target_bb)
4444 fprintf (dump, "/b%d ", INSN_BLOCK (next));
4446 if (effective_cost < 1)
4447 fprintf (dump, "into ready\n");
4449 fprintf (dump, "into queue with cost=%d\n", effective_cost);
4452 /* Adjust the priority of NEXT and either put it on the ready
4453 list or queue it. */
4454 adjust_priority (next);
4455 if (effective_cost < 1)
4456 ready[n_ready++] = next;
4458 queue_insn (next, effective_cost);
4462 /* Annotate the instruction with issue information -- TImode
4463 indicates that the instruction is expected not to be able
4464 to issue on the same cycle as the previous insn. A machine
4465 may use this information to decide how the instruction should
4467 if (reload_completed && issue_rate > 1)
4469 PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
4470 last_clock_var = clock;
4477 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4481 create_reg_dead_note (reg, insn)
4486 /* The number of registers killed after scheduling must be the same as the
4487 number of registers killed before scheduling. The number of REG_DEAD
4488 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4489 might become one DImode hard register REG_DEAD note, but the number of
4490 registers killed will be conserved.
4492 We carefully remove REG_DEAD notes from the dead_notes list, so that
4493 there will be none left at the end. If we run out early, then there
4494 is a bug somewhere in flow, combine and/or sched. */
4496 if (dead_notes == 0)
4498 if (current_nr_blocks <= 1)
4501 link = alloc_EXPR_LIST (REG_DEAD, NULL_RTX, NULL_RTX);
4505 /* Number of regs killed by REG. */
4506 int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
4507 : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
4508 /* Number of regs killed by REG_DEAD notes taken off the list. */
4512 reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4513 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4514 GET_MODE (XEXP (link, 0))));
4515 while (reg_note_regs < regs_killed)
4517 link = XEXP (link, 1);
4519 /* LINK might be zero if we killed more registers after scheduling
4520 than before, and the last hard register we kill is actually
4523 This is normal for interblock scheduling, so deal with it in
4524 that case, else abort. */
4525 if (link == NULL_RTX && current_nr_blocks <= 1)
4527 else if (link == NULL_RTX)
4528 link = alloc_EXPR_LIST (REG_DEAD, gen_rtx_REG (word_mode, 0),
4531 reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4532 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4533 GET_MODE (XEXP (link, 0))));
4535 dead_notes = XEXP (link, 1);
4537 /* If we took too many regs kills off, put the extra ones back. */
4538 while (reg_note_regs > regs_killed)
4540 rtx temp_reg, temp_link;
4542 temp_reg = gen_rtx_REG (word_mode, 0);
4543 temp_link = alloc_EXPR_LIST (REG_DEAD, temp_reg, dead_notes);
4544 dead_notes = temp_link;
4549 XEXP (link, 0) = reg;
4550 XEXP (link, 1) = REG_NOTES (insn);
4551 REG_NOTES (insn) = link;
4554 /* Subroutine on attach_deaths_insn--handles the recursive search
4555 through INSN. If SET_P is true, then x is being modified by the insn. */
4558 attach_deaths (x, insn, set_p)
4565 register enum rtx_code code;
4566 register const char *fmt;
4571 code = GET_CODE (x);
4583 /* Get rid of the easy cases first. */
4588 /* If the register dies in this insn, queue that note, and mark
4589 this register as needing to die. */
4590 /* This code is very similar to mark_used_1 (if set_p is false)
4591 and mark_set_1 (if set_p is true) in flow.c. */
4601 all_needed = some_needed = REGNO_REG_SET_P (old_live_regs, regno);
4602 if (regno < FIRST_PSEUDO_REGISTER)
4606 n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4609 int needed = (REGNO_REG_SET_P (old_live_regs, regno + n));
4610 some_needed |= needed;
4611 all_needed &= needed;
4615 /* If it wasn't live before we started, then add a REG_DEAD note.
4616 We must check the previous lifetime info not the current info,
4617 because we may have to execute this code several times, e.g.
4618 once for a clobber (which doesn't add a note) and later
4619 for a use (which does add a note).
4621 Always make the register live. We must do this even if it was
4622 live before, because this may be an insn which sets and uses
4623 the same register, in which case the register has already been
4624 killed, so we must make it live again.
4626 Global registers are always live, and should never have a REG_DEAD
4627 note added for them, so none of the code below applies to them. */
4629 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
4631 /* Never add REG_DEAD notes for STACK_POINTER_REGNUM
4632 since it's always considered to be live. Similarly
4633 for FRAME_POINTER_REGNUM if a frame pointer is needed
4634 and for ARG_POINTER_REGNUM if it is fixed. */
4635 if (! (regno == FRAME_POINTER_REGNUM
4636 && (! reload_completed || frame_pointer_needed))
4637 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4638 && ! (regno == HARD_FRAME_POINTER_REGNUM
4639 && (! reload_completed || frame_pointer_needed))
4641 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4642 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
4644 && regno != STACK_POINTER_REGNUM)
4646 if (! all_needed && ! dead_or_set_p (insn, x))
4648 /* Check for the case where the register dying partially
4649 overlaps the register set by this insn. */
4650 if (regno < FIRST_PSEUDO_REGISTER
4651 && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
4653 int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4655 some_needed |= dead_or_set_regno_p (insn, regno + n);
4658 /* If none of the words in X is needed, make a REG_DEAD
4659 note. Otherwise, we must make partial REG_DEAD
4662 create_reg_dead_note (x, insn);
4667 /* Don't make a REG_DEAD note for a part of a
4668 register that is set in the insn. */
4669 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
4671 if (! REGNO_REG_SET_P (old_live_regs, regno+i)
4672 && ! dead_or_set_regno_p (insn, regno + i))
4673 create_reg_dead_note (gen_rtx_REG (reg_raw_mode[regno + i],
4680 if (regno < FIRST_PSEUDO_REGISTER)
4682 int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
4685 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4690 /* Recompute REG_BASIC_BLOCK as we update all the other
4691 dataflow information. */
4692 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
4693 sched_reg_basic_block[regno] = current_block_num;
4694 else if (sched_reg_basic_block[regno] != current_block_num)
4695 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
4697 SET_REGNO_REG_SET (bb_live_regs, regno);
4704 /* Handle tail-recursive case. */
4705 attach_deaths (XEXP (x, 0), insn, 0);
4709 attach_deaths (SUBREG_REG (x), insn,
4710 set_p && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4712 || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4713 == GET_MODE_SIZE (GET_MODE ((x))))));
4716 case STRICT_LOW_PART:
4717 attach_deaths (XEXP (x, 0), insn, 0);
4722 attach_deaths (XEXP (x, 0), insn, 0);
4723 attach_deaths (XEXP (x, 1), insn, 0);
4724 attach_deaths (XEXP (x, 2), insn, 0);
4729 && GET_MODE (x) == BLKmode)
4731 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4732 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
4738 /* Other cases: walk the insn. */
4739 fmt = GET_RTX_FORMAT (code);
4740 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4743 attach_deaths (XEXP (x, i), insn, 0);
4744 else if (fmt[i] == 'E')
4745 for (j = 0; j < XVECLEN (x, i); j++)
4746 attach_deaths (XVECEXP (x, i, j), insn, 0);
4751 /* After INSN has executed, add register death notes for each register
4752 that is dead after INSN. */
4755 attach_deaths_insn (insn)
4758 rtx x = PATTERN (insn);
4759 register RTX_CODE code = GET_CODE (x);
4764 attach_deaths (SET_SRC (x), insn, 0);
4766 /* A register might die here even if it is the destination, e.g.
4767 it is the target of a volatile read and is otherwise unused.
4768 Hence we must always call attach_deaths for the SET_DEST. */
4769 attach_deaths (SET_DEST (x), insn, 1);
4771 else if (code == PARALLEL)
4774 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4776 code = GET_CODE (XVECEXP (x, 0, i));
4779 attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
4781 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
4783 /* Flow does not add REG_DEAD notes to registers that die in
4784 clobbers, so we can't either. */
4785 else if (code != CLOBBER)
4786 attach_deaths (XVECEXP (x, 0, i), insn, 0);
4789 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4790 MEM being clobbered, just like flow. */
4791 else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == MEM)
4792 attach_deaths (XEXP (XEXP (x, 0), 0), insn, 0);
4793 /* Otherwise don't add a death note to things being clobbered. */
4794 else if (code != CLOBBER)
4795 attach_deaths (x, insn, 0);
4797 /* Make death notes for things used in the called function. */
4798 if (GET_CODE (insn) == CALL_INSN)
4799 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
4800 attach_deaths (XEXP (XEXP (link, 0), 0), insn,
4801 GET_CODE (XEXP (link, 0)) == CLOBBER);
4804 /* functions for handlnig of notes */
4806 /* Delete notes beginning with INSN and put them in the chain
4807 of notes ended by NOTE_LIST.
4808 Returns the insn following the notes. */
4811 unlink_other_notes (insn, tail)
4814 rtx prev = PREV_INSN (insn);
4816 while (insn != tail && GET_CODE (insn) == NOTE)
4818 rtx next = NEXT_INSN (insn);
4819 /* Delete the note from its current position. */
4821 NEXT_INSN (prev) = next;
4823 PREV_INSN (next) = prev;
4825 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4826 immediately after the call they follow. We use a fake
4827 (REG_DEAD (const_int -1)) note to remember them.
4828 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4829 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
4830 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
4831 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
4832 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_START
4833 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
4834 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
4835 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
4837 /* Insert the note at the end of the notes list. */
4838 PREV_INSN (insn) = note_list;
4840 NEXT_INSN (note_list) = insn;
4849 /* Delete line notes beginning with INSN. Record line-number notes so
4850 they can be reused. Returns the insn following the notes. */
4853 unlink_line_notes (insn, tail)
4856 rtx prev = PREV_INSN (insn);
4858 while (insn != tail && GET_CODE (insn) == NOTE)
4860 rtx next = NEXT_INSN (insn);
4862 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
4864 /* Delete the note from its current position. */
4866 NEXT_INSN (prev) = next;
4868 PREV_INSN (next) = prev;
4870 /* Record line-number notes so they can be reused. */
4871 LINE_NOTE (insn) = insn;
4881 /* Return the head and tail pointers of BB. */
4883 HAIFA_INLINE static void
4884 get_block_head_tail (bb, headp, tailp)
4894 b = BB_TO_BLOCK (bb);
4896 /* HEAD and TAIL delimit the basic block being scheduled. */
4897 head = BLOCK_HEAD (b);
4898 tail = BLOCK_END (b);
4900 /* Don't include any notes or labels at the beginning of the
4901 basic block, or notes at the ends of basic blocks. */
4902 while (head != tail)
4904 if (GET_CODE (head) == NOTE)
4905 head = NEXT_INSN (head);
4906 else if (GET_CODE (tail) == NOTE)
4907 tail = PREV_INSN (tail);
4908 else if (GET_CODE (head) == CODE_LABEL)
4909 head = NEXT_INSN (head);
4918 /* Delete line notes from bb. Save them so they can be later restored
4919 (in restore_line_notes ()). */
4930 get_block_head_tail (bb, &head, &tail);
4933 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4936 next_tail = NEXT_INSN (tail);
4937 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4941 /* Farm out notes, and maybe save them in NOTE_LIST.
4942 This is needed to keep the debugger from
4943 getting completely deranged. */
4944 if (GET_CODE (insn) == NOTE)
4947 insn = unlink_line_notes (insn, next_tail);
4953 if (insn == next_tail)
4959 /* Save line number notes for each insn in bb. */
4962 save_line_notes (bb)
4968 /* We must use the true line number for the first insn in the block
4969 that was computed and saved at the start of this pass. We can't
4970 use the current line number, because scheduling of the previous
4971 block may have changed the current line number. */
4973 rtx line = line_note_head[BB_TO_BLOCK (bb)];
4976 get_block_head_tail (bb, &head, &tail);
4977 next_tail = NEXT_INSN (tail);
4979 for (insn = BLOCK_HEAD (BB_TO_BLOCK (bb));
4981 insn = NEXT_INSN (insn))
4982 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4985 LINE_NOTE (insn) = line;
4989 /* After bb was scheduled, insert line notes into the insns list. */
4992 restore_line_notes (bb)
4995 rtx line, note, prev, new;
4996 int added_notes = 0;
4998 rtx head, next_tail, insn;
5000 b = BB_TO_BLOCK (bb);
5002 head = BLOCK_HEAD (b);
5003 next_tail = NEXT_INSN (BLOCK_END (b));
5005 /* Determine the current line-number. We want to know the current
5006 line number of the first insn of the block here, in case it is
5007 different from the true line number that was saved earlier. If
5008 different, then we need a line number note before the first insn
5009 of this block. If it happens to be the same, then we don't want to
5010 emit another line number note here. */
5011 for (line = head; line; line = PREV_INSN (line))
5012 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
5015 /* Walk the insns keeping track of the current line-number and inserting
5016 the line-number notes as needed. */
5017 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5018 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
5020 /* This used to emit line number notes before every non-deleted note.
5021 However, this confuses a debugger, because line notes not separated
5022 by real instructions all end up at the same address. I can find no
5023 use for line number notes before other notes, so none are emitted. */
5024 else if (GET_CODE (insn) != NOTE
5025 && (note = LINE_NOTE (insn)) != 0
5028 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
5029 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
5032 prev = PREV_INSN (insn);
5033 if (LINE_NOTE (note))
5035 /* Re-use the original line-number note. */
5036 LINE_NOTE (note) = 0;
5037 PREV_INSN (note) = prev;
5038 NEXT_INSN (prev) = note;
5039 PREV_INSN (insn) = note;
5040 NEXT_INSN (note) = insn;
5045 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
5046 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
5047 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
5050 if (sched_verbose && added_notes)
5051 fprintf (dump, ";; added %d line-number notes\n", added_notes);
5054 /* After scheduling the function, delete redundant line notes from the
5058 rm_redundant_line_notes ()
5061 rtx insn = get_insns ();
5062 int active_insn = 0;
5065 /* Walk the insns deleting redundant line-number notes. Many of these
5066 are already present. The remainder tend to occur at basic
5067 block boundaries. */
5068 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
5069 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
5071 /* If there are no active insns following, INSN is redundant. */
5072 if (active_insn == 0)
5075 NOTE_SOURCE_FILE (insn) = 0;
5076 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
5078 /* If the line number is unchanged, LINE is redundant. */
5080 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
5081 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
5084 NOTE_SOURCE_FILE (line) = 0;
5085 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
5092 else if (!((GET_CODE (insn) == NOTE
5093 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
5094 || (GET_CODE (insn) == INSN
5095 && (GET_CODE (PATTERN (insn)) == USE
5096 || GET_CODE (PATTERN (insn)) == CLOBBER))))
5099 if (sched_verbose && notes)
5100 fprintf (dump, ";; deleted %d line-number notes\n", notes);
5103 /* Delete notes between head and tail and put them in the chain
5104 of notes ended by NOTE_LIST. */
5107 rm_other_notes (head, tail)
5115 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
5118 next_tail = NEXT_INSN (tail);
5119 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5123 /* Farm out notes, and maybe save them in NOTE_LIST.
5124 This is needed to keep the debugger from
5125 getting completely deranged. */
5126 if (GET_CODE (insn) == NOTE)
5130 insn = unlink_other_notes (insn, next_tail);
5136 if (insn == next_tail)
5142 /* Constructor for `sometimes' data structure. */
5145 new_sometimes_live (regs_sometimes_live, regno, sometimes_max)
5146 struct sometimes *regs_sometimes_live;
5150 register struct sometimes *p;
5152 /* There should never be a register greater than max_regno here. If there
5153 is, it means that a define_split has created a new pseudo reg. This
5154 is not allowed, since there will not be flow info available for any
5155 new register, so catch the error here. */
5156 if (regno >= max_regno)
5159 p = ®s_sometimes_live[sometimes_max];
5162 p->calls_crossed = 0;
5164 return sometimes_max;
5167 /* Count lengths of all regs we are currently tracking,
5168 and find new registers no longer live. */
5171 finish_sometimes_live (regs_sometimes_live, sometimes_max)
5172 struct sometimes *regs_sometimes_live;
5177 for (i = 0; i < sometimes_max; i++)
5179 register struct sometimes *p = ®s_sometimes_live[i];
5180 int regno = p->regno;
5182 sched_reg_live_length[regno] += p->live_length;
5183 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5187 /* functions for computation of registers live/usage info */
5189 /* It is assumed that prior to scheduling BASIC_BLOCK (b)->global_live_at_start
5190 contains the registers that are alive at the entry to b.
5192 Two passes follow: The first pass is performed before the scheduling
5193 of a region. It scans each block of the region forward, computing
5194 the set of registers alive at the end of the basic block and
5195 discard REG_DEAD notes (done by find_pre_sched_live ()).
5197 The second path is invoked after scheduling all region blocks.
5198 It scans each block of the region backward, a block being traversed
5199 only after its succesors in the region. When the set of registers
5200 live at the end of a basic block may be changed by the scheduling
5201 (this may happen for multiple blocks region), it is computed as
5202 the union of the registers live at the start of its succesors.
5203 The last-use information is updated by inserting REG_DEAD notes.
5204 (done by find_post_sched_live ()) */
5206 /* Scan all the insns to be scheduled, removing register death notes.
5207 Register death notes end up in DEAD_NOTES.
5208 Recreate the register life information for the end of this basic
5212 find_pre_sched_live (bb)
5215 rtx insn, next_tail, head, tail;
5216 int b = BB_TO_BLOCK (bb);
5218 get_block_head_tail (bb, &head, &tail);
5219 COPY_REG_SET (bb_live_regs, BASIC_BLOCK (b)->global_live_at_start);
5220 next_tail = NEXT_INSN (tail);
5222 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5224 rtx prev, next, link;
5227 /* Handle register life information. */
5228 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
5230 /* See if the register gets born here. */
5231 /* We must check for registers being born before we check for
5232 registers dying. It is possible for a register to be born and
5233 die in the same insn, e.g. reading from a volatile memory
5234 location into an otherwise unused register. Such a register
5235 must be marked as dead after this insn. */
5236 if (GET_CODE (PATTERN (insn)) == SET
5237 || GET_CODE (PATTERN (insn)) == CLOBBER)
5239 sched_note_set (PATTERN (insn), 0);
5243 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5246 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5247 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5248 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5250 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5254 /* ??? This code is obsolete and should be deleted. It
5255 is harmless though, so we will leave it in for now. */
5256 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5257 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
5258 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5261 /* Each call cobbers (makes live) all call-clobbered regs
5262 that are not global or fixed. Note that the function-value
5263 reg is a call_clobbered reg. */
5264 if (GET_CODE (insn) == CALL_INSN)
5267 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
5268 if (call_used_regs[j] && !global_regs[j]
5271 SET_REGNO_REG_SET (bb_live_regs, j);
5275 /* Need to know what registers this insn kills. */
5276 for (prev = 0, link = REG_NOTES (insn); link; link = next)
5278 next = XEXP (link, 1);
5279 if ((REG_NOTE_KIND (link) == REG_DEAD
5280 || REG_NOTE_KIND (link) == REG_UNUSED)
5281 /* Verify that the REG_NOTE has a valid value. */
5282 && GET_CODE (XEXP (link, 0)) == REG)
5284 register int regno = REGNO (XEXP (link, 0));
5288 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5290 if (REG_NOTE_KIND (link) == REG_DEAD)
5293 XEXP (prev, 1) = next;
5295 REG_NOTES (insn) = next;
5296 XEXP (link, 1) = dead_notes;
5302 if (regno < FIRST_PSEUDO_REGISTER)
5304 int j = HARD_REGNO_NREGS (regno,
5305 GET_MODE (XEXP (link, 0)));
5308 CLEAR_REGNO_REG_SET (bb_live_regs, regno+j);
5313 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
5321 INSN_REG_WEIGHT (insn) = reg_weight;
5325 /* Update register life and usage information for block bb
5326 after scheduling. Put register dead notes back in the code. */
5329 find_post_sched_live (bb)
5336 rtx head, tail, prev_head, next_tail;
5338 register struct sometimes *regs_sometimes_live;
5340 b = BB_TO_BLOCK (bb);
5342 /* compute live regs at the end of bb as a function of its successors. */
5343 if (current_nr_blocks > 1)
5348 first_edge = e = OUT_EDGES (b);
5349 CLEAR_REG_SET (bb_live_regs);
5356 b_succ = TO_BLOCK (e);
5357 IOR_REG_SET (bb_live_regs,
5358 BASIC_BLOCK (b_succ)->global_live_at_start);
5361 while (e != first_edge);
5364 get_block_head_tail (bb, &head, &tail);
5365 next_tail = NEXT_INSN (tail);
5366 prev_head = PREV_INSN (head);
5368 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, i,
5370 sched_reg_basic_block[i] = REG_BLOCK_GLOBAL;
5373 /* if the block is empty, same regs are alive at its end and its start.
5374 since this is not guaranteed after interblock scheduling, make sure they
5375 are truly identical. */
5376 if (NEXT_INSN (prev_head) == tail
5377 && (GET_RTX_CLASS (GET_CODE (tail)) != 'i'))
5379 if (current_nr_blocks > 1)
5380 COPY_REG_SET (BASIC_BLOCK (b)->global_live_at_start, bb_live_regs);
5385 b = BB_TO_BLOCK (bb);
5386 current_block_num = b;
5388 /* Keep track of register lives. */
5389 old_live_regs = ALLOCA_REG_SET ();
5391 = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
5394 /* initiate "sometimes" data, starting with registers live at end */
5396 COPY_REG_SET (old_live_regs, bb_live_regs);
5397 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, 0, j,
5400 = new_sometimes_live (regs_sometimes_live,
5404 /* scan insns back, computing regs live info */
5405 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
5407 /* First we kill registers set by this insn, and then we
5408 make registers used by this insn live. This is the opposite
5409 order used above because we are traversing the instructions
5412 /* Strictly speaking, we should scan REG_UNUSED notes and make
5413 every register mentioned there live, however, we will just
5414 kill them again immediately below, so there doesn't seem to
5415 be any reason why we bother to do this. */
5417 /* See if this is the last notice we must take of a register. */
5418 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5421 if (GET_CODE (PATTERN (insn)) == SET
5422 || GET_CODE (PATTERN (insn)) == CLOBBER)
5423 sched_note_set (PATTERN (insn), 1);
5424 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5426 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5427 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5428 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5429 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 1);
5432 /* This code keeps life analysis information up to date. */
5433 if (GET_CODE (insn) == CALL_INSN)
5435 register struct sometimes *p;
5437 /* A call kills all call used registers that are not
5438 global or fixed, except for those mentioned in the call
5439 pattern which will be made live again later. */
5440 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5441 if (call_used_regs[i] && ! global_regs[i]
5444 CLEAR_REGNO_REG_SET (bb_live_regs, i);
5447 /* Regs live at the time of a call instruction must not
5448 go in a register clobbered by calls. Record this for
5449 all regs now live. Note that insns which are born or
5450 die in a call do not cross a call, so this must be done
5451 after the killings (above) and before the births
5453 p = regs_sometimes_live;
5454 for (i = 0; i < sometimes_max; i++, p++)
5455 if (REGNO_REG_SET_P (bb_live_regs, p->regno))
5456 p->calls_crossed += 1;
5459 /* Make every register used live, and add REG_DEAD notes for
5460 registers which were not live before we started. */
5461 attach_deaths_insn (insn);
5463 /* Find registers now made live by that instruction. */
5464 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs, old_live_regs, 0, j,
5467 = new_sometimes_live (regs_sometimes_live,
5470 IOR_REG_SET (old_live_regs, bb_live_regs);
5472 /* Count lengths of all regs we are worrying about now,
5473 and handle registers no longer live. */
5475 for (i = 0; i < sometimes_max; i++)
5477 register struct sometimes *p = ®s_sometimes_live[i];
5478 int regno = p->regno;
5480 p->live_length += 1;
5482 if (!REGNO_REG_SET_P (bb_live_regs, regno))
5484 /* This is the end of one of this register's lifetime
5485 segments. Save the lifetime info collected so far,
5486 and clear its bit in the old_live_regs entry. */
5487 sched_reg_live_length[regno] += p->live_length;
5488 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5489 CLEAR_REGNO_REG_SET (old_live_regs, p->regno);
5491 /* Delete the reg_sometimes_live entry for this reg by
5492 copying the last entry over top of it. */
5493 *p = regs_sometimes_live[--sometimes_max];
5494 /* ...and decrement i so that this newly copied entry
5495 will be processed. */
5501 finish_sometimes_live (regs_sometimes_live, sometimes_max);
5503 /* In interblock scheduling, global_live_at_start may have changed. */
5504 if (current_nr_blocks > 1)
5505 COPY_REG_SET (BASIC_BLOCK (b)->global_live_at_start, bb_live_regs);
5508 FREE_REG_SET (old_live_regs);
5509 } /* find_post_sched_live */
5511 /* After scheduling the subroutine, restore information about uses of
5519 if (n_basic_blocks > 0)
5520 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, regno,
5522 sched_reg_basic_block[regno]
5526 for (regno = 0; regno < max_regno; regno++)
5527 if (sched_reg_live_length[regno])
5531 if (REG_LIVE_LENGTH (regno) > sched_reg_live_length[regno])
5533 ";; register %d life shortened from %d to %d\n",
5534 regno, REG_LIVE_LENGTH (regno),
5535 sched_reg_live_length[regno]);
5536 /* Negative values are special; don't overwrite the current
5537 reg_live_length value if it is negative. */
5538 else if (REG_LIVE_LENGTH (regno) < sched_reg_live_length[regno]
5539 && REG_LIVE_LENGTH (regno) >= 0)
5541 ";; register %d life extended from %d to %d\n",
5542 regno, REG_LIVE_LENGTH (regno),
5543 sched_reg_live_length[regno]);
5545 if (!REG_N_CALLS_CROSSED (regno)
5546 && sched_reg_n_calls_crossed[regno])
5548 ";; register %d now crosses calls\n", regno);
5549 else if (REG_N_CALLS_CROSSED (regno)
5550 && !sched_reg_n_calls_crossed[regno]
5551 && REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5553 ";; register %d no longer crosses calls\n", regno);
5555 if (REG_BASIC_BLOCK (regno) != sched_reg_basic_block[regno]
5556 && sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5557 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5559 ";; register %d changed basic block from %d to %d\n",
5560 regno, REG_BASIC_BLOCK(regno),
5561 sched_reg_basic_block[regno]);
5564 /* Negative values are special; don't overwrite the current
5565 reg_live_length value if it is negative. */
5566 if (REG_LIVE_LENGTH (regno) >= 0)
5567 REG_LIVE_LENGTH (regno) = sched_reg_live_length[regno];
5569 if (sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5570 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5571 REG_BASIC_BLOCK(regno) = sched_reg_basic_block[regno];
5573 /* We can't change the value of reg_n_calls_crossed to zero for
5574 pseudos which are live in more than one block.
5576 This is because combine might have made an optimization which
5577 invalidated global_live_at_start and reg_n_calls_crossed,
5578 but it does not update them. If we update reg_n_calls_crossed
5579 here, the two variables are now inconsistent, and this might
5580 confuse the caller-save code into saving a register that doesn't
5581 need to be saved. This is only a problem when we zero calls
5582 crossed for a pseudo live in multiple basic blocks.
5584 Alternatively, we could try to correctly update basic block live
5585 at start here in sched, but that seems complicated.
5587 Note: it is possible that a global register became local, as result
5588 of interblock motion, but will remain marked as a global register. */
5589 if (sched_reg_n_calls_crossed[regno]
5590 || REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5591 REG_N_CALLS_CROSSED (regno) = sched_reg_n_calls_crossed[regno];
5596 /* Scheduling clock, modified in schedule_block() and queue_to_ready () */
5597 static int clock_var;
5599 /* Move insns that became ready to fire from queue to ready list. */
5602 queue_to_ready (ready, n_ready)
5609 q_ptr = NEXT_Q (q_ptr);
5611 /* Add all pending insns that can be scheduled without stalls to the
5613 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
5616 insn = XEXP (link, 0);
5619 if (sched_verbose >= 2)
5620 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5622 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5623 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5625 ready[n_ready++] = insn;
5626 if (sched_verbose >= 2)
5627 fprintf (dump, "moving to ready without stalls\n");
5629 insn_queue[q_ptr] = 0;
5631 /* If there are no ready insns, stall until one is ready and add all
5632 of the pending insns at that point to the ready list. */
5635 register int stalls;
5637 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
5639 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
5641 for (; link; link = XEXP (link, 1))
5643 insn = XEXP (link, 0);
5646 if (sched_verbose >= 2)
5647 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5649 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5650 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5652 ready[n_ready++] = insn;
5653 if (sched_verbose >= 2)
5654 fprintf (dump, "moving to ready with %d stalls\n", stalls);
5656 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
5663 if (sched_verbose && stalls)
5664 visualize_stall_cycles (BB_TO_BLOCK (target_bb), stalls);
5665 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
5666 clock_var += stalls;
5671 /* Print the ready list for debugging purposes. Callable from debugger. */
5674 debug_ready_list (ready, n_ready)
5680 for (i = 0; i < n_ready; i++)
5682 fprintf (dump, " %d", INSN_UID (ready[i]));
5683 if (current_nr_blocks > 1 && INSN_BB (ready[i]) != target_bb)
5684 fprintf (dump, "/b%d", INSN_BLOCK (ready[i]));
5686 fprintf (dump, "\n");
5689 /* Print names of units on which insn can/should execute, for debugging. */
5692 insn_print_units (insn)
5696 int unit = insn_unit (insn);
5699 fprintf (dump, "none");
5701 fprintf (dump, "%s", function_units[unit].name);
5704 fprintf (dump, "[");
5705 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
5708 fprintf (dump, "%s", function_units[i].name);
5710 fprintf (dump, " ");
5712 fprintf (dump, "]");
5716 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5717 of a basic block. If more lines are needed, table is splitted to two.
5718 n_visual_lines is the number of lines printed so far for a block.
5719 visual_tbl contains the block visualization info.
5720 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5721 #define MAX_VISUAL_LINES 100
5726 rtx vis_no_unit[10];
5728 /* Finds units that are in use in this fuction. Required only
5729 for visualization. */
5732 init_target_units ()
5737 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
5739 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5742 unit = insn_unit (insn);
5745 target_units |= ~unit;
5747 target_units |= (1 << unit);
5751 /* Return the length of the visualization table */
5754 get_visual_tbl_length ()
5760 /* compute length of one field in line */
5761 s = (char *) alloca (INSN_LEN + 5);
5762 sprintf (s, " %33s", "uname");
5765 /* compute length of one line */
5768 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5769 if (function_units[unit].bitmask & target_units)
5770 for (i = 0; i < function_units[unit].multiplicity; i++)
5773 n += strlen ("\n") + 2;
5775 /* compute length of visualization string */
5776 return (MAX_VISUAL_LINES * n);
5779 /* Init block visualization debugging info */
5782 init_block_visualization ()
5784 strcpy (visual_tbl, "");
5792 safe_concat (buf, cur, str)
5797 char *end = buf + BUF_LEN - 2; /* leave room for null */
5806 while (cur < end && (c = *str++) != '\0')
5813 /* This recognizes rtx, I classified as expressions. These are always */
5814 /* represent some action on values or results of other expression, */
5815 /* that may be stored in objects representing values. */
5818 print_exp (buf, x, verbose)
5826 const char *fun = (char *)0;
5831 for (i = 0; i < 4; i++)
5837 switch (GET_CODE (x))
5840 op[0] = XEXP (x, 0);
5841 if (GET_CODE (XEXP (x, 1)) == CONST_INT
5842 && INTVAL (XEXP (x, 1)) < 0)
5845 op[1] = GEN_INT (-INTVAL (XEXP (x, 1)));
5850 op[1] = XEXP (x, 1);
5854 op[0] = XEXP (x, 0);
5856 op[1] = XEXP (x, 1);
5860 op[0] = XEXP (x, 0);
5862 op[1] = XEXP (x, 1);
5866 op[0] = XEXP (x, 0);
5867 op[1] = XEXP (x, 1);
5871 op[0] = XEXP (x, 0);
5874 op[0] = XEXP (x, 0);
5876 op[1] = XEXP (x, 1);
5879 op[0] = XEXP (x, 0);
5881 op[1] = XEXP (x, 1);
5885 op[0] = XEXP (x, 0);
5886 op[1] = XEXP (x, 1);
5889 op[0] = XEXP (x, 0);
5891 op[1] = XEXP (x, 1);
5895 op[0] = XEXP (x, 0);
5896 op[1] = XEXP (x, 1);
5900 op[0] = XEXP (x, 0);
5901 op[1] = XEXP (x, 1);
5905 op[0] = XEXP (x, 0);
5906 op[1] = XEXP (x, 1);
5910 op[0] = XEXP (x, 0);
5911 op[1] = XEXP (x, 1);
5915 op[0] = XEXP (x, 0);
5916 op[1] = XEXP (x, 1);
5920 op[0] = XEXP (x, 0);
5923 op[0] = XEXP (x, 0);
5925 op[1] = XEXP (x, 1);
5928 op[0] = XEXP (x, 0);
5930 op[1] = XEXP (x, 1);
5933 op[0] = XEXP (x, 0);
5935 op[1] = XEXP (x, 1);
5938 op[0] = XEXP (x, 0);
5940 op[1] = XEXP (x, 1);
5943 op[0] = XEXP (x, 0);
5945 op[1] = XEXP (x, 1);
5948 op[0] = XEXP (x, 0);
5950 op[1] = XEXP (x, 1);
5953 op[0] = XEXP (x, 0);
5955 op[1] = XEXP (x, 1);
5958 op[0] = XEXP (x, 0);
5960 op[1] = XEXP (x, 1);
5964 op[0] = XEXP (x, 0);
5968 op[0] = XEXP (x, 0);
5972 op[0] = XEXP (x, 0);
5975 op[0] = XEXP (x, 0);
5977 op[1] = XEXP (x, 1);
5980 op[0] = XEXP (x, 0);
5982 op[1] = XEXP (x, 1);
5985 op[0] = XEXP (x, 0);
5987 op[1] = XEXP (x, 1);
5991 op[0] = XEXP (x, 0);
5992 op[1] = XEXP (x, 1);
5995 op[0] = XEXP (x, 0);
5997 op[1] = XEXP (x, 1);
6001 op[0] = XEXP (x, 0);
6002 op[1] = XEXP (x, 1);
6005 op[0] = XEXP (x, 0);
6007 op[1] = XEXP (x, 1);
6011 op[0] = XEXP (x, 0);
6012 op[1] = XEXP (x, 1);
6015 op[0] = XEXP (x, 0);
6017 op[1] = XEXP (x, 1);
6021 op[0] = XEXP (x, 0);
6022 op[1] = XEXP (x, 1);
6025 fun = (verbose) ? "sign_extract" : "sxt";
6026 op[0] = XEXP (x, 0);
6027 op[1] = XEXP (x, 1);
6028 op[2] = XEXP (x, 2);
6031 fun = (verbose) ? "zero_extract" : "zxt";
6032 op[0] = XEXP (x, 0);
6033 op[1] = XEXP (x, 1);
6034 op[2] = XEXP (x, 2);
6037 fun = (verbose) ? "sign_extend" : "sxn";
6038 op[0] = XEXP (x, 0);
6041 fun = (verbose) ? "zero_extend" : "zxn";
6042 op[0] = XEXP (x, 0);
6045 fun = (verbose) ? "float_extend" : "fxn";
6046 op[0] = XEXP (x, 0);
6049 fun = (verbose) ? "trunc" : "trn";
6050 op[0] = XEXP (x, 0);
6052 case FLOAT_TRUNCATE:
6053 fun = (verbose) ? "float_trunc" : "ftr";
6054 op[0] = XEXP (x, 0);
6057 fun = (verbose) ? "float" : "flt";
6058 op[0] = XEXP (x, 0);
6060 case UNSIGNED_FLOAT:
6061 fun = (verbose) ? "uns_float" : "ufl";
6062 op[0] = XEXP (x, 0);
6066 op[0] = XEXP (x, 0);
6069 fun = (verbose) ? "uns_fix" : "ufx";
6070 op[0] = XEXP (x, 0);
6074 op[0] = XEXP (x, 0);
6078 op[0] = XEXP (x, 0);
6081 op[0] = XEXP (x, 0);
6085 op[0] = XEXP (x, 0);
6090 op[0] = XEXP (x, 0);
6094 op[1] = XEXP (x, 1);
6099 op[0] = XEXP (x, 0);
6101 op[1] = XEXP (x, 1);
6103 op[2] = XEXP (x, 2);
6108 op[0] = TRAP_CONDITION (x);
6111 case UNSPEC_VOLATILE:
6113 cur = safe_concat (buf, cur, "unspec");
6114 if (GET_CODE (x) == UNSPEC_VOLATILE)
6115 cur = safe_concat (buf, cur, "/v");
6116 cur = safe_concat (buf, cur, "[");
6118 for (i = 0; i < XVECLEN (x, 0); i++)
6120 print_pattern (tmp, XVECEXP (x, 0, i), verbose);
6121 cur = safe_concat (buf, cur, sep);
6122 cur = safe_concat (buf, cur, tmp);
6125 cur = safe_concat (buf, cur, "] ");
6126 sprintf (tmp, "%d", XINT (x, 1));
6127 cur = safe_concat (buf, cur, tmp);
6131 /* if (verbose) debug_rtx (x); */
6132 st[0] = GET_RTX_NAME (GET_CODE (x));
6136 /* Print this as a function? */
6139 cur = safe_concat (buf, cur, fun);
6140 cur = safe_concat (buf, cur, "(");
6143 for (i = 0; i < 4; i++)
6146 cur = safe_concat (buf, cur, st[i]);
6151 cur = safe_concat (buf, cur, ",");
6153 print_value (tmp, op[i], verbose);
6154 cur = safe_concat (buf, cur, tmp);
6159 cur = safe_concat (buf, cur, ")");
6162 /* Prints rtxes, i customly classified as values. They're constants, */
6163 /* registers, labels, symbols and memory accesses. */
6166 print_value (buf, x, verbose)
6174 switch (GET_CODE (x))
6177 sprintf (t, HOST_WIDE_INT_PRINT_HEX, INTVAL (x));
6178 cur = safe_concat (buf, cur, t);
6181 sprintf (t, "<0x%lx,0x%lx>", (long)XWINT (x, 2), (long)XWINT (x, 3));
6182 cur = safe_concat (buf, cur, t);
6185 cur = safe_concat (buf, cur, "\"");
6186 cur = safe_concat (buf, cur, XSTR (x, 0));
6187 cur = safe_concat (buf, cur, "\"");
6190 cur = safe_concat (buf, cur, "`");
6191 cur = safe_concat (buf, cur, XSTR (x, 0));
6192 cur = safe_concat (buf, cur, "'");
6195 sprintf (t, "L%d", INSN_UID (XEXP (x, 0)));
6196 cur = safe_concat (buf, cur, t);
6199 print_value (t, XEXP (x, 0), verbose);
6200 cur = safe_concat (buf, cur, "const(");
6201 cur = safe_concat (buf, cur, t);
6202 cur = safe_concat (buf, cur, ")");
6205 print_value (t, XEXP (x, 0), verbose);
6206 cur = safe_concat (buf, cur, "high(");
6207 cur = safe_concat (buf, cur, t);
6208 cur = safe_concat (buf, cur, ")");
6211 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
6213 int c = reg_names[ REGNO (x) ][0];
6214 if (c >= '0' && c <= '9')
6215 cur = safe_concat (buf, cur, "%");
6217 cur = safe_concat (buf, cur, reg_names[ REGNO (x) ]);
6221 sprintf (t, "r%d", REGNO (x));
6222 cur = safe_concat (buf, cur, t);
6226 print_value (t, SUBREG_REG (x), verbose);
6227 cur = safe_concat (buf, cur, t);
6228 sprintf (t, "#%d", SUBREG_WORD (x));
6229 cur = safe_concat (buf, cur, t);
6232 cur = safe_concat (buf, cur, "scratch");
6235 cur = safe_concat (buf, cur, "cc0");
6238 cur = safe_concat (buf, cur, "pc");
6241 print_value (t, XEXP (x, 0), verbose);
6242 cur = safe_concat (buf, cur, "[");
6243 cur = safe_concat (buf, cur, t);
6244 cur = safe_concat (buf, cur, "]");
6247 print_exp (t, x, verbose);
6248 cur = safe_concat (buf, cur, t);
6253 /* The next step in insn detalization, its pattern recognition */
6256 print_pattern (buf, x, verbose)
6261 char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
6263 switch (GET_CODE (x))
6266 print_value (t1, SET_DEST (x), verbose);
6267 print_value (t2, SET_SRC (x), verbose);
6268 sprintf (buf, "%s=%s", t1, t2);
6271 sprintf (buf, "return");
6274 print_exp (buf, x, verbose);
6277 print_value (t1, XEXP (x, 0), verbose);
6278 sprintf (buf, "clobber %s", t1);
6281 print_value (t1, XEXP (x, 0), verbose);
6282 sprintf (buf, "use %s", t1);
6289 for (i = 0; i < XVECLEN (x, 0); i++)
6291 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6292 sprintf (t3, "%s%s;", t1, t2);
6295 sprintf (buf, "%s}", t1);
6302 sprintf (t1, "%%{");
6303 for (i = 0; i < XVECLEN (x, 0); i++)
6305 print_insn (t2, XVECEXP (x, 0, i), verbose);
6306 sprintf (t3, "%s%s;", t1, t2);
6309 sprintf (buf, "%s%%}", t1);
6313 sprintf (buf, "asm {%s}", XSTR (x, 0));
6318 print_value (buf, XEXP (x, 0), verbose);
6321 print_value (t1, TRAP_CONDITION (x), verbose);
6322 sprintf (buf, "trap_if %s", t1);
6328 sprintf (t1, "unspec{");
6329 for (i = 0; i < XVECLEN (x, 0); i++)
6331 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6332 sprintf (t3, "%s%s;", t1, t2);
6335 sprintf (buf, "%s}", t1);
6338 case UNSPEC_VOLATILE:
6342 sprintf (t1, "unspec/v{");
6343 for (i = 0; i < XVECLEN (x, 0); i++)
6345 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6346 sprintf (t3, "%s%s;", t1, t2);
6349 sprintf (buf, "%s}", t1);
6353 print_value (buf, x, verbose);
6355 } /* print_pattern */
6357 /* This is the main function in rtl visualization mechanism. It
6358 accepts an rtx and tries to recognize it as an insn, then prints it
6359 properly in human readable form, resembling assembler mnemonics. */
6360 /* For every insn it prints its UID and BB the insn belongs */
6361 /* too. (probably the last "option" should be extended somehow, since */
6362 /* it depends now on sched.c inner variables ...) */
6365 print_insn (buf, x, verbose)
6373 switch (GET_CODE (x))
6376 print_pattern (t, PATTERN (x), verbose);
6378 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (x),
6381 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6384 print_pattern (t, PATTERN (x), verbose);
6386 sprintf (buf, "b%d: i% 4d: jump %s", INSN_BB (x),
6389 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6393 if (GET_CODE (x) == PARALLEL)
6395 x = XVECEXP (x, 0, 0);
6396 print_pattern (t, x, verbose);
6399 strcpy (t, "call <...>");
6401 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (insn),
6402 INSN_UID (insn), t);
6404 sprintf (buf, "%-4d %s", INSN_UID (insn), t);
6407 sprintf (buf, "L%d:", INSN_UID (x));
6410 sprintf (buf, "i% 4d: barrier", INSN_UID (x));
6413 if (NOTE_LINE_NUMBER (x) > 0)
6414 sprintf (buf, "%4d note \"%s\" %d", INSN_UID (x),
6415 NOTE_SOURCE_FILE (x), NOTE_LINE_NUMBER (x));
6417 sprintf (buf, "%4d %s", INSN_UID (x),
6418 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x)));
6423 sprintf (buf, "Not an INSN at all\n");
6427 sprintf (buf, "i%-4d <What?>", INSN_UID (x));
6431 /* Print visualization debugging info */
6434 print_block_visualization (b, s)
6441 fprintf (dump, "\n;; ==================== scheduling visualization for block %d %s \n", b, s);
6443 /* Print names of units */
6444 fprintf (dump, ";; %-8s", "clock");
6445 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6446 if (function_units[unit].bitmask & target_units)
6447 for (i = 0; i < function_units[unit].multiplicity; i++)
6448 fprintf (dump, " %-33s", function_units[unit].name);
6449 fprintf (dump, " %-8s\n", "no-unit");
6451 fprintf (dump, ";; %-8s", "=====");
6452 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6453 if (function_units[unit].bitmask & target_units)
6454 for (i = 0; i < function_units[unit].multiplicity; i++)
6455 fprintf (dump, " %-33s", "==============================");
6456 fprintf (dump, " %-8s\n", "=======");
6458 /* Print insns in each cycle */
6459 fprintf (dump, "%s\n", visual_tbl);
6462 /* Print insns in the 'no_unit' column of visualization */
6465 visualize_no_unit (insn)
6468 vis_no_unit[n_vis_no_unit] = insn;
6472 /* Print insns scheduled in clock, for visualization. */
6475 visualize_scheduled_insns (b, clock)
6480 /* if no more room, split table into two */
6481 if (n_visual_lines >= MAX_VISUAL_LINES)
6483 print_block_visualization (b, "(incomplete)");
6484 init_block_visualization ();
6489 sprintf (visual_tbl + strlen (visual_tbl), ";; %-8d", clock);
6490 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6491 if (function_units[unit].bitmask & target_units)
6492 for (i = 0; i < function_units[unit].multiplicity; i++)
6494 int instance = unit + i * FUNCTION_UNITS_SIZE;
6495 rtx insn = unit_last_insn[instance];
6497 /* print insns that still keep the unit busy */
6499 actual_hazard_this_instance (unit, instance, insn, clock, 0))
6502 print_insn (str, insn, 0);
6503 str[INSN_LEN] = '\0';
6504 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", str);
6507 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", "------------------------------");
6510 /* print insns that are not assigned to any unit */
6511 for (i = 0; i < n_vis_no_unit; i++)
6512 sprintf (visual_tbl + strlen (visual_tbl), " %-8d",
6513 INSN_UID (vis_no_unit[i]));
6516 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6519 /* Print stalled cycles */
6522 visualize_stall_cycles (b, stalls)
6527 /* if no more room, split table into two */
6528 if (n_visual_lines >= MAX_VISUAL_LINES)
6530 print_block_visualization (b, "(incomplete)");
6531 init_block_visualization ();
6536 sprintf (visual_tbl + strlen (visual_tbl), ";; ");
6537 for (i = 0; i < stalls; i++)
6538 sprintf (visual_tbl + strlen (visual_tbl), ".");
6539 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6542 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn */
6545 move_insn1 (insn, last)
6548 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
6549 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
6551 NEXT_INSN (insn) = NEXT_INSN (last);
6552 PREV_INSN (NEXT_INSN (last)) = insn;
6554 NEXT_INSN (last) = insn;
6555 PREV_INSN (insn) = last;
6560 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
6561 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
6562 NOTEs. The REG_DEAD note following first one is contains the saved
6563 value for NOTE_BLOCK_NUMBER which is useful for
6564 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
6565 output by the instruction scheduler. Return the new value of LAST. */
6568 reemit_notes (insn, last)
6575 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
6577 if (REG_NOTE_KIND (note) == REG_DEAD
6578 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6580 int note_type = INTVAL (XEXP (note, 0));
6581 if (note_type == NOTE_INSN_SETJMP)
6583 retval = emit_note_after (NOTE_INSN_SETJMP, insn);
6584 CONST_CALL_P (retval) = CONST_CALL_P (note);
6585 remove_note (insn, note);
6586 note = XEXP (note, 1);
6588 else if (note_type == NOTE_INSN_RANGE_START
6589 || note_type == NOTE_INSN_RANGE_END)
6591 last = emit_note_before (note_type, last);
6592 remove_note (insn, note);
6593 note = XEXP (note, 1);
6594 NOTE_RANGE_INFO (last) = XEXP (note, 0);
6598 last = emit_note_before (note_type, last);
6599 remove_note (insn, note);
6600 note = XEXP (note, 1);
6601 NOTE_BLOCK_NUMBER (last) = INTVAL (XEXP (note, 0));
6603 remove_note (insn, note);
6609 /* Move INSN, and all insns which should be issued before it,
6610 due to SCHED_GROUP_P flag. Reemit notes if needed.
6612 Return the last insn emitted by the scheduler, which is the
6613 return value from the first call to reemit_notes. */
6616 move_insn (insn, last)
6621 /* If INSN has SCHED_GROUP_P set, then issue it and any other
6622 insns with SCHED_GROUP_P set first. */
6623 while (SCHED_GROUP_P (insn))
6625 rtx prev = PREV_INSN (insn);
6627 /* Move a SCHED_GROUP_P insn. */
6628 move_insn1 (insn, last);
6629 /* If this is the first call to reemit_notes, then record
6630 its return value. */
6631 if (retval == NULL_RTX)
6632 retval = reemit_notes (insn, insn);
6634 reemit_notes (insn, insn);
6638 /* Now move the first non SCHED_GROUP_P insn. */
6639 move_insn1 (insn, last);
6641 /* If this is the first call to reemit_notes, then record
6642 its return value. */
6643 if (retval == NULL_RTX)
6644 retval = reemit_notes (insn, insn);
6646 reemit_notes (insn, insn);
6651 /* Return an insn which represents a SCHED_GROUP, which is
6652 the last insn in the group. */
6663 insn = next_nonnote_insn (insn);
6665 while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
6670 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
6671 possibly bringing insns from subsequent blocks in the same region.
6672 Return number of insns scheduled. */
6675 schedule_block (bb, rgn_n_insns)
6679 /* Local variables. */
6685 /* flow block of this bb */
6686 int b = BB_TO_BLOCK (bb);
6688 /* target_n_insns == number of insns in b before scheduling starts.
6689 sched_target_n_insns == how many of b's insns were scheduled.
6690 sched_n_insns == how many insns were scheduled in b */
6691 int target_n_insns = 0;
6692 int sched_target_n_insns = 0;
6693 int sched_n_insns = 0;
6695 #define NEED_NOTHING 0
6700 /* head/tail info for this block */
6707 /* We used to have code to avoid getting parameters moved from hard
6708 argument registers into pseudos.
6710 However, it was removed when it proved to be of marginal benefit
6711 and caused problems because schedule_block and compute_forward_dependences
6712 had different notions of what the "head" insn was. */
6713 get_block_head_tail (bb, &head, &tail);
6715 /* Interblock scheduling could have moved the original head insn from this
6716 block into a proceeding block. This may also cause schedule_block and
6717 compute_forward_dependences to have different notions of what the
6720 If the interblock movement happened to make this block start with
6721 some notes (LOOP, EH or SETJMP) before the first real insn, then
6722 HEAD will have various special notes attached to it which must be
6723 removed so that we don't end up with extra copies of the notes. */
6724 if (GET_RTX_CLASS (GET_CODE (head)) == 'i')
6728 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
6729 if (REG_NOTE_KIND (note) == REG_DEAD
6730 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6731 remove_note (head, note);
6734 next_tail = NEXT_INSN (tail);
6735 prev_head = PREV_INSN (head);
6737 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6738 to schedule this block. */
6740 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6741 return (sched_n_insns);
6746 fprintf (dump, ";; ======================================================\n");
6748 ";; -- basic block %d from %d to %d -- %s reload\n",
6749 b, INSN_UID (BLOCK_HEAD (b)), INSN_UID (BLOCK_END (b)),
6750 (reload_completed ? "after" : "before"));
6751 fprintf (dump, ";; ======================================================\n");
6752 fprintf (dump, "\n");
6754 visual_tbl = (char *) alloca (get_visual_tbl_length ());
6755 init_block_visualization ();
6758 /* remove remaining note insns from the block, save them in
6759 note_list. These notes are restored at the end of
6760 schedule_block (). */
6762 rm_other_notes (head, tail);
6766 /* prepare current target block info */
6767 if (current_nr_blocks > 1)
6769 candidate_table = (candidate *) alloca (current_nr_blocks * sizeof (candidate));
6772 /* ??? It is not clear why bblst_size is computed this way. The original
6773 number was clearly too small as it resulted in compiler failures.
6774 Multiplying by the original number by 2 (to account for update_bbs
6775 members) seems to be a reasonable solution. */
6776 /* ??? Or perhaps there is a bug somewhere else in this file? */
6777 bblst_size = (current_nr_blocks - bb) * rgn_nr_edges * 2;
6778 bblst_table = (int *) alloca (bblst_size * sizeof (int));
6780 bitlst_table_last = 0;
6781 bitlst_table_size = rgn_nr_edges;
6782 bitlst_table = (int *) alloca (rgn_nr_edges * sizeof (int));
6784 compute_trg_info (bb);
6789 /* Allocate the ready list */
6790 ready = (rtx *) alloca ((rgn_n_insns + 1) * sizeof (rtx));
6792 /* Print debugging information. */
6793 if (sched_verbose >= 5)
6794 debug_dependencies ();
6797 /* Initialize ready list with all 'ready' insns in target block.
6798 Count number of insns in the target block being scheduled. */
6800 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6804 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6806 next = NEXT_INSN (insn);
6808 if (INSN_DEP_COUNT (insn) == 0
6809 && (SCHED_GROUP_P (next) == 0 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6810 ready[n_ready++] = insn;
6811 if (!(SCHED_GROUP_P (insn)))
6815 /* Add to ready list all 'ready' insns in valid source blocks.
6816 For speculative insns, check-live, exception-free, and
6818 for (bb_src = bb + 1; bb_src < current_nr_blocks; bb_src++)
6819 if (IS_VALID (bb_src))
6825 get_block_head_tail (bb_src, &head, &tail);
6826 src_next_tail = NEXT_INSN (tail);
6830 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6833 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
6835 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6838 if (!CANT_MOVE (insn)
6839 && (!IS_SPECULATIVE_INSN (insn)
6840 || (insn_issue_delay (insn) <= 3
6841 && check_live (insn, bb_src)
6842 && is_exception_free (insn, bb_src, target_bb))))
6847 next = NEXT_INSN (insn);
6848 if (INSN_DEP_COUNT (insn) == 0
6849 && (SCHED_GROUP_P (next) == 0
6850 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6851 ready[n_ready++] = insn;
6856 #ifdef MD_SCHED_INIT
6857 MD_SCHED_INIT (dump, sched_verbose);
6860 /* no insns scheduled in this block yet */
6861 last_scheduled_insn = 0;
6863 /* Q_SIZE is the total number of insns in the queue. */
6867 bzero ((char *) insn_queue, sizeof (insn_queue));
6869 /* Start just before the beginning of time. */
6872 /* We start inserting insns after PREV_HEAD. */
6875 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6876 new_needs = (NEXT_INSN (prev_head) == BLOCK_HEAD (b)
6877 ? NEED_HEAD : NEED_NOTHING);
6878 if (PREV_INSN (next_tail) == BLOCK_END (b))
6879 new_needs |= NEED_TAIL;
6881 /* loop until all the insns in BB are scheduled. */
6882 while (sched_target_n_insns < target_n_insns)
6888 /* Add to the ready list all pending insns that can be issued now.
6889 If there are no ready insns, increment clock until one
6890 is ready and add all pending insns at that point to the ready
6892 n_ready = queue_to_ready (ready, n_ready);
6897 if (sched_verbose >= 2)
6899 fprintf (dump, ";;\t\tReady list after queue_to_ready: ");
6900 debug_ready_list (ready, n_ready);
6903 /* Sort the ready list based on priority. */
6904 SCHED_SORT (ready, n_ready);
6906 /* Allow the target to reorder the list, typically for
6907 better instruction bundling. */
6908 #ifdef MD_SCHED_REORDER
6909 MD_SCHED_REORDER (dump, sched_verbose, ready, n_ready, clock_var,
6912 can_issue_more = issue_rate;
6917 fprintf (dump, "\n;;\tReady list (t =%3d): ", clock_var);
6918 debug_ready_list (ready, n_ready);
6921 /* Issue insns from ready list. */
6922 while (n_ready != 0 && can_issue_more)
6924 /* Select and remove the insn from the ready list. */
6925 rtx insn = ready[--n_ready];
6926 int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
6930 queue_insn (insn, cost);
6934 /* An interblock motion? */
6935 if (INSN_BB (insn) != target_bb)
6939 if (IS_SPECULATIVE_INSN (insn))
6941 if (!check_live (insn, INSN_BB (insn)))
6943 update_live (insn, INSN_BB (insn));
6945 /* For speculative load, mark insns fed by it. */
6946 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
6947 set_spec_fed (insn);
6954 while (SCHED_GROUP_P (temp))
6955 temp = PREV_INSN (temp);
6957 /* Update source block boundaries. */
6958 b1 = INSN_BLOCK (temp);
6959 if (temp == BLOCK_HEAD (b1)
6960 && insn == BLOCK_END (b1))
6962 /* We moved all the insns in the basic block.
6963 Emit a note after the last insn and update the
6964 begin/end boundaries to point to the note. */
6965 emit_note_after (NOTE_INSN_DELETED, insn);
6966 BLOCK_END (b1) = NEXT_INSN (insn);
6967 BLOCK_HEAD (b1) = NEXT_INSN (insn);
6969 else if (insn == BLOCK_END (b1))
6971 /* We took insns from the end of the basic block,
6972 so update the end of block boundary so that it
6973 points to the first insn we did not move. */
6974 BLOCK_END (b1) = PREV_INSN (temp);
6976 else if (temp == BLOCK_HEAD (b1))
6978 /* We took insns from the start of the basic block,
6979 so update the start of block boundary so that
6980 it points to the first insn we did not move. */
6981 BLOCK_HEAD (b1) = NEXT_INSN (insn);
6986 /* In block motion. */
6987 sched_target_n_insns++;
6990 last_scheduled_insn = insn;
6991 last = move_insn (insn, last);
6994 #ifdef MD_SCHED_VARIABLE_ISSUE
6995 MD_SCHED_VARIABLE_ISSUE (dump, sched_verbose, insn,
7001 n_ready = schedule_insn (insn, ready, n_ready, clock_var);
7003 /* Close this block after scheduling its jump. */
7004 if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
7010 visualize_scheduled_insns (b, clock_var);
7016 fprintf (dump, ";;\tReady list (final): ");
7017 debug_ready_list (ready, n_ready);
7018 print_block_visualization (b, "");
7021 /* Sanity check -- queue must be empty now. Meaningless if region has
7023 if (current_nr_blocks > 1)
7024 if (!flag_schedule_interblock && q_size != 0)
7027 /* update head/tail boundaries. */
7028 head = NEXT_INSN (prev_head);
7031 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
7032 previously found among the insns. Insert them at the beginning
7036 rtx note_head = note_list;
7038 while (PREV_INSN (note_head))
7040 note_head = PREV_INSN (note_head);
7043 PREV_INSN (note_head) = PREV_INSN (head);
7044 NEXT_INSN (PREV_INSN (head)) = note_head;
7045 PREV_INSN (head) = note_list;
7046 NEXT_INSN (note_list) = head;
7050 /* update target block boundaries. */
7051 if (new_needs & NEED_HEAD)
7052 BLOCK_HEAD (b) = head;
7054 if (new_needs & NEED_TAIL)
7055 BLOCK_END (b) = tail;
7060 fprintf (dump, ";; total time = %d\n;; new basic block head = %d\n",
7061 clock_var, INSN_UID (BLOCK_HEAD (b)));
7062 fprintf (dump, ";; new basic block end = %d\n\n",
7063 INSN_UID (BLOCK_END (b)));
7066 return (sched_n_insns);
7067 } /* schedule_block () */
7070 /* print the bit-set of registers, S. callable from debugger */
7073 debug_reg_vector (s)
7078 EXECUTE_IF_SET_IN_REG_SET (s, 0, regno,
7080 fprintf (dump, " %d", regno);
7083 fprintf (dump, "\n");
7086 /* Use the backward dependences from LOG_LINKS to build
7087 forward dependences in INSN_DEPEND. */
7090 compute_block_forward_dependences (bb)
7096 enum reg_note dep_type;
7098 get_block_head_tail (bb, &head, &tail);
7099 next_tail = NEXT_INSN (tail);
7100 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
7102 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7105 insn = group_leader (insn);
7107 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
7109 rtx x = group_leader (XEXP (link, 0));
7112 if (x != XEXP (link, 0))
7115 /* Ignore dependences upon deleted insn */
7116 if (GET_CODE (x) == NOTE || INSN_DELETED_P (x))
7118 if (find_insn_list (insn, INSN_DEPEND (x)))
7121 new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
7123 dep_type = REG_NOTE_KIND (link);
7124 PUT_REG_NOTE_KIND (new_link, dep_type);
7126 INSN_DEPEND (x) = new_link;
7127 INSN_DEP_COUNT (insn) += 1;
7132 /* Initialize variables for region data dependence analysis.
7133 n_bbs is the number of region blocks */
7135 __inline static void
7136 init_rgn_data_dependences (n_bbs)
7141 /* variables for which one copy exists for each block */
7142 bzero ((char *) bb_pending_read_insns, n_bbs * sizeof (rtx));
7143 bzero ((char *) bb_pending_read_mems, n_bbs * sizeof (rtx));
7144 bzero ((char *) bb_pending_write_insns, n_bbs * sizeof (rtx));
7145 bzero ((char *) bb_pending_write_mems, n_bbs * sizeof (rtx));
7146 bzero ((char *) bb_pending_lists_length, n_bbs * sizeof (rtx));
7147 bzero ((char *) bb_last_pending_memory_flush, n_bbs * sizeof (rtx));
7148 bzero ((char *) bb_last_function_call, n_bbs * sizeof (rtx));
7149 bzero ((char *) bb_sched_before_next_call, n_bbs * sizeof (rtx));
7151 /* Create an insn here so that we can hang dependencies off of it later. */
7152 for (bb = 0; bb < n_bbs; bb++)
7154 bb_sched_before_next_call[bb] =
7155 gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
7156 NULL_RTX, 0, NULL_RTX, NULL_RTX);
7157 LOG_LINKS (bb_sched_before_next_call[bb]) = 0;
7161 /* Add dependences so that branches are scheduled to run last in their block */
7164 add_branch_dependences (head, tail)
7170 /* For all branches, calls, uses, and cc0 setters, force them to remain
7171 in order at the end of the block by adding dependencies and giving
7172 the last a high priority. There may be notes present, and prev_head
7175 Branches must obviously remain at the end. Calls should remain at the
7176 end since moving them results in worse register allocation. Uses remain
7177 at the end to ensure proper register allocation. cc0 setters remaim
7178 at the end because they can't be moved away from their cc0 user. */
7181 while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
7182 || (GET_CODE (insn) == INSN
7183 && (GET_CODE (PATTERN (insn)) == USE
7185 || sets_cc0_p (PATTERN (insn))
7188 || GET_CODE (insn) == NOTE)
7190 if (GET_CODE (insn) != NOTE)
7193 && !find_insn_list (insn, LOG_LINKS (last)))
7195 add_dependence (last, insn, REG_DEP_ANTI);
7196 INSN_REF_COUNT (insn)++;
7199 CANT_MOVE (insn) = 1;
7202 /* Skip over insns that are part of a group.
7203 Make each insn explicitly depend on the previous insn.
7204 This ensures that only the group header will ever enter
7205 the ready queue (and, when scheduled, will automatically
7206 schedule the SCHED_GROUP_P block). */
7207 while (SCHED_GROUP_P (insn))
7209 rtx temp = prev_nonnote_insn (insn);
7210 add_dependence (insn, temp, REG_DEP_ANTI);
7215 /* Don't overrun the bounds of the basic block. */
7219 insn = PREV_INSN (insn);
7222 /* make sure these insns are scheduled last in their block */
7225 while (insn != head)
7227 insn = prev_nonnote_insn (insn);
7229 if (INSN_REF_COUNT (insn) != 0)
7232 if (!find_insn_list (last, LOG_LINKS (insn)))
7233 add_dependence (last, insn, REG_DEP_ANTI);
7234 INSN_REF_COUNT (insn) = 1;
7236 /* Skip over insns that are part of a group. */
7237 while (SCHED_GROUP_P (insn))
7238 insn = prev_nonnote_insn (insn);
7242 /* Compute bacward dependences inside BB. In a multiple blocks region:
7243 (1) a bb is analyzed after its predecessors, and (2) the lists in
7244 effect at the end of bb (after analyzing for bb) are inherited by
7247 Specifically for reg-reg data dependences, the block insns are
7248 scanned by sched_analyze () top-to-bottom. Two lists are
7249 naintained by sched_analyze (): reg_last_defs[] for register DEFs,
7250 and reg_last_uses[] for register USEs.
7252 When analysis is completed for bb, we update for its successors:
7253 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7254 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7256 The mechanism for computing mem-mem data dependence is very
7257 similar, and the result is interblock dependences in the region. */
7260 compute_block_backward_dependences (bb)
7266 int max_reg = max_reg_num ();
7268 b = BB_TO_BLOCK (bb);
7270 if (current_nr_blocks == 1)
7272 reg_last_uses = (rtx *) alloca (max_reg * sizeof (rtx));
7273 reg_last_sets = (rtx *) alloca (max_reg * sizeof (rtx));
7274 reg_last_clobbers = (rtx *) alloca (max_reg * sizeof (rtx));
7276 bzero ((char *) reg_last_uses, max_reg * sizeof (rtx));
7277 bzero ((char *) reg_last_sets, max_reg * sizeof (rtx));
7278 bzero ((char *) reg_last_clobbers, max_reg * sizeof (rtx));
7280 pending_read_insns = 0;
7281 pending_read_mems = 0;
7282 pending_write_insns = 0;
7283 pending_write_mems = 0;
7284 pending_lists_length = 0;
7285 last_function_call = 0;
7286 last_pending_memory_flush = 0;
7287 sched_before_next_call
7288 = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
7289 NULL_RTX, 0, NULL_RTX, NULL_RTX);
7290 LOG_LINKS (sched_before_next_call) = 0;
7294 reg_last_uses = bb_reg_last_uses[bb];
7295 reg_last_sets = bb_reg_last_sets[bb];
7296 reg_last_clobbers = bb_reg_last_clobbers[bb];
7298 pending_read_insns = bb_pending_read_insns[bb];
7299 pending_read_mems = bb_pending_read_mems[bb];
7300 pending_write_insns = bb_pending_write_insns[bb];
7301 pending_write_mems = bb_pending_write_mems[bb];
7302 pending_lists_length = bb_pending_lists_length[bb];
7303 last_function_call = bb_last_function_call[bb];
7304 last_pending_memory_flush = bb_last_pending_memory_flush[bb];
7306 sched_before_next_call = bb_sched_before_next_call[bb];
7309 /* do the analysis for this block */
7310 get_block_head_tail (bb, &head, &tail);
7311 sched_analyze (head, tail);
7312 add_branch_dependences (head, tail);
7314 if (current_nr_blocks > 1)
7317 int b_succ, bb_succ;
7319 rtx link_insn, link_mem;
7322 /* these lists should point to the right place, for correct freeing later. */
7323 bb_pending_read_insns[bb] = pending_read_insns;
7324 bb_pending_read_mems[bb] = pending_read_mems;
7325 bb_pending_write_insns[bb] = pending_write_insns;
7326 bb_pending_write_mems[bb] = pending_write_mems;
7328 /* bb's structures are inherited by it's successors */
7329 first_edge = e = OUT_EDGES (b);
7333 b_succ = TO_BLOCK (e);
7334 bb_succ = BLOCK_TO_BB (b_succ);
7336 /* only bbs "below" bb, in the same region, are interesting */
7337 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
7344 for (reg = 0; reg < max_reg; reg++)
7347 /* reg-last-uses lists are inherited by bb_succ */
7348 for (u = reg_last_uses[reg]; u; u = XEXP (u, 1))
7350 if (find_insn_list (XEXP (u, 0), (bb_reg_last_uses[bb_succ])[reg]))
7353 (bb_reg_last_uses[bb_succ])[reg]
7354 = alloc_INSN_LIST (XEXP (u, 0),
7355 (bb_reg_last_uses[bb_succ])[reg]);
7358 /* reg-last-defs lists are inherited by bb_succ */
7359 for (u = reg_last_sets[reg]; u; u = XEXP (u, 1))
7361 if (find_insn_list (XEXP (u, 0), (bb_reg_last_sets[bb_succ])[reg]))
7364 (bb_reg_last_sets[bb_succ])[reg]
7365 = alloc_INSN_LIST (XEXP (u, 0),
7366 (bb_reg_last_sets[bb_succ])[reg]);
7369 for (u = reg_last_clobbers[reg]; u; u = XEXP (u, 1))
7371 if (find_insn_list (XEXP (u, 0), (bb_reg_last_clobbers[bb_succ])[reg]))
7374 (bb_reg_last_clobbers[bb_succ])[reg]
7375 = alloc_INSN_LIST (XEXP (u, 0),
7376 (bb_reg_last_clobbers[bb_succ])[reg]);
7380 /* mem read/write lists are inherited by bb_succ */
7381 link_insn = pending_read_insns;
7382 link_mem = pending_read_mems;
7385 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7386 bb_pending_read_insns[bb_succ],
7387 bb_pending_read_mems[bb_succ])))
7388 add_insn_mem_dependence (&bb_pending_read_insns[bb_succ],
7389 &bb_pending_read_mems[bb_succ],
7390 XEXP (link_insn, 0), XEXP (link_mem, 0));
7391 link_insn = XEXP (link_insn, 1);
7392 link_mem = XEXP (link_mem, 1);
7395 link_insn = pending_write_insns;
7396 link_mem = pending_write_mems;
7399 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7400 bb_pending_write_insns[bb_succ],
7401 bb_pending_write_mems[bb_succ])))
7402 add_insn_mem_dependence (&bb_pending_write_insns[bb_succ],
7403 &bb_pending_write_mems[bb_succ],
7404 XEXP (link_insn, 0), XEXP (link_mem, 0));
7406 link_insn = XEXP (link_insn, 1);
7407 link_mem = XEXP (link_mem, 1);
7410 /* last_function_call is inherited by bb_succ */
7411 for (u = last_function_call; u; u = XEXP (u, 1))
7413 if (find_insn_list (XEXP (u, 0), bb_last_function_call[bb_succ]))
7416 bb_last_function_call[bb_succ]
7417 = alloc_INSN_LIST (XEXP (u, 0),
7418 bb_last_function_call[bb_succ]);
7421 /* last_pending_memory_flush is inherited by bb_succ */
7422 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
7424 if (find_insn_list (XEXP (u, 0), bb_last_pending_memory_flush[bb_succ]))
7427 bb_last_pending_memory_flush[bb_succ]
7428 = alloc_INSN_LIST (XEXP (u, 0),
7429 bb_last_pending_memory_flush[bb_succ]);
7432 /* sched_before_next_call is inherited by bb_succ */
7433 x = LOG_LINKS (sched_before_next_call);
7434 for (; x; x = XEXP (x, 1))
7435 add_dependence (bb_sched_before_next_call[bb_succ],
7436 XEXP (x, 0), REG_DEP_ANTI);
7440 while (e != first_edge);
7443 /* Free up the INSN_LISTs
7445 Note this loop is executed max_reg * nr_regions times. It's first
7446 implementation accounted for over 90% of the calls to free_list.
7447 The list was empty for the vast majority of those calls. On the PA,
7448 not calling free_list in those cases improves -O2 compile times by
7450 for (b = 0; b < max_reg; ++b)
7452 if (reg_last_clobbers[b])
7453 free_list (®_last_clobbers[b], &unused_insn_list);
7454 if (reg_last_sets[b])
7455 free_list (®_last_sets[b], &unused_insn_list);
7456 if (reg_last_uses[b])
7457 free_list (®_last_uses[b], &unused_insn_list);
7460 /* Assert that we won't need bb_reg_last_* for this block anymore. */
7461 if (current_nr_blocks > 1)
7463 bb_reg_last_uses[bb] = (rtx *) NULL_RTX;
7464 bb_reg_last_sets[bb] = (rtx *) NULL_RTX;
7465 bb_reg_last_clobbers[bb] = (rtx *) NULL_RTX;
7469 /* Print dependences for debugging, callable from debugger */
7472 debug_dependencies ()
7476 fprintf (dump, ";; --------------- forward dependences: ------------ \n");
7477 for (bb = 0; bb < current_nr_blocks; bb++)
7485 get_block_head_tail (bb, &head, &tail);
7486 next_tail = NEXT_INSN (tail);
7487 fprintf (dump, "\n;; --- Region Dependences --- b %d bb %d \n",
7488 BB_TO_BLOCK (bb), bb);
7490 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7491 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7492 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7493 "----", "----", "--", "---", "----", "----", "--------", "-----");
7494 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
7499 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7502 fprintf (dump, ";; %6d ", INSN_UID (insn));
7503 if (GET_CODE (insn) == NOTE)
7505 n = NOTE_LINE_NUMBER (insn);
7507 fprintf (dump, "%s\n", GET_NOTE_INSN_NAME (n));
7509 fprintf (dump, "line %d, file %s\n", n,
7510 NOTE_SOURCE_FILE (insn));
7513 fprintf (dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
7517 unit = insn_unit (insn);
7519 || function_units[unit].blockage_range_function == 0) ? 0 :
7520 function_units[unit].blockage_range_function (insn);
7522 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7523 (SCHED_GROUP_P (insn) ? "+" : " "),
7527 INSN_DEP_COUNT (insn),
7528 INSN_PRIORITY (insn),
7529 insn_cost (insn, 0, 0),
7530 (int) MIN_BLOCKAGE_COST (range),
7531 (int) MAX_BLOCKAGE_COST (range));
7532 insn_print_units (insn);
7533 fprintf (dump, "\t: ");
7534 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
7535 fprintf (dump, "%d ", INSN_UID (XEXP (link, 0)));
7536 fprintf (dump, "\n");
7540 fprintf (dump, "\n");
7543 /* Set_priorities: compute priority of each insn in the block */
7556 get_block_head_tail (bb, &head, &tail);
7557 prev_head = PREV_INSN (head);
7560 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
7564 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
7567 if (GET_CODE (insn) == NOTE)
7570 if (!(SCHED_GROUP_P (insn)))
7572 (void) priority (insn);
7578 /* Make each element of VECTOR point at an rtx-vector,
7579 taking the space for all those rtx-vectors from SPACE.
7580 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7581 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7582 (this is the same as init_regset_vector () in flow.c) */
7585 init_rtx_vector (vector, space, nelts, bytes_per_elt)
7592 register rtx *p = space;
7594 for (i = 0; i < nelts; i++)
7597 p += bytes_per_elt / sizeof (*p);
7601 /* Schedule a region. A region is either an inner loop, a loop-free
7602 subroutine, or a single basic block. Each bb in the region is
7603 scheduled after its flow predecessors. */
7606 schedule_region (rgn)
7610 int rgn_n_insns = 0;
7611 int sched_rgn_n_insns = 0;
7613 /* set variables for the current region */
7614 current_nr_blocks = RGN_NR_BLOCKS (rgn);
7615 current_blocks = RGN_BLOCKS (rgn);
7617 reg_pending_sets = ALLOCA_REG_SET ();
7618 reg_pending_clobbers = ALLOCA_REG_SET ();
7619 reg_pending_sets_all = 0;
7621 /* initializations for region data dependence analyisis */
7622 if (current_nr_blocks > 1)
7625 int maxreg = max_reg_num ();
7627 bb_reg_last_uses = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7628 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7629 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7630 init_rtx_vector (bb_reg_last_uses, space, current_nr_blocks,
7631 maxreg * sizeof (rtx *));
7633 bb_reg_last_sets = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7634 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7635 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7636 init_rtx_vector (bb_reg_last_sets, space, current_nr_blocks,
7637 maxreg * sizeof (rtx *));
7639 bb_reg_last_clobbers =
7640 (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7641 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7642 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7643 init_rtx_vector (bb_reg_last_clobbers, space, current_nr_blocks,
7644 maxreg * sizeof (rtx *));
7646 bb_pending_read_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7647 bb_pending_read_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7648 bb_pending_write_insns =
7649 (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7650 bb_pending_write_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7651 bb_pending_lists_length =
7652 (int *) alloca (current_nr_blocks * sizeof (int));
7653 bb_last_pending_memory_flush =
7654 (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7655 bb_last_function_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7656 bb_sched_before_next_call =
7657 (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7659 init_rgn_data_dependences (current_nr_blocks);
7662 /* compute LOG_LINKS */
7663 for (bb = 0; bb < current_nr_blocks; bb++)
7664 compute_block_backward_dependences (bb);
7666 /* compute INSN_DEPEND */
7667 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7668 compute_block_forward_dependences (bb);
7670 /* Delete line notes, compute live-regs at block end, and set priorities. */
7672 for (bb = 0; bb < current_nr_blocks; bb++)
7674 if (reload_completed == 0)
7675 find_pre_sched_live (bb);
7677 if (write_symbols != NO_DEBUG)
7679 save_line_notes (bb);
7683 rgn_n_insns += set_priorities (bb);
7686 /* compute interblock info: probabilities, split-edges, dominators, etc. */
7687 if (current_nr_blocks > 1)
7691 prob = (float *) alloca ((current_nr_blocks) * sizeof (float));
7693 bbset_size = current_nr_blocks / HOST_BITS_PER_WIDE_INT + 1;
7694 dom = (bbset *) alloca (current_nr_blocks * sizeof (bbset));
7695 for (i = 0; i < current_nr_blocks; i++)
7697 dom[i] = (bbset) alloca (bbset_size * sizeof (HOST_WIDE_INT));
7698 bzero ((char *) dom[i], bbset_size * sizeof (HOST_WIDE_INT));
7703 edge_to_bit = (int *) alloca (nr_edges * sizeof (int));
7704 for (i = 1; i < nr_edges; i++)
7705 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
7706 EDGE_TO_BIT (i) = rgn_nr_edges++;
7707 rgn_edges = (int *) alloca (rgn_nr_edges * sizeof (int));
7710 for (i = 1; i < nr_edges; i++)
7711 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
7712 rgn_edges[rgn_nr_edges++] = i;
7715 edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
7716 pot_split = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7717 ancestor_edges = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7718 for (i = 0; i < current_nr_blocks; i++)
7721 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7722 bzero ((char *) pot_split[i],
7723 edgeset_size * sizeof (HOST_WIDE_INT));
7725 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7726 bzero ((char *) ancestor_edges[i],
7727 edgeset_size * sizeof (HOST_WIDE_INT));
7730 /* compute probabilities, dominators, split_edges */
7731 for (bb = 0; bb < current_nr_blocks; bb++)
7732 compute_dom_prob_ps (bb);
7735 /* now we can schedule all blocks */
7736 for (bb = 0; bb < current_nr_blocks; bb++)
7738 sched_rgn_n_insns += schedule_block (bb, rgn_n_insns);
7745 /* sanity check: verify that all region insns were scheduled */
7746 if (sched_rgn_n_insns != rgn_n_insns)
7749 /* update register life and usage information */
7750 if (reload_completed == 0)
7752 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7753 find_post_sched_live (bb);
7755 if (current_nr_blocks <= 1)
7756 /* Sanity check. There should be no REG_DEAD notes leftover at the end.
7757 In practice, this can occur as the result of bugs in flow, combine.c,
7758 and/or sched.c. The values of the REG_DEAD notes remaining are
7759 meaningless, because dead_notes is just used as a free list. */
7760 if (dead_notes != 0)
7764 /* restore line notes. */
7765 if (write_symbols != NO_DEBUG)
7767 for (bb = 0; bb < current_nr_blocks; bb++)
7768 restore_line_notes (bb);
7771 /* Done with this region */
7772 free_pending_lists ();
7774 FREE_REG_SET (reg_pending_sets);
7775 FREE_REG_SET (reg_pending_clobbers);
7778 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
7779 needed for the hard register mentioned in the note. This can happen
7780 if the reference to the hard register in the original insn was split into
7781 several smaller hard register references in the split insns. */
7784 split_hard_reg_notes (note, first, last)
7785 rtx note, first, last;
7787 rtx reg, temp, link;
7788 int n_regs, i, new_reg;
7791 /* Assume that this is a REG_DEAD note. */
7792 if (REG_NOTE_KIND (note) != REG_DEAD)
7795 reg = XEXP (note, 0);
7797 n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
7799 for (i = 0; i < n_regs; i++)
7801 new_reg = REGNO (reg) + i;
7803 /* Check for references to new_reg in the split insns. */
7804 for (insn = last;; insn = PREV_INSN (insn))
7806 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7807 && (temp = regno_use_in (new_reg, PATTERN (insn))))
7809 /* Create a new reg dead note ere. */
7810 link = alloc_EXPR_LIST (REG_DEAD, temp, REG_NOTES (insn));
7811 REG_NOTES (insn) = link;
7813 /* If killed multiple registers here, then add in the excess. */
7814 i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
7818 /* It isn't mentioned anywhere, so no new reg note is needed for
7826 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
7827 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
7830 new_insn_dead_notes (pat, insn, last, orig_insn)
7831 rtx pat, insn, last, orig_insn;
7835 /* PAT is either a CLOBBER or a SET here. */
7836 dest = XEXP (pat, 0);
7838 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
7839 || GET_CODE (dest) == STRICT_LOW_PART
7840 || GET_CODE (dest) == SIGN_EXTRACT)
7841 dest = XEXP (dest, 0);
7843 if (GET_CODE (dest) == REG)
7845 /* If the original insn already used this register, we may not add new
7846 notes for it. One example for a split that needs this test is
7847 when a multi-word memory access with register-indirect addressing
7848 is split into multiple memory accesses with auto-increment and
7849 one adjusting add instruction for the address register. */
7850 if (reg_referenced_p (dest, PATTERN (orig_insn)))
7852 for (tem = last; tem != insn; tem = PREV_INSN (tem))
7854 if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
7855 && reg_overlap_mentioned_p (dest, PATTERN (tem))
7856 && (set = single_set (tem)))
7858 rtx tem_dest = SET_DEST (set);
7860 while (GET_CODE (tem_dest) == ZERO_EXTRACT
7861 || GET_CODE (tem_dest) == SUBREG
7862 || GET_CODE (tem_dest) == STRICT_LOW_PART
7863 || GET_CODE (tem_dest) == SIGN_EXTRACT)
7864 tem_dest = XEXP (tem_dest, 0);
7866 if (!rtx_equal_p (tem_dest, dest))
7868 /* Use the same scheme as combine.c, don't put both REG_DEAD
7869 and REG_UNUSED notes on the same insn. */
7870 if (!find_regno_note (tem, REG_UNUSED, REGNO (dest))
7871 && !find_regno_note (tem, REG_DEAD, REGNO (dest)))
7873 rtx note = alloc_EXPR_LIST (REG_DEAD, dest,
7875 REG_NOTES (tem) = note;
7877 /* The reg only dies in one insn, the last one that uses
7881 else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
7882 /* We found an instruction that both uses the register,
7883 and sets it, so no new REG_NOTE is needed for this set. */
7887 /* If this is a set, it must die somewhere, unless it is the dest of
7888 the original insn, and hence is live after the original insn. Abort
7889 if it isn't supposed to be live after the original insn.
7891 If this is a clobber, then just add a REG_UNUSED note. */
7894 int live_after_orig_insn = 0;
7895 rtx pattern = PATTERN (orig_insn);
7898 if (GET_CODE (pat) == CLOBBER)
7900 rtx note = alloc_EXPR_LIST (REG_UNUSED, dest, REG_NOTES (insn));
7901 REG_NOTES (insn) = note;
7905 /* The original insn could have multiple sets, so search the
7906 insn for all sets. */
7907 if (GET_CODE (pattern) == SET)
7909 if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
7910 live_after_orig_insn = 1;
7912 else if (GET_CODE (pattern) == PARALLEL)
7914 for (i = 0; i < XVECLEN (pattern, 0); i++)
7915 if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
7916 && reg_overlap_mentioned_p (dest,
7917 SET_DEST (XVECEXP (pattern,
7919 live_after_orig_insn = 1;
7922 if (!live_after_orig_insn)
7928 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
7929 registers modified by X. INC is -1 if the containing insn is being deleted,
7930 and is 1 if the containing insn is a newly generated insn. */
7933 update_n_sets (x, inc)
7937 rtx dest = SET_DEST (x);
7939 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
7940 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
7941 dest = SUBREG_REG (dest);
7943 if (GET_CODE (dest) == REG)
7945 int regno = REGNO (dest);
7947 if (regno < FIRST_PSEUDO_REGISTER)
7950 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
7952 for (i = regno; i < endregno; i++)
7953 REG_N_SETS (i) += inc;
7956 REG_N_SETS (regno) += inc;
7960 /* Updates all flow-analysis related quantities (including REG_NOTES) for
7961 the insns from FIRST to LAST inclusive that were created by splitting
7962 ORIG_INSN. NOTES are the original REG_NOTES. */
7965 update_flow_info (notes, first, last, orig_insn)
7972 rtx orig_dest, temp;
7975 /* Get and save the destination set by the original insn. */
7977 orig_dest = single_set (orig_insn);
7979 orig_dest = SET_DEST (orig_dest);
7981 /* Move REG_NOTES from the original insn to where they now belong. */
7983 for (note = notes; note; note = next)
7985 next = XEXP (note, 1);
7986 switch (REG_NOTE_KIND (note))
7990 /* Move these notes from the original insn to the last new insn where
7991 the register is now set. */
7993 for (insn = last;; insn = PREV_INSN (insn))
7995 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7996 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
7998 /* If this note refers to a multiple word hard register, it
7999 may have been split into several smaller hard register
8000 references, so handle it specially. */
8001 temp = XEXP (note, 0);
8002 if (REG_NOTE_KIND (note) == REG_DEAD
8003 && GET_CODE (temp) == REG
8004 && REGNO (temp) < FIRST_PSEUDO_REGISTER
8005 && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
8006 split_hard_reg_notes (note, first, last);
8009 XEXP (note, 1) = REG_NOTES (insn);
8010 REG_NOTES (insn) = note;
8013 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
8015 /* ??? This won't handle multiple word registers correctly,
8016 but should be good enough for now. */
8017 if (REG_NOTE_KIND (note) == REG_UNUSED
8018 && GET_CODE (XEXP (note, 0)) != SCRATCH
8019 && !dead_or_set_p (insn, XEXP (note, 0)))
8020 PUT_REG_NOTE_KIND (note, REG_DEAD);
8022 /* The reg only dies in one insn, the last one that uses
8026 /* It must die somewhere, fail it we couldn't find where it died.
8028 If this is a REG_UNUSED note, then it must be a temporary
8029 register that was not needed by this instantiation of the
8030 pattern, so we can safely ignore it. */
8033 if (REG_NOTE_KIND (note) != REG_UNUSED)
8042 /* If the insn that set the register to 0 was deleted, this
8043 note cannot be relied on any longer. The destination might
8044 even have been moved to memory.
8045 This was observed for SH4 with execute/920501-6.c compilation,
8046 -O2 -fomit-frame-pointer -finline-functions . */
8047 if (GET_CODE (XEXP (note, 0)) == NOTE
8048 || INSN_DELETED_P (XEXP (note, 0)))
8050 /* This note applies to the dest of the original insn. Find the
8051 first new insn that now has the same dest, and move the note
8057 for (insn = first;; insn = NEXT_INSN (insn))
8059 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8060 && (temp = single_set (insn))
8061 && rtx_equal_p (SET_DEST (temp), orig_dest))
8063 XEXP (note, 1) = REG_NOTES (insn);
8064 REG_NOTES (insn) = note;
8065 /* The reg is only zero before one insn, the first that
8069 /* If this note refers to a multiple word hard
8070 register, it may have been split into several smaller
8071 hard register references. We could split the notes,
8072 but simply dropping them is good enough. */
8073 if (GET_CODE (orig_dest) == REG
8074 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
8075 && HARD_REGNO_NREGS (REGNO (orig_dest),
8076 GET_MODE (orig_dest)) > 1)
8078 /* It must be set somewhere, fail if we couldn't find where it
8087 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
8088 set is meaningless. Just drop the note. */
8092 case REG_NO_CONFLICT:
8093 /* These notes apply to the dest of the original insn. Find the last
8094 new insn that now has the same dest, and move the note there. */
8099 for (insn = last;; insn = PREV_INSN (insn))
8101 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8102 && (temp = single_set (insn))
8103 && rtx_equal_p (SET_DEST (temp), orig_dest))
8105 XEXP (note, 1) = REG_NOTES (insn);
8106 REG_NOTES (insn) = note;
8107 /* Only put this note on one of the new insns. */
8111 /* The original dest must still be set someplace. Abort if we
8112 couldn't find it. */
8115 /* However, if this note refers to a multiple word hard
8116 register, it may have been split into several smaller
8117 hard register references. We could split the notes,
8118 but simply dropping them is good enough. */
8119 if (GET_CODE (orig_dest) == REG
8120 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
8121 && HARD_REGNO_NREGS (REGNO (orig_dest),
8122 GET_MODE (orig_dest)) > 1)
8124 /* Likewise for multi-word memory references. */
8125 if (GET_CODE (orig_dest) == MEM
8126 && SIZE_FOR_MODE (orig_dest) > UNITS_PER_WORD)
8134 /* Move a REG_LIBCALL note to the first insn created, and update
8135 the corresponding REG_RETVAL note. */
8136 XEXP (note, 1) = REG_NOTES (first);
8137 REG_NOTES (first) = note;
8139 insn = XEXP (note, 0);
8140 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
8142 XEXP (note, 0) = first;
8145 case REG_EXEC_COUNT:
8146 /* Move a REG_EXEC_COUNT note to the first insn created. */
8147 XEXP (note, 1) = REG_NOTES (first);
8148 REG_NOTES (first) = note;
8152 /* Move a REG_RETVAL note to the last insn created, and update
8153 the corresponding REG_LIBCALL note. */
8154 XEXP (note, 1) = REG_NOTES (last);
8155 REG_NOTES (last) = note;
8157 insn = XEXP (note, 0);
8158 note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
8160 XEXP (note, 0) = last;
8165 /* This should be moved to whichever instruction is a JUMP_INSN. */
8167 for (insn = last;; insn = PREV_INSN (insn))
8169 if (GET_CODE (insn) == JUMP_INSN)
8171 XEXP (note, 1) = REG_NOTES (insn);
8172 REG_NOTES (insn) = note;
8173 /* Only put this note on one of the new insns. */
8176 /* Fail if we couldn't find a JUMP_INSN. */
8183 /* reload sometimes leaves obsolete REG_INC notes around. */
8184 if (reload_completed)
8186 /* This should be moved to whichever instruction now has the
8187 increment operation. */
8191 /* Should be moved to the new insn(s) which use the label. */
8192 for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
8193 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8194 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
8196 REG_NOTES (insn) = alloc_EXPR_LIST (REG_LABEL,
8204 /* These two notes will never appear until after reorg, so we don't
8205 have to handle them here. */
8211 /* Each new insn created, except the last, has a new set. If the destination
8212 is a register, then this reg is now live across several insns, whereas
8213 previously the dest reg was born and died within the same insn. To
8214 reflect this, we now need a REG_DEAD note on the insn where this
8217 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
8219 for (insn = first; insn != last; insn = NEXT_INSN (insn))
8224 pat = PATTERN (insn);
8225 if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
8226 new_insn_dead_notes (pat, insn, last, orig_insn);
8227 else if (GET_CODE (pat) == PARALLEL)
8229 for (i = 0; i < XVECLEN (pat, 0); i++)
8230 if (GET_CODE (XVECEXP (pat, 0, i)) == SET
8231 || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
8232 new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
8236 /* If any insn, except the last, uses the register set by the last insn,
8237 then we need a new REG_DEAD note on that insn. In this case, there
8238 would not have been a REG_DEAD note for this register in the original
8239 insn because it was used and set within one insn. */
8241 set = single_set (last);
8244 rtx dest = SET_DEST (set);
8246 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
8247 || GET_CODE (dest) == STRICT_LOW_PART
8248 || GET_CODE (dest) == SIGN_EXTRACT)
8249 dest = XEXP (dest, 0);
8251 if (GET_CODE (dest) == REG
8252 /* Global registers are always live, so the code below does not
8254 && (REGNO (dest) >= FIRST_PSEUDO_REGISTER
8255 || ! global_regs[REGNO (dest)]))
8257 rtx stop_insn = PREV_INSN (first);
8259 /* If the last insn uses the register that it is setting, then
8260 we don't want to put a REG_DEAD note there. Search backwards
8261 to find the first insn that sets but does not use DEST. */
8264 if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
8266 for (insn = PREV_INSN (insn); insn != first;
8267 insn = PREV_INSN (insn))
8269 if ((set = single_set (insn))
8270 && reg_mentioned_p (dest, SET_DEST (set))
8271 && ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
8276 /* Now find the first insn that uses but does not set DEST. */
8278 for (insn = PREV_INSN (insn); insn != stop_insn;
8279 insn = PREV_INSN (insn))
8281 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8282 && reg_mentioned_p (dest, PATTERN (insn))
8283 && (set = single_set (insn)))
8285 rtx insn_dest = SET_DEST (set);
8287 while (GET_CODE (insn_dest) == ZERO_EXTRACT
8288 || GET_CODE (insn_dest) == SUBREG
8289 || GET_CODE (insn_dest) == STRICT_LOW_PART
8290 || GET_CODE (insn_dest) == SIGN_EXTRACT)
8291 insn_dest = XEXP (insn_dest, 0);
8293 if (insn_dest != dest)
8295 note = alloc_EXPR_LIST (REG_DEAD, dest, REG_NOTES (insn));
8296 REG_NOTES (insn) = note;
8297 /* The reg only dies in one insn, the last one
8306 /* If the original dest is modifying a multiple register target, and the
8307 original instruction was split such that the original dest is now set
8308 by two or more SUBREG sets, then the split insns no longer kill the
8309 destination of the original insn.
8311 In this case, if there exists an instruction in the same basic block,
8312 before the split insn, which uses the original dest, and this use is
8313 killed by the original insn, then we must remove the REG_DEAD note on
8314 this insn, because it is now superfluous.
8316 This does not apply when a hard register gets split, because the code
8317 knows how to handle overlapping hard registers properly. */
8318 if (orig_dest && GET_CODE (orig_dest) == REG)
8320 int found_orig_dest = 0;
8321 int found_split_dest = 0;
8323 for (insn = first;; insn = NEXT_INSN (insn))
8328 /* I'm not sure if this can happen, but let's be safe. */
8329 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
8332 pat = PATTERN (insn);
8333 i = GET_CODE (pat) == PARALLEL ? XVECLEN (pat, 0) : 0;
8338 if (GET_CODE (set) == SET)
8340 if (GET_CODE (SET_DEST (set)) == REG
8341 && REGNO (SET_DEST (set)) == REGNO (orig_dest))
8343 found_orig_dest = 1;
8346 else if (GET_CODE (SET_DEST (set)) == SUBREG
8347 && SUBREG_REG (SET_DEST (set)) == orig_dest)
8349 found_split_dest = 1;
8355 set = XVECEXP (pat, 0, i);
8362 if (found_split_dest)
8364 /* Search backwards from FIRST, looking for the first insn that uses
8365 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
8366 If we find an insn, and it has a REG_DEAD note, then delete the
8369 for (insn = first; insn; insn = PREV_INSN (insn))
8371 if (GET_CODE (insn) == CODE_LABEL
8372 || GET_CODE (insn) == JUMP_INSN)
8374 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8375 && reg_mentioned_p (orig_dest, insn))
8377 note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
8379 remove_note (insn, note);
8383 else if (!found_orig_dest)
8387 /* Should never reach here for a pseudo reg. */
8388 if (REGNO (orig_dest) >= FIRST_PSEUDO_REGISTER)
8391 /* This can happen for a hard register, if the splitter
8392 does not bother to emit instructions which would be no-ops.
8393 We try to verify that this is the case by checking to see if
8394 the original instruction uses all of the registers that it
8395 set. This case is OK, because deleting a no-op can not affect
8396 REG_DEAD notes on other insns. If this is not the case, then
8399 regno = REGNO (orig_dest);
8400 for (i = HARD_REGNO_NREGS (regno, GET_MODE (orig_dest)) - 1;
8402 if (! refers_to_regno_p (regno + i, regno + i + 1, orig_insn,
8410 /* Update reg_n_sets. This is necessary to prevent local alloc from
8411 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
8412 a reg from set once to set multiple times. */
8415 rtx x = PATTERN (orig_insn);
8416 RTX_CODE code = GET_CODE (x);
8418 if (code == SET || code == CLOBBER)
8419 update_n_sets (x, -1);
8420 else if (code == PARALLEL)
8423 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8425 code = GET_CODE (XVECEXP (x, 0, i));
8426 if (code == SET || code == CLOBBER)
8427 update_n_sets (XVECEXP (x, 0, i), -1);
8431 for (insn = first;; insn = NEXT_INSN (insn))
8434 code = GET_CODE (x);
8436 if (code == SET || code == CLOBBER)
8437 update_n_sets (x, 1);
8438 else if (code == PARALLEL)
8441 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8443 code = GET_CODE (XVECEXP (x, 0, i));
8444 if (code == SET || code == CLOBBER)
8445 update_n_sets (XVECEXP (x, 0, i), 1);
8455 /* The one entry point in this file. DUMP_FILE is the dump file for
8459 schedule_insns (dump_file)
8470 /* disable speculative loads in their presence if cc0 defined */
8472 flag_schedule_speculative_load = 0;
8475 /* Taking care of this degenerate case makes the rest of
8476 this code simpler. */
8477 if (n_basic_blocks == 0)
8480 /* set dump and sched_verbose for the desired debugging output. If no
8481 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
8482 For -fsched-verbose-N, N>=10, print everything to stderr. */
8483 sched_verbose = sched_verbose_param;
8484 if (sched_verbose_param == 0 && dump_file)
8486 dump = ((sched_verbose_param >= 10 || !dump_file) ? stderr : dump_file);
8491 /* Initialize the unused_*_lists. We can't use the ones left over from
8492 the previous function, because gcc has freed that memory. We can use
8493 the ones left over from the first sched pass in the second pass however,
8494 so only clear them on the first sched pass. The first pass is before
8495 reload if flag_schedule_insns is set, otherwise it is afterwards. */
8497 if (reload_completed == 0 || !flag_schedule_insns)
8499 unused_insn_list = 0;
8500 unused_expr_list = 0;
8503 /* initialize issue_rate */
8504 issue_rate = ISSUE_RATE;
8506 /* do the splitting first for all blocks */
8507 for (b = 0; b < n_basic_blocks; b++)
8508 split_block_insns (b, 1);
8510 max_uid = (get_max_uid () + 1);
8512 cant_move = (char *) xmalloc (max_uid * sizeof (char));
8513 bzero ((char *) cant_move, max_uid * sizeof (char));
8515 fed_by_spec_load = (char *) xmalloc (max_uid * sizeof (char));
8516 bzero ((char *) fed_by_spec_load, max_uid * sizeof (char));
8518 is_load_insn = (char *) xmalloc (max_uid * sizeof (char));
8519 bzero ((char *) is_load_insn, max_uid * sizeof (char));
8521 insn_orig_block = (int *) xmalloc (max_uid * sizeof (int));
8522 insn_luid = (int *) xmalloc (max_uid * sizeof (int));
8525 for (b = 0; b < n_basic_blocks; b++)
8526 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
8528 INSN_BLOCK (insn) = b;
8529 INSN_LUID (insn) = luid++;
8531 if (insn == BLOCK_END (b))
8535 /* after reload, remove inter-blocks dependences computed before reload. */
8536 if (reload_completed)
8541 for (b = 0; b < n_basic_blocks; b++)
8542 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
8546 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
8549 link = LOG_LINKS (insn);
8552 rtx x = XEXP (link, 0);
8554 if (INSN_BLOCK (x) != b)
8556 remove_dependence (insn, x);
8557 link = prev ? XEXP (prev, 1) : LOG_LINKS (insn);
8560 prev = link, link = XEXP (prev, 1);
8564 if (insn == BLOCK_END (b))
8570 rgn_table = (region *) alloca ((n_basic_blocks) * sizeof (region));
8571 rgn_bb_table = (int *) alloca ((n_basic_blocks) * sizeof (int));
8572 block_to_bb = (int *) alloca ((n_basic_blocks) * sizeof (int));
8573 containing_rgn = (int *) alloca ((n_basic_blocks) * sizeof (int));
8575 /* compute regions for scheduling */
8576 if (reload_completed
8577 || n_basic_blocks == 1
8578 || !flag_schedule_interblock)
8580 find_single_block_region ();
8584 /* verify that a 'good' control flow graph can be built */
8585 if (is_cfg_nonregular ())
8587 find_single_block_region ();
8591 int_list_ptr *s_preds, *s_succs;
8592 int *num_preds, *num_succs;
8593 sbitmap *dom, *pdom;
8595 s_preds = (int_list_ptr *) alloca (n_basic_blocks
8596 * sizeof (int_list_ptr));
8597 s_succs = (int_list_ptr *) alloca (n_basic_blocks
8598 * sizeof (int_list_ptr));
8599 num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
8600 num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
8601 dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
8602 pdom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
8604 /* The scheduler runs after flow; therefore, we can't blindly call
8605 back into find_basic_blocks since doing so could invalidate the
8606 info in global_live_at_start.
8608 Consider a block consisting entirely of dead stores; after life
8609 analysis it would be a block of NOTE_INSN_DELETED notes. If
8610 we call find_basic_blocks again, then the block would be removed
8611 entirely and invalidate our the register live information.
8613 We could (should?) recompute register live information. Doing
8614 so may even be beneficial. */
8616 compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
8618 /* Compute the dominators and post dominators. We don't currently use
8619 post dominators, but we should for speculative motion analysis. */
8620 compute_dominators (dom, pdom, s_preds, s_succs);
8622 /* build_control_flow will return nonzero if it detects unreachable
8623 blocks or any other irregularity with the cfg which prevents
8624 cross block scheduling. */
8625 if (build_control_flow (s_preds, s_succs, num_preds, num_succs) != 0)
8626 find_single_block_region ();
8628 find_rgns (s_preds, s_succs, num_preds, num_succs, dom);
8630 if (sched_verbose >= 3)
8633 /* For now. This will move as more and more of haifa is converted
8634 to using the cfg code in flow.c */
8641 /* Allocate data for this pass. See comments, above,
8642 for what these vectors do.
8644 We use xmalloc instead of alloca, because max_uid can be very large
8645 when there is a lot of function inlining. If we used alloca, we could
8646 exceed stack limits on some hosts for some inputs. */
8647 insn_priority = (int *) xmalloc (max_uid * sizeof (int));
8648 insn_reg_weight = (int *) xmalloc (max_uid * sizeof (int));
8649 insn_tick = (int *) xmalloc (max_uid * sizeof (int));
8650 insn_costs = (short *) xmalloc (max_uid * sizeof (short));
8651 insn_units = (short *) xmalloc (max_uid * sizeof (short));
8652 insn_blockage = (unsigned int *) xmalloc (max_uid * sizeof (unsigned int));
8653 insn_ref_count = (int *) xmalloc (max_uid * sizeof (int));
8655 /* Allocate for forward dependencies */
8656 insn_dep_count = (int *) xmalloc (max_uid * sizeof (int));
8657 insn_depend = (rtx *) xmalloc (max_uid * sizeof (rtx));
8659 if (reload_completed == 0)
8663 sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
8664 sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
8665 sched_reg_basic_block = (int *) alloca (max_regno * sizeof (int));
8666 bb_live_regs = ALLOCA_REG_SET ();
8667 bzero ((char *) sched_reg_n_calls_crossed, max_regno * sizeof (int));
8668 bzero ((char *) sched_reg_live_length, max_regno * sizeof (int));
8670 for (i = 0; i < max_regno; i++)
8671 sched_reg_basic_block[i] = REG_BLOCK_UNKNOWN;
8675 sched_reg_n_calls_crossed = 0;
8676 sched_reg_live_length = 0;
8679 init_alias_analysis ();
8681 if (write_symbols != NO_DEBUG)
8685 line_note = (rtx *) xmalloc (max_uid * sizeof (rtx));
8686 bzero ((char *) line_note, max_uid * sizeof (rtx));
8687 line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
8688 bzero ((char *) line_note_head, n_basic_blocks * sizeof (rtx));
8690 /* Save-line-note-head:
8691 Determine the line-number at the start of each basic block.
8692 This must be computed and saved now, because after a basic block's
8693 predecessor has been scheduled, it is impossible to accurately
8694 determine the correct line number for the first insn of the block. */
8696 for (b = 0; b < n_basic_blocks; b++)
8697 for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line))
8698 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
8700 line_note_head[b] = line;
8705 bzero ((char *) insn_priority, max_uid * sizeof (int));
8706 bzero ((char *) insn_reg_weight, max_uid * sizeof (int));
8707 bzero ((char *) insn_tick, max_uid * sizeof (int));
8708 bzero ((char *) insn_costs, max_uid * sizeof (short));
8709 bzero ((char *) insn_units, max_uid * sizeof (short));
8710 bzero ((char *) insn_blockage, max_uid * sizeof (unsigned int));
8711 bzero ((char *) insn_ref_count, max_uid * sizeof (int));
8713 /* Initialize for forward dependencies */
8714 bzero ((char *) insn_depend, max_uid * sizeof (rtx));
8715 bzero ((char *) insn_dep_count, max_uid * sizeof (int));
8717 /* Find units used in this fuction, for visualization */
8719 init_target_units ();
8721 /* ??? Add a NOTE after the last insn of the last basic block. It is not
8722 known why this is done. */
8724 insn = BLOCK_END (n_basic_blocks - 1);
8725 if (NEXT_INSN (insn) == 0
8726 || (GET_CODE (insn) != NOTE
8727 && GET_CODE (insn) != CODE_LABEL
8728 /* Don't emit a NOTE if it would end up between an unconditional
8729 jump and a BARRIER. */
8730 && !(GET_CODE (insn) == JUMP_INSN
8731 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
8732 emit_note_after (NOTE_INSN_DELETED, BLOCK_END (n_basic_blocks - 1));
8734 /* Schedule every region in the subroutine */
8735 for (rgn = 0; rgn < nr_regions; rgn++)
8737 schedule_region (rgn);
8744 /* Reposition the prologue and epilogue notes in case we moved the
8745 prologue/epilogue insns. */
8746 if (reload_completed)
8747 reposition_prologue_and_epilogue_notes (get_insns ());
8749 /* delete redundant line notes. */
8750 if (write_symbols != NO_DEBUG)
8751 rm_redundant_line_notes ();
8753 /* Update information about uses of registers in the subroutine. */
8754 if (reload_completed == 0)
8755 update_reg_usage ();
8759 if (reload_completed == 0 && flag_schedule_interblock)
8761 fprintf (dump, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8769 fprintf (dump, "\n\n");
8773 free (fed_by_spec_load);
8774 free (is_load_insn);
8775 free (insn_orig_block);
8778 free (insn_priority);
8779 free (insn_reg_weight);
8783 free (insn_blockage);
8784 free (insn_ref_count);
8786 free (insn_dep_count);
8789 if (write_symbols != NO_DEBUG)
8793 FREE_REG_SET (bb_live_regs);
8812 #endif /* INSN_SCHEDULING */