1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 93-97, 1998 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to the Free
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
24 /* Instruction scheduling pass.
26 This pass implements list scheduling within basic blocks. It is
27 run twice: (1) after flow analysis, but before register allocation,
28 and (2) after register allocation.
30 The first run performs interblock scheduling, moving insns between
31 different blocks in the same "region", and the second runs only
32 basic block scheduling.
34 Interblock motions performed are useful motions and speculative
35 motions, including speculative loads. Motions requiring code
36 duplication are not supported. The identification of motion type
37 and the check for validity of speculative motions requires
38 construction and analysis of the function's control flow graph.
39 The scheduler works as follows:
41 We compute insn priorities based on data dependencies. Flow
42 analysis only creates a fraction of the data-dependencies we must
43 observe: namely, only those dependencies which the combiner can be
44 expected to use. For this pass, we must therefore create the
45 remaining dependencies we need to observe: register dependencies,
46 memory dependencies, dependencies to keep function calls in order,
47 and the dependence between a conditional branch and the setting of
48 condition codes are all dealt with here.
50 The scheduler first traverses the data flow graph, starting with
51 the last instruction, and proceeding to the first, assigning values
52 to insn_priority as it goes. This sorts the instructions
53 topologically by data dependence.
55 Once priorities have been established, we order the insns using
56 list scheduling. This works as follows: starting with a list of
57 all the ready insns, and sorted according to priority number, we
58 schedule the insn from the end of the list by placing its
59 predecessors in the list according to their priority order. We
60 consider this insn scheduled by setting the pointer to the "end" of
61 the list to point to the previous insn. When an insn has no
62 predecessors, we either queue it until sufficient time has elapsed
63 or add it to the ready list. As the instructions are scheduled or
64 when stalls are introduced, the queue advances and dumps insns into
65 the ready list. When all insns down to the lowest priority have
66 been scheduled, the critical path of the basic block has been made
67 as short as possible. The remaining insns are then scheduled in
70 Function unit conflicts are resolved during forward list scheduling
71 by tracking the time when each insn is committed to the schedule
72 and from that, the time the function units it uses must be free.
73 As insns on the ready list are considered for scheduling, those
74 that would result in a blockage of the already committed insns are
75 queued until no blockage will result.
77 The following list shows the order in which we want to break ties
78 among insns in the ready list:
80 1. choose insn with the longest path to end of bb, ties
82 2. choose insn with least contribution to register pressure,
84 3. prefer in-block upon interblock motion, ties broken by
85 4. prefer useful upon speculative motion, ties broken by
86 5. choose insn with largest control flow probability, ties
88 6. choose insn with the least dependences upon the previously
89 scheduled insn, or finally
90 7. choose insn with lowest UID.
92 Memory references complicate matters. Only if we can be certain
93 that memory references are not part of the data dependency graph
94 (via true, anti, or output dependence), can we move operations past
95 memory references. To first approximation, reads can be done
96 independently, while writes introduce dependencies. Better
97 approximations will yield fewer dependencies.
99 Before reload, an extended analysis of interblock data dependences
100 is required for interblock scheduling. This is performed in
101 compute_block_backward_dependences ().
103 Dependencies set up by memory references are treated in exactly the
104 same way as other dependencies, by using LOG_LINKS backward
105 dependences. LOG_LINKS are translated into INSN_DEPEND forward
106 dependences for the purpose of forward list scheduling.
108 Having optimized the critical path, we may have also unduly
109 extended the lifetimes of some registers. If an operation requires
110 that constants be loaded into registers, it is certainly desirable
111 to load those constants as early as necessary, but no earlier.
112 I.e., it will not do to load up a bunch of registers at the
113 beginning of a basic block only to use them at the end, if they
114 could be loaded later, since this may result in excessive register
117 Note that since branches are never in basic blocks, but only end
118 basic blocks, this pass will not move branches. But that is ok,
119 since we can use GNU's delayed branch scheduling pass to take care
122 Also note that no further optimizations based on algebraic
123 identities are performed, so this pass would be a good one to
124 perform instruction splitting, such as breaking up a multiply
125 instruction into shifts and adds where that is profitable.
127 Given the memory aliasing analysis that this pass should perform,
128 it should be possible to remove redundant stores to memory, and to
129 load values from registers instead of hitting memory.
131 Before reload, speculative insns are moved only if a 'proof' exists
132 that no exception will be caused by this, and if no live registers
133 exist that inhibit the motion (live registers constraints are not
134 represented by data dependence edges).
136 This pass must update information that subsequent passes expect to
137 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
138 reg_n_calls_crossed, and reg_live_length. Also, basic_block_head,
141 The information in the line number notes is carefully retained by
142 this pass. Notes that refer to the starting and ending of
143 exception regions are also carefully retained by this pass. All
144 other NOTE insns are grouped in their same relative order at the
145 beginning of basic blocks and regions that have been scheduled.
147 The main entry point for this pass is schedule_insns(), called for
148 each function. The work of the scheduler is organized in three
149 levels: (1) function level: insns are subject to splitting,
150 control-flow-graph is constructed, regions are computed (after
151 reload, each region is of one block), (2) region level: control
152 flow graph attributes required for interblock scheduling are
153 computed (dominators, reachability, etc.), data dependences and
154 priorities are computed, and (3) block level: insns in the block
155 are actually scheduled. */
160 #include "basic-block.h"
162 #include "hard-reg-set.h"
164 #include "insn-config.h"
165 #include "insn-attr.h"
168 extern char *reg_known_equiv_p;
169 extern rtx *reg_known_value;
171 #ifdef INSN_SCHEDULING
173 /* enable interblock scheduling code */
175 /* define INTERBLOCK_DEBUG for using the -fsched-max debugging facility */
176 /* #define INTERBLOCK_DEBUG */
178 /* target_units bitmask has 1 for each unit in the cpu. It should be
179 possible to compute this variable from the machine description.
180 But currently it is computed by examinning the insn list. Since
181 this is only needed for visualization, it seems an acceptable
182 solution. (For understanding the mapping of bits to units, see
183 definition of function_units[] in "insn-attrtab.c") */
185 static int target_units = 0;
187 /* issue_rate is the number of insns that can be scheduled in the same
188 machine cycle. It can be defined in the config/mach/mach.h file,
189 otherwise we set it to 1. */
191 static int issue_rate;
197 /* sched_debug_count is used for debugging the scheduler by limiting
198 the number of scheduled insns. It is controlled by the option
199 -fsched-max-N (N is a number).
201 sched-verbose controls the amount of debugging output the
202 scheduler prints. It is controlled by -fsched-verbose-N:
203 N>0 and no -DSR : the output is directed to stderr.
204 N>=10 will direct the printouts to stderr (regardless of -dSR).
206 N=2: bb's probabilities, detailed ready list info, unit/insn info.
207 N=3: rtl at abort point, control-flow, regions info.
208 N=5: dependences info.
210 max_rgn_blocks and max_region_insns limit region size for
211 interblock scheduling. They are controlled by
212 -fsched-interblock-max-blocks-N, -fsched-interblock-max-insns-N */
214 #define MAX_RGN_BLOCKS 10
215 #define MAX_RGN_INSNS 100
217 static int sched_debug_count = -1;
218 static int sched_verbose_param = 0;
219 static int sched_verbose = 0;
220 static int max_rgn_blocks = MAX_RGN_BLOCKS;
221 static int max_rgn_insns = MAX_RGN_INSNS;
223 /* nr_inter/spec counts interblock/speculative motion for the function */
224 static int nr_inter, nr_spec;
227 /* debugging file. all printouts are sent to dump, which is always set,
228 either to stderr, or to the dump listing file (-dRS). */
229 static FILE *dump = 0;
231 /* fix_sched_param() is called from toplev.c upon detection
232 of the -fsched-***-N options. */
235 fix_sched_param (param, val)
238 if (!strcmp (param, "max"))
239 sched_debug_count = ((sched_debug_count == -1) ?
240 atoi (val) : sched_debug_count);
241 else if (!strcmp (param, "verbose"))
242 sched_verbose_param = atoi (val);
243 else if (!strcmp (param, "interblock-max-blocks"))
244 max_rgn_blocks = atoi (val);
245 else if (!strcmp (param, "interblock-max-insns"))
246 max_rgn_insns = atoi (val);
248 warning ("fix_sched_param: unknown param: %s", param);
252 /* Arrays set up by scheduling for the same respective purposes as
253 similar-named arrays set up by flow analysis. We work with these
254 arrays during the scheduling pass so we can compare values against
257 Values of these arrays are copied at the end of this pass into the
258 arrays set up by flow analysis. */
259 static int *sched_reg_n_calls_crossed;
260 static int *sched_reg_live_length;
261 static int *sched_reg_basic_block;
263 /* We need to know the current block number during the post scheduling
264 update of live register information so that we can also update
265 REG_BASIC_BLOCK if a register changes blocks. */
266 static int current_block_num;
268 /* Element N is the next insn that sets (hard or pseudo) register
269 N within the current basic block; or zero, if there is no
270 such insn. Needed for new registers which may be introduced
271 by splitting insns. */
272 static rtx *reg_last_uses;
273 static rtx *reg_last_sets;
274 static regset reg_pending_sets;
275 static int reg_pending_sets_all;
277 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
278 static int *insn_luid;
279 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
281 /* Vector indexed by INSN_UID giving each instruction a priority. */
282 static int *insn_priority;
283 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
285 static short *insn_costs;
286 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
288 /* Vector indexed by INSN_UID giving an encoding of the function units
290 static short *insn_units;
291 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
293 /* Vector indexed by INSN_UID giving each instruction a register-weight.
294 This weight is an estimation of the insn contribution to registers pressure. */
295 static int *insn_reg_weight;
296 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
298 /* Vector indexed by INSN_UID giving list of insns which
299 depend upon INSN. Unlike LOG_LINKS, it represents forward dependences. */
300 static rtx *insn_depend;
301 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
303 /* Vector indexed by INSN_UID. Initialized to the number of incoming
304 edges in forward dependence graph (= number of LOG_LINKS). As
305 scheduling procedes, dependence counts are decreased. An
306 instruction moves to the ready list when its counter is zero. */
307 static int *insn_dep_count;
308 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
310 /* Vector indexed by INSN_UID giving an encoding of the blockage range
311 function. The unit and the range are encoded. */
312 static unsigned int *insn_blockage;
313 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
315 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
316 #define ENCODE_BLOCKAGE(U, R) \
317 ((((U) << UNIT_BITS) << BLOCKAGE_BITS \
318 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
319 | MAX_BLOCKAGE_COST (R))
320 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
321 #define BLOCKAGE_RANGE(B) \
322 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
323 | ((B) & BLOCKAGE_MASK))
325 /* Encodings of the `<name>_unit_blockage_range' function. */
326 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
327 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
329 #define DONE_PRIORITY -1
330 #define MAX_PRIORITY 0x7fffffff
331 #define TAIL_PRIORITY 0x7ffffffe
332 #define LAUNCH_PRIORITY 0x7f000001
333 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
334 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
336 /* Vector indexed by INSN_UID giving number of insns referring to this insn. */
337 static int *insn_ref_count;
338 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
340 /* Vector indexed by INSN_UID giving line-number note in effect for each
341 insn. For line-number notes, this indicates whether the note may be
343 static rtx *line_note;
344 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
346 /* Vector indexed by basic block number giving the starting line-number
347 for each basic block. */
348 static rtx *line_note_head;
350 /* List of important notes we must keep around. This is a pointer to the
351 last element in the list. */
352 static rtx note_list;
354 /* Regsets telling whether a given register is live or dead before the last
355 scheduled insn. Must scan the instructions once before scheduling to
356 determine what registers are live or dead at the end of the block. */
357 static regset bb_live_regs;
359 /* Regset telling whether a given register is live after the insn currently
360 being scheduled. Before processing an insn, this is equal to bb_live_regs
361 above. This is used so that we can find registers that are newly born/dead
362 after processing an insn. */
363 static regset old_live_regs;
365 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
366 during the initial scan and reused later. If there are not exactly as
367 many REG_DEAD notes in the post scheduled code as there were in the
368 prescheduled code then we trigger an abort because this indicates a bug. */
369 static rtx dead_notes;
373 /* An instruction is ready to be scheduled when all insns preceding it
374 have already been scheduled. It is important to ensure that all
375 insns which use its result will not be executed until its result
376 has been computed. An insn is maintained in one of four structures:
378 (P) the "Pending" set of insns which cannot be scheduled until
379 their dependencies have been satisfied.
380 (Q) the "Queued" set of insns that can be scheduled when sufficient
382 (R) the "Ready" list of unscheduled, uncommitted insns.
383 (S) the "Scheduled" list of insns.
385 Initially, all insns are either "Pending" or "Ready" depending on
386 whether their dependencies are satisfied.
388 Insns move from the "Ready" list to the "Scheduled" list as they
389 are committed to the schedule. As this occurs, the insns in the
390 "Pending" list have their dependencies satisfied and move to either
391 the "Ready" list or the "Queued" set depending on whether
392 sufficient time has passed to make them ready. As time passes,
393 insns move from the "Queued" set to the "Ready" list. Insns may
394 move from the "Ready" list to the "Queued" set if they are blocked
395 due to a function unit conflict.
397 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
398 insns, i.e., those that are ready, queued, and pending.
399 The "Queued" set (Q) is implemented by the variable `insn_queue'.
400 The "Ready" list (R) is implemented by the variables `ready' and
402 The "Scheduled" list (S) is the new insn chain built by this pass.
404 The transition (R->S) is implemented in the scheduling loop in
405 `schedule_block' when the best insn to schedule is chosen.
406 The transition (R->Q) is implemented in `queue_insn' when an
407 insn is found to to have a function unit conflict with the already
409 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
410 insns move from the ready list to the scheduled list.
411 The transition (Q->R) is implemented in 'queue_to_insn' as time
412 passes or stalls are introduced. */
414 /* Implement a circular buffer to delay instructions until sufficient
415 time has passed. INSN_QUEUE_SIZE is a power of two larger than
416 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
417 longest time an isnsn may be queued. */
418 static rtx insn_queue[INSN_QUEUE_SIZE];
419 static int q_ptr = 0;
420 static int q_size = 0;
421 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
422 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
424 /* Vector indexed by INSN_UID giving the minimum clock tick at which
425 the insn becomes ready. This is used to note timing constraints for
426 insns in the pending list. */
427 static int *insn_tick;
428 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
430 /* Data structure for keeping track of register information
431 during that register's life. */
440 /* Forward declarations. */
441 static void add_dependence PROTO ((rtx, rtx, enum reg_note));
442 static void remove_dependence PROTO ((rtx, rtx));
443 static rtx find_insn_list PROTO ((rtx, rtx));
444 static int insn_unit PROTO ((rtx));
445 static unsigned int blockage_range PROTO ((int, rtx));
446 static void clear_units PROTO ((void));
447 static int actual_hazard_this_instance PROTO ((int, int, rtx, int, int));
448 static void schedule_unit PROTO ((int, rtx, int));
449 static int actual_hazard PROTO ((int, rtx, int, int));
450 static int potential_hazard PROTO ((int, rtx, int));
451 static int insn_cost PROTO ((rtx, rtx, rtx));
452 static int priority PROTO ((rtx));
453 static void free_pending_lists PROTO ((void));
454 static void add_insn_mem_dependence PROTO ((rtx *, rtx *, rtx, rtx));
455 static void flush_pending_lists PROTO ((rtx, int));
456 static void sched_analyze_1 PROTO ((rtx, rtx));
457 static void sched_analyze_2 PROTO ((rtx, rtx));
458 static void sched_analyze_insn PROTO ((rtx, rtx, rtx));
459 static void sched_analyze PROTO ((rtx, rtx));
460 static void sched_note_set PROTO ((rtx, int));
461 static int rank_for_schedule PROTO ((rtx *, rtx *));
462 static void swap_sort PROTO ((rtx *, int));
463 static void queue_insn PROTO ((rtx, int));
464 static int schedule_insn PROTO ((rtx, rtx *, int, int));
465 static void create_reg_dead_note PROTO ((rtx, rtx));
466 static void attach_deaths PROTO ((rtx, rtx, int));
467 static void attach_deaths_insn PROTO ((rtx));
468 static int new_sometimes_live PROTO ((struct sometimes *, int, int));
469 static void finish_sometimes_live PROTO ((struct sometimes *, int));
470 static int schedule_block PROTO ((int, int));
471 static rtx regno_use_in PROTO ((int, rtx));
472 static void split_hard_reg_notes PROTO ((rtx, rtx, rtx));
473 static void new_insn_dead_notes PROTO ((rtx, rtx, rtx, rtx));
474 static void update_n_sets PROTO ((rtx, int));
475 static void update_flow_info PROTO ((rtx, rtx, rtx, rtx));
477 /* Main entry point of this file. */
478 void schedule_insns PROTO ((FILE *));
480 /* Mapping of insns to their original block prior to scheduling. */
481 static int *insn_orig_block;
482 #define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
484 /* Some insns (e.g. call) are not allowed to move across blocks. */
485 static char *cant_move;
486 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
488 /* Control flow graph edges are kept in circular lists. */
497 static edge *edge_table;
499 #define NEXT_IN(edge) (edge_table[edge].next_in)
500 #define NEXT_OUT(edge) (edge_table[edge].next_out)
501 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
502 #define TO_BLOCK(edge) (edge_table[edge].to_block)
504 /* Number of edges in the control flow graph. (in fact larger than
505 that by 1, since edge 0 is unused.) */
508 /* Circular list of incoming/outgoing edges of a block */
509 static int *in_edges;
510 static int *out_edges;
512 #define IN_EDGES(block) (in_edges[block])
513 #define OUT_EDGES(block) (out_edges[block])
515 /* List of labels which cannot be deleted, needed for control
516 flow graph construction. */
517 extern rtx forced_labels;
520 static char is_cfg_nonregular PROTO ((void));
521 static int uses_reg_or_mem PROTO ((rtx));
522 void debug_control_flow PROTO ((void));
523 static void build_control_flow PROTO ((void));
524 static void build_jmp_edges PROTO ((rtx, int));
525 static void new_edge PROTO ((int, int));
528 /* A region is the main entity for interblock scheduling: insns
529 are allowed to move between blocks in the same region, along
530 control flow graph edges, in the 'up' direction. */
533 int rgn_nr_blocks; /* number of blocks in region */
534 int rgn_blocks; /* blocks in the region (actually index in rgn_bb_table) */
538 /* Number of regions in the procedure */
539 static int nr_regions;
541 /* Table of region descriptions */
542 static region *rgn_table;
544 /* Array of lists of regions' blocks */
545 static int *rgn_bb_table;
547 /* Topological order of blocks in the region (if b2 is reachable from
548 b1, block_to_bb[b2] > block_to_bb[b1]).
549 Note: A basic block is always referred to by either block or b,
550 while its topological order name (in the region) is refered to by
553 static int *block_to_bb;
555 /* The number of the region containing a block. */
556 static int *containing_rgn;
558 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
559 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
560 #define BLOCK_TO_BB(block) (block_to_bb[block])
561 #define CONTAINING_RGN(block) (containing_rgn[block])
563 void debug_regions PROTO ((void));
564 static void find_single_block_region PROTO ((void));
565 static void find_rgns PROTO ((void));
566 static int too_large PROTO ((int, int *, int *));
568 extern void debug_live PROTO ((int, int));
570 /* Blocks of the current region being scheduled. */
571 static int current_nr_blocks;
572 static int current_blocks;
574 /* The mapping from bb to block */
575 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
578 /* Bit vectors and bitset operations are needed for computations on
579 the control flow graph. */
581 typedef unsigned HOST_WIDE_INT *bitset;
584 int *first_member; /* pointer to the list start in bitlst_table. */
585 int nr_members; /* the number of members of the bit list. */
589 static int bitlst_table_last;
590 static int bitlst_table_size;
591 static int *bitlst_table;
593 static char bitset_member PROTO ((bitset, int, int));
594 static void extract_bitlst PROTO ((bitset, int, bitlst *));
596 /* target info declarations.
598 The block currently being scheduled is referred to as the "target" block,
599 while other blocks in the region from which insns can be moved to the
600 target are called "source" blocks. The candidate structure holds info
601 about such sources: are they valid? Speculative? Etc. */
602 typedef bitlst bblst;
613 static candidate *candidate_table;
615 /* A speculative motion requires checking live information on the path
616 from 'source' to 'target'. The split blocks are those to be checked.
617 After a speculative motion, live information should be modified in
620 Lists of split and update blocks for each candidate of the current
621 target are in array bblst_table */
622 static int *bblst_table, bblst_size, bblst_last;
624 #define IS_VALID(src) ( candidate_table[src].is_valid )
625 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
626 #define SRC_PROB(src) ( candidate_table[src].src_prob )
628 /* The bb being currently scheduled. */
629 static int target_bb;
632 typedef bitlst edgelst;
634 /* target info functions */
635 static void split_edges PROTO ((int, int, edgelst *));
636 static void compute_trg_info PROTO ((int));
637 void debug_candidate PROTO ((int));
638 void debug_candidates PROTO ((int));
641 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
642 typedef bitset bbset;
644 /* Number of words of the bbset. */
645 static int bbset_size;
647 /* Dominators array: dom[i] contains the bbset of dominators of
648 bb i in the region. */
651 /* bb 0 is the only region entry */
652 #define IS_RGN_ENTRY(bb) (!bb)
654 /* Is bb_src dominated by bb_trg. */
655 #define IS_DOMINATED(bb_src, bb_trg) \
656 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
658 /* Probability: Prob[i] is a float in [0, 1] which is the probability
659 of bb i relative to the region entry. */
662 /* The probability of bb_src, relative to bb_trg. Note, that while the
663 'prob[bb]' is a float in [0, 1], this macro returns an integer
665 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
668 /* Bit-set of edges, where bit i stands for edge i. */
669 typedef bitset edgeset;
671 /* Number of edges in the region. */
672 static int rgn_nr_edges;
674 /* Array of size rgn_nr_edges. */
675 static int *rgn_edges;
677 /* Number of words in an edgeset. */
678 static int edgeset_size;
680 /* Mapping from each edge in the graph to its number in the rgn. */
681 static int *edge_to_bit;
682 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
684 /* The split edges of a source bb is different for each target
685 bb. In order to compute this efficiently, the 'potential-split edges'
686 are computed for each bb prior to scheduling a region. This is actually
687 the split edges of each bb relative to the region entry.
689 pot_split[bb] is the set of potential split edges of bb. */
690 static edgeset *pot_split;
692 /* For every bb, a set of its ancestor edges. */
693 static edgeset *ancestor_edges;
695 static void compute_dom_prob_ps PROTO ((int));
697 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
698 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
699 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
700 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
702 /* parameters affecting the decision of rank_for_schedule() */
703 #define MIN_DIFF_PRIORITY 2
704 #define MIN_PROBABILITY 40
705 #define MIN_PROB_DIFF 10
707 /* speculative scheduling functions */
708 static int check_live_1 PROTO ((int, rtx));
709 static void update_live_1 PROTO ((int, rtx));
710 static int check_live PROTO ((rtx, int));
711 static void update_live PROTO ((rtx, int));
712 static void set_spec_fed PROTO ((rtx));
713 static int is_pfree PROTO ((rtx, int, int));
714 static int find_conditional_protection PROTO ((rtx, int));
715 static int is_conditionally_protected PROTO ((rtx, int, int));
716 static int may_trap_exp PROTO ((rtx, int));
717 static int haifa_classify_insn PROTO ((rtx));
718 static int is_exception_free PROTO ((rtx, int, int));
720 static char find_insn_mem_list PROTO ((rtx, rtx, rtx, rtx));
721 static void compute_block_forward_dependences PROTO ((int));
722 static void init_rgn_data_dependences PROTO ((int));
723 static void add_branch_dependences PROTO ((rtx, rtx));
724 static void compute_block_backward_dependences PROTO ((int));
725 void debug_dependencies PROTO ((void));
727 /* Notes handling mechanism:
728 =========================
729 Generally, NOTES are saved before scheduling and restored after scheduling.
730 The scheduler distinguishes between three types of notes:
732 (1) LINE_NUMBER notes, generated and used for debugging. Here,
733 before scheduling a region, a pointer to the LINE_NUMBER note is
734 added to the insn following it (in save_line_notes()), and the note
735 is removed (in rm_line_notes() and unlink_line_notes()). After
736 scheduling the region, this pointer is used for regeneration of
737 the LINE_NUMBER note (in restore_line_notes()).
739 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
740 Before scheduling a region, a pointer to the note is added to the insn
741 that follows or precedes it. (This happens as part of the data dependence
742 computation). After scheduling an insn, the pointer contained in it is
743 used for regenerating the corresponding note (in reemit_notes).
745 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
746 these notes are put in a list (in rm_other_notes() and
747 unlink_other_notes ()). After scheduling the block, these notes are
748 inserted at the beginning of the block (in schedule_block()). */
750 static rtx unlink_other_notes PROTO ((rtx, rtx));
751 static rtx unlink_line_notes PROTO ((rtx, rtx));
752 static void rm_line_notes PROTO ((int));
753 static void save_line_notes PROTO ((int));
754 static void restore_line_notes PROTO ((int));
755 static void rm_redundant_line_notes PROTO ((void));
756 static void rm_other_notes PROTO ((rtx, rtx));
757 static rtx reemit_notes PROTO ((rtx, rtx));
759 static void get_block_head_tail PROTO ((int, rtx *, rtx *));
761 static void find_pre_sched_live PROTO ((int));
762 static void find_post_sched_live PROTO ((int));
763 static void update_reg_usage PROTO ((void));
765 void debug_ready_list PROTO ((rtx[], int));
766 static void init_target_units PROTO (());
767 static void insn_print_units PROTO ((rtx));
768 static int get_visual_tbl_length PROTO (());
769 static void init_block_visualization PROTO (());
770 static void print_block_visualization PROTO ((int, char *));
771 static void visualize_scheduled_insns PROTO ((int, int));
772 static void visualize_no_unit PROTO ((rtx));
773 static void visualize_stall_cycles PROTO ((int, int));
774 static void print_exp PROTO ((char *, rtx, int));
775 static void print_value PROTO ((char *, rtx, int));
776 static void print_pattern PROTO ((char *, rtx, int));
777 static void print_insn PROTO ((char *, rtx, int));
778 void debug_reg_vector PROTO ((regset));
780 static rtx move_insn1 PROTO ((rtx, rtx));
781 static rtx move_insn PROTO ((rtx, rtx));
782 static rtx group_leader PROTO ((rtx));
783 static int set_priorities PROTO ((int));
784 static void init_rtx_vector PROTO ((rtx **, rtx *, int, int));
785 static void schedule_region PROTO ((int));
786 static void split_block_insns PROTO ((int));
788 #endif /* INSN_SCHEDULING */
790 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
792 /* Helper functions for instruction scheduling. */
794 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
795 static rtx unused_insn_list;
797 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
798 static rtx unused_expr_list;
800 static void free_list PROTO ((rtx *, rtx *));
801 static rtx alloc_INSN_LIST PROTO ((rtx, rtx));
802 static rtx alloc_EXPR_LIST PROTO ((int, rtx, rtx));
805 free_list (listp, unused_listp)
806 rtx *listp, *unused_listp;
808 register rtx link, prev_link;
814 link = XEXP (prev_link, 1);
819 link = XEXP (link, 1);
822 XEXP (prev_link, 1) = *unused_listp;
823 *unused_listp = *listp;
828 alloc_INSN_LIST (val, next)
833 if (unused_insn_list)
835 r = unused_insn_list;
836 unused_insn_list = XEXP (r, 1);
839 PUT_REG_NOTE_KIND (r, VOIDmode);
842 r = gen_rtx_INSN_LIST (VOIDmode, val, next);
848 alloc_EXPR_LIST (kind, val, next)
854 if (unused_insn_list)
856 r = unused_insn_list;
857 unused_insn_list = XEXP (r, 1);
860 PUT_REG_NOTE_KIND (r, kind);
863 r = gen_rtx_EXPR_LIST (kind, val, next);
868 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
869 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
870 of dependence that this link represents. */
873 add_dependence (insn, elem, dep_type)
876 enum reg_note dep_type;
880 /* Don't depend an insn on itself. */
884 /* If elem is part of a sequence that must be scheduled together, then
885 make the dependence point to the last insn of the sequence.
886 When HAVE_cc0, it is possible for NOTEs to exist between users and
887 setters of the condition codes, so we must skip past notes here.
888 Otherwise, NOTEs are impossible here. */
890 next = NEXT_INSN (elem);
893 while (next && GET_CODE (next) == NOTE)
894 next = NEXT_INSN (next);
897 if (next && SCHED_GROUP_P (next)
898 && GET_CODE (next) != CODE_LABEL)
900 /* Notes will never intervene here though, so don't bother checking
902 /* We must reject CODE_LABELs, so that we don't get confused by one
903 that has LABEL_PRESERVE_P set, which is represented by the same
904 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
906 while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
907 && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
908 next = NEXT_INSN (next);
910 /* Again, don't depend an insn on itself. */
914 /* Make the dependence to NEXT, the last insn of the group, instead
915 of the original ELEM. */
919 #ifdef INSN_SCHEDULING
920 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
921 No need for interblock dependences with calls, since
922 calls are not moved between blocks. Note: the edge where
923 elem is a CALL is still required. */
924 if (GET_CODE (insn) == CALL_INSN
925 && (INSN_BB (elem) != INSN_BB (insn)))
930 /* Check that we don't already have this dependence. */
931 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
932 if (XEXP (link, 0) == elem)
934 /* If this is a more restrictive type of dependence than the existing
935 one, then change the existing dependence to this type. */
936 if ((int) dep_type < (int) REG_NOTE_KIND (link))
937 PUT_REG_NOTE_KIND (link, dep_type);
940 /* Might want to check one level of transitivity to save conses. */
942 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
943 LOG_LINKS (insn) = link;
945 /* Insn dependency, not data dependency. */
946 PUT_REG_NOTE_KIND (link, dep_type);
949 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
950 of INSN. Abort if not found. */
953 remove_dependence (insn, elem)
957 rtx prev, link, next;
960 for (prev = 0, link = LOG_LINKS (insn); link; link = next)
962 next = XEXP (link, 1);
963 if (XEXP (link, 0) == elem)
966 XEXP (prev, 1) = next;
968 LOG_LINKS (insn) = next;
970 XEXP (link, 1) = unused_insn_list;
971 unused_insn_list = link;
984 #ifndef INSN_SCHEDULING
986 schedule_insns (dump_file)
995 /* Computation of memory dependencies. */
997 /* The *_insns and *_mems are paired lists. Each pending memory operation
998 will have a pointer to the MEM rtx on one list and a pointer to the
999 containing insn on the other list in the same place in the list. */
1001 /* We can't use add_dependence like the old code did, because a single insn
1002 may have multiple memory accesses, and hence needs to be on the list
1003 once for each memory access. Add_dependence won't let you add an insn
1004 to a list more than once. */
1006 /* An INSN_LIST containing all insns with pending read operations. */
1007 static rtx pending_read_insns;
1009 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
1010 static rtx pending_read_mems;
1012 /* An INSN_LIST containing all insns with pending write operations. */
1013 static rtx pending_write_insns;
1015 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
1016 static rtx pending_write_mems;
1018 /* Indicates the combined length of the two pending lists. We must prevent
1019 these lists from ever growing too large since the number of dependencies
1020 produced is at least O(N*N), and execution time is at least O(4*N*N), as
1021 a function of the length of these pending lists. */
1023 static int pending_lists_length;
1025 /* The last insn upon which all memory references must depend.
1026 This is an insn which flushed the pending lists, creating a dependency
1027 between it and all previously pending memory references. This creates
1028 a barrier (or a checkpoint) which no memory reference is allowed to cross.
1030 This includes all non constant CALL_INSNs. When we do interprocedural
1031 alias analysis, this restriction can be relaxed.
1032 This may also be an INSN that writes memory if the pending lists grow
1035 static rtx last_pending_memory_flush;
1037 /* The last function call we have seen. All hard regs, and, of course,
1038 the last function call, must depend on this. */
1040 static rtx last_function_call;
1042 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
1043 that does not already cross a call. We create dependencies between each
1044 of those insn and the next call insn, to ensure that they won't cross a call
1045 after scheduling is done. */
1047 static rtx sched_before_next_call;
1049 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1050 so that insns independent of the last scheduled insn will be preferred
1051 over dependent instructions. */
1053 static rtx last_scheduled_insn;
1055 /* Data structures for the computation of data dependences in a regions. We
1056 keep one copy of each of the declared above variables for each bb in the
1057 region. Before analyzing the data dependences for a bb, its variables
1058 are initialized as a function of the variables of its predecessors. When
1059 the analysis for a bb completes, we save the contents of each variable X
1060 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
1061 copied to bb_pending_read_insns[bb]. Another change is that few
1062 variables are now a list of insns rather than a single insn:
1063 last_pending_memory_flash, last_function_call, reg_last_sets. The
1064 manipulation of these variables was changed appropriately. */
1066 static rtx **bb_reg_last_uses;
1067 static rtx **bb_reg_last_sets;
1069 static rtx *bb_pending_read_insns;
1070 static rtx *bb_pending_read_mems;
1071 static rtx *bb_pending_write_insns;
1072 static rtx *bb_pending_write_mems;
1073 static int *bb_pending_lists_length;
1075 static rtx *bb_last_pending_memory_flush;
1076 static rtx *bb_last_function_call;
1077 static rtx *bb_sched_before_next_call;
1079 /* functions for construction of the control flow graph. */
1081 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1082 Estimate in nr_edges the number of edges on the graph.
1083 We decide not to build the control flow graph if there is possibly more
1084 than one entry to the function, or if computed branches exist. */
1087 is_cfg_nonregular ()
1093 rtx nonlocal_label_list = nonlocal_label_rtx_list ();
1095 /* check for non local labels */
1096 if (nonlocal_label_list)
1101 /* check for labels which cannot be deleted */
1107 /* check for labels which probably cannot be deleted */
1108 if (exception_handler_labels)
1113 /* check for labels referred to other thn by jumps */
1114 for (b = 0; b < n_basic_blocks; b++)
1115 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
1117 code = GET_CODE (insn);
1118 if (GET_RTX_CLASS (code) == 'i')
1122 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1123 if (REG_NOTE_KIND (note) == REG_LABEL)
1129 if (insn == basic_block_end[b])
1135 /* check for computed branches */
1136 for (b = 0; b < n_basic_blocks; b++)
1138 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
1141 if (GET_CODE (insn) == JUMP_INSN)
1143 rtx pat = PATTERN (insn);
1146 if (GET_CODE (pat) == PARALLEL)
1148 int len = XVECLEN (pat, 0);
1149 int has_use_labelref = 0;
1151 for (i = len - 1; i >= 0; i--)
1152 if (GET_CODE (XVECEXP (pat, 0, i)) == USE
1153 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
1157 has_use_labelref = 1;
1160 if (!has_use_labelref)
1161 for (i = len - 1; i >= 0; i--)
1162 if (GET_CODE (XVECEXP (pat, 0, i)) == SET
1163 && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
1164 && uses_reg_or_mem (SET_SRC (XVECEXP (pat, 0, i))))
1169 /* check for branch table */
1170 else if (GET_CODE (pat) == ADDR_VEC
1171 || GET_CODE (pat) == ADDR_DIFF_VEC)
1173 int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
1174 int len = XVECLEN (pat, diff_vec_p);
1180 /* check for computed branch */
1181 if (GET_CODE (pat) == SET
1182 && SET_DEST (pat) == pc_rtx
1183 && uses_reg_or_mem (SET_SRC (pat)))
1190 if (insn == basic_block_end[b])
1195 /* count for the fallthrough edges */
1196 for (b = 0; b < n_basic_blocks; b++)
1198 for (insn = PREV_INSN (basic_block_head[b]);
1199 insn && GET_CODE (insn) == NOTE; insn = PREV_INSN (insn))
1202 if (!insn && b != 0)
1204 else if (insn && GET_CODE (insn) != BARRIER)
1214 /* Returns 1 if x uses a reg or a mem (function was taken from flow.c).
1215 x is a target of a jump. Used for the detection of computed
1216 branches. For each label seen, updates the edges estimation
1217 counter nr_edges. */
1223 enum rtx_code code = GET_CODE (x);
1231 && !(GET_CODE (XEXP (x, 0)) == SYMBOL_REF
1232 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0))))
1235 if (code == IF_THEN_ELSE)
1237 if (uses_reg_or_mem (XEXP (x, 1))
1238 || uses_reg_or_mem (XEXP (x, 2)))
1244 if (code == LABEL_REF)
1251 fmt = GET_RTX_FORMAT (code);
1252 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1255 && uses_reg_or_mem (XEXP (x, i)))
1259 for (j = 0; j < XVECLEN (x, i); j++)
1260 if (uses_reg_or_mem (XVECEXP (x, i, j)))
1268 /* Print the control flow graph, for debugging purposes.
1269 Callable from the debugger. */
1272 debug_control_flow ()
1276 fprintf (dump, ";; --------- CONTROL FLOW GRAPH --------- \n\n");
1278 for (i = 0; i < n_basic_blocks; i++)
1280 fprintf (dump, ";;\tBasic block %d: first insn %d, last %d.\n",
1282 INSN_UID (basic_block_head[i]),
1283 INSN_UID (basic_block_end[i]));
1285 fprintf (dump, ";;\tPredecessor blocks:");
1286 for (e = IN_EDGES (i); e; e = next)
1288 fprintf (dump, " %d", FROM_BLOCK (e));
1292 if (next == IN_EDGES (i))
1296 fprintf (dump, "\n;;\tSuccesor blocks:");
1297 for (e = OUT_EDGES (i); e; e = next)
1299 fprintf (dump, " %d", TO_BLOCK (e));
1301 next = NEXT_OUT (e);
1303 if (next == OUT_EDGES (i))
1307 fprintf (dump, " \n\n");
1313 /* build the control flow graph. (also set nr_edges accurately) */
1316 build_control_flow ()
1321 for (i = 0; i < n_basic_blocks; i++)
1325 insn = basic_block_end[i];
1326 if (GET_CODE (insn) == JUMP_INSN)
1328 build_jmp_edges (PATTERN (insn), i);
1331 for (insn = PREV_INSN (basic_block_head[i]);
1332 insn && GET_CODE (insn) == NOTE; insn = PREV_INSN (insn))
1335 /* build fallthrough edges */
1336 if (!insn && i != 0)
1337 new_edge (i - 1, i);
1338 else if (insn && GET_CODE (insn) != BARRIER)
1339 new_edge (i - 1, i);
1342 /* increment by 1, since edge 0 is unused. */
1348 /* construct edges in the control flow graph, from 'source' block, to
1349 blocks refered to by 'pattern'. */
1353 build_jmp_edges (pattern, source)
1357 register RTX_CODE code;
1361 code = GET_CODE (pattern);
1363 if (code == LABEL_REF)
1365 register rtx label = XEXP (pattern, 0);
1366 register int target;
1368 /* This can happen as a result of a syntax error
1369 and a diagnostic has already been printed. */
1370 if (INSN_UID (label) == 0)
1373 target = INSN_BLOCK (label);
1374 new_edge (source, target);
1379 /* proper handling of ADDR_DIFF_VEC: do not add a non-existing edge
1380 from the block containing the branch-on-table, to itself. */
1381 if (code == ADDR_VEC
1382 || code == ADDR_DIFF_VEC)
1384 int diff_vec_p = GET_CODE (pattern) == ADDR_DIFF_VEC;
1385 int len = XVECLEN (pattern, diff_vec_p);
1388 for (k = 0; k < len; k++)
1390 rtx tem = XVECEXP (pattern, diff_vec_p, k);
1392 build_jmp_edges (tem, source);
1396 fmt = GET_RTX_FORMAT (code);
1397 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1400 build_jmp_edges (XEXP (pattern, i), source);
1404 for (j = 0; j < XVECLEN (pattern, i); j++)
1405 build_jmp_edges (XVECEXP (pattern, i, j), source);
1411 /* construct an edge in the control flow graph, from 'source' to 'target'. */
1414 new_edge (source, target)
1418 int curr_edge, fst_edge;
1420 /* check for duplicates */
1421 fst_edge = curr_edge = OUT_EDGES (source);
1424 if (FROM_BLOCK (curr_edge) == source
1425 && TO_BLOCK (curr_edge) == target)
1430 curr_edge = NEXT_OUT (curr_edge);
1432 if (fst_edge == curr_edge)
1438 FROM_BLOCK (e) = source;
1439 TO_BLOCK (e) = target;
1441 if (OUT_EDGES (source))
1443 next_edge = NEXT_OUT (OUT_EDGES (source));
1444 NEXT_OUT (OUT_EDGES (source)) = e;
1445 NEXT_OUT (e) = next_edge;
1449 OUT_EDGES (source) = e;
1453 if (IN_EDGES (target))
1455 next_edge = NEXT_IN (IN_EDGES (target));
1456 NEXT_IN (IN_EDGES (target)) = e;
1457 NEXT_IN (e) = next_edge;
1461 IN_EDGES (target) = e;
1467 /* BITSET macros for operations on the control flow graph. */
1469 /* Compute bitwise union of two bitsets. */
1470 #define BITSET_UNION(set1, set2, len) \
1471 do { register bitset tp = set1, sp = set2; \
1473 for (i = 0; i < len; i++) \
1474 *(tp++) |= *(sp++); } while (0)
1476 /* Compute bitwise intersection of two bitsets. */
1477 #define BITSET_INTER(set1, set2, len) \
1478 do { register bitset tp = set1, sp = set2; \
1480 for (i = 0; i < len; i++) \
1481 *(tp++) &= *(sp++); } while (0)
1483 /* Compute bitwise difference of two bitsets. */
1484 #define BITSET_DIFFER(set1, set2, len) \
1485 do { register bitset tp = set1, sp = set2; \
1487 for (i = 0; i < len; i++) \
1488 *(tp++) &= ~*(sp++); } while (0)
1490 /* Inverts every bit of bitset 'set' */
1491 #define BITSET_INVERT(set, len) \
1492 do { register bitset tmpset = set; \
1494 for (i = 0; i < len; i++, tmpset++) \
1495 *tmpset = ~*tmpset; } while (0)
1497 /* Turn on the index'th bit in bitset set. */
1498 #define BITSET_ADD(set, index, len) \
1500 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1503 set[index/HOST_BITS_PER_WIDE_INT] |= \
1504 1 << (index % HOST_BITS_PER_WIDE_INT); \
1507 /* Turn off the index'th bit in set. */
1508 #define BITSET_REMOVE(set, index, len) \
1510 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1513 set[index/HOST_BITS_PER_WIDE_INT] &= \
1514 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1518 /* Check if the index'th bit in bitset set is on. */
1521 bitset_member (set, index, len)
1525 if (index >= HOST_BITS_PER_WIDE_INT * len)
1527 return (set[index / HOST_BITS_PER_WIDE_INT] &
1528 1 << (index % HOST_BITS_PER_WIDE_INT)) ? 1 : 0;
1532 /* Translate a bit-set SET to a list BL of the bit-set members. */
1535 extract_bitlst (set, len, bl)
1541 unsigned HOST_WIDE_INT word;
1543 /* bblst table space is reused in each call to extract_bitlst */
1544 bitlst_table_last = 0;
1546 bl->first_member = &bitlst_table[bitlst_table_last];
1549 for (i = 0; i < len; i++)
1552 offset = i * HOST_BITS_PER_WIDE_INT;
1553 for (j = 0; word; j++)
1557 bitlst_table[bitlst_table_last++] = offset;
1568 /* functions for the construction of regions */
1570 /* Print the regions, for debugging purposes. Callable from debugger. */
1577 fprintf (dump, "\n;; ------------ REGIONS ----------\n\n");
1578 for (rgn = 0; rgn < nr_regions; rgn++)
1580 fprintf (dump, ";;\trgn %d nr_blocks %d:\n", rgn,
1581 rgn_table[rgn].rgn_nr_blocks);
1582 fprintf (dump, ";;\tbb/block: ");
1584 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
1586 current_blocks = RGN_BLOCKS (rgn);
1588 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
1591 fprintf (dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
1594 fprintf (dump, "\n\n");
1599 /* Build a single block region for each basic block in the function.
1600 This allows for using the same code for interblock and basic block
1604 find_single_block_region ()
1608 for (i = 0; i < n_basic_blocks; i++)
1610 rgn_bb_table[i] = i;
1611 RGN_NR_BLOCKS (i) = 1;
1613 CONTAINING_RGN (i) = i;
1614 BLOCK_TO_BB (i) = 0;
1616 nr_regions = n_basic_blocks;
1620 /* Update number of blocks and the estimate for number of insns
1621 in the region. Return 1 if the region is "too large" for interblock
1622 scheduling (compile time considerations), otherwise return 0. */
1625 too_large (block, num_bbs, num_insns)
1626 int block, *num_bbs, *num_insns;
1629 (*num_insns) += (INSN_LUID (basic_block_end[block]) -
1630 INSN_LUID (basic_block_head[block]));
1631 if ((*num_bbs > max_rgn_blocks) || (*num_insns > max_rgn_insns))
1638 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1639 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1640 loop containing blk. */
1641 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1643 if (max_hdr[blk] == -1) \
1644 max_hdr[blk] = hdr; \
1645 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1647 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1649 inner[max_hdr[blk]] = 0; \
1650 max_hdr[blk] = hdr; \
1655 /* Find regions for interblock scheduling: a loop-free procedure, a reducible
1656 inner loop, or a basic block not contained in any other region.
1657 The procedures control flow graph is traversed twice.
1658 First traversal, a DFS, finds the headers of inner loops in the graph,
1659 and verifies that there are no unreacable blocks.
1660 Second traversal processes headers of inner loops, checking that the
1661 loop is reducible. The loop blocks that form a region are put into the
1662 region's blocks list in topological order.
1664 The following variables are changed by the function: rgn_nr, rgn_table,
1665 rgn_bb_table, block_to_bb and containing_rgn. */
1670 int *max_hdr, *dfs_nr, *stack, *queue, *degree;
1671 char *header, *inner, *passed, *in_stack, *in_queue, no_loops = 1;
1672 int node, child, loop_head, i, j, fst_edge, head, tail;
1673 int count = 0, sp, idx = 0, current_edge = out_edges[0];
1674 int num_bbs, num_insns;
1675 int too_large_failure;
1679 The following data structures are computed by the first traversal and
1680 are used by the second traversal:
1681 header[i] - flag set if the block i is the header of a loop.
1682 inner[i] - initially set. It is reset if the the block i is the header
1683 of a non-inner loop.
1684 max_hdr[i] - the header of the inner loop containing block i.
1685 (for a block i not in an inner loop it may be -1 or the
1686 header of the most inner loop containing the block).
1688 These data structures are used by the first traversal only:
1689 stack - non-recursive DFS implementation which uses a stack of edges.
1690 sp - top of the stack of edges
1691 dfs_nr[i] - the DFS ordering of block i.
1692 in_stack[i] - flag set if the block i is in the DFS stack.
1694 These data structures are used by the second traversal only:
1695 queue - queue containing the blocks of the current region.
1696 head and tail - queue boundaries.
1697 in_queue[i] - flag set if the block i is in queue */
1699 /* function's inner arrays allocation and initialization */
1700 max_hdr = (int *) alloca (n_basic_blocks * sizeof (int));
1701 dfs_nr = (int *) alloca (n_basic_blocks * sizeof (int));
1702 bzero ((char *) dfs_nr, n_basic_blocks * sizeof (int));
1703 stack = (int *) alloca (nr_edges * sizeof (int));
1704 queue = (int *) alloca (n_basic_blocks * sizeof (int));
1706 inner = (char *) alloca (n_basic_blocks * sizeof (char));
1707 header = (char *) alloca (n_basic_blocks * sizeof (char));
1708 bzero ((char *) header, n_basic_blocks * sizeof (char));
1709 passed = (char *) alloca (nr_edges * sizeof (char));
1710 bzero ((char *) passed, nr_edges * sizeof (char));
1711 in_stack = (char *) alloca (nr_edges * sizeof (char));
1712 bzero ((char *) in_stack, nr_edges * sizeof (char));
1713 reachable = (char *) alloca (n_basic_blocks * sizeof (char));
1714 bzero ((char *) reachable, n_basic_blocks * sizeof (char));
1716 in_queue = (char *) alloca (n_basic_blocks * sizeof (char));
1718 for (i = 0; i < n_basic_blocks; i++)
1724 /* First traversal: DFS, finds inner loops in control flow graph */
1730 if (current_edge == 0 || passed[current_edge])
1732 /* Here, if current_edge < 0, this is a leaf block.
1733 Otherwise current_edge was already passed. Note that in
1734 the latter case, not only current_edge but also all its
1735 NEXT_OUT edges are also passed. We have to "climb up on
1736 edges in the stack", looking for the first (already
1737 passed) edge whose NEXT_OUT was not passed yet. */
1739 while (sp >= 0 && (current_edge == 0 || passed[current_edge]))
1741 current_edge = stack[sp--];
1742 node = FROM_BLOCK (current_edge);
1743 child = TO_BLOCK (current_edge);
1744 in_stack[child] = 0;
1745 if (max_hdr[child] >= 0 && in_stack[max_hdr[child]])
1746 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1747 current_edge = NEXT_OUT (current_edge);
1750 /* stack empty - the whole graph is traversed. */
1751 if (sp < 0 && passed[current_edge])
1756 node = FROM_BLOCK (current_edge);
1757 dfs_nr[node] = ++count;
1759 child = TO_BLOCK (current_edge);
1760 reachable[child] = 1;
1762 /* found a loop header */
1763 if (in_stack[child])
1767 max_hdr[child] = child;
1768 UPDATE_LOOP_RELATIONS (node, child);
1769 passed[current_edge] = 1;
1770 current_edge = NEXT_OUT (current_edge);
1774 /* the child was already visited once, no need to go down from
1775 it, everything is traversed there. */
1778 if (max_hdr[child] >= 0 && in_stack[max_hdr[child]])
1779 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1780 passed[current_edge] = 1;
1781 current_edge = NEXT_OUT (current_edge);
1785 /* this is a step down in the dfs traversal */
1786 stack[++sp] = current_edge;
1787 passed[current_edge] = 1;
1788 current_edge = OUT_EDGES (child);
1791 /* if there are unreachable blocks, or more than one entry to
1792 the subroutine, give up on interblock scheduling */
1793 for (i = 1; i < n_basic_blocks; i++)
1795 if (reachable[i] == 0)
1797 find_single_block_region ();
1798 if (sched_verbose >= 3)
1799 fprintf (stderr, "sched: warning: found an unreachable block %d \n", i);
1804 /* Second travsersal: find reducible inner loops, and sort
1805 topologically the blocks of each region */
1806 degree = dfs_nr; /* reuse dfs_nr array - it is not needed anymore */
1807 bzero ((char *) in_queue, n_basic_blocks * sizeof (char));
1812 /* compute the in-degree of every block in the graph */
1813 for (i = 0; i < n_basic_blocks; i++)
1815 fst_edge = IN_EDGES (i);
1819 current_edge = NEXT_IN (fst_edge);
1820 while (fst_edge != current_edge)
1823 current_edge = NEXT_IN (current_edge);
1830 /* pass through all graph blocks, looking for headers of inner loops */
1831 for (i = 0; i < n_basic_blocks; i++)
1834 if (header[i] && inner[i])
1837 /* i is a header of a potentially reducible inner loop, or
1838 block 0 in a subroutine with no loops at all */
1840 too_large_failure = 0;
1841 loop_head = max_hdr[i];
1843 /* decrease in_degree of all i's successors, (this is needed
1844 for the topological ordering) */
1845 fst_edge = current_edge = OUT_EDGES (i);
1850 --degree[TO_BLOCK (current_edge)];
1851 current_edge = NEXT_OUT (current_edge);
1853 while (fst_edge != current_edge);
1856 /* estimate # insns, and count # blocks in the region. */
1858 num_insns = INSN_LUID (basic_block_end[i]) - INSN_LUID (basic_block_head[i]);
1861 /* find all loop latches, if it is a true loop header, or
1862 all leaves if the graph has no loops at all */
1865 for (j = 0; j < n_basic_blocks; j++)
1866 if (out_edges[j] == 0) /* a leaf */
1871 if (too_large (j, &num_bbs, &num_insns))
1873 too_large_failure = 1;
1880 fst_edge = current_edge = IN_EDGES (i);
1883 node = FROM_BLOCK (current_edge);
1884 if (max_hdr[node] == loop_head && node != i) /* a latch */
1886 queue[++tail] = node;
1889 if (too_large (node, &num_bbs, &num_insns))
1891 too_large_failure = 1;
1895 current_edge = NEXT_IN (current_edge);
1897 while (fst_edge != current_edge);
1900 /* Put in queue[] all blocks that belong to the loop. Check
1901 that the loop is reducible, traversing back from the loop
1902 latches up to the loop header. */
1903 while (head < tail && !too_large_failure)
1905 child = queue[++head];
1906 fst_edge = current_edge = IN_EDGES (child);
1909 node = FROM_BLOCK (current_edge);
1911 if (max_hdr[node] != loop_head)
1912 { /* another entry to loop, it is irreducible */
1916 else if (!in_queue[node] && node != i)
1918 queue[++tail] = node;
1921 if (too_large (node, &num_bbs, &num_insns))
1923 too_large_failure = 1;
1927 current_edge = NEXT_IN (current_edge);
1929 while (fst_edge != current_edge);
1932 if (tail >= 0 && !too_large_failure)
1934 /* Place the loop header into list of region blocks */
1936 rgn_bb_table[idx] = i;
1937 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1938 RGN_BLOCKS (nr_regions) = idx++;
1939 CONTAINING_RGN (i) = nr_regions;
1940 BLOCK_TO_BB (i) = count = 0;
1942 /* remove blocks from queue[], (in topological order), when
1943 their in_degree becomes 0. We scan the queue over and
1944 over again until it is empty. Note: there may be a more
1945 efficient way to do it. */
1950 child = queue[head];
1951 if (degree[child] == 0)
1954 rgn_bb_table[idx++] = child;
1955 BLOCK_TO_BB (child) = ++count;
1956 CONTAINING_RGN (child) = nr_regions;
1957 queue[head] = queue[tail--];
1958 fst_edge = current_edge = OUT_EDGES (child);
1964 --degree[TO_BLOCK (current_edge)];
1965 current_edge = NEXT_OUT (current_edge);
1967 while (fst_edge != current_edge);
1978 /* define each of all other blocks as a region itself */
1979 for (i = 0; i < n_basic_blocks; i++)
1982 rgn_bb_table[idx] = i;
1983 RGN_NR_BLOCKS (nr_regions) = 1;
1984 RGN_BLOCKS (nr_regions) = idx++;
1985 CONTAINING_RGN (i) = nr_regions++;
1986 BLOCK_TO_BB (i) = 0;
1992 /* functions for regions scheduling information */
1994 /* Compute dominators, probability, and potential-split-edges of bb.
1995 Assume that these values were already computed for bb's predecessors. */
1998 compute_dom_prob_ps (bb)
2001 int nxt_in_edge, fst_in_edge, pred;
2002 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
2005 if (IS_RGN_ENTRY (bb))
2007 BITSET_ADD (dom[bb], 0, bbset_size);
2012 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
2014 /* intialize dom[bb] to '111..1' */
2015 BITSET_INVERT (dom[bb], bbset_size);
2019 pred = FROM_BLOCK (nxt_in_edge);
2020 BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
2022 BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
2025 BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
2028 nr_rgn_out_edges = 0;
2029 fst_out_edge = OUT_EDGES (pred);
2030 nxt_out_edge = NEXT_OUT (fst_out_edge);
2031 BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
2034 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
2036 /* the successor doesn't belong the region? */
2037 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
2038 CONTAINING_RGN (BB_TO_BLOCK (bb)))
2041 while (fst_out_edge != nxt_out_edge)
2044 /* the successor doesn't belong the region? */
2045 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
2046 CONTAINING_RGN (BB_TO_BLOCK (bb)))
2048 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
2049 nxt_out_edge = NEXT_OUT (nxt_out_edge);
2053 /* now nr_rgn_out_edges is the number of region-exit edges from pred,
2054 and nr_out_edges will be the number of pred out edges not leaving
2056 nr_out_edges -= nr_rgn_out_edges;
2057 if (nr_rgn_out_edges > 0)
2058 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
2060 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
2061 nxt_in_edge = NEXT_IN (nxt_in_edge);
2063 while (fst_in_edge != nxt_in_edge);
2065 BITSET_ADD (dom[bb], bb, bbset_size);
2066 BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
2068 if (sched_verbose >= 2)
2069 fprintf (dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb), (int) (100.0 * prob[bb]));
2070 } /* compute_dom_prob_ps */
2072 /* functions for target info */
2074 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
2075 Note that bb_trg dominates bb_src. */
2078 split_edges (bb_src, bb_trg, bl)
2083 int es = edgeset_size;
2084 edgeset src = (edgeset) alloca (es * sizeof (HOST_WIDE_INT));
2087 src[es] = (pot_split[bb_src])[es];
2088 BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
2089 extract_bitlst (src, edgeset_size, bl);
2093 /* Find the valid candidate-source-blocks for the target block TRG, compute
2094 their probability, and check if they are speculative or not.
2095 For speculative sources, compute their update-blocks and split-blocks. */
2098 compute_trg_info (trg)
2101 register candidate *sp;
2103 int check_block, update_idx;
2104 int i, j, k, fst_edge, nxt_edge;
2106 /* define some of the fields for the target bb as well */
2107 sp = candidate_table + trg;
2109 sp->is_speculative = 0;
2112 for (i = trg + 1; i < current_nr_blocks; i++)
2114 sp = candidate_table + i;
2116 sp->is_valid = IS_DOMINATED (i, trg);
2119 sp->src_prob = GET_SRC_PROB (i, trg);
2120 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
2125 split_edges (i, trg, &el);
2126 sp->is_speculative = (el.nr_members) ? 1 : 0;
2127 if (sp->is_speculative && !flag_schedule_speculative)
2133 sp->split_bbs.first_member = &bblst_table[bblst_last];
2134 sp->split_bbs.nr_members = el.nr_members;
2135 for (j = 0; j < el.nr_members; bblst_last++, j++)
2136 bblst_table[bblst_last] =
2137 TO_BLOCK (rgn_edges[el.first_member[j]]);
2138 sp->update_bbs.first_member = &bblst_table[bblst_last];
2140 for (j = 0; j < el.nr_members; j++)
2142 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
2143 fst_edge = nxt_edge = OUT_EDGES (check_block);
2146 for (k = 0; k < el.nr_members; k++)
2147 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
2150 if (k >= el.nr_members)
2152 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
2156 nxt_edge = NEXT_OUT (nxt_edge);
2158 while (fst_edge != nxt_edge);
2160 sp->update_bbs.nr_members = update_idx;
2165 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
2167 sp->is_speculative = 0;
2171 } /* compute_trg_info */
2174 /* Print candidates info, for debugging purposes. Callable from debugger. */
2180 if (!candidate_table[i].is_valid)
2183 if (candidate_table[i].is_speculative)
2186 fprintf (dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
2188 fprintf (dump, "split path: ");
2189 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
2191 int b = candidate_table[i].split_bbs.first_member[j];
2193 fprintf (dump, " %d ", b);
2195 fprintf (dump, "\n");
2197 fprintf (dump, "update path: ");
2198 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
2200 int b = candidate_table[i].update_bbs.first_member[j];
2202 fprintf (dump, " %d ", b);
2204 fprintf (dump, "\n");
2208 fprintf (dump, " src %d equivalent\n", BB_TO_BLOCK (i));
2213 /* Print candidates info, for debugging purposes. Callable from debugger. */
2216 debug_candidates (trg)
2221 fprintf (dump, "----------- candidate table: target: b=%d bb=%d ---\n",
2222 BB_TO_BLOCK (trg), trg);
2223 for (i = trg + 1; i < current_nr_blocks; i++)
2224 debug_candidate (i);
2228 /* functions for speculative scheduing */
2230 /* Return 0 if x is a set of a register alive in the beginning of one
2231 of the split-blocks of src, otherwise return 1. */
2234 check_live_1 (src, x)
2240 register rtx reg = SET_DEST (x);
2245 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2246 || GET_CODE (reg) == SIGN_EXTRACT
2247 || GET_CODE (reg) == STRICT_LOW_PART)
2248 reg = XEXP (reg, 0);
2250 if (GET_CODE (reg) != REG)
2253 regno = REGNO (reg);
2255 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2257 /* Global registers are assumed live */
2262 if (regno < FIRST_PSEUDO_REGISTER)
2264 /* check for hard registers */
2265 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2268 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2270 int b = candidate_table[src].split_bbs.first_member[i];
2272 if (REGNO_REG_SET_P (basic_block_live_at_start[b], regno + j))
2281 /* check for psuedo registers */
2282 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2284 int b = candidate_table[src].split_bbs.first_member[i];
2286 if (REGNO_REG_SET_P (basic_block_live_at_start[b], regno))
2298 /* If x is a set of a register R, mark that R is alive in the beginning
2299 of every update-block of src. */
2302 update_live_1 (src, x)
2308 register rtx reg = SET_DEST (x);
2313 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2314 || GET_CODE (reg) == SIGN_EXTRACT
2315 || GET_CODE (reg) == STRICT_LOW_PART)
2316 reg = XEXP (reg, 0);
2318 if (GET_CODE (reg) != REG)
2321 /* Global registers are always live, so the code below does not apply
2324 regno = REGNO (reg);
2326 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
2328 if (regno < FIRST_PSEUDO_REGISTER)
2330 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2333 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2335 int b = candidate_table[src].update_bbs.first_member[i];
2337 SET_REGNO_REG_SET (basic_block_live_at_start[b], regno + j);
2343 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2345 int b = candidate_table[src].update_bbs.first_member[i];
2347 SET_REGNO_REG_SET (basic_block_live_at_start[b], regno);
2354 /* Return 1 if insn can be speculatively moved from block src to trg,
2355 otherwise return 0. Called before first insertion of insn to
2356 ready-list or before the scheduling. */
2359 check_live (insn, src)
2363 /* find the registers set by instruction */
2364 if (GET_CODE (PATTERN (insn)) == SET
2365 || GET_CODE (PATTERN (insn)) == CLOBBER)
2366 return check_live_1 (src, PATTERN (insn));
2367 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2370 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2371 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2372 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2373 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
2383 /* Update the live registers info after insn was moved speculatively from
2384 block src to trg. */
2387 update_live (insn, src)
2391 /* find the registers set by instruction */
2392 if (GET_CODE (PATTERN (insn)) == SET
2393 || GET_CODE (PATTERN (insn)) == CLOBBER)
2394 update_live_1 (src, PATTERN (insn));
2395 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2398 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2399 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2400 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2401 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
2405 /* Exception Free Loads:
2407 We define five classes of speculative loads: IFREE, IRISKY,
2408 PFREE, PRISKY, and MFREE.
2410 IFREE loads are loads that are proved to be exception-free, just
2411 by examining the load insn. Examples for such loads are loads
2412 from TOC and loads of global data.
2414 IRISKY loads are loads that are proved to be exception-risky,
2415 just by examining the load insn. Examples for such loads are
2416 volatile loads and loads from shared memory.
2418 PFREE loads are loads for which we can prove, by examining other
2419 insns, that they are exception-free. Currently, this class consists
2420 of loads for which we are able to find a "similar load", either in
2421 the target block, or, if only one split-block exists, in that split
2422 block. Load2 is similar to load1 if both have same single base
2423 register. We identify only part of the similar loads, by finding
2424 an insn upon which both load1 and load2 have a DEF-USE dependence.
2426 PRISKY loads are loads for which we can prove, by examining other
2427 insns, that they are exception-risky. Currently we have two proofs for
2428 such loads. The first proof detects loads that are probably guarded by a
2429 test on the memory address. This proof is based on the
2430 backward and forward data dependence information for the region.
2431 Let load-insn be the examined load.
2432 Load-insn is PRISKY iff ALL the following hold:
2434 - insn1 is not in the same block as load-insn
2435 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2436 - test-insn is either a compare or a branch, not in the same block as load-insn
2437 - load-insn is reachable from test-insn
2438 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2440 This proof might fail when the compare and the load are fed
2441 by an insn not in the region. To solve this, we will add to this
2442 group all loads that have no input DEF-USE dependence.
2444 The second proof detects loads that are directly or indirectly
2445 fed by a speculative load. This proof is affected by the
2446 scheduling process. We will use the flag fed_by_spec_load.
2447 Initially, all insns have this flag reset. After a speculative
2448 motion of an insn, if insn is either a load, or marked as
2449 fed_by_spec_load, we will also mark as fed_by_spec_load every
2450 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2451 load which is fed_by_spec_load is also PRISKY.
2453 MFREE (maybe-free) loads are all the remaining loads. They may be
2454 exception-free, but we cannot prove it.
2456 Now, all loads in IFREE and PFREE classes are considered
2457 exception-free, while all loads in IRISKY and PRISKY classes are
2458 considered exception-risky. As for loads in the MFREE class,
2459 these are considered either exception-free or exception-risky,
2460 depending on whether we are pessimistic or optimistic. We have
2461 to take the pessimistic approach to assure the safety of
2462 speculative scheduling, but we can take the optimistic approach
2463 by invoking the -fsched_spec_load_dangerous option. */
2465 enum INSN_TRAP_CLASS
2467 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
2468 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
2471 #define WORST_CLASS(class1, class2) \
2472 ((class1 > class2) ? class1 : class2)
2474 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between */
2475 /* some speculatively moved load insn and this one. */
2476 char *fed_by_spec_load;
2479 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2480 #define IS_REACHABLE(bb_from, bb_to) \
2482 || IS_RGN_ENTRY (bb_from) \
2483 || (bitset_member (ancestor_edges[bb_to], \
2484 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2486 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2487 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2489 /* Non-zero iff the address is comprised from at most 1 register */
2490 #define CONST_BASED_ADDRESS_P(x) \
2491 (GET_CODE (x) == REG \
2492 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2493 || (GET_CODE (x) == LO_SUM)) \
2494 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2495 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2497 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2500 set_spec_fed (load_insn)
2505 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
2506 if (GET_MODE (link) == VOIDmode)
2507 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
2508 } /* set_spec_fed */
2510 /* On the path from the insn to load_insn_bb, find a conditional branch */
2511 /* depending on insn, that guards the speculative load. */
2514 find_conditional_protection (insn, load_insn_bb)
2520 /* iterate through DEF-USE forward dependences */
2521 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2523 rtx next = XEXP (link, 0);
2524 if ((CONTAINING_RGN (INSN_BLOCK (next)) ==
2525 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
2526 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
2527 && load_insn_bb != INSN_BB (next)
2528 && GET_MODE (link) == VOIDmode
2529 && (GET_CODE (next) == JUMP_INSN
2530 || find_conditional_protection (next, load_insn_bb)))
2534 } /* find_conditional_protection */
2536 /* Returns 1 if the same insn1 that participates in the computation
2537 of load_insn's address is feeding a conditional branch that is
2538 guarding on load_insn. This is true if we find a the two DEF-USE
2540 insn1 -> ... -> conditional-branch
2541 insn1 -> ... -> load_insn,
2542 and if a flow path exist:
2543 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2544 and if insn1 is on the path
2545 region-entry -> ... -> bb_trg -> ... load_insn.
2547 Locate insn1 by climbing on LOG_LINKS from load_insn.
2548 Locate the branch by following INSN_DEPEND from insn1. */
2551 is_conditionally_protected (load_insn, bb_src, bb_trg)
2557 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
2559 rtx insn1 = XEXP (link, 0);
2561 /* must be a DEF-USE dependence upon non-branch */
2562 if (GET_MODE (link) != VOIDmode
2563 || GET_CODE (insn1) == JUMP_INSN)
2566 /* must exist a path: region-entry -> ... -> bb_trg -> ... load_insn */
2567 if (INSN_BB (insn1) == bb_src
2568 || (CONTAINING_RGN (INSN_BLOCK (insn1))
2569 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
2570 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
2571 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
2574 /* now search for the conditional-branch */
2575 if (find_conditional_protection (insn1, bb_src))
2578 /* recursive step: search another insn1, "above" current insn1. */
2579 return is_conditionally_protected (insn1, bb_src, bb_trg);
2582 /* the chain does not exsist */
2584 } /* is_conditionally_protected */
2586 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2587 load_insn can move speculatively from bb_src to bb_trg. All the
2588 following must hold:
2590 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2591 (2) load_insn and load1 have a def-use dependence upon
2592 the same insn 'insn1'.
2593 (3) either load2 is in bb_trg, or:
2594 - there's only one split-block, and
2595 - load1 is on the escape path, and
2597 From all these we can conclude that the two loads access memory
2598 addresses that differ at most by a constant, and hence if moving
2599 load_insn would cause an exception, it would have been caused by
2603 is_pfree (load_insn, bb_src, bb_trg)
2608 register candidate *candp = candidate_table + bb_src;
2610 if (candp->split_bbs.nr_members != 1)
2611 /* must have exactly one escape block */
2614 for (back_link = LOG_LINKS (load_insn);
2615 back_link; back_link = XEXP (back_link, 1))
2617 rtx insn1 = XEXP (back_link, 0);
2619 if (GET_MODE (back_link) == VOIDmode)
2621 /* found a DEF-USE dependence (insn1, load_insn) */
2624 for (fore_link = INSN_DEPEND (insn1);
2625 fore_link; fore_link = XEXP (fore_link, 1))
2627 rtx insn2 = XEXP (fore_link, 0);
2628 if (GET_MODE (fore_link) == VOIDmode)
2630 /* found a DEF-USE dependence (insn1, insn2) */
2631 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
2632 /* insn2 not guaranteed to be a 1 base reg load */
2635 if (INSN_BB (insn2) == bb_trg)
2636 /* insn2 is the similar load, in the target block */
2639 if (*(candp->split_bbs.first_member) == INSN_BLOCK (insn2))
2640 /* insn2 is a similar load, in a split-block */
2647 /* couldn't find a similar load */
2651 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2652 as found by analyzing insn's expression. */
2655 may_trap_exp (x, is_store)
2663 code = GET_CODE (x);
2673 /* The insn uses memory */
2674 /* a volatile load */
2675 if (MEM_VOLATILE_P (x))
2677 /* an exception-free load */
2678 if (!may_trap_p (x))
2680 /* a load with 1 base register, to be further checked */
2681 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
2682 return PFREE_CANDIDATE;
2683 /* no info on the load, to be further checked */
2684 return PRISKY_CANDIDATE;
2689 int i, insn_class = TRAP_FREE;
2691 /* neither store nor load, check if it may cause a trap */
2694 /* recursive step: walk the insn... */
2695 fmt = GET_RTX_FORMAT (code);
2696 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2700 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
2701 insn_class = WORST_CLASS (insn_class, tmp_class);
2703 else if (fmt[i] == 'E')
2706 for (j = 0; j < XVECLEN (x, i); j++)
2708 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
2709 insn_class = WORST_CLASS (insn_class, tmp_class);
2710 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2714 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2719 } /* may_trap_exp */
2722 /* Classifies insn for the purpose of verifying that it can be
2723 moved speculatively, by examining it's patterns, returning:
2724 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2725 TRAP_FREE: non-load insn.
2726 IFREE: load from a globaly safe location.
2727 IRISKY: volatile load.
2728 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2729 being either PFREE or PRISKY. */
2732 haifa_classify_insn (insn)
2735 rtx pat = PATTERN (insn);
2736 int tmp_class = TRAP_FREE;
2737 int insn_class = TRAP_FREE;
2740 if (GET_CODE (pat) == PARALLEL)
2742 int i, len = XVECLEN (pat, 0);
2744 for (i = len - 1; i >= 0; i--)
2746 code = GET_CODE (XVECEXP (pat, 0, i));
2750 /* test if it is a 'store' */
2751 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
2754 /* test if it is a store */
2755 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
2756 if (tmp_class == TRAP_RISKY)
2758 /* test if it is a load */
2760 WORST_CLASS (tmp_class,
2761 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 0));
2764 insn_class = WORST_CLASS (insn_class, tmp_class);
2765 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2771 code = GET_CODE (pat);
2775 /* test if it is a 'store' */
2776 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
2779 /* test if it is a store */
2780 tmp_class = may_trap_exp (SET_DEST (pat), 1);
2781 if (tmp_class == TRAP_RISKY)
2783 /* test if it is a load */
2785 WORST_CLASS (tmp_class,
2786 may_trap_exp (SET_SRC (pat), 0));
2789 insn_class = tmp_class;
2794 } /* haifa_classify_insn */
2796 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2797 a load moved speculatively, or if load_insn is protected by
2798 a compare on load_insn's address). */
2801 is_prisky (load_insn, bb_src, bb_trg)
2805 if (FED_BY_SPEC_LOAD (load_insn))
2808 if (LOG_LINKS (load_insn) == NULL)
2809 /* dependence may 'hide' out of the region. */
2812 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2818 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2819 Return 1 if insn is exception-free (and the motion is valid)
2823 is_exception_free (insn, bb_src, bb_trg)
2827 int insn_class = haifa_classify_insn (insn);
2829 /* handle non-load insns */
2840 if (!flag_schedule_speculative_load)
2842 IS_LOAD_INSN (insn) = 1;
2849 case PFREE_CANDIDATE:
2850 if (is_pfree (insn, bb_src, bb_trg))
2852 /* don't 'break' here: PFREE-candidate is also PRISKY-candidate */
2853 case PRISKY_CANDIDATE:
2854 if (!flag_schedule_speculative_load_dangerous
2855 || is_prisky (insn, bb_src, bb_trg))
2861 return flag_schedule_speculative_load_dangerous;
2862 } /* is_exception_free */
2865 /* Process an insn's memory dependencies. There are four kinds of
2868 (0) read dependence: read follows read
2869 (1) true dependence: read follows write
2870 (2) anti dependence: write follows read
2871 (3) output dependence: write follows write
2873 We are careful to build only dependencies which actually exist, and
2874 use transitivity to avoid building too many links. */
2876 /* Return the INSN_LIST containing INSN in LIST, or NULL
2877 if LIST does not contain INSN. */
2880 find_insn_list (insn, list)
2886 if (XEXP (list, 0) == insn)
2888 list = XEXP (list, 1);
2894 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 otherwise. */
2896 __inline static char
2897 find_insn_mem_list (insn, x, list, list1)
2903 if (XEXP (list, 0) == insn
2904 && XEXP (list1, 0) == x)
2906 list = XEXP (list, 1);
2907 list1 = XEXP (list1, 1);
2913 /* Compute the function units used by INSN. This caches the value
2914 returned by function_units_used. A function unit is encoded as the
2915 unit number if the value is non-negative and the compliment of a
2916 mask if the value is negative. A function unit index is the
2917 non-negative encoding. */
2923 register int unit = INSN_UNIT (insn);
2927 recog_memoized (insn);
2929 /* A USE insn, or something else we don't need to understand.
2930 We can't pass these directly to function_units_used because it will
2931 trigger a fatal error for unrecognizable insns. */
2932 if (INSN_CODE (insn) < 0)
2936 unit = function_units_used (insn);
2937 /* Increment non-negative values so we can cache zero. */
2941 /* We only cache 16 bits of the result, so if the value is out of
2942 range, don't cache it. */
2943 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
2945 || (~unit & ((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
2946 INSN_UNIT (insn) = unit;
2948 return (unit > 0 ? unit - 1 : unit);
2951 /* Compute the blockage range for executing INSN on UNIT. This caches
2952 the value returned by the blockage_range_function for the unit.
2953 These values are encoded in an int where the upper half gives the
2954 minimum value and the lower half gives the maximum value. */
2956 __inline static unsigned int
2957 blockage_range (unit, insn)
2961 unsigned int blockage = INSN_BLOCKAGE (insn);
2964 if (UNIT_BLOCKED (blockage) != unit + 1)
2966 range = function_units[unit].blockage_range_function (insn);
2967 /* We only cache the blockage range for one unit and then only if
2969 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
2970 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
2973 range = BLOCKAGE_RANGE (blockage);
2978 /* A vector indexed by function unit instance giving the last insn to use
2979 the unit. The value of the function unit instance index for unit U
2980 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2981 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2983 /* A vector indexed by function unit instance giving the minimum time when
2984 the unit will unblock based on the maximum blockage cost. */
2985 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2987 /* A vector indexed by function unit number giving the number of insns
2988 that remain to use the unit. */
2989 static int unit_n_insns[FUNCTION_UNITS_SIZE];
2991 /* Reset the function unit state to the null state. */
2996 bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
2997 bzero ((char *) unit_tick, sizeof (unit_tick));
2998 bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
3001 /* Return the issue-delay of an insn */
3004 insn_issue_delay (insn)
3008 int unit = insn_unit (insn);
3010 /* efficiency note: in fact, we are working 'hard' to compute a
3011 value that was available in md file, and is not available in
3012 function_units[] structure. It would be nice to have this
3013 value there, too. */
3016 if (function_units[unit].blockage_range_function &&
3017 function_units[unit].blockage_function)
3018 delay = function_units[unit].blockage_function (insn, insn);
3021 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3022 if ((unit & 1) != 0 && function_units[i].blockage_range_function
3023 && function_units[i].blockage_function)
3024 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
3029 /* Return the actual hazard cost of executing INSN on the unit UNIT,
3030 instance INSTANCE at time CLOCK if the previous actual hazard cost
3034 actual_hazard_this_instance (unit, instance, insn, clock, cost)
3035 int unit, instance, clock, cost;
3038 int tick = unit_tick[instance]; /* issue time of the last issued insn */
3040 if (tick - clock > cost)
3042 /* The scheduler is operating forward, so unit's last insn is the
3043 executing insn and INSN is the candidate insn. We want a
3044 more exact measure of the blockage if we execute INSN at CLOCK
3045 given when we committed the execution of the unit's last insn.
3047 The blockage value is given by either the unit's max blockage
3048 constant, blockage range function, or blockage function. Use
3049 the most exact form for the given unit. */
3051 if (function_units[unit].blockage_range_function)
3053 if (function_units[unit].blockage_function)
3054 tick += (function_units[unit].blockage_function
3055 (unit_last_insn[instance], insn)
3056 - function_units[unit].max_blockage);
3058 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
3059 - function_units[unit].max_blockage);
3061 if (tick - clock > cost)
3062 cost = tick - clock;
3067 /* Record INSN as having begun execution on the units encoded by UNIT at
3070 __inline static void
3071 schedule_unit (unit, insn, clock)
3079 int instance = unit;
3080 #if MAX_MULTIPLICITY > 1
3081 /* Find the first free instance of the function unit and use that
3082 one. We assume that one is free. */
3083 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
3085 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
3087 instance += FUNCTION_UNITS_SIZE;
3090 unit_last_insn[instance] = insn;
3091 unit_tick[instance] = (clock + function_units[unit].max_blockage);
3094 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3095 if ((unit & 1) != 0)
3096 schedule_unit (i, insn, clock);
3099 /* Return the actual hazard cost of executing INSN on the units encoded by
3100 UNIT at time CLOCK if the previous actual hazard cost was COST. */
3103 actual_hazard (unit, insn, clock, cost)
3104 int unit, clock, cost;
3111 /* Find the instance of the function unit with the minimum hazard. */
3112 int instance = unit;
3113 int best_cost = actual_hazard_this_instance (unit, instance, insn,
3117 #if MAX_MULTIPLICITY > 1
3118 if (best_cost > cost)
3120 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
3122 instance += FUNCTION_UNITS_SIZE;
3123 this_cost = actual_hazard_this_instance (unit, instance, insn,
3125 if (this_cost < best_cost)
3127 best_cost = this_cost;
3128 if (this_cost <= cost)
3134 cost = MAX (cost, best_cost);
3137 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3138 if ((unit & 1) != 0)
3139 cost = actual_hazard (i, insn, clock, cost);
3144 /* Return the potential hazard cost of executing an instruction on the
3145 units encoded by UNIT if the previous potential hazard cost was COST.
3146 An insn with a large blockage time is chosen in preference to one
3147 with a smaller time; an insn that uses a unit that is more likely
3148 to be used is chosen in preference to one with a unit that is less
3149 used. We are trying to minimize a subsequent actual hazard. */
3152 potential_hazard (unit, insn, cost)
3157 unsigned int minb, maxb;
3161 minb = maxb = function_units[unit].max_blockage;
3164 if (function_units[unit].blockage_range_function)
3166 maxb = minb = blockage_range (unit, insn);
3167 maxb = MAX_BLOCKAGE_COST (maxb);
3168 minb = MIN_BLOCKAGE_COST (minb);
3173 /* Make the number of instructions left dominate. Make the
3174 minimum delay dominate the maximum delay. If all these
3175 are the same, use the unit number to add an arbitrary
3176 ordering. Other terms can be added. */
3177 ncost = minb * 0x40 + maxb;
3178 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
3185 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3186 if ((unit & 1) != 0)
3187 cost = potential_hazard (i, insn, cost);
3192 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3193 This is the number of cycles between instruction issue and
3194 instruction results. */
3197 insn_cost (insn, link, used)
3198 rtx insn, link, used;
3200 register int cost = INSN_COST (insn);
3204 recog_memoized (insn);
3206 /* A USE insn, or something else we don't need to understand.
3207 We can't pass these directly to result_ready_cost because it will
3208 trigger a fatal error for unrecognizable insns. */
3209 if (INSN_CODE (insn) < 0)
3211 INSN_COST (insn) = 1;
3216 cost = result_ready_cost (insn);
3221 INSN_COST (insn) = cost;
3225 /* in this case estimate cost without caring how insn is used. */
3226 if (link == 0 && used == 0)
3229 /* A USE insn should never require the value used to be computed. This
3230 allows the computation of a function's result and parameter values to
3231 overlap the return and call. */
3232 recog_memoized (used);
3233 if (INSN_CODE (used) < 0)
3234 LINK_COST_FREE (link) = 1;
3236 /* If some dependencies vary the cost, compute the adjustment. Most
3237 commonly, the adjustment is complete: either the cost is ignored
3238 (in the case of an output- or anti-dependence), or the cost is
3239 unchanged. These values are cached in the link as LINK_COST_FREE
3240 and LINK_COST_ZERO. */
3242 if (LINK_COST_FREE (link))
3245 else if (!LINK_COST_ZERO (link))
3249 ADJUST_COST (used, link, insn, ncost);
3251 LINK_COST_FREE (link) = ncost = 1;
3253 LINK_COST_ZERO (link) = 1;
3260 /* Compute the priority number for INSN. */
3269 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
3272 if ((this_priority = INSN_PRIORITY (insn)) == 0)
3274 if (INSN_DEPEND (insn) == 0)
3275 this_priority = insn_cost (insn, 0, 0);
3277 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
3282 if (RTX_INTEGRATED_P (link))
3285 next = XEXP (link, 0);
3287 /* critical path is meaningful in block boundaries only */
3288 if (INSN_BLOCK (next) != INSN_BLOCK (insn))
3291 next_priority = insn_cost (insn, link, next) + priority (next);
3292 if (next_priority > this_priority)
3293 this_priority = next_priority;
3295 INSN_PRIORITY (insn) = this_priority;
3297 return this_priority;
3301 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3302 them to the unused_*_list variables, so that they can be reused. */
3305 free_pending_lists ()
3307 if (current_nr_blocks <= 1)
3309 free_list (&pending_read_insns, &unused_insn_list);
3310 free_list (&pending_write_insns, &unused_insn_list);
3311 free_list (&pending_read_mems, &unused_expr_list);
3312 free_list (&pending_write_mems, &unused_expr_list);
3316 /* interblock scheduling */
3319 for (bb = 0; bb < current_nr_blocks; bb++)
3321 free_list (&bb_pending_read_insns[bb], &unused_insn_list);
3322 free_list (&bb_pending_write_insns[bb], &unused_insn_list);
3323 free_list (&bb_pending_read_mems[bb], &unused_expr_list);
3324 free_list (&bb_pending_write_mems[bb], &unused_expr_list);
3329 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3330 The MEM is a memory reference contained within INSN, which we are saving
3331 so that we can do memory aliasing on it. */
3334 add_insn_mem_dependence (insn_list, mem_list, insn, mem)
3335 rtx *insn_list, *mem_list, insn, mem;
3339 link = alloc_INSN_LIST (insn, *insn_list);
3342 link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
3345 pending_lists_length++;
3349 /* Make a dependency between every memory reference on the pending lists
3350 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3354 flush_pending_lists (insn, only_write)
3361 while (pending_read_insns && ! only_write)
3363 add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
3365 link = pending_read_insns;
3366 pending_read_insns = XEXP (pending_read_insns, 1);
3367 XEXP (link, 1) = unused_insn_list;
3368 unused_insn_list = link;
3370 link = pending_read_mems;
3371 pending_read_mems = XEXP (pending_read_mems, 1);
3372 XEXP (link, 1) = unused_expr_list;
3373 unused_expr_list = link;
3375 while (pending_write_insns)
3377 add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
3379 link = pending_write_insns;
3380 pending_write_insns = XEXP (pending_write_insns, 1);
3381 XEXP (link, 1) = unused_insn_list;
3382 unused_insn_list = link;
3384 link = pending_write_mems;
3385 pending_write_mems = XEXP (pending_write_mems, 1);
3386 XEXP (link, 1) = unused_expr_list;
3387 unused_expr_list = link;
3389 pending_lists_length = 0;
3391 /* last_pending_memory_flush is now a list of insns */
3392 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3393 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3395 free_list (&last_pending_memory_flush, &unused_insn_list);
3396 last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
3399 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
3400 by the write to the destination of X, and reads of everything mentioned. */
3403 sched_analyze_1 (x, insn)
3408 register rtx dest = SET_DEST (x);
3413 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3414 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3416 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3418 /* The second and third arguments are values read by this insn. */
3419 sched_analyze_2 (XEXP (dest, 1), insn);
3420 sched_analyze_2 (XEXP (dest, 2), insn);
3422 dest = SUBREG_REG (dest);
3425 if (GET_CODE (dest) == REG)
3429 regno = REGNO (dest);
3431 /* A hard reg in a wide mode may really be multiple registers.
3432 If so, mark all of them just like the first. */
3433 if (regno < FIRST_PSEUDO_REGISTER)
3435 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
3440 for (u = reg_last_uses[regno + i]; u; u = XEXP (u, 1))
3441 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3442 reg_last_uses[regno + i] = 0;
3444 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3445 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3447 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
3449 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3450 /* Function calls clobber all call_used regs. */
3451 for (u = last_function_call; u; u = XEXP (u, 1))
3452 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3459 for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
3460 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3461 reg_last_uses[regno] = 0;
3463 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3464 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3466 SET_REGNO_REG_SET (reg_pending_sets, regno);
3468 /* Pseudos that are REG_EQUIV to something may be replaced
3469 by that during reloading. We need only add dependencies for
3470 the address in the REG_EQUIV note. */
3471 if (!reload_completed
3472 && reg_known_equiv_p[regno]
3473 && GET_CODE (reg_known_value[regno]) == MEM)
3474 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3476 /* Don't let it cross a call after scheduling if it doesn't
3477 already cross one. */
3479 if (REG_N_CALLS_CROSSED (regno) == 0)
3480 for (u = last_function_call; u; u = XEXP (u, 1))
3481 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3484 else if (GET_CODE (dest) == MEM)
3486 /* Writing memory. */
3488 if (pending_lists_length > 32)
3490 /* Flush all pending reads and writes to prevent the pending lists
3491 from getting any larger. Insn scheduling runs too slowly when
3492 these lists get long. The number 32 was chosen because it
3493 seems like a reasonable number. When compiling GCC with itself,
3494 this flush occurs 8 times for sparc, and 10 times for m88k using
3496 flush_pending_lists (insn, 0);
3501 rtx pending, pending_mem;
3503 pending = pending_read_insns;
3504 pending_mem = pending_read_mems;
3507 /* If a dependency already exists, don't create a new one. */
3508 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3509 if (anti_dependence (XEXP (pending_mem, 0), dest))
3510 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3512 pending = XEXP (pending, 1);
3513 pending_mem = XEXP (pending_mem, 1);
3516 pending = pending_write_insns;
3517 pending_mem = pending_write_mems;
3520 /* If a dependency already exists, don't create a new one. */
3521 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3522 if (output_dependence (XEXP (pending_mem, 0), dest))
3523 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
3525 pending = XEXP (pending, 1);
3526 pending_mem = XEXP (pending_mem, 1);
3529 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3530 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3532 add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
3535 sched_analyze_2 (XEXP (dest, 0), insn);
3538 /* Analyze reads. */
3539 if (GET_CODE (x) == SET)
3540 sched_analyze_2 (SET_SRC (x), insn);
3543 /* Analyze the uses of memory and registers in rtx X in INSN. */
3546 sched_analyze_2 (x, insn)
3552 register enum rtx_code code;
3558 code = GET_CODE (x);
3567 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3568 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3569 this does not mean that this insn is using cc0. */
3577 /* User of CC0 depends on immediately preceding insn. */
3578 SCHED_GROUP_P (insn) = 1;
3580 /* There may be a note before this insn now, but all notes will
3581 be removed before we actually try to schedule the insns, so
3582 it won't cause a problem later. We must avoid it here though. */
3583 prev = prev_nonnote_insn (insn);
3585 /* Make a copy of all dependencies on the immediately previous insn,
3586 and add to this insn. This is so that all the dependencies will
3587 apply to the group. Remove an explicit dependence on this insn
3588 as SCHED_GROUP_P now represents it. */
3590 if (find_insn_list (prev, LOG_LINKS (insn)))
3591 remove_dependence (insn, prev);
3593 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
3594 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3603 int regno = REGNO (x);
3604 if (regno < FIRST_PSEUDO_REGISTER)
3608 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
3611 reg_last_uses[regno + i]
3612 = alloc_INSN_LIST (insn, reg_last_uses[regno + i]);
3614 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3615 add_dependence (insn, XEXP (u, 0), 0);
3617 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3618 /* Function calls clobber all call_used regs. */
3619 for (u = last_function_call; u; u = XEXP (u, 1))
3620 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3625 reg_last_uses[regno] = alloc_INSN_LIST (insn, reg_last_uses[regno]);
3627 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3628 add_dependence (insn, XEXP (u, 0), 0);
3630 /* Pseudos that are REG_EQUIV to something may be replaced
3631 by that during reloading. We need only add dependencies for
3632 the address in the REG_EQUIV note. */
3633 if (!reload_completed
3634 && reg_known_equiv_p[regno]
3635 && GET_CODE (reg_known_value[regno]) == MEM)
3636 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3638 /* If the register does not already cross any calls, then add this
3639 insn to the sched_before_next_call list so that it will still
3640 not cross calls after scheduling. */
3641 if (REG_N_CALLS_CROSSED (regno) == 0)
3642 add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
3649 /* Reading memory. */
3651 rtx pending, pending_mem;
3653 pending = pending_read_insns;
3654 pending_mem = pending_read_mems;
3657 /* If a dependency already exists, don't create a new one. */
3658 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3659 if (read_dependence (XEXP (pending_mem, 0), x))
3660 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3662 pending = XEXP (pending, 1);
3663 pending_mem = XEXP (pending_mem, 1);
3666 pending = pending_write_insns;
3667 pending_mem = pending_write_mems;
3670 /* If a dependency already exists, don't create a new one. */
3671 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3672 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
3674 add_dependence (insn, XEXP (pending, 0), 0);
3676 pending = XEXP (pending, 1);
3677 pending_mem = XEXP (pending_mem, 1);
3680 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3681 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3683 /* Always add these dependencies to pending_reads, since
3684 this insn may be followed by a write. */
3685 add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
3688 /* Take advantage of tail recursion here. */
3689 sched_analyze_2 (XEXP (x, 0), insn);
3695 case UNSPEC_VOLATILE:
3700 /* Traditional and volatile asm instructions must be considered to use
3701 and clobber all hard registers, all pseudo-registers and all of
3702 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3704 Consider for instance a volatile asm that changes the fpu rounding
3705 mode. An insn should not be moved across this even if it only uses
3706 pseudo-regs because it might give an incorrectly rounded result. */
3707 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
3709 int max_reg = max_reg_num ();
3710 for (i = 0; i < max_reg; i++)
3712 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3713 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3714 reg_last_uses[i] = 0;
3716 /* reg_last_sets[r] is now a list of insns */
3717 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3718 add_dependence (insn, XEXP (u, 0), 0);
3720 reg_pending_sets_all = 1;
3722 flush_pending_lists (insn, 0);
3725 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3726 We can not just fall through here since then we would be confused
3727 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3728 traditional asms unlike their normal usage. */
3730 if (code == ASM_OPERANDS)
3732 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3733 sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
3743 /* These both read and modify the result. We must handle them as writes
3744 to get proper dependencies for following instructions. We must handle
3745 them as reads to get proper dependencies from this to previous
3746 instructions. Thus we need to pass them to both sched_analyze_1
3747 and sched_analyze_2. We must call sched_analyze_2 first in order
3748 to get the proper antecedent for the read. */
3749 sched_analyze_2 (XEXP (x, 0), insn);
3750 sched_analyze_1 (x, insn);
3757 /* Other cases: walk the insn. */
3758 fmt = GET_RTX_FORMAT (code);
3759 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3762 sched_analyze_2 (XEXP (x, i), insn);
3763 else if (fmt[i] == 'E')
3764 for (j = 0; j < XVECLEN (x, i); j++)
3765 sched_analyze_2 (XVECEXP (x, i, j), insn);
3769 /* Analyze an INSN with pattern X to find all dependencies. */
3772 sched_analyze_insn (x, insn, loop_notes)
3776 register RTX_CODE code = GET_CODE (x);
3778 int maxreg = max_reg_num ();
3781 if (code == SET || code == CLOBBER)
3782 sched_analyze_1 (x, insn);
3783 else if (code == PARALLEL)
3786 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3788 code = GET_CODE (XVECEXP (x, 0, i));
3789 if (code == SET || code == CLOBBER)
3790 sched_analyze_1 (XVECEXP (x, 0, i), insn);
3792 sched_analyze_2 (XVECEXP (x, 0, i), insn);
3796 sched_analyze_2 (x, insn);
3798 /* Mark registers CLOBBERED or used by called function. */
3799 if (GET_CODE (insn) == CALL_INSN)
3800 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3802 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3803 sched_analyze_1 (XEXP (link, 0), insn);
3805 sched_analyze_2 (XEXP (link, 0), insn);
3808 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic block, then
3809 we must be sure that no instructions are scheduled across it.
3810 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3811 become incorrect. */
3815 int max_reg = max_reg_num ();
3818 for (i = 0; i < max_reg; i++)
3821 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3822 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3823 reg_last_uses[i] = 0;
3825 /* reg_last_sets[r] is now a list of insns */
3826 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3827 add_dependence (insn, XEXP (u, 0), 0);
3829 reg_pending_sets_all = 1;
3831 flush_pending_lists (insn, 0);
3834 while (XEXP (link, 1))
3835 link = XEXP (link, 1);
3836 XEXP (link, 1) = REG_NOTES (insn);
3837 REG_NOTES (insn) = loop_notes;
3840 /* After reload, it is possible for an instruction to have a REG_DEAD note
3841 for a register that actually dies a few instructions earlier. For
3842 example, this can happen with SECONDARY_MEMORY_NEEDED reloads.
3843 In this case, we must consider the insn to use the register mentioned
3844 in the REG_DEAD note. Otherwise, we may accidentally move this insn
3845 after another insn that sets the register, thus getting obviously invalid
3846 rtl. This confuses reorg which believes that REG_DEAD notes are still
3849 ??? We would get better code if we fixed reload to put the REG_DEAD
3850 notes in the right places, but that may not be worth the effort. */
3852 if (reload_completed)
3856 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3857 if (REG_NOTE_KIND (note) == REG_DEAD)
3858 sched_analyze_2 (XEXP (note, 0), insn);
3861 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
3863 /* reg_last_sets[r] is now a list of insns */
3864 free_list (®_last_sets[i], &unused_insn_list);
3866 = alloc_INSN_LIST (insn, NULL_RTX);
3868 CLEAR_REG_SET (reg_pending_sets);
3870 if (reg_pending_sets_all)
3872 for (i = 0; i < maxreg; i++)
3874 /* reg_last_sets[r] is now a list of insns */
3875 free_list (®_last_sets[i], &unused_insn_list);
3876 reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3879 reg_pending_sets_all = 0;
3882 /* Handle function calls and function returns created by the epilogue
3884 if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
3889 /* When scheduling instructions, we make sure calls don't lose their
3890 accompanying USE insns by depending them one on another in order.
3892 Also, we must do the same thing for returns created by the epilogue
3893 threading code. Note this code works only in this special case,
3894 because other passes make no guarantee that they will never emit
3895 an instruction between a USE and a RETURN. There is such a guarantee
3896 for USE instructions immediately before a call. */
3898 prev_dep_insn = insn;
3899 dep_insn = PREV_INSN (insn);
3900 while (GET_CODE (dep_insn) == INSN
3901 && GET_CODE (PATTERN (dep_insn)) == USE
3902 && GET_CODE (XEXP (PATTERN (dep_insn), 0)) == REG)
3904 SCHED_GROUP_P (prev_dep_insn) = 1;
3906 /* Make a copy of all dependencies on dep_insn, and add to insn.
3907 This is so that all of the dependencies will apply to the
3910 for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
3911 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3913 prev_dep_insn = dep_insn;
3914 dep_insn = PREV_INSN (dep_insn);
3919 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3920 for every dependency. */
3923 sched_analyze (head, tail)
3930 for (insn = head;; insn = NEXT_INSN (insn))
3932 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
3934 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3937 else if (GET_CODE (insn) == CALL_INSN)
3942 CANT_MOVE (insn) = 1;
3944 /* Any instruction using a hard register which may get clobbered
3945 by a call needs to be marked as dependent on this call.
3946 This prevents a use of a hard return reg from being moved
3947 past a void call (i.e. it does not explicitly set the hard
3950 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3951 all registers, not just hard registers, may be clobbered by this
3954 /* Insn, being a CALL_INSN, magically depends on
3955 `last_function_call' already. */
3957 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
3958 && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
3960 int max_reg = max_reg_num ();
3961 for (i = 0; i < max_reg; i++)
3963 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3964 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3966 reg_last_uses[i] = 0;
3968 /* reg_last_sets[r] is now a list of insns */
3969 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3970 add_dependence (insn, XEXP (u, 0), 0);
3972 reg_pending_sets_all = 1;
3974 /* Add a pair of fake REG_NOTE which we will later
3975 convert back into a NOTE_INSN_SETJMP note. See
3976 reemit_notes for why we use a pair of NOTEs. */
3977 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3980 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3981 GEN_INT (NOTE_INSN_SETJMP),
3986 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3987 if (call_used_regs[i] || global_regs[i])
3989 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3990 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3991 reg_last_uses[i] = 0;
3993 /* reg_last_sets[r] is now a list of insns */
3994 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3995 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3997 SET_REGNO_REG_SET (reg_pending_sets, i);
4001 /* For each insn which shouldn't cross a call, add a dependence
4002 between that insn and this call insn. */
4003 x = LOG_LINKS (sched_before_next_call);
4006 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
4009 LOG_LINKS (sched_before_next_call) = 0;
4011 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
4014 /* In the absence of interprocedural alias analysis, we must flush
4015 all pending reads and writes, and start new dependencies starting
4016 from here. But only flush writes for constant calls (which may
4017 be passed a pointer to something we haven't written yet). */
4018 flush_pending_lists (insn, CONST_CALL_P (insn));
4020 /* Depend this function call (actually, the user of this
4021 function call) on all hard register clobberage. */
4023 /* last_function_call is now a list of insns */
4024 free_list(&last_function_call, &unused_insn_list);
4025 last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
4028 /* See comments on reemit_notes as to why we do this. */
4029 else if (GET_CODE (insn) == NOTE
4030 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
4031 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
4032 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
4033 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
4034 || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
4035 && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
4037 loop_notes = alloc_EXPR_LIST (REG_DEAD,
4038 GEN_INT (NOTE_BLOCK_NUMBER (insn)),
4040 loop_notes = alloc_EXPR_LIST (REG_DEAD,
4041 GEN_INT (NOTE_LINE_NUMBER (insn)),
4043 CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
4052 /* Called when we see a set of a register. If death is true, then we are
4053 scanning backwards. Mark that register as unborn. If nobody says
4054 otherwise, that is how things will remain. If death is false, then we
4055 are scanning forwards. Mark that register as being born. */
4058 sched_note_set (x, death)
4063 register rtx reg = SET_DEST (x);
4069 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
4070 || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
4072 /* Must treat modification of just one hardware register of a multi-reg
4073 value or just a byte field of a register exactly the same way that
4074 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
4075 does not kill the entire register. */
4076 if (GET_CODE (reg) != SUBREG
4077 || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
4080 reg = SUBREG_REG (reg);
4083 if (GET_CODE (reg) != REG)
4086 /* Global registers are always live, so the code below does not apply
4089 regno = REGNO (reg);
4090 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
4094 /* If we only set part of the register, then this set does not
4099 /* Try killing this register. */
4100 if (regno < FIRST_PSEUDO_REGISTER)
4102 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
4105 CLEAR_REGNO_REG_SET (bb_live_regs, regno + j);
4110 /* Recompute REG_BASIC_BLOCK as we update all the other
4111 dataflow information. */
4112 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
4113 sched_reg_basic_block[regno] = current_block_num;
4114 else if (sched_reg_basic_block[regno] != current_block_num)
4115 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
4117 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
4122 /* Make the register live again. */
4123 if (regno < FIRST_PSEUDO_REGISTER)
4125 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
4128 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4133 SET_REGNO_REG_SET (bb_live_regs, regno);
4139 /* Macros and functions for keeping the priority queue sorted, and
4140 dealing with queueing and dequeueing of instructions. */
4142 #define SCHED_SORT(READY, N_READY) \
4143 do { if ((N_READY) == 2) \
4144 swap_sort (READY, N_READY); \
4145 else if ((N_READY) > 2) \
4146 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4149 /* Returns a positive value if x is preferred; returns a negative value if
4150 y is preferred. Should never return 0, since that will make the sort
4154 rank_for_schedule (x, y)
4160 int tmp_class, tmp2_class;
4161 int val, priority_val, spec_val, prob_val, weight_val;
4164 /* prefer insn with higher priority */
4165 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
4167 return priority_val;
4169 /* prefer an insn with smaller contribution to registers-pressure */
4170 if (!reload_completed &&
4171 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
4172 return (weight_val);
4174 /* some comparison make sense in interblock scheduling only */
4175 if (INSN_BB (tmp) != INSN_BB (tmp2))
4177 /* prefer an inblock motion on an interblock motion */
4178 if ((INSN_BB (tmp2) == target_bb) && (INSN_BB (tmp) != target_bb))
4180 if ((INSN_BB (tmp) == target_bb) && (INSN_BB (tmp2) != target_bb))
4183 /* prefer a useful motion on a speculative one */
4184 if ((spec_val = IS_SPECULATIVE_INSN (tmp) - IS_SPECULATIVE_INSN (tmp2)))
4187 /* prefer a more probable (speculative) insn */
4188 prob_val = INSN_PROBABILITY (tmp2) - INSN_PROBABILITY (tmp);
4193 /* compare insns based on their relation to the last-scheduled-insn */
4194 if (last_scheduled_insn)
4196 /* Classify the instructions into three classes:
4197 1) Data dependent on last schedule insn.
4198 2) Anti/Output dependent on last scheduled insn.
4199 3) Independent of last scheduled insn, or has latency of one.
4200 Choose the insn from the highest numbered class if different. */
4201 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
4202 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
4204 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4209 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
4210 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
4212 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4217 if ((val = tmp2_class - tmp_class))
4221 /* If insns are equally good, sort by INSN_LUID (original insn order),
4222 so that we make the sort stable. This minimizes instruction movement,
4223 thus minimizing sched's effect on debugging and cross-jumping. */
4224 return INSN_LUID (tmp) - INSN_LUID (tmp2);
4227 /* Resort the array A in which only element at index N may be out of order. */
4229 __inline static void
4234 rtx insn = a[n - 1];
4237 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
4245 static int max_priority;
4247 /* Add INSN to the insn queue so that it can be executed at least
4248 N_CYCLES after the currently executing insn. Preserve insns
4249 chain for debugging purposes. */
4251 __inline static void
4252 queue_insn (insn, n_cycles)
4256 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
4257 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
4258 insn_queue[next_q] = link;
4261 if (sched_verbose >= 2)
4263 fprintf (dump, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn));
4265 if (INSN_BB (insn) != target_bb)
4266 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
4268 fprintf (dump, "queued for %d cycles.\n", n_cycles);
4273 /* Return nonzero if PAT is the pattern of an insn which makes a
4277 birthing_insn_p (pat)
4282 if (reload_completed == 1)
4285 if (GET_CODE (pat) == SET
4286 && GET_CODE (SET_DEST (pat)) == REG)
4288 rtx dest = SET_DEST (pat);
4289 int i = REGNO (dest);
4291 /* It would be more accurate to use refers_to_regno_p or
4292 reg_mentioned_p to determine when the dest is not live before this
4295 if (REGNO_REG_SET_P (bb_live_regs, i))
4296 return (REG_N_SETS (i) == 1);
4300 if (GET_CODE (pat) == PARALLEL)
4302 for (j = 0; j < XVECLEN (pat, 0); j++)
4303 if (birthing_insn_p (XVECEXP (pat, 0, j)))
4309 /* PREV is an insn that is ready to execute. Adjust its priority if that
4310 will help shorten register lifetimes. */
4312 __inline static void
4313 adjust_priority (prev)
4316 /* Trying to shorten register lives after reload has completed
4317 is useless and wrong. It gives inaccurate schedules. */
4318 if (reload_completed == 0)
4323 /* ??? This code has no effect, because REG_DEAD notes are removed
4324 before we ever get here. */
4325 for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
4326 if (REG_NOTE_KIND (note) == REG_DEAD)
4329 /* Defer scheduling insns which kill registers, since that
4330 shortens register lives. Prefer scheduling insns which
4331 make registers live for the same reason. */
4335 INSN_PRIORITY (prev) >>= 3;
4338 INSN_PRIORITY (prev) >>= 2;
4342 INSN_PRIORITY (prev) >>= 1;
4345 if (birthing_insn_p (PATTERN (prev)))
4347 int max = max_priority;
4349 if (max > INSN_PRIORITY (prev))
4350 INSN_PRIORITY (prev) = max;
4354 #ifdef ADJUST_PRIORITY
4355 ADJUST_PRIORITY (prev);
4360 /* INSN is the "currently executing insn". Launch each insn which was
4361 waiting on INSN. READY is a vector of insns which are ready to fire.
4362 N_READY is the number of elements in READY. CLOCK is the current
4366 schedule_insn (insn, ready, n_ready, clock)
4375 unit = insn_unit (insn);
4377 if (sched_verbose >= 2)
4379 fprintf (dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ", INSN_UID (insn));
4380 insn_print_units (insn);
4381 fprintf (dump, "\n");
4384 if (sched_verbose && unit == -1)
4385 visualize_no_unit (insn);
4387 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
4388 schedule_unit (unit, insn, clock);
4390 if (INSN_DEPEND (insn) == 0)
4393 /* This is used by the function adjust_priority above. */
4395 max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
4397 max_priority = INSN_PRIORITY (insn);
4399 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
4401 rtx next = XEXP (link, 0);
4402 int cost = insn_cost (insn, link, next);
4404 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
4406 if ((INSN_DEP_COUNT (next) -= 1) == 0)
4408 int effective_cost = INSN_TICK (next) - clock;
4410 /* For speculative insns, before inserting to ready/queue,
4411 check live, exception-free, and issue-delay */
4412 if (INSN_BB (next) != target_bb
4413 && (!IS_VALID (INSN_BB (next))
4415 || (IS_SPECULATIVE_INSN (next)
4416 && (insn_issue_delay (next) > 3
4417 || !check_live (next, INSN_BB (next))
4418 || !is_exception_free (next, INSN_BB (next), target_bb)))))
4421 if (sched_verbose >= 2)
4423 fprintf (dump, ";;\t\tdependences resolved: insn %d ", INSN_UID (next));
4425 if (current_nr_blocks > 1 && INSN_BB (next) != target_bb)
4426 fprintf (dump, "/b%d ", INSN_BLOCK (next));
4428 if (effective_cost <= 1)
4429 fprintf (dump, "into ready\n");
4431 fprintf (dump, "into queue with cost=%d\n", effective_cost);
4434 /* Adjust the priority of NEXT and either put it on the ready
4435 list or queue it. */
4436 adjust_priority (next);
4437 if (effective_cost <= 1)
4438 ready[n_ready++] = next;
4440 queue_insn (next, effective_cost);
4448 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4452 create_reg_dead_note (reg, insn)
4457 /* The number of registers killed after scheduling must be the same as the
4458 number of registers killed before scheduling. The number of REG_DEAD
4459 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4460 might become one DImode hard register REG_DEAD note, but the number of
4461 registers killed will be conserved.
4463 We carefully remove REG_DEAD notes from the dead_notes list, so that
4464 there will be none left at the end. If we run out early, then there
4465 is a bug somewhere in flow, combine and/or sched. */
4467 if (dead_notes == 0)
4469 if (current_nr_blocks <= 1)
4472 link = alloc_EXPR_LIST (REG_DEAD, NULL_RTX, NULL_RTX);
4476 /* Number of regs killed by REG. */
4477 int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
4478 : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
4479 /* Number of regs killed by REG_DEAD notes taken off the list. */
4483 reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4484 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4485 GET_MODE (XEXP (link, 0))));
4486 while (reg_note_regs < regs_killed)
4488 link = XEXP (link, 1);
4490 /* LINK might be zero if we killed more registers after scheduling
4491 than before, and the last hard register we kill is actually
4494 This is normal for interblock scheduling, so deal with it in
4495 that case, else abort. */
4496 if (link == NULL_RTX && current_nr_blocks <= 1)
4498 else if (link == NULL_RTX)
4499 link = alloc_EXPR_LIST (REG_DEAD, gen_rtx_REG (word_mode, 0),
4502 reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4503 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4504 GET_MODE (XEXP (link, 0))));
4506 dead_notes = XEXP (link, 1);
4508 /* If we took too many regs kills off, put the extra ones back. */
4509 while (reg_note_regs > regs_killed)
4511 rtx temp_reg, temp_link;
4513 temp_reg = gen_rtx_REG (word_mode, 0);
4514 temp_link = alloc_EXPR_LIST (REG_DEAD, temp_reg, dead_notes);
4515 dead_notes = temp_link;
4520 XEXP (link, 0) = reg;
4521 XEXP (link, 1) = REG_NOTES (insn);
4522 REG_NOTES (insn) = link;
4525 /* Subroutine on attach_deaths_insn--handles the recursive search
4526 through INSN. If SET_P is true, then x is being modified by the insn. */
4529 attach_deaths (x, insn, set_p)
4536 register enum rtx_code code;
4542 code = GET_CODE (x);
4554 /* Get rid of the easy cases first. */
4559 /* If the register dies in this insn, queue that note, and mark
4560 this register as needing to die. */
4561 /* This code is very similar to mark_used_1 (if set_p is false)
4562 and mark_set_1 (if set_p is true) in flow.c. */
4572 all_needed = some_needed = REGNO_REG_SET_P (old_live_regs, regno);
4573 if (regno < FIRST_PSEUDO_REGISTER)
4577 n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4580 int needed = (REGNO_REG_SET_P (old_live_regs, regno + n));
4581 some_needed |= needed;
4582 all_needed &= needed;
4586 /* If it wasn't live before we started, then add a REG_DEAD note.
4587 We must check the previous lifetime info not the current info,
4588 because we may have to execute this code several times, e.g.
4589 once for a clobber (which doesn't add a note) and later
4590 for a use (which does add a note).
4592 Always make the register live. We must do this even if it was
4593 live before, because this may be an insn which sets and uses
4594 the same register, in which case the register has already been
4595 killed, so we must make it live again.
4597 Global registers are always live, and should never have a REG_DEAD
4598 note added for them, so none of the code below applies to them. */
4600 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
4602 /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
4603 STACK_POINTER_REGNUM, since these are always considered to be
4604 live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
4605 if (regno != FRAME_POINTER_REGNUM
4606 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4607 && ! (regno == HARD_FRAME_POINTER_REGNUM)
4609 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4610 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
4612 && regno != STACK_POINTER_REGNUM)
4614 /* ??? It is perhaps a dead_or_set_p bug that it does
4615 not check for REG_UNUSED notes itself. This is necessary
4616 for the case where the SET_DEST is a subreg of regno, as
4617 dead_or_set_p handles subregs specially. */
4618 if (! all_needed && ! dead_or_set_p (insn, x)
4619 && ! find_reg_note (insn, REG_UNUSED, x))
4621 /* Check for the case where the register dying partially
4622 overlaps the register set by this insn. */
4623 if (regno < FIRST_PSEUDO_REGISTER
4624 && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
4626 int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4628 some_needed |= dead_or_set_regno_p (insn, regno + n);
4631 /* If none of the words in X is needed, make a REG_DEAD
4632 note. Otherwise, we must make partial REG_DEAD
4635 create_reg_dead_note (x, insn);
4640 /* Don't make a REG_DEAD note for a part of a
4641 register that is set in the insn. */
4642 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
4644 if (! REGNO_REG_SET_P (old_live_regs, regno+i)
4645 && ! dead_or_set_regno_p (insn, regno + i))
4646 create_reg_dead_note (gen_rtx_REG (reg_raw_mode[regno + i],
4653 if (regno < FIRST_PSEUDO_REGISTER)
4655 int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
4658 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4663 /* Recompute REG_BASIC_BLOCK as we update all the other
4664 dataflow information. */
4665 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
4666 sched_reg_basic_block[regno] = current_block_num;
4667 else if (sched_reg_basic_block[regno] != current_block_num)
4668 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
4670 SET_REGNO_REG_SET (bb_live_regs, regno);
4677 /* Handle tail-recursive case. */
4678 attach_deaths (XEXP (x, 0), insn, 0);
4682 case STRICT_LOW_PART:
4683 /* These two cases preserve the value of SET_P, so handle them
4685 attach_deaths (XEXP (x, 0), insn, set_p);
4690 /* This case preserves the value of SET_P for the first operand, but
4691 clears it for the other two. */
4692 attach_deaths (XEXP (x, 0), insn, set_p);
4693 attach_deaths (XEXP (x, 1), insn, 0);
4694 attach_deaths (XEXP (x, 2), insn, 0);
4698 /* Other cases: walk the insn. */
4699 fmt = GET_RTX_FORMAT (code);
4700 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4703 attach_deaths (XEXP (x, i), insn, 0);
4704 else if (fmt[i] == 'E')
4705 for (j = 0; j < XVECLEN (x, i); j++)
4706 attach_deaths (XVECEXP (x, i, j), insn, 0);
4711 /* After INSN has executed, add register death notes for each register
4712 that is dead after INSN. */
4715 attach_deaths_insn (insn)
4718 rtx x = PATTERN (insn);
4719 register RTX_CODE code = GET_CODE (x);
4724 attach_deaths (SET_SRC (x), insn, 0);
4726 /* A register might die here even if it is the destination, e.g.
4727 it is the target of a volatile read and is otherwise unused.
4728 Hence we must always call attach_deaths for the SET_DEST. */
4729 attach_deaths (SET_DEST (x), insn, 1);
4731 else if (code == PARALLEL)
4734 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4736 code = GET_CODE (XVECEXP (x, 0, i));
4739 attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
4741 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
4743 /* Flow does not add REG_DEAD notes to registers that die in
4744 clobbers, so we can't either. */
4745 else if (code != CLOBBER)
4746 attach_deaths (XVECEXP (x, 0, i), insn, 0);
4749 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4750 MEM being clobbered, just like flow. */
4751 else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == MEM)
4752 attach_deaths (XEXP (XEXP (x, 0), 0), insn, 0);
4753 /* Otherwise don't add a death note to things being clobbered. */
4754 else if (code != CLOBBER)
4755 attach_deaths (x, insn, 0);
4757 /* Make death notes for things used in the called function. */
4758 if (GET_CODE (insn) == CALL_INSN)
4759 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
4760 attach_deaths (XEXP (XEXP (link, 0), 0), insn,
4761 GET_CODE (XEXP (link, 0)) == CLOBBER);
4764 /* functions for handlnig of notes */
4766 /* Delete notes beginning with INSN and put them in the chain
4767 of notes ended by NOTE_LIST.
4768 Returns the insn following the notes. */
4771 unlink_other_notes (insn, tail)
4774 rtx prev = PREV_INSN (insn);
4776 while (insn != tail && GET_CODE (insn) == NOTE)
4778 rtx next = NEXT_INSN (insn);
4779 /* Delete the note from its current position. */
4781 NEXT_INSN (prev) = next;
4783 PREV_INSN (next) = prev;
4785 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4786 immediately after the call they follow. We use a fake
4787 (REG_DEAD (const_int -1)) note to remember them.
4788 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4789 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
4790 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
4791 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
4792 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
4793 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
4795 /* Insert the note at the end of the notes list. */
4796 PREV_INSN (insn) = note_list;
4798 NEXT_INSN (note_list) = insn;
4807 /* Delete line notes beginning with INSN. Record line-number notes so
4808 they can be reused. Returns the insn following the notes. */
4811 unlink_line_notes (insn, tail)
4814 rtx prev = PREV_INSN (insn);
4816 while (insn != tail && GET_CODE (insn) == NOTE)
4818 rtx next = NEXT_INSN (insn);
4820 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
4822 /* Delete the note from its current position. */
4824 NEXT_INSN (prev) = next;
4826 PREV_INSN (next) = prev;
4828 /* Record line-number notes so they can be reused. */
4829 LINE_NOTE (insn) = insn;
4839 /* Return the head and tail pointers of BB. */
4841 __inline static void
4842 get_block_head_tail (bb, headp, tailp)
4852 b = BB_TO_BLOCK (bb);
4854 /* HEAD and TAIL delimit the basic block being scheduled. */
4855 head = basic_block_head[b];
4856 tail = basic_block_end[b];
4858 /* Don't include any notes or labels at the beginning of the
4859 basic block, or notes at the ends of basic blocks. */
4860 while (head != tail)
4862 if (GET_CODE (head) == NOTE)
4863 head = NEXT_INSN (head);
4864 else if (GET_CODE (tail) == NOTE)
4865 tail = PREV_INSN (tail);
4866 else if (GET_CODE (head) == CODE_LABEL)
4867 head = NEXT_INSN (head);
4876 /* Delete line notes from bb. Save them so they can be later restored
4877 (in restore_line_notes ()). */
4888 get_block_head_tail (bb, &head, &tail);
4891 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4894 next_tail = NEXT_INSN (tail);
4895 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4899 /* Farm out notes, and maybe save them in NOTE_LIST.
4900 This is needed to keep the debugger from
4901 getting completely deranged. */
4902 if (GET_CODE (insn) == NOTE)
4905 insn = unlink_line_notes (insn, next_tail);
4911 if (insn == next_tail)
4917 /* Save line number notes for each insn in bb. */
4920 save_line_notes (bb)
4926 /* We must use the true line number for the first insn in the block
4927 that was computed and saved at the start of this pass. We can't
4928 use the current line number, because scheduling of the previous
4929 block may have changed the current line number. */
4931 rtx line = line_note_head[BB_TO_BLOCK (bb)];
4934 get_block_head_tail (bb, &head, &tail);
4935 next_tail = NEXT_INSN (tail);
4937 for (insn = basic_block_head[BB_TO_BLOCK (bb)];
4939 insn = NEXT_INSN (insn))
4940 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4943 LINE_NOTE (insn) = line;
4947 /* After bb was scheduled, insert line notes into the insns list. */
4950 restore_line_notes (bb)
4953 rtx line, note, prev, new;
4954 int added_notes = 0;
4956 rtx head, next_tail, insn;
4958 b = BB_TO_BLOCK (bb);
4960 head = basic_block_head[b];
4961 next_tail = NEXT_INSN (basic_block_end[b]);
4963 /* Determine the current line-number. We want to know the current
4964 line number of the first insn of the block here, in case it is
4965 different from the true line number that was saved earlier. If
4966 different, then we need a line number note before the first insn
4967 of this block. If it happens to be the same, then we don't want to
4968 emit another line number note here. */
4969 for (line = head; line; line = PREV_INSN (line))
4970 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4973 /* Walk the insns keeping track of the current line-number and inserting
4974 the line-number notes as needed. */
4975 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4976 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4978 /* This used to emit line number notes before every non-deleted note.
4979 However, this confuses a debugger, because line notes not separated
4980 by real instructions all end up at the same address. I can find no
4981 use for line number notes before other notes, so none are emitted. */
4982 else if (GET_CODE (insn) != NOTE
4983 && (note = LINE_NOTE (insn)) != 0
4986 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
4987 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
4990 prev = PREV_INSN (insn);
4991 if (LINE_NOTE (note))
4993 /* Re-use the original line-number note. */
4994 LINE_NOTE (note) = 0;
4995 PREV_INSN (note) = prev;
4996 NEXT_INSN (prev) = note;
4997 PREV_INSN (insn) = note;
4998 NEXT_INSN (note) = insn;
5003 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
5004 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
5005 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
5008 if (sched_verbose && added_notes)
5009 fprintf (dump, ";; added %d line-number notes\n", added_notes);
5012 /* After scheduling the function, delete redundant line notes from the
5016 rm_redundant_line_notes ()
5019 rtx insn = get_insns ();
5020 int active_insn = 0;
5023 /* Walk the insns deleting redundant line-number notes. Many of these
5024 are already present. The remainder tend to occur at basic
5025 block boundaries. */
5026 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
5027 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
5029 /* If there are no active insns following, INSN is redundant. */
5030 if (active_insn == 0)
5033 NOTE_SOURCE_FILE (insn) = 0;
5034 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
5036 /* If the line number is unchanged, LINE is redundant. */
5038 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
5039 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
5042 NOTE_SOURCE_FILE (line) = 0;
5043 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
5050 else if (!((GET_CODE (insn) == NOTE
5051 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
5052 || (GET_CODE (insn) == INSN
5053 && (GET_CODE (PATTERN (insn)) == USE
5054 || GET_CODE (PATTERN (insn)) == CLOBBER))))
5057 if (sched_verbose && notes)
5058 fprintf (dump, ";; deleted %d line-number notes\n", notes);
5061 /* Delete notes between head and tail and put them in the chain
5062 of notes ended by NOTE_LIST. */
5065 rm_other_notes (head, tail)
5073 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
5076 next_tail = NEXT_INSN (tail);
5077 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5081 /* Farm out notes, and maybe save them in NOTE_LIST.
5082 This is needed to keep the debugger from
5083 getting completely deranged. */
5084 if (GET_CODE (insn) == NOTE)
5088 insn = unlink_other_notes (insn, next_tail);
5094 if (insn == next_tail)
5100 /* Constructor for `sometimes' data structure. */
5103 new_sometimes_live (regs_sometimes_live, regno, sometimes_max)
5104 struct sometimes *regs_sometimes_live;
5108 register struct sometimes *p;
5110 /* There should never be a register greater than max_regno here. If there
5111 is, it means that a define_split has created a new pseudo reg. This
5112 is not allowed, since there will not be flow info available for any
5113 new register, so catch the error here. */
5114 if (regno >= max_regno)
5117 p = ®s_sometimes_live[sometimes_max];
5120 p->calls_crossed = 0;
5122 return sometimes_max;
5125 /* Count lengths of all regs we are currently tracking,
5126 and find new registers no longer live. */
5129 finish_sometimes_live (regs_sometimes_live, sometimes_max)
5130 struct sometimes *regs_sometimes_live;
5135 for (i = 0; i < sometimes_max; i++)
5137 register struct sometimes *p = ®s_sometimes_live[i];
5138 int regno = p->regno;
5140 sched_reg_live_length[regno] += p->live_length;
5141 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5145 /* functions for computation of registers live/usage info */
5147 /* It is assumed that prior to scheduling basic_block_live_at_start (b)
5148 contains the registers that are alive at the entry to b.
5150 Two passes follow: The first pass is performed before the scheduling
5151 of a region. It scans each block of the region forward, computing
5152 the set of registers alive at the end of the basic block and
5153 discard REG_DEAD notes (done by find_pre_sched_live ()).
5155 The second path is invoked after scheduling all region blocks.
5156 It scans each block of the region backward, a block being traversed
5157 only after its succesors in the region. When the set of registers
5158 live at the end of a basic block may be changed by the scheduling
5159 (this may happen for multiple blocks region), it is computed as
5160 the union of the registers live at the start of its succesors.
5161 The last-use information is updated by inserting REG_DEAD notes.
5162 (done by find_post_sched_live ()) */
5164 /* Scan all the insns to be scheduled, removing register death notes.
5165 Register death notes end up in DEAD_NOTES.
5166 Recreate the register life information for the end of this basic
5170 find_pre_sched_live (bb)
5173 rtx insn, next_tail, head, tail;
5174 int b = BB_TO_BLOCK (bb);
5176 get_block_head_tail (bb, &head, &tail);
5177 COPY_REG_SET (bb_live_regs, basic_block_live_at_start[b]);
5178 next_tail = NEXT_INSN (tail);
5180 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5182 rtx prev, next, link;
5185 /* Handle register life information. */
5186 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
5188 /* See if the register gets born here. */
5189 /* We must check for registers being born before we check for
5190 registers dying. It is possible for a register to be born and
5191 die in the same insn, e.g. reading from a volatile memory
5192 location into an otherwise unused register. Such a register
5193 must be marked as dead after this insn. */
5194 if (GET_CODE (PATTERN (insn)) == SET
5195 || GET_CODE (PATTERN (insn)) == CLOBBER)
5197 sched_note_set (PATTERN (insn), 0);
5201 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5204 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5205 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5206 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5208 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5212 /* ??? This code is obsolete and should be deleted. It
5213 is harmless though, so we will leave it in for now. */
5214 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5215 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
5216 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5219 /* Each call cobbers (makes live) all call-clobbered regs
5220 that are not global or fixed. Note that the function-value
5221 reg is a call_clobbered reg. */
5222 if (GET_CODE (insn) == CALL_INSN)
5225 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
5226 if (call_used_regs[j] && !global_regs[j]
5229 SET_REGNO_REG_SET (bb_live_regs, j);
5233 /* Need to know what registers this insn kills. */
5234 for (prev = 0, link = REG_NOTES (insn); link; link = next)
5236 next = XEXP (link, 1);
5237 if ((REG_NOTE_KIND (link) == REG_DEAD
5238 || REG_NOTE_KIND (link) == REG_UNUSED)
5239 /* Verify that the REG_NOTE has a valid value. */
5240 && GET_CODE (XEXP (link, 0)) == REG)
5242 register int regno = REGNO (XEXP (link, 0));
5246 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5248 if (REG_NOTE_KIND (link) == REG_DEAD)
5251 XEXP (prev, 1) = next;
5253 REG_NOTES (insn) = next;
5254 XEXP (link, 1) = dead_notes;
5260 if (regno < FIRST_PSEUDO_REGISTER)
5262 int j = HARD_REGNO_NREGS (regno,
5263 GET_MODE (XEXP (link, 0)));
5266 CLEAR_REGNO_REG_SET (bb_live_regs, regno+j);
5271 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
5279 INSN_REG_WEIGHT (insn) = reg_weight;
5283 /* Update register life and usage information for block bb
5284 after scheduling. Put register dead notes back in the code. */
5287 find_post_sched_live (bb)
5294 rtx head, tail, prev_head, next_tail;
5296 register struct sometimes *regs_sometimes_live;
5298 b = BB_TO_BLOCK (bb);
5300 /* compute live regs at the end of bb as a function of its successors. */
5301 if (current_nr_blocks > 1)
5306 first_edge = e = OUT_EDGES (b);
5307 CLEAR_REG_SET (bb_live_regs);
5314 b_succ = TO_BLOCK (e);
5315 IOR_REG_SET (bb_live_regs, basic_block_live_at_start[b_succ]);
5318 while (e != first_edge);
5321 get_block_head_tail (bb, &head, &tail);
5322 next_tail = NEXT_INSN (tail);
5323 prev_head = PREV_INSN (head);
5325 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
5326 if (REGNO_REG_SET_P (bb_live_regs, i))
5327 sched_reg_basic_block[i] = REG_BLOCK_GLOBAL;
5329 /* if the block is empty, same regs are alive at its end and its start.
5330 since this is not guaranteed after interblock scheduling, make sure they
5331 are truly identical. */
5332 if (NEXT_INSN (prev_head) == tail
5333 && (GET_RTX_CLASS (GET_CODE (tail)) != 'i'))
5335 if (current_nr_blocks > 1)
5336 COPY_REG_SET (basic_block_live_at_start[b], bb_live_regs);
5341 b = BB_TO_BLOCK (bb);
5342 current_block_num = b;
5344 /* Keep track of register lives. */
5345 old_live_regs = ALLOCA_REG_SET ();
5347 = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
5350 /* initiate "sometimes" data, starting with registers live at end */
5352 COPY_REG_SET (old_live_regs, bb_live_regs);
5353 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, 0, j,
5356 = new_sometimes_live (regs_sometimes_live,
5360 /* scan insns back, computing regs live info */
5361 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
5363 /* First we kill registers set by this insn, and then we
5364 make registers used by this insn live. This is the opposite
5365 order used above because we are traversing the instructions
5368 /* Strictly speaking, we should scan REG_UNUSED notes and make
5369 every register mentioned there live, however, we will just
5370 kill them again immediately below, so there doesn't seem to
5371 be any reason why we bother to do this. */
5373 /* See if this is the last notice we must take of a register. */
5374 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5377 if (GET_CODE (PATTERN (insn)) == SET
5378 || GET_CODE (PATTERN (insn)) == CLOBBER)
5379 sched_note_set (PATTERN (insn), 1);
5380 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5382 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5383 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5384 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5385 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 1);
5388 /* This code keeps life analysis information up to date. */
5389 if (GET_CODE (insn) == CALL_INSN)
5391 register struct sometimes *p;
5393 /* A call kills all call used registers that are not
5394 global or fixed, except for those mentioned in the call
5395 pattern which will be made live again later. */
5396 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5397 if (call_used_regs[i] && ! global_regs[i]
5400 CLEAR_REGNO_REG_SET (bb_live_regs, i);
5403 /* Regs live at the time of a call instruction must not
5404 go in a register clobbered by calls. Record this for
5405 all regs now live. Note that insns which are born or
5406 die in a call do not cross a call, so this must be done
5407 after the killings (above) and before the births
5409 p = regs_sometimes_live;
5410 for (i = 0; i < sometimes_max; i++, p++)
5411 if (REGNO_REG_SET_P (bb_live_regs, p->regno))
5412 p->calls_crossed += 1;
5415 /* Make every register used live, and add REG_DEAD notes for
5416 registers which were not live before we started. */
5417 attach_deaths_insn (insn);
5419 /* Find registers now made live by that instruction. */
5420 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs, old_live_regs, 0, j,
5423 = new_sometimes_live (regs_sometimes_live,
5426 IOR_REG_SET (old_live_regs, bb_live_regs);
5428 /* Count lengths of all regs we are worrying about now,
5429 and handle registers no longer live. */
5431 for (i = 0; i < sometimes_max; i++)
5433 register struct sometimes *p = ®s_sometimes_live[i];
5434 int regno = p->regno;
5436 p->live_length += 1;
5438 if (!REGNO_REG_SET_P (bb_live_regs, regno))
5440 /* This is the end of one of this register's lifetime
5441 segments. Save the lifetime info collected so far,
5442 and clear its bit in the old_live_regs entry. */
5443 sched_reg_live_length[regno] += p->live_length;
5444 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5445 CLEAR_REGNO_REG_SET (old_live_regs, p->regno);
5447 /* Delete the reg_sometimes_live entry for this reg by
5448 copying the last entry over top of it. */
5449 *p = regs_sometimes_live[--sometimes_max];
5450 /* ...and decrement i so that this newly copied entry
5451 will be processed. */
5457 finish_sometimes_live (regs_sometimes_live, sometimes_max);
5459 /* In interblock scheduling, basic_block_live_at_start may have changed. */
5460 if (current_nr_blocks > 1)
5461 COPY_REG_SET (basic_block_live_at_start[b], bb_live_regs);
5464 FREE_REG_SET (old_live_regs);
5465 } /* find_post_sched_live */
5467 /* After scheduling the subroutine, restore information about uses of
5475 if (n_basic_blocks > 0)
5476 for (regno = FIRST_PSEUDO_REGISTER; regno < max_regno; regno++)
5477 if (REGNO_REG_SET_P (basic_block_live_at_start[0], regno))
5478 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
5480 for (regno = 0; regno < max_regno; regno++)
5481 if (sched_reg_live_length[regno])
5485 if (REG_LIVE_LENGTH (regno) > sched_reg_live_length[regno])
5487 ";; register %d life shortened from %d to %d\n",
5488 regno, REG_LIVE_LENGTH (regno),
5489 sched_reg_live_length[regno]);
5490 /* Negative values are special; don't overwrite the current
5491 reg_live_length value if it is negative. */
5492 else if (REG_LIVE_LENGTH (regno) < sched_reg_live_length[regno]
5493 && REG_LIVE_LENGTH (regno) >= 0)
5495 ";; register %d life extended from %d to %d\n",
5496 regno, REG_LIVE_LENGTH (regno),
5497 sched_reg_live_length[regno]);
5499 if (!REG_N_CALLS_CROSSED (regno)
5500 && sched_reg_n_calls_crossed[regno])
5502 ";; register %d now crosses calls\n", regno);
5503 else if (REG_N_CALLS_CROSSED (regno)
5504 && !sched_reg_n_calls_crossed[regno]
5505 && REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5507 ";; register %d no longer crosses calls\n", regno);
5509 if (REG_BASIC_BLOCK (regno) != sched_reg_basic_block[regno]
5510 && sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5511 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5513 ";; register %d changed basic block from %d to %d\n",
5514 regno, REG_BASIC_BLOCK(regno),
5515 sched_reg_basic_block[regno]);
5518 /* Negative values are special; don't overwrite the current
5519 reg_live_length value if it is negative. */
5520 if (REG_LIVE_LENGTH (regno) >= 0)
5521 REG_LIVE_LENGTH (regno) = sched_reg_live_length[regno];
5523 if (sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5524 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5525 REG_BASIC_BLOCK(regno) = sched_reg_basic_block[regno];
5527 /* We can't change the value of reg_n_calls_crossed to zero for
5528 pseudos which are live in more than one block.
5530 This is because combine might have made an optimization which
5531 invalidated basic_block_live_at_start and reg_n_calls_crossed,
5532 but it does not update them. If we update reg_n_calls_crossed
5533 here, the two variables are now inconsistent, and this might
5534 confuse the caller-save code into saving a register that doesn't
5535 need to be saved. This is only a problem when we zero calls
5536 crossed for a pseudo live in multiple basic blocks.
5538 Alternatively, we could try to correctly update basic block live
5539 at start here in sched, but that seems complicated.
5541 Note: it is possible that a global register became local, as result
5542 of interblock motion, but will remain marked as a global register. */
5543 if (sched_reg_n_calls_crossed[regno]
5544 || REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5545 REG_N_CALLS_CROSSED (regno) = sched_reg_n_calls_crossed[regno];
5550 /* Scheduling clock, modified in schedule_block() and queue_to_ready () */
5551 static int clock_var;
5553 /* Move insns that became ready to fire from queue to ready list. */
5556 queue_to_ready (ready, n_ready)
5563 q_ptr = NEXT_Q (q_ptr);
5565 /* Add all pending insns that can be scheduled without stalls to the
5567 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
5570 insn = XEXP (link, 0);
5573 if (sched_verbose >= 2)
5574 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5576 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5577 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5579 ready[n_ready++] = insn;
5580 if (sched_verbose >= 2)
5581 fprintf (dump, "moving to ready without stalls\n");
5583 insn_queue[q_ptr] = 0;
5585 /* If there are no ready insns, stall until one is ready and add all
5586 of the pending insns at that point to the ready list. */
5589 register int stalls;
5591 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
5593 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
5595 for (; link; link = XEXP (link, 1))
5597 insn = XEXP (link, 0);
5600 if (sched_verbose >= 2)
5601 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5603 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5604 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5606 ready[n_ready++] = insn;
5607 if (sched_verbose >= 2)
5608 fprintf (dump, "moving to ready with %d stalls\n", stalls);
5610 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
5617 if (sched_verbose && stalls)
5618 visualize_stall_cycles (BB_TO_BLOCK (target_bb), stalls);
5619 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
5620 clock_var += stalls;
5625 /* Print the ready list for debugging purposes. Callable from debugger. */
5628 debug_ready_list (ready, n_ready)
5634 for (i = 0; i < n_ready; i++)
5636 fprintf (dump, " %d", INSN_UID (ready[i]));
5637 if (current_nr_blocks > 1 && INSN_BB (ready[i]) != target_bb)
5638 fprintf (dump, "/b%d", INSN_BLOCK (ready[i]));
5640 fprintf (dump, "\n");
5643 /* Print names of units on which insn can/should execute, for debugging. */
5646 insn_print_units (insn)
5650 int unit = insn_unit (insn);
5653 fprintf (dump, "none");
5655 fprintf (dump, "%s", function_units[unit].name);
5658 fprintf (dump, "[");
5659 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
5662 fprintf (dump, "%s", function_units[i].name);
5664 fprintf (dump, " ");
5666 fprintf (dump, "]");
5670 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5671 of a basic block. If more lines are needed, table is splitted to two.
5672 n_visual_lines is the number of lines printed so far for a block.
5673 visual_tbl contains the block visualization info.
5674 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5675 #define MAX_VISUAL_LINES 100
5680 rtx vis_no_unit[10];
5682 /* Finds units that are in use in this fuction. Required only
5683 for visualization. */
5686 init_target_units ()
5691 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
5693 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5696 unit = insn_unit (insn);
5699 target_units |= ~unit;
5701 target_units |= (1 << unit);
5705 /* Return the length of the visualization table */
5708 get_visual_tbl_length ()
5714 /* compute length of one field in line */
5715 s = (char *) alloca (INSN_LEN + 5);
5716 sprintf (s, " %33s", "uname");
5719 /* compute length of one line */
5722 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5723 if (function_units[unit].bitmask & target_units)
5724 for (i = 0; i < function_units[unit].multiplicity; i++)
5727 n += strlen ("\n") + 2;
5729 /* compute length of visualization string */
5730 return (MAX_VISUAL_LINES * n);
5733 /* Init block visualization debugging info */
5736 init_block_visualization ()
5738 strcpy (visual_tbl, "");
5745 /* This recognizes rtx, I classified as expressions. These are always */
5746 /* represent some action on values or results of other expression, */
5747 /* that may be stored in objects representing values. */
5750 print_exp (buf, x, verbose)
5755 char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
5757 switch (GET_CODE (x))
5760 print_value (t1, XEXP (x, 0), verbose);
5761 print_value (t2, XEXP (x, 1), verbose);
5762 sprintf (buf, "%s+%s", t1, t2);
5765 print_value (t1, XEXP (x, 0), verbose);
5766 print_value (t2, XEXP (x, 1), verbose);
5767 sprintf (buf, "%sl+%s", t1, t2);
5770 print_value (t1, XEXP (x, 0), verbose);
5771 print_value (t2, XEXP (x, 1), verbose);
5772 sprintf (buf, "%s-%s", t1, t2);
5775 print_value (t1, XEXP (x, 0), verbose);
5776 print_value (t2, XEXP (x, 1), verbose);
5777 sprintf (buf, "%s??%s", t1, t2);
5780 print_value (t1, XEXP (x, 0), verbose);
5781 sprintf (buf, "-%s", t1);
5784 print_value (t1, XEXP (x, 0), verbose);
5785 print_value (t2, XEXP (x, 1), verbose);
5786 sprintf (buf, "%s*%s", t1, t2);
5789 print_value (t1, XEXP (x, 0), verbose);
5790 print_value (t2, XEXP (x, 1), verbose);
5791 sprintf (buf, "%s/%s", t1, t2);
5794 print_value (t1, XEXP (x, 0), verbose);
5795 print_value (t2, XEXP (x, 1), verbose);
5796 sprintf (buf, "%su/%s", t1, t2);
5799 print_value (t1, XEXP (x, 0), verbose);
5800 print_value (t2, XEXP (x, 1), verbose);
5801 sprintf (buf, "%s%%%s", t1, t2);
5804 print_value (t1, XEXP (x, 0), verbose);
5805 print_value (t2, XEXP (x, 1), verbose);
5806 sprintf (buf, "%su%%%s", t1, t2);
5809 print_value (t1, XEXP (x, 0), verbose);
5810 print_value (t2, XEXP (x, 1), verbose);
5811 sprintf (buf, "smin (%s, %s)", t1, t2);
5814 print_value (t1, XEXP (x, 0), verbose);
5815 print_value (t2, XEXP (x, 1), verbose);
5816 sprintf (buf, "smax(%s,%s)", t1, t2);
5819 print_value (t1, XEXP (x, 0), verbose);
5820 print_value (t2, XEXP (x, 1), verbose);
5821 sprintf (buf, "umin (%s, %s)", t1, t2);
5824 print_value (t1, XEXP (x, 0), verbose);
5825 print_value (t2, XEXP (x, 1), verbose);
5826 sprintf (buf, "umax(%s,%s)", t1, t2);
5829 print_value (t1, XEXP (x, 0), verbose);
5830 sprintf (buf, "!%s", t1);
5833 print_value (t1, XEXP (x, 0), verbose);
5834 print_value (t2, XEXP (x, 1), verbose);
5835 sprintf (buf, "%s&%s", t1, t2);
5838 print_value (t1, XEXP (x, 0), verbose);
5839 print_value (t2, XEXP (x, 1), verbose);
5840 sprintf (buf, "%s|%s", t1, t2);
5843 print_value (t1, XEXP (x, 0), verbose);
5844 print_value (t2, XEXP (x, 1), verbose);
5845 sprintf (buf, "%s^%s", t1, t2);
5848 print_value (t1, XEXP (x, 0), verbose);
5849 print_value (t2, XEXP (x, 1), verbose);
5850 sprintf (buf, "%s<<%s", t1, t2);
5853 print_value (t1, XEXP (x, 0), verbose);
5854 print_value (t2, XEXP (x, 1), verbose);
5855 sprintf (buf, "%s0>%s", t1, t2);
5858 print_value (t1, XEXP (x, 0), verbose);
5859 print_value (t2, XEXP (x, 1), verbose);
5860 sprintf (buf, "%s>>%s", t1, t2);
5863 print_value (t1, XEXP (x, 0), verbose);
5864 print_value (t2, XEXP (x, 1), verbose);
5865 sprintf (buf, "%s<-<%s", t1, t2);
5868 print_value (t1, XEXP (x, 0), verbose);
5869 print_value (t2, XEXP (x, 1), verbose);
5870 sprintf (buf, "%s>->%s", t1, t2);
5873 print_value (t1, XEXP (x, 0), verbose);
5874 sprintf (buf, "abs(%s)", t1);
5877 print_value (t1, XEXP (x, 0), verbose);
5878 sprintf (buf, "sqrt(%s)", t1);
5881 print_value (t1, XEXP (x, 0), verbose);
5882 sprintf (buf, "ffs(%s)", t1);
5885 print_value (t1, XEXP (x, 0), verbose);
5886 print_value (t2, XEXP (x, 1), verbose);
5887 sprintf (buf, "%s == %s", t1, t2);
5890 print_value (t1, XEXP (x, 0), verbose);
5891 print_value (t2, XEXP (x, 1), verbose);
5892 sprintf (buf, "%s!=%s", t1, t2);
5895 print_value (t1, XEXP (x, 0), verbose);
5896 print_value (t2, XEXP (x, 1), verbose);
5897 sprintf (buf, "%s>%s", t1, t2);
5900 print_value (t1, XEXP (x, 0), verbose);
5901 print_value (t2, XEXP (x, 1), verbose);
5902 sprintf (buf, "%s>u%s", t1, t2);
5905 print_value (t1, XEXP (x, 0), verbose);
5906 print_value (t2, XEXP (x, 1), verbose);
5907 sprintf (buf, "%s<%s", t1, t2);
5910 print_value (t1, XEXP (x, 0), verbose);
5911 print_value (t2, XEXP (x, 1), verbose);
5912 sprintf (buf, "%s<u%s", t1, t2);
5915 print_value (t1, XEXP (x, 0), verbose);
5916 print_value (t2, XEXP (x, 1), verbose);
5917 sprintf (buf, "%s>=%s", t1, t2);
5920 print_value (t1, XEXP (x, 0), verbose);
5921 print_value (t2, XEXP (x, 1), verbose);
5922 sprintf (buf, "%s>=u%s", t1, t2);
5925 print_value (t1, XEXP (x, 0), verbose);
5926 print_value (t2, XEXP (x, 1), verbose);
5927 sprintf (buf, "%s<=%s", t1, t2);
5930 print_value (t1, XEXP (x, 0), verbose);
5931 print_value (t2, XEXP (x, 1), verbose);
5932 sprintf (buf, "%s<=u%s", t1, t2);
5935 print_value (t1, XEXP (x, 0), verbose);
5936 print_value (t2, XEXP (x, 1), verbose);
5937 print_value (t3, XEXP (x, 2), verbose);
5939 sprintf (buf, "sign_extract(%s,%s,%s)", t1, t2, t3);
5941 sprintf (buf, "sxt(%s,%s,%s)", t1, t2, t3);
5944 print_value (t1, XEXP (x, 0), verbose);
5945 print_value (t2, XEXP (x, 1), verbose);
5946 print_value (t3, XEXP (x, 2), verbose);
5948 sprintf (buf, "zero_extract(%s,%s,%s)", t1, t2, t3);
5950 sprintf (buf, "zxt(%s,%s,%s)", t1, t2, t3);
5953 print_value (t1, XEXP (x, 0), verbose);
5955 sprintf (buf, "sign_extend(%s)", t1);
5957 sprintf (buf, "sxn(%s)", t1);
5960 print_value (t1, XEXP (x, 0), verbose);
5962 sprintf (buf, "zero_extend(%s)", t1);
5964 sprintf (buf, "zxn(%s)", t1);
5967 print_value (t1, XEXP (x, 0), verbose);
5969 sprintf (buf, "float_extend(%s)", t1);
5971 sprintf (buf, "fxn(%s)", t1);
5974 print_value (t1, XEXP (x, 0), verbose);
5976 sprintf (buf, "trunc(%s)", t1);
5978 sprintf (buf, "trn(%s)", t1);
5980 case FLOAT_TRUNCATE:
5981 print_value (t1, XEXP (x, 0), verbose);
5983 sprintf (buf, "float_trunc(%s)", t1);
5985 sprintf (buf, "ftr(%s)", t1);
5988 print_value (t1, XEXP (x, 0), verbose);
5990 sprintf (buf, "float(%s)", t1);
5992 sprintf (buf, "flt(%s)", t1);
5994 case UNSIGNED_FLOAT:
5995 print_value (t1, XEXP (x, 0), verbose);
5997 sprintf (buf, "uns_float(%s)", t1);
5999 sprintf (buf, "ufl(%s)", t1);
6002 print_value (t1, XEXP (x, 0), verbose);
6003 sprintf (buf, "fix(%s)", t1);
6006 print_value (t1, XEXP (x, 0), verbose);
6008 sprintf (buf, "uns_fix(%s)", t1);
6010 sprintf (buf, "ufx(%s)", t1);
6013 print_value (t1, XEXP (x, 0), verbose);
6014 sprintf (buf, "--%s", t1);
6017 print_value (t1, XEXP (x, 0), verbose);
6018 sprintf (buf, "++%s", t1);
6021 print_value (t1, XEXP (x, 0), verbose);
6022 sprintf (buf, "%s--", t1);
6025 print_value (t1, XEXP (x, 0), verbose);
6026 sprintf (buf, "%s++", t1);
6029 print_value (t1, XEXP (x, 0), verbose);
6032 print_value (t2, XEXP (x, 1), verbose);
6033 sprintf (buf, "call %s argc:%s", t1, t2);
6036 sprintf (buf, "call %s", t1);
6039 print_exp (t1, XEXP (x, 0), verbose);
6040 print_value (t2, XEXP (x, 1), verbose);
6041 print_value (t3, XEXP (x, 2), verbose);
6042 sprintf (buf, "{(%s)?%s:%s}", t1, t2, t3);
6045 print_value (t1, TRAP_CONDITION (x), verbose);
6046 sprintf (buf, "trap_if %s", t1);
6052 sprintf (t1, "unspec{");
6053 for (i = 0; i < XVECLEN (x, 0); i++)
6055 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6056 sprintf (t3, "%s%s;", t1, t2);
6059 sprintf (buf, "%s}", t1);
6062 case UNSPEC_VOLATILE:
6066 sprintf (t1, "unspec/v{");
6067 for (i = 0; i < XVECLEN (x, 0); i++)
6069 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6070 sprintf (t3, "%s%s;", t1, t2);
6073 sprintf (buf, "%s}", t1);
6077 /* if (verbose) debug_rtx (x); else sprintf (buf, "$$$"); */
6078 sprintf (buf, "$$$");
6082 /* Prints rtxes, i customly classified as values. They're constants, */
6083 /* registers, labels, symbols and memory accesses. */
6086 print_value (buf, x, verbose)
6093 switch (GET_CODE (x))
6096 sprintf (buf, "%Xh", INTVAL (x));
6099 print_value (t, XEXP (x, 0), verbose);
6100 sprintf (buf, "<%s>", t);
6103 sprintf (buf, "\"%s\"", (char *) XEXP (x, 0));
6106 sprintf (buf, "`%s'", (char *) XEXP (x, 0));
6109 sprintf (buf, "L%d", INSN_UID (XEXP (x, 0)));
6112 print_value (buf, XEXP (x, 0), verbose);
6115 print_value (buf, XEXP (x, 0), verbose);
6118 if (GET_MODE (x) == SFmode
6119 || GET_MODE (x) == DFmode
6120 || GET_MODE (x) == XFmode
6121 || GET_MODE (x) == TFmode)
6125 sprintf (buf, "%s%d", t, REGNO (x));
6128 print_value (t, XEXP (x, 0), verbose);
6129 sprintf (buf, "%s#%d", t, SUBREG_WORD (x));
6132 sprintf (buf, "scratch");
6135 sprintf (buf, "cc0");
6138 sprintf (buf, "pc");
6141 print_value (t, XEXP (x, 0), verbose);
6142 sprintf (buf, "[%s]", t);
6145 print_exp (buf, x, verbose);
6149 /* The next step in insn detalization, its pattern recognition */
6152 print_pattern (buf, x, verbose)
6157 char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
6159 switch (GET_CODE (x))
6162 print_value (t1, SET_DEST (x), verbose);
6163 print_value (t2, SET_SRC (x), verbose);
6164 sprintf (buf, "%s=%s", t1, t2);
6167 sprintf (buf, "return");
6170 print_exp (buf, x, verbose);
6173 print_value (t1, XEXP (x, 0), verbose);
6174 sprintf (buf, "clobber %s", t1);
6177 print_value (t1, XEXP (x, 0), verbose);
6178 sprintf (buf, "use %s", t1);
6185 for (i = 0; i < XVECLEN (x, 0); i++)
6187 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6188 sprintf (t3, "%s%s;", t1, t2);
6191 sprintf (buf, "%s}", t1);
6198 sprintf (t1, "%%{");
6199 for (i = 0; i < XVECLEN (x, 0); i++)
6201 print_insn (t2, XVECEXP (x, 0, i), verbose);
6202 sprintf (t3, "%s%s;", t1, t2);
6205 sprintf (buf, "%s%%}", t1);
6209 sprintf (buf, "asm {%s}", XEXP (x, 0));
6214 print_value (buf, XEXP (x, 0), verbose);
6217 print_value (t1, TRAP_CONDITION (x), verbose);
6218 sprintf (buf, "trap_if %s", t1);
6224 sprintf (t1, "unspec{");
6225 for (i = 0; i < XVECLEN (x, 0); i++)
6227 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6228 sprintf (t3, "%s%s;", t1, t2);
6231 sprintf (buf, "%s}", t1);
6234 case UNSPEC_VOLATILE:
6238 sprintf (t1, "unspec/v{");
6239 for (i = 0; i < XVECLEN (x, 0); i++)
6241 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6242 sprintf (t3, "%s%s;", t1, t2);
6245 sprintf (buf, "%s}", t1);
6249 print_value (buf, x, verbose);
6251 } /* print_pattern */
6253 /* This is the main function in rtl visualization mechanism. It
6254 accepts an rtx and tries to recognize it as an insn, then prints it
6255 properly in human readable form, resembling assembler mnemonics. */
6256 /* For every insn it prints its UID and BB the insn belongs */
6257 /* too. (probably the last "option" should be extended somehow, since */
6258 /* it depends now on sched.c inner variables ...) */
6261 print_insn (buf, x, verbose)
6269 switch (GET_CODE (x))
6272 print_pattern (t, PATTERN (x), verbose);
6274 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (x),
6277 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6280 print_pattern (t, PATTERN (x), verbose);
6282 sprintf (buf, "b%d: i% 4d: jump %s", INSN_BB (x),
6285 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6289 if (GET_CODE (x) == PARALLEL)
6291 x = XVECEXP (x, 0, 0);
6292 print_pattern (t, x, verbose);
6295 strcpy (t, "call <...>");
6297 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (insn),
6298 INSN_UID (insn), t);
6300 sprintf (buf, "%-4d %s", INSN_UID (insn), t);
6303 sprintf (buf, "L%d:", INSN_UID (x));
6306 sprintf (buf, "i% 4d: barrier", INSN_UID (x));
6309 if (NOTE_LINE_NUMBER (x) > 0)
6310 sprintf (buf, "%4d note \"%s\" %d", INSN_UID (x),
6311 NOTE_SOURCE_FILE (x), NOTE_LINE_NUMBER (x));
6313 sprintf (buf, "%4d %s", INSN_UID (x),
6314 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x)));
6319 sprintf (buf, "Not an INSN at all\n");
6323 sprintf (buf, "i%-4d <What?>", INSN_UID (x));
6328 print_insn_chain (rtx_first)
6331 register rtx tmp_rtx;
6334 strcpy (str, "(nil)\n");
6336 switch (GET_CODE (rtx_first))
6344 for (tmp_rtx = rtx_first; tmp_rtx != NULL;
6345 tmp_rtx = NEXT_INSN (tmp_rtx))
6347 print_insn (str, tmp_rtx, 0);
6348 printf ("%s\n", str);
6352 print_insn (str, rtx_first, 0);
6353 printf ("%s\n", str);
6355 } /* print_insn_chain */
6357 /* Print visualization debugging info */
6360 print_block_visualization (b, s)
6367 fprintf (dump, "\n;; ==================== scheduling visualization for block %d %s \n", b, s);
6369 /* Print names of units */
6370 fprintf (dump, ";; %-8s", "clock");
6371 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6372 if (function_units[unit].bitmask & target_units)
6373 for (i = 0; i < function_units[unit].multiplicity; i++)
6374 fprintf (dump, " %-33s", function_units[unit].name);
6375 fprintf (dump, " %-8s\n", "no-unit");
6377 fprintf (dump, ";; %-8s", "=====");
6378 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6379 if (function_units[unit].bitmask & target_units)
6380 for (i = 0; i < function_units[unit].multiplicity; i++)
6381 fprintf (dump, " %-33s", "==============================");
6382 fprintf (dump, " %-8s\n", "=======");
6384 /* Print insns in each cycle */
6385 fprintf (dump, "%s\n", visual_tbl);
6388 /* Print insns in the 'no_unit' column of visualization */
6391 visualize_no_unit (insn)
6394 vis_no_unit[n_vis_no_unit] = insn;
6398 /* Print insns scheduled in clock, for visualization. */
6401 visualize_scheduled_insns (b, clock)
6406 /* if no more room, split table into two */
6407 if (n_visual_lines >= MAX_VISUAL_LINES)
6409 print_block_visualization (b, "(incomplete)");
6410 init_block_visualization ();
6415 sprintf (visual_tbl + strlen (visual_tbl), ";; %-8d", clock);
6416 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6417 if (function_units[unit].bitmask & target_units)
6418 for (i = 0; i < function_units[unit].multiplicity; i++)
6420 int instance = unit + i * FUNCTION_UNITS_SIZE;
6421 rtx insn = unit_last_insn[instance];
6423 /* print insns that still keep the unit busy */
6425 actual_hazard_this_instance (unit, instance, insn, clock, 0))
6428 print_insn (str, insn, 0);
6429 str[INSN_LEN] = '\0';
6430 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", str);
6433 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", "------------------------------");
6436 /* print insns that are not assigned to any unit */
6437 for (i = 0; i < n_vis_no_unit; i++)
6438 sprintf (visual_tbl + strlen (visual_tbl), " %-8d",
6439 INSN_UID (vis_no_unit[i]));
6442 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6445 /* Print stalled cycles */
6448 visualize_stall_cycles (b, stalls)
6453 /* if no more room, split table into two */
6454 if (n_visual_lines >= MAX_VISUAL_LINES)
6456 print_block_visualization (b, "(incomplete)");
6457 init_block_visualization ();
6462 sprintf (visual_tbl + strlen (visual_tbl), ";; ");
6463 for (i = 0; i < stalls; i++)
6464 sprintf (visual_tbl + strlen (visual_tbl), ".");
6465 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6468 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn */
6471 move_insn1 (insn, last)
6474 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
6475 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
6477 NEXT_INSN (insn) = NEXT_INSN (last);
6478 PREV_INSN (NEXT_INSN (last)) = insn;
6480 NEXT_INSN (last) = insn;
6481 PREV_INSN (insn) = last;
6486 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
6487 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
6488 NOTEs. The REG_DEAD note following first one is contains the saved
6489 value for NOTE_BLOCK_NUMBER which is useful for
6490 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
6491 output by the instruction scheduler. Return the new value of LAST. */
6494 reemit_notes (insn, last)
6501 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
6503 if (REG_NOTE_KIND (note) == REG_DEAD
6504 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6506 if (INTVAL (XEXP (note, 0)) == NOTE_INSN_SETJMP)
6508 retval = emit_note_after (INTVAL (XEXP (note, 0)), insn);
6509 CONST_CALL_P (retval) = CONST_CALL_P (note);
6510 remove_note (insn, note);
6511 note = XEXP (note, 1);
6515 last = emit_note_before (INTVAL (XEXP (note, 0)), last);
6516 remove_note (insn, note);
6517 note = XEXP (note, 1);
6518 NOTE_BLOCK_NUMBER (last) = INTVAL (XEXP (note, 0));
6520 remove_note (insn, note);
6526 /* Move INSN, and all insns which should be issued before it,
6527 due to SCHED_GROUP_P flag. Reemit notes if needed.
6529 Return the last insn emitted by the scheduler, which is the
6530 return value from the first call to reemit_notes. */
6533 move_insn (insn, last)
6538 /* If INSN has SCHED_GROUP_P set, then issue it and any other
6539 insns with SCHED_GROUP_P set first. */
6540 while (SCHED_GROUP_P (insn))
6542 rtx prev = PREV_INSN (insn);
6544 /* Move a SCHED_GROUP_P insn. */
6545 move_insn1 (insn, last);
6546 /* If this is the first call to reemit_notes, then record
6547 its return value. */
6548 if (retval == NULL_RTX)
6549 retval = reemit_notes (insn, insn);
6551 reemit_notes (insn, insn);
6555 /* Now move the first non SCHED_GROUP_P insn. */
6556 move_insn1 (insn, last);
6558 /* If this is the first call to reemit_notes, then record
6559 its return value. */
6560 if (retval == NULL_RTX)
6561 retval = reemit_notes (insn, insn);
6563 reemit_notes (insn, insn);
6568 /* Return an insn which represents a SCHED_GROUP, which is
6569 the last insn in the group. */
6580 insn = next_nonnote_insn (insn);
6582 while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
6587 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
6588 possibly bringing insns from subsequent blocks in the same region.
6589 Return number of insns scheduled. */
6592 schedule_block (bb, rgn_n_insns)
6596 /* Local variables. */
6603 /* flow block of this bb */
6604 int b = BB_TO_BLOCK (bb);
6606 /* target_n_insns == number of insns in b before scheduling starts.
6607 sched_target_n_insns == how many of b's insns were scheduled.
6608 sched_n_insns == how many insns were scheduled in b */
6609 int target_n_insns = 0;
6610 int sched_target_n_insns = 0;
6611 int sched_n_insns = 0;
6613 #define NEED_NOTHING 0
6618 /* head/tail info for this block */
6625 /* We used to have code to avoid getting parameters moved from hard
6626 argument registers into pseudos.
6628 However, it was removed when it proved to be of marginal benefit
6629 and caused problems because schedule_block and compute_forward_dependences
6630 had different notions of what the "head" insn was. */
6631 get_block_head_tail (bb, &head, &tail);
6633 /* Interblock scheduling could have moved the original head insn from this
6634 block into a proceeding block. This may also cause schedule_block and
6635 compute_forward_dependences to have different notions of what the
6638 If the interblock movement happened to make this block start with
6639 some notes (LOOP, EH or SETJMP) before the first real insn, then
6640 HEAD will have various special notes attached to it which must be
6641 removed so that we don't end up with extra copies of the notes. */
6642 if (GET_RTX_CLASS (GET_CODE (head)) == 'i')
6646 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
6647 if (REG_NOTE_KIND (note) == REG_DEAD
6648 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6649 remove_note (head, note);
6652 next_tail = NEXT_INSN (tail);
6653 prev_head = PREV_INSN (head);
6655 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6656 to schedule this block. */
6658 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6659 return (sched_n_insns);
6664 fprintf (dump, ";; ======================================================\n");
6666 ";; -- basic block %d from %d to %d -- %s reload\n",
6667 b, INSN_UID (basic_block_head[b]),
6668 INSN_UID (basic_block_end[b]),
6669 (reload_completed ? "after" : "before"));
6670 fprintf (dump, ";; ======================================================\n");
6671 if (sched_debug_count >= 0)
6672 fprintf (dump, ";;\t -- sched_debug_count=%d\n", sched_debug_count);
6673 fprintf (dump, "\n");
6675 visual_tbl = (char *) alloca (get_visual_tbl_length ());
6676 init_block_visualization ();
6679 /* remove remaining note insns from the block, save them in
6680 note_list. These notes are restored at the end of
6681 schedule_block (). */
6683 rm_other_notes (head, tail);
6687 /* prepare current target block info */
6688 if (current_nr_blocks > 1)
6690 candidate_table = (candidate *) alloca (current_nr_blocks * sizeof (candidate));
6693 /* ??? It is not clear why bblst_size is computed this way. The original
6694 number was clearly too small as it resulted in compiler failures.
6695 Multiplying by the original number by 2 (to account for update_bbs
6696 members) seems to be a reasonable solution. */
6697 /* ??? Or perhaps there is a bug somewhere else in this file? */
6698 bblst_size = (current_nr_blocks - bb) * rgn_nr_edges * 2;
6699 bblst_table = (int *) alloca (bblst_size * sizeof (int));
6701 bitlst_table_last = 0;
6702 bitlst_table_size = rgn_nr_edges;
6703 bitlst_table = (int *) alloca (rgn_nr_edges * sizeof (int));
6705 compute_trg_info (bb);
6710 /* Allocate the ready list */
6711 ready = (rtx *) alloca ((rgn_n_insns + 1) * sizeof (rtx));
6713 /* Print debugging information. */
6714 if (sched_verbose >= 5)
6715 debug_dependencies ();
6718 /* Initialize ready list with all 'ready' insns in target block.
6719 Count number of insns in the target block being scheduled. */
6721 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6725 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6727 next = NEXT_INSN (insn);
6729 if (INSN_DEP_COUNT (insn) == 0
6730 && (SCHED_GROUP_P (next) == 0 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6731 ready[n_ready++] = insn;
6732 if (!(SCHED_GROUP_P (insn)))
6736 /* Add to ready list all 'ready' insns in valid source blocks.
6737 For speculative insns, check-live, exception-free, and
6739 for (bb_src = bb + 1; bb_src < current_nr_blocks; bb_src++)
6740 if (IS_VALID (bb_src))
6746 get_block_head_tail (bb_src, &head, &tail);
6747 src_next_tail = NEXT_INSN (tail);
6751 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6754 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
6756 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6759 if (!CANT_MOVE (insn)
6760 && (!IS_SPECULATIVE_INSN (insn)
6761 || (insn_issue_delay (insn) <= 3
6762 && check_live (insn, bb_src)
6763 && is_exception_free (insn, bb_src, target_bb))))
6768 next = NEXT_INSN (insn);
6769 if (INSN_DEP_COUNT (insn) == 0
6770 && (SCHED_GROUP_P (next) == 0
6771 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6772 ready[n_ready++] = insn;
6777 /* no insns scheduled in this block yet */
6778 last_scheduled_insn = 0;
6780 /* Sort the ready list */
6781 SCHED_SORT (ready, n_ready);
6783 if (sched_verbose >= 2)
6785 fprintf (dump, ";;\t\tReady list initially: ");
6786 debug_ready_list (ready, n_ready);
6789 /* Q_SIZE is the total number of insns in the queue. */
6793 bzero ((char *) insn_queue, sizeof (insn_queue));
6795 /* We start inserting insns after PREV_HEAD. */
6798 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6799 new_needs = (NEXT_INSN (prev_head) == basic_block_head[b]
6800 ? NEED_HEAD : NEED_NOTHING);
6801 if (PREV_INSN (next_tail) == basic_block_end[b])
6802 new_needs |= NEED_TAIL;
6804 /* loop until all the insns in BB are scheduled. */
6805 while (sched_target_n_insns < target_n_insns)
6809 #ifdef INTERBLOCK_DEBUG
6810 if (sched_debug_count == 0)
6815 /* Add to the ready list all pending insns that can be issued now.
6816 If there are no ready insns, increment clock until one
6817 is ready and add all pending insns at that point to the ready
6819 n_ready = queue_to_ready (ready, n_ready);
6824 if (sched_verbose >= 2)
6826 fprintf (dump, ";;\t\tReady list after queue_to_ready: ");
6827 debug_ready_list (ready, n_ready);
6830 /* Sort the ready list. */
6831 SCHED_SORT (ready, n_ready);
6835 fprintf (dump, ";;\tReady list (t =%3d): ", clock_var);
6836 debug_ready_list (ready, n_ready);
6839 /* Issue insns from ready list.
6840 It is important to count down from n_ready, because n_ready may change
6841 as insns are issued. */
6842 can_issue_more = issue_rate;
6843 for (i = n_ready - 1; i >= 0 && can_issue_more; i--)
6845 rtx insn = ready[i];
6846 int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
6850 queue_insn (insn, cost);
6851 ready[i] = ready[--n_ready]; /* remove insn from ready list */
6855 #ifdef INTERBLOCK_DEBUG
6856 if (sched_debug_count == 0)
6860 /* an interblock motion? */
6861 if (INSN_BB (insn) != target_bb)
6865 if (IS_SPECULATIVE_INSN (insn))
6868 if (!check_live (insn, INSN_BB (insn)))
6870 /* speculative motion, live check failed, remove
6871 insn from ready list */
6872 ready[i] = ready[--n_ready];
6875 update_live (insn, INSN_BB (insn));
6877 /* for speculative load, mark insns fed by it. */
6878 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
6879 set_spec_fed (insn);
6886 while (SCHED_GROUP_P (temp))
6887 temp = PREV_INSN (temp);
6889 /* Update source block boundaries. */
6890 b1 = INSN_BLOCK (temp);
6891 if (temp == basic_block_head[b1]
6892 && insn == basic_block_end[b1])
6894 /* We moved all the insns in the basic block.
6895 Emit a note after the last insn and update the
6896 begin/end boundaries to point to the note. */
6897 emit_note_after (NOTE_INSN_DELETED, insn);
6898 basic_block_end[b1] = NEXT_INSN (insn);
6899 basic_block_head[b1] = NEXT_INSN (insn);
6901 else if (insn == basic_block_end[b1])
6903 /* We took insns from the end of the basic block,
6904 so update the end of block boundary so that it
6905 points to the first insn we did not move. */
6906 basic_block_end[b1] = PREV_INSN (temp);
6908 else if (temp == basic_block_head[b1])
6910 /* We took insns from the start of the basic block,
6911 so update the start of block boundary so that
6912 it points to the first insn we did not move. */
6913 basic_block_head[b1] = NEXT_INSN (insn);
6918 /* in block motion */
6919 sched_target_n_insns++;
6922 last_scheduled_insn = insn;
6923 last = move_insn (insn, last);
6928 #ifdef INTERBLOCK_DEBUG
6929 if (sched_debug_count > 0)
6930 sched_debug_count--;
6933 n_ready = schedule_insn (insn, ready, n_ready, clock_var);
6935 /* remove insn from ready list */
6936 ready[i] = ready[--n_ready];
6938 /* close this block after scheduling its jump */
6939 if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
6947 visualize_scheduled_insns (b, clock_var);
6948 #ifdef INTERBLOCK_DEBUG
6949 if (sched_debug_count == 0)
6950 fprintf (dump, "........ sched_debug_count == 0 .................\n");
6958 fprintf (dump, ";;\tReady list (final): ");
6959 debug_ready_list (ready, n_ready);
6960 print_block_visualization (b, "");
6963 /* Sanity check -- queue must be empty now. Meaningless if region has
6964 multiple bbs, or if scheduling stopped by sched_debug_count. */
6965 if (current_nr_blocks > 1)
6966 #ifdef INTERBLOCK_DEBUG
6967 if (sched_debug_count != 0)
6969 if (!flag_schedule_interblock && q_size != 0)
6972 /* update head/tail boundaries. */
6973 head = NEXT_INSN (prev_head);
6976 #ifdef INTERBLOCK_DEBUG
6977 if (sched_debug_count == 0)
6978 /* compensate for stopping scheduling prematurely */
6979 for (i = sched_target_n_insns; i < target_n_insns; i++)
6980 tail = move_insn (group_leader (NEXT_INSN (tail)), tail);
6983 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6984 previously found among the insns. Insert them at the beginning
6988 rtx note_head = note_list;
6990 while (PREV_INSN (note_head))
6992 note_head = PREV_INSN (note_head);
6995 PREV_INSN (note_head) = PREV_INSN (head);
6996 NEXT_INSN (PREV_INSN (head)) = note_head;
6997 PREV_INSN (head) = note_list;
6998 NEXT_INSN (note_list) = head;
7002 /* update target block boundaries. */
7003 if (new_needs & NEED_HEAD)
7004 basic_block_head[b] = head;
7006 if (new_needs & NEED_TAIL)
7007 basic_block_end[b] = tail;
7012 fprintf (dump, ";; total time = %d\n;; new basic block head = %d\n",
7013 clock_var, INSN_UID (basic_block_head[b]));
7014 fprintf (dump, ";; new basic block end = %d\n\n",
7015 INSN_UID (basic_block_end[b]));
7018 return (sched_n_insns);
7019 } /* schedule_block () */
7022 /* print the bit-set of registers, S. callable from debugger */
7025 debug_reg_vector (s)
7030 EXECUTE_IF_SET_IN_REG_SET (s, 0, regno,
7032 fprintf (dump, " %d", regno);
7035 fprintf (dump, "\n");
7038 /* Use the backward dependences from LOG_LINKS to build
7039 forward dependences in INSN_DEPEND. */
7042 compute_block_forward_dependences (bb)
7048 enum reg_note dep_type;
7050 get_block_head_tail (bb, &head, &tail);
7051 next_tail = NEXT_INSN (tail);
7052 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
7054 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7057 insn = group_leader (insn);
7059 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
7061 rtx x = group_leader (XEXP (link, 0));
7064 if (x != XEXP (link, 0))
7067 /* Ignore dependences upon deleted insn */
7068 if (GET_CODE (x) == NOTE || INSN_DELETED_P (x))
7070 if (find_insn_list (insn, INSN_DEPEND (x)))
7073 new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
7075 dep_type = REG_NOTE_KIND (link);
7076 PUT_REG_NOTE_KIND (new_link, dep_type);
7078 INSN_DEPEND (x) = new_link;
7079 INSN_DEP_COUNT (insn) += 1;
7084 /* Initialize variables for region data dependence analysis.
7085 n_bbs is the number of region blocks */
7087 __inline static void
7088 init_rgn_data_dependences (n_bbs)
7093 /* variables for which one copy exists for each block */
7094 bzero ((char *) bb_pending_read_insns, n_bbs * sizeof (rtx));
7095 bzero ((char *) bb_pending_read_mems, n_bbs * sizeof (rtx));
7096 bzero ((char *) bb_pending_write_insns, n_bbs * sizeof (rtx));
7097 bzero ((char *) bb_pending_write_mems, n_bbs * sizeof (rtx));
7098 bzero ((char *) bb_pending_lists_length, n_bbs * sizeof (rtx));
7099 bzero ((char *) bb_last_pending_memory_flush, n_bbs * sizeof (rtx));
7100 bzero ((char *) bb_last_function_call, n_bbs * sizeof (rtx));
7101 bzero ((char *) bb_sched_before_next_call, n_bbs * sizeof (rtx));
7103 /* Create an insn here so that we can hang dependencies off of it later. */
7104 for (bb = 0; bb < n_bbs; bb++)
7106 bb_sched_before_next_call[bb] =
7107 gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
7108 NULL_RTX, 0, NULL_RTX, NULL_RTX);
7109 LOG_LINKS (bb_sched_before_next_call[bb]) = 0;
7113 /* Add dependences so that branches are scheduled to run last in their block */
7116 add_branch_dependences (head, tail)
7122 /* For all branches, calls, uses, and cc0 setters, force them to remain
7123 in order at the end of the block by adding dependencies and giving
7124 the last a high priority. There may be notes present, and prev_head
7127 Branches must obviously remain at the end. Calls should remain at the
7128 end since moving them results in worse register allocation. Uses remain
7129 at the end to ensure proper register allocation. cc0 setters remaim
7130 at the end because they can't be moved away from their cc0 user. */
7133 while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
7134 || (GET_CODE (insn) == INSN
7135 && (GET_CODE (PATTERN (insn)) == USE
7137 || sets_cc0_p (PATTERN (insn))
7140 || GET_CODE (insn) == NOTE)
7142 if (GET_CODE (insn) != NOTE)
7145 && !find_insn_list (insn, LOG_LINKS (last)))
7147 add_dependence (last, insn, REG_DEP_ANTI);
7148 INSN_REF_COUNT (insn)++;
7151 CANT_MOVE (insn) = 1;
7154 /* Skip over insns that are part of a group.
7155 Make each insn explicitly depend on the previous insn.
7156 This ensures that only the group header will ever enter
7157 the ready queue (and, when scheduled, will automatically
7158 schedule the SCHED_GROUP_P block). */
7159 while (SCHED_GROUP_P (insn))
7161 rtx temp = prev_nonnote_insn (insn);
7162 add_dependence (insn, temp, REG_DEP_ANTI);
7167 /* Don't overrun the bounds of the basic block. */
7171 insn = PREV_INSN (insn);
7174 /* make sure these insns are scheduled last in their block */
7177 while (insn != head)
7179 insn = prev_nonnote_insn (insn);
7181 if (INSN_REF_COUNT (insn) != 0)
7184 if (!find_insn_list (last, LOG_LINKS (insn)))
7185 add_dependence (last, insn, REG_DEP_ANTI);
7186 INSN_REF_COUNT (insn) = 1;
7188 /* Skip over insns that are part of a group. */
7189 while (SCHED_GROUP_P (insn))
7190 insn = prev_nonnote_insn (insn);
7194 /* Compute bacward dependences inside BB. In a multiple blocks region:
7195 (1) a bb is analyzed after its predecessors, and (2) the lists in
7196 effect at the end of bb (after analyzing for bb) are inherited by
7199 Specifically for reg-reg data dependences, the block insns are
7200 scanned by sched_analyze () top-to-bottom. Two lists are
7201 naintained by sched_analyze (): reg_last_defs[] for register DEFs,
7202 and reg_last_uses[] for register USEs.
7204 When analysis is completed for bb, we update for its successors:
7205 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7206 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7208 The mechanism for computing mem-mem data dependence is very
7209 similar, and the result is interblock dependences in the region. */
7212 compute_block_backward_dependences (bb)
7218 int max_reg = max_reg_num ();
7220 b = BB_TO_BLOCK (bb);
7222 if (current_nr_blocks == 1)
7224 reg_last_uses = (rtx *) alloca (max_reg * sizeof (rtx));
7225 reg_last_sets = (rtx *) alloca (max_reg * sizeof (rtx));
7227 bzero ((char *) reg_last_uses, max_reg * sizeof (rtx));
7228 bzero ((char *) reg_last_sets, max_reg * sizeof (rtx));
7230 pending_read_insns = 0;
7231 pending_read_mems = 0;
7232 pending_write_insns = 0;
7233 pending_write_mems = 0;
7234 pending_lists_length = 0;
7235 last_function_call = 0;
7236 last_pending_memory_flush = 0;
7237 sched_before_next_call
7238 = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
7239 NULL_RTX, 0, NULL_RTX, NULL_RTX);
7240 LOG_LINKS (sched_before_next_call) = 0;
7244 reg_last_uses = bb_reg_last_uses[bb];
7245 reg_last_sets = bb_reg_last_sets[bb];
7247 pending_read_insns = bb_pending_read_insns[bb];
7248 pending_read_mems = bb_pending_read_mems[bb];
7249 pending_write_insns = bb_pending_write_insns[bb];
7250 pending_write_mems = bb_pending_write_mems[bb];
7251 pending_lists_length = bb_pending_lists_length[bb];
7252 last_function_call = bb_last_function_call[bb];
7253 last_pending_memory_flush = bb_last_pending_memory_flush[bb];
7255 sched_before_next_call = bb_sched_before_next_call[bb];
7258 /* do the analysis for this block */
7259 get_block_head_tail (bb, &head, &tail);
7260 sched_analyze (head, tail);
7261 add_branch_dependences (head, tail);
7263 if (current_nr_blocks > 1)
7266 int b_succ, bb_succ;
7268 rtx link_insn, link_mem;
7271 /* these lists should point to the right place, for correct freeing later. */
7272 bb_pending_read_insns[bb] = pending_read_insns;
7273 bb_pending_read_mems[bb] = pending_read_mems;
7274 bb_pending_write_insns[bb] = pending_write_insns;
7275 bb_pending_write_mems[bb] = pending_write_mems;
7277 /* bb's structures are inherited by it's successors */
7278 first_edge = e = OUT_EDGES (b);
7282 b_succ = TO_BLOCK (e);
7283 bb_succ = BLOCK_TO_BB (b_succ);
7285 /* only bbs "below" bb, in the same region, are interesting */
7286 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
7293 for (reg = 0; reg < max_reg; reg++)
7296 /* reg-last-uses lists are inherited by bb_succ */
7297 for (u = reg_last_uses[reg]; u; u = XEXP (u, 1))
7299 if (find_insn_list (XEXP (u, 0), (bb_reg_last_uses[bb_succ])[reg]))
7302 (bb_reg_last_uses[bb_succ])[reg]
7303 = alloc_INSN_LIST (XEXP (u, 0),
7304 (bb_reg_last_uses[bb_succ])[reg]);
7307 /* reg-last-defs lists are inherited by bb_succ */
7308 for (u = reg_last_sets[reg]; u; u = XEXP (u, 1))
7310 if (find_insn_list (XEXP (u, 0), (bb_reg_last_sets[bb_succ])[reg]))
7313 (bb_reg_last_sets[bb_succ])[reg]
7314 = alloc_INSN_LIST (XEXP (u, 0),
7315 (bb_reg_last_sets[bb_succ])[reg]);
7319 /* mem read/write lists are inherited by bb_succ */
7320 link_insn = pending_read_insns;
7321 link_mem = pending_read_mems;
7324 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7325 bb_pending_read_insns[bb_succ],
7326 bb_pending_read_mems[bb_succ])))
7327 add_insn_mem_dependence (&bb_pending_read_insns[bb_succ],
7328 &bb_pending_read_mems[bb_succ],
7329 XEXP (link_insn, 0), XEXP (link_mem, 0));
7330 link_insn = XEXP (link_insn, 1);
7331 link_mem = XEXP (link_mem, 1);
7334 link_insn = pending_write_insns;
7335 link_mem = pending_write_mems;
7338 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7339 bb_pending_write_insns[bb_succ],
7340 bb_pending_write_mems[bb_succ])))
7341 add_insn_mem_dependence (&bb_pending_write_insns[bb_succ],
7342 &bb_pending_write_mems[bb_succ],
7343 XEXP (link_insn, 0), XEXP (link_mem, 0));
7345 link_insn = XEXP (link_insn, 1);
7346 link_mem = XEXP (link_mem, 1);
7349 /* last_function_call is inherited by bb_succ */
7350 for (u = last_function_call; u; u = XEXP (u, 1))
7352 if (find_insn_list (XEXP (u, 0), bb_last_function_call[bb_succ]))
7355 bb_last_function_call[bb_succ]
7356 = alloc_INSN_LIST (XEXP (u, 0),
7357 bb_last_function_call[bb_succ]);
7360 /* last_pending_memory_flush is inherited by bb_succ */
7361 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
7363 if (find_insn_list (XEXP (u, 0), bb_last_pending_memory_flush[bb_succ]))
7366 bb_last_pending_memory_flush[bb_succ]
7367 = alloc_INSN_LIST (XEXP (u, 0),
7368 bb_last_pending_memory_flush[bb_succ]);
7371 /* sched_before_next_call is inherited by bb_succ */
7372 x = LOG_LINKS (sched_before_next_call);
7373 for (; x; x = XEXP (x, 1))
7374 add_dependence (bb_sched_before_next_call[bb_succ],
7375 XEXP (x, 0), REG_DEP_ANTI);
7379 while (e != first_edge);
7382 /* Free up the INSN_LISTs */
7383 for (b = 0; b < max_reg; ++b)
7385 free_list (®_last_sets[b], &unused_insn_list);
7386 free_list (®_last_uses[b], &unused_insn_list);
7389 /* Assert that we won't need bb_reg_last_* for this block anymore. */
7390 if (current_nr_blocks > 1)
7392 bb_reg_last_uses[bb] = (rtx *) NULL_RTX;
7393 bb_reg_last_sets[bb] = (rtx *) NULL_RTX;
7397 /* Print dependences for debugging, callable from debugger */
7400 debug_dependencies ()
7404 fprintf (dump, ";; --------------- forward dependences: ------------ \n");
7405 for (bb = 0; bb < current_nr_blocks; bb++)
7413 get_block_head_tail (bb, &head, &tail);
7414 next_tail = NEXT_INSN (tail);
7415 fprintf (dump, "\n;; --- Region Dependences --- b %d bb %d \n",
7416 BB_TO_BLOCK (bb), bb);
7418 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7419 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7420 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7421 "----", "----", "--", "---", "----", "----", "--------", "-----");
7422 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
7427 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7430 fprintf (dump, ";; %6d ", INSN_UID (insn));
7431 if (GET_CODE (insn) == NOTE)
7433 n = NOTE_LINE_NUMBER (insn);
7435 fprintf (dump, "%s\n", GET_NOTE_INSN_NAME (n));
7437 fprintf (dump, "line %d, file %s\n", n,
7438 NOTE_SOURCE_FILE (insn));
7441 fprintf (dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
7445 unit = insn_unit (insn);
7447 || function_units[unit].blockage_range_function == 0) ? 0 :
7448 function_units[unit].blockage_range_function (insn);
7450 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7451 (SCHED_GROUP_P (insn) ? "+" : " "),
7455 INSN_DEP_COUNT (insn),
7456 INSN_PRIORITY (insn),
7457 insn_cost (insn, 0, 0),
7458 (int) MIN_BLOCKAGE_COST (range),
7459 (int) MAX_BLOCKAGE_COST (range));
7460 insn_print_units (insn);
7461 fprintf (dump, "\t: ");
7462 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
7463 fprintf (dump, "%d ", INSN_UID (XEXP (link, 0)));
7464 fprintf (dump, "\n");
7468 fprintf (dump, "\n");
7471 /* Set_priorities: compute priority of each insn in the block */
7484 get_block_head_tail (bb, &head, &tail);
7485 prev_head = PREV_INSN (head);
7488 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
7492 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
7495 if (GET_CODE (insn) == NOTE)
7498 if (!(SCHED_GROUP_P (insn)))
7500 (void) priority (insn);
7506 /* Make each element of VECTOR point at an rtx-vector,
7507 taking the space for all those rtx-vectors from SPACE.
7508 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7509 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7510 (this is the same as init_regset_vector () in flow.c) */
7513 init_rtx_vector (vector, space, nelts, bytes_per_elt)
7520 register rtx *p = space;
7522 for (i = 0; i < nelts; i++)
7525 p += bytes_per_elt / sizeof (*p);
7529 /* Schedule a region. A region is either an inner loop, a loop-free
7530 subroutine, or a single basic block. Each bb in the region is
7531 scheduled after its flow predecessors. */
7534 schedule_region (rgn)
7538 int rgn_n_insns = 0;
7539 int sched_rgn_n_insns = 0;
7541 /* set variables for the current region */
7542 current_nr_blocks = RGN_NR_BLOCKS (rgn);
7543 current_blocks = RGN_BLOCKS (rgn);
7545 reg_pending_sets = ALLOCA_REG_SET ();
7546 reg_pending_sets_all = 0;
7548 /* initializations for region data dependence analyisis */
7549 if (current_nr_blocks > 1)
7552 int maxreg = max_reg_num ();
7554 bb_reg_last_uses = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7555 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7556 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7557 init_rtx_vector (bb_reg_last_uses, space, current_nr_blocks, maxreg * sizeof (rtx *));
7559 bb_reg_last_sets = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7560 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7561 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7562 init_rtx_vector (bb_reg_last_sets, space, current_nr_blocks, maxreg * sizeof (rtx *));
7564 bb_pending_read_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7565 bb_pending_read_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7566 bb_pending_write_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7567 bb_pending_write_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7568 bb_pending_lists_length = (int *) alloca (current_nr_blocks * sizeof (int));
7569 bb_last_pending_memory_flush = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7570 bb_last_function_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7571 bb_sched_before_next_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7573 init_rgn_data_dependences (current_nr_blocks);
7576 /* compute LOG_LINKS */
7577 for (bb = 0; bb < current_nr_blocks; bb++)
7578 compute_block_backward_dependences (bb);
7580 /* compute INSN_DEPEND */
7581 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7582 compute_block_forward_dependences (bb);
7584 /* Delete line notes, compute live-regs at block end, and set priorities. */
7586 for (bb = 0; bb < current_nr_blocks; bb++)
7588 if (reload_completed == 0)
7589 find_pre_sched_live (bb);
7591 if (write_symbols != NO_DEBUG)
7593 save_line_notes (bb);
7597 rgn_n_insns += set_priorities (bb);
7600 /* compute interblock info: probabilities, split-edges, dominators, etc. */
7601 if (current_nr_blocks > 1)
7605 prob = (float *) alloca ((current_nr_blocks) * sizeof (float));
7607 bbset_size = current_nr_blocks / HOST_BITS_PER_WIDE_INT + 1;
7608 dom = (bbset *) alloca (current_nr_blocks * sizeof (bbset));
7609 for (i = 0; i < current_nr_blocks; i++)
7611 dom[i] = (bbset) alloca (bbset_size * sizeof (HOST_WIDE_INT));
7612 bzero ((char *) dom[i], bbset_size * sizeof (HOST_WIDE_INT));
7617 edge_to_bit = (int *) alloca (nr_edges * sizeof (int));
7618 for (i = 1; i < nr_edges; i++)
7619 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
7620 EDGE_TO_BIT (i) = rgn_nr_edges++;
7621 rgn_edges = (int *) alloca (rgn_nr_edges * sizeof (int));
7624 for (i = 1; i < nr_edges; i++)
7625 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
7626 rgn_edges[rgn_nr_edges++] = i;
7629 edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
7630 pot_split = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7631 ancestor_edges = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7632 for (i = 0; i < current_nr_blocks; i++)
7635 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7636 bzero ((char *) pot_split[i],
7637 edgeset_size * sizeof (HOST_WIDE_INT));
7639 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7640 bzero ((char *) ancestor_edges[i],
7641 edgeset_size * sizeof (HOST_WIDE_INT));
7644 /* compute probabilities, dominators, split_edges */
7645 for (bb = 0; bb < current_nr_blocks; bb++)
7646 compute_dom_prob_ps (bb);
7649 /* now we can schedule all blocks */
7650 for (bb = 0; bb < current_nr_blocks; bb++)
7652 sched_rgn_n_insns += schedule_block (bb, rgn_n_insns);
7659 #ifdef INTERBLOCK_DEBUG
7660 if (sched_debug_count != 0)
7662 /* sanity check: verify that all region insns were scheduled */
7663 if (sched_rgn_n_insns != rgn_n_insns)
7666 /* update register life and usage information */
7667 if (reload_completed == 0)
7669 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7670 find_post_sched_live (bb);
7672 if (current_nr_blocks <= 1)
7673 /* Sanity check. There should be no REG_DEAD notes leftover at the end.
7674 In practice, this can occur as the result of bugs in flow, combine.c,
7675 and/or sched.c. The values of the REG_DEAD notes remaining are
7676 meaningless, because dead_notes is just used as a free list. */
7677 if (dead_notes != 0)
7681 /* restore line notes. */
7682 if (write_symbols != NO_DEBUG)
7684 for (bb = 0; bb < current_nr_blocks; bb++)
7685 restore_line_notes (bb);
7688 /* Done with this region */
7689 free_pending_lists ();
7691 FREE_REG_SET (reg_pending_sets);
7694 /* Subroutine of split_hard_reg_notes. Searches X for any reference to
7695 REGNO, returning the rtx of the reference found if any. Otherwise,
7699 regno_use_in (regno, x)
7707 if (GET_CODE (x) == REG && REGNO (x) == regno)
7710 fmt = GET_RTX_FORMAT (GET_CODE (x));
7711 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
7715 if ((tem = regno_use_in (regno, XEXP (x, i))))
7718 else if (fmt[i] == 'E')
7719 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
7720 if ((tem = regno_use_in (regno, XVECEXP (x, i, j))))
7727 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
7728 needed for the hard register mentioned in the note. This can happen
7729 if the reference to the hard register in the original insn was split into
7730 several smaller hard register references in the split insns. */
7733 split_hard_reg_notes (note, first, last)
7734 rtx note, first, last;
7736 rtx reg, temp, link;
7737 int n_regs, i, new_reg;
7740 /* Assume that this is a REG_DEAD note. */
7741 if (REG_NOTE_KIND (note) != REG_DEAD)
7744 reg = XEXP (note, 0);
7746 n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
7748 for (i = 0; i < n_regs; i++)
7750 new_reg = REGNO (reg) + i;
7752 /* Check for references to new_reg in the split insns. */
7753 for (insn = last;; insn = PREV_INSN (insn))
7755 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7756 && (temp = regno_use_in (new_reg, PATTERN (insn))))
7758 /* Create a new reg dead note ere. */
7759 link = alloc_EXPR_LIST (REG_DEAD, temp, REG_NOTES (insn));
7760 REG_NOTES (insn) = link;
7762 /* If killed multiple registers here, then add in the excess. */
7763 i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
7767 /* It isn't mentioned anywhere, so no new reg note is needed for
7775 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
7776 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
7779 new_insn_dead_notes (pat, insn, last, orig_insn)
7780 rtx pat, insn, last, orig_insn;
7784 /* PAT is either a CLOBBER or a SET here. */
7785 dest = XEXP (pat, 0);
7787 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
7788 || GET_CODE (dest) == STRICT_LOW_PART
7789 || GET_CODE (dest) == SIGN_EXTRACT)
7790 dest = XEXP (dest, 0);
7792 if (GET_CODE (dest) == REG)
7794 for (tem = last; tem != insn; tem = PREV_INSN (tem))
7796 if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
7797 && reg_overlap_mentioned_p (dest, PATTERN (tem))
7798 && (set = single_set (tem)))
7800 rtx tem_dest = SET_DEST (set);
7802 while (GET_CODE (tem_dest) == ZERO_EXTRACT
7803 || GET_CODE (tem_dest) == SUBREG
7804 || GET_CODE (tem_dest) == STRICT_LOW_PART
7805 || GET_CODE (tem_dest) == SIGN_EXTRACT)
7806 tem_dest = XEXP (tem_dest, 0);
7808 if (!rtx_equal_p (tem_dest, dest))
7810 /* Use the same scheme as combine.c, don't put both REG_DEAD
7811 and REG_UNUSED notes on the same insn. */
7812 if (!find_regno_note (tem, REG_UNUSED, REGNO (dest))
7813 && !find_regno_note (tem, REG_DEAD, REGNO (dest)))
7815 rtx note = alloc_EXPR_LIST (REG_DEAD, dest,
7817 REG_NOTES (tem) = note;
7819 /* The reg only dies in one insn, the last one that uses
7823 else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
7824 /* We found an instruction that both uses the register,
7825 and sets it, so no new REG_NOTE is needed for this set. */
7829 /* If this is a set, it must die somewhere, unless it is the dest of
7830 the original insn, and hence is live after the original insn. Abort
7831 if it isn't supposed to be live after the original insn.
7833 If this is a clobber, then just add a REG_UNUSED note. */
7836 int live_after_orig_insn = 0;
7837 rtx pattern = PATTERN (orig_insn);
7840 if (GET_CODE (pat) == CLOBBER)
7842 rtx note = alloc_EXPR_LIST (REG_UNUSED, dest, REG_NOTES (insn));
7843 REG_NOTES (insn) = note;
7847 /* The original insn could have multiple sets, so search the
7848 insn for all sets. */
7849 if (GET_CODE (pattern) == SET)
7851 if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
7852 live_after_orig_insn = 1;
7854 else if (GET_CODE (pattern) == PARALLEL)
7856 for (i = 0; i < XVECLEN (pattern, 0); i++)
7857 if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
7858 && reg_overlap_mentioned_p (dest,
7859 SET_DEST (XVECEXP (pattern,
7861 live_after_orig_insn = 1;
7864 if (!live_after_orig_insn)
7870 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
7871 registers modified by X. INC is -1 if the containing insn is being deleted,
7872 and is 1 if the containing insn is a newly generated insn. */
7875 update_n_sets (x, inc)
7879 rtx dest = SET_DEST (x);
7881 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
7882 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
7883 dest = SUBREG_REG (dest);
7885 if (GET_CODE (dest) == REG)
7887 int regno = REGNO (dest);
7889 if (regno < FIRST_PSEUDO_REGISTER)
7892 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
7894 for (i = regno; i < endregno; i++)
7895 REG_N_SETS (i) += inc;
7898 REG_N_SETS (regno) += inc;
7902 /* Updates all flow-analysis related quantities (including REG_NOTES) for
7903 the insns from FIRST to LAST inclusive that were created by splitting
7904 ORIG_INSN. NOTES are the original REG_NOTES. */
7907 update_flow_info (notes, first, last, orig_insn)
7914 rtx orig_dest, temp;
7917 /* Get and save the destination set by the original insn. */
7919 orig_dest = single_set (orig_insn);
7921 orig_dest = SET_DEST (orig_dest);
7923 /* Move REG_NOTES from the original insn to where they now belong. */
7925 for (note = notes; note; note = next)
7927 next = XEXP (note, 1);
7928 switch (REG_NOTE_KIND (note))
7932 /* Move these notes from the original insn to the last new insn where
7933 the register is now set. */
7935 for (insn = last;; insn = PREV_INSN (insn))
7937 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7938 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
7940 /* If this note refers to a multiple word hard register, it
7941 may have been split into several smaller hard register
7942 references, so handle it specially. */
7943 temp = XEXP (note, 0);
7944 if (REG_NOTE_KIND (note) == REG_DEAD
7945 && GET_CODE (temp) == REG
7946 && REGNO (temp) < FIRST_PSEUDO_REGISTER
7947 && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
7948 split_hard_reg_notes (note, first, last);
7951 XEXP (note, 1) = REG_NOTES (insn);
7952 REG_NOTES (insn) = note;
7955 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
7957 /* ??? This won't handle multiple word registers correctly,
7958 but should be good enough for now. */
7959 if (REG_NOTE_KIND (note) == REG_UNUSED
7960 && GET_CODE (XEXP (note, 0)) != SCRATCH
7961 && !dead_or_set_p (insn, XEXP (note, 0)))
7962 PUT_REG_NOTE_KIND (note, REG_DEAD);
7964 /* The reg only dies in one insn, the last one that uses
7968 /* It must die somewhere, fail it we couldn't find where it died.
7970 If this is a REG_UNUSED note, then it must be a temporary
7971 register that was not needed by this instantiation of the
7972 pattern, so we can safely ignore it. */
7975 /* After reload, REG_DEAD notes come sometimes an
7976 instruction after the register actually dies. */
7977 if (reload_completed && REG_NOTE_KIND (note) == REG_DEAD)
7979 XEXP (note, 1) = REG_NOTES (insn);
7980 REG_NOTES (insn) = note;
7984 if (REG_NOTE_KIND (note) != REG_UNUSED)
7993 /* If the insn that set the register to 0 was deleted, this
7994 note cannot be relied on any longer. The destination might
7995 even have been moved to memory.
7996 This was observed for SH4 with execute/920501-6.c compilation,
7997 -O2 -fomit-frame-pointer -finline-functions . */
7998 if (GET_CODE (XEXP (note, 0)) == NOTE
7999 || INSN_DELETED_P (XEXP (note, 0)))
8001 /* This note applies to the dest of the original insn. Find the
8002 first new insn that now has the same dest, and move the note
8008 for (insn = first;; insn = NEXT_INSN (insn))
8010 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8011 && (temp = single_set (insn))
8012 && rtx_equal_p (SET_DEST (temp), orig_dest))
8014 XEXP (note, 1) = REG_NOTES (insn);
8015 REG_NOTES (insn) = note;
8016 /* The reg is only zero before one insn, the first that
8020 /* If this note refers to a multiple word hard
8021 register, it may have been split into several smaller
8022 hard register references. We could split the notes,
8023 but simply dropping them is good enough. */
8024 if (GET_CODE (orig_dest) == REG
8025 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
8026 && HARD_REGNO_NREGS (REGNO (orig_dest),
8027 GET_MODE (orig_dest)) > 1)
8029 /* It must be set somewhere, fail if we couldn't find where it
8038 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
8039 set is meaningless. Just drop the note. */
8043 case REG_NO_CONFLICT:
8044 /* These notes apply to the dest of the original insn. Find the last
8045 new insn that now has the same dest, and move the note there. */
8050 for (insn = last;; insn = PREV_INSN (insn))
8052 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8053 && (temp = single_set (insn))
8054 && rtx_equal_p (SET_DEST (temp), orig_dest))
8056 XEXP (note, 1) = REG_NOTES (insn);
8057 REG_NOTES (insn) = note;
8058 /* Only put this note on one of the new insns. */
8062 /* The original dest must still be set someplace. Abort if we
8063 couldn't find it. */
8066 /* However, if this note refers to a multiple word hard
8067 register, it may have been split into several smaller
8068 hard register references. We could split the notes,
8069 but simply dropping them is good enough. */
8070 if (GET_CODE (orig_dest) == REG
8071 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
8072 && HARD_REGNO_NREGS (REGNO (orig_dest),
8073 GET_MODE (orig_dest)) > 1)
8075 /* Likewise for multi-word memory references. */
8076 if (GET_CODE (orig_dest) == MEM
8077 && SIZE_FOR_MODE (orig_dest) > MOVE_MAX)
8085 /* Move a REG_LIBCALL note to the first insn created, and update
8086 the corresponding REG_RETVAL note. */
8087 XEXP (note, 1) = REG_NOTES (first);
8088 REG_NOTES (first) = note;
8090 insn = XEXP (note, 0);
8091 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
8093 XEXP (note, 0) = first;
8096 case REG_EXEC_COUNT:
8097 /* Move a REG_EXEC_COUNT note to the first insn created. */
8098 XEXP (note, 1) = REG_NOTES (first);
8099 REG_NOTES (first) = note;
8103 /* Move a REG_RETVAL note to the last insn created, and update
8104 the corresponding REG_LIBCALL note. */
8105 XEXP (note, 1) = REG_NOTES (last);
8106 REG_NOTES (last) = note;
8108 insn = XEXP (note, 0);
8109 note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
8111 XEXP (note, 0) = last;
8116 /* This should be moved to whichever instruction is a JUMP_INSN. */
8118 for (insn = last;; insn = PREV_INSN (insn))
8120 if (GET_CODE (insn) == JUMP_INSN)
8122 XEXP (note, 1) = REG_NOTES (insn);
8123 REG_NOTES (insn) = note;
8124 /* Only put this note on one of the new insns. */
8127 /* Fail if we couldn't find a JUMP_INSN. */
8134 /* reload sometimes leaves obsolete REG_INC notes around. */
8135 if (reload_completed)
8137 /* This should be moved to whichever instruction now has the
8138 increment operation. */
8142 /* Should be moved to the new insn(s) which use the label. */
8143 for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
8144 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8145 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
8147 REG_NOTES (insn) = alloc_EXPR_LIST (REG_LABEL,
8155 /* These two notes will never appear until after reorg, so we don't
8156 have to handle them here. */
8162 /* Each new insn created, except the last, has a new set. If the destination
8163 is a register, then this reg is now live across several insns, whereas
8164 previously the dest reg was born and died within the same insn. To
8165 reflect this, we now need a REG_DEAD note on the insn where this
8168 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
8170 for (insn = first; insn != last; insn = NEXT_INSN (insn))
8175 pat = PATTERN (insn);
8176 if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
8177 new_insn_dead_notes (pat, insn, last, orig_insn);
8178 else if (GET_CODE (pat) == PARALLEL)
8180 for (i = 0; i < XVECLEN (pat, 0); i++)
8181 if (GET_CODE (XVECEXP (pat, 0, i)) == SET
8182 || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
8183 new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
8187 /* If any insn, except the last, uses the register set by the last insn,
8188 then we need a new REG_DEAD note on that insn. In this case, there
8189 would not have been a REG_DEAD note for this register in the original
8190 insn because it was used and set within one insn. */
8192 set = single_set (last);
8195 rtx dest = SET_DEST (set);
8197 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
8198 || GET_CODE (dest) == STRICT_LOW_PART
8199 || GET_CODE (dest) == SIGN_EXTRACT)
8200 dest = XEXP (dest, 0);
8202 if (GET_CODE (dest) == REG
8203 /* Global registers are always live, so the code below does not
8205 && (REGNO (dest) >= FIRST_PSEUDO_REGISTER
8206 || ! global_regs[REGNO (dest)]))
8208 rtx stop_insn = PREV_INSN (first);
8210 /* If the last insn uses the register that it is setting, then
8211 we don't want to put a REG_DEAD note there. Search backwards
8212 to find the first insn that sets but does not use DEST. */
8215 if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
8217 for (insn = PREV_INSN (insn); insn != first;
8218 insn = PREV_INSN (insn))
8220 if ((set = single_set (insn))
8221 && reg_mentioned_p (dest, SET_DEST (set))
8222 && ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
8227 /* Now find the first insn that uses but does not set DEST. */
8229 for (insn = PREV_INSN (insn); insn != stop_insn;
8230 insn = PREV_INSN (insn))
8232 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8233 && reg_mentioned_p (dest, PATTERN (insn))
8234 && (set = single_set (insn)))
8236 rtx insn_dest = SET_DEST (set);
8238 while (GET_CODE (insn_dest) == ZERO_EXTRACT
8239 || GET_CODE (insn_dest) == SUBREG
8240 || GET_CODE (insn_dest) == STRICT_LOW_PART
8241 || GET_CODE (insn_dest) == SIGN_EXTRACT)
8242 insn_dest = XEXP (insn_dest, 0);
8244 if (insn_dest != dest)
8246 note = alloc_EXPR_LIST (REG_DEAD, dest, REG_NOTES (insn));
8247 REG_NOTES (insn) = note;
8248 /* The reg only dies in one insn, the last one
8257 /* If the original dest is modifying a multiple register target, and the
8258 original instruction was split such that the original dest is now set
8259 by two or more SUBREG sets, then the split insns no longer kill the
8260 destination of the original insn.
8262 In this case, if there exists an instruction in the same basic block,
8263 before the split insn, which uses the original dest, and this use is
8264 killed by the original insn, then we must remove the REG_DEAD note on
8265 this insn, because it is now superfluous.
8267 This does not apply when a hard register gets split, because the code
8268 knows how to handle overlapping hard registers properly. */
8269 if (orig_dest && GET_CODE (orig_dest) == REG)
8271 int found_orig_dest = 0;
8272 int found_split_dest = 0;
8274 for (insn = first;; insn = NEXT_INSN (insn))
8279 /* I'm not sure if this can happen, but let's be safe. */
8280 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
8283 pat = PATTERN (insn);
8284 i = GET_CODE (pat) == PARALLEL ? XVECLEN (pat, 0) : 0;
8289 if (GET_CODE (set) == SET)
8291 if (GET_CODE (SET_DEST (set)) == REG
8292 && REGNO (SET_DEST (set)) == REGNO (orig_dest))
8294 found_orig_dest = 1;
8297 else if (GET_CODE (SET_DEST (set)) == SUBREG
8298 && SUBREG_REG (SET_DEST (set)) == orig_dest)
8300 found_split_dest = 1;
8306 set = XVECEXP (pat, 0, i);
8313 if (found_split_dest)
8315 /* Search backwards from FIRST, looking for the first insn that uses
8316 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
8317 If we find an insn, and it has a REG_DEAD note, then delete the
8320 for (insn = first; insn; insn = PREV_INSN (insn))
8322 if (GET_CODE (insn) == CODE_LABEL
8323 || GET_CODE (insn) == JUMP_INSN)
8325 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8326 && reg_mentioned_p (orig_dest, insn))
8328 note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
8330 remove_note (insn, note);
8334 else if (!found_orig_dest)
8336 /* This should never happen. */
8341 /* Update reg_n_sets. This is necessary to prevent local alloc from
8342 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
8343 a reg from set once to set multiple times. */
8346 rtx x = PATTERN (orig_insn);
8347 RTX_CODE code = GET_CODE (x);
8349 if (code == SET || code == CLOBBER)
8350 update_n_sets (x, -1);
8351 else if (code == PARALLEL)
8354 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8356 code = GET_CODE (XVECEXP (x, 0, i));
8357 if (code == SET || code == CLOBBER)
8358 update_n_sets (XVECEXP (x, 0, i), -1);
8362 for (insn = first;; insn = NEXT_INSN (insn))
8365 code = GET_CODE (x);
8367 if (code == SET || code == CLOBBER)
8368 update_n_sets (x, 1);
8369 else if (code == PARALLEL)
8372 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8374 code = GET_CODE (XVECEXP (x, 0, i));
8375 if (code == SET || code == CLOBBER)
8376 update_n_sets (XVECEXP (x, 0, i), 1);
8386 /* Do the splitting of insns in the block b. */
8389 split_block_insns (b)
8394 for (insn = basic_block_head[b];; insn = next)
8399 /* Can't use `next_real_insn' because that
8400 might go across CODE_LABELS and short-out basic blocks. */
8401 next = NEXT_INSN (insn);
8402 if (GET_CODE (insn) != INSN)
8404 if (insn == basic_block_end[b])
8410 /* Don't split no-op move insns. These should silently disappear
8411 later in final. Splitting such insns would break the code
8412 that handles REG_NO_CONFLICT blocks. */
8413 set = single_set (insn);
8414 if (set && rtx_equal_p (SET_SRC (set), SET_DEST (set)))
8416 if (insn == basic_block_end[b])
8419 /* Nops get in the way while scheduling, so delete them now if
8420 register allocation has already been done. It is too risky
8421 to try to do this before register allocation, and there are
8422 unlikely to be very many nops then anyways. */
8423 if (reload_completed)
8425 PUT_CODE (insn, NOTE);
8426 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
8427 NOTE_SOURCE_FILE (insn) = 0;
8433 /* Split insns here to get max fine-grain parallelism. */
8434 prev = PREV_INSN (insn);
8435 /* It is probably not worthwhile to try to split again in
8436 the second pass. However, if flag_schedule_insns is not set,
8437 the first and only (if any) scheduling pass is after reload. */
8438 if (reload_completed == 0 || ! flag_schedule_insns)
8440 rtx last, first = PREV_INSN (insn);
8441 rtx notes = REG_NOTES (insn);
8442 last = try_split (PATTERN (insn), insn, 1);
8445 /* try_split returns the NOTE that INSN became. */
8446 first = NEXT_INSN (first);
8447 update_flow_info (notes, first, last, insn);
8449 PUT_CODE (insn, NOTE);
8450 NOTE_SOURCE_FILE (insn) = 0;
8451 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
8452 if (insn == basic_block_head[b])
8453 basic_block_head[b] = first;
8454 if (insn == basic_block_end[b])
8456 basic_block_end[b] = last;
8462 if (insn == basic_block_end[b])
8467 /* The one entry point in this file. DUMP_FILE is the dump file for
8471 schedule_insns (dump_file)
8482 /* disable speculative loads in their presence if cc0 defined */
8484 flag_schedule_speculative_load = 0;
8487 /* Taking care of this degenerate case makes the rest of
8488 this code simpler. */
8489 if (n_basic_blocks == 0)
8492 /* set dump and sched_verbose for the desired debugging output. If no
8493 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
8494 For -fsched-verbose-N, N>=10, print everything to stderr. */
8495 sched_verbose = sched_verbose_param;
8496 if (sched_verbose_param == 0 && dump_file)
8498 dump = ((sched_verbose_param >= 10 || !dump_file) ? stderr : dump_file);
8503 /* Initialize the unused_*_lists. We can't use the ones left over from
8504 the previous function, because gcc has freed that memory. We can use
8505 the ones left over from the first sched pass in the second pass however,
8506 so only clear them on the first sched pass. The first pass is before
8507 reload if flag_schedule_insns is set, otherwise it is afterwards. */
8509 if (reload_completed == 0 || !flag_schedule_insns)
8511 unused_insn_list = 0;
8512 unused_expr_list = 0;
8515 /* initialize issue_rate */
8516 issue_rate = ISSUE_RATE;
8518 /* do the splitting first for all blocks */
8519 for (b = 0; b < n_basic_blocks; b++)
8520 split_block_insns (b);
8522 max_uid = (get_max_uid () + 1);
8524 cant_move = (char *) alloca (max_uid * sizeof (char));
8525 bzero ((char *) cant_move, max_uid * sizeof (char));
8527 fed_by_spec_load = (char *) alloca (max_uid * sizeof (char));
8528 bzero ((char *) fed_by_spec_load, max_uid * sizeof (char));
8530 is_load_insn = (char *) alloca (max_uid * sizeof (char));
8531 bzero ((char *) is_load_insn, max_uid * sizeof (char));
8533 insn_orig_block = (int *) alloca (max_uid * sizeof (int));
8534 insn_luid = (int *) alloca (max_uid * sizeof (int));
8537 for (b = 0; b < n_basic_blocks; b++)
8538 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
8540 INSN_BLOCK (insn) = b;
8541 INSN_LUID (insn) = luid++;
8543 if (insn == basic_block_end[b])
8547 /* after reload, remove inter-blocks dependences computed before reload. */
8548 if (reload_completed)
8553 for (b = 0; b < n_basic_blocks; b++)
8554 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
8558 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
8561 link = LOG_LINKS (insn);
8564 rtx x = XEXP (link, 0);
8566 if (INSN_BLOCK (x) != b)
8568 remove_dependence (insn, x);
8569 link = prev ? XEXP (prev, 1) : LOG_LINKS (insn);
8572 prev = link, link = XEXP (prev, 1);
8576 if (insn == basic_block_end[b])
8582 rgn_table = (region *) alloca ((n_basic_blocks) * sizeof (region));
8583 rgn_bb_table = (int *) alloca ((n_basic_blocks) * sizeof (int));
8584 block_to_bb = (int *) alloca ((n_basic_blocks) * sizeof (int));
8585 containing_rgn = (int *) alloca ((n_basic_blocks) * sizeof (int));
8587 /* compute regions for scheduling */
8588 if (reload_completed
8589 || n_basic_blocks == 1
8590 || !flag_schedule_interblock)
8592 find_single_block_region ();
8596 /* an estimation for nr_edges is computed in is_cfg_nonregular () */
8599 /* verify that a 'good' control flow graph can be built */
8600 if (is_cfg_nonregular ()
8603 find_single_block_region ();
8607 /* build control flow graph */
8608 in_edges = (int *) alloca (n_basic_blocks * sizeof (int));
8609 out_edges = (int *) alloca (n_basic_blocks * sizeof (int));
8610 bzero ((char *) in_edges, n_basic_blocks * sizeof (int));
8611 bzero ((char *) out_edges, n_basic_blocks * sizeof (int));
8614 (edge *) alloca ((nr_edges) * sizeof (edge));
8615 bzero ((char *) edge_table,
8616 ((nr_edges) * sizeof (edge)));
8617 build_control_flow ();
8619 /* identify reducible inner loops and compute regions */
8622 if (sched_verbose >= 3)
8624 debug_control_flow ();
8631 /* Allocate data for this pass. See comments, above,
8632 for what these vectors do. */
8633 insn_priority = (int *) alloca (max_uid * sizeof (int));
8634 insn_reg_weight = (int *) alloca (max_uid * sizeof (int));
8635 insn_tick = (int *) alloca (max_uid * sizeof (int));
8636 insn_costs = (short *) alloca (max_uid * sizeof (short));
8637 insn_units = (short *) alloca (max_uid * sizeof (short));
8638 insn_blockage = (unsigned int *) alloca (max_uid * sizeof (unsigned int));
8639 insn_ref_count = (int *) alloca (max_uid * sizeof (int));
8641 /* Allocate for forward dependencies */
8642 insn_dep_count = (int *) alloca (max_uid * sizeof (int));
8643 insn_depend = (rtx *) alloca (max_uid * sizeof (rtx));
8645 if (reload_completed == 0)
8649 sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
8650 sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
8651 sched_reg_basic_block = (int *) alloca (max_regno * sizeof (int));
8652 bb_live_regs = ALLOCA_REG_SET ();
8653 bzero ((char *) sched_reg_n_calls_crossed, max_regno * sizeof (int));
8654 bzero ((char *) sched_reg_live_length, max_regno * sizeof (int));
8656 for (i = 0; i < max_regno; i++)
8657 sched_reg_basic_block[i] = REG_BLOCK_UNKNOWN;
8661 sched_reg_n_calls_crossed = 0;
8662 sched_reg_live_length = 0;
8665 init_alias_analysis ();
8667 if (write_symbols != NO_DEBUG)
8671 line_note = (rtx *) alloca (max_uid * sizeof (rtx));
8672 bzero ((char *) line_note, max_uid * sizeof (rtx));
8673 line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
8674 bzero ((char *) line_note_head, n_basic_blocks * sizeof (rtx));
8676 /* Save-line-note-head:
8677 Determine the line-number at the start of each basic block.
8678 This must be computed and saved now, because after a basic block's
8679 predecessor has been scheduled, it is impossible to accurately
8680 determine the correct line number for the first insn of the block. */
8682 for (b = 0; b < n_basic_blocks; b++)
8683 for (line = basic_block_head[b]; line; line = PREV_INSN (line))
8684 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
8686 line_note_head[b] = line;
8691 bzero ((char *) insn_priority, max_uid * sizeof (int));
8692 bzero ((char *) insn_reg_weight, max_uid * sizeof (int));
8693 bzero ((char *) insn_tick, max_uid * sizeof (int));
8694 bzero ((char *) insn_costs, max_uid * sizeof (short));
8695 bzero ((char *) insn_units, max_uid * sizeof (short));
8696 bzero ((char *) insn_blockage, max_uid * sizeof (unsigned int));
8697 bzero ((char *) insn_ref_count, max_uid * sizeof (int));
8699 /* Initialize for forward dependencies */
8700 bzero ((char *) insn_depend, max_uid * sizeof (rtx));
8701 bzero ((char *) insn_dep_count, max_uid * sizeof (int));
8703 /* Find units used in this fuction, for visualization */
8705 init_target_units ();
8707 /* ??? Add a NOTE after the last insn of the last basic block. It is not
8708 known why this is done. */
8710 insn = basic_block_end[n_basic_blocks - 1];
8711 if (NEXT_INSN (insn) == 0
8712 || (GET_CODE (insn) != NOTE
8713 && GET_CODE (insn) != CODE_LABEL
8714 /* Don't emit a NOTE if it would end up between an unconditional
8715 jump and a BARRIER. */
8716 && !(GET_CODE (insn) == JUMP_INSN
8717 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
8718 emit_note_after (NOTE_INSN_DELETED, basic_block_end[n_basic_blocks - 1]);
8720 /* Schedule every region in the subroutine */
8721 fprintf(stderr, "HELLO: nr_regions=%d max_reg_num=%d\n",
8722 (int)nr_regions, (int)max_reg_num());
8723 for (rgn = 0; rgn < nr_regions; rgn++)
8725 schedule_region (rgn);
8732 /* Reposition the prologue and epilogue notes in case we moved the
8733 prologue/epilogue insns. */
8734 if (reload_completed)
8735 reposition_prologue_and_epilogue_notes (get_insns ());
8737 /* delete redundant line notes. */
8738 if (write_symbols != NO_DEBUG)
8739 rm_redundant_line_notes ();
8741 /* Update information about uses of registers in the subroutine. */
8742 if (reload_completed == 0)
8743 update_reg_usage ();
8747 if (reload_completed == 0 && flag_schedule_interblock)
8749 fprintf (dump, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8757 fprintf (dump, "\n\n");
8761 FREE_REG_SET (bb_live_regs);
8763 #endif /* INSN_SCHEDULING */