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. */
161 #include "basic-block.h"
163 #include "hard-reg-set.h"
165 #include "insn-config.h"
166 #include "insn-attr.h"
171 extern char *reg_known_equiv_p;
172 extern rtx *reg_known_value;
174 #ifdef INSN_SCHEDULING
176 /* target_units bitmask has 1 for each unit in the cpu. It should be
177 possible to compute this variable from the machine description.
178 But currently it is computed by examinning the insn list. Since
179 this is only needed for visualization, it seems an acceptable
180 solution. (For understanding the mapping of bits to units, see
181 definition of function_units[] in "insn-attrtab.c") */
183 static int target_units = 0;
185 /* issue_rate is the number of insns that can be scheduled in the same
186 machine cycle. It can be defined in the config/mach/mach.h file,
187 otherwise we set it to 1. */
189 static int issue_rate;
195 /* sched-verbose controls the amount of debugging output the
196 scheduler prints. It is controlled by -fsched-verbose-N:
197 N>0 and no -DSR : the output is directed to stderr.
198 N>=10 will direct the printouts to stderr (regardless of -dSR).
200 N=2: bb's probabilities, detailed ready list info, unit/insn info.
201 N=3: rtl at abort point, control-flow, regions info.
202 N=5: dependences info. */
204 #define MAX_RGN_BLOCKS 10
205 #define MAX_RGN_INSNS 100
207 static int sched_verbose_param = 0;
208 static int sched_verbose = 0;
210 /* nr_inter/spec counts interblock/speculative motion for the function */
211 static int nr_inter, nr_spec;
214 /* debugging file. all printouts are sent to dump, which is always set,
215 either to stderr, or to the dump listing file (-dRS). */
216 static FILE *dump = 0;
218 /* fix_sched_param() is called from toplev.c upon detection
219 of the -fsched-***-N options. */
222 fix_sched_param (param, val)
225 if (!strcmp (param, "verbose"))
226 sched_verbose_param = atoi (val);
228 warning ("fix_sched_param: unknown param: %s", param);
232 /* Arrays set up by scheduling for the same respective purposes as
233 similar-named arrays set up by flow analysis. We work with these
234 arrays during the scheduling pass so we can compare values against
237 Values of these arrays are copied at the end of this pass into the
238 arrays set up by flow analysis. */
239 static int *sched_reg_n_calls_crossed;
240 static int *sched_reg_live_length;
241 static int *sched_reg_basic_block;
243 /* We need to know the current block number during the post scheduling
244 update of live register information so that we can also update
245 REG_BASIC_BLOCK if a register changes blocks. */
246 static int current_block_num;
248 /* Element N is the next insn that sets (hard or pseudo) register
249 N within the current basic block; or zero, if there is no
250 such insn. Needed for new registers which may be introduced
251 by splitting insns. */
252 static rtx *reg_last_uses;
253 static rtx *reg_last_sets;
254 static rtx *reg_last_clobbers;
255 static regset reg_pending_sets;
256 static regset reg_pending_clobbers;
257 static int reg_pending_sets_all;
259 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
260 static int *insn_luid;
261 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
263 /* Vector indexed by INSN_UID giving each instruction a priority. */
264 static int *insn_priority;
265 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
267 static short *insn_costs;
268 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
270 /* Vector indexed by INSN_UID giving an encoding of the function units
272 static short *insn_units;
273 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
275 /* Vector indexed by INSN_UID giving each instruction a register-weight.
276 This weight is an estimation of the insn contribution to registers pressure. */
277 static int *insn_reg_weight;
278 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
280 /* Vector indexed by INSN_UID giving list of insns which
281 depend upon INSN. Unlike LOG_LINKS, it represents forward dependences. */
282 static rtx *insn_depend;
283 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
285 /* Vector indexed by INSN_UID. Initialized to the number of incoming
286 edges in forward dependence graph (= number of LOG_LINKS). As
287 scheduling procedes, dependence counts are decreased. An
288 instruction moves to the ready list when its counter is zero. */
289 static int *insn_dep_count;
290 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
292 /* Vector indexed by INSN_UID giving an encoding of the blockage range
293 function. The unit and the range are encoded. */
294 static unsigned int *insn_blockage;
295 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
297 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
298 #define ENCODE_BLOCKAGE(U, R) \
299 (((U) << BLOCKAGE_BITS \
300 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
301 | MAX_BLOCKAGE_COST (R))
302 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
303 #define BLOCKAGE_RANGE(B) \
304 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
305 | ((B) & BLOCKAGE_MASK))
307 /* Encodings of the `<name>_unit_blockage_range' function. */
308 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
309 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
311 #define DONE_PRIORITY -1
312 #define MAX_PRIORITY 0x7fffffff
313 #define TAIL_PRIORITY 0x7ffffffe
314 #define LAUNCH_PRIORITY 0x7f000001
315 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
316 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
318 /* Vector indexed by INSN_UID giving number of insns referring to this insn. */
319 static int *insn_ref_count;
320 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
322 /* Vector indexed by INSN_UID giving line-number note in effect for each
323 insn. For line-number notes, this indicates whether the note may be
325 static rtx *line_note;
326 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
328 /* Vector indexed by basic block number giving the starting line-number
329 for each basic block. */
330 static rtx *line_note_head;
332 /* List of important notes we must keep around. This is a pointer to the
333 last element in the list. */
334 static rtx note_list;
336 /* Regsets telling whether a given register is live or dead before the last
337 scheduled insn. Must scan the instructions once before scheduling to
338 determine what registers are live or dead at the end of the block. */
339 static regset bb_live_regs;
341 /* Regset telling whether a given register is live after the insn currently
342 being scheduled. Before processing an insn, this is equal to bb_live_regs
343 above. This is used so that we can find registers that are newly born/dead
344 after processing an insn. */
345 static regset old_live_regs;
347 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
348 during the initial scan and reused later. If there are not exactly as
349 many REG_DEAD notes in the post scheduled code as there were in the
350 prescheduled code then we trigger an abort because this indicates a bug. */
351 static rtx dead_notes;
355 /* An instruction is ready to be scheduled when all insns preceding it
356 have already been scheduled. It is important to ensure that all
357 insns which use its result will not be executed until its result
358 has been computed. An insn is maintained in one of four structures:
360 (P) the "Pending" set of insns which cannot be scheduled until
361 their dependencies have been satisfied.
362 (Q) the "Queued" set of insns that can be scheduled when sufficient
364 (R) the "Ready" list of unscheduled, uncommitted insns.
365 (S) the "Scheduled" list of insns.
367 Initially, all insns are either "Pending" or "Ready" depending on
368 whether their dependencies are satisfied.
370 Insns move from the "Ready" list to the "Scheduled" list as they
371 are committed to the schedule. As this occurs, the insns in the
372 "Pending" list have their dependencies satisfied and move to either
373 the "Ready" list or the "Queued" set depending on whether
374 sufficient time has passed to make them ready. As time passes,
375 insns move from the "Queued" set to the "Ready" list. Insns may
376 move from the "Ready" list to the "Queued" set if they are blocked
377 due to a function unit conflict.
379 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
380 insns, i.e., those that are ready, queued, and pending.
381 The "Queued" set (Q) is implemented by the variable `insn_queue'.
382 The "Ready" list (R) is implemented by the variables `ready' and
384 The "Scheduled" list (S) is the new insn chain built by this pass.
386 The transition (R->S) is implemented in the scheduling loop in
387 `schedule_block' when the best insn to schedule is chosen.
388 The transition (R->Q) is implemented in `queue_insn' when an
389 insn is found to have a function unit conflict with the already
391 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
392 insns move from the ready list to the scheduled list.
393 The transition (Q->R) is implemented in 'queue_to_insn' as time
394 passes or stalls are introduced. */
396 /* Implement a circular buffer to delay instructions until sufficient
397 time has passed. INSN_QUEUE_SIZE is a power of two larger than
398 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
399 longest time an isnsn may be queued. */
400 static rtx insn_queue[INSN_QUEUE_SIZE];
401 static int q_ptr = 0;
402 static int q_size = 0;
403 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
404 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
406 /* Vector indexed by INSN_UID giving the minimum clock tick at which
407 the insn becomes ready. This is used to note timing constraints for
408 insns in the pending list. */
409 static int *insn_tick;
410 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
412 /* Data structure for keeping track of register information
413 during that register's life. */
422 /* Forward declarations. */
423 static void add_dependence PROTO ((rtx, rtx, enum reg_note));
424 static void remove_dependence PROTO ((rtx, rtx));
425 static rtx find_insn_list PROTO ((rtx, rtx));
426 static int insn_unit PROTO ((rtx));
427 static unsigned int blockage_range PROTO ((int, rtx));
428 static void clear_units PROTO ((void));
429 static int actual_hazard_this_instance PROTO ((int, int, rtx, int, int));
430 static void schedule_unit PROTO ((int, rtx, int));
431 static int actual_hazard PROTO ((int, rtx, int, int));
432 static int potential_hazard PROTO ((int, rtx, int));
433 static int insn_cost PROTO ((rtx, rtx, rtx));
434 static int priority PROTO ((rtx));
435 static void free_pending_lists PROTO ((void));
436 static void add_insn_mem_dependence PROTO ((rtx *, rtx *, rtx, rtx));
437 static void flush_pending_lists PROTO ((rtx, int));
438 static void sched_analyze_1 PROTO ((rtx, rtx));
439 static void sched_analyze_2 PROTO ((rtx, rtx));
440 static void sched_analyze_insn PROTO ((rtx, rtx, rtx));
441 static void sched_analyze PROTO ((rtx, rtx));
442 static void sched_note_set PROTO ((rtx, int));
443 static int rank_for_schedule PROTO ((const GENERIC_PTR, const GENERIC_PTR));
444 static void swap_sort PROTO ((rtx *, int));
445 static void queue_insn PROTO ((rtx, int));
446 static int schedule_insn PROTO ((rtx, rtx *, int, int));
447 static void create_reg_dead_note PROTO ((rtx, rtx));
448 static void attach_deaths PROTO ((rtx, rtx, int));
449 static void attach_deaths_insn PROTO ((rtx));
450 static int new_sometimes_live PROTO ((struct sometimes *, int, int));
451 static void finish_sometimes_live PROTO ((struct sometimes *, int));
452 static int schedule_block PROTO ((int, int));
453 static void split_hard_reg_notes PROTO ((rtx, rtx, rtx));
454 static void new_insn_dead_notes PROTO ((rtx, rtx, rtx, rtx));
455 static void update_n_sets PROTO ((rtx, int));
456 static char *safe_concat PROTO ((char *, char *, char *));
457 static int insn_issue_delay PROTO ((rtx));
458 static int birthing_insn_p PROTO ((rtx));
459 static void adjust_priority PROTO ((rtx));
461 /* Mapping of insns to their original block prior to scheduling. */
462 static int *insn_orig_block;
463 #define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
465 /* Some insns (e.g. call) are not allowed to move across blocks. */
466 static char *cant_move;
467 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
469 /* Control flow graph edges are kept in circular lists. */
478 static haifa_edge *edge_table;
480 #define NEXT_IN(edge) (edge_table[edge].next_in)
481 #define NEXT_OUT(edge) (edge_table[edge].next_out)
482 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
483 #define TO_BLOCK(edge) (edge_table[edge].to_block)
485 /* Number of edges in the control flow graph. (in fact larger than
486 that by 1, since edge 0 is unused.) */
489 /* Circular list of incoming/outgoing edges of a block */
490 static int *in_edges;
491 static int *out_edges;
493 #define IN_EDGES(block) (in_edges[block])
494 #define OUT_EDGES(block) (out_edges[block])
496 /* List of labels which cannot be deleted, needed for control
497 flow graph construction. */
498 extern rtx forced_labels;
501 static int is_cfg_nonregular PROTO ((void));
502 static int build_control_flow PROTO ((int_list_ptr *, int_list_ptr *,
504 static void new_edge PROTO ((int, int));
507 /* A region is the main entity for interblock scheduling: insns
508 are allowed to move between blocks in the same region, along
509 control flow graph edges, in the 'up' direction. */
512 int rgn_nr_blocks; /* number of blocks in region */
513 int rgn_blocks; /* blocks in the region (actually index in rgn_bb_table) */
517 /* Number of regions in the procedure */
518 static int nr_regions;
520 /* Table of region descriptions */
521 static region *rgn_table;
523 /* Array of lists of regions' blocks */
524 static int *rgn_bb_table;
526 /* Topological order of blocks in the region (if b2 is reachable from
527 b1, block_to_bb[b2] > block_to_bb[b1]).
528 Note: A basic block is always referred to by either block or b,
529 while its topological order name (in the region) is refered to by
532 static int *block_to_bb;
534 /* The number of the region containing a block. */
535 static int *containing_rgn;
537 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
538 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
539 #define BLOCK_TO_BB(block) (block_to_bb[block])
540 #define CONTAINING_RGN(block) (containing_rgn[block])
542 void debug_regions PROTO ((void));
543 static void find_single_block_region PROTO ((void));
544 static void find_rgns PROTO ((int_list_ptr *, int_list_ptr *,
545 int *, int *, sbitmap *));
546 static int too_large PROTO ((int, int *, int *));
548 extern void debug_live PROTO ((int, int));
550 /* Blocks of the current region being scheduled. */
551 static int current_nr_blocks;
552 static int current_blocks;
554 /* The mapping from bb to block */
555 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
558 /* Bit vectors and bitset operations are needed for computations on
559 the control flow graph. */
561 typedef unsigned HOST_WIDE_INT *bitset;
564 int *first_member; /* pointer to the list start in bitlst_table. */
565 int nr_members; /* the number of members of the bit list. */
569 static int bitlst_table_last;
570 static int bitlst_table_size;
571 static int *bitlst_table;
573 static char bitset_member PROTO ((bitset, int, int));
574 static void extract_bitlst PROTO ((bitset, int, bitlst *));
576 /* target info declarations.
578 The block currently being scheduled is referred to as the "target" block,
579 while other blocks in the region from which insns can be moved to the
580 target are called "source" blocks. The candidate structure holds info
581 about such sources: are they valid? Speculative? Etc. */
582 typedef bitlst bblst;
593 static candidate *candidate_table;
595 /* A speculative motion requires checking live information on the path
596 from 'source' to 'target'. The split blocks are those to be checked.
597 After a speculative motion, live information should be modified in
600 Lists of split and update blocks for each candidate of the current
601 target are in array bblst_table */
602 static int *bblst_table, bblst_size, bblst_last;
604 #define IS_VALID(src) ( candidate_table[src].is_valid )
605 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
606 #define SRC_PROB(src) ( candidate_table[src].src_prob )
608 /* The bb being currently scheduled. */
609 static int target_bb;
612 typedef bitlst edgelst;
614 /* target info functions */
615 static void split_edges PROTO ((int, int, edgelst *));
616 static void compute_trg_info PROTO ((int));
617 void debug_candidate PROTO ((int));
618 void debug_candidates PROTO ((int));
621 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
622 typedef bitset bbset;
624 /* Number of words of the bbset. */
625 static int bbset_size;
627 /* Dominators array: dom[i] contains the bbset of dominators of
628 bb i in the region. */
631 /* bb 0 is the only region entry */
632 #define IS_RGN_ENTRY(bb) (!bb)
634 /* Is bb_src dominated by bb_trg. */
635 #define IS_DOMINATED(bb_src, bb_trg) \
636 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
638 /* Probability: Prob[i] is a float in [0, 1] which is the probability
639 of bb i relative to the region entry. */
642 /* The probability of bb_src, relative to bb_trg. Note, that while the
643 'prob[bb]' is a float in [0, 1], this macro returns an integer
645 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
648 /* Bit-set of edges, where bit i stands for edge i. */
649 typedef bitset edgeset;
651 /* Number of edges in the region. */
652 static int rgn_nr_edges;
654 /* Array of size rgn_nr_edges. */
655 static int *rgn_edges;
657 /* Number of words in an edgeset. */
658 static int edgeset_size;
660 /* Mapping from each edge in the graph to its number in the rgn. */
661 static int *edge_to_bit;
662 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
664 /* The split edges of a source bb is different for each target
665 bb. In order to compute this efficiently, the 'potential-split edges'
666 are computed for each bb prior to scheduling a region. This is actually
667 the split edges of each bb relative to the region entry.
669 pot_split[bb] is the set of potential split edges of bb. */
670 static edgeset *pot_split;
672 /* For every bb, a set of its ancestor edges. */
673 static edgeset *ancestor_edges;
675 static void compute_dom_prob_ps PROTO ((int));
677 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
678 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
679 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
680 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
682 /* parameters affecting the decision of rank_for_schedule() */
683 #define MIN_DIFF_PRIORITY 2
684 #define MIN_PROBABILITY 40
685 #define MIN_PROB_DIFF 10
687 /* speculative scheduling functions */
688 static int check_live_1 PROTO ((int, rtx));
689 static void update_live_1 PROTO ((int, rtx));
690 static int check_live PROTO ((rtx, int));
691 static void update_live PROTO ((rtx, int));
692 static void set_spec_fed PROTO ((rtx));
693 static int is_pfree PROTO ((rtx, int, int));
694 static int find_conditional_protection PROTO ((rtx, int));
695 static int is_conditionally_protected PROTO ((rtx, int, int));
696 static int may_trap_exp PROTO ((rtx, int));
697 static int haifa_classify_insn PROTO ((rtx));
698 static int is_prisky PROTO ((rtx, int, int));
699 static int is_exception_free PROTO ((rtx, int, int));
701 static char find_insn_mem_list PROTO ((rtx, rtx, rtx, rtx));
702 static void compute_block_forward_dependences PROTO ((int));
703 static void init_rgn_data_dependences PROTO ((int));
704 static void add_branch_dependences PROTO ((rtx, rtx));
705 static void compute_block_backward_dependences PROTO ((int));
706 void debug_dependencies PROTO ((void));
708 /* Notes handling mechanism:
709 =========================
710 Generally, NOTES are saved before scheduling and restored after scheduling.
711 The scheduler distinguishes between three types of notes:
713 (1) LINE_NUMBER notes, generated and used for debugging. Here,
714 before scheduling a region, a pointer to the LINE_NUMBER note is
715 added to the insn following it (in save_line_notes()), and the note
716 is removed (in rm_line_notes() and unlink_line_notes()). After
717 scheduling the region, this pointer is used for regeneration of
718 the LINE_NUMBER note (in restore_line_notes()).
720 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
721 Before scheduling a region, a pointer to the note is added to the insn
722 that follows or precedes it. (This happens as part of the data dependence
723 computation). After scheduling an insn, the pointer contained in it is
724 used for regenerating the corresponding note (in reemit_notes).
726 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
727 these notes are put in a list (in rm_other_notes() and
728 unlink_other_notes ()). After scheduling the block, these notes are
729 inserted at the beginning of the block (in schedule_block()). */
731 static rtx unlink_other_notes PROTO ((rtx, rtx));
732 static rtx unlink_line_notes PROTO ((rtx, rtx));
733 static void rm_line_notes PROTO ((int));
734 static void save_line_notes PROTO ((int));
735 static void restore_line_notes PROTO ((int));
736 static void rm_redundant_line_notes PROTO ((void));
737 static void rm_other_notes PROTO ((rtx, rtx));
738 static rtx reemit_notes PROTO ((rtx, rtx));
740 static void get_block_head_tail PROTO ((int, rtx *, rtx *));
742 static void find_pre_sched_live PROTO ((int));
743 static void find_post_sched_live PROTO ((int));
744 static void update_reg_usage PROTO ((void));
745 static int queue_to_ready PROTO ((rtx [], int));
747 static void debug_ready_list PROTO ((rtx[], int));
748 static void init_target_units PROTO ((void));
749 static void insn_print_units PROTO ((rtx));
750 static int get_visual_tbl_length PROTO ((void));
751 static void init_block_visualization PROTO ((void));
752 static void print_block_visualization PROTO ((int, char *));
753 static void visualize_scheduled_insns PROTO ((int, int));
754 static void visualize_no_unit PROTO ((rtx));
755 static void visualize_stall_cycles PROTO ((int, int));
756 static void print_exp PROTO ((char *, rtx, int));
757 static void print_value PROTO ((char *, rtx, int));
758 static void print_pattern PROTO ((char *, rtx, int));
759 static void print_insn PROTO ((char *, rtx, int));
760 void debug_reg_vector PROTO ((regset));
762 static rtx move_insn1 PROTO ((rtx, rtx));
763 static rtx move_insn PROTO ((rtx, rtx));
764 static rtx group_leader PROTO ((rtx));
765 static int set_priorities PROTO ((int));
766 static void init_rtx_vector PROTO ((rtx **, rtx *, int, int));
767 static void schedule_region PROTO ((int));
769 #endif /* INSN_SCHEDULING */
771 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
773 /* Helper functions for instruction scheduling. */
775 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
776 static rtx unused_insn_list;
778 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
779 static rtx unused_expr_list;
781 static void free_list PROTO ((rtx *, rtx *));
782 static rtx alloc_INSN_LIST PROTO ((rtx, rtx));
783 static rtx alloc_EXPR_LIST PROTO ((int, rtx, rtx));
786 free_list (listp, unused_listp)
787 rtx *listp, *unused_listp;
789 register rtx link, prev_link;
795 link = XEXP (prev_link, 1);
800 link = XEXP (link, 1);
803 XEXP (prev_link, 1) = *unused_listp;
804 *unused_listp = *listp;
809 alloc_INSN_LIST (val, next)
814 if (unused_insn_list)
816 r = unused_insn_list;
817 unused_insn_list = XEXP (r, 1);
820 PUT_REG_NOTE_KIND (r, VOIDmode);
823 r = gen_rtx_INSN_LIST (VOIDmode, val, next);
829 alloc_EXPR_LIST (kind, val, next)
835 if (unused_expr_list)
837 r = unused_expr_list;
838 unused_expr_list = XEXP (r, 1);
841 PUT_REG_NOTE_KIND (r, kind);
844 r = gen_rtx_EXPR_LIST (kind, val, next);
849 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
850 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
851 of dependence that this link represents. */
854 add_dependence (insn, elem, dep_type)
857 enum reg_note dep_type;
861 /* Don't depend an insn on itself. */
865 /* We can get a dependency on deleted insns due to optimizations in
866 the register allocation and reloading or due to splitting. Any
867 such dependency is useless and can be ignored. */
868 if (GET_CODE (elem) == NOTE)
871 /* If elem is part of a sequence that must be scheduled together, then
872 make the dependence point to the last insn of the sequence.
873 When HAVE_cc0, it is possible for NOTEs to exist between users and
874 setters of the condition codes, so we must skip past notes here.
875 Otherwise, NOTEs are impossible here. */
877 next = NEXT_INSN (elem);
880 while (next && GET_CODE (next) == NOTE)
881 next = NEXT_INSN (next);
884 if (next && SCHED_GROUP_P (next)
885 && GET_CODE (next) != CODE_LABEL)
887 /* Notes will never intervene here though, so don't bother checking
889 /* We must reject CODE_LABELs, so that we don't get confused by one
890 that has LABEL_PRESERVE_P set, which is represented by the same
891 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
893 while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
894 && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
895 next = NEXT_INSN (next);
897 /* Again, don't depend an insn on itself. */
901 /* Make the dependence to NEXT, the last insn of the group, instead
902 of the original ELEM. */
906 #ifdef INSN_SCHEDULING
907 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
908 No need for interblock dependences with calls, since
909 calls are not moved between blocks. Note: the edge where
910 elem is a CALL is still required. */
911 if (GET_CODE (insn) == CALL_INSN
912 && (INSN_BB (elem) != INSN_BB (insn)))
917 /* Check that we don't already have this dependence. */
918 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
919 if (XEXP (link, 0) == elem)
921 /* If this is a more restrictive type of dependence than the existing
922 one, then change the existing dependence to this type. */
923 if ((int) dep_type < (int) REG_NOTE_KIND (link))
924 PUT_REG_NOTE_KIND (link, dep_type);
927 /* Might want to check one level of transitivity to save conses. */
929 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
930 LOG_LINKS (insn) = link;
932 /* Insn dependency, not data dependency. */
933 PUT_REG_NOTE_KIND (link, dep_type);
936 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
937 of INSN. Abort if not found. */
940 remove_dependence (insn, elem)
944 rtx prev, link, next;
947 for (prev = 0, link = LOG_LINKS (insn); link; link = next)
949 next = XEXP (link, 1);
950 if (XEXP (link, 0) == elem)
953 XEXP (prev, 1) = next;
955 LOG_LINKS (insn) = next;
957 XEXP (link, 1) = unused_insn_list;
958 unused_insn_list = link;
971 #ifndef INSN_SCHEDULING
973 schedule_insns (dump_file)
983 #define HAIFA_INLINE __inline
986 /* Computation of memory dependencies. */
988 /* The *_insns and *_mems are paired lists. Each pending memory operation
989 will have a pointer to the MEM rtx on one list and a pointer to the
990 containing insn on the other list in the same place in the list. */
992 /* We can't use add_dependence like the old code did, because a single insn
993 may have multiple memory accesses, and hence needs to be on the list
994 once for each memory access. Add_dependence won't let you add an insn
995 to a list more than once. */
997 /* An INSN_LIST containing all insns with pending read operations. */
998 static rtx pending_read_insns;
1000 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
1001 static rtx pending_read_mems;
1003 /* An INSN_LIST containing all insns with pending write operations. */
1004 static rtx pending_write_insns;
1006 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
1007 static rtx pending_write_mems;
1009 /* Indicates the combined length of the two pending lists. We must prevent
1010 these lists from ever growing too large since the number of dependencies
1011 produced is at least O(N*N), and execution time is at least O(4*N*N), as
1012 a function of the length of these pending lists. */
1014 static int pending_lists_length;
1016 /* The last insn upon which all memory references must depend.
1017 This is an insn which flushed the pending lists, creating a dependency
1018 between it and all previously pending memory references. This creates
1019 a barrier (or a checkpoint) which no memory reference is allowed to cross.
1021 This includes all non constant CALL_INSNs. When we do interprocedural
1022 alias analysis, this restriction can be relaxed.
1023 This may also be an INSN that writes memory if the pending lists grow
1026 static rtx last_pending_memory_flush;
1028 /* The last function call we have seen. All hard regs, and, of course,
1029 the last function call, must depend on this. */
1031 static rtx last_function_call;
1033 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
1034 that does not already cross a call. We create dependencies between each
1035 of those insn and the next call insn, to ensure that they won't cross a call
1036 after scheduling is done. */
1038 static rtx sched_before_next_call;
1040 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1041 so that insns independent of the last scheduled insn will be preferred
1042 over dependent instructions. */
1044 static rtx last_scheduled_insn;
1046 /* Data structures for the computation of data dependences in a regions. We
1047 keep one copy of each of the declared above variables for each bb in the
1048 region. Before analyzing the data dependences for a bb, its variables
1049 are initialized as a function of the variables of its predecessors. When
1050 the analysis for a bb completes, we save the contents of each variable X
1051 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
1052 copied to bb_pending_read_insns[bb]. Another change is that few
1053 variables are now a list of insns rather than a single insn:
1054 last_pending_memory_flash, last_function_call, reg_last_sets. The
1055 manipulation of these variables was changed appropriately. */
1057 static rtx **bb_reg_last_uses;
1058 static rtx **bb_reg_last_sets;
1059 static rtx **bb_reg_last_clobbers;
1061 static rtx *bb_pending_read_insns;
1062 static rtx *bb_pending_read_mems;
1063 static rtx *bb_pending_write_insns;
1064 static rtx *bb_pending_write_mems;
1065 static int *bb_pending_lists_length;
1067 static rtx *bb_last_pending_memory_flush;
1068 static rtx *bb_last_function_call;
1069 static rtx *bb_sched_before_next_call;
1071 /* functions for construction of the control flow graph. */
1073 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1075 We decide not to build the control flow graph if there is possibly more
1076 than one entry to the function, if computed branches exist, of if we
1077 have nonlocal gotos. */
1080 is_cfg_nonregular ()
1086 /* If we have a label that could be the target of a nonlocal goto, then
1087 the cfg is not well structured. */
1088 if (nonlocal_goto_handler_labels)
1091 /* If we have any forced labels, then the cfg is not well structured. */
1095 /* If this function has a computed jump, then we consider the cfg
1096 not well structured. */
1097 if (current_function_has_computed_jump)
1100 /* If we have exception handlers, then we consider the cfg not well
1101 structured. ?!? We should be able to handle this now that flow.c
1102 computes an accurate cfg for EH. */
1103 if (exception_handler_labels)
1106 /* If we have non-jumping insns which refer to labels, then we consider
1107 the cfg not well structured. */
1108 /* check for labels referred to other thn by jumps */
1109 for (b = 0; b < n_basic_blocks; b++)
1110 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
1112 code = GET_CODE (insn);
1113 if (GET_RTX_CLASS (code) == 'i')
1117 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1118 if (REG_NOTE_KIND (note) == REG_LABEL)
1122 if (insn == BLOCK_END (b))
1126 /* All the tests passed. Consider the cfg well structured. */
1130 /* Build the control flow graph and set nr_edges.
1132 Instead of trying to build a cfg ourselves, we rely on flow to
1133 do it for us. Stamp out useless code (and bug) duplication.
1135 Return nonzero if an irregularity in the cfg is found which would
1136 prevent cross block scheduling. */
1139 build_control_flow (s_preds, s_succs, num_preds, num_succs)
1140 int_list_ptr *s_preds;
1141 int_list_ptr *s_succs;
1149 /* Count the number of edges in the cfg. */
1152 for (i = 0; i < n_basic_blocks; i++)
1154 nr_edges += num_succs[i];
1156 /* Unreachable loops with more than one basic block are detected
1157 during the DFS traversal in find_rgns.
1159 Unreachable loops with a single block are detected here. This
1160 test is redundant with the one in find_rgns, but it's much
1161 cheaper to go ahead and catch the trivial case here. */
1162 if (num_preds[i] == 0
1163 || (num_preds[i] == 1 && INT_LIST_VAL (s_preds[i]) == i))
1167 /* Account for entry/exit edges. */
1170 in_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
1171 out_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
1172 bzero ((char *) in_edges, n_basic_blocks * sizeof (int));
1173 bzero ((char *) out_edges, n_basic_blocks * sizeof (int));
1175 edge_table = (haifa_edge *) xmalloc ((nr_edges) * sizeof (haifa_edge));
1176 bzero ((char *) edge_table, ((nr_edges) * sizeof (haifa_edge)));
1179 for (i = 0; i < n_basic_blocks; i++)
1180 for (succ = s_succs[i]; succ; succ = succ->next)
1182 if (INT_LIST_VAL (succ) != EXIT_BLOCK)
1183 new_edge (i, INT_LIST_VAL (succ));
1186 /* increment by 1, since edge 0 is unused. */
1193 /* Record an edge in the control flow graph from SOURCE to TARGET.
1195 In theory, this is redundant with the s_succs computed above, but
1196 we have not converted all of haifa to use information from the
1200 new_edge (source, target)
1204 int curr_edge, fst_edge;
1206 /* check for duplicates */
1207 fst_edge = curr_edge = OUT_EDGES (source);
1210 if (FROM_BLOCK (curr_edge) == source
1211 && TO_BLOCK (curr_edge) == target)
1216 curr_edge = NEXT_OUT (curr_edge);
1218 if (fst_edge == curr_edge)
1224 FROM_BLOCK (e) = source;
1225 TO_BLOCK (e) = target;
1227 if (OUT_EDGES (source))
1229 next_edge = NEXT_OUT (OUT_EDGES (source));
1230 NEXT_OUT (OUT_EDGES (source)) = e;
1231 NEXT_OUT (e) = next_edge;
1235 OUT_EDGES (source) = e;
1239 if (IN_EDGES (target))
1241 next_edge = NEXT_IN (IN_EDGES (target));
1242 NEXT_IN (IN_EDGES (target)) = e;
1243 NEXT_IN (e) = next_edge;
1247 IN_EDGES (target) = e;
1253 /* BITSET macros for operations on the control flow graph. */
1255 /* Compute bitwise union of two bitsets. */
1256 #define BITSET_UNION(set1, set2, len) \
1257 do { register bitset tp = set1, sp = set2; \
1259 for (i = 0; i < len; i++) \
1260 *(tp++) |= *(sp++); } while (0)
1262 /* Compute bitwise intersection of two bitsets. */
1263 #define BITSET_INTER(set1, set2, len) \
1264 do { register bitset tp = set1, sp = set2; \
1266 for (i = 0; i < len; i++) \
1267 *(tp++) &= *(sp++); } while (0)
1269 /* Compute bitwise difference of two bitsets. */
1270 #define BITSET_DIFFER(set1, set2, len) \
1271 do { register bitset tp = set1, sp = set2; \
1273 for (i = 0; i < len; i++) \
1274 *(tp++) &= ~*(sp++); } while (0)
1276 /* Inverts every bit of bitset 'set' */
1277 #define BITSET_INVERT(set, len) \
1278 do { register bitset tmpset = set; \
1280 for (i = 0; i < len; i++, tmpset++) \
1281 *tmpset = ~*tmpset; } while (0)
1283 /* Turn on the index'th bit in bitset set. */
1284 #define BITSET_ADD(set, index, len) \
1286 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1289 set[index/HOST_BITS_PER_WIDE_INT] |= \
1290 1 << (index % HOST_BITS_PER_WIDE_INT); \
1293 /* Turn off the index'th bit in set. */
1294 #define BITSET_REMOVE(set, index, len) \
1296 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1299 set[index/HOST_BITS_PER_WIDE_INT] &= \
1300 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1304 /* Check if the index'th bit in bitset set is on. */
1307 bitset_member (set, index, len)
1311 if (index >= HOST_BITS_PER_WIDE_INT * len)
1313 return (set[index / HOST_BITS_PER_WIDE_INT] &
1314 1 << (index % HOST_BITS_PER_WIDE_INT)) ? 1 : 0;
1318 /* Translate a bit-set SET to a list BL of the bit-set members. */
1321 extract_bitlst (set, len, bl)
1327 unsigned HOST_WIDE_INT word;
1329 /* bblst table space is reused in each call to extract_bitlst */
1330 bitlst_table_last = 0;
1332 bl->first_member = &bitlst_table[bitlst_table_last];
1335 for (i = 0; i < len; i++)
1338 offset = i * HOST_BITS_PER_WIDE_INT;
1339 for (j = 0; word; j++)
1343 bitlst_table[bitlst_table_last++] = offset;
1354 /* functions for the construction of regions */
1356 /* Print the regions, for debugging purposes. Callable from debugger. */
1363 fprintf (dump, "\n;; ------------ REGIONS ----------\n\n");
1364 for (rgn = 0; rgn < nr_regions; rgn++)
1366 fprintf (dump, ";;\trgn %d nr_blocks %d:\n", rgn,
1367 rgn_table[rgn].rgn_nr_blocks);
1368 fprintf (dump, ";;\tbb/block: ");
1370 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
1372 current_blocks = RGN_BLOCKS (rgn);
1374 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
1377 fprintf (dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
1380 fprintf (dump, "\n\n");
1385 /* Build a single block region for each basic block in the function.
1386 This allows for using the same code for interblock and basic block
1390 find_single_block_region ()
1394 for (i = 0; i < n_basic_blocks; i++)
1396 rgn_bb_table[i] = i;
1397 RGN_NR_BLOCKS (i) = 1;
1399 CONTAINING_RGN (i) = i;
1400 BLOCK_TO_BB (i) = 0;
1402 nr_regions = n_basic_blocks;
1406 /* Update number of blocks and the estimate for number of insns
1407 in the region. Return 1 if the region is "too large" for interblock
1408 scheduling (compile time considerations), otherwise return 0. */
1411 too_large (block, num_bbs, num_insns)
1412 int block, *num_bbs, *num_insns;
1415 (*num_insns) += (INSN_LUID (BLOCK_END (block)) -
1416 INSN_LUID (BLOCK_HEAD (block)));
1417 if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
1424 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1425 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1426 loop containing blk. */
1427 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1429 if (max_hdr[blk] == -1) \
1430 max_hdr[blk] = hdr; \
1431 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1432 RESET_BIT (inner, hdr); \
1433 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1435 RESET_BIT (inner,max_hdr[blk]); \
1436 max_hdr[blk] = hdr; \
1441 /* Find regions for interblock scheduling.
1443 A region for scheduling can be:
1445 * A loop-free procedure, or
1447 * A reducible inner loop, or
1449 * A basic block not contained in any other region.
1452 ?!? In theory we could build other regions based on extended basic
1453 blocks or reverse extended basic blocks. Is it worth the trouble?
1455 Loop blocks that form a region are put into the region's block list
1456 in topological order.
1458 This procedure stores its results into the following global (ick) variables
1467 We use dominator relationships to avoid making regions out of non-reducible
1470 This procedure needs to be converted to work on pred/succ lists instead
1471 of edge tables. That would simplify it somewhat. */
1474 find_rgns (s_preds, s_succs, num_preds, num_succs, dom)
1475 int_list_ptr *s_preds;
1476 int_list_ptr *s_succs;
1481 int *max_hdr, *dfs_nr, *stack, *queue, *degree;
1483 int node, child, loop_head, i, head, tail;
1484 int count = 0, sp, idx = 0, current_edge = out_edges[0];
1485 int num_bbs, num_insns, unreachable;
1486 int too_large_failure;
1488 /* Note if an edge has been passed. */
1491 /* Note if a block is a natural loop header. */
1494 /* Note if a block is an natural inner loop header. */
1497 /* Note if a block is in the block queue. */
1500 /* Note if a block is in the block queue. */
1503 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1504 and a mapping from block to its loop header (if the block is contained
1505 in a loop, else -1).
1507 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1508 be used as inputs to the second traversal.
1510 STACK, SP and DFS_NR are only used during the first traversal. */
1512 /* Allocate and initialize variables for the first traversal. */
1513 max_hdr = (int *) alloca (n_basic_blocks * sizeof (int));
1514 dfs_nr = (int *) alloca (n_basic_blocks * sizeof (int));
1515 bzero ((char *) dfs_nr, n_basic_blocks * sizeof (int));
1516 stack = (int *) alloca (nr_edges * sizeof (int));
1518 inner = sbitmap_alloc (n_basic_blocks);
1519 sbitmap_ones (inner);
1521 header = sbitmap_alloc (n_basic_blocks);
1522 sbitmap_zero (header);
1524 passed = sbitmap_alloc (nr_edges);
1525 sbitmap_zero (passed);
1527 in_queue = sbitmap_alloc (n_basic_blocks);
1528 sbitmap_zero (in_queue);
1530 in_stack = sbitmap_alloc (n_basic_blocks);
1531 sbitmap_zero (in_stack);
1533 for (i = 0; i < n_basic_blocks; i++)
1536 /* DFS traversal to find inner loops in the cfg. */
1541 if (current_edge == 0 || TEST_BIT (passed, current_edge))
1543 /* We have reached a leaf node or a node that was already
1544 processed. Pop edges off the stack until we find
1545 an edge that has not yet been processed. */
1547 && (current_edge == 0 || TEST_BIT (passed, current_edge)))
1549 /* Pop entry off the stack. */
1550 current_edge = stack[sp--];
1551 node = FROM_BLOCK (current_edge);
1552 child = TO_BLOCK (current_edge);
1553 RESET_BIT (in_stack, child);
1554 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1555 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1556 current_edge = NEXT_OUT (current_edge);
1559 /* See if have finished the DFS tree traversal. */
1560 if (sp < 0 && TEST_BIT (passed, current_edge))
1563 /* Nope, continue the traversal with the popped node. */
1567 /* Process a node. */
1568 node = FROM_BLOCK (current_edge);
1569 child = TO_BLOCK (current_edge);
1570 SET_BIT (in_stack, node);
1571 dfs_nr[node] = ++count;
1573 /* If the successor is in the stack, then we've found a loop.
1574 Mark the loop, if it is not a natural loop, then it will
1575 be rejected during the second traversal. */
1576 if (TEST_BIT (in_stack, child))
1579 SET_BIT (header, child);
1580 UPDATE_LOOP_RELATIONS (node, child);
1581 SET_BIT (passed, current_edge);
1582 current_edge = NEXT_OUT (current_edge);
1586 /* If the child was already visited, then there is no need to visit
1587 it again. Just update the loop relationships and restart
1591 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1592 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1593 SET_BIT (passed, current_edge);
1594 current_edge = NEXT_OUT (current_edge);
1598 /* Push an entry on the stack and continue DFS traversal. */
1599 stack[++sp] = current_edge;
1600 SET_BIT (passed, current_edge);
1601 current_edge = OUT_EDGES (child);
1604 /* Another check for unreachable blocks. The earlier test in
1605 is_cfg_nonregular only finds unreachable blocks that do not
1608 The DFS traversal will mark every block that is reachable from
1609 the entry node by placing a nonzero value in dfs_nr. Thus if
1610 dfs_nr is zero for any block, then it must be unreachable. */
1612 for (i = 0; i < n_basic_blocks; i++)
1619 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1620 to hold degree counts. */
1623 /* Compute the in-degree of every block in the graph */
1624 for (i = 0; i < n_basic_blocks; i++)
1625 degree[i] = num_preds[i];
1627 /* Do not perform region scheduling if there are any unreachable
1632 SET_BIT (header, 0);
1634 /* Second travsersal:find reducible inner loops and topologically sort
1635 block of each region. */
1637 queue = (int *) alloca (n_basic_blocks * sizeof (int));
1639 /* Find blocks which are inner loop headers. We still have non-reducible
1640 loops to consider at this point. */
1641 for (i = 0; i < n_basic_blocks; i++)
1643 if (TEST_BIT (header, i) && TEST_BIT (inner, i))
1648 /* Now check that the loop is reducible. We do this separate
1649 from finding inner loops so that we do not find a reducible
1650 loop which contains an inner non-reducible loop.
1652 A simple way to find reducible/natrual loops is to verify
1653 that each block in the loop is dominated by the loop
1656 If there exists a block that is not dominated by the loop
1657 header, then the block is reachable from outside the loop
1658 and thus the loop is not a natural loop. */
1659 for (j = 0; j < n_basic_blocks; j++)
1661 /* First identify blocks in the loop, except for the loop
1663 if (i == max_hdr[j] && i != j)
1665 /* Now verify that the block is dominated by the loop
1667 if (!TEST_BIT (dom[j], i))
1672 /* If we exited the loop early, then I is the header of a non
1673 reducible loop and we should quit processing it now. */
1674 if (j != n_basic_blocks)
1677 /* I is a header of an inner loop, or block 0 in a subroutine
1678 with no loops at all. */
1680 too_large_failure = 0;
1681 loop_head = max_hdr[i];
1683 /* Decrease degree of all I's successors for topological
1685 for (ps = s_succs[i]; ps; ps = ps->next)
1686 if (INT_LIST_VAL (ps) != EXIT_BLOCK
1687 && INT_LIST_VAL (ps) != ENTRY_BLOCK)
1688 --degree[INT_LIST_VAL(ps)];
1690 /* Estimate # insns, and count # blocks in the region. */
1692 num_insns = (INSN_LUID (BLOCK_END (i))
1693 - INSN_LUID (BLOCK_HEAD (i)));
1696 /* Find all loop latches (blocks which back edges to the loop
1697 header) or all the leaf blocks in the cfg has no loops.
1699 Place those blocks into the queue. */
1702 for (j = 0; j < n_basic_blocks; j++)
1703 /* Leaf nodes have only a single successor which must
1705 if (num_succs[j] == 1
1706 && INT_LIST_VAL (s_succs[j]) == EXIT_BLOCK)
1709 SET_BIT (in_queue, j);
1711 if (too_large (j, &num_bbs, &num_insns))
1713 too_large_failure = 1;
1722 for (ps = s_preds[i]; ps; ps = ps->next)
1724 node = INT_LIST_VAL (ps);
1726 if (node == ENTRY_BLOCK || node == EXIT_BLOCK)
1729 if (max_hdr[node] == loop_head && node != i)
1731 /* This is a loop latch. */
1732 queue[++tail] = node;
1733 SET_BIT (in_queue, node);
1735 if (too_large (node, &num_bbs, &num_insns))
1737 too_large_failure = 1;
1745 /* Now add all the blocks in the loop to the queue.
1747 We know the loop is a natural loop; however the algorithm
1748 above will not always mark certain blocks as being in the
1757 The algorithm in the DFS traversal may not mark B & D as part
1758 of the loop (ie they will not have max_hdr set to A).
1760 We know they can not be loop latches (else they would have
1761 had max_hdr set since they'd have a backedge to a dominator
1762 block). So we don't need them on the initial queue.
1764 We know they are part of the loop because they are dominated
1765 by the loop header and can be reached by a backwards walk of
1766 the edges starting with nodes on the initial queue.
1768 It is safe and desirable to include those nodes in the
1769 loop/scheduling region. To do so we would need to decrease
1770 the degree of a node if it is the target of a backedge
1771 within the loop itself as the node is placed in the queue.
1773 We do not do this because I'm not sure that the actual
1774 scheduling code will properly handle this case. ?!? */
1776 while (head < tail && !too_large_failure)
1779 child = queue[++head];
1781 for (ps = s_preds[child]; ps; ps = ps->next)
1783 node = INT_LIST_VAL (ps);
1785 /* See discussion above about nodes not marked as in
1786 this loop during the initial DFS traversal. */
1787 if (node == ENTRY_BLOCK || node == EXIT_BLOCK
1788 || max_hdr[node] != loop_head)
1793 else if (!TEST_BIT (in_queue, node) && node != i)
1795 queue[++tail] = node;
1796 SET_BIT (in_queue, node);
1798 if (too_large (node, &num_bbs, &num_insns))
1800 too_large_failure = 1;
1807 if (tail >= 0 && !too_large_failure)
1809 /* Place the loop header into list of region blocks. */
1811 rgn_bb_table[idx] = i;
1812 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1813 RGN_BLOCKS (nr_regions) = idx++;
1814 CONTAINING_RGN (i) = nr_regions;
1815 BLOCK_TO_BB (i) = count = 0;
1817 /* Remove blocks from queue[] when their in degree becomes
1818 zero. Repeat until no blocks are left on the list. This
1819 produces a topological list of blocks in the region. */
1826 child = queue[head];
1827 if (degree[child] == 0)
1830 rgn_bb_table[idx++] = child;
1831 BLOCK_TO_BB (child) = ++count;
1832 CONTAINING_RGN (child) = nr_regions;
1833 queue[head] = queue[tail--];
1835 for (ps = s_succs[child]; ps; ps = ps->next)
1836 if (INT_LIST_VAL (ps) != ENTRY_BLOCK
1837 && INT_LIST_VAL (ps) != EXIT_BLOCK)
1838 --degree[INT_LIST_VAL (ps)];
1849 /* Any block that did not end up in a region is placed into a region
1851 for (i = 0; i < n_basic_blocks; i++)
1854 rgn_bb_table[idx] = i;
1855 RGN_NR_BLOCKS (nr_regions) = 1;
1856 RGN_BLOCKS (nr_regions) = idx++;
1857 CONTAINING_RGN (i) = nr_regions++;
1858 BLOCK_TO_BB (i) = 0;
1869 /* functions for regions scheduling information */
1871 /* Compute dominators, probability, and potential-split-edges of bb.
1872 Assume that these values were already computed for bb's predecessors. */
1875 compute_dom_prob_ps (bb)
1878 int nxt_in_edge, fst_in_edge, pred;
1879 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1882 if (IS_RGN_ENTRY (bb))
1884 BITSET_ADD (dom[bb], 0, bbset_size);
1889 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1891 /* intialize dom[bb] to '111..1' */
1892 BITSET_INVERT (dom[bb], bbset_size);
1896 pred = FROM_BLOCK (nxt_in_edge);
1897 BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
1899 BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
1902 BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
1905 nr_rgn_out_edges = 0;
1906 fst_out_edge = OUT_EDGES (pred);
1907 nxt_out_edge = NEXT_OUT (fst_out_edge);
1908 BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
1911 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
1913 /* the successor doesn't belong the region? */
1914 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1915 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1918 while (fst_out_edge != nxt_out_edge)
1921 /* the successor doesn't belong the region? */
1922 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1923 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1925 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
1926 nxt_out_edge = NEXT_OUT (nxt_out_edge);
1930 /* now nr_rgn_out_edges is the number of region-exit edges from pred,
1931 and nr_out_edges will be the number of pred out edges not leaving
1933 nr_out_edges -= nr_rgn_out_edges;
1934 if (nr_rgn_out_edges > 0)
1935 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1937 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1938 nxt_in_edge = NEXT_IN (nxt_in_edge);
1940 while (fst_in_edge != nxt_in_edge);
1942 BITSET_ADD (dom[bb], bb, bbset_size);
1943 BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
1945 if (sched_verbose >= 2)
1946 fprintf (dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb), (int) (100.0 * prob[bb]));
1947 } /* compute_dom_prob_ps */
1949 /* functions for target info */
1951 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1952 Note that bb_trg dominates bb_src. */
1955 split_edges (bb_src, bb_trg, bl)
1960 int es = edgeset_size;
1961 edgeset src = (edgeset) alloca (es * sizeof (HOST_WIDE_INT));
1964 src[es] = (pot_split[bb_src])[es];
1965 BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
1966 extract_bitlst (src, edgeset_size, bl);
1970 /* Find the valid candidate-source-blocks for the target block TRG, compute
1971 their probability, and check if they are speculative or not.
1972 For speculative sources, compute their update-blocks and split-blocks. */
1975 compute_trg_info (trg)
1978 register candidate *sp;
1980 int check_block, update_idx;
1981 int i, j, k, fst_edge, nxt_edge;
1983 /* define some of the fields for the target bb as well */
1984 sp = candidate_table + trg;
1986 sp->is_speculative = 0;
1989 for (i = trg + 1; i < current_nr_blocks; i++)
1991 sp = candidate_table + i;
1993 sp->is_valid = IS_DOMINATED (i, trg);
1996 sp->src_prob = GET_SRC_PROB (i, trg);
1997 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
2002 split_edges (i, trg, &el);
2003 sp->is_speculative = (el.nr_members) ? 1 : 0;
2004 if (sp->is_speculative && !flag_schedule_speculative)
2010 sp->split_bbs.first_member = &bblst_table[bblst_last];
2011 sp->split_bbs.nr_members = el.nr_members;
2012 for (j = 0; j < el.nr_members; bblst_last++, j++)
2013 bblst_table[bblst_last] =
2014 TO_BLOCK (rgn_edges[el.first_member[j]]);
2015 sp->update_bbs.first_member = &bblst_table[bblst_last];
2017 for (j = 0; j < el.nr_members; j++)
2019 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
2020 fst_edge = nxt_edge = OUT_EDGES (check_block);
2023 for (k = 0; k < el.nr_members; k++)
2024 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
2027 if (k >= el.nr_members)
2029 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
2033 nxt_edge = NEXT_OUT (nxt_edge);
2035 while (fst_edge != nxt_edge);
2037 sp->update_bbs.nr_members = update_idx;
2042 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
2044 sp->is_speculative = 0;
2048 } /* compute_trg_info */
2051 /* Print candidates info, for debugging purposes. Callable from debugger. */
2057 if (!candidate_table[i].is_valid)
2060 if (candidate_table[i].is_speculative)
2063 fprintf (dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
2065 fprintf (dump, "split path: ");
2066 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
2068 int b = candidate_table[i].split_bbs.first_member[j];
2070 fprintf (dump, " %d ", b);
2072 fprintf (dump, "\n");
2074 fprintf (dump, "update path: ");
2075 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
2077 int b = candidate_table[i].update_bbs.first_member[j];
2079 fprintf (dump, " %d ", b);
2081 fprintf (dump, "\n");
2085 fprintf (dump, " src %d equivalent\n", BB_TO_BLOCK (i));
2090 /* Print candidates info, for debugging purposes. Callable from debugger. */
2093 debug_candidates (trg)
2098 fprintf (dump, "----------- candidate table: target: b=%d bb=%d ---\n",
2099 BB_TO_BLOCK (trg), trg);
2100 for (i = trg + 1; i < current_nr_blocks; i++)
2101 debug_candidate (i);
2105 /* functions for speculative scheduing */
2107 /* Return 0 if x is a set of a register alive in the beginning of one
2108 of the split-blocks of src, otherwise return 1. */
2111 check_live_1 (src, x)
2117 register rtx reg = SET_DEST (x);
2122 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2123 || GET_CODE (reg) == SIGN_EXTRACT
2124 || GET_CODE (reg) == STRICT_LOW_PART)
2125 reg = XEXP (reg, 0);
2127 if (GET_CODE (reg) == PARALLEL
2128 && GET_MODE (reg) == BLKmode)
2131 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2132 if (check_live_1 (src, XVECEXP (reg, 0, i)))
2137 if (GET_CODE (reg) != REG)
2140 regno = REGNO (reg);
2142 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2144 /* Global registers are assumed live */
2149 if (regno < FIRST_PSEUDO_REGISTER)
2151 /* check for hard registers */
2152 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2155 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2157 int b = candidate_table[src].split_bbs.first_member[i];
2159 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
2169 /* check for psuedo registers */
2170 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2172 int b = candidate_table[src].split_bbs.first_member[i];
2174 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
2186 /* If x is a set of a register R, mark that R is alive in the beginning
2187 of every update-block of src. */
2190 update_live_1 (src, x)
2196 register rtx reg = SET_DEST (x);
2201 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2202 || GET_CODE (reg) == SIGN_EXTRACT
2203 || GET_CODE (reg) == STRICT_LOW_PART)
2204 reg = XEXP (reg, 0);
2206 if (GET_CODE (reg) == PARALLEL
2207 && GET_MODE (reg) == BLKmode)
2210 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2211 update_live_1 (src, XVECEXP (reg, 0, i));
2215 if (GET_CODE (reg) != REG)
2218 /* Global registers are always live, so the code below does not apply
2221 regno = REGNO (reg);
2223 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
2225 if (regno < FIRST_PSEUDO_REGISTER)
2227 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2230 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2232 int b = candidate_table[src].update_bbs.first_member[i];
2234 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
2241 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2243 int b = candidate_table[src].update_bbs.first_member[i];
2245 SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
2252 /* Return 1 if insn can be speculatively moved from block src to trg,
2253 otherwise return 0. Called before first insertion of insn to
2254 ready-list or before the scheduling. */
2257 check_live (insn, src)
2261 /* find the registers set by instruction */
2262 if (GET_CODE (PATTERN (insn)) == SET
2263 || GET_CODE (PATTERN (insn)) == CLOBBER)
2264 return check_live_1 (src, PATTERN (insn));
2265 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2268 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2269 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2270 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2271 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
2281 /* Update the live registers info after insn was moved speculatively from
2282 block src to trg. */
2285 update_live (insn, src)
2289 /* find the registers set by instruction */
2290 if (GET_CODE (PATTERN (insn)) == SET
2291 || GET_CODE (PATTERN (insn)) == CLOBBER)
2292 update_live_1 (src, PATTERN (insn));
2293 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2296 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2297 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2298 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2299 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
2303 /* Exception Free Loads:
2305 We define five classes of speculative loads: IFREE, IRISKY,
2306 PFREE, PRISKY, and MFREE.
2308 IFREE loads are loads that are proved to be exception-free, just
2309 by examining the load insn. Examples for such loads are loads
2310 from TOC and loads of global data.
2312 IRISKY loads are loads that are proved to be exception-risky,
2313 just by examining the load insn. Examples for such loads are
2314 volatile loads and loads from shared memory.
2316 PFREE loads are loads for which we can prove, by examining other
2317 insns, that they are exception-free. Currently, this class consists
2318 of loads for which we are able to find a "similar load", either in
2319 the target block, or, if only one split-block exists, in that split
2320 block. Load2 is similar to load1 if both have same single base
2321 register. We identify only part of the similar loads, by finding
2322 an insn upon which both load1 and load2 have a DEF-USE dependence.
2324 PRISKY loads are loads for which we can prove, by examining other
2325 insns, that they are exception-risky. Currently we have two proofs for
2326 such loads. The first proof detects loads that are probably guarded by a
2327 test on the memory address. This proof is based on the
2328 backward and forward data dependence information for the region.
2329 Let load-insn be the examined load.
2330 Load-insn is PRISKY iff ALL the following hold:
2332 - insn1 is not in the same block as load-insn
2333 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2334 - test-insn is either a compare or a branch, not in the same block as load-insn
2335 - load-insn is reachable from test-insn
2336 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2338 This proof might fail when the compare and the load are fed
2339 by an insn not in the region. To solve this, we will add to this
2340 group all loads that have no input DEF-USE dependence.
2342 The second proof detects loads that are directly or indirectly
2343 fed by a speculative load. This proof is affected by the
2344 scheduling process. We will use the flag fed_by_spec_load.
2345 Initially, all insns have this flag reset. After a speculative
2346 motion of an insn, if insn is either a load, or marked as
2347 fed_by_spec_load, we will also mark as fed_by_spec_load every
2348 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2349 load which is fed_by_spec_load is also PRISKY.
2351 MFREE (maybe-free) loads are all the remaining loads. They may be
2352 exception-free, but we cannot prove it.
2354 Now, all loads in IFREE and PFREE classes are considered
2355 exception-free, while all loads in IRISKY and PRISKY classes are
2356 considered exception-risky. As for loads in the MFREE class,
2357 these are considered either exception-free or exception-risky,
2358 depending on whether we are pessimistic or optimistic. We have
2359 to take the pessimistic approach to assure the safety of
2360 speculative scheduling, but we can take the optimistic approach
2361 by invoking the -fsched_spec_load_dangerous option. */
2363 enum INSN_TRAP_CLASS
2365 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
2366 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
2369 #define WORST_CLASS(class1, class2) \
2370 ((class1 > class2) ? class1 : class2)
2372 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between */
2373 /* some speculatively moved load insn and this one. */
2374 char *fed_by_spec_load;
2377 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2378 #define IS_REACHABLE(bb_from, bb_to) \
2380 || IS_RGN_ENTRY (bb_from) \
2381 || (bitset_member (ancestor_edges[bb_to], \
2382 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2384 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2385 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2387 /* Non-zero iff the address is comprised from at most 1 register */
2388 #define CONST_BASED_ADDRESS_P(x) \
2389 (GET_CODE (x) == REG \
2390 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2391 || (GET_CODE (x) == LO_SUM)) \
2392 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2393 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2395 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2398 set_spec_fed (load_insn)
2403 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
2404 if (GET_MODE (link) == VOIDmode)
2405 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
2406 } /* set_spec_fed */
2408 /* On the path from the insn to load_insn_bb, find a conditional branch */
2409 /* depending on insn, that guards the speculative load. */
2412 find_conditional_protection (insn, load_insn_bb)
2418 /* iterate through DEF-USE forward dependences */
2419 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2421 rtx next = XEXP (link, 0);
2422 if ((CONTAINING_RGN (INSN_BLOCK (next)) ==
2423 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
2424 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
2425 && load_insn_bb != INSN_BB (next)
2426 && GET_MODE (link) == VOIDmode
2427 && (GET_CODE (next) == JUMP_INSN
2428 || find_conditional_protection (next, load_insn_bb)))
2432 } /* find_conditional_protection */
2434 /* Returns 1 if the same insn1 that participates in the computation
2435 of load_insn's address is feeding a conditional branch that is
2436 guarding on load_insn. This is true if we find a the two DEF-USE
2438 insn1 -> ... -> conditional-branch
2439 insn1 -> ... -> load_insn,
2440 and if a flow path exist:
2441 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2442 and if insn1 is on the path
2443 region-entry -> ... -> bb_trg -> ... load_insn.
2445 Locate insn1 by climbing on LOG_LINKS from load_insn.
2446 Locate the branch by following INSN_DEPEND from insn1. */
2449 is_conditionally_protected (load_insn, bb_src, bb_trg)
2455 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
2457 rtx insn1 = XEXP (link, 0);
2459 /* must be a DEF-USE dependence upon non-branch */
2460 if (GET_MODE (link) != VOIDmode
2461 || GET_CODE (insn1) == JUMP_INSN)
2464 /* must exist a path: region-entry -> ... -> bb_trg -> ... load_insn */
2465 if (INSN_BB (insn1) == bb_src
2466 || (CONTAINING_RGN (INSN_BLOCK (insn1))
2467 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
2468 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
2469 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
2472 /* now search for the conditional-branch */
2473 if (find_conditional_protection (insn1, bb_src))
2476 /* recursive step: search another insn1, "above" current insn1. */
2477 return is_conditionally_protected (insn1, bb_src, bb_trg);
2480 /* the chain does not exsist */
2482 } /* is_conditionally_protected */
2484 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2485 load_insn can move speculatively from bb_src to bb_trg. All the
2486 following must hold:
2488 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2489 (2) load_insn and load1 have a def-use dependence upon
2490 the same insn 'insn1'.
2491 (3) either load2 is in bb_trg, or:
2492 - there's only one split-block, and
2493 - load1 is on the escape path, and
2495 From all these we can conclude that the two loads access memory
2496 addresses that differ at most by a constant, and hence if moving
2497 load_insn would cause an exception, it would have been caused by
2501 is_pfree (load_insn, bb_src, bb_trg)
2506 register candidate *candp = candidate_table + bb_src;
2508 if (candp->split_bbs.nr_members != 1)
2509 /* must have exactly one escape block */
2512 for (back_link = LOG_LINKS (load_insn);
2513 back_link; back_link = XEXP (back_link, 1))
2515 rtx insn1 = XEXP (back_link, 0);
2517 if (GET_MODE (back_link) == VOIDmode)
2519 /* found a DEF-USE dependence (insn1, load_insn) */
2522 for (fore_link = INSN_DEPEND (insn1);
2523 fore_link; fore_link = XEXP (fore_link, 1))
2525 rtx insn2 = XEXP (fore_link, 0);
2526 if (GET_MODE (fore_link) == VOIDmode)
2528 /* found a DEF-USE dependence (insn1, insn2) */
2529 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
2530 /* insn2 not guaranteed to be a 1 base reg load */
2533 if (INSN_BB (insn2) == bb_trg)
2534 /* insn2 is the similar load, in the target block */
2537 if (*(candp->split_bbs.first_member) == INSN_BLOCK (insn2))
2538 /* insn2 is a similar load, in a split-block */
2545 /* couldn't find a similar load */
2549 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2550 as found by analyzing insn's expression. */
2553 may_trap_exp (x, is_store)
2561 code = GET_CODE (x);
2571 /* The insn uses memory */
2572 /* a volatile load */
2573 if (MEM_VOLATILE_P (x))
2575 /* an exception-free load */
2576 if (!may_trap_p (x))
2578 /* a load with 1 base register, to be further checked */
2579 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
2580 return PFREE_CANDIDATE;
2581 /* no info on the load, to be further checked */
2582 return PRISKY_CANDIDATE;
2587 int i, insn_class = TRAP_FREE;
2589 /* neither store nor load, check if it may cause a trap */
2592 /* recursive step: walk the insn... */
2593 fmt = GET_RTX_FORMAT (code);
2594 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2598 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
2599 insn_class = WORST_CLASS (insn_class, tmp_class);
2601 else if (fmt[i] == 'E')
2604 for (j = 0; j < XVECLEN (x, i); j++)
2606 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
2607 insn_class = WORST_CLASS (insn_class, tmp_class);
2608 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2612 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2617 } /* may_trap_exp */
2620 /* Classifies insn for the purpose of verifying that it can be
2621 moved speculatively, by examining it's patterns, returning:
2622 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2623 TRAP_FREE: non-load insn.
2624 IFREE: load from a globaly safe location.
2625 IRISKY: volatile load.
2626 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2627 being either PFREE or PRISKY. */
2630 haifa_classify_insn (insn)
2633 rtx pat = PATTERN (insn);
2634 int tmp_class = TRAP_FREE;
2635 int insn_class = TRAP_FREE;
2638 if (GET_CODE (pat) == PARALLEL)
2640 int i, len = XVECLEN (pat, 0);
2642 for (i = len - 1; i >= 0; i--)
2644 code = GET_CODE (XVECEXP (pat, 0, i));
2648 /* test if it is a 'store' */
2649 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
2652 /* test if it is a store */
2653 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
2654 if (tmp_class == TRAP_RISKY)
2656 /* test if it is a load */
2658 WORST_CLASS (tmp_class,
2659 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 0));
2662 tmp_class = TRAP_RISKY;
2666 insn_class = WORST_CLASS (insn_class, tmp_class);
2667 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2673 code = GET_CODE (pat);
2677 /* test if it is a 'store' */
2678 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
2681 /* test if it is a store */
2682 tmp_class = may_trap_exp (SET_DEST (pat), 1);
2683 if (tmp_class == TRAP_RISKY)
2685 /* test if it is a load */
2687 WORST_CLASS (tmp_class,
2688 may_trap_exp (SET_SRC (pat), 0));
2691 tmp_class = TRAP_RISKY;
2695 insn_class = tmp_class;
2700 } /* haifa_classify_insn */
2702 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2703 a load moved speculatively, or if load_insn is protected by
2704 a compare on load_insn's address). */
2707 is_prisky (load_insn, bb_src, bb_trg)
2711 if (FED_BY_SPEC_LOAD (load_insn))
2714 if (LOG_LINKS (load_insn) == NULL)
2715 /* dependence may 'hide' out of the region. */
2718 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2724 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2725 Return 1 if insn is exception-free (and the motion is valid)
2729 is_exception_free (insn, bb_src, bb_trg)
2733 int insn_class = haifa_classify_insn (insn);
2735 /* handle non-load insns */
2746 if (!flag_schedule_speculative_load)
2748 IS_LOAD_INSN (insn) = 1;
2755 case PFREE_CANDIDATE:
2756 if (is_pfree (insn, bb_src, bb_trg))
2758 /* don't 'break' here: PFREE-candidate is also PRISKY-candidate */
2759 case PRISKY_CANDIDATE:
2760 if (!flag_schedule_speculative_load_dangerous
2761 || is_prisky (insn, bb_src, bb_trg))
2767 return flag_schedule_speculative_load_dangerous;
2768 } /* is_exception_free */
2771 /* Process an insn's memory dependencies. There are four kinds of
2774 (0) read dependence: read follows read
2775 (1) true dependence: read follows write
2776 (2) anti dependence: write follows read
2777 (3) output dependence: write follows write
2779 We are careful to build only dependencies which actually exist, and
2780 use transitivity to avoid building too many links. */
2782 /* Return the INSN_LIST containing INSN in LIST, or NULL
2783 if LIST does not contain INSN. */
2785 HAIFA_INLINE static rtx
2786 find_insn_list (insn, list)
2792 if (XEXP (list, 0) == insn)
2794 list = XEXP (list, 1);
2800 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 otherwise. */
2802 HAIFA_INLINE static char
2803 find_insn_mem_list (insn, x, list, list1)
2809 if (XEXP (list, 0) == insn
2810 && XEXP (list1, 0) == x)
2812 list = XEXP (list, 1);
2813 list1 = XEXP (list1, 1);
2819 /* Compute the function units used by INSN. This caches the value
2820 returned by function_units_used. A function unit is encoded as the
2821 unit number if the value is non-negative and the compliment of a
2822 mask if the value is negative. A function unit index is the
2823 non-negative encoding. */
2825 HAIFA_INLINE static int
2829 register int unit = INSN_UNIT (insn);
2833 recog_memoized (insn);
2835 /* A USE insn, or something else we don't need to understand.
2836 We can't pass these directly to function_units_used because it will
2837 trigger a fatal error for unrecognizable insns. */
2838 if (INSN_CODE (insn) < 0)
2842 unit = function_units_used (insn);
2843 /* Increment non-negative values so we can cache zero. */
2847 /* We only cache 16 bits of the result, so if the value is out of
2848 range, don't cache it. */
2849 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
2851 || (~unit & ((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
2852 INSN_UNIT (insn) = unit;
2854 return (unit > 0 ? unit - 1 : unit);
2857 /* Compute the blockage range for executing INSN on UNIT. This caches
2858 the value returned by the blockage_range_function for the unit.
2859 These values are encoded in an int where the upper half gives the
2860 minimum value and the lower half gives the maximum value. */
2862 HAIFA_INLINE static unsigned int
2863 blockage_range (unit, insn)
2867 unsigned int blockage = INSN_BLOCKAGE (insn);
2870 if ((int) UNIT_BLOCKED (blockage) != unit + 1)
2872 range = function_units[unit].blockage_range_function (insn);
2873 /* We only cache the blockage range for one unit and then only if
2875 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
2876 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
2879 range = BLOCKAGE_RANGE (blockage);
2884 /* A vector indexed by function unit instance giving the last insn to use
2885 the unit. The value of the function unit instance index for unit U
2886 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2887 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2889 /* A vector indexed by function unit instance giving the minimum time when
2890 the unit will unblock based on the maximum blockage cost. */
2891 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2893 /* A vector indexed by function unit number giving the number of insns
2894 that remain to use the unit. */
2895 static int unit_n_insns[FUNCTION_UNITS_SIZE];
2897 /* Reset the function unit state to the null state. */
2902 bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
2903 bzero ((char *) unit_tick, sizeof (unit_tick));
2904 bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
2907 /* Return the issue-delay of an insn */
2909 HAIFA_INLINE static int
2910 insn_issue_delay (insn)
2914 int unit = insn_unit (insn);
2916 /* efficiency note: in fact, we are working 'hard' to compute a
2917 value that was available in md file, and is not available in
2918 function_units[] structure. It would be nice to have this
2919 value there, too. */
2922 if (function_units[unit].blockage_range_function &&
2923 function_units[unit].blockage_function)
2924 delay = function_units[unit].blockage_function (insn, insn);
2927 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2928 if ((unit & 1) != 0 && function_units[i].blockage_range_function
2929 && function_units[i].blockage_function)
2930 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
2935 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2936 instance INSTANCE at time CLOCK if the previous actual hazard cost
2939 HAIFA_INLINE static int
2940 actual_hazard_this_instance (unit, instance, insn, clock, cost)
2941 int unit, instance, clock, cost;
2944 int tick = unit_tick[instance]; /* issue time of the last issued insn */
2946 if (tick - clock > cost)
2948 /* The scheduler is operating forward, so unit's last insn is the
2949 executing insn and INSN is the candidate insn. We want a
2950 more exact measure of the blockage if we execute INSN at CLOCK
2951 given when we committed the execution of the unit's last insn.
2953 The blockage value is given by either the unit's max blockage
2954 constant, blockage range function, or blockage function. Use
2955 the most exact form for the given unit. */
2957 if (function_units[unit].blockage_range_function)
2959 if (function_units[unit].blockage_function)
2960 tick += (function_units[unit].blockage_function
2961 (unit_last_insn[instance], insn)
2962 - function_units[unit].max_blockage);
2964 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
2965 - function_units[unit].max_blockage);
2967 if (tick - clock > cost)
2968 cost = tick - clock;
2973 /* Record INSN as having begun execution on the units encoded by UNIT at
2976 HAIFA_INLINE static void
2977 schedule_unit (unit, insn, clock)
2985 int instance = unit;
2986 #if MAX_MULTIPLICITY > 1
2987 /* Find the first free instance of the function unit and use that
2988 one. We assume that one is free. */
2989 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2991 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
2993 instance += FUNCTION_UNITS_SIZE;
2996 unit_last_insn[instance] = insn;
2997 unit_tick[instance] = (clock + function_units[unit].max_blockage);
3000 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3001 if ((unit & 1) != 0)
3002 schedule_unit (i, insn, clock);
3005 /* Return the actual hazard cost of executing INSN on the units encoded by
3006 UNIT at time CLOCK if the previous actual hazard cost was COST. */
3008 HAIFA_INLINE static int
3009 actual_hazard (unit, insn, clock, cost)
3010 int unit, clock, cost;
3017 /* Find the instance of the function unit with the minimum hazard. */
3018 int instance = unit;
3019 int best_cost = actual_hazard_this_instance (unit, instance, insn,
3023 #if MAX_MULTIPLICITY > 1
3024 if (best_cost > cost)
3026 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
3028 instance += FUNCTION_UNITS_SIZE;
3029 this_cost = actual_hazard_this_instance (unit, instance, insn,
3031 if (this_cost < best_cost)
3033 best_cost = this_cost;
3034 if (this_cost <= cost)
3040 cost = MAX (cost, best_cost);
3043 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3044 if ((unit & 1) != 0)
3045 cost = actual_hazard (i, insn, clock, cost);
3050 /* Return the potential hazard cost of executing an instruction on the
3051 units encoded by UNIT if the previous potential hazard cost was COST.
3052 An insn with a large blockage time is chosen in preference to one
3053 with a smaller time; an insn that uses a unit that is more likely
3054 to be used is chosen in preference to one with a unit that is less
3055 used. We are trying to minimize a subsequent actual hazard. */
3057 HAIFA_INLINE static int
3058 potential_hazard (unit, insn, cost)
3063 unsigned int minb, maxb;
3067 minb = maxb = function_units[unit].max_blockage;
3070 if (function_units[unit].blockage_range_function)
3072 maxb = minb = blockage_range (unit, insn);
3073 maxb = MAX_BLOCKAGE_COST (maxb);
3074 minb = MIN_BLOCKAGE_COST (minb);
3079 /* Make the number of instructions left dominate. Make the
3080 minimum delay dominate the maximum delay. If all these
3081 are the same, use the unit number to add an arbitrary
3082 ordering. Other terms can be added. */
3083 ncost = minb * 0x40 + maxb;
3084 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
3091 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3092 if ((unit & 1) != 0)
3093 cost = potential_hazard (i, insn, cost);
3098 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3099 This is the number of cycles between instruction issue and
3100 instruction results. */
3102 HAIFA_INLINE static int
3103 insn_cost (insn, link, used)
3104 rtx insn, link, used;
3106 register int cost = INSN_COST (insn);
3110 recog_memoized (insn);
3112 /* A USE insn, or something else we don't need to understand.
3113 We can't pass these directly to result_ready_cost because it will
3114 trigger a fatal error for unrecognizable insns. */
3115 if (INSN_CODE (insn) < 0)
3117 INSN_COST (insn) = 1;
3122 cost = result_ready_cost (insn);
3127 INSN_COST (insn) = cost;
3131 /* in this case estimate cost without caring how insn is used. */
3132 if (link == 0 && used == 0)
3135 /* A USE insn should never require the value used to be computed. This
3136 allows the computation of a function's result and parameter values to
3137 overlap the return and call. */
3138 recog_memoized (used);
3139 if (INSN_CODE (used) < 0)
3140 LINK_COST_FREE (link) = 1;
3142 /* If some dependencies vary the cost, compute the adjustment. Most
3143 commonly, the adjustment is complete: either the cost is ignored
3144 (in the case of an output- or anti-dependence), or the cost is
3145 unchanged. These values are cached in the link as LINK_COST_FREE
3146 and LINK_COST_ZERO. */
3148 if (LINK_COST_FREE (link))
3151 else if (!LINK_COST_ZERO (link))
3155 ADJUST_COST (used, link, insn, ncost);
3157 LINK_COST_FREE (link) = ncost = 1;
3159 LINK_COST_ZERO (link) = 1;
3166 /* Compute the priority number for INSN. */
3175 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
3178 if ((this_priority = INSN_PRIORITY (insn)) == 0)
3180 if (INSN_DEPEND (insn) == 0)
3181 this_priority = insn_cost (insn, 0, 0);
3183 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
3188 if (RTX_INTEGRATED_P (link))
3191 next = XEXP (link, 0);
3193 /* critical path is meaningful in block boundaries only */
3194 if (INSN_BLOCK (next) != INSN_BLOCK (insn))
3197 next_priority = insn_cost (insn, link, next) + priority (next);
3198 if (next_priority > this_priority)
3199 this_priority = next_priority;
3201 INSN_PRIORITY (insn) = this_priority;
3203 return this_priority;
3207 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3208 them to the unused_*_list variables, so that they can be reused. */
3211 free_pending_lists ()
3213 if (current_nr_blocks <= 1)
3215 free_list (&pending_read_insns, &unused_insn_list);
3216 free_list (&pending_write_insns, &unused_insn_list);
3217 free_list (&pending_read_mems, &unused_expr_list);
3218 free_list (&pending_write_mems, &unused_expr_list);
3222 /* interblock scheduling */
3225 for (bb = 0; bb < current_nr_blocks; bb++)
3227 free_list (&bb_pending_read_insns[bb], &unused_insn_list);
3228 free_list (&bb_pending_write_insns[bb], &unused_insn_list);
3229 free_list (&bb_pending_read_mems[bb], &unused_expr_list);
3230 free_list (&bb_pending_write_mems[bb], &unused_expr_list);
3235 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3236 The MEM is a memory reference contained within INSN, which we are saving
3237 so that we can do memory aliasing on it. */
3240 add_insn_mem_dependence (insn_list, mem_list, insn, mem)
3241 rtx *insn_list, *mem_list, insn, mem;
3245 link = alloc_INSN_LIST (insn, *insn_list);
3248 link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
3251 pending_lists_length++;
3255 /* Make a dependency between every memory reference on the pending lists
3256 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3260 flush_pending_lists (insn, only_write)
3267 while (pending_read_insns && ! only_write)
3269 add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
3271 link = pending_read_insns;
3272 pending_read_insns = XEXP (pending_read_insns, 1);
3273 XEXP (link, 1) = unused_insn_list;
3274 unused_insn_list = link;
3276 link = pending_read_mems;
3277 pending_read_mems = XEXP (pending_read_mems, 1);
3278 XEXP (link, 1) = unused_expr_list;
3279 unused_expr_list = link;
3281 while (pending_write_insns)
3283 add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
3285 link = pending_write_insns;
3286 pending_write_insns = XEXP (pending_write_insns, 1);
3287 XEXP (link, 1) = unused_insn_list;
3288 unused_insn_list = link;
3290 link = pending_write_mems;
3291 pending_write_mems = XEXP (pending_write_mems, 1);
3292 XEXP (link, 1) = unused_expr_list;
3293 unused_expr_list = link;
3295 pending_lists_length = 0;
3297 /* last_pending_memory_flush is now a list of insns */
3298 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3299 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3301 free_list (&last_pending_memory_flush, &unused_insn_list);
3302 last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
3305 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
3306 by the write to the destination of X, and reads of everything mentioned. */
3309 sched_analyze_1 (x, insn)
3314 register rtx dest = SET_DEST (x);
3315 enum rtx_code code = GET_CODE (x);
3320 if (GET_CODE (dest) == PARALLEL
3321 && GET_MODE (dest) == BLKmode)
3324 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
3325 sched_analyze_1 (XVECEXP (dest, 0, i), insn);
3326 if (GET_CODE (x) == SET)
3327 sched_analyze_2 (SET_SRC (x), insn);
3331 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3332 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3334 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3336 /* The second and third arguments are values read by this insn. */
3337 sched_analyze_2 (XEXP (dest, 1), insn);
3338 sched_analyze_2 (XEXP (dest, 2), insn);
3340 dest = SUBREG_REG (dest);
3343 if (GET_CODE (dest) == REG)
3347 regno = REGNO (dest);
3349 /* A hard reg in a wide mode may really be multiple registers.
3350 If so, mark all of them just like the first. */
3351 if (regno < FIRST_PSEUDO_REGISTER)
3353 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
3358 for (u = reg_last_uses[regno + i]; u; u = XEXP (u, 1))
3359 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3360 reg_last_uses[regno + i] = 0;
3362 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3363 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3365 /* Clobbers need not be ordered with respect to one another,
3366 but sets must be ordered with respect to a pending clobber. */
3369 for (u = reg_last_clobbers[regno + i]; u; u = XEXP (u, 1))
3370 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3371 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
3374 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
3376 /* Function calls clobber all call_used regs. */
3377 if (global_regs[regno + i]
3378 || (code == SET && call_used_regs[regno + i]))
3379 for (u = last_function_call; u; u = XEXP (u, 1))
3380 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3387 for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
3388 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3389 reg_last_uses[regno] = 0;
3391 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3392 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3396 for (u = reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3397 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3398 SET_REGNO_REG_SET (reg_pending_sets, regno);
3401 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
3403 /* Pseudos that are REG_EQUIV to something may be replaced
3404 by that during reloading. We need only add dependencies for
3405 the address in the REG_EQUIV note. */
3406 if (!reload_completed
3407 && reg_known_equiv_p[regno]
3408 && GET_CODE (reg_known_value[regno]) == MEM)
3409 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3411 /* Don't let it cross a call after scheduling if it doesn't
3412 already cross one. */
3414 if (REG_N_CALLS_CROSSED (regno) == 0)
3415 for (u = last_function_call; u; u = XEXP (u, 1))
3416 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3419 else if (GET_CODE (dest) == MEM)
3421 /* Writing memory. */
3423 if (pending_lists_length > 32)
3425 /* Flush all pending reads and writes to prevent the pending lists
3426 from getting any larger. Insn scheduling runs too slowly when
3427 these lists get long. The number 32 was chosen because it
3428 seems like a reasonable number. When compiling GCC with itself,
3429 this flush occurs 8 times for sparc, and 10 times for m88k using
3431 flush_pending_lists (insn, 0);
3436 rtx pending, pending_mem;
3438 pending = pending_read_insns;
3439 pending_mem = pending_read_mems;
3442 /* If a dependency already exists, don't create a new one. */
3443 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3444 if (anti_dependence (XEXP (pending_mem, 0), dest))
3445 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3447 pending = XEXP (pending, 1);
3448 pending_mem = XEXP (pending_mem, 1);
3451 pending = pending_write_insns;
3452 pending_mem = pending_write_mems;
3455 /* If a dependency already exists, don't create a new one. */
3456 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3457 if (output_dependence (XEXP (pending_mem, 0), dest))
3458 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
3460 pending = XEXP (pending, 1);
3461 pending_mem = XEXP (pending_mem, 1);
3464 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3465 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3467 add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
3470 sched_analyze_2 (XEXP (dest, 0), insn);
3473 /* Analyze reads. */
3474 if (GET_CODE (x) == SET)
3475 sched_analyze_2 (SET_SRC (x), insn);
3478 /* Analyze the uses of memory and registers in rtx X in INSN. */
3481 sched_analyze_2 (x, insn)
3487 register enum rtx_code code;
3493 code = GET_CODE (x);
3502 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3503 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3504 this does not mean that this insn is using cc0. */
3512 /* User of CC0 depends on immediately preceding insn. */
3513 SCHED_GROUP_P (insn) = 1;
3515 /* There may be a note before this insn now, but all notes will
3516 be removed before we actually try to schedule the insns, so
3517 it won't cause a problem later. We must avoid it here though. */
3518 prev = prev_nonnote_insn (insn);
3520 /* Make a copy of all dependencies on the immediately previous insn,
3521 and add to this insn. This is so that all the dependencies will
3522 apply to the group. Remove an explicit dependence on this insn
3523 as SCHED_GROUP_P now represents it. */
3525 if (find_insn_list (prev, LOG_LINKS (insn)))
3526 remove_dependence (insn, prev);
3528 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
3529 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3538 int regno = REGNO (x);
3539 if (regno < FIRST_PSEUDO_REGISTER)
3543 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
3546 reg_last_uses[regno + i]
3547 = alloc_INSN_LIST (insn, reg_last_uses[regno + i]);
3549 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3550 add_dependence (insn, XEXP (u, 0), 0);
3552 /* ??? This should never happen. */
3553 for (u = reg_last_clobbers[regno + i]; u; u = XEXP (u, 1))
3554 add_dependence (insn, XEXP (u, 0), 0);
3556 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3557 /* Function calls clobber all call_used regs. */
3558 for (u = last_function_call; u; u = XEXP (u, 1))
3559 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3564 reg_last_uses[regno] = alloc_INSN_LIST (insn, reg_last_uses[regno]);
3566 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3567 add_dependence (insn, XEXP (u, 0), 0);
3569 /* ??? This should never happen. */
3570 for (u = reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3571 add_dependence (insn, XEXP (u, 0), 0);
3573 /* Pseudos that are REG_EQUIV to something may be replaced
3574 by that during reloading. We need only add dependencies for
3575 the address in the REG_EQUIV note. */
3576 if (!reload_completed
3577 && reg_known_equiv_p[regno]
3578 && GET_CODE (reg_known_value[regno]) == MEM)
3579 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3581 /* If the register does not already cross any calls, then add this
3582 insn to the sched_before_next_call list so that it will still
3583 not cross calls after scheduling. */
3584 if (REG_N_CALLS_CROSSED (regno) == 0)
3585 add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
3592 /* Reading memory. */
3594 rtx pending, pending_mem;
3596 pending = pending_read_insns;
3597 pending_mem = pending_read_mems;
3600 /* If a dependency already exists, don't create a new one. */
3601 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3602 if (read_dependence (XEXP (pending_mem, 0), x))
3603 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3605 pending = XEXP (pending, 1);
3606 pending_mem = XEXP (pending_mem, 1);
3609 pending = pending_write_insns;
3610 pending_mem = pending_write_mems;
3613 /* If a dependency already exists, don't create a new one. */
3614 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3615 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
3617 add_dependence (insn, XEXP (pending, 0), 0);
3619 pending = XEXP (pending, 1);
3620 pending_mem = XEXP (pending_mem, 1);
3623 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3624 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3626 /* Always add these dependencies to pending_reads, since
3627 this insn may be followed by a write. */
3628 add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
3631 /* Take advantage of tail recursion here. */
3632 sched_analyze_2 (XEXP (x, 0), insn);
3636 /* Force pending stores to memory in case a trap handler needs them. */
3638 flush_pending_lists (insn, 1);
3643 case UNSPEC_VOLATILE:
3647 /* Traditional and volatile asm instructions must be considered to use
3648 and clobber all hard registers, all pseudo-registers and all of
3649 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3651 Consider for instance a volatile asm that changes the fpu rounding
3652 mode. An insn should not be moved across this even if it only uses
3653 pseudo-regs because it might give an incorrectly rounded result. */
3654 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
3656 int max_reg = max_reg_num ();
3657 for (i = 0; i < max_reg; i++)
3659 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3660 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3661 reg_last_uses[i] = 0;
3663 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3664 add_dependence (insn, XEXP (u, 0), 0);
3666 for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
3667 add_dependence (insn, XEXP (u, 0), 0);
3669 reg_pending_sets_all = 1;
3671 flush_pending_lists (insn, 0);
3674 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3675 We can not just fall through here since then we would be confused
3676 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3677 traditional asms unlike their normal usage. */
3679 if (code == ASM_OPERANDS)
3681 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3682 sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
3692 /* These both read and modify the result. We must handle them as writes
3693 to get proper dependencies for following instructions. We must handle
3694 them as reads to get proper dependencies from this to previous
3695 instructions. Thus we need to pass them to both sched_analyze_1
3696 and sched_analyze_2. We must call sched_analyze_2 first in order
3697 to get the proper antecedent for the read. */
3698 sched_analyze_2 (XEXP (x, 0), insn);
3699 sched_analyze_1 (x, insn);
3706 /* Other cases: walk the insn. */
3707 fmt = GET_RTX_FORMAT (code);
3708 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3711 sched_analyze_2 (XEXP (x, i), insn);
3712 else if (fmt[i] == 'E')
3713 for (j = 0; j < XVECLEN (x, i); j++)
3714 sched_analyze_2 (XVECEXP (x, i, j), insn);
3718 /* Analyze an INSN with pattern X to find all dependencies. */
3721 sched_analyze_insn (x, insn, loop_notes)
3725 register RTX_CODE code = GET_CODE (x);
3727 int maxreg = max_reg_num ();
3730 if (code == SET || code == CLOBBER)
3731 sched_analyze_1 (x, insn);
3732 else if (code == PARALLEL)
3735 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3737 code = GET_CODE (XVECEXP (x, 0, i));
3738 if (code == SET || code == CLOBBER)
3739 sched_analyze_1 (XVECEXP (x, 0, i), insn);
3741 sched_analyze_2 (XVECEXP (x, 0, i), insn);
3745 sched_analyze_2 (x, insn);
3747 /* Mark registers CLOBBERED or used by called function. */
3748 if (GET_CODE (insn) == CALL_INSN)
3749 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3751 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3752 sched_analyze_1 (XEXP (link, 0), insn);
3754 sched_analyze_2 (XEXP (link, 0), insn);
3757 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3758 block, then we must be sure that no instructions are scheduled across it.
3759 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3760 become incorrect. */
3764 int max_reg = max_reg_num ();
3765 int schedule_barrier_found = 0;
3768 /* Update loop_notes with any notes from this insn. Also determine
3769 if any of the notes on the list correspond to instruction scheduling
3770 barriers (loop, eh & setjmp notes, but not range notes. */
3772 while (XEXP (link, 1))
3774 if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
3775 || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
3776 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
3777 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END
3778 || INTVAL (XEXP (link, 0)) == NOTE_INSN_SETJMP)
3779 schedule_barrier_found = 1;
3781 link = XEXP (link, 1);
3783 XEXP (link, 1) = REG_NOTES (insn);
3784 REG_NOTES (insn) = loop_notes;
3786 /* Add dependencies if a scheduling barrier was found. */
3787 if (schedule_barrier_found)
3789 for (i = 0; i < max_reg; i++)
3792 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3793 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3794 reg_last_uses[i] = 0;
3796 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3797 add_dependence (insn, XEXP (u, 0), 0);
3799 for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
3800 add_dependence (insn, XEXP (u, 0), 0);
3802 reg_pending_sets_all = 1;
3804 flush_pending_lists (insn, 0);
3809 /* Accumulate clobbers until the next set so that it will be output dependant
3810 on all of them. At the next set we can clear the clobber list, since
3811 subsequent sets will be output dependant on it. */
3812 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
3814 free_list (®_last_sets[i], &unused_insn_list);
3815 free_list (®_last_clobbers[i],
3818 = alloc_INSN_LIST (insn, NULL_RTX);
3820 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
3822 reg_last_clobbers[i]
3823 = alloc_INSN_LIST (insn, reg_last_clobbers[i]);
3825 CLEAR_REG_SET (reg_pending_sets);
3826 CLEAR_REG_SET (reg_pending_clobbers);
3828 if (reg_pending_sets_all)
3830 for (i = 0; i < maxreg; i++)
3832 free_list (®_last_sets[i], &unused_insn_list);
3833 reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3836 reg_pending_sets_all = 0;
3839 /* Handle function calls and function returns created by the epilogue
3841 if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
3846 /* When scheduling instructions, we make sure calls don't lose their
3847 accompanying USE insns by depending them one on another in order.
3849 Also, we must do the same thing for returns created by the epilogue
3850 threading code. Note this code works only in this special case,
3851 because other passes make no guarantee that they will never emit
3852 an instruction between a USE and a RETURN. There is such a guarantee
3853 for USE instructions immediately before a call. */
3855 prev_dep_insn = insn;
3856 dep_insn = PREV_INSN (insn);
3857 while (GET_CODE (dep_insn) == INSN
3858 && GET_CODE (PATTERN (dep_insn)) == USE
3859 && GET_CODE (XEXP (PATTERN (dep_insn), 0)) == REG)
3861 SCHED_GROUP_P (prev_dep_insn) = 1;
3863 /* Make a copy of all dependencies on dep_insn, and add to insn.
3864 This is so that all of the dependencies will apply to the
3867 for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
3868 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3870 prev_dep_insn = dep_insn;
3871 dep_insn = PREV_INSN (dep_insn);
3876 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3877 for every dependency. */
3880 sched_analyze (head, tail)
3887 for (insn = head;; insn = NEXT_INSN (insn))
3889 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
3891 /* Make each JUMP_INSN a scheduling barrier for memory references. */
3892 if (GET_CODE (insn) == JUMP_INSN)
3893 last_pending_memory_flush
3894 = alloc_INSN_LIST (insn, last_pending_memory_flush);
3895 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3898 else if (GET_CODE (insn) == CALL_INSN)
3903 CANT_MOVE (insn) = 1;
3905 /* Any instruction using a hard register which may get clobbered
3906 by a call needs to be marked as dependent on this call.
3907 This prevents a use of a hard return reg from being moved
3908 past a void call (i.e. it does not explicitly set the hard
3911 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3912 all registers, not just hard registers, may be clobbered by this
3915 /* Insn, being a CALL_INSN, magically depends on
3916 `last_function_call' already. */
3918 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
3919 && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
3921 int max_reg = max_reg_num ();
3922 for (i = 0; i < max_reg; i++)
3924 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3925 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3927 reg_last_uses[i] = 0;
3929 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3930 add_dependence (insn, XEXP (u, 0), 0);
3932 for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
3933 add_dependence (insn, XEXP (u, 0), 0);
3935 reg_pending_sets_all = 1;
3937 /* Add a pair of fake REG_NOTE which we will later
3938 convert back into a NOTE_INSN_SETJMP note. See
3939 reemit_notes for why we use a pair of NOTEs. */
3940 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3943 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3944 GEN_INT (NOTE_INSN_SETJMP),
3949 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3950 if (call_used_regs[i] || global_regs[i])
3952 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3953 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3954 reg_last_uses[i] = 0;
3956 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3957 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3960 for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
3961 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3963 SET_REGNO_REG_SET (reg_pending_sets, i);
3967 /* For each insn which shouldn't cross a call, add a dependence
3968 between that insn and this call insn. */
3969 x = LOG_LINKS (sched_before_next_call);
3972 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
3975 LOG_LINKS (sched_before_next_call) = 0;
3977 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3980 /* In the absence of interprocedural alias analysis, we must flush
3981 all pending reads and writes, and start new dependencies starting
3982 from here. But only flush writes for constant calls (which may
3983 be passed a pointer to something we haven't written yet). */
3984 flush_pending_lists (insn, CONST_CALL_P (insn));
3986 /* Depend this function call (actually, the user of this
3987 function call) on all hard register clobberage. */
3989 /* last_function_call is now a list of insns */
3990 free_list(&last_function_call, &unused_insn_list);
3991 last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3994 /* See comments on reemit_notes as to why we do this. */
3995 /* ??? Actually, the reemit_notes just say what is done, not why. */
3997 else if (GET_CODE (insn) == NOTE
3998 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_START
3999 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END))
4001 loop_notes = alloc_EXPR_LIST (REG_DEAD, NOTE_RANGE_INFO (insn),
4003 loop_notes = alloc_EXPR_LIST (REG_DEAD,
4004 GEN_INT (NOTE_LINE_NUMBER (insn)),
4007 else if (GET_CODE (insn) == NOTE
4008 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
4009 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
4010 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
4011 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
4012 || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
4013 && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
4015 loop_notes = alloc_EXPR_LIST (REG_DEAD,
4016 GEN_INT (NOTE_BLOCK_NUMBER (insn)),
4018 loop_notes = alloc_EXPR_LIST (REG_DEAD,
4019 GEN_INT (NOTE_LINE_NUMBER (insn)),
4021 CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
4030 /* Called when we see a set of a register. If death is true, then we are
4031 scanning backwards. Mark that register as unborn. If nobody says
4032 otherwise, that is how things will remain. If death is false, then we
4033 are scanning forwards. Mark that register as being born. */
4036 sched_note_set (x, death)
4041 register rtx reg = SET_DEST (x);
4047 if (GET_CODE (reg) == PARALLEL
4048 && GET_MODE (reg) == BLKmode)
4051 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
4052 sched_note_set (XVECEXP (reg, 0, i), death);
4056 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
4057 || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
4059 /* Must treat modification of just one hardware register of a multi-reg
4060 value or just a byte field of a register exactly the same way that
4061 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
4062 does not kill the entire register. */
4063 if (GET_CODE (reg) != SUBREG
4064 || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
4067 reg = SUBREG_REG (reg);
4070 if (GET_CODE (reg) != REG)
4073 /* Global registers are always live, so the code below does not apply
4076 regno = REGNO (reg);
4077 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
4081 /* If we only set part of the register, then this set does not
4086 /* Try killing this register. */
4087 if (regno < FIRST_PSEUDO_REGISTER)
4089 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
4092 CLEAR_REGNO_REG_SET (bb_live_regs, regno + j);
4097 /* Recompute REG_BASIC_BLOCK as we update all the other
4098 dataflow information. */
4099 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
4100 sched_reg_basic_block[regno] = current_block_num;
4101 else if (sched_reg_basic_block[regno] != current_block_num)
4102 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
4104 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
4109 /* Make the register live again. */
4110 if (regno < FIRST_PSEUDO_REGISTER)
4112 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
4115 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4120 SET_REGNO_REG_SET (bb_live_regs, regno);
4126 /* Macros and functions for keeping the priority queue sorted, and
4127 dealing with queueing and dequeueing of instructions. */
4129 #define SCHED_SORT(READY, N_READY) \
4130 do { if ((N_READY) == 2) \
4131 swap_sort (READY, N_READY); \
4132 else if ((N_READY) > 2) \
4133 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4136 /* Returns a positive value if x is preferred; returns a negative value if
4137 y is preferred. Should never return 0, since that will make the sort
4141 rank_for_schedule (x, y)
4142 const GENERIC_PTR x;
4143 const GENERIC_PTR y;
4145 rtx tmp = *(rtx *)y;
4146 rtx tmp2 = *(rtx *)x;
4148 int tmp_class, tmp2_class, depend_count1, depend_count2;
4149 int val, priority_val, spec_val, prob_val, weight_val;
4152 /* prefer insn with higher priority */
4153 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
4155 return priority_val;
4157 /* prefer an insn with smaller contribution to registers-pressure */
4158 if (!reload_completed &&
4159 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
4160 return (weight_val);
4162 /* some comparison make sense in interblock scheduling only */
4163 if (INSN_BB (tmp) != INSN_BB (tmp2))
4165 /* prefer an inblock motion on an interblock motion */
4166 if ((INSN_BB (tmp2) == target_bb) && (INSN_BB (tmp) != target_bb))
4168 if ((INSN_BB (tmp) == target_bb) && (INSN_BB (tmp2) != target_bb))
4171 /* prefer a useful motion on a speculative one */
4172 if ((spec_val = IS_SPECULATIVE_INSN (tmp) - IS_SPECULATIVE_INSN (tmp2)))
4175 /* prefer a more probable (speculative) insn */
4176 prob_val = INSN_PROBABILITY (tmp2) - INSN_PROBABILITY (tmp);
4181 /* compare insns based on their relation to the last-scheduled-insn */
4182 if (last_scheduled_insn)
4184 /* Classify the instructions into three classes:
4185 1) Data dependent on last schedule insn.
4186 2) Anti/Output dependent on last scheduled insn.
4187 3) Independent of last scheduled insn, or has latency of one.
4188 Choose the insn from the highest numbered class if different. */
4189 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
4190 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
4192 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4197 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
4198 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
4200 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4205 if ((val = tmp2_class - tmp_class))
4209 /* Prefer the insn which has more later insns that depend on it.
4210 This gives the scheduler more freedom when scheduling later
4211 instructions at the expense of added register pressure. */
4213 for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
4217 for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
4220 val = depend_count2 - depend_count1;
4224 /* If insns are equally good, sort by INSN_LUID (original insn order),
4225 so that we make the sort stable. This minimizes instruction movement,
4226 thus minimizing sched's effect on debugging and cross-jumping. */
4227 return INSN_LUID (tmp) - INSN_LUID (tmp2);
4230 /* Resort the array A in which only element at index N may be out of order. */
4232 HAIFA_INLINE static void
4237 rtx insn = a[n - 1];
4240 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
4248 static int max_priority;
4250 /* Add INSN to the insn queue so that it can be executed at least
4251 N_CYCLES after the currently executing insn. Preserve insns
4252 chain for debugging purposes. */
4254 HAIFA_INLINE static void
4255 queue_insn (insn, n_cycles)
4259 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
4260 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
4261 insn_queue[next_q] = link;
4264 if (sched_verbose >= 2)
4266 fprintf (dump, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn));
4268 if (INSN_BB (insn) != target_bb)
4269 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
4271 fprintf (dump, "queued for %d cycles.\n", n_cycles);
4276 /* Return nonzero if PAT is the pattern of an insn which makes a
4279 HAIFA_INLINE static int
4280 birthing_insn_p (pat)
4285 if (reload_completed == 1)
4288 if (GET_CODE (pat) == SET
4289 && (GET_CODE (SET_DEST (pat)) == REG
4290 || (GET_CODE (SET_DEST (pat)) == PARALLEL
4291 && GET_MODE (SET_DEST (pat)) == BLKmode)))
4293 rtx dest = SET_DEST (pat);
4296 /* It would be more accurate to use refers_to_regno_p or
4297 reg_mentioned_p to determine when the dest is not live before this
4299 if (GET_CODE (dest) == REG)
4302 if (REGNO_REG_SET_P (bb_live_regs, i))
4303 return (REG_N_SETS (i) == 1);
4307 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
4309 int regno = REGNO (SET_DEST (XVECEXP (dest, 0, i)));
4310 if (REGNO_REG_SET_P (bb_live_regs, regno))
4311 return (REG_N_SETS (regno) == 1);
4316 if (GET_CODE (pat) == PARALLEL)
4318 for (j = 0; j < XVECLEN (pat, 0); j++)
4319 if (birthing_insn_p (XVECEXP (pat, 0, j)))
4325 /* PREV is an insn that is ready to execute. Adjust its priority if that
4326 will help shorten register lifetimes. */
4328 HAIFA_INLINE static void
4329 adjust_priority (prev)
4332 /* Trying to shorten register lives after reload has completed
4333 is useless and wrong. It gives inaccurate schedules. */
4334 if (reload_completed == 0)
4339 /* ??? This code has no effect, because REG_DEAD notes are removed
4340 before we ever get here. */
4341 for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
4342 if (REG_NOTE_KIND (note) == REG_DEAD)
4345 /* Defer scheduling insns which kill registers, since that
4346 shortens register lives. Prefer scheduling insns which
4347 make registers live for the same reason. */
4351 INSN_PRIORITY (prev) >>= 3;
4354 INSN_PRIORITY (prev) >>= 2;
4358 INSN_PRIORITY (prev) >>= 1;
4361 if (birthing_insn_p (PATTERN (prev)))
4363 int max = max_priority;
4365 if (max > INSN_PRIORITY (prev))
4366 INSN_PRIORITY (prev) = max;
4370 #ifdef ADJUST_PRIORITY
4371 ADJUST_PRIORITY (prev);
4376 /* Clock at which the previous instruction was issued. */
4377 static int last_clock_var;
4379 /* INSN is the "currently executing insn". Launch each insn which was
4380 waiting on INSN. READY is a vector of insns which are ready to fire.
4381 N_READY is the number of elements in READY. CLOCK is the current
4385 schedule_insn (insn, ready, n_ready, clock)
4394 unit = insn_unit (insn);
4396 if (sched_verbose >= 2)
4398 fprintf (dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ", INSN_UID (insn));
4399 insn_print_units (insn);
4400 fprintf (dump, "\n");
4403 if (sched_verbose && unit == -1)
4404 visualize_no_unit (insn);
4406 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
4407 schedule_unit (unit, insn, clock);
4409 if (INSN_DEPEND (insn) == 0)
4412 /* This is used by the function adjust_priority above. */
4414 max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
4416 max_priority = INSN_PRIORITY (insn);
4418 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
4420 rtx next = XEXP (link, 0);
4421 int cost = insn_cost (insn, link, next);
4423 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
4425 if ((INSN_DEP_COUNT (next) -= 1) == 0)
4427 int effective_cost = INSN_TICK (next) - clock;
4429 /* For speculative insns, before inserting to ready/queue,
4430 check live, exception-free, and issue-delay */
4431 if (INSN_BB (next) != target_bb
4432 && (!IS_VALID (INSN_BB (next))
4434 || (IS_SPECULATIVE_INSN (next)
4435 && (insn_issue_delay (next) > 3
4436 || !check_live (next, INSN_BB (next))
4437 || !is_exception_free (next, INSN_BB (next), target_bb)))))
4440 if (sched_verbose >= 2)
4442 fprintf (dump, ";;\t\tdependences resolved: insn %d ", INSN_UID (next));
4444 if (current_nr_blocks > 1 && INSN_BB (next) != target_bb)
4445 fprintf (dump, "/b%d ", INSN_BLOCK (next));
4447 if (effective_cost <= 1)
4448 fprintf (dump, "into ready\n");
4450 fprintf (dump, "into queue with cost=%d\n", effective_cost);
4453 /* Adjust the priority of NEXT and either put it on the ready
4454 list or queue it. */
4455 adjust_priority (next);
4456 if (effective_cost <= 1)
4457 ready[n_ready++] = next;
4459 queue_insn (next, effective_cost);
4463 /* Annotate the instruction with issue information -- TImode
4464 indicates that the instruction is expected not to be able
4465 to issue on the same cycle as the previous insn. A machine
4466 may use this information to decide how the instruction should
4468 if (reload_completed && issue_rate > 1)
4470 PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
4471 last_clock_var = clock;
4478 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4482 create_reg_dead_note (reg, insn)
4487 /* The number of registers killed after scheduling must be the same as the
4488 number of registers killed before scheduling. The number of REG_DEAD
4489 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4490 might become one DImode hard register REG_DEAD note, but the number of
4491 registers killed will be conserved.
4493 We carefully remove REG_DEAD notes from the dead_notes list, so that
4494 there will be none left at the end. If we run out early, then there
4495 is a bug somewhere in flow, combine and/or sched. */
4497 if (dead_notes == 0)
4499 if (current_nr_blocks <= 1)
4502 link = alloc_EXPR_LIST (REG_DEAD, NULL_RTX, NULL_RTX);
4506 /* Number of regs killed by REG. */
4507 int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
4508 : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
4509 /* Number of regs killed by REG_DEAD notes taken off the list. */
4513 reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4514 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4515 GET_MODE (XEXP (link, 0))));
4516 while (reg_note_regs < regs_killed)
4518 link = XEXP (link, 1);
4520 /* LINK might be zero if we killed more registers after scheduling
4521 than before, and the last hard register we kill is actually
4524 This is normal for interblock scheduling, so deal with it in
4525 that case, else abort. */
4526 if (link == NULL_RTX && current_nr_blocks <= 1)
4528 else if (link == NULL_RTX)
4529 link = alloc_EXPR_LIST (REG_DEAD, gen_rtx_REG (word_mode, 0),
4532 reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4533 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4534 GET_MODE (XEXP (link, 0))));
4536 dead_notes = XEXP (link, 1);
4538 /* If we took too many regs kills off, put the extra ones back. */
4539 while (reg_note_regs > regs_killed)
4541 rtx temp_reg, temp_link;
4543 temp_reg = gen_rtx_REG (word_mode, 0);
4544 temp_link = alloc_EXPR_LIST (REG_DEAD, temp_reg, dead_notes);
4545 dead_notes = temp_link;
4550 XEXP (link, 0) = reg;
4551 XEXP (link, 1) = REG_NOTES (insn);
4552 REG_NOTES (insn) = link;
4555 /* Subroutine on attach_deaths_insn--handles the recursive search
4556 through INSN. If SET_P is true, then x is being modified by the insn. */
4559 attach_deaths (x, insn, set_p)
4566 register enum rtx_code code;
4572 code = GET_CODE (x);
4584 /* Get rid of the easy cases first. */
4589 /* If the register dies in this insn, queue that note, and mark
4590 this register as needing to die. */
4591 /* This code is very similar to mark_used_1 (if set_p is false)
4592 and mark_set_1 (if set_p is true) in flow.c. */
4602 all_needed = some_needed = REGNO_REG_SET_P (old_live_regs, regno);
4603 if (regno < FIRST_PSEUDO_REGISTER)
4607 n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4610 int needed = (REGNO_REG_SET_P (old_live_regs, regno + n));
4611 some_needed |= needed;
4612 all_needed &= needed;
4616 /* If it wasn't live before we started, then add a REG_DEAD note.
4617 We must check the previous lifetime info not the current info,
4618 because we may have to execute this code several times, e.g.
4619 once for a clobber (which doesn't add a note) and later
4620 for a use (which does add a note).
4622 Always make the register live. We must do this even if it was
4623 live before, because this may be an insn which sets and uses
4624 the same register, in which case the register has already been
4625 killed, so we must make it live again.
4627 Global registers are always live, and should never have a REG_DEAD
4628 note added for them, so none of the code below applies to them. */
4630 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
4632 /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
4633 STACK_POINTER_REGNUM, since these are always considered to be
4634 live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
4635 if (regno != FRAME_POINTER_REGNUM
4636 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4637 && ! (regno == HARD_FRAME_POINTER_REGNUM)
4639 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4640 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
4642 && regno != STACK_POINTER_REGNUM)
4644 if (! all_needed && ! dead_or_set_p (insn, x))
4646 /* Check for the case where the register dying partially
4647 overlaps the register set by this insn. */
4648 if (regno < FIRST_PSEUDO_REGISTER
4649 && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
4651 int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4653 some_needed |= dead_or_set_regno_p (insn, regno + n);
4656 /* If none of the words in X is needed, make a REG_DEAD
4657 note. Otherwise, we must make partial REG_DEAD
4660 create_reg_dead_note (x, insn);
4665 /* Don't make a REG_DEAD note for a part of a
4666 register that is set in the insn. */
4667 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
4669 if (! REGNO_REG_SET_P (old_live_regs, regno+i)
4670 && ! dead_or_set_regno_p (insn, regno + i))
4671 create_reg_dead_note (gen_rtx_REG (reg_raw_mode[regno + i],
4678 if (regno < FIRST_PSEUDO_REGISTER)
4680 int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
4683 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4688 /* Recompute REG_BASIC_BLOCK as we update all the other
4689 dataflow information. */
4690 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
4691 sched_reg_basic_block[regno] = current_block_num;
4692 else if (sched_reg_basic_block[regno] != current_block_num)
4693 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
4695 SET_REGNO_REG_SET (bb_live_regs, regno);
4702 /* Handle tail-recursive case. */
4703 attach_deaths (XEXP (x, 0), insn, 0);
4707 attach_deaths (SUBREG_REG (x), insn,
4708 set_p && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4710 || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4711 == GET_MODE_SIZE (GET_MODE ((x))))));
4714 case STRICT_LOW_PART:
4715 attach_deaths (XEXP (x, 0), insn, 0);
4720 attach_deaths (XEXP (x, 0), insn, 0);
4721 attach_deaths (XEXP (x, 1), insn, 0);
4722 attach_deaths (XEXP (x, 2), insn, 0);
4727 && GET_MODE (x) == BLKmode)
4729 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4730 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
4736 /* Other cases: walk the insn. */
4737 fmt = GET_RTX_FORMAT (code);
4738 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4741 attach_deaths (XEXP (x, i), insn, 0);
4742 else if (fmt[i] == 'E')
4743 for (j = 0; j < XVECLEN (x, i); j++)
4744 attach_deaths (XVECEXP (x, i, j), insn, 0);
4749 /* After INSN has executed, add register death notes for each register
4750 that is dead after INSN. */
4753 attach_deaths_insn (insn)
4756 rtx x = PATTERN (insn);
4757 register RTX_CODE code = GET_CODE (x);
4762 attach_deaths (SET_SRC (x), insn, 0);
4764 /* A register might die here even if it is the destination, e.g.
4765 it is the target of a volatile read and is otherwise unused.
4766 Hence we must always call attach_deaths for the SET_DEST. */
4767 attach_deaths (SET_DEST (x), insn, 1);
4769 else if (code == PARALLEL)
4772 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4774 code = GET_CODE (XVECEXP (x, 0, i));
4777 attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
4779 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
4781 /* Flow does not add REG_DEAD notes to registers that die in
4782 clobbers, so we can't either. */
4783 else if (code != CLOBBER)
4784 attach_deaths (XVECEXP (x, 0, i), insn, 0);
4787 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4788 MEM being clobbered, just like flow. */
4789 else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == MEM)
4790 attach_deaths (XEXP (XEXP (x, 0), 0), insn, 0);
4791 /* Otherwise don't add a death note to things being clobbered. */
4792 else if (code != CLOBBER)
4793 attach_deaths (x, insn, 0);
4795 /* Make death notes for things used in the called function. */
4796 if (GET_CODE (insn) == CALL_INSN)
4797 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
4798 attach_deaths (XEXP (XEXP (link, 0), 0), insn,
4799 GET_CODE (XEXP (link, 0)) == CLOBBER);
4802 /* functions for handlnig of notes */
4804 /* Delete notes beginning with INSN and put them in the chain
4805 of notes ended by NOTE_LIST.
4806 Returns the insn following the notes. */
4809 unlink_other_notes (insn, tail)
4812 rtx prev = PREV_INSN (insn);
4814 while (insn != tail && GET_CODE (insn) == NOTE)
4816 rtx next = NEXT_INSN (insn);
4817 /* Delete the note from its current position. */
4819 NEXT_INSN (prev) = next;
4821 PREV_INSN (next) = prev;
4823 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4824 immediately after the call they follow. We use a fake
4825 (REG_DEAD (const_int -1)) note to remember them.
4826 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4827 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
4828 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
4829 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
4830 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_START
4831 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
4832 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
4833 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
4835 /* Insert the note at the end of the notes list. */
4836 PREV_INSN (insn) = note_list;
4838 NEXT_INSN (note_list) = insn;
4847 /* Delete line notes beginning with INSN. Record line-number notes so
4848 they can be reused. Returns the insn following the notes. */
4851 unlink_line_notes (insn, tail)
4854 rtx prev = PREV_INSN (insn);
4856 while (insn != tail && GET_CODE (insn) == NOTE)
4858 rtx next = NEXT_INSN (insn);
4860 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
4862 /* Delete the note from its current position. */
4864 NEXT_INSN (prev) = next;
4866 PREV_INSN (next) = prev;
4868 /* Record line-number notes so they can be reused. */
4869 LINE_NOTE (insn) = insn;
4879 /* Return the head and tail pointers of BB. */
4881 HAIFA_INLINE static void
4882 get_block_head_tail (bb, headp, tailp)
4892 b = BB_TO_BLOCK (bb);
4894 /* HEAD and TAIL delimit the basic block being scheduled. */
4895 head = BLOCK_HEAD (b);
4896 tail = BLOCK_END (b);
4898 /* Don't include any notes or labels at the beginning of the
4899 basic block, or notes at the ends of basic blocks. */
4900 while (head != tail)
4902 if (GET_CODE (head) == NOTE)
4903 head = NEXT_INSN (head);
4904 else if (GET_CODE (tail) == NOTE)
4905 tail = PREV_INSN (tail);
4906 else if (GET_CODE (head) == CODE_LABEL)
4907 head = NEXT_INSN (head);
4916 /* Delete line notes from bb. Save them so they can be later restored
4917 (in restore_line_notes ()). */
4928 get_block_head_tail (bb, &head, &tail);
4931 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4934 next_tail = NEXT_INSN (tail);
4935 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4939 /* Farm out notes, and maybe save them in NOTE_LIST.
4940 This is needed to keep the debugger from
4941 getting completely deranged. */
4942 if (GET_CODE (insn) == NOTE)
4945 insn = unlink_line_notes (insn, next_tail);
4951 if (insn == next_tail)
4957 /* Save line number notes for each insn in bb. */
4960 save_line_notes (bb)
4966 /* We must use the true line number for the first insn in the block
4967 that was computed and saved at the start of this pass. We can't
4968 use the current line number, because scheduling of the previous
4969 block may have changed the current line number. */
4971 rtx line = line_note_head[BB_TO_BLOCK (bb)];
4974 get_block_head_tail (bb, &head, &tail);
4975 next_tail = NEXT_INSN (tail);
4977 for (insn = BLOCK_HEAD (BB_TO_BLOCK (bb));
4979 insn = NEXT_INSN (insn))
4980 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4983 LINE_NOTE (insn) = line;
4987 /* After bb was scheduled, insert line notes into the insns list. */
4990 restore_line_notes (bb)
4993 rtx line, note, prev, new;
4994 int added_notes = 0;
4996 rtx head, next_tail, insn;
4998 b = BB_TO_BLOCK (bb);
5000 head = BLOCK_HEAD (b);
5001 next_tail = NEXT_INSN (BLOCK_END (b));
5003 /* Determine the current line-number. We want to know the current
5004 line number of the first insn of the block here, in case it is
5005 different from the true line number that was saved earlier. If
5006 different, then we need a line number note before the first insn
5007 of this block. If it happens to be the same, then we don't want to
5008 emit another line number note here. */
5009 for (line = head; line; line = PREV_INSN (line))
5010 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
5013 /* Walk the insns keeping track of the current line-number and inserting
5014 the line-number notes as needed. */
5015 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5016 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
5018 /* This used to emit line number notes before every non-deleted note.
5019 However, this confuses a debugger, because line notes not separated
5020 by real instructions all end up at the same address. I can find no
5021 use for line number notes before other notes, so none are emitted. */
5022 else if (GET_CODE (insn) != NOTE
5023 && (note = LINE_NOTE (insn)) != 0
5026 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
5027 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
5030 prev = PREV_INSN (insn);
5031 if (LINE_NOTE (note))
5033 /* Re-use the original line-number note. */
5034 LINE_NOTE (note) = 0;
5035 PREV_INSN (note) = prev;
5036 NEXT_INSN (prev) = note;
5037 PREV_INSN (insn) = note;
5038 NEXT_INSN (note) = insn;
5043 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
5044 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
5045 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
5048 if (sched_verbose && added_notes)
5049 fprintf (dump, ";; added %d line-number notes\n", added_notes);
5052 /* After scheduling the function, delete redundant line notes from the
5056 rm_redundant_line_notes ()
5059 rtx insn = get_insns ();
5060 int active_insn = 0;
5063 /* Walk the insns deleting redundant line-number notes. Many of these
5064 are already present. The remainder tend to occur at basic
5065 block boundaries. */
5066 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
5067 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
5069 /* If there are no active insns following, INSN is redundant. */
5070 if (active_insn == 0)
5073 NOTE_SOURCE_FILE (insn) = 0;
5074 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
5076 /* If the line number is unchanged, LINE is redundant. */
5078 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
5079 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
5082 NOTE_SOURCE_FILE (line) = 0;
5083 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
5090 else if (!((GET_CODE (insn) == NOTE
5091 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
5092 || (GET_CODE (insn) == INSN
5093 && (GET_CODE (PATTERN (insn)) == USE
5094 || GET_CODE (PATTERN (insn)) == CLOBBER))))
5097 if (sched_verbose && notes)
5098 fprintf (dump, ";; deleted %d line-number notes\n", notes);
5101 /* Delete notes between head and tail and put them in the chain
5102 of notes ended by NOTE_LIST. */
5105 rm_other_notes (head, tail)
5113 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
5116 next_tail = NEXT_INSN (tail);
5117 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5121 /* Farm out notes, and maybe save them in NOTE_LIST.
5122 This is needed to keep the debugger from
5123 getting completely deranged. */
5124 if (GET_CODE (insn) == NOTE)
5128 insn = unlink_other_notes (insn, next_tail);
5134 if (insn == next_tail)
5140 /* Constructor for `sometimes' data structure. */
5143 new_sometimes_live (regs_sometimes_live, regno, sometimes_max)
5144 struct sometimes *regs_sometimes_live;
5148 register struct sometimes *p;
5150 /* There should never be a register greater than max_regno here. If there
5151 is, it means that a define_split has created a new pseudo reg. This
5152 is not allowed, since there will not be flow info available for any
5153 new register, so catch the error here. */
5154 if (regno >= max_regno)
5157 p = ®s_sometimes_live[sometimes_max];
5160 p->calls_crossed = 0;
5162 return sometimes_max;
5165 /* Count lengths of all regs we are currently tracking,
5166 and find new registers no longer live. */
5169 finish_sometimes_live (regs_sometimes_live, sometimes_max)
5170 struct sometimes *regs_sometimes_live;
5175 for (i = 0; i < sometimes_max; i++)
5177 register struct sometimes *p = ®s_sometimes_live[i];
5178 int regno = p->regno;
5180 sched_reg_live_length[regno] += p->live_length;
5181 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5185 /* functions for computation of registers live/usage info */
5187 /* It is assumed that prior to scheduling BASIC_BLOCK (b)->global_live_at_start
5188 contains the registers that are alive at the entry to b.
5190 Two passes follow: The first pass is performed before the scheduling
5191 of a region. It scans each block of the region forward, computing
5192 the set of registers alive at the end of the basic block and
5193 discard REG_DEAD notes (done by find_pre_sched_live ()).
5195 The second path is invoked after scheduling all region blocks.
5196 It scans each block of the region backward, a block being traversed
5197 only after its succesors in the region. When the set of registers
5198 live at the end of a basic block may be changed by the scheduling
5199 (this may happen for multiple blocks region), it is computed as
5200 the union of the registers live at the start of its succesors.
5201 The last-use information is updated by inserting REG_DEAD notes.
5202 (done by find_post_sched_live ()) */
5204 /* Scan all the insns to be scheduled, removing register death notes.
5205 Register death notes end up in DEAD_NOTES.
5206 Recreate the register life information for the end of this basic
5210 find_pre_sched_live (bb)
5213 rtx insn, next_tail, head, tail;
5214 int b = BB_TO_BLOCK (bb);
5216 get_block_head_tail (bb, &head, &tail);
5217 COPY_REG_SET (bb_live_regs, BASIC_BLOCK (b)->global_live_at_start);
5218 next_tail = NEXT_INSN (tail);
5220 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5222 rtx prev, next, link;
5225 /* Handle register life information. */
5226 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
5228 /* See if the register gets born here. */
5229 /* We must check for registers being born before we check for
5230 registers dying. It is possible for a register to be born and
5231 die in the same insn, e.g. reading from a volatile memory
5232 location into an otherwise unused register. Such a register
5233 must be marked as dead after this insn. */
5234 if (GET_CODE (PATTERN (insn)) == SET
5235 || GET_CODE (PATTERN (insn)) == CLOBBER)
5237 sched_note_set (PATTERN (insn), 0);
5241 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5244 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5245 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5246 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5248 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5252 /* ??? This code is obsolete and should be deleted. It
5253 is harmless though, so we will leave it in for now. */
5254 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5255 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
5256 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5259 /* Each call cobbers (makes live) all call-clobbered regs
5260 that are not global or fixed. Note that the function-value
5261 reg is a call_clobbered reg. */
5262 if (GET_CODE (insn) == CALL_INSN)
5265 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
5266 if (call_used_regs[j] && !global_regs[j]
5269 SET_REGNO_REG_SET (bb_live_regs, j);
5273 /* Need to know what registers this insn kills. */
5274 for (prev = 0, link = REG_NOTES (insn); link; link = next)
5276 next = XEXP (link, 1);
5277 if ((REG_NOTE_KIND (link) == REG_DEAD
5278 || REG_NOTE_KIND (link) == REG_UNUSED)
5279 /* Verify that the REG_NOTE has a valid value. */
5280 && GET_CODE (XEXP (link, 0)) == REG)
5282 register int regno = REGNO (XEXP (link, 0));
5286 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5288 if (REG_NOTE_KIND (link) == REG_DEAD)
5291 XEXP (prev, 1) = next;
5293 REG_NOTES (insn) = next;
5294 XEXP (link, 1) = dead_notes;
5300 if (regno < FIRST_PSEUDO_REGISTER)
5302 int j = HARD_REGNO_NREGS (regno,
5303 GET_MODE (XEXP (link, 0)));
5306 CLEAR_REGNO_REG_SET (bb_live_regs, regno+j);
5311 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
5319 INSN_REG_WEIGHT (insn) = reg_weight;
5323 /* Update register life and usage information for block bb
5324 after scheduling. Put register dead notes back in the code. */
5327 find_post_sched_live (bb)
5334 rtx head, tail, prev_head, next_tail;
5336 register struct sometimes *regs_sometimes_live;
5338 b = BB_TO_BLOCK (bb);
5340 /* compute live regs at the end of bb as a function of its successors. */
5341 if (current_nr_blocks > 1)
5346 first_edge = e = OUT_EDGES (b);
5347 CLEAR_REG_SET (bb_live_regs);
5354 b_succ = TO_BLOCK (e);
5355 IOR_REG_SET (bb_live_regs,
5356 BASIC_BLOCK (b_succ)->global_live_at_start);
5359 while (e != first_edge);
5362 get_block_head_tail (bb, &head, &tail);
5363 next_tail = NEXT_INSN (tail);
5364 prev_head = PREV_INSN (head);
5366 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, i,
5368 sched_reg_basic_block[i] = REG_BLOCK_GLOBAL;
5371 /* if the block is empty, same regs are alive at its end and its start.
5372 since this is not guaranteed after interblock scheduling, make sure they
5373 are truly identical. */
5374 if (NEXT_INSN (prev_head) == tail
5375 && (GET_RTX_CLASS (GET_CODE (tail)) != 'i'))
5377 if (current_nr_blocks > 1)
5378 COPY_REG_SET (BASIC_BLOCK (b)->global_live_at_start, bb_live_regs);
5383 b = BB_TO_BLOCK (bb);
5384 current_block_num = b;
5386 /* Keep track of register lives. */
5387 old_live_regs = ALLOCA_REG_SET ();
5389 = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
5392 /* initiate "sometimes" data, starting with registers live at end */
5394 COPY_REG_SET (old_live_regs, bb_live_regs);
5395 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, 0, j,
5398 = new_sometimes_live (regs_sometimes_live,
5402 /* scan insns back, computing regs live info */
5403 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
5405 /* First we kill registers set by this insn, and then we
5406 make registers used by this insn live. This is the opposite
5407 order used above because we are traversing the instructions
5410 /* Strictly speaking, we should scan REG_UNUSED notes and make
5411 every register mentioned there live, however, we will just
5412 kill them again immediately below, so there doesn't seem to
5413 be any reason why we bother to do this. */
5415 /* See if this is the last notice we must take of a register. */
5416 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5419 if (GET_CODE (PATTERN (insn)) == SET
5420 || GET_CODE (PATTERN (insn)) == CLOBBER)
5421 sched_note_set (PATTERN (insn), 1);
5422 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5424 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5425 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5426 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5427 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 1);
5430 /* This code keeps life analysis information up to date. */
5431 if (GET_CODE (insn) == CALL_INSN)
5433 register struct sometimes *p;
5435 /* A call kills all call used registers that are not
5436 global or fixed, except for those mentioned in the call
5437 pattern which will be made live again later. */
5438 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5439 if (call_used_regs[i] && ! global_regs[i]
5442 CLEAR_REGNO_REG_SET (bb_live_regs, i);
5445 /* Regs live at the time of a call instruction must not
5446 go in a register clobbered by calls. Record this for
5447 all regs now live. Note that insns which are born or
5448 die in a call do not cross a call, so this must be done
5449 after the killings (above) and before the births
5451 p = regs_sometimes_live;
5452 for (i = 0; i < sometimes_max; i++, p++)
5453 if (REGNO_REG_SET_P (bb_live_regs, p->regno))
5454 p->calls_crossed += 1;
5457 /* Make every register used live, and add REG_DEAD notes for
5458 registers which were not live before we started. */
5459 attach_deaths_insn (insn);
5461 /* Find registers now made live by that instruction. */
5462 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs, old_live_regs, 0, j,
5465 = new_sometimes_live (regs_sometimes_live,
5468 IOR_REG_SET (old_live_regs, bb_live_regs);
5470 /* Count lengths of all regs we are worrying about now,
5471 and handle registers no longer live. */
5473 for (i = 0; i < sometimes_max; i++)
5475 register struct sometimes *p = ®s_sometimes_live[i];
5476 int regno = p->regno;
5478 p->live_length += 1;
5480 if (!REGNO_REG_SET_P (bb_live_regs, regno))
5482 /* This is the end of one of this register's lifetime
5483 segments. Save the lifetime info collected so far,
5484 and clear its bit in the old_live_regs entry. */
5485 sched_reg_live_length[regno] += p->live_length;
5486 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5487 CLEAR_REGNO_REG_SET (old_live_regs, p->regno);
5489 /* Delete the reg_sometimes_live entry for this reg by
5490 copying the last entry over top of it. */
5491 *p = regs_sometimes_live[--sometimes_max];
5492 /* ...and decrement i so that this newly copied entry
5493 will be processed. */
5499 finish_sometimes_live (regs_sometimes_live, sometimes_max);
5501 /* In interblock scheduling, global_live_at_start may have changed. */
5502 if (current_nr_blocks > 1)
5503 COPY_REG_SET (BASIC_BLOCK (b)->global_live_at_start, bb_live_regs);
5506 FREE_REG_SET (old_live_regs);
5507 } /* find_post_sched_live */
5509 /* After scheduling the subroutine, restore information about uses of
5517 if (n_basic_blocks > 0)
5518 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, regno,
5520 sched_reg_basic_block[regno]
5524 for (regno = 0; regno < max_regno; regno++)
5525 if (sched_reg_live_length[regno])
5529 if (REG_LIVE_LENGTH (regno) > sched_reg_live_length[regno])
5531 ";; register %d life shortened from %d to %d\n",
5532 regno, REG_LIVE_LENGTH (regno),
5533 sched_reg_live_length[regno]);
5534 /* Negative values are special; don't overwrite the current
5535 reg_live_length value if it is negative. */
5536 else if (REG_LIVE_LENGTH (regno) < sched_reg_live_length[regno]
5537 && REG_LIVE_LENGTH (regno) >= 0)
5539 ";; register %d life extended from %d to %d\n",
5540 regno, REG_LIVE_LENGTH (regno),
5541 sched_reg_live_length[regno]);
5543 if (!REG_N_CALLS_CROSSED (regno)
5544 && sched_reg_n_calls_crossed[regno])
5546 ";; register %d now crosses calls\n", regno);
5547 else if (REG_N_CALLS_CROSSED (regno)
5548 && !sched_reg_n_calls_crossed[regno]
5549 && REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5551 ";; register %d no longer crosses calls\n", regno);
5553 if (REG_BASIC_BLOCK (regno) != sched_reg_basic_block[regno]
5554 && sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5555 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5557 ";; register %d changed basic block from %d to %d\n",
5558 regno, REG_BASIC_BLOCK(regno),
5559 sched_reg_basic_block[regno]);
5562 /* Negative values are special; don't overwrite the current
5563 reg_live_length value if it is negative. */
5564 if (REG_LIVE_LENGTH (regno) >= 0)
5565 REG_LIVE_LENGTH (regno) = sched_reg_live_length[regno];
5567 if (sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5568 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5569 REG_BASIC_BLOCK(regno) = sched_reg_basic_block[regno];
5571 /* We can't change the value of reg_n_calls_crossed to zero for
5572 pseudos which are live in more than one block.
5574 This is because combine might have made an optimization which
5575 invalidated global_live_at_start and reg_n_calls_crossed,
5576 but it does not update them. If we update reg_n_calls_crossed
5577 here, the two variables are now inconsistent, and this might
5578 confuse the caller-save code into saving a register that doesn't
5579 need to be saved. This is only a problem when we zero calls
5580 crossed for a pseudo live in multiple basic blocks.
5582 Alternatively, we could try to correctly update basic block live
5583 at start here in sched, but that seems complicated.
5585 Note: it is possible that a global register became local, as result
5586 of interblock motion, but will remain marked as a global register. */
5587 if (sched_reg_n_calls_crossed[regno]
5588 || REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5589 REG_N_CALLS_CROSSED (regno) = sched_reg_n_calls_crossed[regno];
5594 /* Scheduling clock, modified in schedule_block() and queue_to_ready () */
5595 static int clock_var;
5597 /* Move insns that became ready to fire from queue to ready list. */
5600 queue_to_ready (ready, n_ready)
5607 q_ptr = NEXT_Q (q_ptr);
5609 /* Add all pending insns that can be scheduled without stalls to the
5611 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
5614 insn = XEXP (link, 0);
5617 if (sched_verbose >= 2)
5618 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5620 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5621 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5623 ready[n_ready++] = insn;
5624 if (sched_verbose >= 2)
5625 fprintf (dump, "moving to ready without stalls\n");
5627 insn_queue[q_ptr] = 0;
5629 /* If there are no ready insns, stall until one is ready and add all
5630 of the pending insns at that point to the ready list. */
5633 register int stalls;
5635 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
5637 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
5639 for (; link; link = XEXP (link, 1))
5641 insn = XEXP (link, 0);
5644 if (sched_verbose >= 2)
5645 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5647 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5648 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5650 ready[n_ready++] = insn;
5651 if (sched_verbose >= 2)
5652 fprintf (dump, "moving to ready with %d stalls\n", stalls);
5654 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
5661 if (sched_verbose && stalls)
5662 visualize_stall_cycles (BB_TO_BLOCK (target_bb), stalls);
5663 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
5664 clock_var += stalls;
5669 /* Print the ready list for debugging purposes. Callable from debugger. */
5672 debug_ready_list (ready, n_ready)
5678 for (i = 0; i < n_ready; i++)
5680 fprintf (dump, " %d", INSN_UID (ready[i]));
5681 if (current_nr_blocks > 1 && INSN_BB (ready[i]) != target_bb)
5682 fprintf (dump, "/b%d", INSN_BLOCK (ready[i]));
5684 fprintf (dump, "\n");
5687 /* Print names of units on which insn can/should execute, for debugging. */
5690 insn_print_units (insn)
5694 int unit = insn_unit (insn);
5697 fprintf (dump, "none");
5699 fprintf (dump, "%s", function_units[unit].name);
5702 fprintf (dump, "[");
5703 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
5706 fprintf (dump, "%s", function_units[i].name);
5708 fprintf (dump, " ");
5710 fprintf (dump, "]");
5714 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5715 of a basic block. If more lines are needed, table is splitted to two.
5716 n_visual_lines is the number of lines printed so far for a block.
5717 visual_tbl contains the block visualization info.
5718 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5719 #define MAX_VISUAL_LINES 100
5724 rtx vis_no_unit[10];
5726 /* Finds units that are in use in this fuction. Required only
5727 for visualization. */
5730 init_target_units ()
5735 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
5737 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5740 unit = insn_unit (insn);
5743 target_units |= ~unit;
5745 target_units |= (1 << unit);
5749 /* Return the length of the visualization table */
5752 get_visual_tbl_length ()
5758 /* compute length of one field in line */
5759 s = (char *) alloca (INSN_LEN + 5);
5760 sprintf (s, " %33s", "uname");
5763 /* compute length of one line */
5766 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5767 if (function_units[unit].bitmask & target_units)
5768 for (i = 0; i < function_units[unit].multiplicity; i++)
5771 n += strlen ("\n") + 2;
5773 /* compute length of visualization string */
5774 return (MAX_VISUAL_LINES * n);
5777 /* Init block visualization debugging info */
5780 init_block_visualization ()
5782 strcpy (visual_tbl, "");
5790 safe_concat (buf, cur, str)
5795 char *end = buf + BUF_LEN - 2; /* leave room for null */
5804 while (cur < end && (c = *str++) != '\0')
5811 /* This recognizes rtx, I classified as expressions. These are always */
5812 /* represent some action on values or results of other expression, */
5813 /* that may be stored in objects representing values. */
5816 print_exp (buf, x, verbose)
5824 char *fun = (char *)0;
5829 for (i = 0; i < 4; i++)
5835 switch (GET_CODE (x))
5838 op[0] = XEXP (x, 0);
5839 if (GET_CODE (XEXP (x, 1)) == CONST_INT
5840 && INTVAL (XEXP (x, 1)) < 0)
5843 op[1] = GEN_INT (-INTVAL (XEXP (x, 1)));
5848 op[1] = XEXP (x, 1);
5852 op[0] = XEXP (x, 0);
5854 op[1] = XEXP (x, 1);
5858 op[0] = XEXP (x, 0);
5860 op[1] = XEXP (x, 1);
5864 op[0] = XEXP (x, 0);
5865 op[1] = XEXP (x, 1);
5869 op[0] = XEXP (x, 0);
5872 op[0] = XEXP (x, 0);
5874 op[1] = XEXP (x, 1);
5877 op[0] = XEXP (x, 0);
5879 op[1] = XEXP (x, 1);
5883 op[0] = XEXP (x, 0);
5884 op[1] = XEXP (x, 1);
5887 op[0] = XEXP (x, 0);
5889 op[1] = XEXP (x, 1);
5893 op[0] = XEXP (x, 0);
5894 op[1] = XEXP (x, 1);
5898 op[0] = XEXP (x, 0);
5899 op[1] = XEXP (x, 1);
5903 op[0] = XEXP (x, 0);
5904 op[1] = XEXP (x, 1);
5908 op[0] = XEXP (x, 0);
5909 op[1] = XEXP (x, 1);
5913 op[0] = XEXP (x, 0);
5914 op[1] = XEXP (x, 1);
5918 op[0] = XEXP (x, 0);
5921 op[0] = XEXP (x, 0);
5923 op[1] = XEXP (x, 1);
5926 op[0] = XEXP (x, 0);
5928 op[1] = XEXP (x, 1);
5931 op[0] = XEXP (x, 0);
5933 op[1] = XEXP (x, 1);
5936 op[0] = XEXP (x, 0);
5938 op[1] = XEXP (x, 1);
5941 op[0] = XEXP (x, 0);
5943 op[1] = XEXP (x, 1);
5946 op[0] = XEXP (x, 0);
5948 op[1] = XEXP (x, 1);
5951 op[0] = XEXP (x, 0);
5953 op[1] = XEXP (x, 1);
5956 op[0] = XEXP (x, 0);
5958 op[1] = XEXP (x, 1);
5962 op[0] = XEXP (x, 0);
5966 op[0] = XEXP (x, 0);
5970 op[0] = XEXP (x, 0);
5973 op[0] = XEXP (x, 0);
5975 op[1] = XEXP (x, 1);
5978 op[0] = XEXP (x, 0);
5980 op[1] = XEXP (x, 1);
5983 op[0] = XEXP (x, 0);
5985 op[1] = XEXP (x, 1);
5989 op[0] = XEXP (x, 0);
5990 op[1] = XEXP (x, 1);
5993 op[0] = XEXP (x, 0);
5995 op[1] = XEXP (x, 1);
5999 op[0] = XEXP (x, 0);
6000 op[1] = XEXP (x, 1);
6003 op[0] = XEXP (x, 0);
6005 op[1] = XEXP (x, 1);
6009 op[0] = XEXP (x, 0);
6010 op[1] = XEXP (x, 1);
6013 op[0] = XEXP (x, 0);
6015 op[1] = XEXP (x, 1);
6019 op[0] = XEXP (x, 0);
6020 op[1] = XEXP (x, 1);
6023 fun = (verbose) ? "sign_extract" : "sxt";
6024 op[0] = XEXP (x, 0);
6025 op[1] = XEXP (x, 1);
6026 op[2] = XEXP (x, 2);
6029 fun = (verbose) ? "zero_extract" : "zxt";
6030 op[0] = XEXP (x, 0);
6031 op[1] = XEXP (x, 1);
6032 op[2] = XEXP (x, 2);
6035 fun = (verbose) ? "sign_extend" : "sxn";
6036 op[0] = XEXP (x, 0);
6039 fun = (verbose) ? "zero_extend" : "zxn";
6040 op[0] = XEXP (x, 0);
6043 fun = (verbose) ? "float_extend" : "fxn";
6044 op[0] = XEXP (x, 0);
6047 fun = (verbose) ? "trunc" : "trn";
6048 op[0] = XEXP (x, 0);
6050 case FLOAT_TRUNCATE:
6051 fun = (verbose) ? "float_trunc" : "ftr";
6052 op[0] = XEXP (x, 0);
6055 fun = (verbose) ? "float" : "flt";
6056 op[0] = XEXP (x, 0);
6058 case UNSIGNED_FLOAT:
6059 fun = (verbose) ? "uns_float" : "ufl";
6060 op[0] = XEXP (x, 0);
6064 op[0] = XEXP (x, 0);
6067 fun = (verbose) ? "uns_fix" : "ufx";
6068 op[0] = XEXP (x, 0);
6072 op[0] = XEXP (x, 0);
6076 op[0] = XEXP (x, 0);
6079 op[0] = XEXP (x, 0);
6083 op[0] = XEXP (x, 0);
6088 op[0] = XEXP (x, 0);
6092 op[1] = XEXP (x, 1);
6097 op[0] = XEXP (x, 0);
6099 op[1] = XEXP (x, 1);
6101 op[2] = XEXP (x, 2);
6106 op[0] = TRAP_CONDITION (x);
6109 case UNSPEC_VOLATILE:
6111 cur = safe_concat (buf, cur, "unspec");
6112 if (GET_CODE (x) == UNSPEC_VOLATILE)
6113 cur = safe_concat (buf, cur, "/v");
6114 cur = safe_concat (buf, cur, "[");
6116 for (i = 0; i < XVECLEN (x, 0); i++)
6118 print_pattern (tmp, XVECEXP (x, 0, i), verbose);
6119 cur = safe_concat (buf, cur, sep);
6120 cur = safe_concat (buf, cur, tmp);
6123 cur = safe_concat (buf, cur, "] ");
6124 sprintf (tmp, "%d", XINT (x, 1));
6125 cur = safe_concat (buf, cur, tmp);
6129 /* if (verbose) debug_rtx (x); */
6130 st[0] = GET_RTX_NAME (GET_CODE (x));
6134 /* Print this as a function? */
6137 cur = safe_concat (buf, cur, fun);
6138 cur = safe_concat (buf, cur, "(");
6141 for (i = 0; i < 4; i++)
6144 cur = safe_concat (buf, cur, st[i]);
6149 cur = safe_concat (buf, cur, ",");
6151 print_value (tmp, op[i], verbose);
6152 cur = safe_concat (buf, cur, tmp);
6157 cur = safe_concat (buf, cur, ")");
6160 /* Prints rtxes, i customly classified as values. They're constants, */
6161 /* registers, labels, symbols and memory accesses. */
6164 print_value (buf, x, verbose)
6172 switch (GET_CODE (x))
6175 sprintf (t, HOST_WIDE_INT_PRINT_HEX, INTVAL (x));
6176 cur = safe_concat (buf, cur, t);
6179 sprintf (t, "<0x%lx,0x%lx>", (long)XWINT (x, 2), (long)XWINT (x, 3));
6180 cur = safe_concat (buf, cur, t);
6183 cur = safe_concat (buf, cur, "\"");
6184 cur = safe_concat (buf, cur, XSTR (x, 0));
6185 cur = safe_concat (buf, cur, "\"");
6188 cur = safe_concat (buf, cur, "`");
6189 cur = safe_concat (buf, cur, XSTR (x, 0));
6190 cur = safe_concat (buf, cur, "'");
6193 sprintf (t, "L%d", INSN_UID (XEXP (x, 0)));
6194 cur = safe_concat (buf, cur, t);
6197 print_value (t, XEXP (x, 0), verbose);
6198 cur = safe_concat (buf, cur, "const(");
6199 cur = safe_concat (buf, cur, t);
6200 cur = safe_concat (buf, cur, ")");
6203 print_value (t, XEXP (x, 0), verbose);
6204 cur = safe_concat (buf, cur, "high(");
6205 cur = safe_concat (buf, cur, t);
6206 cur = safe_concat (buf, cur, ")");
6209 if (REGNO (x) < FIRST_PSEUDO_REGISTER)
6211 int c = reg_names[ REGNO (x) ][0];
6212 if (c >= '0' && c <= '9')
6213 cur = safe_concat (buf, cur, "%");
6215 cur = safe_concat (buf, cur, reg_names[ REGNO (x) ]);
6219 sprintf (t, "r%d", REGNO (x));
6220 cur = safe_concat (buf, cur, t);
6224 print_value (t, SUBREG_REG (x), verbose);
6225 cur = safe_concat (buf, cur, t);
6226 sprintf (t, "#%d", SUBREG_WORD (x));
6227 cur = safe_concat (buf, cur, t);
6230 cur = safe_concat (buf, cur, "scratch");
6233 cur = safe_concat (buf, cur, "cc0");
6236 cur = safe_concat (buf, cur, "pc");
6239 print_value (t, XEXP (x, 0), verbose);
6240 cur = safe_concat (buf, cur, "[");
6241 cur = safe_concat (buf, cur, t);
6242 cur = safe_concat (buf, cur, "]");
6245 print_exp (t, x, verbose);
6246 cur = safe_concat (buf, cur, t);
6251 /* The next step in insn detalization, its pattern recognition */
6254 print_pattern (buf, x, verbose)
6259 char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
6261 switch (GET_CODE (x))
6264 print_value (t1, SET_DEST (x), verbose);
6265 print_value (t2, SET_SRC (x), verbose);
6266 sprintf (buf, "%s=%s", t1, t2);
6269 sprintf (buf, "return");
6272 print_exp (buf, x, verbose);
6275 print_value (t1, XEXP (x, 0), verbose);
6276 sprintf (buf, "clobber %s", t1);
6279 print_value (t1, XEXP (x, 0), verbose);
6280 sprintf (buf, "use %s", t1);
6287 for (i = 0; i < XVECLEN (x, 0); i++)
6289 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6290 sprintf (t3, "%s%s;", t1, t2);
6293 sprintf (buf, "%s}", t1);
6300 sprintf (t1, "%%{");
6301 for (i = 0; i < XVECLEN (x, 0); i++)
6303 print_insn (t2, XVECEXP (x, 0, i), verbose);
6304 sprintf (t3, "%s%s;", t1, t2);
6307 sprintf (buf, "%s%%}", t1);
6311 sprintf (buf, "asm {%s}", XSTR (x, 0));
6316 print_value (buf, XEXP (x, 0), verbose);
6319 print_value (t1, TRAP_CONDITION (x), verbose);
6320 sprintf (buf, "trap_if %s", t1);
6326 sprintf (t1, "unspec{");
6327 for (i = 0; i < XVECLEN (x, 0); i++)
6329 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6330 sprintf (t3, "%s%s;", t1, t2);
6333 sprintf (buf, "%s}", t1);
6336 case UNSPEC_VOLATILE:
6340 sprintf (t1, "unspec/v{");
6341 for (i = 0; i < XVECLEN (x, 0); i++)
6343 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6344 sprintf (t3, "%s%s;", t1, t2);
6347 sprintf (buf, "%s}", t1);
6351 print_value (buf, x, verbose);
6353 } /* print_pattern */
6355 /* This is the main function in rtl visualization mechanism. It
6356 accepts an rtx and tries to recognize it as an insn, then prints it
6357 properly in human readable form, resembling assembler mnemonics. */
6358 /* For every insn it prints its UID and BB the insn belongs */
6359 /* too. (probably the last "option" should be extended somehow, since */
6360 /* it depends now on sched.c inner variables ...) */
6363 print_insn (buf, x, verbose)
6371 switch (GET_CODE (x))
6374 print_pattern (t, PATTERN (x), verbose);
6376 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (x),
6379 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6382 print_pattern (t, PATTERN (x), verbose);
6384 sprintf (buf, "b%d: i% 4d: jump %s", INSN_BB (x),
6387 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6391 if (GET_CODE (x) == PARALLEL)
6393 x = XVECEXP (x, 0, 0);
6394 print_pattern (t, x, verbose);
6397 strcpy (t, "call <...>");
6399 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (insn),
6400 INSN_UID (insn), t);
6402 sprintf (buf, "%-4d %s", INSN_UID (insn), t);
6405 sprintf (buf, "L%d:", INSN_UID (x));
6408 sprintf (buf, "i% 4d: barrier", INSN_UID (x));
6411 if (NOTE_LINE_NUMBER (x) > 0)
6412 sprintf (buf, "%4d note \"%s\" %d", INSN_UID (x),
6413 NOTE_SOURCE_FILE (x), NOTE_LINE_NUMBER (x));
6415 sprintf (buf, "%4d %s", INSN_UID (x),
6416 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x)));
6421 sprintf (buf, "Not an INSN at all\n");
6425 sprintf (buf, "i%-4d <What?>", INSN_UID (x));
6429 /* Print visualization debugging info */
6432 print_block_visualization (b, s)
6439 fprintf (dump, "\n;; ==================== scheduling visualization for block %d %s \n", b, s);
6441 /* Print names of units */
6442 fprintf (dump, ";; %-8s", "clock");
6443 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6444 if (function_units[unit].bitmask & target_units)
6445 for (i = 0; i < function_units[unit].multiplicity; i++)
6446 fprintf (dump, " %-33s", function_units[unit].name);
6447 fprintf (dump, " %-8s\n", "no-unit");
6449 fprintf (dump, ";; %-8s", "=====");
6450 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6451 if (function_units[unit].bitmask & target_units)
6452 for (i = 0; i < function_units[unit].multiplicity; i++)
6453 fprintf (dump, " %-33s", "==============================");
6454 fprintf (dump, " %-8s\n", "=======");
6456 /* Print insns in each cycle */
6457 fprintf (dump, "%s\n", visual_tbl);
6460 /* Print insns in the 'no_unit' column of visualization */
6463 visualize_no_unit (insn)
6466 vis_no_unit[n_vis_no_unit] = insn;
6470 /* Print insns scheduled in clock, for visualization. */
6473 visualize_scheduled_insns (b, clock)
6478 /* if no more room, split table into two */
6479 if (n_visual_lines >= MAX_VISUAL_LINES)
6481 print_block_visualization (b, "(incomplete)");
6482 init_block_visualization ();
6487 sprintf (visual_tbl + strlen (visual_tbl), ";; %-8d", clock);
6488 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6489 if (function_units[unit].bitmask & target_units)
6490 for (i = 0; i < function_units[unit].multiplicity; i++)
6492 int instance = unit + i * FUNCTION_UNITS_SIZE;
6493 rtx insn = unit_last_insn[instance];
6495 /* print insns that still keep the unit busy */
6497 actual_hazard_this_instance (unit, instance, insn, clock, 0))
6500 print_insn (str, insn, 0);
6501 str[INSN_LEN] = '\0';
6502 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", str);
6505 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", "------------------------------");
6508 /* print insns that are not assigned to any unit */
6509 for (i = 0; i < n_vis_no_unit; i++)
6510 sprintf (visual_tbl + strlen (visual_tbl), " %-8d",
6511 INSN_UID (vis_no_unit[i]));
6514 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6517 /* Print stalled cycles */
6520 visualize_stall_cycles (b, stalls)
6525 /* if no more room, split table into two */
6526 if (n_visual_lines >= MAX_VISUAL_LINES)
6528 print_block_visualization (b, "(incomplete)");
6529 init_block_visualization ();
6534 sprintf (visual_tbl + strlen (visual_tbl), ";; ");
6535 for (i = 0; i < stalls; i++)
6536 sprintf (visual_tbl + strlen (visual_tbl), ".");
6537 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6540 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn */
6543 move_insn1 (insn, last)
6546 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
6547 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
6549 NEXT_INSN (insn) = NEXT_INSN (last);
6550 PREV_INSN (NEXT_INSN (last)) = insn;
6552 NEXT_INSN (last) = insn;
6553 PREV_INSN (insn) = last;
6558 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
6559 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
6560 NOTEs. The REG_DEAD note following first one is contains the saved
6561 value for NOTE_BLOCK_NUMBER which is useful for
6562 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
6563 output by the instruction scheduler. Return the new value of LAST. */
6566 reemit_notes (insn, last)
6573 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
6575 if (REG_NOTE_KIND (note) == REG_DEAD
6576 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6578 int note_type = INTVAL (XEXP (note, 0));
6579 if (note_type == NOTE_INSN_SETJMP)
6581 retval = emit_note_after (NOTE_INSN_SETJMP, insn);
6582 CONST_CALL_P (retval) = CONST_CALL_P (note);
6583 remove_note (insn, note);
6584 note = XEXP (note, 1);
6586 else if (note_type == NOTE_INSN_RANGE_START
6587 || note_type == NOTE_INSN_RANGE_END)
6589 last = emit_note_before (note_type, last);
6590 remove_note (insn, note);
6591 note = XEXP (note, 1);
6592 NOTE_RANGE_INFO (last) = XEXP (note, 0);
6596 last = emit_note_before (INTVAL (XEXP (note, 0)), last);
6597 remove_note (insn, note);
6598 note = XEXP (note, 1);
6599 NOTE_BLOCK_NUMBER (last) = INTVAL (XEXP (note, 0));
6601 remove_note (insn, note);
6607 /* Move INSN, and all insns which should be issued before it,
6608 due to SCHED_GROUP_P flag. Reemit notes if needed.
6610 Return the last insn emitted by the scheduler, which is the
6611 return value from the first call to reemit_notes. */
6614 move_insn (insn, last)
6619 /* If INSN has SCHED_GROUP_P set, then issue it and any other
6620 insns with SCHED_GROUP_P set first. */
6621 while (SCHED_GROUP_P (insn))
6623 rtx prev = PREV_INSN (insn);
6625 /* Move a SCHED_GROUP_P insn. */
6626 move_insn1 (insn, last);
6627 /* If this is the first call to reemit_notes, then record
6628 its return value. */
6629 if (retval == NULL_RTX)
6630 retval = reemit_notes (insn, insn);
6632 reemit_notes (insn, insn);
6636 /* Now move the first non SCHED_GROUP_P insn. */
6637 move_insn1 (insn, last);
6639 /* If this is the first call to reemit_notes, then record
6640 its return value. */
6641 if (retval == NULL_RTX)
6642 retval = reemit_notes (insn, insn);
6644 reemit_notes (insn, insn);
6649 /* Return an insn which represents a SCHED_GROUP, which is
6650 the last insn in the group. */
6661 insn = next_nonnote_insn (insn);
6663 while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
6668 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
6669 possibly bringing insns from subsequent blocks in the same region.
6670 Return number of insns scheduled. */
6673 schedule_block (bb, rgn_n_insns)
6677 /* Local variables. */
6684 /* flow block of this bb */
6685 int b = BB_TO_BLOCK (bb);
6687 /* target_n_insns == number of insns in b before scheduling starts.
6688 sched_target_n_insns == how many of b's insns were scheduled.
6689 sched_n_insns == how many insns were scheduled in b */
6690 int target_n_insns = 0;
6691 int sched_target_n_insns = 0;
6692 int sched_n_insns = 0;
6694 #define NEED_NOTHING 0
6699 /* head/tail info for this block */
6706 /* We used to have code to avoid getting parameters moved from hard
6707 argument registers into pseudos.
6709 However, it was removed when it proved to be of marginal benefit
6710 and caused problems because schedule_block and compute_forward_dependences
6711 had different notions of what the "head" insn was. */
6712 get_block_head_tail (bb, &head, &tail);
6714 /* Interblock scheduling could have moved the original head insn from this
6715 block into a proceeding block. This may also cause schedule_block and
6716 compute_forward_dependences to have different notions of what the
6719 If the interblock movement happened to make this block start with
6720 some notes (LOOP, EH or SETJMP) before the first real insn, then
6721 HEAD will have various special notes attached to it which must be
6722 removed so that we don't end up with extra copies of the notes. */
6723 if (GET_RTX_CLASS (GET_CODE (head)) == 'i')
6727 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
6728 if (REG_NOTE_KIND (note) == REG_DEAD
6729 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6730 remove_note (head, note);
6733 next_tail = NEXT_INSN (tail);
6734 prev_head = PREV_INSN (head);
6736 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6737 to schedule this block. */
6739 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6740 return (sched_n_insns);
6745 fprintf (dump, ";; ======================================================\n");
6747 ";; -- basic block %d from %d to %d -- %s reload\n",
6748 b, INSN_UID (BLOCK_HEAD (b)), INSN_UID (BLOCK_END (b)),
6749 (reload_completed ? "after" : "before"));
6750 fprintf (dump, ";; ======================================================\n");
6751 fprintf (dump, "\n");
6753 visual_tbl = (char *) alloca (get_visual_tbl_length ());
6754 init_block_visualization ();
6757 /* remove remaining note insns from the block, save them in
6758 note_list. These notes are restored at the end of
6759 schedule_block (). */
6761 rm_other_notes (head, tail);
6765 /* prepare current target block info */
6766 if (current_nr_blocks > 1)
6768 candidate_table = (candidate *) alloca (current_nr_blocks * sizeof (candidate));
6771 /* ??? It is not clear why bblst_size is computed this way. The original
6772 number was clearly too small as it resulted in compiler failures.
6773 Multiplying by the original number by 2 (to account for update_bbs
6774 members) seems to be a reasonable solution. */
6775 /* ??? Or perhaps there is a bug somewhere else in this file? */
6776 bblst_size = (current_nr_blocks - bb) * rgn_nr_edges * 2;
6777 bblst_table = (int *) alloca (bblst_size * sizeof (int));
6779 bitlst_table_last = 0;
6780 bitlst_table_size = rgn_nr_edges;
6781 bitlst_table = (int *) alloca (rgn_nr_edges * sizeof (int));
6783 compute_trg_info (bb);
6788 /* Allocate the ready list */
6789 ready = (rtx *) alloca ((rgn_n_insns + 1) * sizeof (rtx));
6791 /* Print debugging information. */
6792 if (sched_verbose >= 5)
6793 debug_dependencies ();
6796 /* Initialize ready list with all 'ready' insns in target block.
6797 Count number of insns in the target block being scheduled. */
6799 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6803 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6805 next = NEXT_INSN (insn);
6807 if (INSN_DEP_COUNT (insn) == 0
6808 && (SCHED_GROUP_P (next) == 0 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6809 ready[n_ready++] = insn;
6810 if (!(SCHED_GROUP_P (insn)))
6814 /* Add to ready list all 'ready' insns in valid source blocks.
6815 For speculative insns, check-live, exception-free, and
6817 for (bb_src = bb + 1; bb_src < current_nr_blocks; bb_src++)
6818 if (IS_VALID (bb_src))
6824 get_block_head_tail (bb_src, &head, &tail);
6825 src_next_tail = NEXT_INSN (tail);
6829 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6832 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
6834 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6837 if (!CANT_MOVE (insn)
6838 && (!IS_SPECULATIVE_INSN (insn)
6839 || (insn_issue_delay (insn) <= 3
6840 && check_live (insn, bb_src)
6841 && is_exception_free (insn, bb_src, target_bb))))
6846 next = NEXT_INSN (insn);
6847 if (INSN_DEP_COUNT (insn) == 0
6848 && (SCHED_GROUP_P (next) == 0
6849 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6850 ready[n_ready++] = insn;
6855 #ifdef MD_SCHED_INIT
6856 MD_SCHED_INIT (dump, sched_verbose);
6859 /* no insns scheduled in this block yet */
6860 last_scheduled_insn = 0;
6862 /* Sort the ready list */
6863 SCHED_SORT (ready, n_ready);
6864 #ifdef MD_SCHED_REORDER
6865 MD_SCHED_REORDER (dump, sched_verbose, ready, n_ready);
6868 if (sched_verbose >= 2)
6870 fprintf (dump, ";;\t\tReady list initially: ");
6871 debug_ready_list (ready, n_ready);
6874 /* Q_SIZE is the total number of insns in the queue. */
6879 bzero ((char *) insn_queue, sizeof (insn_queue));
6881 /* We start inserting insns after PREV_HEAD. */
6884 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6885 new_needs = (NEXT_INSN (prev_head) == BLOCK_HEAD (b)
6886 ? NEED_HEAD : NEED_NOTHING);
6887 if (PREV_INSN (next_tail) == BLOCK_END (b))
6888 new_needs |= NEED_TAIL;
6890 /* loop until all the insns in BB are scheduled. */
6891 while (sched_target_n_insns < target_n_insns)
6897 /* Add to the ready list all pending insns that can be issued now.
6898 If there are no ready insns, increment clock until one
6899 is ready and add all pending insns at that point to the ready
6901 n_ready = queue_to_ready (ready, n_ready);
6906 if (sched_verbose >= 2)
6908 fprintf (dump, ";;\t\tReady list after queue_to_ready: ");
6909 debug_ready_list (ready, n_ready);
6912 /* Sort the ready list. */
6913 SCHED_SORT (ready, n_ready);
6914 #ifdef MD_SCHED_REORDER
6915 MD_SCHED_REORDER (dump, sched_verbose, ready, n_ready);
6920 fprintf (dump, "\n;;\tReady list (t =%3d): ", clock_var);
6921 debug_ready_list (ready, n_ready);
6924 /* Issue insns from ready list.
6925 It is important to count down from n_ready, because n_ready may change
6926 as insns are issued. */
6927 can_issue_more = issue_rate;
6928 for (i = n_ready - 1; i >= 0 && can_issue_more; i--)
6930 rtx insn = ready[i];
6931 int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
6935 queue_insn (insn, cost);
6936 ready[i] = ready[--n_ready]; /* remove insn from ready list */
6940 /* an interblock motion? */
6941 if (INSN_BB (insn) != target_bb)
6945 if (IS_SPECULATIVE_INSN (insn))
6948 if (!check_live (insn, INSN_BB (insn)))
6950 /* speculative motion, live check failed, remove
6951 insn from ready list */
6952 ready[i] = ready[--n_ready];
6955 update_live (insn, INSN_BB (insn));
6957 /* for speculative load, mark insns fed by it. */
6958 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
6959 set_spec_fed (insn);
6966 while (SCHED_GROUP_P (temp))
6967 temp = PREV_INSN (temp);
6969 /* Update source block boundaries. */
6970 b1 = INSN_BLOCK (temp);
6971 if (temp == BLOCK_HEAD (b1)
6972 && insn == BLOCK_END (b1))
6974 /* We moved all the insns in the basic block.
6975 Emit a note after the last insn and update the
6976 begin/end boundaries to point to the note. */
6977 emit_note_after (NOTE_INSN_DELETED, insn);
6978 BLOCK_END (b1) = NEXT_INSN (insn);
6979 BLOCK_HEAD (b1) = NEXT_INSN (insn);
6981 else if (insn == BLOCK_END (b1))
6983 /* We took insns from the end of the basic block,
6984 so update the end of block boundary so that it
6985 points to the first insn we did not move. */
6986 BLOCK_END (b1) = PREV_INSN (temp);
6988 else if (temp == BLOCK_HEAD (b1))
6990 /* We took insns from the start of the basic block,
6991 so update the start of block boundary so that
6992 it points to the first insn we did not move. */
6993 BLOCK_HEAD (b1) = NEXT_INSN (insn);
6998 /* in block motion */
6999 sched_target_n_insns++;
7002 last_scheduled_insn = insn;
7003 last = move_insn (insn, last);
7006 #ifdef MD_SCHED_VARIABLE_ISSUE
7007 MD_SCHED_VARIABLE_ISSUE (dump, sched_verbose, insn, can_issue_more);
7012 n_ready = schedule_insn (insn, ready, n_ready, clock_var);
7014 /* remove insn from ready list */
7015 ready[i] = ready[--n_ready];
7017 /* close this block after scheduling its jump */
7018 if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
7026 visualize_scheduled_insns (b, clock_var);
7033 fprintf (dump, ";;\tReady list (final): ");
7034 debug_ready_list (ready, n_ready);
7035 print_block_visualization (b, "");
7038 /* Sanity check -- queue must be empty now. Meaningless if region has
7040 if (current_nr_blocks > 1)
7041 if (!flag_schedule_interblock && q_size != 0)
7044 /* update head/tail boundaries. */
7045 head = NEXT_INSN (prev_head);
7048 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
7049 previously found among the insns. Insert them at the beginning
7053 rtx note_head = note_list;
7055 while (PREV_INSN (note_head))
7057 note_head = PREV_INSN (note_head);
7060 PREV_INSN (note_head) = PREV_INSN (head);
7061 NEXT_INSN (PREV_INSN (head)) = note_head;
7062 PREV_INSN (head) = note_list;
7063 NEXT_INSN (note_list) = head;
7067 /* update target block boundaries. */
7068 if (new_needs & NEED_HEAD)
7069 BLOCK_HEAD (b) = head;
7071 if (new_needs & NEED_TAIL)
7072 BLOCK_END (b) = tail;
7077 fprintf (dump, ";; total time = %d\n;; new basic block head = %d\n",
7078 clock_var, INSN_UID (BLOCK_HEAD (b)));
7079 fprintf (dump, ";; new basic block end = %d\n\n",
7080 INSN_UID (BLOCK_END (b)));
7083 return (sched_n_insns);
7084 } /* schedule_block () */
7087 /* print the bit-set of registers, S. callable from debugger */
7090 debug_reg_vector (s)
7095 EXECUTE_IF_SET_IN_REG_SET (s, 0, regno,
7097 fprintf (dump, " %d", regno);
7100 fprintf (dump, "\n");
7103 /* Use the backward dependences from LOG_LINKS to build
7104 forward dependences in INSN_DEPEND. */
7107 compute_block_forward_dependences (bb)
7113 enum reg_note dep_type;
7115 get_block_head_tail (bb, &head, &tail);
7116 next_tail = NEXT_INSN (tail);
7117 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
7119 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7122 insn = group_leader (insn);
7124 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
7126 rtx x = group_leader (XEXP (link, 0));
7129 if (x != XEXP (link, 0))
7132 /* Ignore dependences upon deleted insn */
7133 if (GET_CODE (x) == NOTE || INSN_DELETED_P (x))
7135 if (find_insn_list (insn, INSN_DEPEND (x)))
7138 new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
7140 dep_type = REG_NOTE_KIND (link);
7141 PUT_REG_NOTE_KIND (new_link, dep_type);
7143 INSN_DEPEND (x) = new_link;
7144 INSN_DEP_COUNT (insn) += 1;
7149 /* Initialize variables for region data dependence analysis.
7150 n_bbs is the number of region blocks */
7152 __inline static void
7153 init_rgn_data_dependences (n_bbs)
7158 /* variables for which one copy exists for each block */
7159 bzero ((char *) bb_pending_read_insns, n_bbs * sizeof (rtx));
7160 bzero ((char *) bb_pending_read_mems, n_bbs * sizeof (rtx));
7161 bzero ((char *) bb_pending_write_insns, n_bbs * sizeof (rtx));
7162 bzero ((char *) bb_pending_write_mems, n_bbs * sizeof (rtx));
7163 bzero ((char *) bb_pending_lists_length, n_bbs * sizeof (rtx));
7164 bzero ((char *) bb_last_pending_memory_flush, n_bbs * sizeof (rtx));
7165 bzero ((char *) bb_last_function_call, n_bbs * sizeof (rtx));
7166 bzero ((char *) bb_sched_before_next_call, n_bbs * sizeof (rtx));
7168 /* Create an insn here so that we can hang dependencies off of it later. */
7169 for (bb = 0; bb < n_bbs; bb++)
7171 bb_sched_before_next_call[bb] =
7172 gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
7173 NULL_RTX, 0, NULL_RTX, NULL_RTX);
7174 LOG_LINKS (bb_sched_before_next_call[bb]) = 0;
7178 /* Add dependences so that branches are scheduled to run last in their block */
7181 add_branch_dependences (head, tail)
7187 /* For all branches, calls, uses, and cc0 setters, force them to remain
7188 in order at the end of the block by adding dependencies and giving
7189 the last a high priority. There may be notes present, and prev_head
7192 Branches must obviously remain at the end. Calls should remain at the
7193 end since moving them results in worse register allocation. Uses remain
7194 at the end to ensure proper register allocation. cc0 setters remaim
7195 at the end because they can't be moved away from their cc0 user. */
7198 while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
7199 || (GET_CODE (insn) == INSN
7200 && (GET_CODE (PATTERN (insn)) == USE
7202 || sets_cc0_p (PATTERN (insn))
7205 || GET_CODE (insn) == NOTE)
7207 if (GET_CODE (insn) != NOTE)
7210 && !find_insn_list (insn, LOG_LINKS (last)))
7212 add_dependence (last, insn, REG_DEP_ANTI);
7213 INSN_REF_COUNT (insn)++;
7216 CANT_MOVE (insn) = 1;
7219 /* Skip over insns that are part of a group.
7220 Make each insn explicitly depend on the previous insn.
7221 This ensures that only the group header will ever enter
7222 the ready queue (and, when scheduled, will automatically
7223 schedule the SCHED_GROUP_P block). */
7224 while (SCHED_GROUP_P (insn))
7226 rtx temp = prev_nonnote_insn (insn);
7227 add_dependence (insn, temp, REG_DEP_ANTI);
7232 /* Don't overrun the bounds of the basic block. */
7236 insn = PREV_INSN (insn);
7239 /* make sure these insns are scheduled last in their block */
7242 while (insn != head)
7244 insn = prev_nonnote_insn (insn);
7246 if (INSN_REF_COUNT (insn) != 0)
7249 if (!find_insn_list (last, LOG_LINKS (insn)))
7250 add_dependence (last, insn, REG_DEP_ANTI);
7251 INSN_REF_COUNT (insn) = 1;
7253 /* Skip over insns that are part of a group. */
7254 while (SCHED_GROUP_P (insn))
7255 insn = prev_nonnote_insn (insn);
7259 /* Compute bacward dependences inside BB. In a multiple blocks region:
7260 (1) a bb is analyzed after its predecessors, and (2) the lists in
7261 effect at the end of bb (after analyzing for bb) are inherited by
7264 Specifically for reg-reg data dependences, the block insns are
7265 scanned by sched_analyze () top-to-bottom. Two lists are
7266 naintained by sched_analyze (): reg_last_defs[] for register DEFs,
7267 and reg_last_uses[] for register USEs.
7269 When analysis is completed for bb, we update for its successors:
7270 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7271 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7273 The mechanism for computing mem-mem data dependence is very
7274 similar, and the result is interblock dependences in the region. */
7277 compute_block_backward_dependences (bb)
7283 int max_reg = max_reg_num ();
7285 b = BB_TO_BLOCK (bb);
7287 if (current_nr_blocks == 1)
7289 reg_last_uses = (rtx *) alloca (max_reg * sizeof (rtx));
7290 reg_last_sets = (rtx *) alloca (max_reg * sizeof (rtx));
7291 reg_last_clobbers = (rtx *) alloca (max_reg * sizeof (rtx));
7293 bzero ((char *) reg_last_uses, max_reg * sizeof (rtx));
7294 bzero ((char *) reg_last_sets, max_reg * sizeof (rtx));
7295 bzero ((char *) reg_last_clobbers, max_reg * sizeof (rtx));
7297 pending_read_insns = 0;
7298 pending_read_mems = 0;
7299 pending_write_insns = 0;
7300 pending_write_mems = 0;
7301 pending_lists_length = 0;
7302 last_function_call = 0;
7303 last_pending_memory_flush = 0;
7304 sched_before_next_call
7305 = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
7306 NULL_RTX, 0, NULL_RTX, NULL_RTX);
7307 LOG_LINKS (sched_before_next_call) = 0;
7311 reg_last_uses = bb_reg_last_uses[bb];
7312 reg_last_sets = bb_reg_last_sets[bb];
7313 reg_last_clobbers = bb_reg_last_clobbers[bb];
7315 pending_read_insns = bb_pending_read_insns[bb];
7316 pending_read_mems = bb_pending_read_mems[bb];
7317 pending_write_insns = bb_pending_write_insns[bb];
7318 pending_write_mems = bb_pending_write_mems[bb];
7319 pending_lists_length = bb_pending_lists_length[bb];
7320 last_function_call = bb_last_function_call[bb];
7321 last_pending_memory_flush = bb_last_pending_memory_flush[bb];
7323 sched_before_next_call = bb_sched_before_next_call[bb];
7326 /* do the analysis for this block */
7327 get_block_head_tail (bb, &head, &tail);
7328 sched_analyze (head, tail);
7329 add_branch_dependences (head, tail);
7331 if (current_nr_blocks > 1)
7334 int b_succ, bb_succ;
7336 rtx link_insn, link_mem;
7339 /* these lists should point to the right place, for correct freeing later. */
7340 bb_pending_read_insns[bb] = pending_read_insns;
7341 bb_pending_read_mems[bb] = pending_read_mems;
7342 bb_pending_write_insns[bb] = pending_write_insns;
7343 bb_pending_write_mems[bb] = pending_write_mems;
7345 /* bb's structures are inherited by it's successors */
7346 first_edge = e = OUT_EDGES (b);
7350 b_succ = TO_BLOCK (e);
7351 bb_succ = BLOCK_TO_BB (b_succ);
7353 /* only bbs "below" bb, in the same region, are interesting */
7354 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
7361 for (reg = 0; reg < max_reg; reg++)
7364 /* reg-last-uses lists are inherited by bb_succ */
7365 for (u = reg_last_uses[reg]; u; u = XEXP (u, 1))
7367 if (find_insn_list (XEXP (u, 0), (bb_reg_last_uses[bb_succ])[reg]))
7370 (bb_reg_last_uses[bb_succ])[reg]
7371 = alloc_INSN_LIST (XEXP (u, 0),
7372 (bb_reg_last_uses[bb_succ])[reg]);
7375 /* reg-last-defs lists are inherited by bb_succ */
7376 for (u = reg_last_sets[reg]; u; u = XEXP (u, 1))
7378 if (find_insn_list (XEXP (u, 0), (bb_reg_last_sets[bb_succ])[reg]))
7381 (bb_reg_last_sets[bb_succ])[reg]
7382 = alloc_INSN_LIST (XEXP (u, 0),
7383 (bb_reg_last_sets[bb_succ])[reg]);
7386 for (u = reg_last_clobbers[reg]; u; u = XEXP (u, 1))
7388 if (find_insn_list (XEXP (u, 0), (bb_reg_last_clobbers[bb_succ])[reg]))
7391 (bb_reg_last_clobbers[bb_succ])[reg]
7392 = alloc_INSN_LIST (XEXP (u, 0),
7393 (bb_reg_last_clobbers[bb_succ])[reg]);
7397 /* mem read/write lists are inherited by bb_succ */
7398 link_insn = pending_read_insns;
7399 link_mem = pending_read_mems;
7402 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7403 bb_pending_read_insns[bb_succ],
7404 bb_pending_read_mems[bb_succ])))
7405 add_insn_mem_dependence (&bb_pending_read_insns[bb_succ],
7406 &bb_pending_read_mems[bb_succ],
7407 XEXP (link_insn, 0), XEXP (link_mem, 0));
7408 link_insn = XEXP (link_insn, 1);
7409 link_mem = XEXP (link_mem, 1);
7412 link_insn = pending_write_insns;
7413 link_mem = pending_write_mems;
7416 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7417 bb_pending_write_insns[bb_succ],
7418 bb_pending_write_mems[bb_succ])))
7419 add_insn_mem_dependence (&bb_pending_write_insns[bb_succ],
7420 &bb_pending_write_mems[bb_succ],
7421 XEXP (link_insn, 0), XEXP (link_mem, 0));
7423 link_insn = XEXP (link_insn, 1);
7424 link_mem = XEXP (link_mem, 1);
7427 /* last_function_call is inherited by bb_succ */
7428 for (u = last_function_call; u; u = XEXP (u, 1))
7430 if (find_insn_list (XEXP (u, 0), bb_last_function_call[bb_succ]))
7433 bb_last_function_call[bb_succ]
7434 = alloc_INSN_LIST (XEXP (u, 0),
7435 bb_last_function_call[bb_succ]);
7438 /* last_pending_memory_flush is inherited by bb_succ */
7439 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
7441 if (find_insn_list (XEXP (u, 0), bb_last_pending_memory_flush[bb_succ]))
7444 bb_last_pending_memory_flush[bb_succ]
7445 = alloc_INSN_LIST (XEXP (u, 0),
7446 bb_last_pending_memory_flush[bb_succ]);
7449 /* sched_before_next_call is inherited by bb_succ */
7450 x = LOG_LINKS (sched_before_next_call);
7451 for (; x; x = XEXP (x, 1))
7452 add_dependence (bb_sched_before_next_call[bb_succ],
7453 XEXP (x, 0), REG_DEP_ANTI);
7457 while (e != first_edge);
7460 /* Free up the INSN_LISTs
7462 Note this loop is executed max_reg * nr_regions times. It's first
7463 implementation accounted for over 90% of the calls to free_list.
7464 The list was empty for the vast majority of those calls. On the PA,
7465 not calling free_list in those cases improves -O2 compile times by
7467 for (b = 0; b < max_reg; ++b)
7469 if (reg_last_clobbers[b])
7470 free_list (®_last_clobbers[b], &unused_insn_list);
7471 if (reg_last_sets[b])
7472 free_list (®_last_sets[b], &unused_insn_list);
7473 if (reg_last_uses[b])
7474 free_list (®_last_uses[b], &unused_insn_list);
7477 /* Assert that we won't need bb_reg_last_* for this block anymore. */
7478 if (current_nr_blocks > 1)
7480 bb_reg_last_uses[bb] = (rtx *) NULL_RTX;
7481 bb_reg_last_sets[bb] = (rtx *) NULL_RTX;
7482 bb_reg_last_clobbers[bb] = (rtx *) NULL_RTX;
7486 /* Print dependences for debugging, callable from debugger */
7489 debug_dependencies ()
7493 fprintf (dump, ";; --------------- forward dependences: ------------ \n");
7494 for (bb = 0; bb < current_nr_blocks; bb++)
7502 get_block_head_tail (bb, &head, &tail);
7503 next_tail = NEXT_INSN (tail);
7504 fprintf (dump, "\n;; --- Region Dependences --- b %d bb %d \n",
7505 BB_TO_BLOCK (bb), bb);
7507 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7508 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7509 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7510 "----", "----", "--", "---", "----", "----", "--------", "-----");
7511 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
7516 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7519 fprintf (dump, ";; %6d ", INSN_UID (insn));
7520 if (GET_CODE (insn) == NOTE)
7522 n = NOTE_LINE_NUMBER (insn);
7524 fprintf (dump, "%s\n", GET_NOTE_INSN_NAME (n));
7526 fprintf (dump, "line %d, file %s\n", n,
7527 NOTE_SOURCE_FILE (insn));
7530 fprintf (dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
7534 unit = insn_unit (insn);
7536 || function_units[unit].blockage_range_function == 0) ? 0 :
7537 function_units[unit].blockage_range_function (insn);
7539 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7540 (SCHED_GROUP_P (insn) ? "+" : " "),
7544 INSN_DEP_COUNT (insn),
7545 INSN_PRIORITY (insn),
7546 insn_cost (insn, 0, 0),
7547 (int) MIN_BLOCKAGE_COST (range),
7548 (int) MAX_BLOCKAGE_COST (range));
7549 insn_print_units (insn);
7550 fprintf (dump, "\t: ");
7551 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
7552 fprintf (dump, "%d ", INSN_UID (XEXP (link, 0)));
7553 fprintf (dump, "\n");
7557 fprintf (dump, "\n");
7560 /* Set_priorities: compute priority of each insn in the block */
7573 get_block_head_tail (bb, &head, &tail);
7574 prev_head = PREV_INSN (head);
7577 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
7581 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
7584 if (GET_CODE (insn) == NOTE)
7587 if (!(SCHED_GROUP_P (insn)))
7589 (void) priority (insn);
7595 /* Make each element of VECTOR point at an rtx-vector,
7596 taking the space for all those rtx-vectors from SPACE.
7597 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7598 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7599 (this is the same as init_regset_vector () in flow.c) */
7602 init_rtx_vector (vector, space, nelts, bytes_per_elt)
7609 register rtx *p = space;
7611 for (i = 0; i < nelts; i++)
7614 p += bytes_per_elt / sizeof (*p);
7618 /* Schedule a region. A region is either an inner loop, a loop-free
7619 subroutine, or a single basic block. Each bb in the region is
7620 scheduled after its flow predecessors. */
7623 schedule_region (rgn)
7627 int rgn_n_insns = 0;
7628 int sched_rgn_n_insns = 0;
7630 /* set variables for the current region */
7631 current_nr_blocks = RGN_NR_BLOCKS (rgn);
7632 current_blocks = RGN_BLOCKS (rgn);
7634 reg_pending_sets = ALLOCA_REG_SET ();
7635 reg_pending_clobbers = ALLOCA_REG_SET ();
7636 reg_pending_sets_all = 0;
7638 /* initializations for region data dependence analyisis */
7639 if (current_nr_blocks > 1)
7642 int maxreg = max_reg_num ();
7644 bb_reg_last_uses = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7645 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7646 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7647 init_rtx_vector (bb_reg_last_uses, space, current_nr_blocks,
7648 maxreg * sizeof (rtx *));
7650 bb_reg_last_sets = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7651 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7652 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7653 init_rtx_vector (bb_reg_last_sets, space, current_nr_blocks,
7654 maxreg * sizeof (rtx *));
7656 bb_reg_last_clobbers =
7657 (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7658 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7659 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7660 init_rtx_vector (bb_reg_last_clobbers, space, current_nr_blocks,
7661 maxreg * sizeof (rtx *));
7663 bb_pending_read_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7664 bb_pending_read_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7665 bb_pending_write_insns =
7666 (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7667 bb_pending_write_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7668 bb_pending_lists_length =
7669 (int *) alloca (current_nr_blocks * sizeof (int));
7670 bb_last_pending_memory_flush =
7671 (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7672 bb_last_function_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7673 bb_sched_before_next_call =
7674 (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7676 init_rgn_data_dependences (current_nr_blocks);
7679 /* compute LOG_LINKS */
7680 for (bb = 0; bb < current_nr_blocks; bb++)
7681 compute_block_backward_dependences (bb);
7683 /* compute INSN_DEPEND */
7684 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7685 compute_block_forward_dependences (bb);
7687 /* Delete line notes, compute live-regs at block end, and set priorities. */
7689 for (bb = 0; bb < current_nr_blocks; bb++)
7691 if (reload_completed == 0)
7692 find_pre_sched_live (bb);
7694 if (write_symbols != NO_DEBUG)
7696 save_line_notes (bb);
7700 rgn_n_insns += set_priorities (bb);
7703 /* compute interblock info: probabilities, split-edges, dominators, etc. */
7704 if (current_nr_blocks > 1)
7708 prob = (float *) alloca ((current_nr_blocks) * sizeof (float));
7710 bbset_size = current_nr_blocks / HOST_BITS_PER_WIDE_INT + 1;
7711 dom = (bbset *) alloca (current_nr_blocks * sizeof (bbset));
7712 for (i = 0; i < current_nr_blocks; i++)
7714 dom[i] = (bbset) alloca (bbset_size * sizeof (HOST_WIDE_INT));
7715 bzero ((char *) dom[i], bbset_size * sizeof (HOST_WIDE_INT));
7720 edge_to_bit = (int *) alloca (nr_edges * sizeof (int));
7721 for (i = 1; i < nr_edges; i++)
7722 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
7723 EDGE_TO_BIT (i) = rgn_nr_edges++;
7724 rgn_edges = (int *) alloca (rgn_nr_edges * sizeof (int));
7727 for (i = 1; i < nr_edges; i++)
7728 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
7729 rgn_edges[rgn_nr_edges++] = i;
7732 edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
7733 pot_split = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7734 ancestor_edges = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7735 for (i = 0; i < current_nr_blocks; i++)
7738 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7739 bzero ((char *) pot_split[i],
7740 edgeset_size * sizeof (HOST_WIDE_INT));
7742 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7743 bzero ((char *) ancestor_edges[i],
7744 edgeset_size * sizeof (HOST_WIDE_INT));
7747 /* compute probabilities, dominators, split_edges */
7748 for (bb = 0; bb < current_nr_blocks; bb++)
7749 compute_dom_prob_ps (bb);
7752 /* now we can schedule all blocks */
7753 for (bb = 0; bb < current_nr_blocks; bb++)
7755 sched_rgn_n_insns += schedule_block (bb, rgn_n_insns);
7762 /* sanity check: verify that all region insns were scheduled */
7763 if (sched_rgn_n_insns != rgn_n_insns)
7766 /* update register life and usage information */
7767 if (reload_completed == 0)
7769 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7770 find_post_sched_live (bb);
7772 if (current_nr_blocks <= 1)
7773 /* Sanity check. There should be no REG_DEAD notes leftover at the end.
7774 In practice, this can occur as the result of bugs in flow, combine.c,
7775 and/or sched.c. The values of the REG_DEAD notes remaining are
7776 meaningless, because dead_notes is just used as a free list. */
7777 if (dead_notes != 0)
7781 /* restore line notes. */
7782 if (write_symbols != NO_DEBUG)
7784 for (bb = 0; bb < current_nr_blocks; bb++)
7785 restore_line_notes (bb);
7788 /* Done with this region */
7789 free_pending_lists ();
7791 FREE_REG_SET (reg_pending_sets);
7792 FREE_REG_SET (reg_pending_clobbers);
7795 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
7796 needed for the hard register mentioned in the note. This can happen
7797 if the reference to the hard register in the original insn was split into
7798 several smaller hard register references in the split insns. */
7801 split_hard_reg_notes (note, first, last)
7802 rtx note, first, last;
7804 rtx reg, temp, link;
7805 int n_regs, i, new_reg;
7808 /* Assume that this is a REG_DEAD note. */
7809 if (REG_NOTE_KIND (note) != REG_DEAD)
7812 reg = XEXP (note, 0);
7814 n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
7816 for (i = 0; i < n_regs; i++)
7818 new_reg = REGNO (reg) + i;
7820 /* Check for references to new_reg in the split insns. */
7821 for (insn = last;; insn = PREV_INSN (insn))
7823 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7824 && (temp = regno_use_in (new_reg, PATTERN (insn))))
7826 /* Create a new reg dead note ere. */
7827 link = alloc_EXPR_LIST (REG_DEAD, temp, REG_NOTES (insn));
7828 REG_NOTES (insn) = link;
7830 /* If killed multiple registers here, then add in the excess. */
7831 i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
7835 /* It isn't mentioned anywhere, so no new reg note is needed for
7843 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
7844 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
7847 new_insn_dead_notes (pat, insn, last, orig_insn)
7848 rtx pat, insn, last, orig_insn;
7852 /* PAT is either a CLOBBER or a SET here. */
7853 dest = XEXP (pat, 0);
7855 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
7856 || GET_CODE (dest) == STRICT_LOW_PART
7857 || GET_CODE (dest) == SIGN_EXTRACT)
7858 dest = XEXP (dest, 0);
7860 if (GET_CODE (dest) == REG)
7862 /* If the original insn already used this register, we may not add new
7863 notes for it. One example for a split that needs this test is
7864 when a multi-word memory access with register-indirect addressing
7865 is split into multiple memory accesses with auto-increment and
7866 one adjusting add instruction for the address register. */
7867 if (reg_referenced_p (dest, PATTERN (orig_insn)))
7869 for (tem = last; tem != insn; tem = PREV_INSN (tem))
7871 if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
7872 && reg_overlap_mentioned_p (dest, PATTERN (tem))
7873 && (set = single_set (tem)))
7875 rtx tem_dest = SET_DEST (set);
7877 while (GET_CODE (tem_dest) == ZERO_EXTRACT
7878 || GET_CODE (tem_dest) == SUBREG
7879 || GET_CODE (tem_dest) == STRICT_LOW_PART
7880 || GET_CODE (tem_dest) == SIGN_EXTRACT)
7881 tem_dest = XEXP (tem_dest, 0);
7883 if (!rtx_equal_p (tem_dest, dest))
7885 /* Use the same scheme as combine.c, don't put both REG_DEAD
7886 and REG_UNUSED notes on the same insn. */
7887 if (!find_regno_note (tem, REG_UNUSED, REGNO (dest))
7888 && !find_regno_note (tem, REG_DEAD, REGNO (dest)))
7890 rtx note = alloc_EXPR_LIST (REG_DEAD, dest,
7892 REG_NOTES (tem) = note;
7894 /* The reg only dies in one insn, the last one that uses
7898 else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
7899 /* We found an instruction that both uses the register,
7900 and sets it, so no new REG_NOTE is needed for this set. */
7904 /* If this is a set, it must die somewhere, unless it is the dest of
7905 the original insn, and hence is live after the original insn. Abort
7906 if it isn't supposed to be live after the original insn.
7908 If this is a clobber, then just add a REG_UNUSED note. */
7911 int live_after_orig_insn = 0;
7912 rtx pattern = PATTERN (orig_insn);
7915 if (GET_CODE (pat) == CLOBBER)
7917 rtx note = alloc_EXPR_LIST (REG_UNUSED, dest, REG_NOTES (insn));
7918 REG_NOTES (insn) = note;
7922 /* The original insn could have multiple sets, so search the
7923 insn for all sets. */
7924 if (GET_CODE (pattern) == SET)
7926 if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
7927 live_after_orig_insn = 1;
7929 else if (GET_CODE (pattern) == PARALLEL)
7931 for (i = 0; i < XVECLEN (pattern, 0); i++)
7932 if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
7933 && reg_overlap_mentioned_p (dest,
7934 SET_DEST (XVECEXP (pattern,
7936 live_after_orig_insn = 1;
7939 if (!live_after_orig_insn)
7945 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
7946 registers modified by X. INC is -1 if the containing insn is being deleted,
7947 and is 1 if the containing insn is a newly generated insn. */
7950 update_n_sets (x, inc)
7954 rtx dest = SET_DEST (x);
7956 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
7957 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
7958 dest = SUBREG_REG (dest);
7960 if (GET_CODE (dest) == REG)
7962 int regno = REGNO (dest);
7964 if (regno < FIRST_PSEUDO_REGISTER)
7967 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
7969 for (i = regno; i < endregno; i++)
7970 REG_N_SETS (i) += inc;
7973 REG_N_SETS (regno) += inc;
7977 /* Updates all flow-analysis related quantities (including REG_NOTES) for
7978 the insns from FIRST to LAST inclusive that were created by splitting
7979 ORIG_INSN. NOTES are the original REG_NOTES. */
7982 update_flow_info (notes, first, last, orig_insn)
7989 rtx orig_dest, temp;
7992 /* Get and save the destination set by the original insn. */
7994 orig_dest = single_set (orig_insn);
7996 orig_dest = SET_DEST (orig_dest);
7998 /* Move REG_NOTES from the original insn to where they now belong. */
8000 for (note = notes; note; note = next)
8002 next = XEXP (note, 1);
8003 switch (REG_NOTE_KIND (note))
8007 /* Move these notes from the original insn to the last new insn where
8008 the register is now set. */
8010 for (insn = last;; insn = PREV_INSN (insn))
8012 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8013 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
8015 /* If this note refers to a multiple word hard register, it
8016 may have been split into several smaller hard register
8017 references, so handle it specially. */
8018 temp = XEXP (note, 0);
8019 if (REG_NOTE_KIND (note) == REG_DEAD
8020 && GET_CODE (temp) == REG
8021 && REGNO (temp) < FIRST_PSEUDO_REGISTER
8022 && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
8023 split_hard_reg_notes (note, first, last);
8026 XEXP (note, 1) = REG_NOTES (insn);
8027 REG_NOTES (insn) = note;
8030 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
8032 /* ??? This won't handle multiple word registers correctly,
8033 but should be good enough for now. */
8034 if (REG_NOTE_KIND (note) == REG_UNUSED
8035 && GET_CODE (XEXP (note, 0)) != SCRATCH
8036 && !dead_or_set_p (insn, XEXP (note, 0)))
8037 PUT_REG_NOTE_KIND (note, REG_DEAD);
8039 /* The reg only dies in one insn, the last one that uses
8043 /* It must die somewhere, fail it we couldn't find where it died.
8045 If this is a REG_UNUSED note, then it must be a temporary
8046 register that was not needed by this instantiation of the
8047 pattern, so we can safely ignore it. */
8050 if (REG_NOTE_KIND (note) != REG_UNUSED)
8059 /* If the insn that set the register to 0 was deleted, this
8060 note cannot be relied on any longer. The destination might
8061 even have been moved to memory.
8062 This was observed for SH4 with execute/920501-6.c compilation,
8063 -O2 -fomit-frame-pointer -finline-functions . */
8064 if (GET_CODE (XEXP (note, 0)) == NOTE
8065 || INSN_DELETED_P (XEXP (note, 0)))
8067 /* This note applies to the dest of the original insn. Find the
8068 first new insn that now has the same dest, and move the note
8074 for (insn = first;; insn = NEXT_INSN (insn))
8076 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8077 && (temp = single_set (insn))
8078 && rtx_equal_p (SET_DEST (temp), orig_dest))
8080 XEXP (note, 1) = REG_NOTES (insn);
8081 REG_NOTES (insn) = note;
8082 /* The reg is only zero before one insn, the first that
8086 /* If this note refers to a multiple word hard
8087 register, it may have been split into several smaller
8088 hard register references. We could split the notes,
8089 but simply dropping them is good enough. */
8090 if (GET_CODE (orig_dest) == REG
8091 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
8092 && HARD_REGNO_NREGS (REGNO (orig_dest),
8093 GET_MODE (orig_dest)) > 1)
8095 /* It must be set somewhere, fail if we couldn't find where it
8104 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
8105 set is meaningless. Just drop the note. */
8109 case REG_NO_CONFLICT:
8110 /* These notes apply to the dest of the original insn. Find the last
8111 new insn that now has the same dest, and move the note there. */
8116 for (insn = last;; insn = PREV_INSN (insn))
8118 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8119 && (temp = single_set (insn))
8120 && rtx_equal_p (SET_DEST (temp), orig_dest))
8122 XEXP (note, 1) = REG_NOTES (insn);
8123 REG_NOTES (insn) = note;
8124 /* Only put this note on one of the new insns. */
8128 /* The original dest must still be set someplace. Abort if we
8129 couldn't find it. */
8132 /* However, if this note refers to a multiple word hard
8133 register, it may have been split into several smaller
8134 hard register references. We could split the notes,
8135 but simply dropping them is good enough. */
8136 if (GET_CODE (orig_dest) == REG
8137 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
8138 && HARD_REGNO_NREGS (REGNO (orig_dest),
8139 GET_MODE (orig_dest)) > 1)
8141 /* Likewise for multi-word memory references. */
8142 if (GET_CODE (orig_dest) == MEM
8143 && SIZE_FOR_MODE (orig_dest) > UNITS_PER_WORD)
8151 /* Move a REG_LIBCALL note to the first insn created, and update
8152 the corresponding REG_RETVAL note. */
8153 XEXP (note, 1) = REG_NOTES (first);
8154 REG_NOTES (first) = note;
8156 insn = XEXP (note, 0);
8157 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
8159 XEXP (note, 0) = first;
8162 case REG_EXEC_COUNT:
8163 /* Move a REG_EXEC_COUNT note to the first insn created. */
8164 XEXP (note, 1) = REG_NOTES (first);
8165 REG_NOTES (first) = note;
8169 /* Move a REG_RETVAL note to the last insn created, and update
8170 the corresponding REG_LIBCALL note. */
8171 XEXP (note, 1) = REG_NOTES (last);
8172 REG_NOTES (last) = note;
8174 insn = XEXP (note, 0);
8175 note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
8177 XEXP (note, 0) = last;
8182 /* This should be moved to whichever instruction is a JUMP_INSN. */
8184 for (insn = last;; insn = PREV_INSN (insn))
8186 if (GET_CODE (insn) == JUMP_INSN)
8188 XEXP (note, 1) = REG_NOTES (insn);
8189 REG_NOTES (insn) = note;
8190 /* Only put this note on one of the new insns. */
8193 /* Fail if we couldn't find a JUMP_INSN. */
8200 /* reload sometimes leaves obsolete REG_INC notes around. */
8201 if (reload_completed)
8203 /* This should be moved to whichever instruction now has the
8204 increment operation. */
8208 /* Should be moved to the new insn(s) which use the label. */
8209 for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
8210 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8211 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
8213 REG_NOTES (insn) = alloc_EXPR_LIST (REG_LABEL,
8221 /* These two notes will never appear until after reorg, so we don't
8222 have to handle them here. */
8228 /* Each new insn created, except the last, has a new set. If the destination
8229 is a register, then this reg is now live across several insns, whereas
8230 previously the dest reg was born and died within the same insn. To
8231 reflect this, we now need a REG_DEAD note on the insn where this
8234 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
8236 for (insn = first; insn != last; insn = NEXT_INSN (insn))
8241 pat = PATTERN (insn);
8242 if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
8243 new_insn_dead_notes (pat, insn, last, orig_insn);
8244 else if (GET_CODE (pat) == PARALLEL)
8246 for (i = 0; i < XVECLEN (pat, 0); i++)
8247 if (GET_CODE (XVECEXP (pat, 0, i)) == SET
8248 || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
8249 new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
8253 /* If any insn, except the last, uses the register set by the last insn,
8254 then we need a new REG_DEAD note on that insn. In this case, there
8255 would not have been a REG_DEAD note for this register in the original
8256 insn because it was used and set within one insn. */
8258 set = single_set (last);
8261 rtx dest = SET_DEST (set);
8263 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
8264 || GET_CODE (dest) == STRICT_LOW_PART
8265 || GET_CODE (dest) == SIGN_EXTRACT)
8266 dest = XEXP (dest, 0);
8268 if (GET_CODE (dest) == REG
8269 /* Global registers are always live, so the code below does not
8271 && (REGNO (dest) >= FIRST_PSEUDO_REGISTER
8272 || ! global_regs[REGNO (dest)]))
8274 rtx stop_insn = PREV_INSN (first);
8276 /* If the last insn uses the register that it is setting, then
8277 we don't want to put a REG_DEAD note there. Search backwards
8278 to find the first insn that sets but does not use DEST. */
8281 if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
8283 for (insn = PREV_INSN (insn); insn != first;
8284 insn = PREV_INSN (insn))
8286 if ((set = single_set (insn))
8287 && reg_mentioned_p (dest, SET_DEST (set))
8288 && ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
8293 /* Now find the first insn that uses but does not set DEST. */
8295 for (insn = PREV_INSN (insn); insn != stop_insn;
8296 insn = PREV_INSN (insn))
8298 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8299 && reg_mentioned_p (dest, PATTERN (insn))
8300 && (set = single_set (insn)))
8302 rtx insn_dest = SET_DEST (set);
8304 while (GET_CODE (insn_dest) == ZERO_EXTRACT
8305 || GET_CODE (insn_dest) == SUBREG
8306 || GET_CODE (insn_dest) == STRICT_LOW_PART
8307 || GET_CODE (insn_dest) == SIGN_EXTRACT)
8308 insn_dest = XEXP (insn_dest, 0);
8310 if (insn_dest != dest)
8312 note = alloc_EXPR_LIST (REG_DEAD, dest, REG_NOTES (insn));
8313 REG_NOTES (insn) = note;
8314 /* The reg only dies in one insn, the last one
8323 /* If the original dest is modifying a multiple register target, and the
8324 original instruction was split such that the original dest is now set
8325 by two or more SUBREG sets, then the split insns no longer kill the
8326 destination of the original insn.
8328 In this case, if there exists an instruction in the same basic block,
8329 before the split insn, which uses the original dest, and this use is
8330 killed by the original insn, then we must remove the REG_DEAD note on
8331 this insn, because it is now superfluous.
8333 This does not apply when a hard register gets split, because the code
8334 knows how to handle overlapping hard registers properly. */
8335 if (orig_dest && GET_CODE (orig_dest) == REG)
8337 int found_orig_dest = 0;
8338 int found_split_dest = 0;
8340 for (insn = first;; insn = NEXT_INSN (insn))
8345 /* I'm not sure if this can happen, but let's be safe. */
8346 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
8349 pat = PATTERN (insn);
8350 i = GET_CODE (pat) == PARALLEL ? XVECLEN (pat, 0) : 0;
8355 if (GET_CODE (set) == SET)
8357 if (GET_CODE (SET_DEST (set)) == REG
8358 && REGNO (SET_DEST (set)) == REGNO (orig_dest))
8360 found_orig_dest = 1;
8363 else if (GET_CODE (SET_DEST (set)) == SUBREG
8364 && SUBREG_REG (SET_DEST (set)) == orig_dest)
8366 found_split_dest = 1;
8372 set = XVECEXP (pat, 0, i);
8379 if (found_split_dest)
8381 /* Search backwards from FIRST, looking for the first insn that uses
8382 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
8383 If we find an insn, and it has a REG_DEAD note, then delete the
8386 for (insn = first; insn; insn = PREV_INSN (insn))
8388 if (GET_CODE (insn) == CODE_LABEL
8389 || GET_CODE (insn) == JUMP_INSN)
8391 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8392 && reg_mentioned_p (orig_dest, insn))
8394 note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
8396 remove_note (insn, note);
8400 else if (!found_orig_dest)
8404 /* Should never reach here for a pseudo reg. */
8405 if (REGNO (orig_dest) >= FIRST_PSEUDO_REGISTER)
8408 /* This can happen for a hard register, if the splitter
8409 does not bother to emit instructions which would be no-ops.
8410 We try to verify that this is the case by checking to see if
8411 the original instruction uses all of the registers that it
8412 set. This case is OK, because deleting a no-op can not affect
8413 REG_DEAD notes on other insns. If this is not the case, then
8416 regno = REGNO (orig_dest);
8417 for (i = HARD_REGNO_NREGS (regno, GET_MODE (orig_dest)) - 1;
8419 if (! refers_to_regno_p (regno + i, regno + i + 1, orig_insn,
8427 /* Update reg_n_sets. This is necessary to prevent local alloc from
8428 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
8429 a reg from set once to set multiple times. */
8432 rtx x = PATTERN (orig_insn);
8433 RTX_CODE code = GET_CODE (x);
8435 if (code == SET || code == CLOBBER)
8436 update_n_sets (x, -1);
8437 else if (code == PARALLEL)
8440 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8442 code = GET_CODE (XVECEXP (x, 0, i));
8443 if (code == SET || code == CLOBBER)
8444 update_n_sets (XVECEXP (x, 0, i), -1);
8448 for (insn = first;; insn = NEXT_INSN (insn))
8451 code = GET_CODE (x);
8453 if (code == SET || code == CLOBBER)
8454 update_n_sets (x, 1);
8455 else if (code == PARALLEL)
8458 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8460 code = GET_CODE (XVECEXP (x, 0, i));
8461 if (code == SET || code == CLOBBER)
8462 update_n_sets (XVECEXP (x, 0, i), 1);
8472 /* The one entry point in this file. DUMP_FILE is the dump file for
8476 schedule_insns (dump_file)
8487 /* disable speculative loads in their presence if cc0 defined */
8489 flag_schedule_speculative_load = 0;
8492 /* Taking care of this degenerate case makes the rest of
8493 this code simpler. */
8494 if (n_basic_blocks == 0)
8497 /* set dump and sched_verbose for the desired debugging output. If no
8498 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
8499 For -fsched-verbose-N, N>=10, print everything to stderr. */
8500 sched_verbose = sched_verbose_param;
8501 if (sched_verbose_param == 0 && dump_file)
8503 dump = ((sched_verbose_param >= 10 || !dump_file) ? stderr : dump_file);
8508 /* Initialize the unused_*_lists. We can't use the ones left over from
8509 the previous function, because gcc has freed that memory. We can use
8510 the ones left over from the first sched pass in the second pass however,
8511 so only clear them on the first sched pass. The first pass is before
8512 reload if flag_schedule_insns is set, otherwise it is afterwards. */
8514 if (reload_completed == 0 || !flag_schedule_insns)
8516 unused_insn_list = 0;
8517 unused_expr_list = 0;
8520 /* initialize issue_rate */
8521 issue_rate = ISSUE_RATE;
8523 /* do the splitting first for all blocks */
8524 for (b = 0; b < n_basic_blocks; b++)
8525 split_block_insns (b, 1);
8527 max_uid = (get_max_uid () + 1);
8529 cant_move = (char *) xmalloc (max_uid * sizeof (char));
8530 bzero ((char *) cant_move, max_uid * sizeof (char));
8532 fed_by_spec_load = (char *) xmalloc (max_uid * sizeof (char));
8533 bzero ((char *) fed_by_spec_load, max_uid * sizeof (char));
8535 is_load_insn = (char *) xmalloc (max_uid * sizeof (char));
8536 bzero ((char *) is_load_insn, max_uid * sizeof (char));
8538 insn_orig_block = (int *) xmalloc (max_uid * sizeof (int));
8539 insn_luid = (int *) xmalloc (max_uid * sizeof (int));
8542 for (b = 0; b < n_basic_blocks; b++)
8543 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
8545 INSN_BLOCK (insn) = b;
8546 INSN_LUID (insn) = luid++;
8548 if (insn == BLOCK_END (b))
8552 /* after reload, remove inter-blocks dependences computed before reload. */
8553 if (reload_completed)
8558 for (b = 0; b < n_basic_blocks; b++)
8559 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
8563 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
8566 link = LOG_LINKS (insn);
8569 rtx x = XEXP (link, 0);
8571 if (INSN_BLOCK (x) != b)
8573 remove_dependence (insn, x);
8574 link = prev ? XEXP (prev, 1) : LOG_LINKS (insn);
8577 prev = link, link = XEXP (prev, 1);
8581 if (insn == BLOCK_END (b))
8587 rgn_table = (region *) alloca ((n_basic_blocks) * sizeof (region));
8588 rgn_bb_table = (int *) alloca ((n_basic_blocks) * sizeof (int));
8589 block_to_bb = (int *) alloca ((n_basic_blocks) * sizeof (int));
8590 containing_rgn = (int *) alloca ((n_basic_blocks) * sizeof (int));
8592 /* compute regions for scheduling */
8593 if (reload_completed
8594 || n_basic_blocks == 1
8595 || !flag_schedule_interblock)
8597 find_single_block_region ();
8601 /* verify that a 'good' control flow graph can be built */
8602 if (is_cfg_nonregular ())
8604 find_single_block_region ();
8608 int_list_ptr *s_preds, *s_succs;
8609 int *num_preds, *num_succs;
8610 sbitmap *dom, *pdom;
8612 s_preds = (int_list_ptr *) alloca (n_basic_blocks
8613 * sizeof (int_list_ptr));
8614 s_succs = (int_list_ptr *) alloca (n_basic_blocks
8615 * sizeof (int_list_ptr));
8616 num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
8617 num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
8618 dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
8619 pdom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
8621 /* The scheduler runs after flow; therefore, we can't blindly call
8622 back into find_basic_blocks since doing so could invalidate the
8623 info in global_live_at_start.
8625 Consider a block consisting entirely of dead stores; after life
8626 analysis it would be a block of NOTE_INSN_DELETED notes. If
8627 we call find_basic_blocks again, then the block would be removed
8628 entirely and invalidate our the register live information.
8630 We could (should?) recompute register live information. Doing
8631 so may even be beneficial. */
8633 compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
8635 /* Compute the dominators and post dominators. We don't currently use
8636 post dominators, but we should for speculative motion analysis. */
8637 compute_dominators (dom, pdom, s_preds, s_succs);
8639 /* build_control_flow will return nonzero if it detects unreachable
8640 blocks or any other irregularity with the cfg which prevents
8641 cross block scheduling. */
8642 if (build_control_flow (s_preds, s_succs, num_preds, num_succs) != 0)
8643 find_single_block_region ();
8645 find_rgns (s_preds, s_succs, num_preds, num_succs, dom);
8647 if (sched_verbose >= 3)
8650 /* For now. This will move as more and more of haifa is converted
8651 to using the cfg code in flow.c */
8658 /* Allocate data for this pass. See comments, above,
8659 for what these vectors do.
8661 We use xmalloc instead of alloca, because max_uid can be very large
8662 when there is a lot of function inlining. If we used alloca, we could
8663 exceed stack limits on some hosts for some inputs. */
8664 insn_priority = (int *) xmalloc (max_uid * sizeof (int));
8665 insn_reg_weight = (int *) xmalloc (max_uid * sizeof (int));
8666 insn_tick = (int *) xmalloc (max_uid * sizeof (int));
8667 insn_costs = (short *) xmalloc (max_uid * sizeof (short));
8668 insn_units = (short *) xmalloc (max_uid * sizeof (short));
8669 insn_blockage = (unsigned int *) xmalloc (max_uid * sizeof (unsigned int));
8670 insn_ref_count = (int *) xmalloc (max_uid * sizeof (int));
8672 /* Allocate for forward dependencies */
8673 insn_dep_count = (int *) xmalloc (max_uid * sizeof (int));
8674 insn_depend = (rtx *) xmalloc (max_uid * sizeof (rtx));
8676 if (reload_completed == 0)
8680 sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
8681 sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
8682 sched_reg_basic_block = (int *) alloca (max_regno * sizeof (int));
8683 bb_live_regs = ALLOCA_REG_SET ();
8684 bzero ((char *) sched_reg_n_calls_crossed, max_regno * sizeof (int));
8685 bzero ((char *) sched_reg_live_length, max_regno * sizeof (int));
8687 for (i = 0; i < max_regno; i++)
8688 sched_reg_basic_block[i] = REG_BLOCK_UNKNOWN;
8692 sched_reg_n_calls_crossed = 0;
8693 sched_reg_live_length = 0;
8696 init_alias_analysis ();
8698 if (write_symbols != NO_DEBUG)
8702 line_note = (rtx *) xmalloc (max_uid * sizeof (rtx));
8703 bzero ((char *) line_note, max_uid * sizeof (rtx));
8704 line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
8705 bzero ((char *) line_note_head, n_basic_blocks * sizeof (rtx));
8707 /* Save-line-note-head:
8708 Determine the line-number at the start of each basic block.
8709 This must be computed and saved now, because after a basic block's
8710 predecessor has been scheduled, it is impossible to accurately
8711 determine the correct line number for the first insn of the block. */
8713 for (b = 0; b < n_basic_blocks; b++)
8714 for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line))
8715 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
8717 line_note_head[b] = line;
8722 bzero ((char *) insn_priority, max_uid * sizeof (int));
8723 bzero ((char *) insn_reg_weight, max_uid * sizeof (int));
8724 bzero ((char *) insn_tick, max_uid * sizeof (int));
8725 bzero ((char *) insn_costs, max_uid * sizeof (short));
8726 bzero ((char *) insn_units, max_uid * sizeof (short));
8727 bzero ((char *) insn_blockage, max_uid * sizeof (unsigned int));
8728 bzero ((char *) insn_ref_count, max_uid * sizeof (int));
8730 /* Initialize for forward dependencies */
8731 bzero ((char *) insn_depend, max_uid * sizeof (rtx));
8732 bzero ((char *) insn_dep_count, max_uid * sizeof (int));
8734 /* Find units used in this fuction, for visualization */
8736 init_target_units ();
8738 /* ??? Add a NOTE after the last insn of the last basic block. It is not
8739 known why this is done. */
8741 insn = BLOCK_END (n_basic_blocks - 1);
8742 if (NEXT_INSN (insn) == 0
8743 || (GET_CODE (insn) != NOTE
8744 && GET_CODE (insn) != CODE_LABEL
8745 /* Don't emit a NOTE if it would end up between an unconditional
8746 jump and a BARRIER. */
8747 && !(GET_CODE (insn) == JUMP_INSN
8748 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
8749 emit_note_after (NOTE_INSN_DELETED, BLOCK_END (n_basic_blocks - 1));
8751 /* Schedule every region in the subroutine */
8752 for (rgn = 0; rgn < nr_regions; rgn++)
8754 schedule_region (rgn);
8761 /* Reposition the prologue and epilogue notes in case we moved the
8762 prologue/epilogue insns. */
8763 if (reload_completed)
8764 reposition_prologue_and_epilogue_notes (get_insns ());
8766 /* delete redundant line notes. */
8767 if (write_symbols != NO_DEBUG)
8768 rm_redundant_line_notes ();
8770 /* Update information about uses of registers in the subroutine. */
8771 if (reload_completed == 0)
8772 update_reg_usage ();
8776 if (reload_completed == 0 && flag_schedule_interblock)
8778 fprintf (dump, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8786 fprintf (dump, "\n\n");
8790 free (fed_by_spec_load);
8791 free (is_load_insn);
8792 free (insn_orig_block);
8795 free (insn_priority);
8796 free (insn_reg_weight);
8800 free (insn_blockage);
8801 free (insn_ref_count);
8803 free (insn_dep_count);
8806 if (write_symbols != NO_DEBUG)
8810 FREE_REG_SET (bb_live_regs);
8829 #endif /* INSN_SCHEDULING */