1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 93-97, 1998 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to the Free
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
24 /* Instruction scheduling pass.
26 This pass implements list scheduling within basic blocks. It is
27 run twice: (1) after flow analysis, but before register allocation,
28 and (2) after register allocation.
30 The first run performs interblock scheduling, moving insns between
31 different blocks in the same "region", and the second runs only
32 basic block scheduling.
34 Interblock motions performed are useful motions and speculative
35 motions, including speculative loads. Motions requiring code
36 duplication are not supported. The identification of motion type
37 and the check for validity of speculative motions requires
38 construction and analysis of the function's control flow graph.
39 The scheduler works as follows:
41 We compute insn priorities based on data dependencies. Flow
42 analysis only creates a fraction of the data-dependencies we must
43 observe: namely, only those dependencies which the combiner can be
44 expected to use. For this pass, we must therefore create the
45 remaining dependencies we need to observe: register dependencies,
46 memory dependencies, dependencies to keep function calls in order,
47 and the dependence between a conditional branch and the setting of
48 condition codes are all dealt with here.
50 The scheduler first traverses the data flow graph, starting with
51 the last instruction, and proceeding to the first, assigning values
52 to insn_priority as it goes. This sorts the instructions
53 topologically by data dependence.
55 Once priorities have been established, we order the insns using
56 list scheduling. This works as follows: starting with a list of
57 all the ready insns, and sorted according to priority number, we
58 schedule the insn from the end of the list by placing its
59 predecessors in the list according to their priority order. We
60 consider this insn scheduled by setting the pointer to the "end" of
61 the list to point to the previous insn. When an insn has no
62 predecessors, we either queue it until sufficient time has elapsed
63 or add it to the ready list. As the instructions are scheduled or
64 when stalls are introduced, the queue advances and dumps insns into
65 the ready list. When all insns down to the lowest priority have
66 been scheduled, the critical path of the basic block has been made
67 as short as possible. The remaining insns are then scheduled in
70 Function unit conflicts are resolved during forward list scheduling
71 by tracking the time when each insn is committed to the schedule
72 and from that, the time the function units it uses must be free.
73 As insns on the ready list are considered for scheduling, those
74 that would result in a blockage of the already committed insns are
75 queued until no blockage will result.
77 The following list shows the order in which we want to break ties
78 among insns in the ready list:
80 1. choose insn with the longest path to end of bb, ties
82 2. choose insn with least contribution to register pressure,
84 3. prefer in-block upon interblock motion, ties broken by
85 4. prefer useful upon speculative motion, ties broken by
86 5. choose insn with largest control flow probability, ties
88 6. choose insn with the least dependences upon the previously
89 scheduled insn, or finally
90 7. choose insn with lowest UID.
92 Memory references complicate matters. Only if we can be certain
93 that memory references are not part of the data dependency graph
94 (via true, anti, or output dependence), can we move operations past
95 memory references. To first approximation, reads can be done
96 independently, while writes introduce dependencies. Better
97 approximations will yield fewer dependencies.
99 Before reload, an extended analysis of interblock data dependences
100 is required for interblock scheduling. This is performed in
101 compute_block_backward_dependences ().
103 Dependencies set up by memory references are treated in exactly the
104 same way as other dependencies, by using LOG_LINKS backward
105 dependences. LOG_LINKS are translated into INSN_DEPEND forward
106 dependences for the purpose of forward list scheduling.
108 Having optimized the critical path, we may have also unduly
109 extended the lifetimes of some registers. If an operation requires
110 that constants be loaded into registers, it is certainly desirable
111 to load those constants as early as necessary, but no earlier.
112 I.e., it will not do to load up a bunch of registers at the
113 beginning of a basic block only to use them at the end, if they
114 could be loaded later, since this may result in excessive register
117 Note that since branches are never in basic blocks, but only end
118 basic blocks, this pass will not move branches. But that is ok,
119 since we can use GNU's delayed branch scheduling pass to take care
122 Also note that no further optimizations based on algebraic
123 identities are performed, so this pass would be a good one to
124 perform instruction splitting, such as breaking up a multiply
125 instruction into shifts and adds where that is profitable.
127 Given the memory aliasing analysis that this pass should perform,
128 it should be possible to remove redundant stores to memory, and to
129 load values from registers instead of hitting memory.
131 Before reload, speculative insns are moved only if a 'proof' exists
132 that no exception will be caused by this, and if no live registers
133 exist that inhibit the motion (live registers constraints are not
134 represented by data dependence edges).
136 This pass must update information that subsequent passes expect to
137 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
138 reg_n_calls_crossed, and reg_live_length. Also, basic_block_head,
141 The information in the line number notes is carefully retained by
142 this pass. Notes that refer to the starting and ending of
143 exception regions are also carefully retained by this pass. All
144 other NOTE insns are grouped in their same relative order at the
145 beginning of basic blocks and regions that have been scheduled.
147 The main entry point for this pass is schedule_insns(), called for
148 each function. The work of the scheduler is organized in three
149 levels: (1) function level: insns are subject to splitting,
150 control-flow-graph is constructed, regions are computed (after
151 reload, each region is of one block), (2) region level: control
152 flow graph attributes required for interblock scheduling are
153 computed (dominators, reachability, etc.), data dependences and
154 priorities are computed, and (3) block level: insns in the block
155 are actually scheduled. */
160 #include "basic-block.h"
162 #include "hard-reg-set.h"
164 #include "insn-config.h"
165 #include "insn-attr.h"
168 extern char *reg_known_equiv_p
;
169 extern rtx
*reg_known_value
;
171 #ifdef INSN_SCHEDULING
173 /* enable interblock scheduling code */
175 /* define INTERBLOCK_DEBUG for using the -fsched-max debugging facility */
176 /* #define INTERBLOCK_DEBUG */
178 /* target_units bitmask has 1 for each unit in the cpu. It should be
179 possible to compute this variable from the machine description.
180 But currently it is computed by examinning the insn list. Since
181 this is only needed for visualization, it seems an acceptable
182 solution. (For understanding the mapping of bits to units, see
183 definition of function_units[] in "insn-attrtab.c") */
185 static int target_units
= 0;
187 /* issue_rate is the number of insns that can be scheduled in the same
188 machine cycle. It can be defined in the config/mach/mach.h file,
189 otherwise we set it to 1. */
191 static int issue_rate
;
197 /* sched_debug_count is used for debugging the scheduler by limiting
198 the number of scheduled insns. It is controlled by the option
199 -fsched-max-N (N is a number).
201 sched-verbose controls the amount of debugging output the
202 scheduler prints. It is controlled by -fsched-verbose-N:
203 N>0 and no -DSR : the output is directed to stderr.
204 N>=10 will direct the printouts to stderr (regardless of -dSR).
206 N=2: bb's probabilities, detailed ready list info, unit/insn info.
207 N=3: rtl at abort point, control-flow, regions info.
208 N=5: dependences info.
210 max_rgn_blocks and max_region_insns limit region size for
211 interblock scheduling. They are controlled by
212 -fsched-interblock-max-blocks-N, -fsched-interblock-max-insns-N */
214 #define MAX_RGN_BLOCKS 10
215 #define MAX_RGN_INSNS 100
217 static int sched_debug_count
= -1;
218 static int sched_verbose_param
= 0;
219 static int sched_verbose
= 0;
220 static int max_rgn_blocks
= MAX_RGN_BLOCKS
;
221 static int max_rgn_insns
= MAX_RGN_INSNS
;
223 /* nr_inter/spec counts interblock/speculative motion for the function */
224 static int nr_inter
, nr_spec
;
227 /* debugging file. all printouts are sent to dump, which is always set,
228 either to stderr, or to the dump listing file (-dRS). */
229 static FILE *dump
= 0;
231 /* fix_sched_param() is called from toplev.c upon detection
232 of the -fsched-***-N options. */
235 fix_sched_param (param
, val
)
238 if (!strcmp (param
, "max"))
239 sched_debug_count
= ((sched_debug_count
== -1) ?
240 atoi (val
) : sched_debug_count
);
241 else if (!strcmp (param
, "verbose"))
242 sched_verbose_param
= atoi (val
);
243 else if (!strcmp (param
, "interblock-max-blocks"))
244 max_rgn_blocks
= atoi (val
);
245 else if (!strcmp (param
, "interblock-max-insns"))
246 max_rgn_insns
= atoi (val
);
248 warning ("fix_sched_param: unknown param: %s", param
);
252 /* Arrays set up by scheduling for the same respective purposes as
253 similar-named arrays set up by flow analysis. We work with these
254 arrays during the scheduling pass so we can compare values against
257 Values of these arrays are copied at the end of this pass into the
258 arrays set up by flow analysis. */
259 static int *sched_reg_n_calls_crossed
;
260 static int *sched_reg_live_length
;
261 static int *sched_reg_basic_block
;
263 /* We need to know the current block number during the post scheduling
264 update of live register information so that we can also update
265 REG_BASIC_BLOCK if a register changes blocks. */
266 static int current_block_num
;
268 /* Element N is the next insn that sets (hard or pseudo) register
269 N within the current basic block; or zero, if there is no
270 such insn. Needed for new registers which may be introduced
271 by splitting insns. */
272 static rtx
*reg_last_uses
;
273 static rtx
*reg_last_sets
;
274 static regset reg_pending_sets
;
275 static int reg_pending_sets_all
;
277 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
278 static int *insn_luid
;
279 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
281 /* Vector indexed by INSN_UID giving each instruction a priority. */
282 static int *insn_priority
;
283 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
285 static short *insn_costs
;
286 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
288 /* Vector indexed by INSN_UID giving an encoding of the function units
290 static short *insn_units
;
291 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
293 /* Vector indexed by INSN_UID giving each instruction a register-weight.
294 This weight is an estimation of the insn contribution to registers pressure. */
295 static int *insn_reg_weight
;
296 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
298 /* Vector indexed by INSN_UID giving list of insns which
299 depend upon INSN. Unlike LOG_LINKS, it represents forward dependences. */
300 static rtx
*insn_depend
;
301 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
303 /* Vector indexed by INSN_UID. Initialized to the number of incoming
304 edges in forward dependence graph (= number of LOG_LINKS). As
305 scheduling procedes, dependence counts are decreased. An
306 instruction moves to the ready list when its counter is zero. */
307 static int *insn_dep_count
;
308 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
310 /* Vector indexed by INSN_UID giving an encoding of the blockage range
311 function. The unit and the range are encoded. */
312 static unsigned int *insn_blockage
;
313 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
315 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
316 #define ENCODE_BLOCKAGE(U, R) \
317 ((((U) << UNIT_BITS) << BLOCKAGE_BITS \
318 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
319 | MAX_BLOCKAGE_COST (R))
320 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
321 #define BLOCKAGE_RANGE(B) \
322 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
323 | ((B) & BLOCKAGE_MASK))
325 /* Encodings of the `<name>_unit_blockage_range' function. */
326 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
327 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
329 #define DONE_PRIORITY -1
330 #define MAX_PRIORITY 0x7fffffff
331 #define TAIL_PRIORITY 0x7ffffffe
332 #define LAUNCH_PRIORITY 0x7f000001
333 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
334 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
336 /* Vector indexed by INSN_UID giving number of insns referring to this insn. */
337 static int *insn_ref_count
;
338 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
340 /* Vector indexed by INSN_UID giving line-number note in effect for each
341 insn. For line-number notes, this indicates whether the note may be
343 static rtx
*line_note
;
344 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
346 /* Vector indexed by basic block number giving the starting line-number
347 for each basic block. */
348 static rtx
*line_note_head
;
350 /* List of important notes we must keep around. This is a pointer to the
351 last element in the list. */
352 static rtx note_list
;
354 /* Regsets telling whether a given register is live or dead before the last
355 scheduled insn. Must scan the instructions once before scheduling to
356 determine what registers are live or dead at the end of the block. */
357 static regset bb_live_regs
;
359 /* Regset telling whether a given register is live after the insn currently
360 being scheduled. Before processing an insn, this is equal to bb_live_regs
361 above. This is used so that we can find registers that are newly born/dead
362 after processing an insn. */
363 static regset old_live_regs
;
365 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
366 during the initial scan and reused later. If there are not exactly as
367 many REG_DEAD notes in the post scheduled code as there were in the
368 prescheduled code then we trigger an abort because this indicates a bug. */
369 static rtx dead_notes
;
373 /* An instruction is ready to be scheduled when all insns preceding it
374 have already been scheduled. It is important to ensure that all
375 insns which use its result will not be executed until its result
376 has been computed. An insn is maintained in one of four structures:
378 (P) the "Pending" set of insns which cannot be scheduled until
379 their dependencies have been satisfied.
380 (Q) the "Queued" set of insns that can be scheduled when sufficient
382 (R) the "Ready" list of unscheduled, uncommitted insns.
383 (S) the "Scheduled" list of insns.
385 Initially, all insns are either "Pending" or "Ready" depending on
386 whether their dependencies are satisfied.
388 Insns move from the "Ready" list to the "Scheduled" list as they
389 are committed to the schedule. As this occurs, the insns in the
390 "Pending" list have their dependencies satisfied and move to either
391 the "Ready" list or the "Queued" set depending on whether
392 sufficient time has passed to make them ready. As time passes,
393 insns move from the "Queued" set to the "Ready" list. Insns may
394 move from the "Ready" list to the "Queued" set if they are blocked
395 due to a function unit conflict.
397 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
398 insns, i.e., those that are ready, queued, and pending.
399 The "Queued" set (Q) is implemented by the variable `insn_queue'.
400 The "Ready" list (R) is implemented by the variables `ready' and
402 The "Scheduled" list (S) is the new insn chain built by this pass.
404 The transition (R->S) is implemented in the scheduling loop in
405 `schedule_block' when the best insn to schedule is chosen.
406 The transition (R->Q) is implemented in `queue_insn' when an
407 insn is found to to have a function unit conflict with the already
409 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
410 insns move from the ready list to the scheduled list.
411 The transition (Q->R) is implemented in 'queue_to_insn' as time
412 passes or stalls are introduced. */
414 /* Implement a circular buffer to delay instructions until sufficient
415 time has passed. INSN_QUEUE_SIZE is a power of two larger than
416 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
417 longest time an isnsn may be queued. */
418 static rtx insn_queue
[INSN_QUEUE_SIZE
];
419 static int q_ptr
= 0;
420 static int q_size
= 0;
421 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
422 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
424 /* Vector indexed by INSN_UID giving the minimum clock tick at which
425 the insn becomes ready. This is used to note timing constraints for
426 insns in the pending list. */
427 static int *insn_tick
;
428 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
430 /* Data structure for keeping track of register information
431 during that register's life. */
440 /* Forward declarations. */
441 static void add_dependence
PROTO ((rtx
, rtx
, enum reg_note
));
442 static void remove_dependence
PROTO ((rtx
, rtx
));
443 static rtx find_insn_list
PROTO ((rtx
, rtx
));
444 static int insn_unit
PROTO ((rtx
));
445 static unsigned int blockage_range
PROTO ((int, rtx
));
446 static void clear_units
PROTO ((void));
447 static int actual_hazard_this_instance
PROTO ((int, int, rtx
, int, int));
448 static void schedule_unit
PROTO ((int, rtx
, int));
449 static int actual_hazard
PROTO ((int, rtx
, int, int));
450 static int potential_hazard
PROTO ((int, rtx
, int));
451 static int insn_cost
PROTO ((rtx
, rtx
, rtx
));
452 static int priority
PROTO ((rtx
));
453 static void free_pending_lists
PROTO ((void));
454 static void add_insn_mem_dependence
PROTO ((rtx
*, rtx
*, rtx
, rtx
));
455 static void flush_pending_lists
PROTO ((rtx
, int));
456 static void sched_analyze_1
PROTO ((rtx
, rtx
));
457 static void sched_analyze_2
PROTO ((rtx
, rtx
));
458 static void sched_analyze_insn
PROTO ((rtx
, rtx
, rtx
));
459 static void sched_analyze
PROTO ((rtx
, rtx
));
460 static void sched_note_set
PROTO ((rtx
, int));
461 static int rank_for_schedule
PROTO ((rtx
*, rtx
*));
462 static void swap_sort
PROTO ((rtx
*, int));
463 static void queue_insn
PROTO ((rtx
, int));
464 static int schedule_insn
PROTO ((rtx
, rtx
*, int, int));
465 static void create_reg_dead_note
PROTO ((rtx
, rtx
));
466 static void attach_deaths
PROTO ((rtx
, rtx
, int));
467 static void attach_deaths_insn
PROTO ((rtx
));
468 static int new_sometimes_live
PROTO ((struct sometimes
*, int, int));
469 static void finish_sometimes_live
PROTO ((struct sometimes
*, int));
470 static int schedule_block
PROTO ((int, int));
471 static rtx regno_use_in
PROTO ((int, rtx
));
472 static void split_hard_reg_notes
PROTO ((rtx
, rtx
, rtx
));
473 static void new_insn_dead_notes
PROTO ((rtx
, rtx
, rtx
, rtx
));
474 static void update_n_sets
PROTO ((rtx
, int));
475 static void update_flow_info
PROTO ((rtx
, rtx
, rtx
, rtx
));
477 /* Main entry point of this file. */
478 void schedule_insns
PROTO ((FILE *));
480 /* Mapping of insns to their original block prior to scheduling. */
481 static int *insn_orig_block
;
482 #define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
484 /* Some insns (e.g. call) are not allowed to move across blocks. */
485 static char *cant_move
;
486 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
488 /* Control flow graph edges are kept in circular lists. */
497 static edge
*edge_table
;
499 #define NEXT_IN(edge) (edge_table[edge].next_in)
500 #define NEXT_OUT(edge) (edge_table[edge].next_out)
501 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
502 #define TO_BLOCK(edge) (edge_table[edge].to_block)
504 /* Number of edges in the control flow graph. (in fact larger than
505 that by 1, since edge 0 is unused.) */
508 /* Circular list of incoming/outgoing edges of a block */
509 static int *in_edges
;
510 static int *out_edges
;
512 #define IN_EDGES(block) (in_edges[block])
513 #define OUT_EDGES(block) (out_edges[block])
515 /* List of labels which cannot be deleted, needed for control
516 flow graph construction. */
517 extern rtx forced_labels
;
520 static char is_cfg_nonregular
PROTO ((void));
521 static int uses_reg_or_mem
PROTO ((rtx
));
522 void debug_control_flow
PROTO ((void));
523 static void build_control_flow
PROTO ((void));
524 static void build_jmp_edges
PROTO ((rtx
, int));
525 static void new_edge
PROTO ((int, int));
528 /* A region is the main entity for interblock scheduling: insns
529 are allowed to move between blocks in the same region, along
530 control flow graph edges, in the 'up' direction. */
533 int rgn_nr_blocks
; /* number of blocks in region */
534 int rgn_blocks
; /* blocks in the region (actually index in rgn_bb_table) */
538 /* Number of regions in the procedure */
539 static int nr_regions
;
541 /* Table of region descriptions */
542 static region
*rgn_table
;
544 /* Array of lists of regions' blocks */
545 static int *rgn_bb_table
;
547 /* Topological order of blocks in the region (if b2 is reachable from
548 b1, block_to_bb[b2] > block_to_bb[b1]).
549 Note: A basic block is always referred to by either block or b,
550 while its topological order name (in the region) is refered to by
553 static int *block_to_bb
;
555 /* The number of the region containing a block. */
556 static int *containing_rgn
;
558 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
559 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
560 #define BLOCK_TO_BB(block) (block_to_bb[block])
561 #define CONTAINING_RGN(block) (containing_rgn[block])
563 void debug_regions
PROTO ((void));
564 static void find_single_block_region
PROTO ((void));
565 static void find_rgns
PROTO ((void));
566 static int too_large
PROTO ((int, int *, int *));
568 extern void debug_live
PROTO ((int, int));
570 /* Blocks of the current region being scheduled. */
571 static int current_nr_blocks
;
572 static int current_blocks
;
574 /* The mapping from bb to block */
575 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
578 /* Bit vectors and bitset operations are needed for computations on
579 the control flow graph. */
581 typedef unsigned HOST_WIDE_INT
*bitset
;
584 int *first_member
; /* pointer to the list start in bitlst_table. */
585 int nr_members
; /* the number of members of the bit list. */
589 static int bitlst_table_last
;
590 static int bitlst_table_size
;
591 static int *bitlst_table
;
593 static char bitset_member
PROTO ((bitset
, int, int));
594 static void extract_bitlst
PROTO ((bitset
, int, bitlst
*));
596 /* target info declarations.
598 The block currently being scheduled is referred to as the "target" block,
599 while other blocks in the region from which insns can be moved to the
600 target are called "source" blocks. The candidate structure holds info
601 about such sources: are they valid? Speculative? Etc. */
602 typedef bitlst bblst
;
613 static candidate
*candidate_table
;
615 /* A speculative motion requires checking live information on the path
616 from 'source' to 'target'. The split blocks are those to be checked.
617 After a speculative motion, live information should be modified in
620 Lists of split and update blocks for each candidate of the current
621 target are in array bblst_table */
622 static int *bblst_table
, bblst_size
, bblst_last
;
624 #define IS_VALID(src) ( candidate_table[src].is_valid )
625 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
626 #define SRC_PROB(src) ( candidate_table[src].src_prob )
628 /* The bb being currently scheduled. */
629 static int target_bb
;
632 typedef bitlst edgelst
;
634 /* target info functions */
635 static void split_edges
PROTO ((int, int, edgelst
*));
636 static void compute_trg_info
PROTO ((int));
637 void debug_candidate
PROTO ((int));
638 void debug_candidates
PROTO ((int));
641 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
642 typedef bitset bbset
;
644 /* Number of words of the bbset. */
645 static int bbset_size
;
647 /* Dominators array: dom[i] contains the bbset of dominators of
648 bb i in the region. */
651 /* bb 0 is the only region entry */
652 #define IS_RGN_ENTRY(bb) (!bb)
654 /* Is bb_src dominated by bb_trg. */
655 #define IS_DOMINATED(bb_src, bb_trg) \
656 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
658 /* Probability: Prob[i] is a float in [0, 1] which is the probability
659 of bb i relative to the region entry. */
662 /* The probability of bb_src, relative to bb_trg. Note, that while the
663 'prob[bb]' is a float in [0, 1], this macro returns an integer
665 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
668 /* Bit-set of edges, where bit i stands for edge i. */
669 typedef bitset edgeset
;
671 /* Number of edges in the region. */
672 static int rgn_nr_edges
;
674 /* Array of size rgn_nr_edges. */
675 static int *rgn_edges
;
677 /* Number of words in an edgeset. */
678 static int edgeset_size
;
680 /* Mapping from each edge in the graph to its number in the rgn. */
681 static int *edge_to_bit
;
682 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
684 /* The split edges of a source bb is different for each target
685 bb. In order to compute this efficiently, the 'potential-split edges'
686 are computed for each bb prior to scheduling a region. This is actually
687 the split edges of each bb relative to the region entry.
689 pot_split[bb] is the set of potential split edges of bb. */
690 static edgeset
*pot_split
;
692 /* For every bb, a set of its ancestor edges. */
693 static edgeset
*ancestor_edges
;
695 static void compute_dom_prob_ps
PROTO ((int));
697 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
698 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
699 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
700 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
702 /* parameters affecting the decision of rank_for_schedule() */
703 #define MIN_DIFF_PRIORITY 2
704 #define MIN_PROBABILITY 40
705 #define MIN_PROB_DIFF 10
707 /* speculative scheduling functions */
708 static int check_live_1
PROTO ((int, rtx
));
709 static void update_live_1
PROTO ((int, rtx
));
710 static int check_live
PROTO ((rtx
, int));
711 static void update_live
PROTO ((rtx
, int));
712 static void set_spec_fed
PROTO ((rtx
));
713 static int is_pfree
PROTO ((rtx
, int, int));
714 static int find_conditional_protection
PROTO ((rtx
, int));
715 static int is_conditionally_protected
PROTO ((rtx
, int, int));
716 static int may_trap_exp
PROTO ((rtx
, int));
717 static int haifa_classify_insn
PROTO ((rtx
));
718 static int is_exception_free
PROTO ((rtx
, int, int));
720 static char find_insn_mem_list
PROTO ((rtx
, rtx
, rtx
, rtx
));
721 static void compute_block_forward_dependences
PROTO ((int));
722 static void init_rgn_data_dependences
PROTO ((int));
723 static void add_branch_dependences
PROTO ((rtx
, rtx
));
724 static void compute_block_backward_dependences
PROTO ((int));
725 void debug_dependencies
PROTO ((void));
727 /* Notes handling mechanism:
728 =========================
729 Generally, NOTES are saved before scheduling and restored after scheduling.
730 The scheduler distinguishes between three types of notes:
732 (1) LINE_NUMBER notes, generated and used for debugging. Here,
733 before scheduling a region, a pointer to the LINE_NUMBER note is
734 added to the insn following it (in save_line_notes()), and the note
735 is removed (in rm_line_notes() and unlink_line_notes()). After
736 scheduling the region, this pointer is used for regeneration of
737 the LINE_NUMBER note (in restore_line_notes()).
739 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
740 Before scheduling a region, a pointer to the note is added to the insn
741 that follows or precedes it. (This happens as part of the data dependence
742 computation). After scheduling an insn, the pointer contained in it is
743 used for regenerating the corresponding note (in reemit_notes).
745 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
746 these notes are put in a list (in rm_other_notes() and
747 unlink_other_notes ()). After scheduling the block, these notes are
748 inserted at the beginning of the block (in schedule_block()). */
750 static rtx unlink_other_notes
PROTO ((rtx
, rtx
));
751 static rtx unlink_line_notes
PROTO ((rtx
, rtx
));
752 static void rm_line_notes
PROTO ((int));
753 static void save_line_notes
PROTO ((int));
754 static void restore_line_notes
PROTO ((int));
755 static void rm_redundant_line_notes
PROTO ((void));
756 static void rm_other_notes
PROTO ((rtx
, rtx
));
757 static rtx reemit_notes
PROTO ((rtx
, rtx
));
759 static void get_block_head_tail
PROTO ((int, rtx
*, rtx
*));
761 static void find_pre_sched_live
PROTO ((int));
762 static void find_post_sched_live
PROTO ((int));
763 static void update_reg_usage
PROTO ((void));
765 void debug_ready_list
PROTO ((rtx
[], int));
766 static void init_target_units
PROTO (());
767 static void insn_print_units
PROTO ((rtx
));
768 static int get_visual_tbl_length
PROTO (());
769 static void init_block_visualization
PROTO (());
770 static void print_block_visualization
PROTO ((int, char *));
771 static void visualize_scheduled_insns
PROTO ((int, int));
772 static void visualize_no_unit
PROTO ((rtx
));
773 static void visualize_stall_cycles
PROTO ((int, int));
774 static void print_exp
PROTO ((char *, rtx
, int));
775 static void print_value
PROTO ((char *, rtx
, int));
776 static void print_pattern
PROTO ((char *, rtx
, int));
777 static void print_insn
PROTO ((char *, rtx
, int));
778 void debug_reg_vector
PROTO ((regset
));
780 static rtx move_insn1
PROTO ((rtx
, rtx
));
781 static rtx move_insn
PROTO ((rtx
, rtx
));
782 static rtx group_leader
PROTO ((rtx
));
783 static int set_priorities
PROTO ((int));
784 static void init_rtx_vector
PROTO ((rtx
**, rtx
*, int, int));
785 static void schedule_region
PROTO ((int));
786 static void split_block_insns
PROTO ((int));
788 #endif /* INSN_SCHEDULING */
790 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
792 /* Helper functions for instruction scheduling. */
794 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
795 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
796 of dependence that this link represents. */
799 add_dependence (insn
, elem
, dep_type
)
802 enum reg_note dep_type
;
806 /* Don't depend an insn on itself. */
810 /* If elem is part of a sequence that must be scheduled together, then
811 make the dependence point to the last insn of the sequence.
812 When HAVE_cc0, it is possible for NOTEs to exist between users and
813 setters of the condition codes, so we must skip past notes here.
814 Otherwise, NOTEs are impossible here. */
816 next
= NEXT_INSN (elem
);
819 while (next
&& GET_CODE (next
) == NOTE
)
820 next
= NEXT_INSN (next
);
823 if (next
&& SCHED_GROUP_P (next
)
824 && GET_CODE (next
) != CODE_LABEL
)
826 /* Notes will never intervene here though, so don't bother checking
828 /* We must reject CODE_LABELs, so that we don't get confused by one
829 that has LABEL_PRESERVE_P set, which is represented by the same
830 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
832 while (NEXT_INSN (next
) && SCHED_GROUP_P (NEXT_INSN (next
))
833 && GET_CODE (NEXT_INSN (next
)) != CODE_LABEL
)
834 next
= NEXT_INSN (next
);
836 /* Again, don't depend an insn on itself. */
840 /* Make the dependence to NEXT, the last insn of the group, instead
841 of the original ELEM. */
845 #ifdef INSN_SCHEDULING
846 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
847 No need for interblock dependences with calls, since
848 calls are not moved between blocks. Note: the edge where
849 elem is a CALL is still required. */
850 if (GET_CODE (insn
) == CALL_INSN
851 && (INSN_BB (elem
) != INSN_BB (insn
)))
856 /* Check that we don't already have this dependence. */
857 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
858 if (XEXP (link
, 0) == elem
)
860 /* If this is a more restrictive type of dependence than the existing
861 one, then change the existing dependence to this type. */
862 if ((int) dep_type
< (int) REG_NOTE_KIND (link
))
863 PUT_REG_NOTE_KIND (link
, dep_type
);
866 /* Might want to check one level of transitivity to save conses. */
868 link
= rtx_alloc (INSN_LIST
);
869 /* Insn dependency, not data dependency. */
870 PUT_REG_NOTE_KIND (link
, dep_type
);
871 XEXP (link
, 0) = elem
;
872 XEXP (link
, 1) = LOG_LINKS (insn
);
873 LOG_LINKS (insn
) = link
;
876 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
877 of INSN. Abort if not found. */
880 remove_dependence (insn
, elem
)
887 for (prev
= 0, link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
889 if (XEXP (link
, 0) == elem
)
891 RTX_INTEGRATED_P (link
) = 1;
893 XEXP (prev
, 1) = XEXP (link
, 1);
895 LOG_LINKS (insn
) = XEXP (link
, 1);
907 #ifndef INSN_SCHEDULING
909 schedule_insns (dump_file
)
918 /* Computation of memory dependencies. */
920 /* The *_insns and *_mems are paired lists. Each pending memory operation
921 will have a pointer to the MEM rtx on one list and a pointer to the
922 containing insn on the other list in the same place in the list. */
924 /* We can't use add_dependence like the old code did, because a single insn
925 may have multiple memory accesses, and hence needs to be on the list
926 once for each memory access. Add_dependence won't let you add an insn
927 to a list more than once. */
929 /* An INSN_LIST containing all insns with pending read operations. */
930 static rtx pending_read_insns
;
932 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
933 static rtx pending_read_mems
;
935 /* An INSN_LIST containing all insns with pending write operations. */
936 static rtx pending_write_insns
;
938 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
939 static rtx pending_write_mems
;
941 /* Indicates the combined length of the two pending lists. We must prevent
942 these lists from ever growing too large since the number of dependencies
943 produced is at least O(N*N), and execution time is at least O(4*N*N), as
944 a function of the length of these pending lists. */
946 static int pending_lists_length
;
948 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
950 static rtx unused_insn_list
;
952 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
954 static rtx unused_expr_list
;
956 /* The last insn upon which all memory references must depend.
957 This is an insn which flushed the pending lists, creating a dependency
958 between it and all previously pending memory references. This creates
959 a barrier (or a checkpoint) which no memory reference is allowed to cross.
961 This includes all non constant CALL_INSNs. When we do interprocedural
962 alias analysis, this restriction can be relaxed.
963 This may also be an INSN that writes memory if the pending lists grow
966 static rtx last_pending_memory_flush
;
968 /* The last function call we have seen. All hard regs, and, of course,
969 the last function call, must depend on this. */
971 static rtx last_function_call
;
973 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
974 that does not already cross a call. We create dependencies between each
975 of those insn and the next call insn, to ensure that they won't cross a call
976 after scheduling is done. */
978 static rtx sched_before_next_call
;
980 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
981 so that insns independent of the last scheduled insn will be preferred
982 over dependent instructions. */
984 static rtx last_scheduled_insn
;
986 /* Data structures for the computation of data dependences in a regions. We
987 keep one copy of each of the declared above variables for each bb in the
988 region. Before analyzing the data dependences for a bb, its variables
989 are initialized as a function of the variables of its predecessors. When
990 the analysis for a bb completes, we save the contents of each variable X
991 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
992 copied to bb_pending_read_insns[bb]. Another change is that few
993 variables are now a list of insns rather than a single insn:
994 last_pending_memory_flash, last_function_call, reg_last_sets. The
995 manipulation of these variables was changed appropriately. */
997 static rtx
**bb_reg_last_uses
;
998 static rtx
**bb_reg_last_sets
;
1000 static rtx
*bb_pending_read_insns
;
1001 static rtx
*bb_pending_read_mems
;
1002 static rtx
*bb_pending_write_insns
;
1003 static rtx
*bb_pending_write_mems
;
1004 static int *bb_pending_lists_length
;
1006 static rtx
*bb_last_pending_memory_flush
;
1007 static rtx
*bb_last_function_call
;
1008 static rtx
*bb_sched_before_next_call
;
1010 /* functions for construction of the control flow graph. */
1012 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1013 Estimate in nr_edges the number of edges on the graph.
1014 We decide not to build the control flow graph if there is possibly more
1015 than one entry to the function, or if computed branches exist. */
1018 is_cfg_nonregular ()
1024 rtx nonlocal_label_list
= nonlocal_label_rtx_list ();
1026 /* check for non local labels */
1027 if (nonlocal_label_list
)
1032 /* check for labels which cannot be deleted */
1038 /* check for labels which probably cannot be deleted */
1039 if (exception_handler_labels
)
1044 /* check for labels referred to other thn by jumps */
1045 for (b
= 0; b
< n_basic_blocks
; b
++)
1046 for (insn
= basic_block_head
[b
];; insn
= NEXT_INSN (insn
))
1048 code
= GET_CODE (insn
);
1049 if (GET_RTX_CLASS (code
) == 'i')
1053 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1054 if (REG_NOTE_KIND (note
) == REG_LABEL
)
1060 if (insn
== basic_block_end
[b
])
1066 /* check for computed branches */
1067 for (b
= 0; b
< n_basic_blocks
; b
++)
1069 for (insn
= basic_block_head
[b
];; insn
= NEXT_INSN (insn
))
1072 if (GET_CODE (insn
) == JUMP_INSN
)
1074 rtx pat
= PATTERN (insn
);
1077 if (GET_CODE (pat
) == PARALLEL
)
1079 int len
= XVECLEN (pat
, 0);
1080 int has_use_labelref
= 0;
1082 for (i
= len
- 1; i
>= 0; i
--)
1083 if (GET_CODE (XVECEXP (pat
, 0, i
)) == USE
1084 && (GET_CODE (XEXP (XVECEXP (pat
, 0, i
), 0))
1088 has_use_labelref
= 1;
1091 if (!has_use_labelref
)
1092 for (i
= len
- 1; i
>= 0; i
--)
1093 if (GET_CODE (XVECEXP (pat
, 0, i
)) == SET
1094 && SET_DEST (XVECEXP (pat
, 0, i
)) == pc_rtx
1095 && uses_reg_or_mem (SET_SRC (XVECEXP (pat
, 0, i
))))
1100 /* check for branch table */
1101 else if (GET_CODE (pat
) == ADDR_VEC
1102 || GET_CODE (pat
) == ADDR_DIFF_VEC
)
1104 int diff_vec_p
= GET_CODE (pat
) == ADDR_DIFF_VEC
;
1105 int len
= XVECLEN (pat
, diff_vec_p
);
1111 /* check for computed branch */
1112 if (GET_CODE (pat
) == SET
1113 && SET_DEST (pat
) == pc_rtx
1114 && uses_reg_or_mem (SET_SRC (pat
)))
1121 if (insn
== basic_block_end
[b
])
1126 /* count for the fallthrough edges */
1127 for (b
= 0; b
< n_basic_blocks
; b
++)
1129 for (insn
= PREV_INSN (basic_block_head
[b
]);
1130 insn
&& GET_CODE (insn
) == NOTE
; insn
= PREV_INSN (insn
))
1133 if (!insn
&& b
!= 0)
1135 else if (insn
&& GET_CODE (insn
) != BARRIER
)
1145 /* Returns 1 if x uses a reg or a mem (function was taken from flow.c).
1146 x is a target of a jump. Used for the detection of computed
1147 branches. For each label seen, updates the edges estimation
1148 counter nr_edges. */
1154 enum rtx_code code
= GET_CODE (x
);
1162 && !(GET_CODE (XEXP (x
, 0)) == SYMBOL_REF
1163 && CONSTANT_POOL_ADDRESS_P (XEXP (x
, 0))))
1166 if (code
== IF_THEN_ELSE
)
1168 if (uses_reg_or_mem (XEXP (x
, 1))
1169 || uses_reg_or_mem (XEXP (x
, 2)))
1175 if (code
== LABEL_REF
)
1182 fmt
= GET_RTX_FORMAT (code
);
1183 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1186 && uses_reg_or_mem (XEXP (x
, i
)))
1190 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1191 if (uses_reg_or_mem (XVECEXP (x
, i
, j
)))
1199 /* Print the control flow graph, for debugging purposes.
1200 Callable from the debugger. */
1203 debug_control_flow ()
1207 fprintf (dump
, ";; --------- CONTROL FLOW GRAPH --------- \n\n");
1209 for (i
= 0; i
< n_basic_blocks
; i
++)
1211 fprintf (dump
, ";;\tBasic block %d: first insn %d, last %d.\n",
1213 INSN_UID (basic_block_head
[i
]),
1214 INSN_UID (basic_block_end
[i
]));
1216 fprintf (dump
, ";;\tPredecessor blocks:");
1217 for (e
= IN_EDGES (i
); e
; e
= next
)
1219 fprintf (dump
, " %d", FROM_BLOCK (e
));
1223 if (next
== IN_EDGES (i
))
1227 fprintf (dump
, "\n;;\tSuccesor blocks:");
1228 for (e
= OUT_EDGES (i
); e
; e
= next
)
1230 fprintf (dump
, " %d", TO_BLOCK (e
));
1232 next
= NEXT_OUT (e
);
1234 if (next
== OUT_EDGES (i
))
1238 fprintf (dump
, " \n\n");
1244 /* build the control flow graph. (also set nr_edges accurately) */
1247 build_control_flow ()
1252 for (i
= 0; i
< n_basic_blocks
; i
++)
1256 insn
= basic_block_end
[i
];
1257 if (GET_CODE (insn
) == JUMP_INSN
)
1259 build_jmp_edges (PATTERN (insn
), i
);
1262 for (insn
= PREV_INSN (basic_block_head
[i
]);
1263 insn
&& GET_CODE (insn
) == NOTE
; insn
= PREV_INSN (insn
))
1266 /* build fallthrough edges */
1267 if (!insn
&& i
!= 0)
1268 new_edge (i
- 1, i
);
1269 else if (insn
&& GET_CODE (insn
) != BARRIER
)
1270 new_edge (i
- 1, i
);
1273 /* increment by 1, since edge 0 is unused. */
1279 /* construct edges in the control flow graph, from 'source' block, to
1280 blocks refered to by 'pattern'. */
1284 build_jmp_edges (pattern
, source
)
1288 register RTX_CODE code
;
1292 code
= GET_CODE (pattern
);
1294 if (code
== LABEL_REF
)
1296 register rtx label
= XEXP (pattern
, 0);
1297 register int target
;
1299 /* This can happen as a result of a syntax error
1300 and a diagnostic has already been printed. */
1301 if (INSN_UID (label
) == 0)
1304 target
= INSN_BLOCK (label
);
1305 new_edge (source
, target
);
1310 /* proper handling of ADDR_DIFF_VEC: do not add a non-existing edge
1311 from the block containing the branch-on-table, to itself. */
1312 if (code
== ADDR_VEC
1313 || code
== ADDR_DIFF_VEC
)
1315 int diff_vec_p
= GET_CODE (pattern
) == ADDR_DIFF_VEC
;
1316 int len
= XVECLEN (pattern
, diff_vec_p
);
1319 for (k
= 0; k
< len
; k
++)
1321 rtx tem
= XVECEXP (pattern
, diff_vec_p
, k
);
1323 build_jmp_edges (tem
, source
);
1327 fmt
= GET_RTX_FORMAT (code
);
1328 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1331 build_jmp_edges (XEXP (pattern
, i
), source
);
1335 for (j
= 0; j
< XVECLEN (pattern
, i
); j
++)
1336 build_jmp_edges (XVECEXP (pattern
, i
, j
), source
);
1342 /* construct an edge in the control flow graph, from 'source' to 'target'. */
1345 new_edge (source
, target
)
1349 int curr_edge
, fst_edge
;
1351 /* check for duplicates */
1352 fst_edge
= curr_edge
= OUT_EDGES (source
);
1355 if (FROM_BLOCK (curr_edge
) == source
1356 && TO_BLOCK (curr_edge
) == target
)
1361 curr_edge
= NEXT_OUT (curr_edge
);
1363 if (fst_edge
== curr_edge
)
1369 FROM_BLOCK (e
) = source
;
1370 TO_BLOCK (e
) = target
;
1372 if (OUT_EDGES (source
))
1374 next_edge
= NEXT_OUT (OUT_EDGES (source
));
1375 NEXT_OUT (OUT_EDGES (source
)) = e
;
1376 NEXT_OUT (e
) = next_edge
;
1380 OUT_EDGES (source
) = e
;
1384 if (IN_EDGES (target
))
1386 next_edge
= NEXT_IN (IN_EDGES (target
));
1387 NEXT_IN (IN_EDGES (target
)) = e
;
1388 NEXT_IN (e
) = next_edge
;
1392 IN_EDGES (target
) = e
;
1398 /* BITSET macros for operations on the control flow graph. */
1400 /* Compute bitwise union of two bitsets. */
1401 #define BITSET_UNION(set1, set2, len) \
1402 do { register bitset tp = set1, sp = set2; \
1404 for (i = 0; i < len; i++) \
1405 *(tp++) |= *(sp++); } while (0)
1407 /* Compute bitwise intersection of two bitsets. */
1408 #define BITSET_INTER(set1, set2, len) \
1409 do { register bitset tp = set1, sp = set2; \
1411 for (i = 0; i < len; i++) \
1412 *(tp++) &= *(sp++); } while (0)
1414 /* Compute bitwise difference of two bitsets. */
1415 #define BITSET_DIFFER(set1, set2, len) \
1416 do { register bitset tp = set1, sp = set2; \
1418 for (i = 0; i < len; i++) \
1419 *(tp++) &= ~*(sp++); } while (0)
1421 /* Inverts every bit of bitset 'set' */
1422 #define BITSET_INVERT(set, len) \
1423 do { register bitset tmpset = set; \
1425 for (i = 0; i < len; i++, tmpset++) \
1426 *tmpset = ~*tmpset; } while (0)
1428 /* Turn on the index'th bit in bitset set. */
1429 #define BITSET_ADD(set, index, len) \
1431 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1434 set[index/HOST_BITS_PER_WIDE_INT] |= \
1435 1 << (index % HOST_BITS_PER_WIDE_INT); \
1438 /* Turn off the index'th bit in set. */
1439 #define BITSET_REMOVE(set, index, len) \
1441 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1444 set[index/HOST_BITS_PER_WIDE_INT] &= \
1445 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1449 /* Check if the index'th bit in bitset set is on. */
1452 bitset_member (set
, index
, len
)
1456 if (index
>= HOST_BITS_PER_WIDE_INT
* len
)
1458 return (set
[index
/ HOST_BITS_PER_WIDE_INT
] &
1459 1 << (index
% HOST_BITS_PER_WIDE_INT
)) ? 1 : 0;
1463 /* Translate a bit-set SET to a list BL of the bit-set members. */
1466 extract_bitlst (set
, len
, bl
)
1472 unsigned HOST_WIDE_INT word
;
1474 /* bblst table space is reused in each call to extract_bitlst */
1475 bitlst_table_last
= 0;
1477 bl
->first_member
= &bitlst_table
[bitlst_table_last
];
1480 for (i
= 0; i
< len
; i
++)
1483 offset
= i
* HOST_BITS_PER_WIDE_INT
;
1484 for (j
= 0; word
; j
++)
1488 bitlst_table
[bitlst_table_last
++] = offset
;
1499 /* functions for the construction of regions */
1501 /* Print the regions, for debugging purposes. Callable from debugger. */
1508 fprintf (dump
, "\n;; ------------ REGIONS ----------\n\n");
1509 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
1511 fprintf (dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
1512 rgn_table
[rgn
].rgn_nr_blocks
);
1513 fprintf (dump
, ";;\tbb/block: ");
1515 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
1517 current_blocks
= RGN_BLOCKS (rgn
);
1519 if (bb
!= BLOCK_TO_BB (BB_TO_BLOCK (bb
)))
1522 fprintf (dump
, " %d/%d ", bb
, BB_TO_BLOCK (bb
));
1525 fprintf (dump
, "\n\n");
1530 /* Build a single block region for each basic block in the function.
1531 This allows for using the same code for interblock and basic block
1535 find_single_block_region ()
1539 for (i
= 0; i
< n_basic_blocks
; i
++)
1541 rgn_bb_table
[i
] = i
;
1542 RGN_NR_BLOCKS (i
) = 1;
1544 CONTAINING_RGN (i
) = i
;
1545 BLOCK_TO_BB (i
) = 0;
1547 nr_regions
= n_basic_blocks
;
1551 /* Update number of blocks and the estimate for number of insns
1552 in the region. Return 1 if the region is "too large" for interblock
1553 scheduling (compile time considerations), otherwise return 0. */
1556 too_large (block
, num_bbs
, num_insns
)
1557 int block
, *num_bbs
, *num_insns
;
1560 (*num_insns
) += (INSN_LUID (basic_block_end
[block
]) -
1561 INSN_LUID (basic_block_head
[block
]));
1562 if ((*num_bbs
> max_rgn_blocks
) || (*num_insns
> max_rgn_insns
))
1569 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1570 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1571 loop containing blk. */
1572 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1574 if (max_hdr[blk] == -1) \
1575 max_hdr[blk] = hdr; \
1576 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1578 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1580 inner[max_hdr[blk]] = 0; \
1581 max_hdr[blk] = hdr; \
1586 /* Find regions for interblock scheduling: a loop-free procedure, a reducible
1587 inner loop, or a basic block not contained in any other region.
1588 The procedures control flow graph is traversed twice.
1589 First traversal, a DFS, finds the headers of inner loops in the graph,
1590 and verifies that there are no unreacable blocks.
1591 Second traversal processes headers of inner loops, checking that the
1592 loop is reducible. The loop blocks that form a region are put into the
1593 region's blocks list in topological order.
1595 The following variables are changed by the function: rgn_nr, rgn_table,
1596 rgn_bb_table, block_to_bb and containing_rgn. */
1601 int *max_hdr
, *dfs_nr
, *stack
, *queue
, *degree
;
1602 char *header
, *inner
, *passed
, *in_stack
, *in_queue
, no_loops
= 1;
1603 int node
, child
, loop_head
, i
, j
, fst_edge
, head
, tail
;
1604 int count
= 0, sp
, idx
= 0, current_edge
= out_edges
[0];
1605 int num_bbs
, num_insns
;
1606 int too_large_failure
;
1610 The following data structures are computed by the first traversal and
1611 are used by the second traversal:
1612 header[i] - flag set if the block i is the header of a loop.
1613 inner[i] - initially set. It is reset if the the block i is the header
1614 of a non-inner loop.
1615 max_hdr[i] - the header of the inner loop containing block i.
1616 (for a block i not in an inner loop it may be -1 or the
1617 header of the most inner loop containing the block).
1619 These data structures are used by the first traversal only:
1620 stack - non-recursive DFS implementation which uses a stack of edges.
1621 sp - top of the stack of edges
1622 dfs_nr[i] - the DFS ordering of block i.
1623 in_stack[i] - flag set if the block i is in the DFS stack.
1625 These data structures are used by the second traversal only:
1626 queue - queue containing the blocks of the current region.
1627 head and tail - queue boundaries.
1628 in_queue[i] - flag set if the block i is in queue */
1630 /* function's inner arrays allocation and initialization */
1631 max_hdr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1632 dfs_nr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1633 bzero ((char *) dfs_nr
, n_basic_blocks
* sizeof (int));
1634 stack
= (int *) alloca (nr_edges
* sizeof (int));
1635 queue
= (int *) alloca (n_basic_blocks
* sizeof (int));
1637 inner
= (char *) alloca (n_basic_blocks
* sizeof (char));
1638 header
= (char *) alloca (n_basic_blocks
* sizeof (char));
1639 bzero ((char *) header
, n_basic_blocks
* sizeof (char));
1640 passed
= (char *) alloca (nr_edges
* sizeof (char));
1641 bzero ((char *) passed
, nr_edges
* sizeof (char));
1642 in_stack
= (char *) alloca (nr_edges
* sizeof (char));
1643 bzero ((char *) in_stack
, nr_edges
* sizeof (char));
1644 reachable
= (char *) alloca (n_basic_blocks
* sizeof (char));
1645 bzero ((char *) reachable
, n_basic_blocks
* sizeof (char));
1647 in_queue
= (char *) alloca (n_basic_blocks
* sizeof (char));
1649 for (i
= 0; i
< n_basic_blocks
; i
++)
1655 /* First traversal: DFS, finds inner loops in control flow graph */
1661 if (current_edge
== 0 || passed
[current_edge
])
1663 /* Here, if current_edge < 0, this is a leaf block.
1664 Otherwise current_edge was already passed. Note that in
1665 the latter case, not only current_edge but also all its
1666 NEXT_OUT edges are also passed. We have to "climb up on
1667 edges in the stack", looking for the first (already
1668 passed) edge whose NEXT_OUT was not passed yet. */
1670 while (sp
>= 0 && (current_edge
== 0 || passed
[current_edge
]))
1672 current_edge
= stack
[sp
--];
1673 node
= FROM_BLOCK (current_edge
);
1674 child
= TO_BLOCK (current_edge
);
1675 in_stack
[child
] = 0;
1676 if (max_hdr
[child
] >= 0 && in_stack
[max_hdr
[child
]])
1677 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1678 current_edge
= NEXT_OUT (current_edge
);
1681 /* stack empty - the whole graph is traversed. */
1682 if (sp
< 0 && passed
[current_edge
])
1687 node
= FROM_BLOCK (current_edge
);
1688 dfs_nr
[node
] = ++count
;
1690 child
= TO_BLOCK (current_edge
);
1691 reachable
[child
] = 1;
1693 /* found a loop header */
1694 if (in_stack
[child
])
1698 max_hdr
[child
] = child
;
1699 UPDATE_LOOP_RELATIONS (node
, child
);
1700 passed
[current_edge
] = 1;
1701 current_edge
= NEXT_OUT (current_edge
);
1705 /* the child was already visited once, no need to go down from
1706 it, everything is traversed there. */
1709 if (max_hdr
[child
] >= 0 && in_stack
[max_hdr
[child
]])
1710 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1711 passed
[current_edge
] = 1;
1712 current_edge
= NEXT_OUT (current_edge
);
1716 /* this is a step down in the dfs traversal */
1717 stack
[++sp
] = current_edge
;
1718 passed
[current_edge
] = 1;
1719 current_edge
= OUT_EDGES (child
);
1722 /* if there are unreachable blocks, or more than one entry to
1723 the subroutine, give up on interblock scheduling */
1724 for (i
= 1; i
< n_basic_blocks
; i
++)
1726 if (reachable
[i
] == 0)
1728 find_single_block_region ();
1729 if (sched_verbose
>= 3)
1730 fprintf (stderr
, "sched: warning: found an unreachable block %d \n", i
);
1735 /* Second travsersal: find reducible inner loops, and sort
1736 topologically the blocks of each region */
1737 degree
= dfs_nr
; /* reuse dfs_nr array - it is not needed anymore */
1738 bzero ((char *) in_queue
, n_basic_blocks
* sizeof (char));
1743 /* compute the in-degree of every block in the graph */
1744 for (i
= 0; i
< n_basic_blocks
; i
++)
1746 fst_edge
= IN_EDGES (i
);
1750 current_edge
= NEXT_IN (fst_edge
);
1751 while (fst_edge
!= current_edge
)
1754 current_edge
= NEXT_IN (current_edge
);
1761 /* pass through all graph blocks, looking for headers of inner loops */
1762 for (i
= 0; i
< n_basic_blocks
; i
++)
1765 if (header
[i
] && inner
[i
])
1768 /* i is a header of a potentially reducible inner loop, or
1769 block 0 in a subroutine with no loops at all */
1771 too_large_failure
= 0;
1772 loop_head
= max_hdr
[i
];
1774 /* decrease in_degree of all i's successors, (this is needed
1775 for the topological ordering) */
1776 fst_edge
= current_edge
= OUT_EDGES (i
);
1781 --degree
[TO_BLOCK (current_edge
)];
1782 current_edge
= NEXT_OUT (current_edge
);
1784 while (fst_edge
!= current_edge
);
1787 /* estimate # insns, and count # blocks in the region. */
1789 num_insns
= INSN_LUID (basic_block_end
[i
]) - INSN_LUID (basic_block_head
[i
]);
1792 /* find all loop latches, if it is a true loop header, or
1793 all leaves if the graph has no loops at all */
1796 for (j
= 0; j
< n_basic_blocks
; j
++)
1797 if (out_edges
[j
] == 0) /* a leaf */
1802 if (too_large (j
, &num_bbs
, &num_insns
))
1804 too_large_failure
= 1;
1811 fst_edge
= current_edge
= IN_EDGES (i
);
1814 node
= FROM_BLOCK (current_edge
);
1815 if (max_hdr
[node
] == loop_head
&& node
!= i
) /* a latch */
1817 queue
[++tail
] = node
;
1820 if (too_large (node
, &num_bbs
, &num_insns
))
1822 too_large_failure
= 1;
1826 current_edge
= NEXT_IN (current_edge
);
1828 while (fst_edge
!= current_edge
);
1831 /* Put in queue[] all blocks that belong to the loop. Check
1832 that the loop is reducible, traversing back from the loop
1833 latches up to the loop header. */
1834 while (head
< tail
&& !too_large_failure
)
1836 child
= queue
[++head
];
1837 fst_edge
= current_edge
= IN_EDGES (child
);
1840 node
= FROM_BLOCK (current_edge
);
1842 if (max_hdr
[node
] != loop_head
)
1843 { /* another entry to loop, it is irreducible */
1847 else if (!in_queue
[node
] && node
!= i
)
1849 queue
[++tail
] = node
;
1852 if (too_large (node
, &num_bbs
, &num_insns
))
1854 too_large_failure
= 1;
1858 current_edge
= NEXT_IN (current_edge
);
1860 while (fst_edge
!= current_edge
);
1863 if (tail
>= 0 && !too_large_failure
)
1865 /* Place the loop header into list of region blocks */
1867 rgn_bb_table
[idx
] = i
;
1868 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1869 RGN_BLOCKS (nr_regions
) = idx
++;
1870 CONTAINING_RGN (i
) = nr_regions
;
1871 BLOCK_TO_BB (i
) = count
= 0;
1873 /* remove blocks from queue[], (in topological order), when
1874 their in_degree becomes 0. We scan the queue over and
1875 over again until it is empty. Note: there may be a more
1876 efficient way to do it. */
1881 child
= queue
[head
];
1882 if (degree
[child
] == 0)
1885 rgn_bb_table
[idx
++] = child
;
1886 BLOCK_TO_BB (child
) = ++count
;
1887 CONTAINING_RGN (child
) = nr_regions
;
1888 queue
[head
] = queue
[tail
--];
1889 fst_edge
= current_edge
= OUT_EDGES (child
);
1895 --degree
[TO_BLOCK (current_edge
)];
1896 current_edge
= NEXT_OUT (current_edge
);
1898 while (fst_edge
!= current_edge
);
1909 /* define each of all other blocks as a region itself */
1910 for (i
= 0; i
< n_basic_blocks
; i
++)
1913 rgn_bb_table
[idx
] = i
;
1914 RGN_NR_BLOCKS (nr_regions
) = 1;
1915 RGN_BLOCKS (nr_regions
) = idx
++;
1916 CONTAINING_RGN (i
) = nr_regions
++;
1917 BLOCK_TO_BB (i
) = 0;
1923 /* functions for regions scheduling information */
1925 /* Compute dominators, probability, and potential-split-edges of bb.
1926 Assume that these values were already computed for bb's predecessors. */
1929 compute_dom_prob_ps (bb
)
1932 int nxt_in_edge
, fst_in_edge
, pred
;
1933 int fst_out_edge
, nxt_out_edge
, nr_out_edges
, nr_rgn_out_edges
;
1936 if (IS_RGN_ENTRY (bb
))
1938 BITSET_ADD (dom
[bb
], 0, bbset_size
);
1943 fst_in_edge
= nxt_in_edge
= IN_EDGES (BB_TO_BLOCK (bb
));
1945 /* intialize dom[bb] to '111..1' */
1946 BITSET_INVERT (dom
[bb
], bbset_size
);
1950 pred
= FROM_BLOCK (nxt_in_edge
);
1951 BITSET_INTER (dom
[bb
], dom
[BLOCK_TO_BB (pred
)], bbset_size
);
1953 BITSET_UNION (ancestor_edges
[bb
], ancestor_edges
[BLOCK_TO_BB (pred
)],
1956 BITSET_ADD (ancestor_edges
[bb
], EDGE_TO_BIT (nxt_in_edge
), edgeset_size
);
1959 nr_rgn_out_edges
= 0;
1960 fst_out_edge
= OUT_EDGES (pred
);
1961 nxt_out_edge
= NEXT_OUT (fst_out_edge
);
1962 BITSET_UNION (pot_split
[bb
], pot_split
[BLOCK_TO_BB (pred
)],
1965 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (fst_out_edge
), edgeset_size
);
1967 /* the successor doesn't belong the region? */
1968 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge
)) !=
1969 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1972 while (fst_out_edge
!= nxt_out_edge
)
1975 /* the successor doesn't belong the region? */
1976 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge
)) !=
1977 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1979 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (nxt_out_edge
), edgeset_size
);
1980 nxt_out_edge
= NEXT_OUT (nxt_out_edge
);
1984 /* now nr_rgn_out_edges is the number of region-exit edges from pred,
1985 and nr_out_edges will be the number of pred out edges not leaving
1987 nr_out_edges
-= nr_rgn_out_edges
;
1988 if (nr_rgn_out_edges
> 0)
1989 prob
[bb
] += 0.9 * prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1991 prob
[bb
] += prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1992 nxt_in_edge
= NEXT_IN (nxt_in_edge
);
1994 while (fst_in_edge
!= nxt_in_edge
);
1996 BITSET_ADD (dom
[bb
], bb
, bbset_size
);
1997 BITSET_DIFFER (pot_split
[bb
], ancestor_edges
[bb
], edgeset_size
);
1999 if (sched_verbose
>= 2)
2000 fprintf (dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
), (int) (100.0 * prob
[bb
]));
2001 } /* compute_dom_prob_ps */
2003 /* functions for target info */
2005 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
2006 Note that bb_trg dominates bb_src. */
2009 split_edges (bb_src
, bb_trg
, bl
)
2014 int es
= edgeset_size
;
2015 edgeset src
= (edgeset
) alloca (es
* sizeof (HOST_WIDE_INT
));
2018 src
[es
] = (pot_split
[bb_src
])[es
];
2019 BITSET_DIFFER (src
, pot_split
[bb_trg
], edgeset_size
);
2020 extract_bitlst (src
, edgeset_size
, bl
);
2024 /* Find the valid candidate-source-blocks for the target block TRG, compute
2025 their probability, and check if they are speculative or not.
2026 For speculative sources, compute their update-blocks and split-blocks. */
2029 compute_trg_info (trg
)
2032 register candidate
*sp
;
2034 int check_block
, update_idx
;
2035 int i
, j
, k
, fst_edge
, nxt_edge
;
2037 /* define some of the fields for the target bb as well */
2038 sp
= candidate_table
+ trg
;
2040 sp
->is_speculative
= 0;
2043 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
2045 sp
= candidate_table
+ i
;
2047 sp
->is_valid
= IS_DOMINATED (i
, trg
);
2050 sp
->src_prob
= GET_SRC_PROB (i
, trg
);
2051 sp
->is_valid
= (sp
->src_prob
>= MIN_PROBABILITY
);
2056 split_edges (i
, trg
, &el
);
2057 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
2058 if (sp
->is_speculative
&& !flag_schedule_speculative
)
2064 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
2065 sp
->split_bbs
.nr_members
= el
.nr_members
;
2066 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
2067 bblst_table
[bblst_last
] =
2068 TO_BLOCK (rgn_edges
[el
.first_member
[j
]]);
2069 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
2071 for (j
= 0; j
< el
.nr_members
; j
++)
2073 check_block
= FROM_BLOCK (rgn_edges
[el
.first_member
[j
]]);
2074 fst_edge
= nxt_edge
= OUT_EDGES (check_block
);
2077 for (k
= 0; k
< el
.nr_members
; k
++)
2078 if (EDGE_TO_BIT (nxt_edge
) == el
.first_member
[k
])
2081 if (k
>= el
.nr_members
)
2083 bblst_table
[bblst_last
++] = TO_BLOCK (nxt_edge
);
2087 nxt_edge
= NEXT_OUT (nxt_edge
);
2089 while (fst_edge
!= nxt_edge
);
2091 sp
->update_bbs
.nr_members
= update_idx
;
2096 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
2098 sp
->is_speculative
= 0;
2102 } /* compute_trg_info */
2105 /* Print candidates info, for debugging purposes. Callable from debugger. */
2111 if (!candidate_table
[i
].is_valid
)
2114 if (candidate_table
[i
].is_speculative
)
2117 fprintf (dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
2119 fprintf (dump
, "split path: ");
2120 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
2122 int b
= candidate_table
[i
].split_bbs
.first_member
[j
];
2124 fprintf (dump
, " %d ", b
);
2126 fprintf (dump
, "\n");
2128 fprintf (dump
, "update path: ");
2129 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
2131 int b
= candidate_table
[i
].update_bbs
.first_member
[j
];
2133 fprintf (dump
, " %d ", b
);
2135 fprintf (dump
, "\n");
2139 fprintf (dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
2144 /* Print candidates info, for debugging purposes. Callable from debugger. */
2147 debug_candidates (trg
)
2152 fprintf (dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
2153 BB_TO_BLOCK (trg
), trg
);
2154 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
2155 debug_candidate (i
);
2159 /* functions for speculative scheduing */
2161 /* Return 0 if x is a set of a register alive in the beginning of one
2162 of the split-blocks of src, otherwise return 1. */
2165 check_live_1 (src
, x
)
2171 register rtx reg
= SET_DEST (x
);
2176 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2177 || GET_CODE (reg
) == SIGN_EXTRACT
2178 || GET_CODE (reg
) == STRICT_LOW_PART
)
2179 reg
= XEXP (reg
, 0);
2181 if (GET_CODE (reg
) != REG
)
2184 regno
= REGNO (reg
);
2186 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
2188 /* Global registers are assumed live */
2193 if (regno
< FIRST_PSEUDO_REGISTER
)
2195 /* check for hard registers */
2196 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2199 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2201 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2203 if (REGNO_REG_SET_P (basic_block_live_at_start
[b
], regno
+ j
))
2212 /* check for psuedo registers */
2213 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2215 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2217 if (REGNO_REG_SET_P (basic_block_live_at_start
[b
], regno
))
2229 /* If x is a set of a register R, mark that R is alive in the beginning
2230 of every update-block of src. */
2233 update_live_1 (src
, x
)
2239 register rtx reg
= SET_DEST (x
);
2244 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2245 || GET_CODE (reg
) == SIGN_EXTRACT
2246 || GET_CODE (reg
) == STRICT_LOW_PART
)
2247 reg
= XEXP (reg
, 0);
2249 if (GET_CODE (reg
) != REG
)
2252 /* Global registers are always live, so the code below does not apply
2255 regno
= REGNO (reg
);
2257 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
2259 if (regno
< FIRST_PSEUDO_REGISTER
)
2261 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2264 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2266 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2268 SET_REGNO_REG_SET (basic_block_live_at_start
[b
], regno
+ j
);
2274 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2276 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2278 SET_REGNO_REG_SET (basic_block_live_at_start
[b
], regno
);
2285 /* Return 1 if insn can be speculatively moved from block src to trg,
2286 otherwise return 0. Called before first insertion of insn to
2287 ready-list or before the scheduling. */
2290 check_live (insn
, src
)
2294 /* find the registers set by instruction */
2295 if (GET_CODE (PATTERN (insn
)) == SET
2296 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2297 return check_live_1 (src
, PATTERN (insn
));
2298 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2301 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2302 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2303 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2304 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
2314 /* Update the live registers info after insn was moved speculatively from
2315 block src to trg. */
2318 update_live (insn
, src
)
2322 /* find the registers set by instruction */
2323 if (GET_CODE (PATTERN (insn
)) == SET
2324 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2325 update_live_1 (src
, PATTERN (insn
));
2326 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2329 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2330 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2331 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2332 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
2336 /* Exception Free Loads:
2338 We define five classes of speculative loads: IFREE, IRISKY,
2339 PFREE, PRISKY, and MFREE.
2341 IFREE loads are loads that are proved to be exception-free, just
2342 by examining the load insn. Examples for such loads are loads
2343 from TOC and loads of global data.
2345 IRISKY loads are loads that are proved to be exception-risky,
2346 just by examining the load insn. Examples for such loads are
2347 volatile loads and loads from shared memory.
2349 PFREE loads are loads for which we can prove, by examining other
2350 insns, that they are exception-free. Currently, this class consists
2351 of loads for which we are able to find a "similar load", either in
2352 the target block, or, if only one split-block exists, in that split
2353 block. Load2 is similar to load1 if both have same single base
2354 register. We identify only part of the similar loads, by finding
2355 an insn upon which both load1 and load2 have a DEF-USE dependence.
2357 PRISKY loads are loads for which we can prove, by examining other
2358 insns, that they are exception-risky. Currently we have two proofs for
2359 such loads. The first proof detects loads that are probably guarded by a
2360 test on the memory address. This proof is based on the
2361 backward and forward data dependence information for the region.
2362 Let load-insn be the examined load.
2363 Load-insn is PRISKY iff ALL the following hold:
2365 - insn1 is not in the same block as load-insn
2366 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2367 - test-insn is either a compare or a branch, not in the same block as load-insn
2368 - load-insn is reachable from test-insn
2369 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2371 This proof might fail when the compare and the load are fed
2372 by an insn not in the region. To solve this, we will add to this
2373 group all loads that have no input DEF-USE dependence.
2375 The second proof detects loads that are directly or indirectly
2376 fed by a speculative load. This proof is affected by the
2377 scheduling process. We will use the flag fed_by_spec_load.
2378 Initially, all insns have this flag reset. After a speculative
2379 motion of an insn, if insn is either a load, or marked as
2380 fed_by_spec_load, we will also mark as fed_by_spec_load every
2381 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2382 load which is fed_by_spec_load is also PRISKY.
2384 MFREE (maybe-free) loads are all the remaining loads. They may be
2385 exception-free, but we cannot prove it.
2387 Now, all loads in IFREE and PFREE classes are considered
2388 exception-free, while all loads in IRISKY and PRISKY classes are
2389 considered exception-risky. As for loads in the MFREE class,
2390 these are considered either exception-free or exception-risky,
2391 depending on whether we are pessimistic or optimistic. We have
2392 to take the pessimistic approach to assure the safety of
2393 speculative scheduling, but we can take the optimistic approach
2394 by invoking the -fsched_spec_load_dangerous option. */
2396 enum INSN_TRAP_CLASS
2398 TRAP_FREE
= 0, IFREE
= 1, PFREE_CANDIDATE
= 2,
2399 PRISKY_CANDIDATE
= 3, IRISKY
= 4, TRAP_RISKY
= 5
2402 #define WORST_CLASS(class1, class2) \
2403 ((class1 > class2) ? class1 : class2)
2405 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between */
2406 /* some speculatively moved load insn and this one. */
2407 char *fed_by_spec_load
;
2410 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2411 #define IS_REACHABLE(bb_from, bb_to) \
2413 || IS_RGN_ENTRY (bb_from) \
2414 || (bitset_member (ancestor_edges[bb_to], \
2415 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2417 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2418 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2420 /* Non-zero iff the address is comprised from at most 1 register */
2421 #define CONST_BASED_ADDRESS_P(x) \
2422 (GET_CODE (x) == REG \
2423 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2424 || (GET_CODE (x) == LO_SUM)) \
2425 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2426 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2428 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2431 set_spec_fed (load_insn
)
2436 for (link
= INSN_DEPEND (load_insn
); link
; link
= XEXP (link
, 1))
2437 if (GET_MODE (link
) == VOIDmode
)
2438 FED_BY_SPEC_LOAD (XEXP (link
, 0)) = 1;
2439 } /* set_spec_fed */
2441 /* On the path from the insn to load_insn_bb, find a conditional branch */
2442 /* depending on insn, that guards the speculative load. */
2445 find_conditional_protection (insn
, load_insn_bb
)
2451 /* iterate through DEF-USE forward dependences */
2452 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
2454 rtx next
= XEXP (link
, 0);
2455 if ((CONTAINING_RGN (INSN_BLOCK (next
)) ==
2456 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
2457 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
2458 && load_insn_bb
!= INSN_BB (next
)
2459 && GET_MODE (link
) == VOIDmode
2460 && (GET_CODE (next
) == JUMP_INSN
2461 || find_conditional_protection (next
, load_insn_bb
)))
2465 } /* find_conditional_protection */
2467 /* Returns 1 if the same insn1 that participates in the computation
2468 of load_insn's address is feeding a conditional branch that is
2469 guarding on load_insn. This is true if we find a the two DEF-USE
2471 insn1 -> ... -> conditional-branch
2472 insn1 -> ... -> load_insn,
2473 and if a flow path exist:
2474 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2475 and if insn1 is on the path
2476 region-entry -> ... -> bb_trg -> ... load_insn.
2478 Locate insn1 by climbing on LOG_LINKS from load_insn.
2479 Locate the branch by following INSN_DEPEND from insn1. */
2482 is_conditionally_protected (load_insn
, bb_src
, bb_trg
)
2488 for (link
= LOG_LINKS (load_insn
); link
; link
= XEXP (link
, 1))
2490 rtx insn1
= XEXP (link
, 0);
2492 /* must be a DEF-USE dependence upon non-branch */
2493 if (GET_MODE (link
) != VOIDmode
2494 || GET_CODE (insn1
) == JUMP_INSN
)
2497 /* must exist a path: region-entry -> ... -> bb_trg -> ... load_insn */
2498 if (INSN_BB (insn1
) == bb_src
2499 || (CONTAINING_RGN (INSN_BLOCK (insn1
))
2500 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
2501 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
2502 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
2505 /* now search for the conditional-branch */
2506 if (find_conditional_protection (insn1
, bb_src
))
2509 /* recursive step: search another insn1, "above" current insn1. */
2510 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
2513 /* the chain does not exsist */
2515 } /* is_conditionally_protected */
2517 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2518 load_insn can move speculatively from bb_src to bb_trg. All the
2519 following must hold:
2521 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2522 (2) load_insn and load1 have a def-use dependence upon
2523 the same insn 'insn1'.
2524 (3) either load2 is in bb_trg, or:
2525 - there's only one split-block, and
2526 - load1 is on the escape path, and
2528 From all these we can conclude that the two loads access memory
2529 addresses that differ at most by a constant, and hence if moving
2530 load_insn would cause an exception, it would have been caused by
2534 is_pfree (load_insn
, bb_src
, bb_trg
)
2539 register candidate
*candp
= candidate_table
+ bb_src
;
2541 if (candp
->split_bbs
.nr_members
!= 1)
2542 /* must have exactly one escape block */
2545 for (back_link
= LOG_LINKS (load_insn
);
2546 back_link
; back_link
= XEXP (back_link
, 1))
2548 rtx insn1
= XEXP (back_link
, 0);
2550 if (GET_MODE (back_link
) == VOIDmode
)
2552 /* found a DEF-USE dependence (insn1, load_insn) */
2555 for (fore_link
= INSN_DEPEND (insn1
);
2556 fore_link
; fore_link
= XEXP (fore_link
, 1))
2558 rtx insn2
= XEXP (fore_link
, 0);
2559 if (GET_MODE (fore_link
) == VOIDmode
)
2561 /* found a DEF-USE dependence (insn1, insn2) */
2562 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
2563 /* insn2 not guaranteed to be a 1 base reg load */
2566 if (INSN_BB (insn2
) == bb_trg
)
2567 /* insn2 is the similar load, in the target block */
2570 if (*(candp
->split_bbs
.first_member
) == INSN_BLOCK (insn2
))
2571 /* insn2 is a similar load, in a split-block */
2578 /* couldn't find a similar load */
2582 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2583 as found by analyzing insn's expression. */
2586 may_trap_exp (x
, is_store
)
2594 code
= GET_CODE (x
);
2604 /* The insn uses memory */
2605 /* a volatile load */
2606 if (MEM_VOLATILE_P (x
))
2608 /* an exception-free load */
2609 if (!may_trap_p (x
))
2611 /* a load with 1 base register, to be further checked */
2612 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
2613 return PFREE_CANDIDATE
;
2614 /* no info on the load, to be further checked */
2615 return PRISKY_CANDIDATE
;
2620 int i
, insn_class
= TRAP_FREE
;
2622 /* neither store nor load, check if it may cause a trap */
2625 /* recursive step: walk the insn... */
2626 fmt
= GET_RTX_FORMAT (code
);
2627 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2631 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
2632 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2634 else if (fmt
[i
] == 'E')
2637 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2639 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
2640 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2641 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2645 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2650 } /* may_trap_exp */
2653 /* Classifies insn for the purpose of verifying that it can be
2654 moved speculatively, by examining it's patterns, returning:
2655 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2656 TRAP_FREE: non-load insn.
2657 IFREE: load from a globaly safe location.
2658 IRISKY: volatile load.
2659 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2660 being either PFREE or PRISKY. */
2663 haifa_classify_insn (insn
)
2666 rtx pat
= PATTERN (insn
);
2667 int tmp_class
= TRAP_FREE
;
2668 int insn_class
= TRAP_FREE
;
2671 if (GET_CODE (pat
) == PARALLEL
)
2673 int i
, len
= XVECLEN (pat
, 0);
2675 for (i
= len
- 1; i
>= 0; i
--)
2677 code
= GET_CODE (XVECEXP (pat
, 0, i
));
2681 /* test if it is a 'store' */
2682 tmp_class
= may_trap_exp (XEXP (XVECEXP (pat
, 0, i
), 0), 1);
2685 /* test if it is a store */
2686 tmp_class
= may_trap_exp (SET_DEST (XVECEXP (pat
, 0, i
)), 1);
2687 if (tmp_class
== TRAP_RISKY
)
2689 /* test if it is a load */
2691 WORST_CLASS (tmp_class
,
2692 may_trap_exp (SET_SRC (XVECEXP (pat
, 0, i
)), 0));
2695 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2696 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2702 code
= GET_CODE (pat
);
2706 /* test if it is a 'store' */
2707 tmp_class
= may_trap_exp (XEXP (pat
, 0), 1);
2710 /* test if it is a store */
2711 tmp_class
= may_trap_exp (SET_DEST (pat
), 1);
2712 if (tmp_class
== TRAP_RISKY
)
2714 /* test if it is a load */
2716 WORST_CLASS (tmp_class
,
2717 may_trap_exp (SET_SRC (pat
), 0));
2720 insn_class
= tmp_class
;
2725 } /* haifa_classify_insn */
2727 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2728 a load moved speculatively, or if load_insn is protected by
2729 a compare on load_insn's address). */
2732 is_prisky (load_insn
, bb_src
, bb_trg
)
2736 if (FED_BY_SPEC_LOAD (load_insn
))
2739 if (LOG_LINKS (load_insn
) == NULL
)
2740 /* dependence may 'hide' out of the region. */
2743 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2749 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2750 Return 1 if insn is exception-free (and the motion is valid)
2754 is_exception_free (insn
, bb_src
, bb_trg
)
2758 int insn_class
= haifa_classify_insn (insn
);
2760 /* handle non-load insns */
2771 if (!flag_schedule_speculative_load
)
2773 IS_LOAD_INSN (insn
) = 1;
2780 case PFREE_CANDIDATE
:
2781 if (is_pfree (insn
, bb_src
, bb_trg
))
2783 /* don't 'break' here: PFREE-candidate is also PRISKY-candidate */
2784 case PRISKY_CANDIDATE
:
2785 if (!flag_schedule_speculative_load_dangerous
2786 || is_prisky (insn
, bb_src
, bb_trg
))
2792 return flag_schedule_speculative_load_dangerous
;
2793 } /* is_exception_free */
2796 /* Process an insn's memory dependencies. There are four kinds of
2799 (0) read dependence: read follows read
2800 (1) true dependence: read follows write
2801 (2) anti dependence: write follows read
2802 (3) output dependence: write follows write
2804 We are careful to build only dependencies which actually exist, and
2805 use transitivity to avoid building too many links. */
2807 /* Return the INSN_LIST containing INSN in LIST, or NULL
2808 if LIST does not contain INSN. */
2811 find_insn_list (insn
, list
)
2817 if (XEXP (list
, 0) == insn
)
2819 list
= XEXP (list
, 1);
2825 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 otherwise. */
2827 __inline
static char
2828 find_insn_mem_list (insn
, x
, list
, list1
)
2834 if (XEXP (list
, 0) == insn
2835 && XEXP (list1
, 0) == x
)
2837 list
= XEXP (list
, 1);
2838 list1
= XEXP (list1
, 1);
2844 /* Compute the function units used by INSN. This caches the value
2845 returned by function_units_used. A function unit is encoded as the
2846 unit number if the value is non-negative and the compliment of a
2847 mask if the value is negative. A function unit index is the
2848 non-negative encoding. */
2854 register int unit
= INSN_UNIT (insn
);
2858 recog_memoized (insn
);
2860 /* A USE insn, or something else we don't need to understand.
2861 We can't pass these directly to function_units_used because it will
2862 trigger a fatal error for unrecognizable insns. */
2863 if (INSN_CODE (insn
) < 0)
2867 unit
= function_units_used (insn
);
2868 /* Increment non-negative values so we can cache zero. */
2872 /* We only cache 16 bits of the result, so if the value is out of
2873 range, don't cache it. */
2874 if (FUNCTION_UNITS_SIZE
< HOST_BITS_PER_SHORT
2876 || (~unit
& ((1 << (HOST_BITS_PER_SHORT
- 1)) - 1)) == 0)
2877 INSN_UNIT (insn
) = unit
;
2879 return (unit
> 0 ? unit
- 1 : unit
);
2882 /* Compute the blockage range for executing INSN on UNIT. This caches
2883 the value returned by the blockage_range_function for the unit.
2884 These values are encoded in an int where the upper half gives the
2885 minimum value and the lower half gives the maximum value. */
2887 __inline
static unsigned int
2888 blockage_range (unit
, insn
)
2892 unsigned int blockage
= INSN_BLOCKAGE (insn
);
2895 if (UNIT_BLOCKED (blockage
) != unit
+ 1)
2897 range
= function_units
[unit
].blockage_range_function (insn
);
2898 /* We only cache the blockage range for one unit and then only if
2900 if (HOST_BITS_PER_INT
>= UNIT_BITS
+ 2 * BLOCKAGE_BITS
)
2901 INSN_BLOCKAGE (insn
) = ENCODE_BLOCKAGE (unit
+ 1, range
);
2904 range
= BLOCKAGE_RANGE (blockage
);
2909 /* A vector indexed by function unit instance giving the last insn to use
2910 the unit. The value of the function unit instance index for unit U
2911 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2912 static rtx unit_last_insn
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2914 /* A vector indexed by function unit instance giving the minimum time when
2915 the unit will unblock based on the maximum blockage cost. */
2916 static int unit_tick
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2918 /* A vector indexed by function unit number giving the number of insns
2919 that remain to use the unit. */
2920 static int unit_n_insns
[FUNCTION_UNITS_SIZE
];
2922 /* Reset the function unit state to the null state. */
2927 bzero ((char *) unit_last_insn
, sizeof (unit_last_insn
));
2928 bzero ((char *) unit_tick
, sizeof (unit_tick
));
2929 bzero ((char *) unit_n_insns
, sizeof (unit_n_insns
));
2932 /* Return the issue-delay of an insn */
2935 insn_issue_delay (insn
)
2939 int unit
= insn_unit (insn
);
2941 /* efficiency note: in fact, we are working 'hard' to compute a
2942 value that was available in md file, and is not available in
2943 function_units[] structure. It would be nice to have this
2944 value there, too. */
2947 if (function_units
[unit
].blockage_range_function
&&
2948 function_units
[unit
].blockage_function
)
2949 delay
= function_units
[unit
].blockage_function (insn
, insn
);
2952 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2953 if ((unit
& 1) != 0 && function_units
[i
].blockage_range_function
2954 && function_units
[i
].blockage_function
)
2955 delay
= MAX (delay
, function_units
[i
].blockage_function (insn
, insn
));
2960 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2961 instance INSTANCE at time CLOCK if the previous actual hazard cost
2965 actual_hazard_this_instance (unit
, instance
, insn
, clock
, cost
)
2966 int unit
, instance
, clock
, cost
;
2969 int tick
= unit_tick
[instance
]; /* issue time of the last issued insn */
2971 if (tick
- clock
> cost
)
2973 /* The scheduler is operating forward, so unit's last insn is the
2974 executing insn and INSN is the candidate insn. We want a
2975 more exact measure of the blockage if we execute INSN at CLOCK
2976 given when we committed the execution of the unit's last insn.
2978 The blockage value is given by either the unit's max blockage
2979 constant, blockage range function, or blockage function. Use
2980 the most exact form for the given unit. */
2982 if (function_units
[unit
].blockage_range_function
)
2984 if (function_units
[unit
].blockage_function
)
2985 tick
+= (function_units
[unit
].blockage_function
2986 (unit_last_insn
[instance
], insn
)
2987 - function_units
[unit
].max_blockage
);
2989 tick
+= ((int) MAX_BLOCKAGE_COST (blockage_range (unit
, insn
))
2990 - function_units
[unit
].max_blockage
);
2992 if (tick
- clock
> cost
)
2993 cost
= tick
- clock
;
2998 /* Record INSN as having begun execution on the units encoded by UNIT at
3001 __inline
static void
3002 schedule_unit (unit
, insn
, clock
)
3010 int instance
= unit
;
3011 #if MAX_MULTIPLICITY > 1
3012 /* Find the first free instance of the function unit and use that
3013 one. We assume that one is free. */
3014 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
3016 if (!actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
3018 instance
+= FUNCTION_UNITS_SIZE
;
3021 unit_last_insn
[instance
] = insn
;
3022 unit_tick
[instance
] = (clock
+ function_units
[unit
].max_blockage
);
3025 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3026 if ((unit
& 1) != 0)
3027 schedule_unit (i
, insn
, clock
);
3030 /* Return the actual hazard cost of executing INSN on the units encoded by
3031 UNIT at time CLOCK if the previous actual hazard cost was COST. */
3034 actual_hazard (unit
, insn
, clock
, cost
)
3035 int unit
, clock
, cost
;
3042 /* Find the instance of the function unit with the minimum hazard. */
3043 int instance
= unit
;
3044 int best_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
3048 #if MAX_MULTIPLICITY > 1
3049 if (best_cost
> cost
)
3051 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
3053 instance
+= FUNCTION_UNITS_SIZE
;
3054 this_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
3056 if (this_cost
< best_cost
)
3058 best_cost
= this_cost
;
3059 if (this_cost
<= cost
)
3065 cost
= MAX (cost
, best_cost
);
3068 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3069 if ((unit
& 1) != 0)
3070 cost
= actual_hazard (i
, insn
, clock
, cost
);
3075 /* Return the potential hazard cost of executing an instruction on the
3076 units encoded by UNIT if the previous potential hazard cost was COST.
3077 An insn with a large blockage time is chosen in preference to one
3078 with a smaller time; an insn that uses a unit that is more likely
3079 to be used is chosen in preference to one with a unit that is less
3080 used. We are trying to minimize a subsequent actual hazard. */
3083 potential_hazard (unit
, insn
, cost
)
3088 unsigned int minb
, maxb
;
3092 minb
= maxb
= function_units
[unit
].max_blockage
;
3095 if (function_units
[unit
].blockage_range_function
)
3097 maxb
= minb
= blockage_range (unit
, insn
);
3098 maxb
= MAX_BLOCKAGE_COST (maxb
);
3099 minb
= MIN_BLOCKAGE_COST (minb
);
3104 /* Make the number of instructions left dominate. Make the
3105 minimum delay dominate the maximum delay. If all these
3106 are the same, use the unit number to add an arbitrary
3107 ordering. Other terms can be added. */
3108 ncost
= minb
* 0x40 + maxb
;
3109 ncost
*= (unit_n_insns
[unit
] - 1) * 0x1000 + unit
;
3116 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3117 if ((unit
& 1) != 0)
3118 cost
= potential_hazard (i
, insn
, cost
);
3123 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3124 This is the number of cycles between instruction issue and
3125 instruction results. */
3128 insn_cost (insn
, link
, used
)
3129 rtx insn
, link
, used
;
3131 register int cost
= INSN_COST (insn
);
3135 recog_memoized (insn
);
3137 /* A USE insn, or something else we don't need to understand.
3138 We can't pass these directly to result_ready_cost because it will
3139 trigger a fatal error for unrecognizable insns. */
3140 if (INSN_CODE (insn
) < 0)
3142 INSN_COST (insn
) = 1;
3147 cost
= result_ready_cost (insn
);
3152 INSN_COST (insn
) = cost
;
3156 /* in this case estimate cost without caring how insn is used. */
3157 if (link
== 0 && used
== 0)
3160 /* A USE insn should never require the value used to be computed. This
3161 allows the computation of a function's result and parameter values to
3162 overlap the return and call. */
3163 recog_memoized (used
);
3164 if (INSN_CODE (used
) < 0)
3165 LINK_COST_FREE (link
) = 1;
3167 /* If some dependencies vary the cost, compute the adjustment. Most
3168 commonly, the adjustment is complete: either the cost is ignored
3169 (in the case of an output- or anti-dependence), or the cost is
3170 unchanged. These values are cached in the link as LINK_COST_FREE
3171 and LINK_COST_ZERO. */
3173 if (LINK_COST_FREE (link
))
3176 else if (!LINK_COST_ZERO (link
))
3180 ADJUST_COST (used
, link
, insn
, ncost
);
3182 LINK_COST_FREE (link
) = ncost
= 1;
3184 LINK_COST_ZERO (link
) = 1;
3191 /* Compute the priority number for INSN. */
3200 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
3203 if ((this_priority
= INSN_PRIORITY (insn
)) == 0)
3205 if (INSN_DEPEND (insn
) == 0)
3206 this_priority
= insn_cost (insn
, 0, 0);
3208 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
3213 if (RTX_INTEGRATED_P (link
))
3216 next
= XEXP (link
, 0);
3218 /* critical path is meaningful in block boundaries only */
3219 if (INSN_BLOCK (next
) != INSN_BLOCK (insn
))
3222 next_priority
= insn_cost (insn
, link
, next
) + priority (next
);
3223 if (next_priority
> this_priority
)
3224 this_priority
= next_priority
;
3226 INSN_PRIORITY (insn
) = this_priority
;
3228 return this_priority
;
3232 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3233 them to the unused_*_list variables, so that they can be reused. */
3235 __inline
static void
3236 free_pnd_lst (listp
, unused_listp
)
3237 rtx
*listp
, *unused_listp
;
3239 register rtx link
, prev_link
;
3245 link
= XEXP (prev_link
, 1);
3250 link
= XEXP (link
, 1);
3253 XEXP (prev_link
, 1) = *unused_listp
;
3254 *unused_listp
= *listp
;
3259 free_pending_lists ()
3263 if (current_nr_blocks
<= 1)
3265 free_pnd_lst (&pending_read_insns
, &unused_insn_list
);
3266 free_pnd_lst (&pending_write_insns
, &unused_insn_list
);
3267 free_pnd_lst (&pending_read_mems
, &unused_expr_list
);
3268 free_pnd_lst (&pending_write_mems
, &unused_expr_list
);
3272 /* interblock scheduling */
3275 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3277 free_pnd_lst (&bb_pending_read_insns
[bb
], &unused_insn_list
);
3278 free_pnd_lst (&bb_pending_write_insns
[bb
], &unused_insn_list
);
3279 free_pnd_lst (&bb_pending_read_mems
[bb
], &unused_expr_list
);
3280 free_pnd_lst (&bb_pending_write_mems
[bb
], &unused_expr_list
);
3285 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3286 The MEM is a memory reference contained within INSN, which we are saving
3287 so that we can do memory aliasing on it. */
3290 add_insn_mem_dependence (insn_list
, mem_list
, insn
, mem
)
3291 rtx
*insn_list
, *mem_list
, insn
, mem
;
3295 if (unused_insn_list
)
3297 link
= unused_insn_list
;
3298 unused_insn_list
= XEXP (link
, 1);
3301 link
= rtx_alloc (INSN_LIST
);
3302 XEXP (link
, 0) = insn
;
3303 XEXP (link
, 1) = *insn_list
;
3306 if (unused_expr_list
)
3308 link
= unused_expr_list
;
3309 unused_expr_list
= XEXP (link
, 1);
3312 link
= rtx_alloc (EXPR_LIST
);
3313 XEXP (link
, 0) = mem
;
3314 XEXP (link
, 1) = *mem_list
;
3317 pending_lists_length
++;
3321 /* Make a dependency between every memory reference on the pending lists
3322 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3326 flush_pending_lists (insn
, only_write
)
3333 while (pending_read_insns
&& ! only_write
)
3335 add_dependence (insn
, XEXP (pending_read_insns
, 0), REG_DEP_ANTI
);
3337 link
= pending_read_insns
;
3338 pending_read_insns
= XEXP (pending_read_insns
, 1);
3339 XEXP (link
, 1) = unused_insn_list
;
3340 unused_insn_list
= link
;
3342 link
= pending_read_mems
;
3343 pending_read_mems
= XEXP (pending_read_mems
, 1);
3344 XEXP (link
, 1) = unused_expr_list
;
3345 unused_expr_list
= link
;
3347 while (pending_write_insns
)
3349 add_dependence (insn
, XEXP (pending_write_insns
, 0), REG_DEP_ANTI
);
3351 link
= pending_write_insns
;
3352 pending_write_insns
= XEXP (pending_write_insns
, 1);
3353 XEXP (link
, 1) = unused_insn_list
;
3354 unused_insn_list
= link
;
3356 link
= pending_write_mems
;
3357 pending_write_mems
= XEXP (pending_write_mems
, 1);
3358 XEXP (link
, 1) = unused_expr_list
;
3359 unused_expr_list
= link
;
3361 pending_lists_length
= 0;
3363 /* last_pending_memory_flush is now a list of insns */
3364 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3365 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3367 last_pending_memory_flush
=
3368 gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
3371 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
3372 by the write to the destination of X, and reads of everything mentioned. */
3375 sched_analyze_1 (x
, insn
)
3380 register rtx dest
= SET_DEST (x
);
3385 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
3386 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3388 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3390 /* The second and third arguments are values read by this insn. */
3391 sched_analyze_2 (XEXP (dest
, 1), insn
);
3392 sched_analyze_2 (XEXP (dest
, 2), insn
);
3394 dest
= SUBREG_REG (dest
);
3397 if (GET_CODE (dest
) == REG
)
3401 regno
= REGNO (dest
);
3403 /* A hard reg in a wide mode may really be multiple registers.
3404 If so, mark all of them just like the first. */
3405 if (regno
< FIRST_PSEUDO_REGISTER
)
3407 i
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
3412 for (u
= reg_last_uses
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3413 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3414 reg_last_uses
[regno
+ i
] = 0;
3416 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3417 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3419 SET_REGNO_REG_SET (reg_pending_sets
, regno
+ i
);
3421 if ((call_used_regs
[regno
+ i
] || global_regs
[regno
+ i
]))
3422 /* Function calls clobber all call_used regs. */
3423 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3424 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3431 for (u
= reg_last_uses
[regno
]; u
; u
= XEXP (u
, 1))
3432 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3433 reg_last_uses
[regno
] = 0;
3435 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3436 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3438 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
3440 /* Pseudos that are REG_EQUIV to something may be replaced
3441 by that during reloading. We need only add dependencies for
3442 the address in the REG_EQUIV note. */
3443 if (!reload_completed
3444 && reg_known_equiv_p
[regno
]
3445 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3446 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3448 /* Don't let it cross a call after scheduling if it doesn't
3449 already cross one. */
3451 if (REG_N_CALLS_CROSSED (regno
) == 0)
3452 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3453 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3456 else if (GET_CODE (dest
) == MEM
)
3458 /* Writing memory. */
3460 if (pending_lists_length
> 32)
3462 /* Flush all pending reads and writes to prevent the pending lists
3463 from getting any larger. Insn scheduling runs too slowly when
3464 these lists get long. The number 32 was chosen because it
3465 seems like a reasonable number. When compiling GCC with itself,
3466 this flush occurs 8 times for sparc, and 10 times for m88k using
3468 flush_pending_lists (insn
, 0);
3473 rtx pending
, pending_mem
;
3475 pending
= pending_read_insns
;
3476 pending_mem
= pending_read_mems
;
3479 /* If a dependency already exists, don't create a new one. */
3480 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3481 if (anti_dependence (XEXP (pending_mem
, 0), dest
))
3482 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3484 pending
= XEXP (pending
, 1);
3485 pending_mem
= XEXP (pending_mem
, 1);
3488 pending
= pending_write_insns
;
3489 pending_mem
= pending_write_mems
;
3492 /* If a dependency already exists, don't create a new one. */
3493 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3494 if (output_dependence (XEXP (pending_mem
, 0), dest
))
3495 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
3497 pending
= XEXP (pending
, 1);
3498 pending_mem
= XEXP (pending_mem
, 1);
3501 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3502 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3504 add_insn_mem_dependence (&pending_write_insns
, &pending_write_mems
,
3507 sched_analyze_2 (XEXP (dest
, 0), insn
);
3510 /* Analyze reads. */
3511 if (GET_CODE (x
) == SET
)
3512 sched_analyze_2 (SET_SRC (x
), insn
);
3515 /* Analyze the uses of memory and registers in rtx X in INSN. */
3518 sched_analyze_2 (x
, insn
)
3524 register enum rtx_code code
;
3530 code
= GET_CODE (x
);
3539 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3540 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3541 this does not mean that this insn is using cc0. */
3549 /* User of CC0 depends on immediately preceding insn. */
3550 SCHED_GROUP_P (insn
) = 1;
3552 /* There may be a note before this insn now, but all notes will
3553 be removed before we actually try to schedule the insns, so
3554 it won't cause a problem later. We must avoid it here though. */
3555 prev
= prev_nonnote_insn (insn
);
3557 /* Make a copy of all dependencies on the immediately previous insn,
3558 and add to this insn. This is so that all the dependencies will
3559 apply to the group. Remove an explicit dependence on this insn
3560 as SCHED_GROUP_P now represents it. */
3562 if (find_insn_list (prev
, LOG_LINKS (insn
)))
3563 remove_dependence (insn
, prev
);
3565 for (link
= LOG_LINKS (prev
); link
; link
= XEXP (link
, 1))
3566 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3575 int regno
= REGNO (x
);
3576 if (regno
< FIRST_PSEUDO_REGISTER
)
3580 i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
3583 reg_last_uses
[regno
+ i
]
3584 = gen_rtx_INSN_LIST (VOIDmode
,
3585 insn
, reg_last_uses
[regno
+ i
]);
3587 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3588 add_dependence (insn
, XEXP (u
, 0), 0);
3590 if ((call_used_regs
[regno
+ i
] || global_regs
[regno
+ i
]))
3591 /* Function calls clobber all call_used regs. */
3592 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3593 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3598 reg_last_uses
[regno
]
3599 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_last_uses
[regno
]);
3601 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3602 add_dependence (insn
, XEXP (u
, 0), 0);
3604 /* Pseudos that are REG_EQUIV to something may be replaced
3605 by that during reloading. We need only add dependencies for
3606 the address in the REG_EQUIV note. */
3607 if (!reload_completed
3608 && reg_known_equiv_p
[regno
]
3609 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3610 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3612 /* If the register does not already cross any calls, then add this
3613 insn to the sched_before_next_call list so that it will still
3614 not cross calls after scheduling. */
3615 if (REG_N_CALLS_CROSSED (regno
) == 0)
3616 add_dependence (sched_before_next_call
, insn
, REG_DEP_ANTI
);
3623 /* Reading memory. */
3625 rtx pending
, pending_mem
;
3627 pending
= pending_read_insns
;
3628 pending_mem
= pending_read_mems
;
3631 /* If a dependency already exists, don't create a new one. */
3632 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3633 if (read_dependence (XEXP (pending_mem
, 0), x
))
3634 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3636 pending
= XEXP (pending
, 1);
3637 pending_mem
= XEXP (pending_mem
, 1);
3640 pending
= pending_write_insns
;
3641 pending_mem
= pending_write_mems
;
3644 /* If a dependency already exists, don't create a new one. */
3645 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3646 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
3648 add_dependence (insn
, XEXP (pending
, 0), 0);
3650 pending
= XEXP (pending
, 1);
3651 pending_mem
= XEXP (pending_mem
, 1);
3654 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3655 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3657 /* Always add these dependencies to pending_reads, since
3658 this insn may be followed by a write. */
3659 add_insn_mem_dependence (&pending_read_insns
, &pending_read_mems
,
3662 /* Take advantage of tail recursion here. */
3663 sched_analyze_2 (XEXP (x
, 0), insn
);
3669 case UNSPEC_VOLATILE
:
3674 /* Traditional and volatile asm instructions must be considered to use
3675 and clobber all hard registers, all pseudo-registers and all of
3676 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3678 Consider for instance a volatile asm that changes the fpu rounding
3679 mode. An insn should not be moved across this even if it only uses
3680 pseudo-regs because it might give an incorrectly rounded result. */
3681 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
3683 int max_reg
= max_reg_num ();
3684 for (i
= 0; i
< max_reg
; i
++)
3686 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3687 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3688 reg_last_uses
[i
] = 0;
3690 /* reg_last_sets[r] is now a list of insns */
3691 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3692 add_dependence (insn
, XEXP (u
, 0), 0);
3694 reg_pending_sets_all
= 1;
3696 flush_pending_lists (insn
, 0);
3699 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3700 We can not just fall through here since then we would be confused
3701 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3702 traditional asms unlike their normal usage. */
3704 if (code
== ASM_OPERANDS
)
3706 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
3707 sched_analyze_2 (ASM_OPERANDS_INPUT (x
, j
), insn
);
3717 /* These both read and modify the result. We must handle them as writes
3718 to get proper dependencies for following instructions. We must handle
3719 them as reads to get proper dependencies from this to previous
3720 instructions. Thus we need to pass them to both sched_analyze_1
3721 and sched_analyze_2. We must call sched_analyze_2 first in order
3722 to get the proper antecedent for the read. */
3723 sched_analyze_2 (XEXP (x
, 0), insn
);
3724 sched_analyze_1 (x
, insn
);
3731 /* Other cases: walk the insn. */
3732 fmt
= GET_RTX_FORMAT (code
);
3733 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3736 sched_analyze_2 (XEXP (x
, i
), insn
);
3737 else if (fmt
[i
] == 'E')
3738 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3739 sched_analyze_2 (XVECEXP (x
, i
, j
), insn
);
3743 /* Analyze an INSN with pattern X to find all dependencies. */
3746 sched_analyze_insn (x
, insn
, loop_notes
)
3750 register RTX_CODE code
= GET_CODE (x
);
3752 int maxreg
= max_reg_num ();
3755 if (code
== SET
|| code
== CLOBBER
)
3756 sched_analyze_1 (x
, insn
);
3757 else if (code
== PARALLEL
)
3760 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
3762 code
= GET_CODE (XVECEXP (x
, 0, i
));
3763 if (code
== SET
|| code
== CLOBBER
)
3764 sched_analyze_1 (XVECEXP (x
, 0, i
), insn
);
3766 sched_analyze_2 (XVECEXP (x
, 0, i
), insn
);
3770 sched_analyze_2 (x
, insn
);
3772 /* Mark registers CLOBBERED or used by called function. */
3773 if (GET_CODE (insn
) == CALL_INSN
)
3774 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
3776 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
3777 sched_analyze_1 (XEXP (link
, 0), insn
);
3779 sched_analyze_2 (XEXP (link
, 0), insn
);
3782 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic block, then
3783 we must be sure that no instructions are scheduled across it.
3784 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3785 become incorrect. */
3789 int max_reg
= max_reg_num ();
3792 for (i
= 0; i
< max_reg
; i
++)
3795 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3796 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3797 reg_last_uses
[i
] = 0;
3799 /* reg_last_sets[r] is now a list of insns */
3800 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3801 add_dependence (insn
, XEXP (u
, 0), 0);
3803 reg_pending_sets_all
= 1;
3805 flush_pending_lists (insn
, 0);
3808 while (XEXP (link
, 1))
3809 link
= XEXP (link
, 1);
3810 XEXP (link
, 1) = REG_NOTES (insn
);
3811 REG_NOTES (insn
) = loop_notes
;
3814 /* After reload, it is possible for an instruction to have a REG_DEAD note
3815 for a register that actually dies a few instructions earlier. For
3816 example, this can happen with SECONDARY_MEMORY_NEEDED reloads.
3817 In this case, we must consider the insn to use the register mentioned
3818 in the REG_DEAD note. Otherwise, we may accidentally move this insn
3819 after another insn that sets the register, thus getting obviously invalid
3820 rtl. This confuses reorg which believes that REG_DEAD notes are still
3823 ??? We would get better code if we fixed reload to put the REG_DEAD
3824 notes in the right places, but that may not be worth the effort. */
3826 if (reload_completed
)
3830 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
3831 if (REG_NOTE_KIND (note
) == REG_DEAD
)
3832 sched_analyze_2 (XEXP (note
, 0), insn
);
3835 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
3837 /* reg_last_sets[r] is now a list of insns */
3839 = gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
3841 CLEAR_REG_SET (reg_pending_sets
);
3843 if (reg_pending_sets_all
)
3845 for (i
= 0; i
< maxreg
; i
++)
3847 /* reg_last_sets[r] is now a list of insns */
3849 = gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
3851 reg_pending_sets_all
= 0;
3854 /* Handle function calls and function returns created by the epilogue
3856 if (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3861 /* When scheduling instructions, we make sure calls don't lose their
3862 accompanying USE insns by depending them one on another in order.
3864 Also, we must do the same thing for returns created by the epilogue
3865 threading code. Note this code works only in this special case,
3866 because other passes make no guarantee that they will never emit
3867 an instruction between a USE and a RETURN. There is such a guarantee
3868 for USE instructions immediately before a call. */
3870 prev_dep_insn
= insn
;
3871 dep_insn
= PREV_INSN (insn
);
3872 while (GET_CODE (dep_insn
) == INSN
3873 && GET_CODE (PATTERN (dep_insn
)) == USE
3874 && GET_CODE (XEXP (PATTERN (dep_insn
), 0)) == REG
)
3876 SCHED_GROUP_P (prev_dep_insn
) = 1;
3878 /* Make a copy of all dependencies on dep_insn, and add to insn.
3879 This is so that all of the dependencies will apply to the
3882 for (link
= LOG_LINKS (dep_insn
); link
; link
= XEXP (link
, 1))
3883 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3885 prev_dep_insn
= dep_insn
;
3886 dep_insn
= PREV_INSN (dep_insn
);
3891 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3892 for every dependency. */
3895 sched_analyze (head
, tail
)
3902 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3904 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3906 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3909 else if (GET_CODE (insn
) == CALL_INSN
)
3914 CANT_MOVE (insn
) = 1;
3916 /* Any instruction using a hard register which may get clobbered
3917 by a call needs to be marked as dependent on this call.
3918 This prevents a use of a hard return reg from being moved
3919 past a void call (i.e. it does not explicitly set the hard
3922 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3923 all registers, not just hard registers, may be clobbered by this
3926 /* Insn, being a CALL_INSN, magically depends on
3927 `last_function_call' already. */
3929 if (NEXT_INSN (insn
) && GET_CODE (NEXT_INSN (insn
)) == NOTE
3930 && NOTE_LINE_NUMBER (NEXT_INSN (insn
)) == NOTE_INSN_SETJMP
)
3932 int max_reg
= max_reg_num ();
3933 for (i
= 0; i
< max_reg
; i
++)
3935 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3936 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3938 reg_last_uses
[i
] = 0;
3940 /* reg_last_sets[r] is now a list of insns */
3941 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3942 add_dependence (insn
, XEXP (u
, 0), 0);
3944 reg_pending_sets_all
= 1;
3946 /* Add a pair of fake REG_NOTE which we will later
3947 convert back into a NOTE_INSN_SETJMP note. See
3948 reemit_notes for why we use a pair of NOTEs. */
3949 REG_NOTES (insn
) = gen_rtx_EXPR_LIST (REG_DEAD
,
3952 REG_NOTES (insn
) = gen_rtx_EXPR_LIST (REG_DEAD
,
3953 GEN_INT (NOTE_INSN_SETJMP
),
3958 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3959 if (call_used_regs
[i
] || global_regs
[i
])
3961 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3962 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3963 reg_last_uses
[i
] = 0;
3965 /* reg_last_sets[r] is now a list of insns */
3966 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3967 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3969 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3973 /* For each insn which shouldn't cross a call, add a dependence
3974 between that insn and this call insn. */
3975 x
= LOG_LINKS (sched_before_next_call
);
3978 add_dependence (insn
, XEXP (x
, 0), REG_DEP_ANTI
);
3981 LOG_LINKS (sched_before_next_call
) = 0;
3983 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3986 /* In the absence of interprocedural alias analysis, we must flush
3987 all pending reads and writes, and start new dependencies starting
3988 from here. But only flush writes for constant calls (which may
3989 be passed a pointer to something we haven't written yet). */
3990 flush_pending_lists (insn
, CONST_CALL_P (insn
));
3992 /* Depend this function call (actually, the user of this
3993 function call) on all hard register clobberage. */
3995 /* last_function_call is now a list of insns */
3997 = gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
4000 /* See comments on reemit_notes as to why we do this. */
4001 else if (GET_CODE (insn
) == NOTE
4002 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
4003 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
4004 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
4005 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
4006 || (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
4007 && GET_CODE (PREV_INSN (insn
)) != CALL_INSN
)))
4009 loop_notes
= gen_rtx_EXPR_LIST (REG_DEAD
,
4010 GEN_INT (NOTE_BLOCK_NUMBER (insn
)),
4012 loop_notes
= gen_rtx_EXPR_LIST (REG_DEAD
,
4013 GEN_INT (NOTE_LINE_NUMBER (insn
)),
4015 CONST_CALL_P (loop_notes
) = CONST_CALL_P (insn
);
4024 /* Called when we see a set of a register. If death is true, then we are
4025 scanning backwards. Mark that register as unborn. If nobody says
4026 otherwise, that is how things will remain. If death is false, then we
4027 are scanning forwards. Mark that register as being born. */
4030 sched_note_set (x
, death
)
4035 register rtx reg
= SET_DEST (x
);
4041 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == STRICT_LOW_PART
4042 || GET_CODE (reg
) == SIGN_EXTRACT
|| GET_CODE (reg
) == ZERO_EXTRACT
)
4044 /* Must treat modification of just one hardware register of a multi-reg
4045 value or just a byte field of a register exactly the same way that
4046 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
4047 does not kill the entire register. */
4048 if (GET_CODE (reg
) != SUBREG
4049 || REG_SIZE (SUBREG_REG (reg
)) > REG_SIZE (reg
))
4052 reg
= SUBREG_REG (reg
);
4055 if (GET_CODE (reg
) != REG
)
4058 /* Global registers are always live, so the code below does not apply
4061 regno
= REGNO (reg
);
4062 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
4066 /* If we only set part of the register, then this set does not
4071 /* Try killing this register. */
4072 if (regno
< FIRST_PSEUDO_REGISTER
)
4074 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
4077 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4082 /* Recompute REG_BASIC_BLOCK as we update all the other
4083 dataflow information. */
4084 if (sched_reg_basic_block
[regno
] == REG_BLOCK_UNKNOWN
)
4085 sched_reg_basic_block
[regno
] = current_block_num
;
4086 else if (sched_reg_basic_block
[regno
] != current_block_num
)
4087 sched_reg_basic_block
[regno
] = REG_BLOCK_GLOBAL
;
4089 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
);
4094 /* Make the register live again. */
4095 if (regno
< FIRST_PSEUDO_REGISTER
)
4097 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
4100 SET_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4105 SET_REGNO_REG_SET (bb_live_regs
, regno
);
4111 /* Macros and functions for keeping the priority queue sorted, and
4112 dealing with queueing and dequeueing of instructions. */
4114 #define SCHED_SORT(READY, N_READY) \
4115 do { if ((N_READY) == 2) \
4116 swap_sort (READY, N_READY); \
4117 else if ((N_READY) > 2) \
4118 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4121 /* Returns a positive value if x is preferred; returns a negative value if
4122 y is preferred. Should never return 0, since that will make the sort
4126 rank_for_schedule (x
, y
)
4132 int tmp_class
, tmp2_class
;
4133 int val
, priority_val
, spec_val
, prob_val
, weight_val
;
4136 /* prefer insn with higher priority */
4137 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
4139 return priority_val
;
4141 /* prefer an insn with smaller contribution to registers-pressure */
4142 if (!reload_completed
&&
4143 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
4144 return (weight_val
);
4146 /* some comparison make sense in interblock scheduling only */
4147 if (INSN_BB (tmp
) != INSN_BB (tmp2
))
4149 /* prefer an inblock motion on an interblock motion */
4150 if ((INSN_BB (tmp2
) == target_bb
) && (INSN_BB (tmp
) != target_bb
))
4152 if ((INSN_BB (tmp
) == target_bb
) && (INSN_BB (tmp2
) != target_bb
))
4155 /* prefer a useful motion on a speculative one */
4156 if ((spec_val
= IS_SPECULATIVE_INSN (tmp
) - IS_SPECULATIVE_INSN (tmp2
)))
4159 /* prefer a more probable (speculative) insn */
4160 prob_val
= INSN_PROBABILITY (tmp2
) - INSN_PROBABILITY (tmp
);
4165 /* compare insns based on their relation to the last-scheduled-insn */
4166 if (last_scheduled_insn
)
4168 /* Classify the instructions into three classes:
4169 1) Data dependent on last schedule insn.
4170 2) Anti/Output dependent on last scheduled insn.
4171 3) Independent of last scheduled insn, or has latency of one.
4172 Choose the insn from the highest numbered class if different. */
4173 link
= find_insn_list (tmp
, INSN_DEPEND (last_scheduled_insn
));
4174 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp
) == 1)
4176 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4181 link
= find_insn_list (tmp2
, INSN_DEPEND (last_scheduled_insn
));
4182 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp2
) == 1)
4184 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4189 if ((val
= tmp2_class
- tmp_class
))
4193 /* If insns are equally good, sort by INSN_LUID (original insn order),
4194 so that we make the sort stable. This minimizes instruction movement,
4195 thus minimizing sched's effect on debugging and cross-jumping. */
4196 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
4199 /* Resort the array A in which only element at index N may be out of order. */
4201 __inline
static void
4206 rtx insn
= a
[n
- 1];
4209 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
4217 static int max_priority
;
4219 /* Add INSN to the insn queue so that it can be executed at least
4220 N_CYCLES after the currently executing insn. Preserve insns
4221 chain for debugging purposes. */
4223 __inline
static void
4224 queue_insn (insn
, n_cycles
)
4228 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
4229 rtx link
= rtx_alloc (INSN_LIST
);
4230 XEXP (link
, 0) = insn
;
4231 XEXP (link
, 1) = insn_queue
[next_q
];
4232 insn_queue
[next_q
] = link
;
4235 if (sched_verbose
>= 2)
4237 fprintf (dump
, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn
));
4239 if (INSN_BB (insn
) != target_bb
)
4240 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
4242 fprintf (dump
, "queued for %d cycles.\n", n_cycles
);
4247 /* Return nonzero if PAT is the pattern of an insn which makes a
4251 birthing_insn_p (pat
)
4256 if (reload_completed
== 1)
4259 if (GET_CODE (pat
) == SET
4260 && GET_CODE (SET_DEST (pat
)) == REG
)
4262 rtx dest
= SET_DEST (pat
);
4263 int i
= REGNO (dest
);
4265 /* It would be more accurate to use refers_to_regno_p or
4266 reg_mentioned_p to determine when the dest is not live before this
4269 if (REGNO_REG_SET_P (bb_live_regs
, i
))
4270 return (REG_N_SETS (i
) == 1);
4274 if (GET_CODE (pat
) == PARALLEL
)
4276 for (j
= 0; j
< XVECLEN (pat
, 0); j
++)
4277 if (birthing_insn_p (XVECEXP (pat
, 0, j
)))
4283 /* PREV is an insn that is ready to execute. Adjust its priority if that
4284 will help shorten register lifetimes. */
4286 __inline
static void
4287 adjust_priority (prev
)
4290 /* Trying to shorten register lives after reload has completed
4291 is useless and wrong. It gives inaccurate schedules. */
4292 if (reload_completed
== 0)
4297 /* ??? This code has no effect, because REG_DEAD notes are removed
4298 before we ever get here. */
4299 for (note
= REG_NOTES (prev
); note
; note
= XEXP (note
, 1))
4300 if (REG_NOTE_KIND (note
) == REG_DEAD
)
4303 /* Defer scheduling insns which kill registers, since that
4304 shortens register lives. Prefer scheduling insns which
4305 make registers live for the same reason. */
4309 INSN_PRIORITY (prev
) >>= 3;
4312 INSN_PRIORITY (prev
) >>= 2;
4316 INSN_PRIORITY (prev
) >>= 1;
4319 if (birthing_insn_p (PATTERN (prev
)))
4321 int max
= max_priority
;
4323 if (max
> INSN_PRIORITY (prev
))
4324 INSN_PRIORITY (prev
) = max
;
4328 #ifdef ADJUST_PRIORITY
4329 ADJUST_PRIORITY (prev
);
4334 /* INSN is the "currently executing insn". Launch each insn which was
4335 waiting on INSN. READY is a vector of insns which are ready to fire.
4336 N_READY is the number of elements in READY. CLOCK is the current
4340 schedule_insn (insn
, ready
, n_ready
, clock
)
4349 unit
= insn_unit (insn
);
4351 if (sched_verbose
>= 2)
4353 fprintf (dump
, ";;\t\t--> scheduling insn <<<%d>>> on unit ", INSN_UID (insn
));
4354 insn_print_units (insn
);
4355 fprintf (dump
, "\n");
4358 if (sched_verbose
&& unit
== -1)
4359 visualize_no_unit (insn
);
4361 if (MAX_BLOCKAGE
> 1 || issue_rate
> 1 || sched_verbose
)
4362 schedule_unit (unit
, insn
, clock
);
4364 if (INSN_DEPEND (insn
) == 0)
4367 /* This is used by the function adjust_priority above. */
4369 max_priority
= MAX (INSN_PRIORITY (ready
[0]), INSN_PRIORITY (insn
));
4371 max_priority
= INSN_PRIORITY (insn
);
4373 for (link
= INSN_DEPEND (insn
); link
!= 0; link
= XEXP (link
, 1))
4375 rtx next
= XEXP (link
, 0);
4376 int cost
= insn_cost (insn
, link
, next
);
4378 INSN_TICK (next
) = MAX (INSN_TICK (next
), clock
+ cost
);
4380 if ((INSN_DEP_COUNT (next
) -= 1) == 0)
4382 int effective_cost
= INSN_TICK (next
) - clock
;
4384 /* For speculative insns, before inserting to ready/queue,
4385 check live, exception-free, and issue-delay */
4386 if (INSN_BB (next
) != target_bb
4387 && (!IS_VALID (INSN_BB (next
))
4389 || (IS_SPECULATIVE_INSN (next
)
4390 && (insn_issue_delay (next
) > 3
4391 || !check_live (next
, INSN_BB (next
))
4392 || !is_exception_free (next
, INSN_BB (next
), target_bb
)))))
4395 if (sched_verbose
>= 2)
4397 fprintf (dump
, ";;\t\tdependences resolved: insn %d ", INSN_UID (next
));
4399 if (current_nr_blocks
> 1 && INSN_BB (next
) != target_bb
)
4400 fprintf (dump
, "/b%d ", INSN_BLOCK (next
));
4402 if (effective_cost
<= 1)
4403 fprintf (dump
, "into ready\n");
4405 fprintf (dump
, "into queue with cost=%d\n", effective_cost
);
4408 /* Adjust the priority of NEXT and either put it on the ready
4409 list or queue it. */
4410 adjust_priority (next
);
4411 if (effective_cost
<= 1)
4412 ready
[n_ready
++] = next
;
4414 queue_insn (next
, effective_cost
);
4422 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4426 create_reg_dead_note (reg
, insn
)
4431 /* The number of registers killed after scheduling must be the same as the
4432 number of registers killed before scheduling. The number of REG_DEAD
4433 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4434 might become one DImode hard register REG_DEAD note, but the number of
4435 registers killed will be conserved.
4437 We carefully remove REG_DEAD notes from the dead_notes list, so that
4438 there will be none left at the end. If we run out early, then there
4439 is a bug somewhere in flow, combine and/or sched. */
4441 if (dead_notes
== 0)
4443 if (current_nr_blocks
<= 1)
4447 link
= rtx_alloc (EXPR_LIST
);
4448 PUT_REG_NOTE_KIND (link
, REG_DEAD
);
4453 /* Number of regs killed by REG. */
4454 int regs_killed
= (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
? 1
4455 : HARD_REGNO_NREGS (REGNO (reg
), GET_MODE (reg
)));
4456 /* Number of regs killed by REG_DEAD notes taken off the list. */
4460 reg_note_regs
= (REGNO (XEXP (link
, 0)) >= FIRST_PSEUDO_REGISTER
? 1
4461 : HARD_REGNO_NREGS (REGNO (XEXP (link
, 0)),
4462 GET_MODE (XEXP (link
, 0))));
4463 while (reg_note_regs
< regs_killed
)
4465 link
= XEXP (link
, 1);
4467 /* LINK might be zero if we killed more registers after scheduling
4468 than before, and the last hard register we kill is actually
4471 This is normal for interblock scheduling, so deal with it in
4472 that case, else abort. */
4473 if (link
== NULL_RTX
&& current_nr_blocks
<= 1)
4475 else if (link
== NULL_RTX
)
4477 link
= rtx_alloc (EXPR_LIST
);
4478 PUT_REG_NOTE_KIND (link
, REG_DEAD
);
4479 XEXP (link
, 0) = gen_rtx_REG (word_mode
, 0);
4480 XEXP (link
, 1) = NULL_RTX
;
4483 reg_note_regs
+= (REGNO (XEXP (link
, 0)) >= FIRST_PSEUDO_REGISTER
? 1
4484 : HARD_REGNO_NREGS (REGNO (XEXP (link
, 0)),
4485 GET_MODE (XEXP (link
, 0))));
4487 dead_notes
= XEXP (link
, 1);
4489 /* If we took too many regs kills off, put the extra ones back. */
4490 while (reg_note_regs
> regs_killed
)
4492 rtx temp_reg
, temp_link
;
4494 temp_reg
= gen_rtx_REG (word_mode
, 0);
4495 temp_link
= rtx_alloc (EXPR_LIST
);
4496 PUT_REG_NOTE_KIND (temp_link
, REG_DEAD
);
4497 XEXP (temp_link
, 0) = temp_reg
;
4498 XEXP (temp_link
, 1) = dead_notes
;
4499 dead_notes
= temp_link
;
4504 XEXP (link
, 0) = reg
;
4505 XEXP (link
, 1) = REG_NOTES (insn
);
4506 REG_NOTES (insn
) = link
;
4509 /* Subroutine on attach_deaths_insn--handles the recursive search
4510 through INSN. If SET_P is true, then x is being modified by the insn. */
4513 attach_deaths (x
, insn
, set_p
)
4520 register enum rtx_code code
;
4526 code
= GET_CODE (x
);
4538 /* Get rid of the easy cases first. */
4543 /* If the register dies in this insn, queue that note, and mark
4544 this register as needing to die. */
4545 /* This code is very similar to mark_used_1 (if set_p is false)
4546 and mark_set_1 (if set_p is true) in flow.c. */
4556 all_needed
= some_needed
= REGNO_REG_SET_P (old_live_regs
, regno
);
4557 if (regno
< FIRST_PSEUDO_REGISTER
)
4561 n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4564 int needed
= (REGNO_REG_SET_P (old_live_regs
, regno
+ n
));
4565 some_needed
|= needed
;
4566 all_needed
&= needed
;
4570 /* If it wasn't live before we started, then add a REG_DEAD note.
4571 We must check the previous lifetime info not the current info,
4572 because we may have to execute this code several times, e.g.
4573 once for a clobber (which doesn't add a note) and later
4574 for a use (which does add a note).
4576 Always make the register live. We must do this even if it was
4577 live before, because this may be an insn which sets and uses
4578 the same register, in which case the register has already been
4579 killed, so we must make it live again.
4581 Global registers are always live, and should never have a REG_DEAD
4582 note added for them, so none of the code below applies to them. */
4584 if (regno
>= FIRST_PSEUDO_REGISTER
|| ! global_regs
[regno
])
4586 /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
4587 STACK_POINTER_REGNUM, since these are always considered to be
4588 live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
4589 if (regno
!= FRAME_POINTER_REGNUM
4590 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4591 && ! (regno
== HARD_FRAME_POINTER_REGNUM
)
4593 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4594 && ! (regno
== ARG_POINTER_REGNUM
&& fixed_regs
[regno
])
4596 && regno
!= STACK_POINTER_REGNUM
)
4598 /* ??? It is perhaps a dead_or_set_p bug that it does
4599 not check for REG_UNUSED notes itself. This is necessary
4600 for the case where the SET_DEST is a subreg of regno, as
4601 dead_or_set_p handles subregs specially. */
4602 if (! all_needed
&& ! dead_or_set_p (insn
, x
)
4603 && ! find_reg_note (insn
, REG_UNUSED
, x
))
4605 /* Check for the case where the register dying partially
4606 overlaps the register set by this insn. */
4607 if (regno
< FIRST_PSEUDO_REGISTER
4608 && HARD_REGNO_NREGS (regno
, GET_MODE (x
)) > 1)
4610 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4612 some_needed
|= dead_or_set_regno_p (insn
, regno
+ n
);
4615 /* If none of the words in X is needed, make a REG_DEAD
4616 note. Otherwise, we must make partial REG_DEAD
4619 create_reg_dead_note (x
, insn
);
4624 /* Don't make a REG_DEAD note for a part of a
4625 register that is set in the insn. */
4626 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
)) - 1;
4628 if (! REGNO_REG_SET_P (old_live_regs
, regno
+i
)
4629 && ! dead_or_set_regno_p (insn
, regno
+ i
))
4630 create_reg_dead_note (gen_rtx_REG (reg_raw_mode
[regno
+ i
],
4637 if (regno
< FIRST_PSEUDO_REGISTER
)
4639 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4642 SET_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4647 /* Recompute REG_BASIC_BLOCK as we update all the other
4648 dataflow information. */
4649 if (sched_reg_basic_block
[regno
] == REG_BLOCK_UNKNOWN
)
4650 sched_reg_basic_block
[regno
] = current_block_num
;
4651 else if (sched_reg_basic_block
[regno
] != current_block_num
)
4652 sched_reg_basic_block
[regno
] = REG_BLOCK_GLOBAL
;
4654 SET_REGNO_REG_SET (bb_live_regs
, regno
);
4661 /* Handle tail-recursive case. */
4662 attach_deaths (XEXP (x
, 0), insn
, 0);
4666 case STRICT_LOW_PART
:
4667 /* These two cases preserve the value of SET_P, so handle them
4669 attach_deaths (XEXP (x
, 0), insn
, set_p
);
4674 /* This case preserves the value of SET_P for the first operand, but
4675 clears it for the other two. */
4676 attach_deaths (XEXP (x
, 0), insn
, set_p
);
4677 attach_deaths (XEXP (x
, 1), insn
, 0);
4678 attach_deaths (XEXP (x
, 2), insn
, 0);
4682 /* Other cases: walk the insn. */
4683 fmt
= GET_RTX_FORMAT (code
);
4684 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4687 attach_deaths (XEXP (x
, i
), insn
, 0);
4688 else if (fmt
[i
] == 'E')
4689 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
4690 attach_deaths (XVECEXP (x
, i
, j
), insn
, 0);
4695 /* After INSN has executed, add register death notes for each register
4696 that is dead after INSN. */
4699 attach_deaths_insn (insn
)
4702 rtx x
= PATTERN (insn
);
4703 register RTX_CODE code
= GET_CODE (x
);
4708 attach_deaths (SET_SRC (x
), insn
, 0);
4710 /* A register might die here even if it is the destination, e.g.
4711 it is the target of a volatile read and is otherwise unused.
4712 Hence we must always call attach_deaths for the SET_DEST. */
4713 attach_deaths (SET_DEST (x
), insn
, 1);
4715 else if (code
== PARALLEL
)
4718 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
4720 code
= GET_CODE (XVECEXP (x
, 0, i
));
4723 attach_deaths (SET_SRC (XVECEXP (x
, 0, i
)), insn
, 0);
4725 attach_deaths (SET_DEST (XVECEXP (x
, 0, i
)), insn
, 1);
4727 /* Flow does not add REG_DEAD notes to registers that die in
4728 clobbers, so we can't either. */
4729 else if (code
!= CLOBBER
)
4730 attach_deaths (XVECEXP (x
, 0, i
), insn
, 0);
4733 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4734 MEM being clobbered, just like flow. */
4735 else if (code
== CLOBBER
&& GET_CODE (XEXP (x
, 0)) == MEM
)
4736 attach_deaths (XEXP (XEXP (x
, 0), 0), insn
, 0);
4737 /* Otherwise don't add a death note to things being clobbered. */
4738 else if (code
!= CLOBBER
)
4739 attach_deaths (x
, insn
, 0);
4741 /* Make death notes for things used in the called function. */
4742 if (GET_CODE (insn
) == CALL_INSN
)
4743 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
4744 attach_deaths (XEXP (XEXP (link
, 0), 0), insn
,
4745 GET_CODE (XEXP (link
, 0)) == CLOBBER
);
4748 /* functions for handlnig of notes */
4750 /* Delete notes beginning with INSN and put them in the chain
4751 of notes ended by NOTE_LIST.
4752 Returns the insn following the notes. */
4755 unlink_other_notes (insn
, tail
)
4758 rtx prev
= PREV_INSN (insn
);
4760 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4762 rtx next
= NEXT_INSN (insn
);
4763 /* Delete the note from its current position. */
4765 NEXT_INSN (prev
) = next
;
4767 PREV_INSN (next
) = prev
;
4769 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4770 immediately after the call they follow. We use a fake
4771 (REG_DEAD (const_int -1)) note to remember them.
4772 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4773 if (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_SETJMP
4774 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
4775 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
4776 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_BEG
4777 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_END
)
4779 /* Insert the note at the end of the notes list. */
4780 PREV_INSN (insn
) = note_list
;
4782 NEXT_INSN (note_list
) = insn
;
4791 /* Delete line notes beginning with INSN. Record line-number notes so
4792 they can be reused. Returns the insn following the notes. */
4795 unlink_line_notes (insn
, tail
)
4798 rtx prev
= PREV_INSN (insn
);
4800 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4802 rtx next
= NEXT_INSN (insn
);
4804 if (write_symbols
!= NO_DEBUG
&& NOTE_LINE_NUMBER (insn
) > 0)
4806 /* Delete the note from its current position. */
4808 NEXT_INSN (prev
) = next
;
4810 PREV_INSN (next
) = prev
;
4812 /* Record line-number notes so they can be reused. */
4813 LINE_NOTE (insn
) = insn
;
4823 /* Return the head and tail pointers of BB. */
4825 __inline
static void
4826 get_block_head_tail (bb
, headp
, tailp
)
4836 b
= BB_TO_BLOCK (bb
);
4838 /* HEAD and TAIL delimit the basic block being scheduled. */
4839 head
= basic_block_head
[b
];
4840 tail
= basic_block_end
[b
];
4842 /* Don't include any notes or labels at the beginning of the
4843 basic block, or notes at the ends of basic blocks. */
4844 while (head
!= tail
)
4846 if (GET_CODE (head
) == NOTE
)
4847 head
= NEXT_INSN (head
);
4848 else if (GET_CODE (tail
) == NOTE
)
4849 tail
= PREV_INSN (tail
);
4850 else if (GET_CODE (head
) == CODE_LABEL
)
4851 head
= NEXT_INSN (head
);
4860 /* Delete line notes from bb. Save them so they can be later restored
4861 (in restore_line_notes ()). */
4872 get_block_head_tail (bb
, &head
, &tail
);
4875 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
4878 next_tail
= NEXT_INSN (tail
);
4879 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4883 /* Farm out notes, and maybe save them in NOTE_LIST.
4884 This is needed to keep the debugger from
4885 getting completely deranged. */
4886 if (GET_CODE (insn
) == NOTE
)
4889 insn
= unlink_line_notes (insn
, next_tail
);
4895 if (insn
== next_tail
)
4901 /* Save line number notes for each insn in bb. */
4904 save_line_notes (bb
)
4910 /* We must use the true line number for the first insn in the block
4911 that was computed and saved at the start of this pass. We can't
4912 use the current line number, because scheduling of the previous
4913 block may have changed the current line number. */
4915 rtx line
= line_note_head
[BB_TO_BLOCK (bb
)];
4918 get_block_head_tail (bb
, &head
, &tail
);
4919 next_tail
= NEXT_INSN (tail
);
4921 for (insn
= basic_block_head
[BB_TO_BLOCK (bb
)];
4923 insn
= NEXT_INSN (insn
))
4924 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4927 LINE_NOTE (insn
) = line
;
4931 /* After bb was scheduled, insert line notes into the insns list. */
4934 restore_line_notes (bb
)
4937 rtx line
, note
, prev
, new;
4938 int added_notes
= 0;
4940 rtx head
, next_tail
, insn
;
4942 b
= BB_TO_BLOCK (bb
);
4944 head
= basic_block_head
[b
];
4945 next_tail
= NEXT_INSN (basic_block_end
[b
]);
4947 /* Determine the current line-number. We want to know the current
4948 line number of the first insn of the block here, in case it is
4949 different from the true line number that was saved earlier. If
4950 different, then we need a line number note before the first insn
4951 of this block. If it happens to be the same, then we don't want to
4952 emit another line number note here. */
4953 for (line
= head
; line
; line
= PREV_INSN (line
))
4954 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
4957 /* Walk the insns keeping track of the current line-number and inserting
4958 the line-number notes as needed. */
4959 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4960 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4962 /* This used to emit line number notes before every non-deleted note.
4963 However, this confuses a debugger, because line notes not separated
4964 by real instructions all end up at the same address. I can find no
4965 use for line number notes before other notes, so none are emitted. */
4966 else if (GET_CODE (insn
) != NOTE
4967 && (note
= LINE_NOTE (insn
)) != 0
4970 || NOTE_LINE_NUMBER (note
) != NOTE_LINE_NUMBER (line
)
4971 || NOTE_SOURCE_FILE (note
) != NOTE_SOURCE_FILE (line
)))
4974 prev
= PREV_INSN (insn
);
4975 if (LINE_NOTE (note
))
4977 /* Re-use the original line-number note. */
4978 LINE_NOTE (note
) = 0;
4979 PREV_INSN (note
) = prev
;
4980 NEXT_INSN (prev
) = note
;
4981 PREV_INSN (insn
) = note
;
4982 NEXT_INSN (note
) = insn
;
4987 new = emit_note_after (NOTE_LINE_NUMBER (note
), prev
);
4988 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note
);
4989 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note
);
4992 if (sched_verbose
&& added_notes
)
4993 fprintf (dump
, ";; added %d line-number notes\n", added_notes
);
4996 /* After scheduling the function, delete redundant line notes from the
5000 rm_redundant_line_notes ()
5003 rtx insn
= get_insns ();
5004 int active_insn
= 0;
5007 /* Walk the insns deleting redundant line-number notes. Many of these
5008 are already present. The remainder tend to occur at basic
5009 block boundaries. */
5010 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
5011 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
5013 /* If there are no active insns following, INSN is redundant. */
5014 if (active_insn
== 0)
5017 NOTE_SOURCE_FILE (insn
) = 0;
5018 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
5020 /* If the line number is unchanged, LINE is redundant. */
5022 && NOTE_LINE_NUMBER (line
) == NOTE_LINE_NUMBER (insn
)
5023 && NOTE_SOURCE_FILE (line
) == NOTE_SOURCE_FILE (insn
))
5026 NOTE_SOURCE_FILE (line
) = 0;
5027 NOTE_LINE_NUMBER (line
) = NOTE_INSN_DELETED
;
5034 else if (!((GET_CODE (insn
) == NOTE
5035 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
5036 || (GET_CODE (insn
) == INSN
5037 && (GET_CODE (PATTERN (insn
)) == USE
5038 || GET_CODE (PATTERN (insn
)) == CLOBBER
))))
5041 if (sched_verbose
&& notes
)
5042 fprintf (dump
, ";; deleted %d line-number notes\n", notes
);
5045 /* Delete notes between head and tail and put them in the chain
5046 of notes ended by NOTE_LIST. */
5049 rm_other_notes (head
, tail
)
5057 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
5060 next_tail
= NEXT_INSN (tail
);
5061 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5065 /* Farm out notes, and maybe save them in NOTE_LIST.
5066 This is needed to keep the debugger from
5067 getting completely deranged. */
5068 if (GET_CODE (insn
) == NOTE
)
5072 insn
= unlink_other_notes (insn
, next_tail
);
5078 if (insn
== next_tail
)
5084 /* Constructor for `sometimes' data structure. */
5087 new_sometimes_live (regs_sometimes_live
, regno
, sometimes_max
)
5088 struct sometimes
*regs_sometimes_live
;
5092 register struct sometimes
*p
;
5094 /* There should never be a register greater than max_regno here. If there
5095 is, it means that a define_split has created a new pseudo reg. This
5096 is not allowed, since there will not be flow info available for any
5097 new register, so catch the error here. */
5098 if (regno
>= max_regno
)
5101 p
= ®s_sometimes_live
[sometimes_max
];
5104 p
->calls_crossed
= 0;
5106 return sometimes_max
;
5109 /* Count lengths of all regs we are currently tracking,
5110 and find new registers no longer live. */
5113 finish_sometimes_live (regs_sometimes_live
, sometimes_max
)
5114 struct sometimes
*regs_sometimes_live
;
5119 for (i
= 0; i
< sometimes_max
; i
++)
5121 register struct sometimes
*p
= ®s_sometimes_live
[i
];
5122 int regno
= p
->regno
;
5124 sched_reg_live_length
[regno
] += p
->live_length
;
5125 sched_reg_n_calls_crossed
[regno
] += p
->calls_crossed
;
5129 /* functions for computation of registers live/usage info */
5131 /* It is assumed that prior to scheduling basic_block_live_at_start (b)
5132 contains the registers that are alive at the entry to b.
5134 Two passes follow: The first pass is performed before the scheduling
5135 of a region. It scans each block of the region forward, computing
5136 the set of registers alive at the end of the basic block and
5137 discard REG_DEAD notes (done by find_pre_sched_live ()).
5139 The second path is invoked after scheduling all region blocks.
5140 It scans each block of the region backward, a block being traversed
5141 only after its succesors in the region. When the set of registers
5142 live at the end of a basic block may be changed by the scheduling
5143 (this may happen for multiple blocks region), it is computed as
5144 the union of the registers live at the start of its succesors.
5145 The last-use information is updated by inserting REG_DEAD notes.
5146 (done by find_post_sched_live ()) */
5148 /* Scan all the insns to be scheduled, removing register death notes.
5149 Register death notes end up in DEAD_NOTES.
5150 Recreate the register life information for the end of this basic
5154 find_pre_sched_live (bb
)
5157 rtx insn
, next_tail
, head
, tail
;
5158 int b
= BB_TO_BLOCK (bb
);
5160 get_block_head_tail (bb
, &head
, &tail
);
5161 COPY_REG_SET (bb_live_regs
, basic_block_live_at_start
[b
]);
5162 next_tail
= NEXT_INSN (tail
);
5164 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5166 rtx prev
, next
, link
;
5169 /* Handle register life information. */
5170 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
5172 /* See if the register gets born here. */
5173 /* We must check for registers being born before we check for
5174 registers dying. It is possible for a register to be born and
5175 die in the same insn, e.g. reading from a volatile memory
5176 location into an otherwise unused register. Such a register
5177 must be marked as dead after this insn. */
5178 if (GET_CODE (PATTERN (insn
)) == SET
5179 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
5181 sched_note_set (PATTERN (insn
), 0);
5185 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
5188 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5189 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
5190 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
5192 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 0);
5196 /* ??? This code is obsolete and should be deleted. It
5197 is harmless though, so we will leave it in for now. */
5198 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5199 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == USE
)
5200 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 0);
5203 /* Each call cobbers (makes live) all call-clobbered regs
5204 that are not global or fixed. Note that the function-value
5205 reg is a call_clobbered reg. */
5206 if (GET_CODE (insn
) == CALL_INSN
)
5209 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
5210 if (call_used_regs
[j
] && !global_regs
[j
]
5213 SET_REGNO_REG_SET (bb_live_regs
, j
);
5217 /* Need to know what registers this insn kills. */
5218 for (prev
= 0, link
= REG_NOTES (insn
); link
; link
= next
)
5220 next
= XEXP (link
, 1);
5221 if ((REG_NOTE_KIND (link
) == REG_DEAD
5222 || REG_NOTE_KIND (link
) == REG_UNUSED
)
5223 /* Verify that the REG_NOTE has a valid value. */
5224 && GET_CODE (XEXP (link
, 0)) == REG
)
5226 register int regno
= REGNO (XEXP (link
, 0));
5230 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5232 if (REG_NOTE_KIND (link
) == REG_DEAD
)
5235 XEXP (prev
, 1) = next
;
5237 REG_NOTES (insn
) = next
;
5238 XEXP (link
, 1) = dead_notes
;
5244 if (regno
< FIRST_PSEUDO_REGISTER
)
5246 int j
= HARD_REGNO_NREGS (regno
,
5247 GET_MODE (XEXP (link
, 0)));
5250 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
+j
);
5255 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
);
5263 INSN_REG_WEIGHT (insn
) = reg_weight
;
5267 /* Update register life and usage information for block bb
5268 after scheduling. Put register dead notes back in the code. */
5271 find_post_sched_live (bb
)
5278 rtx head
, tail
, prev_head
, next_tail
;
5280 register struct sometimes
*regs_sometimes_live
;
5282 b
= BB_TO_BLOCK (bb
);
5284 /* compute live regs at the end of bb as a function of its successors. */
5285 if (current_nr_blocks
> 1)
5290 first_edge
= e
= OUT_EDGES (b
);
5291 CLEAR_REG_SET (bb_live_regs
);
5298 b_succ
= TO_BLOCK (e
);
5299 IOR_REG_SET (bb_live_regs
, basic_block_live_at_start
[b_succ
]);
5302 while (e
!= first_edge
);
5305 get_block_head_tail (bb
, &head
, &tail
);
5306 next_tail
= NEXT_INSN (tail
);
5307 prev_head
= PREV_INSN (head
);
5309 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
5310 if (REGNO_REG_SET_P (bb_live_regs
, i
))
5311 sched_reg_basic_block
[i
] = REG_BLOCK_GLOBAL
;
5313 /* if the block is empty, same regs are alive at its end and its start.
5314 since this is not guaranteed after interblock scheduling, make sure they
5315 are truly identical. */
5316 if (NEXT_INSN (prev_head
) == tail
5317 && (GET_RTX_CLASS (GET_CODE (tail
)) != 'i'))
5319 if (current_nr_blocks
> 1)
5320 COPY_REG_SET (basic_block_live_at_start
[b
], bb_live_regs
);
5325 b
= BB_TO_BLOCK (bb
);
5326 current_block_num
= b
;
5328 /* Keep track of register lives. */
5329 old_live_regs
= ALLOCA_REG_SET ();
5331 = (struct sometimes
*) alloca (max_regno
* sizeof (struct sometimes
));
5334 /* initiate "sometimes" data, starting with registers live at end */
5336 COPY_REG_SET (old_live_regs
, bb_live_regs
);
5337 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, 0, j
,
5340 = new_sometimes_live (regs_sometimes_live
,
5344 /* scan insns back, computing regs live info */
5345 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
5347 /* First we kill registers set by this insn, and then we
5348 make registers used by this insn live. This is the opposite
5349 order used above because we are traversing the instructions
5352 /* Strictly speaking, we should scan REG_UNUSED notes and make
5353 every register mentioned there live, however, we will just
5354 kill them again immediately below, so there doesn't seem to
5355 be any reason why we bother to do this. */
5357 /* See if this is the last notice we must take of a register. */
5358 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5361 if (GET_CODE (PATTERN (insn
)) == SET
5362 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
5363 sched_note_set (PATTERN (insn
), 1);
5364 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
5366 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5367 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
5368 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
5369 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 1);
5372 /* This code keeps life analysis information up to date. */
5373 if (GET_CODE (insn
) == CALL_INSN
)
5375 register struct sometimes
*p
;
5377 /* A call kills all call used registers that are not
5378 global or fixed, except for those mentioned in the call
5379 pattern which will be made live again later. */
5380 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
5381 if (call_used_regs
[i
] && ! global_regs
[i
]
5384 CLEAR_REGNO_REG_SET (bb_live_regs
, i
);
5387 /* Regs live at the time of a call instruction must not
5388 go in a register clobbered by calls. Record this for
5389 all regs now live. Note that insns which are born or
5390 die in a call do not cross a call, so this must be done
5391 after the killings (above) and before the births
5393 p
= regs_sometimes_live
;
5394 for (i
= 0; i
< sometimes_max
; i
++, p
++)
5395 if (REGNO_REG_SET_P (bb_live_regs
, p
->regno
))
5396 p
->calls_crossed
+= 1;
5399 /* Make every register used live, and add REG_DEAD notes for
5400 registers which were not live before we started. */
5401 attach_deaths_insn (insn
);
5403 /* Find registers now made live by that instruction. */
5404 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs
, old_live_regs
, 0, j
,
5407 = new_sometimes_live (regs_sometimes_live
,
5410 IOR_REG_SET (old_live_regs
, bb_live_regs
);
5412 /* Count lengths of all regs we are worrying about now,
5413 and handle registers no longer live. */
5415 for (i
= 0; i
< sometimes_max
; i
++)
5417 register struct sometimes
*p
= ®s_sometimes_live
[i
];
5418 int regno
= p
->regno
;
5420 p
->live_length
+= 1;
5422 if (!REGNO_REG_SET_P (bb_live_regs
, regno
))
5424 /* This is the end of one of this register's lifetime
5425 segments. Save the lifetime info collected so far,
5426 and clear its bit in the old_live_regs entry. */
5427 sched_reg_live_length
[regno
] += p
->live_length
;
5428 sched_reg_n_calls_crossed
[regno
] += p
->calls_crossed
;
5429 CLEAR_REGNO_REG_SET (old_live_regs
, p
->regno
);
5431 /* Delete the reg_sometimes_live entry for this reg by
5432 copying the last entry over top of it. */
5433 *p
= regs_sometimes_live
[--sometimes_max
];
5434 /* ...and decrement i so that this newly copied entry
5435 will be processed. */
5441 finish_sometimes_live (regs_sometimes_live
, sometimes_max
);
5443 /* In interblock scheduling, basic_block_live_at_start may have changed. */
5444 if (current_nr_blocks
> 1)
5445 COPY_REG_SET (basic_block_live_at_start
[b
], bb_live_regs
);
5448 FREE_REG_SET (old_live_regs
);
5449 } /* find_post_sched_live */
5451 /* After scheduling the subroutine, restore information about uses of
5459 if (n_basic_blocks
> 0)
5460 for (regno
= FIRST_PSEUDO_REGISTER
; regno
< max_regno
; regno
++)
5461 if (REGNO_REG_SET_P (basic_block_live_at_start
[0], regno
))
5462 sched_reg_basic_block
[regno
] = REG_BLOCK_GLOBAL
;
5464 for (regno
= 0; regno
< max_regno
; regno
++)
5465 if (sched_reg_live_length
[regno
])
5469 if (REG_LIVE_LENGTH (regno
) > sched_reg_live_length
[regno
])
5471 ";; register %d life shortened from %d to %d\n",
5472 regno
, REG_LIVE_LENGTH (regno
),
5473 sched_reg_live_length
[regno
]);
5474 /* Negative values are special; don't overwrite the current
5475 reg_live_length value if it is negative. */
5476 else if (REG_LIVE_LENGTH (regno
) < sched_reg_live_length
[regno
]
5477 && REG_LIVE_LENGTH (regno
) >= 0)
5479 ";; register %d life extended from %d to %d\n",
5480 regno
, REG_LIVE_LENGTH (regno
),
5481 sched_reg_live_length
[regno
]);
5483 if (!REG_N_CALLS_CROSSED (regno
)
5484 && sched_reg_n_calls_crossed
[regno
])
5486 ";; register %d now crosses calls\n", regno
);
5487 else if (REG_N_CALLS_CROSSED (regno
)
5488 && !sched_reg_n_calls_crossed
[regno
]
5489 && REG_BASIC_BLOCK (regno
) != REG_BLOCK_GLOBAL
)
5491 ";; register %d no longer crosses calls\n", regno
);
5493 if (REG_BASIC_BLOCK (regno
) != sched_reg_basic_block
[regno
]
5494 && sched_reg_basic_block
[regno
] != REG_BLOCK_UNKNOWN
5495 && REG_BASIC_BLOCK(regno
) != REG_BLOCK_UNKNOWN
)
5497 ";; register %d changed basic block from %d to %d\n",
5498 regno
, REG_BASIC_BLOCK(regno
),
5499 sched_reg_basic_block
[regno
]);
5502 /* Negative values are special; don't overwrite the current
5503 reg_live_length value if it is negative. */
5504 if (REG_LIVE_LENGTH (regno
) >= 0)
5505 REG_LIVE_LENGTH (regno
) = sched_reg_live_length
[regno
];
5507 if (sched_reg_basic_block
[regno
] != REG_BLOCK_UNKNOWN
5508 && REG_BASIC_BLOCK(regno
) != REG_BLOCK_UNKNOWN
)
5509 REG_BASIC_BLOCK(regno
) = sched_reg_basic_block
[regno
];
5511 /* We can't change the value of reg_n_calls_crossed to zero for
5512 pseudos which are live in more than one block.
5514 This is because combine might have made an optimization which
5515 invalidated basic_block_live_at_start and reg_n_calls_crossed,
5516 but it does not update them. If we update reg_n_calls_crossed
5517 here, the two variables are now inconsistent, and this might
5518 confuse the caller-save code into saving a register that doesn't
5519 need to be saved. This is only a problem when we zero calls
5520 crossed for a pseudo live in multiple basic blocks.
5522 Alternatively, we could try to correctly update basic block live
5523 at start here in sched, but that seems complicated.
5525 Note: it is possible that a global register became local, as result
5526 of interblock motion, but will remain marked as a global register. */
5527 if (sched_reg_n_calls_crossed
[regno
]
5528 || REG_BASIC_BLOCK (regno
) != REG_BLOCK_GLOBAL
)
5529 REG_N_CALLS_CROSSED (regno
) = sched_reg_n_calls_crossed
[regno
];
5534 /* Scheduling clock, modified in schedule_block() and queue_to_ready () */
5535 static int clock_var
;
5537 /* Move insns that became ready to fire from queue to ready list. */
5540 queue_to_ready (ready
, n_ready
)
5547 q_ptr
= NEXT_Q (q_ptr
);
5549 /* Add all pending insns that can be scheduled without stalls to the
5551 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
5554 insn
= XEXP (link
, 0);
5557 if (sched_verbose
>= 2)
5558 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
5560 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
5561 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
5563 ready
[n_ready
++] = insn
;
5564 if (sched_verbose
>= 2)
5565 fprintf (dump
, "moving to ready without stalls\n");
5567 insn_queue
[q_ptr
] = 0;
5569 /* If there are no ready insns, stall until one is ready and add all
5570 of the pending insns at that point to the ready list. */
5573 register int stalls
;
5575 for (stalls
= 1; stalls
< INSN_QUEUE_SIZE
; stalls
++)
5577 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
5579 for (; link
; link
= XEXP (link
, 1))
5581 insn
= XEXP (link
, 0);
5584 if (sched_verbose
>= 2)
5585 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
5587 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
5588 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
5590 ready
[n_ready
++] = insn
;
5591 if (sched_verbose
>= 2)
5592 fprintf (dump
, "moving to ready with %d stalls\n", stalls
);
5594 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = 0;
5601 if (sched_verbose
&& stalls
)
5602 visualize_stall_cycles (BB_TO_BLOCK (target_bb
), stalls
);
5603 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
5604 clock_var
+= stalls
;
5609 /* Print the ready list for debugging purposes. Callable from debugger. */
5612 debug_ready_list (ready
, n_ready
)
5618 for (i
= 0; i
< n_ready
; i
++)
5620 fprintf (dump
, " %d", INSN_UID (ready
[i
]));
5621 if (current_nr_blocks
> 1 && INSN_BB (ready
[i
]) != target_bb
)
5622 fprintf (dump
, "/b%d", INSN_BLOCK (ready
[i
]));
5624 fprintf (dump
, "\n");
5627 /* Print names of units on which insn can/should execute, for debugging. */
5630 insn_print_units (insn
)
5634 int unit
= insn_unit (insn
);
5637 fprintf (dump
, "none");
5639 fprintf (dump
, "%s", function_units
[unit
].name
);
5642 fprintf (dump
, "[");
5643 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
5646 fprintf (dump
, "%s", function_units
[i
].name
);
5648 fprintf (dump
, " ");
5650 fprintf (dump
, "]");
5654 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5655 of a basic block. If more lines are needed, table is splitted to two.
5656 n_visual_lines is the number of lines printed so far for a block.
5657 visual_tbl contains the block visualization info.
5658 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5659 #define MAX_VISUAL_LINES 100
5664 rtx vis_no_unit
[10];
5666 /* Finds units that are in use in this fuction. Required only
5667 for visualization. */
5670 init_target_units ()
5675 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
5677 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5680 unit
= insn_unit (insn
);
5683 target_units
|= ~unit
;
5685 target_units
|= (1 << unit
);
5689 /* Return the length of the visualization table */
5692 get_visual_tbl_length ()
5698 /* compute length of one field in line */
5699 s
= (char *) alloca (INSN_LEN
+ 5);
5700 sprintf (s
, " %33s", "uname");
5703 /* compute length of one line */
5706 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5707 if (function_units
[unit
].bitmask
& target_units
)
5708 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5711 n
+= strlen ("\n") + 2;
5713 /* compute length of visualization string */
5714 return (MAX_VISUAL_LINES
* n
);
5717 /* Init block visualization debugging info */
5720 init_block_visualization ()
5722 strcpy (visual_tbl
, "");
5729 /* This recognizes rtx, I classified as expressions. These are always */
5730 /* represent some action on values or results of other expression, */
5731 /* that may be stored in objects representing values. */
5734 print_exp (buf
, x
, verbose
)
5739 char t1
[BUF_LEN
], t2
[BUF_LEN
], t3
[BUF_LEN
];
5741 switch (GET_CODE (x
))
5744 print_value (t1
, XEXP (x
, 0), verbose
);
5745 print_value (t2
, XEXP (x
, 1), verbose
);
5746 sprintf (buf
, "%s+%s", t1
, t2
);
5749 print_value (t1
, XEXP (x
, 0), verbose
);
5750 print_value (t2
, XEXP (x
, 1), verbose
);
5751 sprintf (buf
, "%sl+%s", t1
, t2
);
5754 print_value (t1
, XEXP (x
, 0), verbose
);
5755 print_value (t2
, XEXP (x
, 1), verbose
);
5756 sprintf (buf
, "%s-%s", t1
, t2
);
5759 print_value (t1
, XEXP (x
, 0), verbose
);
5760 print_value (t2
, XEXP (x
, 1), verbose
);
5761 sprintf (buf
, "%s??%s", t1
, t2
);
5764 print_value (t1
, XEXP (x
, 0), verbose
);
5765 sprintf (buf
, "-%s", t1
);
5768 print_value (t1
, XEXP (x
, 0), verbose
);
5769 print_value (t2
, XEXP (x
, 1), verbose
);
5770 sprintf (buf
, "%s*%s", t1
, t2
);
5773 print_value (t1
, XEXP (x
, 0), verbose
);
5774 print_value (t2
, XEXP (x
, 1), verbose
);
5775 sprintf (buf
, "%s/%s", t1
, t2
);
5778 print_value (t1
, XEXP (x
, 0), verbose
);
5779 print_value (t2
, XEXP (x
, 1), verbose
);
5780 sprintf (buf
, "%su/%s", t1
, t2
);
5783 print_value (t1
, XEXP (x
, 0), verbose
);
5784 print_value (t2
, XEXP (x
, 1), verbose
);
5785 sprintf (buf
, "%s%%%s", t1
, t2
);
5788 print_value (t1
, XEXP (x
, 0), verbose
);
5789 print_value (t2
, XEXP (x
, 1), verbose
);
5790 sprintf (buf
, "%su%%%s", t1
, t2
);
5793 print_value (t1
, XEXP (x
, 0), verbose
);
5794 print_value (t2
, XEXP (x
, 1), verbose
);
5795 sprintf (buf
, "smin (%s, %s)", t1
, t2
);
5798 print_value (t1
, XEXP (x
, 0), verbose
);
5799 print_value (t2
, XEXP (x
, 1), verbose
);
5800 sprintf (buf
, "smax(%s,%s)", t1
, t2
);
5803 print_value (t1
, XEXP (x
, 0), verbose
);
5804 print_value (t2
, XEXP (x
, 1), verbose
);
5805 sprintf (buf
, "umin (%s, %s)", t1
, t2
);
5808 print_value (t1
, XEXP (x
, 0), verbose
);
5809 print_value (t2
, XEXP (x
, 1), verbose
);
5810 sprintf (buf
, "umax(%s,%s)", t1
, t2
);
5813 print_value (t1
, XEXP (x
, 0), verbose
);
5814 sprintf (buf
, "!%s", t1
);
5817 print_value (t1
, XEXP (x
, 0), verbose
);
5818 print_value (t2
, XEXP (x
, 1), verbose
);
5819 sprintf (buf
, "%s&%s", t1
, t2
);
5822 print_value (t1
, XEXP (x
, 0), verbose
);
5823 print_value (t2
, XEXP (x
, 1), verbose
);
5824 sprintf (buf
, "%s|%s", t1
, t2
);
5827 print_value (t1
, XEXP (x
, 0), verbose
);
5828 print_value (t2
, XEXP (x
, 1), verbose
);
5829 sprintf (buf
, "%s^%s", t1
, t2
);
5832 print_value (t1
, XEXP (x
, 0), verbose
);
5833 print_value (t2
, XEXP (x
, 1), verbose
);
5834 sprintf (buf
, "%s<<%s", t1
, t2
);
5837 print_value (t1
, XEXP (x
, 0), verbose
);
5838 print_value (t2
, XEXP (x
, 1), verbose
);
5839 sprintf (buf
, "%s0>%s", t1
, t2
);
5842 print_value (t1
, XEXP (x
, 0), verbose
);
5843 print_value (t2
, XEXP (x
, 1), verbose
);
5844 sprintf (buf
, "%s>>%s", t1
, t2
);
5847 print_value (t1
, XEXP (x
, 0), verbose
);
5848 print_value (t2
, XEXP (x
, 1), verbose
);
5849 sprintf (buf
, "%s<-<%s", t1
, t2
);
5852 print_value (t1
, XEXP (x
, 0), verbose
);
5853 print_value (t2
, XEXP (x
, 1), verbose
);
5854 sprintf (buf
, "%s>->%s", t1
, t2
);
5857 print_value (t1
, XEXP (x
, 0), verbose
);
5858 sprintf (buf
, "abs(%s)", t1
);
5861 print_value (t1
, XEXP (x
, 0), verbose
);
5862 sprintf (buf
, "sqrt(%s)", t1
);
5865 print_value (t1
, XEXP (x
, 0), verbose
);
5866 sprintf (buf
, "ffs(%s)", t1
);
5869 print_value (t1
, XEXP (x
, 0), verbose
);
5870 print_value (t2
, XEXP (x
, 1), verbose
);
5871 sprintf (buf
, "%s == %s", t1
, t2
);
5874 print_value (t1
, XEXP (x
, 0), verbose
);
5875 print_value (t2
, XEXP (x
, 1), verbose
);
5876 sprintf (buf
, "%s!=%s", t1
, t2
);
5879 print_value (t1
, XEXP (x
, 0), verbose
);
5880 print_value (t2
, XEXP (x
, 1), verbose
);
5881 sprintf (buf
, "%s>%s", t1
, t2
);
5884 print_value (t1
, XEXP (x
, 0), verbose
);
5885 print_value (t2
, XEXP (x
, 1), verbose
);
5886 sprintf (buf
, "%s>u%s", t1
, t2
);
5889 print_value (t1
, XEXP (x
, 0), verbose
);
5890 print_value (t2
, XEXP (x
, 1), verbose
);
5891 sprintf (buf
, "%s<%s", t1
, t2
);
5894 print_value (t1
, XEXP (x
, 0), verbose
);
5895 print_value (t2
, XEXP (x
, 1), verbose
);
5896 sprintf (buf
, "%s<u%s", t1
, t2
);
5899 print_value (t1
, XEXP (x
, 0), verbose
);
5900 print_value (t2
, XEXP (x
, 1), verbose
);
5901 sprintf (buf
, "%s>=%s", t1
, t2
);
5904 print_value (t1
, XEXP (x
, 0), verbose
);
5905 print_value (t2
, XEXP (x
, 1), verbose
);
5906 sprintf (buf
, "%s>=u%s", t1
, t2
);
5909 print_value (t1
, XEXP (x
, 0), verbose
);
5910 print_value (t2
, XEXP (x
, 1), verbose
);
5911 sprintf (buf
, "%s<=%s", t1
, t2
);
5914 print_value (t1
, XEXP (x
, 0), verbose
);
5915 print_value (t2
, XEXP (x
, 1), verbose
);
5916 sprintf (buf
, "%s<=u%s", t1
, t2
);
5919 print_value (t1
, XEXP (x
, 0), verbose
);
5920 print_value (t2
, XEXP (x
, 1), verbose
);
5921 print_value (t3
, XEXP (x
, 2), verbose
);
5923 sprintf (buf
, "sign_extract(%s,%s,%s)", t1
, t2
, t3
);
5925 sprintf (buf
, "sxt(%s,%s,%s)", t1
, t2
, t3
);
5928 print_value (t1
, XEXP (x
, 0), verbose
);
5929 print_value (t2
, XEXP (x
, 1), verbose
);
5930 print_value (t3
, XEXP (x
, 2), verbose
);
5932 sprintf (buf
, "zero_extract(%s,%s,%s)", t1
, t2
, t3
);
5934 sprintf (buf
, "zxt(%s,%s,%s)", t1
, t2
, t3
);
5937 print_value (t1
, XEXP (x
, 0), verbose
);
5939 sprintf (buf
, "sign_extend(%s)", t1
);
5941 sprintf (buf
, "sxn(%s)", t1
);
5944 print_value (t1
, XEXP (x
, 0), verbose
);
5946 sprintf (buf
, "zero_extend(%s)", t1
);
5948 sprintf (buf
, "zxn(%s)", t1
);
5951 print_value (t1
, XEXP (x
, 0), verbose
);
5953 sprintf (buf
, "float_extend(%s)", t1
);
5955 sprintf (buf
, "fxn(%s)", t1
);
5958 print_value (t1
, XEXP (x
, 0), verbose
);
5960 sprintf (buf
, "trunc(%s)", t1
);
5962 sprintf (buf
, "trn(%s)", t1
);
5964 case FLOAT_TRUNCATE
:
5965 print_value (t1
, XEXP (x
, 0), verbose
);
5967 sprintf (buf
, "float_trunc(%s)", t1
);
5969 sprintf (buf
, "ftr(%s)", t1
);
5972 print_value (t1
, XEXP (x
, 0), verbose
);
5974 sprintf (buf
, "float(%s)", t1
);
5976 sprintf (buf
, "flt(%s)", t1
);
5978 case UNSIGNED_FLOAT
:
5979 print_value (t1
, XEXP (x
, 0), verbose
);
5981 sprintf (buf
, "uns_float(%s)", t1
);
5983 sprintf (buf
, "ufl(%s)", t1
);
5986 print_value (t1
, XEXP (x
, 0), verbose
);
5987 sprintf (buf
, "fix(%s)", t1
);
5990 print_value (t1
, XEXP (x
, 0), verbose
);
5992 sprintf (buf
, "uns_fix(%s)", t1
);
5994 sprintf (buf
, "ufx(%s)", t1
);
5997 print_value (t1
, XEXP (x
, 0), verbose
);
5998 sprintf (buf
, "--%s", t1
);
6001 print_value (t1
, XEXP (x
, 0), verbose
);
6002 sprintf (buf
, "++%s", t1
);
6005 print_value (t1
, XEXP (x
, 0), verbose
);
6006 sprintf (buf
, "%s--", t1
);
6009 print_value (t1
, XEXP (x
, 0), verbose
);
6010 sprintf (buf
, "%s++", t1
);
6013 print_value (t1
, XEXP (x
, 0), verbose
);
6016 print_value (t2
, XEXP (x
, 1), verbose
);
6017 sprintf (buf
, "call %s argc:%s", t1
, t2
);
6020 sprintf (buf
, "call %s", t1
);
6023 print_exp (t1
, XEXP (x
, 0), verbose
);
6024 print_value (t2
, XEXP (x
, 1), verbose
);
6025 print_value (t3
, XEXP (x
, 2), verbose
);
6026 sprintf (buf
, "{(%s)?%s:%s}", t1
, t2
, t3
);
6029 print_value (t1
, TRAP_CONDITION (x
), verbose
);
6030 sprintf (buf
, "trap_if %s", t1
);
6036 sprintf (t1
, "unspec{");
6037 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6039 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6040 sprintf (t3
, "%s%s;", t1
, t2
);
6043 sprintf (buf
, "%s}", t1
);
6046 case UNSPEC_VOLATILE
:
6050 sprintf (t1
, "unspec/v{");
6051 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6053 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6054 sprintf (t3
, "%s%s;", t1
, t2
);
6057 sprintf (buf
, "%s}", t1
);
6061 /* if (verbose) debug_rtx (x); else sprintf (buf, "$$$"); */
6062 sprintf (buf
, "$$$");
6066 /* Prints rtxes, i customly classified as values. They're constants, */
6067 /* registers, labels, symbols and memory accesses. */
6070 print_value (buf
, x
, verbose
)
6077 switch (GET_CODE (x
))
6080 sprintf (buf
, "%Xh", INTVAL (x
));
6083 print_value (t
, XEXP (x
, 0), verbose
);
6084 sprintf (buf
, "<%s>", t
);
6087 sprintf (buf
, "\"%s\"", (char *) XEXP (x
, 0));
6090 sprintf (buf
, "`%s'", (char *) XEXP (x
, 0));
6093 sprintf (buf
, "L%d", INSN_UID (XEXP (x
, 0)));
6096 print_value (buf
, XEXP (x
, 0), verbose
);
6099 print_value (buf
, XEXP (x
, 0), verbose
);
6102 if (GET_MODE (x
) == SFmode
6103 || GET_MODE (x
) == DFmode
6104 || GET_MODE (x
) == XFmode
6105 || GET_MODE (x
) == TFmode
)
6109 sprintf (buf
, "%s%d", t
, REGNO (x
));
6112 print_value (t
, XEXP (x
, 0), verbose
);
6113 sprintf (buf
, "%s#%d", t
, SUBREG_WORD (x
));
6116 sprintf (buf
, "scratch");
6119 sprintf (buf
, "cc0");
6122 sprintf (buf
, "pc");
6125 print_value (t
, XEXP (x
, 0), verbose
);
6126 sprintf (buf
, "[%s]", t
);
6129 print_exp (buf
, x
, verbose
);
6133 /* The next step in insn detalization, its pattern recognition */
6136 print_pattern (buf
, x
, verbose
)
6141 char t1
[BUF_LEN
], t2
[BUF_LEN
], t3
[BUF_LEN
];
6143 switch (GET_CODE (x
))
6146 print_value (t1
, SET_DEST (x
), verbose
);
6147 print_value (t2
, SET_SRC (x
), verbose
);
6148 sprintf (buf
, "%s=%s", t1
, t2
);
6151 sprintf (buf
, "return");
6154 print_exp (buf
, x
, verbose
);
6157 print_value (t1
, XEXP (x
, 0), verbose
);
6158 sprintf (buf
, "clobber %s", t1
);
6161 print_value (t1
, XEXP (x
, 0), verbose
);
6162 sprintf (buf
, "use %s", t1
);
6169 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6171 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6172 sprintf (t3
, "%s%s;", t1
, t2
);
6175 sprintf (buf
, "%s}", t1
);
6182 sprintf (t1
, "%%{");
6183 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6185 print_insn (t2
, XVECEXP (x
, 0, i
), verbose
);
6186 sprintf (t3
, "%s%s;", t1
, t2
);
6189 sprintf (buf
, "%s%%}", t1
);
6193 sprintf (buf
, "asm {%s}", XEXP (x
, 0));
6198 print_value (buf
, XEXP (x
, 0), verbose
);
6201 print_value (t1
, TRAP_CONDITION (x
), verbose
);
6202 sprintf (buf
, "trap_if %s", t1
);
6208 sprintf (t1
, "unspec{");
6209 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6211 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6212 sprintf (t3
, "%s%s;", t1
, t2
);
6215 sprintf (buf
, "%s}", t1
);
6218 case UNSPEC_VOLATILE
:
6222 sprintf (t1
, "unspec/v{");
6223 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6225 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6226 sprintf (t3
, "%s%s;", t1
, t2
);
6229 sprintf (buf
, "%s}", t1
);
6233 print_value (buf
, x
, verbose
);
6235 } /* print_pattern */
6237 /* This is the main function in rtl visualization mechanism. It
6238 accepts an rtx and tries to recognize it as an insn, then prints it
6239 properly in human readable form, resembling assembler mnemonics. */
6240 /* For every insn it prints its UID and BB the insn belongs */
6241 /* too. (probably the last "option" should be extended somehow, since */
6242 /* it depends now on sched.c inner variables ...) */
6245 print_insn (buf
, x
, verbose
)
6253 switch (GET_CODE (x
))
6256 print_pattern (t
, PATTERN (x
), verbose
);
6258 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (x
),
6261 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
6264 print_pattern (t
, PATTERN (x
), verbose
);
6266 sprintf (buf
, "b%d: i% 4d: jump %s", INSN_BB (x
),
6269 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
6273 if (GET_CODE (x
) == PARALLEL
)
6275 x
= XVECEXP (x
, 0, 0);
6276 print_pattern (t
, x
, verbose
);
6279 strcpy (t
, "call <...>");
6281 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (insn
),
6282 INSN_UID (insn
), t
);
6284 sprintf (buf
, "%-4d %s", INSN_UID (insn
), t
);
6287 sprintf (buf
, "L%d:", INSN_UID (x
));
6290 sprintf (buf
, "i% 4d: barrier", INSN_UID (x
));
6293 if (NOTE_LINE_NUMBER (x
) > 0)
6294 sprintf (buf
, "%4d note \"%s\" %d", INSN_UID (x
),
6295 NOTE_SOURCE_FILE (x
), NOTE_LINE_NUMBER (x
));
6297 sprintf (buf
, "%4d %s", INSN_UID (x
),
6298 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x
)));
6303 sprintf (buf
, "Not an INSN at all\n");
6307 sprintf (buf
, "i%-4d <What?>", INSN_UID (x
));
6312 print_insn_chain (rtx_first
)
6315 register rtx tmp_rtx
;
6318 strcpy (str
, "(nil)\n");
6320 switch (GET_CODE (rtx_first
))
6328 for (tmp_rtx
= rtx_first
; tmp_rtx
!= NULL
;
6329 tmp_rtx
= NEXT_INSN (tmp_rtx
))
6331 print_insn (str
, tmp_rtx
, 0);
6332 printf ("%s\n", str
);
6336 print_insn (str
, rtx_first
, 0);
6337 printf ("%s\n", str
);
6339 } /* print_insn_chain */
6341 /* Print visualization debugging info */
6344 print_block_visualization (b
, s
)
6351 fprintf (dump
, "\n;; ==================== scheduling visualization for block %d %s \n", b
, s
);
6353 /* Print names of units */
6354 fprintf (dump
, ";; %-8s", "clock");
6355 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6356 if (function_units
[unit
].bitmask
& target_units
)
6357 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6358 fprintf (dump
, " %-33s", function_units
[unit
].name
);
6359 fprintf (dump
, " %-8s\n", "no-unit");
6361 fprintf (dump
, ";; %-8s", "=====");
6362 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6363 if (function_units
[unit
].bitmask
& target_units
)
6364 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6365 fprintf (dump
, " %-33s", "==============================");
6366 fprintf (dump
, " %-8s\n", "=======");
6368 /* Print insns in each cycle */
6369 fprintf (dump
, "%s\n", visual_tbl
);
6372 /* Print insns in the 'no_unit' column of visualization */
6375 visualize_no_unit (insn
)
6378 vis_no_unit
[n_vis_no_unit
] = insn
;
6382 /* Print insns scheduled in clock, for visualization. */
6385 visualize_scheduled_insns (b
, clock
)
6390 /* if no more room, split table into two */
6391 if (n_visual_lines
>= MAX_VISUAL_LINES
)
6393 print_block_visualization (b
, "(incomplete)");
6394 init_block_visualization ();
6399 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; %-8d", clock
);
6400 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6401 if (function_units
[unit
].bitmask
& target_units
)
6402 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6404 int instance
= unit
+ i
* FUNCTION_UNITS_SIZE
;
6405 rtx insn
= unit_last_insn
[instance
];
6407 /* print insns that still keep the unit busy */
6409 actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
6412 print_insn (str
, insn
, 0);
6413 str
[INSN_LEN
] = '\0';
6414 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", str
);
6417 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", "------------------------------");
6420 /* print insns that are not assigned to any unit */
6421 for (i
= 0; i
< n_vis_no_unit
; i
++)
6422 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-8d",
6423 INSN_UID (vis_no_unit
[i
]));
6426 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
6429 /* Print stalled cycles */
6432 visualize_stall_cycles (b
, stalls
)
6437 /* if no more room, split table into two */
6438 if (n_visual_lines
>= MAX_VISUAL_LINES
)
6440 print_block_visualization (b
, "(incomplete)");
6441 init_block_visualization ();
6446 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; ");
6447 for (i
= 0; i
< stalls
; i
++)
6448 sprintf (visual_tbl
+ strlen (visual_tbl
), ".");
6449 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
6452 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn */
6455 move_insn1 (insn
, last
)
6458 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
6459 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
6461 NEXT_INSN (insn
) = NEXT_INSN (last
);
6462 PREV_INSN (NEXT_INSN (last
)) = insn
;
6464 NEXT_INSN (last
) = insn
;
6465 PREV_INSN (insn
) = last
;
6470 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
6471 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
6472 NOTEs. The REG_DEAD note following first one is contains the saved
6473 value for NOTE_BLOCK_NUMBER which is useful for
6474 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
6475 output by the instruction scheduler. Return the new value of LAST. */
6478 reemit_notes (insn
, last
)
6485 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
6487 if (REG_NOTE_KIND (note
) == REG_DEAD
6488 && GET_CODE (XEXP (note
, 0)) == CONST_INT
)
6490 if (INTVAL (XEXP (note
, 0)) == NOTE_INSN_SETJMP
)
6492 retval
= emit_note_after (INTVAL (XEXP (note
, 0)), insn
);
6493 CONST_CALL_P (retval
) = CONST_CALL_P (note
);
6494 remove_note (insn
, note
);
6495 note
= XEXP (note
, 1);
6499 last
= emit_note_before (INTVAL (XEXP (note
, 0)), last
);
6500 remove_note (insn
, note
);
6501 note
= XEXP (note
, 1);
6502 NOTE_BLOCK_NUMBER (last
) = INTVAL (XEXP (note
, 0));
6504 remove_note (insn
, note
);
6510 /* Move INSN, and all insns which should be issued before it,
6511 due to SCHED_GROUP_P flag. Reemit notes if needed.
6513 Return the last insn emitted by the scheduler, which is the
6514 return value from the first call to reemit_notes. */
6517 move_insn (insn
, last
)
6522 /* If INSN has SCHED_GROUP_P set, then issue it and any other
6523 insns with SCHED_GROUP_P set first. */
6524 while (SCHED_GROUP_P (insn
))
6526 rtx prev
= PREV_INSN (insn
);
6528 /* Move a SCHED_GROUP_P insn. */
6529 move_insn1 (insn
, last
);
6530 /* If this is the first call to reemit_notes, then record
6531 its return value. */
6532 if (retval
== NULL_RTX
)
6533 retval
= reemit_notes (insn
, insn
);
6535 reemit_notes (insn
, insn
);
6539 /* Now move the first non SCHED_GROUP_P insn. */
6540 move_insn1 (insn
, last
);
6542 /* If this is the first call to reemit_notes, then record
6543 its return value. */
6544 if (retval
== NULL_RTX
)
6545 retval
= reemit_notes (insn
, insn
);
6547 reemit_notes (insn
, insn
);
6552 /* Return an insn which represents a SCHED_GROUP, which is
6553 the last insn in the group. */
6564 insn
= next_nonnote_insn (insn
);
6566 while (insn
&& SCHED_GROUP_P (insn
) && (GET_CODE (insn
) != CODE_LABEL
));
6571 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
6572 possibly bringing insns from subsequent blocks in the same region.
6573 Return number of insns scheduled. */
6576 schedule_block (bb
, rgn_n_insns
)
6580 /* Local variables. */
6587 /* flow block of this bb */
6588 int b
= BB_TO_BLOCK (bb
);
6590 /* target_n_insns == number of insns in b before scheduling starts.
6591 sched_target_n_insns == how many of b's insns were scheduled.
6592 sched_n_insns == how many insns were scheduled in b */
6593 int target_n_insns
= 0;
6594 int sched_target_n_insns
= 0;
6595 int sched_n_insns
= 0;
6597 #define NEED_NOTHING 0
6602 /* head/tail info for this block */
6609 /* We used to have code to avoid getting parameters moved from hard
6610 argument registers into pseudos.
6612 However, it was removed when it proved to be of marginal benefit
6613 and caused problems because schedule_block and compute_forward_dependences
6614 had different notions of what the "head" insn was. */
6615 get_block_head_tail (bb
, &head
, &tail
);
6617 /* Interblock scheduling could have moved the original head insn from this
6618 block into a proceeding block. This may also cause schedule_block and
6619 compute_forward_dependences to have different notions of what the
6622 If the interblock movement happened to make this block start with
6623 some notes (LOOP, EH or SETJMP) before the first real insn, then
6624 HEAD will have various special notes attached to it which must be
6625 removed so that we don't end up with extra copies of the notes. */
6626 if (GET_RTX_CLASS (GET_CODE (head
)) == 'i')
6630 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
6631 if (REG_NOTE_KIND (note
) == REG_DEAD
6632 && GET_CODE (XEXP (note
, 0)) == CONST_INT
)
6633 remove_note (head
, note
);
6636 next_tail
= NEXT_INSN (tail
);
6637 prev_head
= PREV_INSN (head
);
6639 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6640 to schedule this block. */
6642 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6643 return (sched_n_insns
);
6648 fprintf (dump
, ";; ======================================================\n");
6650 ";; -- basic block %d from %d to %d -- %s reload\n",
6651 b
, INSN_UID (basic_block_head
[b
]),
6652 INSN_UID (basic_block_end
[b
]),
6653 (reload_completed
? "after" : "before"));
6654 fprintf (dump
, ";; ======================================================\n");
6655 if (sched_debug_count
>= 0)
6656 fprintf (dump
, ";;\t -- sched_debug_count=%d\n", sched_debug_count
);
6657 fprintf (dump
, "\n");
6659 visual_tbl
= (char *) alloca (get_visual_tbl_length ());
6660 init_block_visualization ();
6663 /* remove remaining note insns from the block, save them in
6664 note_list. These notes are restored at the end of
6665 schedule_block (). */
6667 rm_other_notes (head
, tail
);
6671 /* prepare current target block info */
6672 if (current_nr_blocks
> 1)
6674 candidate_table
= (candidate
*) alloca (current_nr_blocks
* sizeof (candidate
));
6677 /* ??? It is not clear why bblst_size is computed this way. The original
6678 number was clearly too small as it resulted in compiler failures.
6679 Multiplying by the original number by 2 (to account for update_bbs
6680 members) seems to be a reasonable solution. */
6681 /* ??? Or perhaps there is a bug somewhere else in this file? */
6682 bblst_size
= (current_nr_blocks
- bb
) * rgn_nr_edges
* 2;
6683 bblst_table
= (int *) alloca (bblst_size
* sizeof (int));
6685 bitlst_table_last
= 0;
6686 bitlst_table_size
= rgn_nr_edges
;
6687 bitlst_table
= (int *) alloca (rgn_nr_edges
* sizeof (int));
6689 compute_trg_info (bb
);
6694 /* Allocate the ready list */
6695 ready
= (rtx
*) alloca ((rgn_n_insns
+ 1) * sizeof (rtx
));
6697 /* Print debugging information. */
6698 if (sched_verbose
>= 5)
6699 debug_dependencies ();
6702 /* Initialize ready list with all 'ready' insns in target block.
6703 Count number of insns in the target block being scheduled. */
6705 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
6709 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6711 next
= NEXT_INSN (insn
);
6713 if (INSN_DEP_COUNT (insn
) == 0
6714 && (SCHED_GROUP_P (next
) == 0 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
6715 ready
[n_ready
++] = insn
;
6716 if (!(SCHED_GROUP_P (insn
)))
6720 /* Add to ready list all 'ready' insns in valid source blocks.
6721 For speculative insns, check-live, exception-free, and
6723 for (bb_src
= bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
6724 if (IS_VALID (bb_src
))
6730 get_block_head_tail (bb_src
, &head
, &tail
);
6731 src_next_tail
= NEXT_INSN (tail
);
6735 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6738 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
6740 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6743 if (!CANT_MOVE (insn
)
6744 && (!IS_SPECULATIVE_INSN (insn
)
6745 || (insn_issue_delay (insn
) <= 3
6746 && check_live (insn
, bb_src
)
6747 && is_exception_free (insn
, bb_src
, target_bb
))))
6752 next
= NEXT_INSN (insn
);
6753 if (INSN_DEP_COUNT (insn
) == 0
6754 && (SCHED_GROUP_P (next
) == 0
6755 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
6756 ready
[n_ready
++] = insn
;
6761 /* no insns scheduled in this block yet */
6762 last_scheduled_insn
= 0;
6764 /* Sort the ready list */
6765 SCHED_SORT (ready
, n_ready
);
6767 if (sched_verbose
>= 2)
6769 fprintf (dump
, ";;\t\tReady list initially: ");
6770 debug_ready_list (ready
, n_ready
);
6773 /* Q_SIZE is the total number of insns in the queue. */
6777 bzero ((char *) insn_queue
, sizeof (insn_queue
));
6779 /* We start inserting insns after PREV_HEAD. */
6782 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6783 new_needs
= (NEXT_INSN (prev_head
) == basic_block_head
[b
]
6784 ? NEED_HEAD
: NEED_NOTHING
);
6785 if (PREV_INSN (next_tail
) == basic_block_end
[b
])
6786 new_needs
|= NEED_TAIL
;
6788 /* loop until all the insns in BB are scheduled. */
6789 while (sched_target_n_insns
< target_n_insns
)
6793 #ifdef INTERBLOCK_DEBUG
6794 if (sched_debug_count
== 0)
6799 /* Add to the ready list all pending insns that can be issued now.
6800 If there are no ready insns, increment clock until one
6801 is ready and add all pending insns at that point to the ready
6803 n_ready
= queue_to_ready (ready
, n_ready
);
6808 if (sched_verbose
>= 2)
6810 fprintf (dump
, ";;\t\tReady list after queue_to_ready: ");
6811 debug_ready_list (ready
, n_ready
);
6814 /* Sort the ready list. */
6815 SCHED_SORT (ready
, n_ready
);
6819 fprintf (dump
, ";;\tReady list (t =%3d): ", clock_var
);
6820 debug_ready_list (ready
, n_ready
);
6823 /* Issue insns from ready list.
6824 It is important to count down from n_ready, because n_ready may change
6825 as insns are issued. */
6826 can_issue_more
= issue_rate
;
6827 for (i
= n_ready
- 1; i
>= 0 && can_issue_more
; i
--)
6829 rtx insn
= ready
[i
];
6830 int cost
= actual_hazard (insn_unit (insn
), insn
, clock_var
, 0);
6834 queue_insn (insn
, cost
);
6835 ready
[i
] = ready
[--n_ready
]; /* remove insn from ready list */
6839 #ifdef INTERBLOCK_DEBUG
6840 if (sched_debug_count
== 0)
6844 /* an interblock motion? */
6845 if (INSN_BB (insn
) != target_bb
)
6849 if (IS_SPECULATIVE_INSN (insn
))
6852 if (!check_live (insn
, INSN_BB (insn
)))
6854 /* speculative motion, live check failed, remove
6855 insn from ready list */
6856 ready
[i
] = ready
[--n_ready
];
6859 update_live (insn
, INSN_BB (insn
));
6861 /* for speculative load, mark insns fed by it. */
6862 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
6863 set_spec_fed (insn
);
6870 while (SCHED_GROUP_P (temp
))
6871 temp
= PREV_INSN (temp
);
6873 /* Update source block boundaries. */
6874 b1
= INSN_BLOCK (temp
);
6875 if (temp
== basic_block_head
[b1
]
6876 && insn
== basic_block_end
[b1
])
6878 /* We moved all the insns in the basic block.
6879 Emit a note after the last insn and update the
6880 begin/end boundaries to point to the note. */
6881 emit_note_after (NOTE_INSN_DELETED
, insn
);
6882 basic_block_end
[b1
] = NEXT_INSN (insn
);
6883 basic_block_head
[b1
] = NEXT_INSN (insn
);
6885 else if (insn
== basic_block_end
[b1
])
6887 /* We took insns from the end of the basic block,
6888 so update the end of block boundary so that it
6889 points to the first insn we did not move. */
6890 basic_block_end
[b1
] = PREV_INSN (temp
);
6892 else if (temp
== basic_block_head
[b1
])
6894 /* We took insns from the start of the basic block,
6895 so update the start of block boundary so that
6896 it points to the first insn we did not move. */
6897 basic_block_head
[b1
] = NEXT_INSN (insn
);
6902 /* in block motion */
6903 sched_target_n_insns
++;
6906 last_scheduled_insn
= insn
;
6907 last
= move_insn (insn
, last
);
6912 #ifdef INTERBLOCK_DEBUG
6913 if (sched_debug_count
> 0)
6914 sched_debug_count
--;
6917 n_ready
= schedule_insn (insn
, ready
, n_ready
, clock_var
);
6919 /* remove insn from ready list */
6920 ready
[i
] = ready
[--n_ready
];
6922 /* close this block after scheduling its jump */
6923 if (GET_CODE (last_scheduled_insn
) == JUMP_INSN
)
6931 visualize_scheduled_insns (b
, clock_var
);
6932 #ifdef INTERBLOCK_DEBUG
6933 if (sched_debug_count
== 0)
6934 fprintf (dump
, "........ sched_debug_count == 0 .................\n");
6942 fprintf (dump
, ";;\tReady list (final): ");
6943 debug_ready_list (ready
, n_ready
);
6944 print_block_visualization (b
, "");
6947 /* Sanity check -- queue must be empty now. Meaningless if region has
6948 multiple bbs, or if scheduling stopped by sched_debug_count. */
6949 if (current_nr_blocks
> 1)
6950 #ifdef INTERBLOCK_DEBUG
6951 if (sched_debug_count
!= 0)
6953 if (!flag_schedule_interblock
&& q_size
!= 0)
6956 /* update head/tail boundaries. */
6957 head
= NEXT_INSN (prev_head
);
6960 #ifdef INTERBLOCK_DEBUG
6961 if (sched_debug_count
== 0)
6962 /* compensate for stopping scheduling prematurely */
6963 for (i
= sched_target_n_insns
; i
< target_n_insns
; i
++)
6964 tail
= move_insn (group_leader (NEXT_INSN (tail
)), tail
);
6967 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6968 previously found among the insns. Insert them at the beginning
6972 rtx note_head
= note_list
;
6974 while (PREV_INSN (note_head
))
6976 note_head
= PREV_INSN (note_head
);
6979 PREV_INSN (note_head
) = PREV_INSN (head
);
6980 NEXT_INSN (PREV_INSN (head
)) = note_head
;
6981 PREV_INSN (head
) = note_list
;
6982 NEXT_INSN (note_list
) = head
;
6986 /* update target block boundaries. */
6987 if (new_needs
& NEED_HEAD
)
6988 basic_block_head
[b
] = head
;
6990 if (new_needs
& NEED_TAIL
)
6991 basic_block_end
[b
] = tail
;
6996 fprintf (dump
, ";; total time = %d\n;; new basic block head = %d\n",
6997 clock_var
, INSN_UID (basic_block_head
[b
]));
6998 fprintf (dump
, ";; new basic block end = %d\n\n",
6999 INSN_UID (basic_block_end
[b
]));
7002 return (sched_n_insns
);
7003 } /* schedule_block () */
7006 /* print the bit-set of registers, S. callable from debugger */
7009 debug_reg_vector (s
)
7014 EXECUTE_IF_SET_IN_REG_SET (s
, 0, regno
,
7016 fprintf (dump
, " %d", regno
);
7019 fprintf (dump
, "\n");
7022 /* Use the backward dependences from LOG_LINKS to build
7023 forward dependences in INSN_DEPEND. */
7026 compute_block_forward_dependences (bb
)
7032 enum reg_note dep_type
;
7034 get_block_head_tail (bb
, &head
, &tail
);
7035 next_tail
= NEXT_INSN (tail
);
7036 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
7038 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
7041 insn
= group_leader (insn
);
7043 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
7045 rtx x
= group_leader (XEXP (link
, 0));
7048 if (x
!= XEXP (link
, 0))
7051 /* Ignore dependences upon deleted insn */
7052 if (GET_CODE (x
) == NOTE
|| INSN_DELETED_P (x
))
7054 if (find_insn_list (insn
, INSN_DEPEND (x
)))
7057 new_link
= rtx_alloc (INSN_LIST
);
7059 dep_type
= REG_NOTE_KIND (link
);
7060 PUT_REG_NOTE_KIND (new_link
, dep_type
);
7062 XEXP (new_link
, 0) = insn
;
7063 XEXP (new_link
, 1) = INSN_DEPEND (x
);
7065 INSN_DEPEND (x
) = new_link
;
7066 INSN_DEP_COUNT (insn
) += 1;
7071 /* Initialize variables for region data dependence analysis.
7072 n_bbs is the number of region blocks */
7074 __inline
static void
7075 init_rgn_data_dependences (n_bbs
)
7080 /* variables for which one copy exists for each block */
7081 bzero ((char *) bb_pending_read_insns
, n_bbs
* sizeof (rtx
));
7082 bzero ((char *) bb_pending_read_mems
, n_bbs
* sizeof (rtx
));
7083 bzero ((char *) bb_pending_write_insns
, n_bbs
* sizeof (rtx
));
7084 bzero ((char *) bb_pending_write_mems
, n_bbs
* sizeof (rtx
));
7085 bzero ((char *) bb_pending_lists_length
, n_bbs
* sizeof (rtx
));
7086 bzero ((char *) bb_last_pending_memory_flush
, n_bbs
* sizeof (rtx
));
7087 bzero ((char *) bb_last_function_call
, n_bbs
* sizeof (rtx
));
7088 bzero ((char *) bb_sched_before_next_call
, n_bbs
* sizeof (rtx
));
7090 /* Create an insn here so that we can hang dependencies off of it later. */
7091 for (bb
= 0; bb
< n_bbs
; bb
++)
7093 bb_sched_before_next_call
[bb
] =
7094 gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
7095 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
7096 LOG_LINKS (bb_sched_before_next_call
[bb
]) = 0;
7100 /* Add dependences so that branches are scheduled to run last in their block */
7103 add_branch_dependences (head
, tail
)
7109 /* For all branches, calls, uses, and cc0 setters, force them to remain
7110 in order at the end of the block by adding dependencies and giving
7111 the last a high priority. There may be notes present, and prev_head
7114 Branches must obviously remain at the end. Calls should remain at the
7115 end since moving them results in worse register allocation. Uses remain
7116 at the end to ensure proper register allocation. cc0 setters remaim
7117 at the end because they can't be moved away from their cc0 user. */
7120 while (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
7121 || (GET_CODE (insn
) == INSN
7122 && (GET_CODE (PATTERN (insn
)) == USE
7124 || sets_cc0_p (PATTERN (insn
))
7127 || GET_CODE (insn
) == NOTE
)
7129 if (GET_CODE (insn
) != NOTE
)
7132 && !find_insn_list (insn
, LOG_LINKS (last
)))
7134 add_dependence (last
, insn
, REG_DEP_ANTI
);
7135 INSN_REF_COUNT (insn
)++;
7138 CANT_MOVE (insn
) = 1;
7141 /* Skip over insns that are part of a group.
7142 Make each insn explicitly depend on the previous insn.
7143 This ensures that only the group header will ever enter
7144 the ready queue (and, when scheduled, will automatically
7145 schedule the SCHED_GROUP_P block). */
7146 while (SCHED_GROUP_P (insn
))
7148 rtx temp
= prev_nonnote_insn (insn
);
7149 add_dependence (insn
, temp
, REG_DEP_ANTI
);
7154 /* Don't overrun the bounds of the basic block. */
7158 insn
= PREV_INSN (insn
);
7161 /* make sure these insns are scheduled last in their block */
7164 while (insn
!= head
)
7166 insn
= prev_nonnote_insn (insn
);
7168 if (INSN_REF_COUNT (insn
) != 0)
7171 if (!find_insn_list (last
, LOG_LINKS (insn
)))
7172 add_dependence (last
, insn
, REG_DEP_ANTI
);
7173 INSN_REF_COUNT (insn
) = 1;
7175 /* Skip over insns that are part of a group. */
7176 while (SCHED_GROUP_P (insn
))
7177 insn
= prev_nonnote_insn (insn
);
7181 /* Compute bacward dependences inside BB. In a multiple blocks region:
7182 (1) a bb is analyzed after its predecessors, and (2) the lists in
7183 effect at the end of bb (after analyzing for bb) are inherited by
7186 Specifically for reg-reg data dependences, the block insns are
7187 scanned by sched_analyze () top-to-bottom. Two lists are
7188 naintained by sched_analyze (): reg_last_defs[] for register DEFs,
7189 and reg_last_uses[] for register USEs.
7191 When analysis is completed for bb, we update for its successors:
7192 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7193 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7195 The mechanism for computing mem-mem data dependence is very
7196 similar, and the result is interblock dependences in the region. */
7199 compute_block_backward_dependences (bb
)
7205 int max_reg
= max_reg_num ();
7207 b
= BB_TO_BLOCK (bb
);
7209 if (current_nr_blocks
== 1)
7211 reg_last_uses
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7212 reg_last_sets
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7214 bzero ((char *) reg_last_uses
, max_reg
* sizeof (rtx
));
7215 bzero ((char *) reg_last_sets
, max_reg
* sizeof (rtx
));
7217 pending_read_insns
= 0;
7218 pending_read_mems
= 0;
7219 pending_write_insns
= 0;
7220 pending_write_mems
= 0;
7221 pending_lists_length
= 0;
7222 last_function_call
= 0;
7223 last_pending_memory_flush
= 0;
7224 sched_before_next_call
7225 = gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
7226 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
7227 LOG_LINKS (sched_before_next_call
) = 0;
7231 reg_last_uses
= bb_reg_last_uses
[bb
];
7232 reg_last_sets
= bb_reg_last_sets
[bb
];
7234 pending_read_insns
= bb_pending_read_insns
[bb
];
7235 pending_read_mems
= bb_pending_read_mems
[bb
];
7236 pending_write_insns
= bb_pending_write_insns
[bb
];
7237 pending_write_mems
= bb_pending_write_mems
[bb
];
7238 pending_lists_length
= bb_pending_lists_length
[bb
];
7239 last_function_call
= bb_last_function_call
[bb
];
7240 last_pending_memory_flush
= bb_last_pending_memory_flush
[bb
];
7242 sched_before_next_call
= bb_sched_before_next_call
[bb
];
7245 /* do the analysis for this block */
7246 get_block_head_tail (bb
, &head
, &tail
);
7247 sched_analyze (head
, tail
);
7248 add_branch_dependences (head
, tail
);
7250 if (current_nr_blocks
> 1)
7253 int b_succ
, bb_succ
;
7255 rtx link_insn
, link_mem
;
7258 /* these lists should point to the right place, for correct freeing later. */
7259 bb_pending_read_insns
[bb
] = pending_read_insns
;
7260 bb_pending_read_mems
[bb
] = pending_read_mems
;
7261 bb_pending_write_insns
[bb
] = pending_write_insns
;
7262 bb_pending_write_mems
[bb
] = pending_write_mems
;
7264 /* bb's structures are inherited by it's successors */
7265 first_edge
= e
= OUT_EDGES (b
);
7269 b_succ
= TO_BLOCK (e
);
7270 bb_succ
= BLOCK_TO_BB (b_succ
);
7272 /* only bbs "below" bb, in the same region, are interesting */
7273 if (CONTAINING_RGN (b
) != CONTAINING_RGN (b_succ
)
7280 for (reg
= 0; reg
< max_reg
; reg
++)
7283 /* reg-last-uses lists are inherited by bb_succ */
7284 for (u
= reg_last_uses
[reg
]; u
; u
= XEXP (u
, 1))
7286 if (find_insn_list (XEXP (u
, 0), (bb_reg_last_uses
[bb_succ
])[reg
]))
7289 (bb_reg_last_uses
[bb_succ
])[reg
]
7290 = gen_rtx_INSN_LIST (VOIDmode
, XEXP (u
, 0),
7291 (bb_reg_last_uses
[bb_succ
])[reg
]);
7294 /* reg-last-defs lists are inherited by bb_succ */
7295 for (u
= reg_last_sets
[reg
]; u
; u
= XEXP (u
, 1))
7297 if (find_insn_list (XEXP (u
, 0), (bb_reg_last_sets
[bb_succ
])[reg
]))
7300 (bb_reg_last_sets
[bb_succ
])[reg
]
7301 = gen_rtx_INSN_LIST (VOIDmode
, XEXP (u
, 0),
7302 (bb_reg_last_sets
[bb_succ
])[reg
]);
7306 /* mem read/write lists are inherited by bb_succ */
7307 link_insn
= pending_read_insns
;
7308 link_mem
= pending_read_mems
;
7311 if (!(find_insn_mem_list (XEXP (link_insn
, 0), XEXP (link_mem
, 0),
7312 bb_pending_read_insns
[bb_succ
],
7313 bb_pending_read_mems
[bb_succ
])))
7314 add_insn_mem_dependence (&bb_pending_read_insns
[bb_succ
],
7315 &bb_pending_read_mems
[bb_succ
],
7316 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
7317 link_insn
= XEXP (link_insn
, 1);
7318 link_mem
= XEXP (link_mem
, 1);
7321 link_insn
= pending_write_insns
;
7322 link_mem
= pending_write_mems
;
7325 if (!(find_insn_mem_list (XEXP (link_insn
, 0), XEXP (link_mem
, 0),
7326 bb_pending_write_insns
[bb_succ
],
7327 bb_pending_write_mems
[bb_succ
])))
7328 add_insn_mem_dependence (&bb_pending_write_insns
[bb_succ
],
7329 &bb_pending_write_mems
[bb_succ
],
7330 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
7332 link_insn
= XEXP (link_insn
, 1);
7333 link_mem
= XEXP (link_mem
, 1);
7336 /* last_function_call is inherited by bb_succ */
7337 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
7339 if (find_insn_list (XEXP (u
, 0), bb_last_function_call
[bb_succ
]))
7342 bb_last_function_call
[bb_succ
]
7343 = gen_rtx_INSN_LIST (VOIDmode
, XEXP (u
, 0),
7344 bb_last_function_call
[bb_succ
]);
7347 /* last_pending_memory_flush is inherited by bb_succ */
7348 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
7350 if (find_insn_list (XEXP (u
, 0), bb_last_pending_memory_flush
[bb_succ
]))
7353 bb_last_pending_memory_flush
[bb_succ
]
7354 = gen_rtx_INSN_LIST (VOIDmode
, XEXP (u
, 0),
7355 bb_last_pending_memory_flush
[bb_succ
]);
7358 /* sched_before_next_call is inherited by bb_succ */
7359 x
= LOG_LINKS (sched_before_next_call
);
7360 for (; x
; x
= XEXP (x
, 1))
7361 add_dependence (bb_sched_before_next_call
[bb_succ
],
7362 XEXP (x
, 0), REG_DEP_ANTI
);
7366 while (e
!= first_edge
);
7370 /* Print dependences for debugging, callable from debugger */
7373 debug_dependencies ()
7377 fprintf (dump
, ";; --------------- forward dependences: ------------ \n");
7378 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7386 get_block_head_tail (bb
, &head
, &tail
);
7387 next_tail
= NEXT_INSN (tail
);
7388 fprintf (dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
7389 BB_TO_BLOCK (bb
), bb
);
7391 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7392 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7393 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7394 "----", "----", "--", "---", "----", "----", "--------", "-----");
7395 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
7400 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
7403 fprintf (dump
, ";; %6d ", INSN_UID (insn
));
7404 if (GET_CODE (insn
) == NOTE
)
7406 n
= NOTE_LINE_NUMBER (insn
);
7408 fprintf (dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
7410 fprintf (dump
, "line %d, file %s\n", n
,
7411 NOTE_SOURCE_FILE (insn
));
7414 fprintf (dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
7418 unit
= insn_unit (insn
);
7420 || function_units
[unit
].blockage_range_function
== 0) ? 0 :
7421 function_units
[unit
].blockage_range_function (insn
);
7423 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7424 (SCHED_GROUP_P (insn
) ? "+" : " "),
7428 INSN_DEP_COUNT (insn
),
7429 INSN_PRIORITY (insn
),
7430 insn_cost (insn
, 0, 0),
7431 (int) MIN_BLOCKAGE_COST (range
),
7432 (int) MAX_BLOCKAGE_COST (range
));
7433 insn_print_units (insn
);
7434 fprintf (dump
, "\t: ");
7435 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
7436 fprintf (dump
, "%d ", INSN_UID (XEXP (link
, 0)));
7437 fprintf (dump
, "\n");
7441 fprintf (dump
, "\n");
7444 /* Set_priorities: compute priority of each insn in the block */
7457 get_block_head_tail (bb
, &head
, &tail
);
7458 prev_head
= PREV_INSN (head
);
7461 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
7465 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
7468 if (GET_CODE (insn
) == NOTE
)
7471 if (!(SCHED_GROUP_P (insn
)))
7473 (void) priority (insn
);
7479 /* Make each element of VECTOR point at an rtx-vector,
7480 taking the space for all those rtx-vectors from SPACE.
7481 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7482 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7483 (this is the same as init_regset_vector () in flow.c) */
7486 init_rtx_vector (vector
, space
, nelts
, bytes_per_elt
)
7493 register rtx
*p
= space
;
7495 for (i
= 0; i
< nelts
; i
++)
7498 p
+= bytes_per_elt
/ sizeof (*p
);
7502 /* Schedule a region. A region is either an inner loop, a loop-free
7503 subroutine, or a single basic block. Each bb in the region is
7504 scheduled after its flow predecessors. */
7507 schedule_region (rgn
)
7511 int rgn_n_insns
= 0;
7512 int sched_rgn_n_insns
= 0;
7514 /* set variables for the current region */
7515 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
7516 current_blocks
= RGN_BLOCKS (rgn
);
7518 reg_pending_sets
= ALLOCA_REG_SET ();
7519 reg_pending_sets_all
= 0;
7521 /* initializations for region data dependence analyisis */
7522 if (current_nr_blocks
> 1)
7525 int maxreg
= max_reg_num ();
7527 bb_reg_last_uses
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7528 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7529 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7530 init_rtx_vector (bb_reg_last_uses
, space
, current_nr_blocks
, maxreg
* sizeof (rtx
*));
7532 bb_reg_last_sets
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7533 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7534 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7535 init_rtx_vector (bb_reg_last_sets
, space
, current_nr_blocks
, maxreg
* sizeof (rtx
*));
7537 bb_pending_read_insns
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7538 bb_pending_read_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7539 bb_pending_write_insns
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7540 bb_pending_write_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7541 bb_pending_lists_length
= (int *) alloca (current_nr_blocks
* sizeof (int));
7542 bb_last_pending_memory_flush
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7543 bb_last_function_call
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7544 bb_sched_before_next_call
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7546 init_rgn_data_dependences (current_nr_blocks
);
7549 /* compute LOG_LINKS */
7550 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7551 compute_block_backward_dependences (bb
);
7553 /* compute INSN_DEPEND */
7554 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
7555 compute_block_forward_dependences (bb
);
7557 /* Delete line notes, compute live-regs at block end, and set priorities. */
7559 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7561 if (reload_completed
== 0)
7562 find_pre_sched_live (bb
);
7564 if (write_symbols
!= NO_DEBUG
)
7566 save_line_notes (bb
);
7570 rgn_n_insns
+= set_priorities (bb
);
7573 /* compute interblock info: probabilities, split-edges, dominators, etc. */
7574 if (current_nr_blocks
> 1)
7578 prob
= (float *) alloca ((current_nr_blocks
) * sizeof (float));
7580 bbset_size
= current_nr_blocks
/ HOST_BITS_PER_WIDE_INT
+ 1;
7581 dom
= (bbset
*) alloca (current_nr_blocks
* sizeof (bbset
));
7582 for (i
= 0; i
< current_nr_blocks
; i
++)
7584 dom
[i
] = (bbset
) alloca (bbset_size
* sizeof (HOST_WIDE_INT
));
7585 bzero ((char *) dom
[i
], bbset_size
* sizeof (HOST_WIDE_INT
));
7590 edge_to_bit
= (int *) alloca (nr_edges
* sizeof (int));
7591 for (i
= 1; i
< nr_edges
; i
++)
7592 if (CONTAINING_RGN (FROM_BLOCK (i
)) == rgn
)
7593 EDGE_TO_BIT (i
) = rgn_nr_edges
++;
7594 rgn_edges
= (int *) alloca (rgn_nr_edges
* sizeof (int));
7597 for (i
= 1; i
< nr_edges
; i
++)
7598 if (CONTAINING_RGN (FROM_BLOCK (i
)) == (rgn
))
7599 rgn_edges
[rgn_nr_edges
++] = i
;
7602 edgeset_size
= rgn_nr_edges
/ HOST_BITS_PER_WIDE_INT
+ 1;
7603 pot_split
= (edgeset
*) alloca (current_nr_blocks
* sizeof (edgeset
));
7604 ancestor_edges
= (edgeset
*) alloca (current_nr_blocks
* sizeof (edgeset
));
7605 for (i
= 0; i
< current_nr_blocks
; i
++)
7608 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
7609 bzero ((char *) pot_split
[i
],
7610 edgeset_size
* sizeof (HOST_WIDE_INT
));
7612 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
7613 bzero ((char *) ancestor_edges
[i
],
7614 edgeset_size
* sizeof (HOST_WIDE_INT
));
7617 /* compute probabilities, dominators, split_edges */
7618 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7619 compute_dom_prob_ps (bb
);
7622 /* now we can schedule all blocks */
7623 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7625 sched_rgn_n_insns
+= schedule_block (bb
, rgn_n_insns
);
7632 #ifdef INTERBLOCK_DEBUG
7633 if (sched_debug_count
!= 0)
7635 /* sanity check: verify that all region insns were scheduled */
7636 if (sched_rgn_n_insns
!= rgn_n_insns
)
7639 /* update register life and usage information */
7640 if (reload_completed
== 0)
7642 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
7643 find_post_sched_live (bb
);
7645 if (current_nr_blocks
<= 1)
7646 /* Sanity check. There should be no REG_DEAD notes leftover at the end.
7647 In practice, this can occur as the result of bugs in flow, combine.c,
7648 and/or sched.c. The values of the REG_DEAD notes remaining are
7649 meaningless, because dead_notes is just used as a free list. */
7650 if (dead_notes
!= 0)
7654 /* restore line notes. */
7655 if (write_symbols
!= NO_DEBUG
)
7657 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7658 restore_line_notes (bb
);
7661 /* Done with this region */
7662 free_pending_lists ();
7664 FREE_REG_SET (reg_pending_sets
);
7667 /* Subroutine of split_hard_reg_notes. Searches X for any reference to
7668 REGNO, returning the rtx of the reference found if any. Otherwise,
7672 regno_use_in (regno
, x
)
7680 if (GET_CODE (x
) == REG
&& REGNO (x
) == regno
)
7683 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
7684 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0; i
--)
7688 if ((tem
= regno_use_in (regno
, XEXP (x
, i
))))
7691 else if (fmt
[i
] == 'E')
7692 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
7693 if ((tem
= regno_use_in (regno
, XVECEXP (x
, i
, j
))))
7700 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
7701 needed for the hard register mentioned in the note. This can happen
7702 if the reference to the hard register in the original insn was split into
7703 several smaller hard register references in the split insns. */
7706 split_hard_reg_notes (note
, first
, last
)
7707 rtx note
, first
, last
;
7709 rtx reg
, temp
, link
;
7710 int n_regs
, i
, new_reg
;
7713 /* Assume that this is a REG_DEAD note. */
7714 if (REG_NOTE_KIND (note
) != REG_DEAD
)
7717 reg
= XEXP (note
, 0);
7719 n_regs
= HARD_REGNO_NREGS (REGNO (reg
), GET_MODE (reg
));
7721 for (i
= 0; i
< n_regs
; i
++)
7723 new_reg
= REGNO (reg
) + i
;
7725 /* Check for references to new_reg in the split insns. */
7726 for (insn
= last
;; insn
= PREV_INSN (insn
))
7728 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7729 && (temp
= regno_use_in (new_reg
, PATTERN (insn
))))
7731 /* Create a new reg dead note ere. */
7732 link
= rtx_alloc (EXPR_LIST
);
7733 PUT_REG_NOTE_KIND (link
, REG_DEAD
);
7734 XEXP (link
, 0) = temp
;
7735 XEXP (link
, 1) = REG_NOTES (insn
);
7736 REG_NOTES (insn
) = link
;
7738 /* If killed multiple registers here, then add in the excess. */
7739 i
+= HARD_REGNO_NREGS (REGNO (temp
), GET_MODE (temp
)) - 1;
7743 /* It isn't mentioned anywhere, so no new reg note is needed for
7751 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
7752 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
7755 new_insn_dead_notes (pat
, insn
, last
, orig_insn
)
7756 rtx pat
, insn
, last
, orig_insn
;
7760 /* PAT is either a CLOBBER or a SET here. */
7761 dest
= XEXP (pat
, 0);
7763 while (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
7764 || GET_CODE (dest
) == STRICT_LOW_PART
7765 || GET_CODE (dest
) == SIGN_EXTRACT
)
7766 dest
= XEXP (dest
, 0);
7768 if (GET_CODE (dest
) == REG
)
7770 for (tem
= last
; tem
!= insn
; tem
= PREV_INSN (tem
))
7772 if (GET_RTX_CLASS (GET_CODE (tem
)) == 'i'
7773 && reg_overlap_mentioned_p (dest
, PATTERN (tem
))
7774 && (set
= single_set (tem
)))
7776 rtx tem_dest
= SET_DEST (set
);
7778 while (GET_CODE (tem_dest
) == ZERO_EXTRACT
7779 || GET_CODE (tem_dest
) == SUBREG
7780 || GET_CODE (tem_dest
) == STRICT_LOW_PART
7781 || GET_CODE (tem_dest
) == SIGN_EXTRACT
)
7782 tem_dest
= XEXP (tem_dest
, 0);
7784 if (!rtx_equal_p (tem_dest
, dest
))
7786 /* Use the same scheme as combine.c, don't put both REG_DEAD
7787 and REG_UNUSED notes on the same insn. */
7788 if (!find_regno_note (tem
, REG_UNUSED
, REGNO (dest
))
7789 && !find_regno_note (tem
, REG_DEAD
, REGNO (dest
)))
7791 rtx note
= rtx_alloc (EXPR_LIST
);
7792 PUT_REG_NOTE_KIND (note
, REG_DEAD
);
7793 XEXP (note
, 0) = dest
;
7794 XEXP (note
, 1) = REG_NOTES (tem
);
7795 REG_NOTES (tem
) = note
;
7797 /* The reg only dies in one insn, the last one that uses
7801 else if (reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
7802 /* We found an instruction that both uses the register,
7803 and sets it, so no new REG_NOTE is needed for this set. */
7807 /* If this is a set, it must die somewhere, unless it is the dest of
7808 the original insn, and hence is live after the original insn. Abort
7809 if it isn't supposed to be live after the original insn.
7811 If this is a clobber, then just add a REG_UNUSED note. */
7814 int live_after_orig_insn
= 0;
7815 rtx pattern
= PATTERN (orig_insn
);
7818 if (GET_CODE (pat
) == CLOBBER
)
7820 rtx note
= rtx_alloc (EXPR_LIST
);
7821 PUT_REG_NOTE_KIND (note
, REG_UNUSED
);
7822 XEXP (note
, 0) = dest
;
7823 XEXP (note
, 1) = REG_NOTES (insn
);
7824 REG_NOTES (insn
) = note
;
7828 /* The original insn could have multiple sets, so search the
7829 insn for all sets. */
7830 if (GET_CODE (pattern
) == SET
)
7832 if (reg_overlap_mentioned_p (dest
, SET_DEST (pattern
)))
7833 live_after_orig_insn
= 1;
7835 else if (GET_CODE (pattern
) == PARALLEL
)
7837 for (i
= 0; i
< XVECLEN (pattern
, 0); i
++)
7838 if (GET_CODE (XVECEXP (pattern
, 0, i
)) == SET
7839 && reg_overlap_mentioned_p (dest
,
7840 SET_DEST (XVECEXP (pattern
,
7842 live_after_orig_insn
= 1;
7845 if (!live_after_orig_insn
)
7851 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
7852 registers modified by X. INC is -1 if the containing insn is being deleted,
7853 and is 1 if the containing insn is a newly generated insn. */
7856 update_n_sets (x
, inc
)
7860 rtx dest
= SET_DEST (x
);
7862 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
7863 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
7864 dest
= SUBREG_REG (dest
);
7866 if (GET_CODE (dest
) == REG
)
7868 int regno
= REGNO (dest
);
7870 if (regno
< FIRST_PSEUDO_REGISTER
)
7873 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
7875 for (i
= regno
; i
< endregno
; i
++)
7876 REG_N_SETS (i
) += inc
;
7879 REG_N_SETS (regno
) += inc
;
7883 /* Updates all flow-analysis related quantities (including REG_NOTES) for
7884 the insns from FIRST to LAST inclusive that were created by splitting
7885 ORIG_INSN. NOTES are the original REG_NOTES. */
7888 update_flow_info (notes
, first
, last
, orig_insn
)
7895 rtx orig_dest
, temp
;
7898 /* Get and save the destination set by the original insn. */
7900 orig_dest
= single_set (orig_insn
);
7902 orig_dest
= SET_DEST (orig_dest
);
7904 /* Move REG_NOTES from the original insn to where they now belong. */
7906 for (note
= notes
; note
; note
= next
)
7908 next
= XEXP (note
, 1);
7909 switch (REG_NOTE_KIND (note
))
7913 /* Move these notes from the original insn to the last new insn where
7914 the register is now set. */
7916 for (insn
= last
;; insn
= PREV_INSN (insn
))
7918 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7919 && reg_mentioned_p (XEXP (note
, 0), PATTERN (insn
)))
7921 /* If this note refers to a multiple word hard register, it
7922 may have been split into several smaller hard register
7923 references, so handle it specially. */
7924 temp
= XEXP (note
, 0);
7925 if (REG_NOTE_KIND (note
) == REG_DEAD
7926 && GET_CODE (temp
) == REG
7927 && REGNO (temp
) < FIRST_PSEUDO_REGISTER
7928 && HARD_REGNO_NREGS (REGNO (temp
), GET_MODE (temp
)) > 1)
7929 split_hard_reg_notes (note
, first
, last
);
7932 XEXP (note
, 1) = REG_NOTES (insn
);
7933 REG_NOTES (insn
) = note
;
7936 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
7938 /* ??? This won't handle multiple word registers correctly,
7939 but should be good enough for now. */
7940 if (REG_NOTE_KIND (note
) == REG_UNUSED
7941 && GET_CODE (XEXP (note
, 0)) != SCRATCH
7942 && !dead_or_set_p (insn
, XEXP (note
, 0)))
7943 PUT_REG_NOTE_KIND (note
, REG_DEAD
);
7945 /* The reg only dies in one insn, the last one that uses
7949 /* It must die somewhere, fail it we couldn't find where it died.
7951 If this is a REG_UNUSED note, then it must be a temporary
7952 register that was not needed by this instantiation of the
7953 pattern, so we can safely ignore it. */
7956 /* After reload, REG_DEAD notes come sometimes an
7957 instruction after the register actually dies. */
7958 if (reload_completed
&& REG_NOTE_KIND (note
) == REG_DEAD
)
7960 XEXP (note
, 1) = REG_NOTES (insn
);
7961 REG_NOTES (insn
) = note
;
7965 if (REG_NOTE_KIND (note
) != REG_UNUSED
)
7974 /* If the insn that set the register to 0 was deleted, this
7975 note cannot be relied on any longer. The destination might
7976 even have been moved to memory.
7977 This was observed for SH4 with execute/920501-6.c compilation,
7978 -O2 -fomit-frame-pointer -finline-functions . */
7979 if (GET_CODE (XEXP (note
, 0)) == NOTE
7980 || INSN_DELETED_P (XEXP (note
, 0)))
7982 /* This note applies to the dest of the original insn. Find the
7983 first new insn that now has the same dest, and move the note
7989 for (insn
= first
;; insn
= NEXT_INSN (insn
))
7991 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7992 && (temp
= single_set (insn
))
7993 && rtx_equal_p (SET_DEST (temp
), orig_dest
))
7995 XEXP (note
, 1) = REG_NOTES (insn
);
7996 REG_NOTES (insn
) = note
;
7997 /* The reg is only zero before one insn, the first that
8001 /* If this note refers to a multiple word hard
8002 register, it may have been split into several smaller
8003 hard register references. We could split the notes,
8004 but simply dropping them is good enough. */
8005 if (GET_CODE (orig_dest
) == REG
8006 && REGNO (orig_dest
) < FIRST_PSEUDO_REGISTER
8007 && HARD_REGNO_NREGS (REGNO (orig_dest
),
8008 GET_MODE (orig_dest
)) > 1)
8010 /* It must be set somewhere, fail if we couldn't find where it
8019 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
8020 set is meaningless. Just drop the note. */
8024 case REG_NO_CONFLICT
:
8025 /* These notes apply to the dest of the original insn. Find the last
8026 new insn that now has the same dest, and move the note there. */
8031 for (insn
= last
;; insn
= PREV_INSN (insn
))
8033 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8034 && (temp
= single_set (insn
))
8035 && rtx_equal_p (SET_DEST (temp
), orig_dest
))
8037 XEXP (note
, 1) = REG_NOTES (insn
);
8038 REG_NOTES (insn
) = note
;
8039 /* Only put this note on one of the new insns. */
8043 /* The original dest must still be set someplace. Abort if we
8044 couldn't find it. */
8047 /* However, if this note refers to a multiple word hard
8048 register, it may have been split into several smaller
8049 hard register references. We could split the notes,
8050 but simply dropping them is good enough. */
8051 if (GET_CODE (orig_dest
) == REG
8052 && REGNO (orig_dest
) < FIRST_PSEUDO_REGISTER
8053 && HARD_REGNO_NREGS (REGNO (orig_dest
),
8054 GET_MODE (orig_dest
)) > 1)
8056 /* Likewise for multi-word memory references. */
8057 if (GET_CODE (orig_dest
) == MEM
8058 && SIZE_FOR_MODE (orig_dest
) > MOVE_MAX
)
8066 /* Move a REG_LIBCALL note to the first insn created, and update
8067 the corresponding REG_RETVAL note. */
8068 XEXP (note
, 1) = REG_NOTES (first
);
8069 REG_NOTES (first
) = note
;
8071 insn
= XEXP (note
, 0);
8072 note
= find_reg_note (insn
, REG_RETVAL
, NULL_RTX
);
8074 XEXP (note
, 0) = first
;
8077 case REG_EXEC_COUNT
:
8078 /* Move a REG_EXEC_COUNT note to the first insn created. */
8079 XEXP (note
, 1) = REG_NOTES (first
);
8080 REG_NOTES (first
) = note
;
8084 /* Move a REG_RETVAL note to the last insn created, and update
8085 the corresponding REG_LIBCALL note. */
8086 XEXP (note
, 1) = REG_NOTES (last
);
8087 REG_NOTES (last
) = note
;
8089 insn
= XEXP (note
, 0);
8090 note
= find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
);
8092 XEXP (note
, 0) = last
;
8097 /* This should be moved to whichever instruction is a JUMP_INSN. */
8099 for (insn
= last
;; insn
= PREV_INSN (insn
))
8101 if (GET_CODE (insn
) == JUMP_INSN
)
8103 XEXP (note
, 1) = REG_NOTES (insn
);
8104 REG_NOTES (insn
) = note
;
8105 /* Only put this note on one of the new insns. */
8108 /* Fail if we couldn't find a JUMP_INSN. */
8115 /* reload sometimes leaves obsolete REG_INC notes around. */
8116 if (reload_completed
)
8118 /* This should be moved to whichever instruction now has the
8119 increment operation. */
8123 /* Should be moved to the new insn(s) which use the label. */
8124 for (insn
= first
; insn
!= NEXT_INSN (last
); insn
= NEXT_INSN (insn
))
8125 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8126 && reg_mentioned_p (XEXP (note
, 0), PATTERN (insn
)))
8127 REG_NOTES (insn
) = gen_rtx_EXPR_LIST (REG_LABEL
,
8134 /* These two notes will never appear until after reorg, so we don't
8135 have to handle them here. */
8141 /* Each new insn created, except the last, has a new set. If the destination
8142 is a register, then this reg is now live across several insns, whereas
8143 previously the dest reg was born and died within the same insn. To
8144 reflect this, we now need a REG_DEAD note on the insn where this
8147 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
8149 for (insn
= first
; insn
!= last
; insn
= NEXT_INSN (insn
))
8154 pat
= PATTERN (insn
);
8155 if (GET_CODE (pat
) == SET
|| GET_CODE (pat
) == CLOBBER
)
8156 new_insn_dead_notes (pat
, insn
, last
, orig_insn
);
8157 else if (GET_CODE (pat
) == PARALLEL
)
8159 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
8160 if (GET_CODE (XVECEXP (pat
, 0, i
)) == SET
8161 || GET_CODE (XVECEXP (pat
, 0, i
)) == CLOBBER
)
8162 new_insn_dead_notes (XVECEXP (pat
, 0, i
), insn
, last
, orig_insn
);
8166 /* If any insn, except the last, uses the register set by the last insn,
8167 then we need a new REG_DEAD note on that insn. In this case, there
8168 would not have been a REG_DEAD note for this register in the original
8169 insn because it was used and set within one insn. */
8171 set
= single_set (last
);
8174 rtx dest
= SET_DEST (set
);
8176 while (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
8177 || GET_CODE (dest
) == STRICT_LOW_PART
8178 || GET_CODE (dest
) == SIGN_EXTRACT
)
8179 dest
= XEXP (dest
, 0);
8181 if (GET_CODE (dest
) == REG
8182 /* Global registers are always live, so the code below does not
8184 && (REGNO (dest
) >= FIRST_PSEUDO_REGISTER
8185 || ! global_regs
[REGNO (dest
)]))
8187 rtx stop_insn
= PREV_INSN (first
);
8189 /* If the last insn uses the register that it is setting, then
8190 we don't want to put a REG_DEAD note there. Search backwards
8191 to find the first insn that sets but does not use DEST. */
8194 if (reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
8196 for (insn
= PREV_INSN (insn
); insn
!= first
;
8197 insn
= PREV_INSN (insn
))
8199 if ((set
= single_set (insn
))
8200 && reg_mentioned_p (dest
, SET_DEST (set
))
8201 && ! reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
8206 /* Now find the first insn that uses but does not set DEST. */
8208 for (insn
= PREV_INSN (insn
); insn
!= stop_insn
;
8209 insn
= PREV_INSN (insn
))
8211 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8212 && reg_mentioned_p (dest
, PATTERN (insn
))
8213 && (set
= single_set (insn
)))
8215 rtx insn_dest
= SET_DEST (set
);
8217 while (GET_CODE (insn_dest
) == ZERO_EXTRACT
8218 || GET_CODE (insn_dest
) == SUBREG
8219 || GET_CODE (insn_dest
) == STRICT_LOW_PART
8220 || GET_CODE (insn_dest
) == SIGN_EXTRACT
)
8221 insn_dest
= XEXP (insn_dest
, 0);
8223 if (insn_dest
!= dest
)
8225 note
= rtx_alloc (EXPR_LIST
);
8226 PUT_REG_NOTE_KIND (note
, REG_DEAD
);
8227 XEXP (note
, 0) = dest
;
8228 XEXP (note
, 1) = REG_NOTES (insn
);
8229 REG_NOTES (insn
) = note
;
8230 /* The reg only dies in one insn, the last one
8239 /* If the original dest is modifying a multiple register target, and the
8240 original instruction was split such that the original dest is now set
8241 by two or more SUBREG sets, then the split insns no longer kill the
8242 destination of the original insn.
8244 In this case, if there exists an instruction in the same basic block,
8245 before the split insn, which uses the original dest, and this use is
8246 killed by the original insn, then we must remove the REG_DEAD note on
8247 this insn, because it is now superfluous.
8249 This does not apply when a hard register gets split, because the code
8250 knows how to handle overlapping hard registers properly. */
8251 if (orig_dest
&& GET_CODE (orig_dest
) == REG
)
8253 int found_orig_dest
= 0;
8254 int found_split_dest
= 0;
8256 for (insn
= first
;; insn
= NEXT_INSN (insn
))
8261 /* I'm not sure if this can happen, but let's be safe. */
8262 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
8265 pat
= PATTERN (insn
);
8266 i
= GET_CODE (pat
) == PARALLEL
? XVECLEN (pat
, 0) : 0;
8271 if (GET_CODE (set
) == SET
)
8273 if (GET_CODE (SET_DEST (set
)) == REG
8274 && REGNO (SET_DEST (set
)) == REGNO (orig_dest
))
8276 found_orig_dest
= 1;
8279 else if (GET_CODE (SET_DEST (set
)) == SUBREG
8280 && SUBREG_REG (SET_DEST (set
)) == orig_dest
)
8282 found_split_dest
= 1;
8288 set
= XVECEXP (pat
, 0, i
);
8295 if (found_split_dest
)
8297 /* Search backwards from FIRST, looking for the first insn that uses
8298 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
8299 If we find an insn, and it has a REG_DEAD note, then delete the
8302 for (insn
= first
; insn
; insn
= PREV_INSN (insn
))
8304 if (GET_CODE (insn
) == CODE_LABEL
8305 || GET_CODE (insn
) == JUMP_INSN
)
8307 else if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8308 && reg_mentioned_p (orig_dest
, insn
))
8310 note
= find_regno_note (insn
, REG_DEAD
, REGNO (orig_dest
));
8312 remove_note (insn
, note
);
8316 else if (!found_orig_dest
)
8318 /* This should never happen. */
8323 /* Update reg_n_sets. This is necessary to prevent local alloc from
8324 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
8325 a reg from set once to set multiple times. */
8328 rtx x
= PATTERN (orig_insn
);
8329 RTX_CODE code
= GET_CODE (x
);
8331 if (code
== SET
|| code
== CLOBBER
)
8332 update_n_sets (x
, -1);
8333 else if (code
== PARALLEL
)
8336 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
8338 code
= GET_CODE (XVECEXP (x
, 0, i
));
8339 if (code
== SET
|| code
== CLOBBER
)
8340 update_n_sets (XVECEXP (x
, 0, i
), -1);
8344 for (insn
= first
;; insn
= NEXT_INSN (insn
))
8347 code
= GET_CODE (x
);
8349 if (code
== SET
|| code
== CLOBBER
)
8350 update_n_sets (x
, 1);
8351 else if (code
== PARALLEL
)
8354 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
8356 code
= GET_CODE (XVECEXP (x
, 0, i
));
8357 if (code
== SET
|| code
== CLOBBER
)
8358 update_n_sets (XVECEXP (x
, 0, i
), 1);
8368 /* Do the splitting of insns in the block b. */
8371 split_block_insns (b
)
8376 for (insn
= basic_block_head
[b
];; insn
= next
)
8381 /* Can't use `next_real_insn' because that
8382 might go across CODE_LABELS and short-out basic blocks. */
8383 next
= NEXT_INSN (insn
);
8384 if (GET_CODE (insn
) != INSN
)
8386 if (insn
== basic_block_end
[b
])
8392 /* Don't split no-op move insns. These should silently disappear
8393 later in final. Splitting such insns would break the code
8394 that handles REG_NO_CONFLICT blocks. */
8395 set
= single_set (insn
);
8396 if (set
&& rtx_equal_p (SET_SRC (set
), SET_DEST (set
)))
8398 if (insn
== basic_block_end
[b
])
8401 /* Nops get in the way while scheduling, so delete them now if
8402 register allocation has already been done. It is too risky
8403 to try to do this before register allocation, and there are
8404 unlikely to be very many nops then anyways. */
8405 if (reload_completed
)
8407 PUT_CODE (insn
, NOTE
);
8408 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
8409 NOTE_SOURCE_FILE (insn
) = 0;
8415 /* Split insns here to get max fine-grain parallelism. */
8416 prev
= PREV_INSN (insn
);
8417 /* It is probably not worthwhile to try to split again in
8418 the second pass. However, if flag_schedule_insns is not set,
8419 the first and only (if any) scheduling pass is after reload. */
8420 if (reload_completed
== 0 || ! flag_schedule_insns
)
8422 rtx last
, first
= PREV_INSN (insn
);
8423 rtx notes
= REG_NOTES (insn
);
8424 last
= try_split (PATTERN (insn
), insn
, 1);
8427 /* try_split returns the NOTE that INSN became. */
8428 first
= NEXT_INSN (first
);
8429 update_flow_info (notes
, first
, last
, insn
);
8431 PUT_CODE (insn
, NOTE
);
8432 NOTE_SOURCE_FILE (insn
) = 0;
8433 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
8434 if (insn
== basic_block_head
[b
])
8435 basic_block_head
[b
] = first
;
8436 if (insn
== basic_block_end
[b
])
8438 basic_block_end
[b
] = last
;
8444 if (insn
== basic_block_end
[b
])
8449 /* The one entry point in this file. DUMP_FILE is the dump file for
8453 schedule_insns (dump_file
)
8464 /* disable speculative loads in their presence if cc0 defined */
8466 flag_schedule_speculative_load
= 0;
8469 /* Taking care of this degenerate case makes the rest of
8470 this code simpler. */
8471 if (n_basic_blocks
== 0)
8474 /* set dump and sched_verbose for the desired debugging output. If no
8475 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
8476 For -fsched-verbose-N, N>=10, print everything to stderr. */
8477 sched_verbose
= sched_verbose_param
;
8478 if (sched_verbose_param
== 0 && dump_file
)
8480 dump
= ((sched_verbose_param
>= 10 || !dump_file
) ? stderr
: dump_file
);
8485 /* Initialize the unused_*_lists. We can't use the ones left over from
8486 the previous function, because gcc has freed that memory. We can use
8487 the ones left over from the first sched pass in the second pass however,
8488 so only clear them on the first sched pass. The first pass is before
8489 reload if flag_schedule_insns is set, otherwise it is afterwards. */
8491 if (reload_completed
== 0 || !flag_schedule_insns
)
8493 unused_insn_list
= 0;
8494 unused_expr_list
= 0;
8497 /* initialize issue_rate */
8498 issue_rate
= ISSUE_RATE
;
8500 /* do the splitting first for all blocks */
8501 for (b
= 0; b
< n_basic_blocks
; b
++)
8502 split_block_insns (b
);
8504 max_uid
= (get_max_uid () + 1);
8506 cant_move
= (char *) alloca (max_uid
* sizeof (char));
8507 bzero ((char *) cant_move
, max_uid
* sizeof (char));
8509 fed_by_spec_load
= (char *) alloca (max_uid
* sizeof (char));
8510 bzero ((char *) fed_by_spec_load
, max_uid
* sizeof (char));
8512 is_load_insn
= (char *) alloca (max_uid
* sizeof (char));
8513 bzero ((char *) is_load_insn
, max_uid
* sizeof (char));
8515 insn_orig_block
= (int *) alloca (max_uid
* sizeof (int));
8516 insn_luid
= (int *) alloca (max_uid
* sizeof (int));
8519 for (b
= 0; b
< n_basic_blocks
; b
++)
8520 for (insn
= basic_block_head
[b
];; insn
= NEXT_INSN (insn
))
8522 INSN_BLOCK (insn
) = b
;
8523 INSN_LUID (insn
) = luid
++;
8525 if (insn
== basic_block_end
[b
])
8529 /* after reload, remove inter-blocks dependences computed before reload. */
8530 if (reload_completed
)
8535 for (b
= 0; b
< n_basic_blocks
; b
++)
8536 for (insn
= basic_block_head
[b
];; insn
= NEXT_INSN (insn
))
8540 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
8543 link
= LOG_LINKS (insn
);
8546 rtx x
= XEXP (link
, 0);
8548 if (INSN_BLOCK (x
) != b
)
8550 remove_dependence (insn
, x
);
8551 link
= prev
? XEXP (prev
, 1) : LOG_LINKS (insn
);
8554 prev
= link
, link
= XEXP (prev
, 1);
8558 if (insn
== basic_block_end
[b
])
8564 rgn_table
= (region
*) alloca ((n_basic_blocks
) * sizeof (region
));
8565 rgn_bb_table
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8566 block_to_bb
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8567 containing_rgn
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8569 /* compute regions for scheduling */
8570 if (reload_completed
8571 || n_basic_blocks
== 1
8572 || !flag_schedule_interblock
)
8574 find_single_block_region ();
8578 /* an estimation for nr_edges is computed in is_cfg_nonregular () */
8581 /* verify that a 'good' control flow graph can be built */
8582 if (is_cfg_nonregular ()
8585 find_single_block_region ();
8589 /* build control flow graph */
8590 in_edges
= (int *) alloca (n_basic_blocks
* sizeof (int));
8591 out_edges
= (int *) alloca (n_basic_blocks
* sizeof (int));
8592 bzero ((char *) in_edges
, n_basic_blocks
* sizeof (int));
8593 bzero ((char *) out_edges
, n_basic_blocks
* sizeof (int));
8596 (edge
*) alloca ((nr_edges
) * sizeof (edge
));
8597 bzero ((char *) edge_table
,
8598 ((nr_edges
) * sizeof (edge
)));
8599 build_control_flow ();
8601 /* identify reducible inner loops and compute regions */
8604 if (sched_verbose
>= 3)
8606 debug_control_flow ();
8613 /* Allocate data for this pass. See comments, above,
8614 for what these vectors do. */
8615 insn_priority
= (int *) alloca (max_uid
* sizeof (int));
8616 insn_reg_weight
= (int *) alloca (max_uid
* sizeof (int));
8617 insn_tick
= (int *) alloca (max_uid
* sizeof (int));
8618 insn_costs
= (short *) alloca (max_uid
* sizeof (short));
8619 insn_units
= (short *) alloca (max_uid
* sizeof (short));
8620 insn_blockage
= (unsigned int *) alloca (max_uid
* sizeof (unsigned int));
8621 insn_ref_count
= (int *) alloca (max_uid
* sizeof (int));
8623 /* Allocate for forward dependencies */
8624 insn_dep_count
= (int *) alloca (max_uid
* sizeof (int));
8625 insn_depend
= (rtx
*) alloca (max_uid
* sizeof (rtx
));
8627 if (reload_completed
== 0)
8631 sched_reg_n_calls_crossed
= (int *) alloca (max_regno
* sizeof (int));
8632 sched_reg_live_length
= (int *) alloca (max_regno
* sizeof (int));
8633 sched_reg_basic_block
= (int *) alloca (max_regno
* sizeof (int));
8634 bb_live_regs
= ALLOCA_REG_SET ();
8635 bzero ((char *) sched_reg_n_calls_crossed
, max_regno
* sizeof (int));
8636 bzero ((char *) sched_reg_live_length
, max_regno
* sizeof (int));
8638 for (i
= 0; i
< max_regno
; i
++)
8639 sched_reg_basic_block
[i
] = REG_BLOCK_UNKNOWN
;
8643 sched_reg_n_calls_crossed
= 0;
8644 sched_reg_live_length
= 0;
8647 init_alias_analysis ();
8649 if (write_symbols
!= NO_DEBUG
)
8653 line_note
= (rtx
*) alloca (max_uid
* sizeof (rtx
));
8654 bzero ((char *) line_note
, max_uid
* sizeof (rtx
));
8655 line_note_head
= (rtx
*) alloca (n_basic_blocks
* sizeof (rtx
));
8656 bzero ((char *) line_note_head
, n_basic_blocks
* sizeof (rtx
));
8658 /* Save-line-note-head:
8659 Determine the line-number at the start of each basic block.
8660 This must be computed and saved now, because after a basic block's
8661 predecessor has been scheduled, it is impossible to accurately
8662 determine the correct line number for the first insn of the block. */
8664 for (b
= 0; b
< n_basic_blocks
; b
++)
8665 for (line
= basic_block_head
[b
]; line
; line
= PREV_INSN (line
))
8666 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
8668 line_note_head
[b
] = line
;
8673 bzero ((char *) insn_priority
, max_uid
* sizeof (int));
8674 bzero ((char *) insn_reg_weight
, max_uid
* sizeof (int));
8675 bzero ((char *) insn_tick
, max_uid
* sizeof (int));
8676 bzero ((char *) insn_costs
, max_uid
* sizeof (short));
8677 bzero ((char *) insn_units
, max_uid
* sizeof (short));
8678 bzero ((char *) insn_blockage
, max_uid
* sizeof (unsigned int));
8679 bzero ((char *) insn_ref_count
, max_uid
* sizeof (int));
8681 /* Initialize for forward dependencies */
8682 bzero ((char *) insn_depend
, max_uid
* sizeof (rtx
));
8683 bzero ((char *) insn_dep_count
, max_uid
* sizeof (int));
8685 /* Find units used in this fuction, for visualization */
8687 init_target_units ();
8689 /* ??? Add a NOTE after the last insn of the last basic block. It is not
8690 known why this is done. */
8692 insn
= basic_block_end
[n_basic_blocks
- 1];
8693 if (NEXT_INSN (insn
) == 0
8694 || (GET_CODE (insn
) != NOTE
8695 && GET_CODE (insn
) != CODE_LABEL
8696 /* Don't emit a NOTE if it would end up between an unconditional
8697 jump and a BARRIER. */
8698 && !(GET_CODE (insn
) == JUMP_INSN
8699 && GET_CODE (NEXT_INSN (insn
)) == BARRIER
)))
8700 emit_note_after (NOTE_INSN_DELETED
, basic_block_end
[n_basic_blocks
- 1]);
8702 /* Schedule every region in the subroutine */
8703 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
8705 schedule_region (rgn
);
8712 /* Reposition the prologue and epilogue notes in case we moved the
8713 prologue/epilogue insns. */
8714 if (reload_completed
)
8715 reposition_prologue_and_epilogue_notes (get_insns ());
8717 /* delete redundant line notes. */
8718 if (write_symbols
!= NO_DEBUG
)
8719 rm_redundant_line_notes ();
8721 /* Update information about uses of registers in the subroutine. */
8722 if (reload_completed
== 0)
8723 update_reg_usage ();
8727 if (reload_completed
== 0 && flag_schedule_interblock
)
8729 fprintf (dump
, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8737 fprintf (dump
, "\n\n");
8741 FREE_REG_SET (bb_live_regs
);
8743 #endif /* INSN_SCHEDULING */