1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 93-98, 1999 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to the Free
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
24 /* Instruction scheduling pass.
26 This pass implements list scheduling within basic blocks. It is
27 run twice: (1) after flow analysis, but before register allocation,
28 and (2) after register allocation.
30 The first run performs interblock scheduling, moving insns between
31 different blocks in the same "region", and the second runs only
32 basic block scheduling.
34 Interblock motions performed are useful motions and speculative
35 motions, including speculative loads. Motions requiring code
36 duplication are not supported. The identification of motion type
37 and the check for validity of speculative motions requires
38 construction and analysis of the function's control flow graph.
39 The scheduler works as follows:
41 We compute insn priorities based on data dependencies. Flow
42 analysis only creates a fraction of the data-dependencies we must
43 observe: namely, only those dependencies which the combiner can be
44 expected to use. For this pass, we must therefore create the
45 remaining dependencies we need to observe: register dependencies,
46 memory dependencies, dependencies to keep function calls in order,
47 and the dependence between a conditional branch and the setting of
48 condition codes are all dealt with here.
50 The scheduler first traverses the data flow graph, starting with
51 the last instruction, and proceeding to the first, assigning values
52 to insn_priority as it goes. This sorts the instructions
53 topologically by data dependence.
55 Once priorities have been established, we order the insns using
56 list scheduling. This works as follows: starting with a list of
57 all the ready insns, and sorted according to priority number, we
58 schedule the insn from the end of the list by placing its
59 predecessors in the list according to their priority order. We
60 consider this insn scheduled by setting the pointer to the "end" of
61 the list to point to the previous insn. When an insn has no
62 predecessors, we either queue it until sufficient time has elapsed
63 or add it to the ready list. As the instructions are scheduled or
64 when stalls are introduced, the queue advances and dumps insns into
65 the ready list. When all insns down to the lowest priority have
66 been scheduled, the critical path of the basic block has been made
67 as short as possible. The remaining insns are then scheduled in
70 Function unit conflicts are resolved during forward list scheduling
71 by tracking the time when each insn is committed to the schedule
72 and from that, the time the function units it uses must be free.
73 As insns on the ready list are considered for scheduling, those
74 that would result in a blockage of the already committed insns are
75 queued until no blockage will result.
77 The following list shows the order in which we want to break ties
78 among insns in the ready list:
80 1. choose insn with the longest path to end of bb, ties
82 2. choose insn with least contribution to register pressure,
84 3. prefer in-block upon interblock motion, ties broken by
85 4. prefer useful upon speculative motion, ties broken by
86 5. choose insn with largest control flow probability, ties
88 6. choose insn with the least dependences upon the previously
89 scheduled insn, or finally
90 7 choose the insn which has the most insns dependent on it.
91 8. choose insn with lowest UID.
93 Memory references complicate matters. Only if we can be certain
94 that memory references are not part of the data dependency graph
95 (via true, anti, or output dependence), can we move operations past
96 memory references. To first approximation, reads can be done
97 independently, while writes introduce dependencies. Better
98 approximations will yield fewer dependencies.
100 Before reload, an extended analysis of interblock data dependences
101 is required for interblock scheduling. This is performed in
102 compute_block_backward_dependences ().
104 Dependencies set up by memory references are treated in exactly the
105 same way as other dependencies, by using LOG_LINKS backward
106 dependences. LOG_LINKS are translated into INSN_DEPEND forward
107 dependences for the purpose of forward list scheduling.
109 Having optimized the critical path, we may have also unduly
110 extended the lifetimes of some registers. If an operation requires
111 that constants be loaded into registers, it is certainly desirable
112 to load those constants as early as necessary, but no earlier.
113 I.e., it will not do to load up a bunch of registers at the
114 beginning of a basic block only to use them at the end, if they
115 could be loaded later, since this may result in excessive register
118 Note that since branches are never in basic blocks, but only end
119 basic blocks, this pass will not move branches. But that is ok,
120 since we can use GNU's delayed branch scheduling pass to take care
123 Also note that no further optimizations based on algebraic
124 identities are performed, so this pass would be a good one to
125 perform instruction splitting, such as breaking up a multiply
126 instruction into shifts and adds where that is profitable.
128 Given the memory aliasing analysis that this pass should perform,
129 it should be possible to remove redundant stores to memory, and to
130 load values from registers instead of hitting memory.
132 Before reload, speculative insns are moved only if a 'proof' exists
133 that no exception will be caused by this, and if no live registers
134 exist that inhibit the motion (live registers constraints are not
135 represented by data dependence edges).
137 This pass must update information that subsequent passes expect to
138 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
139 reg_n_calls_crossed, and reg_live_length. Also, BLOCK_HEAD,
142 The information in the line number notes is carefully retained by
143 this pass. Notes that refer to the starting and ending of
144 exception regions are also carefully retained by this pass. All
145 other NOTE insns are grouped in their same relative order at the
146 beginning of basic blocks and regions that have been scheduled.
148 The main entry point for this pass is schedule_insns(), called for
149 each function. The work of the scheduler is organized in three
150 levels: (1) function level: insns are subject to splitting,
151 control-flow-graph is constructed, regions are computed (after
152 reload, each region is of one block), (2) region level: control
153 flow graph attributes required for interblock scheduling are
154 computed (dominators, reachability, etc.), data dependences and
155 priorities are computed, and (3) block level: insns in the block
156 are actually scheduled. */
162 #include "basic-block.h"
164 #include "hard-reg-set.h"
166 #include "insn-config.h"
167 #include "insn-attr.h"
172 extern char *reg_known_equiv_p
;
173 extern rtx
*reg_known_value
;
175 #ifdef INSN_SCHEDULING
177 /* target_units bitmask has 1 for each unit in the cpu. It should be
178 possible to compute this variable from the machine description.
179 But currently it is computed by examinning the insn list. Since
180 this is only needed for visualization, it seems an acceptable
181 solution. (For understanding the mapping of bits to units, see
182 definition of function_units[] in "insn-attrtab.c") */
184 static int target_units
= 0;
186 /* issue_rate is the number of insns that can be scheduled in the same
187 machine cycle. It can be defined in the config/mach/mach.h file,
188 otherwise we set it to 1. */
190 static int issue_rate
;
196 /* sched-verbose controls the amount of debugging output the
197 scheduler prints. It is controlled by -fsched-verbose-N:
198 N>0 and no -DSR : the output is directed to stderr.
199 N>=10 will direct the printouts to stderr (regardless of -dSR).
201 N=2: bb's probabilities, detailed ready list info, unit/insn info.
202 N=3: rtl at abort point, control-flow, regions info.
203 N=5: dependences info. */
205 #define MAX_RGN_BLOCKS 10
206 #define MAX_RGN_INSNS 100
208 static int sched_verbose_param
= 0;
209 static int sched_verbose
= 0;
211 /* nr_inter/spec counts interblock/speculative motion for the function */
212 static int nr_inter
, nr_spec
;
215 /* debugging file. all printouts are sent to dump, which is always set,
216 either to stderr, or to the dump listing file (-dRS). */
217 static FILE *dump
= 0;
219 /* fix_sched_param() is called from toplev.c upon detection
220 of the -fsched-***-N options. */
223 fix_sched_param (param
, val
)
226 if (!strcmp (param
, "verbose"))
227 sched_verbose_param
= atoi (val
);
229 warning ("fix_sched_param: unknown param: %s", param
);
233 /* Arrays set up by scheduling for the same respective purposes as
234 similar-named arrays set up by flow analysis. We work with these
235 arrays during the scheduling pass so we can compare values against
238 Values of these arrays are copied at the end of this pass into the
239 arrays set up by flow analysis. */
240 static int *sched_reg_n_calls_crossed
;
241 static int *sched_reg_live_length
;
242 static int *sched_reg_basic_block
;
244 /* We need to know the current block number during the post scheduling
245 update of live register information so that we can also update
246 REG_BASIC_BLOCK if a register changes blocks. */
247 static int current_block_num
;
249 /* Element N is the next insn that sets (hard or pseudo) register
250 N within the current basic block; or zero, if there is no
251 such insn. Needed for new registers which may be introduced
252 by splitting insns. */
253 static rtx
*reg_last_uses
;
254 static rtx
*reg_last_sets
;
255 static rtx
*reg_last_clobbers
;
256 static regset reg_pending_sets
;
257 static regset reg_pending_clobbers
;
258 static int reg_pending_sets_all
;
260 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
261 static int *insn_luid
;
262 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
264 /* Vector indexed by INSN_UID giving each instruction a priority. */
265 static int *insn_priority
;
266 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
268 static short *insn_costs
;
269 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
271 /* Vector indexed by INSN_UID giving an encoding of the function units
273 static short *insn_units
;
274 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
276 /* Vector indexed by INSN_UID giving each instruction a register-weight.
277 This weight is an estimation of the insn contribution to registers pressure. */
278 static int *insn_reg_weight
;
279 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
281 /* Vector indexed by INSN_UID giving list of insns which
282 depend upon INSN. Unlike LOG_LINKS, it represents forward dependences. */
283 static rtx
*insn_depend
;
284 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
286 /* Vector indexed by INSN_UID. Initialized to the number of incoming
287 edges in forward dependence graph (= number of LOG_LINKS). As
288 scheduling procedes, dependence counts are decreased. An
289 instruction moves to the ready list when its counter is zero. */
290 static int *insn_dep_count
;
291 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
293 /* Vector indexed by INSN_UID giving an encoding of the blockage range
294 function. The unit and the range are encoded. */
295 static unsigned int *insn_blockage
;
296 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
298 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
299 #define ENCODE_BLOCKAGE(U, R) \
300 (((U) << BLOCKAGE_BITS \
301 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
302 | MAX_BLOCKAGE_COST (R))
303 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
304 #define BLOCKAGE_RANGE(B) \
305 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
306 | ((B) & BLOCKAGE_MASK))
308 /* Encodings of the `<name>_unit_blockage_range' function. */
309 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
310 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
312 #define DONE_PRIORITY -1
313 #define MAX_PRIORITY 0x7fffffff
314 #define TAIL_PRIORITY 0x7ffffffe
315 #define LAUNCH_PRIORITY 0x7f000001
316 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
317 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
319 /* Vector indexed by INSN_UID giving number of insns referring to this insn. */
320 static int *insn_ref_count
;
321 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
323 /* Vector indexed by INSN_UID giving line-number note in effect for each
324 insn. For line-number notes, this indicates whether the note may be
326 static rtx
*line_note
;
327 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
329 /* Vector indexed by basic block number giving the starting line-number
330 for each basic block. */
331 static rtx
*line_note_head
;
333 /* List of important notes we must keep around. This is a pointer to the
334 last element in the list. */
335 static rtx note_list
;
337 /* Regsets telling whether a given register is live or dead before the last
338 scheduled insn. Must scan the instructions once before scheduling to
339 determine what registers are live or dead at the end of the block. */
340 static regset bb_live_regs
;
342 /* Regset telling whether a given register is live after the insn currently
343 being scheduled. Before processing an insn, this is equal to bb_live_regs
344 above. This is used so that we can find registers that are newly born/dead
345 after processing an insn. */
346 static regset old_live_regs
;
348 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
349 during the initial scan and reused later. If there are not exactly as
350 many REG_DEAD notes in the post scheduled code as there were in the
351 prescheduled code then we trigger an abort because this indicates a bug. */
352 static rtx dead_notes
;
356 /* An instruction is ready to be scheduled when all insns preceding it
357 have already been scheduled. It is important to ensure that all
358 insns which use its result will not be executed until its result
359 has been computed. An insn is maintained in one of four structures:
361 (P) the "Pending" set of insns which cannot be scheduled until
362 their dependencies have been satisfied.
363 (Q) the "Queued" set of insns that can be scheduled when sufficient
365 (R) the "Ready" list of unscheduled, uncommitted insns.
366 (S) the "Scheduled" list of insns.
368 Initially, all insns are either "Pending" or "Ready" depending on
369 whether their dependencies are satisfied.
371 Insns move from the "Ready" list to the "Scheduled" list as they
372 are committed to the schedule. As this occurs, the insns in the
373 "Pending" list have their dependencies satisfied and move to either
374 the "Ready" list or the "Queued" set depending on whether
375 sufficient time has passed to make them ready. As time passes,
376 insns move from the "Queued" set to the "Ready" list. Insns may
377 move from the "Ready" list to the "Queued" set if they are blocked
378 due to a function unit conflict.
380 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
381 insns, i.e., those that are ready, queued, and pending.
382 The "Queued" set (Q) is implemented by the variable `insn_queue'.
383 The "Ready" list (R) is implemented by the variables `ready' and
385 The "Scheduled" list (S) is the new insn chain built by this pass.
387 The transition (R->S) is implemented in the scheduling loop in
388 `schedule_block' when the best insn to schedule is chosen.
389 The transition (R->Q) is implemented in `queue_insn' when an
390 insn is found to have a function unit conflict with the already
392 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
393 insns move from the ready list to the scheduled list.
394 The transition (Q->R) is implemented in 'queue_to_insn' as time
395 passes or stalls are introduced. */
397 /* Implement a circular buffer to delay instructions until sufficient
398 time has passed. INSN_QUEUE_SIZE is a power of two larger than
399 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
400 longest time an isnsn may be queued. */
401 static rtx insn_queue
[INSN_QUEUE_SIZE
];
402 static int q_ptr
= 0;
403 static int q_size
= 0;
404 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
405 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
407 /* Vector indexed by INSN_UID giving the minimum clock tick at which
408 the insn becomes ready. This is used to note timing constraints for
409 insns in the pending list. */
410 static int *insn_tick
;
411 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
413 /* Data structure for keeping track of register information
414 during that register's life. */
423 /* Forward declarations. */
424 static void add_dependence
PROTO ((rtx
, rtx
, enum reg_note
));
425 static void remove_dependence
PROTO ((rtx
, rtx
));
426 static rtx find_insn_list
PROTO ((rtx
, rtx
));
427 static int insn_unit
PROTO ((rtx
));
428 static unsigned int blockage_range
PROTO ((int, rtx
));
429 static void clear_units
PROTO ((void));
430 static int actual_hazard_this_instance
PROTO ((int, int, rtx
, int, int));
431 static void schedule_unit
PROTO ((int, rtx
, int));
432 static int actual_hazard
PROTO ((int, rtx
, int, int));
433 static int potential_hazard
PROTO ((int, rtx
, int));
434 static int insn_cost
PROTO ((rtx
, rtx
, rtx
));
435 static int priority
PROTO ((rtx
));
436 static void free_pending_lists
PROTO ((void));
437 static void add_insn_mem_dependence
PROTO ((rtx
*, rtx
*, rtx
, rtx
));
438 static void flush_pending_lists
PROTO ((rtx
, int));
439 static void sched_analyze_1
PROTO ((rtx
, rtx
));
440 static void sched_analyze_2
PROTO ((rtx
, rtx
));
441 static void sched_analyze_insn
PROTO ((rtx
, rtx
, rtx
));
442 static void sched_analyze
PROTO ((rtx
, rtx
));
443 static void sched_note_set
PROTO ((rtx
, int));
444 static int rank_for_schedule
PROTO ((const GENERIC_PTR
, const GENERIC_PTR
));
445 static void swap_sort
PROTO ((rtx
*, int));
446 static void queue_insn
PROTO ((rtx
, int));
447 static int schedule_insn
PROTO ((rtx
, rtx
*, int, int));
448 static void create_reg_dead_note
PROTO ((rtx
, rtx
));
449 static void attach_deaths
PROTO ((rtx
, rtx
, int));
450 static void attach_deaths_insn
PROTO ((rtx
));
451 static int new_sometimes_live
PROTO ((struct sometimes
*, int, int));
452 static void finish_sometimes_live
PROTO ((struct sometimes
*, int));
453 static int schedule_block
PROTO ((int, int));
454 static void split_hard_reg_notes
PROTO ((rtx
, rtx
, rtx
));
455 static void new_insn_dead_notes
PROTO ((rtx
, rtx
, rtx
, rtx
));
456 static void update_n_sets
PROTO ((rtx
, int));
457 static char *safe_concat
PROTO ((char *, char *, char *));
458 static int insn_issue_delay
PROTO ((rtx
));
459 static int birthing_insn_p
PROTO ((rtx
));
460 static void adjust_priority
PROTO ((rtx
));
462 /* Mapping of insns to their original block prior to scheduling. */
463 static int *insn_orig_block
;
464 #define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
466 /* Some insns (e.g. call) are not allowed to move across blocks. */
467 static char *cant_move
;
468 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
470 /* Control flow graph edges are kept in circular lists. */
479 static haifa_edge
*edge_table
;
481 #define NEXT_IN(edge) (edge_table[edge].next_in)
482 #define NEXT_OUT(edge) (edge_table[edge].next_out)
483 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
484 #define TO_BLOCK(edge) (edge_table[edge].to_block)
486 /* Number of edges in the control flow graph. (in fact larger than
487 that by 1, since edge 0 is unused.) */
490 /* Circular list of incoming/outgoing edges of a block */
491 static int *in_edges
;
492 static int *out_edges
;
494 #define IN_EDGES(block) (in_edges[block])
495 #define OUT_EDGES(block) (out_edges[block])
497 /* List of labels which cannot be deleted, needed for control
498 flow graph construction. */
499 extern rtx forced_labels
;
502 static int is_cfg_nonregular
PROTO ((void));
503 static int build_control_flow
PROTO ((int_list_ptr
*, int_list_ptr
*,
505 static void new_edge
PROTO ((int, int));
508 /* A region is the main entity for interblock scheduling: insns
509 are allowed to move between blocks in the same region, along
510 control flow graph edges, in the 'up' direction. */
513 int rgn_nr_blocks
; /* number of blocks in region */
514 int rgn_blocks
; /* blocks in the region (actually index in rgn_bb_table) */
518 /* Number of regions in the procedure */
519 static int nr_regions
;
521 /* Table of region descriptions */
522 static region
*rgn_table
;
524 /* Array of lists of regions' blocks */
525 static int *rgn_bb_table
;
527 /* Topological order of blocks in the region (if b2 is reachable from
528 b1, block_to_bb[b2] > block_to_bb[b1]).
529 Note: A basic block is always referred to by either block or b,
530 while its topological order name (in the region) is refered to by
533 static int *block_to_bb
;
535 /* The number of the region containing a block. */
536 static int *containing_rgn
;
538 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
539 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
540 #define BLOCK_TO_BB(block) (block_to_bb[block])
541 #define CONTAINING_RGN(block) (containing_rgn[block])
543 void debug_regions
PROTO ((void));
544 static void find_single_block_region
PROTO ((void));
545 static void find_rgns
PROTO ((int_list_ptr
*, int_list_ptr
*,
546 int *, int *, sbitmap
*));
547 static int too_large
PROTO ((int, int *, int *));
549 extern void debug_live
PROTO ((int, int));
551 /* Blocks of the current region being scheduled. */
552 static int current_nr_blocks
;
553 static int current_blocks
;
555 /* The mapping from bb to block */
556 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
559 /* Bit vectors and bitset operations are needed for computations on
560 the control flow graph. */
562 typedef unsigned HOST_WIDE_INT
*bitset
;
565 int *first_member
; /* pointer to the list start in bitlst_table. */
566 int nr_members
; /* the number of members of the bit list. */
570 static int bitlst_table_last
;
571 static int bitlst_table_size
;
572 static int *bitlst_table
;
574 static char bitset_member
PROTO ((bitset
, int, int));
575 static void extract_bitlst
PROTO ((bitset
, int, bitlst
*));
577 /* target info declarations.
579 The block currently being scheduled is referred to as the "target" block,
580 while other blocks in the region from which insns can be moved to the
581 target are called "source" blocks. The candidate structure holds info
582 about such sources: are they valid? Speculative? Etc. */
583 typedef bitlst bblst
;
594 static candidate
*candidate_table
;
596 /* A speculative motion requires checking live information on the path
597 from 'source' to 'target'. The split blocks are those to be checked.
598 After a speculative motion, live information should be modified in
601 Lists of split and update blocks for each candidate of the current
602 target are in array bblst_table */
603 static int *bblst_table
, bblst_size
, bblst_last
;
605 #define IS_VALID(src) ( candidate_table[src].is_valid )
606 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
607 #define SRC_PROB(src) ( candidate_table[src].src_prob )
609 /* The bb being currently scheduled. */
610 static int target_bb
;
613 typedef bitlst edgelst
;
615 /* target info functions */
616 static void split_edges
PROTO ((int, int, edgelst
*));
617 static void compute_trg_info
PROTO ((int));
618 void debug_candidate
PROTO ((int));
619 void debug_candidates
PROTO ((int));
622 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
623 typedef bitset bbset
;
625 /* Number of words of the bbset. */
626 static int bbset_size
;
628 /* Dominators array: dom[i] contains the bbset of dominators of
629 bb i in the region. */
632 /* bb 0 is the only region entry */
633 #define IS_RGN_ENTRY(bb) (!bb)
635 /* Is bb_src dominated by bb_trg. */
636 #define IS_DOMINATED(bb_src, bb_trg) \
637 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
639 /* Probability: Prob[i] is a float in [0, 1] which is the probability
640 of bb i relative to the region entry. */
643 /* The probability of bb_src, relative to bb_trg. Note, that while the
644 'prob[bb]' is a float in [0, 1], this macro returns an integer
646 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
649 /* Bit-set of edges, where bit i stands for edge i. */
650 typedef bitset edgeset
;
652 /* Number of edges in the region. */
653 static int rgn_nr_edges
;
655 /* Array of size rgn_nr_edges. */
656 static int *rgn_edges
;
658 /* Number of words in an edgeset. */
659 static int edgeset_size
;
661 /* Mapping from each edge in the graph to its number in the rgn. */
662 static int *edge_to_bit
;
663 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
665 /* The split edges of a source bb is different for each target
666 bb. In order to compute this efficiently, the 'potential-split edges'
667 are computed for each bb prior to scheduling a region. This is actually
668 the split edges of each bb relative to the region entry.
670 pot_split[bb] is the set of potential split edges of bb. */
671 static edgeset
*pot_split
;
673 /* For every bb, a set of its ancestor edges. */
674 static edgeset
*ancestor_edges
;
676 static void compute_dom_prob_ps
PROTO ((int));
678 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
679 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
680 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
681 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
683 /* parameters affecting the decision of rank_for_schedule() */
684 #define MIN_DIFF_PRIORITY 2
685 #define MIN_PROBABILITY 40
686 #define MIN_PROB_DIFF 10
688 /* speculative scheduling functions */
689 static int check_live_1
PROTO ((int, rtx
));
690 static void update_live_1
PROTO ((int, rtx
));
691 static int check_live
PROTO ((rtx
, int));
692 static void update_live
PROTO ((rtx
, int));
693 static void set_spec_fed
PROTO ((rtx
));
694 static int is_pfree
PROTO ((rtx
, int, int));
695 static int find_conditional_protection
PROTO ((rtx
, int));
696 static int is_conditionally_protected
PROTO ((rtx
, int, int));
697 static int may_trap_exp
PROTO ((rtx
, int));
698 static int haifa_classify_insn
PROTO ((rtx
));
699 static int is_prisky
PROTO ((rtx
, int, int));
700 static int is_exception_free
PROTO ((rtx
, int, int));
702 static char find_insn_mem_list
PROTO ((rtx
, rtx
, rtx
, rtx
));
703 static void compute_block_forward_dependences
PROTO ((int));
704 static void init_rgn_data_dependences
PROTO ((int));
705 static void add_branch_dependences
PROTO ((rtx
, rtx
));
706 static void compute_block_backward_dependences
PROTO ((int));
707 void debug_dependencies
PROTO ((void));
709 /* Notes handling mechanism:
710 =========================
711 Generally, NOTES are saved before scheduling and restored after scheduling.
712 The scheduler distinguishes between three types of notes:
714 (1) LINE_NUMBER notes, generated and used for debugging. Here,
715 before scheduling a region, a pointer to the LINE_NUMBER note is
716 added to the insn following it (in save_line_notes()), and the note
717 is removed (in rm_line_notes() and unlink_line_notes()). After
718 scheduling the region, this pointer is used for regeneration of
719 the LINE_NUMBER note (in restore_line_notes()).
721 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
722 Before scheduling a region, a pointer to the note is added to the insn
723 that follows or precedes it. (This happens as part of the data dependence
724 computation). After scheduling an insn, the pointer contained in it is
725 used for regenerating the corresponding note (in reemit_notes).
727 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
728 these notes are put in a list (in rm_other_notes() and
729 unlink_other_notes ()). After scheduling the block, these notes are
730 inserted at the beginning of the block (in schedule_block()). */
732 static rtx unlink_other_notes
PROTO ((rtx
, rtx
));
733 static rtx unlink_line_notes
PROTO ((rtx
, rtx
));
734 static void rm_line_notes
PROTO ((int));
735 static void save_line_notes
PROTO ((int));
736 static void restore_line_notes
PROTO ((int));
737 static void rm_redundant_line_notes
PROTO ((void));
738 static void rm_other_notes
PROTO ((rtx
, rtx
));
739 static rtx reemit_notes
PROTO ((rtx
, rtx
));
741 static void get_block_head_tail
PROTO ((int, rtx
*, rtx
*));
743 static void find_pre_sched_live
PROTO ((int));
744 static void find_post_sched_live
PROTO ((int));
745 static void update_reg_usage
PROTO ((void));
746 static int queue_to_ready
PROTO ((rtx
[], int));
748 static void debug_ready_list
PROTO ((rtx
[], int));
749 static void init_target_units
PROTO ((void));
750 static void insn_print_units
PROTO ((rtx
));
751 static int get_visual_tbl_length
PROTO ((void));
752 static void init_block_visualization
PROTO ((void));
753 static void print_block_visualization
PROTO ((int, char *));
754 static void visualize_scheduled_insns
PROTO ((int, int));
755 static void visualize_no_unit
PROTO ((rtx
));
756 static void visualize_stall_cycles
PROTO ((int, int));
757 static void print_exp
PROTO ((char *, rtx
, int));
758 static void print_value
PROTO ((char *, rtx
, int));
759 static void print_pattern
PROTO ((char *, rtx
, int));
760 static void print_insn
PROTO ((char *, rtx
, int));
761 void debug_reg_vector
PROTO ((regset
));
763 static rtx move_insn1
PROTO ((rtx
, rtx
));
764 static rtx move_insn
PROTO ((rtx
, rtx
));
765 static rtx group_leader
PROTO ((rtx
));
766 static int set_priorities
PROTO ((int));
767 static void init_rtx_vector
PROTO ((rtx
**, rtx
*, int, int));
768 static void schedule_region
PROTO ((int));
770 #endif /* INSN_SCHEDULING */
772 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
774 /* Helper functions for instruction scheduling. */
776 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
777 static rtx unused_insn_list
;
779 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
780 static rtx unused_expr_list
;
782 static void free_list
PROTO ((rtx
*, rtx
*));
783 static rtx alloc_INSN_LIST
PROTO ((rtx
, rtx
));
784 static rtx alloc_EXPR_LIST
PROTO ((int, rtx
, rtx
));
787 free_list (listp
, unused_listp
)
788 rtx
*listp
, *unused_listp
;
790 register rtx link
, prev_link
;
796 link
= XEXP (prev_link
, 1);
801 link
= XEXP (link
, 1);
804 XEXP (prev_link
, 1) = *unused_listp
;
805 *unused_listp
= *listp
;
810 alloc_INSN_LIST (val
, next
)
815 if (unused_insn_list
)
817 r
= unused_insn_list
;
818 unused_insn_list
= XEXP (r
, 1);
821 PUT_REG_NOTE_KIND (r
, VOIDmode
);
824 r
= gen_rtx_INSN_LIST (VOIDmode
, val
, next
);
830 alloc_EXPR_LIST (kind
, val
, next
)
836 if (unused_expr_list
)
838 r
= unused_expr_list
;
839 unused_expr_list
= XEXP (r
, 1);
842 PUT_REG_NOTE_KIND (r
, kind
);
845 r
= gen_rtx_EXPR_LIST (kind
, val
, next
);
850 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
851 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
852 of dependence that this link represents. */
855 add_dependence (insn
, elem
, dep_type
)
858 enum reg_note dep_type
;
862 /* Don't depend an insn on itself. */
866 /* We can get a dependency on deleted insns due to optimizations in
867 the register allocation and reloading or due to splitting. Any
868 such dependency is useless and can be ignored. */
869 if (GET_CODE (elem
) == NOTE
)
872 /* If elem is part of a sequence that must be scheduled together, then
873 make the dependence point to the last insn of the sequence.
874 When HAVE_cc0, it is possible for NOTEs to exist between users and
875 setters of the condition codes, so we must skip past notes here.
876 Otherwise, NOTEs are impossible here. */
878 next
= NEXT_INSN (elem
);
881 while (next
&& GET_CODE (next
) == NOTE
)
882 next
= NEXT_INSN (next
);
885 if (next
&& SCHED_GROUP_P (next
)
886 && GET_CODE (next
) != CODE_LABEL
)
888 /* Notes will never intervene here though, so don't bother checking
890 /* We must reject CODE_LABELs, so that we don't get confused by one
891 that has LABEL_PRESERVE_P set, which is represented by the same
892 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
894 while (NEXT_INSN (next
) && SCHED_GROUP_P (NEXT_INSN (next
))
895 && GET_CODE (NEXT_INSN (next
)) != CODE_LABEL
)
896 next
= NEXT_INSN (next
);
898 /* Again, don't depend an insn on itself. */
902 /* Make the dependence to NEXT, the last insn of the group, instead
903 of the original ELEM. */
907 #ifdef INSN_SCHEDULING
908 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
909 No need for interblock dependences with calls, since
910 calls are not moved between blocks. Note: the edge where
911 elem is a CALL is still required. */
912 if (GET_CODE (insn
) == CALL_INSN
913 && (INSN_BB (elem
) != INSN_BB (insn
)))
918 /* Check that we don't already have this dependence. */
919 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
920 if (XEXP (link
, 0) == elem
)
922 /* If this is a more restrictive type of dependence than the existing
923 one, then change the existing dependence to this type. */
924 if ((int) dep_type
< (int) REG_NOTE_KIND (link
))
925 PUT_REG_NOTE_KIND (link
, dep_type
);
928 /* Might want to check one level of transitivity to save conses. */
930 link
= alloc_INSN_LIST (elem
, LOG_LINKS (insn
));
931 LOG_LINKS (insn
) = link
;
933 /* Insn dependency, not data dependency. */
934 PUT_REG_NOTE_KIND (link
, dep_type
);
937 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
938 of INSN. Abort if not found. */
941 remove_dependence (insn
, elem
)
945 rtx prev
, link
, next
;
948 for (prev
= 0, link
= LOG_LINKS (insn
); link
; link
= next
)
950 next
= XEXP (link
, 1);
951 if (XEXP (link
, 0) == elem
)
954 XEXP (prev
, 1) = next
;
956 LOG_LINKS (insn
) = next
;
958 XEXP (link
, 1) = unused_insn_list
;
959 unused_insn_list
= link
;
972 #ifndef INSN_SCHEDULING
974 schedule_insns (dump_file
)
984 #define HAIFA_INLINE __inline
987 /* Computation of memory dependencies. */
989 /* The *_insns and *_mems are paired lists. Each pending memory operation
990 will have a pointer to the MEM rtx on one list and a pointer to the
991 containing insn on the other list in the same place in the list. */
993 /* We can't use add_dependence like the old code did, because a single insn
994 may have multiple memory accesses, and hence needs to be on the list
995 once for each memory access. Add_dependence won't let you add an insn
996 to a list more than once. */
998 /* An INSN_LIST containing all insns with pending read operations. */
999 static rtx pending_read_insns
;
1001 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
1002 static rtx pending_read_mems
;
1004 /* An INSN_LIST containing all insns with pending write operations. */
1005 static rtx pending_write_insns
;
1007 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
1008 static rtx pending_write_mems
;
1010 /* Indicates the combined length of the two pending lists. We must prevent
1011 these lists from ever growing too large since the number of dependencies
1012 produced is at least O(N*N), and execution time is at least O(4*N*N), as
1013 a function of the length of these pending lists. */
1015 static int pending_lists_length
;
1017 /* The last insn upon which all memory references must depend.
1018 This is an insn which flushed the pending lists, creating a dependency
1019 between it and all previously pending memory references. This creates
1020 a barrier (or a checkpoint) which no memory reference is allowed to cross.
1022 This includes all non constant CALL_INSNs. When we do interprocedural
1023 alias analysis, this restriction can be relaxed.
1024 This may also be an INSN that writes memory if the pending lists grow
1027 static rtx last_pending_memory_flush
;
1029 /* The last function call we have seen. All hard regs, and, of course,
1030 the last function call, must depend on this. */
1032 static rtx last_function_call
;
1034 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
1035 that does not already cross a call. We create dependencies between each
1036 of those insn and the next call insn, to ensure that they won't cross a call
1037 after scheduling is done. */
1039 static rtx sched_before_next_call
;
1041 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1042 so that insns independent of the last scheduled insn will be preferred
1043 over dependent instructions. */
1045 static rtx last_scheduled_insn
;
1047 /* Data structures for the computation of data dependences in a regions. We
1048 keep one copy of each of the declared above variables for each bb in the
1049 region. Before analyzing the data dependences for a bb, its variables
1050 are initialized as a function of the variables of its predecessors. When
1051 the analysis for a bb completes, we save the contents of each variable X
1052 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
1053 copied to bb_pending_read_insns[bb]. Another change is that few
1054 variables are now a list of insns rather than a single insn:
1055 last_pending_memory_flash, last_function_call, reg_last_sets. The
1056 manipulation of these variables was changed appropriately. */
1058 static rtx
**bb_reg_last_uses
;
1059 static rtx
**bb_reg_last_sets
;
1060 static rtx
**bb_reg_last_clobbers
;
1062 static rtx
*bb_pending_read_insns
;
1063 static rtx
*bb_pending_read_mems
;
1064 static rtx
*bb_pending_write_insns
;
1065 static rtx
*bb_pending_write_mems
;
1066 static int *bb_pending_lists_length
;
1068 static rtx
*bb_last_pending_memory_flush
;
1069 static rtx
*bb_last_function_call
;
1070 static rtx
*bb_sched_before_next_call
;
1072 /* functions for construction of the control flow graph. */
1074 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1076 We decide not to build the control flow graph if there is possibly more
1077 than one entry to the function, if computed branches exist, of if we
1078 have nonlocal gotos. */
1081 is_cfg_nonregular ()
1087 /* If we have a label that could be the target of a nonlocal goto, then
1088 the cfg is not well structured. */
1089 if (nonlocal_goto_handler_labels
)
1092 /* If we have any forced labels, then the cfg is not well structured. */
1096 /* If this function has a computed jump, then we consider the cfg
1097 not well structured. */
1098 if (current_function_has_computed_jump
)
1101 /* If we have exception handlers, then we consider the cfg not well
1102 structured. ?!? We should be able to handle this now that flow.c
1103 computes an accurate cfg for EH. */
1104 if (exception_handler_labels
)
1107 /* If we have non-jumping insns which refer to labels, then we consider
1108 the cfg not well structured. */
1109 /* check for labels referred to other thn by jumps */
1110 for (b
= 0; b
< n_basic_blocks
; b
++)
1111 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
1113 code
= GET_CODE (insn
);
1114 if (GET_RTX_CLASS (code
) == 'i')
1118 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1119 if (REG_NOTE_KIND (note
) == REG_LABEL
)
1123 if (insn
== BLOCK_END (b
))
1127 /* All the tests passed. Consider the cfg well structured. */
1131 /* Build the control flow graph and set nr_edges.
1133 Instead of trying to build a cfg ourselves, we rely on flow to
1134 do it for us. Stamp out useless code (and bug) duplication.
1136 Return nonzero if an irregularity in the cfg is found which would
1137 prevent cross block scheduling. */
1140 build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
)
1141 int_list_ptr
*s_preds
;
1142 int_list_ptr
*s_succs
;
1150 /* Count the number of edges in the cfg. */
1153 for (i
= 0; i
< n_basic_blocks
; i
++)
1155 nr_edges
+= num_succs
[i
];
1157 /* Unreachable loops with more than one basic block are detected
1158 during the DFS traversal in find_rgns.
1160 Unreachable loops with a single block are detected here. This
1161 test is redundant with the one in find_rgns, but it's much
1162 cheaper to go ahead and catch the trivial case here. */
1163 if (num_preds
[i
] == 0
1164 || (num_preds
[i
] == 1 && INT_LIST_VAL (s_preds
[i
]) == i
))
1168 /* Account for entry/exit edges. */
1171 in_edges
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
1172 out_edges
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
1173 bzero ((char *) in_edges
, n_basic_blocks
* sizeof (int));
1174 bzero ((char *) out_edges
, n_basic_blocks
* sizeof (int));
1176 edge_table
= (haifa_edge
*) xmalloc ((nr_edges
) * sizeof (haifa_edge
));
1177 bzero ((char *) edge_table
, ((nr_edges
) * sizeof (haifa_edge
)));
1180 for (i
= 0; i
< n_basic_blocks
; i
++)
1181 for (succ
= s_succs
[i
]; succ
; succ
= succ
->next
)
1183 if (INT_LIST_VAL (succ
) != EXIT_BLOCK
)
1184 new_edge (i
, INT_LIST_VAL (succ
));
1187 /* increment by 1, since edge 0 is unused. */
1194 /* Record an edge in the control flow graph from SOURCE to TARGET.
1196 In theory, this is redundant with the s_succs computed above, but
1197 we have not converted all of haifa to use information from the
1201 new_edge (source
, target
)
1205 int curr_edge
, fst_edge
;
1207 /* check for duplicates */
1208 fst_edge
= curr_edge
= OUT_EDGES (source
);
1211 if (FROM_BLOCK (curr_edge
) == source
1212 && TO_BLOCK (curr_edge
) == target
)
1217 curr_edge
= NEXT_OUT (curr_edge
);
1219 if (fst_edge
== curr_edge
)
1225 FROM_BLOCK (e
) = source
;
1226 TO_BLOCK (e
) = target
;
1228 if (OUT_EDGES (source
))
1230 next_edge
= NEXT_OUT (OUT_EDGES (source
));
1231 NEXT_OUT (OUT_EDGES (source
)) = e
;
1232 NEXT_OUT (e
) = next_edge
;
1236 OUT_EDGES (source
) = e
;
1240 if (IN_EDGES (target
))
1242 next_edge
= NEXT_IN (IN_EDGES (target
));
1243 NEXT_IN (IN_EDGES (target
)) = e
;
1244 NEXT_IN (e
) = next_edge
;
1248 IN_EDGES (target
) = e
;
1254 /* BITSET macros for operations on the control flow graph. */
1256 /* Compute bitwise union of two bitsets. */
1257 #define BITSET_UNION(set1, set2, len) \
1258 do { register bitset tp = set1, sp = set2; \
1260 for (i = 0; i < len; i++) \
1261 *(tp++) |= *(sp++); } while (0)
1263 /* Compute bitwise intersection of two bitsets. */
1264 #define BITSET_INTER(set1, set2, len) \
1265 do { register bitset tp = set1, sp = set2; \
1267 for (i = 0; i < len; i++) \
1268 *(tp++) &= *(sp++); } while (0)
1270 /* Compute bitwise difference of two bitsets. */
1271 #define BITSET_DIFFER(set1, set2, len) \
1272 do { register bitset tp = set1, sp = set2; \
1274 for (i = 0; i < len; i++) \
1275 *(tp++) &= ~*(sp++); } while (0)
1277 /* Inverts every bit of bitset 'set' */
1278 #define BITSET_INVERT(set, len) \
1279 do { register bitset tmpset = set; \
1281 for (i = 0; i < len; i++, tmpset++) \
1282 *tmpset = ~*tmpset; } while (0)
1284 /* Turn on the index'th bit in bitset set. */
1285 #define BITSET_ADD(set, index, len) \
1287 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1290 set[index/HOST_BITS_PER_WIDE_INT] |= \
1291 1 << (index % HOST_BITS_PER_WIDE_INT); \
1294 /* Turn off the index'th bit in set. */
1295 #define BITSET_REMOVE(set, index, len) \
1297 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1300 set[index/HOST_BITS_PER_WIDE_INT] &= \
1301 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1305 /* Check if the index'th bit in bitset set is on. */
1308 bitset_member (set
, index
, len
)
1312 if (index
>= HOST_BITS_PER_WIDE_INT
* len
)
1314 return (set
[index
/ HOST_BITS_PER_WIDE_INT
] &
1315 1 << (index
% HOST_BITS_PER_WIDE_INT
)) ? 1 : 0;
1319 /* Translate a bit-set SET to a list BL of the bit-set members. */
1322 extract_bitlst (set
, len
, bl
)
1328 unsigned HOST_WIDE_INT word
;
1330 /* bblst table space is reused in each call to extract_bitlst */
1331 bitlst_table_last
= 0;
1333 bl
->first_member
= &bitlst_table
[bitlst_table_last
];
1336 for (i
= 0; i
< len
; i
++)
1339 offset
= i
* HOST_BITS_PER_WIDE_INT
;
1340 for (j
= 0; word
; j
++)
1344 bitlst_table
[bitlst_table_last
++] = offset
;
1355 /* functions for the construction of regions */
1357 /* Print the regions, for debugging purposes. Callable from debugger. */
1364 fprintf (dump
, "\n;; ------------ REGIONS ----------\n\n");
1365 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
1367 fprintf (dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
1368 rgn_table
[rgn
].rgn_nr_blocks
);
1369 fprintf (dump
, ";;\tbb/block: ");
1371 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
1373 current_blocks
= RGN_BLOCKS (rgn
);
1375 if (bb
!= BLOCK_TO_BB (BB_TO_BLOCK (bb
)))
1378 fprintf (dump
, " %d/%d ", bb
, BB_TO_BLOCK (bb
));
1381 fprintf (dump
, "\n\n");
1386 /* Build a single block region for each basic block in the function.
1387 This allows for using the same code for interblock and basic block
1391 find_single_block_region ()
1395 for (i
= 0; i
< n_basic_blocks
; i
++)
1397 rgn_bb_table
[i
] = i
;
1398 RGN_NR_BLOCKS (i
) = 1;
1400 CONTAINING_RGN (i
) = i
;
1401 BLOCK_TO_BB (i
) = 0;
1403 nr_regions
= n_basic_blocks
;
1407 /* Update number of blocks and the estimate for number of insns
1408 in the region. Return 1 if the region is "too large" for interblock
1409 scheduling (compile time considerations), otherwise return 0. */
1412 too_large (block
, num_bbs
, num_insns
)
1413 int block
, *num_bbs
, *num_insns
;
1416 (*num_insns
) += (INSN_LUID (BLOCK_END (block
)) -
1417 INSN_LUID (BLOCK_HEAD (block
)));
1418 if ((*num_bbs
> MAX_RGN_BLOCKS
) || (*num_insns
> MAX_RGN_INSNS
))
1425 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1426 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1427 loop containing blk. */
1428 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1430 if (max_hdr[blk] == -1) \
1431 max_hdr[blk] = hdr; \
1432 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1433 RESET_BIT (inner, hdr); \
1434 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1436 RESET_BIT (inner,max_hdr[blk]); \
1437 max_hdr[blk] = hdr; \
1442 /* Find regions for interblock scheduling.
1444 A region for scheduling can be:
1446 * A loop-free procedure, or
1448 * A reducible inner loop, or
1450 * A basic block not contained in any other region.
1453 ?!? In theory we could build other regions based on extended basic
1454 blocks or reverse extended basic blocks. Is it worth the trouble?
1456 Loop blocks that form a region are put into the region's block list
1457 in topological order.
1459 This procedure stores its results into the following global (ick) variables
1468 We use dominator relationships to avoid making regions out of non-reducible
1471 This procedure needs to be converted to work on pred/succ lists instead
1472 of edge tables. That would simplify it somewhat. */
1475 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
)
1476 int_list_ptr
*s_preds
;
1477 int_list_ptr
*s_succs
;
1482 int *max_hdr
, *dfs_nr
, *stack
, *queue
, *degree
;
1484 int node
, child
, loop_head
, i
, head
, tail
;
1485 int count
= 0, sp
, idx
= 0, current_edge
= out_edges
[0];
1486 int num_bbs
, num_insns
, unreachable
;
1487 int too_large_failure
;
1489 /* Note if an edge has been passed. */
1492 /* Note if a block is a natural loop header. */
1495 /* Note if a block is an natural inner loop header. */
1498 /* Note if a block is in the block queue. */
1501 /* Note if a block is in the block queue. */
1504 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1505 and a mapping from block to its loop header (if the block is contained
1506 in a loop, else -1).
1508 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1509 be used as inputs to the second traversal.
1511 STACK, SP and DFS_NR are only used during the first traversal. */
1513 /* Allocate and initialize variables for the first traversal. */
1514 max_hdr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1515 dfs_nr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1516 bzero ((char *) dfs_nr
, n_basic_blocks
* sizeof (int));
1517 stack
= (int *) alloca (nr_edges
* sizeof (int));
1519 inner
= sbitmap_alloc (n_basic_blocks
);
1520 sbitmap_ones (inner
);
1522 header
= sbitmap_alloc (n_basic_blocks
);
1523 sbitmap_zero (header
);
1525 passed
= sbitmap_alloc (nr_edges
);
1526 sbitmap_zero (passed
);
1528 in_queue
= sbitmap_alloc (n_basic_blocks
);
1529 sbitmap_zero (in_queue
);
1531 in_stack
= sbitmap_alloc (n_basic_blocks
);
1532 sbitmap_zero (in_stack
);
1534 for (i
= 0; i
< n_basic_blocks
; i
++)
1537 /* DFS traversal to find inner loops in the cfg. */
1542 if (current_edge
== 0 || TEST_BIT (passed
, current_edge
))
1544 /* We have reached a leaf node or a node that was already
1545 processed. Pop edges off the stack until we find
1546 an edge that has not yet been processed. */
1548 && (current_edge
== 0 || TEST_BIT (passed
, current_edge
)))
1550 /* Pop entry off the stack. */
1551 current_edge
= stack
[sp
--];
1552 node
= FROM_BLOCK (current_edge
);
1553 child
= TO_BLOCK (current_edge
);
1554 RESET_BIT (in_stack
, child
);
1555 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1556 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1557 current_edge
= NEXT_OUT (current_edge
);
1560 /* See if have finished the DFS tree traversal. */
1561 if (sp
< 0 && TEST_BIT (passed
, current_edge
))
1564 /* Nope, continue the traversal with the popped node. */
1568 /* Process a node. */
1569 node
= FROM_BLOCK (current_edge
);
1570 child
= TO_BLOCK (current_edge
);
1571 SET_BIT (in_stack
, node
);
1572 dfs_nr
[node
] = ++count
;
1574 /* If the successor is in the stack, then we've found a loop.
1575 Mark the loop, if it is not a natural loop, then it will
1576 be rejected during the second traversal. */
1577 if (TEST_BIT (in_stack
, child
))
1580 SET_BIT (header
, child
);
1581 UPDATE_LOOP_RELATIONS (node
, child
);
1582 SET_BIT (passed
, current_edge
);
1583 current_edge
= NEXT_OUT (current_edge
);
1587 /* If the child was already visited, then there is no need to visit
1588 it again. Just update the loop relationships and restart
1592 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1593 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1594 SET_BIT (passed
, current_edge
);
1595 current_edge
= NEXT_OUT (current_edge
);
1599 /* Push an entry on the stack and continue DFS traversal. */
1600 stack
[++sp
] = current_edge
;
1601 SET_BIT (passed
, current_edge
);
1602 current_edge
= OUT_EDGES (child
);
1605 /* Another check for unreachable blocks. The earlier test in
1606 is_cfg_nonregular only finds unreachable blocks that do not
1609 The DFS traversal will mark every block that is reachable from
1610 the entry node by placing a nonzero value in dfs_nr. Thus if
1611 dfs_nr is zero for any block, then it must be unreachable. */
1613 for (i
= 0; i
< n_basic_blocks
; i
++)
1620 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1621 to hold degree counts. */
1624 /* Compute the in-degree of every block in the graph */
1625 for (i
= 0; i
< n_basic_blocks
; i
++)
1626 degree
[i
] = num_preds
[i
];
1628 /* Do not perform region scheduling if there are any unreachable
1633 SET_BIT (header
, 0);
1635 /* Second travsersal:find reducible inner loops and topologically sort
1636 block of each region. */
1638 queue
= (int *) alloca (n_basic_blocks
* sizeof (int));
1640 /* Find blocks which are inner loop headers. We still have non-reducible
1641 loops to consider at this point. */
1642 for (i
= 0; i
< n_basic_blocks
; i
++)
1644 if (TEST_BIT (header
, i
) && TEST_BIT (inner
, i
))
1649 /* Now check that the loop is reducible. We do this separate
1650 from finding inner loops so that we do not find a reducible
1651 loop which contains an inner non-reducible loop.
1653 A simple way to find reducible/natrual loops is to verify
1654 that each block in the loop is dominated by the loop
1657 If there exists a block that is not dominated by the loop
1658 header, then the block is reachable from outside the loop
1659 and thus the loop is not a natural loop. */
1660 for (j
= 0; j
< n_basic_blocks
; j
++)
1662 /* First identify blocks in the loop, except for the loop
1664 if (i
== max_hdr
[j
] && i
!= j
)
1666 /* Now verify that the block is dominated by the loop
1668 if (!TEST_BIT (dom
[j
], i
))
1673 /* If we exited the loop early, then I is the header of a non
1674 reducible loop and we should quit processing it now. */
1675 if (j
!= n_basic_blocks
)
1678 /* I is a header of an inner loop, or block 0 in a subroutine
1679 with no loops at all. */
1681 too_large_failure
= 0;
1682 loop_head
= max_hdr
[i
];
1684 /* Decrease degree of all I's successors for topological
1686 for (ps
= s_succs
[i
]; ps
; ps
= ps
->next
)
1687 if (INT_LIST_VAL (ps
) != EXIT_BLOCK
1688 && INT_LIST_VAL (ps
) != ENTRY_BLOCK
)
1689 --degree
[INT_LIST_VAL(ps
)];
1691 /* Estimate # insns, and count # blocks in the region. */
1693 num_insns
= (INSN_LUID (BLOCK_END (i
))
1694 - INSN_LUID (BLOCK_HEAD (i
)));
1697 /* Find all loop latches (blocks which back edges to the loop
1698 header) or all the leaf blocks in the cfg has no loops.
1700 Place those blocks into the queue. */
1703 for (j
= 0; j
< n_basic_blocks
; j
++)
1704 /* Leaf nodes have only a single successor which must
1706 if (num_succs
[j
] == 1
1707 && INT_LIST_VAL (s_succs
[j
]) == EXIT_BLOCK
)
1710 SET_BIT (in_queue
, j
);
1712 if (too_large (j
, &num_bbs
, &num_insns
))
1714 too_large_failure
= 1;
1723 for (ps
= s_preds
[i
]; ps
; ps
= ps
->next
)
1725 node
= INT_LIST_VAL (ps
);
1727 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
)
1730 if (max_hdr
[node
] == loop_head
&& node
!= i
)
1732 /* This is a loop latch. */
1733 queue
[++tail
] = node
;
1734 SET_BIT (in_queue
, node
);
1736 if (too_large (node
, &num_bbs
, &num_insns
))
1738 too_large_failure
= 1;
1746 /* Now add all the blocks in the loop to the queue.
1748 We know the loop is a natural loop; however the algorithm
1749 above will not always mark certain blocks as being in the
1758 The algorithm in the DFS traversal may not mark B & D as part
1759 of the loop (ie they will not have max_hdr set to A).
1761 We know they can not be loop latches (else they would have
1762 had max_hdr set since they'd have a backedge to a dominator
1763 block). So we don't need them on the initial queue.
1765 We know they are part of the loop because they are dominated
1766 by the loop header and can be reached by a backwards walk of
1767 the edges starting with nodes on the initial queue.
1769 It is safe and desirable to include those nodes in the
1770 loop/scheduling region. To do so we would need to decrease
1771 the degree of a node if it is the target of a backedge
1772 within the loop itself as the node is placed in the queue.
1774 We do not do this because I'm not sure that the actual
1775 scheduling code will properly handle this case. ?!? */
1777 while (head
< tail
&& !too_large_failure
)
1780 child
= queue
[++head
];
1782 for (ps
= s_preds
[child
]; ps
; ps
= ps
->next
)
1784 node
= INT_LIST_VAL (ps
);
1786 /* See discussion above about nodes not marked as in
1787 this loop during the initial DFS traversal. */
1788 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
1789 || max_hdr
[node
] != loop_head
)
1794 else if (!TEST_BIT (in_queue
, node
) && node
!= i
)
1796 queue
[++tail
] = node
;
1797 SET_BIT (in_queue
, node
);
1799 if (too_large (node
, &num_bbs
, &num_insns
))
1801 too_large_failure
= 1;
1808 if (tail
>= 0 && !too_large_failure
)
1810 /* Place the loop header into list of region blocks. */
1812 rgn_bb_table
[idx
] = i
;
1813 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1814 RGN_BLOCKS (nr_regions
) = idx
++;
1815 CONTAINING_RGN (i
) = nr_regions
;
1816 BLOCK_TO_BB (i
) = count
= 0;
1818 /* Remove blocks from queue[] when their in degree becomes
1819 zero. Repeat until no blocks are left on the list. This
1820 produces a topological list of blocks in the region. */
1827 child
= queue
[head
];
1828 if (degree
[child
] == 0)
1831 rgn_bb_table
[idx
++] = child
;
1832 BLOCK_TO_BB (child
) = ++count
;
1833 CONTAINING_RGN (child
) = nr_regions
;
1834 queue
[head
] = queue
[tail
--];
1836 for (ps
= s_succs
[child
]; ps
; ps
= ps
->next
)
1837 if (INT_LIST_VAL (ps
) != ENTRY_BLOCK
1838 && INT_LIST_VAL (ps
) != EXIT_BLOCK
)
1839 --degree
[INT_LIST_VAL (ps
)];
1850 /* Any block that did not end up in a region is placed into a region
1852 for (i
= 0; i
< n_basic_blocks
; i
++)
1855 rgn_bb_table
[idx
] = i
;
1856 RGN_NR_BLOCKS (nr_regions
) = 1;
1857 RGN_BLOCKS (nr_regions
) = idx
++;
1858 CONTAINING_RGN (i
) = nr_regions
++;
1859 BLOCK_TO_BB (i
) = 0;
1870 /* functions for regions scheduling information */
1872 /* Compute dominators, probability, and potential-split-edges of bb.
1873 Assume that these values were already computed for bb's predecessors. */
1876 compute_dom_prob_ps (bb
)
1879 int nxt_in_edge
, fst_in_edge
, pred
;
1880 int fst_out_edge
, nxt_out_edge
, nr_out_edges
, nr_rgn_out_edges
;
1883 if (IS_RGN_ENTRY (bb
))
1885 BITSET_ADD (dom
[bb
], 0, bbset_size
);
1890 fst_in_edge
= nxt_in_edge
= IN_EDGES (BB_TO_BLOCK (bb
));
1892 /* intialize dom[bb] to '111..1' */
1893 BITSET_INVERT (dom
[bb
], bbset_size
);
1897 pred
= FROM_BLOCK (nxt_in_edge
);
1898 BITSET_INTER (dom
[bb
], dom
[BLOCK_TO_BB (pred
)], bbset_size
);
1900 BITSET_UNION (ancestor_edges
[bb
], ancestor_edges
[BLOCK_TO_BB (pred
)],
1903 BITSET_ADD (ancestor_edges
[bb
], EDGE_TO_BIT (nxt_in_edge
), edgeset_size
);
1906 nr_rgn_out_edges
= 0;
1907 fst_out_edge
= OUT_EDGES (pred
);
1908 nxt_out_edge
= NEXT_OUT (fst_out_edge
);
1909 BITSET_UNION (pot_split
[bb
], pot_split
[BLOCK_TO_BB (pred
)],
1912 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (fst_out_edge
), edgeset_size
);
1914 /* the successor doesn't belong the region? */
1915 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge
)) !=
1916 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1919 while (fst_out_edge
!= nxt_out_edge
)
1922 /* the successor doesn't belong the region? */
1923 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge
)) !=
1924 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1926 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (nxt_out_edge
), edgeset_size
);
1927 nxt_out_edge
= NEXT_OUT (nxt_out_edge
);
1931 /* now nr_rgn_out_edges is the number of region-exit edges from pred,
1932 and nr_out_edges will be the number of pred out edges not leaving
1934 nr_out_edges
-= nr_rgn_out_edges
;
1935 if (nr_rgn_out_edges
> 0)
1936 prob
[bb
] += 0.9 * prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1938 prob
[bb
] += prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1939 nxt_in_edge
= NEXT_IN (nxt_in_edge
);
1941 while (fst_in_edge
!= nxt_in_edge
);
1943 BITSET_ADD (dom
[bb
], bb
, bbset_size
);
1944 BITSET_DIFFER (pot_split
[bb
], ancestor_edges
[bb
], edgeset_size
);
1946 if (sched_verbose
>= 2)
1947 fprintf (dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
), (int) (100.0 * prob
[bb
]));
1948 } /* compute_dom_prob_ps */
1950 /* functions for target info */
1952 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1953 Note that bb_trg dominates bb_src. */
1956 split_edges (bb_src
, bb_trg
, bl
)
1961 int es
= edgeset_size
;
1962 edgeset src
= (edgeset
) alloca (es
* sizeof (HOST_WIDE_INT
));
1965 src
[es
] = (pot_split
[bb_src
])[es
];
1966 BITSET_DIFFER (src
, pot_split
[bb_trg
], edgeset_size
);
1967 extract_bitlst (src
, edgeset_size
, bl
);
1971 /* Find the valid candidate-source-blocks for the target block TRG, compute
1972 their probability, and check if they are speculative or not.
1973 For speculative sources, compute their update-blocks and split-blocks. */
1976 compute_trg_info (trg
)
1979 register candidate
*sp
;
1981 int check_block
, update_idx
;
1982 int i
, j
, k
, fst_edge
, nxt_edge
;
1984 /* define some of the fields for the target bb as well */
1985 sp
= candidate_table
+ trg
;
1987 sp
->is_speculative
= 0;
1990 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1992 sp
= candidate_table
+ i
;
1994 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1997 sp
->src_prob
= GET_SRC_PROB (i
, trg
);
1998 sp
->is_valid
= (sp
->src_prob
>= MIN_PROBABILITY
);
2003 split_edges (i
, trg
, &el
);
2004 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
2005 if (sp
->is_speculative
&& !flag_schedule_speculative
)
2011 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
2012 sp
->split_bbs
.nr_members
= el
.nr_members
;
2013 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
2014 bblst_table
[bblst_last
] =
2015 TO_BLOCK (rgn_edges
[el
.first_member
[j
]]);
2016 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
2018 for (j
= 0; j
< el
.nr_members
; j
++)
2020 check_block
= FROM_BLOCK (rgn_edges
[el
.first_member
[j
]]);
2021 fst_edge
= nxt_edge
= OUT_EDGES (check_block
);
2024 for (k
= 0; k
< el
.nr_members
; k
++)
2025 if (EDGE_TO_BIT (nxt_edge
) == el
.first_member
[k
])
2028 if (k
>= el
.nr_members
)
2030 bblst_table
[bblst_last
++] = TO_BLOCK (nxt_edge
);
2034 nxt_edge
= NEXT_OUT (nxt_edge
);
2036 while (fst_edge
!= nxt_edge
);
2038 sp
->update_bbs
.nr_members
= update_idx
;
2043 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
2045 sp
->is_speculative
= 0;
2049 } /* compute_trg_info */
2052 /* Print candidates info, for debugging purposes. Callable from debugger. */
2058 if (!candidate_table
[i
].is_valid
)
2061 if (candidate_table
[i
].is_speculative
)
2064 fprintf (dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
2066 fprintf (dump
, "split path: ");
2067 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
2069 int b
= candidate_table
[i
].split_bbs
.first_member
[j
];
2071 fprintf (dump
, " %d ", b
);
2073 fprintf (dump
, "\n");
2075 fprintf (dump
, "update path: ");
2076 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
2078 int b
= candidate_table
[i
].update_bbs
.first_member
[j
];
2080 fprintf (dump
, " %d ", b
);
2082 fprintf (dump
, "\n");
2086 fprintf (dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
2091 /* Print candidates info, for debugging purposes. Callable from debugger. */
2094 debug_candidates (trg
)
2099 fprintf (dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
2100 BB_TO_BLOCK (trg
), trg
);
2101 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
2102 debug_candidate (i
);
2106 /* functions for speculative scheduing */
2108 /* Return 0 if x is a set of a register alive in the beginning of one
2109 of the split-blocks of src, otherwise return 1. */
2112 check_live_1 (src
, x
)
2118 register rtx reg
= SET_DEST (x
);
2123 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2124 || GET_CODE (reg
) == SIGN_EXTRACT
2125 || GET_CODE (reg
) == STRICT_LOW_PART
)
2126 reg
= XEXP (reg
, 0);
2128 if (GET_CODE (reg
) == PARALLEL
2129 && GET_MODE (reg
) == BLKmode
)
2132 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2133 if (check_live_1 (src
, XVECEXP (reg
, 0, i
)))
2138 if (GET_CODE (reg
) != REG
)
2141 regno
= REGNO (reg
);
2143 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
2145 /* Global registers are assumed live */
2150 if (regno
< FIRST_PSEUDO_REGISTER
)
2152 /* check for hard registers */
2153 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2156 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2158 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2160 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
,
2170 /* check for psuedo registers */
2171 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2173 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2175 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
, regno
))
2187 /* If x is a set of a register R, mark that R is alive in the beginning
2188 of every update-block of src. */
2191 update_live_1 (src
, x
)
2197 register rtx reg
= SET_DEST (x
);
2202 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2203 || GET_CODE (reg
) == SIGN_EXTRACT
2204 || GET_CODE (reg
) == STRICT_LOW_PART
)
2205 reg
= XEXP (reg
, 0);
2207 if (GET_CODE (reg
) == PARALLEL
2208 && GET_MODE (reg
) == BLKmode
)
2211 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2212 update_live_1 (src
, XVECEXP (reg
, 0, i
));
2216 if (GET_CODE (reg
) != REG
)
2219 /* Global registers are always live, so the code below does not apply
2222 regno
= REGNO (reg
);
2224 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
2226 if (regno
< FIRST_PSEUDO_REGISTER
)
2228 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2231 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2233 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2235 SET_REGNO_REG_SET (BASIC_BLOCK (b
)->global_live_at_start
,
2242 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2244 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2246 SET_REGNO_REG_SET (BASIC_BLOCK (b
)->global_live_at_start
, regno
);
2253 /* Return 1 if insn can be speculatively moved from block src to trg,
2254 otherwise return 0. Called before first insertion of insn to
2255 ready-list or before the scheduling. */
2258 check_live (insn
, src
)
2262 /* find the registers set by instruction */
2263 if (GET_CODE (PATTERN (insn
)) == SET
2264 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2265 return check_live_1 (src
, PATTERN (insn
));
2266 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2269 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2270 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2271 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2272 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
2282 /* Update the live registers info after insn was moved speculatively from
2283 block src to trg. */
2286 update_live (insn
, src
)
2290 /* find the registers set by instruction */
2291 if (GET_CODE (PATTERN (insn
)) == SET
2292 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2293 update_live_1 (src
, PATTERN (insn
));
2294 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2297 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2298 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2299 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2300 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
2304 /* Exception Free Loads:
2306 We define five classes of speculative loads: IFREE, IRISKY,
2307 PFREE, PRISKY, and MFREE.
2309 IFREE loads are loads that are proved to be exception-free, just
2310 by examining the load insn. Examples for such loads are loads
2311 from TOC and loads of global data.
2313 IRISKY loads are loads that are proved to be exception-risky,
2314 just by examining the load insn. Examples for such loads are
2315 volatile loads and loads from shared memory.
2317 PFREE loads are loads for which we can prove, by examining other
2318 insns, that they are exception-free. Currently, this class consists
2319 of loads for which we are able to find a "similar load", either in
2320 the target block, or, if only one split-block exists, in that split
2321 block. Load2 is similar to load1 if both have same single base
2322 register. We identify only part of the similar loads, by finding
2323 an insn upon which both load1 and load2 have a DEF-USE dependence.
2325 PRISKY loads are loads for which we can prove, by examining other
2326 insns, that they are exception-risky. Currently we have two proofs for
2327 such loads. The first proof detects loads that are probably guarded by a
2328 test on the memory address. This proof is based on the
2329 backward and forward data dependence information for the region.
2330 Let load-insn be the examined load.
2331 Load-insn is PRISKY iff ALL the following hold:
2333 - insn1 is not in the same block as load-insn
2334 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2335 - test-insn is either a compare or a branch, not in the same block as load-insn
2336 - load-insn is reachable from test-insn
2337 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2339 This proof might fail when the compare and the load are fed
2340 by an insn not in the region. To solve this, we will add to this
2341 group all loads that have no input DEF-USE dependence.
2343 The second proof detects loads that are directly or indirectly
2344 fed by a speculative load. This proof is affected by the
2345 scheduling process. We will use the flag fed_by_spec_load.
2346 Initially, all insns have this flag reset. After a speculative
2347 motion of an insn, if insn is either a load, or marked as
2348 fed_by_spec_load, we will also mark as fed_by_spec_load every
2349 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2350 load which is fed_by_spec_load is also PRISKY.
2352 MFREE (maybe-free) loads are all the remaining loads. They may be
2353 exception-free, but we cannot prove it.
2355 Now, all loads in IFREE and PFREE classes are considered
2356 exception-free, while all loads in IRISKY and PRISKY classes are
2357 considered exception-risky. As for loads in the MFREE class,
2358 these are considered either exception-free or exception-risky,
2359 depending on whether we are pessimistic or optimistic. We have
2360 to take the pessimistic approach to assure the safety of
2361 speculative scheduling, but we can take the optimistic approach
2362 by invoking the -fsched_spec_load_dangerous option. */
2364 enum INSN_TRAP_CLASS
2366 TRAP_FREE
= 0, IFREE
= 1, PFREE_CANDIDATE
= 2,
2367 PRISKY_CANDIDATE
= 3, IRISKY
= 4, TRAP_RISKY
= 5
2370 #define WORST_CLASS(class1, class2) \
2371 ((class1 > class2) ? class1 : class2)
2373 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between */
2374 /* some speculatively moved load insn and this one. */
2375 char *fed_by_spec_load
;
2378 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2379 #define IS_REACHABLE(bb_from, bb_to) \
2381 || IS_RGN_ENTRY (bb_from) \
2382 || (bitset_member (ancestor_edges[bb_to], \
2383 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2385 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2386 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2388 /* Non-zero iff the address is comprised from at most 1 register */
2389 #define CONST_BASED_ADDRESS_P(x) \
2390 (GET_CODE (x) == REG \
2391 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2392 || (GET_CODE (x) == LO_SUM)) \
2393 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2394 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2396 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2399 set_spec_fed (load_insn
)
2404 for (link
= INSN_DEPEND (load_insn
); link
; link
= XEXP (link
, 1))
2405 if (GET_MODE (link
) == VOIDmode
)
2406 FED_BY_SPEC_LOAD (XEXP (link
, 0)) = 1;
2407 } /* set_spec_fed */
2409 /* On the path from the insn to load_insn_bb, find a conditional branch */
2410 /* depending on insn, that guards the speculative load. */
2413 find_conditional_protection (insn
, load_insn_bb
)
2419 /* iterate through DEF-USE forward dependences */
2420 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
2422 rtx next
= XEXP (link
, 0);
2423 if ((CONTAINING_RGN (INSN_BLOCK (next
)) ==
2424 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
2425 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
2426 && load_insn_bb
!= INSN_BB (next
)
2427 && GET_MODE (link
) == VOIDmode
2428 && (GET_CODE (next
) == JUMP_INSN
2429 || find_conditional_protection (next
, load_insn_bb
)))
2433 } /* find_conditional_protection */
2435 /* Returns 1 if the same insn1 that participates in the computation
2436 of load_insn's address is feeding a conditional branch that is
2437 guarding on load_insn. This is true if we find a the two DEF-USE
2439 insn1 -> ... -> conditional-branch
2440 insn1 -> ... -> load_insn,
2441 and if a flow path exist:
2442 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2443 and if insn1 is on the path
2444 region-entry -> ... -> bb_trg -> ... load_insn.
2446 Locate insn1 by climbing on LOG_LINKS from load_insn.
2447 Locate the branch by following INSN_DEPEND from insn1. */
2450 is_conditionally_protected (load_insn
, bb_src
, bb_trg
)
2456 for (link
= LOG_LINKS (load_insn
); link
; link
= XEXP (link
, 1))
2458 rtx insn1
= XEXP (link
, 0);
2460 /* must be a DEF-USE dependence upon non-branch */
2461 if (GET_MODE (link
) != VOIDmode
2462 || GET_CODE (insn1
) == JUMP_INSN
)
2465 /* must exist a path: region-entry -> ... -> bb_trg -> ... load_insn */
2466 if (INSN_BB (insn1
) == bb_src
2467 || (CONTAINING_RGN (INSN_BLOCK (insn1
))
2468 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
2469 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
2470 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
2473 /* now search for the conditional-branch */
2474 if (find_conditional_protection (insn1
, bb_src
))
2477 /* recursive step: search another insn1, "above" current insn1. */
2478 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
2481 /* the chain does not exsist */
2483 } /* is_conditionally_protected */
2485 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2486 load_insn can move speculatively from bb_src to bb_trg. All the
2487 following must hold:
2489 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2490 (2) load_insn and load1 have a def-use dependence upon
2491 the same insn 'insn1'.
2492 (3) either load2 is in bb_trg, or:
2493 - there's only one split-block, and
2494 - load1 is on the escape path, and
2496 From all these we can conclude that the two loads access memory
2497 addresses that differ at most by a constant, and hence if moving
2498 load_insn would cause an exception, it would have been caused by
2502 is_pfree (load_insn
, bb_src
, bb_trg
)
2507 register candidate
*candp
= candidate_table
+ bb_src
;
2509 if (candp
->split_bbs
.nr_members
!= 1)
2510 /* must have exactly one escape block */
2513 for (back_link
= LOG_LINKS (load_insn
);
2514 back_link
; back_link
= XEXP (back_link
, 1))
2516 rtx insn1
= XEXP (back_link
, 0);
2518 if (GET_MODE (back_link
) == VOIDmode
)
2520 /* found a DEF-USE dependence (insn1, load_insn) */
2523 for (fore_link
= INSN_DEPEND (insn1
);
2524 fore_link
; fore_link
= XEXP (fore_link
, 1))
2526 rtx insn2
= XEXP (fore_link
, 0);
2527 if (GET_MODE (fore_link
) == VOIDmode
)
2529 /* found a DEF-USE dependence (insn1, insn2) */
2530 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
2531 /* insn2 not guaranteed to be a 1 base reg load */
2534 if (INSN_BB (insn2
) == bb_trg
)
2535 /* insn2 is the similar load, in the target block */
2538 if (*(candp
->split_bbs
.first_member
) == INSN_BLOCK (insn2
))
2539 /* insn2 is a similar load, in a split-block */
2546 /* couldn't find a similar load */
2550 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2551 as found by analyzing insn's expression. */
2554 may_trap_exp (x
, is_store
)
2562 code
= GET_CODE (x
);
2572 /* The insn uses memory */
2573 /* a volatile load */
2574 if (MEM_VOLATILE_P (x
))
2576 /* an exception-free load */
2577 if (!may_trap_p (x
))
2579 /* a load with 1 base register, to be further checked */
2580 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
2581 return PFREE_CANDIDATE
;
2582 /* no info on the load, to be further checked */
2583 return PRISKY_CANDIDATE
;
2588 int i
, insn_class
= TRAP_FREE
;
2590 /* neither store nor load, check if it may cause a trap */
2593 /* recursive step: walk the insn... */
2594 fmt
= GET_RTX_FORMAT (code
);
2595 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2599 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
2600 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2602 else if (fmt
[i
] == 'E')
2605 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2607 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
2608 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2609 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2613 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2618 } /* may_trap_exp */
2621 /* Classifies insn for the purpose of verifying that it can be
2622 moved speculatively, by examining it's patterns, returning:
2623 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2624 TRAP_FREE: non-load insn.
2625 IFREE: load from a globaly safe location.
2626 IRISKY: volatile load.
2627 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2628 being either PFREE or PRISKY. */
2631 haifa_classify_insn (insn
)
2634 rtx pat
= PATTERN (insn
);
2635 int tmp_class
= TRAP_FREE
;
2636 int insn_class
= TRAP_FREE
;
2639 if (GET_CODE (pat
) == PARALLEL
)
2641 int i
, len
= XVECLEN (pat
, 0);
2643 for (i
= len
- 1; i
>= 0; i
--)
2645 code
= GET_CODE (XVECEXP (pat
, 0, i
));
2649 /* test if it is a 'store' */
2650 tmp_class
= may_trap_exp (XEXP (XVECEXP (pat
, 0, i
), 0), 1);
2653 /* test if it is a store */
2654 tmp_class
= may_trap_exp (SET_DEST (XVECEXP (pat
, 0, i
)), 1);
2655 if (tmp_class
== TRAP_RISKY
)
2657 /* test if it is a load */
2659 WORST_CLASS (tmp_class
,
2660 may_trap_exp (SET_SRC (XVECEXP (pat
, 0, i
)), 0));
2663 tmp_class
= TRAP_RISKY
;
2667 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2668 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2674 code
= GET_CODE (pat
);
2678 /* test if it is a 'store' */
2679 tmp_class
= may_trap_exp (XEXP (pat
, 0), 1);
2682 /* test if it is a store */
2683 tmp_class
= may_trap_exp (SET_DEST (pat
), 1);
2684 if (tmp_class
== TRAP_RISKY
)
2686 /* test if it is a load */
2688 WORST_CLASS (tmp_class
,
2689 may_trap_exp (SET_SRC (pat
), 0));
2692 tmp_class
= TRAP_RISKY
;
2696 insn_class
= tmp_class
;
2701 } /* haifa_classify_insn */
2703 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2704 a load moved speculatively, or if load_insn is protected by
2705 a compare on load_insn's address). */
2708 is_prisky (load_insn
, bb_src
, bb_trg
)
2712 if (FED_BY_SPEC_LOAD (load_insn
))
2715 if (LOG_LINKS (load_insn
) == NULL
)
2716 /* dependence may 'hide' out of the region. */
2719 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2725 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2726 Return 1 if insn is exception-free (and the motion is valid)
2730 is_exception_free (insn
, bb_src
, bb_trg
)
2734 int insn_class
= haifa_classify_insn (insn
);
2736 /* handle non-load insns */
2747 if (!flag_schedule_speculative_load
)
2749 IS_LOAD_INSN (insn
) = 1;
2756 case PFREE_CANDIDATE
:
2757 if (is_pfree (insn
, bb_src
, bb_trg
))
2759 /* don't 'break' here: PFREE-candidate is also PRISKY-candidate */
2760 case PRISKY_CANDIDATE
:
2761 if (!flag_schedule_speculative_load_dangerous
2762 || is_prisky (insn
, bb_src
, bb_trg
))
2768 return flag_schedule_speculative_load_dangerous
;
2769 } /* is_exception_free */
2772 /* Process an insn's memory dependencies. There are four kinds of
2775 (0) read dependence: read follows read
2776 (1) true dependence: read follows write
2777 (2) anti dependence: write follows read
2778 (3) output dependence: write follows write
2780 We are careful to build only dependencies which actually exist, and
2781 use transitivity to avoid building too many links. */
2783 /* Return the INSN_LIST containing INSN in LIST, or NULL
2784 if LIST does not contain INSN. */
2786 HAIFA_INLINE
static rtx
2787 find_insn_list (insn
, list
)
2793 if (XEXP (list
, 0) == insn
)
2795 list
= XEXP (list
, 1);
2801 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 otherwise. */
2803 HAIFA_INLINE
static char
2804 find_insn_mem_list (insn
, x
, list
, list1
)
2810 if (XEXP (list
, 0) == insn
2811 && XEXP (list1
, 0) == x
)
2813 list
= XEXP (list
, 1);
2814 list1
= XEXP (list1
, 1);
2820 /* Compute the function units used by INSN. This caches the value
2821 returned by function_units_used. A function unit is encoded as the
2822 unit number if the value is non-negative and the compliment of a
2823 mask if the value is negative. A function unit index is the
2824 non-negative encoding. */
2826 HAIFA_INLINE
static int
2830 register int unit
= INSN_UNIT (insn
);
2834 recog_memoized (insn
);
2836 /* A USE insn, or something else we don't need to understand.
2837 We can't pass these directly to function_units_used because it will
2838 trigger a fatal error for unrecognizable insns. */
2839 if (INSN_CODE (insn
) < 0)
2843 unit
= function_units_used (insn
);
2844 /* Increment non-negative values so we can cache zero. */
2848 /* We only cache 16 bits of the result, so if the value is out of
2849 range, don't cache it. */
2850 if (FUNCTION_UNITS_SIZE
< HOST_BITS_PER_SHORT
2852 || (~unit
& ((1 << (HOST_BITS_PER_SHORT
- 1)) - 1)) == 0)
2853 INSN_UNIT (insn
) = unit
;
2855 return (unit
> 0 ? unit
- 1 : unit
);
2858 /* Compute the blockage range for executing INSN on UNIT. This caches
2859 the value returned by the blockage_range_function for the unit.
2860 These values are encoded in an int where the upper half gives the
2861 minimum value and the lower half gives the maximum value. */
2863 HAIFA_INLINE
static unsigned int
2864 blockage_range (unit
, insn
)
2868 unsigned int blockage
= INSN_BLOCKAGE (insn
);
2871 if ((int) UNIT_BLOCKED (blockage
) != unit
+ 1)
2873 range
= function_units
[unit
].blockage_range_function (insn
);
2874 /* We only cache the blockage range for one unit and then only if
2876 if (HOST_BITS_PER_INT
>= UNIT_BITS
+ 2 * BLOCKAGE_BITS
)
2877 INSN_BLOCKAGE (insn
) = ENCODE_BLOCKAGE (unit
+ 1, range
);
2880 range
= BLOCKAGE_RANGE (blockage
);
2885 /* A vector indexed by function unit instance giving the last insn to use
2886 the unit. The value of the function unit instance index for unit U
2887 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2888 static rtx unit_last_insn
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2890 /* A vector indexed by function unit instance giving the minimum time when
2891 the unit will unblock based on the maximum blockage cost. */
2892 static int unit_tick
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2894 /* A vector indexed by function unit number giving the number of insns
2895 that remain to use the unit. */
2896 static int unit_n_insns
[FUNCTION_UNITS_SIZE
];
2898 /* Reset the function unit state to the null state. */
2903 bzero ((char *) unit_last_insn
, sizeof (unit_last_insn
));
2904 bzero ((char *) unit_tick
, sizeof (unit_tick
));
2905 bzero ((char *) unit_n_insns
, sizeof (unit_n_insns
));
2908 /* Return the issue-delay of an insn */
2910 HAIFA_INLINE
static int
2911 insn_issue_delay (insn
)
2915 int unit
= insn_unit (insn
);
2917 /* efficiency note: in fact, we are working 'hard' to compute a
2918 value that was available in md file, and is not available in
2919 function_units[] structure. It would be nice to have this
2920 value there, too. */
2923 if (function_units
[unit
].blockage_range_function
&&
2924 function_units
[unit
].blockage_function
)
2925 delay
= function_units
[unit
].blockage_function (insn
, insn
);
2928 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2929 if ((unit
& 1) != 0 && function_units
[i
].blockage_range_function
2930 && function_units
[i
].blockage_function
)
2931 delay
= MAX (delay
, function_units
[i
].blockage_function (insn
, insn
));
2936 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2937 instance INSTANCE at time CLOCK if the previous actual hazard cost
2940 HAIFA_INLINE
static int
2941 actual_hazard_this_instance (unit
, instance
, insn
, clock
, cost
)
2942 int unit
, instance
, clock
, cost
;
2945 int tick
= unit_tick
[instance
]; /* issue time of the last issued insn */
2947 if (tick
- clock
> cost
)
2949 /* The scheduler is operating forward, so unit's last insn is the
2950 executing insn and INSN is the candidate insn. We want a
2951 more exact measure of the blockage if we execute INSN at CLOCK
2952 given when we committed the execution of the unit's last insn.
2954 The blockage value is given by either the unit's max blockage
2955 constant, blockage range function, or blockage function. Use
2956 the most exact form for the given unit. */
2958 if (function_units
[unit
].blockage_range_function
)
2960 if (function_units
[unit
].blockage_function
)
2961 tick
+= (function_units
[unit
].blockage_function
2962 (unit_last_insn
[instance
], insn
)
2963 - function_units
[unit
].max_blockage
);
2965 tick
+= ((int) MAX_BLOCKAGE_COST (blockage_range (unit
, insn
))
2966 - function_units
[unit
].max_blockage
);
2968 if (tick
- clock
> cost
)
2969 cost
= tick
- clock
;
2974 /* Record INSN as having begun execution on the units encoded by UNIT at
2977 HAIFA_INLINE
static void
2978 schedule_unit (unit
, insn
, clock
)
2986 int instance
= unit
;
2987 #if MAX_MULTIPLICITY > 1
2988 /* Find the first free instance of the function unit and use that
2989 one. We assume that one is free. */
2990 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
2992 if (!actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
2994 instance
+= FUNCTION_UNITS_SIZE
;
2997 unit_last_insn
[instance
] = insn
;
2998 unit_tick
[instance
] = (clock
+ function_units
[unit
].max_blockage
);
3001 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3002 if ((unit
& 1) != 0)
3003 schedule_unit (i
, insn
, clock
);
3006 /* Return the actual hazard cost of executing INSN on the units encoded by
3007 UNIT at time CLOCK if the previous actual hazard cost was COST. */
3009 HAIFA_INLINE
static int
3010 actual_hazard (unit
, insn
, clock
, cost
)
3011 int unit
, clock
, cost
;
3018 /* Find the instance of the function unit with the minimum hazard. */
3019 int instance
= unit
;
3020 int best_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
3024 #if MAX_MULTIPLICITY > 1
3025 if (best_cost
> cost
)
3027 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
3029 instance
+= FUNCTION_UNITS_SIZE
;
3030 this_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
3032 if (this_cost
< best_cost
)
3034 best_cost
= this_cost
;
3035 if (this_cost
<= cost
)
3041 cost
= MAX (cost
, best_cost
);
3044 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3045 if ((unit
& 1) != 0)
3046 cost
= actual_hazard (i
, insn
, clock
, cost
);
3051 /* Return the potential hazard cost of executing an instruction on the
3052 units encoded by UNIT if the previous potential hazard cost was COST.
3053 An insn with a large blockage time is chosen in preference to one
3054 with a smaller time; an insn that uses a unit that is more likely
3055 to be used is chosen in preference to one with a unit that is less
3056 used. We are trying to minimize a subsequent actual hazard. */
3058 HAIFA_INLINE
static int
3059 potential_hazard (unit
, insn
, cost
)
3064 unsigned int minb
, maxb
;
3068 minb
= maxb
= function_units
[unit
].max_blockage
;
3071 if (function_units
[unit
].blockage_range_function
)
3073 maxb
= minb
= blockage_range (unit
, insn
);
3074 maxb
= MAX_BLOCKAGE_COST (maxb
);
3075 minb
= MIN_BLOCKAGE_COST (minb
);
3080 /* Make the number of instructions left dominate. Make the
3081 minimum delay dominate the maximum delay. If all these
3082 are the same, use the unit number to add an arbitrary
3083 ordering. Other terms can be added. */
3084 ncost
= minb
* 0x40 + maxb
;
3085 ncost
*= (unit_n_insns
[unit
] - 1) * 0x1000 + unit
;
3092 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3093 if ((unit
& 1) != 0)
3094 cost
= potential_hazard (i
, insn
, cost
);
3099 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3100 This is the number of cycles between instruction issue and
3101 instruction results. */
3103 HAIFA_INLINE
static int
3104 insn_cost (insn
, link
, used
)
3105 rtx insn
, link
, used
;
3107 register int cost
= INSN_COST (insn
);
3111 recog_memoized (insn
);
3113 /* A USE insn, or something else we don't need to understand.
3114 We can't pass these directly to result_ready_cost because it will
3115 trigger a fatal error for unrecognizable insns. */
3116 if (INSN_CODE (insn
) < 0)
3118 INSN_COST (insn
) = 1;
3123 cost
= result_ready_cost (insn
);
3128 INSN_COST (insn
) = cost
;
3132 /* in this case estimate cost without caring how insn is used. */
3133 if (link
== 0 && used
== 0)
3136 /* A USE insn should never require the value used to be computed. This
3137 allows the computation of a function's result and parameter values to
3138 overlap the return and call. */
3139 recog_memoized (used
);
3140 if (INSN_CODE (used
) < 0)
3141 LINK_COST_FREE (link
) = 1;
3143 /* If some dependencies vary the cost, compute the adjustment. Most
3144 commonly, the adjustment is complete: either the cost is ignored
3145 (in the case of an output- or anti-dependence), or the cost is
3146 unchanged. These values are cached in the link as LINK_COST_FREE
3147 and LINK_COST_ZERO. */
3149 if (LINK_COST_FREE (link
))
3152 else if (!LINK_COST_ZERO (link
))
3156 ADJUST_COST (used
, link
, insn
, ncost
);
3158 LINK_COST_FREE (link
) = ncost
= 1;
3160 LINK_COST_ZERO (link
) = 1;
3167 /* Compute the priority number for INSN. */
3176 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
3179 if ((this_priority
= INSN_PRIORITY (insn
)) == 0)
3181 if (INSN_DEPEND (insn
) == 0)
3182 this_priority
= insn_cost (insn
, 0, 0);
3184 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
3189 if (RTX_INTEGRATED_P (link
))
3192 next
= XEXP (link
, 0);
3194 /* critical path is meaningful in block boundaries only */
3195 if (INSN_BLOCK (next
) != INSN_BLOCK (insn
))
3198 next_priority
= insn_cost (insn
, link
, next
) + priority (next
);
3199 if (next_priority
> this_priority
)
3200 this_priority
= next_priority
;
3202 INSN_PRIORITY (insn
) = this_priority
;
3204 return this_priority
;
3208 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3209 them to the unused_*_list variables, so that they can be reused. */
3212 free_pending_lists ()
3214 if (current_nr_blocks
<= 1)
3216 free_list (&pending_read_insns
, &unused_insn_list
);
3217 free_list (&pending_write_insns
, &unused_insn_list
);
3218 free_list (&pending_read_mems
, &unused_expr_list
);
3219 free_list (&pending_write_mems
, &unused_expr_list
);
3223 /* interblock scheduling */
3226 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3228 free_list (&bb_pending_read_insns
[bb
], &unused_insn_list
);
3229 free_list (&bb_pending_write_insns
[bb
], &unused_insn_list
);
3230 free_list (&bb_pending_read_mems
[bb
], &unused_expr_list
);
3231 free_list (&bb_pending_write_mems
[bb
], &unused_expr_list
);
3236 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3237 The MEM is a memory reference contained within INSN, which we are saving
3238 so that we can do memory aliasing on it. */
3241 add_insn_mem_dependence (insn_list
, mem_list
, insn
, mem
)
3242 rtx
*insn_list
, *mem_list
, insn
, mem
;
3246 link
= alloc_INSN_LIST (insn
, *insn_list
);
3249 link
= alloc_EXPR_LIST (VOIDmode
, mem
, *mem_list
);
3252 pending_lists_length
++;
3256 /* Make a dependency between every memory reference on the pending lists
3257 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3261 flush_pending_lists (insn
, only_write
)
3268 while (pending_read_insns
&& ! only_write
)
3270 add_dependence (insn
, XEXP (pending_read_insns
, 0), REG_DEP_ANTI
);
3272 link
= pending_read_insns
;
3273 pending_read_insns
= XEXP (pending_read_insns
, 1);
3274 XEXP (link
, 1) = unused_insn_list
;
3275 unused_insn_list
= link
;
3277 link
= pending_read_mems
;
3278 pending_read_mems
= XEXP (pending_read_mems
, 1);
3279 XEXP (link
, 1) = unused_expr_list
;
3280 unused_expr_list
= link
;
3282 while (pending_write_insns
)
3284 add_dependence (insn
, XEXP (pending_write_insns
, 0), REG_DEP_ANTI
);
3286 link
= pending_write_insns
;
3287 pending_write_insns
= XEXP (pending_write_insns
, 1);
3288 XEXP (link
, 1) = unused_insn_list
;
3289 unused_insn_list
= link
;
3291 link
= pending_write_mems
;
3292 pending_write_mems
= XEXP (pending_write_mems
, 1);
3293 XEXP (link
, 1) = unused_expr_list
;
3294 unused_expr_list
= link
;
3296 pending_lists_length
= 0;
3298 /* last_pending_memory_flush is now a list of insns */
3299 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3300 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3302 free_list (&last_pending_memory_flush
, &unused_insn_list
);
3303 last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
3306 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
3307 by the write to the destination of X, and reads of everything mentioned. */
3310 sched_analyze_1 (x
, insn
)
3315 register rtx dest
= SET_DEST (x
);
3316 enum rtx_code code
= GET_CODE (x
);
3321 if (GET_CODE (dest
) == PARALLEL
3322 && GET_MODE (dest
) == BLKmode
)
3325 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
3326 sched_analyze_1 (XVECEXP (dest
, 0, i
), insn
);
3327 if (GET_CODE (x
) == SET
)
3328 sched_analyze_2 (SET_SRC (x
), insn
);
3332 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
3333 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3335 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3337 /* The second and third arguments are values read by this insn. */
3338 sched_analyze_2 (XEXP (dest
, 1), insn
);
3339 sched_analyze_2 (XEXP (dest
, 2), insn
);
3341 dest
= SUBREG_REG (dest
);
3344 if (GET_CODE (dest
) == REG
)
3348 regno
= REGNO (dest
);
3350 /* A hard reg in a wide mode may really be multiple registers.
3351 If so, mark all of them just like the first. */
3352 if (regno
< FIRST_PSEUDO_REGISTER
)
3354 i
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
3359 for (u
= reg_last_uses
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3360 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3362 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3363 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3365 /* Clobbers need not be ordered with respect to one another,
3366 but sets must be ordered with respect to a pending clobber. */
3369 reg_last_uses
[regno
+ i
] = 0;
3370 for (u
= reg_last_clobbers
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3371 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3372 SET_REGNO_REG_SET (reg_pending_sets
, regno
+ i
);
3375 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
+ i
);
3377 /* Function calls clobber all call_used regs. */
3378 if (global_regs
[regno
+ i
]
3379 || (code
== SET
&& call_used_regs
[regno
+ i
]))
3380 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3381 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3388 for (u
= reg_last_uses
[regno
]; u
; u
= XEXP (u
, 1))
3389 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3391 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3392 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3396 reg_last_uses
[regno
] = 0;
3397 for (u
= reg_last_clobbers
[regno
]; u
; u
= XEXP (u
, 1))
3398 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3399 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
3402 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
3404 /* Pseudos that are REG_EQUIV to something may be replaced
3405 by that during reloading. We need only add dependencies for
3406 the address in the REG_EQUIV note. */
3407 if (!reload_completed
3408 && reg_known_equiv_p
[regno
]
3409 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3410 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3412 /* Don't let it cross a call after scheduling if it doesn't
3413 already cross one. */
3415 if (REG_N_CALLS_CROSSED (regno
) == 0)
3416 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3417 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3420 else if (GET_CODE (dest
) == MEM
)
3422 /* Writing memory. */
3424 if (pending_lists_length
> 32)
3426 /* Flush all pending reads and writes to prevent the pending lists
3427 from getting any larger. Insn scheduling runs too slowly when
3428 these lists get long. The number 32 was chosen because it
3429 seems like a reasonable number. When compiling GCC with itself,
3430 this flush occurs 8 times for sparc, and 10 times for m88k using
3432 flush_pending_lists (insn
, 0);
3437 rtx pending
, pending_mem
;
3439 pending
= pending_read_insns
;
3440 pending_mem
= pending_read_mems
;
3443 /* If a dependency already exists, don't create a new one. */
3444 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3445 if (anti_dependence (XEXP (pending_mem
, 0), dest
))
3446 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3448 pending
= XEXP (pending
, 1);
3449 pending_mem
= XEXP (pending_mem
, 1);
3452 pending
= pending_write_insns
;
3453 pending_mem
= pending_write_mems
;
3456 /* If a dependency already exists, don't create a new one. */
3457 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3458 if (output_dependence (XEXP (pending_mem
, 0), dest
))
3459 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
3461 pending
= XEXP (pending
, 1);
3462 pending_mem
= XEXP (pending_mem
, 1);
3465 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3466 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3468 add_insn_mem_dependence (&pending_write_insns
, &pending_write_mems
,
3471 sched_analyze_2 (XEXP (dest
, 0), insn
);
3474 /* Analyze reads. */
3475 if (GET_CODE (x
) == SET
)
3476 sched_analyze_2 (SET_SRC (x
), insn
);
3479 /* Analyze the uses of memory and registers in rtx X in INSN. */
3482 sched_analyze_2 (x
, insn
)
3488 register enum rtx_code code
;
3494 code
= GET_CODE (x
);
3503 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3504 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3505 this does not mean that this insn is using cc0. */
3513 /* User of CC0 depends on immediately preceding insn. */
3514 SCHED_GROUP_P (insn
) = 1;
3516 /* There may be a note before this insn now, but all notes will
3517 be removed before we actually try to schedule the insns, so
3518 it won't cause a problem later. We must avoid it here though. */
3519 prev
= prev_nonnote_insn (insn
);
3521 /* Make a copy of all dependencies on the immediately previous insn,
3522 and add to this insn. This is so that all the dependencies will
3523 apply to the group. Remove an explicit dependence on this insn
3524 as SCHED_GROUP_P now represents it. */
3526 if (find_insn_list (prev
, LOG_LINKS (insn
)))
3527 remove_dependence (insn
, prev
);
3529 for (link
= LOG_LINKS (prev
); link
; link
= XEXP (link
, 1))
3530 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3539 int regno
= REGNO (x
);
3540 if (regno
< FIRST_PSEUDO_REGISTER
)
3544 i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
3547 reg_last_uses
[regno
+ i
]
3548 = alloc_INSN_LIST (insn
, reg_last_uses
[regno
+ i
]);
3550 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3551 add_dependence (insn
, XEXP (u
, 0), 0);
3553 /* ??? This should never happen. */
3554 for (u
= reg_last_clobbers
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3555 add_dependence (insn
, XEXP (u
, 0), 0);
3557 if ((call_used_regs
[regno
+ i
] || global_regs
[regno
+ i
]))
3558 /* Function calls clobber all call_used regs. */
3559 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3560 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3565 reg_last_uses
[regno
] = alloc_INSN_LIST (insn
, reg_last_uses
[regno
]);
3567 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3568 add_dependence (insn
, XEXP (u
, 0), 0);
3570 /* ??? This should never happen. */
3571 for (u
= reg_last_clobbers
[regno
]; u
; u
= XEXP (u
, 1))
3572 add_dependence (insn
, XEXP (u
, 0), 0);
3574 /* Pseudos that are REG_EQUIV to something may be replaced
3575 by that during reloading. We need only add dependencies for
3576 the address in the REG_EQUIV note. */
3577 if (!reload_completed
3578 && reg_known_equiv_p
[regno
]
3579 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3580 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3582 /* If the register does not already cross any calls, then add this
3583 insn to the sched_before_next_call list so that it will still
3584 not cross calls after scheduling. */
3585 if (REG_N_CALLS_CROSSED (regno
) == 0)
3586 add_dependence (sched_before_next_call
, insn
, REG_DEP_ANTI
);
3593 /* Reading memory. */
3595 rtx pending
, pending_mem
;
3597 pending
= pending_read_insns
;
3598 pending_mem
= pending_read_mems
;
3601 /* If a dependency already exists, don't create a new one. */
3602 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3603 if (read_dependence (XEXP (pending_mem
, 0), x
))
3604 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3606 pending
= XEXP (pending
, 1);
3607 pending_mem
= XEXP (pending_mem
, 1);
3610 pending
= pending_write_insns
;
3611 pending_mem
= pending_write_mems
;
3614 /* If a dependency already exists, don't create a new one. */
3615 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3616 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
3618 add_dependence (insn
, XEXP (pending
, 0), 0);
3620 pending
= XEXP (pending
, 1);
3621 pending_mem
= XEXP (pending_mem
, 1);
3624 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3625 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3627 /* Always add these dependencies to pending_reads, since
3628 this insn may be followed by a write. */
3629 add_insn_mem_dependence (&pending_read_insns
, &pending_read_mems
,
3632 /* Take advantage of tail recursion here. */
3633 sched_analyze_2 (XEXP (x
, 0), insn
);
3637 /* Force pending stores to memory in case a trap handler needs them. */
3639 flush_pending_lists (insn
, 1);
3644 case UNSPEC_VOLATILE
:
3648 /* Traditional and volatile asm instructions must be considered to use
3649 and clobber all hard registers, all pseudo-registers and all of
3650 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3652 Consider for instance a volatile asm that changes the fpu rounding
3653 mode. An insn should not be moved across this even if it only uses
3654 pseudo-regs because it might give an incorrectly rounded result. */
3655 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
3657 int max_reg
= max_reg_num ();
3658 for (i
= 0; i
< max_reg
; i
++)
3660 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3661 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3662 reg_last_uses
[i
] = 0;
3664 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3665 add_dependence (insn
, XEXP (u
, 0), 0);
3667 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3668 add_dependence (insn
, XEXP (u
, 0), 0);
3670 reg_pending_sets_all
= 1;
3672 flush_pending_lists (insn
, 0);
3675 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3676 We can not just fall through here since then we would be confused
3677 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3678 traditional asms unlike their normal usage. */
3680 if (code
== ASM_OPERANDS
)
3682 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
3683 sched_analyze_2 (ASM_OPERANDS_INPUT (x
, j
), insn
);
3693 /* These both read and modify the result. We must handle them as writes
3694 to get proper dependencies for following instructions. We must handle
3695 them as reads to get proper dependencies from this to previous
3696 instructions. Thus we need to pass them to both sched_analyze_1
3697 and sched_analyze_2. We must call sched_analyze_2 first in order
3698 to get the proper antecedent for the read. */
3699 sched_analyze_2 (XEXP (x
, 0), insn
);
3700 sched_analyze_1 (x
, insn
);
3707 /* Other cases: walk the insn. */
3708 fmt
= GET_RTX_FORMAT (code
);
3709 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3712 sched_analyze_2 (XEXP (x
, i
), insn
);
3713 else if (fmt
[i
] == 'E')
3714 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3715 sched_analyze_2 (XVECEXP (x
, i
, j
), insn
);
3719 /* Analyze an INSN with pattern X to find all dependencies. */
3722 sched_analyze_insn (x
, insn
, loop_notes
)
3726 register RTX_CODE code
= GET_CODE (x
);
3728 int maxreg
= max_reg_num ();
3731 if (code
== SET
|| code
== CLOBBER
)
3732 sched_analyze_1 (x
, insn
);
3733 else if (code
== PARALLEL
)
3736 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
3738 code
= GET_CODE (XVECEXP (x
, 0, i
));
3739 if (code
== SET
|| code
== CLOBBER
)
3740 sched_analyze_1 (XVECEXP (x
, 0, i
), insn
);
3742 sched_analyze_2 (XVECEXP (x
, 0, i
), insn
);
3746 sched_analyze_2 (x
, insn
);
3748 /* Mark registers CLOBBERED or used by called function. */
3749 if (GET_CODE (insn
) == CALL_INSN
)
3750 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
3752 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
3753 sched_analyze_1 (XEXP (link
, 0), insn
);
3755 sched_analyze_2 (XEXP (link
, 0), insn
);
3758 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3759 block, then we must be sure that no instructions are scheduled across it.
3760 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3761 become incorrect. */
3765 int max_reg
= max_reg_num ();
3766 int schedule_barrier_found
= 0;
3769 /* Update loop_notes with any notes from this insn. Also determine
3770 if any of the notes on the list correspond to instruction scheduling
3771 barriers (loop, eh & setjmp notes, but not range notes. */
3773 while (XEXP (link
, 1))
3775 if (INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_BEG
3776 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_END
3777 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_BEG
3778 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_END
3779 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_SETJMP
)
3780 schedule_barrier_found
= 1;
3782 link
= XEXP (link
, 1);
3784 XEXP (link
, 1) = REG_NOTES (insn
);
3785 REG_NOTES (insn
) = loop_notes
;
3787 /* Add dependencies if a scheduling barrier was found. */
3788 if (schedule_barrier_found
)
3790 for (i
= 0; i
< max_reg
; i
++)
3793 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3794 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3795 reg_last_uses
[i
] = 0;
3797 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3798 add_dependence (insn
, XEXP (u
, 0), 0);
3800 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3801 add_dependence (insn
, XEXP (u
, 0), 0);
3803 reg_pending_sets_all
= 1;
3805 flush_pending_lists (insn
, 0);
3810 /* Accumulate clobbers until the next set so that it will be output dependant
3811 on all of them. At the next set we can clear the clobber list, since
3812 subsequent sets will be output dependant on it. */
3813 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
3815 free_list (®_last_sets
[i
], &unused_insn_list
);
3816 free_list (®_last_clobbers
[i
],
3819 = alloc_INSN_LIST (insn
, NULL_RTX
);
3821 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
,
3823 reg_last_clobbers
[i
]
3824 = alloc_INSN_LIST (insn
, reg_last_clobbers
[i
]);
3826 CLEAR_REG_SET (reg_pending_sets
);
3827 CLEAR_REG_SET (reg_pending_clobbers
);
3829 if (reg_pending_sets_all
)
3831 for (i
= 0; i
< maxreg
; i
++)
3833 free_list (®_last_sets
[i
], &unused_insn_list
);
3834 reg_last_sets
[i
] = alloc_INSN_LIST (insn
, NULL_RTX
);
3837 reg_pending_sets_all
= 0;
3840 /* Handle function calls and function returns created by the epilogue
3842 if (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3847 /* When scheduling instructions, we make sure calls don't lose their
3848 accompanying USE insns by depending them one on another in order.
3850 Also, we must do the same thing for returns created by the epilogue
3851 threading code. Note this code works only in this special case,
3852 because other passes make no guarantee that they will never emit
3853 an instruction between a USE and a RETURN. There is such a guarantee
3854 for USE instructions immediately before a call. */
3856 prev_dep_insn
= insn
;
3857 dep_insn
= PREV_INSN (insn
);
3858 while (GET_CODE (dep_insn
) == INSN
3859 && GET_CODE (PATTERN (dep_insn
)) == USE
3860 && GET_CODE (XEXP (PATTERN (dep_insn
), 0)) == REG
)
3862 SCHED_GROUP_P (prev_dep_insn
) = 1;
3864 /* Make a copy of all dependencies on dep_insn, and add to insn.
3865 This is so that all of the dependencies will apply to the
3868 for (link
= LOG_LINKS (dep_insn
); link
; link
= XEXP (link
, 1))
3869 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3871 prev_dep_insn
= dep_insn
;
3872 dep_insn
= PREV_INSN (dep_insn
);
3877 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3878 for every dependency. */
3881 sched_analyze (head
, tail
)
3888 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3890 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3892 /* Make each JUMP_INSN a scheduling barrier for memory references. */
3893 if (GET_CODE (insn
) == JUMP_INSN
)
3894 last_pending_memory_flush
3895 = alloc_INSN_LIST (insn
, last_pending_memory_flush
);
3896 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3899 else if (GET_CODE (insn
) == CALL_INSN
)
3904 CANT_MOVE (insn
) = 1;
3906 /* Any instruction using a hard register which may get clobbered
3907 by a call needs to be marked as dependent on this call.
3908 This prevents a use of a hard return reg from being moved
3909 past a void call (i.e. it does not explicitly set the hard
3912 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3913 all registers, not just hard registers, may be clobbered by this
3916 /* Insn, being a CALL_INSN, magically depends on
3917 `last_function_call' already. */
3919 if (NEXT_INSN (insn
) && GET_CODE (NEXT_INSN (insn
)) == NOTE
3920 && NOTE_LINE_NUMBER (NEXT_INSN (insn
)) == NOTE_INSN_SETJMP
)
3922 int max_reg
= max_reg_num ();
3923 for (i
= 0; i
< max_reg
; i
++)
3925 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3926 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3928 reg_last_uses
[i
] = 0;
3930 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3931 add_dependence (insn
, XEXP (u
, 0), 0);
3933 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3934 add_dependence (insn
, XEXP (u
, 0), 0);
3936 reg_pending_sets_all
= 1;
3938 /* Add a pair of fake REG_NOTE which we will later
3939 convert back into a NOTE_INSN_SETJMP note. See
3940 reemit_notes for why we use a pair of NOTEs. */
3941 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_DEAD
,
3944 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_DEAD
,
3945 GEN_INT (NOTE_INSN_SETJMP
),
3950 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3951 if (call_used_regs
[i
] || global_regs
[i
])
3953 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3954 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3955 reg_last_uses
[i
] = 0;
3957 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3958 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3961 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3962 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3964 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3968 /* For each insn which shouldn't cross a call, add a dependence
3969 between that insn and this call insn. */
3970 x
= LOG_LINKS (sched_before_next_call
);
3973 add_dependence (insn
, XEXP (x
, 0), REG_DEP_ANTI
);
3976 LOG_LINKS (sched_before_next_call
) = 0;
3978 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3981 /* In the absence of interprocedural alias analysis, we must flush
3982 all pending reads and writes, and start new dependencies starting
3983 from here. But only flush writes for constant calls (which may
3984 be passed a pointer to something we haven't written yet). */
3985 flush_pending_lists (insn
, CONST_CALL_P (insn
));
3987 /* Depend this function call (actually, the user of this
3988 function call) on all hard register clobberage. */
3990 /* last_function_call is now a list of insns */
3991 free_list(&last_function_call
, &unused_insn_list
);
3992 last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3995 /* See comments on reemit_notes as to why we do this. */
3996 /* ??? Actually, the reemit_notes just say what is done, not why. */
3998 else if (GET_CODE (insn
) == NOTE
3999 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_START
4000 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_END
))
4002 loop_notes
= alloc_EXPR_LIST (REG_DEAD
, NOTE_RANGE_INFO (insn
),
4004 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
4005 GEN_INT (NOTE_LINE_NUMBER (insn
)),
4008 else if (GET_CODE (insn
) == NOTE
4009 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
4010 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
4011 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
4012 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
4013 || (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
4014 && GET_CODE (PREV_INSN (insn
)) != CALL_INSN
)))
4016 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
4017 GEN_INT (NOTE_BLOCK_NUMBER (insn
)),
4019 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
4020 GEN_INT (NOTE_LINE_NUMBER (insn
)),
4022 CONST_CALL_P (loop_notes
) = CONST_CALL_P (insn
);
4031 /* Called when we see a set of a register. If death is true, then we are
4032 scanning backwards. Mark that register as unborn. If nobody says
4033 otherwise, that is how things will remain. If death is false, then we
4034 are scanning forwards. Mark that register as being born. */
4037 sched_note_set (x
, death
)
4042 register rtx reg
= SET_DEST (x
);
4048 if (GET_CODE (reg
) == PARALLEL
4049 && GET_MODE (reg
) == BLKmode
)
4052 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
4053 sched_note_set (XVECEXP (reg
, 0, i
), death
);
4057 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == STRICT_LOW_PART
4058 || GET_CODE (reg
) == SIGN_EXTRACT
|| GET_CODE (reg
) == ZERO_EXTRACT
)
4060 /* Must treat modification of just one hardware register of a multi-reg
4061 value or just a byte field of a register exactly the same way that
4062 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
4063 does not kill the entire register. */
4064 if (GET_CODE (reg
) != SUBREG
4065 || REG_SIZE (SUBREG_REG (reg
)) > REG_SIZE (reg
))
4068 reg
= SUBREG_REG (reg
);
4071 if (GET_CODE (reg
) != REG
)
4074 /* Global registers are always live, so the code below does not apply
4077 regno
= REGNO (reg
);
4078 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
4082 /* If we only set part of the register, then this set does not
4087 /* Try killing this register. */
4088 if (regno
< FIRST_PSEUDO_REGISTER
)
4090 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
4093 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4098 /* Recompute REG_BASIC_BLOCK as we update all the other
4099 dataflow information. */
4100 if (sched_reg_basic_block
[regno
] == REG_BLOCK_UNKNOWN
)
4101 sched_reg_basic_block
[regno
] = current_block_num
;
4102 else if (sched_reg_basic_block
[regno
] != current_block_num
)
4103 sched_reg_basic_block
[regno
] = REG_BLOCK_GLOBAL
;
4105 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
);
4110 /* Make the register live again. */
4111 if (regno
< FIRST_PSEUDO_REGISTER
)
4113 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
4116 SET_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4121 SET_REGNO_REG_SET (bb_live_regs
, regno
);
4127 /* Macros and functions for keeping the priority queue sorted, and
4128 dealing with queueing and dequeueing of instructions. */
4130 #define SCHED_SORT(READY, N_READY) \
4131 do { if ((N_READY) == 2) \
4132 swap_sort (READY, N_READY); \
4133 else if ((N_READY) > 2) \
4134 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4137 /* Returns a positive value if x is preferred; returns a negative value if
4138 y is preferred. Should never return 0, since that will make the sort
4142 rank_for_schedule (x
, y
)
4143 const GENERIC_PTR x
;
4144 const GENERIC_PTR y
;
4146 rtx tmp
= *(rtx
*)y
;
4147 rtx tmp2
= *(rtx
*)x
;
4149 int tmp_class
, tmp2_class
, depend_count1
, depend_count2
;
4150 int val
, priority_val
, spec_val
, prob_val
, weight_val
;
4153 /* prefer insn with higher priority */
4154 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
4156 return priority_val
;
4158 /* prefer an insn with smaller contribution to registers-pressure */
4159 if (!reload_completed
&&
4160 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
4161 return (weight_val
);
4163 /* some comparison make sense in interblock scheduling only */
4164 if (INSN_BB (tmp
) != INSN_BB (tmp2
))
4166 /* prefer an inblock motion on an interblock motion */
4167 if ((INSN_BB (tmp2
) == target_bb
) && (INSN_BB (tmp
) != target_bb
))
4169 if ((INSN_BB (tmp
) == target_bb
) && (INSN_BB (tmp2
) != target_bb
))
4172 /* prefer a useful motion on a speculative one */
4173 if ((spec_val
= IS_SPECULATIVE_INSN (tmp
) - IS_SPECULATIVE_INSN (tmp2
)))
4176 /* prefer a more probable (speculative) insn */
4177 prob_val
= INSN_PROBABILITY (tmp2
) - INSN_PROBABILITY (tmp
);
4182 /* compare insns based on their relation to the last-scheduled-insn */
4183 if (last_scheduled_insn
)
4185 /* Classify the instructions into three classes:
4186 1) Data dependent on last schedule insn.
4187 2) Anti/Output dependent on last scheduled insn.
4188 3) Independent of last scheduled insn, or has latency of one.
4189 Choose the insn from the highest numbered class if different. */
4190 link
= find_insn_list (tmp
, INSN_DEPEND (last_scheduled_insn
));
4191 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp
) == 1)
4193 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4198 link
= find_insn_list (tmp2
, INSN_DEPEND (last_scheduled_insn
));
4199 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp2
) == 1)
4201 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4206 if ((val
= tmp2_class
- tmp_class
))
4210 /* Prefer the insn which has more later insns that depend on it.
4211 This gives the scheduler more freedom when scheduling later
4212 instructions at the expense of added register pressure. */
4214 for (link
= INSN_DEPEND (tmp
); link
; link
= XEXP (link
, 1))
4218 for (link
= INSN_DEPEND (tmp2
); link
; link
= XEXP (link
, 1))
4221 val
= depend_count2
- depend_count1
;
4225 /* If insns are equally good, sort by INSN_LUID (original insn order),
4226 so that we make the sort stable. This minimizes instruction movement,
4227 thus minimizing sched's effect on debugging and cross-jumping. */
4228 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
4231 /* Resort the array A in which only element at index N may be out of order. */
4233 HAIFA_INLINE
static void
4238 rtx insn
= a
[n
- 1];
4241 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
4249 static int max_priority
;
4251 /* Add INSN to the insn queue so that it can be executed at least
4252 N_CYCLES after the currently executing insn. Preserve insns
4253 chain for debugging purposes. */
4255 HAIFA_INLINE
static void
4256 queue_insn (insn
, n_cycles
)
4260 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
4261 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
4262 insn_queue
[next_q
] = link
;
4265 if (sched_verbose
>= 2)
4267 fprintf (dump
, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn
));
4269 if (INSN_BB (insn
) != target_bb
)
4270 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
4272 fprintf (dump
, "queued for %d cycles.\n", n_cycles
);
4277 /* Return nonzero if PAT is the pattern of an insn which makes a
4280 HAIFA_INLINE
static int
4281 birthing_insn_p (pat
)
4286 if (reload_completed
== 1)
4289 if (GET_CODE (pat
) == SET
4290 && (GET_CODE (SET_DEST (pat
)) == REG
4291 || (GET_CODE (SET_DEST (pat
)) == PARALLEL
4292 && GET_MODE (SET_DEST (pat
)) == BLKmode
)))
4294 rtx dest
= SET_DEST (pat
);
4297 /* It would be more accurate to use refers_to_regno_p or
4298 reg_mentioned_p to determine when the dest is not live before this
4300 if (GET_CODE (dest
) == REG
)
4303 if (REGNO_REG_SET_P (bb_live_regs
, i
))
4304 return (REG_N_SETS (i
) == 1);
4308 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
4310 int regno
= REGNO (SET_DEST (XVECEXP (dest
, 0, i
)));
4311 if (REGNO_REG_SET_P (bb_live_regs
, regno
))
4312 return (REG_N_SETS (regno
) == 1);
4317 if (GET_CODE (pat
) == PARALLEL
)
4319 for (j
= 0; j
< XVECLEN (pat
, 0); j
++)
4320 if (birthing_insn_p (XVECEXP (pat
, 0, j
)))
4326 /* PREV is an insn that is ready to execute. Adjust its priority if that
4327 will help shorten register lifetimes. */
4329 HAIFA_INLINE
static void
4330 adjust_priority (prev
)
4333 /* Trying to shorten register lives after reload has completed
4334 is useless and wrong. It gives inaccurate schedules. */
4335 if (reload_completed
== 0)
4340 /* ??? This code has no effect, because REG_DEAD notes are removed
4341 before we ever get here. */
4342 for (note
= REG_NOTES (prev
); note
; note
= XEXP (note
, 1))
4343 if (REG_NOTE_KIND (note
) == REG_DEAD
)
4346 /* Defer scheduling insns which kill registers, since that
4347 shortens register lives. Prefer scheduling insns which
4348 make registers live for the same reason. */
4352 INSN_PRIORITY (prev
) >>= 3;
4355 INSN_PRIORITY (prev
) >>= 2;
4359 INSN_PRIORITY (prev
) >>= 1;
4362 if (birthing_insn_p (PATTERN (prev
)))
4364 int max
= max_priority
;
4366 if (max
> INSN_PRIORITY (prev
))
4367 INSN_PRIORITY (prev
) = max
;
4371 #ifdef ADJUST_PRIORITY
4372 ADJUST_PRIORITY (prev
);
4377 /* Clock at which the previous instruction was issued. */
4378 static int last_clock_var
;
4380 /* INSN is the "currently executing insn". Launch each insn which was
4381 waiting on INSN. READY is a vector of insns which are ready to fire.
4382 N_READY is the number of elements in READY. CLOCK is the current
4386 schedule_insn (insn
, ready
, n_ready
, clock
)
4395 unit
= insn_unit (insn
);
4397 if (sched_verbose
>= 2)
4399 fprintf (dump
, ";;\t\t--> scheduling insn <<<%d>>> on unit ", INSN_UID (insn
));
4400 insn_print_units (insn
);
4401 fprintf (dump
, "\n");
4404 if (sched_verbose
&& unit
== -1)
4405 visualize_no_unit (insn
);
4407 if (MAX_BLOCKAGE
> 1 || issue_rate
> 1 || sched_verbose
)
4408 schedule_unit (unit
, insn
, clock
);
4410 if (INSN_DEPEND (insn
) == 0)
4413 /* This is used by the function adjust_priority above. */
4415 max_priority
= MAX (INSN_PRIORITY (ready
[0]), INSN_PRIORITY (insn
));
4417 max_priority
= INSN_PRIORITY (insn
);
4419 for (link
= INSN_DEPEND (insn
); link
!= 0; link
= XEXP (link
, 1))
4421 rtx next
= XEXP (link
, 0);
4422 int cost
= insn_cost (insn
, link
, next
);
4424 INSN_TICK (next
) = MAX (INSN_TICK (next
), clock
+ cost
);
4426 if ((INSN_DEP_COUNT (next
) -= 1) == 0)
4428 int effective_cost
= INSN_TICK (next
) - clock
;
4430 /* For speculative insns, before inserting to ready/queue,
4431 check live, exception-free, and issue-delay */
4432 if (INSN_BB (next
) != target_bb
4433 && (!IS_VALID (INSN_BB (next
))
4435 || (IS_SPECULATIVE_INSN (next
)
4436 && (insn_issue_delay (next
) > 3
4437 || !check_live (next
, INSN_BB (next
))
4438 || !is_exception_free (next
, INSN_BB (next
), target_bb
)))))
4441 if (sched_verbose
>= 2)
4443 fprintf (dump
, ";;\t\tdependences resolved: insn %d ", INSN_UID (next
));
4445 if (current_nr_blocks
> 1 && INSN_BB (next
) != target_bb
)
4446 fprintf (dump
, "/b%d ", INSN_BLOCK (next
));
4448 if (effective_cost
<= 1)
4449 fprintf (dump
, "into ready\n");
4451 fprintf (dump
, "into queue with cost=%d\n", effective_cost
);
4454 /* Adjust the priority of NEXT and either put it on the ready
4455 list or queue it. */
4456 adjust_priority (next
);
4457 if (effective_cost
<= 1)
4458 ready
[n_ready
++] = next
;
4460 queue_insn (next
, effective_cost
);
4464 /* Annotate the instruction with issue information -- TImode
4465 indicates that the instruction is expected not to be able
4466 to issue on the same cycle as the previous insn. A machine
4467 may use this information to decide how the instruction should
4469 if (reload_completed
&& issue_rate
> 1)
4471 PUT_MODE (insn
, clock
> last_clock_var
? TImode
: VOIDmode
);
4472 last_clock_var
= clock
;
4479 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4483 create_reg_dead_note (reg
, insn
)
4488 /* The number of registers killed after scheduling must be the same as the
4489 number of registers killed before scheduling. The number of REG_DEAD
4490 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4491 might become one DImode hard register REG_DEAD note, but the number of
4492 registers killed will be conserved.
4494 We carefully remove REG_DEAD notes from the dead_notes list, so that
4495 there will be none left at the end. If we run out early, then there
4496 is a bug somewhere in flow, combine and/or sched. */
4498 if (dead_notes
== 0)
4500 if (current_nr_blocks
<= 1)
4503 link
= alloc_EXPR_LIST (REG_DEAD
, NULL_RTX
, NULL_RTX
);
4507 /* Number of regs killed by REG. */
4508 int regs_killed
= (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
? 1
4509 : HARD_REGNO_NREGS (REGNO (reg
), GET_MODE (reg
)));
4510 /* Number of regs killed by REG_DEAD notes taken off the list. */
4514 reg_note_regs
= (REGNO (XEXP (link
, 0)) >= FIRST_PSEUDO_REGISTER
? 1
4515 : HARD_REGNO_NREGS (REGNO (XEXP (link
, 0)),
4516 GET_MODE (XEXP (link
, 0))));
4517 while (reg_note_regs
< regs_killed
)
4519 link
= XEXP (link
, 1);
4521 /* LINK might be zero if we killed more registers after scheduling
4522 than before, and the last hard register we kill is actually
4525 This is normal for interblock scheduling, so deal with it in
4526 that case, else abort. */
4527 if (link
== NULL_RTX
&& current_nr_blocks
<= 1)
4529 else if (link
== NULL_RTX
)
4530 link
= alloc_EXPR_LIST (REG_DEAD
, gen_rtx_REG (word_mode
, 0),
4533 reg_note_regs
+= (REGNO (XEXP (link
, 0)) >= FIRST_PSEUDO_REGISTER
? 1
4534 : HARD_REGNO_NREGS (REGNO (XEXP (link
, 0)),
4535 GET_MODE (XEXP (link
, 0))));
4537 dead_notes
= XEXP (link
, 1);
4539 /* If we took too many regs kills off, put the extra ones back. */
4540 while (reg_note_regs
> regs_killed
)
4542 rtx temp_reg
, temp_link
;
4544 temp_reg
= gen_rtx_REG (word_mode
, 0);
4545 temp_link
= alloc_EXPR_LIST (REG_DEAD
, temp_reg
, dead_notes
);
4546 dead_notes
= temp_link
;
4551 XEXP (link
, 0) = reg
;
4552 XEXP (link
, 1) = REG_NOTES (insn
);
4553 REG_NOTES (insn
) = link
;
4556 /* Subroutine on attach_deaths_insn--handles the recursive search
4557 through INSN. If SET_P is true, then x is being modified by the insn. */
4560 attach_deaths (x
, insn
, set_p
)
4567 register enum rtx_code code
;
4573 code
= GET_CODE (x
);
4585 /* Get rid of the easy cases first. */
4590 /* If the register dies in this insn, queue that note, and mark
4591 this register as needing to die. */
4592 /* This code is very similar to mark_used_1 (if set_p is false)
4593 and mark_set_1 (if set_p is true) in flow.c. */
4603 all_needed
= some_needed
= REGNO_REG_SET_P (old_live_regs
, regno
);
4604 if (regno
< FIRST_PSEUDO_REGISTER
)
4608 n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4611 int needed
= (REGNO_REG_SET_P (old_live_regs
, regno
+ n
));
4612 some_needed
|= needed
;
4613 all_needed
&= needed
;
4617 /* If it wasn't live before we started, then add a REG_DEAD note.
4618 We must check the previous lifetime info not the current info,
4619 because we may have to execute this code several times, e.g.
4620 once for a clobber (which doesn't add a note) and later
4621 for a use (which does add a note).
4623 Always make the register live. We must do this even if it was
4624 live before, because this may be an insn which sets and uses
4625 the same register, in which case the register has already been
4626 killed, so we must make it live again.
4628 Global registers are always live, and should never have a REG_DEAD
4629 note added for them, so none of the code below applies to them. */
4631 if (regno
>= FIRST_PSEUDO_REGISTER
|| ! global_regs
[regno
])
4633 /* Never add REG_DEAD notes for STACK_POINTER_REGNUM
4634 since it's always considered to be live. Similarly
4635 for FRAME_POINTER_REGNUM if a frame pointer is needed
4636 and for ARG_POINTER_REGNUM if it is fixed. */
4637 if (! (regno
== FRAME_POINTER_REGNUM
4638 && (! reload_completed
|| frame_pointer_needed
))
4639 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4640 && ! (regno
== HARD_FRAME_POINTER_REGNUM
4641 && (! reload_completed
|| frame_pointer_needed
))
4643 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4644 && ! (regno
== ARG_POINTER_REGNUM
&& fixed_regs
[regno
])
4646 && regno
!= STACK_POINTER_REGNUM
)
4648 if (! all_needed
&& ! dead_or_set_p (insn
, x
))
4650 /* Check for the case where the register dying partially
4651 overlaps the register set by this insn. */
4652 if (regno
< FIRST_PSEUDO_REGISTER
4653 && HARD_REGNO_NREGS (regno
, GET_MODE (x
)) > 1)
4655 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4657 some_needed
|= dead_or_set_regno_p (insn
, regno
+ n
);
4660 /* If none of the words in X is needed, make a REG_DEAD
4661 note. Otherwise, we must make partial REG_DEAD
4664 create_reg_dead_note (x
, insn
);
4669 /* Don't make a REG_DEAD note for a part of a
4670 register that is set in the insn. */
4671 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
)) - 1;
4673 if (! REGNO_REG_SET_P (old_live_regs
, regno
+i
)
4674 && ! dead_or_set_regno_p (insn
, regno
+ i
))
4675 create_reg_dead_note (gen_rtx_REG (reg_raw_mode
[regno
+ i
],
4682 if (regno
< FIRST_PSEUDO_REGISTER
)
4684 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4687 SET_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4692 /* Recompute REG_BASIC_BLOCK as we update all the other
4693 dataflow information. */
4694 if (sched_reg_basic_block
[regno
] == REG_BLOCK_UNKNOWN
)
4695 sched_reg_basic_block
[regno
] = current_block_num
;
4696 else if (sched_reg_basic_block
[regno
] != current_block_num
)
4697 sched_reg_basic_block
[regno
] = REG_BLOCK_GLOBAL
;
4699 SET_REGNO_REG_SET (bb_live_regs
, regno
);
4706 /* Handle tail-recursive case. */
4707 attach_deaths (XEXP (x
, 0), insn
, 0);
4711 attach_deaths (SUBREG_REG (x
), insn
,
4712 set_p
&& ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
)))
4714 || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
)))
4715 == GET_MODE_SIZE (GET_MODE ((x
))))));
4718 case STRICT_LOW_PART
:
4719 attach_deaths (XEXP (x
, 0), insn
, 0);
4724 attach_deaths (XEXP (x
, 0), insn
, 0);
4725 attach_deaths (XEXP (x
, 1), insn
, 0);
4726 attach_deaths (XEXP (x
, 2), insn
, 0);
4731 && GET_MODE (x
) == BLKmode
)
4733 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
4734 attach_deaths (SET_DEST (XVECEXP (x
, 0, i
)), insn
, 1);
4740 /* Other cases: walk the insn. */
4741 fmt
= GET_RTX_FORMAT (code
);
4742 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4745 attach_deaths (XEXP (x
, i
), insn
, 0);
4746 else if (fmt
[i
] == 'E')
4747 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
4748 attach_deaths (XVECEXP (x
, i
, j
), insn
, 0);
4753 /* After INSN has executed, add register death notes for each register
4754 that is dead after INSN. */
4757 attach_deaths_insn (insn
)
4760 rtx x
= PATTERN (insn
);
4761 register RTX_CODE code
= GET_CODE (x
);
4766 attach_deaths (SET_SRC (x
), insn
, 0);
4768 /* A register might die here even if it is the destination, e.g.
4769 it is the target of a volatile read and is otherwise unused.
4770 Hence we must always call attach_deaths for the SET_DEST. */
4771 attach_deaths (SET_DEST (x
), insn
, 1);
4773 else if (code
== PARALLEL
)
4776 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
4778 code
= GET_CODE (XVECEXP (x
, 0, i
));
4781 attach_deaths (SET_SRC (XVECEXP (x
, 0, i
)), insn
, 0);
4783 attach_deaths (SET_DEST (XVECEXP (x
, 0, i
)), insn
, 1);
4785 /* Flow does not add REG_DEAD notes to registers that die in
4786 clobbers, so we can't either. */
4787 else if (code
!= CLOBBER
)
4788 attach_deaths (XVECEXP (x
, 0, i
), insn
, 0);
4791 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4792 MEM being clobbered, just like flow. */
4793 else if (code
== CLOBBER
&& GET_CODE (XEXP (x
, 0)) == MEM
)
4794 attach_deaths (XEXP (XEXP (x
, 0), 0), insn
, 0);
4795 /* Otherwise don't add a death note to things being clobbered. */
4796 else if (code
!= CLOBBER
)
4797 attach_deaths (x
, insn
, 0);
4799 /* Make death notes for things used in the called function. */
4800 if (GET_CODE (insn
) == CALL_INSN
)
4801 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
4802 attach_deaths (XEXP (XEXP (link
, 0), 0), insn
,
4803 GET_CODE (XEXP (link
, 0)) == CLOBBER
);
4806 /* functions for handlnig of notes */
4808 /* Delete notes beginning with INSN and put them in the chain
4809 of notes ended by NOTE_LIST.
4810 Returns the insn following the notes. */
4813 unlink_other_notes (insn
, tail
)
4816 rtx prev
= PREV_INSN (insn
);
4818 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4820 rtx next
= NEXT_INSN (insn
);
4821 /* Delete the note from its current position. */
4823 NEXT_INSN (prev
) = next
;
4825 PREV_INSN (next
) = prev
;
4827 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4828 immediately after the call they follow. We use a fake
4829 (REG_DEAD (const_int -1)) note to remember them.
4830 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4831 if (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_SETJMP
4832 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
4833 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
4834 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_START
4835 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_END
4836 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_BEG
4837 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_END
)
4839 /* Insert the note at the end of the notes list. */
4840 PREV_INSN (insn
) = note_list
;
4842 NEXT_INSN (note_list
) = insn
;
4851 /* Delete line notes beginning with INSN. Record line-number notes so
4852 they can be reused. Returns the insn following the notes. */
4855 unlink_line_notes (insn
, tail
)
4858 rtx prev
= PREV_INSN (insn
);
4860 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4862 rtx next
= NEXT_INSN (insn
);
4864 if (write_symbols
!= NO_DEBUG
&& NOTE_LINE_NUMBER (insn
) > 0)
4866 /* Delete the note from its current position. */
4868 NEXT_INSN (prev
) = next
;
4870 PREV_INSN (next
) = prev
;
4872 /* Record line-number notes so they can be reused. */
4873 LINE_NOTE (insn
) = insn
;
4883 /* Return the head and tail pointers of BB. */
4885 HAIFA_INLINE
static void
4886 get_block_head_tail (bb
, headp
, tailp
)
4896 b
= BB_TO_BLOCK (bb
);
4898 /* HEAD and TAIL delimit the basic block being scheduled. */
4899 head
= BLOCK_HEAD (b
);
4900 tail
= BLOCK_END (b
);
4902 /* Don't include any notes or labels at the beginning of the
4903 basic block, or notes at the ends of basic blocks. */
4904 while (head
!= tail
)
4906 if (GET_CODE (head
) == NOTE
)
4907 head
= NEXT_INSN (head
);
4908 else if (GET_CODE (tail
) == NOTE
)
4909 tail
= PREV_INSN (tail
);
4910 else if (GET_CODE (head
) == CODE_LABEL
)
4911 head
= NEXT_INSN (head
);
4920 /* Delete line notes from bb. Save them so they can be later restored
4921 (in restore_line_notes ()). */
4932 get_block_head_tail (bb
, &head
, &tail
);
4935 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
4938 next_tail
= NEXT_INSN (tail
);
4939 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4943 /* Farm out notes, and maybe save them in NOTE_LIST.
4944 This is needed to keep the debugger from
4945 getting completely deranged. */
4946 if (GET_CODE (insn
) == NOTE
)
4949 insn
= unlink_line_notes (insn
, next_tail
);
4955 if (insn
== next_tail
)
4961 /* Save line number notes for each insn in bb. */
4964 save_line_notes (bb
)
4970 /* We must use the true line number for the first insn in the block
4971 that was computed and saved at the start of this pass. We can't
4972 use the current line number, because scheduling of the previous
4973 block may have changed the current line number. */
4975 rtx line
= line_note_head
[BB_TO_BLOCK (bb
)];
4978 get_block_head_tail (bb
, &head
, &tail
);
4979 next_tail
= NEXT_INSN (tail
);
4981 for (insn
= BLOCK_HEAD (BB_TO_BLOCK (bb
));
4983 insn
= NEXT_INSN (insn
))
4984 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4987 LINE_NOTE (insn
) = line
;
4991 /* After bb was scheduled, insert line notes into the insns list. */
4994 restore_line_notes (bb
)
4997 rtx line
, note
, prev
, new;
4998 int added_notes
= 0;
5000 rtx head
, next_tail
, insn
;
5002 b
= BB_TO_BLOCK (bb
);
5004 head
= BLOCK_HEAD (b
);
5005 next_tail
= NEXT_INSN (BLOCK_END (b
));
5007 /* Determine the current line-number. We want to know the current
5008 line number of the first insn of the block here, in case it is
5009 different from the true line number that was saved earlier. If
5010 different, then we need a line number note before the first insn
5011 of this block. If it happens to be the same, then we don't want to
5012 emit another line number note here. */
5013 for (line
= head
; line
; line
= PREV_INSN (line
))
5014 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
5017 /* Walk the insns keeping track of the current line-number and inserting
5018 the line-number notes as needed. */
5019 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5020 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
5022 /* This used to emit line number notes before every non-deleted note.
5023 However, this confuses a debugger, because line notes not separated
5024 by real instructions all end up at the same address. I can find no
5025 use for line number notes before other notes, so none are emitted. */
5026 else if (GET_CODE (insn
) != NOTE
5027 && (note
= LINE_NOTE (insn
)) != 0
5030 || NOTE_LINE_NUMBER (note
) != NOTE_LINE_NUMBER (line
)
5031 || NOTE_SOURCE_FILE (note
) != NOTE_SOURCE_FILE (line
)))
5034 prev
= PREV_INSN (insn
);
5035 if (LINE_NOTE (note
))
5037 /* Re-use the original line-number note. */
5038 LINE_NOTE (note
) = 0;
5039 PREV_INSN (note
) = prev
;
5040 NEXT_INSN (prev
) = note
;
5041 PREV_INSN (insn
) = note
;
5042 NEXT_INSN (note
) = insn
;
5047 new = emit_note_after (NOTE_LINE_NUMBER (note
), prev
);
5048 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note
);
5049 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note
);
5052 if (sched_verbose
&& added_notes
)
5053 fprintf (dump
, ";; added %d line-number notes\n", added_notes
);
5056 /* After scheduling the function, delete redundant line notes from the
5060 rm_redundant_line_notes ()
5063 rtx insn
= get_insns ();
5064 int active_insn
= 0;
5067 /* Walk the insns deleting redundant line-number notes. Many of these
5068 are already present. The remainder tend to occur at basic
5069 block boundaries. */
5070 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
5071 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
5073 /* If there are no active insns following, INSN is redundant. */
5074 if (active_insn
== 0)
5077 NOTE_SOURCE_FILE (insn
) = 0;
5078 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
5080 /* If the line number is unchanged, LINE is redundant. */
5082 && NOTE_LINE_NUMBER (line
) == NOTE_LINE_NUMBER (insn
)
5083 && NOTE_SOURCE_FILE (line
) == NOTE_SOURCE_FILE (insn
))
5086 NOTE_SOURCE_FILE (line
) = 0;
5087 NOTE_LINE_NUMBER (line
) = NOTE_INSN_DELETED
;
5094 else if (!((GET_CODE (insn
) == NOTE
5095 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
5096 || (GET_CODE (insn
) == INSN
5097 && (GET_CODE (PATTERN (insn
)) == USE
5098 || GET_CODE (PATTERN (insn
)) == CLOBBER
))))
5101 if (sched_verbose
&& notes
)
5102 fprintf (dump
, ";; deleted %d line-number notes\n", notes
);
5105 /* Delete notes between head and tail and put them in the chain
5106 of notes ended by NOTE_LIST. */
5109 rm_other_notes (head
, tail
)
5117 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
5120 next_tail
= NEXT_INSN (tail
);
5121 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5125 /* Farm out notes, and maybe save them in NOTE_LIST.
5126 This is needed to keep the debugger from
5127 getting completely deranged. */
5128 if (GET_CODE (insn
) == NOTE
)
5132 insn
= unlink_other_notes (insn
, next_tail
);
5138 if (insn
== next_tail
)
5144 /* Constructor for `sometimes' data structure. */
5147 new_sometimes_live (regs_sometimes_live
, regno
, sometimes_max
)
5148 struct sometimes
*regs_sometimes_live
;
5152 register struct sometimes
*p
;
5154 /* There should never be a register greater than max_regno here. If there
5155 is, it means that a define_split has created a new pseudo reg. This
5156 is not allowed, since there will not be flow info available for any
5157 new register, so catch the error here. */
5158 if (regno
>= max_regno
)
5161 p
= ®s_sometimes_live
[sometimes_max
];
5164 p
->calls_crossed
= 0;
5166 return sometimes_max
;
5169 /* Count lengths of all regs we are currently tracking,
5170 and find new registers no longer live. */
5173 finish_sometimes_live (regs_sometimes_live
, sometimes_max
)
5174 struct sometimes
*regs_sometimes_live
;
5179 for (i
= 0; i
< sometimes_max
; i
++)
5181 register struct sometimes
*p
= ®s_sometimes_live
[i
];
5182 int regno
= p
->regno
;
5184 sched_reg_live_length
[regno
] += p
->live_length
;
5185 sched_reg_n_calls_crossed
[regno
] += p
->calls_crossed
;
5189 /* functions for computation of registers live/usage info */
5191 /* It is assumed that prior to scheduling BASIC_BLOCK (b)->global_live_at_start
5192 contains the registers that are alive at the entry to b.
5194 Two passes follow: The first pass is performed before the scheduling
5195 of a region. It scans each block of the region forward, computing
5196 the set of registers alive at the end of the basic block and
5197 discard REG_DEAD notes (done by find_pre_sched_live ()).
5199 The second path is invoked after scheduling all region blocks.
5200 It scans each block of the region backward, a block being traversed
5201 only after its succesors in the region. When the set of registers
5202 live at the end of a basic block may be changed by the scheduling
5203 (this may happen for multiple blocks region), it is computed as
5204 the union of the registers live at the start of its succesors.
5205 The last-use information is updated by inserting REG_DEAD notes.
5206 (done by find_post_sched_live ()) */
5208 /* Scan all the insns to be scheduled, removing register death notes.
5209 Register death notes end up in DEAD_NOTES.
5210 Recreate the register life information for the end of this basic
5214 find_pre_sched_live (bb
)
5217 rtx insn
, next_tail
, head
, tail
;
5218 int b
= BB_TO_BLOCK (bb
);
5220 get_block_head_tail (bb
, &head
, &tail
);
5221 COPY_REG_SET (bb_live_regs
, BASIC_BLOCK (b
)->global_live_at_start
);
5222 next_tail
= NEXT_INSN (tail
);
5224 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5226 rtx prev
, next
, link
;
5229 /* Handle register life information. */
5230 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
5232 /* See if the register gets born here. */
5233 /* We must check for registers being born before we check for
5234 registers dying. It is possible for a register to be born and
5235 die in the same insn, e.g. reading from a volatile memory
5236 location into an otherwise unused register. Such a register
5237 must be marked as dead after this insn. */
5238 if (GET_CODE (PATTERN (insn
)) == SET
5239 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
5241 sched_note_set (PATTERN (insn
), 0);
5245 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
5248 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5249 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
5250 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
5252 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 0);
5256 /* ??? This code is obsolete and should be deleted. It
5257 is harmless though, so we will leave it in for now. */
5258 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5259 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == USE
)
5260 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 0);
5263 /* Each call cobbers (makes live) all call-clobbered regs
5264 that are not global or fixed. Note that the function-value
5265 reg is a call_clobbered reg. */
5266 if (GET_CODE (insn
) == CALL_INSN
)
5269 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
5270 if (call_used_regs
[j
] && !global_regs
[j
]
5273 SET_REGNO_REG_SET (bb_live_regs
, j
);
5277 /* Need to know what registers this insn kills. */
5278 for (prev
= 0, link
= REG_NOTES (insn
); link
; link
= next
)
5280 next
= XEXP (link
, 1);
5281 if ((REG_NOTE_KIND (link
) == REG_DEAD
5282 || REG_NOTE_KIND (link
) == REG_UNUSED
)
5283 /* Verify that the REG_NOTE has a valid value. */
5284 && GET_CODE (XEXP (link
, 0)) == REG
)
5286 register int regno
= REGNO (XEXP (link
, 0));
5290 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5292 if (REG_NOTE_KIND (link
) == REG_DEAD
)
5295 XEXP (prev
, 1) = next
;
5297 REG_NOTES (insn
) = next
;
5298 XEXP (link
, 1) = dead_notes
;
5304 if (regno
< FIRST_PSEUDO_REGISTER
)
5306 int j
= HARD_REGNO_NREGS (regno
,
5307 GET_MODE (XEXP (link
, 0)));
5310 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
+j
);
5315 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
);
5323 INSN_REG_WEIGHT (insn
) = reg_weight
;
5327 /* Update register life and usage information for block bb
5328 after scheduling. Put register dead notes back in the code. */
5331 find_post_sched_live (bb
)
5338 rtx head
, tail
, prev_head
, next_tail
;
5340 register struct sometimes
*regs_sometimes_live
;
5342 b
= BB_TO_BLOCK (bb
);
5344 /* compute live regs at the end of bb as a function of its successors. */
5345 if (current_nr_blocks
> 1)
5350 first_edge
= e
= OUT_EDGES (b
);
5351 CLEAR_REG_SET (bb_live_regs
);
5358 b_succ
= TO_BLOCK (e
);
5359 IOR_REG_SET (bb_live_regs
,
5360 BASIC_BLOCK (b_succ
)->global_live_at_start
);
5363 while (e
!= first_edge
);
5366 get_block_head_tail (bb
, &head
, &tail
);
5367 next_tail
= NEXT_INSN (tail
);
5368 prev_head
= PREV_INSN (head
);
5370 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, FIRST_PSEUDO_REGISTER
, i
,
5372 sched_reg_basic_block
[i
] = REG_BLOCK_GLOBAL
;
5375 /* if the block is empty, same regs are alive at its end and its start.
5376 since this is not guaranteed after interblock scheduling, make sure they
5377 are truly identical. */
5378 if (NEXT_INSN (prev_head
) == tail
5379 && (GET_RTX_CLASS (GET_CODE (tail
)) != 'i'))
5381 if (current_nr_blocks
> 1)
5382 COPY_REG_SET (BASIC_BLOCK (b
)->global_live_at_start
, bb_live_regs
);
5387 b
= BB_TO_BLOCK (bb
);
5388 current_block_num
= b
;
5390 /* Keep track of register lives. */
5391 old_live_regs
= ALLOCA_REG_SET ();
5393 = (struct sometimes
*) alloca (max_regno
* sizeof (struct sometimes
));
5396 /* initiate "sometimes" data, starting with registers live at end */
5398 COPY_REG_SET (old_live_regs
, bb_live_regs
);
5399 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, 0, j
,
5402 = new_sometimes_live (regs_sometimes_live
,
5406 /* scan insns back, computing regs live info */
5407 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
5409 /* First we kill registers set by this insn, and then we
5410 make registers used by this insn live. This is the opposite
5411 order used above because we are traversing the instructions
5414 /* Strictly speaking, we should scan REG_UNUSED notes and make
5415 every register mentioned there live, however, we will just
5416 kill them again immediately below, so there doesn't seem to
5417 be any reason why we bother to do this. */
5419 /* See if this is the last notice we must take of a register. */
5420 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5423 if (GET_CODE (PATTERN (insn
)) == SET
5424 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
5425 sched_note_set (PATTERN (insn
), 1);
5426 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
5428 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5429 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
5430 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
5431 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 1);
5434 /* This code keeps life analysis information up to date. */
5435 if (GET_CODE (insn
) == CALL_INSN
)
5437 register struct sometimes
*p
;
5439 /* A call kills all call used registers that are not
5440 global or fixed, except for those mentioned in the call
5441 pattern which will be made live again later. */
5442 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
5443 if (call_used_regs
[i
] && ! global_regs
[i
]
5446 CLEAR_REGNO_REG_SET (bb_live_regs
, i
);
5449 /* Regs live at the time of a call instruction must not
5450 go in a register clobbered by calls. Record this for
5451 all regs now live. Note that insns which are born or
5452 die in a call do not cross a call, so this must be done
5453 after the killings (above) and before the births
5455 p
= regs_sometimes_live
;
5456 for (i
= 0; i
< sometimes_max
; i
++, p
++)
5457 if (REGNO_REG_SET_P (bb_live_regs
, p
->regno
))
5458 p
->calls_crossed
+= 1;
5461 /* Make every register used live, and add REG_DEAD notes for
5462 registers which were not live before we started. */
5463 attach_deaths_insn (insn
);
5465 /* Find registers now made live by that instruction. */
5466 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs
, old_live_regs
, 0, j
,
5469 = new_sometimes_live (regs_sometimes_live
,
5472 IOR_REG_SET (old_live_regs
, bb_live_regs
);
5474 /* Count lengths of all regs we are worrying about now,
5475 and handle registers no longer live. */
5477 for (i
= 0; i
< sometimes_max
; i
++)
5479 register struct sometimes
*p
= ®s_sometimes_live
[i
];
5480 int regno
= p
->regno
;
5482 p
->live_length
+= 1;
5484 if (!REGNO_REG_SET_P (bb_live_regs
, regno
))
5486 /* This is the end of one of this register's lifetime
5487 segments. Save the lifetime info collected so far,
5488 and clear its bit in the old_live_regs entry. */
5489 sched_reg_live_length
[regno
] += p
->live_length
;
5490 sched_reg_n_calls_crossed
[regno
] += p
->calls_crossed
;
5491 CLEAR_REGNO_REG_SET (old_live_regs
, p
->regno
);
5493 /* Delete the reg_sometimes_live entry for this reg by
5494 copying the last entry over top of it. */
5495 *p
= regs_sometimes_live
[--sometimes_max
];
5496 /* ...and decrement i so that this newly copied entry
5497 will be processed. */
5503 finish_sometimes_live (regs_sometimes_live
, sometimes_max
);
5505 /* In interblock scheduling, global_live_at_start may have changed. */
5506 if (current_nr_blocks
> 1)
5507 COPY_REG_SET (BASIC_BLOCK (b
)->global_live_at_start
, bb_live_regs
);
5510 FREE_REG_SET (old_live_regs
);
5511 } /* find_post_sched_live */
5513 /* After scheduling the subroutine, restore information about uses of
5521 if (n_basic_blocks
> 0)
5522 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, FIRST_PSEUDO_REGISTER
, regno
,
5524 sched_reg_basic_block
[regno
]
5528 for (regno
= 0; regno
< max_regno
; regno
++)
5529 if (sched_reg_live_length
[regno
])
5533 if (REG_LIVE_LENGTH (regno
) > sched_reg_live_length
[regno
])
5535 ";; register %d life shortened from %d to %d\n",
5536 regno
, REG_LIVE_LENGTH (regno
),
5537 sched_reg_live_length
[regno
]);
5538 /* Negative values are special; don't overwrite the current
5539 reg_live_length value if it is negative. */
5540 else if (REG_LIVE_LENGTH (regno
) < sched_reg_live_length
[regno
]
5541 && REG_LIVE_LENGTH (regno
) >= 0)
5543 ";; register %d life extended from %d to %d\n",
5544 regno
, REG_LIVE_LENGTH (regno
),
5545 sched_reg_live_length
[regno
]);
5547 if (!REG_N_CALLS_CROSSED (regno
)
5548 && sched_reg_n_calls_crossed
[regno
])
5550 ";; register %d now crosses calls\n", regno
);
5551 else if (REG_N_CALLS_CROSSED (regno
)
5552 && !sched_reg_n_calls_crossed
[regno
]
5553 && REG_BASIC_BLOCK (regno
) != REG_BLOCK_GLOBAL
)
5555 ";; register %d no longer crosses calls\n", regno
);
5557 if (REG_BASIC_BLOCK (regno
) != sched_reg_basic_block
[regno
]
5558 && sched_reg_basic_block
[regno
] != REG_BLOCK_UNKNOWN
5559 && REG_BASIC_BLOCK(regno
) != REG_BLOCK_UNKNOWN
)
5561 ";; register %d changed basic block from %d to %d\n",
5562 regno
, REG_BASIC_BLOCK(regno
),
5563 sched_reg_basic_block
[regno
]);
5566 /* Negative values are special; don't overwrite the current
5567 reg_live_length value if it is negative. */
5568 if (REG_LIVE_LENGTH (regno
) >= 0)
5569 REG_LIVE_LENGTH (regno
) = sched_reg_live_length
[regno
];
5571 if (sched_reg_basic_block
[regno
] != REG_BLOCK_UNKNOWN
5572 && REG_BASIC_BLOCK(regno
) != REG_BLOCK_UNKNOWN
)
5573 REG_BASIC_BLOCK(regno
) = sched_reg_basic_block
[regno
];
5575 /* We can't change the value of reg_n_calls_crossed to zero for
5576 pseudos which are live in more than one block.
5578 This is because combine might have made an optimization which
5579 invalidated global_live_at_start and reg_n_calls_crossed,
5580 but it does not update them. If we update reg_n_calls_crossed
5581 here, the two variables are now inconsistent, and this might
5582 confuse the caller-save code into saving a register that doesn't
5583 need to be saved. This is only a problem when we zero calls
5584 crossed for a pseudo live in multiple basic blocks.
5586 Alternatively, we could try to correctly update basic block live
5587 at start here in sched, but that seems complicated.
5589 Note: it is possible that a global register became local, as result
5590 of interblock motion, but will remain marked as a global register. */
5591 if (sched_reg_n_calls_crossed
[regno
]
5592 || REG_BASIC_BLOCK (regno
) != REG_BLOCK_GLOBAL
)
5593 REG_N_CALLS_CROSSED (regno
) = sched_reg_n_calls_crossed
[regno
];
5598 /* Scheduling clock, modified in schedule_block() and queue_to_ready () */
5599 static int clock_var
;
5601 /* Move insns that became ready to fire from queue to ready list. */
5604 queue_to_ready (ready
, n_ready
)
5611 q_ptr
= NEXT_Q (q_ptr
);
5613 /* Add all pending insns that can be scheduled without stalls to the
5615 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
5618 insn
= XEXP (link
, 0);
5621 if (sched_verbose
>= 2)
5622 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
5624 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
5625 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
5627 ready
[n_ready
++] = insn
;
5628 if (sched_verbose
>= 2)
5629 fprintf (dump
, "moving to ready without stalls\n");
5631 insn_queue
[q_ptr
] = 0;
5633 /* If there are no ready insns, stall until one is ready and add all
5634 of the pending insns at that point to the ready list. */
5637 register int stalls
;
5639 for (stalls
= 1; stalls
< INSN_QUEUE_SIZE
; stalls
++)
5641 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
5643 for (; link
; link
= XEXP (link
, 1))
5645 insn
= XEXP (link
, 0);
5648 if (sched_verbose
>= 2)
5649 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
5651 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
5652 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
5654 ready
[n_ready
++] = insn
;
5655 if (sched_verbose
>= 2)
5656 fprintf (dump
, "moving to ready with %d stalls\n", stalls
);
5658 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = 0;
5665 if (sched_verbose
&& stalls
)
5666 visualize_stall_cycles (BB_TO_BLOCK (target_bb
), stalls
);
5667 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
5668 clock_var
+= stalls
;
5673 /* Print the ready list for debugging purposes. Callable from debugger. */
5676 debug_ready_list (ready
, n_ready
)
5682 for (i
= 0; i
< n_ready
; i
++)
5684 fprintf (dump
, " %d", INSN_UID (ready
[i
]));
5685 if (current_nr_blocks
> 1 && INSN_BB (ready
[i
]) != target_bb
)
5686 fprintf (dump
, "/b%d", INSN_BLOCK (ready
[i
]));
5688 fprintf (dump
, "\n");
5691 /* Print names of units on which insn can/should execute, for debugging. */
5694 insn_print_units (insn
)
5698 int unit
= insn_unit (insn
);
5701 fprintf (dump
, "none");
5703 fprintf (dump
, "%s", function_units
[unit
].name
);
5706 fprintf (dump
, "[");
5707 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
5710 fprintf (dump
, "%s", function_units
[i
].name
);
5712 fprintf (dump
, " ");
5714 fprintf (dump
, "]");
5718 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5719 of a basic block. If more lines are needed, table is splitted to two.
5720 n_visual_lines is the number of lines printed so far for a block.
5721 visual_tbl contains the block visualization info.
5722 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5723 #define MAX_VISUAL_LINES 100
5728 rtx vis_no_unit
[10];
5730 /* Finds units that are in use in this fuction. Required only
5731 for visualization. */
5734 init_target_units ()
5739 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
5741 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5744 unit
= insn_unit (insn
);
5747 target_units
|= ~unit
;
5749 target_units
|= (1 << unit
);
5753 /* Return the length of the visualization table */
5756 get_visual_tbl_length ()
5762 /* compute length of one field in line */
5763 s
= (char *) alloca (INSN_LEN
+ 5);
5764 sprintf (s
, " %33s", "uname");
5767 /* compute length of one line */
5770 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5771 if (function_units
[unit
].bitmask
& target_units
)
5772 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5775 n
+= strlen ("\n") + 2;
5777 /* compute length of visualization string */
5778 return (MAX_VISUAL_LINES
* n
);
5781 /* Init block visualization debugging info */
5784 init_block_visualization ()
5786 strcpy (visual_tbl
, "");
5794 safe_concat (buf
, cur
, str
)
5799 char *end
= buf
+ BUF_LEN
- 2; /* leave room for null */
5808 while (cur
< end
&& (c
= *str
++) != '\0')
5815 /* This recognizes rtx, I classified as expressions. These are always */
5816 /* represent some action on values or results of other expression, */
5817 /* that may be stored in objects representing values. */
5820 print_exp (buf
, x
, verbose
)
5828 char *fun
= (char *)0;
5833 for (i
= 0; i
< 4; i
++)
5839 switch (GET_CODE (x
))
5842 op
[0] = XEXP (x
, 0);
5843 if (GET_CODE (XEXP (x
, 1)) == CONST_INT
5844 && INTVAL (XEXP (x
, 1)) < 0)
5847 op
[1] = GEN_INT (-INTVAL (XEXP (x
, 1)));
5852 op
[1] = XEXP (x
, 1);
5856 op
[0] = XEXP (x
, 0);
5858 op
[1] = XEXP (x
, 1);
5862 op
[0] = XEXP (x
, 0);
5864 op
[1] = XEXP (x
, 1);
5868 op
[0] = XEXP (x
, 0);
5869 op
[1] = XEXP (x
, 1);
5873 op
[0] = XEXP (x
, 0);
5876 op
[0] = XEXP (x
, 0);
5878 op
[1] = XEXP (x
, 1);
5881 op
[0] = XEXP (x
, 0);
5883 op
[1] = XEXP (x
, 1);
5887 op
[0] = XEXP (x
, 0);
5888 op
[1] = XEXP (x
, 1);
5891 op
[0] = XEXP (x
, 0);
5893 op
[1] = XEXP (x
, 1);
5897 op
[0] = XEXP (x
, 0);
5898 op
[1] = XEXP (x
, 1);
5902 op
[0] = XEXP (x
, 0);
5903 op
[1] = XEXP (x
, 1);
5907 op
[0] = XEXP (x
, 0);
5908 op
[1] = XEXP (x
, 1);
5912 op
[0] = XEXP (x
, 0);
5913 op
[1] = XEXP (x
, 1);
5917 op
[0] = XEXP (x
, 0);
5918 op
[1] = XEXP (x
, 1);
5922 op
[0] = XEXP (x
, 0);
5925 op
[0] = XEXP (x
, 0);
5927 op
[1] = XEXP (x
, 1);
5930 op
[0] = XEXP (x
, 0);
5932 op
[1] = XEXP (x
, 1);
5935 op
[0] = XEXP (x
, 0);
5937 op
[1] = XEXP (x
, 1);
5940 op
[0] = XEXP (x
, 0);
5942 op
[1] = XEXP (x
, 1);
5945 op
[0] = XEXP (x
, 0);
5947 op
[1] = XEXP (x
, 1);
5950 op
[0] = XEXP (x
, 0);
5952 op
[1] = XEXP (x
, 1);
5955 op
[0] = XEXP (x
, 0);
5957 op
[1] = XEXP (x
, 1);
5960 op
[0] = XEXP (x
, 0);
5962 op
[1] = XEXP (x
, 1);
5966 op
[0] = XEXP (x
, 0);
5970 op
[0] = XEXP (x
, 0);
5974 op
[0] = XEXP (x
, 0);
5977 op
[0] = XEXP (x
, 0);
5979 op
[1] = XEXP (x
, 1);
5982 op
[0] = XEXP (x
, 0);
5984 op
[1] = XEXP (x
, 1);
5987 op
[0] = XEXP (x
, 0);
5989 op
[1] = XEXP (x
, 1);
5993 op
[0] = XEXP (x
, 0);
5994 op
[1] = XEXP (x
, 1);
5997 op
[0] = XEXP (x
, 0);
5999 op
[1] = XEXP (x
, 1);
6003 op
[0] = XEXP (x
, 0);
6004 op
[1] = XEXP (x
, 1);
6007 op
[0] = XEXP (x
, 0);
6009 op
[1] = XEXP (x
, 1);
6013 op
[0] = XEXP (x
, 0);
6014 op
[1] = XEXP (x
, 1);
6017 op
[0] = XEXP (x
, 0);
6019 op
[1] = XEXP (x
, 1);
6023 op
[0] = XEXP (x
, 0);
6024 op
[1] = XEXP (x
, 1);
6027 fun
= (verbose
) ? "sign_extract" : "sxt";
6028 op
[0] = XEXP (x
, 0);
6029 op
[1] = XEXP (x
, 1);
6030 op
[2] = XEXP (x
, 2);
6033 fun
= (verbose
) ? "zero_extract" : "zxt";
6034 op
[0] = XEXP (x
, 0);
6035 op
[1] = XEXP (x
, 1);
6036 op
[2] = XEXP (x
, 2);
6039 fun
= (verbose
) ? "sign_extend" : "sxn";
6040 op
[0] = XEXP (x
, 0);
6043 fun
= (verbose
) ? "zero_extend" : "zxn";
6044 op
[0] = XEXP (x
, 0);
6047 fun
= (verbose
) ? "float_extend" : "fxn";
6048 op
[0] = XEXP (x
, 0);
6051 fun
= (verbose
) ? "trunc" : "trn";
6052 op
[0] = XEXP (x
, 0);
6054 case FLOAT_TRUNCATE
:
6055 fun
= (verbose
) ? "float_trunc" : "ftr";
6056 op
[0] = XEXP (x
, 0);
6059 fun
= (verbose
) ? "float" : "flt";
6060 op
[0] = XEXP (x
, 0);
6062 case UNSIGNED_FLOAT
:
6063 fun
= (verbose
) ? "uns_float" : "ufl";
6064 op
[0] = XEXP (x
, 0);
6068 op
[0] = XEXP (x
, 0);
6071 fun
= (verbose
) ? "uns_fix" : "ufx";
6072 op
[0] = XEXP (x
, 0);
6076 op
[0] = XEXP (x
, 0);
6080 op
[0] = XEXP (x
, 0);
6083 op
[0] = XEXP (x
, 0);
6087 op
[0] = XEXP (x
, 0);
6092 op
[0] = XEXP (x
, 0);
6096 op
[1] = XEXP (x
, 1);
6101 op
[0] = XEXP (x
, 0);
6103 op
[1] = XEXP (x
, 1);
6105 op
[2] = XEXP (x
, 2);
6110 op
[0] = TRAP_CONDITION (x
);
6113 case UNSPEC_VOLATILE
:
6115 cur
= safe_concat (buf
, cur
, "unspec");
6116 if (GET_CODE (x
) == UNSPEC_VOLATILE
)
6117 cur
= safe_concat (buf
, cur
, "/v");
6118 cur
= safe_concat (buf
, cur
, "[");
6120 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6122 print_pattern (tmp
, XVECEXP (x
, 0, i
), verbose
);
6123 cur
= safe_concat (buf
, cur
, sep
);
6124 cur
= safe_concat (buf
, cur
, tmp
);
6127 cur
= safe_concat (buf
, cur
, "] ");
6128 sprintf (tmp
, "%d", XINT (x
, 1));
6129 cur
= safe_concat (buf
, cur
, tmp
);
6133 /* if (verbose) debug_rtx (x); */
6134 st
[0] = GET_RTX_NAME (GET_CODE (x
));
6138 /* Print this as a function? */
6141 cur
= safe_concat (buf
, cur
, fun
);
6142 cur
= safe_concat (buf
, cur
, "(");
6145 for (i
= 0; i
< 4; i
++)
6148 cur
= safe_concat (buf
, cur
, st
[i
]);
6153 cur
= safe_concat (buf
, cur
, ",");
6155 print_value (tmp
, op
[i
], verbose
);
6156 cur
= safe_concat (buf
, cur
, tmp
);
6161 cur
= safe_concat (buf
, cur
, ")");
6164 /* Prints rtxes, i customly classified as values. They're constants, */
6165 /* registers, labels, symbols and memory accesses. */
6168 print_value (buf
, x
, verbose
)
6176 switch (GET_CODE (x
))
6179 sprintf (t
, HOST_WIDE_INT_PRINT_HEX
, INTVAL (x
));
6180 cur
= safe_concat (buf
, cur
, t
);
6183 sprintf (t
, "<0x%lx,0x%lx>", (long)XWINT (x
, 2), (long)XWINT (x
, 3));
6184 cur
= safe_concat (buf
, cur
, t
);
6187 cur
= safe_concat (buf
, cur
, "\"");
6188 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
6189 cur
= safe_concat (buf
, cur
, "\"");
6192 cur
= safe_concat (buf
, cur
, "`");
6193 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
6194 cur
= safe_concat (buf
, cur
, "'");
6197 sprintf (t
, "L%d", INSN_UID (XEXP (x
, 0)));
6198 cur
= safe_concat (buf
, cur
, t
);
6201 print_value (t
, XEXP (x
, 0), verbose
);
6202 cur
= safe_concat (buf
, cur
, "const(");
6203 cur
= safe_concat (buf
, cur
, t
);
6204 cur
= safe_concat (buf
, cur
, ")");
6207 print_value (t
, XEXP (x
, 0), verbose
);
6208 cur
= safe_concat (buf
, cur
, "high(");
6209 cur
= safe_concat (buf
, cur
, t
);
6210 cur
= safe_concat (buf
, cur
, ")");
6213 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
)
6215 int c
= reg_names
[ REGNO (x
) ][0];
6216 if (c
>= '0' && c
<= '9')
6217 cur
= safe_concat (buf
, cur
, "%");
6219 cur
= safe_concat (buf
, cur
, reg_names
[ REGNO (x
) ]);
6223 sprintf (t
, "r%d", REGNO (x
));
6224 cur
= safe_concat (buf
, cur
, t
);
6228 print_value (t
, SUBREG_REG (x
), verbose
);
6229 cur
= safe_concat (buf
, cur
, t
);
6230 sprintf (t
, "#%d", SUBREG_WORD (x
));
6231 cur
= safe_concat (buf
, cur
, t
);
6234 cur
= safe_concat (buf
, cur
, "scratch");
6237 cur
= safe_concat (buf
, cur
, "cc0");
6240 cur
= safe_concat (buf
, cur
, "pc");
6243 print_value (t
, XEXP (x
, 0), verbose
);
6244 cur
= safe_concat (buf
, cur
, "[");
6245 cur
= safe_concat (buf
, cur
, t
);
6246 cur
= safe_concat (buf
, cur
, "]");
6249 print_exp (t
, x
, verbose
);
6250 cur
= safe_concat (buf
, cur
, t
);
6255 /* The next step in insn detalization, its pattern recognition */
6258 print_pattern (buf
, x
, verbose
)
6263 char t1
[BUF_LEN
], t2
[BUF_LEN
], t3
[BUF_LEN
];
6265 switch (GET_CODE (x
))
6268 print_value (t1
, SET_DEST (x
), verbose
);
6269 print_value (t2
, SET_SRC (x
), verbose
);
6270 sprintf (buf
, "%s=%s", t1
, t2
);
6273 sprintf (buf
, "return");
6276 print_exp (buf
, x
, verbose
);
6279 print_value (t1
, XEXP (x
, 0), verbose
);
6280 sprintf (buf
, "clobber %s", t1
);
6283 print_value (t1
, XEXP (x
, 0), verbose
);
6284 sprintf (buf
, "use %s", t1
);
6291 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6293 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6294 sprintf (t3
, "%s%s;", t1
, t2
);
6297 sprintf (buf
, "%s}", t1
);
6304 sprintf (t1
, "%%{");
6305 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6307 print_insn (t2
, XVECEXP (x
, 0, i
), verbose
);
6308 sprintf (t3
, "%s%s;", t1
, t2
);
6311 sprintf (buf
, "%s%%}", t1
);
6315 sprintf (buf
, "asm {%s}", XSTR (x
, 0));
6320 print_value (buf
, XEXP (x
, 0), verbose
);
6323 print_value (t1
, TRAP_CONDITION (x
), verbose
);
6324 sprintf (buf
, "trap_if %s", t1
);
6330 sprintf (t1
, "unspec{");
6331 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6333 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6334 sprintf (t3
, "%s%s;", t1
, t2
);
6337 sprintf (buf
, "%s}", t1
);
6340 case UNSPEC_VOLATILE
:
6344 sprintf (t1
, "unspec/v{");
6345 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6347 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6348 sprintf (t3
, "%s%s;", t1
, t2
);
6351 sprintf (buf
, "%s}", t1
);
6355 print_value (buf
, x
, verbose
);
6357 } /* print_pattern */
6359 /* This is the main function in rtl visualization mechanism. It
6360 accepts an rtx and tries to recognize it as an insn, then prints it
6361 properly in human readable form, resembling assembler mnemonics. */
6362 /* For every insn it prints its UID and BB the insn belongs */
6363 /* too. (probably the last "option" should be extended somehow, since */
6364 /* it depends now on sched.c inner variables ...) */
6367 print_insn (buf
, x
, verbose
)
6375 switch (GET_CODE (x
))
6378 print_pattern (t
, PATTERN (x
), verbose
);
6380 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (x
),
6383 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
6386 print_pattern (t
, PATTERN (x
), verbose
);
6388 sprintf (buf
, "b%d: i% 4d: jump %s", INSN_BB (x
),
6391 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
6395 if (GET_CODE (x
) == PARALLEL
)
6397 x
= XVECEXP (x
, 0, 0);
6398 print_pattern (t
, x
, verbose
);
6401 strcpy (t
, "call <...>");
6403 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (insn
),
6404 INSN_UID (insn
), t
);
6406 sprintf (buf
, "%-4d %s", INSN_UID (insn
), t
);
6409 sprintf (buf
, "L%d:", INSN_UID (x
));
6412 sprintf (buf
, "i% 4d: barrier", INSN_UID (x
));
6415 if (NOTE_LINE_NUMBER (x
) > 0)
6416 sprintf (buf
, "%4d note \"%s\" %d", INSN_UID (x
),
6417 NOTE_SOURCE_FILE (x
), NOTE_LINE_NUMBER (x
));
6419 sprintf (buf
, "%4d %s", INSN_UID (x
),
6420 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x
)));
6425 sprintf (buf
, "Not an INSN at all\n");
6429 sprintf (buf
, "i%-4d <What?>", INSN_UID (x
));
6433 /* Print visualization debugging info */
6436 print_block_visualization (b
, s
)
6443 fprintf (dump
, "\n;; ==================== scheduling visualization for block %d %s \n", b
, s
);
6445 /* Print names of units */
6446 fprintf (dump
, ";; %-8s", "clock");
6447 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6448 if (function_units
[unit
].bitmask
& target_units
)
6449 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6450 fprintf (dump
, " %-33s", function_units
[unit
].name
);
6451 fprintf (dump
, " %-8s\n", "no-unit");
6453 fprintf (dump
, ";; %-8s", "=====");
6454 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6455 if (function_units
[unit
].bitmask
& target_units
)
6456 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6457 fprintf (dump
, " %-33s", "==============================");
6458 fprintf (dump
, " %-8s\n", "=======");
6460 /* Print insns in each cycle */
6461 fprintf (dump
, "%s\n", visual_tbl
);
6464 /* Print insns in the 'no_unit' column of visualization */
6467 visualize_no_unit (insn
)
6470 vis_no_unit
[n_vis_no_unit
] = insn
;
6474 /* Print insns scheduled in clock, for visualization. */
6477 visualize_scheduled_insns (b
, clock
)
6482 /* if no more room, split table into two */
6483 if (n_visual_lines
>= MAX_VISUAL_LINES
)
6485 print_block_visualization (b
, "(incomplete)");
6486 init_block_visualization ();
6491 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; %-8d", clock
);
6492 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6493 if (function_units
[unit
].bitmask
& target_units
)
6494 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6496 int instance
= unit
+ i
* FUNCTION_UNITS_SIZE
;
6497 rtx insn
= unit_last_insn
[instance
];
6499 /* print insns that still keep the unit busy */
6501 actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
6504 print_insn (str
, insn
, 0);
6505 str
[INSN_LEN
] = '\0';
6506 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", str
);
6509 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", "------------------------------");
6512 /* print insns that are not assigned to any unit */
6513 for (i
= 0; i
< n_vis_no_unit
; i
++)
6514 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-8d",
6515 INSN_UID (vis_no_unit
[i
]));
6518 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
6521 /* Print stalled cycles */
6524 visualize_stall_cycles (b
, stalls
)
6529 /* if no more room, split table into two */
6530 if (n_visual_lines
>= MAX_VISUAL_LINES
)
6532 print_block_visualization (b
, "(incomplete)");
6533 init_block_visualization ();
6538 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; ");
6539 for (i
= 0; i
< stalls
; i
++)
6540 sprintf (visual_tbl
+ strlen (visual_tbl
), ".");
6541 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
6544 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn */
6547 move_insn1 (insn
, last
)
6550 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
6551 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
6553 NEXT_INSN (insn
) = NEXT_INSN (last
);
6554 PREV_INSN (NEXT_INSN (last
)) = insn
;
6556 NEXT_INSN (last
) = insn
;
6557 PREV_INSN (insn
) = last
;
6562 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
6563 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
6564 NOTEs. The REG_DEAD note following first one is contains the saved
6565 value for NOTE_BLOCK_NUMBER which is useful for
6566 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
6567 output by the instruction scheduler. Return the new value of LAST. */
6570 reemit_notes (insn
, last
)
6577 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
6579 if (REG_NOTE_KIND (note
) == REG_DEAD
6580 && GET_CODE (XEXP (note
, 0)) == CONST_INT
)
6582 int note_type
= INTVAL (XEXP (note
, 0));
6583 if (note_type
== NOTE_INSN_SETJMP
)
6585 retval
= emit_note_after (NOTE_INSN_SETJMP
, insn
);
6586 CONST_CALL_P (retval
) = CONST_CALL_P (note
);
6587 remove_note (insn
, note
);
6588 note
= XEXP (note
, 1);
6590 else if (note_type
== NOTE_INSN_RANGE_START
6591 || note_type
== NOTE_INSN_RANGE_END
)
6593 last
= emit_note_before (note_type
, last
);
6594 remove_note (insn
, note
);
6595 note
= XEXP (note
, 1);
6596 NOTE_RANGE_INFO (last
) = XEXP (note
, 0);
6600 last
= emit_note_before (INTVAL (XEXP (note
, 0)), last
);
6601 remove_note (insn
, note
);
6602 note
= XEXP (note
, 1);
6603 NOTE_BLOCK_NUMBER (last
) = INTVAL (XEXP (note
, 0));
6605 remove_note (insn
, note
);
6611 /* Move INSN, and all insns which should be issued before it,
6612 due to SCHED_GROUP_P flag. Reemit notes if needed.
6614 Return the last insn emitted by the scheduler, which is the
6615 return value from the first call to reemit_notes. */
6618 move_insn (insn
, last
)
6623 /* If INSN has SCHED_GROUP_P set, then issue it and any other
6624 insns with SCHED_GROUP_P set first. */
6625 while (SCHED_GROUP_P (insn
))
6627 rtx prev
= PREV_INSN (insn
);
6629 /* Move a SCHED_GROUP_P insn. */
6630 move_insn1 (insn
, last
);
6631 /* If this is the first call to reemit_notes, then record
6632 its return value. */
6633 if (retval
== NULL_RTX
)
6634 retval
= reemit_notes (insn
, insn
);
6636 reemit_notes (insn
, insn
);
6640 /* Now move the first non SCHED_GROUP_P insn. */
6641 move_insn1 (insn
, last
);
6643 /* If this is the first call to reemit_notes, then record
6644 its return value. */
6645 if (retval
== NULL_RTX
)
6646 retval
= reemit_notes (insn
, insn
);
6648 reemit_notes (insn
, insn
);
6653 /* Return an insn which represents a SCHED_GROUP, which is
6654 the last insn in the group. */
6665 insn
= next_nonnote_insn (insn
);
6667 while (insn
&& SCHED_GROUP_P (insn
) && (GET_CODE (insn
) != CODE_LABEL
));
6672 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
6673 possibly bringing insns from subsequent blocks in the same region.
6674 Return number of insns scheduled. */
6677 schedule_block (bb
, rgn_n_insns
)
6681 /* Local variables. */
6688 /* flow block of this bb */
6689 int b
= BB_TO_BLOCK (bb
);
6691 /* target_n_insns == number of insns in b before scheduling starts.
6692 sched_target_n_insns == how many of b's insns were scheduled.
6693 sched_n_insns == how many insns were scheduled in b */
6694 int target_n_insns
= 0;
6695 int sched_target_n_insns
= 0;
6696 int sched_n_insns
= 0;
6698 #define NEED_NOTHING 0
6703 /* head/tail info for this block */
6710 /* We used to have code to avoid getting parameters moved from hard
6711 argument registers into pseudos.
6713 However, it was removed when it proved to be of marginal benefit
6714 and caused problems because schedule_block and compute_forward_dependences
6715 had different notions of what the "head" insn was. */
6716 get_block_head_tail (bb
, &head
, &tail
);
6718 /* Interblock scheduling could have moved the original head insn from this
6719 block into a proceeding block. This may also cause schedule_block and
6720 compute_forward_dependences to have different notions of what the
6723 If the interblock movement happened to make this block start with
6724 some notes (LOOP, EH or SETJMP) before the first real insn, then
6725 HEAD will have various special notes attached to it which must be
6726 removed so that we don't end up with extra copies of the notes. */
6727 if (GET_RTX_CLASS (GET_CODE (head
)) == 'i')
6731 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
6732 if (REG_NOTE_KIND (note
) == REG_DEAD
6733 && GET_CODE (XEXP (note
, 0)) == CONST_INT
)
6734 remove_note (head
, note
);
6737 next_tail
= NEXT_INSN (tail
);
6738 prev_head
= PREV_INSN (head
);
6740 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6741 to schedule this block. */
6743 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6744 return (sched_n_insns
);
6749 fprintf (dump
, ";; ======================================================\n");
6751 ";; -- basic block %d from %d to %d -- %s reload\n",
6752 b
, INSN_UID (BLOCK_HEAD (b
)), INSN_UID (BLOCK_END (b
)),
6753 (reload_completed
? "after" : "before"));
6754 fprintf (dump
, ";; ======================================================\n");
6755 fprintf (dump
, "\n");
6757 visual_tbl
= (char *) alloca (get_visual_tbl_length ());
6758 init_block_visualization ();
6761 /* remove remaining note insns from the block, save them in
6762 note_list. These notes are restored at the end of
6763 schedule_block (). */
6765 rm_other_notes (head
, tail
);
6769 /* prepare current target block info */
6770 if (current_nr_blocks
> 1)
6772 candidate_table
= (candidate
*) alloca (current_nr_blocks
* sizeof (candidate
));
6775 /* ??? It is not clear why bblst_size is computed this way. The original
6776 number was clearly too small as it resulted in compiler failures.
6777 Multiplying by the original number by 2 (to account for update_bbs
6778 members) seems to be a reasonable solution. */
6779 /* ??? Or perhaps there is a bug somewhere else in this file? */
6780 bblst_size
= (current_nr_blocks
- bb
) * rgn_nr_edges
* 2;
6781 bblst_table
= (int *) alloca (bblst_size
* sizeof (int));
6783 bitlst_table_last
= 0;
6784 bitlst_table_size
= rgn_nr_edges
;
6785 bitlst_table
= (int *) alloca (rgn_nr_edges
* sizeof (int));
6787 compute_trg_info (bb
);
6792 /* Allocate the ready list */
6793 ready
= (rtx
*) alloca ((rgn_n_insns
+ 1) * sizeof (rtx
));
6795 /* Print debugging information. */
6796 if (sched_verbose
>= 5)
6797 debug_dependencies ();
6800 /* Initialize ready list with all 'ready' insns in target block.
6801 Count number of insns in the target block being scheduled. */
6803 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
6807 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6809 next
= NEXT_INSN (insn
);
6811 if (INSN_DEP_COUNT (insn
) == 0
6812 && (SCHED_GROUP_P (next
) == 0 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
6813 ready
[n_ready
++] = insn
;
6814 if (!(SCHED_GROUP_P (insn
)))
6818 /* Add to ready list all 'ready' insns in valid source blocks.
6819 For speculative insns, check-live, exception-free, and
6821 for (bb_src
= bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
6822 if (IS_VALID (bb_src
))
6828 get_block_head_tail (bb_src
, &head
, &tail
);
6829 src_next_tail
= NEXT_INSN (tail
);
6833 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6836 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
6838 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6841 if (!CANT_MOVE (insn
)
6842 && (!IS_SPECULATIVE_INSN (insn
)
6843 || (insn_issue_delay (insn
) <= 3
6844 && check_live (insn
, bb_src
)
6845 && is_exception_free (insn
, bb_src
, target_bb
))))
6850 next
= NEXT_INSN (insn
);
6851 if (INSN_DEP_COUNT (insn
) == 0
6852 && (SCHED_GROUP_P (next
) == 0
6853 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
6854 ready
[n_ready
++] = insn
;
6859 #ifdef MD_SCHED_INIT
6860 MD_SCHED_INIT (dump
, sched_verbose
);
6863 /* no insns scheduled in this block yet */
6864 last_scheduled_insn
= 0;
6866 /* Sort the ready list */
6867 SCHED_SORT (ready
, n_ready
);
6868 #ifdef MD_SCHED_REORDER
6869 MD_SCHED_REORDER (dump
, sched_verbose
, ready
, n_ready
);
6872 if (sched_verbose
>= 2)
6874 fprintf (dump
, ";;\t\tReady list initially: ");
6875 debug_ready_list (ready
, n_ready
);
6878 /* Q_SIZE is the total number of insns in the queue. */
6883 bzero ((char *) insn_queue
, sizeof (insn_queue
));
6885 /* We start inserting insns after PREV_HEAD. */
6888 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6889 new_needs
= (NEXT_INSN (prev_head
) == BLOCK_HEAD (b
)
6890 ? NEED_HEAD
: NEED_NOTHING
);
6891 if (PREV_INSN (next_tail
) == BLOCK_END (b
))
6892 new_needs
|= NEED_TAIL
;
6894 /* loop until all the insns in BB are scheduled. */
6895 while (sched_target_n_insns
< target_n_insns
)
6901 /* Add to the ready list all pending insns that can be issued now.
6902 If there are no ready insns, increment clock until one
6903 is ready and add all pending insns at that point to the ready
6905 n_ready
= queue_to_ready (ready
, n_ready
);
6910 if (sched_verbose
>= 2)
6912 fprintf (dump
, ";;\t\tReady list after queue_to_ready: ");
6913 debug_ready_list (ready
, n_ready
);
6916 /* Sort the ready list. */
6917 SCHED_SORT (ready
, n_ready
);
6918 #ifdef MD_SCHED_REORDER
6919 MD_SCHED_REORDER (dump
, sched_verbose
, ready
, n_ready
);
6924 fprintf (dump
, "\n;;\tReady list (t =%3d): ", clock_var
);
6925 debug_ready_list (ready
, n_ready
);
6928 /* Issue insns from ready list.
6929 It is important to count down from n_ready, because n_ready may change
6930 as insns are issued. */
6931 can_issue_more
= issue_rate
;
6932 for (i
= n_ready
- 1; i
>= 0 && can_issue_more
; i
--)
6934 rtx insn
= ready
[i
];
6935 int cost
= actual_hazard (insn_unit (insn
), insn
, clock_var
, 0);
6939 queue_insn (insn
, cost
);
6940 ready
[i
] = ready
[--n_ready
]; /* remove insn from ready list */
6944 /* an interblock motion? */
6945 if (INSN_BB (insn
) != target_bb
)
6949 if (IS_SPECULATIVE_INSN (insn
))
6952 if (!check_live (insn
, INSN_BB (insn
)))
6954 /* speculative motion, live check failed, remove
6955 insn from ready list */
6956 ready
[i
] = ready
[--n_ready
];
6959 update_live (insn
, INSN_BB (insn
));
6961 /* for speculative load, mark insns fed by it. */
6962 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
6963 set_spec_fed (insn
);
6970 while (SCHED_GROUP_P (temp
))
6971 temp
= PREV_INSN (temp
);
6973 /* Update source block boundaries. */
6974 b1
= INSN_BLOCK (temp
);
6975 if (temp
== BLOCK_HEAD (b1
)
6976 && insn
== BLOCK_END (b1
))
6978 /* We moved all the insns in the basic block.
6979 Emit a note after the last insn and update the
6980 begin/end boundaries to point to the note. */
6981 emit_note_after (NOTE_INSN_DELETED
, insn
);
6982 BLOCK_END (b1
) = NEXT_INSN (insn
);
6983 BLOCK_HEAD (b1
) = NEXT_INSN (insn
);
6985 else if (insn
== BLOCK_END (b1
))
6987 /* We took insns from the end of the basic block,
6988 so update the end of block boundary so that it
6989 points to the first insn we did not move. */
6990 BLOCK_END (b1
) = PREV_INSN (temp
);
6992 else if (temp
== BLOCK_HEAD (b1
))
6994 /* We took insns from the start of the basic block,
6995 so update the start of block boundary so that
6996 it points to the first insn we did not move. */
6997 BLOCK_HEAD (b1
) = NEXT_INSN (insn
);
7002 /* in block motion */
7003 sched_target_n_insns
++;
7006 last_scheduled_insn
= insn
;
7007 last
= move_insn (insn
, last
);
7010 #ifdef MD_SCHED_VARIABLE_ISSUE
7011 MD_SCHED_VARIABLE_ISSUE (dump
, sched_verbose
, insn
, can_issue_more
);
7016 n_ready
= schedule_insn (insn
, ready
, n_ready
, clock_var
);
7018 /* remove insn from ready list */
7019 ready
[i
] = ready
[--n_ready
];
7021 /* close this block after scheduling its jump */
7022 if (GET_CODE (last_scheduled_insn
) == JUMP_INSN
)
7030 visualize_scheduled_insns (b
, clock_var
);
7037 fprintf (dump
, ";;\tReady list (final): ");
7038 debug_ready_list (ready
, n_ready
);
7039 print_block_visualization (b
, "");
7042 /* Sanity check -- queue must be empty now. Meaningless if region has
7044 if (current_nr_blocks
> 1)
7045 if (!flag_schedule_interblock
&& q_size
!= 0)
7048 /* update head/tail boundaries. */
7049 head
= NEXT_INSN (prev_head
);
7052 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
7053 previously found among the insns. Insert them at the beginning
7057 rtx note_head
= note_list
;
7059 while (PREV_INSN (note_head
))
7061 note_head
= PREV_INSN (note_head
);
7064 PREV_INSN (note_head
) = PREV_INSN (head
);
7065 NEXT_INSN (PREV_INSN (head
)) = note_head
;
7066 PREV_INSN (head
) = note_list
;
7067 NEXT_INSN (note_list
) = head
;
7071 /* update target block boundaries. */
7072 if (new_needs
& NEED_HEAD
)
7073 BLOCK_HEAD (b
) = head
;
7075 if (new_needs
& NEED_TAIL
)
7076 BLOCK_END (b
) = tail
;
7081 fprintf (dump
, ";; total time = %d\n;; new basic block head = %d\n",
7082 clock_var
, INSN_UID (BLOCK_HEAD (b
)));
7083 fprintf (dump
, ";; new basic block end = %d\n\n",
7084 INSN_UID (BLOCK_END (b
)));
7087 return (sched_n_insns
);
7088 } /* schedule_block () */
7091 /* print the bit-set of registers, S. callable from debugger */
7094 debug_reg_vector (s
)
7099 EXECUTE_IF_SET_IN_REG_SET (s
, 0, regno
,
7101 fprintf (dump
, " %d", regno
);
7104 fprintf (dump
, "\n");
7107 /* Use the backward dependences from LOG_LINKS to build
7108 forward dependences in INSN_DEPEND. */
7111 compute_block_forward_dependences (bb
)
7117 enum reg_note dep_type
;
7119 get_block_head_tail (bb
, &head
, &tail
);
7120 next_tail
= NEXT_INSN (tail
);
7121 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
7123 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
7126 insn
= group_leader (insn
);
7128 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
7130 rtx x
= group_leader (XEXP (link
, 0));
7133 if (x
!= XEXP (link
, 0))
7136 /* Ignore dependences upon deleted insn */
7137 if (GET_CODE (x
) == NOTE
|| INSN_DELETED_P (x
))
7139 if (find_insn_list (insn
, INSN_DEPEND (x
)))
7142 new_link
= alloc_INSN_LIST (insn
, INSN_DEPEND (x
));
7144 dep_type
= REG_NOTE_KIND (link
);
7145 PUT_REG_NOTE_KIND (new_link
, dep_type
);
7147 INSN_DEPEND (x
) = new_link
;
7148 INSN_DEP_COUNT (insn
) += 1;
7153 /* Initialize variables for region data dependence analysis.
7154 n_bbs is the number of region blocks */
7156 __inline
static void
7157 init_rgn_data_dependences (n_bbs
)
7162 /* variables for which one copy exists for each block */
7163 bzero ((char *) bb_pending_read_insns
, n_bbs
* sizeof (rtx
));
7164 bzero ((char *) bb_pending_read_mems
, n_bbs
* sizeof (rtx
));
7165 bzero ((char *) bb_pending_write_insns
, n_bbs
* sizeof (rtx
));
7166 bzero ((char *) bb_pending_write_mems
, n_bbs
* sizeof (rtx
));
7167 bzero ((char *) bb_pending_lists_length
, n_bbs
* sizeof (rtx
));
7168 bzero ((char *) bb_last_pending_memory_flush
, n_bbs
* sizeof (rtx
));
7169 bzero ((char *) bb_last_function_call
, n_bbs
* sizeof (rtx
));
7170 bzero ((char *) bb_sched_before_next_call
, n_bbs
* sizeof (rtx
));
7172 /* Create an insn here so that we can hang dependencies off of it later. */
7173 for (bb
= 0; bb
< n_bbs
; bb
++)
7175 bb_sched_before_next_call
[bb
] =
7176 gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
7177 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
7178 LOG_LINKS (bb_sched_before_next_call
[bb
]) = 0;
7182 /* Add dependences so that branches are scheduled to run last in their block */
7185 add_branch_dependences (head
, tail
)
7191 /* For all branches, calls, uses, and cc0 setters, force them to remain
7192 in order at the end of the block by adding dependencies and giving
7193 the last a high priority. There may be notes present, and prev_head
7196 Branches must obviously remain at the end. Calls should remain at the
7197 end since moving them results in worse register allocation. Uses remain
7198 at the end to ensure proper register allocation. cc0 setters remaim
7199 at the end because they can't be moved away from their cc0 user. */
7202 while (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
7203 || (GET_CODE (insn
) == INSN
7204 && (GET_CODE (PATTERN (insn
)) == USE
7206 || sets_cc0_p (PATTERN (insn
))
7209 || GET_CODE (insn
) == NOTE
)
7211 if (GET_CODE (insn
) != NOTE
)
7214 && !find_insn_list (insn
, LOG_LINKS (last
)))
7216 add_dependence (last
, insn
, REG_DEP_ANTI
);
7217 INSN_REF_COUNT (insn
)++;
7220 CANT_MOVE (insn
) = 1;
7223 /* Skip over insns that are part of a group.
7224 Make each insn explicitly depend on the previous insn.
7225 This ensures that only the group header will ever enter
7226 the ready queue (and, when scheduled, will automatically
7227 schedule the SCHED_GROUP_P block). */
7228 while (SCHED_GROUP_P (insn
))
7230 rtx temp
= prev_nonnote_insn (insn
);
7231 add_dependence (insn
, temp
, REG_DEP_ANTI
);
7236 /* Don't overrun the bounds of the basic block. */
7240 insn
= PREV_INSN (insn
);
7243 /* make sure these insns are scheduled last in their block */
7246 while (insn
!= head
)
7248 insn
= prev_nonnote_insn (insn
);
7250 if (INSN_REF_COUNT (insn
) != 0)
7253 if (!find_insn_list (last
, LOG_LINKS (insn
)))
7254 add_dependence (last
, insn
, REG_DEP_ANTI
);
7255 INSN_REF_COUNT (insn
) = 1;
7257 /* Skip over insns that are part of a group. */
7258 while (SCHED_GROUP_P (insn
))
7259 insn
= prev_nonnote_insn (insn
);
7263 /* Compute bacward dependences inside BB. In a multiple blocks region:
7264 (1) a bb is analyzed after its predecessors, and (2) the lists in
7265 effect at the end of bb (after analyzing for bb) are inherited by
7268 Specifically for reg-reg data dependences, the block insns are
7269 scanned by sched_analyze () top-to-bottom. Two lists are
7270 naintained by sched_analyze (): reg_last_defs[] for register DEFs,
7271 and reg_last_uses[] for register USEs.
7273 When analysis is completed for bb, we update for its successors:
7274 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7275 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7277 The mechanism for computing mem-mem data dependence is very
7278 similar, and the result is interblock dependences in the region. */
7281 compute_block_backward_dependences (bb
)
7287 int max_reg
= max_reg_num ();
7289 b
= BB_TO_BLOCK (bb
);
7291 if (current_nr_blocks
== 1)
7293 reg_last_uses
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7294 reg_last_sets
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7295 reg_last_clobbers
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7297 bzero ((char *) reg_last_uses
, max_reg
* sizeof (rtx
));
7298 bzero ((char *) reg_last_sets
, max_reg
* sizeof (rtx
));
7299 bzero ((char *) reg_last_clobbers
, max_reg
* sizeof (rtx
));
7301 pending_read_insns
= 0;
7302 pending_read_mems
= 0;
7303 pending_write_insns
= 0;
7304 pending_write_mems
= 0;
7305 pending_lists_length
= 0;
7306 last_function_call
= 0;
7307 last_pending_memory_flush
= 0;
7308 sched_before_next_call
7309 = gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
7310 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
7311 LOG_LINKS (sched_before_next_call
) = 0;
7315 reg_last_uses
= bb_reg_last_uses
[bb
];
7316 reg_last_sets
= bb_reg_last_sets
[bb
];
7317 reg_last_clobbers
= bb_reg_last_clobbers
[bb
];
7319 pending_read_insns
= bb_pending_read_insns
[bb
];
7320 pending_read_mems
= bb_pending_read_mems
[bb
];
7321 pending_write_insns
= bb_pending_write_insns
[bb
];
7322 pending_write_mems
= bb_pending_write_mems
[bb
];
7323 pending_lists_length
= bb_pending_lists_length
[bb
];
7324 last_function_call
= bb_last_function_call
[bb
];
7325 last_pending_memory_flush
= bb_last_pending_memory_flush
[bb
];
7327 sched_before_next_call
= bb_sched_before_next_call
[bb
];
7330 /* do the analysis for this block */
7331 get_block_head_tail (bb
, &head
, &tail
);
7332 sched_analyze (head
, tail
);
7333 add_branch_dependences (head
, tail
);
7335 if (current_nr_blocks
> 1)
7338 int b_succ
, bb_succ
;
7340 rtx link_insn
, link_mem
;
7343 /* these lists should point to the right place, for correct freeing later. */
7344 bb_pending_read_insns
[bb
] = pending_read_insns
;
7345 bb_pending_read_mems
[bb
] = pending_read_mems
;
7346 bb_pending_write_insns
[bb
] = pending_write_insns
;
7347 bb_pending_write_mems
[bb
] = pending_write_mems
;
7349 /* bb's structures are inherited by it's successors */
7350 first_edge
= e
= OUT_EDGES (b
);
7354 b_succ
= TO_BLOCK (e
);
7355 bb_succ
= BLOCK_TO_BB (b_succ
);
7357 /* only bbs "below" bb, in the same region, are interesting */
7358 if (CONTAINING_RGN (b
) != CONTAINING_RGN (b_succ
)
7365 for (reg
= 0; reg
< max_reg
; reg
++)
7368 /* reg-last-uses lists are inherited by bb_succ */
7369 for (u
= reg_last_uses
[reg
]; u
; u
= XEXP (u
, 1))
7371 if (find_insn_list (XEXP (u
, 0), (bb_reg_last_uses
[bb_succ
])[reg
]))
7374 (bb_reg_last_uses
[bb_succ
])[reg
]
7375 = alloc_INSN_LIST (XEXP (u
, 0),
7376 (bb_reg_last_uses
[bb_succ
])[reg
]);
7379 /* reg-last-defs lists are inherited by bb_succ */
7380 for (u
= reg_last_sets
[reg
]; u
; u
= XEXP (u
, 1))
7382 if (find_insn_list (XEXP (u
, 0), (bb_reg_last_sets
[bb_succ
])[reg
]))
7385 (bb_reg_last_sets
[bb_succ
])[reg
]
7386 = alloc_INSN_LIST (XEXP (u
, 0),
7387 (bb_reg_last_sets
[bb_succ
])[reg
]);
7390 for (u
= reg_last_clobbers
[reg
]; u
; u
= XEXP (u
, 1))
7392 if (find_insn_list (XEXP (u
, 0), (bb_reg_last_clobbers
[bb_succ
])[reg
]))
7395 (bb_reg_last_clobbers
[bb_succ
])[reg
]
7396 = alloc_INSN_LIST (XEXP (u
, 0),
7397 (bb_reg_last_clobbers
[bb_succ
])[reg
]);
7401 /* mem read/write lists are inherited by bb_succ */
7402 link_insn
= pending_read_insns
;
7403 link_mem
= pending_read_mems
;
7406 if (!(find_insn_mem_list (XEXP (link_insn
, 0), XEXP (link_mem
, 0),
7407 bb_pending_read_insns
[bb_succ
],
7408 bb_pending_read_mems
[bb_succ
])))
7409 add_insn_mem_dependence (&bb_pending_read_insns
[bb_succ
],
7410 &bb_pending_read_mems
[bb_succ
],
7411 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
7412 link_insn
= XEXP (link_insn
, 1);
7413 link_mem
= XEXP (link_mem
, 1);
7416 link_insn
= pending_write_insns
;
7417 link_mem
= pending_write_mems
;
7420 if (!(find_insn_mem_list (XEXP (link_insn
, 0), XEXP (link_mem
, 0),
7421 bb_pending_write_insns
[bb_succ
],
7422 bb_pending_write_mems
[bb_succ
])))
7423 add_insn_mem_dependence (&bb_pending_write_insns
[bb_succ
],
7424 &bb_pending_write_mems
[bb_succ
],
7425 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
7427 link_insn
= XEXP (link_insn
, 1);
7428 link_mem
= XEXP (link_mem
, 1);
7431 /* last_function_call is inherited by bb_succ */
7432 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
7434 if (find_insn_list (XEXP (u
, 0), bb_last_function_call
[bb_succ
]))
7437 bb_last_function_call
[bb_succ
]
7438 = alloc_INSN_LIST (XEXP (u
, 0),
7439 bb_last_function_call
[bb_succ
]);
7442 /* last_pending_memory_flush is inherited by bb_succ */
7443 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
7445 if (find_insn_list (XEXP (u
, 0), bb_last_pending_memory_flush
[bb_succ
]))
7448 bb_last_pending_memory_flush
[bb_succ
]
7449 = alloc_INSN_LIST (XEXP (u
, 0),
7450 bb_last_pending_memory_flush
[bb_succ
]);
7453 /* sched_before_next_call is inherited by bb_succ */
7454 x
= LOG_LINKS (sched_before_next_call
);
7455 for (; x
; x
= XEXP (x
, 1))
7456 add_dependence (bb_sched_before_next_call
[bb_succ
],
7457 XEXP (x
, 0), REG_DEP_ANTI
);
7461 while (e
!= first_edge
);
7464 /* Free up the INSN_LISTs
7466 Note this loop is executed max_reg * nr_regions times. It's first
7467 implementation accounted for over 90% of the calls to free_list.
7468 The list was empty for the vast majority of those calls. On the PA,
7469 not calling free_list in those cases improves -O2 compile times by
7471 for (b
= 0; b
< max_reg
; ++b
)
7473 if (reg_last_clobbers
[b
])
7474 free_list (®_last_clobbers
[b
], &unused_insn_list
);
7475 if (reg_last_sets
[b
])
7476 free_list (®_last_sets
[b
], &unused_insn_list
);
7477 if (reg_last_uses
[b
])
7478 free_list (®_last_uses
[b
], &unused_insn_list
);
7481 /* Assert that we won't need bb_reg_last_* for this block anymore. */
7482 if (current_nr_blocks
> 1)
7484 bb_reg_last_uses
[bb
] = (rtx
*) NULL_RTX
;
7485 bb_reg_last_sets
[bb
] = (rtx
*) NULL_RTX
;
7486 bb_reg_last_clobbers
[bb
] = (rtx
*) NULL_RTX
;
7490 /* Print dependences for debugging, callable from debugger */
7493 debug_dependencies ()
7497 fprintf (dump
, ";; --------------- forward dependences: ------------ \n");
7498 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7506 get_block_head_tail (bb
, &head
, &tail
);
7507 next_tail
= NEXT_INSN (tail
);
7508 fprintf (dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
7509 BB_TO_BLOCK (bb
), bb
);
7511 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7512 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7513 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7514 "----", "----", "--", "---", "----", "----", "--------", "-----");
7515 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
7520 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
7523 fprintf (dump
, ";; %6d ", INSN_UID (insn
));
7524 if (GET_CODE (insn
) == NOTE
)
7526 n
= NOTE_LINE_NUMBER (insn
);
7528 fprintf (dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
7530 fprintf (dump
, "line %d, file %s\n", n
,
7531 NOTE_SOURCE_FILE (insn
));
7534 fprintf (dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
7538 unit
= insn_unit (insn
);
7540 || function_units
[unit
].blockage_range_function
== 0) ? 0 :
7541 function_units
[unit
].blockage_range_function (insn
);
7543 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7544 (SCHED_GROUP_P (insn
) ? "+" : " "),
7548 INSN_DEP_COUNT (insn
),
7549 INSN_PRIORITY (insn
),
7550 insn_cost (insn
, 0, 0),
7551 (int) MIN_BLOCKAGE_COST (range
),
7552 (int) MAX_BLOCKAGE_COST (range
));
7553 insn_print_units (insn
);
7554 fprintf (dump
, "\t: ");
7555 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
7556 fprintf (dump
, "%d ", INSN_UID (XEXP (link
, 0)));
7557 fprintf (dump
, "\n");
7561 fprintf (dump
, "\n");
7564 /* Set_priorities: compute priority of each insn in the block */
7577 get_block_head_tail (bb
, &head
, &tail
);
7578 prev_head
= PREV_INSN (head
);
7581 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
7585 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
7588 if (GET_CODE (insn
) == NOTE
)
7591 if (!(SCHED_GROUP_P (insn
)))
7593 (void) priority (insn
);
7599 /* Make each element of VECTOR point at an rtx-vector,
7600 taking the space for all those rtx-vectors from SPACE.
7601 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7602 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7603 (this is the same as init_regset_vector () in flow.c) */
7606 init_rtx_vector (vector
, space
, nelts
, bytes_per_elt
)
7613 register rtx
*p
= space
;
7615 for (i
= 0; i
< nelts
; i
++)
7618 p
+= bytes_per_elt
/ sizeof (*p
);
7622 /* Schedule a region. A region is either an inner loop, a loop-free
7623 subroutine, or a single basic block. Each bb in the region is
7624 scheduled after its flow predecessors. */
7627 schedule_region (rgn
)
7631 int rgn_n_insns
= 0;
7632 int sched_rgn_n_insns
= 0;
7634 /* set variables for the current region */
7635 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
7636 current_blocks
= RGN_BLOCKS (rgn
);
7638 reg_pending_sets
= ALLOCA_REG_SET ();
7639 reg_pending_clobbers
= ALLOCA_REG_SET ();
7640 reg_pending_sets_all
= 0;
7642 /* initializations for region data dependence analyisis */
7643 if (current_nr_blocks
> 1)
7646 int maxreg
= max_reg_num ();
7648 bb_reg_last_uses
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7649 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7650 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7651 init_rtx_vector (bb_reg_last_uses
, space
, current_nr_blocks
,
7652 maxreg
* sizeof (rtx
*));
7654 bb_reg_last_sets
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7655 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7656 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7657 init_rtx_vector (bb_reg_last_sets
, space
, current_nr_blocks
,
7658 maxreg
* sizeof (rtx
*));
7660 bb_reg_last_clobbers
=
7661 (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7662 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7663 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7664 init_rtx_vector (bb_reg_last_clobbers
, space
, current_nr_blocks
,
7665 maxreg
* sizeof (rtx
*));
7667 bb_pending_read_insns
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7668 bb_pending_read_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7669 bb_pending_write_insns
=
7670 (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7671 bb_pending_write_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7672 bb_pending_lists_length
=
7673 (int *) alloca (current_nr_blocks
* sizeof (int));
7674 bb_last_pending_memory_flush
=
7675 (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7676 bb_last_function_call
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7677 bb_sched_before_next_call
=
7678 (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7680 init_rgn_data_dependences (current_nr_blocks
);
7683 /* compute LOG_LINKS */
7684 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7685 compute_block_backward_dependences (bb
);
7687 /* compute INSN_DEPEND */
7688 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
7689 compute_block_forward_dependences (bb
);
7691 /* Delete line notes, compute live-regs at block end, and set priorities. */
7693 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7695 if (reload_completed
== 0)
7696 find_pre_sched_live (bb
);
7698 if (write_symbols
!= NO_DEBUG
)
7700 save_line_notes (bb
);
7704 rgn_n_insns
+= set_priorities (bb
);
7707 /* compute interblock info: probabilities, split-edges, dominators, etc. */
7708 if (current_nr_blocks
> 1)
7712 prob
= (float *) alloca ((current_nr_blocks
) * sizeof (float));
7714 bbset_size
= current_nr_blocks
/ HOST_BITS_PER_WIDE_INT
+ 1;
7715 dom
= (bbset
*) alloca (current_nr_blocks
* sizeof (bbset
));
7716 for (i
= 0; i
< current_nr_blocks
; i
++)
7718 dom
[i
] = (bbset
) alloca (bbset_size
* sizeof (HOST_WIDE_INT
));
7719 bzero ((char *) dom
[i
], bbset_size
* sizeof (HOST_WIDE_INT
));
7724 edge_to_bit
= (int *) alloca (nr_edges
* sizeof (int));
7725 for (i
= 1; i
< nr_edges
; i
++)
7726 if (CONTAINING_RGN (FROM_BLOCK (i
)) == rgn
)
7727 EDGE_TO_BIT (i
) = rgn_nr_edges
++;
7728 rgn_edges
= (int *) alloca (rgn_nr_edges
* sizeof (int));
7731 for (i
= 1; i
< nr_edges
; i
++)
7732 if (CONTAINING_RGN (FROM_BLOCK (i
)) == (rgn
))
7733 rgn_edges
[rgn_nr_edges
++] = i
;
7736 edgeset_size
= rgn_nr_edges
/ HOST_BITS_PER_WIDE_INT
+ 1;
7737 pot_split
= (edgeset
*) alloca (current_nr_blocks
* sizeof (edgeset
));
7738 ancestor_edges
= (edgeset
*) alloca (current_nr_blocks
* sizeof (edgeset
));
7739 for (i
= 0; i
< current_nr_blocks
; i
++)
7742 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
7743 bzero ((char *) pot_split
[i
],
7744 edgeset_size
* sizeof (HOST_WIDE_INT
));
7746 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
7747 bzero ((char *) ancestor_edges
[i
],
7748 edgeset_size
* sizeof (HOST_WIDE_INT
));
7751 /* compute probabilities, dominators, split_edges */
7752 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7753 compute_dom_prob_ps (bb
);
7756 /* now we can schedule all blocks */
7757 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7759 sched_rgn_n_insns
+= schedule_block (bb
, rgn_n_insns
);
7766 /* sanity check: verify that all region insns were scheduled */
7767 if (sched_rgn_n_insns
!= rgn_n_insns
)
7770 /* update register life and usage information */
7771 if (reload_completed
== 0)
7773 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
7774 find_post_sched_live (bb
);
7776 if (current_nr_blocks
<= 1)
7777 /* Sanity check. There should be no REG_DEAD notes leftover at the end.
7778 In practice, this can occur as the result of bugs in flow, combine.c,
7779 and/or sched.c. The values of the REG_DEAD notes remaining are
7780 meaningless, because dead_notes is just used as a free list. */
7781 if (dead_notes
!= 0)
7785 /* restore line notes. */
7786 if (write_symbols
!= NO_DEBUG
)
7788 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7789 restore_line_notes (bb
);
7792 /* Done with this region */
7793 free_pending_lists ();
7795 FREE_REG_SET (reg_pending_sets
);
7796 FREE_REG_SET (reg_pending_clobbers
);
7799 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
7800 needed for the hard register mentioned in the note. This can happen
7801 if the reference to the hard register in the original insn was split into
7802 several smaller hard register references in the split insns. */
7805 split_hard_reg_notes (note
, first
, last
)
7806 rtx note
, first
, last
;
7808 rtx reg
, temp
, link
;
7809 int n_regs
, i
, new_reg
;
7812 /* Assume that this is a REG_DEAD note. */
7813 if (REG_NOTE_KIND (note
) != REG_DEAD
)
7816 reg
= XEXP (note
, 0);
7818 n_regs
= HARD_REGNO_NREGS (REGNO (reg
), GET_MODE (reg
));
7820 for (i
= 0; i
< n_regs
; i
++)
7822 new_reg
= REGNO (reg
) + i
;
7824 /* Check for references to new_reg in the split insns. */
7825 for (insn
= last
;; insn
= PREV_INSN (insn
))
7827 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7828 && (temp
= regno_use_in (new_reg
, PATTERN (insn
))))
7830 /* Create a new reg dead note ere. */
7831 link
= alloc_EXPR_LIST (REG_DEAD
, temp
, REG_NOTES (insn
));
7832 REG_NOTES (insn
) = link
;
7834 /* If killed multiple registers here, then add in the excess. */
7835 i
+= HARD_REGNO_NREGS (REGNO (temp
), GET_MODE (temp
)) - 1;
7839 /* It isn't mentioned anywhere, so no new reg note is needed for
7847 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
7848 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
7851 new_insn_dead_notes (pat
, insn
, last
, orig_insn
)
7852 rtx pat
, insn
, last
, orig_insn
;
7856 /* PAT is either a CLOBBER or a SET here. */
7857 dest
= XEXP (pat
, 0);
7859 while (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
7860 || GET_CODE (dest
) == STRICT_LOW_PART
7861 || GET_CODE (dest
) == SIGN_EXTRACT
)
7862 dest
= XEXP (dest
, 0);
7864 if (GET_CODE (dest
) == REG
)
7866 /* If the original insn already used this register, we may not add new
7867 notes for it. One example for a split that needs this test is
7868 when a multi-word memory access with register-indirect addressing
7869 is split into multiple memory accesses with auto-increment and
7870 one adjusting add instruction for the address register. */
7871 if (reg_referenced_p (dest
, PATTERN (orig_insn
)))
7873 for (tem
= last
; tem
!= insn
; tem
= PREV_INSN (tem
))
7875 if (GET_RTX_CLASS (GET_CODE (tem
)) == 'i'
7876 && reg_overlap_mentioned_p (dest
, PATTERN (tem
))
7877 && (set
= single_set (tem
)))
7879 rtx tem_dest
= SET_DEST (set
);
7881 while (GET_CODE (tem_dest
) == ZERO_EXTRACT
7882 || GET_CODE (tem_dest
) == SUBREG
7883 || GET_CODE (tem_dest
) == STRICT_LOW_PART
7884 || GET_CODE (tem_dest
) == SIGN_EXTRACT
)
7885 tem_dest
= XEXP (tem_dest
, 0);
7887 if (!rtx_equal_p (tem_dest
, dest
))
7889 /* Use the same scheme as combine.c, don't put both REG_DEAD
7890 and REG_UNUSED notes on the same insn. */
7891 if (!find_regno_note (tem
, REG_UNUSED
, REGNO (dest
))
7892 && !find_regno_note (tem
, REG_DEAD
, REGNO (dest
)))
7894 rtx note
= alloc_EXPR_LIST (REG_DEAD
, dest
,
7896 REG_NOTES (tem
) = note
;
7898 /* The reg only dies in one insn, the last one that uses
7902 else if (reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
7903 /* We found an instruction that both uses the register,
7904 and sets it, so no new REG_NOTE is needed for this set. */
7908 /* If this is a set, it must die somewhere, unless it is the dest of
7909 the original insn, and hence is live after the original insn. Abort
7910 if it isn't supposed to be live after the original insn.
7912 If this is a clobber, then just add a REG_UNUSED note. */
7915 int live_after_orig_insn
= 0;
7916 rtx pattern
= PATTERN (orig_insn
);
7919 if (GET_CODE (pat
) == CLOBBER
)
7921 rtx note
= alloc_EXPR_LIST (REG_UNUSED
, dest
, REG_NOTES (insn
));
7922 REG_NOTES (insn
) = note
;
7926 /* The original insn could have multiple sets, so search the
7927 insn for all sets. */
7928 if (GET_CODE (pattern
) == SET
)
7930 if (reg_overlap_mentioned_p (dest
, SET_DEST (pattern
)))
7931 live_after_orig_insn
= 1;
7933 else if (GET_CODE (pattern
) == PARALLEL
)
7935 for (i
= 0; i
< XVECLEN (pattern
, 0); i
++)
7936 if (GET_CODE (XVECEXP (pattern
, 0, i
)) == SET
7937 && reg_overlap_mentioned_p (dest
,
7938 SET_DEST (XVECEXP (pattern
,
7940 live_after_orig_insn
= 1;
7943 if (!live_after_orig_insn
)
7949 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
7950 registers modified by X. INC is -1 if the containing insn is being deleted,
7951 and is 1 if the containing insn is a newly generated insn. */
7954 update_n_sets (x
, inc
)
7958 rtx dest
= SET_DEST (x
);
7960 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
7961 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
7962 dest
= SUBREG_REG (dest
);
7964 if (GET_CODE (dest
) == REG
)
7966 int regno
= REGNO (dest
);
7968 if (regno
< FIRST_PSEUDO_REGISTER
)
7971 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
7973 for (i
= regno
; i
< endregno
; i
++)
7974 REG_N_SETS (i
) += inc
;
7977 REG_N_SETS (regno
) += inc
;
7981 /* Updates all flow-analysis related quantities (including REG_NOTES) for
7982 the insns from FIRST to LAST inclusive that were created by splitting
7983 ORIG_INSN. NOTES are the original REG_NOTES. */
7986 update_flow_info (notes
, first
, last
, orig_insn
)
7993 rtx orig_dest
, temp
;
7996 /* Get and save the destination set by the original insn. */
7998 orig_dest
= single_set (orig_insn
);
8000 orig_dest
= SET_DEST (orig_dest
);
8002 /* Move REG_NOTES from the original insn to where they now belong. */
8004 for (note
= notes
; note
; note
= next
)
8006 next
= XEXP (note
, 1);
8007 switch (REG_NOTE_KIND (note
))
8011 /* Move these notes from the original insn to the last new insn where
8012 the register is now set. */
8014 for (insn
= last
;; insn
= PREV_INSN (insn
))
8016 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8017 && reg_mentioned_p (XEXP (note
, 0), PATTERN (insn
)))
8019 /* If this note refers to a multiple word hard register, it
8020 may have been split into several smaller hard register
8021 references, so handle it specially. */
8022 temp
= XEXP (note
, 0);
8023 if (REG_NOTE_KIND (note
) == REG_DEAD
8024 && GET_CODE (temp
) == REG
8025 && REGNO (temp
) < FIRST_PSEUDO_REGISTER
8026 && HARD_REGNO_NREGS (REGNO (temp
), GET_MODE (temp
)) > 1)
8027 split_hard_reg_notes (note
, first
, last
);
8030 XEXP (note
, 1) = REG_NOTES (insn
);
8031 REG_NOTES (insn
) = note
;
8034 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
8036 /* ??? This won't handle multiple word registers correctly,
8037 but should be good enough for now. */
8038 if (REG_NOTE_KIND (note
) == REG_UNUSED
8039 && GET_CODE (XEXP (note
, 0)) != SCRATCH
8040 && !dead_or_set_p (insn
, XEXP (note
, 0)))
8041 PUT_REG_NOTE_KIND (note
, REG_DEAD
);
8043 /* The reg only dies in one insn, the last one that uses
8047 /* It must die somewhere, fail it we couldn't find where it died.
8049 If this is a REG_UNUSED note, then it must be a temporary
8050 register that was not needed by this instantiation of the
8051 pattern, so we can safely ignore it. */
8054 if (REG_NOTE_KIND (note
) != REG_UNUSED
)
8063 /* If the insn that set the register to 0 was deleted, this
8064 note cannot be relied on any longer. The destination might
8065 even have been moved to memory.
8066 This was observed for SH4 with execute/920501-6.c compilation,
8067 -O2 -fomit-frame-pointer -finline-functions . */
8068 if (GET_CODE (XEXP (note
, 0)) == NOTE
8069 || INSN_DELETED_P (XEXP (note
, 0)))
8071 /* This note applies to the dest of the original insn. Find the
8072 first new insn that now has the same dest, and move the note
8078 for (insn
= first
;; insn
= NEXT_INSN (insn
))
8080 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8081 && (temp
= single_set (insn
))
8082 && rtx_equal_p (SET_DEST (temp
), orig_dest
))
8084 XEXP (note
, 1) = REG_NOTES (insn
);
8085 REG_NOTES (insn
) = note
;
8086 /* The reg is only zero before one insn, the first that
8090 /* If this note refers to a multiple word hard
8091 register, it may have been split into several smaller
8092 hard register references. We could split the notes,
8093 but simply dropping them is good enough. */
8094 if (GET_CODE (orig_dest
) == REG
8095 && REGNO (orig_dest
) < FIRST_PSEUDO_REGISTER
8096 && HARD_REGNO_NREGS (REGNO (orig_dest
),
8097 GET_MODE (orig_dest
)) > 1)
8099 /* It must be set somewhere, fail if we couldn't find where it
8108 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
8109 set is meaningless. Just drop the note. */
8113 case REG_NO_CONFLICT
:
8114 /* These notes apply to the dest of the original insn. Find the last
8115 new insn that now has the same dest, and move the note there. */
8120 for (insn
= last
;; insn
= PREV_INSN (insn
))
8122 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8123 && (temp
= single_set (insn
))
8124 && rtx_equal_p (SET_DEST (temp
), orig_dest
))
8126 XEXP (note
, 1) = REG_NOTES (insn
);
8127 REG_NOTES (insn
) = note
;
8128 /* Only put this note on one of the new insns. */
8132 /* The original dest must still be set someplace. Abort if we
8133 couldn't find it. */
8136 /* However, if this note refers to a multiple word hard
8137 register, it may have been split into several smaller
8138 hard register references. We could split the notes,
8139 but simply dropping them is good enough. */
8140 if (GET_CODE (orig_dest
) == REG
8141 && REGNO (orig_dest
) < FIRST_PSEUDO_REGISTER
8142 && HARD_REGNO_NREGS (REGNO (orig_dest
),
8143 GET_MODE (orig_dest
)) > 1)
8145 /* Likewise for multi-word memory references. */
8146 if (GET_CODE (orig_dest
) == MEM
8147 && SIZE_FOR_MODE (orig_dest
) > UNITS_PER_WORD
)
8155 /* Move a REG_LIBCALL note to the first insn created, and update
8156 the corresponding REG_RETVAL note. */
8157 XEXP (note
, 1) = REG_NOTES (first
);
8158 REG_NOTES (first
) = note
;
8160 insn
= XEXP (note
, 0);
8161 note
= find_reg_note (insn
, REG_RETVAL
, NULL_RTX
);
8163 XEXP (note
, 0) = first
;
8166 case REG_EXEC_COUNT
:
8167 /* Move a REG_EXEC_COUNT note to the first insn created. */
8168 XEXP (note
, 1) = REG_NOTES (first
);
8169 REG_NOTES (first
) = note
;
8173 /* Move a REG_RETVAL note to the last insn created, and update
8174 the corresponding REG_LIBCALL note. */
8175 XEXP (note
, 1) = REG_NOTES (last
);
8176 REG_NOTES (last
) = note
;
8178 insn
= XEXP (note
, 0);
8179 note
= find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
);
8181 XEXP (note
, 0) = last
;
8186 /* This should be moved to whichever instruction is a JUMP_INSN. */
8188 for (insn
= last
;; insn
= PREV_INSN (insn
))
8190 if (GET_CODE (insn
) == JUMP_INSN
)
8192 XEXP (note
, 1) = REG_NOTES (insn
);
8193 REG_NOTES (insn
) = note
;
8194 /* Only put this note on one of the new insns. */
8197 /* Fail if we couldn't find a JUMP_INSN. */
8204 /* reload sometimes leaves obsolete REG_INC notes around. */
8205 if (reload_completed
)
8207 /* This should be moved to whichever instruction now has the
8208 increment operation. */
8212 /* Should be moved to the new insn(s) which use the label. */
8213 for (insn
= first
; insn
!= NEXT_INSN (last
); insn
= NEXT_INSN (insn
))
8214 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8215 && reg_mentioned_p (XEXP (note
, 0), PATTERN (insn
)))
8217 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_LABEL
,
8225 /* These two notes will never appear until after reorg, so we don't
8226 have to handle them here. */
8232 /* Each new insn created, except the last, has a new set. If the destination
8233 is a register, then this reg is now live across several insns, whereas
8234 previously the dest reg was born and died within the same insn. To
8235 reflect this, we now need a REG_DEAD note on the insn where this
8238 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
8240 for (insn
= first
; insn
!= last
; insn
= NEXT_INSN (insn
))
8245 pat
= PATTERN (insn
);
8246 if (GET_CODE (pat
) == SET
|| GET_CODE (pat
) == CLOBBER
)
8247 new_insn_dead_notes (pat
, insn
, last
, orig_insn
);
8248 else if (GET_CODE (pat
) == PARALLEL
)
8250 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
8251 if (GET_CODE (XVECEXP (pat
, 0, i
)) == SET
8252 || GET_CODE (XVECEXP (pat
, 0, i
)) == CLOBBER
)
8253 new_insn_dead_notes (XVECEXP (pat
, 0, i
), insn
, last
, orig_insn
);
8257 /* If any insn, except the last, uses the register set by the last insn,
8258 then we need a new REG_DEAD note on that insn. In this case, there
8259 would not have been a REG_DEAD note for this register in the original
8260 insn because it was used and set within one insn. */
8262 set
= single_set (last
);
8265 rtx dest
= SET_DEST (set
);
8267 while (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
8268 || GET_CODE (dest
) == STRICT_LOW_PART
8269 || GET_CODE (dest
) == SIGN_EXTRACT
)
8270 dest
= XEXP (dest
, 0);
8272 if (GET_CODE (dest
) == REG
8273 /* Global registers are always live, so the code below does not
8275 && (REGNO (dest
) >= FIRST_PSEUDO_REGISTER
8276 || ! global_regs
[REGNO (dest
)]))
8278 rtx stop_insn
= PREV_INSN (first
);
8280 /* If the last insn uses the register that it is setting, then
8281 we don't want to put a REG_DEAD note there. Search backwards
8282 to find the first insn that sets but does not use DEST. */
8285 if (reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
8287 for (insn
= PREV_INSN (insn
); insn
!= first
;
8288 insn
= PREV_INSN (insn
))
8290 if ((set
= single_set (insn
))
8291 && reg_mentioned_p (dest
, SET_DEST (set
))
8292 && ! reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
8297 /* Now find the first insn that uses but does not set DEST. */
8299 for (insn
= PREV_INSN (insn
); insn
!= stop_insn
;
8300 insn
= PREV_INSN (insn
))
8302 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8303 && reg_mentioned_p (dest
, PATTERN (insn
))
8304 && (set
= single_set (insn
)))
8306 rtx insn_dest
= SET_DEST (set
);
8308 while (GET_CODE (insn_dest
) == ZERO_EXTRACT
8309 || GET_CODE (insn_dest
) == SUBREG
8310 || GET_CODE (insn_dest
) == STRICT_LOW_PART
8311 || GET_CODE (insn_dest
) == SIGN_EXTRACT
)
8312 insn_dest
= XEXP (insn_dest
, 0);
8314 if (insn_dest
!= dest
)
8316 note
= alloc_EXPR_LIST (REG_DEAD
, dest
, REG_NOTES (insn
));
8317 REG_NOTES (insn
) = note
;
8318 /* The reg only dies in one insn, the last one
8327 /* If the original dest is modifying a multiple register target, and the
8328 original instruction was split such that the original dest is now set
8329 by two or more SUBREG sets, then the split insns no longer kill the
8330 destination of the original insn.
8332 In this case, if there exists an instruction in the same basic block,
8333 before the split insn, which uses the original dest, and this use is
8334 killed by the original insn, then we must remove the REG_DEAD note on
8335 this insn, because it is now superfluous.
8337 This does not apply when a hard register gets split, because the code
8338 knows how to handle overlapping hard registers properly. */
8339 if (orig_dest
&& GET_CODE (orig_dest
) == REG
)
8341 int found_orig_dest
= 0;
8342 int found_split_dest
= 0;
8344 for (insn
= first
;; insn
= NEXT_INSN (insn
))
8349 /* I'm not sure if this can happen, but let's be safe. */
8350 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
8353 pat
= PATTERN (insn
);
8354 i
= GET_CODE (pat
) == PARALLEL
? XVECLEN (pat
, 0) : 0;
8359 if (GET_CODE (set
) == SET
)
8361 if (GET_CODE (SET_DEST (set
)) == REG
8362 && REGNO (SET_DEST (set
)) == REGNO (orig_dest
))
8364 found_orig_dest
= 1;
8367 else if (GET_CODE (SET_DEST (set
)) == SUBREG
8368 && SUBREG_REG (SET_DEST (set
)) == orig_dest
)
8370 found_split_dest
= 1;
8376 set
= XVECEXP (pat
, 0, i
);
8383 if (found_split_dest
)
8385 /* Search backwards from FIRST, looking for the first insn that uses
8386 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
8387 If we find an insn, and it has a REG_DEAD note, then delete the
8390 for (insn
= first
; insn
; insn
= PREV_INSN (insn
))
8392 if (GET_CODE (insn
) == CODE_LABEL
8393 || GET_CODE (insn
) == JUMP_INSN
)
8395 else if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8396 && reg_mentioned_p (orig_dest
, insn
))
8398 note
= find_regno_note (insn
, REG_DEAD
, REGNO (orig_dest
));
8400 remove_note (insn
, note
);
8404 else if (!found_orig_dest
)
8408 /* Should never reach here for a pseudo reg. */
8409 if (REGNO (orig_dest
) >= FIRST_PSEUDO_REGISTER
)
8412 /* This can happen for a hard register, if the splitter
8413 does not bother to emit instructions which would be no-ops.
8414 We try to verify that this is the case by checking to see if
8415 the original instruction uses all of the registers that it
8416 set. This case is OK, because deleting a no-op can not affect
8417 REG_DEAD notes on other insns. If this is not the case, then
8420 regno
= REGNO (orig_dest
);
8421 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (orig_dest
)) - 1;
8423 if (! refers_to_regno_p (regno
+ i
, regno
+ i
+ 1, orig_insn
,
8431 /* Update reg_n_sets. This is necessary to prevent local alloc from
8432 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
8433 a reg from set once to set multiple times. */
8436 rtx x
= PATTERN (orig_insn
);
8437 RTX_CODE code
= GET_CODE (x
);
8439 if (code
== SET
|| code
== CLOBBER
)
8440 update_n_sets (x
, -1);
8441 else if (code
== PARALLEL
)
8444 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
8446 code
= GET_CODE (XVECEXP (x
, 0, i
));
8447 if (code
== SET
|| code
== CLOBBER
)
8448 update_n_sets (XVECEXP (x
, 0, i
), -1);
8452 for (insn
= first
;; insn
= NEXT_INSN (insn
))
8455 code
= GET_CODE (x
);
8457 if (code
== SET
|| code
== CLOBBER
)
8458 update_n_sets (x
, 1);
8459 else if (code
== PARALLEL
)
8462 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
8464 code
= GET_CODE (XVECEXP (x
, 0, i
));
8465 if (code
== SET
|| code
== CLOBBER
)
8466 update_n_sets (XVECEXP (x
, 0, i
), 1);
8476 /* The one entry point in this file. DUMP_FILE is the dump file for
8480 schedule_insns (dump_file
)
8491 /* disable speculative loads in their presence if cc0 defined */
8493 flag_schedule_speculative_load
= 0;
8496 /* Taking care of this degenerate case makes the rest of
8497 this code simpler. */
8498 if (n_basic_blocks
== 0)
8501 /* set dump and sched_verbose for the desired debugging output. If no
8502 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
8503 For -fsched-verbose-N, N>=10, print everything to stderr. */
8504 sched_verbose
= sched_verbose_param
;
8505 if (sched_verbose_param
== 0 && dump_file
)
8507 dump
= ((sched_verbose_param
>= 10 || !dump_file
) ? stderr
: dump_file
);
8512 /* Initialize the unused_*_lists. We can't use the ones left over from
8513 the previous function, because gcc has freed that memory. We can use
8514 the ones left over from the first sched pass in the second pass however,
8515 so only clear them on the first sched pass. The first pass is before
8516 reload if flag_schedule_insns is set, otherwise it is afterwards. */
8518 if (reload_completed
== 0 || !flag_schedule_insns
)
8520 unused_insn_list
= 0;
8521 unused_expr_list
= 0;
8524 /* initialize issue_rate */
8525 issue_rate
= ISSUE_RATE
;
8527 /* do the splitting first for all blocks */
8528 for (b
= 0; b
< n_basic_blocks
; b
++)
8529 split_block_insns (b
, 1);
8531 max_uid
= (get_max_uid () + 1);
8533 cant_move
= (char *) xmalloc (max_uid
* sizeof (char));
8534 bzero ((char *) cant_move
, max_uid
* sizeof (char));
8536 fed_by_spec_load
= (char *) xmalloc (max_uid
* sizeof (char));
8537 bzero ((char *) fed_by_spec_load
, max_uid
* sizeof (char));
8539 is_load_insn
= (char *) xmalloc (max_uid
* sizeof (char));
8540 bzero ((char *) is_load_insn
, max_uid
* sizeof (char));
8542 insn_orig_block
= (int *) xmalloc (max_uid
* sizeof (int));
8543 insn_luid
= (int *) xmalloc (max_uid
* sizeof (int));
8546 for (b
= 0; b
< n_basic_blocks
; b
++)
8547 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
8549 INSN_BLOCK (insn
) = b
;
8550 INSN_LUID (insn
) = luid
++;
8552 if (insn
== BLOCK_END (b
))
8556 /* after reload, remove inter-blocks dependences computed before reload. */
8557 if (reload_completed
)
8562 for (b
= 0; b
< n_basic_blocks
; b
++)
8563 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
8567 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
8570 link
= LOG_LINKS (insn
);
8573 rtx x
= XEXP (link
, 0);
8575 if (INSN_BLOCK (x
) != b
)
8577 remove_dependence (insn
, x
);
8578 link
= prev
? XEXP (prev
, 1) : LOG_LINKS (insn
);
8581 prev
= link
, link
= XEXP (prev
, 1);
8585 if (insn
== BLOCK_END (b
))
8591 rgn_table
= (region
*) alloca ((n_basic_blocks
) * sizeof (region
));
8592 rgn_bb_table
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8593 block_to_bb
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8594 containing_rgn
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8596 /* compute regions for scheduling */
8597 if (reload_completed
8598 || n_basic_blocks
== 1
8599 || !flag_schedule_interblock
)
8601 find_single_block_region ();
8605 /* verify that a 'good' control flow graph can be built */
8606 if (is_cfg_nonregular ())
8608 find_single_block_region ();
8612 int_list_ptr
*s_preds
, *s_succs
;
8613 int *num_preds
, *num_succs
;
8614 sbitmap
*dom
, *pdom
;
8616 s_preds
= (int_list_ptr
*) alloca (n_basic_blocks
8617 * sizeof (int_list_ptr
));
8618 s_succs
= (int_list_ptr
*) alloca (n_basic_blocks
8619 * sizeof (int_list_ptr
));
8620 num_preds
= (int *) alloca (n_basic_blocks
* sizeof (int));
8621 num_succs
= (int *) alloca (n_basic_blocks
* sizeof (int));
8622 dom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
8623 pdom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
8625 /* The scheduler runs after flow; therefore, we can't blindly call
8626 back into find_basic_blocks since doing so could invalidate the
8627 info in global_live_at_start.
8629 Consider a block consisting entirely of dead stores; after life
8630 analysis it would be a block of NOTE_INSN_DELETED notes. If
8631 we call find_basic_blocks again, then the block would be removed
8632 entirely and invalidate our the register live information.
8634 We could (should?) recompute register live information. Doing
8635 so may even be beneficial. */
8637 compute_preds_succs (s_preds
, s_succs
, num_preds
, num_succs
);
8639 /* Compute the dominators and post dominators. We don't currently use
8640 post dominators, but we should for speculative motion analysis. */
8641 compute_dominators (dom
, pdom
, s_preds
, s_succs
);
8643 /* build_control_flow will return nonzero if it detects unreachable
8644 blocks or any other irregularity with the cfg which prevents
8645 cross block scheduling. */
8646 if (build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
) != 0)
8647 find_single_block_region ();
8649 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
);
8651 if (sched_verbose
>= 3)
8654 /* For now. This will move as more and more of haifa is converted
8655 to using the cfg code in flow.c */
8662 /* Allocate data for this pass. See comments, above,
8663 for what these vectors do.
8665 We use xmalloc instead of alloca, because max_uid can be very large
8666 when there is a lot of function inlining. If we used alloca, we could
8667 exceed stack limits on some hosts for some inputs. */
8668 insn_priority
= (int *) xmalloc (max_uid
* sizeof (int));
8669 insn_reg_weight
= (int *) xmalloc (max_uid
* sizeof (int));
8670 insn_tick
= (int *) xmalloc (max_uid
* sizeof (int));
8671 insn_costs
= (short *) xmalloc (max_uid
* sizeof (short));
8672 insn_units
= (short *) xmalloc (max_uid
* sizeof (short));
8673 insn_blockage
= (unsigned int *) xmalloc (max_uid
* sizeof (unsigned int));
8674 insn_ref_count
= (int *) xmalloc (max_uid
* sizeof (int));
8676 /* Allocate for forward dependencies */
8677 insn_dep_count
= (int *) xmalloc (max_uid
* sizeof (int));
8678 insn_depend
= (rtx
*) xmalloc (max_uid
* sizeof (rtx
));
8680 if (reload_completed
== 0)
8684 sched_reg_n_calls_crossed
= (int *) alloca (max_regno
* sizeof (int));
8685 sched_reg_live_length
= (int *) alloca (max_regno
* sizeof (int));
8686 sched_reg_basic_block
= (int *) alloca (max_regno
* sizeof (int));
8687 bb_live_regs
= ALLOCA_REG_SET ();
8688 bzero ((char *) sched_reg_n_calls_crossed
, max_regno
* sizeof (int));
8689 bzero ((char *) sched_reg_live_length
, max_regno
* sizeof (int));
8691 for (i
= 0; i
< max_regno
; i
++)
8692 sched_reg_basic_block
[i
] = REG_BLOCK_UNKNOWN
;
8696 sched_reg_n_calls_crossed
= 0;
8697 sched_reg_live_length
= 0;
8700 init_alias_analysis ();
8702 if (write_symbols
!= NO_DEBUG
)
8706 line_note
= (rtx
*) xmalloc (max_uid
* sizeof (rtx
));
8707 bzero ((char *) line_note
, max_uid
* sizeof (rtx
));
8708 line_note_head
= (rtx
*) alloca (n_basic_blocks
* sizeof (rtx
));
8709 bzero ((char *) line_note_head
, n_basic_blocks
* sizeof (rtx
));
8711 /* Save-line-note-head:
8712 Determine the line-number at the start of each basic block.
8713 This must be computed and saved now, because after a basic block's
8714 predecessor has been scheduled, it is impossible to accurately
8715 determine the correct line number for the first insn of the block. */
8717 for (b
= 0; b
< n_basic_blocks
; b
++)
8718 for (line
= BLOCK_HEAD (b
); line
; line
= PREV_INSN (line
))
8719 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
8721 line_note_head
[b
] = line
;
8726 bzero ((char *) insn_priority
, max_uid
* sizeof (int));
8727 bzero ((char *) insn_reg_weight
, max_uid
* sizeof (int));
8728 bzero ((char *) insn_tick
, max_uid
* sizeof (int));
8729 bzero ((char *) insn_costs
, max_uid
* sizeof (short));
8730 bzero ((char *) insn_units
, max_uid
* sizeof (short));
8731 bzero ((char *) insn_blockage
, max_uid
* sizeof (unsigned int));
8732 bzero ((char *) insn_ref_count
, max_uid
* sizeof (int));
8734 /* Initialize for forward dependencies */
8735 bzero ((char *) insn_depend
, max_uid
* sizeof (rtx
));
8736 bzero ((char *) insn_dep_count
, max_uid
* sizeof (int));
8738 /* Find units used in this fuction, for visualization */
8740 init_target_units ();
8742 /* ??? Add a NOTE after the last insn of the last basic block. It is not
8743 known why this is done. */
8745 insn
= BLOCK_END (n_basic_blocks
- 1);
8746 if (NEXT_INSN (insn
) == 0
8747 || (GET_CODE (insn
) != NOTE
8748 && GET_CODE (insn
) != CODE_LABEL
8749 /* Don't emit a NOTE if it would end up between an unconditional
8750 jump and a BARRIER. */
8751 && !(GET_CODE (insn
) == JUMP_INSN
8752 && GET_CODE (NEXT_INSN (insn
)) == BARRIER
)))
8753 emit_note_after (NOTE_INSN_DELETED
, BLOCK_END (n_basic_blocks
- 1));
8755 /* Schedule every region in the subroutine */
8756 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
8758 schedule_region (rgn
);
8765 /* Reposition the prologue and epilogue notes in case we moved the
8766 prologue/epilogue insns. */
8767 if (reload_completed
)
8768 reposition_prologue_and_epilogue_notes (get_insns ());
8770 /* delete redundant line notes. */
8771 if (write_symbols
!= NO_DEBUG
)
8772 rm_redundant_line_notes ();
8774 /* Update information about uses of registers in the subroutine. */
8775 if (reload_completed
== 0)
8776 update_reg_usage ();
8780 if (reload_completed
== 0 && flag_schedule_interblock
)
8782 fprintf (dump
, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8790 fprintf (dump
, "\n\n");
8794 free (fed_by_spec_load
);
8795 free (is_load_insn
);
8796 free (insn_orig_block
);
8799 free (insn_priority
);
8800 free (insn_reg_weight
);
8804 free (insn_blockage
);
8805 free (insn_ref_count
);
8807 free (insn_dep_count
);
8810 if (write_symbols
!= NO_DEBUG
)
8814 FREE_REG_SET (bb_live_regs
);
8833 #endif /* INSN_SCHEDULING */