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 "function.h"
165 #include "hard-reg-set.h"
167 #include "insn-config.h"
168 #include "insn-attr.h"
173 extern char *reg_known_equiv_p
;
174 extern rtx
*reg_known_value
;
176 #ifdef INSN_SCHEDULING
178 /* target_units bitmask has 1 for each unit in the cpu. It should be
179 possible to compute this variable from the machine description.
180 But currently it is computed by examining the insn list. Since
181 this is only needed for visualization, it seems an acceptable
182 solution. (For understanding the mapping of bits to units, see
183 definition of function_units[] in "insn-attrtab.c".) */
185 static int target_units
= 0;
187 /* issue_rate is the number of insns that can be scheduled in the same
188 machine cycle. It can be defined in the config/mach/mach.h file,
189 otherwise we set it to 1. */
191 static int issue_rate
;
197 /* sched-verbose controls the amount of debugging output the
198 scheduler prints. It is controlled by -fsched-verbose-N:
199 N>0 and no -DSR : the output is directed to stderr.
200 N>=10 will direct the printouts to stderr (regardless of -dSR).
202 N=2: bb's probabilities, detailed ready list info, unit/insn info.
203 N=3: rtl at abort point, control-flow, regions info.
204 N=5: dependences info. */
206 #define MAX_RGN_BLOCKS 10
207 #define MAX_RGN_INSNS 100
209 static int sched_verbose_param
= 0;
210 static int sched_verbose
= 0;
212 /* nr_inter/spec counts interblock/speculative motion for the function. */
213 static int nr_inter
, nr_spec
;
216 /* Debugging file. All printouts are sent to dump, which is always set,
217 either to stderr, or to the dump listing file (-dRS). */
218 static FILE *dump
= 0;
220 /* fix_sched_param() is called from toplev.c upon detection
221 of the -fsched-***-N options. */
224 fix_sched_param (param
, val
)
225 const char *param
, *val
;
227 if (!strcmp (param
, "verbose"))
228 sched_verbose_param
= atoi (val
);
230 warning ("fix_sched_param: unknown param: %s", param
);
234 /* Arrays set up by scheduling for the same respective purposes as
235 similar-named arrays set up by flow analysis. We work with these
236 arrays during the scheduling pass so we can compare values against
239 Values of these arrays are copied at the end of this pass into the
240 arrays set up by flow analysis. */
241 static int *sched_reg_n_calls_crossed
;
242 static int *sched_reg_live_length
;
243 static int *sched_reg_basic_block
;
245 /* We need to know the current block number during the post scheduling
246 update of live register information so that we can also update
247 REG_BASIC_BLOCK if a register changes blocks. */
248 static int current_block_num
;
250 /* Element N is the next insn that sets (hard or pseudo) register
251 N within the current basic block; or zero, if there is no
252 such insn. Needed for new registers which may be introduced
253 by splitting insns. */
254 static rtx
*reg_last_uses
;
255 static rtx
*reg_last_sets
;
256 static rtx
*reg_last_clobbers
;
257 static regset reg_pending_sets
;
258 static regset reg_pending_clobbers
;
259 static int reg_pending_sets_all
;
261 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
262 static int *insn_luid
;
263 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
265 /* Vector indexed by INSN_UID giving each instruction a priority. */
266 static int *insn_priority
;
267 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
269 static short *insn_costs
;
270 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
272 /* Vector indexed by INSN_UID giving an encoding of the function units
274 static short *insn_units
;
275 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
277 /* Vector indexed by INSN_UID giving each instruction a
278 register-weight. This weight is an estimation of the insn
279 contribution to registers pressure. */
280 static int *insn_reg_weight
;
281 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
283 /* Vector indexed by INSN_UID giving list of insns which
284 depend upon INSN. Unlike LOG_LINKS, it represents forward dependences. */
285 static rtx
*insn_depend
;
286 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
288 /* Vector indexed by INSN_UID. Initialized to the number of incoming
289 edges in forward dependence graph (= number of LOG_LINKS). As
290 scheduling procedes, dependence counts are decreased. An
291 instruction moves to the ready list when its counter is zero. */
292 static int *insn_dep_count
;
293 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
295 /* Vector indexed by INSN_UID giving an encoding of the blockage range
296 function. The unit and the range are encoded. */
297 static unsigned int *insn_blockage
;
298 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
300 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
301 #define ENCODE_BLOCKAGE(U, R) \
302 (((U) << BLOCKAGE_BITS \
303 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
304 | MAX_BLOCKAGE_COST (R))
305 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
306 #define BLOCKAGE_RANGE(B) \
307 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
308 | ((B) & BLOCKAGE_MASK))
310 /* Encodings of the `<name>_unit_blockage_range' function. */
311 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
312 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
314 #define DONE_PRIORITY -1
315 #define MAX_PRIORITY 0x7fffffff
316 #define TAIL_PRIORITY 0x7ffffffe
317 #define LAUNCH_PRIORITY 0x7f000001
318 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
319 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
321 /* Vector indexed by INSN_UID giving number of insns referring to this
323 static int *insn_ref_count
;
324 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
326 /* Vector indexed by INSN_UID giving line-number note in effect for each
327 insn. For line-number notes, this indicates whether the note may be
329 static rtx
*line_note
;
330 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
332 /* Vector indexed by basic block number giving the starting line-number
333 for each basic block. */
334 static rtx
*line_note_head
;
336 /* List of important notes we must keep around. This is a pointer to the
337 last element in the list. */
338 static rtx note_list
;
340 /* Regsets telling whether a given register is live or dead before the last
341 scheduled insn. Must scan the instructions once before scheduling to
342 determine what registers are live or dead at the end of the block. */
343 static regset bb_live_regs
;
345 /* Regset telling whether a given register is live after the insn currently
346 being scheduled. Before processing an insn, this is equal to bb_live_regs
347 above. This is used so that we can find registers that are newly born/dead
348 after processing an insn. */
349 static regset old_live_regs
;
351 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
352 during the initial scan and reused later. If there are not exactly as
353 many REG_DEAD notes in the post scheduled code as there were in the
354 prescheduled code then we trigger an abort because this indicates a bug. */
355 static rtx dead_notes
;
359 /* An instruction is ready to be scheduled when all insns preceding it
360 have already been scheduled. It is important to ensure that all
361 insns which use its result will not be executed until its result
362 has been computed. An insn is maintained in one of four structures:
364 (P) the "Pending" set of insns which cannot be scheduled until
365 their dependencies have been satisfied.
366 (Q) the "Queued" set of insns that can be scheduled when sufficient
368 (R) the "Ready" list of unscheduled, uncommitted insns.
369 (S) the "Scheduled" list of insns.
371 Initially, all insns are either "Pending" or "Ready" depending on
372 whether their dependencies are satisfied.
374 Insns move from the "Ready" list to the "Scheduled" list as they
375 are committed to the schedule. As this occurs, the insns in the
376 "Pending" list have their dependencies satisfied and move to either
377 the "Ready" list or the "Queued" set depending on whether
378 sufficient time has passed to make them ready. As time passes,
379 insns move from the "Queued" set to the "Ready" list. Insns may
380 move from the "Ready" list to the "Queued" set if they are blocked
381 due to a function unit conflict.
383 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
384 insns, i.e., those that are ready, queued, and pending.
385 The "Queued" set (Q) is implemented by the variable `insn_queue'.
386 The "Ready" list (R) is implemented by the variables `ready' and
388 The "Scheduled" list (S) is the new insn chain built by this pass.
390 The transition (R->S) is implemented in the scheduling loop in
391 `schedule_block' when the best insn to schedule is chosen.
392 The transition (R->Q) is implemented in `queue_insn' when an
393 insn is found to have a function unit conflict with the already
395 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
396 insns move from the ready list to the scheduled list.
397 The transition (Q->R) is implemented in 'queue_to_insn' as time
398 passes or stalls are introduced. */
400 /* Implement a circular buffer to delay instructions until sufficient
401 time has passed. INSN_QUEUE_SIZE is a power of two larger than
402 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
403 longest time an isnsn may be queued. */
404 static rtx insn_queue
[INSN_QUEUE_SIZE
];
405 static int q_ptr
= 0;
406 static int q_size
= 0;
407 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
408 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
410 /* Vector indexed by INSN_UID giving the minimum clock tick at which
411 the insn becomes ready. This is used to note timing constraints for
412 insns in the pending list. */
413 static int *insn_tick
;
414 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
416 /* Data structure for keeping track of register information
417 during that register's life. */
426 /* Forward declarations. */
427 static void add_dependence
PROTO ((rtx
, rtx
, enum reg_note
));
428 static void remove_dependence
PROTO ((rtx
, rtx
));
429 static rtx find_insn_list
PROTO ((rtx
, rtx
));
430 static int insn_unit
PROTO ((rtx
));
431 static unsigned int blockage_range
PROTO ((int, rtx
));
432 static void clear_units
PROTO ((void));
433 static int actual_hazard_this_instance
PROTO ((int, int, rtx
, int, int));
434 static void schedule_unit
PROTO ((int, rtx
, int));
435 static int actual_hazard
PROTO ((int, rtx
, int, int));
436 static int potential_hazard
PROTO ((int, rtx
, int));
437 static int insn_cost
PROTO ((rtx
, rtx
, rtx
));
438 static int priority
PROTO ((rtx
));
439 static void free_pending_lists
PROTO ((void));
440 static void add_insn_mem_dependence
PROTO ((rtx
*, rtx
*, rtx
, rtx
));
441 static void flush_pending_lists
PROTO ((rtx
, int));
442 static void sched_analyze_1
PROTO ((rtx
, rtx
));
443 static void sched_analyze_2
PROTO ((rtx
, rtx
));
444 static void sched_analyze_insn
PROTO ((rtx
, rtx
, rtx
));
445 static void sched_analyze
PROTO ((rtx
, rtx
));
446 static void sched_note_set
PROTO ((rtx
, int));
447 static int rank_for_schedule
PROTO ((const GENERIC_PTR
, const GENERIC_PTR
));
448 static void swap_sort
PROTO ((rtx
*, int));
449 static void queue_insn
PROTO ((rtx
, int));
450 static int schedule_insn
PROTO ((rtx
, rtx
*, int, int));
451 static void create_reg_dead_note
PROTO ((rtx
, rtx
));
452 static void attach_deaths
PROTO ((rtx
, rtx
, int));
453 static void attach_deaths_insn
PROTO ((rtx
));
454 static int new_sometimes_live
PROTO ((struct sometimes
*, int, int));
455 static void finish_sometimes_live
PROTO ((struct sometimes
*, int));
456 static int schedule_block
PROTO ((int, int));
457 static char *safe_concat
PROTO ((char *, char *, const 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])
499 static int is_cfg_nonregular
PROTO ((void));
500 static int build_control_flow
PROTO ((int_list_ptr
*, int_list_ptr
*,
502 static void new_edge
PROTO ((int, int));
505 /* A region is the main entity for interblock scheduling: insns
506 are allowed to move between blocks in the same region, along
507 control flow graph edges, in the 'up' direction. */
510 int rgn_nr_blocks
; /* Number of blocks in region. */
511 int rgn_blocks
; /* cblocks in the region (actually index in rgn_bb_table). */
515 /* Number of regions in the procedure. */
516 static int nr_regions
;
518 /* Table of region descriptions. */
519 static region
*rgn_table
;
521 /* Array of lists of regions' blocks. */
522 static int *rgn_bb_table
;
524 /* Topological order of blocks in the region (if b2 is reachable from
525 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
526 always referred to by either block or b, while its topological
527 order name (in the region) is refered to by bb. */
528 static int *block_to_bb
;
530 /* The number of the region containing a block. */
531 static int *containing_rgn
;
533 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
534 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
535 #define BLOCK_TO_BB(block) (block_to_bb[block])
536 #define CONTAINING_RGN(block) (containing_rgn[block])
538 void debug_regions
PROTO ((void));
539 static void find_single_block_region
PROTO ((void));
540 static void find_rgns
PROTO ((int_list_ptr
*, int_list_ptr
*,
541 int *, int *, sbitmap
*));
542 static int too_large
PROTO ((int, int *, int *));
544 extern void debug_live
PROTO ((int, int));
546 /* Blocks of the current region being scheduled. */
547 static int current_nr_blocks
;
548 static int current_blocks
;
550 /* The mapping from bb to block. */
551 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
554 /* Bit vectors and bitset operations are needed for computations on
555 the control flow graph. */
557 typedef unsigned HOST_WIDE_INT
*bitset
;
560 int *first_member
; /* Pointer to the list start in bitlst_table. */
561 int nr_members
; /* The number of members of the bit list. */
565 static int bitlst_table_last
;
566 static int bitlst_table_size
;
567 static int *bitlst_table
;
569 static char bitset_member
PROTO ((bitset
, int, int));
570 static void extract_bitlst
PROTO ((bitset
, int, bitlst
*));
572 /* Target info declarations.
574 The block currently being scheduled is referred to as the "target" block,
575 while other blocks in the region from which insns can be moved to the
576 target are called "source" blocks. The candidate structure holds info
577 about such sources: are they valid? Speculative? Etc. */
578 typedef bitlst bblst
;
589 static candidate
*candidate_table
;
591 /* A speculative motion requires checking live information on the path
592 from 'source' to 'target'. The split blocks are those to be checked.
593 After a speculative motion, live information should be modified in
596 Lists of split and update blocks for each candidate of the current
597 target are in array bblst_table. */
598 static int *bblst_table
, bblst_size
, bblst_last
;
600 #define IS_VALID(src) ( candidate_table[src].is_valid )
601 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
602 #define SRC_PROB(src) ( candidate_table[src].src_prob )
604 /* The bb being currently scheduled. */
605 static int target_bb
;
608 typedef bitlst edgelst
;
610 /* Target info functions. */
611 static void split_edges
PROTO ((int, int, edgelst
*));
612 static void compute_trg_info
PROTO ((int));
613 void debug_candidate
PROTO ((int));
614 void debug_candidates
PROTO ((int));
617 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
618 typedef bitset bbset
;
620 /* Number of words of the bbset. */
621 static int bbset_size
;
623 /* Dominators array: dom[i] contains the bbset of dominators of
624 bb i in the region. */
627 /* bb 0 is the only region entry. */
628 #define IS_RGN_ENTRY(bb) (!bb)
630 /* Is bb_src dominated by bb_trg. */
631 #define IS_DOMINATED(bb_src, bb_trg) \
632 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
634 /* Probability: Prob[i] is a float in [0, 1] which is the probability
635 of bb i relative to the region entry. */
638 /* The probability of bb_src, relative to bb_trg. Note, that while the
639 'prob[bb]' is a float in [0, 1], this macro returns an integer
641 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
644 /* Bit-set of edges, where bit i stands for edge i. */
645 typedef bitset edgeset
;
647 /* Number of edges in the region. */
648 static int rgn_nr_edges
;
650 /* Array of size rgn_nr_edges. */
651 static int *rgn_edges
;
653 /* Number of words in an edgeset. */
654 static int edgeset_size
;
656 /* Mapping from each edge in the graph to its number in the rgn. */
657 static int *edge_to_bit
;
658 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
660 /* The split edges of a source bb is different for each target
661 bb. In order to compute this efficiently, the 'potential-split edges'
662 are computed for each bb prior to scheduling a region. This is actually
663 the split edges of each bb relative to the region entry.
665 pot_split[bb] is the set of potential split edges of bb. */
666 static edgeset
*pot_split
;
668 /* For every bb, a set of its ancestor edges. */
669 static edgeset
*ancestor_edges
;
671 static void compute_dom_prob_ps
PROTO ((int));
673 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
674 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
675 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
676 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
678 /* Parameters affecting the decision of rank_for_schedule(). */
679 #define MIN_DIFF_PRIORITY 2
680 #define MIN_PROBABILITY 40
681 #define MIN_PROB_DIFF 10
683 /* Speculative scheduling functions. */
684 static int check_live_1
PROTO ((int, rtx
));
685 static void update_live_1
PROTO ((int, rtx
));
686 static int check_live
PROTO ((rtx
, int));
687 static void update_live
PROTO ((rtx
, int));
688 static void set_spec_fed
PROTO ((rtx
));
689 static int is_pfree
PROTO ((rtx
, int, int));
690 static int find_conditional_protection
PROTO ((rtx
, int));
691 static int is_conditionally_protected
PROTO ((rtx
, int, int));
692 static int may_trap_exp
PROTO ((rtx
, int));
693 static int haifa_classify_insn
PROTO ((rtx
));
694 static int is_prisky
PROTO ((rtx
, int, int));
695 static int is_exception_free
PROTO ((rtx
, int, int));
697 static char find_insn_mem_list
PROTO ((rtx
, rtx
, rtx
, rtx
));
698 static void compute_block_forward_dependences
PROTO ((int));
699 static void init_rgn_data_dependences
PROTO ((int));
700 static void add_branch_dependences
PROTO ((rtx
, rtx
));
701 static void compute_block_backward_dependences
PROTO ((int));
702 void debug_dependencies
PROTO ((void));
704 /* Notes handling mechanism:
705 =========================
706 Generally, NOTES are saved before scheduling and restored after scheduling.
707 The scheduler distinguishes between three types of notes:
709 (1) LINE_NUMBER notes, generated and used for debugging. Here,
710 before scheduling a region, a pointer to the LINE_NUMBER note is
711 added to the insn following it (in save_line_notes()), and the note
712 is removed (in rm_line_notes() and unlink_line_notes()). After
713 scheduling the region, this pointer is used for regeneration of
714 the LINE_NUMBER note (in restore_line_notes()).
716 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
717 Before scheduling a region, a pointer to the note is added to the insn
718 that follows or precedes it. (This happens as part of the data dependence
719 computation). After scheduling an insn, the pointer contained in it is
720 used for regenerating the corresponding note (in reemit_notes).
722 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
723 these notes are put in a list (in rm_other_notes() and
724 unlink_other_notes ()). After scheduling the block, these notes are
725 inserted at the beginning of the block (in schedule_block()). */
727 static rtx unlink_other_notes
PROTO ((rtx
, rtx
));
728 static rtx unlink_line_notes
PROTO ((rtx
, rtx
));
729 static void rm_line_notes
PROTO ((int));
730 static void save_line_notes
PROTO ((int));
731 static void restore_line_notes
PROTO ((int));
732 static void rm_redundant_line_notes
PROTO ((void));
733 static void rm_other_notes
PROTO ((rtx
, rtx
));
734 static rtx reemit_notes
PROTO ((rtx
, rtx
));
736 static void get_block_head_tail
PROTO ((int, rtx
*, rtx
*));
738 static void find_pre_sched_live
PROTO ((int));
739 static void find_post_sched_live
PROTO ((int));
740 static void update_reg_usage
PROTO ((void));
741 static int queue_to_ready
PROTO ((rtx
[], int));
743 static void debug_ready_list
PROTO ((rtx
[], int));
744 static void init_target_units
PROTO ((void));
745 static void insn_print_units
PROTO ((rtx
));
746 static int get_visual_tbl_length
PROTO ((void));
747 static void init_block_visualization
PROTO ((void));
748 static void print_block_visualization
PROTO ((int, const char *));
749 static void visualize_scheduled_insns
PROTO ((int, int));
750 static void visualize_no_unit
PROTO ((rtx
));
751 static void visualize_stall_cycles
PROTO ((int, int));
752 static void print_exp
PROTO ((char *, rtx
, int));
753 static void print_value
PROTO ((char *, rtx
, int));
754 static void print_pattern
PROTO ((char *, rtx
, int));
755 static void print_insn
PROTO ((char *, rtx
, int));
756 void debug_reg_vector
PROTO ((regset
));
758 static rtx move_insn1
PROTO ((rtx
, rtx
));
759 static rtx move_insn
PROTO ((rtx
, rtx
));
760 static rtx group_leader
PROTO ((rtx
));
761 static int set_priorities
PROTO ((int));
762 static void init_rtx_vector
PROTO ((rtx
**, rtx
*, int, int));
763 static void schedule_region
PROTO ((int));
765 #endif /* INSN_SCHEDULING */
767 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
769 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
770 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
771 of dependence that this link represents. */
774 add_dependence (insn
, elem
, dep_type
)
777 enum reg_note dep_type
;
781 /* Don't depend an insn on itself. */
785 /* We can get a dependency on deleted insns due to optimizations in
786 the register allocation and reloading or due to splitting. Any
787 such dependency is useless and can be ignored. */
788 if (GET_CODE (elem
) == NOTE
)
791 /* If elem is part of a sequence that must be scheduled together, then
792 make the dependence point to the last insn of the sequence.
793 When HAVE_cc0, it is possible for NOTEs to exist between users and
794 setters of the condition codes, so we must skip past notes here.
795 Otherwise, NOTEs are impossible here. */
797 next
= NEXT_INSN (elem
);
800 while (next
&& GET_CODE (next
) == NOTE
)
801 next
= NEXT_INSN (next
);
804 if (next
&& SCHED_GROUP_P (next
)
805 && GET_CODE (next
) != CODE_LABEL
)
807 /* Notes will never intervene here though, so don't bother checking
809 /* We must reject CODE_LABELs, so that we don't get confused by one
810 that has LABEL_PRESERVE_P set, which is represented by the same
811 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
813 while (NEXT_INSN (next
) && SCHED_GROUP_P (NEXT_INSN (next
))
814 && GET_CODE (NEXT_INSN (next
)) != CODE_LABEL
)
815 next
= NEXT_INSN (next
);
817 /* Again, don't depend an insn on itself. */
821 /* Make the dependence to NEXT, the last insn of the group, instead
822 of the original ELEM. */
826 #ifdef INSN_SCHEDULING
827 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
828 No need for interblock dependences with calls, since
829 calls are not moved between blocks. Note: the edge where
830 elem is a CALL is still required. */
831 if (GET_CODE (insn
) == CALL_INSN
832 && (INSN_BB (elem
) != INSN_BB (insn
)))
837 /* Check that we don't already have this dependence. */
838 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
839 if (XEXP (link
, 0) == elem
)
841 /* If this is a more restrictive type of dependence than the existing
842 one, then change the existing dependence to this type. */
843 if ((int) dep_type
< (int) REG_NOTE_KIND (link
))
844 PUT_REG_NOTE_KIND (link
, dep_type
);
847 /* Might want to check one level of transitivity to save conses. */
849 link
= alloc_INSN_LIST (elem
, LOG_LINKS (insn
));
850 LOG_LINKS (insn
) = link
;
852 /* Insn dependency, not data dependency. */
853 PUT_REG_NOTE_KIND (link
, dep_type
);
856 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
857 of INSN. Abort if not found. */
860 remove_dependence (insn
, elem
)
864 rtx prev
, link
, next
;
867 for (prev
= 0, link
= LOG_LINKS (insn
); link
; link
= next
)
869 next
= XEXP (link
, 1);
870 if (XEXP (link
, 0) == elem
)
873 XEXP (prev
, 1) = next
;
875 LOG_LINKS (insn
) = next
;
876 free_INSN_LIST_node (link
);
889 #ifndef INSN_SCHEDULING
891 schedule_insns (dump_file
)
901 #define HAIFA_INLINE __inline
904 /* Computation of memory dependencies. */
906 /* The *_insns and *_mems are paired lists. Each pending memory operation
907 will have a pointer to the MEM rtx on one list and a pointer to the
908 containing insn on the other list in the same place in the list. */
910 /* We can't use add_dependence like the old code did, because a single insn
911 may have multiple memory accesses, and hence needs to be on the list
912 once for each memory access. Add_dependence won't let you add an insn
913 to a list more than once. */
915 /* An INSN_LIST containing all insns with pending read operations. */
916 static rtx pending_read_insns
;
918 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
919 static rtx pending_read_mems
;
921 /* An INSN_LIST containing all insns with pending write operations. */
922 static rtx pending_write_insns
;
924 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
925 static rtx pending_write_mems
;
927 /* Indicates the combined length of the two pending lists. We must prevent
928 these lists from ever growing too large since the number of dependencies
929 produced is at least O(N*N), and execution time is at least O(4*N*N), as
930 a function of the length of these pending lists. */
932 static int pending_lists_length
;
934 /* The last insn upon which all memory references must depend.
935 This is an insn which flushed the pending lists, creating a dependency
936 between it and all previously pending memory references. This creates
937 a barrier (or a checkpoint) which no memory reference is allowed to cross.
939 This includes all non constant CALL_INSNs. When we do interprocedural
940 alias analysis, this restriction can be relaxed.
941 This may also be an INSN that writes memory if the pending lists grow
944 static rtx last_pending_memory_flush
;
946 /* The last function call we have seen. All hard regs, and, of course,
947 the last function call, must depend on this. */
949 static rtx last_function_call
;
951 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
952 that does not already cross a call. We create dependencies between each
953 of those insn and the next call insn, to ensure that they won't cross a call
954 after scheduling is done. */
956 static rtx sched_before_next_call
;
958 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
959 so that insns independent of the last scheduled insn will be preferred
960 over dependent instructions. */
962 static rtx last_scheduled_insn
;
964 /* Data structures for the computation of data dependences in a regions. We
965 keep one copy of each of the declared above variables for each bb in the
966 region. Before analyzing the data dependences for a bb, its variables
967 are initialized as a function of the variables of its predecessors. When
968 the analysis for a bb completes, we save the contents of each variable X
969 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
970 copied to bb_pending_read_insns[bb]. Another change is that few
971 variables are now a list of insns rather than a single insn:
972 last_pending_memory_flash, last_function_call, reg_last_sets. The
973 manipulation of these variables was changed appropriately. */
975 static rtx
**bb_reg_last_uses
;
976 static rtx
**bb_reg_last_sets
;
977 static rtx
**bb_reg_last_clobbers
;
979 static rtx
*bb_pending_read_insns
;
980 static rtx
*bb_pending_read_mems
;
981 static rtx
*bb_pending_write_insns
;
982 static rtx
*bb_pending_write_mems
;
983 static int *bb_pending_lists_length
;
985 static rtx
*bb_last_pending_memory_flush
;
986 static rtx
*bb_last_function_call
;
987 static rtx
*bb_sched_before_next_call
;
989 /* Functions for construction of the control flow graph. */
991 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
993 We decide not to build the control flow graph if there is possibly more
994 than one entry to the function, if computed branches exist, of if we
995 have nonlocal gotos. */
1004 /* If we have a label that could be the target of a nonlocal goto, then
1005 the cfg is not well structured. */
1006 if (nonlocal_goto_handler_labels
)
1009 /* If we have any forced labels, then the cfg is not well structured. */
1013 /* If this function has a computed jump, then we consider the cfg
1014 not well structured. */
1015 if (current_function_has_computed_jump
)
1018 /* If we have exception handlers, then we consider the cfg not well
1019 structured. ?!? We should be able to handle this now that flow.c
1020 computes an accurate cfg for EH. */
1021 if (exception_handler_labels
)
1024 /* If we have non-jumping insns which refer to labels, then we consider
1025 the cfg not well structured. */
1026 /* Check for labels referred to other thn by jumps. */
1027 for (b
= 0; b
< n_basic_blocks
; b
++)
1028 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
1030 code
= GET_CODE (insn
);
1031 if (GET_RTX_CLASS (code
) == 'i')
1035 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1036 if (REG_NOTE_KIND (note
) == REG_LABEL
)
1040 if (insn
== BLOCK_END (b
))
1044 /* All the tests passed. Consider the cfg well structured. */
1048 /* Build the control flow graph and set nr_edges.
1050 Instead of trying to build a cfg ourselves, we rely on flow to
1051 do it for us. Stamp out useless code (and bug) duplication.
1053 Return nonzero if an irregularity in the cfg is found which would
1054 prevent cross block scheduling. */
1057 build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
)
1058 int_list_ptr
*s_preds
;
1059 int_list_ptr
*s_succs
;
1067 /* Count the number of edges in the cfg. */
1070 for (i
= 0; i
< n_basic_blocks
; i
++)
1072 nr_edges
+= num_succs
[i
];
1074 /* Unreachable loops with more than one basic block are detected
1075 during the DFS traversal in find_rgns.
1077 Unreachable loops with a single block are detected here. This
1078 test is redundant with the one in find_rgns, but it's much
1079 cheaper to go ahead and catch the trivial case here. */
1080 if (num_preds
[i
] == 0
1081 || (num_preds
[i
] == 1 && INT_LIST_VAL (s_preds
[i
]) == i
))
1085 /* Account for entry/exit edges. */
1088 in_edges
= (int *) xcalloc (n_basic_blocks
, sizeof (int));
1089 out_edges
= (int *) xcalloc (n_basic_blocks
, sizeof (int));
1090 edge_table
= (haifa_edge
*) xcalloc (nr_edges
, sizeof (haifa_edge
));
1093 for (i
= 0; i
< n_basic_blocks
; i
++)
1094 for (succ
= s_succs
[i
]; succ
; succ
= succ
->next
)
1096 if (INT_LIST_VAL (succ
) != EXIT_BLOCK
)
1097 new_edge (i
, INT_LIST_VAL (succ
));
1100 /* Increment by 1, since edge 0 is unused. */
1107 /* Record an edge in the control flow graph from SOURCE to TARGET.
1109 In theory, this is redundant with the s_succs computed above, but
1110 we have not converted all of haifa to use information from the
1114 new_edge (source
, target
)
1118 int curr_edge
, fst_edge
;
1120 /* Check for duplicates. */
1121 fst_edge
= curr_edge
= OUT_EDGES (source
);
1124 if (FROM_BLOCK (curr_edge
) == source
1125 && TO_BLOCK (curr_edge
) == target
)
1130 curr_edge
= NEXT_OUT (curr_edge
);
1132 if (fst_edge
== curr_edge
)
1138 FROM_BLOCK (e
) = source
;
1139 TO_BLOCK (e
) = target
;
1141 if (OUT_EDGES (source
))
1143 next_edge
= NEXT_OUT (OUT_EDGES (source
));
1144 NEXT_OUT (OUT_EDGES (source
)) = e
;
1145 NEXT_OUT (e
) = next_edge
;
1149 OUT_EDGES (source
) = e
;
1153 if (IN_EDGES (target
))
1155 next_edge
= NEXT_IN (IN_EDGES (target
));
1156 NEXT_IN (IN_EDGES (target
)) = e
;
1157 NEXT_IN (e
) = next_edge
;
1161 IN_EDGES (target
) = e
;
1167 /* BITSET macros for operations on the control flow graph. */
1169 /* Compute bitwise union of two bitsets. */
1170 #define BITSET_UNION(set1, set2, len) \
1171 do { register bitset tp = set1, sp = set2; \
1173 for (i = 0; i < len; i++) \
1174 *(tp++) |= *(sp++); } while (0)
1176 /* Compute bitwise intersection of two bitsets. */
1177 #define BITSET_INTER(set1, set2, len) \
1178 do { register bitset tp = set1, sp = set2; \
1180 for (i = 0; i < len; i++) \
1181 *(tp++) &= *(sp++); } while (0)
1183 /* Compute bitwise difference of two bitsets. */
1184 #define BITSET_DIFFER(set1, set2, len) \
1185 do { register bitset tp = set1, sp = set2; \
1187 for (i = 0; i < len; i++) \
1188 *(tp++) &= ~*(sp++); } while (0)
1190 /* Inverts every bit of bitset 'set'. */
1191 #define BITSET_INVERT(set, len) \
1192 do { register bitset tmpset = set; \
1194 for (i = 0; i < len; i++, tmpset++) \
1195 *tmpset = ~*tmpset; } while (0)
1197 /* Turn on the index'th bit in bitset set. */
1198 #define BITSET_ADD(set, index, len) \
1200 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1203 set[index/HOST_BITS_PER_WIDE_INT] |= \
1204 1 << (index % HOST_BITS_PER_WIDE_INT); \
1207 /* Turn off the index'th bit in set. */
1208 #define BITSET_REMOVE(set, index, len) \
1210 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1213 set[index/HOST_BITS_PER_WIDE_INT] &= \
1214 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1218 /* Check if the index'th bit in bitset set is on. */
1221 bitset_member (set
, index
, len
)
1225 if (index
>= HOST_BITS_PER_WIDE_INT
* len
)
1227 return (set
[index
/ HOST_BITS_PER_WIDE_INT
] &
1228 1 << (index
% HOST_BITS_PER_WIDE_INT
)) ? 1 : 0;
1232 /* Translate a bit-set SET to a list BL of the bit-set members. */
1235 extract_bitlst (set
, len
, bl
)
1241 unsigned HOST_WIDE_INT word
;
1243 /* bblst table space is reused in each call to extract_bitlst. */
1244 bitlst_table_last
= 0;
1246 bl
->first_member
= &bitlst_table
[bitlst_table_last
];
1249 for (i
= 0; i
< len
; i
++)
1252 offset
= i
* HOST_BITS_PER_WIDE_INT
;
1253 for (j
= 0; word
; j
++)
1257 bitlst_table
[bitlst_table_last
++] = offset
;
1268 /* Functions for the construction of regions. */
1270 /* Print the regions, for debugging purposes. Callable from debugger. */
1277 fprintf (dump
, "\n;; ------------ REGIONS ----------\n\n");
1278 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
1280 fprintf (dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
1281 rgn_table
[rgn
].rgn_nr_blocks
);
1282 fprintf (dump
, ";;\tbb/block: ");
1284 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
1286 current_blocks
= RGN_BLOCKS (rgn
);
1288 if (bb
!= BLOCK_TO_BB (BB_TO_BLOCK (bb
)))
1291 fprintf (dump
, " %d/%d ", bb
, BB_TO_BLOCK (bb
));
1294 fprintf (dump
, "\n\n");
1299 /* Build a single block region for each basic block in the function.
1300 This allows for using the same code for interblock and basic block
1304 find_single_block_region ()
1308 for (i
= 0; i
< n_basic_blocks
; i
++)
1310 rgn_bb_table
[i
] = i
;
1311 RGN_NR_BLOCKS (i
) = 1;
1313 CONTAINING_RGN (i
) = i
;
1314 BLOCK_TO_BB (i
) = 0;
1316 nr_regions
= n_basic_blocks
;
1320 /* Update number of blocks and the estimate for number of insns
1321 in the region. Return 1 if the region is "too large" for interblock
1322 scheduling (compile time considerations), otherwise return 0. */
1325 too_large (block
, num_bbs
, num_insns
)
1326 int block
, *num_bbs
, *num_insns
;
1329 (*num_insns
) += (INSN_LUID (BLOCK_END (block
)) -
1330 INSN_LUID (BLOCK_HEAD (block
)));
1331 if ((*num_bbs
> MAX_RGN_BLOCKS
) || (*num_insns
> MAX_RGN_INSNS
))
1338 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1339 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1340 loop containing blk. */
1341 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1343 if (max_hdr[blk] == -1) \
1344 max_hdr[blk] = hdr; \
1345 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1346 RESET_BIT (inner, hdr); \
1347 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1349 RESET_BIT (inner,max_hdr[blk]); \
1350 max_hdr[blk] = hdr; \
1355 /* Find regions for interblock scheduling.
1357 A region for scheduling can be:
1359 * A loop-free procedure, or
1361 * A reducible inner loop, or
1363 * A basic block not contained in any other region.
1366 ?!? In theory we could build other regions based on extended basic
1367 blocks or reverse extended basic blocks. Is it worth the trouble?
1369 Loop blocks that form a region are put into the region's block list
1370 in topological order.
1372 This procedure stores its results into the following global (ick) variables
1381 We use dominator relationships to avoid making regions out of non-reducible
1384 This procedure needs to be converted to work on pred/succ lists instead
1385 of edge tables. That would simplify it somewhat. */
1388 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
)
1389 int_list_ptr
*s_preds
;
1390 int_list_ptr
*s_succs
;
1395 int *max_hdr
, *dfs_nr
, *stack
, *queue
, *degree
;
1397 int node
, child
, loop_head
, i
, head
, tail
;
1398 int count
= 0, sp
, idx
= 0, current_edge
= out_edges
[0];
1399 int num_bbs
, num_insns
, unreachable
;
1400 int too_large_failure
;
1402 /* Note if an edge has been passed. */
1405 /* Note if a block is a natural loop header. */
1408 /* Note if a block is an natural inner loop header. */
1411 /* Note if a block is in the block queue. */
1414 /* Note if a block is in the block queue. */
1417 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1418 and a mapping from block to its loop header (if the block is contained
1419 in a loop, else -1).
1421 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1422 be used as inputs to the second traversal.
1424 STACK, SP and DFS_NR are only used during the first traversal. */
1426 /* Allocate and initialize variables for the first traversal. */
1427 max_hdr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1428 dfs_nr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1429 bzero ((char *) dfs_nr
, n_basic_blocks
* sizeof (int));
1430 stack
= (int *) alloca (nr_edges
* sizeof (int));
1432 inner
= sbitmap_alloc (n_basic_blocks
);
1433 sbitmap_ones (inner
);
1435 header
= sbitmap_alloc (n_basic_blocks
);
1436 sbitmap_zero (header
);
1438 passed
= sbitmap_alloc (nr_edges
);
1439 sbitmap_zero (passed
);
1441 in_queue
= sbitmap_alloc (n_basic_blocks
);
1442 sbitmap_zero (in_queue
);
1444 in_stack
= sbitmap_alloc (n_basic_blocks
);
1445 sbitmap_zero (in_stack
);
1447 for (i
= 0; i
< n_basic_blocks
; i
++)
1450 /* DFS traversal to find inner loops in the cfg. */
1455 if (current_edge
== 0 || TEST_BIT (passed
, current_edge
))
1457 /* We have reached a leaf node or a node that was already
1458 processed. Pop edges off the stack until we find
1459 an edge that has not yet been processed. */
1461 && (current_edge
== 0 || TEST_BIT (passed
, current_edge
)))
1463 /* Pop entry off the stack. */
1464 current_edge
= stack
[sp
--];
1465 node
= FROM_BLOCK (current_edge
);
1466 child
= TO_BLOCK (current_edge
);
1467 RESET_BIT (in_stack
, child
);
1468 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1469 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1470 current_edge
= NEXT_OUT (current_edge
);
1473 /* See if have finished the DFS tree traversal. */
1474 if (sp
< 0 && TEST_BIT (passed
, current_edge
))
1477 /* Nope, continue the traversal with the popped node. */
1481 /* Process a node. */
1482 node
= FROM_BLOCK (current_edge
);
1483 child
= TO_BLOCK (current_edge
);
1484 SET_BIT (in_stack
, node
);
1485 dfs_nr
[node
] = ++count
;
1487 /* If the successor is in the stack, then we've found a loop.
1488 Mark the loop, if it is not a natural loop, then it will
1489 be rejected during the second traversal. */
1490 if (TEST_BIT (in_stack
, child
))
1493 SET_BIT (header
, child
);
1494 UPDATE_LOOP_RELATIONS (node
, child
);
1495 SET_BIT (passed
, current_edge
);
1496 current_edge
= NEXT_OUT (current_edge
);
1500 /* If the child was already visited, then there is no need to visit
1501 it again. Just update the loop relationships and restart
1505 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1506 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1507 SET_BIT (passed
, current_edge
);
1508 current_edge
= NEXT_OUT (current_edge
);
1512 /* Push an entry on the stack and continue DFS traversal. */
1513 stack
[++sp
] = current_edge
;
1514 SET_BIT (passed
, current_edge
);
1515 current_edge
= OUT_EDGES (child
);
1517 /* This is temporary until haifa is converted to use rth's new
1518 cfg routines which have true entry/exit blocks and the
1519 appropriate edges from/to those blocks.
1521 Generally we update dfs_nr for a node when we process its
1522 out edge. However, if the node has no out edge then we will
1523 not set dfs_nr for that node. This can confuse the scheduler
1524 into thinking that we have unreachable blocks, which in turn
1525 disables cross block scheduling.
1527 So, if we have a node with no out edges, go ahead and mark it
1528 as reachable now. */
1529 if (current_edge
== 0)
1530 dfs_nr
[child
] = ++count
;
1533 /* Another check for unreachable blocks. The earlier test in
1534 is_cfg_nonregular only finds unreachable blocks that do not
1537 The DFS traversal will mark every block that is reachable from
1538 the entry node by placing a nonzero value in dfs_nr. Thus if
1539 dfs_nr is zero for any block, then it must be unreachable. */
1541 for (i
= 0; i
< n_basic_blocks
; i
++)
1548 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1549 to hold degree counts. */
1552 /* Compute the in-degree of every block in the graph. */
1553 for (i
= 0; i
< n_basic_blocks
; i
++)
1554 degree
[i
] = num_preds
[i
];
1556 /* Do not perform region scheduling if there are any unreachable
1561 SET_BIT (header
, 0);
1563 /* Second travsersal:find reducible inner loops and topologically sort
1564 block of each region. */
1566 queue
= (int *) alloca (n_basic_blocks
* sizeof (int));
1568 /* Find blocks which are inner loop headers. We still have non-reducible
1569 loops to consider at this point. */
1570 for (i
= 0; i
< n_basic_blocks
; i
++)
1572 if (TEST_BIT (header
, i
) && TEST_BIT (inner
, i
))
1577 /* Now check that the loop is reducible. We do this separate
1578 from finding inner loops so that we do not find a reducible
1579 loop which contains an inner non-reducible loop.
1581 A simple way to find reducible/natural loops is to verify
1582 that each block in the loop is dominated by the loop
1585 If there exists a block that is not dominated by the loop
1586 header, then the block is reachable from outside the loop
1587 and thus the loop is not a natural loop. */
1588 for (j
= 0; j
< n_basic_blocks
; j
++)
1590 /* First identify blocks in the loop, except for the loop
1592 if (i
== max_hdr
[j
] && i
!= j
)
1594 /* Now verify that the block is dominated by the loop
1596 if (!TEST_BIT (dom
[j
], i
))
1601 /* If we exited the loop early, then I is the header of
1602 a non-reducible loop and we should quit processing it
1604 if (j
!= n_basic_blocks
)
1607 /* I is a header of an inner loop, or block 0 in a subroutine
1608 with no loops at all. */
1610 too_large_failure
= 0;
1611 loop_head
= max_hdr
[i
];
1613 /* Decrease degree of all I's successors for topological
1615 for (ps
= s_succs
[i
]; ps
; ps
= ps
->next
)
1616 if (INT_LIST_VAL (ps
) != EXIT_BLOCK
1617 && INT_LIST_VAL (ps
) != ENTRY_BLOCK
)
1618 --degree
[INT_LIST_VAL(ps
)];
1620 /* Estimate # insns, and count # blocks in the region. */
1622 num_insns
= (INSN_LUID (BLOCK_END (i
))
1623 - INSN_LUID (BLOCK_HEAD (i
)));
1626 /* Find all loop latches (blocks with back edges to the loop
1627 header) or all the leaf blocks in the cfg has no loops.
1629 Place those blocks into the queue. */
1632 for (j
= 0; j
< n_basic_blocks
; j
++)
1633 /* Leaf nodes have only a single successor which must
1635 if (num_succs
[j
] == 1
1636 && INT_LIST_VAL (s_succs
[j
]) == EXIT_BLOCK
)
1639 SET_BIT (in_queue
, j
);
1641 if (too_large (j
, &num_bbs
, &num_insns
))
1643 too_large_failure
= 1;
1652 for (ps
= s_preds
[i
]; ps
; ps
= ps
->next
)
1654 node
= INT_LIST_VAL (ps
);
1656 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
)
1659 if (max_hdr
[node
] == loop_head
&& node
!= i
)
1661 /* This is a loop latch. */
1662 queue
[++tail
] = node
;
1663 SET_BIT (in_queue
, node
);
1665 if (too_large (node
, &num_bbs
, &num_insns
))
1667 too_large_failure
= 1;
1675 /* Now add all the blocks in the loop to the queue.
1677 We know the loop is a natural loop; however the algorithm
1678 above will not always mark certain blocks as being in the
1687 The algorithm in the DFS traversal may not mark B & D as part
1688 of the loop (ie they will not have max_hdr set to A).
1690 We know they can not be loop latches (else they would have
1691 had max_hdr set since they'd have a backedge to a dominator
1692 block). So we don't need them on the initial queue.
1694 We know they are part of the loop because they are dominated
1695 by the loop header and can be reached by a backwards walk of
1696 the edges starting with nodes on the initial queue.
1698 It is safe and desirable to include those nodes in the
1699 loop/scheduling region. To do so we would need to decrease
1700 the degree of a node if it is the target of a backedge
1701 within the loop itself as the node is placed in the queue.
1703 We do not do this because I'm not sure that the actual
1704 scheduling code will properly handle this case. ?!? */
1706 while (head
< tail
&& !too_large_failure
)
1709 child
= queue
[++head
];
1711 for (ps
= s_preds
[child
]; ps
; ps
= ps
->next
)
1713 node
= INT_LIST_VAL (ps
);
1715 /* See discussion above about nodes not marked as in
1716 this loop during the initial DFS traversal. */
1717 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
1718 || max_hdr
[node
] != loop_head
)
1723 else if (!TEST_BIT (in_queue
, node
) && node
!= i
)
1725 queue
[++tail
] = node
;
1726 SET_BIT (in_queue
, node
);
1728 if (too_large (node
, &num_bbs
, &num_insns
))
1730 too_large_failure
= 1;
1737 if (tail
>= 0 && !too_large_failure
)
1739 /* Place the loop header into list of region blocks. */
1741 rgn_bb_table
[idx
] = i
;
1742 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1743 RGN_BLOCKS (nr_regions
) = idx
++;
1744 CONTAINING_RGN (i
) = nr_regions
;
1745 BLOCK_TO_BB (i
) = count
= 0;
1747 /* Remove blocks from queue[] when their in degree
1748 becomes zero. Repeat until no blocks are left on the
1749 list. This produces a topological list of blocks in
1757 child
= queue
[head
];
1758 if (degree
[child
] == 0)
1761 rgn_bb_table
[idx
++] = child
;
1762 BLOCK_TO_BB (child
) = ++count
;
1763 CONTAINING_RGN (child
) = nr_regions
;
1764 queue
[head
] = queue
[tail
--];
1766 for (ps
= s_succs
[child
]; ps
; ps
= ps
->next
)
1767 if (INT_LIST_VAL (ps
) != ENTRY_BLOCK
1768 && INT_LIST_VAL (ps
) != EXIT_BLOCK
)
1769 --degree
[INT_LIST_VAL (ps
)];
1780 /* Any block that did not end up in a region is placed into a region
1782 for (i
= 0; i
< n_basic_blocks
; i
++)
1785 rgn_bb_table
[idx
] = i
;
1786 RGN_NR_BLOCKS (nr_regions
) = 1;
1787 RGN_BLOCKS (nr_regions
) = idx
++;
1788 CONTAINING_RGN (i
) = nr_regions
++;
1789 BLOCK_TO_BB (i
) = 0;
1800 /* Functions for regions scheduling information. */
1802 /* Compute dominators, probability, and potential-split-edges of bb.
1803 Assume that these values were already computed for bb's predecessors. */
1806 compute_dom_prob_ps (bb
)
1809 int nxt_in_edge
, fst_in_edge
, pred
;
1810 int fst_out_edge
, nxt_out_edge
, nr_out_edges
, nr_rgn_out_edges
;
1813 if (IS_RGN_ENTRY (bb
))
1815 BITSET_ADD (dom
[bb
], 0, bbset_size
);
1820 fst_in_edge
= nxt_in_edge
= IN_EDGES (BB_TO_BLOCK (bb
));
1822 /* Intialize dom[bb] to '111..1'. */
1823 BITSET_INVERT (dom
[bb
], bbset_size
);
1827 pred
= FROM_BLOCK (nxt_in_edge
);
1828 BITSET_INTER (dom
[bb
], dom
[BLOCK_TO_BB (pred
)], bbset_size
);
1830 BITSET_UNION (ancestor_edges
[bb
], ancestor_edges
[BLOCK_TO_BB (pred
)],
1833 BITSET_ADD (ancestor_edges
[bb
], EDGE_TO_BIT (nxt_in_edge
), edgeset_size
);
1836 nr_rgn_out_edges
= 0;
1837 fst_out_edge
= OUT_EDGES (pred
);
1838 nxt_out_edge
= NEXT_OUT (fst_out_edge
);
1839 BITSET_UNION (pot_split
[bb
], pot_split
[BLOCK_TO_BB (pred
)],
1842 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (fst_out_edge
), edgeset_size
);
1844 /* The successor doesn't belong in the region? */
1845 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge
)) !=
1846 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1849 while (fst_out_edge
!= nxt_out_edge
)
1852 /* The successor doesn't belong in the region? */
1853 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge
)) !=
1854 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1856 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (nxt_out_edge
), edgeset_size
);
1857 nxt_out_edge
= NEXT_OUT (nxt_out_edge
);
1861 /* Now nr_rgn_out_edges is the number of region-exit edges from
1862 pred, and nr_out_edges will be the number of pred out edges
1863 not leaving the region. */
1864 nr_out_edges
-= nr_rgn_out_edges
;
1865 if (nr_rgn_out_edges
> 0)
1866 prob
[bb
] += 0.9 * prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1868 prob
[bb
] += prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1869 nxt_in_edge
= NEXT_IN (nxt_in_edge
);
1871 while (fst_in_edge
!= nxt_in_edge
);
1873 BITSET_ADD (dom
[bb
], bb
, bbset_size
);
1874 BITSET_DIFFER (pot_split
[bb
], ancestor_edges
[bb
], edgeset_size
);
1876 if (sched_verbose
>= 2)
1877 fprintf (dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
), (int) (100.0 * prob
[bb
]));
1878 } /* compute_dom_prob_ps */
1880 /* Functions for target info. */
1882 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1883 Note that bb_trg dominates bb_src. */
1886 split_edges (bb_src
, bb_trg
, bl
)
1891 int es
= edgeset_size
;
1892 edgeset src
= (edgeset
) alloca (es
* sizeof (HOST_WIDE_INT
));
1895 src
[es
] = (pot_split
[bb_src
])[es
];
1896 BITSET_DIFFER (src
, pot_split
[bb_trg
], edgeset_size
);
1897 extract_bitlst (src
, edgeset_size
, bl
);
1901 /* Find the valid candidate-source-blocks for the target block TRG, compute
1902 their probability, and check if they are speculative or not.
1903 For speculative sources, compute their update-blocks and split-blocks. */
1906 compute_trg_info (trg
)
1909 register candidate
*sp
;
1911 int check_block
, update_idx
;
1912 int i
, j
, k
, fst_edge
, nxt_edge
;
1914 /* Define some of the fields for the target bb as well. */
1915 sp
= candidate_table
+ trg
;
1917 sp
->is_speculative
= 0;
1920 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1922 sp
= candidate_table
+ i
;
1924 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1927 sp
->src_prob
= GET_SRC_PROB (i
, trg
);
1928 sp
->is_valid
= (sp
->src_prob
>= MIN_PROBABILITY
);
1933 split_edges (i
, trg
, &el
);
1934 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1935 if (sp
->is_speculative
&& !flag_schedule_speculative
)
1941 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
1942 sp
->split_bbs
.nr_members
= el
.nr_members
;
1943 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
1944 bblst_table
[bblst_last
] =
1945 TO_BLOCK (rgn_edges
[el
.first_member
[j
]]);
1946 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
1948 for (j
= 0; j
< el
.nr_members
; j
++)
1950 check_block
= FROM_BLOCK (rgn_edges
[el
.first_member
[j
]]);
1951 fst_edge
= nxt_edge
= OUT_EDGES (check_block
);
1954 for (k
= 0; k
< el
.nr_members
; k
++)
1955 if (EDGE_TO_BIT (nxt_edge
) == el
.first_member
[k
])
1958 if (k
>= el
.nr_members
)
1960 bblst_table
[bblst_last
++] = TO_BLOCK (nxt_edge
);
1964 nxt_edge
= NEXT_OUT (nxt_edge
);
1966 while (fst_edge
!= nxt_edge
);
1968 sp
->update_bbs
.nr_members
= update_idx
;
1973 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
1975 sp
->is_speculative
= 0;
1979 } /* compute_trg_info */
1982 /* Print candidates info, for debugging purposes. Callable from debugger. */
1988 if (!candidate_table
[i
].is_valid
)
1991 if (candidate_table
[i
].is_speculative
)
1994 fprintf (dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
1996 fprintf (dump
, "split path: ");
1997 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
1999 int b
= candidate_table
[i
].split_bbs
.first_member
[j
];
2001 fprintf (dump
, " %d ", b
);
2003 fprintf (dump
, "\n");
2005 fprintf (dump
, "update path: ");
2006 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
2008 int b
= candidate_table
[i
].update_bbs
.first_member
[j
];
2010 fprintf (dump
, " %d ", b
);
2012 fprintf (dump
, "\n");
2016 fprintf (dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
2021 /* Print candidates info, for debugging purposes. Callable from debugger. */
2024 debug_candidates (trg
)
2029 fprintf (dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
2030 BB_TO_BLOCK (trg
), trg
);
2031 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
2032 debug_candidate (i
);
2036 /* Functions for speculative scheduing. */
2038 /* Return 0 if x is a set of a register alive in the beginning of one
2039 of the split-blocks of src, otherwise return 1. */
2042 check_live_1 (src
, x
)
2048 register rtx reg
= SET_DEST (x
);
2053 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2054 || GET_CODE (reg
) == SIGN_EXTRACT
2055 || GET_CODE (reg
) == STRICT_LOW_PART
)
2056 reg
= XEXP (reg
, 0);
2058 if (GET_CODE (reg
) == PARALLEL
2059 && GET_MODE (reg
) == BLKmode
)
2062 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2063 if (check_live_1 (src
, XVECEXP (reg
, 0, i
)))
2068 if (GET_CODE (reg
) != REG
)
2071 regno
= REGNO (reg
);
2073 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
2075 /* Global registers are assumed live. */
2080 if (regno
< FIRST_PSEUDO_REGISTER
)
2082 /* Check for hard registers. */
2083 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2086 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2088 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2090 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
,
2100 /* Check for psuedo registers. */
2101 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2103 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2105 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
, regno
))
2117 /* If x is a set of a register R, mark that R is alive in the beginning
2118 of every update-block of src. */
2121 update_live_1 (src
, x
)
2127 register rtx reg
= SET_DEST (x
);
2132 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2133 || GET_CODE (reg
) == SIGN_EXTRACT
2134 || GET_CODE (reg
) == STRICT_LOW_PART
)
2135 reg
= XEXP (reg
, 0);
2137 if (GET_CODE (reg
) == PARALLEL
2138 && GET_MODE (reg
) == BLKmode
)
2141 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2142 update_live_1 (src
, XVECEXP (reg
, 0, i
));
2146 if (GET_CODE (reg
) != REG
)
2149 /* Global registers are always live, so the code below does not apply
2152 regno
= REGNO (reg
);
2154 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
2156 if (regno
< FIRST_PSEUDO_REGISTER
)
2158 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2161 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2163 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2165 SET_REGNO_REG_SET (BASIC_BLOCK (b
)->global_live_at_start
,
2172 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2174 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2176 SET_REGNO_REG_SET (BASIC_BLOCK (b
)->global_live_at_start
, regno
);
2183 /* Return 1 if insn can be speculatively moved from block src to trg,
2184 otherwise return 0. Called before first insertion of insn to
2185 ready-list or before the scheduling. */
2188 check_live (insn
, src
)
2192 /* Find the registers set by instruction. */
2193 if (GET_CODE (PATTERN (insn
)) == SET
2194 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2195 return check_live_1 (src
, PATTERN (insn
));
2196 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2199 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2200 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2201 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2202 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
2212 /* Update the live registers info after insn was moved speculatively from
2213 block src to trg. */
2216 update_live (insn
, src
)
2220 /* Find the registers set by instruction. */
2221 if (GET_CODE (PATTERN (insn
)) == SET
2222 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2223 update_live_1 (src
, PATTERN (insn
));
2224 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2227 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2228 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2229 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2230 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
2234 /* Exception Free Loads:
2236 We define five classes of speculative loads: IFREE, IRISKY,
2237 PFREE, PRISKY, and MFREE.
2239 IFREE loads are loads that are proved to be exception-free, just
2240 by examining the load insn. Examples for such loads are loads
2241 from TOC and loads of global data.
2243 IRISKY loads are loads that are proved to be exception-risky,
2244 just by examining the load insn. Examples for such loads are
2245 volatile loads and loads from shared memory.
2247 PFREE loads are loads for which we can prove, by examining other
2248 insns, that they are exception-free. Currently, this class consists
2249 of loads for which we are able to find a "similar load", either in
2250 the target block, or, if only one split-block exists, in that split
2251 block. Load2 is similar to load1 if both have same single base
2252 register. We identify only part of the similar loads, by finding
2253 an insn upon which both load1 and load2 have a DEF-USE dependence.
2255 PRISKY loads are loads for which we can prove, by examining other
2256 insns, that they are exception-risky. Currently we have two proofs for
2257 such loads. The first proof detects loads that are probably guarded by a
2258 test on the memory address. This proof is based on the
2259 backward and forward data dependence information for the region.
2260 Let load-insn be the examined load.
2261 Load-insn is PRISKY iff ALL the following hold:
2263 - insn1 is not in the same block as load-insn
2264 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2265 - test-insn is either a compare or a branch, not in the same block
2267 - load-insn is reachable from test-insn
2268 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2270 This proof might fail when the compare and the load are fed
2271 by an insn not in the region. To solve this, we will add to this
2272 group all loads that have no input DEF-USE dependence.
2274 The second proof detects loads that are directly or indirectly
2275 fed by a speculative load. This proof is affected by the
2276 scheduling process. We will use the flag fed_by_spec_load.
2277 Initially, all insns have this flag reset. After a speculative
2278 motion of an insn, if insn is either a load, or marked as
2279 fed_by_spec_load, we will also mark as fed_by_spec_load every
2280 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2281 load which is fed_by_spec_load is also PRISKY.
2283 MFREE (maybe-free) loads are all the remaining loads. They may be
2284 exception-free, but we cannot prove it.
2286 Now, all loads in IFREE and PFREE classes are considered
2287 exception-free, while all loads in IRISKY and PRISKY classes are
2288 considered exception-risky. As for loads in the MFREE class,
2289 these are considered either exception-free or exception-risky,
2290 depending on whether we are pessimistic or optimistic. We have
2291 to take the pessimistic approach to assure the safety of
2292 speculative scheduling, but we can take the optimistic approach
2293 by invoking the -fsched_spec_load_dangerous option. */
2295 enum INSN_TRAP_CLASS
2297 TRAP_FREE
= 0, IFREE
= 1, PFREE_CANDIDATE
= 2,
2298 PRISKY_CANDIDATE
= 3, IRISKY
= 4, TRAP_RISKY
= 5
2301 #define WORST_CLASS(class1, class2) \
2302 ((class1 > class2) ? class1 : class2)
2304 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between
2305 some speculatively moved load insn and this one. */
2306 char *fed_by_spec_load
;
2309 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2310 #define IS_REACHABLE(bb_from, bb_to) \
2312 || IS_RGN_ENTRY (bb_from) \
2313 || (bitset_member (ancestor_edges[bb_to], \
2314 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2316 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2317 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2319 /* Non-zero iff the address is comprised from at most 1 register. */
2320 #define CONST_BASED_ADDRESS_P(x) \
2321 (GET_CODE (x) == REG \
2322 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2323 || (GET_CODE (x) == LO_SUM)) \
2324 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2325 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2327 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2330 set_spec_fed (load_insn
)
2335 for (link
= INSN_DEPEND (load_insn
); link
; link
= XEXP (link
, 1))
2336 if (GET_MODE (link
) == VOIDmode
)
2337 FED_BY_SPEC_LOAD (XEXP (link
, 0)) = 1;
2338 } /* set_spec_fed */
2340 /* On the path from the insn to load_insn_bb, find a conditional
2341 branch depending on insn, that guards the speculative load. */
2344 find_conditional_protection (insn
, load_insn_bb
)
2350 /* Iterate through DEF-USE forward dependences. */
2351 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
2353 rtx next
= XEXP (link
, 0);
2354 if ((CONTAINING_RGN (INSN_BLOCK (next
)) ==
2355 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
2356 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
2357 && load_insn_bb
!= INSN_BB (next
)
2358 && GET_MODE (link
) == VOIDmode
2359 && (GET_CODE (next
) == JUMP_INSN
2360 || find_conditional_protection (next
, load_insn_bb
)))
2364 } /* find_conditional_protection */
2366 /* Returns 1 if the same insn1 that participates in the computation
2367 of load_insn's address is feeding a conditional branch that is
2368 guarding on load_insn. This is true if we find a the two DEF-USE
2370 insn1 -> ... -> conditional-branch
2371 insn1 -> ... -> load_insn,
2372 and if a flow path exist:
2373 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2374 and if insn1 is on the path
2375 region-entry -> ... -> bb_trg -> ... load_insn.
2377 Locate insn1 by climbing on LOG_LINKS from load_insn.
2378 Locate the branch by following INSN_DEPEND from insn1. */
2381 is_conditionally_protected (load_insn
, bb_src
, bb_trg
)
2387 for (link
= LOG_LINKS (load_insn
); link
; link
= XEXP (link
, 1))
2389 rtx insn1
= XEXP (link
, 0);
2391 /* Must be a DEF-USE dependence upon non-branch. */
2392 if (GET_MODE (link
) != VOIDmode
2393 || GET_CODE (insn1
) == JUMP_INSN
)
2396 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
2397 if (INSN_BB (insn1
) == bb_src
2398 || (CONTAINING_RGN (INSN_BLOCK (insn1
))
2399 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
2400 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
2401 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
2404 /* Now search for the conditional-branch. */
2405 if (find_conditional_protection (insn1
, bb_src
))
2408 /* Recursive step: search another insn1, "above" current insn1. */
2409 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
2412 /* The chain does not exist. */
2414 } /* is_conditionally_protected */
2416 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2417 load_insn can move speculatively from bb_src to bb_trg. All the
2418 following must hold:
2420 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2421 (2) load_insn and load1 have a def-use dependence upon
2422 the same insn 'insn1'.
2423 (3) either load2 is in bb_trg, or:
2424 - there's only one split-block, and
2425 - load1 is on the escape path, and
2427 From all these we can conclude that the two loads access memory
2428 addresses that differ at most by a constant, and hence if moving
2429 load_insn would cause an exception, it would have been caused by
2433 is_pfree (load_insn
, bb_src
, bb_trg
)
2438 register candidate
*candp
= candidate_table
+ bb_src
;
2440 if (candp
->split_bbs
.nr_members
!= 1)
2441 /* Must have exactly one escape block. */
2444 for (back_link
= LOG_LINKS (load_insn
);
2445 back_link
; back_link
= XEXP (back_link
, 1))
2447 rtx insn1
= XEXP (back_link
, 0);
2449 if (GET_MODE (back_link
) == VOIDmode
)
2451 /* Found a DEF-USE dependence (insn1, load_insn). */
2454 for (fore_link
= INSN_DEPEND (insn1
);
2455 fore_link
; fore_link
= XEXP (fore_link
, 1))
2457 rtx insn2
= XEXP (fore_link
, 0);
2458 if (GET_MODE (fore_link
) == VOIDmode
)
2460 /* Found a DEF-USE dependence (insn1, insn2). */
2461 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
2462 /* insn2 not guaranteed to be a 1 base reg load. */
2465 if (INSN_BB (insn2
) == bb_trg
)
2466 /* insn2 is the similar load, in the target block. */
2469 if (*(candp
->split_bbs
.first_member
) == INSN_BLOCK (insn2
))
2470 /* insn2 is a similar load, in a split-block. */
2477 /* Couldn't find a similar load. */
2481 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2482 as found by analyzing insn's expression. */
2485 may_trap_exp (x
, is_store
)
2493 code
= GET_CODE (x
);
2503 /* The insn uses memory: a volatile load. */
2504 if (MEM_VOLATILE_P (x
))
2506 /* An exception-free load. */
2507 if (!may_trap_p (x
))
2509 /* A load with 1 base register, to be further checked. */
2510 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
2511 return PFREE_CANDIDATE
;
2512 /* No info on the load, to be further checked. */
2513 return PRISKY_CANDIDATE
;
2518 int i
, insn_class
= TRAP_FREE
;
2520 /* Neither store nor load, check if it may cause a trap. */
2523 /* Recursive step: walk the insn... */
2524 fmt
= GET_RTX_FORMAT (code
);
2525 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2529 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
2530 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2532 else if (fmt
[i
] == 'E')
2535 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2537 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
2538 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2539 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2543 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2548 } /* may_trap_exp */
2551 /* Classifies insn for the purpose of verifying that it can be
2552 moved speculatively, by examining it's patterns, returning:
2553 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2554 TRAP_FREE: non-load insn.
2555 IFREE: load from a globaly safe location.
2556 IRISKY: volatile load.
2557 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2558 being either PFREE or PRISKY. */
2561 haifa_classify_insn (insn
)
2564 rtx pat
= PATTERN (insn
);
2565 int tmp_class
= TRAP_FREE
;
2566 int insn_class
= TRAP_FREE
;
2569 if (GET_CODE (pat
) == PARALLEL
)
2571 int i
, len
= XVECLEN (pat
, 0);
2573 for (i
= len
- 1; i
>= 0; i
--)
2575 code
= GET_CODE (XVECEXP (pat
, 0, i
));
2579 /* Test if it is a 'store'. */
2580 tmp_class
= may_trap_exp (XEXP (XVECEXP (pat
, 0, i
), 0), 1);
2583 /* Test if it is a store. */
2584 tmp_class
= may_trap_exp (SET_DEST (XVECEXP (pat
, 0, i
)), 1);
2585 if (tmp_class
== TRAP_RISKY
)
2587 /* Test if it is a load. */
2589 WORST_CLASS (tmp_class
,
2590 may_trap_exp (SET_SRC (XVECEXP (pat
, 0, i
)), 0));
2593 tmp_class
= TRAP_RISKY
;
2597 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2598 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2604 code
= GET_CODE (pat
);
2608 /* Test if it is a 'store'. */
2609 tmp_class
= may_trap_exp (XEXP (pat
, 0), 1);
2612 /* Test if it is a store. */
2613 tmp_class
= may_trap_exp (SET_DEST (pat
), 1);
2614 if (tmp_class
== TRAP_RISKY
)
2616 /* Test if it is a load. */
2618 WORST_CLASS (tmp_class
,
2619 may_trap_exp (SET_SRC (pat
), 0));
2622 tmp_class
= TRAP_RISKY
;
2626 insn_class
= tmp_class
;
2631 } /* haifa_classify_insn */
2633 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2634 a load moved speculatively, or if load_insn is protected by
2635 a compare on load_insn's address). */
2638 is_prisky (load_insn
, bb_src
, bb_trg
)
2642 if (FED_BY_SPEC_LOAD (load_insn
))
2645 if (LOG_LINKS (load_insn
) == NULL
)
2646 /* Dependence may 'hide' out of the region. */
2649 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2655 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2656 Return 1 if insn is exception-free (and the motion is valid)
2660 is_exception_free (insn
, bb_src
, bb_trg
)
2664 int insn_class
= haifa_classify_insn (insn
);
2666 /* Handle non-load insns. */
2677 if (!flag_schedule_speculative_load
)
2679 IS_LOAD_INSN (insn
) = 1;
2686 case PFREE_CANDIDATE
:
2687 if (is_pfree (insn
, bb_src
, bb_trg
))
2689 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2690 case PRISKY_CANDIDATE
:
2691 if (!flag_schedule_speculative_load_dangerous
2692 || is_prisky (insn
, bb_src
, bb_trg
))
2698 return flag_schedule_speculative_load_dangerous
;
2699 } /* is_exception_free */
2702 /* Process an insn's memory dependencies. There are four kinds of
2705 (0) read dependence: read follows read
2706 (1) true dependence: read follows write
2707 (2) anti dependence: write follows read
2708 (3) output dependence: write follows write
2710 We are careful to build only dependencies which actually exist, and
2711 use transitivity to avoid building too many links. */
2713 /* Return the INSN_LIST containing INSN in LIST, or NULL
2714 if LIST does not contain INSN. */
2716 HAIFA_INLINE
static rtx
2717 find_insn_list (insn
, list
)
2723 if (XEXP (list
, 0) == insn
)
2725 list
= XEXP (list
, 1);
2731 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0
2734 HAIFA_INLINE
static char
2735 find_insn_mem_list (insn
, x
, list
, list1
)
2741 if (XEXP (list
, 0) == insn
2742 && XEXP (list1
, 0) == x
)
2744 list
= XEXP (list
, 1);
2745 list1
= XEXP (list1
, 1);
2751 /* Compute the function units used by INSN. This caches the value
2752 returned by function_units_used. A function unit is encoded as the
2753 unit number if the value is non-negative and the compliment of a
2754 mask if the value is negative. A function unit index is the
2755 non-negative encoding. */
2757 HAIFA_INLINE
static int
2761 register int unit
= INSN_UNIT (insn
);
2765 recog_memoized (insn
);
2767 /* A USE insn, or something else we don't need to understand.
2768 We can't pass these directly to function_units_used because it will
2769 trigger a fatal error for unrecognizable insns. */
2770 if (INSN_CODE (insn
) < 0)
2774 unit
= function_units_used (insn
);
2775 /* Increment non-negative values so we can cache zero. */
2779 /* We only cache 16 bits of the result, so if the value is out of
2780 range, don't cache it. */
2781 if (FUNCTION_UNITS_SIZE
< HOST_BITS_PER_SHORT
2783 || (unit
& ~((1 << (HOST_BITS_PER_SHORT
- 1)) - 1)) == 0)
2784 INSN_UNIT (insn
) = unit
;
2786 return (unit
> 0 ? unit
- 1 : unit
);
2789 /* Compute the blockage range for executing INSN on UNIT. This caches
2790 the value returned by the blockage_range_function for the unit.
2791 These values are encoded in an int where the upper half gives the
2792 minimum value and the lower half gives the maximum value. */
2794 HAIFA_INLINE
static unsigned int
2795 blockage_range (unit
, insn
)
2799 unsigned int blockage
= INSN_BLOCKAGE (insn
);
2802 if ((int) UNIT_BLOCKED (blockage
) != unit
+ 1)
2804 range
= function_units
[unit
].blockage_range_function (insn
);
2805 /* We only cache the blockage range for one unit and then only if
2807 if (HOST_BITS_PER_INT
>= UNIT_BITS
+ 2 * BLOCKAGE_BITS
)
2808 INSN_BLOCKAGE (insn
) = ENCODE_BLOCKAGE (unit
+ 1, range
);
2811 range
= BLOCKAGE_RANGE (blockage
);
2816 /* A vector indexed by function unit instance giving the last insn to use
2817 the unit. The value of the function unit instance index for unit U
2818 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2819 static rtx unit_last_insn
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2821 /* A vector indexed by function unit instance giving the minimum time when
2822 the unit will unblock based on the maximum blockage cost. */
2823 static int unit_tick
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2825 /* A vector indexed by function unit number giving the number of insns
2826 that remain to use the unit. */
2827 static int unit_n_insns
[FUNCTION_UNITS_SIZE
];
2829 /* Reset the function unit state to the null state. */
2834 bzero ((char *) unit_last_insn
, sizeof (unit_last_insn
));
2835 bzero ((char *) unit_tick
, sizeof (unit_tick
));
2836 bzero ((char *) unit_n_insns
, sizeof (unit_n_insns
));
2839 /* Return the issue-delay of an insn. */
2841 HAIFA_INLINE
static int
2842 insn_issue_delay (insn
)
2846 int unit
= insn_unit (insn
);
2848 /* Efficiency note: in fact, we are working 'hard' to compute a
2849 value that was available in md file, and is not available in
2850 function_units[] structure. It would be nice to have this
2851 value there, too. */
2854 if (function_units
[unit
].blockage_range_function
&&
2855 function_units
[unit
].blockage_function
)
2856 delay
= function_units
[unit
].blockage_function (insn
, insn
);
2859 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2860 if ((unit
& 1) != 0 && function_units
[i
].blockage_range_function
2861 && function_units
[i
].blockage_function
)
2862 delay
= MAX (delay
, function_units
[i
].blockage_function (insn
, insn
));
2867 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2868 instance INSTANCE at time CLOCK if the previous actual hazard cost
2871 HAIFA_INLINE
static int
2872 actual_hazard_this_instance (unit
, instance
, insn
, clock
, cost
)
2873 int unit
, instance
, clock
, cost
;
2876 int tick
= unit_tick
[instance
]; /* Issue time of the last issued insn. */
2878 if (tick
- clock
> cost
)
2880 /* The scheduler is operating forward, so unit's last insn is the
2881 executing insn and INSN is the candidate insn. We want a
2882 more exact measure of the blockage if we execute INSN at CLOCK
2883 given when we committed the execution of the unit's last insn.
2885 The blockage value is given by either the unit's max blockage
2886 constant, blockage range function, or blockage function. Use
2887 the most exact form for the given unit. */
2889 if (function_units
[unit
].blockage_range_function
)
2891 if (function_units
[unit
].blockage_function
)
2892 tick
+= (function_units
[unit
].blockage_function
2893 (unit_last_insn
[instance
], insn
)
2894 - function_units
[unit
].max_blockage
);
2896 tick
+= ((int) MAX_BLOCKAGE_COST (blockage_range (unit
, insn
))
2897 - function_units
[unit
].max_blockage
);
2899 if (tick
- clock
> cost
)
2900 cost
= tick
- clock
;
2905 /* Record INSN as having begun execution on the units encoded by UNIT at
2908 HAIFA_INLINE
static void
2909 schedule_unit (unit
, insn
, clock
)
2917 int instance
= unit
;
2918 #if MAX_MULTIPLICITY > 1
2919 /* Find the first free instance of the function unit and use that
2920 one. We assume that one is free. */
2921 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
2923 if (!actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
2925 instance
+= FUNCTION_UNITS_SIZE
;
2928 unit_last_insn
[instance
] = insn
;
2929 unit_tick
[instance
] = (clock
+ function_units
[unit
].max_blockage
);
2932 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2933 if ((unit
& 1) != 0)
2934 schedule_unit (i
, insn
, clock
);
2937 /* Return the actual hazard cost of executing INSN on the units encoded by
2938 UNIT at time CLOCK if the previous actual hazard cost was COST. */
2940 HAIFA_INLINE
static int
2941 actual_hazard (unit
, insn
, clock
, cost
)
2942 int unit
, clock
, cost
;
2949 /* Find the instance of the function unit with the minimum hazard. */
2950 int instance
= unit
;
2951 int best_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
2955 #if MAX_MULTIPLICITY > 1
2956 if (best_cost
> cost
)
2958 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
2960 instance
+= FUNCTION_UNITS_SIZE
;
2961 this_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
2963 if (this_cost
< best_cost
)
2965 best_cost
= this_cost
;
2966 if (this_cost
<= cost
)
2972 cost
= MAX (cost
, best_cost
);
2975 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2976 if ((unit
& 1) != 0)
2977 cost
= actual_hazard (i
, insn
, clock
, cost
);
2982 /* Return the potential hazard cost of executing an instruction on the
2983 units encoded by UNIT if the previous potential hazard cost was COST.
2984 An insn with a large blockage time is chosen in preference to one
2985 with a smaller time; an insn that uses a unit that is more likely
2986 to be used is chosen in preference to one with a unit that is less
2987 used. We are trying to minimize a subsequent actual hazard. */
2989 HAIFA_INLINE
static int
2990 potential_hazard (unit
, insn
, cost
)
2995 unsigned int minb
, maxb
;
2999 minb
= maxb
= function_units
[unit
].max_blockage
;
3002 if (function_units
[unit
].blockage_range_function
)
3004 maxb
= minb
= blockage_range (unit
, insn
);
3005 maxb
= MAX_BLOCKAGE_COST (maxb
);
3006 minb
= MIN_BLOCKAGE_COST (minb
);
3011 /* Make the number of instructions left dominate. Make the
3012 minimum delay dominate the maximum delay. If all these
3013 are the same, use the unit number to add an arbitrary
3014 ordering. Other terms can be added. */
3015 ncost
= minb
* 0x40 + maxb
;
3016 ncost
*= (unit_n_insns
[unit
] - 1) * 0x1000 + unit
;
3023 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3024 if ((unit
& 1) != 0)
3025 cost
= potential_hazard (i
, insn
, cost
);
3030 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3031 This is the number of cycles between instruction issue and
3032 instruction results. */
3034 HAIFA_INLINE
static int
3035 insn_cost (insn
, link
, used
)
3036 rtx insn
, link
, used
;
3038 register int cost
= INSN_COST (insn
);
3042 recog_memoized (insn
);
3044 /* A USE insn, or something else we don't need to understand.
3045 We can't pass these directly to result_ready_cost because it will
3046 trigger a fatal error for unrecognizable insns. */
3047 if (INSN_CODE (insn
) < 0)
3049 INSN_COST (insn
) = 1;
3054 cost
= result_ready_cost (insn
);
3059 INSN_COST (insn
) = cost
;
3063 /* In this case estimate cost without caring how insn is used. */
3064 if (link
== 0 && used
== 0)
3067 /* A USE insn should never require the value used to be computed. This
3068 allows the computation of a function's result and parameter values to
3069 overlap the return and call. */
3070 recog_memoized (used
);
3071 if (INSN_CODE (used
) < 0)
3072 LINK_COST_FREE (link
) = 1;
3074 /* If some dependencies vary the cost, compute the adjustment. Most
3075 commonly, the adjustment is complete: either the cost is ignored
3076 (in the case of an output- or anti-dependence), or the cost is
3077 unchanged. These values are cached in the link as LINK_COST_FREE
3078 and LINK_COST_ZERO. */
3080 if (LINK_COST_FREE (link
))
3083 else if (!LINK_COST_ZERO (link
))
3087 ADJUST_COST (used
, link
, insn
, ncost
);
3090 LINK_COST_FREE (link
) = 1;
3094 LINK_COST_ZERO (link
) = 1;
3101 /* Compute the priority number for INSN. */
3110 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
3113 if ((this_priority
= INSN_PRIORITY (insn
)) == 0)
3115 if (INSN_DEPEND (insn
) == 0)
3116 this_priority
= insn_cost (insn
, 0, 0);
3118 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
3123 if (RTX_INTEGRATED_P (link
))
3126 next
= XEXP (link
, 0);
3128 /* Critical path is meaningful in block boundaries only. */
3129 if (INSN_BLOCK (next
) != INSN_BLOCK (insn
))
3132 next_priority
= insn_cost (insn
, link
, next
) + priority (next
);
3133 if (next_priority
> this_priority
)
3134 this_priority
= next_priority
;
3136 INSN_PRIORITY (insn
) = this_priority
;
3138 return this_priority
;
3142 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3143 them to the unused_*_list variables, so that they can be reused. */
3146 free_pending_lists ()
3148 if (current_nr_blocks
<= 1)
3150 free_INSN_LIST_list (&pending_read_insns
);
3151 free_INSN_LIST_list (&pending_write_insns
);
3152 free_EXPR_LIST_list (&pending_read_mems
);
3153 free_EXPR_LIST_list (&pending_write_mems
);
3157 /* Interblock scheduling. */
3160 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3162 free_INSN_LIST_list (&bb_pending_read_insns
[bb
]);
3163 free_INSN_LIST_list (&bb_pending_write_insns
[bb
]);
3164 free_EXPR_LIST_list (&bb_pending_read_mems
[bb
]);
3165 free_EXPR_LIST_list (&bb_pending_write_mems
[bb
]);
3170 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3171 The MEM is a memory reference contained within INSN, which we are saving
3172 so that we can do memory aliasing on it. */
3175 add_insn_mem_dependence (insn_list
, mem_list
, insn
, mem
)
3176 rtx
*insn_list
, *mem_list
, insn
, mem
;
3180 link
= alloc_INSN_LIST (insn
, *insn_list
);
3183 link
= alloc_EXPR_LIST (VOIDmode
, mem
, *mem_list
);
3186 pending_lists_length
++;
3190 /* Make a dependency between every memory reference on the pending lists
3191 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3195 flush_pending_lists (insn
, only_write
)
3202 while (pending_read_insns
&& ! only_write
)
3204 add_dependence (insn
, XEXP (pending_read_insns
, 0), REG_DEP_ANTI
);
3206 link
= pending_read_insns
;
3207 pending_read_insns
= XEXP (pending_read_insns
, 1);
3208 free_INSN_LIST_node (link
);
3210 link
= pending_read_mems
;
3211 pending_read_mems
= XEXP (pending_read_mems
, 1);
3212 free_EXPR_LIST_node (link
);
3214 while (pending_write_insns
)
3216 add_dependence (insn
, XEXP (pending_write_insns
, 0), REG_DEP_ANTI
);
3218 link
= pending_write_insns
;
3219 pending_write_insns
= XEXP (pending_write_insns
, 1);
3220 free_INSN_LIST_node (link
);
3222 link
= pending_write_mems
;
3223 pending_write_mems
= XEXP (pending_write_mems
, 1);
3224 free_EXPR_LIST_node (link
);
3226 pending_lists_length
= 0;
3228 /* last_pending_memory_flush is now a list of insns. */
3229 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3230 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3232 free_INSN_LIST_list (&last_pending_memory_flush
);
3233 last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
3236 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
3237 by the write to the destination of X, and reads of everything mentioned. */
3240 sched_analyze_1 (x
, insn
)
3245 register rtx dest
= SET_DEST (x
);
3246 enum rtx_code code
= GET_CODE (x
);
3251 if (GET_CODE (dest
) == PARALLEL
3252 && GET_MODE (dest
) == BLKmode
)
3255 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
3256 sched_analyze_1 (XVECEXP (dest
, 0, i
), insn
);
3257 if (GET_CODE (x
) == SET
)
3258 sched_analyze_2 (SET_SRC (x
), insn
);
3262 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
3263 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3265 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3267 /* The second and third arguments are values read by this insn. */
3268 sched_analyze_2 (XEXP (dest
, 1), insn
);
3269 sched_analyze_2 (XEXP (dest
, 2), insn
);
3271 dest
= SUBREG_REG (dest
);
3274 if (GET_CODE (dest
) == REG
)
3278 regno
= REGNO (dest
);
3280 /* A hard reg in a wide mode may really be multiple registers.
3281 If so, mark all of them just like the first. */
3282 if (regno
< FIRST_PSEUDO_REGISTER
)
3284 i
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
3289 for (u
= reg_last_uses
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3290 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3292 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3293 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3295 /* Clobbers need not be ordered with respect to one
3296 another, but sets must be ordered with respect to a
3300 free_INSN_LIST_list (®_last_uses
[regno
+ i
]);
3301 for (u
= reg_last_clobbers
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3302 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3303 SET_REGNO_REG_SET (reg_pending_sets
, regno
+ i
);
3306 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
+ i
);
3308 /* Function calls clobber all call_used regs. */
3309 if (global_regs
[regno
+ i
]
3310 || (code
== SET
&& call_used_regs
[regno
+ i
]))
3311 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3312 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3319 for (u
= reg_last_uses
[regno
]; u
; u
= XEXP (u
, 1))
3320 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3322 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3323 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3327 free_INSN_LIST_list (®_last_uses
[regno
]);
3328 for (u
= reg_last_clobbers
[regno
]; u
; u
= XEXP (u
, 1))
3329 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3330 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
3333 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
3335 /* Pseudos that are REG_EQUIV to something may be replaced
3336 by that during reloading. We need only add dependencies for
3337 the address in the REG_EQUIV note. */
3338 if (!reload_completed
3339 && reg_known_equiv_p
[regno
]
3340 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3341 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3343 /* Don't let it cross a call after scheduling if it doesn't
3344 already cross one. */
3346 if (REG_N_CALLS_CROSSED (regno
) == 0)
3347 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3348 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3351 else if (GET_CODE (dest
) == MEM
)
3353 /* Writing memory. */
3355 if (pending_lists_length
> 32)
3357 /* Flush all pending reads and writes to prevent the pending lists
3358 from getting any larger. Insn scheduling runs too slowly when
3359 these lists get long. The number 32 was chosen because it
3360 seems like a reasonable number. When compiling GCC with itself,
3361 this flush occurs 8 times for sparc, and 10 times for m88k using
3363 flush_pending_lists (insn
, 0);
3368 rtx pending
, pending_mem
;
3370 pending
= pending_read_insns
;
3371 pending_mem
= pending_read_mems
;
3374 if (anti_dependence (XEXP (pending_mem
, 0), dest
))
3375 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3377 pending
= XEXP (pending
, 1);
3378 pending_mem
= XEXP (pending_mem
, 1);
3381 pending
= pending_write_insns
;
3382 pending_mem
= pending_write_mems
;
3385 if (output_dependence (XEXP (pending_mem
, 0), dest
))
3386 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
3388 pending
= XEXP (pending
, 1);
3389 pending_mem
= XEXP (pending_mem
, 1);
3392 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3393 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3395 add_insn_mem_dependence (&pending_write_insns
, &pending_write_mems
,
3398 sched_analyze_2 (XEXP (dest
, 0), insn
);
3401 /* Analyze reads. */
3402 if (GET_CODE (x
) == SET
)
3403 sched_analyze_2 (SET_SRC (x
), insn
);
3406 /* Analyze the uses of memory and registers in rtx X in INSN. */
3409 sched_analyze_2 (x
, insn
)
3415 register enum rtx_code code
;
3416 register const char *fmt
;
3421 code
= GET_CODE (x
);
3430 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3431 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3432 this does not mean that this insn is using cc0. */
3440 /* User of CC0 depends on immediately preceding insn. */
3441 SCHED_GROUP_P (insn
) = 1;
3443 /* There may be a note before this insn now, but all notes will
3444 be removed before we actually try to schedule the insns, so
3445 it won't cause a problem later. We must avoid it here though. */
3446 prev
= prev_nonnote_insn (insn
);
3448 /* Make a copy of all dependencies on the immediately previous insn,
3449 and add to this insn. This is so that all the dependencies will
3450 apply to the group. Remove an explicit dependence on this insn
3451 as SCHED_GROUP_P now represents it. */
3453 if (find_insn_list (prev
, LOG_LINKS (insn
)))
3454 remove_dependence (insn
, prev
);
3456 for (link
= LOG_LINKS (prev
); link
; link
= XEXP (link
, 1))
3457 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3466 int regno
= REGNO (x
);
3467 if (regno
< FIRST_PSEUDO_REGISTER
)
3471 i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
3474 reg_last_uses
[regno
+ i
]
3475 = alloc_INSN_LIST (insn
, reg_last_uses
[regno
+ i
]);
3477 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3478 add_dependence (insn
, XEXP (u
, 0), 0);
3480 /* ??? This should never happen. */
3481 for (u
= reg_last_clobbers
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3482 add_dependence (insn
, XEXP (u
, 0), 0);
3484 if ((call_used_regs
[regno
+ i
] || global_regs
[regno
+ i
]))
3485 /* Function calls clobber all call_used regs. */
3486 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3487 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3492 reg_last_uses
[regno
] = alloc_INSN_LIST (insn
,
3493 reg_last_uses
[regno
]);
3495 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3496 add_dependence (insn
, XEXP (u
, 0), 0);
3498 /* ??? This should never happen. */
3499 for (u
= reg_last_clobbers
[regno
]; u
; u
= XEXP (u
, 1))
3500 add_dependence (insn
, XEXP (u
, 0), 0);
3502 /* Pseudos that are REG_EQUIV to something may be replaced
3503 by that during reloading. We need only add dependencies for
3504 the address in the REG_EQUIV note. */
3505 if (!reload_completed
3506 && reg_known_equiv_p
[regno
]
3507 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3508 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3510 /* If the register does not already cross any calls, then add this
3511 insn to the sched_before_next_call list so that it will still
3512 not cross calls after scheduling. */
3513 if (REG_N_CALLS_CROSSED (regno
) == 0)
3514 add_dependence (sched_before_next_call
, insn
, REG_DEP_ANTI
);
3521 /* Reading memory. */
3523 rtx pending
, pending_mem
;
3525 pending
= pending_read_insns
;
3526 pending_mem
= pending_read_mems
;
3529 if (read_dependence (XEXP (pending_mem
, 0), x
))
3530 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3532 pending
= XEXP (pending
, 1);
3533 pending_mem
= XEXP (pending_mem
, 1);
3536 pending
= pending_write_insns
;
3537 pending_mem
= pending_write_mems
;
3540 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
3542 add_dependence (insn
, XEXP (pending
, 0), 0);
3544 pending
= XEXP (pending
, 1);
3545 pending_mem
= XEXP (pending_mem
, 1);
3548 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3549 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3551 /* Always add these dependencies to pending_reads, since
3552 this insn may be followed by a write. */
3553 add_insn_mem_dependence (&pending_read_insns
, &pending_read_mems
,
3556 /* Take advantage of tail recursion here. */
3557 sched_analyze_2 (XEXP (x
, 0), insn
);
3561 /* Force pending stores to memory in case a trap handler needs them. */
3563 flush_pending_lists (insn
, 1);
3568 case UNSPEC_VOLATILE
:
3572 /* Traditional and volatile asm instructions must be considered to use
3573 and clobber all hard registers, all pseudo-registers and all of
3574 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3576 Consider for instance a volatile asm that changes the fpu rounding
3577 mode. An insn should not be moved across this even if it only uses
3578 pseudo-regs because it might give an incorrectly rounded result. */
3579 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
3581 int max_reg
= max_reg_num ();
3582 for (i
= 0; i
< max_reg
; i
++)
3584 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3585 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3586 free_INSN_LIST_list (®_last_uses
[i
]);
3588 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3589 add_dependence (insn
, XEXP (u
, 0), 0);
3591 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3592 add_dependence (insn
, XEXP (u
, 0), 0);
3594 reg_pending_sets_all
= 1;
3596 flush_pending_lists (insn
, 0);
3599 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3600 We can not just fall through here since then we would be confused
3601 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3602 traditional asms unlike their normal usage. */
3604 if (code
== ASM_OPERANDS
)
3606 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
3607 sched_analyze_2 (ASM_OPERANDS_INPUT (x
, j
), insn
);
3617 /* These both read and modify the result. We must handle them as writes
3618 to get proper dependencies for following instructions. We must handle
3619 them as reads to get proper dependencies from this to previous
3620 instructions. Thus we need to pass them to both sched_analyze_1
3621 and sched_analyze_2. We must call sched_analyze_2 first in order
3622 to get the proper antecedent for the read. */
3623 sched_analyze_2 (XEXP (x
, 0), insn
);
3624 sched_analyze_1 (x
, insn
);
3631 /* Other cases: walk the insn. */
3632 fmt
= GET_RTX_FORMAT (code
);
3633 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3636 sched_analyze_2 (XEXP (x
, i
), insn
);
3637 else if (fmt
[i
] == 'E')
3638 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3639 sched_analyze_2 (XVECEXP (x
, i
, j
), insn
);
3643 /* Analyze an INSN with pattern X to find all dependencies. */
3646 sched_analyze_insn (x
, insn
, loop_notes
)
3650 register RTX_CODE code
= GET_CODE (x
);
3652 int maxreg
= max_reg_num ();
3655 if (code
== SET
|| code
== CLOBBER
)
3656 sched_analyze_1 (x
, insn
);
3657 else if (code
== PARALLEL
)
3660 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
3662 code
= GET_CODE (XVECEXP (x
, 0, i
));
3663 if (code
== SET
|| code
== CLOBBER
)
3664 sched_analyze_1 (XVECEXP (x
, 0, i
), insn
);
3666 sched_analyze_2 (XVECEXP (x
, 0, i
), insn
);
3670 sched_analyze_2 (x
, insn
);
3672 /* Mark registers CLOBBERED or used by called function. */
3673 if (GET_CODE (insn
) == CALL_INSN
)
3674 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
3676 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
3677 sched_analyze_1 (XEXP (link
, 0), insn
);
3679 sched_analyze_2 (XEXP (link
, 0), insn
);
3682 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3683 block, then we must be sure that no instructions are scheduled across it.
3684 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3685 become incorrect. */
3689 int max_reg
= max_reg_num ();
3690 int schedule_barrier_found
= 0;
3693 /* Update loop_notes with any notes from this insn. Also determine
3694 if any of the notes on the list correspond to instruction scheduling
3695 barriers (loop, eh & setjmp notes, but not range notes. */
3697 while (XEXP (link
, 1))
3699 if (INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_BEG
3700 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_END
3701 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_BEG
3702 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_END
3703 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_SETJMP
)
3704 schedule_barrier_found
= 1;
3706 link
= XEXP (link
, 1);
3708 XEXP (link
, 1) = REG_NOTES (insn
);
3709 REG_NOTES (insn
) = loop_notes
;
3711 /* Add dependencies if a scheduling barrier was found. */
3712 if (schedule_barrier_found
)
3714 for (i
= 0; i
< max_reg
; i
++)
3717 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3718 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3719 free_INSN_LIST_list (®_last_uses
[i
]);
3721 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3722 add_dependence (insn
, XEXP (u
, 0), 0);
3724 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3725 add_dependence (insn
, XEXP (u
, 0), 0);
3727 reg_pending_sets_all
= 1;
3729 flush_pending_lists (insn
, 0);
3734 /* Accumulate clobbers until the next set so that it will be output dependent
3735 on all of them. At the next set we can clear the clobber list, since
3736 subsequent sets will be output dependent on it. */
3737 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
3739 free_INSN_LIST_list (®_last_sets
[i
]);
3740 free_INSN_LIST_list (®_last_clobbers
[i
]);
3742 = alloc_INSN_LIST (insn
, NULL_RTX
);
3744 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
,
3746 reg_last_clobbers
[i
]
3747 = alloc_INSN_LIST (insn
,
3748 reg_last_clobbers
[i
]);
3750 CLEAR_REG_SET (reg_pending_sets
);
3751 CLEAR_REG_SET (reg_pending_clobbers
);
3753 if (reg_pending_sets_all
)
3755 for (i
= 0; i
< maxreg
; i
++)
3757 free_INSN_LIST_list (®_last_sets
[i
]);
3758 reg_last_sets
[i
] = alloc_INSN_LIST (insn
, NULL_RTX
);
3761 reg_pending_sets_all
= 0;
3764 /* Handle function calls and function returns created by the epilogue
3766 if (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3771 /* When scheduling instructions, we make sure calls don't lose their
3772 accompanying USE insns by depending them one on another in order.
3774 Also, we must do the same thing for returns created by the epilogue
3775 threading code. Note this code works only in this special case,
3776 because other passes make no guarantee that they will never emit
3777 an instruction between a USE and a RETURN. There is such a guarantee
3778 for USE instructions immediately before a call. */
3780 prev_dep_insn
= insn
;
3781 dep_insn
= PREV_INSN (insn
);
3782 while (GET_CODE (dep_insn
) == INSN
3783 && GET_CODE (PATTERN (dep_insn
)) == USE
3784 && GET_CODE (XEXP (PATTERN (dep_insn
), 0)) == REG
)
3786 SCHED_GROUP_P (prev_dep_insn
) = 1;
3788 /* Make a copy of all dependencies on dep_insn, and add to insn.
3789 This is so that all of the dependencies will apply to the
3792 for (link
= LOG_LINKS (dep_insn
); link
; link
= XEXP (link
, 1))
3793 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3795 prev_dep_insn
= dep_insn
;
3796 dep_insn
= PREV_INSN (dep_insn
);
3801 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3802 for every dependency. */
3805 sched_analyze (head
, tail
)
3812 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3814 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3816 /* Clear out the stale LOG_LINKS from flow. */
3817 free_INSN_LIST_list (&LOG_LINKS (insn
));
3819 /* Make each JUMP_INSN a scheduling barrier for memory
3821 if (GET_CODE (insn
) == JUMP_INSN
)
3822 last_pending_memory_flush
3823 = alloc_INSN_LIST (insn
, last_pending_memory_flush
);
3824 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3827 else if (GET_CODE (insn
) == CALL_INSN
)
3832 CANT_MOVE (insn
) = 1;
3834 /* Clear out the stale LOG_LINKS from flow. */
3835 free_INSN_LIST_list (&LOG_LINKS (insn
));
3837 /* Any instruction using a hard register which may get clobbered
3838 by a call needs to be marked as dependent on this call.
3839 This prevents a use of a hard return reg from being moved
3840 past a void call (i.e. it does not explicitly set the hard
3843 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3844 all registers, not just hard registers, may be clobbered by this
3847 /* Insn, being a CALL_INSN, magically depends on
3848 `last_function_call' already. */
3850 if (NEXT_INSN (insn
) && GET_CODE (NEXT_INSN (insn
)) == NOTE
3851 && NOTE_LINE_NUMBER (NEXT_INSN (insn
)) == NOTE_INSN_SETJMP
)
3853 int max_reg
= max_reg_num ();
3854 for (i
= 0; i
< max_reg
; i
++)
3856 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3857 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3858 free_INSN_LIST_list (®_last_uses
[i
]);
3860 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3861 add_dependence (insn
, XEXP (u
, 0), 0);
3863 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3864 add_dependence (insn
, XEXP (u
, 0), 0);
3866 reg_pending_sets_all
= 1;
3868 /* Add a pair of fake REG_NOTEs which we will later
3869 convert back into a NOTE_INSN_SETJMP note. See
3870 reemit_notes for why we use a pair of NOTEs. */
3871 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_DEAD
,
3874 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_DEAD
,
3875 GEN_INT (NOTE_INSN_SETJMP
),
3880 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3881 if (call_used_regs
[i
] || global_regs
[i
])
3883 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3884 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3886 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3887 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3889 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3893 /* For each insn which shouldn't cross a call, add a dependence
3894 between that insn and this call insn. */
3895 x
= LOG_LINKS (sched_before_next_call
);
3898 add_dependence (insn
, XEXP (x
, 0), REG_DEP_ANTI
);
3901 LOG_LINKS (sched_before_next_call
) = 0;
3903 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3906 /* In the absence of interprocedural alias analysis, we must flush
3907 all pending reads and writes, and start new dependencies starting
3908 from here. But only flush writes for constant calls (which may
3909 be passed a pointer to something we haven't written yet). */
3910 flush_pending_lists (insn
, CONST_CALL_P (insn
));
3912 /* Depend this function call (actually, the user of this
3913 function call) on all hard register clobberage. */
3915 /* last_function_call is now a list of insns. */
3916 free_INSN_LIST_list(&last_function_call
);
3917 last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3920 /* See comments on reemit_notes as to why we do this.
3921 ??? Actually, the reemit_notes just say what is done, not why. */
3923 else if (GET_CODE (insn
) == NOTE
3924 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_START
3925 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_END
))
3927 loop_notes
= alloc_EXPR_LIST (REG_DEAD
, NOTE_RANGE_INFO (insn
),
3929 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
3930 GEN_INT (NOTE_LINE_NUMBER (insn
)),
3933 else if (GET_CODE (insn
) == NOTE
3934 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
3935 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
3936 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
3937 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
3938 || (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
3939 && GET_CODE (PREV_INSN (insn
)) != CALL_INSN
)))
3941 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
3942 GEN_INT (NOTE_BLOCK_NUMBER (insn
)),
3944 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
3945 GEN_INT (NOTE_LINE_NUMBER (insn
)),
3947 CONST_CALL_P (loop_notes
) = CONST_CALL_P (insn
);
3956 /* Called when we see a set of a register. If death is true, then we are
3957 scanning backwards. Mark that register as unborn. If nobody says
3958 otherwise, that is how things will remain. If death is false, then we
3959 are scanning forwards. Mark that register as being born. */
3962 sched_note_set (x
, death
)
3967 register rtx reg
= SET_DEST (x
);
3973 if (GET_CODE (reg
) == PARALLEL
3974 && GET_MODE (reg
) == BLKmode
)
3977 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
3978 sched_note_set (XVECEXP (reg
, 0, i
), death
);
3982 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == STRICT_LOW_PART
3983 || GET_CODE (reg
) == SIGN_EXTRACT
|| GET_CODE (reg
) == ZERO_EXTRACT
)
3985 /* Must treat modification of just one hardware register of a multi-reg
3986 value or just a byte field of a register exactly the same way that
3987 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
3988 does not kill the entire register. */
3989 if (GET_CODE (reg
) != SUBREG
3990 || REG_SIZE (SUBREG_REG (reg
)) > REG_SIZE (reg
))
3993 reg
= SUBREG_REG (reg
);
3996 if (GET_CODE (reg
) != REG
)
3999 /* Global registers are always live, so the code below does not apply
4002 regno
= REGNO (reg
);
4003 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
4007 /* If we only set part of the register, then this set does not
4012 /* Try killing this register. */
4013 if (regno
< FIRST_PSEUDO_REGISTER
)
4015 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
4018 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4023 /* Recompute REG_BASIC_BLOCK as we update all the other
4024 dataflow information. */
4025 if (sched_reg_basic_block
[regno
] == REG_BLOCK_UNKNOWN
)
4026 sched_reg_basic_block
[regno
] = current_block_num
;
4027 else if (sched_reg_basic_block
[regno
] != current_block_num
)
4028 sched_reg_basic_block
[regno
] = REG_BLOCK_GLOBAL
;
4030 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
);
4035 /* Make the register live again. */
4036 if (regno
< FIRST_PSEUDO_REGISTER
)
4038 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
4041 SET_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4046 SET_REGNO_REG_SET (bb_live_regs
, regno
);
4052 /* Macros and functions for keeping the priority queue sorted, and
4053 dealing with queueing and dequeueing of instructions. */
4055 #define SCHED_SORT(READY, N_READY) \
4056 do { if ((N_READY) == 2) \
4057 swap_sort (READY, N_READY); \
4058 else if ((N_READY) > 2) \
4059 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4062 /* Returns a positive value if x is preferred; returns a negative value if
4063 y is preferred. Should never return 0, since that will make the sort
4067 rank_for_schedule (x
, y
)
4068 const GENERIC_PTR x
;
4069 const GENERIC_PTR y
;
4071 rtx tmp
= *(rtx
*)y
;
4072 rtx tmp2
= *(rtx
*)x
;
4074 int tmp_class
, tmp2_class
, depend_count1
, depend_count2
;
4075 int val
, priority_val
, spec_val
, prob_val
, weight_val
;
4078 /* Prefer insn with higher priority. */
4079 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
4081 return priority_val
;
4083 /* Prefer an insn with smaller contribution to registers-pressure. */
4084 if (!reload_completed
&&
4085 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
4086 return (weight_val
);
4088 /* Some comparison make sense in interblock scheduling only. */
4089 if (INSN_BB (tmp
) != INSN_BB (tmp2
))
4091 /* Prefer an inblock motion on an interblock motion. */
4092 if ((INSN_BB (tmp2
) == target_bb
) && (INSN_BB (tmp
) != target_bb
))
4094 if ((INSN_BB (tmp
) == target_bb
) && (INSN_BB (tmp2
) != target_bb
))
4097 /* Prefer a useful motion on a speculative one. */
4098 if ((spec_val
= IS_SPECULATIVE_INSN (tmp
) - IS_SPECULATIVE_INSN (tmp2
)))
4101 /* Prefer a more probable (speculative) insn. */
4102 prob_val
= INSN_PROBABILITY (tmp2
) - INSN_PROBABILITY (tmp
);
4107 /* Compare insns based on their relation to the last-scheduled-insn. */
4108 if (last_scheduled_insn
)
4110 /* Classify the instructions into three classes:
4111 1) Data dependent on last schedule insn.
4112 2) Anti/Output dependent on last scheduled insn.
4113 3) Independent of last scheduled insn, or has latency of one.
4114 Choose the insn from the highest numbered class if different. */
4115 link
= find_insn_list (tmp
, INSN_DEPEND (last_scheduled_insn
));
4116 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp
) == 1)
4118 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4123 link
= find_insn_list (tmp2
, INSN_DEPEND (last_scheduled_insn
));
4124 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp2
) == 1)
4126 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4131 if ((val
= tmp2_class
- tmp_class
))
4135 /* Prefer the insn which has more later insns that depend on it.
4136 This gives the scheduler more freedom when scheduling later
4137 instructions at the expense of added register pressure. */
4139 for (link
= INSN_DEPEND (tmp
); link
; link
= XEXP (link
, 1))
4143 for (link
= INSN_DEPEND (tmp2
); link
; link
= XEXP (link
, 1))
4146 val
= depend_count2
- depend_count1
;
4150 /* If insns are equally good, sort by INSN_LUID (original insn order),
4151 so that we make the sort stable. This minimizes instruction movement,
4152 thus minimizing sched's effect on debugging and cross-jumping. */
4153 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
4156 /* Resort the array A in which only element at index N may be out of order. */
4158 HAIFA_INLINE
static void
4163 rtx insn
= a
[n
- 1];
4166 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
4174 static int max_priority
;
4176 /* Add INSN to the insn queue so that it can be executed at least
4177 N_CYCLES after the currently executing insn. Preserve insns
4178 chain for debugging purposes. */
4180 HAIFA_INLINE
static void
4181 queue_insn (insn
, n_cycles
)
4185 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
4186 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
4187 insn_queue
[next_q
] = link
;
4190 if (sched_verbose
>= 2)
4192 fprintf (dump
, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn
));
4194 if (INSN_BB (insn
) != target_bb
)
4195 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
4197 fprintf (dump
, "queued for %d cycles.\n", n_cycles
);
4202 /* Return nonzero if PAT is the pattern of an insn which makes a
4205 HAIFA_INLINE
static int
4206 birthing_insn_p (pat
)
4211 if (reload_completed
== 1)
4214 if (GET_CODE (pat
) == SET
4215 && (GET_CODE (SET_DEST (pat
)) == REG
4216 || (GET_CODE (SET_DEST (pat
)) == PARALLEL
4217 && GET_MODE (SET_DEST (pat
)) == BLKmode
)))
4219 rtx dest
= SET_DEST (pat
);
4222 /* It would be more accurate to use refers_to_regno_p or
4223 reg_mentioned_p to determine when the dest is not live before this
4225 if (GET_CODE (dest
) == REG
)
4228 if (REGNO_REG_SET_P (bb_live_regs
, i
))
4229 return (REG_N_SETS (i
) == 1);
4233 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
4235 int regno
= REGNO (SET_DEST (XVECEXP (dest
, 0, i
)));
4236 if (REGNO_REG_SET_P (bb_live_regs
, regno
))
4237 return (REG_N_SETS (regno
) == 1);
4242 if (GET_CODE (pat
) == PARALLEL
)
4244 for (j
= 0; j
< XVECLEN (pat
, 0); j
++)
4245 if (birthing_insn_p (XVECEXP (pat
, 0, j
)))
4251 /* PREV is an insn that is ready to execute. Adjust its priority if that
4252 will help shorten register lifetimes. */
4254 HAIFA_INLINE
static void
4255 adjust_priority (prev
)
4258 /* Trying to shorten register lives after reload has completed
4259 is useless and wrong. It gives inaccurate schedules. */
4260 if (reload_completed
== 0)
4265 /* ??? This code has no effect, because REG_DEAD notes are removed
4266 before we ever get here. */
4267 for (note
= REG_NOTES (prev
); note
; note
= XEXP (note
, 1))
4268 if (REG_NOTE_KIND (note
) == REG_DEAD
)
4271 /* Defer scheduling insns which kill registers, since that
4272 shortens register lives. Prefer scheduling insns which
4273 make registers live for the same reason. */
4277 INSN_PRIORITY (prev
) >>= 3;
4280 INSN_PRIORITY (prev
) >>= 2;
4284 INSN_PRIORITY (prev
) >>= 1;
4287 if (birthing_insn_p (PATTERN (prev
)))
4289 int max
= max_priority
;
4291 if (max
> INSN_PRIORITY (prev
))
4292 INSN_PRIORITY (prev
) = max
;
4298 /* That said, a target might have it's own reasons for adjusting
4299 priority after reload. */
4300 #ifdef ADJUST_PRIORITY
4301 ADJUST_PRIORITY (prev
);
4305 /* Clock at which the previous instruction was issued. */
4306 static int last_clock_var
;
4308 /* INSN is the "currently executing insn". Launch each insn which was
4309 waiting on INSN. READY is a vector of insns which are ready to fire.
4310 N_READY is the number of elements in READY. CLOCK is the current
4314 schedule_insn (insn
, ready
, n_ready
, clock
)
4323 unit
= insn_unit (insn
);
4325 if (sched_verbose
>= 2)
4327 fprintf (dump
, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
4329 insn_print_units (insn
);
4330 fprintf (dump
, "\n");
4333 if (sched_verbose
&& unit
== -1)
4334 visualize_no_unit (insn
);
4336 if (MAX_BLOCKAGE
> 1 || issue_rate
> 1 || sched_verbose
)
4337 schedule_unit (unit
, insn
, clock
);
4339 if (INSN_DEPEND (insn
) == 0)
4342 /* This is used by the function adjust_priority above. */
4344 max_priority
= MAX (INSN_PRIORITY (ready
[0]), INSN_PRIORITY (insn
));
4346 max_priority
= INSN_PRIORITY (insn
);
4348 for (link
= INSN_DEPEND (insn
); link
!= 0; link
= XEXP (link
, 1))
4350 rtx next
= XEXP (link
, 0);
4351 int cost
= insn_cost (insn
, link
, next
);
4353 INSN_TICK (next
) = MAX (INSN_TICK (next
), clock
+ cost
);
4355 if ((INSN_DEP_COUNT (next
) -= 1) == 0)
4357 int effective_cost
= INSN_TICK (next
) - clock
;
4359 /* For speculative insns, before inserting to ready/queue,
4360 check live, exception-free, and issue-delay. */
4361 if (INSN_BB (next
) != target_bb
4362 && (!IS_VALID (INSN_BB (next
))
4364 || (IS_SPECULATIVE_INSN (next
)
4365 && (insn_issue_delay (next
) > 3
4366 || !check_live (next
, INSN_BB (next
))
4367 || !is_exception_free (next
, INSN_BB (next
), target_bb
)))))
4370 if (sched_verbose
>= 2)
4372 fprintf (dump
, ";;\t\tdependences resolved: insn %d ",
4375 if (current_nr_blocks
> 1 && INSN_BB (next
) != target_bb
)
4376 fprintf (dump
, "/b%d ", INSN_BLOCK (next
));
4378 if (effective_cost
< 1)
4379 fprintf (dump
, "into ready\n");
4381 fprintf (dump
, "into queue with cost=%d\n", effective_cost
);
4384 /* Adjust the priority of NEXT and either put it on the ready
4385 list or queue it. */
4386 adjust_priority (next
);
4387 if (effective_cost
< 1)
4388 ready
[n_ready
++] = next
;
4390 queue_insn (next
, effective_cost
);
4394 /* Annotate the instruction with issue information -- TImode
4395 indicates that the instruction is expected not to be able
4396 to issue on the same cycle as the previous insn. A machine
4397 may use this information to decide how the instruction should
4399 if (reload_completed
&& issue_rate
> 1)
4401 PUT_MODE (insn
, clock
> last_clock_var
? TImode
: VOIDmode
);
4402 last_clock_var
= clock
;
4409 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4413 create_reg_dead_note (reg
, insn
)
4418 /* The number of registers killed after scheduling must be the same as the
4419 number of registers killed before scheduling. The number of REG_DEAD
4420 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4421 might become one DImode hard register REG_DEAD note, but the number of
4422 registers killed will be conserved.
4424 We carefully remove REG_DEAD notes from the dead_notes list, so that
4425 there will be none left at the end. If we run out early, then there
4426 is a bug somewhere in flow, combine and/or sched. */
4428 if (dead_notes
== 0)
4430 if (current_nr_blocks
<= 1)
4433 link
= alloc_EXPR_LIST (REG_DEAD
, NULL_RTX
, NULL_RTX
);
4437 /* Number of regs killed by REG. */
4438 int regs_killed
= (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
? 1
4439 : HARD_REGNO_NREGS (REGNO (reg
), GET_MODE (reg
)));
4440 /* Number of regs killed by REG_DEAD notes taken off the list. */
4444 reg_note_regs
= (REGNO (XEXP (link
, 0)) >= FIRST_PSEUDO_REGISTER
? 1
4445 : HARD_REGNO_NREGS (REGNO (XEXP (link
, 0)),
4446 GET_MODE (XEXP (link
, 0))));
4447 while (reg_note_regs
< regs_killed
)
4449 link
= XEXP (link
, 1);
4451 /* LINK might be zero if we killed more registers after scheduling
4452 than before, and the last hard register we kill is actually
4455 This is normal for interblock scheduling, so deal with it in
4456 that case, else abort. */
4457 if (link
== NULL_RTX
&& current_nr_blocks
<= 1)
4459 else if (link
== NULL_RTX
)
4460 link
= alloc_EXPR_LIST (REG_DEAD
, gen_rtx_REG (word_mode
, 0),
4463 reg_note_regs
+= (REGNO (XEXP (link
, 0)) >= FIRST_PSEUDO_REGISTER
? 1
4464 : HARD_REGNO_NREGS (REGNO (XEXP (link
, 0)),
4465 GET_MODE (XEXP (link
, 0))));
4467 dead_notes
= XEXP (link
, 1);
4469 /* If we took too many regs kills off, put the extra ones back. */
4470 while (reg_note_regs
> regs_killed
)
4472 rtx temp_reg
, temp_link
;
4474 temp_reg
= gen_rtx_REG (word_mode
, 0);
4475 temp_link
= alloc_EXPR_LIST (REG_DEAD
, temp_reg
, dead_notes
);
4476 dead_notes
= temp_link
;
4481 XEXP (link
, 0) = reg
;
4482 XEXP (link
, 1) = REG_NOTES (insn
);
4483 REG_NOTES (insn
) = link
;
4486 /* Subroutine on attach_deaths_insn--handles the recursive search
4487 through INSN. If SET_P is true, then x is being modified by the insn. */
4490 attach_deaths (x
, insn
, set_p
)
4497 register enum rtx_code code
;
4498 register const char *fmt
;
4503 code
= GET_CODE (x
);
4515 /* Get rid of the easy cases first. */
4520 /* If the register dies in this insn, queue that note, and mark
4521 this register as needing to die. */
4522 /* This code is very similar to mark_used_1 (if set_p is false)
4523 and mark_set_1 (if set_p is true) in flow.c. */
4533 all_needed
= some_needed
= REGNO_REG_SET_P (old_live_regs
, regno
);
4534 if (regno
< FIRST_PSEUDO_REGISTER
)
4538 n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4541 int needed
= (REGNO_REG_SET_P (old_live_regs
, regno
+ n
));
4542 some_needed
|= needed
;
4543 all_needed
&= needed
;
4547 /* If it wasn't live before we started, then add a REG_DEAD note.
4548 We must check the previous lifetime info not the current info,
4549 because we may have to execute this code several times, e.g.
4550 once for a clobber (which doesn't add a note) and later
4551 for a use (which does add a note).
4553 Always make the register live. We must do this even if it was
4554 live before, because this may be an insn which sets and uses
4555 the same register, in which case the register has already been
4556 killed, so we must make it live again.
4558 Global registers are always live, and should never have a REG_DEAD
4559 note added for them, so none of the code below applies to them. */
4561 if (regno
>= FIRST_PSEUDO_REGISTER
|| ! global_regs
[regno
])
4563 /* Never add REG_DEAD notes for STACK_POINTER_REGNUM
4564 since it's always considered to be live. Similarly
4565 for FRAME_POINTER_REGNUM if a frame pointer is needed
4566 and for ARG_POINTER_REGNUM if it is fixed. */
4567 if (! (regno
== FRAME_POINTER_REGNUM
4568 && (! reload_completed
|| frame_pointer_needed
))
4569 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4570 && ! (regno
== HARD_FRAME_POINTER_REGNUM
4571 && (! reload_completed
|| frame_pointer_needed
))
4573 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4574 && ! (regno
== ARG_POINTER_REGNUM
&& fixed_regs
[regno
])
4576 && regno
!= STACK_POINTER_REGNUM
)
4578 if (! all_needed
&& ! dead_or_set_p (insn
, x
))
4580 /* Check for the case where the register dying partially
4581 overlaps the register set by this insn. */
4582 if (regno
< FIRST_PSEUDO_REGISTER
4583 && HARD_REGNO_NREGS (regno
, GET_MODE (x
)) > 1)
4585 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4587 some_needed
|= dead_or_set_regno_p (insn
, regno
+ n
);
4590 /* If none of the words in X is needed, make a REG_DEAD
4591 note. Otherwise, we must make partial REG_DEAD
4594 create_reg_dead_note (x
, insn
);
4599 /* Don't make a REG_DEAD note for a part of a
4600 register that is set in the insn. */
4601 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
)) - 1;
4603 if (! REGNO_REG_SET_P (old_live_regs
, regno
+i
)
4604 && ! dead_or_set_regno_p (insn
, regno
+ i
))
4605 create_reg_dead_note (gen_rtx_REG (reg_raw_mode
[regno
+ i
],
4612 if (regno
< FIRST_PSEUDO_REGISTER
)
4614 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4617 SET_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4622 /* Recompute REG_BASIC_BLOCK as we update all the other
4623 dataflow information. */
4624 if (sched_reg_basic_block
[regno
] == REG_BLOCK_UNKNOWN
)
4625 sched_reg_basic_block
[regno
] = current_block_num
;
4626 else if (sched_reg_basic_block
[regno
] != current_block_num
)
4627 sched_reg_basic_block
[regno
] = REG_BLOCK_GLOBAL
;
4629 SET_REGNO_REG_SET (bb_live_regs
, regno
);
4636 /* Handle tail-recursive case. */
4637 attach_deaths (XEXP (x
, 0), insn
, 0);
4641 attach_deaths (SUBREG_REG (x
), insn
,
4642 set_p
&& ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
)))
4644 || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
)))
4645 == GET_MODE_SIZE (GET_MODE ((x
))))));
4648 case STRICT_LOW_PART
:
4649 attach_deaths (XEXP (x
, 0), insn
, 0);
4654 attach_deaths (XEXP (x
, 0), insn
, 0);
4655 attach_deaths (XEXP (x
, 1), insn
, 0);
4656 attach_deaths (XEXP (x
, 2), insn
, 0);
4661 && GET_MODE (x
) == BLKmode
)
4663 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
4664 attach_deaths (SET_DEST (XVECEXP (x
, 0, i
)), insn
, 1);
4670 /* Other cases: walk the insn. */
4671 fmt
= GET_RTX_FORMAT (code
);
4672 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4675 attach_deaths (XEXP (x
, i
), insn
, 0);
4676 else if (fmt
[i
] == 'E')
4677 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
4678 attach_deaths (XVECEXP (x
, i
, j
), insn
, 0);
4683 /* After INSN has executed, add register death notes for each register
4684 that is dead after INSN. */
4687 attach_deaths_insn (insn
)
4690 rtx x
= PATTERN (insn
);
4691 register RTX_CODE code
= GET_CODE (x
);
4696 attach_deaths (SET_SRC (x
), insn
, 0);
4698 /* A register might die here even if it is the destination, e.g.
4699 it is the target of a volatile read and is otherwise unused.
4700 Hence we must always call attach_deaths for the SET_DEST. */
4701 attach_deaths (SET_DEST (x
), insn
, 1);
4703 else if (code
== PARALLEL
)
4706 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
4708 code
= GET_CODE (XVECEXP (x
, 0, i
));
4711 attach_deaths (SET_SRC (XVECEXP (x
, 0, i
)), insn
, 0);
4713 attach_deaths (SET_DEST (XVECEXP (x
, 0, i
)), insn
, 1);
4715 /* Flow does not add REG_DEAD notes to registers that die in
4716 clobbers, so we can't either. */
4717 else if (code
!= CLOBBER
)
4718 attach_deaths (XVECEXP (x
, 0, i
), insn
, 0);
4721 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4722 MEM being clobbered, just like flow. */
4723 else if (code
== CLOBBER
&& GET_CODE (XEXP (x
, 0)) == MEM
)
4724 attach_deaths (XEXP (XEXP (x
, 0), 0), insn
, 0);
4725 /* Otherwise don't add a death note to things being clobbered. */
4726 else if (code
!= CLOBBER
)
4727 attach_deaths (x
, insn
, 0);
4729 /* Make death notes for things used in the called function. */
4730 if (GET_CODE (insn
) == CALL_INSN
)
4731 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
4732 attach_deaths (XEXP (XEXP (link
, 0), 0), insn
,
4733 GET_CODE (XEXP (link
, 0)) == CLOBBER
);
4736 /* Functions for handling of notes. */
4738 /* Delete notes beginning with INSN and put them in the chain
4739 of notes ended by NOTE_LIST.
4740 Returns the insn following the notes. */
4743 unlink_other_notes (insn
, tail
)
4746 rtx prev
= PREV_INSN (insn
);
4748 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4750 rtx next
= NEXT_INSN (insn
);
4751 /* Delete the note from its current position. */
4753 NEXT_INSN (prev
) = next
;
4755 PREV_INSN (next
) = prev
;
4757 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4758 immediately after the call they follow. We use a fake
4759 (REG_DEAD (const_int -1)) note to remember them.
4760 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4761 if (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_SETJMP
4762 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
4763 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
4764 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_START
4765 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_END
4766 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_BEG
4767 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_END
)
4769 /* Insert the note at the end of the notes list. */
4770 PREV_INSN (insn
) = note_list
;
4772 NEXT_INSN (note_list
) = insn
;
4781 /* Delete line notes beginning with INSN. Record line-number notes so
4782 they can be reused. Returns the insn following the notes. */
4785 unlink_line_notes (insn
, tail
)
4788 rtx prev
= PREV_INSN (insn
);
4790 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4792 rtx next
= NEXT_INSN (insn
);
4794 if (write_symbols
!= NO_DEBUG
&& NOTE_LINE_NUMBER (insn
) > 0)
4796 /* Delete the note from its current position. */
4798 NEXT_INSN (prev
) = next
;
4800 PREV_INSN (next
) = prev
;
4802 /* Record line-number notes so they can be reused. */
4803 LINE_NOTE (insn
) = insn
;
4813 /* Return the head and tail pointers of BB. */
4815 HAIFA_INLINE
static void
4816 get_block_head_tail (bb
, headp
, tailp
)
4826 b
= BB_TO_BLOCK (bb
);
4828 /* HEAD and TAIL delimit the basic block being scheduled. */
4829 head
= BLOCK_HEAD (b
);
4830 tail
= BLOCK_END (b
);
4832 /* Don't include any notes or labels at the beginning of the
4833 basic block, or notes at the ends of basic blocks. */
4834 while (head
!= tail
)
4836 if (GET_CODE (head
) == NOTE
)
4837 head
= NEXT_INSN (head
);
4838 else if (GET_CODE (tail
) == NOTE
)
4839 tail
= PREV_INSN (tail
);
4840 else if (GET_CODE (head
) == CODE_LABEL
)
4841 head
= NEXT_INSN (head
);
4850 /* Delete line notes from bb. Save them so they can be later restored
4851 (in restore_line_notes ()). */
4862 get_block_head_tail (bb
, &head
, &tail
);
4865 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
4868 next_tail
= NEXT_INSN (tail
);
4869 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4873 /* Farm out notes, and maybe save them in NOTE_LIST.
4874 This is needed to keep the debugger from
4875 getting completely deranged. */
4876 if (GET_CODE (insn
) == NOTE
)
4879 insn
= unlink_line_notes (insn
, next_tail
);
4885 if (insn
== next_tail
)
4891 /* Save line number notes for each insn in bb. */
4894 save_line_notes (bb
)
4900 /* We must use the true line number for the first insn in the block
4901 that was computed and saved at the start of this pass. We can't
4902 use the current line number, because scheduling of the previous
4903 block may have changed the current line number. */
4905 rtx line
= line_note_head
[BB_TO_BLOCK (bb
)];
4908 get_block_head_tail (bb
, &head
, &tail
);
4909 next_tail
= NEXT_INSN (tail
);
4911 for (insn
= BLOCK_HEAD (BB_TO_BLOCK (bb
));
4913 insn
= NEXT_INSN (insn
))
4914 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4917 LINE_NOTE (insn
) = line
;
4921 /* After bb was scheduled, insert line notes into the insns list. */
4924 restore_line_notes (bb
)
4927 rtx line
, note
, prev
, new;
4928 int added_notes
= 0;
4930 rtx head
, next_tail
, insn
;
4932 b
= BB_TO_BLOCK (bb
);
4934 head
= BLOCK_HEAD (b
);
4935 next_tail
= NEXT_INSN (BLOCK_END (b
));
4937 /* Determine the current line-number. We want to know the current
4938 line number of the first insn of the block here, in case it is
4939 different from the true line number that was saved earlier. If
4940 different, then we need a line number note before the first insn
4941 of this block. If it happens to be the same, then we don't want to
4942 emit another line number note here. */
4943 for (line
= head
; line
; line
= PREV_INSN (line
))
4944 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
4947 /* Walk the insns keeping track of the current line-number and inserting
4948 the line-number notes as needed. */
4949 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4950 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4952 /* This used to emit line number notes before every non-deleted note.
4953 However, this confuses a debugger, because line notes not separated
4954 by real instructions all end up at the same address. I can find no
4955 use for line number notes before other notes, so none are emitted. */
4956 else if (GET_CODE (insn
) != NOTE
4957 && (note
= LINE_NOTE (insn
)) != 0
4960 || NOTE_LINE_NUMBER (note
) != NOTE_LINE_NUMBER (line
)
4961 || NOTE_SOURCE_FILE (note
) != NOTE_SOURCE_FILE (line
)))
4964 prev
= PREV_INSN (insn
);
4965 if (LINE_NOTE (note
))
4967 /* Re-use the original line-number note. */
4968 LINE_NOTE (note
) = 0;
4969 PREV_INSN (note
) = prev
;
4970 NEXT_INSN (prev
) = note
;
4971 PREV_INSN (insn
) = note
;
4972 NEXT_INSN (note
) = insn
;
4977 new = emit_note_after (NOTE_LINE_NUMBER (note
), prev
);
4978 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note
);
4979 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note
);
4982 if (sched_verbose
&& added_notes
)
4983 fprintf (dump
, ";; added %d line-number notes\n", added_notes
);
4986 /* After scheduling the function, delete redundant line notes from the
4990 rm_redundant_line_notes ()
4993 rtx insn
= get_insns ();
4994 int active_insn
= 0;
4997 /* Walk the insns deleting redundant line-number notes. Many of these
4998 are already present. The remainder tend to occur at basic
4999 block boundaries. */
5000 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
5001 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
5003 /* If there are no active insns following, INSN is redundant. */
5004 if (active_insn
== 0)
5007 NOTE_SOURCE_FILE (insn
) = 0;
5008 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
5010 /* If the line number is unchanged, LINE is redundant. */
5012 && NOTE_LINE_NUMBER (line
) == NOTE_LINE_NUMBER (insn
)
5013 && NOTE_SOURCE_FILE (line
) == NOTE_SOURCE_FILE (insn
))
5016 NOTE_SOURCE_FILE (line
) = 0;
5017 NOTE_LINE_NUMBER (line
) = NOTE_INSN_DELETED
;
5024 else if (!((GET_CODE (insn
) == NOTE
5025 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
5026 || (GET_CODE (insn
) == INSN
5027 && (GET_CODE (PATTERN (insn
)) == USE
5028 || GET_CODE (PATTERN (insn
)) == CLOBBER
))))
5031 if (sched_verbose
&& notes
)
5032 fprintf (dump
, ";; deleted %d line-number notes\n", notes
);
5035 /* Delete notes between head and tail and put them in the chain
5036 of notes ended by NOTE_LIST. */
5039 rm_other_notes (head
, tail
)
5047 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
5050 next_tail
= NEXT_INSN (tail
);
5051 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5055 /* Farm out notes, and maybe save them in NOTE_LIST.
5056 This is needed to keep the debugger from
5057 getting completely deranged. */
5058 if (GET_CODE (insn
) == NOTE
)
5062 insn
= unlink_other_notes (insn
, next_tail
);
5068 if (insn
== next_tail
)
5074 /* Constructor for `sometimes' data structure. */
5077 new_sometimes_live (regs_sometimes_live
, regno
, sometimes_max
)
5078 struct sometimes
*regs_sometimes_live
;
5082 register struct sometimes
*p
;
5084 /* There should never be a register greater than max_regno here. If there
5085 is, it means that a define_split has created a new pseudo reg. This
5086 is not allowed, since there will not be flow info available for any
5087 new register, so catch the error here. */
5088 if (regno
>= max_regno
)
5091 p
= ®s_sometimes_live
[sometimes_max
];
5094 p
->calls_crossed
= 0;
5096 return sometimes_max
;
5099 /* Count lengths of all regs we are currently tracking,
5100 and find new registers no longer live. */
5103 finish_sometimes_live (regs_sometimes_live
, sometimes_max
)
5104 struct sometimes
*regs_sometimes_live
;
5109 for (i
= 0; i
< sometimes_max
; i
++)
5111 register struct sometimes
*p
= ®s_sometimes_live
[i
];
5112 int regno
= p
->regno
;
5114 sched_reg_live_length
[regno
] += p
->live_length
;
5115 sched_reg_n_calls_crossed
[regno
] += p
->calls_crossed
;
5119 /* Functions for computation of registers live/usage info. */
5121 /* It is assumed that prior to scheduling BASIC_BLOCK (b)->global_live_at_start
5122 contains the registers that are alive at the entry to b.
5124 Two passes follow: The first pass is performed before the scheduling
5125 of a region. It scans each block of the region forward, computing
5126 the set of registers alive at the end of the basic block and
5127 discard REG_DEAD notes (done by find_pre_sched_live ()).
5129 The second path is invoked after scheduling all region blocks.
5130 It scans each block of the region backward, a block being traversed
5131 only after its succesors in the region. When the set of registers
5132 live at the end of a basic block may be changed by the scheduling
5133 (this may happen for multiple blocks region), it is computed as
5134 the union of the registers live at the start of its succesors.
5135 The last-use information is updated by inserting REG_DEAD notes.
5136 (done by find_post_sched_live ()) */
5138 /* Scan all the insns to be scheduled, removing register death notes.
5139 Register death notes end up in DEAD_NOTES.
5140 Recreate the register life information for the end of this basic
5144 find_pre_sched_live (bb
)
5147 rtx insn
, next_tail
, head
, tail
;
5148 int b
= BB_TO_BLOCK (bb
);
5150 get_block_head_tail (bb
, &head
, &tail
);
5151 COPY_REG_SET (bb_live_regs
, BASIC_BLOCK (b
)->global_live_at_start
);
5152 next_tail
= NEXT_INSN (tail
);
5154 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5156 rtx prev
, next
, link
;
5159 /* Handle register life information. */
5160 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
5162 /* See if the register gets born here. */
5163 /* We must check for registers being born before we check for
5164 registers dying. It is possible for a register to be born and
5165 die in the same insn, e.g. reading from a volatile memory
5166 location into an otherwise unused register. Such a register
5167 must be marked as dead after this insn. */
5168 if (GET_CODE (PATTERN (insn
)) == SET
5169 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
5171 sched_note_set (PATTERN (insn
), 0);
5175 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
5178 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5179 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
5180 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
5182 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 0);
5186 /* ??? This code is obsolete and should be deleted. It
5187 is harmless though, so we will leave it in for now. */
5188 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5189 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == USE
)
5190 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 0);
5193 /* Each call cobbers (makes live) all call-clobbered regs
5194 that are not global or fixed. Note that the function-value
5195 reg is a call_clobbered reg. */
5196 if (GET_CODE (insn
) == CALL_INSN
)
5199 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
5200 if (call_used_regs
[j
] && !global_regs
[j
]
5203 SET_REGNO_REG_SET (bb_live_regs
, j
);
5207 /* Need to know what registers this insn kills. */
5208 for (prev
= 0, link
= REG_NOTES (insn
); link
; link
= next
)
5210 next
= XEXP (link
, 1);
5211 if ((REG_NOTE_KIND (link
) == REG_DEAD
5212 || REG_NOTE_KIND (link
) == REG_UNUSED
)
5213 /* Verify that the REG_NOTE has a valid value. */
5214 && GET_CODE (XEXP (link
, 0)) == REG
)
5216 register int regno
= REGNO (XEXP (link
, 0));
5220 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5222 if (REG_NOTE_KIND (link
) == REG_DEAD
)
5225 XEXP (prev
, 1) = next
;
5227 REG_NOTES (insn
) = next
;
5228 XEXP (link
, 1) = dead_notes
;
5234 if (regno
< FIRST_PSEUDO_REGISTER
)
5236 int j
= HARD_REGNO_NREGS (regno
,
5237 GET_MODE (XEXP (link
, 0)));
5240 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
+j
);
5245 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
);
5253 INSN_REG_WEIGHT (insn
) = reg_weight
;
5257 /* Update register life and usage information for block bb
5258 after scheduling. Put register dead notes back in the code. */
5261 find_post_sched_live (bb
)
5268 rtx head
, tail
, prev_head
, next_tail
;
5270 register struct sometimes
*regs_sometimes_live
;
5272 b
= BB_TO_BLOCK (bb
);
5274 /* Compute live regs at the end of bb as a function of its successors. */
5275 if (current_nr_blocks
> 1)
5280 first_edge
= e
= OUT_EDGES (b
);
5281 CLEAR_REG_SET (bb_live_regs
);
5288 b_succ
= TO_BLOCK (e
);
5289 IOR_REG_SET (bb_live_regs
,
5290 BASIC_BLOCK (b_succ
)->global_live_at_start
);
5293 while (e
!= first_edge
);
5296 get_block_head_tail (bb
, &head
, &tail
);
5297 next_tail
= NEXT_INSN (tail
);
5298 prev_head
= PREV_INSN (head
);
5300 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, FIRST_PSEUDO_REGISTER
, i
,
5302 sched_reg_basic_block
[i
] = REG_BLOCK_GLOBAL
;
5305 /* If the block is empty, same regs are alive at its end and its start.
5306 since this is not guaranteed after interblock scheduling, make sure they
5307 are truly identical. */
5308 if (NEXT_INSN (prev_head
) == tail
5309 && (GET_RTX_CLASS (GET_CODE (tail
)) != 'i'))
5311 if (current_nr_blocks
> 1)
5312 COPY_REG_SET (BASIC_BLOCK (b
)->global_live_at_start
, bb_live_regs
);
5317 b
= BB_TO_BLOCK (bb
);
5318 current_block_num
= b
;
5320 /* Keep track of register lives. */
5321 old_live_regs
= ALLOCA_REG_SET ();
5323 = (struct sometimes
*) alloca (max_regno
* sizeof (struct sometimes
));
5326 /* Initiate "sometimes" data, starting with registers live at end. */
5328 COPY_REG_SET (old_live_regs
, bb_live_regs
);
5329 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, 0, j
,
5332 = new_sometimes_live (regs_sometimes_live
,
5336 /* Scan insns back, computing regs live info. */
5337 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
5339 /* First we kill registers set by this insn, and then we
5340 make registers used by this insn live. This is the opposite
5341 order used above because we are traversing the instructions
5344 /* Strictly speaking, we should scan REG_UNUSED notes and make
5345 every register mentioned there live, however, we will just
5346 kill them again immediately below, so there doesn't seem to
5347 be any reason why we bother to do this. */
5349 /* See if this is the last notice we must take of a register. */
5350 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5353 if (GET_CODE (PATTERN (insn
)) == SET
5354 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
5355 sched_note_set (PATTERN (insn
), 1);
5356 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
5358 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5359 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
5360 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
5361 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 1);
5364 /* This code keeps life analysis information up to date. */
5365 if (GET_CODE (insn
) == CALL_INSN
)
5367 register struct sometimes
*p
;
5369 /* A call kills all call used registers that are not
5370 global or fixed, except for those mentioned in the call
5371 pattern which will be made live again later. */
5372 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
5373 if (call_used_regs
[i
] && ! global_regs
[i
]
5376 CLEAR_REGNO_REG_SET (bb_live_regs
, i
);
5379 /* Regs live at the time of a call instruction must not
5380 go in a register clobbered by calls. Record this for
5381 all regs now live. Note that insns which are born or
5382 die in a call do not cross a call, so this must be done
5383 after the killings (above) and before the births
5385 p
= regs_sometimes_live
;
5386 for (i
= 0; i
< sometimes_max
; i
++, p
++)
5387 if (REGNO_REG_SET_P (bb_live_regs
, p
->regno
))
5388 p
->calls_crossed
+= 1;
5391 /* Make every register used live, and add REG_DEAD notes for
5392 registers which were not live before we started. */
5393 attach_deaths_insn (insn
);
5395 /* Find registers now made live by that instruction. */
5396 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs
, old_live_regs
, 0, j
,
5399 = new_sometimes_live (regs_sometimes_live
,
5402 IOR_REG_SET (old_live_regs
, bb_live_regs
);
5404 /* Count lengths of all regs we are worrying about now,
5405 and handle registers no longer live. */
5407 for (i
= 0; i
< sometimes_max
; i
++)
5409 register struct sometimes
*p
= ®s_sometimes_live
[i
];
5410 int regno
= p
->regno
;
5412 p
->live_length
+= 1;
5414 if (!REGNO_REG_SET_P (bb_live_regs
, regno
))
5416 /* This is the end of one of this register's lifetime
5417 segments. Save the lifetime info collected so far,
5418 and clear its bit in the old_live_regs entry. */
5419 sched_reg_live_length
[regno
] += p
->live_length
;
5420 sched_reg_n_calls_crossed
[regno
] += p
->calls_crossed
;
5421 CLEAR_REGNO_REG_SET (old_live_regs
, p
->regno
);
5423 /* Delete the reg_sometimes_live entry for this reg by
5424 copying the last entry over top of it. */
5425 *p
= regs_sometimes_live
[--sometimes_max
];
5426 /* ...and decrement i so that this newly copied entry
5427 will be processed. */
5433 finish_sometimes_live (regs_sometimes_live
, sometimes_max
);
5435 /* In interblock scheduling, global_live_at_start may have changed. */
5436 if (current_nr_blocks
> 1)
5437 COPY_REG_SET (BASIC_BLOCK (b
)->global_live_at_start
, bb_live_regs
);
5440 FREE_REG_SET (old_live_regs
);
5441 } /* find_post_sched_live */
5443 /* After scheduling the subroutine, restore information about uses of
5451 if (n_basic_blocks
> 0)
5452 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, FIRST_PSEUDO_REGISTER
, regno
,
5454 sched_reg_basic_block
[regno
]
5458 for (regno
= 0; regno
< max_regno
; regno
++)
5459 if (sched_reg_live_length
[regno
])
5463 if (REG_LIVE_LENGTH (regno
) > sched_reg_live_length
[regno
])
5465 ";; register %d life shortened from %d to %d\n",
5466 regno
, REG_LIVE_LENGTH (regno
),
5467 sched_reg_live_length
[regno
]);
5468 /* Negative values are special; don't overwrite the current
5469 reg_live_length value if it is negative. */
5470 else if (REG_LIVE_LENGTH (regno
) < sched_reg_live_length
[regno
]
5471 && REG_LIVE_LENGTH (regno
) >= 0)
5473 ";; register %d life extended from %d to %d\n",
5474 regno
, REG_LIVE_LENGTH (regno
),
5475 sched_reg_live_length
[regno
]);
5477 if (!REG_N_CALLS_CROSSED (regno
)
5478 && sched_reg_n_calls_crossed
[regno
])
5480 ";; register %d now crosses calls\n", regno
);
5481 else if (REG_N_CALLS_CROSSED (regno
)
5482 && !sched_reg_n_calls_crossed
[regno
]
5483 && REG_BASIC_BLOCK (regno
) != REG_BLOCK_GLOBAL
)
5485 ";; register %d no longer crosses calls\n", regno
);
5487 if (REG_BASIC_BLOCK (regno
) != sched_reg_basic_block
[regno
]
5488 && sched_reg_basic_block
[regno
] != REG_BLOCK_UNKNOWN
5489 && REG_BASIC_BLOCK(regno
) != REG_BLOCK_UNKNOWN
)
5491 ";; register %d changed basic block from %d to %d\n",
5492 regno
, REG_BASIC_BLOCK(regno
),
5493 sched_reg_basic_block
[regno
]);
5496 /* Negative values are special; don't overwrite the current
5497 reg_live_length value if it is negative. */
5498 if (REG_LIVE_LENGTH (regno
) >= 0)
5499 REG_LIVE_LENGTH (regno
) = sched_reg_live_length
[regno
];
5501 if (sched_reg_basic_block
[regno
] != REG_BLOCK_UNKNOWN
5502 && REG_BASIC_BLOCK(regno
) != REG_BLOCK_UNKNOWN
)
5503 REG_BASIC_BLOCK(regno
) = sched_reg_basic_block
[regno
];
5505 /* We can't change the value of reg_n_calls_crossed to zero for
5506 pseudos which are live in more than one block.
5508 This is because combine might have made an optimization which
5509 invalidated global_live_at_start and reg_n_calls_crossed,
5510 but it does not update them. If we update reg_n_calls_crossed
5511 here, the two variables are now inconsistent, and this might
5512 confuse the caller-save code into saving a register that doesn't
5513 need to be saved. This is only a problem when we zero calls
5514 crossed for a pseudo live in multiple basic blocks.
5516 Alternatively, we could try to correctly update basic block live
5517 at start here in sched, but that seems complicated.
5519 Note: it is possible that a global register became local,
5520 as result of interblock motion, but will remain marked as a
5522 if (sched_reg_n_calls_crossed
[regno
]
5523 || REG_BASIC_BLOCK (regno
) != REG_BLOCK_GLOBAL
)
5524 REG_N_CALLS_CROSSED (regno
) = sched_reg_n_calls_crossed
[regno
];
5529 /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
5530 static int clock_var
;
5532 /* Move insns that became ready to fire from queue to ready list. */
5535 queue_to_ready (ready
, n_ready
)
5542 q_ptr
= NEXT_Q (q_ptr
);
5544 /* Add all pending insns that can be scheduled without stalls to the
5546 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
5549 insn
= XEXP (link
, 0);
5552 if (sched_verbose
>= 2)
5553 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
5555 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
5556 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
5558 ready
[n_ready
++] = insn
;
5559 if (sched_verbose
>= 2)
5560 fprintf (dump
, "moving to ready without stalls\n");
5562 insn_queue
[q_ptr
] = 0;
5564 /* If there are no ready insns, stall until one is ready and add all
5565 of the pending insns at that point to the ready list. */
5568 register int stalls
;
5570 for (stalls
= 1; stalls
< INSN_QUEUE_SIZE
; stalls
++)
5572 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
5574 for (; link
; link
= XEXP (link
, 1))
5576 insn
= XEXP (link
, 0);
5579 if (sched_verbose
>= 2)
5580 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
5582 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
5583 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
5585 ready
[n_ready
++] = insn
;
5586 if (sched_verbose
>= 2)
5587 fprintf (dump
, "moving to ready with %d stalls\n", stalls
);
5589 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = 0;
5596 if (sched_verbose
&& stalls
)
5597 visualize_stall_cycles (BB_TO_BLOCK (target_bb
), stalls
);
5598 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
5599 clock_var
+= stalls
;
5604 /* Print the ready list for debugging purposes. Callable from debugger. */
5607 debug_ready_list (ready
, n_ready
)
5613 for (i
= 0; i
< n_ready
; i
++)
5615 fprintf (dump
, " %d", INSN_UID (ready
[i
]));
5616 if (current_nr_blocks
> 1 && INSN_BB (ready
[i
]) != target_bb
)
5617 fprintf (dump
, "/b%d", INSN_BLOCK (ready
[i
]));
5619 fprintf (dump
, "\n");
5622 /* Print names of units on which insn can/should execute, for debugging. */
5625 insn_print_units (insn
)
5629 int unit
= insn_unit (insn
);
5632 fprintf (dump
, "none");
5634 fprintf (dump
, "%s", function_units
[unit
].name
);
5637 fprintf (dump
, "[");
5638 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
5641 fprintf (dump
, "%s", function_units
[i
].name
);
5643 fprintf (dump
, " ");
5645 fprintf (dump
, "]");
5649 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5650 of a basic block. If more lines are needed, table is splitted to two.
5651 n_visual_lines is the number of lines printed so far for a block.
5652 visual_tbl contains the block visualization info.
5653 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5654 #define MAX_VISUAL_LINES 100
5659 rtx vis_no_unit
[10];
5661 /* Finds units that are in use in this fuction. Required only
5662 for visualization. */
5665 init_target_units ()
5670 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
5672 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5675 unit
= insn_unit (insn
);
5678 target_units
|= ~unit
;
5680 target_units
|= (1 << unit
);
5684 /* Return the length of the visualization table. */
5687 get_visual_tbl_length ()
5693 /* Compute length of one field in line. */
5694 s
= (char *) alloca (INSN_LEN
+ 6);
5695 sprintf (s
, " %33s", "uname");
5698 /* Compute length of one line. */
5701 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5702 if (function_units
[unit
].bitmask
& target_units
)
5703 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5706 n
+= strlen ("\n") + 2;
5708 /* Compute length of visualization string. */
5709 return (MAX_VISUAL_LINES
* n
);
5712 /* Init block visualization debugging info. */
5715 init_block_visualization ()
5717 strcpy (visual_tbl
, "");
5725 safe_concat (buf
, cur
, str
)
5730 char *end
= buf
+ BUF_LEN
- 2; /* Leave room for null. */
5739 while (cur
< end
&& (c
= *str
++) != '\0')
5746 /* This recognizes rtx, I classified as expressions. These are always
5747 represent some action on values or results of other expression, that
5748 may be stored in objects representing values. */
5751 print_exp (buf
, x
, verbose
)
5759 const char *fun
= (char *)0;
5764 for (i
= 0; i
< 4; i
++)
5770 switch (GET_CODE (x
))
5773 op
[0] = XEXP (x
, 0);
5774 if (GET_CODE (XEXP (x
, 1)) == CONST_INT
5775 && INTVAL (XEXP (x
, 1)) < 0)
5778 op
[1] = GEN_INT (-INTVAL (XEXP (x
, 1)));
5783 op
[1] = XEXP (x
, 1);
5787 op
[0] = XEXP (x
, 0);
5789 op
[1] = XEXP (x
, 1);
5793 op
[0] = XEXP (x
, 0);
5795 op
[1] = XEXP (x
, 1);
5799 op
[0] = XEXP (x
, 0);
5800 op
[1] = XEXP (x
, 1);
5804 op
[0] = XEXP (x
, 0);
5807 op
[0] = XEXP (x
, 0);
5809 op
[1] = XEXP (x
, 1);
5812 op
[0] = XEXP (x
, 0);
5814 op
[1] = XEXP (x
, 1);
5818 op
[0] = XEXP (x
, 0);
5819 op
[1] = XEXP (x
, 1);
5822 op
[0] = XEXP (x
, 0);
5824 op
[1] = XEXP (x
, 1);
5828 op
[0] = XEXP (x
, 0);
5829 op
[1] = XEXP (x
, 1);
5833 op
[0] = XEXP (x
, 0);
5834 op
[1] = XEXP (x
, 1);
5838 op
[0] = XEXP (x
, 0);
5839 op
[1] = XEXP (x
, 1);
5843 op
[0] = XEXP (x
, 0);
5844 op
[1] = XEXP (x
, 1);
5848 op
[0] = XEXP (x
, 0);
5849 op
[1] = XEXP (x
, 1);
5853 op
[0] = XEXP (x
, 0);
5856 op
[0] = XEXP (x
, 0);
5858 op
[1] = XEXP (x
, 1);
5861 op
[0] = XEXP (x
, 0);
5863 op
[1] = XEXP (x
, 1);
5866 op
[0] = XEXP (x
, 0);
5868 op
[1] = XEXP (x
, 1);
5871 op
[0] = XEXP (x
, 0);
5873 op
[1] = XEXP (x
, 1);
5876 op
[0] = XEXP (x
, 0);
5878 op
[1] = XEXP (x
, 1);
5881 op
[0] = XEXP (x
, 0);
5883 op
[1] = XEXP (x
, 1);
5886 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);
5901 op
[0] = XEXP (x
, 0);
5905 op
[0] = XEXP (x
, 0);
5908 op
[0] = XEXP (x
, 0);
5910 op
[1] = XEXP (x
, 1);
5913 op
[0] = XEXP (x
, 0);
5915 op
[1] = XEXP (x
, 1);
5918 op
[0] = XEXP (x
, 0);
5920 op
[1] = XEXP (x
, 1);
5924 op
[0] = XEXP (x
, 0);
5925 op
[1] = XEXP (x
, 1);
5928 op
[0] = XEXP (x
, 0);
5930 op
[1] = XEXP (x
, 1);
5934 op
[0] = XEXP (x
, 0);
5935 op
[1] = XEXP (x
, 1);
5938 op
[0] = XEXP (x
, 0);
5940 op
[1] = XEXP (x
, 1);
5944 op
[0] = XEXP (x
, 0);
5945 op
[1] = XEXP (x
, 1);
5948 op
[0] = XEXP (x
, 0);
5950 op
[1] = XEXP (x
, 1);
5954 op
[0] = XEXP (x
, 0);
5955 op
[1] = XEXP (x
, 1);
5958 fun
= (verbose
) ? "sign_extract" : "sxt";
5959 op
[0] = XEXP (x
, 0);
5960 op
[1] = XEXP (x
, 1);
5961 op
[2] = XEXP (x
, 2);
5964 fun
= (verbose
) ? "zero_extract" : "zxt";
5965 op
[0] = XEXP (x
, 0);
5966 op
[1] = XEXP (x
, 1);
5967 op
[2] = XEXP (x
, 2);
5970 fun
= (verbose
) ? "sign_extend" : "sxn";
5971 op
[0] = XEXP (x
, 0);
5974 fun
= (verbose
) ? "zero_extend" : "zxn";
5975 op
[0] = XEXP (x
, 0);
5978 fun
= (verbose
) ? "float_extend" : "fxn";
5979 op
[0] = XEXP (x
, 0);
5982 fun
= (verbose
) ? "trunc" : "trn";
5983 op
[0] = XEXP (x
, 0);
5985 case FLOAT_TRUNCATE
:
5986 fun
= (verbose
) ? "float_trunc" : "ftr";
5987 op
[0] = XEXP (x
, 0);
5990 fun
= (verbose
) ? "float" : "flt";
5991 op
[0] = XEXP (x
, 0);
5993 case UNSIGNED_FLOAT
:
5994 fun
= (verbose
) ? "uns_float" : "ufl";
5995 op
[0] = XEXP (x
, 0);
5999 op
[0] = XEXP (x
, 0);
6002 fun
= (verbose
) ? "uns_fix" : "ufx";
6003 op
[0] = XEXP (x
, 0);
6007 op
[0] = XEXP (x
, 0);
6011 op
[0] = XEXP (x
, 0);
6014 op
[0] = XEXP (x
, 0);
6018 op
[0] = XEXP (x
, 0);
6023 op
[0] = XEXP (x
, 0);
6027 op
[1] = XEXP (x
, 1);
6032 op
[0] = XEXP (x
, 0);
6034 op
[1] = XEXP (x
, 1);
6036 op
[2] = XEXP (x
, 2);
6041 op
[0] = TRAP_CONDITION (x
);
6044 case UNSPEC_VOLATILE
:
6046 cur
= safe_concat (buf
, cur
, "unspec");
6047 if (GET_CODE (x
) == UNSPEC_VOLATILE
)
6048 cur
= safe_concat (buf
, cur
, "/v");
6049 cur
= safe_concat (buf
, cur
, "[");
6051 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6053 print_pattern (tmp
, XVECEXP (x
, 0, i
), verbose
);
6054 cur
= safe_concat (buf
, cur
, sep
);
6055 cur
= safe_concat (buf
, cur
, tmp
);
6058 cur
= safe_concat (buf
, cur
, "] ");
6059 sprintf (tmp
, "%d", XINT (x
, 1));
6060 cur
= safe_concat (buf
, cur
, tmp
);
6064 /* If (verbose) debug_rtx (x); */
6065 st
[0] = GET_RTX_NAME (GET_CODE (x
));
6069 /* Print this as a function? */
6072 cur
= safe_concat (buf
, cur
, fun
);
6073 cur
= safe_concat (buf
, cur
, "(");
6076 for (i
= 0; i
< 4; i
++)
6079 cur
= safe_concat (buf
, cur
, st
[i
]);
6084 cur
= safe_concat (buf
, cur
, ",");
6086 print_value (tmp
, op
[i
], verbose
);
6087 cur
= safe_concat (buf
, cur
, tmp
);
6092 cur
= safe_concat (buf
, cur
, ")");
6095 /* Prints rtxes, I customly classified as values. They're constants,
6096 registers, labels, symbols and memory accesses. */
6099 print_value (buf
, x
, verbose
)
6107 switch (GET_CODE (x
))
6110 sprintf (t
, HOST_WIDE_INT_PRINT_HEX
, INTVAL (x
));
6111 cur
= safe_concat (buf
, cur
, t
);
6114 sprintf (t
, "<0x%lx,0x%lx>", (long)XWINT (x
, 2), (long)XWINT (x
, 3));
6115 cur
= safe_concat (buf
, cur
, t
);
6118 cur
= safe_concat (buf
, cur
, "\"");
6119 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
6120 cur
= safe_concat (buf
, cur
, "\"");
6123 cur
= safe_concat (buf
, cur
, "`");
6124 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
6125 cur
= safe_concat (buf
, cur
, "'");
6128 sprintf (t
, "L%d", INSN_UID (XEXP (x
, 0)));
6129 cur
= safe_concat (buf
, cur
, t
);
6132 print_value (t
, XEXP (x
, 0), verbose
);
6133 cur
= safe_concat (buf
, cur
, "const(");
6134 cur
= safe_concat (buf
, cur
, t
);
6135 cur
= safe_concat (buf
, cur
, ")");
6138 print_value (t
, XEXP (x
, 0), verbose
);
6139 cur
= safe_concat (buf
, cur
, "high(");
6140 cur
= safe_concat (buf
, cur
, t
);
6141 cur
= safe_concat (buf
, cur
, ")");
6144 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
)
6146 int c
= reg_names
[ REGNO (x
) ][0];
6147 if (c
>= '0' && c
<= '9')
6148 cur
= safe_concat (buf
, cur
, "%");
6150 cur
= safe_concat (buf
, cur
, reg_names
[ REGNO (x
) ]);
6154 sprintf (t
, "r%d", REGNO (x
));
6155 cur
= safe_concat (buf
, cur
, t
);
6159 print_value (t
, SUBREG_REG (x
), verbose
);
6160 cur
= safe_concat (buf
, cur
, t
);
6161 sprintf (t
, "#%d", SUBREG_WORD (x
));
6162 cur
= safe_concat (buf
, cur
, t
);
6165 cur
= safe_concat (buf
, cur
, "scratch");
6168 cur
= safe_concat (buf
, cur
, "cc0");
6171 cur
= safe_concat (buf
, cur
, "pc");
6174 print_value (t
, XEXP (x
, 0), verbose
);
6175 cur
= safe_concat (buf
, cur
, "[");
6176 cur
= safe_concat (buf
, cur
, t
);
6177 cur
= safe_concat (buf
, cur
, "]");
6180 print_exp (t
, x
, verbose
);
6181 cur
= safe_concat (buf
, cur
, t
);
6186 /* The next step in insn detalization, its pattern recognition. */
6189 print_pattern (buf
, x
, verbose
)
6194 char t1
[BUF_LEN
], t2
[BUF_LEN
], t3
[BUF_LEN
];
6196 switch (GET_CODE (x
))
6199 print_value (t1
, SET_DEST (x
), verbose
);
6200 print_value (t2
, SET_SRC (x
), verbose
);
6201 sprintf (buf
, "%s=%s", t1
, t2
);
6204 sprintf (buf
, "return");
6207 print_exp (buf
, x
, verbose
);
6210 print_value (t1
, XEXP (x
, 0), verbose
);
6211 sprintf (buf
, "clobber %s", t1
);
6214 print_value (t1
, XEXP (x
, 0), verbose
);
6215 sprintf (buf
, "use %s", t1
);
6222 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6224 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6225 sprintf (t3
, "%s%s;", t1
, t2
);
6228 sprintf (buf
, "%s}", t1
);
6235 sprintf (t1
, "%%{");
6236 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6238 print_insn (t2
, XVECEXP (x
, 0, i
), verbose
);
6239 sprintf (t3
, "%s%s;", t1
, t2
);
6242 sprintf (buf
, "%s%%}", t1
);
6246 sprintf (buf
, "asm {%s}", XSTR (x
, 0));
6251 print_value (buf
, XEXP (x
, 0), verbose
);
6254 print_value (t1
, TRAP_CONDITION (x
), verbose
);
6255 sprintf (buf
, "trap_if %s", t1
);
6261 sprintf (t1
, "unspec{");
6262 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6264 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6265 sprintf (t3
, "%s%s;", t1
, t2
);
6268 sprintf (buf
, "%s}", t1
);
6271 case UNSPEC_VOLATILE
:
6275 sprintf (t1
, "unspec/v{");
6276 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6278 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6279 sprintf (t3
, "%s%s;", t1
, t2
);
6282 sprintf (buf
, "%s}", t1
);
6286 print_value (buf
, x
, verbose
);
6288 } /* print_pattern */
6290 /* This is the main function in rtl visualization mechanism. It
6291 accepts an rtx and tries to recognize it as an insn, then prints it
6292 properly in human readable form, resembling assembler mnemonics.
6293 For every insn it prints its UID and BB the insn belongs too.
6294 (Probably the last "option" should be extended somehow, since it
6295 depends now on sched.c inner variables ...) */
6298 print_insn (buf
, x
, verbose
)
6306 switch (GET_CODE (x
))
6309 print_pattern (t
, PATTERN (x
), verbose
);
6311 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (x
),
6314 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
6317 print_pattern (t
, PATTERN (x
), verbose
);
6319 sprintf (buf
, "b%d: i% 4d: jump %s", INSN_BB (x
),
6322 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
6326 if (GET_CODE (x
) == PARALLEL
)
6328 x
= XVECEXP (x
, 0, 0);
6329 print_pattern (t
, x
, verbose
);
6332 strcpy (t
, "call <...>");
6334 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (insn
),
6335 INSN_UID (insn
), t
);
6337 sprintf (buf
, "%-4d %s", INSN_UID (insn
), t
);
6340 sprintf (buf
, "L%d:", INSN_UID (x
));
6343 sprintf (buf
, "i% 4d: barrier", INSN_UID (x
));
6346 if (NOTE_LINE_NUMBER (x
) > 0)
6347 sprintf (buf
, "%4d note \"%s\" %d", INSN_UID (x
),
6348 NOTE_SOURCE_FILE (x
), NOTE_LINE_NUMBER (x
));
6350 sprintf (buf
, "%4d %s", INSN_UID (x
),
6351 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x
)));
6356 sprintf (buf
, "Not an INSN at all\n");
6360 sprintf (buf
, "i%-4d <What?>", INSN_UID (x
));
6364 /* Print visualization debugging info. */
6367 print_block_visualization (b
, s
)
6374 fprintf (dump
, "\n;; ==================== scheduling visualization for block %d %s \n", b
, s
);
6376 /* Print names of units. */
6377 fprintf (dump
, ";; %-8s", "clock");
6378 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6379 if (function_units
[unit
].bitmask
& target_units
)
6380 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6381 fprintf (dump
, " %-33s", function_units
[unit
].name
);
6382 fprintf (dump
, " %-8s\n", "no-unit");
6384 fprintf (dump
, ";; %-8s", "=====");
6385 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6386 if (function_units
[unit
].bitmask
& target_units
)
6387 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6388 fprintf (dump
, " %-33s", "==============================");
6389 fprintf (dump
, " %-8s\n", "=======");
6391 /* Print insns in each cycle. */
6392 fprintf (dump
, "%s\n", visual_tbl
);
6395 /* Print insns in the 'no_unit' column of visualization. */
6398 visualize_no_unit (insn
)
6401 vis_no_unit
[n_vis_no_unit
] = insn
;
6405 /* Print insns scheduled in clock, for visualization. */
6408 visualize_scheduled_insns (b
, clock
)
6413 /* If no more room, split table into two. */
6414 if (n_visual_lines
>= MAX_VISUAL_LINES
)
6416 print_block_visualization (b
, "(incomplete)");
6417 init_block_visualization ();
6422 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; %-8d", clock
);
6423 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6424 if (function_units
[unit
].bitmask
& target_units
)
6425 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6427 int instance
= unit
+ i
* FUNCTION_UNITS_SIZE
;
6428 rtx insn
= unit_last_insn
[instance
];
6430 /* Print insns that still keep the unit busy. */
6432 actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
6435 print_insn (str
, insn
, 0);
6436 str
[INSN_LEN
] = '\0';
6437 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", str
);
6440 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", "------------------------------");
6443 /* Print insns that are not assigned to any unit. */
6444 for (i
= 0; i
< n_vis_no_unit
; i
++)
6445 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-8d",
6446 INSN_UID (vis_no_unit
[i
]));
6449 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
6452 /* Print stalled cycles. */
6455 visualize_stall_cycles (b
, stalls
)
6460 /* If no more room, split table into two. */
6461 if (n_visual_lines
>= MAX_VISUAL_LINES
)
6463 print_block_visualization (b
, "(incomplete)");
6464 init_block_visualization ();
6469 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; ");
6470 for (i
= 0; i
< stalls
; i
++)
6471 sprintf (visual_tbl
+ strlen (visual_tbl
), ".");
6472 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
6475 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
6478 move_insn1 (insn
, last
)
6481 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
6482 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
6484 NEXT_INSN (insn
) = NEXT_INSN (last
);
6485 PREV_INSN (NEXT_INSN (last
)) = insn
;
6487 NEXT_INSN (last
) = insn
;
6488 PREV_INSN (insn
) = last
;
6493 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
6494 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
6495 NOTEs. The REG_DEAD note following first one is contains the saved
6496 value for NOTE_BLOCK_NUMBER which is useful for
6497 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
6498 output by the instruction scheduler. Return the new value of LAST. */
6501 reemit_notes (insn
, last
)
6508 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
6510 if (REG_NOTE_KIND (note
) == REG_DEAD
6511 && GET_CODE (XEXP (note
, 0)) == CONST_INT
)
6513 int note_type
= INTVAL (XEXP (note
, 0));
6514 if (note_type
== NOTE_INSN_SETJMP
)
6516 retval
= emit_note_after (NOTE_INSN_SETJMP
, insn
);
6517 CONST_CALL_P (retval
) = CONST_CALL_P (note
);
6518 remove_note (insn
, note
);
6519 note
= XEXP (note
, 1);
6521 else if (note_type
== NOTE_INSN_RANGE_START
6522 || note_type
== NOTE_INSN_RANGE_END
)
6524 last
= emit_note_before (note_type
, last
);
6525 remove_note (insn
, note
);
6526 note
= XEXP (note
, 1);
6527 NOTE_RANGE_INFO (last
) = XEXP (note
, 0);
6531 last
= emit_note_before (note_type
, last
);
6532 remove_note (insn
, note
);
6533 note
= XEXP (note
, 1);
6534 NOTE_BLOCK_NUMBER (last
) = INTVAL (XEXP (note
, 0));
6536 remove_note (insn
, note
);
6542 /* Move INSN, and all insns which should be issued before it,
6543 due to SCHED_GROUP_P flag. Reemit notes if needed.
6545 Return the last insn emitted by the scheduler, which is the
6546 return value from the first call to reemit_notes. */
6549 move_insn (insn
, last
)
6554 /* If INSN has SCHED_GROUP_P set, then issue it and any other
6555 insns with SCHED_GROUP_P set first. */
6556 while (SCHED_GROUP_P (insn
))
6558 rtx prev
= PREV_INSN (insn
);
6560 /* Move a SCHED_GROUP_P insn. */
6561 move_insn1 (insn
, last
);
6562 /* If this is the first call to reemit_notes, then record
6563 its return value. */
6564 if (retval
== NULL_RTX
)
6565 retval
= reemit_notes (insn
, insn
);
6567 reemit_notes (insn
, insn
);
6571 /* Now move the first non SCHED_GROUP_P insn. */
6572 move_insn1 (insn
, last
);
6574 /* If this is the first call to reemit_notes, then record
6575 its return value. */
6576 if (retval
== NULL_RTX
)
6577 retval
= reemit_notes (insn
, insn
);
6579 reemit_notes (insn
, insn
);
6584 /* Return an insn which represents a SCHED_GROUP, which is
6585 the last insn in the group. */
6596 insn
= next_nonnote_insn (insn
);
6598 while (insn
&& SCHED_GROUP_P (insn
) && (GET_CODE (insn
) != CODE_LABEL
));
6603 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
6604 possibly bringing insns from subsequent blocks in the same region.
6605 Return number of insns scheduled. */
6608 schedule_block (bb
, rgn_n_insns
)
6612 /* Local variables. */
6618 /* Flow block of this bb. */
6619 int b
= BB_TO_BLOCK (bb
);
6621 /* target_n_insns == number of insns in b before scheduling starts.
6622 sched_target_n_insns == how many of b's insns were scheduled.
6623 sched_n_insns == how many insns were scheduled in b. */
6624 int target_n_insns
= 0;
6625 int sched_target_n_insns
= 0;
6626 int sched_n_insns
= 0;
6628 #define NEED_NOTHING 0
6633 /* Head/tail info for this block. */
6640 /* We used to have code to avoid getting parameters moved from hard
6641 argument registers into pseudos.
6643 However, it was removed when it proved to be of marginal benefit
6644 and caused problems because schedule_block and compute_forward_dependences
6645 had different notions of what the "head" insn was. */
6646 get_block_head_tail (bb
, &head
, &tail
);
6648 /* Interblock scheduling could have moved the original head insn from this
6649 block into a proceeding block. This may also cause schedule_block and
6650 compute_forward_dependences to have different notions of what the
6653 If the interblock movement happened to make this block start with
6654 some notes (LOOP, EH or SETJMP) before the first real insn, then
6655 HEAD will have various special notes attached to it which must be
6656 removed so that we don't end up with extra copies of the notes. */
6657 if (GET_RTX_CLASS (GET_CODE (head
)) == 'i')
6661 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
6662 if (REG_NOTE_KIND (note
) == REG_DEAD
6663 && GET_CODE (XEXP (note
, 0)) == CONST_INT
)
6664 remove_note (head
, note
);
6667 next_tail
= NEXT_INSN (tail
);
6668 prev_head
= PREV_INSN (head
);
6670 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6671 to schedule this block. */
6673 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6674 return (sched_n_insns
);
6679 fprintf (dump
, ";; ======================================================\n");
6681 ";; -- basic block %d from %d to %d -- %s reload\n",
6682 b
, INSN_UID (BLOCK_HEAD (b
)), INSN_UID (BLOCK_END (b
)),
6683 (reload_completed
? "after" : "before"));
6684 fprintf (dump
, ";; ======================================================\n");
6685 fprintf (dump
, "\n");
6687 visual_tbl
= (char *) alloca (get_visual_tbl_length ());
6688 init_block_visualization ();
6691 /* Remove remaining note insns from the block, save them in
6692 note_list. These notes are restored at the end of
6693 schedule_block (). */
6695 rm_other_notes (head
, tail
);
6699 /* Prepare current target block info. */
6700 if (current_nr_blocks
> 1)
6702 candidate_table
= (candidate
*) alloca (current_nr_blocks
6703 * sizeof (candidate
));
6706 /* ??? It is not clear why bblst_size is computed this way. The original
6707 number was clearly too small as it resulted in compiler failures.
6708 Multiplying by the original number by 2 (to account for update_bbs
6709 members) seems to be a reasonable solution. */
6710 /* ??? Or perhaps there is a bug somewhere else in this file? */
6711 bblst_size
= (current_nr_blocks
- bb
) * rgn_nr_edges
* 2;
6712 bblst_table
= (int *) alloca (bblst_size
* sizeof (int));
6714 bitlst_table_last
= 0;
6715 bitlst_table_size
= rgn_nr_edges
;
6716 bitlst_table
= (int *) alloca (rgn_nr_edges
* sizeof (int));
6718 compute_trg_info (bb
);
6723 /* Allocate the ready list. */
6724 ready
= (rtx
*) alloca ((rgn_n_insns
+ 1) * sizeof (rtx
));
6726 /* Print debugging information. */
6727 if (sched_verbose
>= 5)
6728 debug_dependencies ();
6731 /* Initialize ready list with all 'ready' insns in target block.
6732 Count number of insns in the target block being scheduled. */
6734 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
6738 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6740 next
= NEXT_INSN (insn
);
6742 if (INSN_DEP_COUNT (insn
) == 0
6743 && (SCHED_GROUP_P (next
) == 0 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
6744 ready
[n_ready
++] = insn
;
6745 if (!(SCHED_GROUP_P (insn
)))
6749 /* Add to ready list all 'ready' insns in valid source blocks.
6750 For speculative insns, check-live, exception-free, and
6752 for (bb_src
= bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
6753 if (IS_VALID (bb_src
))
6759 get_block_head_tail (bb_src
, &head
, &tail
);
6760 src_next_tail
= NEXT_INSN (tail
);
6764 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6767 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
6769 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6772 if (!CANT_MOVE (insn
)
6773 && (!IS_SPECULATIVE_INSN (insn
)
6774 || (insn_issue_delay (insn
) <= 3
6775 && check_live (insn
, bb_src
)
6776 && is_exception_free (insn
, bb_src
, target_bb
))))
6781 /* Note that we havn't squirrled away the notes for
6782 blocks other than the current. So if this is a
6783 speculative insn, NEXT might otherwise be a note. */
6784 next
= next_nonnote_insn (insn
);
6785 if (INSN_DEP_COUNT (insn
) == 0
6786 && (SCHED_GROUP_P (next
) == 0
6787 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
6788 ready
[n_ready
++] = insn
;
6793 #ifdef MD_SCHED_INIT
6794 MD_SCHED_INIT (dump
, sched_verbose
);
6797 /* No insns scheduled in this block yet. */
6798 last_scheduled_insn
= 0;
6800 /* Q_SIZE is the total number of insns in the queue. */
6804 bzero ((char *) insn_queue
, sizeof (insn_queue
));
6806 /* Start just before the beginning of time. */
6809 /* We start inserting insns after PREV_HEAD. */
6812 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6813 new_needs
= (NEXT_INSN (prev_head
) == BLOCK_HEAD (b
)
6814 ? NEED_HEAD
: NEED_NOTHING
);
6815 if (PREV_INSN (next_tail
) == BLOCK_END (b
))
6816 new_needs
|= NEED_TAIL
;
6818 /* Loop until all the insns in BB are scheduled. */
6819 while (sched_target_n_insns
< target_n_insns
)
6825 /* Add to the ready list all pending insns that can be issued now.
6826 If there are no ready insns, increment clock until one
6827 is ready and add all pending insns at that point to the ready
6829 n_ready
= queue_to_ready (ready
, n_ready
);
6834 if (sched_verbose
>= 2)
6836 fprintf (dump
, ";;\t\tReady list after queue_to_ready: ");
6837 debug_ready_list (ready
, n_ready
);
6840 /* Sort the ready list based on priority. */
6841 SCHED_SORT (ready
, n_ready
);
6843 /* Allow the target to reorder the list, typically for
6844 better instruction bundling. */
6845 #ifdef MD_SCHED_REORDER
6846 MD_SCHED_REORDER (dump
, sched_verbose
, ready
, n_ready
, clock_var
,
6849 can_issue_more
= issue_rate
;
6854 fprintf (dump
, "\n;;\tReady list (t =%3d): ", clock_var
);
6855 debug_ready_list (ready
, n_ready
);
6858 /* Issue insns from ready list. */
6859 while (n_ready
!= 0 && can_issue_more
)
6861 /* Select and remove the insn from the ready list. */
6862 rtx insn
= ready
[--n_ready
];
6863 int cost
= actual_hazard (insn_unit (insn
), insn
, clock_var
, 0);
6867 queue_insn (insn
, cost
);
6871 /* An interblock motion? */
6872 if (INSN_BB (insn
) != target_bb
)
6876 if (IS_SPECULATIVE_INSN (insn
))
6878 if (!check_live (insn
, INSN_BB (insn
)))
6880 update_live (insn
, INSN_BB (insn
));
6882 /* For speculative load, mark insns fed by it. */
6883 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
6884 set_spec_fed (insn
);
6891 while (SCHED_GROUP_P (temp
))
6892 temp
= PREV_INSN (temp
);
6894 /* Update source block boundaries. */
6895 b1
= INSN_BLOCK (temp
);
6896 if (temp
== BLOCK_HEAD (b1
)
6897 && insn
== BLOCK_END (b1
))
6899 /* We moved all the insns in the basic block.
6900 Emit a note after the last insn and update the
6901 begin/end boundaries to point to the note. */
6902 emit_note_after (NOTE_INSN_DELETED
, insn
);
6903 BLOCK_END (b1
) = NEXT_INSN (insn
);
6904 BLOCK_HEAD (b1
) = NEXT_INSN (insn
);
6906 else if (insn
== BLOCK_END (b1
))
6908 /* We took insns from the end of the basic block,
6909 so update the end of block boundary so that it
6910 points to the first insn we did not move. */
6911 BLOCK_END (b1
) = PREV_INSN (temp
);
6913 else if (temp
== BLOCK_HEAD (b1
))
6915 /* We took insns from the start of the basic block,
6916 so update the start of block boundary so that
6917 it points to the first insn we did not move. */
6918 BLOCK_HEAD (b1
) = NEXT_INSN (insn
);
6923 /* In block motion. */
6924 sched_target_n_insns
++;
6927 last_scheduled_insn
= insn
;
6928 last
= move_insn (insn
, last
);
6931 #ifdef MD_SCHED_VARIABLE_ISSUE
6932 MD_SCHED_VARIABLE_ISSUE (dump
, sched_verbose
, insn
,
6938 n_ready
= schedule_insn (insn
, ready
, n_ready
, clock_var
);
6940 /* Close this block after scheduling its jump. */
6941 if (GET_CODE (last_scheduled_insn
) == JUMP_INSN
)
6947 visualize_scheduled_insns (b
, clock_var
);
6953 fprintf (dump
, ";;\tReady list (final): ");
6954 debug_ready_list (ready
, n_ready
);
6955 print_block_visualization (b
, "");
6958 /* Sanity check -- queue must be empty now. Meaningless if region has
6960 if (current_nr_blocks
> 1)
6961 if (!flag_schedule_interblock
&& q_size
!= 0)
6964 /* Update head/tail boundaries. */
6965 head
= NEXT_INSN (prev_head
);
6968 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6969 previously found among the insns. Insert them at the beginning
6973 rtx note_head
= note_list
;
6975 while (PREV_INSN (note_head
))
6977 note_head
= PREV_INSN (note_head
);
6980 PREV_INSN (note_head
) = PREV_INSN (head
);
6981 NEXT_INSN (PREV_INSN (head
)) = note_head
;
6982 PREV_INSN (head
) = note_list
;
6983 NEXT_INSN (note_list
) = head
;
6987 /* Update target block boundaries. */
6988 if (new_needs
& NEED_HEAD
)
6989 BLOCK_HEAD (b
) = head
;
6991 if (new_needs
& NEED_TAIL
)
6992 BLOCK_END (b
) = tail
;
6997 fprintf (dump
, ";; total time = %d\n;; new basic block head = %d\n",
6998 clock_var
, INSN_UID (BLOCK_HEAD (b
)));
6999 fprintf (dump
, ";; new basic block end = %d\n\n",
7000 INSN_UID (BLOCK_END (b
)));
7003 return (sched_n_insns
);
7004 } /* schedule_block () */
7007 /* Print the bit-set of registers, S, callable from debugger. */
7010 debug_reg_vector (s
)
7015 EXECUTE_IF_SET_IN_REG_SET (s
, 0, regno
,
7017 fprintf (dump
, " %d", regno
);
7020 fprintf (dump
, "\n");
7023 /* Use the backward dependences from LOG_LINKS to build
7024 forward dependences in INSN_DEPEND. */
7027 compute_block_forward_dependences (bb
)
7033 enum reg_note dep_type
;
7035 get_block_head_tail (bb
, &head
, &tail
);
7036 next_tail
= NEXT_INSN (tail
);
7037 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
7039 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
7042 insn
= group_leader (insn
);
7044 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
7046 rtx x
= group_leader (XEXP (link
, 0));
7049 if (x
!= XEXP (link
, 0))
7052 /* Ignore dependences upon deleted insn. */
7053 if (GET_CODE (x
) == NOTE
|| INSN_DELETED_P (x
))
7055 if (find_insn_list (insn
, INSN_DEPEND (x
)))
7058 new_link
= alloc_INSN_LIST (insn
, INSN_DEPEND (x
));
7060 dep_type
= REG_NOTE_KIND (link
);
7061 PUT_REG_NOTE_KIND (new_link
, dep_type
);
7063 INSN_DEPEND (x
) = new_link
;
7064 INSN_DEP_COUNT (insn
) += 1;
7069 /* Initialize variables for region data dependence analysis.
7070 n_bbs is the number of region blocks. */
7072 __inline
static void
7073 init_rgn_data_dependences (n_bbs
)
7078 /* Variables for which one copy exists for each block. */
7079 bzero ((char *) bb_pending_read_insns
, n_bbs
* sizeof (rtx
));
7080 bzero ((char *) bb_pending_read_mems
, n_bbs
* sizeof (rtx
));
7081 bzero ((char *) bb_pending_write_insns
, n_bbs
* sizeof (rtx
));
7082 bzero ((char *) bb_pending_write_mems
, n_bbs
* sizeof (rtx
));
7083 bzero ((char *) bb_pending_lists_length
, n_bbs
* sizeof (rtx
));
7084 bzero ((char *) bb_last_pending_memory_flush
, n_bbs
* sizeof (rtx
));
7085 bzero ((char *) bb_last_function_call
, n_bbs
* sizeof (rtx
));
7086 bzero ((char *) bb_sched_before_next_call
, n_bbs
* sizeof (rtx
));
7088 /* Create an insn here so that we can hang dependencies off of it later. */
7089 for (bb
= 0; bb
< n_bbs
; bb
++)
7091 bb_sched_before_next_call
[bb
] =
7092 gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
7093 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
7094 LOG_LINKS (bb_sched_before_next_call
[bb
]) = 0;
7098 /* Add dependences so that branches are scheduled to run last in their
7102 add_branch_dependences (head
, tail
)
7108 /* For all branches, calls, uses, and cc0 setters, force them to remain
7109 in order at the end of the block by adding dependencies and giving
7110 the last a high priority. There may be notes present, and prev_head
7113 Branches must obviously remain at the end. Calls should remain at the
7114 end since moving them results in worse register allocation. Uses remain
7115 at the end to ensure proper register allocation. cc0 setters remaim
7116 at the end because they can't be moved away from their cc0 user. */
7119 while (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
7120 || (GET_CODE (insn
) == INSN
7121 && (GET_CODE (PATTERN (insn
)) == USE
7123 || sets_cc0_p (PATTERN (insn
))
7126 || GET_CODE (insn
) == NOTE
)
7128 if (GET_CODE (insn
) != NOTE
)
7131 && !find_insn_list (insn
, LOG_LINKS (last
)))
7133 add_dependence (last
, insn
, REG_DEP_ANTI
);
7134 INSN_REF_COUNT (insn
)++;
7137 CANT_MOVE (insn
) = 1;
7140 /* Skip over insns that are part of a group.
7141 Make each insn explicitly depend on the previous insn.
7142 This ensures that only the group header will ever enter
7143 the ready queue (and, when scheduled, will automatically
7144 schedule the SCHED_GROUP_P block). */
7145 while (SCHED_GROUP_P (insn
))
7147 rtx temp
= prev_nonnote_insn (insn
);
7148 add_dependence (insn
, temp
, REG_DEP_ANTI
);
7153 /* Don't overrun the bounds of the basic block. */
7157 insn
= PREV_INSN (insn
);
7160 /* Make sure these insns are scheduled last in their block. */
7163 while (insn
!= head
)
7165 insn
= prev_nonnote_insn (insn
);
7167 if (INSN_REF_COUNT (insn
) != 0)
7170 add_dependence (last
, insn
, REG_DEP_ANTI
);
7171 INSN_REF_COUNT (insn
) = 1;
7173 /* Skip over insns that are part of a group. */
7174 while (SCHED_GROUP_P (insn
))
7175 insn
= prev_nonnote_insn (insn
);
7179 /* Compute backward dependences inside bb. In a multiple blocks region:
7180 (1) a bb is analyzed after its predecessors, and (2) the lists in
7181 effect at the end of bb (after analyzing for bb) are inherited by
7184 Specifically for reg-reg data dependences, the block insns are
7185 scanned by sched_analyze () top-to-bottom. Two lists are
7186 maintained by sched_analyze (): reg_last_sets[] for register DEFs,
7187 and reg_last_uses[] for register USEs.
7189 When analysis is completed for bb, we update for its successors:
7190 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7191 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7193 The mechanism for computing mem-mem data dependence is very
7194 similar, and the result is interblock dependences in the region. */
7197 compute_block_backward_dependences (bb
)
7203 int max_reg
= max_reg_num ();
7205 b
= BB_TO_BLOCK (bb
);
7207 if (current_nr_blocks
== 1)
7209 reg_last_uses
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7210 reg_last_sets
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7211 reg_last_clobbers
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7213 bzero ((char *) reg_last_uses
, max_reg
* sizeof (rtx
));
7214 bzero ((char *) reg_last_sets
, max_reg
* sizeof (rtx
));
7215 bzero ((char *) reg_last_clobbers
, max_reg
* sizeof (rtx
));
7217 pending_read_insns
= 0;
7218 pending_read_mems
= 0;
7219 pending_write_insns
= 0;
7220 pending_write_mems
= 0;
7221 pending_lists_length
= 0;
7222 last_function_call
= 0;
7223 last_pending_memory_flush
= 0;
7224 sched_before_next_call
7225 = gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
7226 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
7227 LOG_LINKS (sched_before_next_call
) = 0;
7231 reg_last_uses
= bb_reg_last_uses
[bb
];
7232 reg_last_sets
= bb_reg_last_sets
[bb
];
7233 reg_last_clobbers
= bb_reg_last_clobbers
[bb
];
7235 pending_read_insns
= bb_pending_read_insns
[bb
];
7236 pending_read_mems
= bb_pending_read_mems
[bb
];
7237 pending_write_insns
= bb_pending_write_insns
[bb
];
7238 pending_write_mems
= bb_pending_write_mems
[bb
];
7239 pending_lists_length
= bb_pending_lists_length
[bb
];
7240 last_function_call
= bb_last_function_call
[bb
];
7241 last_pending_memory_flush
= bb_last_pending_memory_flush
[bb
];
7243 sched_before_next_call
= bb_sched_before_next_call
[bb
];
7246 /* Do the analysis for this block. */
7247 get_block_head_tail (bb
, &head
, &tail
);
7248 sched_analyze (head
, tail
);
7249 add_branch_dependences (head
, tail
);
7251 if (current_nr_blocks
> 1)
7254 int b_succ
, bb_succ
;
7256 rtx link_insn
, link_mem
;
7259 /* These lists should point to the right place, for correct
7261 bb_pending_read_insns
[bb
] = pending_read_insns
;
7262 bb_pending_read_mems
[bb
] = pending_read_mems
;
7263 bb_pending_write_insns
[bb
] = pending_write_insns
;
7264 bb_pending_write_mems
[bb
] = pending_write_mems
;
7266 /* bb's structures are inherited by it's successors. */
7267 first_edge
= e
= OUT_EDGES (b
);
7271 b_succ
= TO_BLOCK (e
);
7272 bb_succ
= BLOCK_TO_BB (b_succ
);
7274 /* Only bbs "below" bb, in the same region, are interesting. */
7275 if (CONTAINING_RGN (b
) != CONTAINING_RGN (b_succ
)
7282 for (reg
= 0; reg
< max_reg
; reg
++)
7285 /* reg-last-uses lists are inherited by bb_succ. */
7286 for (u
= reg_last_uses
[reg
]; u
; u
= XEXP (u
, 1))
7288 if (find_insn_list (XEXP (u
, 0),
7289 (bb_reg_last_uses
[bb_succ
])[reg
]))
7292 (bb_reg_last_uses
[bb_succ
])[reg
]
7293 = alloc_INSN_LIST (XEXP (u
, 0),
7294 (bb_reg_last_uses
[bb_succ
])[reg
]);
7297 /* reg-last-defs lists are inherited by bb_succ. */
7298 for (u
= reg_last_sets
[reg
]; u
; u
= XEXP (u
, 1))
7300 if (find_insn_list (XEXP (u
, 0),
7301 (bb_reg_last_sets
[bb_succ
])[reg
]))
7304 (bb_reg_last_sets
[bb_succ
])[reg
]
7305 = alloc_INSN_LIST (XEXP (u
, 0),
7306 (bb_reg_last_sets
[bb_succ
])[reg
]);
7309 for (u
= reg_last_clobbers
[reg
]; u
; u
= XEXP (u
, 1))
7311 if (find_insn_list (XEXP (u
, 0),
7312 (bb_reg_last_clobbers
[bb_succ
])[reg
]))
7315 (bb_reg_last_clobbers
[bb_succ
])[reg
]
7316 = alloc_INSN_LIST (XEXP (u
, 0),
7317 (bb_reg_last_clobbers
[bb_succ
])[reg
]);
7321 /* Mem read/write lists are inherited by bb_succ. */
7322 link_insn
= pending_read_insns
;
7323 link_mem
= pending_read_mems
;
7326 if (!(find_insn_mem_list (XEXP (link_insn
, 0),
7328 bb_pending_read_insns
[bb_succ
],
7329 bb_pending_read_mems
[bb_succ
])))
7330 add_insn_mem_dependence (&bb_pending_read_insns
[bb_succ
],
7331 &bb_pending_read_mems
[bb_succ
],
7332 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
7333 link_insn
= XEXP (link_insn
, 1);
7334 link_mem
= XEXP (link_mem
, 1);
7337 link_insn
= pending_write_insns
;
7338 link_mem
= pending_write_mems
;
7341 if (!(find_insn_mem_list (XEXP (link_insn
, 0),
7343 bb_pending_write_insns
[bb_succ
],
7344 bb_pending_write_mems
[bb_succ
])))
7345 add_insn_mem_dependence (&bb_pending_write_insns
[bb_succ
],
7346 &bb_pending_write_mems
[bb_succ
],
7347 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
7349 link_insn
= XEXP (link_insn
, 1);
7350 link_mem
= XEXP (link_mem
, 1);
7353 /* last_function_call is inherited by bb_succ. */
7354 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
7356 if (find_insn_list (XEXP (u
, 0),
7357 bb_last_function_call
[bb_succ
]))
7360 bb_last_function_call
[bb_succ
]
7361 = alloc_INSN_LIST (XEXP (u
, 0),
7362 bb_last_function_call
[bb_succ
]);
7365 /* last_pending_memory_flush is inherited by bb_succ. */
7366 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
7368 if (find_insn_list (XEXP (u
, 0),
7369 bb_last_pending_memory_flush
[bb_succ
]))
7372 bb_last_pending_memory_flush
[bb_succ
]
7373 = alloc_INSN_LIST (XEXP (u
, 0),
7374 bb_last_pending_memory_flush
[bb_succ
]);
7377 /* sched_before_next_call is inherited by bb_succ. */
7378 x
= LOG_LINKS (sched_before_next_call
);
7379 for (; x
; x
= XEXP (x
, 1))
7380 add_dependence (bb_sched_before_next_call
[bb_succ
],
7381 XEXP (x
, 0), REG_DEP_ANTI
);
7385 while (e
!= first_edge
);
7388 /* Free up the INSN_LISTs.
7390 Note this loop is executed max_reg * nr_regions times. It's first
7391 implementation accounted for over 90% of the calls to free_INSN_LIST_list.
7392 The list was empty for the vast majority of those calls. On the PA, not
7393 calling free_INSN_LIST_list in those cases improves -O2 compile times by
7395 for (b
= 0; b
< max_reg
; ++b
)
7397 if (reg_last_clobbers
[b
])
7398 free_INSN_LIST_list (®_last_clobbers
[b
]);
7399 if (reg_last_sets
[b
])
7400 free_INSN_LIST_list (®_last_sets
[b
]);
7401 if (reg_last_uses
[b
])
7402 free_INSN_LIST_list (®_last_uses
[b
]);
7405 /* Assert that we won't need bb_reg_last_* for this block anymore. */
7406 if (current_nr_blocks
> 1)
7408 bb_reg_last_uses
[bb
] = (rtx
*) NULL_RTX
;
7409 bb_reg_last_sets
[bb
] = (rtx
*) NULL_RTX
;
7410 bb_reg_last_clobbers
[bb
] = (rtx
*) NULL_RTX
;
7414 /* Print dependences for debugging, callable from debugger. */
7417 debug_dependencies ()
7421 fprintf (dump
, ";; --------------- forward dependences: ------------ \n");
7422 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7430 get_block_head_tail (bb
, &head
, &tail
);
7431 next_tail
= NEXT_INSN (tail
);
7432 fprintf (dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
7433 BB_TO_BLOCK (bb
), bb
);
7435 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7436 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7437 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7438 "----", "----", "--", "---", "----", "----", "--------", "-----");
7439 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
7444 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
7447 fprintf (dump
, ";; %6d ", INSN_UID (insn
));
7448 if (GET_CODE (insn
) == NOTE
)
7450 n
= NOTE_LINE_NUMBER (insn
);
7452 fprintf (dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
7454 fprintf (dump
, "line %d, file %s\n", n
,
7455 NOTE_SOURCE_FILE (insn
));
7458 fprintf (dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
7462 unit
= insn_unit (insn
);
7464 || function_units
[unit
].blockage_range_function
== 0) ? 0 :
7465 function_units
[unit
].blockage_range_function (insn
);
7467 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7468 (SCHED_GROUP_P (insn
) ? "+" : " "),
7472 INSN_DEP_COUNT (insn
),
7473 INSN_PRIORITY (insn
),
7474 insn_cost (insn
, 0, 0),
7475 (int) MIN_BLOCKAGE_COST (range
),
7476 (int) MAX_BLOCKAGE_COST (range
));
7477 insn_print_units (insn
);
7478 fprintf (dump
, "\t: ");
7479 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
7480 fprintf (dump
, "%d ", INSN_UID (XEXP (link
, 0)));
7481 fprintf (dump
, "\n");
7485 fprintf (dump
, "\n");
7488 /* Set_priorities: compute priority of each insn in the block. */
7501 get_block_head_tail (bb
, &head
, &tail
);
7502 prev_head
= PREV_INSN (head
);
7505 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
7509 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
7512 if (GET_CODE (insn
) == NOTE
)
7515 if (!(SCHED_GROUP_P (insn
)))
7517 (void) priority (insn
);
7523 /* Make each element of VECTOR point at an rtx-vector,
7524 taking the space for all those rtx-vectors from SPACE.
7525 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7526 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7527 (this is the same as init_regset_vector () in flow.c) */
7530 init_rtx_vector (vector
, space
, nelts
, bytes_per_elt
)
7537 register rtx
*p
= space
;
7539 for (i
= 0; i
< nelts
; i
++)
7542 p
+= bytes_per_elt
/ sizeof (*p
);
7546 /* Schedule a region. A region is either an inner loop, a loop-free
7547 subroutine, or a single basic block. Each bb in the region is
7548 scheduled after its flow predecessors. */
7551 schedule_region (rgn
)
7555 int rgn_n_insns
= 0;
7556 int sched_rgn_n_insns
= 0;
7558 /* Set variables for the current region. */
7559 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
7560 current_blocks
= RGN_BLOCKS (rgn
);
7562 reg_pending_sets
= ALLOCA_REG_SET ();
7563 reg_pending_clobbers
= ALLOCA_REG_SET ();
7564 reg_pending_sets_all
= 0;
7566 /* Initializations for region data dependence analyisis. */
7567 if (current_nr_blocks
> 1)
7570 int maxreg
= max_reg_num ();
7572 bb_reg_last_uses
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7573 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7574 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7575 init_rtx_vector (bb_reg_last_uses
, space
, current_nr_blocks
,
7576 maxreg
* sizeof (rtx
*));
7578 bb_reg_last_sets
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7579 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7580 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7581 init_rtx_vector (bb_reg_last_sets
, space
, current_nr_blocks
,
7582 maxreg
* sizeof (rtx
*));
7584 bb_reg_last_clobbers
=
7585 (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7586 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7587 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7588 init_rtx_vector (bb_reg_last_clobbers
, space
, current_nr_blocks
,
7589 maxreg
* sizeof (rtx
*));
7591 bb_pending_read_insns
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7592 bb_pending_read_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7593 bb_pending_write_insns
=
7594 (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7595 bb_pending_write_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7596 bb_pending_lists_length
=
7597 (int *) alloca (current_nr_blocks
* sizeof (int));
7598 bb_last_pending_memory_flush
=
7599 (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7600 bb_last_function_call
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7601 bb_sched_before_next_call
=
7602 (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7604 init_rgn_data_dependences (current_nr_blocks
);
7607 /* Compute LOG_LINKS. */
7608 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7609 compute_block_backward_dependences (bb
);
7611 /* Compute INSN_DEPEND. */
7612 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
7613 compute_block_forward_dependences (bb
);
7615 /* Delete line notes, compute live-regs at block end, and set priorities. */
7617 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7619 if (reload_completed
== 0)
7620 find_pre_sched_live (bb
);
7622 if (write_symbols
!= NO_DEBUG
)
7624 save_line_notes (bb
);
7628 rgn_n_insns
+= set_priorities (bb
);
7631 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
7632 if (current_nr_blocks
> 1)
7636 prob
= (float *) alloca ((current_nr_blocks
) * sizeof (float));
7638 bbset_size
= current_nr_blocks
/ HOST_BITS_PER_WIDE_INT
+ 1;
7639 dom
= (bbset
*) alloca (current_nr_blocks
* sizeof (bbset
));
7640 for (i
= 0; i
< current_nr_blocks
; i
++)
7642 dom
[i
] = (bbset
) alloca (bbset_size
* sizeof (HOST_WIDE_INT
));
7643 bzero ((char *) dom
[i
], bbset_size
* sizeof (HOST_WIDE_INT
));
7648 edge_to_bit
= (int *) alloca (nr_edges
* sizeof (int));
7649 for (i
= 1; i
< nr_edges
; i
++)
7650 if (CONTAINING_RGN (FROM_BLOCK (i
)) == rgn
)
7651 EDGE_TO_BIT (i
) = rgn_nr_edges
++;
7652 rgn_edges
= (int *) alloca (rgn_nr_edges
* sizeof (int));
7655 for (i
= 1; i
< nr_edges
; i
++)
7656 if (CONTAINING_RGN (FROM_BLOCK (i
)) == (rgn
))
7657 rgn_edges
[rgn_nr_edges
++] = i
;
7660 edgeset_size
= rgn_nr_edges
/ HOST_BITS_PER_WIDE_INT
+ 1;
7661 pot_split
= (edgeset
*) alloca (current_nr_blocks
* sizeof (edgeset
));
7662 ancestor_edges
= (edgeset
*) alloca (current_nr_blocks
7663 * sizeof (edgeset
));
7664 for (i
= 0; i
< current_nr_blocks
; i
++)
7667 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
7668 bzero ((char *) pot_split
[i
],
7669 edgeset_size
* sizeof (HOST_WIDE_INT
));
7671 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
7672 bzero ((char *) ancestor_edges
[i
],
7673 edgeset_size
* sizeof (HOST_WIDE_INT
));
7676 /* Compute probabilities, dominators, split_edges. */
7677 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7678 compute_dom_prob_ps (bb
);
7681 /* Now we can schedule all blocks. */
7682 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7684 sched_rgn_n_insns
+= schedule_block (bb
, rgn_n_insns
);
7691 /* Sanity check: verify that all region insns were scheduled. */
7692 if (sched_rgn_n_insns
!= rgn_n_insns
)
7695 /* Update register life and usage information. */
7696 if (reload_completed
== 0)
7698 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
7699 find_post_sched_live (bb
);
7701 if (current_nr_blocks
<= 1)
7702 /* Sanity check. There should be no REG_DEAD notes leftover
7703 at the end. In practice, this can occur as the result of
7704 bugs in flow, combine.c, and/or sched.c. The values of the
7705 REG_DEAD notes remaining are meaningless, because
7706 dead_notes is just used as a free list. */
7707 if (dead_notes
!= 0)
7711 /* Restore line notes. */
7712 if (write_symbols
!= NO_DEBUG
)
7714 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7715 restore_line_notes (bb
);
7718 /* Done with this region. */
7719 free_pending_lists ();
7721 FREE_REG_SET (reg_pending_sets
);
7722 FREE_REG_SET (reg_pending_clobbers
);
7725 /* The one entry point in this file. DUMP_FILE is the dump file for
7729 schedule_insns (dump_file
)
7740 /* Disable speculative loads in their presence if cc0 defined. */
7742 flag_schedule_speculative_load
= 0;
7745 /* Taking care of this degenerate case makes the rest of
7746 this code simpler. */
7747 if (n_basic_blocks
== 0)
7750 /* Set dump and sched_verbose for the desired debugging output. If no
7751 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
7752 For -fsched-verbose-N, N>=10, print everything to stderr. */
7753 sched_verbose
= sched_verbose_param
;
7754 if (sched_verbose_param
== 0 && dump_file
)
7756 dump
= ((sched_verbose_param
>= 10 || !dump_file
) ? stderr
: dump_file
);
7761 /* Initialize issue_rate. */
7762 issue_rate
= ISSUE_RATE
;
7764 /* Do the splitting first for all blocks. */
7765 for (b
= 0; b
< n_basic_blocks
; b
++)
7766 split_block_insns (b
, 1);
7768 max_uid
= (get_max_uid () + 1);
7770 cant_move
= xcalloc (max_uid
, sizeof (char));
7771 fed_by_spec_load
= xcalloc (max_uid
, sizeof (char));
7772 is_load_insn
= xcalloc (max_uid
, sizeof (char));
7774 insn_orig_block
= (int *) xmalloc (max_uid
* sizeof (int));
7775 insn_luid
= (int *) xmalloc (max_uid
* sizeof (int));
7778 for (b
= 0; b
< n_basic_blocks
; b
++)
7779 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
7781 INSN_BLOCK (insn
) = b
;
7782 INSN_LUID (insn
) = luid
++;
7784 if (insn
== BLOCK_END (b
))
7788 /* After reload, remove inter-blocks dependences computed before reload. */
7789 if (reload_completed
)
7794 for (b
= 0; b
< n_basic_blocks
; b
++)
7795 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
7799 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
7802 link
= LOG_LINKS (insn
);
7805 rtx x
= XEXP (link
, 0);
7807 if (INSN_BLOCK (x
) != b
)
7809 remove_dependence (insn
, x
);
7810 link
= prev
? XEXP (prev
, 1) : LOG_LINKS (insn
);
7813 prev
= link
, link
= XEXP (prev
, 1);
7817 if (insn
== BLOCK_END (b
))
7823 rgn_table
= (region
*) alloca ((n_basic_blocks
) * sizeof (region
));
7824 rgn_bb_table
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
7825 block_to_bb
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
7826 containing_rgn
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
7828 /* Compute regions for scheduling. */
7829 if (reload_completed
7830 || n_basic_blocks
== 1
7831 || !flag_schedule_interblock
)
7833 find_single_block_region ();
7837 /* Verify that a 'good' control flow graph can be built. */
7838 if (is_cfg_nonregular ())
7840 find_single_block_region ();
7844 int_list_ptr
*s_preds
, *s_succs
;
7845 int *num_preds
, *num_succs
;
7846 sbitmap
*dom
, *pdom
;
7848 s_preds
= (int_list_ptr
*) alloca (n_basic_blocks
7849 * sizeof (int_list_ptr
));
7850 s_succs
= (int_list_ptr
*) alloca (n_basic_blocks
7851 * sizeof (int_list_ptr
));
7852 num_preds
= (int *) alloca (n_basic_blocks
* sizeof (int));
7853 num_succs
= (int *) alloca (n_basic_blocks
* sizeof (int));
7854 dom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
7855 pdom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
7857 /* The scheduler runs after flow; therefore, we can't blindly call
7858 back into find_basic_blocks since doing so could invalidate the
7859 info in global_live_at_start.
7861 Consider a block consisting entirely of dead stores; after life
7862 analysis it would be a block of NOTE_INSN_DELETED notes. If
7863 we call find_basic_blocks again, then the block would be removed
7864 entirely and invalidate our the register live information.
7866 We could (should?) recompute register live information. Doing
7867 so may even be beneficial. */
7869 compute_preds_succs (s_preds
, s_succs
, num_preds
, num_succs
);
7871 /* Compute the dominators and post dominators. We don't
7872 currently use post dominators, but we should for
7873 speculative motion analysis. */
7874 compute_dominators (dom
, pdom
, s_preds
, s_succs
);
7876 /* build_control_flow will return nonzero if it detects unreachable
7877 blocks or any other irregularity with the cfg which prevents
7878 cross block scheduling. */
7879 if (build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
) != 0)
7880 find_single_block_region ();
7882 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
);
7884 if (sched_verbose
>= 3)
7887 /* For now. This will move as more and more of haifa is converted
7888 to using the cfg code in flow.c. */
7895 /* Allocate data for this pass. See comments, above,
7896 for what these vectors do.
7898 We use xmalloc instead of alloca, because max_uid can be very large
7899 when there is a lot of function inlining. If we used alloca, we could
7900 exceed stack limits on some hosts for some inputs. */
7901 insn_priority
= (int *) xcalloc (max_uid
, sizeof (int));
7902 insn_reg_weight
= (int *) xcalloc (max_uid
, sizeof (int));
7903 insn_tick
= (int *) xcalloc (max_uid
, sizeof (int));
7904 insn_costs
= (short *) xcalloc (max_uid
, sizeof (short));
7905 insn_units
= (short *) xcalloc (max_uid
, sizeof (short));
7906 insn_blockage
= (unsigned int *) xcalloc (max_uid
, sizeof (unsigned int));
7907 insn_ref_count
= (int *) xcalloc (max_uid
, sizeof (int));
7909 /* Allocate for forward dependencies. */
7910 insn_dep_count
= (int *) xcalloc (max_uid
, sizeof (int));
7911 insn_depend
= (rtx
*) xcalloc (max_uid
, sizeof (rtx
));
7913 if (reload_completed
== 0)
7917 sched_reg_n_calls_crossed
= (int *) alloca (max_regno
* sizeof (int));
7918 sched_reg_live_length
= (int *) alloca (max_regno
* sizeof (int));
7919 sched_reg_basic_block
= (int *) alloca (max_regno
* sizeof (int));
7920 bb_live_regs
= ALLOCA_REG_SET ();
7921 bzero ((char *) sched_reg_n_calls_crossed
, max_regno
* sizeof (int));
7922 bzero ((char *) sched_reg_live_length
, max_regno
* sizeof (int));
7924 for (i
= 0; i
< max_regno
; i
++)
7925 sched_reg_basic_block
[i
] = REG_BLOCK_UNKNOWN
;
7929 sched_reg_n_calls_crossed
= 0;
7930 sched_reg_live_length
= 0;
7933 init_alias_analysis ();
7935 if (write_symbols
!= NO_DEBUG
)
7939 line_note
= (rtx
*) xcalloc (max_uid
, sizeof (rtx
));
7940 line_note_head
= (rtx
*) alloca (n_basic_blocks
* sizeof (rtx
));
7941 bzero ((char *) line_note_head
, n_basic_blocks
* sizeof (rtx
));
7943 /* Save-line-note-head:
7944 Determine the line-number at the start of each basic block.
7945 This must be computed and saved now, because after a basic block's
7946 predecessor has been scheduled, it is impossible to accurately
7947 determine the correct line number for the first insn of the block. */
7949 for (b
= 0; b
< n_basic_blocks
; b
++)
7950 for (line
= BLOCK_HEAD (b
); line
; line
= PREV_INSN (line
))
7951 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
7953 line_note_head
[b
] = line
;
7958 /* Find units used in this fuction, for visualization. */
7960 init_target_units ();
7962 /* ??? Add a NOTE after the last insn of the last basic block. It is not
7963 known why this is done. */
7965 insn
= BLOCK_END (n_basic_blocks
- 1);
7966 if (NEXT_INSN (insn
) == 0
7967 || (GET_CODE (insn
) != NOTE
7968 && GET_CODE (insn
) != CODE_LABEL
7969 /* Don't emit a NOTE if it would end up between an unconditional
7970 jump and a BARRIER. */
7971 && !(GET_CODE (insn
) == JUMP_INSN
7972 && GET_CODE (NEXT_INSN (insn
)) == BARRIER
)))
7973 emit_note_after (NOTE_INSN_DELETED
, BLOCK_END (n_basic_blocks
- 1));
7975 /* Schedule every region in the subroutine. */
7976 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
7978 schedule_region (rgn
);
7985 /* Reposition the prologue and epilogue notes in case we moved the
7986 prologue/epilogue insns. */
7987 if (reload_completed
)
7988 reposition_prologue_and_epilogue_notes (get_insns ());
7990 /* Delete redundant line notes. */
7991 if (write_symbols
!= NO_DEBUG
)
7992 rm_redundant_line_notes ();
7994 /* Update information about uses of registers in the subroutine. */
7995 if (reload_completed
== 0)
7996 update_reg_usage ();
8000 if (reload_completed
== 0 && flag_schedule_interblock
)
8002 fprintf (dump
, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8010 fprintf (dump
, "\n\n");
8014 free (fed_by_spec_load
);
8015 free (is_load_insn
);
8016 free (insn_orig_block
);
8019 free (insn_priority
);
8020 free (insn_reg_weight
);
8024 free (insn_blockage
);
8025 free (insn_ref_count
);
8027 free (insn_dep_count
);
8030 if (write_symbols
!= NO_DEBUG
)
8034 FREE_REG_SET (bb_live_regs
);
8053 #endif /* INSN_SCHEDULING */