1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 93-97, 1998 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to the Free
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
24 /* Instruction scheduling pass.
26 This pass implements list scheduling within basic blocks. It is
27 run twice: (1) after flow analysis, but before register allocation,
28 and (2) after register allocation.
30 The first run performs interblock scheduling, moving insns between
31 different blocks in the same "region", and the second runs only
32 basic block scheduling.
34 Interblock motions performed are useful motions and speculative
35 motions, including speculative loads. Motions requiring code
36 duplication are not supported. The identification of motion type
37 and the check for validity of speculative motions requires
38 construction and analysis of the function's control flow graph.
39 The scheduler works as follows:
41 We compute insn priorities based on data dependencies. Flow
42 analysis only creates a fraction of the data-dependencies we must
43 observe: namely, only those dependencies which the combiner can be
44 expected to use. For this pass, we must therefore create the
45 remaining dependencies we need to observe: register dependencies,
46 memory dependencies, dependencies to keep function calls in order,
47 and the dependence between a conditional branch and the setting of
48 condition codes are all dealt with here.
50 The scheduler first traverses the data flow graph, starting with
51 the last instruction, and proceeding to the first, assigning values
52 to insn_priority as it goes. This sorts the instructions
53 topologically by data dependence.
55 Once priorities have been established, we order the insns using
56 list scheduling. This works as follows: starting with a list of
57 all the ready insns, and sorted according to priority number, we
58 schedule the insn from the end of the list by placing its
59 predecessors in the list according to their priority order. We
60 consider this insn scheduled by setting the pointer to the "end" of
61 the list to point to the previous insn. When an insn has no
62 predecessors, we either queue it until sufficient time has elapsed
63 or add it to the ready list. As the instructions are scheduled or
64 when stalls are introduced, the queue advances and dumps insns into
65 the ready list. When all insns down to the lowest priority have
66 been scheduled, the critical path of the basic block has been made
67 as short as possible. The remaining insns are then scheduled in
70 Function unit conflicts are resolved during forward list scheduling
71 by tracking the time when each insn is committed to the schedule
72 and from that, the time the function units it uses must be free.
73 As insns on the ready list are considered for scheduling, those
74 that would result in a blockage of the already committed insns are
75 queued until no blockage will result.
77 The following list shows the order in which we want to break ties
78 among insns in the ready list:
80 1. choose insn with the longest path to end of bb, ties
82 2. choose insn with least contribution to register pressure,
84 3. prefer in-block upon interblock motion, ties broken by
85 4. prefer useful upon speculative motion, ties broken by
86 5. choose insn with largest control flow probability, ties
88 6. choose insn with the least dependences upon the previously
89 scheduled insn, or finally
90 7. choose insn with lowest UID.
92 Memory references complicate matters. Only if we can be certain
93 that memory references are not part of the data dependency graph
94 (via true, anti, or output dependence), can we move operations past
95 memory references. To first approximation, reads can be done
96 independently, while writes introduce dependencies. Better
97 approximations will yield fewer dependencies.
99 Before reload, an extended analysis of interblock data dependences
100 is required for interblock scheduling. This is performed in
101 compute_block_backward_dependences ().
103 Dependencies set up by memory references are treated in exactly the
104 same way as other dependencies, by using LOG_LINKS backward
105 dependences. LOG_LINKS are translated into INSN_DEPEND forward
106 dependences for the purpose of forward list scheduling.
108 Having optimized the critical path, we may have also unduly
109 extended the lifetimes of some registers. If an operation requires
110 that constants be loaded into registers, it is certainly desirable
111 to load those constants as early as necessary, but no earlier.
112 I.e., it will not do to load up a bunch of registers at the
113 beginning of a basic block only to use them at the end, if they
114 could be loaded later, since this may result in excessive register
117 Note that since branches are never in basic blocks, but only end
118 basic blocks, this pass will not move branches. But that is ok,
119 since we can use GNU's delayed branch scheduling pass to take care
122 Also note that no further optimizations based on algebraic
123 identities are performed, so this pass would be a good one to
124 perform instruction splitting, such as breaking up a multiply
125 instruction into shifts and adds where that is profitable.
127 Given the memory aliasing analysis that this pass should perform,
128 it should be possible to remove redundant stores to memory, and to
129 load values from registers instead of hitting memory.
131 Before reload, speculative insns are moved only if a 'proof' exists
132 that no exception will be caused by this, and if no live registers
133 exist that inhibit the motion (live registers constraints are not
134 represented by data dependence edges).
136 This pass must update information that subsequent passes expect to
137 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
138 reg_n_calls_crossed, and reg_live_length. Also, basic_block_head,
141 The information in the line number notes is carefully retained by
142 this pass. Notes that refer to the starting and ending of
143 exception regions are also carefully retained by this pass. All
144 other NOTE insns are grouped in their same relative order at the
145 beginning of basic blocks and regions that have been scheduled.
147 The main entry point for this pass is schedule_insns(), called for
148 each function. The work of the scheduler is organized in three
149 levels: (1) function level: insns are subject to splitting,
150 control-flow-graph is constructed, regions are computed (after
151 reload, each region is of one block), (2) region level: control
152 flow graph attributes required for interblock scheduling are
153 computed (dominators, reachability, etc.), data dependences and
154 priorities are computed, and (3) block level: insns in the block
155 are actually scheduled. */
160 #include "basic-block.h"
162 #include "hard-reg-set.h"
164 #include "insn-config.h"
165 #include "insn-attr.h"
168 extern char *reg_known_equiv_p
;
169 extern rtx
*reg_known_value
;
171 #ifdef INSN_SCHEDULING
173 /* enable interblock scheduling code */
175 /* define INTERBLOCK_DEBUG for using the -fsched-max debugging facility */
176 /* #define INTERBLOCK_DEBUG */
178 /* target_units bitmask has 1 for each unit in the cpu. It should be
179 possible to compute this variable from the machine description.
180 But currently it is computed by examinning the insn list. Since
181 this is only needed for visualization, it seems an acceptable
182 solution. (For understanding the mapping of bits to units, see
183 definition of function_units[] in "insn-attrtab.c") */
185 static int target_units
= 0;
187 /* issue_rate is the number of insns that can be scheduled in the same
188 machine cycle. It can be defined in the config/mach/mach.h file,
189 otherwise we set it to 1. */
191 static int issue_rate
;
197 /* sched_debug_count is used for debugging the scheduler by limiting
198 the number of scheduled insns. It is controlled by the option
199 -fsched-max-N (N is a number).
201 sched-verbose controls the amount of debugging output the
202 scheduler prints. It is controlled by -fsched-verbose-N:
203 N>0 and no -DSR : the output is directed to stderr.
204 N>=10 will direct the printouts to stderr (regardless of -dSR).
206 N=2: bb's probabilities, detailed ready list info, unit/insn info.
207 N=3: rtl at abort point, control-flow, regions info.
208 N=5: dependences info.
210 max_rgn_blocks and max_region_insns limit region size for
211 interblock scheduling. They are controlled by
212 -fsched-interblock-max-blocks-N, -fsched-interblock-max-insns-N */
214 #define MAX_RGN_BLOCKS 10
215 #define MAX_RGN_INSNS 100
217 static int sched_debug_count
= -1;
218 static int sched_verbose_param
= 0;
219 static int sched_verbose
= 0;
220 static int max_rgn_blocks
= MAX_RGN_BLOCKS
;
221 static int max_rgn_insns
= MAX_RGN_INSNS
;
223 /* nr_inter/spec counts interblock/speculative motion for the function */
224 static int nr_inter
, nr_spec
;
227 /* debugging file. all printouts are sent to dump, which is always set,
228 either to stderr, or to the dump listing file (-dRS). */
229 static FILE *dump
= 0;
231 /* fix_sched_param() is called from toplev.c upon detection
232 of the -fsched-***-N options. */
235 fix_sched_param (param
, val
)
238 if (!strcmp (param
, "max"))
239 sched_debug_count
= ((sched_debug_count
== -1) ?
240 atoi (val
) : sched_debug_count
);
241 else if (!strcmp (param
, "verbose"))
242 sched_verbose_param
= atoi (val
);
243 else if (!strcmp (param
, "interblock-max-blocks"))
244 max_rgn_blocks
= atoi (val
);
245 else if (!strcmp (param
, "interblock-max-insns"))
246 max_rgn_insns
= atoi (val
);
248 warning ("fix_sched_param: unknown param: %s", param
);
252 /* Arrays set up by scheduling for the same respective purposes as
253 similar-named arrays set up by flow analysis. We work with these
254 arrays during the scheduling pass so we can compare values against
257 Values of these arrays are copied at the end of this pass into the
258 arrays set up by flow analysis. */
259 static int *sched_reg_n_calls_crossed
;
260 static int *sched_reg_live_length
;
261 static int *sched_reg_basic_block
;
263 /* We need to know the current block number during the post scheduling
264 update of live register information so that we can also update
265 REG_BASIC_BLOCK if a register changes blocks. */
266 static int current_block_num
;
268 /* Element N is the next insn that sets (hard or pseudo) register
269 N within the current basic block; or zero, if there is no
270 such insn. Needed for new registers which may be introduced
271 by splitting insns. */
272 static rtx
*reg_last_uses
;
273 static rtx
*reg_last_sets
;
274 static regset reg_pending_sets
;
275 static int reg_pending_sets_all
;
277 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
278 static int *insn_luid
;
279 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
281 /* Vector indexed by INSN_UID giving each instruction a priority. */
282 static int *insn_priority
;
283 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
285 static short *insn_costs
;
286 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
288 /* Vector indexed by INSN_UID giving an encoding of the function units
290 static short *insn_units
;
291 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
293 /* Vector indexed by INSN_UID giving each instruction a register-weight.
294 This weight is an estimation of the insn contribution to registers pressure. */
295 static int *insn_reg_weight
;
296 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
298 /* Vector indexed by INSN_UID giving list of insns which
299 depend upon INSN. Unlike LOG_LINKS, it represents forward dependences. */
300 static rtx
*insn_depend
;
301 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
303 /* Vector indexed by INSN_UID. Initialized to the number of incoming
304 edges in forward dependence graph (= number of LOG_LINKS). As
305 scheduling procedes, dependence counts are decreased. An
306 instruction moves to the ready list when its counter is zero. */
307 static int *insn_dep_count
;
308 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
310 /* Vector indexed by INSN_UID giving an encoding of the blockage range
311 function. The unit and the range are encoded. */
312 static unsigned int *insn_blockage
;
313 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
315 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
316 #define ENCODE_BLOCKAGE(U, R) \
317 ((((U) << UNIT_BITS) << BLOCKAGE_BITS \
318 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
319 | MAX_BLOCKAGE_COST (R))
320 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
321 #define BLOCKAGE_RANGE(B) \
322 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
323 | ((B) & BLOCKAGE_MASK))
325 /* Encodings of the `<name>_unit_blockage_range' function. */
326 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
327 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
329 #define DONE_PRIORITY -1
330 #define MAX_PRIORITY 0x7fffffff
331 #define TAIL_PRIORITY 0x7ffffffe
332 #define LAUNCH_PRIORITY 0x7f000001
333 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
334 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
336 /* Vector indexed by INSN_UID giving number of insns referring to this insn. */
337 static int *insn_ref_count
;
338 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
340 /* Vector indexed by INSN_UID giving line-number note in effect for each
341 insn. For line-number notes, this indicates whether the note may be
343 static rtx
*line_note
;
344 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
346 /* Vector indexed by basic block number giving the starting line-number
347 for each basic block. */
348 static rtx
*line_note_head
;
350 /* List of important notes we must keep around. This is a pointer to the
351 last element in the list. */
352 static rtx note_list
;
354 /* Regsets telling whether a given register is live or dead before the last
355 scheduled insn. Must scan the instructions once before scheduling to
356 determine what registers are live or dead at the end of the block. */
357 static regset bb_live_regs
;
359 /* Regset telling whether a given register is live after the insn currently
360 being scheduled. Before processing an insn, this is equal to bb_live_regs
361 above. This is used so that we can find registers that are newly born/dead
362 after processing an insn. */
363 static regset old_live_regs
;
365 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
366 during the initial scan and reused later. If there are not exactly as
367 many REG_DEAD notes in the post scheduled code as there were in the
368 prescheduled code then we trigger an abort because this indicates a bug. */
369 static rtx dead_notes
;
373 /* An instruction is ready to be scheduled when all insns preceding it
374 have already been scheduled. It is important to ensure that all
375 insns which use its result will not be executed until its result
376 has been computed. An insn is maintained in one of four structures:
378 (P) the "Pending" set of insns which cannot be scheduled until
379 their dependencies have been satisfied.
380 (Q) the "Queued" set of insns that can be scheduled when sufficient
382 (R) the "Ready" list of unscheduled, uncommitted insns.
383 (S) the "Scheduled" list of insns.
385 Initially, all insns are either "Pending" or "Ready" depending on
386 whether their dependencies are satisfied.
388 Insns move from the "Ready" list to the "Scheduled" list as they
389 are committed to the schedule. As this occurs, the insns in the
390 "Pending" list have their dependencies satisfied and move to either
391 the "Ready" list or the "Queued" set depending on whether
392 sufficient time has passed to make them ready. As time passes,
393 insns move from the "Queued" set to the "Ready" list. Insns may
394 move from the "Ready" list to the "Queued" set if they are blocked
395 due to a function unit conflict.
397 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
398 insns, i.e., those that are ready, queued, and pending.
399 The "Queued" set (Q) is implemented by the variable `insn_queue'.
400 The "Ready" list (R) is implemented by the variables `ready' and
402 The "Scheduled" list (S) is the new insn chain built by this pass.
404 The transition (R->S) is implemented in the scheduling loop in
405 `schedule_block' when the best insn to schedule is chosen.
406 The transition (R->Q) is implemented in `queue_insn' when an
407 insn is found to to have a function unit conflict with the already
409 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
410 insns move from the ready list to the scheduled list.
411 The transition (Q->R) is implemented in 'queue_to_insn' as time
412 passes or stalls are introduced. */
414 /* Implement a circular buffer to delay instructions until sufficient
415 time has passed. INSN_QUEUE_SIZE is a power of two larger than
416 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
417 longest time an isnsn may be queued. */
418 static rtx insn_queue
[INSN_QUEUE_SIZE
];
419 static int q_ptr
= 0;
420 static int q_size
= 0;
421 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
422 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
424 /* Vector indexed by INSN_UID giving the minimum clock tick at which
425 the insn becomes ready. This is used to note timing constraints for
426 insns in the pending list. */
427 static int *insn_tick
;
428 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
430 /* Data structure for keeping track of register information
431 during that register's life. */
440 /* Forward declarations. */
441 static void add_dependence
PROTO ((rtx
, rtx
, enum reg_note
));
442 static void remove_dependence
PROTO ((rtx
, rtx
));
443 static rtx find_insn_list
PROTO ((rtx
, rtx
));
444 static int insn_unit
PROTO ((rtx
));
445 static unsigned int blockage_range
PROTO ((int, rtx
));
446 static void clear_units
PROTO ((void));
447 static int actual_hazard_this_instance
PROTO ((int, int, rtx
, int, int));
448 static void schedule_unit
PROTO ((int, rtx
, int));
449 static int actual_hazard
PROTO ((int, rtx
, int, int));
450 static int potential_hazard
PROTO ((int, rtx
, int));
451 static int insn_cost
PROTO ((rtx
, rtx
, rtx
));
452 static int priority
PROTO ((rtx
));
453 static void free_pending_lists
PROTO ((void));
454 static void add_insn_mem_dependence
PROTO ((rtx
*, rtx
*, rtx
, rtx
));
455 static void flush_pending_lists
PROTO ((rtx
, int));
456 static void sched_analyze_1
PROTO ((rtx
, rtx
));
457 static void sched_analyze_2
PROTO ((rtx
, rtx
));
458 static void sched_analyze_insn
PROTO ((rtx
, rtx
, rtx
));
459 static void sched_analyze
PROTO ((rtx
, rtx
));
460 static void sched_note_set
PROTO ((rtx
, int));
461 static int rank_for_schedule
PROTO ((const GENERIC_PTR
, const GENERIC_PTR
));
462 static void swap_sort
PROTO ((rtx
*, int));
463 static void queue_insn
PROTO ((rtx
, int));
464 static int schedule_insn
PROTO ((rtx
, rtx
*, int, int));
465 static void create_reg_dead_note
PROTO ((rtx
, rtx
));
466 static void attach_deaths
PROTO ((rtx
, rtx
, int));
467 static void attach_deaths_insn
PROTO ((rtx
));
468 static int new_sometimes_live
PROTO ((struct sometimes
*, int, int));
469 static void finish_sometimes_live
PROTO ((struct sometimes
*, int));
470 static int schedule_block
PROTO ((int, int));
471 static rtx regno_use_in
PROTO ((int, rtx
));
472 static void split_hard_reg_notes
PROTO ((rtx
, rtx
, rtx
));
473 static void new_insn_dead_notes
PROTO ((rtx
, rtx
, rtx
, rtx
));
474 static void update_n_sets
PROTO ((rtx
, int));
475 static void update_flow_info
PROTO ((rtx
, rtx
, rtx
, rtx
));
476 static char *safe_concat
PROTO ((char *, char *, char *));
478 /* Main entry point of this file. */
479 void schedule_insns
PROTO ((FILE *));
481 /* Mapping of insns to their original block prior to scheduling. */
482 static int *insn_orig_block
;
483 #define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
485 /* Some insns (e.g. call) are not allowed to move across blocks. */
486 static char *cant_move
;
487 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
489 /* Control flow graph edges are kept in circular lists. */
498 static edge
*edge_table
;
500 #define NEXT_IN(edge) (edge_table[edge].next_in)
501 #define NEXT_OUT(edge) (edge_table[edge].next_out)
502 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
503 #define TO_BLOCK(edge) (edge_table[edge].to_block)
505 /* Number of edges in the control flow graph. (in fact larger than
506 that by 1, since edge 0 is unused.) */
509 /* Circular list of incoming/outgoing edges of a block */
510 static int *in_edges
;
511 static int *out_edges
;
513 #define IN_EDGES(block) (in_edges[block])
514 #define OUT_EDGES(block) (out_edges[block])
516 /* List of labels which cannot be deleted, needed for control
517 flow graph construction. */
518 extern rtx forced_labels
;
521 static int is_cfg_nonregular
PROTO ((void));
522 static int build_control_flow
PROTO ((int_list_ptr
*, int_list_ptr
*,
524 static void new_edge
PROTO ((int, int));
527 /* A region is the main entity for interblock scheduling: insns
528 are allowed to move between blocks in the same region, along
529 control flow graph edges, in the 'up' direction. */
532 int rgn_nr_blocks
; /* number of blocks in region */
533 int rgn_blocks
; /* blocks in the region (actually index in rgn_bb_table) */
537 /* Number of regions in the procedure */
538 static int nr_regions
;
540 /* Table of region descriptions */
541 static region
*rgn_table
;
543 /* Array of lists of regions' blocks */
544 static int *rgn_bb_table
;
546 /* Topological order of blocks in the region (if b2 is reachable from
547 b1, block_to_bb[b2] > block_to_bb[b1]).
548 Note: A basic block is always referred to by either block or b,
549 while its topological order name (in the region) is refered to by
552 static int *block_to_bb
;
554 /* The number of the region containing a block. */
555 static int *containing_rgn
;
557 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
558 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
559 #define BLOCK_TO_BB(block) (block_to_bb[block])
560 #define CONTAINING_RGN(block) (containing_rgn[block])
562 void debug_regions
PROTO ((void));
563 static void find_single_block_region
PROTO ((void));
564 static void find_rgns
PROTO ((int_list_ptr
*, int_list_ptr
*,
565 int *, int *, sbitmap
*));
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_prisky
PROTO ((rtx
, int, int));
719 static int is_exception_free
PROTO ((rtx
, int, int));
721 static char find_insn_mem_list
PROTO ((rtx
, rtx
, rtx
, rtx
));
722 static void compute_block_forward_dependences
PROTO ((int));
723 static void init_rgn_data_dependences
PROTO ((int));
724 static void add_branch_dependences
PROTO ((rtx
, rtx
));
725 static void compute_block_backward_dependences
PROTO ((int));
726 void debug_dependencies
PROTO ((void));
728 /* Notes handling mechanism:
729 =========================
730 Generally, NOTES are saved before scheduling and restored after scheduling.
731 The scheduler distinguishes between three types of notes:
733 (1) LINE_NUMBER notes, generated and used for debugging. Here,
734 before scheduling a region, a pointer to the LINE_NUMBER note is
735 added to the insn following it (in save_line_notes()), and the note
736 is removed (in rm_line_notes() and unlink_line_notes()). After
737 scheduling the region, this pointer is used for regeneration of
738 the LINE_NUMBER note (in restore_line_notes()).
740 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
741 Before scheduling a region, a pointer to the note is added to the insn
742 that follows or precedes it. (This happens as part of the data dependence
743 computation). After scheduling an insn, the pointer contained in it is
744 used for regenerating the corresponding note (in reemit_notes).
746 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
747 these notes are put in a list (in rm_other_notes() and
748 unlink_other_notes ()). After scheduling the block, these notes are
749 inserted at the beginning of the block (in schedule_block()). */
751 static rtx unlink_other_notes
PROTO ((rtx
, rtx
));
752 static rtx unlink_line_notes
PROTO ((rtx
, rtx
));
753 static void rm_line_notes
PROTO ((int));
754 static void save_line_notes
PROTO ((int));
755 static void restore_line_notes
PROTO ((int));
756 static void rm_redundant_line_notes
PROTO ((void));
757 static void rm_other_notes
PROTO ((rtx
, rtx
));
758 static rtx reemit_notes
PROTO ((rtx
, rtx
));
760 static void get_block_head_tail
PROTO ((int, rtx
*, rtx
*));
762 static void find_pre_sched_live
PROTO ((int));
763 static void find_post_sched_live
PROTO ((int));
764 static void update_reg_usage
PROTO ((void));
765 static int queue_to_ready
PROTO ((rtx
[], int));
767 void debug_ready_list
PROTO ((rtx
[], int));
768 static void init_target_units
PROTO (());
769 static void insn_print_units
PROTO ((rtx
));
770 static int get_visual_tbl_length
PROTO (());
771 static void init_block_visualization
PROTO (());
772 static void print_block_visualization
PROTO ((int, char *));
773 static void visualize_scheduled_insns
PROTO ((int, int));
774 static void visualize_no_unit
PROTO ((rtx
));
775 static void visualize_stall_cycles
PROTO ((int, int));
776 static void print_exp
PROTO ((char *, rtx
, int));
777 static void print_value
PROTO ((char *, rtx
, int));
778 static void print_pattern
PROTO ((char *, rtx
, int));
779 static void print_insn
PROTO ((char *, rtx
, int));
780 void debug_reg_vector
PROTO ((regset
));
782 static rtx move_insn1
PROTO ((rtx
, rtx
));
783 static rtx move_insn
PROTO ((rtx
, rtx
));
784 static rtx group_leader
PROTO ((rtx
));
785 static int set_priorities
PROTO ((int));
786 static void init_rtx_vector
PROTO ((rtx
**, rtx
*, int, int));
787 static void schedule_region
PROTO ((int));
788 static void split_block_insns
PROTO ((int));
790 #endif /* INSN_SCHEDULING */
792 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
794 /* Helper functions for instruction scheduling. */
796 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
797 static rtx unused_insn_list
;
799 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
800 static rtx unused_expr_list
;
802 static void free_list
PROTO ((rtx
*, rtx
*));
803 static rtx alloc_INSN_LIST
PROTO ((rtx
, rtx
));
804 static rtx alloc_EXPR_LIST
PROTO ((int, rtx
, rtx
));
807 free_list (listp
, unused_listp
)
808 rtx
*listp
, *unused_listp
;
810 register rtx link
, prev_link
;
816 link
= XEXP (prev_link
, 1);
821 link
= XEXP (link
, 1);
824 XEXP (prev_link
, 1) = *unused_listp
;
825 *unused_listp
= *listp
;
830 alloc_INSN_LIST (val
, next
)
835 if (unused_insn_list
)
837 r
= unused_insn_list
;
838 unused_insn_list
= XEXP (r
, 1);
841 PUT_REG_NOTE_KIND (r
, VOIDmode
);
844 r
= gen_rtx_INSN_LIST (VOIDmode
, val
, next
);
850 alloc_EXPR_LIST (kind
, val
, next
)
856 if (unused_insn_list
)
858 r
= unused_insn_list
;
859 unused_insn_list
= XEXP (r
, 1);
862 PUT_REG_NOTE_KIND (r
, kind
);
865 r
= gen_rtx_EXPR_LIST (kind
, val
, next
);
870 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
871 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
872 of dependence that this link represents. */
875 add_dependence (insn
, elem
, dep_type
)
878 enum reg_note dep_type
;
882 /* Don't depend an insn on itself. */
886 /* If elem is part of a sequence that must be scheduled together, then
887 make the dependence point to the last insn of the sequence.
888 When HAVE_cc0, it is possible for NOTEs to exist between users and
889 setters of the condition codes, so we must skip past notes here.
890 Otherwise, NOTEs are impossible here. */
892 next
= NEXT_INSN (elem
);
895 while (next
&& GET_CODE (next
) == NOTE
)
896 next
= NEXT_INSN (next
);
899 if (next
&& SCHED_GROUP_P (next
)
900 && GET_CODE (next
) != CODE_LABEL
)
902 /* Notes will never intervene here though, so don't bother checking
904 /* We must reject CODE_LABELs, so that we don't get confused by one
905 that has LABEL_PRESERVE_P set, which is represented by the same
906 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
908 while (NEXT_INSN (next
) && SCHED_GROUP_P (NEXT_INSN (next
))
909 && GET_CODE (NEXT_INSN (next
)) != CODE_LABEL
)
910 next
= NEXT_INSN (next
);
912 /* Again, don't depend an insn on itself. */
916 /* Make the dependence to NEXT, the last insn of the group, instead
917 of the original ELEM. */
921 #ifdef INSN_SCHEDULING
922 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
923 No need for interblock dependences with calls, since
924 calls are not moved between blocks. Note: the edge where
925 elem is a CALL is still required. */
926 if (GET_CODE (insn
) == CALL_INSN
927 && (INSN_BB (elem
) != INSN_BB (insn
)))
932 /* Check that we don't already have this dependence. */
933 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
934 if (XEXP (link
, 0) == elem
)
936 /* If this is a more restrictive type of dependence than the existing
937 one, then change the existing dependence to this type. */
938 if ((int) dep_type
< (int) REG_NOTE_KIND (link
))
939 PUT_REG_NOTE_KIND (link
, dep_type
);
942 /* Might want to check one level of transitivity to save conses. */
944 link
= alloc_INSN_LIST (elem
, LOG_LINKS (insn
));
945 LOG_LINKS (insn
) = link
;
947 /* Insn dependency, not data dependency. */
948 PUT_REG_NOTE_KIND (link
, dep_type
);
951 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
952 of INSN. Abort if not found. */
955 remove_dependence (insn
, elem
)
959 rtx prev
, link
, next
;
962 for (prev
= 0, link
= LOG_LINKS (insn
); link
; link
= next
)
964 next
= XEXP (link
, 1);
965 if (XEXP (link
, 0) == elem
)
968 XEXP (prev
, 1) = next
;
970 LOG_LINKS (insn
) = next
;
972 XEXP (link
, 1) = unused_insn_list
;
973 unused_insn_list
= link
;
986 #ifndef INSN_SCHEDULING
988 schedule_insns (dump_file
)
997 /* Computation of memory dependencies. */
999 /* The *_insns and *_mems are paired lists. Each pending memory operation
1000 will have a pointer to the MEM rtx on one list and a pointer to the
1001 containing insn on the other list in the same place in the list. */
1003 /* We can't use add_dependence like the old code did, because a single insn
1004 may have multiple memory accesses, and hence needs to be on the list
1005 once for each memory access. Add_dependence won't let you add an insn
1006 to a list more than once. */
1008 /* An INSN_LIST containing all insns with pending read operations. */
1009 static rtx pending_read_insns
;
1011 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
1012 static rtx pending_read_mems
;
1014 /* An INSN_LIST containing all insns with pending write operations. */
1015 static rtx pending_write_insns
;
1017 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
1018 static rtx pending_write_mems
;
1020 /* Indicates the combined length of the two pending lists. We must prevent
1021 these lists from ever growing too large since the number of dependencies
1022 produced is at least O(N*N), and execution time is at least O(4*N*N), as
1023 a function of the length of these pending lists. */
1025 static int pending_lists_length
;
1027 /* The last insn upon which all memory references must depend.
1028 This is an insn which flushed the pending lists, creating a dependency
1029 between it and all previously pending memory references. This creates
1030 a barrier (or a checkpoint) which no memory reference is allowed to cross.
1032 This includes all non constant CALL_INSNs. When we do interprocedural
1033 alias analysis, this restriction can be relaxed.
1034 This may also be an INSN that writes memory if the pending lists grow
1037 static rtx last_pending_memory_flush
;
1039 /* The last function call we have seen. All hard regs, and, of course,
1040 the last function call, must depend on this. */
1042 static rtx last_function_call
;
1044 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
1045 that does not already cross a call. We create dependencies between each
1046 of those insn and the next call insn, to ensure that they won't cross a call
1047 after scheduling is done. */
1049 static rtx sched_before_next_call
;
1051 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1052 so that insns independent of the last scheduled insn will be preferred
1053 over dependent instructions. */
1055 static rtx last_scheduled_insn
;
1057 /* Data structures for the computation of data dependences in a regions. We
1058 keep one copy of each of the declared above variables for each bb in the
1059 region. Before analyzing the data dependences for a bb, its variables
1060 are initialized as a function of the variables of its predecessors. When
1061 the analysis for a bb completes, we save the contents of each variable X
1062 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
1063 copied to bb_pending_read_insns[bb]. Another change is that few
1064 variables are now a list of insns rather than a single insn:
1065 last_pending_memory_flash, last_function_call, reg_last_sets. The
1066 manipulation of these variables was changed appropriately. */
1068 static rtx
**bb_reg_last_uses
;
1069 static rtx
**bb_reg_last_sets
;
1071 static rtx
*bb_pending_read_insns
;
1072 static rtx
*bb_pending_read_mems
;
1073 static rtx
*bb_pending_write_insns
;
1074 static rtx
*bb_pending_write_mems
;
1075 static int *bb_pending_lists_length
;
1077 static rtx
*bb_last_pending_memory_flush
;
1078 static rtx
*bb_last_function_call
;
1079 static rtx
*bb_sched_before_next_call
;
1081 /* functions for construction of the control flow graph. */
1083 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1085 We decide not to build the control flow graph if there is possibly more
1086 than one entry to the function, if computed branches exist, of if we
1087 have nonlocal gotos. */
1090 is_cfg_nonregular ()
1096 /* If we have a label that could be the target of a nonlocal goto, then
1097 the cfg is not well structured. */
1098 if (nonlocal_label_rtx_list () != NULL
)
1101 /* If we have any forced labels, then the cfg is not well structured. */
1105 /* If this function has a computed jump, then we consider the cfg
1106 not well structured. */
1107 if (current_function_has_computed_jump
)
1110 /* If we have exception handlers, then we consider the cfg not well
1111 structured. ?!? We should be able to handle this now that flow.c
1112 computes an accurate cfg for EH. */
1113 if (exception_handler_labels
)
1116 /* If we have non-jumping insns which refer to labels, then we consider
1117 the cfg not well structured. */
1118 /* check for labels referred to other thn by jumps */
1119 for (b
= 0; b
< n_basic_blocks
; b
++)
1120 for (insn
= basic_block_head
[b
];; insn
= NEXT_INSN (insn
))
1122 code
= GET_CODE (insn
);
1123 if (GET_RTX_CLASS (code
) == 'i')
1127 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1128 if (REG_NOTE_KIND (note
) == REG_LABEL
)
1132 if (insn
== basic_block_end
[b
])
1136 /* All the tests passed. Consider the cfg well structured. */
1140 /* Build the control flow graph and set nr_edges.
1142 Instead of trying to build a cfg ourselves, we rely on flow to
1143 do it for us. Stamp out useless code (and bug) duplication.
1145 Return nonzero if an irregularity in the cfg is found which would
1146 prevent cross block scheduling. */
1149 build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
)
1150 int_list_ptr
*s_preds
;
1151 int_list_ptr
*s_succs
;
1159 /* Count the number of edges in the cfg. */
1162 for (i
= 0; i
< n_basic_blocks
; i
++)
1164 nr_edges
+= num_succs
[i
];
1165 /* ??? We must also detect unreachable loops here. We only handle the
1166 trivial case of a loop with one basic block for now. */
1167 if (num_preds
[i
] == 0
1168 || (num_preds
[i
] == 1 && INT_LIST_VAL (s_preds
[i
]) == i
))
1172 /* Account for entry/exit edges. */
1175 in_edges
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
1176 out_edges
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
1177 bzero ((char *) in_edges
, n_basic_blocks
* sizeof (int));
1178 bzero ((char *) out_edges
, n_basic_blocks
* sizeof (int));
1180 edge_table
= (edge
*) xmalloc ((nr_edges
) * sizeof (edge
));
1181 bzero ((char *) edge_table
, ((nr_edges
) * sizeof (edge
)));
1184 for (i
= 0; i
< n_basic_blocks
; i
++)
1185 for (succ
= s_succs
[i
]; succ
; succ
= succ
->next
)
1187 if (INT_LIST_VAL (succ
) != EXIT_BLOCK
)
1188 new_edge (i
, INT_LIST_VAL (succ
));
1191 /* increment by 1, since edge 0 is unused. */
1198 /* Record an edge in the control flow graph from SOURCE to TARGET.
1200 In theory, this is redundant with the s_succs computed above, but
1201 we have not converted all of haifa to use information from the
1205 new_edge (source
, target
)
1209 int curr_edge
, fst_edge
;
1211 /* check for duplicates */
1212 fst_edge
= curr_edge
= OUT_EDGES (source
);
1215 if (FROM_BLOCK (curr_edge
) == source
1216 && TO_BLOCK (curr_edge
) == target
)
1221 curr_edge
= NEXT_OUT (curr_edge
);
1223 if (fst_edge
== curr_edge
)
1229 FROM_BLOCK (e
) = source
;
1230 TO_BLOCK (e
) = target
;
1232 if (OUT_EDGES (source
))
1234 next_edge
= NEXT_OUT (OUT_EDGES (source
));
1235 NEXT_OUT (OUT_EDGES (source
)) = e
;
1236 NEXT_OUT (e
) = next_edge
;
1240 OUT_EDGES (source
) = e
;
1244 if (IN_EDGES (target
))
1246 next_edge
= NEXT_IN (IN_EDGES (target
));
1247 NEXT_IN (IN_EDGES (target
)) = e
;
1248 NEXT_IN (e
) = next_edge
;
1252 IN_EDGES (target
) = e
;
1258 /* BITSET macros for operations on the control flow graph. */
1260 /* Compute bitwise union of two bitsets. */
1261 #define BITSET_UNION(set1, set2, len) \
1262 do { register bitset tp = set1, sp = set2; \
1264 for (i = 0; i < len; i++) \
1265 *(tp++) |= *(sp++); } while (0)
1267 /* Compute bitwise intersection of two bitsets. */
1268 #define BITSET_INTER(set1, set2, len) \
1269 do { register bitset tp = set1, sp = set2; \
1271 for (i = 0; i < len; i++) \
1272 *(tp++) &= *(sp++); } while (0)
1274 /* Compute bitwise difference of two bitsets. */
1275 #define BITSET_DIFFER(set1, set2, len) \
1276 do { register bitset tp = set1, sp = set2; \
1278 for (i = 0; i < len; i++) \
1279 *(tp++) &= ~*(sp++); } while (0)
1281 /* Inverts every bit of bitset 'set' */
1282 #define BITSET_INVERT(set, len) \
1283 do { register bitset tmpset = set; \
1285 for (i = 0; i < len; i++, tmpset++) \
1286 *tmpset = ~*tmpset; } while (0)
1288 /* Turn on the index'th bit in bitset set. */
1289 #define BITSET_ADD(set, index, len) \
1291 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1294 set[index/HOST_BITS_PER_WIDE_INT] |= \
1295 1 << (index % HOST_BITS_PER_WIDE_INT); \
1298 /* Turn off the index'th bit in set. */
1299 #define BITSET_REMOVE(set, index, len) \
1301 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1304 set[index/HOST_BITS_PER_WIDE_INT] &= \
1305 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1309 /* Check if the index'th bit in bitset set is on. */
1312 bitset_member (set
, index
, len
)
1316 if (index
>= HOST_BITS_PER_WIDE_INT
* len
)
1318 return (set
[index
/ HOST_BITS_PER_WIDE_INT
] &
1319 1 << (index
% HOST_BITS_PER_WIDE_INT
)) ? 1 : 0;
1323 /* Translate a bit-set SET to a list BL of the bit-set members. */
1326 extract_bitlst (set
, len
, bl
)
1332 unsigned HOST_WIDE_INT word
;
1334 /* bblst table space is reused in each call to extract_bitlst */
1335 bitlst_table_last
= 0;
1337 bl
->first_member
= &bitlst_table
[bitlst_table_last
];
1340 for (i
= 0; i
< len
; i
++)
1343 offset
= i
* HOST_BITS_PER_WIDE_INT
;
1344 for (j
= 0; word
; j
++)
1348 bitlst_table
[bitlst_table_last
++] = offset
;
1359 /* functions for the construction of regions */
1361 /* Print the regions, for debugging purposes. Callable from debugger. */
1368 fprintf (dump
, "\n;; ------------ REGIONS ----------\n\n");
1369 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
1371 fprintf (dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
1372 rgn_table
[rgn
].rgn_nr_blocks
);
1373 fprintf (dump
, ";;\tbb/block: ");
1375 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
1377 current_blocks
= RGN_BLOCKS (rgn
);
1379 if (bb
!= BLOCK_TO_BB (BB_TO_BLOCK (bb
)))
1382 fprintf (dump
, " %d/%d ", bb
, BB_TO_BLOCK (bb
));
1385 fprintf (dump
, "\n\n");
1390 /* Build a single block region for each basic block in the function.
1391 This allows for using the same code for interblock and basic block
1395 find_single_block_region ()
1399 for (i
= 0; i
< n_basic_blocks
; i
++)
1401 rgn_bb_table
[i
] = i
;
1402 RGN_NR_BLOCKS (i
) = 1;
1404 CONTAINING_RGN (i
) = i
;
1405 BLOCK_TO_BB (i
) = 0;
1407 nr_regions
= n_basic_blocks
;
1411 /* Update number of blocks and the estimate for number of insns
1412 in the region. Return 1 if the region is "too large" for interblock
1413 scheduling (compile time considerations), otherwise return 0. */
1416 too_large (block
, num_bbs
, num_insns
)
1417 int block
, *num_bbs
, *num_insns
;
1420 (*num_insns
) += (INSN_LUID (basic_block_end
[block
]) -
1421 INSN_LUID (basic_block_head
[block
]));
1422 if ((*num_bbs
> max_rgn_blocks
) || (*num_insns
> max_rgn_insns
))
1429 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1430 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1431 loop containing blk. */
1432 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1434 if (max_hdr[blk] == -1) \
1435 max_hdr[blk] = hdr; \
1436 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1437 RESET_BIT (inner, hdr); \
1438 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1440 RESET_BIT (inner,max_hdr[blk]); \
1441 max_hdr[blk] = hdr; \
1446 /* Find regions for interblock scheduling.
1448 A region for scheduling can be:
1450 * A loop-free procedure, or
1452 * A reducible inner loop, or
1454 * A basic block not contained in any other region.
1457 ?!? In theory we could build other regions based on extended basic
1458 blocks or reverse extended basic blocks. Is it worth the trouble?
1460 Loop blocks that form a region are put into the region's block list
1461 in topological order.
1463 This procedure stores its results into the following global (ick) variables
1472 We use dominator relationships to avoid making regions out of non-reducible
1475 This procedure needs to be converted to work on pred/succ lists instead
1476 of edge tables. That would simplify it somewhat. */
1479 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
)
1480 int_list_ptr
*s_preds
;
1481 int_list_ptr
*s_succs
;
1486 int *max_hdr
, *dfs_nr
, *stack
, *queue
, *degree
;
1488 int node
, child
, loop_head
, i
, j
, head
, tail
;
1489 int count
= 0, sp
, idx
= 0, current_edge
= out_edges
[0];
1490 int num_bbs
, num_insns
;
1491 int too_large_failure
;
1493 /* Note if an edge has been passed. */
1496 /* Note if a block is a natural loop header. */
1499 /* Note if a block is an natural inner loop header. */
1502 /* Note if a block is in the block queue. */
1505 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1506 and a mapping from block to its loop header (if the block is contained
1507 in a loop, else -1).
1509 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1510 be used as inputs to the second traversal.
1512 STACK, SP and DFS_NR are only used during the first traversal. */
1514 /* Allocate and initialize variables for the first traversal. */
1515 max_hdr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1516 dfs_nr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1517 bzero ((char *) dfs_nr
, n_basic_blocks
* sizeof (int));
1518 stack
= (int *) alloca (nr_edges
* sizeof (int));
1520 inner
= sbitmap_alloc (n_basic_blocks
);
1521 sbitmap_ones (inner
);
1523 header
= sbitmap_alloc (n_basic_blocks
);
1524 sbitmap_zero (header
);
1526 passed
= sbitmap_alloc (nr_edges
);
1527 sbitmap_zero (passed
);
1529 in_queue
= sbitmap_alloc (n_basic_blocks
);
1530 sbitmap_zero (in_queue
);
1532 for (i
= 0; i
< n_basic_blocks
; i
++)
1535 /* DFS traversal to find inner loops in the cfg. */
1540 if (current_edge
== 0 || TEST_BIT (passed
, current_edge
))
1542 /* We have reached a leaf node or a node that was already
1543 proc4essed. Pop edges off the stack until we find
1544 an edge that has not yet been processed. */
1546 && (current_edge
== 0 || TEST_BIT (passed
, current_edge
)))
1548 /* Pop entry off the stack. */
1549 current_edge
= stack
[sp
--];
1550 node
= FROM_BLOCK (current_edge
);
1551 child
= TO_BLOCK (current_edge
);
1552 if (max_hdr
[child
] >= 0 && TEST_BIT (dom
[node
], max_hdr
[child
]))
1553 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1554 current_edge
= NEXT_OUT (current_edge
);
1557 /* See if have finished the DFS tree traversal. */
1558 if (sp
< 0 && TEST_BIT (passed
, current_edge
))
1561 /* Nope, continue the traversal with the popped node. */
1565 /* Process a node. */
1566 node
= FROM_BLOCK (current_edge
);
1567 child
= TO_BLOCK (current_edge
);
1568 dfs_nr
[node
] = ++count
;
1570 /* If the successor block dominates the current block, then
1571 we've found a natural loop, record the header block for
1572 future reference. */
1573 if (TEST_BIT (dom
[node
], child
))
1576 SET_BIT (header
, child
);
1577 UPDATE_LOOP_RELATIONS (node
, child
);
1578 SET_BIT (passed
, current_edge
);
1579 current_edge
= NEXT_OUT (current_edge
);
1583 /* If the child was already visited, then there is no need to visit
1584 it again. Just update the loop relationships and restart
1588 if (max_hdr
[child
] >= 0 && TEST_BIT (dom
[node
], max_hdr
[child
]))
1589 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1590 SET_BIT (passed
, current_edge
);
1591 current_edge
= NEXT_OUT (current_edge
);
1595 /* Push an entry on the stack and continue DFS traversal. */
1596 stack
[++sp
] = current_edge
;
1597 SET_BIT (passed
, current_edge
);
1598 current_edge
= OUT_EDGES (child
);
1601 /* ?!? This might be a good place to detect unreachable loops and
1602 avoid problems with them by forcing single block scheduling. */
1604 SET_BIT (header
, 0);
1606 /* Second travsersal:find reducible inner loops and topologically sort
1607 block of each region. */
1609 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1610 to hold degree counts. */
1613 /* Compute the in-degree of every block in the graph */
1614 for (i
= 0; i
< n_basic_blocks
; i
++)
1615 degree
[i
] = num_preds
[i
];
1617 queue
= (int *) alloca (n_basic_blocks
* sizeof (int));
1619 /* Find blocks which are inner loop headers. */
1620 for (i
= 0; i
< n_basic_blocks
; i
++)
1622 if (TEST_BIT (header
, i
) && TEST_BIT (inner
, i
))
1626 /* I is a header of a reducible inner loop, or block 0 in a
1627 subroutine with no loops at all. */
1629 too_large_failure
= 0;
1630 loop_head
= max_hdr
[i
];
1632 /* Decrease degree of all I's successors for topological
1634 for (ps
= s_succs
[i
]; ps
; ps
= ps
->next
)
1635 if (INT_LIST_VAL (ps
) != EXIT_BLOCK
1636 && INT_LIST_VAL (ps
) != ENTRY_BLOCK
)
1637 --degree
[INT_LIST_VAL (ps
)];
1639 /* Estimate # insns, and count # blocks in the region. */
1642 = INSN_LUID (basic_block_end
[i
]) - INSN_LUID (basic_block_head
[i
]);
1645 /* Find all loop latches (blocks which back edges to the loop
1646 header) or all the leaf blocks in the cfg has no loops.
1648 Place those blocks into the queue. */
1651 for (j
= 0; j
< n_basic_blocks
; j
++)
1652 if (num_succs
[j
] == 0)
1655 SET_BIT (in_queue
, j
);
1657 if (too_large (j
, &num_bbs
, &num_insns
))
1659 too_large_failure
= 1;
1668 for (ps
= s_preds
[i
]; ps
; ps
= ps
->next
)
1670 node
= INT_LIST_VAL (ps
);
1672 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
)
1675 if (max_hdr
[node
] == loop_head
&& node
!= i
)
1677 /* This is a loop latch. */
1678 queue
[++tail
] = node
;
1679 SET_BIT (in_queue
, node
);
1681 if (too_large (node
, &num_bbs
, &num_insns
))
1683 too_large_failure
= 1;
1691 /* Now add all the blocks in the loop to the queue.
1693 We know the loop is a natural loop; however the algorithm
1694 above will not always mark certain blocks as being in the
1703 The algorithm in the DFS traversal may not mark B & D as part
1704 of the loop (ie they will not have max_hdr set to A).
1706 We know they can not be loop latches (else they would have
1707 had max_hdr set since they'd have a backedge to a dominator
1708 block). So we don't need them on the initial queue.
1710 We know they are part of the loop because they are dominated
1711 by the loop header and can be reached by a backwards walk of
1712 the edges starting with nodes on the initial queue.
1714 It is safe and desirable to include those nodes in the
1715 loop/scheduling region. To do so we would need to decrease
1716 the degree of a node if it is the target of a backedge
1717 within the loop itself as the node is placed in the queue.
1719 We do not do this because I'm not sure that the actual
1720 scheduling code will properly handle this case. ?!? */
1722 while (head
< tail
&& !too_large_failure
)
1725 child
= queue
[++head
];
1727 for (ps
= s_preds
[child
]; ps
; ps
= ps
->next
)
1729 node
= INT_LIST_VAL (ps
);
1731 /* See discussion above about nodes not marked as in
1732 this loop during the initial DFS traversal. */
1733 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
1734 || max_hdr
[node
] != loop_head
)
1739 else if (!TEST_BIT (in_queue
, node
) && node
!= i
)
1741 queue
[++tail
] = node
;
1742 SET_BIT (in_queue
, node
);
1744 if (too_large (node
, &num_bbs
, &num_insns
))
1746 too_large_failure
= 1;
1753 if (tail
>= 0 && !too_large_failure
)
1755 /* Place the loop header into list of region blocks. */
1757 rgn_bb_table
[idx
] = i
;
1758 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1759 RGN_BLOCKS (nr_regions
) = idx
++;
1760 CONTAINING_RGN (i
) = nr_regions
;
1761 BLOCK_TO_BB (i
) = count
= 0;
1763 /* Remove blocks from queue[] when their in degree becomes
1764 zero. Repeat until no blocks are left on the list. This
1765 produces a topological list of blocks in the region. */
1772 child
= queue
[head
];
1773 if (degree
[child
] == 0)
1776 rgn_bb_table
[idx
++] = child
;
1777 BLOCK_TO_BB (child
) = ++count
;
1778 CONTAINING_RGN (child
) = nr_regions
;
1779 queue
[head
] = queue
[tail
--];
1781 for (ps
= s_succs
[child
]; ps
; ps
= ps
->next
)
1782 if (INT_LIST_VAL (ps
) != ENTRY_BLOCK
1783 && INT_LIST_VAL (ps
) != EXIT_BLOCK
)
1784 --degree
[INT_LIST_VAL (ps
)];
1794 /* Any block that did not end up in a region is placed into a region
1796 for (i
= 0; i
< n_basic_blocks
; i
++)
1799 rgn_bb_table
[idx
] = i
;
1800 RGN_NR_BLOCKS (nr_regions
) = 1;
1801 RGN_BLOCKS (nr_regions
) = idx
++;
1802 CONTAINING_RGN (i
) = nr_regions
++;
1803 BLOCK_TO_BB (i
) = 0;
1813 /* functions for regions scheduling information */
1815 /* Compute dominators, probability, and potential-split-edges of bb.
1816 Assume that these values were already computed for bb's predecessors. */
1819 compute_dom_prob_ps (bb
)
1822 int nxt_in_edge
, fst_in_edge
, pred
;
1823 int fst_out_edge
, nxt_out_edge
, nr_out_edges
, nr_rgn_out_edges
;
1826 if (IS_RGN_ENTRY (bb
))
1828 BITSET_ADD (dom
[bb
], 0, bbset_size
);
1833 fst_in_edge
= nxt_in_edge
= IN_EDGES (BB_TO_BLOCK (bb
));
1835 /* intialize dom[bb] to '111..1' */
1836 BITSET_INVERT (dom
[bb
], bbset_size
);
1840 pred
= FROM_BLOCK (nxt_in_edge
);
1841 BITSET_INTER (dom
[bb
], dom
[BLOCK_TO_BB (pred
)], bbset_size
);
1843 BITSET_UNION (ancestor_edges
[bb
], ancestor_edges
[BLOCK_TO_BB (pred
)],
1846 BITSET_ADD (ancestor_edges
[bb
], EDGE_TO_BIT (nxt_in_edge
), edgeset_size
);
1849 nr_rgn_out_edges
= 0;
1850 fst_out_edge
= OUT_EDGES (pred
);
1851 nxt_out_edge
= NEXT_OUT (fst_out_edge
);
1852 BITSET_UNION (pot_split
[bb
], pot_split
[BLOCK_TO_BB (pred
)],
1855 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (fst_out_edge
), edgeset_size
);
1857 /* the successor doesn't belong the region? */
1858 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge
)) !=
1859 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1862 while (fst_out_edge
!= nxt_out_edge
)
1865 /* the successor doesn't belong the region? */
1866 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge
)) !=
1867 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1869 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (nxt_out_edge
), edgeset_size
);
1870 nxt_out_edge
= NEXT_OUT (nxt_out_edge
);
1874 /* now nr_rgn_out_edges is the number of region-exit edges from pred,
1875 and nr_out_edges will be the number of pred out edges not leaving
1877 nr_out_edges
-= nr_rgn_out_edges
;
1878 if (nr_rgn_out_edges
> 0)
1879 prob
[bb
] += 0.9 * prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1881 prob
[bb
] += prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1882 nxt_in_edge
= NEXT_IN (nxt_in_edge
);
1884 while (fst_in_edge
!= nxt_in_edge
);
1886 BITSET_ADD (dom
[bb
], bb
, bbset_size
);
1887 BITSET_DIFFER (pot_split
[bb
], ancestor_edges
[bb
], edgeset_size
);
1889 if (sched_verbose
>= 2)
1890 fprintf (dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
), (int) (100.0 * prob
[bb
]));
1891 } /* compute_dom_prob_ps */
1893 /* functions for target info */
1895 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1896 Note that bb_trg dominates bb_src. */
1899 split_edges (bb_src
, bb_trg
, bl
)
1904 int es
= edgeset_size
;
1905 edgeset src
= (edgeset
) alloca (es
* sizeof (HOST_WIDE_INT
));
1908 src
[es
] = (pot_split
[bb_src
])[es
];
1909 BITSET_DIFFER (src
, pot_split
[bb_trg
], edgeset_size
);
1910 extract_bitlst (src
, edgeset_size
, bl
);
1914 /* Find the valid candidate-source-blocks for the target block TRG, compute
1915 their probability, and check if they are speculative or not.
1916 For speculative sources, compute their update-blocks and split-blocks. */
1919 compute_trg_info (trg
)
1922 register candidate
*sp
;
1924 int check_block
, update_idx
;
1925 int i
, j
, k
, fst_edge
, nxt_edge
;
1927 /* define some of the fields for the target bb as well */
1928 sp
= candidate_table
+ trg
;
1930 sp
->is_speculative
= 0;
1933 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1935 sp
= candidate_table
+ i
;
1937 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1940 sp
->src_prob
= GET_SRC_PROB (i
, trg
);
1941 sp
->is_valid
= (sp
->src_prob
>= MIN_PROBABILITY
);
1946 split_edges (i
, trg
, &el
);
1947 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1948 if (sp
->is_speculative
&& !flag_schedule_speculative
)
1954 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
1955 sp
->split_bbs
.nr_members
= el
.nr_members
;
1956 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
1957 bblst_table
[bblst_last
] =
1958 TO_BLOCK (rgn_edges
[el
.first_member
[j
]]);
1959 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
1961 for (j
= 0; j
< el
.nr_members
; j
++)
1963 check_block
= FROM_BLOCK (rgn_edges
[el
.first_member
[j
]]);
1964 fst_edge
= nxt_edge
= OUT_EDGES (check_block
);
1967 for (k
= 0; k
< el
.nr_members
; k
++)
1968 if (EDGE_TO_BIT (nxt_edge
) == el
.first_member
[k
])
1971 if (k
>= el
.nr_members
)
1973 bblst_table
[bblst_last
++] = TO_BLOCK (nxt_edge
);
1977 nxt_edge
= NEXT_OUT (nxt_edge
);
1979 while (fst_edge
!= nxt_edge
);
1981 sp
->update_bbs
.nr_members
= update_idx
;
1986 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
1988 sp
->is_speculative
= 0;
1992 } /* compute_trg_info */
1995 /* Print candidates info, for debugging purposes. Callable from debugger. */
2001 if (!candidate_table
[i
].is_valid
)
2004 if (candidate_table
[i
].is_speculative
)
2007 fprintf (dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
2009 fprintf (dump
, "split path: ");
2010 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
2012 int b
= candidate_table
[i
].split_bbs
.first_member
[j
];
2014 fprintf (dump
, " %d ", b
);
2016 fprintf (dump
, "\n");
2018 fprintf (dump
, "update path: ");
2019 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
2021 int b
= candidate_table
[i
].update_bbs
.first_member
[j
];
2023 fprintf (dump
, " %d ", b
);
2025 fprintf (dump
, "\n");
2029 fprintf (dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
2034 /* Print candidates info, for debugging purposes. Callable from debugger. */
2037 debug_candidates (trg
)
2042 fprintf (dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
2043 BB_TO_BLOCK (trg
), trg
);
2044 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
2045 debug_candidate (i
);
2049 /* functions for speculative scheduing */
2051 /* Return 0 if x is a set of a register alive in the beginning of one
2052 of the split-blocks of src, otherwise return 1. */
2055 check_live_1 (src
, x
)
2061 register rtx reg
= SET_DEST (x
);
2066 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2067 || GET_CODE (reg
) == SIGN_EXTRACT
2068 || GET_CODE (reg
) == STRICT_LOW_PART
)
2069 reg
= XEXP (reg
, 0);
2071 if (GET_CODE (reg
) != REG
)
2074 regno
= REGNO (reg
);
2076 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
2078 /* Global registers are assumed live */
2083 if (regno
< FIRST_PSEUDO_REGISTER
)
2085 /* check for hard registers */
2086 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2089 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2091 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2093 if (REGNO_REG_SET_P (basic_block_live_at_start
[b
], regno
+ j
))
2102 /* check for psuedo registers */
2103 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2105 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2107 if (REGNO_REG_SET_P (basic_block_live_at_start
[b
], regno
))
2119 /* If x is a set of a register R, mark that R is alive in the beginning
2120 of every update-block of src. */
2123 update_live_1 (src
, x
)
2129 register rtx reg
= SET_DEST (x
);
2134 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2135 || GET_CODE (reg
) == SIGN_EXTRACT
2136 || GET_CODE (reg
) == STRICT_LOW_PART
)
2137 reg
= XEXP (reg
, 0);
2139 if (GET_CODE (reg
) != REG
)
2142 /* Global registers are always live, so the code below does not apply
2145 regno
= REGNO (reg
);
2147 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
2149 if (regno
< FIRST_PSEUDO_REGISTER
)
2151 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2154 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2156 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2158 SET_REGNO_REG_SET (basic_block_live_at_start
[b
], regno
+ j
);
2164 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2166 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2168 SET_REGNO_REG_SET (basic_block_live_at_start
[b
], regno
);
2175 /* Return 1 if insn can be speculatively moved from block src to trg,
2176 otherwise return 0. Called before first insertion of insn to
2177 ready-list or before the scheduling. */
2180 check_live (insn
, src
)
2184 /* find the registers set by instruction */
2185 if (GET_CODE (PATTERN (insn
)) == SET
2186 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2187 return check_live_1 (src
, PATTERN (insn
));
2188 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2191 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2192 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2193 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2194 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
2204 /* Update the live registers info after insn was moved speculatively from
2205 block src to trg. */
2208 update_live (insn
, src
)
2212 /* find the registers set by instruction */
2213 if (GET_CODE (PATTERN (insn
)) == SET
2214 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2215 update_live_1 (src
, PATTERN (insn
));
2216 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2219 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2220 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2221 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2222 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
2226 /* Exception Free Loads:
2228 We define five classes of speculative loads: IFREE, IRISKY,
2229 PFREE, PRISKY, and MFREE.
2231 IFREE loads are loads that are proved to be exception-free, just
2232 by examining the load insn. Examples for such loads are loads
2233 from TOC and loads of global data.
2235 IRISKY loads are loads that are proved to be exception-risky,
2236 just by examining the load insn. Examples for such loads are
2237 volatile loads and loads from shared memory.
2239 PFREE loads are loads for which we can prove, by examining other
2240 insns, that they are exception-free. Currently, this class consists
2241 of loads for which we are able to find a "similar load", either in
2242 the target block, or, if only one split-block exists, in that split
2243 block. Load2 is similar to load1 if both have same single base
2244 register. We identify only part of the similar loads, by finding
2245 an insn upon which both load1 and load2 have a DEF-USE dependence.
2247 PRISKY loads are loads for which we can prove, by examining other
2248 insns, that they are exception-risky. Currently we have two proofs for
2249 such loads. The first proof detects loads that are probably guarded by a
2250 test on the memory address. This proof is based on the
2251 backward and forward data dependence information for the region.
2252 Let load-insn be the examined load.
2253 Load-insn is PRISKY iff ALL the following hold:
2255 - insn1 is not in the same block as load-insn
2256 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2257 - test-insn is either a compare or a branch, not in the same block as load-insn
2258 - load-insn is reachable from test-insn
2259 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2261 This proof might fail when the compare and the load are fed
2262 by an insn not in the region. To solve this, we will add to this
2263 group all loads that have no input DEF-USE dependence.
2265 The second proof detects loads that are directly or indirectly
2266 fed by a speculative load. This proof is affected by the
2267 scheduling process. We will use the flag fed_by_spec_load.
2268 Initially, all insns have this flag reset. After a speculative
2269 motion of an insn, if insn is either a load, or marked as
2270 fed_by_spec_load, we will also mark as fed_by_spec_load every
2271 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2272 load which is fed_by_spec_load is also PRISKY.
2274 MFREE (maybe-free) loads are all the remaining loads. They may be
2275 exception-free, but we cannot prove it.
2277 Now, all loads in IFREE and PFREE classes are considered
2278 exception-free, while all loads in IRISKY and PRISKY classes are
2279 considered exception-risky. As for loads in the MFREE class,
2280 these are considered either exception-free or exception-risky,
2281 depending on whether we are pessimistic or optimistic. We have
2282 to take the pessimistic approach to assure the safety of
2283 speculative scheduling, but we can take the optimistic approach
2284 by invoking the -fsched_spec_load_dangerous option. */
2286 enum INSN_TRAP_CLASS
2288 TRAP_FREE
= 0, IFREE
= 1, PFREE_CANDIDATE
= 2,
2289 PRISKY_CANDIDATE
= 3, IRISKY
= 4, TRAP_RISKY
= 5
2292 #define WORST_CLASS(class1, class2) \
2293 ((class1 > class2) ? class1 : class2)
2295 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between */
2296 /* some speculatively moved load insn and this one. */
2297 char *fed_by_spec_load
;
2300 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2301 #define IS_REACHABLE(bb_from, bb_to) \
2303 || IS_RGN_ENTRY (bb_from) \
2304 || (bitset_member (ancestor_edges[bb_to], \
2305 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2307 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2308 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2310 /* Non-zero iff the address is comprised from at most 1 register */
2311 #define CONST_BASED_ADDRESS_P(x) \
2312 (GET_CODE (x) == REG \
2313 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2314 || (GET_CODE (x) == LO_SUM)) \
2315 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2316 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2318 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2321 set_spec_fed (load_insn
)
2326 for (link
= INSN_DEPEND (load_insn
); link
; link
= XEXP (link
, 1))
2327 if (GET_MODE (link
) == VOIDmode
)
2328 FED_BY_SPEC_LOAD (XEXP (link
, 0)) = 1;
2329 } /* set_spec_fed */
2331 /* On the path from the insn to load_insn_bb, find a conditional branch */
2332 /* depending on insn, that guards the speculative load. */
2335 find_conditional_protection (insn
, load_insn_bb
)
2341 /* iterate through DEF-USE forward dependences */
2342 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
2344 rtx next
= XEXP (link
, 0);
2345 if ((CONTAINING_RGN (INSN_BLOCK (next
)) ==
2346 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
2347 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
2348 && load_insn_bb
!= INSN_BB (next
)
2349 && GET_MODE (link
) == VOIDmode
2350 && (GET_CODE (next
) == JUMP_INSN
2351 || find_conditional_protection (next
, load_insn_bb
)))
2355 } /* find_conditional_protection */
2357 /* Returns 1 if the same insn1 that participates in the computation
2358 of load_insn's address is feeding a conditional branch that is
2359 guarding on load_insn. This is true if we find a the two DEF-USE
2361 insn1 -> ... -> conditional-branch
2362 insn1 -> ... -> load_insn,
2363 and if a flow path exist:
2364 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2365 and if insn1 is on the path
2366 region-entry -> ... -> bb_trg -> ... load_insn.
2368 Locate insn1 by climbing on LOG_LINKS from load_insn.
2369 Locate the branch by following INSN_DEPEND from insn1. */
2372 is_conditionally_protected (load_insn
, bb_src
, bb_trg
)
2378 for (link
= LOG_LINKS (load_insn
); link
; link
= XEXP (link
, 1))
2380 rtx insn1
= XEXP (link
, 0);
2382 /* must be a DEF-USE dependence upon non-branch */
2383 if (GET_MODE (link
) != VOIDmode
2384 || GET_CODE (insn1
) == JUMP_INSN
)
2387 /* must exist a path: region-entry -> ... -> bb_trg -> ... load_insn */
2388 if (INSN_BB (insn1
) == bb_src
2389 || (CONTAINING_RGN (INSN_BLOCK (insn1
))
2390 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
2391 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
2392 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
2395 /* now search for the conditional-branch */
2396 if (find_conditional_protection (insn1
, bb_src
))
2399 /* recursive step: search another insn1, "above" current insn1. */
2400 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
2403 /* the chain does not exsist */
2405 } /* is_conditionally_protected */
2407 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2408 load_insn can move speculatively from bb_src to bb_trg. All the
2409 following must hold:
2411 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2412 (2) load_insn and load1 have a def-use dependence upon
2413 the same insn 'insn1'.
2414 (3) either load2 is in bb_trg, or:
2415 - there's only one split-block, and
2416 - load1 is on the escape path, and
2418 From all these we can conclude that the two loads access memory
2419 addresses that differ at most by a constant, and hence if moving
2420 load_insn would cause an exception, it would have been caused by
2424 is_pfree (load_insn
, bb_src
, bb_trg
)
2429 register candidate
*candp
= candidate_table
+ bb_src
;
2431 if (candp
->split_bbs
.nr_members
!= 1)
2432 /* must have exactly one escape block */
2435 for (back_link
= LOG_LINKS (load_insn
);
2436 back_link
; back_link
= XEXP (back_link
, 1))
2438 rtx insn1
= XEXP (back_link
, 0);
2440 if (GET_MODE (back_link
) == VOIDmode
)
2442 /* found a DEF-USE dependence (insn1, load_insn) */
2445 for (fore_link
= INSN_DEPEND (insn1
);
2446 fore_link
; fore_link
= XEXP (fore_link
, 1))
2448 rtx insn2
= XEXP (fore_link
, 0);
2449 if (GET_MODE (fore_link
) == VOIDmode
)
2451 /* found a DEF-USE dependence (insn1, insn2) */
2452 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
2453 /* insn2 not guaranteed to be a 1 base reg load */
2456 if (INSN_BB (insn2
) == bb_trg
)
2457 /* insn2 is the similar load, in the target block */
2460 if (*(candp
->split_bbs
.first_member
) == INSN_BLOCK (insn2
))
2461 /* insn2 is a similar load, in a split-block */
2468 /* couldn't find a similar load */
2472 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2473 as found by analyzing insn's expression. */
2476 may_trap_exp (x
, is_store
)
2484 code
= GET_CODE (x
);
2494 /* The insn uses memory */
2495 /* a volatile load */
2496 if (MEM_VOLATILE_P (x
))
2498 /* an exception-free load */
2499 if (!may_trap_p (x
))
2501 /* a load with 1 base register, to be further checked */
2502 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
2503 return PFREE_CANDIDATE
;
2504 /* no info on the load, to be further checked */
2505 return PRISKY_CANDIDATE
;
2510 int i
, insn_class
= TRAP_FREE
;
2512 /* neither store nor load, check if it may cause a trap */
2515 /* recursive step: walk the insn... */
2516 fmt
= GET_RTX_FORMAT (code
);
2517 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2521 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
2522 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2524 else if (fmt
[i
] == 'E')
2527 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2529 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
2530 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2531 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2535 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2540 } /* may_trap_exp */
2543 /* Classifies insn for the purpose of verifying that it can be
2544 moved speculatively, by examining it's patterns, returning:
2545 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2546 TRAP_FREE: non-load insn.
2547 IFREE: load from a globaly safe location.
2548 IRISKY: volatile load.
2549 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2550 being either PFREE or PRISKY. */
2553 haifa_classify_insn (insn
)
2556 rtx pat
= PATTERN (insn
);
2557 int tmp_class
= TRAP_FREE
;
2558 int insn_class
= TRAP_FREE
;
2561 if (GET_CODE (pat
) == PARALLEL
)
2563 int i
, len
= XVECLEN (pat
, 0);
2565 for (i
= len
- 1; i
>= 0; i
--)
2567 code
= GET_CODE (XVECEXP (pat
, 0, i
));
2571 /* test if it is a 'store' */
2572 tmp_class
= may_trap_exp (XEXP (XVECEXP (pat
, 0, i
), 0), 1);
2575 /* test if it is a store */
2576 tmp_class
= may_trap_exp (SET_DEST (XVECEXP (pat
, 0, i
)), 1);
2577 if (tmp_class
== TRAP_RISKY
)
2579 /* test if it is a load */
2581 WORST_CLASS (tmp_class
,
2582 may_trap_exp (SET_SRC (XVECEXP (pat
, 0, i
)), 0));
2585 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2586 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2592 code
= GET_CODE (pat
);
2596 /* test if it is a 'store' */
2597 tmp_class
= may_trap_exp (XEXP (pat
, 0), 1);
2600 /* test if it is a store */
2601 tmp_class
= may_trap_exp (SET_DEST (pat
), 1);
2602 if (tmp_class
== TRAP_RISKY
)
2604 /* test if it is a load */
2606 WORST_CLASS (tmp_class
,
2607 may_trap_exp (SET_SRC (pat
), 0));
2610 insn_class
= tmp_class
;
2615 } /* haifa_classify_insn */
2617 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2618 a load moved speculatively, or if load_insn is protected by
2619 a compare on load_insn's address). */
2622 is_prisky (load_insn
, bb_src
, bb_trg
)
2626 if (FED_BY_SPEC_LOAD (load_insn
))
2629 if (LOG_LINKS (load_insn
) == NULL
)
2630 /* dependence may 'hide' out of the region. */
2633 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2639 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2640 Return 1 if insn is exception-free (and the motion is valid)
2644 is_exception_free (insn
, bb_src
, bb_trg
)
2648 int insn_class
= haifa_classify_insn (insn
);
2650 /* handle non-load insns */
2661 if (!flag_schedule_speculative_load
)
2663 IS_LOAD_INSN (insn
) = 1;
2670 case PFREE_CANDIDATE
:
2671 if (is_pfree (insn
, bb_src
, bb_trg
))
2673 /* don't 'break' here: PFREE-candidate is also PRISKY-candidate */
2674 case PRISKY_CANDIDATE
:
2675 if (!flag_schedule_speculative_load_dangerous
2676 || is_prisky (insn
, bb_src
, bb_trg
))
2682 return flag_schedule_speculative_load_dangerous
;
2683 } /* is_exception_free */
2686 /* Process an insn's memory dependencies. There are four kinds of
2689 (0) read dependence: read follows read
2690 (1) true dependence: read follows write
2691 (2) anti dependence: write follows read
2692 (3) output dependence: write follows write
2694 We are careful to build only dependencies which actually exist, and
2695 use transitivity to avoid building too many links. */
2697 /* Return the INSN_LIST containing INSN in LIST, or NULL
2698 if LIST does not contain INSN. */
2701 find_insn_list (insn
, list
)
2707 if (XEXP (list
, 0) == insn
)
2709 list
= XEXP (list
, 1);
2715 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 otherwise. */
2717 __inline
static char
2718 find_insn_mem_list (insn
, x
, list
, list1
)
2724 if (XEXP (list
, 0) == insn
2725 && XEXP (list1
, 0) == x
)
2727 list
= XEXP (list
, 1);
2728 list1
= XEXP (list1
, 1);
2734 /* Compute the function units used by INSN. This caches the value
2735 returned by function_units_used. A function unit is encoded as the
2736 unit number if the value is non-negative and the compliment of a
2737 mask if the value is negative. A function unit index is the
2738 non-negative encoding. */
2744 register int unit
= INSN_UNIT (insn
);
2748 recog_memoized (insn
);
2750 /* A USE insn, or something else we don't need to understand.
2751 We can't pass these directly to function_units_used because it will
2752 trigger a fatal error for unrecognizable insns. */
2753 if (INSN_CODE (insn
) < 0)
2757 unit
= function_units_used (insn
);
2758 /* Increment non-negative values so we can cache zero. */
2762 /* We only cache 16 bits of the result, so if the value is out of
2763 range, don't cache it. */
2764 if (FUNCTION_UNITS_SIZE
< HOST_BITS_PER_SHORT
2766 || (~unit
& ((1 << (HOST_BITS_PER_SHORT
- 1)) - 1)) == 0)
2767 INSN_UNIT (insn
) = unit
;
2769 return (unit
> 0 ? unit
- 1 : unit
);
2772 /* Compute the blockage range for executing INSN on UNIT. This caches
2773 the value returned by the blockage_range_function for the unit.
2774 These values are encoded in an int where the upper half gives the
2775 minimum value and the lower half gives the maximum value. */
2777 __inline
static unsigned int
2778 blockage_range (unit
, insn
)
2782 unsigned int blockage
= INSN_BLOCKAGE (insn
);
2785 if (UNIT_BLOCKED (blockage
) != unit
+ 1)
2787 range
= function_units
[unit
].blockage_range_function (insn
);
2788 /* We only cache the blockage range for one unit and then only if
2790 if (HOST_BITS_PER_INT
>= UNIT_BITS
+ 2 * BLOCKAGE_BITS
)
2791 INSN_BLOCKAGE (insn
) = ENCODE_BLOCKAGE (unit
+ 1, range
);
2794 range
= BLOCKAGE_RANGE (blockage
);
2799 /* A vector indexed by function unit instance giving the last insn to use
2800 the unit. The value of the function unit instance index for unit U
2801 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2802 static rtx unit_last_insn
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2804 /* A vector indexed by function unit instance giving the minimum time when
2805 the unit will unblock based on the maximum blockage cost. */
2806 static int unit_tick
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2808 /* A vector indexed by function unit number giving the number of insns
2809 that remain to use the unit. */
2810 static int unit_n_insns
[FUNCTION_UNITS_SIZE
];
2812 /* Reset the function unit state to the null state. */
2817 bzero ((char *) unit_last_insn
, sizeof (unit_last_insn
));
2818 bzero ((char *) unit_tick
, sizeof (unit_tick
));
2819 bzero ((char *) unit_n_insns
, sizeof (unit_n_insns
));
2822 /* Return the issue-delay of an insn */
2825 insn_issue_delay (insn
)
2829 int unit
= insn_unit (insn
);
2831 /* efficiency note: in fact, we are working 'hard' to compute a
2832 value that was available in md file, and is not available in
2833 function_units[] structure. It would be nice to have this
2834 value there, too. */
2837 if (function_units
[unit
].blockage_range_function
&&
2838 function_units
[unit
].blockage_function
)
2839 delay
= function_units
[unit
].blockage_function (insn
, insn
);
2842 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2843 if ((unit
& 1) != 0 && function_units
[i
].blockage_range_function
2844 && function_units
[i
].blockage_function
)
2845 delay
= MAX (delay
, function_units
[i
].blockage_function (insn
, insn
));
2850 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2851 instance INSTANCE at time CLOCK if the previous actual hazard cost
2855 actual_hazard_this_instance (unit
, instance
, insn
, clock
, cost
)
2856 int unit
, instance
, clock
, cost
;
2859 int tick
= unit_tick
[instance
]; /* issue time of the last issued insn */
2861 if (tick
- clock
> cost
)
2863 /* The scheduler is operating forward, so unit's last insn is the
2864 executing insn and INSN is the candidate insn. We want a
2865 more exact measure of the blockage if we execute INSN at CLOCK
2866 given when we committed the execution of the unit's last insn.
2868 The blockage value is given by either the unit's max blockage
2869 constant, blockage range function, or blockage function. Use
2870 the most exact form for the given unit. */
2872 if (function_units
[unit
].blockage_range_function
)
2874 if (function_units
[unit
].blockage_function
)
2875 tick
+= (function_units
[unit
].blockage_function
2876 (unit_last_insn
[instance
], insn
)
2877 - function_units
[unit
].max_blockage
);
2879 tick
+= ((int) MAX_BLOCKAGE_COST (blockage_range (unit
, insn
))
2880 - function_units
[unit
].max_blockage
);
2882 if (tick
- clock
> cost
)
2883 cost
= tick
- clock
;
2888 /* Record INSN as having begun execution on the units encoded by UNIT at
2891 __inline
static void
2892 schedule_unit (unit
, insn
, clock
)
2900 int instance
= unit
;
2901 #if MAX_MULTIPLICITY > 1
2902 /* Find the first free instance of the function unit and use that
2903 one. We assume that one is free. */
2904 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
2906 if (!actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
2908 instance
+= FUNCTION_UNITS_SIZE
;
2911 unit_last_insn
[instance
] = insn
;
2912 unit_tick
[instance
] = (clock
+ function_units
[unit
].max_blockage
);
2915 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2916 if ((unit
& 1) != 0)
2917 schedule_unit (i
, insn
, clock
);
2920 /* Return the actual hazard cost of executing INSN on the units encoded by
2921 UNIT at time CLOCK if the previous actual hazard cost was COST. */
2924 actual_hazard (unit
, insn
, clock
, cost
)
2925 int unit
, clock
, cost
;
2932 /* Find the instance of the function unit with the minimum hazard. */
2933 int instance
= unit
;
2934 int best_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
2938 #if MAX_MULTIPLICITY > 1
2939 if (best_cost
> cost
)
2941 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
2943 instance
+= FUNCTION_UNITS_SIZE
;
2944 this_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
2946 if (this_cost
< best_cost
)
2948 best_cost
= this_cost
;
2949 if (this_cost
<= cost
)
2955 cost
= MAX (cost
, best_cost
);
2958 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2959 if ((unit
& 1) != 0)
2960 cost
= actual_hazard (i
, insn
, clock
, cost
);
2965 /* Return the potential hazard cost of executing an instruction on the
2966 units encoded by UNIT if the previous potential hazard cost was COST.
2967 An insn with a large blockage time is chosen in preference to one
2968 with a smaller time; an insn that uses a unit that is more likely
2969 to be used is chosen in preference to one with a unit that is less
2970 used. We are trying to minimize a subsequent actual hazard. */
2973 potential_hazard (unit
, insn
, cost
)
2978 unsigned int minb
, maxb
;
2982 minb
= maxb
= function_units
[unit
].max_blockage
;
2985 if (function_units
[unit
].blockage_range_function
)
2987 maxb
= minb
= blockage_range (unit
, insn
);
2988 maxb
= MAX_BLOCKAGE_COST (maxb
);
2989 minb
= MIN_BLOCKAGE_COST (minb
);
2994 /* Make the number of instructions left dominate. Make the
2995 minimum delay dominate the maximum delay. If all these
2996 are the same, use the unit number to add an arbitrary
2997 ordering. Other terms can be added. */
2998 ncost
= minb
* 0x40 + maxb
;
2999 ncost
*= (unit_n_insns
[unit
] - 1) * 0x1000 + unit
;
3006 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3007 if ((unit
& 1) != 0)
3008 cost
= potential_hazard (i
, insn
, cost
);
3013 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3014 This is the number of cycles between instruction issue and
3015 instruction results. */
3018 insn_cost (insn
, link
, used
)
3019 rtx insn
, link
, used
;
3021 register int cost
= INSN_COST (insn
);
3025 recog_memoized (insn
);
3027 /* A USE insn, or something else we don't need to understand.
3028 We can't pass these directly to result_ready_cost because it will
3029 trigger a fatal error for unrecognizable insns. */
3030 if (INSN_CODE (insn
) < 0)
3032 INSN_COST (insn
) = 1;
3037 cost
= result_ready_cost (insn
);
3042 INSN_COST (insn
) = cost
;
3046 /* in this case estimate cost without caring how insn is used. */
3047 if (link
== 0 && used
== 0)
3050 /* A USE insn should never require the value used to be computed. This
3051 allows the computation of a function's result and parameter values to
3052 overlap the return and call. */
3053 recog_memoized (used
);
3054 if (INSN_CODE (used
) < 0)
3055 LINK_COST_FREE (link
) = 1;
3057 /* If some dependencies vary the cost, compute the adjustment. Most
3058 commonly, the adjustment is complete: either the cost is ignored
3059 (in the case of an output- or anti-dependence), or the cost is
3060 unchanged. These values are cached in the link as LINK_COST_FREE
3061 and LINK_COST_ZERO. */
3063 if (LINK_COST_FREE (link
))
3066 else if (!LINK_COST_ZERO (link
))
3070 ADJUST_COST (used
, link
, insn
, ncost
);
3072 LINK_COST_FREE (link
) = ncost
= 1;
3074 LINK_COST_ZERO (link
) = 1;
3081 /* Compute the priority number for INSN. */
3090 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
3093 if ((this_priority
= INSN_PRIORITY (insn
)) == 0)
3095 if (INSN_DEPEND (insn
) == 0)
3096 this_priority
= insn_cost (insn
, 0, 0);
3098 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
3103 if (RTX_INTEGRATED_P (link
))
3106 next
= XEXP (link
, 0);
3108 /* critical path is meaningful in block boundaries only */
3109 if (INSN_BLOCK (next
) != INSN_BLOCK (insn
))
3112 next_priority
= insn_cost (insn
, link
, next
) + priority (next
);
3113 if (next_priority
> this_priority
)
3114 this_priority
= next_priority
;
3116 INSN_PRIORITY (insn
) = this_priority
;
3118 return this_priority
;
3122 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3123 them to the unused_*_list variables, so that they can be reused. */
3126 free_pending_lists ()
3128 if (current_nr_blocks
<= 1)
3130 free_list (&pending_read_insns
, &unused_insn_list
);
3131 free_list (&pending_write_insns
, &unused_insn_list
);
3132 free_list (&pending_read_mems
, &unused_expr_list
);
3133 free_list (&pending_write_mems
, &unused_expr_list
);
3137 /* interblock scheduling */
3140 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3142 free_list (&bb_pending_read_insns
[bb
], &unused_insn_list
);
3143 free_list (&bb_pending_write_insns
[bb
], &unused_insn_list
);
3144 free_list (&bb_pending_read_mems
[bb
], &unused_expr_list
);
3145 free_list (&bb_pending_write_mems
[bb
], &unused_expr_list
);
3150 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3151 The MEM is a memory reference contained within INSN, which we are saving
3152 so that we can do memory aliasing on it. */
3155 add_insn_mem_dependence (insn_list
, mem_list
, insn
, mem
)
3156 rtx
*insn_list
, *mem_list
, insn
, mem
;
3160 link
= alloc_INSN_LIST (insn
, *insn_list
);
3163 link
= alloc_EXPR_LIST (VOIDmode
, mem
, *mem_list
);
3166 pending_lists_length
++;
3170 /* Make a dependency between every memory reference on the pending lists
3171 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3175 flush_pending_lists (insn
, only_write
)
3182 while (pending_read_insns
&& ! only_write
)
3184 add_dependence (insn
, XEXP (pending_read_insns
, 0), REG_DEP_ANTI
);
3186 link
= pending_read_insns
;
3187 pending_read_insns
= XEXP (pending_read_insns
, 1);
3188 XEXP (link
, 1) = unused_insn_list
;
3189 unused_insn_list
= link
;
3191 link
= pending_read_mems
;
3192 pending_read_mems
= XEXP (pending_read_mems
, 1);
3193 XEXP (link
, 1) = unused_expr_list
;
3194 unused_expr_list
= link
;
3196 while (pending_write_insns
)
3198 add_dependence (insn
, XEXP (pending_write_insns
, 0), REG_DEP_ANTI
);
3200 link
= pending_write_insns
;
3201 pending_write_insns
= XEXP (pending_write_insns
, 1);
3202 XEXP (link
, 1) = unused_insn_list
;
3203 unused_insn_list
= link
;
3205 link
= pending_write_mems
;
3206 pending_write_mems
= XEXP (pending_write_mems
, 1);
3207 XEXP (link
, 1) = unused_expr_list
;
3208 unused_expr_list
= link
;
3210 pending_lists_length
= 0;
3212 /* last_pending_memory_flush is now a list of insns */
3213 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3214 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3216 free_list (&last_pending_memory_flush
, &unused_insn_list
);
3217 last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
3220 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
3221 by the write to the destination of X, and reads of everything mentioned. */
3224 sched_analyze_1 (x
, insn
)
3229 register rtx dest
= SET_DEST (x
);
3234 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
3235 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3237 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3239 /* The second and third arguments are values read by this insn. */
3240 sched_analyze_2 (XEXP (dest
, 1), insn
);
3241 sched_analyze_2 (XEXP (dest
, 2), insn
);
3243 dest
= SUBREG_REG (dest
);
3246 if (GET_CODE (dest
) == REG
)
3250 regno
= REGNO (dest
);
3252 /* A hard reg in a wide mode may really be multiple registers.
3253 If so, mark all of them just like the first. */
3254 if (regno
< FIRST_PSEUDO_REGISTER
)
3256 i
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
3261 for (u
= reg_last_uses
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3262 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3263 reg_last_uses
[regno
+ i
] = 0;
3265 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3266 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3268 SET_REGNO_REG_SET (reg_pending_sets
, regno
+ i
);
3270 if ((call_used_regs
[regno
+ i
] || global_regs
[regno
+ i
]))
3271 /* Function calls clobber all call_used regs. */
3272 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3273 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3280 for (u
= reg_last_uses
[regno
]; u
; u
= XEXP (u
, 1))
3281 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3282 reg_last_uses
[regno
] = 0;
3284 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3285 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3287 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
3289 /* Pseudos that are REG_EQUIV to something may be replaced
3290 by that during reloading. We need only add dependencies for
3291 the address in the REG_EQUIV note. */
3292 if (!reload_completed
3293 && reg_known_equiv_p
[regno
]
3294 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3295 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3297 /* Don't let it cross a call after scheduling if it doesn't
3298 already cross one. */
3300 if (REG_N_CALLS_CROSSED (regno
) == 0)
3301 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3302 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3305 else if (GET_CODE (dest
) == MEM
)
3307 /* Writing memory. */
3309 if (pending_lists_length
> 32)
3311 /* Flush all pending reads and writes to prevent the pending lists
3312 from getting any larger. Insn scheduling runs too slowly when
3313 these lists get long. The number 32 was chosen because it
3314 seems like a reasonable number. When compiling GCC with itself,
3315 this flush occurs 8 times for sparc, and 10 times for m88k using
3317 flush_pending_lists (insn
, 0);
3322 rtx pending
, pending_mem
;
3324 pending
= pending_read_insns
;
3325 pending_mem
= pending_read_mems
;
3328 /* If a dependency already exists, don't create a new one. */
3329 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3330 if (anti_dependence (XEXP (pending_mem
, 0), dest
))
3331 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3333 pending
= XEXP (pending
, 1);
3334 pending_mem
= XEXP (pending_mem
, 1);
3337 pending
= pending_write_insns
;
3338 pending_mem
= pending_write_mems
;
3341 /* If a dependency already exists, don't create a new one. */
3342 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3343 if (output_dependence (XEXP (pending_mem
, 0), dest
))
3344 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
3346 pending
= XEXP (pending
, 1);
3347 pending_mem
= XEXP (pending_mem
, 1);
3350 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3351 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3353 add_insn_mem_dependence (&pending_write_insns
, &pending_write_mems
,
3356 sched_analyze_2 (XEXP (dest
, 0), insn
);
3359 /* Analyze reads. */
3360 if (GET_CODE (x
) == SET
)
3361 sched_analyze_2 (SET_SRC (x
), insn
);
3364 /* Analyze the uses of memory and registers in rtx X in INSN. */
3367 sched_analyze_2 (x
, insn
)
3373 register enum rtx_code code
;
3379 code
= GET_CODE (x
);
3388 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3389 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3390 this does not mean that this insn is using cc0. */
3398 /* User of CC0 depends on immediately preceding insn. */
3399 SCHED_GROUP_P (insn
) = 1;
3401 /* There may be a note before this insn now, but all notes will
3402 be removed before we actually try to schedule the insns, so
3403 it won't cause a problem later. We must avoid it here though. */
3404 prev
= prev_nonnote_insn (insn
);
3406 /* Make a copy of all dependencies on the immediately previous insn,
3407 and add to this insn. This is so that all the dependencies will
3408 apply to the group. Remove an explicit dependence on this insn
3409 as SCHED_GROUP_P now represents it. */
3411 if (find_insn_list (prev
, LOG_LINKS (insn
)))
3412 remove_dependence (insn
, prev
);
3414 for (link
= LOG_LINKS (prev
); link
; link
= XEXP (link
, 1))
3415 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3424 int regno
= REGNO (x
);
3425 if (regno
< FIRST_PSEUDO_REGISTER
)
3429 i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
3432 reg_last_uses
[regno
+ i
]
3433 = alloc_INSN_LIST (insn
, reg_last_uses
[regno
+ i
]);
3435 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3436 add_dependence (insn
, XEXP (u
, 0), 0);
3438 if ((call_used_regs
[regno
+ i
] || global_regs
[regno
+ i
]))
3439 /* Function calls clobber all call_used regs. */
3440 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3441 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3446 reg_last_uses
[regno
] = alloc_INSN_LIST (insn
, reg_last_uses
[regno
]);
3448 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3449 add_dependence (insn
, XEXP (u
, 0), 0);
3451 /* Pseudos that are REG_EQUIV to something may be replaced
3452 by that during reloading. We need only add dependencies for
3453 the address in the REG_EQUIV note. */
3454 if (!reload_completed
3455 && reg_known_equiv_p
[regno
]
3456 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3457 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3459 /* If the register does not already cross any calls, then add this
3460 insn to the sched_before_next_call list so that it will still
3461 not cross calls after scheduling. */
3462 if (REG_N_CALLS_CROSSED (regno
) == 0)
3463 add_dependence (sched_before_next_call
, insn
, REG_DEP_ANTI
);
3470 /* Reading memory. */
3472 rtx pending
, pending_mem
;
3474 pending
= pending_read_insns
;
3475 pending_mem
= pending_read_mems
;
3478 /* If a dependency already exists, don't create a new one. */
3479 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3480 if (read_dependence (XEXP (pending_mem
, 0), x
))
3481 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3483 pending
= XEXP (pending
, 1);
3484 pending_mem
= XEXP (pending_mem
, 1);
3487 pending
= pending_write_insns
;
3488 pending_mem
= pending_write_mems
;
3491 /* If a dependency already exists, don't create a new one. */
3492 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3493 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
3495 add_dependence (insn
, XEXP (pending
, 0), 0);
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 /* Always add these dependencies to pending_reads, since
3505 this insn may be followed by a write. */
3506 add_insn_mem_dependence (&pending_read_insns
, &pending_read_mems
,
3509 /* Take advantage of tail recursion here. */
3510 sched_analyze_2 (XEXP (x
, 0), insn
);
3516 case UNSPEC_VOLATILE
:
3521 /* Traditional and volatile asm instructions must be considered to use
3522 and clobber all hard registers, all pseudo-registers and all of
3523 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3525 Consider for instance a volatile asm that changes the fpu rounding
3526 mode. An insn should not be moved across this even if it only uses
3527 pseudo-regs because it might give an incorrectly rounded result. */
3528 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
3530 int max_reg
= max_reg_num ();
3531 for (i
= 0; i
< max_reg
; i
++)
3533 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3534 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3535 reg_last_uses
[i
] = 0;
3537 /* reg_last_sets[r] is now a list of insns */
3538 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3539 add_dependence (insn
, XEXP (u
, 0), 0);
3541 reg_pending_sets_all
= 1;
3543 flush_pending_lists (insn
, 0);
3546 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3547 We can not just fall through here since then we would be confused
3548 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3549 traditional asms unlike their normal usage. */
3551 if (code
== ASM_OPERANDS
)
3553 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
3554 sched_analyze_2 (ASM_OPERANDS_INPUT (x
, j
), insn
);
3564 /* These both read and modify the result. We must handle them as writes
3565 to get proper dependencies for following instructions. We must handle
3566 them as reads to get proper dependencies from this to previous
3567 instructions. Thus we need to pass them to both sched_analyze_1
3568 and sched_analyze_2. We must call sched_analyze_2 first in order
3569 to get the proper antecedent for the read. */
3570 sched_analyze_2 (XEXP (x
, 0), insn
);
3571 sched_analyze_1 (x
, insn
);
3578 /* Other cases: walk the insn. */
3579 fmt
= GET_RTX_FORMAT (code
);
3580 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3583 sched_analyze_2 (XEXP (x
, i
), insn
);
3584 else if (fmt
[i
] == 'E')
3585 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3586 sched_analyze_2 (XVECEXP (x
, i
, j
), insn
);
3590 /* Analyze an INSN with pattern X to find all dependencies. */
3593 sched_analyze_insn (x
, insn
, loop_notes
)
3597 register RTX_CODE code
= GET_CODE (x
);
3599 int maxreg
= max_reg_num ();
3602 if (code
== SET
|| code
== CLOBBER
)
3603 sched_analyze_1 (x
, insn
);
3604 else if (code
== PARALLEL
)
3607 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
3609 code
= GET_CODE (XVECEXP (x
, 0, i
));
3610 if (code
== SET
|| code
== CLOBBER
)
3611 sched_analyze_1 (XVECEXP (x
, 0, i
), insn
);
3613 sched_analyze_2 (XVECEXP (x
, 0, i
), insn
);
3617 sched_analyze_2 (x
, insn
);
3619 /* Mark registers CLOBBERED or used by called function. */
3620 if (GET_CODE (insn
) == CALL_INSN
)
3621 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
3623 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
3624 sched_analyze_1 (XEXP (link
, 0), insn
);
3626 sched_analyze_2 (XEXP (link
, 0), insn
);
3629 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic block, then
3630 we must be sure that no instructions are scheduled across it.
3631 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3632 become incorrect. */
3636 int max_reg
= max_reg_num ();
3639 for (i
= 0; i
< max_reg
; i
++)
3642 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3643 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3644 reg_last_uses
[i
] = 0;
3646 /* reg_last_sets[r] is now a list of insns */
3647 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3648 add_dependence (insn
, XEXP (u
, 0), 0);
3650 reg_pending_sets_all
= 1;
3652 flush_pending_lists (insn
, 0);
3655 while (XEXP (link
, 1))
3656 link
= XEXP (link
, 1);
3657 XEXP (link
, 1) = REG_NOTES (insn
);
3658 REG_NOTES (insn
) = loop_notes
;
3661 /* After reload, it is possible for an instruction to have a REG_DEAD note
3662 for a register that actually dies a few instructions earlier. For
3663 example, this can happen with SECONDARY_MEMORY_NEEDED reloads.
3664 In this case, we must consider the insn to use the register mentioned
3665 in the REG_DEAD note. Otherwise, we may accidentally move this insn
3666 after another insn that sets the register, thus getting obviously invalid
3667 rtl. This confuses reorg which believes that REG_DEAD notes are still
3670 ??? We would get better code if we fixed reload to put the REG_DEAD
3671 notes in the right places, but that may not be worth the effort. */
3673 if (reload_completed
)
3677 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
3678 if (REG_NOTE_KIND (note
) == REG_DEAD
)
3679 sched_analyze_2 (XEXP (note
, 0), insn
);
3682 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
3684 /* reg_last_sets[r] is now a list of insns */
3685 free_list (®_last_sets
[i
], &unused_insn_list
);
3687 = alloc_INSN_LIST (insn
, NULL_RTX
);
3689 CLEAR_REG_SET (reg_pending_sets
);
3691 if (reg_pending_sets_all
)
3693 for (i
= 0; i
< maxreg
; i
++)
3695 /* reg_last_sets[r] is now a list of insns */
3696 free_list (®_last_sets
[i
], &unused_insn_list
);
3697 reg_last_sets
[i
] = alloc_INSN_LIST (insn
, NULL_RTX
);
3700 reg_pending_sets_all
= 0;
3703 /* Handle function calls and function returns created by the epilogue
3705 if (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3710 /* When scheduling instructions, we make sure calls don't lose their
3711 accompanying USE insns by depending them one on another in order.
3713 Also, we must do the same thing for returns created by the epilogue
3714 threading code. Note this code works only in this special case,
3715 because other passes make no guarantee that they will never emit
3716 an instruction between a USE and a RETURN. There is such a guarantee
3717 for USE instructions immediately before a call. */
3719 prev_dep_insn
= insn
;
3720 dep_insn
= PREV_INSN (insn
);
3721 while (GET_CODE (dep_insn
) == INSN
3722 && GET_CODE (PATTERN (dep_insn
)) == USE
3723 && GET_CODE (XEXP (PATTERN (dep_insn
), 0)) == REG
)
3725 SCHED_GROUP_P (prev_dep_insn
) = 1;
3727 /* Make a copy of all dependencies on dep_insn, and add to insn.
3728 This is so that all of the dependencies will apply to the
3731 for (link
= LOG_LINKS (dep_insn
); link
; link
= XEXP (link
, 1))
3732 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3734 prev_dep_insn
= dep_insn
;
3735 dep_insn
= PREV_INSN (dep_insn
);
3740 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3741 for every dependency. */
3744 sched_analyze (head
, tail
)
3751 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3753 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3755 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3758 else if (GET_CODE (insn
) == CALL_INSN
)
3763 CANT_MOVE (insn
) = 1;
3765 /* Any instruction using a hard register which may get clobbered
3766 by a call needs to be marked as dependent on this call.
3767 This prevents a use of a hard return reg from being moved
3768 past a void call (i.e. it does not explicitly set the hard
3771 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3772 all registers, not just hard registers, may be clobbered by this
3775 /* Insn, being a CALL_INSN, magically depends on
3776 `last_function_call' already. */
3778 if (NEXT_INSN (insn
) && GET_CODE (NEXT_INSN (insn
)) == NOTE
3779 && NOTE_LINE_NUMBER (NEXT_INSN (insn
)) == NOTE_INSN_SETJMP
)
3781 int max_reg
= max_reg_num ();
3782 for (i
= 0; i
< max_reg
; i
++)
3784 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3785 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3787 reg_last_uses
[i
] = 0;
3789 /* reg_last_sets[r] is now a list of insns */
3790 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3791 add_dependence (insn
, XEXP (u
, 0), 0);
3793 reg_pending_sets_all
= 1;
3795 /* Add a pair of fake REG_NOTE which we will later
3796 convert back into a NOTE_INSN_SETJMP note. See
3797 reemit_notes for why we use a pair of NOTEs. */
3798 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_DEAD
,
3801 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_DEAD
,
3802 GEN_INT (NOTE_INSN_SETJMP
),
3807 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3808 if (call_used_regs
[i
] || global_regs
[i
])
3810 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3811 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3812 reg_last_uses
[i
] = 0;
3814 /* reg_last_sets[r] is now a list of insns */
3815 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3816 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3818 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3822 /* For each insn which shouldn't cross a call, add a dependence
3823 between that insn and this call insn. */
3824 x
= LOG_LINKS (sched_before_next_call
);
3827 add_dependence (insn
, XEXP (x
, 0), REG_DEP_ANTI
);
3830 LOG_LINKS (sched_before_next_call
) = 0;
3832 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3835 /* In the absence of interprocedural alias analysis, we must flush
3836 all pending reads and writes, and start new dependencies starting
3837 from here. But only flush writes for constant calls (which may
3838 be passed a pointer to something we haven't written yet). */
3839 flush_pending_lists (insn
, CONST_CALL_P (insn
));
3841 /* Depend this function call (actually, the user of this
3842 function call) on all hard register clobberage. */
3844 /* last_function_call is now a list of insns */
3845 free_list(&last_function_call
, &unused_insn_list
);
3846 last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3849 /* See comments on reemit_notes as to why we do this. */
3850 else if (GET_CODE (insn
) == NOTE
3851 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
3852 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
3853 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
3854 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
3855 || (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
3856 && GET_CODE (PREV_INSN (insn
)) != CALL_INSN
)))
3858 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
3859 GEN_INT (NOTE_BLOCK_NUMBER (insn
)),
3861 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
3862 GEN_INT (NOTE_LINE_NUMBER (insn
)),
3864 CONST_CALL_P (loop_notes
) = CONST_CALL_P (insn
);
3873 /* Called when we see a set of a register. If death is true, then we are
3874 scanning backwards. Mark that register as unborn. If nobody says
3875 otherwise, that is how things will remain. If death is false, then we
3876 are scanning forwards. Mark that register as being born. */
3879 sched_note_set (x
, death
)
3884 register rtx reg
= SET_DEST (x
);
3890 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == STRICT_LOW_PART
3891 || GET_CODE (reg
) == SIGN_EXTRACT
|| GET_CODE (reg
) == ZERO_EXTRACT
)
3893 /* Must treat modification of just one hardware register of a multi-reg
3894 value or just a byte field of a register exactly the same way that
3895 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
3896 does not kill the entire register. */
3897 if (GET_CODE (reg
) != SUBREG
3898 || REG_SIZE (SUBREG_REG (reg
)) > REG_SIZE (reg
))
3901 reg
= SUBREG_REG (reg
);
3904 if (GET_CODE (reg
) != REG
)
3907 /* Global registers are always live, so the code below does not apply
3910 regno
= REGNO (reg
);
3911 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
3915 /* If we only set part of the register, then this set does not
3920 /* Try killing this register. */
3921 if (regno
< FIRST_PSEUDO_REGISTER
)
3923 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
3926 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
3931 /* Recompute REG_BASIC_BLOCK as we update all the other
3932 dataflow information. */
3933 if (sched_reg_basic_block
[regno
] == REG_BLOCK_UNKNOWN
)
3934 sched_reg_basic_block
[regno
] = current_block_num
;
3935 else if (sched_reg_basic_block
[regno
] != current_block_num
)
3936 sched_reg_basic_block
[regno
] = REG_BLOCK_GLOBAL
;
3938 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
);
3943 /* Make the register live again. */
3944 if (regno
< FIRST_PSEUDO_REGISTER
)
3946 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
3949 SET_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
3954 SET_REGNO_REG_SET (bb_live_regs
, regno
);
3960 /* Macros and functions for keeping the priority queue sorted, and
3961 dealing with queueing and dequeueing of instructions. */
3963 #define SCHED_SORT(READY, N_READY) \
3964 do { if ((N_READY) == 2) \
3965 swap_sort (READY, N_READY); \
3966 else if ((N_READY) > 2) \
3967 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
3970 /* Returns a positive value if x is preferred; returns a negative value if
3971 y is preferred. Should never return 0, since that will make the sort
3975 rank_for_schedule (x
, y
)
3976 const GENERIC_PTR x
;
3977 const GENERIC_PTR y
;
3979 rtx tmp
= *(rtx
*)y
;
3980 rtx tmp2
= *(rtx
*)x
;
3982 int tmp_class
, tmp2_class
;
3983 int val
, priority_val
, spec_val
, prob_val
, weight_val
;
3986 /* prefer insn with higher priority */
3987 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
3989 return priority_val
;
3991 /* prefer an insn with smaller contribution to registers-pressure */
3992 if (!reload_completed
&&
3993 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
3994 return (weight_val
);
3996 /* some comparison make sense in interblock scheduling only */
3997 if (INSN_BB (tmp
) != INSN_BB (tmp2
))
3999 /* prefer an inblock motion on an interblock motion */
4000 if ((INSN_BB (tmp2
) == target_bb
) && (INSN_BB (tmp
) != target_bb
))
4002 if ((INSN_BB (tmp
) == target_bb
) && (INSN_BB (tmp2
) != target_bb
))
4005 /* prefer a useful motion on a speculative one */
4006 if ((spec_val
= IS_SPECULATIVE_INSN (tmp
) - IS_SPECULATIVE_INSN (tmp2
)))
4009 /* prefer a more probable (speculative) insn */
4010 prob_val
= INSN_PROBABILITY (tmp2
) - INSN_PROBABILITY (tmp
);
4015 /* compare insns based on their relation to the last-scheduled-insn */
4016 if (last_scheduled_insn
)
4018 /* Classify the instructions into three classes:
4019 1) Data dependent on last schedule insn.
4020 2) Anti/Output dependent on last scheduled insn.
4021 3) Independent of last scheduled insn, or has latency of one.
4022 Choose the insn from the highest numbered class if different. */
4023 link
= find_insn_list (tmp
, INSN_DEPEND (last_scheduled_insn
));
4024 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp
) == 1)
4026 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4031 link
= find_insn_list (tmp2
, INSN_DEPEND (last_scheduled_insn
));
4032 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp2
) == 1)
4034 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4039 if ((val
= tmp2_class
- tmp_class
))
4043 /* If insns are equally good, sort by INSN_LUID (original insn order),
4044 so that we make the sort stable. This minimizes instruction movement,
4045 thus minimizing sched's effect on debugging and cross-jumping. */
4046 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
4049 /* Resort the array A in which only element at index N may be out of order. */
4051 __inline
static void
4056 rtx insn
= a
[n
- 1];
4059 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
4067 static int max_priority
;
4069 /* Add INSN to the insn queue so that it can be executed at least
4070 N_CYCLES after the currently executing insn. Preserve insns
4071 chain for debugging purposes. */
4073 __inline
static void
4074 queue_insn (insn
, n_cycles
)
4078 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
4079 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
4080 insn_queue
[next_q
] = link
;
4083 if (sched_verbose
>= 2)
4085 fprintf (dump
, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn
));
4087 if (INSN_BB (insn
) != target_bb
)
4088 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
4090 fprintf (dump
, "queued for %d cycles.\n", n_cycles
);
4095 /* Return nonzero if PAT is the pattern of an insn which makes a
4099 birthing_insn_p (pat
)
4104 if (reload_completed
== 1)
4107 if (GET_CODE (pat
) == SET
4108 && GET_CODE (SET_DEST (pat
)) == REG
)
4110 rtx dest
= SET_DEST (pat
);
4111 int i
= REGNO (dest
);
4113 /* It would be more accurate to use refers_to_regno_p or
4114 reg_mentioned_p to determine when the dest is not live before this
4117 if (REGNO_REG_SET_P (bb_live_regs
, i
))
4118 return (REG_N_SETS (i
) == 1);
4122 if (GET_CODE (pat
) == PARALLEL
)
4124 for (j
= 0; j
< XVECLEN (pat
, 0); j
++)
4125 if (birthing_insn_p (XVECEXP (pat
, 0, j
)))
4131 /* PREV is an insn that is ready to execute. Adjust its priority if that
4132 will help shorten register lifetimes. */
4134 __inline
static void
4135 adjust_priority (prev
)
4138 /* Trying to shorten register lives after reload has completed
4139 is useless and wrong. It gives inaccurate schedules. */
4140 if (reload_completed
== 0)
4145 /* ??? This code has no effect, because REG_DEAD notes are removed
4146 before we ever get here. */
4147 for (note
= REG_NOTES (prev
); note
; note
= XEXP (note
, 1))
4148 if (REG_NOTE_KIND (note
) == REG_DEAD
)
4151 /* Defer scheduling insns which kill registers, since that
4152 shortens register lives. Prefer scheduling insns which
4153 make registers live for the same reason. */
4157 INSN_PRIORITY (prev
) >>= 3;
4160 INSN_PRIORITY (prev
) >>= 2;
4164 INSN_PRIORITY (prev
) >>= 1;
4167 if (birthing_insn_p (PATTERN (prev
)))
4169 int max
= max_priority
;
4171 if (max
> INSN_PRIORITY (prev
))
4172 INSN_PRIORITY (prev
) = max
;
4176 #ifdef ADJUST_PRIORITY
4177 ADJUST_PRIORITY (prev
);
4182 /* INSN is the "currently executing insn". Launch each insn which was
4183 waiting on INSN. READY is a vector of insns which are ready to fire.
4184 N_READY is the number of elements in READY. CLOCK is the current
4188 schedule_insn (insn
, ready
, n_ready
, clock
)
4197 unit
= insn_unit (insn
);
4199 if (sched_verbose
>= 2)
4201 fprintf (dump
, ";;\t\t--> scheduling insn <<<%d>>> on unit ", INSN_UID (insn
));
4202 insn_print_units (insn
);
4203 fprintf (dump
, "\n");
4206 if (sched_verbose
&& unit
== -1)
4207 visualize_no_unit (insn
);
4209 if (MAX_BLOCKAGE
> 1 || issue_rate
> 1 || sched_verbose
)
4210 schedule_unit (unit
, insn
, clock
);
4212 if (INSN_DEPEND (insn
) == 0)
4215 /* This is used by the function adjust_priority above. */
4217 max_priority
= MAX (INSN_PRIORITY (ready
[0]), INSN_PRIORITY (insn
));
4219 max_priority
= INSN_PRIORITY (insn
);
4221 for (link
= INSN_DEPEND (insn
); link
!= 0; link
= XEXP (link
, 1))
4223 rtx next
= XEXP (link
, 0);
4224 int cost
= insn_cost (insn
, link
, next
);
4226 INSN_TICK (next
) = MAX (INSN_TICK (next
), clock
+ cost
);
4228 if ((INSN_DEP_COUNT (next
) -= 1) == 0)
4230 int effective_cost
= INSN_TICK (next
) - clock
;
4232 /* For speculative insns, before inserting to ready/queue,
4233 check live, exception-free, and issue-delay */
4234 if (INSN_BB (next
) != target_bb
4235 && (!IS_VALID (INSN_BB (next
))
4237 || (IS_SPECULATIVE_INSN (next
)
4238 && (insn_issue_delay (next
) > 3
4239 || !check_live (next
, INSN_BB (next
))
4240 || !is_exception_free (next
, INSN_BB (next
), target_bb
)))))
4243 if (sched_verbose
>= 2)
4245 fprintf (dump
, ";;\t\tdependences resolved: insn %d ", INSN_UID (next
));
4247 if (current_nr_blocks
> 1 && INSN_BB (next
) != target_bb
)
4248 fprintf (dump
, "/b%d ", INSN_BLOCK (next
));
4250 if (effective_cost
<= 1)
4251 fprintf (dump
, "into ready\n");
4253 fprintf (dump
, "into queue with cost=%d\n", effective_cost
);
4256 /* Adjust the priority of NEXT and either put it on the ready
4257 list or queue it. */
4258 adjust_priority (next
);
4259 if (effective_cost
<= 1)
4260 ready
[n_ready
++] = next
;
4262 queue_insn (next
, effective_cost
);
4270 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4274 create_reg_dead_note (reg
, insn
)
4279 /* The number of registers killed after scheduling must be the same as the
4280 number of registers killed before scheduling. The number of REG_DEAD
4281 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4282 might become one DImode hard register REG_DEAD note, but the number of
4283 registers killed will be conserved.
4285 We carefully remove REG_DEAD notes from the dead_notes list, so that
4286 there will be none left at the end. If we run out early, then there
4287 is a bug somewhere in flow, combine and/or sched. */
4289 if (dead_notes
== 0)
4291 if (current_nr_blocks
<= 1)
4294 link
= alloc_EXPR_LIST (REG_DEAD
, NULL_RTX
, NULL_RTX
);
4298 /* Number of regs killed by REG. */
4299 int regs_killed
= (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
? 1
4300 : HARD_REGNO_NREGS (REGNO (reg
), GET_MODE (reg
)));
4301 /* Number of regs killed by REG_DEAD notes taken off the list. */
4305 reg_note_regs
= (REGNO (XEXP (link
, 0)) >= FIRST_PSEUDO_REGISTER
? 1
4306 : HARD_REGNO_NREGS (REGNO (XEXP (link
, 0)),
4307 GET_MODE (XEXP (link
, 0))));
4308 while (reg_note_regs
< regs_killed
)
4310 link
= XEXP (link
, 1);
4312 /* LINK might be zero if we killed more registers after scheduling
4313 than before, and the last hard register we kill is actually
4316 This is normal for interblock scheduling, so deal with it in
4317 that case, else abort. */
4318 if (link
== NULL_RTX
&& current_nr_blocks
<= 1)
4320 else if (link
== NULL_RTX
)
4321 link
= alloc_EXPR_LIST (REG_DEAD
, gen_rtx_REG (word_mode
, 0),
4324 reg_note_regs
+= (REGNO (XEXP (link
, 0)) >= FIRST_PSEUDO_REGISTER
? 1
4325 : HARD_REGNO_NREGS (REGNO (XEXP (link
, 0)),
4326 GET_MODE (XEXP (link
, 0))));
4328 dead_notes
= XEXP (link
, 1);
4330 /* If we took too many regs kills off, put the extra ones back. */
4331 while (reg_note_regs
> regs_killed
)
4333 rtx temp_reg
, temp_link
;
4335 temp_reg
= gen_rtx_REG (word_mode
, 0);
4336 temp_link
= alloc_EXPR_LIST (REG_DEAD
, temp_reg
, dead_notes
);
4337 dead_notes
= temp_link
;
4342 XEXP (link
, 0) = reg
;
4343 XEXP (link
, 1) = REG_NOTES (insn
);
4344 REG_NOTES (insn
) = link
;
4347 /* Subroutine on attach_deaths_insn--handles the recursive search
4348 through INSN. If SET_P is true, then x is being modified by the insn. */
4351 attach_deaths (x
, insn
, set_p
)
4358 register enum rtx_code code
;
4364 code
= GET_CODE (x
);
4376 /* Get rid of the easy cases first. */
4381 /* If the register dies in this insn, queue that note, and mark
4382 this register as needing to die. */
4383 /* This code is very similar to mark_used_1 (if set_p is false)
4384 and mark_set_1 (if set_p is true) in flow.c. */
4394 all_needed
= some_needed
= REGNO_REG_SET_P (old_live_regs
, regno
);
4395 if (regno
< FIRST_PSEUDO_REGISTER
)
4399 n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4402 int needed
= (REGNO_REG_SET_P (old_live_regs
, regno
+ n
));
4403 some_needed
|= needed
;
4404 all_needed
&= needed
;
4408 /* If it wasn't live before we started, then add a REG_DEAD note.
4409 We must check the previous lifetime info not the current info,
4410 because we may have to execute this code several times, e.g.
4411 once for a clobber (which doesn't add a note) and later
4412 for a use (which does add a note).
4414 Always make the register live. We must do this even if it was
4415 live before, because this may be an insn which sets and uses
4416 the same register, in which case the register has already been
4417 killed, so we must make it live again.
4419 Global registers are always live, and should never have a REG_DEAD
4420 note added for them, so none of the code below applies to them. */
4422 if (regno
>= FIRST_PSEUDO_REGISTER
|| ! global_regs
[regno
])
4424 /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
4425 STACK_POINTER_REGNUM, since these are always considered to be
4426 live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
4427 if (regno
!= FRAME_POINTER_REGNUM
4428 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4429 && ! (regno
== HARD_FRAME_POINTER_REGNUM
)
4431 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4432 && ! (regno
== ARG_POINTER_REGNUM
&& fixed_regs
[regno
])
4434 && regno
!= STACK_POINTER_REGNUM
)
4436 if (! all_needed
&& ! dead_or_set_p (insn
, x
))
4438 /* Check for the case where the register dying partially
4439 overlaps the register set by this insn. */
4440 if (regno
< FIRST_PSEUDO_REGISTER
4441 && HARD_REGNO_NREGS (regno
, GET_MODE (x
)) > 1)
4443 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4445 some_needed
|= dead_or_set_regno_p (insn
, regno
+ n
);
4448 /* If none of the words in X is needed, make a REG_DEAD
4449 note. Otherwise, we must make partial REG_DEAD
4452 create_reg_dead_note (x
, insn
);
4457 /* Don't make a REG_DEAD note for a part of a
4458 register that is set in the insn. */
4459 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
)) - 1;
4461 if (! REGNO_REG_SET_P (old_live_regs
, regno
+i
)
4462 && ! dead_or_set_regno_p (insn
, regno
+ i
))
4463 create_reg_dead_note (gen_rtx_REG (reg_raw_mode
[regno
+ i
],
4470 if (regno
< FIRST_PSEUDO_REGISTER
)
4472 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4475 SET_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4480 /* Recompute REG_BASIC_BLOCK as we update all the other
4481 dataflow information. */
4482 if (sched_reg_basic_block
[regno
] == REG_BLOCK_UNKNOWN
)
4483 sched_reg_basic_block
[regno
] = current_block_num
;
4484 else if (sched_reg_basic_block
[regno
] != current_block_num
)
4485 sched_reg_basic_block
[regno
] = REG_BLOCK_GLOBAL
;
4487 SET_REGNO_REG_SET (bb_live_regs
, regno
);
4494 /* Handle tail-recursive case. */
4495 attach_deaths (XEXP (x
, 0), insn
, 0);
4499 attach_deaths (SUBREG_REG (x
), insn
,
4500 set_p
&& ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
)))
4502 || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
)))
4503 == GET_MODE_SIZE (GET_MODE ((x
))))));
4506 case STRICT_LOW_PART
:
4507 attach_deaths (XEXP (x
, 0), insn
, 0);
4512 attach_deaths (XEXP (x
, 0), insn
, 0);
4513 attach_deaths (XEXP (x
, 1), insn
, 0);
4514 attach_deaths (XEXP (x
, 2), insn
, 0);
4518 /* Other cases: walk the insn. */
4519 fmt
= GET_RTX_FORMAT (code
);
4520 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4523 attach_deaths (XEXP (x
, i
), insn
, 0);
4524 else if (fmt
[i
] == 'E')
4525 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
4526 attach_deaths (XVECEXP (x
, i
, j
), insn
, 0);
4531 /* After INSN has executed, add register death notes for each register
4532 that is dead after INSN. */
4535 attach_deaths_insn (insn
)
4538 rtx x
= PATTERN (insn
);
4539 register RTX_CODE code
= GET_CODE (x
);
4544 attach_deaths (SET_SRC (x
), insn
, 0);
4546 /* A register might die here even if it is the destination, e.g.
4547 it is the target of a volatile read and is otherwise unused.
4548 Hence we must always call attach_deaths for the SET_DEST. */
4549 attach_deaths (SET_DEST (x
), insn
, 1);
4551 else if (code
== PARALLEL
)
4554 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
4556 code
= GET_CODE (XVECEXP (x
, 0, i
));
4559 attach_deaths (SET_SRC (XVECEXP (x
, 0, i
)), insn
, 0);
4561 attach_deaths (SET_DEST (XVECEXP (x
, 0, i
)), insn
, 1);
4563 /* Flow does not add REG_DEAD notes to registers that die in
4564 clobbers, so we can't either. */
4565 else if (code
!= CLOBBER
)
4566 attach_deaths (XVECEXP (x
, 0, i
), insn
, 0);
4569 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4570 MEM being clobbered, just like flow. */
4571 else if (code
== CLOBBER
&& GET_CODE (XEXP (x
, 0)) == MEM
)
4572 attach_deaths (XEXP (XEXP (x
, 0), 0), insn
, 0);
4573 /* Otherwise don't add a death note to things being clobbered. */
4574 else if (code
!= CLOBBER
)
4575 attach_deaths (x
, insn
, 0);
4577 /* Make death notes for things used in the called function. */
4578 if (GET_CODE (insn
) == CALL_INSN
)
4579 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
4580 attach_deaths (XEXP (XEXP (link
, 0), 0), insn
,
4581 GET_CODE (XEXP (link
, 0)) == CLOBBER
);
4584 /* functions for handlnig of notes */
4586 /* Delete notes beginning with INSN and put them in the chain
4587 of notes ended by NOTE_LIST.
4588 Returns the insn following the notes. */
4591 unlink_other_notes (insn
, tail
)
4594 rtx prev
= PREV_INSN (insn
);
4596 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4598 rtx next
= NEXT_INSN (insn
);
4599 /* Delete the note from its current position. */
4601 NEXT_INSN (prev
) = next
;
4603 PREV_INSN (next
) = prev
;
4605 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4606 immediately after the call they follow. We use a fake
4607 (REG_DEAD (const_int -1)) note to remember them.
4608 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4609 if (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_SETJMP
4610 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
4611 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
4612 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_BEG
4613 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_END
)
4615 /* Insert the note at the end of the notes list. */
4616 PREV_INSN (insn
) = note_list
;
4618 NEXT_INSN (note_list
) = insn
;
4627 /* Delete line notes beginning with INSN. Record line-number notes so
4628 they can be reused. Returns the insn following the notes. */
4631 unlink_line_notes (insn
, tail
)
4634 rtx prev
= PREV_INSN (insn
);
4636 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4638 rtx next
= NEXT_INSN (insn
);
4640 if (write_symbols
!= NO_DEBUG
&& NOTE_LINE_NUMBER (insn
) > 0)
4642 /* Delete the note from its current position. */
4644 NEXT_INSN (prev
) = next
;
4646 PREV_INSN (next
) = prev
;
4648 /* Record line-number notes so they can be reused. */
4649 LINE_NOTE (insn
) = insn
;
4659 /* Return the head and tail pointers of BB. */
4661 __inline
static void
4662 get_block_head_tail (bb
, headp
, tailp
)
4672 b
= BB_TO_BLOCK (bb
);
4674 /* HEAD and TAIL delimit the basic block being scheduled. */
4675 head
= basic_block_head
[b
];
4676 tail
= basic_block_end
[b
];
4678 /* Don't include any notes or labels at the beginning of the
4679 basic block, or notes at the ends of basic blocks. */
4680 while (head
!= tail
)
4682 if (GET_CODE (head
) == NOTE
)
4683 head
= NEXT_INSN (head
);
4684 else if (GET_CODE (tail
) == NOTE
)
4685 tail
= PREV_INSN (tail
);
4686 else if (GET_CODE (head
) == CODE_LABEL
)
4687 head
= NEXT_INSN (head
);
4696 /* Delete line notes from bb. Save them so they can be later restored
4697 (in restore_line_notes ()). */
4708 get_block_head_tail (bb
, &head
, &tail
);
4711 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
4714 next_tail
= NEXT_INSN (tail
);
4715 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4719 /* Farm out notes, and maybe save them in NOTE_LIST.
4720 This is needed to keep the debugger from
4721 getting completely deranged. */
4722 if (GET_CODE (insn
) == NOTE
)
4725 insn
= unlink_line_notes (insn
, next_tail
);
4731 if (insn
== next_tail
)
4737 /* Save line number notes for each insn in bb. */
4740 save_line_notes (bb
)
4746 /* We must use the true line number for the first insn in the block
4747 that was computed and saved at the start of this pass. We can't
4748 use the current line number, because scheduling of the previous
4749 block may have changed the current line number. */
4751 rtx line
= line_note_head
[BB_TO_BLOCK (bb
)];
4754 get_block_head_tail (bb
, &head
, &tail
);
4755 next_tail
= NEXT_INSN (tail
);
4757 for (insn
= basic_block_head
[BB_TO_BLOCK (bb
)];
4759 insn
= NEXT_INSN (insn
))
4760 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4763 LINE_NOTE (insn
) = line
;
4767 /* After bb was scheduled, insert line notes into the insns list. */
4770 restore_line_notes (bb
)
4773 rtx line
, note
, prev
, new;
4774 int added_notes
= 0;
4776 rtx head
, next_tail
, insn
;
4778 b
= BB_TO_BLOCK (bb
);
4780 head
= basic_block_head
[b
];
4781 next_tail
= NEXT_INSN (basic_block_end
[b
]);
4783 /* Determine the current line-number. We want to know the current
4784 line number of the first insn of the block here, in case it is
4785 different from the true line number that was saved earlier. If
4786 different, then we need a line number note before the first insn
4787 of this block. If it happens to be the same, then we don't want to
4788 emit another line number note here. */
4789 for (line
= head
; line
; line
= PREV_INSN (line
))
4790 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
4793 /* Walk the insns keeping track of the current line-number and inserting
4794 the line-number notes as needed. */
4795 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4796 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4798 /* This used to emit line number notes before every non-deleted note.
4799 However, this confuses a debugger, because line notes not separated
4800 by real instructions all end up at the same address. I can find no
4801 use for line number notes before other notes, so none are emitted. */
4802 else if (GET_CODE (insn
) != NOTE
4803 && (note
= LINE_NOTE (insn
)) != 0
4806 || NOTE_LINE_NUMBER (note
) != NOTE_LINE_NUMBER (line
)
4807 || NOTE_SOURCE_FILE (note
) != NOTE_SOURCE_FILE (line
)))
4810 prev
= PREV_INSN (insn
);
4811 if (LINE_NOTE (note
))
4813 /* Re-use the original line-number note. */
4814 LINE_NOTE (note
) = 0;
4815 PREV_INSN (note
) = prev
;
4816 NEXT_INSN (prev
) = note
;
4817 PREV_INSN (insn
) = note
;
4818 NEXT_INSN (note
) = insn
;
4823 new = emit_note_after (NOTE_LINE_NUMBER (note
), prev
);
4824 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note
);
4825 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note
);
4828 if (sched_verbose
&& added_notes
)
4829 fprintf (dump
, ";; added %d line-number notes\n", added_notes
);
4832 /* After scheduling the function, delete redundant line notes from the
4836 rm_redundant_line_notes ()
4839 rtx insn
= get_insns ();
4840 int active_insn
= 0;
4843 /* Walk the insns deleting redundant line-number notes. Many of these
4844 are already present. The remainder tend to occur at basic
4845 block boundaries. */
4846 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
4847 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4849 /* If there are no active insns following, INSN is redundant. */
4850 if (active_insn
== 0)
4853 NOTE_SOURCE_FILE (insn
) = 0;
4854 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
4856 /* If the line number is unchanged, LINE is redundant. */
4858 && NOTE_LINE_NUMBER (line
) == NOTE_LINE_NUMBER (insn
)
4859 && NOTE_SOURCE_FILE (line
) == NOTE_SOURCE_FILE (insn
))
4862 NOTE_SOURCE_FILE (line
) = 0;
4863 NOTE_LINE_NUMBER (line
) = NOTE_INSN_DELETED
;
4870 else if (!((GET_CODE (insn
) == NOTE
4871 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
4872 || (GET_CODE (insn
) == INSN
4873 && (GET_CODE (PATTERN (insn
)) == USE
4874 || GET_CODE (PATTERN (insn
)) == CLOBBER
))))
4877 if (sched_verbose
&& notes
)
4878 fprintf (dump
, ";; deleted %d line-number notes\n", notes
);
4881 /* Delete notes between head and tail and put them in the chain
4882 of notes ended by NOTE_LIST. */
4885 rm_other_notes (head
, tail
)
4893 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
4896 next_tail
= NEXT_INSN (tail
);
4897 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4901 /* Farm out notes, and maybe save them in NOTE_LIST.
4902 This is needed to keep the debugger from
4903 getting completely deranged. */
4904 if (GET_CODE (insn
) == NOTE
)
4908 insn
= unlink_other_notes (insn
, next_tail
);
4914 if (insn
== next_tail
)
4920 /* Constructor for `sometimes' data structure. */
4923 new_sometimes_live (regs_sometimes_live
, regno
, sometimes_max
)
4924 struct sometimes
*regs_sometimes_live
;
4928 register struct sometimes
*p
;
4930 /* There should never be a register greater than max_regno here. If there
4931 is, it means that a define_split has created a new pseudo reg. This
4932 is not allowed, since there will not be flow info available for any
4933 new register, so catch the error here. */
4934 if (regno
>= max_regno
)
4937 p
= ®s_sometimes_live
[sometimes_max
];
4940 p
->calls_crossed
= 0;
4942 return sometimes_max
;
4945 /* Count lengths of all regs we are currently tracking,
4946 and find new registers no longer live. */
4949 finish_sometimes_live (regs_sometimes_live
, sometimes_max
)
4950 struct sometimes
*regs_sometimes_live
;
4955 for (i
= 0; i
< sometimes_max
; i
++)
4957 register struct sometimes
*p
= ®s_sometimes_live
[i
];
4958 int regno
= p
->regno
;
4960 sched_reg_live_length
[regno
] += p
->live_length
;
4961 sched_reg_n_calls_crossed
[regno
] += p
->calls_crossed
;
4965 /* functions for computation of registers live/usage info */
4967 /* It is assumed that prior to scheduling basic_block_live_at_start (b)
4968 contains the registers that are alive at the entry to b.
4970 Two passes follow: The first pass is performed before the scheduling
4971 of a region. It scans each block of the region forward, computing
4972 the set of registers alive at the end of the basic block and
4973 discard REG_DEAD notes (done by find_pre_sched_live ()).
4975 The second path is invoked after scheduling all region blocks.
4976 It scans each block of the region backward, a block being traversed
4977 only after its succesors in the region. When the set of registers
4978 live at the end of a basic block may be changed by the scheduling
4979 (this may happen for multiple blocks region), it is computed as
4980 the union of the registers live at the start of its succesors.
4981 The last-use information is updated by inserting REG_DEAD notes.
4982 (done by find_post_sched_live ()) */
4984 /* Scan all the insns to be scheduled, removing register death notes.
4985 Register death notes end up in DEAD_NOTES.
4986 Recreate the register life information for the end of this basic
4990 find_pre_sched_live (bb
)
4993 rtx insn
, next_tail
, head
, tail
;
4994 int b
= BB_TO_BLOCK (bb
);
4996 get_block_head_tail (bb
, &head
, &tail
);
4997 COPY_REG_SET (bb_live_regs
, basic_block_live_at_start
[b
]);
4998 next_tail
= NEXT_INSN (tail
);
5000 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5002 rtx prev
, next
, link
;
5005 /* Handle register life information. */
5006 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
5008 /* See if the register gets born here. */
5009 /* We must check for registers being born before we check for
5010 registers dying. It is possible for a register to be born and
5011 die in the same insn, e.g. reading from a volatile memory
5012 location into an otherwise unused register. Such a register
5013 must be marked as dead after this insn. */
5014 if (GET_CODE (PATTERN (insn
)) == SET
5015 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
5017 sched_note_set (PATTERN (insn
), 0);
5021 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
5024 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5025 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
5026 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
5028 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 0);
5032 /* ??? This code is obsolete and should be deleted. It
5033 is harmless though, so we will leave it in for now. */
5034 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5035 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == USE
)
5036 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 0);
5039 /* Each call cobbers (makes live) all call-clobbered regs
5040 that are not global or fixed. Note that the function-value
5041 reg is a call_clobbered reg. */
5042 if (GET_CODE (insn
) == CALL_INSN
)
5045 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
5046 if (call_used_regs
[j
] && !global_regs
[j
]
5049 SET_REGNO_REG_SET (bb_live_regs
, j
);
5053 /* Need to know what registers this insn kills. */
5054 for (prev
= 0, link
= REG_NOTES (insn
); link
; link
= next
)
5056 next
= XEXP (link
, 1);
5057 if ((REG_NOTE_KIND (link
) == REG_DEAD
5058 || REG_NOTE_KIND (link
) == REG_UNUSED
)
5059 /* Verify that the REG_NOTE has a valid value. */
5060 && GET_CODE (XEXP (link
, 0)) == REG
)
5062 register int regno
= REGNO (XEXP (link
, 0));
5066 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5068 if (REG_NOTE_KIND (link
) == REG_DEAD
)
5071 XEXP (prev
, 1) = next
;
5073 REG_NOTES (insn
) = next
;
5074 XEXP (link
, 1) = dead_notes
;
5080 if (regno
< FIRST_PSEUDO_REGISTER
)
5082 int j
= HARD_REGNO_NREGS (regno
,
5083 GET_MODE (XEXP (link
, 0)));
5086 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
+j
);
5091 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
);
5099 INSN_REG_WEIGHT (insn
) = reg_weight
;
5103 /* Update register life and usage information for block bb
5104 after scheduling. Put register dead notes back in the code. */
5107 find_post_sched_live (bb
)
5114 rtx head
, tail
, prev_head
, next_tail
;
5116 register struct sometimes
*regs_sometimes_live
;
5118 b
= BB_TO_BLOCK (bb
);
5120 /* compute live regs at the end of bb as a function of its successors. */
5121 if (current_nr_blocks
> 1)
5126 first_edge
= e
= OUT_EDGES (b
);
5127 CLEAR_REG_SET (bb_live_regs
);
5134 b_succ
= TO_BLOCK (e
);
5135 IOR_REG_SET (bb_live_regs
, basic_block_live_at_start
[b_succ
]);
5138 while (e
!= first_edge
);
5141 get_block_head_tail (bb
, &head
, &tail
);
5142 next_tail
= NEXT_INSN (tail
);
5143 prev_head
= PREV_INSN (head
);
5145 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, FIRST_PSEUDO_REGISTER
, i
,
5147 sched_reg_basic_block
[i
] = REG_BLOCK_GLOBAL
;
5150 /* if the block is empty, same regs are alive at its end and its start.
5151 since this is not guaranteed after interblock scheduling, make sure they
5152 are truly identical. */
5153 if (NEXT_INSN (prev_head
) == tail
5154 && (GET_RTX_CLASS (GET_CODE (tail
)) != 'i'))
5156 if (current_nr_blocks
> 1)
5157 COPY_REG_SET (basic_block_live_at_start
[b
], bb_live_regs
);
5162 b
= BB_TO_BLOCK (bb
);
5163 current_block_num
= b
;
5165 /* Keep track of register lives. */
5166 old_live_regs
= ALLOCA_REG_SET ();
5168 = (struct sometimes
*) alloca (max_regno
* sizeof (struct sometimes
));
5171 /* initiate "sometimes" data, starting with registers live at end */
5173 COPY_REG_SET (old_live_regs
, bb_live_regs
);
5174 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, 0, j
,
5177 = new_sometimes_live (regs_sometimes_live
,
5181 /* scan insns back, computing regs live info */
5182 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
5184 /* First we kill registers set by this insn, and then we
5185 make registers used by this insn live. This is the opposite
5186 order used above because we are traversing the instructions
5189 /* Strictly speaking, we should scan REG_UNUSED notes and make
5190 every register mentioned there live, however, we will just
5191 kill them again immediately below, so there doesn't seem to
5192 be any reason why we bother to do this. */
5194 /* See if this is the last notice we must take of a register. */
5195 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5198 if (GET_CODE (PATTERN (insn
)) == SET
5199 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
5200 sched_note_set (PATTERN (insn
), 1);
5201 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
5203 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5204 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
5205 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
5206 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 1);
5209 /* This code keeps life analysis information up to date. */
5210 if (GET_CODE (insn
) == CALL_INSN
)
5212 register struct sometimes
*p
;
5214 /* A call kills all call used registers that are not
5215 global or fixed, except for those mentioned in the call
5216 pattern which will be made live again later. */
5217 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
5218 if (call_used_regs
[i
] && ! global_regs
[i
]
5221 CLEAR_REGNO_REG_SET (bb_live_regs
, i
);
5224 /* Regs live at the time of a call instruction must not
5225 go in a register clobbered by calls. Record this for
5226 all regs now live. Note that insns which are born or
5227 die in a call do not cross a call, so this must be done
5228 after the killings (above) and before the births
5230 p
= regs_sometimes_live
;
5231 for (i
= 0; i
< sometimes_max
; i
++, p
++)
5232 if (REGNO_REG_SET_P (bb_live_regs
, p
->regno
))
5233 p
->calls_crossed
+= 1;
5236 /* Make every register used live, and add REG_DEAD notes for
5237 registers which were not live before we started. */
5238 attach_deaths_insn (insn
);
5240 /* Find registers now made live by that instruction. */
5241 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs
, old_live_regs
, 0, j
,
5244 = new_sometimes_live (regs_sometimes_live
,
5247 IOR_REG_SET (old_live_regs
, bb_live_regs
);
5249 /* Count lengths of all regs we are worrying about now,
5250 and handle registers no longer live. */
5252 for (i
= 0; i
< sometimes_max
; i
++)
5254 register struct sometimes
*p
= ®s_sometimes_live
[i
];
5255 int regno
= p
->regno
;
5257 p
->live_length
+= 1;
5259 if (!REGNO_REG_SET_P (bb_live_regs
, regno
))
5261 /* This is the end of one of this register's lifetime
5262 segments. Save the lifetime info collected so far,
5263 and clear its bit in the old_live_regs entry. */
5264 sched_reg_live_length
[regno
] += p
->live_length
;
5265 sched_reg_n_calls_crossed
[regno
] += p
->calls_crossed
;
5266 CLEAR_REGNO_REG_SET (old_live_regs
, p
->regno
);
5268 /* Delete the reg_sometimes_live entry for this reg by
5269 copying the last entry over top of it. */
5270 *p
= regs_sometimes_live
[--sometimes_max
];
5271 /* ...and decrement i so that this newly copied entry
5272 will be processed. */
5278 finish_sometimes_live (regs_sometimes_live
, sometimes_max
);
5280 /* In interblock scheduling, basic_block_live_at_start may have changed. */
5281 if (current_nr_blocks
> 1)
5282 COPY_REG_SET (basic_block_live_at_start
[b
], bb_live_regs
);
5285 FREE_REG_SET (old_live_regs
);
5286 } /* find_post_sched_live */
5288 /* After scheduling the subroutine, restore information about uses of
5296 if (n_basic_blocks
> 0)
5297 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, FIRST_PSEUDO_REGISTER
, regno
,
5299 sched_reg_basic_block
[regno
]
5303 for (regno
= 0; regno
< max_regno
; regno
++)
5304 if (sched_reg_live_length
[regno
])
5308 if (REG_LIVE_LENGTH (regno
) > sched_reg_live_length
[regno
])
5310 ";; register %d life shortened from %d to %d\n",
5311 regno
, REG_LIVE_LENGTH (regno
),
5312 sched_reg_live_length
[regno
]);
5313 /* Negative values are special; don't overwrite the current
5314 reg_live_length value if it is negative. */
5315 else if (REG_LIVE_LENGTH (regno
) < sched_reg_live_length
[regno
]
5316 && REG_LIVE_LENGTH (regno
) >= 0)
5318 ";; register %d life extended from %d to %d\n",
5319 regno
, REG_LIVE_LENGTH (regno
),
5320 sched_reg_live_length
[regno
]);
5322 if (!REG_N_CALLS_CROSSED (regno
)
5323 && sched_reg_n_calls_crossed
[regno
])
5325 ";; register %d now crosses calls\n", regno
);
5326 else if (REG_N_CALLS_CROSSED (regno
)
5327 && !sched_reg_n_calls_crossed
[regno
]
5328 && REG_BASIC_BLOCK (regno
) != REG_BLOCK_GLOBAL
)
5330 ";; register %d no longer crosses calls\n", regno
);
5332 if (REG_BASIC_BLOCK (regno
) != sched_reg_basic_block
[regno
]
5333 && sched_reg_basic_block
[regno
] != REG_BLOCK_UNKNOWN
5334 && REG_BASIC_BLOCK(regno
) != REG_BLOCK_UNKNOWN
)
5336 ";; register %d changed basic block from %d to %d\n",
5337 regno
, REG_BASIC_BLOCK(regno
),
5338 sched_reg_basic_block
[regno
]);
5341 /* Negative values are special; don't overwrite the current
5342 reg_live_length value if it is negative. */
5343 if (REG_LIVE_LENGTH (regno
) >= 0)
5344 REG_LIVE_LENGTH (regno
) = sched_reg_live_length
[regno
];
5346 if (sched_reg_basic_block
[regno
] != REG_BLOCK_UNKNOWN
5347 && REG_BASIC_BLOCK(regno
) != REG_BLOCK_UNKNOWN
)
5348 REG_BASIC_BLOCK(regno
) = sched_reg_basic_block
[regno
];
5350 /* We can't change the value of reg_n_calls_crossed to zero for
5351 pseudos which are live in more than one block.
5353 This is because combine might have made an optimization which
5354 invalidated basic_block_live_at_start and reg_n_calls_crossed,
5355 but it does not update them. If we update reg_n_calls_crossed
5356 here, the two variables are now inconsistent, and this might
5357 confuse the caller-save code into saving a register that doesn't
5358 need to be saved. This is only a problem when we zero calls
5359 crossed for a pseudo live in multiple basic blocks.
5361 Alternatively, we could try to correctly update basic block live
5362 at start here in sched, but that seems complicated.
5364 Note: it is possible that a global register became local, as result
5365 of interblock motion, but will remain marked as a global register. */
5366 if (sched_reg_n_calls_crossed
[regno
]
5367 || REG_BASIC_BLOCK (regno
) != REG_BLOCK_GLOBAL
)
5368 REG_N_CALLS_CROSSED (regno
) = sched_reg_n_calls_crossed
[regno
];
5373 /* Scheduling clock, modified in schedule_block() and queue_to_ready () */
5374 static int clock_var
;
5376 /* Move insns that became ready to fire from queue to ready list. */
5379 queue_to_ready (ready
, n_ready
)
5386 q_ptr
= NEXT_Q (q_ptr
);
5388 /* Add all pending insns that can be scheduled without stalls to the
5390 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
5393 insn
= XEXP (link
, 0);
5396 if (sched_verbose
>= 2)
5397 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
5399 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
5400 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
5402 ready
[n_ready
++] = insn
;
5403 if (sched_verbose
>= 2)
5404 fprintf (dump
, "moving to ready without stalls\n");
5406 insn_queue
[q_ptr
] = 0;
5408 /* If there are no ready insns, stall until one is ready and add all
5409 of the pending insns at that point to the ready list. */
5412 register int stalls
;
5414 for (stalls
= 1; stalls
< INSN_QUEUE_SIZE
; stalls
++)
5416 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
5418 for (; link
; link
= XEXP (link
, 1))
5420 insn
= XEXP (link
, 0);
5423 if (sched_verbose
>= 2)
5424 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
5426 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
5427 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
5429 ready
[n_ready
++] = insn
;
5430 if (sched_verbose
>= 2)
5431 fprintf (dump
, "moving to ready with %d stalls\n", stalls
);
5433 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = 0;
5440 if (sched_verbose
&& stalls
)
5441 visualize_stall_cycles (BB_TO_BLOCK (target_bb
), stalls
);
5442 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
5443 clock_var
+= stalls
;
5448 /* Print the ready list for debugging purposes. Callable from debugger. */
5451 debug_ready_list (ready
, n_ready
)
5457 for (i
= 0; i
< n_ready
; i
++)
5459 fprintf (dump
, " %d", INSN_UID (ready
[i
]));
5460 if (current_nr_blocks
> 1 && INSN_BB (ready
[i
]) != target_bb
)
5461 fprintf (dump
, "/b%d", INSN_BLOCK (ready
[i
]));
5463 fprintf (dump
, "\n");
5466 /* Print names of units on which insn can/should execute, for debugging. */
5469 insn_print_units (insn
)
5473 int unit
= insn_unit (insn
);
5476 fprintf (dump
, "none");
5478 fprintf (dump
, "%s", function_units
[unit
].name
);
5481 fprintf (dump
, "[");
5482 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
5485 fprintf (dump
, "%s", function_units
[i
].name
);
5487 fprintf (dump
, " ");
5489 fprintf (dump
, "]");
5493 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5494 of a basic block. If more lines are needed, table is splitted to two.
5495 n_visual_lines is the number of lines printed so far for a block.
5496 visual_tbl contains the block visualization info.
5497 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5498 #define MAX_VISUAL_LINES 100
5503 rtx vis_no_unit
[10];
5505 /* Finds units that are in use in this fuction. Required only
5506 for visualization. */
5509 init_target_units ()
5514 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
5516 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5519 unit
= insn_unit (insn
);
5522 target_units
|= ~unit
;
5524 target_units
|= (1 << unit
);
5528 /* Return the length of the visualization table */
5531 get_visual_tbl_length ()
5537 /* compute length of one field in line */
5538 s
= (char *) alloca (INSN_LEN
+ 5);
5539 sprintf (s
, " %33s", "uname");
5542 /* compute length of one line */
5545 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5546 if (function_units
[unit
].bitmask
& target_units
)
5547 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5550 n
+= strlen ("\n") + 2;
5552 /* compute length of visualization string */
5553 return (MAX_VISUAL_LINES
* n
);
5556 /* Init block visualization debugging info */
5559 init_block_visualization ()
5561 strcpy (visual_tbl
, "");
5569 safe_concat (buf
, cur
, str
)
5574 char *end
= buf
+ BUF_LEN
- 2; /* leave room for null */
5583 while (cur
< end
&& (c
= *str
++) != '\0')
5590 /* This recognizes rtx, I classified as expressions. These are always */
5591 /* represent some action on values or results of other expression, */
5592 /* that may be stored in objects representing values. */
5595 print_exp (buf
, x
, verbose
)
5603 char *fun
= (char *)0;
5608 for (i
= 0; i
< 4; i
++)
5614 switch (GET_CODE (x
))
5617 op
[0] = XEXP (x
, 0);
5619 op
[1] = XEXP (x
, 1);
5622 op
[0] = XEXP (x
, 0);
5624 op
[1] = XEXP (x
, 1);
5628 op
[0] = XEXP (x
, 0);
5630 op
[1] = XEXP (x
, 1);
5634 op
[0] = XEXP (x
, 0);
5635 op
[1] = XEXP (x
, 1);
5639 op
[0] = XEXP (x
, 0);
5642 op
[0] = XEXP (x
, 0);
5644 op
[1] = XEXP (x
, 1);
5647 op
[0] = XEXP (x
, 0);
5649 op
[1] = XEXP (x
, 1);
5653 op
[0] = XEXP (x
, 0);
5654 op
[1] = XEXP (x
, 1);
5657 op
[0] = XEXP (x
, 0);
5659 op
[1] = XEXP (x
, 1);
5663 op
[0] = XEXP (x
, 0);
5664 op
[1] = XEXP (x
, 1);
5668 op
[0] = XEXP (x
, 0);
5669 op
[1] = XEXP (x
, 1);
5673 op
[0] = XEXP (x
, 0);
5674 op
[1] = XEXP (x
, 1);
5678 op
[0] = XEXP (x
, 0);
5679 op
[1] = XEXP (x
, 1);
5683 op
[0] = XEXP (x
, 0);
5684 op
[1] = XEXP (x
, 1);
5688 op
[0] = XEXP (x
, 0);
5691 op
[0] = XEXP (x
, 0);
5693 op
[1] = XEXP (x
, 1);
5696 op
[0] = XEXP (x
, 0);
5698 op
[1] = XEXP (x
, 1);
5701 op
[0] = XEXP (x
, 0);
5703 op
[1] = XEXP (x
, 1);
5706 op
[0] = XEXP (x
, 0);
5708 op
[1] = XEXP (x
, 1);
5711 op
[0] = XEXP (x
, 0);
5713 op
[1] = XEXP (x
, 1);
5716 op
[0] = XEXP (x
, 0);
5718 op
[1] = XEXP (x
, 1);
5721 op
[0] = XEXP (x
, 0);
5723 op
[1] = XEXP (x
, 1);
5726 op
[0] = XEXP (x
, 0);
5728 op
[1] = XEXP (x
, 1);
5732 op
[0] = XEXP (x
, 0);
5736 op
[0] = XEXP (x
, 0);
5740 op
[0] = XEXP (x
, 0);
5743 op
[0] = XEXP (x
, 0);
5745 op
[1] = XEXP (x
, 1);
5748 op
[0] = XEXP (x
, 0);
5750 op
[1] = XEXP (x
, 1);
5753 op
[0] = XEXP (x
, 0);
5755 op
[1] = XEXP (x
, 1);
5759 op
[0] = XEXP (x
, 0);
5760 op
[1] = XEXP (x
, 1);
5763 op
[0] = XEXP (x
, 0);
5765 op
[1] = XEXP (x
, 1);
5769 op
[0] = XEXP (x
, 0);
5770 op
[1] = XEXP (x
, 1);
5773 op
[0] = XEXP (x
, 0);
5775 op
[1] = XEXP (x
, 1);
5779 op
[0] = XEXP (x
, 0);
5780 op
[1] = XEXP (x
, 1);
5783 op
[0] = XEXP (x
, 0);
5785 op
[1] = XEXP (x
, 1);
5789 op
[0] = XEXP (x
, 0);
5790 op
[1] = XEXP (x
, 1);
5793 fun
= (verbose
) ? "sign_extract" : "sxt";
5794 op
[0] = XEXP (x
, 0);
5795 op
[1] = XEXP (x
, 1);
5796 op
[2] = XEXP (x
, 2);
5799 fun
= (verbose
) ? "zero_extract" : "zxt";
5800 op
[0] = XEXP (x
, 0);
5801 op
[1] = XEXP (x
, 1);
5802 op
[2] = XEXP (x
, 2);
5805 fun
= (verbose
) ? "sign_extend" : "sxn";
5806 op
[0] = XEXP (x
, 0);
5809 fun
= (verbose
) ? "zero_extend" : "zxn";
5810 op
[0] = XEXP (x
, 0);
5813 fun
= (verbose
) ? "float_extend" : "fxn";
5814 op
[0] = XEXP (x
, 0);
5817 fun
= (verbose
) ? "trunc" : "trn";
5818 op
[0] = XEXP (x
, 0);
5820 case FLOAT_TRUNCATE
:
5821 fun
= (verbose
) ? "float_trunc" : "ftr";
5822 op
[0] = XEXP (x
, 0);
5825 fun
= (verbose
) ? "float" : "flt";
5826 op
[0] = XEXP (x
, 0);
5828 case UNSIGNED_FLOAT
:
5829 fun
= (verbose
) ? "uns_float" : "ufl";
5830 op
[0] = XEXP (x
, 0);
5834 op
[0] = XEXP (x
, 0);
5837 fun
= (verbose
) ? "uns_fix" : "ufx";
5838 op
[0] = XEXP (x
, 0);
5842 op
[0] = XEXP (x
, 0);
5846 op
[0] = XEXP (x
, 0);
5849 op
[0] = XEXP (x
, 0);
5853 op
[0] = XEXP (x
, 0);
5858 op
[0] = XEXP (x
, 0);
5862 op
[1] = XEXP (x
, 1);
5867 op
[0] = XEXP (x
, 0);
5869 op
[1] = XEXP (x
, 1);
5871 op
[2] = XEXP (x
, 2);
5876 op
[0] = TRAP_CONDITION (x
);
5879 case UNSPEC_VOLATILE
:
5881 cur
= safe_concat (buf
, cur
, "unspec");
5882 if (GET_CODE (x
) == UNSPEC_VOLATILE
)
5883 cur
= safe_concat (buf
, cur
, "/v");
5884 cur
= safe_concat (buf
, cur
, "[");
5886 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5888 print_pattern (tmp
, XVECEXP (x
, 0, i
), verbose
);
5889 cur
= safe_concat (buf
, cur
, sep
);
5890 cur
= safe_concat (buf
, cur
, tmp
);
5893 cur
= safe_concat (buf
, cur
, "] ");
5894 sprintf (tmp
, "%d", XINT (x
, 1));
5895 cur
= safe_concat (buf
, cur
, tmp
);
5899 /* if (verbose) debug_rtx (x); */
5900 st
[0] = GET_RTX_NAME (x
);
5904 /* Print this as a function? */
5907 cur
= safe_concat (buf
, cur
, fun
);
5908 cur
= safe_concat (buf
, cur
, "(");
5911 for (i
= 0; i
< 4; i
++)
5914 cur
= safe_concat (buf
, cur
, st
[i
]);
5919 cur
= safe_concat (buf
, cur
, ",");
5921 print_value (tmp
, op
[i
], verbose
);
5922 cur
= safe_concat (buf
, cur
, tmp
);
5927 cur
= safe_concat (buf
, cur
, ")");
5930 /* Prints rtxes, i customly classified as values. They're constants, */
5931 /* registers, labels, symbols and memory accesses. */
5934 print_value (buf
, x
, verbose
)
5942 switch (GET_CODE (x
))
5945 sprintf (t
, "0x%lx", (long)INTVAL (x
));
5946 cur
= safe_concat (buf
, cur
, t
);
5949 sprintf (t
, "<0x%lx,0x%lx>", (long)XWINT (x
, 2), (long)XWINT (x
, 3));
5950 cur
= safe_concat (buf
, cur
, t
);
5953 cur
= safe_concat (buf
, cur
, "\"");
5954 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
5955 cur
= safe_concat (buf
, cur
, "\"");
5958 cur
= safe_concat (buf
, cur
, "`");
5959 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
5960 cur
= safe_concat (buf
, cur
, "'");
5963 sprintf (t
, "L%d", INSN_UID (XEXP (x
, 0)));
5964 cur
= safe_concat (buf
, cur
, t
);
5967 print_value (t
, XEXP (x
, 0), verbose
);
5968 cur
= safe_concat (buf
, cur
, "const(");
5969 cur
= safe_concat (buf
, cur
, t
);
5970 cur
= safe_concat (buf
, cur
, ")");
5973 print_value (t
, XEXP (x
, 0), verbose
);
5974 cur
= safe_concat (buf
, cur
, "high(");
5975 cur
= safe_concat (buf
, cur
, t
);
5976 cur
= safe_concat (buf
, cur
, ")");
5979 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
)
5981 int c
= reg_names
[ REGNO (x
) ][0];
5982 if (c
>= '0' && c
<= '9')
5983 cur
= safe_concat (buf
, cur
, "%");
5985 cur
= safe_concat (buf
, cur
, reg_names
[ REGNO (x
) ]);
5989 sprintf (t
, "r%d", REGNO (x
));
5990 cur
= safe_concat (buf
, cur
, t
);
5994 print_value (t
, SUBREG_REG (x
), verbose
);
5995 cur
= safe_concat (buf
, cur
, t
);
5996 sprintf (t
, "#%d", t
, SUBREG_WORD (x
));
5997 cur
= safe_concat (buf
, cur
, t
);
6000 cur
= safe_concat (buf
, cur
, "scratch");
6003 cur
= safe_concat (buf
, cur
, "cc0");
6006 cur
= safe_concat (buf
, cur
, "pc");
6009 print_value (t
, XEXP (x
, 0), verbose
);
6010 cur
= safe_concat (buf
, cur
, "[");
6011 cur
= safe_concat (buf
, cur
, t
);
6012 cur
= safe_concat (buf
, cur
, "]");
6015 print_exp (t
, x
, verbose
);
6016 cur
= safe_concat (buf
, cur
, t
);
6021 /* The next step in insn detalization, its pattern recognition */
6024 print_pattern (buf
, x
, verbose
)
6029 char t1
[BUF_LEN
], t2
[BUF_LEN
], t3
[BUF_LEN
];
6031 switch (GET_CODE (x
))
6034 print_value (t1
, SET_DEST (x
), verbose
);
6035 print_value (t2
, SET_SRC (x
), verbose
);
6036 sprintf (buf
, "%s=%s", t1
, t2
);
6039 sprintf (buf
, "return");
6042 print_exp (buf
, x
, verbose
);
6045 print_value (t1
, XEXP (x
, 0), verbose
);
6046 sprintf (buf
, "clobber %s", t1
);
6049 print_value (t1
, XEXP (x
, 0), verbose
);
6050 sprintf (buf
, "use %s", t1
);
6057 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6059 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6060 sprintf (t3
, "%s%s;", t1
, t2
);
6063 sprintf (buf
, "%s}", t1
);
6070 sprintf (t1
, "%%{");
6071 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6073 print_insn (t2
, XVECEXP (x
, 0, i
), verbose
);
6074 sprintf (t3
, "%s%s;", t1
, t2
);
6077 sprintf (buf
, "%s%%}", t1
);
6081 sprintf (buf
, "asm {%s}", XSTR (x
, 0));
6086 print_value (buf
, XEXP (x
, 0), verbose
);
6089 print_value (t1
, TRAP_CONDITION (x
), verbose
);
6090 sprintf (buf
, "trap_if %s", t1
);
6096 sprintf (t1
, "unspec{");
6097 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6099 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6100 sprintf (t3
, "%s%s;", t1
, t2
);
6103 sprintf (buf
, "%s}", t1
);
6106 case UNSPEC_VOLATILE
:
6110 sprintf (t1
, "unspec/v{");
6111 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6113 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6114 sprintf (t3
, "%s%s;", t1
, t2
);
6117 sprintf (buf
, "%s}", t1
);
6121 print_value (buf
, x
, verbose
);
6123 } /* print_pattern */
6125 /* This is the main function in rtl visualization mechanism. It
6126 accepts an rtx and tries to recognize it as an insn, then prints it
6127 properly in human readable form, resembling assembler mnemonics. */
6128 /* For every insn it prints its UID and BB the insn belongs */
6129 /* too. (probably the last "option" should be extended somehow, since */
6130 /* it depends now on sched.c inner variables ...) */
6133 print_insn (buf
, x
, verbose
)
6141 switch (GET_CODE (x
))
6144 print_pattern (t
, PATTERN (x
), verbose
);
6146 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (x
),
6149 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
6152 print_pattern (t
, PATTERN (x
), verbose
);
6154 sprintf (buf
, "b%d: i% 4d: jump %s", INSN_BB (x
),
6157 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
6161 if (GET_CODE (x
) == PARALLEL
)
6163 x
= XVECEXP (x
, 0, 0);
6164 print_pattern (t
, x
, verbose
);
6167 strcpy (t
, "call <...>");
6169 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (insn
),
6170 INSN_UID (insn
), t
);
6172 sprintf (buf
, "%-4d %s", INSN_UID (insn
), t
);
6175 sprintf (buf
, "L%d:", INSN_UID (x
));
6178 sprintf (buf
, "i% 4d: barrier", INSN_UID (x
));
6181 if (NOTE_LINE_NUMBER (x
) > 0)
6182 sprintf (buf
, "%4d note \"%s\" %d", INSN_UID (x
),
6183 NOTE_SOURCE_FILE (x
), NOTE_LINE_NUMBER (x
));
6185 sprintf (buf
, "%4d %s", INSN_UID (x
),
6186 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x
)));
6191 sprintf (buf
, "Not an INSN at all\n");
6195 sprintf (buf
, "i%-4d <What?>", INSN_UID (x
));
6200 print_insn_chain (rtx_first
)
6203 register rtx tmp_rtx
;
6206 strcpy (str
, "(nil)\n");
6208 switch (GET_CODE (rtx_first
))
6216 for (tmp_rtx
= rtx_first
; tmp_rtx
!= NULL
;
6217 tmp_rtx
= NEXT_INSN (tmp_rtx
))
6219 print_insn (str
, tmp_rtx
, 0);
6220 printf ("%s\n", str
);
6224 print_insn (str
, rtx_first
, 0);
6225 printf ("%s\n", str
);
6227 } /* print_insn_chain */
6229 /* Print visualization debugging info */
6232 print_block_visualization (b
, s
)
6239 fprintf (dump
, "\n;; ==================== scheduling visualization for block %d %s \n", b
, s
);
6241 /* Print names of units */
6242 fprintf (dump
, ";; %-8s", "clock");
6243 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6244 if (function_units
[unit
].bitmask
& target_units
)
6245 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6246 fprintf (dump
, " %-33s", function_units
[unit
].name
);
6247 fprintf (dump
, " %-8s\n", "no-unit");
6249 fprintf (dump
, ";; %-8s", "=====");
6250 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6251 if (function_units
[unit
].bitmask
& target_units
)
6252 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6253 fprintf (dump
, " %-33s", "==============================");
6254 fprintf (dump
, " %-8s\n", "=======");
6256 /* Print insns in each cycle */
6257 fprintf (dump
, "%s\n", visual_tbl
);
6260 /* Print insns in the 'no_unit' column of visualization */
6263 visualize_no_unit (insn
)
6266 vis_no_unit
[n_vis_no_unit
] = insn
;
6270 /* Print insns scheduled in clock, for visualization. */
6273 visualize_scheduled_insns (b
, clock
)
6278 /* if no more room, split table into two */
6279 if (n_visual_lines
>= MAX_VISUAL_LINES
)
6281 print_block_visualization (b
, "(incomplete)");
6282 init_block_visualization ();
6287 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; %-8d", clock
);
6288 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6289 if (function_units
[unit
].bitmask
& target_units
)
6290 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6292 int instance
= unit
+ i
* FUNCTION_UNITS_SIZE
;
6293 rtx insn
= unit_last_insn
[instance
];
6295 /* print insns that still keep the unit busy */
6297 actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
6300 print_insn (str
, insn
, 0);
6301 str
[INSN_LEN
] = '\0';
6302 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", str
);
6305 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", "------------------------------");
6308 /* print insns that are not assigned to any unit */
6309 for (i
= 0; i
< n_vis_no_unit
; i
++)
6310 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-8d",
6311 INSN_UID (vis_no_unit
[i
]));
6314 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
6317 /* Print stalled cycles */
6320 visualize_stall_cycles (b
, stalls
)
6325 /* if no more room, split table into two */
6326 if (n_visual_lines
>= MAX_VISUAL_LINES
)
6328 print_block_visualization (b
, "(incomplete)");
6329 init_block_visualization ();
6334 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; ");
6335 for (i
= 0; i
< stalls
; i
++)
6336 sprintf (visual_tbl
+ strlen (visual_tbl
), ".");
6337 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
6340 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn */
6343 move_insn1 (insn
, last
)
6346 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
6347 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
6349 NEXT_INSN (insn
) = NEXT_INSN (last
);
6350 PREV_INSN (NEXT_INSN (last
)) = insn
;
6352 NEXT_INSN (last
) = insn
;
6353 PREV_INSN (insn
) = last
;
6358 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
6359 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
6360 NOTEs. The REG_DEAD note following first one is contains the saved
6361 value for NOTE_BLOCK_NUMBER which is useful for
6362 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
6363 output by the instruction scheduler. Return the new value of LAST. */
6366 reemit_notes (insn
, last
)
6373 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
6375 if (REG_NOTE_KIND (note
) == REG_DEAD
6376 && GET_CODE (XEXP (note
, 0)) == CONST_INT
)
6378 if (INTVAL (XEXP (note
, 0)) == NOTE_INSN_SETJMP
)
6380 retval
= emit_note_after (INTVAL (XEXP (note
, 0)), insn
);
6381 CONST_CALL_P (retval
) = CONST_CALL_P (note
);
6382 remove_note (insn
, note
);
6383 note
= XEXP (note
, 1);
6387 last
= emit_note_before (INTVAL (XEXP (note
, 0)), last
);
6388 remove_note (insn
, note
);
6389 note
= XEXP (note
, 1);
6390 NOTE_BLOCK_NUMBER (last
) = INTVAL (XEXP (note
, 0));
6392 remove_note (insn
, note
);
6398 /* Move INSN, and all insns which should be issued before it,
6399 due to SCHED_GROUP_P flag. Reemit notes if needed.
6401 Return the last insn emitted by the scheduler, which is the
6402 return value from the first call to reemit_notes. */
6405 move_insn (insn
, last
)
6410 /* If INSN has SCHED_GROUP_P set, then issue it and any other
6411 insns with SCHED_GROUP_P set first. */
6412 while (SCHED_GROUP_P (insn
))
6414 rtx prev
= PREV_INSN (insn
);
6416 /* Move a SCHED_GROUP_P insn. */
6417 move_insn1 (insn
, last
);
6418 /* If this is the first call to reemit_notes, then record
6419 its return value. */
6420 if (retval
== NULL_RTX
)
6421 retval
= reemit_notes (insn
, insn
);
6423 reemit_notes (insn
, insn
);
6427 /* Now move the first non SCHED_GROUP_P insn. */
6428 move_insn1 (insn
, last
);
6430 /* If this is the first call to reemit_notes, then record
6431 its return value. */
6432 if (retval
== NULL_RTX
)
6433 retval
= reemit_notes (insn
, insn
);
6435 reemit_notes (insn
, insn
);
6440 /* Return an insn which represents a SCHED_GROUP, which is
6441 the last insn in the group. */
6452 insn
= next_nonnote_insn (insn
);
6454 while (insn
&& SCHED_GROUP_P (insn
) && (GET_CODE (insn
) != CODE_LABEL
));
6459 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
6460 possibly bringing insns from subsequent blocks in the same region.
6461 Return number of insns scheduled. */
6464 schedule_block (bb
, rgn_n_insns
)
6468 /* Local variables. */
6475 /* flow block of this bb */
6476 int b
= BB_TO_BLOCK (bb
);
6478 /* target_n_insns == number of insns in b before scheduling starts.
6479 sched_target_n_insns == how many of b's insns were scheduled.
6480 sched_n_insns == how many insns were scheduled in b */
6481 int target_n_insns
= 0;
6482 int sched_target_n_insns
= 0;
6483 int sched_n_insns
= 0;
6485 #define NEED_NOTHING 0
6490 /* head/tail info for this block */
6497 /* We used to have code to avoid getting parameters moved from hard
6498 argument registers into pseudos.
6500 However, it was removed when it proved to be of marginal benefit
6501 and caused problems because schedule_block and compute_forward_dependences
6502 had different notions of what the "head" insn was. */
6503 get_block_head_tail (bb
, &head
, &tail
);
6505 /* Interblock scheduling could have moved the original head insn from this
6506 block into a proceeding block. This may also cause schedule_block and
6507 compute_forward_dependences to have different notions of what the
6510 If the interblock movement happened to make this block start with
6511 some notes (LOOP, EH or SETJMP) before the first real insn, then
6512 HEAD will have various special notes attached to it which must be
6513 removed so that we don't end up with extra copies of the notes. */
6514 if (GET_RTX_CLASS (GET_CODE (head
)) == 'i')
6518 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
6519 if (REG_NOTE_KIND (note
) == REG_DEAD
6520 && GET_CODE (XEXP (note
, 0)) == CONST_INT
)
6521 remove_note (head
, note
);
6524 next_tail
= NEXT_INSN (tail
);
6525 prev_head
= PREV_INSN (head
);
6527 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6528 to schedule this block. */
6530 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6531 return (sched_n_insns
);
6536 fprintf (dump
, ";; ======================================================\n");
6538 ";; -- basic block %d from %d to %d -- %s reload\n",
6539 b
, INSN_UID (basic_block_head
[b
]),
6540 INSN_UID (basic_block_end
[b
]),
6541 (reload_completed
? "after" : "before"));
6542 fprintf (dump
, ";; ======================================================\n");
6543 if (sched_debug_count
>= 0)
6544 fprintf (dump
, ";;\t -- sched_debug_count=%d\n", sched_debug_count
);
6545 fprintf (dump
, "\n");
6547 visual_tbl
= (char *) alloca (get_visual_tbl_length ());
6548 init_block_visualization ();
6551 /* remove remaining note insns from the block, save them in
6552 note_list. These notes are restored at the end of
6553 schedule_block (). */
6555 rm_other_notes (head
, tail
);
6559 /* prepare current target block info */
6560 if (current_nr_blocks
> 1)
6562 candidate_table
= (candidate
*) alloca (current_nr_blocks
* sizeof (candidate
));
6565 /* ??? It is not clear why bblst_size is computed this way. The original
6566 number was clearly too small as it resulted in compiler failures.
6567 Multiplying by the original number by 2 (to account for update_bbs
6568 members) seems to be a reasonable solution. */
6569 /* ??? Or perhaps there is a bug somewhere else in this file? */
6570 bblst_size
= (current_nr_blocks
- bb
) * rgn_nr_edges
* 2;
6571 bblst_table
= (int *) alloca (bblst_size
* sizeof (int));
6573 bitlst_table_last
= 0;
6574 bitlst_table_size
= rgn_nr_edges
;
6575 bitlst_table
= (int *) alloca (rgn_nr_edges
* sizeof (int));
6577 compute_trg_info (bb
);
6582 /* Allocate the ready list */
6583 ready
= (rtx
*) alloca ((rgn_n_insns
+ 1) * sizeof (rtx
));
6585 /* Print debugging information. */
6586 if (sched_verbose
>= 5)
6587 debug_dependencies ();
6590 /* Initialize ready list with all 'ready' insns in target block.
6591 Count number of insns in the target block being scheduled. */
6593 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
6597 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6599 next
= NEXT_INSN (insn
);
6601 if (INSN_DEP_COUNT (insn
) == 0
6602 && (SCHED_GROUP_P (next
) == 0 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
6603 ready
[n_ready
++] = insn
;
6604 if (!(SCHED_GROUP_P (insn
)))
6608 /* Add to ready list all 'ready' insns in valid source blocks.
6609 For speculative insns, check-live, exception-free, and
6611 for (bb_src
= bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
6612 if (IS_VALID (bb_src
))
6618 get_block_head_tail (bb_src
, &head
, &tail
);
6619 src_next_tail
= NEXT_INSN (tail
);
6623 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6626 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
6628 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6631 if (!CANT_MOVE (insn
)
6632 && (!IS_SPECULATIVE_INSN (insn
)
6633 || (insn_issue_delay (insn
) <= 3
6634 && check_live (insn
, bb_src
)
6635 && is_exception_free (insn
, bb_src
, target_bb
))))
6640 next
= NEXT_INSN (insn
);
6641 if (INSN_DEP_COUNT (insn
) == 0
6642 && (SCHED_GROUP_P (next
) == 0
6643 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
6644 ready
[n_ready
++] = insn
;
6649 /* no insns scheduled in this block yet */
6650 last_scheduled_insn
= 0;
6652 /* Sort the ready list */
6653 SCHED_SORT (ready
, n_ready
);
6655 if (sched_verbose
>= 2)
6657 fprintf (dump
, ";;\t\tReady list initially: ");
6658 debug_ready_list (ready
, n_ready
);
6661 /* Q_SIZE is the total number of insns in the queue. */
6665 bzero ((char *) insn_queue
, sizeof (insn_queue
));
6667 /* We start inserting insns after PREV_HEAD. */
6670 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6671 new_needs
= (NEXT_INSN (prev_head
) == basic_block_head
[b
]
6672 ? NEED_HEAD
: NEED_NOTHING
);
6673 if (PREV_INSN (next_tail
) == basic_block_end
[b
])
6674 new_needs
|= NEED_TAIL
;
6676 /* loop until all the insns in BB are scheduled. */
6677 while (sched_target_n_insns
< target_n_insns
)
6681 #ifdef INTERBLOCK_DEBUG
6682 if (sched_debug_count
== 0)
6687 /* Add to the ready list all pending insns that can be issued now.
6688 If there are no ready insns, increment clock until one
6689 is ready and add all pending insns at that point to the ready
6691 n_ready
= queue_to_ready (ready
, n_ready
);
6696 if (sched_verbose
>= 2)
6698 fprintf (dump
, ";;\t\tReady list after queue_to_ready: ");
6699 debug_ready_list (ready
, n_ready
);
6702 /* Sort the ready list. */
6703 SCHED_SORT (ready
, n_ready
);
6707 fprintf (dump
, ";;\tReady list (t =%3d): ", clock_var
);
6708 debug_ready_list (ready
, n_ready
);
6711 /* Issue insns from ready list.
6712 It is important to count down from n_ready, because n_ready may change
6713 as insns are issued. */
6714 can_issue_more
= issue_rate
;
6715 for (i
= n_ready
- 1; i
>= 0 && can_issue_more
; i
--)
6717 rtx insn
= ready
[i
];
6718 int cost
= actual_hazard (insn_unit (insn
), insn
, clock_var
, 0);
6722 queue_insn (insn
, cost
);
6723 ready
[i
] = ready
[--n_ready
]; /* remove insn from ready list */
6727 #ifdef INTERBLOCK_DEBUG
6728 if (sched_debug_count
== 0)
6732 /* an interblock motion? */
6733 if (INSN_BB (insn
) != target_bb
)
6737 if (IS_SPECULATIVE_INSN (insn
))
6740 if (!check_live (insn
, INSN_BB (insn
)))
6742 /* speculative motion, live check failed, remove
6743 insn from ready list */
6744 ready
[i
] = ready
[--n_ready
];
6747 update_live (insn
, INSN_BB (insn
));
6749 /* for speculative load, mark insns fed by it. */
6750 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
6751 set_spec_fed (insn
);
6758 while (SCHED_GROUP_P (temp
))
6759 temp
= PREV_INSN (temp
);
6761 /* Update source block boundaries. */
6762 b1
= INSN_BLOCK (temp
);
6763 if (temp
== basic_block_head
[b1
]
6764 && insn
== basic_block_end
[b1
])
6766 /* We moved all the insns in the basic block.
6767 Emit a note after the last insn and update the
6768 begin/end boundaries to point to the note. */
6769 emit_note_after (NOTE_INSN_DELETED
, insn
);
6770 basic_block_end
[b1
] = NEXT_INSN (insn
);
6771 basic_block_head
[b1
] = NEXT_INSN (insn
);
6773 else if (insn
== basic_block_end
[b1
])
6775 /* We took insns from the end of the basic block,
6776 so update the end of block boundary so that it
6777 points to the first insn we did not move. */
6778 basic_block_end
[b1
] = PREV_INSN (temp
);
6780 else if (temp
== basic_block_head
[b1
])
6782 /* We took insns from the start of the basic block,
6783 so update the start of block boundary so that
6784 it points to the first insn we did not move. */
6785 basic_block_head
[b1
] = NEXT_INSN (insn
);
6790 /* in block motion */
6791 sched_target_n_insns
++;
6794 last_scheduled_insn
= insn
;
6795 last
= move_insn (insn
, last
);
6800 #ifdef INTERBLOCK_DEBUG
6801 if (sched_debug_count
> 0)
6802 sched_debug_count
--;
6805 n_ready
= schedule_insn (insn
, ready
, n_ready
, clock_var
);
6807 /* remove insn from ready list */
6808 ready
[i
] = ready
[--n_ready
];
6810 /* close this block after scheduling its jump */
6811 if (GET_CODE (last_scheduled_insn
) == JUMP_INSN
)
6819 visualize_scheduled_insns (b
, clock_var
);
6820 #ifdef INTERBLOCK_DEBUG
6821 if (sched_debug_count
== 0)
6822 fprintf (dump
, "........ sched_debug_count == 0 .................\n");
6830 fprintf (dump
, ";;\tReady list (final): ");
6831 debug_ready_list (ready
, n_ready
);
6832 print_block_visualization (b
, "");
6835 /* Sanity check -- queue must be empty now. Meaningless if region has
6836 multiple bbs, or if scheduling stopped by sched_debug_count. */
6837 if (current_nr_blocks
> 1)
6838 #ifdef INTERBLOCK_DEBUG
6839 if (sched_debug_count
!= 0)
6841 if (!flag_schedule_interblock
&& q_size
!= 0)
6844 /* update head/tail boundaries. */
6845 head
= NEXT_INSN (prev_head
);
6848 #ifdef INTERBLOCK_DEBUG
6849 if (sched_debug_count
== 0)
6850 /* compensate for stopping scheduling prematurely */
6851 for (i
= sched_target_n_insns
; i
< target_n_insns
; i
++)
6852 tail
= move_insn (group_leader (NEXT_INSN (tail
)), tail
);
6855 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6856 previously found among the insns. Insert them at the beginning
6860 rtx note_head
= note_list
;
6862 while (PREV_INSN (note_head
))
6864 note_head
= PREV_INSN (note_head
);
6867 PREV_INSN (note_head
) = PREV_INSN (head
);
6868 NEXT_INSN (PREV_INSN (head
)) = note_head
;
6869 PREV_INSN (head
) = note_list
;
6870 NEXT_INSN (note_list
) = head
;
6874 /* update target block boundaries. */
6875 if (new_needs
& NEED_HEAD
)
6876 basic_block_head
[b
] = head
;
6878 if (new_needs
& NEED_TAIL
)
6879 basic_block_end
[b
] = tail
;
6884 fprintf (dump
, ";; total time = %d\n;; new basic block head = %d\n",
6885 clock_var
, INSN_UID (basic_block_head
[b
]));
6886 fprintf (dump
, ";; new basic block end = %d\n\n",
6887 INSN_UID (basic_block_end
[b
]));
6890 return (sched_n_insns
);
6891 } /* schedule_block () */
6894 /* print the bit-set of registers, S. callable from debugger */
6897 debug_reg_vector (s
)
6902 EXECUTE_IF_SET_IN_REG_SET (s
, 0, regno
,
6904 fprintf (dump
, " %d", regno
);
6907 fprintf (dump
, "\n");
6910 /* Use the backward dependences from LOG_LINKS to build
6911 forward dependences in INSN_DEPEND. */
6914 compute_block_forward_dependences (bb
)
6920 enum reg_note dep_type
;
6922 get_block_head_tail (bb
, &head
, &tail
);
6923 next_tail
= NEXT_INSN (tail
);
6924 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
6926 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6929 insn
= group_leader (insn
);
6931 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
6933 rtx x
= group_leader (XEXP (link
, 0));
6936 if (x
!= XEXP (link
, 0))
6939 /* Ignore dependences upon deleted insn */
6940 if (GET_CODE (x
) == NOTE
|| INSN_DELETED_P (x
))
6942 if (find_insn_list (insn
, INSN_DEPEND (x
)))
6945 new_link
= alloc_INSN_LIST (insn
, INSN_DEPEND (x
));
6947 dep_type
= REG_NOTE_KIND (link
);
6948 PUT_REG_NOTE_KIND (new_link
, dep_type
);
6950 INSN_DEPEND (x
) = new_link
;
6951 INSN_DEP_COUNT (insn
) += 1;
6956 /* Initialize variables for region data dependence analysis.
6957 n_bbs is the number of region blocks */
6959 __inline
static void
6960 init_rgn_data_dependences (n_bbs
)
6965 /* variables for which one copy exists for each block */
6966 bzero ((char *) bb_pending_read_insns
, n_bbs
* sizeof (rtx
));
6967 bzero ((char *) bb_pending_read_mems
, n_bbs
* sizeof (rtx
));
6968 bzero ((char *) bb_pending_write_insns
, n_bbs
* sizeof (rtx
));
6969 bzero ((char *) bb_pending_write_mems
, n_bbs
* sizeof (rtx
));
6970 bzero ((char *) bb_pending_lists_length
, n_bbs
* sizeof (rtx
));
6971 bzero ((char *) bb_last_pending_memory_flush
, n_bbs
* sizeof (rtx
));
6972 bzero ((char *) bb_last_function_call
, n_bbs
* sizeof (rtx
));
6973 bzero ((char *) bb_sched_before_next_call
, n_bbs
* sizeof (rtx
));
6975 /* Create an insn here so that we can hang dependencies off of it later. */
6976 for (bb
= 0; bb
< n_bbs
; bb
++)
6978 bb_sched_before_next_call
[bb
] =
6979 gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
6980 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
6981 LOG_LINKS (bb_sched_before_next_call
[bb
]) = 0;
6985 /* Add dependences so that branches are scheduled to run last in their block */
6988 add_branch_dependences (head
, tail
)
6994 /* For all branches, calls, uses, and cc0 setters, force them to remain
6995 in order at the end of the block by adding dependencies and giving
6996 the last a high priority. There may be notes present, and prev_head
6999 Branches must obviously remain at the end. Calls should remain at the
7000 end since moving them results in worse register allocation. Uses remain
7001 at the end to ensure proper register allocation. cc0 setters remaim
7002 at the end because they can't be moved away from their cc0 user. */
7005 while (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
7006 || (GET_CODE (insn
) == INSN
7007 && (GET_CODE (PATTERN (insn
)) == USE
7009 || sets_cc0_p (PATTERN (insn
))
7012 || GET_CODE (insn
) == NOTE
)
7014 if (GET_CODE (insn
) != NOTE
)
7017 && !find_insn_list (insn
, LOG_LINKS (last
)))
7019 add_dependence (last
, insn
, REG_DEP_ANTI
);
7020 INSN_REF_COUNT (insn
)++;
7023 CANT_MOVE (insn
) = 1;
7026 /* Skip over insns that are part of a group.
7027 Make each insn explicitly depend on the previous insn.
7028 This ensures that only the group header will ever enter
7029 the ready queue (and, when scheduled, will automatically
7030 schedule the SCHED_GROUP_P block). */
7031 while (SCHED_GROUP_P (insn
))
7033 rtx temp
= prev_nonnote_insn (insn
);
7034 add_dependence (insn
, temp
, REG_DEP_ANTI
);
7039 /* Don't overrun the bounds of the basic block. */
7043 insn
= PREV_INSN (insn
);
7046 /* make sure these insns are scheduled last in their block */
7049 while (insn
!= head
)
7051 insn
= prev_nonnote_insn (insn
);
7053 if (INSN_REF_COUNT (insn
) != 0)
7056 if (!find_insn_list (last
, LOG_LINKS (insn
)))
7057 add_dependence (last
, insn
, REG_DEP_ANTI
);
7058 INSN_REF_COUNT (insn
) = 1;
7060 /* Skip over insns that are part of a group. */
7061 while (SCHED_GROUP_P (insn
))
7062 insn
= prev_nonnote_insn (insn
);
7066 /* Compute bacward dependences inside BB. In a multiple blocks region:
7067 (1) a bb is analyzed after its predecessors, and (2) the lists in
7068 effect at the end of bb (after analyzing for bb) are inherited by
7071 Specifically for reg-reg data dependences, the block insns are
7072 scanned by sched_analyze () top-to-bottom. Two lists are
7073 naintained by sched_analyze (): reg_last_defs[] for register DEFs,
7074 and reg_last_uses[] for register USEs.
7076 When analysis is completed for bb, we update for its successors:
7077 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7078 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7080 The mechanism for computing mem-mem data dependence is very
7081 similar, and the result is interblock dependences in the region. */
7084 compute_block_backward_dependences (bb
)
7090 int max_reg
= max_reg_num ();
7092 b
= BB_TO_BLOCK (bb
);
7094 if (current_nr_blocks
== 1)
7096 reg_last_uses
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7097 reg_last_sets
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7099 bzero ((char *) reg_last_uses
, max_reg
* sizeof (rtx
));
7100 bzero ((char *) reg_last_sets
, max_reg
* sizeof (rtx
));
7102 pending_read_insns
= 0;
7103 pending_read_mems
= 0;
7104 pending_write_insns
= 0;
7105 pending_write_mems
= 0;
7106 pending_lists_length
= 0;
7107 last_function_call
= 0;
7108 last_pending_memory_flush
= 0;
7109 sched_before_next_call
7110 = gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
7111 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
7112 LOG_LINKS (sched_before_next_call
) = 0;
7116 reg_last_uses
= bb_reg_last_uses
[bb
];
7117 reg_last_sets
= bb_reg_last_sets
[bb
];
7119 pending_read_insns
= bb_pending_read_insns
[bb
];
7120 pending_read_mems
= bb_pending_read_mems
[bb
];
7121 pending_write_insns
= bb_pending_write_insns
[bb
];
7122 pending_write_mems
= bb_pending_write_mems
[bb
];
7123 pending_lists_length
= bb_pending_lists_length
[bb
];
7124 last_function_call
= bb_last_function_call
[bb
];
7125 last_pending_memory_flush
= bb_last_pending_memory_flush
[bb
];
7127 sched_before_next_call
= bb_sched_before_next_call
[bb
];
7130 /* do the analysis for this block */
7131 get_block_head_tail (bb
, &head
, &tail
);
7132 sched_analyze (head
, tail
);
7133 add_branch_dependences (head
, tail
);
7135 if (current_nr_blocks
> 1)
7138 int b_succ
, bb_succ
;
7140 rtx link_insn
, link_mem
;
7143 /* these lists should point to the right place, for correct freeing later. */
7144 bb_pending_read_insns
[bb
] = pending_read_insns
;
7145 bb_pending_read_mems
[bb
] = pending_read_mems
;
7146 bb_pending_write_insns
[bb
] = pending_write_insns
;
7147 bb_pending_write_mems
[bb
] = pending_write_mems
;
7149 /* bb's structures are inherited by it's successors */
7150 first_edge
= e
= OUT_EDGES (b
);
7154 b_succ
= TO_BLOCK (e
);
7155 bb_succ
= BLOCK_TO_BB (b_succ
);
7157 /* only bbs "below" bb, in the same region, are interesting */
7158 if (CONTAINING_RGN (b
) != CONTAINING_RGN (b_succ
)
7165 for (reg
= 0; reg
< max_reg
; reg
++)
7168 /* reg-last-uses lists are inherited by bb_succ */
7169 for (u
= reg_last_uses
[reg
]; u
; u
= XEXP (u
, 1))
7171 if (find_insn_list (XEXP (u
, 0), (bb_reg_last_uses
[bb_succ
])[reg
]))
7174 (bb_reg_last_uses
[bb_succ
])[reg
]
7175 = alloc_INSN_LIST (XEXP (u
, 0),
7176 (bb_reg_last_uses
[bb_succ
])[reg
]);
7179 /* reg-last-defs lists are inherited by bb_succ */
7180 for (u
= reg_last_sets
[reg
]; u
; u
= XEXP (u
, 1))
7182 if (find_insn_list (XEXP (u
, 0), (bb_reg_last_sets
[bb_succ
])[reg
]))
7185 (bb_reg_last_sets
[bb_succ
])[reg
]
7186 = alloc_INSN_LIST (XEXP (u
, 0),
7187 (bb_reg_last_sets
[bb_succ
])[reg
]);
7191 /* mem read/write lists are inherited by bb_succ */
7192 link_insn
= pending_read_insns
;
7193 link_mem
= pending_read_mems
;
7196 if (!(find_insn_mem_list (XEXP (link_insn
, 0), XEXP (link_mem
, 0),
7197 bb_pending_read_insns
[bb_succ
],
7198 bb_pending_read_mems
[bb_succ
])))
7199 add_insn_mem_dependence (&bb_pending_read_insns
[bb_succ
],
7200 &bb_pending_read_mems
[bb_succ
],
7201 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
7202 link_insn
= XEXP (link_insn
, 1);
7203 link_mem
= XEXP (link_mem
, 1);
7206 link_insn
= pending_write_insns
;
7207 link_mem
= pending_write_mems
;
7210 if (!(find_insn_mem_list (XEXP (link_insn
, 0), XEXP (link_mem
, 0),
7211 bb_pending_write_insns
[bb_succ
],
7212 bb_pending_write_mems
[bb_succ
])))
7213 add_insn_mem_dependence (&bb_pending_write_insns
[bb_succ
],
7214 &bb_pending_write_mems
[bb_succ
],
7215 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
7217 link_insn
= XEXP (link_insn
, 1);
7218 link_mem
= XEXP (link_mem
, 1);
7221 /* last_function_call is inherited by bb_succ */
7222 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
7224 if (find_insn_list (XEXP (u
, 0), bb_last_function_call
[bb_succ
]))
7227 bb_last_function_call
[bb_succ
]
7228 = alloc_INSN_LIST (XEXP (u
, 0),
7229 bb_last_function_call
[bb_succ
]);
7232 /* last_pending_memory_flush is inherited by bb_succ */
7233 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
7235 if (find_insn_list (XEXP (u
, 0), bb_last_pending_memory_flush
[bb_succ
]))
7238 bb_last_pending_memory_flush
[bb_succ
]
7239 = alloc_INSN_LIST (XEXP (u
, 0),
7240 bb_last_pending_memory_flush
[bb_succ
]);
7243 /* sched_before_next_call is inherited by bb_succ */
7244 x
= LOG_LINKS (sched_before_next_call
);
7245 for (; x
; x
= XEXP (x
, 1))
7246 add_dependence (bb_sched_before_next_call
[bb_succ
],
7247 XEXP (x
, 0), REG_DEP_ANTI
);
7251 while (e
!= first_edge
);
7254 /* Free up the INSN_LISTs
7256 Note this loop is executed max_reg * nr_regions times. It's first
7257 implementation accounted for over 90% of the calls to free_list.
7258 The list was empty for the vast majority of those calls. On the PA,
7259 not calling free_list in those cases improves -O2 compile times by
7261 for (b
= 0; b
< max_reg
; ++b
)
7263 if (reg_last_sets
[b
])
7264 free_list (®_last_sets
[b
], &unused_insn_list
);
7265 if (reg_last_uses
[b
])
7266 free_list (®_last_uses
[b
], &unused_insn_list
);
7269 /* Assert that we won't need bb_reg_last_* for this block anymore. */
7270 if (current_nr_blocks
> 1)
7272 bb_reg_last_uses
[bb
] = (rtx
*) NULL_RTX
;
7273 bb_reg_last_sets
[bb
] = (rtx
*) NULL_RTX
;
7277 /* Print dependences for debugging, callable from debugger */
7280 debug_dependencies ()
7284 fprintf (dump
, ";; --------------- forward dependences: ------------ \n");
7285 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7293 get_block_head_tail (bb
, &head
, &tail
);
7294 next_tail
= NEXT_INSN (tail
);
7295 fprintf (dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
7296 BB_TO_BLOCK (bb
), bb
);
7298 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7299 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7300 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7301 "----", "----", "--", "---", "----", "----", "--------", "-----");
7302 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
7307 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
7310 fprintf (dump
, ";; %6d ", INSN_UID (insn
));
7311 if (GET_CODE (insn
) == NOTE
)
7313 n
= NOTE_LINE_NUMBER (insn
);
7315 fprintf (dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
7317 fprintf (dump
, "line %d, file %s\n", n
,
7318 NOTE_SOURCE_FILE (insn
));
7321 fprintf (dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
7325 unit
= insn_unit (insn
);
7327 || function_units
[unit
].blockage_range_function
== 0) ? 0 :
7328 function_units
[unit
].blockage_range_function (insn
);
7330 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7331 (SCHED_GROUP_P (insn
) ? "+" : " "),
7335 INSN_DEP_COUNT (insn
),
7336 INSN_PRIORITY (insn
),
7337 insn_cost (insn
, 0, 0),
7338 (int) MIN_BLOCKAGE_COST (range
),
7339 (int) MAX_BLOCKAGE_COST (range
));
7340 insn_print_units (insn
);
7341 fprintf (dump
, "\t: ");
7342 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
7343 fprintf (dump
, "%d ", INSN_UID (XEXP (link
, 0)));
7344 fprintf (dump
, "\n");
7348 fprintf (dump
, "\n");
7351 /* Set_priorities: compute priority of each insn in the block */
7364 get_block_head_tail (bb
, &head
, &tail
);
7365 prev_head
= PREV_INSN (head
);
7368 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
7372 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
7375 if (GET_CODE (insn
) == NOTE
)
7378 if (!(SCHED_GROUP_P (insn
)))
7380 (void) priority (insn
);
7386 /* Make each element of VECTOR point at an rtx-vector,
7387 taking the space for all those rtx-vectors from SPACE.
7388 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7389 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7390 (this is the same as init_regset_vector () in flow.c) */
7393 init_rtx_vector (vector
, space
, nelts
, bytes_per_elt
)
7400 register rtx
*p
= space
;
7402 for (i
= 0; i
< nelts
; i
++)
7405 p
+= bytes_per_elt
/ sizeof (*p
);
7409 /* Schedule a region. A region is either an inner loop, a loop-free
7410 subroutine, or a single basic block. Each bb in the region is
7411 scheduled after its flow predecessors. */
7414 schedule_region (rgn
)
7418 int rgn_n_insns
= 0;
7419 int sched_rgn_n_insns
= 0;
7421 /* set variables for the current region */
7422 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
7423 current_blocks
= RGN_BLOCKS (rgn
);
7425 reg_pending_sets
= ALLOCA_REG_SET ();
7426 reg_pending_sets_all
= 0;
7428 /* initializations for region data dependence analyisis */
7429 if (current_nr_blocks
> 1)
7432 int maxreg
= max_reg_num ();
7434 bb_reg_last_uses
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7435 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7436 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7437 init_rtx_vector (bb_reg_last_uses
, space
, current_nr_blocks
, maxreg
* sizeof (rtx
*));
7439 bb_reg_last_sets
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7440 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7441 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7442 init_rtx_vector (bb_reg_last_sets
, space
, current_nr_blocks
, maxreg
* sizeof (rtx
*));
7444 bb_pending_read_insns
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7445 bb_pending_read_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7446 bb_pending_write_insns
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7447 bb_pending_write_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7448 bb_pending_lists_length
= (int *) alloca (current_nr_blocks
* sizeof (int));
7449 bb_last_pending_memory_flush
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7450 bb_last_function_call
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7451 bb_sched_before_next_call
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7453 init_rgn_data_dependences (current_nr_blocks
);
7456 /* compute LOG_LINKS */
7457 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7458 compute_block_backward_dependences (bb
);
7460 /* compute INSN_DEPEND */
7461 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
7462 compute_block_forward_dependences (bb
);
7464 /* Delete line notes, compute live-regs at block end, and set priorities. */
7466 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7468 if (reload_completed
== 0)
7469 find_pre_sched_live (bb
);
7471 if (write_symbols
!= NO_DEBUG
)
7473 save_line_notes (bb
);
7477 rgn_n_insns
+= set_priorities (bb
);
7480 /* compute interblock info: probabilities, split-edges, dominators, etc. */
7481 if (current_nr_blocks
> 1)
7485 prob
= (float *) alloca ((current_nr_blocks
) * sizeof (float));
7487 bbset_size
= current_nr_blocks
/ HOST_BITS_PER_WIDE_INT
+ 1;
7488 dom
= (bbset
*) alloca (current_nr_blocks
* sizeof (bbset
));
7489 for (i
= 0; i
< current_nr_blocks
; i
++)
7491 dom
[i
] = (bbset
) alloca (bbset_size
* sizeof (HOST_WIDE_INT
));
7492 bzero ((char *) dom
[i
], bbset_size
* sizeof (HOST_WIDE_INT
));
7497 edge_to_bit
= (int *) alloca (nr_edges
* sizeof (int));
7498 for (i
= 1; i
< nr_edges
; i
++)
7499 if (CONTAINING_RGN (FROM_BLOCK (i
)) == rgn
)
7500 EDGE_TO_BIT (i
) = rgn_nr_edges
++;
7501 rgn_edges
= (int *) alloca (rgn_nr_edges
* sizeof (int));
7504 for (i
= 1; i
< nr_edges
; i
++)
7505 if (CONTAINING_RGN (FROM_BLOCK (i
)) == (rgn
))
7506 rgn_edges
[rgn_nr_edges
++] = i
;
7509 edgeset_size
= rgn_nr_edges
/ HOST_BITS_PER_WIDE_INT
+ 1;
7510 pot_split
= (edgeset
*) alloca (current_nr_blocks
* sizeof (edgeset
));
7511 ancestor_edges
= (edgeset
*) alloca (current_nr_blocks
* sizeof (edgeset
));
7512 for (i
= 0; i
< current_nr_blocks
; i
++)
7515 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
7516 bzero ((char *) pot_split
[i
],
7517 edgeset_size
* sizeof (HOST_WIDE_INT
));
7519 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
7520 bzero ((char *) ancestor_edges
[i
],
7521 edgeset_size
* sizeof (HOST_WIDE_INT
));
7524 /* compute probabilities, dominators, split_edges */
7525 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7526 compute_dom_prob_ps (bb
);
7529 /* now we can schedule all blocks */
7530 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7532 sched_rgn_n_insns
+= schedule_block (bb
, rgn_n_insns
);
7539 #ifdef INTERBLOCK_DEBUG
7540 if (sched_debug_count
!= 0)
7542 /* sanity check: verify that all region insns were scheduled */
7543 if (sched_rgn_n_insns
!= rgn_n_insns
)
7546 /* update register life and usage information */
7547 if (reload_completed
== 0)
7549 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
7550 find_post_sched_live (bb
);
7552 if (current_nr_blocks
<= 1)
7553 /* Sanity check. There should be no REG_DEAD notes leftover at the end.
7554 In practice, this can occur as the result of bugs in flow, combine.c,
7555 and/or sched.c. The values of the REG_DEAD notes remaining are
7556 meaningless, because dead_notes is just used as a free list. */
7557 if (dead_notes
!= 0)
7561 /* restore line notes. */
7562 if (write_symbols
!= NO_DEBUG
)
7564 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7565 restore_line_notes (bb
);
7568 /* Done with this region */
7569 free_pending_lists ();
7571 FREE_REG_SET (reg_pending_sets
);
7574 /* Subroutine of split_hard_reg_notes. Searches X for any reference to
7575 REGNO, returning the rtx of the reference found if any. Otherwise,
7579 regno_use_in (regno
, x
)
7587 if (GET_CODE (x
) == REG
&& REGNO (x
) == regno
)
7590 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
7591 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0; i
--)
7595 if ((tem
= regno_use_in (regno
, XEXP (x
, i
))))
7598 else if (fmt
[i
] == 'E')
7599 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
7600 if ((tem
= regno_use_in (regno
, XVECEXP (x
, i
, j
))))
7607 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
7608 needed for the hard register mentioned in the note. This can happen
7609 if the reference to the hard register in the original insn was split into
7610 several smaller hard register references in the split insns. */
7613 split_hard_reg_notes (note
, first
, last
)
7614 rtx note
, first
, last
;
7616 rtx reg
, temp
, link
;
7617 int n_regs
, i
, new_reg
;
7620 /* Assume that this is a REG_DEAD note. */
7621 if (REG_NOTE_KIND (note
) != REG_DEAD
)
7624 reg
= XEXP (note
, 0);
7626 n_regs
= HARD_REGNO_NREGS (REGNO (reg
), GET_MODE (reg
));
7628 for (i
= 0; i
< n_regs
; i
++)
7630 new_reg
= REGNO (reg
) + i
;
7632 /* Check for references to new_reg in the split insns. */
7633 for (insn
= last
;; insn
= PREV_INSN (insn
))
7635 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7636 && (temp
= regno_use_in (new_reg
, PATTERN (insn
))))
7638 /* Create a new reg dead note ere. */
7639 link
= alloc_EXPR_LIST (REG_DEAD
, temp
, REG_NOTES (insn
));
7640 REG_NOTES (insn
) = link
;
7642 /* If killed multiple registers here, then add in the excess. */
7643 i
+= HARD_REGNO_NREGS (REGNO (temp
), GET_MODE (temp
)) - 1;
7647 /* It isn't mentioned anywhere, so no new reg note is needed for
7655 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
7656 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
7659 new_insn_dead_notes (pat
, insn
, last
, orig_insn
)
7660 rtx pat
, insn
, last
, orig_insn
;
7664 /* PAT is either a CLOBBER or a SET here. */
7665 dest
= XEXP (pat
, 0);
7667 while (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
7668 || GET_CODE (dest
) == STRICT_LOW_PART
7669 || GET_CODE (dest
) == SIGN_EXTRACT
)
7670 dest
= XEXP (dest
, 0);
7672 if (GET_CODE (dest
) == REG
)
7674 /* If the original insn already used this register, we may not add new
7675 notes for it. One example for a split that needs this test is
7676 when a multi-word memory access with register-indirect addressing
7677 is split into multiple memory accesses with auto-increment and
7678 one adjusting add instruction for the address register. */
7679 if (reg_referenced_p (dest
, PATTERN (orig_insn
)))
7681 for (tem
= last
; tem
!= insn
; tem
= PREV_INSN (tem
))
7683 if (GET_RTX_CLASS (GET_CODE (tem
)) == 'i'
7684 && reg_overlap_mentioned_p (dest
, PATTERN (tem
))
7685 && (set
= single_set (tem
)))
7687 rtx tem_dest
= SET_DEST (set
);
7689 while (GET_CODE (tem_dest
) == ZERO_EXTRACT
7690 || GET_CODE (tem_dest
) == SUBREG
7691 || GET_CODE (tem_dest
) == STRICT_LOW_PART
7692 || GET_CODE (tem_dest
) == SIGN_EXTRACT
)
7693 tem_dest
= XEXP (tem_dest
, 0);
7695 if (!rtx_equal_p (tem_dest
, dest
))
7697 /* Use the same scheme as combine.c, don't put both REG_DEAD
7698 and REG_UNUSED notes on the same insn. */
7699 if (!find_regno_note (tem
, REG_UNUSED
, REGNO (dest
))
7700 && !find_regno_note (tem
, REG_DEAD
, REGNO (dest
)))
7702 rtx note
= alloc_EXPR_LIST (REG_DEAD
, dest
,
7704 REG_NOTES (tem
) = note
;
7706 /* The reg only dies in one insn, the last one that uses
7710 else if (reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
7711 /* We found an instruction that both uses the register,
7712 and sets it, so no new REG_NOTE is needed for this set. */
7716 /* If this is a set, it must die somewhere, unless it is the dest of
7717 the original insn, and hence is live after the original insn. Abort
7718 if it isn't supposed to be live after the original insn.
7720 If this is a clobber, then just add a REG_UNUSED note. */
7723 int live_after_orig_insn
= 0;
7724 rtx pattern
= PATTERN (orig_insn
);
7727 if (GET_CODE (pat
) == CLOBBER
)
7729 rtx note
= alloc_EXPR_LIST (REG_UNUSED
, dest
, REG_NOTES (insn
));
7730 REG_NOTES (insn
) = note
;
7734 /* The original insn could have multiple sets, so search the
7735 insn for all sets. */
7736 if (GET_CODE (pattern
) == SET
)
7738 if (reg_overlap_mentioned_p (dest
, SET_DEST (pattern
)))
7739 live_after_orig_insn
= 1;
7741 else if (GET_CODE (pattern
) == PARALLEL
)
7743 for (i
= 0; i
< XVECLEN (pattern
, 0); i
++)
7744 if (GET_CODE (XVECEXP (pattern
, 0, i
)) == SET
7745 && reg_overlap_mentioned_p (dest
,
7746 SET_DEST (XVECEXP (pattern
,
7748 live_after_orig_insn
= 1;
7751 if (!live_after_orig_insn
)
7757 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
7758 registers modified by X. INC is -1 if the containing insn is being deleted,
7759 and is 1 if the containing insn is a newly generated insn. */
7762 update_n_sets (x
, inc
)
7766 rtx dest
= SET_DEST (x
);
7768 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
7769 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
7770 dest
= SUBREG_REG (dest
);
7772 if (GET_CODE (dest
) == REG
)
7774 int regno
= REGNO (dest
);
7776 if (regno
< FIRST_PSEUDO_REGISTER
)
7779 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
7781 for (i
= regno
; i
< endregno
; i
++)
7782 REG_N_SETS (i
) += inc
;
7785 REG_N_SETS (regno
) += inc
;
7789 /* Updates all flow-analysis related quantities (including REG_NOTES) for
7790 the insns from FIRST to LAST inclusive that were created by splitting
7791 ORIG_INSN. NOTES are the original REG_NOTES. */
7794 update_flow_info (notes
, first
, last
, orig_insn
)
7801 rtx orig_dest
, temp
;
7804 /* Get and save the destination set by the original insn. */
7806 orig_dest
= single_set (orig_insn
);
7808 orig_dest
= SET_DEST (orig_dest
);
7810 /* Move REG_NOTES from the original insn to where they now belong. */
7812 for (note
= notes
; note
; note
= next
)
7814 next
= XEXP (note
, 1);
7815 switch (REG_NOTE_KIND (note
))
7819 /* Move these notes from the original insn to the last new insn where
7820 the register is now set. */
7822 for (insn
= last
;; insn
= PREV_INSN (insn
))
7824 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7825 && reg_mentioned_p (XEXP (note
, 0), PATTERN (insn
)))
7827 /* If this note refers to a multiple word hard register, it
7828 may have been split into several smaller hard register
7829 references, so handle it specially. */
7830 temp
= XEXP (note
, 0);
7831 if (REG_NOTE_KIND (note
) == REG_DEAD
7832 && GET_CODE (temp
) == REG
7833 && REGNO (temp
) < FIRST_PSEUDO_REGISTER
7834 && HARD_REGNO_NREGS (REGNO (temp
), GET_MODE (temp
)) > 1)
7835 split_hard_reg_notes (note
, first
, last
);
7838 XEXP (note
, 1) = REG_NOTES (insn
);
7839 REG_NOTES (insn
) = note
;
7842 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
7844 /* ??? This won't handle multiple word registers correctly,
7845 but should be good enough for now. */
7846 if (REG_NOTE_KIND (note
) == REG_UNUSED
7847 && GET_CODE (XEXP (note
, 0)) != SCRATCH
7848 && !dead_or_set_p (insn
, XEXP (note
, 0)))
7849 PUT_REG_NOTE_KIND (note
, REG_DEAD
);
7851 /* The reg only dies in one insn, the last one that uses
7855 /* It must die somewhere, fail it we couldn't find where it died.
7857 If this is a REG_UNUSED note, then it must be a temporary
7858 register that was not needed by this instantiation of the
7859 pattern, so we can safely ignore it. */
7862 /* After reload, REG_DEAD notes come sometimes an
7863 instruction after the register actually dies. */
7864 if (reload_completed
&& REG_NOTE_KIND (note
) == REG_DEAD
)
7866 XEXP (note
, 1) = REG_NOTES (insn
);
7867 REG_NOTES (insn
) = note
;
7871 if (REG_NOTE_KIND (note
) != REG_UNUSED
)
7880 /* If the insn that set the register to 0 was deleted, this
7881 note cannot be relied on any longer. The destination might
7882 even have been moved to memory.
7883 This was observed for SH4 with execute/920501-6.c compilation,
7884 -O2 -fomit-frame-pointer -finline-functions . */
7885 if (GET_CODE (XEXP (note
, 0)) == NOTE
7886 || INSN_DELETED_P (XEXP (note
, 0)))
7888 /* This note applies to the dest of the original insn. Find the
7889 first new insn that now has the same dest, and move the note
7895 for (insn
= first
;; insn
= NEXT_INSN (insn
))
7897 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7898 && (temp
= single_set (insn
))
7899 && rtx_equal_p (SET_DEST (temp
), orig_dest
))
7901 XEXP (note
, 1) = REG_NOTES (insn
);
7902 REG_NOTES (insn
) = note
;
7903 /* The reg is only zero before one insn, the first that
7907 /* If this note refers to a multiple word hard
7908 register, it may have been split into several smaller
7909 hard register references. We could split the notes,
7910 but simply dropping them is good enough. */
7911 if (GET_CODE (orig_dest
) == REG
7912 && REGNO (orig_dest
) < FIRST_PSEUDO_REGISTER
7913 && HARD_REGNO_NREGS (REGNO (orig_dest
),
7914 GET_MODE (orig_dest
)) > 1)
7916 /* It must be set somewhere, fail if we couldn't find where it
7925 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
7926 set is meaningless. Just drop the note. */
7930 case REG_NO_CONFLICT
:
7931 /* These notes apply to the dest of the original insn. Find the last
7932 new insn that now has the same dest, and move the note there. */
7937 for (insn
= last
;; insn
= PREV_INSN (insn
))
7939 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7940 && (temp
= single_set (insn
))
7941 && rtx_equal_p (SET_DEST (temp
), orig_dest
))
7943 XEXP (note
, 1) = REG_NOTES (insn
);
7944 REG_NOTES (insn
) = note
;
7945 /* Only put this note on one of the new insns. */
7949 /* The original dest must still be set someplace. Abort if we
7950 couldn't find it. */
7953 /* However, if this note refers to a multiple word hard
7954 register, it may have been split into several smaller
7955 hard register references. We could split the notes,
7956 but simply dropping them is good enough. */
7957 if (GET_CODE (orig_dest
) == REG
7958 && REGNO (orig_dest
) < FIRST_PSEUDO_REGISTER
7959 && HARD_REGNO_NREGS (REGNO (orig_dest
),
7960 GET_MODE (orig_dest
)) > 1)
7962 /* Likewise for multi-word memory references. */
7963 if (GET_CODE (orig_dest
) == MEM
7964 && SIZE_FOR_MODE (orig_dest
) > MOVE_MAX
)
7972 /* Move a REG_LIBCALL note to the first insn created, and update
7973 the corresponding REG_RETVAL note. */
7974 XEXP (note
, 1) = REG_NOTES (first
);
7975 REG_NOTES (first
) = note
;
7977 insn
= XEXP (note
, 0);
7978 note
= find_reg_note (insn
, REG_RETVAL
, NULL_RTX
);
7980 XEXP (note
, 0) = first
;
7983 case REG_EXEC_COUNT
:
7984 /* Move a REG_EXEC_COUNT note to the first insn created. */
7985 XEXP (note
, 1) = REG_NOTES (first
);
7986 REG_NOTES (first
) = note
;
7990 /* Move a REG_RETVAL note to the last insn created, and update
7991 the corresponding REG_LIBCALL note. */
7992 XEXP (note
, 1) = REG_NOTES (last
);
7993 REG_NOTES (last
) = note
;
7995 insn
= XEXP (note
, 0);
7996 note
= find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
);
7998 XEXP (note
, 0) = last
;
8003 /* This should be moved to whichever instruction is a JUMP_INSN. */
8005 for (insn
= last
;; insn
= PREV_INSN (insn
))
8007 if (GET_CODE (insn
) == JUMP_INSN
)
8009 XEXP (note
, 1) = REG_NOTES (insn
);
8010 REG_NOTES (insn
) = note
;
8011 /* Only put this note on one of the new insns. */
8014 /* Fail if we couldn't find a JUMP_INSN. */
8021 /* reload sometimes leaves obsolete REG_INC notes around. */
8022 if (reload_completed
)
8024 /* This should be moved to whichever instruction now has the
8025 increment operation. */
8029 /* Should be moved to the new insn(s) which use the label. */
8030 for (insn
= first
; insn
!= NEXT_INSN (last
); insn
= NEXT_INSN (insn
))
8031 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8032 && reg_mentioned_p (XEXP (note
, 0), PATTERN (insn
)))
8034 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_LABEL
,
8042 /* These two notes will never appear until after reorg, so we don't
8043 have to handle them here. */
8049 /* Each new insn created, except the last, has a new set. If the destination
8050 is a register, then this reg is now live across several insns, whereas
8051 previously the dest reg was born and died within the same insn. To
8052 reflect this, we now need a REG_DEAD note on the insn where this
8055 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
8057 for (insn
= first
; insn
!= last
; insn
= NEXT_INSN (insn
))
8062 pat
= PATTERN (insn
);
8063 if (GET_CODE (pat
) == SET
|| GET_CODE (pat
) == CLOBBER
)
8064 new_insn_dead_notes (pat
, insn
, last
, orig_insn
);
8065 else if (GET_CODE (pat
) == PARALLEL
)
8067 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
8068 if (GET_CODE (XVECEXP (pat
, 0, i
)) == SET
8069 || GET_CODE (XVECEXP (pat
, 0, i
)) == CLOBBER
)
8070 new_insn_dead_notes (XVECEXP (pat
, 0, i
), insn
, last
, orig_insn
);
8074 /* If any insn, except the last, uses the register set by the last insn,
8075 then we need a new REG_DEAD note on that insn. In this case, there
8076 would not have been a REG_DEAD note for this register in the original
8077 insn because it was used and set within one insn. */
8079 set
= single_set (last
);
8082 rtx dest
= SET_DEST (set
);
8084 while (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
8085 || GET_CODE (dest
) == STRICT_LOW_PART
8086 || GET_CODE (dest
) == SIGN_EXTRACT
)
8087 dest
= XEXP (dest
, 0);
8089 if (GET_CODE (dest
) == REG
8090 /* Global registers are always live, so the code below does not
8092 && (REGNO (dest
) >= FIRST_PSEUDO_REGISTER
8093 || ! global_regs
[REGNO (dest
)]))
8095 rtx stop_insn
= PREV_INSN (first
);
8097 /* If the last insn uses the register that it is setting, then
8098 we don't want to put a REG_DEAD note there. Search backwards
8099 to find the first insn that sets but does not use DEST. */
8102 if (reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
8104 for (insn
= PREV_INSN (insn
); insn
!= first
;
8105 insn
= PREV_INSN (insn
))
8107 if ((set
= single_set (insn
))
8108 && reg_mentioned_p (dest
, SET_DEST (set
))
8109 && ! reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
8114 /* Now find the first insn that uses but does not set DEST. */
8116 for (insn
= PREV_INSN (insn
); insn
!= stop_insn
;
8117 insn
= PREV_INSN (insn
))
8119 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8120 && reg_mentioned_p (dest
, PATTERN (insn
))
8121 && (set
= single_set (insn
)))
8123 rtx insn_dest
= SET_DEST (set
);
8125 while (GET_CODE (insn_dest
) == ZERO_EXTRACT
8126 || GET_CODE (insn_dest
) == SUBREG
8127 || GET_CODE (insn_dest
) == STRICT_LOW_PART
8128 || GET_CODE (insn_dest
) == SIGN_EXTRACT
)
8129 insn_dest
= XEXP (insn_dest
, 0);
8131 if (insn_dest
!= dest
)
8133 note
= alloc_EXPR_LIST (REG_DEAD
, dest
, REG_NOTES (insn
));
8134 REG_NOTES (insn
) = note
;
8135 /* The reg only dies in one insn, the last one
8144 /* If the original dest is modifying a multiple register target, and the
8145 original instruction was split such that the original dest is now set
8146 by two or more SUBREG sets, then the split insns no longer kill the
8147 destination of the original insn.
8149 In this case, if there exists an instruction in the same basic block,
8150 before the split insn, which uses the original dest, and this use is
8151 killed by the original insn, then we must remove the REG_DEAD note on
8152 this insn, because it is now superfluous.
8154 This does not apply when a hard register gets split, because the code
8155 knows how to handle overlapping hard registers properly. */
8156 if (orig_dest
&& GET_CODE (orig_dest
) == REG
)
8158 int found_orig_dest
= 0;
8159 int found_split_dest
= 0;
8161 for (insn
= first
;; insn
= NEXT_INSN (insn
))
8166 /* I'm not sure if this can happen, but let's be safe. */
8167 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
8170 pat
= PATTERN (insn
);
8171 i
= GET_CODE (pat
) == PARALLEL
? XVECLEN (pat
, 0) : 0;
8176 if (GET_CODE (set
) == SET
)
8178 if (GET_CODE (SET_DEST (set
)) == REG
8179 && REGNO (SET_DEST (set
)) == REGNO (orig_dest
))
8181 found_orig_dest
= 1;
8184 else if (GET_CODE (SET_DEST (set
)) == SUBREG
8185 && SUBREG_REG (SET_DEST (set
)) == orig_dest
)
8187 found_split_dest
= 1;
8193 set
= XVECEXP (pat
, 0, i
);
8200 if (found_split_dest
)
8202 /* Search backwards from FIRST, looking for the first insn that uses
8203 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
8204 If we find an insn, and it has a REG_DEAD note, then delete the
8207 for (insn
= first
; insn
; insn
= PREV_INSN (insn
))
8209 if (GET_CODE (insn
) == CODE_LABEL
8210 || GET_CODE (insn
) == JUMP_INSN
)
8212 else if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8213 && reg_mentioned_p (orig_dest
, insn
))
8215 note
= find_regno_note (insn
, REG_DEAD
, REGNO (orig_dest
));
8217 remove_note (insn
, note
);
8221 else if (!found_orig_dest
)
8223 /* This should never happen. */
8228 /* Update reg_n_sets. This is necessary to prevent local alloc from
8229 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
8230 a reg from set once to set multiple times. */
8233 rtx x
= PATTERN (orig_insn
);
8234 RTX_CODE code
= GET_CODE (x
);
8236 if (code
== SET
|| code
== CLOBBER
)
8237 update_n_sets (x
, -1);
8238 else if (code
== PARALLEL
)
8241 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
8243 code
= GET_CODE (XVECEXP (x
, 0, i
));
8244 if (code
== SET
|| code
== CLOBBER
)
8245 update_n_sets (XVECEXP (x
, 0, i
), -1);
8249 for (insn
= first
;; insn
= NEXT_INSN (insn
))
8252 code
= GET_CODE (x
);
8254 if (code
== SET
|| code
== CLOBBER
)
8255 update_n_sets (x
, 1);
8256 else if (code
== PARALLEL
)
8259 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
8261 code
= GET_CODE (XVECEXP (x
, 0, i
));
8262 if (code
== SET
|| code
== CLOBBER
)
8263 update_n_sets (XVECEXP (x
, 0, i
), 1);
8273 /* Do the splitting of insns in the block b. */
8276 split_block_insns (b
)
8281 for (insn
= basic_block_head
[b
];; insn
= next
)
8283 rtx set
, last
, first
, notes
;
8285 /* Can't use `next_real_insn' because that
8286 might go across CODE_LABELS and short-out basic blocks. */
8287 next
= NEXT_INSN (insn
);
8288 if (GET_CODE (insn
) != INSN
)
8290 if (insn
== basic_block_end
[b
])
8296 /* Don't split no-op move insns. These should silently disappear
8297 later in final. Splitting such insns would break the code
8298 that handles REG_NO_CONFLICT blocks. */
8299 set
= single_set (insn
);
8300 if (set
&& rtx_equal_p (SET_SRC (set
), SET_DEST (set
)))
8302 if (insn
== basic_block_end
[b
])
8305 /* Nops get in the way while scheduling, so delete them now if
8306 register allocation has already been done. It is too risky
8307 to try to do this before register allocation, and there are
8308 unlikely to be very many nops then anyways. */
8309 if (reload_completed
)
8311 PUT_CODE (insn
, NOTE
);
8312 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
8313 NOTE_SOURCE_FILE (insn
) = 0;
8319 /* Split insns here to get max fine-grain parallelism. */
8320 first
= PREV_INSN (insn
);
8321 notes
= REG_NOTES (insn
);
8322 last
= try_split (PATTERN (insn
), insn
, 1);
8325 /* try_split returns the NOTE that INSN became. */
8326 first
= NEXT_INSN (first
);
8327 update_flow_info (notes
, first
, last
, insn
);
8329 PUT_CODE (insn
, NOTE
);
8330 NOTE_SOURCE_FILE (insn
) = 0;
8331 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
8332 if (insn
== basic_block_head
[b
])
8333 basic_block_head
[b
] = first
;
8334 if (insn
== basic_block_end
[b
])
8336 basic_block_end
[b
] = last
;
8341 if (insn
== basic_block_end
[b
])
8346 /* The one entry point in this file. DUMP_FILE is the dump file for
8350 schedule_insns (dump_file
)
8361 /* disable speculative loads in their presence if cc0 defined */
8363 flag_schedule_speculative_load
= 0;
8366 /* Taking care of this degenerate case makes the rest of
8367 this code simpler. */
8368 if (n_basic_blocks
== 0)
8371 /* set dump and sched_verbose for the desired debugging output. If no
8372 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
8373 For -fsched-verbose-N, N>=10, print everything to stderr. */
8374 sched_verbose
= sched_verbose_param
;
8375 if (sched_verbose_param
== 0 && dump_file
)
8377 dump
= ((sched_verbose_param
>= 10 || !dump_file
) ? stderr
: dump_file
);
8382 /* Initialize the unused_*_lists. We can't use the ones left over from
8383 the previous function, because gcc has freed that memory. We can use
8384 the ones left over from the first sched pass in the second pass however,
8385 so only clear them on the first sched pass. The first pass is before
8386 reload if flag_schedule_insns is set, otherwise it is afterwards. */
8388 if (reload_completed
== 0 || !flag_schedule_insns
)
8390 unused_insn_list
= 0;
8391 unused_expr_list
= 0;
8394 /* initialize issue_rate */
8395 issue_rate
= ISSUE_RATE
;
8397 /* do the splitting first for all blocks */
8398 for (b
= 0; b
< n_basic_blocks
; b
++)
8399 split_block_insns (b
);
8401 max_uid
= (get_max_uid () + 1);
8403 cant_move
= (char *) alloca (max_uid
* sizeof (char));
8404 bzero ((char *) cant_move
, max_uid
* sizeof (char));
8406 fed_by_spec_load
= (char *) alloca (max_uid
* sizeof (char));
8407 bzero ((char *) fed_by_spec_load
, max_uid
* sizeof (char));
8409 is_load_insn
= (char *) alloca (max_uid
* sizeof (char));
8410 bzero ((char *) is_load_insn
, max_uid
* sizeof (char));
8412 insn_orig_block
= (int *) alloca (max_uid
* sizeof (int));
8413 insn_luid
= (int *) alloca (max_uid
* sizeof (int));
8416 for (b
= 0; b
< n_basic_blocks
; b
++)
8417 for (insn
= basic_block_head
[b
];; insn
= NEXT_INSN (insn
))
8419 INSN_BLOCK (insn
) = b
;
8420 INSN_LUID (insn
) = luid
++;
8422 if (insn
== basic_block_end
[b
])
8426 /* after reload, remove inter-blocks dependences computed before reload. */
8427 if (reload_completed
)
8432 for (b
= 0; b
< n_basic_blocks
; b
++)
8433 for (insn
= basic_block_head
[b
];; insn
= NEXT_INSN (insn
))
8437 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
8440 link
= LOG_LINKS (insn
);
8443 rtx x
= XEXP (link
, 0);
8445 if (INSN_BLOCK (x
) != b
)
8447 remove_dependence (insn
, x
);
8448 link
= prev
? XEXP (prev
, 1) : LOG_LINKS (insn
);
8451 prev
= link
, link
= XEXP (prev
, 1);
8455 if (insn
== basic_block_end
[b
])
8461 rgn_table
= (region
*) alloca ((n_basic_blocks
) * sizeof (region
));
8462 rgn_bb_table
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8463 block_to_bb
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8464 containing_rgn
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8466 /* compute regions for scheduling */
8467 if (reload_completed
8468 || n_basic_blocks
== 1
8469 || !flag_schedule_interblock
)
8471 find_single_block_region ();
8475 /* verify that a 'good' control flow graph can be built */
8476 if (is_cfg_nonregular ())
8478 find_single_block_region ();
8482 int_list_ptr
*s_preds
, *s_succs
;
8483 int *num_preds
, *num_succs
;
8484 sbitmap
*dom
, *pdom
;
8486 s_preds
= (int_list_ptr
*) alloca (n_basic_blocks
8487 * sizeof (int_list_ptr
));
8488 s_succs
= (int_list_ptr
*) alloca (n_basic_blocks
8489 * sizeof (int_list_ptr
));
8490 num_preds
= (int *) alloca (n_basic_blocks
* sizeof (int));
8491 num_succs
= (int *) alloca (n_basic_blocks
* sizeof (int));
8492 dom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
8493 pdom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
8495 /* The scheduler runs after flow; therefore, we can't blindly call
8496 back into find_basic_blocks since doing so could invalidate the
8497 info in basic_block_live_at_start.
8499 Consider a block consisting entirely of dead stores; after life
8500 analysis it would be a block of NOTE_INSN_DELETED notes. If
8501 we call find_basic_blocks again, then the block would be removed
8502 entirely and invalidate our the register live information.
8504 We could (should?) recompute register live information. Doing
8505 so may even be beneficial. */
8507 compute_preds_succs (s_preds
, s_succs
, num_preds
, num_succs
);
8509 /* Compute the dominators and post dominators. We don't currently use
8510 post dominators, but we should for speculative motion analysis. */
8511 compute_dominators (dom
, pdom
, s_preds
, s_succs
);
8513 /* build_control_flow will return nonzero if it detects unreachable
8514 blocks or any other irregularity with the cfg which prevents
8515 cross block scheduling. */
8516 if (build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
) != 0)
8517 find_single_block_region ();
8519 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
);
8521 if (sched_verbose
>= 3)
8524 /* For now. This will move as more and more of haifa is converted
8525 to using the cfg code in flow.c */
8532 /* Allocate data for this pass. See comments, above,
8533 for what these vectors do. */
8534 insn_priority
= (int *) alloca (max_uid
* sizeof (int));
8535 insn_reg_weight
= (int *) alloca (max_uid
* sizeof (int));
8536 insn_tick
= (int *) alloca (max_uid
* sizeof (int));
8537 insn_costs
= (short *) alloca (max_uid
* sizeof (short));
8538 insn_units
= (short *) alloca (max_uid
* sizeof (short));
8539 insn_blockage
= (unsigned int *) alloca (max_uid
* sizeof (unsigned int));
8540 insn_ref_count
= (int *) alloca (max_uid
* sizeof (int));
8542 /* Allocate for forward dependencies */
8543 insn_dep_count
= (int *) alloca (max_uid
* sizeof (int));
8544 insn_depend
= (rtx
*) alloca (max_uid
* sizeof (rtx
));
8546 if (reload_completed
== 0)
8550 sched_reg_n_calls_crossed
= (int *) alloca (max_regno
* sizeof (int));
8551 sched_reg_live_length
= (int *) alloca (max_regno
* sizeof (int));
8552 sched_reg_basic_block
= (int *) alloca (max_regno
* sizeof (int));
8553 bb_live_regs
= ALLOCA_REG_SET ();
8554 bzero ((char *) sched_reg_n_calls_crossed
, max_regno
* sizeof (int));
8555 bzero ((char *) sched_reg_live_length
, max_regno
* sizeof (int));
8557 for (i
= 0; i
< max_regno
; i
++)
8558 sched_reg_basic_block
[i
] = REG_BLOCK_UNKNOWN
;
8562 sched_reg_n_calls_crossed
= 0;
8563 sched_reg_live_length
= 0;
8566 init_alias_analysis ();
8568 if (write_symbols
!= NO_DEBUG
)
8572 line_note
= (rtx
*) alloca (max_uid
* sizeof (rtx
));
8573 bzero ((char *) line_note
, max_uid
* sizeof (rtx
));
8574 line_note_head
= (rtx
*) alloca (n_basic_blocks
* sizeof (rtx
));
8575 bzero ((char *) line_note_head
, n_basic_blocks
* sizeof (rtx
));
8577 /* Save-line-note-head:
8578 Determine the line-number at the start of each basic block.
8579 This must be computed and saved now, because after a basic block's
8580 predecessor has been scheduled, it is impossible to accurately
8581 determine the correct line number for the first insn of the block. */
8583 for (b
= 0; b
< n_basic_blocks
; b
++)
8584 for (line
= basic_block_head
[b
]; line
; line
= PREV_INSN (line
))
8585 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
8587 line_note_head
[b
] = line
;
8592 bzero ((char *) insn_priority
, max_uid
* sizeof (int));
8593 bzero ((char *) insn_reg_weight
, max_uid
* sizeof (int));
8594 bzero ((char *) insn_tick
, max_uid
* sizeof (int));
8595 bzero ((char *) insn_costs
, max_uid
* sizeof (short));
8596 bzero ((char *) insn_units
, max_uid
* sizeof (short));
8597 bzero ((char *) insn_blockage
, max_uid
* sizeof (unsigned int));
8598 bzero ((char *) insn_ref_count
, max_uid
* sizeof (int));
8600 /* Initialize for forward dependencies */
8601 bzero ((char *) insn_depend
, max_uid
* sizeof (rtx
));
8602 bzero ((char *) insn_dep_count
, max_uid
* sizeof (int));
8604 /* Find units used in this fuction, for visualization */
8606 init_target_units ();
8608 /* ??? Add a NOTE after the last insn of the last basic block. It is not
8609 known why this is done. */
8611 insn
= basic_block_end
[n_basic_blocks
- 1];
8612 if (NEXT_INSN (insn
) == 0
8613 || (GET_CODE (insn
) != NOTE
8614 && GET_CODE (insn
) != CODE_LABEL
8615 /* Don't emit a NOTE if it would end up between an unconditional
8616 jump and a BARRIER. */
8617 && !(GET_CODE (insn
) == JUMP_INSN
8618 && GET_CODE (NEXT_INSN (insn
)) == BARRIER
)))
8619 emit_note_after (NOTE_INSN_DELETED
, basic_block_end
[n_basic_blocks
- 1]);
8621 /* Schedule every region in the subroutine */
8622 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
8624 schedule_region (rgn
);
8631 /* Reposition the prologue and epilogue notes in case we moved the
8632 prologue/epilogue insns. */
8633 if (reload_completed
)
8634 reposition_prologue_and_epilogue_notes (get_insns ());
8636 /* delete redundant line notes. */
8637 if (write_symbols
!= NO_DEBUG
)
8638 rm_redundant_line_notes ();
8640 /* Update information about uses of registers in the subroutine. */
8641 if (reload_completed
== 0)
8642 update_reg_usage ();
8646 if (reload_completed
== 0 && flag_schedule_interblock
)
8648 fprintf (dump
, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8656 fprintf (dump
, "\n\n");
8660 FREE_REG_SET (bb_live_regs
);
8679 #endif /* INSN_SCHEDULING */