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 ((const GENERIC_PTR, const GENERIC_PTR));
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 int is_cfg_nonregular PROTO ((void));
521 void debug_control_flow PROTO ((void));
522 static int build_control_flow PROTO ((void));
523 static void new_edge PROTO ((int, int));
526 /* A region is the main entity for interblock scheduling: insns
527 are allowed to move between blocks in the same region, along
528 control flow graph edges, in the 'up' direction. */
531 int rgn_nr_blocks; /* number of blocks in region */
532 int rgn_blocks; /* blocks in the region (actually index in rgn_bb_table) */
536 /* Number of regions in the procedure */
537 static int nr_regions;
539 /* Table of region descriptions */
540 static region *rgn_table;
542 /* Array of lists of regions' blocks */
543 static int *rgn_bb_table;
545 /* Topological order of blocks in the region (if b2 is reachable from
546 b1, block_to_bb[b2] > block_to_bb[b1]).
547 Note: A basic block is always referred to by either block or b,
548 while its topological order name (in the region) is refered to by
551 static int *block_to_bb;
553 /* The number of the region containing a block. */
554 static int *containing_rgn;
556 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
557 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
558 #define BLOCK_TO_BB(block) (block_to_bb[block])
559 #define CONTAINING_RGN(block) (containing_rgn[block])
561 void debug_regions PROTO ((void));
562 static void find_single_block_region PROTO ((void));
563 static void find_rgns PROTO ((void));
564 static int too_large PROTO ((int, int *, int *));
566 extern void debug_live PROTO ((int, int));
568 /* Blocks of the current region being scheduled. */
569 static int current_nr_blocks;
570 static int current_blocks;
572 /* The mapping from bb to block */
573 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
576 /* Bit vectors and bitset operations are needed for computations on
577 the control flow graph. */
579 typedef unsigned HOST_WIDE_INT *bitset;
582 int *first_member; /* pointer to the list start in bitlst_table. */
583 int nr_members; /* the number of members of the bit list. */
587 static int bitlst_table_last;
588 static int bitlst_table_size;
589 static int *bitlst_table;
591 static char bitset_member PROTO ((bitset, int, int));
592 static void extract_bitlst PROTO ((bitset, int, bitlst *));
594 /* target info declarations.
596 The block currently being scheduled is referred to as the "target" block,
597 while other blocks in the region from which insns can be moved to the
598 target are called "source" blocks. The candidate structure holds info
599 about such sources: are they valid? Speculative? Etc. */
600 typedef bitlst bblst;
611 static candidate *candidate_table;
613 /* A speculative motion requires checking live information on the path
614 from 'source' to 'target'. The split blocks are those to be checked.
615 After a speculative motion, live information should be modified in
618 Lists of split and update blocks for each candidate of the current
619 target are in array bblst_table */
620 static int *bblst_table, bblst_size, bblst_last;
622 #define IS_VALID(src) ( candidate_table[src].is_valid )
623 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
624 #define SRC_PROB(src) ( candidate_table[src].src_prob )
626 /* The bb being currently scheduled. */
627 static int target_bb;
630 typedef bitlst edgelst;
632 /* target info functions */
633 static void split_edges PROTO ((int, int, edgelst *));
634 static void compute_trg_info PROTO ((int));
635 void debug_candidate PROTO ((int));
636 void debug_candidates PROTO ((int));
639 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
640 typedef bitset bbset;
642 /* Number of words of the bbset. */
643 static int bbset_size;
645 /* Dominators array: dom[i] contains the bbset of dominators of
646 bb i in the region. */
649 /* bb 0 is the only region entry */
650 #define IS_RGN_ENTRY(bb) (!bb)
652 /* Is bb_src dominated by bb_trg. */
653 #define IS_DOMINATED(bb_src, bb_trg) \
654 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
656 /* Probability: Prob[i] is a float in [0, 1] which is the probability
657 of bb i relative to the region entry. */
660 /* The probability of bb_src, relative to bb_trg. Note, that while the
661 'prob[bb]' is a float in [0, 1], this macro returns an integer
663 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
666 /* Bit-set of edges, where bit i stands for edge i. */
667 typedef bitset edgeset;
669 /* Number of edges in the region. */
670 static int rgn_nr_edges;
672 /* Array of size rgn_nr_edges. */
673 static int *rgn_edges;
675 /* Number of words in an edgeset. */
676 static int edgeset_size;
678 /* Mapping from each edge in the graph to its number in the rgn. */
679 static int *edge_to_bit;
680 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
682 /* The split edges of a source bb is different for each target
683 bb. In order to compute this efficiently, the 'potential-split edges'
684 are computed for each bb prior to scheduling a region. This is actually
685 the split edges of each bb relative to the region entry.
687 pot_split[bb] is the set of potential split edges of bb. */
688 static edgeset *pot_split;
690 /* For every bb, a set of its ancestor edges. */
691 static edgeset *ancestor_edges;
693 static void compute_dom_prob_ps PROTO ((int));
695 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
696 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
697 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
698 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
700 /* parameters affecting the decision of rank_for_schedule() */
701 #define MIN_DIFF_PRIORITY 2
702 #define MIN_PROBABILITY 40
703 #define MIN_PROB_DIFF 10
705 /* speculative scheduling functions */
706 static int check_live_1 PROTO ((int, rtx));
707 static void update_live_1 PROTO ((int, rtx));
708 static int check_live PROTO ((rtx, int));
709 static void update_live PROTO ((rtx, int));
710 static void set_spec_fed PROTO ((rtx));
711 static int is_pfree PROTO ((rtx, int, int));
712 static int find_conditional_protection PROTO ((rtx, int));
713 static int is_conditionally_protected PROTO ((rtx, int, int));
714 static int may_trap_exp PROTO ((rtx, int));
715 static int haifa_classify_insn PROTO ((rtx));
716 static int is_exception_free PROTO ((rtx, int, int));
718 static char find_insn_mem_list PROTO ((rtx, rtx, rtx, rtx));
719 static void compute_block_forward_dependences PROTO ((int));
720 static void init_rgn_data_dependences PROTO ((int));
721 static void add_branch_dependences PROTO ((rtx, rtx));
722 static void compute_block_backward_dependences PROTO ((int));
723 void debug_dependencies PROTO ((void));
725 /* Notes handling mechanism:
726 =========================
727 Generally, NOTES are saved before scheduling and restored after scheduling.
728 The scheduler distinguishes between three types of notes:
730 (1) LINE_NUMBER notes, generated and used for debugging. Here,
731 before scheduling a region, a pointer to the LINE_NUMBER note is
732 added to the insn following it (in save_line_notes()), and the note
733 is removed (in rm_line_notes() and unlink_line_notes()). After
734 scheduling the region, this pointer is used for regeneration of
735 the LINE_NUMBER note (in restore_line_notes()).
737 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
738 Before scheduling a region, a pointer to the note is added to the insn
739 that follows or precedes it. (This happens as part of the data dependence
740 computation). After scheduling an insn, the pointer contained in it is
741 used for regenerating the corresponding note (in reemit_notes).
743 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
744 these notes are put in a list (in rm_other_notes() and
745 unlink_other_notes ()). After scheduling the block, these notes are
746 inserted at the beginning of the block (in schedule_block()). */
748 static rtx unlink_other_notes PROTO ((rtx, rtx));
749 static rtx unlink_line_notes PROTO ((rtx, rtx));
750 static void rm_line_notes PROTO ((int));
751 static void save_line_notes PROTO ((int));
752 static void restore_line_notes PROTO ((int));
753 static void rm_redundant_line_notes PROTO ((void));
754 static void rm_other_notes PROTO ((rtx, rtx));
755 static rtx reemit_notes PROTO ((rtx, rtx));
757 static void get_block_head_tail PROTO ((int, rtx *, rtx *));
759 static void find_pre_sched_live PROTO ((int));
760 static void find_post_sched_live PROTO ((int));
761 static void update_reg_usage PROTO ((void));
763 void debug_ready_list PROTO ((rtx[], int));
764 static void init_target_units PROTO (());
765 static void insn_print_units PROTO ((rtx));
766 static int get_visual_tbl_length PROTO (());
767 static void init_block_visualization PROTO (());
768 static void print_block_visualization PROTO ((int, char *));
769 static void visualize_scheduled_insns PROTO ((int, int));
770 static void visualize_no_unit PROTO ((rtx));
771 static void visualize_stall_cycles PROTO ((int, int));
772 static void print_exp PROTO ((char *, rtx, int));
773 static void print_value PROTO ((char *, rtx, int));
774 static void print_pattern PROTO ((char *, rtx, int));
775 static void print_insn PROTO ((char *, rtx, int));
776 void debug_reg_vector PROTO ((regset));
778 static rtx move_insn1 PROTO ((rtx, rtx));
779 static rtx move_insn PROTO ((rtx, rtx));
780 static rtx group_leader PROTO ((rtx));
781 static int set_priorities PROTO ((int));
782 static void init_rtx_vector PROTO ((rtx **, rtx *, int, int));
783 static void schedule_region PROTO ((int));
784 static void split_block_insns PROTO ((int));
786 #endif /* INSN_SCHEDULING */
788 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
790 /* Helper functions for instruction scheduling. */
792 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
793 static rtx unused_insn_list;
795 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
796 static rtx unused_expr_list;
798 static void free_list PROTO ((rtx *, rtx *));
799 static rtx alloc_INSN_LIST PROTO ((rtx, rtx));
800 static rtx alloc_EXPR_LIST PROTO ((int, rtx, rtx));
803 free_list (listp, unused_listp)
804 rtx *listp, *unused_listp;
806 register rtx link, prev_link;
812 link = XEXP (prev_link, 1);
817 link = XEXP (link, 1);
820 XEXP (prev_link, 1) = *unused_listp;
821 *unused_listp = *listp;
826 alloc_INSN_LIST (val, next)
831 if (unused_insn_list)
833 r = unused_insn_list;
834 unused_insn_list = XEXP (r, 1);
837 PUT_REG_NOTE_KIND (r, VOIDmode);
840 r = gen_rtx_INSN_LIST (VOIDmode, val, next);
846 alloc_EXPR_LIST (kind, val, next)
852 if (unused_insn_list)
854 r = unused_insn_list;
855 unused_insn_list = XEXP (r, 1);
858 PUT_REG_NOTE_KIND (r, kind);
861 r = gen_rtx_EXPR_LIST (kind, val, next);
866 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
867 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
868 of dependence that this link represents. */
871 add_dependence (insn, elem, dep_type)
874 enum reg_note dep_type;
878 /* Don't depend an insn on itself. */
882 /* If elem is part of a sequence that must be scheduled together, then
883 make the dependence point to the last insn of the sequence.
884 When HAVE_cc0, it is possible for NOTEs to exist between users and
885 setters of the condition codes, so we must skip past notes here.
886 Otherwise, NOTEs are impossible here. */
888 next = NEXT_INSN (elem);
891 while (next && GET_CODE (next) == NOTE)
892 next = NEXT_INSN (next);
895 if (next && SCHED_GROUP_P (next)
896 && GET_CODE (next) != CODE_LABEL)
898 /* Notes will never intervene here though, so don't bother checking
900 /* We must reject CODE_LABELs, so that we don't get confused by one
901 that has LABEL_PRESERVE_P set, which is represented by the same
902 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
904 while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
905 && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
906 next = NEXT_INSN (next);
908 /* Again, don't depend an insn on itself. */
912 /* Make the dependence to NEXT, the last insn of the group, instead
913 of the original ELEM. */
917 #ifdef INSN_SCHEDULING
918 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
919 No need for interblock dependences with calls, since
920 calls are not moved between blocks. Note: the edge where
921 elem is a CALL is still required. */
922 if (GET_CODE (insn) == CALL_INSN
923 && (INSN_BB (elem) != INSN_BB (insn)))
928 /* Check that we don't already have this dependence. */
929 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
930 if (XEXP (link, 0) == elem)
932 /* If this is a more restrictive type of dependence than the existing
933 one, then change the existing dependence to this type. */
934 if ((int) dep_type < (int) REG_NOTE_KIND (link))
935 PUT_REG_NOTE_KIND (link, dep_type);
938 /* Might want to check one level of transitivity to save conses. */
940 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
941 LOG_LINKS (insn) = link;
943 /* Insn dependency, not data dependency. */
944 PUT_REG_NOTE_KIND (link, dep_type);
947 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
948 of INSN. Abort if not found. */
951 remove_dependence (insn, elem)
955 rtx prev, link, next;
958 for (prev = 0, link = LOG_LINKS (insn); link; link = next)
960 next = XEXP (link, 1);
961 if (XEXP (link, 0) == elem)
964 XEXP (prev, 1) = next;
966 LOG_LINKS (insn) = next;
968 XEXP (link, 1) = unused_insn_list;
969 unused_insn_list = link;
982 #ifndef INSN_SCHEDULING
984 schedule_insns (dump_file)
993 /* Computation of memory dependencies. */
995 /* The *_insns and *_mems are paired lists. Each pending memory operation
996 will have a pointer to the MEM rtx on one list and a pointer to the
997 containing insn on the other list in the same place in the list. */
999 /* We can't use add_dependence like the old code did, because a single insn
1000 may have multiple memory accesses, and hence needs to be on the list
1001 once for each memory access. Add_dependence won't let you add an insn
1002 to a list more than once. */
1004 /* An INSN_LIST containing all insns with pending read operations. */
1005 static rtx pending_read_insns;
1007 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
1008 static rtx pending_read_mems;
1010 /* An INSN_LIST containing all insns with pending write operations. */
1011 static rtx pending_write_insns;
1013 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
1014 static rtx pending_write_mems;
1016 /* Indicates the combined length of the two pending lists. We must prevent
1017 these lists from ever growing too large since the number of dependencies
1018 produced is at least O(N*N), and execution time is at least O(4*N*N), as
1019 a function of the length of these pending lists. */
1021 static int pending_lists_length;
1023 /* The last insn upon which all memory references must depend.
1024 This is an insn which flushed the pending lists, creating a dependency
1025 between it and all previously pending memory references. This creates
1026 a barrier (or a checkpoint) which no memory reference is allowed to cross.
1028 This includes all non constant CALL_INSNs. When we do interprocedural
1029 alias analysis, this restriction can be relaxed.
1030 This may also be an INSN that writes memory if the pending lists grow
1033 static rtx last_pending_memory_flush;
1035 /* The last function call we have seen. All hard regs, and, of course,
1036 the last function call, must depend on this. */
1038 static rtx last_function_call;
1040 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
1041 that does not already cross a call. We create dependencies between each
1042 of those insn and the next call insn, to ensure that they won't cross a call
1043 after scheduling is done. */
1045 static rtx sched_before_next_call;
1047 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1048 so that insns independent of the last scheduled insn will be preferred
1049 over dependent instructions. */
1051 static rtx last_scheduled_insn;
1053 /* Data structures for the computation of data dependences in a regions. We
1054 keep one copy of each of the declared above variables for each bb in the
1055 region. Before analyzing the data dependences for a bb, its variables
1056 are initialized as a function of the variables of its predecessors. When
1057 the analysis for a bb completes, we save the contents of each variable X
1058 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
1059 copied to bb_pending_read_insns[bb]. Another change is that few
1060 variables are now a list of insns rather than a single insn:
1061 last_pending_memory_flash, last_function_call, reg_last_sets. The
1062 manipulation of these variables was changed appropriately. */
1064 static rtx **bb_reg_last_uses;
1065 static rtx **bb_reg_last_sets;
1067 static rtx *bb_pending_read_insns;
1068 static rtx *bb_pending_read_mems;
1069 static rtx *bb_pending_write_insns;
1070 static rtx *bb_pending_write_mems;
1071 static int *bb_pending_lists_length;
1073 static rtx *bb_last_pending_memory_flush;
1074 static rtx *bb_last_function_call;
1075 static rtx *bb_sched_before_next_call;
1077 /* functions for construction of the control flow graph. */
1079 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1081 We decide not to build the control flow graph if there is possibly more
1082 than one entry to the function, if computed branches exist, of if we
1083 have nonlocal gotos. */
1086 is_cfg_nonregular ()
1092 /* If we have a label that could be the target of a nonlocal goto, then
1093 the cfg is not well structured. */
1094 if (nonlocal_label_rtx_list () != NULL)
1097 /* If we have any forced labels, then the cfg is not well structured. */
1101 /* If this function has a computed jump, then we consider the cfg
1102 not well structured. */
1103 if (current_function_has_computed_jump)
1106 /* If we have exception handlers, then we consider the cfg not well
1107 structured. ?!? We should be able to handle this now that flow.c
1108 computes an accurate cfg for EH. */
1109 if (exception_handler_labels)
1112 /* If we have non-jumping insns which refer to labels, then we consider
1113 the cfg not well structured. */
1114 /* check for labels referred to other thn by jumps */
1115 for (b = 0; b < n_basic_blocks; b++)
1116 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
1118 code = GET_CODE (insn);
1119 if (GET_RTX_CLASS (code) == 'i')
1123 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1124 if (REG_NOTE_KIND (note) == REG_LABEL)
1128 if (insn == basic_block_end[b])
1132 /* All the tests passed. Consider the cfg well structured. */
1136 /* Print the control flow graph, for debugging purposes.
1137 Callable from the debugger. */
1140 debug_control_flow ()
1144 fprintf (dump, ";; --------- CONTROL FLOW GRAPH --------- \n\n");
1146 for (i = 0; i < n_basic_blocks; i++)
1148 fprintf (dump, ";;\tBasic block %d: first insn %d, last %d.\n",
1150 INSN_UID (basic_block_head[i]),
1151 INSN_UID (basic_block_end[i]));
1153 fprintf (dump, ";;\tPredecessor blocks:");
1154 for (e = IN_EDGES (i); e; e = next)
1156 fprintf (dump, " %d", FROM_BLOCK (e));
1160 if (next == IN_EDGES (i))
1164 fprintf (dump, "\n;;\tSuccesor blocks:");
1165 for (e = OUT_EDGES (i); e; e = next)
1167 fprintf (dump, " %d", TO_BLOCK (e));
1169 next = NEXT_OUT (e);
1171 if (next == OUT_EDGES (i))
1175 fprintf (dump, " \n\n");
1181 /* Build the control flow graph and set nr_edges.
1183 Instead of trying to build a cfg ourselves, we rely on flow to
1184 do it for us. Stamp out useless code (and bug) duplication.
1186 Return nonzero if an irregularity in the cfg is found which would
1187 prevent cross block scheduling. */
1190 build_control_flow ()
1193 int_list_ptr *s_preds;
1194 int_list_ptr *s_succs;
1200 /* The scheduler runs after flow; therefore, we can't blindly call
1201 back into find_basic_blocks since doing so could invalidate the
1202 info in basic_block_live_at_start.
1204 Consider a block consisting entirely of dead stores; after life
1205 analysis it would be a block of NOTE_INSN_DELETED notes. If
1206 we call find_basic_blocks again, then the block would be removed
1207 entirely and invalidate our the register live information.
1209 We could (should?) recompute register live information. Doing
1210 so may even be beneficial. */
1211 s_preds = (int_list_ptr *) alloca (n_basic_blocks * sizeof (int_list_ptr));
1212 s_succs = (int_list_ptr *) alloca (n_basic_blocks * sizeof (int_list_ptr));
1213 num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
1214 num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
1215 compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
1217 /* Count the number of edges in the cfg. */
1220 for (i = 0; i < n_basic_blocks; i++)
1222 nr_edges += num_succs[i];
1223 /* ??? We must also detect unreachable loops here. We only handle the
1224 trivial case of a loop with one basic block for now. */
1225 if (num_preds[i] == 0
1226 || (num_preds[i] == 1 && INT_LIST_VAL (s_preds[i]) == i))
1230 /* Account for entry/exit edges. */
1233 in_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
1234 out_edges = (int *) xmalloc (n_basic_blocks * sizeof (int));
1235 bzero ((char *) in_edges, n_basic_blocks * sizeof (int));
1236 bzero ((char *) out_edges, n_basic_blocks * sizeof (int));
1238 edge_table = (edge *) xmalloc ((nr_edges) * sizeof (edge));
1239 bzero ((char *) edge_table, ((nr_edges) * sizeof (edge)));
1242 for (i = 0; i < n_basic_blocks; i++)
1243 for (succ = s_succs[i]; succ; succ = succ->next)
1245 if (INT_LIST_VAL (succ) != EXIT_BLOCK)
1246 new_edge (i, INT_LIST_VAL (succ));
1249 /* increment by 1, since edge 0 is unused. */
1252 /* For now. This will move as more and more of haifa is converted
1253 to using the cfg code in flow.c */
1259 /* Record an edge in the control flow graph from SOURCE to TARGET.
1261 In theory, this is redundant with the s_succs computed above, but
1262 we have not converted all of haifa to use information from the
1266 new_edge (source, target)
1270 int curr_edge, fst_edge;
1272 /* check for duplicates */
1273 fst_edge = curr_edge = OUT_EDGES (source);
1276 if (FROM_BLOCK (curr_edge) == source
1277 && TO_BLOCK (curr_edge) == target)
1282 curr_edge = NEXT_OUT (curr_edge);
1284 if (fst_edge == curr_edge)
1290 FROM_BLOCK (e) = source;
1291 TO_BLOCK (e) = target;
1293 if (OUT_EDGES (source))
1295 next_edge = NEXT_OUT (OUT_EDGES (source));
1296 NEXT_OUT (OUT_EDGES (source)) = e;
1297 NEXT_OUT (e) = next_edge;
1301 OUT_EDGES (source) = e;
1305 if (IN_EDGES (target))
1307 next_edge = NEXT_IN (IN_EDGES (target));
1308 NEXT_IN (IN_EDGES (target)) = e;
1309 NEXT_IN (e) = next_edge;
1313 IN_EDGES (target) = e;
1319 /* BITSET macros for operations on the control flow graph. */
1321 /* Compute bitwise union of two bitsets. */
1322 #define BITSET_UNION(set1, set2, len) \
1323 do { register bitset tp = set1, sp = set2; \
1325 for (i = 0; i < len; i++) \
1326 *(tp++) |= *(sp++); } while (0)
1328 /* Compute bitwise intersection of two bitsets. */
1329 #define BITSET_INTER(set1, set2, len) \
1330 do { register bitset tp = set1, sp = set2; \
1332 for (i = 0; i < len; i++) \
1333 *(tp++) &= *(sp++); } while (0)
1335 /* Compute bitwise difference of two bitsets. */
1336 #define BITSET_DIFFER(set1, set2, len) \
1337 do { register bitset tp = set1, sp = set2; \
1339 for (i = 0; i < len; i++) \
1340 *(tp++) &= ~*(sp++); } while (0)
1342 /* Inverts every bit of bitset 'set' */
1343 #define BITSET_INVERT(set, len) \
1344 do { register bitset tmpset = set; \
1346 for (i = 0; i < len; i++, tmpset++) \
1347 *tmpset = ~*tmpset; } while (0)
1349 /* Turn on the index'th bit in bitset set. */
1350 #define BITSET_ADD(set, index, len) \
1352 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1355 set[index/HOST_BITS_PER_WIDE_INT] |= \
1356 1 << (index % HOST_BITS_PER_WIDE_INT); \
1359 /* Turn off the index'th bit in set. */
1360 #define BITSET_REMOVE(set, index, len) \
1362 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1365 set[index/HOST_BITS_PER_WIDE_INT] &= \
1366 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1370 /* Check if the index'th bit in bitset set is on. */
1373 bitset_member (set, index, len)
1377 if (index >= HOST_BITS_PER_WIDE_INT * len)
1379 return (set[index / HOST_BITS_PER_WIDE_INT] &
1380 1 << (index % HOST_BITS_PER_WIDE_INT)) ? 1 : 0;
1384 /* Translate a bit-set SET to a list BL of the bit-set members. */
1387 extract_bitlst (set, len, bl)
1393 unsigned HOST_WIDE_INT word;
1395 /* bblst table space is reused in each call to extract_bitlst */
1396 bitlst_table_last = 0;
1398 bl->first_member = &bitlst_table[bitlst_table_last];
1401 for (i = 0; i < len; i++)
1404 offset = i * HOST_BITS_PER_WIDE_INT;
1405 for (j = 0; word; j++)
1409 bitlst_table[bitlst_table_last++] = offset;
1420 /* functions for the construction of regions */
1422 /* Print the regions, for debugging purposes. Callable from debugger. */
1429 fprintf (dump, "\n;; ------------ REGIONS ----------\n\n");
1430 for (rgn = 0; rgn < nr_regions; rgn++)
1432 fprintf (dump, ";;\trgn %d nr_blocks %d:\n", rgn,
1433 rgn_table[rgn].rgn_nr_blocks);
1434 fprintf (dump, ";;\tbb/block: ");
1436 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
1438 current_blocks = RGN_BLOCKS (rgn);
1440 if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
1443 fprintf (dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
1446 fprintf (dump, "\n\n");
1451 /* Build a single block region for each basic block in the function.
1452 This allows for using the same code for interblock and basic block
1456 find_single_block_region ()
1460 for (i = 0; i < n_basic_blocks; i++)
1462 rgn_bb_table[i] = i;
1463 RGN_NR_BLOCKS (i) = 1;
1465 CONTAINING_RGN (i) = i;
1466 BLOCK_TO_BB (i) = 0;
1468 nr_regions = n_basic_blocks;
1472 /* Update number of blocks and the estimate for number of insns
1473 in the region. Return 1 if the region is "too large" for interblock
1474 scheduling (compile time considerations), otherwise return 0. */
1477 too_large (block, num_bbs, num_insns)
1478 int block, *num_bbs, *num_insns;
1481 (*num_insns) += (INSN_LUID (basic_block_end[block]) -
1482 INSN_LUID (basic_block_head[block]));
1483 if ((*num_bbs > max_rgn_blocks) || (*num_insns > max_rgn_insns))
1490 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1491 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1492 loop containing blk. */
1493 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1495 if (max_hdr[blk] == -1) \
1496 max_hdr[blk] = hdr; \
1497 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1499 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1501 inner[max_hdr[blk]] = 0; \
1502 max_hdr[blk] = hdr; \
1507 /* Find regions for interblock scheduling: a loop-free procedure, a reducible
1508 inner loop, or a basic block not contained in any other region.
1509 The procedures control flow graph is traversed twice.
1510 First traversal, a DFS, finds the headers of inner loops in the graph,
1511 and verifies that there are no unreacable blocks.
1512 Second traversal processes headers of inner loops, checking that the
1513 loop is reducible. The loop blocks that form a region are put into the
1514 region's blocks list in topological order.
1516 The following variables are changed by the function: rgn_nr, rgn_table,
1517 rgn_bb_table, block_to_bb and containing_rgn. */
1522 int *max_hdr, *dfs_nr, *stack, *queue, *degree;
1523 char *header, *inner, *passed, *in_stack, *in_queue, no_loops = 1;
1524 int node, child, loop_head, i, j, fst_edge, head, tail;
1525 int count = 0, sp, idx = 0, current_edge = out_edges[0];
1526 int num_bbs, num_insns;
1527 int too_large_failure;
1530 The following data structures are computed by the first traversal and
1531 are used by the second traversal:
1532 header[i] - flag set if the block i is the header of a loop.
1533 inner[i] - initially set. It is reset if the the block i is the header
1534 of a non-inner loop.
1535 max_hdr[i] - the header of the inner loop containing block i.
1536 (for a block i not in an inner loop it may be -1 or the
1537 header of the most inner loop containing the block).
1539 These data structures are used by the first traversal only:
1540 stack - non-recursive DFS implementation which uses a stack of edges.
1541 sp - top of the stack of edges
1542 dfs_nr[i] - the DFS ordering of block i.
1543 in_stack[i] - flag set if the block i is in the DFS stack.
1545 These data structures are used by the second traversal only:
1546 queue - queue containing the blocks of the current region.
1547 head and tail - queue boundaries.
1548 in_queue[i] - flag set if the block i is in queue */
1550 /* function's inner arrays allocation and initialization */
1551 max_hdr = (int *) alloca (n_basic_blocks * sizeof (int));
1552 dfs_nr = (int *) alloca (n_basic_blocks * sizeof (int));
1553 bzero ((char *) dfs_nr, n_basic_blocks * sizeof (int));
1554 stack = (int *) alloca (nr_edges * sizeof (int));
1555 queue = (int *) alloca (n_basic_blocks * sizeof (int));
1557 inner = (char *) alloca (n_basic_blocks * sizeof (char));
1558 header = (char *) alloca (n_basic_blocks * sizeof (char));
1559 bzero ((char *) header, n_basic_blocks * sizeof (char));
1560 passed = (char *) alloca (nr_edges * sizeof (char));
1561 bzero ((char *) passed, nr_edges * sizeof (char));
1562 in_stack = (char *) alloca (nr_edges * sizeof (char));
1563 bzero ((char *) in_stack, nr_edges * sizeof (char));
1565 in_queue = (char *) alloca (n_basic_blocks * sizeof (char));
1567 for (i = 0; i < n_basic_blocks; i++)
1573 /* First traversal: DFS, finds inner loops in control flow graph */
1578 if (current_edge == 0 || passed[current_edge])
1580 /* Here, if current_edge < 0, this is a leaf block.
1581 Otherwise current_edge was already passed. Note that in
1582 the latter case, not only current_edge but also all its
1583 NEXT_OUT edges are also passed. We have to "climb up on
1584 edges in the stack", looking for the first (already
1585 passed) edge whose NEXT_OUT was not passed yet. */
1587 while (sp >= 0 && (current_edge == 0 || passed[current_edge]))
1589 current_edge = stack[sp--];
1590 node = FROM_BLOCK (current_edge);
1591 child = TO_BLOCK (current_edge);
1592 in_stack[child] = 0;
1593 if (max_hdr[child] >= 0 && in_stack[max_hdr[child]])
1594 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1595 current_edge = NEXT_OUT (current_edge);
1598 /* stack empty - the whole graph is traversed. */
1599 if (sp < 0 && passed[current_edge])
1604 node = FROM_BLOCK (current_edge);
1605 dfs_nr[node] = ++count;
1607 child = TO_BLOCK (current_edge);
1609 /* found a loop header */
1610 if (in_stack[child])
1614 max_hdr[child] = child;
1615 UPDATE_LOOP_RELATIONS (node, child);
1616 passed[current_edge] = 1;
1617 current_edge = NEXT_OUT (current_edge);
1621 /* the child was already visited once, no need to go down from
1622 it, everything is traversed there. */
1625 if (max_hdr[child] >= 0 && in_stack[max_hdr[child]])
1626 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1627 passed[current_edge] = 1;
1628 current_edge = NEXT_OUT (current_edge);
1632 /* this is a step down in the dfs traversal */
1633 stack[++sp] = current_edge;
1634 passed[current_edge] = 1;
1635 current_edge = OUT_EDGES (child);
1638 /* Second travsersal: find reducible inner loops, and sort
1639 topologically the blocks of each region */
1640 degree = dfs_nr; /* reuse dfs_nr array - it is not needed anymore */
1641 bzero ((char *) in_queue, n_basic_blocks * sizeof (char));
1646 /* compute the in-degree of every block in the graph */
1647 for (i = 0; i < n_basic_blocks; i++)
1649 fst_edge = IN_EDGES (i);
1653 current_edge = NEXT_IN (fst_edge);
1654 while (fst_edge != current_edge)
1657 current_edge = NEXT_IN (current_edge);
1664 /* pass through all graph blocks, looking for headers of inner loops */
1665 for (i = 0; i < n_basic_blocks; i++)
1668 if (header[i] && inner[i])
1671 /* i is a header of a potentially reducible inner loop, or
1672 block 0 in a subroutine with no loops at all */
1674 too_large_failure = 0;
1675 loop_head = max_hdr[i];
1677 /* decrease in_degree of all i's successors, (this is needed
1678 for the topological ordering) */
1679 fst_edge = current_edge = OUT_EDGES (i);
1684 --degree[TO_BLOCK (current_edge)];
1685 current_edge = NEXT_OUT (current_edge);
1687 while (fst_edge != current_edge);
1690 /* estimate # insns, and count # blocks in the region. */
1692 num_insns = INSN_LUID (basic_block_end[i]) - INSN_LUID (basic_block_head[i]);
1695 /* find all loop latches, if it is a true loop header, or
1696 all leaves if the graph has no loops at all */
1699 for (j = 0; j < n_basic_blocks; j++)
1700 if (out_edges[j] == 0) /* a leaf */
1705 if (too_large (j, &num_bbs, &num_insns))
1707 too_large_failure = 1;
1714 fst_edge = current_edge = IN_EDGES (i);
1717 node = FROM_BLOCK (current_edge);
1718 if (max_hdr[node] == loop_head && node != i) /* a latch */
1720 queue[++tail] = node;
1723 if (too_large (node, &num_bbs, &num_insns))
1725 too_large_failure = 1;
1729 current_edge = NEXT_IN (current_edge);
1731 while (fst_edge != current_edge);
1734 /* Put in queue[] all blocks that belong to the loop. Check
1735 that the loop is reducible, traversing back from the loop
1736 latches up to the loop header. */
1737 while (head < tail && !too_large_failure)
1739 child = queue[++head];
1740 fst_edge = current_edge = IN_EDGES (child);
1743 node = FROM_BLOCK (current_edge);
1745 if (max_hdr[node] != loop_head)
1746 { /* another entry to loop, it is irreducible */
1750 else if (!in_queue[node] && node != i)
1752 queue[++tail] = node;
1755 if (too_large (node, &num_bbs, &num_insns))
1757 too_large_failure = 1;
1761 current_edge = NEXT_IN (current_edge);
1763 while (fst_edge != current_edge);
1766 if (tail >= 0 && !too_large_failure)
1768 /* Place the loop header into list of region blocks */
1770 rgn_bb_table[idx] = i;
1771 RGN_NR_BLOCKS (nr_regions) = num_bbs;
1772 RGN_BLOCKS (nr_regions) = idx++;
1773 CONTAINING_RGN (i) = nr_regions;
1774 BLOCK_TO_BB (i) = count = 0;
1776 /* remove blocks from queue[], (in topological order), when
1777 their in_degree becomes 0. We scan the queue over and
1778 over again until it is empty. Note: there may be a more
1779 efficient way to do it. */
1784 child = queue[head];
1785 if (degree[child] == 0)
1788 rgn_bb_table[idx++] = child;
1789 BLOCK_TO_BB (child) = ++count;
1790 CONTAINING_RGN (child) = nr_regions;
1791 queue[head] = queue[tail--];
1792 fst_edge = current_edge = OUT_EDGES (child);
1798 --degree[TO_BLOCK (current_edge)];
1799 current_edge = NEXT_OUT (current_edge);
1801 while (fst_edge != current_edge);
1812 /* define each of all other blocks as a region itself */
1813 for (i = 0; i < n_basic_blocks; i++)
1816 rgn_bb_table[idx] = i;
1817 RGN_NR_BLOCKS (nr_regions) = 1;
1818 RGN_BLOCKS (nr_regions) = idx++;
1819 CONTAINING_RGN (i) = nr_regions++;
1820 BLOCK_TO_BB (i) = 0;
1826 /* functions for regions scheduling information */
1828 /* Compute dominators, probability, and potential-split-edges of bb.
1829 Assume that these values were already computed for bb's predecessors. */
1832 compute_dom_prob_ps (bb)
1835 int nxt_in_edge, fst_in_edge, pred;
1836 int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1839 if (IS_RGN_ENTRY (bb))
1841 BITSET_ADD (dom[bb], 0, bbset_size);
1846 fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1848 /* intialize dom[bb] to '111..1' */
1849 BITSET_INVERT (dom[bb], bbset_size);
1853 pred = FROM_BLOCK (nxt_in_edge);
1854 BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
1856 BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
1859 BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
1862 nr_rgn_out_edges = 0;
1863 fst_out_edge = OUT_EDGES (pred);
1864 nxt_out_edge = NEXT_OUT (fst_out_edge);
1865 BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
1868 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
1870 /* the successor doesn't belong the region? */
1871 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1872 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1875 while (fst_out_edge != nxt_out_edge)
1878 /* the successor doesn't belong the region? */
1879 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1880 CONTAINING_RGN (BB_TO_BLOCK (bb)))
1882 BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
1883 nxt_out_edge = NEXT_OUT (nxt_out_edge);
1887 /* now nr_rgn_out_edges is the number of region-exit edges from pred,
1888 and nr_out_edges will be the number of pred out edges not leaving
1890 nr_out_edges -= nr_rgn_out_edges;
1891 if (nr_rgn_out_edges > 0)
1892 prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1894 prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1895 nxt_in_edge = NEXT_IN (nxt_in_edge);
1897 while (fst_in_edge != nxt_in_edge);
1899 BITSET_ADD (dom[bb], bb, bbset_size);
1900 BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
1902 if (sched_verbose >= 2)
1903 fprintf (dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb), (int) (100.0 * prob[bb]));
1904 } /* compute_dom_prob_ps */
1906 /* functions for target info */
1908 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1909 Note that bb_trg dominates bb_src. */
1912 split_edges (bb_src, bb_trg, bl)
1917 int es = edgeset_size;
1918 edgeset src = (edgeset) alloca (es * sizeof (HOST_WIDE_INT));
1921 src[es] = (pot_split[bb_src])[es];
1922 BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
1923 extract_bitlst (src, edgeset_size, bl);
1927 /* Find the valid candidate-source-blocks for the target block TRG, compute
1928 their probability, and check if they are speculative or not.
1929 For speculative sources, compute their update-blocks and split-blocks. */
1932 compute_trg_info (trg)
1935 register candidate *sp;
1937 int check_block, update_idx;
1938 int i, j, k, fst_edge, nxt_edge;
1940 /* define some of the fields for the target bb as well */
1941 sp = candidate_table + trg;
1943 sp->is_speculative = 0;
1946 for (i = trg + 1; i < current_nr_blocks; i++)
1948 sp = candidate_table + i;
1950 sp->is_valid = IS_DOMINATED (i, trg);
1953 sp->src_prob = GET_SRC_PROB (i, trg);
1954 sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
1959 split_edges (i, trg, &el);
1960 sp->is_speculative = (el.nr_members) ? 1 : 0;
1961 if (sp->is_speculative && !flag_schedule_speculative)
1967 sp->split_bbs.first_member = &bblst_table[bblst_last];
1968 sp->split_bbs.nr_members = el.nr_members;
1969 for (j = 0; j < el.nr_members; bblst_last++, j++)
1970 bblst_table[bblst_last] =
1971 TO_BLOCK (rgn_edges[el.first_member[j]]);
1972 sp->update_bbs.first_member = &bblst_table[bblst_last];
1974 for (j = 0; j < el.nr_members; j++)
1976 check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
1977 fst_edge = nxt_edge = OUT_EDGES (check_block);
1980 for (k = 0; k < el.nr_members; k++)
1981 if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
1984 if (k >= el.nr_members)
1986 bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
1990 nxt_edge = NEXT_OUT (nxt_edge);
1992 while (fst_edge != nxt_edge);
1994 sp->update_bbs.nr_members = update_idx;
1999 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
2001 sp->is_speculative = 0;
2005 } /* compute_trg_info */
2008 /* Print candidates info, for debugging purposes. Callable from debugger. */
2014 if (!candidate_table[i].is_valid)
2017 if (candidate_table[i].is_speculative)
2020 fprintf (dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
2022 fprintf (dump, "split path: ");
2023 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
2025 int b = candidate_table[i].split_bbs.first_member[j];
2027 fprintf (dump, " %d ", b);
2029 fprintf (dump, "\n");
2031 fprintf (dump, "update path: ");
2032 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
2034 int b = candidate_table[i].update_bbs.first_member[j];
2036 fprintf (dump, " %d ", b);
2038 fprintf (dump, "\n");
2042 fprintf (dump, " src %d equivalent\n", BB_TO_BLOCK (i));
2047 /* Print candidates info, for debugging purposes. Callable from debugger. */
2050 debug_candidates (trg)
2055 fprintf (dump, "----------- candidate table: target: b=%d bb=%d ---\n",
2056 BB_TO_BLOCK (trg), trg);
2057 for (i = trg + 1; i < current_nr_blocks; i++)
2058 debug_candidate (i);
2062 /* functions for speculative scheduing */
2064 /* Return 0 if x is a set of a register alive in the beginning of one
2065 of the split-blocks of src, otherwise return 1. */
2068 check_live_1 (src, x)
2074 register rtx reg = SET_DEST (x);
2079 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2080 || GET_CODE (reg) == SIGN_EXTRACT
2081 || GET_CODE (reg) == STRICT_LOW_PART)
2082 reg = XEXP (reg, 0);
2084 if (GET_CODE (reg) != REG)
2087 regno = REGNO (reg);
2089 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2091 /* Global registers are assumed live */
2096 if (regno < FIRST_PSEUDO_REGISTER)
2098 /* check for hard registers */
2099 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2102 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2104 int b = candidate_table[src].split_bbs.first_member[i];
2106 if (REGNO_REG_SET_P (basic_block_live_at_start[b], regno + j))
2115 /* check for psuedo registers */
2116 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2118 int b = candidate_table[src].split_bbs.first_member[i];
2120 if (REGNO_REG_SET_P (basic_block_live_at_start[b], regno))
2132 /* If x is a set of a register R, mark that R is alive in the beginning
2133 of every update-block of src. */
2136 update_live_1 (src, x)
2142 register rtx reg = SET_DEST (x);
2147 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2148 || GET_CODE (reg) == SIGN_EXTRACT
2149 || GET_CODE (reg) == STRICT_LOW_PART)
2150 reg = XEXP (reg, 0);
2152 if (GET_CODE (reg) != REG)
2155 /* Global registers are always live, so the code below does not apply
2158 regno = REGNO (reg);
2160 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
2162 if (regno < FIRST_PSEUDO_REGISTER)
2164 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2167 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2169 int b = candidate_table[src].update_bbs.first_member[i];
2171 SET_REGNO_REG_SET (basic_block_live_at_start[b], regno + j);
2177 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2179 int b = candidate_table[src].update_bbs.first_member[i];
2181 SET_REGNO_REG_SET (basic_block_live_at_start[b], regno);
2188 /* Return 1 if insn can be speculatively moved from block src to trg,
2189 otherwise return 0. Called before first insertion of insn to
2190 ready-list or before the scheduling. */
2193 check_live (insn, src)
2197 /* find the registers set by instruction */
2198 if (GET_CODE (PATTERN (insn)) == SET
2199 || GET_CODE (PATTERN (insn)) == CLOBBER)
2200 return check_live_1 (src, PATTERN (insn));
2201 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2204 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2205 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2206 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2207 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
2217 /* Update the live registers info after insn was moved speculatively from
2218 block src to trg. */
2221 update_live (insn, src)
2225 /* find the registers set by instruction */
2226 if (GET_CODE (PATTERN (insn)) == SET
2227 || GET_CODE (PATTERN (insn)) == CLOBBER)
2228 update_live_1 (src, PATTERN (insn));
2229 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2232 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2233 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2234 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2235 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
2239 /* Exception Free Loads:
2241 We define five classes of speculative loads: IFREE, IRISKY,
2242 PFREE, PRISKY, and MFREE.
2244 IFREE loads are loads that are proved to be exception-free, just
2245 by examining the load insn. Examples for such loads are loads
2246 from TOC and loads of global data.
2248 IRISKY loads are loads that are proved to be exception-risky,
2249 just by examining the load insn. Examples for such loads are
2250 volatile loads and loads from shared memory.
2252 PFREE loads are loads for which we can prove, by examining other
2253 insns, that they are exception-free. Currently, this class consists
2254 of loads for which we are able to find a "similar load", either in
2255 the target block, or, if only one split-block exists, in that split
2256 block. Load2 is similar to load1 if both have same single base
2257 register. We identify only part of the similar loads, by finding
2258 an insn upon which both load1 and load2 have a DEF-USE dependence.
2260 PRISKY loads are loads for which we can prove, by examining other
2261 insns, that they are exception-risky. Currently we have two proofs for
2262 such loads. The first proof detects loads that are probably guarded by a
2263 test on the memory address. This proof is based on the
2264 backward and forward data dependence information for the region.
2265 Let load-insn be the examined load.
2266 Load-insn is PRISKY iff ALL the following hold:
2268 - insn1 is not in the same block as load-insn
2269 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2270 - test-insn is either a compare or a branch, not in the same block as load-insn
2271 - load-insn is reachable from test-insn
2272 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2274 This proof might fail when the compare and the load are fed
2275 by an insn not in the region. To solve this, we will add to this
2276 group all loads that have no input DEF-USE dependence.
2278 The second proof detects loads that are directly or indirectly
2279 fed by a speculative load. This proof is affected by the
2280 scheduling process. We will use the flag fed_by_spec_load.
2281 Initially, all insns have this flag reset. After a speculative
2282 motion of an insn, if insn is either a load, or marked as
2283 fed_by_spec_load, we will also mark as fed_by_spec_load every
2284 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2285 load which is fed_by_spec_load is also PRISKY.
2287 MFREE (maybe-free) loads are all the remaining loads. They may be
2288 exception-free, but we cannot prove it.
2290 Now, all loads in IFREE and PFREE classes are considered
2291 exception-free, while all loads in IRISKY and PRISKY classes are
2292 considered exception-risky. As for loads in the MFREE class,
2293 these are considered either exception-free or exception-risky,
2294 depending on whether we are pessimistic or optimistic. We have
2295 to take the pessimistic approach to assure the safety of
2296 speculative scheduling, but we can take the optimistic approach
2297 by invoking the -fsched_spec_load_dangerous option. */
2299 enum INSN_TRAP_CLASS
2301 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
2302 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
2305 #define WORST_CLASS(class1, class2) \
2306 ((class1 > class2) ? class1 : class2)
2308 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between */
2309 /* some speculatively moved load insn and this one. */
2310 char *fed_by_spec_load;
2313 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2314 #define IS_REACHABLE(bb_from, bb_to) \
2316 || IS_RGN_ENTRY (bb_from) \
2317 || (bitset_member (ancestor_edges[bb_to], \
2318 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2320 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2321 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2323 /* Non-zero iff the address is comprised from at most 1 register */
2324 #define CONST_BASED_ADDRESS_P(x) \
2325 (GET_CODE (x) == REG \
2326 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2327 || (GET_CODE (x) == LO_SUM)) \
2328 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2329 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2331 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2334 set_spec_fed (load_insn)
2339 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
2340 if (GET_MODE (link) == VOIDmode)
2341 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
2342 } /* set_spec_fed */
2344 /* On the path from the insn to load_insn_bb, find a conditional branch */
2345 /* depending on insn, that guards the speculative load. */
2348 find_conditional_protection (insn, load_insn_bb)
2354 /* iterate through DEF-USE forward dependences */
2355 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2357 rtx next = XEXP (link, 0);
2358 if ((CONTAINING_RGN (INSN_BLOCK (next)) ==
2359 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
2360 && IS_REACHABLE (INSN_BB (next), load_insn_bb)
2361 && load_insn_bb != INSN_BB (next)
2362 && GET_MODE (link) == VOIDmode
2363 && (GET_CODE (next) == JUMP_INSN
2364 || find_conditional_protection (next, load_insn_bb)))
2368 } /* find_conditional_protection */
2370 /* Returns 1 if the same insn1 that participates in the computation
2371 of load_insn's address is feeding a conditional branch that is
2372 guarding on load_insn. This is true if we find a the two DEF-USE
2374 insn1 -> ... -> conditional-branch
2375 insn1 -> ... -> load_insn,
2376 and if a flow path exist:
2377 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2378 and if insn1 is on the path
2379 region-entry -> ... -> bb_trg -> ... load_insn.
2381 Locate insn1 by climbing on LOG_LINKS from load_insn.
2382 Locate the branch by following INSN_DEPEND from insn1. */
2385 is_conditionally_protected (load_insn, bb_src, bb_trg)
2391 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
2393 rtx insn1 = XEXP (link, 0);
2395 /* must be a DEF-USE dependence upon non-branch */
2396 if (GET_MODE (link) != VOIDmode
2397 || GET_CODE (insn1) == JUMP_INSN)
2400 /* must exist a path: region-entry -> ... -> bb_trg -> ... load_insn */
2401 if (INSN_BB (insn1) == bb_src
2402 || (CONTAINING_RGN (INSN_BLOCK (insn1))
2403 != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
2404 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
2405 && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
2408 /* now search for the conditional-branch */
2409 if (find_conditional_protection (insn1, bb_src))
2412 /* recursive step: search another insn1, "above" current insn1. */
2413 return is_conditionally_protected (insn1, bb_src, bb_trg);
2416 /* the chain does not exsist */
2418 } /* is_conditionally_protected */
2420 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2421 load_insn can move speculatively from bb_src to bb_trg. All the
2422 following must hold:
2424 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2425 (2) load_insn and load1 have a def-use dependence upon
2426 the same insn 'insn1'.
2427 (3) either load2 is in bb_trg, or:
2428 - there's only one split-block, and
2429 - load1 is on the escape path, and
2431 From all these we can conclude that the two loads access memory
2432 addresses that differ at most by a constant, and hence if moving
2433 load_insn would cause an exception, it would have been caused by
2437 is_pfree (load_insn, bb_src, bb_trg)
2442 register candidate *candp = candidate_table + bb_src;
2444 if (candp->split_bbs.nr_members != 1)
2445 /* must have exactly one escape block */
2448 for (back_link = LOG_LINKS (load_insn);
2449 back_link; back_link = XEXP (back_link, 1))
2451 rtx insn1 = XEXP (back_link, 0);
2453 if (GET_MODE (back_link) == VOIDmode)
2455 /* found a DEF-USE dependence (insn1, load_insn) */
2458 for (fore_link = INSN_DEPEND (insn1);
2459 fore_link; fore_link = XEXP (fore_link, 1))
2461 rtx insn2 = XEXP (fore_link, 0);
2462 if (GET_MODE (fore_link) == VOIDmode)
2464 /* found a DEF-USE dependence (insn1, insn2) */
2465 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
2466 /* insn2 not guaranteed to be a 1 base reg load */
2469 if (INSN_BB (insn2) == bb_trg)
2470 /* insn2 is the similar load, in the target block */
2473 if (*(candp->split_bbs.first_member) == INSN_BLOCK (insn2))
2474 /* insn2 is a similar load, in a split-block */
2481 /* couldn't find a similar load */
2485 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2486 as found by analyzing insn's expression. */
2489 may_trap_exp (x, is_store)
2497 code = GET_CODE (x);
2507 /* The insn uses memory */
2508 /* a volatile load */
2509 if (MEM_VOLATILE_P (x))
2511 /* an exception-free load */
2512 if (!may_trap_p (x))
2514 /* a load with 1 base register, to be further checked */
2515 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
2516 return PFREE_CANDIDATE;
2517 /* no info on the load, to be further checked */
2518 return PRISKY_CANDIDATE;
2523 int i, insn_class = TRAP_FREE;
2525 /* neither store nor load, check if it may cause a trap */
2528 /* recursive step: walk the insn... */
2529 fmt = GET_RTX_FORMAT (code);
2530 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2534 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
2535 insn_class = WORST_CLASS (insn_class, tmp_class);
2537 else if (fmt[i] == 'E')
2540 for (j = 0; j < XVECLEN (x, i); j++)
2542 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
2543 insn_class = WORST_CLASS (insn_class, tmp_class);
2544 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2548 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2553 } /* may_trap_exp */
2556 /* Classifies insn for the purpose of verifying that it can be
2557 moved speculatively, by examining it's patterns, returning:
2558 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2559 TRAP_FREE: non-load insn.
2560 IFREE: load from a globaly safe location.
2561 IRISKY: volatile load.
2562 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2563 being either PFREE or PRISKY. */
2566 haifa_classify_insn (insn)
2569 rtx pat = PATTERN (insn);
2570 int tmp_class = TRAP_FREE;
2571 int insn_class = TRAP_FREE;
2574 if (GET_CODE (pat) == PARALLEL)
2576 int i, len = XVECLEN (pat, 0);
2578 for (i = len - 1; i >= 0; i--)
2580 code = GET_CODE (XVECEXP (pat, 0, i));
2584 /* test if it is a 'store' */
2585 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
2588 /* test if it is a store */
2589 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
2590 if (tmp_class == TRAP_RISKY)
2592 /* test if it is a load */
2594 WORST_CLASS (tmp_class,
2595 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 0));
2598 insn_class = WORST_CLASS (insn_class, tmp_class);
2599 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2605 code = GET_CODE (pat);
2609 /* test if it is a 'store' */
2610 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
2613 /* test if it is a store */
2614 tmp_class = may_trap_exp (SET_DEST (pat), 1);
2615 if (tmp_class == TRAP_RISKY)
2617 /* test if it is a load */
2619 WORST_CLASS (tmp_class,
2620 may_trap_exp (SET_SRC (pat), 0));
2623 insn_class = tmp_class;
2628 } /* haifa_classify_insn */
2630 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2631 a load moved speculatively, or if load_insn is protected by
2632 a compare on load_insn's address). */
2635 is_prisky (load_insn, bb_src, bb_trg)
2639 if (FED_BY_SPEC_LOAD (load_insn))
2642 if (LOG_LINKS (load_insn) == NULL)
2643 /* dependence may 'hide' out of the region. */
2646 if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2652 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2653 Return 1 if insn is exception-free (and the motion is valid)
2657 is_exception_free (insn, bb_src, bb_trg)
2661 int insn_class = haifa_classify_insn (insn);
2663 /* handle non-load insns */
2674 if (!flag_schedule_speculative_load)
2676 IS_LOAD_INSN (insn) = 1;
2683 case PFREE_CANDIDATE:
2684 if (is_pfree (insn, bb_src, bb_trg))
2686 /* don't 'break' here: PFREE-candidate is also PRISKY-candidate */
2687 case PRISKY_CANDIDATE:
2688 if (!flag_schedule_speculative_load_dangerous
2689 || is_prisky (insn, bb_src, bb_trg))
2695 return flag_schedule_speculative_load_dangerous;
2696 } /* is_exception_free */
2699 /* Process an insn's memory dependencies. There are four kinds of
2702 (0) read dependence: read follows read
2703 (1) true dependence: read follows write
2704 (2) anti dependence: write follows read
2705 (3) output dependence: write follows write
2707 We are careful to build only dependencies which actually exist, and
2708 use transitivity to avoid building too many links. */
2710 /* Return the INSN_LIST containing INSN in LIST, or NULL
2711 if LIST does not contain INSN. */
2714 find_insn_list (insn, list)
2720 if (XEXP (list, 0) == insn)
2722 list = XEXP (list, 1);
2728 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 otherwise. */
2730 __inline static char
2731 find_insn_mem_list (insn, x, list, list1)
2737 if (XEXP (list, 0) == insn
2738 && XEXP (list1, 0) == x)
2740 list = XEXP (list, 1);
2741 list1 = XEXP (list1, 1);
2747 /* Compute the function units used by INSN. This caches the value
2748 returned by function_units_used. A function unit is encoded as the
2749 unit number if the value is non-negative and the compliment of a
2750 mask if the value is negative. A function unit index is the
2751 non-negative encoding. */
2757 register int unit = INSN_UNIT (insn);
2761 recog_memoized (insn);
2763 /* A USE insn, or something else we don't need to understand.
2764 We can't pass these directly to function_units_used because it will
2765 trigger a fatal error for unrecognizable insns. */
2766 if (INSN_CODE (insn) < 0)
2770 unit = function_units_used (insn);
2771 /* Increment non-negative values so we can cache zero. */
2775 /* We only cache 16 bits of the result, so if the value is out of
2776 range, don't cache it. */
2777 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
2779 || (~unit & ((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
2780 INSN_UNIT (insn) = unit;
2782 return (unit > 0 ? unit - 1 : unit);
2785 /* Compute the blockage range for executing INSN on UNIT. This caches
2786 the value returned by the blockage_range_function for the unit.
2787 These values are encoded in an int where the upper half gives the
2788 minimum value and the lower half gives the maximum value. */
2790 __inline static unsigned int
2791 blockage_range (unit, insn)
2795 unsigned int blockage = INSN_BLOCKAGE (insn);
2798 if (UNIT_BLOCKED (blockage) != unit + 1)
2800 range = function_units[unit].blockage_range_function (insn);
2801 /* We only cache the blockage range for one unit and then only if
2803 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
2804 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
2807 range = BLOCKAGE_RANGE (blockage);
2812 /* A vector indexed by function unit instance giving the last insn to use
2813 the unit. The value of the function unit instance index for unit U
2814 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2815 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2817 /* A vector indexed by function unit instance giving the minimum time when
2818 the unit will unblock based on the maximum blockage cost. */
2819 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2821 /* A vector indexed by function unit number giving the number of insns
2822 that remain to use the unit. */
2823 static int unit_n_insns[FUNCTION_UNITS_SIZE];
2825 /* Reset the function unit state to the null state. */
2830 bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
2831 bzero ((char *) unit_tick, sizeof (unit_tick));
2832 bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
2835 /* Return the issue-delay of an insn */
2838 insn_issue_delay (insn)
2842 int unit = insn_unit (insn);
2844 /* efficiency note: in fact, we are working 'hard' to compute a
2845 value that was available in md file, and is not available in
2846 function_units[] structure. It would be nice to have this
2847 value there, too. */
2850 if (function_units[unit].blockage_range_function &&
2851 function_units[unit].blockage_function)
2852 delay = function_units[unit].blockage_function (insn, insn);
2855 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2856 if ((unit & 1) != 0 && function_units[i].blockage_range_function
2857 && function_units[i].blockage_function)
2858 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
2863 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2864 instance INSTANCE at time CLOCK if the previous actual hazard cost
2868 actual_hazard_this_instance (unit, instance, insn, clock, cost)
2869 int unit, instance, clock, cost;
2872 int tick = unit_tick[instance]; /* issue time of the last issued insn */
2874 if (tick - clock > cost)
2876 /* The scheduler is operating forward, so unit's last insn is the
2877 executing insn and INSN is the candidate insn. We want a
2878 more exact measure of the blockage if we execute INSN at CLOCK
2879 given when we committed the execution of the unit's last insn.
2881 The blockage value is given by either the unit's max blockage
2882 constant, blockage range function, or blockage function. Use
2883 the most exact form for the given unit. */
2885 if (function_units[unit].blockage_range_function)
2887 if (function_units[unit].blockage_function)
2888 tick += (function_units[unit].blockage_function
2889 (unit_last_insn[instance], insn)
2890 - function_units[unit].max_blockage);
2892 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
2893 - function_units[unit].max_blockage);
2895 if (tick - clock > cost)
2896 cost = tick - clock;
2901 /* Record INSN as having begun execution on the units encoded by UNIT at
2904 __inline static void
2905 schedule_unit (unit, insn, clock)
2913 int instance = unit;
2914 #if MAX_MULTIPLICITY > 1
2915 /* Find the first free instance of the function unit and use that
2916 one. We assume that one is free. */
2917 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2919 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
2921 instance += FUNCTION_UNITS_SIZE;
2924 unit_last_insn[instance] = insn;
2925 unit_tick[instance] = (clock + function_units[unit].max_blockage);
2928 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2929 if ((unit & 1) != 0)
2930 schedule_unit (i, insn, clock);
2933 /* Return the actual hazard cost of executing INSN on the units encoded by
2934 UNIT at time CLOCK if the previous actual hazard cost was COST. */
2937 actual_hazard (unit, insn, clock, cost)
2938 int unit, clock, cost;
2945 /* Find the instance of the function unit with the minimum hazard. */
2946 int instance = unit;
2947 int best_cost = actual_hazard_this_instance (unit, instance, insn,
2951 #if MAX_MULTIPLICITY > 1
2952 if (best_cost > cost)
2954 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2956 instance += FUNCTION_UNITS_SIZE;
2957 this_cost = actual_hazard_this_instance (unit, instance, insn,
2959 if (this_cost < best_cost)
2961 best_cost = this_cost;
2962 if (this_cost <= cost)
2968 cost = MAX (cost, best_cost);
2971 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2972 if ((unit & 1) != 0)
2973 cost = actual_hazard (i, insn, clock, cost);
2978 /* Return the potential hazard cost of executing an instruction on the
2979 units encoded by UNIT if the previous potential hazard cost was COST.
2980 An insn with a large blockage time is chosen in preference to one
2981 with a smaller time; an insn that uses a unit that is more likely
2982 to be used is chosen in preference to one with a unit that is less
2983 used. We are trying to minimize a subsequent actual hazard. */
2986 potential_hazard (unit, insn, cost)
2991 unsigned int minb, maxb;
2995 minb = maxb = function_units[unit].max_blockage;
2998 if (function_units[unit].blockage_range_function)
3000 maxb = minb = blockage_range (unit, insn);
3001 maxb = MAX_BLOCKAGE_COST (maxb);
3002 minb = MIN_BLOCKAGE_COST (minb);
3007 /* Make the number of instructions left dominate. Make the
3008 minimum delay dominate the maximum delay. If all these
3009 are the same, use the unit number to add an arbitrary
3010 ordering. Other terms can be added. */
3011 ncost = minb * 0x40 + maxb;
3012 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
3019 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
3020 if ((unit & 1) != 0)
3021 cost = potential_hazard (i, insn, cost);
3026 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3027 This is the number of cycles between instruction issue and
3028 instruction results. */
3031 insn_cost (insn, link, used)
3032 rtx insn, link, used;
3034 register int cost = INSN_COST (insn);
3038 recog_memoized (insn);
3040 /* A USE insn, or something else we don't need to understand.
3041 We can't pass these directly to result_ready_cost because it will
3042 trigger a fatal error for unrecognizable insns. */
3043 if (INSN_CODE (insn) < 0)
3045 INSN_COST (insn) = 1;
3050 cost = result_ready_cost (insn);
3055 INSN_COST (insn) = cost;
3059 /* in this case estimate cost without caring how insn is used. */
3060 if (link == 0 && used == 0)
3063 /* A USE insn should never require the value used to be computed. This
3064 allows the computation of a function's result and parameter values to
3065 overlap the return and call. */
3066 recog_memoized (used);
3067 if (INSN_CODE (used) < 0)
3068 LINK_COST_FREE (link) = 1;
3070 /* If some dependencies vary the cost, compute the adjustment. Most
3071 commonly, the adjustment is complete: either the cost is ignored
3072 (in the case of an output- or anti-dependence), or the cost is
3073 unchanged. These values are cached in the link as LINK_COST_FREE
3074 and LINK_COST_ZERO. */
3076 if (LINK_COST_FREE (link))
3079 else if (!LINK_COST_ZERO (link))
3083 ADJUST_COST (used, link, insn, ncost);
3085 LINK_COST_FREE (link) = ncost = 1;
3087 LINK_COST_ZERO (link) = 1;
3094 /* Compute the priority number for INSN. */
3103 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
3106 if ((this_priority = INSN_PRIORITY (insn)) == 0)
3108 if (INSN_DEPEND (insn) == 0)
3109 this_priority = insn_cost (insn, 0, 0);
3111 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
3116 if (RTX_INTEGRATED_P (link))
3119 next = XEXP (link, 0);
3121 /* critical path is meaningful in block boundaries only */
3122 if (INSN_BLOCK (next) != INSN_BLOCK (insn))
3125 next_priority = insn_cost (insn, link, next) + priority (next);
3126 if (next_priority > this_priority)
3127 this_priority = next_priority;
3129 INSN_PRIORITY (insn) = this_priority;
3131 return this_priority;
3135 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3136 them to the unused_*_list variables, so that they can be reused. */
3139 free_pending_lists ()
3141 if (current_nr_blocks <= 1)
3143 free_list (&pending_read_insns, &unused_insn_list);
3144 free_list (&pending_write_insns, &unused_insn_list);
3145 free_list (&pending_read_mems, &unused_expr_list);
3146 free_list (&pending_write_mems, &unused_expr_list);
3150 /* interblock scheduling */
3153 for (bb = 0; bb < current_nr_blocks; bb++)
3155 free_list (&bb_pending_read_insns[bb], &unused_insn_list);
3156 free_list (&bb_pending_write_insns[bb], &unused_insn_list);
3157 free_list (&bb_pending_read_mems[bb], &unused_expr_list);
3158 free_list (&bb_pending_write_mems[bb], &unused_expr_list);
3163 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3164 The MEM is a memory reference contained within INSN, which we are saving
3165 so that we can do memory aliasing on it. */
3168 add_insn_mem_dependence (insn_list, mem_list, insn, mem)
3169 rtx *insn_list, *mem_list, insn, mem;
3173 link = alloc_INSN_LIST (insn, *insn_list);
3176 link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
3179 pending_lists_length++;
3183 /* Make a dependency between every memory reference on the pending lists
3184 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3188 flush_pending_lists (insn, only_write)
3195 while (pending_read_insns && ! only_write)
3197 add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
3199 link = pending_read_insns;
3200 pending_read_insns = XEXP (pending_read_insns, 1);
3201 XEXP (link, 1) = unused_insn_list;
3202 unused_insn_list = link;
3204 link = pending_read_mems;
3205 pending_read_mems = XEXP (pending_read_mems, 1);
3206 XEXP (link, 1) = unused_expr_list;
3207 unused_expr_list = link;
3209 while (pending_write_insns)
3211 add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
3213 link = pending_write_insns;
3214 pending_write_insns = XEXP (pending_write_insns, 1);
3215 XEXP (link, 1) = unused_insn_list;
3216 unused_insn_list = link;
3218 link = pending_write_mems;
3219 pending_write_mems = XEXP (pending_write_mems, 1);
3220 XEXP (link, 1) = unused_expr_list;
3221 unused_expr_list = link;
3223 pending_lists_length = 0;
3225 /* last_pending_memory_flush is now a list of insns */
3226 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3227 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3229 free_list (&last_pending_memory_flush, &unused_insn_list);
3230 last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
3233 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
3234 by the write to the destination of X, and reads of everything mentioned. */
3237 sched_analyze_1 (x, insn)
3242 register rtx dest = SET_DEST (x);
3247 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3248 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3250 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3252 /* The second and third arguments are values read by this insn. */
3253 sched_analyze_2 (XEXP (dest, 1), insn);
3254 sched_analyze_2 (XEXP (dest, 2), insn);
3256 dest = SUBREG_REG (dest);
3259 if (GET_CODE (dest) == REG)
3263 regno = REGNO (dest);
3265 /* A hard reg in a wide mode may really be multiple registers.
3266 If so, mark all of them just like the first. */
3267 if (regno < FIRST_PSEUDO_REGISTER)
3269 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
3274 for (u = reg_last_uses[regno + i]; u; u = XEXP (u, 1))
3275 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3276 reg_last_uses[regno + i] = 0;
3278 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3279 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3281 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
3283 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3284 /* Function calls clobber all call_used regs. */
3285 for (u = last_function_call; u; u = XEXP (u, 1))
3286 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3293 for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
3294 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3295 reg_last_uses[regno] = 0;
3297 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3298 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3300 SET_REGNO_REG_SET (reg_pending_sets, regno);
3302 /* Pseudos that are REG_EQUIV to something may be replaced
3303 by that during reloading. We need only add dependencies for
3304 the address in the REG_EQUIV note. */
3305 if (!reload_completed
3306 && reg_known_equiv_p[regno]
3307 && GET_CODE (reg_known_value[regno]) == MEM)
3308 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3310 /* Don't let it cross a call after scheduling if it doesn't
3311 already cross one. */
3313 if (REG_N_CALLS_CROSSED (regno) == 0)
3314 for (u = last_function_call; u; u = XEXP (u, 1))
3315 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3318 else if (GET_CODE (dest) == MEM)
3320 /* Writing memory. */
3322 if (pending_lists_length > 32)
3324 /* Flush all pending reads and writes to prevent the pending lists
3325 from getting any larger. Insn scheduling runs too slowly when
3326 these lists get long. The number 32 was chosen because it
3327 seems like a reasonable number. When compiling GCC with itself,
3328 this flush occurs 8 times for sparc, and 10 times for m88k using
3330 flush_pending_lists (insn, 0);
3335 rtx pending, pending_mem;
3337 pending = pending_read_insns;
3338 pending_mem = pending_read_mems;
3341 /* If a dependency already exists, don't create a new one. */
3342 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3343 if (anti_dependence (XEXP (pending_mem, 0), dest))
3344 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3346 pending = XEXP (pending, 1);
3347 pending_mem = XEXP (pending_mem, 1);
3350 pending = pending_write_insns;
3351 pending_mem = pending_write_mems;
3354 /* If a dependency already exists, don't create a new one. */
3355 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3356 if (output_dependence (XEXP (pending_mem, 0), dest))
3357 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
3359 pending = XEXP (pending, 1);
3360 pending_mem = XEXP (pending_mem, 1);
3363 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3364 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3366 add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
3369 sched_analyze_2 (XEXP (dest, 0), insn);
3372 /* Analyze reads. */
3373 if (GET_CODE (x) == SET)
3374 sched_analyze_2 (SET_SRC (x), insn);
3377 /* Analyze the uses of memory and registers in rtx X in INSN. */
3380 sched_analyze_2 (x, insn)
3386 register enum rtx_code code;
3392 code = GET_CODE (x);
3401 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3402 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3403 this does not mean that this insn is using cc0. */
3411 /* User of CC0 depends on immediately preceding insn. */
3412 SCHED_GROUP_P (insn) = 1;
3414 /* There may be a note before this insn now, but all notes will
3415 be removed before we actually try to schedule the insns, so
3416 it won't cause a problem later. We must avoid it here though. */
3417 prev = prev_nonnote_insn (insn);
3419 /* Make a copy of all dependencies on the immediately previous insn,
3420 and add to this insn. This is so that all the dependencies will
3421 apply to the group. Remove an explicit dependence on this insn
3422 as SCHED_GROUP_P now represents it. */
3424 if (find_insn_list (prev, LOG_LINKS (insn)))
3425 remove_dependence (insn, prev);
3427 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
3428 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3437 int regno = REGNO (x);
3438 if (regno < FIRST_PSEUDO_REGISTER)
3442 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
3445 reg_last_uses[regno + i]
3446 = alloc_INSN_LIST (insn, reg_last_uses[regno + i]);
3448 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3449 add_dependence (insn, XEXP (u, 0), 0);
3451 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3452 /* Function calls clobber all call_used regs. */
3453 for (u = last_function_call; u; u = XEXP (u, 1))
3454 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3459 reg_last_uses[regno] = alloc_INSN_LIST (insn, reg_last_uses[regno]);
3461 for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3462 add_dependence (insn, XEXP (u, 0), 0);
3464 /* Pseudos that are REG_EQUIV to something may be replaced
3465 by that during reloading. We need only add dependencies for
3466 the address in the REG_EQUIV note. */
3467 if (!reload_completed
3468 && reg_known_equiv_p[regno]
3469 && GET_CODE (reg_known_value[regno]) == MEM)
3470 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3472 /* If the register does not already cross any calls, then add this
3473 insn to the sched_before_next_call list so that it will still
3474 not cross calls after scheduling. */
3475 if (REG_N_CALLS_CROSSED (regno) == 0)
3476 add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
3483 /* Reading memory. */
3485 rtx pending, pending_mem;
3487 pending = pending_read_insns;
3488 pending_mem = pending_read_mems;
3491 /* If a dependency already exists, don't create a new one. */
3492 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3493 if (read_dependence (XEXP (pending_mem, 0), x))
3494 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3496 pending = XEXP (pending, 1);
3497 pending_mem = XEXP (pending_mem, 1);
3500 pending = pending_write_insns;
3501 pending_mem = pending_write_mems;
3504 /* If a dependency already exists, don't create a new one. */
3505 if (!find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
3506 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
3508 add_dependence (insn, XEXP (pending, 0), 0);
3510 pending = XEXP (pending, 1);
3511 pending_mem = XEXP (pending_mem, 1);
3514 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3515 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3517 /* Always add these dependencies to pending_reads, since
3518 this insn may be followed by a write. */
3519 add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
3522 /* Take advantage of tail recursion here. */
3523 sched_analyze_2 (XEXP (x, 0), insn);
3529 case UNSPEC_VOLATILE:
3534 /* Traditional and volatile asm instructions must be considered to use
3535 and clobber all hard registers, all pseudo-registers and all of
3536 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3538 Consider for instance a volatile asm that changes the fpu rounding
3539 mode. An insn should not be moved across this even if it only uses
3540 pseudo-regs because it might give an incorrectly rounded result. */
3541 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
3543 int max_reg = max_reg_num ();
3544 for (i = 0; i < max_reg; i++)
3546 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3547 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3548 reg_last_uses[i] = 0;
3550 /* reg_last_sets[r] is now a list of insns */
3551 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3552 add_dependence (insn, XEXP (u, 0), 0);
3554 reg_pending_sets_all = 1;
3556 flush_pending_lists (insn, 0);
3559 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3560 We can not just fall through here since then we would be confused
3561 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3562 traditional asms unlike their normal usage. */
3564 if (code == ASM_OPERANDS)
3566 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3567 sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
3577 /* These both read and modify the result. We must handle them as writes
3578 to get proper dependencies for following instructions. We must handle
3579 them as reads to get proper dependencies from this to previous
3580 instructions. Thus we need to pass them to both sched_analyze_1
3581 and sched_analyze_2. We must call sched_analyze_2 first in order
3582 to get the proper antecedent for the read. */
3583 sched_analyze_2 (XEXP (x, 0), insn);
3584 sched_analyze_1 (x, insn);
3591 /* Other cases: walk the insn. */
3592 fmt = GET_RTX_FORMAT (code);
3593 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3596 sched_analyze_2 (XEXP (x, i), insn);
3597 else if (fmt[i] == 'E')
3598 for (j = 0; j < XVECLEN (x, i); j++)
3599 sched_analyze_2 (XVECEXP (x, i, j), insn);
3603 /* Analyze an INSN with pattern X to find all dependencies. */
3606 sched_analyze_insn (x, insn, loop_notes)
3610 register RTX_CODE code = GET_CODE (x);
3612 int maxreg = max_reg_num ();
3615 if (code == SET || code == CLOBBER)
3616 sched_analyze_1 (x, insn);
3617 else if (code == PARALLEL)
3620 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3622 code = GET_CODE (XVECEXP (x, 0, i));
3623 if (code == SET || code == CLOBBER)
3624 sched_analyze_1 (XVECEXP (x, 0, i), insn);
3626 sched_analyze_2 (XVECEXP (x, 0, i), insn);
3630 sched_analyze_2 (x, insn);
3632 /* Mark registers CLOBBERED or used by called function. */
3633 if (GET_CODE (insn) == CALL_INSN)
3634 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3636 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3637 sched_analyze_1 (XEXP (link, 0), insn);
3639 sched_analyze_2 (XEXP (link, 0), insn);
3642 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic block, then
3643 we must be sure that no instructions are scheduled across it.
3644 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3645 become incorrect. */
3649 int max_reg = max_reg_num ();
3652 for (i = 0; i < max_reg; i++)
3655 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3656 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3657 reg_last_uses[i] = 0;
3659 /* reg_last_sets[r] is now a list of insns */
3660 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3661 add_dependence (insn, XEXP (u, 0), 0);
3663 reg_pending_sets_all = 1;
3665 flush_pending_lists (insn, 0);
3668 while (XEXP (link, 1))
3669 link = XEXP (link, 1);
3670 XEXP (link, 1) = REG_NOTES (insn);
3671 REG_NOTES (insn) = loop_notes;
3674 /* After reload, it is possible for an instruction to have a REG_DEAD note
3675 for a register that actually dies a few instructions earlier. For
3676 example, this can happen with SECONDARY_MEMORY_NEEDED reloads.
3677 In this case, we must consider the insn to use the register mentioned
3678 in the REG_DEAD note. Otherwise, we may accidentally move this insn
3679 after another insn that sets the register, thus getting obviously invalid
3680 rtl. This confuses reorg which believes that REG_DEAD notes are still
3683 ??? We would get better code if we fixed reload to put the REG_DEAD
3684 notes in the right places, but that may not be worth the effort. */
3686 if (reload_completed)
3690 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3691 if (REG_NOTE_KIND (note) == REG_DEAD)
3692 sched_analyze_2 (XEXP (note, 0), insn);
3695 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
3697 /* reg_last_sets[r] is now a list of insns */
3698 free_list (®_last_sets[i], &unused_insn_list);
3700 = alloc_INSN_LIST (insn, NULL_RTX);
3702 CLEAR_REG_SET (reg_pending_sets);
3704 if (reg_pending_sets_all)
3706 for (i = 0; i < maxreg; i++)
3708 /* reg_last_sets[r] is now a list of insns */
3709 free_list (®_last_sets[i], &unused_insn_list);
3710 reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3713 reg_pending_sets_all = 0;
3716 /* Handle function calls and function returns created by the epilogue
3718 if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
3723 /* When scheduling instructions, we make sure calls don't lose their
3724 accompanying USE insns by depending them one on another in order.
3726 Also, we must do the same thing for returns created by the epilogue
3727 threading code. Note this code works only in this special case,
3728 because other passes make no guarantee that they will never emit
3729 an instruction between a USE and a RETURN. There is such a guarantee
3730 for USE instructions immediately before a call. */
3732 prev_dep_insn = insn;
3733 dep_insn = PREV_INSN (insn);
3734 while (GET_CODE (dep_insn) == INSN
3735 && GET_CODE (PATTERN (dep_insn)) == USE
3736 && GET_CODE (XEXP (PATTERN (dep_insn), 0)) == REG)
3738 SCHED_GROUP_P (prev_dep_insn) = 1;
3740 /* Make a copy of all dependencies on dep_insn, and add to insn.
3741 This is so that all of the dependencies will apply to the
3744 for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
3745 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3747 prev_dep_insn = dep_insn;
3748 dep_insn = PREV_INSN (dep_insn);
3753 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3754 for every dependency. */
3757 sched_analyze (head, tail)
3764 for (insn = head;; insn = NEXT_INSN (insn))
3766 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
3768 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3771 else if (GET_CODE (insn) == CALL_INSN)
3776 CANT_MOVE (insn) = 1;
3778 /* Any instruction using a hard register which may get clobbered
3779 by a call needs to be marked as dependent on this call.
3780 This prevents a use of a hard return reg from being moved
3781 past a void call (i.e. it does not explicitly set the hard
3784 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3785 all registers, not just hard registers, may be clobbered by this
3788 /* Insn, being a CALL_INSN, magically depends on
3789 `last_function_call' already. */
3791 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
3792 && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
3794 int max_reg = max_reg_num ();
3795 for (i = 0; i < max_reg; i++)
3797 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3798 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3800 reg_last_uses[i] = 0;
3802 /* reg_last_sets[r] is now a list of insns */
3803 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3804 add_dependence (insn, XEXP (u, 0), 0);
3806 reg_pending_sets_all = 1;
3808 /* Add a pair of fake REG_NOTE which we will later
3809 convert back into a NOTE_INSN_SETJMP note. See
3810 reemit_notes for why we use a pair of NOTEs. */
3811 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3814 REG_NOTES (insn) = alloc_EXPR_LIST (REG_DEAD,
3815 GEN_INT (NOTE_INSN_SETJMP),
3820 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3821 if (call_used_regs[i] || global_regs[i])
3823 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3824 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3825 reg_last_uses[i] = 0;
3827 /* reg_last_sets[r] is now a list of insns */
3828 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3829 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3831 SET_REGNO_REG_SET (reg_pending_sets, i);
3835 /* For each insn which shouldn't cross a call, add a dependence
3836 between that insn and this call insn. */
3837 x = LOG_LINKS (sched_before_next_call);
3840 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
3843 LOG_LINKS (sched_before_next_call) = 0;
3845 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3848 /* In the absence of interprocedural alias analysis, we must flush
3849 all pending reads and writes, and start new dependencies starting
3850 from here. But only flush writes for constant calls (which may
3851 be passed a pointer to something we haven't written yet). */
3852 flush_pending_lists (insn, CONST_CALL_P (insn));
3854 /* Depend this function call (actually, the user of this
3855 function call) on all hard register clobberage. */
3857 /* last_function_call is now a list of insns */
3858 free_list(&last_function_call, &unused_insn_list);
3859 last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3862 /* See comments on reemit_notes as to why we do this. */
3863 else if (GET_CODE (insn) == NOTE
3864 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
3865 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
3866 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
3867 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
3868 || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
3869 && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
3871 loop_notes = alloc_EXPR_LIST (REG_DEAD,
3872 GEN_INT (NOTE_BLOCK_NUMBER (insn)),
3874 loop_notes = alloc_EXPR_LIST (REG_DEAD,
3875 GEN_INT (NOTE_LINE_NUMBER (insn)),
3877 CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
3886 /* Called when we see a set of a register. If death is true, then we are
3887 scanning backwards. Mark that register as unborn. If nobody says
3888 otherwise, that is how things will remain. If death is false, then we
3889 are scanning forwards. Mark that register as being born. */
3892 sched_note_set (x, death)
3897 register rtx reg = SET_DEST (x);
3903 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
3904 || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
3906 /* Must treat modification of just one hardware register of a multi-reg
3907 value or just a byte field of a register exactly the same way that
3908 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
3909 does not kill the entire register. */
3910 if (GET_CODE (reg) != SUBREG
3911 || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
3914 reg = SUBREG_REG (reg);
3917 if (GET_CODE (reg) != REG)
3920 /* Global registers are always live, so the code below does not apply
3923 regno = REGNO (reg);
3924 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
3928 /* If we only set part of the register, then this set does not
3933 /* Try killing this register. */
3934 if (regno < FIRST_PSEUDO_REGISTER)
3936 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
3939 CLEAR_REGNO_REG_SET (bb_live_regs, regno + j);
3944 /* Recompute REG_BASIC_BLOCK as we update all the other
3945 dataflow information. */
3946 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
3947 sched_reg_basic_block[regno] = current_block_num;
3948 else if (sched_reg_basic_block[regno] != current_block_num)
3949 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
3951 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
3956 /* Make the register live again. */
3957 if (regno < FIRST_PSEUDO_REGISTER)
3959 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
3962 SET_REGNO_REG_SET (bb_live_regs, regno + j);
3967 SET_REGNO_REG_SET (bb_live_regs, regno);
3973 /* Macros and functions for keeping the priority queue sorted, and
3974 dealing with queueing and dequeueing of instructions. */
3976 #define SCHED_SORT(READY, N_READY) \
3977 do { if ((N_READY) == 2) \
3978 swap_sort (READY, N_READY); \
3979 else if ((N_READY) > 2) \
3980 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
3983 /* Returns a positive value if x is preferred; returns a negative value if
3984 y is preferred. Should never return 0, since that will make the sort
3988 rank_for_schedule (x, y)
3989 const GENERIC_PTR x;
3990 const GENERIC_PTR y;
3992 rtx tmp = *(rtx *)y;
3993 rtx tmp2 = *(rtx *)x;
3995 int tmp_class, tmp2_class;
3996 int val, priority_val, spec_val, prob_val, weight_val;
3999 /* prefer insn with higher priority */
4000 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
4002 return priority_val;
4004 /* prefer an insn with smaller contribution to registers-pressure */
4005 if (!reload_completed &&
4006 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
4007 return (weight_val);
4009 /* some comparison make sense in interblock scheduling only */
4010 if (INSN_BB (tmp) != INSN_BB (tmp2))
4012 /* prefer an inblock motion on an interblock motion */
4013 if ((INSN_BB (tmp2) == target_bb) && (INSN_BB (tmp) != target_bb))
4015 if ((INSN_BB (tmp) == target_bb) && (INSN_BB (tmp2) != target_bb))
4018 /* prefer a useful motion on a speculative one */
4019 if ((spec_val = IS_SPECULATIVE_INSN (tmp) - IS_SPECULATIVE_INSN (tmp2)))
4022 /* prefer a more probable (speculative) insn */
4023 prob_val = INSN_PROBABILITY (tmp2) - INSN_PROBABILITY (tmp);
4028 /* compare insns based on their relation to the last-scheduled-insn */
4029 if (last_scheduled_insn)
4031 /* Classify the instructions into three classes:
4032 1) Data dependent on last schedule insn.
4033 2) Anti/Output dependent on last scheduled insn.
4034 3) Independent of last scheduled insn, or has latency of one.
4035 Choose the insn from the highest numbered class if different. */
4036 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
4037 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
4039 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4044 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
4045 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
4047 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
4052 if ((val = tmp2_class - tmp_class))
4056 /* If insns are equally good, sort by INSN_LUID (original insn order),
4057 so that we make the sort stable. This minimizes instruction movement,
4058 thus minimizing sched's effect on debugging and cross-jumping. */
4059 return INSN_LUID (tmp) - INSN_LUID (tmp2);
4062 /* Resort the array A in which only element at index N may be out of order. */
4064 __inline static void
4069 rtx insn = a[n - 1];
4072 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
4080 static int max_priority;
4082 /* Add INSN to the insn queue so that it can be executed at least
4083 N_CYCLES after the currently executing insn. Preserve insns
4084 chain for debugging purposes. */
4086 __inline static void
4087 queue_insn (insn, n_cycles)
4091 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
4092 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
4093 insn_queue[next_q] = link;
4096 if (sched_verbose >= 2)
4098 fprintf (dump, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn));
4100 if (INSN_BB (insn) != target_bb)
4101 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
4103 fprintf (dump, "queued for %d cycles.\n", n_cycles);
4108 /* Return nonzero if PAT is the pattern of an insn which makes a
4112 birthing_insn_p (pat)
4117 if (reload_completed == 1)
4120 if (GET_CODE (pat) == SET
4121 && GET_CODE (SET_DEST (pat)) == REG)
4123 rtx dest = SET_DEST (pat);
4124 int i = REGNO (dest);
4126 /* It would be more accurate to use refers_to_regno_p or
4127 reg_mentioned_p to determine when the dest is not live before this
4130 if (REGNO_REG_SET_P (bb_live_regs, i))
4131 return (REG_N_SETS (i) == 1);
4135 if (GET_CODE (pat) == PARALLEL)
4137 for (j = 0; j < XVECLEN (pat, 0); j++)
4138 if (birthing_insn_p (XVECEXP (pat, 0, j)))
4144 /* PREV is an insn that is ready to execute. Adjust its priority if that
4145 will help shorten register lifetimes. */
4147 __inline static void
4148 adjust_priority (prev)
4151 /* Trying to shorten register lives after reload has completed
4152 is useless and wrong. It gives inaccurate schedules. */
4153 if (reload_completed == 0)
4158 /* ??? This code has no effect, because REG_DEAD notes are removed
4159 before we ever get here. */
4160 for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
4161 if (REG_NOTE_KIND (note) == REG_DEAD)
4164 /* Defer scheduling insns which kill registers, since that
4165 shortens register lives. Prefer scheduling insns which
4166 make registers live for the same reason. */
4170 INSN_PRIORITY (prev) >>= 3;
4173 INSN_PRIORITY (prev) >>= 2;
4177 INSN_PRIORITY (prev) >>= 1;
4180 if (birthing_insn_p (PATTERN (prev)))
4182 int max = max_priority;
4184 if (max > INSN_PRIORITY (prev))
4185 INSN_PRIORITY (prev) = max;
4189 #ifdef ADJUST_PRIORITY
4190 ADJUST_PRIORITY (prev);
4195 /* INSN is the "currently executing insn". Launch each insn which was
4196 waiting on INSN. READY is a vector of insns which are ready to fire.
4197 N_READY is the number of elements in READY. CLOCK is the current
4201 schedule_insn (insn, ready, n_ready, clock)
4210 unit = insn_unit (insn);
4212 if (sched_verbose >= 2)
4214 fprintf (dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ", INSN_UID (insn));
4215 insn_print_units (insn);
4216 fprintf (dump, "\n");
4219 if (sched_verbose && unit == -1)
4220 visualize_no_unit (insn);
4222 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
4223 schedule_unit (unit, insn, clock);
4225 if (INSN_DEPEND (insn) == 0)
4228 /* This is used by the function adjust_priority above. */
4230 max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
4232 max_priority = INSN_PRIORITY (insn);
4234 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
4236 rtx next = XEXP (link, 0);
4237 int cost = insn_cost (insn, link, next);
4239 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
4241 if ((INSN_DEP_COUNT (next) -= 1) == 0)
4243 int effective_cost = INSN_TICK (next) - clock;
4245 /* For speculative insns, before inserting to ready/queue,
4246 check live, exception-free, and issue-delay */
4247 if (INSN_BB (next) != target_bb
4248 && (!IS_VALID (INSN_BB (next))
4250 || (IS_SPECULATIVE_INSN (next)
4251 && (insn_issue_delay (next) > 3
4252 || !check_live (next, INSN_BB (next))
4253 || !is_exception_free (next, INSN_BB (next), target_bb)))))
4256 if (sched_verbose >= 2)
4258 fprintf (dump, ";;\t\tdependences resolved: insn %d ", INSN_UID (next));
4260 if (current_nr_blocks > 1 && INSN_BB (next) != target_bb)
4261 fprintf (dump, "/b%d ", INSN_BLOCK (next));
4263 if (effective_cost <= 1)
4264 fprintf (dump, "into ready\n");
4266 fprintf (dump, "into queue with cost=%d\n", effective_cost);
4269 /* Adjust the priority of NEXT and either put it on the ready
4270 list or queue it. */
4271 adjust_priority (next);
4272 if (effective_cost <= 1)
4273 ready[n_ready++] = next;
4275 queue_insn (next, effective_cost);
4283 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4287 create_reg_dead_note (reg, insn)
4292 /* The number of registers killed after scheduling must be the same as the
4293 number of registers killed before scheduling. The number of REG_DEAD
4294 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4295 might become one DImode hard register REG_DEAD note, but the number of
4296 registers killed will be conserved.
4298 We carefully remove REG_DEAD notes from the dead_notes list, so that
4299 there will be none left at the end. If we run out early, then there
4300 is a bug somewhere in flow, combine and/or sched. */
4302 if (dead_notes == 0)
4304 if (current_nr_blocks <= 1)
4307 link = alloc_EXPR_LIST (REG_DEAD, NULL_RTX, NULL_RTX);
4311 /* Number of regs killed by REG. */
4312 int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
4313 : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
4314 /* Number of regs killed by REG_DEAD notes taken off the list. */
4318 reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4319 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4320 GET_MODE (XEXP (link, 0))));
4321 while (reg_note_regs < regs_killed)
4323 link = XEXP (link, 1);
4325 /* LINK might be zero if we killed more registers after scheduling
4326 than before, and the last hard register we kill is actually
4329 This is normal for interblock scheduling, so deal with it in
4330 that case, else abort. */
4331 if (link == NULL_RTX && current_nr_blocks <= 1)
4333 else if (link == NULL_RTX)
4334 link = alloc_EXPR_LIST (REG_DEAD, gen_rtx_REG (word_mode, 0),
4337 reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
4338 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
4339 GET_MODE (XEXP (link, 0))));
4341 dead_notes = XEXP (link, 1);
4343 /* If we took too many regs kills off, put the extra ones back. */
4344 while (reg_note_regs > regs_killed)
4346 rtx temp_reg, temp_link;
4348 temp_reg = gen_rtx_REG (word_mode, 0);
4349 temp_link = alloc_EXPR_LIST (REG_DEAD, temp_reg, dead_notes);
4350 dead_notes = temp_link;
4355 XEXP (link, 0) = reg;
4356 XEXP (link, 1) = REG_NOTES (insn);
4357 REG_NOTES (insn) = link;
4360 /* Subroutine on attach_deaths_insn--handles the recursive search
4361 through INSN. If SET_P is true, then x is being modified by the insn. */
4364 attach_deaths (x, insn, set_p)
4371 register enum rtx_code code;
4377 code = GET_CODE (x);
4389 /* Get rid of the easy cases first. */
4394 /* If the register dies in this insn, queue that note, and mark
4395 this register as needing to die. */
4396 /* This code is very similar to mark_used_1 (if set_p is false)
4397 and mark_set_1 (if set_p is true) in flow.c. */
4407 all_needed = some_needed = REGNO_REG_SET_P (old_live_regs, regno);
4408 if (regno < FIRST_PSEUDO_REGISTER)
4412 n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4415 int needed = (REGNO_REG_SET_P (old_live_regs, regno + n));
4416 some_needed |= needed;
4417 all_needed &= needed;
4421 /* If it wasn't live before we started, then add a REG_DEAD note.
4422 We must check the previous lifetime info not the current info,
4423 because we may have to execute this code several times, e.g.
4424 once for a clobber (which doesn't add a note) and later
4425 for a use (which does add a note).
4427 Always make the register live. We must do this even if it was
4428 live before, because this may be an insn which sets and uses
4429 the same register, in which case the register has already been
4430 killed, so we must make it live again.
4432 Global registers are always live, and should never have a REG_DEAD
4433 note added for them, so none of the code below applies to them. */
4435 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
4437 /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
4438 STACK_POINTER_REGNUM, since these are always considered to be
4439 live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
4440 if (regno != FRAME_POINTER_REGNUM
4441 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4442 && ! (regno == HARD_FRAME_POINTER_REGNUM)
4444 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4445 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
4447 && regno != STACK_POINTER_REGNUM)
4449 if (! all_needed && ! dead_or_set_p (insn, x))
4451 /* Check for the case where the register dying partially
4452 overlaps the register set by this insn. */
4453 if (regno < FIRST_PSEUDO_REGISTER
4454 && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
4456 int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4458 some_needed |= dead_or_set_regno_p (insn, regno + n);
4461 /* If none of the words in X is needed, make a REG_DEAD
4462 note. Otherwise, we must make partial REG_DEAD
4465 create_reg_dead_note (x, insn);
4470 /* Don't make a REG_DEAD note for a part of a
4471 register that is set in the insn. */
4472 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
4474 if (! REGNO_REG_SET_P (old_live_regs, regno+i)
4475 && ! dead_or_set_regno_p (insn, regno + i))
4476 create_reg_dead_note (gen_rtx_REG (reg_raw_mode[regno + i],
4483 if (regno < FIRST_PSEUDO_REGISTER)
4485 int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
4488 SET_REGNO_REG_SET (bb_live_regs, regno + j);
4493 /* Recompute REG_BASIC_BLOCK as we update all the other
4494 dataflow information. */
4495 if (sched_reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
4496 sched_reg_basic_block[regno] = current_block_num;
4497 else if (sched_reg_basic_block[regno] != current_block_num)
4498 sched_reg_basic_block[regno] = REG_BLOCK_GLOBAL;
4500 SET_REGNO_REG_SET (bb_live_regs, regno);
4507 /* Handle tail-recursive case. */
4508 attach_deaths (XEXP (x, 0), insn, 0);
4512 attach_deaths (SUBREG_REG (x), insn,
4513 set_p && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4515 || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
4516 == GET_MODE_SIZE (GET_MODE ((x))))));
4519 case STRICT_LOW_PART:
4520 attach_deaths (XEXP (x, 0), insn, 0);
4525 attach_deaths (XEXP (x, 0), insn, 0);
4526 attach_deaths (XEXP (x, 1), insn, 0);
4527 attach_deaths (XEXP (x, 2), insn, 0);
4531 /* Other cases: walk the insn. */
4532 fmt = GET_RTX_FORMAT (code);
4533 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4536 attach_deaths (XEXP (x, i), insn, 0);
4537 else if (fmt[i] == 'E')
4538 for (j = 0; j < XVECLEN (x, i); j++)
4539 attach_deaths (XVECEXP (x, i, j), insn, 0);
4544 /* After INSN has executed, add register death notes for each register
4545 that is dead after INSN. */
4548 attach_deaths_insn (insn)
4551 rtx x = PATTERN (insn);
4552 register RTX_CODE code = GET_CODE (x);
4557 attach_deaths (SET_SRC (x), insn, 0);
4559 /* A register might die here even if it is the destination, e.g.
4560 it is the target of a volatile read and is otherwise unused.
4561 Hence we must always call attach_deaths for the SET_DEST. */
4562 attach_deaths (SET_DEST (x), insn, 1);
4564 else if (code == PARALLEL)
4567 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4569 code = GET_CODE (XVECEXP (x, 0, i));
4572 attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
4574 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
4576 /* Flow does not add REG_DEAD notes to registers that die in
4577 clobbers, so we can't either. */
4578 else if (code != CLOBBER)
4579 attach_deaths (XVECEXP (x, 0, i), insn, 0);
4582 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4583 MEM being clobbered, just like flow. */
4584 else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == MEM)
4585 attach_deaths (XEXP (XEXP (x, 0), 0), insn, 0);
4586 /* Otherwise don't add a death note to things being clobbered. */
4587 else if (code != CLOBBER)
4588 attach_deaths (x, insn, 0);
4590 /* Make death notes for things used in the called function. */
4591 if (GET_CODE (insn) == CALL_INSN)
4592 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
4593 attach_deaths (XEXP (XEXP (link, 0), 0), insn,
4594 GET_CODE (XEXP (link, 0)) == CLOBBER);
4597 /* functions for handlnig of notes */
4599 /* Delete notes beginning with INSN and put them in the chain
4600 of notes ended by NOTE_LIST.
4601 Returns the insn following the notes. */
4604 unlink_other_notes (insn, tail)
4607 rtx prev = PREV_INSN (insn);
4609 while (insn != tail && GET_CODE (insn) == NOTE)
4611 rtx next = NEXT_INSN (insn);
4612 /* Delete the note from its current position. */
4614 NEXT_INSN (prev) = next;
4616 PREV_INSN (next) = prev;
4618 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4619 immediately after the call they follow. We use a fake
4620 (REG_DEAD (const_int -1)) note to remember them.
4621 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4622 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
4623 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
4624 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
4625 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
4626 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
4628 /* Insert the note at the end of the notes list. */
4629 PREV_INSN (insn) = note_list;
4631 NEXT_INSN (note_list) = insn;
4640 /* Delete line notes beginning with INSN. Record line-number notes so
4641 they can be reused. Returns the insn following the notes. */
4644 unlink_line_notes (insn, tail)
4647 rtx prev = PREV_INSN (insn);
4649 while (insn != tail && GET_CODE (insn) == NOTE)
4651 rtx next = NEXT_INSN (insn);
4653 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
4655 /* Delete the note from its current position. */
4657 NEXT_INSN (prev) = next;
4659 PREV_INSN (next) = prev;
4661 /* Record line-number notes so they can be reused. */
4662 LINE_NOTE (insn) = insn;
4672 /* Return the head and tail pointers of BB. */
4674 __inline static void
4675 get_block_head_tail (bb, headp, tailp)
4685 b = BB_TO_BLOCK (bb);
4687 /* HEAD and TAIL delimit the basic block being scheduled. */
4688 head = basic_block_head[b];
4689 tail = basic_block_end[b];
4691 /* Don't include any notes or labels at the beginning of the
4692 basic block, or notes at the ends of basic blocks. */
4693 while (head != tail)
4695 if (GET_CODE (head) == NOTE)
4696 head = NEXT_INSN (head);
4697 else if (GET_CODE (tail) == NOTE)
4698 tail = PREV_INSN (tail);
4699 else if (GET_CODE (head) == CODE_LABEL)
4700 head = NEXT_INSN (head);
4709 /* Delete line notes from bb. Save them so they can be later restored
4710 (in restore_line_notes ()). */
4721 get_block_head_tail (bb, &head, &tail);
4724 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4727 next_tail = NEXT_INSN (tail);
4728 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4732 /* Farm out notes, and maybe save them in NOTE_LIST.
4733 This is needed to keep the debugger from
4734 getting completely deranged. */
4735 if (GET_CODE (insn) == NOTE)
4738 insn = unlink_line_notes (insn, next_tail);
4744 if (insn == next_tail)
4750 /* Save line number notes for each insn in bb. */
4753 save_line_notes (bb)
4759 /* We must use the true line number for the first insn in the block
4760 that was computed and saved at the start of this pass. We can't
4761 use the current line number, because scheduling of the previous
4762 block may have changed the current line number. */
4764 rtx line = line_note_head[BB_TO_BLOCK (bb)];
4767 get_block_head_tail (bb, &head, &tail);
4768 next_tail = NEXT_INSN (tail);
4770 for (insn = basic_block_head[BB_TO_BLOCK (bb)];
4772 insn = NEXT_INSN (insn))
4773 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4776 LINE_NOTE (insn) = line;
4780 /* After bb was scheduled, insert line notes into the insns list. */
4783 restore_line_notes (bb)
4786 rtx line, note, prev, new;
4787 int added_notes = 0;
4789 rtx head, next_tail, insn;
4791 b = BB_TO_BLOCK (bb);
4793 head = basic_block_head[b];
4794 next_tail = NEXT_INSN (basic_block_end[b]);
4796 /* Determine the current line-number. We want to know the current
4797 line number of the first insn of the block here, in case it is
4798 different from the true line number that was saved earlier. If
4799 different, then we need a line number note before the first insn
4800 of this block. If it happens to be the same, then we don't want to
4801 emit another line number note here. */
4802 for (line = head; line; line = PREV_INSN (line))
4803 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4806 /* Walk the insns keeping track of the current line-number and inserting
4807 the line-number notes as needed. */
4808 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4809 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4811 /* This used to emit line number notes before every non-deleted note.
4812 However, this confuses a debugger, because line notes not separated
4813 by real instructions all end up at the same address. I can find no
4814 use for line number notes before other notes, so none are emitted. */
4815 else if (GET_CODE (insn) != NOTE
4816 && (note = LINE_NOTE (insn)) != 0
4819 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
4820 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
4823 prev = PREV_INSN (insn);
4824 if (LINE_NOTE (note))
4826 /* Re-use the original line-number note. */
4827 LINE_NOTE (note) = 0;
4828 PREV_INSN (note) = prev;
4829 NEXT_INSN (prev) = note;
4830 PREV_INSN (insn) = note;
4831 NEXT_INSN (note) = insn;
4836 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
4837 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
4838 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
4841 if (sched_verbose && added_notes)
4842 fprintf (dump, ";; added %d line-number notes\n", added_notes);
4845 /* After scheduling the function, delete redundant line notes from the
4849 rm_redundant_line_notes ()
4852 rtx insn = get_insns ();
4853 int active_insn = 0;
4856 /* Walk the insns deleting redundant line-number notes. Many of these
4857 are already present. The remainder tend to occur at basic
4858 block boundaries. */
4859 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4860 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4862 /* If there are no active insns following, INSN is redundant. */
4863 if (active_insn == 0)
4866 NOTE_SOURCE_FILE (insn) = 0;
4867 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4869 /* If the line number is unchanged, LINE is redundant. */
4871 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
4872 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
4875 NOTE_SOURCE_FILE (line) = 0;
4876 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
4883 else if (!((GET_CODE (insn) == NOTE
4884 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
4885 || (GET_CODE (insn) == INSN
4886 && (GET_CODE (PATTERN (insn)) == USE
4887 || GET_CODE (PATTERN (insn)) == CLOBBER))))
4890 if (sched_verbose && notes)
4891 fprintf (dump, ";; deleted %d line-number notes\n", notes);
4894 /* Delete notes between head and tail and put them in the chain
4895 of notes ended by NOTE_LIST. */
4898 rm_other_notes (head, tail)
4906 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4909 next_tail = NEXT_INSN (tail);
4910 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4914 /* Farm out notes, and maybe save them in NOTE_LIST.
4915 This is needed to keep the debugger from
4916 getting completely deranged. */
4917 if (GET_CODE (insn) == NOTE)
4921 insn = unlink_other_notes (insn, next_tail);
4927 if (insn == next_tail)
4933 /* Constructor for `sometimes' data structure. */
4936 new_sometimes_live (regs_sometimes_live, regno, sometimes_max)
4937 struct sometimes *regs_sometimes_live;
4941 register struct sometimes *p;
4943 /* There should never be a register greater than max_regno here. If there
4944 is, it means that a define_split has created a new pseudo reg. This
4945 is not allowed, since there will not be flow info available for any
4946 new register, so catch the error here. */
4947 if (regno >= max_regno)
4950 p = ®s_sometimes_live[sometimes_max];
4953 p->calls_crossed = 0;
4955 return sometimes_max;
4958 /* Count lengths of all regs we are currently tracking,
4959 and find new registers no longer live. */
4962 finish_sometimes_live (regs_sometimes_live, sometimes_max)
4963 struct sometimes *regs_sometimes_live;
4968 for (i = 0; i < sometimes_max; i++)
4970 register struct sometimes *p = ®s_sometimes_live[i];
4971 int regno = p->regno;
4973 sched_reg_live_length[regno] += p->live_length;
4974 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
4978 /* functions for computation of registers live/usage info */
4980 /* It is assumed that prior to scheduling basic_block_live_at_start (b)
4981 contains the registers that are alive at the entry to b.
4983 Two passes follow: The first pass is performed before the scheduling
4984 of a region. It scans each block of the region forward, computing
4985 the set of registers alive at the end of the basic block and
4986 discard REG_DEAD notes (done by find_pre_sched_live ()).
4988 The second path is invoked after scheduling all region blocks.
4989 It scans each block of the region backward, a block being traversed
4990 only after its succesors in the region. When the set of registers
4991 live at the end of a basic block may be changed by the scheduling
4992 (this may happen for multiple blocks region), it is computed as
4993 the union of the registers live at the start of its succesors.
4994 The last-use information is updated by inserting REG_DEAD notes.
4995 (done by find_post_sched_live ()) */
4997 /* Scan all the insns to be scheduled, removing register death notes.
4998 Register death notes end up in DEAD_NOTES.
4999 Recreate the register life information for the end of this basic
5003 find_pre_sched_live (bb)
5006 rtx insn, next_tail, head, tail;
5007 int b = BB_TO_BLOCK (bb);
5009 get_block_head_tail (bb, &head, &tail);
5010 COPY_REG_SET (bb_live_regs, basic_block_live_at_start[b]);
5011 next_tail = NEXT_INSN (tail);
5013 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5015 rtx prev, next, link;
5018 /* Handle register life information. */
5019 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
5021 /* See if the register gets born here. */
5022 /* We must check for registers being born before we check for
5023 registers dying. It is possible for a register to be born and
5024 die in the same insn, e.g. reading from a volatile memory
5025 location into an otherwise unused register. Such a register
5026 must be marked as dead after this insn. */
5027 if (GET_CODE (PATTERN (insn)) == SET
5028 || GET_CODE (PATTERN (insn)) == CLOBBER)
5030 sched_note_set (PATTERN (insn), 0);
5034 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5037 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5038 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5039 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5041 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5045 /* ??? This code is obsolete and should be deleted. It
5046 is harmless though, so we will leave it in for now. */
5047 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5048 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
5049 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
5052 /* Each call cobbers (makes live) all call-clobbered regs
5053 that are not global or fixed. Note that the function-value
5054 reg is a call_clobbered reg. */
5055 if (GET_CODE (insn) == CALL_INSN)
5058 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
5059 if (call_used_regs[j] && !global_regs[j]
5062 SET_REGNO_REG_SET (bb_live_regs, j);
5066 /* Need to know what registers this insn kills. */
5067 for (prev = 0, link = REG_NOTES (insn); link; link = next)
5069 next = XEXP (link, 1);
5070 if ((REG_NOTE_KIND (link) == REG_DEAD
5071 || REG_NOTE_KIND (link) == REG_UNUSED)
5072 /* Verify that the REG_NOTE has a valid value. */
5073 && GET_CODE (XEXP (link, 0)) == REG)
5075 register int regno = REGNO (XEXP (link, 0));
5079 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5081 if (REG_NOTE_KIND (link) == REG_DEAD)
5084 XEXP (prev, 1) = next;
5086 REG_NOTES (insn) = next;
5087 XEXP (link, 1) = dead_notes;
5093 if (regno < FIRST_PSEUDO_REGISTER)
5095 int j = HARD_REGNO_NREGS (regno,
5096 GET_MODE (XEXP (link, 0)));
5099 CLEAR_REGNO_REG_SET (bb_live_regs, regno+j);
5104 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
5112 INSN_REG_WEIGHT (insn) = reg_weight;
5116 /* Update register life and usage information for block bb
5117 after scheduling. Put register dead notes back in the code. */
5120 find_post_sched_live (bb)
5127 rtx head, tail, prev_head, next_tail;
5129 register struct sometimes *regs_sometimes_live;
5131 b = BB_TO_BLOCK (bb);
5133 /* compute live regs at the end of bb as a function of its successors. */
5134 if (current_nr_blocks > 1)
5139 first_edge = e = OUT_EDGES (b);
5140 CLEAR_REG_SET (bb_live_regs);
5147 b_succ = TO_BLOCK (e);
5148 IOR_REG_SET (bb_live_regs, basic_block_live_at_start[b_succ]);
5151 while (e != first_edge);
5154 get_block_head_tail (bb, &head, &tail);
5155 next_tail = NEXT_INSN (tail);
5156 prev_head = PREV_INSN (head);
5158 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, i,
5160 sched_reg_basic_block[i] = REG_BLOCK_GLOBAL;
5163 /* if the block is empty, same regs are alive at its end and its start.
5164 since this is not guaranteed after interblock scheduling, make sure they
5165 are truly identical. */
5166 if (NEXT_INSN (prev_head) == tail
5167 && (GET_RTX_CLASS (GET_CODE (tail)) != 'i'))
5169 if (current_nr_blocks > 1)
5170 COPY_REG_SET (basic_block_live_at_start[b], bb_live_regs);
5175 b = BB_TO_BLOCK (bb);
5176 current_block_num = b;
5178 /* Keep track of register lives. */
5179 old_live_regs = ALLOCA_REG_SET ();
5181 = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
5184 /* initiate "sometimes" data, starting with registers live at end */
5186 COPY_REG_SET (old_live_regs, bb_live_regs);
5187 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, 0, j,
5190 = new_sometimes_live (regs_sometimes_live,
5194 /* scan insns back, computing regs live info */
5195 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
5197 /* First we kill registers set by this insn, and then we
5198 make registers used by this insn live. This is the opposite
5199 order used above because we are traversing the instructions
5202 /* Strictly speaking, we should scan REG_UNUSED notes and make
5203 every register mentioned there live, however, we will just
5204 kill them again immediately below, so there doesn't seem to
5205 be any reason why we bother to do this. */
5207 /* See if this is the last notice we must take of a register. */
5208 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5211 if (GET_CODE (PATTERN (insn)) == SET
5212 || GET_CODE (PATTERN (insn)) == CLOBBER)
5213 sched_note_set (PATTERN (insn), 1);
5214 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
5216 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
5217 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
5218 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
5219 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 1);
5222 /* This code keeps life analysis information up to date. */
5223 if (GET_CODE (insn) == CALL_INSN)
5225 register struct sometimes *p;
5227 /* A call kills all call used registers that are not
5228 global or fixed, except for those mentioned in the call
5229 pattern which will be made live again later. */
5230 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5231 if (call_used_regs[i] && ! global_regs[i]
5234 CLEAR_REGNO_REG_SET (bb_live_regs, i);
5237 /* Regs live at the time of a call instruction must not
5238 go in a register clobbered by calls. Record this for
5239 all regs now live. Note that insns which are born or
5240 die in a call do not cross a call, so this must be done
5241 after the killings (above) and before the births
5243 p = regs_sometimes_live;
5244 for (i = 0; i < sometimes_max; i++, p++)
5245 if (REGNO_REG_SET_P (bb_live_regs, p->regno))
5246 p->calls_crossed += 1;
5249 /* Make every register used live, and add REG_DEAD notes for
5250 registers which were not live before we started. */
5251 attach_deaths_insn (insn);
5253 /* Find registers now made live by that instruction. */
5254 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs, old_live_regs, 0, j,
5257 = new_sometimes_live (regs_sometimes_live,
5260 IOR_REG_SET (old_live_regs, bb_live_regs);
5262 /* Count lengths of all regs we are worrying about now,
5263 and handle registers no longer live. */
5265 for (i = 0; i < sometimes_max; i++)
5267 register struct sometimes *p = ®s_sometimes_live[i];
5268 int regno = p->regno;
5270 p->live_length += 1;
5272 if (!REGNO_REG_SET_P (bb_live_regs, regno))
5274 /* This is the end of one of this register's lifetime
5275 segments. Save the lifetime info collected so far,
5276 and clear its bit in the old_live_regs entry. */
5277 sched_reg_live_length[regno] += p->live_length;
5278 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
5279 CLEAR_REGNO_REG_SET (old_live_regs, p->regno);
5281 /* Delete the reg_sometimes_live entry for this reg by
5282 copying the last entry over top of it. */
5283 *p = regs_sometimes_live[--sometimes_max];
5284 /* ...and decrement i so that this newly copied entry
5285 will be processed. */
5291 finish_sometimes_live (regs_sometimes_live, sometimes_max);
5293 /* In interblock scheduling, basic_block_live_at_start may have changed. */
5294 if (current_nr_blocks > 1)
5295 COPY_REG_SET (basic_block_live_at_start[b], bb_live_regs);
5298 FREE_REG_SET (old_live_regs);
5299 } /* find_post_sched_live */
5301 /* After scheduling the subroutine, restore information about uses of
5309 if (n_basic_blocks > 0)
5310 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, FIRST_PSEUDO_REGISTER, regno,
5312 sched_reg_basic_block[regno]
5316 for (regno = 0; regno < max_regno; regno++)
5317 if (sched_reg_live_length[regno])
5321 if (REG_LIVE_LENGTH (regno) > sched_reg_live_length[regno])
5323 ";; register %d life shortened from %d to %d\n",
5324 regno, REG_LIVE_LENGTH (regno),
5325 sched_reg_live_length[regno]);
5326 /* Negative values are special; don't overwrite the current
5327 reg_live_length value if it is negative. */
5328 else if (REG_LIVE_LENGTH (regno) < sched_reg_live_length[regno]
5329 && REG_LIVE_LENGTH (regno) >= 0)
5331 ";; register %d life extended from %d to %d\n",
5332 regno, REG_LIVE_LENGTH (regno),
5333 sched_reg_live_length[regno]);
5335 if (!REG_N_CALLS_CROSSED (regno)
5336 && sched_reg_n_calls_crossed[regno])
5338 ";; register %d now crosses calls\n", regno);
5339 else if (REG_N_CALLS_CROSSED (regno)
5340 && !sched_reg_n_calls_crossed[regno]
5341 && REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5343 ";; register %d no longer crosses calls\n", regno);
5345 if (REG_BASIC_BLOCK (regno) != sched_reg_basic_block[regno]
5346 && sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5347 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5349 ";; register %d changed basic block from %d to %d\n",
5350 regno, REG_BASIC_BLOCK(regno),
5351 sched_reg_basic_block[regno]);
5354 /* Negative values are special; don't overwrite the current
5355 reg_live_length value if it is negative. */
5356 if (REG_LIVE_LENGTH (regno) >= 0)
5357 REG_LIVE_LENGTH (regno) = sched_reg_live_length[regno];
5359 if (sched_reg_basic_block[regno] != REG_BLOCK_UNKNOWN
5360 && REG_BASIC_BLOCK(regno) != REG_BLOCK_UNKNOWN)
5361 REG_BASIC_BLOCK(regno) = sched_reg_basic_block[regno];
5363 /* We can't change the value of reg_n_calls_crossed to zero for
5364 pseudos which are live in more than one block.
5366 This is because combine might have made an optimization which
5367 invalidated basic_block_live_at_start and reg_n_calls_crossed,
5368 but it does not update them. If we update reg_n_calls_crossed
5369 here, the two variables are now inconsistent, and this might
5370 confuse the caller-save code into saving a register that doesn't
5371 need to be saved. This is only a problem when we zero calls
5372 crossed for a pseudo live in multiple basic blocks.
5374 Alternatively, we could try to correctly update basic block live
5375 at start here in sched, but that seems complicated.
5377 Note: it is possible that a global register became local, as result
5378 of interblock motion, but will remain marked as a global register. */
5379 if (sched_reg_n_calls_crossed[regno]
5380 || REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
5381 REG_N_CALLS_CROSSED (regno) = sched_reg_n_calls_crossed[regno];
5386 /* Scheduling clock, modified in schedule_block() and queue_to_ready () */
5387 static int clock_var;
5389 /* Move insns that became ready to fire from queue to ready list. */
5392 queue_to_ready (ready, n_ready)
5399 q_ptr = NEXT_Q (q_ptr);
5401 /* Add all pending insns that can be scheduled without stalls to the
5403 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
5406 insn = XEXP (link, 0);
5409 if (sched_verbose >= 2)
5410 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5412 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5413 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5415 ready[n_ready++] = insn;
5416 if (sched_verbose >= 2)
5417 fprintf (dump, "moving to ready without stalls\n");
5419 insn_queue[q_ptr] = 0;
5421 /* If there are no ready insns, stall until one is ready and add all
5422 of the pending insns at that point to the ready list. */
5425 register int stalls;
5427 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
5429 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
5431 for (; link; link = XEXP (link, 1))
5433 insn = XEXP (link, 0);
5436 if (sched_verbose >= 2)
5437 fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
5439 if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
5440 fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
5442 ready[n_ready++] = insn;
5443 if (sched_verbose >= 2)
5444 fprintf (dump, "moving to ready with %d stalls\n", stalls);
5446 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
5453 if (sched_verbose && stalls)
5454 visualize_stall_cycles (BB_TO_BLOCK (target_bb), stalls);
5455 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
5456 clock_var += stalls;
5461 /* Print the ready list for debugging purposes. Callable from debugger. */
5464 debug_ready_list (ready, n_ready)
5470 for (i = 0; i < n_ready; i++)
5472 fprintf (dump, " %d", INSN_UID (ready[i]));
5473 if (current_nr_blocks > 1 && INSN_BB (ready[i]) != target_bb)
5474 fprintf (dump, "/b%d", INSN_BLOCK (ready[i]));
5476 fprintf (dump, "\n");
5479 /* Print names of units on which insn can/should execute, for debugging. */
5482 insn_print_units (insn)
5486 int unit = insn_unit (insn);
5489 fprintf (dump, "none");
5491 fprintf (dump, "%s", function_units[unit].name);
5494 fprintf (dump, "[");
5495 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
5498 fprintf (dump, "%s", function_units[i].name);
5500 fprintf (dump, " ");
5502 fprintf (dump, "]");
5506 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5507 of a basic block. If more lines are needed, table is splitted to two.
5508 n_visual_lines is the number of lines printed so far for a block.
5509 visual_tbl contains the block visualization info.
5510 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5511 #define MAX_VISUAL_LINES 100
5516 rtx vis_no_unit[10];
5518 /* Finds units that are in use in this fuction. Required only
5519 for visualization. */
5522 init_target_units ()
5527 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
5529 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5532 unit = insn_unit (insn);
5535 target_units |= ~unit;
5537 target_units |= (1 << unit);
5541 /* Return the length of the visualization table */
5544 get_visual_tbl_length ()
5550 /* compute length of one field in line */
5551 s = (char *) alloca (INSN_LEN + 5);
5552 sprintf (s, " %33s", "uname");
5555 /* compute length of one line */
5558 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5559 if (function_units[unit].bitmask & target_units)
5560 for (i = 0; i < function_units[unit].multiplicity; i++)
5563 n += strlen ("\n") + 2;
5565 /* compute length of visualization string */
5566 return (MAX_VISUAL_LINES * n);
5569 /* Init block visualization debugging info */
5572 init_block_visualization ()
5574 strcpy (visual_tbl, "");
5581 /* This recognizes rtx, I classified as expressions. These are always */
5582 /* represent some action on values or results of other expression, */
5583 /* that may be stored in objects representing values. */
5586 print_exp (buf, x, verbose)
5591 char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
5593 switch (GET_CODE (x))
5596 print_value (t1, XEXP (x, 0), verbose);
5597 print_value (t2, XEXP (x, 1), verbose);
5598 sprintf (buf, "%s+%s", t1, t2);
5601 print_value (t1, XEXP (x, 0), verbose);
5602 print_value (t2, XEXP (x, 1), verbose);
5603 sprintf (buf, "%sl+%s", t1, t2);
5606 print_value (t1, XEXP (x, 0), verbose);
5607 print_value (t2, XEXP (x, 1), verbose);
5608 sprintf (buf, "%s-%s", t1, t2);
5611 print_value (t1, XEXP (x, 0), verbose);
5612 print_value (t2, XEXP (x, 1), verbose);
5613 sprintf (buf, "%s??%s", t1, t2);
5616 print_value (t1, XEXP (x, 0), verbose);
5617 sprintf (buf, "-%s", t1);
5620 print_value (t1, XEXP (x, 0), verbose);
5621 print_value (t2, XEXP (x, 1), verbose);
5622 sprintf (buf, "%s*%s", t1, t2);
5625 print_value (t1, XEXP (x, 0), verbose);
5626 print_value (t2, XEXP (x, 1), verbose);
5627 sprintf (buf, "%s/%s", t1, t2);
5630 print_value (t1, XEXP (x, 0), verbose);
5631 print_value (t2, XEXP (x, 1), verbose);
5632 sprintf (buf, "%su/%s", t1, t2);
5635 print_value (t1, XEXP (x, 0), verbose);
5636 print_value (t2, XEXP (x, 1), verbose);
5637 sprintf (buf, "%s%%%s", t1, t2);
5640 print_value (t1, XEXP (x, 0), verbose);
5641 print_value (t2, XEXP (x, 1), verbose);
5642 sprintf (buf, "%su%%%s", t1, t2);
5645 print_value (t1, XEXP (x, 0), verbose);
5646 print_value (t2, XEXP (x, 1), verbose);
5647 sprintf (buf, "smin (%s, %s)", t1, t2);
5650 print_value (t1, XEXP (x, 0), verbose);
5651 print_value (t2, XEXP (x, 1), verbose);
5652 sprintf (buf, "smax(%s,%s)", t1, t2);
5655 print_value (t1, XEXP (x, 0), verbose);
5656 print_value (t2, XEXP (x, 1), verbose);
5657 sprintf (buf, "umin (%s, %s)", t1, t2);
5660 print_value (t1, XEXP (x, 0), verbose);
5661 print_value (t2, XEXP (x, 1), verbose);
5662 sprintf (buf, "umax(%s,%s)", t1, t2);
5665 print_value (t1, XEXP (x, 0), verbose);
5666 sprintf (buf, "!%s", t1);
5669 print_value (t1, XEXP (x, 0), verbose);
5670 print_value (t2, XEXP (x, 1), verbose);
5671 sprintf (buf, "%s&%s", t1, t2);
5674 print_value (t1, XEXP (x, 0), verbose);
5675 print_value (t2, XEXP (x, 1), verbose);
5676 sprintf (buf, "%s|%s", t1, t2);
5679 print_value (t1, XEXP (x, 0), verbose);
5680 print_value (t2, XEXP (x, 1), verbose);
5681 sprintf (buf, "%s^%s", t1, t2);
5684 print_value (t1, XEXP (x, 0), verbose);
5685 print_value (t2, XEXP (x, 1), verbose);
5686 sprintf (buf, "%s<<%s", t1, t2);
5689 print_value (t1, XEXP (x, 0), verbose);
5690 print_value (t2, XEXP (x, 1), verbose);
5691 sprintf (buf, "%s0>%s", t1, t2);
5694 print_value (t1, XEXP (x, 0), verbose);
5695 print_value (t2, XEXP (x, 1), verbose);
5696 sprintf (buf, "%s>>%s", t1, t2);
5699 print_value (t1, XEXP (x, 0), verbose);
5700 print_value (t2, XEXP (x, 1), verbose);
5701 sprintf (buf, "%s<-<%s", t1, t2);
5704 print_value (t1, XEXP (x, 0), verbose);
5705 print_value (t2, XEXP (x, 1), verbose);
5706 sprintf (buf, "%s>->%s", t1, t2);
5709 print_value (t1, XEXP (x, 0), verbose);
5710 sprintf (buf, "abs(%s)", t1);
5713 print_value (t1, XEXP (x, 0), verbose);
5714 sprintf (buf, "sqrt(%s)", t1);
5717 print_value (t1, XEXP (x, 0), verbose);
5718 sprintf (buf, "ffs(%s)", t1);
5721 print_value (t1, XEXP (x, 0), verbose);
5722 print_value (t2, XEXP (x, 1), verbose);
5723 sprintf (buf, "%s == %s", t1, t2);
5726 print_value (t1, XEXP (x, 0), verbose);
5727 print_value (t2, XEXP (x, 1), verbose);
5728 sprintf (buf, "%s!=%s", t1, t2);
5731 print_value (t1, XEXP (x, 0), verbose);
5732 print_value (t2, XEXP (x, 1), verbose);
5733 sprintf (buf, "%s>%s", t1, t2);
5736 print_value (t1, XEXP (x, 0), verbose);
5737 print_value (t2, XEXP (x, 1), verbose);
5738 sprintf (buf, "%s>u%s", t1, t2);
5741 print_value (t1, XEXP (x, 0), verbose);
5742 print_value (t2, XEXP (x, 1), verbose);
5743 sprintf (buf, "%s<%s", t1, t2);
5746 print_value (t1, XEXP (x, 0), verbose);
5747 print_value (t2, XEXP (x, 1), verbose);
5748 sprintf (buf, "%s<u%s", t1, t2);
5751 print_value (t1, XEXP (x, 0), verbose);
5752 print_value (t2, XEXP (x, 1), verbose);
5753 sprintf (buf, "%s>=%s", t1, t2);
5756 print_value (t1, XEXP (x, 0), verbose);
5757 print_value (t2, XEXP (x, 1), verbose);
5758 sprintf (buf, "%s>=u%s", t1, t2);
5761 print_value (t1, XEXP (x, 0), verbose);
5762 print_value (t2, XEXP (x, 1), verbose);
5763 sprintf (buf, "%s<=%s", t1, t2);
5766 print_value (t1, XEXP (x, 0), verbose);
5767 print_value (t2, XEXP (x, 1), verbose);
5768 sprintf (buf, "%s<=u%s", t1, t2);
5771 print_value (t1, XEXP (x, 0), verbose);
5772 print_value (t2, XEXP (x, 1), verbose);
5773 print_value (t3, XEXP (x, 2), verbose);
5775 sprintf (buf, "sign_extract(%s,%s,%s)", t1, t2, t3);
5777 sprintf (buf, "sxt(%s,%s,%s)", t1, t2, t3);
5780 print_value (t1, XEXP (x, 0), verbose);
5781 print_value (t2, XEXP (x, 1), verbose);
5782 print_value (t3, XEXP (x, 2), verbose);
5784 sprintf (buf, "zero_extract(%s,%s,%s)", t1, t2, t3);
5786 sprintf (buf, "zxt(%s,%s,%s)", t1, t2, t3);
5789 print_value (t1, XEXP (x, 0), verbose);
5791 sprintf (buf, "sign_extend(%s)", t1);
5793 sprintf (buf, "sxn(%s)", t1);
5796 print_value (t1, XEXP (x, 0), verbose);
5798 sprintf (buf, "zero_extend(%s)", t1);
5800 sprintf (buf, "zxn(%s)", t1);
5803 print_value (t1, XEXP (x, 0), verbose);
5805 sprintf (buf, "float_extend(%s)", t1);
5807 sprintf (buf, "fxn(%s)", t1);
5810 print_value (t1, XEXP (x, 0), verbose);
5812 sprintf (buf, "trunc(%s)", t1);
5814 sprintf (buf, "trn(%s)", t1);
5816 case FLOAT_TRUNCATE:
5817 print_value (t1, XEXP (x, 0), verbose);
5819 sprintf (buf, "float_trunc(%s)", t1);
5821 sprintf (buf, "ftr(%s)", t1);
5824 print_value (t1, XEXP (x, 0), verbose);
5826 sprintf (buf, "float(%s)", t1);
5828 sprintf (buf, "flt(%s)", t1);
5830 case UNSIGNED_FLOAT:
5831 print_value (t1, XEXP (x, 0), verbose);
5833 sprintf (buf, "uns_float(%s)", t1);
5835 sprintf (buf, "ufl(%s)", t1);
5838 print_value (t1, XEXP (x, 0), verbose);
5839 sprintf (buf, "fix(%s)", t1);
5842 print_value (t1, XEXP (x, 0), verbose);
5844 sprintf (buf, "uns_fix(%s)", t1);
5846 sprintf (buf, "ufx(%s)", t1);
5849 print_value (t1, XEXP (x, 0), verbose);
5850 sprintf (buf, "--%s", t1);
5853 print_value (t1, XEXP (x, 0), verbose);
5854 sprintf (buf, "++%s", t1);
5857 print_value (t1, XEXP (x, 0), verbose);
5858 sprintf (buf, "%s--", t1);
5861 print_value (t1, XEXP (x, 0), verbose);
5862 sprintf (buf, "%s++", t1);
5865 print_value (t1, XEXP (x, 0), verbose);
5868 print_value (t2, XEXP (x, 1), verbose);
5869 sprintf (buf, "call %s argc:%s", t1, t2);
5872 sprintf (buf, "call %s", t1);
5875 print_exp (t1, XEXP (x, 0), verbose);
5876 print_value (t2, XEXP (x, 1), verbose);
5877 print_value (t3, XEXP (x, 2), verbose);
5878 sprintf (buf, "{(%s)?%s:%s}", t1, t2, t3);
5881 print_value (t1, TRAP_CONDITION (x), verbose);
5882 sprintf (buf, "trap_if %s", t1);
5888 sprintf (t1, "unspec{");
5889 for (i = 0; i < XVECLEN (x, 0); i++)
5891 print_pattern (t2, XVECEXP (x, 0, i), verbose);
5892 sprintf (t3, "%s%s;", t1, t2);
5895 sprintf (buf, "%s}", t1);
5898 case UNSPEC_VOLATILE:
5902 sprintf (t1, "unspec/v{");
5903 for (i = 0; i < XVECLEN (x, 0); i++)
5905 print_pattern (t2, XVECEXP (x, 0, i), verbose);
5906 sprintf (t3, "%s%s;", t1, t2);
5909 sprintf (buf, "%s}", t1);
5913 /* if (verbose) debug_rtx (x); else sprintf (buf, "$$$"); */
5914 sprintf (buf, "$$$");
5918 /* Prints rtxes, i customly classified as values. They're constants, */
5919 /* registers, labels, symbols and memory accesses. */
5922 print_value (buf, x, verbose)
5929 switch (GET_CODE (x))
5932 sprintf (buf, "%Xh", INTVAL (x));
5935 print_value (t, XEXP (x, 0), verbose);
5936 sprintf (buf, "<%s>", t);
5939 sprintf (buf, "\"%s\"", (char *) XEXP (x, 0));
5942 sprintf (buf, "`%s'", (char *) XEXP (x, 0));
5945 sprintf (buf, "L%d", INSN_UID (XEXP (x, 0)));
5948 print_value (buf, XEXP (x, 0), verbose);
5951 print_value (buf, XEXP (x, 0), verbose);
5954 if (GET_MODE (x) == SFmode
5955 || GET_MODE (x) == DFmode
5956 || GET_MODE (x) == XFmode
5957 || GET_MODE (x) == TFmode)
5961 sprintf (buf, "%s%d", t, REGNO (x));
5964 print_value (t, XEXP (x, 0), verbose);
5965 sprintf (buf, "%s#%d", t, SUBREG_WORD (x));
5968 sprintf (buf, "scratch");
5971 sprintf (buf, "cc0");
5974 sprintf (buf, "pc");
5977 print_value (t, XEXP (x, 0), verbose);
5978 sprintf (buf, "[%s]", t);
5981 print_exp (buf, x, verbose);
5985 /* The next step in insn detalization, its pattern recognition */
5988 print_pattern (buf, x, verbose)
5993 char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
5995 switch (GET_CODE (x))
5998 print_value (t1, SET_DEST (x), verbose);
5999 print_value (t2, SET_SRC (x), verbose);
6000 sprintf (buf, "%s=%s", t1, t2);
6003 sprintf (buf, "return");
6006 print_exp (buf, x, verbose);
6009 print_value (t1, XEXP (x, 0), verbose);
6010 sprintf (buf, "clobber %s", t1);
6013 print_value (t1, XEXP (x, 0), verbose);
6014 sprintf (buf, "use %s", t1);
6021 for (i = 0; i < XVECLEN (x, 0); i++)
6023 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6024 sprintf (t3, "%s%s;", t1, t2);
6027 sprintf (buf, "%s}", t1);
6034 sprintf (t1, "%%{");
6035 for (i = 0; i < XVECLEN (x, 0); i++)
6037 print_insn (t2, XVECEXP (x, 0, i), verbose);
6038 sprintf (t3, "%s%s;", t1, t2);
6041 sprintf (buf, "%s%%}", t1);
6045 sprintf (buf, "asm {%s}", XSTR (x, 0));
6050 print_value (buf, XEXP (x, 0), verbose);
6053 print_value (t1, TRAP_CONDITION (x), verbose);
6054 sprintf (buf, "trap_if %s", t1);
6060 sprintf (t1, "unspec{");
6061 for (i = 0; i < XVECLEN (x, 0); i++)
6063 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6064 sprintf (t3, "%s%s;", t1, t2);
6067 sprintf (buf, "%s}", t1);
6070 case UNSPEC_VOLATILE:
6074 sprintf (t1, "unspec/v{");
6075 for (i = 0; i < XVECLEN (x, 0); i++)
6077 print_pattern (t2, XVECEXP (x, 0, i), verbose);
6078 sprintf (t3, "%s%s;", t1, t2);
6081 sprintf (buf, "%s}", t1);
6085 print_value (buf, x, verbose);
6087 } /* print_pattern */
6089 /* This is the main function in rtl visualization mechanism. It
6090 accepts an rtx and tries to recognize it as an insn, then prints it
6091 properly in human readable form, resembling assembler mnemonics. */
6092 /* For every insn it prints its UID and BB the insn belongs */
6093 /* too. (probably the last "option" should be extended somehow, since */
6094 /* it depends now on sched.c inner variables ...) */
6097 print_insn (buf, x, verbose)
6105 switch (GET_CODE (x))
6108 print_pattern (t, PATTERN (x), verbose);
6110 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (x),
6113 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6116 print_pattern (t, PATTERN (x), verbose);
6118 sprintf (buf, "b%d: i% 4d: jump %s", INSN_BB (x),
6121 sprintf (buf, "%-4d %s", INSN_UID (x), t);
6125 if (GET_CODE (x) == PARALLEL)
6127 x = XVECEXP (x, 0, 0);
6128 print_pattern (t, x, verbose);
6131 strcpy (t, "call <...>");
6133 sprintf (buf, "b%d: i% 4d: %s", INSN_BB (insn),
6134 INSN_UID (insn), t);
6136 sprintf (buf, "%-4d %s", INSN_UID (insn), t);
6139 sprintf (buf, "L%d:", INSN_UID (x));
6142 sprintf (buf, "i% 4d: barrier", INSN_UID (x));
6145 if (NOTE_LINE_NUMBER (x) > 0)
6146 sprintf (buf, "%4d note \"%s\" %d", INSN_UID (x),
6147 NOTE_SOURCE_FILE (x), NOTE_LINE_NUMBER (x));
6149 sprintf (buf, "%4d %s", INSN_UID (x),
6150 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x)));
6155 sprintf (buf, "Not an INSN at all\n");
6159 sprintf (buf, "i%-4d <What?>", INSN_UID (x));
6164 print_insn_chain (rtx_first)
6167 register rtx tmp_rtx;
6170 strcpy (str, "(nil)\n");
6172 switch (GET_CODE (rtx_first))
6180 for (tmp_rtx = rtx_first; tmp_rtx != NULL;
6181 tmp_rtx = NEXT_INSN (tmp_rtx))
6183 print_insn (str, tmp_rtx, 0);
6184 printf ("%s\n", str);
6188 print_insn (str, rtx_first, 0);
6189 printf ("%s\n", str);
6191 } /* print_insn_chain */
6193 /* Print visualization debugging info */
6196 print_block_visualization (b, s)
6203 fprintf (dump, "\n;; ==================== scheduling visualization for block %d %s \n", b, s);
6205 /* Print names of units */
6206 fprintf (dump, ";; %-8s", "clock");
6207 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6208 if (function_units[unit].bitmask & target_units)
6209 for (i = 0; i < function_units[unit].multiplicity; i++)
6210 fprintf (dump, " %-33s", function_units[unit].name);
6211 fprintf (dump, " %-8s\n", "no-unit");
6213 fprintf (dump, ";; %-8s", "=====");
6214 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6215 if (function_units[unit].bitmask & target_units)
6216 for (i = 0; i < function_units[unit].multiplicity; i++)
6217 fprintf (dump, " %-33s", "==============================");
6218 fprintf (dump, " %-8s\n", "=======");
6220 /* Print insns in each cycle */
6221 fprintf (dump, "%s\n", visual_tbl);
6224 /* Print insns in the 'no_unit' column of visualization */
6227 visualize_no_unit (insn)
6230 vis_no_unit[n_vis_no_unit] = insn;
6234 /* Print insns scheduled in clock, for visualization. */
6237 visualize_scheduled_insns (b, clock)
6242 /* if no more room, split table into two */
6243 if (n_visual_lines >= MAX_VISUAL_LINES)
6245 print_block_visualization (b, "(incomplete)");
6246 init_block_visualization ();
6251 sprintf (visual_tbl + strlen (visual_tbl), ";; %-8d", clock);
6252 for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
6253 if (function_units[unit].bitmask & target_units)
6254 for (i = 0; i < function_units[unit].multiplicity; i++)
6256 int instance = unit + i * FUNCTION_UNITS_SIZE;
6257 rtx insn = unit_last_insn[instance];
6259 /* print insns that still keep the unit busy */
6261 actual_hazard_this_instance (unit, instance, insn, clock, 0))
6264 print_insn (str, insn, 0);
6265 str[INSN_LEN] = '\0';
6266 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", str);
6269 sprintf (visual_tbl + strlen (visual_tbl), " %-33s", "------------------------------");
6272 /* print insns that are not assigned to any unit */
6273 for (i = 0; i < n_vis_no_unit; i++)
6274 sprintf (visual_tbl + strlen (visual_tbl), " %-8d",
6275 INSN_UID (vis_no_unit[i]));
6278 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6281 /* Print stalled cycles */
6284 visualize_stall_cycles (b, stalls)
6289 /* if no more room, split table into two */
6290 if (n_visual_lines >= MAX_VISUAL_LINES)
6292 print_block_visualization (b, "(incomplete)");
6293 init_block_visualization ();
6298 sprintf (visual_tbl + strlen (visual_tbl), ";; ");
6299 for (i = 0; i < stalls; i++)
6300 sprintf (visual_tbl + strlen (visual_tbl), ".");
6301 sprintf (visual_tbl + strlen (visual_tbl), "\n");
6304 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn */
6307 move_insn1 (insn, last)
6310 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
6311 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
6313 NEXT_INSN (insn) = NEXT_INSN (last);
6314 PREV_INSN (NEXT_INSN (last)) = insn;
6316 NEXT_INSN (last) = insn;
6317 PREV_INSN (insn) = last;
6322 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
6323 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
6324 NOTEs. The REG_DEAD note following first one is contains the saved
6325 value for NOTE_BLOCK_NUMBER which is useful for
6326 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
6327 output by the instruction scheduler. Return the new value of LAST. */
6330 reemit_notes (insn, last)
6337 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
6339 if (REG_NOTE_KIND (note) == REG_DEAD
6340 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6342 if (INTVAL (XEXP (note, 0)) == NOTE_INSN_SETJMP)
6344 retval = emit_note_after (INTVAL (XEXP (note, 0)), insn);
6345 CONST_CALL_P (retval) = CONST_CALL_P (note);
6346 remove_note (insn, note);
6347 note = XEXP (note, 1);
6351 last = emit_note_before (INTVAL (XEXP (note, 0)), last);
6352 remove_note (insn, note);
6353 note = XEXP (note, 1);
6354 NOTE_BLOCK_NUMBER (last) = INTVAL (XEXP (note, 0));
6356 remove_note (insn, note);
6362 /* Move INSN, and all insns which should be issued before it,
6363 due to SCHED_GROUP_P flag. Reemit notes if needed.
6365 Return the last insn emitted by the scheduler, which is the
6366 return value from the first call to reemit_notes. */
6369 move_insn (insn, last)
6374 /* If INSN has SCHED_GROUP_P set, then issue it and any other
6375 insns with SCHED_GROUP_P set first. */
6376 while (SCHED_GROUP_P (insn))
6378 rtx prev = PREV_INSN (insn);
6380 /* Move a SCHED_GROUP_P insn. */
6381 move_insn1 (insn, last);
6382 /* If this is the first call to reemit_notes, then record
6383 its return value. */
6384 if (retval == NULL_RTX)
6385 retval = reemit_notes (insn, insn);
6387 reemit_notes (insn, insn);
6391 /* Now move the first non SCHED_GROUP_P insn. */
6392 move_insn1 (insn, last);
6394 /* If this is the first call to reemit_notes, then record
6395 its return value. */
6396 if (retval == NULL_RTX)
6397 retval = reemit_notes (insn, insn);
6399 reemit_notes (insn, insn);
6404 /* Return an insn which represents a SCHED_GROUP, which is
6405 the last insn in the group. */
6416 insn = next_nonnote_insn (insn);
6418 while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
6423 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
6424 possibly bringing insns from subsequent blocks in the same region.
6425 Return number of insns scheduled. */
6428 schedule_block (bb, rgn_n_insns)
6432 /* Local variables. */
6439 /* flow block of this bb */
6440 int b = BB_TO_BLOCK (bb);
6442 /* target_n_insns == number of insns in b before scheduling starts.
6443 sched_target_n_insns == how many of b's insns were scheduled.
6444 sched_n_insns == how many insns were scheduled in b */
6445 int target_n_insns = 0;
6446 int sched_target_n_insns = 0;
6447 int sched_n_insns = 0;
6449 #define NEED_NOTHING 0
6454 /* head/tail info for this block */
6461 /* We used to have code to avoid getting parameters moved from hard
6462 argument registers into pseudos.
6464 However, it was removed when it proved to be of marginal benefit
6465 and caused problems because schedule_block and compute_forward_dependences
6466 had different notions of what the "head" insn was. */
6467 get_block_head_tail (bb, &head, &tail);
6469 /* Interblock scheduling could have moved the original head insn from this
6470 block into a proceeding block. This may also cause schedule_block and
6471 compute_forward_dependences to have different notions of what the
6474 If the interblock movement happened to make this block start with
6475 some notes (LOOP, EH or SETJMP) before the first real insn, then
6476 HEAD will have various special notes attached to it which must be
6477 removed so that we don't end up with extra copies of the notes. */
6478 if (GET_RTX_CLASS (GET_CODE (head)) == 'i')
6482 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
6483 if (REG_NOTE_KIND (note) == REG_DEAD
6484 && GET_CODE (XEXP (note, 0)) == CONST_INT)
6485 remove_note (head, note);
6488 next_tail = NEXT_INSN (tail);
6489 prev_head = PREV_INSN (head);
6491 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6492 to schedule this block. */
6494 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6495 return (sched_n_insns);
6500 fprintf (dump, ";; ======================================================\n");
6502 ";; -- basic block %d from %d to %d -- %s reload\n",
6503 b, INSN_UID (basic_block_head[b]),
6504 INSN_UID (basic_block_end[b]),
6505 (reload_completed ? "after" : "before"));
6506 fprintf (dump, ";; ======================================================\n");
6507 if (sched_debug_count >= 0)
6508 fprintf (dump, ";;\t -- sched_debug_count=%d\n", sched_debug_count);
6509 fprintf (dump, "\n");
6511 visual_tbl = (char *) alloca (get_visual_tbl_length ());
6512 init_block_visualization ();
6515 /* remove remaining note insns from the block, save them in
6516 note_list. These notes are restored at the end of
6517 schedule_block (). */
6519 rm_other_notes (head, tail);
6523 /* prepare current target block info */
6524 if (current_nr_blocks > 1)
6526 candidate_table = (candidate *) alloca (current_nr_blocks * sizeof (candidate));
6529 /* ??? It is not clear why bblst_size is computed this way. The original
6530 number was clearly too small as it resulted in compiler failures.
6531 Multiplying by the original number by 2 (to account for update_bbs
6532 members) seems to be a reasonable solution. */
6533 /* ??? Or perhaps there is a bug somewhere else in this file? */
6534 bblst_size = (current_nr_blocks - bb) * rgn_nr_edges * 2;
6535 bblst_table = (int *) alloca (bblst_size * sizeof (int));
6537 bitlst_table_last = 0;
6538 bitlst_table_size = rgn_nr_edges;
6539 bitlst_table = (int *) alloca (rgn_nr_edges * sizeof (int));
6541 compute_trg_info (bb);
6546 /* Allocate the ready list */
6547 ready = (rtx *) alloca ((rgn_n_insns + 1) * sizeof (rtx));
6549 /* Print debugging information. */
6550 if (sched_verbose >= 5)
6551 debug_dependencies ();
6554 /* Initialize ready list with all 'ready' insns in target block.
6555 Count number of insns in the target block being scheduled. */
6557 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6561 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6563 next = NEXT_INSN (insn);
6565 if (INSN_DEP_COUNT (insn) == 0
6566 && (SCHED_GROUP_P (next) == 0 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6567 ready[n_ready++] = insn;
6568 if (!(SCHED_GROUP_P (insn)))
6572 /* Add to ready list all 'ready' insns in valid source blocks.
6573 For speculative insns, check-live, exception-free, and
6575 for (bb_src = bb + 1; bb_src < current_nr_blocks; bb_src++)
6576 if (IS_VALID (bb_src))
6582 get_block_head_tail (bb_src, &head, &tail);
6583 src_next_tail = NEXT_INSN (tail);
6587 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6590 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
6592 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6595 if (!CANT_MOVE (insn)
6596 && (!IS_SPECULATIVE_INSN (insn)
6597 || (insn_issue_delay (insn) <= 3
6598 && check_live (insn, bb_src)
6599 && is_exception_free (insn, bb_src, target_bb))))
6604 next = NEXT_INSN (insn);
6605 if (INSN_DEP_COUNT (insn) == 0
6606 && (SCHED_GROUP_P (next) == 0
6607 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
6608 ready[n_ready++] = insn;
6613 /* no insns scheduled in this block yet */
6614 last_scheduled_insn = 0;
6616 /* Sort the ready list */
6617 SCHED_SORT (ready, n_ready);
6619 if (sched_verbose >= 2)
6621 fprintf (dump, ";;\t\tReady list initially: ");
6622 debug_ready_list (ready, n_ready);
6625 /* Q_SIZE is the total number of insns in the queue. */
6629 bzero ((char *) insn_queue, sizeof (insn_queue));
6631 /* We start inserting insns after PREV_HEAD. */
6634 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6635 new_needs = (NEXT_INSN (prev_head) == basic_block_head[b]
6636 ? NEED_HEAD : NEED_NOTHING);
6637 if (PREV_INSN (next_tail) == basic_block_end[b])
6638 new_needs |= NEED_TAIL;
6640 /* loop until all the insns in BB are scheduled. */
6641 while (sched_target_n_insns < target_n_insns)
6645 #ifdef INTERBLOCK_DEBUG
6646 if (sched_debug_count == 0)
6651 /* Add to the ready list all pending insns that can be issued now.
6652 If there are no ready insns, increment clock until one
6653 is ready and add all pending insns at that point to the ready
6655 n_ready = queue_to_ready (ready, n_ready);
6660 if (sched_verbose >= 2)
6662 fprintf (dump, ";;\t\tReady list after queue_to_ready: ");
6663 debug_ready_list (ready, n_ready);
6666 /* Sort the ready list. */
6667 SCHED_SORT (ready, n_ready);
6671 fprintf (dump, ";;\tReady list (t =%3d): ", clock_var);
6672 debug_ready_list (ready, n_ready);
6675 /* Issue insns from ready list.
6676 It is important to count down from n_ready, because n_ready may change
6677 as insns are issued. */
6678 can_issue_more = issue_rate;
6679 for (i = n_ready - 1; i >= 0 && can_issue_more; i--)
6681 rtx insn = ready[i];
6682 int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
6686 queue_insn (insn, cost);
6687 ready[i] = ready[--n_ready]; /* remove insn from ready list */
6691 #ifdef INTERBLOCK_DEBUG
6692 if (sched_debug_count == 0)
6696 /* an interblock motion? */
6697 if (INSN_BB (insn) != target_bb)
6701 if (IS_SPECULATIVE_INSN (insn))
6704 if (!check_live (insn, INSN_BB (insn)))
6706 /* speculative motion, live check failed, remove
6707 insn from ready list */
6708 ready[i] = ready[--n_ready];
6711 update_live (insn, INSN_BB (insn));
6713 /* for speculative load, mark insns fed by it. */
6714 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
6715 set_spec_fed (insn);
6722 while (SCHED_GROUP_P (temp))
6723 temp = PREV_INSN (temp);
6725 /* Update source block boundaries. */
6726 b1 = INSN_BLOCK (temp);
6727 if (temp == basic_block_head[b1]
6728 && insn == basic_block_end[b1])
6730 /* We moved all the insns in the basic block.
6731 Emit a note after the last insn and update the
6732 begin/end boundaries to point to the note. */
6733 emit_note_after (NOTE_INSN_DELETED, insn);
6734 basic_block_end[b1] = NEXT_INSN (insn);
6735 basic_block_head[b1] = NEXT_INSN (insn);
6737 else if (insn == basic_block_end[b1])
6739 /* We took insns from the end of the basic block,
6740 so update the end of block boundary so that it
6741 points to the first insn we did not move. */
6742 basic_block_end[b1] = PREV_INSN (temp);
6744 else if (temp == basic_block_head[b1])
6746 /* We took insns from the start of the basic block,
6747 so update the start of block boundary so that
6748 it points to the first insn we did not move. */
6749 basic_block_head[b1] = NEXT_INSN (insn);
6754 /* in block motion */
6755 sched_target_n_insns++;
6758 last_scheduled_insn = insn;
6759 last = move_insn (insn, last);
6764 #ifdef INTERBLOCK_DEBUG
6765 if (sched_debug_count > 0)
6766 sched_debug_count--;
6769 n_ready = schedule_insn (insn, ready, n_ready, clock_var);
6771 /* remove insn from ready list */
6772 ready[i] = ready[--n_ready];
6774 /* close this block after scheduling its jump */
6775 if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
6783 visualize_scheduled_insns (b, clock_var);
6784 #ifdef INTERBLOCK_DEBUG
6785 if (sched_debug_count == 0)
6786 fprintf (dump, "........ sched_debug_count == 0 .................\n");
6794 fprintf (dump, ";;\tReady list (final): ");
6795 debug_ready_list (ready, n_ready);
6796 print_block_visualization (b, "");
6799 /* Sanity check -- queue must be empty now. Meaningless if region has
6800 multiple bbs, or if scheduling stopped by sched_debug_count. */
6801 if (current_nr_blocks > 1)
6802 #ifdef INTERBLOCK_DEBUG
6803 if (sched_debug_count != 0)
6805 if (!flag_schedule_interblock && q_size != 0)
6808 /* update head/tail boundaries. */
6809 head = NEXT_INSN (prev_head);
6812 #ifdef INTERBLOCK_DEBUG
6813 if (sched_debug_count == 0)
6814 /* compensate for stopping scheduling prematurely */
6815 for (i = sched_target_n_insns; i < target_n_insns; i++)
6816 tail = move_insn (group_leader (NEXT_INSN (tail)), tail);
6819 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6820 previously found among the insns. Insert them at the beginning
6824 rtx note_head = note_list;
6826 while (PREV_INSN (note_head))
6828 note_head = PREV_INSN (note_head);
6831 PREV_INSN (note_head) = PREV_INSN (head);
6832 NEXT_INSN (PREV_INSN (head)) = note_head;
6833 PREV_INSN (head) = note_list;
6834 NEXT_INSN (note_list) = head;
6838 /* update target block boundaries. */
6839 if (new_needs & NEED_HEAD)
6840 basic_block_head[b] = head;
6842 if (new_needs & NEED_TAIL)
6843 basic_block_end[b] = tail;
6848 fprintf (dump, ";; total time = %d\n;; new basic block head = %d\n",
6849 clock_var, INSN_UID (basic_block_head[b]));
6850 fprintf (dump, ";; new basic block end = %d\n\n",
6851 INSN_UID (basic_block_end[b]));
6854 return (sched_n_insns);
6855 } /* schedule_block () */
6858 /* print the bit-set of registers, S. callable from debugger */
6861 debug_reg_vector (s)
6866 EXECUTE_IF_SET_IN_REG_SET (s, 0, regno,
6868 fprintf (dump, " %d", regno);
6871 fprintf (dump, "\n");
6874 /* Use the backward dependences from LOG_LINKS to build
6875 forward dependences in INSN_DEPEND. */
6878 compute_block_forward_dependences (bb)
6884 enum reg_note dep_type;
6886 get_block_head_tail (bb, &head, &tail);
6887 next_tail = NEXT_INSN (tail);
6888 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6890 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6893 insn = group_leader (insn);
6895 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
6897 rtx x = group_leader (XEXP (link, 0));
6900 if (x != XEXP (link, 0))
6903 /* Ignore dependences upon deleted insn */
6904 if (GET_CODE (x) == NOTE || INSN_DELETED_P (x))
6906 if (find_insn_list (insn, INSN_DEPEND (x)))
6909 new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
6911 dep_type = REG_NOTE_KIND (link);
6912 PUT_REG_NOTE_KIND (new_link, dep_type);
6914 INSN_DEPEND (x) = new_link;
6915 INSN_DEP_COUNT (insn) += 1;
6920 /* Initialize variables for region data dependence analysis.
6921 n_bbs is the number of region blocks */
6923 __inline static void
6924 init_rgn_data_dependences (n_bbs)
6929 /* variables for which one copy exists for each block */
6930 bzero ((char *) bb_pending_read_insns, n_bbs * sizeof (rtx));
6931 bzero ((char *) bb_pending_read_mems, n_bbs * sizeof (rtx));
6932 bzero ((char *) bb_pending_write_insns, n_bbs * sizeof (rtx));
6933 bzero ((char *) bb_pending_write_mems, n_bbs * sizeof (rtx));
6934 bzero ((char *) bb_pending_lists_length, n_bbs * sizeof (rtx));
6935 bzero ((char *) bb_last_pending_memory_flush, n_bbs * sizeof (rtx));
6936 bzero ((char *) bb_last_function_call, n_bbs * sizeof (rtx));
6937 bzero ((char *) bb_sched_before_next_call, n_bbs * sizeof (rtx));
6939 /* Create an insn here so that we can hang dependencies off of it later. */
6940 for (bb = 0; bb < n_bbs; bb++)
6942 bb_sched_before_next_call[bb] =
6943 gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
6944 NULL_RTX, 0, NULL_RTX, NULL_RTX);
6945 LOG_LINKS (bb_sched_before_next_call[bb]) = 0;
6949 /* Add dependences so that branches are scheduled to run last in their block */
6952 add_branch_dependences (head, tail)
6958 /* For all branches, calls, uses, and cc0 setters, force them to remain
6959 in order at the end of the block by adding dependencies and giving
6960 the last a high priority. There may be notes present, and prev_head
6963 Branches must obviously remain at the end. Calls should remain at the
6964 end since moving them results in worse register allocation. Uses remain
6965 at the end to ensure proper register allocation. cc0 setters remaim
6966 at the end because they can't be moved away from their cc0 user. */
6969 while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
6970 || (GET_CODE (insn) == INSN
6971 && (GET_CODE (PATTERN (insn)) == USE
6973 || sets_cc0_p (PATTERN (insn))
6976 || GET_CODE (insn) == NOTE)
6978 if (GET_CODE (insn) != NOTE)
6981 && !find_insn_list (insn, LOG_LINKS (last)))
6983 add_dependence (last, insn, REG_DEP_ANTI);
6984 INSN_REF_COUNT (insn)++;
6987 CANT_MOVE (insn) = 1;
6990 /* Skip over insns that are part of a group.
6991 Make each insn explicitly depend on the previous insn.
6992 This ensures that only the group header will ever enter
6993 the ready queue (and, when scheduled, will automatically
6994 schedule the SCHED_GROUP_P block). */
6995 while (SCHED_GROUP_P (insn))
6997 rtx temp = prev_nonnote_insn (insn);
6998 add_dependence (insn, temp, REG_DEP_ANTI);
7003 /* Don't overrun the bounds of the basic block. */
7007 insn = PREV_INSN (insn);
7010 /* make sure these insns are scheduled last in their block */
7013 while (insn != head)
7015 insn = prev_nonnote_insn (insn);
7017 if (INSN_REF_COUNT (insn) != 0)
7020 if (!find_insn_list (last, LOG_LINKS (insn)))
7021 add_dependence (last, insn, REG_DEP_ANTI);
7022 INSN_REF_COUNT (insn) = 1;
7024 /* Skip over insns that are part of a group. */
7025 while (SCHED_GROUP_P (insn))
7026 insn = prev_nonnote_insn (insn);
7030 /* Compute bacward dependences inside BB. In a multiple blocks region:
7031 (1) a bb is analyzed after its predecessors, and (2) the lists in
7032 effect at the end of bb (after analyzing for bb) are inherited by
7035 Specifically for reg-reg data dependences, the block insns are
7036 scanned by sched_analyze () top-to-bottom. Two lists are
7037 naintained by sched_analyze (): reg_last_defs[] for register DEFs,
7038 and reg_last_uses[] for register USEs.
7040 When analysis is completed for bb, we update for its successors:
7041 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7042 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7044 The mechanism for computing mem-mem data dependence is very
7045 similar, and the result is interblock dependences in the region. */
7048 compute_block_backward_dependences (bb)
7054 int max_reg = max_reg_num ();
7056 b = BB_TO_BLOCK (bb);
7058 if (current_nr_blocks == 1)
7060 reg_last_uses = (rtx *) alloca (max_reg * sizeof (rtx));
7061 reg_last_sets = (rtx *) alloca (max_reg * sizeof (rtx));
7063 bzero ((char *) reg_last_uses, max_reg * sizeof (rtx));
7064 bzero ((char *) reg_last_sets, max_reg * sizeof (rtx));
7066 pending_read_insns = 0;
7067 pending_read_mems = 0;
7068 pending_write_insns = 0;
7069 pending_write_mems = 0;
7070 pending_lists_length = 0;
7071 last_function_call = 0;
7072 last_pending_memory_flush = 0;
7073 sched_before_next_call
7074 = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
7075 NULL_RTX, 0, NULL_RTX, NULL_RTX);
7076 LOG_LINKS (sched_before_next_call) = 0;
7080 reg_last_uses = bb_reg_last_uses[bb];
7081 reg_last_sets = bb_reg_last_sets[bb];
7083 pending_read_insns = bb_pending_read_insns[bb];
7084 pending_read_mems = bb_pending_read_mems[bb];
7085 pending_write_insns = bb_pending_write_insns[bb];
7086 pending_write_mems = bb_pending_write_mems[bb];
7087 pending_lists_length = bb_pending_lists_length[bb];
7088 last_function_call = bb_last_function_call[bb];
7089 last_pending_memory_flush = bb_last_pending_memory_flush[bb];
7091 sched_before_next_call = bb_sched_before_next_call[bb];
7094 /* do the analysis for this block */
7095 get_block_head_tail (bb, &head, &tail);
7096 sched_analyze (head, tail);
7097 add_branch_dependences (head, tail);
7099 if (current_nr_blocks > 1)
7102 int b_succ, bb_succ;
7104 rtx link_insn, link_mem;
7107 /* these lists should point to the right place, for correct freeing later. */
7108 bb_pending_read_insns[bb] = pending_read_insns;
7109 bb_pending_read_mems[bb] = pending_read_mems;
7110 bb_pending_write_insns[bb] = pending_write_insns;
7111 bb_pending_write_mems[bb] = pending_write_mems;
7113 /* bb's structures are inherited by it's successors */
7114 first_edge = e = OUT_EDGES (b);
7118 b_succ = TO_BLOCK (e);
7119 bb_succ = BLOCK_TO_BB (b_succ);
7121 /* only bbs "below" bb, in the same region, are interesting */
7122 if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
7129 for (reg = 0; reg < max_reg; reg++)
7132 /* reg-last-uses lists are inherited by bb_succ */
7133 for (u = reg_last_uses[reg]; u; u = XEXP (u, 1))
7135 if (find_insn_list (XEXP (u, 0), (bb_reg_last_uses[bb_succ])[reg]))
7138 (bb_reg_last_uses[bb_succ])[reg]
7139 = alloc_INSN_LIST (XEXP (u, 0),
7140 (bb_reg_last_uses[bb_succ])[reg]);
7143 /* reg-last-defs lists are inherited by bb_succ */
7144 for (u = reg_last_sets[reg]; u; u = XEXP (u, 1))
7146 if (find_insn_list (XEXP (u, 0), (bb_reg_last_sets[bb_succ])[reg]))
7149 (bb_reg_last_sets[bb_succ])[reg]
7150 = alloc_INSN_LIST (XEXP (u, 0),
7151 (bb_reg_last_sets[bb_succ])[reg]);
7155 /* mem read/write lists are inherited by bb_succ */
7156 link_insn = pending_read_insns;
7157 link_mem = pending_read_mems;
7160 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7161 bb_pending_read_insns[bb_succ],
7162 bb_pending_read_mems[bb_succ])))
7163 add_insn_mem_dependence (&bb_pending_read_insns[bb_succ],
7164 &bb_pending_read_mems[bb_succ],
7165 XEXP (link_insn, 0), XEXP (link_mem, 0));
7166 link_insn = XEXP (link_insn, 1);
7167 link_mem = XEXP (link_mem, 1);
7170 link_insn = pending_write_insns;
7171 link_mem = pending_write_mems;
7174 if (!(find_insn_mem_list (XEXP (link_insn, 0), XEXP (link_mem, 0),
7175 bb_pending_write_insns[bb_succ],
7176 bb_pending_write_mems[bb_succ])))
7177 add_insn_mem_dependence (&bb_pending_write_insns[bb_succ],
7178 &bb_pending_write_mems[bb_succ],
7179 XEXP (link_insn, 0), XEXP (link_mem, 0));
7181 link_insn = XEXP (link_insn, 1);
7182 link_mem = XEXP (link_mem, 1);
7185 /* last_function_call is inherited by bb_succ */
7186 for (u = last_function_call; u; u = XEXP (u, 1))
7188 if (find_insn_list (XEXP (u, 0), bb_last_function_call[bb_succ]))
7191 bb_last_function_call[bb_succ]
7192 = alloc_INSN_LIST (XEXP (u, 0),
7193 bb_last_function_call[bb_succ]);
7196 /* last_pending_memory_flush is inherited by bb_succ */
7197 for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
7199 if (find_insn_list (XEXP (u, 0), bb_last_pending_memory_flush[bb_succ]))
7202 bb_last_pending_memory_flush[bb_succ]
7203 = alloc_INSN_LIST (XEXP (u, 0),
7204 bb_last_pending_memory_flush[bb_succ]);
7207 /* sched_before_next_call is inherited by bb_succ */
7208 x = LOG_LINKS (sched_before_next_call);
7209 for (; x; x = XEXP (x, 1))
7210 add_dependence (bb_sched_before_next_call[bb_succ],
7211 XEXP (x, 0), REG_DEP_ANTI);
7215 while (e != first_edge);
7218 /* Free up the INSN_LISTs
7220 Note this loop is executed max_reg * nr_regions times. It's first
7221 implementation accounted for over 90% of the calls to free_list.
7222 The list was empty for the vast majority of those calls. On the PA,
7223 not calling free_list in those cases improves -O2 compile times by
7225 for (b = 0; b < max_reg; ++b)
7227 if (reg_last_sets[b])
7228 free_list (®_last_sets[b], &unused_insn_list);
7229 if (reg_last_uses[b])
7230 free_list (®_last_uses[b], &unused_insn_list);
7233 /* Assert that we won't need bb_reg_last_* for this block anymore. */
7234 if (current_nr_blocks > 1)
7236 bb_reg_last_uses[bb] = (rtx *) NULL_RTX;
7237 bb_reg_last_sets[bb] = (rtx *) NULL_RTX;
7241 /* Print dependences for debugging, callable from debugger */
7244 debug_dependencies ()
7248 fprintf (dump, ";; --------------- forward dependences: ------------ \n");
7249 for (bb = 0; bb < current_nr_blocks; bb++)
7257 get_block_head_tail (bb, &head, &tail);
7258 next_tail = NEXT_INSN (tail);
7259 fprintf (dump, "\n;; --- Region Dependences --- b %d bb %d \n",
7260 BB_TO_BLOCK (bb), bb);
7262 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7263 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7264 fprintf (dump, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7265 "----", "----", "--", "---", "----", "----", "--------", "-----");
7266 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
7271 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7274 fprintf (dump, ";; %6d ", INSN_UID (insn));
7275 if (GET_CODE (insn) == NOTE)
7277 n = NOTE_LINE_NUMBER (insn);
7279 fprintf (dump, "%s\n", GET_NOTE_INSN_NAME (n));
7281 fprintf (dump, "line %d, file %s\n", n,
7282 NOTE_SOURCE_FILE (insn));
7285 fprintf (dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
7289 unit = insn_unit (insn);
7291 || function_units[unit].blockage_range_function == 0) ? 0 :
7292 function_units[unit].blockage_range_function (insn);
7294 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7295 (SCHED_GROUP_P (insn) ? "+" : " "),
7299 INSN_DEP_COUNT (insn),
7300 INSN_PRIORITY (insn),
7301 insn_cost (insn, 0, 0),
7302 (int) MIN_BLOCKAGE_COST (range),
7303 (int) MAX_BLOCKAGE_COST (range));
7304 insn_print_units (insn);
7305 fprintf (dump, "\t: ");
7306 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
7307 fprintf (dump, "%d ", INSN_UID (XEXP (link, 0)));
7308 fprintf (dump, "\n");
7312 fprintf (dump, "\n");
7315 /* Set_priorities: compute priority of each insn in the block */
7328 get_block_head_tail (bb, &head, &tail);
7329 prev_head = PREV_INSN (head);
7332 && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
7336 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
7339 if (GET_CODE (insn) == NOTE)
7342 if (!(SCHED_GROUP_P (insn)))
7344 (void) priority (insn);
7350 /* Make each element of VECTOR point at an rtx-vector,
7351 taking the space for all those rtx-vectors from SPACE.
7352 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7353 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7354 (this is the same as init_regset_vector () in flow.c) */
7357 init_rtx_vector (vector, space, nelts, bytes_per_elt)
7364 register rtx *p = space;
7366 for (i = 0; i < nelts; i++)
7369 p += bytes_per_elt / sizeof (*p);
7373 /* Schedule a region. A region is either an inner loop, a loop-free
7374 subroutine, or a single basic block. Each bb in the region is
7375 scheduled after its flow predecessors. */
7378 schedule_region (rgn)
7382 int rgn_n_insns = 0;
7383 int sched_rgn_n_insns = 0;
7385 /* set variables for the current region */
7386 current_nr_blocks = RGN_NR_BLOCKS (rgn);
7387 current_blocks = RGN_BLOCKS (rgn);
7389 reg_pending_sets = ALLOCA_REG_SET ();
7390 reg_pending_sets_all = 0;
7392 /* initializations for region data dependence analyisis */
7393 if (current_nr_blocks > 1)
7396 int maxreg = max_reg_num ();
7398 bb_reg_last_uses = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7399 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7400 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7401 init_rtx_vector (bb_reg_last_uses, space, current_nr_blocks, maxreg * sizeof (rtx *));
7403 bb_reg_last_sets = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
7404 space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
7405 bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
7406 init_rtx_vector (bb_reg_last_sets, space, current_nr_blocks, maxreg * sizeof (rtx *));
7408 bb_pending_read_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7409 bb_pending_read_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7410 bb_pending_write_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7411 bb_pending_write_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7412 bb_pending_lists_length = (int *) alloca (current_nr_blocks * sizeof (int));
7413 bb_last_pending_memory_flush = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7414 bb_last_function_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7415 bb_sched_before_next_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
7417 init_rgn_data_dependences (current_nr_blocks);
7420 /* compute LOG_LINKS */
7421 for (bb = 0; bb < current_nr_blocks; bb++)
7422 compute_block_backward_dependences (bb);
7424 /* compute INSN_DEPEND */
7425 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7426 compute_block_forward_dependences (bb);
7428 /* Delete line notes, compute live-regs at block end, and set priorities. */
7430 for (bb = 0; bb < current_nr_blocks; bb++)
7432 if (reload_completed == 0)
7433 find_pre_sched_live (bb);
7435 if (write_symbols != NO_DEBUG)
7437 save_line_notes (bb);
7441 rgn_n_insns += set_priorities (bb);
7444 /* compute interblock info: probabilities, split-edges, dominators, etc. */
7445 if (current_nr_blocks > 1)
7449 prob = (float *) alloca ((current_nr_blocks) * sizeof (float));
7451 bbset_size = current_nr_blocks / HOST_BITS_PER_WIDE_INT + 1;
7452 dom = (bbset *) alloca (current_nr_blocks * sizeof (bbset));
7453 for (i = 0; i < current_nr_blocks; i++)
7455 dom[i] = (bbset) alloca (bbset_size * sizeof (HOST_WIDE_INT));
7456 bzero ((char *) dom[i], bbset_size * sizeof (HOST_WIDE_INT));
7461 edge_to_bit = (int *) alloca (nr_edges * sizeof (int));
7462 for (i = 1; i < nr_edges; i++)
7463 if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
7464 EDGE_TO_BIT (i) = rgn_nr_edges++;
7465 rgn_edges = (int *) alloca (rgn_nr_edges * sizeof (int));
7468 for (i = 1; i < nr_edges; i++)
7469 if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
7470 rgn_edges[rgn_nr_edges++] = i;
7473 edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
7474 pot_split = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7475 ancestor_edges = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
7476 for (i = 0; i < current_nr_blocks; i++)
7479 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7480 bzero ((char *) pot_split[i],
7481 edgeset_size * sizeof (HOST_WIDE_INT));
7483 (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
7484 bzero ((char *) ancestor_edges[i],
7485 edgeset_size * sizeof (HOST_WIDE_INT));
7488 /* compute probabilities, dominators, split_edges */
7489 for (bb = 0; bb < current_nr_blocks; bb++)
7490 compute_dom_prob_ps (bb);
7493 /* now we can schedule all blocks */
7494 for (bb = 0; bb < current_nr_blocks; bb++)
7496 sched_rgn_n_insns += schedule_block (bb, rgn_n_insns);
7503 #ifdef INTERBLOCK_DEBUG
7504 if (sched_debug_count != 0)
7506 /* sanity check: verify that all region insns were scheduled */
7507 if (sched_rgn_n_insns != rgn_n_insns)
7510 /* update register life and usage information */
7511 if (reload_completed == 0)
7513 for (bb = current_nr_blocks - 1; bb >= 0; bb--)
7514 find_post_sched_live (bb);
7516 if (current_nr_blocks <= 1)
7517 /* Sanity check. There should be no REG_DEAD notes leftover at the end.
7518 In practice, this can occur as the result of bugs in flow, combine.c,
7519 and/or sched.c. The values of the REG_DEAD notes remaining are
7520 meaningless, because dead_notes is just used as a free list. */
7521 if (dead_notes != 0)
7525 /* restore line notes. */
7526 if (write_symbols != NO_DEBUG)
7528 for (bb = 0; bb < current_nr_blocks; bb++)
7529 restore_line_notes (bb);
7532 /* Done with this region */
7533 free_pending_lists ();
7535 FREE_REG_SET (reg_pending_sets);
7538 /* Subroutine of split_hard_reg_notes. Searches X for any reference to
7539 REGNO, returning the rtx of the reference found if any. Otherwise,
7543 regno_use_in (regno, x)
7551 if (GET_CODE (x) == REG && REGNO (x) == regno)
7554 fmt = GET_RTX_FORMAT (GET_CODE (x));
7555 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
7559 if ((tem = regno_use_in (regno, XEXP (x, i))))
7562 else if (fmt[i] == 'E')
7563 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
7564 if ((tem = regno_use_in (regno, XVECEXP (x, i, j))))
7571 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
7572 needed for the hard register mentioned in the note. This can happen
7573 if the reference to the hard register in the original insn was split into
7574 several smaller hard register references in the split insns. */
7577 split_hard_reg_notes (note, first, last)
7578 rtx note, first, last;
7580 rtx reg, temp, link;
7581 int n_regs, i, new_reg;
7584 /* Assume that this is a REG_DEAD note. */
7585 if (REG_NOTE_KIND (note) != REG_DEAD)
7588 reg = XEXP (note, 0);
7590 n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
7592 for (i = 0; i < n_regs; i++)
7594 new_reg = REGNO (reg) + i;
7596 /* Check for references to new_reg in the split insns. */
7597 for (insn = last;; insn = PREV_INSN (insn))
7599 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7600 && (temp = regno_use_in (new_reg, PATTERN (insn))))
7602 /* Create a new reg dead note ere. */
7603 link = alloc_EXPR_LIST (REG_DEAD, temp, REG_NOTES (insn));
7604 REG_NOTES (insn) = link;
7606 /* If killed multiple registers here, then add in the excess. */
7607 i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
7611 /* It isn't mentioned anywhere, so no new reg note is needed for
7619 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
7620 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
7623 new_insn_dead_notes (pat, insn, last, orig_insn)
7624 rtx pat, insn, last, orig_insn;
7628 /* PAT is either a CLOBBER or a SET here. */
7629 dest = XEXP (pat, 0);
7631 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
7632 || GET_CODE (dest) == STRICT_LOW_PART
7633 || GET_CODE (dest) == SIGN_EXTRACT)
7634 dest = XEXP (dest, 0);
7636 if (GET_CODE (dest) == REG)
7638 for (tem = last; tem != insn; tem = PREV_INSN (tem))
7640 if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
7641 && reg_overlap_mentioned_p (dest, PATTERN (tem))
7642 && (set = single_set (tem)))
7644 rtx tem_dest = SET_DEST (set);
7646 while (GET_CODE (tem_dest) == ZERO_EXTRACT
7647 || GET_CODE (tem_dest) == SUBREG
7648 || GET_CODE (tem_dest) == STRICT_LOW_PART
7649 || GET_CODE (tem_dest) == SIGN_EXTRACT)
7650 tem_dest = XEXP (tem_dest, 0);
7652 if (!rtx_equal_p (tem_dest, dest))
7654 /* Use the same scheme as combine.c, don't put both REG_DEAD
7655 and REG_UNUSED notes on the same insn. */
7656 if (!find_regno_note (tem, REG_UNUSED, REGNO (dest))
7657 && !find_regno_note (tem, REG_DEAD, REGNO (dest)))
7659 rtx note = alloc_EXPR_LIST (REG_DEAD, dest,
7661 REG_NOTES (tem) = note;
7663 /* The reg only dies in one insn, the last one that uses
7667 else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
7668 /* We found an instruction that both uses the register,
7669 and sets it, so no new REG_NOTE is needed for this set. */
7673 /* If this is a set, it must die somewhere, unless it is the dest of
7674 the original insn, and hence is live after the original insn. Abort
7675 if it isn't supposed to be live after the original insn.
7677 If this is a clobber, then just add a REG_UNUSED note. */
7680 int live_after_orig_insn = 0;
7681 rtx pattern = PATTERN (orig_insn);
7684 if (GET_CODE (pat) == CLOBBER)
7686 rtx note = alloc_EXPR_LIST (REG_UNUSED, dest, REG_NOTES (insn));
7687 REG_NOTES (insn) = note;
7691 /* The original insn could have multiple sets, so search the
7692 insn for all sets. */
7693 if (GET_CODE (pattern) == SET)
7695 if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
7696 live_after_orig_insn = 1;
7698 else if (GET_CODE (pattern) == PARALLEL)
7700 for (i = 0; i < XVECLEN (pattern, 0); i++)
7701 if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
7702 && reg_overlap_mentioned_p (dest,
7703 SET_DEST (XVECEXP (pattern,
7705 live_after_orig_insn = 1;
7708 if (!live_after_orig_insn)
7714 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
7715 registers modified by X. INC is -1 if the containing insn is being deleted,
7716 and is 1 if the containing insn is a newly generated insn. */
7719 update_n_sets (x, inc)
7723 rtx dest = SET_DEST (x);
7725 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
7726 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
7727 dest = SUBREG_REG (dest);
7729 if (GET_CODE (dest) == REG)
7731 int regno = REGNO (dest);
7733 if (regno < FIRST_PSEUDO_REGISTER)
7736 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
7738 for (i = regno; i < endregno; i++)
7739 REG_N_SETS (i) += inc;
7742 REG_N_SETS (regno) += inc;
7746 /* Updates all flow-analysis related quantities (including REG_NOTES) for
7747 the insns from FIRST to LAST inclusive that were created by splitting
7748 ORIG_INSN. NOTES are the original REG_NOTES. */
7751 update_flow_info (notes, first, last, orig_insn)
7758 rtx orig_dest, temp;
7761 /* Get and save the destination set by the original insn. */
7763 orig_dest = single_set (orig_insn);
7765 orig_dest = SET_DEST (orig_dest);
7767 /* Move REG_NOTES from the original insn to where they now belong. */
7769 for (note = notes; note; note = next)
7771 next = XEXP (note, 1);
7772 switch (REG_NOTE_KIND (note))
7776 /* Move these notes from the original insn to the last new insn where
7777 the register is now set. */
7779 for (insn = last;; insn = PREV_INSN (insn))
7781 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7782 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
7784 /* If this note refers to a multiple word hard register, it
7785 may have been split into several smaller hard register
7786 references, so handle it specially. */
7787 temp = XEXP (note, 0);
7788 if (REG_NOTE_KIND (note) == REG_DEAD
7789 && GET_CODE (temp) == REG
7790 && REGNO (temp) < FIRST_PSEUDO_REGISTER
7791 && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
7792 split_hard_reg_notes (note, first, last);
7795 XEXP (note, 1) = REG_NOTES (insn);
7796 REG_NOTES (insn) = note;
7799 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
7801 /* ??? This won't handle multiple word registers correctly,
7802 but should be good enough for now. */
7803 if (REG_NOTE_KIND (note) == REG_UNUSED
7804 && GET_CODE (XEXP (note, 0)) != SCRATCH
7805 && !dead_or_set_p (insn, XEXP (note, 0)))
7806 PUT_REG_NOTE_KIND (note, REG_DEAD);
7808 /* The reg only dies in one insn, the last one that uses
7812 /* It must die somewhere, fail it we couldn't find where it died.
7814 If this is a REG_UNUSED note, then it must be a temporary
7815 register that was not needed by this instantiation of the
7816 pattern, so we can safely ignore it. */
7819 /* After reload, REG_DEAD notes come sometimes an
7820 instruction after the register actually dies. */
7821 if (reload_completed && REG_NOTE_KIND (note) == REG_DEAD)
7823 XEXP (note, 1) = REG_NOTES (insn);
7824 REG_NOTES (insn) = note;
7828 if (REG_NOTE_KIND (note) != REG_UNUSED)
7837 /* If the insn that set the register to 0 was deleted, this
7838 note cannot be relied on any longer. The destination might
7839 even have been moved to memory.
7840 This was observed for SH4 with execute/920501-6.c compilation,
7841 -O2 -fomit-frame-pointer -finline-functions . */
7842 if (GET_CODE (XEXP (note, 0)) == NOTE
7843 || INSN_DELETED_P (XEXP (note, 0)))
7845 /* This note applies to the dest of the original insn. Find the
7846 first new insn that now has the same dest, and move the note
7852 for (insn = first;; insn = NEXT_INSN (insn))
7854 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7855 && (temp = single_set (insn))
7856 && rtx_equal_p (SET_DEST (temp), orig_dest))
7858 XEXP (note, 1) = REG_NOTES (insn);
7859 REG_NOTES (insn) = note;
7860 /* The reg is only zero before one insn, the first that
7864 /* If this note refers to a multiple word hard
7865 register, it may have been split into several smaller
7866 hard register references. We could split the notes,
7867 but simply dropping them is good enough. */
7868 if (GET_CODE (orig_dest) == REG
7869 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
7870 && HARD_REGNO_NREGS (REGNO (orig_dest),
7871 GET_MODE (orig_dest)) > 1)
7873 /* It must be set somewhere, fail if we couldn't find where it
7882 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
7883 set is meaningless. Just drop the note. */
7887 case REG_NO_CONFLICT:
7888 /* These notes apply to the dest of the original insn. Find the last
7889 new insn that now has the same dest, and move the note there. */
7894 for (insn = last;; insn = PREV_INSN (insn))
7896 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7897 && (temp = single_set (insn))
7898 && rtx_equal_p (SET_DEST (temp), orig_dest))
7900 XEXP (note, 1) = REG_NOTES (insn);
7901 REG_NOTES (insn) = note;
7902 /* Only put this note on one of the new insns. */
7906 /* The original dest must still be set someplace. Abort if we
7907 couldn't find it. */
7910 /* However, if this note refers to a multiple word hard
7911 register, it may have been split into several smaller
7912 hard register references. We could split the notes,
7913 but simply dropping them is good enough. */
7914 if (GET_CODE (orig_dest) == REG
7915 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
7916 && HARD_REGNO_NREGS (REGNO (orig_dest),
7917 GET_MODE (orig_dest)) > 1)
7919 /* Likewise for multi-word memory references. */
7920 if (GET_CODE (orig_dest) == MEM
7921 && SIZE_FOR_MODE (orig_dest) > MOVE_MAX)
7929 /* Move a REG_LIBCALL note to the first insn created, and update
7930 the corresponding REG_RETVAL note. */
7931 XEXP (note, 1) = REG_NOTES (first);
7932 REG_NOTES (first) = note;
7934 insn = XEXP (note, 0);
7935 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
7937 XEXP (note, 0) = first;
7940 case REG_EXEC_COUNT:
7941 /* Move a REG_EXEC_COUNT note to the first insn created. */
7942 XEXP (note, 1) = REG_NOTES (first);
7943 REG_NOTES (first) = note;
7947 /* Move a REG_RETVAL note to the last insn created, and update
7948 the corresponding REG_LIBCALL note. */
7949 XEXP (note, 1) = REG_NOTES (last);
7950 REG_NOTES (last) = note;
7952 insn = XEXP (note, 0);
7953 note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
7955 XEXP (note, 0) = last;
7960 /* This should be moved to whichever instruction is a JUMP_INSN. */
7962 for (insn = last;; insn = PREV_INSN (insn))
7964 if (GET_CODE (insn) == JUMP_INSN)
7966 XEXP (note, 1) = REG_NOTES (insn);
7967 REG_NOTES (insn) = note;
7968 /* Only put this note on one of the new insns. */
7971 /* Fail if we couldn't find a JUMP_INSN. */
7978 /* reload sometimes leaves obsolete REG_INC notes around. */
7979 if (reload_completed)
7981 /* This should be moved to whichever instruction now has the
7982 increment operation. */
7986 /* Should be moved to the new insn(s) which use the label. */
7987 for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
7988 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7989 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
7991 REG_NOTES (insn) = alloc_EXPR_LIST (REG_LABEL,
7999 /* These two notes will never appear until after reorg, so we don't
8000 have to handle them here. */
8006 /* Each new insn created, except the last, has a new set. If the destination
8007 is a register, then this reg is now live across several insns, whereas
8008 previously the dest reg was born and died within the same insn. To
8009 reflect this, we now need a REG_DEAD note on the insn where this
8012 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
8014 for (insn = first; insn != last; insn = NEXT_INSN (insn))
8019 pat = PATTERN (insn);
8020 if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
8021 new_insn_dead_notes (pat, insn, last, orig_insn);
8022 else if (GET_CODE (pat) == PARALLEL)
8024 for (i = 0; i < XVECLEN (pat, 0); i++)
8025 if (GET_CODE (XVECEXP (pat, 0, i)) == SET
8026 || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
8027 new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
8031 /* If any insn, except the last, uses the register set by the last insn,
8032 then we need a new REG_DEAD note on that insn. In this case, there
8033 would not have been a REG_DEAD note for this register in the original
8034 insn because it was used and set within one insn. */
8036 set = single_set (last);
8039 rtx dest = SET_DEST (set);
8041 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
8042 || GET_CODE (dest) == STRICT_LOW_PART
8043 || GET_CODE (dest) == SIGN_EXTRACT)
8044 dest = XEXP (dest, 0);
8046 if (GET_CODE (dest) == REG
8047 /* Global registers are always live, so the code below does not
8049 && (REGNO (dest) >= FIRST_PSEUDO_REGISTER
8050 || ! global_regs[REGNO (dest)]))
8052 rtx stop_insn = PREV_INSN (first);
8054 /* If the last insn uses the register that it is setting, then
8055 we don't want to put a REG_DEAD note there. Search backwards
8056 to find the first insn that sets but does not use DEST. */
8059 if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
8061 for (insn = PREV_INSN (insn); insn != first;
8062 insn = PREV_INSN (insn))
8064 if ((set = single_set (insn))
8065 && reg_mentioned_p (dest, SET_DEST (set))
8066 && ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
8071 /* Now find the first insn that uses but does not set DEST. */
8073 for (insn = PREV_INSN (insn); insn != stop_insn;
8074 insn = PREV_INSN (insn))
8076 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8077 && reg_mentioned_p (dest, PATTERN (insn))
8078 && (set = single_set (insn)))
8080 rtx insn_dest = SET_DEST (set);
8082 while (GET_CODE (insn_dest) == ZERO_EXTRACT
8083 || GET_CODE (insn_dest) == SUBREG
8084 || GET_CODE (insn_dest) == STRICT_LOW_PART
8085 || GET_CODE (insn_dest) == SIGN_EXTRACT)
8086 insn_dest = XEXP (insn_dest, 0);
8088 if (insn_dest != dest)
8090 note = alloc_EXPR_LIST (REG_DEAD, dest, REG_NOTES (insn));
8091 REG_NOTES (insn) = note;
8092 /* The reg only dies in one insn, the last one
8101 /* If the original dest is modifying a multiple register target, and the
8102 original instruction was split such that the original dest is now set
8103 by two or more SUBREG sets, then the split insns no longer kill the
8104 destination of the original insn.
8106 In this case, if there exists an instruction in the same basic block,
8107 before the split insn, which uses the original dest, and this use is
8108 killed by the original insn, then we must remove the REG_DEAD note on
8109 this insn, because it is now superfluous.
8111 This does not apply when a hard register gets split, because the code
8112 knows how to handle overlapping hard registers properly. */
8113 if (orig_dest && GET_CODE (orig_dest) == REG)
8115 int found_orig_dest = 0;
8116 int found_split_dest = 0;
8118 for (insn = first;; insn = NEXT_INSN (insn))
8123 /* I'm not sure if this can happen, but let's be safe. */
8124 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
8127 pat = PATTERN (insn);
8128 i = GET_CODE (pat) == PARALLEL ? XVECLEN (pat, 0) : 0;
8133 if (GET_CODE (set) == SET)
8135 if (GET_CODE (SET_DEST (set)) == REG
8136 && REGNO (SET_DEST (set)) == REGNO (orig_dest))
8138 found_orig_dest = 1;
8141 else if (GET_CODE (SET_DEST (set)) == SUBREG
8142 && SUBREG_REG (SET_DEST (set)) == orig_dest)
8144 found_split_dest = 1;
8150 set = XVECEXP (pat, 0, i);
8157 if (found_split_dest)
8159 /* Search backwards from FIRST, looking for the first insn that uses
8160 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
8161 If we find an insn, and it has a REG_DEAD note, then delete the
8164 for (insn = first; insn; insn = PREV_INSN (insn))
8166 if (GET_CODE (insn) == CODE_LABEL
8167 || GET_CODE (insn) == JUMP_INSN)
8169 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
8170 && reg_mentioned_p (orig_dest, insn))
8172 note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
8174 remove_note (insn, note);
8178 else if (!found_orig_dest)
8180 /* This should never happen. */
8185 /* Update reg_n_sets. This is necessary to prevent local alloc from
8186 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
8187 a reg from set once to set multiple times. */
8190 rtx x = PATTERN (orig_insn);
8191 RTX_CODE code = GET_CODE (x);
8193 if (code == SET || code == CLOBBER)
8194 update_n_sets (x, -1);
8195 else if (code == PARALLEL)
8198 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8200 code = GET_CODE (XVECEXP (x, 0, i));
8201 if (code == SET || code == CLOBBER)
8202 update_n_sets (XVECEXP (x, 0, i), -1);
8206 for (insn = first;; insn = NEXT_INSN (insn))
8209 code = GET_CODE (x);
8211 if (code == SET || code == CLOBBER)
8212 update_n_sets (x, 1);
8213 else if (code == PARALLEL)
8216 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
8218 code = GET_CODE (XVECEXP (x, 0, i));
8219 if (code == SET || code == CLOBBER)
8220 update_n_sets (XVECEXP (x, 0, i), 1);
8230 /* Do the splitting of insns in the block b. */
8233 split_block_insns (b)
8238 for (insn = basic_block_head[b];; insn = next)
8240 rtx set, last, first, notes;
8242 /* Can't use `next_real_insn' because that
8243 might go across CODE_LABELS and short-out basic blocks. */
8244 next = NEXT_INSN (insn);
8245 if (GET_CODE (insn) != INSN)
8247 if (insn == basic_block_end[b])
8253 /* Don't split no-op move insns. These should silently disappear
8254 later in final. Splitting such insns would break the code
8255 that handles REG_NO_CONFLICT blocks. */
8256 set = single_set (insn);
8257 if (set && rtx_equal_p (SET_SRC (set), SET_DEST (set)))
8259 if (insn == basic_block_end[b])
8262 /* Nops get in the way while scheduling, so delete them now if
8263 register allocation has already been done. It is too risky
8264 to try to do this before register allocation, and there are
8265 unlikely to be very many nops then anyways. */
8266 if (reload_completed)
8268 PUT_CODE (insn, NOTE);
8269 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
8270 NOTE_SOURCE_FILE (insn) = 0;
8276 /* Split insns here to get max fine-grain parallelism. */
8277 first = PREV_INSN (insn);
8278 notes = REG_NOTES (insn);
8279 last = try_split (PATTERN (insn), insn, 1);
8282 /* try_split returns the NOTE that INSN became. */
8283 first = NEXT_INSN (first);
8284 update_flow_info (notes, first, last, insn);
8286 PUT_CODE (insn, NOTE);
8287 NOTE_SOURCE_FILE (insn) = 0;
8288 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
8289 if (insn == basic_block_head[b])
8290 basic_block_head[b] = first;
8291 if (insn == basic_block_end[b])
8293 basic_block_end[b] = last;
8298 if (insn == basic_block_end[b])
8303 /* The one entry point in this file. DUMP_FILE is the dump file for
8307 schedule_insns (dump_file)
8318 /* disable speculative loads in their presence if cc0 defined */
8320 flag_schedule_speculative_load = 0;
8323 /* Taking care of this degenerate case makes the rest of
8324 this code simpler. */
8325 if (n_basic_blocks == 0)
8328 /* set dump and sched_verbose for the desired debugging output. If no
8329 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
8330 For -fsched-verbose-N, N>=10, print everything to stderr. */
8331 sched_verbose = sched_verbose_param;
8332 if (sched_verbose_param == 0 && dump_file)
8334 dump = ((sched_verbose_param >= 10 || !dump_file) ? stderr : dump_file);
8339 /* Initialize the unused_*_lists. We can't use the ones left over from
8340 the previous function, because gcc has freed that memory. We can use
8341 the ones left over from the first sched pass in the second pass however,
8342 so only clear them on the first sched pass. The first pass is before
8343 reload if flag_schedule_insns is set, otherwise it is afterwards. */
8345 if (reload_completed == 0 || !flag_schedule_insns)
8347 unused_insn_list = 0;
8348 unused_expr_list = 0;
8351 /* initialize issue_rate */
8352 issue_rate = ISSUE_RATE;
8354 /* do the splitting first for all blocks */
8355 for (b = 0; b < n_basic_blocks; b++)
8356 split_block_insns (b);
8358 max_uid = (get_max_uid () + 1);
8360 cant_move = (char *) alloca (max_uid * sizeof (char));
8361 bzero ((char *) cant_move, max_uid * sizeof (char));
8363 fed_by_spec_load = (char *) alloca (max_uid * sizeof (char));
8364 bzero ((char *) fed_by_spec_load, max_uid * sizeof (char));
8366 is_load_insn = (char *) alloca (max_uid * sizeof (char));
8367 bzero ((char *) is_load_insn, max_uid * sizeof (char));
8369 insn_orig_block = (int *) alloca (max_uid * sizeof (int));
8370 insn_luid = (int *) alloca (max_uid * sizeof (int));
8373 for (b = 0; b < n_basic_blocks; b++)
8374 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
8376 INSN_BLOCK (insn) = b;
8377 INSN_LUID (insn) = luid++;
8379 if (insn == basic_block_end[b])
8383 /* after reload, remove inter-blocks dependences computed before reload. */
8384 if (reload_completed)
8389 for (b = 0; b < n_basic_blocks; b++)
8390 for (insn = basic_block_head[b];; insn = NEXT_INSN (insn))
8394 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
8397 link = LOG_LINKS (insn);
8400 rtx x = XEXP (link, 0);
8402 if (INSN_BLOCK (x) != b)
8404 remove_dependence (insn, x);
8405 link = prev ? XEXP (prev, 1) : LOG_LINKS (insn);
8408 prev = link, link = XEXP (prev, 1);
8412 if (insn == basic_block_end[b])
8418 rgn_table = (region *) alloca ((n_basic_blocks) * sizeof (region));
8419 rgn_bb_table = (int *) alloca ((n_basic_blocks) * sizeof (int));
8420 block_to_bb = (int *) alloca ((n_basic_blocks) * sizeof (int));
8421 containing_rgn = (int *) alloca ((n_basic_blocks) * sizeof (int));
8423 /* compute regions for scheduling */
8424 if (reload_completed
8425 || n_basic_blocks == 1
8426 || !flag_schedule_interblock)
8428 find_single_block_region ();
8432 /* verify that a 'good' control flow graph can be built */
8433 if (is_cfg_nonregular ())
8435 find_single_block_region ();
8439 /* build_control_flow will return nonzero if it detects unreachable
8440 blocks or any other irregularity with the cfg which prevents
8441 cross block scheduling. */
8442 if (build_control_flow () != 0)
8443 find_single_block_region ();
8447 if (sched_verbose >= 3)
8449 debug_control_flow ();
8456 /* Allocate data for this pass. See comments, above,
8457 for what these vectors do. */
8458 insn_priority = (int *) alloca (max_uid * sizeof (int));
8459 insn_reg_weight = (int *) alloca (max_uid * sizeof (int));
8460 insn_tick = (int *) alloca (max_uid * sizeof (int));
8461 insn_costs = (short *) alloca (max_uid * sizeof (short));
8462 insn_units = (short *) alloca (max_uid * sizeof (short));
8463 insn_blockage = (unsigned int *) alloca (max_uid * sizeof (unsigned int));
8464 insn_ref_count = (int *) alloca (max_uid * sizeof (int));
8466 /* Allocate for forward dependencies */
8467 insn_dep_count = (int *) alloca (max_uid * sizeof (int));
8468 insn_depend = (rtx *) alloca (max_uid * sizeof (rtx));
8470 if (reload_completed == 0)
8474 sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
8475 sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
8476 sched_reg_basic_block = (int *) alloca (max_regno * sizeof (int));
8477 bb_live_regs = ALLOCA_REG_SET ();
8478 bzero ((char *) sched_reg_n_calls_crossed, max_regno * sizeof (int));
8479 bzero ((char *) sched_reg_live_length, max_regno * sizeof (int));
8481 for (i = 0; i < max_regno; i++)
8482 sched_reg_basic_block[i] = REG_BLOCK_UNKNOWN;
8486 sched_reg_n_calls_crossed = 0;
8487 sched_reg_live_length = 0;
8490 init_alias_analysis ();
8492 if (write_symbols != NO_DEBUG)
8496 line_note = (rtx *) alloca (max_uid * sizeof (rtx));
8497 bzero ((char *) line_note, max_uid * sizeof (rtx));
8498 line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
8499 bzero ((char *) line_note_head, n_basic_blocks * sizeof (rtx));
8501 /* Save-line-note-head:
8502 Determine the line-number at the start of each basic block.
8503 This must be computed and saved now, because after a basic block's
8504 predecessor has been scheduled, it is impossible to accurately
8505 determine the correct line number for the first insn of the block. */
8507 for (b = 0; b < n_basic_blocks; b++)
8508 for (line = basic_block_head[b]; line; line = PREV_INSN (line))
8509 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
8511 line_note_head[b] = line;
8516 bzero ((char *) insn_priority, max_uid * sizeof (int));
8517 bzero ((char *) insn_reg_weight, max_uid * sizeof (int));
8518 bzero ((char *) insn_tick, max_uid * sizeof (int));
8519 bzero ((char *) insn_costs, max_uid * sizeof (short));
8520 bzero ((char *) insn_units, max_uid * sizeof (short));
8521 bzero ((char *) insn_blockage, max_uid * sizeof (unsigned int));
8522 bzero ((char *) insn_ref_count, max_uid * sizeof (int));
8524 /* Initialize for forward dependencies */
8525 bzero ((char *) insn_depend, max_uid * sizeof (rtx));
8526 bzero ((char *) insn_dep_count, max_uid * sizeof (int));
8528 /* Find units used in this fuction, for visualization */
8530 init_target_units ();
8532 /* ??? Add a NOTE after the last insn of the last basic block. It is not
8533 known why this is done. */
8535 insn = basic_block_end[n_basic_blocks - 1];
8536 if (NEXT_INSN (insn) == 0
8537 || (GET_CODE (insn) != NOTE
8538 && GET_CODE (insn) != CODE_LABEL
8539 /* Don't emit a NOTE if it would end up between an unconditional
8540 jump and a BARRIER. */
8541 && !(GET_CODE (insn) == JUMP_INSN
8542 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
8543 emit_note_after (NOTE_INSN_DELETED, basic_block_end[n_basic_blocks - 1]);
8545 /* Schedule every region in the subroutine */
8546 for (rgn = 0; rgn < nr_regions; rgn++)
8548 schedule_region (rgn);
8555 /* Reposition the prologue and epilogue notes in case we moved the
8556 prologue/epilogue insns. */
8557 if (reload_completed)
8558 reposition_prologue_and_epilogue_notes (get_insns ());
8560 /* delete redundant line notes. */
8561 if (write_symbols != NO_DEBUG)
8562 rm_redundant_line_notes ();
8564 /* Update information about uses of registers in the subroutine. */
8565 if (reload_completed == 0)
8566 update_reg_usage ();
8570 if (reload_completed == 0 && flag_schedule_interblock)
8572 fprintf (dump, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8580 fprintf (dump, "\n\n");
8584 FREE_REG_SET (bb_live_regs);
8603 #endif /* INSN_SCHEDULING */